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