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