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