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