2 * This is a really stupid C tokenizer. It doesn't do any include
3 * files or anything complex at all. That's the pre-processor.
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
;
29 #define BUFSIZE (8192)
34 struct token
**tokenlist
;
36 unsigned char *buffer
;
40 const char *show_special(int val
)
42 static const char *combinations
[] = COMBINATION_STRINGS
;
43 static char buffer
[4];
47 if (val
>= SPECIAL_BASE
)
48 strcpy(buffer
, combinations
[val
- SPECIAL_BASE
]);
52 const char *show_ident(const struct ident
*ident
)
54 static char buffer
[256];
57 sprintf(buffer
, "%.*s", ident
->len
, ident
->name
);
61 char *charstr(char *ptr
, unsigned char c
, unsigned char escape
, unsigned char next
)
64 if (c
== escape
|| c
== '\\')
79 return ptr
+ sprintf(ptr
, "%o", c
);
81 return ptr
+ sprintf(ptr
, "%03o", c
);
84 const char *show_string(const struct string
*string
)
86 static char buffer
[256];
92 for (i
= 0; i
< string
->length
-1; i
++) {
93 const unsigned char *p
= string
->data
+ i
;
94 ptr
= charstr(ptr
, p
[0], '"', p
[1]);
101 const char *show_token(const struct token
*token
)
103 static char buffer
[256];
107 switch (token_type(token
)) {
109 return "syntax error";
112 return "end-of-input";
115 return show_ident(token
->ident
);
118 return show_string(token
->string
);
121 return token
->number
;
124 return show_special(token
->special
);
128 int c
= token
->character
;
130 ptr
= charstr(ptr
, c
, '\'', 0);
136 case TOKEN_STREAMBEGIN
:
137 sprintf(buffer
, "<beginning of '%s'>", (input_streams
+ token
->pos
.stream
)->name
);
140 case TOKEN_STREAMEND
:
141 sprintf(buffer
, "<end of '%s'>", (input_streams
+ token
->pos
.stream
)->name
);
149 int init_stream(const char *name
, int fd
, const char **next_path
)
151 int stream
= input_stream_nr
;
152 struct stream
*current
;
155 if (stream
>= input_streams_allocated
) {
156 int newalloc
= stream
* 4 / 3 + 10;
157 input_streams
= realloc(input_streams
, newalloc
* sizeof(struct stream
));
159 die("Unable to allocate more streams space");
160 input_streams_allocated
= newalloc
;
162 current
= input_streams
+ stream
;
163 memset(current
, 0, sizeof(*current
));
164 current
->name
= name
;
166 current
->next_path
= next_path
;
167 current
->constant
= CONSTANT_FILE_MAYBE
;
168 if (fd
>= 0 && fstat(fd
, &st
) == 0 && S_ISREG(st
.st_mode
)) {
171 for (i
= 0; i
< stream
; i
++) {
172 struct stream
*s
= input_streams
+ i
;
173 if (s
->constant
== CONSTANT_FILE_YES
&&
174 identical_files(s
, &st
, name
) &&
175 lookup_symbol(s
->protect
, NS_MACRO
))
179 current
->dev
= st
.st_dev
;
180 current
->ino
= st
.st_ino
;
182 input_stream_nr
= stream
+1;
186 static struct token
* alloc_token(stream_t
*stream
)
188 struct token
*token
= __alloc_token(0);
189 token
->pos
= stream
->pos
;
194 * Argh... That was surprisingly messy - handling '\r' complicates the
197 static int nextchar_slow(stream_t
*stream
)
199 int offset
= stream
->offset
;
200 int size
= stream
->size
;
202 int spliced
= 0, had_cr
, had_backslash
, complain
;
205 had_cr
= had_backslash
= complain
= 0;
208 if (offset
>= size
) {
209 size
= read(stream
->fd
, stream
->buffer
, BUFSIZE
);
213 stream
->offset
= offset
= 0;
216 c
= stream
->buffer
[offset
++];
218 if (had_cr
&& c
!= '\n')
233 if (!had_backslash
) {
239 stream
->pos
.newline
= 1;
243 warning(stream
->pos
, "non-ASCII data stream");
253 stream
->offset
= offset
;
255 warning(stream
->pos
, "non-ASCII data stream");
265 warning(stream
->pos
, "no newline at end of file");
267 warning(stream
->pos
, "non-ASCII data stream");
269 warning(stream
->pos
, "backslash-newline at end of file");
274 * We want that as light as possible while covering all normal cases.
275 * Slow path (including the logics with line-splicing and EOF sanity
276 * checks) is in nextchar_slow().
278 static inline int nextchar(stream_t
*stream
)
280 int offset
= stream
->offset
;
282 if (offset
< stream
->size
) {
283 int c
= stream
->buffer
[offset
++];
289 stream
->offset
= offset
;
291 stream
->pos
.newline
= 1;
295 if (offset
>= stream
->size
)
297 next
= stream
->buffer
[offset
];
298 if (next
== '\n' || next
== '\r')
302 stream
->offset
= offset
;
307 return nextchar_slow(stream
);
310 struct token eof_token_entry
;
312 static void mark_eof(stream_t
*stream
, struct token
*end_token
)
316 end
= alloc_token(stream
);
317 token_type(end
) = TOKEN_STREAMEND
;
318 end
->pos
.newline
= 1;
320 eof_token_entry
.next
= &eof_token_entry
;
321 eof_token_entry
.pos
.newline
= 1;
324 end_token
= &eof_token_entry
;
325 end
->next
= end_token
;
326 *stream
->tokenlist
= end
;
327 stream
->tokenlist
= NULL
;
330 static void add_token(stream_t
*stream
)
332 struct token
*token
= stream
->token
;
334 stream
->token
= NULL
;
336 *stream
->tokenlist
= token
;
337 stream
->tokenlist
= &token
->next
;
340 static void drop_token(stream_t
*stream
)
342 stream
->pos
.newline
|= stream
->token
->pos
.newline
;
343 stream
->pos
.whitespace
|= stream
->token
->pos
.whitespace
;
344 stream
->token
= NULL
;
356 static const long cclass
[257] = {
357 ['0' + 1 ... '9' + 1] = Digit
| Hex
,
358 ['A' + 1 ... 'D' + 1] = Letter
| Hex
,
359 ['E' + 1] = Letter
| Hex
| Exp
,
360 ['F' + 1] = Letter
| Hex
,
361 ['G' + 1 ... 'O' + 1] = Letter
,
362 ['P' + 1] = Letter
| Exp
,
363 ['Q' + 1 ... 'Z' + 1] = Letter
,
364 ['a' + 1 ... 'd' + 1] = Letter
| Hex
,
365 ['e' + 1] = Letter
| Hex
| Exp
,
366 ['f' + 1] = Letter
| Hex
,
367 ['g' + 1 ... 'o' + 1] = Letter
,
368 ['p' + 1] = Letter
| Exp
,
369 ['q' + 1 ... 'z' + 1] = Letter
,
371 ['.' + 1] = Dot
| ValidSecond
,
372 ['=' + 1] = ValidSecond
,
373 ['+' + 1] = ValidSecond
,
374 ['-' + 1] = ValidSecond
,
375 ['>' + 1] = ValidSecond
,
376 ['<' + 1] = ValidSecond
,
377 ['&' + 1] = ValidSecond
,
378 ['|' + 1] = ValidSecond
,
379 ['#' + 1] = ValidSecond
,
387 * pp-number identifier-nodigit
394 static int get_one_number(int c
, int next
, stream_t
*stream
)
397 static char buffer
[256];
398 char *p
= buffer
, *buf
;
403 long class = cclass
[next
+ 1];
404 if (!(class & (Dot
| Digit
| Letter
)))
407 next
= nextchar(stream
);
409 if (next
== '-' || next
== '+') {
411 next
= nextchar(stream
);
417 buf
= __alloc_bytes(len
);
418 memcpy(buf
, buffer
, len
);
420 token
= stream
->token
;
421 token_type(token
) = TOKEN_NUMBER
;
428 static int escapechar(int first
, int type
, stream_t
*stream
, int *valp
)
432 next
= nextchar(stream
);
436 warning(stream
->pos
, "Newline in string or character constant");
438 if (first
== '\\' && next
!= EOF
) {
440 next
= nextchar(stream
);
474 warning(stream
->pos
, "Newline in string or character constant");
479 while (next
>= '0' && next
<= '9') {
480 value
= (value
<< 3) + (next
-'0');
481 next
= nextchar(stream
);
489 int hex
= hexval(next
);
492 next
= nextchar(stream
);
493 while ((hex
= hexval(next
)) < 16) {
494 value
= (value
<< 4) + hex
;
495 next
= nextchar(stream
);
503 warning(stream
->pos
, "Unknown escape '%c'", value
);
506 /* Mark it as escaped */
513 static int get_char_token(int next
, stream_t
*stream
)
518 next
= escapechar(next
, '\'', stream
, &value
);
519 if (value
== '\'' || next
!= '\'') {
520 warning(stream
->pos
, "Bad character constant");
525 token
= stream
->token
;
526 token_type(token
) = TOKEN_CHAR
;
527 token
->character
= value
& 0xff;
530 return nextchar(stream
);
533 static int get_string_token(int next
, stream_t
*stream
)
535 static char buffer
[MAX_STRING
];
536 struct string
*string
;
542 next
= escapechar(next
, '"', stream
, &val
);
546 warning(stream
->pos
, "End of file in middle of string");
549 if (len
< MAX_STRING
)
554 if (len
> MAX_STRING
) {
555 warning(stream
->pos
, "string too long (%d bytes, %d bytes max)", len
, MAX_STRING
);
559 string
= __alloc_string(len
+1);
560 memcpy(string
->data
, buffer
, len
);
561 string
->data
[len
] = '\0';
562 string
->length
= len
+1;
565 token
= stream
->token
;
566 token_type(token
) = TOKEN_STRING
;
567 token
->string
= string
;
573 static int drop_stream_eoln(stream_t
*stream
)
575 int next
= nextchar(stream
);
581 next
= nextchar(stream
);
587 static int drop_stream_comment(stream_t
*stream
)
592 newline
= stream
->pos
.newline
;
594 next
= nextchar(stream
);
598 warning(stream
->pos
, "End of file in the middle of a comment");
601 next
= nextchar(stream
);
602 if (curr
== '*' && next
== '/')
605 stream
->pos
.newline
= newline
;
606 return nextchar(stream
);
609 unsigned char combinations
[][3] = COMBINATION_STRINGS
;
611 #define NR_COMBINATIONS (SPECIAL_ARG_SEPARATOR - SPECIAL_BASE)
613 static int get_one_special(int c
, stream_t
*stream
)
616 unsigned char c1
, c2
, c3
;
620 next
= nextchar(stream
);
623 * Check for numbers, strings, character constants, and comments
627 if (next
>= '0' && next
<= '9')
628 return get_one_number(c
, next
, stream
);
631 return get_string_token(next
, stream
);
633 return get_char_token(next
, stream
);
636 return drop_stream_eoln(stream
);
638 return drop_stream_comment(stream
);
642 * Check for combinations
645 if (cclass
[next
+ 1] & ValidSecond
) {
646 comb
= combinations
[0];
647 c1
= c
; c2
= next
; c3
= 0;
648 for (i
= 0; i
< NR_COMBINATIONS
; i
++) {
649 if (comb
[0] == c1
&& comb
[1] == c2
&& comb
[2] == c3
) {
650 value
= i
+ SPECIAL_BASE
;
651 next
= nextchar(stream
);
661 token
= stream
->token
;
662 token_type(token
) = TOKEN_SPECIAL
;
663 token
->special
= value
;
668 #define IDENT_HASH_BITS (10)
669 #define IDENT_HASH_SIZE (1<<IDENT_HASH_BITS)
670 #define IDENT_HASH_MASK (IDENT_HASH_SIZE-1)
672 #define ident_hash_init(c) (c)
673 #define ident_hash_add(oldhash,c) ((oldhash)*11 + (c))
674 #define ident_hash_end(hash) ((((hash) >> IDENT_HASH_BITS) + (hash)) & IDENT_HASH_MASK)
676 static struct ident
*hash_table
[IDENT_HASH_SIZE
];
677 int ident_hit
, ident_miss
;
679 void show_identifier_stats(void)
682 int distribution
[100];
684 fprintf(stderr
, "identifiers: %d hits, %d misses\n",
685 ident_hit
, ident_miss
);
687 for (i
= 0; i
< 100; i
++)
690 for (i
= 0; i
< IDENT_HASH_SIZE
; i
++) {
691 struct ident
* ident
= hash_table
[i
];
700 distribution
[count
]++;
703 for (i
= 0; i
< 100; i
++) {
705 fprintf(stderr
, "%2d: %d buckets\n", i
, distribution
[i
]);
709 static struct ident
*alloc_ident(const char *name
, int len
)
711 struct ident
*ident
= __alloc_ident(len
);
712 ident
->symbols
= NULL
;
715 memcpy(ident
->name
, name
, len
);
719 static struct ident
* insert_hash(struct ident
*ident
, unsigned long hash
)
721 ident
->next
= hash_table
[hash
];
722 hash_table
[hash
] = ident
;
727 static struct ident
*create_hashed_ident(const char *name
, int len
, unsigned long hash
)
732 p
= &hash_table
[hash
];
733 while ((ident
= *p
) != NULL
) {
734 if (ident
->len
== len
&& !memcmp(ident
->name
, name
, len
)) {
741 ident
= alloc_ident(name
, len
);
748 static unsigned long hash_name(const char *name
, int len
)
751 const unsigned char *p
= (const unsigned char *)name
;
753 hash
= ident_hash_init(*p
++);
755 unsigned int i
= *p
++;
756 hash
= ident_hash_add(hash
, i
);
758 return ident_hash_end(hash
);
761 struct ident
*hash_ident(struct ident
*ident
)
763 return insert_hash(ident
, hash_name(ident
->name
, ident
->len
));
766 struct ident
*built_in_ident(const char *name
)
768 int len
= strlen(name
);
769 return create_hashed_ident(name
, len
, hash_name(name
, len
));
772 struct token
*built_in_token(int stream
, const char *name
)
776 token
= __alloc_token(0);
777 token
->pos
.stream
= stream
;
778 token_type(token
) = TOKEN_IDENT
;
779 token
->ident
= built_in_ident(name
);
783 static int get_one_identifier(int c
, stream_t
*stream
)
792 hash
= ident_hash_init(c
);
795 next
= nextchar(stream
);
796 if (!(cclass
[next
+ 1] & (Letter
| Digit
)))
798 if (len
>= sizeof(buf
))
800 hash
= ident_hash_add(hash
, next
);
804 hash
= ident_hash_end(hash
);
806 ident
= create_hashed_ident(buf
, len
, hash
);
809 token
= stream
->token
;
810 token_type(token
) = TOKEN_IDENT
;
811 token
->ident
= ident
;
816 static int get_one_token(int c
, stream_t
*stream
)
818 long class = cclass
[c
+ 1];
820 return get_one_number(c
, nextchar(stream
), stream
);
822 return get_one_identifier(c
, stream
);
823 return get_one_special(c
, stream
);
826 static struct token
*setup_stream(stream_t
*stream
, int idx
, int fd
,
827 unsigned char *buf
, unsigned int buf_size
)
831 stream
->pos
.stream
= idx
;
832 stream
->pos
.line
= 1;
833 stream
->pos
.newline
= 1;
834 stream
->pos
.whitespace
= 0;
836 stream
->pos
.noexpand
= 0;
838 stream
->token
= NULL
;
841 stream
->size
= buf_size
;
842 stream
->buffer
= buf
;
844 begin
= alloc_token(stream
);
845 token_type(begin
) = TOKEN_STREAMBEGIN
;
846 stream
->tokenlist
= &begin
->next
;
850 static void tokenize_stream(stream_t
*stream
, struct token
*endtoken
)
852 int c
= nextchar(stream
);
855 struct token
*token
= alloc_token(stream
);
856 stream
->token
= token
;
857 stream
->pos
.newline
= 0;
858 stream
->pos
.whitespace
= 0;
859 c
= get_one_token(c
, stream
);
862 stream
->pos
.whitespace
= 1;
863 c
= nextchar(stream
);
865 mark_eof(stream
, endtoken
);
868 struct token
* tokenize_buffer(unsigned char *buffer
, unsigned long size
, struct token
*endtoken
)
873 begin
= setup_stream(&stream
, 0, -1, buffer
, size
);
874 tokenize_stream(&stream
, endtoken
);
878 struct token
* tokenize(const char *name
, int fd
, struct token
*endtoken
, const char **next_path
)
882 unsigned char buffer
[BUFSIZE
];
885 idx
= init_stream(name
, fd
, next_path
);
887 // info(endtoken->pos, "File %s is const", name);
891 begin
= setup_stream(&stream
, idx
, fd
, buffer
, 0);
892 tokenize_stream(&stream
, endtoken
);