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.
5 * Copyright (C) 2003 Transmeta Corp.
8 * Licensed under the Open Software License version 1.1
25 int input_stream_nr
= 0;
26 struct stream
*input_streams
;
27 static int input_streams_allocated
;
28 unsigned int tabstop
= 8;
31 #define BUFSIZE (8192)
36 int newline
, whitespace
;
37 struct token
**tokenlist
;
39 unsigned char *buffer
;
42 const char *stream_name(int stream
)
44 if (stream
< 0 || stream
> input_stream_nr
)
45 return "<bad stream>";
46 return input_streams
[stream
].name
;
49 static struct position
stream_pos(stream_t
*stream
)
53 pos
.stream
= stream
->nr
;
54 pos
.newline
= stream
->newline
;
55 pos
.whitespace
= stream
->whitespace
;
56 pos
.pos
= stream
->pos
;
58 pos
.line
= stream
->line
;
66 const char *show_special(int val
)
68 static char buffer
[4];
72 if (val
>= SPECIAL_BASE
)
73 strcpy(buffer
, (char *) combinations
[val
- SPECIAL_BASE
]);
77 const char *show_ident(const struct ident
*ident
)
79 static char buffer
[256];
82 sprintf(buffer
, "%.*s", ident
->len
, ident
->name
);
86 static char *charstr(char *ptr
, unsigned char c
, unsigned char escape
, unsigned char next
)
89 if (c
== escape
|| c
== '\\')
104 return ptr
+ sprintf(ptr
, "%o", c
);
106 return ptr
+ sprintf(ptr
, "%03o", c
);
109 const char *show_string(const struct string
*string
)
111 static char buffer
[4 * MAX_STRING
+ 3];
116 return "<bad_string>";
119 for (i
= 0; i
< string
->length
-1; i
++) {
120 const char *p
= string
->data
+ i
;
121 ptr
= charstr(ptr
, p
[0], '"', p
[1]);
128 const char *show_token(const struct token
*token
)
130 static char buffer
[256];
134 switch (token_type(token
)) {
136 return "syntax error";
139 return "end-of-input";
142 return show_ident(token
->ident
);
145 return show_string(token
->string
);
148 return token
->number
;
151 return show_special(token
->special
);
155 int c
= token
->character
;
157 ptr
= charstr(ptr
, c
, '\'', 0);
163 case TOKEN_STREAMBEGIN
:
164 sprintf(buffer
, "<beginning of '%s'>", stream_name(token
->pos
.stream
));
167 case TOKEN_STREAMEND
:
168 sprintf(buffer
, "<end of '%s'>", stream_name(token
->pos
.stream
));
172 sprintf(buffer
, "<untaint>");
175 case TOKEN_ARG_COUNT
:
176 sprintf(buffer
, "<argcnt>");
180 sprintf(buffer
, "unhandled token type '%d' ", token_type(token
));
185 int init_stream(const char *name
, int fd
, const char **next_path
)
187 int stream
= input_stream_nr
;
188 struct stream
*current
;
190 if (stream
>= input_streams_allocated
) {
191 int newalloc
= stream
* 4 / 3 + 10;
192 input_streams
= realloc(input_streams
, newalloc
* sizeof(struct stream
));
194 die("Unable to allocate more streams space");
195 input_streams_allocated
= newalloc
;
197 current
= input_streams
+ stream
;
198 memset(current
, 0, sizeof(*current
));
199 current
->name
= name
;
201 current
->next_path
= next_path
;
202 current
->path
= NULL
;
203 current
->constant
= CONSTANT_FILE_MAYBE
;
204 input_stream_nr
= stream
+1;
208 static struct token
* alloc_token(stream_t
*stream
)
210 struct token
*token
= __alloc_token(0);
211 token
->pos
= stream_pos(stream
);
216 * Argh... That was surprisingly messy - handling '\r' complicates the
219 static int nextchar_slow(stream_t
*stream
)
221 int offset
= stream
->offset
;
222 int size
= stream
->size
;
224 int spliced
= 0, had_cr
, had_backslash
, complain
;
227 had_cr
= had_backslash
= complain
= 0;
230 if (offset
>= size
) {
233 size
= read(stream
->fd
, stream
->buffer
, BUFSIZE
);
237 stream
->offset
= offset
= 0;
240 c
= stream
->buffer
[offset
++];
242 if (had_cr
&& c
!= '\n')
250 stream
->pos
+= (c
== '\t') ? (tabstop
- stream
->pos
% tabstop
) : 1;
257 if (!had_backslash
) {
267 warning(stream_pos(stream
), "non-ASCII data stream");
277 stream
->offset
= offset
;
279 warning(stream_pos(stream
), "non-ASCII data stream");
289 warning(stream_pos(stream
), "no newline at end of file");
291 warning(stream_pos(stream
), "non-ASCII data stream");
293 warning(stream_pos(stream
), "backslash-newline at end of file");
298 * We want that as light as possible while covering all normal cases.
299 * Slow path (including the logics with line-splicing and EOF sanity
300 * checks) is in nextchar_slow().
302 static inline int nextchar(stream_t
*stream
)
304 int offset
= stream
->offset
;
306 if (offset
< stream
->size
) {
307 int c
= stream
->buffer
[offset
++];
308 static const char special
[256] = {
309 ['\t'] = 1, ['\r'] = 1, ['\n'] = 1, ['\\'] = 1
312 stream
->offset
= offset
;
317 return nextchar_slow(stream
);
320 struct token eof_token_entry
;
322 static struct token
*mark_eof(stream_t
*stream
)
326 end
= alloc_token(stream
);
327 token_type(end
) = TOKEN_STREAMEND
;
328 end
->pos
.newline
= 1;
330 eof_token_entry
.next
= &eof_token_entry
;
331 eof_token_entry
.pos
.newline
= 1;
333 end
->next
= &eof_token_entry
;
334 *stream
->tokenlist
= end
;
335 stream
->tokenlist
= NULL
;
339 static void add_token(stream_t
*stream
)
341 struct token
*token
= stream
->token
;
343 stream
->token
= NULL
;
345 *stream
->tokenlist
= token
;
346 stream
->tokenlist
= &token
->next
;
349 static void drop_token(stream_t
*stream
)
351 stream
->newline
|= stream
->token
->pos
.newline
;
352 stream
->whitespace
|= stream
->token
->pos
.whitespace
;
353 stream
->token
= NULL
;
365 static const long cclass
[257] = {
366 ['0' + 1 ... '9' + 1] = Digit
| Hex
,
367 ['A' + 1 ... 'D' + 1] = Letter
| Hex
,
368 ['E' + 1] = Letter
| Hex
| Exp
,
369 ['F' + 1] = Letter
| Hex
,
370 ['G' + 1 ... 'O' + 1] = Letter
,
371 ['P' + 1] = Letter
| Exp
,
372 ['Q' + 1 ... 'Z' + 1] = Letter
,
373 ['a' + 1 ... 'd' + 1] = Letter
| Hex
,
374 ['e' + 1] = Letter
| Hex
| Exp
,
375 ['f' + 1] = Letter
| Hex
,
376 ['g' + 1 ... 'o' + 1] = Letter
,
377 ['p' + 1] = Letter
| Exp
,
378 ['q' + 1 ... 'z' + 1] = Letter
,
380 ['.' + 1] = Dot
| ValidSecond
,
381 ['=' + 1] = ValidSecond
,
382 ['+' + 1] = ValidSecond
,
383 ['-' + 1] = ValidSecond
,
384 ['>' + 1] = ValidSecond
,
385 ['<' + 1] = ValidSecond
,
386 ['&' + 1] = ValidSecond
,
387 ['|' + 1] = ValidSecond
,
388 ['#' + 1] = ValidSecond
,
396 * pp-number identifier-nodigit
403 static int get_one_number(int c
, int next
, stream_t
*stream
)
406 static char buffer
[4095];
407 char *p
= buffer
, *buf
, *buffer_end
= buffer
+ sizeof (buffer
);
412 long class = cclass
[next
+ 1];
413 if (!(class & (Dot
| Digit
| Letter
)))
417 next
= nextchar(stream
);
419 if (next
== '-' || next
== '+') {
422 next
= nextchar(stream
);
427 if (p
== buffer_end
) {
428 sparse_error(stream_pos(stream
), "number token exceeds %td characters",
429 buffer_end
- buffer
);
430 // Pretend we saw just "1".
437 buf
= __alloc_bytes(len
);
438 memcpy(buf
, buffer
, len
);
440 token
= stream
->token
;
441 token_type(token
) = TOKEN_NUMBER
;
448 static int escapechar(int first
, int type
, stream_t
*stream
, int *valp
)
452 next
= nextchar(stream
);
456 warning(stream_pos(stream
), "Newline in string or character constant");
458 if (first
== '\\' && next
!= EOF
) {
460 next
= nextchar(stream
);
496 warning(stream_pos(stream
), "Newline in string or character constant");
501 while (next
>= '0' && next
<= '9') {
502 value
= (value
<< 3) + (next
-'0');
503 next
= nextchar(stream
);
511 int hex
= hexval(next
);
514 next
= nextchar(stream
);
515 while ((hex
= hexval(next
)) < 16) {
516 value
= (value
<< 4) + hex
;
517 next
= nextchar(stream
);
525 warning(stream_pos(stream
), "Unknown escape '%c'", value
);
528 /* Mark it as escaped */
535 static int get_char_token(int next
, stream_t
*stream
)
540 next
= escapechar(next
, '\'', stream
, &value
);
541 if (value
== '\'' || next
!= '\'') {
542 sparse_error(stream_pos(stream
), "Bad character constant");
547 token
= stream
->token
;
548 token_type(token
) = TOKEN_CHAR
;
549 token
->character
= value
& 0xff;
552 return nextchar(stream
);
555 static int get_string_token(int next
, stream_t
*stream
)
557 static char buffer
[MAX_STRING
];
558 struct string
*string
;
564 next
= escapechar(next
, '"', stream
, &val
);
568 warning(stream_pos(stream
), "End of file in middle of string");
571 if (len
< MAX_STRING
)
576 if (len
> MAX_STRING
) {
577 warning(stream_pos(stream
), "string too long (%d bytes, %d bytes max)", len
, MAX_STRING
);
581 string
= __alloc_string(len
+1);
582 memcpy(string
->data
, buffer
, len
);
583 string
->data
[len
] = '\0';
584 string
->length
= len
+1;
587 token
= stream
->token
;
588 token_type(token
) = TOKEN_STRING
;
589 token
->string
= string
;
595 static int drop_stream_eoln(stream_t
*stream
)
599 switch (nextchar(stream
)) {
603 return nextchar(stream
);
608 static int drop_stream_comment(stream_t
*stream
)
613 newline
= stream
->newline
;
615 next
= nextchar(stream
);
619 warning(stream_pos(stream
), "End of file in the middle of a comment");
622 next
= nextchar(stream
);
623 if (curr
== '*' && next
== '/')
626 stream
->newline
= newline
;
627 return nextchar(stream
);
630 unsigned char combinations
[][4] = COMBINATION_STRINGS
;
632 #define NR_COMBINATIONS (SPECIAL_ARG_SEPARATOR - SPECIAL_BASE)
634 /* hash function for two-character punctuators - all give unique values */
635 #define special_hash(c0, c1) (((c0*8+c1*2)+((c0*8+c1*2)>>5))&31)
638 * note that we won't get false positives - special_hash(0,0) is 0 and
639 * entry 0 is filled (by +=), so all the missing ones are OK.
641 static unsigned char hash_results
[32][2] = {
642 #define RES(c0, c1) [special_hash(c0, c1)] = {c0, c1}
643 RES('+', '='), /* 00 */
644 RES('/', '='), /* 01 */
645 RES('^', '='), /* 05 */
646 RES('&', '&'), /* 07 */
647 RES('#', '#'), /* 08 */
648 RES('<', '<'), /* 0a */
649 RES('<', '='), /* 0c */
650 RES('!', '='), /* 0e */
651 RES('%', '='), /* 0f */
652 RES('-', '-'), /* 10 */
653 RES('-', '='), /* 11 */
654 RES('-', '>'), /* 13 */
655 RES('=', '='), /* 15 */
656 RES('&', '='), /* 17 */
657 RES('*', '='), /* 18 */
658 RES('.', '.'), /* 1a */
659 RES('+', '+'), /* 1b */
660 RES('|', '='), /* 1c */
661 RES('>', '='), /* 1d */
662 RES('|', '|'), /* 1e */
663 RES('>', '>') /* 1f */
666 static int code
[32] = {
667 #define CODE(c0, c1, value) [special_hash(c0, c1)] = value
668 CODE('+', '=', SPECIAL_ADD_ASSIGN
), /* 00 */
669 CODE('/', '=', SPECIAL_DIV_ASSIGN
), /* 01 */
670 CODE('^', '=', SPECIAL_XOR_ASSIGN
), /* 05 */
671 CODE('&', '&', SPECIAL_LOGICAL_AND
), /* 07 */
672 CODE('#', '#', SPECIAL_HASHHASH
), /* 08 */
673 CODE('<', '<', SPECIAL_LEFTSHIFT
), /* 0a */
674 CODE('<', '=', SPECIAL_LTE
), /* 0c */
675 CODE('!', '=', SPECIAL_NOTEQUAL
), /* 0e */
676 CODE('%', '=', SPECIAL_MOD_ASSIGN
), /* 0f */
677 CODE('-', '-', SPECIAL_DECREMENT
), /* 10 */
678 CODE('-', '=', SPECIAL_SUB_ASSIGN
), /* 11 */
679 CODE('-', '>', SPECIAL_DEREFERENCE
), /* 13 */
680 CODE('=', '=', SPECIAL_EQUAL
), /* 15 */
681 CODE('&', '=', SPECIAL_AND_ASSIGN
), /* 17 */
682 CODE('*', '=', SPECIAL_MUL_ASSIGN
), /* 18 */
683 CODE('.', '.', SPECIAL_DOTDOT
), /* 1a */
684 CODE('+', '+', SPECIAL_INCREMENT
), /* 1b */
685 CODE('|', '=', SPECIAL_OR_ASSIGN
), /* 1c */
686 CODE('>', '=', SPECIAL_GTE
), /* 1d */
687 CODE('|', '|', SPECIAL_LOGICAL_OR
), /* 1e */
688 CODE('>', '>', SPECIAL_RIGHTSHIFT
) /* 1f */
692 static int get_one_special(int c
, stream_t
*stream
)
697 next
= nextchar(stream
);
700 * Check for numbers, strings, character constants, and comments
704 if (next
>= '0' && next
<= '9')
705 return get_one_number(c
, next
, stream
);
708 return get_string_token(next
, stream
);
710 return get_char_token(next
, stream
);
713 return drop_stream_eoln(stream
);
715 return drop_stream_comment(stream
);
719 * Check for combinations
722 if (cclass
[next
+ 1] & ValidSecond
) {
723 i
= special_hash(c
, next
);
724 if (hash_results
[i
][0] == c
&& hash_results
[i
][1] == next
) {
726 next
= nextchar(stream
);
727 if (value
>= SPECIAL_LEFTSHIFT
&&
728 next
== "==."[value
- SPECIAL_LEFTSHIFT
]) {
730 next
= nextchar(stream
);
736 token
= stream
->token
;
737 token_type(token
) = TOKEN_SPECIAL
;
738 token
->special
= value
;
743 #define IDENT_HASH_BITS (13)
744 #define IDENT_HASH_SIZE (1<<IDENT_HASH_BITS)
745 #define IDENT_HASH_MASK (IDENT_HASH_SIZE-1)
747 #define ident_hash_init(c) (c)
748 #define ident_hash_add(oldhash,c) ((oldhash)*11 + (c))
749 #define ident_hash_end(hash) ((((hash) >> IDENT_HASH_BITS) + (hash)) & IDENT_HASH_MASK)
751 static struct ident
*hash_table
[IDENT_HASH_SIZE
];
752 static int ident_hit
, ident_miss
, idents
;
754 void show_identifier_stats(void)
757 int distribution
[100];
759 fprintf(stderr
, "identifiers: %d hits, %d misses\n",
760 ident_hit
, ident_miss
);
762 for (i
= 0; i
< 100; i
++)
765 for (i
= 0; i
< IDENT_HASH_SIZE
; i
++) {
766 struct ident
* ident
= hash_table
[i
];
775 distribution
[count
]++;
778 for (i
= 0; i
< 100; i
++) {
780 fprintf(stderr
, "%2d: %d buckets\n", i
, distribution
[i
]);
784 static struct ident
*alloc_ident(const char *name
, int len
)
786 struct ident
*ident
= __alloc_ident(len
);
787 ident
->symbols
= NULL
;
790 memcpy(ident
->name
, name
, len
);
794 static struct ident
* insert_hash(struct ident
*ident
, unsigned long hash
)
796 ident
->next
= hash_table
[hash
];
797 hash_table
[hash
] = ident
;
802 static struct ident
*create_hashed_ident(const char *name
, int len
, unsigned long hash
)
807 p
= &hash_table
[hash
];
808 while ((ident
= *p
) != NULL
) {
809 if (ident
->len
== (unsigned char) len
) {
810 if (strncmp(name
, ident
->name
, len
) != 0)
820 ident
= alloc_ident(name
, len
);
828 static unsigned long hash_name(const char *name
, int len
)
831 const unsigned char *p
= (const unsigned char *)name
;
833 hash
= ident_hash_init(*p
++);
835 unsigned int i
= *p
++;
836 hash
= ident_hash_add(hash
, i
);
838 return ident_hash_end(hash
);
841 struct ident
*hash_ident(struct ident
*ident
)
843 return insert_hash(ident
, hash_name(ident
->name
, ident
->len
));
846 struct ident
*built_in_ident(const char *name
)
848 int len
= strlen(name
);
849 return create_hashed_ident(name
, len
, hash_name(name
, len
));
852 struct token
*built_in_token(int stream
, const char *name
)
856 token
= __alloc_token(0);
857 token
->pos
.stream
= stream
;
858 token_type(token
) = TOKEN_IDENT
;
859 token
->ident
= built_in_ident(name
);
863 static int get_one_identifier(int c
, stream_t
*stream
)
872 hash
= ident_hash_init(c
);
875 next
= nextchar(stream
);
876 if (!(cclass
[next
+ 1] & (Letter
| Digit
)))
878 if (len
>= sizeof(buf
))
880 hash
= ident_hash_add(hash
, next
);
884 hash
= ident_hash_end(hash
);
886 ident
= create_hashed_ident(buf
, len
, hash
);
889 token
= stream
->token
;
890 token_type(token
) = TOKEN_IDENT
;
891 token
->ident
= ident
;
896 static int get_one_token(int c
, stream_t
*stream
)
898 long class = cclass
[c
+ 1];
900 return get_one_number(c
, nextchar(stream
), stream
);
902 return get_one_identifier(c
, stream
);
903 return get_one_special(c
, stream
);
906 static struct token
*setup_stream(stream_t
*stream
, int idx
, int fd
,
907 unsigned char *buf
, unsigned int buf_size
)
914 stream
->whitespace
= 0;
917 stream
->token
= NULL
;
920 stream
->size
= buf_size
;
921 stream
->buffer
= buf
;
923 begin
= alloc_token(stream
);
924 token_type(begin
) = TOKEN_STREAMBEGIN
;
925 stream
->tokenlist
= &begin
->next
;
929 static struct token
*tokenize_stream(stream_t
*stream
)
931 int c
= nextchar(stream
);
934 struct token
*token
= alloc_token(stream
);
935 stream
->token
= token
;
937 stream
->whitespace
= 0;
938 c
= get_one_token(c
, stream
);
941 stream
->whitespace
= 1;
942 c
= nextchar(stream
);
944 return mark_eof(stream
);
947 struct token
* tokenize_buffer(void *buffer
, unsigned long size
, struct token
**endtoken
)
952 begin
= setup_stream(&stream
, 0, -1, buffer
, size
);
953 *endtoken
= tokenize_stream(&stream
);
957 struct token
* tokenize(const char *name
, int fd
, struct token
*endtoken
, const char **next_path
)
959 struct token
*begin
, *end
;
961 unsigned char buffer
[BUFSIZE
];
964 idx
= init_stream(name
, fd
, next_path
);
966 // info(endtoken->pos, "File %s is const", name);
970 begin
= setup_stream(&stream
, idx
, fd
, buffer
, 0);
971 end
= tokenize_stream(&stream
);
973 end
->next
= endtoken
;