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