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