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