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