isl_input_omega.c

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