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 /* Add a dimension to the given tuple.
 795  * The dimension is initially undefined, so it is encoded
 796  * as one times itself.
 797  */
 798 static __isl_give isl_multi_pw_aff *tuple_add_dim(
 799         __isl_take isl_multi_pw_aff *tuple, struct vars *v)
 800 {
 801         isl_space *space;
 802         isl_aff *aff;
 803         isl_pw_aff *pa;
 804
 805         tuple = isl_multi_pw_aff_add_dims(tuple, isl_dim_in, 1);
 806         space = isl_multi_pw_aff_get_domain_space(tuple);
 807         aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
 808         aff = isl_aff_add_coefficient_si(aff, isl_dim_in, v->n, 1);
 809         pa = isl_pw_aff_from_aff(aff);
 810         tuple = isl_multi_pw_aff_flat_range_product(tuple,
 811                                             isl_multi_pw_aff_from_pw_aff(pa));
 812
 813         return tuple;
 814 }
 815
 816 /* Set the name of dimension "pos" in "tuple" to "name".
 817  * During printing, we add primes if the same name appears more than once
 818  * to distinguish the occurrences.  Here, we remove those primes from "name"
 819  * before setting the name of the dimension.
 820  */
 821 static __isl_give isl_multi_pw_aff *tuple_set_dim_name(
 822         __isl_take isl_multi_pw_aff *tuple, int pos, char *name)
 823 {
 824         char *prime;
 825
 826         if (!name)
 827                 return tuple;
 828
 829         prime = strchr(name, '\'');
 830         if (prime)
 831                 *prime = '\0';
 832         tuple = isl_multi_pw_aff_set_dim_name(tuple, isl_dim_set, pos, name);
 833         if (prime)
 834                 *prime = '\'';
 835
 836         return tuple;
 837 }
 838
 839 /* Read an affine expression from "s" and replace the definition
 840  * of dimension "pos" in "tuple" by this expression.
 841  *
 842  * accept_extended_affine requires a wrapped space as input.
 843  * The domain space of "tuple", on the other hand is an anonymous space,
 844  * so we have to adjust the space of the isl_pw_aff before adding it
 845  * to "tuple".
 846  */
 847 static __isl_give isl_multi_pw_aff *read_tuple_var_def(struct isl_stream *s,
 848         __isl_take isl_multi_pw_aff *tuple, int pos, struct vars *v)
 849 {
 850         isl_space *space;
 851         isl_pw_aff *def;
 852
 853         space = isl_space_wrap(isl_space_alloc(s->ctx, 0, v->n, 0));
 854         def = accept_extended_affine(s, space, v);
 855         space = isl_space_set_alloc(s->ctx, 0, v->n);
 856         def = isl_pw_aff_reset_domain_space(def, space);
 857         tuple = isl_multi_pw_aff_set_pw_aff(tuple, pos, def);
 858
 859         return tuple;
 860 }
 861
 862 /* Read a list of variables and/or affine expressions and return the list
 863  * as an isl_multi_pw_aff.
 864  * The elements in the list are separated by either "," or "][".
 865  */
 866 static __isl_give isl_multi_pw_aff *read_tuple_var_list(struct isl_stream *s,
 867         struct vars *v)
 868 {
 869         int i = 0;
 870         struct isl_token *tok;
 871         isl_multi_pw_aff *res;
 872
 873         res = tuple_alloc(v);
 874
 875         if (isl_stream_next_token_is(s, ']'))
 876                 return res;
 877
 878         while ((tok = next_token(s)) != NULL) {
 879                 int new_name = 0;
 880
 881                 res = tuple_add_dim(res, v);
 882
 883                 if (tok->type == ISL_TOKEN_IDENT) {
 884                         int n = v->n;
 885                         int p = vars_pos(v, tok->u.s, -1);
 886                         if (p < 0)
 887                                 goto error;
 888                         new_name = p >= n;
 889                 }
 890
 891                 if (new_name) {
 892                         res = tuple_set_dim_name(res, i, v->v->name);
 893                         isl_token_free(tok);
 894                         if (isl_stream_eat_if_available(s, '='))
 895                                 res = read_tuple_var_def(s, res, i, v);
 896                 } else {
 897                         isl_stream_push_token(s, tok);
 898                         tok = NULL;
 899                         if (vars_add_anon(v) < 0)
 900                                 goto error;
 901                         res = read_tuple_var_def(s, res, i, v);
 902                 }
 903
 904                 tok = isl_stream_next_token(s);
 905                 if (tok && tok->type == ']' &&
 906                     isl_stream_next_token_is(s, '[')) {
 907                         isl_token_free(tok);
 908                         tok = isl_stream_next_token(s);
 909                 } else if (!tok || tok->type != ',')
 910                         break;
 911
 912                 isl_token_free(tok);
 913                 i++;
 914         }
 915         if (tok)
 916                 isl_stream_push_token(s, tok);
 917
 918         return res;
 919 error:
 920         isl_token_free(tok);
 921         return isl_multi_pw_aff_free(res);
 922 }
 923
 924 /* Read a tuple and represent it as an isl_multi_pw_aff.  See tuple_alloc.
 925  */
 926 static __isl_give isl_multi_pw_aff *read_tuple(struct isl_stream *s,
 927         struct vars *v)
 928 {
 929         struct isl_token *tok;
 930         char *name = NULL;
 931         isl_multi_pw_aff *res = NULL;
 932
 933         tok = isl_stream_next_token(s);
 934         if (!tok)
 935                 goto error;
 936         if (tok->type == ISL_TOKEN_IDENT || tok->is_keyword) {
 937                 name = strdup(tok->u.s);
 938                 isl_token_free(tok);
 939                 if (!name)
 940                         goto error;
 941         } else
 942                 isl_stream_push_token(s, tok);
 943         if (isl_stream_eat(s, '['))
 944                 goto error;
 945         if (next_is_tuple(s)) {
 946                 isl_multi_pw_aff *out;
 947                 int n;
 948                 res = read_tuple(s, v);
 949                 if (isl_stream_eat(s, ISL_TOKEN_TO))
 950                         goto error;
 951                 out = read_tuple(s, v);
 952                 n = isl_multi_pw_aff_dim(out, isl_dim_out);
 953                 res = isl_multi_pw_aff_add_dims(res, isl_dim_in, n);
 954                 res = isl_multi_pw_aff_range_product(res, out);
 955         } else
 956                 res = read_tuple_var_list(s, v);
 957         if (isl_stream_eat(s, ']'))
 958                 goto error;
 959
 960         if (name) {
 961                 res = isl_multi_pw_aff_set_tuple_name(res, isl_dim_out, name);
 962                 free(name);
 963         }
 964
 965         return res;
 966 error:
 967         free(name);
 968         return isl_multi_pw_aff_free(res);
 969 }
 970
 971 /* Read a tuple from "s" and add it to "map".
 972  * The tuple is initially represented as an isl_multi_pw_aff.
 973  * We first create the appropriate space in "map" based on the range
 974  * space of this isl_multi_pw_aff.  Then, we add equalities based
 975  * on the affine expressions.  These live in an anonymous space,
 976  * however, so we first need to reset the space to that of "map".
 977  */
 978 static __isl_give isl_map *read_map_tuple(struct isl_stream *s,
 979         __isl_take isl_map *map, enum isl_dim_type type, struct vars *v)
 980 {
 981         int i, n;
 982         isl_multi_pw_aff *tuple;
 983         isl_space *space = NULL;
 984
 985         tuple = read_tuple(s, v);
 986         if (!tuple)
 987                 goto error;
 988
 989         n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
 990         space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
 991
 992         if (type == isl_dim_param) {
 993                 if (isl_space_has_tuple_name(space, isl_dim_set) ||
 994                     isl_space_is_wrapping(space)) {
 995                         isl_die(s->ctx, isl_error_invalid,
 996                                 "parameter tuples cannot be named or nested",
 997                                 goto error);
 998                 }
 999                 map = isl_map_add_dims(map, type, n);
1000                 for (i = 0; i < n; ++i) {
1001                         isl_id *id;
1002                         if (!isl_space_has_dim_name(space, isl_dim_set, i))
1003                                 isl_die(s->ctx, isl_error_invalid,
1004                                         "parameters must be named",
1005                                         goto error);
1006                         id = isl_space_get_dim_id(space, isl_dim_set, i);
1007                         map = isl_map_set_dim_id(map, isl_dim_param, i, id);
1008                 }
1009         } else if (type == isl_dim_in) {
1010                 isl_set *set;
1011
1012                 set = isl_set_universe(isl_space_copy(space));
1013                 set = isl_set_intersect_params(set, isl_map_params(map));
1014                 map = isl_map_from_domain(set);
1015         } else {
1016                 isl_set *set;
1017
1018                 set = isl_set_universe(isl_space_copy(space));
1019                 map = isl_map_from_domain_and_range(isl_map_domain(map), set);
1020         }
1021
1022         for (i = 0; i < n; ++i) {
1023                 isl_pw_aff *pa;
1024                 isl_space *space;
1025                 isl_aff *aff;
1026                 isl_set *set;
1027                 isl_map *map_i;
1028
1029                 pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
1030                 space = isl_pw_aff_get_domain_space(pa);
1031                 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1032                 aff = isl_aff_add_coefficient_si(aff,
1033                                                 isl_dim_in, v->n - n + i, -1);
1034                 pa = isl_pw_aff_add(pa, isl_pw_aff_from_aff(aff));
1035                 set = isl_pw_aff_zero_set(pa);
1036                 map_i = isl_map_from_range(set);
1037                 map_i = isl_map_reset_space(map_i, isl_map_get_space(map));
1038                 map = isl_map_intersect(map, map_i);
1039         }
1040
1041         isl_space_free(space);
1042         isl_multi_pw_aff_free(tuple);
1043         return map;
1044 error:
1045         isl_space_free(space);
1046         isl_multi_pw_aff_free(tuple);
1047         isl_map_free(map);
1048         return NULL;
1049 }
1050
1051 static __isl_give isl_set *construct_constraints(
1052         __isl_take isl_set *set, int type,
1053         __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right)
1054 {
1055         isl_set *cond;
1056
1057         if (type == ISL_TOKEN_LE)
1058                 cond = isl_pw_aff_list_le_set(isl_pw_aff_list_copy(left),
1059                                               isl_pw_aff_list_copy(right));
1060         else if (type == ISL_TOKEN_GE)
1061                 cond = isl_pw_aff_list_ge_set(isl_pw_aff_list_copy(left),
1062                                               isl_pw_aff_list_copy(right));
1063         else if (type == ISL_TOKEN_LT)
1064                 cond = isl_pw_aff_list_lt_set(isl_pw_aff_list_copy(left),
1065                                               isl_pw_aff_list_copy(right));
1066         else if (type == ISL_TOKEN_GT)
1067                 cond = isl_pw_aff_list_gt_set(isl_pw_aff_list_copy(left),
1068                                               isl_pw_aff_list_copy(right));
1069         else if (type == ISL_TOKEN_NE)
1070                 cond = isl_pw_aff_list_ne_set(isl_pw_aff_list_copy(left),
1071                                               isl_pw_aff_list_copy(right));
1072         else
1073                 cond = isl_pw_aff_list_eq_set(isl_pw_aff_list_copy(left),
1074                                               isl_pw_aff_list_copy(right));
1075
1076         return isl_set_intersect(set, cond);
1077 }
1078
1079 static __isl_give isl_map *add_constraint(struct isl_stream *s,
1080         struct vars *v, __isl_take isl_map *map)
1081 {
1082         struct isl_token *tok = NULL;
1083         isl_pw_aff_list *list1 = NULL, *list2 = NULL;
1084         isl_set *set;
1085
1086         set = isl_map_wrap(map);
1087         list1 = accept_affine_list(s, isl_set_get_space(set), v);
1088         if (!list1)
1089                 goto error;
1090         tok = isl_stream_next_token(s);
1091         if (!is_comparator(tok)) {
1092                 isl_stream_error(s, tok, "missing operator");
1093                 if (tok)
1094                         isl_stream_push_token(s, tok);
1095                 tok = NULL;
1096                 goto error;
1097         }
1098         for (;;) {
1099                 list2 = accept_affine_list(s, isl_set_get_space(set), v);
1100                 if (!list2)
1101                         goto error;
1102
1103                 set = construct_constraints(set, tok->type, list1, list2);
1104                 isl_token_free(tok);
1105                 isl_pw_aff_list_free(list1);
1106                 list1 = list2;
1107
1108                 tok = isl_stream_next_token(s);
1109                 if (!is_comparator(tok)) {
1110                         if (tok)
1111                                 isl_stream_push_token(s, tok);
1112                         break;
1113                 }
1114         }
1115         isl_pw_aff_list_free(list1);
1116
1117         return isl_set_unwrap(set);
1118 error:
1119         if (tok)
1120                 isl_token_free(tok);
1121         isl_pw_aff_list_free(list1);
1122         isl_pw_aff_list_free(list2);
1123         isl_set_free(set);
1124         return NULL;
1125 }
1126
1127 static __isl_give isl_map *read_exists(struct isl_stream *s,
1128         struct vars *v, __isl_take isl_map *map)
1129 {
1130         int n = v->n;
1131         int seen_paren = isl_stream_eat_if_available(s, '(');
1132
1133         map = isl_map_from_domain(isl_map_wrap(map));
1134         map = read_defined_var_list(s, v, map);
1135
1136         if (isl_stream_eat(s, ':'))
1137                 goto error;
1138
1139         map = read_disjuncts(s, v, map);
1140         map = isl_set_unwrap(isl_map_domain(map));
1141
1142         vars_drop(v, v->n - n);
1143         if (seen_paren && isl_stream_eat(s, ')'))
1144                 goto error;
1145
1146         return map;
1147 error:
1148         isl_map_free(map);
1149         return NULL;
1150 }
1151
1152 /* Parse an expression between parentheses and push the result
1153  * back on the stream.
1154  *
1155  * The parsed expression may be either an affine expression
1156  * or a condition.  The first type is pushed onto the stream
1157  * as an isl_pw_aff, while the second is pushed as an isl_map.
1158  *
1159  * If the initial token indicates the start of a condition,
1160  * we parse it as such.
1161  * Otherwise, we first parse an affine expression and push
1162  * that onto the stream.  If the affine expression covers the
1163  * entire expression between parentheses, we return.
1164  * Otherwise, we assume that the affine expression is the
1165  * start of a condition and continue parsing.
1166  */
1167 static int resolve_paren_expr(struct isl_stream *s,
1168         struct vars *v, __isl_take isl_map *map)
1169 {
1170         struct isl_token *tok, *tok2;
1171         int line, col;
1172         isl_pw_aff *pwaff;
1173
1174         tok = isl_stream_next_token(s);
1175         if (!tok || tok->type != '(')
1176                 goto error;
1177
1178         if (isl_stream_next_token_is(s, '('))
1179                 if (resolve_paren_expr(s, v, isl_map_copy(map)))
1180                         goto error;
1181
1182         if (isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) ||
1183             isl_stream_next_token_is(s, ISL_TOKEN_NOT) ||
1184             isl_stream_next_token_is(s, ISL_TOKEN_TRUE) ||
1185             isl_stream_next_token_is(s, ISL_TOKEN_FALSE) ||
1186             isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1187                 map = read_disjuncts(s, v, map);
1188                 if (isl_stream_eat(s, ')'))
1189                         goto error;
1190                 tok->type = ISL_TOKEN_MAP;
1191                 tok->u.map = map;
1192                 isl_stream_push_token(s, tok);
1193                 return 0;
1194         }
1195
1196         tok2 = isl_stream_next_token(s);
1197         if (!tok2)
1198                 goto error;
1199         line = tok2->line;
1200         col = tok2->col;
1201         isl_stream_push_token(s, tok2);
1202
1203         pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
1204         if (!pwaff)
1205                 goto error;
1206
1207         tok2 = isl_token_new(s->ctx, line, col, 0);
1208         if (!tok2)
1209                 goto error2;
1210         tok2->type = ISL_TOKEN_AFF;
1211         tok2->u.pwaff = pwaff;
1212
1213         if (isl_stream_eat_if_available(s, ')')) {
1214                 isl_stream_push_token(s, tok2);
1215                 isl_token_free(tok);
1216                 isl_map_free(map);
1217                 return 0;
1218         }
1219
1220         isl_stream_push_token(s, tok2);
1221
1222         map = read_disjuncts(s, v, map);
1223         if (isl_stream_eat(s, ')'))
1224                 goto error;
1225
1226         tok->type = ISL_TOKEN_MAP;
1227         tok->u.map = map;
1228         isl_stream_push_token(s, tok);
1229
1230         return 0;
1231 error2:
1232         isl_pw_aff_free(pwaff);
1233 error:
1234         isl_token_free(tok);
1235         isl_map_free(map);
1236         return -1;
1237 }
1238
1239 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1240         struct vars *v, __isl_take isl_map *map)
1241 {
1242         if (isl_stream_next_token_is(s, '('))
1243                 if (resolve_paren_expr(s, v, isl_map_copy(map)))
1244                         goto error;
1245
1246         if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1247                 struct isl_token *tok;
1248                 tok = isl_stream_next_token(s);
1249                 if (!tok)
1250                         goto error;
1251                 isl_map_free(map);
1252                 map = isl_map_copy(tok->u.map);
1253                 isl_token_free(tok);
1254                 return map;
1255         }
1256
1257         if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1258                 return read_exists(s, v, map);
1259
1260         if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1261                 return map;
1262
1263         if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1264                 isl_space *dim = isl_map_get_space(map);
1265                 isl_map_free(map);
1266                 return isl_map_empty(dim);
1267         }
1268
1269         return add_constraint(s, v, map);
1270 error:
1271         isl_map_free(map);
1272         return NULL;
1273 }
1274
1275 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1276         struct vars *v, __isl_take isl_map *map)
1277 {
1278         isl_map *res;
1279         int negate;
1280
1281         negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1282         res = read_conjunct(s, v, isl_map_copy(map));
1283         if (negate)
1284                 res = isl_map_subtract(isl_map_copy(map), res);
1285
1286         while (isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1287                 isl_map *res_i;
1288
1289                 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1290                 res_i = read_conjunct(s, v, isl_map_copy(map));
1291                 if (negate)
1292                         res = isl_map_subtract(res, res_i);
1293                 else
1294                         res = isl_map_intersect(res, res_i);
1295         }
1296
1297         isl_map_free(map);
1298         return res;
1299 }
1300
1301 static struct isl_map *read_disjuncts(struct isl_stream *s,
1302         struct vars *v, __isl_take isl_map *map)
1303 {
1304         isl_map *res;
1305
1306         if (isl_stream_next_token_is(s, '}')) {
1307                 isl_space *dim = isl_map_get_space(map);
1308                 isl_map_free(map);
1309                 return isl_map_universe(dim);
1310         }
1311
1312         res = read_conjuncts(s, v, isl_map_copy(map));
1313         while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1314                 isl_map *res_i;
1315
1316                 res_i = read_conjuncts(s, v, isl_map_copy(map));
1317                 res = isl_map_union(res, res_i);
1318         }
1319
1320         isl_map_free(map);
1321         return res;
1322 }
1323
1324 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1325 {
1326         if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1327                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1328                            isl_basic_map_dim(bmap, isl_dim_in) + pos;
1329         pos -= isl_basic_map_dim(bmap, isl_dim_out);
1330
1331         if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1332                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1333         pos -= isl_basic_map_dim(bmap, isl_dim_in);
1334
1335         if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1336                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1337                            isl_basic_map_dim(bmap, isl_dim_in) +
1338                            isl_basic_map_dim(bmap, isl_dim_out) + pos;
1339         pos -= isl_basic_map_dim(bmap, isl_dim_div);
1340
1341         if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1342                 return 1 + pos;
1343
1344         return 0;
1345 }
1346
1347 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1348         struct isl_stream *s, __isl_take isl_basic_map *bmap)
1349 {
1350         int j;
1351         struct isl_token *tok;
1352         int type;
1353         int k;
1354         isl_int *c;
1355         unsigned nparam;
1356         unsigned dim;
1357
1358         if (!bmap)
1359                 return NULL;
1360
1361         nparam = isl_basic_map_dim(bmap, isl_dim_param);
1362         dim = isl_basic_map_dim(bmap, isl_dim_out);
1363
1364         tok = isl_stream_next_token(s);
1365         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1366                 isl_stream_error(s, tok, "expecting coefficient");
1367                 if (tok)
1368                         isl_stream_push_token(s, tok);
1369                 goto error;
1370         }
1371         if (!tok->on_new_line) {
1372                 isl_stream_error(s, tok, "coefficient should appear on new line");
1373                 isl_stream_push_token(s, tok);
1374                 goto error;
1375         }
1376
1377         type = isl_int_get_si(tok->u.v);
1378         isl_token_free(tok);
1379
1380         isl_assert(s->ctx, type == 0 || type == 1, goto error);
1381         if (type == 0) {
1382                 k = isl_basic_map_alloc_equality(bmap);
1383                 c = bmap->eq[k];
1384         } else {
1385                 k = isl_basic_map_alloc_inequality(bmap);
1386                 c = bmap->ineq[k];
1387         }
1388         if (k < 0)
1389                 goto error;
1390
1391         for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1392                 int pos;
1393                 tok = isl_stream_next_token(s);
1394                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1395                         isl_stream_error(s, tok, "expecting coefficient");
1396                         if (tok)
1397                                 isl_stream_push_token(s, tok);
1398                         goto error;
1399                 }
1400                 if (tok->on_new_line) {
1401                         isl_stream_error(s, tok,
1402                                 "coefficient should not appear on new line");
1403                         isl_stream_push_token(s, tok);
1404                         goto error;
1405                 }
1406                 pos = polylib_pos_to_isl_pos(bmap, j);
1407                 isl_int_set(c[pos], tok->u.v);
1408                 isl_token_free(tok);
1409         }
1410
1411         return bmap;
1412 error:
1413         isl_basic_map_free(bmap);
1414         return NULL;
1415 }
1416
1417 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s)
1418 {
1419         int i;
1420         struct isl_token *tok;
1421         struct isl_token *tok2;
1422         int n_row, n_col;
1423         int on_new_line;
1424         unsigned in = 0, out, local = 0;
1425         struct isl_basic_map *bmap = NULL;
1426         int nparam = 0;
1427
1428         tok = isl_stream_next_token(s);
1429         if (!tok) {
1430                 isl_stream_error(s, NULL, "unexpected EOF");
1431                 return NULL;
1432         }
1433         tok2 = isl_stream_next_token(s);
1434         if (!tok2) {
1435                 isl_token_free(tok);
1436                 isl_stream_error(s, NULL, "unexpected EOF");
1437                 return NULL;
1438         }
1439         if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1440                 isl_stream_push_token(s, tok2);
1441                 isl_stream_push_token(s, tok);
1442                 isl_stream_error(s, NULL,
1443                                  "expecting constraint matrix dimensions");
1444                 return NULL;
1445         }
1446         n_row = isl_int_get_si(tok->u.v);
1447         n_col = isl_int_get_si(tok2->u.v);
1448         on_new_line = tok2->on_new_line;
1449         isl_token_free(tok2);
1450         isl_token_free(tok);
1451         isl_assert(s->ctx, !on_new_line, return NULL);
1452         isl_assert(s->ctx, n_row >= 0, return NULL);
1453         isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1454         tok = isl_stream_next_token_on_same_line(s);
1455         if (tok) {
1456                 if (tok->type != ISL_TOKEN_VALUE) {
1457                         isl_stream_error(s, tok,
1458                                     "expecting number of output dimensions");
1459                         isl_stream_push_token(s, tok);
1460                         goto error;
1461                 }
1462                 out = isl_int_get_si(tok->u.v);
1463                 isl_token_free(tok);
1464
1465                 tok = isl_stream_next_token_on_same_line(s);
1466                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1467                         isl_stream_error(s, tok,
1468                                     "expecting number of input dimensions");
1469                         if (tok)
1470                                 isl_stream_push_token(s, tok);
1471                         goto error;
1472                 }
1473                 in = isl_int_get_si(tok->u.v);
1474                 isl_token_free(tok);
1475
1476                 tok = isl_stream_next_token_on_same_line(s);
1477                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1478                         isl_stream_error(s, tok,
1479                                     "expecting number of existentials");
1480                         if (tok)
1481                                 isl_stream_push_token(s, tok);
1482                         goto error;
1483                 }
1484                 local = isl_int_get_si(tok->u.v);
1485                 isl_token_free(tok);
1486
1487                 tok = isl_stream_next_token_on_same_line(s);
1488                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1489                         isl_stream_error(s, tok,
1490                                     "expecting number of parameters");
1491                         if (tok)
1492                                 isl_stream_push_token(s, tok);
1493                         goto error;
1494                 }
1495                 nparam = isl_int_get_si(tok->u.v);
1496                 isl_token_free(tok);
1497                 if (n_col != 1 + out + in + local + nparam + 1) {
1498                         isl_stream_error(s, NULL,
1499                                     "dimensions don't match");
1500                         goto error;
1501                 }
1502         } else
1503                 out = n_col - 2 - nparam;
1504         bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1505         if (!bmap)
1506                 return NULL;
1507
1508         for (i = 0; i < local; ++i) {
1509                 int k = isl_basic_map_alloc_div(bmap);
1510                 if (k < 0)
1511                         goto error;
1512                 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1513         }
1514
1515         for (i = 0; i < n_row; ++i)
1516                 bmap = basic_map_read_polylib_constraint(s, bmap);
1517
1518         tok = isl_stream_next_token_on_same_line(s);
1519         if (tok) {
1520                 isl_stream_error(s, tok, "unexpected extra token on line");
1521                 isl_stream_push_token(s, tok);
1522                 goto error;
1523         }
1524
1525         bmap = isl_basic_map_simplify(bmap);
1526         bmap = isl_basic_map_finalize(bmap);
1527         return bmap;
1528 error:
1529         isl_basic_map_free(bmap);
1530         return NULL;
1531 }
1532
1533 static struct isl_map *map_read_polylib(struct isl_stream *s)
1534 {
1535         struct isl_token *tok;
1536         struct isl_token *tok2;
1537         int i, n;
1538         struct isl_map *map;
1539
1540         tok = isl_stream_next_token(s);
1541         if (!tok) {
1542                 isl_stream_error(s, NULL, "unexpected EOF");
1543                 return NULL;
1544         }
1545         tok2 = isl_stream_next_token_on_same_line(s);
1546         if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1547                 isl_stream_push_token(s, tok2);
1548                 isl_stream_push_token(s, tok);
1549                 return isl_map_from_basic_map(basic_map_read_polylib(s));
1550         }
1551         if (tok2) {
1552                 isl_stream_error(s, tok2, "unexpected token");
1553                 isl_stream_push_token(s, tok2);
1554                 isl_stream_push_token(s, tok);
1555                 return NULL;
1556         }
1557         n = isl_int_get_si(tok->u.v);
1558         isl_token_free(tok);
1559
1560         isl_assert(s->ctx, n >= 1, return NULL);
1561
1562         map = isl_map_from_basic_map(basic_map_read_polylib(s));
1563
1564         for (i = 1; map && i < n; ++i)
1565                 map = isl_map_union(map,
1566                         isl_map_from_basic_map(basic_map_read_polylib(s)));
1567
1568         return map;
1569 }
1570
1571 static int optional_power(struct isl_stream *s)
1572 {
1573         int pow;
1574         struct isl_token *tok;
1575
1576         tok = isl_stream_next_token(s);
1577         if (!tok)
1578                 return 1;
1579         if (tok->type != '^') {
1580                 isl_stream_push_token(s, tok);
1581                 return 1;
1582         }
1583         isl_token_free(tok);
1584         tok = isl_stream_next_token(s);
1585         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1586                 isl_stream_error(s, tok, "expecting exponent");
1587                 if (tok)
1588                         isl_stream_push_token(s, tok);
1589                 return 1;
1590         }
1591         pow = isl_int_get_si(tok->u.v);
1592         isl_token_free(tok);
1593         return pow;
1594 }
1595
1596 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1597         __isl_keep isl_map *map, struct vars *v);
1598
1599 static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s,
1600         __isl_keep isl_map *map, struct vars *v)
1601 {
1602         isl_pw_qpolynomial *pwqp;
1603         struct isl_token *tok;
1604
1605         tok = next_token(s);
1606         if (!tok) {
1607                 isl_stream_error(s, NULL, "unexpected EOF");
1608                 return NULL;
1609         }
1610         if (tok->type == '(') {
1611                 int pow;
1612
1613                 isl_token_free(tok);
1614                 pwqp = read_term(s, map, v);
1615                 if (!pwqp)
1616                         return NULL;
1617                 if (isl_stream_eat(s, ')'))
1618                         goto error;
1619                 pow = optional_power(s);
1620                 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1621         } else if (tok->type == ISL_TOKEN_VALUE) {
1622                 struct isl_token *tok2;
1623                 tok2 = isl_stream_next_token(s);
1624                 isl_qpolynomial *qp;
1625                 if (tok2 && tok2->type == '/') {
1626                         isl_token_free(tok2);
1627                         tok2 = next_token(s);
1628                         if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1629                                 isl_stream_error(s, tok2, "expected denominator");
1630                                 isl_token_free(tok);
1631                                 isl_token_free(tok2);
1632                                 return NULL;
1633                         }
1634                         qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
1635                                                     tok->u.v, tok2->u.v);
1636                         isl_token_free(tok2);
1637                 } else {
1638                         isl_stream_push_token(s, tok2);
1639                         qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
1640                                                 tok->u.v);
1641                 }
1642                 isl_token_free(tok);
1643                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1644         } else if (tok->type == ISL_TOKEN_INFTY) {
1645                 isl_qpolynomial *qp;
1646                 isl_token_free(tok);
1647                 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
1648                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1649         } else if (tok->type == ISL_TOKEN_NAN) {
1650                 isl_qpolynomial *qp;
1651                 isl_token_free(tok);
1652                 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
1653                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1654         } else if (tok->type == ISL_TOKEN_IDENT) {
1655                 int n = v->n;
1656                 int pos = vars_pos(v, tok->u.s, -1);
1657                 int pow;
1658                 isl_qpolynomial *qp;
1659                 if (pos < 0) {
1660                         isl_token_free(tok);
1661                         return NULL;
1662                 }
1663                 if (pos >= n) {
1664                         vars_drop(v, v->n - n);
1665                         isl_stream_error(s, tok, "unknown identifier");
1666                         isl_token_free(tok);
1667                         return NULL;
1668                 }
1669                 isl_token_free(tok);
1670                 pow = optional_power(s);
1671                 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
1672                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1673         } else if (tok->type == '[') {
1674                 isl_pw_aff *pwaff;
1675                 int pow;
1676
1677                 isl_stream_push_token(s, tok);
1678                 pwaff = accept_div(s, isl_map_get_space(map), v);
1679                 pow = optional_power(s);
1680                 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
1681                 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1682         } else if (tok->type == '-') {
1683                 isl_token_free(tok);
1684                 pwqp = read_factor(s, map, v);
1685                 pwqp = isl_pw_qpolynomial_neg(pwqp);
1686         } else {
1687                 isl_stream_error(s, tok, "unexpected isl_token");
1688                 isl_stream_push_token(s, tok);
1689                 return NULL;
1690         }
1691
1692         if (isl_stream_eat_if_available(s, '*') ||
1693             isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1694                 isl_pw_qpolynomial *pwqp2;
1695
1696                 pwqp2 = read_factor(s, map, v);
1697                 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
1698         }
1699
1700         return pwqp;
1701 error:
1702         isl_pw_qpolynomial_free(pwqp);
1703         return NULL;
1704 }
1705
1706 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1707         __isl_keep isl_map *map, struct vars *v)
1708 {
1709         struct isl_token *tok;
1710         isl_pw_qpolynomial *pwqp;
1711
1712         pwqp = read_factor(s, map, v);
1713
1714         for (;;) {
1715                 tok = next_token(s);
1716                 if (!tok)
1717                         return pwqp;
1718
1719                 if (tok->type == '+') {
1720                         isl_pw_qpolynomial *pwqp2;
1721
1722                         isl_token_free(tok);
1723                         pwqp2 = read_factor(s, map, v);
1724                         pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1725                 } else if (tok->type == '-') {
1726                         isl_pw_qpolynomial *pwqp2;
1727
1728                         isl_token_free(tok);
1729                         pwqp2 = read_factor(s, map, v);
1730                         pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
1731                 } else if (tok->type == ISL_TOKEN_VALUE &&
1732                             isl_int_is_neg(tok->u.v)) {
1733                         isl_pw_qpolynomial *pwqp2;
1734
1735                         isl_stream_push_token(s, tok);
1736                         pwqp2 = read_factor(s, map, v);
1737                         pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1738                 } else {
1739                         isl_stream_push_token(s, tok);
1740                         break;
1741                 }
1742         }
1743
1744         return pwqp;
1745 }
1746
1747 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1748         __isl_take isl_map *map, struct vars *v)
1749 {
1750         struct isl_token *tok;
1751
1752         tok = isl_stream_next_token(s);
1753         if (!tok) {
1754                 isl_stream_error(s, NULL, "unexpected EOF");
1755                 goto error;
1756         }
1757         if (tok->type == ':' ||
1758             (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
1759                 isl_token_free(tok);
1760                 map = read_disjuncts(s, v, map);
1761         } else
1762                 isl_stream_push_token(s, tok);
1763
1764         return map;
1765 error:
1766         isl_map_free(map);
1767         return NULL;
1768 }
1769
1770 static struct isl_obj obj_read_poly(struct isl_stream *s,
1771         __isl_take isl_map *map, struct vars *v, int n)
1772 {
1773         struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1774         isl_pw_qpolynomial *pwqp;
1775         struct isl_set *set;
1776
1777         pwqp = read_term(s, map, v);
1778         map = read_optional_disjuncts(s, map, v);
1779         set = isl_map_range(map);
1780
1781         pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
1782
1783         vars_drop(v, v->n - n);
1784
1785         obj.v = pwqp;
1786         return obj;
1787 }
1788
1789 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1790         __isl_take isl_set *set, struct vars *v, int n)
1791 {
1792         struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1793         isl_pw_qpolynomial *pwqp;
1794         isl_pw_qpolynomial_fold *pwf = NULL;
1795
1796         if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1797                 return obj_read_poly(s, set, v, n);
1798
1799         if (isl_stream_eat(s, '('))
1800                 goto error;
1801
1802         pwqp = read_term(s, set, v);
1803         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
1804
1805         while (isl_stream_eat_if_available(s, ',')) {
1806                 isl_pw_qpolynomial_fold *pwf_i;
1807                 pwqp = read_term(s, set, v);
1808                 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
1809                                                                         pwqp);
1810                 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
1811         }
1812
1813         if (isl_stream_eat(s, ')'))
1814                 goto error;
1815
1816         set = read_optional_disjuncts(s, set, v);
1817         pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
1818
1819         vars_drop(v, v->n - n);
1820
1821         obj.v = pwf;
1822         return obj;
1823 error:
1824         isl_set_free(set);
1825         isl_pw_qpolynomial_fold_free(pwf);
1826         obj.type = isl_obj_none;
1827         return obj;
1828 }
1829
1830 static int is_rational(struct isl_stream *s)
1831 {
1832         struct isl_token *tok;
1833
1834         tok = isl_stream_next_token(s);
1835         if (!tok)
1836                 return 0;
1837         if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
1838                 isl_token_free(tok);
1839                 isl_stream_eat(s, ':');
1840                 return 1;
1841         }
1842
1843         isl_stream_push_token(s, tok);
1844
1845         return 0;
1846 }
1847
1848 static struct isl_obj obj_read_body(struct isl_stream *s,
1849         __isl_take isl_map *map, struct vars *v)
1850 {
1851         struct isl_token *tok;
1852         struct isl_obj obj = { isl_obj_set, NULL };
1853         int n = v->n;
1854
1855         if (is_rational(s))
1856                 map = isl_map_set_rational(map);
1857
1858         if (isl_stream_next_token_is(s, ':')) {
1859                 obj.type = isl_obj_set;
1860                 obj.v = read_optional_disjuncts(s, map, v);
1861                 return obj;
1862         }
1863
1864         if (!next_is_tuple(s))
1865                 return obj_read_poly_or_fold(s, map, v, n);
1866
1867         map = read_map_tuple(s, map, isl_dim_in, v);
1868         if (!map)
1869                 goto error;
1870         tok = isl_stream_next_token(s);
1871         if (!tok)
1872                 goto error;
1873         if (tok->type == ISL_TOKEN_TO) {
1874                 obj.type = isl_obj_map;
1875                 isl_token_free(tok);
1876                 if (!next_is_tuple(s)) {
1877                         isl_set *set = isl_map_domain(map);
1878                         return obj_read_poly_or_fold(s, set, v, n);
1879                 }
1880                 map = read_map_tuple(s, map, isl_dim_out, v);
1881                 if (!map)
1882                         goto error;
1883         } else {
1884                 map = isl_map_domain(map);
1885                 isl_stream_push_token(s, tok);
1886         }
1887
1888         map = read_optional_disjuncts(s, map, v);
1889
1890         vars_drop(v, v->n - n);
1891
1892         obj.v = map;
1893         return obj;
1894 error:
1895         isl_map_free(map);
1896         obj.type = isl_obj_none;
1897         return obj;
1898 }
1899
1900 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
1901 {
1902         if (obj.type == isl_obj_map) {
1903                 obj.v = isl_union_map_from_map(obj.v);
1904                 obj.type = isl_obj_union_map;
1905         } else if (obj.type == isl_obj_set) {
1906                 obj.v = isl_union_set_from_set(obj.v);
1907                 obj.type = isl_obj_union_set;
1908         } else if (obj.type == isl_obj_pw_qpolynomial) {
1909                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
1910                 obj.type = isl_obj_union_pw_qpolynomial;
1911         } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
1912                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
1913                 obj.type = isl_obj_union_pw_qpolynomial_fold;
1914         } else
1915                 isl_assert(ctx, 0, goto error);
1916         return obj;
1917 error:
1918         obj.type->free(obj.v);
1919         obj.type = isl_obj_none;
1920         return obj;
1921 }
1922
1923 static struct isl_obj obj_add(struct isl_ctx *ctx,
1924         struct isl_obj obj1, struct isl_obj obj2)
1925 {
1926         if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
1927                 obj1 = to_union(ctx, obj1);
1928         if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
1929                 obj2 = to_union(ctx, obj2);
1930         if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
1931                 obj1 = to_union(ctx, obj1);
1932         if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
1933                 obj2 = to_union(ctx, obj2);
1934         if (obj1.type == isl_obj_pw_qpolynomial &&
1935             obj2.type == isl_obj_union_pw_qpolynomial)
1936                 obj1 = to_union(ctx, obj1);
1937         if (obj1.type == isl_obj_union_pw_qpolynomial &&
1938             obj2.type == isl_obj_pw_qpolynomial)
1939                 obj2 = to_union(ctx, obj2);
1940         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1941             obj2.type == isl_obj_union_pw_qpolynomial_fold)
1942                 obj1 = to_union(ctx, obj1);
1943         if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
1944             obj2.type == isl_obj_pw_qpolynomial_fold)
1945                 obj2 = to_union(ctx, obj2);
1946         isl_assert(ctx, obj1.type == obj2.type, goto error);
1947         if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
1948                 obj1 = to_union(ctx, obj1);
1949                 obj2 = to_union(ctx, obj2);
1950         }
1951         if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
1952                 obj1 = to_union(ctx, obj1);
1953                 obj2 = to_union(ctx, obj2);
1954         }
1955         if (obj1.type == isl_obj_pw_qpolynomial &&
1956             !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
1957                 obj1 = to_union(ctx, obj1);
1958                 obj2 = to_union(ctx, obj2);
1959         }
1960         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1961             !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
1962                 obj1 = to_union(ctx, obj1);
1963                 obj2 = to_union(ctx, obj2);
1964         }
1965         obj1.v = obj1.type->add(obj1.v, obj2.v);
1966         return obj1;
1967 error:
1968         obj1.type->free(obj1.v);
1969         obj2.type->free(obj2.v);
1970         obj1.type = isl_obj_none;
1971         obj1.v = NULL;
1972         return obj1;
1973 }
1974
1975 static struct isl_obj obj_read(struct isl_stream *s)
1976 {
1977         isl_map *map = NULL;
1978         struct isl_token *tok;
1979         struct vars *v = NULL;
1980         struct isl_obj obj = { isl_obj_set, NULL };
1981
1982         tok = next_token(s);
1983         if (!tok) {
1984                 isl_stream_error(s, NULL, "unexpected EOF");
1985                 goto error;
1986         }
1987         if (tok->type == ISL_TOKEN_VALUE) {
1988                 struct isl_token *tok2;
1989                 struct isl_map *map;
1990
1991                 tok2 = isl_stream_next_token(s);
1992                 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
1993                     isl_int_is_neg(tok2->u.v)) {
1994                         if (tok2)
1995                                 isl_stream_push_token(s, tok2);
1996                         obj.type = isl_obj_int;
1997                         obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
1998                         isl_token_free(tok);
1999                         return obj;
2000                 }
2001                 isl_stream_push_token(s, tok2);
2002                 isl_stream_push_token(s, tok);
2003                 map = map_read_polylib(s);
2004                 if (!map)
2005                         goto error;
2006                 if (isl_map_may_be_set(map))
2007                         obj.v = isl_map_range(map);
2008                 else {
2009                         obj.type = isl_obj_map;
2010                         obj.v = map;
2011                 }
2012                 return obj;
2013         }
2014         v = vars_new(s->ctx);
2015         if (!v) {
2016                 isl_stream_push_token(s, tok);
2017                 goto error;
2018         }
2019         map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
2020         if (tok->type == '[') {
2021                 isl_stream_push_token(s, tok);
2022                 map = read_map_tuple(s, map, isl_dim_param, v);
2023                 if (!map)
2024                         goto error;
2025                 tok = isl_stream_next_token(s);
2026                 if (!tok || tok->type != ISL_TOKEN_TO) {
2027                         isl_stream_error(s, tok, "expecting '->'");
2028                         if (tok)
2029                                 isl_stream_push_token(s, tok);
2030                         goto error;
2031                 }
2032                 isl_token_free(tok);
2033                 tok = isl_stream_next_token(s);
2034         }
2035         if (!tok || tok->type != '{') {
2036                 isl_stream_error(s, tok, "expecting '{'");
2037                 if (tok)
2038                         isl_stream_push_token(s, tok);
2039                 goto error;
2040         }
2041         isl_token_free(tok);
2042
2043         tok = isl_stream_next_token(s);
2044         if (!tok)
2045                 ;
2046         else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
2047                 isl_token_free(tok);
2048                 if (isl_stream_eat(s, '='))
2049                         goto error;
2050                 map = read_map_tuple(s, map, isl_dim_param, v);
2051                 if (!map)
2052                         goto error;
2053         } else if (tok->type == '}') {
2054                 obj.type = isl_obj_union_set;
2055                 obj.v = isl_union_set_empty(isl_map_get_space(map));
2056                 isl_token_free(tok);
2057                 goto done;
2058         } else
2059                 isl_stream_push_token(s, tok);
2060
2061         for (;;) {
2062                 struct isl_obj o;
2063                 tok = NULL;
2064                 o = obj_read_body(s, isl_map_copy(map), v);
2065                 if (o.type == isl_obj_none || !o.v)
2066                         goto error;
2067                 if (!obj.v)
2068                         obj = o;
2069                 else {
2070                         obj = obj_add(s->ctx, obj, o);
2071                         if (obj.type == isl_obj_none || !obj.v)
2072                                 goto error;
2073                 }
2074                 tok = isl_stream_next_token(s);
2075                 if (!tok || tok->type != ';')
2076                         break;
2077                 isl_token_free(tok);
2078                 if (isl_stream_next_token_is(s, '}')) {
2079                         tok = isl_stream_next_token(s);
2080                         break;
2081                 }
2082         }
2083
2084         if (tok && tok->type == '}') {
2085                 isl_token_free(tok);
2086         } else {
2087                 isl_stream_error(s, tok, "unexpected isl_token");
2088                 if (tok)
2089                         isl_token_free(tok);
2090                 goto error;
2091         }
2092 done:
2093         vars_free(v);
2094         isl_map_free(map);
2095
2096         return obj;
2097 error:
2098         isl_map_free(map);
2099         obj.type->free(obj.v);
2100         if (v)
2101                 vars_free(v);
2102         obj.v = NULL;
2103         return obj;
2104 }
2105
2106 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
2107 {
2108         return obj_read(s);
2109 }
2110
2111 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
2112 {
2113         struct isl_obj obj;
2114
2115         obj = obj_read(s);
2116         if (obj.v)
2117                 isl_assert(s->ctx, obj.type == isl_obj_map ||
2118                                    obj.type == isl_obj_set, goto error);
2119
2120         if (obj.type == isl_obj_set)
2121                 obj.v = isl_map_from_range(obj.v);
2122
2123         return obj.v;
2124 error:
2125         obj.type->free(obj.v);
2126         return NULL;
2127 }
2128
2129 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2130 {
2131         struct isl_obj obj;
2132
2133         obj = obj_read(s);
2134         if (obj.v) {
2135                 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2136                         obj.v = isl_map_range(obj.v);
2137                         obj.type = isl_obj_set;
2138                 }
2139                 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2140         }
2141
2142         return obj.v;
2143 error:
2144         obj.type->free(obj.v);
2145         return NULL;
2146 }
2147
2148 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2149 {
2150         struct isl_obj obj;
2151
2152         obj = obj_read(s);
2153         if (obj.type == isl_obj_map) {
2154                 obj.type = isl_obj_union_map;
2155                 obj.v = isl_union_map_from_map(obj.v);
2156         }
2157         if (obj.type == isl_obj_set) {
2158                 obj.type = isl_obj_union_set;
2159                 obj.v = isl_union_set_from_set(obj.v);
2160         }
2161         if (obj.v && obj.type == isl_obj_union_set &&
2162             isl_union_set_is_empty(obj.v))
2163                 obj.type = isl_obj_union_map;
2164         if (obj.v && obj.type != isl_obj_union_map)
2165                 isl_die(s->ctx, isl_error_invalid, "invalid input", goto error);
2166
2167         return obj.v;
2168 error:
2169         obj.type->free(obj.v);
2170         return NULL;
2171 }
2172
2173 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2174 {
2175         struct isl_obj obj;
2176
2177         obj = obj_read(s);
2178         if (obj.type == isl_obj_set) {
2179                 obj.type = isl_obj_union_set;
2180                 obj.v = isl_union_set_from_set(obj.v);
2181         }
2182         if (obj.v)
2183                 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2184
2185         return obj.v;
2186 error:
2187         obj.type->free(obj.v);
2188         return NULL;
2189 }
2190
2191 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2192 {
2193         struct isl_obj obj;
2194         struct isl_map *map;
2195         struct isl_basic_map *bmap;
2196
2197         obj = obj_read(s);
2198         map = obj.v;
2199         if (!map)
2200                 return NULL;
2201
2202         isl_assert(map->ctx, map->n <= 1, goto error);
2203
2204         if (map->n == 0)
2205                 bmap = isl_basic_map_empty_like_map(map);
2206         else
2207                 bmap = isl_basic_map_copy(map->p[0]);
2208
2209         isl_map_free(map);
2210
2211         return bmap;
2212 error:
2213         isl_map_free(map);
2214         return NULL;
2215 }
2216
2217 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2218 {
2219         isl_basic_map *bmap;
2220         bmap = basic_map_read(s);
2221         if (!bmap)
2222                 return NULL;
2223         if (!isl_basic_map_may_be_set(bmap))
2224                 isl_die(s->ctx, isl_error_invalid,
2225                         "input is not a set", goto error);
2226         return isl_basic_map_range(bmap);
2227 error:
2228         isl_basic_map_free(bmap);
2229         return NULL;
2230 }
2231
2232 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2233         FILE *input)
2234 {
2235         struct isl_basic_map *bmap;
2236         struct isl_stream *s = isl_stream_new_file(ctx, input);
2237         if (!s)
2238                 return NULL;
2239         bmap = basic_map_read(s);
2240         isl_stream_free(s);
2241         return bmap;
2242 }
2243
2244 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2245         FILE *input)
2246 {
2247         isl_basic_set *bset;
2248         struct isl_stream *s = isl_stream_new_file(ctx, input);
2249         if (!s)
2250                 return NULL;
2251         bset = basic_set_read(s);
2252         isl_stream_free(s);
2253         return bset;
2254 }
2255
2256 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2257         const char *str)
2258 {
2259         struct isl_basic_map *bmap;
2260         struct isl_stream *s = isl_stream_new_str(ctx, str);
2261         if (!s)
2262                 return NULL;
2263         bmap = basic_map_read(s);
2264         isl_stream_free(s);
2265         return bmap;
2266 }
2267
2268 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2269         const char *str)
2270 {
2271         isl_basic_set *bset;
2272         struct isl_stream *s = isl_stream_new_str(ctx, str);
2273         if (!s)
2274                 return NULL;
2275         bset = basic_set_read(s);
2276         isl_stream_free(s);
2277         return bset;
2278 }
2279
2280 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2281         FILE *input)
2282 {
2283         struct isl_map *map;
2284         struct isl_stream *s = isl_stream_new_file(ctx, input);
2285         if (!s)
2286                 return NULL;
2287         map = isl_stream_read_map(s);
2288         isl_stream_free(s);
2289         return map;
2290 }
2291
2292 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2293         const char *str)
2294 {
2295         struct isl_map *map;
2296         struct isl_stream *s = isl_stream_new_str(ctx, str);
2297         if (!s)
2298                 return NULL;
2299         map = isl_stream_read_map(s);
2300         isl_stream_free(s);
2301         return map;
2302 }
2303
2304 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2305         FILE *input)
2306 {
2307         isl_set *set;
2308         struct isl_stream *s = isl_stream_new_file(ctx, input);
2309         if (!s)
2310                 return NULL;
2311         set = isl_stream_read_set(s);
2312         isl_stream_free(s);
2313         return set;
2314 }
2315
2316 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2317         const char *str)
2318 {
2319         isl_set *set;
2320         struct isl_stream *s = isl_stream_new_str(ctx, str);
2321         if (!s)
2322                 return NULL;
2323         set = isl_stream_read_set(s);
2324         isl_stream_free(s);
2325         return set;
2326 }
2327
2328 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2329         FILE *input)
2330 {
2331         isl_union_map *umap;
2332         struct isl_stream *s = isl_stream_new_file(ctx, input);
2333         if (!s)
2334                 return NULL;
2335         umap = isl_stream_read_union_map(s);
2336         isl_stream_free(s);
2337         return umap;
2338 }
2339
2340 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2341                 const char *str)
2342 {
2343         isl_union_map *umap;
2344         struct isl_stream *s = isl_stream_new_str(ctx, str);
2345         if (!s)
2346                 return NULL;
2347         umap = isl_stream_read_union_map(s);
2348         isl_stream_free(s);
2349         return umap;
2350 }
2351
2352 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2353         FILE *input)
2354 {
2355         isl_union_set *uset;
2356         struct isl_stream *s = isl_stream_new_file(ctx, input);
2357         if (!s)
2358                 return NULL;
2359         uset = isl_stream_read_union_set(s);
2360         isl_stream_free(s);
2361         return uset;
2362 }
2363
2364 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2365                 const char *str)
2366 {
2367         isl_union_set *uset;
2368         struct isl_stream *s = isl_stream_new_str(ctx, str);
2369         if (!s)
2370                 return NULL;
2371         uset = isl_stream_read_union_set(s);
2372         isl_stream_free(s);
2373         return uset;
2374 }
2375
2376 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2377 {
2378         struct isl_vec *vec = NULL;
2379         struct isl_token *tok;
2380         unsigned size;
2381         int j;
2382
2383         tok = isl_stream_next_token(s);
2384         if (!tok || tok->type != ISL_TOKEN_VALUE) {
2385                 isl_stream_error(s, tok, "expecting vector length");
2386                 goto error;
2387         }
2388
2389         size = isl_int_get_si(tok->u.v);
2390         isl_token_free(tok);
2391
2392         vec = isl_vec_alloc(s->ctx, size);
2393
2394         for (j = 0; j < size; ++j) {
2395                 tok = isl_stream_next_token(s);
2396                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2397                         isl_stream_error(s, tok, "expecting constant value");
2398                         goto error;
2399                 }
2400                 isl_int_set(vec->el[j], tok->u.v);
2401                 isl_token_free(tok);
2402         }
2403
2404         return vec;
2405 error:
2406         isl_token_free(tok);
2407         isl_vec_free(vec);
2408         return NULL;
2409 }
2410
2411 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2412 {
2413         return isl_vec_read_polylib(s);
2414 }
2415
2416 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2417 {
2418         isl_vec *v;
2419         struct isl_stream *s = isl_stream_new_file(ctx, input);
2420         if (!s)
2421                 return NULL;
2422         v = vec_read(s);
2423         isl_stream_free(s);
2424         return v;
2425 }
2426
2427 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2428         struct isl_stream *s)
2429 {
2430         struct isl_obj obj;
2431
2432         obj = obj_read(s);
2433         if (obj.v)
2434                 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2435                            goto error);
2436
2437         return obj.v;
2438 error:
2439         obj.type->free(obj.v);
2440         return NULL;
2441 }
2442
2443 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2444                 const char *str)
2445 {
2446         isl_pw_qpolynomial *pwqp;
2447         struct isl_stream *s = isl_stream_new_str(ctx, str);
2448         if (!s)
2449                 return NULL;
2450         pwqp = isl_stream_read_pw_qpolynomial(s);
2451         isl_stream_free(s);
2452         return pwqp;
2453 }
2454
2455 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2456                 FILE *input)
2457 {
2458         isl_pw_qpolynomial *pwqp;
2459         struct isl_stream *s = isl_stream_new_file(ctx, input);
2460         if (!s)
2461                 return NULL;
2462         pwqp = isl_stream_read_pw_qpolynomial(s);
2463         isl_stream_free(s);
2464         return pwqp;
2465 }
2466
2467 /* Read an affine expression from "s" with domain (space) "dom".
2468  * We call accept_affine to parse a possibly piecewise affine expression
2469  * and then check that the result is a single affine expression on
2470  * a universe domain.
2471  */
2472 static __isl_give isl_aff *read_aff_with_dom(struct isl_stream *s,
2473         __isl_take isl_set *dom, struct vars *v)
2474 {
2475         isl_aff *aff = NULL;
2476         isl_pw_aff *pwaff = NULL;
2477
2478         if (!isl_set_plain_is_universe(dom))
2479                 isl_die(s->ctx, isl_error_invalid,
2480                         "expecting universe domain", goto error);
2481
2482         if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2483                 goto error;
2484
2485         if (isl_stream_eat(s, '['))
2486                 goto error;
2487
2488         pwaff = accept_affine(s, isl_set_get_space(dom), v);
2489
2490         if (isl_stream_eat(s, ']'))
2491                 goto error;
2492         if (isl_stream_eat(s, '}'))
2493                 goto error;
2494
2495         if (!pwaff)
2496                 goto error;
2497
2498         if (pwaff->n != 1)
2499                 isl_die(s->ctx, isl_error_invalid,
2500                         "expecting single affine expression", goto error);
2501         if (!isl_set_plain_is_universe(pwaff->p[0].set))
2502                 isl_die(s->ctx, isl_error_invalid,
2503                         "expecting universe domain", goto error);
2504
2505         aff = isl_aff_copy(pwaff->p[0].aff);
2506
2507         vars_free(v);
2508         isl_pw_aff_free(pwaff);
2509         isl_set_free(dom);
2510         return aff;
2511 error:
2512         vars_free(v);
2513         isl_pw_aff_free(pwaff);
2514         isl_set_free(dom);
2515         return NULL;
2516 }
2517
2518 /* Is the next token an identifer not in "v"?
2519  */
2520 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2521 {
2522         int n = v->n;
2523         int fresh;
2524         struct isl_token *tok;
2525
2526         tok = isl_stream_next_token(s);
2527         if (!tok)
2528                 return 0;
2529         fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2530         isl_stream_push_token(s, tok);
2531
2532         vars_drop(v, v->n - n);
2533
2534         return fresh;
2535 }
2536
2537 /* First read the domain of the affine expression, which may be
2538  * a parameter space or a set.
2539  * The tricky part is that we don't know if the domain is a set or not,
2540  * so when we are trying to read the domain, we may actually be reading
2541  * the affine expression itself (defined on a parameter domains)
2542  * If the tuple we are reading is named, we assume it's the domain.
2543  * Also, if inside the tuple, the first thing we find is a nested tuple
2544  * or a new identifier, we again assume it's the domain.
2545  * Otherwise, we assume we are reading an affine expression.
2546  */
2547 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2548         __isl_take isl_set *dom, struct vars *v)
2549 {
2550         struct isl_token *tok;
2551
2552         tok = isl_stream_next_token(s);
2553         if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2554                 isl_stream_push_token(s, tok);
2555                 return read_map_tuple(s, dom, isl_dim_set, v);
2556         }
2557         if (!tok || tok->type != '[') {
2558                 isl_stream_error(s, tok, "expecting '['");
2559                 goto error;
2560         }
2561         if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2562                 isl_stream_push_token(s, tok);
2563                 dom = read_map_tuple(s, dom, isl_dim_set, v);
2564         } else
2565                 isl_stream_push_token(s, tok);
2566
2567         return dom;
2568 error:
2569         if (tok)
2570                 isl_stream_push_token(s, tok);
2571         vars_free(v);
2572         isl_set_free(dom);
2573         return NULL;
2574 }
2575
2576 /* Read an affine expression from "s".
2577  * We first read the domain of the affine expression, which may be
2578  * a parameter space or a set, and then call read_aff_with_dom.
2579  */
2580 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2581 {
2582         struct vars *v;
2583         isl_set *dom = NULL;
2584
2585         v = vars_new(s->ctx);
2586         if (!v)
2587                 return NULL;
2588
2589         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2590         if (next_is_tuple(s)) {
2591                 dom = read_map_tuple(s, dom, isl_dim_param, v);
2592                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2593                         goto error;
2594         }
2595         if (isl_stream_eat(s, '{'))
2596                 goto error;
2597
2598         dom = read_aff_domain(s, dom, v);
2599         return read_aff_with_dom(s, dom, v);
2600 error:
2601         vars_free(v);
2602         isl_set_free(dom);
2603         return NULL;
2604 }
2605
2606 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2607  */
2608 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2609         __isl_take isl_set *dom, struct vars *v)
2610 {
2611         isl_pw_aff *pwaff = NULL;
2612
2613         if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2614                 goto error;
2615
2616         if (isl_stream_eat(s, '['))
2617                 goto error;
2618
2619         pwaff = accept_affine(s, isl_set_get_space(dom), v);
2620
2621         if (isl_stream_eat(s, ']'))
2622                 goto error;
2623
2624         dom = read_optional_disjuncts(s, dom, v);
2625         pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2626
2627         return pwaff;
2628 error:
2629         isl_set_free(dom);
2630         isl_pw_aff_free(pwaff);
2631         return NULL;
2632 }
2633
2634 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
2635 {
2636         struct vars *v;
2637         isl_set *dom = NULL;
2638         isl_set *aff_dom;
2639         isl_pw_aff *pa = NULL;
2640         int n;
2641
2642         v = vars_new(s->ctx);
2643         if (!v)
2644                 return NULL;
2645
2646         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2647         if (next_is_tuple(s)) {
2648                 dom = read_map_tuple(s, dom, isl_dim_param, v);
2649                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2650                         goto error;
2651         }
2652         if (isl_stream_eat(s, '{'))
2653                 goto error;
2654
2655         n = v->n;
2656         aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2657         pa = read_pw_aff_with_dom(s, aff_dom, v);
2658         vars_drop(v, v->n - n);
2659
2660         while (isl_stream_eat_if_available(s, ';')) {
2661                 isl_pw_aff *pa_i;
2662
2663                 n = v->n;
2664                 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2665                 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
2666                 vars_drop(v, v->n - n);
2667
2668                 pa = isl_pw_aff_union_add(pa, pa_i);
2669         }
2670
2671         if (isl_stream_eat(s, '}'))
2672                 goto error;
2673
2674         vars_free(v);
2675         isl_set_free(dom);
2676         return pa;
2677 error:
2678         vars_free(v);
2679         isl_set_free(dom);
2680         isl_pw_aff_free(pa);
2681         return NULL;
2682 }
2683
2684 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
2685 {
2686         isl_aff *aff;
2687         struct isl_stream *s = isl_stream_new_str(ctx, str);
2688         if (!s)
2689                 return NULL;
2690         aff = isl_stream_read_aff(s);
2691         isl_stream_free(s);
2692         return aff;
2693 }
2694
2695 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
2696 {
2697         isl_pw_aff *pa;
2698         struct isl_stream *s = isl_stream_new_str(ctx, str);
2699         if (!s)
2700                 return NULL;
2701         pa = isl_stream_read_pw_aff(s);
2702         isl_stream_free(s);
2703         return pa;
2704 }
2705
2706 /* Read an isl_pw_multi_aff from "s".
2707  * We currently read a generic object and if it turns out to be a set or
2708  * a map, we convert that to an isl_pw_multi_aff.
2709  * It would be more efficient if we were to construct the isl_pw_multi_aff
2710  * directly.
2711  */
2712 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
2713 {
2714         struct isl_obj obj;
2715
2716         obj = obj_read(s);
2717         if (!obj.v)
2718                 return NULL;
2719
2720         if (obj.type == isl_obj_map)
2721                 return isl_pw_multi_aff_from_map(obj.v);
2722         if (obj.type == isl_obj_set)
2723                 return isl_pw_multi_aff_from_set(obj.v);
2724
2725         obj.type->free(obj.v);
2726         isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2727                 return NULL);
2728 }
2729
2730 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
2731         const char *str)
2732 {
2733         isl_pw_multi_aff *pma;
2734         struct isl_stream *s = isl_stream_new_str(ctx, str);
2735         if (!s)
2736                 return NULL;
2737         pma = isl_stream_read_pw_multi_aff(s);
2738         isl_stream_free(s);
2739         return pma;
2740 }
2741
2742 /* Read a multi-affine expression from "s".
2743  * We call isl_stream_read_pw_multi_aff to parse a possibly piecewise
2744  * multi-affine expression and then check that the result is
2745  * a single multi-affine expression on a universe domain.
2746  */
2747 __isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s)
2748 {
2749         isl_pw_multi_aff *pma;
2750         isl_multi_aff *maff;
2751
2752         pma = isl_stream_read_pw_multi_aff(s);
2753         if (!pma)
2754                 return NULL;
2755         if (pma->n != 1)
2756                 isl_die(s->ctx, isl_error_invalid,
2757                         "expecting single list of affine expressions",
2758                         return isl_pw_multi_aff_free(pma));
2759         if (!isl_set_plain_is_universe(pma->p[0].set))
2760                 isl_die(s->ctx, isl_error_invalid, "expecting universe domain",
2761                         return isl_pw_multi_aff_free(pma));
2762         maff = isl_multi_aff_copy(pma->p[0].maff);
2763         isl_pw_multi_aff_free(pma);
2764         return maff;
2765 }
2766
2767 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
2768         const char *str)
2769 {
2770         isl_multi_aff *maff;
2771         struct isl_stream *s = isl_stream_new_str(ctx, str);
2772         if (!s)
2773                 return NULL;
2774         maff = isl_stream_read_multi_aff(s);
2775         isl_stream_free(s);
2776         return maff;
2777 }
2778
2779 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
2780         struct isl_stream *s)
2781 {
2782         struct isl_obj obj;
2783
2784         obj = obj_read(s);
2785         if (obj.type == isl_obj_pw_qpolynomial) {
2786                 obj.type = isl_obj_union_pw_qpolynomial;
2787                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2788         }
2789         if (obj.v)
2790                 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
2791                            goto error);
2792
2793         return obj.v;
2794 error:
2795         obj.type->free(obj.v);
2796         return NULL;
2797 }
2798
2799 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
2800         isl_ctx *ctx, const char *str)
2801 {
2802         isl_union_pw_qpolynomial *upwqp;
2803         struct isl_stream *s = isl_stream_new_str(ctx, str);
2804         if (!s)
2805                 return NULL;
2806         upwqp = isl_stream_read_union_pw_qpolynomial(s);
2807         isl_stream_free(s);
2808         return upwqp;
2809 }