isl_input.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  * Copyright 2010      INRIA Saclay
   4  * Copyright 2012      Ecole Normale Superieure
   5  *
   6  * Use of this software is governed by the MIT license
   7  *
   8  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   9  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
  10  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  11  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
  12  * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  13  */
  14
  15 #include <ctype.h>
  16 #include <stdio.h>
  17 #include <string.h>
  18 #include <isl_ctx_private.h>
  19 #include <isl_map_private.h>
  20 #include <isl/set.h>
  21 #include <isl/seq.h>
  22 #include <isl_stream_private.h>
  23 #include <isl/obj.h>
  24 #include "isl_polynomial_private.h"
  25 #include <isl/union_map.h>
  26 #include <isl_mat_private.h>
  27 #include <isl_aff_private.h>
  28 #include <isl/list.h>
  29 #include <isl_val_private.h>
  30
  31 struct variable {
  32         char                    *name;
  33         int                      pos;
  34         struct variable         *next;
  35 };
  36
  37 struct vars {
  38         struct isl_ctx  *ctx;
  39         int              n;
  40         struct variable *v;
  41 };
  42
  43 static struct vars *vars_new(struct isl_ctx *ctx)
  44 {
  45         struct vars *v;
  46         v = isl_alloc_type(ctx, struct vars);
  47         if (!v)
  48                 return NULL;
  49         v->ctx = ctx;
  50         v->n = 0;
  51         v->v = NULL;
  52         return v;
  53 }
  54
  55 static void variable_free(struct variable *var)
  56 {
  57         while (var) {
  58                 struct variable *next = var->next;
  59                 free(var->name);
  60                 free(var);
  61                 var = next;
  62         }
  63 }
  64
  65 static void vars_free(struct vars *v)
  66 {
  67         if (!v)
  68                 return;
  69         variable_free(v->v);
  70         free(v);
  71 }
  72
  73 static void vars_drop(struct vars *v, int n)
  74 {
  75         struct variable *var;
  76
  77         if (!v || !v->v)
  78                 return;
  79
  80         v->n -= n;
  81
  82         var = v->v;
  83         while (--n >= 0) {
  84                 struct variable *next = var->next;
  85                 free(var->name);
  86                 free(var);
  87                 var = next;
  88         }
  89         v->v = var;
  90 }
  91
  92 static struct variable *variable_new(struct vars *v, const char *name, int len,
  93                                 int pos)
  94 {
  95         struct variable *var;
  96         var = isl_calloc_type(v->ctx, struct variable);
  97         if (!var)
  98                 goto error;
  99         var->name = strdup(name);
 100         var->name[len] = '\0';
 101         var->pos = pos;
 102         var->next = v->v;
 103         return var;
 104 error:
 105         variable_free(v->v);
 106         return NULL;
 107 }
 108
 109 static int vars_pos(struct vars *v, const char *s, int len)
 110 {
 111         int pos;
 112         struct variable *q;
 113
 114         if (len == -1)
 115                 len = strlen(s);
 116         for (q = v->v; q; q = q->next) {
 117                 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
 118                         break;
 119         }
 120         if (q)
 121                 pos = q->pos;
 122         else {
 123                 pos = v->n;
 124                 v->v = variable_new(v, s, len, v->n);
 125                 if (!v->v)
 126                         return -1;
 127                 v->n++;
 128         }
 129         return pos;
 130 }
 131
 132 static int vars_add_anon(struct vars *v)
 133 {
 134         v->v = variable_new(v, "", 0, v->n);
 135
 136         if (!v->v)
 137                 return -1;
 138         v->n++;
 139
 140         return 0;
 141 }
 142
 143 /* Obtain next token, with some preprocessing.
 144  * In particular, evaluate expressions of the form x^y,
 145  * with x and y values.
 146  */
 147 static struct isl_token *next_token(struct isl_stream *s)
 148 {
 149         struct isl_token *tok, *tok2;
 150
 151         tok = isl_stream_next_token(s);
 152         if (!tok || tok->type != ISL_TOKEN_VALUE)
 153                 return tok;
 154         if (!isl_stream_eat_if_available(s, '^'))
 155                 return tok;
 156         tok2 = isl_stream_next_token(s);
 157         if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
 158                 isl_stream_error(s, tok2, "expecting constant value");
 159                 goto error;
 160         }
 161
 162         isl_int_pow_ui(tok->u.v, tok->u.v, isl_int_get_ui(tok2->u.v));
 163
 164         isl_token_free(tok2);
 165         return tok;
 166 error:
 167         isl_token_free(tok);
 168         isl_token_free(tok2);
 169         return NULL;
 170 }
 171
 172 /* Read an isl_val from "s".
 173  *
 174  * The following token sequences are recognized
 175  *
 176  *      "infty"         ->      infty
 177  *      "-" "infty"     ->      -infty
 178  *      "NaN"           ->      NaN
 179  *      n "/" d         ->      n/d
 180  *      v               ->      v
 181  *
 182  * where n, d and v are integer constants.
 183  */
 184 __isl_give isl_val *isl_stream_read_val(struct isl_stream *s)
 185 {
 186         struct isl_token *tok = NULL;
 187         struct isl_token *tok2 = NULL;
 188         isl_val *val;
 189
 190         tok = next_token(s);
 191         if (!tok) {
 192                 isl_stream_error(s, NULL, "unexpected EOF");
 193                 goto error;
 194         }
 195         if (tok->type == ISL_TOKEN_INFTY) {
 196                 isl_token_free(tok);
 197                 return isl_val_infty(s->ctx);
 198         }
 199         if (tok->type == '-' &&
 200             isl_stream_eat_if_available(s, ISL_TOKEN_INFTY)) {
 201                 isl_token_free(tok);
 202                 return isl_val_neginfty(s->ctx);
 203         }
 204         if (tok->type == ISL_TOKEN_NAN) {
 205                 isl_token_free(tok);
 206                 return isl_val_nan(s->ctx);
 207         }
 208         if (tok->type != ISL_TOKEN_VALUE) {
 209                 isl_stream_error(s, tok, "expecting value");
 210                 goto error;
 211         }
 212
 213         if (isl_stream_eat_if_available(s, '/')) {
 214                 tok2 = next_token(s);
 215                 if (!tok2) {
 216                         isl_stream_error(s, NULL, "unexpected EOF");
 217                         goto error;
 218                 }
 219                 if (tok2->type != ISL_TOKEN_VALUE) {
 220                         isl_stream_error(s, tok2, "expecting value");
 221                         goto error;
 222                 }
 223                 val = isl_val_rat_from_isl_int(s->ctx, tok->u.v, tok2->u.v);
 224                 val = isl_val_normalize(val);
 225         } else {
 226                 val = isl_val_int_from_isl_int(s->ctx, tok->u.v);
 227         }
 228
 229         isl_token_free(tok);
 230         isl_token_free(tok2);
 231         return val;
 232 error:
 233         isl_token_free(tok);
 234         isl_token_free(tok2);
 235         return NULL;
 236 }
 237
 238 /* Read an isl_val from "str".
 239  */
 240 struct isl_val *isl_val_read_from_str(struct isl_ctx *ctx,
 241         const char *str)
 242 {
 243         isl_val *val;
 244         struct isl_stream *s = isl_stream_new_str(ctx, str);
 245         if (!s)
 246                 return NULL;
 247         val = isl_stream_read_val(s);
 248         isl_stream_free(s);
 249         return val;
 250 }
 251
 252 static int accept_cst_factor(struct isl_stream *s, isl_int *f)
 253 {
 254         struct isl_token *tok;
 255
 256         tok = next_token(s);
 257         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 258                 isl_stream_error(s, tok, "expecting constant value");
 259                 goto error;
 260         }
 261
 262         isl_int_mul(*f, *f, tok->u.v);
 263
 264         isl_token_free(tok);
 265
 266         if (isl_stream_eat_if_available(s, '*'))
 267                 return accept_cst_factor(s, f);
 268
 269         return 0;
 270 error:
 271         isl_token_free(tok);
 272         return -1;
 273 }
 274
 275 /* Given an affine expression aff, return an affine expression
 276  * for aff % d, with d the next token on the stream, which is
 277  * assumed to be a constant.
 278  *
 279  * We introduce an integer division q = [aff/d] and the result
 280  * is set to aff - d q.
 281  */
 282 static __isl_give isl_pw_aff *affine_mod(struct isl_stream *s,
 283         struct vars *v, __isl_take isl_pw_aff *aff)
 284 {
 285         struct isl_token *tok;
 286         isl_pw_aff *q;
 287
 288         tok = next_token(s);
 289         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 290                 isl_stream_error(s, tok, "expecting constant value");
 291                 goto error;
 292         }
 293
 294         q = isl_pw_aff_copy(aff);
 295         q = isl_pw_aff_scale_down(q, tok->u.v);
 296         q = isl_pw_aff_floor(q);
 297         q = isl_pw_aff_scale(q, tok->u.v);
 298
 299         aff = isl_pw_aff_sub(aff, q);
 300
 301         isl_token_free(tok);
 302         return aff;
 303 error:
 304         isl_pw_aff_free(aff);
 305         isl_token_free(tok);
 306         return NULL;
 307 }
 308
 309 static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s,
 310         __isl_take isl_space *dim, struct vars *v);
 311 static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s,
 312         __isl_take isl_space *dim, struct vars *v);
 313
 314 static __isl_give isl_pw_aff *accept_minmax(struct isl_stream *s,
 315         __isl_take isl_space *dim, struct vars *v)
 316 {
 317         struct isl_token *tok;
 318         isl_pw_aff_list *list = NULL;
 319         int min;
 320
 321         tok = isl_stream_next_token(s);
 322         if (!tok)
 323                 goto error;
 324         min = tok->type == ISL_TOKEN_MIN;
 325         isl_token_free(tok);
 326
 327         if (isl_stream_eat(s, '('))
 328                 goto error;
 329
 330         list = accept_affine_list(s, isl_space_copy(dim), v);
 331         if (!list)
 332                 goto error;
 333
 334         if (isl_stream_eat(s, ')'))
 335                 goto error;
 336
 337         isl_space_free(dim);
 338         return min ? isl_pw_aff_list_min(list) : isl_pw_aff_list_max(list);
 339 error:
 340         isl_space_free(dim);
 341         isl_pw_aff_list_free(list);
 342         return NULL;
 343 }
 344
 345 /* Is "tok" the start of an integer division?
 346  */
 347 static int is_start_of_div(struct isl_token *tok)
 348 {
 349         if (!tok)
 350                 return 0;
 351         if (tok->type == '[')
 352                 return 1;
 353         if (tok->type == ISL_TOKEN_FLOOR)
 354                 return 1;
 355         if (tok->type == ISL_TOKEN_CEIL)
 356                 return 1;
 357         if (tok->type == ISL_TOKEN_FLOORD)
 358                 return 1;
 359         if (tok->type == ISL_TOKEN_CEILD)
 360                 return 1;
 361         return 0;
 362 }
 363
 364 /* Read an integer division from "s" and return it as an isl_pw_aff.
 365  *
 366  * The integer division can be of the form
 367  *
 368  *      [<affine expression>]
 369  *      floor(<affine expression>)
 370  *      ceil(<affine expression>)
 371  *      floord(<affine expression>,<denominator>)
 372  *      ceild(<affine expression>,<denominator>)
 373  */
 374 static __isl_give isl_pw_aff *accept_div(struct isl_stream *s,
 375         __isl_take isl_space *dim, struct vars *v)
 376 {
 377         struct isl_token *tok;
 378         int f = 0;
 379         int c = 0;
 380         int extra = 0;
 381         isl_pw_aff *pwaff = NULL;
 382
 383         if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD))
 384                 extra = f = 1;
 385         else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEILD))
 386                 extra = c = 1;
 387         else if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOOR))
 388                 f = 1;
 389         else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEIL))
 390                 c = 1;
 391         if (f || c) {
 392                 if (isl_stream_eat(s, '('))
 393                         goto error;
 394         } else {
 395                 if (isl_stream_eat(s, '['))
 396                         goto error;
 397         }
 398
 399         pwaff = accept_affine(s, isl_space_copy(dim), v);
 400
 401         if (extra) {
 402                 if (isl_stream_eat(s, ','))
 403                         goto error;
 404
 405                 tok = next_token(s);
 406                 if (!tok)
 407                         goto error;
 408                 if (tok->type != ISL_TOKEN_VALUE) {
 409                         isl_stream_error(s, tok, "expected denominator");
 410                         isl_stream_push_token(s, tok);
 411                         goto error;
 412                 }
 413                 isl_pw_aff_scale_down(pwaff,  tok->u.v);
 414                 isl_token_free(tok);
 415         }
 416
 417         if (c)
 418                 pwaff = isl_pw_aff_ceil(pwaff);
 419         else
 420                 pwaff = isl_pw_aff_floor(pwaff);
 421
 422         if (f || c) {
 423                 if (isl_stream_eat(s, ')'))
 424                         goto error;
 425         } else {
 426                 if (isl_stream_eat(s, ']'))
 427                         goto error;
 428         }
 429
 430         isl_space_free(dim);
 431         return pwaff;
 432 error:
 433         isl_space_free(dim);
 434         isl_pw_aff_free(pwaff);
 435         return NULL;
 436 }
 437
 438 static __isl_give isl_pw_aff *accept_affine_factor(struct isl_stream *s,
 439         __isl_take isl_space *dim, struct vars *v)
 440 {
 441         struct isl_token *tok = NULL;
 442         isl_pw_aff *res = NULL;
 443
 444         tok = next_token(s);
 445         if (!tok) {
 446                 isl_stream_error(s, NULL, "unexpected EOF");
 447                 goto error;
 448         }
 449
 450         if (tok->type == ISL_TOKEN_AFF) {
 451                 res = isl_pw_aff_copy(tok->u.pwaff);
 452                 isl_token_free(tok);
 453         } else if (tok->type == ISL_TOKEN_IDENT) {
 454                 int n = v->n;
 455                 int pos = vars_pos(v, tok->u.s, -1);
 456                 isl_aff *aff;
 457
 458                 if (pos < 0)
 459                         goto error;
 460                 if (pos >= n) {
 461                         vars_drop(v, v->n - n);
 462                         isl_stream_error(s, tok, "unknown identifier");
 463                         goto error;
 464                 }
 465
 466                 aff = isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(dim)));
 467                 if (!aff)
 468                         goto error;
 469                 isl_int_set_si(aff->v->el[2 + pos], 1);
 470                 res = isl_pw_aff_from_aff(aff);
 471                 isl_token_free(tok);
 472         } else if (tok->type == ISL_TOKEN_VALUE) {
 473                 if (isl_stream_eat_if_available(s, '*')) {
 474                         res = accept_affine_factor(s, isl_space_copy(dim), v);
 475                         res = isl_pw_aff_scale(res, tok->u.v);
 476                 } else {
 477                         isl_local_space *ls;
 478                         isl_aff *aff;
 479                         ls = isl_local_space_from_space(isl_space_copy(dim));
 480                         aff = isl_aff_zero_on_domain(ls);
 481                         aff = isl_aff_add_constant(aff, tok->u.v);
 482                         res = isl_pw_aff_from_aff(aff);
 483                 }
 484                 isl_token_free(tok);
 485         } else if (tok->type == '(') {
 486                 isl_token_free(tok);
 487                 tok = NULL;
 488                 res = accept_affine(s, isl_space_copy(dim), v);
 489                 if (!res)
 490                         goto error;
 491                 if (isl_stream_eat(s, ')'))
 492                         goto error;
 493         } else if (is_start_of_div(tok)) {
 494                 isl_stream_push_token(s, tok);
 495                 tok = NULL;
 496                 res = accept_div(s, isl_space_copy(dim), v);
 497         } else if (tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX) {
 498                 isl_stream_push_token(s, tok);
 499                 tok = NULL;
 500                 res = accept_minmax(s, isl_space_copy(dim), v);
 501         } else {
 502                 isl_stream_error(s, tok, "expecting factor");
 503                 goto error;
 504         }
 505         if (isl_stream_eat_if_available(s, '%') ||
 506             isl_stream_eat_if_available(s, ISL_TOKEN_MOD)) {
 507                 isl_space_free(dim);
 508                 return affine_mod(s, v, res);
 509         }
 510         if (isl_stream_eat_if_available(s, '*')) {
 511                 isl_int f;
 512                 isl_int_init(f);
 513                 isl_int_set_si(f, 1);
 514                 if (accept_cst_factor(s, &f) < 0) {
 515                         isl_int_clear(f);
 516                         goto error2;
 517                 }
 518                 res = isl_pw_aff_scale(res, f);
 519                 isl_int_clear(f);
 520         }
 521         if (isl_stream_eat_if_available(s, '/')) {
 522                 isl_int f;
 523                 isl_int_init(f);
 524                 isl_int_set_si(f, 1);
 525                 if (accept_cst_factor(s, &f) < 0) {
 526                         isl_int_clear(f);
 527                         goto error2;
 528                 }
 529                 res = isl_pw_aff_scale_down(res, f);
 530                 isl_int_clear(f);
 531         }
 532
 533         isl_space_free(dim);
 534         return res;
 535 error:
 536         isl_token_free(tok);
 537 error2:
 538         isl_pw_aff_free(res);
 539         isl_space_free(dim);
 540         return NULL;
 541 }
 542
 543 static __isl_give isl_pw_aff *add_cst(__isl_take isl_pw_aff *pwaff, isl_int v)
 544 {
 545         isl_aff *aff;
 546         isl_space *space;
 547
 548         space = isl_pw_aff_get_domain_space(pwaff);
 549         aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
 550         aff = isl_aff_add_constant(aff, v);
 551
 552         return isl_pw_aff_add(pwaff, isl_pw_aff_from_aff(aff));
 553 }
 554
 555 static __isl_give isl_pw_aff *accept_affine(struct isl_stream *s,
 556         __isl_take isl_space *dim, struct vars *v)
 557 {
 558         struct isl_token *tok = NULL;
 559         isl_local_space *ls;
 560         isl_pw_aff *res;
 561         int sign = 1;
 562
 563         ls = isl_local_space_from_space(isl_space_copy(dim));
 564         res = isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls));
 565         if (!res)
 566                 goto error;
 567
 568         for (;;) {
 569                 tok = next_token(s);
 570                 if (!tok) {
 571                         isl_stream_error(s, NULL, "unexpected EOF");
 572                         goto error;
 573                 }
 574                 if (tok->type == '-') {
 575                         sign = -sign;
 576                         isl_token_free(tok);
 577                         continue;
 578                 }
 579                 if (tok->type == '(' || is_start_of_div(tok) ||
 580                     tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX ||
 581                     tok->type == ISL_TOKEN_IDENT ||
 582                     tok->type == ISL_TOKEN_AFF) {
 583                         isl_pw_aff *term;
 584                         isl_stream_push_token(s, tok);
 585                         tok = NULL;
 586                         term = accept_affine_factor(s, isl_space_copy(dim), v);
 587                         if (sign < 0)
 588                                 res = isl_pw_aff_sub(res, term);
 589                         else
 590                                 res = isl_pw_aff_add(res, term);
 591                         if (!res)
 592                                 goto error;
 593                         sign = 1;
 594                 } else if (tok->type == ISL_TOKEN_VALUE) {
 595                         if (sign < 0)
 596                                 isl_int_neg(tok->u.v, tok->u.v);
 597                         if (isl_stream_eat_if_available(s, '*') ||
 598                             isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
 599                                 isl_pw_aff *term;
 600                                 term = accept_affine_factor(s,
 601                                                         isl_space_copy(dim), v);
 602                                 term = isl_pw_aff_scale(term, tok->u.v);
 603                                 res = isl_pw_aff_add(res, term);
 604                                 if (!res)
 605                                         goto error;
 606                         } else {
 607                                 res = add_cst(res, tok->u.v);
 608                         }
 609                         sign = 1;
 610                 } else {
 611                         isl_stream_error(s, tok, "unexpected isl_token");
 612                         isl_stream_push_token(s, tok);
 613                         isl_pw_aff_free(res);
 614                         isl_space_free(dim);
 615                         return NULL;
 616                 }
 617                 isl_token_free(tok);
 618
 619                 tok = next_token(s);
 620                 if (tok && tok->type == '-') {
 621                         sign = -sign;
 622                         isl_token_free(tok);
 623                 } else if (tok && tok->type == '+') {
 624                         /* nothing */
 625                         isl_token_free(tok);
 626                 } else if (tok && tok->type == ISL_TOKEN_VALUE &&
 627                            isl_int_is_neg(tok->u.v)) {
 628                         isl_stream_push_token(s, tok);
 629                 } else {
 630                         if (tok)
 631                                 isl_stream_push_token(s, tok);
 632                         break;
 633                 }
 634         }
 635
 636         isl_space_free(dim);
 637         return res;
 638 error:
 639         isl_space_free(dim);
 640         isl_token_free(tok);
 641         isl_pw_aff_free(res);
 642         return NULL;
 643 }
 644
 645 static int is_comparator(struct isl_token *tok)
 646 {
 647         if (!tok)
 648                 return 0;
 649
 650         switch (tok->type) {
 651         case ISL_TOKEN_LT:
 652         case ISL_TOKEN_GT:
 653         case ISL_TOKEN_LE:
 654         case ISL_TOKEN_GE:
 655         case ISL_TOKEN_NE:
 656         case '=':
 657                 return 1;
 658         default:
 659                 return 0;
 660         }
 661 }
 662
 663 static __isl_give isl_map *read_formula(struct isl_stream *s,
 664         struct vars *v, __isl_take isl_map *map, int rational);
 665 static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s,
 666         __isl_take isl_space *dim, struct vars *v, int rational);
 667
 668 /* Accept a ternary operator, given the first argument.
 669  */
 670 static __isl_give isl_pw_aff *accept_ternary(struct isl_stream *s,
 671         __isl_take isl_map *cond, struct vars *v, int rational)
 672 {
 673         isl_space *dim;
 674         isl_pw_aff *pwaff1 = NULL, *pwaff2 = NULL, *pa_cond;
 675
 676         if (!cond)
 677                 return NULL;
 678
 679         if (isl_stream_eat(s, '?'))
 680                 goto error;
 681
 682         dim = isl_space_wrap(isl_map_get_space(cond));
 683         pwaff1 = accept_extended_affine(s, dim, v, rational);
 684         if (!pwaff1)
 685                 goto error;
 686
 687         if (isl_stream_eat(s, ':'))
 688                 goto error;
 689
 690         dim = isl_pw_aff_get_domain_space(pwaff1);
 691         pwaff2 = accept_extended_affine(s, dim, v, rational);
 692         if (!pwaff1)
 693                 goto error;
 694
 695         pa_cond = isl_set_indicator_function(isl_map_wrap(cond));
 696         return isl_pw_aff_cond(pa_cond, pwaff1, pwaff2);
 697 error:
 698         isl_map_free(cond);
 699         isl_pw_aff_free(pwaff1);
 700         isl_pw_aff_free(pwaff2);
 701         return NULL;
 702 }
 703
 704 /* Accept an affine expression that may involve ternary operators.
 705  * We first read an affine expression.
 706  * If it is not followed by a comparison operator, we simply return it.
 707  * Otherwise, we assume the affine epxression is part of the first
 708  * argument of a ternary operator and try to parse that.
 709  */
 710 static __isl_give isl_pw_aff *accept_extended_affine(struct isl_stream *s,
 711         __isl_take isl_space *dim, struct vars *v, int rational)
 712 {
 713         isl_space *space;
 714         isl_map *cond;
 715         isl_pw_aff *pwaff;
 716         struct isl_token *tok;
 717         int line = -1, col = -1;
 718         int is_comp;
 719
 720         tok = isl_stream_next_token(s);
 721         if (tok) {
 722                 line = tok->line;
 723                 col = tok->col;
 724                 isl_stream_push_token(s, tok);
 725         }
 726
 727         pwaff = accept_affine(s, dim, v);
 728         if (rational)
 729                 pwaff = isl_pw_aff_set_rational(pwaff);
 730         if (!pwaff)
 731                 return NULL;
 732
 733         tok = isl_stream_next_token(s);
 734         if (!tok)
 735                 return isl_pw_aff_free(pwaff);
 736
 737         is_comp = is_comparator(tok);
 738         isl_stream_push_token(s, tok);
 739         if (!is_comp)
 740                 return pwaff;
 741
 742         tok = isl_token_new(s->ctx, line, col, 0);
 743         if (!tok)
 744                 return isl_pw_aff_free(pwaff);
 745         tok->type = ISL_TOKEN_AFF;
 746         tok->u.pwaff = pwaff;
 747
 748         space = isl_pw_aff_get_domain_space(pwaff);
 749         cond = isl_map_universe(isl_space_unwrap(space));
 750
 751         isl_stream_push_token(s, tok);
 752
 753         cond = read_formula(s, v, cond, rational);
 754
 755         return accept_ternary(s, cond, v, rational);
 756 }
 757
 758 static __isl_give isl_map *read_var_def(struct isl_stream *s,
 759         __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
 760         int rational)
 761 {
 762         isl_pw_aff *def;
 763         int pos;
 764         isl_map *def_map;
 765
 766         if (type == isl_dim_param)
 767                 pos = isl_map_dim(map, isl_dim_param);
 768         else {
 769                 pos = isl_map_dim(map, isl_dim_in);
 770                 if (type == isl_dim_out)
 771                         pos += isl_map_dim(map, isl_dim_out);
 772                 type = isl_dim_in;
 773         }
 774         --pos;
 775
 776         def = accept_extended_affine(s, isl_space_wrap(isl_map_get_space(map)),
 777                                         v, rational);
 778         def_map = isl_map_from_pw_aff(def);
 779         def_map = isl_map_equate(def_map, type, pos, isl_dim_out, 0);
 780         def_map = isl_set_unwrap(isl_map_domain(def_map));
 781
 782         map = isl_map_intersect(map, def_map);
 783
 784         return map;
 785 }
 786
 787 static __isl_give isl_pw_aff_list *accept_affine_list(struct isl_stream *s,
 788         __isl_take isl_space *dim, struct vars *v)
 789 {
 790         isl_pw_aff *pwaff;
 791         isl_pw_aff_list *list;
 792         struct isl_token *tok = NULL;
 793
 794         pwaff = accept_affine(s, isl_space_copy(dim), v);
 795         list = isl_pw_aff_list_from_pw_aff(pwaff);
 796         if (!list)
 797                 goto error;
 798
 799         for (;;) {
 800                 tok = isl_stream_next_token(s);
 801                 if (!tok) {
 802                         isl_stream_error(s, NULL, "unexpected EOF");
 803                         goto error;
 804                 }
 805                 if (tok->type != ',') {
 806                         isl_stream_push_token(s, tok);
 807                         break;
 808                 }
 809                 isl_token_free(tok);
 810
 811                 pwaff = accept_affine(s, isl_space_copy(dim), v);
 812                 list = isl_pw_aff_list_concat(list,
 813                                 isl_pw_aff_list_from_pw_aff(pwaff));
 814                 if (!list)
 815                         goto error;
 816         }
 817
 818         isl_space_free(dim);
 819         return list;
 820 error:
 821         isl_space_free(dim);
 822         isl_pw_aff_list_free(list);
 823         return NULL;
 824 }
 825
 826 static __isl_give isl_map *read_defined_var_list(struct isl_stream *s,
 827         struct vars *v, __isl_take isl_map *map, int rational)
 828 {
 829         struct isl_token *tok;
 830
 831         while ((tok = isl_stream_next_token(s)) != NULL) {
 832                 int p;
 833                 int n = v->n;
 834
 835                 if (tok->type != ISL_TOKEN_IDENT)
 836                         break;
 837
 838                 p = vars_pos(v, tok->u.s, -1);
 839                 if (p < 0)
 840                         goto error;
 841                 if (p < n) {
 842                         isl_stream_error(s, tok, "expecting unique identifier");
 843                         goto error;
 844                 }
 845
 846                 map = isl_map_add_dims(map, isl_dim_out, 1);
 847
 848                 isl_token_free(tok);
 849                 tok = isl_stream_next_token(s);
 850                 if (tok && tok->type == '=') {
 851                         isl_token_free(tok);
 852                         map = read_var_def(s, map, isl_dim_out, v, rational);
 853                         tok = isl_stream_next_token(s);
 854                 }
 855
 856                 if (!tok || tok->type != ',')
 857                         break;
 858
 859                 isl_token_free(tok);
 860         }
 861         if (tok)
 862                 isl_stream_push_token(s, tok);
 863
 864         return map;
 865 error:
 866         isl_token_free(tok);
 867         isl_map_free(map);
 868         return NULL;
 869 }
 870
 871 static int next_is_tuple(struct isl_stream *s)
 872 {
 873         struct isl_token *tok;
 874         int is_tuple;
 875
 876         tok = isl_stream_next_token(s);
 877         if (!tok)
 878                 return 0;
 879         if (tok->type == '[') {
 880                 isl_stream_push_token(s, tok);
 881                 return 1;
 882         }
 883         if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) {
 884                 isl_stream_push_token(s, tok);
 885                 return 0;
 886         }
 887
 888         is_tuple = isl_stream_next_token_is(s, '[');
 889
 890         isl_stream_push_token(s, tok);
 891
 892         return is_tuple;
 893 }
 894
 895 /* Allocate an initial tuple with zero dimensions and an anonymous,
 896  * unstructured space.
 897  * A tuple is represented as an isl_multi_pw_aff.
 898  * The range space is the space of the tuple.
 899  * The domain space is an anonymous space
 900  * with a dimension for each variable in the set of variables in "v".
 901  * If a given dimension is not defined in terms of earlier dimensions in
 902  * the input, then the corresponding isl_pw_aff is set equal to one time
 903  * the variable corresponding to the dimension being defined.
 904  */
 905 static __isl_give isl_multi_pw_aff *tuple_alloc(struct vars *v)
 906 {
 907         return isl_multi_pw_aff_alloc(isl_space_alloc(v->ctx, 0, v->n, 0));
 908 }
 909
 910 /* Is "pa" an expression in term of earlier dimensions?
 911  * The alternative is that the dimension is defined to be equal to itself,
 912  * meaning that it has a universe domain and an expression that depends
 913  * on itself.  "i" is the position of the expression in a sequence
 914  * of "n" expressions.  The final dimensions of "pa" correspond to
 915  * these "n" expressions.
 916  */
 917 static int pw_aff_is_expr(__isl_keep isl_pw_aff *pa, int i, int n)
 918 {
 919         isl_aff *aff;
 920
 921         if (!pa)
 922                 return -1;
 923         if (pa->n != 1)
 924                 return 1;
 925         if (!isl_set_plain_is_universe(pa->p[0].set))
 926                 return 1;
 927
 928         aff = pa->p[0].aff;
 929         if (isl_int_is_zero(aff->v->el[aff->v->size - n + i]))
 930                 return 1;
 931         return 0;
 932 }
 933
 934 /* Does the tuple contain any dimensions that are defined
 935  * in terms of earlier dimensions?
 936  */
 937 static int tuple_has_expr(__isl_keep isl_multi_pw_aff *tuple)
 938 {
 939         int i, n;
 940         int has_expr = 0;
 941         isl_pw_aff *pa;
 942
 943         if (!tuple)
 944                 return -1;
 945         n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
 946         for (i = 0; i < n; ++i) {
 947                 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
 948                 has_expr = pw_aff_is_expr(pa, i, n);
 949                 isl_pw_aff_free(pa);
 950                 if (has_expr < 0 || has_expr)
 951                         break;
 952         }
 953
 954         return has_expr;
 955 }
 956
 957 /* Add a dimension to the given tuple.
 958  * The dimension is initially undefined, so it is encoded
 959  * as one times itself.
 960  */
 961 static __isl_give isl_multi_pw_aff *tuple_add_dim(
 962         __isl_take isl_multi_pw_aff *tuple, struct vars *v)
 963 {
 964         isl_space *space;
 965         isl_aff *aff;
 966         isl_pw_aff *pa;
 967
 968         tuple = isl_multi_pw_aff_add_dims(tuple, isl_dim_in, 1);
 969         space = isl_multi_pw_aff_get_domain_space(tuple);
 970         aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
 971         aff = isl_aff_add_coefficient_si(aff, isl_dim_in, v->n, 1);
 972         pa = isl_pw_aff_from_aff(aff);
 973         tuple = isl_multi_pw_aff_flat_range_product(tuple,
 974                                             isl_multi_pw_aff_from_pw_aff(pa));
 975
 976         return tuple;
 977 }
 978
 979 /* Set the name of dimension "pos" in "tuple" to "name".
 980  * During printing, we add primes if the same name appears more than once
 981  * to distinguish the occurrences.  Here, we remove those primes from "name"
 982  * before setting the name of the dimension.
 983  */
 984 static __isl_give isl_multi_pw_aff *tuple_set_dim_name(
 985         __isl_take isl_multi_pw_aff *tuple, int pos, char *name)
 986 {
 987         char *prime;
 988
 989         if (!name)
 990                 return tuple;
 991
 992         prime = strchr(name, '\'');
 993         if (prime)
 994                 *prime = '\0';
 995         tuple = isl_multi_pw_aff_set_dim_name(tuple, isl_dim_set, pos, name);
 996         if (prime)
 997                 *prime = '\'';
 998
 999         return tuple;
1000 }
1001
1002 /* Read an affine expression from "s" and replace the definition
1003  * of dimension "pos" in "tuple" by this expression.
1004  *
1005  * accept_extended_affine requires a wrapped space as input.
1006  * The domain space of "tuple", on the other hand is an anonymous space,
1007  * so we have to adjust the space of the isl_pw_aff before adding it
1008  * to "tuple".
1009  */
1010 static __isl_give isl_multi_pw_aff *read_tuple_var_def(struct isl_stream *s,
1011         __isl_take isl_multi_pw_aff *tuple, int pos, struct vars *v,
1012         int rational)
1013 {
1014         isl_space *space;
1015         isl_pw_aff *def;
1016
1017         space = isl_space_wrap(isl_space_alloc(s->ctx, 0, v->n, 0));
1018         def = accept_extended_affine(s, space, v, rational);
1019         space = isl_space_set_alloc(s->ctx, 0, v->n);
1020         def = isl_pw_aff_reset_domain_space(def, space);
1021         tuple = isl_multi_pw_aff_set_pw_aff(tuple, pos, def);
1022
1023         return tuple;
1024 }
1025
1026 /* Read a list of variables and/or affine expressions and return the list
1027  * as an isl_multi_pw_aff.
1028  * The elements in the list are separated by either "," or "][".
1029  * If "comma" is set then only "," is allowed.
1030  */
1031 static __isl_give isl_multi_pw_aff *read_tuple_var_list(struct isl_stream *s,
1032         struct vars *v, int rational, int comma)
1033 {
1034         int i = 0;
1035         struct isl_token *tok;
1036         isl_multi_pw_aff *res;
1037
1038         res = tuple_alloc(v);
1039
1040         if (isl_stream_next_token_is(s, ']'))
1041                 return res;
1042
1043         while ((tok = next_token(s)) != NULL) {
1044                 int new_name = 0;
1045
1046                 res = tuple_add_dim(res, v);
1047
1048                 if (tok->type == ISL_TOKEN_IDENT) {
1049                         int n = v->n;
1050                         int p = vars_pos(v, tok->u.s, -1);
1051                         if (p < 0)
1052                                 goto error;
1053                         new_name = p >= n;
1054                 }
1055
1056                 if (tok->type == '*') {
1057                         if (vars_add_anon(v) < 0)
1058                                 goto error;
1059                         isl_token_free(tok);
1060                 } else if (new_name) {
1061                         res = tuple_set_dim_name(res, i, v->v->name);
1062                         isl_token_free(tok);
1063                         if (isl_stream_eat_if_available(s, '='))
1064                                 res = read_tuple_var_def(s, res, i, v,
1065                                                         rational);
1066                 } else {
1067                         isl_stream_push_token(s, tok);
1068                         tok = NULL;
1069                         if (vars_add_anon(v) < 0)
1070                                 goto error;
1071                         res = read_tuple_var_def(s, res, i, v, rational);
1072                 }
1073
1074                 tok = isl_stream_next_token(s);
1075                 if (!comma && tok && tok->type == ']' &&
1076                     isl_stream_next_token_is(s, '[')) {
1077                         isl_token_free(tok);
1078                         tok = isl_stream_next_token(s);
1079                 } else if (!tok || tok->type != ',')
1080                         break;
1081
1082                 isl_token_free(tok);
1083                 i++;
1084         }
1085         if (tok)
1086                 isl_stream_push_token(s, tok);
1087
1088         return res;
1089 error:
1090         isl_token_free(tok);
1091         return isl_multi_pw_aff_free(res);
1092 }
1093
1094 /* Read a tuple and represent it as an isl_multi_pw_aff.  See tuple_alloc.
1095  */
1096 static __isl_give isl_multi_pw_aff *read_tuple(struct isl_stream *s,
1097         struct vars *v, int rational, int comma)
1098 {
1099         struct isl_token *tok;
1100         char *name = NULL;
1101         isl_multi_pw_aff *res = NULL;
1102
1103         tok = isl_stream_next_token(s);
1104         if (!tok)
1105                 goto error;
1106         if (tok->type == ISL_TOKEN_IDENT || tok->is_keyword) {
1107                 name = strdup(tok->u.s);
1108                 isl_token_free(tok);
1109                 if (!name)
1110                         goto error;
1111         } else
1112                 isl_stream_push_token(s, tok);
1113         if (isl_stream_eat(s, '['))
1114                 goto error;
1115         if (next_is_tuple(s)) {
1116                 isl_multi_pw_aff *out;
1117                 int n;
1118                 res = read_tuple(s, v, rational, comma);
1119                 if (isl_stream_eat(s, ISL_TOKEN_TO))
1120                         goto error;
1121                 out = read_tuple(s, v, rational, comma);
1122                 n = isl_multi_pw_aff_dim(out, isl_dim_out);
1123                 res = isl_multi_pw_aff_add_dims(res, isl_dim_in, n);
1124                 res = isl_multi_pw_aff_range_product(res, out);
1125         } else
1126                 res = read_tuple_var_list(s, v, rational, comma);
1127         if (isl_stream_eat(s, ']'))
1128                 goto error;
1129
1130         if (name) {
1131                 res = isl_multi_pw_aff_set_tuple_name(res, isl_dim_out, name);
1132                 free(name);
1133         }
1134
1135         return res;
1136 error:
1137         free(name);
1138         return isl_multi_pw_aff_free(res);
1139 }
1140
1141 /* Read a tuple from "s" and add it to "map".
1142  * The tuple is initially represented as an isl_multi_pw_aff.
1143  * We first create the appropriate space in "map" based on the range
1144  * space of this isl_multi_pw_aff.  Then, we add equalities based
1145  * on the affine expressions.  These live in an anonymous space,
1146  * however, so we first need to reset the space to that of "map".
1147  */
1148 static __isl_give isl_map *read_map_tuple(struct isl_stream *s,
1149         __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1150         int rational, int comma)
1151 {
1152         int i, n;
1153         isl_multi_pw_aff *tuple;
1154         isl_space *space = NULL;
1155
1156         tuple = read_tuple(s, v, rational, comma);
1157         if (!tuple)
1158                 goto error;
1159
1160         n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
1161         space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
1162         if (!space)
1163                 goto error;
1164
1165         if (type == isl_dim_param) {
1166                 if (isl_space_has_tuple_name(space, isl_dim_set) ||
1167                     isl_space_is_wrapping(space)) {
1168                         isl_die(s->ctx, isl_error_invalid,
1169                                 "parameter tuples cannot be named or nested",
1170                                 goto error);
1171                 }
1172                 map = isl_map_add_dims(map, type, n);
1173                 for (i = 0; i < n; ++i) {
1174                         isl_id *id;
1175                         if (!isl_space_has_dim_name(space, isl_dim_set, i))
1176                                 isl_die(s->ctx, isl_error_invalid,
1177                                         "parameters must be named",
1178                                         goto error);
1179                         id = isl_space_get_dim_id(space, isl_dim_set, i);
1180                         map = isl_map_set_dim_id(map, isl_dim_param, i, id);
1181                 }
1182         } else if (type == isl_dim_in) {
1183                 isl_set *set;
1184
1185                 set = isl_set_universe(isl_space_copy(space));
1186                 if (rational)
1187                         set = isl_set_set_rational(set);
1188                 set = isl_set_intersect_params(set, isl_map_params(map));
1189                 map = isl_map_from_domain(set);
1190         } else {
1191                 isl_set *set;
1192
1193                 set = isl_set_universe(isl_space_copy(space));
1194                 if (rational)
1195                         set = isl_set_set_rational(set);
1196                 map = isl_map_from_domain_and_range(isl_map_domain(map), set);
1197         }
1198
1199         for (i = 0; i < n; ++i) {
1200                 isl_pw_aff *pa;
1201                 isl_space *space;
1202                 isl_aff *aff;
1203                 isl_set *set;
1204                 isl_map *map_i;
1205
1206                 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
1207                 space = isl_pw_aff_get_domain_space(pa);
1208                 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1209                 aff = isl_aff_add_coefficient_si(aff,
1210                                                 isl_dim_in, v->n - n + i, -1);
1211                 pa = isl_pw_aff_add(pa, isl_pw_aff_from_aff(aff));
1212                 if (rational)
1213                         pa = isl_pw_aff_set_rational(pa);
1214                 set = isl_pw_aff_zero_set(pa);
1215                 map_i = isl_map_from_range(set);
1216                 map_i = isl_map_reset_space(map_i, isl_map_get_space(map));
1217                 map = isl_map_intersect(map, map_i);
1218         }
1219
1220         isl_space_free(space);
1221         isl_multi_pw_aff_free(tuple);
1222         return map;
1223 error:
1224         isl_space_free(space);
1225         isl_multi_pw_aff_free(tuple);
1226         isl_map_free(map);
1227         return NULL;
1228 }
1229
1230 static __isl_give isl_set *construct_constraints(
1231         __isl_take isl_set *set, int type,
1232         __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right,
1233         int rational)
1234 {
1235         isl_set *cond;
1236
1237         left = isl_pw_aff_list_copy(left);
1238         right = isl_pw_aff_list_copy(right);
1239         if (rational) {
1240                 left = isl_pw_aff_list_set_rational(left);
1241                 right = isl_pw_aff_list_set_rational(right);
1242         }
1243         if (type == ISL_TOKEN_LE)
1244                 cond = isl_pw_aff_list_le_set(left, right);
1245         else if (type == ISL_TOKEN_GE)
1246                 cond = isl_pw_aff_list_ge_set(left, right);
1247         else if (type == ISL_TOKEN_LT)
1248                 cond = isl_pw_aff_list_lt_set(left, right);
1249         else if (type == ISL_TOKEN_GT)
1250                 cond = isl_pw_aff_list_gt_set(left, right);
1251         else if (type == ISL_TOKEN_NE)
1252                 cond = isl_pw_aff_list_ne_set(left, right);
1253         else
1254                 cond = isl_pw_aff_list_eq_set(left, right);
1255
1256         return isl_set_intersect(set, cond);
1257 }
1258
1259 static __isl_give isl_map *add_constraint(struct isl_stream *s,
1260         struct vars *v, __isl_take isl_map *map, int rational)
1261 {
1262         struct isl_token *tok = NULL;
1263         isl_pw_aff_list *list1 = NULL, *list2 = NULL;
1264         isl_set *set;
1265
1266         set = isl_map_wrap(map);
1267         list1 = accept_affine_list(s, isl_set_get_space(set), v);
1268         if (!list1)
1269                 goto error;
1270         tok = isl_stream_next_token(s);
1271         if (!is_comparator(tok)) {
1272                 isl_stream_error(s, tok, "missing operator");
1273                 if (tok)
1274                         isl_stream_push_token(s, tok);
1275                 tok = NULL;
1276                 goto error;
1277         }
1278         for (;;) {
1279                 list2 = accept_affine_list(s, isl_set_get_space(set), v);
1280                 if (!list2)
1281                         goto error;
1282
1283                 set = construct_constraints(set, tok->type, list1, list2,
1284                                                 rational);
1285                 isl_token_free(tok);
1286                 isl_pw_aff_list_free(list1);
1287                 list1 = list2;
1288
1289                 tok = isl_stream_next_token(s);
1290                 if (!is_comparator(tok)) {
1291                         if (tok)
1292                                 isl_stream_push_token(s, tok);
1293                         break;
1294                 }
1295         }
1296         isl_pw_aff_list_free(list1);
1297
1298         return isl_set_unwrap(set);
1299 error:
1300         if (tok)
1301                 isl_token_free(tok);
1302         isl_pw_aff_list_free(list1);
1303         isl_pw_aff_list_free(list2);
1304         isl_set_free(set);
1305         return NULL;
1306 }
1307
1308 static __isl_give isl_map *read_exists(struct isl_stream *s,
1309         struct vars *v, __isl_take isl_map *map, int rational)
1310 {
1311         int n = v->n;
1312         int seen_paren = isl_stream_eat_if_available(s, '(');
1313
1314         map = isl_map_from_domain(isl_map_wrap(map));
1315         map = read_defined_var_list(s, v, map, rational);
1316
1317         if (isl_stream_eat(s, ':'))
1318                 goto error;
1319
1320         map = read_formula(s, v, map, rational);
1321         map = isl_set_unwrap(isl_map_domain(map));
1322
1323         vars_drop(v, v->n - n);
1324         if (seen_paren && isl_stream_eat(s, ')'))
1325                 goto error;
1326
1327         return map;
1328 error:
1329         isl_map_free(map);
1330         return NULL;
1331 }
1332
1333 /* Parse an expression between parentheses and push the result
1334  * back on the stream.
1335  *
1336  * The parsed expression may be either an affine expression
1337  * or a condition.  The first type is pushed onto the stream
1338  * as an isl_pw_aff, while the second is pushed as an isl_map.
1339  *
1340  * If the initial token indicates the start of a condition,
1341  * we parse it as such.
1342  * Otherwise, we first parse an affine expression and push
1343  * that onto the stream.  If the affine expression covers the
1344  * entire expression between parentheses, we return.
1345  * Otherwise, we assume that the affine expression is the
1346  * start of a condition and continue parsing.
1347  */
1348 static int resolve_paren_expr(struct isl_stream *s,
1349         struct vars *v, __isl_take isl_map *map, int rational)
1350 {
1351         struct isl_token *tok, *tok2;
1352         int line, col;
1353         isl_pw_aff *pwaff;
1354
1355         tok = isl_stream_next_token(s);
1356         if (!tok || tok->type != '(')
1357                 goto error;
1358
1359         if (isl_stream_next_token_is(s, '('))
1360                 if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1361                         goto error;
1362
1363         if (isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) ||
1364             isl_stream_next_token_is(s, ISL_TOKEN_NOT) ||
1365             isl_stream_next_token_is(s, ISL_TOKEN_TRUE) ||
1366             isl_stream_next_token_is(s, ISL_TOKEN_FALSE) ||
1367             isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1368                 map = read_formula(s, v, map, rational);
1369                 if (isl_stream_eat(s, ')'))
1370                         goto error;
1371                 tok->type = ISL_TOKEN_MAP;
1372                 tok->u.map = map;
1373                 isl_stream_push_token(s, tok);
1374                 return 0;
1375         }
1376
1377         tok2 = isl_stream_next_token(s);
1378         if (!tok2)
1379                 goto error;
1380         line = tok2->line;
1381         col = tok2->col;
1382         isl_stream_push_token(s, tok2);
1383
1384         pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
1385         if (!pwaff)
1386                 goto error;
1387
1388         tok2 = isl_token_new(s->ctx, line, col, 0);
1389         if (!tok2)
1390                 goto error2;
1391         tok2->type = ISL_TOKEN_AFF;
1392         tok2->u.pwaff = pwaff;
1393
1394         if (isl_stream_eat_if_available(s, ')')) {
1395                 isl_stream_push_token(s, tok2);
1396                 isl_token_free(tok);
1397                 isl_map_free(map);
1398                 return 0;
1399         }
1400
1401         isl_stream_push_token(s, tok2);
1402
1403         map = read_formula(s, v, map, rational);
1404         if (isl_stream_eat(s, ')'))
1405                 goto error;
1406
1407         tok->type = ISL_TOKEN_MAP;
1408         tok->u.map = map;
1409         isl_stream_push_token(s, tok);
1410
1411         return 0;
1412 error2:
1413         isl_pw_aff_free(pwaff);
1414 error:
1415         isl_token_free(tok);
1416         isl_map_free(map);
1417         return -1;
1418 }
1419
1420 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1421         struct vars *v, __isl_take isl_map *map, int rational)
1422 {
1423         if (isl_stream_next_token_is(s, '('))
1424                 if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1425                         goto error;
1426
1427         if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1428                 struct isl_token *tok;
1429                 tok = isl_stream_next_token(s);
1430                 if (!tok)
1431                         goto error;
1432                 isl_map_free(map);
1433                 map = isl_map_copy(tok->u.map);
1434                 isl_token_free(tok);
1435                 return map;
1436         }
1437
1438         if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1439                 return read_exists(s, v, map, rational);
1440
1441         if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1442                 return map;
1443
1444         if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1445                 isl_space *dim = isl_map_get_space(map);
1446                 isl_map_free(map);
1447                 return isl_map_empty(dim);
1448         }
1449
1450         return add_constraint(s, v, map, rational);
1451 error:
1452         isl_map_free(map);
1453         return NULL;
1454 }
1455
1456 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1457         struct vars *v, __isl_take isl_map *map, int rational)
1458 {
1459         isl_map *res;
1460         int negate;
1461
1462         negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1463         res = read_conjunct(s, v, isl_map_copy(map), rational);
1464         if (negate)
1465                 res = isl_map_subtract(isl_map_copy(map), res);
1466
1467         while (res && isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1468                 isl_map *res_i;
1469
1470                 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1471                 res_i = read_conjunct(s, v, isl_map_copy(map), rational);
1472                 if (negate)
1473                         res = isl_map_subtract(res, res_i);
1474                 else
1475                         res = isl_map_intersect(res, res_i);
1476         }
1477
1478         isl_map_free(map);
1479         return res;
1480 }
1481
1482 static struct isl_map *read_disjuncts(struct isl_stream *s,
1483         struct vars *v, __isl_take isl_map *map, int rational)
1484 {
1485         isl_map *res;
1486
1487         if (isl_stream_next_token_is(s, '}')) {
1488                 isl_space *dim = isl_map_get_space(map);
1489                 isl_map_free(map);
1490                 return isl_map_universe(dim);
1491         }
1492
1493         res = read_conjuncts(s, v, isl_map_copy(map), rational);
1494         while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1495                 isl_map *res_i;
1496
1497                 res_i = read_conjuncts(s, v, isl_map_copy(map), rational);
1498                 res = isl_map_union(res, res_i);
1499         }
1500
1501         isl_map_free(map);
1502         return res;
1503 }
1504
1505 /* Read a first order formula from "s", add the corresponding
1506  * constraints to "map" and return the result.
1507  *
1508  * In particular, read a formula of the form
1509  *
1510  *      a
1511  *
1512  * or
1513  *
1514  *      a implies b
1515  *
1516  * where a and b are disjunctions.
1517  *
1518  * In the first case, map is replaced by
1519  *
1520  *      map \cap { [..] : a }
1521  *
1522  * In the second case, it is replaced by
1523  *
1524  *      (map \setminus { [..] : a}) \cup (map \cap { [..] : b })
1525  */
1526 static __isl_give isl_map *read_formula(struct isl_stream *s,
1527         struct vars *v, __isl_take isl_map *map, int rational)
1528 {
1529         isl_map *res;
1530
1531         res = read_disjuncts(s, v, isl_map_copy(map), rational);
1532
1533         if (isl_stream_eat_if_available(s, ISL_TOKEN_IMPLIES)) {
1534                 isl_map *res2;
1535
1536                 res = isl_map_subtract(isl_map_copy(map), res);
1537                 res2 = read_disjuncts(s, v, map, rational);
1538                 res = isl_map_union(res, res2);
1539         } else
1540                 isl_map_free(map);
1541
1542         return res;
1543 }
1544
1545 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1546 {
1547         if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1548                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1549                            isl_basic_map_dim(bmap, isl_dim_in) + pos;
1550         pos -= isl_basic_map_dim(bmap, isl_dim_out);
1551
1552         if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1553                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1554         pos -= isl_basic_map_dim(bmap, isl_dim_in);
1555
1556         if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1557                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1558                            isl_basic_map_dim(bmap, isl_dim_in) +
1559                            isl_basic_map_dim(bmap, isl_dim_out) + pos;
1560         pos -= isl_basic_map_dim(bmap, isl_dim_div);
1561
1562         if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1563                 return 1 + pos;
1564
1565         return 0;
1566 }
1567
1568 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1569         struct isl_stream *s, __isl_take isl_basic_map *bmap)
1570 {
1571         int j;
1572         struct isl_token *tok;
1573         int type;
1574         int k;
1575         isl_int *c;
1576         unsigned nparam;
1577         unsigned dim;
1578
1579         if (!bmap)
1580                 return NULL;
1581
1582         nparam = isl_basic_map_dim(bmap, isl_dim_param);
1583         dim = isl_basic_map_dim(bmap, isl_dim_out);
1584
1585         tok = isl_stream_next_token(s);
1586         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1587                 isl_stream_error(s, tok, "expecting coefficient");
1588                 if (tok)
1589                         isl_stream_push_token(s, tok);
1590                 goto error;
1591         }
1592         if (!tok->on_new_line) {
1593                 isl_stream_error(s, tok, "coefficient should appear on new line");
1594                 isl_stream_push_token(s, tok);
1595                 goto error;
1596         }
1597
1598         type = isl_int_get_si(tok->u.v);
1599         isl_token_free(tok);
1600
1601         isl_assert(s->ctx, type == 0 || type == 1, goto error);
1602         if (type == 0) {
1603                 k = isl_basic_map_alloc_equality(bmap);
1604                 c = bmap->eq[k];
1605         } else {
1606                 k = isl_basic_map_alloc_inequality(bmap);
1607                 c = bmap->ineq[k];
1608         }
1609         if (k < 0)
1610                 goto error;
1611
1612         for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1613                 int pos;
1614                 tok = isl_stream_next_token(s);
1615                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1616                         isl_stream_error(s, tok, "expecting coefficient");
1617                         if (tok)
1618                                 isl_stream_push_token(s, tok);
1619                         goto error;
1620                 }
1621                 if (tok->on_new_line) {
1622                         isl_stream_error(s, tok,
1623                                 "coefficient should not appear on new line");
1624                         isl_stream_push_token(s, tok);
1625                         goto error;
1626                 }
1627                 pos = polylib_pos_to_isl_pos(bmap, j);
1628                 isl_int_set(c[pos], tok->u.v);
1629                 isl_token_free(tok);
1630         }
1631
1632         return bmap;
1633 error:
1634         isl_basic_map_free(bmap);
1635         return NULL;
1636 }
1637
1638 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s)
1639 {
1640         int i;
1641         struct isl_token *tok;
1642         struct isl_token *tok2;
1643         int n_row, n_col;
1644         int on_new_line;
1645         unsigned in = 0, out, local = 0;
1646         struct isl_basic_map *bmap = NULL;
1647         int nparam = 0;
1648
1649         tok = isl_stream_next_token(s);
1650         if (!tok) {
1651                 isl_stream_error(s, NULL, "unexpected EOF");
1652                 return NULL;
1653         }
1654         tok2 = isl_stream_next_token(s);
1655         if (!tok2) {
1656                 isl_token_free(tok);
1657                 isl_stream_error(s, NULL, "unexpected EOF");
1658                 return NULL;
1659         }
1660         if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1661                 isl_stream_push_token(s, tok2);
1662                 isl_stream_push_token(s, tok);
1663                 isl_stream_error(s, NULL,
1664                                  "expecting constraint matrix dimensions");
1665                 return NULL;
1666         }
1667         n_row = isl_int_get_si(tok->u.v);
1668         n_col = isl_int_get_si(tok2->u.v);
1669         on_new_line = tok2->on_new_line;
1670         isl_token_free(tok2);
1671         isl_token_free(tok);
1672         isl_assert(s->ctx, !on_new_line, return NULL);
1673         isl_assert(s->ctx, n_row >= 0, return NULL);
1674         isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1675         tok = isl_stream_next_token_on_same_line(s);
1676         if (tok) {
1677                 if (tok->type != ISL_TOKEN_VALUE) {
1678                         isl_stream_error(s, tok,
1679                                     "expecting number of output dimensions");
1680                         isl_stream_push_token(s, tok);
1681                         goto error;
1682                 }
1683                 out = isl_int_get_si(tok->u.v);
1684                 isl_token_free(tok);
1685
1686                 tok = isl_stream_next_token_on_same_line(s);
1687                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1688                         isl_stream_error(s, tok,
1689                                     "expecting number of input dimensions");
1690                         if (tok)
1691                                 isl_stream_push_token(s, tok);
1692                         goto error;
1693                 }
1694                 in = isl_int_get_si(tok->u.v);
1695                 isl_token_free(tok);
1696
1697                 tok = isl_stream_next_token_on_same_line(s);
1698                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1699                         isl_stream_error(s, tok,
1700                                     "expecting number of existentials");
1701                         if (tok)
1702                                 isl_stream_push_token(s, tok);
1703                         goto error;
1704                 }
1705                 local = isl_int_get_si(tok->u.v);
1706                 isl_token_free(tok);
1707
1708                 tok = isl_stream_next_token_on_same_line(s);
1709                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1710                         isl_stream_error(s, tok,
1711                                     "expecting number of parameters");
1712                         if (tok)
1713                                 isl_stream_push_token(s, tok);
1714                         goto error;
1715                 }
1716                 nparam = isl_int_get_si(tok->u.v);
1717                 isl_token_free(tok);
1718                 if (n_col != 1 + out + in + local + nparam + 1) {
1719                         isl_stream_error(s, NULL,
1720                                     "dimensions don't match");
1721                         goto error;
1722                 }
1723         } else
1724                 out = n_col - 2 - nparam;
1725         bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1726         if (!bmap)
1727                 return NULL;
1728
1729         for (i = 0; i < local; ++i) {
1730                 int k = isl_basic_map_alloc_div(bmap);
1731                 if (k < 0)
1732                         goto error;
1733                 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1734         }
1735
1736         for (i = 0; i < n_row; ++i)
1737                 bmap = basic_map_read_polylib_constraint(s, bmap);
1738
1739         tok = isl_stream_next_token_on_same_line(s);
1740         if (tok) {
1741                 isl_stream_error(s, tok, "unexpected extra token on line");
1742                 isl_stream_push_token(s, tok);
1743                 goto error;
1744         }
1745
1746         bmap = isl_basic_map_simplify(bmap);
1747         bmap = isl_basic_map_finalize(bmap);
1748         return bmap;
1749 error:
1750         isl_basic_map_free(bmap);
1751         return NULL;
1752 }
1753
1754 static struct isl_map *map_read_polylib(struct isl_stream *s)
1755 {
1756         struct isl_token *tok;
1757         struct isl_token *tok2;
1758         int i, n;
1759         struct isl_map *map;
1760
1761         tok = isl_stream_next_token(s);
1762         if (!tok) {
1763                 isl_stream_error(s, NULL, "unexpected EOF");
1764                 return NULL;
1765         }
1766         tok2 = isl_stream_next_token_on_same_line(s);
1767         if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1768                 isl_stream_push_token(s, tok2);
1769                 isl_stream_push_token(s, tok);
1770                 return isl_map_from_basic_map(basic_map_read_polylib(s));
1771         }
1772         if (tok2) {
1773                 isl_stream_error(s, tok2, "unexpected token");
1774                 isl_stream_push_token(s, tok2);
1775                 isl_stream_push_token(s, tok);
1776                 return NULL;
1777         }
1778         n = isl_int_get_si(tok->u.v);
1779         isl_token_free(tok);
1780
1781         isl_assert(s->ctx, n >= 1, return NULL);
1782
1783         map = isl_map_from_basic_map(basic_map_read_polylib(s));
1784
1785         for (i = 1; map && i < n; ++i)
1786                 map = isl_map_union(map,
1787                         isl_map_from_basic_map(basic_map_read_polylib(s)));
1788
1789         return map;
1790 }
1791
1792 static int optional_power(struct isl_stream *s)
1793 {
1794         int pow;
1795         struct isl_token *tok;
1796
1797         tok = isl_stream_next_token(s);
1798         if (!tok)
1799                 return 1;
1800         if (tok->type != '^') {
1801                 isl_stream_push_token(s, tok);
1802                 return 1;
1803         }
1804         isl_token_free(tok);
1805         tok = isl_stream_next_token(s);
1806         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1807                 isl_stream_error(s, tok, "expecting exponent");
1808                 if (tok)
1809                         isl_stream_push_token(s, tok);
1810                 return 1;
1811         }
1812         pow = isl_int_get_si(tok->u.v);
1813         isl_token_free(tok);
1814         return pow;
1815 }
1816
1817 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1818         __isl_keep isl_map *map, struct vars *v);
1819
1820 static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s,
1821         __isl_keep isl_map *map, struct vars *v)
1822 {
1823         isl_pw_qpolynomial *pwqp;
1824         struct isl_token *tok;
1825
1826         tok = next_token(s);
1827         if (!tok) {
1828                 isl_stream_error(s, NULL, "unexpected EOF");
1829                 return NULL;
1830         }
1831         if (tok->type == '(') {
1832                 int pow;
1833
1834                 isl_token_free(tok);
1835                 pwqp = read_term(s, map, v);
1836                 if (!pwqp)
1837                         return NULL;
1838                 if (isl_stream_eat(s, ')'))
1839                         goto error;
1840                 pow = optional_power(s);
1841                 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1842         } else if (tok->type == ISL_TOKEN_VALUE) {
1843                 struct isl_token *tok2;
1844                 isl_qpolynomial *qp;
1845
1846                 tok2 = isl_stream_next_token(s);
1847                 if (tok2 && tok2->type == '/') {
1848                         isl_token_free(tok2);
1849                         tok2 = next_token(s);
1850                         if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1851                                 isl_stream_error(s, tok2, "expected denominator");
1852                                 isl_token_free(tok);
1853                                 isl_token_free(tok2);
1854                                 return NULL;
1855                         }
1856                         qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
1857                                                     tok->u.v, tok2->u.v);
1858                         isl_token_free(tok2);
1859                 } else {
1860                         isl_stream_push_token(s, tok2);
1861                         qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
1862                                                 tok->u.v);
1863                 }
1864                 isl_token_free(tok);
1865                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1866         } else if (tok->type == ISL_TOKEN_INFTY) {
1867                 isl_qpolynomial *qp;
1868                 isl_token_free(tok);
1869                 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
1870                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1871         } else if (tok->type == ISL_TOKEN_NAN) {
1872                 isl_qpolynomial *qp;
1873                 isl_token_free(tok);
1874                 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
1875                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1876         } else if (tok->type == ISL_TOKEN_IDENT) {
1877                 int n = v->n;
1878                 int pos = vars_pos(v, tok->u.s, -1);
1879                 int pow;
1880                 isl_qpolynomial *qp;
1881                 if (pos < 0) {
1882                         isl_token_free(tok);
1883                         return NULL;
1884                 }
1885                 if (pos >= n) {
1886                         vars_drop(v, v->n - n);
1887                         isl_stream_error(s, tok, "unknown identifier");
1888                         isl_token_free(tok);
1889                         return NULL;
1890                 }
1891                 isl_token_free(tok);
1892                 pow = optional_power(s);
1893                 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
1894                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1895         } else if (is_start_of_div(tok)) {
1896                 isl_pw_aff *pwaff;
1897                 int pow;
1898
1899                 isl_stream_push_token(s, tok);
1900                 pwaff = accept_div(s, isl_map_get_space(map), v);
1901                 pow = optional_power(s);
1902                 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
1903                 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1904         } else if (tok->type == '-') {
1905                 isl_token_free(tok);
1906                 pwqp = read_factor(s, map, v);
1907                 pwqp = isl_pw_qpolynomial_neg(pwqp);
1908         } else {
1909                 isl_stream_error(s, tok, "unexpected isl_token");
1910                 isl_stream_push_token(s, tok);
1911                 return NULL;
1912         }
1913
1914         if (isl_stream_eat_if_available(s, '*') ||
1915             isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1916                 isl_pw_qpolynomial *pwqp2;
1917
1918                 pwqp2 = read_factor(s, map, v);
1919                 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
1920         }
1921
1922         return pwqp;
1923 error:
1924         isl_pw_qpolynomial_free(pwqp);
1925         return NULL;
1926 }
1927
1928 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1929         __isl_keep isl_map *map, struct vars *v)
1930 {
1931         struct isl_token *tok;
1932         isl_pw_qpolynomial *pwqp;
1933
1934         pwqp = read_factor(s, map, v);
1935
1936         for (;;) {
1937                 tok = next_token(s);
1938                 if (!tok)
1939                         return pwqp;
1940
1941                 if (tok->type == '+') {
1942                         isl_pw_qpolynomial *pwqp2;
1943
1944                         isl_token_free(tok);
1945                         pwqp2 = read_factor(s, map, v);
1946                         pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1947                 } else if (tok->type == '-') {
1948                         isl_pw_qpolynomial *pwqp2;
1949
1950                         isl_token_free(tok);
1951                         pwqp2 = read_factor(s, map, v);
1952                         pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
1953                 } else if (tok->type == ISL_TOKEN_VALUE &&
1954                             isl_int_is_neg(tok->u.v)) {
1955                         isl_pw_qpolynomial *pwqp2;
1956
1957                         isl_stream_push_token(s, tok);
1958                         pwqp2 = read_factor(s, map, v);
1959                         pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1960                 } else {
1961                         isl_stream_push_token(s, tok);
1962                         break;
1963                 }
1964         }
1965
1966         return pwqp;
1967 }
1968
1969 static __isl_give isl_map *read_optional_formula(struct isl_stream *s,
1970         __isl_take isl_map *map, struct vars *v, int rational)
1971 {
1972         struct isl_token *tok;
1973
1974         tok = isl_stream_next_token(s);
1975         if (!tok) {
1976                 isl_stream_error(s, NULL, "unexpected EOF");
1977                 goto error;
1978         }
1979         if (tok->type == ':' ||
1980             (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
1981                 isl_token_free(tok);
1982                 map = read_formula(s, v, map, rational);
1983         } else
1984                 isl_stream_push_token(s, tok);
1985
1986         return map;
1987 error:
1988         isl_map_free(map);
1989         return NULL;
1990 }
1991
1992 static struct isl_obj obj_read_poly(struct isl_stream *s,
1993         __isl_take isl_map *map, struct vars *v, int n)
1994 {
1995         struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1996         isl_pw_qpolynomial *pwqp;
1997         struct isl_set *set;
1998
1999         pwqp = read_term(s, map, v);
2000         map = read_optional_formula(s, map, v, 0);
2001         set = isl_map_range(map);
2002
2003         pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
2004
2005         vars_drop(v, v->n - n);
2006
2007         obj.v = pwqp;
2008         return obj;
2009 }
2010
2011 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
2012         __isl_take isl_set *set, struct vars *v, int n)
2013 {
2014         struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
2015         isl_pw_qpolynomial *pwqp;
2016         isl_pw_qpolynomial_fold *pwf = NULL;
2017
2018         if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
2019                 return obj_read_poly(s, set, v, n);
2020
2021         if (isl_stream_eat(s, '('))
2022                 goto error;
2023
2024         pwqp = read_term(s, set, v);
2025         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
2026
2027         while (isl_stream_eat_if_available(s, ',')) {
2028                 isl_pw_qpolynomial_fold *pwf_i;
2029                 pwqp = read_term(s, set, v);
2030                 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
2031                                                                         pwqp);
2032                 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
2033         }
2034
2035         if (isl_stream_eat(s, ')'))
2036                 goto error;
2037
2038         set = read_optional_formula(s, set, v, 0);
2039         pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
2040
2041         vars_drop(v, v->n - n);
2042
2043         obj.v = pwf;
2044         return obj;
2045 error:
2046         isl_set_free(set);
2047         isl_pw_qpolynomial_fold_free(pwf);
2048         obj.type = isl_obj_none;
2049         return obj;
2050 }
2051
2052 static int is_rational(struct isl_stream *s)
2053 {
2054         struct isl_token *tok;
2055
2056         tok = isl_stream_next_token(s);
2057         if (!tok)
2058                 return 0;
2059         if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
2060                 isl_token_free(tok);
2061                 isl_stream_eat(s, ':');
2062                 return 1;
2063         }
2064
2065         isl_stream_push_token(s, tok);
2066
2067         return 0;
2068 }
2069
2070 static struct isl_obj obj_read_body(struct isl_stream *s,
2071         __isl_take isl_map *map, struct vars *v)
2072 {
2073         struct isl_token *tok;
2074         struct isl_obj obj = { isl_obj_set, NULL };
2075         int n = v->n;
2076         int rational;
2077
2078         rational = is_rational(s);
2079         if (rational)
2080                 map = isl_map_set_rational(map);
2081
2082         if (isl_stream_next_token_is(s, ':')) {
2083                 obj.type = isl_obj_set;
2084                 obj.v = read_optional_formula(s, map, v, rational);
2085                 return obj;
2086         }
2087
2088         if (!next_is_tuple(s))
2089                 return obj_read_poly_or_fold(s, map, v, n);
2090
2091         map = read_map_tuple(s, map, isl_dim_in, v, rational, 0);
2092         if (!map)
2093                 goto error;
2094         tok = isl_stream_next_token(s);
2095         if (!tok)
2096                 goto error;
2097         if (tok->type == ISL_TOKEN_TO) {
2098                 obj.type = isl_obj_map;
2099                 isl_token_free(tok);
2100                 if (!next_is_tuple(s)) {
2101                         isl_set *set = isl_map_domain(map);
2102                         return obj_read_poly_or_fold(s, set, v, n);
2103                 }
2104                 map = read_map_tuple(s, map, isl_dim_out, v, rational, 0);
2105                 if (!map)
2106                         goto error;
2107         } else {
2108                 map = isl_map_domain(map);
2109                 isl_stream_push_token(s, tok);
2110         }
2111
2112         map = read_optional_formula(s, map, v, rational);
2113
2114         vars_drop(v, v->n - n);
2115
2116         obj.v = map;
2117         return obj;
2118 error:
2119         isl_map_free(map);
2120         obj.type = isl_obj_none;
2121         return obj;
2122 }
2123
2124 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2125 {
2126         if (obj.type == isl_obj_map) {
2127                 obj.v = isl_union_map_from_map(obj.v);
2128                 obj.type = isl_obj_union_map;
2129         } else if (obj.type == isl_obj_set) {
2130                 obj.v = isl_union_set_from_set(obj.v);
2131                 obj.type = isl_obj_union_set;
2132         } else if (obj.type == isl_obj_pw_qpolynomial) {
2133                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2134                 obj.type = isl_obj_union_pw_qpolynomial;
2135         } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
2136                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
2137                 obj.type = isl_obj_union_pw_qpolynomial_fold;
2138         } else
2139                 isl_assert(ctx, 0, goto error);
2140         return obj;
2141 error:
2142         obj.type->free(obj.v);
2143         obj.type = isl_obj_none;
2144         return obj;
2145 }
2146
2147 static struct isl_obj obj_add(struct isl_ctx *ctx,
2148         struct isl_obj obj1, struct isl_obj obj2)
2149 {
2150         if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
2151                 obj1 = to_union(ctx, obj1);
2152         if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
2153                 obj2 = to_union(ctx, obj2);
2154         if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
2155                 obj1 = to_union(ctx, obj1);
2156         if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
2157                 obj2 = to_union(ctx, obj2);
2158         if (obj1.type == isl_obj_pw_qpolynomial &&
2159             obj2.type == isl_obj_union_pw_qpolynomial)
2160                 obj1 = to_union(ctx, obj1);
2161         if (obj1.type == isl_obj_union_pw_qpolynomial &&
2162             obj2.type == isl_obj_pw_qpolynomial)
2163                 obj2 = to_union(ctx, obj2);
2164         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2165             obj2.type == isl_obj_union_pw_qpolynomial_fold)
2166                 obj1 = to_union(ctx, obj1);
2167         if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2168             obj2.type == isl_obj_pw_qpolynomial_fold)
2169                 obj2 = to_union(ctx, obj2);
2170         isl_assert(ctx, obj1.type == obj2.type, goto error);
2171         if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
2172                 obj1 = to_union(ctx, obj1);
2173                 obj2 = to_union(ctx, obj2);
2174         }
2175         if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
2176                 obj1 = to_union(ctx, obj1);
2177                 obj2 = to_union(ctx, obj2);
2178         }
2179         if (obj1.type == isl_obj_pw_qpolynomial &&
2180             !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
2181                 obj1 = to_union(ctx, obj1);
2182                 obj2 = to_union(ctx, obj2);
2183         }
2184         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2185             !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
2186                 obj1 = to_union(ctx, obj1);
2187                 obj2 = to_union(ctx, obj2);
2188         }
2189         obj1.v = obj1.type->add(obj1.v, obj2.v);
2190         return obj1;
2191 error:
2192         obj1.type->free(obj1.v);
2193         obj2.type->free(obj2.v);
2194         obj1.type = isl_obj_none;
2195         obj1.v = NULL;
2196         return obj1;
2197 }
2198
2199 static struct isl_obj obj_read(struct isl_stream *s)
2200 {
2201         isl_map *map = NULL;
2202         struct isl_token *tok;
2203         struct vars *v = NULL;
2204         struct isl_obj obj = { isl_obj_set, NULL };
2205
2206         tok = next_token(s);
2207         if (!tok) {
2208                 isl_stream_error(s, NULL, "unexpected EOF");
2209                 goto error;
2210         }
2211         if (tok->type == ISL_TOKEN_VALUE) {
2212                 struct isl_token *tok2;
2213                 struct isl_map *map;
2214
2215                 tok2 = isl_stream_next_token(s);
2216                 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
2217                     isl_int_is_neg(tok2->u.v)) {
2218                         if (tok2)
2219                                 isl_stream_push_token(s, tok2);
2220                         obj.type = isl_obj_int;
2221                         obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
2222                         isl_token_free(tok);
2223                         return obj;
2224                 }
2225                 isl_stream_push_token(s, tok2);
2226                 isl_stream_push_token(s, tok);
2227                 map = map_read_polylib(s);
2228                 if (!map)
2229                         goto error;
2230                 if (isl_map_may_be_set(map))
2231                         obj.v = isl_map_range(map);
2232                 else {
2233                         obj.type = isl_obj_map;
2234                         obj.v = map;
2235                 }
2236                 return obj;
2237         }
2238         v = vars_new(s->ctx);
2239         if (!v) {
2240                 isl_stream_push_token(s, tok);
2241                 goto error;
2242         }
2243         map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
2244         if (tok->type == '[') {
2245                 isl_stream_push_token(s, tok);
2246                 map = read_map_tuple(s, map, isl_dim_param, v, 0, 0);
2247                 if (!map)
2248                         goto error;
2249                 tok = isl_stream_next_token(s);
2250                 if (!tok || tok->type != ISL_TOKEN_TO) {
2251                         isl_stream_error(s, tok, "expecting '->'");
2252                         if (tok)
2253                                 isl_stream_push_token(s, tok);
2254                         goto error;
2255                 }
2256                 isl_token_free(tok);
2257                 tok = isl_stream_next_token(s);
2258         }
2259         if (!tok || tok->type != '{') {
2260                 isl_stream_error(s, tok, "expecting '{'");
2261                 if (tok)
2262                         isl_stream_push_token(s, tok);
2263                 goto error;
2264         }
2265         isl_token_free(tok);
2266
2267         tok = isl_stream_next_token(s);
2268         if (!tok)
2269                 ;
2270         else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
2271                 isl_token_free(tok);
2272                 if (isl_stream_eat(s, '='))
2273                         goto error;
2274                 map = read_map_tuple(s, map, isl_dim_param, v, 0, 1);
2275                 if (!map)
2276                         goto error;
2277         } else if (tok->type == '}') {
2278                 obj.type = isl_obj_union_set;
2279                 obj.v = isl_union_set_empty(isl_map_get_space(map));
2280                 isl_token_free(tok);
2281                 goto done;
2282         } else
2283                 isl_stream_push_token(s, tok);
2284
2285         for (;;) {
2286                 struct isl_obj o;
2287                 tok = NULL;
2288                 o = obj_read_body(s, isl_map_copy(map), v);
2289                 if (o.type == isl_obj_none || !o.v)
2290                         goto error;
2291                 if (!obj.v)
2292                         obj = o;
2293                 else {
2294                         obj = obj_add(s->ctx, obj, o);
2295                         if (obj.type == isl_obj_none || !obj.v)
2296                                 goto error;
2297                 }
2298                 tok = isl_stream_next_token(s);
2299                 if (!tok || tok->type != ';')
2300                         break;
2301                 isl_token_free(tok);
2302                 if (isl_stream_next_token_is(s, '}')) {
2303                         tok = isl_stream_next_token(s);
2304                         break;
2305                 }
2306         }
2307
2308         if (tok && tok->type == '}') {
2309                 isl_token_free(tok);
2310         } else {
2311                 isl_stream_error(s, tok, "unexpected isl_token");
2312                 if (tok)
2313                         isl_token_free(tok);
2314                 goto error;
2315         }
2316 done:
2317         vars_free(v);
2318         isl_map_free(map);
2319
2320         return obj;
2321 error:
2322         isl_map_free(map);
2323         obj.type->free(obj.v);
2324         if (v)
2325                 vars_free(v);
2326         obj.v = NULL;
2327         return obj;
2328 }
2329
2330 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
2331 {
2332         return obj_read(s);
2333 }
2334
2335 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
2336 {
2337         struct isl_obj obj;
2338
2339         obj = obj_read(s);
2340         if (obj.v)
2341                 isl_assert(s->ctx, obj.type == isl_obj_map ||
2342                                    obj.type == isl_obj_set, goto error);
2343
2344         if (obj.type == isl_obj_set)
2345                 obj.v = isl_map_from_range(obj.v);
2346
2347         return obj.v;
2348 error:
2349         obj.type->free(obj.v);
2350         return NULL;
2351 }
2352
2353 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2354 {
2355         struct isl_obj obj;
2356
2357         obj = obj_read(s);
2358         if (obj.v) {
2359                 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2360                         obj.v = isl_map_range(obj.v);
2361                         obj.type = isl_obj_set;
2362                 }
2363                 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2364         }
2365
2366         return obj.v;
2367 error:
2368         obj.type->free(obj.v);
2369         return NULL;
2370 }
2371
2372 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2373 {
2374         struct isl_obj obj;
2375
2376         obj = obj_read(s);
2377         if (obj.type == isl_obj_map) {
2378                 obj.type = isl_obj_union_map;
2379                 obj.v = isl_union_map_from_map(obj.v);
2380         }
2381         if (obj.type == isl_obj_set) {
2382                 obj.type = isl_obj_union_set;
2383                 obj.v = isl_union_set_from_set(obj.v);
2384         }
2385         if (obj.v && obj.type == isl_obj_union_set &&
2386             isl_union_set_is_empty(obj.v))
2387                 obj.type = isl_obj_union_map;
2388         if (obj.v && obj.type != isl_obj_union_map)
2389                 isl_die(s->ctx, isl_error_invalid, "invalid input", goto error);
2390
2391         return obj.v;
2392 error:
2393         obj.type->free(obj.v);
2394         return NULL;
2395 }
2396
2397 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2398 {
2399         struct isl_obj obj;
2400
2401         obj = obj_read(s);
2402         if (obj.type == isl_obj_set) {
2403                 obj.type = isl_obj_union_set;
2404                 obj.v = isl_union_set_from_set(obj.v);
2405         }
2406         if (obj.v)
2407                 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2408
2409         return obj.v;
2410 error:
2411         obj.type->free(obj.v);
2412         return NULL;
2413 }
2414
2415 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2416 {
2417         struct isl_obj obj;
2418         struct isl_map *map;
2419         struct isl_basic_map *bmap;
2420
2421         obj = obj_read(s);
2422         map = obj.v;
2423         if (!map)
2424                 return NULL;
2425
2426         isl_assert(map->ctx, map->n <= 1, goto error);
2427
2428         if (map->n == 0)
2429                 bmap = isl_basic_map_empty_like_map(map);
2430         else
2431                 bmap = isl_basic_map_copy(map->p[0]);
2432
2433         isl_map_free(map);
2434
2435         return bmap;
2436 error:
2437         isl_map_free(map);
2438         return NULL;
2439 }
2440
2441 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2442 {
2443         isl_basic_map *bmap;
2444         bmap = basic_map_read(s);
2445         if (!bmap)
2446                 return NULL;
2447         if (!isl_basic_map_may_be_set(bmap))
2448                 isl_die(s->ctx, isl_error_invalid,
2449                         "input is not a set", goto error);
2450         return isl_basic_map_range(bmap);
2451 error:
2452         isl_basic_map_free(bmap);
2453         return NULL;
2454 }
2455
2456 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2457         FILE *input)
2458 {
2459         struct isl_basic_map *bmap;
2460         struct isl_stream *s = isl_stream_new_file(ctx, input);
2461         if (!s)
2462                 return NULL;
2463         bmap = basic_map_read(s);
2464         isl_stream_free(s);
2465         return bmap;
2466 }
2467
2468 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2469         FILE *input)
2470 {
2471         isl_basic_set *bset;
2472         struct isl_stream *s = isl_stream_new_file(ctx, input);
2473         if (!s)
2474                 return NULL;
2475         bset = basic_set_read(s);
2476         isl_stream_free(s);
2477         return bset;
2478 }
2479
2480 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2481         const char *str)
2482 {
2483         struct isl_basic_map *bmap;
2484         struct isl_stream *s = isl_stream_new_str(ctx, str);
2485         if (!s)
2486                 return NULL;
2487         bmap = basic_map_read(s);
2488         isl_stream_free(s);
2489         return bmap;
2490 }
2491
2492 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2493         const char *str)
2494 {
2495         isl_basic_set *bset;
2496         struct isl_stream *s = isl_stream_new_str(ctx, str);
2497         if (!s)
2498                 return NULL;
2499         bset = basic_set_read(s);
2500         isl_stream_free(s);
2501         return bset;
2502 }
2503
2504 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2505         FILE *input)
2506 {
2507         struct isl_map *map;
2508         struct isl_stream *s = isl_stream_new_file(ctx, input);
2509         if (!s)
2510                 return NULL;
2511         map = isl_stream_read_map(s);
2512         isl_stream_free(s);
2513         return map;
2514 }
2515
2516 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2517         const char *str)
2518 {
2519         struct isl_map *map;
2520         struct isl_stream *s = isl_stream_new_str(ctx, str);
2521         if (!s)
2522                 return NULL;
2523         map = isl_stream_read_map(s);
2524         isl_stream_free(s);
2525         return map;
2526 }
2527
2528 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2529         FILE *input)
2530 {
2531         isl_set *set;
2532         struct isl_stream *s = isl_stream_new_file(ctx, input);
2533         if (!s)
2534                 return NULL;
2535         set = isl_stream_read_set(s);
2536         isl_stream_free(s);
2537         return set;
2538 }
2539
2540 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2541         const char *str)
2542 {
2543         isl_set *set;
2544         struct isl_stream *s = isl_stream_new_str(ctx, str);
2545         if (!s)
2546                 return NULL;
2547         set = isl_stream_read_set(s);
2548         isl_stream_free(s);
2549         return set;
2550 }
2551
2552 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2553         FILE *input)
2554 {
2555         isl_union_map *umap;
2556         struct isl_stream *s = isl_stream_new_file(ctx, input);
2557         if (!s)
2558                 return NULL;
2559         umap = isl_stream_read_union_map(s);
2560         isl_stream_free(s);
2561         return umap;
2562 }
2563
2564 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2565                 const char *str)
2566 {
2567         isl_union_map *umap;
2568         struct isl_stream *s = isl_stream_new_str(ctx, str);
2569         if (!s)
2570                 return NULL;
2571         umap = isl_stream_read_union_map(s);
2572         isl_stream_free(s);
2573         return umap;
2574 }
2575
2576 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2577         FILE *input)
2578 {
2579         isl_union_set *uset;
2580         struct isl_stream *s = isl_stream_new_file(ctx, input);
2581         if (!s)
2582                 return NULL;
2583         uset = isl_stream_read_union_set(s);
2584         isl_stream_free(s);
2585         return uset;
2586 }
2587
2588 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2589                 const char *str)
2590 {
2591         isl_union_set *uset;
2592         struct isl_stream *s = isl_stream_new_str(ctx, str);
2593         if (!s)
2594                 return NULL;
2595         uset = isl_stream_read_union_set(s);
2596         isl_stream_free(s);
2597         return uset;
2598 }
2599
2600 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2601 {
2602         struct isl_vec *vec = NULL;
2603         struct isl_token *tok;
2604         unsigned size;
2605         int j;
2606
2607         tok = isl_stream_next_token(s);
2608         if (!tok || tok->type != ISL_TOKEN_VALUE) {
2609                 isl_stream_error(s, tok, "expecting vector length");
2610                 goto error;
2611         }
2612
2613         size = isl_int_get_si(tok->u.v);
2614         isl_token_free(tok);
2615
2616         vec = isl_vec_alloc(s->ctx, size);
2617
2618         for (j = 0; j < size; ++j) {
2619                 tok = isl_stream_next_token(s);
2620                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2621                         isl_stream_error(s, tok, "expecting constant value");
2622                         goto error;
2623                 }
2624                 isl_int_set(vec->el[j], tok->u.v);
2625                 isl_token_free(tok);
2626         }
2627
2628         return vec;
2629 error:
2630         isl_token_free(tok);
2631         isl_vec_free(vec);
2632         return NULL;
2633 }
2634
2635 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2636 {
2637         return isl_vec_read_polylib(s);
2638 }
2639
2640 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2641 {
2642         isl_vec *v;
2643         struct isl_stream *s = isl_stream_new_file(ctx, input);
2644         if (!s)
2645                 return NULL;
2646         v = vec_read(s);
2647         isl_stream_free(s);
2648         return v;
2649 }
2650
2651 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2652         struct isl_stream *s)
2653 {
2654         struct isl_obj obj;
2655
2656         obj = obj_read(s);
2657         if (obj.v)
2658                 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2659                            goto error);
2660
2661         return obj.v;
2662 error:
2663         obj.type->free(obj.v);
2664         return NULL;
2665 }
2666
2667 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2668                 const char *str)
2669 {
2670         isl_pw_qpolynomial *pwqp;
2671         struct isl_stream *s = isl_stream_new_str(ctx, str);
2672         if (!s)
2673                 return NULL;
2674         pwqp = isl_stream_read_pw_qpolynomial(s);
2675         isl_stream_free(s);
2676         return pwqp;
2677 }
2678
2679 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2680                 FILE *input)
2681 {
2682         isl_pw_qpolynomial *pwqp;
2683         struct isl_stream *s = isl_stream_new_file(ctx, input);
2684         if (!s)
2685                 return NULL;
2686         pwqp = isl_stream_read_pw_qpolynomial(s);
2687         isl_stream_free(s);
2688         return pwqp;
2689 }
2690
2691 /* Is the next token an identifer not in "v"?
2692  */
2693 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2694 {
2695         int n = v->n;
2696         int fresh;
2697         struct isl_token *tok;
2698
2699         tok = isl_stream_next_token(s);
2700         if (!tok)
2701                 return 0;
2702         fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2703         isl_stream_push_token(s, tok);
2704
2705         vars_drop(v, v->n - n);
2706
2707         return fresh;
2708 }
2709
2710 /* First read the domain of the affine expression, which may be
2711  * a parameter space or a set.
2712  * The tricky part is that we don't know if the domain is a set or not,
2713  * so when we are trying to read the domain, we may actually be reading
2714  * the affine expression itself (defined on a parameter domains)
2715  * If the tuple we are reading is named, we assume it's the domain.
2716  * Also, if inside the tuple, the first thing we find is a nested tuple
2717  * or a new identifier, we again assume it's the domain.
2718  * Otherwise, we assume we are reading an affine expression.
2719  */
2720 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2721         __isl_take isl_set *dom, struct vars *v)
2722 {
2723         struct isl_token *tok;
2724
2725         tok = isl_stream_next_token(s);
2726         if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2727                 isl_stream_push_token(s, tok);
2728                 return read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2729         }
2730         if (!tok || tok->type != '[') {
2731                 isl_stream_error(s, tok, "expecting '['");
2732                 goto error;
2733         }
2734         if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2735                 isl_stream_push_token(s, tok);
2736                 dom = read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2737         } else
2738                 isl_stream_push_token(s, tok);
2739
2740         return dom;
2741 error:
2742         if (tok)
2743                 isl_stream_push_token(s, tok);
2744         isl_set_free(dom);
2745         return NULL;
2746 }
2747
2748 /* Read an affine expression from "s".
2749  */
2750 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2751 {
2752         isl_aff *aff;
2753         isl_multi_aff *ma;
2754
2755         ma = isl_stream_read_multi_aff(s);
2756         if (!ma)
2757                 return NULL;
2758         if (isl_multi_aff_dim(ma, isl_dim_out) != 1)
2759                 isl_die(s->ctx, isl_error_invalid,
2760                         "expecting single affine expression",
2761                         goto error);
2762
2763         aff = isl_multi_aff_get_aff(ma, 0);
2764         isl_multi_aff_free(ma);
2765         return aff;
2766 error:
2767         isl_multi_aff_free(ma);
2768         return NULL;
2769 }
2770
2771 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2772  */
2773 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2774         __isl_take isl_set *dom, struct vars *v)
2775 {
2776         isl_pw_aff *pwaff = NULL;
2777
2778         if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2779                 goto error;
2780
2781         if (isl_stream_eat(s, '['))
2782                 goto error;
2783
2784         pwaff = accept_affine(s, isl_set_get_space(dom), v);
2785
2786         if (isl_stream_eat(s, ']'))
2787                 goto error;
2788
2789         dom = read_optional_formula(s, dom, v, 0);
2790         pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2791
2792         return pwaff;
2793 error:
2794         isl_set_free(dom);
2795         isl_pw_aff_free(pwaff);
2796         return NULL;
2797 }
2798
2799 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
2800 {
2801         struct vars *v;
2802         isl_set *dom = NULL;
2803         isl_set *aff_dom;
2804         isl_pw_aff *pa = NULL;
2805         int n;
2806
2807         v = vars_new(s->ctx);
2808         if (!v)
2809                 return NULL;
2810
2811         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2812         if (next_is_tuple(s)) {
2813                 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
2814                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2815                         goto error;
2816         }
2817         if (isl_stream_eat(s, '{'))
2818                 goto error;
2819
2820         n = v->n;
2821         aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2822         pa = read_pw_aff_with_dom(s, aff_dom, v);
2823         vars_drop(v, v->n - n);
2824
2825         while (isl_stream_eat_if_available(s, ';')) {
2826                 isl_pw_aff *pa_i;
2827
2828                 n = v->n;
2829                 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2830                 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
2831                 vars_drop(v, v->n - n);
2832
2833                 pa = isl_pw_aff_union_add(pa, pa_i);
2834         }
2835
2836         if (isl_stream_eat(s, '}'))
2837                 goto error;
2838
2839         vars_free(v);
2840         isl_set_free(dom);
2841         return pa;
2842 error:
2843         vars_free(v);
2844         isl_set_free(dom);
2845         isl_pw_aff_free(pa);
2846         return NULL;
2847 }
2848
2849 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
2850 {
2851         isl_aff *aff;
2852         struct isl_stream *s = isl_stream_new_str(ctx, str);
2853         if (!s)
2854                 return NULL;
2855         aff = isl_stream_read_aff(s);
2856         isl_stream_free(s);
2857         return aff;
2858 }
2859
2860 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
2861 {
2862         isl_pw_aff *pa;
2863         struct isl_stream *s = isl_stream_new_str(ctx, str);
2864         if (!s)
2865                 return NULL;
2866         pa = isl_stream_read_pw_aff(s);
2867         isl_stream_free(s);
2868         return pa;
2869 }
2870
2871 /* Read an isl_pw_multi_aff from "s".
2872  * We currently read a generic object and if it turns out to be a set or
2873  * a map, we convert that to an isl_pw_multi_aff.
2874  * It would be more efficient if we were to construct the isl_pw_multi_aff
2875  * directly.
2876  */
2877 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
2878 {
2879         struct isl_obj obj;
2880
2881         obj = obj_read(s);
2882         if (!obj.v)
2883                 return NULL;
2884
2885         if (obj.type == isl_obj_map)
2886                 return isl_pw_multi_aff_from_map(obj.v);
2887         if (obj.type == isl_obj_set)
2888                 return isl_pw_multi_aff_from_set(obj.v);
2889
2890         obj.type->free(obj.v);
2891         isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2892                 return NULL);
2893 }
2894
2895 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
2896         const char *str)
2897 {
2898         isl_pw_multi_aff *pma;
2899         struct isl_stream *s = isl_stream_new_str(ctx, str);
2900         if (!s)
2901                 return NULL;
2902         pma = isl_stream_read_pw_multi_aff(s);
2903         isl_stream_free(s);
2904         return pma;
2905 }
2906
2907 /* Read an isl_union_pw_multi_aff from "s".
2908  * We currently read a generic object and if it turns out to be a set or
2909  * a map, we convert that to an isl_union_pw_multi_aff.
2910  * It would be more efficient if we were to construct
2911  * the isl_union_pw_multi_aff directly.
2912  */
2913 __isl_give isl_union_pw_multi_aff *isl_stream_read_union_pw_multi_aff(
2914         struct isl_stream *s)
2915 {
2916         struct isl_obj obj;
2917
2918         obj = obj_read(s);
2919         if (!obj.v)
2920                 return NULL;
2921
2922         if (obj.type == isl_obj_map || obj.type == isl_obj_set)
2923                 obj = to_union(s->ctx, obj);
2924         if (obj.type == isl_obj_union_map)
2925                 return isl_union_pw_multi_aff_from_union_map(obj.v);
2926         if (obj.type == isl_obj_union_set)
2927                 return isl_union_pw_multi_aff_from_union_set(obj.v);
2928
2929         obj.type->free(obj.v);
2930         isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2931                 return NULL);
2932 }
2933
2934 /* Read an isl_union_pw_multi_aff from "str".
2935  */
2936 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_read_from_str(
2937         isl_ctx *ctx, const char *str)
2938 {
2939         isl_union_pw_multi_aff *upma;
2940         struct isl_stream *s = isl_stream_new_str(ctx, str);
2941         if (!s)
2942                 return NULL;
2943         upma = isl_stream_read_union_pw_multi_aff(s);
2944         isl_stream_free(s);
2945         return upma;
2946 }
2947
2948 /* Assuming "pa" represents a single affine expression defined on a universe
2949  * domain, extract this affine expression.
2950  */
2951 static __isl_give isl_aff *aff_from_pw_aff(__isl_take isl_pw_aff *pa)
2952 {
2953         isl_aff *aff;
2954
2955         if (!pa)
2956                 return NULL;
2957         if (pa->n != 1)
2958                 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
2959                         "expecting single affine expression",
2960                         goto error);
2961         if (!isl_set_plain_is_universe(pa->p[0].set))
2962                 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
2963                         "expecting universe domain",
2964                         goto error);
2965
2966         aff = isl_aff_copy(pa->p[0].aff);
2967         isl_pw_aff_free(pa);
2968         return aff;
2969 error:
2970         isl_pw_aff_free(pa);
2971         return NULL;
2972 }
2973
2974 /* Read a multi-affine expression from "s".
2975  * If the multi-affine expression has a domain, then then tuple
2976  * representing this domain cannot involve any affine expressions.
2977  * The tuple representing the actual expressions needs to consist
2978  * of only affine expressions.  Moreover, these expressions can
2979  * only depend on parameters and input dimensions and not on other
2980  * output dimensions.
2981  */
2982 __isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s)
2983 {
2984         struct vars *v;
2985         isl_set *dom = NULL;
2986         isl_multi_pw_aff *tuple = NULL;
2987         int dim, i, n;
2988         isl_space *space, *dom_space;
2989         isl_multi_aff *ma = NULL;
2990
2991         v = vars_new(s->ctx);
2992         if (!v)
2993                 return NULL;
2994
2995         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2996         if (next_is_tuple(s)) {
2997                 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
2998                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2999                         goto error;
3000         }
3001         if (!isl_set_plain_is_universe(dom))
3002                 isl_die(s->ctx, isl_error_invalid,
3003                         "expecting universe parameter domain", goto error);
3004         if (isl_stream_eat(s, '{'))
3005                 goto error;
3006
3007         tuple = read_tuple(s, v, 0, 0);
3008         if (!tuple)
3009                 goto error;
3010         if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
3011                 isl_set *set;
3012                 isl_space *space;
3013                 int has_expr;
3014
3015                 has_expr = tuple_has_expr(tuple);
3016                 if (has_expr < 0)
3017                         goto error;
3018                 if (has_expr)
3019                         isl_die(s->ctx, isl_error_invalid,
3020                                 "expecting universe domain", goto error);
3021                 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3022                 set = isl_set_universe(space);
3023                 dom = isl_set_intersect_params(set, dom);
3024                 isl_multi_pw_aff_free(tuple);
3025                 tuple = read_tuple(s, v, 0, 0);
3026                 if (!tuple)
3027                         goto error;
3028         }
3029
3030         if (isl_stream_eat(s, '}'))
3031                 goto error;
3032
3033         n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
3034         dim = isl_set_dim(dom, isl_dim_all);
3035         dom_space = isl_set_get_space(dom);
3036         space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3037         space = isl_space_align_params(space, isl_space_copy(dom_space));
3038         if (!isl_space_is_params(dom_space))
3039                 space = isl_space_map_from_domain_and_range(
3040                                 isl_space_copy(dom_space), space);
3041         isl_space_free(dom_space);
3042         ma = isl_multi_aff_alloc(space);
3043
3044         for (i = 0; i < n; ++i) {
3045                 isl_pw_aff *pa;
3046                 isl_aff *aff;
3047                 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
3048                 aff = aff_from_pw_aff(pa);
3049                 if (!aff)
3050                         goto error;
3051                 if (isl_aff_involves_dims(aff, isl_dim_in, dim, i + 1)) {
3052                         isl_aff_free(aff);
3053                         isl_die(s->ctx, isl_error_invalid,
3054                                 "not an affine expression", goto error);
3055                 }
3056                 aff = isl_aff_drop_dims(aff, isl_dim_in, dim, n);
3057                 space = isl_multi_aff_get_domain_space(ma);
3058                 aff = isl_aff_reset_domain_space(aff, space);
3059                 ma = isl_multi_aff_set_aff(ma, i, aff);
3060         }
3061
3062         isl_multi_pw_aff_free(tuple);
3063         vars_free(v);
3064         isl_set_free(dom);
3065         return ma;
3066 error:
3067         isl_multi_pw_aff_free(tuple);
3068         vars_free(v);
3069         isl_set_free(dom);
3070         isl_multi_aff_free(ma);
3071         return NULL;
3072 }
3073
3074 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
3075         const char *str)
3076 {
3077         isl_multi_aff *maff;
3078         struct isl_stream *s = isl_stream_new_str(ctx, str);
3079         if (!s)
3080                 return NULL;
3081         maff = isl_stream_read_multi_aff(s);
3082         isl_stream_free(s);
3083         return maff;
3084 }
3085
3086 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
3087         struct isl_stream *s)
3088 {
3089         struct isl_obj obj;
3090
3091         obj = obj_read(s);
3092         if (obj.type == isl_obj_pw_qpolynomial) {
3093                 obj.type = isl_obj_union_pw_qpolynomial;
3094                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
3095         }
3096         if (obj.v)
3097                 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
3098                            goto error);
3099
3100         return obj.v;
3101 error:
3102         obj.type->free(obj.v);
3103         return NULL;
3104 }
3105
3106 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
3107         isl_ctx *ctx, const char *str)
3108 {
3109         isl_union_pw_qpolynomial *upwqp;
3110         struct isl_stream *s = isl_stream_new_str(ctx, str);
3111         if (!s)
3112                 return NULL;
3113         upwqp = isl_stream_read_union_pw_qpolynomial(s);
3114         isl_stream_free(s);
3115         return upwqp;
3116 }