isl_input.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  * Copyright 2010      INRIA Saclay
   4  *
   5  * Use of this software is governed by the GNU LGPLv2.1 license
   6  *
   7  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   8  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   9  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  10  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
  11  */
  12
  13 #include <ctype.h>
  14 #include <stdio.h>
  15 #include <string.h>
  16 #include <strings.h>
  17 #include <isl_set.h>
  18 #include <isl_seq.h>
  19 #include <isl_div.h>
  20 #include "isl_stream.h"
  21 #include "isl_map_private.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         struct variable         *next;
  32 };
  33
  34 struct vars {
  35         struct isl_ctx  *ctx;
  36         int              n;
  37         struct variable *v;
  38 };
  39
  40 static struct vars *vars_new(struct isl_ctx *ctx)
  41 {
  42         struct vars *v;
  43         v = isl_alloc_type(ctx, struct vars);
  44         if (!v)
  45                 return NULL;
  46         v->ctx = ctx;
  47         v->n = 0;
  48         v->v = NULL;
  49         return v;
  50 }
  51
  52 static void variable_free(struct variable *var)
  53 {
  54         while (var) {
  55                 struct variable *next = var->next;
  56                 isl_vec_free(var->def);
  57                 free(var->name);
  58                 free(var);
  59                 var = next;
  60         }
  61 }
  62
  63 static void vars_free(struct vars *v)
  64 {
  65         if (!v)
  66                 return;
  67         variable_free(v->v);
  68         free(v);
  69 }
  70
  71 static void vars_drop(struct vars *v, int n)
  72 {
  73         struct variable *var;
  74
  75         if (!v || !v->v)
  76                 return;
  77
  78         v->n -= n;
  79
  80         var = v->v;
  81         while (--n >= 0) {
  82                 struct variable *next = var->next;
  83                 isl_vec_free(var->def);
  84                 free(var->name);
  85                 free(var);
  86                 var = next;
  87         }
  88         v->v = var;
  89 }
  90
  91 static struct variable *variable_new(struct vars *v, const char *name, int len,
  92                                 int pos)
  93 {
  94         struct variable *var;
  95         var = isl_alloc_type(v->ctx, struct variable);
  96         if (!var)
  97                 goto error;
  98         var->name = strdup(name);
  99         var->name[len] = '\0';
 100         var->pos = pos;
 101         var->def = NULL;
 102         var->next = v->v;
 103         return var;
 104 error:
 105         variable_free(v->v);
 106         return NULL;
 107 }
 108
 109 static int vars_pos(struct vars *v, const char *s, int len)
 110 {
 111         int pos;
 112         struct variable *q;
 113
 114         if (len == -1)
 115                 len = strlen(s);
 116         for (q = v->v; q; q = q->next) {
 117                 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
 118                         break;
 119         }
 120         if (q)
 121                 pos = q->pos;
 122         else {
 123                 pos = v->n;
 124                 v->v = variable_new(v, s, len, v->n);
 125                 if (!v->v)
 126                         return -1;
 127                 v->n++;
 128         }
 129         return pos;
 130 }
 131
 132 static int vars_add_anon(struct vars *v)
 133 {
 134         v->v = variable_new(v, "", 0, v->n);
 135
 136         if (!v->v)
 137                 return -1;
 138         v->n++;
 139
 140         return 0;
 141 }
 142
 143 static __isl_give isl_basic_map *set_name(__isl_take isl_basic_map *bmap,
 144         enum isl_dim_type type, unsigned pos, char *name)
 145 {
 146         char *prime;
 147
 148         if (!bmap)
 149                 return NULL;
 150         if (!name)
 151                 return bmap;
 152
 153         prime = strchr(name, '\'');
 154         if (prime)
 155                 *prime = '\0';
 156         bmap = isl_basic_map_set_dim_name(bmap, type, pos, name);
 157         if (prime)
 158                 *prime = '\'';
 159
 160         return bmap;
 161 }
 162
 163 static int accept_cst_factor(struct isl_stream *s, isl_int *f)
 164 {
 165         struct isl_token *tok;
 166
 167         tok = isl_stream_next_token(s);
 168         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 169                 isl_stream_error(s, tok, "expecting constant value");
 170                 goto error;
 171         }
 172
 173         isl_int_mul(*f, *f, tok->u.v);
 174
 175         isl_token_free(tok);
 176
 177         if (isl_stream_eat_if_available(s, '*'))
 178                 return accept_cst_factor(s, f);
 179
 180         return 0;
 181 error:
 182         isl_token_free(tok);
 183         return -1;
 184 }
 185
 186 static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v);
 187 static int read_div_definition(struct isl_stream *s, struct vars *v);
 188
 189 static __isl_give isl_vec *accept_affine_factor(struct isl_stream *s,
 190         struct vars *v)
 191 {
 192         struct isl_token *tok = NULL;
 193         isl_vec *aff = NULL;
 194
 195         tok = isl_stream_next_token(s);
 196         if (!tok) {
 197                 isl_stream_error(s, NULL, "unexpected EOF");
 198                 goto error;
 199         }
 200         if (tok->type == ISL_TOKEN_IDENT) {
 201                 int n = v->n;
 202                 int pos = vars_pos(v, tok->u.s, -1);
 203                 if (pos < 0)
 204                         goto error;
 205                 if (pos >= n) {
 206                         isl_stream_error(s, tok, "unknown identifier");
 207                         goto error;
 208                 }
 209
 210                 aff = isl_vec_alloc(v->ctx, 1 + v->n);
 211                 if (!aff)
 212                         goto error;
 213                 isl_seq_clr(aff->el, aff->size);
 214                 isl_int_set_si(aff->el[1 + pos], 1);
 215                 isl_token_free(tok);
 216         } else if (tok->type == ISL_TOKEN_VALUE) {
 217                 if (isl_stream_eat_if_available(s, '*')) {
 218                         aff = accept_affine_factor(s, v);
 219                         aff = isl_vec_scale(aff, tok->u.v);
 220                 } else {
 221                         aff = isl_vec_alloc(v->ctx, 1 + v->n);
 222                         if (!aff)
 223                                 goto error;
 224                         isl_seq_clr(aff->el, aff->size);
 225                         isl_int_set(aff->el[0], tok->u.v);
 226                 }
 227                 isl_token_free(tok);
 228         } else if (tok->type == '(') {
 229                 isl_token_free(tok);
 230                 tok = NULL;
 231                 aff = accept_affine(s, v);
 232                 if (!aff)
 233                         goto error;
 234                 if (isl_stream_eat(s, ')'))
 235                         goto error;
 236         } else if (tok->type == '[') {
 237                 if (vars_add_anon(v) < 0)
 238                         goto error;
 239                 aff = isl_vec_alloc(v->ctx, 1 + v->n);
 240                 if (!aff)
 241                         goto error;
 242                 isl_seq_clr(aff->el, aff->size);
 243                 isl_int_set_si(aff->el[1 + v->n - 1], 1);
 244                 isl_stream_push_token(s, tok);
 245                 tok = NULL;
 246                 if (read_div_definition(s, v) < 0)
 247                         goto error;
 248         } else {
 249                 isl_stream_error(s, tok, "expecting factor");
 250                 goto error;
 251         }
 252         if (isl_stream_eat_if_available(s, '*')) {
 253                 isl_int f;
 254                 isl_int_init(f);
 255                 isl_int_set_si(f, 1);
 256                 if (accept_cst_factor(s, &f) < 0) {
 257                         isl_int_clear(f);
 258                         goto error;
 259                 }
 260                 aff = isl_vec_scale(aff, f);
 261                 isl_int_clear(f);
 262         }
 263
 264         return aff;
 265 error:
 266         isl_token_free(tok);
 267         isl_vec_free(aff);
 268         return NULL;
 269 }
 270
 271 static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v)
 272 {
 273         struct isl_token *tok = NULL;
 274         struct isl_vec *aff;
 275         int sign = 1;
 276
 277         aff = isl_vec_alloc(v->ctx, 1 + v->n);
 278         if (!aff)
 279                 return NULL;
 280         isl_seq_clr(aff->el, aff->size);
 281
 282         for (;;) {
 283                 tok = isl_stream_next_token(s);
 284                 if (!tok) {
 285                         isl_stream_error(s, NULL, "unexpected EOF");
 286                         goto error;
 287                 }
 288                 if (tok->type == '-') {
 289                         sign = -sign;
 290                         isl_token_free(tok);
 291                         continue;
 292                 }
 293                 if (tok->type == '(' || tok->type == '[' ||
 294                     tok->type == ISL_TOKEN_IDENT) {
 295                         isl_vec *aff2;
 296                         isl_stream_push_token(s, tok);
 297                         tok = NULL;
 298                         aff2 = accept_affine_factor(s, v);
 299                         if (sign < 0)
 300                                 aff2 = isl_vec_scale(aff2, s->ctx->negone);
 301                         aff = isl_vec_zero_extend(aff, 1 + v->n);
 302                         aff = isl_vec_add(aff, aff2);
 303                         if (!aff)
 304                                 goto error;
 305                         sign = 1;
 306                 } else if (tok->type == ISL_TOKEN_VALUE) {
 307                         if (sign < 0)
 308                                 isl_int_neg(tok->u.v, tok->u.v);
 309                         if (isl_stream_eat_if_available(s, '*') ||
 310                             isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
 311                                 isl_vec *aff2;
 312                                 aff2 = accept_affine_factor(s, v);
 313                                 aff2 = isl_vec_scale(aff2, tok->u.v);
 314                                 aff = isl_vec_zero_extend(aff, 1 + v->n);
 315                                 aff = isl_vec_add(aff, aff2);
 316                                 if (!aff)
 317                                         goto error;
 318                         } else {
 319                                 isl_int_add(aff->el[0], aff->el[0], tok->u.v);
 320                         }
 321                         sign = 1;
 322                 } else {
 323                         isl_stream_error(s, tok, "unexpected isl_token");
 324                         isl_stream_push_token(s, tok);
 325                         isl_vec_free(aff);
 326                         return NULL;
 327                 }
 328                 isl_token_free(tok);
 329
 330                 tok = isl_stream_next_token(s);
 331                 if (tok && tok->type == '-') {
 332                         sign = -sign;
 333                         isl_token_free(tok);
 334                 } else if (tok && tok->type == '+') {
 335                         /* nothing */
 336                         isl_token_free(tok);
 337                 } else if (tok && tok->type == ISL_TOKEN_VALUE &&
 338                            isl_int_is_neg(tok->u.v)) {
 339                         isl_stream_push_token(s, tok);
 340                 } else {
 341                         if (tok)
 342                                 isl_stream_push_token(s, tok);
 343                         break;
 344                 }
 345         }
 346
 347         return aff;
 348 error:
 349         isl_token_free(tok);
 350         isl_vec_free(aff);
 351         return NULL;
 352 }
 353
 354 /* Add any variables in the variable list "v" that are not already in "bmap"
 355  * as existentially quantified variables in "bmap".
 356  */
 357 static __isl_give isl_basic_map *add_divs(__isl_take isl_basic_map *bmap,
 358         struct vars *v)
 359 {
 360         int i;
 361         int extra;
 362         struct variable *var;
 363
 364         extra = v->n - isl_basic_map_total_dim(bmap);
 365
 366         if (extra == 0)
 367                 return bmap;
 368
 369         bmap = isl_basic_map_extend_dim(bmap, isl_basic_map_get_dim(bmap),
 370                                         extra, 0, 2 * extra);
 371
 372         for (i = 0; i < extra; ++i)
 373                 if (isl_basic_map_alloc_div(bmap) < 0)
 374                         goto error;
 375
 376         for (i = 0, var = v->v; i < extra; ++i, var = var->next) {
 377                 int k = bmap->n_div - 1 - i;
 378
 379                 isl_seq_cpy(bmap->div[k], var->def->el, 2 + var->pos);
 380                 isl_seq_clr(bmap->div[k] + 2 + var->pos, v->n - var->pos);
 381
 382                 if (isl_basic_map_add_div_constraints(bmap, k) < 0)
 383                         goto error;
 384         }
 385
 386         return bmap;
 387 error:
 388         isl_basic_map_free(bmap);
 389         return NULL;
 390 }
 391
 392 static __isl_give isl_basic_map *read_var_def(struct isl_stream *s,
 393         __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
 394 {
 395         struct isl_vec *vec;
 396         int k;
 397         int n;
 398
 399         if (vars_add_anon(v) < 0)
 400                 goto error;
 401         n = v->n;
 402
 403         vec = accept_affine(s, v);
 404         if (!vec)
 405                 goto error;
 406
 407         bmap = add_divs(bmap, v);
 408         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
 409         k = isl_basic_map_alloc_equality(bmap);
 410         if (k >= 0) {
 411                 isl_seq_cpy(bmap->eq[k], vec->el, vec->size);
 412                 isl_int_set_si(bmap->eq[k][1 + n - 1], -1);
 413         }
 414         isl_vec_free(vec);
 415         if (k < 0)
 416                 goto error;
 417
 418         vars_drop(v, v->n - n);
 419
 420         return bmap;
 421 error:
 422         isl_basic_map_free(bmap);
 423         return NULL;
 424 }
 425
 426 static __isl_give isl_basic_map *read_var_list(struct isl_stream *s,
 427         __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
 428 {
 429         int i = 0;
 430         struct isl_token *tok;
 431
 432         while ((tok = isl_stream_next_token(s)) != NULL) {
 433                 int new_name = 0;
 434
 435                 if (tok->type == ISL_TOKEN_IDENT) {
 436                         int n = v->n;
 437                         int p = vars_pos(v, tok->u.s, -1);
 438                         if (p < 0)
 439                                 goto error;
 440                         new_name = p >= n;
 441                 }
 442
 443                 if (new_name) {
 444                         bmap = isl_basic_map_add(bmap, type, 1);
 445                         bmap = set_name(bmap, type, i, v->v->name);
 446                         isl_token_free(tok);
 447                 } else if (tok->type == ISL_TOKEN_IDENT ||
 448                            tok->type == ISL_TOKEN_VALUE ||
 449                            tok->type == '-' ||
 450                            tok->type == '(') {
 451                         if (type == isl_dim_param) {
 452                                 isl_stream_error(s, tok,
 453                                                 "expecting unique identifier");
 454                                 goto error;
 455                         }
 456                         isl_stream_push_token(s, tok);
 457                         tok = NULL;
 458                         bmap = isl_basic_map_add(bmap, type, 1);
 459                         bmap = read_var_def(s, bmap, type, v);
 460                 } else
 461                         break;
 462
 463                 tok = isl_stream_next_token(s);
 464                 if (!tok || tok->type != ',')
 465                         break;
 466
 467                 isl_token_free(tok);
 468                 i++;
 469         }
 470         if (tok)
 471                 isl_stream_push_token(s, tok);
 472
 473         bmap = isl_basic_map_simplify(bmap);
 474         bmap = isl_basic_map_finalize(bmap);
 475         return bmap;
 476 error:
 477         isl_token_free(tok);
 478         isl_basic_map_free(bmap);
 479         return NULL;
 480 }
 481
 482 static __isl_give isl_mat *accept_affine_list(struct isl_stream *s,
 483         struct vars *v)
 484 {
 485         struct isl_vec *vec;
 486         struct isl_mat *mat;
 487         struct isl_token *tok = NULL;
 488
 489         vec = accept_affine(s, v);
 490         mat = isl_mat_from_row_vec(vec);
 491         if (!mat)
 492                 return NULL;
 493
 494         for (;;) {
 495                 tok = isl_stream_next_token(s);
 496                 if (!tok) {
 497                         isl_stream_error(s, NULL, "unexpected EOF");
 498                         goto error;
 499                 }
 500                 if (tok->type != ',') {
 501                         isl_stream_push_token(s, tok);
 502                         break;
 503                 }
 504                 isl_token_free(tok);
 505
 506                 vec = accept_affine(s, v);
 507                 mat = isl_mat_add_zero_cols(mat, 1 + v->n - isl_mat_cols(mat));
 508                 mat = isl_mat_vec_concat(mat, vec);
 509                 if (!mat)
 510                         return NULL;
 511         }
 512
 513         return mat;
 514 error:
 515         isl_mat_free(mat);
 516         return NULL;
 517 }
 518
 519 static int read_div_definition(struct isl_stream *s, struct vars *v)
 520 {
 521         struct isl_token *tok;
 522         int seen_paren = 0;
 523         struct isl_vec *aff;
 524         struct variable *var;
 525
 526         if (isl_stream_eat(s, '['))
 527                 return -1;
 528
 529         tok = isl_stream_next_token(s);
 530         if (!tok)
 531                 return -1;
 532         if (tok->type == '(') {
 533                 seen_paren = 1;
 534                 isl_token_free(tok);
 535         } else
 536                 isl_stream_push_token(s, tok);
 537
 538         var = v->v;
 539
 540         aff = accept_affine(s, v);
 541         if (!aff)
 542                 return -1;
 543
 544         var->def = isl_vec_alloc(s->ctx, 2 + v->n);
 545         if (!var->def) {
 546                 isl_vec_free(aff);
 547                 return -1;
 548         }
 549
 550         isl_seq_cpy(var->def->el + 1, aff->el, aff->size);
 551
 552         isl_vec_free(aff);
 553
 554         if (seen_paren && isl_stream_eat(s, ')'))
 555                 return -1;
 556         if (isl_stream_eat(s, '/'))
 557                 return -1;
 558
 559         tok = isl_stream_next_token(s);
 560         if (!tok)
 561                 return -1;
 562         if (tok->type != ISL_TOKEN_VALUE) {
 563                 isl_stream_error(s, tok, "expected denominator");
 564                 isl_stream_push_token(s, tok);
 565                 return -1;
 566         }
 567         isl_int_set(var->def->el[0], tok->u.v);
 568         isl_token_free(tok);
 569
 570         if (isl_stream_eat(s, ']'))
 571                 return -1;
 572
 573         return 0;
 574 }
 575
 576 static struct isl_basic_map *add_div_definition(struct isl_stream *s,
 577         struct vars *v, struct isl_basic_map *bmap, int k)
 578 {
 579         struct variable *var = v->v;
 580
 581         if (read_div_definition(s, v) < 0)
 582                 goto error;
 583
 584         isl_seq_cpy(bmap->div[k], var->def->el, 2 + v->n);
 585
 586         if (isl_basic_map_add_div_constraints(bmap, k) < 0)
 587                 goto error;
 588
 589         return bmap;
 590 error:
 591         isl_basic_map_free(bmap);
 592         return NULL;
 593 }
 594
 595 static struct isl_basic_map *read_defined_var_list(struct isl_stream *s,
 596         struct vars *v, struct isl_basic_map *bmap)
 597 {
 598         struct isl_token *tok;
 599
 600         while ((tok = isl_stream_next_token(s)) != NULL) {
 601                 int k;
 602                 int p;
 603                 int n = v->n;
 604                 unsigned total = isl_basic_map_total_dim(bmap);
 605
 606                 if (tok->type != ISL_TOKEN_IDENT)
 607                         break;
 608
 609                 p = vars_pos(v, tok->u.s, -1);
 610                 if (p < 0)
 611                         goto error;
 612                 if (p < n) {
 613                         isl_stream_error(s, tok, "expecting unique identifier");
 614                         goto error;
 615                 }
 616
 617                 bmap = isl_basic_map_cow(bmap);
 618                 bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
 619                                                 1, 0, 2);
 620
 621                 if ((k = isl_basic_map_alloc_div(bmap)) < 0)
 622                         goto error;
 623                 isl_seq_clr(bmap->div[k], 1 + 1 + total);
 624
 625                 isl_token_free(tok);
 626                 tok = isl_stream_next_token(s);
 627                 if (tok && tok->type == '=') {
 628                         isl_token_free(tok);
 629                         bmap = add_div_definition(s, v, bmap, k);
 630                         tok = isl_stream_next_token(s);
 631                 }
 632
 633                 if (!tok || tok->type != ',')
 634                         break;
 635
 636                 isl_token_free(tok);
 637         }
 638         if (tok)
 639                 isl_stream_push_token(s, tok);
 640
 641         return bmap;
 642 error:
 643         isl_token_free(tok);
 644         isl_basic_map_free(bmap);
 645         return NULL;
 646 }
 647
 648 static int next_is_tuple(struct isl_stream *s)
 649 {
 650         struct isl_token *tok;
 651         int is_tuple;
 652
 653         tok = isl_stream_next_token(s);
 654         if (!tok)
 655                 return 0;
 656         if (tok->type == '[') {
 657                 isl_stream_push_token(s, tok);
 658                 return 1;
 659         }
 660         if (tok->type != ISL_TOKEN_IDENT) {
 661                 isl_stream_push_token(s, tok);
 662                 return 0;
 663         }
 664
 665         is_tuple = isl_stream_next_token_is(s, '[');
 666
 667         isl_stream_push_token(s, tok);
 668
 669         return is_tuple;
 670 }
 671
 672 static __isl_give isl_basic_map *read_tuple(struct isl_stream *s,
 673         __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v);
 674
 675 static __isl_give isl_basic_map *read_nested_tuple(struct isl_stream *s,
 676         __isl_take isl_basic_map *bmap, struct vars *v)
 677 {
 678         bmap = read_tuple(s, bmap, isl_dim_in, v);
 679         if (isl_stream_eat(s, ISL_TOKEN_TO))
 680                 goto error;
 681         bmap = read_tuple(s, bmap, isl_dim_out, v);
 682         bmap = isl_basic_map_from_range(isl_basic_map_wrap(bmap));
 683         return bmap;
 684 error:
 685         isl_basic_map_free(bmap);
 686         return NULL;
 687 }
 688
 689 static __isl_give isl_basic_map *read_tuple(struct isl_stream *s,
 690         __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
 691 {
 692         struct isl_token *tok;
 693         char *name = NULL;
 694
 695         tok = isl_stream_next_token(s);
 696         if (tok && tok->type == ISL_TOKEN_IDENT) {
 697                 name = strdup(tok->u.s);
 698                 if (!name)
 699                         goto error;
 700                 isl_token_free(tok);
 701                 tok = isl_stream_next_token(s);
 702         }
 703         if (!tok || tok->type != '[') {
 704                 isl_stream_error(s, tok, "expecting '['");
 705                 goto error;
 706         }
 707         isl_token_free(tok);
 708         if (type != isl_dim_param && next_is_tuple(s)) {
 709                 isl_dim *dim = isl_basic_map_get_dim(bmap);
 710                 int nparam = isl_dim_size(dim, isl_dim_param);
 711                 int n_in = isl_dim_size(dim, isl_dim_in);
 712                 isl_basic_map *nested;
 713                 if (type == isl_dim_out)
 714                         dim = isl_dim_move(dim, isl_dim_param, nparam,
 715                                                 isl_dim_in, 0, n_in);
 716                 nested = isl_basic_map_alloc_dim(dim, 0, 0, 0);
 717                 nested = read_nested_tuple(s, nested, v);
 718                 if (type == isl_dim_in) {
 719                         nested = isl_basic_map_reverse(nested);
 720                         bmap = isl_basic_map_intersect(nested, bmap);
 721                 } else {
 722                         isl_basic_set *bset;
 723                         dim = isl_dim_range(isl_basic_map_get_dim(nested));
 724                         dim = isl_dim_drop(dim, isl_dim_param, nparam, n_in);
 725                         dim = isl_dim_join(isl_basic_map_get_dim(bmap), dim);
 726                         bset = isl_basic_map_domain(bmap);
 727                         nested = isl_basic_map_reset_dim(nested, dim);
 728                         bmap = isl_basic_map_intersect_domain(nested, bset);
 729                 }
 730         } else
 731                 bmap = read_var_list(s, bmap, type, v);
 732         tok = isl_stream_next_token(s);
 733         if (!tok || tok->type != ']') {
 734                 isl_stream_error(s, tok, "expecting ']'");
 735                 goto error;
 736         }
 737         isl_token_free(tok);
 738
 739         if (name) {
 740                 bmap = isl_basic_map_set_tuple_name(bmap, type, name);
 741                 free(name);
 742         }
 743
 744         return bmap;
 745 error:
 746         if (tok)
 747                 isl_token_free(tok);
 748         isl_basic_map_free(bmap);
 749         return NULL;
 750 }
 751
 752 static struct isl_basic_map *add_constraints(struct isl_stream *s,
 753         struct vars *v, struct isl_basic_map *bmap);
 754
 755 static struct isl_basic_map *add_exists(struct isl_stream *s,
 756         struct vars *v, struct isl_basic_map *bmap)
 757 {
 758         struct isl_token *tok;
 759         int n = v->n;
 760         int extra;
 761         int seen_paren = 0;
 762         int i;
 763         unsigned total;
 764
 765         tok = isl_stream_next_token(s);
 766         if (!tok)
 767                 goto error;
 768         if (tok->type == '(') {
 769                 seen_paren = 1;
 770                 isl_token_free(tok);
 771         } else
 772                 isl_stream_push_token(s, tok);
 773
 774         bmap = read_defined_var_list(s, v, bmap);
 775         if (!bmap)
 776                 goto error;
 777
 778         if (isl_stream_eat(s, ':'))
 779                 goto error;
 780         bmap = add_constraints(s, v, bmap);
 781         if (seen_paren && isl_stream_eat(s, ')'))
 782                 goto error;
 783         return bmap;
 784 error:
 785         isl_basic_map_free(bmap);
 786         return NULL;
 787 }
 788
 789 static __isl_give isl_basic_map *construct_constraint(
 790         __isl_take isl_basic_map *bmap, enum isl_token_type type,
 791         isl_int *left, isl_int *right)
 792 {
 793         int k;
 794         unsigned len;
 795         struct isl_ctx *ctx;
 796
 797         if (!bmap)
 798                 return NULL;
 799         len = 1 + isl_basic_map_total_dim(bmap);
 800         ctx = bmap->ctx;
 801
 802         k = isl_basic_map_alloc_inequality(bmap);
 803         if (k < 0)
 804                 goto error;
 805         if (type == ISL_TOKEN_LE)
 806                 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
 807                                                ctx->one, right,
 808                                                len);
 809         else if (type == ISL_TOKEN_GE)
 810                 isl_seq_combine(bmap->ineq[k], ctx->one, left,
 811                                                ctx->negone, right,
 812                                                len);
 813         else if (type == ISL_TOKEN_LT) {
 814                 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
 815                                                ctx->one, right,
 816                                                len);
 817                 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
 818         } else if (type == ISL_TOKEN_GT) {
 819                 isl_seq_combine(bmap->ineq[k], ctx->one, left,
 820                                                ctx->negone, right,
 821                                                len);
 822                 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
 823         } else {
 824                 isl_seq_combine(bmap->ineq[k], ctx->one, left,
 825                                                ctx->negone, right,
 826                                                len);
 827                 isl_basic_map_inequality_to_equality(bmap, k);
 828         }
 829
 830         return bmap;
 831 error:
 832         isl_basic_map_free(bmap);
 833         return NULL;
 834 }
 835
 836 static int is_comparator(struct isl_token *tok)
 837 {
 838         if (!tok)
 839                 return 0;
 840
 841         switch (tok->type) {
 842         case ISL_TOKEN_LT:
 843         case ISL_TOKEN_GT:
 844         case ISL_TOKEN_LE:
 845         case ISL_TOKEN_GE:
 846         case '=':
 847                 return 1;
 848         default:
 849                 return 0;
 850         }
 851 }
 852
 853 static struct isl_basic_map *add_constraint(struct isl_stream *s,
 854         struct vars *v, struct isl_basic_map *bmap)
 855 {
 856         int i, j;
 857         struct isl_token *tok = NULL;
 858         struct isl_mat *aff1 = NULL, *aff2 = NULL;
 859
 860         tok = isl_stream_next_token(s);
 861         if (!tok)
 862                 goto error;
 863         if (tok->type == ISL_TOKEN_EXISTS) {
 864                 isl_token_free(tok);
 865                 return add_exists(s, v, bmap);
 866         }
 867         isl_stream_push_token(s, tok);
 868         tok = NULL;
 869
 870         bmap = isl_basic_map_cow(bmap);
 871
 872         aff1 = accept_affine_list(s, v);
 873         if (!aff1)
 874                 goto error;
 875         tok = isl_stream_next_token(s);
 876         if (!is_comparator(tok)) {
 877                 isl_stream_error(s, tok, "missing operator");
 878                 if (tok)
 879                         isl_stream_push_token(s, tok);
 880                 tok = NULL;
 881                 goto error;
 882         }
 883         for (;;) {
 884                 aff2 = accept_affine_list(s, v);
 885                 if (!aff2)
 886                         goto error;
 887
 888                 aff1 = isl_mat_add_zero_cols(aff1, aff2->n_col - aff1->n_col);
 889                 if (!aff1)
 890                         goto error;
 891                 bmap = add_divs(bmap, v);
 892                 bmap = isl_basic_map_extend_constraints(bmap, 0,
 893                                                 aff1->n_row * aff2->n_row);
 894                 for (i = 0; i < aff1->n_row; ++i)
 895                         for (j = 0; j < aff2->n_row; ++j)
 896                                 bmap = construct_constraint(bmap, tok->type,
 897                                                     aff1->row[i], aff2->row[j]);
 898                 isl_token_free(tok);
 899                 isl_mat_free(aff1);
 900                 aff1 = aff2;
 901
 902                 tok = isl_stream_next_token(s);
 903                 if (!is_comparator(tok)) {
 904                         if (tok)
 905                                 isl_stream_push_token(s, tok);
 906                         break;
 907                 }
 908         }
 909         isl_mat_free(aff1);
 910
 911         return bmap;
 912 error:
 913         if (tok)
 914                 isl_token_free(tok);
 915         isl_mat_free(aff1);
 916         isl_mat_free(aff2);
 917         isl_basic_map_free(bmap);
 918         return NULL;
 919 }
 920
 921 static struct isl_basic_map *add_constraints(struct isl_stream *s,
 922         struct vars *v, struct isl_basic_map *bmap)
 923 {
 924         struct isl_token *tok;
 925
 926         for (;;) {
 927                 bmap = add_constraint(s, v, bmap);
 928                 if (!bmap)
 929                         return NULL;
 930                 tok = isl_stream_next_token(s);
 931                 if (!tok) {
 932                         isl_stream_error(s, NULL, "unexpected EOF");
 933                         goto error;
 934                 }
 935                 if (tok->type != ISL_TOKEN_AND)
 936                         break;
 937                 isl_token_free(tok);
 938         }
 939         isl_stream_push_token(s, tok);
 940
 941         return bmap;
 942 error:
 943         if (tok)
 944                 isl_token_free(tok);
 945         isl_basic_map_free(bmap);
 946         return NULL;
 947 }
 948
 949 static struct isl_basic_map *read_disjunct(struct isl_stream *s,
 950         struct vars *v, __isl_take isl_dim *dim)
 951 {
 952         int seen_paren = 0;
 953         struct isl_token *tok;
 954         struct isl_basic_map *bmap;
 955
 956         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
 957         if (!bmap)
 958                 return NULL;
 959
 960         tok = isl_stream_next_token(s);
 961         if (!tok)
 962                 goto error;
 963         if (tok->type == '(') {
 964                 seen_paren = 1;
 965                 isl_token_free(tok);
 966         } else
 967                 isl_stream_push_token(s, tok);
 968
 969         bmap = add_constraints(s, v, bmap);
 970         bmap = isl_basic_map_simplify(bmap);
 971         bmap = isl_basic_map_finalize(bmap);
 972
 973         if (seen_paren && isl_stream_eat(s, ')'))
 974                 goto error;
 975
 976         return bmap;
 977 error:
 978         isl_basic_map_free(bmap);
 979         return NULL;
 980 }
 981
 982 static struct isl_map *read_disjuncts(struct isl_stream *s,
 983         struct vars *v, __isl_take isl_dim *dim)
 984 {
 985         struct isl_token *tok;
 986         struct isl_map *map;
 987
 988         tok = isl_stream_next_token(s);
 989         if (!tok) {
 990                 isl_stream_error(s, NULL, "unexpected EOF");
 991                 goto error;
 992         }
 993         if (tok->type == '}') {
 994                 isl_stream_push_token(s, tok);
 995                 return isl_map_universe(dim);
 996         }
 997         isl_stream_push_token(s, tok);
 998
 999         map = isl_map_empty(isl_dim_copy(dim));
1000         for (;;) {
1001                 struct isl_basic_map *bmap;
1002                 int n = v->n;
1003
1004                 bmap = read_disjunct(s, v, isl_dim_copy(dim));
1005                 map = isl_map_union(map, isl_map_from_basic_map(bmap));
1006
1007                 vars_drop(v, v->n - n);
1008
1009                 tok = isl_stream_next_token(s);
1010                 if (!tok || tok->type != ISL_TOKEN_OR)
1011                         break;
1012                 isl_token_free(tok);
1013         }
1014         if (tok)
1015                 isl_stream_push_token(s, tok);
1016
1017         isl_dim_free(dim);
1018         return map;
1019 error:
1020         isl_dim_free(dim);
1021         return NULL;
1022 }
1023
1024 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1025 {
1026         if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1027                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1028                            isl_basic_map_dim(bmap, isl_dim_in) + pos;
1029         pos -= isl_basic_map_dim(bmap, isl_dim_out);
1030
1031         if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1032                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1033         pos -= isl_basic_map_dim(bmap, isl_dim_in);
1034
1035         if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1036                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1037                            isl_basic_map_dim(bmap, isl_dim_in) +
1038                            isl_basic_map_dim(bmap, isl_dim_out) + pos;
1039         pos -= isl_basic_map_dim(bmap, isl_dim_div);
1040
1041         if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1042                 return 1 + pos;
1043
1044         return 0;
1045 }
1046
1047 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1048         struct isl_stream *s, __isl_take isl_basic_map *bmap)
1049 {
1050         int j;
1051         struct isl_token *tok;
1052         int type;
1053         int k;
1054         isl_int *c;
1055         unsigned nparam;
1056         unsigned dim;
1057
1058         if (!bmap)
1059                 return NULL;
1060
1061         nparam = isl_basic_map_dim(bmap, isl_dim_param);
1062         dim = isl_basic_map_dim(bmap, isl_dim_out);
1063
1064         tok = isl_stream_next_token(s);
1065         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1066                 isl_stream_error(s, tok, "expecting coefficient");
1067                 if (tok)
1068                         isl_stream_push_token(s, tok);
1069                 goto error;
1070         }
1071         if (!tok->on_new_line) {
1072                 isl_stream_error(s, tok, "coefficient should appear on new line");
1073                 isl_stream_push_token(s, tok);
1074                 goto error;
1075         }
1076
1077         type = isl_int_get_si(tok->u.v);
1078         isl_token_free(tok);
1079
1080         isl_assert(s->ctx, type == 0 || type == 1, goto error);
1081         if (type == 0) {
1082                 k = isl_basic_map_alloc_equality(bmap);
1083                 c = bmap->eq[k];
1084         } else {
1085                 k = isl_basic_map_alloc_inequality(bmap);
1086                 c = bmap->ineq[k];
1087         }
1088         if (k < 0)
1089                 goto error;
1090
1091         for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1092                 int pos;
1093                 tok = isl_stream_next_token(s);
1094                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1095                         isl_stream_error(s, tok, "expecting coefficient");
1096                         if (tok)
1097                                 isl_stream_push_token(s, tok);
1098                         goto error;
1099                 }
1100                 if (tok->on_new_line) {
1101                         isl_stream_error(s, tok,
1102                                 "coefficient should not appear on new line");
1103                         isl_stream_push_token(s, tok);
1104                         goto error;
1105                 }
1106                 pos = polylib_pos_to_isl_pos(bmap, j);
1107                 isl_int_set(c[pos], tok->u.v);
1108                 isl_token_free(tok);
1109         }
1110
1111         return bmap;
1112 error:
1113         isl_basic_map_free(bmap);
1114         return NULL;
1115 }
1116
1117 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s,
1118         int nparam)
1119 {
1120         int i;
1121         struct isl_token *tok;
1122         struct isl_token *tok2;
1123         int n_row, n_col;
1124         int on_new_line;
1125         unsigned in = 0, out, local = 0;
1126         struct isl_basic_map *bmap = NULL;
1127
1128         if (nparam < 0)
1129                 nparam = 0;
1130
1131         tok = isl_stream_next_token(s);
1132         if (!tok) {
1133                 isl_stream_error(s, NULL, "unexpected EOF");
1134                 return NULL;
1135         }
1136         tok2 = isl_stream_next_token(s);
1137         if (!tok2) {
1138                 isl_token_free(tok);
1139                 isl_stream_error(s, NULL, "unexpected EOF");
1140                 return NULL;
1141         }
1142         n_row = isl_int_get_si(tok->u.v);
1143         n_col = isl_int_get_si(tok2->u.v);
1144         on_new_line = tok2->on_new_line;
1145         isl_token_free(tok2);
1146         isl_token_free(tok);
1147         isl_assert(s->ctx, !on_new_line, return NULL);
1148         isl_assert(s->ctx, n_row >= 0, return NULL);
1149         isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1150         tok = isl_stream_next_token_on_same_line(s);
1151         if (tok) {
1152                 if (tok->type != ISL_TOKEN_VALUE) {
1153                         isl_stream_error(s, tok,
1154                                     "expecting number of output dimensions");
1155                         isl_stream_push_token(s, tok);
1156                         goto error;
1157                 }
1158                 out = isl_int_get_si(tok->u.v);
1159                 isl_token_free(tok);
1160
1161                 tok = isl_stream_next_token_on_same_line(s);
1162                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1163                         isl_stream_error(s, tok,
1164                                     "expecting number of input dimensions");
1165                         if (tok)
1166                                 isl_stream_push_token(s, tok);
1167                         goto error;
1168                 }
1169                 in = isl_int_get_si(tok->u.v);
1170                 isl_token_free(tok);
1171
1172                 tok = isl_stream_next_token_on_same_line(s);
1173                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1174                         isl_stream_error(s, tok,
1175                                     "expecting number of existentials");
1176                         if (tok)
1177                                 isl_stream_push_token(s, tok);
1178                         goto error;
1179                 }
1180                 local = isl_int_get_si(tok->u.v);
1181                 isl_token_free(tok);
1182
1183                 tok = isl_stream_next_token_on_same_line(s);
1184                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1185                         isl_stream_error(s, tok,
1186                                     "expecting number of parameters");
1187                         if (tok)
1188                                 isl_stream_push_token(s, tok);
1189                         goto error;
1190                 }
1191                 nparam = isl_int_get_si(tok->u.v);
1192                 isl_token_free(tok);
1193                 if (n_col != 1 + out + in + local + nparam + 1) {
1194                         isl_stream_error(s, NULL,
1195                                     "dimensions don't match");
1196                         goto error;
1197                 }
1198         } else
1199                 out = n_col - 2 - nparam;
1200         bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1201         if (!bmap)
1202                 return NULL;
1203
1204         for (i = 0; i < local; ++i) {
1205                 int k = isl_basic_map_alloc_div(bmap);
1206                 if (k < 0)
1207                         goto error;
1208                 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1209         }
1210
1211         for (i = 0; i < n_row; ++i)
1212                 bmap = basic_map_read_polylib_constraint(s, bmap);
1213
1214         tok = isl_stream_next_token_on_same_line(s);
1215         if (tok) {
1216                 isl_stream_error(s, tok, "unexpected extra token on line");
1217                 isl_stream_push_token(s, tok);
1218                 goto error;
1219         }
1220
1221         bmap = isl_basic_map_simplify(bmap);
1222         bmap = isl_basic_map_finalize(bmap);
1223         return bmap;
1224 error:
1225         isl_basic_map_free(bmap);
1226         return NULL;
1227 }
1228
1229 static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam)
1230 {
1231         struct isl_token *tok;
1232         struct isl_token *tok2;
1233         int i, n;
1234         struct isl_map *map;
1235
1236         tok = isl_stream_next_token(s);
1237         if (!tok) {
1238                 isl_stream_error(s, NULL, "unexpected EOF");
1239                 return NULL;
1240         }
1241         tok2 = isl_stream_next_token_on_same_line(s);
1242         if (tok2) {
1243                 isl_stream_push_token(s, tok2);
1244                 isl_stream_push_token(s, tok);
1245                 return isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
1246         }
1247         n = isl_int_get_si(tok->u.v);
1248         isl_token_free(tok);
1249
1250         isl_assert(s->ctx, n >= 1, return NULL);
1251
1252         map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
1253
1254         for (i = 1; i < n; ++i)
1255                 map = isl_map_union(map,
1256                         isl_map_from_basic_map(basic_map_read_polylib(s, nparam)));
1257
1258         return map;
1259 }
1260
1261 static int optional_power(struct isl_stream *s)
1262 {
1263         int pow;
1264         struct isl_token *tok;
1265
1266         tok = isl_stream_next_token(s);
1267         if (!tok)
1268                 return 1;
1269         if (tok->type != '^') {
1270                 isl_stream_push_token(s, tok);
1271                 return 1;
1272         }
1273         isl_token_free(tok);
1274         tok = isl_stream_next_token(s);
1275         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1276                 isl_stream_error(s, tok, "expecting exponent");
1277                 if (tok)
1278                         isl_stream_push_token(s, tok);
1279                 return 1;
1280         }
1281         pow = isl_int_get_si(tok->u.v);
1282         isl_token_free(tok);
1283         return pow;
1284 }
1285
1286 static __isl_give isl_div *read_div(struct isl_stream *s,
1287         __isl_keep isl_basic_map *bmap, struct vars *v)
1288 {
1289         unsigned total = isl_basic_map_total_dim(bmap);
1290         int k;
1291
1292         bmap = isl_basic_map_copy(bmap);
1293         bmap = isl_basic_map_cow(bmap);
1294         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
1295                                         1, 0, 2);
1296
1297         if ((k = isl_basic_map_alloc_div(bmap)) < 0)
1298                 goto error;
1299         isl_seq_clr(bmap->div[k], 1 + 1 + total);
1300
1301         if (vars_add_anon(v) < 0)
1302                 goto error;
1303         bmap = add_div_definition(s, v, bmap, k);
1304         vars_drop(v, 1);
1305
1306         return isl_basic_map_div(bmap, k);
1307 error:
1308         isl_basic_map_free(bmap);
1309         return NULL;
1310 }
1311
1312 static __isl_give isl_qpolynomial *read_term(struct isl_stream *s,
1313         __isl_keep isl_basic_map *bmap, struct vars *v);
1314
1315 static __isl_give isl_qpolynomial *read_factor(struct isl_stream *s,
1316         __isl_keep isl_basic_map *bmap, struct vars *v)
1317 {
1318         struct isl_qpolynomial *qp;
1319         struct isl_token *tok;
1320
1321         tok = isl_stream_next_token(s);
1322         if (!tok) {
1323                 isl_stream_error(s, NULL, "unexpected EOF");
1324                 return NULL;
1325         }
1326         if (tok->type == '(') {
1327                 isl_token_free(tok);
1328                 qp = read_term(s, bmap, v);
1329                 if (!qp)
1330                         return NULL;
1331                 if (isl_stream_eat(s, ')'))
1332                         goto error;
1333         } else if (tok->type == ISL_TOKEN_VALUE) {
1334                 struct isl_token *tok2;
1335                 tok2 = isl_stream_next_token(s);
1336                 if (tok2 && tok2->type == '/') {
1337                         isl_token_free(tok2);
1338                         tok2 = isl_stream_next_token(s);
1339                         if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1340                                 isl_stream_error(s, tok2, "expected denominator");
1341                                 isl_token_free(tok);
1342                                 isl_token_free(tok2);
1343                                 return NULL;
1344                         }
1345                         qp = isl_qpolynomial_rat_cst(isl_basic_map_get_dim(bmap),
1346                                                     tok->u.v, tok2->u.v);
1347                         isl_token_free(tok2);
1348                 } else {
1349                         isl_stream_push_token(s, tok2);
1350                         qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1351                                                 tok->u.v);
1352                 }
1353                 isl_token_free(tok);
1354         } else if (tok->type == ISL_TOKEN_INFTY) {
1355                 isl_token_free(tok);
1356                 qp = isl_qpolynomial_infty(isl_basic_map_get_dim(bmap));
1357         } else if (tok->type == ISL_TOKEN_NAN) {
1358                 isl_token_free(tok);
1359                 qp = isl_qpolynomial_nan(isl_basic_map_get_dim(bmap));
1360         } else if (tok->type == ISL_TOKEN_IDENT) {
1361                 int n = v->n;
1362                 int pos = vars_pos(v, tok->u.s, -1);
1363                 int pow;
1364                 if (pos < 0) {
1365                         isl_token_free(tok);
1366                         return NULL;
1367                 }
1368                 if (pos >= n) {
1369                         isl_stream_error(s, tok, "unknown identifier");
1370                         isl_token_free(tok);
1371                         return NULL;
1372                 }
1373                 isl_token_free(tok);
1374                 pow = optional_power(s);
1375                 qp = isl_qpolynomial_pow(isl_basic_map_get_dim(bmap), pos, pow);
1376         } else if (tok->type == '[') {
1377                 isl_div *div;
1378                 int pow;
1379
1380                 isl_stream_push_token(s, tok);
1381                 div = read_div(s, bmap, v);
1382                 pow = optional_power(s);
1383                 qp = isl_qpolynomial_div_pow(div, pow);
1384         } else if (tok->type == '-') {
1385                 struct isl_qpolynomial *qp2;
1386
1387                 isl_token_free(tok);
1388                 qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap),
1389                                             s->ctx->negone);
1390                 qp2 = read_factor(s, bmap, v);
1391                 qp = isl_qpolynomial_mul(qp, qp2);
1392         } else {
1393                 isl_stream_error(s, tok, "unexpected isl_token");
1394                 isl_stream_push_token(s, tok);
1395                 return NULL;
1396         }
1397
1398         if (isl_stream_eat_if_available(s, '*') ||
1399             isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1400                 struct isl_qpolynomial *qp2;
1401
1402                 qp2 = read_factor(s, bmap, v);
1403                 qp = isl_qpolynomial_mul(qp, qp2);
1404         }
1405
1406         return qp;
1407 error:
1408         isl_qpolynomial_free(qp);
1409         return NULL;
1410 }
1411
1412 static __isl_give isl_qpolynomial *read_term(struct isl_stream *s,
1413         __isl_keep isl_basic_map *bmap, struct vars *v)
1414 {
1415         struct isl_token *tok;
1416         struct isl_qpolynomial *qp;
1417
1418         qp = read_factor(s, bmap, v);
1419
1420         for (;;) {
1421                 tok = isl_stream_next_token(s);
1422                 if (!tok)
1423                         return qp;
1424
1425                 if (tok->type == '+') {
1426                         struct isl_qpolynomial *qp2;
1427
1428                         isl_token_free(tok);
1429                         qp2 = read_factor(s, bmap, v);
1430                         qp = isl_qpolynomial_add(qp, qp2);
1431                 } else if (tok->type == '-') {
1432                         struct isl_qpolynomial *qp2;
1433
1434                         isl_token_free(tok);
1435                         qp2 = read_factor(s, bmap, v);
1436                         qp = isl_qpolynomial_sub(qp, qp2);
1437                 } else if (tok->type == ISL_TOKEN_VALUE &&
1438                             isl_int_is_neg(tok->u.v)) {
1439                         struct isl_qpolynomial *qp2;
1440
1441                         isl_stream_push_token(s, tok);
1442                         qp2 = read_factor(s, bmap, v);
1443                         qp = isl_qpolynomial_add(qp, qp2);
1444                 } else {
1445                         isl_stream_push_token(s, tok);
1446                         break;
1447                 }
1448         }
1449
1450         return qp;
1451 }
1452
1453 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1454         __isl_take isl_basic_map *bmap, struct vars *v)
1455 {
1456         struct isl_token *tok;
1457         struct isl_map *map;
1458
1459         tok = isl_stream_next_token(s);
1460         if (!tok) {
1461                 isl_stream_error(s, NULL, "unexpected EOF");
1462                 goto error;
1463         }
1464         map = isl_map_from_basic_map(isl_basic_map_copy(bmap));
1465         if (tok->type == ':') {
1466                 isl_token_free(tok);
1467                 map = isl_map_intersect(map,
1468                             read_disjuncts(s, v, isl_basic_map_get_dim(bmap)));
1469         } else
1470                 isl_stream_push_token(s, tok);
1471
1472         isl_basic_map_free(bmap);
1473
1474         return map;
1475 error:
1476         isl_basic_map_free(bmap);
1477         return NULL;
1478 }
1479
1480 static struct isl_obj obj_read_poly(struct isl_stream *s,
1481         __isl_take isl_basic_map *bmap, struct vars *v, int n)
1482 {
1483         struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1484         struct isl_pw_qpolynomial *pwqp;
1485         struct isl_qpolynomial *qp;
1486         struct isl_map *map;
1487         struct isl_set *set;
1488
1489         qp = read_term(s, bmap, v);
1490         map = read_optional_disjuncts(s, bmap, v);
1491         set = isl_map_range(map);
1492
1493         pwqp = isl_pw_qpolynomial_alloc(set, qp);
1494
1495         vars_drop(v, v->n - n);
1496
1497         obj.v = pwqp;
1498         return obj;
1499 }
1500
1501 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1502         __isl_take isl_basic_map *bmap, struct vars *v, int n)
1503 {
1504         struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1505         struct isl_obj obj_p;
1506         isl_qpolynomial *qp;
1507         isl_qpolynomial_fold *fold = NULL;
1508         isl_pw_qpolynomial_fold *pwf;
1509         isl_map *map;
1510         isl_set *set;
1511
1512         if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1513                 return obj_read_poly(s, bmap, v, n);
1514
1515         if (isl_stream_eat(s, '('))
1516                 goto error;
1517
1518         qp = read_term(s, bmap, v);
1519         fold = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1520
1521         while (isl_stream_eat_if_available(s, ',')) {
1522                 isl_qpolynomial_fold *fold_i;
1523                 qp = read_term(s, bmap, v);
1524                 fold_i = isl_qpolynomial_fold_alloc(isl_fold_max, qp);
1525                 fold = isl_qpolynomial_fold_fold(fold, fold_i);
1526         }
1527
1528         if (isl_stream_eat(s, ')'))
1529                 goto error;
1530
1531         map = read_optional_disjuncts(s, bmap, v);
1532         set = isl_map_range(map);
1533         pwf = isl_pw_qpolynomial_fold_alloc(isl_fold_max, set, fold);
1534
1535         vars_drop(v, v->n - n);
1536
1537         obj.v = pwf;
1538         return obj;
1539 error:
1540         isl_basic_map_free(bmap);
1541         isl_qpolynomial_fold_free(fold);
1542         obj.type = isl_obj_none;
1543         return obj;
1544 }
1545
1546 static struct isl_obj obj_read_body(struct isl_stream *s,
1547         __isl_take isl_basic_map *bmap, struct vars *v)
1548 {
1549         struct isl_map *map = NULL;
1550         struct isl_token *tok;
1551         struct isl_obj obj = { isl_obj_set, NULL };
1552         int n = v->n;
1553
1554         if (!next_is_tuple(s))
1555                 return obj_read_poly_or_fold(s, bmap, v, n);
1556
1557         bmap = read_tuple(s, bmap, isl_dim_in, v);
1558         if (!bmap)
1559                 goto error;
1560         tok = isl_stream_next_token(s);
1561         if (tok && tok->type == ISL_TOKEN_TO) {
1562                 obj.type = isl_obj_map;
1563                 isl_token_free(tok);
1564                 if (!next_is_tuple(s)) {
1565                         bmap = isl_basic_map_reverse(bmap);
1566                         return obj_read_poly_or_fold(s, bmap, v, n);
1567                 }
1568                 bmap = read_tuple(s, bmap, isl_dim_out, v);
1569                 if (!bmap)
1570                         goto error;
1571         } else {
1572                 bmap = isl_basic_map_reverse(bmap);
1573                 if (tok)
1574                         isl_stream_push_token(s, tok);
1575         }
1576
1577         map = read_optional_disjuncts(s, bmap, v);
1578
1579         vars_drop(v, v->n - n);
1580
1581         obj.v = map;
1582         return obj;
1583 error:
1584         isl_basic_map_free(bmap);
1585         obj.type = isl_obj_none;
1586         return obj;
1587 }
1588
1589 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
1590 {
1591         if (obj.type == isl_obj_map) {
1592                 obj.v = isl_union_map_from_map(obj.v);
1593                 obj.type = isl_obj_union_map;
1594         } else if (obj.type == isl_obj_set) {
1595                 obj.v = isl_union_set_from_set(obj.v);
1596                 obj.type = isl_obj_union_set;
1597         } else if (obj.type == isl_obj_pw_qpolynomial) {
1598                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
1599                 obj.type = isl_obj_union_pw_qpolynomial;
1600         } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
1601                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
1602                 obj.type = isl_obj_union_pw_qpolynomial_fold;
1603         } else
1604                 isl_assert(ctx, 0, goto error);
1605         return obj;
1606 error:
1607         obj.type->free(obj.v);
1608         obj.type = isl_obj_none;
1609         return obj;
1610 }
1611
1612 static struct isl_obj obj_add(struct isl_ctx *ctx,
1613         struct isl_obj obj1, struct isl_obj obj2)
1614 {
1615         if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
1616                 obj1 = to_union(ctx, obj1);
1617         if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
1618                 obj2 = to_union(ctx, obj2);
1619         if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
1620                 obj1 = to_union(ctx, obj1);
1621         if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
1622                 obj2 = to_union(ctx, obj2);
1623         if (obj1.type == isl_obj_pw_qpolynomial &&
1624             obj2.type == isl_obj_union_pw_qpolynomial)
1625                 obj1 = to_union(ctx, obj1);
1626         if (obj1.type == isl_obj_union_pw_qpolynomial &&
1627             obj2.type == isl_obj_pw_qpolynomial)
1628                 obj2 = to_union(ctx, obj2);
1629         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1630             obj2.type == isl_obj_union_pw_qpolynomial_fold)
1631                 obj1 = to_union(ctx, obj1);
1632         if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
1633             obj2.type == isl_obj_pw_qpolynomial_fold)
1634                 obj2 = to_union(ctx, obj2);
1635         isl_assert(ctx, obj1.type == obj2.type, goto error);
1636         if (obj1.type == isl_obj_map && !isl_map_has_equal_dim(obj1.v, obj2.v)) {
1637                 obj1 = to_union(ctx, obj1);
1638                 obj2 = to_union(ctx, obj2);
1639         }
1640         if (obj1.type == isl_obj_set && !isl_set_has_equal_dim(obj1.v, obj2.v)) {
1641                 obj1 = to_union(ctx, obj1);
1642                 obj2 = to_union(ctx, obj2);
1643         }
1644         if (obj1.type == isl_obj_pw_qpolynomial &&
1645             !isl_pw_qpolynomial_has_equal_dim(obj1.v, obj2.v)) {
1646                 obj1 = to_union(ctx, obj1);
1647                 obj2 = to_union(ctx, obj2);
1648         }
1649         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1650             !isl_pw_qpolynomial_fold_has_equal_dim(obj1.v, obj2.v)) {
1651                 obj1 = to_union(ctx, obj1);
1652                 obj2 = to_union(ctx, obj2);
1653         }
1654         obj1.v = obj1.type->add(obj1.v, obj2.v);
1655         return obj1;
1656 error:
1657         obj1.type->free(obj1.v);
1658         obj2.type->free(obj2.v);
1659         obj1.type = isl_obj_none;
1660         obj1.v = NULL;
1661         return obj1;
1662 }
1663
1664 static struct isl_obj obj_read(struct isl_stream *s, int nparam)
1665 {
1666         isl_basic_map *bmap = NULL;
1667         struct isl_token *tok;
1668         struct vars *v = NULL;
1669         struct isl_obj obj = { isl_obj_set, NULL };
1670
1671         tok = isl_stream_next_token(s);
1672         if (!tok) {
1673                 isl_stream_error(s, NULL, "unexpected EOF");
1674                 goto error;
1675         }
1676         if (tok->type == ISL_TOKEN_VALUE) {
1677                 struct isl_map *map;
1678                 isl_stream_push_token(s, tok);
1679                 map = map_read_polylib(s, nparam);
1680                 if (!map)
1681                         goto error;
1682                 if (isl_map_dim(map, isl_dim_in) > 0)
1683                         obj.type = isl_obj_map;
1684                 obj.v = map;
1685                 return obj;
1686         }
1687         v = vars_new(s->ctx);
1688         if (!v) {
1689                 isl_stream_push_token(s, tok);
1690                 goto error;
1691         }
1692         bmap = isl_basic_map_alloc(s->ctx, 0, 0, 0, 0, 0, 0);
1693         if (tok->type == '[') {
1694                 isl_stream_push_token(s, tok);
1695                 bmap = read_tuple(s, bmap, isl_dim_param, v);
1696                 if (!bmap)
1697                         goto error;
1698                 if (nparam >= 0)
1699                         isl_assert(s->ctx, nparam == v->n, goto error);
1700                 tok = isl_stream_next_token(s);
1701                 if (!tok || tok->type != ISL_TOKEN_TO) {
1702                         isl_stream_error(s, tok, "expecting '->'");
1703                         if (tok)
1704                                 isl_stream_push_token(s, tok);
1705                         goto error;
1706                 }
1707                 isl_token_free(tok);
1708                 tok = isl_stream_next_token(s);
1709         } else if (nparam > 0)
1710                 bmap = isl_basic_map_add(bmap, isl_dim_param, nparam);
1711         if (!tok || tok->type != '{') {
1712                 isl_stream_error(s, tok, "expecting '{'");
1713                 if (tok)
1714                         isl_stream_push_token(s, tok);
1715                 goto error;
1716         }
1717         isl_token_free(tok);
1718
1719         tok = isl_stream_next_token(s);
1720         if (!tok)
1721                 ;
1722         else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
1723                 isl_token_free(tok);
1724                 if (isl_stream_eat(s, '='))
1725                         goto error;
1726                 bmap = read_tuple(s, bmap, isl_dim_param, v);
1727                 if (!bmap)
1728                         goto error;
1729                 if (nparam >= 0)
1730                         isl_assert(s->ctx, nparam == v->n, goto error);
1731         } else if (tok->type == '}') {
1732                 obj.type = isl_obj_union_set;
1733                 obj.v = isl_union_set_empty(isl_basic_map_get_dim(bmap));
1734                 isl_token_free(tok);
1735                 goto done;
1736         } else
1737                 isl_stream_push_token(s, tok);
1738
1739         for (;;) {
1740                 struct isl_obj o;
1741                 tok = NULL;
1742                 o = obj_read_body(s, isl_basic_map_copy(bmap), v);
1743                 if (o.type == isl_obj_none || !o.v)
1744                         goto error;
1745                 if (!obj.v)
1746                         obj = o;
1747                 else {
1748                         obj = obj_add(s->ctx, obj, o);
1749                         if (obj.type == isl_obj_none || !obj.v)
1750                                 goto error;
1751                 }
1752                 tok = isl_stream_next_token(s);
1753                 if (!tok || tok->type != ';')
1754                         break;
1755                 isl_token_free(tok);
1756         }
1757
1758         if (tok && tok->type == '}') {
1759                 isl_token_free(tok);
1760         } else {
1761                 isl_stream_error(s, tok, "unexpected isl_token");
1762                 if (tok)
1763                         isl_token_free(tok);
1764                 goto error;
1765         }
1766 done:
1767         vars_free(v);
1768         isl_basic_map_free(bmap);
1769
1770         return obj;
1771 error:
1772         isl_basic_map_free(bmap);
1773         obj.type->free(obj.v);
1774         if (v)
1775                 vars_free(v);
1776         obj.v = NULL;
1777         return obj;
1778 }
1779
1780 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
1781 {
1782         return obj_read(s, -1);
1783 }
1784
1785 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s, int nparam)
1786 {
1787         struct isl_obj obj;
1788         struct isl_map *map;
1789
1790         obj = obj_read(s, nparam);
1791         if (obj.v)
1792                 isl_assert(s->ctx, obj.type == isl_obj_map ||
1793                                    obj.type == isl_obj_set, goto error);
1794
1795         return obj.v;
1796 error:
1797         obj.type->free(obj.v);
1798         return NULL;
1799 }
1800
1801 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s, int nparam)
1802 {
1803         struct isl_obj obj;
1804         struct isl_set *set;
1805
1806         obj = obj_read(s, nparam);
1807         if (obj.v)
1808                 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
1809
1810         return obj.v;
1811 error:
1812         obj.type->free(obj.v);
1813         return NULL;
1814 }
1815
1816 static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam)
1817 {
1818         struct isl_obj obj;
1819         struct isl_map *map;
1820         struct isl_basic_map *bmap;
1821
1822         obj = obj_read(s, nparam);
1823         map = obj.v;
1824         if (!map)
1825                 return NULL;
1826
1827         isl_assert(map->ctx, map->n <= 1, goto error);
1828
1829         if (map->n == 0)
1830                 bmap = isl_basic_map_empty_like_map(map);
1831         else
1832                 bmap = isl_basic_map_copy(map->p[0]);
1833
1834         isl_map_free(map);
1835
1836         return bmap;
1837 error:
1838         isl_map_free(map);
1839         return NULL;
1840 }
1841
1842 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
1843                 FILE *input, int nparam)
1844 {
1845         struct isl_basic_map *bmap;
1846         struct isl_stream *s = isl_stream_new_file(ctx, input);
1847         if (!s)
1848                 return NULL;
1849         bmap = basic_map_read(s, nparam);
1850         isl_stream_free(s);
1851         return bmap;
1852 }
1853
1854 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
1855                 FILE *input, int nparam)
1856 {
1857         struct isl_basic_map *bmap;
1858         bmap = isl_basic_map_read_from_file(ctx, input, nparam);
1859         if (!bmap)
1860                 return NULL;
1861         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
1862         return (struct isl_basic_set *)bmap;
1863 error:
1864         isl_basic_map_free(bmap);
1865         return NULL;
1866 }
1867
1868 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
1869                 const char *str, int nparam)
1870 {
1871         struct isl_basic_map *bmap;
1872         struct isl_stream *s = isl_stream_new_str(ctx, str);
1873         if (!s)
1874                 return NULL;
1875         bmap = basic_map_read(s, nparam);
1876         isl_stream_free(s);
1877         return bmap;
1878 }
1879
1880 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
1881                 const char *str, int nparam)
1882 {
1883         struct isl_basic_map *bmap;
1884         bmap = isl_basic_map_read_from_str(ctx, str, nparam);
1885         if (!bmap)
1886                 return NULL;
1887         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
1888         return (struct isl_basic_set *)bmap;
1889 error:
1890         isl_basic_map_free(bmap);
1891         return NULL;
1892 }
1893
1894 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
1895                 FILE *input, int nparam)
1896 {
1897         struct isl_map *map;
1898         struct isl_stream *s = isl_stream_new_file(ctx, input);
1899         if (!s)
1900                 return NULL;
1901         map = isl_stream_read_map(s, nparam);
1902         isl_stream_free(s);
1903         return map;
1904 }
1905
1906 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
1907                 const char *str, int nparam)
1908 {
1909         struct isl_map *map;
1910         struct isl_stream *s = isl_stream_new_str(ctx, str);
1911         if (!s)
1912                 return NULL;
1913         map = isl_stream_read_map(s, nparam);
1914         isl_stream_free(s);
1915         return map;
1916 }
1917
1918 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
1919                 FILE *input, int nparam)
1920 {
1921         struct isl_map *map;
1922         map = isl_map_read_from_file(ctx, input, nparam);
1923         if (!map)
1924                 return NULL;
1925         isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
1926         return (struct isl_set *)map;
1927 error:
1928         isl_map_free(map);
1929         return NULL;
1930 }
1931
1932 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
1933                 const char *str, int nparam)
1934 {
1935         struct isl_map *map;
1936         map = isl_map_read_from_str(ctx, str, nparam);
1937         if (!map)
1938                 return NULL;
1939         isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
1940         return (struct isl_set *)map;
1941 error:
1942         isl_map_free(map);
1943         return NULL;
1944 }
1945
1946 static char *next_line(FILE *input, char *line, unsigned len)
1947 {
1948         char *p;
1949
1950         do {
1951                 if (!(p = fgets(line, len, input)))
1952                         return NULL;
1953                 while (isspace(*p) && *p != '\n')
1954                         ++p;
1955         } while (*p == '#' || *p == '\n');
1956
1957         return p;
1958 }
1959
1960 static struct isl_vec *isl_vec_read_from_file_polylib(struct isl_ctx *ctx,
1961                 FILE *input)
1962 {
1963         struct isl_vec *vec = NULL;
1964         char line[1024];
1965         char val[1024];
1966         char *p;
1967         unsigned size;
1968         int j;
1969         int n;
1970         int offset;
1971
1972         isl_assert(ctx, next_line(input, line, sizeof(line)), return NULL);
1973         isl_assert(ctx, sscanf(line, "%u", &size) == 1, return NULL);
1974
1975         vec = isl_vec_alloc(ctx, size);
1976
1977         p = next_line(input, line, sizeof(line));
1978         isl_assert(ctx, p, goto error);
1979
1980         for (j = 0; j < size; ++j) {
1981                 n = sscanf(p, "%s%n", val, &offset);
1982                 isl_assert(ctx, n != 0, goto error);
1983                 isl_int_read(vec->el[j], val);
1984                 p += offset;
1985         }
1986
1987         return vec;
1988 error:
1989         isl_vec_free(vec);
1990         return NULL;
1991 }
1992
1993 struct isl_vec *isl_vec_read_from_file(struct isl_ctx *ctx,
1994                 FILE *input, unsigned input_format)
1995 {
1996         if (input_format == ISL_FORMAT_POLYLIB)
1997                 return isl_vec_read_from_file_polylib(ctx, input);
1998         else
1999                 isl_assert(ctx, 0, return NULL);
2000 }
2001
2002 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2003         struct isl_stream *s)
2004 {
2005         struct isl_obj obj;
2006         struct isl_pw_qpolynomial *pwqp;
2007
2008         obj = obj_read(s, -1);
2009         if (obj.v)
2010                 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2011                            goto error);
2012
2013         return obj.v;
2014 error:
2015         obj.type->free(obj.v);
2016         return NULL;
2017 }
2018
2019 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2020                 const char *str)
2021 {
2022         isl_pw_qpolynomial *pwqp;
2023         struct isl_stream *s = isl_stream_new_str(ctx, str);
2024         if (!s)
2025                 return NULL;
2026         pwqp = isl_stream_read_pw_qpolynomial(s);
2027         isl_stream_free(s);
2028         return pwqp;
2029 }