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 <strings.h> 13#include <isl/ctx.h> 14#include <isl_stream_private.h> 15#include <isl/map.h> 16#include <isl/aff.h> 17#include <isl_val_private.h> 18 19struct isl_keyword { 20 char *name; 21 enum isl_token_type type; 22}; 23 24static int same_name(const void *entry, const void *val) 25{ 26 const struct isl_keyword *keyword = (const struct isl_keyword *)entry; 27 28 return !strcmp(keyword->name, val); 29} 30 31enum isl_token_type isl_stream_register_keyword(struct isl_stream *s, 32 const char *name) 33{ 34 struct isl_hash_table_entry *entry; 35 struct isl_keyword *keyword; 36 uint32_t name_hash; 37 38 if (!s->keywords) { 39 s->keywords = isl_hash_table_alloc(s->ctx, 10); 40 if (!s->keywords) 41 return ISL_TOKEN_ERROR; 42 s->next_type = ISL_TOKEN_LAST; 43 } 44 45 name_hash = isl_hash_string(isl_hash_init(), name); 46 47 entry = isl_hash_table_find(s->ctx, s->keywords, name_hash, 48 same_name, name, 1); 49 if (!entry) 50 return ISL_TOKEN_ERROR; 51 if (entry->data) { 52 keyword = entry->data; 53 return keyword->type; 54 } 55 56 keyword = isl_calloc_type(s->ctx, struct isl_keyword); 57 if (!keyword) 58 return ISL_TOKEN_ERROR; 59 keyword->type = s->next_type++; 60 keyword->name = strdup(name); 61 if (!keyword->name) { 62 free(keyword); 63 return ISL_TOKEN_ERROR; 64 } 65 entry->data = keyword; 66 67 return keyword->type; 68} 69 70struct isl_token *isl_token_new(isl_ctx *ctx, 71 int line, int col, unsigned on_new_line) 72{ 73 struct isl_token *tok = isl_alloc_type(ctx, struct isl_token); 74 if (!tok) 75 return NULL; 76 tok->line = line; 77 tok->col = col; 78 tok->on_new_line = on_new_line; 79 tok->is_keyword = 0; 80 tok->u.s = NULL; 81 return tok; 82} 83 84/* Return the type of "tok". 85 */ 86int isl_token_get_type(struct isl_token *tok) 87{ 88 return tok ? tok->type : ISL_TOKEN_ERROR; 89} 90 91/* Given a token of type ISL_TOKEN_VALUE, return the value it represents. 92 */ 93__isl_give isl_val *isl_token_get_val(isl_ctx *ctx, struct isl_token *tok) 94{ 95 if (!tok) 96 return NULL; 97 if (tok->type != ISL_TOKEN_VALUE) 98 isl_die(ctx, isl_error_invalid, "not a value token", 99 return NULL); 100 101 return isl_val_int_from_isl_int(ctx, tok->u.v); 102} 103 104/* Given a token of type ISL_TOKEN_STRING, return the string it represents. 105 */ 106__isl_give char *isl_token_get_str(isl_ctx *ctx, struct isl_token *tok) 107{ 108 if (!tok) 109 return NULL; 110 if (tok->type != ISL_TOKEN_STRING) 111 isl_die(ctx, isl_error_invalid, "not a string token", 112 return NULL); 113 114 return strdup(tok->u.s); 115} 116 117void 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 132void isl_stream_error(struct isl_stream *s, struct isl_token *tok, char *msg) 133{ 134 int line = tok ? tok->line : s->line; 135 int col = tok ? tok->col : s->col; 136 fprintf(stderr, "syntax error (%d, %d): %s\n", line, col, msg); 137 if (tok) { 138 if (tok->type < 256) 139 fprintf(stderr, "got '%c'\n", tok->type); 140 else if (tok->type == ISL_TOKEN_IDENT) 141 fprintf(stderr, "got ident '%s'\n", tok->u.s); 142 else if (tok->is_keyword) 143 fprintf(stderr, "got keyword '%s'\n", tok->u.s); 144 else if (tok->type == ISL_TOKEN_VALUE) { 145 fprintf(stderr, "got value '"); 146 isl_int_print(stderr, tok->u.v, 0); 147 fprintf(stderr, "'\n"); 148 } else if (tok->type == ISL_TOKEN_MAP) { 149 isl_printer *p; 150 fprintf(stderr, "got map '"); 151 p = isl_printer_to_file(s->ctx, stderr); 152 p = isl_printer_print_map(p, tok->u.map); 153 isl_printer_free(p); 154 fprintf(stderr, "'\n"); 155 } else if (tok->type == ISL_TOKEN_AFF) { 156 isl_printer *p; 157 fprintf(stderr, "got affine expression '"); 158 p = isl_printer_to_file(s->ctx, stderr); 159 p = isl_printer_print_pw_aff(p, tok->u.pwaff); 160 isl_printer_free(p); 161 fprintf(stderr, "'\n"); 162 } else if (tok->u.s) 163 fprintf(stderr, "got token '%s'\n", tok->u.s); 164 else 165 fprintf(stderr, "got token type %d\n", tok->type); 166 } 167} 168 169static struct isl_stream* isl_stream_new(struct isl_ctx *ctx) 170{ 171 int i; 172 struct isl_stream *s = isl_alloc_type(ctx, struct isl_stream); 173 if (!s) 174 return NULL; 175 s->ctx = ctx; 176 isl_ctx_ref(s->ctx); 177 s->file = NULL; 178 s->str = NULL; 179 s->len = 0; 180 s->line = 1; 181 s->col = 0; 182 s->eof = 0; 183 s->c = -1; 184 s->n_un = 0; 185 for (i = 0; i < 5; ++i) 186 s->tokens[i] = NULL; 187 s->n_token = 0; 188 s->keywords = NULL; 189 s->size = 256; 190 s->buffer = isl_alloc_array(ctx, char, s->size); 191 if (!s->buffer) 192 goto error; 193 return s; 194error: 195 isl_stream_free(s); 196 return NULL; 197} 198 199struct isl_stream* isl_stream_new_file(struct isl_ctx *ctx, FILE *file) 200{ 201 struct isl_stream *s = isl_stream_new(ctx); 202 if (!s) 203 return NULL; 204 s->file = file; 205 return s; 206} 207 208struct isl_stream* isl_stream_new_str(struct isl_ctx *ctx, const char *str) 209{ 210 struct isl_stream *s; 211 if (!str) 212 return NULL; 213 s = isl_stream_new(ctx); 214 if (!s) 215 return NULL; 216 s->str = str; 217 return s; 218} 219 220static int stream_getc(struct isl_stream *s) 221{ 222 int c; 223 if (s->eof) 224 return -1; 225 if (s->n_un) 226 return s->c = s->un[--s->n_un]; 227 if (s->file) 228 c = fgetc(s->file); 229 else { 230 c = *s->str++; 231 if (c == '\0') 232 c = -1; 233 } 234 if (c == -1) 235 s->eof = 1; 236 if (!s->eof) { 237 if (s->c == '\n') { 238 s->line++; 239 s->col = 0; 240 } else 241 s->col++; 242 } 243 s->c = c; 244 return c; 245} 246 247static void isl_stream_ungetc(struct isl_stream *s, int c) 248{ 249 isl_assert(s->ctx, s->n_un < 5, return); 250 s->un[s->n_un++] = c; 251 s->c = -1; 252} 253 254static int isl_stream_getc(struct isl_stream *s) 255{ 256 int c; 257 258 do { 259 c = stream_getc(s); 260 if (c != '\\') 261 return c; 262 c = stream_getc(s); 263 } while (c == '\n'); 264 265 isl_stream_ungetc(s, c); 266 267 return '\\'; 268} 269 270static int isl_stream_push_char(struct isl_stream *s, int c) 271{ 272 if (s->len >= s->size) { 273 char *buffer; 274 s->size = (3*s->size)/2; 275 buffer = isl_realloc_array(s->ctx, s->buffer, char, s->size); 276 if (!buffer) 277 return -1; 278 s->buffer = buffer; 279 } 280 s->buffer[s->len++] = c; 281 return 0; 282} 283 284void isl_stream_push_token(struct isl_stream *s, struct isl_token *tok) 285{ 286 isl_assert(s->ctx, s->n_token < 5, return); 287 s->tokens[s->n_token++] = tok; 288} 289 290static enum isl_token_type check_keywords(struct isl_stream *s) 291{ 292 struct isl_hash_table_entry *entry; 293 struct isl_keyword *keyword; 294 uint32_t name_hash; 295 296 if (!strcasecmp(s->buffer, "exists")) 297 return ISL_TOKEN_EXISTS; 298 if (!strcasecmp(s->buffer, "and")) 299 return ISL_TOKEN_AND; 300 if (!strcasecmp(s->buffer, "or")) 301 return ISL_TOKEN_OR; 302 if (!strcasecmp(s->buffer, "implies")) 303 return ISL_TOKEN_IMPLIES; 304 if (!strcasecmp(s->buffer, "not")) 305 return ISL_TOKEN_NOT; 306 if (!strcasecmp(s->buffer, "infty")) 307 return ISL_TOKEN_INFTY; 308 if (!strcasecmp(s->buffer, "infinity")) 309 return ISL_TOKEN_INFTY; 310 if (!strcasecmp(s->buffer, "NaN")) 311 return ISL_TOKEN_NAN; 312 if (!strcasecmp(s->buffer, "min")) 313 return ISL_TOKEN_MIN; 314 if (!strcasecmp(s->buffer, "max")) 315 return ISL_TOKEN_MAX; 316 if (!strcasecmp(s->buffer, "rat")) 317 return ISL_TOKEN_RAT; 318 if (!strcasecmp(s->buffer, "true")) 319 return ISL_TOKEN_TRUE; 320 if (!strcasecmp(s->buffer, "false")) 321 return ISL_TOKEN_FALSE; 322 if (!strcasecmp(s->buffer, "ceild")) 323 return ISL_TOKEN_CEILD; 324 if (!strcasecmp(s->buffer, "floord")) 325 return ISL_TOKEN_FLOORD; 326 if (!strcasecmp(s->buffer, "mod")) 327 return ISL_TOKEN_MOD; 328 if (!strcasecmp(s->buffer, "ceil")) 329 return ISL_TOKEN_CEIL; 330 if (!strcasecmp(s->buffer, "floor")) 331 return ISL_TOKEN_FLOOR; 332 333 if (!s->keywords) 334 return ISL_TOKEN_IDENT; 335 336 name_hash = isl_hash_string(isl_hash_init(), s->buffer); 337 entry = isl_hash_table_find(s->ctx, s->keywords, name_hash, same_name, 338 s->buffer, 0); 339 if (entry) { 340 keyword = entry->data; 341 return keyword->type; 342 } 343 344 return ISL_TOKEN_IDENT; 345} 346 347int isl_stream_skip_line(struct isl_stream *s) 348{ 349 int c; 350 351 while ((c = isl_stream_getc(s)) != -1 && c != '\n') 352 /* nothing */ 353 ; 354 355 return c == -1 ? -1 : 0; 356} 357 358static struct isl_token *next_token(struct isl_stream *s, int same_line) 359{ 360 int c; 361 struct isl_token *tok = NULL; 362 int line, col; 363 int old_line = s->line; 364 365 if (s->n_token) { 366 if (same_line && s->tokens[s->n_token - 1]->on_new_line) 367 return NULL; 368 return s->tokens[--s->n_token]; 369 } 370 371 if (same_line && s->c == '\n') 372 return NULL; 373 374 s->len = 0; 375 376 /* skip spaces and comment lines */ 377 while ((c = isl_stream_getc(s)) != -1) { 378 if (c == '#') { 379 if (isl_stream_skip_line(s) < 0) 380 break; 381 c = '\n'; 382 if (same_line) 383 break; 384 } else if (!isspace(c) || (same_line && c == '\n')) 385 break; 386 } 387 388 line = s->line; 389 col = s->col; 390 391 if (c == -1 || (same_line && c == '\n')) 392 return NULL; 393 if (c == '(' || 394 c == ')' || 395 c == '+' || 396 c == '*' || 397 c == '%' || 398 c == '?' || 399 c == '^' || 400 c == '@' || 401 c == '$' || 402 c == ',' || 403 c == '.' || 404 c == ';' || 405 c == '[' || 406 c == ']' || 407 c == '{' || 408 c == '}') { 409 tok = isl_token_new(s->ctx, line, col, old_line != line); 410 if (!tok) 411 return NULL; 412 tok->type = (enum isl_token_type)c; 413 return tok; 414 } 415 if (c == '-') { 416 int c; 417 if ((c = isl_stream_getc(s)) == '>') { 418 tok = isl_token_new(s->ctx, line, col, old_line != line); 419 if (!tok) 420 return NULL; 421 tok->u.s = strdup("->"); 422 tok->type = ISL_TOKEN_TO; 423 return tok; 424 } 425 if (c != -1) 426 isl_stream_ungetc(s, c); 427 if (!isdigit(c)) { 428 tok = isl_token_new(s->ctx, line, col, old_line != line); 429 if (!tok) 430 return NULL; 431 tok->type = (enum isl_token_type) '-'; 432 return tok; 433 } 434 } 435 if (c == '-' || isdigit(c)) { 436 int minus = c == '-'; 437 tok = isl_token_new(s->ctx, line, col, old_line != line); 438 if (!tok) 439 return NULL; 440 tok->type = ISL_TOKEN_VALUE; 441 isl_int_init(tok->u.v); 442 if (isl_stream_push_char(s, c)) 443 goto error; 444 while ((c = isl_stream_getc(s)) != -1 && isdigit(c)) 445 if (isl_stream_push_char(s, c)) 446 goto error; 447 if (c != -1) 448 isl_stream_ungetc(s, c); 449 isl_stream_push_char(s, '\0'); 450 isl_int_read(tok->u.v, s->buffer); 451 if (minus && isl_int_is_zero(tok->u.v)) { 452 tok->col++; 453 tok->on_new_line = 0; 454 isl_stream_push_token(s, tok); 455 tok = isl_token_new(s->ctx, line, col, old_line != line); 456 if (!tok) 457 return NULL; 458 tok->type = (enum isl_token_type) '-'; 459 } 460 return tok; 461 } 462 if (isalpha(c) || c == '_') { 463 tok = isl_token_new(s->ctx, line, col, old_line != line); 464 if (!tok) 465 return NULL; 466 isl_stream_push_char(s, c); 467 while ((c = isl_stream_getc(s)) != -1 && 468 (isalnum(c) || c == '_')) 469 isl_stream_push_char(s, c); 470 if (c != -1) 471 isl_stream_ungetc(s, c); 472 while ((c = isl_stream_getc(s)) != -1 && c == '\'') 473 isl_stream_push_char(s, c); 474 if (c != -1) 475 isl_stream_ungetc(s, c); 476 isl_stream_push_char(s, '\0'); 477 tok->type = check_keywords(s); 478 if (tok->type != ISL_TOKEN_IDENT) 479 tok->is_keyword = 1; 480 tok->u.s = strdup(s->buffer); 481 if (!tok->u.s) 482 goto error; 483 return tok; 484 } 485 if (c == '"') { 486 tok = isl_token_new(s->ctx, line, col, old_line != line); 487 if (!tok) 488 return NULL; 489 tok->type = ISL_TOKEN_STRING; 490 tok->u.s = NULL; 491 while ((c = isl_stream_getc(s)) != -1 && c != '"' && c != '\n') 492 isl_stream_push_char(s, c); 493 if (c != '"') { 494 isl_stream_error(s, NULL, "unterminated string"); 495 goto error; 496 } 497 isl_stream_push_char(s, '\0'); 498 tok->u.s = strdup(s->buffer); 499 return tok; 500 } 501 if (c == '=') { 502 int c; 503 tok = isl_token_new(s->ctx, line, col, old_line != line); 504 if (!tok) 505 return NULL; 506 if ((c = isl_stream_getc(s)) == '=') { 507 tok->u.s = strdup("=="); 508 tok->type = ISL_TOKEN_EQ_EQ; 509 return tok; 510 } 511 if (c != -1) 512 isl_stream_ungetc(s, c); 513 tok->type = (enum isl_token_type) '='; 514 return tok; 515 } 516 if (c == ':') { 517 int c; 518 tok = isl_token_new(s->ctx, line, col, old_line != line); 519 if (!tok) 520 return NULL; 521 if ((c = isl_stream_getc(s)) == '=') { 522 tok->u.s = strdup(":="); 523 tok->type = ISL_TOKEN_DEF; 524 return tok; 525 } 526 if (c != -1) 527 isl_stream_ungetc(s, c); 528 tok->type = (enum isl_token_type) ':'; 529 return tok; 530 } 531 if (c == '>') { 532 int c; 533 tok = isl_token_new(s->ctx, line, col, old_line != line); 534 if (!tok) 535 return NULL; 536 if ((c = isl_stream_getc(s)) == '=') { 537 tok->u.s = strdup(">="); 538 tok->type = ISL_TOKEN_GE; 539 return tok; 540 } else if (c == '>') { 541 if ((c = isl_stream_getc(s)) == '=') { 542 tok->u.s = strdup(">>="); 543 tok->type = ISL_TOKEN_LEX_GE; 544 return tok; 545 } 546 tok->u.s = strdup(">>"); 547 tok->type = ISL_TOKEN_LEX_GT; 548 } else { 549 tok->u.s = strdup(">"); 550 tok->type = ISL_TOKEN_GT; 551 } 552 if (c != -1) 553 isl_stream_ungetc(s, c); 554 return tok; 555 } 556 if (c == '<') { 557 int c; 558 tok = isl_token_new(s->ctx, line, col, old_line != line); 559 if (!tok) 560 return NULL; 561 if ((c = isl_stream_getc(s)) == '=') { 562 tok->u.s = strdup("<="); 563 tok->type = ISL_TOKEN_LE; 564 return tok; 565 } else if (c == '<') { 566 if ((c = isl_stream_getc(s)) == '=') { 567 tok->u.s = strdup("<<="); 568 tok->type = ISL_TOKEN_LEX_LE; 569 return tok; 570 } 571 tok->u.s = strdup("<<"); 572 tok->type = ISL_TOKEN_LEX_LT; 573 } else { 574 tok->u.s = strdup("<"); 575 tok->type = ISL_TOKEN_LT; 576 } 577 if (c != -1) 578 isl_stream_ungetc(s, c); 579 return tok; 580 } 581 if (c == '&') { 582 tok = isl_token_new(s->ctx, line, col, old_line != line); 583 if (!tok) 584 return NULL; 585 tok->type = ISL_TOKEN_AND; 586 if ((c = isl_stream_getc(s)) != '&' && c != -1) { 587 tok->u.s = strdup("&"); 588 isl_stream_ungetc(s, c); 589 } else 590 tok->u.s = strdup("&&"); 591 return tok; 592 } 593 if (c == '|') { 594 tok = isl_token_new(s->ctx, line, col, old_line != line); 595 if (!tok) 596 return NULL; 597 tok->type = ISL_TOKEN_OR; 598 if ((c = isl_stream_getc(s)) != '|' && c != -1) { 599 tok->u.s = strdup("|"); 600 isl_stream_ungetc(s, c); 601 } else 602 tok->u.s = strdup("||"); 603 return tok; 604 } 605 if (c == '/') { 606 tok = isl_token_new(s->ctx, line, col, old_line != line); 607 if (!tok) 608 return NULL; 609 if ((c = isl_stream_getc(s)) != '\\' && c != -1) { 610 tok->type = (enum isl_token_type) '/'; 611 isl_stream_ungetc(s, c); 612 } else { 613 tok->u.s = strdup("/\\"); 614 tok->type = ISL_TOKEN_AND; 615 } 616 return tok; 617 } 618 if (c == '\\') { 619 tok = isl_token_new(s->ctx, line, col, old_line != line); 620 if (!tok) 621 return NULL; 622 if ((c = isl_stream_getc(s)) != '/' && c != -1) { 623 tok->type = (enum isl_token_type) '\\'; 624 isl_stream_ungetc(s, c); 625 } else { 626 tok->u.s = strdup("\\/"); 627 tok->type = ISL_TOKEN_OR; 628 } 629 return tok; 630 } 631 if (c == '!') { 632 tok = isl_token_new(s->ctx, line, col, old_line != line); 633 if (!tok) 634 return NULL; 635 if ((c = isl_stream_getc(s)) == '=') { 636 tok->u.s = strdup("!="); 637 tok->type = ISL_TOKEN_NE; 638 return tok; 639 } else { 640 tok->type = ISL_TOKEN_NOT; 641 tok->u.s = strdup("!"); 642 } 643 if (c != -1) 644 isl_stream_ungetc(s, c); 645 return tok; 646 } 647 648 tok = isl_token_new(s->ctx, line, col, old_line != line); 649 if (!tok) 650 return NULL; 651 tok->type = ISL_TOKEN_UNKNOWN; 652 return tok; 653error: 654 isl_token_free(tok); 655 return NULL; 656} 657 658struct isl_token *isl_stream_next_token(struct isl_stream *s) 659{ 660 return next_token(s, 0); 661} 662 663struct isl_token *isl_stream_next_token_on_same_line(struct isl_stream *s) 664{ 665 return next_token(s, 1); 666} 667 668int isl_stream_eat_if_available(struct isl_stream *s, int type) 669{ 670 struct isl_token *tok; 671 672 tok = isl_stream_next_token(s); 673 if (!tok) 674 return 0; 675 if (tok->type == type) { 676 isl_token_free(tok); 677 return 1; 678 } 679 isl_stream_push_token(s, tok); 680 return 0; 681} 682 683int isl_stream_next_token_is(struct isl_stream *s, int type) 684{ 685 struct isl_token *tok; 686 int r; 687 688 tok = isl_stream_next_token(s); 689 if (!tok) 690 return 0; 691 r = tok->type == type; 692 isl_stream_push_token(s, tok); 693 return r; 694} 695 696char *isl_stream_read_ident_if_available(struct isl_stream *s) 697{ 698 struct isl_token *tok; 699 700 tok = isl_stream_next_token(s); 701 if (!tok) 702 return NULL; 703 if (tok->type == ISL_TOKEN_IDENT) { 704 char *ident = strdup(tok->u.s); 705 isl_token_free(tok); 706 return ident; 707 } 708 isl_stream_push_token(s, tok); 709 return NULL; 710} 711 712int isl_stream_eat(struct isl_stream *s, int type) 713{ 714 struct isl_token *tok; 715 716 tok = isl_stream_next_token(s); 717 if (!tok) 718 return -1; 719 if (tok->type == type) { 720 isl_token_free(tok); 721 return 0; 722 } 723 isl_stream_error(s, tok, "expecting other token"); 724 isl_stream_push_token(s, tok); 725 return -1; 726} 727 728int isl_stream_is_empty(struct isl_stream *s) 729{ 730 struct isl_token *tok; 731 732 tok = isl_stream_next_token(s); 733 734 if (!tok) 735 return 1; 736 737 isl_stream_push_token(s, tok); 738 return 0; 739} 740 741static int free_keyword(void **p, void *user) 742{ 743 struct isl_keyword *keyword = *p; 744 745 free(keyword->name); 746 free(keyword); 747 748 return 0; 749} 750 751void isl_stream_flush_tokens(struct isl_stream *s) 752{ 753 int i; 754 755 if (!s) 756 return; 757 for (i = 0; i < s->n_token; ++i) 758 isl_token_free(s->tokens[i]); 759 s->n_token = 0; 760} 761 762void isl_stream_free(struct isl_stream *s) 763{ 764 if (!s) 765 return; 766 free(s->buffer); 767 if (s->n_token != 0) { 768 struct isl_token *tok = isl_stream_next_token(s); 769 isl_stream_error(s, tok, "unexpected token"); 770 isl_token_free(tok); 771 } 772 if (s->keywords) { 773 isl_hash_table_foreach(s->ctx, s->keywords, &free_keyword, NULL); 774 isl_hash_table_free(s->ctx, s->keywords); 775 } 776 isl_ctx_deref(s->ctx); 777 free(s); 778} 779