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