isl_input.c

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