isl_stream.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   7  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   8  */
   9
  10 #include <ctype.h>
  11 #include <string.h>
  12 #include <strings.h>
  13 #include <isl/ctx.h>
  14 #include <isl/stream.h>
  15
  16 struct isl_keyword {
  17         char                    *name;
  18         enum isl_token_type     type;
  19 };
  20
  21 static int same_name(const void *entry, const void *val)
  22 {
  23         const struct isl_keyword *keyword = (const struct isl_keyword *)entry;
  24
  25         return !strcmp(keyword->name, val);
  26 }
  27
  28 enum isl_token_type isl_stream_register_keyword(struct isl_stream *s,
  29         const char *name)
  30 {
  31         struct isl_hash_table_entry *entry;
  32         struct isl_keyword *keyword;
  33         uint32_t name_hash;
  34
  35         if (!s->keywords) {
  36                 s->keywords = isl_hash_table_alloc(s->ctx, 10);
  37                 if (!s->keywords)
  38                         return ISL_TOKEN_ERROR;
  39                 s->next_type = ISL_TOKEN_LAST;
  40         }
  41
  42         name_hash = isl_hash_string(isl_hash_init(), name);
  43
  44         entry = isl_hash_table_find(s->ctx, s->keywords, name_hash,
  45                                         same_name, name, 1);
  46         if (!entry)
  47                 return ISL_TOKEN_ERROR;
  48         if (entry->data) {
  49                 keyword = entry->data;
  50                 return keyword->type;
  51         }
  52
  53         keyword = isl_calloc_type(s->ctx, struct isl_keyword);
  54         if (!keyword)
  55                 return ISL_TOKEN_ERROR;
  56         keyword->type = s->next_type++;
  57         keyword->name = strdup(name);
  58         if (!keyword->name) {
  59                 free(keyword);
  60                 return ISL_TOKEN_ERROR;
  61         }
  62         entry->data = keyword;
  63
  64         return keyword->type;
  65 }
  66
  67 static struct isl_token *isl_token_new(struct isl_ctx *ctx,
  68         int line, int col, unsigned on_new_line)
  69 {
  70         struct isl_token *tok = isl_alloc_type(ctx, struct isl_token);
  71         if (!tok)
  72                 return NULL;
  73         tok->line = line;
  74         tok->col = col;
  75         tok->on_new_line = on_new_line;
  76         tok->is_keyword = 0;
  77         tok->u.s = NULL;
  78         return tok;
  79 }
  80
  81 void isl_token_free(struct isl_token *tok)
  82 {
  83         if (!tok)
  84                 return;
  85         if (tok->type == ISL_TOKEN_VALUE)
  86                 isl_int_clear(tok->u.v);
  87         else
  88                 free(tok->u.s);
  89         free(tok);
  90 }
  91
  92 void isl_stream_error(struct isl_stream *s, struct isl_token *tok, char *msg)
  93 {
  94         int line = tok ? tok->line : s->line;
  95         int col = tok ? tok->col : s->col;
  96         fprintf(stderr, "syntax error (%d, %d): %s\n", line, col, msg);
  97         if (tok) {
  98                 if (tok->type < 256)
  99                         fprintf(stderr, "got '%c'\n", tok->type);
 100                 else if (tok->type == ISL_TOKEN_IDENT)
 101                         fprintf(stderr, "got ident '%s'\n", tok->u.s);
 102                 else if (tok->is_keyword)
 103                         fprintf(stderr, "got keyword '%s'\n", tok->u.s);
 104                 else if (tok->type == ISL_TOKEN_VALUE) {
 105                         fprintf(stderr, "got value '");
 106                         isl_int_print(stderr, tok->u.v, 0);
 107                         fprintf(stderr, "'\n");
 108                 } else if (tok->u.s)
 109                         fprintf(stderr, "got token '%s'\n", tok->u.s);
 110                 else
 111                         fprintf(stderr, "got token type %d\n", tok->type);
 112         }
 113 }
 114
 115 static struct isl_stream* isl_stream_new(struct isl_ctx *ctx)
 116 {
 117         int i;
 118         struct isl_stream *s = isl_alloc_type(ctx, struct isl_stream);
 119         if (!s)
 120                 return NULL;
 121         s->ctx = ctx;
 122         isl_ctx_ref(s->ctx);
 123         s->file = NULL;
 124         s->str = NULL;
 125         s->len = 0;
 126         s->line = 1;
 127         s->col = 0;
 128         s->eof = 0;
 129         s->c = -1;
 130         s->n_un = 0;
 131         for (i = 0; i < 5; ++i)
 132                 s->tokens[i] = NULL;
 133         s->n_token = 0;
 134         s->keywords = NULL;
 135         s->size = 256;
 136         s->buffer = isl_alloc_array(ctx, char, s->size);
 137         if (!s->buffer)
 138                 goto error;
 139         return s;
 140 error:
 141         isl_stream_free(s);
 142         return NULL;
 143 }
 144
 145 struct isl_stream* isl_stream_new_file(struct isl_ctx *ctx, FILE *file)
 146 {
 147         struct isl_stream *s = isl_stream_new(ctx);
 148         if (!s)
 149                 return NULL;
 150         s->file = file;
 151         return s;
 152 }
 153
 154 struct isl_stream* isl_stream_new_str(struct isl_ctx *ctx, const char *str)
 155 {
 156         struct isl_stream *s = isl_stream_new(ctx);
 157         if (!s)
 158                 return NULL;
 159         s->str = str;
 160         return s;
 161 }
 162
 163 static int stream_getc(struct isl_stream *s)
 164 {
 165         int c;
 166         if (s->eof)
 167                 return -1;
 168         if (s->n_un)
 169                 return s->c = s->un[--s->n_un];
 170         if (s->file)
 171                 c = fgetc(s->file);
 172         else {
 173                 c = *s->str++;
 174                 if (c == '\0')
 175                         c = -1;
 176         }
 177         if (c == -1)
 178                 s->eof = 1;
 179         if (!s->eof) {
 180                 if (s->c == '\n') {
 181                         s->line++;
 182                         s->col = 0;
 183                 } else
 184                         s->col++;
 185         }
 186         s->c = c;
 187         return c;
 188 }
 189
 190 static void isl_stream_ungetc(struct isl_stream *s, int c)
 191 {
 192         isl_assert(s->ctx, s->n_un < 5, return);
 193         s->un[s->n_un++] = c;
 194         s->c = -1;
 195 }
 196
 197 static int isl_stream_getc(struct isl_stream *s)
 198 {
 199         int c;
 200
 201         do {
 202                 c = stream_getc(s);
 203                 if (c != '\\')
 204                         return c;
 205                 c = stream_getc(s);
 206         } while (c == '\n');
 207
 208         isl_stream_ungetc(s, c);
 209
 210         return '\\';
 211 }
 212
 213 static int isl_stream_push_char(struct isl_stream *s, int c)
 214 {
 215         if (s->len >= s->size) {
 216                 char *buffer;
 217                 s->size = (3*s->size)/2;
 218                 buffer = isl_realloc_array(s->ctx, s->buffer, char, s->size);
 219                 if (!buffer)
 220                         return -1;
 221                 s->buffer = buffer;
 222         }
 223         s->buffer[s->len++] = c;
 224         return 0;
 225 }
 226
 227 void isl_stream_push_token(struct isl_stream *s, struct isl_token *tok)
 228 {
 229         isl_assert(s->ctx, s->n_token < 5, return);
 230         s->tokens[s->n_token++] = tok;
 231 }
 232
 233 static enum isl_token_type check_keywords(struct isl_stream *s)
 234 {
 235         struct isl_hash_table_entry *entry;
 236         struct isl_keyword *keyword;
 237         uint32_t name_hash;
 238
 239         if (!strcasecmp(s->buffer, "exists"))
 240                 return ISL_TOKEN_EXISTS;
 241         if (!strcasecmp(s->buffer, "and"))
 242                 return ISL_TOKEN_AND;
 243         if (!strcasecmp(s->buffer, "or"))
 244                 return ISL_TOKEN_OR;
 245         if (!strcasecmp(s->buffer, "not"))
 246                 return ISL_TOKEN_NOT;
 247         if (!strcasecmp(s->buffer, "infty"))
 248                 return ISL_TOKEN_INFTY;
 249         if (!strcasecmp(s->buffer, "infinity"))
 250                 return ISL_TOKEN_INFTY;
 251         if (!strcasecmp(s->buffer, "NaN"))
 252                 return ISL_TOKEN_NAN;
 253         if (!strcasecmp(s->buffer, "min"))
 254                 return ISL_TOKEN_MIN;
 255         if (!strcasecmp(s->buffer, "max"))
 256                 return ISL_TOKEN_MAX;
 257         if (!strcasecmp(s->buffer, "rat"))
 258                 return ISL_TOKEN_RAT;
 259         if (!strcasecmp(s->buffer, "true"))
 260                 return ISL_TOKEN_TRUE;
 261         if (!strcasecmp(s->buffer, "false"))
 262                 return ISL_TOKEN_FALSE;
 263         if (!strcasecmp(s->buffer, "ceild"))
 264                 return ISL_TOKEN_CEILD;
 265         if (!strcasecmp(s->buffer, "floord"))
 266                 return ISL_TOKEN_FLOORD;
 267         if (!strcasecmp(s->buffer, "mod"))
 268                 return ISL_TOKEN_MOD;
 269
 270         if (!s->keywords)
 271                 return ISL_TOKEN_IDENT;
 272
 273         name_hash = isl_hash_string(isl_hash_init(), s->buffer);
 274         entry = isl_hash_table_find(s->ctx, s->keywords, name_hash, same_name,
 275                                         s->buffer, 0);
 276         if (entry) {
 277                 keyword = entry->data;
 278                 return keyword->type;
 279         }
 280
 281         return ISL_TOKEN_IDENT;
 282 }
 283
 284 int isl_stream_skip_line(struct isl_stream *s)
 285 {
 286         int c;
 287
 288         while ((c = isl_stream_getc(s)) != -1 && c != '\n')
 289                 /* nothing */
 290                 ;
 291
 292         return c == -1 ? -1 : 0;
 293 }
 294
 295 static struct isl_token *next_token(struct isl_stream *s, int same_line)
 296 {
 297         int c;
 298         struct isl_token *tok = NULL;
 299         int line, col;
 300         int old_line = s->line;
 301
 302         if (s->n_token) {
 303                 if (same_line && s->tokens[s->n_token - 1]->on_new_line)
 304                         return NULL;
 305                 return s->tokens[--s->n_token];
 306         }
 307
 308         if (same_line && s->c == '\n')
 309                 return NULL;
 310
 311         s->len = 0;
 312
 313         /* skip spaces and comment lines */
 314         while ((c = isl_stream_getc(s)) != -1) {
 315                 if (c == '#') {
 316                         if (isl_stream_skip_line(s) < 0)
 317                                 break;
 318                         c = '\n';
 319                         if (same_line)
 320                                 break;
 321                 } else if (!isspace(c) || (same_line && c == '\n'))
 322                         break;
 323         }
 324
 325         line = s->line;
 326         col = s->col;
 327
 328         if (c == -1 || (same_line && c == '\n'))
 329                 return NULL;
 330         if (c == '(' ||
 331             c == ')' ||
 332             c == '+' ||
 333             c == '*' ||
 334             c == '%' ||
 335             c == '^' ||
 336             c == '=' ||
 337             c == '@' ||
 338             c == '$' ||
 339             c == ',' ||
 340             c == '.' ||
 341             c == ';' ||
 342             c == '[' ||
 343             c == ']' ||
 344             c == '{' ||
 345             c == '}') {
 346                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 347                 if (!tok)
 348                         return NULL;
 349                 tok->type = (enum isl_token_type)c;
 350                 return tok;
 351         }
 352         if (c == '-') {
 353                 int c;
 354                 if ((c = isl_stream_getc(s)) == '>') {
 355                         tok = isl_token_new(s->ctx, line, col, old_line != line);
 356                         if (!tok)
 357                                 return NULL;
 358                         tok->u.s = strdup("->");
 359                         tok->type = ISL_TOKEN_TO;
 360                         return tok;
 361                 }
 362                 if (c != -1)
 363                         isl_stream_ungetc(s, c);
 364                 if (!isdigit(c)) {
 365                         tok = isl_token_new(s->ctx, line, col, old_line != line);
 366                         if (!tok)
 367                                 return NULL;
 368                         tok->type = (enum isl_token_type) '-';
 369                         return tok;
 370                 }
 371         }
 372         if (c == '-' || isdigit(c)) {
 373                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 374                 if (!tok)
 375                         return NULL;
 376                 tok->type = ISL_TOKEN_VALUE;
 377                 isl_int_init(tok->u.v);
 378                 if (isl_stream_push_char(s, c))
 379                         goto error;
 380                 while ((c = isl_stream_getc(s)) != -1 && isdigit(c))
 381                         if (isl_stream_push_char(s, c))
 382                                 goto error;
 383                 if (c != -1)
 384                         isl_stream_ungetc(s, c);
 385                 isl_stream_push_char(s, '\0');
 386                 isl_int_read(tok->u.v, s->buffer);
 387                 return tok;
 388         }
 389         if (isalpha(c) || c == '_') {
 390                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 391                 if (!tok)
 392                         return NULL;
 393                 isl_stream_push_char(s, c);
 394                 while ((c = isl_stream_getc(s)) != -1 &&
 395                                 (isalnum(c) || c == '_'))
 396                         isl_stream_push_char(s, c);
 397                 if (c != -1)
 398                         isl_stream_ungetc(s, c);
 399                 while ((c = isl_stream_getc(s)) != -1 && c == '\'')
 400                         isl_stream_push_char(s, c);
 401                 if (c != -1)
 402                         isl_stream_ungetc(s, c);
 403                 isl_stream_push_char(s, '\0');
 404                 tok->type = check_keywords(s);
 405                 if (tok->type != ISL_TOKEN_IDENT)
 406                         tok->is_keyword = 1;
 407                 tok->u.s = strdup(s->buffer);
 408                 if (!tok->u.s)
 409                         goto error;
 410                 return tok;
 411         }
 412         if (c == '"') {
 413                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 414                 if (!tok)
 415                         return NULL;
 416                 tok->type = ISL_TOKEN_STRING;
 417                 tok->u.s = NULL;
 418                 while ((c = isl_stream_getc(s)) != -1 && c != '"' && c != '\n')
 419                         isl_stream_push_char(s, c);
 420                 if (c != '"') {
 421                         isl_stream_error(s, NULL, "unterminated string");
 422                         goto error;
 423                 }
 424                 isl_stream_push_char(s, '\0');
 425                 tok->u.s = strdup(s->buffer);
 426                 return tok;
 427         }
 428         if (c == ':') {
 429                 int c;
 430                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 431                 if (!tok)
 432                         return NULL;
 433                 if ((c = isl_stream_getc(s)) == '=') {
 434                         tok->u.s = strdup(":=");
 435                         tok->type = ISL_TOKEN_DEF;
 436                         return tok;
 437                 }
 438                 if (c != -1)
 439                         isl_stream_ungetc(s, c);
 440                 tok->type = (enum isl_token_type) ':';
 441                 return tok;
 442         }
 443         if (c == '>') {
 444                 int c;
 445                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 446                 if (!tok)
 447                         return NULL;
 448                 if ((c = isl_stream_getc(s)) == '=') {
 449                         tok->u.s = strdup(">=");
 450                         tok->type = ISL_TOKEN_GE;
 451                         return tok;
 452                 } else if (c == '>') {
 453                         if ((c = isl_stream_getc(s)) == '=') {
 454                                 tok->u.s = strdup(">>=");
 455                                 tok->type = ISL_TOKEN_LEX_GE;
 456                                 return tok;
 457                         }
 458                         tok->u.s = strdup(">>");
 459                         tok->type = ISL_TOKEN_LEX_GT;
 460                 } else {
 461                         tok->u.s = strdup(">");
 462                         tok->type = ISL_TOKEN_GT;
 463                 }
 464                 if (c != -1)
 465                         isl_stream_ungetc(s, c);
 466                 return tok;
 467         }
 468         if (c == '<') {
 469                 int c;
 470                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 471                 if (!tok)
 472                         return NULL;
 473                 if ((c = isl_stream_getc(s)) == '=') {
 474                         tok->u.s = strdup("<=");
 475                         tok->type = ISL_TOKEN_LE;
 476                         return tok;
 477                 } else if (c == '<') {
 478                         if ((c = isl_stream_getc(s)) == '=') {
 479                                 tok->u.s = strdup("<<=");
 480                                 tok->type = ISL_TOKEN_LEX_LE;
 481                                 return tok;
 482                         }
 483                         tok->u.s = strdup("<<");
 484                         tok->type = ISL_TOKEN_LEX_LT;
 485                 } else {
 486                         tok->u.s = strdup("<");
 487                         tok->type = ISL_TOKEN_LT;
 488                 }
 489                 if (c != -1)
 490                         isl_stream_ungetc(s, c);
 491                 return tok;
 492         }
 493         if (c == '&') {
 494                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 495                 if (!tok)
 496                         return NULL;
 497                 tok->type = ISL_TOKEN_AND;
 498                 if ((c = isl_stream_getc(s)) != '&' && c != -1) {
 499                         tok->u.s = strdup("&");
 500                         isl_stream_ungetc(s, c);
 501                 } else
 502                         tok->u.s = strdup("&&");
 503                 return tok;
 504         }
 505         if (c == '|') {
 506                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 507                 if (!tok)
 508                         return NULL;
 509                 tok->type = ISL_TOKEN_OR;
 510                 if ((c = isl_stream_getc(s)) != '|' && c != -1) {
 511                         tok->u.s = strdup("|");
 512                         isl_stream_ungetc(s, c);
 513                 } else
 514                         tok->u.s = strdup("||");
 515                 return tok;
 516         }
 517         if (c == '/') {
 518                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 519                 if (!tok)
 520                         return NULL;
 521                 if ((c = isl_stream_getc(s)) != '\\' && c != -1) {
 522                         tok->type = (enum isl_token_type) '/';
 523                         isl_stream_ungetc(s, c);
 524                 } else {
 525                         tok->u.s = strdup("/\\");
 526                         tok->type = ISL_TOKEN_AND;
 527                 }
 528                 return tok;
 529         }
 530         if (c == '\\') {
 531                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 532                 if (!tok)
 533                         return NULL;
 534                 if ((c = isl_stream_getc(s)) != '/' && c != -1) {
 535                         tok->type = (enum isl_token_type) '\\';
 536                         isl_stream_ungetc(s, c);
 537                 } else {
 538                         tok->u.s = strdup("\\/");
 539                         tok->type = ISL_TOKEN_OR;
 540                 }
 541                 return tok;
 542         }
 543         if (c == '!') {
 544                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 545                 if (!tok)
 546                         return NULL;
 547                 tok->type = ISL_TOKEN_NOT;
 548                 tok->u.s = strdup("!");
 549                 return tok;
 550         }
 551
 552         tok = isl_token_new(s->ctx, line, col, old_line != line);
 553         if (!tok)
 554                 return NULL;
 555         tok->type = ISL_TOKEN_UNKNOWN;
 556         return tok;
 557 error:
 558         isl_token_free(tok);
 559         return NULL;
 560 }
 561
 562 struct isl_token *isl_stream_next_token(struct isl_stream *s)
 563 {
 564         return next_token(s, 0);
 565 }
 566
 567 struct isl_token *isl_stream_next_token_on_same_line(struct isl_stream *s)
 568 {
 569         return next_token(s, 1);
 570 }
 571
 572 int isl_stream_eat_if_available(struct isl_stream *s, int type)
 573 {
 574         struct isl_token *tok;
 575
 576         tok = isl_stream_next_token(s);
 577         if (!tok)
 578                 return 0;
 579         if (tok->type == type) {
 580                 isl_token_free(tok);
 581                 return 1;
 582         }
 583         isl_stream_push_token(s, tok);
 584         return 0;
 585 }
 586
 587 int isl_stream_next_token_is(struct isl_stream *s, int type)
 588 {
 589         struct isl_token *tok;
 590         int r;
 591
 592         tok = isl_stream_next_token(s);
 593         if (!tok)
 594                 return 0;
 595         r = tok->type == type;
 596         isl_stream_push_token(s, tok);
 597         return r;
 598 }
 599
 600 char *isl_stream_read_ident_if_available(struct isl_stream *s)
 601 {
 602         struct isl_token *tok;
 603
 604         tok = isl_stream_next_token(s);
 605         if (!tok)
 606                 return NULL;
 607         if (tok->type == ISL_TOKEN_IDENT) {
 608                 char *ident = strdup(tok->u.s);
 609                 isl_token_free(tok);
 610                 return ident;
 611         }
 612         isl_stream_push_token(s, tok);
 613         return NULL;
 614 }
 615
 616 int isl_stream_eat(struct isl_stream *s, int type)
 617 {
 618         struct isl_token *tok;
 619
 620         tok = isl_stream_next_token(s);
 621         if (!tok)
 622                 return -1;
 623         if (tok->type == type) {
 624                 isl_token_free(tok);
 625                 return 0;
 626         }
 627         isl_stream_error(s, tok, "expecting other token");
 628         isl_stream_push_token(s, tok);
 629         return -1;
 630 }
 631
 632 int isl_stream_is_empty(struct isl_stream *s)
 633 {
 634         struct isl_token *tok;
 635
 636         tok = isl_stream_next_token(s);
 637
 638         if (!tok)
 639                 return 1;
 640
 641         isl_stream_push_token(s, tok);
 642         return 0;
 643 }
 644
 645 static int free_keyword(void **p, void *user)
 646 {
 647         struct isl_keyword *keyword = *p;
 648
 649         free(keyword->name);
 650         free(keyword);
 651
 652         return 0;
 653 }
 654
 655 void isl_stream_flush_tokens(struct isl_stream *s)
 656 {
 657         int i;
 658
 659         if (!s)
 660                 return;
 661         for (i = 0; i < s->n_token; ++i)
 662                 isl_token_free(s->tokens[i]);
 663         s->n_token = 0;
 664 }
 665
 666 void isl_stream_free(struct isl_stream *s)
 667 {
 668         if (!s)
 669                 return;
 670         free(s->buffer);
 671         if (s->n_token != 0) {
 672                 struct isl_token *tok = isl_stream_next_token(s);
 673                 isl_stream_error(s, tok, "unexpected token");
 674                 isl_token_free(tok);
 675         }
 676         if (s->keywords) {
 677                 isl_hash_table_foreach(s->ctx, s->keywords, &free_keyword, NULL);
 678                 isl_hash_table_free(s->ctx, s->keywords);
 679         }
 680         isl_ctx_deref(s->ctx);
 681         free(s);
 682 }