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)
  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     s->str = str;
 145     return s;
 146 }
 147
 148 static int isl_stream_getc(struct isl_stream *s)
 149 {
 150         int c;
 151         if (s->eof)
 152                 return -1;
 153         if (s->file)
 154                 c = fgetc(s->file);
 155         else {
 156                 c = *s->str++;
 157                 if (c == '\0')
 158                         c = -1;
 159         }
 160         if (c == -1)
 161                 s->eof = 1;
 162         if (!s->eof) {
 163                 if (s->c == '\n') {
 164                         s->line++;
 165                         s->col = 0;
 166                 } else
 167                         s->col++;
 168         }
 169         s->c = c;
 170         return c;
 171 }
 172
 173 static void isl_stream_ungetc(struct isl_stream *s, int c)
 174 {
 175         if (s->file)
 176                 ungetc(c, s->file);
 177         else
 178                 --s->str;
 179         s->c = -1;
 180 }
 181
 182 static int isl_stream_push_char(struct isl_stream *s, int c)
 183 {
 184         if (s->len >= s->size) {
 185                 s->size = (3*s->size)/2;
 186                 s->buffer = isl_realloc_array(ctx, s->buffer, char, s->size);
 187                 if (!s->buffer)
 188                         return -1;
 189         }
 190         s->buffer[s->len++] = c;
 191         return 0;
 192 }
 193
 194 void isl_stream_push_token(struct isl_stream *s, struct isl_token *tok)
 195 {
 196         isl_assert(s->ctx, s->n_token < 5, return);
 197         s->tokens[s->n_token++] = tok;
 198 }
 199
 200 static enum isl_token_type check_keywords(struct isl_stream *s)
 201 {
 202         struct isl_hash_table_entry *entry;
 203         struct isl_keyword *keyword;
 204         uint32_t name_hash;
 205
 206         if (!strcasecmp(s->buffer, "exists"))
 207                 return ISL_TOKEN_EXISTS;
 208         if (!strcasecmp(s->buffer, "and"))
 209                 return ISL_TOKEN_AND;
 210         if (!strcasecmp(s->buffer, "or"))
 211                 return ISL_TOKEN_OR;
 212         if (!strcasecmp(s->buffer, "infty"))
 213                 return ISL_TOKEN_INFTY;
 214         if (!strcasecmp(s->buffer, "infinity"))
 215                 return ISL_TOKEN_INFTY;
 216         if (!strcasecmp(s->buffer, "NaN"))
 217                 return ISL_TOKEN_NAN;
 218
 219         if (!s->keywords)
 220                 return ISL_TOKEN_IDENT;
 221
 222         name_hash = isl_hash_string(isl_hash_init(), s->buffer);
 223         entry = isl_hash_table_find(s->ctx, s->keywords, name_hash, same_name,
 224                                         s->buffer, 0);
 225         if (entry) {
 226                 keyword = entry->data;
 227                 return keyword->type;
 228         }
 229
 230         return ISL_TOKEN_IDENT;
 231 }
 232
 233 static struct isl_token *next_token(struct isl_stream *s, int same_line)
 234 {
 235         int c;
 236         struct isl_token *tok = NULL;
 237         int line, col;
 238         int old_line = s->line;
 239
 240         if (s->n_token) {
 241                 if (same_line && s->tokens[s->n_token - 1]->on_new_line)
 242                         return NULL;
 243                 return s->tokens[--s->n_token];
 244         }
 245
 246         if (same_line && s->c == '\n')
 247                 return NULL;
 248
 249         s->len = 0;
 250
 251         /* skip spaces and comment lines */
 252         while ((c = isl_stream_getc(s)) != -1) {
 253                 if (c == '#') {
 254                         while ((c = isl_stream_getc(s)) != -1 && c != '\n')
 255                                 /* nothing */
 256                                 ;
 257                         if (c == -1 || (same_line && c == '\n'))
 258                                 break;
 259                 } else if (!isspace(c) || (same_line && c == '\n'))
 260                         break;
 261         }
 262
 263         line = s->line;
 264         col = s->col;
 265
 266         if (c == -1 || (same_line && c == '\n'))
 267                 return NULL;
 268         if (c == '(' ||
 269             c == ')' ||
 270             c == '+' ||
 271             c == '/' ||
 272             c == '*' ||
 273             c == '^' ||
 274             c == '=' ||
 275             c == '@' ||
 276             c == ',' ||
 277             c == ';' ||
 278             c == '[' ||
 279             c == ']' ||
 280             c == '{' ||
 281             c == '}') {
 282                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 283                 if (!tok)
 284                         return NULL;
 285                 tok->type = (enum isl_token_type)c;
 286                 return tok;
 287         }
 288         if (c == '-') {
 289                 int c;
 290                 if ((c = isl_stream_getc(s)) == '>') {
 291                         tok = isl_token_new(s->ctx, line, col, old_line != line);
 292                         if (!tok)
 293                                 return NULL;
 294                         tok->type = ISL_TOKEN_TO;
 295                         return tok;
 296                 }
 297                 if (c != -1)
 298                         isl_stream_ungetc(s, c);
 299                 if (!isdigit(c)) {
 300                         tok = isl_token_new(s->ctx, line, col, old_line != line);
 301                         if (!tok)
 302                                 return NULL;
 303                         tok->type = (enum isl_token_type) '-';
 304                         return tok;
 305                 }
 306         }
 307         if (c == '-' || isdigit(c)) {
 308                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 309                 if (!tok)
 310                         return NULL;
 311                 tok->type = ISL_TOKEN_VALUE;
 312                 isl_int_init(tok->u.v);
 313                 if (isl_stream_push_char(s, c))
 314                         goto error;
 315                 while ((c = isl_stream_getc(s)) != -1 && isdigit(c))
 316                         if (isl_stream_push_char(s, c))
 317                                 goto error;
 318                 if (c != -1)
 319                         isl_stream_ungetc(s, c);
 320                 isl_stream_push_char(s, '\0');
 321                 isl_int_read(tok->u.v, s->buffer);
 322                 return tok;
 323         }
 324         if (isalpha(c)) {
 325                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 326                 if (!tok)
 327                         return NULL;
 328                 isl_stream_push_char(s, c);
 329                 while ((c = isl_stream_getc(s)) != -1 &&
 330                                 (isalnum(c) || c == '_'))
 331                         isl_stream_push_char(s, c);
 332                 if (c != -1)
 333                         isl_stream_ungetc(s, c);
 334                 while ((c = isl_stream_getc(s)) != -1 && c == '\'')
 335                         isl_stream_push_char(s, c);
 336                 if (c != -1)
 337                         isl_stream_ungetc(s, c);
 338                 isl_stream_push_char(s, '\0');
 339                 tok->type = check_keywords(s);
 340                 if (tok->type == ISL_TOKEN_IDENT)
 341                         tok->u.s = strdup(s->buffer);
 342                 return tok;
 343         }
 344         if (c == ':') {
 345                 int c;
 346                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 347                 if (!tok)
 348                         return NULL;
 349                 if ((c = isl_stream_getc(s)) == '=') {
 350                         tok->type = ISL_TOKEN_DEF;
 351                         return tok;
 352                 }
 353                 if (c != -1)
 354                         isl_stream_ungetc(s, c);
 355                 tok->type = ':';
 356                 return tok;
 357         }
 358         if (c == '>') {
 359                 int c;
 360                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 361                 if (!tok)
 362                         return NULL;
 363                 if ((c = isl_stream_getc(s)) == '=') {
 364                         tok->type = ISL_TOKEN_GE;
 365                         return tok;
 366                 }
 367                 if (c != -1)
 368                         isl_stream_ungetc(s, c);
 369                 tok->type = ISL_TOKEN_GT;
 370                 return tok;
 371         }
 372         if (c == '<') {
 373                 int c;
 374                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 375                 if (!tok)
 376                         return NULL;
 377                 if ((c = isl_stream_getc(s)) == '=') {
 378                         tok->type = ISL_TOKEN_LE;
 379                         return tok;
 380                 }
 381                 if (c != -1)
 382                         isl_stream_ungetc(s, c);
 383                 tok->type = ISL_TOKEN_LT;
 384                 return tok;
 385         }
 386         if (c == '&') {
 387                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 388                 if (!tok)
 389                         return NULL;
 390                 tok->type = ISL_TOKEN_AND;
 391                 if ((c = isl_stream_getc(s)) != '&' && c != -1)
 392                         isl_stream_ungetc(s, c);
 393                 return tok;
 394         }
 395         if (c == '|') {
 396                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 397                 if (!tok)
 398                         return NULL;
 399                 tok->type = ISL_TOKEN_OR;
 400                 if ((c = isl_stream_getc(s)) != '|' && c != -1)
 401                         isl_stream_ungetc(s, c);
 402                 return tok;
 403         }
 404
 405         tok = isl_token_new(s->ctx, line, col, old_line != line);
 406         if (!tok)
 407                 return NULL;
 408         tok->type = ISL_TOKEN_UNKNOWN;
 409         return tok;
 410 error:
 411         isl_token_free(tok);
 412         return NULL;
 413 }
 414
 415 struct isl_token *isl_stream_next_token(struct isl_stream *s)
 416 {
 417         return next_token(s, 0);
 418 }
 419
 420 struct isl_token *isl_stream_next_token_on_same_line(struct isl_stream *s)
 421 {
 422         return next_token(s, 1);
 423 }
 424
 425 int isl_stream_eat_if_available(struct isl_stream *s, int type)
 426 {
 427         struct isl_token *tok;
 428
 429         tok = isl_stream_next_token(s);
 430         if (!tok)
 431                 return 0;
 432         if (tok->type == type) {
 433                 isl_token_free(tok);
 434                 return 1;
 435         }
 436         isl_stream_push_token(s, tok);
 437         return 0;
 438 }
 439
 440 int isl_stream_next_token_is(struct isl_stream *s, int type)
 441 {
 442         struct isl_token *tok;
 443         int r;
 444
 445         tok = isl_stream_next_token(s);
 446         if (!tok)
 447                 return 0;
 448         r = tok->type == type;
 449         isl_stream_push_token(s, tok);
 450         return r;
 451 }
 452
 453 char *isl_stream_read_ident_if_available(struct isl_stream *s)
 454 {
 455         struct isl_token *tok;
 456
 457         tok = isl_stream_next_token(s);
 458         if (!tok)
 459                 return NULL;
 460         if (tok->type == ISL_TOKEN_IDENT) {
 461                 char *ident = strdup(tok->u.s);
 462                 isl_token_free(tok);
 463                 return ident;
 464         }
 465         isl_stream_push_token(s, tok);
 466         return NULL;
 467 }
 468
 469 int isl_stream_eat(struct isl_stream *s, int type)
 470 {
 471         struct isl_token *tok;
 472
 473         tok = isl_stream_next_token(s);
 474         if (!tok)
 475                 return -1;
 476         if (tok->type == type) {
 477                 isl_token_free(tok);
 478                 return 0;
 479         }
 480         isl_stream_error(s, tok, "expecting other token");
 481         isl_stream_push_token(s, tok);
 482         return -1;
 483 }
 484
 485 int isl_stream_is_empty(struct isl_stream *s)
 486 {
 487         struct isl_token *tok;
 488
 489         tok = isl_stream_next_token(s);
 490
 491         if (!tok)
 492                 return 1;
 493
 494         isl_stream_push_token(s, tok);
 495         return 0;
 496 }
 497
 498 static int free_keyword(void *p)
 499 {
 500         struct isl_keyword *keyword = p;
 501
 502         free(keyword->name);
 503         free(keyword);
 504
 505         return 0;
 506 }
 507
 508 void isl_stream_free(struct isl_stream *s)
 509 {
 510         if (!s)
 511                 return;
 512         free(s->buffer);
 513         if (s->n_token != 0) {
 514                 struct isl_token *tok = isl_stream_next_token(s);
 515                 isl_stream_error(s, tok, "unexpected token");
 516                 isl_token_free(tok);
 517         }
 518         if (s->keywords) {
 519                 isl_hash_table_foreach(s->ctx, s->keywords, free_keyword);
 520                 isl_hash_table_free(s->ctx, s->keywords);
 521         }
 522         isl_ctx_deref(s->ctx);
 523         free(s);
 524 }