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