isl_input.c

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