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 <isl_ctx_private.h>
  17 #include <isl_map_private.h>
  18 #include <isl/set.h>
  19 #include <isl/seq.h>
  20 #include <isl_stream_private.h>
  21 #include <isl/obj.h>
  22 #include "isl_polynomial_private.h"
  23 #include <isl/union_map.h>
  24 #include <isl_mat_private.h>
  25 #include <isl_aff_private.h>
  26 #include <isl/list.h>
  27
  28 struct variable {
  29         char                    *name;
  30         int                      pos;
  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                 free(var->name);
  57                 free(var);
  58                 var = next;
  59         }
  60 }
  61
  62 static void vars_free(struct vars *v)
  63 {
  64         if (!v)
  65                 return;
  66         variable_free(v->v);
  67         free(v);
  68 }
  69
  70 static void vars_drop(struct vars *v, int n)
  71 {
  72         struct variable *var;
  73
  74         if (!v || !v->v)
  75                 return;
  76
  77         v->n -= n;
  78
  79         var = v->v;
  80         while (--n >= 0) {
  81                 struct variable *next = var->next;
  82                 free(var->name);
  83                 free(var);
  84                 var = next;
  85         }
  86         v->v = var;
  87 }
  88
  89 static struct variable *variable_new(struct vars *v, const char *name, int len,
  90                                 int pos)
  91 {
  92         struct variable *var;
  93         var = isl_calloc_type(v->ctx, struct variable);
  94         if (!var)
  95                 goto error;
  96         var->name = strdup(name);
  97         var->name[len] = '\0';
  98         var->pos = pos;
  99         var->next = v->v;
 100         return var;
 101 error:
 102         variable_free(v->v);
 103         return NULL;
 104 }
 105
 106 static int vars_pos(struct vars *v, const char *s, int len)
 107 {
 108         int pos;
 109         struct variable *q;
 110
 111         if (len == -1)
 112                 len = strlen(s);
 113         for (q = v->v; q; q = q->next) {
 114                 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
 115                         break;
 116         }
 117         if (q)
 118                 pos = q->pos;
 119         else {
 120                 pos = v->n;
 121                 v->v = variable_new(v, s, len, v->n);
 122                 if (!v->v)
 123                         return -1;
 124                 v->n++;
 125         }
 126         return pos;
 127 }
 128
 129 static int vars_add_anon(struct vars *v)
 130 {
 131         v->v = variable_new(v, "", 0, v->n);
 132
 133         if (!v->v)
 134                 return -1;
 135         v->n++;
 136
 137         return 0;
 138 }
 139
 140 static __isl_give isl_map *set_name(__isl_take isl_map *map,
 141         enum isl_dim_type type, unsigned pos, char *name)
 142 {
 143         char *prime;
 144
 145         if (!map)
 146                 return NULL;
 147         if (!name)
 148                 return map;
 149
 150         prime = strchr(name, '\'');
 151         if (prime)
 152                 *prime = '\0';
 153         map = isl_map_set_dim_name(map, type, pos, name);
 154         if (prime)
 155                 *prime = '\'';
 156
 157         return map;
 158 }
 159
 160 /* Obtain next token, with some preprocessing.
 161  * In particular, evaluate expressions of the form x^y,
 162  * with x and y values.
 163  */
 164 static struct isl_token *next_token(struct isl_stream *s)
 165 {
 166         struct isl_token *tok, *tok2;
 167
 168         tok = isl_stream_next_token(s);
 169         if (!tok || tok->type != ISL_TOKEN_VALUE)
 170                 return tok;
 171         if (!isl_stream_eat_if_available(s, '^'))
 172                 return tok;
 173         tok2 = isl_stream_next_token(s);
 174         if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
 175                 isl_stream_error(s, tok2, "expecting constant value");
 176                 goto error;
 177         }
 178
 179         isl_int_pow_ui(tok->u.v, tok->u.v, isl_int_get_ui(tok2->u.v));
 180
 181         isl_token_free(tok2);
 182         return tok;
 183 error:
 184         isl_token_free(tok);
 185         isl_token_free(tok2);
 186         return NULL;
 187 }
 188
 189 static int accept_cst_factor(struct isl_stream *s, isl_int *f)
 190 {
 191         struct isl_token *tok;
 192
 193         tok = next_token(s);
 194         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 195                 isl_stream_error(s, tok, "expecting constant value");
 196                 goto error;
 197         }
 198
 199         isl_int_mul(*f, *f, tok->u.v);
 200
 201         isl_token_free(tok);
 202
 203         if (isl_stream_eat_if_available(s, '*'))
 204                 return accept_cst_factor(s, f);
 205
 206         return 0;
 207 error:
 208         isl_token_free(tok);
 209         return -1;
 210 }
 211
 212 /* Given an affine expression aff, return an affine expression
 213  * for aff % d, with d the next token on the stream, which is
 214  * assumed to be a constant.
 215  *
 216  * We introduce an integer division q = [aff/d] and the result
 217  * is set to aff - d q.
 218  */
 219 static __isl_give isl_pw_aff *affine_mod(struct isl_stream *s,
 220         struct vars *v, __isl_take isl_pw_aff *aff)
 221 {
 222         struct isl_token *tok;
 223         isl_pw_aff *q;
 224
 225         tok = next_token(s);
 226         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 227                 isl_stream_error(s, tok, "expecting constant value");
 228                 goto error;
 229         }
 230
 231         q = isl_pw_aff_copy(aff);
 232         q = isl_pw_aff_scale_down(q, tok->u.v);
 233         q = isl_pw_aff_floor(q);
 234         q = isl_pw_aff_scale(q, tok->u.v);
 235
 236         aff = isl_pw_aff_sub(aff, q);
 237
 238         isl_token_free(tok);
 239         return aff;
 240 error:
 241         isl_pw_aff_free(aff);
 242         isl_token_free(tok);
 243         return NULL;
 244 }
 245
 246 static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s,
 247         __isl_take isl_space *dim, struct vars *v);
 248 static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s,
 249         __isl_take isl_space *dim, struct vars *v);
 250
 251 static __isl_give isl_pw_aff *accept_minmax(struct isl_stream *s,
 252         __isl_take isl_space *dim, struct vars *v)
 253 {
 254         struct isl_token *tok;
 255         isl_pw_aff_list *list = NULL;
 256         int min;
 257
 258         tok = isl_stream_next_token(s);
 259         if (!tok)
 260                 goto error;
 261         min = tok->type == ISL_TOKEN_MIN;
 262         isl_token_free(tok);
 263
 264         if (isl_stream_eat(s, '('))
 265                 goto error;
 266
 267         list = accept_affine_list(s, isl_space_copy(dim), v);
 268         if (!list)
 269                 goto error;
 270
 271         if (isl_stream_eat(s, ')'))
 272                 goto error;
 273
 274         isl_space_free(dim);
 275         return min ? isl_pw_aff_list_min(list) : isl_pw_aff_list_max(list);
 276 error:
 277         isl_space_free(dim);
 278         isl_pw_aff_list_free(list);
 279         return NULL;
 280 }
 281
 282 static __isl_give isl_pw_aff *accept_div(struct isl_stream *s,
 283         __isl_take isl_space *dim, struct vars *v)
 284 {
 285         struct isl_token *tok;
 286         int seen_paren = 0;
 287         int f = 0;
 288         int c = 0;
 289         isl_pw_aff *pwaff = NULL;
 290
 291         if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD))
 292                 f = 1;
 293         else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEILD))
 294                 c = 1;
 295         if (f || c) {
 296                 if (isl_stream_eat(s, '('))
 297                         goto error;
 298         } else {
 299                 if (isl_stream_eat(s, '['))
 300                         goto error;
 301                 if (isl_stream_eat_if_available(s, '('))
 302                         seen_paren = 1;
 303         }
 304
 305         pwaff = accept_affine(s, isl_space_copy(dim), v);
 306
 307         if (f || c) {
 308                 if (isl_stream_eat(s, ','))
 309                         goto error;
 310         } else {
 311                 if (seen_paren && isl_stream_eat(s, ')'))
 312                         goto error;
 313                 if (isl_stream_eat(s, '/'))
 314                         goto error;
 315         }
 316
 317         tok = next_token(s);
 318         if (!tok)
 319                 goto error;
 320         if (tok->type != ISL_TOKEN_VALUE) {
 321                 isl_stream_error(s, tok, "expected denominator");
 322                 isl_stream_push_token(s, tok);
 323                 goto error;
 324         }
 325         isl_pw_aff_scale_down(pwaff,  tok->u.v);
 326         isl_token_free(tok);
 327
 328         if (c)
 329                 pwaff = isl_pw_aff_ceil(pwaff);
 330         else
 331                 pwaff = isl_pw_aff_floor(pwaff);
 332
 333         if (f || c) {
 334                 if (isl_stream_eat(s, ')'))
 335                         goto error;
 336         } else {
 337                 if (isl_stream_eat(s, ']'))
 338                         goto error;
 339         }
 340
 341         isl_space_free(dim);
 342         return pwaff;
 343 error:
 344         isl_space_free(dim);
 345         isl_pw_aff_free(pwaff);
 346         return NULL;
 347 }
 348
 349 static __isl_give isl_pw_aff *accept_affine_factor(struct isl_stream *s,
 350         __isl_take isl_space *dim, struct vars *v)
 351 {
 352         struct isl_token *tok = NULL;
 353         isl_pw_aff *res = NULL;
 354
 355         tok = next_token(s);
 356         if (!tok) {
 357                 isl_stream_error(s, NULL, "unexpected EOF");
 358                 goto error;
 359         }
 360
 361         if (tok->type == ISL_TOKEN_AFF) {
 362                 res = isl_pw_aff_copy(tok->u.pwaff);
 363                 isl_token_free(tok);
 364         } else if (tok->type == ISL_TOKEN_IDENT) {
 365                 int n = v->n;
 366                 int pos = vars_pos(v, tok->u.s, -1);
 367                 isl_aff *aff;
 368
 369                 if (pos < 0)
 370                         goto error;
 371                 if (pos >= n) {
 372                         isl_stream_error(s, tok, "unknown identifier");
 373                         goto error;
 374                 }
 375
 376                 aff = isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(dim)));
 377                 if (!aff)
 378                         goto error;
 379                 isl_int_set_si(aff->v->el[2 + pos], 1);
 380                 res = isl_pw_aff_from_aff(aff);
 381                 isl_token_free(tok);
 382         } else if (tok->type == ISL_TOKEN_VALUE) {
 383                 if (isl_stream_eat_if_available(s, '*')) {
 384                         res = accept_affine_factor(s, isl_space_copy(dim), v);
 385                         res = isl_pw_aff_scale(res, tok->u.v);
 386                 } else {
 387                         isl_local_space *ls;
 388                         isl_aff *aff;
 389                         ls = isl_local_space_from_space(isl_space_copy(dim));
 390                         aff = isl_aff_zero_on_domain(ls);
 391                         aff = isl_aff_add_constant(aff, tok->u.v);
 392                         res = isl_pw_aff_from_aff(aff);
 393                 }
 394                 isl_token_free(tok);
 395         } else if (tok->type == '(') {
 396                 isl_token_free(tok);
 397                 tok = NULL;
 398                 res = accept_affine(s, isl_space_copy(dim), v);
 399                 if (!res)
 400                         goto error;
 401                 if (isl_stream_eat(s, ')'))
 402                         goto error;
 403         } else if (tok->type == '[' ||
 404                     tok->type == ISL_TOKEN_FLOORD ||
 405                     tok->type == ISL_TOKEN_CEILD) {
 406                 isl_stream_push_token(s, tok);
 407                 tok = NULL;
 408                 res = accept_div(s, isl_space_copy(dim), v);
 409         } else if (tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX) {
 410                 isl_stream_push_token(s, tok);
 411                 tok = NULL;
 412                 res = accept_minmax(s, isl_space_copy(dim), v);
 413         } else {
 414                 isl_stream_error(s, tok, "expecting factor");
 415                 goto error;
 416         }
 417         if (isl_stream_eat_if_available(s, '%') ||
 418             isl_stream_eat_if_available(s, ISL_TOKEN_MOD)) {
 419                 isl_space_free(dim);
 420                 return affine_mod(s, v, res);
 421         }
 422         if (isl_stream_eat_if_available(s, '*')) {
 423                 isl_int f;
 424                 isl_int_init(f);
 425                 isl_int_set_si(f, 1);
 426                 if (accept_cst_factor(s, &f) < 0) {
 427                         isl_int_clear(f);
 428                         goto error2;
 429                 }
 430                 res = isl_pw_aff_scale(res, f);
 431                 isl_int_clear(f);
 432         }
 433
 434         isl_space_free(dim);
 435         return res;
 436 error:
 437         isl_token_free(tok);
 438 error2:
 439         isl_pw_aff_free(res);
 440         isl_space_free(dim);
 441         return NULL;
 442 }
 443
 444 static __isl_give isl_pw_aff *add_cst(__isl_take isl_pw_aff *pwaff, isl_int v)
 445 {
 446         isl_aff *aff;
 447         isl_space *space;
 448
 449         space = isl_pw_aff_get_domain_space(pwaff);
 450         aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
 451         aff = isl_aff_add_constant(aff, v);
 452
 453         return isl_pw_aff_add(pwaff, isl_pw_aff_from_aff(aff));
 454 }
 455
 456 static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s,
 457         __isl_take isl_space *dim, struct vars *v)
 458 {
 459         struct isl_token *tok = NULL;
 460         isl_local_space *ls;
 461         isl_pw_aff *res;
 462         int sign = 1;
 463
 464         ls = isl_local_space_from_space(isl_space_copy(dim));
 465         res = isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls));
 466         if (!res)
 467                 goto error;
 468
 469         for (;;) {
 470                 tok = next_token(s);
 471                 if (!tok) {
 472                         isl_stream_error(s, NULL, "unexpected EOF");
 473                         goto error;
 474                 }
 475                 if (tok->type == '-') {
 476                         sign = -sign;
 477                         isl_token_free(tok);
 478                         continue;
 479                 }
 480                 if (tok->type == '(' || tok->type == '[' ||
 481                     tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX ||
 482                     tok->type == ISL_TOKEN_FLOORD ||
 483                     tok->type == ISL_TOKEN_CEILD ||
 484                     tok->type == ISL_TOKEN_IDENT ||
 485                     tok->type == ISL_TOKEN_AFF) {
 486                         isl_pw_aff *term;
 487                         isl_stream_push_token(s, tok);
 488                         tok = NULL;
 489                         term = accept_affine_factor(s, isl_space_copy(dim), v);
 490                         if (sign < 0)
 491                                 res = isl_pw_aff_sub(res, term);
 492                         else
 493                                 res = isl_pw_aff_add(res, term);
 494                         if (!res)
 495                                 goto error;
 496                         sign = 1;
 497                 } else if (tok->type == ISL_TOKEN_VALUE) {
 498                         if (sign < 0)
 499                                 isl_int_neg(tok->u.v, tok->u.v);
 500                         if (isl_stream_eat_if_available(s, '*') ||
 501                             isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
 502                                 isl_pw_aff *term;
 503                                 term = accept_affine_factor(s,
 504                                                         isl_space_copy(dim), v);
 505                                 term = isl_pw_aff_scale(term, tok->u.v);
 506                                 res = isl_pw_aff_add(res, term);
 507                                 if (!res)
 508                                         goto error;
 509                         } else {
 510                                 res = add_cst(res, tok->u.v);
 511                         }
 512                         sign = 1;
 513                 } else {
 514                         isl_stream_error(s, tok, "unexpected isl_token");
 515                         isl_stream_push_token(s, tok);
 516                         isl_pw_aff_free(res);
 517                         isl_space_free(dim);
 518                         return NULL;
 519                 }
 520                 isl_token_free(tok);
 521
 522                 tok = next_token(s);
 523                 if (tok && tok->type == '-') {
 524                         sign = -sign;
 525                         isl_token_free(tok);
 526                 } else if (tok && tok->type == '+') {
 527                         /* nothing */
 528                         isl_token_free(tok);
 529                 } else if (tok && tok->type == ISL_TOKEN_VALUE &&
 530                            isl_int_is_neg(tok->u.v)) {
 531                         isl_stream_push_token(s, tok);
 532                 } else {
 533                         if (tok)
 534                                 isl_stream_push_token(s, tok);
 535                         break;
 536                 }
 537         }
 538
 539         isl_space_free(dim);
 540         return res;
 541 error:
 542         isl_space_free(dim);
 543         isl_token_free(tok);
 544         isl_pw_aff_free(res);
 545         return NULL;
 546 }
 547
 548 static int is_comparator(struct isl_token *tok)
 549 {
 550         if (!tok)
 551                 return 0;
 552
 553         switch (tok->type) {
 554         case ISL_TOKEN_LT:
 555         case ISL_TOKEN_GT:
 556         case ISL_TOKEN_LE:
 557         case ISL_TOKEN_GE:
 558         case ISL_TOKEN_NE:
 559         case '=':
 560                 return 1;
 561         default:
 562                 return 0;
 563         }
 564 }
 565
 566 static struct isl_map *read_disjuncts(struct isl_stream *s,
 567         struct vars *v, __isl_take isl_map *map);
 568 static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s,
 569         __isl_take isl_space *dim, struct vars *v);
 570
 571 /* Accept a ternary operator, given the first argument.
 572  */
 573 static __isl_give isl_pw_aff *accept_ternary(struct isl_stream *s,
 574         __isl_take isl_map *cond, struct vars *v)
 575 {
 576         isl_space *dim;
 577         isl_pw_aff *pwaff1 = NULL, *pwaff2 = NULL;
 578
 579         if (!cond)
 580                 return NULL;
 581
 582         if (isl_stream_eat(s, '?'))
 583                 goto error;
 584
 585         dim = isl_space_wrap(isl_map_get_space(cond));
 586         pwaff1 = accept_extended_affine(s, dim, v);
 587         if (!pwaff1)
 588                 goto error;
 589
 590         if (isl_stream_eat(s, ':'))
 591                 goto error;
 592
 593         dim = isl_pw_aff_get_domain_space(pwaff1);
 594         pwaff2 = accept_extended_affine(s, dim, v);
 595         if (!pwaff1)
 596                 goto error;
 597
 598         return isl_pw_aff_cond(isl_map_wrap(cond), pwaff1, pwaff2);
 599 error:
 600         isl_map_free(cond);
 601         isl_pw_aff_free(pwaff1);
 602         isl_pw_aff_free(pwaff2);
 603         return NULL;
 604 }
 605
 606 /* Accept an affine expression that may involve ternary operators.
 607  * We first read an affine expression.
 608  * If it is not followed by a comparison operator, we simply return it.
 609  * Otherwise, we assume the affine epxression is part of the first
 610  * argument of a ternary operator and try to parse that.
 611  */
 612 static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s,
 613         __isl_take isl_space *dim, struct vars *v)
 614 {
 615         isl_space *space;
 616         isl_map *cond;
 617         isl_pw_aff *pwaff;
 618         struct isl_token *tok;
 619         int line = -1, col = -1;
 620         int is_comp;
 621
 622         tok = isl_stream_next_token(s);
 623         if (tok) {
 624                 line = tok->line;
 625                 col = tok->col;
 626                 isl_stream_push_token(s, tok);
 627         }
 628
 629         pwaff = accept_affine(s, dim, v);
 630         if (!pwaff)
 631                 return NULL;
 632
 633         tok = isl_stream_next_token(s);
 634         if (!tok)
 635                 return isl_pw_aff_free(pwaff);
 636
 637         is_comp = is_comparator(tok);
 638         isl_stream_push_token(s, tok);
 639         if (!is_comp)
 640                 return pwaff;
 641
 642         tok = isl_token_new(s->ctx, line, col, 0);
 643         if (!tok)
 644                 return isl_pw_aff_free(pwaff);
 645         tok->type = ISL_TOKEN_AFF;
 646         tok->u.pwaff = pwaff;
 647
 648         space = isl_pw_aff_get_domain_space(pwaff);
 649         cond = isl_map_universe(isl_space_unwrap(space));
 650
 651         isl_stream_push_token(s, tok);
 652
 653         cond = read_disjuncts(s, v, cond);
 654
 655         return accept_ternary(s, cond, v);
 656 }
 657
 658 static __isl_give isl_map *read_var_def(struct isl_stream *s,
 659         __isl_take isl_map *map, enum isl_dim_type type, struct vars *v)
 660 {
 661         isl_pw_aff *def;
 662         int pos;
 663         isl_map *def_map;
 664
 665         if (type == isl_dim_param)
 666                 pos = isl_map_dim(map, isl_dim_param);
 667         else {
 668                 pos = isl_map_dim(map, isl_dim_in);
 669                 if (type == isl_dim_out)
 670                         pos += isl_map_dim(map, isl_dim_out);
 671                 type = isl_dim_in;
 672         }
 673         --pos;
 674
 675         def = accept_extended_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
 676         def_map = isl_map_from_pw_aff(def);
 677         def_map = isl_map_equate(def_map, type, pos, isl_dim_out, 0);
 678         def_map = isl_set_unwrap(isl_map_domain(def_map));
 679
 680         map = isl_map_intersect(map, def_map);
 681
 682         return map;
 683 }
 684
 685 static __isl_give isl_map *read_var_list(struct isl_stream *s,
 686         __isl_take isl_map *map, enum isl_dim_type type, struct vars *v)
 687 {
 688         int i = 0;
 689         struct isl_token *tok;
 690
 691         if (isl_stream_next_token_is(s, ']'))
 692                 return isl_map_add_dims(map, type, 0);
 693
 694         while ((tok = next_token(s)) != NULL) {
 695                 int new_name = 0;
 696
 697                 if (tok->type == ISL_TOKEN_IDENT) {
 698                         int n = v->n;
 699                         int p = vars_pos(v, tok->u.s, -1);
 700                         if (p < 0)
 701                                 goto error;
 702                         new_name = p >= n;
 703                 }
 704
 705                 if (new_name) {
 706                         map = isl_map_add_dims(map, type, 1);
 707                         map = set_name(map, type, i, v->v->name);
 708                         isl_token_free(tok);
 709                         if (isl_stream_eat_if_available(s, '='))
 710                                 map = read_var_def(s, map, type, v);
 711                 } else {
 712                         if (type == isl_dim_param) {
 713                                 isl_stream_error(s, tok,
 714                                                 "expecting unique identifier");
 715                                 goto error;
 716                         }
 717                         isl_stream_push_token(s, tok);
 718                         tok = NULL;
 719                         if (vars_add_anon(v) < 0)
 720                                 goto error;
 721                         map = isl_map_add_dims(map, type, 1);
 722                         map = read_var_def(s, map, type, v);
 723                 }
 724
 725                 tok = isl_stream_next_token(s);
 726                 if (tok && tok->type == ']' &&
 727                     isl_stream_next_token_is(s, '[')) {
 728                         isl_token_free(tok);
 729                         tok = isl_stream_next_token(s);
 730                 } else if (!tok || tok->type != ',')
 731                         break;
 732
 733                 isl_token_free(tok);
 734                 i++;
 735         }
 736         if (tok)
 737                 isl_stream_push_token(s, tok);
 738
 739         return map;
 740 error:
 741         isl_token_free(tok);
 742         isl_map_free(map);
 743         return NULL;
 744 }
 745
 746 static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s,
 747         __isl_take isl_space *dim, struct vars *v)
 748 {
 749         isl_pw_aff *pwaff;
 750         isl_pw_aff_list *list;
 751         struct isl_token *tok = NULL;
 752
 753         pwaff = accept_affine(s, isl_space_copy(dim), v);
 754         list = isl_pw_aff_list_from_pw_aff(pwaff);
 755         if (!list)
 756                 goto error;
 757
 758         for (;;) {
 759                 tok = isl_stream_next_token(s);
 760                 if (!tok) {
 761                         isl_stream_error(s, NULL, "unexpected EOF");
 762                         goto error;
 763                 }
 764                 if (tok->type != ',') {
 765                         isl_stream_push_token(s, tok);
 766                         break;
 767                 }
 768                 isl_token_free(tok);
 769
 770                 pwaff = accept_affine(s, isl_space_copy(dim), v);
 771                 list = isl_pw_aff_list_concat(list,
 772                                 isl_pw_aff_list_from_pw_aff(pwaff));
 773                 if (!list)
 774                         return NULL;
 775         }
 776
 777         isl_space_free(dim);
 778         return list;
 779 error:
 780         isl_space_free(dim);
 781         isl_pw_aff_list_free(list);
 782         return NULL;
 783 }
 784
 785 static __isl_give isl_map *read_defined_var_list(struct isl_stream *s,
 786         struct vars *v, __isl_take isl_map *map)
 787 {
 788         struct isl_token *tok;
 789
 790         while ((tok = isl_stream_next_token(s)) != NULL) {
 791                 int p;
 792                 int n = v->n;
 793
 794                 if (tok->type != ISL_TOKEN_IDENT)
 795                         break;
 796
 797                 p = vars_pos(v, tok->u.s, -1);
 798                 if (p < 0)
 799                         goto error;
 800                 if (p < n) {
 801                         isl_stream_error(s, tok, "expecting unique identifier");
 802                         goto error;
 803                 }
 804
 805                 map = isl_map_add_dims(map, isl_dim_out, 1);
 806
 807                 isl_token_free(tok);
 808                 tok = isl_stream_next_token(s);
 809                 if (tok && tok->type == '=') {
 810                         isl_token_free(tok);
 811                         map = read_var_def(s, map, isl_dim_out, v);
 812                         tok = isl_stream_next_token(s);
 813                 }
 814
 815                 if (!tok || tok->type != ',')
 816                         break;
 817
 818                 isl_token_free(tok);
 819         }
 820         if (tok)
 821                 isl_stream_push_token(s, tok);
 822
 823         return map;
 824 error:
 825         isl_token_free(tok);
 826         isl_map_free(map);
 827         return NULL;
 828 }
 829
 830 static int next_is_tuple(struct isl_stream *s)
 831 {
 832         struct isl_token *tok;
 833         int is_tuple;
 834
 835         tok = isl_stream_next_token(s);
 836         if (!tok)
 837                 return 0;
 838         if (tok->type == '[') {
 839                 isl_stream_push_token(s, tok);
 840                 return 1;
 841         }
 842         if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) {
 843                 isl_stream_push_token(s, tok);
 844                 return 0;
 845         }
 846
 847         is_tuple = isl_stream_next_token_is(s, '[');
 848
 849         isl_stream_push_token(s, tok);
 850
 851         return is_tuple;
 852 }
 853
 854 static __isl_give isl_map *read_tuple(struct isl_stream *s,
 855         __isl_take isl_map *map, enum isl_dim_type type, struct vars *v);
 856
 857 static __isl_give isl_set *read_nested_tuple(struct isl_stream *s,
 858         __isl_take isl_map *map, struct vars *v)
 859 {
 860         map = read_tuple(s, map, isl_dim_in, v);
 861         if (isl_stream_eat(s, ISL_TOKEN_TO))
 862                 goto error;
 863         map = read_tuple(s, map, isl_dim_out, v);
 864         return isl_map_wrap(map);
 865 error:
 866         isl_map_free(map);
 867         return NULL;
 868 }
 869
 870 static __isl_give isl_map *read_tuple(struct isl_stream *s,
 871         __isl_take isl_map *map, enum isl_dim_type type, struct vars *v)
 872 {
 873         struct isl_token *tok;
 874         char *name = NULL;
 875
 876         tok = isl_stream_next_token(s);
 877         if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
 878                 name = strdup(tok->u.s);
 879                 if (!name)
 880                         goto error;
 881                 isl_token_free(tok);
 882                 tok = isl_stream_next_token(s);
 883         }
 884         if (!tok || tok->type != '[') {
 885                 isl_stream_error(s, tok, "expecting '['");
 886                 goto error;
 887         }
 888         isl_token_free(tok);
 889         if (type != isl_dim_param && next_is_tuple(s)) {
 890                 isl_space *dim = isl_map_get_space(map);
 891                 int nparam = isl_space_dim(dim, isl_dim_param);
 892                 int n_in = isl_space_dim(dim, isl_dim_in);
 893                 isl_set *nested;
 894                 if (type == isl_dim_out) {
 895                         dim = isl_space_move_dims(dim, isl_dim_param, nparam,
 896                                                 isl_dim_in, 0, n_in);
 897                         dim = isl_space_params(dim);
 898                 }
 899                 nested = read_nested_tuple(s, isl_map_universe(dim), v);
 900                 if (type == isl_dim_in) {
 901                         nested = isl_map_reverse(nested);
 902                         map = isl_map_intersect(nested, map);
 903                 } else {
 904                         isl_set *set;
 905                         dim = isl_set_get_space(nested);
 906                         dim = isl_space_drop_dims(dim, isl_dim_param, nparam, n_in);
 907                         dim = isl_space_join(isl_map_get_space(map), dim);
 908                         set = isl_map_domain(map);
 909                         nested = isl_map_reset_space(nested, dim);
 910                         map = isl_map_intersect_domain(nested, set);
 911                 }
 912         } else
 913                 map = read_var_list(s, map, type, v);
 914         tok = isl_stream_next_token(s);
 915         if (!tok || tok->type != ']') {
 916                 isl_stream_error(s, tok, "expecting ']'");
 917                 goto error;
 918         }
 919         isl_token_free(tok);
 920
 921         if (name) {
 922                 map = isl_map_set_tuple_name(map, type, name);
 923                 free(name);
 924         }
 925
 926         return map;
 927 error:
 928         if (tok)
 929                 isl_token_free(tok);
 930         isl_map_free(map);
 931         return NULL;
 932 }
 933
 934 static __isl_give isl_set *construct_constraints(
 935         __isl_take isl_set *set, enum isl_token_type type,
 936         __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right)
 937 {
 938         isl_set *cond;
 939
 940         if (type == ISL_TOKEN_LE)
 941                 cond = isl_pw_aff_list_le_set(isl_pw_aff_list_copy(left),
 942                                               isl_pw_aff_list_copy(right));
 943         else if (type == ISL_TOKEN_GE)
 944                 cond = isl_pw_aff_list_ge_set(isl_pw_aff_list_copy(left),
 945                                               isl_pw_aff_list_copy(right));
 946         else if (type == ISL_TOKEN_LT)
 947                 cond = isl_pw_aff_list_lt_set(isl_pw_aff_list_copy(left),
 948                                               isl_pw_aff_list_copy(right));
 949         else if (type == ISL_TOKEN_GT)
 950                 cond = isl_pw_aff_list_gt_set(isl_pw_aff_list_copy(left),
 951                                               isl_pw_aff_list_copy(right));
 952         else if (type == ISL_TOKEN_NE)
 953                 cond = isl_pw_aff_list_ne_set(isl_pw_aff_list_copy(left),
 954                                               isl_pw_aff_list_copy(right));
 955         else
 956                 cond = isl_pw_aff_list_eq_set(isl_pw_aff_list_copy(left),
 957                                               isl_pw_aff_list_copy(right));
 958
 959         return isl_set_intersect(set, cond);
 960 }
 961
 962 static __isl_give isl_map *add_constraint(struct isl_stream *s,
 963         struct vars *v, __isl_take isl_map *map)
 964 {
 965         struct isl_token *tok = NULL;
 966         isl_pw_aff_list *list1 = NULL, *list2 = NULL;
 967         isl_set *set;
 968
 969         set = isl_map_wrap(map);
 970         list1 = accept_affine_list(s, isl_set_get_space(set), v);
 971         if (!list1)
 972                 goto error;
 973         tok = isl_stream_next_token(s);
 974         if (!is_comparator(tok)) {
 975                 isl_stream_error(s, tok, "missing operator");
 976                 if (tok)
 977                         isl_stream_push_token(s, tok);
 978                 tok = NULL;
 979                 goto error;
 980         }
 981         for (;;) {
 982                 list2 = accept_affine_list(s, isl_set_get_space(set), v);
 983                 if (!list2)
 984                         goto error;
 985
 986                 set = construct_constraints(set, tok->type, list1, list2);
 987                 isl_token_free(tok);
 988                 isl_pw_aff_list_free(list1);
 989                 list1 = list2;
 990
 991                 tok = isl_stream_next_token(s);
 992                 if (!is_comparator(tok)) {
 993                         if (tok)
 994                                 isl_stream_push_token(s, tok);
 995                         break;
 996                 }
 997         }
 998         isl_pw_aff_list_free(list1);
 999
1000         return isl_set_unwrap(set);
1001 error:
1002         if (tok)
1003                 isl_token_free(tok);
1004         isl_pw_aff_list_free(list1);
1005         isl_pw_aff_list_free(list2);
1006         isl_set_free(set);
1007         return NULL;
1008 }
1009
1010 static __isl_give isl_map *read_exists(struct isl_stream *s,
1011         struct vars *v, __isl_take isl_map *map)
1012 {
1013         int n = v->n;
1014         int seen_paren = isl_stream_eat_if_available(s, '(');
1015
1016         map = isl_map_from_domain(isl_map_wrap(map));
1017         map = read_defined_var_list(s, v, map);
1018
1019         if (isl_stream_eat(s, ':'))
1020                 goto error;
1021
1022         map = read_disjuncts(s, v, map);
1023         map = isl_set_unwrap(isl_map_domain(map));
1024
1025         vars_drop(v, v->n - n);
1026         if (seen_paren && isl_stream_eat(s, ')'))
1027                 goto error;
1028
1029         return map;
1030 error:
1031         isl_map_free(map);
1032         return NULL;
1033 }
1034
1035 /* Parse an expression between parentheses and push the result
1036  * back on the stream.
1037  *
1038  * The parsed expression may be either an affine expression
1039  * or a condition.  The first type is pushed onto the stream
1040  * as an isl_pw_aff, while the second is pushed as an isl_map.
1041  *
1042  * If the initial token indicates the start of a condition,
1043  * we parse it as such.
1044  * Otherwise, we first parse an affine expression and push
1045  * that onto the stream.  If the affine expression covers the
1046  * entire expression between parentheses, we return.
1047  * Otherwise, we assume that the affine expression is the
1048  * start of a condition and continue parsing.
1049  */
1050 static int resolve_paren_expr(struct isl_stream *s,
1051         struct vars *v, __isl_take isl_map *map)
1052 {
1053         struct isl_token *tok, *tok2;
1054         int line, col;
1055         isl_pw_aff *pwaff;
1056
1057         tok = isl_stream_next_token(s);
1058         if (!tok || tok->type != '(')
1059                 goto error;
1060
1061         if (isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) ||
1062             isl_stream_next_token_is(s, ISL_TOKEN_TRUE) ||
1063             isl_stream_next_token_is(s, ISL_TOKEN_FALSE)) {
1064                 map = read_disjuncts(s, v, map);
1065                 if (isl_stream_eat(s, ')'))
1066                         goto error;
1067                 tok->type = ISL_TOKEN_MAP;
1068                 tok->u.map = map;
1069                 isl_stream_push_token(s, tok);
1070                 return 0;
1071         }
1072
1073         tok2 = isl_stream_next_token(s);
1074         if (!tok2)
1075                 goto error;
1076         line = tok2->line;
1077         col = tok2->col;
1078         isl_stream_push_token(s, tok2);
1079
1080         pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
1081         if (!pwaff)
1082                 goto error;
1083
1084         tok2 = isl_token_new(s->ctx, line, col, 0);
1085         if (!tok2)
1086                 goto error2;
1087         tok2->type = ISL_TOKEN_AFF;
1088         tok2->u.pwaff = pwaff;
1089
1090         if (isl_stream_eat_if_available(s, ')')) {
1091                 isl_stream_push_token(s, tok2);
1092                 isl_token_free(tok);
1093                 isl_map_free(map);
1094                 return 0;
1095         }
1096
1097         isl_stream_push_token(s, tok2);
1098
1099         map = read_disjuncts(s, v, map);
1100         if (isl_stream_eat(s, ')'))
1101                 goto error;
1102
1103         tok->type = ISL_TOKEN_MAP;
1104         tok->u.map = map;
1105         isl_stream_push_token(s, tok);
1106
1107         return 0;
1108 error2:
1109         isl_pw_aff_free(pwaff);
1110 error:
1111         isl_token_free(tok);
1112         isl_map_free(map);
1113         return -1;
1114 }
1115
1116 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1117         struct vars *v, __isl_take isl_map *map)
1118 {
1119         if (isl_stream_next_token_is(s, '('))
1120                 if (resolve_paren_expr(s, v, isl_map_copy(map)))
1121                         goto error;
1122
1123         if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1124                 struct isl_token *tok;
1125                 tok = isl_stream_next_token(s);
1126                 if (!tok)
1127                         goto error;
1128                 isl_map_free(map);
1129                 map = isl_map_copy(tok->u.map);
1130                 isl_token_free(tok);
1131                 return map;
1132         }
1133
1134         if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1135                 return read_exists(s, v, map);
1136
1137         if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1138                 return map;
1139
1140         if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1141                 isl_space *dim = isl_map_get_space(map);
1142                 isl_map_free(map);
1143                 return isl_map_empty(dim);
1144         }
1145
1146         return add_constraint(s, v, map);
1147 error:
1148         isl_map_free(map);
1149         return NULL;
1150 }
1151
1152 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1153         struct vars *v, __isl_take isl_map *map)
1154 {
1155         isl_map *res;
1156         int negate;
1157
1158         negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1159         res = read_conjunct(s, v, isl_map_copy(map));
1160         if (negate)
1161                 res = isl_map_subtract(isl_map_copy(map), res);
1162
1163         while (isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1164                 isl_map *res_i;
1165
1166                 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1167                 res_i = read_conjunct(s, v, isl_map_copy(map));
1168                 if (negate)
1169                         res = isl_map_subtract(res, res_i);
1170                 else
1171                         res = isl_map_intersect(res, res_i);
1172         }
1173
1174         isl_map_free(map);
1175         return res;
1176 }
1177
1178 static struct isl_map *read_disjuncts(struct isl_stream *s,
1179         struct vars *v, __isl_take isl_map *map)
1180 {
1181         isl_map *res;
1182
1183         if (isl_stream_next_token_is(s, '}')) {
1184                 isl_space *dim = isl_map_get_space(map);
1185                 isl_map_free(map);
1186                 return isl_map_universe(dim);
1187         }
1188
1189         res = read_conjuncts(s, v, isl_map_copy(map));
1190         while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1191                 isl_map *res_i;
1192
1193                 res_i = read_conjuncts(s, v, isl_map_copy(map));
1194                 res = isl_map_union(res, res_i);
1195         }
1196
1197         isl_map_free(map);
1198         return res;
1199 }
1200
1201 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1202 {
1203         if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1204                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1205                            isl_basic_map_dim(bmap, isl_dim_in) + pos;
1206         pos -= isl_basic_map_dim(bmap, isl_dim_out);
1207
1208         if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1209                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1210         pos -= isl_basic_map_dim(bmap, isl_dim_in);
1211
1212         if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1213                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1214                            isl_basic_map_dim(bmap, isl_dim_in) +
1215                            isl_basic_map_dim(bmap, isl_dim_out) + pos;
1216         pos -= isl_basic_map_dim(bmap, isl_dim_div);
1217
1218         if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1219                 return 1 + pos;
1220
1221         return 0;
1222 }
1223
1224 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1225         struct isl_stream *s, __isl_take isl_basic_map *bmap)
1226 {
1227         int j;
1228         struct isl_token *tok;
1229         int type;
1230         int k;
1231         isl_int *c;
1232         unsigned nparam;
1233         unsigned dim;
1234
1235         if (!bmap)
1236                 return NULL;
1237
1238         nparam = isl_basic_map_dim(bmap, isl_dim_param);
1239         dim = isl_basic_map_dim(bmap, isl_dim_out);
1240
1241         tok = isl_stream_next_token(s);
1242         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1243                 isl_stream_error(s, tok, "expecting coefficient");
1244                 if (tok)
1245                         isl_stream_push_token(s, tok);
1246                 goto error;
1247         }
1248         if (!tok->on_new_line) {
1249                 isl_stream_error(s, tok, "coefficient should appear on new line");
1250                 isl_stream_push_token(s, tok);
1251                 goto error;
1252         }
1253
1254         type = isl_int_get_si(tok->u.v);
1255         isl_token_free(tok);
1256
1257         isl_assert(s->ctx, type == 0 || type == 1, goto error);
1258         if (type == 0) {
1259                 k = isl_basic_map_alloc_equality(bmap);
1260                 c = bmap->eq[k];
1261         } else {
1262                 k = isl_basic_map_alloc_inequality(bmap);
1263                 c = bmap->ineq[k];
1264         }
1265         if (k < 0)
1266                 goto error;
1267
1268         for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1269                 int pos;
1270                 tok = isl_stream_next_token(s);
1271                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1272                         isl_stream_error(s, tok, "expecting coefficient");
1273                         if (tok)
1274                                 isl_stream_push_token(s, tok);
1275                         goto error;
1276                 }
1277                 if (tok->on_new_line) {
1278                         isl_stream_error(s, tok,
1279                                 "coefficient should not appear on new line");
1280                         isl_stream_push_token(s, tok);
1281                         goto error;
1282                 }
1283                 pos = polylib_pos_to_isl_pos(bmap, j);
1284                 isl_int_set(c[pos], tok->u.v);
1285                 isl_token_free(tok);
1286         }
1287
1288         return bmap;
1289 error:
1290         isl_basic_map_free(bmap);
1291         return NULL;
1292 }
1293
1294 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s)
1295 {
1296         int i;
1297         struct isl_token *tok;
1298         struct isl_token *tok2;
1299         int n_row, n_col;
1300         int on_new_line;
1301         unsigned in = 0, out, local = 0;
1302         struct isl_basic_map *bmap = NULL;
1303         int nparam = 0;
1304
1305         tok = isl_stream_next_token(s);
1306         if (!tok) {
1307                 isl_stream_error(s, NULL, "unexpected EOF");
1308                 return NULL;
1309         }
1310         tok2 = isl_stream_next_token(s);
1311         if (!tok2) {
1312                 isl_token_free(tok);
1313                 isl_stream_error(s, NULL, "unexpected EOF");
1314                 return NULL;
1315         }
1316         if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1317                 isl_stream_push_token(s, tok2);
1318                 isl_stream_push_token(s, tok);
1319                 isl_stream_error(s, NULL,
1320                                  "expecting constraint matrix dimensions");
1321                 return NULL;
1322         }
1323         n_row = isl_int_get_si(tok->u.v);
1324         n_col = isl_int_get_si(tok2->u.v);
1325         on_new_line = tok2->on_new_line;
1326         isl_token_free(tok2);
1327         isl_token_free(tok);
1328         isl_assert(s->ctx, !on_new_line, return NULL);
1329         isl_assert(s->ctx, n_row >= 0, return NULL);
1330         isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1331         tok = isl_stream_next_token_on_same_line(s);
1332         if (tok) {
1333                 if (tok->type != ISL_TOKEN_VALUE) {
1334                         isl_stream_error(s, tok,
1335                                     "expecting number of output dimensions");
1336                         isl_stream_push_token(s, tok);
1337                         goto error;
1338                 }
1339                 out = isl_int_get_si(tok->u.v);
1340                 isl_token_free(tok);
1341
1342                 tok = isl_stream_next_token_on_same_line(s);
1343                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1344                         isl_stream_error(s, tok,
1345                                     "expecting number of input dimensions");
1346                         if (tok)
1347                                 isl_stream_push_token(s, tok);
1348                         goto error;
1349                 }
1350                 in = isl_int_get_si(tok->u.v);
1351                 isl_token_free(tok);
1352
1353                 tok = isl_stream_next_token_on_same_line(s);
1354                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1355                         isl_stream_error(s, tok,
1356                                     "expecting number of existentials");
1357                         if (tok)
1358                                 isl_stream_push_token(s, tok);
1359                         goto error;
1360                 }
1361                 local = isl_int_get_si(tok->u.v);
1362                 isl_token_free(tok);
1363
1364                 tok = isl_stream_next_token_on_same_line(s);
1365                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1366                         isl_stream_error(s, tok,
1367                                     "expecting number of parameters");
1368                         if (tok)
1369                                 isl_stream_push_token(s, tok);
1370                         goto error;
1371                 }
1372                 nparam = isl_int_get_si(tok->u.v);
1373                 isl_token_free(tok);
1374                 if (n_col != 1 + out + in + local + nparam + 1) {
1375                         isl_stream_error(s, NULL,
1376                                     "dimensions don't match");
1377                         goto error;
1378                 }
1379         } else
1380                 out = n_col - 2 - nparam;
1381         bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1382         if (!bmap)
1383                 return NULL;
1384
1385         for (i = 0; i < local; ++i) {
1386                 int k = isl_basic_map_alloc_div(bmap);
1387                 if (k < 0)
1388                         goto error;
1389                 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1390         }
1391
1392         for (i = 0; i < n_row; ++i)
1393                 bmap = basic_map_read_polylib_constraint(s, bmap);
1394
1395         tok = isl_stream_next_token_on_same_line(s);
1396         if (tok) {
1397                 isl_stream_error(s, tok, "unexpected extra token on line");
1398                 isl_stream_push_token(s, tok);
1399                 goto error;
1400         }
1401
1402         bmap = isl_basic_map_simplify(bmap);
1403         bmap = isl_basic_map_finalize(bmap);
1404         return bmap;
1405 error:
1406         isl_basic_map_free(bmap);
1407         return NULL;
1408 }
1409
1410 static struct isl_map *map_read_polylib(struct isl_stream *s)
1411 {
1412         struct isl_token *tok;
1413         struct isl_token *tok2;
1414         int i, n;
1415         struct isl_map *map;
1416
1417         tok = isl_stream_next_token(s);
1418         if (!tok) {
1419                 isl_stream_error(s, NULL, "unexpected EOF");
1420                 return NULL;
1421         }
1422         tok2 = isl_stream_next_token_on_same_line(s);
1423         if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1424                 isl_stream_push_token(s, tok2);
1425                 isl_stream_push_token(s, tok);
1426                 return isl_map_from_basic_map(basic_map_read_polylib(s));
1427         }
1428         if (tok2) {
1429                 isl_stream_error(s, tok2, "unexpected token");
1430                 isl_stream_push_token(s, tok2);
1431                 isl_stream_push_token(s, tok);
1432                 return NULL;
1433         }
1434         n = isl_int_get_si(tok->u.v);
1435         isl_token_free(tok);
1436
1437         isl_assert(s->ctx, n >= 1, return NULL);
1438
1439         map = isl_map_from_basic_map(basic_map_read_polylib(s));
1440
1441         for (i = 1; map && i < n; ++i)
1442                 map = isl_map_union(map,
1443                         isl_map_from_basic_map(basic_map_read_polylib(s)));
1444
1445         return map;
1446 }
1447
1448 static int optional_power(struct isl_stream *s)
1449 {
1450         int pow;
1451         struct isl_token *tok;
1452
1453         tok = isl_stream_next_token(s);
1454         if (!tok)
1455                 return 1;
1456         if (tok->type != '^') {
1457                 isl_stream_push_token(s, tok);
1458                 return 1;
1459         }
1460         isl_token_free(tok);
1461         tok = isl_stream_next_token(s);
1462         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1463                 isl_stream_error(s, tok, "expecting exponent");
1464                 if (tok)
1465                         isl_stream_push_token(s, tok);
1466                 return 1;
1467         }
1468         pow = isl_int_get_si(tok->u.v);
1469         isl_token_free(tok);
1470         return pow;
1471 }
1472
1473 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1474         __isl_keep isl_map *map, struct vars *v);
1475
1476 static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s,
1477         __isl_keep isl_map *map, struct vars *v)
1478 {
1479         isl_pw_qpolynomial *pwqp;
1480         struct isl_token *tok;
1481
1482         tok = next_token(s);
1483         if (!tok) {
1484                 isl_stream_error(s, NULL, "unexpected EOF");
1485                 return NULL;
1486         }
1487         if (tok->type == '(') {
1488                 int pow;
1489
1490                 isl_token_free(tok);
1491                 pwqp = read_term(s, map, v);
1492                 if (!pwqp)
1493                         return NULL;
1494                 if (isl_stream_eat(s, ')'))
1495                         goto error;
1496                 pow = optional_power(s);
1497                 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1498         } else if (tok->type == ISL_TOKEN_VALUE) {
1499                 struct isl_token *tok2;
1500                 tok2 = isl_stream_next_token(s);
1501                 isl_qpolynomial *qp;
1502                 if (tok2 && tok2->type == '/') {
1503                         isl_token_free(tok2);
1504                         tok2 = next_token(s);
1505                         if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1506                                 isl_stream_error(s, tok2, "expected denominator");
1507                                 isl_token_free(tok);
1508                                 isl_token_free(tok2);
1509                                 return NULL;
1510                         }
1511                         qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
1512                                                     tok->u.v, tok2->u.v);
1513                         isl_token_free(tok2);
1514                 } else {
1515                         isl_stream_push_token(s, tok2);
1516                         qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
1517                                                 tok->u.v);
1518                 }
1519                 isl_token_free(tok);
1520                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1521         } else if (tok->type == ISL_TOKEN_INFTY) {
1522                 isl_qpolynomial *qp;
1523                 isl_token_free(tok);
1524                 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
1525                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1526         } else if (tok->type == ISL_TOKEN_NAN) {
1527                 isl_qpolynomial *qp;
1528                 isl_token_free(tok);
1529                 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
1530                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1531         } else if (tok->type == ISL_TOKEN_IDENT) {
1532                 int n = v->n;
1533                 int pos = vars_pos(v, tok->u.s, -1);
1534                 int pow;
1535                 isl_qpolynomial *qp;
1536                 if (pos < 0) {
1537                         isl_token_free(tok);
1538                         return NULL;
1539                 }
1540                 if (pos >= n) {
1541                         vars_drop(v, v->n - n);
1542                         isl_stream_error(s, tok, "unknown identifier");
1543                         isl_token_free(tok);
1544                         return NULL;
1545                 }
1546                 isl_token_free(tok);
1547                 pow = optional_power(s);
1548                 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
1549                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1550         } else if (tok->type == '[') {
1551                 isl_pw_aff *pwaff;
1552                 int pow;
1553
1554                 isl_stream_push_token(s, tok);
1555                 pwaff = accept_affine(s, isl_map_get_space(map), v);
1556                 pow = optional_power(s);
1557                 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
1558                 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1559         } else if (tok->type == '-') {
1560                 isl_token_free(tok);
1561                 pwqp = read_factor(s, map, v);
1562                 pwqp = isl_pw_qpolynomial_neg(pwqp);
1563         } else {
1564                 isl_stream_error(s, tok, "unexpected isl_token");
1565                 isl_stream_push_token(s, tok);
1566                 return NULL;
1567         }
1568
1569         if (isl_stream_eat_if_available(s, '*') ||
1570             isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1571                 isl_pw_qpolynomial *pwqp2;
1572
1573                 pwqp2 = read_factor(s, map, v);
1574                 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
1575         }
1576
1577         return pwqp;
1578 error:
1579         isl_pw_qpolynomial_free(pwqp);
1580         return NULL;
1581 }
1582
1583 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1584         __isl_keep isl_map *map, struct vars *v)
1585 {
1586         struct isl_token *tok;
1587         isl_pw_qpolynomial *pwqp;
1588
1589         pwqp = read_factor(s, map, v);
1590
1591         for (;;) {
1592                 tok = next_token(s);
1593                 if (!tok)
1594                         return pwqp;
1595
1596                 if (tok->type == '+') {
1597                         isl_pw_qpolynomial *pwqp2;
1598
1599                         isl_token_free(tok);
1600                         pwqp2 = read_factor(s, map, v);
1601                         pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1602                 } else if (tok->type == '-') {
1603                         isl_pw_qpolynomial *pwqp2;
1604
1605                         isl_token_free(tok);
1606                         pwqp2 = read_factor(s, map, v);
1607                         pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
1608                 } else if (tok->type == ISL_TOKEN_VALUE &&
1609                             isl_int_is_neg(tok->u.v)) {
1610                         isl_pw_qpolynomial *pwqp2;
1611
1612                         isl_stream_push_token(s, tok);
1613                         pwqp2 = read_factor(s, map, v);
1614                         pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1615                 } else {
1616                         isl_stream_push_token(s, tok);
1617                         break;
1618                 }
1619         }
1620
1621         return pwqp;
1622 }
1623
1624 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1625         __isl_take isl_map *map, struct vars *v)
1626 {
1627         struct isl_token *tok;
1628
1629         tok = isl_stream_next_token(s);
1630         if (!tok) {
1631                 isl_stream_error(s, NULL, "unexpected EOF");
1632                 goto error;
1633         }
1634         if (tok->type == ':' ||
1635             (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
1636                 isl_token_free(tok);
1637                 map = read_disjuncts(s, v, map);
1638         } else
1639                 isl_stream_push_token(s, tok);
1640
1641         return map;
1642 error:
1643         isl_map_free(map);
1644         return NULL;
1645 }
1646
1647 static struct isl_obj obj_read_poly(struct isl_stream *s,
1648         __isl_take isl_map *map, struct vars *v, int n)
1649 {
1650         struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1651         isl_pw_qpolynomial *pwqp;
1652         struct isl_set *set;
1653
1654         pwqp = read_term(s, map, v);
1655         map = read_optional_disjuncts(s, map, v);
1656         set = isl_map_range(map);
1657
1658         pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
1659
1660         vars_drop(v, v->n - n);
1661
1662         obj.v = pwqp;
1663         return obj;
1664 }
1665
1666 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1667         __isl_take isl_set *set, struct vars *v, int n)
1668 {
1669         struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1670         isl_pw_qpolynomial *pwqp;
1671         isl_pw_qpolynomial_fold *pwf = NULL;
1672
1673         if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1674                 return obj_read_poly(s, set, v, n);
1675
1676         if (isl_stream_eat(s, '('))
1677                 goto error;
1678
1679         pwqp = read_term(s, set, v);
1680         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
1681
1682         while (isl_stream_eat_if_available(s, ',')) {
1683                 isl_pw_qpolynomial_fold *pwf_i;
1684                 pwqp = read_term(s, set, v);
1685                 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
1686                                                                         pwqp);
1687                 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
1688         }
1689
1690         if (isl_stream_eat(s, ')'))
1691                 goto error;
1692
1693         set = read_optional_disjuncts(s, set, v);
1694         pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
1695
1696         vars_drop(v, v->n - n);
1697
1698         obj.v = pwf;
1699         return obj;
1700 error:
1701         isl_set_free(set);
1702         isl_pw_qpolynomial_fold_free(pwf);
1703         obj.type = isl_obj_none;
1704         return obj;
1705 }
1706
1707 static int is_rational(struct isl_stream *s)
1708 {
1709         struct isl_token *tok;
1710
1711         tok = isl_stream_next_token(s);
1712         if (!tok)
1713                 return 0;
1714         if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
1715                 isl_token_free(tok);
1716                 isl_stream_eat(s, ':');
1717                 return 1;
1718         }
1719
1720         isl_stream_push_token(s, tok);
1721
1722         return 0;
1723 }
1724
1725 static struct isl_obj obj_read_body(struct isl_stream *s,
1726         __isl_take isl_map *map, struct vars *v)
1727 {
1728         struct isl_token *tok;
1729         struct isl_obj obj = { isl_obj_set, NULL };
1730         int n = v->n;
1731
1732         if (is_rational(s))
1733                 map = isl_map_set_rational(map);
1734
1735         if (isl_stream_next_token_is(s, ':')) {
1736                 obj.type = isl_obj_set;
1737                 obj.v = read_optional_disjuncts(s, map, v);
1738                 return obj;
1739         }
1740
1741         if (!next_is_tuple(s))
1742                 return obj_read_poly_or_fold(s, map, v, n);
1743
1744         map = read_tuple(s, map, isl_dim_in, v);
1745         if (!map)
1746                 goto error;
1747         tok = isl_stream_next_token(s);
1748         if (tok && tok->type == ISL_TOKEN_TO) {
1749                 obj.type = isl_obj_map;
1750                 isl_token_free(tok);
1751                 if (!next_is_tuple(s)) {
1752                         isl_set *set = isl_map_domain(map);
1753                         return obj_read_poly_or_fold(s, set, v, n);
1754                 }
1755                 map = read_tuple(s, map, isl_dim_out, v);
1756                 if (!map)
1757                         goto error;
1758         } else {
1759                 map = isl_map_reverse(map);
1760                 if (tok)
1761                         isl_stream_push_token(s, tok);
1762         }
1763
1764         map = read_optional_disjuncts(s, map, v);
1765
1766         vars_drop(v, v->n - n);
1767
1768         obj.v = map;
1769         return obj;
1770 error:
1771         isl_map_free(map);
1772         obj.type = isl_obj_none;
1773         return obj;
1774 }
1775
1776 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
1777 {
1778         if (obj.type == isl_obj_map) {
1779                 obj.v = isl_union_map_from_map(obj.v);
1780                 obj.type = isl_obj_union_map;
1781         } else if (obj.type == isl_obj_set) {
1782                 obj.v = isl_union_set_from_set(obj.v);
1783                 obj.type = isl_obj_union_set;
1784         } else if (obj.type == isl_obj_pw_qpolynomial) {
1785                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
1786                 obj.type = isl_obj_union_pw_qpolynomial;
1787         } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
1788                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
1789                 obj.type = isl_obj_union_pw_qpolynomial_fold;
1790         } else
1791                 isl_assert(ctx, 0, goto error);
1792         return obj;
1793 error:
1794         obj.type->free(obj.v);
1795         obj.type = isl_obj_none;
1796         return obj;
1797 }
1798
1799 static struct isl_obj obj_add(struct isl_ctx *ctx,
1800         struct isl_obj obj1, struct isl_obj obj2)
1801 {
1802         if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
1803                 obj1 = to_union(ctx, obj1);
1804         if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
1805                 obj2 = to_union(ctx, obj2);
1806         if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
1807                 obj1 = to_union(ctx, obj1);
1808         if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
1809                 obj2 = to_union(ctx, obj2);
1810         if (obj1.type == isl_obj_pw_qpolynomial &&
1811             obj2.type == isl_obj_union_pw_qpolynomial)
1812                 obj1 = to_union(ctx, obj1);
1813         if (obj1.type == isl_obj_union_pw_qpolynomial &&
1814             obj2.type == isl_obj_pw_qpolynomial)
1815                 obj2 = to_union(ctx, obj2);
1816         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1817             obj2.type == isl_obj_union_pw_qpolynomial_fold)
1818                 obj1 = to_union(ctx, obj1);
1819         if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
1820             obj2.type == isl_obj_pw_qpolynomial_fold)
1821                 obj2 = to_union(ctx, obj2);
1822         isl_assert(ctx, obj1.type == obj2.type, goto error);
1823         if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
1824                 obj1 = to_union(ctx, obj1);
1825                 obj2 = to_union(ctx, obj2);
1826         }
1827         if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
1828                 obj1 = to_union(ctx, obj1);
1829                 obj2 = to_union(ctx, obj2);
1830         }
1831         if (obj1.type == isl_obj_pw_qpolynomial &&
1832             !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
1833                 obj1 = to_union(ctx, obj1);
1834                 obj2 = to_union(ctx, obj2);
1835         }
1836         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1837             !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
1838                 obj1 = to_union(ctx, obj1);
1839                 obj2 = to_union(ctx, obj2);
1840         }
1841         obj1.v = obj1.type->add(obj1.v, obj2.v);
1842         return obj1;
1843 error:
1844         obj1.type->free(obj1.v);
1845         obj2.type->free(obj2.v);
1846         obj1.type = isl_obj_none;
1847         obj1.v = NULL;
1848         return obj1;
1849 }
1850
1851 static struct isl_obj obj_read(struct isl_stream *s)
1852 {
1853         isl_map *map = NULL;
1854         struct isl_token *tok;
1855         struct vars *v = NULL;
1856         struct isl_obj obj = { isl_obj_set, NULL };
1857
1858         tok = next_token(s);
1859         if (!tok) {
1860                 isl_stream_error(s, NULL, "unexpected EOF");
1861                 goto error;
1862         }
1863         if (tok->type == ISL_TOKEN_VALUE) {
1864                 struct isl_token *tok2;
1865                 struct isl_map *map;
1866
1867                 tok2 = isl_stream_next_token(s);
1868                 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
1869                     isl_int_is_neg(tok2->u.v)) {
1870                         if (tok2)
1871                                 isl_stream_push_token(s, tok2);
1872                         obj.type = isl_obj_int;
1873                         obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
1874                         isl_token_free(tok);
1875                         return obj;
1876                 }
1877                 isl_stream_push_token(s, tok2);
1878                 isl_stream_push_token(s, tok);
1879                 map = map_read_polylib(s);
1880                 if (!map)
1881                         goto error;
1882                 if (isl_map_may_be_set(map))
1883                         obj.v = isl_map_range(map);
1884                 else {
1885                         obj.type = isl_obj_map;
1886                         obj.v = map;
1887                 }
1888                 return obj;
1889         }
1890         v = vars_new(s->ctx);
1891         if (!v) {
1892                 isl_stream_push_token(s, tok);
1893                 goto error;
1894         }
1895         map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
1896         if (tok->type == '[') {
1897                 isl_stream_push_token(s, tok);
1898                 map = read_tuple(s, map, isl_dim_param, v);
1899                 if (!map)
1900                         goto error;
1901                 tok = isl_stream_next_token(s);
1902                 if (!tok || tok->type != ISL_TOKEN_TO) {
1903                         isl_stream_error(s, tok, "expecting '->'");
1904                         if (tok)
1905                                 isl_stream_push_token(s, tok);
1906                         goto error;
1907                 }
1908                 isl_token_free(tok);
1909                 tok = isl_stream_next_token(s);
1910         }
1911         if (!tok || tok->type != '{') {
1912                 isl_stream_error(s, tok, "expecting '{'");
1913                 if (tok)
1914                         isl_stream_push_token(s, tok);
1915                 goto error;
1916         }
1917         isl_token_free(tok);
1918
1919         tok = isl_stream_next_token(s);
1920         if (!tok)
1921                 ;
1922         else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
1923                 isl_token_free(tok);
1924                 if (isl_stream_eat(s, '='))
1925                         goto error;
1926                 map = read_tuple(s, map, isl_dim_param, v);
1927                 if (!map)
1928                         goto error;
1929         } else if (tok->type == '}') {
1930                 obj.type = isl_obj_union_set;
1931                 obj.v = isl_union_set_empty(isl_map_get_space(map));
1932                 isl_token_free(tok);
1933                 goto done;
1934         } else
1935                 isl_stream_push_token(s, tok);
1936
1937         for (;;) {
1938                 struct isl_obj o;
1939                 tok = NULL;
1940                 o = obj_read_body(s, isl_map_copy(map), v);
1941                 if (o.type == isl_obj_none || !o.v)
1942                         goto error;
1943                 if (!obj.v)
1944                         obj = o;
1945                 else {
1946                         obj = obj_add(s->ctx, obj, o);
1947                         if (obj.type == isl_obj_none || !obj.v)
1948                                 goto error;
1949                 }
1950                 tok = isl_stream_next_token(s);
1951                 if (!tok || tok->type != ';')
1952                         break;
1953                 isl_token_free(tok);
1954                 if (isl_stream_next_token_is(s, '}')) {
1955                         tok = isl_stream_next_token(s);
1956                         break;
1957                 }
1958         }
1959
1960         if (tok && tok->type == '}') {
1961                 isl_token_free(tok);
1962         } else {
1963                 isl_stream_error(s, tok, "unexpected isl_token");
1964                 if (tok)
1965                         isl_token_free(tok);
1966                 goto error;
1967         }
1968 done:
1969         vars_free(v);
1970         isl_map_free(map);
1971
1972         return obj;
1973 error:
1974         isl_map_free(map);
1975         obj.type->free(obj.v);
1976         if (v)
1977                 vars_free(v);
1978         obj.v = NULL;
1979         return obj;
1980 }
1981
1982 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
1983 {
1984         return obj_read(s);
1985 }
1986
1987 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
1988 {
1989         struct isl_obj obj;
1990
1991         obj = obj_read(s);
1992         if (obj.v)
1993                 isl_assert(s->ctx, obj.type == isl_obj_map ||
1994                                    obj.type == isl_obj_set, goto error);
1995
1996         return obj.v;
1997 error:
1998         obj.type->free(obj.v);
1999         return NULL;
2000 }
2001
2002 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2003 {
2004         struct isl_obj obj;
2005
2006         obj = obj_read(s);
2007         if (obj.v) {
2008                 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2009                         obj.v = isl_map_range(obj.v);
2010                         obj.type = isl_obj_set;
2011                 }
2012                 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2013         }
2014
2015         return obj.v;
2016 error:
2017         obj.type->free(obj.v);
2018         return NULL;
2019 }
2020
2021 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2022 {
2023         struct isl_obj obj;
2024
2025         obj = obj_read(s);
2026         if (obj.type == isl_obj_map) {
2027                 obj.type = isl_obj_union_map;
2028                 obj.v = isl_union_map_from_map(obj.v);
2029         }
2030         if (obj.type == isl_obj_set) {
2031                 obj.type = isl_obj_union_set;
2032                 obj.v = isl_union_set_from_set(obj.v);
2033         }
2034         if (obj.v)
2035                 isl_assert(s->ctx, obj.type == isl_obj_union_map ||
2036                                    obj.type == isl_obj_union_set, goto error);
2037
2038         return obj.v;
2039 error:
2040         obj.type->free(obj.v);
2041         return NULL;
2042 }
2043
2044 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2045 {
2046         struct isl_obj obj;
2047
2048         obj = obj_read(s);
2049         if (obj.type == isl_obj_set) {
2050                 obj.type = isl_obj_union_set;
2051                 obj.v = isl_union_set_from_set(obj.v);
2052         }
2053         if (obj.v)
2054                 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2055
2056         return obj.v;
2057 error:
2058         obj.type->free(obj.v);
2059         return NULL;
2060 }
2061
2062 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2063 {
2064         struct isl_obj obj;
2065         struct isl_map *map;
2066         struct isl_basic_map *bmap;
2067
2068         obj = obj_read(s);
2069         map = obj.v;
2070         if (!map)
2071                 return NULL;
2072
2073         isl_assert(map->ctx, map->n <= 1, goto error);
2074
2075         if (map->n == 0)
2076                 bmap = isl_basic_map_empty_like_map(map);
2077         else
2078                 bmap = isl_basic_map_copy(map->p[0]);
2079
2080         isl_map_free(map);
2081
2082         return bmap;
2083 error:
2084         isl_map_free(map);
2085         return NULL;
2086 }
2087
2088 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2089 {
2090         isl_basic_map *bmap;
2091         bmap = basic_map_read(s);
2092         if (!bmap)
2093                 return NULL;
2094         if (!isl_basic_map_may_be_set(bmap))
2095                 isl_die(s->ctx, isl_error_invalid,
2096                         "input is not a set", goto error);
2097         return isl_basic_map_range(bmap);
2098 error:
2099         isl_basic_map_free(bmap);
2100         return NULL;
2101 }
2102
2103 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2104         FILE *input)
2105 {
2106         struct isl_basic_map *bmap;
2107         struct isl_stream *s = isl_stream_new_file(ctx, input);
2108         if (!s)
2109                 return NULL;
2110         bmap = basic_map_read(s);
2111         isl_stream_free(s);
2112         return bmap;
2113 }
2114
2115 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2116         FILE *input)
2117 {
2118         isl_basic_set *bset;
2119         struct isl_stream *s = isl_stream_new_file(ctx, input);
2120         if (!s)
2121                 return NULL;
2122         bset = basic_set_read(s);
2123         isl_stream_free(s);
2124         return bset;
2125 }
2126
2127 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2128         const char *str)
2129 {
2130         struct isl_basic_map *bmap;
2131         struct isl_stream *s = isl_stream_new_str(ctx, str);
2132         if (!s)
2133                 return NULL;
2134         bmap = basic_map_read(s);
2135         isl_stream_free(s);
2136         return bmap;
2137 }
2138
2139 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2140         const char *str)
2141 {
2142         isl_basic_set *bset;
2143         struct isl_stream *s = isl_stream_new_str(ctx, str);
2144         if (!s)
2145                 return NULL;
2146         bset = basic_set_read(s);
2147         isl_stream_free(s);
2148         return bset;
2149 }
2150
2151 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2152         FILE *input)
2153 {
2154         struct isl_map *map;
2155         struct isl_stream *s = isl_stream_new_file(ctx, input);
2156         if (!s)
2157                 return NULL;
2158         map = isl_stream_read_map(s);
2159         isl_stream_free(s);
2160         return map;
2161 }
2162
2163 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2164         const char *str)
2165 {
2166         struct isl_map *map;
2167         struct isl_stream *s = isl_stream_new_str(ctx, str);
2168         if (!s)
2169                 return NULL;
2170         map = isl_stream_read_map(s);
2171         isl_stream_free(s);
2172         return map;
2173 }
2174
2175 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2176         FILE *input)
2177 {
2178         isl_set *set;
2179         struct isl_stream *s = isl_stream_new_file(ctx, input);
2180         if (!s)
2181                 return NULL;
2182         set = isl_stream_read_set(s);
2183         isl_stream_free(s);
2184         return set;
2185 }
2186
2187 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2188         const char *str)
2189 {
2190         isl_set *set;
2191         struct isl_stream *s = isl_stream_new_str(ctx, str);
2192         if (!s)
2193                 return NULL;
2194         set = isl_stream_read_set(s);
2195         isl_stream_free(s);
2196         return set;
2197 }
2198
2199 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2200         FILE *input)
2201 {
2202         isl_union_map *umap;
2203         struct isl_stream *s = isl_stream_new_file(ctx, input);
2204         if (!s)
2205                 return NULL;
2206         umap = isl_stream_read_union_map(s);
2207         isl_stream_free(s);
2208         return umap;
2209 }
2210
2211 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2212                 const char *str)
2213 {
2214         isl_union_map *umap;
2215         struct isl_stream *s = isl_stream_new_str(ctx, str);
2216         if (!s)
2217                 return NULL;
2218         umap = isl_stream_read_union_map(s);
2219         isl_stream_free(s);
2220         return umap;
2221 }
2222
2223 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2224         FILE *input)
2225 {
2226         isl_union_set *uset;
2227         struct isl_stream *s = isl_stream_new_file(ctx, input);
2228         if (!s)
2229                 return NULL;
2230         uset = isl_stream_read_union_set(s);
2231         isl_stream_free(s);
2232         return uset;
2233 }
2234
2235 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2236                 const char *str)
2237 {
2238         isl_union_set *uset;
2239         struct isl_stream *s = isl_stream_new_str(ctx, str);
2240         if (!s)
2241                 return NULL;
2242         uset = isl_stream_read_union_set(s);
2243         isl_stream_free(s);
2244         return uset;
2245 }
2246
2247 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2248 {
2249         struct isl_vec *vec = NULL;
2250         struct isl_token *tok;
2251         unsigned size;
2252         int j;
2253
2254         tok = isl_stream_next_token(s);
2255         if (!tok || tok->type != ISL_TOKEN_VALUE) {
2256                 isl_stream_error(s, tok, "expecting vector length");
2257                 goto error;
2258         }
2259
2260         size = isl_int_get_si(tok->u.v);
2261         isl_token_free(tok);
2262
2263         vec = isl_vec_alloc(s->ctx, size);
2264
2265         for (j = 0; j < size; ++j) {
2266                 tok = isl_stream_next_token(s);
2267                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2268                         isl_stream_error(s, tok, "expecting constant value");
2269                         goto error;
2270                 }
2271                 isl_int_set(vec->el[j], tok->u.v);
2272                 isl_token_free(tok);
2273         }
2274
2275         return vec;
2276 error:
2277         isl_token_free(tok);
2278         isl_vec_free(vec);
2279         return NULL;
2280 }
2281
2282 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2283 {
2284         return isl_vec_read_polylib(s);
2285 }
2286
2287 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2288 {
2289         isl_vec *v;
2290         struct isl_stream *s = isl_stream_new_file(ctx, input);
2291         if (!s)
2292                 return NULL;
2293         v = vec_read(s);
2294         isl_stream_free(s);
2295         return v;
2296 }
2297
2298 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2299         struct isl_stream *s)
2300 {
2301         struct isl_obj obj;
2302
2303         obj = obj_read(s);
2304         if (obj.v)
2305                 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2306                            goto error);
2307
2308         return obj.v;
2309 error:
2310         obj.type->free(obj.v);
2311         return NULL;
2312 }
2313
2314 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2315                 const char *str)
2316 {
2317         isl_pw_qpolynomial *pwqp;
2318         struct isl_stream *s = isl_stream_new_str(ctx, str);
2319         if (!s)
2320                 return NULL;
2321         pwqp = isl_stream_read_pw_qpolynomial(s);
2322         isl_stream_free(s);
2323         return pwqp;
2324 }
2325
2326 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2327                 FILE *input)
2328 {
2329         isl_pw_qpolynomial *pwqp;
2330         struct isl_stream *s = isl_stream_new_file(ctx, input);
2331         if (!s)
2332                 return NULL;
2333         pwqp = isl_stream_read_pw_qpolynomial(s);
2334         isl_stream_free(s);
2335         return pwqp;
2336 }
2337
2338 /* Read an affine expression from "s" with domain (space) "dom".
2339  * We call accept_affine to parse a possibly piecewise affine expression
2340  * and then check that the result is a single affine expression on
2341  * a universe domain.
2342  */
2343 static __isl_give isl_aff *read_aff_with_dom(struct isl_stream *s,
2344         __isl_take isl_set *dom, struct vars *v)
2345 {
2346         isl_aff *aff = NULL;
2347         isl_pw_aff *pwaff = NULL;
2348
2349         if (!isl_set_plain_is_universe(dom))
2350                 isl_die(s->ctx, isl_error_invalid,
2351                         "expecting universe domain", goto error);
2352
2353         if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2354                 goto error;
2355
2356         if (isl_stream_eat(s, '['))
2357                 goto error;
2358
2359         pwaff = accept_affine(s, isl_set_get_space(dom), v);
2360
2361         if (isl_stream_eat(s, ']'))
2362                 goto error;
2363         if (isl_stream_eat(s, '}'))
2364                 goto error;
2365
2366         if (!pwaff)
2367                 goto error;
2368
2369         if (pwaff->n != 1)
2370                 isl_die(s->ctx, isl_error_invalid,
2371                         "expecting single affine expression", goto error);
2372         if (!isl_set_plain_is_universe(pwaff->p[0].set))
2373                 isl_die(s->ctx, isl_error_invalid,
2374                         "expecting universe domain", goto error);
2375
2376         aff = isl_aff_copy(pwaff->p[0].aff);
2377
2378         vars_free(v);
2379         isl_pw_aff_free(pwaff);
2380         isl_set_free(dom);
2381         return aff;
2382 error:
2383         vars_free(v);
2384         isl_pw_aff_free(pwaff);
2385         isl_set_free(dom);
2386         return NULL;
2387 }
2388
2389 /* Is the next token an identifer not in "v"?
2390  */
2391 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2392 {
2393         int n = v->n;
2394         int fresh;
2395         struct isl_token *tok;
2396
2397         tok = isl_stream_next_token(s);
2398         if (!tok)
2399                 return 0;
2400         fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2401         isl_stream_push_token(s, tok);
2402
2403         vars_drop(v, v->n - n);
2404
2405         return fresh;
2406 }
2407
2408 /* First read the domain of the affine expression, which may be
2409  * a parameter space or a set.
2410  * The tricky part is that we don't know if the domain is a set or not,
2411  * so when we are trying to read the domain, we may actually be reading
2412  * the affine expression itself (defined on a parameter domains)
2413  * If the tuple we are reading is named, we assume it's the domain.
2414  * Also, if inside the tuple, the first thing we find is a nested tuple
2415  * or a new identifier, we again assume it's the domain.
2416  * Otherwise, we assume we are reading an affine expression.
2417  */
2418 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2419         __isl_take isl_set *dom, struct vars *v)
2420 {
2421         struct isl_token *tok;
2422
2423         tok = isl_stream_next_token(s);
2424         if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2425                 isl_stream_push_token(s, tok);
2426                 return read_tuple(s, dom, isl_dim_set, v);
2427         }
2428         if (!tok || tok->type != '[') {
2429                 isl_stream_error(s, tok, "expecting '['");
2430                 goto error;
2431         }
2432         if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2433                 isl_stream_push_token(s, tok);
2434                 dom = read_tuple(s, dom, isl_dim_set, v);
2435         } else
2436                 isl_stream_push_token(s, tok);
2437
2438         return dom;
2439 error:
2440         if (tok)
2441                 isl_stream_push_token(s, tok);
2442         vars_free(v);
2443         isl_set_free(dom);
2444         return NULL;
2445 }
2446
2447 /* Read an affine expression from "s".
2448  * We first read the domain of the affine expression, which may be
2449  * a parameter space or a set, and then call read_aff_with_dom.
2450  */
2451 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2452 {
2453         struct vars *v;
2454         isl_set *dom = NULL;
2455
2456         v = vars_new(s->ctx);
2457         if (!v)
2458                 return NULL;
2459
2460         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2461         if (next_is_tuple(s)) {
2462                 dom = read_tuple(s, dom, isl_dim_param, v);
2463                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2464                         goto error;
2465         }
2466         if (isl_stream_eat(s, '{'))
2467                 goto error;
2468
2469         dom = read_aff_domain(s, dom, v);
2470         return read_aff_with_dom(s, dom, v);
2471 error:
2472         vars_free(v);
2473         isl_set_free(dom);
2474         return NULL;
2475 }
2476
2477 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2478  */
2479 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2480         __isl_take isl_set *dom, struct vars *v)
2481 {
2482         isl_pw_aff *pwaff = NULL;
2483
2484         if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2485                 goto error;
2486
2487         if (isl_stream_eat(s, '['))
2488                 goto error;
2489
2490         pwaff = accept_affine(s, isl_set_get_space(dom), v);
2491
2492         if (isl_stream_eat(s, ']'))
2493                 goto error;
2494
2495         dom = read_optional_disjuncts(s, dom, v);
2496         pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2497
2498         return pwaff;
2499 error:
2500         isl_set_free(dom);
2501         isl_pw_aff_free(pwaff);
2502         return NULL;
2503 }
2504
2505 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
2506 {
2507         struct vars *v;
2508         isl_set *dom = NULL;
2509         isl_set *aff_dom;
2510         isl_pw_aff *pa = NULL;
2511         int n;
2512
2513         v = vars_new(s->ctx);
2514         if (!v)
2515                 return NULL;
2516
2517         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2518         if (next_is_tuple(s)) {
2519                 dom = read_tuple(s, dom, isl_dim_param, v);
2520                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2521                         goto error;
2522         }
2523         if (isl_stream_eat(s, '{'))
2524                 goto error;
2525
2526         n = v->n;
2527         aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2528         pa = read_pw_aff_with_dom(s, aff_dom, v);
2529         vars_drop(v, v->n - n);
2530
2531         while (isl_stream_eat_if_available(s, ';')) {
2532                 isl_pw_aff *pa_i;
2533
2534                 n = v->n;
2535                 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2536                 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
2537                 vars_drop(v, v->n - n);
2538
2539                 pa = isl_pw_aff_add(pa, pa_i);
2540         }
2541
2542         if (isl_stream_eat(s, '}'))
2543                 goto error;
2544
2545         vars_free(v);
2546         isl_set_free(dom);
2547         return pa;
2548 error:
2549         vars_free(v);
2550         isl_set_free(dom);
2551         isl_pw_aff_free(pa);
2552         return NULL;
2553 }
2554
2555 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
2556 {
2557         isl_aff *aff;
2558         struct isl_stream *s = isl_stream_new_str(ctx, str);
2559         if (!s)
2560                 return NULL;
2561         aff = isl_stream_read_aff(s);
2562         isl_stream_free(s);
2563         return aff;
2564 }
2565
2566 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
2567 {
2568         isl_pw_aff *pa;
2569         struct isl_stream *s = isl_stream_new_str(ctx, str);
2570         if (!s)
2571                 return NULL;
2572         pa = isl_stream_read_pw_aff(s);
2573         isl_stream_free(s);
2574         return pa;
2575 }
2576
2577 /* Read an isl_pw_multi_aff from "s".
2578  * We currently read a generic object and if it turns out to be a set or
2579  * a map, we convert that to an isl_pw_multi_aff.
2580  * It would be more efficient if we were to construct the isl_pw_multi_aff
2581  * directly.
2582  */
2583 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
2584 {
2585         struct isl_obj obj;
2586
2587         obj = obj_read(s);
2588         if (!obj.v)
2589                 return NULL;
2590
2591         if (obj.type == isl_obj_map)
2592                 return isl_pw_multi_aff_from_map(obj.v);
2593         if (obj.type == isl_obj_set)
2594                 return isl_pw_multi_aff_from_set(obj.v);
2595
2596         obj.type->free(obj.v);
2597         isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2598                 return NULL);
2599 }
2600
2601 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
2602         const char *str)
2603 {
2604         isl_pw_multi_aff *pma;
2605         struct isl_stream *s = isl_stream_new_str(ctx, str);
2606         if (!s)
2607                 return NULL;
2608         pma = isl_stream_read_pw_multi_aff(s);
2609         isl_stream_free(s);
2610         return pma;
2611 }