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