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