extract out shared isl_pw_*_un_op
[isl.git] / isl_space.c
blobfd67a89c65a6411b82cea1aae392d3210f02f555
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;
479 long dummy;
481 dummy = strtol(s, &p, 0);
482 if (p != s)
483 isl_die(ctx, isl_error_invalid, "name looks like a number",
484 return 0);
486 return 1;
489 /* Return a copy of the nested space at the given position.
491 static __isl_keep isl_space *isl_space_get_nested(__isl_keep isl_space *space,
492 int pos)
494 return isl_space_copy(isl_space_peek_nested(space, pos));
497 /* Return the nested space at the given position.
498 * This may be either a copy or the nested space itself
499 * if there is only one reference to "space".
500 * This allows the nested space to be modified inplace
501 * if both "space" and the nested space have only a single reference.
502 * The caller is not allowed to modify "space" between this call and
503 * a subsequent call to isl_space_restore_nested.
504 * The only exception is that isl_space_free can be called instead.
506 static __isl_give isl_space *isl_space_take_nested(__isl_keep isl_space *space,
507 int pos)
509 isl_space *nested;
511 if (!space)
512 return NULL;
513 if (space->ref != 1)
514 return isl_space_get_nested(space, pos);
515 nested = space->nested[pos];
516 space->nested[pos] = NULL;
517 return nested;
520 /* Replace the nested space at the given position by "nested",
521 * where this nested space of "space" may be missing
522 * due to a preceding call to isl_space_take_nested.
523 * However, in this case, "space" only has a single reference and
524 * then the call to isl_space_cow has no effect.
526 static __isl_give isl_space *isl_space_restore_nested(
527 __isl_take isl_space *space, int pos, __isl_take isl_space *nested)
529 if (!space || !nested)
530 goto error;
532 if (space->nested[pos] == nested) {
533 isl_space_free(nested);
534 return space;
537 space = isl_space_cow(space);
538 if (!space)
539 goto error;
540 isl_space_free(space->nested[pos]);
541 space->nested[pos] = nested;
543 return space;
544 error:
545 isl_space_free(space);
546 isl_space_free(nested);
547 return NULL;
550 /* Is it possible for the given dimension type to have a tuple id?
552 static int space_can_have_id(__isl_keep isl_space *space,
553 enum isl_dim_type type)
555 if (!space)
556 return 0;
557 if (isl_space_is_params(space))
558 isl_die(space->ctx, isl_error_invalid,
559 "parameter spaces don't have tuple ids", return 0);
560 if (isl_space_is_set(space) && type != isl_dim_set)
561 isl_die(space->ctx, isl_error_invalid,
562 "set spaces can only have a set id", return 0);
563 if (type != isl_dim_in && type != isl_dim_out)
564 isl_die(space->ctx, isl_error_invalid,
565 "only input, output and set tuples can have ids",
566 return 0);
568 return 1;
571 /* Does the tuple have an id?
573 isl_bool isl_space_has_tuple_id(__isl_keep isl_space *space,
574 enum isl_dim_type type)
576 if (!space_can_have_id(space, type))
577 return isl_bool_error;
578 return isl_bool_ok(space->tuple_id[type - isl_dim_in] != NULL);
581 /* Does the domain tuple of the map space "space" have an identifier?
583 isl_bool isl_space_has_domain_tuple_id(__isl_keep isl_space *space)
585 if (isl_space_check_is_map(space) < 0)
586 return isl_bool_error;
587 return isl_space_has_tuple_id(space, isl_dim_in);
590 /* Does the range tuple of the map space "space" have an identifier?
592 isl_bool isl_space_has_range_tuple_id(__isl_keep isl_space *space)
594 if (isl_space_check_is_map(space) < 0)
595 return isl_bool_error;
596 return isl_space_has_tuple_id(space, isl_dim_out);
599 __isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *space,
600 enum isl_dim_type type)
602 int has_id;
604 if (!space)
605 return NULL;
606 has_id = isl_space_has_tuple_id(space, type);
607 if (has_id < 0)
608 return NULL;
609 if (!has_id)
610 isl_die(space->ctx, isl_error_invalid,
611 "tuple has no id", return NULL);
612 return isl_id_copy(space->tuple_id[type - isl_dim_in]);
615 /* Return the identifier of the domain tuple of the map space "space",
616 * assuming it has one.
618 __isl_give isl_id *isl_space_get_domain_tuple_id(
619 __isl_keep isl_space *space)
621 if (isl_space_check_is_map(space) < 0)
622 return NULL;
623 return isl_space_get_tuple_id(space, isl_dim_in);
626 /* Return the identifier of the range tuple of the map space "space",
627 * assuming it has one.
629 __isl_give isl_id *isl_space_get_range_tuple_id(
630 __isl_keep isl_space *space)
632 if (isl_space_check_is_map(space) < 0)
633 return NULL;
634 return isl_space_get_tuple_id(space, isl_dim_out);
637 __isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *space,
638 enum isl_dim_type type, __isl_take isl_id *id)
640 space = isl_space_cow(space);
641 if (!space || !id)
642 goto error;
643 if (type != isl_dim_in && type != isl_dim_out)
644 isl_die(space->ctx, isl_error_invalid,
645 "only input, output and set tuples can have names",
646 goto error);
648 isl_id_free(space->tuple_id[type - isl_dim_in]);
649 space->tuple_id[type - isl_dim_in] = id;
651 return space;
652 error:
653 isl_id_free(id);
654 isl_space_free(space);
655 return NULL;
658 /* Replace the identifier of the domain tuple of the map space "space"
659 * by "id".
661 __isl_give isl_space *isl_space_set_domain_tuple_id(
662 __isl_take isl_space *space, __isl_take isl_id *id)
664 if (isl_space_check_is_map(space) < 0)
665 space = isl_space_free(space);
666 return isl_space_set_tuple_id(space, isl_dim_in, id);
669 /* Replace the identifier of the range tuple of the map space "space"
670 * by "id".
672 __isl_give isl_space *isl_space_set_range_tuple_id(
673 __isl_take isl_space *space, __isl_take isl_id *id)
675 if (isl_space_check_is_map(space) < 0)
676 space = isl_space_free(space);
677 return isl_space_set_tuple_id(space, isl_dim_out, id);
680 __isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *space,
681 enum isl_dim_type type)
683 space = isl_space_cow(space);
684 if (!space)
685 return NULL;
686 if (type != isl_dim_in && type != isl_dim_out)
687 isl_die(space->ctx, isl_error_invalid,
688 "only input, output and set tuples can have names",
689 goto error);
691 isl_id_free(space->tuple_id[type - isl_dim_in]);
692 space->tuple_id[type - isl_dim_in] = NULL;
694 return space;
695 error:
696 isl_space_free(space);
697 return NULL;
700 /* Set the id of the given dimension of "space" to "id".
701 * If the dimension already has an id, then it is replaced.
702 * If the dimension is a parameter, then we need to change it
703 * in the nested spaces (if any) as well.
705 __isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *space,
706 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
708 space = isl_space_cow(space);
709 if (!space || !id)
710 goto error;
712 if (type == isl_dim_param) {
713 int i;
715 for (i = 0; i < 2; ++i) {
716 if (!space->nested[i])
717 continue;
718 space->nested[i] =
719 isl_space_set_dim_id(space->nested[i],
720 type, pos, isl_id_copy(id));
721 if (!space->nested[i])
722 goto error;
726 isl_id_free(get_id(space, type, pos));
727 return set_id(space, type, pos, id);
728 error:
729 isl_id_free(id);
730 isl_space_free(space);
731 return NULL;
734 /* Reset the id of the given dimension of "space".
735 * If the dimension already has an id, then it is removed.
736 * If the dimension is a parameter, then we need to reset it
737 * in the nested spaces (if any) as well.
739 __isl_give isl_space *isl_space_reset_dim_id(__isl_take isl_space *space,
740 enum isl_dim_type type, unsigned pos)
742 space = isl_space_cow(space);
743 if (!space)
744 goto error;
746 if (type == isl_dim_param) {
747 int i;
749 for (i = 0; i < 2; ++i) {
750 if (!space->nested[i])
751 continue;
752 space->nested[i] =
753 isl_space_reset_dim_id(space->nested[i],
754 type, pos);
755 if (!space->nested[i])
756 goto error;
760 isl_id_free(get_id(space, type, pos));
761 return set_id(space, type, pos, NULL);
762 error:
763 isl_space_free(space);
764 return NULL;
767 isl_bool isl_space_has_dim_id(__isl_keep isl_space *space,
768 enum isl_dim_type type, unsigned pos)
770 if (!space)
771 return isl_bool_error;
772 return isl_bool_ok(get_id(space, type, pos) != NULL);
775 __isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *space,
776 enum isl_dim_type type, unsigned pos)
778 if (!space)
779 return NULL;
780 if (!get_id(space, type, pos))
781 isl_die(space->ctx, isl_error_invalid,
782 "dim has no id", return NULL);
783 return isl_id_copy(get_id(space, type, pos));
786 __isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *space,
787 enum isl_dim_type type, const char *s)
789 isl_id *id;
791 if (!space)
792 return NULL;
794 if (!s)
795 return isl_space_reset_tuple_id(space, type);
797 if (!name_ok(space->ctx, s))
798 goto error;
800 id = isl_id_alloc(space->ctx, s, NULL);
801 return isl_space_set_tuple_id(space, type, id);
802 error:
803 isl_space_free(space);
804 return NULL;
807 /* Does the tuple have a name?
809 isl_bool isl_space_has_tuple_name(__isl_keep isl_space *space,
810 enum isl_dim_type type)
812 isl_id *id;
814 if (!space_can_have_id(space, type))
815 return isl_bool_error;
816 id = space->tuple_id[type - isl_dim_in];
817 return isl_bool_ok(id && id->name);
820 __isl_keep const char *isl_space_get_tuple_name(__isl_keep isl_space *space,
821 enum isl_dim_type type)
823 isl_id *id;
824 if (!space)
825 return NULL;
826 if (type != isl_dim_in && type != isl_dim_out)
827 return NULL;
828 id = space->tuple_id[type - isl_dim_in];
829 return id ? id->name : NULL;
832 __isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *space,
833 enum isl_dim_type type, unsigned pos,
834 const char *s)
836 isl_id *id;
838 if (!space)
839 return NULL;
840 if (!s)
841 return isl_space_reset_dim_id(space, type, pos);
842 if (!name_ok(space->ctx, s))
843 goto error;
844 id = isl_id_alloc(space->ctx, s, NULL);
845 return isl_space_set_dim_id(space, type, pos, id);
846 error:
847 isl_space_free(space);
848 return NULL;
851 /* Does the given dimension have a name?
853 isl_bool isl_space_has_dim_name(__isl_keep isl_space *space,
854 enum isl_dim_type type, unsigned pos)
856 isl_id *id;
858 if (!space)
859 return isl_bool_error;
860 id = get_id(space, type, pos);
861 return isl_bool_ok(id && id->name);
864 __isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *space,
865 enum isl_dim_type type, unsigned pos)
867 isl_id *id = get_id(space, type, pos);
868 return id ? id->name : NULL;
871 int isl_space_find_dim_by_id(__isl_keep isl_space *space,
872 enum isl_dim_type type, __isl_keep isl_id *id)
874 int i;
875 int offset;
876 isl_size n;
878 n = isl_space_dim(space, type);
879 if (n < 0 || !id)
880 return -1;
882 offset = isl_space_offset(space, type);
883 for (i = 0; i < n && offset + i < space->n_id; ++i)
884 if (space->ids[offset + i] == id)
885 return i;
887 return -1;
890 int isl_space_find_dim_by_name(__isl_keep isl_space *space,
891 enum isl_dim_type type, const char *name)
893 int i;
894 int offset;
895 isl_size n;
897 n = isl_space_dim(space, type);
898 if (n < 0 || !name)
899 return -1;
901 offset = isl_space_offset(space, type);
902 for (i = 0; i < n && offset + i < space->n_id; ++i) {
903 isl_id *id = get_id(space, type, i);
904 if (id && id->name && !strcmp(id->name, name))
905 return i;
908 return -1;
911 /* Reset the user pointer on all identifiers of parameters and tuples
912 * of "space".
914 __isl_give isl_space *isl_space_reset_user(__isl_take isl_space *space)
916 int i;
917 isl_ctx *ctx;
918 isl_id *id;
919 const char *name;
921 if (!space)
922 return NULL;
924 ctx = isl_space_get_ctx(space);
926 for (i = 0; i < space->nparam && i < space->n_id; ++i) {
927 if (!isl_id_get_user(space->ids[i]))
928 continue;
929 space = isl_space_cow(space);
930 if (!space)
931 return NULL;
932 name = isl_id_get_name(space->ids[i]);
933 id = isl_id_alloc(ctx, name, NULL);
934 isl_id_free(space->ids[i]);
935 space->ids[i] = id;
936 if (!id)
937 return isl_space_free(space);
940 for (i = 0; i < 2; ++i) {
941 if (!space->tuple_id[i])
942 continue;
943 if (!isl_id_get_user(space->tuple_id[i]))
944 continue;
945 space = isl_space_cow(space);
946 if (!space)
947 return NULL;
948 name = isl_id_get_name(space->tuple_id[i]);
949 id = isl_id_alloc(ctx, name, NULL);
950 isl_id_free(space->tuple_id[i]);
951 space->tuple_id[i] = id;
952 if (!id)
953 return isl_space_free(space);
956 for (i = 0; i < 2; ++i) {
957 isl_space *nested;
959 if (!space->nested[i])
960 continue;
961 nested = isl_space_take_nested(space, i);
962 nested = isl_space_reset_user(nested);
963 space = isl_space_restore_nested(space, i, nested);
964 if (!space)
965 return NULL;
968 return space;
971 static __isl_keep isl_id *tuple_id(__isl_keep isl_space *space,
972 enum isl_dim_type type)
974 if (!space)
975 return NULL;
976 if (type == isl_dim_in)
977 return space->tuple_id[0];
978 if (type == isl_dim_out)
979 return space->tuple_id[1];
980 return NULL;
983 static __isl_keep isl_space *nested(__isl_keep isl_space *space,
984 enum isl_dim_type type)
986 if (!space)
987 return NULL;
988 if (type == isl_dim_in)
989 return space->nested[0];
990 if (type == isl_dim_out)
991 return space->nested[1];
992 return NULL;
995 /* Are the two spaces the same, apart from positions and names of parameters?
997 isl_bool isl_space_has_equal_tuples(__isl_keep isl_space *space1,
998 __isl_keep isl_space *space2)
1000 if (!space1 || !space2)
1001 return isl_bool_error;
1002 if (space1 == space2)
1003 return isl_bool_true;
1004 return isl_space_tuple_is_equal(space1, isl_dim_in,
1005 space2, isl_dim_in) &&
1006 isl_space_tuple_is_equal(space1, isl_dim_out,
1007 space2, isl_dim_out);
1010 /* Check that a match involving "space" was successful.
1011 * That is, check that "match" is equal to isl_bool_true.
1013 static isl_stat check_match(__isl_keep isl_space *space, isl_bool match)
1015 if (match < 0)
1016 return isl_stat_error;
1017 if (!match)
1018 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1019 "incompatible spaces", return isl_stat_error);
1021 return isl_stat_ok;
1024 /* Check that the two spaces are the same,
1025 * apart from positions and names of parameters.
1027 isl_stat isl_space_check_equal_tuples(__isl_keep isl_space *space1,
1028 __isl_keep isl_space *space2)
1030 isl_bool is_equal;
1032 is_equal = isl_space_has_equal_tuples(space1, space2);
1033 return check_match(space1, is_equal);
1036 /* Check if the tuple of type "type1" of "space1" is the same as
1037 * the tuple of type "type2" of "space2".
1039 * That is, check if the tuples have the same identifier, the same dimension
1040 * and the same internal structure.
1041 * The identifiers of the dimensions inside the tuples do not affect the result.
1043 * Note that this function only checks the tuples themselves.
1044 * If nested tuples are involved, then we need to be careful not
1045 * to have result affected by possibly differing parameters
1046 * in those nested tuples.
1048 isl_bool isl_space_tuple_is_equal(__isl_keep isl_space *space1,
1049 enum isl_dim_type type1, __isl_keep isl_space *space2,
1050 enum isl_dim_type type2)
1052 isl_id *id1, *id2;
1053 isl_space *nested1, *nested2;
1055 if (!space1 || !space2)
1056 return isl_bool_error;
1058 if (space1 == space2 && type1 == type2)
1059 return isl_bool_true;
1061 if (n(space1, type1) != n(space2, type2))
1062 return isl_bool_false;
1063 id1 = tuple_id(space1, type1);
1064 id2 = tuple_id(space2, type2);
1065 if (!id1 ^ !id2)
1066 return isl_bool_false;
1067 if (id1 && id1 != id2)
1068 return isl_bool_false;
1069 nested1 = nested(space1, type1);
1070 nested2 = nested(space2, type2);
1071 if (!nested1 ^ !nested2)
1072 return isl_bool_false;
1073 if (nested1 && !isl_space_has_equal_tuples(nested1, nested2))
1074 return isl_bool_false;
1075 return isl_bool_true;
1078 /* Is the tuple "inner" within the wrapped relation inside tuple "outer"
1079 * of "space1" equal to tuple "type2" of "space2"?
1081 isl_bool isl_space_wrapped_tuple_is_equal(__isl_keep isl_space *space1,
1082 enum isl_dim_type outer, enum isl_dim_type inner,
1083 __isl_keep isl_space *space2, enum isl_dim_type type2)
1085 int pos;
1086 isl_space *nested;
1088 if (!space1)
1089 return isl_bool_error;
1090 if (outer != isl_dim_in && outer != isl_dim_out)
1091 isl_die(isl_space_get_ctx(space1), isl_error_invalid,
1092 "only input, output and set tuples "
1093 "can have nested relations", return isl_bool_error);
1094 pos = outer - isl_dim_in;
1095 nested = isl_space_peek_nested(space1, pos);
1096 return isl_space_tuple_is_equal(nested, inner, space2, type2);
1099 /* Check that the tuple "inner" within the wrapped relation inside tuple "outer"
1100 * of "space1" is equal to tuple "type2" of "space2".
1102 isl_stat isl_space_check_wrapped_tuple_is_equal(__isl_keep isl_space *space1,
1103 enum isl_dim_type outer, enum isl_dim_type inner,
1104 __isl_keep isl_space *space2, enum isl_dim_type type2)
1106 isl_bool is_equal;
1108 is_equal = isl_space_wrapped_tuple_is_equal(space1, outer, inner,
1109 space2, type2);
1110 return check_match(space1, is_equal);
1113 static isl_bool match(__isl_keep isl_space *space1, enum isl_dim_type type1,
1114 __isl_keep isl_space *space2, enum isl_dim_type type2)
1116 int i;
1117 isl_bool equal;
1119 if (!space1 || !space2)
1120 return isl_bool_error;
1122 if (space1 == space2 && type1 == type2)
1123 return isl_bool_true;
1125 equal = isl_space_tuple_is_equal(space1, type1, space2, type2);
1126 if (equal < 0 || !equal)
1127 return equal;
1129 if (!space1->ids && !space2->ids)
1130 return isl_bool_true;
1132 for (i = 0; i < n(space1, type1); ++i) {
1133 if (get_id(space1, type1, i) != get_id(space2, type2, i))
1134 return isl_bool_false;
1136 return isl_bool_true;
1139 /* Do "space1" and "space2" have the same parameters?
1141 isl_bool isl_space_has_equal_params(__isl_keep isl_space *space1,
1142 __isl_keep isl_space *space2)
1144 return match(space1, isl_dim_param, space2, isl_dim_param);
1147 /* Do "space1" and "space2" have the same identifiers for all
1148 * the tuple variables?
1150 isl_bool isl_space_has_equal_ids(__isl_keep isl_space *space1,
1151 __isl_keep isl_space *space2)
1153 isl_bool equal;
1155 equal = match(space1, isl_dim_in, space2, isl_dim_in);
1156 if (equal < 0 || !equal)
1157 return equal;
1158 return match(space1, isl_dim_out, space2, isl_dim_out);
1161 isl_bool isl_space_match(__isl_keep isl_space *space1, enum isl_dim_type type1,
1162 __isl_keep isl_space *space2, enum isl_dim_type type2)
1164 return match(space1, type1, space2, type2);
1167 static void get_ids(__isl_keep isl_space *space, enum isl_dim_type type,
1168 unsigned first, unsigned n, __isl_keep isl_id **ids)
1170 int i;
1172 for (i = 0; i < n ; ++i)
1173 ids[i] = get_id(space, type, first + i);
1176 static __isl_give isl_space *space_extend(__isl_take isl_space *space,
1177 unsigned nparam, unsigned n_in, unsigned n_out)
1179 isl_id **ids = NULL;
1181 if (!space)
1182 return NULL;
1183 if (space->nparam == nparam &&
1184 space->n_in == n_in && space->n_out == n_out)
1185 return space;
1187 isl_assert(space->ctx, space->nparam <= nparam, goto error);
1188 isl_assert(space->ctx, space->n_in <= n_in, goto error);
1189 isl_assert(space->ctx, space->n_out <= n_out, goto error);
1191 space = isl_space_cow(space);
1192 if (!space)
1193 goto error;
1195 if (space->ids) {
1196 unsigned n;
1197 n = nparam + n_in + n_out;
1198 if (n < nparam || n < n_in || n < n_out)
1199 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1200 "overflow in total number of dimensions",
1201 goto error);
1202 ids = isl_calloc_array(space->ctx, isl_id *, n);
1203 if (!ids)
1204 goto error;
1205 get_ids(space, isl_dim_param, 0, space->nparam, ids);
1206 get_ids(space, isl_dim_in, 0, space->n_in, ids + nparam);
1207 get_ids(space, isl_dim_out, 0, space->n_out,
1208 ids + nparam + n_in);
1209 free(space->ids);
1210 space->ids = ids;
1211 space->n_id = nparam + n_in + n_out;
1213 space->nparam = nparam;
1214 space->n_in = n_in;
1215 space->n_out = n_out;
1217 return space;
1218 error:
1219 free(ids);
1220 isl_space_free(space);
1221 return NULL;
1224 __isl_give isl_space *isl_space_extend(__isl_take isl_space *space,
1225 unsigned nparam, unsigned n_in, unsigned n_out)
1227 return space_extend(space, nparam, n_in, n_out);
1230 __isl_give isl_space *isl_space_add_dims(__isl_take isl_space *space,
1231 enum isl_dim_type type, unsigned n)
1233 space = isl_space_reset(space, type);
1234 if (!space)
1235 return NULL;
1236 switch (type) {
1237 case isl_dim_param:
1238 space = space_extend(space,
1239 space->nparam + n, space->n_in, space->n_out);
1240 if (space && space->nested[0] &&
1241 !(space->nested[0] = isl_space_add_dims(space->nested[0],
1242 isl_dim_param, n)))
1243 goto error;
1244 if (space && space->nested[1] &&
1245 !(space->nested[1] = isl_space_add_dims(space->nested[1],
1246 isl_dim_param, n)))
1247 goto error;
1248 return space;
1249 case isl_dim_in:
1250 return space_extend(space,
1251 space->nparam, space->n_in + n, space->n_out);
1252 case isl_dim_out:
1253 return space_extend(space,
1254 space->nparam, space->n_in, space->n_out + n);
1255 default:
1256 isl_die(space->ctx, isl_error_invalid,
1257 "cannot add dimensions of specified type", goto error);
1259 error:
1260 isl_space_free(space);
1261 return NULL;
1264 /* Add a parameter with identifier "id" to "space", provided
1265 * it does not already appear in "space".
1267 __isl_give isl_space *isl_space_add_param_id(__isl_take isl_space *space,
1268 __isl_take isl_id *id)
1270 isl_size pos;
1272 if (!space || !id)
1273 goto error;
1275 if (isl_space_find_dim_by_id(space, isl_dim_param, id) >= 0) {
1276 isl_id_free(id);
1277 return space;
1280 pos = isl_space_dim(space, isl_dim_param);
1281 if (pos < 0)
1282 goto error;
1283 space = isl_space_add_dims(space, isl_dim_param, 1);
1284 space = isl_space_set_dim_id(space, isl_dim_param, pos, id);
1286 return space;
1287 error:
1288 isl_space_free(space);
1289 isl_id_free(id);
1290 return NULL;
1293 static int valid_dim_type(enum isl_dim_type type)
1295 switch (type) {
1296 case isl_dim_param:
1297 case isl_dim_in:
1298 case isl_dim_out:
1299 return 1;
1300 default:
1301 return 0;
1305 #undef TYPE
1306 #define TYPE isl_space
1307 #include "check_type_range_templ.c"
1309 /* Insert "n" dimensions of type "type" at position "pos".
1310 * If we are inserting parameters, then they are also inserted in
1311 * any nested spaces.
1313 __isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *space,
1314 enum isl_dim_type type, unsigned pos, unsigned n)
1316 isl_ctx *ctx;
1317 isl_id **ids = NULL;
1319 if (!space)
1320 return NULL;
1321 if (n == 0)
1322 return isl_space_reset(space, type);
1324 ctx = isl_space_get_ctx(space);
1325 if (!valid_dim_type(type))
1326 isl_die(ctx, isl_error_invalid,
1327 "cannot insert dimensions of specified type",
1328 goto error);
1330 if (isl_space_check_range(space, type, pos, 0) < 0)
1331 return isl_space_free(space);
1333 space = isl_space_cow(space);
1334 if (!space)
1335 return NULL;
1337 if (space->ids) {
1338 enum isl_dim_type t, o = isl_dim_param;
1339 int off;
1340 int s[3];
1341 ids = isl_calloc_array(ctx, isl_id *,
1342 space->nparam + space->n_in + space->n_out + n);
1343 if (!ids)
1344 goto error;
1345 off = 0;
1346 s[isl_dim_param - o] = space->nparam;
1347 s[isl_dim_in - o] = space->n_in;
1348 s[isl_dim_out - o] = space->n_out;
1349 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
1350 if (t != type) {
1351 get_ids(space, t, 0, s[t - o], ids + off);
1352 off += s[t - o];
1353 } else {
1354 get_ids(space, t, 0, pos, ids + off);
1355 off += pos + n;
1356 get_ids(space, t, pos, s[t - o] - pos,
1357 ids + off);
1358 off += s[t - o] - pos;
1361 free(space->ids);
1362 space->ids = ids;
1363 space->n_id = space->nparam + space->n_in + space->n_out + n;
1365 switch (type) {
1366 case isl_dim_param: space->nparam += n; break;
1367 case isl_dim_in: space->n_in += n; break;
1368 case isl_dim_out: space->n_out += n; break;
1369 default: ;
1371 space = isl_space_reset(space, type);
1373 if (type == isl_dim_param) {
1374 if (space && space->nested[0] &&
1375 !(space->nested[0] = isl_space_insert_dims(space->nested[0],
1376 isl_dim_param, pos, n)))
1377 goto error;
1378 if (space && space->nested[1] &&
1379 !(space->nested[1] = isl_space_insert_dims(space->nested[1],
1380 isl_dim_param, pos, n)))
1381 goto error;
1384 return space;
1385 error:
1386 isl_space_free(space);
1387 return NULL;
1390 __isl_give isl_space *isl_space_move_dims(__isl_take isl_space *space,
1391 enum isl_dim_type dst_type, unsigned dst_pos,
1392 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1394 int i;
1396 space = isl_space_reset(space, src_type);
1397 space = isl_space_reset(space, dst_type);
1398 if (!space)
1399 return NULL;
1400 if (n == 0)
1401 return space;
1403 if (isl_space_check_range(space, src_type, src_pos, n) < 0)
1404 return isl_space_free(space);
1406 if (dst_type == src_type && dst_pos == src_pos)
1407 return space;
1409 isl_assert(space->ctx, dst_type != src_type, goto error);
1411 space = isl_space_cow(space);
1412 if (!space)
1413 return NULL;
1415 if (space->ids) {
1416 isl_id **ids;
1417 enum isl_dim_type t, o = isl_dim_param;
1418 int off;
1419 int s[3];
1420 ids = isl_calloc_array(space->ctx, isl_id *,
1421 space->nparam + space->n_in + space->n_out);
1422 if (!ids)
1423 goto error;
1424 off = 0;
1425 s[isl_dim_param - o] = space->nparam;
1426 s[isl_dim_in - o] = space->n_in;
1427 s[isl_dim_out - o] = space->n_out;
1428 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
1429 if (t == dst_type) {
1430 get_ids(space, t, 0, dst_pos, ids + off);
1431 off += dst_pos;
1432 get_ids(space, src_type, src_pos, n, ids + off);
1433 off += n;
1434 get_ids(space, t, dst_pos, s[t - o] - dst_pos,
1435 ids + off);
1436 off += s[t - o] - dst_pos;
1437 } else if (t == src_type) {
1438 get_ids(space, t, 0, src_pos, ids + off);
1439 off += src_pos;
1440 get_ids(space, t, src_pos + n,
1441 s[t - o] - src_pos - n, ids + off);
1442 off += s[t - o] - src_pos - n;
1443 } else {
1444 get_ids(space, t, 0, s[t - o], ids + off);
1445 off += s[t - o];
1448 free(space->ids);
1449 space->ids = ids;
1450 space->n_id = space->nparam + space->n_in + space->n_out;
1453 switch (dst_type) {
1454 case isl_dim_param: space->nparam += n; break;
1455 case isl_dim_in: space->n_in += n; break;
1456 case isl_dim_out: space->n_out += n; break;
1457 default: ;
1460 switch (src_type) {
1461 case isl_dim_param: space->nparam -= n; break;
1462 case isl_dim_in: space->n_in -= n; break;
1463 case isl_dim_out: space->n_out -= n; break;
1464 default: ;
1467 if (dst_type != isl_dim_param && src_type != isl_dim_param)
1468 return space;
1470 for (i = 0; i < 2; ++i) {
1471 isl_space *nested;
1473 if (!space->nested[i])
1474 continue;
1475 nested = isl_space_take_nested(space, i);
1476 nested = isl_space_replace_params(nested, space);
1477 space = isl_space_restore_nested(space, i, nested);
1478 if (!space)
1479 return NULL;
1482 return space;
1483 error:
1484 isl_space_free(space);
1485 return NULL;
1488 /* Check that "space1" and "space2" have the same parameters,
1489 * reporting an error if they do not.
1491 isl_stat isl_space_check_equal_params(__isl_keep isl_space *space1,
1492 __isl_keep isl_space *space2)
1494 isl_bool equal;
1496 equal = isl_space_has_equal_params(space1, space2);
1497 if (equal < 0)
1498 return isl_stat_error;
1499 if (!equal)
1500 isl_die(isl_space_get_ctx(space1), isl_error_invalid,
1501 "parameters need to match", return isl_stat_error);
1502 return isl_stat_ok;
1505 __isl_give isl_space *isl_space_join(__isl_take isl_space *left,
1506 __isl_take isl_space *right)
1508 isl_space *space;
1510 if (isl_space_check_equal_params(left, right) < 0)
1511 goto error;
1513 isl_assert(left->ctx,
1514 isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_in),
1515 goto error);
1517 space = isl_space_alloc(left->ctx,
1518 left->nparam, left->n_in, right->n_out);
1519 if (!space)
1520 goto error;
1522 space = copy_ids(space, isl_dim_param, 0, left, isl_dim_param);
1523 space = copy_ids(space, isl_dim_in, 0, left, isl_dim_in);
1524 space = copy_ids(space, isl_dim_out, 0, right, isl_dim_out);
1526 if (space && left->tuple_id[0] &&
1527 !(space->tuple_id[0] = isl_id_copy(left->tuple_id[0])))
1528 goto error;
1529 if (space && right->tuple_id[1] &&
1530 !(space->tuple_id[1] = isl_id_copy(right->tuple_id[1])))
1531 goto error;
1532 if (space && left->nested[0] &&
1533 !(space->nested[0] = isl_space_copy(left->nested[0])))
1534 goto error;
1535 if (space && right->nested[1] &&
1536 !(space->nested[1] = isl_space_copy(right->nested[1])))
1537 goto error;
1539 isl_space_free(left);
1540 isl_space_free(right);
1542 return space;
1543 error:
1544 isl_space_free(left);
1545 isl_space_free(right);
1546 return NULL;
1549 /* Given two map spaces { A -> C } and { B -> D }, construct the space
1550 * { [A -> B] -> [C -> D] }.
1551 * Given two set spaces { A } and { B }, construct the space { [A -> B] }.
1553 __isl_give isl_space *isl_space_product(__isl_take isl_space *left,
1554 __isl_take isl_space *right)
1556 isl_space *dom1, *dom2, *nest1, *nest2;
1557 int is_set;
1559 if (!left || !right)
1560 goto error;
1562 is_set = isl_space_is_set(left);
1563 if (is_set != isl_space_is_set(right))
1564 isl_die(isl_space_get_ctx(left), isl_error_invalid,
1565 "expecting either two set spaces or two map spaces",
1566 goto error);
1567 if (is_set)
1568 return isl_space_range_product(left, right);
1570 if (isl_space_check_equal_params(left, right) < 0)
1571 goto error;
1573 dom1 = isl_space_domain(isl_space_copy(left));
1574 dom2 = isl_space_domain(isl_space_copy(right));
1575 nest1 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1577 dom1 = isl_space_range(left);
1578 dom2 = isl_space_range(right);
1579 nest2 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1581 return isl_space_join(isl_space_reverse(nest1), nest2);
1582 error:
1583 isl_space_free(left);
1584 isl_space_free(right);
1585 return NULL;
1588 /* Given two spaces { A -> C } and { B -> C }, construct the space
1589 * { [A -> B] -> C }
1591 __isl_give isl_space *isl_space_domain_product(__isl_take isl_space *left,
1592 __isl_take isl_space *right)
1594 isl_space *ran, *dom1, *dom2, *nest;
1596 if (isl_space_check_equal_params(left, right) < 0)
1597 goto error;
1599 if (!isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_out))
1600 isl_die(left->ctx, isl_error_invalid,
1601 "ranges need to match", goto error);
1603 ran = isl_space_range(isl_space_copy(left));
1605 dom1 = isl_space_domain(left);
1606 dom2 = isl_space_domain(right);
1607 nest = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1609 return isl_space_join(isl_space_reverse(nest), ran);
1610 error:
1611 isl_space_free(left);
1612 isl_space_free(right);
1613 return NULL;
1616 __isl_give isl_space *isl_space_range_product(__isl_take isl_space *left,
1617 __isl_take isl_space *right)
1619 isl_space *dom, *ran1, *ran2, *nest;
1621 if (isl_space_check_equal_params(left, right) < 0)
1622 goto error;
1624 if (!isl_space_tuple_is_equal(left, isl_dim_in, right, isl_dim_in))
1625 isl_die(left->ctx, isl_error_invalid,
1626 "domains need to match", goto error);
1628 dom = isl_space_domain(isl_space_copy(left));
1630 ran1 = isl_space_range(left);
1631 ran2 = isl_space_range(right);
1632 nest = isl_space_wrap(isl_space_join(isl_space_reverse(ran1), ran2));
1634 return isl_space_join(isl_space_reverse(dom), nest);
1635 error:
1636 isl_space_free(left);
1637 isl_space_free(right);
1638 return NULL;
1641 /* Given a space of the form [A -> B] -> C, return the space A -> C.
1643 __isl_give isl_space *isl_space_domain_factor_domain(
1644 __isl_take isl_space *space)
1646 isl_space *nested;
1647 isl_space *domain;
1649 if (isl_space_check_domain_is_wrapping(space) < 0)
1650 return isl_space_free(space);
1652 nested = space->nested[0];
1653 domain = isl_space_copy(space);
1654 domain = isl_space_drop_dims(domain, isl_dim_in,
1655 nested->n_in, nested->n_out);
1656 if (!domain)
1657 return isl_space_free(space);
1658 if (nested->tuple_id[0]) {
1659 domain->tuple_id[0] = isl_id_copy(nested->tuple_id[0]);
1660 if (!domain->tuple_id[0])
1661 goto error;
1663 if (nested->nested[0]) {
1664 domain->nested[0] = isl_space_copy(nested->nested[0]);
1665 if (!domain->nested[0])
1666 goto error;
1669 isl_space_free(space);
1670 return domain;
1671 error:
1672 isl_space_free(space);
1673 isl_space_free(domain);
1674 return NULL;
1677 /* Given a space of the form [A -> B] -> C, return the space B -> C.
1679 __isl_give isl_space *isl_space_domain_factor_range(
1680 __isl_take isl_space *space)
1682 isl_space *nested;
1683 isl_space *range;
1685 if (isl_space_check_domain_is_wrapping(space) < 0)
1686 return isl_space_free(space);
1688 nested = space->nested[0];
1689 range = isl_space_copy(space);
1690 range = isl_space_drop_dims(range, isl_dim_in, 0, nested->n_in);
1691 if (!range)
1692 return isl_space_free(space);
1693 if (nested->tuple_id[1]) {
1694 range->tuple_id[0] = isl_id_copy(nested->tuple_id[1]);
1695 if (!range->tuple_id[0])
1696 goto error;
1698 if (nested->nested[1]) {
1699 range->nested[0] = isl_space_copy(nested->nested[1]);
1700 if (!range->nested[0])
1701 goto error;
1704 isl_space_free(space);
1705 return range;
1706 error:
1707 isl_space_free(space);
1708 isl_space_free(range);
1709 return NULL;
1712 /* Internal function that selects the domain of the map that is
1713 * embedded in either a set space or the range of a map space.
1714 * In particular, given a space of the form [A -> B], return the space A.
1715 * Given a space of the form A -> [B -> C], return the space A -> B.
1717 static __isl_give isl_space *range_factor_domain(__isl_take isl_space *space)
1719 isl_space *nested;
1720 isl_space *domain;
1722 if (!space)
1723 return NULL;
1725 nested = space->nested[1];
1726 domain = isl_space_copy(space);
1727 domain = isl_space_drop_dims(domain, isl_dim_out,
1728 nested->n_in, nested->n_out);
1729 if (!domain)
1730 return isl_space_free(space);
1731 if (nested->tuple_id[0]) {
1732 domain->tuple_id[1] = isl_id_copy(nested->tuple_id[0]);
1733 if (!domain->tuple_id[1])
1734 goto error;
1736 if (nested->nested[0]) {
1737 domain->nested[1] = isl_space_copy(nested->nested[0]);
1738 if (!domain->nested[1])
1739 goto error;
1742 isl_space_free(space);
1743 return domain;
1744 error:
1745 isl_space_free(space);
1746 isl_space_free(domain);
1747 return NULL;
1750 /* Given a space of the form A -> [B -> C], return the space A -> B.
1752 __isl_give isl_space *isl_space_range_factor_domain(
1753 __isl_take isl_space *space)
1755 if (isl_space_check_range_is_wrapping(space) < 0)
1756 return isl_space_free(space);
1758 return range_factor_domain(space);
1761 /* Given a space of the form [A -> B], return the space A.
1763 static __isl_give isl_space *set_factor_domain(__isl_take isl_space *space)
1765 if (!space)
1766 return NULL;
1767 if (!isl_space_is_wrapping(space))
1768 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1769 "not a product", return isl_space_free(space));
1771 return range_factor_domain(space);
1774 /* Given a space of the form [A -> B] -> [C -> D], return the space A -> C.
1775 * Given a space of the form [A -> B], return the space A.
1777 __isl_give isl_space *isl_space_factor_domain(__isl_take isl_space *space)
1779 if (!space)
1780 return NULL;
1781 if (isl_space_is_set(space))
1782 return set_factor_domain(space);
1783 space = isl_space_domain_factor_domain(space);
1784 space = isl_space_range_factor_domain(space);
1785 return space;
1788 /* Internal function that selects the range of the map that is
1789 * embedded in either a set space or the range of a map space.
1790 * In particular, given a space of the form [A -> B], return the space B.
1791 * Given a space of the form A -> [B -> C], return the space A -> C.
1793 static __isl_give isl_space *range_factor_range(__isl_take isl_space *space)
1795 isl_space *nested;
1796 isl_space *range;
1798 if (!space)
1799 return NULL;
1801 nested = space->nested[1];
1802 range = isl_space_copy(space);
1803 range = isl_space_drop_dims(range, isl_dim_out, 0, nested->n_in);
1804 if (!range)
1805 return isl_space_free(space);
1806 if (nested->tuple_id[1]) {
1807 range->tuple_id[1] = isl_id_copy(nested->tuple_id[1]);
1808 if (!range->tuple_id[1])
1809 goto error;
1811 if (nested->nested[1]) {
1812 range->nested[1] = isl_space_copy(nested->nested[1]);
1813 if (!range->nested[1])
1814 goto error;
1817 isl_space_free(space);
1818 return range;
1819 error:
1820 isl_space_free(space);
1821 isl_space_free(range);
1822 return NULL;
1825 /* Given a space of the form A -> [B -> C], return the space A -> C.
1827 __isl_give isl_space *isl_space_range_factor_range(
1828 __isl_take isl_space *space)
1830 if (isl_space_check_range_is_wrapping(space) < 0)
1831 return isl_space_free(space);
1833 return range_factor_range(space);
1836 /* Given a space of the form [A -> B], return the space B.
1838 static __isl_give isl_space *set_factor_range(__isl_take isl_space *space)
1840 if (!space)
1841 return NULL;
1842 if (!isl_space_is_wrapping(space))
1843 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1844 "not a product", return isl_space_free(space));
1846 return range_factor_range(space);
1849 /* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
1850 * Given a space of the form [A -> B], return the space B.
1852 __isl_give isl_space *isl_space_factor_range(__isl_take isl_space *space)
1854 if (!space)
1855 return NULL;
1856 if (isl_space_is_set(space))
1857 return set_factor_range(space);
1858 space = isl_space_domain_factor_range(space);
1859 space = isl_space_range_factor_range(space);
1860 return space;
1863 __isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *space)
1865 isl_ctx *ctx;
1866 isl_id **ids = NULL;
1867 int n_id;
1869 if (!space)
1870 return NULL;
1871 ctx = isl_space_get_ctx(space);
1872 if (!isl_space_is_set(space))
1873 isl_die(ctx, isl_error_invalid, "not a set space", goto error);
1874 space = isl_space_cow(space);
1875 if (!space)
1876 return NULL;
1877 n_id = space->nparam + space->n_out + space->n_out;
1878 if (n_id > 0 && space->ids) {
1879 ids = isl_calloc_array(space->ctx, isl_id *, n_id);
1880 if (!ids)
1881 goto error;
1882 get_ids(space, isl_dim_param, 0, space->nparam, ids);
1883 get_ids(space, isl_dim_out, 0, space->n_out,
1884 ids + space->nparam);
1886 space->n_in = space->n_out;
1887 if (ids) {
1888 free(space->ids);
1889 space->ids = ids;
1890 space->n_id = n_id;
1891 space = copy_ids(space, isl_dim_out, 0, space, isl_dim_in);
1893 isl_id_free(space->tuple_id[0]);
1894 space->tuple_id[0] = isl_id_copy(space->tuple_id[1]);
1895 isl_space_free(space->nested[0]);
1896 space->nested[0] = isl_space_copy(space->nested[1]);
1897 return space;
1898 error:
1899 isl_space_free(space);
1900 return NULL;
1903 __isl_give isl_space *isl_space_map_from_domain_and_range(
1904 __isl_take isl_space *domain, __isl_take isl_space *range)
1906 if (!domain || !range)
1907 goto error;
1908 if (!isl_space_is_set(domain))
1909 isl_die(isl_space_get_ctx(domain), isl_error_invalid,
1910 "domain is not a set space", goto error);
1911 if (!isl_space_is_set(range))
1912 isl_die(isl_space_get_ctx(range), isl_error_invalid,
1913 "range is not a set space", goto error);
1914 return isl_space_join(isl_space_reverse(domain), range);
1915 error:
1916 isl_space_free(domain);
1917 isl_space_free(range);
1918 return NULL;
1921 static __isl_give isl_space *set_ids(__isl_take isl_space *space,
1922 enum isl_dim_type type,
1923 unsigned first, unsigned n, __isl_take isl_id **ids)
1925 int i;
1927 for (i = 0; i < n ; ++i)
1928 space = set_id(space, type, first + i, ids[i]);
1930 return space;
1933 __isl_give isl_space *isl_space_reverse(__isl_take isl_space *space)
1935 unsigned t;
1936 isl_bool equal;
1937 isl_space *nested;
1938 isl_id **ids = NULL;
1939 isl_id *id;
1941 equal = match(space, isl_dim_in, space, isl_dim_out);
1942 if (equal < 0)
1943 return isl_space_free(space);
1944 if (equal)
1945 return space;
1947 space = isl_space_cow(space);
1948 if (!space)
1949 return NULL;
1951 id = space->tuple_id[0];
1952 space->tuple_id[0] = space->tuple_id[1];
1953 space->tuple_id[1] = id;
1955 nested = space->nested[0];
1956 space->nested[0] = space->nested[1];
1957 space->nested[1] = nested;
1959 if (space->ids) {
1960 int n_id = space->n_in + space->n_out;
1961 ids = isl_alloc_array(space->ctx, isl_id *, n_id);
1962 if (n_id && !ids)
1963 goto error;
1964 get_ids(space, isl_dim_in, 0, space->n_in, ids);
1965 get_ids(space, isl_dim_out, 0, space->n_out, ids + space->n_in);
1968 t = space->n_in;
1969 space->n_in = space->n_out;
1970 space->n_out = t;
1972 if (space->ids) {
1973 space = set_ids(space, isl_dim_out, 0, space->n_out, ids);
1974 space = set_ids(space, isl_dim_in, 0, space->n_in,
1975 ids + space->n_out);
1976 free(ids);
1979 return space;
1980 error:
1981 free(ids);
1982 isl_space_free(space);
1983 return NULL;
1986 /* Given a space A -> (B -> C), return the corresponding space
1987 * A -> (C -> B).
1989 * If the range tuple is named, then the name is only preserved
1990 * if B and C are equal tuples, in which case the output
1991 * of this function is identical to the input.
1993 __isl_give isl_space *isl_space_range_reverse(__isl_take isl_space *space)
1995 isl_space *nested;
1996 isl_bool equal;
1998 if (isl_space_check_range_is_wrapping(space) < 0)
1999 return isl_space_free(space);
2001 nested = isl_space_peek_nested(space, 1);
2002 equal = isl_space_tuple_is_equal(nested, isl_dim_in,
2003 nested, isl_dim_out);
2004 if (equal < 0)
2005 return isl_space_free(space);
2007 nested = isl_space_take_nested(space, 1);
2008 nested = isl_space_reverse(nested);
2009 space = isl_space_restore_nested(space, 1, nested);
2010 if (!equal)
2011 space = isl_space_reset_tuple_id(space, isl_dim_out);
2013 return space;
2016 __isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *space,
2017 enum isl_dim_type type, unsigned first, unsigned num)
2019 int i;
2021 if (!space)
2022 return NULL;
2024 if (num == 0)
2025 return isl_space_reset(space, type);
2027 if (!valid_dim_type(type))
2028 isl_die(space->ctx, isl_error_invalid,
2029 "cannot drop dimensions of specified type", goto error);
2031 if (isl_space_check_range(space, type, first, num) < 0)
2032 return isl_space_free(space);
2033 space = isl_space_cow(space);
2034 if (!space)
2035 goto error;
2036 if (space->ids) {
2037 space = extend_ids(space);
2038 if (!space)
2039 goto error;
2040 for (i = 0; i < num; ++i)
2041 isl_id_free(get_id(space, type, first + i));
2042 for (i = first+num; i < n(space, type); ++i)
2043 set_id(space, type, i - num, get_id(space, type, i));
2044 switch (type) {
2045 case isl_dim_param:
2046 get_ids(space, isl_dim_in, 0, space->n_in,
2047 space->ids + offset(space, isl_dim_in) - num);
2048 case isl_dim_in:
2049 get_ids(space, isl_dim_out, 0, space->n_out,
2050 space->ids + offset(space, isl_dim_out) - num);
2051 default:
2054 space->n_id -= num;
2056 switch (type) {
2057 case isl_dim_param: space->nparam -= num; break;
2058 case isl_dim_in: space->n_in -= num; break;
2059 case isl_dim_out: space->n_out -= num; break;
2060 default: ;
2062 space = isl_space_reset(space, type);
2063 if (type == isl_dim_param) {
2064 if (space && space->nested[0] &&
2065 !(space->nested[0] = isl_space_drop_dims(space->nested[0],
2066 isl_dim_param, first, num)))
2067 goto error;
2068 if (space && space->nested[1] &&
2069 !(space->nested[1] = isl_space_drop_dims(space->nested[1],
2070 isl_dim_param, first, num)))
2071 goto error;
2073 return space;
2074 error:
2075 isl_space_free(space);
2076 return NULL;
2079 __isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *space,
2080 unsigned first, unsigned n)
2082 if (!space)
2083 return NULL;
2084 return isl_space_drop_dims(space, isl_dim_in, first, n);
2087 __isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *space,
2088 unsigned first, unsigned n)
2090 if (!space)
2091 return NULL;
2092 return isl_space_drop_dims(space, isl_dim_out, first, n);
2095 /* Remove all parameters from "space".
2097 __isl_give isl_space *isl_space_drop_all_params(__isl_take isl_space *space)
2099 isl_size nparam;
2101 nparam = isl_space_dim(space, isl_dim_param);
2102 if (nparam < 0)
2103 return isl_space_free(space);
2104 return isl_space_drop_dims(space, isl_dim_param, 0, nparam);
2107 __isl_give isl_space *isl_space_domain(__isl_take isl_space *space)
2109 if (!space)
2110 return NULL;
2111 space = isl_space_drop_dims(space, isl_dim_out, 0, space->n_out);
2112 space = isl_space_reverse(space);
2113 space = mark_as_set(space);
2114 return space;
2117 __isl_give isl_space *isl_space_from_domain(__isl_take isl_space *space)
2119 if (!space)
2120 return NULL;
2121 if (!isl_space_is_set(space))
2122 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2123 "not a set space", goto error);
2124 space = isl_space_reverse(space);
2125 space = isl_space_reset(space, isl_dim_out);
2126 return space;
2127 error:
2128 isl_space_free(space);
2129 return NULL;
2132 __isl_give isl_space *isl_space_range(__isl_take isl_space *space)
2134 if (!space)
2135 return NULL;
2136 space = isl_space_drop_dims(space, isl_dim_in, 0, space->n_in);
2137 space = mark_as_set(space);
2138 return space;
2141 __isl_give isl_space *isl_space_from_range(__isl_take isl_space *space)
2143 if (!space)
2144 return NULL;
2145 if (!isl_space_is_set(space))
2146 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2147 "not a set space", goto error);
2148 return isl_space_reset(space, isl_dim_in);
2149 error:
2150 isl_space_free(space);
2151 return NULL;
2154 /* Given a map space A -> B, return the map space [A -> B] -> A.
2156 __isl_give isl_space *isl_space_domain_map(__isl_take isl_space *space)
2158 isl_space *domain;
2160 domain = isl_space_from_range(isl_space_domain(isl_space_copy(space)));
2161 space = isl_space_from_domain(isl_space_wrap(space));
2162 space = isl_space_join(space, domain);
2164 return space;
2167 /* Given a map space A -> B, return the map space [A -> B] -> B.
2169 __isl_give isl_space *isl_space_range_map(__isl_take isl_space *space)
2171 isl_space *range;
2173 range = isl_space_from_range(isl_space_range(isl_space_copy(space)));
2174 space = isl_space_from_domain(isl_space_wrap(space));
2175 space = isl_space_join(space, range);
2177 return space;
2180 __isl_give isl_space *isl_space_params(__isl_take isl_space *space)
2182 isl_size n_in, n_out;
2184 if (isl_space_is_params(space))
2185 return space;
2186 n_in = isl_space_dim(space, isl_dim_in);
2187 n_out = isl_space_dim(space, isl_dim_out);
2188 if (n_in < 0 || n_out < 0)
2189 return isl_space_free(space);
2190 space = isl_space_drop_dims(space, isl_dim_in, 0, n_in);
2191 space = isl_space_drop_dims(space, isl_dim_out, 0, n_out);
2192 space = mark_as_params(space);
2193 return space;
2196 __isl_give isl_space *isl_space_set_from_params(__isl_take isl_space *space)
2198 if (!space)
2199 return NULL;
2200 if (!isl_space_is_params(space))
2201 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2202 "not a parameter space", goto error);
2203 return isl_space_reset(space, isl_dim_set);
2204 error:
2205 isl_space_free(space);
2206 return NULL;
2209 /* Add an unnamed tuple of dimension "dim" to "space".
2210 * This requires "space" to be a parameter or set space.
2212 * In particular, if "space" is a parameter space, then return
2213 * a set space with the given dimension.
2214 * If "space" is a set space, then return a map space
2215 * with "space" as domain and a range of the given dimension.
2217 __isl_give isl_space *isl_space_add_unnamed_tuple_ui(
2218 __isl_take isl_space *space, unsigned dim)
2220 isl_bool is_params, is_set;
2222 is_params = isl_space_is_params(space);
2223 is_set = isl_space_is_set(space);
2224 if (is_params < 0 || is_set < 0)
2225 return isl_space_free(space);
2226 if (!is_params && !is_set)
2227 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2228 "cannot add tuple to map space",
2229 return isl_space_free(space));
2230 if (is_params)
2231 space = isl_space_set_from_params(space);
2232 else
2233 space = isl_space_from_domain(space);
2234 space = isl_space_add_dims(space, isl_dim_out, dim);
2235 return space;
2238 /* Add a tuple of dimension "dim" and with tuple identifier "tuple_id"
2239 * to "space".
2240 * This requires "space" to be a parameter or set space.
2242 __isl_give isl_space *isl_space_add_named_tuple_id_ui(
2243 __isl_take isl_space *space, __isl_take isl_id *tuple_id, unsigned dim)
2245 space = isl_space_add_unnamed_tuple_ui(space, dim);
2246 space = isl_space_set_tuple_id(space, isl_dim_out, tuple_id);
2247 return space;
2250 /* Check that the identifiers in "tuple" do not appear as parameters
2251 * in "space".
2253 static isl_stat check_fresh_params(__isl_keep isl_space *space,
2254 __isl_keep isl_multi_id *tuple)
2256 int i;
2257 isl_size n;
2259 n = isl_multi_id_size(tuple);
2260 if (n < 0)
2261 return isl_stat_error;
2262 for (i = 0; i < n; ++i) {
2263 isl_id *id;
2264 int pos;
2266 id = isl_multi_id_get_at(tuple, i);
2267 if (!id)
2268 return isl_stat_error;
2269 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
2270 isl_id_free(id);
2271 if (pos >= 0)
2272 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2273 "parameters not unique", return isl_stat_error);
2276 return isl_stat_ok;
2279 /* Add the identifiers in "tuple" as parameters of "space"
2280 * that are known to be fresh.
2282 static __isl_give isl_space *add_bind_params(__isl_take isl_space *space,
2283 __isl_keep isl_multi_id *tuple)
2285 int i;
2286 isl_size first, n;
2288 first = isl_space_dim(space, isl_dim_param);
2289 n = isl_multi_id_size(tuple);
2290 if (first < 0 || n < 0)
2291 return isl_space_free(space);
2292 space = isl_space_add_dims(space, isl_dim_param, n);
2293 for (i = 0; i < n; ++i) {
2294 isl_id *id;
2296 id = isl_multi_id_get_at(tuple, i);
2297 space = isl_space_set_dim_id(space,
2298 isl_dim_param, first + i, id);
2301 return space;
2304 /* Internal function that removes the set tuple of "space",
2305 * which is assumed to correspond to the range space of "tuple", and
2306 * adds the identifiers in "tuple" as fresh parameters.
2307 * In other words, the set dimensions of "space" are reinterpreted
2308 * as parameters, but stay in the same global positions.
2310 __isl_give isl_space *isl_space_bind_set(__isl_take isl_space *space,
2311 __isl_keep isl_multi_id *tuple)
2313 isl_space *tuple_space;
2315 if (isl_space_check_is_set(space) < 0)
2316 return isl_space_free(space);
2317 tuple_space = isl_multi_id_peek_space(tuple);
2318 if (isl_space_check_equal_tuples(tuple_space, space) < 0)
2319 return isl_space_free(space);
2320 if (check_fresh_params(space, tuple) < 0)
2321 return isl_space_free(space);
2322 space = isl_space_params(space);
2323 space = add_bind_params(space, tuple);
2324 return space;
2327 /* Internal function that removes the domain tuple of the map space "space",
2328 * which is assumed to correspond to the range space of "tuple", and
2329 * adds the identifiers in "tuple" as fresh parameters.
2330 * In other words, the domain dimensions of "space" are reinterpreted
2331 * as parameters, but stay in the same global positions.
2333 __isl_give isl_space *isl_space_bind_map_domain(__isl_take isl_space *space,
2334 __isl_keep isl_multi_id *tuple)
2336 isl_space *tuple_space;
2338 if (isl_space_check_is_map(space) < 0)
2339 return isl_space_free(space);
2340 tuple_space = isl_multi_id_peek_space(tuple);
2341 if (isl_space_check_domain_tuples(tuple_space, space) < 0)
2342 return isl_space_free(space);
2343 if (check_fresh_params(space, tuple) < 0)
2344 return isl_space_free(space);
2345 space = isl_space_range(space);
2346 space = add_bind_params(space, tuple);
2347 return space;
2350 /* Internal function that, given a space of the form [A -> B] -> C and
2351 * a tuple of identifiers in A, returns a space B -> C with
2352 * the identifiers in "tuple" added as fresh parameters.
2353 * In other words, the domain dimensions of the wrapped relation
2354 * in the domain of "space" are reinterpreted
2355 * as parameters, but stay in the same global positions.
2357 __isl_give isl_space *isl_space_bind_domain_wrapped_domain(
2358 __isl_take isl_space *space, __isl_keep isl_multi_id *tuple)
2360 isl_space *tuple_space;
2362 if (isl_space_check_is_map(space) < 0)
2363 return isl_space_free(space);
2364 tuple_space = isl_multi_id_peek_space(tuple);
2365 if (isl_space_check_domain_wrapped_domain_tuples(tuple_space,
2366 space) < 0)
2367 return isl_space_free(space);
2368 if (check_fresh_params(space, tuple) < 0)
2369 return isl_space_free(space);
2370 space = isl_space_domain_factor_range(space);
2371 space = add_bind_params(space, tuple);
2372 return space;
2375 /* Insert a domain tuple in "space" corresponding to the set space "domain".
2376 * In particular, if "space" is a parameter space, then the result
2377 * is the set space "domain" combined with the parameters of "space".
2378 * If "space" is a set space, then the result
2379 * is a map space with "domain" as domain and the original space as range.
2381 static __isl_give isl_space *isl_space_insert_domain(
2382 __isl_take isl_space *space, __isl_take isl_space *domain)
2384 isl_bool is_params;
2386 domain = isl_space_replace_params(domain, space);
2388 is_params = isl_space_is_params(space);
2389 if (is_params < 0) {
2390 isl_space_free(domain);
2391 space = isl_space_free(space);
2392 } else if (is_params) {
2393 isl_space_free(space);
2394 space = domain;
2395 } else {
2396 space = isl_space_map_from_domain_and_range(domain, space);
2398 return space;
2401 /* Internal function that introduces a domain in "space"
2402 * corresponding to the range space of "tuple".
2403 * In particular, if "space" is a parameter space, then the result
2404 * is a set space. If "space" is a set space, then the result
2405 * is a map space with the original space as range.
2406 * Parameters that correspond to the identifiers in "tuple" are removed.
2408 * The parameters are removed in reverse order (under the assumption
2409 * that they appear in the same order in "multi") because
2410 * it is slightly more efficient to remove parameters at the end.
2412 * For pretty-printing purposes, the identifiers of the set dimensions
2413 * of the introduced domain are set to the identifiers in "tuple".
2415 __isl_give isl_space *isl_space_unbind_params_insert_domain(
2416 __isl_take isl_space *space, __isl_keep isl_multi_id *tuple)
2418 int i;
2419 isl_size n;
2420 isl_space *tuple_space;
2422 n = isl_multi_id_size(tuple);
2423 if (!space || n < 0)
2424 return isl_space_free(space);
2425 for (i = n - 1; i >= 0; --i) {
2426 isl_id *id;
2427 int pos;
2429 id = isl_multi_id_get_id(tuple, i);
2430 if (!id)
2431 return isl_space_free(space);
2432 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
2433 isl_id_free(id);
2434 if (pos < 0)
2435 continue;
2436 space = isl_space_drop_dims(space, isl_dim_param, pos, 1);
2438 tuple_space = isl_multi_id_get_space(tuple);
2439 for (i = 0; i < n; ++i) {
2440 isl_id *id;
2442 id = isl_multi_id_get_id(tuple, i);
2443 tuple_space = isl_space_set_dim_id(tuple_space,
2444 isl_dim_set, i, id);
2446 return isl_space_insert_domain(space, tuple_space);
2449 __isl_give isl_space *isl_space_underlying(__isl_take isl_space *space,
2450 unsigned n_div)
2452 int i;
2453 isl_bool is_set;
2455 is_set = isl_space_is_set(space);
2456 if (is_set < 0)
2457 return isl_space_free(space);
2458 if (n_div == 0 && is_set &&
2459 space->nparam == 0 && space->n_in == 0 && space->n_id == 0)
2460 return isl_space_reset(space, isl_dim_out);
2461 space = isl_space_cow(space);
2462 if (!space)
2463 return NULL;
2464 space->n_out += space->nparam + space->n_in + n_div;
2465 space->nparam = 0;
2466 space->n_in = 0;
2468 for (i = 0; i < space->n_id; ++i)
2469 isl_id_free(get_id(space, isl_dim_out, i));
2470 space->n_id = 0;
2471 space = isl_space_reset(space, isl_dim_in);
2472 space = isl_space_reset(space, isl_dim_out);
2473 space = mark_as_set(space);
2475 return space;
2478 /* Are the two spaces the same, including positions and names of parameters?
2480 isl_bool isl_space_is_equal(__isl_keep isl_space *space1,
2481 __isl_keep isl_space *space2)
2483 isl_bool equal;
2485 if (!space1 || !space2)
2486 return isl_bool_error;
2487 if (space1 == space2)
2488 return isl_bool_true;
2489 equal = isl_space_has_equal_params(space1, space2);
2490 if (equal < 0 || !equal)
2491 return equal;
2492 return isl_space_has_equal_tuples(space1, space2);
2495 /* Do the tuples of "space1" correspond to those of the domain of "space2"?
2496 * That is, is "space1" equal to the domain of "space2", ignoring parameters.
2498 * "space2" is allowed to be a set space, in which case "space1"
2499 * should be a parameter space.
2501 isl_bool isl_space_has_domain_tuples(__isl_keep isl_space *space1,
2502 __isl_keep isl_space *space2)
2504 isl_bool is_set;
2506 is_set = isl_space_is_set(space1);
2507 if (is_set < 0 || !is_set)
2508 return is_set;
2509 return isl_space_tuple_is_equal(space1, isl_dim_set,
2510 space2, isl_dim_in);
2513 /* Do the tuples of "space1" correspond to those of the range of "space2"?
2514 * That is, is "space1" equal to the range of "space2", ignoring parameters.
2516 * "space2" is allowed to be the space of a set,
2517 * in which case it should be equal to "space1", ignoring parameters.
2519 isl_bool isl_space_has_range_tuples(__isl_keep isl_space *space1,
2520 __isl_keep isl_space *space2)
2522 isl_bool is_set;
2524 is_set = isl_space_is_set(space1);
2525 if (is_set < 0 || !is_set)
2526 return is_set;
2527 return isl_space_tuple_is_equal(space1, isl_dim_set,
2528 space2, isl_dim_out);
2531 /* Check that the tuples of "space1" correspond to those
2532 * of the domain of "space2".
2533 * That is, check that "space1" is equal to the domain of "space2",
2534 * ignoring parameters.
2536 isl_stat isl_space_check_domain_tuples(__isl_keep isl_space *space1,
2537 __isl_keep isl_space *space2)
2539 isl_bool is_equal;
2541 is_equal = isl_space_has_domain_tuples(space1, space2);
2542 return check_match(space1, is_equal);
2545 /* Check that the tuples of "space1" correspond to those
2546 * of the domain of the wrapped relation in the domain of "space2".
2547 * That is, check that "space1" is equal to this domain,
2548 * ignoring parameters.
2550 isl_stat isl_space_check_domain_wrapped_domain_tuples(
2551 __isl_keep isl_space *space1, __isl_keep isl_space *space2)
2553 isl_space *domain;
2554 isl_stat r;
2556 domain = isl_space_unwrap(isl_space_domain(isl_space_copy(space2)));
2557 r = isl_space_check_domain_tuples(space1, domain);
2558 isl_space_free(domain);
2560 return r;
2563 /* Is space1 equal to the domain of space2?
2565 * In the internal version we also allow space2 to be the space of a set,
2566 * provided space1 is a parameter space.
2568 isl_bool isl_space_is_domain_internal(__isl_keep isl_space *space1,
2569 __isl_keep isl_space *space2)
2571 isl_bool equal_params;
2573 if (!space1 || !space2)
2574 return isl_bool_error;
2575 equal_params = isl_space_has_equal_params(space1, space2);
2576 if (equal_params < 0 || !equal_params)
2577 return equal_params;
2578 return isl_space_has_domain_tuples(space1, space2);
2581 /* Is space1 equal to the domain of space2?
2583 isl_bool isl_space_is_domain(__isl_keep isl_space *space1,
2584 __isl_keep isl_space *space2)
2586 if (!space2)
2587 return isl_bool_error;
2588 if (!isl_space_is_map(space2))
2589 return isl_bool_false;
2590 return isl_space_is_domain_internal(space1, space2);
2593 /* Is space1 equal to the range of space2?
2595 * In the internal version, space2 is allowed to be the space of a set,
2596 * in which case it should be equal to space1.
2598 isl_bool isl_space_is_range_internal(__isl_keep isl_space *space1,
2599 __isl_keep isl_space *space2)
2601 isl_bool equal_params;
2603 if (!space1 || !space2)
2604 return isl_bool_error;
2605 equal_params = isl_space_has_equal_params(space1, space2);
2606 if (equal_params < 0 || !equal_params)
2607 return equal_params;
2608 return isl_space_has_range_tuples(space1, space2);
2611 /* Is space1 equal to the range of space2?
2613 isl_bool isl_space_is_range(__isl_keep isl_space *space1,
2614 __isl_keep isl_space *space2)
2616 if (!space2)
2617 return isl_bool_error;
2618 if (!isl_space_is_map(space2))
2619 return isl_bool_false;
2620 return isl_space_is_range_internal(space1, space2);
2623 /* Update "hash" by hashing in the parameters of "space".
2625 static uint32_t isl_hash_params(uint32_t hash, __isl_keep isl_space *space)
2627 int i;
2628 isl_id *id;
2630 if (!space)
2631 return hash;
2633 isl_hash_byte(hash, space->nparam % 256);
2635 for (i = 0; i < space->nparam; ++i) {
2636 id = get_id(space, isl_dim_param, i);
2637 hash = isl_hash_id(hash, id);
2640 return hash;
2643 /* Update "hash" by hashing in the tuples of "space".
2644 * Changes in this function should be reflected in isl_hash_tuples_domain.
2646 static uint32_t isl_hash_tuples(uint32_t hash, __isl_keep isl_space *space)
2648 isl_id *id;
2650 if (!space)
2651 return hash;
2653 isl_hash_byte(hash, space->n_in % 256);
2654 isl_hash_byte(hash, space->n_out % 256);
2656 id = tuple_id(space, isl_dim_in);
2657 hash = isl_hash_id(hash, id);
2658 id = tuple_id(space, isl_dim_out);
2659 hash = isl_hash_id(hash, id);
2661 hash = isl_hash_tuples(hash, space->nested[0]);
2662 hash = isl_hash_tuples(hash, space->nested[1]);
2664 return hash;
2667 /* Update "hash" by hashing in the domain tuple of "space".
2668 * The result of this function is equal to the result of applying
2669 * isl_hash_tuples to the domain of "space".
2671 static uint32_t isl_hash_tuples_domain(uint32_t hash,
2672 __isl_keep isl_space *space)
2674 isl_id *id;
2676 if (!space)
2677 return hash;
2679 isl_hash_byte(hash, 0);
2680 isl_hash_byte(hash, space->n_in % 256);
2682 hash = isl_hash_id(hash, &isl_id_none);
2683 id = tuple_id(space, isl_dim_in);
2684 hash = isl_hash_id(hash, id);
2686 hash = isl_hash_tuples(hash, space->nested[0]);
2688 return hash;
2691 /* Return a hash value that digests the tuples of "space",
2692 * i.e., that ignores the parameters.
2693 * Changes in this function should be reflected
2694 * in isl_space_get_tuple_domain_hash.
2696 uint32_t isl_space_get_tuple_hash(__isl_keep isl_space *space)
2698 uint32_t hash;
2700 if (!space)
2701 return 0;
2703 hash = isl_hash_init();
2704 hash = isl_hash_tuples(hash, space);
2706 return hash;
2709 /* Return the hash value of "space".
2711 uint32_t isl_space_get_full_hash(__isl_keep isl_space *space)
2713 uint32_t hash;
2715 if (!space)
2716 return 0;
2718 hash = isl_hash_init();
2719 hash = isl_hash_params(hash, space);
2720 hash = isl_hash_tuples(hash, space);
2722 return hash;
2725 /* Return the hash value of the domain tuple of "space".
2726 * That is, isl_space_get_tuple_domain_hash(space) is equal to
2727 * isl_space_get_tuple_hash(isl_space_domain(space)).
2729 uint32_t isl_space_get_tuple_domain_hash(__isl_keep isl_space *space)
2731 uint32_t hash;
2733 if (!space)
2734 return 0;
2736 hash = isl_hash_init();
2737 hash = isl_hash_tuples_domain(hash, space);
2739 return hash;
2742 /* Is "space" the space of a set wrapping a map space?
2744 isl_bool isl_space_is_wrapping(__isl_keep isl_space *space)
2746 if (!space)
2747 return isl_bool_error;
2749 if (!isl_space_is_set(space))
2750 return isl_bool_false;
2752 return isl_bool_ok(space->nested[1] != NULL);
2755 /* Is "space" the space of a map where the domain is a wrapped map space?
2757 isl_bool isl_space_domain_is_wrapping(__isl_keep isl_space *space)
2759 if (!space)
2760 return isl_bool_error;
2762 if (isl_space_is_set(space))
2763 return isl_bool_false;
2765 return isl_bool_ok(space->nested[0] != NULL);
2768 /* Is "space" the space of a map where the range is a wrapped map space?
2770 isl_bool isl_space_range_is_wrapping(__isl_keep isl_space *space)
2772 if (!space)
2773 return isl_bool_error;
2775 if (isl_space_is_set(space))
2776 return isl_bool_false;
2778 return isl_bool_ok(space->nested[1] != NULL);
2781 /* Is "space" a product of two spaces?
2782 * That is, is it a wrapping set space or a map space
2783 * with wrapping domain and range?
2785 isl_bool isl_space_is_product(__isl_keep isl_space *space)
2787 isl_bool is_set;
2788 isl_bool is_product;
2790 is_set = isl_space_is_set(space);
2791 if (is_set < 0)
2792 return isl_bool_error;
2793 if (is_set)
2794 return isl_space_is_wrapping(space);
2795 is_product = isl_space_domain_is_wrapping(space);
2796 if (is_product < 0 || !is_product)
2797 return is_product;
2798 return isl_space_range_is_wrapping(space);
2801 __isl_give isl_space *isl_space_wrap(__isl_take isl_space *space)
2803 isl_space *wrap;
2805 if (!space)
2806 return NULL;
2808 wrap = isl_space_set_alloc(space->ctx,
2809 space->nparam, space->n_in + space->n_out);
2811 wrap = copy_ids(wrap, isl_dim_param, 0, space, isl_dim_param);
2812 wrap = copy_ids(wrap, isl_dim_set, 0, space, isl_dim_in);
2813 wrap = copy_ids(wrap, isl_dim_set, space->n_in, space, isl_dim_out);
2815 if (!wrap)
2816 goto error;
2818 wrap->nested[1] = space;
2820 return wrap;
2821 error:
2822 isl_space_free(space);
2823 return NULL;
2826 __isl_give isl_space *isl_space_unwrap(__isl_take isl_space *space)
2828 isl_space *unwrap;
2830 if (!space)
2831 return NULL;
2833 if (!isl_space_is_wrapping(space))
2834 isl_die(space->ctx, isl_error_invalid, "not a wrapping space",
2835 goto error);
2837 unwrap = isl_space_copy(space->nested[1]);
2838 isl_space_free(space);
2840 return unwrap;
2841 error:
2842 isl_space_free(space);
2843 return NULL;
2846 isl_bool isl_space_is_named_or_nested(__isl_keep isl_space *space,
2847 enum isl_dim_type type)
2849 if (type != isl_dim_in && type != isl_dim_out)
2850 return isl_bool_false;
2851 if (!space)
2852 return isl_bool_error;
2853 if (space->tuple_id[type - isl_dim_in])
2854 return isl_bool_true;
2855 if (space->nested[type - isl_dim_in])
2856 return isl_bool_true;
2857 return isl_bool_false;
2860 isl_bool isl_space_may_be_set(__isl_keep isl_space *space)
2862 isl_bool nested;
2863 isl_size n_in;
2865 if (!space)
2866 return isl_bool_error;
2867 if (isl_space_is_set(space))
2868 return isl_bool_true;
2869 n_in = isl_space_dim(space, isl_dim_in);
2870 if (n_in < 0)
2871 return isl_bool_error;
2872 if (n_in != 0)
2873 return isl_bool_false;
2874 nested = isl_space_is_named_or_nested(space, isl_dim_in);
2875 if (nested < 0 || nested)
2876 return isl_bool_not(nested);
2877 return isl_bool_true;
2880 __isl_give isl_space *isl_space_reset(__isl_take isl_space *space,
2881 enum isl_dim_type type)
2883 if (!isl_space_is_named_or_nested(space, type))
2884 return space;
2886 space = isl_space_cow(space);
2887 if (!space)
2888 return NULL;
2890 isl_id_free(space->tuple_id[type - isl_dim_in]);
2891 space->tuple_id[type - isl_dim_in] = NULL;
2892 isl_space_free(space->nested[type - isl_dim_in]);
2893 space->nested[type - isl_dim_in] = NULL;
2895 return space;
2898 __isl_give isl_space *isl_space_flatten(__isl_take isl_space *space)
2900 if (!space)
2901 return NULL;
2902 if (!space->nested[0] && !space->nested[1])
2903 return space;
2905 if (space->nested[0])
2906 space = isl_space_reset(space, isl_dim_in);
2907 if (space && space->nested[1])
2908 space = isl_space_reset(space, isl_dim_out);
2910 return space;
2913 __isl_give isl_space *isl_space_flatten_domain(__isl_take isl_space *space)
2915 if (!space)
2916 return NULL;
2917 if (!space->nested[0])
2918 return space;
2920 return isl_space_reset(space, isl_dim_in);
2923 __isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *space)
2925 if (!space)
2926 return NULL;
2927 if (!space->nested[1])
2928 return space;
2930 return isl_space_reset(space, isl_dim_out);
2933 /* Replace the parameters of dst by those of src.
2935 __isl_give isl_space *isl_space_replace_params(__isl_take isl_space *dst,
2936 __isl_keep isl_space *src)
2938 isl_size dst_dim, src_dim;
2939 isl_bool equal_params;
2940 enum isl_dim_type type = isl_dim_param;
2942 equal_params = isl_space_has_equal_params(dst, src);
2943 if (equal_params < 0)
2944 return isl_space_free(dst);
2945 if (equal_params)
2946 return dst;
2948 dst = isl_space_cow(dst);
2950 dst_dim = isl_space_dim(dst, type);
2951 src_dim = isl_space_dim(src, type);
2952 if (dst_dim < 0 || src_dim < 0)
2953 goto error;
2955 dst = isl_space_drop_dims(dst, type, 0, dst_dim);
2956 dst = isl_space_add_dims(dst, type, src_dim);
2957 dst = copy_ids(dst, type, 0, src, type);
2959 if (dst) {
2960 int i;
2961 for (i = 0; i <= 1; ++i) {
2962 isl_space *nested;
2964 if (!dst->nested[i])
2965 continue;
2966 nested = isl_space_take_nested(dst, i);
2967 nested = isl_space_replace_params(nested, src);
2968 dst = isl_space_restore_nested(dst, i, nested);
2969 if (!dst)
2970 return NULL;
2974 return dst;
2975 error:
2976 isl_space_free(dst);
2977 return NULL;
2980 /* Given two tuples ("dst_type" in "dst" and "src_type" in "src")
2981 * of the same size, check if any of the dimensions in the "dst" tuple
2982 * have no identifier, while the corresponding dimensions in "src"
2983 * does have an identifier,
2984 * If so, copy the identifier over to "dst".
2986 __isl_give isl_space *isl_space_copy_ids_if_unset(__isl_take isl_space *dst,
2987 enum isl_dim_type dst_type, __isl_keep isl_space *src,
2988 enum isl_dim_type src_type)
2990 int i;
2991 isl_size n;
2993 n = isl_space_dim(dst, dst_type);
2994 if (n < 0)
2995 return isl_space_free(dst);
2996 for (i = 0; i < n; ++i) {
2997 isl_bool set;
2998 isl_id *id;
3000 set = isl_space_has_dim_id(dst, dst_type, i);
3001 if (set < 0)
3002 return isl_space_free(dst);
3003 if (set)
3004 continue;
3006 set = isl_space_has_dim_id(src, src_type, i);
3007 if (set < 0)
3008 return isl_space_free(dst);
3009 if (!set)
3010 continue;
3012 id = isl_space_get_dim_id(src, src_type, i);
3013 dst = isl_space_set_dim_id(dst, dst_type, i, id);
3016 return dst;
3019 /* Given a space "space" of a set, create a space
3020 * for the lift of the set. In particular, the result
3021 * is of the form lifted[space -> local[..]], with n_local variables in the
3022 * range of the wrapped map.
3024 __isl_give isl_space *isl_space_lift(__isl_take isl_space *space,
3025 unsigned n_local)
3027 isl_space *local_space;
3029 if (!space)
3030 return NULL;
3032 local_space = isl_space_dup(space);
3033 local_space = isl_space_drop_dims(local_space, isl_dim_set, 0,
3034 space->n_out);
3035 local_space = isl_space_add_dims(local_space, isl_dim_set, n_local);
3036 local_space = isl_space_set_tuple_name(local_space,
3037 isl_dim_set, "local");
3038 space = isl_space_join(isl_space_from_domain(space),
3039 isl_space_from_range(local_space));
3040 space = isl_space_wrap(space);
3041 space = isl_space_set_tuple_name(space, isl_dim_set, "lifted");
3043 return space;
3046 isl_bool isl_space_can_zip(__isl_keep isl_space *space)
3048 isl_bool is_set;
3050 is_set = isl_space_is_set(space);
3051 if (is_set < 0)
3052 return isl_bool_error;
3053 if (is_set)
3054 return isl_bool_false;
3055 return isl_space_is_product(space);
3058 __isl_give isl_space *isl_space_zip(__isl_take isl_space *space)
3060 isl_space *dom, *ran;
3061 isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran;
3063 if (!isl_space_can_zip(space))
3064 isl_die(space->ctx, isl_error_invalid, "space cannot be zipped",
3065 goto error);
3067 if (!space)
3068 return NULL;
3069 dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));
3070 ran = isl_space_unwrap(isl_space_range(space));
3071 dom_dom = isl_space_domain(isl_space_copy(dom));
3072 dom_ran = isl_space_range(dom);
3073 ran_dom = isl_space_domain(isl_space_copy(ran));
3074 ran_ran = isl_space_range(ran);
3075 dom = isl_space_join(isl_space_from_domain(dom_dom),
3076 isl_space_from_range(ran_dom));
3077 ran = isl_space_join(isl_space_from_domain(dom_ran),
3078 isl_space_from_range(ran_ran));
3079 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
3080 isl_space_from_range(isl_space_wrap(ran)));
3081 error:
3082 isl_space_free(space);
3083 return NULL;
3086 /* Can we apply isl_space_curry to "space"?
3087 * That is, does is it have a map space with a nested relation in its domain?
3089 isl_bool isl_space_can_curry(__isl_keep isl_space *space)
3091 return isl_space_domain_is_wrapping(space);
3094 /* Given a space (A -> B) -> C, return the corresponding space
3095 * A -> (B -> C).
3097 __isl_give isl_space *isl_space_curry(__isl_take isl_space *space)
3099 isl_space *dom, *ran;
3100 isl_space *dom_dom, *dom_ran;
3102 if (!space)
3103 return NULL;
3105 if (!isl_space_can_curry(space))
3106 isl_die(space->ctx, isl_error_invalid,
3107 "space cannot be curried", goto error);
3109 dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));
3110 ran = isl_space_range(space);
3111 dom_dom = isl_space_domain(isl_space_copy(dom));
3112 dom_ran = isl_space_range(dom);
3113 ran = isl_space_join(isl_space_from_domain(dom_ran),
3114 isl_space_from_range(ran));
3115 return isl_space_join(isl_space_from_domain(dom_dom),
3116 isl_space_from_range(isl_space_wrap(ran)));
3117 error:
3118 isl_space_free(space);
3119 return NULL;
3122 /* Can isl_space_range_curry be applied to "space"?
3123 * That is, does it have a nested relation in its range,
3124 * the domain of which is itself a nested relation?
3126 isl_bool isl_space_can_range_curry(__isl_keep isl_space *space)
3128 isl_bool can;
3130 if (!space)
3131 return isl_bool_error;
3132 can = isl_space_range_is_wrapping(space);
3133 if (can < 0 || !can)
3134 return can;
3135 return isl_space_can_curry(space->nested[1]);
3138 /* Given a space A -> ((B -> C) -> D), return the corresponding space
3139 * A -> (B -> (C -> D)).
3141 __isl_give isl_space *isl_space_range_curry(__isl_take isl_space *space)
3143 isl_space *nested;
3145 if (!space)
3146 return NULL;
3148 if (!isl_space_can_range_curry(space))
3149 isl_die(isl_space_get_ctx(space), isl_error_invalid,
3150 "space range cannot be curried",
3151 return isl_space_free(space));
3153 nested = isl_space_take_nested(space, 1);
3154 nested = isl_space_curry(nested);
3155 space = isl_space_restore_nested(space, 1, nested);
3157 return space;
3160 /* Can we apply isl_space_uncurry to "space"?
3161 * That is, does it have a map space with a nested relation in its range?
3163 isl_bool isl_space_can_uncurry(__isl_keep isl_space *space)
3165 return isl_space_range_is_wrapping(space);
3168 /* Given a space A -> (B -> C), return the corresponding space
3169 * (A -> B) -> C.
3171 __isl_give isl_space *isl_space_uncurry(__isl_take isl_space *space)
3173 isl_space *dom, *ran;
3174 isl_space *ran_dom, *ran_ran;
3176 if (!space)
3177 return NULL;
3179 if (!isl_space_can_uncurry(space))
3180 isl_die(space->ctx, isl_error_invalid,
3181 "space cannot be uncurried",
3182 return isl_space_free(space));
3184 dom = isl_space_domain(isl_space_copy(space));
3185 ran = isl_space_unwrap(isl_space_range(space));
3186 ran_dom = isl_space_domain(isl_space_copy(ran));
3187 ran_ran = isl_space_range(ran);
3188 dom = isl_space_join(isl_space_from_domain(dom),
3189 isl_space_from_range(ran_dom));
3190 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
3191 isl_space_from_range(ran_ran));
3194 isl_bool isl_space_has_named_params(__isl_keep isl_space *space)
3196 int i;
3197 unsigned off;
3199 if (!space)
3200 return isl_bool_error;
3201 if (space->nparam == 0)
3202 return isl_bool_true;
3203 off = isl_space_offset(space, isl_dim_param);
3204 if (off + space->nparam > space->n_id)
3205 return isl_bool_false;
3206 for (i = 0; i < space->nparam; ++i)
3207 if (!space->ids[off + i])
3208 return isl_bool_false;
3209 return isl_bool_true;
3212 /* Check that "space" has only named parameters, reporting an error
3213 * if it does not.
3215 isl_stat isl_space_check_named_params(__isl_keep isl_space *space)
3217 isl_bool named;
3219 named = isl_space_has_named_params(space);
3220 if (named < 0)
3221 return isl_stat_error;
3222 if (!named)
3223 isl_die(isl_space_get_ctx(space), isl_error_invalid,
3224 "unexpected unnamed parameters", return isl_stat_error);
3226 return isl_stat_ok;
3229 /* Align the initial parameters of space1 to match the order in space2.
3231 __isl_give isl_space *isl_space_align_params(__isl_take isl_space *space1,
3232 __isl_take isl_space *space2)
3234 isl_reordering *exp;
3236 if (isl_space_check_named_params(space1) < 0 ||
3237 isl_space_check_named_params(space2) < 0)
3238 goto error;
3240 exp = isl_parameter_alignment_reordering(space1, space2);
3241 exp = isl_reordering_extend_space(exp, space1);
3242 isl_space_free(space2);
3243 space1 = isl_reordering_get_space(exp);
3244 isl_reordering_free(exp);
3245 return space1;
3246 error:
3247 isl_space_free(space1);
3248 isl_space_free(space2);
3249 return NULL;
3252 /* Given the space of set (domain), construct a space for a map
3253 * with as domain the given space and as range the range of "model".
3255 __isl_give isl_space *isl_space_extend_domain_with_range(
3256 __isl_take isl_space *space, __isl_take isl_space *model)
3258 isl_size n_out;
3260 if (!model)
3261 goto error;
3263 space = isl_space_from_domain(space);
3264 n_out = isl_space_dim(model, isl_dim_out);
3265 if (n_out < 0)
3266 goto error;
3267 space = isl_space_add_dims(space, isl_dim_out, n_out);
3268 if (isl_space_has_tuple_id(model, isl_dim_out))
3269 space = isl_space_set_tuple_id(space, isl_dim_out,
3270 isl_space_get_tuple_id(model, isl_dim_out));
3271 if (!space)
3272 goto error;
3273 if (model->nested[1]) {
3274 isl_space *nested = isl_space_copy(model->nested[1]);
3275 isl_size n_nested, n_space;
3276 nested = isl_space_align_params(nested, isl_space_copy(space));
3277 n_nested = isl_space_dim(nested, isl_dim_param);
3278 n_space = isl_space_dim(space, isl_dim_param);
3279 if (n_nested < 0 || n_space < 0)
3280 goto error;
3281 if (n_nested > n_space)
3282 nested = isl_space_drop_dims(nested, isl_dim_param,
3283 n_space, n_nested - n_space);
3284 if (!nested)
3285 goto error;
3286 space->nested[1] = nested;
3288 isl_space_free(model);
3289 return space;
3290 error:
3291 isl_space_free(model);
3292 isl_space_free(space);
3293 return NULL;
3296 /* Compare the "type" dimensions of two isl_spaces.
3298 * The order is fairly arbitrary.
3300 static int isl_space_cmp_type(__isl_keep isl_space *space1,
3301 __isl_keep isl_space *space2, enum isl_dim_type type)
3303 int cmp;
3304 isl_size dim1, dim2;
3305 isl_space *nested1, *nested2;
3307 dim1 = isl_space_dim(space1, type);
3308 dim2 = isl_space_dim(space2, type);
3309 if (dim1 < 0 || dim2 < 0)
3310 return 0;
3311 if (dim1 != dim2)
3312 return dim1 - dim2;
3314 cmp = isl_id_cmp(tuple_id(space1, type), tuple_id(space2, type));
3315 if (cmp != 0)
3316 return cmp;
3318 nested1 = nested(space1, type);
3319 nested2 = nested(space2, type);
3320 if (!nested1 != !nested2)
3321 return !nested1 - !nested2;
3323 if (nested1)
3324 return isl_space_cmp(nested1, nested2);
3326 return 0;
3329 /* Compare two isl_spaces.
3331 * The order is fairly arbitrary.
3333 int isl_space_cmp(__isl_keep isl_space *space1, __isl_keep isl_space *space2)
3335 int i;
3336 int cmp;
3338 if (space1 == space2)
3339 return 0;
3340 if (!space1)
3341 return -1;
3342 if (!space2)
3343 return 1;
3345 cmp = isl_space_cmp_type(space1, space2, isl_dim_param);
3346 if (cmp != 0)
3347 return cmp;
3348 cmp = isl_space_cmp_type(space1, space2, isl_dim_in);
3349 if (cmp != 0)
3350 return cmp;
3351 cmp = isl_space_cmp_type(space1, space2, isl_dim_out);
3352 if (cmp != 0)
3353 return cmp;
3355 if (!space1->ids && !space2->ids)
3356 return 0;
3358 for (i = 0; i < n(space1, isl_dim_param); ++i) {
3359 cmp = isl_id_cmp(get_id(space1, isl_dim_param, i),
3360 get_id(space2, isl_dim_param, i));
3361 if (cmp != 0)
3362 return cmp;
3365 return 0;