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 struct variable *variable_new(struct vars *v, const char *name, int len,
  65                                 int pos)
  66 {
  67         struct variable *var;
  68         var = isl_alloc_type(v->ctx, struct variable);
  69         if (!var)
  70                 goto error;
  71         var->name = strdup(name);
  72         var->name[len] = '\0';
  73         var->pos = pos;
  74         var->next = v->v;
  75         return var;
  76 error:
  77         variable_free(v->v);
  78         return NULL;
  79 }
  80
  81 static int vars_pos(struct vars *v, const char *s, int len)
  82 {
  83         int pos;
  84         struct variable *q;
  85
  86         if (len == -1)
  87                 len = strlen(s);
  88         for (q = v->v; q; q = q->next) {
  89                 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
  90                         break;
  91         }
  92         if (q)
  93                 pos = q->pos;
  94         else {
  95                 pos = v->n;
  96                 v->v = variable_new(v, s, len, v->n);
  97                 if (!v->v)
  98                         return -1;
  99                 v->n++;
 100         }
 101         return pos;
 102 }
 103
 104 static struct vars *read_var_list(struct isl_stream *s, struct vars *v)
 105 {
 106         struct isl_token *tok;
 107
 108         while ((tok = isl_stream_next_token(s)) != NULL) {
 109                 int p;
 110                 int n = v->n;
 111
 112                 if (tok->type != ISL_TOKEN_IDENT)
 113                         break;
 114
 115                 p = vars_pos(v, tok->u.s, -1);
 116                 if (p < 0)
 117                         goto error;
 118                 if (p < n) {
 119                         isl_stream_error(s, tok, "expecting unique identifier");
 120                         goto error;
 121                 }
 122                 isl_token_free(tok);
 123                 tok = isl_stream_next_token(s);
 124                 if (!tok || tok->type != ',')
 125                         break;
 126
 127                 isl_token_free(tok);
 128         }
 129         if (tok)
 130                 isl_stream_push_token(s, tok);
 131
 132         return v;
 133 error:
 134         isl_token_free(tok);
 135         vars_free(v);
 136         return NULL;
 137 }
 138
 139 static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v)
 140 {
 141         struct isl_token *tok = NULL;
 142         struct isl_vec *aff;
 143
 144         aff = isl_vec_alloc(v->ctx, 1 + v->n);
 145         isl_seq_clr(aff->el, aff->size);
 146         if (!aff)
 147                 return NULL;
 148
 149         for (;;) {
 150                 tok = isl_stream_next_token(s);
 151                 if (!tok) {
 152                         isl_stream_error(s, NULL, "unexpected EOF");
 153                         goto error;
 154                 }
 155                 if (tok->type == ISL_TOKEN_IDENT) {
 156                         int n = v->n;
 157                         int pos = vars_pos(v, tok->u.s, -1);
 158                         if (pos < 0)
 159                                 goto error;
 160                         if (pos >= n) {
 161                                 isl_stream_error(s, tok, "unknown identifier");
 162                                 goto error;
 163                         }
 164                         isl_int_add_ui(aff->el[1 + pos], aff->el[1 + pos], 1);
 165                 } else if (tok->type == ISL_TOKEN_VALUE) {
 166                         struct isl_token *tok2;
 167                         int n = v->n;
 168                         int pos = -1;
 169                         tok2 = isl_stream_next_token(s);
 170                         if (tok2 && tok2->type == ISL_TOKEN_IDENT) {
 171                                 pos = vars_pos(v, tok2->u.s, -1);
 172                                 if (pos < 0)
 173                                         goto error;
 174                                 if (pos >= n) {
 175                                         isl_stream_error(s, tok2,
 176                                                 "unknown identifier");
 177                                         isl_token_free(tok2);
 178                                         goto error;
 179                                 }
 180                                 isl_token_free(tok2);
 181                         } else if (tok2)
 182                                 isl_stream_push_token(s, tok2);
 183                         isl_int_add(aff->el[1 + pos],
 184                                         aff->el[1 + pos], tok->u.v);
 185                 } else if (tok->type == '+') {
 186                         /* nothing */
 187                 } else {
 188                         isl_stream_push_token(s, tok);
 189                         break;
 190                 }
 191                 isl_token_free(tok);
 192         }
 193
 194         return aff;
 195 error:
 196         isl_vec_free(aff);
 197         return NULL;
 198 }
 199
 200 static struct isl_basic_map *add_div_definition(struct isl_stream *s,
 201         struct vars *v, struct isl_basic_map *bmap, int k)
 202 {
 203         struct isl_token *tok;
 204         int seen_paren = 0;
 205         struct isl_vec *aff;
 206
 207         if (isl_stream_eat(s, '['))
 208                 goto error;
 209
 210         tok = isl_stream_next_token(s);
 211         if (!tok)
 212                 goto error;
 213         if (tok->type == '(') {
 214                 seen_paren = 1;
 215                 isl_token_free(tok);
 216         } else
 217                 isl_stream_push_token(s, tok);
 218
 219         aff = accept_affine(s, v);
 220         if (!aff)
 221                 goto error;
 222
 223         isl_seq_cpy(bmap->div[k] + 1, aff->el, aff->size);
 224
 225         isl_vec_free(aff);
 226
 227         if (seen_paren && isl_stream_eat(s, ')'))
 228                 goto error;
 229         if (isl_stream_eat(s, '/'))
 230                 goto error;
 231
 232         tok = isl_stream_next_token(s);
 233         if (!tok)
 234                 goto error;
 235         if (tok->type != ISL_TOKEN_VALUE) {
 236                 isl_stream_error(s, tok, "expected denominator");
 237                 isl_stream_push_token(s, tok);
 238                 goto error;
 239         }
 240         isl_int_set(bmap->div[k][0], tok->u.v);
 241         isl_token_free(tok);
 242
 243         if (isl_stream_eat(s, ']'))
 244                 goto error;
 245
 246         if (isl_basic_map_add_div_constraints(bmap, k) < 0)
 247                 goto error;
 248
 249         return bmap;
 250 error:
 251         isl_basic_map_free(bmap);
 252         return NULL;
 253 }
 254
 255 static struct isl_basic_map *read_defined_var_list(struct isl_stream *s,
 256         struct vars *v, struct isl_basic_map *bmap)
 257 {
 258         struct isl_token *tok;
 259
 260         while ((tok = isl_stream_next_token(s)) != NULL) {
 261                 int k;
 262                 int p;
 263                 int n = v->n;
 264                 unsigned total = isl_basic_map_total_dim(bmap);
 265
 266                 if (tok->type != ISL_TOKEN_IDENT)
 267                         break;
 268
 269                 p = vars_pos(v, tok->u.s, -1);
 270                 if (p < 0)
 271                         goto error;
 272                 if (p < n) {
 273                         isl_stream_error(s, tok, "expecting unique identifier");
 274                         goto error;
 275                 }
 276                 isl_token_free(tok);
 277
 278                 bmap = isl_basic_map_cow(bmap);
 279                 bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
 280                                                 1, 0, 2);
 281
 282                 if ((k = isl_basic_map_alloc_div(bmap)) < 0)
 283                         goto error;
 284                 isl_seq_clr(bmap->div[k], 1 + 1 + total);
 285
 286                 tok = isl_stream_next_token(s);
 287                 if (tok && tok->type == '=') {
 288                         isl_token_free(tok);
 289                         bmap = add_div_definition(s, v, bmap, k);
 290                         tok = isl_stream_next_token(s);
 291                 }
 292
 293                 if (!tok || tok->type != ',')
 294                         break;
 295
 296                 isl_token_free(tok);
 297         }
 298         if (tok)
 299                 isl_stream_push_token(s, tok);
 300
 301         return bmap;
 302 error:
 303         isl_token_free(tok);
 304         isl_basic_map_free(bmap);
 305         return NULL;
 306 }
 307
 308 static struct vars *read_tuple(struct isl_stream *s, struct vars *v)
 309 {
 310         struct isl_token *tok;
 311
 312         tok = isl_stream_next_token(s);
 313         if (!tok || tok->type != '[') {
 314                 isl_stream_error(s, tok, "expecting '['");
 315                 goto error;
 316         }
 317         isl_token_free(tok);
 318         v = read_var_list(s, v);
 319         tok = isl_stream_next_token(s);
 320         if (!tok || tok->type != ']') {
 321                 isl_stream_error(s, tok, "expecting ']'");
 322                 goto error;
 323         }
 324         isl_token_free(tok);
 325
 326         return v;
 327 error:
 328         if (tok)
 329                 isl_token_free(tok);
 330         vars_free(v);
 331         return NULL;
 332 }
 333
 334 static struct isl_basic_map *add_constraints(struct isl_stream *s,
 335         struct vars **v, struct isl_basic_map *bmap);
 336
 337 static struct isl_basic_map *add_exists(struct isl_stream *s,
 338         struct vars **v, struct isl_basic_map *bmap)
 339 {
 340         struct isl_token *tok;
 341         int n = (*v)->n;
 342         int extra;
 343         int seen_paren = 0;
 344         int i;
 345         unsigned total;
 346
 347         tok = isl_stream_next_token(s);
 348         if (!tok)
 349                 goto error;
 350         if (tok->type == '(') {
 351                 seen_paren = 1;
 352                 isl_token_free(tok);
 353         } else
 354                 isl_stream_push_token(s, tok);
 355
 356         bmap = read_defined_var_list(s, *v, bmap);
 357         if (!bmap)
 358                 goto error;
 359
 360         if (isl_stream_eat(s, ':'))
 361                 goto error;
 362         bmap = add_constraints(s, v, bmap);
 363         if (seen_paren && isl_stream_eat(s, ')'))
 364                 goto error;
 365         return bmap;
 366 error:
 367         isl_basic_map_free(bmap);
 368         return NULL;
 369 }
 370
 371 static struct isl_basic_map *add_constraint(struct isl_stream *s,
 372         struct vars **v, struct isl_basic_map *bmap)
 373 {
 374         unsigned total = isl_basic_map_total_dim(bmap);
 375         int k;
 376         struct isl_token *tok = NULL;
 377         struct isl_vec *aff1 = NULL, *aff2 = NULL;
 378
 379         tok = isl_stream_next_token(s);
 380         if (!tok)
 381                 goto error;
 382         if (tok->type == ISL_TOKEN_EXISTS) {
 383                 isl_token_free(tok);
 384                 return add_exists(s, v, bmap);
 385         }
 386         isl_stream_push_token(s, tok);
 387         tok = NULL;
 388
 389         bmap = isl_basic_map_cow(bmap);
 390         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
 391         k = isl_basic_map_alloc_inequality(bmap);
 392         if (k < 0)
 393                 goto error;
 394
 395         aff1 = accept_affine(s, *v);
 396         if (!aff1)
 397                 goto error;
 398         tok = isl_stream_next_token(s);
 399         switch (tok->type) {
 400         case ISL_TOKEN_LT:
 401         case ISL_TOKEN_GT:
 402         case ISL_TOKEN_LE:
 403         case ISL_TOKEN_GE:
 404         case '=':
 405                 break;
 406         default:
 407                 isl_stream_error(s, tok, "missing operator");
 408                 isl_stream_push_token(s, tok);
 409                 tok = NULL;
 410                 goto error;
 411         }
 412         aff2 = accept_affine(s, *v);
 413         if (!aff2)
 414                 goto error;
 415         isl_assert(aff1->ctx, aff1->size == 1 + total, goto error);
 416         isl_assert(aff2->ctx, aff2->size == 1 + total, goto error);
 417
 418         if (tok->type == ISL_TOKEN_LE)
 419                 isl_seq_combine(bmap->ineq[k], (*v)->ctx->negone, aff1->el,
 420                                                (*v)->ctx->one, aff2->el,
 421                                                aff1->size);
 422         else if (tok->type == ISL_TOKEN_GE)
 423                 isl_seq_combine(bmap->ineq[k], (*v)->ctx->one, aff1->el,
 424                                                (*v)->ctx->negone, aff2->el,
 425                                                aff1->size);
 426         else if (tok->type == ISL_TOKEN_LT) {
 427                 isl_seq_combine(bmap->ineq[k], (*v)->ctx->negone, aff1->el,
 428                                                (*v)->ctx->one, aff2->el,
 429                                                aff1->size);
 430                 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
 431         } else if (tok->type == ISL_TOKEN_GT) {
 432                 isl_seq_combine(bmap->ineq[k], (*v)->ctx->one, aff1->el,
 433                                                (*v)->ctx->negone, aff2->el,
 434                                                aff1->size);
 435                 isl_int_sub_ui(bmap->ineq[k][0], bmap->ineq[k][0], 1);
 436         } else {
 437                 isl_seq_combine(bmap->ineq[k], (*v)->ctx->one, aff1->el,
 438                                                (*v)->ctx->negone, aff2->el,
 439                                                aff1->size);
 440                 isl_basic_map_inequality_to_equality(bmap, k);
 441         }
 442         isl_token_free(tok);
 443         isl_vec_free(aff1);
 444         isl_vec_free(aff2);
 445
 446         return bmap;
 447 error:
 448         if (tok)
 449                 isl_token_free(tok);
 450         isl_vec_free(aff1);
 451         isl_vec_free(aff2);
 452         isl_basic_map_free(bmap);
 453         return NULL;
 454 }
 455
 456 static struct isl_basic_map *add_constraints(struct isl_stream *s,
 457         struct vars **v, struct isl_basic_map *bmap)
 458 {
 459         struct isl_token *tok;
 460
 461         for (;;) {
 462                 bmap = add_constraint(s, v, bmap);
 463                 if (!bmap)
 464                         return NULL;
 465                 tok = isl_stream_next_token(s);
 466                 if (!tok) {
 467                         isl_stream_error(s, NULL, "unexpected EOF");
 468                         goto error;
 469                 }
 470                 if (tok->type != ISL_TOKEN_AND)
 471                         break;
 472                 isl_token_free(tok);
 473         }
 474         isl_stream_push_token(s, tok);
 475
 476         return bmap;
 477 error:
 478         if (tok)
 479                 isl_token_free(tok);
 480         isl_basic_map_free(bmap);
 481         return NULL;
 482 }
 483
 484 static struct isl_basic_map *read_disjunct(struct isl_stream *s,
 485         struct vars **v, __isl_take isl_dim *dim)
 486 {
 487         struct isl_basic_map *bmap;
 488
 489         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0);
 490         if (!bmap)
 491                 return NULL;
 492
 493         bmap = add_constraints(s, v, bmap);
 494         bmap = isl_basic_map_simplify(bmap);
 495         bmap = isl_basic_map_finalize(bmap);
 496         return bmap;
 497 }
 498
 499 static struct isl_map *read_disjuncts(struct isl_stream *s,
 500         struct vars **v, __isl_take isl_dim *dim)
 501 {
 502         struct isl_token *tok;
 503         struct isl_map *map;
 504
 505         tok = isl_stream_next_token(s);
 506         if (!tok) {
 507                 isl_stream_error(s, NULL, "unexpected EOF");
 508                 goto error;
 509         }
 510         if (tok->type == '}') {
 511                 isl_stream_push_token(s, tok);
 512                 return isl_map_universe(dim);
 513         }
 514         isl_stream_push_token(s, tok);
 515
 516         map = isl_map_empty(isl_dim_copy(dim));
 517         for (;;) {
 518                 struct isl_basic_map *bmap;
 519
 520                 bmap = read_disjunct(s, v, isl_dim_copy(dim));
 521                 map = isl_map_union(map, isl_map_from_basic_map(bmap));
 522
 523                 tok = isl_stream_next_token(s);
 524                 if (!tok || tok->type != ISL_TOKEN_OR)
 525                         break;
 526                 isl_token_free(tok);
 527         }
 528         if (tok)
 529                 isl_stream_push_token(s, tok);
 530
 531         isl_dim_free(dim);
 532         return map;
 533 error:
 534         isl_dim_free(dim);
 535         return NULL;
 536 }
 537
 538 static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
 539         struct isl_stream *s, __isl_take isl_basic_map *bmap)
 540 {
 541         int j;
 542         struct isl_token *tok;
 543         int type;
 544         int k;
 545         isl_int *c;
 546         unsigned nparam;
 547         unsigned dim;
 548
 549         if (!bmap)
 550                 return NULL;
 551
 552         nparam = isl_basic_map_dim(bmap, isl_dim_param);
 553         dim = isl_basic_map_dim(bmap, isl_dim_out);
 554
 555         tok = isl_stream_next_token(s);
 556         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 557                 isl_stream_error(s, tok, "expecting coefficient");
 558                 if (tok)
 559                         isl_stream_push_token(s, tok);
 560                 goto error;
 561         }
 562         if (!tok->on_new_line) {
 563                 isl_stream_error(s, tok, "coefficient should appear on new line");
 564                 isl_stream_push_token(s, tok);
 565                 goto error;
 566         }
 567
 568         type = isl_int_get_si(tok->u.v);
 569         isl_token_free(tok);
 570
 571         isl_assert(s->ctx, type == 0 || type == 1, goto error);
 572         if (type == 0) {
 573                 k = isl_basic_map_alloc_equality(bmap);
 574                 c = bmap->eq[k];
 575         } else {
 576                 k = isl_basic_map_alloc_inequality(bmap);
 577                 c = bmap->ineq[k];
 578         }
 579         if (k < 0)
 580                 goto error;
 581
 582         for (j = 0; j < dim; ++j) {
 583                 tok = isl_stream_next_token(s);
 584                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
 585                         isl_stream_error(s, tok, "expecting coefficient");
 586                         if (tok)
 587                                 isl_stream_push_token(s, tok);
 588                         goto error;
 589                 }
 590                 isl_int_set(c[1 + nparam + j], tok->u.v);
 591                 isl_token_free(tok);
 592         }
 593         for (j = 0; j < nparam; ++j) {
 594                 tok = isl_stream_next_token(s);
 595                 if (!tok || tok->type != ISL_TOKEN_VALUE) {
 596                         isl_stream_error(s, tok, "expecting coefficient");
 597                         if (tok)
 598                                 isl_stream_push_token(s, tok);
 599                         goto error;
 600                 }
 601                 isl_int_set(c[1 + j], tok->u.v);
 602                 isl_token_free(tok);
 603         }
 604         tok = isl_stream_next_token(s);
 605         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 606                 isl_stream_error(s, tok, "expecting coefficient");
 607                 if (tok)
 608                         isl_stream_push_token(s, tok);
 609                 goto error;
 610         }
 611         isl_int_set(c[0], tok->u.v);
 612         isl_token_free(tok);
 613
 614         return bmap;
 615 error:
 616         isl_basic_map_free(bmap);
 617         return NULL;
 618 }
 619
 620 static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s,
 621         int nparam)
 622 {
 623         int i;
 624         struct isl_token *tok;
 625         struct isl_token *tok2;
 626         int n_row, n_col;
 627         int on_new_line;
 628         unsigned dim;
 629         struct isl_basic_map *bmap = NULL;
 630
 631         if (nparam < 0)
 632                 nparam = 0;
 633
 634         tok = isl_stream_next_token(s);
 635         if (!tok) {
 636                 isl_stream_error(s, NULL, "unexpected EOF");
 637                 return NULL;
 638         }
 639         tok2 = isl_stream_next_token(s);
 640         if (!tok2) {
 641                 isl_token_free(tok);
 642                 isl_stream_error(s, NULL, "unexpected EOF");
 643                 return NULL;
 644         }
 645         n_row = isl_int_get_si(tok->u.v);
 646         n_col = isl_int_get_si(tok2->u.v);
 647         on_new_line = tok2->on_new_line;
 648         isl_token_free(tok2);
 649         isl_token_free(tok);
 650         isl_assert(s->ctx, !on_new_line, return NULL);
 651         isl_assert(s->ctx, n_row >= 0, return NULL);
 652         isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
 653         dim = n_col - 2 - nparam;
 654         bmap = isl_basic_map_alloc(s->ctx, nparam, 0, dim, 0, n_row, n_row);
 655         if (!bmap)
 656                 return NULL;
 657
 658         for (i = 0; i < n_row; ++i)
 659                 bmap = basic_map_read_polylib_constraint(s, bmap);
 660
 661         bmap = isl_basic_map_simplify(bmap);
 662         bmap = isl_basic_map_finalize(bmap);
 663         return bmap;
 664 }
 665
 666 static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam)
 667 {
 668         struct isl_token *tok;
 669         struct isl_token *tok2;
 670         int i, n;
 671         struct isl_map *map;
 672
 673         tok = isl_stream_next_token(s);
 674         if (!tok) {
 675                 isl_stream_error(s, NULL, "unexpected EOF");
 676                 return NULL;
 677         }
 678         tok2 = isl_stream_next_token(s);
 679         if (!tok2) {
 680                 isl_token_free(tok);
 681                 isl_stream_error(s, NULL, "unexpected EOF");
 682                 return NULL;
 683         }
 684         if (!tok2->on_new_line) {
 685                 isl_stream_push_token(s, tok2);
 686                 isl_stream_push_token(s, tok);
 687                 return isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
 688         }
 689         isl_stream_push_token(s, tok2);
 690         n = isl_int_get_si(tok->u.v);
 691         isl_token_free(tok);
 692
 693         isl_assert(s->ctx, n >= 1, return NULL);
 694
 695         map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam));
 696
 697         for (i = 1; i < n; ++i)
 698                 map = isl_map_union(map,
 699                         isl_map_from_basic_map(basic_map_read_polylib(s, nparam)));
 700
 701         return map;
 702 }
 703
 704 static struct isl_dim *set_names(struct isl_dim *dim, struct vars *vars,
 705         enum isl_dim_type type, int offset, int n)
 706 {
 707         int i;
 708         struct variable *v;
 709
 710         for (i = 0, v = vars->v; i < offset; ++i, v = v->next)
 711                 ;
 712         for (i = n - 1; i >= 0; --i, v = v->next)
 713                 dim = isl_dim_set_name(dim, type, i, v->name);
 714
 715         return dim;
 716 }
 717
 718 static struct isl_dim *dim_from_vars(struct vars *vars,
 719         int nparam, int n_in, int n_out)
 720 {
 721         struct isl_dim *dim;
 722
 723         dim = isl_dim_alloc(vars->ctx, nparam, n_in, n_out);
 724         dim = set_names(dim, vars, isl_dim_param, n_out + n_in, nparam);
 725         dim = set_names(dim, vars, isl_dim_in, n_out, n_in);
 726         dim = set_names(dim, vars, isl_dim_out, 0, n_out);
 727
 728         return dim;
 729 }
 730
 731 static struct isl_map *map_read(struct isl_stream *s, int nparam)
 732 {
 733         struct isl_dim *dim = NULL;
 734         struct isl_map *map = NULL;
 735         struct isl_token *tok;
 736         struct vars *v = NULL;
 737         int n1;
 738         int n2;
 739
 740         tok = isl_stream_next_token(s);
 741         if (!tok) {
 742                 isl_stream_error(s, NULL, "unexpected EOF");
 743                 goto error;
 744         }
 745         if (tok->type == ISL_TOKEN_VALUE) {
 746                 isl_stream_push_token(s, tok);
 747                 return map_read_polylib(s, nparam);
 748         }
 749         v = vars_new(s->ctx);
 750         if (tok->type == '[') {
 751                 isl_stream_push_token(s, tok);
 752                 v = read_tuple(s, v);
 753                 if (!v)
 754                         return NULL;
 755                 if (nparam >= 0)
 756                         isl_assert(s->ctx, nparam == v->n, goto error);
 757                 nparam = v->n;
 758                 tok = isl_stream_next_token(s);
 759                 if (!tok || tok->type != ISL_TOKEN_TO) {
 760                         isl_stream_error(s, tok, "expecting '->'");
 761                         if (tok)
 762                                 isl_stream_push_token(s, tok);
 763                         goto error;
 764                 }
 765                 isl_token_free(tok);
 766                 tok = isl_stream_next_token(s);
 767         }
 768         if (nparam < 0)
 769                 nparam = 0;
 770         if (!tok || tok->type != '{') {
 771                 isl_stream_error(s, tok, "expecting '{'");
 772                 if (tok)
 773                         isl_stream_push_token(s, tok);
 774                 goto error;
 775         }
 776         isl_token_free(tok);
 777         v = read_tuple(s, v);
 778         if (!v)
 779                 return NULL;
 780         n1 = v->n - nparam;
 781         tok = isl_stream_next_token(s);
 782         if (tok && tok->type == ISL_TOKEN_TO) {
 783                 isl_token_free(tok);
 784                 v = read_tuple(s, v);
 785                 if (!v)
 786                         return NULL;
 787                 n2 = v->n - n1 - nparam;
 788         } else {
 789                 if (tok)
 790                         isl_stream_push_token(s, tok);
 791                 n2 = n1;
 792                 n1 = 0;
 793         }
 794         dim = dim_from_vars(v, nparam, n1, n2);
 795         tok = isl_stream_next_token(s);
 796         if (!tok) {
 797                 isl_stream_error(s, NULL, "unexpected EOF");
 798                 goto error;
 799         }
 800         if (tok->type == ':') {
 801                 isl_token_free(tok);
 802                 map = read_disjuncts(s, &v, isl_dim_copy(dim));
 803                 tok = isl_stream_next_token(s);
 804         } else
 805                 map = isl_map_universe(isl_dim_copy(dim));
 806         if (tok && tok->type == '}') {
 807                 isl_token_free(tok);
 808         } else {
 809                 isl_stream_error(s, tok, "unexpected isl_token");
 810                 if (tok)
 811                         isl_token_free(tok);
 812                 goto error;
 813         }
 814         vars_free(v);
 815         isl_dim_free(dim);
 816
 817         return map;
 818 error:
 819         isl_dim_free(dim);
 820         isl_map_free(map);
 821         if (v)
 822                 vars_free(v);
 823         return NULL;
 824 }
 825
 826 static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam)
 827 {
 828         struct isl_map *map;
 829         struct isl_basic_map *bmap;
 830
 831         map = map_read(s, nparam);
 832         if (!map)
 833                 return NULL;
 834
 835         isl_assert(map->ctx, map->n <= 1, goto error);
 836
 837         if (map->n == 0)
 838                 bmap = isl_basic_map_empty_like_map(map);
 839         else
 840                 bmap = isl_basic_map_copy(map->p[0]);
 841
 842         isl_map_free(map);
 843
 844         return bmap;
 845 error:
 846         isl_map_free(map);
 847         return NULL;
 848 }
 849
 850 __isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
 851                 FILE *input, int nparam)
 852 {
 853         struct isl_basic_map *bmap;
 854         struct isl_stream *s = isl_stream_new_file(ctx, input);
 855         if (!s)
 856                 return NULL;
 857         bmap = basic_map_read(s, nparam);
 858         isl_stream_free(s);
 859         return bmap;
 860 }
 861
 862 __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
 863                 FILE *input, int nparam)
 864 {
 865         struct isl_basic_map *bmap;
 866         bmap = isl_basic_map_read_from_file(ctx, input, nparam);
 867         if (!bmap)
 868                 return NULL;
 869         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
 870         return (struct isl_basic_set *)bmap;
 871 error:
 872         isl_basic_map_free(bmap);
 873         return NULL;
 874 }
 875
 876 struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
 877                 const char *str, int nparam)
 878 {
 879         struct isl_basic_map *bmap;
 880         struct isl_stream *s = isl_stream_new_str(ctx, str);
 881         if (!s)
 882                 return NULL;
 883         bmap = basic_map_read(s, nparam);
 884         isl_stream_free(s);
 885         return bmap;
 886 }
 887
 888 struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
 889                 const char *str, int nparam)
 890 {
 891         struct isl_basic_map *bmap;
 892         bmap = isl_basic_map_read_from_str(ctx, str, nparam);
 893         if (!bmap)
 894                 return NULL;
 895         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
 896         return (struct isl_basic_set *)bmap;
 897 error:
 898         isl_basic_map_free(bmap);
 899         return NULL;
 900 }
 901
 902 __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
 903                 FILE *input, int nparam)
 904 {
 905         struct isl_map *map;
 906         struct isl_stream *s = isl_stream_new_file(ctx, input);
 907         if (!s)
 908                 return NULL;
 909         map = map_read(s, nparam);
 910         isl_stream_free(s);
 911         return map;
 912 }
 913
 914 __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
 915                 const char *str, int nparam)
 916 {
 917         struct isl_map *map;
 918         struct isl_stream *s = isl_stream_new_str(ctx, str);
 919         if (!s)
 920                 return NULL;
 921         map = map_read(s, nparam);
 922         isl_stream_free(s);
 923         return map;
 924 }
 925
 926 __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
 927                 FILE *input, int nparam)
 928 {
 929         struct isl_map *map;
 930         map = isl_map_read_from_file(ctx, input, nparam);
 931         if (!map)
 932                 return NULL;
 933         isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
 934         return (struct isl_set *)map;
 935 error:
 936         isl_map_free(map);
 937         return NULL;
 938 }
 939
 940 struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
 941                 const char *str, int nparam)
 942 {
 943         struct isl_map *map;
 944         map = isl_map_read_from_str(ctx, str, nparam);
 945         if (!map)
 946                 return NULL;
 947         isl_assert(ctx, isl_map_n_in(map) == 0, goto error);
 948         return (struct isl_set *)map;
 949 error:
 950         isl_map_free(map);
 951         return NULL;
 952 }
 953
 954 static char *next_line(FILE *input, char *line, unsigned len)
 955 {
 956         char *p;
 957
 958         do {
 959                 if (!(p = fgets(line, len, input)))
 960                         return NULL;
 961                 while (isspace(*p) && *p != '\n')
 962                         ++p;
 963         } while (*p == '#' || *p == '\n');
 964
 965         return p;
 966 }
 967
 968 static struct isl_vec *isl_vec_read_from_file_polylib(struct isl_ctx *ctx,
 969                 FILE *input)
 970 {
 971         struct isl_vec *vec = NULL;
 972         char line[1024];
 973         char val[1024];
 974         char *p;
 975         unsigned size;
 976         int j;
 977         int n;
 978         int offset;
 979
 980         isl_assert(ctx, next_line(input, line, sizeof(line)), return NULL);
 981         isl_assert(ctx, sscanf(line, "%u", &size) == 1, return NULL);
 982
 983         vec = isl_vec_alloc(ctx, size);
 984
 985         p = next_line(input, line, sizeof(line));
 986         isl_assert(ctx, p, goto error);
 987
 988         for (j = 0; j < size; ++j) {
 989                 n = sscanf(p, "%s%n", val, &offset);
 990                 isl_assert(ctx, n != 0, goto error);
 991                 isl_int_read(vec->el[j], val);
 992                 p += offset;
 993         }
 994
 995         return vec;
 996 error:
 997         isl_vec_free(vec);
 998         return NULL;
 999 }
1000
1001 struct isl_vec *isl_vec_read_from_file(struct isl_ctx *ctx,
1002                 FILE *input, unsigned input_format)
1003 {
1004         if (input_format == ISL_FORMAT_POLYLIB)
1005                 return isl_vec_read_from_file_polylib(ctx, input);
1006         else
1007                 isl_assert(ctx, 0, return NULL);
1008 }