isl_input.c

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