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