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