support (type safe) user object on id in bindings
[isl.git] / isl_space.c
blobe2e788affd5e545701b9c99d24327158f1e1caea
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2013-2014 Ecole Normale Superieure
5 * Copyright 2018-2019 Cerebras Systems
7 * Use of this software is governed by the MIT license
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
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>
23 isl_ctx *isl_space_get_ctx(__isl_keep isl_space *space)
25 return space ? space->ctx : NULL;
28 __isl_give isl_space *isl_space_alloc(isl_ctx *ctx,
29 unsigned nparam, unsigned n_in, unsigned n_out)
31 isl_space *space;
33 space = isl_alloc_type(ctx, struct isl_space);
34 if (!space)
35 return NULL;
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;
44 space->tuple_id[0] = NULL;
45 space->tuple_id[1] = NULL;
47 space->nested[0] = NULL;
48 space->nested[1] = NULL;
50 space->n_id = 0;
51 space->ids = NULL;
53 return space;
56 /* Mark the space as being that of a set, by setting the domain tuple
57 * to isl_id_none.
59 static __isl_give isl_space *mark_as_set(__isl_take isl_space *space)
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;
68 /* Is the space that of a set?
70 isl_bool isl_space_is_set(__isl_keep isl_space *space)
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;
81 /* Check that "space" is a set space.
83 isl_stat isl_space_check_is_set(__isl_keep isl_space *space)
85 isl_bool is_set;
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;
96 /* Is the given space that of a map?
98 isl_bool isl_space_is_map(__isl_keep isl_space *space)
100 int r;
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);
109 /* Check that "space" is the space of a map.
111 static isl_stat isl_space_check_is_map(__isl_keep isl_space *space)
113 isl_bool is_space;
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;
124 /* Check that "space" is the space of a map
125 * where the domain is a wrapped map space.
127 isl_stat isl_space_check_domain_is_wrapping(__isl_keep isl_space *space)
129 isl_bool wrapping;
131 wrapping = isl_space_domain_is_wrapping(space);
132 if (wrapping < 0)
133 return isl_stat_error;
134 if (!wrapping)
135 isl_die(isl_space_get_ctx(space), isl_error_invalid,
136 "domain not a product", return isl_stat_error);
137 return isl_stat_ok;
140 /* Check that "space" is the space of a map
141 * where the range is a wrapped map space.
143 isl_stat isl_space_check_range_is_wrapping(__isl_keep isl_space *space)
145 isl_bool wrapping;
147 wrapping = isl_space_range_is_wrapping(space);
148 if (wrapping < 0)
149 return isl_stat_error;
150 if (!wrapping)
151 isl_die(isl_space_get_ctx(space), isl_error_invalid,
152 "range not a product", return isl_stat_error);
153 return isl_stat_ok;
156 __isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,
157 unsigned nparam, unsigned dim)
159 isl_space *space;
160 space = isl_space_alloc(ctx, nparam, 0, dim);
161 space = mark_as_set(space);
162 return space;
165 /* Mark the space as being that of a parameter domain, by setting
166 * both tuples to isl_id_none.
168 static __isl_give isl_space *mark_as_params(isl_space *space)
170 if (!space)
171 return NULL;
172 space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
173 space = isl_space_set_tuple_id(space, isl_dim_out, &isl_id_none);
174 return space;
177 /* Is the space that of a parameter domain?
179 isl_bool isl_space_is_params(__isl_keep isl_space *space)
181 if (!space)
182 return isl_bool_error;
183 if (space->n_in != 0 || space->nested[0] ||
184 space->n_out != 0 || space->nested[1])
185 return isl_bool_false;
186 if (space->tuple_id[0] != &isl_id_none)
187 return isl_bool_false;
188 if (space->tuple_id[1] != &isl_id_none)
189 return isl_bool_false;
190 return isl_bool_true;
193 /* Create a space for a parameter domain.
195 __isl_give isl_space *isl_space_params_alloc(isl_ctx *ctx, unsigned nparam)
197 isl_space *space;
198 space = isl_space_alloc(ctx, nparam, 0, 0);
199 space = mark_as_params(space);
200 return space;
203 /* Create a space for a parameter domain, without any parameters.
205 __isl_give isl_space *isl_space_unit(isl_ctx *ctx)
207 return isl_space_params_alloc(ctx, 0);
210 static isl_size global_pos(__isl_keep isl_space *space,
211 enum isl_dim_type type, unsigned pos)
213 if (isl_space_check_range(space, type, pos, 1) < 0)
214 return isl_size_error;
216 switch (type) {
217 case isl_dim_param:
218 return pos;
219 case isl_dim_in:
220 return pos + space->nparam;
221 case isl_dim_out:
222 return pos + space->nparam + space->n_in;
223 default:
224 isl_assert(isl_space_get_ctx(space), 0, return isl_size_error);
226 return isl_size_error;
229 /* Extend length of ids array to the total number of dimensions.
231 static __isl_give isl_space *extend_ids(__isl_take isl_space *space)
233 isl_id **ids;
234 int i;
235 isl_size dim;
237 dim = isl_space_dim(space, isl_dim_all);
238 if (dim < 0)
239 return isl_space_free(space);
240 if (dim <= space->n_id)
241 return space;
243 if (!space->ids) {
244 space->ids = isl_calloc_array(space->ctx, isl_id *, dim);
245 if (!space->ids)
246 goto error;
247 } else {
248 ids = isl_realloc_array(space->ctx, space->ids, isl_id *, dim);
249 if (!ids)
250 goto error;
251 space->ids = ids;
252 for (i = space->n_id; i < dim; ++i)
253 space->ids[i] = NULL;
256 space->n_id = dim;
258 return space;
259 error:
260 isl_space_free(space);
261 return NULL;
264 static __isl_give isl_space *set_id(__isl_take isl_space *space,
265 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
267 isl_size gpos;
269 space = isl_space_cow(space);
271 gpos = global_pos(space, type, pos);
272 if (gpos < 0)
273 goto error;
275 if (gpos >= space->n_id) {
276 if (!id)
277 return space;
278 space = extend_ids(space);
279 if (!space)
280 goto error;
283 space->ids[gpos] = id;
285 return space;
286 error:
287 isl_id_free(id);
288 isl_space_free(space);
289 return NULL;
292 static __isl_keep isl_id *get_id(__isl_keep isl_space *space,
293 enum isl_dim_type type, unsigned pos)
295 isl_size gpos;
297 gpos = global_pos(space, type, pos);
298 if (gpos < 0)
299 return NULL;
300 if (gpos >= space->n_id)
301 return NULL;
302 return space->ids[gpos];
305 /* Return the nested space at the given position.
307 static __isl_keep isl_space *isl_space_peek_nested(__isl_keep isl_space *space,
308 int pos)
310 if (!space)
311 return NULL;
312 if (!space->nested[pos])
313 isl_die(isl_space_get_ctx(space), isl_error_invalid,
314 "no nested space", return NULL);
315 return space->nested[pos];
318 static unsigned offset(__isl_keep isl_space *space, enum isl_dim_type type)
320 switch (type) {
321 case isl_dim_param: return 0;
322 case isl_dim_in: return space->nparam;
323 case isl_dim_out: return space->nparam + space->n_in;
324 default: return 0;
328 static unsigned n(__isl_keep isl_space *space, enum isl_dim_type type)
330 switch (type) {
331 case isl_dim_param: return space->nparam;
332 case isl_dim_in: return space->n_in;
333 case isl_dim_out: return space->n_out;
334 case isl_dim_all:
335 return space->nparam + space->n_in + space->n_out;
336 default: return 0;
340 isl_size isl_space_dim(__isl_keep isl_space *space, enum isl_dim_type type)
342 if (!space)
343 return isl_size_error;
344 return n(space, type);
347 /* Return the dimensionality of tuple "inner" within the wrapped relation
348 * inside tuple "outer".
350 isl_size isl_space_wrapped_dim(__isl_keep isl_space *space,
351 enum isl_dim_type outer, enum isl_dim_type inner)
353 int pos;
355 if (!space)
356 return isl_size_error;
357 if (outer != isl_dim_in && outer != isl_dim_out)
358 isl_die(isl_space_get_ctx(space), isl_error_invalid,
359 "only input, output and set tuples "
360 "can have nested relations", return isl_size_error);
361 pos = outer - isl_dim_in;
362 return isl_space_dim(isl_space_peek_nested(space, pos), inner);
365 unsigned isl_space_offset(__isl_keep isl_space *space, enum isl_dim_type type)
367 if (!space)
368 return 0;
369 return offset(space, type);
372 static __isl_give isl_space *copy_ids(__isl_take isl_space *dst,
373 enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_space *src,
374 enum isl_dim_type src_type)
376 int i;
377 isl_id *id;
379 if (!dst)
380 return NULL;
382 for (i = 0; i < n(src, src_type); ++i) {
383 id = get_id(src, src_type, i);
384 if (!id)
385 continue;
386 dst = set_id(dst, dst_type, offset + i, isl_id_copy(id));
387 if (!dst)
388 return NULL;
390 return dst;
393 __isl_take isl_space *isl_space_dup(__isl_keep isl_space *space)
395 isl_space *dup;
396 if (!space)
397 return NULL;
398 dup = isl_space_alloc(space->ctx,
399 space->nparam, space->n_in, space->n_out);
400 if (!dup)
401 return NULL;
402 if (space->tuple_id[0] &&
403 !(dup->tuple_id[0] = isl_id_copy(space->tuple_id[0])))
404 goto error;
405 if (space->tuple_id[1] &&
406 !(dup->tuple_id[1] = isl_id_copy(space->tuple_id[1])))
407 goto error;
408 if (space->nested[0] &&
409 !(dup->nested[0] = isl_space_copy(space->nested[0])))
410 goto error;
411 if (space->nested[1] &&
412 !(dup->nested[1] = isl_space_copy(space->nested[1])))
413 goto error;
414 if (!space->ids)
415 return dup;
416 dup = copy_ids(dup, isl_dim_param, 0, space, isl_dim_param);
417 dup = copy_ids(dup, isl_dim_in, 0, space, isl_dim_in);
418 dup = copy_ids(dup, isl_dim_out, 0, space, isl_dim_out);
419 return dup;
420 error:
421 isl_space_free(dup);
422 return NULL;
425 __isl_give isl_space *isl_space_cow(__isl_take isl_space *space)
427 if (!space)
428 return NULL;
430 if (space->ref == 1)
431 return space;
432 space->ref--;
433 return isl_space_dup(space);
436 __isl_give isl_space *isl_space_copy(__isl_keep isl_space *space)
438 if (!space)
439 return NULL;
441 space->ref++;
442 return space;
445 __isl_null isl_space *isl_space_free(__isl_take isl_space *space)
447 int i;
449 if (!space)
450 return NULL;
452 if (--space->ref > 0)
453 return NULL;
455 isl_id_free(space->tuple_id[0]);
456 isl_id_free(space->tuple_id[1]);
458 isl_space_free(space->nested[0]);
459 isl_space_free(space->nested[1]);
461 for (i = 0; i < space->n_id; ++i)
462 isl_id_free(space->ids[i]);
463 free(space->ids);
464 isl_ctx_deref(space->ctx);
466 free(space);
468 return NULL;
471 /* Check if "s" is a valid dimension or tuple name.
472 * We currently only forbid names that look like a number.
474 * s is assumed to be non-NULL.
476 static int name_ok(isl_ctx *ctx, const char *s)
478 char *p;
480 strtol(s, &p, 0);
481 if (p != s)
482 isl_die(ctx, isl_error_invalid, "name looks like a number",
483 return 0);
485 return 1;
488 /* Return a copy of the nested space at the given position.
490 static __isl_keep isl_space *isl_space_get_nested(__isl_keep isl_space *space,
491 int pos)
493 return isl_space_copy(isl_space_peek_nested(space, pos));
496 /* Return the nested space at the given position.
497 * This may be either a copy or the nested space itself
498 * if there is only one reference to "space".
499 * This allows the nested space to be modified inplace
500 * if both "space" and the nested space have only a single reference.
501 * The caller is not allowed to modify "space" between this call and
502 * a subsequent call to isl_space_restore_nested.
503 * The only exception is that isl_space_free can be called instead.
505 static __isl_give isl_space *isl_space_take_nested(__isl_keep isl_space *space,
506 int pos)
508 isl_space *nested;
510 if (!space)
511 return NULL;
512 if (space->ref != 1)
513 return isl_space_get_nested(space, pos);
514 nested = space->nested[pos];
515 space->nested[pos] = NULL;
516 return nested;
519 /* Replace the nested space at the given position by "nested",
520 * where this nested space of "space" may be missing
521 * due to a preceding call to isl_space_take_nested.
522 * However, in this case, "space" only has a single reference and
523 * then the call to isl_space_cow has no effect.
525 static __isl_give isl_space *isl_space_restore_nested(
526 __isl_take isl_space *space, int pos, __isl_take isl_space *nested)
528 if (!space || !nested)
529 goto error;
531 if (space->nested[pos] == nested) {
532 isl_space_free(nested);
533 return space;
536 space = isl_space_cow(space);
537 if (!space)
538 goto error;
539 isl_space_free(space->nested[pos]);
540 space->nested[pos] = nested;
542 return space;
543 error:
544 isl_space_free(space);
545 isl_space_free(nested);
546 return NULL;
549 /* Is it possible for the given dimension type to have a tuple id?
551 static int space_can_have_id(__isl_keep isl_space *space,
552 enum isl_dim_type type)
554 if (!space)
555 return 0;
556 if (isl_space_is_params(space))
557 isl_die(space->ctx, isl_error_invalid,
558 "parameter spaces don't have tuple ids", return 0);
559 if (isl_space_is_set(space) && type != isl_dim_set)
560 isl_die(space->ctx, isl_error_invalid,
561 "set spaces can only have a set id", return 0);
562 if (type != isl_dim_in && type != isl_dim_out)
563 isl_die(space->ctx, isl_error_invalid,
564 "only input, output and set tuples can have ids",
565 return 0);
567 return 1;
570 /* Does the tuple have an id?
572 isl_bool isl_space_has_tuple_id(__isl_keep isl_space *space,
573 enum isl_dim_type type)
575 if (!space_can_have_id(space, type))
576 return isl_bool_error;
577 return isl_bool_ok(space->tuple_id[type - isl_dim_in] != NULL);
580 /* Does the domain tuple of the map space "space" have an identifier?
582 isl_bool isl_space_has_domain_tuple_id(__isl_keep isl_space *space)
584 if (isl_space_check_is_map(space) < 0)
585 return isl_bool_error;
586 return isl_space_has_tuple_id(space, isl_dim_in);
589 /* Does the range tuple of the map space "space" have an identifier?
591 isl_bool isl_space_has_range_tuple_id(__isl_keep isl_space *space)
593 if (isl_space_check_is_map(space) < 0)
594 return isl_bool_error;
595 return isl_space_has_tuple_id(space, isl_dim_out);
598 __isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *space,
599 enum isl_dim_type type)
601 int has_id;
603 if (!space)
604 return NULL;
605 has_id = isl_space_has_tuple_id(space, type);
606 if (has_id < 0)
607 return NULL;
608 if (!has_id)
609 isl_die(space->ctx, isl_error_invalid,
610 "tuple has no id", return NULL);
611 return isl_id_copy(space->tuple_id[type - isl_dim_in]);
614 /* Return the identifier of the domain tuple of the map space "space",
615 * assuming it has one.
617 __isl_give isl_id *isl_space_get_domain_tuple_id(
618 __isl_keep isl_space *space)
620 if (isl_space_check_is_map(space) < 0)
621 return NULL;
622 return isl_space_get_tuple_id(space, isl_dim_in);
625 /* Return the identifier of the range tuple of the map space "space",
626 * assuming it has one.
628 __isl_give isl_id *isl_space_get_range_tuple_id(
629 __isl_keep isl_space *space)
631 if (isl_space_check_is_map(space) < 0)
632 return NULL;
633 return isl_space_get_tuple_id(space, isl_dim_out);
636 __isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *space,
637 enum isl_dim_type type, __isl_take isl_id *id)
639 space = isl_space_cow(space);
640 if (!space || !id)
641 goto error;
642 if (type != isl_dim_in && type != isl_dim_out)
643 isl_die(space->ctx, isl_error_invalid,
644 "only input, output and set tuples can have names",
645 goto error);
647 isl_id_free(space->tuple_id[type - isl_dim_in]);
648 space->tuple_id[type - isl_dim_in] = id;
650 return space;
651 error:
652 isl_id_free(id);
653 isl_space_free(space);
654 return NULL;
657 /* Replace the identifier of the domain tuple of the map space "space"
658 * by "id".
660 __isl_give isl_space *isl_space_set_domain_tuple_id(
661 __isl_take isl_space *space, __isl_take isl_id *id)
663 if (isl_space_check_is_map(space) < 0)
664 space = isl_space_free(space);
665 return isl_space_set_tuple_id(space, isl_dim_in, id);
668 /* Replace the identifier of the range tuple of the map space "space"
669 * by "id".
671 __isl_give isl_space *isl_space_set_range_tuple_id(
672 __isl_take isl_space *space, __isl_take isl_id *id)
674 if (isl_space_check_is_map(space) < 0)
675 space = isl_space_free(space);
676 return isl_space_set_tuple_id(space, isl_dim_out, id);
679 __isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *space,
680 enum isl_dim_type type)
682 space = isl_space_cow(space);
683 if (!space)
684 return NULL;
685 if (type != isl_dim_in && type != isl_dim_out)
686 isl_die(space->ctx, isl_error_invalid,
687 "only input, output and set tuples can have names",
688 goto error);
690 isl_id_free(space->tuple_id[type - isl_dim_in]);
691 space->tuple_id[type - isl_dim_in] = NULL;
693 return space;
694 error:
695 isl_space_free(space);
696 return NULL;
699 /* Set the id of the given dimension of "space" to "id".
700 * If the dimension already has an id, then it is replaced.
701 * If the dimension is a parameter, then we need to change it
702 * in the nested spaces (if any) as well.
704 __isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *space,
705 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
707 space = isl_space_cow(space);
708 if (!space || !id)
709 goto error;
711 if (type == isl_dim_param) {
712 int i;
714 for (i = 0; i < 2; ++i) {
715 if (!space->nested[i])
716 continue;
717 space->nested[i] =
718 isl_space_set_dim_id(space->nested[i],
719 type, pos, isl_id_copy(id));
720 if (!space->nested[i])
721 goto error;
725 isl_id_free(get_id(space, type, pos));
726 return set_id(space, type, pos, id);
727 error:
728 isl_id_free(id);
729 isl_space_free(space);
730 return NULL;
733 /* Reset the id of the given dimension of "space".
734 * If the dimension already has an id, then it is removed.
735 * If the dimension is a parameter, then we need to reset it
736 * in the nested spaces (if any) as well.
738 __isl_give isl_space *isl_space_reset_dim_id(__isl_take isl_space *space,
739 enum isl_dim_type type, unsigned pos)
741 space = isl_space_cow(space);
742 if (!space)
743 goto error;
745 if (type == isl_dim_param) {
746 int i;
748 for (i = 0; i < 2; ++i) {
749 if (!space->nested[i])
750 continue;
751 space->nested[i] =
752 isl_space_reset_dim_id(space->nested[i],
753 type, pos);
754 if (!space->nested[i])
755 goto error;
759 isl_id_free(get_id(space, type, pos));
760 return set_id(space, type, pos, NULL);
761 error:
762 isl_space_free(space);
763 return NULL;
766 isl_bool isl_space_has_dim_id(__isl_keep isl_space *space,
767 enum isl_dim_type type, unsigned pos)
769 if (!space)
770 return isl_bool_error;
771 return isl_bool_ok(get_id(space, type, pos) != NULL);
774 __isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *space,
775 enum isl_dim_type type, unsigned pos)
777 if (!space)
778 return NULL;
779 if (!get_id(space, type, pos))
780 isl_die(space->ctx, isl_error_invalid,
781 "dim has no id", return NULL);
782 return isl_id_copy(get_id(space, type, pos));
785 __isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *space,
786 enum isl_dim_type type, const char *s)
788 isl_id *id;
790 if (!space)
791 return NULL;
793 if (!s)
794 return isl_space_reset_tuple_id(space, type);
796 if (!name_ok(space->ctx, s))
797 goto error;
799 id = isl_id_alloc(space->ctx, s, NULL);
800 return isl_space_set_tuple_id(space, type, id);
801 error:
802 isl_space_free(space);
803 return NULL;
806 /* Does the tuple have a name?
808 isl_bool isl_space_has_tuple_name(__isl_keep isl_space *space,
809 enum isl_dim_type type)
811 isl_id *id;
813 if (!space_can_have_id(space, type))
814 return isl_bool_error;
815 id = space->tuple_id[type - isl_dim_in];
816 return isl_bool_ok(id && id->name);
819 __isl_keep const char *isl_space_get_tuple_name(__isl_keep isl_space *space,
820 enum isl_dim_type type)
822 isl_id *id;
823 if (!space)
824 return NULL;
825 if (type != isl_dim_in && type != isl_dim_out)
826 return NULL;
827 id = space->tuple_id[type - isl_dim_in];
828 return id ? id->name : NULL;
831 __isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *space,
832 enum isl_dim_type type, unsigned pos,
833 const char *s)
835 isl_id *id;
837 if (!space)
838 return NULL;
839 if (!s)
840 return isl_space_reset_dim_id(space, type, pos);
841 if (!name_ok(space->ctx, s))
842 goto error;
843 id = isl_id_alloc(space->ctx, s, NULL);
844 return isl_space_set_dim_id(space, type, pos, id);
845 error:
846 isl_space_free(space);
847 return NULL;
850 /* Does the given dimension have a name?
852 isl_bool isl_space_has_dim_name(__isl_keep isl_space *space,
853 enum isl_dim_type type, unsigned pos)
855 isl_id *id;
857 if (!space)
858 return isl_bool_error;
859 id = get_id(space, type, pos);
860 return isl_bool_ok(id && id->name);
863 __isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *space,
864 enum isl_dim_type type, unsigned pos)
866 isl_id *id = get_id(space, type, pos);
867 return id ? id->name : NULL;
870 int isl_space_find_dim_by_id(__isl_keep isl_space *space,
871 enum isl_dim_type type, __isl_keep isl_id *id)
873 int i;
874 int offset;
875 isl_size n;
877 n = isl_space_dim(space, type);
878 if (n < 0 || !id)
879 return -1;
881 offset = isl_space_offset(space, type);
882 for (i = 0; i < n && offset + i < space->n_id; ++i)
883 if (space->ids[offset + i] == id)
884 return i;
886 return -1;
889 int isl_space_find_dim_by_name(__isl_keep isl_space *space,
890 enum isl_dim_type type, const char *name)
892 int i;
893 int offset;
894 isl_size n;
896 n = isl_space_dim(space, type);
897 if (n < 0 || !name)
898 return -1;
900 offset = isl_space_offset(space, type);
901 for (i = 0; i < n && offset + i < space->n_id; ++i) {
902 isl_id *id = get_id(space, type, i);
903 if (id && id->name && !strcmp(id->name, name))
904 return i;
907 return -1;
910 /* Reset the user pointer on all identifiers of parameters and tuples
911 * of "space".
913 __isl_give isl_space *isl_space_reset_user(__isl_take isl_space *space)
915 int i;
916 isl_ctx *ctx;
917 isl_id *id;
918 const char *name;
920 if (!space)
921 return NULL;
923 ctx = isl_space_get_ctx(space);
925 for (i = 0; i < space->nparam && i < space->n_id; ++i) {
926 if (!isl_id_get_user(space->ids[i]))
927 continue;
928 space = isl_space_cow(space);
929 if (!space)
930 return NULL;
931 name = isl_id_get_name(space->ids[i]);
932 id = isl_id_alloc(ctx, name, NULL);
933 isl_id_free(space->ids[i]);
934 space->ids[i] = id;
935 if (!id)
936 return isl_space_free(space);
939 for (i = 0; i < 2; ++i) {
940 if (!space->tuple_id[i])
941 continue;
942 if (!isl_id_get_user(space->tuple_id[i]))
943 continue;
944 space = isl_space_cow(space);
945 if (!space)
946 return NULL;
947 name = isl_id_get_name(space->tuple_id[i]);
948 id = isl_id_alloc(ctx, name, NULL);
949 isl_id_free(space->tuple_id[i]);
950 space->tuple_id[i] = id;
951 if (!id)
952 return isl_space_free(space);
955 for (i = 0; i < 2; ++i) {
956 isl_space *nested;
958 if (!space->nested[i])
959 continue;
960 nested = isl_space_take_nested(space, i);
961 nested = isl_space_reset_user(nested);
962 space = isl_space_restore_nested(space, i, nested);
963 if (!space)
964 return NULL;
967 return space;
970 static __isl_keep isl_id *tuple_id(__isl_keep isl_space *space,
971 enum isl_dim_type type)
973 if (!space)
974 return NULL;
975 if (type == isl_dim_in)
976 return space->tuple_id[0];
977 if (type == isl_dim_out)
978 return space->tuple_id[1];
979 return NULL;
982 static __isl_keep isl_space *nested(__isl_keep isl_space *space,
983 enum isl_dim_type type)
985 if (!space)
986 return NULL;
987 if (type == isl_dim_in)
988 return space->nested[0];
989 if (type == isl_dim_out)
990 return space->nested[1];
991 return NULL;
994 /* Are the two spaces the same, apart from positions and names of parameters?
996 isl_bool isl_space_has_equal_tuples(__isl_keep isl_space *space1,
997 __isl_keep isl_space *space2)
999 if (!space1 || !space2)
1000 return isl_bool_error;
1001 if (space1 == space2)
1002 return isl_bool_true;
1003 return isl_space_tuple_is_equal(space1, isl_dim_in,
1004 space2, isl_dim_in) &&
1005 isl_space_tuple_is_equal(space1, isl_dim_out,
1006 space2, isl_dim_out);
1009 /* Check that a match involving "space" was successful.
1010 * That is, check that "match" is equal to isl_bool_true.
1012 static isl_stat check_match(__isl_keep isl_space *space, isl_bool match)
1014 if (match < 0)
1015 return isl_stat_error;
1016 if (!match)
1017 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1018 "incompatible spaces", return isl_stat_error);
1020 return isl_stat_ok;
1023 /* Check that the two spaces are the same,
1024 * apart from positions and names of parameters.
1026 isl_stat isl_space_check_equal_tuples(__isl_keep isl_space *space1,
1027 __isl_keep isl_space *space2)
1029 isl_bool is_equal;
1031 is_equal = isl_space_has_equal_tuples(space1, space2);
1032 return check_match(space1, is_equal);
1035 /* Check if the tuple of type "type1" of "space1" is the same as
1036 * the tuple of type "type2" of "space2".
1038 * That is, check if the tuples have the same identifier, the same dimension
1039 * and the same internal structure.
1040 * The identifiers of the dimensions inside the tuples do not affect the result.
1042 * Note that this function only checks the tuples themselves.
1043 * If nested tuples are involved, then we need to be careful not
1044 * to have result affected by possibly differing parameters
1045 * in those nested tuples.
1047 isl_bool isl_space_tuple_is_equal(__isl_keep isl_space *space1,
1048 enum isl_dim_type type1, __isl_keep isl_space *space2,
1049 enum isl_dim_type type2)
1051 isl_id *id1, *id2;
1052 isl_space *nested1, *nested2;
1054 if (!space1 || !space2)
1055 return isl_bool_error;
1057 if (space1 == space2 && type1 == type2)
1058 return isl_bool_true;
1060 if (n(space1, type1) != n(space2, type2))
1061 return isl_bool_false;
1062 id1 = tuple_id(space1, type1);
1063 id2 = tuple_id(space2, type2);
1064 if (!id1 ^ !id2)
1065 return isl_bool_false;
1066 if (id1 && id1 != id2)
1067 return isl_bool_false;
1068 nested1 = nested(space1, type1);
1069 nested2 = nested(space2, type2);
1070 if (!nested1 ^ !nested2)
1071 return isl_bool_false;
1072 if (nested1 && !isl_space_has_equal_tuples(nested1, nested2))
1073 return isl_bool_false;
1074 return isl_bool_true;
1077 /* Is the tuple "inner" within the wrapped relation inside tuple "outer"
1078 * of "space1" equal to tuple "type2" of "space2"?
1080 isl_bool isl_space_wrapped_tuple_is_equal(__isl_keep isl_space *space1,
1081 enum isl_dim_type outer, enum isl_dim_type inner,
1082 __isl_keep isl_space *space2, enum isl_dim_type type2)
1084 int pos;
1085 isl_space *nested;
1087 if (!space1)
1088 return isl_bool_error;
1089 if (outer != isl_dim_in && outer != isl_dim_out)
1090 isl_die(isl_space_get_ctx(space1), isl_error_invalid,
1091 "only input, output and set tuples "
1092 "can have nested relations", return isl_bool_error);
1093 pos = outer - isl_dim_in;
1094 nested = isl_space_peek_nested(space1, pos);
1095 return isl_space_tuple_is_equal(nested, inner, space2, type2);
1098 /* Check that the tuple "inner" within the wrapped relation inside tuple "outer"
1099 * of "space1" is equal to tuple "type2" of "space2".
1101 isl_stat isl_space_check_wrapped_tuple_is_equal(__isl_keep isl_space *space1,
1102 enum isl_dim_type outer, enum isl_dim_type inner,
1103 __isl_keep isl_space *space2, enum isl_dim_type type2)
1105 isl_bool is_equal;
1107 is_equal = isl_space_wrapped_tuple_is_equal(space1, outer, inner,
1108 space2, type2);
1109 return check_match(space1, is_equal);
1112 static isl_bool match(__isl_keep isl_space *space1, enum isl_dim_type type1,
1113 __isl_keep isl_space *space2, enum isl_dim_type type2)
1115 int i;
1116 isl_bool equal;
1118 if (!space1 || !space2)
1119 return isl_bool_error;
1121 if (space1 == space2 && type1 == type2)
1122 return isl_bool_true;
1124 equal = isl_space_tuple_is_equal(space1, type1, space2, type2);
1125 if (equal < 0 || !equal)
1126 return equal;
1128 if (!space1->ids && !space2->ids)
1129 return isl_bool_true;
1131 for (i = 0; i < n(space1, type1); ++i) {
1132 if (get_id(space1, type1, i) != get_id(space2, type2, i))
1133 return isl_bool_false;
1135 return isl_bool_true;
1138 /* Do "space1" and "space2" have the same parameters?
1140 isl_bool isl_space_has_equal_params(__isl_keep isl_space *space1,
1141 __isl_keep isl_space *space2)
1143 return match(space1, isl_dim_param, space2, isl_dim_param);
1146 /* Do "space1" and "space2" have the same identifiers for all
1147 * the tuple variables?
1149 isl_bool isl_space_has_equal_ids(__isl_keep isl_space *space1,
1150 __isl_keep isl_space *space2)
1152 isl_bool equal;
1154 equal = match(space1, isl_dim_in, space2, isl_dim_in);
1155 if (equal < 0 || !equal)
1156 return equal;
1157 return match(space1, isl_dim_out, space2, isl_dim_out);
1160 isl_bool isl_space_match(__isl_keep isl_space *space1, enum isl_dim_type type1,
1161 __isl_keep isl_space *space2, enum isl_dim_type type2)
1163 return match(space1, type1, space2, type2);
1166 static void get_ids(__isl_keep isl_space *space, enum isl_dim_type type,
1167 unsigned first, unsigned n, __isl_keep isl_id **ids)
1169 int i;
1171 for (i = 0; i < n ; ++i)
1172 ids[i] = get_id(space, type, first + i);
1175 static __isl_give isl_space *space_extend(__isl_take isl_space *space,
1176 unsigned nparam, unsigned n_in, unsigned n_out)
1178 isl_id **ids = NULL;
1180 if (!space)
1181 return NULL;
1182 if (space->nparam == nparam &&
1183 space->n_in == n_in && space->n_out == n_out)
1184 return space;
1186 isl_assert(space->ctx, space->nparam <= nparam, goto error);
1187 isl_assert(space->ctx, space->n_in <= n_in, goto error);
1188 isl_assert(space->ctx, space->n_out <= n_out, goto error);
1190 space = isl_space_cow(space);
1191 if (!space)
1192 goto error;
1194 if (space->ids) {
1195 unsigned n;
1196 n = nparam + n_in + n_out;
1197 if (n < nparam || n < n_in || n < n_out)
1198 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1199 "overflow in total number of dimensions",
1200 goto error);
1201 ids = isl_calloc_array(space->ctx, isl_id *, n);
1202 if (!ids)
1203 goto error;
1204 get_ids(space, isl_dim_param, 0, space->nparam, ids);
1205 get_ids(space, isl_dim_in, 0, space->n_in, ids + nparam);
1206 get_ids(space, isl_dim_out, 0, space->n_out,
1207 ids + nparam + n_in);
1208 free(space->ids);
1209 space->ids = ids;
1210 space->n_id = nparam + n_in + n_out;
1212 space->nparam = nparam;
1213 space->n_in = n_in;
1214 space->n_out = n_out;
1216 return space;
1217 error:
1218 free(ids);
1219 isl_space_free(space);
1220 return NULL;
1223 __isl_give isl_space *isl_space_extend(__isl_take isl_space *space,
1224 unsigned nparam, unsigned n_in, unsigned n_out)
1226 return space_extend(space, nparam, n_in, n_out);
1229 __isl_give isl_space *isl_space_add_dims(__isl_take isl_space *space,
1230 enum isl_dim_type type, unsigned n)
1232 space = isl_space_reset(space, type);
1233 if (!space)
1234 return NULL;
1235 switch (type) {
1236 case isl_dim_param:
1237 space = space_extend(space,
1238 space->nparam + n, space->n_in, space->n_out);
1239 if (space && space->nested[0] &&
1240 !(space->nested[0] = isl_space_add_dims(space->nested[0],
1241 isl_dim_param, n)))
1242 goto error;
1243 if (space && space->nested[1] &&
1244 !(space->nested[1] = isl_space_add_dims(space->nested[1],
1245 isl_dim_param, n)))
1246 goto error;
1247 return space;
1248 case isl_dim_in:
1249 return space_extend(space,
1250 space->nparam, space->n_in + n, space->n_out);
1251 case isl_dim_out:
1252 return space_extend(space,
1253 space->nparam, space->n_in, space->n_out + n);
1254 default:
1255 isl_die(space->ctx, isl_error_invalid,
1256 "cannot add dimensions of specified type", goto error);
1258 error:
1259 isl_space_free(space);
1260 return NULL;
1263 /* Add a parameter with identifier "id" to "space", provided
1264 * it does not already appear in "space".
1266 __isl_give isl_space *isl_space_add_param_id(__isl_take isl_space *space,
1267 __isl_take isl_id *id)
1269 isl_size pos;
1271 if (!space || !id)
1272 goto error;
1274 if (isl_space_find_dim_by_id(space, isl_dim_param, id) >= 0) {
1275 isl_id_free(id);
1276 return space;
1279 pos = isl_space_dim(space, isl_dim_param);
1280 if (pos < 0)
1281 goto error;
1282 space = isl_space_add_dims(space, isl_dim_param, 1);
1283 space = isl_space_set_dim_id(space, isl_dim_param, pos, id);
1285 return space;
1286 error:
1287 isl_space_free(space);
1288 isl_id_free(id);
1289 return NULL;
1292 static int valid_dim_type(enum isl_dim_type type)
1294 switch (type) {
1295 case isl_dim_param:
1296 case isl_dim_in:
1297 case isl_dim_out:
1298 return 1;
1299 default:
1300 return 0;
1304 #undef TYPE
1305 #define TYPE isl_space
1306 #include "check_type_range_templ.c"
1308 /* Insert "n" dimensions of type "type" at position "pos".
1309 * If we are inserting parameters, then they are also inserted in
1310 * any nested spaces.
1312 __isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *space,
1313 enum isl_dim_type type, unsigned pos, unsigned n)
1315 isl_ctx *ctx;
1316 isl_id **ids = NULL;
1318 if (!space)
1319 return NULL;
1320 if (n == 0)
1321 return isl_space_reset(space, type);
1323 ctx = isl_space_get_ctx(space);
1324 if (!valid_dim_type(type))
1325 isl_die(ctx, isl_error_invalid,
1326 "cannot insert dimensions of specified type",
1327 goto error);
1329 if (isl_space_check_range(space, type, pos, 0) < 0)
1330 return isl_space_free(space);
1332 space = isl_space_cow(space);
1333 if (!space)
1334 return NULL;
1336 if (space->ids) {
1337 enum isl_dim_type t, o = isl_dim_param;
1338 int off;
1339 int s[3];
1340 ids = isl_calloc_array(ctx, isl_id *,
1341 space->nparam + space->n_in + space->n_out + n);
1342 if (!ids)
1343 goto error;
1344 off = 0;
1345 s[isl_dim_param - o] = space->nparam;
1346 s[isl_dim_in - o] = space->n_in;
1347 s[isl_dim_out - o] = space->n_out;
1348 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
1349 if (t != type) {
1350 get_ids(space, t, 0, s[t - o], ids + off);
1351 off += s[t - o];
1352 } else {
1353 get_ids(space, t, 0, pos, ids + off);
1354 off += pos + n;
1355 get_ids(space, t, pos, s[t - o] - pos,
1356 ids + off);
1357 off += s[t - o] - pos;
1360 free(space->ids);
1361 space->ids = ids;
1362 space->n_id = space->nparam + space->n_in + space->n_out + n;
1364 switch (type) {
1365 case isl_dim_param: space->nparam += n; break;
1366 case isl_dim_in: space->n_in += n; break;
1367 case isl_dim_out: space->n_out += n; break;
1368 default: ;
1370 space = isl_space_reset(space, type);
1372 if (type == isl_dim_param) {
1373 if (space && space->nested[0] &&
1374 !(space->nested[0] = isl_space_insert_dims(space->nested[0],
1375 isl_dim_param, pos, n)))
1376 goto error;
1377 if (space && space->nested[1] &&
1378 !(space->nested[1] = isl_space_insert_dims(space->nested[1],
1379 isl_dim_param, pos, n)))
1380 goto error;
1383 return space;
1384 error:
1385 isl_space_free(space);
1386 return NULL;
1389 __isl_give isl_space *isl_space_move_dims(__isl_take isl_space *space,
1390 enum isl_dim_type dst_type, unsigned dst_pos,
1391 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1393 int i;
1395 space = isl_space_reset(space, src_type);
1396 space = isl_space_reset(space, dst_type);
1397 if (!space)
1398 return NULL;
1399 if (n == 0)
1400 return space;
1402 if (isl_space_check_range(space, src_type, src_pos, n) < 0)
1403 return isl_space_free(space);
1405 if (dst_type == src_type && dst_pos == src_pos)
1406 return space;
1408 isl_assert(space->ctx, dst_type != src_type, goto error);
1410 space = isl_space_cow(space);
1411 if (!space)
1412 return NULL;
1414 if (space->ids) {
1415 isl_id **ids;
1416 enum isl_dim_type t, o = isl_dim_param;
1417 int off;
1418 int s[3];
1419 ids = isl_calloc_array(space->ctx, isl_id *,
1420 space->nparam + space->n_in + space->n_out);
1421 if (!ids)
1422 goto error;
1423 off = 0;
1424 s[isl_dim_param - o] = space->nparam;
1425 s[isl_dim_in - o] = space->n_in;
1426 s[isl_dim_out - o] = space->n_out;
1427 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
1428 if (t == dst_type) {
1429 get_ids(space, t, 0, dst_pos, ids + off);
1430 off += dst_pos;
1431 get_ids(space, src_type, src_pos, n, ids + off);
1432 off += n;
1433 get_ids(space, t, dst_pos, s[t - o] - dst_pos,
1434 ids + off);
1435 off += s[t - o] - dst_pos;
1436 } else if (t == src_type) {
1437 get_ids(space, t, 0, src_pos, ids + off);
1438 off += src_pos;
1439 get_ids(space, t, src_pos + n,
1440 s[t - o] - src_pos - n, ids + off);
1441 off += s[t - o] - src_pos - n;
1442 } else {
1443 get_ids(space, t, 0, s[t - o], ids + off);
1444 off += s[t - o];
1447 free(space->ids);
1448 space->ids = ids;
1449 space->n_id = space->nparam + space->n_in + space->n_out;
1452 switch (dst_type) {
1453 case isl_dim_param: space->nparam += n; break;
1454 case isl_dim_in: space->n_in += n; break;
1455 case isl_dim_out: space->n_out += n; break;
1456 default: ;
1459 switch (src_type) {
1460 case isl_dim_param: space->nparam -= n; break;
1461 case isl_dim_in: space->n_in -= n; break;
1462 case isl_dim_out: space->n_out -= n; break;
1463 default: ;
1466 if (dst_type != isl_dim_param && src_type != isl_dim_param)
1467 return space;
1469 for (i = 0; i < 2; ++i) {
1470 isl_space *nested;
1472 if (!space->nested[i])
1473 continue;
1474 nested = isl_space_take_nested(space, i);
1475 nested = isl_space_replace_params(nested, space);
1476 space = isl_space_restore_nested(space, i, nested);
1477 if (!space)
1478 return NULL;
1481 return space;
1482 error:
1483 isl_space_free(space);
1484 return NULL;
1487 /* Check that "space1" and "space2" have the same parameters,
1488 * reporting an error if they do not.
1490 isl_stat isl_space_check_equal_params(__isl_keep isl_space *space1,
1491 __isl_keep isl_space *space2)
1493 isl_bool equal;
1495 equal = isl_space_has_equal_params(space1, space2);
1496 if (equal < 0)
1497 return isl_stat_error;
1498 if (!equal)
1499 isl_die(isl_space_get_ctx(space1), isl_error_invalid,
1500 "parameters need to match", return isl_stat_error);
1501 return isl_stat_ok;
1504 __isl_give isl_space *isl_space_join(__isl_take isl_space *left,
1505 __isl_take isl_space *right)
1507 isl_space *space;
1509 if (isl_space_check_equal_params(left, right) < 0)
1510 goto error;
1512 isl_assert(left->ctx,
1513 isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_in),
1514 goto error);
1516 space = isl_space_alloc(left->ctx,
1517 left->nparam, left->n_in, right->n_out);
1518 if (!space)
1519 goto error;
1521 space = copy_ids(space, isl_dim_param, 0, left, isl_dim_param);
1522 space = copy_ids(space, isl_dim_in, 0, left, isl_dim_in);
1523 space = copy_ids(space, isl_dim_out, 0, right, isl_dim_out);
1525 if (space && left->tuple_id[0] &&
1526 !(space->tuple_id[0] = isl_id_copy(left->tuple_id[0])))
1527 goto error;
1528 if (space && right->tuple_id[1] &&
1529 !(space->tuple_id[1] = isl_id_copy(right->tuple_id[1])))
1530 goto error;
1531 if (space && left->nested[0] &&
1532 !(space->nested[0] = isl_space_copy(left->nested[0])))
1533 goto error;
1534 if (space && right->nested[1] &&
1535 !(space->nested[1] = isl_space_copy(right->nested[1])))
1536 goto error;
1538 isl_space_free(left);
1539 isl_space_free(right);
1541 return space;
1542 error:
1543 isl_space_free(left);
1544 isl_space_free(right);
1545 return NULL;
1548 /* Given two map spaces { A -> C } and { B -> D }, construct the space
1549 * { [A -> B] -> [C -> D] }.
1550 * Given two set spaces { A } and { B }, construct the space { [A -> B] }.
1552 __isl_give isl_space *isl_space_product(__isl_take isl_space *left,
1553 __isl_take isl_space *right)
1555 isl_space *dom1, *dom2, *nest1, *nest2;
1556 int is_set;
1558 if (!left || !right)
1559 goto error;
1561 is_set = isl_space_is_set(left);
1562 if (is_set != isl_space_is_set(right))
1563 isl_die(isl_space_get_ctx(left), isl_error_invalid,
1564 "expecting either two set spaces or two map spaces",
1565 goto error);
1566 if (is_set)
1567 return isl_space_range_product(left, right);
1569 if (isl_space_check_equal_params(left, right) < 0)
1570 goto error;
1572 dom1 = isl_space_domain(isl_space_copy(left));
1573 dom2 = isl_space_domain(isl_space_copy(right));
1574 nest1 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1576 dom1 = isl_space_range(left);
1577 dom2 = isl_space_range(right);
1578 nest2 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1580 return isl_space_join(isl_space_reverse(nest1), nest2);
1581 error:
1582 isl_space_free(left);
1583 isl_space_free(right);
1584 return NULL;
1587 /* Given two spaces { A -> C } and { B -> C }, construct the space
1588 * { [A -> B] -> C }
1590 __isl_give isl_space *isl_space_domain_product(__isl_take isl_space *left,
1591 __isl_take isl_space *right)
1593 isl_space *ran, *dom1, *dom2, *nest;
1595 if (isl_space_check_equal_params(left, right) < 0)
1596 goto error;
1598 if (!isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_out))
1599 isl_die(left->ctx, isl_error_invalid,
1600 "ranges need to match", goto error);
1602 ran = isl_space_range(isl_space_copy(left));
1604 dom1 = isl_space_domain(left);
1605 dom2 = isl_space_domain(right);
1606 nest = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1608 return isl_space_join(isl_space_reverse(nest), ran);
1609 error:
1610 isl_space_free(left);
1611 isl_space_free(right);
1612 return NULL;
1615 __isl_give isl_space *isl_space_range_product(__isl_take isl_space *left,
1616 __isl_take isl_space *right)
1618 isl_space *dom, *ran1, *ran2, *nest;
1620 if (isl_space_check_equal_params(left, right) < 0)
1621 goto error;
1623 if (!isl_space_tuple_is_equal(left, isl_dim_in, right, isl_dim_in))
1624 isl_die(left->ctx, isl_error_invalid,
1625 "domains need to match", goto error);
1627 dom = isl_space_domain(isl_space_copy(left));
1629 ran1 = isl_space_range(left);
1630 ran2 = isl_space_range(right);
1631 nest = isl_space_wrap(isl_space_join(isl_space_reverse(ran1), ran2));
1633 return isl_space_join(isl_space_reverse(dom), nest);
1634 error:
1635 isl_space_free(left);
1636 isl_space_free(right);
1637 return NULL;
1640 /* Given a space of the form [A -> B] -> C, return the space A -> C.
1642 __isl_give isl_space *isl_space_domain_factor_domain(
1643 __isl_take isl_space *space)
1645 isl_space *nested;
1646 isl_space *domain;
1648 if (isl_space_check_domain_is_wrapping(space) < 0)
1649 return isl_space_free(space);
1651 nested = space->nested[0];
1652 domain = isl_space_copy(space);
1653 domain = isl_space_drop_dims(domain, isl_dim_in,
1654 nested->n_in, nested->n_out);
1655 if (!domain)
1656 return isl_space_free(space);
1657 if (nested->tuple_id[0]) {
1658 domain->tuple_id[0] = isl_id_copy(nested->tuple_id[0]);
1659 if (!domain->tuple_id[0])
1660 goto error;
1662 if (nested->nested[0]) {
1663 domain->nested[0] = isl_space_copy(nested->nested[0]);
1664 if (!domain->nested[0])
1665 goto error;
1668 isl_space_free(space);
1669 return domain;
1670 error:
1671 isl_space_free(space);
1672 isl_space_free(domain);
1673 return NULL;
1676 /* Given a space of the form [A -> B] -> C, return the space B -> C.
1678 __isl_give isl_space *isl_space_domain_factor_range(
1679 __isl_take isl_space *space)
1681 isl_space *nested;
1682 isl_space *range;
1684 if (isl_space_check_domain_is_wrapping(space) < 0)
1685 return isl_space_free(space);
1687 nested = space->nested[0];
1688 range = isl_space_copy(space);
1689 range = isl_space_drop_dims(range, isl_dim_in, 0, nested->n_in);
1690 if (!range)
1691 return isl_space_free(space);
1692 if (nested->tuple_id[1]) {
1693 range->tuple_id[0] = isl_id_copy(nested->tuple_id[1]);
1694 if (!range->tuple_id[0])
1695 goto error;
1697 if (nested->nested[1]) {
1698 range->nested[0] = isl_space_copy(nested->nested[1]);
1699 if (!range->nested[0])
1700 goto error;
1703 isl_space_free(space);
1704 return range;
1705 error:
1706 isl_space_free(space);
1707 isl_space_free(range);
1708 return NULL;
1711 /* Internal function that selects the domain of the map that is
1712 * embedded in either a set space or the range of a map space.
1713 * In particular, given a space of the form [A -> B], return the space A.
1714 * Given a space of the form A -> [B -> C], return the space A -> B.
1716 static __isl_give isl_space *range_factor_domain(__isl_take isl_space *space)
1718 isl_space *nested;
1719 isl_space *domain;
1721 if (!space)
1722 return NULL;
1724 nested = space->nested[1];
1725 domain = isl_space_copy(space);
1726 domain = isl_space_drop_dims(domain, isl_dim_out,
1727 nested->n_in, nested->n_out);
1728 if (!domain)
1729 return isl_space_free(space);
1730 if (nested->tuple_id[0]) {
1731 domain->tuple_id[1] = isl_id_copy(nested->tuple_id[0]);
1732 if (!domain->tuple_id[1])
1733 goto error;
1735 if (nested->nested[0]) {
1736 domain->nested[1] = isl_space_copy(nested->nested[0]);
1737 if (!domain->nested[1])
1738 goto error;
1741 isl_space_free(space);
1742 return domain;
1743 error:
1744 isl_space_free(space);
1745 isl_space_free(domain);
1746 return NULL;
1749 /* Given a space of the form A -> [B -> C], return the space A -> B.
1751 __isl_give isl_space *isl_space_range_factor_domain(
1752 __isl_take isl_space *space)
1754 if (isl_space_check_range_is_wrapping(space) < 0)
1755 return isl_space_free(space);
1757 return range_factor_domain(space);
1760 /* Given a space of the form [A -> B], return the space A.
1762 static __isl_give isl_space *set_factor_domain(__isl_take isl_space *space)
1764 if (!space)
1765 return NULL;
1766 if (!isl_space_is_wrapping(space))
1767 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1768 "not a product", return isl_space_free(space));
1770 return range_factor_domain(space);
1773 /* Given a space of the form [A -> B] -> [C -> D], return the space A -> C.
1774 * Given a space of the form [A -> B], return the space A.
1776 __isl_give isl_space *isl_space_factor_domain(__isl_take isl_space *space)
1778 if (!space)
1779 return NULL;
1780 if (isl_space_is_set(space))
1781 return set_factor_domain(space);
1782 space = isl_space_domain_factor_domain(space);
1783 space = isl_space_range_factor_domain(space);
1784 return space;
1787 /* Internal function that selects the range of the map that is
1788 * embedded in either a set space or the range of a map space.
1789 * In particular, given a space of the form [A -> B], return the space B.
1790 * Given a space of the form A -> [B -> C], return the space A -> C.
1792 static __isl_give isl_space *range_factor_range(__isl_take isl_space *space)
1794 isl_space *nested;
1795 isl_space *range;
1797 if (!space)
1798 return NULL;
1800 nested = space->nested[1];
1801 range = isl_space_copy(space);
1802 range = isl_space_drop_dims(range, isl_dim_out, 0, nested->n_in);
1803 if (!range)
1804 return isl_space_free(space);
1805 if (nested->tuple_id[1]) {
1806 range->tuple_id[1] = isl_id_copy(nested->tuple_id[1]);
1807 if (!range->tuple_id[1])
1808 goto error;
1810 if (nested->nested[1]) {
1811 range->nested[1] = isl_space_copy(nested->nested[1]);
1812 if (!range->nested[1])
1813 goto error;
1816 isl_space_free(space);
1817 return range;
1818 error:
1819 isl_space_free(space);
1820 isl_space_free(range);
1821 return NULL;
1824 /* Given a space of the form A -> [B -> C], return the space A -> C.
1826 __isl_give isl_space *isl_space_range_factor_range(
1827 __isl_take isl_space *space)
1829 if (isl_space_check_range_is_wrapping(space) < 0)
1830 return isl_space_free(space);
1832 return range_factor_range(space);
1835 /* Given a space of the form [A -> B], return the space B.
1837 static __isl_give isl_space *set_factor_range(__isl_take isl_space *space)
1839 if (!space)
1840 return NULL;
1841 if (!isl_space_is_wrapping(space))
1842 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1843 "not a product", return isl_space_free(space));
1845 return range_factor_range(space);
1848 /* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
1849 * Given a space of the form [A -> B], return the space B.
1851 __isl_give isl_space *isl_space_factor_range(__isl_take isl_space *space)
1853 if (!space)
1854 return NULL;
1855 if (isl_space_is_set(space))
1856 return set_factor_range(space);
1857 space = isl_space_domain_factor_range(space);
1858 space = isl_space_range_factor_range(space);
1859 return space;
1862 __isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *space)
1864 isl_ctx *ctx;
1865 isl_id **ids = NULL;
1866 int n_id;
1868 if (!space)
1869 return NULL;
1870 ctx = isl_space_get_ctx(space);
1871 if (!isl_space_is_set(space))
1872 isl_die(ctx, isl_error_invalid, "not a set space", goto error);
1873 space = isl_space_cow(space);
1874 if (!space)
1875 return NULL;
1876 n_id = space->nparam + space->n_out + space->n_out;
1877 if (n_id > 0 && space->ids) {
1878 ids = isl_calloc_array(space->ctx, isl_id *, n_id);
1879 if (!ids)
1880 goto error;
1881 get_ids(space, isl_dim_param, 0, space->nparam, ids);
1882 get_ids(space, isl_dim_out, 0, space->n_out,
1883 ids + space->nparam);
1885 space->n_in = space->n_out;
1886 if (ids) {
1887 free(space->ids);
1888 space->ids = ids;
1889 space->n_id = n_id;
1890 space = copy_ids(space, isl_dim_out, 0, space, isl_dim_in);
1892 isl_id_free(space->tuple_id[0]);
1893 space->tuple_id[0] = isl_id_copy(space->tuple_id[1]);
1894 isl_space_free(space->nested[0]);
1895 space->nested[0] = isl_space_copy(space->nested[1]);
1896 return space;
1897 error:
1898 isl_space_free(space);
1899 return NULL;
1902 __isl_give isl_space *isl_space_map_from_domain_and_range(
1903 __isl_take isl_space *domain, __isl_take isl_space *range)
1905 if (!domain || !range)
1906 goto error;
1907 if (!isl_space_is_set(domain))
1908 isl_die(isl_space_get_ctx(domain), isl_error_invalid,
1909 "domain is not a set space", goto error);
1910 if (!isl_space_is_set(range))
1911 isl_die(isl_space_get_ctx(range), isl_error_invalid,
1912 "range is not a set space", goto error);
1913 return isl_space_join(isl_space_reverse(domain), range);
1914 error:
1915 isl_space_free(domain);
1916 isl_space_free(range);
1917 return NULL;
1920 static __isl_give isl_space *set_ids(__isl_take isl_space *space,
1921 enum isl_dim_type type,
1922 unsigned first, unsigned n, __isl_take isl_id **ids)
1924 int i;
1926 for (i = 0; i < n ; ++i)
1927 space = set_id(space, type, first + i, ids[i]);
1929 return space;
1932 __isl_give isl_space *isl_space_reverse(__isl_take isl_space *space)
1934 unsigned t;
1935 isl_bool equal;
1936 isl_space *nested;
1937 isl_id **ids = NULL;
1938 isl_id *id;
1940 equal = match(space, isl_dim_in, space, isl_dim_out);
1941 if (equal < 0)
1942 return isl_space_free(space);
1943 if (equal)
1944 return space;
1946 space = isl_space_cow(space);
1947 if (!space)
1948 return NULL;
1950 id = space->tuple_id[0];
1951 space->tuple_id[0] = space->tuple_id[1];
1952 space->tuple_id[1] = id;
1954 nested = space->nested[0];
1955 space->nested[0] = space->nested[1];
1956 space->nested[1] = nested;
1958 if (space->ids) {
1959 int n_id = space->n_in + space->n_out;
1960 ids = isl_alloc_array(space->ctx, isl_id *, n_id);
1961 if (n_id && !ids)
1962 goto error;
1963 get_ids(space, isl_dim_in, 0, space->n_in, ids);
1964 get_ids(space, isl_dim_out, 0, space->n_out, ids + space->n_in);
1967 t = space->n_in;
1968 space->n_in = space->n_out;
1969 space->n_out = t;
1971 if (space->ids) {
1972 space = set_ids(space, isl_dim_out, 0, space->n_out, ids);
1973 space = set_ids(space, isl_dim_in, 0, space->n_in,
1974 ids + space->n_out);
1975 free(ids);
1978 return space;
1979 error:
1980 free(ids);
1981 isl_space_free(space);
1982 return NULL;
1985 /* Given a space A -> (B -> C), return the corresponding space
1986 * A -> (C -> B).
1988 * If the range tuple is named, then the name is only preserved
1989 * if B and C are equal tuples, in which case the output
1990 * of this function is identical to the input.
1992 __isl_give isl_space *isl_space_range_reverse(__isl_take isl_space *space)
1994 isl_space *nested;
1995 isl_bool equal;
1997 if (isl_space_check_range_is_wrapping(space) < 0)
1998 return isl_space_free(space);
2000 nested = isl_space_peek_nested(space, 1);
2001 equal = isl_space_tuple_is_equal(nested, isl_dim_in,
2002 nested, isl_dim_out);
2003 if (equal < 0)
2004 return isl_space_free(space);
2006 nested = isl_space_take_nested(space, 1);
2007 nested = isl_space_reverse(nested);
2008 space = isl_space_restore_nested(space, 1, nested);
2009 if (!equal)
2010 space = isl_space_reset_tuple_id(space, isl_dim_out);
2012 return space;
2015 __isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *space,
2016 enum isl_dim_type type, unsigned first, unsigned num)
2018 int i;
2020 if (!space)
2021 return NULL;
2023 if (num == 0)
2024 return isl_space_reset(space, type);
2026 if (!valid_dim_type(type))
2027 isl_die(space->ctx, isl_error_invalid,
2028 "cannot drop dimensions of specified type", goto error);
2030 if (isl_space_check_range(space, type, first, num) < 0)
2031 return isl_space_free(space);
2032 space = isl_space_cow(space);
2033 if (!space)
2034 goto error;
2035 if (space->ids) {
2036 space = extend_ids(space);
2037 if (!space)
2038 goto error;
2039 for (i = 0; i < num; ++i)
2040 isl_id_free(get_id(space, type, first + i));
2041 for (i = first+num; i < n(space, type); ++i)
2042 set_id(space, type, i - num, get_id(space, type, i));
2043 switch (type) {
2044 case isl_dim_param:
2045 get_ids(space, isl_dim_in, 0, space->n_in,
2046 space->ids + offset(space, isl_dim_in) - num);
2047 case isl_dim_in:
2048 get_ids(space, isl_dim_out, 0, space->n_out,
2049 space->ids + offset(space, isl_dim_out) - num);
2050 default:
2053 space->n_id -= num;
2055 switch (type) {
2056 case isl_dim_param: space->nparam -= num; break;
2057 case isl_dim_in: space->n_in -= num; break;
2058 case isl_dim_out: space->n_out -= num; break;
2059 default: ;
2061 space = isl_space_reset(space, type);
2062 if (type == isl_dim_param) {
2063 if (space && space->nested[0] &&
2064 !(space->nested[0] = isl_space_drop_dims(space->nested[0],
2065 isl_dim_param, first, num)))
2066 goto error;
2067 if (space && space->nested[1] &&
2068 !(space->nested[1] = isl_space_drop_dims(space->nested[1],
2069 isl_dim_param, first, num)))
2070 goto error;
2072 return space;
2073 error:
2074 isl_space_free(space);
2075 return NULL;
2078 __isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *space,
2079 unsigned first, unsigned n)
2081 if (!space)
2082 return NULL;
2083 return isl_space_drop_dims(space, isl_dim_in, first, n);
2086 __isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *space,
2087 unsigned first, unsigned n)
2089 if (!space)
2090 return NULL;
2091 return isl_space_drop_dims(space, isl_dim_out, first, n);
2094 /* Remove all parameters from "space".
2096 __isl_give isl_space *isl_space_drop_all_params(__isl_take isl_space *space)
2098 isl_size nparam;
2100 nparam = isl_space_dim(space, isl_dim_param);
2101 if (nparam < 0)
2102 return isl_space_free(space);
2103 return isl_space_drop_dims(space, isl_dim_param, 0, nparam);
2106 __isl_give isl_space *isl_space_domain(__isl_take isl_space *space)
2108 if (!space)
2109 return NULL;
2110 space = isl_space_drop_dims(space, isl_dim_out, 0, space->n_out);
2111 space = isl_space_reverse(space);
2112 space = mark_as_set(space);
2113 return space;
2116 __isl_give isl_space *isl_space_from_domain(__isl_take isl_space *space)
2118 if (!space)
2119 return NULL;
2120 if (!isl_space_is_set(space))
2121 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2122 "not a set space", goto error);
2123 space = isl_space_reverse(space);
2124 space = isl_space_reset(space, isl_dim_out);
2125 return space;
2126 error:
2127 isl_space_free(space);
2128 return NULL;
2131 __isl_give isl_space *isl_space_range(__isl_take isl_space *space)
2133 if (!space)
2134 return NULL;
2135 space = isl_space_drop_dims(space, isl_dim_in, 0, space->n_in);
2136 space = mark_as_set(space);
2137 return space;
2140 __isl_give isl_space *isl_space_from_range(__isl_take isl_space *space)
2142 if (!space)
2143 return NULL;
2144 if (!isl_space_is_set(space))
2145 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2146 "not a set space", goto error);
2147 return isl_space_reset(space, isl_dim_in);
2148 error:
2149 isl_space_free(space);
2150 return NULL;
2153 /* Given a map space A -> B, return the map space [A -> B] -> A.
2155 __isl_give isl_space *isl_space_domain_map(__isl_take isl_space *space)
2157 isl_space *domain;
2159 domain = isl_space_from_range(isl_space_domain(isl_space_copy(space)));
2160 space = isl_space_from_domain(isl_space_wrap(space));
2161 space = isl_space_join(space, domain);
2163 return space;
2166 /* Given a map space A -> B, return the map space [A -> B] -> B.
2168 __isl_give isl_space *isl_space_range_map(__isl_take isl_space *space)
2170 isl_space *range;
2172 range = isl_space_from_range(isl_space_range(isl_space_copy(space)));
2173 space = isl_space_from_domain(isl_space_wrap(space));
2174 space = isl_space_join(space, range);
2176 return space;
2179 __isl_give isl_space *isl_space_params(__isl_take isl_space *space)
2181 isl_size n_in, n_out;
2183 if (isl_space_is_params(space))
2184 return space;
2185 n_in = isl_space_dim(space, isl_dim_in);
2186 n_out = isl_space_dim(space, isl_dim_out);
2187 if (n_in < 0 || n_out < 0)
2188 return isl_space_free(space);
2189 space = isl_space_drop_dims(space, isl_dim_in, 0, n_in);
2190 space = isl_space_drop_dims(space, isl_dim_out, 0, n_out);
2191 space = mark_as_params(space);
2192 return space;
2195 __isl_give isl_space *isl_space_set_from_params(__isl_take isl_space *space)
2197 if (!space)
2198 return NULL;
2199 if (!isl_space_is_params(space))
2200 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2201 "not a parameter space", goto error);
2202 return isl_space_reset(space, isl_dim_set);
2203 error:
2204 isl_space_free(space);
2205 return NULL;
2208 /* Add an unnamed tuple of dimension "dim" to "space".
2209 * This requires "space" to be a parameter or set space.
2211 * In particular, if "space" is a parameter space, then return
2212 * a set space with the given dimension.
2213 * If "space" is a set space, then return a map space
2214 * with "space" as domain and a range of the given dimension.
2216 __isl_give isl_space *isl_space_add_unnamed_tuple_ui(
2217 __isl_take isl_space *space, unsigned dim)
2219 isl_bool is_params, is_set;
2221 is_params = isl_space_is_params(space);
2222 is_set = isl_space_is_set(space);
2223 if (is_params < 0 || is_set < 0)
2224 return isl_space_free(space);
2225 if (!is_params && !is_set)
2226 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2227 "cannot add tuple to map space",
2228 return isl_space_free(space));
2229 if (is_params)
2230 space = isl_space_set_from_params(space);
2231 else
2232 space = isl_space_from_domain(space);
2233 space = isl_space_add_dims(space, isl_dim_out, dim);
2234 return space;
2237 /* Add a tuple of dimension "dim" and with tuple identifier "tuple_id"
2238 * to "space".
2239 * This requires "space" to be a parameter or set space.
2241 __isl_give isl_space *isl_space_add_named_tuple_id_ui(
2242 __isl_take isl_space *space, __isl_take isl_id *tuple_id, unsigned dim)
2244 space = isl_space_add_unnamed_tuple_ui(space, dim);
2245 space = isl_space_set_tuple_id(space, isl_dim_out, tuple_id);
2246 return space;
2249 /* Check that the identifiers in "tuple" do not appear as parameters
2250 * in "space".
2252 static isl_stat check_fresh_params(__isl_keep isl_space *space,
2253 __isl_keep isl_multi_id *tuple)
2255 int i;
2256 isl_size n;
2258 n = isl_multi_id_size(tuple);
2259 if (n < 0)
2260 return isl_stat_error;
2261 for (i = 0; i < n; ++i) {
2262 isl_id *id;
2263 int pos;
2265 id = isl_multi_id_get_at(tuple, i);
2266 if (!id)
2267 return isl_stat_error;
2268 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
2269 isl_id_free(id);
2270 if (pos >= 0)
2271 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2272 "parameters not unique", return isl_stat_error);
2275 return isl_stat_ok;
2278 /* Add the identifiers in "tuple" as parameters of "space"
2279 * that are known to be fresh.
2281 static __isl_give isl_space *add_bind_params(__isl_take isl_space *space,
2282 __isl_keep isl_multi_id *tuple)
2284 int i;
2285 isl_size first, n;
2287 first = isl_space_dim(space, isl_dim_param);
2288 n = isl_multi_id_size(tuple);
2289 if (first < 0 || n < 0)
2290 return isl_space_free(space);
2291 space = isl_space_add_dims(space, isl_dim_param, n);
2292 for (i = 0; i < n; ++i) {
2293 isl_id *id;
2295 id = isl_multi_id_get_at(tuple, i);
2296 space = isl_space_set_dim_id(space,
2297 isl_dim_param, first + i, id);
2300 return space;
2303 /* Internal function that removes the set tuple of "space",
2304 * which is assumed to correspond to the range space of "tuple", and
2305 * adds the identifiers in "tuple" as fresh parameters.
2306 * In other words, the set dimensions of "space" are reinterpreted
2307 * as parameters, but stay in the same global positions.
2309 __isl_give isl_space *isl_space_bind_set(__isl_take isl_space *space,
2310 __isl_keep isl_multi_id *tuple)
2312 isl_space *tuple_space;
2314 if (isl_space_check_is_set(space) < 0)
2315 return isl_space_free(space);
2316 tuple_space = isl_multi_id_peek_space(tuple);
2317 if (isl_space_check_equal_tuples(tuple_space, space) < 0)
2318 return isl_space_free(space);
2319 if (check_fresh_params(space, tuple) < 0)
2320 return isl_space_free(space);
2321 space = isl_space_params(space);
2322 space = add_bind_params(space, tuple);
2323 return space;
2326 /* Internal function that removes the domain tuple of the map space "space",
2327 * which is assumed to correspond to the range space of "tuple", and
2328 * adds the identifiers in "tuple" as fresh parameters.
2329 * In other words, the domain dimensions of "space" are reinterpreted
2330 * as parameters, but stay in the same global positions.
2332 __isl_give isl_space *isl_space_bind_map_domain(__isl_take isl_space *space,
2333 __isl_keep isl_multi_id *tuple)
2335 isl_space *tuple_space;
2337 if (isl_space_check_is_map(space) < 0)
2338 return isl_space_free(space);
2339 tuple_space = isl_multi_id_peek_space(tuple);
2340 if (isl_space_check_domain_tuples(tuple_space, space) < 0)
2341 return isl_space_free(space);
2342 if (check_fresh_params(space, tuple) < 0)
2343 return isl_space_free(space);
2344 space = isl_space_range(space);
2345 space = add_bind_params(space, tuple);
2346 return space;
2349 /* Internal function that, given a space of the form [A -> B] -> C and
2350 * a tuple of identifiers in A, returns a space B -> C with
2351 * the identifiers in "tuple" added as fresh parameters.
2352 * In other words, the domain dimensions of the wrapped relation
2353 * in the domain of "space" are reinterpreted
2354 * as parameters, but stay in the same global positions.
2356 __isl_give isl_space *isl_space_bind_domain_wrapped_domain(
2357 __isl_take isl_space *space, __isl_keep isl_multi_id *tuple)
2359 isl_space *tuple_space;
2361 if (isl_space_check_is_map(space) < 0)
2362 return isl_space_free(space);
2363 tuple_space = isl_multi_id_peek_space(tuple);
2364 if (isl_space_check_domain_wrapped_domain_tuples(tuple_space,
2365 space) < 0)
2366 return isl_space_free(space);
2367 if (check_fresh_params(space, tuple) < 0)
2368 return isl_space_free(space);
2369 space = isl_space_domain_factor_range(space);
2370 space = add_bind_params(space, tuple);
2371 return space;
2374 /* Insert a domain tuple in "space" corresponding to the set space "domain".
2375 * In particular, if "space" is a parameter space, then the result
2376 * is the set space "domain" combined with the parameters of "space".
2377 * If "space" is a set space, then the result
2378 * is a map space with "domain" as domain and the original space as range.
2380 static __isl_give isl_space *isl_space_insert_domain(
2381 __isl_take isl_space *space, __isl_take isl_space *domain)
2383 isl_bool is_params;
2385 domain = isl_space_replace_params(domain, space);
2387 is_params = isl_space_is_params(space);
2388 if (is_params < 0) {
2389 isl_space_free(domain);
2390 space = isl_space_free(space);
2391 } else if (is_params) {
2392 isl_space_free(space);
2393 space = domain;
2394 } else {
2395 space = isl_space_map_from_domain_and_range(domain, space);
2397 return space;
2400 /* Internal function that introduces a domain in "space"
2401 * corresponding to the range space of "tuple".
2402 * In particular, if "space" is a parameter space, then the result
2403 * is a set space. If "space" is a set space, then the result
2404 * is a map space with the original space as range.
2405 * Parameters that correspond to the identifiers in "tuple" are removed.
2407 * The parameters are removed in reverse order (under the assumption
2408 * that they appear in the same order in "multi") because
2409 * it is slightly more efficient to remove parameters at the end.
2411 * For pretty-printing purposes, the identifiers of the set dimensions
2412 * of the introduced domain are set to the identifiers in "tuple".
2414 __isl_give isl_space *isl_space_unbind_params_insert_domain(
2415 __isl_take isl_space *space, __isl_keep isl_multi_id *tuple)
2417 int i;
2418 isl_size n;
2419 isl_space *tuple_space;
2421 n = isl_multi_id_size(tuple);
2422 if (!space || n < 0)
2423 return isl_space_free(space);
2424 for (i = n - 1; i >= 0; --i) {
2425 isl_id *id;
2426 int pos;
2428 id = isl_multi_id_get_id(tuple, i);
2429 if (!id)
2430 return isl_space_free(space);
2431 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
2432 isl_id_free(id);
2433 if (pos < 0)
2434 continue;
2435 space = isl_space_drop_dims(space, isl_dim_param, pos, 1);
2437 tuple_space = isl_multi_id_get_space(tuple);
2438 for (i = 0; i < n; ++i) {
2439 isl_id *id;
2441 id = isl_multi_id_get_id(tuple, i);
2442 tuple_space = isl_space_set_dim_id(tuple_space,
2443 isl_dim_set, i, id);
2445 return isl_space_insert_domain(space, tuple_space);
2448 __isl_give isl_space *isl_space_underlying(__isl_take isl_space *space,
2449 unsigned n_div)
2451 int i;
2452 isl_bool is_set;
2454 is_set = isl_space_is_set(space);
2455 if (is_set < 0)
2456 return isl_space_free(space);
2457 if (n_div == 0 && is_set &&
2458 space->nparam == 0 && space->n_in == 0 && space->n_id == 0)
2459 return isl_space_reset(space, isl_dim_out);
2460 space = isl_space_cow(space);
2461 if (!space)
2462 return NULL;
2463 space->n_out += space->nparam + space->n_in + n_div;
2464 space->nparam = 0;
2465 space->n_in = 0;
2467 for (i = 0; i < space->n_id; ++i)
2468 isl_id_free(get_id(space, isl_dim_out, i));
2469 space->n_id = 0;
2470 space = isl_space_reset(space, isl_dim_in);
2471 space = isl_space_reset(space, isl_dim_out);
2472 space = mark_as_set(space);
2474 return space;
2477 /* Are the two spaces the same, including positions and names of parameters?
2479 isl_bool isl_space_is_equal(__isl_keep isl_space *space1,
2480 __isl_keep isl_space *space2)
2482 isl_bool equal;
2484 if (!space1 || !space2)
2485 return isl_bool_error;
2486 if (space1 == space2)
2487 return isl_bool_true;
2488 equal = isl_space_has_equal_params(space1, space2);
2489 if (equal < 0 || !equal)
2490 return equal;
2491 return isl_space_has_equal_tuples(space1, space2);
2494 /* Do the tuples of "space1" correspond to those of the domain of "space2"?
2495 * That is, is "space1" equal to the domain of "space2", ignoring parameters.
2497 * "space2" is allowed to be a set space, in which case "space1"
2498 * should be a parameter space.
2500 isl_bool isl_space_has_domain_tuples(__isl_keep isl_space *space1,
2501 __isl_keep isl_space *space2)
2503 isl_bool is_set;
2505 is_set = isl_space_is_set(space1);
2506 if (is_set < 0 || !is_set)
2507 return is_set;
2508 return isl_space_tuple_is_equal(space1, isl_dim_set,
2509 space2, isl_dim_in);
2512 /* Do the tuples of "space1" correspond to those of the range of "space2"?
2513 * That is, is "space1" equal to the range of "space2", ignoring parameters.
2515 * "space2" is allowed to be the space of a set,
2516 * in which case it should be equal to "space1", ignoring parameters.
2518 isl_bool isl_space_has_range_tuples(__isl_keep isl_space *space1,
2519 __isl_keep isl_space *space2)
2521 isl_bool is_set;
2523 is_set = isl_space_is_set(space1);
2524 if (is_set < 0 || !is_set)
2525 return is_set;
2526 return isl_space_tuple_is_equal(space1, isl_dim_set,
2527 space2, isl_dim_out);
2530 /* Check that the tuples of "space1" correspond to those
2531 * of the domain of "space2".
2532 * That is, check that "space1" is equal to the domain of "space2",
2533 * ignoring parameters.
2535 isl_stat isl_space_check_domain_tuples(__isl_keep isl_space *space1,
2536 __isl_keep isl_space *space2)
2538 isl_bool is_equal;
2540 is_equal = isl_space_has_domain_tuples(space1, space2);
2541 return check_match(space1, is_equal);
2544 /* Check that the tuples of "space1" correspond to those
2545 * of the domain of the wrapped relation in the domain of "space2".
2546 * That is, check that "space1" is equal to this domain,
2547 * ignoring parameters.
2549 isl_stat isl_space_check_domain_wrapped_domain_tuples(
2550 __isl_keep isl_space *space1, __isl_keep isl_space *space2)
2552 isl_space *domain;
2553 isl_stat r;
2555 domain = isl_space_unwrap(isl_space_domain(isl_space_copy(space2)));
2556 r = isl_space_check_domain_tuples(space1, domain);
2557 isl_space_free(domain);
2559 return r;
2562 /* Is space1 equal to the domain of space2?
2564 * In the internal version we also allow space2 to be the space of a set,
2565 * provided space1 is a parameter space.
2567 isl_bool isl_space_is_domain_internal(__isl_keep isl_space *space1,
2568 __isl_keep isl_space *space2)
2570 isl_bool equal_params;
2572 if (!space1 || !space2)
2573 return isl_bool_error;
2574 equal_params = isl_space_has_equal_params(space1, space2);
2575 if (equal_params < 0 || !equal_params)
2576 return equal_params;
2577 return isl_space_has_domain_tuples(space1, space2);
2580 /* Is space1 equal to the domain of space2?
2582 isl_bool isl_space_is_domain(__isl_keep isl_space *space1,
2583 __isl_keep isl_space *space2)
2585 if (!space2)
2586 return isl_bool_error;
2587 if (!isl_space_is_map(space2))
2588 return isl_bool_false;
2589 return isl_space_is_domain_internal(space1, space2);
2592 /* Is space1 equal to the range of space2?
2594 * In the internal version, space2 is allowed to be the space of a set,
2595 * in which case it should be equal to space1.
2597 isl_bool isl_space_is_range_internal(__isl_keep isl_space *space1,
2598 __isl_keep isl_space *space2)
2600 isl_bool equal_params;
2602 if (!space1 || !space2)
2603 return isl_bool_error;
2604 equal_params = isl_space_has_equal_params(space1, space2);
2605 if (equal_params < 0 || !equal_params)
2606 return equal_params;
2607 return isl_space_has_range_tuples(space1, space2);
2610 /* Is space1 equal to the range of space2?
2612 isl_bool isl_space_is_range(__isl_keep isl_space *space1,
2613 __isl_keep isl_space *space2)
2615 if (!space2)
2616 return isl_bool_error;
2617 if (!isl_space_is_map(space2))
2618 return isl_bool_false;
2619 return isl_space_is_range_internal(space1, space2);
2622 /* Update "hash" by hashing in the parameters of "space".
2624 static uint32_t isl_hash_params(uint32_t hash, __isl_keep isl_space *space)
2626 int i;
2627 isl_id *id;
2629 if (!space)
2630 return hash;
2632 isl_hash_byte(hash, space->nparam % 256);
2634 for (i = 0; i < space->nparam; ++i) {
2635 id = get_id(space, isl_dim_param, i);
2636 hash = isl_hash_id(hash, id);
2639 return hash;
2642 /* Update "hash" by hashing in the tuples of "space".
2643 * Changes in this function should be reflected in isl_hash_tuples_domain.
2645 static uint32_t isl_hash_tuples(uint32_t hash, __isl_keep isl_space *space)
2647 isl_id *id;
2649 if (!space)
2650 return hash;
2652 isl_hash_byte(hash, space->n_in % 256);
2653 isl_hash_byte(hash, space->n_out % 256);
2655 id = tuple_id(space, isl_dim_in);
2656 hash = isl_hash_id(hash, id);
2657 id = tuple_id(space, isl_dim_out);
2658 hash = isl_hash_id(hash, id);
2660 hash = isl_hash_tuples(hash, space->nested[0]);
2661 hash = isl_hash_tuples(hash, space->nested[1]);
2663 return hash;
2666 /* Update "hash" by hashing in the domain tuple of "space".
2667 * The result of this function is equal to the result of applying
2668 * isl_hash_tuples to the domain of "space".
2670 static uint32_t isl_hash_tuples_domain(uint32_t hash,
2671 __isl_keep isl_space *space)
2673 isl_id *id;
2675 if (!space)
2676 return hash;
2678 isl_hash_byte(hash, 0);
2679 isl_hash_byte(hash, space->n_in % 256);
2681 hash = isl_hash_id(hash, &isl_id_none);
2682 id = tuple_id(space, isl_dim_in);
2683 hash = isl_hash_id(hash, id);
2685 hash = isl_hash_tuples(hash, space->nested[0]);
2687 return hash;
2690 /* Return a hash value that digests the tuples of "space",
2691 * i.e., that ignores the parameters.
2692 * Changes in this function should be reflected
2693 * in isl_space_get_tuple_domain_hash.
2695 uint32_t isl_space_get_tuple_hash(__isl_keep isl_space *space)
2697 uint32_t hash;
2699 if (!space)
2700 return 0;
2702 hash = isl_hash_init();
2703 hash = isl_hash_tuples(hash, space);
2705 return hash;
2708 /* Return the hash value of "space".
2710 uint32_t isl_space_get_full_hash(__isl_keep isl_space *space)
2712 uint32_t hash;
2714 if (!space)
2715 return 0;
2717 hash = isl_hash_init();
2718 hash = isl_hash_params(hash, space);
2719 hash = isl_hash_tuples(hash, space);
2721 return hash;
2724 /* Return the hash value of the domain tuple of "space".
2725 * That is, isl_space_get_tuple_domain_hash(space) is equal to
2726 * isl_space_get_tuple_hash(isl_space_domain(space)).
2728 uint32_t isl_space_get_tuple_domain_hash(__isl_keep isl_space *space)
2730 uint32_t hash;
2732 if (!space)
2733 return 0;
2735 hash = isl_hash_init();
2736 hash = isl_hash_tuples_domain(hash, space);
2738 return hash;
2741 /* Is "space" the space of a set wrapping a map space?
2743 isl_bool isl_space_is_wrapping(__isl_keep isl_space *space)
2745 if (!space)
2746 return isl_bool_error;
2748 if (!isl_space_is_set(space))
2749 return isl_bool_false;
2751 return isl_bool_ok(space->nested[1] != NULL);
2754 /* Is "space" the space of a map where the domain is a wrapped map space?
2756 isl_bool isl_space_domain_is_wrapping(__isl_keep isl_space *space)
2758 if (!space)
2759 return isl_bool_error;
2761 if (isl_space_is_set(space))
2762 return isl_bool_false;
2764 return isl_bool_ok(space->nested[0] != NULL);
2767 /* Is "space" the space of a map where the range is a wrapped map space?
2769 isl_bool isl_space_range_is_wrapping(__isl_keep isl_space *space)
2771 if (!space)
2772 return isl_bool_error;
2774 if (isl_space_is_set(space))
2775 return isl_bool_false;
2777 return isl_bool_ok(space->nested[1] != NULL);
2780 /* Is "space" a product of two spaces?
2781 * That is, is it a wrapping set space or a map space
2782 * with wrapping domain and range?
2784 isl_bool isl_space_is_product(__isl_keep isl_space *space)
2786 isl_bool is_set;
2787 isl_bool is_product;
2789 is_set = isl_space_is_set(space);
2790 if (is_set < 0)
2791 return isl_bool_error;
2792 if (is_set)
2793 return isl_space_is_wrapping(space);
2794 is_product = isl_space_domain_is_wrapping(space);
2795 if (is_product < 0 || !is_product)
2796 return is_product;
2797 return isl_space_range_is_wrapping(space);
2800 __isl_give isl_space *isl_space_wrap(__isl_take isl_space *space)
2802 isl_space *wrap;
2804 if (!space)
2805 return NULL;
2807 wrap = isl_space_set_alloc(space->ctx,
2808 space->nparam, space->n_in + space->n_out);
2810 wrap = copy_ids(wrap, isl_dim_param, 0, space, isl_dim_param);
2811 wrap = copy_ids(wrap, isl_dim_set, 0, space, isl_dim_in);
2812 wrap = copy_ids(wrap, isl_dim_set, space->n_in, space, isl_dim_out);
2814 if (!wrap)
2815 goto error;
2817 wrap->nested[1] = space;
2819 return wrap;
2820 error:
2821 isl_space_free(space);
2822 return NULL;
2825 __isl_give isl_space *isl_space_unwrap(__isl_take isl_space *space)
2827 isl_space *unwrap;
2829 if (!space)
2830 return NULL;
2832 if (!isl_space_is_wrapping(space))
2833 isl_die(space->ctx, isl_error_invalid, "not a wrapping space",
2834 goto error);
2836 unwrap = isl_space_copy(space->nested[1]);
2837 isl_space_free(space);
2839 return unwrap;
2840 error:
2841 isl_space_free(space);
2842 return NULL;
2845 isl_bool isl_space_is_named_or_nested(__isl_keep isl_space *space,
2846 enum isl_dim_type type)
2848 if (type != isl_dim_in && type != isl_dim_out)
2849 return isl_bool_false;
2850 if (!space)
2851 return isl_bool_error;
2852 if (space->tuple_id[type - isl_dim_in])
2853 return isl_bool_true;
2854 if (space->nested[type - isl_dim_in])
2855 return isl_bool_true;
2856 return isl_bool_false;
2859 isl_bool isl_space_may_be_set(__isl_keep isl_space *space)
2861 isl_bool nested;
2862 isl_size n_in;
2864 if (!space)
2865 return isl_bool_error;
2866 if (isl_space_is_set(space))
2867 return isl_bool_true;
2868 n_in = isl_space_dim(space, isl_dim_in);
2869 if (n_in < 0)
2870 return isl_bool_error;
2871 if (n_in != 0)
2872 return isl_bool_false;
2873 nested = isl_space_is_named_or_nested(space, isl_dim_in);
2874 if (nested < 0 || nested)
2875 return isl_bool_not(nested);
2876 return isl_bool_true;
2879 __isl_give isl_space *isl_space_reset(__isl_take isl_space *space,
2880 enum isl_dim_type type)
2882 if (!isl_space_is_named_or_nested(space, type))
2883 return space;
2885 space = isl_space_cow(space);
2886 if (!space)
2887 return NULL;
2889 isl_id_free(space->tuple_id[type - isl_dim_in]);
2890 space->tuple_id[type - isl_dim_in] = NULL;
2891 isl_space_free(space->nested[type - isl_dim_in]);
2892 space->nested[type - isl_dim_in] = NULL;
2894 return space;
2897 __isl_give isl_space *isl_space_flatten(__isl_take isl_space *space)
2899 if (!space)
2900 return NULL;
2901 if (!space->nested[0] && !space->nested[1])
2902 return space;
2904 if (space->nested[0])
2905 space = isl_space_reset(space, isl_dim_in);
2906 if (space && space->nested[1])
2907 space = isl_space_reset(space, isl_dim_out);
2909 return space;
2912 __isl_give isl_space *isl_space_flatten_domain(__isl_take isl_space *space)
2914 if (!space)
2915 return NULL;
2916 if (!space->nested[0])
2917 return space;
2919 return isl_space_reset(space, isl_dim_in);
2922 __isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *space)
2924 if (!space)
2925 return NULL;
2926 if (!space->nested[1])
2927 return space;
2929 return isl_space_reset(space, isl_dim_out);
2932 /* Replace the parameters of dst by those of src.
2934 __isl_give isl_space *isl_space_replace_params(__isl_take isl_space *dst,
2935 __isl_keep isl_space *src)
2937 isl_size dst_dim, src_dim;
2938 isl_bool equal_params;
2939 enum isl_dim_type type = isl_dim_param;
2941 equal_params = isl_space_has_equal_params(dst, src);
2942 if (equal_params < 0)
2943 return isl_space_free(dst);
2944 if (equal_params)
2945 return dst;
2947 dst = isl_space_cow(dst);
2949 dst_dim = isl_space_dim(dst, type);
2950 src_dim = isl_space_dim(src, type);
2951 if (dst_dim < 0 || src_dim < 0)
2952 goto error;
2954 dst = isl_space_drop_dims(dst, type, 0, dst_dim);
2955 dst = isl_space_add_dims(dst, type, src_dim);
2956 dst = copy_ids(dst, type, 0, src, type);
2958 if (dst) {
2959 int i;
2960 for (i = 0; i <= 1; ++i) {
2961 isl_space *nested;
2963 if (!dst->nested[i])
2964 continue;
2965 nested = isl_space_take_nested(dst, i);
2966 nested = isl_space_replace_params(nested, src);
2967 dst = isl_space_restore_nested(dst, i, nested);
2968 if (!dst)
2969 return NULL;
2973 return dst;
2974 error:
2975 isl_space_free(dst);
2976 return NULL;
2979 /* Given two tuples ("dst_type" in "dst" and "src_type" in "src")
2980 * of the same size, check if any of the dimensions in the "dst" tuple
2981 * have no identifier, while the corresponding dimensions in "src"
2982 * does have an identifier,
2983 * If so, copy the identifier over to "dst".
2985 __isl_give isl_space *isl_space_copy_ids_if_unset(__isl_take isl_space *dst,
2986 enum isl_dim_type dst_type, __isl_keep isl_space *src,
2987 enum isl_dim_type src_type)
2989 int i;
2990 isl_size n;
2992 n = isl_space_dim(dst, dst_type);
2993 if (n < 0)
2994 return isl_space_free(dst);
2995 for (i = 0; i < n; ++i) {
2996 isl_bool set;
2997 isl_id *id;
2999 set = isl_space_has_dim_id(dst, dst_type, i);
3000 if (set < 0)
3001 return isl_space_free(dst);
3002 if (set)
3003 continue;
3005 set = isl_space_has_dim_id(src, src_type, i);
3006 if (set < 0)
3007 return isl_space_free(dst);
3008 if (!set)
3009 continue;
3011 id = isl_space_get_dim_id(src, src_type, i);
3012 dst = isl_space_set_dim_id(dst, dst_type, i, id);
3015 return dst;
3018 /* Given a space "space" of a set, create a space
3019 * for the lift of the set. In particular, the result
3020 * is of the form lifted[space -> local[..]], with n_local variables in the
3021 * range of the wrapped map.
3023 __isl_give isl_space *isl_space_lift(__isl_take isl_space *space,
3024 unsigned n_local)
3026 isl_space *local_space;
3028 if (!space)
3029 return NULL;
3031 local_space = isl_space_dup(space);
3032 local_space = isl_space_drop_dims(local_space, isl_dim_set, 0,
3033 space->n_out);
3034 local_space = isl_space_add_dims(local_space, isl_dim_set, n_local);
3035 local_space = isl_space_set_tuple_name(local_space,
3036 isl_dim_set, "local");
3037 space = isl_space_join(isl_space_from_domain(space),
3038 isl_space_from_range(local_space));
3039 space = isl_space_wrap(space);
3040 space = isl_space_set_tuple_name(space, isl_dim_set, "lifted");
3042 return space;
3045 isl_bool isl_space_can_zip(__isl_keep isl_space *space)
3047 isl_bool is_set;
3049 is_set = isl_space_is_set(space);
3050 if (is_set < 0)
3051 return isl_bool_error;
3052 if (is_set)
3053 return isl_bool_false;
3054 return isl_space_is_product(space);
3057 __isl_give isl_space *isl_space_zip(__isl_take isl_space *space)
3059 isl_space *dom, *ran;
3060 isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran;
3062 if (!isl_space_can_zip(space))
3063 isl_die(space->ctx, isl_error_invalid, "space cannot be zipped",
3064 goto error);
3066 if (!space)
3067 return NULL;
3068 dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));
3069 ran = isl_space_unwrap(isl_space_range(space));
3070 dom_dom = isl_space_domain(isl_space_copy(dom));
3071 dom_ran = isl_space_range(dom);
3072 ran_dom = isl_space_domain(isl_space_copy(ran));
3073 ran_ran = isl_space_range(ran);
3074 dom = isl_space_join(isl_space_from_domain(dom_dom),
3075 isl_space_from_range(ran_dom));
3076 ran = isl_space_join(isl_space_from_domain(dom_ran),
3077 isl_space_from_range(ran_ran));
3078 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
3079 isl_space_from_range(isl_space_wrap(ran)));
3080 error:
3081 isl_space_free(space);
3082 return NULL;
3085 /* Can we apply isl_space_curry to "space"?
3086 * That is, does is it have a map space with a nested relation in its domain?
3088 isl_bool isl_space_can_curry(__isl_keep isl_space *space)
3090 return isl_space_domain_is_wrapping(space);
3093 /* Given a space (A -> B) -> C, return the corresponding space
3094 * A -> (B -> C).
3096 __isl_give isl_space *isl_space_curry(__isl_take isl_space *space)
3098 isl_space *dom, *ran;
3099 isl_space *dom_dom, *dom_ran;
3101 if (!space)
3102 return NULL;
3104 if (!isl_space_can_curry(space))
3105 isl_die(space->ctx, isl_error_invalid,
3106 "space cannot be curried", goto error);
3108 dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));
3109 ran = isl_space_range(space);
3110 dom_dom = isl_space_domain(isl_space_copy(dom));
3111 dom_ran = isl_space_range(dom);
3112 ran = isl_space_join(isl_space_from_domain(dom_ran),
3113 isl_space_from_range(ran));
3114 return isl_space_join(isl_space_from_domain(dom_dom),
3115 isl_space_from_range(isl_space_wrap(ran)));
3116 error:
3117 isl_space_free(space);
3118 return NULL;
3121 /* Can isl_space_range_curry be applied to "space"?
3122 * That is, does it have a nested relation in its range,
3123 * the domain of which is itself a nested relation?
3125 isl_bool isl_space_can_range_curry(__isl_keep isl_space *space)
3127 isl_bool can;
3129 if (!space)
3130 return isl_bool_error;
3131 can = isl_space_range_is_wrapping(space);
3132 if (can < 0 || !can)
3133 return can;
3134 return isl_space_can_curry(space->nested[1]);
3137 /* Given a space A -> ((B -> C) -> D), return the corresponding space
3138 * A -> (B -> (C -> D)).
3140 __isl_give isl_space *isl_space_range_curry(__isl_take isl_space *space)
3142 isl_space *nested;
3144 if (!space)
3145 return NULL;
3147 if (!isl_space_can_range_curry(space))
3148 isl_die(isl_space_get_ctx(space), isl_error_invalid,
3149 "space range cannot be curried",
3150 return isl_space_free(space));
3152 nested = isl_space_take_nested(space, 1);
3153 nested = isl_space_curry(nested);
3154 space = isl_space_restore_nested(space, 1, nested);
3156 return space;
3159 /* Can we apply isl_space_uncurry to "space"?
3160 * That is, does it have a map space with a nested relation in its range?
3162 isl_bool isl_space_can_uncurry(__isl_keep isl_space *space)
3164 return isl_space_range_is_wrapping(space);
3167 /* Given a space A -> (B -> C), return the corresponding space
3168 * (A -> B) -> C.
3170 __isl_give isl_space *isl_space_uncurry(__isl_take isl_space *space)
3172 isl_space *dom, *ran;
3173 isl_space *ran_dom, *ran_ran;
3175 if (!space)
3176 return NULL;
3178 if (!isl_space_can_uncurry(space))
3179 isl_die(space->ctx, isl_error_invalid,
3180 "space cannot be uncurried",
3181 return isl_space_free(space));
3183 dom = isl_space_domain(isl_space_copy(space));
3184 ran = isl_space_unwrap(isl_space_range(space));
3185 ran_dom = isl_space_domain(isl_space_copy(ran));
3186 ran_ran = isl_space_range(ran);
3187 dom = isl_space_join(isl_space_from_domain(dom),
3188 isl_space_from_range(ran_dom));
3189 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
3190 isl_space_from_range(ran_ran));
3193 isl_bool isl_space_has_named_params(__isl_keep isl_space *space)
3195 int i;
3196 unsigned off;
3198 if (!space)
3199 return isl_bool_error;
3200 if (space->nparam == 0)
3201 return isl_bool_true;
3202 off = isl_space_offset(space, isl_dim_param);
3203 if (off + space->nparam > space->n_id)
3204 return isl_bool_false;
3205 for (i = 0; i < space->nparam; ++i)
3206 if (!space->ids[off + i])
3207 return isl_bool_false;
3208 return isl_bool_true;
3211 /* Check that "space" has only named parameters, reporting an error
3212 * if it does not.
3214 isl_stat isl_space_check_named_params(__isl_keep isl_space *space)
3216 isl_bool named;
3218 named = isl_space_has_named_params(space);
3219 if (named < 0)
3220 return isl_stat_error;
3221 if (!named)
3222 isl_die(isl_space_get_ctx(space), isl_error_invalid,
3223 "unexpected unnamed parameters", return isl_stat_error);
3225 return isl_stat_ok;
3228 /* Align the initial parameters of space1 to match the order in space2.
3230 __isl_give isl_space *isl_space_align_params(__isl_take isl_space *space1,
3231 __isl_take isl_space *space2)
3233 isl_reordering *exp;
3235 if (isl_space_check_named_params(space1) < 0 ||
3236 isl_space_check_named_params(space2) < 0)
3237 goto error;
3239 exp = isl_parameter_alignment_reordering(space1, space2);
3240 exp = isl_reordering_extend_space(exp, space1);
3241 isl_space_free(space2);
3242 space1 = isl_reordering_get_space(exp);
3243 isl_reordering_free(exp);
3244 return space1;
3245 error:
3246 isl_space_free(space1);
3247 isl_space_free(space2);
3248 return NULL;
3251 /* Given the space of set (domain), construct a space for a map
3252 * with as domain the given space and as range the range of "model".
3254 __isl_give isl_space *isl_space_extend_domain_with_range(
3255 __isl_take isl_space *space, __isl_take isl_space *model)
3257 isl_size n_out;
3259 if (!model)
3260 goto error;
3262 space = isl_space_from_domain(space);
3263 n_out = isl_space_dim(model, isl_dim_out);
3264 if (n_out < 0)
3265 goto error;
3266 space = isl_space_add_dims(space, isl_dim_out, n_out);
3267 if (isl_space_has_tuple_id(model, isl_dim_out))
3268 space = isl_space_set_tuple_id(space, isl_dim_out,
3269 isl_space_get_tuple_id(model, isl_dim_out));
3270 if (!space)
3271 goto error;
3272 if (model->nested[1]) {
3273 isl_space *nested = isl_space_copy(model->nested[1]);
3274 isl_size n_nested, n_space;
3275 nested = isl_space_align_params(nested, isl_space_copy(space));
3276 n_nested = isl_space_dim(nested, isl_dim_param);
3277 n_space = isl_space_dim(space, isl_dim_param);
3278 if (n_nested < 0 || n_space < 0)
3279 goto error;
3280 if (n_nested > n_space)
3281 nested = isl_space_drop_dims(nested, isl_dim_param,
3282 n_space, n_nested - n_space);
3283 if (!nested)
3284 goto error;
3285 space->nested[1] = nested;
3287 isl_space_free(model);
3288 return space;
3289 error:
3290 isl_space_free(model);
3291 isl_space_free(space);
3292 return NULL;
3295 /* Compare the "type" dimensions of two isl_spaces.
3297 * The order is fairly arbitrary.
3299 static int isl_space_cmp_type(__isl_keep isl_space *space1,
3300 __isl_keep isl_space *space2, enum isl_dim_type type)
3302 int cmp;
3303 isl_size dim1, dim2;
3304 isl_space *nested1, *nested2;
3306 dim1 = isl_space_dim(space1, type);
3307 dim2 = isl_space_dim(space2, type);
3308 if (dim1 < 0 || dim2 < 0)
3309 return 0;
3310 if (dim1 != dim2)
3311 return dim1 - dim2;
3313 cmp = isl_id_cmp(tuple_id(space1, type), tuple_id(space2, type));
3314 if (cmp != 0)
3315 return cmp;
3317 nested1 = nested(space1, type);
3318 nested2 = nested(space2, type);
3319 if (!nested1 != !nested2)
3320 return !nested1 - !nested2;
3322 if (nested1)
3323 return isl_space_cmp(nested1, nested2);
3325 return 0;
3328 /* Compare two isl_spaces.
3330 * The order is fairly arbitrary.
3332 int isl_space_cmp(__isl_keep isl_space *space1, __isl_keep isl_space *space2)
3334 int i;
3335 int cmp;
3337 if (space1 == space2)
3338 return 0;
3339 if (!space1)
3340 return -1;
3341 if (!space2)
3342 return 1;
3344 cmp = isl_space_cmp_type(space1, space2, isl_dim_param);
3345 if (cmp != 0)
3346 return cmp;
3347 cmp = isl_space_cmp_type(space1, space2, isl_dim_in);
3348 if (cmp != 0)
3349 return cmp;
3350 cmp = isl_space_cmp_type(space1, space2, isl_dim_out);
3351 if (cmp != 0)
3352 return cmp;
3354 if (!space1->ids && !space2->ids)
3355 return 0;
3357 for (i = 0; i < n(space1, isl_dim_param); ++i) {
3358 cmp = isl_id_cmp(get_id(space1, isl_dim_param, i),
3359 get_id(space2, isl_dim_param, i));
3360 if (cmp != 0)
3361 return cmp;
3364 return 0;