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
[4 * MAX_STRING
+ 3];
91 return "<bad_string>";
94 for (i
= 0; i
< string
->length
-1; i
++) {
95 const unsigned char *p
= string
->data
+ i
;
96 ptr
= charstr(ptr
, p
[0], '"', p
[1]);
103 const char *show_token(const struct token
*token
)
105 static char buffer
[256];
109 switch (token_type(token
)) {
111 return "syntax error";
114 return "end-of-input";
117 return show_ident(token
->ident
);
120 return show_string(token
->string
);
123 return token
->number
;
126 return show_special(token
->special
);
130 int c
= token
->character
;
132 ptr
= charstr(ptr
, c
, '\'', 0);
138 case TOKEN_STREAMBEGIN
:
139 sprintf(buffer
, "<beginning of '%s'>", (input_streams
+ token
->pos
.stream
)->name
);
142 case TOKEN_STREAMEND
:
143 sprintf(buffer
, "<end of '%s'>", (input_streams
+ token
->pos
.stream
)->name
);
151 int init_stream(const char *name
, int fd
, const char **next_path
)
153 int stream
= input_stream_nr
;
154 struct stream
*current
;
157 if (stream
>= input_streams_allocated
) {
158 int newalloc
= stream
* 4 / 3 + 10;
159 input_streams
= realloc(input_streams
, newalloc
* sizeof(struct stream
));
161 die("Unable to allocate more streams space");
162 input_streams_allocated
= newalloc
;
164 current
= input_streams
+ stream
;
165 memset(current
, 0, sizeof(*current
));
166 current
->name
= name
;
168 current
->next_path
= next_path
;
169 current
->constant
= CONSTANT_FILE_MAYBE
;
170 if (fd
>= 0 && fstat(fd
, &st
) == 0 && S_ISREG(st
.st_mode
)) {
173 for (i
= 0; i
< stream
; i
++) {
174 struct stream
*s
= input_streams
+ i
;
175 if (s
->constant
== CONSTANT_FILE_YES
&&
176 identical_files(s
, &st
, name
) &&
177 lookup_symbol(s
->protect
, NS_MACRO
))
181 current
->dev
= st
.st_dev
;
182 current
->ino
= st
.st_ino
;
184 input_stream_nr
= stream
+1;
188 static struct token
* alloc_token(stream_t
*stream
)
190 struct token
*token
= __alloc_token(0);
191 token
->pos
= stream
->pos
;
196 * Argh... That was surprisingly messy - handling '\r' complicates the
199 static int nextchar_slow(stream_t
*stream
)
201 int offset
= stream
->offset
;
202 int size
= stream
->size
;
204 int spliced
= 0, had_cr
, had_backslash
, complain
;
207 had_cr
= had_backslash
= complain
= 0;
210 if (offset
>= size
) {
211 size
= read(stream
->fd
, stream
->buffer
, BUFSIZE
);
215 stream
->offset
= offset
= 0;
218 c
= stream
->buffer
[offset
++];
220 if (had_cr
&& c
!= '\n')
235 if (!had_backslash
) {
241 stream
->pos
.newline
= 1;
245 warning(stream
->pos
, "non-ASCII data stream");
255 stream
->offset
= offset
;
257 warning(stream
->pos
, "non-ASCII data stream");
267 warning(stream
->pos
, "no newline at end of file");
269 warning(stream
->pos
, "non-ASCII data stream");
271 warning(stream
->pos
, "backslash-newline at end of file");
276 * We want that as light as possible while covering all normal cases.
277 * Slow path (including the logics with line-splicing and EOF sanity
278 * checks) is in nextchar_slow().
280 static inline int nextchar(stream_t
*stream
)
282 int offset
= stream
->offset
;
284 if (offset
< stream
->size
) {
285 int c
= stream
->buffer
[offset
++];
291 stream
->offset
= offset
;
293 stream
->pos
.newline
= 1;
297 if (offset
>= stream
->size
)
299 next
= stream
->buffer
[offset
];
300 if (next
== '\n' || next
== '\r')
304 stream
->offset
= offset
;
309 return nextchar_slow(stream
);
312 struct token eof_token_entry
;
314 static void mark_eof(stream_t
*stream
, struct token
*end_token
)
318 end
= alloc_token(stream
);
319 token_type(end
) = TOKEN_STREAMEND
;
320 end
->pos
.newline
= 1;
322 eof_token_entry
.next
= &eof_token_entry
;
323 eof_token_entry
.pos
.newline
= 1;
326 end_token
= &eof_token_entry
;
327 end
->next
= end_token
;
328 *stream
->tokenlist
= end
;
329 stream
->tokenlist
= NULL
;
332 static void add_token(stream_t
*stream
)
334 struct token
*token
= stream
->token
;
336 stream
->token
= NULL
;
338 *stream
->tokenlist
= token
;
339 stream
->tokenlist
= &token
->next
;
342 static void drop_token(stream_t
*stream
)
344 stream
->pos
.newline
|= stream
->token
->pos
.newline
;
345 stream
->pos
.whitespace
|= stream
->token
->pos
.whitespace
;
346 stream
->token
= NULL
;
358 static const long cclass
[257] = {
359 ['0' + 1 ... '9' + 1] = Digit
| Hex
,
360 ['A' + 1 ... 'D' + 1] = Letter
| Hex
,
361 ['E' + 1] = Letter
| Hex
| Exp
,
362 ['F' + 1] = Letter
| Hex
,
363 ['G' + 1 ... 'O' + 1] = Letter
,
364 ['P' + 1] = Letter
| Exp
,
365 ['Q' + 1 ... 'Z' + 1] = Letter
,
366 ['a' + 1 ... 'd' + 1] = Letter
| Hex
,
367 ['e' + 1] = Letter
| Hex
| Exp
,
368 ['f' + 1] = Letter
| Hex
,
369 ['g' + 1 ... 'o' + 1] = Letter
,
370 ['p' + 1] = Letter
| Exp
,
371 ['q' + 1 ... 'z' + 1] = Letter
,
373 ['.' + 1] = Dot
| ValidSecond
,
374 ['=' + 1] = ValidSecond
,
375 ['+' + 1] = ValidSecond
,
376 ['-' + 1] = ValidSecond
,
377 ['>' + 1] = ValidSecond
,
378 ['<' + 1] = ValidSecond
,
379 ['&' + 1] = ValidSecond
,
380 ['|' + 1] = ValidSecond
,
381 ['#' + 1] = ValidSecond
,
389 * pp-number identifier-nodigit
396 static int get_one_number(int c
, int next
, stream_t
*stream
)
399 static char buffer
[4095];
400 char *p
= buffer
, *buf
, *buffer_end
= buffer
+ sizeof (buffer
);
405 long class = cclass
[next
+ 1];
406 if (!(class & (Dot
| Digit
| Letter
)))
410 next
= nextchar(stream
);
412 if (next
== '-' || next
== '+') {
415 next
= nextchar(stream
);
420 if (p
== buffer_end
) {
421 error(stream
->pos
, "number token exceeds %td characters",
422 buffer_end
- buffer
);
423 // Pretend we saw just "1".
430 buf
= __alloc_bytes(len
);
431 memcpy(buf
, buffer
, len
);
433 token
= stream
->token
;
434 token_type(token
) = TOKEN_NUMBER
;
441 static int escapechar(int first
, int type
, stream_t
*stream
, int *valp
)
445 next
= nextchar(stream
);
449 warning(stream
->pos
, "Newline in string or character constant");
451 if (first
== '\\' && next
!= EOF
) {
453 next
= nextchar(stream
);
487 warning(stream
->pos
, "Newline in string or character constant");
492 while (next
>= '0' && next
<= '9') {
493 value
= (value
<< 3) + (next
-'0');
494 next
= nextchar(stream
);
502 int hex
= hexval(next
);
505 next
= nextchar(stream
);
506 while ((hex
= hexval(next
)) < 16) {
507 value
= (value
<< 4) + hex
;
508 next
= nextchar(stream
);
516 warning(stream
->pos
, "Unknown escape '%c'", value
);
519 /* Mark it as escaped */
526 static int get_char_token(int next
, stream_t
*stream
)
531 next
= escapechar(next
, '\'', stream
, &value
);
532 if (value
== '\'' || next
!= '\'') {
533 warning(stream
->pos
, "Bad character constant");
538 token
= stream
->token
;
539 token_type(token
) = TOKEN_CHAR
;
540 token
->character
= value
& 0xff;
543 return nextchar(stream
);
546 static int get_string_token(int next
, stream_t
*stream
)
548 static char buffer
[MAX_STRING
];
549 struct string
*string
;
555 next
= escapechar(next
, '"', stream
, &val
);
559 warning(stream
->pos
, "End of file in middle of string");
562 if (len
< MAX_STRING
)
567 if (len
> MAX_STRING
) {
568 warning(stream
->pos
, "string too long (%d bytes, %d bytes max)", len
, MAX_STRING
);
572 string
= __alloc_string(len
+1);
573 memcpy(string
->data
, buffer
, len
);
574 string
->data
[len
] = '\0';
575 string
->length
= len
+1;
578 token
= stream
->token
;
579 token_type(token
) = TOKEN_STRING
;
580 token
->string
= string
;
586 static int drop_stream_eoln(stream_t
*stream
)
588 int next
= nextchar(stream
);
594 next
= nextchar(stream
);
600 static int drop_stream_comment(stream_t
*stream
)
605 newline
= stream
->pos
.newline
;
607 next
= nextchar(stream
);
611 warning(stream
->pos
, "End of file in the middle of a comment");
614 next
= nextchar(stream
);
615 if (curr
== '*' && next
== '/')
618 stream
->pos
.newline
= newline
;
619 return nextchar(stream
);
622 unsigned char combinations
[][3] = COMBINATION_STRINGS
;
624 #define NR_COMBINATIONS (SPECIAL_ARG_SEPARATOR - SPECIAL_BASE)
626 static int get_one_special(int c
, stream_t
*stream
)
629 unsigned char c1
, c2
, c3
;
633 next
= nextchar(stream
);
636 * Check for numbers, strings, character constants, and comments
640 if (next
>= '0' && next
<= '9')
641 return get_one_number(c
, next
, stream
);
644 return get_string_token(next
, stream
);
646 return get_char_token(next
, stream
);
649 return drop_stream_eoln(stream
);
651 return drop_stream_comment(stream
);
655 * Check for combinations
658 if (cclass
[next
+ 1] & ValidSecond
) {
659 comb
= combinations
[0];
660 c1
= c
; c2
= next
; c3
= 0;
661 for (i
= 0; i
< NR_COMBINATIONS
; i
++) {
662 if (comb
[0] == c1
&& comb
[1] == c2
&& comb
[2] == c3
) {
663 value
= i
+ SPECIAL_BASE
;
664 next
= nextchar(stream
);
674 token
= stream
->token
;
675 token_type(token
) = TOKEN_SPECIAL
;
676 token
->special
= value
;
681 #define IDENT_HASH_BITS (13)
682 #define IDENT_HASH_SIZE (1<<IDENT_HASH_BITS)
683 #define IDENT_HASH_MASK (IDENT_HASH_SIZE-1)
685 #define ident_hash_init(c) (c)
686 #define ident_hash_add(oldhash,c) ((oldhash)*11 + (c))
687 #define ident_hash_end(hash) ((((hash) >> IDENT_HASH_BITS) + (hash)) & IDENT_HASH_MASK)
689 static struct ident
*hash_table
[IDENT_HASH_SIZE
];
690 int ident_hit
, ident_miss
, idents
;
692 void show_identifier_stats(void)
695 int distribution
[100];
697 fprintf(stderr
, "identifiers: %d hits, %d misses\n",
698 ident_hit
, ident_miss
);
700 for (i
= 0; i
< 100; i
++)
703 for (i
= 0; i
< IDENT_HASH_SIZE
; i
++) {
704 struct ident
* ident
= hash_table
[i
];
713 distribution
[count
]++;
716 for (i
= 0; i
< 100; i
++) {
718 fprintf(stderr
, "%2d: %d buckets\n", i
, distribution
[i
]);
722 static struct ident
*alloc_ident(const char *name
, int len
)
724 struct ident
*ident
= __alloc_ident(len
);
725 ident
->symbols
= NULL
;
728 memcpy(ident
->name
, name
, len
);
732 static struct ident
* insert_hash(struct ident
*ident
, unsigned long hash
)
734 ident
->next
= hash_table
[hash
];
735 hash_table
[hash
] = ident
;
740 static struct ident
*create_hashed_ident(const char *name
, int len
, unsigned long hash
)
745 p
= &hash_table
[hash
];
746 while ((ident
= *p
) != NULL
) {
747 if (ident
->len
== len
&& !memcmp(ident
->name
, name
, len
)) {
754 ident
= alloc_ident(name
, len
);
762 static unsigned long hash_name(const char *name
, int len
)
765 const unsigned char *p
= (const unsigned char *)name
;
767 hash
= ident_hash_init(*p
++);
769 unsigned int i
= *p
++;
770 hash
= ident_hash_add(hash
, i
);
772 return ident_hash_end(hash
);
775 struct ident
*hash_ident(struct ident
*ident
)
777 return insert_hash(ident
, hash_name(ident
->name
, ident
->len
));
780 struct ident
*built_in_ident(const char *name
)
782 int len
= strlen(name
);
783 return create_hashed_ident(name
, len
, hash_name(name
, len
));
786 struct token
*built_in_token(int stream
, const char *name
)
790 token
= __alloc_token(0);
791 token
->pos
.stream
= stream
;
792 token_type(token
) = TOKEN_IDENT
;
793 token
->ident
= built_in_ident(name
);
797 static int get_one_identifier(int c
, stream_t
*stream
)
806 hash
= ident_hash_init(c
);
809 next
= nextchar(stream
);
810 if (!(cclass
[next
+ 1] & (Letter
| Digit
)))
812 if (len
>= sizeof(buf
))
814 hash
= ident_hash_add(hash
, next
);
818 hash
= ident_hash_end(hash
);
820 ident
= create_hashed_ident(buf
, len
, hash
);
823 token
= stream
->token
;
824 token_type(token
) = TOKEN_IDENT
;
825 token
->ident
= ident
;
830 static int get_one_token(int c
, stream_t
*stream
)
832 long class = cclass
[c
+ 1];
834 return get_one_number(c
, nextchar(stream
), stream
);
836 return get_one_identifier(c
, stream
);
837 return get_one_special(c
, stream
);
840 static struct token
*setup_stream(stream_t
*stream
, int idx
, int fd
,
841 unsigned char *buf
, unsigned int buf_size
)
845 stream
->pos
.stream
= idx
;
846 stream
->pos
.line
= 1;
847 stream
->pos
.newline
= 1;
848 stream
->pos
.whitespace
= 0;
850 stream
->pos
.noexpand
= 0;
852 stream
->token
= NULL
;
855 stream
->size
= buf_size
;
856 stream
->buffer
= buf
;
858 begin
= alloc_token(stream
);
859 token_type(begin
) = TOKEN_STREAMBEGIN
;
860 stream
->tokenlist
= &begin
->next
;
864 static void tokenize_stream(stream_t
*stream
, struct token
*endtoken
)
866 int c
= nextchar(stream
);
869 struct token
*token
= alloc_token(stream
);
870 stream
->token
= token
;
871 stream
->pos
.newline
= 0;
872 stream
->pos
.whitespace
= 0;
873 c
= get_one_token(c
, stream
);
876 stream
->pos
.whitespace
= 1;
877 c
= nextchar(stream
);
879 mark_eof(stream
, endtoken
);
882 struct token
* tokenize_buffer(unsigned char *buffer
, unsigned long size
, struct token
*endtoken
)
887 begin
= setup_stream(&stream
, 0, -1, buffer
, size
);
888 tokenize_stream(&stream
, endtoken
);
892 struct token
* tokenize(const char *name
, int fd
, struct token
*endtoken
, const char **next_path
)
896 unsigned char buffer
[BUFSIZE
];
899 idx
= init_stream(name
, fd
, next_path
);
901 // info(endtoken->pos, "File %s is const", name);
905 begin
= setup_stream(&stream
, idx
, fd
, buffer
, 0);
906 tokenize_stream(&stream
, endtoken
);