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