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