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