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