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 && tok->type == ISL_TOKEN_TO) {
1759                 obj.type = isl_obj_map;
1760                 isl_token_free(tok);
1761                 if (!next_is_tuple(s)) {
1762                         isl_set *set = isl_map_domain(map);
1763                         return obj_read_poly_or_fold(s, set, v, n);
1764                 }
1765                 map = read_tuple(s, map, isl_dim_out, v);
1766                 if (!map)
1767                         goto error;
1768         } else {
1769                 map = isl_map_reverse(map);
1770                 if (tok)
1771                         isl_stream_push_token(s, tok);
1772         }
1773
1774         map = read_optional_disjuncts(s, map, v);
1775
1776         vars_drop(v, v->n - n);
1777
1778         obj.v = map;
1779         return obj;
1780 error:
1781         isl_map_free(map);
1782         obj.type = isl_obj_none;
1783         return obj;
1784 }
1785
1786 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
1787 {
1788         if (obj.type == isl_obj_map) {
1789                 obj.v = isl_union_map_from_map(obj.v);
1790                 obj.type = isl_obj_union_map;
1791         } else if (obj.type == isl_obj_set) {
1792                 obj.v = isl_union_set_from_set(obj.v);
1793                 obj.type = isl_obj_union_set;
1794         } else if (obj.type == isl_obj_pw_qpolynomial) {
1795                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
1796                 obj.type = isl_obj_union_pw_qpolynomial;
1797         } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
1798                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
1799                 obj.type = isl_obj_union_pw_qpolynomial_fold;
1800         } else
1801                 isl_assert(ctx, 0, goto error);
1802         return obj;
1803 error:
1804         obj.type->free(obj.v);
1805         obj.type = isl_obj_none;
1806         return obj;
1807 }
1808
1809 static struct isl_obj obj_add(struct isl_ctx *ctx,
1810         struct isl_obj obj1, struct isl_obj obj2)
1811 {
1812         if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
1813                 obj1 = to_union(ctx, obj1);
1814         if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
1815                 obj2 = to_union(ctx, obj2);
1816         if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
1817                 obj1 = to_union(ctx, obj1);
1818         if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
1819                 obj2 = to_union(ctx, obj2);
1820         if (obj1.type == isl_obj_pw_qpolynomial &&
1821             obj2.type == isl_obj_union_pw_qpolynomial)
1822                 obj1 = to_union(ctx, obj1);
1823         if (obj1.type == isl_obj_union_pw_qpolynomial &&
1824             obj2.type == isl_obj_pw_qpolynomial)
1825                 obj2 = to_union(ctx, obj2);
1826         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1827             obj2.type == isl_obj_union_pw_qpolynomial_fold)
1828                 obj1 = to_union(ctx, obj1);
1829         if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
1830             obj2.type == isl_obj_pw_qpolynomial_fold)
1831                 obj2 = to_union(ctx, obj2);
1832         isl_assert(ctx, obj1.type == obj2.type, goto error);
1833         if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
1834                 obj1 = to_union(ctx, obj1);
1835                 obj2 = to_union(ctx, obj2);
1836         }
1837         if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
1838                 obj1 = to_union(ctx, obj1);
1839                 obj2 = to_union(ctx, obj2);
1840         }
1841         if (obj1.type == isl_obj_pw_qpolynomial &&
1842             !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
1843                 obj1 = to_union(ctx, obj1);
1844                 obj2 = to_union(ctx, obj2);
1845         }
1846         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1847             !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
1848                 obj1 = to_union(ctx, obj1);
1849                 obj2 = to_union(ctx, obj2);
1850         }
1851         obj1.v = obj1.type->add(obj1.v, obj2.v);
1852         return obj1;
1853 error:
1854         obj1.type->free(obj1.v);
1855         obj2.type->free(obj2.v);
1856         obj1.type = isl_obj_none;
1857         obj1.v = NULL;
1858         return obj1;
1859 }
1860
1861 static struct isl_obj obj_read(struct isl_stream *s)
1862 {
1863         isl_map *map = NULL;
1864         struct isl_token *tok;
1865         struct vars *v = NULL;
1866         struct isl_obj obj = { isl_obj_set, NULL };
1867
1868         tok = next_token(s);
1869         if (!tok) {
1870                 isl_stream_error(s, NULL, "unexpected EOF");
1871                 goto error;
1872         }
1873         if (tok->type == ISL_TOKEN_VALUE) {
1874                 struct isl_token *tok2;
1875                 struct isl_map *map;
1876
1877                 tok2 = isl_stream_next_token(s);
1878                 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
1879                     isl_int_is_neg(tok2->u.v)) {
1880                         if (tok2)
1881                                 isl_stream_push_token(s, tok2);
1882                         obj.type = isl_obj_int;
1883                         obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
1884                         isl_token_free(tok);
1885                         return obj;
1886                 }
1887                 isl_stream_push_token(s, tok2);
1888                 isl_stream_push_token(s, tok);
1889                 map = map_read_polylib(s);
1890                 if (!map)
1891                         goto error;
1892                 if (isl_map_may_be_set(map))
1893                         obj.v = isl_map_range(map);
1894                 else {
1895                         obj.type = isl_obj_map;
1896                         obj.v = map;
1897                 }
1898                 return obj;
1899         }
1900         v = vars_new(s->ctx);
1901         if (!v) {
1902                 isl_stream_push_token(s, tok);
1903                 goto error;
1904         }
1905         map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
1906         if (tok->type == '[') {
1907                 isl_stream_push_token(s, tok);
1908                 map = read_tuple(s, map, isl_dim_param, v);
1909                 if (!map)
1910                         goto error;
1911                 tok = isl_stream_next_token(s);
1912                 if (!tok || tok->type != ISL_TOKEN_TO) {
1913                         isl_stream_error(s, tok, "expecting '->'");
1914                         if (tok)
1915                                 isl_stream_push_token(s, tok);
1916                         goto error;
1917                 }
1918                 isl_token_free(tok);
1919                 tok = isl_stream_next_token(s);
1920         }
1921         if (!tok || tok->type != '{') {
1922                 isl_stream_error(s, tok, "expecting '{'");
1923                 if (tok)
1924                         isl_stream_push_token(s, tok);
1925                 goto error;
1926         }
1927         isl_token_free(tok);
1928
1929         tok = isl_stream_next_token(s);
1930         if (!tok)
1931                 ;
1932         else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
1933                 isl_token_free(tok);
1934                 if (isl_stream_eat(s, '='))
1935                         goto error;
1936                 map = read_tuple(s, map, isl_dim_param, v);
1937                 if (!map)
1938                         goto error;
1939         } else if (tok->type == '}') {
1940                 obj.type = isl_obj_union_set;
1941                 obj.v = isl_union_set_empty(isl_map_get_space(map));
1942                 isl_token_free(tok);
1943                 goto done;
1944         } else
1945                 isl_stream_push_token(s, tok);
1946
1947         for (;;) {
1948                 struct isl_obj o;
1949                 tok = NULL;
1950                 o = obj_read_body(s, isl_map_copy(map), v);
1951                 if (o.type == isl_obj_none || !o.v)
1952                         goto error;
1953                 if (!obj.v)
1954                         obj = o;
1955                 else {
1956                         obj = obj_add(s->ctx, obj, o);
1957                         if (obj.type == isl_obj_none || !obj.v)
1958                                 goto error;
1959                 }
1960                 tok = isl_stream_next_token(s);
1961                 if (!tok || tok->type != ';')
1962                         break;
1963                 isl_token_free(tok);
1964                 if (isl_stream_next_token_is(s, '}')) {
1965                         tok = isl_stream_next_token(s);
1966                         break;
1967                 }
1968         }
1969
1970         if (tok && tok->type == '}') {
1971                 isl_token_free(tok);
1972         } else {
1973                 isl_stream_error(s, tok, "unexpected isl_token");
1974                 if (tok)
1975                         isl_token_free(tok);
1976                 goto error;
1977         }
1978 done:
1979         vars_free(v);
1980         isl_map_free(map);
1981
1982         return obj;
1983 error:
1984         isl_map_free(map);
1985         obj.type->free(obj.v);
1986         if (v)
1987                 vars_free(v);
1988         obj.v = NULL;
1989         return obj;
1990 }
1991
1992 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
1993 {
1994         return obj_read(s);
1995 }
1996
1997 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
1998 {
1999         struct isl_obj obj;
2000
2001         obj = obj_read(s);
2002         if (obj.v)
2003                 isl_assert(s->ctx, obj.type == isl_obj_map ||
2004                                    obj.type == isl_obj_set, goto error);
2005
2006         if (obj.type == isl_obj_set)
2007                 obj.v = isl_map_from_range(obj.v);
2008
2009         return obj.v;
2010 error:
2011         obj.type->free(obj.v);
2012         return NULL;
2013 }
2014
2015 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2016 {
2017         struct isl_obj obj;
2018
2019         obj = obj_read(s);
2020         if (obj.v) {
2021                 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2022                         obj.v = isl_map_range(obj.v);
2023                         obj.type = isl_obj_set;
2024                 }
2025                 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2026         }
2027
2028         return obj.v;
2029 error:
2030         obj.type->free(obj.v);
2031         return NULL;
2032 }
2033
2034 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2035 {
2036         struct isl_obj obj;
2037
2038         obj = obj_read(s);
2039         if (obj.type == isl_obj_map) {
2040                 obj.type = isl_obj_union_map;
2041                 obj.v = isl_union_map_from_map(obj.v);
2042         }
2043         if (obj.type == isl_obj_set) {
2044                 obj.type = isl_obj_union_set;
2045                 obj.v = isl_union_set_from_set(obj.v);
2046         }
2047         if (obj.v)
2048                 isl_assert(s->ctx, obj.type == isl_obj_union_map ||
2049                                    obj.type == isl_obj_union_set, goto error);
2050
2051         return obj.v;
2052 error:
2053         obj.type->free(obj.v);
2054         return NULL;
2055 }
2056
2057 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2058 {
2059         struct isl_obj obj;
2060
2061         obj = obj_read(s);
2062         if (obj.type == isl_obj_set) {
2063                 obj.type = isl_obj_union_set;
2064                 obj.v = isl_union_set_from_set(obj.v);
2065         }
2066         if (obj.v)
2067                 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2068
2069         return obj.v;
2070 error:
2071         obj.type->free(obj.v);
2072         return NULL;
2073 }
2074
2075 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2076 {
2077         struct isl_obj obj;
2078         struct isl_map *map;
2079         struct isl_basic_map *bmap;
2080
2081         obj = obj_read(s);
2082         map = obj.v;
2083         if (!map)
2084                 return NULL;
2085
2086         isl_assert(map->ctx, map->n <= 1, goto error);
2087
2088         if (map->n == 0)
2089                 bmap = isl_basic_map_empty_like_map(map);
2090         else
2091                 bmap = isl_basic_map_copy(map->p[0]);
2092
2093         isl_map_free(map);
2094
2095         return bmap;
2096 error:
2097         isl_map_free(map);
2098         return NULL;
2099 }
2100
2101 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2102 {
2103         isl_basic_map *bmap;
2104         bmap = basic_map_read(s);
2105         if (!bmap)
2106                 return NULL;
2107         if (!isl_basic_map_may_be_set(bmap))
2108                 isl_die(s->ctx, isl_error_invalid,
2109                         "input is not a set", goto error);
2110         return isl_basic_map_range(bmap);
2111 error:
2112         isl_basic_map_free(bmap);
2113         return NULL;
2114 }
2115
2116 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2117         FILE *input)
2118 {
2119         struct isl_basic_map *bmap;
2120         struct isl_stream *s = isl_stream_new_file(ctx, input);
2121         if (!s)
2122                 return NULL;
2123         bmap = basic_map_read(s);
2124         isl_stream_free(s);
2125         return bmap;
2126 }
2127
2128 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2129         FILE *input)
2130 {
2131         isl_basic_set *bset;
2132         struct isl_stream *s = isl_stream_new_file(ctx, input);
2133         if (!s)
2134                 return NULL;
2135         bset = basic_set_read(s);
2136         isl_stream_free(s);
2137         return bset;
2138 }
2139
2140 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2141         const char *str)
2142 {
2143         struct isl_basic_map *bmap;
2144         struct isl_stream *s = isl_stream_new_str(ctx, str);
2145         if (!s)
2146                 return NULL;
2147         bmap = basic_map_read(s);
2148         isl_stream_free(s);
2149         return bmap;
2150 }
2151
2152 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2153         const char *str)
2154 {
2155         isl_basic_set *bset;
2156         struct isl_stream *s = isl_stream_new_str(ctx, str);
2157         if (!s)
2158                 return NULL;
2159         bset = basic_set_read(s);
2160         isl_stream_free(s);
2161         return bset;
2162 }
2163
2164 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2165         FILE *input)
2166 {
2167         struct isl_map *map;
2168         struct isl_stream *s = isl_stream_new_file(ctx, input);
2169         if (!s)
2170                 return NULL;
2171         map = isl_stream_read_map(s);
2172         isl_stream_free(s);
2173         return map;
2174 }
2175
2176 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2177         const char *str)
2178 {
2179         struct isl_map *map;
2180         struct isl_stream *s = isl_stream_new_str(ctx, str);
2181         if (!s)
2182                 return NULL;
2183         map = isl_stream_read_map(s);
2184         isl_stream_free(s);
2185         return map;
2186 }
2187
2188 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2189         FILE *input)
2190 {
2191         isl_set *set;
2192         struct isl_stream *s = isl_stream_new_file(ctx, input);
2193         if (!s)
2194                 return NULL;
2195         set = isl_stream_read_set(s);
2196         isl_stream_free(s);
2197         return set;
2198 }
2199
2200 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2201         const char *str)
2202 {
2203         isl_set *set;
2204         struct isl_stream *s = isl_stream_new_str(ctx, str);
2205         if (!s)
2206                 return NULL;
2207         set = isl_stream_read_set(s);
2208         isl_stream_free(s);
2209         return set;
2210 }
2211
2212 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2213         FILE *input)
2214 {
2215         isl_union_map *umap;
2216         struct isl_stream *s = isl_stream_new_file(ctx, input);
2217         if (!s)
2218                 return NULL;
2219         umap = isl_stream_read_union_map(s);
2220         isl_stream_free(s);
2221         return umap;
2222 }
2223
2224 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2225                 const char *str)
2226 {
2227         isl_union_map *umap;
2228         struct isl_stream *s = isl_stream_new_str(ctx, str);
2229         if (!s)
2230                 return NULL;
2231         umap = isl_stream_read_union_map(s);
2232         isl_stream_free(s);
2233         return umap;
2234 }
2235
2236 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2237         FILE *input)
2238 {
2239         isl_union_set *uset;
2240         struct isl_stream *s = isl_stream_new_file(ctx, input);
2241         if (!s)
2242                 return NULL;
2243         uset = isl_stream_read_union_set(s);
2244         isl_stream_free(s);
2245         return uset;
2246 }
2247
2248 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2249                 const char *str)
2250 {
2251         isl_union_set *uset;
2252         struct isl_stream *s = isl_stream_new_str(ctx, str);
2253         if (!s)
2254                 return NULL;
2255         uset = isl_stream_read_union_set(s);
2256         isl_stream_free(s);
2257         return uset;
2258 }
2259
2260 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2261 {
2262         struct isl_vec *vec = NULL;
2263         struct isl_token *tok;
2264         unsigned size;
2265         int j;
2266
2267         tok = isl_stream_next_token(s);
2268         if (!tok || tok->type != ISL_TOKEN_VALUE) {
2269                 isl_stream_error(s, tok, "expecting vector length");
2270                 goto error;
2271         }
2272
2273         size = isl_int_get_si(tok->u.v);
2274         isl_token_free(tok);
2275
2276         vec = isl_vec_alloc(s->ctx, size);
2277
2278         for (j = 0; j < size; ++j) {
2279                 tok = isl_stream_next_token(s);
2280                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2281                         isl_stream_error(s, tok, "expecting constant value");
2282                         goto error;
2283                 }
2284                 isl_int_set(vec->el[j], tok->u.v);
2285                 isl_token_free(tok);
2286         }
2287
2288         return vec;
2289 error:
2290         isl_token_free(tok);
2291         isl_vec_free(vec);
2292         return NULL;
2293 }
2294
2295 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2296 {
2297         return isl_vec_read_polylib(s);
2298 }
2299
2300 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2301 {
2302         isl_vec *v;
2303         struct isl_stream *s = isl_stream_new_file(ctx, input);
2304         if (!s)
2305                 return NULL;
2306         v = vec_read(s);
2307         isl_stream_free(s);
2308         return v;
2309 }
2310
2311 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2312         struct isl_stream *s)
2313 {
2314         struct isl_obj obj;
2315
2316         obj = obj_read(s);
2317         if (obj.v)
2318                 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2319                            goto error);
2320
2321         return obj.v;
2322 error:
2323         obj.type->free(obj.v);
2324         return NULL;
2325 }
2326
2327 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2328                 const char *str)
2329 {
2330         isl_pw_qpolynomial *pwqp;
2331         struct isl_stream *s = isl_stream_new_str(ctx, str);
2332         if (!s)
2333                 return NULL;
2334         pwqp = isl_stream_read_pw_qpolynomial(s);
2335         isl_stream_free(s);
2336         return pwqp;
2337 }
2338
2339 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2340                 FILE *input)
2341 {
2342         isl_pw_qpolynomial *pwqp;
2343         struct isl_stream *s = isl_stream_new_file(ctx, input);
2344         if (!s)
2345                 return NULL;
2346         pwqp = isl_stream_read_pw_qpolynomial(s);
2347         isl_stream_free(s);
2348         return pwqp;
2349 }
2350
2351 /* Read an affine expression from "s" with domain (space) "dom".
2352  * We call accept_affine to parse a possibly piecewise affine expression
2353  * and then check that the result is a single affine expression on
2354  * a universe domain.
2355  */
2356 static __isl_give isl_aff *read_aff_with_dom(struct isl_stream *s,
2357         __isl_take isl_set *dom, struct vars *v)
2358 {
2359         isl_aff *aff = NULL;
2360         isl_pw_aff *pwaff = NULL;
2361
2362         if (!isl_set_plain_is_universe(dom))
2363                 isl_die(s->ctx, isl_error_invalid,
2364                         "expecting universe domain", goto error);
2365
2366         if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2367                 goto error;
2368
2369         if (isl_stream_eat(s, '['))
2370                 goto error;
2371
2372         pwaff = accept_affine(s, isl_set_get_space(dom), v);
2373
2374         if (isl_stream_eat(s, ']'))
2375                 goto error;
2376         if (isl_stream_eat(s, '}'))
2377                 goto error;
2378
2379         if (!pwaff)
2380                 goto error;
2381
2382         if (pwaff->n != 1)
2383                 isl_die(s->ctx, isl_error_invalid,
2384                         "expecting single affine expression", goto error);
2385         if (!isl_set_plain_is_universe(pwaff->p[0].set))
2386                 isl_die(s->ctx, isl_error_invalid,
2387                         "expecting universe domain", goto error);
2388
2389         aff = isl_aff_copy(pwaff->p[0].aff);
2390
2391         vars_free(v);
2392         isl_pw_aff_free(pwaff);
2393         isl_set_free(dom);
2394         return aff;
2395 error:
2396         vars_free(v);
2397         isl_pw_aff_free(pwaff);
2398         isl_set_free(dom);
2399         return NULL;
2400 }
2401
2402 /* Is the next token an identifer not in "v"?
2403  */
2404 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2405 {
2406         int n = v->n;
2407         int fresh;
2408         struct isl_token *tok;
2409
2410         tok = isl_stream_next_token(s);
2411         if (!tok)
2412                 return 0;
2413         fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2414         isl_stream_push_token(s, tok);
2415
2416         vars_drop(v, v->n - n);
2417
2418         return fresh;
2419 }
2420
2421 /* First read the domain of the affine expression, which may be
2422  * a parameter space or a set.
2423  * The tricky part is that we don't know if the domain is a set or not,
2424  * so when we are trying to read the domain, we may actually be reading
2425  * the affine expression itself (defined on a parameter domains)
2426  * If the tuple we are reading is named, we assume it's the domain.
2427  * Also, if inside the tuple, the first thing we find is a nested tuple
2428  * or a new identifier, we again assume it's the domain.
2429  * Otherwise, we assume we are reading an affine expression.
2430  */
2431 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2432         __isl_take isl_set *dom, struct vars *v)
2433 {
2434         struct isl_token *tok;
2435
2436         tok = isl_stream_next_token(s);
2437         if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2438                 isl_stream_push_token(s, tok);
2439                 return read_tuple(s, dom, isl_dim_set, v);
2440         }
2441         if (!tok || tok->type != '[') {
2442                 isl_stream_error(s, tok, "expecting '['");
2443                 goto error;
2444         }
2445         if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2446                 isl_stream_push_token(s, tok);
2447                 dom = read_tuple(s, dom, isl_dim_set, v);
2448         } else
2449                 isl_stream_push_token(s, tok);
2450
2451         return dom;
2452 error:
2453         if (tok)
2454                 isl_stream_push_token(s, tok);
2455         vars_free(v);
2456         isl_set_free(dom);
2457         return NULL;
2458 }
2459
2460 /* Read an affine expression from "s".
2461  * We first read the domain of the affine expression, which may be
2462  * a parameter space or a set, and then call read_aff_with_dom.
2463  */
2464 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2465 {
2466         struct vars *v;
2467         isl_set *dom = NULL;
2468
2469         v = vars_new(s->ctx);
2470         if (!v)
2471                 return NULL;
2472
2473         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2474         if (next_is_tuple(s)) {
2475                 dom = read_tuple(s, dom, isl_dim_param, v);
2476                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2477                         goto error;
2478         }
2479         if (isl_stream_eat(s, '{'))
2480                 goto error;
2481
2482         dom = read_aff_domain(s, dom, v);
2483         return read_aff_with_dom(s, dom, v);
2484 error:
2485         vars_free(v);
2486         isl_set_free(dom);
2487         return NULL;
2488 }
2489
2490 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2491  */
2492 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2493         __isl_take isl_set *dom, struct vars *v)
2494 {
2495         isl_pw_aff *pwaff = NULL;
2496
2497         if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2498                 goto error;
2499
2500         if (isl_stream_eat(s, '['))
2501                 goto error;
2502
2503         pwaff = accept_affine(s, isl_set_get_space(dom), v);
2504
2505         if (isl_stream_eat(s, ']'))
2506                 goto error;
2507
2508         dom = read_optional_disjuncts(s, dom, v);
2509         pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2510
2511         return pwaff;
2512 error:
2513         isl_set_free(dom);
2514         isl_pw_aff_free(pwaff);
2515         return NULL;
2516 }
2517
2518 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
2519 {
2520         struct vars *v;
2521         isl_set *dom = NULL;
2522         isl_set *aff_dom;
2523         isl_pw_aff *pa = NULL;
2524         int n;
2525
2526         v = vars_new(s->ctx);
2527         if (!v)
2528                 return NULL;
2529
2530         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2531         if (next_is_tuple(s)) {
2532                 dom = read_tuple(s, dom, isl_dim_param, v);
2533                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2534                         goto error;
2535         }
2536         if (isl_stream_eat(s, '{'))
2537                 goto error;
2538
2539         n = v->n;
2540         aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2541         pa = read_pw_aff_with_dom(s, aff_dom, v);
2542         vars_drop(v, v->n - n);
2543
2544         while (isl_stream_eat_if_available(s, ';')) {
2545                 isl_pw_aff *pa_i;
2546
2547                 n = v->n;
2548                 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2549                 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
2550                 vars_drop(v, v->n - n);
2551
2552                 pa = isl_pw_aff_union_add(pa, pa_i);
2553         }
2554
2555         if (isl_stream_eat(s, '}'))
2556                 goto error;
2557
2558         vars_free(v);
2559         isl_set_free(dom);
2560         return pa;
2561 error:
2562         vars_free(v);
2563         isl_set_free(dom);
2564         isl_pw_aff_free(pa);
2565         return NULL;
2566 }
2567
2568 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
2569 {
2570         isl_aff *aff;
2571         struct isl_stream *s = isl_stream_new_str(ctx, str);
2572         if (!s)
2573                 return NULL;
2574         aff = isl_stream_read_aff(s);
2575         isl_stream_free(s);
2576         return aff;
2577 }
2578
2579 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
2580 {
2581         isl_pw_aff *pa;
2582         struct isl_stream *s = isl_stream_new_str(ctx, str);
2583         if (!s)
2584                 return NULL;
2585         pa = isl_stream_read_pw_aff(s);
2586         isl_stream_free(s);
2587         return pa;
2588 }
2589
2590 /* Read an isl_pw_multi_aff from "s".
2591  * We currently read a generic object and if it turns out to be a set or
2592  * a map, we convert that to an isl_pw_multi_aff.
2593  * It would be more efficient if we were to construct the isl_pw_multi_aff
2594  * directly.
2595  */
2596 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
2597 {
2598         struct isl_obj obj;
2599
2600         obj = obj_read(s);
2601         if (!obj.v)
2602                 return NULL;
2603
2604         if (obj.type == isl_obj_map)
2605                 return isl_pw_multi_aff_from_map(obj.v);
2606         if (obj.type == isl_obj_set)
2607                 return isl_pw_multi_aff_from_set(obj.v);
2608
2609         obj.type->free(obj.v);
2610         isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2611                 return NULL);
2612 }
2613
2614 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
2615         const char *str)
2616 {
2617         isl_pw_multi_aff *pma;
2618         struct isl_stream *s = isl_stream_new_str(ctx, str);
2619         if (!s)
2620                 return NULL;
2621         pma = isl_stream_read_pw_multi_aff(s);
2622         isl_stream_free(s);
2623         return pma;
2624 }
2625
2626 /* Read a multi-affine expression from "s".
2627  * We call isl_stream_read_pw_multi_aff to parse a possibly piecewise
2628  * multi-affine expression and then check that the result is
2629  * a single multi-affine expression on a universe domain.
2630  */
2631 __isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s)
2632 {
2633         isl_pw_multi_aff *pma;
2634         isl_multi_aff *maff;
2635
2636         pma = isl_stream_read_pw_multi_aff(s);
2637         if (!pma)
2638                 return NULL;
2639         if (pma->n != 1)
2640                 isl_die(s->ctx, isl_error_invalid,
2641                         "expecting single list of affine expressions",
2642                         return isl_pw_multi_aff_free(pma));
2643         if (!isl_set_plain_is_universe(pma->p[0].set))
2644                 isl_die(s->ctx, isl_error_invalid, "expecting universe domain",
2645                         return isl_pw_multi_aff_free(pma));
2646         maff = isl_multi_aff_copy(pma->p[0].maff);
2647         isl_pw_multi_aff_free(pma);
2648         return maff;
2649 }
2650
2651 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
2652         const char *str)
2653 {
2654         isl_multi_aff *maff;
2655         struct isl_stream *s = isl_stream_new_str(ctx, str);
2656         if (!s)
2657                 return NULL;
2658         maff = isl_stream_read_multi_aff(s);
2659         isl_stream_free(s);
2660         return maff;
2661 }
2662
2663 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
2664         struct isl_stream *s)
2665 {
2666         struct isl_obj obj;
2667
2668         obj = obj_read(s);
2669         if (obj.type == isl_obj_pw_qpolynomial) {
2670                 obj.type = isl_obj_union_pw_qpolynomial;
2671                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2672         }
2673         if (obj.v)
2674                 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
2675                            goto error);
2676
2677         return obj.v;
2678 error:
2679         obj.type->free(obj.v);
2680         return NULL;
2681 }
2682
2683 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
2684         isl_ctx *ctx, const char *str)
2685 {
2686         isl_union_pw_qpolynomial *upwqp;
2687         struct isl_stream *s = isl_stream_new_str(ctx, str);
2688         if (!s)
2689                 return NULL;
2690         upwqp = isl_stream_read_union_pw_qpolynomial(s);
2691         isl_stream_free(s);
2692         return upwqp;
2693 }