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