isl_stream.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  *
   4  * Use of this software is governed by the MIT 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 <isl/ctx.h>
  13 #include <isl_stream_private.h>
  14 #include <isl/map.h>
  15 #include <isl/aff.h>
  16 #include <isl_val_private.h>
  17
  18 struct isl_keyword {
  19         char                    *name;
  20         enum isl_token_type     type;
  21 };
  22
  23 static int same_name(const void *entry, const void *val)
  24 {
  25         const struct isl_keyword *keyword = (const struct isl_keyword *)entry;
  26
  27         return !strcmp(keyword->name, val);
  28 }
  29
  30 enum isl_token_type isl_stream_register_keyword(__isl_keep isl_stream *s,
  31         const char *name)
  32 {
  33         struct isl_hash_table_entry *entry;
  34         struct isl_keyword *keyword;
  35         uint32_t name_hash;
  36
  37         if (!s->keywords) {
  38                 s->keywords = isl_hash_table_alloc(s->ctx, 10);
  39                 if (!s->keywords)
  40                         return ISL_TOKEN_ERROR;
  41                 s->next_type = ISL_TOKEN_LAST;
  42         }
  43
  44         name_hash = isl_hash_string(isl_hash_init(), name);
  45
  46         entry = isl_hash_table_find(s->ctx, s->keywords, name_hash,
  47                                         same_name, name, 1);
  48         if (!entry)
  49                 return ISL_TOKEN_ERROR;
  50         if (entry->data) {
  51                 keyword = entry->data;
  52                 return keyword->type;
  53         }
  54
  55         keyword = isl_calloc_type(s->ctx, struct isl_keyword);
  56         if (!keyword)
  57                 return ISL_TOKEN_ERROR;
  58         keyword->type = s->next_type++;
  59         keyword->name = strdup(name);
  60         if (!keyword->name) {
  61                 free(keyword);
  62                 return ISL_TOKEN_ERROR;
  63         }
  64         entry->data = keyword;
  65
  66         return keyword->type;
  67 }
  68
  69 struct isl_token *isl_token_new(isl_ctx *ctx,
  70         int line, int col, unsigned on_new_line)
  71 {
  72         struct isl_token *tok = isl_alloc_type(ctx, struct isl_token);
  73         if (!tok)
  74                 return NULL;
  75         tok->line = line;
  76         tok->col = col;
  77         tok->on_new_line = on_new_line;
  78         tok->is_keyword = 0;
  79         tok->u.s = NULL;
  80         return tok;
  81 }
  82
  83 /* Return the type of "tok".
  84  */
  85 int isl_token_get_type(struct isl_token *tok)
  86 {
  87         return tok ? tok->type : ISL_TOKEN_ERROR;
  88 }
  89
  90 /* Given a token of type ISL_TOKEN_VALUE, return the value it represents.
  91  */
  92 __isl_give isl_val *isl_token_get_val(isl_ctx *ctx, struct isl_token *tok)
  93 {
  94         if (!tok)
  95                 return NULL;
  96         if (tok->type != ISL_TOKEN_VALUE)
  97                 isl_die(ctx, isl_error_invalid, "not a value token",
  98                         return NULL);
  99
 100         return isl_val_int_from_isl_int(ctx, tok->u.v);
 101 }
 102
 103 /* Given a token with a string representation, return a copy of this string.
 104  */
 105 __isl_give char *isl_token_get_str(isl_ctx *ctx, struct isl_token *tok)
 106 {
 107         if (!tok)
 108                 return NULL;
 109         if (!tok->u.s)
 110                 isl_die(ctx, isl_error_invalid,
 111                         "token does not have a string representation",
 112                         return NULL);
 113
 114         return strdup(tok->u.s);
 115 }
 116
 117 void isl_token_free(struct isl_token *tok)
 118 {
 119         if (!tok)
 120                 return;
 121         if (tok->type == ISL_TOKEN_VALUE)
 122                 isl_int_clear(tok->u.v);
 123         else if (tok->type == ISL_TOKEN_MAP)
 124                 isl_map_free(tok->u.map);
 125         else if (tok->type == ISL_TOKEN_AFF)
 126                 isl_pw_aff_free(tok->u.pwaff);
 127         else
 128                 free(tok->u.s);
 129         free(tok);
 130 }
 131
 132 void isl_stream_error(__isl_keep isl_stream *s, struct isl_token *tok,
 133         char *msg)
 134 {
 135         int line = tok ? tok->line : s->line;
 136         int col = tok ? tok->col : s->col;
 137         fprintf(stderr, "syntax error (%d, %d): %s\n", line, col, msg);
 138         if (tok) {
 139                 if (tok->type < 256)
 140                         fprintf(stderr, "got '%c'\n", tok->type);
 141                 else if (tok->type == ISL_TOKEN_IDENT)
 142                         fprintf(stderr, "got ident '%s'\n", tok->u.s);
 143                 else if (tok->is_keyword)
 144                         fprintf(stderr, "got keyword '%s'\n", tok->u.s);
 145                 else if (tok->type == ISL_TOKEN_VALUE) {
 146                         fprintf(stderr, "got value '");
 147                         isl_int_print(stderr, tok->u.v, 0);
 148                         fprintf(stderr, "'\n");
 149                 } else if (tok->type == ISL_TOKEN_MAP) {
 150                         isl_printer *p;
 151                         fprintf(stderr, "got map '");
 152                         p = isl_printer_to_file(s->ctx, stderr);
 153                         p = isl_printer_print_map(p, tok->u.map);
 154                         isl_printer_free(p);
 155                         fprintf(stderr, "'\n");
 156                 } else if (tok->type == ISL_TOKEN_AFF) {
 157                         isl_printer *p;
 158                         fprintf(stderr, "got affine expression '");
 159                         p = isl_printer_to_file(s->ctx, stderr);
 160                         p = isl_printer_print_pw_aff(p, tok->u.pwaff);
 161                         isl_printer_free(p);
 162                         fprintf(stderr, "'\n");
 163                 } else if (tok->u.s)
 164                         fprintf(stderr, "got token '%s'\n", tok->u.s);
 165                 else
 166                         fprintf(stderr, "got token type %d\n", tok->type);
 167         }
 168 }
 169
 170 static __isl_give isl_stream* isl_stream_new(struct isl_ctx *ctx)
 171 {
 172         int i;
 173         isl_stream *s = isl_calloc_type(ctx, struct isl_stream);
 174         if (!s)
 175                 return NULL;
 176         s->ctx = ctx;
 177         isl_ctx_ref(s->ctx);
 178         s->file = NULL;
 179         s->str = NULL;
 180         s->len = 0;
 181         s->line = 1;
 182         s->col = 1;
 183         s->eof = 0;
 184         s->last_line = 0;
 185         s->c = -1;
 186         s->n_un = 0;
 187         for (i = 0; i < 5; ++i)
 188                 s->tokens[i] = NULL;
 189         s->n_token = 0;
 190         s->keywords = NULL;
 191         s->size = 256;
 192         s->buffer = isl_alloc_array(ctx, char, s->size);
 193         if (!s->buffer)
 194                 goto error;
 195         return s;
 196 error:
 197         isl_stream_free(s);
 198         return NULL;
 199 }
 200
 201 __isl_give isl_stream* isl_stream_new_file(struct isl_ctx *ctx, FILE *file)
 202 {
 203         isl_stream *s = isl_stream_new(ctx);
 204         if (!s)
 205                 return NULL;
 206         s->file = file;
 207         return s;
 208 }
 209
 210 __isl_give isl_stream* isl_stream_new_str(struct isl_ctx *ctx, const char *str)
 211 {
 212         isl_stream *s;
 213         if (!str)
 214                 return NULL;
 215         s = isl_stream_new(ctx);
 216         if (!s)
 217                 return NULL;
 218         s->str = str;
 219         return s;
 220 }
 221
 222 /* Read a character from the stream and advance s->line and s->col
 223  * to point to the next character.
 224  */
 225 static int stream_getc(__isl_keep isl_stream *s)
 226 {
 227         int c;
 228         if (s->eof)
 229                 return -1;
 230         if (s->n_un)
 231                 return s->c = s->un[--s->n_un];
 232         if (s->file)
 233                 c = fgetc(s->file);
 234         else {
 235                 c = *s->str++;
 236                 if (c == '\0')
 237                         c = -1;
 238         }
 239         if (c == -1)
 240                 s->eof = 1;
 241         else if (c == '\n') {
 242                 s->line++;
 243                 s->col = 1;
 244         } else
 245                 s->col++;
 246         s->c = c;
 247         return c;
 248 }
 249
 250 static void isl_stream_ungetc(__isl_keep isl_stream *s, int c)
 251 {
 252         isl_assert(s->ctx, s->n_un < 5, return);
 253         s->un[s->n_un++] = c;
 254         s->c = -1;
 255 }
 256
 257 /* Read a character from the stream, skipping pairs of '\\' and '\n'.
 258  * Set s->start_line and s->start_col to the line and column
 259  * of the returned character.
 260  */
 261 static int isl_stream_getc(__isl_keep isl_stream *s)
 262 {
 263         int c;
 264
 265         do {
 266                 s->start_line = s->line;
 267                 s->start_col = s->col;
 268                 c = stream_getc(s);
 269                 if (c != '\\')
 270                         return c;
 271                 c = stream_getc(s);
 272         } while (c == '\n');
 273
 274         isl_stream_ungetc(s, c);
 275
 276         return '\\';
 277 }
 278
 279 static int isl_stream_push_char(__isl_keep isl_stream *s, int c)
 280 {
 281         if (s->len >= s->size) {
 282                 char *buffer;
 283                 s->size = (3*s->size)/2;
 284                 buffer = isl_realloc_array(s->ctx, s->buffer, char, s->size);
 285                 if (!buffer)
 286                         return -1;
 287                 s->buffer = buffer;
 288         }
 289         s->buffer[s->len++] = c;
 290         return 0;
 291 }
 292
 293 void isl_stream_push_token(__isl_keep isl_stream *s, struct isl_token *tok)
 294 {
 295         isl_assert(s->ctx, s->n_token < 5, return);
 296         s->tokens[s->n_token++] = tok;
 297 }
 298
 299 static enum isl_token_type check_keywords(__isl_keep isl_stream *s)
 300 {
 301         struct isl_hash_table_entry *entry;
 302         struct isl_keyword *keyword;
 303         uint32_t name_hash;
 304
 305         if (!strcasecmp(s->buffer, "exists"))
 306                 return ISL_TOKEN_EXISTS;
 307         if (!strcasecmp(s->buffer, "and"))
 308                 return ISL_TOKEN_AND;
 309         if (!strcasecmp(s->buffer, "or"))
 310                 return ISL_TOKEN_OR;
 311         if (!strcasecmp(s->buffer, "implies"))
 312                 return ISL_TOKEN_IMPLIES;
 313         if (!strcasecmp(s->buffer, "not"))
 314                 return ISL_TOKEN_NOT;
 315         if (!strcasecmp(s->buffer, "infty"))
 316                 return ISL_TOKEN_INFTY;
 317         if (!strcasecmp(s->buffer, "infinity"))
 318                 return ISL_TOKEN_INFTY;
 319         if (!strcasecmp(s->buffer, "NaN"))
 320                 return ISL_TOKEN_NAN;
 321         if (!strcasecmp(s->buffer, "min"))
 322                 return ISL_TOKEN_MIN;
 323         if (!strcasecmp(s->buffer, "max"))
 324                 return ISL_TOKEN_MAX;
 325         if (!strcasecmp(s->buffer, "rat"))
 326                 return ISL_TOKEN_RAT;
 327         if (!strcasecmp(s->buffer, "true"))
 328                 return ISL_TOKEN_TRUE;
 329         if (!strcasecmp(s->buffer, "false"))
 330                 return ISL_TOKEN_FALSE;
 331         if (!strcasecmp(s->buffer, "ceild"))
 332                 return ISL_TOKEN_CEILD;
 333         if (!strcasecmp(s->buffer, "floord"))
 334                 return ISL_TOKEN_FLOORD;
 335         if (!strcasecmp(s->buffer, "mod"))
 336                 return ISL_TOKEN_MOD;
 337         if (!strcasecmp(s->buffer, "ceil"))
 338                 return ISL_TOKEN_CEIL;
 339         if (!strcasecmp(s->buffer, "floor"))
 340                 return ISL_TOKEN_FLOOR;
 341
 342         if (!s->keywords)
 343                 return ISL_TOKEN_IDENT;
 344
 345         name_hash = isl_hash_string(isl_hash_init(), s->buffer);
 346         entry = isl_hash_table_find(s->ctx, s->keywords, name_hash, same_name,
 347                                         s->buffer, 0);
 348         if (entry) {
 349                 keyword = entry->data;
 350                 return keyword->type;
 351         }
 352
 353         return ISL_TOKEN_IDENT;
 354 }
 355
 356 int isl_stream_skip_line(__isl_keep isl_stream *s)
 357 {
 358         int c;
 359
 360         while ((c = isl_stream_getc(s)) != -1 && c != '\n')
 361                 /* nothing */
 362                 ;
 363
 364         return c == -1 ? -1 : 0;
 365 }
 366
 367 static struct isl_token *next_token(__isl_keep isl_stream *s, int same_line)
 368 {
 369         int c;
 370         struct isl_token *tok = NULL;
 371         int line, col;
 372         int old_line = s->last_line;
 373
 374         if (s->n_token) {
 375                 if (same_line && s->tokens[s->n_token - 1]->on_new_line)
 376                         return NULL;
 377                 return s->tokens[--s->n_token];
 378         }
 379
 380         if (same_line && s->c == '\n')
 381                 return NULL;
 382
 383         s->len = 0;
 384
 385         /* skip spaces and comment lines */
 386         while ((c = isl_stream_getc(s)) != -1) {
 387                 if (c == '#') {
 388                         if (isl_stream_skip_line(s) < 0)
 389                                 break;
 390                         c = '\n';
 391                         if (same_line)
 392                                 break;
 393                 } else if (!isspace(c) || (same_line && c == '\n'))
 394                         break;
 395         }
 396
 397         line = s->start_line;
 398         col = s->start_col;
 399
 400         if (c == -1 || (same_line && c == '\n'))
 401                 return NULL;
 402         s->last_line = line;
 403
 404         if (c == '(' ||
 405             c == ')' ||
 406             c == '+' ||
 407             c == '*' ||
 408             c == '%' ||
 409             c == '?' ||
 410             c == '^' ||
 411             c == '@' ||
 412             c == '$' ||
 413             c == ',' ||
 414             c == '.' ||
 415             c == ';' ||
 416             c == '[' ||
 417             c == ']' ||
 418             c == '{' ||
 419             c == '}') {
 420                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 421                 if (!tok)
 422                         return NULL;
 423                 tok->type = (enum isl_token_type)c;
 424                 return tok;
 425         }
 426         if (c == '-') {
 427                 int c;
 428                 if ((c = isl_stream_getc(s)) == '>') {
 429                         tok = isl_token_new(s->ctx, line, col, old_line != line);
 430                         if (!tok)
 431                                 return NULL;
 432                         tok->u.s = strdup("->");
 433                         tok->type = ISL_TOKEN_TO;
 434                         return tok;
 435                 }
 436                 if (c != -1)
 437                         isl_stream_ungetc(s, c);
 438                 if (!isdigit(c)) {
 439                         tok = isl_token_new(s->ctx, line, col, old_line != line);
 440                         if (!tok)
 441                                 return NULL;
 442                         tok->type = (enum isl_token_type) '-';
 443                         return tok;
 444                 }
 445         }
 446         if (c == '-' || isdigit(c)) {
 447                 int minus = c == '-';
 448                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 449                 if (!tok)
 450                         return NULL;
 451                 tok->type = ISL_TOKEN_VALUE;
 452                 isl_int_init(tok->u.v);
 453                 if (isl_stream_push_char(s, c))
 454                         goto error;
 455                 while ((c = isl_stream_getc(s)) != -1 && isdigit(c))
 456                         if (isl_stream_push_char(s, c))
 457                                 goto error;
 458                 if (c != -1)
 459                         isl_stream_ungetc(s, c);
 460                 isl_stream_push_char(s, '\0');
 461                 isl_int_read(tok->u.v, s->buffer);
 462                 if (minus && isl_int_is_zero(tok->u.v)) {
 463                         tok->col++;
 464                         tok->on_new_line = 0;
 465                         isl_stream_push_token(s, tok);
 466                         tok = isl_token_new(s->ctx, line, col, old_line != line);
 467                         if (!tok)
 468                                 return NULL;
 469                         tok->type = (enum isl_token_type) '-';
 470                 }
 471                 return tok;
 472         }
 473         if (isalpha(c) || c == '_') {
 474                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 475                 if (!tok)
 476                         return NULL;
 477                 isl_stream_push_char(s, c);
 478                 while ((c = isl_stream_getc(s)) != -1 &&
 479                                 (isalnum(c) || c == '_'))
 480                         isl_stream_push_char(s, c);
 481                 if (c != -1)
 482                         isl_stream_ungetc(s, c);
 483                 while ((c = isl_stream_getc(s)) != -1 && c == '\'')
 484                         isl_stream_push_char(s, c);
 485                 if (c != -1)
 486                         isl_stream_ungetc(s, c);
 487                 isl_stream_push_char(s, '\0');
 488                 tok->type = check_keywords(s);
 489                 if (tok->type != ISL_TOKEN_IDENT)
 490                         tok->is_keyword = 1;
 491                 tok->u.s = strdup(s->buffer);
 492                 if (!tok->u.s)
 493                         goto error;
 494                 return tok;
 495         }
 496         if (c == '"') {
 497                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 498                 if (!tok)
 499                         return NULL;
 500                 tok->type = ISL_TOKEN_STRING;
 501                 tok->u.s = NULL;
 502                 while ((c = isl_stream_getc(s)) != -1 && c != '"' && c != '\n')
 503                         isl_stream_push_char(s, c);
 504                 if (c != '"') {
 505                         isl_stream_error(s, NULL, "unterminated string");
 506                         goto error;
 507                 }
 508                 isl_stream_push_char(s, '\0');
 509                 tok->u.s = strdup(s->buffer);
 510                 return tok;
 511         }
 512         if (c == '=') {
 513                 int c;
 514                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 515                 if (!tok)
 516                         return NULL;
 517                 if ((c = isl_stream_getc(s)) == '=') {
 518                         tok->u.s = strdup("==");
 519                         tok->type = ISL_TOKEN_EQ_EQ;
 520                         return tok;
 521                 }
 522                 if (c != -1)
 523                         isl_stream_ungetc(s, c);
 524                 tok->type = (enum isl_token_type) '=';
 525                 return tok;
 526         }
 527         if (c == ':') {
 528                 int c;
 529                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 530                 if (!tok)
 531                         return NULL;
 532                 if ((c = isl_stream_getc(s)) == '=') {
 533                         tok->u.s = strdup(":=");
 534                         tok->type = ISL_TOKEN_DEF;
 535                         return tok;
 536                 }
 537                 if (c != -1)
 538                         isl_stream_ungetc(s, c);
 539                 tok->type = (enum isl_token_type) ':';
 540                 return tok;
 541         }
 542         if (c == '>') {
 543                 int c;
 544                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 545                 if (!tok)
 546                         return NULL;
 547                 if ((c = isl_stream_getc(s)) == '=') {
 548                         tok->u.s = strdup(">=");
 549                         tok->type = ISL_TOKEN_GE;
 550                         return tok;
 551                 } else if (c == '>') {
 552                         if ((c = isl_stream_getc(s)) == '=') {
 553                                 tok->u.s = strdup(">>=");
 554                                 tok->type = ISL_TOKEN_LEX_GE;
 555                                 return tok;
 556                         }
 557                         tok->u.s = strdup(">>");
 558                         tok->type = ISL_TOKEN_LEX_GT;
 559                 } else {
 560                         tok->u.s = strdup(">");
 561                         tok->type = ISL_TOKEN_GT;
 562                 }
 563                 if (c != -1)
 564                         isl_stream_ungetc(s, c);
 565                 return tok;
 566         }
 567         if (c == '<') {
 568                 int c;
 569                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 570                 if (!tok)
 571                         return NULL;
 572                 if ((c = isl_stream_getc(s)) == '=') {
 573                         tok->u.s = strdup("<=");
 574                         tok->type = ISL_TOKEN_LE;
 575                         return tok;
 576                 } else if (c == '<') {
 577                         if ((c = isl_stream_getc(s)) == '=') {
 578                                 tok->u.s = strdup("<<=");
 579                                 tok->type = ISL_TOKEN_LEX_LE;
 580                                 return tok;
 581                         }
 582                         tok->u.s = strdup("<<");
 583                         tok->type = ISL_TOKEN_LEX_LT;
 584                 } else {
 585                         tok->u.s = strdup("<");
 586                         tok->type = ISL_TOKEN_LT;
 587                 }
 588                 if (c != -1)
 589                         isl_stream_ungetc(s, c);
 590                 return tok;
 591         }
 592         if (c == '&') {
 593                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 594                 if (!tok)
 595                         return NULL;
 596                 tok->type = ISL_TOKEN_AND;
 597                 if ((c = isl_stream_getc(s)) != '&' && c != -1) {
 598                         tok->u.s = strdup("&");
 599                         isl_stream_ungetc(s, c);
 600                 } else
 601                         tok->u.s = strdup("&&");
 602                 return tok;
 603         }
 604         if (c == '|') {
 605                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 606                 if (!tok)
 607                         return NULL;
 608                 tok->type = ISL_TOKEN_OR;
 609                 if ((c = isl_stream_getc(s)) != '|' && c != -1) {
 610                         tok->u.s = strdup("|");
 611                         isl_stream_ungetc(s, c);
 612                 } else
 613                         tok->u.s = strdup("||");
 614                 return tok;
 615         }
 616         if (c == '/') {
 617                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 618                 if (!tok)
 619                         return NULL;
 620                 if ((c = isl_stream_getc(s)) != '\\' && c != -1) {
 621                         tok->type = (enum isl_token_type) '/';
 622                         isl_stream_ungetc(s, c);
 623                 } else {
 624                         tok->u.s = strdup("/\\");
 625                         tok->type = ISL_TOKEN_AND;
 626                 }
 627                 return tok;
 628         }
 629         if (c == '\\') {
 630                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 631                 if (!tok)
 632                         return NULL;
 633                 if ((c = isl_stream_getc(s)) != '/' && c != -1) {
 634                         tok->type = (enum isl_token_type) '\\';
 635                         isl_stream_ungetc(s, c);
 636                 } else {
 637                         tok->u.s = strdup("\\/");
 638                         tok->type = ISL_TOKEN_OR;
 639                 }
 640                 return tok;
 641         }
 642         if (c == '!') {
 643                 tok = isl_token_new(s->ctx, line, col, old_line != line);
 644                 if (!tok)
 645                         return NULL;
 646                 if ((c = isl_stream_getc(s)) == '=') {
 647                         tok->u.s = strdup("!=");
 648                         tok->type = ISL_TOKEN_NE;
 649                         return tok;
 650                 } else {
 651                         tok->type = ISL_TOKEN_NOT;
 652                         tok->u.s = strdup("!");
 653                 }
 654                 if (c != -1)
 655                         isl_stream_ungetc(s, c);
 656                 return tok;
 657         }
 658
 659         tok = isl_token_new(s->ctx, line, col, old_line != line);
 660         if (!tok)
 661                 return NULL;
 662         tok->type = ISL_TOKEN_UNKNOWN;
 663         return tok;
 664 error:
 665         isl_token_free(tok);
 666         return NULL;
 667 }
 668
 669 struct isl_token *isl_stream_next_token(__isl_keep isl_stream *s)
 670 {
 671         return next_token(s, 0);
 672 }
 673
 674 struct isl_token *isl_stream_next_token_on_same_line(__isl_keep isl_stream *s)
 675 {
 676         return next_token(s, 1);
 677 }
 678
 679 int isl_stream_eat_if_available(__isl_keep isl_stream *s, int type)
 680 {
 681         struct isl_token *tok;
 682
 683         tok = isl_stream_next_token(s);
 684         if (!tok)
 685                 return 0;
 686         if (tok->type == type) {
 687                 isl_token_free(tok);
 688                 return 1;
 689         }
 690         isl_stream_push_token(s, tok);
 691         return 0;
 692 }
 693
 694 int isl_stream_next_token_is(__isl_keep isl_stream *s, int type)
 695 {
 696         struct isl_token *tok;
 697         int r;
 698
 699         tok = isl_stream_next_token(s);
 700         if (!tok)
 701                 return 0;
 702         r = tok->type == type;
 703         isl_stream_push_token(s, tok);
 704         return r;
 705 }
 706
 707 char *isl_stream_read_ident_if_available(__isl_keep isl_stream *s)
 708 {
 709         struct isl_token *tok;
 710
 711         tok = isl_stream_next_token(s);
 712         if (!tok)
 713                 return NULL;
 714         if (tok->type == ISL_TOKEN_IDENT) {
 715                 char *ident = strdup(tok->u.s);
 716                 isl_token_free(tok);
 717                 return ident;
 718         }
 719         isl_stream_push_token(s, tok);
 720         return NULL;
 721 }
 722
 723 int isl_stream_eat(__isl_keep isl_stream *s, int type)
 724 {
 725         struct isl_token *tok;
 726
 727         tok = isl_stream_next_token(s);
 728         if (!tok)
 729                 return -1;
 730         if (tok->type == type) {
 731                 isl_token_free(tok);
 732                 return 0;
 733         }
 734         isl_stream_error(s, tok, "expecting other token");
 735         isl_stream_push_token(s, tok);
 736         return -1;
 737 }
 738
 739 int isl_stream_is_empty(__isl_keep isl_stream *s)
 740 {
 741         struct isl_token *tok;
 742
 743         tok = isl_stream_next_token(s);
 744
 745         if (!tok)
 746                 return 1;
 747
 748         isl_stream_push_token(s, tok);
 749         return 0;
 750 }
 751
 752 static isl_stat free_keyword(void **p, void *user)
 753 {
 754         struct isl_keyword *keyword = *p;
 755
 756         free(keyword->name);
 757         free(keyword);
 758
 759         return isl_stat_ok;
 760 }
 761
 762 void isl_stream_flush_tokens(__isl_keep isl_stream *s)
 763 {
 764         int i;
 765
 766         if (!s)
 767                 return;
 768         for (i = 0; i < s->n_token; ++i)
 769                 isl_token_free(s->tokens[i]);
 770         s->n_token = 0;
 771 }
 772
 773 isl_ctx *isl_stream_get_ctx(__isl_keep isl_stream *s)
 774 {
 775         return s ? s->ctx : NULL;
 776 }
 777
 778 void isl_stream_free(__isl_take isl_stream *s)
 779 {
 780         if (!s)
 781                 return;
 782         free(s->buffer);
 783         if (s->n_token != 0) {
 784                 struct isl_token *tok = isl_stream_next_token(s);
 785                 isl_stream_error(s, tok, "unexpected token");
 786                 isl_token_free(tok);
 787         }
 788         if (s->keywords) {
 789                 isl_hash_table_foreach(s->ctx, s->keywords, &free_keyword, NULL);
 790                 isl_hash_table_free(s->ctx, s->keywords);
 791         }
 792         free(s->yaml_state);
 793         free(s->yaml_indent);
 794         isl_ctx_deref(s->ctx);
 795         free(s);
 796 }
 797
 798 /* Push "state" onto the stack of currently active YAML elements.
 799  * The caller is responsible for setting the corresponding indentation.
 800  * Return 0 on success and -1 on failure.
 801  */
 802 static int push_state(__isl_keep isl_stream *s, enum isl_yaml_state state)
 803 {
 804         if (s->yaml_size < s->yaml_depth + 1) {
 805                 int *indent;
 806                 enum isl_yaml_state *state;
 807
 808                 state = isl_realloc_array(s->ctx, s->yaml_state,
 809                                         enum isl_yaml_state, s->yaml_depth + 1);
 810                 if (!state)
 811                         return -1;
 812                 s->yaml_state = state;
 813
 814                 indent = isl_realloc_array(s->ctx, s->yaml_indent,
 815                                         int, s->yaml_depth + 1);
 816                 if (!indent)
 817                         return -1;
 818                 s->yaml_indent = indent;
 819
 820                 s->yaml_size = s->yaml_depth + 1;
 821         }
 822
 823         s->yaml_state[s->yaml_depth] = state;
 824         s->yaml_depth++;
 825
 826         return 0;
 827 }
 828
 829 /* Remove the innermost active YAML element from the stack.
 830  * Return 0 on success and -1 on failure.
 831  */
 832 static int pop_state(__isl_keep isl_stream *s)
 833 {
 834         if (!s)
 835                 return -1;
 836         if (s->yaml_depth < 1)
 837                 isl_die(isl_stream_get_ctx(s), isl_error_invalid,
 838                         "not in YAML construct", return -1);
 839
 840         s->yaml_depth--;
 841
 842         return 0;
 843 }
 844
 845 /* Set the state of the innermost active YAML element to "state".
 846  * Return 0 on success and -1 on failure.
 847  */
 848 static int update_state(__isl_keep isl_stream *s, enum isl_yaml_state state)
 849 {
 850         if (!s)
 851                 return -1;
 852         if (s->yaml_depth < 1)
 853                 isl_die(isl_stream_get_ctx(s), isl_error_invalid,
 854                         "not in YAML construct", return -1);
 855
 856         s->yaml_state[s->yaml_depth - 1] = state;
 857
 858         return 0;
 859 }
 860
 861 /* Return the state of the innermost active YAML element.
 862  * Return isl_yaml_none if we are not inside any YAML element.
 863  */
 864 static enum isl_yaml_state current_state(__isl_keep isl_stream *s)
 865 {
 866         if (!s)
 867                 return isl_yaml_none;
 868         if (s->yaml_depth < 1)
 869                 return isl_yaml_none;
 870         return s->yaml_state[s->yaml_depth - 1];
 871 }
 872
 873 /* Set the indentation of the innermost active YAML element to "indent".
 874  * If "indent" is equal to ISL_YAML_INDENT_FLOW, then this means
 875  * that the current elemient is in flow format.
 876  */
 877 static int set_yaml_indent(__isl_keep isl_stream *s, int indent)
 878 {
 879         if (s->yaml_depth < 1)
 880                 isl_die(s->ctx, isl_error_internal,
 881                         "not in YAML element", return -1);
 882
 883         s->yaml_indent[s->yaml_depth - 1] = indent;
 884
 885         return 0;
 886 }
 887
 888 /* Return the indentation of the innermost active YAML element
 889  * of -1 on error.
 890  */
 891 static int get_yaml_indent(__isl_keep isl_stream *s)
 892 {
 893         if (s->yaml_depth < 1)
 894                 isl_die(s->ctx, isl_error_internal,
 895                         "not in YAML element", return -1);
 896
 897         return s->yaml_indent[s->yaml_depth - 1];
 898 }
 899
 900 /* Move to the next state at the innermost level.
 901  * Return 1 if successful.
 902  * Return 0 if we are at the end of the innermost level.
 903  * Return -1 on error.
 904  *
 905  * If we are in state isl_yaml_mapping_key_start, then we have just
 906  * started a mapping and we are expecting a key.  If the mapping started
 907  * with a '{', then we check if the next token is a '}'.  If so,
 908  * then the mapping is empty and there is no next state at this level.
 909  * Otherwise, we assume that there is at least one key (the one from
 910  * which we derived the indentation in isl_stream_yaml_read_start_mapping.
 911  *
 912  * If we are in state isl_yaml_mapping_key, then the we expect a colon
 913  * followed by a value, so there is always a next state unless
 914  * some error occurs.
 915  *
 916  * If we are in state isl_yaml_mapping_val, then there may or may
 917  * not be a subsequent key in the same mapping.
 918  * In flow format, the next key is preceded by a comma.
 919  * In block format, the next key has the same indentation as the first key.
 920  * If the first token has a smaller indentation, then we have reached
 921  * the end of the current mapping.
 922  *
 923  * If we are in state isl_yaml_sequence_start, then we have just
 924  * started a sequence.  If the sequence started with a '[',
 925  * then we check if the next token is a ']'.  If so, then the sequence
 926  * is empty and there is no next state at this level.
 927  * Otherwise, we assume that there is at least one element in the sequence
 928  * (the one from which we derived the indentation in
 929  * isl_stream_yaml_read_start_sequence.
 930  *
 931  * If we are in state isl_yaml_sequence, then there may or may
 932  * not be a subsequent element in the same sequence.
 933  * In flow format, the next element is preceded by a comma.
 934  * In block format, the next element is introduced by a dash with
 935  * the same indentation as that of the first element.
 936  * If the first token is not a dash or if it has a smaller indentation,
 937  * then we have reached the end of the current sequence.
 938  */
 939 int isl_stream_yaml_next(__isl_keep isl_stream *s)
 940 {
 941         struct isl_token *tok;
 942         enum isl_yaml_state state;
 943         int indent;
 944
 945         state = current_state(s);
 946         if (state == isl_yaml_none)
 947                 isl_die(s->ctx, isl_error_invalid,
 948                         "not in YAML element", return -1);
 949         switch (state) {
 950         case isl_yaml_mapping_key_start:
 951                 if (get_yaml_indent(s) == ISL_YAML_INDENT_FLOW &&
 952                     isl_stream_next_token_is(s, '}'))
 953                         return 0;
 954                 if (update_state(s, isl_yaml_mapping_key) < 0)
 955                         return -1;
 956                 return 1;
 957         case isl_yaml_mapping_key:
 958                 tok = isl_stream_next_token(s);
 959                 if (!tok) {
 960                         if (s->eof)
 961                                 isl_stream_error(s, NULL, "unexpected EOF");
 962                         return -1;
 963                 }
 964                 if (tok->type == ':') {
 965                         isl_token_free(tok);
 966                         if (update_state(s, isl_yaml_mapping_val) < 0)
 967                                 return -1;
 968                         return 1;
 969                 }
 970                 isl_stream_error(s, tok, "expecting ':'");
 971                 isl_stream_push_token(s, tok);
 972                 return -1;
 973         case isl_yaml_mapping_val:
 974                 if (get_yaml_indent(s) == ISL_YAML_INDENT_FLOW) {
 975                         if (!isl_stream_eat_if_available(s, ','))
 976                                 return 0;
 977                         if (update_state(s, isl_yaml_mapping_key) < 0)
 978                                 return -1;
 979                         return 1;
 980                 }
 981                 tok = isl_stream_next_token(s);
 982                 if (!tok)
 983                         return 0;
 984                 indent = tok->col - 1;
 985                 isl_stream_push_token(s, tok);
 986                 if (indent < get_yaml_indent(s))
 987                         return 0;
 988                 if (update_state(s, isl_yaml_mapping_key) < 0)
 989                         return -1;
 990                 return 1;
 991         case isl_yaml_sequence_start:
 992                 if (get_yaml_indent(s) == ISL_YAML_INDENT_FLOW) {
 993                         if (isl_stream_next_token_is(s, ']'))
 994                                 return 0;
 995                         if (update_state(s, isl_yaml_sequence) < 0)
 996                                 return -1;
 997                         return 1;
 998                 }
 999                 tok = isl_stream_next_token(s);
1000                 if (!tok) {
1001                         if (s->eof)
1002                                 isl_stream_error(s, NULL, "unexpected EOF");
1003                         return -1;
1004                 }
1005                 if (tok->type == '-') {
1006                         isl_token_free(tok);
1007                         if (update_state(s, isl_yaml_sequence) < 0)
1008                                 return -1;
1009                         return 1;
1010                 }
1011                 isl_stream_error(s, tok, "expecting '-'");
1012                 isl_stream_push_token(s, tok);
1013                 return 0;
1014         case isl_yaml_sequence:
1015                 if (get_yaml_indent(s) == ISL_YAML_INDENT_FLOW)
1016                         return isl_stream_eat_if_available(s, ',');
1017                 tok = isl_stream_next_token(s);
1018                 if (!tok)
1019                         return 0;
1020                 indent = tok->col - 1;
1021                 if (indent < get_yaml_indent(s) || tok->type != '-') {
1022                         isl_stream_push_token(s, tok);
1023                         return 0;
1024                 }
1025                 isl_token_free(tok);
1026                 return 1;
1027         default:
1028                 isl_die(s->ctx, isl_error_internal,
1029                         "unexpected state", return 0);
1030         }
1031 }
1032
1033 /* Start reading a YAML mapping.
1034  * Return 0 on success and -1 on error.
1035  *
1036  * If the first token on the stream is a '{' then we remove this token
1037  * from the stream and keep track of the fact that the mapping
1038  * is given in flow format.
1039  * Otherwise, we assume the first token is the first key of the mapping and
1040  * keep track of its indentation, but keep the token on the stream.
1041  * In both cases, the next token we expect is the first key of the mapping.
1042  */
1043 int isl_stream_yaml_read_start_mapping(__isl_keep isl_stream *s)
1044 {
1045         struct isl_token *tok;
1046         int indent;
1047
1048         if (push_state(s, isl_yaml_mapping_key_start) < 0)
1049                 return -1;
1050
1051         tok = isl_stream_next_token(s);
1052         if (!tok) {
1053                 if (s->eof)
1054                         isl_stream_error(s, NULL, "unexpected EOF");
1055                 return -1;
1056         }
1057         if (isl_token_get_type(tok) == '{') {
1058                 isl_token_free(tok);
1059                 return set_yaml_indent(s, ISL_YAML_INDENT_FLOW);
1060         }
1061         indent = tok->col - 1;
1062         isl_stream_push_token(s, tok);
1063
1064         return set_yaml_indent(s, indent);
1065 }
1066
1067 /* Finish reading a YAML mapping.
1068  * Return 0 on success and -1 on error.
1069  *
1070  * If the mapping started with a '{', then we expect a '}' to close
1071  * the mapping.
1072  * Otherwise, we double-check that the next token (if any)
1073  * has a smaller indentation than that of the current mapping.
1074  */
1075 int isl_stream_yaml_read_end_mapping(__isl_keep isl_stream *s)
1076 {
1077         struct isl_token *tok;
1078         int indent;
1079
1080         if (get_yaml_indent(s) == ISL_YAML_INDENT_FLOW) {
1081                 if (isl_stream_eat(s, '}') < 0)
1082                         return -1;
1083                 return pop_state(s);
1084         }
1085
1086         tok = isl_stream_next_token(s);
1087         if (!tok)
1088                 return pop_state(s);
1089
1090         indent = tok->col - 1;
1091         isl_stream_push_token(s, tok);
1092
1093         if (indent >= get_yaml_indent(s))
1094                 isl_die(isl_stream_get_ctx(s), isl_error_invalid,
1095                         "mapping not finished", return -1);
1096
1097         return pop_state(s);
1098 }
1099
1100 /* Start reading a YAML sequence.
1101  * Return 0 on success and -1 on error.
1102  *
1103  * If the first token on the stream is a '[' then we remove this token
1104  * from the stream and keep track of the fact that the sequence
1105  * is given in flow format.
1106  * Otherwise, we assume the first token is the dash that introduces
1107  * the first element of the sequence and keep track of its indentation,
1108  * but keep the token on the stream.
1109  * In both cases, the next token we expect is the first element
1110  * of the sequence.
1111  */
1112 int isl_stream_yaml_read_start_sequence(__isl_keep isl_stream *s)
1113 {
1114         struct isl_token *tok;
1115         int indent;
1116
1117         if (push_state(s, isl_yaml_sequence_start) < 0)
1118                 return -1;
1119
1120         tok = isl_stream_next_token(s);
1121         if (!tok) {
1122                 if (s->eof)
1123                         isl_stream_error(s, NULL, "unexpected EOF");
1124                 return -1;
1125         }
1126         if (isl_token_get_type(tok) == '[') {
1127                 isl_token_free(tok);
1128                 return set_yaml_indent(s, ISL_YAML_INDENT_FLOW);
1129         }
1130         indent = tok->col - 1;
1131         isl_stream_push_token(s, tok);
1132
1133         return set_yaml_indent(s, indent);
1134 }
1135
1136 /* Finish reading a YAML sequence.
1137  * Return 0 on success and -1 on error.
1138  *
1139  * If the sequence started with a '[', then we expect a ']' to close
1140  * the sequence.
1141  * Otherwise, we double-check that the next token (if any)
1142  * is not a dash or that it has a smaller indentation than
1143  * that of the current sequence.
1144  */
1145 int isl_stream_yaml_read_end_sequence(__isl_keep isl_stream *s)
1146 {
1147         struct isl_token *tok;
1148         int indent;
1149         int dash;
1150
1151         if (get_yaml_indent(s) == ISL_YAML_INDENT_FLOW) {
1152                 if (isl_stream_eat(s, ']') < 0)
1153                         return -1;
1154                 return pop_state(s);
1155         }
1156
1157         tok = isl_stream_next_token(s);
1158         if (!tok)
1159                 return pop_state(s);
1160
1161         indent = tok->col - 1;
1162         dash = tok->type == '-';
1163         isl_stream_push_token(s, tok);
1164
1165         if (indent >= get_yaml_indent(s) && dash)
1166                 isl_die(isl_stream_get_ctx(s), isl_error_invalid,
1167                         "sequence not finished", return -1);
1168
1169         return pop_state(s);
1170 }