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
26 int input_stream_nr
= 0;
27 struct stream
*input_streams
;
28 static int input_streams_allocated
;
29 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
;
57 pos
.line
= stream
->line
;
62 const char *show_special(int val
)
64 static char buffer
[4];
68 if (val
>= SPECIAL_BASE
)
69 strcpy(buffer
, (char *) combinations
[val
- SPECIAL_BASE
]);
73 const char *show_ident(const struct ident
*ident
)
75 static char buffer
[256];
78 sprintf(buffer
, "%.*s", ident
->len
, ident
->name
);
82 static char *charstr(char *ptr
, unsigned char c
, unsigned char escape
, unsigned char next
)
85 if (c
== escape
|| c
== '\\')
100 return ptr
+ sprintf(ptr
, "%o", c
);
102 return ptr
+ sprintf(ptr
, "%03o", c
);
105 const char *show_string(const struct string
*string
)
107 static char buffer
[4 * MAX_STRING
+ 3];
112 return "<bad_string>";
115 for (i
= 0; i
< string
->length
-1; i
++) {
116 const char *p
= string
->data
+ i
;
117 ptr
= charstr(ptr
, p
[0], '"', p
[1]);
124 const char *show_token(const struct token
*token
)
126 static char buffer
[256];
130 switch (token_type(token
)) {
132 return "syntax error";
135 return "end-of-input";
138 return show_ident(token
->ident
);
141 case TOKEN_WIDE_STRING
:
142 return show_string(token
->string
);
145 return token
->number
;
148 return show_special(token
->special
);
151 case TOKEN_WIDE_CHAR
: {
153 int c
= token
->character
;
155 ptr
= charstr(ptr
, c
, '\'', 0);
161 case TOKEN_STREAMBEGIN
:
162 sprintf(buffer
, "<beginning of '%s'>", stream_name(token
->pos
.stream
));
165 case TOKEN_STREAMEND
:
166 sprintf(buffer
, "<end of '%s'>", stream_name(token
->pos
.stream
));
170 sprintf(buffer
, "<untaint>");
173 case TOKEN_ARG_COUNT
:
174 sprintf(buffer
, "<argcnt>");
178 sprintf(buffer
, "unhandled token type '%d' ", token_type(token
));
183 #define HASHED_INPUT_BITS (6)
184 #define HASHED_INPUT (1 << HASHED_INPUT_BITS)
185 #define HASH_PRIME 0x9e370001UL
187 static int input_stream_hashes
[HASHED_INPUT
] = { [0 ... HASHED_INPUT
-1] = -1 };
189 int *hash_stream(const char *name
)
194 while ((c
= *name
++) != 0)
195 hash
= (hash
+ (c
<< 4) + (c
>> 4)) * 11;
198 hash
>>= 32 - HASHED_INPUT_BITS
;
199 return input_stream_hashes
+ hash
;
202 int init_stream(const char *name
, int fd
, const char **next_path
)
204 int stream
= input_stream_nr
, *hash
;
205 struct stream
*current
;
207 if (stream
>= input_streams_allocated
) {
208 int newalloc
= stream
* 4 / 3 + 10;
209 input_streams
= realloc(input_streams
, newalloc
* sizeof(struct stream
));
211 die("Unable to allocate more streams space");
212 input_streams_allocated
= newalloc
;
214 current
= input_streams
+ stream
;
215 memset(current
, 0, sizeof(*current
));
216 current
->name
= name
;
218 current
->next_path
= next_path
;
219 current
->path
= NULL
;
220 current
->constant
= CONSTANT_FILE_MAYBE
;
221 input_stream_nr
= stream
+1;
222 hash
= hash_stream(name
);
223 current
->next_stream
= *hash
;
228 static struct token
* alloc_token(stream_t
*stream
)
230 struct token
*token
= __alloc_token(0);
231 token
->pos
= stream_pos(stream
);
236 * Argh... That was surprisingly messy - handling '\r' complicates the
239 static int nextchar_slow(stream_t
*stream
)
241 int offset
= stream
->offset
;
242 int size
= stream
->size
;
244 int spliced
= 0, had_cr
, had_backslash
, complain
;
247 had_cr
= had_backslash
= complain
= 0;
250 if (offset
>= size
) {
253 size
= read(stream
->fd
, stream
->buffer
, BUFSIZE
);
257 stream
->offset
= offset
= 0;
260 c
= stream
->buffer
[offset
++];
262 if (had_cr
&& c
!= '\n')
270 stream
->pos
+= (c
== '\t') ? (tabstop
- stream
->pos
% tabstop
) : 1;
277 if (!had_backslash
) {
287 warning(stream_pos(stream
), "non-ASCII data stream");
297 stream
->offset
= offset
;
299 warning(stream_pos(stream
), "non-ASCII data stream");
309 warning(stream_pos(stream
), "no newline at end of file");
311 warning(stream_pos(stream
), "non-ASCII data stream");
313 warning(stream_pos(stream
), "backslash-newline at end of file");
318 * We want that as light as possible while covering all normal cases.
319 * Slow path (including the logics with line-splicing and EOF sanity
320 * checks) is in nextchar_slow().
322 static inline int nextchar(stream_t
*stream
)
324 int offset
= stream
->offset
;
326 if (offset
< stream
->size
) {
327 int c
= stream
->buffer
[offset
++];
328 static const char special
[256] = {
329 ['\t'] = 1, ['\r'] = 1, ['\n'] = 1, ['\\'] = 1
332 stream
->offset
= offset
;
337 return nextchar_slow(stream
);
340 struct token eof_token_entry
;
342 static struct token
*mark_eof(stream_t
*stream
)
346 end
= alloc_token(stream
);
347 token_type(end
) = TOKEN_STREAMEND
;
348 end
->pos
.newline
= 1;
350 eof_token_entry
.next
= &eof_token_entry
;
351 eof_token_entry
.pos
.newline
= 1;
353 end
->next
= &eof_token_entry
;
354 *stream
->tokenlist
= end
;
355 stream
->tokenlist
= NULL
;
359 static void add_token(stream_t
*stream
)
361 struct token
*token
= stream
->token
;
363 stream
->token
= NULL
;
365 *stream
->tokenlist
= token
;
366 stream
->tokenlist
= &token
->next
;
369 static void drop_token(stream_t
*stream
)
371 stream
->newline
|= stream
->token
->pos
.newline
;
372 stream
->whitespace
|= stream
->token
->pos
.whitespace
;
373 stream
->token
= NULL
;
385 static const long cclass
[257] = {
386 ['0' + 1 ... '9' + 1] = Digit
| Hex
,
387 ['A' + 1 ... 'D' + 1] = Letter
| Hex
,
388 ['E' + 1] = Letter
| Hex
| Exp
,
389 ['F' + 1] = Letter
| Hex
,
390 ['G' + 1 ... 'O' + 1] = Letter
,
391 ['P' + 1] = Letter
| Exp
,
392 ['Q' + 1 ... 'Z' + 1] = Letter
,
393 ['a' + 1 ... 'd' + 1] = Letter
| Hex
,
394 ['e' + 1] = Letter
| Hex
| Exp
,
395 ['f' + 1] = Letter
| Hex
,
396 ['g' + 1 ... 'o' + 1] = Letter
,
397 ['p' + 1] = Letter
| Exp
,
398 ['q' + 1 ... 'z' + 1] = Letter
,
400 ['.' + 1] = Dot
| ValidSecond
,
401 ['=' + 1] = ValidSecond
,
402 ['+' + 1] = ValidSecond
,
403 ['-' + 1] = ValidSecond
,
404 ['>' + 1] = ValidSecond
,
405 ['<' + 1] = ValidSecond
,
406 ['&' + 1] = ValidSecond
,
407 ['|' + 1] = ValidSecond
,
408 ['#' + 1] = ValidSecond
,
416 * pp-number identifier-nodigit
423 static int get_one_number(int c
, int next
, stream_t
*stream
)
426 static char buffer
[4095];
427 char *p
= buffer
, *buf
, *buffer_end
= buffer
+ sizeof (buffer
);
432 long class = cclass
[next
+ 1];
433 if (!(class & (Dot
| Digit
| Letter
)))
437 next
= nextchar(stream
);
439 if (next
== '-' || next
== '+') {
442 next
= nextchar(stream
);
447 if (p
== buffer_end
) {
448 sparse_error(stream_pos(stream
), "number token exceeds %td characters",
449 buffer_end
- buffer
);
450 // Pretend we saw just "1".
457 buf
= __alloc_bytes(len
);
458 memcpy(buf
, buffer
, len
);
460 token
= stream
->token
;
461 token_type(token
) = TOKEN_NUMBER
;
468 static int escapechar(int first
, int type
, stream_t
*stream
, int *valp
)
472 next
= nextchar(stream
);
476 warning(stream_pos(stream
), "Newline in string or character constant");
478 if (first
== '\\' && next
!= EOF
) {
480 next
= nextchar(stream
);
516 warning(stream_pos(stream
), "Newline in string or character constant");
521 while (next
>= '0' && next
<= '7') {
522 value
= (value
<< 3) + (next
-'0');
523 next
= nextchar(stream
);
531 int hex
= hexval(next
);
534 next
= nextchar(stream
);
535 while ((hex
= hexval(next
)) < 16) {
536 value
= (value
<< 4) + hex
;
537 next
= nextchar(stream
);
545 warning(stream_pos(stream
), "Unknown escape '%c'", value
);
548 /* Mark it as escaped */
555 static int get_char_token(int next
, stream_t
*stream
, enum token_type type
)
560 next
= escapechar(next
, '\'', stream
, &value
);
561 if (value
== '\'' || next
!= '\'') {
562 sparse_error(stream_pos(stream
), "Bad character constant");
567 token
= stream
->token
;
568 token_type(token
) = type
;
569 token
->character
= value
& 0xff;
572 return nextchar(stream
);
575 static int get_string_token(int next
, stream_t
*stream
, enum token_type type
)
577 static char buffer
[MAX_STRING
];
578 struct string
*string
;
584 next
= escapechar(next
, '"', stream
, &val
);
588 warning(stream_pos(stream
), "End of file in middle of string");
591 if (len
< MAX_STRING
)
596 if (len
> MAX_STRING
) {
597 warning(stream_pos(stream
), "string too long (%d bytes, %d bytes max)", len
, MAX_STRING
);
601 string
= __alloc_string(len
+1);
602 memcpy(string
->data
, buffer
, len
);
603 string
->data
[len
] = '\0';
604 string
->length
= len
+1;
607 token
= stream
->token
;
608 token_type(token
) = type
;
609 token
->string
= string
;
615 static int drop_stream_eoln(stream_t
*stream
)
619 switch (nextchar(stream
)) {
623 return nextchar(stream
);
628 static int drop_stream_comment(stream_t
*stream
)
633 newline
= stream
->newline
;
635 next
= nextchar(stream
);
639 warning(stream_pos(stream
), "End of file in the middle of a comment");
642 next
= nextchar(stream
);
643 if (curr
== '*' && next
== '/')
646 stream
->newline
= newline
;
647 return nextchar(stream
);
650 unsigned char combinations
[][4] = COMBINATION_STRINGS
;
652 #define NR_COMBINATIONS (SPECIAL_ARG_SEPARATOR - SPECIAL_BASE)
654 /* hash function for two-character punctuators - all give unique values */
655 #define special_hash(c0, c1) (((c0*8+c1*2)+((c0*8+c1*2)>>5))&31)
658 * note that we won't get false positives - special_hash(0,0) is 0 and
659 * entry 0 is filled (by +=), so all the missing ones are OK.
661 static unsigned char hash_results
[32][2] = {
662 #define RES(c0, c1) [special_hash(c0, c1)] = {c0, c1}
663 RES('+', '='), /* 00 */
664 RES('/', '='), /* 01 */
665 RES('^', '='), /* 05 */
666 RES('&', '&'), /* 07 */
667 RES('#', '#'), /* 08 */
668 RES('<', '<'), /* 0a */
669 RES('<', '='), /* 0c */
670 RES('!', '='), /* 0e */
671 RES('%', '='), /* 0f */
672 RES('-', '-'), /* 10 */
673 RES('-', '='), /* 11 */
674 RES('-', '>'), /* 13 */
675 RES('=', '='), /* 15 */
676 RES('&', '='), /* 17 */
677 RES('*', '='), /* 18 */
678 RES('.', '.'), /* 1a */
679 RES('+', '+'), /* 1b */
680 RES('|', '='), /* 1c */
681 RES('>', '='), /* 1d */
682 RES('|', '|'), /* 1e */
683 RES('>', '>') /* 1f */
686 static int code
[32] = {
687 #define CODE(c0, c1, value) [special_hash(c0, c1)] = value
688 CODE('+', '=', SPECIAL_ADD_ASSIGN
), /* 00 */
689 CODE('/', '=', SPECIAL_DIV_ASSIGN
), /* 01 */
690 CODE('^', '=', SPECIAL_XOR_ASSIGN
), /* 05 */
691 CODE('&', '&', SPECIAL_LOGICAL_AND
), /* 07 */
692 CODE('#', '#', SPECIAL_HASHHASH
), /* 08 */
693 CODE('<', '<', SPECIAL_LEFTSHIFT
), /* 0a */
694 CODE('<', '=', SPECIAL_LTE
), /* 0c */
695 CODE('!', '=', SPECIAL_NOTEQUAL
), /* 0e */
696 CODE('%', '=', SPECIAL_MOD_ASSIGN
), /* 0f */
697 CODE('-', '-', SPECIAL_DECREMENT
), /* 10 */
698 CODE('-', '=', SPECIAL_SUB_ASSIGN
), /* 11 */
699 CODE('-', '>', SPECIAL_DEREFERENCE
), /* 13 */
700 CODE('=', '=', SPECIAL_EQUAL
), /* 15 */
701 CODE('&', '=', SPECIAL_AND_ASSIGN
), /* 17 */
702 CODE('*', '=', SPECIAL_MUL_ASSIGN
), /* 18 */
703 CODE('.', '.', SPECIAL_DOTDOT
), /* 1a */
704 CODE('+', '+', SPECIAL_INCREMENT
), /* 1b */
705 CODE('|', '=', SPECIAL_OR_ASSIGN
), /* 1c */
706 CODE('>', '=', SPECIAL_GTE
), /* 1d */
707 CODE('|', '|', SPECIAL_LOGICAL_OR
), /* 1e */
708 CODE('>', '>', SPECIAL_RIGHTSHIFT
) /* 1f */
712 static int get_one_special(int c
, stream_t
*stream
)
717 next
= nextchar(stream
);
720 * Check for numbers, strings, character constants, and comments
724 if (next
>= '0' && next
<= '9')
725 return get_one_number(c
, next
, stream
);
728 return get_string_token(next
, stream
, TOKEN_STRING
);
730 return get_char_token(next
, stream
, TOKEN_CHAR
);
733 return drop_stream_eoln(stream
);
735 return drop_stream_comment(stream
);
739 * Check for combinations
742 if (cclass
[next
+ 1] & ValidSecond
) {
743 i
= special_hash(c
, next
);
744 if (hash_results
[i
][0] == c
&& hash_results
[i
][1] == next
) {
746 next
= nextchar(stream
);
747 if (value
>= SPECIAL_LEFTSHIFT
&&
748 next
== "==."[value
- SPECIAL_LEFTSHIFT
]) {
750 next
= nextchar(stream
);
756 token
= stream
->token
;
757 token_type(token
) = TOKEN_SPECIAL
;
758 token
->special
= value
;
763 #define IDENT_HASH_BITS (13)
764 #define IDENT_HASH_SIZE (1<<IDENT_HASH_BITS)
765 #define IDENT_HASH_MASK (IDENT_HASH_SIZE-1)
767 #define ident_hash_init(c) (c)
768 #define ident_hash_add(oldhash,c) ((oldhash)*11 + (c))
769 #define ident_hash_end(hash) ((((hash) >> IDENT_HASH_BITS) + (hash)) & IDENT_HASH_MASK)
771 static struct ident
*hash_table
[IDENT_HASH_SIZE
];
772 static int ident_hit
, ident_miss
, idents
;
774 void show_identifier_stats(void)
777 int distribution
[100];
779 fprintf(stderr
, "identifiers: %d hits, %d misses\n",
780 ident_hit
, ident_miss
);
782 for (i
= 0; i
< 100; i
++)
785 for (i
= 0; i
< IDENT_HASH_SIZE
; i
++) {
786 struct ident
* ident
= hash_table
[i
];
795 distribution
[count
]++;
798 for (i
= 0; i
< 100; i
++) {
800 fprintf(stderr
, "%2d: %d buckets\n", i
, distribution
[i
]);
804 static struct ident
*alloc_ident(const char *name
, int len
)
806 struct ident
*ident
= __alloc_ident(len
);
807 ident
->symbols
= NULL
;
810 memcpy(ident
->name
, name
, len
);
814 static struct ident
* insert_hash(struct ident
*ident
, unsigned long hash
)
816 ident
->next
= hash_table
[hash
];
817 hash_table
[hash
] = ident
;
822 static struct ident
*create_hashed_ident(const char *name
, int len
, unsigned long hash
)
827 p
= &hash_table
[hash
];
828 while ((ident
= *p
) != NULL
) {
829 if (ident
->len
== (unsigned char) len
) {
830 if (strncmp(name
, ident
->name
, len
) != 0)
840 ident
= alloc_ident(name
, len
);
848 static unsigned long hash_name(const char *name
, int len
)
851 const unsigned char *p
= (const unsigned char *)name
;
853 hash
= ident_hash_init(*p
++);
855 unsigned int i
= *p
++;
856 hash
= ident_hash_add(hash
, i
);
858 return ident_hash_end(hash
);
861 struct ident
*hash_ident(struct ident
*ident
)
863 return insert_hash(ident
, hash_name(ident
->name
, ident
->len
));
866 struct ident
*built_in_ident(const char *name
)
868 int len
= strlen(name
);
869 return create_hashed_ident(name
, len
, hash_name(name
, len
));
872 struct token
*built_in_token(int stream
, const char *name
)
876 token
= __alloc_token(0);
877 token
->pos
.stream
= stream
;
878 token_type(token
) = TOKEN_IDENT
;
879 token
->ident
= built_in_ident(name
);
883 static int get_one_identifier(int c
, stream_t
*stream
)
892 hash
= ident_hash_init(c
);
895 next
= nextchar(stream
);
896 if (!(cclass
[next
+ 1] & (Letter
| Digit
)))
898 if (len
>= sizeof(buf
))
900 hash
= ident_hash_add(hash
, next
);
904 hash
= ident_hash_end(hash
);
906 ident
= create_hashed_ident(buf
, len
, hash
);
908 if (ident
== &L_ident
) {
910 return get_char_token(nextchar(stream
), stream
, TOKEN_WIDE_CHAR
);
912 return get_string_token(nextchar(stream
), stream
, TOKEN_WIDE_STRING
);
916 token
= stream
->token
;
917 token_type(token
) = TOKEN_IDENT
;
918 token
->ident
= ident
;
923 static int get_one_token(int c
, stream_t
*stream
)
925 long class = cclass
[c
+ 1];
927 return get_one_number(c
, nextchar(stream
), stream
);
929 return get_one_identifier(c
, stream
);
930 return get_one_special(c
, stream
);
933 static struct token
*setup_stream(stream_t
*stream
, int idx
, int fd
,
934 unsigned char *buf
, unsigned int buf_size
)
941 stream
->whitespace
= 0;
944 stream
->token
= NULL
;
947 stream
->size
= buf_size
;
948 stream
->buffer
= buf
;
950 begin
= alloc_token(stream
);
951 token_type(begin
) = TOKEN_STREAMBEGIN
;
952 stream
->tokenlist
= &begin
->next
;
956 static struct token
*tokenize_stream(stream_t
*stream
)
958 int c
= nextchar(stream
);
961 struct token
*token
= alloc_token(stream
);
962 stream
->token
= token
;
964 stream
->whitespace
= 0;
965 c
= get_one_token(c
, stream
);
968 stream
->whitespace
= 1;
969 c
= nextchar(stream
);
971 return mark_eof(stream
);
974 struct token
* tokenize_buffer(void *buffer
, unsigned long size
, struct token
**endtoken
)
979 begin
= setup_stream(&stream
, 0, -1, buffer
, size
);
980 *endtoken
= tokenize_stream(&stream
);
984 struct token
* tokenize(const char *name
, int fd
, struct token
*endtoken
, const char **next_path
)
986 struct token
*begin
, *end
;
988 unsigned char buffer
[BUFSIZE
];
991 idx
= init_stream(name
, fd
, next_path
);
993 // info(endtoken->pos, "File %s is const", name);
997 begin
= setup_stream(&stream
, idx
, fd
, buffer
, 0);
998 end
= tokenize_stream(&stream
);
1000 end
->next
= endtoken
;