1	/*
2	* Copyright 2008-2009 Katholieke Universiteit Leuven
3	* Copyright 2010 INRIA Saclay
4	* Copyright 2013-2014 Ecole Normale Superieure
5	* Copyright 2018-2019 Cerebras Systems
6	*
7	* Use of this software is governed by the MIT license
8	*
9	* Written by Sven Verdoolaege, K.U.Leuven, Departement
10	* Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
11	* and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
12	* ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
13	* and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14	* and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
15	*/
16
17	#include <stdlib.h>
18	#include <string.h>
19	#include <isl_space_private.h>
20	#include <isl_id_private.h>
21	#include <isl_reordering.h>
22
23	isl_ctx *isl_space_get_ctx(__isl_keep isl_space *space)
24	{
25	return space ? space->ctx : NULL;
26	}
27
28	__isl_give isl_space *isl_space_alloc(isl_ctx *ctx,
29	unsigned nparam, unsigned n_in, unsigned n_out)
30	{
31	isl_space *space;
32
33	space = isl_alloc_type(ctx, struct isl_space);
34	if (!space)
35	return NULL;
36
37	space->ctx = ctx;
38	isl_ctx_ref(ctx);
39	space->ref = 1;
40	space->nparam = nparam;
41	space->n_in = n_in;
42	space->n_out = n_out;
43
44	space->tuple_id[0] = NULL;
45	space->tuple_id[1] = NULL;
46
47	space->nested[0] = NULL;
48	space->nested[1] = NULL;
49
50	space->n_id = 0;
51	space->ids = NULL;
52
53	return space;
54	}
55
56	/* Mark the space as being that of a set, by setting the domain tuple
57	* to isl_id_none.
58	*/
59	static __isl_give isl_space *mark_as_set(__isl_take isl_space *space)
60	{
61	space = isl_space_cow(space);
62	if (!space)
63	return NULL;
64	space = isl_space_set_tuple_id(space, type: isl_dim_in, id: &isl_id_none);
65	return space;
66	}
67
68	/* Is the space that of a set?
69	*/
70	isl_bool isl_space_is_set(__isl_keep isl_space *space)
71	{
72	if (!space)
73	return isl_bool_error;
74	if (space->n_in != 0 || space->nested[0])
75	return isl_bool_false;
76	if (space->tuple_id[0] != &isl_id_none)
77	return isl_bool_false;
78	return isl_bool_true;
79	}
80
81	/* Check that "space" is a set space.
82	*/
83	isl_stat isl_space_check_is_set(__isl_keep isl_space *space)
84	{
85	isl_bool is_set;
86
87	is_set = isl_space_is_set(space);
88	if (is_set < 0)
89	return isl_stat_error;
90	if (!is_set)
91	isl_die(isl_space_get_ctx(space), isl_error_invalid,
92	"space is not a set", return isl_stat_error);
93	return isl_stat_ok;
94	}
95
96	/* Is the given space that of a map?
97	*/
98	isl_bool isl_space_is_map(__isl_keep isl_space *space)
99	{
100	int r;
101
102	if (!space)
103	return isl_bool_error;
104	r = space->tuple_id[0] != &isl_id_none &&
105	space->tuple_id[1] != &isl_id_none;
106	return isl_bool_ok(b: r);
107	}
108
109	/* Check that "space" is the space of a map.
110	*/
111	static isl_stat isl_space_check_is_map(__isl_keep isl_space *space)
112	{
113	isl_bool is_space;
114
115	is_space = isl_space_is_map(space);
116	if (is_space < 0)
117	return isl_stat_error;
118	if (!is_space)
119	isl_die(isl_space_get_ctx(space), isl_error_invalid,
120	"expecting map space", return isl_stat_error);
121	return isl_stat_ok;
122	}
123
124	/* Check that "space" is the space of a map
125	* where the domain is a wrapped map space.
126	*/
127	isl_stat isl_space_check_domain_is_wrapping(__isl_keep isl_space *space)
128	{
129	isl_bool wrapping;
130
131	wrapping = isl_space_domain_is_wrapping(space);
132	if (wrapping < 0)
133	return isl_stat_error;
134	if (!wrapping)
135	isl_die(isl_space_get_ctx(space), isl_error_invalid,
136	"domain not a product", return isl_stat_error);
137	return isl_stat_ok;
138	}
139
140	/* Check that "space" is the space of a map
141	* where the range is a wrapped map space.
142	*/
143	isl_stat isl_space_check_range_is_wrapping(__isl_keep isl_space *space)
144	{
145	isl_bool wrapping;
146
147	wrapping = isl_space_range_is_wrapping(space);
148	if (wrapping < 0)
149	return isl_stat_error;
150	if (!wrapping)
151	isl_die(isl_space_get_ctx(space), isl_error_invalid,
152	"range not a product", return isl_stat_error);
153	return isl_stat_ok;
154	}
155
156	__isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,
157	unsigned nparam, unsigned dim)
158	{
159	isl_space *space;
160	space = isl_space_alloc(ctx, nparam, n_in: 0, n_out: dim);
161	space = mark_as_set(space);
162	return space;
163	}
164
165	/* Mark the space as being that of a parameter domain, by setting
166	* both tuples to isl_id_none.
167	*/
168	static __isl_give isl_space *mark_as_params(isl_space *space)
169	{
170	if (!space)
171	return NULL;
172	space = isl_space_set_tuple_id(space, type: isl_dim_in, id: &isl_id_none);
173	space = isl_space_set_tuple_id(space, type: isl_dim_out, id: &isl_id_none);
174	return space;
175	}
176
177	/* Is the space that of a parameter domain?
178	*/
179	isl_bool isl_space_is_params(__isl_keep isl_space *space)
180	{
181	if (!space)
182	return isl_bool_error;
183	if (space->n_in != 0 || space->nested[0] ||
184	space->n_out != 0 || space->nested[1])
185	return isl_bool_false;
186	if (space->tuple_id[0] != &isl_id_none)
187	return isl_bool_false;
188	if (space->tuple_id[1] != &isl_id_none)
189	return isl_bool_false;
190	return isl_bool_true;
191	}
192
193	/* Create a space for a parameter domain.
194	*/
195	__isl_give isl_space *isl_space_params_alloc(isl_ctx *ctx, unsigned nparam)
196	{
197	isl_space *space;
198	space = isl_space_alloc(ctx, nparam, n_in: 0, n_out: 0);
199	space = mark_as_params(space);
200	return space;
201	}
202
203	/* Create a space for a parameter domain, without any parameters.
204	*/
205	__isl_give isl_space *isl_space_unit(isl_ctx *ctx)
206	{
207	return isl_space_params_alloc(ctx, nparam: 0);
208	}
209
210	static isl_size global_pos(__isl_keep isl_space *space,
211	enum isl_dim_type type, unsigned pos)
212	{
213	if (isl_space_check_range(space, type, first: pos, n: 1) < 0)
214	return isl_size_error;
215
216	switch (type) {
217	case isl_dim_param:
218	return pos;
219	case isl_dim_in:
220	return pos + space->nparam;
221	case isl_dim_out:
222	return pos + space->nparam + space->n_in;
223	default:
224	isl_assert(isl_space_get_ctx(space), 0, return isl_size_error);
225	}
226	return isl_size_error;
227	}
228
229	/* Extend length of ids array to the total number of dimensions.
230	*/
231	static __isl_give isl_space *extend_ids(__isl_take isl_space *space)
232	{
233	isl_id **ids;
234	int i;
235	isl_size dim;
236
237	dim = isl_space_dim(space, type: isl_dim_all);
238	if (dim < 0)
239	return isl_space_free(space);
240	if (dim <= space->n_id)
241	return space;
242
243	if (!space->ids) {
244	space->ids = isl_calloc_array(space->ctx, isl_id *, dim);
245	if (!space->ids)
246	goto error;
247	} else {
248	ids = isl_realloc_array(space->ctx, space->ids, isl_id *, dim);
249	if (!ids)
250	goto error;
251	space->ids = ids;
252	for (i = space->n_id; i < dim; ++i)
253	space->ids[i] = NULL;
254	}
255
256	space->n_id = dim;
257
258	return space;
259	error:
260	isl_space_free(space);
261	return NULL;
262	}
263
264	static __isl_give isl_space *set_id(__isl_take isl_space *space,
265	enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
266	{
267	isl_size gpos;
268
269	space = isl_space_cow(space);
270
271	gpos = global_pos(space, type, pos);
272	if (gpos < 0)
273	goto error;
274
275	if (gpos >= space->n_id) {
276	if (!id)
277	return space;
278	space = extend_ids(space);
279	if (!space)
280	goto error;
281	}
282
283	space->ids[gpos] = id;
284
285	return space;
286	error:
287	isl_id_free(id);
288	isl_space_free(space);
289	return NULL;
290	}
291
292	static __isl_keep isl_id *get_id(__isl_keep isl_space *space,
293	enum isl_dim_type type, unsigned pos)
294	{
295	isl_size gpos;
296
297	gpos = global_pos(space, type, pos);
298	if (gpos < 0)
299	return NULL;
300	if (gpos >= space->n_id)
301	return NULL;
302	return space->ids[gpos];
303	}
304
305	/* Return the nested space at the given position.
306	*/
307	static __isl_keep isl_space *isl_space_peek_nested(__isl_keep isl_space *space,
308	int pos)
309	{
310	if (!space)
311	return NULL;
312	if (!space->nested[pos])
313	isl_die(isl_space_get_ctx(space), isl_error_invalid,
314	"no nested space", return NULL);
315	return space->nested[pos];
316	}
317
318	static unsigned offset(__isl_keep isl_space *space, enum isl_dim_type type)
319	{
320	switch (type) {
321	case isl_dim_param: return 0;
322	case isl_dim_in: return space->nparam;
323	case isl_dim_out: return space->nparam + space->n_in;
324	default: return 0;
325	}
326	}
327
328	static unsigned n(__isl_keep isl_space *space, enum isl_dim_type type)
329	{
330	switch (type) {
331	case isl_dim_param: return space->nparam;
332	case isl_dim_in: return space->n_in;
333	case isl_dim_out: return space->n_out;
334	case isl_dim_all:
335	return space->nparam + space->n_in + space->n_out;
336	default: return 0;
337	}
338	}
339
340	isl_size isl_space_dim(__isl_keep isl_space *space, enum isl_dim_type type)
341	{
342	if (!space)
343	return isl_size_error;
344	return n(space, type);
345	}
346
347	/* Return the dimensionality of tuple "inner" within the wrapped relation
348	* inside tuple "outer".
349	*/
350	isl_size isl_space_wrapped_dim(__isl_keep isl_space *space,
351	enum isl_dim_type outer, enum isl_dim_type inner)
352	{
353	int pos;
354
355	if (!space)
356	return isl_size_error;
357	if (outer != isl_dim_in && outer != isl_dim_out)
358	isl_die(isl_space_get_ctx(space), isl_error_invalid,
359	"only input, output and set tuples "
360	"can have nested relations", return isl_size_error);
361	pos = outer - isl_dim_in;
362	return isl_space_dim(space: isl_space_peek_nested(space, pos), type: inner);
363	}
364
365	unsigned isl_space_offset(__isl_keep isl_space *space, enum isl_dim_type type)
366	{
367	if (!space)
368	return 0;
369	return offset(space, type);
370	}
371
372	static __isl_give isl_space *copy_ids(__isl_take isl_space *dst,
373	enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_space *src,
374	enum isl_dim_type src_type)
375	{
376	int i;
377	isl_id *id;
378
379	if (!dst)
380	return NULL;
381
382	for (i = 0; i < n(space: src, type: src_type); ++i) {
383	id = get_id(space: src, type: src_type, pos: i);
384	if (!id)
385	continue;
386	dst = set_id(space: dst, type: dst_type, pos: offset + i, id: isl_id_copy(id));
387	if (!dst)
388	return NULL;
389	}
390	return dst;
391	}
392
393	__isl_give isl_space *isl_space_dup(__isl_keep isl_space *space)
394	{
395	isl_space *dup;
396	if (!space)
397	return NULL;
398	dup = isl_space_alloc(ctx: space->ctx,
399	nparam: space->nparam, n_in: space->n_in, n_out: space->n_out);
400	if (!dup)
401	return NULL;
402	if (space->tuple_id[0] &&
403	!(dup->tuple_id[0] = isl_id_copy(id: space->tuple_id[0])))
404	goto error;
405	if (space->tuple_id[1] &&
406	!(dup->tuple_id[1] = isl_id_copy(id: space->tuple_id[1])))
407	goto error;
408	if (space->nested[0] &&
409	!(dup->nested[0] = isl_space_copy(space: space->nested[0])))
410	goto error;
411	if (space->nested[1] &&
412	!(dup->nested[1] = isl_space_copy(space: space->nested[1])))
413	goto error;
414	if (!space->ids)
415	return dup;
416	dup = copy_ids(dst: dup, dst_type: isl_dim_param, offset: 0, src: space, src_type: isl_dim_param);
417	dup = copy_ids(dst: dup, dst_type: isl_dim_in, offset: 0, src: space, src_type: isl_dim_in);
418	dup = copy_ids(dst: dup, dst_type: isl_dim_out, offset: 0, src: space, src_type: isl_dim_out);
419	return dup;
420	error:
421	isl_space_free(space: dup);
422	return NULL;
423	}
424
425	__isl_give isl_space *isl_space_cow(__isl_take isl_space *space)
426	{
427	if (!space)
428	return NULL;
429
430	if (space->ref == 1)
431	return space;
432	space->ref--;
433	return isl_space_dup(space);
434	}
435
436	__isl_give isl_space *isl_space_copy(__isl_keep isl_space *space)
437	{
438	if (!space)
439	return NULL;
440
441	space->ref++;
442	return space;
443	}
444
445	__isl_null isl_space *isl_space_free(__isl_take isl_space *space)
446	{
447	int i;
448
449	if (!space)
450	return NULL;
451
452	if (--space->ref > 0)
453	return NULL;
454
455	isl_id_free(id: space->tuple_id[0]);
456	isl_id_free(id: space->tuple_id[1]);
457
458	isl_space_free(space: space->nested[0]);
459	isl_space_free(space: space->nested[1]);
460
461	for (i = 0; i < space->n_id; ++i)
462	isl_id_free(id: space->ids[i]);
463	free(ptr: space->ids);
464	isl_ctx_deref(ctx: space->ctx);
465
466	free(ptr: space);
467
468	return NULL;
469	}
470
471	/* Check if "s" is a valid dimension or tuple name.
472	* We currently only forbid names that look like a number.
473	*
474	* s is assumed to be non-NULL.
475	*/
476	static int name_ok(isl_ctx *ctx, const char *s)
477	{
478	char *p;
479
480	strtol(nptr: s, endptr: &p, base: 0);
481	if (p != s)
482	isl_die(ctx, isl_error_invalid, "name looks like a number",
483	return 0);
484
485	return 1;
486	}
487
488	/* Return a copy of the nested space at the given position.
489	*/
490	static __isl_keep isl_space *isl_space_get_nested(__isl_keep isl_space *space,
491	int pos)
492	{
493	return isl_space_copy(space: isl_space_peek_nested(space, pos));
494	}
495
496	/* Return the nested space at the given position.
497	* This may be either a copy or the nested space itself
498	* if there is only one reference to "space".
499	* This allows the nested space to be modified inplace
500	* if both "space" and the nested space have only a single reference.
501	* The caller is not allowed to modify "space" between this call and
502	* a subsequent call to isl_space_restore_nested.
503	* The only exception is that isl_space_free can be called instead.
504	*/
505	static __isl_give isl_space *isl_space_take_nested(__isl_keep isl_space *space,
506	int pos)
507	{
508	isl_space *nested;
509
510	if (!space)
511	return NULL;
512	if (space->ref != 1)
513	return isl_space_get_nested(space, pos);
514	nested = space->nested[pos];
515	space->nested[pos] = NULL;
516	return nested;
517	}
518
519	/* Replace the nested space at the given position by "nested",
520	* where this nested space of "space" may be missing
521	* due to a preceding call to isl_space_take_nested.
522	* However, in this case, "space" only has a single reference and
523	* then the call to isl_space_cow has no effect.
524	*/
525	static __isl_give isl_space *isl_space_restore_nested(
526	__isl_take isl_space *space, int pos, __isl_take isl_space *nested)
527	{
528	if (!space || !nested)
529	goto error;
530
531	if (space->nested[pos] == nested) {
532	isl_space_free(space: nested);
533	return space;
534	}
535
536	space = isl_space_cow(space);
537	if (!space)
538	goto error;
539	isl_space_free(space: space->nested[pos]);
540	space->nested[pos] = nested;
541
542	return space;
543	error:
544	isl_space_free(space);
545	isl_space_free(space: nested);
546	return NULL;
547	}
548
549	/* Is it possible for the given dimension type to have a tuple id?
550	*/
551	static int space_can_have_id(__isl_keep isl_space *space,
552	enum isl_dim_type type)
553	{
554	if (!space)
555	return 0;
556	if (isl_space_is_params(space))
557	isl_die(space->ctx, isl_error_invalid,
558	"parameter spaces don't have tuple ids", return 0);
559	if (isl_space_is_set(space) && type != isl_dim_set)
560	isl_die(space->ctx, isl_error_invalid,
561	"set spaces can only have a set id", return 0);
562	if (type != isl_dim_in && type != isl_dim_out)
563	isl_die(space->ctx, isl_error_invalid,
564	"only input, output and set tuples can have ids",
565	return 0);
566
567	return 1;
568	}
569
570	/* Does the tuple have an id?
571	*/
572	isl_bool isl_space_has_tuple_id(__isl_keep isl_space *space,
573	enum isl_dim_type type)
574	{
575	if (!space_can_have_id(space, type))
576	return isl_bool_error;
577	return isl_bool_ok(b: space->tuple_id[type - isl_dim_in] != NULL);
578	}
579
580	/* Does the domain tuple of the map space "space" have an identifier?
581	*/
582	isl_bool isl_space_has_domain_tuple_id(__isl_keep isl_space *space)
583	{
584	if (isl_space_check_is_map(space) < 0)
585	return isl_bool_error;
586	return isl_space_has_tuple_id(space, type: isl_dim_in);
587	}
588
589	/* Does the range tuple of the map space "space" have an identifier?
590	*/
591	isl_bool isl_space_has_range_tuple_id(__isl_keep isl_space *space)
592	{
593	if (isl_space_check_is_map(space) < 0)
594	return isl_bool_error;
595	return isl_space_has_tuple_id(space, type: isl_dim_out);
596	}
597
598	__isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *space,
599	enum isl_dim_type type)
600	{
601	int has_id;
602
603	if (!space)
604	return NULL;
605	has_id = isl_space_has_tuple_id(space, type);
606	if (has_id < 0)
607	return NULL;
608	if (!has_id)
609	isl_die(space->ctx, isl_error_invalid,
610	"tuple has no id", return NULL);
611	return isl_id_copy(id: space->tuple_id[type - isl_dim_in]);
612	}
613
614	/* Return the identifier of the domain tuple of the map space "space",
615	* assuming it has one.
616	*/
617	__isl_give isl_id *isl_space_get_domain_tuple_id(
618	__isl_keep isl_space *space)
619	{
620	if (isl_space_check_is_map(space) < 0)
621	return NULL;
622	return isl_space_get_tuple_id(space, type: isl_dim_in);
623	}
624
625	/* Return the identifier of the range tuple of the map space "space",
626	* assuming it has one.
627	*/
628	__isl_give isl_id *isl_space_get_range_tuple_id(
629	__isl_keep isl_space *space)
630	{
631	if (isl_space_check_is_map(space) < 0)
632	return NULL;
633	return isl_space_get_tuple_id(space, type: isl_dim_out);
634	}
635
636	__isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *space,
637	enum isl_dim_type type, __isl_take isl_id *id)
638	{
639	space = isl_space_cow(space);
640	if (!space || !id)
641	goto error;
642	if (type != isl_dim_in && type != isl_dim_out)
643	isl_die(space->ctx, isl_error_invalid,
644	"only input, output and set tuples can have names",
645	goto error);
646
647	isl_id_free(id: space->tuple_id[type - isl_dim_in]);
648	space->tuple_id[type - isl_dim_in] = id;
649
650	return space;
651	error:
652	isl_id_free(id);
653	isl_space_free(space);
654	return NULL;
655	}
656
657	/* Replace the identifier of the domain tuple of the map space "space"
658	* by "id".
659	*/
660	__isl_give isl_space *isl_space_set_domain_tuple_id(
661	__isl_take isl_space *space, __isl_take isl_id *id)
662	{
663	if (isl_space_check_is_map(space) < 0)
664	space = isl_space_free(space);
665	return isl_space_set_tuple_id(space, type: isl_dim_in, id);
666	}
667
668	/* Replace the identifier of the range tuple of the map space "space"
669	* by "id".
670	*/
671	__isl_give isl_space *isl_space_set_range_tuple_id(
672	__isl_take isl_space *space, __isl_take isl_id *id)
673	{
674	if (isl_space_check_is_map(space) < 0)
675	space = isl_space_free(space);
676	return isl_space_set_tuple_id(space, type: isl_dim_out, id);
677	}
678
679	__isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *space,
680	enum isl_dim_type type)
681	{
682	space = isl_space_cow(space);
683	if (!space)
684	return NULL;
685	if (type != isl_dim_in && type != isl_dim_out)
686	isl_die(space->ctx, isl_error_invalid,
687	"only input, output and set tuples can have names",
688	goto error);
689
690	isl_id_free(id: space->tuple_id[type - isl_dim_in]);
691	space->tuple_id[type - isl_dim_in] = NULL;
692
693	return space;
694	error:
695	isl_space_free(space);
696	return NULL;
697	}
698
699	/* Set the id of the given dimension of "space" to "id".
700	* If the dimension already has an id, then it is replaced.
701	* If the dimension is a parameter, then we need to change it
702	* in the nested spaces (if any) as well.
703	*/
704	__isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *space,
705	enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
706	{
707	space = isl_space_cow(space);
708	if (!space || !id)
709	goto error;
710
711	if (type == isl_dim_param) {
712	int i;
713
714	for (i = 0; i < 2; ++i) {
715	if (!space->nested[i])
716	continue;
717	space->nested[i] =
718	isl_space_set_dim_id(space: space->nested[i],
719	type, pos, id: isl_id_copy(id));
720	if (!space->nested[i])
721	goto error;
722	}
723	}
724
725	isl_id_free(id: get_id(space, type, pos));
726	return set_id(space, type, pos, id);
727	error:
728	isl_id_free(id);
729	isl_space_free(space);
730	return NULL;
731	}
732
733	/* Reset the id of the given dimension of "space".
734	* If the dimension already has an id, then it is removed.
735	* If the dimension is a parameter, then we need to reset it
736	* in the nested spaces (if any) as well.
737	*/
738	__isl_give isl_space *isl_space_reset_dim_id(__isl_take isl_space *space,
739	enum isl_dim_type type, unsigned pos)
740	{
741	space = isl_space_cow(space);
742	if (!space)
743	goto error;
744
745	if (type == isl_dim_param) {
746	int i;
747
748	for (i = 0; i < 2; ++i) {
749	if (!space->nested[i])
750	continue;
751	space->nested[i] =
752	isl_space_reset_dim_id(space: space->nested[i],
753	type, pos);
754	if (!space->nested[i])
755	goto error;
756	}
757	}
758
759	isl_id_free(id: get_id(space, type, pos));
760	return set_id(space, type, pos, NULL);
761	error:
762	isl_space_free(space);
763	return NULL;
764	}
765
766	isl_bool isl_space_has_dim_id(__isl_keep isl_space *space,
767	enum isl_dim_type type, unsigned pos)
768	{
769	if (!space)
770	return isl_bool_error;
771	return isl_bool_ok(b: get_id(space, type, pos) != NULL);
772	}
773
774	__isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *space,
775	enum isl_dim_type type, unsigned pos)
776	{
777	if (!space)
778	return NULL;
779	if (!get_id(space, type, pos))
780	isl_die(space->ctx, isl_error_invalid,
781	"dim has no id", return NULL);
782	return isl_id_copy(id: get_id(space, type, pos));
783	}
784
785	__isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *space,
786	enum isl_dim_type type, const char *s)
787	{
788	isl_id *id;
789
790	if (!space)
791	return NULL;
792
793	if (!s)
794	return isl_space_reset_tuple_id(space, type);
795
796	if (!name_ok(ctx: space->ctx, s))
797	goto error;
798
799	id = isl_id_alloc(ctx: space->ctx, name: s, NULL);
800	return isl_space_set_tuple_id(space, type, id);
801	error:
802	isl_space_free(space);
803	return NULL;
804	}
805
806	/* Does the tuple have a name?
807	*/
808	isl_bool isl_space_has_tuple_name(__isl_keep isl_space *space,
809	enum isl_dim_type type)
810	{
811	isl_id *id;
812
813	if (!space_can_have_id(space, type))
814	return isl_bool_error;
815	id = space->tuple_id[type - isl_dim_in];
816	return isl_bool_ok(b: id && id->name);
817	}
818
819	__isl_keep const char *isl_space_get_tuple_name(__isl_keep isl_space *space,
820	enum isl_dim_type type)
821	{
822	isl_id *id;
823	if (!space)
824	return NULL;
825	if (type != isl_dim_in && type != isl_dim_out)
826	return NULL;
827	id = space->tuple_id[type - isl_dim_in];
828	return id ? id->name : NULL;
829	}
830
831	__isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *space,
832	enum isl_dim_type type, unsigned pos,
833	const char *s)
834	{
835	isl_id *id;
836
837	if (!space)
838	return NULL;
839	if (!s)
840	return isl_space_reset_dim_id(space, type, pos);
841	if (!name_ok(ctx: space->ctx, s))
842	goto error;
843	id = isl_id_alloc(ctx: space->ctx, name: s, NULL);
844	return isl_space_set_dim_id(space, type, pos, id);
845	error:
846	isl_space_free(space);
847	return NULL;
848	}
849
850	/* Does the given dimension have a name?
851	*/
852	isl_bool isl_space_has_dim_name(__isl_keep isl_space *space,
853	enum isl_dim_type type, unsigned pos)
854	{
855	isl_id *id;
856
857	if (!space)
858	return isl_bool_error;
859	id = get_id(space, type, pos);
860	return isl_bool_ok(b: id && id->name);
861	}
862
863	__isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *space,
864	enum isl_dim_type type, unsigned pos)
865	{
866	isl_id *id = get_id(space, type, pos);
867	return id ? id->name : NULL;
868	}
869
870	int isl_space_find_dim_by_id(__isl_keep isl_space *space,
871	enum isl_dim_type type, __isl_keep isl_id *id)
872	{
873	int i;
874	int offset;
875	isl_size n;
876
877	n = isl_space_dim(space, type);
878	if (n < 0 || !id)
879	return -1;
880
881	offset = isl_space_offset(space, type);
882	for (i = 0; i < n && offset + i < space->n_id; ++i)
883	if (space->ids[offset + i] == id)
884	return i;
885
886	return -1;
887	}
888
889	int isl_space_find_dim_by_name(__isl_keep isl_space *space,
890	enum isl_dim_type type, const char *name)
891	{
892	int i;
893	int offset;
894	isl_size n;
895
896	n = isl_space_dim(space, type);
897	if (n < 0 || !name)
898	return -1;
899
900	offset = isl_space_offset(space, type);
901	for (i = 0; i < n && offset + i < space->n_id; ++i) {
902	isl_id *id = get_id(space, type, pos: i);
903	if (id && id->name && !strcmp(s1: id->name, s2: name))
904	return i;
905	}
906
907	return -1;
908	}
909
910	/* Reset the user pointer on all identifiers of parameters and tuples
911	* of "space".
912	*/
913	__isl_give isl_space *isl_space_reset_user(__isl_take isl_space *space)
914	{
915	int i;
916	isl_ctx *ctx;
917	isl_id *id;
918	const char *name;
919
920	if (!space)
921	return NULL;
922
923	ctx = isl_space_get_ctx(space);
924
925	for (i = 0; i < space->nparam && i < space->n_id; ++i) {
926	if (!isl_id_get_user(id: space->ids[i]))
927	continue;
928	space = isl_space_cow(space);
929	if (!space)
930	return NULL;
931	name = isl_id_get_name(id: space->ids[i]);
932	id = isl_id_alloc(ctx, name, NULL);
933	isl_id_free(id: space->ids[i]);
934	space->ids[i] = id;
935	if (!id)
936	return isl_space_free(space);
937	}
938
939	for (i = 0; i < 2; ++i) {
940	if (!space->tuple_id[i])
941	continue;
942	if (!isl_id_get_user(id: space->tuple_id[i]))
943	continue;
944	space = isl_space_cow(space);
945	if (!space)
946	return NULL;
947	name = isl_id_get_name(id: space->tuple_id[i]);
948	id = isl_id_alloc(ctx, name, NULL);
949	isl_id_free(id: space->tuple_id[i]);
950	space->tuple_id[i] = id;
951	if (!id)
952	return isl_space_free(space);
953	}
954
955	for (i = 0; i < 2; ++i) {
956	isl_space *nested;
957
958	if (!space->nested[i])
959	continue;
960	nested = isl_space_take_nested(space, pos: i);
961	nested = isl_space_reset_user(space: nested);
962	space = isl_space_restore_nested(space, pos: i, nested);
963	if (!space)
964	return NULL;
965	}
966
967	return space;
968	}
969
970	static __isl_keep isl_id *tuple_id(__isl_keep isl_space *space,
971	enum isl_dim_type type)
972	{
973	if (!space)
974	return NULL;
975	if (type == isl_dim_in)
976	return space->tuple_id[0];
977	if (type == isl_dim_out)
978	return space->tuple_id[1];
979	return NULL;
980	}
981
982	static __isl_keep isl_space *nested(__isl_keep isl_space *space,
983	enum isl_dim_type type)
984	{
985	if (!space)
986	return NULL;
987	if (type == isl_dim_in)
988	return space->nested[0];
989	if (type == isl_dim_out)
990	return space->nested[1];
991	return NULL;
992	}
993
994	/* Are the two spaces the same, apart from positions and names of parameters?
995	*/
996	isl_bool isl_space_has_equal_tuples(__isl_keep isl_space *space1,
997	__isl_keep isl_space *space2)
998	{
999	if (!space1 || !space2)
1000	return isl_bool_error;
1001	if (space1 == space2)
1002	return isl_bool_true;
1003	return isl_space_tuple_is_equal(space1, type1: isl_dim_in,
1004	space2, type2: isl_dim_in) &&
1005	isl_space_tuple_is_equal(space1, type1: isl_dim_out,
1006	space2, type2: isl_dim_out);
1007	}
1008
1009	/* Check that a match involving "space" was successful.
1010	* That is, check that "match" is equal to isl_bool_true.
1011	*/
1012	static isl_stat check_match(__isl_keep isl_space *space, isl_bool match)
1013	{
1014	if (match < 0)
1015	return isl_stat_error;
1016	if (!match)
1017	isl_die(isl_space_get_ctx(space), isl_error_invalid,
1018	"incompatible spaces", return isl_stat_error);
1019
1020	return isl_stat_ok;
1021	}
1022
1023	/* Check that the two spaces are the same,
1024	* apart from positions and names of parameters.
1025	*/
1026	isl_stat isl_space_check_equal_tuples(__isl_keep isl_space *space1,
1027	__isl_keep isl_space *space2)
1028	{
1029	isl_bool is_equal;
1030
1031	is_equal = isl_space_has_equal_tuples(space1, space2);
1032	return check_match(space: space1, match: is_equal);
1033	}
1034
1035	/* Check if the tuple of type "type1" of "space1" is the same as
1036	* the tuple of type "type2" of "space2".
1037	*
1038	* That is, check if the tuples have the same identifier, the same dimension
1039	* and the same internal structure.
1040	* The identifiers of the dimensions inside the tuples do not affect the result.
1041	*
1042	* Note that this function only checks the tuples themselves.
1043	* If nested tuples are involved, then we need to be careful not
1044	* to have result affected by possibly differing parameters
1045	* in those nested tuples.
1046	*/
1047	isl_bool isl_space_tuple_is_equal(__isl_keep isl_space *space1,
1048	enum isl_dim_type type1, __isl_keep isl_space *space2,
1049	enum isl_dim_type type2)
1050	{
1051	isl_id *id1, *id2;
1052	isl_space *nested1, *nested2;
1053
1054	if (!space1 || !space2)
1055	return isl_bool_error;
1056
1057	if (space1 == space2 && type1 == type2)
1058	return isl_bool_true;
1059
1060	if (n(space: space1, type: type1) != n(space: space2, type: type2))
1061	return isl_bool_false;
1062	id1 = tuple_id(space: space1, type: type1);
1063	id2 = tuple_id(space: space2, type: type2);
1064	if (!id1 ^ !id2)
1065	return isl_bool_false;
1066	if (id1 && id1 != id2)
1067	return isl_bool_false;
1068	nested1 = nested(space: space1, type: type1);
1069	nested2 = nested(space: space2, type: type2);
1070	if (!nested1 ^ !nested2)
1071	return isl_bool_false;
1072	if (nested1 && !isl_space_has_equal_tuples(space1: nested1, space2: nested2))
1073	return isl_bool_false;
1074	return isl_bool_true;
1075	}
1076
1077	/* Is the tuple "inner" within the wrapped relation inside tuple "outer"
1078	* of "space1" equal to tuple "type2" of "space2"?
1079	*/
1080	isl_bool isl_space_wrapped_tuple_is_equal(__isl_keep isl_space *space1,
1081	enum isl_dim_type outer, enum isl_dim_type inner,
1082	__isl_keep isl_space *space2, enum isl_dim_type type2)
1083	{
1084	int pos;
1085	isl_space *nested;
1086
1087	if (!space1)
1088	return isl_bool_error;
1089	if (outer != isl_dim_in && outer != isl_dim_out)
1090	isl_die(isl_space_get_ctx(space1), isl_error_invalid,
1091	"only input, output and set tuples "
1092	"can have nested relations", return isl_bool_error);
1093	pos = outer - isl_dim_in;
1094	nested = isl_space_peek_nested(space: space1, pos);
1095	return isl_space_tuple_is_equal(space1: nested, type1: inner, space2, type2);
1096	}
1097
1098	/* Check that the tuple "inner" within the wrapped relation inside tuple "outer"
1099	* of "space1" is equal to tuple "type2" of "space2".
1100	*/
1101	isl_stat isl_space_check_wrapped_tuple_is_equal(__isl_keep isl_space *space1,
1102	enum isl_dim_type outer, enum isl_dim_type inner,
1103	__isl_keep isl_space *space2, enum isl_dim_type type2)
1104	{
1105	isl_bool is_equal;
1106
1107	is_equal = isl_space_wrapped_tuple_is_equal(space1, outer, inner,
1108	space2, type2);
1109	return check_match(space: space1, match: is_equal);
1110	}
1111
1112	static isl_bool match(__isl_keep isl_space *space1, enum isl_dim_type type1,
1113	__isl_keep isl_space *space2, enum isl_dim_type type2)
1114	{
1115	int i;
1116	isl_bool equal;
1117
1118	if (!space1 || !space2)
1119	return isl_bool_error;
1120
1121	if (space1 == space2 && type1 == type2)
1122	return isl_bool_true;
1123
1124	equal = isl_space_tuple_is_equal(space1, type1, space2, type2);
1125	if (equal < 0 || !equal)
1126	return equal;
1127
1128	if (!space1->ids && !space2->ids)
1129	return isl_bool_true;
1130
1131	for (i = 0; i < n(space: space1, type: type1); ++i) {
1132	if (get_id(space: space1, type: type1, pos: i) != get_id(space: space2, type: type2, pos: i))
1133	return isl_bool_false;
1134	}
1135	return isl_bool_true;
1136	}
1137
1138	/* Do "space1" and "space2" have the same parameters?
1139	*/
1140	isl_bool isl_space_has_equal_params(__isl_keep isl_space *space1,
1141	__isl_keep isl_space *space2)
1142	{
1143	return match(space1, type1: isl_dim_param, space2, type2: isl_dim_param);
1144	}
1145
1146	/* Do "space1" and "space2" have the same identifiers for all
1147	* the tuple variables?
1148	*/
1149	isl_bool isl_space_has_equal_ids(__isl_keep isl_space *space1,
1150	__isl_keep isl_space *space2)
1151	{
1152	isl_bool equal;
1153
1154	equal = match(space1, type1: isl_dim_in, space2, type2: isl_dim_in);
1155	if (equal < 0 || !equal)
1156	return equal;
1157	return match(space1, type1: isl_dim_out, space2, type2: isl_dim_out);
1158	}
1159
1160	isl_bool isl_space_match(__isl_keep isl_space *space1, enum isl_dim_type type1,
1161	__isl_keep isl_space *space2, enum isl_dim_type type2)
1162	{
1163	return match(space1, type1, space2, type2);
1164	}
1165
1166	static void get_ids(__isl_keep isl_space *space, enum isl_dim_type type,
1167	unsigned first, unsigned n, __isl_keep isl_id **ids)
1168	{
1169	int i;
1170
1171	for (i = 0; i < n ; ++i)
1172	ids[i] = get_id(space, type, pos: first + i);
1173	}
1174
1175	static __isl_give isl_space *space_extend(__isl_take isl_space *space,
1176	unsigned nparam, unsigned n_in, unsigned n_out)
1177	{
1178	isl_id **ids = NULL;
1179
1180	if (!space)
1181	return NULL;
1182	if (space->nparam == nparam &&
1183	space->n_in == n_in && space->n_out == n_out)
1184	return space;
1185
1186	isl_assert(space->ctx, space->nparam <= nparam, goto error);
1187	isl_assert(space->ctx, space->n_in <= n_in, goto error);
1188	isl_assert(space->ctx, space->n_out <= n_out, goto error);
1189
1190	space = isl_space_cow(space);
1191	if (!space)
1192	goto error;
1193
1194	if (space->ids) {
1195	unsigned n;
1196	n = nparam + n_in + n_out;
1197	if (n < nparam || n < n_in || n < n_out)
1198	isl_die(isl_space_get_ctx(space), isl_error_invalid,
1199	"overflow in total number of dimensions",
1200	goto error);
1201	ids = isl_calloc_array(space->ctx, isl_id *, n);
1202	if (!ids)
1203	goto error;
1204	get_ids(space, type: isl_dim_param, first: 0, n: space->nparam, ids);
1205	get_ids(space, type: isl_dim_in, first: 0, n: space->n_in, ids: ids + nparam);
1206	get_ids(space, type: isl_dim_out, first: 0, n: space->n_out,
1207	ids: ids + nparam + n_in);
1208	free(ptr: space->ids);
1209	space->ids = ids;
1210	space->n_id = nparam + n_in + n_out;
1211	}
1212	space->nparam = nparam;
1213	space->n_in = n_in;
1214	space->n_out = n_out;
1215
1216	return space;
1217	error:
1218	free(ptr: ids);
1219	isl_space_free(space);
1220	return NULL;
1221	}
1222
1223	__isl_give isl_space *isl_space_extend(__isl_take isl_space *space,
1224	unsigned nparam, unsigned n_in, unsigned n_out)
1225	{
1226	return space_extend(space, nparam, n_in, n_out);
1227	}
1228
1229	__isl_give isl_space *isl_space_add_dims(__isl_take isl_space *space,
1230	enum isl_dim_type type, unsigned n)
1231	{
1232	space = isl_space_reset(space, type);
1233	if (!space)
1234	return NULL;
1235	switch (type) {
1236	case isl_dim_param:
1237	space = space_extend(space,
1238	nparam: space->nparam + n, n_in: space->n_in, n_out: space->n_out);
1239	if (space && space->nested[0] &&
1240	!(space->nested[0] = isl_space_add_dims(space: space->nested[0],
1241	type: isl_dim_param, n)))
1242	goto error;
1243	if (space && space->nested[1] &&
1244	!(space->nested[1] = isl_space_add_dims(space: space->nested[1],
1245	type: isl_dim_param, n)))
1246	goto error;
1247	return space;
1248	case isl_dim_in:
1249	return space_extend(space,
1250	nparam: space->nparam, n_in: space->n_in + n, n_out: space->n_out);
1251	case isl_dim_out:
1252	return space_extend(space,
1253	nparam: space->nparam, n_in: space->n_in, n_out: space->n_out + n);
1254	default:
1255	isl_die(space->ctx, isl_error_invalid,
1256	"cannot add dimensions of specified type", goto error);
1257	}
1258	error:
1259	isl_space_free(space);
1260	return NULL;
1261	}
1262
1263	/* Add a parameter with identifier "id" to "space", provided
1264	* it does not already appear in "space".
1265	*/
1266	__isl_give isl_space *isl_space_add_param_id(__isl_take isl_space *space,
1267	__isl_take isl_id *id)
1268	{
1269	isl_size pos;
1270
1271	if (!space || !id)
1272	goto error;
1273
1274	if (isl_space_find_dim_by_id(space, type: isl_dim_param, id) >= 0) {
1275	isl_id_free(id);
1276	return space;
1277	}
1278
1279	pos = isl_space_dim(space, type: isl_dim_param);
1280	if (pos < 0)
1281	goto error;
1282	space = isl_space_add_dims(space, type: isl_dim_param, n: 1);
1283	space = isl_space_set_dim_id(space, type: isl_dim_param, pos, id);
1284
1285	return space;
1286	error:
1287	isl_space_free(space);
1288	isl_id_free(id);
1289	return NULL;
1290	}
1291
1292	static int valid_dim_type(enum isl_dim_type type)
1293	{
1294	switch (type) {
1295	case isl_dim_param:
1296	case isl_dim_in:
1297	case isl_dim_out:
1298	return 1;
1299	default:
1300	return 0;
1301	}
1302	}
1303
1304	#undef TYPE
1305	#define TYPE isl_space
1306	#include "check_type_range_templ.c"
1307
1308	/* Insert "n" dimensions of type "type" at position "pos".
1309	* If we are inserting parameters, then they are also inserted in
1310	* any nested spaces.
1311	*/
1312	__isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *space,
1313	enum isl_dim_type type, unsigned pos, unsigned n)
1314	{
1315	isl_ctx *ctx;
1316	isl_id **ids = NULL;
1317
1318	if (!space)
1319	return NULL;
1320	if (n == 0)
1321	return isl_space_reset(space, type);
1322
1323	ctx = isl_space_get_ctx(space);
1324	if (!valid_dim_type(type))
1325	isl_die(ctx, isl_error_invalid,
1326	"cannot insert dimensions of specified type",
1327	goto error);
1328
1329	if (isl_space_check_range(obj: space, type, first: pos, n: 0) < 0)
1330	return isl_space_free(space);
1331
1332	space = isl_space_cow(space);
1333	if (!space)
1334	return NULL;
1335
1336	if (space->ids) {
1337	enum isl_dim_type t, o = isl_dim_param;
1338	int off;
1339	int s[3];
1340	ids = isl_calloc_array(ctx, isl_id *,
1341	space->nparam + space->n_in + space->n_out + n);
1342	if (!ids)
1343	goto error;
1344	off = 0;
1345	s[isl_dim_param - o] = space->nparam;
1346	s[isl_dim_in - o] = space->n_in;
1347	s[isl_dim_out - o] = space->n_out;
1348	for (t = isl_dim_param; t <= isl_dim_out; ++t) {
1349	if (t != type) {
1350	get_ids(space, type: t, first: 0, n: s[t - o], ids: ids + off);
1351	off += s[t - o];
1352	} else {
1353	get_ids(space, type: t, first: 0, n: pos, ids: ids + off);
1354	off += pos + n;
1355	get_ids(space, type: t, first: pos, n: s[t - o] - pos,
1356	ids: ids + off);
1357	off += s[t - o] - pos;
1358	}
1359	}
1360	free(ptr: space->ids);
1361	space->ids = ids;
1362	space->n_id = space->nparam + space->n_in + space->n_out + n;
1363	}
1364	switch (type) {
1365	case isl_dim_param: space->nparam += n; break;
1366	case isl_dim_in: space->n_in += n; break;
1367	case isl_dim_out: space->n_out += n; break;
1368	default: ;
1369	}
1370	space = isl_space_reset(space, type);
1371
1372	if (type == isl_dim_param) {
1373	if (space && space->nested[0] &&
1374	!(space->nested[0] = isl_space_insert_dims(space: space->nested[0],
1375	type: isl_dim_param, pos, n)))
1376	goto error;
1377	if (space && space->nested[1] &&
1378	!(space->nested[1] = isl_space_insert_dims(space: space->nested[1],
1379	type: isl_dim_param, pos, n)))
1380	goto error;
1381	}
1382
1383	return space;
1384	error:
1385	isl_space_free(space);
1386	return NULL;
1387	}
1388
1389	__isl_give isl_space *isl_space_move_dims(__isl_take isl_space *space,
1390	enum isl_dim_type dst_type, unsigned dst_pos,
1391	enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1392	{
1393	int i;
1394
1395	space = isl_space_reset(space, type: src_type);
1396	space = isl_space_reset(space, type: dst_type);
1397	if (!space)
1398	return NULL;
1399	if (n == 0)
1400	return space;
1401
1402	if (isl_space_check_range(obj: space, type: src_type, first: src_pos, n) < 0)
1403	return isl_space_free(space);
1404
1405	if (dst_type == src_type && dst_pos == src_pos)
1406	return space;
1407
1408	isl_assert(space->ctx, dst_type != src_type, goto error);
1409
1410	space = isl_space_cow(space);
1411	if (!space)
1412	return NULL;
1413
1414	if (space->ids) {
1415	isl_id **ids;
1416	enum isl_dim_type t, o = isl_dim_param;
1417	int off;
1418	int s[3];
1419	ids = isl_calloc_array(space->ctx, isl_id *,
1420	space->nparam + space->n_in + space->n_out);
1421	if (!ids)
1422	goto error;
1423	off = 0;
1424	s[isl_dim_param - o] = space->nparam;
1425	s[isl_dim_in - o] = space->n_in;
1426	s[isl_dim_out - o] = space->n_out;
1427	for (t = isl_dim_param; t <= isl_dim_out; ++t) {
1428	if (t == dst_type) {
1429	get_ids(space, type: t, first: 0, n: dst_pos, ids: ids + off);
1430	off += dst_pos;
1431	get_ids(space, type: src_type, first: src_pos, n, ids: ids + off);
1432	off += n;
1433	get_ids(space, type: t, first: dst_pos, n: s[t - o] - dst_pos,
1434	ids: ids + off);
1435	off += s[t - o] - dst_pos;
1436	} else if (t == src_type) {
1437	get_ids(space, type: t, first: 0, n: src_pos, ids: ids + off);
1438	off += src_pos;
1439	get_ids(space, type: t, first: src_pos + n,
1440	n: s[t - o] - src_pos - n, ids: ids + off);
1441	off += s[t - o] - src_pos - n;
1442	} else {
1443	get_ids(space, type: t, first: 0, n: s[t - o], ids: ids + off);
1444	off += s[t - o];
1445	}
1446	}
1447	free(ptr: space->ids);
1448	space->ids = ids;
1449	space->n_id = space->nparam + space->n_in + space->n_out;
1450	}
1451
1452	switch (dst_type) {
1453	case isl_dim_param: space->nparam += n; break;
1454	case isl_dim_in: space->n_in += n; break;
1455	case isl_dim_out: space->n_out += n; break;
1456	default: ;
1457	}
1458
1459	switch (src_type) {
1460	case isl_dim_param: space->nparam -= n; break;
1461	case isl_dim_in: space->n_in -= n; break;
1462	case isl_dim_out: space->n_out -= n; break;
1463	default: ;
1464	}
1465
1466	if (dst_type != isl_dim_param && src_type != isl_dim_param)
1467	return space;
1468
1469	for (i = 0; i < 2; ++i) {
1470	isl_space *nested;
1471
1472	if (!space->nested[i])
1473	continue;
1474	nested = isl_space_take_nested(space, pos: i);
1475	nested = isl_space_replace_params(dst: nested, src: space);
1476	space = isl_space_restore_nested(space, pos: i, nested);
1477	if (!space)
1478	return NULL;
1479	}
1480
1481	return space;
1482	error:
1483	isl_space_free(space);
1484	return NULL;
1485	}
1486
1487	/* Check that "space1" and "space2" have the same parameters,
1488	* reporting an error if they do not.
1489	*/
1490	isl_stat isl_space_check_equal_params(__isl_keep isl_space *space1,
1491	__isl_keep isl_space *space2)
1492	{
1493	isl_bool equal;
1494
1495	equal = isl_space_has_equal_params(space1, space2);
1496	if (equal < 0)
1497	return isl_stat_error;
1498	if (!equal)
1499	isl_die(isl_space_get_ctx(space1), isl_error_invalid,
1500	"parameters need to match", return isl_stat_error);
1501	return isl_stat_ok;
1502	}
1503
1504	__isl_give isl_space *isl_space_join(__isl_take isl_space *left,
1505	__isl_take isl_space *right)
1506	{
1507	isl_space *space;
1508
1509	if (isl_space_check_equal_params(space1: left, space2: right) < 0)
1510	goto error;
1511
1512	isl_assert(left->ctx,
1513	isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_in),
1514	goto error);
1515
1516	space = isl_space_alloc(ctx: left->ctx,
1517	nparam: left->nparam, n_in: left->n_in, n_out: right->n_out);
1518	if (!space)
1519	goto error;
1520
1521	space = copy_ids(dst: space, dst_type: isl_dim_param, offset: 0, src: left, src_type: isl_dim_param);
1522	space = copy_ids(dst: space, dst_type: isl_dim_in, offset: 0, src: left, src_type: isl_dim_in);
1523	space = copy_ids(dst: space, dst_type: isl_dim_out, offset: 0, src: right, src_type: isl_dim_out);
1524
1525	if (space && left->tuple_id[0] &&
1526	!(space->tuple_id[0] = isl_id_copy(id: left->tuple_id[0])))
1527	goto error;
1528	if (space && right->tuple_id[1] &&
1529	!(space->tuple_id[1] = isl_id_copy(id: right->tuple_id[1])))
1530	goto error;
1531	if (space && left->nested[0] &&
1532	!(space->nested[0] = isl_space_copy(space: left->nested[0])))
1533	goto error;
1534	if (space && right->nested[1] &&
1535	!(space->nested[1] = isl_space_copy(space: right->nested[1])))
1536	goto error;
1537
1538	isl_space_free(space: left);
1539	isl_space_free(space: right);
1540
1541	return space;
1542	error:
1543	isl_space_free(space: left);
1544	isl_space_free(space: right);
1545	return NULL;
1546	}
1547
1548	/* Given two map spaces { A -> C } and { B -> D }, construct the space
1549	* { [A -> B] -> [C -> D] }.
1550	* Given two set spaces { A } and { B }, construct the space { [A -> B] }.
1551	*/
1552	__isl_give isl_space *isl_space_product(__isl_take isl_space *left,
1553	__isl_take isl_space *right)
1554	{
1555	isl_space *dom1, *dom2, *nest1, *nest2;
1556	int is_set;
1557
1558	if (!left || !right)
1559	goto error;
1560
1561	is_set = isl_space_is_set(space: left);
1562	if (is_set != isl_space_is_set(space: right))
1563	isl_die(isl_space_get_ctx(left), isl_error_invalid,
1564	"expecting either two set spaces or two map spaces",
1565	goto error);
1566	if (is_set)
1567	return isl_space_range_product(left, right);
1568
1569	if (isl_space_check_equal_params(space1: left, space2: right) < 0)
1570	goto error;
1571
1572	dom1 = isl_space_domain(space: isl_space_copy(space: left));
1573	dom2 = isl_space_domain(space: isl_space_copy(space: right));
1574	nest1 = isl_space_wrap(space: isl_space_join(left: isl_space_reverse(space: dom1), right: dom2));
1575
1576	dom1 = isl_space_range(space: left);
1577	dom2 = isl_space_range(space: right);
1578	nest2 = isl_space_wrap(space: isl_space_join(left: isl_space_reverse(space: dom1), right: dom2));
1579
1580	return isl_space_join(left: isl_space_reverse(space: nest1), right: nest2);
1581	error:
1582	isl_space_free(space: left);
1583	isl_space_free(space: right);
1584	return NULL;
1585	}
1586
1587	/* Given two spaces { A -> C } and { B -> C }, construct the space
1588	* { [A -> B] -> C }
1589	*/
1590	__isl_give isl_space *isl_space_domain_product(__isl_take isl_space *left,
1591	__isl_take isl_space *right)
1592	{
1593	isl_space *ran, *dom1, *dom2, *nest;
1594
1595	if (isl_space_check_equal_params(space1: left, space2: right) < 0)
1596	goto error;
1597
1598	if (!isl_space_tuple_is_equal(space1: left, type1: isl_dim_out, space2: right, type2: isl_dim_out))
1599	isl_die(left->ctx, isl_error_invalid,
1600	"ranges need to match", goto error);
1601
1602	ran = isl_space_range(space: isl_space_copy(space: left));
1603
1604	dom1 = isl_space_domain(space: left);
1605	dom2 = isl_space_domain(space: right);
1606	nest = isl_space_wrap(space: isl_space_join(left: isl_space_reverse(space: dom1), right: dom2));
1607
1608	return isl_space_join(left: isl_space_reverse(space: nest), right: ran);
1609	error:
1610	isl_space_free(space: left);
1611	isl_space_free(space: right);
1612	return NULL;
1613	}
1614
1615	__isl_give isl_space *isl_space_range_product(__isl_take isl_space *left,
1616	__isl_take isl_space *right)
1617	{
1618	isl_space *dom, *ran1, *ran2, *nest;
1619
1620	if (isl_space_check_equal_params(space1: left, space2: right) < 0)
1621	goto error;
1622
1623	if (!isl_space_tuple_is_equal(space1: left, type1: isl_dim_in, space2: right, type2: isl_dim_in))
1624	isl_die(left->ctx, isl_error_invalid,
1625	"domains need to match", goto error);
1626
1627	dom = isl_space_domain(space: isl_space_copy(space: left));
1628
1629	ran1 = isl_space_range(space: left);
1630	ran2 = isl_space_range(space: right);
1631	nest = isl_space_wrap(space: isl_space_join(left: isl_space_reverse(space: ran1), right: ran2));
1632
1633	return isl_space_join(left: isl_space_reverse(space: dom), right: nest);
1634	error:
1635	isl_space_free(space: left);
1636	isl_space_free(space: right);
1637	return NULL;
1638	}
1639
1640	/* Given a space of the form [A -> B] -> C, return the space A -> C.
1641	*/
1642	__isl_give isl_space *isl_space_domain_factor_domain(
1643	__isl_take isl_space *space)
1644	{
1645	isl_space *nested;
1646	isl_space *domain;
1647
1648	if (isl_space_check_domain_is_wrapping(space) < 0)
1649	return isl_space_free(space);
1650
1651	nested = space->nested[0];
1652	domain = isl_space_copy(space);
1653	domain = isl_space_drop_dims(space: domain, type: isl_dim_in,
1654	first: nested->n_in, num: nested->n_out);
1655	if (!domain)
1656	return isl_space_free(space);
1657	if (nested->tuple_id[0]) {
1658	domain->tuple_id[0] = isl_id_copy(id: nested->tuple_id[0]);
1659	if (!domain->tuple_id[0])
1660	goto error;
1661	}
1662	if (nested->nested[0]) {
1663	domain->nested[0] = isl_space_copy(space: nested->nested[0]);
1664	if (!domain->nested[0])
1665	goto error;
1666	}
1667
1668	isl_space_free(space);
1669	return domain;
1670	error:
1671	isl_space_free(space);
1672	isl_space_free(space: domain);
1673	return NULL;
1674	}
1675
1676	/* Given a space of the form [A -> B] -> C, return the space B -> C.
1677	*/
1678	__isl_give isl_space *isl_space_domain_factor_range(
1679	__isl_take isl_space *space)
1680	{
1681	isl_space *nested;
1682	isl_space *range;
1683
1684	if (isl_space_check_domain_is_wrapping(space) < 0)
1685	return isl_space_free(space);
1686
1687	nested = space->nested[0];
1688	range = isl_space_copy(space);
1689	range = isl_space_drop_dims(space: range, type: isl_dim_in, first: 0, num: nested->n_in);
1690	if (!range)
1691	return isl_space_free(space);
1692	if (nested->tuple_id[1]) {
1693	range->tuple_id[0] = isl_id_copy(id: nested->tuple_id[1]);
1694	if (!range->tuple_id[0])
1695	goto error;
1696	}
1697	if (nested->nested[1]) {
1698	range->nested[0] = isl_space_copy(space: nested->nested[1]);
1699	if (!range->nested[0])
1700	goto error;
1701	}
1702
1703	isl_space_free(space);
1704	return range;
1705	error:
1706	isl_space_free(space);
1707	isl_space_free(space: range);
1708	return NULL;
1709	}
1710
1711	/* Internal function that selects the domain of the map that is
1712	* embedded in either a set space or the range of a map space.
1713	* In particular, given a space of the form [A -> B], return the space A.
1714	* Given a space of the form A -> [B -> C], return the space A -> B.
1715	*/
1716	static __isl_give isl_space *range_factor_domain(__isl_take isl_space *space)
1717	{
1718	isl_space *nested;
1719	isl_space *domain;
1720
1721	if (!space)
1722	return NULL;
1723
1724	nested = space->nested[1];
1725	domain = isl_space_copy(space);
1726	domain = isl_space_drop_dims(space: domain, type: isl_dim_out,
1727	first: nested->n_in, num: nested->n_out);
1728	if (!domain)
1729	return isl_space_free(space);
1730	if (nested->tuple_id[0]) {
1731	domain->tuple_id[1] = isl_id_copy(id: nested->tuple_id[0]);
1732	if (!domain->tuple_id[1])
1733	goto error;
1734	}
1735	if (nested->nested[0]) {
1736	domain->nested[1] = isl_space_copy(space: nested->nested[0]);
1737	if (!domain->nested[1])
1738	goto error;
1739	}
1740
1741	isl_space_free(space);
1742	return domain;
1743	error:
1744	isl_space_free(space);
1745	isl_space_free(space: domain);
1746	return NULL;
1747	}
1748
1749	/* Given a space of the form A -> [B -> C], return the space A -> B.
1750	*/
1751	__isl_give isl_space *isl_space_range_factor_domain(
1752	__isl_take isl_space *space)
1753	{
1754	if (isl_space_check_range_is_wrapping(space) < 0)
1755	return isl_space_free(space);
1756
1757	return range_factor_domain(space);
1758	}
1759
1760	/* Given a space of the form [A -> B], return the space A.
1761	*/
1762	static __isl_give isl_space *set_factor_domain(__isl_take isl_space *space)
1763	{
1764	if (!space)
1765	return NULL;
1766	if (!isl_space_is_wrapping(space))
1767	isl_die(isl_space_get_ctx(space), isl_error_invalid,
1768	"not a product", return isl_space_free(space));
1769
1770	return range_factor_domain(space);
1771	}
1772
1773	/* Given a space of the form [A -> B] -> [C -> D], return the space A -> C.
1774	* Given a space of the form [A -> B], return the space A.
1775	*/
1776	__isl_give isl_space *isl_space_factor_domain(__isl_take isl_space *space)
1777	{
1778	if (!space)
1779	return NULL;
1780	if (isl_space_is_set(space))
1781	return set_factor_domain(space);
1782	space = isl_space_domain_factor_domain(space);
1783	space = isl_space_range_factor_domain(space);
1784	return space;
1785	}
1786
1787	/* Internal function that selects the range of the map that is
1788	* embedded in either a set space or the range of a map space.
1789	* In particular, given a space of the form [A -> B], return the space B.
1790	* Given a space of the form A -> [B -> C], return the space A -> C.
1791	*/
1792	static __isl_give isl_space *range_factor_range(__isl_take isl_space *space)
1793	{
1794	isl_space *nested;
1795	isl_space *range;
1796
1797	if (!space)
1798	return NULL;
1799
1800	nested = space->nested[1];
1801	range = isl_space_copy(space);
1802	range = isl_space_drop_dims(space: range, type: isl_dim_out, first: 0, num: nested->n_in);
1803	if (!range)
1804	return isl_space_free(space);
1805	if (nested->tuple_id[1]) {
1806	range->tuple_id[1] = isl_id_copy(id: nested->tuple_id[1]);
1807	if (!range->tuple_id[1])
1808	goto error;
1809	}
1810	if (nested->nested[1]) {
1811	range->nested[1] = isl_space_copy(space: nested->nested[1]);
1812	if (!range->nested[1])
1813	goto error;
1814	}
1815
1816	isl_space_free(space);
1817	return range;
1818	error:
1819	isl_space_free(space);
1820	isl_space_free(space: range);
1821	return NULL;
1822	}
1823
1824	/* Given a space of the form A -> [B -> C], return the space A -> C.
1825	*/
1826	__isl_give isl_space *isl_space_range_factor_range(
1827	__isl_take isl_space *space)
1828	{
1829	if (isl_space_check_range_is_wrapping(space) < 0)
1830	return isl_space_free(space);
1831
1832	return range_factor_range(space);
1833	}
1834
1835	/* Given a space of the form [A -> B], return the space B.
1836	*/
1837	static __isl_give isl_space *set_factor_range(__isl_take isl_space *space)
1838	{
1839	if (!space)
1840	return NULL;
1841	if (!isl_space_is_wrapping(space))
1842	isl_die(isl_space_get_ctx(space), isl_error_invalid,
1843	"not a product", return isl_space_free(space));
1844
1845	return range_factor_range(space);
1846	}
1847
1848	/* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
1849	* Given a space of the form [A -> B], return the space B.
1850	*/
1851	__isl_give isl_space *isl_space_factor_range(__isl_take isl_space *space)
1852	{
1853	if (!space)
1854	return NULL;
1855	if (isl_space_is_set(space))
1856	return set_factor_range(space);
1857	space = isl_space_domain_factor_range(space);
1858	space = isl_space_range_factor_range(space);
1859	return space;
1860	}
1861
1862	/* Given a space of the form [A -> B] -> C, return the space A.
1863	*/
1864	__isl_give isl_space *isl_space_domain_wrapped_domain(
1865	__isl_take isl_space *space)
1866	{
1867	return isl_space_factor_domain(space: isl_space_domain(space));
1868	}
1869
1870	/* Given a space of the form [A -> B] -> C, return the space B.
1871	*/
1872	__isl_give isl_space *isl_space_domain_wrapped_range(
1873	__isl_take isl_space *space)
1874	{
1875	return isl_space_factor_range(space: isl_space_domain(space));
1876	}
1877
1878	/* Given a space of the form A -> [B -> C], return the space B.
1879	*/
1880	__isl_give isl_space *isl_space_range_wrapped_domain(
1881	__isl_take isl_space *space)
1882	{
1883	return isl_space_factor_domain(space: isl_space_range(space));
1884	}
1885
1886	/* Given a space of the form A -> [B -> C], return the space C.
1887	*/
1888	__isl_give isl_space *isl_space_range_wrapped_range(
1889	__isl_take isl_space *space)
1890	{
1891	return isl_space_factor_range(space: isl_space_range(space));
1892	}
1893
1894	__isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *space)
1895	{
1896	isl_ctx *ctx;
1897	isl_id **ids = NULL;
1898	int n_id;
1899
1900	if (!space)
1901	return NULL;
1902	ctx = isl_space_get_ctx(space);
1903	if (!isl_space_is_set(space))
1904	isl_die(ctx, isl_error_invalid, "not a set space", goto error);
1905	space = isl_space_cow(space);
1906	if (!space)
1907	return NULL;
1908	n_id = space->nparam + space->n_out + space->n_out;
1909	if (n_id > 0 && space->ids) {
1910	ids = isl_calloc_array(space->ctx, isl_id *, n_id);
1911	if (!ids)
1912	goto error;
1913	get_ids(space, type: isl_dim_param, first: 0, n: space->nparam, ids);
1914	get_ids(space, type: isl_dim_out, first: 0, n: space->n_out,
1915	ids: ids + space->nparam);
1916	}
1917	space->n_in = space->n_out;
1918	if (ids) {
1919	free(ptr: space->ids);
1920	space->ids = ids;
1921	space->n_id = n_id;
1922	space = copy_ids(dst: space, dst_type: isl_dim_out, offset: 0, src: space, src_type: isl_dim_in);
1923	}
1924	isl_id_free(id: space->tuple_id[0]);
1925	space->tuple_id[0] = isl_id_copy(id: space->tuple_id[1]);
1926	isl_space_free(space: space->nested[0]);
1927	space->nested[0] = isl_space_copy(space: space->nested[1]);
1928	return space;
1929	error:
1930	isl_space_free(space);
1931	return NULL;
1932	}
1933
1934	__isl_give isl_space *isl_space_map_from_domain_and_range(
1935	__isl_take isl_space *domain, __isl_take isl_space *range)
1936	{
1937	if (!domain || !range)
1938	goto error;
1939	if (!isl_space_is_set(space: domain))
1940	isl_die(isl_space_get_ctx(domain), isl_error_invalid,
1941	"domain is not a set space", goto error);
1942	if (!isl_space_is_set(space: range))
1943	isl_die(isl_space_get_ctx(range), isl_error_invalid,
1944	"range is not a set space", goto error);
1945	return isl_space_join(left: isl_space_reverse(space: domain), right: range);
1946	error:
1947	isl_space_free(space: domain);
1948	isl_space_free(space: range);
1949	return NULL;
1950	}
1951
1952	static __isl_give isl_space *set_ids(__isl_take isl_space *space,
1953	enum isl_dim_type type,
1954	unsigned first, unsigned n, __isl_take isl_id **ids)
1955	{
1956	int i;
1957
1958	for (i = 0; i < n ; ++i)
1959	space = set_id(space, type, pos: first + i, id: ids[i]);
1960
1961	return space;
1962	}
1963
1964	__isl_give isl_space *isl_space_reverse(__isl_take isl_space *space)
1965	{
1966	unsigned t;
1967	isl_bool equal;
1968	isl_space *nested;
1969	isl_id **ids = NULL;
1970	isl_id *id;
1971
1972	equal = match(space1: space, type1: isl_dim_in, space2: space, type2: isl_dim_out);
1973	if (equal < 0)
1974	return isl_space_free(space);
1975	if (equal)
1976	return space;
1977
1978	space = isl_space_cow(space);
1979	if (!space)
1980	return NULL;
1981
1982	id = space->tuple_id[0];
1983	space->tuple_id[0] = space->tuple_id[1];
1984	space->tuple_id[1] = id;
1985
1986	nested = space->nested[0];
1987	space->nested[0] = space->nested[1];
1988	space->nested[1] = nested;
1989
1990	if (space->ids) {
1991	int n_id = space->n_in + space->n_out;
1992	ids = isl_alloc_array(space->ctx, isl_id *, n_id);
1993	if (n_id && !ids)
1994	goto error;
1995	get_ids(space, type: isl_dim_in, first: 0, n: space->n_in, ids);
1996	get_ids(space, type: isl_dim_out, first: 0, n: space->n_out, ids: ids + space->n_in);
1997	}
1998
1999	t = space->n_in;
2000	space->n_in = space->n_out;
2001	space->n_out = t;
2002
2003	if (space->ids) {
2004	space = set_ids(space, type: isl_dim_out, first: 0, n: space->n_out, ids);
2005	space = set_ids(space, type: isl_dim_in, first: 0, n: space->n_in,
2006	ids: ids + space->n_out);
2007	free(ptr: ids);
2008	}
2009
2010	return space;
2011	error:
2012	free(ptr: ids);
2013	isl_space_free(space);
2014	return NULL;
2015	}
2016
2017	/* Given a space A -> (B -> C), return the corresponding space
2018	* A -> (C -> B).
2019	*
2020	* If the range tuple is named, then the name is only preserved
2021	* if B and C are equal tuples, in which case the output
2022	* of this function is identical to the input.
2023	*/
2024	__isl_give isl_space *isl_space_range_reverse(__isl_take isl_space *space)
2025	{
2026	isl_space *nested;
2027	isl_bool equal;
2028
2029	if (isl_space_check_range_is_wrapping(space) < 0)
2030	return isl_space_free(space);
2031
2032	nested = isl_space_peek_nested(space, pos: 1);
2033	equal = isl_space_tuple_is_equal(space1: nested, type1: isl_dim_in,
2034	space2: nested, type2: isl_dim_out);
2035	if (equal < 0)
2036	return isl_space_free(space);
2037
2038	nested = isl_space_take_nested(space, pos: 1);
2039	nested = isl_space_reverse(space: nested);
2040	space = isl_space_restore_nested(space, pos: 1, nested);
2041	if (!equal)
2042	space = isl_space_reset_tuple_id(space, type: isl_dim_out);
2043
2044	return space;
2045	}
2046
2047	__isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *space,
2048	enum isl_dim_type type, unsigned first, unsigned num)
2049	{
2050	int i;
2051
2052	if (!space)
2053	return NULL;
2054
2055	if (num == 0)
2056	return isl_space_reset(space, type);
2057
2058	if (!valid_dim_type(type))
2059	isl_die(space->ctx, isl_error_invalid,
2060	"cannot drop dimensions of specified type", goto error);
2061
2062	if (isl_space_check_range(obj: space, type, first, n: num) < 0)
2063	return isl_space_free(space);
2064	space = isl_space_cow(space);
2065	if (!space)
2066	goto error;
2067	if (space->ids) {
2068	space = extend_ids(space);
2069	if (!space)
2070	goto error;
2071	for (i = 0; i < num; ++i)
2072	isl_id_free(id: get_id(space, type, pos: first + i));
2073	for (i = first+num; i < n(space, type); ++i)
2074	set_id(space, type, pos: i - num, id: get_id(space, type, pos: i));
2075	switch (type) {
2076	case isl_dim_param:
2077	get_ids(space, type: isl_dim_in, first: 0, n: space->n_in,
2078	ids: space->ids + offset(space, type: isl_dim_in) - num);
2079	case isl_dim_in:
2080	get_ids(space, type: isl_dim_out, first: 0, n: space->n_out,
2081	ids: space->ids + offset(space, type: isl_dim_out) - num);
2082	default:
2083	;
2084	}
2085	space->n_id -= num;
2086	}
2087	switch (type) {
2088	case isl_dim_param: space->nparam -= num; break;
2089	case isl_dim_in: space->n_in -= num; break;
2090	case isl_dim_out: space->n_out -= num; break;
2091	default: ;
2092	}
2093	space = isl_space_reset(space, type);
2094	if (type == isl_dim_param) {
2095	if (space && space->nested[0] &&
2096	!(space->nested[0] = isl_space_drop_dims(space: space->nested[0],
2097	type: isl_dim_param, first, num)))
2098	goto error;
2099	if (space && space->nested[1] &&
2100	!(space->nested[1] = isl_space_drop_dims(space: space->nested[1],
2101	type: isl_dim_param, first, num)))
2102	goto error;
2103	}
2104	return space;
2105	error:
2106	isl_space_free(space);
2107	return NULL;
2108	}
2109
2110	__isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *space,
2111	unsigned first, unsigned n)
2112	{
2113	if (!space)
2114	return NULL;
2115	return isl_space_drop_dims(space, type: isl_dim_in, first, num: n);
2116	}
2117
2118	__isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *space,
2119	unsigned first, unsigned n)
2120	{
2121	if (!space)
2122	return NULL;
2123	return isl_space_drop_dims(space, type: isl_dim_out, first, num: n);
2124	}
2125
2126	/* Remove all parameters from "space".
2127	*/
2128	__isl_give isl_space *isl_space_drop_all_params(__isl_take isl_space *space)
2129	{
2130	isl_size nparam;
2131
2132	nparam = isl_space_dim(space, type: isl_dim_param);
2133	if (nparam < 0)
2134	return isl_space_free(space);
2135	return isl_space_drop_dims(space, type: isl_dim_param, first: 0, num: nparam);
2136	}
2137
2138	__isl_give isl_space *isl_space_domain(__isl_take isl_space *space)
2139	{
2140	if (!space)
2141	return NULL;
2142	space = isl_space_drop_dims(space, type: isl_dim_out, first: 0, num: space->n_out);
2143	space = isl_space_reverse(space);
2144	space = mark_as_set(space);
2145	return space;
2146	}
2147
2148	__isl_give isl_space *isl_space_from_domain(__isl_take isl_space *space)
2149	{
2150	if (!space)
2151	return NULL;
2152	if (!isl_space_is_set(space))
2153	isl_die(isl_space_get_ctx(space), isl_error_invalid,
2154	"not a set space", goto error);
2155	space = isl_space_reverse(space);
2156	space = isl_space_reset(space, type: isl_dim_out);
2157	return space;
2158	error:
2159	isl_space_free(space);
2160	return NULL;
2161	}
2162
2163	__isl_give isl_space *isl_space_range(__isl_take isl_space *space)
2164	{
2165	if (!space)
2166	return NULL;
2167	space = isl_space_drop_dims(space, type: isl_dim_in, first: 0, num: space->n_in);
2168	space = mark_as_set(space);
2169	return space;
2170	}
2171
2172	__isl_give isl_space *isl_space_from_range(__isl_take isl_space *space)
2173	{
2174	if (!space)
2175	return NULL;
2176	if (!isl_space_is_set(space))
2177	isl_die(isl_space_get_ctx(space), isl_error_invalid,
2178	"not a set space", goto error);
2179	return isl_space_reset(space, type: isl_dim_in);
2180	error:
2181	isl_space_free(space);
2182	return NULL;
2183	}
2184
2185	/* Given a map space A -> B, return the map space [A -> B] -> A.
2186	*/
2187	__isl_give isl_space *isl_space_domain_map(__isl_take isl_space *space)
2188	{
2189	isl_space *domain;
2190
2191	domain = isl_space_from_range(space: isl_space_domain(space: isl_space_copy(space)));
2192	space = isl_space_from_domain(space: isl_space_wrap(space));
2193	space = isl_space_join(left: space, right: domain);
2194
2195	return space;
2196	}
2197
2198	/* Given a map space A -> B, return the map space [A -> B] -> B.
2199	*/
2200	__isl_give isl_space *isl_space_range_map(__isl_take isl_space *space)
2201	{
2202	isl_space *range;
2203
2204	range = isl_space_from_range(space: isl_space_range(space: isl_space_copy(space)));
2205	space = isl_space_from_domain(space: isl_space_wrap(space));
2206	space = isl_space_join(left: space, right: range);
2207
2208	return space;
2209	}
2210
2211	__isl_give isl_space *isl_space_params(__isl_take isl_space *space)
2212	{
2213	isl_size n_in, n_out;
2214
2215	if (isl_space_is_params(space))
2216	return space;
2217	n_in = isl_space_dim(space, type: isl_dim_in);
2218	n_out = isl_space_dim(space, type: isl_dim_out);
2219	if (n_in < 0 || n_out < 0)
2220	return isl_space_free(space);
2221	space = isl_space_drop_dims(space, type: isl_dim_in, first: 0, num: n_in);
2222	space = isl_space_drop_dims(space, type: isl_dim_out, first: 0, num: n_out);
2223	space = mark_as_params(space);
2224	return space;
2225	}
2226
2227	__isl_give isl_space *isl_space_set_from_params(__isl_take isl_space *space)
2228	{
2229	if (!space)
2230	return NULL;
2231	if (!isl_space_is_params(space))
2232	isl_die(isl_space_get_ctx(space), isl_error_invalid,
2233	"not a parameter space", goto error);
2234	return isl_space_reset(space, type: isl_dim_set);
2235	error:
2236	isl_space_free(space);
2237	return NULL;
2238	}
2239
2240	/* Add an unnamed tuple of dimension "dim" to "space".
2241	* This requires "space" to be a parameter or set space.
2242	*
2243	* In particular, if "space" is a parameter space, then return
2244	* a set space with the given dimension.
2245	* If "space" is a set space, then return a map space
2246	* with "space" as domain and a range of the given dimension.
2247	*/
2248	__isl_give isl_space *isl_space_add_unnamed_tuple_ui(
2249	__isl_take isl_space *space, unsigned dim)
2250	{
2251	isl_bool is_params, is_set;
2252
2253	is_params = isl_space_is_params(space);
2254	is_set = isl_space_is_set(space);
2255	if (is_params < 0 || is_set < 0)
2256	return isl_space_free(space);
2257	if (!is_params && !is_set)
2258	isl_die(isl_space_get_ctx(space), isl_error_invalid,
2259	"cannot add tuple to map space",
2260	return isl_space_free(space));
2261	if (is_params)
2262	space = isl_space_set_from_params(space);
2263	else
2264	space = isl_space_from_domain(space);
2265	space = isl_space_add_dims(space, type: isl_dim_out, n: dim);
2266	return space;
2267	}
2268
2269	/* Add a tuple of dimension "dim" and with tuple identifier "tuple_id"
2270	* to "space".
2271	* This requires "space" to be a parameter or set space.
2272	*/
2273	__isl_give isl_space *isl_space_add_named_tuple_id_ui(
2274	__isl_take isl_space *space, __isl_take isl_id *tuple_id, unsigned dim)
2275	{
2276	space = isl_space_add_unnamed_tuple_ui(space, dim);
2277	space = isl_space_set_tuple_id(space, type: isl_dim_out, id: tuple_id);
2278	return space;
2279	}
2280
2281	/* Check that the identifiers in "tuple" do not appear as parameters
2282	* in "space".
2283	*/
2284	static isl_stat check_fresh_params(__isl_keep isl_space *space,
2285	__isl_keep isl_multi_id *tuple)
2286	{
2287	int i;
2288	isl_size n;
2289
2290	n = isl_multi_id_size(multi: tuple);
2291	if (n < 0)
2292	return isl_stat_error;
2293	for (i = 0; i < n; ++i) {
2294	isl_id *id;
2295	int pos;
2296
2297	id = isl_multi_id_get_at(multi: tuple, pos: i);
2298	if (!id)
2299	return isl_stat_error;
2300	pos = isl_space_find_dim_by_id(space, type: isl_dim_param, id);
2301	isl_id_free(id);
2302	if (pos >= 0)
2303	isl_die(isl_space_get_ctx(space), isl_error_invalid,
2304	"parameters not unique", return isl_stat_error);
2305	}
2306
2307	return isl_stat_ok;
2308	}
2309
2310	/* Add the identifiers in "tuple" as parameters of "space"
2311	* that are known to be fresh.
2312	*/
2313	static __isl_give isl_space *add_bind_params(__isl_take isl_space *space,
2314	__isl_keep isl_multi_id *tuple)
2315	{
2316	int i;
2317	isl_size first, n;
2318
2319	first = isl_space_dim(space, type: isl_dim_param);
2320	n = isl_multi_id_size(multi: tuple);
2321	if (first < 0 || n < 0)
2322	return isl_space_free(space);
2323	space = isl_space_add_dims(space, type: isl_dim_param, n);
2324	for (i = 0; i < n; ++i) {
2325	isl_id *id;
2326
2327	id = isl_multi_id_get_at(multi: tuple, pos: i);
2328	space = isl_space_set_dim_id(space,
2329	type: isl_dim_param, pos: first + i, id);
2330	}
2331
2332	return space;
2333	}
2334
2335	/* Internal function that removes the set tuple of "space",
2336	* which is assumed to correspond to the range space of "tuple", and
2337	* adds the identifiers in "tuple" as fresh parameters.
2338	* In other words, the set dimensions of "space" are reinterpreted
2339	* as parameters, but stay in the same global positions.
2340	*/
2341	__isl_give isl_space *isl_space_bind_set(__isl_take isl_space *space,
2342	__isl_keep isl_multi_id *tuple)
2343	{
2344	isl_space *tuple_space;
2345
2346	if (isl_space_check_is_set(space) < 0)
2347	return isl_space_free(space);
2348	tuple_space = isl_multi_id_peek_space(multi: tuple);
2349	if (isl_space_check_equal_tuples(space1: tuple_space, space2: space) < 0)
2350	return isl_space_free(space);
2351	if (check_fresh_params(space, tuple) < 0)
2352	return isl_space_free(space);
2353	space = isl_space_params(space);
2354	space = add_bind_params(space, tuple);
2355	return space;
2356	}
2357
2358	/* Internal function that removes the domain tuple of the map space "space",
2359	* which is assumed to correspond to the range space of "tuple", and
2360	* adds the identifiers in "tuple" as fresh parameters.
2361	* In other words, the domain dimensions of "space" are reinterpreted
2362	* as parameters, but stay in the same global positions.
2363	*/
2364	__isl_give isl_space *isl_space_bind_map_domain(__isl_take isl_space *space,
2365	__isl_keep isl_multi_id *tuple)
2366	{
2367	isl_space *tuple_space;
2368
2369	if (isl_space_check_is_map(space) < 0)
2370	return isl_space_free(space);
2371	tuple_space = isl_multi_id_peek_space(multi: tuple);
2372	if (isl_space_check_domain_tuples(space1: tuple_space, space2: space) < 0)
2373	return isl_space_free(space);
2374	if (check_fresh_params(space, tuple) < 0)
2375	return isl_space_free(space);
2376	space = isl_space_range(space);
2377	space = add_bind_params(space, tuple);
2378	return space;
2379	}
2380
2381	/* Internal function that, given a space of the form [A -> B] -> C and
2382	* a tuple of identifiers in A, returns a space B -> C with
2383	* the identifiers in "tuple" added as fresh parameters.
2384	* In other words, the domain dimensions of the wrapped relation
2385	* in the domain of "space" are reinterpreted
2386	* as parameters, but stay in the same global positions.
2387	*/
2388	__isl_give isl_space *isl_space_bind_domain_wrapped_domain(
2389	__isl_take isl_space *space, __isl_keep isl_multi_id *tuple)
2390	{
2391	isl_space *tuple_space;
2392
2393	if (isl_space_check_is_map(space) < 0)
2394	return isl_space_free(space);
2395	tuple_space = isl_multi_id_peek_space(multi: tuple);
2396	if (isl_space_check_domain_wrapped_domain_tuples(space1: tuple_space,
2397	space2: space) < 0)
2398	return isl_space_free(space);
2399	if (check_fresh_params(space, tuple) < 0)
2400	return isl_space_free(space);
2401	space = isl_space_domain_factor_range(space);
2402	space = add_bind_params(space, tuple);
2403	return space;
2404	}
2405
2406	/* Insert a domain tuple in "space" corresponding to the set space "domain".
2407	* In particular, if "space" is a parameter space, then the result
2408	* is the set space "domain" combined with the parameters of "space".
2409	* If "space" is a set space, then the result
2410	* is a map space with "domain" as domain and the original space as range.
2411	*/
2412	static __isl_give isl_space *isl_space_insert_domain(
2413	__isl_take isl_space *space, __isl_take isl_space *domain)
2414	{
2415	isl_bool is_params;
2416
2417	domain = isl_space_replace_params(dst: domain, src: space);
2418
2419	is_params = isl_space_is_params(space);
2420	if (is_params < 0) {
2421	isl_space_free(space: domain);
2422	space = isl_space_free(space);
2423	} else if (is_params) {
2424	isl_space_free(space);
2425	space = domain;
2426	} else {
2427	space = isl_space_map_from_domain_and_range(domain, range: space);
2428	}
2429	return space;
2430	}
2431
2432	/* Internal function that introduces a domain in "space"
2433	* corresponding to the range space of "tuple".
2434	* In particular, if "space" is a parameter space, then the result
2435	* is a set space. If "space" is a set space, then the result
2436	* is a map space with the original space as range.
2437	* Parameters that correspond to the identifiers in "tuple" are removed.
2438	*
2439	* The parameters are removed in reverse order (under the assumption
2440	* that they appear in the same order in "multi") because
2441	* it is slightly more efficient to remove parameters at the end.
2442	*
2443	* For pretty-printing purposes, the identifiers of the set dimensions
2444	* of the introduced domain are set to the identifiers in "tuple".
2445	*/
2446	__isl_give isl_space *isl_space_unbind_params_insert_domain(
2447	__isl_take isl_space *space, __isl_keep isl_multi_id *tuple)
2448	{
2449	int i;
2450	isl_size n;
2451	isl_space *tuple_space;
2452
2453	n = isl_multi_id_size(multi: tuple);
2454	if (!space || n < 0)
2455	return isl_space_free(space);
2456	for (i = n - 1; i >= 0; --i) {
2457	isl_id *id;
2458	int pos;
2459
2460	id = isl_multi_id_get_id(multi: tuple, pos: i);
2461	if (!id)
2462	return isl_space_free(space);
2463	pos = isl_space_find_dim_by_id(space, type: isl_dim_param, id);
2464	isl_id_free(id);
2465	if (pos < 0)
2466	continue;
2467	space = isl_space_drop_dims(space, type: isl_dim_param, first: pos, num: 1);
2468	}
2469	tuple_space = isl_multi_id_get_space(multi: tuple);
2470	for (i = 0; i < n; ++i) {
2471	isl_id *id;
2472
2473	id = isl_multi_id_get_id(multi: tuple, pos: i);
2474	tuple_space = isl_space_set_dim_id(space: tuple_space,
2475	type: isl_dim_set, pos: i, id);
2476	}
2477	return isl_space_insert_domain(space, domain: tuple_space);
2478	}
2479
2480	__isl_give isl_space *isl_space_underlying(__isl_take isl_space *space,
2481	unsigned n_div)
2482	{
2483	int i;
2484	isl_bool is_set;
2485
2486	is_set = isl_space_is_set(space);
2487	if (is_set < 0)
2488	return isl_space_free(space);
2489	if (n_div == 0 && is_set &&
2490	space->nparam == 0 && space->n_in == 0 && space->n_id == 0)
2491	return isl_space_reset(space, type: isl_dim_out);
2492	space = isl_space_cow(space);
2493	if (!space)
2494	return NULL;
2495	space->n_out += space->nparam + space->n_in + n_div;
2496	space->nparam = 0;
2497	space->n_in = 0;
2498
2499	for (i = 0; i < space->n_id; ++i)
2500	isl_id_free(id: get_id(space, type: isl_dim_out, pos: i));
2501	space->n_id = 0;
2502	space = isl_space_reset(space, type: isl_dim_in);
2503	space = isl_space_reset(space, type: isl_dim_out);
2504	space = mark_as_set(space);
2505
2506	return space;
2507	}
2508
2509	/* Are the two spaces the same, including positions and names of parameters?
2510	*/
2511	isl_bool isl_space_is_equal(__isl_keep isl_space *space1,
2512	__isl_keep isl_space *space2)
2513	{
2514	isl_bool equal;
2515
2516	if (!space1 || !space2)
2517	return isl_bool_error;
2518	if (space1 == space2)
2519	return isl_bool_true;
2520	equal = isl_space_has_equal_params(space1, space2);
2521	if (equal < 0 || !equal)
2522	return equal;
2523	return isl_space_has_equal_tuples(space1, space2);
2524	}
2525
2526	/* Do the tuples of "space1" correspond to those of the domain of "space2"?
2527	* That is, is "space1" equal to the domain of "space2", ignoring parameters.
2528	*
2529	* "space2" is allowed to be a set space, in which case "space1"
2530	* should be a parameter space.
2531	*/
2532	isl_bool isl_space_has_domain_tuples(__isl_keep isl_space *space1,
2533	__isl_keep isl_space *space2)
2534	{
2535	isl_bool is_set;
2536
2537	is_set = isl_space_is_set(space: space1);
2538	if (is_set < 0 || !is_set)
2539	return is_set;
2540	return isl_space_tuple_is_equal(space1, type1: isl_dim_set,
2541	space2, type2: isl_dim_in);
2542	}
2543
2544	/* Do the tuples of "space1" correspond to those of the range of "space2"?
2545	* That is, is "space1" equal to the range of "space2", ignoring parameters.
2546	*
2547	* "space2" is allowed to be the space of a set,
2548	* in which case it should be equal to "space1", ignoring parameters.
2549	*/
2550	isl_bool isl_space_has_range_tuples(__isl_keep isl_space *space1,
2551	__isl_keep isl_space *space2)
2552	{
2553	isl_bool is_set;
2554
2555	is_set = isl_space_is_set(space: space1);
2556	if (is_set < 0 || !is_set)
2557	return is_set;
2558	return isl_space_tuple_is_equal(space1, type1: isl_dim_set,
2559	space2, type2: isl_dim_out);
2560	}
2561
2562	/* Check that the tuples of "space1" correspond to those
2563	* of the domain of "space2".
2564	* That is, check that "space1" is equal to the domain of "space2",
2565	* ignoring parameters.
2566	*/
2567	isl_stat isl_space_check_domain_tuples(__isl_keep isl_space *space1,
2568	__isl_keep isl_space *space2)
2569	{
2570	isl_bool is_equal;
2571
2572	is_equal = isl_space_has_domain_tuples(space1, space2);
2573	return check_match(space: space1, match: is_equal);
2574	}
2575
2576	/* Check that the tuples of "space1" correspond to those
2577	* of the domain of the wrapped relation in the domain of "space2".
2578	* That is, check that "space1" is equal to this domain,
2579	* ignoring parameters.
2580	*/
2581	isl_stat isl_space_check_domain_wrapped_domain_tuples(
2582	__isl_keep isl_space *space1, __isl_keep isl_space *space2)
2583	{
2584	isl_space *domain;
2585	isl_stat r;
2586
2587	domain = isl_space_unwrap(space: isl_space_domain(space: isl_space_copy(space: space2)));
2588	r = isl_space_check_domain_tuples(space1, space2: domain);
2589	isl_space_free(space: domain);
2590
2591	return r;
2592	}
2593
2594	/* Is space1 equal to the domain of space2?
2595	*
2596	* In the internal version we also allow space2 to be the space of a set,
2597	* provided space1 is a parameter space.
2598	*/
2599	isl_bool isl_space_is_domain_internal(__isl_keep isl_space *space1,
2600	__isl_keep isl_space *space2)
2601	{
2602	isl_bool equal_params;
2603
2604	if (!space1 || !space2)
2605	return isl_bool_error;
2606	equal_params = isl_space_has_equal_params(space1, space2);
2607	if (equal_params < 0 || !equal_params)
2608	return equal_params;
2609	return isl_space_has_domain_tuples(space1, space2);
2610	}
2611
2612	/* Is space1 equal to the domain of space2?
2613	*/
2614	isl_bool isl_space_is_domain(__isl_keep isl_space *space1,
2615	__isl_keep isl_space *space2)
2616	{
2617	if (!space2)
2618	return isl_bool_error;
2619	if (!isl_space_is_map(space: space2))
2620	return isl_bool_false;
2621	return isl_space_is_domain_internal(space1, space2);
2622	}
2623
2624	/* Is space1 equal to the range of space2?
2625	*
2626	* In the internal version, space2 is allowed to be the space of a set,
2627	* in which case it should be equal to space1.
2628	*/
2629	isl_bool isl_space_is_range_internal(__isl_keep isl_space *space1,
2630	__isl_keep isl_space *space2)
2631	{
2632	isl_bool equal_params;
2633
2634	if (!space1 || !space2)
2635	return isl_bool_error;
2636	equal_params = isl_space_has_equal_params(space1, space2);
2637	if (equal_params < 0 || !equal_params)
2638	return equal_params;
2639	return isl_space_has_range_tuples(space1, space2);
2640	}
2641
2642	/* Is space1 equal to the range of space2?
2643	*/
2644	isl_bool isl_space_is_range(__isl_keep isl_space *space1,
2645	__isl_keep isl_space *space2)
2646	{
2647	if (!space2)
2648	return isl_bool_error;
2649	if (!isl_space_is_map(space: space2))
2650	return isl_bool_false;
2651	return isl_space_is_range_internal(space1, space2);
2652	}
2653
2654	/* Update "hash" by hashing in the parameters of "space".
2655	*/
2656	static uint32_t isl_hash_params(uint32_t hash, __isl_keep isl_space *space)
2657	{
2658	int i;
2659	isl_id *id;
2660
2661	if (!space)
2662	return hash;
2663
2664	isl_hash_byte(hash, space->nparam % 256);
2665
2666	for (i = 0; i < space->nparam; ++i) {
2667	id = get_id(space, type: isl_dim_param, pos: i);
2668	hash = isl_hash_id(hash, id);
2669	}
2670
2671	return hash;
2672	}
2673
2674	/* Update "hash" by hashing in the tuples of "space".
2675	* Changes in this function should be reflected in isl_hash_tuples_domain.
2676	*/
2677	static uint32_t isl_hash_tuples(uint32_t hash, __isl_keep isl_space *space)
2678	{
2679	isl_id *id;
2680
2681	if (!space)
2682	return hash;
2683
2684	isl_hash_byte(hash, space->n_in % 256);
2685	isl_hash_byte(hash, space->n_out % 256);
2686
2687	id = tuple_id(space, type: isl_dim_in);
2688	hash = isl_hash_id(hash, id);
2689	id = tuple_id(space, type: isl_dim_out);
2690	hash = isl_hash_id(hash, id);
2691
2692	hash = isl_hash_tuples(hash, space: space->nested[0]);
2693	hash = isl_hash_tuples(hash, space: space->nested[1]);
2694
2695	return hash;
2696	}
2697
2698	/* Update "hash" by hashing in the domain tuple of "space".
2699	* The result of this function is equal to the result of applying
2700	* isl_hash_tuples to the domain of "space".
2701	*/
2702	static uint32_t isl_hash_tuples_domain(uint32_t hash,
2703	__isl_keep isl_space *space)
2704	{
2705	isl_id *id;
2706
2707	if (!space)
2708	return hash;
2709
2710	isl_hash_byte(hash, 0);
2711	isl_hash_byte(hash, space->n_in % 256);
2712
2713	hash = isl_hash_id(hash, id: &isl_id_none);
2714	id = tuple_id(space, type: isl_dim_in);
2715	hash = isl_hash_id(hash, id);
2716
2717	hash = isl_hash_tuples(hash, space: space->nested[0]);
2718
2719	return hash;
2720	}
2721
2722	/* Return a hash value that digests the tuples of "space",
2723	* i.e., that ignores the parameters.
2724	* Changes in this function should be reflected
2725	* in isl_space_get_tuple_domain_hash.
2726	*/
2727	uint32_t isl_space_get_tuple_hash(__isl_keep isl_space *space)
2728	{
2729	uint32_t hash;
2730
2731	if (!space)
2732	return 0;
2733
2734	hash = isl_hash_init();
2735	hash = isl_hash_tuples(hash, space);
2736
2737	return hash;
2738	}
2739
2740	/* Return the hash value of "space".
2741	*/
2742	uint32_t isl_space_get_full_hash(__isl_keep isl_space *space)
2743	{
2744	uint32_t hash;
2745
2746	if (!space)
2747	return 0;
2748
2749	hash = isl_hash_init();
2750	hash = isl_hash_params(hash, space);
2751	hash = isl_hash_tuples(hash, space);
2752
2753	return hash;
2754	}
2755
2756	/* Return the hash value of the domain tuple of "space".
2757	* That is, isl_space_get_tuple_domain_hash(space) is equal to
2758	* isl_space_get_tuple_hash(isl_space_domain(space)).
2759	*/
2760	uint32_t isl_space_get_tuple_domain_hash(__isl_keep isl_space *space)
2761	{
2762	uint32_t hash;
2763
2764	if (!space)
2765	return 0;
2766
2767	hash = isl_hash_init();
2768	hash = isl_hash_tuples_domain(hash, space);
2769
2770	return hash;
2771	}
2772
2773	/* Is "space" the space of a set wrapping a map space?
2774	*/
2775	isl_bool isl_space_is_wrapping(__isl_keep isl_space *space)
2776	{
2777	if (!space)
2778	return isl_bool_error;
2779
2780	if (!isl_space_is_set(space))
2781	return isl_bool_false;
2782
2783	return isl_bool_ok(b: space->nested[1] != NULL);
2784	}
2785
2786	/* Is "space" the space of a map where the domain is a wrapped map space?
2787	*/
2788	isl_bool isl_space_domain_is_wrapping(__isl_keep isl_space *space)
2789	{
2790	if (!space)
2791	return isl_bool_error;
2792
2793	if (isl_space_is_set(space))
2794	return isl_bool_false;
2795
2796	return isl_bool_ok(b: space->nested[0] != NULL);
2797	}
2798
2799	/* Is "space" the space of a map where the range is a wrapped map space?
2800	*/
2801	isl_bool isl_space_range_is_wrapping(__isl_keep isl_space *space)
2802	{
2803	if (!space)
2804	return isl_bool_error;
2805
2806	if (isl_space_is_set(space))
2807	return isl_bool_false;
2808
2809	return isl_bool_ok(b: space->nested[1] != NULL);
2810	}
2811
2812	/* Is "space" a product of two spaces?
2813	* That is, is it a wrapping set space or a map space
2814	* with wrapping domain and range?
2815	*/
2816	isl_bool isl_space_is_product(__isl_keep isl_space *space)
2817	{
2818	isl_bool is_set;
2819	isl_bool is_product;
2820
2821	is_set = isl_space_is_set(space);
2822	if (is_set < 0)
2823	return isl_bool_error;
2824	if (is_set)
2825	return isl_space_is_wrapping(space);
2826	is_product = isl_space_domain_is_wrapping(space);
2827	if (is_product < 0 || !is_product)
2828	return is_product;
2829	return isl_space_range_is_wrapping(space);
2830	}
2831
2832	__isl_give isl_space *isl_space_wrap(__isl_take isl_space *space)
2833	{
2834	isl_space *wrap;
2835
2836	if (!space)
2837	return NULL;
2838
2839	wrap = isl_space_set_alloc(ctx: space->ctx,
2840	nparam: space->nparam, dim: space->n_in + space->n_out);
2841
2842	wrap = copy_ids(dst: wrap, dst_type: isl_dim_param, offset: 0, src: space, src_type: isl_dim_param);
2843	wrap = copy_ids(dst: wrap, dst_type: isl_dim_set, offset: 0, src: space, src_type: isl_dim_in);
2844	wrap = copy_ids(dst: wrap, dst_type: isl_dim_set, offset: space->n_in, src: space, src_type: isl_dim_out);
2845
2846	if (!wrap)
2847	goto error;
2848
2849	wrap->nested[1] = space;
2850
2851	return wrap;
2852	error:
2853	isl_space_free(space);
2854	return NULL;
2855	}
2856
2857	__isl_give isl_space *isl_space_unwrap(__isl_take isl_space *space)
2858	{
2859	isl_space *unwrap;
2860
2861	if (!space)
2862	return NULL;
2863
2864	if (!isl_space_is_wrapping(space))
2865	isl_die(space->ctx, isl_error_invalid, "not a wrapping space",
2866	goto error);
2867
2868	unwrap = isl_space_copy(space: space->nested[1]);
2869	isl_space_free(space);
2870
2871	return unwrap;
2872	error:
2873	isl_space_free(space);
2874	return NULL;
2875	}
2876
2877	isl_bool isl_space_is_named_or_nested(__isl_keep isl_space *space,
2878	enum isl_dim_type type)
2879	{
2880	if (type != isl_dim_in && type != isl_dim_out)
2881	return isl_bool_false;
2882	if (!space)
2883	return isl_bool_error;
2884	if (space->tuple_id[type - isl_dim_in])
2885	return isl_bool_true;
2886	if (space->nested[type - isl_dim_in])
2887	return isl_bool_true;
2888	return isl_bool_false;
2889	}
2890
2891	isl_bool isl_space_may_be_set(__isl_keep isl_space *space)
2892	{
2893	isl_bool nested;
2894	isl_size n_in;
2895
2896	if (!space)
2897	return isl_bool_error;
2898	if (isl_space_is_set(space))
2899	return isl_bool_true;
2900	n_in = isl_space_dim(space, type: isl_dim_in);
2901	if (n_in < 0)
2902	return isl_bool_error;
2903	if (n_in != 0)
2904	return isl_bool_false;
2905	nested = isl_space_is_named_or_nested(space, type: isl_dim_in);
2906	if (nested < 0 || nested)
2907	return isl_bool_not(b: nested);
2908	return isl_bool_true;
2909	}
2910
2911	__isl_give isl_space *isl_space_reset(__isl_take isl_space *space,
2912	enum isl_dim_type type)
2913	{
2914	if (!isl_space_is_named_or_nested(space, type))
2915	return space;
2916
2917	space = isl_space_cow(space);
2918	if (!space)
2919	return NULL;
2920
2921	isl_id_free(id: space->tuple_id[type - isl_dim_in]);
2922	space->tuple_id[type - isl_dim_in] = NULL;
2923	isl_space_free(space: space->nested[type - isl_dim_in]);
2924	space->nested[type - isl_dim_in] = NULL;
2925
2926	return space;
2927	}
2928
2929	__isl_give isl_space *isl_space_flatten(__isl_take isl_space *space)
2930	{
2931	if (!space)
2932	return NULL;
2933	if (!space->nested[0] && !space->nested[1])
2934	return space;
2935
2936	if (space->nested[0])
2937	space = isl_space_reset(space, type: isl_dim_in);
2938	if (space && space->nested[1])
2939	space = isl_space_reset(space, type: isl_dim_out);
2940
2941	return space;
2942	}
2943
2944	__isl_give isl_space *isl_space_flatten_domain(__isl_take isl_space *space)
2945	{
2946	if (!space)
2947	return NULL;
2948	if (!space->nested[0])
2949	return space;
2950
2951	return isl_space_reset(space, type: isl_dim_in);
2952	}
2953
2954	__isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *space)
2955	{
2956	if (!space)
2957	return NULL;
2958	if (!space->nested[1])
2959	return space;
2960
2961	return isl_space_reset(space, type: isl_dim_out);
2962	}
2963
2964	/* Replace the parameters of dst by those of src.
2965	*/
2966	__isl_give isl_space *isl_space_replace_params(__isl_take isl_space *dst,
2967	__isl_keep isl_space *src)
2968	{
2969	isl_size dst_dim, src_dim;
2970	isl_bool equal_params;
2971	enum isl_dim_type type = isl_dim_param;
2972
2973	equal_params = isl_space_has_equal_params(space1: dst, space2: src);
2974	if (equal_params < 0)
2975	return isl_space_free(space: dst);
2976	if (equal_params)
2977	return dst;
2978
2979	dst = isl_space_cow(space: dst);
2980
2981	dst_dim = isl_space_dim(space: dst, type);
2982	src_dim = isl_space_dim(space: src, type);
2983	if (dst_dim < 0 || src_dim < 0)
2984	goto error;
2985
2986	dst = isl_space_drop_dims(space: dst, type, first: 0, num: dst_dim);
2987	dst = isl_space_add_dims(space: dst, type, n: src_dim);
2988	dst = copy_ids(dst, dst_type: type, offset: 0, src, src_type: type);
2989
2990	if (dst) {
2991	int i;
2992	for (i = 0; i <= 1; ++i) {
2993	isl_space *nested;
2994
2995	if (!dst->nested[i])
2996	continue;
2997	nested = isl_space_take_nested(space: dst, pos: i);
2998	nested = isl_space_replace_params(dst: nested, src);
2999	dst = isl_space_restore_nested(space: dst, pos: i, nested);
3000	if (!dst)
3001	return NULL;
3002	}
3003	}
3004
3005	return dst;
3006	error:
3007	isl_space_free(space: dst);
3008	return NULL;
3009	}
3010
3011	/* Given two tuples ("dst_type" in "dst" and "src_type" in "src")
3012	* of the same size, check if any of the dimensions in the "dst" tuple
3013	* have no identifier, while the corresponding dimensions in "src"
3014	* does have an identifier,
3015	* If so, copy the identifier over to "dst".
3016	*/
3017	__isl_give isl_space *isl_space_copy_ids_if_unset(__isl_take isl_space *dst,
3018	enum isl_dim_type dst_type, __isl_keep isl_space *src,
3019	enum isl_dim_type src_type)
3020	{
3021	int i;
3022	isl_size n;
3023
3024	n = isl_space_dim(space: dst, type: dst_type);
3025	if (n < 0)
3026	return isl_space_free(space: dst);
3027	for (i = 0; i < n; ++i) {
3028	isl_bool set;
3029	isl_id *id;
3030
3031	set = isl_space_has_dim_id(space: dst, type: dst_type, pos: i);
3032	if (set < 0)
3033	return isl_space_free(space: dst);
3034	if (set)
3035	continue;
3036
3037	set = isl_space_has_dim_id(space: src, type: src_type, pos: i);
3038	if (set < 0)
3039	return isl_space_free(space: dst);
3040	if (!set)
3041	continue;
3042
3043	id = isl_space_get_dim_id(space: src, type: src_type, pos: i);
3044	dst = isl_space_set_dim_id(space: dst, type: dst_type, pos: i, id);
3045	}
3046
3047	return dst;
3048	}
3049
3050	/* Given a space "space" of a set, create a space
3051	* for the lift of the set. In particular, the result
3052	* is of the form lifted[space -> local[..]], with n_local variables in the
3053	* range of the wrapped map.
3054	*/
3055	__isl_give isl_space *isl_space_lift(__isl_take isl_space *space,
3056	unsigned n_local)
3057	{
3058	isl_space *local_space;
3059
3060	if (!space)
3061	return NULL;
3062
3063	local_space = isl_space_dup(space);
3064	local_space = isl_space_drop_dims(space: local_space, type: isl_dim_set, first: 0,
3065	num: space->n_out);
3066	local_space = isl_space_add_dims(space: local_space, type: isl_dim_set, n: n_local);
3067	local_space = isl_space_set_tuple_name(space: local_space,
3068	type: isl_dim_set, s: "local");
3069	space = isl_space_join(left: isl_space_from_domain(space),
3070	right: isl_space_from_range(space: local_space));
3071	space = isl_space_wrap(space);
3072	space = isl_space_set_tuple_name(space, type: isl_dim_set, s: "lifted");
3073
3074	return space;
3075	}
3076
3077	isl_bool isl_space_can_zip(__isl_keep isl_space *space)
3078	{
3079	isl_bool is_set;
3080
3081	is_set = isl_space_is_set(space);
3082	if (is_set < 0)
3083	return isl_bool_error;
3084	if (is_set)
3085	return isl_bool_false;
3086	return isl_space_is_product(space);
3087	}
3088
3089	__isl_give isl_space *isl_space_zip(__isl_take isl_space *space)
3090	{
3091	isl_space *dom, *ran;
3092	isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran;
3093
3094	if (!isl_space_can_zip(space))
3095	isl_die(space->ctx, isl_error_invalid, "space cannot be zipped",
3096	goto error);
3097
3098	if (!space)
3099	return NULL;
3100	dom = isl_space_unwrap(space: isl_space_domain(space: isl_space_copy(space)));
3101	ran = isl_space_unwrap(space: isl_space_range(space));
3102	dom_dom = isl_space_domain(space: isl_space_copy(space: dom));
3103	dom_ran = isl_space_range(space: dom);
3104	ran_dom = isl_space_domain(space: isl_space_copy(space: ran));
3105	ran_ran = isl_space_range(space: ran);
3106	dom = isl_space_join(left: isl_space_from_domain(space: dom_dom),
3107	right: isl_space_from_range(space: ran_dom));
3108	ran = isl_space_join(left: isl_space_from_domain(space: dom_ran),
3109	right: isl_space_from_range(space: ran_ran));
3110	return isl_space_join(left: isl_space_from_domain(space: isl_space_wrap(space: dom)),
3111	right: isl_space_from_range(space: isl_space_wrap(space: ran)));
3112	error:
3113	isl_space_free(space);
3114	return NULL;
3115	}
3116
3117	/* Can we apply isl_space_curry to "space"?
3118	* That is, does is it have a map space with a nested relation in its domain?
3119	*/
3120	isl_bool isl_space_can_curry(__isl_keep isl_space *space)
3121	{
3122	return isl_space_domain_is_wrapping(space);
3123	}
3124
3125	/* Given a space (A -> B) -> C, return the corresponding space
3126	* A -> (B -> C).
3127	*/
3128	__isl_give isl_space *isl_space_curry(__isl_take isl_space *space)
3129	{
3130	isl_space *dom, *ran;
3131	isl_space *dom_dom, *dom_ran;
3132
3133	if (!space)
3134	return NULL;
3135
3136	if (!isl_space_can_curry(space))
3137	isl_die(space->ctx, isl_error_invalid,
3138	"space cannot be curried", goto error);
3139
3140	dom = isl_space_unwrap(space: isl_space_domain(space: isl_space_copy(space)));
3141	ran = isl_space_range(space);
3142	dom_dom = isl_space_domain(space: isl_space_copy(space: dom));
3143	dom_ran = isl_space_range(space: dom);
3144	ran = isl_space_join(left: isl_space_from_domain(space: dom_ran),
3145	right: isl_space_from_range(space: ran));
3146	return isl_space_join(left: isl_space_from_domain(space: dom_dom),
3147	right: isl_space_from_range(space: isl_space_wrap(space: ran)));
3148	error:
3149	isl_space_free(space);
3150	return NULL;
3151	}
3152
3153	/* Can isl_space_range_curry be applied to "space"?
3154	* That is, does it have a nested relation in its range,
3155	* the domain of which is itself a nested relation?
3156	*/
3157	isl_bool isl_space_can_range_curry(__isl_keep isl_space *space)
3158	{
3159	isl_bool can;
3160
3161	if (!space)
3162	return isl_bool_error;
3163	can = isl_space_range_is_wrapping(space);
3164	if (can < 0 || !can)
3165	return can;
3166	return isl_space_can_curry(space: space->nested[1]);
3167	}
3168
3169	/* Given a space A -> ((B -> C) -> D), return the corresponding space
3170	* A -> (B -> (C -> D)).
3171	*/
3172	__isl_give isl_space *isl_space_range_curry(__isl_take isl_space *space)
3173	{
3174	isl_space *nested;
3175
3176	if (!space)
3177	return NULL;
3178
3179	if (!isl_space_can_range_curry(space))
3180	isl_die(isl_space_get_ctx(space), isl_error_invalid,
3181	"space range cannot be curried",
3182	return isl_space_free(space));
3183
3184	nested = isl_space_take_nested(space, pos: 1);
3185	nested = isl_space_curry(space: nested);
3186	space = isl_space_restore_nested(space, pos: 1, nested);
3187
3188	return space;
3189	}
3190
3191	/* Can we apply isl_space_uncurry to "space"?
3192	* That is, does it have a map space with a nested relation in its range?
3193	*/
3194	isl_bool isl_space_can_uncurry(__isl_keep isl_space *space)
3195	{
3196	return isl_space_range_is_wrapping(space);
3197	}
3198
3199	/* Given a space A -> (B -> C), return the corresponding space
3200	* (A -> B) -> C.
3201	*/
3202	__isl_give isl_space *isl_space_uncurry(__isl_take isl_space *space)
3203	{
3204	isl_space *dom, *ran;
3205	isl_space *ran_dom, *ran_ran;
3206
3207	if (!space)
3208	return NULL;
3209
3210	if (!isl_space_can_uncurry(space))
3211	isl_die(space->ctx, isl_error_invalid,
3212	"space cannot be uncurried",
3213	return isl_space_free(space));
3214
3215	dom = isl_space_domain(space: isl_space_copy(space));
3216	ran = isl_space_unwrap(space: isl_space_range(space));
3217	ran_dom = isl_space_domain(space: isl_space_copy(space: ran));
3218	ran_ran = isl_space_range(space: ran);
3219	dom = isl_space_join(left: isl_space_from_domain(space: dom),
3220	right: isl_space_from_range(space: ran_dom));
3221	return isl_space_join(left: isl_space_from_domain(space: isl_space_wrap(space: dom)),
3222	right: isl_space_from_range(space: ran_ran));
3223	}
3224
3225	isl_bool isl_space_has_named_params(__isl_keep isl_space *space)
3226	{
3227	int i;
3228	unsigned off;
3229
3230	if (!space)
3231	return isl_bool_error;
3232	if (space->nparam == 0)
3233	return isl_bool_true;
3234	off = isl_space_offset(space, type: isl_dim_param);
3235	if (off + space->nparam > space->n_id)
3236	return isl_bool_false;
3237	for (i = 0; i < space->nparam; ++i)
3238	if (!space->ids[off + i])
3239	return isl_bool_false;
3240	return isl_bool_true;
3241	}
3242
3243	/* Check that "space" has only named parameters, reporting an error
3244	* if it does not.
3245	*/
3246	isl_stat isl_space_check_named_params(__isl_keep isl_space *space)
3247	{
3248	isl_bool named;
3249
3250	named = isl_space_has_named_params(space);
3251	if (named < 0)
3252	return isl_stat_error;
3253	if (!named)
3254	isl_die(isl_space_get_ctx(space), isl_error_invalid,
3255	"unexpected unnamed parameters", return isl_stat_error);
3256
3257	return isl_stat_ok;
3258	}
3259
3260	/* Align the initial parameters of space1 to match the order in space2.
3261	*/
3262	__isl_give isl_space *isl_space_align_params(__isl_take isl_space *space1,
3263	__isl_take isl_space *space2)
3264	{
3265	isl_reordering *exp;
3266
3267	if (isl_space_check_named_params(space: space1) < 0 ||
3268	isl_space_check_named_params(space: space2) < 0)
3269	goto error;
3270
3271	exp = isl_parameter_alignment_reordering(alignee: space1, aligner: space2);
3272	isl_space_free(space: space1);
3273	isl_space_free(space: space2);
3274	space1 = isl_reordering_get_space(r: exp);
3275	isl_reordering_free(exp);
3276	return space1;
3277	error:
3278	isl_space_free(space: space1);
3279	isl_space_free(space: space2);
3280	return NULL;
3281	}
3282
3283	/* Given the space of set (domain), construct a space for a map
3284	* with as domain the given space and as range the range of "model".
3285	*/
3286	__isl_give isl_space *isl_space_extend_domain_with_range(
3287	__isl_take isl_space *space, __isl_take isl_space *model)
3288	{
3289	isl_size n_out;
3290
3291	if (!model)
3292	goto error;
3293
3294	space = isl_space_from_domain(space);
3295	n_out = isl_space_dim(space: model, type: isl_dim_out);
3296	if (n_out < 0)
3297	goto error;
3298	space = isl_space_add_dims(space, type: isl_dim_out, n: n_out);
3299	if (isl_space_has_tuple_id(space: model, type: isl_dim_out))
3300	space = isl_space_set_tuple_id(space, type: isl_dim_out,
3301	id: isl_space_get_tuple_id(space: model, type: isl_dim_out));
3302	if (!space)
3303	goto error;
3304	if (model->nested[1]) {
3305	isl_space *nested = isl_space_copy(space: model->nested[1]);
3306	isl_size n_nested, n_space;
3307	nested = isl_space_align_params(space1: nested, space2: isl_space_copy(space));
3308	n_nested = isl_space_dim(space: nested, type: isl_dim_param);
3309	n_space = isl_space_dim(space, type: isl_dim_param);
3310	if (n_nested < 0 || n_space < 0)
3311	goto error;
3312	if (n_nested > n_space)
3313	nested = isl_space_drop_dims(space: nested, type: isl_dim_param,
3314	first: n_space, num: n_nested - n_space);
3315	if (!nested)
3316	goto error;
3317	space->nested[1] = nested;
3318	}
3319	isl_space_free(space: model);
3320	return space;
3321	error:
3322	isl_space_free(space: model);
3323	isl_space_free(space);
3324	return NULL;
3325	}
3326
3327	/* Compare the "type" dimensions of two isl_spaces.
3328	*
3329	* The order is fairly arbitrary.
3330	*/
3331	static int isl_space_cmp_type(__isl_keep isl_space *space1,
3332	__isl_keep isl_space *space2, enum isl_dim_type type)
3333	{
3334	int cmp;
3335	isl_size dim1, dim2;
3336	isl_space *nested1, *nested2;
3337
3338	dim1 = isl_space_dim(space: space1, type);
3339	dim2 = isl_space_dim(space: space2, type);
3340	if (dim1 < 0 || dim2 < 0)
3341	return 0;
3342	if (dim1 != dim2)
3343	return dim1 - dim2;
3344
3345	cmp = isl_id_cmp(id1: tuple_id(space: space1, type), id2: tuple_id(space: space2, type));
3346	if (cmp != 0)
3347	return cmp;
3348
3349	nested1 = nested(space: space1, type);
3350	nested2 = nested(space: space2, type);
3351	if (!nested1 != !nested2)
3352	return !nested1 - !nested2;
3353
3354	if (nested1)
3355	return isl_space_cmp(space1: nested1, space2: nested2);
3356
3357	return 0;
3358	}
3359
3360	/* Compare two isl_spaces.
3361	*
3362	* The order is fairly arbitrary.
3363	*/
3364	int isl_space_cmp(__isl_keep isl_space *space1, __isl_keep isl_space *space2)
3365	{
3366	int i;
3367	int cmp;
3368
3369	if (space1 == space2)
3370	return 0;
3371	if (!space1)
3372	return -1;
3373	if (!space2)
3374	return 1;
3375
3376	cmp = isl_space_cmp_type(space1, space2, type: isl_dim_param);
3377	if (cmp != 0)
3378	return cmp;
3379	cmp = isl_space_cmp_type(space1, space2, type: isl_dim_in);
3380	if (cmp != 0)
3381	return cmp;
3382	cmp = isl_space_cmp_type(space1, space2, type: isl_dim_out);
3383	if (cmp != 0)
3384	return cmp;
3385
3386	if (!space1->ids && !space2->ids)
3387	return 0;
3388
3389	for (i = 0; i < n(space: space1, type: isl_dim_param); ++i) {
3390	cmp = isl_id_cmp(id1: get_id(space: space1, type: isl_dim_param, pos: i),
3391	id2: get_id(space: space2, type: isl_dim_param, pos: i));
3392	if (cmp != 0)
3393	return cmp;
3394	}
3395
3396	return 0;
3397	}
3398