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