lexi.c revision 1.57 1 /* $NetBSD: lexi.c,v 1.57 2021/09/25 20:05:55 rillig Exp $ */
2
3 /*-
4 * SPDX-License-Identifier: BSD-4-Clause
5 *
6 * Copyright (c) 1985 Sun Microsystems, Inc.
7 * Copyright (c) 1980, 1993
8 * The Regents of the University of California. All rights reserved.
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. All advertising materials mentioning features or use of this software
20 * must display the following acknowledgement:
21 * This product includes software developed by the University of
22 * California, Berkeley and its contributors.
23 * 4. Neither the name of the University nor the names of its contributors
24 * may be used to endorse or promote products derived from this software
25 * without specific prior written permission.
26 *
27 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * SUCH DAMAGE.
38 */
39
40 #if 0
41 static char sccsid[] = "@(#)lexi.c 8.1 (Berkeley) 6/6/93";
42 #endif
43
44 #include <sys/cdefs.h>
45 #if defined(__NetBSD__)
46 __RCSID("$NetBSD: lexi.c,v 1.57 2021/09/25 20:05:55 rillig Exp $");
47 #elif defined(__FreeBSD__)
48 __FBSDID("$FreeBSD: head/usr.bin/indent/lexi.c 337862 2018-08-15 18:19:45Z pstef $");
49 #endif
50
51 #include <assert.h>
52 #include <err.h>
53 #include <stdio.h>
54 #include <ctype.h>
55 #include <stdint.h>
56 #include <stdlib.h>
57 #include <string.h>
58 #include <sys/param.h>
59
60 #include "indent.h"
61
62 struct templ {
63 const char *rwd;
64 enum rwcode rwcode;
65 };
66
67 /*
68 * This table has to be sorted alphabetically, because it'll be used in binary
69 * search.
70 */
71 const struct templ specials[] =
72 {
73 {"_Bool", rw_type},
74 {"_Complex", rw_type},
75 {"_Imaginary", rw_type},
76 {"auto", rw_storage_class},
77 {"bool", rw_type},
78 {"break", rw_jump},
79 {"case", rw_case_or_default},
80 {"char", rw_type},
81 {"complex", rw_type},
82 {"const", rw_type},
83 {"continue", rw_jump},
84 {"default", rw_case_or_default},
85 {"do", rw_do_or_else},
86 {"double", rw_type},
87 {"else", rw_do_or_else},
88 {"enum", rw_struct_or_union_or_enum},
89 {"extern", rw_storage_class},
90 {"float", rw_type},
91 {"for", rw_for_or_if_or_while},
92 {"global", rw_type},
93 {"goto", rw_jump},
94 {"if", rw_for_or_if_or_while},
95 {"imaginary", rw_type},
96 {"inline", rw_inline_or_restrict},
97 {"int", rw_type},
98 {"long", rw_type},
99 {"offsetof", rw_offsetof},
100 {"register", rw_storage_class},
101 {"restrict", rw_inline_or_restrict},
102 {"return", rw_jump},
103 {"short", rw_type},
104 {"signed", rw_type},
105 {"sizeof", rw_sizeof},
106 {"static", rw_storage_class},
107 {"struct", rw_struct_or_union_or_enum},
108 {"switch", rw_switch},
109 {"typedef", rw_typedef},
110 {"union", rw_struct_or_union_or_enum},
111 {"unsigned", rw_type},
112 {"void", rw_type},
113 {"volatile", rw_type},
114 {"while", rw_for_or_if_or_while}
115 };
116
117 const char **typenames;
118 int typename_count;
119 int typename_top = -1;
120
121 /*
122 * The transition table below was rewritten by hand from lx's output, given
123 * the following definitions. lx is Katherine Flavel's lexer generator.
124 *
125 * O = /[0-7]/; D = /[0-9]/; NZ = /[1-9]/;
126 * H = /[a-f0-9]/i; B = /[0-1]/; HP = /0x/i;
127 * BP = /0b/i; E = /e[+\-]?/i D+; P = /p[+\-]?/i D+;
128 * FS = /[fl]/i; IS = /u/i /(l|L|ll|LL)/? | /(l|L|ll|LL)/ /u/i?;
129 *
130 * D+ E FS? -> $float;
131 * D* "." D+ E? FS? -> $float;
132 * D+ "." E? FS? -> $float; HP H+ IS? -> $int;
133 * HP H+ P FS? -> $float; NZ D* IS? -> $int;
134 * HP H* "." H+ P FS? -> $float; "0" O* IS? -> $int;
135 * HP H+ "." P FS -> $float; BP B+ IS? -> $int;
136 */
137 static const char num_lex_state[][26] = {
138 /* examples:
139 00
140 s 0xx
141 t 00xaa
142 a 11 101100xxa..
143 r 11ee0001101lbuuxx.a.pp
144 t.01.e+008bLuxll0Ll.aa.p+0
145 states: ABCDEFGHIJKLMNOPQRSTUVWXYZ */
146 [0] = "uuiifuufiuuiiuiiiiiuiuuuuu",
147 [1] = "CEIDEHHHIJQ U Q VUVVZZZ",
148 [2] = "DEIDEHHHIJQ U Q VUVVZZZ",
149 [3] = "DEIDEHHHIJ U VUVVZZZ",
150 [4] = "DEJDEHHHJJ U VUVVZZZ",
151 [5] = " U VUVV ",
152 [6] = " K U VUVV ",
153 [7] = " FFF FF U VUVV ",
154 [8] = " f f U VUVV f",
155 [9] = " LLf fL PR Li L f",
156 [10] = " OOf fO S P O i O f",
157 [11] = " FFX ",
158 [12] = " MM M i iiM M ",
159 [13] = " N ",
160 [14] = " G Y ",
161 [15] = "B EE EE T W ",
162 /* ABCDEFGHIJKLMNOPQRSTUVWXYZ */
163 };
164
165 static const uint8_t num_lex_row[] = {
166 ['0'] = 1,
167 ['1'] = 2,
168 ['2'] = 3, ['3'] = 3, ['4'] = 3, ['5'] = 3, ['6'] = 3, ['7'] = 3,
169 ['8'] = 4, ['9'] = 4,
170 ['A'] = 5, ['a'] = 5, ['C'] = 5, ['c'] = 5, ['D'] = 5, ['d'] = 5,
171 ['B'] = 6, ['b'] = 6,
172 ['E'] = 7, ['e'] = 7,
173 ['F'] = 8, ['f'] = 8,
174 ['L'] = 9,
175 ['l'] = 10,
176 ['P'] = 11, ['p'] = 11,
177 ['U'] = 12, ['u'] = 12,
178 ['X'] = 13, ['x'] = 13,
179 ['+'] = 14, ['-'] = 14,
180 ['.'] = 15,
181 };
182
183 static char
184 inbuf_peek(void)
185 {
186 return *buf_ptr;
187 }
188
189 static void
190 inbuf_skip(void)
191 {
192 buf_ptr++;
193 if (buf_ptr >= buf_end)
194 fill_buffer();
195 }
196
197 static char
198 inbuf_next(void)
199 {
200 char ch = inbuf_peek();
201 inbuf_skip();
202 return ch;
203 }
204
205 static void
206 check_size_token(size_t desired_size)
207 {
208 if (token.e + (desired_size) < token.l)
209 return;
210
211 size_t nsize = token.l - token.s + 400 + desired_size;
212 size_t token_len = token.e - token.s;
213 token.buf = xrealloc(token.buf, nsize);
214 token.e = token.buf + token_len + 1;
215 token.l = token.buf + nsize - 5;
216 token.s = token.buf + 1;
217 }
218
219 static int
220 compare_templ_array(const void *key, const void *elem)
221 {
222 return strcmp(key, ((const struct templ *)elem)->rwd);
223 }
224
225 static int
226 compare_string_array(const void *key, const void *elem)
227 {
228 return strcmp(key, *((const char *const *)elem));
229 }
230
231 #ifdef debug
232 const char *
233 token_type_name(token_type ttype)
234 {
235 static const char *const name[] = {
236 "end_of_file", "newline", "lparen", "rparen", "unary_op",
237 "binary_op", "postfix_op", "question", "case_label", "colon",
238 "semicolon", "lbrace", "rbrace", "ident", "comma",
239 "comment", "switch_expr", "preprocessing", "form_feed", "decl",
240 "keyword_for_if_while", "keyword_do_else",
241 "if_expr", "while_expr", "for_exprs",
242 "stmt", "stmt_list", "keyword_else", "keyword_do", "do_stmt",
243 "if_expr_stmt", "if_expr_stmt_else", "period", "string_prefix",
244 "storage_class", "funcname", "type_def", "keyword_struct_union_enum"
245 };
246
247 assert(0 <= ttype && ttype < sizeof name / sizeof name[0]);
248
249 return name[ttype];
250 }
251
252 static void
253 print_buf(const char *name, const char *s, const char *e)
254 {
255 if (s < e) {
256 debug_printf(" %s ", name);
257 debug_vis_range("\"", s, e, "\"");
258 }
259 }
260
261 static token_type
262 lexi_end(token_type ttype)
263 {
264 debug_printf("in line %d, lexi returns '%s'",
265 line_no, token_type_name(ttype));
266 print_buf("token", token.s, token.e);
267 print_buf("label", lab.s, lab.e);
268 print_buf("code", code.s, code.e);
269 print_buf("comment", com.s, com.e);
270 debug_printf("\n");
271
272 return ttype;
273 }
274 #else
275 # define lexi_end(tk) (tk)
276 #endif
277
278 static void
279 lex_number(void)
280 {
281 for (uint8_t s = 'A'; s != 'f' && s != 'i' && s != 'u'; ) {
282 uint8_t ch = (uint8_t)*buf_ptr;
283 if (ch >= nitems(num_lex_row) || num_lex_row[ch] == 0)
284 break;
285 uint8_t row = num_lex_row[ch];
286 if (num_lex_state[row][s - 'A'] == ' ') {
287 /*
288 * num_lex_state[0][s - 'A'] now indicates the type:
289 * f = floating, ch = integer, u = unknown
290 */
291 break;
292 }
293 s = num_lex_state[row][s - 'A'];
294 check_size_token(1);
295 *token.e++ = inbuf_next();
296 }
297 }
298
299 static void
300 lex_word(void)
301 {
302 while (isalnum((unsigned char)*buf_ptr) ||
303 *buf_ptr == '\\' ||
304 *buf_ptr == '_' || *buf_ptr == '$') {
305 /* fill_buffer() terminates buffer with newline */
306 if (*buf_ptr == '\\') {
307 if (buf_ptr[1] == '\n') {
308 buf_ptr += 2;
309 if (buf_ptr >= buf_end)
310 fill_buffer();
311 } else
312 break;
313 }
314 check_size_token(1);
315 *token.e++ = inbuf_next();
316 }
317 }
318
319 static void
320 lex_char_or_string(void)
321 {
322 for (char delim = *token.s;;) {
323 if (*buf_ptr == '\n') {
324 diag(1, "Unterminated literal");
325 return;
326 }
327 check_size_token(2);
328 *token.e++ = inbuf_next();
329 if (token.e[-1] == delim)
330 return;
331 if (token.e[-1] == '\\') {
332 if (*buf_ptr == '\n')
333 ++line_no;
334 *token.e++ = inbuf_next();
335 }
336 }
337 }
338
339 /*
340 * This hack attempts to guess whether the current token is in fact a
341 * declaration keyword -- one that has been defined by typedef.
342 */
343 static bool
344 probably_typedef(const struct parser_state *state)
345 {
346 return state->p_l_follow == 0 && !state->block_init && !state->in_stmt &&
347 ((*buf_ptr == '*' && buf_ptr[1] != '=') ||
348 isalpha((unsigned char)*buf_ptr)) &&
349 (state->last_token == semicolon || state->last_token == lbrace ||
350 state->last_token == rbrace);
351 }
352
353 /* Reads the next token, placing it in the global variable "token". */
354 token_type
355 lexi(struct parser_state *state)
356 {
357 bool unary_delim; /* whether the current token
358 * forces a following operator to be unary */
359 token_type ttype;
360
361 token.e = token.s; /* point to start of place to save token */
362 unary_delim = false;
363 state->col_1 = state->last_nl; /* tell world that this token started
364 * in column 1 iff the last thing
365 * scanned was a newline */
366 state->last_nl = false;
367
368 while (*buf_ptr == ' ' || *buf_ptr == '\t') { /* get rid of blanks */
369 state->col_1 = false; /* leading blanks imply token is not in column
370 * 1 */
371 inbuf_skip();
372 }
373
374 /* Scan an alphanumeric token */
375 if (isalnum((unsigned char)*buf_ptr) ||
376 *buf_ptr == '_' || *buf_ptr == '$' ||
377 (buf_ptr[0] == '.' && isdigit((unsigned char)buf_ptr[1]))) {
378 /*
379 * we have a letter or number
380 */
381 struct templ *p;
382
383 if (isdigit((unsigned char)*buf_ptr) ||
384 (buf_ptr[0] == '.' && isdigit((unsigned char)buf_ptr[1]))) {
385 lex_number();
386 } else {
387 lex_word();
388 }
389 *token.e = '\0';
390
391 if (token.s[0] == 'L' && token.s[1] == '\0' &&
392 (*buf_ptr == '"' || *buf_ptr == '\''))
393 return lexi_end(string_prefix);
394
395 while (*buf_ptr == ' ' || *buf_ptr == '\t') /* get rid of blanks */
396 inbuf_next();
397 state->keyword = rw_0;
398 if (state->last_token == keyword_struct_union_enum &&
399 state->p_l_follow == 0) {
400 /* if last token was 'struct' and we're not in parentheses, then
401 * this token should be treated as a declaration */
402 state->last_u_d = true;
403 return lexi_end(decl);
404 }
405 /*
406 * Operator after identifier is binary unless last token was 'struct'
407 */
408 state->last_u_d = (state->last_token == keyword_struct_union_enum);
409
410 p = bsearch(token.s, specials, sizeof specials / sizeof specials[0],
411 sizeof specials[0], compare_templ_array);
412 if (p == NULL) { /* not a special keyword... */
413 char *u;
414
415 /* ... so maybe a type_t or a typedef */
416 if ((opt.auto_typedefs && ((u = strrchr(token.s, '_')) != NULL) &&
417 strcmp(u, "_t") == 0) || (typename_top >= 0 &&
418 bsearch(token.s, typenames, (size_t)typename_top + 1,
419 sizeof typenames[0], compare_string_array) != NULL)) {
420 state->keyword = rw_type;
421 state->last_u_d = true;
422 goto found_typename;
423 }
424 } else { /* we have a keyword */
425 state->keyword = p->rwcode;
426 state->last_u_d = true;
427 switch (p->rwcode) {
428 case rw_switch:
429 return lexi_end(switch_expr);
430 case rw_case_or_default:
431 return lexi_end(case_label);
432 case rw_struct_or_union_or_enum:
433 case rw_type:
434 found_typename:
435 if (state->p_l_follow != 0) {
436 /* inside parens: cast, param list, offsetof or sizeof */
437 state->cast_mask |= (1 << state->p_l_follow) & ~state->not_cast_mask;
438 }
439 if (state->last_token == period || state->last_token == unary_op) {
440 state->keyword = rw_0;
441 break;
442 }
443 if (p != NULL && p->rwcode == rw_struct_or_union_or_enum)
444 return lexi_end(keyword_struct_union_enum);
445 if (state->p_l_follow != 0)
446 break;
447 return lexi_end(decl);
448
449 case rw_for_or_if_or_while:
450 return lexi_end(keyword_for_if_while);
451
452 case rw_do_or_else:
453 return lexi_end(keyword_do_else);
454
455 case rw_storage_class:
456 return lexi_end(storage_class);
457
458 case rw_typedef:
459 return lexi_end(type_def);
460
461 default: /* all others are treated like any other
462 * identifier */
463 return lexi_end(ident);
464 } /* end of switch */
465 } /* end of if (found_it) */
466 if (*buf_ptr == '(' && state->tos <= 1 && state->ind_level == 0 &&
467 !state->in_parameter_declaration && !state->block_init) {
468 char *tp = buf_ptr;
469 while (tp < buf_end)
470 if (*tp++ == ')' && (*tp == ';' || *tp == ','))
471 goto not_proc;
472 strncpy(state->procname, token.s, sizeof state->procname - 1);
473 if (state->in_decl)
474 state->in_parameter_declaration = true;
475 return lexi_end(funcname);
476 not_proc:;
477 } else if (probably_typedef(state)) {
478 state->keyword = rw_type;
479 state->last_u_d = true;
480 return lexi_end(decl);
481 }
482 if (state->last_token == decl) /* if this is a declared variable,
483 * then following sign is unary */
484 state->last_u_d = true; /* will make "int a -1" work */
485 return lexi_end(ident); /* the ident is not in the list */
486 } /* end of procesing for alpanum character */
487
488 /* Scan a non-alphanumeric token */
489
490 check_size_token(3); /* things like "<<=" */
491 *token.e++ = inbuf_next(); /* if it is only a one-character token, it is
492 * moved here */
493 *token.e = '\0';
494
495 switch (*token.s) {
496 case '\n':
497 unary_delim = state->last_u_d;
498 state->last_nl = true; /* remember that we just had a newline */
499 /* if data has been exhausted, the newline is a dummy. */
500 ttype = had_eof ? end_of_file : newline;
501 break;
502
503 case '\'':
504 case '"':
505 lex_char_or_string();
506 ttype = ident;
507 break;
508
509 case '(':
510 case '[':
511 unary_delim = true;
512 ttype = lparen;
513 break;
514
515 case ')':
516 case ']':
517 ttype = rparen;
518 break;
519
520 case '#':
521 unary_delim = state->last_u_d;
522 ttype = preprocessing;
523 break;
524
525 case '?':
526 unary_delim = true;
527 ttype = question;
528 break;
529
530 case ':':
531 ttype = colon;
532 unary_delim = true;
533 break;
534
535 case ';':
536 unary_delim = true;
537 ttype = semicolon;
538 break;
539
540 case '{':
541 unary_delim = true;
542 ttype = lbrace;
543 break;
544
545 case '}':
546 unary_delim = true;
547 ttype = rbrace;
548 break;
549
550 case 014: /* a form feed */
551 unary_delim = state->last_u_d;
552 state->last_nl = true; /* remember this so we can set 'state->col_1'
553 * right */
554 ttype = form_feed;
555 break;
556
557 case ',':
558 unary_delim = true;
559 ttype = comma;
560 break;
561
562 case '.':
563 unary_delim = false;
564 ttype = period;
565 break;
566
567 case '-':
568 case '+': /* check for -, +, --, ++ */
569 ttype = state->last_u_d ? unary_op : binary_op;
570 unary_delim = true;
571
572 if (*buf_ptr == token.s[0]) {
573 /* check for doubled character */
574 *token.e++ = *buf_ptr++;
575 /* buffer overflow will be checked at end of loop */
576 if (state->last_token == ident || state->last_token == rparen) {
577 ttype = state->last_u_d ? unary_op : postfix_op;
578 /* check for following ++ or -- */
579 unary_delim = false;
580 }
581 } else if (*buf_ptr == '=')
582 /* check for operator += */
583 *token.e++ = *buf_ptr++;
584 else if (*buf_ptr == '>') {
585 /* check for operator -> */
586 *token.e++ = *buf_ptr++;
587 unary_delim = false;
588 ttype = unary_op;
589 state->want_blank = false;
590 }
591 break; /* buffer overflow will be checked at end of
592 * switch */
593
594 case '=':
595 if (state->in_or_st)
596 state->block_init = true;
597 if (*buf_ptr == '=') { /* == */
598 *token.e++ = '='; /* Flip =+ to += */
599 buf_ptr++;
600 *token.e = 0;
601 }
602 ttype = binary_op;
603 unary_delim = true;
604 break;
605 /* can drop thru!!! */
606
607 case '>':
608 case '<':
609 case '!': /* ops like <, <<, <=, !=, etc */
610 if (*buf_ptr == '>' || *buf_ptr == '<' || *buf_ptr == '=')
611 *token.e++ = inbuf_next();
612 if (*buf_ptr == '=')
613 *token.e++ = *buf_ptr++;
614 ttype = state->last_u_d ? unary_op : binary_op;
615 unary_delim = true;
616 break;
617
618 case '*':
619 unary_delim = true;
620 if (!state->last_u_d) {
621 if (*buf_ptr == '=')
622 *token.e++ = *buf_ptr++;
623 ttype = binary_op;
624 break;
625 }
626 while (*buf_ptr == '*' || isspace((unsigned char)*buf_ptr)) {
627 if (*buf_ptr == '*') {
628 check_size_token(1);
629 *token.e++ = *buf_ptr;
630 }
631 inbuf_skip();
632 }
633 if (ps.in_decl) {
634 char *tp = buf_ptr;
635
636 while (isalpha((unsigned char)*tp) ||
637 isspace((unsigned char)*tp)) {
638 if (++tp >= buf_end)
639 fill_buffer();
640 }
641 if (*tp == '(')
642 ps.procname[0] = ' ';
643 }
644 ttype = unary_op;
645 break;
646
647 default:
648 if (token.s[0] == '/' && (*buf_ptr == '*' || *buf_ptr == '/')) {
649 /* it is start of comment */
650 *token.e++ = inbuf_next();
651
652 ttype = comment;
653 unary_delim = state->last_u_d;
654 break;
655 }
656 while (token.e[-1] == *buf_ptr || *buf_ptr == '=') {
657 /*
658 * handle ||, &&, etc, and also things as in int *****i
659 */
660 check_size_token(1);
661 *token.e++ = inbuf_next();
662 }
663 ttype = state->last_u_d ? unary_op : binary_op;
664 unary_delim = true;
665 }
666
667 if (buf_ptr >= buf_end) /* check for input buffer empty */
668 fill_buffer();
669 state->last_u_d = unary_delim;
670 check_size_token(1);
671 *token.e = '\0';
672 return lexi_end(ttype);
673 }
674
675 void
676 alloc_typenames(void)
677 {
678
679 typenames = xmalloc(sizeof(typenames[0]) * (typename_count = 16));
680 }
681
682 void
683 add_typename(const char *key)
684 {
685 int comparison;
686
687 if (typename_top + 1 >= typename_count) {
688 typenames = xrealloc((void *)typenames,
689 sizeof(typenames[0]) * (typename_count *= 2));
690 }
691 if (typename_top == -1)
692 typenames[++typename_top] = xstrdup(key);
693 else if ((comparison = strcmp(key, typenames[typename_top])) >= 0) {
694 /* take advantage of sorted input */
695 if (comparison == 0) /* remove duplicates */
696 return;
697 typenames[++typename_top] = xstrdup(key);
698 } else {
699 int p;
700
701 for (p = 0; (comparison = strcmp(key, typenames[p])) > 0; p++)
702 /* find place for the new key */;
703 if (comparison == 0) /* remove duplicates */
704 return;
705 memmove(&typenames[p + 1], &typenames[p],
706 sizeof(typenames[0]) * (++typename_top - p));
707 typenames[p] = xstrdup(key);
708 }
709 }
710