isl_space.c

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