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