isl_input_omega.c

   1 #include <ctype.h>
   2 #include <string.h>
   3 #include <strings.h>
   4 #include "isl_map_private.h"
   5 #include "isl_input_omega.h"
   6
   7 enum token_type { TOKEN_UNKNOWN = 256, TOKEN_VALUE, TOKEN_IDENT, TOKEN_GE,
   8                   TOKEN_LE, TOKEN_TO, TOKEN_AND, TOKEN_EXISTS };
   9
  10 struct token {
  11         enum token_type  type;
  12
  13         unsigned int on_new_line : 1;
  14         int line;
  15         int col;
  16
  17         union {
  18                 isl_int v;
  19                 char    *s;
  20         } u;
  21 };
  22
  23 static struct token *token_new(struct isl_ctx *ctx,
  24         int line, int col, unsigned on_new_line)
  25 {
  26         struct token *tok = isl_alloc_type(ctx, struct token);
  27         if (!tok)
  28                 return NULL;
  29         tok->line = line;
  30         tok->col = col;
  31         tok->on_new_line = on_new_line;
  32         return tok;
  33 }
  34
  35 void token_free(struct token *tok)
  36 {
  37         if (!tok)
  38                 return;
  39         if (tok->type == TOKEN_VALUE)
  40                 isl_int_clear(tok->u.v);
  41         else if (tok->type == TOKEN_IDENT)
  42                 free(tok->u.s);
  43         free(tok);
  44 }
  45
  46 struct stream {
  47         struct isl_ctx  *ctx;
  48         FILE            *file;
  49         const char      *str;
  50         int             line;
  51         int             col;
  52         int             eof;
  53
  54         char            *buffer;
  55         size_t          size;
  56         size_t          len;
  57         int             c;
  58
  59         struct token    *tokens[5];
  60         int             n_token;
  61 };
  62
  63 void stream_error(struct stream *s, struct token *tok, char *msg)
  64 {
  65         int line = tok ? tok->line : s->line;
  66         int col = tok ? tok->col : s->col;
  67         fprintf(stderr, "syntax error (%d, %d): %s\n", line, col, msg);
  68         if (tok) {
  69                 if (tok->type < 256)
  70                         fprintf(stderr, "got '%c'\n", tok->type);
  71                 else
  72                         fprintf(stderr, "got token type %d\n", tok->type);
  73         }
  74 }
  75
  76 static void stream_free(struct stream *s);
  77
  78 static struct stream* stream_new(struct isl_ctx *ctx)
  79 {
  80         int i;
  81         struct stream *s = isl_alloc_type(ctx, struct stream);
  82         if (!s)
  83                 return NULL;
  84         s->ctx = ctx;
  85         s->size = 256;
  86         s->file = NULL;
  87         s->str = NULL;
  88         s->buffer = isl_alloc_array(ctx, char, s->size);
  89         if (!s->buffer)
  90                 goto error;
  91         s->len = 0;
  92         s->line = 1;
  93         s->col = 0;
  94         s->eof = 0;
  95         s->c = -1;
  96         for (i = 0; i < 5; ++i)
  97                 s->tokens[i] = NULL;
  98         s->n_token = 0;
  99         return s;
 100 error:
 101         stream_free(s);
 102         return NULL;
 103 }
 104
 105 static struct stream* stream_new_file(struct isl_ctx *ctx, FILE *file)
 106 {
 107         struct stream *s = stream_new(ctx);
 108         if (!s)
 109                 return NULL;
 110         s->file = file;
 111         return s;
 112 }
 113
 114 static int stream_getc(struct stream *s)
 115 {
 116         int c;
 117         if (s->eof)
 118                 return -1;
 119         if (s->file)
 120                 c = fgetc(s->file);
 121         else {
 122                 c = *s->str++;
 123                 if (c == '\0')
 124                         c = -1;
 125         }
 126         if (c == -1)
 127                 s->eof = 1;
 128         if (!s->eof) {
 129                 if (s->c == '\n') {
 130                         s->line++;
 131                         s->col = 0;
 132                 } else
 133                         s->col++;
 134         }
 135         s->c = c;
 136         return c;
 137 }
 138
 139 static void stream_ungetc(struct stream *s, int c)
 140 {
 141         if (s->file)
 142                 ungetc(c, s->file);
 143         else
 144                 --s->str;
 145         s->c = -1;
 146 }
 147
 148 static int stream_push_char(struct stream *s, int c)
 149 {
 150         if (s->len >= s->size) {
 151                 s->size = (3*s->size)/2;
 152                 s->buffer = isl_realloc_array(ctx, s->buffer, char, s->size);
 153                 if (!s->buffer)
 154                         return -1;
 155         }
 156         s->buffer[s->len++] = c;
 157         return 0;
 158 }
 159
 160 static void stream_push_token(struct stream *s, struct token *tok)
 161 {
 162         isl_assert(s->ctx, s->n_token < 5, return);
 163         s->tokens[s->n_token++] = tok;
 164 }
 165
 166 static struct token *stream_next_token(struct stream *s)
 167 {
 168         int c;
 169         struct token *tok = NULL;
 170         int line, col;
 171         int old_line = s->line;
 172
 173         if (s->n_token)
 174                 return s->tokens[--s->n_token];
 175
 176         s->len = 0;
 177
 178         /* skip spaces */
 179         while ((c = stream_getc(s)) != -1 && isspace(c))
 180                 /* nothing */
 181                 ;
 182
 183         line = s->line;
 184         col = s->col;
 185
 186         if (c == -1)
 187                 return NULL;
 188         if (c == '(' ||
 189             c == ')' ||
 190             c == '+' ||
 191             c == '/' ||
 192             c == '*' ||
 193             c == '^' ||
 194             c == '=' ||
 195             c == ',' ||
 196             c == ':' ||
 197             c == '[' ||
 198             c == ']' ||
 199             c == '{' ||
 200             c == '}') {
 201                 tok = token_new(s->ctx, line, col, old_line != line);
 202                 if (!tok)
 203                         return NULL;
 204                 tok->type = (enum token_type)c;
 205                 return tok;
 206         }
 207         if (c == '-') {
 208                 int c;
 209                 if ((c = stream_getc(s)) == '>') {
 210                         tok = token_new(s->ctx, line, col, old_line != line);
 211                         if (!tok)
 212                                 return NULL;
 213                         tok->type = TOKEN_TO;
 214                         return tok;
 215                 }
 216                 if (c != -1)
 217                         stream_ungetc(s, c);
 218         }
 219         if (c == '-' || isdigit(c)) {
 220                 tok = token_new(s->ctx, line, col, old_line != line);
 221                 if (!tok)
 222                         return NULL;
 223                 tok->type = TOKEN_VALUE;
 224                 isl_int_init(tok->u.v);
 225                 if (stream_push_char(s, c))
 226                         goto error;
 227                 while ((c = stream_getc(s)) != -1 && isdigit(c))
 228                         if (stream_push_char(s, c))
 229                                 goto error;
 230                 if (c != -1)
 231                         stream_ungetc(s, c);
 232                 if (s->len == 1 && s->buffer[0] == '-')
 233                         isl_int_set_si(tok->u.v, -1);
 234                 else {
 235                         stream_push_char(s, '\0');
 236                         isl_int_read(tok->u.v, s->buffer);
 237                 }
 238                 return tok;
 239         }
 240         if (isalpha(c)) {
 241                 tok = token_new(s->ctx, line, col, old_line != line);
 242                 if (!tok)
 243                         return NULL;
 244                 stream_push_char(s, c);
 245                 while ((c = stream_getc(s)) != -1 && isalnum(c))
 246                         stream_push_char(s, c);
 247                 if (c != -1)
 248                         stream_ungetc(s, c);
 249                 stream_push_char(s, '\0');
 250                 if (!strcasecmp(s->buffer, "exists"))
 251                         tok->type = TOKEN_EXISTS;
 252                 else {
 253                         tok->type = TOKEN_IDENT;
 254                         tok->u.s = strdup(s->buffer);
 255                 }
 256                 return tok;
 257         }
 258         if (c == '>') {
 259                 int c;
 260                 if ((c = stream_getc(s)) == '=') {
 261                         tok = token_new(s->ctx, line, col, old_line != line);
 262                         if (!tok)
 263                                 return NULL;
 264                         tok->type = TOKEN_GE;
 265                         return tok;
 266                 }
 267                 if (c != -1)
 268                         stream_ungetc(s, c);
 269         }
 270         if (c == '<') {
 271                 int c;
 272                 if ((c = stream_getc(s)) == '=') {
 273                         tok = token_new(s->ctx, line, col, old_line != line);
 274                         if (!tok)
 275                                 return NULL;
 276                         tok->type = TOKEN_LE;
 277                         return tok;
 278                 }
 279                 if (c != -1)
 280                         stream_ungetc(s, c);
 281         }
 282         if (c == '&') {
 283                 tok = token_new(s->ctx, line, col, old_line != line);
 284                 if (!tok)
 285                         return NULL;
 286                 tok->type = TOKEN_AND;
 287                 if ((c = stream_getc(s)) != '&' && c != -1)
 288                         stream_ungetc(s, c);
 289                 return tok;
 290         }
 291
 292         tok = token_new(s->ctx, line, col, old_line != line);
 293         if (!tok)
 294                 return NULL;
 295         tok->type = TOKEN_UNKNOWN;
 296         return tok;
 297 error:
 298         token_free(tok);
 299         return NULL;
 300 }
 301
 302 static int stream_eat(struct stream *s, int type)
 303 {
 304         struct token *tok;
 305
 306         tok = stream_next_token(s);
 307         if (!tok)
 308                 return -1;
 309         if (tok->type == type) {
 310                 token_free(tok);
 311                 return 0;
 312         }
 313         stream_error(s, tok, "expecting other token");
 314         stream_push_token(s, tok);
 315         return -1;
 316 }
 317
 318 static void stream_free(struct stream *s)
 319 {
 320         if (!s)
 321                 return;
 322         free(s->buffer);
 323         if (s->n_token != 0) {
 324                 struct token *tok = stream_next_token(s);
 325                 stream_error(s, tok, "unexpected token");
 326                 token_free(tok);
 327         }
 328         free(s);
 329 }
 330
 331 struct variable {
 332         char                    *name;
 333         int                      pos;
 334         struct variable         *next;
 335 };
 336
 337 struct vars {
 338         struct isl_ctx  *ctx;
 339         int              n;
 340         struct variable *v;
 341 };
 342
 343 static struct vars *vars_new(struct isl_ctx *ctx)
 344 {
 345         struct vars *v;
 346         v = isl_alloc_type(ctx, struct vars);
 347         if (!v)
 348                 return NULL;
 349         v->ctx = ctx;
 350         v->n = 0;
 351         v->v = NULL;
 352         return v;
 353 }
 354
 355 void variable_free(struct variable *var)
 356 {
 357         while (var) {
 358                 struct variable *next = var->next;
 359                 free(var->name);
 360                 free(var);
 361                 var = next;
 362         }
 363 }
 364
 365 static void vars_free(struct vars *v)
 366 {
 367         if (!v)
 368                 return;
 369         variable_free(v->v);
 370         free(v);
 371 }
 372
 373 struct variable *variable_new(struct vars *v, const char *name, int len,
 374                                 int pos)
 375 {
 376         struct variable *var;
 377         var = isl_alloc_type(v->ctx, struct variable);
 378         if (!var)
 379                 goto error;
 380         var->name = strdup(name);
 381         var->name[len] = '\0';
 382         var->pos = pos;
 383         var->next = v->v;
 384         return var;
 385 error:
 386         variable_free(v->v);
 387         return NULL;
 388 }
 389
 390 static int vars_pos(struct vars *v, const char *s, int len)
 391 {
 392         int pos;
 393         struct variable *q;
 394
 395         if (len == -1)
 396                 len = strlen(s);
 397         for (q = v->v; q; q = q->next) {
 398                 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
 399                         break;
 400         }
 401         if (q)
 402                 pos = q->pos;
 403         else {
 404                 pos = v->n;
 405                 v->v = variable_new(v, s, len, v->n);
 406                 if (!v)
 407                         return -1;
 408                 v->n++;
 409         }
 410         return pos;
 411 }
 412
 413 static struct vars *read_var_list(struct stream *s, struct vars *v)
 414 {
 415         struct token *tok;
 416
 417         while ((tok = stream_next_token(s)) != NULL) {
 418                 int p;
 419                 int n = v->n;
 420
 421                 if (tok->type != TOKEN_IDENT)
 422                         break;
 423
 424                 p = vars_pos(v, tok->u.s, -1);
 425                 if (p < 0)
 426                         goto error;
 427                 if (p < n) {
 428                         stream_error(s, tok, "expecting unique identifier");
 429                         goto error;
 430                 }
 431                 token_free(tok);
 432                 tok = stream_next_token(s);
 433                 if (!tok || tok->type != ',')
 434                         break;
 435
 436                 token_free(tok);
 437         }
 438         if (tok)
 439                 stream_push_token(s, tok);
 440
 441         return v;
 442 error:
 443         token_free(tok);
 444         vars_free(v);
 445         return NULL;
 446 }
 447
 448 static struct vars *read_tuple(struct stream *s, struct vars *v)
 449 {
 450         struct token *tok;
 451
 452         tok = stream_next_token(s);
 453         if (!tok || tok->type != '[') {
 454                 stream_error(s, tok, "expecting '['");
 455                 goto error;
 456         }
 457         token_free(tok);
 458         v = read_var_list(s, v);
 459         tok = stream_next_token(s);
 460         if (!tok || tok->type != ']') {
 461                 stream_error(s, tok, "expecting ']'");
 462                 goto error;
 463         }
 464         token_free(tok);
 465
 466         return v;
 467 error:
 468         if (tok)
 469                 token_free(tok);
 470         vars_free(v);
 471         return NULL;
 472 }
 473
 474 static struct isl_basic_map *add_constraints(struct stream *s,
 475         struct vars **v, struct isl_basic_map *bmap);
 476
 477 static struct isl_basic_map *add_exists(struct stream *s,
 478         struct vars **v, struct isl_basic_map *bmap)
 479 {
 480         struct token *tok;
 481         int n = (*v)->n;
 482         int extra;
 483         int seen_paren = 0;
 484         int i;
 485         unsigned total;
 486
 487         tok = stream_next_token(s);
 488         if (!tok)
 489                 goto error;
 490         if (tok->type == '(') {
 491                 seen_paren = 1;
 492                 token_free(tok);
 493         } else
 494                 stream_push_token(s, tok);
 495         *v = read_var_list(s, *v);
 496         if (!*v)
 497                 goto error;
 498         extra = (*v)->n - n;
 499         bmap = isl_basic_map_extend(bmap, bmap->nparam,
 500                         bmap->n_in, bmap->n_out, extra, 0, 0);
 501         total = bmap->nparam+bmap->n_in+bmap->n_out+bmap->extra;
 502         for (i = 0; i < extra; ++i) {
 503                 int k;
 504                 if ((k = isl_basic_map_alloc_div(bmap)) < 0)
 505                         goto error;
 506                 isl_seq_clr(bmap->div[k], 1+1+total);
 507         }
 508         if (!bmap)
 509                 return NULL;
 510         if (stream_eat(s, ':'))
 511                 goto error;
 512         bmap = add_constraints(s, v, bmap);
 513         if (seen_paren && stream_eat(s, ')'))
 514                 goto error;
 515         return bmap;
 516 error:
 517         isl_basic_map_free(bmap);
 518         return NULL;
 519 }
 520
 521 static struct isl_basic_map *add_constraint(struct stream *s,
 522         struct vars **v, struct isl_basic_map *bmap)
 523 {
 524         unsigned total = bmap->nparam+bmap->n_in+bmap->n_out+bmap->extra;
 525         int k;
 526         int sign = 1;
 527         int equality = 0;
 528         int op = 0;
 529         struct token *tok = NULL;
 530
 531         tok = stream_next_token(s);
 532         if (!tok)
 533                 goto error;
 534         if (tok->type == TOKEN_EXISTS) {
 535                 token_free(tok);
 536                 return add_exists(s, v, bmap);
 537         }
 538         stream_push_token(s, tok);
 539
 540         bmap = isl_basic_map_extend(bmap, bmap->nparam,
 541                         bmap->n_in, bmap->n_out, 0, 0, 1);
 542         k = isl_basic_map_alloc_inequality(bmap);
 543         if (k < 0)
 544                 goto error;
 545         isl_seq_clr(bmap->ineq[k], 1+total);
 546
 547         for (;;) {
 548                 tok = stream_next_token(s);
 549                 if (!tok) {
 550                         stream_error(s, NULL, "unexpected EOF");
 551                         goto error;
 552                 }
 553                 if (tok->type == TOKEN_IDENT) {
 554                         int n = (*v)->n;
 555                         int pos = vars_pos(*v, tok->u.s, -1);
 556                         if (pos < 0)
 557                                 goto error;
 558                         if (pos >= n) {
 559                                 stream_error(s, tok, "unknown identifier");
 560                                 goto error;
 561                         }
 562                         if (sign > 0)
 563                                 isl_int_add_ui(bmap->ineq[k][1+pos],
 564                                                 bmap->ineq[k][1+pos], 1);
 565                         else
 566                                 isl_int_sub_ui(bmap->ineq[k][1+pos],
 567                                                 bmap->ineq[k][1+pos], 1);
 568                 } else if (tok->type == TOKEN_VALUE) {
 569                         struct token *tok2;
 570                         int n = (*v)->n;
 571                         int pos = -1;
 572                         tok2 = stream_next_token(s);
 573                         if (tok2 && tok2->type == TOKEN_IDENT) {
 574                                 pos = vars_pos(*v, tok2->u.s, -1);
 575                                 if (pos < 0)
 576                                         goto error;
 577                                 if (pos >= n) {
 578                                         stream_error(s, tok2,
 579                                                 "unknown identifier");
 580                                         token_free(tok2);
 581                                         goto error;
 582                                 }
 583                                 token_free(tok2);
 584                         } else if (tok2)
 585                                 stream_push_token(s, tok2);
 586                         if (sign < 0)
 587                                 isl_int_neg(tok->u.v, tok->u.v);
 588                         isl_int_add(bmap->ineq[k][1+pos],
 589                                         bmap->ineq[k][1+pos], tok->u.v);
 590                 } else if (tok->type == TOKEN_LE) {
 591                         op = 1;
 592                         isl_seq_neg(bmap->ineq[k], bmap->ineq[k], 1+total);
 593                 } else if (tok->type == TOKEN_GE) {
 594                         op = 1;
 595                         sign = -1;
 596                 } else if (tok->type == '=') {
 597                         if (op) {
 598                                 stream_error(s, tok, "too many operators");
 599                                 goto error;
 600                         }
 601                         op = 1;
 602                         equality = 1;
 603                         sign = -1;
 604                 } else {
 605                         stream_push_token(s, tok);
 606                         break;
 607                 }
 608                 token_free(tok);
 609         }
 610         tok = NULL;
 611         if (!op) {
 612                 stream_error(s, tok, "missing operator");
 613                 goto error;
 614         }
 615         if (equality)
 616                 isl_basic_map_inequality_to_equality(bmap, k);
 617         return bmap;
 618 error:
 619         if (tok)
 620                 token_free(tok);
 621         isl_basic_map_free(bmap);
 622         return NULL;
 623 }
 624
 625 static struct isl_basic_map *add_constraints(struct stream *s,
 626         struct vars **v, struct isl_basic_map *bmap)
 627 {
 628         struct token *tok;
 629
 630         for (;;) {
 631                 bmap = add_constraint(s, v, bmap);
 632                 if (!bmap)
 633                         return NULL;
 634                 tok = stream_next_token(s);
 635                 if (!tok) {
 636                         stream_error(s, NULL, "unexpected EOF");
 637                         goto error;
 638                 }
 639                 if (tok->type != TOKEN_AND)
 640                         break;
 641                 token_free(tok);
 642         }
 643         stream_push_token(s, tok);
 644
 645         return bmap;
 646 error:
 647         if (tok)
 648                 token_free(tok);
 649         isl_basic_map_free(bmap);
 650         return NULL;
 651 }
 652
 653 static struct isl_basic_map *basic_map_read(struct stream *s)
 654 {
 655         struct isl_basic_map *bmap = NULL;
 656         struct token *tok;
 657         struct vars *v = NULL;
 658         int n1;
 659         int n2;
 660
 661         tok = stream_next_token(s);
 662         if (!tok || tok->type != '{') {
 663                 stream_error(s, tok, "expecting '{'");
 664                 if (tok)
 665                         stream_push_token(s, tok);
 666                 goto error;
 667         }
 668         token_free(tok);
 669         v = vars_new(s->ctx);
 670         v = read_tuple(s, v);
 671         if (!v)
 672                 return NULL;
 673         n1 = v->n;
 674         tok = stream_next_token(s);
 675         if (tok && tok->type == TOKEN_TO) {
 676                 token_free(tok);
 677                 v = read_tuple(s, v);
 678                 if (!v)
 679                         return NULL;
 680                 n2 = v->n - n1;
 681         } else {
 682                 if (tok)
 683                         stream_push_token(s, tok);
 684                 n2 = n1;
 685                 n1 = 0;
 686         }
 687         bmap = isl_basic_map_alloc(s->ctx, 0, n1, n2, 0, 0,0);
 688         if (!bmap)
 689                 goto error;
 690         tok = stream_next_token(s);
 691         if (tok && tok->type == ':') {
 692                 token_free(tok);
 693                 bmap = add_constraints(s, &v, bmap);
 694                 tok = stream_next_token(s);
 695         }
 696         if (tok && tok->type == '}') {
 697                 token_free(tok);
 698         } else {
 699                 stream_error(s, tok, "unexpected token");
 700                 if (tok)
 701                         token_free(tok);
 702                 goto error;
 703         }
 704         vars_free(v);
 705
 706         return bmap;
 707 error:
 708         isl_basic_map_free(bmap);
 709         if (v)
 710                 vars_free(v);
 711         return NULL;
 712 }
 713
 714 struct isl_basic_map *isl_basic_map_read_from_file_omega(
 715                 struct isl_ctx *ctx, FILE *input)
 716 {
 717         struct isl_basic_map *bmap;
 718         struct stream *s = stream_new_file(ctx, input);
 719         if (!s)
 720                 return NULL;
 721         bmap = basic_map_read(s);
 722         stream_free(s);
 723         return bmap;
 724 }
 725
 726 struct isl_basic_set *isl_basic_set_read_from_file_omega(
 727                 struct isl_ctx *ctx, FILE *input)
 728 {
 729         struct isl_basic_map *bmap;
 730         bmap = isl_basic_map_read_from_file_omega(ctx, input);
 731         if (!bmap)
 732                 return NULL;
 733         isl_assert(ctx, bmap->n_in == 0, goto error);
 734         return (struct isl_basic_set *)bmap;
 735 error:
 736         isl_basic_map_free(bmap);
 737         return NULL;
 738 }