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