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