lexi.c revision 1.56 1 /* $NetBSD: lexi.c,v 1.56 2021/09/25 19:49:13 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.56 2021/09/25 19:49:13 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 /* Reads the next token, placing it in the global variable "token". */
340 token_type
341 lexi(struct parser_state *state)
342 {
343 bool unary_delim; /* whether the current token
344 * forces a following operator to be unary */
345 token_type ttype;
346
347 token.e = token.s; /* point to start of place to save token */
348 unary_delim = false;
349 state->col_1 = state->last_nl; /* tell world that this token started
350 * in column 1 iff the last thing
351 * scanned was a newline */
352 state->last_nl = false;
353
354 while (*buf_ptr == ' ' || *buf_ptr == '\t') { /* get rid of blanks */
355 state->col_1 = false; /* leading blanks imply token is not in column
356 * 1 */
357 inbuf_skip();
358 }
359
360 /* Scan an alphanumeric token */
361 if (isalnum((unsigned char)*buf_ptr) ||
362 *buf_ptr == '_' || *buf_ptr == '$' ||
363 (buf_ptr[0] == '.' && isdigit((unsigned char)buf_ptr[1]))) {
364 /*
365 * we have a letter or number
366 */
367 struct templ *p;
368
369 if (isdigit((unsigned char)*buf_ptr) ||
370 (buf_ptr[0] == '.' && isdigit((unsigned char)buf_ptr[1]))) {
371 lex_number();
372 } else {
373 lex_word();
374 }
375 *token.e = '\0';
376
377 if (token.s[0] == 'L' && token.s[1] == '\0' &&
378 (*buf_ptr == '"' || *buf_ptr == '\''))
379 return lexi_end(string_prefix);
380
381 while (*buf_ptr == ' ' || *buf_ptr == '\t') /* get rid of blanks */
382 inbuf_next();
383 state->keyword = rw_0;
384 if (state->last_token == keyword_struct_union_enum &&
385 state->p_l_follow == 0) {
386 /* if last token was 'struct' and we're not in parentheses, then
387 * this token should be treated as a declaration */
388 state->last_u_d = true;
389 return lexi_end(decl);
390 }
391 /*
392 * Operator after identifier is binary unless last token was 'struct'
393 */
394 state->last_u_d = (state->last_token == keyword_struct_union_enum);
395
396 p = bsearch(token.s, specials, sizeof specials / sizeof specials[0],
397 sizeof specials[0], compare_templ_array);
398 if (p == NULL) { /* not a special keyword... */
399 char *u;
400
401 /* ... so maybe a type_t or a typedef */
402 if ((opt.auto_typedefs && ((u = strrchr(token.s, '_')) != NULL) &&
403 strcmp(u, "_t") == 0) || (typename_top >= 0 &&
404 bsearch(token.s, typenames, (size_t)typename_top + 1,
405 sizeof typenames[0], compare_string_array) != NULL)) {
406 state->keyword = rw_type;
407 state->last_u_d = true;
408 goto found_typename;
409 }
410 } else { /* we have a keyword */
411 state->keyword = p->rwcode;
412 state->last_u_d = true;
413 switch (p->rwcode) {
414 case rw_switch:
415 return lexi_end(switch_expr);
416 case rw_case_or_default:
417 return lexi_end(case_label);
418 case rw_struct_or_union_or_enum:
419 case rw_type:
420 found_typename:
421 if (state->p_l_follow != 0) {
422 /* inside parens: cast, param list, offsetof or sizeof */
423 state->cast_mask |= (1 << state->p_l_follow) & ~state->not_cast_mask;
424 }
425 if (state->last_token == period || state->last_token == unary_op) {
426 state->keyword = rw_0;
427 break;
428 }
429 if (p != NULL && p->rwcode == rw_struct_or_union_or_enum)
430 return lexi_end(keyword_struct_union_enum);
431 if (state->p_l_follow != 0)
432 break;
433 return lexi_end(decl);
434
435 case rw_for_or_if_or_while:
436 return lexi_end(keyword_for_if_while);
437
438 case rw_do_or_else:
439 return lexi_end(keyword_do_else);
440
441 case rw_storage_class:
442 return lexi_end(storage_class);
443
444 case rw_typedef:
445 return lexi_end(type_def);
446
447 default: /* all others are treated like any other
448 * identifier */
449 return lexi_end(ident);
450 } /* end of switch */
451 } /* end of if (found_it) */
452 if (*buf_ptr == '(' && state->tos <= 1 && state->ind_level == 0 &&
453 !state->in_parameter_declaration && !state->block_init) {
454 char *tp = buf_ptr;
455 while (tp < buf_end)
456 if (*tp++ == ')' && (*tp == ';' || *tp == ','))
457 goto not_proc;
458 strncpy(state->procname, token.s, sizeof state->procname - 1);
459 if (state->in_decl)
460 state->in_parameter_declaration = true;
461 return lexi_end(funcname);
462 not_proc:;
463 }
464 /*
465 * The following hack attempts to guess whether or not the current
466 * token is in fact a declaration keyword -- one that has been
467 * typedefd
468 */
469 else if (state->p_l_follow == 0 && !state->block_init &&
470 !state->in_stmt &&
471 ((*buf_ptr == '*' && buf_ptr[1] != '=') ||
472 isalpha((unsigned char)*buf_ptr)) &&
473 (state->last_token == semicolon || state->last_token == lbrace ||
474 state->last_token == rbrace)) {
475 state->keyword = rw_type;
476 state->last_u_d = true;
477 return lexi_end(decl);
478 }
479 if (state->last_token == decl) /* if this is a declared variable,
480 * then following sign is unary */
481 state->last_u_d = true; /* will make "int a -1" work */
482 return lexi_end(ident); /* the ident is not in the list */
483 } /* end of procesing for alpanum character */
484
485 /* Scan a non-alphanumeric token */
486
487 check_size_token(3); /* things like "<<=" */
488 *token.e++ = inbuf_next(); /* if it is only a one-character token, it is
489 * moved here */
490 *token.e = '\0';
491
492 switch (*token.s) {
493 case '\n':
494 unary_delim = state->last_u_d;
495 state->last_nl = true; /* remember that we just had a newline */
496 /* if data has been exhausted, the newline is a dummy. */
497 ttype = had_eof ? end_of_file : newline;
498 break;
499
500 case '\'':
501 case '"':
502 lex_char_or_string();
503 ttype = ident;
504 break;
505
506 case '(':
507 case '[':
508 unary_delim = true;
509 ttype = lparen;
510 break;
511
512 case ')':
513 case ']':
514 ttype = rparen;
515 break;
516
517 case '#':
518 unary_delim = state->last_u_d;
519 ttype = preprocessing;
520 break;
521
522 case '?':
523 unary_delim = true;
524 ttype = question;
525 break;
526
527 case ':':
528 ttype = colon;
529 unary_delim = true;
530 break;
531
532 case ';':
533 unary_delim = true;
534 ttype = semicolon;
535 break;
536
537 case '{':
538 unary_delim = true;
539 ttype = lbrace;
540 break;
541
542 case '}':
543 unary_delim = true;
544 ttype = rbrace;
545 break;
546
547 case 014: /* a form feed */
548 unary_delim = state->last_u_d;
549 state->last_nl = true; /* remember this so we can set 'state->col_1'
550 * right */
551 ttype = form_feed;
552 break;
553
554 case ',':
555 unary_delim = true;
556 ttype = comma;
557 break;
558
559 case '.':
560 unary_delim = false;
561 ttype = period;
562 break;
563
564 case '-':
565 case '+': /* check for -, +, --, ++ */
566 ttype = state->last_u_d ? unary_op : binary_op;
567 unary_delim = true;
568
569 if (*buf_ptr == token.s[0]) {
570 /* check for doubled character */
571 *token.e++ = *buf_ptr++;
572 /* buffer overflow will be checked at end of loop */
573 if (state->last_token == ident || state->last_token == rparen) {
574 ttype = state->last_u_d ? unary_op : postfix_op;
575 /* check for following ++ or -- */
576 unary_delim = false;
577 }
578 } else if (*buf_ptr == '=')
579 /* check for operator += */
580 *token.e++ = *buf_ptr++;
581 else if (*buf_ptr == '>') {
582 /* check for operator -> */
583 *token.e++ = *buf_ptr++;
584 unary_delim = false;
585 ttype = unary_op;
586 state->want_blank = false;
587 }
588 break; /* buffer overflow will be checked at end of
589 * switch */
590
591 case '=':
592 if (state->in_or_st)
593 state->block_init = true;
594 if (*buf_ptr == '=') { /* == */
595 *token.e++ = '='; /* Flip =+ to += */
596 buf_ptr++;
597 *token.e = 0;
598 }
599 ttype = binary_op;
600 unary_delim = true;
601 break;
602 /* can drop thru!!! */
603
604 case '>':
605 case '<':
606 case '!': /* ops like <, <<, <=, !=, etc */
607 if (*buf_ptr == '>' || *buf_ptr == '<' || *buf_ptr == '=')
608 *token.e++ = inbuf_next();
609 if (*buf_ptr == '=')
610 *token.e++ = *buf_ptr++;
611 ttype = state->last_u_d ? unary_op : binary_op;
612 unary_delim = true;
613 break;
614
615 case '*':
616 unary_delim = true;
617 if (!state->last_u_d) {
618 if (*buf_ptr == '=')
619 *token.e++ = *buf_ptr++;
620 ttype = binary_op;
621 break;
622 }
623 while (*buf_ptr == '*' || isspace((unsigned char)*buf_ptr)) {
624 if (*buf_ptr == '*') {
625 check_size_token(1);
626 *token.e++ = *buf_ptr;
627 }
628 inbuf_skip();
629 }
630 if (ps.in_decl) {
631 char *tp = buf_ptr;
632
633 while (isalpha((unsigned char)*tp) ||
634 isspace((unsigned char)*tp)) {
635 if (++tp >= buf_end)
636 fill_buffer();
637 }
638 if (*tp == '(')
639 ps.procname[0] = ' ';
640 }
641 ttype = unary_op;
642 break;
643
644 default:
645 if (token.s[0] == '/' && (*buf_ptr == '*' || *buf_ptr == '/')) {
646 /* it is start of comment */
647 *token.e++ = inbuf_next();
648
649 ttype = comment;
650 unary_delim = state->last_u_d;
651 break;
652 }
653 while (token.e[-1] == *buf_ptr || *buf_ptr == '=') {
654 /*
655 * handle ||, &&, etc, and also things as in int *****i
656 */
657 check_size_token(1);
658 *token.e++ = inbuf_next();
659 }
660 ttype = state->last_u_d ? unary_op : binary_op;
661 unary_delim = true;
662 }
663
664 if (buf_ptr >= buf_end) /* check for input buffer empty */
665 fill_buffer();
666 state->last_u_d = unary_delim;
667 check_size_token(1);
668 *token.e = '\0';
669 return lexi_end(ttype);
670 }
671
672 void
673 alloc_typenames(void)
674 {
675
676 typenames = xmalloc(sizeof(typenames[0]) * (typename_count = 16));
677 }
678
679 void
680 add_typename(const char *key)
681 {
682 int comparison;
683
684 if (typename_top + 1 >= typename_count) {
685 typenames = xrealloc((void *)typenames,
686 sizeof(typenames[0]) * (typename_count *= 2));
687 }
688 if (typename_top == -1)
689 typenames[++typename_top] = xstrdup(key);
690 else if ((comparison = strcmp(key, typenames[typename_top])) >= 0) {
691 /* take advantage of sorted input */
692 if (comparison == 0) /* remove duplicates */
693 return;
694 typenames[++typename_top] = xstrdup(key);
695 } else {
696 int p;
697
698 for (p = 0; (comparison = strcmp(key, typenames[p])) > 0; p++)
699 /* find place for the new key */;
700 if (comparison == 0) /* remove duplicates */
701 return;
702 memmove(&typenames[p + 1], &typenames[p],
703 sizeof(typenames[0]) * (++typename_top - p));
704 typenames[p] = xstrdup(key);
705 }
706 }
707