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