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
26 int input_stream_nr
= 0;
27 struct stream
*input_streams
;
28 static int input_streams_allocated
;
30 #define BUFSIZE (8192)
35 int newline
, whitespace
;
36 struct token
**tokenlist
;
38 unsigned char *buffer
;
41 struct position
stream_pos(stream_t
*stream
)
45 pos
.stream
= stream
->nr
;
46 pos
.newline
= stream
->newline
;
47 pos
.whitespace
= stream
->whitespace
;
48 pos
.pos
= stream
->pos
;
49 pos
.line
= stream
->line
;
54 const char *show_special(int val
)
56 static const char *combinations
[] = COMBINATION_STRINGS
;
57 static char buffer
[4];
61 if (val
>= SPECIAL_BASE
)
62 strcpy(buffer
, combinations
[val
- SPECIAL_BASE
]);
66 const char *show_ident(const struct ident
*ident
)
68 static char buffer
[256];
71 sprintf(buffer
, "%.*s", ident
->len
, ident
->name
);
75 char *charstr(char *ptr
, unsigned char c
, unsigned char escape
, unsigned char next
)
78 if (c
== escape
|| c
== '\\')
93 return ptr
+ sprintf(ptr
, "%o", c
);
95 return ptr
+ sprintf(ptr
, "%03o", c
);
98 const char *show_string(const struct string
*string
)
100 static char buffer
[4 * MAX_STRING
+ 3];
105 return "<bad_string>";
108 for (i
= 0; i
< string
->length
-1; i
++) {
109 const unsigned char *p
= string
->data
+ i
;
110 ptr
= charstr(ptr
, p
[0], '"', p
[1]);
117 const char *show_token(const struct token
*token
)
119 static char buffer
[256];
123 switch (token_type(token
)) {
125 return "syntax error";
128 return "end-of-input";
131 return show_ident(token
->ident
);
134 return show_string(token
->string
);
137 return token
->number
;
140 return show_special(token
->special
);
144 int c
= token
->character
;
146 ptr
= charstr(ptr
, c
, '\'', 0);
152 case TOKEN_STREAMBEGIN
:
153 sprintf(buffer
, "<beginning of '%s'>", (input_streams
+ token
->pos
.stream
)->name
);
156 case TOKEN_STREAMEND
:
157 sprintf(buffer
, "<end of '%s'>", (input_streams
+ token
->pos
.stream
)->name
);
165 int init_stream(const char *name
, int fd
, const char **next_path
)
167 int stream
= input_stream_nr
;
168 struct stream
*current
;
171 if (stream
>= input_streams_allocated
) {
172 int newalloc
= stream
* 4 / 3 + 10;
173 input_streams
= realloc(input_streams
, newalloc
* sizeof(struct stream
));
175 die("Unable to allocate more streams space");
176 input_streams_allocated
= newalloc
;
178 current
= input_streams
+ stream
;
179 memset(current
, 0, sizeof(*current
));
180 current
->name
= name
;
182 current
->next_path
= next_path
;
183 current
->constant
= CONSTANT_FILE_MAYBE
;
184 if (fd
>= 0 && fstat(fd
, &st
) == 0 && S_ISREG(st
.st_mode
)) {
187 for (i
= 0; i
< stream
; i
++) {
188 struct stream
*s
= input_streams
+ i
;
189 if (s
->constant
== CONSTANT_FILE_YES
&&
190 identical_files(s
, &st
, name
) &&
191 lookup_symbol(s
->protect
, NS_MACRO
))
195 current
->dev
= st
.st_dev
;
196 current
->ino
= st
.st_ino
;
198 input_stream_nr
= stream
+1;
202 static struct token
* alloc_token(stream_t
*stream
)
204 struct token
*token
= __alloc_token(0);
205 token
->pos
= stream_pos(stream
);
210 * Argh... That was surprisingly messy - handling '\r' complicates the
213 static int nextchar_slow(stream_t
*stream
)
215 int offset
= stream
->offset
;
216 int size
= stream
->size
;
218 int spliced
= 0, had_cr
, had_backslash
, complain
;
221 had_cr
= had_backslash
= complain
= 0;
224 if (offset
>= size
) {
225 size
= read(stream
->fd
, stream
->buffer
, BUFSIZE
);
229 stream
->offset
= offset
= 0;
232 c
= stream
->buffer
[offset
++];
234 if (had_cr
&& c
!= '\n')
249 if (!had_backslash
) {
259 warning(stream_pos(stream
), "non-ASCII data stream");
269 stream
->offset
= offset
;
271 warning(stream_pos(stream
), "non-ASCII data stream");
281 warning(stream_pos(stream
), "no newline at end of file");
283 warning(stream_pos(stream
), "non-ASCII data stream");
285 warning(stream_pos(stream
), "backslash-newline at end of file");
290 * We want that as light as possible while covering all normal cases.
291 * Slow path (including the logics with line-splicing and EOF sanity
292 * checks) is in nextchar_slow().
294 static int nextchar(stream_t
*stream
)
296 int offset
= stream
->offset
;
298 if (offset
< stream
->size
) {
299 int c
= stream
->buffer
[offset
++];
300 static const char special
[256] = {
301 ['\r'] = 1, ['\n'] = 1, ['\\'] = 1
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
->newline
|= stream
->token
->pos
.newline
;
345 stream
->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(stream
), "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(stream
), "Newline in string or character constant");
451 if (first
== '\\' && next
!= EOF
) {
453 next
= nextchar(stream
);
487 warning(stream_pos(stream
), "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(stream
), "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(stream
), "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(stream
), "End of file in middle of string");
562 if (len
< MAX_STRING
)
567 if (len
> MAX_STRING
) {
568 warning(stream_pos(stream
), "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
->newline
;
607 next
= nextchar(stream
);
611 warning(stream_pos(stream
), "End of file in the middle of a comment");
614 next
= nextchar(stream
);
615 if (curr
== '*' && next
== '/')
618 stream
->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
== (unsigned char) len
) {
748 const char *n
= name
;
749 const char *m
= ident
->name
;
765 ident
= alloc_ident(name
, len
);
773 static unsigned long hash_name(const char *name
, int len
)
776 const unsigned char *p
= (const unsigned char *)name
;
778 hash
= ident_hash_init(*p
++);
780 unsigned int i
= *p
++;
781 hash
= ident_hash_add(hash
, i
);
783 return ident_hash_end(hash
);
786 struct ident
*hash_ident(struct ident
*ident
)
788 return insert_hash(ident
, hash_name(ident
->name
, ident
->len
));
791 struct ident
*built_in_ident(const char *name
)
793 int len
= strlen(name
);
794 return create_hashed_ident(name
, len
, hash_name(name
, len
));
797 struct token
*built_in_token(int stream
, const char *name
)
801 token
= __alloc_token(0);
802 token
->pos
.stream
= stream
;
803 token_type(token
) = TOKEN_IDENT
;
804 token
->ident
= built_in_ident(name
);
808 static int get_one_identifier(int c
, stream_t
*stream
)
817 hash
= ident_hash_init(c
);
820 next
= nextchar(stream
);
821 if (!(cclass
[next
+ 1] & (Letter
| Digit
)))
823 if (len
>= sizeof(buf
))
825 hash
= ident_hash_add(hash
, next
);
829 hash
= ident_hash_end(hash
);
831 ident
= create_hashed_ident(buf
, len
, hash
);
834 token
= stream
->token
;
835 token_type(token
) = TOKEN_IDENT
;
836 token
->ident
= ident
;
841 static int get_one_token(int c
, stream_t
*stream
)
843 long class = cclass
[c
+ 1];
845 return get_one_number(c
, nextchar(stream
), stream
);
847 return get_one_identifier(c
, stream
);
848 return get_one_special(c
, stream
);
851 static struct token
*setup_stream(stream_t
*stream
, int idx
, int fd
,
852 unsigned char *buf
, unsigned int buf_size
)
859 stream
->whitespace
= 0;
862 stream
->token
= NULL
;
865 stream
->size
= buf_size
;
866 stream
->buffer
= buf
;
868 begin
= alloc_token(stream
);
869 token_type(begin
) = TOKEN_STREAMBEGIN
;
870 stream
->tokenlist
= &begin
->next
;
874 static void tokenize_stream(stream_t
*stream
, struct token
*endtoken
)
876 int c
= nextchar(stream
);
879 struct token
*token
= alloc_token(stream
);
880 stream
->token
= token
;
882 stream
->whitespace
= 0;
883 c
= get_one_token(c
, stream
);
886 stream
->whitespace
= 1;
887 c
= nextchar(stream
);
889 mark_eof(stream
, endtoken
);
892 struct token
* tokenize_buffer(unsigned char *buffer
, unsigned long size
, struct token
*endtoken
)
897 begin
= setup_stream(&stream
, 0, -1, buffer
, size
);
898 tokenize_stream(&stream
, endtoken
);
902 struct token
* tokenize(const char *name
, int fd
, struct token
*endtoken
, const char **next_path
)
906 unsigned char buffer
[BUFSIZE
];
909 idx
= init_stream(name
, fd
, next_path
);
911 // info(endtoken->pos, "File %s is const", name);
915 begin
= setup_stream(&stream
, idx
, fd
, buffer
, 0);
916 tokenize_stream(&stream
, endtoken
);