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