lexi.c revision 1.101 1 /* $NetBSD: lexi.c,v 1.101 2021/10/25 21:33:24 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.101 2021/10/25 21:33:24 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 static const char *name[] = {
266 "0",
267 "offsetof",
268 "sizeof",
269 "struct_or_union_or_enum",
270 "type",
271 "for",
272 "if",
273 "while",
274 "do",
275 "else",
276 "switch",
277 "case_or_default",
278 "jump",
279 "storage_class",
280 "typedef",
281 "inline_or_restrict",
282 };
283
284 return name[kw];
285 }
286
287 static void
288 debug_print_buf(const char *name, const struct buffer *buf)
289 {
290 if (buf->s < buf->e) {
291 debug_printf("%s ", name);
292 debug_vis_range("\"", buf->s, buf->e, "\"\n");
293 }
294 }
295
296 static void
297 debug_lexi(lexer_symbol lsym)
298 {
299 debug_printf("\n");
300 debug_printf("line %d\n", line_no);
301 debug_print_buf("label", &lab);
302 debug_print_buf("code", &code);
303 debug_print_buf("comment", &com);
304 debug_printf("lexi returns '%s'", lsym_name(lsym));
305 if (ps.keyword != kw_0)
306 debug_printf(" keyword '%s'", kw_name(ps.keyword));
307 debug_printf("\n");
308 debug_print_buf("token", &token);
309 }
310 #endif
311
312 static lexer_symbol
313 lexi_end(lexer_symbol lsym)
314 {
315 #ifdef debug
316 debug_lexi(lsym);
317 #endif
318 return lsym;
319 }
320
321 static void
322 lex_number(void)
323 {
324 for (uint8_t s = 'A'; s != 'f' && s != 'i' && s != 'u';) {
325 uint8_t ch = (uint8_t)*inp.s;
326 if (ch >= array_length(lex_number_row) || lex_number_row[ch] == 0)
327 break;
328
329 uint8_t row = lex_number_row[ch];
330 if (lex_number_state[row][s - 'A'] == ' ') {
331 /*-
332 * lex_number_state[0][s - 'A'] now indicates the type:
333 * f = floating, i = integer, u = unknown
334 */
335 break;
336 }
337
338 s = lex_number_state[row][s - 'A'];
339 token_add_char(inbuf_next());
340 }
341 }
342
343 static void
344 lex_word(void)
345 {
346 while (isalnum((unsigned char)*inp.s) ||
347 *inp.s == '\\' ||
348 *inp.s == '_' || *inp.s == '$') {
349
350 if (*inp.s == '\\') {
351 if (inp.s[1] == '\n') {
352 inp.s += 2;
353 if (inp.s >= inp.e)
354 inbuf_read_line();
355 } else
356 break;
357 }
358
359 token_add_char(inbuf_next());
360 }
361 }
362
363 static void
364 lex_char_or_string(void)
365 {
366 for (char delim = *token.s;;) {
367 if (*inp.s == '\n') {
368 diag(1, "Unterminated literal");
369 return;
370 }
371
372 token_add_char(inbuf_next());
373 if (token.e[-1] == delim)
374 return;
375
376 if (token.e[-1] == '\\') {
377 if (*inp.s == '\n')
378 ++line_no;
379 token_add_char(inbuf_next());
380 }
381 }
382 }
383
384 /* Guess whether the current token is a declared type. */
385 static bool
386 probably_typename(const struct parser_state *state)
387 {
388 if (state->p_l_follow != 0)
389 return false;
390 if (state->block_init || state->in_stmt)
391 return false;
392 if (inp.s[0] == '*' && inp.s[1] != '=')
393 goto maybe;
394 if (isalpha((unsigned char)*inp.s))
395 goto maybe;
396 return false;
397 maybe:
398 return state->last_token == lsym_semicolon ||
399 state->last_token == lsym_lbrace ||
400 state->last_token == lsym_rbrace;
401 }
402
403 static int
404 bsearch_typenames(const char *key)
405 {
406 const char **arr = typenames.items;
407 int lo = 0;
408 int hi = (int)typenames.len - 1;
409
410 while (lo <= hi) {
411 int mid = (int)((unsigned)(lo + hi) >> 1);
412 int cmp = strcmp(arr[mid], key);
413 if (cmp < 0)
414 lo = mid + 1;
415 else if (cmp > 0)
416 hi = mid - 1;
417 else
418 return mid;
419 }
420 return -(lo + 1);
421 }
422
423 static bool
424 is_typename(void)
425 {
426 if (opt.auto_typedefs &&
427 token.e - token.s >= 2 && memcmp(token.e - 2, "_t", 2) == 0)
428 return true;
429
430 return bsearch_typenames(token.s) >= 0;
431 }
432
433 /* Read an alphanumeric token into 'token', or return end_of_file. */
434 static lexer_symbol
435 lexi_alnum(struct parser_state *state)
436 {
437 if (!(isalnum((unsigned char)*inp.s) ||
438 *inp.s == '_' || *inp.s == '$' ||
439 (inp.s[0] == '.' && isdigit((unsigned char)inp.s[1]))))
440 return lsym_eof; /* just as a placeholder */
441
442 if (isdigit((unsigned char)*inp.s) ||
443 (inp.s[0] == '.' && isdigit((unsigned char)inp.s[1]))) {
444 lex_number();
445 } else {
446 lex_word();
447 }
448 *token.e = '\0';
449
450 if (token.s[0] == 'L' && token.s[1] == '\0' &&
451 (*inp.s == '"' || *inp.s == '\''))
452 return lsym_string_prefix;
453
454 while (is_hspace(inbuf_peek()))
455 inbuf_skip();
456 state->keyword = kw_0;
457
458 if (state->last_token == lsym_tag &&
459 state->p_l_follow == 0) {
460 state->next_unary = true;
461 return lsym_type;
462 }
463
464 /* Operator after identifier is binary unless last token was 'struct'. */
465 state->next_unary = state->last_token == lsym_tag;
466
467 const struct keyword *kw = bsearch(token.s, keywords,
468 array_length(keywords), sizeof(keywords[0]), cmp_keyword_by_name);
469 if (kw == NULL) {
470 if (is_typename()) {
471 state->keyword = kw_type;
472 state->next_unary = true;
473 goto found_typename;
474 }
475
476 } else { /* we have a keyword */
477 state->keyword = kw->kind;
478 state->next_unary = true;
479
480 switch (kw->kind) {
481 case kw_switch:
482 return lsym_switch;
483
484 case kw_case_or_default:
485 return lsym_case_label;
486
487 case kw_struct_or_union_or_enum:
488 case kw_type:
489 found_typename:
490 if (state->p_l_follow != 0) {
491 /* inside parens: cast, param list, offsetof or sizeof */
492 state->cast_mask |= (1 << state->p_l_follow) & ~state->not_cast_mask;
493 }
494 if (state->last_token == lsym_period ||
495 state->last_token == lsym_unary_op) {
496 state->keyword = kw_0;
497 break;
498 }
499 if (kw != NULL && kw->kind == kw_struct_or_union_or_enum)
500 return lsym_tag;
501 if (state->p_l_follow != 0)
502 break;
503 return lsym_type;
504
505 case kw_for:
506 return lsym_for;
507
508 case kw_if:
509 return lsym_if;
510
511 case kw_while:
512 return lsym_while;
513
514 case kw_do:
515 return lsym_do;
516
517 case kw_else:
518 return lsym_else;
519
520 case kw_storage_class:
521 return lsym_storage_class;
522
523 case kw_typedef:
524 return lsym_typedef;
525
526 default: /* all others are treated like any other
527 * identifier */
528 return lsym_ident;
529 }
530 }
531
532 if (*inp.s == '(' && state->tos <= 1 && state->ind_level == 0 &&
533 !state->in_parameter_declaration && !state->block_init) {
534
535 for (const char *p = inp.s; p < inp.e;)
536 if (*p++ == ')' && (*p == ';' || *p == ','))
537 goto not_proc;
538
539 strncpy(state->procname, token.s, sizeof state->procname - 1);
540 if (state->in_decl)
541 state->in_parameter_declaration = true;
542 return lsym_funcname;
543 not_proc:;
544
545 } else if (probably_typename(state)) {
546 state->keyword = kw_type;
547 state->next_unary = true;
548 return lsym_type;
549 }
550
551 if (state->last_token == lsym_type) /* if this is a declared variable,
552 * then following sign is unary */
553 state->next_unary = true; /* will make "int a -1" work */
554
555 return lsym_ident; /* the ident is not in the list */
556 }
557
558 /* Reads the next token, placing it in the global variable "token". */
559 lexer_symbol
560 lexi(struct parser_state *state)
561 {
562 token.e = token.s;
563 state->col_1 = state->last_nl;
564 state->last_nl = false;
565
566 while (is_hspace(*inp.s)) {
567 state->col_1 = false;
568 inbuf_skip();
569 }
570
571 lexer_symbol alnum_lsym = lexi_alnum(state);
572 if (alnum_lsym != lsym_eof)
573 return lexi_end(alnum_lsym);
574
575 /* Scan a non-alphanumeric token */
576
577 check_size_token(3); /* for things like "<<=" */
578 *token.e++ = inbuf_next();
579 *token.e = '\0';
580
581 lexer_symbol lsym;
582 bool unary_delim = false; /* whether the current token forces a
583 * following operator to be unary */
584
585 switch (*token.s) {
586 case '\n':
587 unary_delim = state->next_unary;
588 state->last_nl = true; /* remember that we just had a newline */
589 /* if data has been exhausted, the newline is a dummy. */
590 lsym = had_eof ? lsym_eof : lsym_newline;
591 break;
592
593 case '\'':
594 case '"':
595 lex_char_or_string();
596 lsym = lsym_ident;
597 break;
598
599 case '(':
600 case '[':
601 unary_delim = true;
602 lsym = lsym_lparen_or_lbracket;
603 break;
604
605 case ')':
606 case ']':
607 lsym = lsym_rparen_or_rbracket;
608 break;
609
610 case '#':
611 unary_delim = state->next_unary;
612 lsym = lsym_preprocessing;
613 break;
614
615 case '?':
616 unary_delim = true;
617 lsym = lsym_question;
618 break;
619
620 case ':':
621 lsym = lsym_colon;
622 unary_delim = true;
623 break;
624
625 case ';':
626 unary_delim = true;
627 lsym = lsym_semicolon;
628 break;
629
630 case '{':
631 unary_delim = true;
632 lsym = lsym_lbrace;
633 break;
634
635 case '}':
636 unary_delim = true;
637 lsym = lsym_rbrace;
638 break;
639
640 case '\f':
641 unary_delim = state->next_unary;
642 state->last_nl = true; /* remember this, so we can set 'state->col_1'
643 * right */
644 lsym = lsym_form_feed;
645 break;
646
647 case ',':
648 unary_delim = true;
649 lsym = lsym_comma;
650 break;
651
652 case '.':
653 unary_delim = false;
654 lsym = lsym_period;
655 break;
656
657 case '-':
658 case '+':
659 lsym = state->next_unary ? lsym_unary_op : lsym_binary_op;
660 unary_delim = true;
661
662 if (*inp.s == token.s[0]) { /* ++, -- */
663 *token.e++ = *inp.s++;
664 if (state->last_token == lsym_ident ||
665 state->last_token == lsym_rparen_or_rbracket) {
666 lsym = state->next_unary ? lsym_unary_op : lsym_postfix_op;
667 unary_delim = false;
668 }
669
670 } else if (*inp.s == '=') { /* += */
671 *token.e++ = *inp.s++;
672
673 } else if (*inp.s == '>') { /* -> */
674 *token.e++ = *inp.s++;
675 unary_delim = false;
676 lsym = lsym_unary_op;
677 state->want_blank = false;
678 }
679 break;
680
681 case '=':
682 if (state->init_or_struct)
683 state->block_init = true;
684 if (*inp.s == '=') { /* == */
685 *token.e++ = *inp.s++;
686 *token.e = '\0';
687 }
688 lsym = lsym_binary_op;
689 unary_delim = true;
690 break;
691
692 case '>':
693 case '<':
694 case '!': /* ops like <, <<, <=, !=, etc */
695 if (*inp.s == '>' || *inp.s == '<' || *inp.s == '=')
696 *token.e++ = inbuf_next();
697 if (*inp.s == '=')
698 *token.e++ = *inp.s++;
699 lsym = state->next_unary ? lsym_unary_op : lsym_binary_op;
700 unary_delim = true;
701 break;
702
703 case '*':
704 unary_delim = true;
705 if (!state->next_unary) {
706 if (*inp.s == '=')
707 *token.e++ = *inp.s++;
708 lsym = lsym_binary_op;
709 break;
710 }
711
712 while (*inp.s == '*' || isspace((unsigned char)*inp.s)) {
713 if (*inp.s == '*')
714 token_add_char('*');
715 inbuf_skip();
716 }
717
718 if (ps.in_decl) {
719 char *tp = inp.s;
720
721 while (isalpha((unsigned char)*tp) ||
722 isspace((unsigned char)*tp)) {
723 if (++tp >= inp.e)
724 inbuf_read_line();
725 }
726 if (*tp == '(')
727 ps.procname[0] = ' ';
728 }
729
730 lsym = lsym_unary_op;
731 break;
732
733 default:
734 if (token.s[0] == '/' && (*inp.s == '*' || *inp.s == '/')) {
735 /* it is start of comment */
736 *token.e++ = inbuf_next();
737
738 lsym = lsym_comment;
739 unary_delim = state->next_unary;
740 break;
741 }
742
743 while (token.e[-1] == *inp.s || *inp.s == '=') {
744 /* handle '||', '&&', etc., and also things as in 'int *****i' */
745 token_add_char(inbuf_next());
746 }
747
748 lsym = state->next_unary ? lsym_unary_op : lsym_binary_op;
749 unary_delim = true;
750 }
751
752 if (inp.s >= inp.e) /* check for input buffer empty */
753 inbuf_read_line();
754
755 state->next_unary = unary_delim;
756
757 check_size_token(1);
758 *token.e = '\0';
759
760 return lexi_end(lsym);
761 }
762
763 void
764 add_typename(const char *name)
765 {
766 if (typenames.len >= typenames.cap) {
767 typenames.cap = 16 + 2 * typenames.cap;
768 typenames.items = xrealloc(typenames.items,
769 sizeof(typenames.items[0]) * typenames.cap);
770 }
771
772 int pos = bsearch_typenames(name);
773 if (pos >= 0)
774 return; /* already in the list */
775
776 pos = -(pos + 1);
777 memmove(typenames.items + pos + 1, typenames.items + pos,
778 sizeof(typenames.items[0]) * (typenames.len++ - (unsigned)pos));
779 typenames.items[pos] = xstrdup(name);
780 }
781