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_stream.h"
  20 #include "isl_map_private.h"
  21
  22 struct variable {
  23         char                    *name;
  24         int                      pos;
  25         struct variable         *next;
  26 };
  27
  28 struct vars {
  29         struct isl_ctx  *ctx;
  30         int              n;
  31         struct variable *v;
  32 };
  33
  34 static struct vars *vars_new(struct isl_ctx *ctx)
  35 {
  36         struct vars *v;
  37         v = isl_alloc_type(ctx, struct vars);
  38         if (!v)
  39                 return NULL;
  40         v->ctx = ctx;
  41         v->n = 0;
  42         v->v = NULL;
  43         return v;
  44 }
  45
  46 static void variable_free(struct variable *var)
  47 {
  48         while (var) {
  49                 struct variable *next = var->next;
  50                 free(var->name);
  51                 free(var);
  52                 var = next;
  53         }
  54 }
  55
  56 static void vars_free(struct vars *v)
  57 {
  58         if (!v)
  59                 return;
  60         variable_free(v->v);
  61         free(v);
  62 }
  63
  64 static void vars_drop(struct vars *v, int n)
  65 {
  66         struct variable *var;
  67
  68         if (!v)
  69                 return;
  70
  71         v->n -= n;
  72
  73         var = v->v;
  74         while (--n >= 0) {
  75                 struct variable *next = var->next;
  76                 free(var->name);
  77                 free(var);
  78                 var = next;
  79         }
  80         v->v = var;
  81 }
  82
  83 static struct variable *variable_new(struct vars *v, const char *name, int len,
  84                                 int pos)
  85 {
  86         struct variable *var;
  87         var = isl_alloc_type(v->ctx, struct variable);
  88         if (!var)
  89                 goto error;
  90         var->name = strdup(name);
  91         var->name[len] = '\0';
  92         var->pos = pos;
  93         var->next = v->v;
  94         return var;
  95 error:
  96         variable_free(v->v);
  97         return NULL;
  98 }
  99
 100 static int vars_pos(struct vars *v, const char *s, int len)
 101 {
 102         int pos;
 103         struct variable *q;
 104
 105         if (len == -1)
 106                 len = strlen(s);
 107         for (q = v->v; q; q = q->next) {
 108                 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
 109                         break;
 110         }
 111         if (q)
 112                 pos = q->pos;
 113         else {
 114                 pos = v->n;
 115                 v->v = variable_new(v, s, len, v->n);
 116                 if (!v->v)
 117                         return -1;
 118                 v->n++;
 119         }
 120         return pos;
 121 }
 122
 123 static __isl_give isl_basic_map *set_name(__isl_take isl_basic_map *bmap,
 124         enum isl_dim_type type, unsigned pos, char *name)
 125 {
 126         char *prime;
 127
 128         if (!bmap)
 129                 return NULL;
 130         if (!name)
 131                 return bmap;
 132
 133         prime = strchr(name, '\'');
 134         if (prime)
 135                 *prime = '\0';
 136         bmap->dim = isl_dim_set_name(bmap->dim, type, pos, name);
 137         if (prime)
 138                 *prime = '\'';
 139
 140         if (!bmap->dim)
 141                 goto error;
 142
 143         return bmap;
 144 error:
 145         isl_basic_map_free(bmap);
 146         return NULL;
 147 }
 148
 149 static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v)
 150 {
 151         struct isl_token *tok = NULL;
 152         struct isl_vec *aff;
 153         int sign = 1;
 154
 155         aff = isl_vec_alloc(v->ctx, 1 + v->n);
 156         isl_seq_clr(aff->el, aff->size);
 157         if (!aff)
 158                 return NULL;
 159
 160         for (;;) {
 161                 tok = isl_stream_next_token(s);
 162                 if (!tok) {
 163                         isl_stream_error(s, NULL, "unexpected EOF");
 164                         goto error;
 165                 }
 166                 if (tok->type == ISL_TOKEN_IDENT) {
 167                         int n = v->n;
 168                         int pos = vars_pos(v, tok->u.s, -1);
 169                         if (pos < 0)
 170                                 goto error;
 171                         if (pos >= n) {
 172                                 isl_stream_error(s, tok, "unknown identifier");
 173                                 isl_token_free(tok);
 174                                 goto error;
 175                         }
 176                         if (sign > 0)
 177                                 isl_int_add_ui(aff->el[1 + pos],
 178                                                aff->el[1 + pos], 1);
 179                         else
 180                                 isl_int_sub_ui(aff->el[1 + pos],
 181                                                aff->el[1 + pos], 1);
 182                         sign = 1;
 183                 } else if (tok->type == ISL_TOKEN_VALUE) {
 184                         struct isl_token *tok2;
 185                         int n = v->n;
 186                         int pos = -1;
 187                         tok2 = isl_stream_next_token(s);
 188                         if (tok2 && tok2->type == ISL_TOKEN_IDENT) {
 189                                 pos = vars_pos(v, tok2->u.s, -1);
 190                                 if (pos < 0)
 191                                         goto error;
 192                                 if (pos >= n) {
 193                                         isl_stream_error(s, tok2,
 194                                                 "unknown identifier");
 195                                         isl_token_free(tok);
 196                                         isl_token_free(tok2);
 197                                         goto error;
 198                                 }
 199                                 isl_token_free(tok2);
 200                         } else if (tok2)
 201                                 isl_stream_push_token(s, tok2);
 202                         if (sign < 0)
 203                                 isl_int_neg(tok->u.v, tok->u.v);
 204                         isl_int_add(aff->el[1 + pos],
 205                                         aff->el[1 + pos], tok->u.v);
 206                         sign = 1;
 207                 } else if (tok->type == '-') {
 208                         sign = -sign;
 209                 } else if (tok->type == '+') {
 210                         /* nothing */
 211                 } else {
 212                         isl_stream_push_token(s, tok);
 213                         break;
 214                 }
 215                 isl_token_free(tok);
 216         }
 217
 218         return aff;
 219 error:
 220         isl_vec_free(aff);
 221         return NULL;
 222 }
 223
 224 static __isl_give isl_basic_map *read_var_list(struct isl_stream *s,
 225         __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
 226 {
 227         int i = 0;
 228         struct isl_token *tok;
 229
 230         while ((tok = isl_stream_next_token(s)) != NULL) {
 231                 int new_name = 0;
 232
 233                 if (tok->type == ISL_TOKEN_IDENT) {
 234                         int n = v->n;
 235                         int p = vars_pos(v, tok->u.s, -1);
 236                         if (p < 0)
 237                                 goto error;
 238                         new_name = p >= n;
 239                 }
 240
 241                 if (new_name) {
 242                         bmap = isl_basic_map_add(bmap, type, 1);
 243                         bmap = set_name(bmap, type, i, v->v->name);
 244                         isl_token_free(tok);
 245                 } else if (tok->type == ISL_TOKEN_IDENT ||
 246                            tok->type == ISL_TOKEN_VALUE) {
 247                         struct isl_vec *vec;
 248                         int k;
 249                         if (type == isl_dim_param) {
 250                                 isl_stream_error(s, tok,
 251                                                 "expecting unique identifier");
 252                                 goto error;
 253                         }
 254                         isl_stream_push_token(s, tok);
 255                         tok = NULL;
 256                         vec = accept_affine(s, v);
 257                         if (!vec)
 258                                 goto error;
 259                         v->v = variable_new(v, "", 0, v->n);
 260                         if (!v->v)
 261                                 goto error;
 262                         v->n++;
 263                         bmap = isl_basic_map_add(bmap, type, 1);
 264                         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
 265                         k = isl_basic_map_alloc_equality(bmap);
 266                         if (k >= 0) {
 267                                 isl_seq_cpy(bmap->eq[k], vec->el, vec->size);
 268                                 isl_int_set_si(bmap->eq[k][vec->size], -1);
 269                         }
 270                         isl_vec_free(vec);
 271                         if (k < 0)
 272                                 goto error;
 273                 } else
 274                         break;
 275
 276                 tok = isl_stream_next_token(s);
 277                 if (!tok || tok->type != ',')
 278                         break;
 279
 280                 isl_token_free(tok);
 281                 i++;
 282         }
 283         if (tok)
 284                 isl_stream_push_token(s, tok);
 285
 286         return bmap;
 287 error:
 288         isl_token_free(tok);
 289         isl_basic_map_free(bmap);
 290         return NULL;
 291 }
 292
 293 static __isl_give isl_mat *accept_affine_list(struct isl_stream *s,
 294         struct vars *v)
 295 {
 296         struct isl_vec *vec;
 297         struct isl_mat *mat;
 298         struct isl_token *tok = NULL;
 299
 300         vec = accept_affine(s, v);
 301         mat = isl_mat_from_row_vec(vec);
 302         if (!mat)
 303                 return NULL;
 304
 305         for (;;) {
 306                 tok = isl_stream_next_token(s);
 307                 if (!tok) {
 308                         isl_stream_error(s, NULL, "unexpected EOF");
 309                         goto error;
 310                 }
 311                 if (tok->type != ',') {
 312                         isl_stream_push_token(s, tok);
 313                         break;
 314                 }
 315                 isl_token_free(tok);
 316
 317                 vec = accept_affine(s, v);
 318                 mat = isl_mat_vec_concat(mat, vec);
 319                 if (!mat)
 320                         return NULL;
 321         }
 322
 323         return mat;
 324 error:
 325         isl_mat_free(mat);
 326         return NULL;
 327 }
 328
 329 static struct isl_basic_map *add_div_definition(struct isl_stream *s,
 330         struct vars *v, struct isl_basic_map *bmap, int k)
 331 {
 332         struct isl_token *tok;
 333         int seen_paren = 0;
 334         struct isl_vec *aff;
 335
 336         if (isl_stream_eat(s, '['))
 337                 goto error;
 338
 339         tok = isl_stream_next_token(s);
 340         if (!tok)
 341                 goto error;
 342         if (tok->type == '(') {
 343                 seen_paren = 1;
 344                 isl_token_free(tok);
 345         } else
 346                 isl_stream_push_token(s, tok);
 347
 348         aff = accept_affine(s, v);
 349         if (!aff)
 350                 goto error;
 351
 352         isl_seq_cpy(bmap->div[k] + 1, aff->el, aff->size);
 353
 354         isl_vec_free(aff);
 355
 356         if (seen_paren && isl_stream_eat(s, ')'))
 357                 goto error;
 358         if (isl_stream_eat(s, '/'))
 359                 goto error;
 360
 361         tok = isl_stream_next_token(s);
 362         if (!tok)
 363                 goto error;
 364         if (tok->type != ISL_TOKEN_VALUE) {
 365                 isl_stream_error(s, tok, "expected denominator");
 366                 isl_stream_push_token(s, tok);
 367                 goto error;
 368         }
 369         isl_int_set(bmap->div[k][0], tok->u.v);
 370         isl_token_free(tok);
 371
 372         if (isl_stream_eat(s, ']'))
 373                 goto error;
 374
 375         if (isl_basic_map_add_div_constraints(bmap, k) < 0)
 376                 goto error;
 377
 378         return bmap;
 379 error:
 380         isl_basic_map_free(bmap);
 381         return NULL;
 382 }
 383
 384 static struct isl_basic_map *read_defined_var_list(struct isl_stream *s,
 385         struct vars *v, struct isl_basic_map *bmap)
 386 {
 387         struct isl_token *tok;
 388
 389         while ((tok = isl_stream_next_token(s)) != NULL) {
 390                 int k;
 391                 int p;
 392                 int n = v->n;
 393                 unsigned total = isl_basic_map_total_dim(bmap);
 394
 395                 if (tok->type != ISL_TOKEN_IDENT)
 396                         break;
 397
 398                 p = vars_pos(v, tok->u.s, -1);
 399                 if (p < 0)
 400                         goto error;
 401                 if (p < n) {
 402                         isl_stream_error(s, tok, "expecting unique identifier");
 403                         goto error;
 404                 }
 405                 isl_token_free(tok);
 406
 407                 bmap = isl_basic_map_cow(bmap);
 408                 bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
 409                                                 1, 0, 2);
 410
 411                 if ((k = isl_basic_map_alloc_div(bmap)) < 0)
 412                         goto error;
 413                 isl_seq_clr(bmap->div[k], 1 + 1 + total);
 414
 415                 tok = isl_stream_next_token(s);
 416                 if (tok && tok->type == '=') {
 417                         isl_token_free(tok);
 418                         bmap = add_div_definition(s, v, bmap, k);
 419                         tok = isl_stream_next_token(s);
 420                 }
 421
 422                 if (!tok || tok->type != ',')
 423                         break;
 424
 425                 isl_token_free(tok);
 426         }
 427         if (tok)
 428                 isl_stream_push_token(s, tok);
 429
 430         return bmap;
 431 error:
 432         isl_token_free(tok);
 433         isl_basic_map_free(bmap);
 434         return NULL;
 435 }
 436
 437 static __isl_give isl_basic_map *read_tuple(struct isl_stream *s,
 438         __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v)
 439 {
 440         struct isl_token *tok;
 441
 442         tok = isl_stream_next_token(s);
 443         if (!tok || tok->type != '[') {
 444                 isl_stream_error(s, tok, "expecting '['");
 445                 goto error;
 446         }
 447         isl_token_free(tok);
 448         bmap = read_var_list(s, bmap, type, v);
 449         tok = isl_stream_next_token(s);
 450         if (!tok || tok->type != ']') {
 451                 isl_stream_error(s, tok, "expecting ']'");
 452                 goto error;
 453         }
 454         isl_token_free(tok);
 455
 456         return bmap;
 457 error:
 458         if (tok)
 459                 isl_token_free(tok);
 460         isl_basic_map_free(bmap);
 461         return NULL;
 462 }
 463
 464 static struct isl_basic_map *add_constraints(struct isl_stream *s,
 465         struct vars *v, struct isl_basic_map *bmap);
 466
 467 static struct isl_basic_map *add_exists(struct isl_stream *s,
 468         struct vars *v, struct isl_basic_map *bmap)
 469 {
 470         struct isl_token *tok;
 471         int n = v->n;
 472         int extra;
 473         int seen_paren = 0;
 474         int i;
 475         unsigned total;
 476
 477         tok = isl_stream_next_token(s);
 478         if (!tok)
 479                 goto error;
 480         if (tok->type == '(') {
 481                 seen_paren = 1;
 482                 isl_token_free(tok);
 483         } else
 484                 isl_stream_push_token(s, tok);
 485
 486         bmap = read_defined_var_list(s, v, bmap);
 487         if (!bmap)
 488                 goto error;
 489
 490         if (isl_stream_eat(s, ':'))
 491                 goto error;
 492         bmap = add_constraints(s, v, bmap);
 493         if (seen_paren && isl_stream_eat(s, ')'))
 494                 goto error;
 495         return bmap;
 496 error:
 497         isl_basic_map_free(bmap);
 498         return NULL;
 499 }
 500
 501 static __isl_give isl_basic_map *construct_constraint(
 502         __isl_take isl_basic_map *bmap, enum isl_token_type type,
 503         isl_int *left, isl_int *right)
 504 {
 505         int k;
 506         unsigned len;
 507         struct isl_ctx *ctx;
 508
 509         if (!bmap)
 510                 return NULL;
 511         len = 1 + isl_basic_map_total_dim(bmap);
 512         ctx = bmap->ctx;
 513
 514         k = isl_basic_map_alloc_inequality(bmap);
 515         if (k < 0)
 516                 goto error;
 517         if (type == ISL_TOKEN_LE)
 518                 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
 519                                                ctx->one, right,
 520                                                len);
 521         else if (type == ISL_TOKEN_GE)
 522                 isl_seq_combine(bmap->ineq[k], ctx->one, left,
 523                                                ctx->negone, right,
 524                                                len);
 525         else if (type == ISL_TOKEN_LT) {
 526                 isl_seq_combine(bmap->ineq[k], ctx->negone, left,
 527                                                ctx->one, right,
 528                                                len);
 529                 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
 530         } else if (type == ISL_TOKEN_GT) {
 531                 isl_seq_combine(bmap->ineq[k], ctx->one, left,
 532                                                ctx->negone, right,
 533                                                len);
 534                 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
 535         } else {
 536                 isl_seq_combine(bmap->ineq[k], ctx->one, left,
 537                                                ctx->negone, right,
 538                                                len);
 539                 isl_basic_map_inequality_to_equality(bmap, k);
 540         }
 541
 542         return bmap;
 543 error:
 544         isl_basic_map_free(bmap);
 545         return NULL;
 546 }
 547
 548 static int is_comparator(struct isl_token *tok)
 549 {
 550         if (!tok)
 551                 return 0;
 552
 553         switch (tok->type) {
 554         case ISL_TOKEN_LT:
 555         case ISL_TOKEN_GT:
 556         case ISL_TOKEN_LE:
 557         case ISL_TOKEN_GE:
 558         case '=':
 559                 return 1;
 560         default:
 561                 return 0;
 562         }
 563 }
 564
 565 static struct isl_basic_map *add_constraint(struct isl_stream *s,
 566         struct vars *v, struct isl_basic_map *bmap)
 567 {
 568         int i, j;
 569         unsigned total = isl_basic_map_total_dim(bmap);
 570         struct isl_token *tok = NULL;
 571         struct isl_mat *aff1 = NULL, *aff2 = NULL;
 572
 573         tok = isl_stream_next_token(s);
 574         if (!tok)
 575                 goto error;
 576         if (tok->type == ISL_TOKEN_EXISTS) {
 577                 isl_token_free(tok);
 578                 return add_exists(s, v, bmap);
 579         }
 580         isl_stream_push_token(s, tok);
 581         tok = NULL;
 582
 583         bmap = isl_basic_map_cow(bmap);
 584
 585         aff1 = accept_affine_list(s, v);
 586         if (!aff1)
 587                 goto error;
 588         tok = isl_stream_next_token(s);
 589         if (!is_comparator(tok)) {
 590                 isl_stream_error(s, tok, "missing operator");
 591                 if (tok)
 592                         isl_stream_push_token(s, tok);
 593                 tok = NULL;
 594                 goto error;
 595         }
 596         isl_assert(aff1->ctx, aff1->n_col == 1 + total, goto error);
 597         for (;;) {
 598                 aff2 = accept_affine_list(s, v);
 599                 if (!aff2)
 600                         goto error;
 601                 isl_assert(aff2->ctx, aff2->n_col == 1 + total, goto error);
 602
 603                 bmap = isl_basic_map_extend_constraints(bmap, 0,
 604                                                 aff1->n_row * aff2->n_row);
 605                 for (i = 0; i < aff1->n_row; ++i)
 606                         for (j = 0; j < aff2->n_row; ++j)
 607                                 bmap = construct_constraint(bmap, tok->type,
 608                                                     aff1->row[i], aff2->row[j]);
 609                 isl_token_free(tok);
 610                 isl_mat_free(aff1);
 611                 aff1 = aff2;
 612
 613                 tok = isl_stream_next_token(s);
 614                 if (!is_comparator(tok)) {
 615                         if (tok)
 616                                 isl_stream_push_token(s, tok);
 617                         break;
 618                 }
 619         }
 620         isl_mat_free(aff1);
 621
 622         return bmap;
 623 error:
 624         if (tok)
 625                 isl_token_free(tok);
 626         isl_mat_free(aff1);
 627         isl_mat_free(aff2);
 628         isl_basic_map_free(bmap);
 629         return NULL;
 630 }
 631
 632 static struct isl_basic_map *add_constraints(struct isl_stream *s,
 633         struct vars *v, struct isl_basic_map *bmap)
 634 {
 635         struct isl_token *tok;
 636
 637         for (;;) {
 638                 bmap = add_constraint(s, v, bmap);
 639                 if (!bmap)
 640                         return NULL;
 641                 tok = isl_stream_next_token(s);
 642                 if (!tok) {
 643                         isl_stream_error(s, NULL, "unexpected EOF");
 644                         goto error;
 645                 }
 646                 if (tok->type != ISL_TOKEN_AND)
 647                         break;
 648                 isl_token_free(tok);
 649         }
 650         isl_stream_push_token(s, tok);
 651
 652         return bmap;
 653 error:
 654         if (tok)
 655                 isl_token_free(tok);
 656         isl_basic_map_free(bmap);
 657         return NULL;
 658 }
 659
 660 static struct isl_basic_map *read_disjunct(struct isl_stream *s,
 661         struct vars *v, __isl_take isl_dim *dim)
 662 {
 663         int seen_paren = 0;
 664         struct isl_token *tok;
 665         struct isl_basic_map *bmap;
 666
 667         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
 668         if (!bmap)
 669                 return NULL;
 670
 671         tok = isl_stream_next_token(s);
 672         if (!tok)
 673                 goto error;
 674         if (tok->type == '(') {
 675                 seen_paren = 1;
 676                 isl_token_free(tok);
 677         } else
 678                 isl_stream_push_token(s, tok);
 679
 680         bmap = add_constraints(s, v, bmap);
 681         bmap = isl_basic_map_simplify(bmap);
 682         bmap = isl_basic_map_finalize(bmap);
 683
 684         if (seen_paren && isl_stream_eat(s, ')'))
 685                 goto error;
 686
 687         return bmap;
 688 error:
 689         isl_basic_map_free(bmap);
 690         return NULL;
 691 }
 692
 693 static struct isl_map *read_disjuncts(struct isl_stream *s,
 694         struct vars *v, __isl_take isl_dim *dim)
 695 {
 696         struct isl_token *tok;
 697         struct isl_map *map;
 698
 699         tok = isl_stream_next_token(s);
 700         if (!tok) {
 701                 isl_stream_error(s, NULL, "unexpected EOF");
 702                 goto error;
 703         }
 704         if (tok->type == '}') {
 705                 isl_stream_push_token(s, tok);
 706                 return isl_map_universe(dim);
 707         }
 708         isl_stream_push_token(s, tok);
 709
 710         map = isl_map_empty(isl_dim_copy(dim));
 711         for (;;) {
 712                 struct isl_basic_map *bmap;
 713                 int n = v->n;
 714
 715                 bmap = read_disjunct(s, v, isl_dim_copy(dim));
 716                 map = isl_map_union(map, isl_map_from_basic_map(bmap));
 717
 718                 vars_drop(v, v->n - n);
 719
 720                 tok = isl_stream_next_token(s);
 721                 if (!tok || tok->type != ISL_TOKEN_OR)
 722                         break;
 723                 isl_token_free(tok);
 724         }
 725         if (tok)
 726                 isl_stream_push_token(s, tok);
 727
 728         isl_dim_free(dim);
 729         return map;
 730 error:
 731         isl_dim_free(dim);
 732         return NULL;
 733 }
 734
 735 static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
 736 {
 737         if (pos < isl_basic_map_dim(bmap, isl_dim_out))
 738                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
 739                            isl_basic_map_dim(bmap, isl_dim_in) + pos;
 740         pos -= isl_basic_map_dim(bmap, isl_dim_out);
 741
 742         if (pos < isl_basic_map_dim(bmap, isl_dim_in))
 743                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
 744         pos -= isl_basic_map_dim(bmap, isl_dim_in);
 745
 746         if (pos < isl_basic_map_dim(bmap, isl_dim_div))
 747                 return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
 748                            isl_basic_map_dim(bmap, isl_dim_in) +
 749                            isl_basic_map_dim(bmap, isl_dim_out) + pos;
 750         pos -= isl_basic_map_dim(bmap, isl_dim_div);
 751
 752         if (pos < isl_basic_map_dim(bmap, isl_dim_param))
 753                 return 1 + pos;
 754
 755         return 0;
 756 }
 757
 758 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
 759         struct isl_stream *s, __isl_take isl_basic_map *bmap)
 760 {
 761         int j;
 762         struct isl_token *tok;
 763         int type;
 764         int k;
 765         isl_int *c;
 766         unsigned nparam;
 767         unsigned dim;
 768
 769         if (!bmap)
 770                 return NULL;
 771
 772         nparam = isl_basic_map_dim(bmap, isl_dim_param);
 773         dim = isl_basic_map_dim(bmap, isl_dim_out);
 774
 775         tok = isl_stream_next_token(s);
 776         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 777                 isl_stream_error(s, tok, "expecting coefficient");
 778                 if (tok)
 779                         isl_stream_push_token(s, tok);
 780                 goto error;
 781         }
 782         if (!tok->on_new_line) {
 783                 isl_stream_error(s, tok, "coefficient should appear on new line");
 784                 isl_stream_push_token(s, tok);
 785                 goto error;
 786         }
 787
 788         type = isl_int_get_si(tok->u.v);
 789         isl_token_free(tok);
 790
 791         isl_assert(s->ctx, type == 0 || type == 1, goto error);
 792         if (type == 0) {
 793                 k = isl_basic_map_alloc_equality(bmap);
 794                 c = bmap->eq[k];
 795         } else {
 796                 k = isl_basic_map_alloc_inequality(bmap);
 797                 c = bmap->ineq[k];
 798         }
 799         if (k < 0)
 800                 goto error;
 801
 802         for (j = 0; j < 1 + isl_basic_map_total_dim(bmap); ++j) {
 803                 int pos;
 804                 tok = isl_stream_next_token(s);
 805                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
 806                         isl_stream_error(s, tok, "expecting coefficient");
 807                         if (tok)
 808                                 isl_stream_push_token(s, tok);
 809                         goto error;
 810                 }
 811                 if (tok->on_new_line) {
 812                         isl_stream_error(s, tok,
 813                                 "coefficient should not appear on new line");
 814                         isl_stream_push_token(s, tok);
 815                         goto error;
 816                 }
 817                 pos = polylib_pos_to_isl_pos(bmap, j);
 818                 isl_int_set(c[pos], tok->u.v);
 819                 isl_token_free(tok);
 820         }
 821
 822         return bmap;
 823 error:
 824         isl_basic_map_free(bmap);
 825         return NULL;
 826 }
 827
 828 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s,
 829         int nparam)
 830 {
 831         int i;
 832         struct isl_token *tok;
 833         struct isl_token *tok2;
 834         int n_row, n_col;
 835         int on_new_line;
 836         unsigned in = 0, out, local = 0;
 837         struct isl_basic_map *bmap = NULL;
 838
 839         if (nparam < 0)
 840                 nparam = 0;
 841
 842         tok = isl_stream_next_token(s);
 843         if (!tok) {
 844                 isl_stream_error(s, NULL, "unexpected EOF");
 845                 return NULL;
 846         }
 847         tok2 = isl_stream_next_token(s);
 848         if (!tok2) {
 849                 isl_token_free(tok);
 850                 isl_stream_error(s, NULL, "unexpected EOF");
 851                 return NULL;
 852         }
 853         n_row = isl_int_get_si(tok->u.v);
 854         n_col = isl_int_get_si(tok2->u.v);
 855         on_new_line = tok2->on_new_line;
 856         isl_token_free(tok2);
 857         isl_token_free(tok);
 858         isl_assert(s->ctx, !on_new_line, return NULL);
 859         isl_assert(s->ctx, n_row >= 0, return NULL);
 860         isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
 861         tok = isl_stream_next_token_on_same_line(s);
 862         if (tok) {
 863                 if (tok->type != ISL_TOKEN_VALUE) {
 864                         isl_stream_error(s, tok,
 865                                     "expecting number of output dimensions");
 866                         isl_stream_push_token(s, tok);
 867                         goto error;
 868                 }
 869                 out = isl_int_get_si(tok->u.v);
 870                 isl_token_free(tok);
 871
 872                 tok = isl_stream_next_token_on_same_line(s);
 873                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
 874                         isl_stream_error(s, tok,
 875                                     "expecting number of input dimensions");
 876                         if (tok)
 877                                 isl_stream_push_token(s, tok);
 878                         goto error;
 879                 }
 880                 in = isl_int_get_si(tok->u.v);
 881                 isl_token_free(tok);
 882
 883                 tok = isl_stream_next_token_on_same_line(s);
 884                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
 885                         isl_stream_error(s, tok,
 886                                     "expecting number of existentials");
 887                         if (tok)
 888                                 isl_stream_push_token(s, tok);
 889                         goto error;
 890                 }
 891                 local = isl_int_get_si(tok->u.v);
 892                 isl_token_free(tok);
 893
 894                 tok = isl_stream_next_token_on_same_line(s);
 895                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
 896                         isl_stream_error(s, tok,
 897                                     "expecting number of parameters");
 898                         if (tok)
 899                                 isl_stream_push_token(s, tok);
 900                         goto error;
 901                 }
 902                 nparam = isl_int_get_si(tok->u.v);
 903                 isl_token_free(tok);
 904                 if (n_col != 1 + out + in + local + nparam + 1) {
 905                         isl_stream_error(s, NULL,
 906                                     "dimensions don't match");
 907                         goto error;
 908                 }
 909         } else
 910                 out = n_col - 2 - nparam;
 911         bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
 912         if (!bmap)
 913                 return NULL;
 914
 915         for (i = 0; i < local; ++i) {
 916                 int k = isl_basic_map_alloc_div(bmap);
 917                 if (k < 0)
 918                         goto error;
 919         }
 920
 921         for (i = 0; i < n_row; ++i)
 922                 bmap = basic_map_read_polylib_constraint(s, bmap);
 923
 924         tok = isl_stream_next_token_on_same_line(s);
 925         if (tok) {
 926                 isl_stream_error(s, tok, "unexpected extra token on line");
 927                 isl_stream_push_token(s, tok);
 928                 goto error;
 929         }
 930
 931         bmap = isl_basic_map_simplify(bmap);
 932         bmap = isl_basic_map_finalize(bmap);
 933         return bmap;
 934 error:
 935         isl_basic_map_free(bmap);
 936         return NULL;
 937 }
 938
 939 static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam)
 940 {
 941         struct isl_token *tok;
 942         struct isl_token *tok2;
 943         int i, n;
 944         struct isl_map *map;
 945
 946         tok = isl_stream_next_token(s);
 947         if (!tok) {
 948                 isl_stream_error(s, NULL, "unexpected EOF");
 949                 return NULL;
 950         }
 951         tok2 = isl_stream_next_token_on_same_line(s);
 952         if (tok2) {
 953                 isl_stream_push_token(s, tok2);
 954                 isl_stream_push_token(s, tok);
 955                 return isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
 956         }
 957         n = isl_int_get_si(tok->u.v);
 958         isl_token_free(tok);
 959
 960         isl_assert(s->ctx, n >= 1, return NULL);
 961
 962         map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
 963
 964         for (i = 1; i < n; ++i)
 965                 map = isl_map_union(map,
 966                         isl_map_from_basic_map(basic_map_read_polylib(s, nparam)));
 967
 968         return map;
 969 }
 970
 971 static struct isl_map *map_read_body(struct isl_stream *s,
 972         __isl_take isl_basic_map *bmap, struct vars *v)
 973 {
 974         struct isl_map *map = NULL;
 975         struct isl_token *tok;
 976         int n = v->n;
 977
 978         bmap = read_tuple(s, bmap, isl_dim_in, v);
 979         if (!bmap)
 980                 goto error;
 981         tok = isl_stream_next_token(s);
 982         if (tok && tok->type == ISL_TOKEN_TO) {
 983                 isl_token_free(tok);
 984                 bmap = read_tuple(s, bmap, isl_dim_out, v);
 985                 if (!bmap)
 986                         goto error;
 987         } else {
 988                 bmap = isl_basic_map_reverse(bmap);
 989                 if (tok)
 990                         isl_stream_push_token(s, tok);
 991         }
 992         tok = isl_stream_next_token(s);
 993         if (!tok) {
 994                 isl_stream_error(s, NULL, "unexpected EOF");
 995                 goto error;
 996         }
 997         map = isl_map_from_basic_map(isl_basic_map_copy(bmap));
 998         if (tok->type == ':') {
 999                 isl_token_free(tok);
1000                 map = isl_map_intersect(map,
1001                             read_disjuncts(s, v, isl_basic_map_get_dim(bmap)));
1002         } else
1003                 isl_stream_push_token(s, tok);
1004
1005         vars_drop(v, v->n - n);
1006
1007         isl_basic_map_free(bmap);
1008         return map;
1009 error:
1010         isl_basic_map_free(bmap);
1011         return NULL;
1012 }
1013
1014 static struct isl_map *map_read(struct isl_stream *s, int nparam)
1015 {
1016         struct isl_basic_map *bmap = NULL;
1017         struct isl_map *map = NULL;
1018         struct isl_token *tok;
1019         struct vars *v = NULL;
1020
1021         tok = isl_stream_next_token(s);
1022         if (!tok) {
1023                 isl_stream_error(s, NULL, "unexpected EOF");
1024                 goto error;
1025         }
1026         if (tok->type == ISL_TOKEN_VALUE) {
1027                 isl_stream_push_token(s, tok);
1028                 return map_read_polylib(s, nparam);
1029         }
1030         v = vars_new(s->ctx);
1031         bmap = isl_basic_map_alloc(s->ctx, 0, 0, 0, 0, 0, 0);
1032         if (tok->type == '[') {
1033                 isl_stream_push_token(s, tok);
1034                 bmap = read_tuple(s, bmap, isl_dim_param, v);
1035                 if (!bmap)
1036                         goto error;
1037                 if (nparam >= 0)
1038                         isl_assert(s->ctx, nparam == v->n, goto error);
1039                 tok = isl_stream_next_token(s);
1040                 if (!tok || tok->type != ISL_TOKEN_TO) {
1041                         isl_stream_error(s, tok, "expecting '->'");
1042                         if (tok)
1043                                 isl_stream_push_token(s, tok);
1044                         goto error;
1045                 }
1046                 isl_token_free(tok);
1047                 tok = isl_stream_next_token(s);
1048         } if (nparam > 0)
1049                 bmap = isl_basic_map_add(bmap, isl_dim_param, nparam);
1050         if (!tok || tok->type != '{') {
1051                 isl_stream_error(s, tok, "expecting '{'");
1052                 if (tok)
1053                         isl_stream_push_token(s, tok);
1054                 goto error;
1055         }
1056         isl_token_free(tok);
1057
1058         for (;;) {
1059                 isl_map *m = map_read_body(s, isl_basic_map_copy(bmap), v);
1060                 if (!m)
1061                         break;
1062                 if (map)
1063                         map = isl_map_union(map, m);
1064                 else
1065                         map = m;
1066                 tok = isl_stream_next_token(s);
1067                 if (!tok || tok->type != ';')
1068                         break;
1069                 isl_token_free(tok);
1070         }
1071
1072         if (tok && tok->type == '}') {
1073                 isl_token_free(tok);
1074         } else {
1075                 isl_stream_error(s, tok, "unexpected isl_token");
1076                 if (tok)
1077                         isl_token_free(tok);
1078                 goto error;
1079         }
1080         vars_free(v);
1081         isl_basic_map_free(bmap);
1082
1083         return map;
1084 error:
1085         isl_basic_map_free(bmap);
1086         isl_map_free(map);
1087         if (v)
1088                 vars_free(v);
1089         return NULL;
1090 }
1091
1092 static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam)
1093 {
1094         struct isl_map *map;
1095         struct isl_basic_map *bmap;
1096
1097         map = map_read(s, nparam);
1098         if (!map)
1099                 return NULL;
1100
1101         isl_assert(map->ctx, map->n <= 1, goto error);
1102
1103         if (map->n == 0)
1104                 bmap = isl_basic_map_empty_like_map(map);
1105         else
1106                 bmap = isl_basic_map_copy(map->p[0]);
1107
1108         isl_map_free(map);
1109
1110         return bmap;
1111 error:
1112         isl_map_free(map);
1113         return NULL;
1114 }
1115
1116 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
1117                 FILE *input, int nparam)
1118 {
1119         struct isl_basic_map *bmap;
1120         struct isl_stream *s = isl_stream_new_file(ctx, input);
1121         if (!s)
1122                 return NULL;
1123         bmap = basic_map_read(s, nparam);
1124         isl_stream_free(s);
1125         return bmap;
1126 }
1127
1128 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
1129                 FILE *input, int nparam)
1130 {
1131         struct isl_basic_map *bmap;
1132         bmap = isl_basic_map_read_from_file(ctx, input, nparam);
1133         if (!bmap)
1134                 return NULL;
1135         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
1136         return (struct isl_basic_set *)bmap;
1137 error:
1138         isl_basic_map_free(bmap);
1139         return NULL;
1140 }
1141
1142 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
1143                 const char *str, int nparam)
1144 {
1145         struct isl_basic_map *bmap;
1146         struct isl_stream *s = isl_stream_new_str(ctx, str);
1147         if (!s)
1148                 return NULL;
1149         bmap = basic_map_read(s, nparam);
1150         isl_stream_free(s);
1151         return bmap;
1152 }
1153
1154 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
1155                 const char *str, int nparam)
1156 {
1157         struct isl_basic_map *bmap;
1158         bmap = isl_basic_map_read_from_str(ctx, str, nparam);
1159         if (!bmap)
1160                 return NULL;
1161         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
1162         return (struct isl_basic_set *)bmap;
1163 error:
1164         isl_basic_map_free(bmap);
1165         return NULL;
1166 }
1167
1168 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
1169                 FILE *input, int nparam)
1170 {
1171         struct isl_map *map;
1172         struct isl_stream *s = isl_stream_new_file(ctx, input);
1173         if (!s)
1174                 return NULL;
1175         map = map_read(s, nparam);
1176         isl_stream_free(s);
1177         return map;
1178 }
1179
1180 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
1181                 const char *str, int nparam)
1182 {
1183         struct isl_map *map;
1184         struct isl_stream *s = isl_stream_new_str(ctx, str);
1185         if (!s)
1186                 return NULL;
1187         map = map_read(s, nparam);
1188         isl_stream_free(s);
1189         return map;
1190 }
1191
1192 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
1193                 FILE *input, int nparam)
1194 {
1195         struct isl_map *map;
1196         map = isl_map_read_from_file(ctx, input, nparam);
1197         if (!map)
1198                 return NULL;
1199         isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
1200         return (struct isl_set *)map;
1201 error:
1202         isl_map_free(map);
1203         return NULL;
1204 }
1205
1206 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
1207                 const char *str, int nparam)
1208 {
1209         struct isl_map *map;
1210         map = isl_map_read_from_str(ctx, str, nparam);
1211         if (!map)
1212                 return NULL;
1213         isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
1214         return (struct isl_set *)map;
1215 error:
1216         isl_map_free(map);
1217         return NULL;
1218 }
1219
1220 static char *next_line(FILE *input, char *line, unsigned len)
1221 {
1222         char *p;
1223
1224         do {
1225                 if (!(p = fgets(line, len, input)))
1226                         return NULL;
1227                 while (isspace(*p) && *p != '\n')
1228                         ++p;
1229         } while (*p == '#' || *p == '\n');
1230
1231         return p;
1232 }
1233
1234 static struct isl_vec *isl_vec_read_from_file_polylib(struct isl_ctx *ctx,
1235                 FILE *input)
1236 {
1237         struct isl_vec *vec = NULL;
1238         char line[1024];
1239         char val[1024];
1240         char *p;
1241         unsigned size;
1242         int j;
1243         int n;
1244         int offset;
1245
1246         isl_assert(ctx, next_line(input, line, sizeof(line)), return NULL);
1247         isl_assert(ctx, sscanf(line, "%u", &size) == 1, return NULL);
1248
1249         vec = isl_vec_alloc(ctx, size);
1250
1251         p = next_line(input, line, sizeof(line));
1252         isl_assert(ctx, p, goto error);
1253
1254         for (j = 0; j < size; ++j) {
1255                 n = sscanf(p, "%s%n", val, &offset);
1256                 isl_assert(ctx, n != 0, goto error);
1257                 isl_int_read(vec->el[j], val);
1258                 p += offset;
1259         }
1260
1261         return vec;
1262 error:
1263         isl_vec_free(vec);
1264         return NULL;
1265 }
1266
1267 struct isl_vec *isl_vec_read_from_file(struct isl_ctx *ctx,
1268                 FILE *input, unsigned input_format)
1269 {
1270         if (input_format == ISL_FORMAT_POLYLIB)
1271                 return isl_vec_read_from_file_polylib(ctx, input);
1272         else
1273                 isl_assert(ctx, 0, return NULL);
1274 }