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_NOT) ||
1068             isl_stream_next_token_is(s, ISL_TOKEN_TRUE) ||
1069             isl_stream_next_token_is(s, ISL_TOKEN_FALSE) ||
1070             isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1071                 map = read_disjuncts(s, v, map);
1072                 if (isl_stream_eat(s, ')'))
1073                         goto error;
1074                 tok->type = ISL_TOKEN_MAP;
1075                 tok->u.map = map;
1076                 isl_stream_push_token(s, tok);
1077                 return 0;
1078         }
1079
1080         tok2 = isl_stream_next_token(s);
1081         if (!tok2)
1082                 goto error;
1083         line = tok2->line;
1084         col = tok2->col;
1085         isl_stream_push_token(s, tok2);
1086
1087         pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
1088         if (!pwaff)
1089                 goto error;
1090
1091         tok2 = isl_token_new(s->ctx, line, col, 0);
1092         if (!tok2)
1093                 goto error2;
1094         tok2->type = ISL_TOKEN_AFF;
1095         tok2->u.pwaff = pwaff;
1096
1097         if (isl_stream_eat_if_available(s, ')')) {
1098                 isl_stream_push_token(s, tok2);
1099                 isl_token_free(tok);
1100                 isl_map_free(map);
1101                 return 0;
1102         }
1103
1104         isl_stream_push_token(s, tok2);
1105
1106         map = read_disjuncts(s, v, map);
1107         if (isl_stream_eat(s, ')'))
1108                 goto error;
1109
1110         tok->type = ISL_TOKEN_MAP;
1111         tok->u.map = map;
1112         isl_stream_push_token(s, tok);
1113
1114         return 0;
1115 error2:
1116         isl_pw_aff_free(pwaff);
1117 error:
1118         isl_token_free(tok);
1119         isl_map_free(map);
1120         return -1;
1121 }
1122
1123 static __isl_give isl_map *read_conjunct(struct isl_stream *s,
1124         struct vars *v, __isl_take isl_map *map)
1125 {
1126         if (isl_stream_next_token_is(s, '('))
1127                 if (resolve_paren_expr(s, v, isl_map_copy(map)))
1128                         goto error;
1129
1130         if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1131                 struct isl_token *tok;
1132                 tok = isl_stream_next_token(s);
1133                 if (!tok)
1134                         goto error;
1135                 isl_map_free(map);
1136                 map = isl_map_copy(tok->u.map);
1137                 isl_token_free(tok);
1138                 return map;
1139         }
1140
1141         if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1142                 return read_exists(s, v, map);
1143
1144         if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1145                 return map;
1146
1147         if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1148                 isl_space *dim = isl_map_get_space(map);
1149                 isl_map_free(map);
1150                 return isl_map_empty(dim);
1151         }
1152
1153         return add_constraint(s, v, map);
1154 error:
1155         isl_map_free(map);
1156         return NULL;
1157 }
1158
1159 static __isl_give isl_map *read_conjuncts(struct isl_stream *s,
1160         struct vars *v, __isl_take isl_map *map)
1161 {
1162         isl_map *res;
1163         int negate;
1164
1165         negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1166         res = read_conjunct(s, v, isl_map_copy(map));
1167         if (negate)
1168                 res = isl_map_subtract(isl_map_copy(map), res);
1169
1170         while (isl_stream_eat_if_available(s, ISL_TOKEN_AND)) {
1171                 isl_map *res_i;
1172
1173                 negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1174                 res_i = read_conjunct(s, v, isl_map_copy(map));
1175                 if (negate)
1176                         res = isl_map_subtract(res, res_i);
1177                 else
1178                         res = isl_map_intersect(res, res_i);
1179         }
1180
1181         isl_map_free(map);
1182         return res;
1183 }
1184
1185 static struct isl_map *read_disjuncts(struct isl_stream *s,
1186         struct vars *v, __isl_take isl_map *map)
1187 {
1188         isl_map *res;
1189
1190         if (isl_stream_next_token_is(s, '}')) {
1191                 isl_space *dim = isl_map_get_space(map);
1192                 isl_map_free(map);
1193                 return isl_map_universe(dim);
1194         }
1195
1196         res = read_conjuncts(s, v, isl_map_copy(map));
1197         while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1198                 isl_map *res_i;
1199
1200                 res_i = read_conjuncts(s, v, isl_map_copy(map));
1201                 res = isl_map_union(res, res_i);
1202         }
1203
1204         isl_map_free(map);
1205         return res;
1206 }
1207
1208 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1209 {
1210         if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1211                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1212                            isl_basic_map_dim(bmap, isl_dim_in) + pos;
1213         pos -= isl_basic_map_dim(bmap, isl_dim_out);
1214
1215         if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1216                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1217         pos -= isl_basic_map_dim(bmap, isl_dim_in);
1218
1219         if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1220                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1221                            isl_basic_map_dim(bmap, isl_dim_in) +
1222                            isl_basic_map_dim(bmap, isl_dim_out) + pos;
1223         pos -= isl_basic_map_dim(bmap, isl_dim_div);
1224
1225         if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1226                 return 1 + pos;
1227
1228         return 0;
1229 }
1230
1231 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1232         struct isl_stream *s, __isl_take isl_basic_map *bmap)
1233 {
1234         int j;
1235         struct isl_token *tok;
1236         int type;
1237         int k;
1238         isl_int *c;
1239         unsigned nparam;
1240         unsigned dim;
1241
1242         if (!bmap)
1243                 return NULL;
1244
1245         nparam = isl_basic_map_dim(bmap, isl_dim_param);
1246         dim = isl_basic_map_dim(bmap, isl_dim_out);
1247
1248         tok = isl_stream_next_token(s);
1249         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1250                 isl_stream_error(s, tok, "expecting coefficient");
1251                 if (tok)
1252                         isl_stream_push_token(s, tok);
1253                 goto error;
1254         }
1255         if (!tok->on_new_line) {
1256                 isl_stream_error(s, tok, "coefficient should appear on new line");
1257                 isl_stream_push_token(s, tok);
1258                 goto error;
1259         }
1260
1261         type = isl_int_get_si(tok->u.v);
1262         isl_token_free(tok);
1263
1264         isl_assert(s->ctx, type == 0 || type == 1, goto error);
1265         if (type == 0) {
1266                 k = isl_basic_map_alloc_equality(bmap);
1267                 c = bmap->eq[k];
1268         } else {
1269                 k = isl_basic_map_alloc_inequality(bmap);
1270                 c = bmap->ineq[k];
1271         }
1272         if (k < 0)
1273                 goto error;
1274
1275         for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
1276                 int pos;
1277                 tok = isl_stream_next_token(s);
1278                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1279                         isl_stream_error(s, tok, "expecting coefficient");
1280                         if (tok)
1281                                 isl_stream_push_token(s, tok);
1282                         goto error;
1283                 }
1284                 if (tok->on_new_line) {
1285                         isl_stream_error(s, tok,
1286                                 "coefficient should not appear on new line");
1287                         isl_stream_push_token(s, tok);
1288                         goto error;
1289                 }
1290                 pos = polylib_pos_to_isl_pos(bmap, j);
1291                 isl_int_set(c[pos], tok->u.v);
1292                 isl_token_free(tok);
1293         }
1294
1295         return bmap;
1296 error:
1297         isl_basic_map_free(bmap);
1298         return NULL;
1299 }
1300
1301 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s)
1302 {
1303         int i;
1304         struct isl_token *tok;
1305         struct isl_token *tok2;
1306         int n_row, n_col;
1307         int on_new_line;
1308         unsigned in = 0, out, local = 0;
1309         struct isl_basic_map *bmap = NULL;
1310         int nparam = 0;
1311
1312         tok = isl_stream_next_token(s);
1313         if (!tok) {
1314                 isl_stream_error(s, NULL, "unexpected EOF");
1315                 return NULL;
1316         }
1317         tok2 = isl_stream_next_token(s);
1318         if (!tok2) {
1319                 isl_token_free(tok);
1320                 isl_stream_error(s, NULL, "unexpected EOF");
1321                 return NULL;
1322         }
1323         if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1324                 isl_stream_push_token(s, tok2);
1325                 isl_stream_push_token(s, tok);
1326                 isl_stream_error(s, NULL,
1327                                  "expecting constraint matrix dimensions");
1328                 return NULL;
1329         }
1330         n_row = isl_int_get_si(tok->u.v);
1331         n_col = isl_int_get_si(tok2->u.v);
1332         on_new_line = tok2->on_new_line;
1333         isl_token_free(tok2);
1334         isl_token_free(tok);
1335         isl_assert(s->ctx, !on_new_line, return NULL);
1336         isl_assert(s->ctx, n_row >= 0, return NULL);
1337         isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1338         tok = isl_stream_next_token_on_same_line(s);
1339         if (tok) {
1340                 if (tok->type != ISL_TOKEN_VALUE) {
1341                         isl_stream_error(s, tok,
1342                                     "expecting number of output dimensions");
1343                         isl_stream_push_token(s, tok);
1344                         goto error;
1345                 }
1346                 out = isl_int_get_si(tok->u.v);
1347                 isl_token_free(tok);
1348
1349                 tok = isl_stream_next_token_on_same_line(s);
1350                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1351                         isl_stream_error(s, tok,
1352                                     "expecting number of input dimensions");
1353                         if (tok)
1354                                 isl_stream_push_token(s, tok);
1355                         goto error;
1356                 }
1357                 in = isl_int_get_si(tok->u.v);
1358                 isl_token_free(tok);
1359
1360                 tok = isl_stream_next_token_on_same_line(s);
1361                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1362                         isl_stream_error(s, tok,
1363                                     "expecting number of existentials");
1364                         if (tok)
1365                                 isl_stream_push_token(s, tok);
1366                         goto error;
1367                 }
1368                 local = isl_int_get_si(tok->u.v);
1369                 isl_token_free(tok);
1370
1371                 tok = isl_stream_next_token_on_same_line(s);
1372                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1373                         isl_stream_error(s, tok,
1374                                     "expecting number of parameters");
1375                         if (tok)
1376                                 isl_stream_push_token(s, tok);
1377                         goto error;
1378                 }
1379                 nparam = isl_int_get_si(tok->u.v);
1380                 isl_token_free(tok);
1381                 if (n_col != 1 + out + in + local + nparam + 1) {
1382                         isl_stream_error(s, NULL,
1383                                     "dimensions don't match");
1384                         goto error;
1385                 }
1386         } else
1387                 out = n_col - 2 - nparam;
1388         bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
1389         if (!bmap)
1390                 return NULL;
1391
1392         for (i = 0; i < local; ++i) {
1393                 int k = isl_basic_map_alloc_div(bmap);
1394                 if (k < 0)
1395                         goto error;
1396                 isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
1397         }
1398
1399         for (i = 0; i < n_row; ++i)
1400                 bmap = basic_map_read_polylib_constraint(s, bmap);
1401
1402         tok = isl_stream_next_token_on_same_line(s);
1403         if (tok) {
1404                 isl_stream_error(s, tok, "unexpected extra token on line");
1405                 isl_stream_push_token(s, tok);
1406                 goto error;
1407         }
1408
1409         bmap = isl_basic_map_simplify(bmap);
1410         bmap = isl_basic_map_finalize(bmap);
1411         return bmap;
1412 error:
1413         isl_basic_map_free(bmap);
1414         return NULL;
1415 }
1416
1417 static struct isl_map *map_read_polylib(struct isl_stream *s)
1418 {
1419         struct isl_token *tok;
1420         struct isl_token *tok2;
1421         int i, n;
1422         struct isl_map *map;
1423
1424         tok = isl_stream_next_token(s);
1425         if (!tok) {
1426                 isl_stream_error(s, NULL, "unexpected EOF");
1427                 return NULL;
1428         }
1429         tok2 = isl_stream_next_token_on_same_line(s);
1430         if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
1431                 isl_stream_push_token(s, tok2);
1432                 isl_stream_push_token(s, tok);
1433                 return isl_map_from_basic_map(basic_map_read_polylib(s));
1434         }
1435         if (tok2) {
1436                 isl_stream_error(s, tok2, "unexpected token");
1437                 isl_stream_push_token(s, tok2);
1438                 isl_stream_push_token(s, tok);
1439                 return NULL;
1440         }
1441         n = isl_int_get_si(tok->u.v);
1442         isl_token_free(tok);
1443
1444         isl_assert(s->ctx, n >= 1, return NULL);
1445
1446         map = isl_map_from_basic_map(basic_map_read_polylib(s));
1447
1448         for (i = 1; map && i < n; ++i)
1449                 map = isl_map_union(map,
1450                         isl_map_from_basic_map(basic_map_read_polylib(s)));
1451
1452         return map;
1453 }
1454
1455 static int optional_power(struct isl_stream *s)
1456 {
1457         int pow;
1458         struct isl_token *tok;
1459
1460         tok = isl_stream_next_token(s);
1461         if (!tok)
1462                 return 1;
1463         if (tok->type != '^') {
1464                 isl_stream_push_token(s, tok);
1465                 return 1;
1466         }
1467         isl_token_free(tok);
1468         tok = isl_stream_next_token(s);
1469         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1470                 isl_stream_error(s, tok, "expecting exponent");
1471                 if (tok)
1472                         isl_stream_push_token(s, tok);
1473                 return 1;
1474         }
1475         pow = isl_int_get_si(tok->u.v);
1476         isl_token_free(tok);
1477         return pow;
1478 }
1479
1480 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1481         __isl_keep isl_map *map, struct vars *v);
1482
1483 static __isl_give isl_pw_qpolynomial *read_factor(struct isl_stream *s,
1484         __isl_keep isl_map *map, struct vars *v)
1485 {
1486         isl_pw_qpolynomial *pwqp;
1487         struct isl_token *tok;
1488
1489         tok = next_token(s);
1490         if (!tok) {
1491                 isl_stream_error(s, NULL, "unexpected EOF");
1492                 return NULL;
1493         }
1494         if (tok->type == '(') {
1495                 int pow;
1496
1497                 isl_token_free(tok);
1498                 pwqp = read_term(s, map, v);
1499                 if (!pwqp)
1500                         return NULL;
1501                 if (isl_stream_eat(s, ')'))
1502                         goto error;
1503                 pow = optional_power(s);
1504                 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1505         } else if (tok->type == ISL_TOKEN_VALUE) {
1506                 struct isl_token *tok2;
1507                 tok2 = isl_stream_next_token(s);
1508                 isl_qpolynomial *qp;
1509                 if (tok2 && tok2->type == '/') {
1510                         isl_token_free(tok2);
1511                         tok2 = next_token(s);
1512                         if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
1513                                 isl_stream_error(s, tok2, "expected denominator");
1514                                 isl_token_free(tok);
1515                                 isl_token_free(tok2);
1516                                 return NULL;
1517                         }
1518                         qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
1519                                                     tok->u.v, tok2->u.v);
1520                         isl_token_free(tok2);
1521                 } else {
1522                         isl_stream_push_token(s, tok2);
1523                         qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
1524                                                 tok->u.v);
1525                 }
1526                 isl_token_free(tok);
1527                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1528         } else if (tok->type == ISL_TOKEN_INFTY) {
1529                 isl_qpolynomial *qp;
1530                 isl_token_free(tok);
1531                 qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
1532                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1533         } else if (tok->type == ISL_TOKEN_NAN) {
1534                 isl_qpolynomial *qp;
1535                 isl_token_free(tok);
1536                 qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
1537                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1538         } else if (tok->type == ISL_TOKEN_IDENT) {
1539                 int n = v->n;
1540                 int pos = vars_pos(v, tok->u.s, -1);
1541                 int pow;
1542                 isl_qpolynomial *qp;
1543                 if (pos < 0) {
1544                         isl_token_free(tok);
1545                         return NULL;
1546                 }
1547                 if (pos >= n) {
1548                         vars_drop(v, v->n - n);
1549                         isl_stream_error(s, tok, "unknown identifier");
1550                         isl_token_free(tok);
1551                         return NULL;
1552                 }
1553                 isl_token_free(tok);
1554                 pow = optional_power(s);
1555                 qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
1556                 pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
1557         } else if (tok->type == '[') {
1558                 isl_pw_aff *pwaff;
1559                 int pow;
1560
1561                 isl_stream_push_token(s, tok);
1562                 pwaff = accept_div(s, isl_map_get_space(map), v);
1563                 pow = optional_power(s);
1564                 pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
1565                 pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
1566         } else if (tok->type == '-') {
1567                 isl_token_free(tok);
1568                 pwqp = read_factor(s, map, v);
1569                 pwqp = isl_pw_qpolynomial_neg(pwqp);
1570         } else {
1571                 isl_stream_error(s, tok, "unexpected isl_token");
1572                 isl_stream_push_token(s, tok);
1573                 return NULL;
1574         }
1575
1576         if (isl_stream_eat_if_available(s, '*') ||
1577             isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) {
1578                 isl_pw_qpolynomial *pwqp2;
1579
1580                 pwqp2 = read_factor(s, map, v);
1581                 pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
1582         }
1583
1584         return pwqp;
1585 error:
1586         isl_pw_qpolynomial_free(pwqp);
1587         return NULL;
1588 }
1589
1590 static __isl_give isl_pw_qpolynomial *read_term(struct isl_stream *s,
1591         __isl_keep isl_map *map, struct vars *v)
1592 {
1593         struct isl_token *tok;
1594         isl_pw_qpolynomial *pwqp;
1595
1596         pwqp = read_factor(s, map, v);
1597
1598         for (;;) {
1599                 tok = next_token(s);
1600                 if (!tok)
1601                         return pwqp;
1602
1603                 if (tok->type == '+') {
1604                         isl_pw_qpolynomial *pwqp2;
1605
1606                         isl_token_free(tok);
1607                         pwqp2 = read_factor(s, map, v);
1608                         pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1609                 } else if (tok->type == '-') {
1610                         isl_pw_qpolynomial *pwqp2;
1611
1612                         isl_token_free(tok);
1613                         pwqp2 = read_factor(s, map, v);
1614                         pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
1615                 } else if (tok->type == ISL_TOKEN_VALUE &&
1616                             isl_int_is_neg(tok->u.v)) {
1617                         isl_pw_qpolynomial *pwqp2;
1618
1619                         isl_stream_push_token(s, tok);
1620                         pwqp2 = read_factor(s, map, v);
1621                         pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
1622                 } else {
1623                         isl_stream_push_token(s, tok);
1624                         break;
1625                 }
1626         }
1627
1628         return pwqp;
1629 }
1630
1631 static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s,
1632         __isl_take isl_map *map, struct vars *v)
1633 {
1634         struct isl_token *tok;
1635
1636         tok = isl_stream_next_token(s);
1637         if (!tok) {
1638                 isl_stream_error(s, NULL, "unexpected EOF");
1639                 goto error;
1640         }
1641         if (tok->type == ':' ||
1642             (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) {
1643                 isl_token_free(tok);
1644                 map = read_disjuncts(s, v, map);
1645         } else
1646                 isl_stream_push_token(s, tok);
1647
1648         return map;
1649 error:
1650         isl_map_free(map);
1651         return NULL;
1652 }
1653
1654 static struct isl_obj obj_read_poly(struct isl_stream *s,
1655         __isl_take isl_map *map, struct vars *v, int n)
1656 {
1657         struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
1658         isl_pw_qpolynomial *pwqp;
1659         struct isl_set *set;
1660
1661         pwqp = read_term(s, map, v);
1662         map = read_optional_disjuncts(s, map, v);
1663         set = isl_map_range(map);
1664
1665         pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
1666
1667         vars_drop(v, v->n - n);
1668
1669         obj.v = pwqp;
1670         return obj;
1671 }
1672
1673 static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s,
1674         __isl_take isl_set *set, struct vars *v, int n)
1675 {
1676         struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
1677         isl_pw_qpolynomial *pwqp;
1678         isl_pw_qpolynomial_fold *pwf = NULL;
1679
1680         if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
1681                 return obj_read_poly(s, set, v, n);
1682
1683         if (isl_stream_eat(s, '('))
1684                 goto error;
1685
1686         pwqp = read_term(s, set, v);
1687         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
1688
1689         while (isl_stream_eat_if_available(s, ',')) {
1690                 isl_pw_qpolynomial_fold *pwf_i;
1691                 pwqp = read_term(s, set, v);
1692                 pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
1693                                                                         pwqp);
1694                 pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
1695         }
1696
1697         if (isl_stream_eat(s, ')'))
1698                 goto error;
1699
1700         set = read_optional_disjuncts(s, set, v);
1701         pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
1702
1703         vars_drop(v, v->n - n);
1704
1705         obj.v = pwf;
1706         return obj;
1707 error:
1708         isl_set_free(set);
1709         isl_pw_qpolynomial_fold_free(pwf);
1710         obj.type = isl_obj_none;
1711         return obj;
1712 }
1713
1714 static int is_rational(struct isl_stream *s)
1715 {
1716         struct isl_token *tok;
1717
1718         tok = isl_stream_next_token(s);
1719         if (!tok)
1720                 return 0;
1721         if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) {
1722                 isl_token_free(tok);
1723                 isl_stream_eat(s, ':');
1724                 return 1;
1725         }
1726
1727         isl_stream_push_token(s, tok);
1728
1729         return 0;
1730 }
1731
1732 static struct isl_obj obj_read_body(struct isl_stream *s,
1733         __isl_take isl_map *map, struct vars *v)
1734 {
1735         struct isl_token *tok;
1736         struct isl_obj obj = { isl_obj_set, NULL };
1737         int n = v->n;
1738
1739         if (is_rational(s))
1740                 map = isl_map_set_rational(map);
1741
1742         if (isl_stream_next_token_is(s, ':')) {
1743                 obj.type = isl_obj_set;
1744                 obj.v = read_optional_disjuncts(s, map, v);
1745                 return obj;
1746         }
1747
1748         if (!next_is_tuple(s))
1749                 return obj_read_poly_or_fold(s, map, v, n);
1750
1751         map = read_tuple(s, map, isl_dim_in, v);
1752         if (!map)
1753                 goto error;
1754         tok = isl_stream_next_token(s);
1755         if (tok && tok->type == ISL_TOKEN_TO) {
1756                 obj.type = isl_obj_map;
1757                 isl_token_free(tok);
1758                 if (!next_is_tuple(s)) {
1759                         isl_set *set = isl_map_domain(map);
1760                         return obj_read_poly_or_fold(s, set, v, n);
1761                 }
1762                 map = read_tuple(s, map, isl_dim_out, v);
1763                 if (!map)
1764                         goto error;
1765         } else {
1766                 map = isl_map_reverse(map);
1767                 if (tok)
1768                         isl_stream_push_token(s, tok);
1769         }
1770
1771         map = read_optional_disjuncts(s, map, v);
1772
1773         vars_drop(v, v->n - n);
1774
1775         obj.v = map;
1776         return obj;
1777 error:
1778         isl_map_free(map);
1779         obj.type = isl_obj_none;
1780         return obj;
1781 }
1782
1783 static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
1784 {
1785         if (obj.type == isl_obj_map) {
1786                 obj.v = isl_union_map_from_map(obj.v);
1787                 obj.type = isl_obj_union_map;
1788         } else if (obj.type == isl_obj_set) {
1789                 obj.v = isl_union_set_from_set(obj.v);
1790                 obj.type = isl_obj_union_set;
1791         } else if (obj.type == isl_obj_pw_qpolynomial) {
1792                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
1793                 obj.type = isl_obj_union_pw_qpolynomial;
1794         } else if (obj.type == isl_obj_pw_qpolynomial_fold) {
1795                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
1796                 obj.type = isl_obj_union_pw_qpolynomial_fold;
1797         } else
1798                 isl_assert(ctx, 0, goto error);
1799         return obj;
1800 error:
1801         obj.type->free(obj.v);
1802         obj.type = isl_obj_none;
1803         return obj;
1804 }
1805
1806 static struct isl_obj obj_add(struct isl_ctx *ctx,
1807         struct isl_obj obj1, struct isl_obj obj2)
1808 {
1809         if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set)
1810                 obj1 = to_union(ctx, obj1);
1811         if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set)
1812                 obj2 = to_union(ctx, obj2);
1813         if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map)
1814                 obj1 = to_union(ctx, obj1);
1815         if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map)
1816                 obj2 = to_union(ctx, obj2);
1817         if (obj1.type == isl_obj_pw_qpolynomial &&
1818             obj2.type == isl_obj_union_pw_qpolynomial)
1819                 obj1 = to_union(ctx, obj1);
1820         if (obj1.type == isl_obj_union_pw_qpolynomial &&
1821             obj2.type == isl_obj_pw_qpolynomial)
1822                 obj2 = to_union(ctx, obj2);
1823         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1824             obj2.type == isl_obj_union_pw_qpolynomial_fold)
1825                 obj1 = to_union(ctx, obj1);
1826         if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
1827             obj2.type == isl_obj_pw_qpolynomial_fold)
1828                 obj2 = to_union(ctx, obj2);
1829         isl_assert(ctx, obj1.type == obj2.type, goto error);
1830         if (obj1.type == isl_obj_map && !isl_map_has_equal_space(obj1.v, obj2.v)) {
1831                 obj1 = to_union(ctx, obj1);
1832                 obj2 = to_union(ctx, obj2);
1833         }
1834         if (obj1.type == isl_obj_set && !isl_set_has_equal_space(obj1.v, obj2.v)) {
1835                 obj1 = to_union(ctx, obj1);
1836                 obj2 = to_union(ctx, obj2);
1837         }
1838         if (obj1.type == isl_obj_pw_qpolynomial &&
1839             !isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)) {
1840                 obj1 = to_union(ctx, obj1);
1841                 obj2 = to_union(ctx, obj2);
1842         }
1843         if (obj1.type == isl_obj_pw_qpolynomial_fold &&
1844             !isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)) {
1845                 obj1 = to_union(ctx, obj1);
1846                 obj2 = to_union(ctx, obj2);
1847         }
1848         obj1.v = obj1.type->add(obj1.v, obj2.v);
1849         return obj1;
1850 error:
1851         obj1.type->free(obj1.v);
1852         obj2.type->free(obj2.v);
1853         obj1.type = isl_obj_none;
1854         obj1.v = NULL;
1855         return obj1;
1856 }
1857
1858 static struct isl_obj obj_read(struct isl_stream *s)
1859 {
1860         isl_map *map = NULL;
1861         struct isl_token *tok;
1862         struct vars *v = NULL;
1863         struct isl_obj obj = { isl_obj_set, NULL };
1864
1865         tok = next_token(s);
1866         if (!tok) {
1867                 isl_stream_error(s, NULL, "unexpected EOF");
1868                 goto error;
1869         }
1870         if (tok->type == ISL_TOKEN_VALUE) {
1871                 struct isl_token *tok2;
1872                 struct isl_map *map;
1873
1874                 tok2 = isl_stream_next_token(s);
1875                 if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
1876                     isl_int_is_neg(tok2->u.v)) {
1877                         if (tok2)
1878                                 isl_stream_push_token(s, tok2);
1879                         obj.type = isl_obj_int;
1880                         obj.v = isl_int_obj_alloc(s->ctx, tok->u.v);
1881                         isl_token_free(tok);
1882                         return obj;
1883                 }
1884                 isl_stream_push_token(s, tok2);
1885                 isl_stream_push_token(s, tok);
1886                 map = map_read_polylib(s);
1887                 if (!map)
1888                         goto error;
1889                 if (isl_map_may_be_set(map))
1890                         obj.v = isl_map_range(map);
1891                 else {
1892                         obj.type = isl_obj_map;
1893                         obj.v = map;
1894                 }
1895                 return obj;
1896         }
1897         v = vars_new(s->ctx);
1898         if (!v) {
1899                 isl_stream_push_token(s, tok);
1900                 goto error;
1901         }
1902         map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
1903         if (tok->type == '[') {
1904                 isl_stream_push_token(s, tok);
1905                 map = read_tuple(s, map, isl_dim_param, v);
1906                 if (!map)
1907                         goto error;
1908                 tok = isl_stream_next_token(s);
1909                 if (!tok || tok->type != ISL_TOKEN_TO) {
1910                         isl_stream_error(s, tok, "expecting '->'");
1911                         if (tok)
1912                                 isl_stream_push_token(s, tok);
1913                         goto error;
1914                 }
1915                 isl_token_free(tok);
1916                 tok = isl_stream_next_token(s);
1917         }
1918         if (!tok || tok->type != '{') {
1919                 isl_stream_error(s, tok, "expecting '{'");
1920                 if (tok)
1921                         isl_stream_push_token(s, tok);
1922                 goto error;
1923         }
1924         isl_token_free(tok);
1925
1926         tok = isl_stream_next_token(s);
1927         if (!tok)
1928                 ;
1929         else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) {
1930                 isl_token_free(tok);
1931                 if (isl_stream_eat(s, '='))
1932                         goto error;
1933                 map = read_tuple(s, map, isl_dim_param, v);
1934                 if (!map)
1935                         goto error;
1936         } else if (tok->type == '}') {
1937                 obj.type = isl_obj_union_set;
1938                 obj.v = isl_union_set_empty(isl_map_get_space(map));
1939                 isl_token_free(tok);
1940                 goto done;
1941         } else
1942                 isl_stream_push_token(s, tok);
1943
1944         for (;;) {
1945                 struct isl_obj o;
1946                 tok = NULL;
1947                 o = obj_read_body(s, isl_map_copy(map), v);
1948                 if (o.type == isl_obj_none || !o.v)
1949                         goto error;
1950                 if (!obj.v)
1951                         obj = o;
1952                 else {
1953                         obj = obj_add(s->ctx, obj, o);
1954                         if (obj.type == isl_obj_none || !obj.v)
1955                                 goto error;
1956                 }
1957                 tok = isl_stream_next_token(s);
1958                 if (!tok || tok->type != ';')
1959                         break;
1960                 isl_token_free(tok);
1961                 if (isl_stream_next_token_is(s, '}')) {
1962                         tok = isl_stream_next_token(s);
1963                         break;
1964                 }
1965         }
1966
1967         if (tok && tok->type == '}') {
1968                 isl_token_free(tok);
1969         } else {
1970                 isl_stream_error(s, tok, "unexpected isl_token");
1971                 if (tok)
1972                         isl_token_free(tok);
1973                 goto error;
1974         }
1975 done:
1976         vars_free(v);
1977         isl_map_free(map);
1978
1979         return obj;
1980 error:
1981         isl_map_free(map);
1982         obj.type->free(obj.v);
1983         if (v)
1984                 vars_free(v);
1985         obj.v = NULL;
1986         return obj;
1987 }
1988
1989 struct isl_obj isl_stream_read_obj(struct isl_stream *s)
1990 {
1991         return obj_read(s);
1992 }
1993
1994 __isl_give isl_map *isl_stream_read_map(struct isl_stream *s)
1995 {
1996         struct isl_obj obj;
1997
1998         obj = obj_read(s);
1999         if (obj.v)
2000                 isl_assert(s->ctx, obj.type == isl_obj_map ||
2001                                    obj.type == isl_obj_set, goto error);
2002
2003         return obj.v;
2004 error:
2005         obj.type->free(obj.v);
2006         return NULL;
2007 }
2008
2009 __isl_give isl_set *isl_stream_read_set(struct isl_stream *s)
2010 {
2011         struct isl_obj obj;
2012
2013         obj = obj_read(s);
2014         if (obj.v) {
2015                 if (obj.type == isl_obj_map && isl_map_may_be_set(obj.v)) {
2016                         obj.v = isl_map_range(obj.v);
2017                         obj.type = isl_obj_set;
2018                 }
2019                 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2020         }
2021
2022         return obj.v;
2023 error:
2024         obj.type->free(obj.v);
2025         return NULL;
2026 }
2027
2028 __isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s)
2029 {
2030         struct isl_obj obj;
2031
2032         obj = obj_read(s);
2033         if (obj.type == isl_obj_map) {
2034                 obj.type = isl_obj_union_map;
2035                 obj.v = isl_union_map_from_map(obj.v);
2036         }
2037         if (obj.type == isl_obj_set) {
2038                 obj.type = isl_obj_union_set;
2039                 obj.v = isl_union_set_from_set(obj.v);
2040         }
2041         if (obj.v)
2042                 isl_assert(s->ctx, obj.type == isl_obj_union_map ||
2043                                    obj.type == isl_obj_union_set, goto error);
2044
2045         return obj.v;
2046 error:
2047         obj.type->free(obj.v);
2048         return NULL;
2049 }
2050
2051 __isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s)
2052 {
2053         struct isl_obj obj;
2054
2055         obj = obj_read(s);
2056         if (obj.type == isl_obj_set) {
2057                 obj.type = isl_obj_union_set;
2058                 obj.v = isl_union_set_from_set(obj.v);
2059         }
2060         if (obj.v)
2061                 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
2062
2063         return obj.v;
2064 error:
2065         obj.type->free(obj.v);
2066         return NULL;
2067 }
2068
2069 static __isl_give isl_basic_map *basic_map_read(struct isl_stream *s)
2070 {
2071         struct isl_obj obj;
2072         struct isl_map *map;
2073         struct isl_basic_map *bmap;
2074
2075         obj = obj_read(s);
2076         map = obj.v;
2077         if (!map)
2078                 return NULL;
2079
2080         isl_assert(map->ctx, map->n <= 1, goto error);
2081
2082         if (map->n == 0)
2083                 bmap = isl_basic_map_empty_like_map(map);
2084         else
2085                 bmap = isl_basic_map_copy(map->p[0]);
2086
2087         isl_map_free(map);
2088
2089         return bmap;
2090 error:
2091         isl_map_free(map);
2092         return NULL;
2093 }
2094
2095 static __isl_give isl_basic_set *basic_set_read(struct isl_stream *s)
2096 {
2097         isl_basic_map *bmap;
2098         bmap = basic_map_read(s);
2099         if (!bmap)
2100                 return NULL;
2101         if (!isl_basic_map_may_be_set(bmap))
2102                 isl_die(s->ctx, isl_error_invalid,
2103                         "input is not a set", goto error);
2104         return isl_basic_map_range(bmap);
2105 error:
2106         isl_basic_map_free(bmap);
2107         return NULL;
2108 }
2109
2110 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2111         FILE *input)
2112 {
2113         struct isl_basic_map *bmap;
2114         struct isl_stream *s = isl_stream_new_file(ctx, input);
2115         if (!s)
2116                 return NULL;
2117         bmap = basic_map_read(s);
2118         isl_stream_free(s);
2119         return bmap;
2120 }
2121
2122 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2123         FILE *input)
2124 {
2125         isl_basic_set *bset;
2126         struct isl_stream *s = isl_stream_new_file(ctx, input);
2127         if (!s)
2128                 return NULL;
2129         bset = basic_set_read(s);
2130         isl_stream_free(s);
2131         return bset;
2132 }
2133
2134 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2135         const char *str)
2136 {
2137         struct isl_basic_map *bmap;
2138         struct isl_stream *s = isl_stream_new_str(ctx, str);
2139         if (!s)
2140                 return NULL;
2141         bmap = basic_map_read(s);
2142         isl_stream_free(s);
2143         return bmap;
2144 }
2145
2146 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2147         const char *str)
2148 {
2149         isl_basic_set *bset;
2150         struct isl_stream *s = isl_stream_new_str(ctx, str);
2151         if (!s)
2152                 return NULL;
2153         bset = basic_set_read(s);
2154         isl_stream_free(s);
2155         return bset;
2156 }
2157
2158 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2159         FILE *input)
2160 {
2161         struct isl_map *map;
2162         struct isl_stream *s = isl_stream_new_file(ctx, input);
2163         if (!s)
2164                 return NULL;
2165         map = isl_stream_read_map(s);
2166         isl_stream_free(s);
2167         return map;
2168 }
2169
2170 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2171         const char *str)
2172 {
2173         struct isl_map *map;
2174         struct isl_stream *s = isl_stream_new_str(ctx, str);
2175         if (!s)
2176                 return NULL;
2177         map = isl_stream_read_map(s);
2178         isl_stream_free(s);
2179         return map;
2180 }
2181
2182 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2183         FILE *input)
2184 {
2185         isl_set *set;
2186         struct isl_stream *s = isl_stream_new_file(ctx, input);
2187         if (!s)
2188                 return NULL;
2189         set = isl_stream_read_set(s);
2190         isl_stream_free(s);
2191         return set;
2192 }
2193
2194 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2195         const char *str)
2196 {
2197         isl_set *set;
2198         struct isl_stream *s = isl_stream_new_str(ctx, str);
2199         if (!s)
2200                 return NULL;
2201         set = isl_stream_read_set(s);
2202         isl_stream_free(s);
2203         return set;
2204 }
2205
2206 __isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2207         FILE *input)
2208 {
2209         isl_union_map *umap;
2210         struct isl_stream *s = isl_stream_new_file(ctx, input);
2211         if (!s)
2212                 return NULL;
2213         umap = isl_stream_read_union_map(s);
2214         isl_stream_free(s);
2215         return umap;
2216 }
2217
2218 __isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2219                 const char *str)
2220 {
2221         isl_union_map *umap;
2222         struct isl_stream *s = isl_stream_new_str(ctx, str);
2223         if (!s)
2224                 return NULL;
2225         umap = isl_stream_read_union_map(s);
2226         isl_stream_free(s);
2227         return umap;
2228 }
2229
2230 __isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2231         FILE *input)
2232 {
2233         isl_union_set *uset;
2234         struct isl_stream *s = isl_stream_new_file(ctx, input);
2235         if (!s)
2236                 return NULL;
2237         uset = isl_stream_read_union_set(s);
2238         isl_stream_free(s);
2239         return uset;
2240 }
2241
2242 __isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
2243                 const char *str)
2244 {
2245         isl_union_set *uset;
2246         struct isl_stream *s = isl_stream_new_str(ctx, str);
2247         if (!s)
2248                 return NULL;
2249         uset = isl_stream_read_union_set(s);
2250         isl_stream_free(s);
2251         return uset;
2252 }
2253
2254 static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s)
2255 {
2256         struct isl_vec *vec = NULL;
2257         struct isl_token *tok;
2258         unsigned size;
2259         int j;
2260
2261         tok = isl_stream_next_token(s);
2262         if (!tok || tok->type != ISL_TOKEN_VALUE) {
2263                 isl_stream_error(s, tok, "expecting vector length");
2264                 goto error;
2265         }
2266
2267         size = isl_int_get_si(tok->u.v);
2268         isl_token_free(tok);
2269
2270         vec = isl_vec_alloc(s->ctx, size);
2271
2272         for (j = 0; j < size; ++j) {
2273                 tok = isl_stream_next_token(s);
2274                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
2275                         isl_stream_error(s, tok, "expecting constant value");
2276                         goto error;
2277                 }
2278                 isl_int_set(vec->el[j], tok->u.v);
2279                 isl_token_free(tok);
2280         }
2281
2282         return vec;
2283 error:
2284         isl_token_free(tok);
2285         isl_vec_free(vec);
2286         return NULL;
2287 }
2288
2289 static __isl_give isl_vec *vec_read(struct isl_stream *s)
2290 {
2291         return isl_vec_read_polylib(s);
2292 }
2293
2294 __isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
2295 {
2296         isl_vec *v;
2297         struct isl_stream *s = isl_stream_new_file(ctx, input);
2298         if (!s)
2299                 return NULL;
2300         v = vec_read(s);
2301         isl_stream_free(s);
2302         return v;
2303 }
2304
2305 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
2306         struct isl_stream *s)
2307 {
2308         struct isl_obj obj;
2309
2310         obj = obj_read(s);
2311         if (obj.v)
2312                 isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
2313                            goto error);
2314
2315         return obj.v;
2316 error:
2317         obj.type->free(obj.v);
2318         return NULL;
2319 }
2320
2321 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
2322                 const char *str)
2323 {
2324         isl_pw_qpolynomial *pwqp;
2325         struct isl_stream *s = isl_stream_new_str(ctx, str);
2326         if (!s)
2327                 return NULL;
2328         pwqp = isl_stream_read_pw_qpolynomial(s);
2329         isl_stream_free(s);
2330         return pwqp;
2331 }
2332
2333 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
2334                 FILE *input)
2335 {
2336         isl_pw_qpolynomial *pwqp;
2337         struct isl_stream *s = isl_stream_new_file(ctx, input);
2338         if (!s)
2339                 return NULL;
2340         pwqp = isl_stream_read_pw_qpolynomial(s);
2341         isl_stream_free(s);
2342         return pwqp;
2343 }
2344
2345 /* Read an affine expression from "s" with domain (space) "dom".
2346  * We call accept_affine to parse a possibly piecewise affine expression
2347  * and then check that the result is a single affine expression on
2348  * a universe domain.
2349  */
2350 static __isl_give isl_aff *read_aff_with_dom(struct isl_stream *s,
2351         __isl_take isl_set *dom, struct vars *v)
2352 {
2353         isl_aff *aff = NULL;
2354         isl_pw_aff *pwaff = NULL;
2355
2356         if (!isl_set_plain_is_universe(dom))
2357                 isl_die(s->ctx, isl_error_invalid,
2358                         "expecting universe domain", goto error);
2359
2360         if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2361                 goto error;
2362
2363         if (isl_stream_eat(s, '['))
2364                 goto error;
2365
2366         pwaff = accept_affine(s, isl_set_get_space(dom), v);
2367
2368         if (isl_stream_eat(s, ']'))
2369                 goto error;
2370         if (isl_stream_eat(s, '}'))
2371                 goto error;
2372
2373         if (!pwaff)
2374                 goto error;
2375
2376         if (pwaff->n != 1)
2377                 isl_die(s->ctx, isl_error_invalid,
2378                         "expecting single affine expression", goto error);
2379         if (!isl_set_plain_is_universe(pwaff->p[0].set))
2380                 isl_die(s->ctx, isl_error_invalid,
2381                         "expecting universe domain", goto error);
2382
2383         aff = isl_aff_copy(pwaff->p[0].aff);
2384
2385         vars_free(v);
2386         isl_pw_aff_free(pwaff);
2387         isl_set_free(dom);
2388         return aff;
2389 error:
2390         vars_free(v);
2391         isl_pw_aff_free(pwaff);
2392         isl_set_free(dom);
2393         return NULL;
2394 }
2395
2396 /* Is the next token an identifer not in "v"?
2397  */
2398 static int next_is_fresh_ident(struct isl_stream *s, struct vars *v)
2399 {
2400         int n = v->n;
2401         int fresh;
2402         struct isl_token *tok;
2403
2404         tok = isl_stream_next_token(s);
2405         if (!tok)
2406                 return 0;
2407         fresh = tok->type == ISL_TOKEN_IDENT && vars_pos(v, tok->u.s, -1) >= n;
2408         isl_stream_push_token(s, tok);
2409
2410         vars_drop(v, v->n - n);
2411
2412         return fresh;
2413 }
2414
2415 /* First read the domain of the affine expression, which may be
2416  * a parameter space or a set.
2417  * The tricky part is that we don't know if the domain is a set or not,
2418  * so when we are trying to read the domain, we may actually be reading
2419  * the affine expression itself (defined on a parameter domains)
2420  * If the tuple we are reading is named, we assume it's the domain.
2421  * Also, if inside the tuple, the first thing we find is a nested tuple
2422  * or a new identifier, we again assume it's the domain.
2423  * Otherwise, we assume we are reading an affine expression.
2424  */
2425 static __isl_give isl_set *read_aff_domain(struct isl_stream *s,
2426         __isl_take isl_set *dom, struct vars *v)
2427 {
2428         struct isl_token *tok;
2429
2430         tok = isl_stream_next_token(s);
2431         if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) {
2432                 isl_stream_push_token(s, tok);
2433                 return read_tuple(s, dom, isl_dim_set, v);
2434         }
2435         if (!tok || tok->type != '[') {
2436                 isl_stream_error(s, tok, "expecting '['");
2437                 goto error;
2438         }
2439         if (next_is_tuple(s) || next_is_fresh_ident(s, v)) {
2440                 isl_stream_push_token(s, tok);
2441                 dom = read_tuple(s, dom, isl_dim_set, v);
2442         } else
2443                 isl_stream_push_token(s, tok);
2444
2445         return dom;
2446 error:
2447         if (tok)
2448                 isl_stream_push_token(s, tok);
2449         vars_free(v);
2450         isl_set_free(dom);
2451         return NULL;
2452 }
2453
2454 /* Read an affine expression from "s".
2455  * We first read the domain of the affine expression, which may be
2456  * a parameter space or a set, and then call read_aff_with_dom.
2457  */
2458 __isl_give isl_aff *isl_stream_read_aff(struct isl_stream *s)
2459 {
2460         struct vars *v;
2461         isl_set *dom = NULL;
2462
2463         v = vars_new(s->ctx);
2464         if (!v)
2465                 return NULL;
2466
2467         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2468         if (next_is_tuple(s)) {
2469                 dom = read_tuple(s, dom, isl_dim_param, v);
2470                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2471                         goto error;
2472         }
2473         if (isl_stream_eat(s, '{'))
2474                 goto error;
2475
2476         dom = read_aff_domain(s, dom, v);
2477         return read_aff_with_dom(s, dom, v);
2478 error:
2479         vars_free(v);
2480         isl_set_free(dom);
2481         return NULL;
2482 }
2483
2484 /* Read a piecewise affine expression from "s" with domain (space) "dom".
2485  */
2486 static __isl_give isl_pw_aff *read_pw_aff_with_dom(struct isl_stream *s,
2487         __isl_take isl_set *dom, struct vars *v)
2488 {
2489         isl_pw_aff *pwaff = NULL;
2490
2491         if (!isl_set_is_params(dom) && isl_stream_eat(s, ISL_TOKEN_TO))
2492                 goto error;
2493
2494         if (isl_stream_eat(s, '['))
2495                 goto error;
2496
2497         pwaff = accept_affine(s, isl_set_get_space(dom), v);
2498
2499         if (isl_stream_eat(s, ']'))
2500                 goto error;
2501
2502         dom = read_optional_disjuncts(s, dom, v);
2503         pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2504
2505         return pwaff;
2506 error:
2507         isl_set_free(dom);
2508         isl_pw_aff_free(pwaff);
2509         return NULL;
2510 }
2511
2512 __isl_give isl_pw_aff *isl_stream_read_pw_aff(struct isl_stream *s)
2513 {
2514         struct vars *v;
2515         isl_set *dom = NULL;
2516         isl_set *aff_dom;
2517         isl_pw_aff *pa = NULL;
2518         int n;
2519
2520         v = vars_new(s->ctx);
2521         if (!v)
2522                 return NULL;
2523
2524         dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
2525         if (next_is_tuple(s)) {
2526                 dom = read_tuple(s, dom, isl_dim_param, v);
2527                 if (isl_stream_eat(s, ISL_TOKEN_TO))
2528                         goto error;
2529         }
2530         if (isl_stream_eat(s, '{'))
2531                 goto error;
2532
2533         n = v->n;
2534         aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2535         pa = read_pw_aff_with_dom(s, aff_dom, v);
2536         vars_drop(v, v->n - n);
2537
2538         while (isl_stream_eat_if_available(s, ';')) {
2539                 isl_pw_aff *pa_i;
2540
2541                 n = v->n;
2542                 aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
2543                 pa_i = read_pw_aff_with_dom(s, aff_dom, v);
2544                 vars_drop(v, v->n - n);
2545
2546                 pa = isl_pw_aff_union_add(pa, pa_i);
2547         }
2548
2549         if (isl_stream_eat(s, '}'))
2550                 goto error;
2551
2552         vars_free(v);
2553         isl_set_free(dom);
2554         return pa;
2555 error:
2556         vars_free(v);
2557         isl_set_free(dom);
2558         isl_pw_aff_free(pa);
2559         return NULL;
2560 }
2561
2562 __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
2563 {
2564         isl_aff *aff;
2565         struct isl_stream *s = isl_stream_new_str(ctx, str);
2566         if (!s)
2567                 return NULL;
2568         aff = isl_stream_read_aff(s);
2569         isl_stream_free(s);
2570         return aff;
2571 }
2572
2573 __isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
2574 {
2575         isl_pw_aff *pa;
2576         struct isl_stream *s = isl_stream_new_str(ctx, str);
2577         if (!s)
2578                 return NULL;
2579         pa = isl_stream_read_pw_aff(s);
2580         isl_stream_free(s);
2581         return pa;
2582 }
2583
2584 /* Read an isl_pw_multi_aff from "s".
2585  * We currently read a generic object and if it turns out to be a set or
2586  * a map, we convert that to an isl_pw_multi_aff.
2587  * It would be more efficient if we were to construct the isl_pw_multi_aff
2588  * directly.
2589  */
2590 __isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(struct isl_stream *s)
2591 {
2592         struct isl_obj obj;
2593
2594         obj = obj_read(s);
2595         if (!obj.v)
2596                 return NULL;
2597
2598         if (obj.type == isl_obj_map)
2599                 return isl_pw_multi_aff_from_map(obj.v);
2600         if (obj.type == isl_obj_set)
2601                 return isl_pw_multi_aff_from_set(obj.v);
2602
2603         obj.type->free(obj.v);
2604         isl_die(s->ctx, isl_error_invalid, "unexpected object type",
2605                 return NULL);
2606 }
2607
2608 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
2609         const char *str)
2610 {
2611         isl_pw_multi_aff *pma;
2612         struct isl_stream *s = isl_stream_new_str(ctx, str);
2613         if (!s)
2614                 return NULL;
2615         pma = isl_stream_read_pw_multi_aff(s);
2616         isl_stream_free(s);
2617         return pma;
2618 }
2619
2620 /* Read a multi-affine expression from "s".
2621  * We call isl_stream_read_pw_multi_aff to parse a possibly piecewise
2622  * multi-affine expression and then check that the result is
2623  * a single multi-affine expression on a universe domain.
2624  */
2625 __isl_give isl_multi_aff *isl_stream_read_multi_aff(struct isl_stream *s)
2626 {
2627         isl_pw_multi_aff *pma;
2628         isl_multi_aff *maff;
2629
2630         pma = isl_stream_read_pw_multi_aff(s);
2631         if (!pma)
2632                 return NULL;
2633         if (pma->n != 1)
2634                 isl_die(s->ctx, isl_error_invalid,
2635                         "expecting single list of affine expressions",
2636                         return isl_pw_multi_aff_free(pma));
2637         if (!isl_set_plain_is_universe(pma->p[0].set))
2638                 isl_die(s->ctx, isl_error_invalid, "expecting universe domain",
2639                         return isl_pw_multi_aff_free(pma));
2640         maff = isl_multi_aff_copy(pma->p[0].maff);
2641         isl_pw_multi_aff_free(pma);
2642         return maff;
2643 }
2644
2645 __isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
2646         const char *str)
2647 {
2648         isl_multi_aff *maff;
2649         struct isl_stream *s = isl_stream_new_str(ctx, str);
2650         if (!s)
2651                 return NULL;
2652         maff = isl_stream_read_multi_aff(s);
2653         isl_stream_free(s);
2654         return maff;
2655 }
2656
2657 __isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
2658         struct isl_stream *s)
2659 {
2660         struct isl_obj obj;
2661
2662         obj = obj_read(s);
2663         if (obj.type == isl_obj_pw_qpolynomial) {
2664                 obj.type = isl_obj_union_pw_qpolynomial;
2665                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2666         }
2667         if (obj.v)
2668                 isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
2669                            goto error);
2670
2671         return obj.v;
2672 error:
2673         obj.type->free(obj.v);
2674         return NULL;
2675 }
2676
2677 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
2678         isl_ctx *ctx, const char *str)
2679 {
2680         isl_union_pw_qpolynomial *upwqp;
2681         struct isl_stream *s = isl_stream_new_str(ctx, str);
2682         if (!s)
2683                 return NULL;
2684         upwqp = isl_stream_read_union_pw_qpolynomial(s);
2685         isl_stream_free(s);
2686         return upwqp;
2687 }