xref: /illumos-gate/usr/src/tools/smatch/src/tokenize.c (revision 6523a3aa7f325d64841382707603be7a86e68147)
1 /*
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.
4  *
5  * Copyright (C) 2003 Transmeta Corp.
6  *               2003 Linus Torvalds
7  *
8  * Permission is hereby granted, free of charge, to any person obtaining a copy
9  * of this software and associated documentation files (the "Software"), to deal
10  * in the Software without restriction, including without limitation the rights
11  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12  * copies of the Software, and to permit persons to whom the Software is
13  * furnished to do so, subject to the following conditions:
14  *
15  * The above copyright notice and this permission notice shall be included in
16  * all copies or substantial portions of the Software.
17  *
18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24  * THE SOFTWARE.
25  */
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <stdarg.h>
29 #include <stddef.h>
30 #include <string.h>
31 #include <ctype.h>
32 #include <unistd.h>
33 #include <stdint.h>
34 
35 #include "lib.h"
36 #include "allocate.h"
37 #include "token.h"
38 #include "symbol.h"
39 
40 #define EOF (-1)
41 
42 int input_stream_nr = 0;
43 struct stream *input_streams;
44 static int input_streams_allocated;
45 unsigned int tabstop = 8;
46 int no_lineno = 0;
47 
48 #define BUFSIZE (8192)
49 
50 typedef struct {
51 	int fd, offset, size;
52 	int pos, line, nr;
53 	int newline, whitespace;
54 	struct token **tokenlist;
55 	struct token *token;
56 	unsigned char *buffer;
57 } stream_t;
58 
stream_name(int stream)59 const char *stream_name(int stream)
60 {
61 	if (stream < 0 || stream > input_stream_nr)
62 		return "<bad stream>";
63 	return input_streams[stream].name;
64 }
65 
stream_pos(stream_t * stream)66 static struct position stream_pos(stream_t *stream)
67 {
68 	struct position pos;
69 	pos.type = 0;
70 	pos.stream = stream->nr;
71 	pos.newline = stream->newline;
72 	pos.whitespace = stream->whitespace;
73 	pos.pos = stream->pos;
74 
75 	pos.line = stream->line;
76 	if (no_lineno)
77 		pos.line = 123456;
78 
79 	pos.noexpand = 0;
80 	return pos;
81 }
82 
show_special(int val)83 const char *show_special(int val)
84 {
85 	static char buffer[4];
86 
87 	buffer[0] = val;
88 	buffer[1] = 0;
89 	if (val >= SPECIAL_BASE)
90 		strcpy(buffer, (char *) combinations[val - SPECIAL_BASE]);
91 	return buffer;
92 }
93 
show_ident(const struct ident * ident)94 const char *show_ident(const struct ident *ident)
95 {
96 	static char buff[4][256];
97 	static int n;
98 	char *buffer;
99 
100 	if (!ident)
101 		return "<noident>";
102 	buffer = buff[3 & ++n];
103 	sprintf(buffer, "%.*s", ident->len, ident->name);
104 	return buffer;
105 }
106 
charstr(char * ptr,unsigned char c,unsigned char escape,unsigned char next)107 static char *charstr(char *ptr, unsigned char c, unsigned char escape, unsigned char next)
108 {
109 	if (isprint(c)) {
110 		if (c == escape || c == '\\')
111 			*ptr++ = '\\';
112 		*ptr++ = c;
113 		return ptr;
114 	}
115 	*ptr++ = '\\';
116 	switch (c) {
117 	case '\n':
118 		*ptr++ = 'n';
119 		return ptr;
120 	case '\t':
121 		*ptr++ = 't';
122 		return ptr;
123 	}
124 	if (!isdigit(next))
125 		return ptr + sprintf(ptr, "%o", c);
126 
127 	return ptr + sprintf(ptr, "%03o", c);
128 }
129 
show_string(const struct string * string)130 const char *show_string(const struct string *string)
131 {
132 	static char buffer[4 * MAX_STRING + 3];
133 	char *ptr;
134 	int i;
135 
136 	if (!string || !string->length)
137 		return "<bad_string>";
138 	ptr = buffer;
139 	*ptr++ = '"';
140 	for (i = 0; i < string->length-1; i++) {
141 		const char *p = string->data + i;
142 		ptr = charstr(ptr, p[0], '"', p[1]);
143 	}
144 	*ptr++ = '"';
145 	*ptr = '\0';
146 	return buffer;
147 }
148 
show_char(const char * s,size_t len,char prefix,char delim)149 static const char *show_char(const char *s, size_t len, char prefix, char delim)
150 {
151 	static char buffer[MAX_STRING + 4];
152 	char *p = buffer;
153 	if (prefix)
154 		*p++ = prefix;
155 	*p++ = delim;
156 	memcpy(p, s, len);
157 	p += len;
158 	*p++ = delim;
159 	*p++ = '\0';
160 	return buffer;
161 }
162 
quote_char(const char * s,size_t len,char prefix,char delim)163 static const char *quote_char(const char *s, size_t len, char prefix, char delim)
164 {
165 	static char buffer[2*MAX_STRING + 6];
166 	size_t i;
167 	char *p = buffer;
168 	if (prefix)
169 		*p++ = prefix;
170 	if (delim == '"')
171 		*p++ = '\\';
172 	*p++ = delim;
173 	for (i = 0; i < len; i++) {
174 		if (s[i] == '"' || s[i] == '\\')
175 			*p++ = '\\';
176 		*p++ = s[i];
177 	}
178 	if (delim == '"')
179 		*p++ = '\\';
180 	*p++ = delim;
181 	*p++ = '\0';
182 	return buffer;
183 }
184 
show_token(const struct token * token)185 const char *show_token(const struct token *token)
186 {
187 	static char buffer[256];
188 
189 	if (!token)
190 		return "<no token>";
191 	switch (token_type(token)) {
192 	case TOKEN_ERROR:
193 		return "syntax error";
194 
195 	case TOKEN_EOF:
196 		return "end-of-input";
197 
198 	case TOKEN_IDENT:
199 		return show_ident(token->ident);
200 
201 	case TOKEN_NUMBER:
202 		return token->number;
203 
204 	case TOKEN_SPECIAL:
205 		return show_special(token->special);
206 
207 	case TOKEN_CHAR:
208 		return show_char(token->string->data,
209 			token->string->length - 1, 0, '\'');
210 	case TOKEN_CHAR_EMBEDDED_0 ... TOKEN_CHAR_EMBEDDED_3:
211 		return show_char(token->embedded,
212 			token_type(token) - TOKEN_CHAR, 0, '\'');
213 	case TOKEN_WIDE_CHAR:
214 		return show_char(token->string->data,
215 			token->string->length - 1, 'L', '\'');
216 	case TOKEN_WIDE_CHAR_EMBEDDED_0 ... TOKEN_WIDE_CHAR_EMBEDDED_3:
217 		return show_char(token->embedded,
218 			token_type(token) - TOKEN_WIDE_CHAR, 'L', '\'');
219 	case TOKEN_STRING:
220 		return show_char(token->string->data,
221 			token->string->length - 1, 0, '"');
222 	case TOKEN_WIDE_STRING:
223 		return show_char(token->string->data,
224 			token->string->length - 1, 'L', '"');
225 
226 	case TOKEN_STREAMBEGIN:
227 		sprintf(buffer, "<beginning of '%s'>", stream_name(token->pos.stream));
228 		return buffer;
229 
230 	case TOKEN_STREAMEND:
231 		sprintf(buffer, "<end of '%s'>", stream_name(token->pos.stream));
232 		return buffer;
233 
234 	case TOKEN_UNTAINT:
235 		sprintf(buffer, "<untaint>");
236 		return buffer;
237 
238 	case TOKEN_ARG_COUNT:
239 		sprintf(buffer, "<argcnt>");
240 		return buffer;
241 
242 	default:
243 		sprintf(buffer, "unhandled token type '%d' ", token_type(token));
244 		return buffer;
245 	}
246 }
247 
quote_token(const struct token * token)248 const char *quote_token(const struct token *token)
249 {
250 	static char buffer[256];
251 
252 	switch (token_type(token)) {
253 	case TOKEN_ERROR:
254 		return "syntax error";
255 
256 	case TOKEN_IDENT:
257 		return show_ident(token->ident);
258 
259 	case TOKEN_NUMBER:
260 		return token->number;
261 
262 	case TOKEN_SPECIAL:
263 		return show_special(token->special);
264 
265 	case TOKEN_CHAR:
266 		return quote_char(token->string->data,
267 			token->string->length - 1, 0, '\'');
268 	case TOKEN_CHAR_EMBEDDED_0 ... TOKEN_CHAR_EMBEDDED_3:
269 		return quote_char(token->embedded,
270 			token_type(token) - TOKEN_CHAR, 0, '\'');
271 	case TOKEN_WIDE_CHAR:
272 		return quote_char(token->string->data,
273 			token->string->length - 1, 'L', '\'');
274 	case TOKEN_WIDE_CHAR_EMBEDDED_0 ... TOKEN_WIDE_CHAR_EMBEDDED_3:
275 		return quote_char(token->embedded,
276 			token_type(token) - TOKEN_WIDE_CHAR, 'L', '\'');
277 	case TOKEN_STRING:
278 		return quote_char(token->string->data,
279 			token->string->length - 1, 0, '"');
280 	case TOKEN_WIDE_STRING:
281 		return quote_char(token->string->data,
282 			token->string->length - 1, 'L', '"');
283 	default:
284 		sprintf(buffer, "unhandled token type '%d' ", token_type(token));
285 		return buffer;
286 	}
287 }
288 
289 #define HASHED_INPUT_BITS (6)
290 #define HASHED_INPUT (1 << HASHED_INPUT_BITS)
291 #define HASH_PRIME 0x9e370001UL
292 
293 static int input_stream_hashes[HASHED_INPUT] = { [0 ... HASHED_INPUT-1] = -1 };
294 
hash_stream(const char * name)295 int *hash_stream(const char *name)
296 {
297 	uint32_t hash = 0;
298 	unsigned char c;
299 
300 	while ((c = *name++) != 0)
301 		hash = (hash + (c << 4) + (c >> 4)) * 11;
302 
303 	hash *= HASH_PRIME;
304 	hash >>= 32 - HASHED_INPUT_BITS;
305 	return input_stream_hashes + hash;
306 }
307 
init_stream(const char * name,int fd,const char ** next_path)308 int init_stream(const char *name, int fd, const char **next_path)
309 {
310 	int stream = input_stream_nr, *hash;
311 	struct stream *current;
312 
313 	if (stream >= input_streams_allocated) {
314 		int newalloc = stream * 4 / 3 + 10;
315 		input_streams = realloc(input_streams, newalloc * sizeof(struct stream));
316 		if (!input_streams)
317 			die("Unable to allocate more streams space");
318 		input_streams_allocated = newalloc;
319 	}
320 	current = input_streams + stream;
321 	memset(current, 0, sizeof(*current));
322 	current->name = name;
323 	current->fd = fd;
324 	current->next_path = next_path;
325 	current->path = NULL;
326 	current->constant = CONSTANT_FILE_MAYBE;
327 	input_stream_nr = stream+1;
328 	hash = hash_stream(name);
329 	current->next_stream = *hash;
330 	*hash = stream;
331 	return stream;
332 }
333 
alloc_token(stream_t * stream)334 static struct token * alloc_token(stream_t *stream)
335 {
336 	struct token *token = __alloc_token(0);
337 	token->pos = stream_pos(stream);
338 	return token;
339 }
340 
341 /*
342  *  Argh...  That was surprisingly messy - handling '\r' complicates the
343  *  things a _lot_.
344  */
nextchar_slow(stream_t * stream)345 static int nextchar_slow(stream_t *stream)
346 {
347 	int offset = stream->offset;
348 	int size = stream->size;
349 	int c;
350 	int spliced = 0, had_cr, had_backslash;
351 
352 restart:
353 	had_cr = had_backslash = 0;
354 
355 repeat:
356 	if (offset >= size) {
357 		if (stream->fd < 0)
358 			goto got_eof;
359 		size = read(stream->fd, stream->buffer, BUFSIZE);
360 		if (size <= 0)
361 			goto got_eof;
362 		stream->size = size;
363 		stream->offset = offset = 0;
364 	}
365 
366 	c = stream->buffer[offset++];
367 	if (had_cr)
368 		goto check_lf;
369 
370 	if (c == '\r') {
371 		had_cr = 1;
372 		goto repeat;
373 	}
374 
375 norm:
376 	if (!had_backslash) {
377 		switch (c) {
378 		case '\t':
379 			stream->pos += tabstop - stream->pos % tabstop;
380 			break;
381 		case '\n':
382 			stream->line++;
383 			stream->pos = 0;
384 			stream->newline = 1;
385 			break;
386 		case '\\':
387 			had_backslash = 1;
388 			stream->pos++;
389 			goto repeat;
390 		default:
391 			stream->pos++;
392 		}
393 	} else {
394 		if (c == '\n') {
395 			stream->line++;
396 			stream->pos = 0;
397 			spliced = 1;
398 			goto restart;
399 		}
400 		offset--;
401 		c = '\\';
402 	}
403 out:
404 	stream->offset = offset;
405 
406 	return c;
407 
408 check_lf:
409 	if (c != '\n')
410 		offset--;
411 	c = '\n';
412 	goto norm;
413 
414 got_eof:
415 	if (had_backslash) {
416 		c = '\\';
417 		goto out;
418 	}
419 	if (stream->pos)
420 		warning(stream_pos(stream), "no newline at end of file");
421 	else if (spliced)
422 		warning(stream_pos(stream), "backslash-newline at end of file");
423 	return EOF;
424 }
425 
426 /*
427  *  We want that as light as possible while covering all normal cases.
428  *  Slow path (including the logics with line-splicing and EOF sanity
429  *  checks) is in nextchar_slow().
430  */
nextchar(stream_t * stream)431 static inline int nextchar(stream_t *stream)
432 {
433 	int offset = stream->offset;
434 
435 	if (offset < stream->size) {
436 		int c = stream->buffer[offset++];
437 		static const char special[256] = {
438 			['\t'] = 1, ['\r'] = 1, ['\n'] = 1, ['\\'] = 1
439 		};
440 		if (!special[c]) {
441 			stream->offset = offset;
442 			stream->pos++;
443 			return c;
444 		}
445 	}
446 	return nextchar_slow(stream);
447 }
448 
449 struct token eof_token_entry;
450 
mark_eof(stream_t * stream)451 static struct token *mark_eof(stream_t *stream)
452 {
453 	struct token *end;
454 
455 	end = alloc_token(stream);
456 	eof_token_entry.pos = end->pos;
457 	token_type(end) = TOKEN_STREAMEND;
458 	end->pos.newline = 1;
459 
460 	eof_token_entry.next = &eof_token_entry;
461 	eof_token_entry.pos.newline = 1;
462 
463 	end->next =  &eof_token_entry;
464 	*stream->tokenlist = end;
465 	stream->tokenlist = NULL;
466 	return end;
467 }
468 
add_token(stream_t * stream)469 static void add_token(stream_t *stream)
470 {
471 	struct token *token = stream->token;
472 
473 	stream->token = NULL;
474 	token->next = NULL;
475 	*stream->tokenlist = token;
476 	stream->tokenlist = &token->next;
477 }
478 
drop_token(stream_t * stream)479 static void drop_token(stream_t *stream)
480 {
481 	stream->newline |= stream->token->pos.newline;
482 	stream->whitespace |= stream->token->pos.whitespace;
483 	stream->token = NULL;
484 }
485 
486 enum {
487 	Letter = 1,
488 	Digit = 2,
489 	Hex = 4,
490 	Exp = 8,
491 	Dot = 16,
492 	ValidSecond = 32,
493 	Quote = 64,
494 };
495 
496 static const char cclass[257] = {
497 	['0' + 1 ... '9' + 1] = Digit | Hex,
498 	['A' + 1 ... 'D' + 1] = Letter | Hex,
499 	['E' + 1] = Letter | Hex | Exp,	/* E<exp> */
500 	['F' + 1] = Letter | Hex,
501 	['G' + 1 ... 'O' + 1] = Letter,
502 	['P' + 1] = Letter | Exp,	/* P<exp> */
503 	['Q' + 1 ... 'Z' + 1] = Letter,
504 	['a' + 1 ... 'd' + 1] = Letter | Hex,
505 	['e' + 1] = Letter | Hex | Exp,	/* e<exp> */
506 	['f' + 1] = Letter | Hex,
507 	['g' + 1 ... 'o' + 1] = Letter,
508 	['p' + 1] = Letter | Exp,	/* p<exp> */
509 	['q' + 1 ... 'z' + 1] = Letter,
510 	['_' + 1] = Letter,
511 	['.' + 1] = Dot | ValidSecond,
512 	['=' + 1] = ValidSecond,
513 	['+' + 1] = ValidSecond,
514 	['-' + 1] = ValidSecond,
515 	['>' + 1] = ValidSecond,
516 	['<' + 1] = ValidSecond,
517 	['&' + 1] = ValidSecond,
518 	['|' + 1] = ValidSecond,
519 	['#' + 1] = ValidSecond,
520 	['\'' + 1] = Quote,
521 	['"' + 1] = Quote,
522 };
523 
524 /*
525  * pp-number:
526  *	digit
527  *	. digit
528  *	pp-number digit
529  *	pp-number identifier-nodigit
530  *	pp-number e sign
531  *	pp-number E sign
532  *	pp-number p sign
533  *	pp-number P sign
534  *	pp-number .
535  */
get_one_number(int c,int next,stream_t * stream)536 static int get_one_number(int c, int next, stream_t *stream)
537 {
538 	struct token *token;
539 	static char buffer[4095];
540 	char *p = buffer, *buffer_end = buffer + sizeof (buffer);
541 
542 	*p++ = c;
543 	for (;;) {
544 		long class =  cclass[next + 1];
545 		if (!(class & (Dot | Digit | Letter)))
546 			break;
547 		if (p != buffer_end)
548 			*p++ = next;
549 		next = nextchar(stream);
550 		if (class & Exp) {
551 			if (next == '-' || next == '+') {
552 				if (p != buffer_end)
553 					*p++ = next;
554 				next = nextchar(stream);
555 			}
556 		}
557 	}
558 
559 	if (p == buffer_end) {
560 		sparse_error(stream_pos(stream), "number token exceeds %td characters",
561 		      buffer_end - buffer);
562 		// Pretend we saw just "1".
563 		buffer[0] = '1';
564 		p = buffer + 1;
565 	}
566 
567 	*p++ = 0;
568 	token = stream->token;
569 	token_type(token) = TOKEN_NUMBER;
570 	token->number = xmemdup(buffer, p - buffer);
571 	add_token(stream);
572 
573 	return next;
574 }
575 
eat_string(int next,stream_t * stream,enum token_type type)576 static int eat_string(int next, stream_t *stream, enum token_type type)
577 {
578 	static char buffer[MAX_STRING];
579 	struct string *string;
580 	struct token *token = stream->token;
581 	int len = 0;
582 	int escape;
583 	int want_hex = 0;
584 	char delim = type < TOKEN_STRING ? '\'' : '"';
585 
586 	for (escape = 0; escape || next != delim; next = nextchar(stream)) {
587 		if (len < MAX_STRING)
588 			buffer[len] = next;
589 		len++;
590 		if (next == '\n') {
591 			warning(stream_pos(stream),
592 				"missing terminating %c character", delim);
593 			/* assume delimiter is lost */
594 			break;
595 		}
596 		if (next == EOF) {
597 			warning(stream_pos(stream),
598 				"End of file in middle of string");
599 			return next;
600 		}
601 		if (!escape) {
602 			if (want_hex && !(cclass[next + 1] & Hex))
603 				warning(stream_pos(stream),
604 					"\\x used with no following hex digits");
605 			want_hex = 0;
606 			escape = next == '\\';
607 		} else {
608 			escape = 0;
609 			want_hex = next == 'x';
610 		}
611 	}
612 	if (want_hex)
613 		warning(stream_pos(stream),
614 			"\\x used with no following hex digits");
615 	if (len > MAX_STRING) {
616 		warning(stream_pos(stream), "string too long (%d bytes, %d bytes max)", len, MAX_STRING);
617 		len = MAX_STRING;
618 	}
619 	if (delim == '\'' && len <= 4) {
620 		if (len == 0) {
621 			sparse_error(stream_pos(stream),
622 				"empty character constant");
623 			return nextchar(stream);
624 		}
625 		token_type(token) = type + len;
626 		memset(buffer + len, '\0', 4 - len);
627 		memcpy(token->embedded, buffer, 4);
628 	} else {
629 		token_type(token) = type;
630 		string = __alloc_string(len+1);
631 		memcpy(string->data, buffer, len);
632 		string->data[len] = '\0';
633 		string->length = len+1;
634 		token->string = string;
635 	}
636 
637 	/* Pass it on.. */
638 	token = stream->token;
639 	add_token(stream);
640 	return nextchar(stream);
641 }
642 
drop_stream_eoln(stream_t * stream)643 static int drop_stream_eoln(stream_t *stream)
644 {
645 	drop_token(stream);
646 	for (;;) {
647 		switch (nextchar(stream)) {
648 		case EOF:
649 			return EOF;
650 		case '\n':
651 			return nextchar(stream);
652 		}
653 	}
654 }
655 
drop_stream_comment(stream_t * stream)656 static int drop_stream_comment(stream_t *stream)
657 {
658 	int newline;
659 	int next;
660 	drop_token(stream);
661 	newline = stream->newline;
662 
663 	next = nextchar(stream);
664 	for (;;) {
665 		int curr = next;
666 		if (curr == EOF) {
667 			warning(stream_pos(stream), "End of file in the middle of a comment");
668 			return curr;
669 		}
670 		next = nextchar(stream);
671 		if (curr == '*' && next == '/')
672 			break;
673 	}
674 	stream->newline = newline;
675 	return nextchar(stream);
676 }
677 
678 unsigned char combinations[][4] = COMBINATION_STRINGS;
679 
680 #define NR_COMBINATIONS (SPECIAL_ARG_SEPARATOR - SPECIAL_BASE)
681 
682 /* hash function for two-character punctuators - all give unique values */
683 #define special_hash(c0, c1) (((c0*8+c1*2)+((c0*8+c1*2)>>5))&31)
684 
685 /*
686  * note that we won't get false positives - special_hash(0,0) is 0 and
687  * entry 0 is filled (by +=), so all the missing ones are OK.
688  */
689 static unsigned char hash_results[32][2] = {
690 #define RES(c0, c1) [special_hash(c0, c1)] = {c0, c1}
691 	RES('+', '='), /* 00 */
692 	RES('/', '='), /* 01 */
693 	RES('^', '='), /* 05 */
694 	RES('&', '&'), /* 07 */
695 	RES('#', '#'), /* 08 */
696 	RES('<', '<'), /* 0a */
697 	RES('<', '='), /* 0c */
698 	RES('!', '='), /* 0e */
699 	RES('%', '='), /* 0f */
700 	RES('-', '-'), /* 10 */
701 	RES('-', '='), /* 11 */
702 	RES('-', '>'), /* 13 */
703 	RES('=', '='), /* 15 */
704 	RES('&', '='), /* 17 */
705 	RES('*', '='), /* 18 */
706 	RES('.', '.'), /* 1a */
707 	RES('+', '+'), /* 1b */
708 	RES('|', '='), /* 1c */
709 	RES('>', '='), /* 1d */
710 	RES('|', '|'), /* 1e */
711 	RES('>', '>')  /* 1f */
712 #undef RES
713 };
714 static int code[32] = {
715 #define CODE(c0, c1, value) [special_hash(c0, c1)] = value
716 	CODE('+', '=', SPECIAL_ADD_ASSIGN), /* 00 */
717 	CODE('/', '=', SPECIAL_DIV_ASSIGN), /* 01 */
718 	CODE('^', '=', SPECIAL_XOR_ASSIGN), /* 05 */
719 	CODE('&', '&', SPECIAL_LOGICAL_AND), /* 07 */
720 	CODE('#', '#', SPECIAL_HASHHASH), /* 08 */
721 	CODE('<', '<', SPECIAL_LEFTSHIFT), /* 0a */
722 	CODE('<', '=', SPECIAL_LTE), /* 0c */
723 	CODE('!', '=', SPECIAL_NOTEQUAL), /* 0e */
724 	CODE('%', '=', SPECIAL_MOD_ASSIGN), /* 0f */
725 	CODE('-', '-', SPECIAL_DECREMENT), /* 10 */
726 	CODE('-', '=', SPECIAL_SUB_ASSIGN), /* 11 */
727 	CODE('-', '>', SPECIAL_DEREFERENCE), /* 13 */
728 	CODE('=', '=', SPECIAL_EQUAL), /* 15 */
729 	CODE('&', '=', SPECIAL_AND_ASSIGN), /* 17 */
730 	CODE('*', '=', SPECIAL_MUL_ASSIGN), /* 18 */
731 	CODE('.', '.', SPECIAL_DOTDOT), /* 1a */
732 	CODE('+', '+', SPECIAL_INCREMENT), /* 1b */
733 	CODE('|', '=', SPECIAL_OR_ASSIGN), /* 1c */
734 	CODE('>', '=', SPECIAL_GTE), /* 1d */
735 	CODE('|', '|', SPECIAL_LOGICAL_OR), /* 1e */
736 	CODE('>', '>', SPECIAL_RIGHTSHIFT)  /* 1f */
737 #undef CODE
738 };
739 
get_one_special(int c,stream_t * stream)740 static int get_one_special(int c, stream_t *stream)
741 {
742 	struct token *token;
743 	int next, value, i;
744 
745 	next = nextchar(stream);
746 
747 	/*
748 	 * Check for numbers, strings, character constants, and comments
749 	 */
750 	switch (c) {
751 	case '.':
752 		if (next >= '0' && next <= '9')
753 			return get_one_number(c, next, stream);
754 		break;
755 	case '"':
756 		return eat_string(next, stream, TOKEN_STRING);
757 	case '\'':
758 		return eat_string(next, stream, TOKEN_CHAR);
759 	case '/':
760 		if (next == '/')
761 			return drop_stream_eoln(stream);
762 		if (next == '*')
763 			return drop_stream_comment(stream);
764 	}
765 
766 	/*
767 	 * Check for combinations
768 	 */
769 	value = c;
770 	if (cclass[next + 1] & ValidSecond) {
771 		i = special_hash(c, next);
772 		if (hash_results[i][0] == c && hash_results[i][1] == next) {
773 			value = code[i];
774 			next = nextchar(stream);
775 			if (value >= SPECIAL_LEFTSHIFT &&
776 			    next == "==."[value - SPECIAL_LEFTSHIFT]) {
777 				value += 3;
778 				next = nextchar(stream);
779 			}
780 		}
781 	}
782 
783 	/* Pass it on.. */
784 	token = stream->token;
785 	token_type(token) = TOKEN_SPECIAL;
786 	token->special = value;
787 	add_token(stream);
788 	return next;
789 }
790 
791 #define IDENT_HASH_BITS (13)
792 #define IDENT_HASH_SIZE (1<<IDENT_HASH_BITS)
793 #define IDENT_HASH_MASK (IDENT_HASH_SIZE-1)
794 
795 #define ident_hash_init(c)		(c)
796 #define ident_hash_add(oldhash,c)	((oldhash)*11 + (c))
797 #define ident_hash_end(hash)		((((hash) >> IDENT_HASH_BITS) + (hash)) & IDENT_HASH_MASK)
798 
799 static struct ident *hash_table[IDENT_HASH_SIZE];
800 static int ident_hit, ident_miss, idents;
801 
show_identifier_stats(void)802 void show_identifier_stats(void)
803 {
804 	int i;
805 	int distribution[100];
806 
807 	fprintf(stderr, "identifiers: %d hits, %d misses\n",
808 		ident_hit, ident_miss);
809 
810 	for (i = 0; i < 100; i++)
811 		distribution[i] = 0;
812 
813 	for (i = 0; i < IDENT_HASH_SIZE; i++) {
814 		struct ident * ident = hash_table[i];
815 		int count = 0;
816 
817 		while (ident) {
818 			count++;
819 			ident = ident->next;
820 		}
821 		if (count > 99)
822 			count = 99;
823 		distribution[count]++;
824 	}
825 
826 	for (i = 0; i < 100; i++) {
827 		if (distribution[i])
828 			fprintf(stderr, "%2d: %d buckets\n", i, distribution[i]);
829 	}
830 }
831 
alloc_ident(const char * name,int len)832 struct ident *alloc_ident(const char *name, int len)
833 {
834 	struct ident *ident = __alloc_ident(len);
835 	ident->symbols = NULL;
836 	ident->len = len;
837 	ident->tainted = 0;
838 	memcpy(ident->name, name, len);
839 	return ident;
840 }
841 
insert_hash(struct ident * ident,unsigned long hash)842 static struct ident * insert_hash(struct ident *ident, unsigned long hash)
843 {
844 	ident->next = hash_table[hash];
845 	hash_table[hash] = ident;
846 	ident_miss++;
847 	return ident;
848 }
849 
create_hashed_ident(const char * name,int len,unsigned long hash)850 static struct ident *create_hashed_ident(const char *name, int len, unsigned long hash)
851 {
852 	struct ident *ident;
853 	struct ident **p;
854 
855 	p = &hash_table[hash];
856 	while ((ident = *p) != NULL) {
857 		if (ident->len == (unsigned char) len) {
858 			if (strncmp(name, ident->name, len) != 0)
859 				goto next;
860 
861 			ident_hit++;
862 			return ident;
863 		}
864 next:
865 		//misses++;
866 		p = &ident->next;
867 	}
868 	ident = alloc_ident(name, len);
869 	*p = ident;
870 	ident->next = NULL;
871 	ident_miss++;
872 	idents++;
873 	return ident;
874 }
875 
hash_name(const char * name,int len)876 static unsigned long hash_name(const char *name, int len)
877 {
878 	unsigned long hash;
879 	const unsigned char *p = (const unsigned char *)name;
880 
881 	hash = ident_hash_init(*p++);
882 	while (--len) {
883 		unsigned int i = *p++;
884 		hash = ident_hash_add(hash, i);
885 	}
886 	return ident_hash_end(hash);
887 }
888 
hash_ident(struct ident * ident)889 struct ident *hash_ident(struct ident *ident)
890 {
891 	return insert_hash(ident, hash_name(ident->name, ident->len));
892 }
893 
built_in_ident(const char * name)894 struct ident *built_in_ident(const char *name)
895 {
896 	int len = strlen(name);
897 	return create_hashed_ident(name, len, hash_name(name, len));
898 }
899 
built_in_token(int stream,struct ident * ident)900 struct token *built_in_token(int stream, struct ident *ident)
901 {
902 	struct token *token;
903 
904 	token = __alloc_token(0);
905 	token->pos.stream = stream;
906 	token_type(token) = TOKEN_IDENT;
907 	token->ident = ident;
908 	return token;
909 }
910 
get_one_identifier(int c,stream_t * stream)911 static int get_one_identifier(int c, stream_t *stream)
912 {
913 	struct token *token;
914 	struct ident *ident;
915 	unsigned long hash;
916 	char buf[256];
917 	int len = 1;
918 	int next;
919 
920 	hash = ident_hash_init(c);
921 	buf[0] = c;
922 	for (;;) {
923 		next = nextchar(stream);
924 		if (!(cclass[next + 1] & (Letter | Digit)))
925 			break;
926 		if (len >= sizeof(buf))
927 			break;
928 		hash = ident_hash_add(hash, next);
929 		buf[len] = next;
930 		len++;
931 	};
932 	if (cclass[next + 1] & Quote) {
933 		if (len == 1 && buf[0] == 'L') {
934 			if (next == '\'')
935 				return eat_string(nextchar(stream), stream,
936 							TOKEN_WIDE_CHAR);
937 			else
938 				return eat_string(nextchar(stream), stream,
939 							TOKEN_WIDE_STRING);
940 		}
941 	}
942 	hash = ident_hash_end(hash);
943 	ident = create_hashed_ident(buf, len, hash);
944 
945 	/* Pass it on.. */
946 	token = stream->token;
947 	token_type(token) = TOKEN_IDENT;
948 	token->ident = ident;
949 	add_token(stream);
950 	return next;
951 }
952 
get_one_token(int c,stream_t * stream)953 static int get_one_token(int c, stream_t *stream)
954 {
955 	long class = cclass[c + 1];
956 	if (class & Digit)
957 		return get_one_number(c, nextchar(stream), stream);
958 	if (class & Letter)
959 		return get_one_identifier(c, stream);
960 	return get_one_special(c, stream);
961 }
962 
setup_stream(stream_t * stream,int idx,int fd,unsigned char * buf,unsigned int buf_size)963 static struct token *setup_stream(stream_t *stream, int idx, int fd,
964 	unsigned char *buf, unsigned int buf_size)
965 {
966 	struct token *begin;
967 
968 	stream->nr = idx;
969 	stream->line = 1;
970 	stream->newline = 1;
971 	stream->whitespace = 0;
972 	stream->pos = 0;
973 
974 	stream->token = NULL;
975 	stream->fd = fd;
976 	stream->offset = 0;
977 	stream->size = buf_size;
978 	stream->buffer = buf;
979 
980 	begin = alloc_token(stream);
981 	token_type(begin) = TOKEN_STREAMBEGIN;
982 	stream->tokenlist = &begin->next;
983 	return begin;
984 }
985 
tokenize_stream(stream_t * stream)986 static struct token *tokenize_stream(stream_t *stream)
987 {
988 	int c = nextchar(stream);
989 	while (c != EOF) {
990 		if (!isspace(c)) {
991 			struct token *token = alloc_token(stream);
992 			stream->token = token;
993 			stream->newline = 0;
994 			stream->whitespace = 0;
995 			c = get_one_token(c, stream);
996 			continue;
997 		}
998 		stream->whitespace = 1;
999 		c = nextchar(stream);
1000 	}
1001 	return mark_eof(stream);
1002 }
1003 
tokenize_buffer(void * buffer,unsigned long size,struct token ** endtoken)1004 struct token * tokenize_buffer(void *buffer, unsigned long size, struct token **endtoken)
1005 {
1006 	stream_t stream;
1007 	struct token *begin;
1008 
1009 	begin = setup_stream(&stream, 0, -1, buffer, size);
1010 	*endtoken = tokenize_stream(&stream);
1011 	return begin;
1012 }
1013 
tokenize(const char * name,int fd,struct token * endtoken,const char ** next_path)1014 struct token * tokenize(const char *name, int fd, struct token *endtoken, const char **next_path)
1015 {
1016 	struct token *begin, *end;
1017 	stream_t stream;
1018 	unsigned char buffer[BUFSIZE];
1019 	int idx;
1020 
1021 	idx = init_stream(name, fd, next_path);
1022 	if (idx < 0) {
1023 		// info(endtoken->pos, "File %s is const", name);
1024 		return endtoken;
1025 	}
1026 
1027 	begin = setup_stream(&stream, idx, fd, buffer, 0);
1028 	end = tokenize_stream(&stream);
1029 	if (endtoken)
1030 		end->next = endtoken;
1031 	return begin;
1032 }
1033