1 /* 2 * This is a really stupid C tokenizer. It doesn't do any include 3 * files or anything complex at all. That's the preprocessor. 4 * 5 * Copyright (C) 2003 Transmeta Corp. 6 * 2003 Linus Torvalds 7 * 8 * Permission is hereby granted, free of charge, to any person obtaining a copy 9 * of this software and associated documentation files (the "Software"), to deal 10 * in the Software without restriction, including without limitation the rights 11 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 12 * copies of the Software, and to permit persons to whom the Software is 13 * furnished to do so, subject to the following conditions: 14 * 15 * The above copyright notice and this permission notice shall be included in 16 * all copies or substantial portions of the Software. 17 * 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 21 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 22 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 23 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 24 * THE SOFTWARE. 25 */ 26 #include <stdio.h> 27 #include <stdlib.h> 28 #include <stdarg.h> 29 #include <stddef.h> 30 #include <string.h> 31 #include <ctype.h> 32 #include <unistd.h> 33 #include <stdint.h> 34 35 #include "lib.h" 36 #include "allocate.h" 37 #include "token.h" 38 #include "symbol.h" 39 40 #define EOF (-1) 41 42 int input_stream_nr = 0; 43 struct stream *input_streams; 44 static int input_streams_allocated; 45 unsigned int tabstop = 8; 46 int no_lineno = 0; 47 48 #define BUFSIZE (8192) 49 50 typedef struct { 51 int fd, offset, size; 52 int pos, line, nr; 53 int newline, whitespace; 54 struct token **tokenlist; 55 struct token *token; 56 unsigned char *buffer; 57 } stream_t; 58 59 const char *stream_name(int stream) 60 { 61 if (stream < 0 || stream > input_stream_nr) 62 return "<bad stream>"; 63 return input_streams[stream].name; 64 } 65 66 static struct position stream_pos(stream_t *stream) 67 { 68 struct position pos; 69 pos.type = 0; 70 pos.stream = stream->nr; 71 pos.newline = stream->newline; 72 pos.whitespace = stream->whitespace; 73 pos.pos = stream->pos; 74 75 pos.line = stream->line; 76 if (no_lineno) 77 pos.line = 123456; 78 79 pos.noexpand = 0; 80 return pos; 81 } 82 83 const char *show_special(int val) 84 { 85 static char buffer[4]; 86 87 buffer[0] = val; 88 buffer[1] = 0; 89 if (val >= SPECIAL_BASE) 90 strcpy(buffer, (char *) combinations[val - SPECIAL_BASE]); 91 return buffer; 92 } 93 94 const char *show_ident(const struct ident *ident) 95 { 96 static char buffer[256]; 97 if (!ident) 98 return "<noident>"; 99 sprintf(buffer, "%.*s", ident->len, ident->name); 100 return buffer; 101 } 102 103 static char *charstr(char *ptr, unsigned char c, unsigned char escape, unsigned char next) 104 { 105 if (isprint(c)) { 106 if (c == escape || c == '\\') 107 *ptr++ = '\\'; 108 *ptr++ = c; 109 return ptr; 110 } 111 *ptr++ = '\\'; 112 switch (c) { 113 case '\n': 114 *ptr++ = 'n'; 115 return ptr; 116 case '\t': 117 *ptr++ = 't'; 118 return ptr; 119 } 120 if (!isdigit(next)) 121 return ptr + sprintf(ptr, "%o", c); 122 123 return ptr + sprintf(ptr, "%03o", c); 124 } 125 126 const char *show_string(const struct string *string) 127 { 128 static char buffer[4 * MAX_STRING + 3]; 129 char *ptr; 130 int i; 131 132 if (!string->length) 133 return "<bad_string>"; 134 ptr = buffer; 135 *ptr++ = '"'; 136 for (i = 0; i < string->length-1; i++) { 137 const char *p = string->data + i; 138 ptr = charstr(ptr, p[0], '"', p[1]); 139 } 140 *ptr++ = '"'; 141 *ptr = '\0'; 142 return buffer; 143 } 144 145 static const char *show_char(const char *s, size_t len, char prefix, char delim) 146 { 147 static char buffer[MAX_STRING + 4]; 148 char *p = buffer; 149 if (prefix) 150 *p++ = prefix; 151 *p++ = delim; 152 memcpy(p, s, len); 153 p += len; 154 *p++ = delim; 155 *p++ = '\0'; 156 return buffer; 157 } 158 159 static const char *quote_char(const char *s, size_t len, char prefix, char delim) 160 { 161 static char buffer[2*MAX_STRING + 6]; 162 size_t i; 163 char *p = buffer; 164 if (prefix) 165 *p++ = prefix; 166 if (delim == '"') 167 *p++ = '\\'; 168 *p++ = delim; 169 for (i = 0; i < len; i++) { 170 if (s[i] == '"' || s[i] == '\\') 171 *p++ = '\\'; 172 *p++ = s[i]; 173 } 174 if (delim == '"') 175 *p++ = '\\'; 176 *p++ = delim; 177 *p++ = '\0'; 178 return buffer; 179 } 180 181 const char *show_token(const struct token *token) 182 { 183 static char buffer[256]; 184 185 if (!token) 186 return "<no token>"; 187 switch (token_type(token)) { 188 case TOKEN_ERROR: 189 return "syntax error"; 190 191 case TOKEN_EOF: 192 return "end-of-input"; 193 194 case TOKEN_IDENT: 195 return show_ident(token->ident); 196 197 case TOKEN_NUMBER: 198 return token->number; 199 200 case TOKEN_SPECIAL: 201 return show_special(token->special); 202 203 case TOKEN_CHAR: 204 return show_char(token->string->data, 205 token->string->length - 1, 0, '\''); 206 case TOKEN_CHAR_EMBEDDED_0 ... TOKEN_CHAR_EMBEDDED_3: 207 return show_char(token->embedded, 208 token_type(token) - TOKEN_CHAR, 0, '\''); 209 case TOKEN_WIDE_CHAR: 210 return show_char(token->string->data, 211 token->string->length - 1, 'L', '\''); 212 case TOKEN_WIDE_CHAR_EMBEDDED_0 ... TOKEN_WIDE_CHAR_EMBEDDED_3: 213 return show_char(token->embedded, 214 token_type(token) - TOKEN_WIDE_CHAR, 'L', '\''); 215 case TOKEN_STRING: 216 return show_char(token->string->data, 217 token->string->length - 1, 0, '"'); 218 case TOKEN_WIDE_STRING: 219 return show_char(token->string->data, 220 token->string->length - 1, 'L', '"'); 221 222 case TOKEN_STREAMBEGIN: 223 sprintf(buffer, "<beginning of '%s'>", stream_name(token->pos.stream)); 224 return buffer; 225 226 case TOKEN_STREAMEND: 227 sprintf(buffer, "<end of '%s'>", stream_name(token->pos.stream)); 228 return buffer; 229 230 case TOKEN_UNTAINT: 231 sprintf(buffer, "<untaint>"); 232 return buffer; 233 234 case TOKEN_ARG_COUNT: 235 sprintf(buffer, "<argcnt>"); 236 return buffer; 237 238 default: 239 sprintf(buffer, "unhandled token type '%d' ", token_type(token)); 240 return buffer; 241 } 242 } 243 244 const char *quote_token(const struct token *token) 245 { 246 static char buffer[256]; 247 248 switch (token_type(token)) { 249 case TOKEN_ERROR: 250 return "syntax error"; 251 252 case TOKEN_IDENT: 253 return show_ident(token->ident); 254 255 case TOKEN_NUMBER: 256 return token->number; 257 258 case TOKEN_SPECIAL: 259 return show_special(token->special); 260 261 case TOKEN_CHAR: 262 return quote_char(token->string->data, 263 token->string->length - 1, 0, '\''); 264 case TOKEN_CHAR_EMBEDDED_0 ... TOKEN_CHAR_EMBEDDED_3: 265 return quote_char(token->embedded, 266 token_type(token) - TOKEN_CHAR, 0, '\''); 267 case TOKEN_WIDE_CHAR: 268 return quote_char(token->string->data, 269 token->string->length - 1, 'L', '\''); 270 case TOKEN_WIDE_CHAR_EMBEDDED_0 ... TOKEN_WIDE_CHAR_EMBEDDED_3: 271 return quote_char(token->embedded, 272 token_type(token) - TOKEN_WIDE_CHAR, 'L', '\''); 273 case TOKEN_STRING: 274 return quote_char(token->string->data, 275 token->string->length - 1, 0, '"'); 276 case TOKEN_WIDE_STRING: 277 return quote_char(token->string->data, 278 token->string->length - 1, 'L', '"'); 279 default: 280 sprintf(buffer, "unhandled token type '%d' ", token_type(token)); 281 return buffer; 282 } 283 } 284 285 #define HASHED_INPUT_BITS (6) 286 #define HASHED_INPUT (1 << HASHED_INPUT_BITS) 287 #define HASH_PRIME 0x9e370001UL 288 289 static int input_stream_hashes[HASHED_INPUT] = { [0 ... HASHED_INPUT-1] = -1 }; 290 291 int *hash_stream(const char *name) 292 { 293 uint32_t hash = 0; 294 unsigned char c; 295 296 while ((c = *name++) != 0) 297 hash = (hash + (c << 4) + (c >> 4)) * 11; 298 299 hash *= HASH_PRIME; 300 hash >>= 32 - HASHED_INPUT_BITS; 301 return input_stream_hashes + hash; 302 } 303 304 int init_stream(const char *name, int fd, const char **next_path) 305 { 306 int stream = input_stream_nr, *hash; 307 struct stream *current; 308 309 if (stream >= input_streams_allocated) { 310 int newalloc = stream * 4 / 3 + 10; 311 input_streams = realloc(input_streams, newalloc * sizeof(struct stream)); 312 if (!input_streams) 313 die("Unable to allocate more streams space"); 314 input_streams_allocated = newalloc; 315 } 316 current = input_streams + stream; 317 memset(current, 0, sizeof(*current)); 318 current->name = name; 319 current->fd = fd; 320 current->next_path = next_path; 321 current->path = NULL; 322 current->constant = CONSTANT_FILE_MAYBE; 323 input_stream_nr = stream+1; 324 hash = hash_stream(name); 325 current->next_stream = *hash; 326 *hash = stream; 327 return stream; 328 } 329 330 static struct token * alloc_token(stream_t *stream) 331 { 332 struct token *token = __alloc_token(0); 333 token->pos = stream_pos(stream); 334 return token; 335 } 336 337 /* 338 * Argh... That was surprisingly messy - handling '\r' complicates the 339 * things a _lot_. 340 */ 341 static int nextchar_slow(stream_t *stream) 342 { 343 int offset = stream->offset; 344 int size = stream->size; 345 int c; 346 int spliced = 0, had_cr, had_backslash; 347 348 restart: 349 had_cr = had_backslash = 0; 350 351 repeat: 352 if (offset >= size) { 353 if (stream->fd < 0) 354 goto got_eof; 355 size = read(stream->fd, stream->buffer, BUFSIZE); 356 if (size <= 0) 357 goto got_eof; 358 stream->size = size; 359 stream->offset = offset = 0; 360 } 361 362 c = stream->buffer[offset++]; 363 if (had_cr) 364 goto check_lf; 365 366 if (c == '\r') { 367 had_cr = 1; 368 goto repeat; 369 } 370 371 norm: 372 if (!had_backslash) { 373 switch (c) { 374 case '\t': 375 stream->pos += tabstop - stream->pos % tabstop; 376 break; 377 case '\n': 378 stream->line++; 379 stream->pos = 0; 380 stream->newline = 1; 381 break; 382 case '\\': 383 had_backslash = 1; 384 stream->pos++; 385 goto repeat; 386 default: 387 stream->pos++; 388 } 389 } else { 390 if (c == '\n') { 391 stream->line++; 392 stream->pos = 0; 393 spliced = 1; 394 goto restart; 395 } 396 offset--; 397 c = '\\'; 398 } 399 out: 400 stream->offset = offset; 401 402 return c; 403 404 check_lf: 405 if (c != '\n') 406 offset--; 407 c = '\n'; 408 goto norm; 409 410 got_eof: 411 if (had_backslash) { 412 c = '\\'; 413 goto out; 414 } 415 if (stream->pos) 416 warning(stream_pos(stream), "no newline at end of file"); 417 else if (spliced) 418 warning(stream_pos(stream), "backslash-newline at end of file"); 419 return EOF; 420 } 421 422 /* 423 * We want that as light as possible while covering all normal cases. 424 * Slow path (including the logics with line-splicing and EOF sanity 425 * checks) is in nextchar_slow(). 426 */ 427 static inline int nextchar(stream_t *stream) 428 { 429 int offset = stream->offset; 430 431 if (offset < stream->size) { 432 int c = stream->buffer[offset++]; 433 static const char special[256] = { 434 ['\t'] = 1, ['\r'] = 1, ['\n'] = 1, ['\\'] = 1 435 }; 436 if (!special[c]) { 437 stream->offset = offset; 438 stream->pos++; 439 return c; 440 } 441 } 442 return nextchar_slow(stream); 443 } 444 445 struct token eof_token_entry; 446 447 static struct token *mark_eof(stream_t *stream) 448 { 449 struct token *end; 450 451 end = alloc_token(stream); 452 token_type(end) = TOKEN_STREAMEND; 453 end->pos.newline = 1; 454 455 eof_token_entry.next = &eof_token_entry; 456 eof_token_entry.pos.newline = 1; 457 458 end->next = &eof_token_entry; 459 *stream->tokenlist = end; 460 stream->tokenlist = NULL; 461 return end; 462 } 463 464 static void add_token(stream_t *stream) 465 { 466 struct token *token = stream->token; 467 468 stream->token = NULL; 469 token->next = NULL; 470 *stream->tokenlist = token; 471 stream->tokenlist = &token->next; 472 } 473 474 static void drop_token(stream_t *stream) 475 { 476 stream->newline |= stream->token->pos.newline; 477 stream->whitespace |= stream->token->pos.whitespace; 478 stream->token = NULL; 479 } 480 481 enum { 482 Letter = 1, 483 Digit = 2, 484 Hex = 4, 485 Exp = 8, 486 Dot = 16, 487 ValidSecond = 32, 488 Quote = 64, 489 }; 490 491 static const long cclass[257] = { 492 ['0' + 1 ... '7' + 1] = Digit | Hex, /* \<octal> */ 493 ['8' + 1 ... '9' + 1] = Digit | Hex, 494 ['A' + 1 ... 'D' + 1] = Letter | Hex, 495 ['E' + 1] = Letter | Hex | Exp, /* E<exp> */ 496 ['F' + 1] = Letter | Hex, 497 ['G' + 1 ... 'O' + 1] = Letter, 498 ['P' + 1] = Letter | Exp, /* P<exp> */ 499 ['Q' + 1 ... 'Z' + 1] = Letter, 500 ['a' + 1 ... 'b' + 1] = Letter | Hex, /* \a, \b */ 501 ['c' + 1 ... 'd' + 1] = Letter | Hex, 502 ['e' + 1] = Letter | Hex | Exp,/* \e, e<exp> */ 503 ['f' + 1] = Letter | Hex, /* \f */ 504 ['g' + 1 ... 'm' + 1] = Letter, 505 ['n' + 1] = Letter, /* \n */ 506 ['o' + 1] = Letter, 507 ['p' + 1] = Letter | Exp, /* p<exp> */ 508 ['q' + 1] = Letter, 509 ['r' + 1] = Letter, /* \r */ 510 ['s' + 1] = Letter, 511 ['t' + 1] = Letter, /* \t */ 512 ['u' + 1] = Letter, 513 ['v' + 1] = Letter, /* \v */ 514 ['w' + 1] = Letter, 515 ['x' + 1] = Letter, /* \x<hex> */ 516 ['y' + 1 ... 'z' + 1] = Letter, 517 ['_' + 1] = Letter, 518 ['.' + 1] = Dot | ValidSecond, 519 ['=' + 1] = ValidSecond, 520 ['+' + 1] = ValidSecond, 521 ['-' + 1] = ValidSecond, 522 ['>' + 1] = ValidSecond, 523 ['<' + 1] = ValidSecond, 524 ['&' + 1] = ValidSecond, 525 ['|' + 1] = ValidSecond, 526 ['#' + 1] = ValidSecond, 527 ['\'' + 1] = Quote, 528 ['"' + 1] = Quote, 529 }; 530 531 /* 532 * pp-number: 533 * digit 534 * . digit 535 * pp-number digit 536 * pp-number identifier-nodigit 537 * pp-number e sign 538 * pp-number E sign 539 * pp-number p sign 540 * pp-number P sign 541 * pp-number . 542 */ 543 static int get_one_number(int c, int next, stream_t *stream) 544 { 545 struct token *token; 546 static char buffer[4095]; 547 char *p = buffer, *buf, *buffer_end = buffer + sizeof (buffer); 548 int len; 549 550 *p++ = c; 551 for (;;) { 552 long class = cclass[next + 1]; 553 if (!(class & (Dot | Digit | Letter))) 554 break; 555 if (p != buffer_end) 556 *p++ = next; 557 next = nextchar(stream); 558 if (class & Exp) { 559 if (next == '-' || next == '+') { 560 if (p != buffer_end) 561 *p++ = next; 562 next = nextchar(stream); 563 } 564 } 565 } 566 567 if (p == buffer_end) { 568 sparse_error(stream_pos(stream), "number token exceeds %td characters", 569 buffer_end - buffer); 570 // Pretend we saw just "1". 571 buffer[0] = '1'; 572 p = buffer + 1; 573 } 574 575 *p++ = 0; 576 len = p - buffer; 577 buf = __alloc_bytes(len); 578 memcpy(buf, buffer, len); 579 580 token = stream->token; 581 token_type(token) = TOKEN_NUMBER; 582 token->number = buf; 583 add_token(stream); 584 585 return next; 586 } 587 588 static int eat_string(int next, stream_t *stream, enum token_type type) 589 { 590 static char buffer[MAX_STRING]; 591 struct string *string; 592 struct token *token = stream->token; 593 int len = 0; 594 int escape; 595 int want_hex = 0; 596 char delim = type < TOKEN_STRING ? '\'' : '"'; 597 598 for (escape = 0; escape || next != delim; next = nextchar(stream)) { 599 if (len < MAX_STRING) 600 buffer[len] = next; 601 len++; 602 if (next == '\n') { 603 warning(stream_pos(stream), 604 "Newline in string or character constant"); 605 if (delim == '\'') /* assume it's lost ' */ 606 break; 607 } 608 if (next == EOF) { 609 warning(stream_pos(stream), 610 "End of file in middle of string"); 611 return next; 612 } 613 if (!escape) { 614 if (want_hex && !(cclass[next + 1] & Hex)) 615 warning(stream_pos(stream), 616 "\\x used with no following hex digits"); 617 want_hex = 0; 618 escape = next == '\\'; 619 } else { 620 escape = 0; 621 want_hex = next == 'x'; 622 } 623 } 624 if (want_hex) 625 warning(stream_pos(stream), 626 "\\x used with no following hex digits"); 627 if (len > MAX_STRING) { 628 warning(stream_pos(stream), "string too long (%d bytes, %d bytes max)", len, MAX_STRING); 629 len = MAX_STRING; 630 } 631 if (delim == '\'' && len <= 4) { 632 if (len == 0) { 633 sparse_error(stream_pos(stream), 634 "empty character constant"); 635 return nextchar(stream); 636 } 637 token_type(token) = type + len; 638 memset(buffer + len, '\0', 4 - len); 639 memcpy(token->embedded, buffer, 4); 640 } else { 641 token_type(token) = type; 642 string = __alloc_string(len+1); 643 memcpy(string->data, buffer, len); 644 string->data[len] = '\0'; 645 string->length = len+1; 646 token->string = string; 647 } 648 649 /* Pass it on.. */ 650 token = stream->token; 651 add_token(stream); 652 return nextchar(stream); 653 } 654 655 static int drop_stream_eoln(stream_t *stream) 656 { 657 drop_token(stream); 658 for (;;) { 659 switch (nextchar(stream)) { 660 case EOF: 661 return EOF; 662 case '\n': 663 return nextchar(stream); 664 } 665 } 666 } 667 668 static int drop_stream_comment(stream_t *stream) 669 { 670 int newline; 671 int next; 672 drop_token(stream); 673 newline = stream->newline; 674 675 next = nextchar(stream); 676 for (;;) { 677 int curr = next; 678 if (curr == EOF) { 679 warning(stream_pos(stream), "End of file in the middle of a comment"); 680 return curr; 681 } 682 next = nextchar(stream); 683 if (curr == '*' && next == '/') 684 break; 685 } 686 stream->newline = newline; 687 return nextchar(stream); 688 } 689 690 unsigned char combinations[][4] = COMBINATION_STRINGS; 691 692 #define NR_COMBINATIONS (SPECIAL_ARG_SEPARATOR - SPECIAL_BASE) 693 694 /* hash function for two-character punctuators - all give unique values */ 695 #define special_hash(c0, c1) (((c0*8+c1*2)+((c0*8+c1*2)>>5))&31) 696 697 /* 698 * note that we won't get false positives - special_hash(0,0) is 0 and 699 * entry 0 is filled (by +=), so all the missing ones are OK. 700 */ 701 static unsigned char hash_results[32][2] = { 702 #define RES(c0, c1) [special_hash(c0, c1)] = {c0, c1} 703 RES('+', '='), /* 00 */ 704 RES('/', '='), /* 01 */ 705 RES('^', '='), /* 05 */ 706 RES('&', '&'), /* 07 */ 707 RES('#', '#'), /* 08 */ 708 RES('<', '<'), /* 0a */ 709 RES('<', '='), /* 0c */ 710 RES('!', '='), /* 0e */ 711 RES('%', '='), /* 0f */ 712 RES('-', '-'), /* 10 */ 713 RES('-', '='), /* 11 */ 714 RES('-', '>'), /* 13 */ 715 RES('=', '='), /* 15 */ 716 RES('&', '='), /* 17 */ 717 RES('*', '='), /* 18 */ 718 RES('.', '.'), /* 1a */ 719 RES('+', '+'), /* 1b */ 720 RES('|', '='), /* 1c */ 721 RES('>', '='), /* 1d */ 722 RES('|', '|'), /* 1e */ 723 RES('>', '>') /* 1f */ 724 #undef RES 725 }; 726 static int code[32] = { 727 #define CODE(c0, c1, value) [special_hash(c0, c1)] = value 728 CODE('+', '=', SPECIAL_ADD_ASSIGN), /* 00 */ 729 CODE('/', '=', SPECIAL_DIV_ASSIGN), /* 01 */ 730 CODE('^', '=', SPECIAL_XOR_ASSIGN), /* 05 */ 731 CODE('&', '&', SPECIAL_LOGICAL_AND), /* 07 */ 732 CODE('#', '#', SPECIAL_HASHHASH), /* 08 */ 733 CODE('<', '<', SPECIAL_LEFTSHIFT), /* 0a */ 734 CODE('<', '=', SPECIAL_LTE), /* 0c */ 735 CODE('!', '=', SPECIAL_NOTEQUAL), /* 0e */ 736 CODE('%', '=', SPECIAL_MOD_ASSIGN), /* 0f */ 737 CODE('-', '-', SPECIAL_DECREMENT), /* 10 */ 738 CODE('-', '=', SPECIAL_SUB_ASSIGN), /* 11 */ 739 CODE('-', '>', SPECIAL_DEREFERENCE), /* 13 */ 740 CODE('=', '=', SPECIAL_EQUAL), /* 15 */ 741 CODE('&', '=', SPECIAL_AND_ASSIGN), /* 17 */ 742 CODE('*', '=', SPECIAL_MUL_ASSIGN), /* 18 */ 743 CODE('.', '.', SPECIAL_DOTDOT), /* 1a */ 744 CODE('+', '+', SPECIAL_INCREMENT), /* 1b */ 745 CODE('|', '=', SPECIAL_OR_ASSIGN), /* 1c */ 746 CODE('>', '=', SPECIAL_GTE), /* 1d */ 747 CODE('|', '|', SPECIAL_LOGICAL_OR), /* 1e */ 748 CODE('>', '>', SPECIAL_RIGHTSHIFT) /* 1f */ 749 #undef CODE 750 }; 751 752 static int get_one_special(int c, stream_t *stream) 753 { 754 struct token *token; 755 int next, value, i; 756 757 next = nextchar(stream); 758 759 /* 760 * Check for numbers, strings, character constants, and comments 761 */ 762 switch (c) { 763 case '.': 764 if (next >= '0' && next <= '9') 765 return get_one_number(c, next, stream); 766 break; 767 case '"': 768 return eat_string(next, stream, TOKEN_STRING); 769 case '\'': 770 return eat_string(next, stream, TOKEN_CHAR); 771 case '/': 772 if (next == '/') 773 return drop_stream_eoln(stream); 774 if (next == '*') 775 return drop_stream_comment(stream); 776 } 777 778 /* 779 * Check for combinations 780 */ 781 value = c; 782 if (cclass[next + 1] & ValidSecond) { 783 i = special_hash(c, next); 784 if (hash_results[i][0] == c && hash_results[i][1] == next) { 785 value = code[i]; 786 next = nextchar(stream); 787 if (value >= SPECIAL_LEFTSHIFT && 788 next == "==."[value - SPECIAL_LEFTSHIFT]) { 789 value += 3; 790 next = nextchar(stream); 791 } 792 } 793 } 794 795 /* Pass it on.. */ 796 token = stream->token; 797 token_type(token) = TOKEN_SPECIAL; 798 token->special = value; 799 add_token(stream); 800 return next; 801 } 802 803 #define IDENT_HASH_BITS (13) 804 #define IDENT_HASH_SIZE (1<<IDENT_HASH_BITS) 805 #define IDENT_HASH_MASK (IDENT_HASH_SIZE-1) 806 807 #define ident_hash_init(c) (c) 808 #define ident_hash_add(oldhash,c) ((oldhash)*11 + (c)) 809 #define ident_hash_end(hash) ((((hash) >> IDENT_HASH_BITS) + (hash)) & IDENT_HASH_MASK) 810 811 static struct ident *hash_table[IDENT_HASH_SIZE]; 812 static int ident_hit, ident_miss, idents; 813 814 void show_identifier_stats(void) 815 { 816 int i; 817 int distribution[100]; 818 819 fprintf(stderr, "identifiers: %d hits, %d misses\n", 820 ident_hit, ident_miss); 821 822 for (i = 0; i < 100; i++) 823 distribution[i] = 0; 824 825 for (i = 0; i < IDENT_HASH_SIZE; i++) { 826 struct ident * ident = hash_table[i]; 827 int count = 0; 828 829 while (ident) { 830 count++; 831 ident = ident->next; 832 } 833 if (count > 99) 834 count = 99; 835 distribution[count]++; 836 } 837 838 for (i = 0; i < 100; i++) { 839 if (distribution[i]) 840 fprintf(stderr, "%2d: %d buckets\n", i, distribution[i]); 841 } 842 } 843 844 static struct ident *alloc_ident(const char *name, int len) 845 { 846 struct ident *ident = __alloc_ident(len); 847 ident->symbols = NULL; 848 ident->len = len; 849 ident->tainted = 0; 850 memcpy(ident->name, name, len); 851 return ident; 852 } 853 854 static struct ident * insert_hash(struct ident *ident, unsigned long hash) 855 { 856 ident->next = hash_table[hash]; 857 hash_table[hash] = ident; 858 ident_miss++; 859 return ident; 860 } 861 862 static struct ident *create_hashed_ident(const char *name, int len, unsigned long hash) 863 { 864 struct ident *ident; 865 struct ident **p; 866 867 p = &hash_table[hash]; 868 while ((ident = *p) != NULL) { 869 if (ident->len == (unsigned char) len) { 870 if (strncmp(name, ident->name, len) != 0) 871 goto next; 872 873 ident_hit++; 874 return ident; 875 } 876 next: 877 //misses++; 878 p = &ident->next; 879 } 880 ident = alloc_ident(name, len); 881 *p = ident; 882 ident->next = NULL; 883 ident_miss++; 884 idents++; 885 return ident; 886 } 887 888 static unsigned long hash_name(const char *name, int len) 889 { 890 unsigned long hash; 891 const unsigned char *p = (const unsigned char *)name; 892 893 hash = ident_hash_init(*p++); 894 while (--len) { 895 unsigned int i = *p++; 896 hash = ident_hash_add(hash, i); 897 } 898 return ident_hash_end(hash); 899 } 900 901 struct ident *hash_ident(struct ident *ident) 902 { 903 return insert_hash(ident, hash_name(ident->name, ident->len)); 904 } 905 906 struct ident *built_in_ident(const char *name) 907 { 908 int len = strlen(name); 909 return create_hashed_ident(name, len, hash_name(name, len)); 910 } 911 912 struct token *built_in_token(int stream, struct ident *ident) 913 { 914 struct token *token; 915 916 token = __alloc_token(0); 917 token->pos.stream = stream; 918 token_type(token) = TOKEN_IDENT; 919 token->ident = ident; 920 return token; 921 } 922 923 static int get_one_identifier(int c, stream_t *stream) 924 { 925 struct token *token; 926 struct ident *ident; 927 unsigned long hash; 928 char buf[256]; 929 int len = 1; 930 int next; 931 932 hash = ident_hash_init(c); 933 buf[0] = c; 934 for (;;) { 935 next = nextchar(stream); 936 if (!(cclass[next + 1] & (Letter | Digit))) 937 break; 938 if (len >= sizeof(buf)) 939 break; 940 hash = ident_hash_add(hash, next); 941 buf[len] = next; 942 len++; 943 }; 944 if (cclass[next + 1] & Quote) { 945 if (len == 1 && buf[0] == 'L') { 946 if (next == '\'') 947 return eat_string(nextchar(stream), stream, 948 TOKEN_WIDE_CHAR); 949 else 950 return eat_string(nextchar(stream), stream, 951 TOKEN_WIDE_STRING); 952 } 953 } 954 hash = ident_hash_end(hash); 955 ident = create_hashed_ident(buf, len, hash); 956 957 /* Pass it on.. */ 958 token = stream->token; 959 token_type(token) = TOKEN_IDENT; 960 token->ident = ident; 961 add_token(stream); 962 return next; 963 } 964 965 static int get_one_token(int c, stream_t *stream) 966 { 967 long class = cclass[c + 1]; 968 if (class & Digit) 969 return get_one_number(c, nextchar(stream), stream); 970 if (class & Letter) 971 return get_one_identifier(c, stream); 972 return get_one_special(c, stream); 973 } 974 975 static struct token *setup_stream(stream_t *stream, int idx, int fd, 976 unsigned char *buf, unsigned int buf_size) 977 { 978 struct token *begin; 979 980 stream->nr = idx; 981 stream->line = 1; 982 stream->newline = 1; 983 stream->whitespace = 0; 984 stream->pos = 0; 985 986 stream->token = NULL; 987 stream->fd = fd; 988 stream->offset = 0; 989 stream->size = buf_size; 990 stream->buffer = buf; 991 992 begin = alloc_token(stream); 993 token_type(begin) = TOKEN_STREAMBEGIN; 994 stream->tokenlist = &begin->next; 995 return begin; 996 } 997 998 static struct token *tokenize_stream(stream_t *stream) 999 { 1000 int c = nextchar(stream); 1001 while (c != EOF) { 1002 if (!isspace(c)) { 1003 struct token *token = alloc_token(stream); 1004 stream->token = token; 1005 stream->newline = 0; 1006 stream->whitespace = 0; 1007 c = get_one_token(c, stream); 1008 continue; 1009 } 1010 stream->whitespace = 1; 1011 c = nextchar(stream); 1012 } 1013 return mark_eof(stream); 1014 } 1015 1016 struct token * tokenize_buffer(void *buffer, unsigned long size, struct token **endtoken) 1017 { 1018 stream_t stream; 1019 struct token *begin; 1020 1021 begin = setup_stream(&stream, 0, -1, buffer, size); 1022 *endtoken = tokenize_stream(&stream); 1023 return begin; 1024 } 1025 1026 struct token * tokenize(const char *name, int fd, struct token *endtoken, const char **next_path) 1027 { 1028 struct token *begin, *end; 1029 stream_t stream; 1030 unsigned char buffer[BUFSIZE]; 1031 int idx; 1032 1033 idx = init_stream(name, fd, next_path); 1034 if (idx < 0) { 1035 // info(endtoken->pos, "File %s is const", name); 1036 return endtoken; 1037 } 1038 1039 begin = setup_stream(&stream, idx, fd, buffer, 0); 1040 end = tokenize_stream(&stream); 1041 if (endtoken) 1042 end->next = endtoken; 1043 return begin; 1044 } 1045