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