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