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