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 struct isl_map *read_disjuncts(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_disjuncts(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_disjuncts(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_disjuncts(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_disjuncts(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 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1506 {
1507         if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1508                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1509                            isl_basic_map_dim(bmap, isl_dim_in) + pos;
1510         pos -= isl_basic_map_dim(bmap, isl_dim_out);
1511
1512         if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1513                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1514         pos -= isl_basic_map_dim(bmap, isl_dim_in);
1515
1516         if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1517                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1518                            isl_basic_map_dim(bmap, isl_dim_in) +
1519                            isl_basic_map_dim(bmap, isl_dim_out) + pos;
1520         pos -= isl_basic_map_dim(bmap, isl_dim_div);
1521
1522         if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1523                 return 1 + pos;
1524
1525         return 0;
1526 }
1527
1528 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1529         struct isl_stream *s, __isl_take isl_basic_map *bmap)
1530 {
1531         int j;
1532         struct isl_token *tok;
1533         int type;
1534         int k;
1535         isl_int *c;
1536         unsigned nparam;
1537         unsigned dim;
1538
1539         if (!bmap)
1540                 return NULL;
1541
1542         nparam = isl_basic_map_dim(bmap, isl_dim_param);
1543         dim = isl_basic_map_dim(bmap, isl_dim_out);
1544
1545         tok = isl_stream_next_token(s);
1546         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1547                 isl_stream_error(s, tok, "expecting coefficient");
1548                 if (tok)
1549                         isl_stream_push_token(s, tok);
1550                 goto error;
1551         }
1552         if (!tok->on_new_line) {
1553                 isl_stream_error(s, tok, "coefficient should appear on new line");
1554                 isl_stream_push_token(s, tok);
1555                 goto error;
1556         }
1557
1558         type = isl_int_get_si(tok->u.v);
1559         isl_token_free(tok);
1560
1561         isl_assert(s->ctx, type == 0 || type == 1, goto error);
1562         if (type == 0) {
1563                 k = isl_basic_map_alloc_equality(bmap);
1564                 c = bmap->eq[k];
1565         } else {
1566                 k = isl_basic_map_alloc_inequality(bmap);
1567                 c = bmap->ineq[k];
1568         }
1569         if (k < 0)
1570                 goto error;
1571
1572         for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1573                 int pos;
1574                 tok = isl_stream_next_token(s);
1575                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1576                         isl_stream_error(s, tok, "expecting coefficient");
1577                         if (tok)
1578                                 isl_stream_push_token(s, tok);
1579                         goto error;
1580                 }
1581                 if (tok->on_new_line) {
1582                         isl_stream_error(s, tok,
1583                                 "coefficient should not appear on new line");
1584                         isl_stream_push_token(s, tok);
1585                         goto error;
1586                 }
1587                 pos = polylib_pos_to_isl_pos(bmap, j);
1588                 isl_int_set(c[pos], tok->u.v);
1589                 isl_token_free(tok);
1590         }
1591
1592         return bmap;
1593 error:
1594         isl_basic_map_free(bmap);
1595         return NULL;
1596 }
1597
1598 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s)
1599 {
1600         int i;
1601         struct isl_token *tok;
1602         struct isl_token *tok2;
1603         int n_row, n_col;
1604         int on_new_line;
1605         unsigned in = 0, out, local = 0;
1606         struct isl_basic_map *bmap = NULL;
1607         int nparam = 0;
1608
1609         tok = isl_stream_next_token(s);
1610         if (!tok) {
1611                 isl_stream_error(s, NULL, "unexpected EOF");
1612                 return NULL;
1613         }
1614         tok2 = isl_stream_next_token(s);
1615         if (!tok2) {
1616                 isl_token_free(tok);
1617                 isl_stream_error(s, NULL, "unexpected EOF");
1618                 return NULL;
1619         }
1620         if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1621                 isl_stream_push_token(s, tok2);
1622                 isl_stream_push_token(s, tok);
1623                 isl_stream_error(s, NULL,
1624                                  "expecting constraint matrix dimensions");
1625                 return NULL;
1626         }
1627         n_row = isl_int_get_si(tok->u.v);
1628         n_col = isl_int_get_si(tok2->u.v);
1629         on_new_line = tok2->on_new_line;
1630         isl_token_free(tok2);
1631         isl_token_free(tok);
1632         isl_assert(s->ctx, !on_new_line, return NULL);
1633         isl_assert(s->ctx, n_row >= 0, return NULL);
1634         isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1635         tok = isl_stream_next_token_on_same_line(s);
1636         if (tok) {
1637                 if (tok->type != ISL_TOKEN_VALUE) {
1638                         isl_stream_error(s, tok,
1639                                     "expecting number of output dimensions");
1640                         isl_stream_push_token(s, tok);
1641                         goto error;
1642                 }
1643                 out = isl_int_get_si(tok->u.v);
1644                 isl_token_free(tok);
1645
1646                 tok = isl_stream_next_token_on_same_line(s);
1647                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1648                         isl_stream_error(s, tok,
1649                                     "expecting number of input dimensions");
1650                         if (tok)
1651                                 isl_stream_push_token(s, tok);
1652                         goto error;
1653                 }
1654                 in = isl_int_get_si(tok->u.v);
1655                 isl_token_free(tok);
1656
1657                 tok = isl_stream_next_token_on_same_line(s);
1658                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1659                         isl_stream_error(s, tok,
1660                                     "expecting number of existentials");
1661                         if (tok)
1662                                 isl_stream_push_token(s, tok);
1663                         goto error;
1664                 }
1665                 local = isl_int_get_si(tok->u.v);
1666                 isl_token_free(tok);
1667
1668                 tok = isl_stream_next_token_on_same_line(s);
1669                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1670                         isl_stream_error(s, tok,
1671                                     "expecting number of parameters");
1672                         if (tok)
1673                                 isl_stream_push_token(s, tok);
1674                         goto error;
1675                 }
1676                 nparam = isl_int_get_si(tok->u.v);
1677                 isl_token_free(tok);
1678                 if (n_col != 1 + out + in + local + nparam + 1) {
1679                         isl_stream_error(s, NULL,
1680                                     "dimensions don't match");
1681                         goto error;
1682                 }
1683         } else
1684                 out = n_col - 2 - nparam;
1685         bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1686         if (!bmap)
1687                 return NULL;
1688
1689         for (i = 0; i < local; ++i) {
1690                 int k = isl_basic_map_alloc_div(bmap);
1691                 if (k < 0)
1692                         goto error;
1693                 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1694         }
1695
1696         for (i = 0; i < n_row; ++i)
1697                 bmap = basic_map_read_polylib_constraint(s, bmap);
1698
1699         tok = isl_stream_next_token_on_same_line(s);
1700         if (tok) {
1701                 isl_stream_error(s, tok, "unexpected extra token on line");
1702                 isl_stream_push_token(s, tok);
1703                 goto error;
1704         }
1705
1706         bmap = isl_basic_map_simplify(bmap);
1707         bmap = isl_basic_map_finalize(bmap);
1708         return bmap;
1709 error:
1710         isl_basic_map_free(bmap);
1711         return NULL;
1712 }
1713
1714 static struct isl_map *map_read_polylib(struct isl_stream *s)
1715 {
1716         struct isl_token *tok;
1717         struct isl_token *tok2;
1718         int i, n;
1719         struct isl_map *map;
1720
1721         tok = isl_stream_next_token(s);
1722         if (!tok) {
1723                 isl_stream_error(s, NULL, "unexpected EOF");
1724                 return NULL;
1725         }
1726         tok2 = isl_stream_next_token_on_same_line(s);
1727         if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1728                 isl_stream_push_token(s, tok2);
1729                 isl_stream_push_token(s, tok);
1730                 return isl_map_from_basic_map(basic_map_read_polylib(s));
1731         }
1732         if (tok2) {
1733                 isl_stream_error(s, tok2, "unexpected token");
1734                 isl_stream_push_token(s, tok2);
1735                 isl_stream_push_token(s, tok);
1736                 return NULL;
1737         }
1738         n = isl_int_get_si(tok->u.v);
1739         isl_token_free(tok);
1740
1741         isl_assert(s->ctx, n >= 1, return NULL);
1742
1743         map = isl_map_from_basic_map(basic_map_read_polylib(s));
1744
1745         for (i = 1; map && i < n; ++i)
1746                 map = isl_map_union(map,
1747                         isl_map_from_basic_map(basic_map_read_polylib(s)));
1748
1749         return map;
1750 }
1751
1752 static int optional_power(struct isl_stream *s)
1753 {
1754         int pow;
1755         struct isl_token *tok;
1756
1757         tok = isl_stream_next_token(s);
1758         if (!tok)
1759                 return 1;
1760         if (tok->type != '^') {
1761                 isl_stream_push_token(s, tok);
1762                 return 1;
1763         }
1764         isl_token_free(tok);
1765         tok = isl_stream_next_token(s);
1766         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1767                 isl_stream_error(s, tok, "expecting exponent");
1768                 if (tok)
1769                         isl_stream_push_token(s, tok);
1770                 return 1;
1771         }
1772         pow = isl_int_get_si(tok->u.v);
1773         isl_token_free(tok);
1774         return pow;
1775 }
1776
1777 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1778         __isl_keep isl_map *map, struct vars *v);
1779
1780 static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s,
1781         __isl_keep isl_map *map, struct vars *v)
1782 {
1783         isl_pw_qpolynomial *pwqp;
1784         struct isl_token *tok;
1785
1786         tok = next_token(s);
1787         if (!tok) {
1788                 isl_stream_error(s, NULL, "unexpected EOF");
1789                 return NULL;
1790         }
1791         if (tok->type == '(') {
1792                 int pow;
1793
1794                 isl_token_free(tok);
1795                 pwqp = read_term(s, map, v);
1796                 if (!pwqp)
1797                         return NULL;
1798                 if (isl_stream_eat(s, ')'))
1799                         goto error;
1800                 pow = optional_power(s);
1801                 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1802         } else if (tok->type == ISL_TOKEN_VALUE) {
1803                 struct isl_token *tok2;
1804                 isl_qpolynomial *qp;
1805
1806                 tok2 = isl_stream_next_token(s);
1807                 if (tok2 && tok2->type == '/') {
1808                         isl_token_free(tok2);
1809                         tok2 = next_token(s);
1810                         if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1811                                 isl_stream_error(s, tok2, "expected denominator");
1812                                 isl_token_free(tok);
1813                                 isl_token_free(tok2);
1814                                 return NULL;
1815                         }
1816                         qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
1817                                                     tok->u.v, tok2->u.v);
1818                         isl_token_free(tok2);
1819                 } else {
1820                         isl_stream_push_token(s, tok2);
1821                         qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
1822                                                 tok->u.v);
1823                 }
1824                 isl_token_free(tok);
1825                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1826         } else if (tok->type == ISL_TOKEN_INFTY) {
1827                 isl_qpolynomial *qp;
1828                 isl_token_free(tok);
1829                 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
1830                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1831         } else if (tok->type == ISL_TOKEN_NAN) {
1832                 isl_qpolynomial *qp;
1833                 isl_token_free(tok);
1834                 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
1835                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1836         } else if (tok->type == ISL_TOKEN_IDENT) {
1837                 int n = v->n;
1838                 int pos = vars_pos(v, tok->u.s, -1);
1839                 int pow;
1840                 isl_qpolynomial *qp;
1841                 if (pos < 0) {
1842                         isl_token_free(tok);
1843                         return NULL;
1844                 }
1845                 if (pos >= n) {
1846                         vars_drop(v, v->n - n);
1847                         isl_stream_error(s, tok, "unknown identifier");
1848                         isl_token_free(tok);
1849                         return NULL;
1850                 }
1851                 isl_token_free(tok);
1852                 pow = optional_power(s);
1853                 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
1854                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1855         } else if (is_start_of_div(tok)) {
1856                 isl_pw_aff *pwaff;
1857                 int pow;
1858
1859                 isl_stream_push_token(s, tok);
1860                 pwaff = accept_div(s, isl_map_get_space(map), v);
1861                 pow = optional_power(s);
1862                 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
1863                 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1864         } else if (tok->type == '-') {
1865                 isl_token_free(tok);
1866                 pwqp = read_factor(s, map, v);
1867                 pwqp = isl_pw_qpolynomial_neg(pwqp);
1868         } else {
1869                 isl_stream_error(s, tok, "unexpected isl_token");
1870                 isl_stream_push_token(s, tok);
1871                 return NULL;
1872         }
1873
1874         if (isl_stream_eat_if_available(s, '*') ||
1875             isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1876                 isl_pw_qpolynomial *pwqp2;
1877
1878                 pwqp2 = read_factor(s, map, v);
1879                 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
1880         }
1881
1882         return pwqp;
1883 error:
1884         isl_pw_qpolynomial_free(pwqp);
1885         return NULL;
1886 }
1887
1888 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1889         __isl_keep isl_map *map, struct vars *v)
1890 {
1891         struct isl_token *tok;
1892         isl_pw_qpolynomial *pwqp;
1893
1894         pwqp = read_factor(s, map, v);
1895
1896         for (;;) {
1897                 tok = next_token(s);
1898                 if (!tok)
1899                         return pwqp;
1900
1901                 if (tok->type == '+') {
1902                         isl_pw_qpolynomial *pwqp2;
1903
1904                         isl_token_free(tok);
1905                         pwqp2 = read_factor(s, map, v);
1906                         pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1907                 } else if (tok->type == '-') {
1908                         isl_pw_qpolynomial *pwqp2;
1909
1910                         isl_token_free(tok);
1911                         pwqp2 = read_factor(s, map, v);
1912                         pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
1913                 } else if (tok->type == ISL_TOKEN_VALUE &&
1914                             isl_int_is_neg(tok->u.v)) {
1915                         isl_pw_qpolynomial *pwqp2;
1916
1917                         isl_stream_push_token(s, tok);
1918                         pwqp2 = read_factor(s, map, v);
1919                         pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1920                 } else {
1921                         isl_stream_push_token(s, tok);
1922                         break;
1923                 }
1924         }
1925
1926         return pwqp;
1927 }
1928
1929 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1930         __isl_take isl_map *map, struct vars *v, int rational)
1931 {
1932         struct isl_token *tok;
1933
1934         tok = isl_stream_next_token(s);
1935         if (!tok) {
1936                 isl_stream_error(s, NULL, "unexpected EOF");
1937                 goto error;
1938         }
1939         if (tok->type == ':' ||
1940             (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
1941                 isl_token_free(tok);
1942                 map = read_disjuncts(s, v, map, rational);
1943         } else
1944                 isl_stream_push_token(s, tok);
1945
1946         return map;
1947 error:
1948         isl_map_free(map);
1949         return NULL;
1950 }
1951
1952 static struct isl_obj obj_read_poly(struct isl_stream *s,
1953         __isl_take isl_map *map, struct vars *v, int n)
1954 {
1955         struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1956         isl_pw_qpolynomial *pwqp;
1957         struct isl_set *set;
1958
1959         pwqp = read_term(s, map, v);
1960         map = read_optional_disjuncts(s, map, v, 0);
1961         set = isl_map_range(map);
1962
1963         pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
1964
1965         vars_drop(v, v->n - n);
1966
1967         obj.v = pwqp;
1968         return obj;
1969 }
1970
1971 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1972         __isl_take isl_set *set, struct vars *v, int n)
1973 {
1974         struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1975         isl_pw_qpolynomial *pwqp;
1976         isl_pw_qpolynomial_fold *pwf = NULL;
1977
1978         if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1979                 return obj_read_poly(s, set, v, n);
1980
1981         if (isl_stream_eat(s, '('))
1982                 goto error;
1983
1984         pwqp = read_term(s, set, v);
1985         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
1986
1987         while (isl_stream_eat_if_available(s, ',')) {
1988                 isl_pw_qpolynomial_fold *pwf_i;
1989                 pwqp = read_term(s, set, v);
1990                 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
1991                                                                         pwqp);
1992                 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
1993         }
1994
1995         if (isl_stream_eat(s, ')'))
1996                 goto error;
1997
1998         set = read_optional_disjuncts(s, set, v, 0);
1999         pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
2000
2001         vars_drop(v, v->n - n);
2002
2003         obj.v = pwf;
2004         return obj;
2005 error:
2006         isl_set_free(set);
2007         isl_pw_qpolynomial_fold_free(pwf);
2008         obj.type = isl_obj_none;
2009         return obj;
2010 }
2011
2012 static int is_rational(struct isl_stream *s)
2013 {
2014         struct isl_token *tok;
2015
2016         tok = isl_stream_next_token(s);
2017         if (!tok)
2018                 return 0;
2019         if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
2020                 isl_token_free(tok);
2021                 isl_stream_eat(s, ':');
2022                 return 1;
2023         }
2024
2025         isl_stream_push_token(s, tok);
2026
2027         return 0;
2028 }
2029
2030 static struct isl_obj obj_read_body(struct isl_stream *s,
2031         __isl_take isl_map *map, struct vars *v)
2032 {
2033         struct isl_token *tok;
2034         struct isl_obj obj = { isl_obj_set, NULL };
2035         int n = v->n;
2036         int rational;
2037
2038         rational = is_rational(s);
2039         if (rational)
2040                 map = isl_map_set_rational(map);
2041
2042         if (isl_stream_next_token_is(s, ':')) {
2043                 obj.type = isl_obj_set;
2044                 obj.v = read_optional_disjuncts(s, map, v, rational);
2045                 return obj;
2046         }
2047
2048         if (!next_is_tuple(s))
2049                 return obj_read_poly_or_fold(s, map, v, n);
2050
2051         map = read_map_tuple(s, map, isl_dim_in, v, rational, 0);
2052         if (!map)
2053                 goto error;
2054         tok = isl_stream_next_token(s);
2055         if (!tok)
2056                 goto error;
2057         if (tok->type == ISL_TOKEN_TO) {
2058                 obj.type = isl_obj_map;
2059                 isl_token_free(tok);
2060                 if (!next_is_tuple(s)) {
2061                         isl_set *set = isl_map_domain(map);
2062                         return obj_read_poly_or_fold(s, set, v, n);
2063                 }
2064                 map = read_map_tuple(s, map, isl_dim_out, v, rational, 0);
2065                 if (!map)
2066                         goto error;
2067         } else {
2068                 map = isl_map_domain(map);
2069                 isl_stream_push_token(s, tok);
2070         }
2071
2072         map = read_optional_disjuncts(s, map, v, rational);
2073
2074         vars_drop(v, v->n - n);
2075
2076         obj.v = map;
2077         return obj;
2078 error:
2079         isl_map_free(map);
2080         obj.type = isl_obj_none;
2081         return obj;
2082 }
2083
2084 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2085 {
2086         if (obj.type == isl_obj_map) {
2087                 obj.v = isl_union_map_from_map(obj.v);
2088                 obj.type = isl_obj_union_map;
2089         } else if (obj.type == isl_obj_set) {
2090                 obj.v = isl_union_set_from_set(obj.v);
2091                 obj.type = isl_obj_union_set;
2092         } else if (obj.type == isl_obj_pw_qpolynomial) {
2093                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2094                 obj.type = isl_obj_union_pw_qpolynomial;
2095         } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
2096                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
2097                 obj.type = isl_obj_union_pw_qpolynomial_fold;
2098         } else
2099                 isl_assert(ctx, 0, goto error);
2100         return obj;
2101 error:
2102         obj.type->free(obj.v);
2103         obj.type = isl_obj_none;
2104         return obj;
2105 }
2106
2107 static struct isl_obj obj_add(struct isl_ctx *ctx,
2108         struct isl_obj obj1, struct isl_obj obj2)
2109 {
2110         if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
2111                 obj1 = to_union(ctx, obj1);
2112         if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
2113                 obj2 = to_union(ctx, obj2);
2114         if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
2115                 obj1 = to_union(ctx, obj1);
2116         if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
2117                 obj2 = to_union(ctx, obj2);
2118         if (obj1.type == isl_obj_pw_qpolynomial &&
2119             obj2.type == isl_obj_union_pw_qpolynomial)
2120                 obj1 = to_union(ctx, obj1);
2121         if (obj1.type == isl_obj_union_pw_qpolynomial &&
2122             obj2.type == isl_obj_pw_qpolynomial)
2123                 obj2 = to_union(ctx, obj2);
2124         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2125             obj2.type == isl_obj_union_pw_qpolynomial_fold)
2126                 obj1 = to_union(ctx, obj1);
2127         if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2128             obj2.type == isl_obj_pw_qpolynomial_fold)
2129                 obj2 = to_union(ctx, obj2);
2130         isl_assert(ctx, obj1.type == obj2.type, goto error);
2131         if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
2132                 obj1 = to_union(ctx, obj1);
2133                 obj2 = to_union(ctx, obj2);
2134         }
2135         if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
2136                 obj1 = to_union(ctx, obj1);
2137                 obj2 = to_union(ctx, obj2);
2138         }
2139         if (obj1.type == isl_obj_pw_qpolynomial &&
2140             !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
2141                 obj1 = to_union(ctx, obj1);
2142                 obj2 = to_union(ctx, obj2);
2143         }
2144         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2145             !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
2146                 obj1 = to_union(ctx, obj1);
2147                 obj2 = to_union(ctx, obj2);
2148         }
2149         obj1.v = obj1.type->add(obj1.v, obj2.v);
2150         return obj1;
2151 error:
2152         obj1.type->free(obj1.v);
2153         obj2.type->free(obj2.v);
2154         obj1.type = isl_obj_none;
2155         obj1.v = NULL;
2156         return obj1;
2157 }
2158
2159 static struct isl_obj obj_read(struct isl_stream *s)
2160 {
2161         isl_map *map = NULL;
2162         struct isl_token *tok;
2163         struct vars *v = NULL;
2164         struct isl_obj obj = { isl_obj_set, NULL };
2165
2166         tok = next_token(s);
2167         if (!tok) {
2168                 isl_stream_error(s, NULL, "unexpected EOF");
2169                 goto error;
2170         }
2171         if (tok->type == ISL_TOKEN_VALUE) {
2172                 struct isl_token *tok2;
2173                 struct isl_map *map;
2174
2175                 tok2 = isl_stream_next_token(s);
2176                 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
2177                     isl_int_is_neg(tok2->u.v)) {
2178                         if (tok2)
2179                                 isl_stream_push_token(s, tok2);
2180                         obj.type = isl_obj_int;
2181                         obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
2182                         isl_token_free(tok);
2183                         return obj;
2184                 }
2185                 isl_stream_push_token(s, tok2);
2186                 isl_stream_push_token(s, tok);
2187                 map = map_read_polylib(s);
2188                 if (!map)
2189                         goto error;
2190                 if (isl_map_may_be_set(map))
2191                         obj.v = isl_map_range(map);
2192                 else {
2193                         obj.type = isl_obj_map;
2194                         obj.v = map;
2195                 }
2196                 return obj;
2197         }
2198         v = vars_new(s->ctx);
2199         if (!v) {
2200                 isl_stream_push_token(s, tok);
2201                 goto error;
2202         }
2203         map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
2204         if (tok->type == '[') {
2205                 isl_stream_push_token(s, tok);
2206                 map = read_map_tuple(s, map, isl_dim_param, v, 0, 0);
2207                 if (!map)
2208                         goto error;
2209                 tok = isl_stream_next_token(s);
2210                 if (!tok || tok->type != ISL_TOKEN_TO) {
2211                         isl_stream_error(s, tok, "expecting '->'");
2212                         if (tok)
2213                                 isl_stream_push_token(s, tok);
2214                         goto error;
2215                 }
2216                 isl_token_free(tok);
2217                 tok = isl_stream_next_token(s);
2218         }
2219         if (!tok || tok->type != '{') {
2220                 isl_stream_error(s, tok, "expecting '{'");
2221                 if (tok)
2222                         isl_stream_push_token(s, tok);
2223                 goto error;
2224         }
2225         isl_token_free(tok);
2226
2227         tok = isl_stream_next_token(s);
2228         if (!tok)
2229                 ;
2230         else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
2231                 isl_token_free(tok);
2232                 if (isl_stream_eat(s, '='))
2233                         goto error;
2234                 map = read_map_tuple(s, map, isl_dim_param, v, 0, 1);
2235                 if (!map)
2236                         goto error;
2237         } else if (tok->type == '}') {
2238                 obj.type = isl_obj_union_set;
2239                 obj.v = isl_union_set_empty(isl_map_get_space(map));
2240                 isl_token_free(tok);
2241                 goto done;
2242         } else
2243                 isl_stream_push_token(s, tok);
2244
2245         for (;;) {
2246                 struct isl_obj o;
2247                 tok = NULL;
2248                 o = obj_read_body(s, isl_map_copy(map), v);
2249                 if (o.type == isl_obj_none || !o.v)
2250                         goto error;
2251                 if (!obj.v)
2252                         obj = o;
2253                 else {
2254                         obj = obj_add(s->ctx, obj, o);
2255                         if (obj.type == isl_obj_none || !obj.v)
2256                                 goto error;
2257                 }
2258                 tok = isl_stream_next_token(s);
2259                 if (!tok || tok->type != ';')
2260                         break;
2261                 isl_token_free(tok);
2262                 if (isl_stream_next_token_is(s, '}')) {
2263                         tok = isl_stream_next_token(s);
2264                         break;
2265                 }
2266         }
2267
2268         if (tok && tok->type == '}') {
2269                 isl_token_free(tok);
2270         } else {
2271                 isl_stream_error(s, tok, "unexpected isl_token");
2272                 if (tok)
2273                         isl_token_free(tok);
2274                 goto error;
2275         }
2276 done:
2277         vars_free(v);
2278         isl_map_free(map);
2279
2280         return obj;
2281 error:
2282         isl_map_free(map);
2283         obj.type->free(obj.v);
2284         if (v)
2285                 vars_free(v);
2286         obj.v = NULL;
2287         return obj;
2288 }
2289
2290 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
2291 {
2292         return obj_read(s);
2293 }
2294
2295 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
2296 {
2297         struct isl_obj obj;
2298
2299         obj = obj_read(s);
2300         if (obj.v)
2301                 isl_assert(s->ctx, obj.type == isl_obj_map ||
2302                                    obj.type == isl_obj_set, goto error);
2303
2304         if (obj.type == isl_obj_set)
2305                 obj.v = isl_map_from_range(obj.v);
2306
2307         return obj.v;
2308 error:
2309         obj.type->free(obj.v);
2310         return NULL;
2311 }
2312
2313 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2314 {
2315         struct isl_obj obj;
2316
2317         obj = obj_read(s);
2318         if (obj.v) {
2319                 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2320                         obj.v = isl_map_range(obj.v);
2321                         obj.type = isl_obj_set;
2322                 }
2323                 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2324         }
2325
2326         return obj.v;
2327 error:
2328         obj.type->free(obj.v);
2329         return NULL;
2330 }
2331
2332 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2333 {
2334         struct isl_obj obj;
2335
2336         obj = obj_read(s);
2337         if (obj.type == isl_obj_map) {
2338                 obj.type = isl_obj_union_map;
2339                 obj.v = isl_union_map_from_map(obj.v);
2340         }
2341         if (obj.type == isl_obj_set) {
2342                 obj.type = isl_obj_union_set;
2343                 obj.v = isl_union_set_from_set(obj.v);
2344         }
2345         if (obj.v && obj.type == isl_obj_union_set &&
2346             isl_union_set_is_empty(obj.v))
2347                 obj.type = isl_obj_union_map;
2348         if (obj.v && obj.type != isl_obj_union_map)
2349                 isl_die(s->ctx, isl_error_invalid, "invalid input", goto error);
2350
2351         return obj.v;
2352 error:
2353         obj.type->free(obj.v);
2354         return NULL;
2355 }
2356
2357 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2358 {
2359         struct isl_obj obj;
2360
2361         obj = obj_read(s);
2362         if (obj.type == isl_obj_set) {
2363                 obj.type = isl_obj_union_set;
2364                 obj.v = isl_union_set_from_set(obj.v);
2365         }
2366         if (obj.v)
2367                 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2368
2369         return obj.v;
2370 error:
2371         obj.type->free(obj.v);
2372         return NULL;
2373 }
2374
2375 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2376 {
2377         struct isl_obj obj;
2378         struct isl_map *map;
2379         struct isl_basic_map *bmap;
2380
2381         obj = obj_read(s);
2382         map = obj.v;
2383         if (!map)
2384                 return NULL;
2385
2386         isl_assert(map->ctx, map->n <= 1, goto error);
2387
2388         if (map->n == 0)
2389                 bmap = isl_basic_map_empty_like_map(map);
2390         else
2391                 bmap = isl_basic_map_copy(map->p[0]);
2392
2393         isl_map_free(map);
2394
2395         return bmap;
2396 error:
2397         isl_map_free(map);
2398         return NULL;
2399 }
2400
2401 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2402 {
2403         isl_basic_map *bmap;
2404         bmap = basic_map_read(s);
2405         if (!bmap)
2406                 return NULL;
2407         if (!isl_basic_map_may_be_set(bmap))
2408                 isl_die(s->ctx, isl_error_invalid,
2409                         "input is not a set", goto error);
2410         return isl_basic_map_range(bmap);
2411 error:
2412         isl_basic_map_free(bmap);
2413         return NULL;
2414 }
2415
2416 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2417         FILE *input)
2418 {
2419         struct isl_basic_map *bmap;
2420         struct isl_stream *s = isl_stream_new_file(ctx, input);
2421         if (!s)
2422                 return NULL;
2423         bmap = basic_map_read(s);
2424         isl_stream_free(s);
2425         return bmap;
2426 }
2427
2428 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2429         FILE *input)
2430 {
2431         isl_basic_set *bset;
2432         struct isl_stream *s = isl_stream_new_file(ctx, input);
2433         if (!s)
2434                 return NULL;
2435         bset = basic_set_read(s);
2436         isl_stream_free(s);
2437         return bset;
2438 }
2439
2440 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2441         const char *str)
2442 {
2443         struct isl_basic_map *bmap;
2444         struct isl_stream *s = isl_stream_new_str(ctx, str);
2445         if (!s)
2446                 return NULL;
2447         bmap = basic_map_read(s);
2448         isl_stream_free(s);
2449         return bmap;
2450 }
2451
2452 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2453         const char *str)
2454 {
2455         isl_basic_set *bset;
2456         struct isl_stream *s = isl_stream_new_str(ctx, str);
2457         if (!s)
2458                 return NULL;
2459         bset = basic_set_read(s);
2460         isl_stream_free(s);
2461         return bset;
2462 }
2463
2464 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2465         FILE *input)
2466 {
2467         struct isl_map *map;
2468         struct isl_stream *s = isl_stream_new_file(ctx, input);
2469         if (!s)
2470                 return NULL;
2471         map = isl_stream_read_map(s);
2472         isl_stream_free(s);
2473         return map;
2474 }
2475
2476 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2477         const char *str)
2478 {
2479         struct isl_map *map;
2480         struct isl_stream *s = isl_stream_new_str(ctx, str);
2481         if (!s)
2482                 return NULL;
2483         map = isl_stream_read_map(s);
2484         isl_stream_free(s);
2485         return map;
2486 }
2487
2488 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2489         FILE *input)
2490 {
2491         isl_set *set;
2492         struct isl_stream *s = isl_stream_new_file(ctx, input);
2493         if (!s)
2494                 return NULL;
2495         set = isl_stream_read_set(s);
2496         isl_stream_free(s);
2497         return set;
2498 }
2499
2500 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2501         const char *str)
2502 {
2503         isl_set *set;
2504         struct isl_stream *s = isl_stream_new_str(ctx, str);
2505         if (!s)
2506                 return NULL;
2507         set = isl_stream_read_set(s);
2508         isl_stream_free(s);
2509         return set;
2510 }
2511
2512 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2513         FILE *input)
2514 {
2515         isl_union_map *umap;
2516         struct isl_stream *s = isl_stream_new_file(ctx, input);
2517         if (!s)
2518                 return NULL;
2519         umap = isl_stream_read_union_map(s);
2520         isl_stream_free(s);
2521         return umap;
2522 }
2523
2524 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2525                 const char *str)
2526 {
2527         isl_union_map *umap;
2528         struct isl_stream *s = isl_stream_new_str(ctx, str);
2529         if (!s)
2530                 return NULL;
2531         umap = isl_stream_read_union_map(s);
2532         isl_stream_free(s);
2533         return umap;
2534 }
2535
2536 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2537         FILE *input)
2538 {
2539         isl_union_set *uset;
2540         struct isl_stream *s = isl_stream_new_file(ctx, input);
2541         if (!s)
2542                 return NULL;
2543         uset = isl_stream_read_union_set(s);
2544         isl_stream_free(s);
2545         return uset;
2546 }
2547
2548 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2549                 const char *str)
2550 {
2551         isl_union_set *uset;
2552         struct isl_stream *s = isl_stream_new_str(ctx, str);
2553         if (!s)
2554                 return NULL;
2555         uset = isl_stream_read_union_set(s);
2556         isl_stream_free(s);
2557         return uset;
2558 }
2559
2560 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2561 {
2562         struct isl_vec *vec = NULL;
2563         struct isl_token *tok;
2564         unsigned size;
2565         int j;
2566
2567         tok = isl_stream_next_token(s);
2568         if (!tok || tok->type != ISL_TOKEN_VALUE) {
2569                 isl_stream_error(s, tok, "expecting vector length");
2570                 goto error;
2571         }
2572
2573         size = isl_int_get_si(tok->u.v);
2574         isl_token_free(tok);
2575
2576         vec = isl_vec_alloc(s->ctx, size);
2577
2578         for (j = 0; j < size; ++j) {
2579                 tok = isl_stream_next_token(s);
2580                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2581                         isl_stream_error(s, tok, "expecting constant value");
2582                         goto error;
2583                 }
2584                 isl_int_set(vec->el[j], tok->u.v);
2585                 isl_token_free(tok);
2586         }
2587
2588         return vec;
2589 error:
2590         isl_token_free(tok);
2591         isl_vec_free(vec);
2592         return NULL;
2593 }
2594
2595 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2596 {
2597         return isl_vec_read_polylib(s);
2598 }
2599
2600 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2601 {
2602         isl_vec *v;
2603         struct isl_stream *s = isl_stream_new_file(ctx, input);
2604         if (!s)
2605                 return NULL;
2606         v = vec_read(s);
2607         isl_stream_free(s);
2608         return v;
2609 }
2610
2611 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2612         struct isl_stream *s)
2613 {
2614         struct isl_obj obj;
2615
2616         obj = obj_read(s);
2617         if (obj.v)
2618                 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2619                            goto error);
2620
2621         return obj.v;
2622 error:
2623         obj.type->free(obj.v);
2624         return NULL;
2625 }
2626
2627 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2628                 const char *str)
2629 {
2630         isl_pw_qpolynomial *pwqp;
2631         struct isl_stream *s = isl_stream_new_str(ctx, str);
2632         if (!s)
2633                 return NULL;
2634         pwqp = isl_stream_read_pw_qpolynomial(s);
2635         isl_stream_free(s);
2636         return pwqp;
2637 }
2638
2639 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2640                 FILE *input)
2641 {
2642         isl_pw_qpolynomial *pwqp;
2643         struct isl_stream *s = isl_stream_new_file(ctx, input);
2644         if (!s)
2645                 return NULL;
2646         pwqp = isl_stream_read_pw_qpolynomial(s);
2647         isl_stream_free(s);
2648         return pwqp;
2649 }
2650
2651 /* Is the next token an identifer not in "v"?
2652  */
2653 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2654 {
2655         int n = v->n;
2656         int fresh;
2657         struct isl_token *tok;
2658
2659         tok = isl_stream_next_token(s);
2660         if (!tok)
2661                 return 0;
2662         fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2663         isl_stream_push_token(s, tok);
2664
2665         vars_drop(v, v->n - n);
2666
2667         return fresh;
2668 }
2669
2670 /* First read the domain of the affine expression, which may be
2671  * a parameter space or a set.
2672  * The tricky part is that we don't know if the domain is a set or not,
2673  * so when we are trying to read the domain, we may actually be reading
2674  * the affine expression itself (defined on a parameter domains)
2675  * If the tuple we are reading is named, we assume it's the domain.
2676  * Also, if inside the tuple, the first thing we find is a nested tuple
2677  * or a new identifier, we again assume it's the domain.
2678  * Otherwise, we assume we are reading an affine expression.
2679  */
2680 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2681         __isl_take isl_set *dom, struct vars *v)
2682 {
2683         struct isl_token *tok;
2684
2685         tok = isl_stream_next_token(s);
2686         if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2687                 isl_stream_push_token(s, tok);
2688                 return read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2689         }
2690         if (!tok || tok->type != '[') {
2691                 isl_stream_error(s, tok, "expecting '['");
2692                 goto error;
2693         }
2694         if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2695                 isl_stream_push_token(s, tok);
2696                 dom = read_map_tuple(s, dom, isl_dim_set, v, 1, 0);
2697         } else
2698                 isl_stream_push_token(s, tok);
2699
2700         return dom;
2701 error:
2702         if (tok)
2703                 isl_stream_push_token(s, tok);
2704         isl_set_free(dom);
2705         return NULL;
2706 }
2707
2708 /* Read an affine expression from "s".
2709  */
2710 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2711 {
2712         isl_aff *aff;
2713         isl_multi_aff *ma;
2714
2715         ma = isl_stream_read_multi_aff(s);
2716         if (!ma)
2717                 return NULL;
2718         if (isl_multi_aff_dim(ma, isl_dim_out) != 1)
2719                 isl_die(s->ctx, isl_error_invalid,
2720                         "expecting single affine expression",
2721                         goto error);
2722
2723         aff = isl_multi_aff_get_aff(ma, 0);
2724         isl_multi_aff_free(ma);
2725         return aff;
2726 error:
2727         isl_multi_aff_free(ma);
2728         return NULL;
2729 }
2730
2731 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2732  */
2733 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2734         __isl_take isl_set *dom, struct vars *v)
2735 {
2736         isl_pw_aff *pwaff = NULL;
2737
2738         if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2739                 goto error;
2740
2741         if (isl_stream_eat(s, '['))
2742                 goto error;
2743
2744         pwaff = accept_affine(s, isl_set_get_space(dom), v);
2745
2746         if (isl_stream_eat(s, ']'))
2747                 goto error;
2748
2749         dom = read_optional_disjuncts(s, dom, v, 0);
2750         pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2751
2752         return pwaff;
2753 error:
2754         isl_set_free(dom);
2755         isl_pw_aff_free(pwaff);
2756         return NULL;
2757 }
2758
2759 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
2760 {
2761         struct vars *v;
2762         isl_set *dom = NULL;
2763         isl_set *aff_dom;
2764         isl_pw_aff *pa = NULL;
2765         int n;
2766
2767         v = vars_new(s->ctx);
2768         if (!v)
2769                 return NULL;
2770
2771         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2772         if (next_is_tuple(s)) {
2773                 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
2774                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2775                         goto error;
2776         }
2777         if (isl_stream_eat(s, '{'))
2778                 goto error;
2779
2780         n = v->n;
2781         aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2782         pa = read_pw_aff_with_dom(s, aff_dom, v);
2783         vars_drop(v, v->n - n);
2784
2785         while (isl_stream_eat_if_available(s, ';')) {
2786                 isl_pw_aff *pa_i;
2787
2788                 n = v->n;
2789                 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2790                 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
2791                 vars_drop(v, v->n - n);
2792
2793                 pa = isl_pw_aff_union_add(pa, pa_i);
2794         }
2795
2796         if (isl_stream_eat(s, '}'))
2797                 goto error;
2798
2799         vars_free(v);
2800         isl_set_free(dom);
2801         return pa;
2802 error:
2803         vars_free(v);
2804         isl_set_free(dom);
2805         isl_pw_aff_free(pa);
2806         return NULL;
2807 }
2808
2809 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
2810 {
2811         isl_aff *aff;
2812         struct isl_stream *s = isl_stream_new_str(ctx, str);
2813         if (!s)
2814                 return NULL;
2815         aff = isl_stream_read_aff(s);
2816         isl_stream_free(s);
2817         return aff;
2818 }
2819
2820 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
2821 {
2822         isl_pw_aff *pa;
2823         struct isl_stream *s = isl_stream_new_str(ctx, str);
2824         if (!s)
2825                 return NULL;
2826         pa = isl_stream_read_pw_aff(s);
2827         isl_stream_free(s);
2828         return pa;
2829 }
2830
2831 /* Read an isl_pw_multi_aff from "s".
2832  * We currently read a generic object and if it turns out to be a set or
2833  * a map, we convert that to an isl_pw_multi_aff.
2834  * It would be more efficient if we were to construct the isl_pw_multi_aff
2835  * directly.
2836  */
2837 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
2838 {
2839         struct isl_obj obj;
2840
2841         obj = obj_read(s);
2842         if (!obj.v)
2843                 return NULL;
2844
2845         if (obj.type == isl_obj_map)
2846                 return isl_pw_multi_aff_from_map(obj.v);
2847         if (obj.type == isl_obj_set)
2848                 return isl_pw_multi_aff_from_set(obj.v);
2849
2850         obj.type->free(obj.v);
2851         isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2852                 return NULL);
2853 }
2854
2855 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
2856         const char *str)
2857 {
2858         isl_pw_multi_aff *pma;
2859         struct isl_stream *s = isl_stream_new_str(ctx, str);
2860         if (!s)
2861                 return NULL;
2862         pma = isl_stream_read_pw_multi_aff(s);
2863         isl_stream_free(s);
2864         return pma;
2865 }
2866
2867 /* Read an isl_union_pw_multi_aff from "s".
2868  * We currently read a generic object and if it turns out to be a set or
2869  * a map, we convert that to an isl_union_pw_multi_aff.
2870  * It would be more efficient if we were to construct
2871  * the isl_union_pw_multi_aff directly.
2872  */
2873 __isl_give isl_union_pw_multi_aff *isl_stream_read_union_pw_multi_aff(
2874         struct isl_stream *s)
2875 {
2876         struct isl_obj obj;
2877
2878         obj = obj_read(s);
2879         if (!obj.v)
2880                 return NULL;
2881
2882         if (obj.type == isl_obj_map || obj.type == isl_obj_set)
2883                 obj = to_union(s->ctx, obj);
2884         if (obj.type == isl_obj_union_map)
2885                 return isl_union_pw_multi_aff_from_union_map(obj.v);
2886         if (obj.type == isl_obj_union_set)
2887                 return isl_union_pw_multi_aff_from_union_set(obj.v);
2888
2889         obj.type->free(obj.v);
2890         isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2891                 return NULL);
2892 }
2893
2894 /* Read an isl_union_pw_multi_aff from "str".
2895  */
2896 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_read_from_str(
2897         isl_ctx *ctx, const char *str)
2898 {
2899         isl_union_pw_multi_aff *upma;
2900         struct isl_stream *s = isl_stream_new_str(ctx, str);
2901         if (!s)
2902                 return NULL;
2903         upma = isl_stream_read_union_pw_multi_aff(s);
2904         isl_stream_free(s);
2905         return upma;
2906 }
2907
2908 /* Assuming "pa" represents a single affine expression defined on a universe
2909  * domain, extract this affine expression.
2910  */
2911 static __isl_give isl_aff *aff_from_pw_aff(__isl_take isl_pw_aff *pa)
2912 {
2913         isl_aff *aff;
2914
2915         if (!pa)
2916                 return NULL;
2917         if (pa->n != 1)
2918                 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
2919                         "expecting single affine expression",
2920                         goto error);
2921         if (!isl_set_plain_is_universe(pa->p[0].set))
2922                 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
2923                         "expecting universe domain",
2924                         goto error);
2925
2926         aff = isl_aff_copy(pa->p[0].aff);
2927         isl_pw_aff_free(pa);
2928         return aff;
2929 error:
2930         isl_pw_aff_free(pa);
2931         return NULL;
2932 }
2933
2934 /* Read a multi-affine expression from "s".
2935  * If the multi-affine expression has a domain, then then tuple
2936  * representing this domain cannot involve any affine expressions.
2937  * The tuple representing the actual expressions needs to consist
2938  * of only affine expressions.  Moreover, these expressions can
2939  * only depend on parameters and input dimensions and not on other
2940  * output dimensions.
2941  */
2942 __isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s)
2943 {
2944         struct vars *v;
2945         isl_set *dom = NULL;
2946         isl_multi_pw_aff *tuple = NULL;
2947         int dim, i, n;
2948         isl_space *space, *dom_space;
2949         isl_multi_aff *ma = NULL;
2950
2951         v = vars_new(s->ctx);
2952         if (!v)
2953                 return NULL;
2954
2955         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2956         if (next_is_tuple(s)) {
2957                 dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
2958                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2959                         goto error;
2960         }
2961         if (!isl_set_plain_is_universe(dom))
2962                 isl_die(s->ctx, isl_error_invalid,
2963                         "expecting universe parameter domain", goto error);
2964         if (isl_stream_eat(s, '{'))
2965                 goto error;
2966
2967         tuple = read_tuple(s, v, 0, 0);
2968         if (!tuple)
2969                 goto error;
2970         if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
2971                 isl_set *set;
2972                 isl_space *space;
2973                 int has_expr;
2974
2975                 has_expr = tuple_has_expr(tuple);
2976                 if (has_expr < 0)
2977                         goto error;
2978                 if (has_expr)
2979                         isl_die(s->ctx, isl_error_invalid,
2980                                 "expecting universe domain", goto error);
2981                 space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
2982                 set = isl_set_universe(space);
2983                 dom = isl_set_intersect_params(set, dom);
2984                 isl_multi_pw_aff_free(tuple);
2985                 tuple = read_tuple(s, v, 0, 0);
2986                 if (!tuple)
2987                         goto error;
2988         }
2989
2990         if (isl_stream_eat(s, '}'))
2991                 goto error;
2992
2993         n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
2994         dim = isl_set_dim(dom, isl_dim_all);
2995         dom_space = isl_set_get_space(dom);
2996         space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
2997         space = isl_space_align_params(space, isl_space_copy(dom_space));
2998         if (!isl_space_is_params(dom_space))
2999                 space = isl_space_map_from_domain_and_range(
3000                                 isl_space_copy(dom_space), space);
3001         isl_space_free(dom_space);
3002         ma = isl_multi_aff_alloc(space);
3003
3004         for (i = 0; i < n; ++i) {
3005                 isl_pw_aff *pa;
3006                 isl_aff *aff;
3007                 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
3008                 aff = aff_from_pw_aff(pa);
3009                 if (!aff)
3010                         goto error;
3011                 if (isl_aff_involves_dims(aff, isl_dim_in, dim, i + 1)) {
3012                         isl_aff_free(aff);
3013                         isl_die(s->ctx, isl_error_invalid,
3014                                 "not an affine expression", goto error);
3015                 }
3016                 aff = isl_aff_drop_dims(aff, isl_dim_in, dim, n);
3017                 space = isl_multi_aff_get_domain_space(ma);
3018                 aff = isl_aff_reset_domain_space(aff, space);
3019                 ma = isl_multi_aff_set_aff(ma, i, aff);
3020         }
3021
3022         isl_multi_pw_aff_free(tuple);
3023         vars_free(v);
3024         isl_set_free(dom);
3025         return ma;
3026 error:
3027         isl_multi_pw_aff_free(tuple);
3028         vars_free(v);
3029         isl_set_free(dom);
3030         isl_multi_aff_free(ma);
3031         return NULL;
3032 }
3033
3034 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
3035         const char *str)
3036 {
3037         isl_multi_aff *maff;
3038         struct isl_stream *s = isl_stream_new_str(ctx, str);
3039         if (!s)
3040                 return NULL;
3041         maff = isl_stream_read_multi_aff(s);
3042         isl_stream_free(s);
3043         return maff;
3044 }
3045
3046 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
3047         struct isl_stream *s)
3048 {
3049         struct isl_obj obj;
3050
3051         obj = obj_read(s);
3052         if (obj.type == isl_obj_pw_qpolynomial) {
3053                 obj.type = isl_obj_union_pw_qpolynomial;
3054                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
3055         }
3056         if (obj.v)
3057                 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
3058                            goto error);
3059
3060         return obj.v;
3061 error:
3062         obj.type->free(obj.v);
3063         return NULL;
3064 }
3065
3066 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
3067         isl_ctx *ctx, const char *str)
3068 {
3069         isl_union_pw_qpolynomial *upwqp;
3070         struct isl_stream *s = isl_stream_new_str(ctx, str);
3071         if (!s)
3072                 return NULL;
3073         upwqp = isl_stream_read_union_pw_qpolynomial(s);
3074         isl_stream_free(s);
3075         return upwqp;
3076 }