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