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