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