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