add packaging
[platform/upstream/isl.git] / isl_space.c
1 /*
2  * Copyright 2008-2009 Katholieke Universiteit Leuven
3  * Copyright 2010      INRIA Saclay
4  *
5  * Use of this software is governed by the MIT license
6  *
7  * Written by Sven Verdoolaege, K.U.Leuven, Departement
8  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
10  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 
11  */
12
13 #include <stdlib.h>
14 #include <string.h>
15 #include <isl_space_private.h>
16 #include <isl_id_private.h>
17 #include <isl_reordering.h>
18
19 isl_ctx *isl_space_get_ctx(__isl_keep isl_space *dim)
20 {
21         return dim ? dim->ctx : NULL;
22 }
23
24 __isl_give isl_space *isl_space_alloc(isl_ctx *ctx,
25                         unsigned nparam, unsigned n_in, unsigned n_out)
26 {
27         isl_space *dim;
28
29         dim = isl_alloc_type(ctx, struct isl_space);
30         if (!dim)
31                 return NULL;
32
33         dim->ctx = ctx;
34         isl_ctx_ref(ctx);
35         dim->ref = 1;
36         dim->nparam = nparam;
37         dim->n_in = n_in;
38         dim->n_out = n_out;
39
40         dim->tuple_id[0] = NULL;
41         dim->tuple_id[1] = NULL;
42
43         dim->nested[0] = NULL;
44         dim->nested[1] = NULL;
45
46         dim->n_id = 0;
47         dim->ids = NULL;
48
49         return dim;
50 }
51
52 /* Mark the space as being that of a set, by setting the domain tuple
53  * to isl_id_none.
54  */
55 static __isl_give isl_space *mark_as_set(__isl_take isl_space *space)
56 {
57         space = isl_space_cow(space);
58         if (!space)
59                 return NULL;
60         space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
61         return space;
62 }
63
64 /* Is the space that of a set?
65  */
66 int isl_space_is_set(__isl_keep isl_space *space)
67 {
68         if (!space)
69                 return -1;
70         if (space->n_in != 0 || space->nested[0])
71                 return 0;
72         if (space->tuple_id[0] != &isl_id_none)
73                 return 0;
74         return 1;
75 }
76
77 /* Is the given space that of a map?
78  */
79 int isl_space_is_map(__isl_keep isl_space *space)
80 {
81         if (!space)
82                 return -1;
83         return space->tuple_id[0] != &isl_id_none &&
84                 space->tuple_id[1] != &isl_id_none;
85 }
86
87 __isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,
88                         unsigned nparam, unsigned dim)
89 {
90         isl_space *space;
91         space = isl_space_alloc(ctx, nparam, 0, dim);
92         space = mark_as_set(space);
93         return space;
94 }
95
96 /* Mark the space as being that of a parameter domain, by setting
97  * both tuples to isl_id_none.
98  */
99 static __isl_give isl_space *mark_as_params(isl_space *space)
100 {
101         if (!space)
102                 return NULL;
103         space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
104         space = isl_space_set_tuple_id(space, isl_dim_out, &isl_id_none);
105         return space;
106 }
107
108 /* Is the space that of a parameter domain?
109  */
110 int isl_space_is_params(__isl_keep isl_space *space)
111 {
112         if (!space)
113                 return -1;
114         if (space->n_in != 0 || space->nested[0] ||
115             space->n_out != 0 || space->nested[1])
116                 return 0;
117         if (space->tuple_id[0] != &isl_id_none)
118                 return 0;
119         if (space->tuple_id[1] != &isl_id_none)
120                 return 0;
121         return 1;
122 }
123
124 /* Create a space for a parameter domain.
125  */
126 __isl_give isl_space *isl_space_params_alloc(isl_ctx *ctx, unsigned nparam)
127 {
128         isl_space *space;
129         space = isl_space_alloc(ctx, nparam, 0, 0);
130         space = mark_as_params(space);
131         return space;
132 }
133
134 static unsigned global_pos(__isl_keep isl_space *dim,
135                                  enum isl_dim_type type, unsigned pos)
136 {
137         struct isl_ctx *ctx = dim->ctx;
138
139         switch (type) {
140         case isl_dim_param:
141                 isl_assert(ctx, pos < dim->nparam,
142                             return isl_space_dim(dim, isl_dim_all));
143                 return pos;
144         case isl_dim_in:
145                 isl_assert(ctx, pos < dim->n_in,
146                             return isl_space_dim(dim, isl_dim_all));
147                 return pos + dim->nparam;
148         case isl_dim_out:
149                 isl_assert(ctx, pos < dim->n_out,
150                             return isl_space_dim(dim, isl_dim_all));
151                 return pos + dim->nparam + dim->n_in;
152         default:
153                 isl_assert(ctx, 0, return isl_space_dim(dim, isl_dim_all));
154         }
155         return isl_space_dim(dim, isl_dim_all);
156 }
157
158 /* Extend length of ids array to the total number of dimensions.
159  */
160 static __isl_give isl_space *extend_ids(__isl_take isl_space *dim)
161 {
162         isl_id **ids;
163         int i;
164
165         if (isl_space_dim(dim, isl_dim_all) <= dim->n_id)
166                 return dim;
167
168         if (!dim->ids) {
169                 dim->ids = isl_calloc_array(dim->ctx,
170                                 isl_id *, isl_space_dim(dim, isl_dim_all));
171                 if (!dim->ids)
172                         goto error;
173         } else {
174                 ids = isl_realloc_array(dim->ctx, dim->ids,
175                                 isl_id *, isl_space_dim(dim, isl_dim_all));
176                 if (!ids)
177                         goto error;
178                 dim->ids = ids;
179                 for (i = dim->n_id; i < isl_space_dim(dim, isl_dim_all); ++i)
180                         dim->ids[i] = NULL;
181         }
182
183         dim->n_id = isl_space_dim(dim, isl_dim_all);
184
185         return dim;
186 error:
187         isl_space_free(dim);
188         return NULL;
189 }
190
191 static __isl_give isl_space *set_id(__isl_take isl_space *dim,
192         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
193 {
194         dim = isl_space_cow(dim);
195
196         if (!dim)
197                 goto error;
198
199         pos = global_pos(dim, type, pos);
200         if (pos == isl_space_dim(dim, isl_dim_all))
201                 goto error;
202
203         if (pos >= dim->n_id) {
204                 if (!id)
205                         return dim;
206                 dim = extend_ids(dim);
207                 if (!dim)
208                         goto error;
209         }
210
211         dim->ids[pos] = id;
212
213         return dim;
214 error:
215         isl_id_free(id);
216         isl_space_free(dim);
217         return NULL;
218 }
219
220 static __isl_keep isl_id *get_id(__isl_keep isl_space *dim,
221                                  enum isl_dim_type type, unsigned pos)
222 {
223         if (!dim)
224                 return NULL;
225
226         pos = global_pos(dim, type, pos);
227         if (pos == isl_space_dim(dim, isl_dim_all))
228                 return NULL;
229         if (pos >= dim->n_id)
230                 return NULL;
231         return dim->ids[pos];
232 }
233
234 static unsigned offset(__isl_keep isl_space *dim, enum isl_dim_type type)
235 {
236         switch (type) {
237         case isl_dim_param:     return 0;
238         case isl_dim_in:        return dim->nparam;
239         case isl_dim_out:       return dim->nparam + dim->n_in;
240         default:                return 0;
241         }
242 }
243
244 static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type)
245 {
246         switch (type) {
247         case isl_dim_param:     return dim->nparam;
248         case isl_dim_in:        return dim->n_in;
249         case isl_dim_out:       return dim->n_out;
250         case isl_dim_all:       return dim->nparam + dim->n_in + dim->n_out;
251         default:                return 0;
252         }
253 }
254
255 unsigned isl_space_dim(__isl_keep isl_space *dim, enum isl_dim_type type)
256 {
257         if (!dim)
258                 return 0;
259         return n(dim, type);
260 }
261
262 unsigned isl_space_offset(__isl_keep isl_space *dim, enum isl_dim_type type)
263 {
264         if (!dim)
265                 return 0;
266         return offset(dim, type);
267 }
268
269 static __isl_give isl_space *copy_ids(__isl_take isl_space *dst,
270         enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_space *src,
271         enum isl_dim_type src_type)
272 {
273         int i;
274         isl_id *id;
275
276         if (!dst)
277                 return NULL;
278
279         for (i = 0; i < n(src, src_type); ++i) {
280                 id = get_id(src, src_type, i);
281                 if (!id)
282                         continue;
283                 dst = set_id(dst, dst_type, offset + i, isl_id_copy(id));
284                 if (!dst)
285                         return NULL;
286         }
287         return dst;
288 }
289
290 __isl_take isl_space *isl_space_dup(__isl_keep isl_space *dim)
291 {
292         isl_space *dup;
293         if (!dim)
294                 return NULL;
295         dup = isl_space_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
296         if (!dup)
297                 return NULL;
298         if (dim->tuple_id[0] &&
299             !(dup->tuple_id[0] = isl_id_copy(dim->tuple_id[0])))
300                 goto error;
301         if (dim->tuple_id[1] &&
302             !(dup->tuple_id[1] = isl_id_copy(dim->tuple_id[1])))
303                 goto error;
304         if (dim->nested[0] && !(dup->nested[0] = isl_space_copy(dim->nested[0])))
305                 goto error;
306         if (dim->nested[1] && !(dup->nested[1] = isl_space_copy(dim->nested[1])))
307                 goto error;
308         if (!dim->ids)
309                 return dup;
310         dup = copy_ids(dup, isl_dim_param, 0, dim, isl_dim_param);
311         dup = copy_ids(dup, isl_dim_in, 0, dim, isl_dim_in);
312         dup = copy_ids(dup, isl_dim_out, 0, dim, isl_dim_out);
313         return dup;
314 error:
315         isl_space_free(dup);
316         return NULL;
317 }
318
319 __isl_give isl_space *isl_space_cow(__isl_take isl_space *dim)
320 {
321         if (!dim)
322                 return NULL;
323
324         if (dim->ref == 1)
325                 return dim;
326         dim->ref--;
327         return isl_space_dup(dim);
328 }
329
330 __isl_give isl_space *isl_space_copy(__isl_keep isl_space *dim)
331 {
332         if (!dim)
333                 return NULL;
334
335         dim->ref++;
336         return dim;
337 }
338
339 void *isl_space_free(__isl_take isl_space *dim)
340 {
341         int i;
342
343         if (!dim)
344                 return NULL;
345
346         if (--dim->ref > 0)
347                 return NULL;
348
349         isl_id_free(dim->tuple_id[0]);
350         isl_id_free(dim->tuple_id[1]);
351
352         isl_space_free(dim->nested[0]);
353         isl_space_free(dim->nested[1]);
354
355         for (i = 0; i < dim->n_id; ++i)
356                 isl_id_free(dim->ids[i]);
357         free(dim->ids);
358         isl_ctx_deref(dim->ctx);
359         
360         free(dim);
361
362         return NULL;
363 }
364
365 /* Check if "s" is a valid dimension or tuple name.
366  * We currently only forbid names that look like a number.
367  *
368  * s is assumed to be non-NULL.
369  */
370 static int name_ok(isl_ctx *ctx, const char *s)
371 {
372         char *p;
373         long dummy;
374
375         dummy = strtol(s, &p, 0);
376         if (p != s)
377                 isl_die(ctx, isl_error_invalid, "name looks like a number",
378                         return 0);
379
380         return 1;
381 }
382
383 /* Is it possible for the given dimension type to have a tuple id?
384  */
385 static int space_can_have_id(__isl_keep isl_space *space,
386         enum isl_dim_type type)
387 {
388         if (!space)
389                 return 0;
390         if (isl_space_is_params(space))
391                 isl_die(space->ctx, isl_error_invalid,
392                         "parameter spaces don't have tuple ids", return 0);
393         if (isl_space_is_set(space) && type != isl_dim_set)
394                 isl_die(space->ctx, isl_error_invalid,
395                         "set spaces can only have a set id", return 0);
396         if (type != isl_dim_in && type != isl_dim_out)
397                 isl_die(space->ctx, isl_error_invalid,
398                         "only input, output and set tuples can have ids",
399                         return 0);
400
401         return 1;
402 }
403
404 /* Does the tuple have an id?
405  */
406 int isl_space_has_tuple_id(__isl_keep isl_space *dim, enum isl_dim_type type)
407 {
408         if (!space_can_have_id(dim, type))
409                 return -1;
410         return dim->tuple_id[type - isl_dim_in] != NULL;
411 }
412
413 __isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *dim,
414         enum isl_dim_type type)
415 {
416         int has_id;
417
418         if (!dim)
419                 return NULL;
420         has_id = isl_space_has_tuple_id(dim, type);
421         if (has_id < 0)
422                 return NULL;
423         if (!has_id)
424                 isl_die(dim->ctx, isl_error_invalid,
425                         "tuple has no id", return NULL);
426         return isl_id_copy(dim->tuple_id[type - isl_dim_in]);
427 }
428
429 __isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *dim,
430         enum isl_dim_type type, __isl_take isl_id *id)
431 {
432         dim = isl_space_cow(dim);
433         if (!dim || !id)
434                 goto error;
435         if (type != isl_dim_in && type != isl_dim_out)
436                 isl_die(dim->ctx, isl_error_invalid,
437                         "only input, output and set tuples can have names",
438                         goto error);
439
440         isl_id_free(dim->tuple_id[type - isl_dim_in]);
441         dim->tuple_id[type - isl_dim_in] = id;
442
443         return dim;
444 error:
445         isl_id_free(id);
446         isl_space_free(dim);
447         return NULL;
448 }
449
450 __isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *dim,
451         enum isl_dim_type type)
452 {
453         dim = isl_space_cow(dim);
454         if (!dim)
455                 return NULL;
456         if (type != isl_dim_in && type != isl_dim_out)
457                 isl_die(dim->ctx, isl_error_invalid,
458                         "only input, output and set tuples can have names",
459                         goto error);
460
461         isl_id_free(dim->tuple_id[type - isl_dim_in]);
462         dim->tuple_id[type - isl_dim_in] = NULL;
463
464         return dim;
465 error:
466         isl_space_free(dim);
467         return NULL;
468 }
469
470 /* Set the id of the given dimension of "space" to "id".
471  * If the dimension already has an id, then it is replaced.
472  * If the dimension is a parameter, then we need to change it
473  * in the nested spaces (if any) as well.
474  */
475 __isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *space,
476         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
477 {
478         space = isl_space_cow(space);
479         if (!space || !id)
480                 goto error;
481
482         if (type == isl_dim_param) {
483                 int i;
484
485                 for (i = 0; i < 2; ++i) {
486                         if (!space->nested[i])
487                                 continue;
488                         space->nested[i] =
489                                 isl_space_set_dim_id(space->nested[i],
490                                                 type, pos, isl_id_copy(id));
491                         if (!space->nested[i])
492                                 goto error;
493                 }
494         }
495
496         isl_id_free(get_id(space, type, pos));
497         return set_id(space, type, pos, id);
498 error:
499         isl_id_free(id);
500         isl_space_free(space);
501         return NULL;
502 }
503
504 /* Reset the id of the given dimension of "space".
505  * If the dimension already has an id, then it is removed.
506  * If the dimension is a parameter, then we need to reset it
507  * in the nested spaces (if any) as well.
508  */
509 __isl_give isl_space *isl_space_reset_dim_id(__isl_take isl_space *space,
510         enum isl_dim_type type, unsigned pos)
511 {
512         space = isl_space_cow(space);
513         if (!space)
514                 goto error;
515
516         if (type == isl_dim_param) {
517                 int i;
518
519                 for (i = 0; i < 2; ++i) {
520                         if (!space->nested[i])
521                                 continue;
522                         space->nested[i] =
523                                 isl_space_reset_dim_id(space->nested[i],
524                                                         type, pos);
525                         if (!space->nested[i])
526                                 goto error;
527                 }
528         }
529
530         isl_id_free(get_id(space, type, pos));
531         return set_id(space, type, pos, NULL);
532 error:
533         isl_space_free(space);
534         return NULL;
535 }
536
537 int isl_space_has_dim_id(__isl_keep isl_space *dim,
538         enum isl_dim_type type, unsigned pos)
539 {
540         if (!dim)
541                 return -1;
542         return get_id(dim, type, pos) != NULL;
543 }
544
545 __isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *dim,
546         enum isl_dim_type type, unsigned pos)
547 {
548         if (!dim)
549                 return NULL;
550         if (!get_id(dim, type, pos))
551                 isl_die(dim->ctx, isl_error_invalid,
552                         "dim has no id", return NULL);
553         return isl_id_copy(get_id(dim, type, pos));
554 }
555
556 __isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *dim,
557         enum isl_dim_type type, const char *s)
558 {
559         isl_id *id;
560
561         if (!dim)
562                 return NULL;
563
564         if (!s)
565                 return isl_space_reset_tuple_id(dim, type);
566
567         if (!name_ok(dim->ctx, s))
568                 goto error;
569
570         id = isl_id_alloc(dim->ctx, s, NULL);
571         return isl_space_set_tuple_id(dim, type, id);
572 error:
573         isl_space_free(dim);
574         return NULL;
575 }
576
577 /* Does the tuple have a name?
578  */
579 int isl_space_has_tuple_name(__isl_keep isl_space *space,
580         enum isl_dim_type type)
581 {
582         isl_id *id;
583
584         if (!space_can_have_id(space, type))
585                 return -1;
586         id = space->tuple_id[type - isl_dim_in];
587         return id && id->name;
588 }
589
590 const char *isl_space_get_tuple_name(__isl_keep isl_space *dim,
591          enum isl_dim_type type)
592 {
593         isl_id *id;
594         if (!dim)
595                 return NULL;
596         if (type != isl_dim_in && type != isl_dim_out)
597                 return NULL;
598         id = dim->tuple_id[type - isl_dim_in];
599         return id ? id->name : NULL;
600 }
601
602 __isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *dim,
603                                  enum isl_dim_type type, unsigned pos,
604                                  const char *s)
605 {
606         isl_id *id;
607
608         if (!dim)
609                 return NULL;
610         if (!s)
611                 return isl_space_reset_dim_id(dim, type, pos);
612         if (!name_ok(dim->ctx, s))
613                 goto error;
614         id = isl_id_alloc(dim->ctx, s, NULL);
615         return isl_space_set_dim_id(dim, type, pos, id);
616 error:
617         isl_space_free(dim);
618         return NULL;
619 }
620
621 /* Does the given dimension have a name?
622  */
623 int isl_space_has_dim_name(__isl_keep isl_space *space,
624         enum isl_dim_type type, unsigned pos)
625 {
626         isl_id *id;
627
628         if (!space)
629                 return -1;
630         id = get_id(space, type, pos);
631         return id && id->name;
632 }
633
634 __isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *dim,
635                                  enum isl_dim_type type, unsigned pos)
636 {
637         isl_id *id = get_id(dim, type, pos);
638         return id ? id->name : NULL;
639 }
640
641 int isl_space_find_dim_by_id(__isl_keep isl_space *dim, enum isl_dim_type type,
642         __isl_keep isl_id *id)
643 {
644         int i;
645         int offset;
646         int n;
647
648         if (!dim || !id)
649                 return -1;
650
651         offset = isl_space_offset(dim, type);
652         n = isl_space_dim(dim, type);
653         for (i = 0; i < n && offset + i < dim->n_id; ++i)
654                 if (dim->ids[offset + i] == id)
655                         return i;
656
657         return -1;
658 }
659
660 int isl_space_find_dim_by_name(__isl_keep isl_space *space,
661         enum isl_dim_type type, const char *name)
662 {
663         int i;
664         int offset;
665         int n;
666
667         if (!space || !name)
668                 return -1;
669
670         offset = isl_space_offset(space, type);
671         n = isl_space_dim(space, type);
672         for (i = 0; i < n && offset + i < space->n_id; ++i)
673                 if (space->ids[offset + i]->name &&
674                     !strcmp(space->ids[offset + i]->name, name))
675                         return i;
676
677         return -1;
678 }
679
680 static __isl_keep isl_id *tuple_id(__isl_keep isl_space *dim,
681         enum isl_dim_type type)
682 {
683         if (!dim)
684                 return NULL;
685         if (type == isl_dim_in)
686                 return dim->tuple_id[0];
687         if (type == isl_dim_out)
688                 return dim->tuple_id[1];
689         return NULL;
690 }
691
692 static __isl_keep isl_space *nested(__isl_keep isl_space *dim,
693         enum isl_dim_type type)
694 {
695         if (!dim)
696                 return NULL;
697         if (type == isl_dim_in)
698                 return dim->nested[0];
699         if (type == isl_dim_out)
700                 return dim->nested[1];
701         return NULL;
702 }
703
704 int isl_space_tuple_match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
705                         __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
706 {
707         isl_id *id1, *id2;
708         isl_space *nested1, *nested2;
709
710         if (!dim1 || !dim2)
711                 return -1;
712
713         if (dim1 == dim2 && dim1_type == dim2_type)
714                 return 1;
715
716         if (n(dim1, dim1_type) != n(dim2, dim2_type))
717                 return 0;
718         id1 = tuple_id(dim1, dim1_type);
719         id2 = tuple_id(dim2, dim2_type);
720         if (!id1 ^ !id2)
721                 return 0;
722         if (id1 && id1 != id2)
723                 return 0;
724         nested1 = nested(dim1, dim1_type);
725         nested2 = nested(dim2, dim2_type);
726         if (!nested1 ^ !nested2)
727                 return 0;
728         if (nested1 && !isl_space_is_equal(nested1, nested2))
729                 return 0;
730         return 1;
731 }
732
733 static int match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
734         __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
735 {
736         int i;
737
738         if (dim1 == dim2 && dim1_type == dim2_type)
739                 return 1;
740
741         if (!isl_space_tuple_match(dim1, dim1_type, dim2, dim2_type))
742                 return 0;
743
744         if (!dim1->ids && !dim2->ids)
745                 return 1;
746
747         for (i = 0; i < n(dim1, dim1_type); ++i) {
748                 if (get_id(dim1, dim1_type, i) != get_id(dim2, dim2_type, i))
749                         return 0;
750         }
751         return 1;
752 }
753
754 int isl_space_match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
755         __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
756 {
757         if (!dim1 || !dim2)
758                 return -1;
759
760         return match(dim1, dim1_type, dim2, dim2_type);
761 }
762
763 static void get_ids(__isl_keep isl_space *dim, enum isl_dim_type type,
764         unsigned first, unsigned n, __isl_keep isl_id **ids)
765 {
766         int i;
767
768         for (i = 0; i < n ; ++i)
769                 ids[i] = get_id(dim, type, first + i);
770 }
771
772 __isl_give isl_space *isl_space_extend(__isl_take isl_space *dim,
773                         unsigned nparam, unsigned n_in, unsigned n_out)
774 {
775         isl_id **ids = NULL;
776
777         if (!dim)
778                 return NULL;
779         if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
780                 return dim;
781
782         isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
783         isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
784         isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
785
786         dim = isl_space_cow(dim);
787         if (!dim)
788                 goto error;
789
790         if (dim->ids) {
791                 ids = isl_calloc_array(dim->ctx, isl_id *,
792                                          nparam + n_in + n_out);
793                 if (!ids)
794                         goto error;
795                 get_ids(dim, isl_dim_param, 0, dim->nparam, ids);
796                 get_ids(dim, isl_dim_in, 0, dim->n_in, ids + nparam);
797                 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + nparam + n_in);
798                 free(dim->ids);
799                 dim->ids = ids;
800                 dim->n_id = nparam + n_in + n_out;
801         }
802         dim->nparam = nparam;
803         dim->n_in = n_in;
804         dim->n_out = n_out;
805
806         return dim;
807 error:
808         free(ids);
809         isl_space_free(dim);
810         return NULL;
811 }
812
813 __isl_give isl_space *isl_space_add_dims(__isl_take isl_space *dim,
814         enum isl_dim_type type, unsigned n)
815 {
816         if (!dim)
817                 return NULL;
818         dim = isl_space_reset(dim, type);
819         switch (type) {
820         case isl_dim_param:
821                 dim = isl_space_extend(dim,
822                                         dim->nparam + n, dim->n_in, dim->n_out);
823                 if (dim && dim->nested[0] &&
824                     !(dim->nested[0] = isl_space_add_dims(dim->nested[0],
825                                                     isl_dim_param, n)))
826                         goto error;
827                 if (dim && dim->nested[1] &&
828                     !(dim->nested[1] = isl_space_add_dims(dim->nested[1],
829                                                     isl_dim_param, n)))
830                         goto error;
831                 return dim;
832         case isl_dim_in:
833                 return isl_space_extend(dim,
834                                         dim->nparam, dim->n_in + n, dim->n_out);
835         case isl_dim_out:
836                 return isl_space_extend(dim,
837                                         dim->nparam, dim->n_in, dim->n_out + n);
838         default:
839                 isl_die(dim->ctx, isl_error_invalid,
840                         "cannot add dimensions of specified type", goto error);
841         }
842 error:
843         isl_space_free(dim);
844         return NULL;
845 }
846
847 static int valid_dim_type(enum isl_dim_type type)
848 {
849         switch (type) {
850         case isl_dim_param:
851         case isl_dim_in:
852         case isl_dim_out:
853                 return 1;
854         default:
855                 return 0;
856         }
857 }
858
859 /* Insert "n" dimensions of type "type" at position "pos".
860  * If we are inserting parameters, then they are also inserted in
861  * any nested spaces.
862  */
863 __isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *dim,
864         enum isl_dim_type type, unsigned pos, unsigned n)
865 {
866         isl_id **ids = NULL;
867
868         if (!dim)
869                 return NULL;
870         if (n == 0)
871                 return isl_space_reset(dim, type);
872
873         if (!valid_dim_type(type))
874                 isl_die(dim->ctx, isl_error_invalid,
875                         "cannot insert dimensions of specified type",
876                         goto error);
877
878         isl_assert(dim->ctx, pos <= isl_space_dim(dim, type), goto error);
879
880         dim = isl_space_cow(dim);
881         if (!dim)
882                 return NULL;
883
884         if (dim->ids) {
885                 enum isl_dim_type t, o = isl_dim_param;
886                 int off;
887                 int s[3];
888                 ids = isl_calloc_array(dim->ctx, isl_id *,
889                                      dim->nparam + dim->n_in + dim->n_out + n);
890                 if (!ids)
891                         goto error;
892                 off = 0;
893                 s[isl_dim_param - o] = dim->nparam;
894                 s[isl_dim_in - o] = dim->n_in;
895                 s[isl_dim_out - o] = dim->n_out;
896                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
897                         if (t != type) {
898                                 get_ids(dim, t, 0, s[t - o], ids + off);
899                                 off += s[t - o];
900                         } else {
901                                 get_ids(dim, t, 0, pos, ids + off);
902                                 off += pos + n;
903                                 get_ids(dim, t, pos, s[t - o] - pos, ids + off);
904                                 off += s[t - o] - pos;
905                         }
906                 }
907                 free(dim->ids);
908                 dim->ids = ids;
909                 dim->n_id = dim->nparam + dim->n_in + dim->n_out + n;
910         }
911         switch (type) {
912         case isl_dim_param:     dim->nparam += n; break;
913         case isl_dim_in:        dim->n_in += n; break;
914         case isl_dim_out:       dim->n_out += n; break;
915         default:                ;
916         }
917         dim = isl_space_reset(dim, type);
918
919         if (type == isl_dim_param) {
920                 if (dim && dim->nested[0] &&
921                     !(dim->nested[0] = isl_space_insert_dims(dim->nested[0],
922                                                     isl_dim_param, pos, n)))
923                         goto error;
924                 if (dim && dim->nested[1] &&
925                     !(dim->nested[1] = isl_space_insert_dims(dim->nested[1],
926                                                     isl_dim_param, pos, n)))
927                         goto error;
928         }
929
930         return dim;
931 error:
932         isl_space_free(dim);
933         return NULL;
934 }
935
936 __isl_give isl_space *isl_space_move_dims(__isl_take isl_space *dim,
937         enum isl_dim_type dst_type, unsigned dst_pos,
938         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
939 {
940         int i;
941
942         if (!dim)
943                 return NULL;
944         if (n == 0)
945                 return dim;
946
947         isl_assert(dim->ctx, src_pos + n <= isl_space_dim(dim, src_type),
948                 goto error);
949
950         if (dst_type == src_type && dst_pos == src_pos)
951                 return dim;
952
953         isl_assert(dim->ctx, dst_type != src_type, goto error);
954
955         dim = isl_space_reset(dim, src_type);
956         dim = isl_space_reset(dim, dst_type);
957
958         dim = isl_space_cow(dim);
959         if (!dim)
960                 return NULL;
961
962         if (dim->ids) {
963                 isl_id **ids;
964                 enum isl_dim_type t, o = isl_dim_param;
965                 int off;
966                 int s[3];
967                 ids = isl_calloc_array(dim->ctx, isl_id *,
968                                          dim->nparam + dim->n_in + dim->n_out);
969                 if (!ids)
970                         goto error;
971                 off = 0;
972                 s[isl_dim_param - o] = dim->nparam;
973                 s[isl_dim_in - o] = dim->n_in;
974                 s[isl_dim_out - o] = dim->n_out;
975                 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
976                         if (t == dst_type) {
977                                 get_ids(dim, t, 0, dst_pos, ids + off);
978                                 off += dst_pos;
979                                 get_ids(dim, src_type, src_pos, n, ids + off);
980                                 off += n;
981                                 get_ids(dim, t, dst_pos, s[t - o] - dst_pos,
982                                                 ids + off);
983                                 off += s[t - o] - dst_pos;
984                         } else if (t == src_type) {
985                                 get_ids(dim, t, 0, src_pos, ids + off);
986                                 off += src_pos;
987                                 get_ids(dim, t, src_pos + n,
988                                             s[t - o] - src_pos - n, ids + off);
989                                 off += s[t - o] - src_pos - n;
990                         } else {
991                                 get_ids(dim, t, 0, s[t - o], ids + off);
992                                 off += s[t - o];
993                         }
994                 }
995                 free(dim->ids);
996                 dim->ids = ids;
997                 dim->n_id = dim->nparam + dim->n_in + dim->n_out;
998         }
999
1000         switch (dst_type) {
1001         case isl_dim_param:     dim->nparam += n; break;
1002         case isl_dim_in:        dim->n_in += n; break;
1003         case isl_dim_out:       dim->n_out += n; break;
1004         default:                ;
1005         }
1006
1007         switch (src_type) {
1008         case isl_dim_param:     dim->nparam -= n; break;
1009         case isl_dim_in:        dim->n_in -= n; break;
1010         case isl_dim_out:       dim->n_out -= n; break;
1011         default:                ;
1012         }
1013
1014         if (dst_type != isl_dim_param && src_type != isl_dim_param)
1015                 return dim;
1016
1017         for (i = 0; i < 2; ++i) {
1018                 if (!dim->nested[i])
1019                         continue;
1020                 dim->nested[i] = isl_space_replace(dim->nested[i],
1021                                                  isl_dim_param, dim);
1022                 if (!dim->nested[i])
1023                         goto error;
1024         }
1025
1026         return dim;
1027 error:
1028         isl_space_free(dim);
1029         return NULL;
1030 }
1031
1032 __isl_give isl_space *isl_space_join(__isl_take isl_space *left,
1033         __isl_take isl_space *right)
1034 {
1035         isl_space *dim;
1036
1037         if (!left || !right)
1038                 goto error;
1039
1040         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
1041                         goto error);
1042         isl_assert(left->ctx,
1043                 isl_space_tuple_match(left, isl_dim_out, right, isl_dim_in),
1044                 goto error);
1045
1046         dim = isl_space_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
1047         if (!dim)
1048                 goto error;
1049
1050         dim = copy_ids(dim, isl_dim_param, 0, left, isl_dim_param);
1051         dim = copy_ids(dim, isl_dim_in, 0, left, isl_dim_in);
1052         dim = copy_ids(dim, isl_dim_out, 0, right, isl_dim_out);
1053
1054         if (dim && left->tuple_id[0] &&
1055             !(dim->tuple_id[0] = isl_id_copy(left->tuple_id[0])))
1056                 goto error;
1057         if (dim && right->tuple_id[1] &&
1058             !(dim->tuple_id[1] = isl_id_copy(right->tuple_id[1])))
1059                 goto error;
1060         if (dim && left->nested[0] &&
1061             !(dim->nested[0] = isl_space_copy(left->nested[0])))
1062                 goto error;
1063         if (dim && right->nested[1] &&
1064             !(dim->nested[1] = isl_space_copy(right->nested[1])))
1065                 goto error;
1066
1067         isl_space_free(left);
1068         isl_space_free(right);
1069
1070         return dim;
1071 error:
1072         isl_space_free(left);
1073         isl_space_free(right);
1074         return NULL;
1075 }
1076
1077 __isl_give isl_space *isl_space_product(__isl_take isl_space *left,
1078         __isl_take isl_space *right)
1079 {
1080         isl_space *dom1, *dom2, *nest1, *nest2;
1081
1082         if (!left || !right)
1083                 goto error;
1084
1085         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
1086                         goto error);
1087
1088         dom1 = isl_space_domain(isl_space_copy(left));
1089         dom2 = isl_space_domain(isl_space_copy(right));
1090         nest1 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1091
1092         dom1 = isl_space_range(left);
1093         dom2 = isl_space_range(right);
1094         nest2 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1095
1096         return isl_space_join(isl_space_reverse(nest1), nest2);
1097 error:
1098         isl_space_free(left);
1099         isl_space_free(right);
1100         return NULL;
1101 }
1102
1103 /* Given two spaces { A -> C } and { B -> C }, construct the space
1104  * { [A -> B] -> C }
1105  */
1106 __isl_give isl_space *isl_space_domain_product(__isl_take isl_space *left,
1107         __isl_take isl_space *right)
1108 {
1109         isl_space *ran, *dom1, *dom2, *nest;
1110
1111         if (!left || !right)
1112                 goto error;
1113
1114         if (!match(left, isl_dim_param, right, isl_dim_param))
1115                 isl_die(left->ctx, isl_error_invalid,
1116                         "parameters need to match", goto error);
1117         if (!isl_space_tuple_match(left, isl_dim_out, right, isl_dim_out))
1118                 isl_die(left->ctx, isl_error_invalid,
1119                         "ranges need to match", goto error);
1120
1121         ran = isl_space_range(isl_space_copy(left));
1122
1123         dom1 = isl_space_domain(left);
1124         dom2 = isl_space_domain(right);
1125         nest = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1126
1127         return isl_space_join(isl_space_reverse(nest), ran);
1128 error:
1129         isl_space_free(left);
1130         isl_space_free(right);
1131         return NULL;
1132 }
1133
1134 __isl_give isl_space *isl_space_range_product(__isl_take isl_space *left,
1135         __isl_take isl_space *right)
1136 {
1137         isl_space *dom, *ran1, *ran2, *nest;
1138
1139         if (!left || !right)
1140                 goto error;
1141
1142         isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
1143                         goto error);
1144         if (!isl_space_tuple_match(left, isl_dim_in, right, isl_dim_in))
1145                 isl_die(left->ctx, isl_error_invalid,
1146                         "domains need to match", goto error);
1147
1148         dom = isl_space_domain(isl_space_copy(left));
1149
1150         ran1 = isl_space_range(left);
1151         ran2 = isl_space_range(right);
1152         nest = isl_space_wrap(isl_space_join(isl_space_reverse(ran1), ran2));
1153
1154         return isl_space_join(isl_space_reverse(dom), nest);
1155 error:
1156         isl_space_free(left);
1157         isl_space_free(right);
1158         return NULL;
1159 }
1160
1161 __isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *dim)
1162 {
1163         isl_ctx *ctx;
1164         isl_id **ids = NULL;
1165
1166         if (!dim)
1167                 return NULL;
1168         ctx = isl_space_get_ctx(dim);
1169         if (!isl_space_is_set(dim))
1170                 isl_die(ctx, isl_error_invalid, "not a set space", goto error);
1171         dim = isl_space_cow(dim);
1172         if (!dim)
1173                 return NULL;
1174         if (dim->ids) {
1175                 ids = isl_calloc_array(dim->ctx, isl_id *,
1176                                         dim->nparam + dim->n_out + dim->n_out);
1177                 if (!ids)
1178                         goto error;
1179                 get_ids(dim, isl_dim_param, 0, dim->nparam, ids);
1180                 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->nparam);
1181         }
1182         dim->n_in = dim->n_out;
1183         if (ids) {
1184                 free(dim->ids);
1185                 dim->ids = ids;
1186                 dim->n_id = dim->nparam + dim->n_out + dim->n_out;
1187                 dim = copy_ids(dim, isl_dim_out, 0, dim, isl_dim_in);
1188         }
1189         isl_id_free(dim->tuple_id[0]);
1190         dim->tuple_id[0] = isl_id_copy(dim->tuple_id[1]);
1191         isl_space_free(dim->nested[0]);
1192         dim->nested[0] = isl_space_copy(dim->nested[1]);
1193         return dim;
1194 error:
1195         isl_space_free(dim);
1196         return NULL;
1197 }
1198
1199 __isl_give isl_space *isl_space_map_from_domain_and_range(
1200         __isl_take isl_space *domain, __isl_take isl_space *range)
1201 {
1202         if (!domain || !range)
1203                 goto error;
1204         if (!isl_space_is_set(domain))
1205                 isl_die(isl_space_get_ctx(domain), isl_error_invalid,
1206                         "domain is not a set space", goto error);
1207         if (!isl_space_is_set(range))
1208                 isl_die(isl_space_get_ctx(range), isl_error_invalid,
1209                         "range is not a set space", goto error);
1210         return isl_space_join(isl_space_reverse(domain), range);
1211 error:
1212         isl_space_free(domain);
1213         isl_space_free(range);
1214         return NULL;
1215 }
1216
1217 static __isl_give isl_space *set_ids(__isl_take isl_space *dim,
1218         enum isl_dim_type type,
1219         unsigned first, unsigned n, __isl_take isl_id **ids)
1220 {
1221         int i;
1222
1223         for (i = 0; i < n ; ++i)
1224                 dim = set_id(dim, type, first + i, ids[i]);
1225
1226         return dim;
1227 }
1228
1229 __isl_give isl_space *isl_space_reverse(__isl_take isl_space *dim)
1230 {
1231         unsigned t;
1232         isl_space *nested;
1233         isl_id **ids = NULL;
1234         isl_id *id;
1235
1236         if (!dim)
1237                 return NULL;
1238         if (match(dim, isl_dim_in, dim, isl_dim_out))
1239                 return dim;
1240
1241         dim = isl_space_cow(dim);
1242         if (!dim)
1243                 return NULL;
1244
1245         id = dim->tuple_id[0];
1246         dim->tuple_id[0] = dim->tuple_id[1];
1247         dim->tuple_id[1] = id;
1248
1249         nested = dim->nested[0];
1250         dim->nested[0] = dim->nested[1];
1251         dim->nested[1] = nested;
1252
1253         if (dim->ids) {
1254                 ids = isl_alloc_array(dim->ctx, isl_id *,
1255                                         dim->n_in + dim->n_out);
1256                 if (!ids)
1257                         goto error;
1258                 get_ids(dim, isl_dim_in, 0, dim->n_in, ids);
1259                 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->n_in);
1260         }
1261
1262         t = dim->n_in;
1263         dim->n_in = dim->n_out;
1264         dim->n_out = t;
1265
1266         if (dim->ids) {
1267                 dim = set_ids(dim, isl_dim_out, 0, dim->n_out, ids);
1268                 dim = set_ids(dim, isl_dim_in, 0, dim->n_in, ids + dim->n_out);
1269                 free(ids);
1270         }
1271
1272         return dim;
1273 error:
1274         free(ids);
1275         isl_space_free(dim);
1276         return NULL;
1277 }
1278
1279 __isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *dim,
1280         enum isl_dim_type type, unsigned first, unsigned num)
1281 {
1282         int i;
1283
1284         if (!dim)
1285                 return NULL;
1286
1287         if (num == 0)
1288                 return isl_space_reset(dim, type);
1289
1290         if (!valid_dim_type(type))
1291                 isl_die(dim->ctx, isl_error_invalid,
1292                         "cannot drop dimensions of specified type", goto error);
1293
1294         isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
1295         dim = isl_space_cow(dim);
1296         if (!dim)
1297                 goto error;
1298         if (dim->ids) {
1299                 dim = extend_ids(dim);
1300                 if (!dim)
1301                         goto error;
1302                 for (i = 0; i < num; ++i)
1303                         isl_id_free(get_id(dim, type, first + i));
1304                 for (i = first+num; i < n(dim, type); ++i)
1305                         set_id(dim, type, i - num, get_id(dim, type, i));
1306                 switch (type) {
1307                 case isl_dim_param:
1308                         get_ids(dim, isl_dim_in, 0, dim->n_in,
1309                                 dim->ids + offset(dim, isl_dim_in) - num);
1310                 case isl_dim_in:
1311                         get_ids(dim, isl_dim_out, 0, dim->n_out,
1312                                 dim->ids + offset(dim, isl_dim_out) - num);
1313                 default:
1314                         ;
1315                 }
1316                 dim->n_id -= num;
1317         }
1318         switch (type) {
1319         case isl_dim_param:     dim->nparam -= num; break;
1320         case isl_dim_in:        dim->n_in -= num; break;
1321         case isl_dim_out:       dim->n_out -= num; break;
1322         default:                ;
1323         }
1324         dim = isl_space_reset(dim, type);
1325         if (type == isl_dim_param) {
1326                 if (dim && dim->nested[0] &&
1327                     !(dim->nested[0] = isl_space_drop_dims(dim->nested[0],
1328                                                     isl_dim_param, first, num)))
1329                         goto error;
1330                 if (dim && dim->nested[1] &&
1331                     !(dim->nested[1] = isl_space_drop_dims(dim->nested[1],
1332                                                     isl_dim_param, first, num)))
1333                         goto error;
1334         }
1335         return dim;
1336 error:
1337         isl_space_free(dim);
1338         return NULL;
1339 }
1340
1341 __isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *dim,
1342                 unsigned first, unsigned n)
1343 {
1344         if (!dim)
1345                 return NULL;
1346         return isl_space_drop_dims(dim, isl_dim_in, first, n);
1347 }
1348
1349 __isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *dim,
1350                 unsigned first, unsigned n)
1351 {
1352         if (!dim)
1353                 return NULL;
1354         return isl_space_drop_dims(dim, isl_dim_out, first, n);
1355 }
1356
1357 __isl_give isl_space *isl_space_domain(__isl_take isl_space *dim)
1358 {
1359         if (!dim)
1360                 return NULL;
1361         dim = isl_space_drop_outputs(dim, 0, dim->n_out);
1362         dim = isl_space_reverse(dim);
1363         dim = mark_as_set(dim);
1364         return dim;
1365 }
1366
1367 __isl_give isl_space *isl_space_from_domain(__isl_take isl_space *dim)
1368 {
1369         if (!dim)
1370                 return NULL;
1371         if (!isl_space_is_set(dim))
1372                 isl_die(isl_space_get_ctx(dim), isl_error_invalid,
1373                         "not a set space", goto error);
1374         dim = isl_space_reverse(dim);
1375         dim = isl_space_reset(dim, isl_dim_out);
1376         return dim;
1377 error:
1378         isl_space_free(dim);
1379         return NULL;
1380 }
1381
1382 __isl_give isl_space *isl_space_range(__isl_take isl_space *dim)
1383 {
1384         if (!dim)
1385                 return NULL;
1386         dim = isl_space_drop_inputs(dim, 0, dim->n_in);
1387         dim = mark_as_set(dim);
1388         return dim;
1389 }
1390
1391 __isl_give isl_space *isl_space_from_range(__isl_take isl_space *dim)
1392 {
1393         if (!dim)
1394                 return NULL;
1395         if (!isl_space_is_set(dim))
1396                 isl_die(isl_space_get_ctx(dim), isl_error_invalid,
1397                         "not a set space", goto error);
1398         return isl_space_reset(dim, isl_dim_in);
1399 error:
1400         isl_space_free(dim);
1401         return NULL;
1402 }
1403
1404 __isl_give isl_space *isl_space_params(__isl_take isl_space *space)
1405 {
1406         if (isl_space_is_params(space))
1407                 return space;
1408         space = isl_space_drop_dims(space,
1409                             isl_dim_in, 0, isl_space_dim(space, isl_dim_in));
1410         space = isl_space_drop_dims(space,
1411                             isl_dim_out, 0, isl_space_dim(space, isl_dim_out));
1412         space = mark_as_params(space);
1413         return space;
1414 }
1415
1416 __isl_give isl_space *isl_space_set_from_params(__isl_take isl_space *space)
1417 {
1418         if (!space)
1419                 return NULL;
1420         if (!isl_space_is_params(space))
1421                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1422                         "not a parameter space", goto error);
1423         return isl_space_reset(space, isl_dim_set);
1424 error:
1425         isl_space_free(space);
1426         return NULL;
1427 }
1428
1429 __isl_give isl_space *isl_space_as_set_space(__isl_take isl_space *dim)
1430 {
1431         dim = isl_space_cow(dim);
1432         if (!dim)
1433                 return NULL;
1434
1435         dim->n_out += dim->n_in;
1436         dim->n_in = 0;
1437         dim = isl_space_reset(dim, isl_dim_in);
1438         dim = isl_space_reset(dim, isl_dim_out);
1439
1440         return dim;
1441 }
1442
1443 __isl_give isl_space *isl_space_underlying(__isl_take isl_space *dim,
1444         unsigned n_div)
1445 {
1446         int i;
1447
1448         if (!dim)
1449                 return NULL;
1450         if (n_div == 0 &&
1451             dim->nparam == 0 && dim->n_in == 0 && dim->n_id == 0)
1452                 return isl_space_reset(isl_space_reset(dim, isl_dim_in), isl_dim_out);
1453         dim = isl_space_cow(dim);
1454         if (!dim)
1455                 return NULL;
1456         dim->n_out += dim->nparam + dim->n_in + n_div;
1457         dim->nparam = 0;
1458         dim->n_in = 0;
1459
1460         for (i = 0; i < dim->n_id; ++i)
1461                 isl_id_free(get_id(dim, isl_dim_out, i));
1462         dim->n_id = 0;
1463         dim = isl_space_reset(dim, isl_dim_in);
1464         dim = isl_space_reset(dim, isl_dim_out);
1465
1466         return dim;
1467 }
1468
1469 /* Are the two spaces the same, including positions and names of parameters?
1470  */
1471 int isl_space_is_equal(__isl_keep isl_space *dim1, __isl_keep isl_space *dim2)
1472 {
1473         if (!dim1 || !dim2)
1474                 return -1;
1475         if (dim1 == dim2)
1476                 return 1;
1477         return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
1478                isl_space_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
1479                isl_space_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
1480 }
1481
1482 /* Is space1 equal to the domain of space2?
1483  *
1484  * In the internal version we also allow space2 to be the space of a set,
1485  * provided space1 is a parameter space.
1486  */
1487 int isl_space_is_domain_internal(__isl_keep isl_space *space1,
1488         __isl_keep isl_space *space2)
1489 {
1490         if (!space1 || !space2)
1491                 return -1;
1492         if (!isl_space_is_set(space1))
1493                 return 0;
1494         return match(space1, isl_dim_param, space2, isl_dim_param) &&
1495                isl_space_tuple_match(space1, isl_dim_set, space2, isl_dim_in);
1496 }
1497
1498 /* Is space1 equal to the domain of space2?
1499  */
1500 int isl_space_is_domain(__isl_keep isl_space *space1,
1501         __isl_keep isl_space *space2)
1502 {
1503         if (!space2)
1504                 return -1;
1505         if (!isl_space_is_map(space2))
1506                 return 0;
1507         return isl_space_is_domain_internal(space1, space2);
1508 }
1509
1510 /* Is space1 equal to the range of space2?
1511  *
1512  * In the internal version, space2 is allowed to be the space of a set,
1513  * in which case it should be equal to space1.
1514  */
1515 int isl_space_is_range_internal(__isl_keep isl_space *space1,
1516         __isl_keep isl_space *space2)
1517 {
1518         if (!space1 || !space2)
1519                 return -1;
1520         if (!isl_space_is_set(space1))
1521                 return 0;
1522         return match(space1, isl_dim_param, space2, isl_dim_param) &&
1523                isl_space_tuple_match(space1, isl_dim_set, space2, isl_dim_out);
1524 }
1525
1526 /* Is space1 equal to the range of space2?
1527  */
1528 int isl_space_is_range(__isl_keep isl_space *space1,
1529         __isl_keep isl_space *space2)
1530 {
1531         if (!space2)
1532                 return -1;
1533         if (!isl_space_is_map(space2))
1534                 return 0;
1535         return isl_space_is_range_internal(space1, space2);
1536 }
1537
1538 int isl_space_compatible(__isl_keep isl_space *dim1,
1539         __isl_keep isl_space *dim2)
1540 {
1541         return dim1->nparam == dim2->nparam &&
1542                dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
1543 }
1544
1545 static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_space *dim)
1546 {
1547         int i;
1548         isl_id *id;
1549
1550         if (!dim)
1551                 return hash;
1552
1553         isl_hash_byte(hash, dim->nparam % 256);
1554         isl_hash_byte(hash, dim->n_in % 256);
1555         isl_hash_byte(hash, dim->n_out % 256);
1556
1557         for (i = 0; i < dim->nparam; ++i) {
1558                 id = get_id(dim, isl_dim_param, i);
1559                 hash = isl_hash_id(hash, id);
1560         }
1561
1562         id = tuple_id(dim, isl_dim_in);
1563         hash = isl_hash_id(hash, id);
1564         id = tuple_id(dim, isl_dim_out);
1565         hash = isl_hash_id(hash, id);
1566
1567         hash = isl_hash_dim(hash, dim->nested[0]);
1568         hash = isl_hash_dim(hash, dim->nested[1]);
1569
1570         return hash;
1571 }
1572
1573 uint32_t isl_space_get_hash(__isl_keep isl_space *dim)
1574 {
1575         uint32_t hash;
1576
1577         if (!dim)
1578                 return 0;
1579
1580         hash = isl_hash_init();
1581         hash = isl_hash_dim(hash, dim);
1582
1583         return hash;
1584 }
1585
1586 int isl_space_is_wrapping(__isl_keep isl_space *dim)
1587 {
1588         if (!dim)
1589                 return -1;
1590
1591         if (!isl_space_is_set(dim))
1592                 return 0;
1593
1594         return dim->nested[1] != NULL;
1595 }
1596
1597 __isl_give isl_space *isl_space_wrap(__isl_take isl_space *dim)
1598 {
1599         isl_space *wrap;
1600
1601         if (!dim)
1602                 return NULL;
1603
1604         wrap = isl_space_set_alloc(dim->ctx,
1605                                     dim->nparam, dim->n_in + dim->n_out);
1606
1607         wrap = copy_ids(wrap, isl_dim_param, 0, dim, isl_dim_param);
1608         wrap = copy_ids(wrap, isl_dim_set, 0, dim, isl_dim_in);
1609         wrap = copy_ids(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
1610
1611         if (!wrap)
1612                 goto error;
1613
1614         wrap->nested[1] = dim;
1615
1616         return wrap;
1617 error:
1618         isl_space_free(dim);
1619         return NULL;
1620 }
1621
1622 __isl_give isl_space *isl_space_unwrap(__isl_take isl_space *dim)
1623 {
1624         isl_space *unwrap;
1625
1626         if (!dim)
1627                 return NULL;
1628
1629         if (!isl_space_is_wrapping(dim))
1630                 isl_die(dim->ctx, isl_error_invalid, "not a wrapping space",
1631                         goto error);
1632
1633         unwrap = isl_space_copy(dim->nested[1]);
1634         isl_space_free(dim);
1635
1636         return unwrap;
1637 error:
1638         isl_space_free(dim);
1639         return NULL;
1640 }
1641
1642 int isl_space_is_named_or_nested(__isl_keep isl_space *dim, enum isl_dim_type type)
1643 {
1644         if (type != isl_dim_in && type != isl_dim_out)
1645                 return 0;
1646         if (!dim)
1647                 return -1;
1648         if (dim->tuple_id[type - isl_dim_in])
1649                 return 1;
1650         if (dim->nested[type - isl_dim_in])
1651                 return 1;
1652         return 0;
1653 }
1654
1655 int isl_space_may_be_set(__isl_keep isl_space *dim)
1656 {
1657         if (!dim)
1658                 return -1;
1659         if (isl_space_is_set(dim))
1660                 return 1;
1661         if (isl_space_dim(dim, isl_dim_in) != 0)
1662                 return 0;
1663         if (isl_space_is_named_or_nested(dim, isl_dim_in))
1664                 return 0;
1665         return 1;
1666 }
1667
1668 __isl_give isl_space *isl_space_reset(__isl_take isl_space *dim,
1669         enum isl_dim_type type)
1670 {
1671         if (!isl_space_is_named_or_nested(dim, type))
1672                 return dim;
1673
1674         dim = isl_space_cow(dim);
1675         if (!dim)
1676                 return NULL;
1677
1678         isl_id_free(dim->tuple_id[type - isl_dim_in]);
1679         dim->tuple_id[type - isl_dim_in] = NULL;
1680         isl_space_free(dim->nested[type - isl_dim_in]);
1681         dim->nested[type - isl_dim_in] = NULL;
1682
1683         return dim;
1684 }
1685
1686 __isl_give isl_space *isl_space_flatten(__isl_take isl_space *dim)
1687 {
1688         if (!dim)
1689                 return NULL;
1690         if (!dim->nested[0] && !dim->nested[1])
1691                 return dim;
1692
1693         if (dim->nested[0])
1694                 dim = isl_space_reset(dim, isl_dim_in);
1695         if (dim && dim->nested[1])
1696                 dim = isl_space_reset(dim, isl_dim_out);
1697
1698         return dim;
1699 }
1700
1701 __isl_give isl_space *isl_space_flatten_domain(__isl_take isl_space *dim)
1702 {
1703         if (!dim)
1704                 return NULL;
1705         if (!dim->nested[0])
1706                 return dim;
1707
1708         return isl_space_reset(dim, isl_dim_in);
1709 }
1710
1711 __isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *dim)
1712 {
1713         if (!dim)
1714                 return NULL;
1715         if (!dim->nested[1])
1716                 return dim;
1717
1718         return isl_space_reset(dim, isl_dim_out);
1719 }
1720
1721 /* Replace the dimensions of the given type of dst by those of src.
1722  */
1723 __isl_give isl_space *isl_space_replace(__isl_take isl_space *dst,
1724         enum isl_dim_type type, __isl_keep isl_space *src)
1725 {
1726         dst = isl_space_cow(dst);
1727
1728         if (!dst || !src)
1729                 goto error;
1730
1731         dst = isl_space_drop_dims(dst, type, 0, isl_space_dim(dst, type));
1732         dst = isl_space_add_dims(dst, type, isl_space_dim(src, type));
1733         dst = copy_ids(dst, type, 0, src, type);
1734
1735         if (dst && type == isl_dim_param) {
1736                 int i;
1737                 for (i = 0; i <= 1; ++i) {
1738                         if (!dst->nested[i])
1739                                 continue;
1740                         dst->nested[i] = isl_space_replace(dst->nested[i],
1741                                                          type, src);
1742                         if (!dst->nested[i])
1743                                 goto error;
1744                 }
1745         }
1746
1747         return dst;
1748 error:
1749         isl_space_free(dst);
1750         return NULL;
1751 }
1752
1753 /* Given a dimension specification "dim" of a set, create a dimension
1754  * specification for the lift of the set.  In particular, the result
1755  * is of the form [dim -> local[..]], with n_local variables in the
1756  * range of the wrapped map.
1757  */
1758 __isl_give isl_space *isl_space_lift(__isl_take isl_space *dim, unsigned n_local)
1759 {
1760         isl_space *local_dim;
1761
1762         if (!dim)
1763                 return NULL;
1764
1765         local_dim = isl_space_dup(dim);
1766         local_dim = isl_space_drop_dims(local_dim, isl_dim_set, 0, dim->n_out);
1767         local_dim = isl_space_add_dims(local_dim, isl_dim_set, n_local);
1768         local_dim = isl_space_set_tuple_name(local_dim, isl_dim_set, "local");
1769         dim = isl_space_join(isl_space_from_domain(dim),
1770                             isl_space_from_range(local_dim));
1771         dim = isl_space_wrap(dim);
1772         dim = isl_space_set_tuple_name(dim, isl_dim_set, "lifted");
1773
1774         return dim;
1775 }
1776
1777 int isl_space_can_zip(__isl_keep isl_space *dim)
1778 {
1779         if (!dim)
1780                 return -1;
1781
1782         return dim->nested[0] && dim->nested[1];
1783 }
1784
1785 __isl_give isl_space *isl_space_zip(__isl_take isl_space *dim)
1786 {
1787         isl_space *dom, *ran;
1788         isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran;
1789
1790         if (!isl_space_can_zip(dim))
1791                 isl_die(dim->ctx, isl_error_invalid, "dim cannot be zipped",
1792                         goto error);
1793
1794         if (!dim)
1795                 return NULL;
1796         dom = isl_space_unwrap(isl_space_domain(isl_space_copy(dim)));
1797         ran = isl_space_unwrap(isl_space_range(dim));
1798         dom_dom = isl_space_domain(isl_space_copy(dom));
1799         dom_ran = isl_space_range(dom);
1800         ran_dom = isl_space_domain(isl_space_copy(ran));
1801         ran_ran = isl_space_range(ran);
1802         dom = isl_space_join(isl_space_from_domain(dom_dom),
1803                            isl_space_from_range(ran_dom));
1804         ran = isl_space_join(isl_space_from_domain(dom_ran),
1805                            isl_space_from_range(ran_ran));
1806         return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
1807                             isl_space_from_range(isl_space_wrap(ran)));
1808 error:
1809         isl_space_free(dim);
1810         return NULL;
1811 }
1812
1813 /* Can we apply isl_space_curry to "space"?
1814  * That is, does it have a nested relation in its domain?
1815  */
1816 int isl_space_can_curry(__isl_keep isl_space *space)
1817 {
1818         if (!space)
1819                 return -1;
1820
1821         return !!space->nested[0];
1822 }
1823
1824 /* Given a space (A -> B) -> C, return the corresponding space
1825  * A -> (B -> C).
1826  */
1827 __isl_give isl_space *isl_space_curry(__isl_take isl_space *space)
1828 {
1829         isl_space *dom, *ran;
1830         isl_space *dom_dom, *dom_ran;
1831
1832         if (!space)
1833                 return NULL;
1834
1835         if (!isl_space_can_curry(space))
1836                 isl_die(space->ctx, isl_error_invalid,
1837                         "space cannot be curried", goto error);
1838
1839         dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));
1840         ran = isl_space_range(space);
1841         dom_dom = isl_space_domain(isl_space_copy(dom));
1842         dom_ran = isl_space_range(dom);
1843         ran = isl_space_join(isl_space_from_domain(dom_ran),
1844                            isl_space_from_range(ran));
1845         return isl_space_join(isl_space_from_domain(dom_dom),
1846                             isl_space_from_range(isl_space_wrap(ran)));
1847 error:
1848         isl_space_free(space);
1849         return NULL;
1850 }
1851
1852 /* Can we apply isl_space_uncurry to "space"?
1853  * That is, does it have a nested relation in its range?
1854  */
1855 int isl_space_can_uncurry(__isl_keep isl_space *space)
1856 {
1857         if (!space)
1858                 return -1;
1859
1860         return !!space->nested[1];
1861 }
1862
1863 /* Given a space A -> (B -> C), return the corresponding space
1864  * (A -> B) -> C.
1865  */
1866 __isl_give isl_space *isl_space_uncurry(__isl_take isl_space *space)
1867 {
1868         isl_space *dom, *ran;
1869         isl_space *ran_dom, *ran_ran;
1870
1871         if (!space)
1872                 return NULL;
1873
1874         if (!isl_space_can_uncurry(space))
1875                 isl_die(space->ctx, isl_error_invalid,
1876                         "space cannot be uncurried",
1877                         return isl_space_free(space));
1878
1879         dom = isl_space_domain(isl_space_copy(space));
1880         ran = isl_space_unwrap(isl_space_range(space));
1881         ran_dom = isl_space_domain(isl_space_copy(ran));
1882         ran_ran = isl_space_range(ran);
1883         dom = isl_space_join(isl_space_from_domain(dom),
1884                            isl_space_from_range(ran_dom));
1885         return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
1886                             isl_space_from_range(ran_ran));
1887 }
1888
1889 int isl_space_has_named_params(__isl_keep isl_space *dim)
1890 {
1891         int i;
1892         unsigned off;
1893
1894         if (!dim)
1895                 return -1;
1896         if (dim->nparam == 0)
1897                 return 1;
1898         off = isl_space_offset(dim, isl_dim_param);
1899         if (off + dim->nparam > dim->n_id)
1900                 return 0;
1901         for (i = 0; i < dim->nparam; ++i)
1902                 if (!dim->ids[off + i])
1903                         return 0;
1904         return 1;
1905 }
1906
1907 /* Align the initial parameters of dim1 to match the order in dim2.
1908  */
1909 __isl_give isl_space *isl_space_align_params(__isl_take isl_space *dim1,
1910         __isl_take isl_space *dim2)
1911 {
1912         isl_reordering *exp;
1913
1914         if (!isl_space_has_named_params(dim1) || !isl_space_has_named_params(dim2))
1915                 isl_die(isl_space_get_ctx(dim1), isl_error_invalid,
1916                         "parameter alignment requires named parameters",
1917                         goto error);
1918
1919         dim2 = isl_space_params(dim2);
1920         exp = isl_parameter_alignment_reordering(dim1, dim2);
1921         exp = isl_reordering_extend_space(exp, dim1);
1922         isl_space_free(dim2);
1923         if (!exp)
1924                 return NULL;
1925         dim1 = isl_space_copy(exp->dim);
1926         isl_reordering_free(exp);
1927         return dim1;
1928 error:
1929         isl_space_free(dim1);
1930         isl_space_free(dim2);
1931         return NULL;
1932 }
1933
1934 /* Given the space of set (domain), construct a space for a map
1935  * with as domain the given space and as range the range of "model".
1936  */
1937 __isl_give isl_space *isl_space_extend_domain_with_range(
1938         __isl_take isl_space *space, __isl_take isl_space *model)
1939 {
1940         if (!model)
1941                 goto error;
1942
1943         space = isl_space_from_domain(space);
1944         space = isl_space_add_dims(space, isl_dim_out,
1945                                     isl_space_dim(model, isl_dim_out));
1946         if (isl_space_has_tuple_id(model, isl_dim_out))
1947                 space = isl_space_set_tuple_id(space, isl_dim_out,
1948                                 isl_space_get_tuple_id(model, isl_dim_out));
1949         if (!space)
1950                 goto error;
1951         if (model->nested[1]) {
1952                 isl_space *nested = isl_space_copy(model->nested[1]);
1953                 int n_nested, n_space;
1954                 nested = isl_space_align_params(nested, isl_space_copy(space));
1955                 n_nested = isl_space_dim(nested, isl_dim_param);
1956                 n_space = isl_space_dim(space, isl_dim_param);
1957                 if (n_nested > n_space)
1958                         nested = isl_space_drop_dims(nested, isl_dim_param,
1959                                                 n_space, n_nested - n_space);
1960                 if (!nested)
1961                         goto error;
1962                 space->nested[1] = nested;
1963         }
1964         isl_space_free(model);
1965         return space;
1966 error:
1967         isl_space_free(model);
1968         isl_space_free(space);
1969         return NULL;
1970 }