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         for (i = 0; i < 5; ++i)
 131                 s->tokens[i] = NULL;
 132         s->n_token = 0;
 133         s->keywords = NULL;
 134         s->size = 256;
 135         s->buffer = isl_alloc_array(ctx, char, s->size);
 136         if (!s->buffer)
 137                 goto error;
 138         return s;
 139 error:
 140         isl_stream_free(s);
 141         return NULL;
 142 }
 143
 144 struct isl_stream* isl_stream_new_file(struct isl_ctx *ctx, FILE *file)
 145 {
 146         struct isl_stream *s = isl_stream_new(ctx);
 147         if (!s)
 148                 return NULL;
 149         s->file = file;
 150         return s;
 151 }
 152
 153 struct isl_stream* isl_stream_new_str(struct isl_ctx *ctx, const char *str)
 154 {
 155         struct isl_stream *s = isl_stream_new(ctx);
 156         if (!s)
 157                 return NULL;
 158         s->str = str;
 159         return s;
 160 }
 161
 162 static int stream_getc(struct isl_stream *s)
 163 {
 164         int c;
 165         if (s->eof)
 166                 return -1;
 167         if (s->file)
 168                 c = fgetc(s->file);
 169         else {
 170                 c = *s->str++;
 171                 if (c == '\0')
 172                         c = -1;
 173         }
 174         if (c == -1)
 175                 s->eof = 1;
 176         if (!s->eof) {
 177                 if (s->c == '\n') {
 178                         s->line++;
 179                         s->col = 0;
 180                 } else
 181                         s->col++;
 182         }
 183         s->c = c;
 184         return c;
 185 }
 186
 187 static int isl_stream_getc(struct isl_stream *s)
 188 {
 189         int c;
 190
 191         do {
 192                 c = stream_getc(s);
 193                 if (c != '\\')
 194                         break;
 195                 c = stream_getc(s);
 196         } while (c == '\n');
 197
 198         return c;
 199 }
 200
 201 static void isl_stream_ungetc(struct isl_stream *s, int c)
 202 {
 203         if (s->file)
 204                 ungetc(c, s->file);
 205         else
 206                 --s->str;
 207         s->c = -1;
 208 }
 209
 210 static int isl_stream_push_char(struct isl_stream *s, int c)
 211 {
 212         if (s->len >= s->size) {
 213                 s->size = (3*s->size)/2;
 214                 s->buffer = isl_realloc_array(s->ctx, s->buffer, char, s->size);
 215                 if (!s->buffer)
 216                         return -1;
 217         }
 218         s->buffer[s->len++] = c;
 219         return 0;
 220 }
 221
 222 void isl_stream_push_token(struct isl_stream *s, struct isl_token *tok)
 223 {
 224         isl_assert(s->ctx, s->n_token < 5, return);
 225         s->tokens[s->n_token++] = tok;
 226 }
 227
 228 static enum isl_token_type check_keywords(struct isl_stream *s)
 229 {
 230         struct isl_hash_table_entry *entry;
 231         struct isl_keyword *keyword;
 232         uint32_t name_hash;
 233
 234         if (!strcasecmp(s->buffer, "exists"))
 235                 return ISL_TOKEN_EXISTS;
 236         if (!strcasecmp(s->buffer, "and"))
 237                 return ISL_TOKEN_AND;
 238         if (!strcasecmp(s->buffer, "or"))
 239                 return ISL_TOKEN_OR;
 240         if (!strcasecmp(s->buffer, "not"))
 241                 return ISL_TOKEN_NOT;
 242         if (!strcasecmp(s->buffer, "infty"))
 243                 return ISL_TOKEN_INFTY;
 244         if (!strcasecmp(s->buffer, "infinity"))
 245                 return ISL_TOKEN_INFTY;
 246         if (!strcasecmp(s->buffer, "NaN"))
 247                 return ISL_TOKEN_NAN;
 248         if (!strcasecmp(s->buffer, "max"))
 249                 return ISL_TOKEN_MAX;
 250         if (!strcasecmp(s->buffer, "rat"))
 251                 return ISL_TOKEN_RAT;
 252         if (!strcasecmp(s->buffer, "true"))
 253                 return ISL_TOKEN_TRUE;
 254         if (!strcasecmp(s->buffer, "false"))
 255                 return ISL_TOKEN_FALSE;
 256
 257         if (!s->keywords)
 258                 return ISL_TOKEN_IDENT;
 259
 260         name_hash = isl_hash_string(isl_hash_init(), s->buffer);
 261         entry = isl_hash_table_find(s->ctx, s->keywords, name_hash, same_name,
 262                                         s->buffer, 0);
 263         if (entry) {
 264                 keyword = entry->data;
 265                 return keyword->type;
 266         }
 267
 268         return ISL_TOKEN_IDENT;
 269 }
 270
 271 int isl_stream_skip_line(struct isl_stream *s)
 272 {
 273         int c;
 274
 275         while ((c = isl_stream_getc(s)) != -1 && c != '\n')
 276                 /* nothing */
 277                 ;
 278
 279         return c == -1 ? -1 : 0;
 280 }
 281
 282 static struct isl_token *next_token(struct isl_stream *s, int same_line)
 283 {
 284         int c;
 285         struct isl_token *tok = NULL;
 286         int line, col;
 287         int old_line = s->line;
 288
 289         if (s->n_token) {
 290                 if (same_line && s->tokens[s->n_token - 1]->on_new_line)
 291                         return NULL;
 292                 return s->tokens[--s->n_token];
 293         }
 294
 295         if (same_line && s->c == '\n')
 296                 return NULL;
 297
 298         s->len = 0;
 299
 300         /* skip spaces and comment lines */
 301         while ((c = isl_stream_getc(s)) != -1) {
 302                 if (c == '#') {
 303                         if (isl_stream_skip_line(s) < 0)
 304                                 break;
 305                         c = '\n';
 306                         if (same_line)
 307                                 break;
 308                 } else if (!isspace(c) || (same_line && c == '\n'))
 309                         break;
 310         }
 311
 312         line = s->line;
 313         col = s->col;
 314
 315         if (c == -1 || (same_line && c == '\n'))
 316                 return NULL;
 317         if (c == '(' ||
 318             c == ')' ||
 319             c == '+' ||
 320             c == '/' ||
 321             c == '*' ||
 322             c == '%' ||
 323             c == '^' ||
 324             c == '=' ||
 325             c == '@' ||
 326             c == ',' ||
 327             c == '.' ||
 328             c == ';' ||
 329             c == '[' ||
 330             c == ']' ||
 331             c == '{' ||
 332             c == '}') {
 333                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 334                 if (!tok)
 335                         return NULL;
 336                 tok->type = (enum isl_token_type)c;
 337                 return tok;
 338         }
 339         if (c == '-') {
 340                 int c;
 341                 if ((c = isl_stream_getc(s)) == '>') {
 342                         tok = isl_token_new(s->ctx, line, col, old_line != line);
 343                         if (!tok)
 344                                 return NULL;
 345                         tok->u.s = strdup("->");
 346                         tok->type = ISL_TOKEN_TO;
 347                         return tok;
 348                 }
 349                 if (c != -1)
 350                         isl_stream_ungetc(s, c);
 351                 if (!isdigit(c)) {
 352                         tok = isl_token_new(s->ctx, line, col, old_line != line);
 353                         if (!tok)
 354                                 return NULL;
 355                         tok->type = (enum isl_token_type) '-';
 356                         return tok;
 357                 }
 358         }
 359         if (c == '-' || isdigit(c)) {
 360                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 361                 if (!tok)
 362                         return NULL;
 363                 tok->type = ISL_TOKEN_VALUE;
 364                 isl_int_init(tok->u.v);
 365                 if (isl_stream_push_char(s, c))
 366                         goto error;
 367                 while ((c = isl_stream_getc(s)) != -1 && isdigit(c))
 368                         if (isl_stream_push_char(s, c))
 369                                 goto error;
 370                 if (c != -1)
 371                         isl_stream_ungetc(s, c);
 372                 isl_stream_push_char(s, '\0');
 373                 isl_int_read(tok->u.v, s->buffer);
 374                 return tok;
 375         }
 376         if (isalpha(c) || c == '_') {
 377                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 378                 if (!tok)
 379                         return NULL;
 380                 isl_stream_push_char(s, c);
 381                 while ((c = isl_stream_getc(s)) != -1 &&
 382                                 (isalnum(c) || c == '_'))
 383                         isl_stream_push_char(s, c);
 384                 if (c != -1)
 385                         isl_stream_ungetc(s, c);
 386                 while ((c = isl_stream_getc(s)) != -1 && c == '\'')
 387                         isl_stream_push_char(s, c);
 388                 if (c != -1)
 389                         isl_stream_ungetc(s, c);
 390                 isl_stream_push_char(s, '\0');
 391                 tok->type = check_keywords(s);
 392                 if (tok->type != ISL_TOKEN_IDENT)
 393                         tok->is_keyword = 1;
 394                 tok->u.s = strdup(s->buffer);
 395                 if (!tok->u.s)
 396                         goto error;
 397                 return tok;
 398         }
 399         if (c == '"') {
 400                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 401                 if (!tok)
 402                         return NULL;
 403                 tok->type = ISL_TOKEN_STRING;
 404                 tok->u.s = NULL;
 405                 while ((c = isl_stream_getc(s)) != -1 && c != '"' && c != '\n')
 406                         isl_stream_push_char(s, c);
 407                 if (c != '"') {
 408                         isl_stream_error(s, NULL, "unterminated string");
 409                         goto error;
 410                 }
 411                 isl_stream_push_char(s, '\0');
 412                 tok->u.s = strdup(s->buffer);
 413                 return tok;
 414         }
 415         if (c == ':') {
 416                 int c;
 417                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 418                 if (!tok)
 419                         return NULL;
 420                 if ((c = isl_stream_getc(s)) == '=') {
 421                         tok->u.s = strdup(":=");
 422                         tok->type = ISL_TOKEN_DEF;
 423                         return tok;
 424                 }
 425                 if (c != -1)
 426                         isl_stream_ungetc(s, c);
 427                 tok->type = (enum isl_token_type) ':';
 428                 return tok;
 429         }
 430         if (c == '>') {
 431                 int c;
 432                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 433                 if (!tok)
 434                         return NULL;
 435                 if ((c = isl_stream_getc(s)) == '=') {
 436                         tok->u.s = strdup(">=");
 437                         tok->type = ISL_TOKEN_GE;
 438                         return tok;
 439                 } else if (c == '>') {
 440                         if ((c = isl_stream_getc(s)) == '=') {
 441                                 tok->u.s = strdup(">>=");
 442                                 tok->type = ISL_TOKEN_LEX_GE;
 443                                 return tok;
 444                         }
 445                         tok->u.s = strdup(">>");
 446                         tok->type = ISL_TOKEN_LEX_GT;
 447                 } else {
 448                         tok->u.s = strdup(">");
 449                         tok->type = ISL_TOKEN_GT;
 450                 }
 451                 if (c != -1)
 452                         isl_stream_ungetc(s, c);
 453                 return tok;
 454         }
 455         if (c == '<') {
 456                 int c;
 457                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 458                 if (!tok)
 459                         return NULL;
 460                 if ((c = isl_stream_getc(s)) == '=') {
 461                         tok->u.s = strdup("<=");
 462                         tok->type = ISL_TOKEN_LE;
 463                         return tok;
 464                 } else if (c == '<') {
 465                         if ((c = isl_stream_getc(s)) == '=') {
 466                                 tok->u.s = strdup("<<=");
 467                                 tok->type = ISL_TOKEN_LEX_LE;
 468                                 return tok;
 469                         }
 470                         tok->u.s = strdup("<<");
 471                         tok->type = ISL_TOKEN_LEX_LT;
 472                 } else {
 473                         tok->u.s = strdup("<");
 474                         tok->type = ISL_TOKEN_LT;
 475                 }
 476                 if (c != -1)
 477                         isl_stream_ungetc(s, c);
 478                 return tok;
 479         }
 480         if (c == '&') {
 481                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 482                 if (!tok)
 483                         return NULL;
 484                 tok->type = ISL_TOKEN_AND;
 485                 if ((c = isl_stream_getc(s)) != '&' && c != -1) {
 486                         tok->u.s = strdup("&");
 487                         isl_stream_ungetc(s, c);
 488                 } else
 489                         tok->u.s = strdup("&&");
 490                 return tok;
 491         }
 492         if (c == '|') {
 493                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 494                 if (!tok)
 495                         return NULL;
 496                 tok->type = ISL_TOKEN_OR;
 497                 if ((c = isl_stream_getc(s)) != '|' && c != -1) {
 498                         tok->u.s = strdup("|");
 499                         isl_stream_ungetc(s, c);
 500                 } else
 501                         tok->u.s = strdup("||");
 502                 return tok;
 503         }
 504         if (c == '!') {
 505                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 506                 if (!tok)
 507                         return NULL;
 508                 tok->type = ISL_TOKEN_NOT;
 509                 tok->u.s = strdup("!");
 510                 return tok;
 511         }
 512
 513         tok = isl_token_new(s->ctx, line, col, old_line != line);
 514         if (!tok)
 515                 return NULL;
 516         tok->type = ISL_TOKEN_UNKNOWN;
 517         return tok;
 518 error:
 519         isl_token_free(tok);
 520         return NULL;
 521 }
 522
 523 struct isl_token *isl_stream_next_token(struct isl_stream *s)
 524 {
 525         return next_token(s, 0);
 526 }
 527
 528 struct isl_token *isl_stream_next_token_on_same_line(struct isl_stream *s)
 529 {
 530         return next_token(s, 1);
 531 }
 532
 533 int isl_stream_eat_if_available(struct isl_stream *s, int type)
 534 {
 535         struct isl_token *tok;
 536
 537         tok = isl_stream_next_token(s);
 538         if (!tok)
 539                 return 0;
 540         if (tok->type == type) {
 541                 isl_token_free(tok);
 542                 return 1;
 543         }
 544         isl_stream_push_token(s, tok);
 545         return 0;
 546 }
 547
 548 int isl_stream_next_token_is(struct isl_stream *s, int type)
 549 {
 550         struct isl_token *tok;
 551         int r;
 552
 553         tok = isl_stream_next_token(s);
 554         if (!tok)
 555                 return 0;
 556         r = tok->type == type;
 557         isl_stream_push_token(s, tok);
 558         return r;
 559 }
 560
 561 char *isl_stream_read_ident_if_available(struct isl_stream *s)
 562 {
 563         struct isl_token *tok;
 564
 565         tok = isl_stream_next_token(s);
 566         if (!tok)
 567                 return NULL;
 568         if (tok->type == ISL_TOKEN_IDENT) {
 569                 char *ident = strdup(tok->u.s);
 570                 isl_token_free(tok);
 571                 return ident;
 572         }
 573         isl_stream_push_token(s, tok);
 574         return NULL;
 575 }
 576
 577 int isl_stream_eat(struct isl_stream *s, int type)
 578 {
 579         struct isl_token *tok;
 580
 581         tok = isl_stream_next_token(s);
 582         if (!tok)
 583                 return -1;
 584         if (tok->type == type) {
 585                 isl_token_free(tok);
 586                 return 0;
 587         }
 588         isl_stream_error(s, tok, "expecting other token");
 589         isl_stream_push_token(s, tok);
 590         return -1;
 591 }
 592
 593 int isl_stream_is_empty(struct isl_stream *s)
 594 {
 595         struct isl_token *tok;
 596
 597         tok = isl_stream_next_token(s);
 598
 599         if (!tok)
 600                 return 1;
 601
 602         isl_stream_push_token(s, tok);
 603         return 0;
 604 }
 605
 606 static int free_keyword(void **p, void *user)
 607 {
 608         struct isl_keyword *keyword = *p;
 609
 610         free(keyword->name);
 611         free(keyword);
 612
 613         return 0;
 614 }
 615
 616 void isl_stream_flush_tokens(struct isl_stream *s)
 617 {
 618         int i;
 619
 620         if (!s)
 621                 return;
 622         for (i = 0; i < s->n_token; ++i)
 623                 isl_token_free(s->tokens[i]);
 624         s->n_token = 0;
 625 }
 626
 627 void isl_stream_free(struct isl_stream *s)
 628 {
 629         if (!s)
 630                 return;
 631         free(s->buffer);
 632         if (s->n_token != 0) {
 633                 struct isl_token *tok = isl_stream_next_token(s);
 634                 isl_stream_error(s, tok, "unexpected token");
 635                 isl_token_free(tok);
 636         }
 637         if (s->keywords) {
 638                 isl_hash_table_foreach(s->ctx, s->keywords, &free_keyword, NULL);
 639                 isl_hash_table_free(s->ctx, s->keywords);
 640         }
 641         isl_ctx_deref(s->ctx);
 642         free(s);
 643 }