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

source code of polly/lib/External/isl/isl_space.c