isl_input.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 <ctype.h>
  14 #include <stdio.h>
  15 #include <string.h>
  16 #include <strings.h>
  17 #include <isl_ctx_private.h>
  18 #include <isl_map_private.h>
  19 #include <isl/set.h>
  20 #include <isl/seq.h>
  21 #include <isl/div.h>
  22 #include <isl/stream.h>
  23 #include <isl/obj.h>
  24 #include "isl_polynomial_private.h"
  25 #include <isl/union_map.h>
  26 #include <isl_mat_private.h>
  27
  28 struct variable {
  29         char                    *name;
  30         int                      pos;
  31         isl_vec                 *def;
  32         /* non-zero if variable represents a min (-1) or a max (1) */
  33         int                      sign;
  34         isl_mat                 *list;
  35         struct variable         *next;
  36 };
  37
  38 struct vars {
  39         struct isl_ctx  *ctx;
  40         int              n;
  41         struct variable *v;
  42 };
  43
  44 static struct vars *vars_new(struct isl_ctx *ctx)
  45 {
  46         struct vars *v;
  47         v = isl_alloc_type(ctx, struct vars);
  48         if (!v)
  49                 return NULL;
  50         v->ctx = ctx;
  51         v->n = 0;
  52         v->v = NULL;
  53         return v;
  54 }
  55
  56 static void variable_free(struct variable *var)
  57 {
  58         while (var) {
  59                 struct variable *next = var->next;
  60                 isl_mat_free(var->list);
  61                 isl_vec_free(var->def);
  62                 free(var->name);
  63                 free(var);
  64                 var = next;
  65         }
  66 }
  67
  68 static void vars_free(struct vars *v)
  69 {
  70         if (!v)
  71                 return;
  72         variable_free(v->v);
  73         free(v);
  74 }
  75
  76 static void vars_drop(struct vars *v, int n)
  77 {
  78         struct variable *var;
  79
  80         if (!v || !v->v)
  81                 return;
  82
  83         v->n -= n;
  84
  85         var = v->v;
  86         while (--n >= 0) {
  87                 struct variable *next = var->next;
  88                 isl_mat_free(var->list);
  89                 isl_vec_free(var->def);
  90                 free(var->name);
  91                 free(var);
  92                 var = next;
  93         }
  94         v->v = var;
  95 }
  96
  97 static struct variable *variable_new(struct vars *v, const char *name, int len,
  98                                 int pos)
  99 {
 100         struct variable *var;
 101         var = isl_calloc_type(v->ctx, struct variable);
 102         if (!var)
 103                 goto error;
 104         var->name = strdup(name);
 105         var->name[len] = '\0';
 106         var->pos = pos;
 107         var->def = NULL;
 108         var->next = v->v;
 109         return var;
 110 error:
 111         variable_free(v->v);
 112         return NULL;
 113 }
 114
 115 static int vars_pos(struct vars *v, const char *s, int len)
 116 {
 117         int pos;
 118         struct variable *q;
 119
 120         if (len == -1)
 121                 len = strlen(s);
 122         for (q = v->v; q; q = q->next) {
 123                 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
 124                         break;
 125         }
 126         if (q)
 127                 pos = q->pos;
 128         else {
 129                 pos = v->n;
 130                 v->v = variable_new(v, s, len, v->n);
 131                 if (!v->v)
 132                         return -1;
 133                 v->n++;
 134         }
 135         return pos;
 136 }
 137
 138 static int vars_add_anon(struct vars *v)
 139 {
 140         v->v = variable_new(v, "", 0, v->n);
 141
 142         if (!v->v)
 143                 return -1;
 144         v->n++;
 145
 146         return 0;
 147 }
 148
 149 static __isl_give isl_basic_map *set_name(__isl_take isl_basic_map *bmap,
 150         enum isl_dim_type type, unsigned pos, char *name)
 151 {
 152         char *prime;
 153
 154         if (!bmap)
 155                 return NULL;
 156         if (!name)
 157                 return bmap;
 158
 159         prime = strchr(name, '\'');
 160         if (prime)
 161                 *prime = '\0';
 162         bmap = isl_basic_map_set_dim_name(bmap, type, pos, name);
 163         if (prime)
 164                 *prime = '\'';
 165
 166         return bmap;
 167 }
 168
 169 /* Obtain next token, with some preprocessing.
 170  * In particular, evaluate expressions of the form x^y,
 171  * with x and y values.
 172  */
 173 static struct isl_token *next_token(struct isl_stream *s)
 174 {
 175         struct isl_token *tok, *tok2;
 176
 177         tok = isl_stream_next_token(s);
 178         if (!tok || tok->type != ISL_TOKEN_VALUE)
 179                 return tok;
 180         if (!isl_stream_eat_if_available(s, '^'))
 181                 return tok;
 182         tok2 = isl_stream_next_token(s);
 183         if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
 184                 isl_stream_error(s, tok2, "expecting constant value");
 185                 goto error;
 186         }
 187
 188         isl_int_pow_ui(tok->u.v, tok->u.v, isl_int_get_ui(tok2->u.v));
 189
 190         isl_token_free(tok2);
 191         return tok;
 192 error:
 193         isl_token_free(tok);
 194         isl_token_free(tok2);
 195         return NULL;
 196 }
 197
 198 static int accept_cst_factor(struct isl_stream *s, isl_int *f)
 199 {
 200         struct isl_token *tok;
 201
 202         tok = next_token(s);
 203         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 204                 isl_stream_error(s, tok, "expecting constant value");
 205                 goto error;
 206         }
 207
 208         isl_int_mul(*f, *f, tok->u.v);
 209
 210         isl_token_free(tok);
 211
 212         if (isl_stream_eat_if_available(s, '*'))
 213                 return accept_cst_factor(s, f);
 214
 215         return 0;
 216 error:
 217         isl_token_free(tok);
 218         return -1;
 219 }
 220
 221 /* Given an affine expression aff, return an affine expression
 222  * for aff % d, with d the next token on the stream, which is
 223  * assumed to be a constant.
 224  *
 225  * We introduce an integer division q = [aff/d] and the result
 226  * is set to aff - d q.
 227  */
 228 static __isl_give isl_vec *affine_mod(struct isl_stream *s,
 229         struct vars *v, __isl_take isl_vec *aff)
 230 {
 231         struct isl_token *tok;
 232         struct variable *var;
 233         isl_vec *mod;
 234
 235         tok = next_token(s);
 236         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 237                 isl_stream_error(s, tok, "expecting constant value");
 238                 goto error;
 239         }
 240
 241         if (vars_add_anon(v) < 0)
 242                 goto error;
 243
 244         var = v->v;
 245
 246         var->def = isl_vec_alloc(s->ctx, 2 + v->n);
 247         if (!var->def)
 248                 goto error;
 249         isl_seq_cpy(var->def->el + 1, aff->el, aff->size);
 250         isl_int_set_si(var->def->el[1 + aff->size], 0);
 251         isl_int_set(var->def->el[0], tok->u.v);
 252
 253         mod = isl_vec_alloc(v->ctx, 1 + v->n);
 254         if (!mod)
 255                 goto error;
 256
 257         isl_seq_cpy(mod->el, aff->el, aff->size);
 258         isl_int_neg(mod->el[aff->size], tok->u.v);
 259
 260         isl_vec_free(aff);
 261         isl_token_free(tok);
 262         return mod;
 263 error:
 264         isl_vec_free(aff);
 265         isl_token_free(tok);
 266         return NULL;
 267 }
 268
 269 static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v);
 270 static int read_div_definition(struct isl_stream *s, struct vars *v);
 271 static int read_minmax_definition(struct isl_stream *s, struct vars *v);
 272
 273 static __isl_give isl_vec *accept_affine_factor(struct isl_stream *s,
 274         struct vars *v)
 275 {
 276         struct isl_token *tok = NULL;
 277         isl_vec *aff = NULL;
 278
 279         tok = next_token(s);
 280         if (!tok) {
 281                 isl_stream_error(s, NULL, "unexpected EOF");
 282                 goto error;
 283         }
 284         if (tok->type == ISL_TOKEN_IDENT) {
 285                 int n = v->n;
 286                 int pos = vars_pos(v, tok->u.s, -1);
 287                 if (pos < 0)
 288                         goto error;
 289                 if (pos >= n) {
 290                         isl_stream_error(s, tok, "unknown identifier");
 291                         goto error;
 292                 }
 293
 294                 aff = isl_vec_alloc(v->ctx, 1 + v->n);
 295                 if (!aff)
 296                         goto error;
 297                 isl_seq_clr(aff->el, aff->size);
 298                 isl_int_set_si(aff->el[1 + pos], 1);
 299                 isl_token_free(tok);
 300         } else if (tok->type == ISL_TOKEN_VALUE) {
 301                 if (isl_stream_eat_if_available(s, '*')) {
 302                         aff = accept_affine_factor(s, v);
 303                         aff = isl_vec_scale(aff, tok->u.v);
 304                 } else {
 305                         aff = isl_vec_alloc(v->ctx, 1 + v->n);
 306                         if (!aff)
 307                                 goto error;
 308                         isl_seq_clr(aff->el, aff->size);
 309                         isl_int_set(aff->el[0], tok->u.v);
 310                 }
 311                 isl_token_free(tok);
 312         } else if (tok->type == '(') {
 313                 isl_token_free(tok);
 314                 tok = NULL;
 315                 aff = accept_affine(s, v);
 316                 if (!aff)
 317                         goto error;
 318                 if (isl_stream_eat(s, ')'))
 319                         goto error;
 320         } else if (tok->type == '[' ||
 321                     tok->type == ISL_TOKEN_FLOORD ||
 322                     tok->type == ISL_TOKEN_CEILD) {
 323                 int ceil = tok->type == ISL_TOKEN_CEILD;
 324                 struct variable *var;
 325                 if (vars_add_anon(v) < 0)
 326                         goto error;
 327                 var = v->v;
 328                 aff = isl_vec_alloc(v->ctx, 1 + v->n);
 329                 if (!aff)
 330                         goto error;
 331                 isl_seq_clr(aff->el, aff->size);
 332                 isl_int_set_si(aff->el[1 + v->n - 1], ceil ? -1 : 1);
 333                 isl_stream_push_token(s, tok);
 334                 tok = NULL;
 335                 if (read_div_definition(s, v) < 0)
 336                         goto error;
 337                 if (ceil)
 338                         isl_seq_neg(var->def->el + 1, var->def->el + 1,
 339                                     var->def->size - 1);
 340                 aff = isl_vec_zero_extend(aff, 1 + v->n);
 341         } else if (tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX) {
 342                 if (vars_add_anon(v) < 0)
 343                         goto error;
 344                 aff = isl_vec_alloc(v->ctx, 1 + v->n);
 345                 if (!aff)
 346                         goto error;
 347                 isl_seq_clr(aff->el, aff->size);
 348                 isl_int_set_si(aff->el[1 + v->n - 1], 1);
 349                 isl_stream_push_token(s, tok);
 350                 tok = NULL;
 351                 if (read_minmax_definition(s, v) < 0)
 352                         goto error;
 353                 aff = isl_vec_zero_extend(aff, 1 + v->n);
 354         } else {
 355                 isl_stream_error(s, tok, "expecting factor");
 356                 goto error;
 357         }
 358         if (isl_stream_eat_if_available(s, '%'))
 359                 return affine_mod(s, v, aff);
 360         if (isl_stream_eat_if_available(s, '*')) {
 361                 isl_int f;
 362                 isl_int_init(f);
 363                 isl_int_set_si(f, 1);
 364                 if (accept_cst_factor(s, &f) < 0) {
 365                         isl_int_clear(f);
 366                         goto error2;
 367                 }
 368                 aff = isl_vec_scale(aff, f);
 369                 isl_int_clear(f);
 370         }
 371
 372         return aff;
 373 error:
 374         isl_token_free(tok);
 375 error2:
 376         isl_vec_free(aff);
 377         return NULL;
 378 }
 379
 380 static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v)
 381 {
 382         struct isl_token *tok = NULL;
 383         struct isl_vec *aff;
 384         int sign = 1;
 385
 386         aff = isl_vec_alloc(v->ctx, 1 + v->n);
 387         if (!aff)
 388                 return NULL;
 389         isl_seq_clr(aff->el, aff->size);
 390
 391         for (;;) {
 392                 tok = next_token(s);
 393                 if (!tok) {
 394                         isl_stream_error(s, NULL, "unexpected EOF");
 395                         goto error;
 396                 }
 397                 if (tok->type == '-') {
 398                         sign = -sign;
 399                         isl_token_free(tok);
 400                         continue;
 401                 }
 402                 if (tok->type == '(' || tok->type == '[' ||
 403                     tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX ||
 404                     tok->type == ISL_TOKEN_FLOORD ||
 405                     tok->type == ISL_TOKEN_CEILD ||
 406                     tok->type == ISL_TOKEN_IDENT) {
 407                         isl_vec *aff2;
 408                         isl_stream_push_token(s, tok);
 409                         tok = NULL;
 410                         aff2 = accept_affine_factor(s, v);
 411                         if (sign < 0)
 412                                 aff2 = isl_vec_scale(aff2, s->ctx->negone);
 413                         aff = isl_vec_zero_extend(aff, 1 + v->n);
 414                         aff = isl_vec_add(aff, aff2);
 415                         if (!aff)
 416                                 goto error;
 417                         sign = 1;
 418                 } else if (tok->type == ISL_TOKEN_VALUE) {
 419                         if (sign < 0)
 420                                 isl_int_neg(tok->u.v, tok->u.v);
 421                         if (isl_stream_eat_if_available(s, '*') ||
 422                             isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
 423                                 isl_vec *aff2;
 424                                 aff2 = accept_affine_factor(s, v);
 425                                 aff2 = isl_vec_scale(aff2, tok->u.v);
 426                                 aff = isl_vec_zero_extend(aff, 1 + v->n);
 427                                 aff = isl_vec_add(aff, aff2);
 428                                 if (!aff)
 429                                         goto error;
 430                         } else {
 431                                 isl_int_add(aff->el[0], aff->el[0], tok->u.v);
 432                         }
 433                         sign = 1;
 434                 } else {
 435                         isl_stream_error(s, tok, "unexpected isl_token");
 436                         isl_stream_push_token(s, tok);
 437                         isl_vec_free(aff);
 438                         return NULL;
 439                 }
 440                 isl_token_free(tok);
 441
 442                 tok = next_token(s);
 443                 if (tok && tok->type == '-') {
 444                         sign = -sign;
 445                         isl_token_free(tok);
 446                 } else if (tok && tok->type == '+') {
 447                         /* nothing */
 448                         isl_token_free(tok);
 449                 } else if (tok && tok->type == ISL_TOKEN_VALUE &&
 450                            isl_int_is_neg(tok->u.v)) {
 451                         isl_stream_push_token(s, tok);
 452                 } else {
 453                         if (tok)
 454                                 isl_stream_push_token(s, tok);
 455                         break;
 456                 }
 457         }
 458
 459         return aff;
 460 error:
 461         isl_token_free(tok);
 462         isl_vec_free(aff);
 463         return NULL;
 464 }
 465
 466 /* Add any variables in the variable list "v" that are not already in "bmap"
 467  * as existentially quantified variables in "bmap".
 468  */
 469 static __isl_give isl_basic_map *add_divs(__isl_take isl_basic_map *bmap,
 470         struct vars *v)
 471 {
 472         int i;
 473         int extra;
 474         struct variable *var;
 475
 476         extra = v->n - isl_basic_map_total_dim(bmap);
 477
 478         if (extra == 0)
 479                 return bmap;
 480
 481         bmap = isl_basic_map_extend_dim(bmap, isl_basic_map_get_dim(bmap),
 482                                         extra, 0, 2 * extra);
 483
 484         for (i = 0; i < extra; ++i)
 485                 if (isl_basic_map_alloc_div(bmap) < 0)
 486                         goto error;
 487
 488         for (i = 0, var = v->v; i < extra; ++i, var = var->next) {
 489                 int k = bmap->n_div - 1 - i;
 490
 491                 isl_seq_cpy(bmap->div[k], var->def->el, var->def->size);
 492                 isl_seq_clr(bmap->div[k] + var->def->size,
 493                             2 + v->n - var->def->size);
 494
 495                 if (isl_basic_map_add_div_constraints(bmap, k) < 0)
 496                         goto error;
 497         }
 498
 499         return bmap;
 500 error:
 501         isl_basic_map_free(bmap);
 502         return NULL;
 503 }
 504
 505 static __isl_give isl_basic_map *read_var_def(struct isl_stream *s,
 506         __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
 507 {
 508         isl_dim *dim;
 509         isl_basic_map *def = NULL;
 510         struct isl_vec *vec;
 511         int k;
 512         int n;
 513
 514         if (vars_add_anon(v) < 0)
 515                 goto error;
 516         n = v->n;
 517
 518         vec = accept_affine(s, v);
 519         if (!vec)
 520                 goto error;
 521
 522         dim = isl_basic_map_get_dim(bmap);
 523         def = isl_basic_map_universe(dim);
 524         def = add_divs(def, v);
 525         def = isl_basic_map_extend_constraints(def, 1, 0);
 526         k = isl_basic_map_alloc_equality(def);
 527         if (k >= 0) {
 528                 isl_seq_cpy(def->eq[k], vec->el, vec->size);
 529                 isl_int_set_si(def->eq[k][1 + n - 1], -1);
 530         }
 531         isl_vec_free(vec);
 532         if (k < 0)
 533                 goto error;
 534
 535         vars_drop(v, v->n - n);
 536
 537         def = isl_basic_map_simplify(def);
 538         def = isl_basic_map_finalize(def);
 539         bmap = isl_basic_map_intersect(bmap, def);
 540         return bmap;
 541 error:
 542         isl_basic_map_free(bmap);
 543         isl_basic_map_free(def);
 544         return NULL;
 545 }
 546
 547 static __isl_give isl_basic_map *read_var_list(struct isl_stream *s,
 548         __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
 549 {
 550         int i = 0;
 551         struct isl_token *tok;
 552
 553         while ((tok = next_token(s)) != NULL) {
 554                 int new_name = 0;
 555
 556                 if (tok->type == ISL_TOKEN_IDENT) {
 557                         int n = v->n;
 558                         int p = vars_pos(v, tok->u.s, -1);
 559                         if (p < 0)
 560                                 goto error;
 561                         new_name = p >= n;
 562                 }
 563
 564                 if (new_name) {
 565                         bmap = isl_basic_map_add(bmap, type, 1);
 566                         bmap = set_name(bmap, type, i, v->v->name);
 567                         isl_token_free(tok);
 568                 } else if (tok->type == ISL_TOKEN_IDENT ||
 569                            tok->type == ISL_TOKEN_VALUE ||
 570                            tok->type == '-' ||
 571                            tok->type == '(') {
 572                         if (type == isl_dim_param) {
 573                                 isl_stream_error(s, tok,
 574                                                 "expecting unique identifier");
 575                                 goto error;
 576                         }
 577                         isl_stream_push_token(s, tok);
 578                         tok = NULL;
 579                         bmap = isl_basic_map_add(bmap, type, 1);
 580                         bmap = read_var_def(s, bmap, type, v);
 581                 } else
 582                         break;
 583
 584                 tok = isl_stream_next_token(s);
 585                 if (!tok || tok->type != ',')
 586                         break;
 587
 588                 isl_token_free(tok);
 589                 i++;
 590         }
 591         if (tok)
 592                 isl_stream_push_token(s, tok);
 593
 594         return bmap;
 595 error:
 596         isl_token_free(tok);
 597         isl_basic_map_free(bmap);
 598         return NULL;
 599 }
 600
 601 static __isl_give isl_mat *accept_affine_list(struct isl_stream *s,
 602         struct vars *v)
 603 {
 604         struct isl_vec *vec;
 605         struct isl_mat *mat;
 606         struct isl_token *tok = NULL;
 607
 608         vec = accept_affine(s, v);
 609         mat = isl_mat_from_row_vec(vec);
 610         if (!mat)
 611                 return NULL;
 612
 613         for (;;) {
 614                 tok = isl_stream_next_token(s);
 615                 if (!tok) {
 616                         isl_stream_error(s, NULL, "unexpected EOF");
 617                         goto error;
 618                 }
 619                 if (tok->type != ',') {
 620                         isl_stream_push_token(s, tok);
 621                         break;
 622                 }
 623                 isl_token_free(tok);
 624
 625                 vec = accept_affine(s, v);
 626                 mat = isl_mat_add_zero_cols(mat, 1 + v->n - isl_mat_cols(mat));
 627                 mat = isl_mat_vec_concat(mat, vec);
 628                 if (!mat)
 629                         return NULL;
 630         }
 631
 632         return mat;
 633 error:
 634         isl_mat_free(mat);
 635         return NULL;
 636 }
 637
 638 static int read_minmax_definition(struct isl_stream *s, struct vars *v)
 639 {
 640         struct isl_token *tok;
 641         struct variable *var;
 642
 643         var = v->v;
 644
 645         tok = isl_stream_next_token(s);
 646         if (!tok)
 647                 return -1;
 648         var->sign = tok->type == ISL_TOKEN_MIN ? -1 : 1;
 649         isl_token_free(tok);
 650
 651         if (isl_stream_eat(s, '('))
 652                 return -1;
 653
 654         var->list = accept_affine_list(s, v);
 655         if (!var->list)
 656                 return -1;
 657
 658         if (isl_stream_eat(s, ')'))
 659                 return -1;
 660
 661         return 0;
 662 }
 663
 664 static int read_div_definition(struct isl_stream *s, struct vars *v)
 665 {
 666         struct isl_token *tok;
 667         int seen_paren = 0;
 668         struct isl_vec *aff;
 669         struct variable *var;
 670         int fc = 0;
 671
 672         if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD) ||
 673             isl_stream_eat_if_available(s, ISL_TOKEN_CEILD)) {
 674                 fc = 1;
 675                 if (isl_stream_eat(s, '('))
 676                         return -1;
 677         } else {
 678                 if (isl_stream_eat(s, '['))
 679                         return -1;
 680                 if (isl_stream_eat_if_available(s, '('))
 681                         seen_paren = 1;
 682         }
 683
 684         var = v->v;
 685
 686         aff = accept_affine(s, v);
 687         if (!aff)
 688                 return -1;
 689
 690         var->def = isl_vec_alloc(s->ctx, 2 + v->n);
 691         if (!var->def) {
 692                 isl_vec_free(aff);
 693                 return -1;
 694         }
 695
 696         isl_seq_cpy(var->def->el + 1, aff->el, aff->size);
 697
 698         isl_vec_free(aff);
 699
 700         if (fc) {
 701                 if (isl_stream_eat(s, ','))
 702                         return -1;
 703         } else {
 704                 if (seen_paren && isl_stream_eat(s, ')'))
 705                         return -1;
 706                 if (isl_stream_eat(s, '/'))
 707                         return -1;
 708         }
 709
 710         tok = next_token(s);
 711         if (!tok)
 712                 return -1;
 713         if (tok->type != ISL_TOKEN_VALUE) {
 714                 isl_stream_error(s, tok, "expected denominator");
 715                 isl_stream_push_token(s, tok);
 716                 return -1;
 717         }
 718         isl_int_set(var->def->el[0], tok->u.v);
 719         isl_token_free(tok);
 720
 721         if (fc) {
 722                 if (isl_stream_eat(s, ')'))
 723                         return -1;
 724         } else {
 725                 if (isl_stream_eat(s, ']'))
 726                         return -1;
 727         }
 728
 729         return 0;
 730 }
 731
 732 static struct isl_basic_map *add_div_definition(struct isl_stream *s,
 733         struct vars *v, struct isl_basic_map *bmap, int pos)
 734 {
 735         struct variable *var = v->v;
 736         unsigned o_out = isl_basic_map_offset(bmap, isl_dim_out) - 1;
 737
 738         if (read_div_definition(s, v) < 0)
 739                 goto error;
 740
 741         if (isl_basic_map_add_div_constraints_var(bmap, o_out + pos,
 742                                                   var->def->el) < 0)
 743                 goto error;
 744
 745         return bmap;
 746 error:
 747         isl_basic_map_free(bmap);
 748         return NULL;
 749 }
 750
 751 static struct isl_basic_map *read_defined_var_list(struct isl_stream *s,
 752         struct vars *v, struct isl_basic_map *bmap)
 753 {
 754         struct isl_token *tok;
 755
 756         while ((tok = isl_stream_next_token(s)) != NULL) {
 757                 int p;
 758                 int n = v->n;
 759                 unsigned n_out = isl_basic_map_dim(bmap, isl_dim_out);
 760
 761                 if (tok->type != ISL_TOKEN_IDENT)
 762                         break;
 763
 764                 p = vars_pos(v, tok->u.s, -1);
 765                 if (p < 0)
 766                         goto error;
 767                 if (p < n) {
 768                         isl_stream_error(s, tok, "expecting unique identifier");
 769                         goto error;
 770                 }
 771
 772                 bmap = isl_basic_map_cow(bmap);
 773                 bmap = isl_basic_map_add(bmap, isl_dim_out, 1);
 774                 bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
 775                                                 0, 0, 2);
 776
 777                 isl_token_free(tok);
 778                 tok = isl_stream_next_token(s);
 779                 if (tok && tok->type == '=') {
 780                         isl_token_free(tok);
 781                         bmap = add_div_definition(s, v, bmap, n_out);
 782                         tok = isl_stream_next_token(s);
 783                 }
 784
 785                 if (!tok || tok->type != ',')
 786                         break;
 787
 788                 isl_token_free(tok);
 789         }
 790         if (tok)
 791                 isl_stream_push_token(s, tok);
 792
 793         return bmap;
 794 error:
 795         isl_token_free(tok);
 796         isl_basic_map_free(bmap);
 797         return NULL;
 798 }
 799
 800 static int next_is_tuple(struct isl_stream *s)
 801 {
 802         struct isl_token *tok;
 803         int is_tuple;
 804
 805         tok = isl_stream_next_token(s);
 806         if (!tok)
 807                 return 0;
 808         if (tok->type == '[') {
 809                 isl_stream_push_token(s, tok);
 810                 return 1;
 811         }
 812         if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) {
 813                 isl_stream_push_token(s, tok);
 814                 return 0;
 815         }
 816
 817         is_tuple = isl_stream_next_token_is(s, '[');
 818
 819         isl_stream_push_token(s, tok);
 820
 821         return is_tuple;
 822 }
 823
 824 static __isl_give isl_basic_map *read_tuple(struct isl_stream *s,
 825         __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v);
 826
 827 static __isl_give isl_basic_map *read_nested_tuple(struct isl_stream *s,
 828         __isl_take isl_basic_map *bmap, struct vars *v)
 829 {
 830         bmap = read_tuple(s, bmap, isl_dim_in, v);
 831         if (isl_stream_eat(s, ISL_TOKEN_TO))
 832                 goto error;
 833         bmap = read_tuple(s, bmap, isl_dim_out, v);
 834         bmap = isl_basic_map_from_range(isl_basic_map_wrap(bmap));
 835         return bmap;
 836 error:
 837         isl_basic_map_free(bmap);
 838         return NULL;
 839 }
 840
 841 static __isl_give isl_basic_map *read_tuple(struct isl_stream *s,
 842         __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
 843 {
 844         struct isl_token *tok;
 845         char *name = NULL;
 846
 847         tok = isl_stream_next_token(s);
 848         if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
 849                 name = strdup(tok->u.s);
 850                 if (!name)
 851                         goto error;
 852                 isl_token_free(tok);
 853                 tok = isl_stream_next_token(s);
 854         }
 855         if (!tok || tok->type != '[') {
 856                 isl_stream_error(s, tok, "expecting '['");
 857                 goto error;
 858         }
 859         isl_token_free(tok);
 860         if (type != isl_dim_param && next_is_tuple(s)) {
 861                 isl_dim *dim = isl_basic_map_get_dim(bmap);
 862                 int nparam = isl_dim_size(dim, isl_dim_param);
 863                 int n_in = isl_dim_size(dim, isl_dim_in);
 864                 isl_basic_map *nested;
 865                 if (type == isl_dim_out)
 866                         dim = isl_dim_move(dim, isl_dim_param, nparam,
 867                                                 isl_dim_in, 0, n_in);
 868                 nested = isl_basic_map_alloc_dim(dim, 0, 0, 0);
 869                 nested = read_nested_tuple(s, nested, v);
 870                 if (type == isl_dim_in) {
 871                         nested = isl_basic_map_reverse(nested);
 872                         bmap = isl_basic_map_intersect(nested, bmap);
 873                 } else {
 874                         isl_basic_set *bset;
 875                         dim = isl_dim_range(isl_basic_map_get_dim(nested));
 876                         dim = isl_dim_drop(dim, isl_dim_param, nparam, n_in);
 877                         dim = isl_dim_join(isl_basic_map_get_dim(bmap), dim);
 878                         bset = isl_basic_map_domain(bmap);
 879                         nested = isl_basic_map_reset_dim(nested, dim);
 880                         bmap = isl_basic_map_intersect_domain(nested, bset);
 881                 }
 882         } else
 883                 bmap = read_var_list(s, bmap, type, v);
 884         tok = isl_stream_next_token(s);
 885         if (!tok || tok->type != ']') {
 886                 isl_stream_error(s, tok, "expecting ']'");
 887                 goto error;
 888         }
 889         isl_token_free(tok);
 890
 891         if (name) {
 892                 bmap = isl_basic_map_set_tuple_name(bmap, type, name);
 893                 free(name);
 894         }
 895
 896         return bmap;
 897 error:
 898         if (tok)
 899                 isl_token_free(tok);
 900         isl_basic_map_free(bmap);
 901         return NULL;
 902 }
 903
 904 static __isl_give isl_basic_map *construct_constraint(
 905         __isl_take isl_basic_map *bmap, enum isl_token_type type,
 906         isl_int *left, isl_int *right)
 907 {
 908         int k;
 909         unsigned len;
 910         struct isl_ctx *ctx;
 911
 912         if (!bmap)
 913                 return NULL;
 914         len = 1 + isl_basic_map_total_dim(bmap);
 915         ctx = bmap->ctx;
 916
 917         k = isl_basic_map_alloc_inequality(bmap);
 918         if (k < 0)
 919                 goto error;
 920         if (type == ISL_TOKEN_LE)
 921                 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
 922                                                ctx->one, right,
 923                                                len);
 924         else if (type == ISL_TOKEN_GE)
 925                 isl_seq_combine(bmap->ineq[k], ctx->one, left,
 926                                                ctx->negone, right,
 927                                                len);
 928         else if (type == ISL_TOKEN_LT) {
 929                 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
 930                                                ctx->one, right,
 931                                                len);
 932                 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
 933         } else if (type == ISL_TOKEN_GT) {
 934                 isl_seq_combine(bmap->ineq[k], ctx->one, left,
 935                                                ctx->negone, right,
 936                                                len);
 937                 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
 938         } else {
 939                 isl_seq_combine(bmap->ineq[k], ctx->one, left,
 940                                                ctx->negone, right,
 941                                                len);
 942                 isl_basic_map_inequality_to_equality(bmap, k);
 943         }
 944
 945         return bmap;
 946 error:
 947         isl_basic_map_free(bmap);
 948         return NULL;
 949 }
 950
 951 static int is_comparator(struct isl_token *tok)
 952 {
 953         if (!tok)
 954                 return 0;
 955
 956         switch (tok->type) {
 957         case ISL_TOKEN_LT:
 958         case ISL_TOKEN_GT:
 959         case ISL_TOKEN_LE:
 960         case ISL_TOKEN_GE:
 961         case '=':
 962                 return 1;
 963         default:
 964                 return 0;
 965         }
 966 }
 967
 968 /* Add any variables in the variable list "v" that are not already in "bmap"
 969  * as output variables in "bmap".
 970  */
 971 static __isl_give isl_basic_map *add_lifted_divs(__isl_take isl_basic_map *bmap,
 972         struct vars *v)
 973 {
 974         int i;
 975         int extra;
 976         struct variable *var;
 977
 978         extra = v->n - isl_basic_map_total_dim(bmap);
 979
 980         if (extra == 0)
 981                 return bmap;
 982
 983         bmap = isl_basic_map_add(bmap, isl_dim_out, extra);
 984         bmap = isl_basic_map_extend_dim(bmap, isl_basic_map_get_dim(bmap),
 985                                         0, 0, 2 * extra);
 986
 987         for (i = 0, var = v->v; i < extra; ++i, var = var->next) {
 988                 if (!var->def)
 989                         continue;
 990                 var->def = isl_vec_zero_extend(var->def, 2 + v->n);
 991                 if (!var->def)
 992                         goto error;
 993                 if (isl_basic_map_add_div_constraints_var(bmap, var->pos,
 994                                                           var->def->el) < 0)
 995                         goto error;
 996         }
 997
 998         return bmap;
 999 error:
1000         isl_basic_map_free(bmap);
1001         return NULL;
1002 }
1003
1004 static struct isl_basic_map *add_constraint(struct isl_stream *s,
1005         struct vars *v, struct isl_basic_map *bmap)
1006 {
1007         int i, j;
1008         struct isl_token *tok = NULL;
1009         struct isl_mat *aff1 = NULL, *aff2 = NULL;
1010
1011         bmap = isl_basic_map_cow(bmap);
1012
1013         aff1 = accept_affine_list(s, v);
1014         if (!aff1)
1015                 goto error;
1016         tok = isl_stream_next_token(s);
1017         if (!is_comparator(tok)) {
1018                 isl_stream_error(s, tok, "missing operator");
1019                 if (tok)
1020                         isl_stream_push_token(s, tok);
1021                 tok = NULL;
1022                 goto error;
1023         }
1024         for (;;) {
1025                 aff2 = accept_affine_list(s, v);
1026                 if (!aff2)
1027                         goto error;
1028
1029                 aff1 = isl_mat_add_zero_cols(aff1, aff2->n_col - aff1->n_col);
1030                 if (!aff1)
1031                         goto error;
1032                 bmap = add_lifted_divs(bmap, v);
1033                 bmap = isl_basic_map_extend_constraints(bmap, 0,
1034                                                 aff1->n_row * aff2->n_row);
1035                 for (i = 0; i < aff1->n_row; ++i)
1036                         for (j = 0; j < aff2->n_row; ++j)
1037                                 bmap = construct_constraint(bmap, tok->type,
1038                                                     aff1->row[i], aff2->row[j]);
1039                 isl_token_free(tok);
1040                 isl_mat_free(aff1);
1041                 aff1 = aff2;
1042
1043                 tok = isl_stream_next_token(s);
1044                 if (!is_comparator(tok)) {
1045                         if (tok)
1046                                 isl_stream_push_token(s, tok);
1047                         break;
1048                 }
1049         }
1050         isl_mat_free(aff1);
1051
1052         return bmap;
1053 error:
1054         if (tok)
1055                 isl_token_free(tok);
1056         isl_mat_free(aff1);
1057         isl_mat_free(aff2);
1058         isl_basic_map_free(bmap);
1059         return NULL;
1060 }
1061
1062 /* Return first variable, starting at n, representing a min or max,
1063  * or NULL if there is no such variable.
1064  */
1065 static struct variable *first_minmax(struct vars *v, int n)
1066 {
1067         struct variable *first = NULL;
1068         struct variable *var;
1069
1070         for (var = v->v; var && var->pos >= n; var = var->next)
1071                 if (var->list)
1072                         first = var;
1073
1074         return first;
1075 }
1076
1077 /* Check whether the variable at the given position only occurs in
1078  * inequalities and only with the given sign.
1079  */
1080 static int all_coefficients_of_sign(__isl_keep isl_map *map, int pos, int sign)
1081 {
1082         int i, j;
1083
1084         if (!map)
1085                 return -1;
1086
1087         for (i = 0; i < map->n; ++i) {
1088                 isl_basic_map *bmap = map->p[i];
1089
1090                 for (j = 0; j < bmap->n_eq; ++j)
1091                         if (!isl_int_is_zero(bmap->eq[j][1 + pos]))
1092                                 return 0;
1093                 for (j = 0; j < bmap->n_ineq; ++j) {
1094                         int s = isl_int_sgn(bmap->ineq[j][1 + pos]);
1095                         if (s == 0)
1096                                 continue;
1097                         if (s != sign)
1098                                 return 0;
1099                 }
1100         }
1101
1102         return 1;
1103 }
1104
1105 /* Given a variable m which represents a min or a max of n expressions
1106  * b_i, add the constraints
1107  *
1108  *      m <= b_i
1109  *
1110  * in case of a min (var->sign < 0) and m >= b_i in case of a max.
1111  */
1112 static __isl_give isl_map *bound_minmax(__isl_take isl_map *map,
1113         struct variable *var)
1114 {
1115         int i, k;
1116         isl_basic_map *bound;
1117         int total;
1118
1119         total = isl_map_dim(map, isl_dim_all);
1120         bound = isl_basic_map_alloc_dim(isl_map_get_dim(map),
1121                                         0, 0, var->list->n_row);
1122
1123         for (i = 0; i < var->list->n_row; ++i) {
1124                 k = isl_basic_map_alloc_inequality(bound);
1125                 if (k < 0)
1126                         goto error;
1127                 if (var->sign < 0)
1128                         isl_seq_cpy(bound->ineq[k], var->list->row[i],
1129                                     var->list->n_col);
1130                 else
1131                         isl_seq_neg(bound->ineq[k], var->list->row[i],
1132                                     var->list->n_col);
1133                 isl_int_set_si(bound->ineq[k][1 + var->pos], var->sign);
1134                 isl_seq_clr(bound->ineq[k] + var->list->n_col,
1135                             1 + total - var->list->n_col);
1136         }
1137
1138         map = isl_map_intersect(map, isl_map_from_basic_map(bound));
1139
1140         return map;
1141 error:
1142         isl_basic_map_free(bound);
1143         isl_map_free(map);
1144         return NULL;
1145 }
1146
1147 /* Given a variable m which represents a min (or max) of n expressions
1148  * b_i, add constraints that assigns the minimal upper bound to m, i.e.,
1149  * divide the space into cells where one
1150  * of the upper bounds is smaller than all the others and assign
1151  * this upper bound to m.
1152  *
1153  * In particular, if there are n bounds b_i, then the input map
1154  * is split into n pieces, each with the extra constraints
1155  *
1156  *      m = b_i
1157  *      b_i <= b_j      for j > i
1158  *      b_i <  b_j      for j < i
1159  *
1160  * in case of a min (var->sign < 0) and similarly in case of a max.
1161  *
1162  * Note: this function is very similar to set_minimum in isl_tab_pip.c
1163  * Perhaps we should try to merge the two.
1164  */
1165 static __isl_give isl_map *set_minmax(__isl_take isl_map *map,
1166         struct variable *var)
1167 {
1168         int i, j, k;
1169         isl_basic_map *bmap = NULL;
1170         isl_ctx *ctx;
1171         isl_map *split = NULL;
1172         int total;
1173
1174         ctx = isl_map_get_ctx(map);
1175         total = isl_map_dim(map, isl_dim_all);
1176         split = isl_map_alloc_dim(isl_map_get_dim(map),
1177                                 var->list->n_row, ISL_SET_DISJOINT);
1178
1179         for (i = 0; i < var->list->n_row; ++i) {
1180                 bmap = isl_basic_map_alloc_dim(isl_map_get_dim(map), 0,
1181                                                1, var->list->n_row - 1);
1182                 k = isl_basic_map_alloc_equality(bmap);
1183                 if (k < 0)
1184                         goto error;
1185                 isl_seq_cpy(bmap->eq[k], var->list->row[i], var->list->n_col);
1186                 isl_int_set_si(bmap->eq[k][1 + var->pos], -1);
1187                 for (j = 0; j < var->list->n_row; ++j) {
1188                         if (j == i)
1189                                 continue;
1190                         k = isl_basic_map_alloc_inequality(bmap);
1191                         if (k < 0)
1192                                 goto error;
1193                         if (var->sign < 0)
1194                                 isl_seq_combine(bmap->ineq[k],
1195                                                 ctx->one, var->list->row[j],
1196                                                 ctx->negone, var->list->row[i],
1197                                                 var->list->n_col);
1198                         else
1199                                 isl_seq_combine(bmap->ineq[k],
1200                                                 ctx->negone, var->list->row[j],
1201                                                 ctx->one, var->list->row[i],
1202                                                 var->list->n_col);
1203                         isl_seq_clr(bmap->ineq[k] + var->list->n_col,
1204                                     1 + total - var->list->n_col);
1205                         if (j < i)
1206                                 isl_int_sub_ui(bmap->ineq[k][0],
1207                                                bmap->ineq[k][0], 1);
1208                 }
1209                 bmap = isl_basic_map_finalize(bmap);
1210                 split = isl_map_add_basic_map(split, bmap);
1211         }
1212
1213         map = isl_map_intersect(map, split);
1214
1215         return map;
1216 error:
1217         isl_basic_map_free(bmap);
1218         isl_map_free(split);
1219         isl_map_free(map);
1220         return NULL;
1221 }
1222
1223 /* Plug in the definitions of all min and max expressions.
1224  * If a min expression only appears in inequalities and only
1225  * with a positive coefficient, then we can simply bound
1226  * the variable representing the min by its defining terms
1227  * and similarly for a max expression.
1228  * Otherwise, we have to assign the different terms to the
1229  * variable under the condition that the assigned term is smaller
1230  * than the other terms.
1231  */
1232 static __isl_give isl_map *add_minmax(__isl_take isl_map *map,
1233         struct vars *v, int n)
1234 {
1235         int i;
1236         struct variable *var;
1237
1238         while (n < v->n) {
1239                 var = first_minmax(v, n);
1240                 if (!var)
1241                         break;
1242                 if (all_coefficients_of_sign(map, var->pos, -var->sign))
1243                         map = bound_minmax(map, var);
1244                 else
1245                         map = set_minmax(map, var);
1246                 n = var->pos + 1;
1247         }
1248
1249         return map;
1250 }
1251
1252 static isl_map *read_constraint(struct isl_stream *s,
1253         struct vars *v, __isl_take isl_basic_map *bmap)
1254 {
1255         int n = v->n;
1256         isl_map *map;
1257         unsigned total;
1258
1259         if (!bmap)
1260                 return NULL;
1261
1262         bmap = isl_basic_set_unwrap(isl_basic_set_lift(isl_basic_map_wrap(bmap)));
1263         total = isl_basic_map_total_dim(bmap);
1264         while (v->n < total)
1265                 if (vars_add_anon(v) < 0)
1266                         goto error;
1267
1268         bmap = add_constraint(s, v, bmap);
1269         bmap = isl_basic_map_simplify(bmap);
1270         bmap = isl_basic_map_finalize(bmap);
1271
1272         map = isl_map_from_basic_map(bmap);
1273
1274         map = add_minmax(map, v, n);
1275
1276         map = isl_set_unwrap(isl_map_domain(map));
1277
1278         vars_drop(v, v->n - n);
1279
1280         return map;
1281 error:
1282         isl_basic_map_free(bmap);
1283         return NULL;
1284 }
1285
1286 static struct isl_map *read_disjuncts(struct isl_stream *s,
1287         struct vars *v, __isl_take isl_basic_map *bmap);
1288
1289 static __isl_give isl_map *read_exists(struct isl_stream *s,
1290         struct vars *v, __isl_take isl_basic_map *bmap)
1291 {
1292         int n = v->n;
1293         int seen_paren = isl_stream_eat_if_available(s, '(');
1294         isl_map *map = NULL;
1295
1296         bmap = isl_basic_map_from_domain(isl_basic_map_wrap(bmap));
1297         bmap = read_defined_var_list(s, v, bmap);
1298
1299         if (isl_stream_eat(s, ':'))
1300                 goto error;
1301
1302         map = read_disjuncts(s, v, bmap);
1303         map = isl_set_unwrap(isl_map_domain(map));
1304         bmap = NULL;
1305
1306         vars_drop(v, v->n - n);
1307         if (seen_paren && isl_stream_eat(s, ')'))
1308                 goto error;
1309
1310         return map;
1311 error:
1312         isl_basic_map_free(bmap);
1313         isl_map_free(map);
1314         return NULL;
1315 }
1316
1317 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1318         struct vars *v, __isl_take isl_basic_map *bmap)
1319 {
1320         isl_map *map;
1321
1322         if (isl_stream_eat_if_available(s, '(')) {
1323                 map = read_disjuncts(s, v, bmap);
1324                 if (isl_stream_eat(s, ')'))
1325                         goto error;
1326                 return map;
1327         }
1328
1329         if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1330                 return read_exists(s, v, bmap);
1331
1332         if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1333                 return isl_map_from_basic_map(bmap);
1334
1335         if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1336                 isl_dim *dim = isl_basic_map_get_dim(bmap);
1337                 isl_basic_map_free(bmap);
1338                 return isl_map_empty(dim);
1339         }
1340
1341         return read_constraint(s, v, bmap);
1342 error:
1343         isl_map_free(map);
1344         return NULL;
1345 }
1346
1347 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1348         struct vars *v, __isl_take isl_basic_map *bmap)
1349 {
1350         isl_map *map;
1351         int negate;
1352
1353         negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1354         map = read_conjunct(s, v, isl_basic_map_copy(bmap));
1355         if (negate) {
1356                 isl_map *t;
1357                 t = isl_map_from_basic_map(isl_basic_map_copy(bmap));
1358                 map = isl_map_subtract(t, map);
1359         }
1360
1361         while (isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1362                 isl_map *map_i;
1363
1364                 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1365                 map_i = read_conjunct(s, v, isl_basic_map_copy(bmap));
1366                 if (negate)
1367                         map = isl_map_subtract(map, map_i);
1368                 else
1369                         map = isl_map_intersect(map, map_i);
1370         }
1371
1372         isl_basic_map_free(bmap);
1373         return map;
1374 }
1375
1376 static struct isl_map *read_disjuncts(struct isl_stream *s,
1377         struct vars *v, __isl_take isl_basic_map *bmap)
1378 {
1379         struct isl_map *map;
1380
1381         if (isl_stream_next_token_is(s, '}')) {
1382                 isl_dim *dim = isl_basic_map_get_dim(bmap);
1383                 isl_basic_map_free(bmap);
1384                 return isl_map_universe(dim);
1385         }
1386
1387         map = read_conjuncts(s, v, isl_basic_map_copy(bmap));
1388         while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1389                 isl_map *map_i;
1390
1391                 map_i = read_conjuncts(s, v, isl_basic_map_copy(bmap));
1392                 map = isl_map_union(map, map_i);
1393         }
1394
1395         isl_basic_map_free(bmap);
1396         return map;
1397 }
1398
1399 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1400 {
1401         if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1402                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1403                            isl_basic_map_dim(bmap, isl_dim_in) + pos;
1404         pos -= isl_basic_map_dim(bmap, isl_dim_out);
1405
1406         if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1407                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1408         pos -= isl_basic_map_dim(bmap, isl_dim_in);
1409
1410         if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1411                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1412                            isl_basic_map_dim(bmap, isl_dim_in) +
1413                            isl_basic_map_dim(bmap, isl_dim_out) + pos;
1414         pos -= isl_basic_map_dim(bmap, isl_dim_div);
1415
1416         if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1417                 return 1 + pos;
1418
1419         return 0;
1420 }
1421
1422 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1423         struct isl_stream *s, __isl_take isl_basic_map *bmap)
1424 {
1425         int j;
1426         struct isl_token *tok;
1427         int type;
1428         int k;
1429         isl_int *c;
1430         unsigned nparam;
1431         unsigned dim;
1432
1433         if (!bmap)
1434                 return NULL;
1435
1436         nparam = isl_basic_map_dim(bmap, isl_dim_param);
1437         dim = isl_basic_map_dim(bmap, isl_dim_out);
1438
1439         tok = isl_stream_next_token(s);
1440         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1441                 isl_stream_error(s, tok, "expecting coefficient");
1442                 if (tok)
1443                         isl_stream_push_token(s, tok);
1444                 goto error;
1445         }
1446         if (!tok->on_new_line) {
1447                 isl_stream_error(s, tok, "coefficient should appear on new line");
1448                 isl_stream_push_token(s, tok);
1449                 goto error;
1450         }
1451
1452         type = isl_int_get_si(tok->u.v);
1453         isl_token_free(tok);
1454
1455         isl_assert(s->ctx, type == 0 || type == 1, goto error);
1456         if (type == 0) {
1457                 k = isl_basic_map_alloc_equality(bmap);
1458                 c = bmap->eq[k];
1459         } else {
1460                 k = isl_basic_map_alloc_inequality(bmap);
1461                 c = bmap->ineq[k];
1462         }
1463         if (k < 0)
1464                 goto error;
1465
1466         for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1467                 int pos;
1468                 tok = isl_stream_next_token(s);
1469                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1470                         isl_stream_error(s, tok, "expecting coefficient");
1471                         if (tok)
1472                                 isl_stream_push_token(s, tok);
1473                         goto error;
1474                 }
1475                 if (tok->on_new_line) {
1476                         isl_stream_error(s, tok,
1477                                 "coefficient should not appear on new line");
1478                         isl_stream_push_token(s, tok);
1479                         goto error;
1480                 }
1481                 pos = polylib_pos_to_isl_pos(bmap, j);
1482                 isl_int_set(c[pos], tok->u.v);
1483                 isl_token_free(tok);
1484         }
1485
1486         return bmap;
1487 error:
1488         isl_basic_map_free(bmap);
1489         return NULL;
1490 }
1491
1492 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s,
1493         int nparam)
1494 {
1495         int i;
1496         struct isl_token *tok;
1497         struct isl_token *tok2;
1498         int n_row, n_col;
1499         int on_new_line;
1500         unsigned in = 0, out, local = 0;
1501         struct isl_basic_map *bmap = NULL;
1502
1503         if (nparam < 0)
1504                 nparam = 0;
1505
1506         tok = isl_stream_next_token(s);
1507         if (!tok) {
1508                 isl_stream_error(s, NULL, "unexpected EOF");
1509                 return NULL;
1510         }
1511         tok2 = isl_stream_next_token(s);
1512         if (!tok2) {
1513                 isl_token_free(tok);
1514                 isl_stream_error(s, NULL, "unexpected EOF");
1515                 return NULL;
1516         }
1517         if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1518                 isl_stream_push_token(s, tok2);
1519                 isl_stream_push_token(s, tok);
1520                 isl_stream_error(s, NULL,
1521                                  "expecting constraint matrix dimensions");
1522                 return NULL;
1523         }
1524         n_row = isl_int_get_si(tok->u.v);
1525         n_col = isl_int_get_si(tok2->u.v);
1526         on_new_line = tok2->on_new_line;
1527         isl_token_free(tok2);
1528         isl_token_free(tok);
1529         isl_assert(s->ctx, !on_new_line, return NULL);
1530         isl_assert(s->ctx, n_row >= 0, return NULL);
1531         isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1532         tok = isl_stream_next_token_on_same_line(s);
1533         if (tok) {
1534                 if (tok->type != ISL_TOKEN_VALUE) {
1535                         isl_stream_error(s, tok,
1536                                     "expecting number of output dimensions");
1537                         isl_stream_push_token(s, tok);
1538                         goto error;
1539                 }
1540                 out = isl_int_get_si(tok->u.v);
1541                 isl_token_free(tok);
1542
1543                 tok = isl_stream_next_token_on_same_line(s);
1544                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1545                         isl_stream_error(s, tok,
1546                                     "expecting number of input dimensions");
1547                         if (tok)
1548                                 isl_stream_push_token(s, tok);
1549                         goto error;
1550                 }
1551                 in = isl_int_get_si(tok->u.v);
1552                 isl_token_free(tok);
1553
1554                 tok = isl_stream_next_token_on_same_line(s);
1555                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1556                         isl_stream_error(s, tok,
1557                                     "expecting number of existentials");
1558                         if (tok)
1559                                 isl_stream_push_token(s, tok);
1560                         goto error;
1561                 }
1562                 local = isl_int_get_si(tok->u.v);
1563                 isl_token_free(tok);
1564
1565                 tok = isl_stream_next_token_on_same_line(s);
1566                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1567                         isl_stream_error(s, tok,
1568                                     "expecting number of parameters");
1569                         if (tok)
1570                                 isl_stream_push_token(s, tok);
1571                         goto error;
1572                 }
1573                 nparam = isl_int_get_si(tok->u.v);
1574                 isl_token_free(tok);
1575                 if (n_col != 1 + out + in + local + nparam + 1) {
1576                         isl_stream_error(s, NULL,
1577                                     "dimensions don't match");
1578                         goto error;
1579                 }
1580         } else
1581                 out = n_col - 2 - nparam;
1582         bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1583         if (!bmap)
1584                 return NULL;
1585
1586         for (i = 0; i < local; ++i) {
1587                 int k = isl_basic_map_alloc_div(bmap);
1588                 if (k < 0)
1589                         goto error;
1590                 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1591         }
1592
1593         for (i = 0; i < n_row; ++i)
1594                 bmap = basic_map_read_polylib_constraint(s, bmap);
1595
1596         tok = isl_stream_next_token_on_same_line(s);
1597         if (tok) {
1598                 isl_stream_error(s, tok, "unexpected extra token on line");
1599                 isl_stream_push_token(s, tok);
1600                 goto error;
1601         }
1602
1603         bmap = isl_basic_map_simplify(bmap);
1604         bmap = isl_basic_map_finalize(bmap);
1605         return bmap;
1606 error:
1607         isl_basic_map_free(bmap);
1608         return NULL;
1609 }
1610
1611 static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam)
1612 {
1613         struct isl_token *tok;
1614         struct isl_token *tok2;
1615         int i, n;
1616         struct isl_map *map;
1617
1618         tok = isl_stream_next_token(s);
1619         if (!tok) {
1620                 isl_stream_error(s, NULL, "unexpected EOF");
1621                 return NULL;
1622         }
1623         tok2 = isl_stream_next_token_on_same_line(s);
1624         if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1625                 isl_stream_push_token(s, tok2);
1626                 isl_stream_push_token(s, tok);
1627                 return isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
1628         }
1629         if (tok2) {
1630                 isl_stream_error(s, tok2, "unexpected token");
1631                 isl_stream_push_token(s, tok2);
1632                 isl_stream_push_token(s, tok);
1633                 return NULL;
1634         }
1635         n = isl_int_get_si(tok->u.v);
1636         isl_token_free(tok);
1637
1638         isl_assert(s->ctx, n >= 1, return NULL);
1639
1640         map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
1641
1642         for (i = 1; map && i < n; ++i)
1643                 map = isl_map_union(map,
1644                         isl_map_from_basic_map(basic_map_read_polylib(s, nparam)));
1645
1646         return map;
1647 }
1648
1649 static int optional_power(struct isl_stream *s)
1650 {
1651         int pow;
1652         struct isl_token *tok;
1653
1654         tok = isl_stream_next_token(s);
1655         if (!tok)
1656                 return 1;
1657         if (tok->type != '^') {
1658                 isl_stream_push_token(s, tok);
1659                 return 1;
1660         }
1661         isl_token_free(tok);
1662         tok = isl_stream_next_token(s);
1663         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1664                 isl_stream_error(s, tok, "expecting exponent");
1665                 if (tok)
1666                         isl_stream_push_token(s, tok);
1667                 return 1;
1668         }
1669         pow = isl_int_get_si(tok->u.v);
1670         isl_token_free(tok);
1671         return pow;
1672 }
1673
1674 static __isl_give isl_div *read_div(struct isl_stream *s,
1675         __isl_take isl_dim *dim, struct vars *v)
1676 {
1677         int n;
1678         isl_basic_map *bmap;
1679
1680         n = v->n;
1681         bmap = isl_basic_map_universe(dim);
1682
1683         if (vars_add_anon(v) < 0)
1684                 goto error;
1685         if (read_div_definition(s, v) < 0)
1686                 goto error;
1687         bmap = add_divs(bmap, v);
1688         bmap = isl_basic_map_order_divs(bmap);
1689         if (!bmap)
1690                 goto error;
1691         vars_drop(v, v->n - n);
1692
1693         return isl_basic_map_div(bmap, bmap->n_div - 1);
1694 error:
1695         isl_basic_map_free(bmap);
1696         return NULL;
1697 }
1698
1699 static __isl_give isl_qpolynomial *read_term(struct isl_stream *s,
1700         __isl_keep isl_basic_map *bmap, struct vars *v);
1701
1702 static __isl_give isl_qpolynomial *read_factor(struct isl_stream *s,
1703         __isl_keep isl_basic_map *bmap, struct vars *v)
1704 {
1705         struct isl_qpolynomial *qp;
1706         struct isl_token *tok;
1707
1708         tok = next_token(s);
1709         if (!tok) {
1710                 isl_stream_error(s, NULL, "unexpected EOF");
1711                 return NULL;
1712         }
1713         if (tok->type == '(') {
1714                 int pow;
1715
1716                 isl_token_free(tok);
1717                 qp = read_term(s, bmap, v);
1718                 if (!qp)
1719                         return NULL;
1720                 if (isl_stream_eat(s, ')'))
1721                         goto error;
1722                 pow = optional_power(s);
1723                 qp = isl_qpolynomial_pow(qp, pow);
1724         } else if (tok->type == ISL_TOKEN_VALUE) {
1725                 struct isl_token *tok2;
1726                 tok2 = isl_stream_next_token(s);
1727                 if (tok2 && tok2->type == '/') {
1728                         isl_token_free(tok2);
1729                         tok2 = next_token(s);
1730                         if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1731                                 isl_stream_error(s, tok2, "expected denominator");
1732                                 isl_token_free(tok);
1733                                 isl_token_free(tok2);
1734                                 return NULL;
1735                         }
1736                         qp = isl_qpolynomial_rat_cst(isl_basic_map_get_dim(bmap),
1737                                                     tok->u.v, tok2->u.v);
1738                         isl_token_free(tok2);
1739                 } else {
1740                         isl_stream_push_token(s, tok2);
1741                         qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1742                                                 tok->u.v);
1743                 }
1744                 isl_token_free(tok);
1745         } else if (tok->type == ISL_TOKEN_INFTY) {
1746                 isl_token_free(tok);
1747                 qp = isl_qpolynomial_infty(isl_basic_map_get_dim(bmap));
1748         } else if (tok->type == ISL_TOKEN_NAN) {
1749                 isl_token_free(tok);
1750                 qp = isl_qpolynomial_nan(isl_basic_map_get_dim(bmap));
1751         } else if (tok->type == ISL_TOKEN_IDENT) {
1752                 int n = v->n;
1753                 int pos = vars_pos(v, tok->u.s, -1);
1754                 int pow;
1755                 if (pos < 0) {
1756                         isl_token_free(tok);
1757                         return NULL;
1758                 }
1759                 if (pos >= n) {
1760                         vars_drop(v, v->n - n);
1761                         isl_stream_error(s, tok, "unknown identifier");
1762                         isl_token_free(tok);
1763                         return NULL;
1764                 }
1765                 isl_token_free(tok);
1766                 pow = optional_power(s);
1767                 qp = isl_qpolynomial_var_pow(isl_basic_map_get_dim(bmap), pos, pow);
1768         } else if (tok->type == '[') {
1769                 isl_div *div;
1770                 int pow;
1771
1772                 isl_stream_push_token(s, tok);
1773                 div = read_div(s, isl_basic_map_get_dim(bmap), v);
1774                 pow = optional_power(s);
1775                 qp = isl_qpolynomial_div_pow(div, pow);
1776         } else if (tok->type == '-') {
1777                 struct isl_qpolynomial *qp2;
1778
1779                 isl_token_free(tok);
1780                 qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1781                                             s->ctx->negone);
1782                 qp2 = read_factor(s, bmap, v);
1783                 qp = isl_qpolynomial_mul(qp, qp2);
1784         } else {
1785                 isl_stream_error(s, tok, "unexpected isl_token");
1786                 isl_stream_push_token(s, tok);
1787                 return NULL;
1788         }
1789
1790         if (isl_stream_eat_if_available(s, '*') ||
1791             isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1792                 struct isl_qpolynomial *qp2;
1793
1794                 qp2 = read_factor(s, bmap, v);
1795                 qp = isl_qpolynomial_mul(qp, qp2);
1796         }
1797
1798         return qp;
1799 error:
1800         isl_qpolynomial_free(qp);
1801         return NULL;
1802 }
1803
1804 static __isl_give isl_qpolynomial *read_term(struct isl_stream *s,
1805         __isl_keep isl_basic_map *bmap, struct vars *v)
1806 {
1807         struct isl_token *tok;
1808         struct isl_qpolynomial *qp;
1809
1810         qp = read_factor(s, bmap, v);
1811
1812         for (;;) {
1813                 tok = next_token(s);
1814                 if (!tok)
1815                         return qp;
1816
1817                 if (tok->type == '+') {
1818                         struct isl_qpolynomial *qp2;
1819
1820                         isl_token_free(tok);
1821                         qp2 = read_factor(s, bmap, v);
1822                         qp = isl_qpolynomial_add(qp, qp2);
1823                 } else if (tok->type == '-') {
1824                         struct isl_qpolynomial *qp2;
1825
1826                         isl_token_free(tok);
1827                         qp2 = read_factor(s, bmap, v);
1828                         qp = isl_qpolynomial_sub(qp, qp2);
1829                 } else if (tok->type == ISL_TOKEN_VALUE &&
1830                             isl_int_is_neg(tok->u.v)) {
1831                         struct isl_qpolynomial *qp2;
1832
1833                         isl_stream_push_token(s, tok);
1834                         qp2 = read_factor(s, bmap, v);
1835                         qp = isl_qpolynomial_add(qp, qp2);
1836                 } else {
1837                         isl_stream_push_token(s, tok);
1838                         break;
1839                 }
1840         }
1841
1842         return qp;
1843 }
1844
1845 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1846         __isl_take isl_basic_map *bmap, struct vars *v)
1847 {
1848         struct isl_token *tok;
1849         struct isl_map *map;
1850
1851         tok = isl_stream_next_token(s);
1852         if (!tok) {
1853                 isl_stream_error(s, NULL, "unexpected EOF");
1854                 goto error;
1855         }
1856         map = isl_map_from_basic_map(isl_basic_map_copy(bmap));
1857         if (tok->type == ':' ||
1858             (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
1859                 isl_token_free(tok);
1860                 map = isl_map_intersect(map,
1861                             read_disjuncts(s, v, isl_basic_map_copy(bmap)));
1862         } else
1863                 isl_stream_push_token(s, tok);
1864
1865         isl_basic_map_free(bmap);
1866
1867         return map;
1868 error:
1869         isl_basic_map_free(bmap);
1870         return NULL;
1871 }
1872
1873 static struct isl_obj obj_read_poly(struct isl_stream *s,
1874         __isl_take isl_basic_map *bmap, struct vars *v, int n)
1875 {
1876         struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1877         struct isl_pw_qpolynomial *pwqp;
1878         struct isl_qpolynomial *qp;
1879         struct isl_map *map;
1880         struct isl_set *set;
1881
1882         qp = read_term(s, bmap, v);
1883         map = read_optional_disjuncts(s, bmap, v);
1884         set = isl_map_range(map);
1885
1886         pwqp = isl_pw_qpolynomial_alloc(set, qp);
1887
1888         vars_drop(v, v->n - n);
1889
1890         obj.v = pwqp;
1891         return obj;
1892 }
1893
1894 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1895         __isl_take isl_basic_map *bmap, struct vars *v, int n)
1896 {
1897         struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1898         struct isl_obj obj_p;
1899         isl_qpolynomial *qp;
1900         isl_qpolynomial_fold *fold = NULL;
1901         isl_pw_qpolynomial_fold *pwf;
1902         isl_map *map;
1903         isl_set *set;
1904
1905         if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1906                 return obj_read_poly(s, bmap, v, n);
1907
1908         if (isl_stream_eat(s, '('))
1909                 goto error;
1910
1911         qp = read_term(s, bmap, v);
1912         fold = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1913
1914         while (isl_stream_eat_if_available(s, ',')) {
1915                 isl_qpolynomial_fold *fold_i;
1916                 qp = read_term(s, bmap, v);
1917                 fold_i = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1918                 fold = isl_qpolynomial_fold_fold(fold, fold_i);
1919         }
1920
1921         if (isl_stream_eat(s, ')'))
1922                 goto error;
1923
1924         map = read_optional_disjuncts(s, bmap, v);
1925         set = isl_map_range(map);
1926         pwf = isl_pw_qpolynomial_fold_alloc(isl_fold_max, set, fold);
1927
1928         vars_drop(v, v->n - n);
1929
1930         obj.v = pwf;
1931         return obj;
1932 error:
1933         isl_basic_map_free(bmap);
1934         isl_qpolynomial_fold_free(fold);
1935         obj.type = isl_obj_none;
1936         return obj;
1937 }
1938
1939 static int is_rational(struct isl_stream *s)
1940 {
1941         struct isl_token *tok;
1942
1943         tok = isl_stream_next_token(s);
1944         if (!tok)
1945                 return 0;
1946         if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
1947                 isl_token_free(tok);
1948                 isl_stream_eat(s, ':');
1949                 return 1;
1950         }
1951
1952         isl_stream_push_token(s, tok);
1953
1954         return 0;
1955 }
1956
1957 static struct isl_obj obj_read_body(struct isl_stream *s,
1958         __isl_take isl_basic_map *bmap, struct vars *v)
1959 {
1960         struct isl_map *map = NULL;
1961         struct isl_token *tok;
1962         struct isl_obj obj = { isl_obj_set, NULL };
1963         int n = v->n;
1964
1965         if (is_rational(s))
1966                 bmap = isl_basic_map_set_rational(bmap);
1967
1968         if (!next_is_tuple(s))
1969                 return obj_read_poly_or_fold(s, bmap, v, n);
1970
1971         bmap = read_tuple(s, bmap, isl_dim_in, v);
1972         if (!bmap)
1973                 goto error;
1974         tok = isl_stream_next_token(s);
1975         if (tok && tok->type == ISL_TOKEN_TO) {
1976                 obj.type = isl_obj_map;
1977                 isl_token_free(tok);
1978                 if (!next_is_tuple(s)) {
1979                         bmap = isl_basic_map_reverse(bmap);
1980                         return obj_read_poly_or_fold(s, bmap, v, n);
1981                 }
1982                 bmap = read_tuple(s, bmap, isl_dim_out, v);
1983                 if (!bmap)
1984                         goto error;
1985         } else {
1986                 bmap = isl_basic_map_reverse(bmap);
1987                 if (tok)
1988                         isl_stream_push_token(s, tok);
1989         }
1990
1991         map = read_optional_disjuncts(s, bmap, v);
1992
1993         vars_drop(v, v->n - n);
1994
1995         obj.v = map;
1996         return obj;
1997 error:
1998         isl_basic_map_free(bmap);
1999         obj.type = isl_obj_none;
2000         return obj;
2001 }
2002
2003 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2004 {
2005         if (obj.type == isl_obj_map) {
2006                 obj.v = isl_union_map_from_map(obj.v);
2007                 obj.type = isl_obj_union_map;
2008         } else if (obj.type == isl_obj_set) {
2009                 obj.v = isl_union_set_from_set(obj.v);
2010                 obj.type = isl_obj_union_set;
2011         } else if (obj.type == isl_obj_pw_qpolynomial) {
2012                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2013                 obj.type = isl_obj_union_pw_qpolynomial;
2014         } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
2015                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
2016                 obj.type = isl_obj_union_pw_qpolynomial_fold;
2017         } else
2018                 isl_assert(ctx, 0, goto error);
2019         return obj;
2020 error:
2021         obj.type->free(obj.v);
2022         obj.type = isl_obj_none;
2023         return obj;
2024 }
2025
2026 static struct isl_obj obj_add(struct isl_ctx *ctx,
2027         struct isl_obj obj1, struct isl_obj obj2)
2028 {
2029         if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
2030                 obj1 = to_union(ctx, obj1);
2031         if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
2032                 obj2 = to_union(ctx, obj2);
2033         if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
2034                 obj1 = to_union(ctx, obj1);
2035         if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
2036                 obj2 = to_union(ctx, obj2);
2037         if (obj1.type == isl_obj_pw_qpolynomial &&
2038             obj2.type == isl_obj_union_pw_qpolynomial)
2039                 obj1 = to_union(ctx, obj1);
2040         if (obj1.type == isl_obj_union_pw_qpolynomial &&
2041             obj2.type == isl_obj_pw_qpolynomial)
2042                 obj2 = to_union(ctx, obj2);
2043         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2044             obj2.type == isl_obj_union_pw_qpolynomial_fold)
2045                 obj1 = to_union(ctx, obj1);
2046         if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2047             obj2.type == isl_obj_pw_qpolynomial_fold)
2048                 obj2 = to_union(ctx, obj2);
2049         isl_assert(ctx, obj1.type == obj2.type, goto error);
2050         if (obj1.type == isl_obj_map && !isl_map_has_equal_dim(obj1.v, obj2.v)) {
2051                 obj1 = to_union(ctx, obj1);
2052                 obj2 = to_union(ctx, obj2);
2053         }
2054         if (obj1.type == isl_obj_set && !isl_set_has_equal_dim(obj1.v, obj2.v)) {
2055                 obj1 = to_union(ctx, obj1);
2056                 obj2 = to_union(ctx, obj2);
2057         }
2058         if (obj1.type == isl_obj_pw_qpolynomial &&
2059             !isl_pw_qpolynomial_has_equal_dim(obj1.v, obj2.v)) {
2060                 obj1 = to_union(ctx, obj1);
2061                 obj2 = to_union(ctx, obj2);
2062         }
2063         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2064             !isl_pw_qpolynomial_fold_has_equal_dim(obj1.v, obj2.v)) {
2065                 obj1 = to_union(ctx, obj1);
2066                 obj2 = to_union(ctx, obj2);
2067         }
2068         obj1.v = obj1.type->add(obj1.v, obj2.v);
2069         return obj1;
2070 error:
2071         obj1.type->free(obj1.v);
2072         obj2.type->free(obj2.v);
2073         obj1.type = isl_obj_none;
2074         obj1.v = NULL;
2075         return obj1;
2076 }
2077
2078 static struct isl_obj obj_read(struct isl_stream *s, int nparam)
2079 {
2080         isl_basic_map *bmap = NULL;
2081         struct isl_token *tok;
2082         struct vars *v = NULL;
2083         struct isl_obj obj = { isl_obj_set, NULL };
2084
2085         tok = next_token(s);
2086         if (!tok) {
2087                 isl_stream_error(s, NULL, "unexpected EOF");
2088                 goto error;
2089         }
2090         if (tok->type == ISL_TOKEN_VALUE) {
2091                 struct isl_token *tok2;
2092                 struct isl_map *map;
2093
2094                 tok2 = isl_stream_next_token(s);
2095                 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
2096                     isl_int_is_neg(tok2->u.v)) {
2097                         if (tok2)
2098                                 isl_stream_push_token(s, tok2);
2099                         obj.type = isl_obj_int;
2100                         obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
2101                         isl_token_free(tok);
2102                         return obj;
2103                 }
2104                 isl_stream_push_token(s, tok2);
2105                 isl_stream_push_token(s, tok);
2106                 map = map_read_polylib(s, nparam);
2107                 if (!map)
2108                         goto error;
2109                 if (isl_map_dim(map, isl_dim_in) > 0)
2110                         obj.type = isl_obj_map;
2111                 obj.v = map;
2112                 return obj;
2113         }
2114         v = vars_new(s->ctx);
2115         if (!v) {
2116                 isl_stream_push_token(s, tok);
2117                 goto error;
2118         }
2119         bmap = isl_basic_map_alloc(s->ctx, 0, 0, 0, 0, 0, 0);
2120         if (tok->type == '[') {
2121                 isl_stream_push_token(s, tok);
2122                 bmap = read_tuple(s, bmap, isl_dim_param, v);
2123                 if (!bmap)
2124                         goto error;
2125                 if (nparam >= 0)
2126                         isl_assert(s->ctx, nparam == v->n, goto error);
2127                 tok = isl_stream_next_token(s);
2128                 if (!tok || tok->type != ISL_TOKEN_TO) {
2129                         isl_stream_error(s, tok, "expecting '->'");
2130                         if (tok)
2131                                 isl_stream_push_token(s, tok);
2132                         goto error;
2133                 }
2134                 isl_token_free(tok);
2135                 tok = isl_stream_next_token(s);
2136         } else if (nparam > 0)
2137                 bmap = isl_basic_map_add(bmap, isl_dim_param, nparam);
2138         if (!tok || tok->type != '{') {
2139                 isl_stream_error(s, tok, "expecting '{'");
2140                 if (tok)
2141                         isl_stream_push_token(s, tok);
2142                 goto error;
2143         }
2144         isl_token_free(tok);
2145
2146         tok = isl_stream_next_token(s);
2147         if (!tok)
2148                 ;
2149         else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
2150                 isl_token_free(tok);
2151                 if (isl_stream_eat(s, '='))
2152                         goto error;
2153                 bmap = read_tuple(s, bmap, isl_dim_param, v);
2154                 if (!bmap)
2155                         goto error;
2156                 if (nparam >= 0)
2157                         isl_assert(s->ctx, nparam == v->n, goto error);
2158         } else if (tok->type == '}') {
2159                 obj.type = isl_obj_union_set;
2160                 obj.v = isl_union_set_empty(isl_basic_map_get_dim(bmap));
2161                 isl_token_free(tok);
2162                 goto done;
2163         } else
2164                 isl_stream_push_token(s, tok);
2165
2166         for (;;) {
2167                 struct isl_obj o;
2168                 tok = NULL;
2169                 o = obj_read_body(s, isl_basic_map_copy(bmap), v);
2170                 if (o.type == isl_obj_none || !o.v)
2171                         goto error;
2172                 if (!obj.v)
2173                         obj = o;
2174                 else {
2175                         obj = obj_add(s->ctx, obj, o);
2176                         if (obj.type == isl_obj_none || !obj.v)
2177                                 goto error;
2178                 }
2179                 tok = isl_stream_next_token(s);
2180                 if (!tok || tok->type != ';')
2181                         break;
2182                 isl_token_free(tok);
2183                 if (isl_stream_next_token_is(s, '}')) {
2184                         tok = isl_stream_next_token(s);
2185                         break;
2186                 }
2187         }
2188
2189         if (tok && tok->type == '}') {
2190                 isl_token_free(tok);
2191         } else {
2192                 isl_stream_error(s, tok, "unexpected isl_token");
2193                 if (tok)
2194                         isl_token_free(tok);
2195                 goto error;
2196         }
2197 done:
2198         vars_free(v);
2199         isl_basic_map_free(bmap);
2200
2201         return obj;
2202 error:
2203         isl_basic_map_free(bmap);
2204         obj.type->free(obj.v);
2205         if (v)
2206                 vars_free(v);
2207         obj.v = NULL;
2208         return obj;
2209 }
2210
2211 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
2212 {
2213         return obj_read(s, -1);
2214 }
2215
2216 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s, int nparam)
2217 {
2218         struct isl_obj obj;
2219         struct isl_map *map;
2220
2221         obj = obj_read(s, nparam);
2222         if (obj.v)
2223                 isl_assert(s->ctx, obj.type == isl_obj_map ||
2224                                    obj.type == isl_obj_set, goto error);
2225
2226         return obj.v;
2227 error:
2228         obj.type->free(obj.v);
2229         return NULL;
2230 }
2231
2232 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s, int nparam)
2233 {
2234         struct isl_obj obj;
2235         struct isl_set *set;
2236
2237         obj = obj_read(s, nparam);
2238         if (obj.v)
2239                 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2240
2241         return obj.v;
2242 error:
2243         obj.type->free(obj.v);
2244         return NULL;
2245 }
2246
2247 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2248 {
2249         struct isl_obj obj;
2250         isl_union_map *umap;
2251
2252         obj = obj_read(s, -1);
2253         if (obj.type == isl_obj_map) {
2254                 obj.type = isl_obj_union_map;
2255                 obj.v = isl_union_map_from_map(obj.v);
2256         }
2257         if (obj.type == isl_obj_set) {
2258                 obj.type = isl_obj_union_set;
2259                 obj.v = isl_union_set_from_set(obj.v);
2260         }
2261         if (obj.v)
2262                 isl_assert(s->ctx, obj.type == isl_obj_union_map ||
2263                                    obj.type == isl_obj_union_set, goto error);
2264
2265         return obj.v;
2266 error:
2267         obj.type->free(obj.v);
2268         return NULL;
2269 }
2270
2271 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2272 {
2273         struct isl_obj obj;
2274         isl_union_set *uset;
2275
2276         obj = obj_read(s, -1);
2277         if (obj.type == isl_obj_set) {
2278                 obj.type = isl_obj_union_set;
2279                 obj.v = isl_union_set_from_set(obj.v);
2280         }
2281         if (obj.v)
2282                 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2283
2284         return obj.v;
2285 error:
2286         obj.type->free(obj.v);
2287         return NULL;
2288 }
2289
2290 static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam)
2291 {
2292         struct isl_obj obj;
2293         struct isl_map *map;
2294         struct isl_basic_map *bmap;
2295
2296         obj = obj_read(s, nparam);
2297         map = obj.v;
2298         if (!map)
2299                 return NULL;
2300
2301         isl_assert(map->ctx, map->n <= 1, goto error);
2302
2303         if (map->n == 0)
2304                 bmap = isl_basic_map_empty_like_map(map);
2305         else
2306                 bmap = isl_basic_map_copy(map->p[0]);
2307
2308         isl_map_free(map);
2309
2310         return bmap;
2311 error:
2312         isl_map_free(map);
2313         return NULL;
2314 }
2315
2316 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2317                 FILE *input, int nparam)
2318 {
2319         struct isl_basic_map *bmap;
2320         struct isl_stream *s = isl_stream_new_file(ctx, input);
2321         if (!s)
2322                 return NULL;
2323         bmap = basic_map_read(s, nparam);
2324         isl_stream_free(s);
2325         return bmap;
2326 }
2327
2328 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2329                 FILE *input, int nparam)
2330 {
2331         struct isl_basic_map *bmap;
2332         bmap = isl_basic_map_read_from_file(ctx, input, nparam);
2333         if (!bmap)
2334                 return NULL;
2335         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
2336         return (struct isl_basic_set *)bmap;
2337 error:
2338         isl_basic_map_free(bmap);
2339         return NULL;
2340 }
2341
2342 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2343                 const char *str, int nparam)
2344 {
2345         struct isl_basic_map *bmap;
2346         struct isl_stream *s = isl_stream_new_str(ctx, str);
2347         if (!s)
2348                 return NULL;
2349         bmap = basic_map_read(s, nparam);
2350         isl_stream_free(s);
2351         return bmap;
2352 }
2353
2354 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2355                 const char *str, int nparam)
2356 {
2357         struct isl_basic_map *bmap;
2358         bmap = isl_basic_map_read_from_str(ctx, str, nparam);
2359         if (!bmap)
2360                 return NULL;
2361         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
2362         return (struct isl_basic_set *)bmap;
2363 error:
2364         isl_basic_map_free(bmap);
2365         return NULL;
2366 }
2367
2368 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2369                 FILE *input, int nparam)
2370 {
2371         struct isl_map *map;
2372         struct isl_stream *s = isl_stream_new_file(ctx, input);
2373         if (!s)
2374                 return NULL;
2375         map = isl_stream_read_map(s, nparam);
2376         isl_stream_free(s);
2377         return map;
2378 }
2379
2380 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2381                 const char *str, int nparam)
2382 {
2383         struct isl_map *map;
2384         struct isl_stream *s = isl_stream_new_str(ctx, str);
2385         if (!s)
2386                 return NULL;
2387         map = isl_stream_read_map(s, nparam);
2388         isl_stream_free(s);
2389         return map;
2390 }
2391
2392 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2393                 FILE *input, int nparam)
2394 {
2395         struct isl_map *map;
2396         map = isl_map_read_from_file(ctx, input, nparam);
2397         if (!map)
2398                 return NULL;
2399         isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
2400         return (struct isl_set *)map;
2401 error:
2402         isl_map_free(map);
2403         return NULL;
2404 }
2405
2406 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2407                 const char *str, int nparam)
2408 {
2409         struct isl_map *map;
2410         map = isl_map_read_from_str(ctx, str, nparam);
2411         if (!map)
2412                 return NULL;
2413         isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
2414         return (struct isl_set *)map;
2415 error:
2416         isl_map_free(map);
2417         return NULL;
2418 }
2419
2420 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2421         FILE *input)
2422 {
2423         isl_union_map *umap;
2424         struct isl_stream *s = isl_stream_new_file(ctx, input);
2425         if (!s)
2426                 return NULL;
2427         umap = isl_stream_read_union_map(s);
2428         isl_stream_free(s);
2429         return umap;
2430 }
2431
2432 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2433                 const char *str)
2434 {
2435         isl_union_map *umap;
2436         struct isl_stream *s = isl_stream_new_str(ctx, str);
2437         if (!s)
2438                 return NULL;
2439         umap = isl_stream_read_union_map(s);
2440         isl_stream_free(s);
2441         return umap;
2442 }
2443
2444 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2445         FILE *input)
2446 {
2447         isl_union_set *uset;
2448         struct isl_stream *s = isl_stream_new_file(ctx, input);
2449         if (!s)
2450                 return NULL;
2451         uset = isl_stream_read_union_set(s);
2452         isl_stream_free(s);
2453         return uset;
2454 }
2455
2456 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2457                 const char *str)
2458 {
2459         isl_union_set *uset;
2460         struct isl_stream *s = isl_stream_new_str(ctx, str);
2461         if (!s)
2462                 return NULL;
2463         uset = isl_stream_read_union_set(s);
2464         isl_stream_free(s);
2465         return uset;
2466 }
2467
2468 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2469 {
2470         struct isl_vec *vec = NULL;
2471         struct isl_token *tok;
2472         unsigned size;
2473         int j;
2474
2475         tok = isl_stream_next_token(s);
2476         if (!tok || tok->type != ISL_TOKEN_VALUE) {
2477                 isl_stream_error(s, tok, "expecting vector length");
2478                 goto error;
2479         }
2480
2481         size = isl_int_get_si(tok->u.v);
2482         isl_token_free(tok);
2483
2484         vec = isl_vec_alloc(s->ctx, size);
2485
2486         for (j = 0; j < size; ++j) {
2487                 tok = isl_stream_next_token(s);
2488                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2489                         isl_stream_error(s, tok, "expecting constant value");
2490                         goto error;
2491                 }
2492                 isl_int_set(vec->el[j], tok->u.v);
2493                 isl_token_free(tok);
2494         }
2495
2496         return vec;
2497 error:
2498         isl_token_free(tok);
2499         isl_vec_free(vec);
2500         return NULL;
2501 }
2502
2503 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2504 {
2505         return isl_vec_read_polylib(s);
2506 }
2507
2508 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2509 {
2510         isl_vec *v;
2511         struct isl_stream *s = isl_stream_new_file(ctx, input);
2512         if (!s)
2513                 return NULL;
2514         v = vec_read(s);
2515         isl_stream_free(s);
2516         return v;
2517 }
2518
2519 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2520         struct isl_stream *s)
2521 {
2522         struct isl_obj obj;
2523         struct isl_pw_qpolynomial *pwqp;
2524
2525         obj = obj_read(s, -1);
2526         if (obj.v)
2527                 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2528                            goto error);
2529
2530         return obj.v;
2531 error:
2532         obj.type->free(obj.v);
2533         return NULL;
2534 }
2535
2536 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2537                 const char *str)
2538 {
2539         isl_pw_qpolynomial *pwqp;
2540         struct isl_stream *s = isl_stream_new_str(ctx, str);
2541         if (!s)
2542                 return NULL;
2543         pwqp = isl_stream_read_pw_qpolynomial(s);
2544         isl_stream_free(s);
2545         return pwqp;
2546 }