lexi.c revision 1.104 1 /* $NetBSD: lexi.c,v 1.104 2021/10/26 20:17:42 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.104 2021/10/26 20:17:42 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 <sys/param.h>
52 #include <assert.h>
53 #include <stdio.h>
54 #include <ctype.h>
55 #include <stdlib.h>
56 #include <string.h>
57
58 #include "indent.h"
59
60 /* must be sorted alphabetically, is used in binary search */
61 static const struct keyword {
62 const char *name;
63 enum keyword_kind kind;
64 } keywords[] = {
65 {"_Bool", kw_type},
66 {"_Complex", kw_type},
67 {"_Imaginary", kw_type},
68 {"auto", kw_storage_class},
69 {"bool", kw_type},
70 {"break", kw_jump},
71 {"case", kw_case_or_default},
72 {"char", kw_type},
73 {"complex", kw_type},
74 {"const", kw_type},
75 {"continue", kw_jump},
76 {"default", kw_case_or_default},
77 {"do", kw_do},
78 {"double", kw_type},
79 {"else", kw_else},
80 {"enum", kw_struct_or_union_or_enum},
81 {"extern", kw_storage_class},
82 {"float", kw_type},
83 {"for", kw_for},
84 {"goto", kw_jump},
85 {"if", kw_if},
86 {"imaginary", kw_type},
87 {"inline", kw_inline_or_restrict},
88 {"int", kw_type},
89 {"long", kw_type},
90 {"offsetof", kw_offsetof},
91 {"register", kw_storage_class},
92 {"restrict", kw_inline_or_restrict},
93 {"return", kw_jump},
94 {"short", kw_type},
95 {"signed", kw_type},
96 {"sizeof", kw_sizeof},
97 {"static", kw_storage_class},
98 {"struct", kw_struct_or_union_or_enum},
99 {"switch", kw_switch},
100 {"typedef", kw_typedef},
101 {"union", kw_struct_or_union_or_enum},
102 {"unsigned", kw_type},
103 {"void", kw_type},
104 {"volatile", kw_type},
105 {"while", kw_while}
106 };
107
108 static struct {
109 const char **items;
110 unsigned int len;
111 unsigned int cap;
112 } typenames;
113
114 /*
115 * The transition table below was rewritten by hand from lx's output, given
116 * the following definitions. lx is Katherine Flavel's lexer generator.
117 *
118 * O = /[0-7]/; D = /[0-9]/; NZ = /[1-9]/;
119 * H = /[a-f0-9]/i; B = /[0-1]/; HP = /0x/i;
120 * BP = /0b/i; E = /e[+\-]?/i D+; P = /p[+\-]?/i D+;
121 * FS = /[fl]/i; IS = /u/i /(l|L|ll|LL)/? | /(l|L|ll|LL)/ /u/i?;
122 *
123 * D+ E FS? -> $float;
124 * D* "." D+ E? FS? -> $float;
125 * D+ "." E? FS? -> $float; HP H+ IS? -> $int;
126 * HP H+ P FS? -> $float; NZ D* IS? -> $int;
127 * HP H* "." H+ P FS? -> $float; "0" O* IS? -> $int;
128 * HP H+ "." P FS -> $float; BP B+ IS? -> $int;
129 */
130 /* INDENT OFF */
131 static const unsigned char lex_number_state[][26] = {
132 /* examples:
133 00
134 s 0xx
135 t 00xaa
136 a 11 101100xxa..
137 r 11ee0001101lbuuxx.a.pp
138 t.01.e+008bLuxll0Ll.aa.p+0
139 states: ABCDEFGHIJKLMNOPQRSTUVWXYZ */
140 [0] = "uuiifuufiuuiiuiiiiiuiuuuuu", /* (other) */
141 [1] = "CEIDEHHHIJQ U Q VUVVZZZ", /* 0 */
142 [2] = "DEIDEHHHIJQ U Q VUVVZZZ", /* 1 */
143 [3] = "DEIDEHHHIJ U VUVVZZZ", /* 2 3 4 5 6 7 */
144 [4] = "DEJDEHHHJJ U VUVVZZZ", /* 8 9 */
145 [5] = " U VUVV ", /* A a C c D d */
146 [6] = " K U VUVV ", /* B b */
147 [7] = " FFF FF U VUVV ", /* E e */
148 [8] = " f f U VUVV f", /* F f */
149 [9] = " LLf fL PR Li L f", /* L */
150 [10] = " OOf fO S P O i O f", /* l */
151 [11] = " FFX ", /* P p */
152 [12] = " MM M i iiM M ", /* U u */
153 [13] = " N ", /* X x */
154 [14] = " G Y ", /* + - */
155 [15] = "B EE EE T W ", /* . */
156 /* ABCDEFGHIJKLMNOPQRSTUVWXYZ */
157 };
158 /* INDENT ON */
159
160 static const uint8_t lex_number_row[] = {
161 ['0'] = 1,
162 ['1'] = 2,
163 ['2'] = 3, ['3'] = 3, ['4'] = 3, ['5'] = 3, ['6'] = 3, ['7'] = 3,
164 ['8'] = 4, ['9'] = 4,
165 ['A'] = 5, ['a'] = 5, ['C'] = 5, ['c'] = 5, ['D'] = 5, ['d'] = 5,
166 ['B'] = 6, ['b'] = 6,
167 ['E'] = 7, ['e'] = 7,
168 ['F'] = 8, ['f'] = 8,
169 ['L'] = 9,
170 ['l'] = 10,
171 ['P'] = 11, ['p'] = 11,
172 ['U'] = 12, ['u'] = 12,
173 ['X'] = 13, ['x'] = 13,
174 ['+'] = 14, ['-'] = 14,
175 ['.'] = 15,
176 };
177
178 static char
179 inbuf_peek(void)
180 {
181 return *inp.s;
182 }
183
184 void
185 inbuf_skip(void)
186 {
187 inp.s++;
188 if (inp.s >= inp.e)
189 inbuf_read_line();
190 }
191
192 char
193 inbuf_next(void)
194 {
195 char ch = inbuf_peek();
196 inbuf_skip();
197 return ch;
198 }
199
200 static void
201 check_size_token(size_t desired_size)
202 {
203 if (token.e + desired_size >= token.l)
204 buf_expand(&token, desired_size);
205 }
206
207 static void
208 token_add_char(char ch)
209 {
210 check_size_token(1);
211 *token.e++ = ch;
212 }
213
214 static int
215 cmp_keyword_by_name(const void *key, const void *elem)
216 {
217 return strcmp(key, ((const struct keyword *)elem)->name);
218 }
219
220 #ifdef debug
221 static const char *
222 lsym_name(lexer_symbol sym)
223 {
224 static const char *const name[] = {
225 "eof",
226 "preprocessing",
227 "newline",
228 "form_feed",
229 "comment",
230 "lparen_or_lbracket",
231 "rparen_or_rbracket",
232 "lbrace",
233 "rbrace",
234 "period",
235 "unary_op",
236 "binary_op",
237 "postfix_op",
238 "question",
239 "colon",
240 "comma",
241 "semicolon",
242 "typedef",
243 "storage_class",
244 "type",
245 "tag",
246 "case_label",
247 "string_prefix",
248 "ident",
249 "funcname",
250 "do",
251 "else",
252 "for",
253 "if",
254 "switch",
255 "while",
256 };
257
258 assert(array_length(name) == (int)lsym_while + 1);
259
260 return name[sym];
261 }
262
263 static const char *
264 kw_name(enum keyword_kind kw)
265 {
266 static const char *name[] = {
267 "0",
268 "offsetof",
269 "sizeof",
270 "struct_or_union_or_enum",
271 "type",
272 "for",
273 "if",
274 "while",
275 "do",
276 "else",
277 "switch",
278 "case_or_default",
279 "jump",
280 "storage_class",
281 "typedef",
282 "inline_or_restrict",
283 };
284
285 return name[kw];
286 }
287
288 static void
289 debug_print_buf(const char *name, const struct buffer *buf)
290 {
291 if (buf->s < buf->e) {
292 debug_printf("%s ", name);
293 debug_vis_range("\"", buf->s, buf->e, "\"\n");
294 }
295 }
296
297 static void
298 debug_lexi(const struct parser_state *state, lexer_symbol lsym)
299 {
300 debug_println("");
301 debug_printf("line %d\n", line_no);
302 if (state != &ps)
303 debug_println("transient state");
304 debug_print_buf("label", &lab);
305 debug_print_buf("code", &code);
306 debug_print_buf("comment", &com);
307 debug_printf("lexi returns '%s'", lsym_name(lsym));
308 if (state->keyword != kw_0)
309 debug_printf(" keyword '%s'", kw_name(state->keyword));
310 debug_println("");
311 debug_print_buf("token", &token);
312 }
313 #endif
314
315 /* ARGSUSED */
316 static lexer_symbol
317 lexi_end(const struct parser_state *state, lexer_symbol lsym)
318 {
319 #ifdef debug
320 debug_lexi(state, lsym);
321 #endif
322 return lsym;
323 }
324
325 static void
326 lex_number(void)
327 {
328 for (uint8_t s = 'A'; s != 'f' && s != 'i' && s != 'u';) {
329 uint8_t ch = (uint8_t)*inp.s;
330 if (ch >= array_length(lex_number_row) || lex_number_row[ch] == 0)
331 break;
332
333 uint8_t row = lex_number_row[ch];
334 if (lex_number_state[row][s - 'A'] == ' ') {
335 /*-
336 * lex_number_state[0][s - 'A'] now indicates the type:
337 * f = floating, i = integer, u = unknown
338 */
339 break;
340 }
341
342 s = lex_number_state[row][s - 'A'];
343 token_add_char(inbuf_next());
344 }
345 }
346
347 static void
348 lex_word(void)
349 {
350 while (isalnum((unsigned char)*inp.s) ||
351 *inp.s == '\\' ||
352 *inp.s == '_' || *inp.s == '$') {
353
354 if (*inp.s == '\\') {
355 if (inp.s[1] == '\n') {
356 inp.s += 2;
357 if (inp.s >= inp.e)
358 inbuf_read_line();
359 } else
360 break;
361 }
362
363 token_add_char(inbuf_next());
364 }
365 }
366
367 static void
368 lex_char_or_string(void)
369 {
370 for (char delim = *token.s;;) {
371 if (*inp.s == '\n') {
372 diag(1, "Unterminated literal");
373 return;
374 }
375
376 token_add_char(inbuf_next());
377 if (token.e[-1] == delim)
378 return;
379
380 if (token.e[-1] == '\\') {
381 if (*inp.s == '\n')
382 ++line_no;
383 token_add_char(inbuf_next());
384 }
385 }
386 }
387
388 /* Guess whether the current token is a declared type. */
389 static bool
390 probably_typename(const struct parser_state *state)
391 {
392 if (state->p_l_follow != 0)
393 return false;
394 if (state->block_init || state->in_stmt)
395 return false;
396 if (inp.s[0] == '*' && inp.s[1] != '=')
397 goto maybe;
398 if (isalpha((unsigned char)*inp.s))
399 goto maybe;
400 return false;
401 maybe:
402 return state->last_token == lsym_semicolon ||
403 state->last_token == lsym_lbrace ||
404 state->last_token == lsym_rbrace;
405 }
406
407 static int
408 bsearch_typenames(const char *key)
409 {
410 const char **arr = typenames.items;
411 int lo = 0;
412 int hi = (int)typenames.len - 1;
413
414 while (lo <= hi) {
415 int mid = (int)((unsigned)(lo + hi) >> 1);
416 int cmp = strcmp(arr[mid], key);
417 if (cmp < 0)
418 lo = mid + 1;
419 else if (cmp > 0)
420 hi = mid - 1;
421 else
422 return mid;
423 }
424 return -(lo + 1);
425 }
426
427 static bool
428 is_typename(void)
429 {
430 if (opt.auto_typedefs &&
431 token.e - token.s >= 2 && memcmp(token.e - 2, "_t", 2) == 0)
432 return true;
433
434 return bsearch_typenames(token.s) >= 0;
435 }
436
437 /* Read an alphanumeric token into 'token', or return end_of_file. */
438 static lexer_symbol
439 lexi_alnum(struct parser_state *state)
440 {
441 if (isdigit((unsigned char)*inp.s) ||
442 (inp.s[0] == '.' && isdigit((unsigned char)inp.s[1]))) {
443 lex_number();
444 } else if (isalnum((unsigned char)*inp.s) ||
445 *inp.s == '_' || *inp.s == '$') {
446 lex_word();
447 } else
448 return lsym_eof; /* just as a placeholder */
449
450 *token.e = '\0';
451
452 if (token.s[0] == 'L' && token.s[1] == '\0' &&
453 (*inp.s == '"' || *inp.s == '\''))
454 return lsym_string_prefix;
455
456 while (is_hspace(inbuf_peek()))
457 inbuf_skip();
458 state->keyword = kw_0;
459
460 if (state->last_token == lsym_tag && state->p_l_follow == 0) {
461 state->next_unary = true;
462 return lsym_type;
463 }
464
465 /* Operator after identifier is binary unless last token was 'struct'. */
466 state->next_unary = state->last_token == lsym_tag;
467
468 const struct keyword *kw = bsearch(token.s, keywords,
469 array_length(keywords), sizeof(keywords[0]), cmp_keyword_by_name);
470 if (kw == NULL) {
471 if (is_typename()) {
472 state->keyword = kw_type;
473 state->next_unary = true;
474 goto found_typename;
475 }
476
477 } else { /* we have a keyword */
478 state->keyword = kw->kind;
479 state->next_unary = true;
480
481 switch (kw->kind) {
482 case kw_switch:
483 return lsym_switch;
484
485 case kw_case_or_default:
486 return lsym_case_label;
487
488 case kw_struct_or_union_or_enum:
489 case kw_type:
490 found_typename:
491 if (state->p_l_follow != 0) {
492 /* inside parens: cast, param list, offsetof or sizeof */
493 state->cast_mask |= (1 << state->p_l_follow) & ~state->not_cast_mask;
494 }
495 if (state->last_token == lsym_period ||
496 state->last_token == lsym_unary_op) {
497 state->keyword = kw_0;
498 break;
499 }
500 if (kw != NULL && kw->kind == kw_struct_or_union_or_enum)
501 return lsym_tag;
502 if (state->p_l_follow != 0)
503 break;
504 return lsym_type;
505
506 case kw_for:
507 return lsym_for;
508
509 case kw_if:
510 return lsym_if;
511
512 case kw_while:
513 return lsym_while;
514
515 case kw_do:
516 return lsym_do;
517
518 case kw_else:
519 return lsym_else;
520
521 case kw_storage_class:
522 return lsym_storage_class;
523
524 case kw_typedef:
525 return lsym_typedef;
526
527 default: /* all others are treated like any other
528 * identifier */
529 return lsym_ident;
530 }
531 }
532
533 if (*inp.s == '(' && state->tos <= 1 && state->ind_level == 0 &&
534 !state->in_parameter_declaration && !state->block_init) {
535
536 for (const char *p = inp.s; p < inp.e;)
537 if (*p++ == ')' && (*p == ';' || *p == ','))
538 goto not_proc;
539
540 strncpy(state->procname, token.s, sizeof state->procname - 1);
541 if (state->in_decl)
542 state->in_parameter_declaration = true;
543 return lsym_funcname;
544 not_proc:;
545
546 } else if (probably_typename(state)) {
547 state->keyword = kw_type;
548 state->next_unary = true;
549 return lsym_type;
550 }
551
552 if (state->last_token == lsym_type) /* if this is a declared variable,
553 * then following sign is unary */
554 state->next_unary = true; /* will make "int a -1" work */
555
556 return lsym_ident; /* the ident is not in the list */
557 }
558
559 /* Reads the next token, placing it in the global variable "token". */
560 lexer_symbol
561 lexi(struct parser_state *state)
562 {
563 token.e = token.s;
564 state->col_1 = state->last_nl;
565 state->last_nl = false;
566
567 while (is_hspace(*inp.s)) {
568 state->col_1 = false;
569 inbuf_skip();
570 }
571
572 lexer_symbol alnum_lsym = lexi_alnum(state);
573 if (alnum_lsym != lsym_eof)
574 return lexi_end(state, alnum_lsym);
575
576 /* Scan a non-alphanumeric token */
577
578 check_size_token(3); /* for things like "<<=" */
579 *token.e++ = inbuf_next();
580 *token.e = '\0';
581
582 lexer_symbol lsym;
583 bool unary_delim = false; /* whether the current token forces a
584 * following operator to be unary */
585
586 switch (*token.s) {
587 case '\n':
588 unary_delim = state->next_unary;
589 state->last_nl = true; /* remember that we just had a newline */
590 /* if data has been exhausted, the newline is a dummy. */
591 lsym = had_eof ? lsym_eof : lsym_newline;
592 break;
593
594 case '\'':
595 case '"':
596 lex_char_or_string();
597 lsym = lsym_ident;
598 break;
599
600 case '(':
601 case '[':
602 unary_delim = true;
603 lsym = lsym_lparen_or_lbracket;
604 break;
605
606 case ')':
607 case ']':
608 lsym = lsym_rparen_or_rbracket;
609 break;
610
611 case '#':
612 unary_delim = state->next_unary;
613 lsym = lsym_preprocessing;
614 break;
615
616 case '?':
617 unary_delim = true;
618 lsym = lsym_question;
619 break;
620
621 case ':':
622 lsym = lsym_colon;
623 unary_delim = true;
624 break;
625
626 case ';':
627 unary_delim = true;
628 lsym = lsym_semicolon;
629 break;
630
631 case '{':
632 unary_delim = true;
633 lsym = lsym_lbrace;
634 break;
635
636 case '}':
637 unary_delim = true;
638 lsym = lsym_rbrace;
639 break;
640
641 case '\f':
642 unary_delim = state->next_unary;
643 state->last_nl = true; /* remember this, so we can set 'state->col_1'
644 * right */
645 lsym = lsym_form_feed;
646 break;
647
648 case ',':
649 unary_delim = true;
650 lsym = lsym_comma;
651 break;
652
653 case '.':
654 unary_delim = false;
655 lsym = lsym_period;
656 break;
657
658 case '-':
659 case '+':
660 lsym = state->next_unary ? lsym_unary_op : lsym_binary_op;
661 unary_delim = true;
662
663 if (*inp.s == token.s[0]) { /* ++, -- */
664 *token.e++ = *inp.s++;
665 if (state->last_token == lsym_ident ||
666 state->last_token == lsym_rparen_or_rbracket) {
667 lsym = state->next_unary ? lsym_unary_op : lsym_postfix_op;
668 unary_delim = false;
669 }
670
671 } else if (*inp.s == '=') { /* += */
672 *token.e++ = *inp.s++;
673
674 } else if (*inp.s == '>') { /* -> */
675 *token.e++ = *inp.s++;
676 unary_delim = false;
677 lsym = lsym_unary_op;
678 state->want_blank = false;
679 }
680 break;
681
682 case '=':
683 if (state->init_or_struct)
684 state->block_init = true;
685 if (*inp.s == '=') { /* == */
686 *token.e++ = *inp.s++;
687 *token.e = '\0';
688 }
689 lsym = lsym_binary_op;
690 unary_delim = true;
691 break;
692
693 case '>':
694 case '<':
695 case '!': /* ops like <, <<, <=, !=, etc */
696 if (*inp.s == '>' || *inp.s == '<' || *inp.s == '=')
697 *token.e++ = inbuf_next();
698 if (*inp.s == '=')
699 *token.e++ = *inp.s++;
700 lsym = state->next_unary ? lsym_unary_op : lsym_binary_op;
701 unary_delim = true;
702 break;
703
704 case '*':
705 unary_delim = true;
706 if (!state->next_unary) {
707 if (*inp.s == '=')
708 *token.e++ = *inp.s++;
709 lsym = lsym_binary_op;
710 break;
711 }
712
713 while (*inp.s == '*' || isspace((unsigned char)*inp.s)) {
714 if (*inp.s == '*')
715 token_add_char('*');
716 inbuf_skip();
717 }
718
719 if (ps.in_decl) {
720 char *tp = inp.s;
721
722 while (isalpha((unsigned char)*tp) ||
723 isspace((unsigned char)*tp)) {
724 if (++tp >= inp.e)
725 inbuf_read_line();
726 }
727 if (*tp == '(')
728 ps.procname[0] = ' ';
729 }
730
731 lsym = lsym_unary_op;
732 break;
733
734 default:
735 if (token.s[0] == '/' && (*inp.s == '*' || *inp.s == '/')) {
736 /* it is start of comment */
737 *token.e++ = inbuf_next();
738
739 lsym = lsym_comment;
740 unary_delim = state->next_unary;
741 break;
742 }
743
744 while (token.e[-1] == *inp.s || *inp.s == '=') {
745 /* handle '||', '&&', etc., and also things as in 'int *****i' */
746 token_add_char(inbuf_next());
747 }
748
749 lsym = state->next_unary ? lsym_unary_op : lsym_binary_op;
750 unary_delim = true;
751 }
752
753 if (inp.s >= inp.e) /* check for input buffer empty */
754 inbuf_read_line();
755
756 state->next_unary = unary_delim;
757
758 check_size_token(1);
759 *token.e = '\0';
760
761 return lexi_end(state, lsym);
762 }
763
764 void
765 add_typename(const char *name)
766 {
767 if (typenames.len >= typenames.cap) {
768 typenames.cap = 16 + 2 * typenames.cap;
769 typenames.items = xrealloc(typenames.items,
770 sizeof(typenames.items[0]) * typenames.cap);
771 }
772
773 int pos = bsearch_typenames(name);
774 if (pos >= 0)
775 return; /* already in the list */
776
777 pos = -(pos + 1);
778 memmove(typenames.items + pos + 1, typenames.items + pos,
779 sizeof(typenames.items[0]) * (typenames.len++ - (unsigned)pos));
780 typenames.items[pos] = xstrdup(name);
781 }
782