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