1/* $NetBSD: read.c,v 1.92 2024/05/12 18:49:36 rillig Exp $ */
2
3/*
4 * Copyright (c) 1996 Christopher G. Demetriou.  All Rights Reserved.
5 * Copyright (c) 1994, 1995 Jochen Pohl
6 * All Rights Reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 *    must display the following acknowledgement:
18 *	This product includes software developed by Jochen Pohl for
19 *	The NetBSD Project.
20 * 4. The name of the author may not be used to endorse or promote products
21 *    derived from this software without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
24 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
25 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
26 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
28 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
32 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 */
34
35#if HAVE_NBTOOL_CONFIG_H
36#include "nbtool_config.h"
37#endif
38
39#include <sys/cdefs.h>
40#if defined(__RCSID)
41__RCSID("$NetBSD: read.c,v 1.92 2024/05/12 18:49:36 rillig Exp $");
42#endif
43
44#include <ctype.h>
45#include <limits.h>
46#include <stdarg.h>
47#include <stdio.h>
48#include <stdlib.h>
49#include <string.h>
50
51#include "lint2.h"
52
53
54/* index of current (included) source file */
55static int srcfile;
56
57/*
58 * The array pointed to by inpfns maps the file name indices of input files
59 * to the file name indices used in lint2
60 */
61static short *inpfns;
62static size_t ninpfns;
63
64/*
65 * The array pointed to by *fnames maps file name indices to file names.
66 * Indices of type short are used instead of pointers to save memory.
67 */
68const char **fnames;
69static size_t *flines;
70static size_t nfnames;
71
72/*
73 * Types are shared (to save memory for the types itself) and accessed
74 * via indices (to save memory for references to types (indices are short)).
75 * To share types, an equal type must be located fast. This is done by a
76 * hash table. Access by indices is done via an array of pointers to the
77 * types.
78 */
79typedef struct thtab {
80	const char *th_name;
81	unsigned short th_idx;
82	struct thtab *th_next;
83} thtab_t;
84static thtab_t *thtab[1009];		/* hash table */
85type_t **tlst;				/* array for indexed access */
86static size_t tlstlen;		/* length of tlst */
87
88static hte_t **renametab;
89
90/* index of current C source file (as specified at the command line) */
91static int csrcfile;
92
93static const char *readfile_line;
94
95static void inperr(const char *, ...)
96    __printflike(1, 2) __attribute__((noreturn));
97static void setsrc(const char *);
98static void setfnid(int, const char *);
99static void funccall(pos_t, const char *);
100static void decldef(pos_t, const char *);
101static void usedsym(pos_t, const char *);
102static unsigned short inptype(const char *, const char **);
103static size_t gettlen(const char *, const char **);
104static unsigned short findtype(const char *, size_t, int);
105static unsigned short storetyp(type_t *, const char *, size_t, int);
106static unsigned int thash(const char *, size_t);
107static char *inpqstrg(const char *, const char **);
108static const char *inpname(const char *, const char **);
109static int getfnidx(const char *);
110
111/* Allocate zero-initialized memory that doesn't need to be freed. */
112static void *
113xalloc(size_t sz)
114{
115
116	void *ptr = xmalloc(sz);
117	(void)memset(ptr, 0, sz);
118	return ptr;
119}
120
121static bool
122try_parse_int(const char **p, int *num)
123{
124	char *end;
125
126	*num = (int)strtol(*p, &end, 10);
127	if (end == *p)
128		return false;
129	*p = end;
130	return true;
131}
132
133static int
134parse_int(const char **p)
135{
136	char *end;
137	int n;
138
139	n = (int)strtol(*p, &end, 10);
140	if (end == *p)
141		inperr("not a number: %s", *p);
142	*p = end;
143	return n;
144}
145
146static short
147parse_short(const char **p)
148{
149	return (short)parse_int(p);
150}
151
152static void
153read_ln_line(const char *line)
154{
155	const char *cp;
156	int cline, isrc, iline;
157	char rt;
158	pos_t pos;
159
160	cp = line;
161
162	/* line number in csrcfile */
163	if (!try_parse_int(&cp, &cline))
164		cline = -1;
165
166	/* record type */
167	if (*cp == '\0')
168		inperr("missing record type");
169	rt = *cp++;
170
171	if (rt == 'S') {
172		setsrc(cp);
173		return;
174	}
175	if (rt == 's') {
176		setfnid(cline, cp);
177		return;
178	}
179
180	/*
181	 * Index of (included) source file. If this index is different from
182	 * csrcfile, it refers to an included file.
183	 */
184	isrc = parse_int(&cp);
185	isrc = inpfns[isrc];
186
187	/* line number in isrc */
188	if (*cp++ != '.')
189		inperr("bad line number");
190	iline = parse_int(&cp);
191
192	pos.p_src = (unsigned short)csrcfile;
193	pos.p_line = (unsigned short)cline;
194	pos.p_isrc = (unsigned short)isrc;
195	pos.p_iline = (unsigned short)iline;
196
197	/* process rest of this record */
198	switch (rt) {
199	case 'c':
200		funccall(pos, cp);
201		break;
202	case 'd':
203		decldef(pos, cp);
204		break;
205	case 'u':
206		usedsym(pos, cp);
207		break;
208	default:
209		inperr("bad record type %c", rt);
210	}
211}
212
213void
214readfile(const char *name)
215{
216	FILE *inp;
217	size_t len;
218	char *line;
219
220	if (inpfns == NULL)
221		inpfns = xcalloc(ninpfns = 128, sizeof(*inpfns));
222	if (fnames == NULL)
223		fnames = xcalloc(nfnames = 256, sizeof(*fnames));
224	if (flines == NULL)
225		flines = xcalloc(nfnames, sizeof(*flines));
226	if (tlstlen == 0)
227		tlst = xcalloc(tlstlen = 256, sizeof(*tlst));
228
229	renametab = htab_new();
230
231	srcfile = getfnidx(name);
232
233	if ((inp = fopen(name, "r")) == NULL)
234		err(1, "cannot open %s", name);
235
236	while ((line = fgetln(inp, &len)) != NULL) {
237		flines[srcfile]++;
238
239		readfile_line = line;
240		if (len == 0 || line[len - 1] != '\n')
241			inperr("missing newline after '%s'", &line[len - 1]);
242		line[len - 1] = '\0';
243
244		read_ln_line(line);
245		readfile_line = NULL;
246	}
247
248	hash_free(renametab);
249
250	if (ferror(inp) != 0)
251		err(1, "read error on %s", name);
252
253	(void)fclose(inp);
254}
255
256
257static void
258inperr(const char *fmt, ...)
259{
260	va_list ap;
261	char buf[1024];
262
263	va_start(ap, fmt);
264	(void)vsnprintf(buf, sizeof(buf), fmt, ap);
265	va_end(ap);
266
267	errx(1, "error: %s:%zu: %s (for '%s')",
268	    fnames[srcfile], flines[srcfile], buf, readfile_line);
269}
270
271/*
272 * Set the name of the C source file of the .ln file which is
273 * currently read.
274 */
275static void
276setsrc(const char *cp)
277{
278
279	csrcfile = getfnidx(cp);
280}
281
282/*
283 * setfnid() gets as input an index as used in an input file and the
284 * associated file name. If necessary, it creates a new lint2 file
285 * name index for this file name and creates the mapping of the index
286 * as used in the input file to the index used in lint2.
287 */
288static void
289setfnid(int fid, const char *cp)
290{
291
292	if (fid < 0)
293		inperr("bad fid");
294
295	if ((size_t)fid >= ninpfns) {
296		inpfns = xrealloc(inpfns, (ninpfns * 2) * sizeof(*inpfns));
297		(void)memset(inpfns + ninpfns, 0, ninpfns * sizeof(*inpfns));
298		ninpfns *= 2;
299	}
300	/*
301	 * Should always be true because indices written in the output file by
302	 * lint1 are always the previous index + 1.
303	 */
304	if ((size_t)fid >= ninpfns)
305		errx(1, "internal error: setfnid");
306	inpfns[fid] = (unsigned short)getfnidx(cp);
307}
308
309/*
310 * Process a function call record (c-record).
311 */
312static void
313funccall(pos_t pos, const char *cp)
314{
315	arginf_t *ai, **lai;
316	char c;
317	bool rused, rdisc;
318	hte_t *hte;
319	fcall_t *fcall;
320	const char *name;
321
322	fcall = xalloc(sizeof(*fcall));
323	fcall->f_pos = pos;
324
325	/* read flags */
326	rused = rdisc = false;
327	lai = &fcall->f_args;
328
329again:
330	c = *cp++;
331	switch (c) {
332	case 'u':
333		if (rused || rdisc)
334			inperr("used or discovered: %c", c);
335		rused = true;
336		goto again;
337	case 'i':
338		if (rused || rdisc)
339			inperr("used or discovered: %c", c);
340		goto again;
341	case 'd':
342		if (rused || rdisc)
343			inperr("used or discovered: %c", c);
344		rdisc = true;
345		goto again;
346	case 'z':
347	case 'p':
348	case 'n':
349	case 's':
350		ai = xalloc(sizeof(*ai));
351		ai->a_num = parse_int(&cp);
352		if (c == 'z')
353			ai->a_pcon = ai->a_zero = true;
354		else if (c == 'p')
355			ai->a_pcon = true;
356		else if (c == 'n')
357			ai->a_ncon = true;
358		else {
359			ai->a_fmt = true;
360			ai->a_fstrg = inpqstrg(cp, &cp);
361		}
362		*lai = ai;
363		lai = &ai->a_next;
364		goto again;
365	default:
366		cp--;
367	}
368
369	fcall->f_rused = rused;
370	fcall->f_rdisc = rdisc;
371
372	/* read name of function */
373	name = inpname(cp, &cp);
374
375	/* first look it up in the renaming table, then in the normal table */
376	hte = hash_search(renametab, name, false);
377	if (hte != NULL)
378		hte = hte->h_hte;
379	else
380		hte = htab_search(name, true);
381	hte->h_used = true;
382
383	fcall->f_type = inptype(cp, &cp);
384
385	*hte->h_lcall = fcall;
386	hte->h_lcall = &fcall->f_next;
387
388	if (*cp != '\0')
389		inperr("trailing line data: %s", cp);
390}
391
392static bool
393parse_function_attribute(const char **pp, sym_t *sym, bool *used)
394{
395
396	switch (*(*pp)++) {
397	case 'd':
398		if (sym->s_def != NODECL)
399			inperr("def");
400		sym->s_def = DEF;
401		break;
402	case 'e':
403		if (sym->s_def != NODECL)
404			inperr("decl");
405		sym->s_def = DECL;
406		break;
407	case 'i':
408		if (sym->s_inline)
409			inperr("inline");
410		sym->s_inline = true;
411		break;
412	case 'o':
413		if (sym->s_old_style_function)
414			inperr("osdef");
415		sym->s_old_style_function = true;
416		break;
417	case 'r':
418		if (sym->s_function_has_return_value)
419			inperr("r");
420		sym->s_function_has_return_value = true;
421		break;
422	case 's':
423		if (sym->s_static)
424			inperr("static");
425		sym->s_static = true;
426		break;
427	case 't':
428		if (sym->s_def != NODECL)
429			inperr("tdef");
430		sym->s_def = TDEF;
431		break;
432	case 'u':
433		if (*used)
434			inperr("used");
435		*used = true;
436		break;
437	case 'v':
438		if (sym->s_check_only_first_args)
439			inperr("v");
440		sym->s_check_only_first_args = true;
441		sym->s_check_num_args = parse_short(pp);
442		break;
443	case 'P':
444		if (sym->s_printflike)
445			inperr("P");
446		sym->s_printflike = true;
447		sym->s_printflike_arg = parse_short(pp);
448		break;
449	case 'S':
450		if (sym->s_scanflike)
451			inperr("S");
452		sym->s_scanflike = true;
453		sym->s_scanflike_arg = parse_short(pp);
454		break;
455	default:
456		(*pp)--;
457		return false;
458	}
459	return true;
460}
461
462/*
463 * Process a declaration or definition (d-record).
464 */
465static void
466decldef(pos_t pos, const char *cp)
467{
468	sym_t *symp, sym;
469	char *tname;
470	bool used, renamed;
471	hte_t *hte, *renamehte = NULL;
472	const char *name, *newname;
473
474	(void)memset(&sym, 0, sizeof(sym));
475	sym.s_pos = pos;
476	sym.s_def = NODECL;
477
478	used = false;
479
480	while (parse_function_attribute(&cp, &sym, &used))
481		continue;
482
483	/* read symbol name, doing renaming if necessary */
484	name = inpname(cp, &cp);
485	renamed = false;
486	if (*cp == 'r') {
487		cp++;
488		tname = xstrdup(name);
489		newname = inpname(cp, &cp);
490
491		/* enter it and see if it's already been renamed */
492		renamehte = hash_search(renametab, tname, true);
493		if (renamehte->h_hte == NULL) {
494			hte = htab_search(newname, true);
495			renamehte->h_hte = hte;
496			renamed = true;
497		} else if (hte = renamehte->h_hte,
498		    strcmp(hte->h_name, newname) != 0) {
499			/* %s renamed multiple times  \t%s  ::  %s */
500			msg(18, tname, mkpos(&renamehte->h_syms->s_pos),
501			    mkpos(&sym.s_pos));
502		}
503		free(tname);
504	} else {
505		/* it might be a previously-done rename */
506		hte = hash_search(renametab, name, false);
507		if (hte != NULL)
508			hte = hte->h_hte;
509		else
510			hte = htab_search(name, true);
511	}
512	hte->h_used |= used;
513	if (sym.s_def == DEF || sym.s_def == TDEF)
514		hte->h_def = true;
515
516	sym.s_type = inptype(cp, &cp);
517
518	/*
519	 * Allocate memory for this symbol only if it was not already declared
520	 * or tentatively defined at the same location with the same type.
521	 * Works only for symbols with external linkage, because static
522	 * symbols, tentatively defined at the same location but in different
523	 * translation units are really different symbols.
524	 */
525	for (symp = hte->h_syms; symp != NULL; symp = symp->s_next) {
526		if (symp->s_pos.p_isrc == sym.s_pos.p_isrc &&
527		    symp->s_pos.p_iline == sym.s_pos.p_iline &&
528		    symp->s_type == sym.s_type &&
529		    ((symp->s_def == DECL && sym.s_def == DECL) ||
530		     (!sflag && symp->s_def == TDEF && sym.s_def == TDEF)) &&
531		    !symp->s_static && !sym.s_static)
532			break;
533	}
534
535	if (symp == NULL) {
536		if (sym.s_check_only_first_args ||
537		    sym.s_printflike || sym.s_scanflike) {
538			symp = xalloc(sizeof(*symp));
539			*symp = sym;
540		} else {
541			/* no need to allocate memory for unused members */
542			symp = xalloc(sizeof(symp->s_s));
543			symp->s_s = sym.s_s;
544		}
545		*hte->h_lsym = symp;
546		hte->h_lsym = &symp->s_next;
547
548		/* XXX hack so we can remember where a symbol was renamed */
549		if (renamed)
550			renamehte->h_syms = symp;
551	}
552
553	if (*cp != '\0')
554		inperr("trailing line: %s", cp);
555}
556
557/*
558 * Read an u-record (emitted by lint1 if a symbol was used).
559 */
560static void
561usedsym(pos_t pos, const char *cp)
562{
563	usym_t *usym;
564	hte_t *hte;
565	const char *name;
566
567	usym = xalloc(sizeof(*usym));
568	usym->u_pos = pos;
569
570	/* needed as delimiter between two numbers */
571	if (*cp++ != 'x')
572		inperr("bad delim %c", cp[-1]);
573
574	name = inpname(cp, &cp);
575	hte = hash_search(renametab, name, false);
576	if (hte != NULL)
577		hte = hte->h_hte;
578	else
579		hte = htab_search(name, true);
580	hte->h_used = true;
581
582	*hte->h_lusym = usym;
583	hte->h_lusym = &usym->u_next;
584}
585
586static tspec_t
587parse_tspec(const char **pp, char c, bool *osdef)
588{
589	char s;
590
591	switch (c) {
592	case 's':		/* 'signed' or 'struct' or 'float' */
593	case 'u':		/* 'unsigned' or 'union' */
594	case 'l':		/* 'long double' */
595	case 'e':		/* 'enum' */
596		s = c;
597		c = *(*pp)++;
598		break;
599	default:
600		s = '\0';
601		break;
602	}
603
604	switch (c) {
605	case 'B':
606		return BOOL;
607	case 'C':
608		return s == 's' ? SCHAR : (s == 'u' ? UCHAR : CHAR);
609	case 'S':
610		return s == 'u' ? USHORT : SHORT;
611	case 'I':
612		return s == 'u' ? UINT : INT;
613	case 'L':
614		return s == 'u' ? ULONG : LONG;
615	case 'Q':
616		return s == 'u' ? ULLONG : LLONG;
617#ifdef INT128_SIZE
618	case 'J':
619		return s == 'u' ? UINT128 : INT128;
620#endif
621	case 'D':
622		return s == 's' ? FLOAT : (s == 'l' ? LDOUBLE : DOUBLE);
623	case 'V':
624		return VOID;
625	case 'P':
626		return PTR;
627	case 'A':
628		return ARRAY;
629	case 'F':
630	case 'f':
631		*osdef = c == 'f';
632		return FUNC;
633	case 'T':
634		return s == 'e' ? ENUM : (s == 's' ? STRUCT : UNION);
635	case 'X':
636		return s == 's' ? FCOMPLEX
637		    : (s == 'l' ? LCOMPLEX : DCOMPLEX);
638	default:
639		inperr("tspec '%c'", c);
640		/* NOTREACHED */
641	}
642}
643
644/*
645 * Read a type and return the index of this type.
646 */
647static unsigned short
648inptype(const char *cp, const char **epp)
649{
650	char c;
651	const char *ep;
652	type_t *tp;
653	int narg, i;
654	bool osdef = false;
655	size_t tlen;
656	unsigned short tidx;
657	int h;
658
659	/* If we have this type already, return its index. */
660	tlen = gettlen(cp, &ep);
661	h = thash(cp, tlen);
662	if ((tidx = findtype(cp, tlen, h)) != 0) {
663		*epp = ep;
664		return tidx;
665	}
666
667	/* No, we must create a new type. */
668	tp = xalloc(sizeof(*tp));
669
670	tidx = storetyp(tp, cp, tlen, h);
671
672	c = *cp++;
673
674	if (c == 'c') {
675		tp->t_const = true;
676		c = *cp++;
677	}
678	if (c == 'v') {
679		tp->t_volatile = true;
680		c = *cp++;
681	}
682
683	tp->t_tspec = parse_tspec(&cp, c, &osdef);
684
685	switch (tp->t_tspec) {
686	case ARRAY:
687		tp->t_dim = parse_int(&cp);
688		tp->t_subt = TP(inptype(cp, &cp));
689		break;
690	case PTR:
691		tp->t_subt = TP(inptype(cp, &cp));
692		break;
693	case FUNC:
694		c = *cp;
695		if (ch_isdigit(c)) {
696			if (!osdef)
697				tp->t_proto = true;
698			narg = parse_int(&cp);
699			tp->t_args = xcalloc((size_t)narg + 1,
700			    sizeof(*tp->t_args));
701			for (i = 0; i < narg; i++) {
702				if (i == narg - 1 && *cp == 'E') {
703					tp->t_vararg = true;
704					cp++;
705				} else
706					tp->t_args[i] = TP(inptype(cp, &cp));
707			}
708		}
709		tp->t_subt = TP(inptype(cp, &cp));
710		break;
711	case ENUM:
712		tp->t_tspec = INT;
713		tp->t_is_enum = true;
714		/* FALLTHROUGH */
715	case STRUCT:
716	case UNION:
717		switch (*cp++) {
718		case '1':
719			tp->t_istag = true;
720			tp->t_tag = htab_search(inpname(cp, &cp), true);
721			break;
722		case '2':
723			tp->t_istynam = true;
724			tp->t_tynam = htab_search(inpname(cp, &cp), true);
725			break;
726		case '3':
727			tp->t_isuniqpos = true;
728			tp->t_uniqpos.p_line = parse_int(&cp);
729			cp++;
730			/* xlate to 'global' file name. */
731			tp->t_uniqpos.p_file = (short)
732			    addoutfile(inpfns[parse_int(&cp)]);
733			cp++;
734			tp->t_uniqpos.p_uniq = parse_int(&cp);
735			break;
736		}
737		break;
738	default:
739		break;
740	}
741
742	*epp = cp;
743	return tidx;
744}
745
746/*
747 * Get the length of a type string.
748 */
749static size_t
750gettlen(const char *cp, const char **epp)
751{
752	const char *cp1;
753	char c, s;
754	tspec_t t;
755	int narg, i;
756
757	cp1 = cp;
758
759	c = *cp++;
760
761	if (c == 'c')
762		c = *cp++;
763	if (c == 'v')
764		c = *cp++;
765
766	switch (c) {
767	case 's':
768	case 'u':
769	case 'l':
770	case 'e':
771		s = c;
772		c = *cp++;
773		break;
774	default:
775		s = '\0';
776		break;
777	}
778
779	t = NO_TSPEC;
780
781	switch (c) {
782	case 'B':
783		if (s == '\0')
784			t = BOOL;
785		break;
786	case 'C':
787		if (s == 's')
788			t = SCHAR;
789		else if (s == 'u')
790			t = UCHAR;
791		else if (s == '\0')
792			t = CHAR;
793		break;
794	case 'S':
795		if (s == 'u')
796			t = USHORT;
797		else if (s == '\0')
798			t = SHORT;
799		break;
800	case 'I':
801		if (s == 'u')
802			t = UINT;
803		else if (s == '\0')
804			t = INT;
805		break;
806	case 'L':
807		if (s == 'u')
808			t = ULONG;
809		else if (s == '\0')
810			t = LONG;
811		break;
812	case 'Q':
813		if (s == 'u')
814			t = ULLONG;
815		else if (s == '\0')
816			t = LLONG;
817		break;
818#ifdef INT128_SIZE
819	case 'J':
820		if (s == 'u')
821			t = UINT128;
822		else if (s == '\0')
823			t = INT128;
824		break;
825#endif
826	case 'D':
827		if (s == 's')
828			t = FLOAT;
829		else if (s == 'l')
830			t = LDOUBLE;
831		else if (s == '\0')
832			t = DOUBLE;
833		break;
834	case 'V':
835		if (s == '\0')
836			t = VOID;
837		break;
838	case 'P':
839		if (s == '\0')
840			t = PTR;
841		break;
842	case 'A':
843		if (s == '\0')
844			t = ARRAY;
845		break;
846	case 'F':
847	case 'f':
848		if (s == '\0')
849			t = FUNC;
850		break;
851	case 'T':
852		if (s == 'e')
853			t = ENUM;
854		else if (s == 's')
855			t = STRUCT;
856		else if (s == 'u')
857			t = UNION;
858		break;
859	case 'X':
860		if (s == 's')
861			t = FCOMPLEX;
862		else if (s == 'l')
863			t = LCOMPLEX;
864		else if (s == '\0')
865			t = DCOMPLEX;
866		break;
867	default:
868		break;
869	}
870
871	if (t == NO_TSPEC)
872		inperr("bad type: %c %c", c, s);
873
874	switch (t) {
875	case ARRAY:
876		(void)parse_int(&cp);
877		(void)gettlen(cp, &cp);
878		break;
879	case PTR:
880		(void)gettlen(cp, &cp);
881		break;
882	case FUNC:
883		c = *cp;
884		if (ch_isdigit(c)) {
885			narg = parse_int(&cp);
886			for (i = 0; i < narg; i++) {
887				if (i == narg - 1 && *cp == 'E')
888					cp++;
889				else
890					(void)gettlen(cp, &cp);
891			}
892		}
893		(void)gettlen(cp, &cp);
894		break;
895	case ENUM:
896	case STRUCT:
897	case UNION:
898		switch (*cp++) {
899		case '1':
900		case '2':
901			(void)inpname(cp, &cp);
902			break;
903		case '3':
904			/* unique position: line.file.uniquifier */
905			(void)parse_int(&cp);
906			if (*cp++ != '.')
907				inperr("not dot: %c", cp[-1]);
908			(void)parse_int(&cp);
909			if (*cp++ != '.')
910				inperr("not dot: %c", cp[-1]);
911			(void)parse_int(&cp);
912			break;
913		default:
914			inperr("bad value: %c", cp[-1]);
915		}
916		break;
917	default:
918		break;
919	}
920
921	*epp = cp;
922	return (size_t)(cp - cp1);
923}
924
925/*
926 * Search a type by its type string.
927 */
928static unsigned short
929findtype(const char *cp, size_t len, int h)
930{
931	thtab_t *thte;
932
933	for (thte = thtab[h]; thte != NULL; thte = thte->th_next) {
934		if (strncmp(thte->th_name, cp, len) != 0)
935			continue;
936		if (thte->th_name[len] == '\0')
937			return thte->th_idx;
938	}
939
940	return 0;
941}
942
943/*
944 * Store a type and its type string, so we can later share this type
945 * if we read the same type string from the input file.
946 */
947static unsigned short
948storetyp(type_t *tp, const char *cp, size_t len, int h)
949{
950	static unsigned int tidx = 1;	/* 0 is reserved */
951	thtab_t *thte;
952	char *name;
953
954	if (tidx >= USHRT_MAX)
955		errx(1, "sorry, too many types");
956
957	if (tidx == tlstlen - 1) {
958		tlst = xrealloc(tlst, (tlstlen * 2) * sizeof(*tlst));
959		(void)memset(tlst + tlstlen, 0, tlstlen * sizeof(*tlst));
960		tlstlen *= 2;
961	}
962
963	tlst[tidx] = tp;
964
965	/* create a hash table entry */
966	name = xalloc(len + 1);
967	(void)memcpy(name, cp, len);
968	name[len] = '\0';
969
970	thte = xalloc(sizeof(*thte));
971	thte->th_name = name;
972	thte->th_idx = (unsigned short)tidx;
973	thte->th_next = thtab[h];
974	thtab[h] = thte;
975
976	return (unsigned short)tidx++;
977}
978
979/*
980 * Hash function for types
981 */
982static unsigned int
983thash(const char *s, size_t len)
984{
985	unsigned int v;
986
987	v = 0;
988	while (len-- != 0) {
989		v = (v << sizeof(v)) + (unsigned char)*s++;
990		v ^= v >> (sizeof(v) * CHAR_BIT - sizeof(v));
991	}
992	return v % (sizeof(thtab) / sizeof(thtab[0]));
993}
994
995/*
996 * Read a string enclosed by "". This string may contain quoted chars.
997 */
998static char *
999inpqstrg(const char *src, const char **epp)
1000{
1001	char *strg, *dst;
1002	size_t slen;
1003	char c;
1004	int v;
1005
1006	dst = strg = xmalloc(slen = 32);
1007
1008	if ((c = *src++) != '"')
1009		inperr("not quote: %c", c);
1010	if ((c = *src++) == '\0')
1011		inperr("trailing data: %c", c);
1012
1013	while (c != '"') {
1014		if (c == '\\') {
1015			if ((c = *src++) == '\0')
1016				inperr("missing after \\");
1017			switch (c) {
1018			case 'n':
1019				c = '\n';
1020				break;
1021			case 't':
1022				c = '\t';
1023				break;
1024			case 'v':
1025				c = '\v';
1026				break;
1027			case 'b':
1028				c = '\b';
1029				break;
1030			case 'r':
1031				c = '\r';
1032				break;
1033			case 'f':
1034				c = '\f';
1035				break;
1036			case 'a':
1037				c = '\a';
1038				break;
1039			case '\\':
1040				c = '\\';
1041				break;
1042			case '"':
1043				c = '"';
1044				break;
1045			case '\'':
1046				c = '\'';
1047				break;
1048			case '0': case '1': case '2': case '3':
1049				v = (c - '0') << 6;
1050				if ((c = *src++) < '0' || c > '7')
1051					inperr("not octal: %c", c);
1052				v |= (c - '0') << 3;
1053				if ((c = *src++) < '0' || c > '7')
1054					inperr("not octal: %c", c);
1055				v |= c - '0';
1056				c = (char)v;
1057				break;
1058			default:
1059				inperr("bad \\ escape: %c", c);
1060			}
1061		}
1062		/* keep space for trailing '\0' */
1063		if ((size_t)(dst - strg) == slen - 1) {
1064			strg = xrealloc(strg, slen * 2);
1065			dst = strg + (slen - 1);
1066			slen *= 2;
1067		}
1068		*dst++ = c;
1069		if ((c = *src++) == '\0')
1070			inperr("missing closing quote");
1071	}
1072	*dst = '\0';
1073
1074	*epp = src;
1075	return strg;
1076}
1077
1078/*
1079 * Read the name of a symbol in static memory.
1080 */
1081static const char *
1082inpname(const char *cp, const char **epp)
1083{
1084	static char *buf;
1085	static size_t blen = 0;
1086	size_t len, i;
1087	char c;
1088
1089	len = parse_int(&cp);
1090	if (len + 1 > blen)
1091		buf = xrealloc(buf, blen = len + 1);
1092	for (i = 0; i < len; i++) {
1093		c = *cp++;
1094		if (!ch_isalnum(c) && c != '_')
1095			inperr("not alnum or _: %c", c);
1096		buf[i] = c;
1097	}
1098	buf[i] = '\0';
1099
1100	*epp = cp;
1101	return buf;
1102}
1103
1104/*
1105 * Return the index of a file name. If the name cannot be found, create
1106 * a new entry and return the index of the newly created entry.
1107 */
1108static int
1109getfnidx(const char *fn)
1110{
1111	size_t i;
1112
1113	/* 0 is reserved */
1114	for (i = 1; fnames[i] != NULL; i++) {
1115		if (strcmp(fnames[i], fn) == 0)
1116			return (int)i;
1117	}
1118
1119	if (i == nfnames - 1) {
1120		size_t nlen = nfnames * 2;
1121		fnames = xrealloc(fnames, nlen * sizeof(*fnames));
1122		(void)memset(fnames + nfnames, 0, nfnames * sizeof(*fnames));
1123		flines = xrealloc(flines, nlen * sizeof(*flines));
1124		(void)memset(flines + nfnames, 0, nfnames * sizeof(*flines));
1125		nfnames = nlen;
1126	}
1127
1128	fnames[i] = xstrdup(fn);
1129	flines[i] = 0;
1130	return (int)i;
1131}
1132
1133/*
1134 * Separate symbols with static and external linkage.
1135 */
1136void
1137mkstatic(hte_t *hte)
1138{
1139	sym_t *sym1, **symp, *sym;
1140	fcall_t **callp, *call;
1141	usym_t **usymp, *usym;
1142	hte_t *nhte;
1143	bool ofnd;
1144
1145	/* Look for first static definition */
1146	for (sym1 = hte->h_syms; sym1 != NULL; sym1 = sym1->s_next) {
1147		if (sym1->s_static)
1148			break;
1149	}
1150	if (sym1 == NULL)
1151		return;
1152
1153	/* Do nothing if this name is used only in one translation unit. */
1154	ofnd = false;
1155	for (sym = hte->h_syms; sym != NULL && !ofnd; sym = sym->s_next) {
1156		if (sym->s_pos.p_src != sym1->s_pos.p_src)
1157			ofnd = true;
1158	}
1159	for (call = hte->h_calls; call != NULL && !ofnd; call = call->f_next) {
1160		if (call->f_pos.p_src != sym1->s_pos.p_src)
1161			ofnd = true;
1162	}
1163	for (usym = hte->h_usyms; usym != NULL && !ofnd; usym = usym->u_next) {
1164		if (usym->u_pos.p_src != sym1->s_pos.p_src)
1165			ofnd = true;
1166	}
1167	if (!ofnd) {
1168		hte->h_used = true;
1169		/* errors about undef. static symbols are printed in lint1 */
1170		hte->h_def = true;
1171		hte->h_static = true;
1172		return;
1173	}
1174
1175	/*
1176	 * Create a new hash table entry
1177	 *
1178	 * XXX this entry should be put at the beginning of the list to avoid
1179	 * processing the same symbol twice.
1180	 */
1181	for (nhte = hte; nhte->h_link != NULL; nhte = nhte->h_link)
1182		continue;
1183	nhte->h_link = xmalloc(sizeof(*nhte->h_link));
1184	nhte = nhte->h_link;
1185	nhte->h_name = hte->h_name;
1186	nhte->h_used = true;
1187	nhte->h_def = true;	/* error in lint1 */
1188	nhte->h_static = true;
1189	nhte->h_syms = NULL;
1190	nhte->h_lsym = &nhte->h_syms;
1191	nhte->h_calls = NULL;
1192	nhte->h_lcall = &nhte->h_calls;
1193	nhte->h_usyms = NULL;
1194	nhte->h_lusym = &nhte->h_usyms;
1195	nhte->h_link = NULL;
1196	nhte->h_hte = NULL;
1197
1198	/*
1199	 * move all symbols used in this translation unit into the new hash
1200	 * table entry.
1201	 */
1202	for (symp = &hte->h_syms; (sym = *symp) != NULL; ) {
1203		if (sym->s_pos.p_src == sym1->s_pos.p_src) {
1204			sym->s_static = true;
1205			*symp = sym->s_next;
1206			if (hte->h_lsym == &sym->s_next)
1207				hte->h_lsym = symp;
1208			sym->s_next = NULL;
1209			*nhte->h_lsym = sym;
1210			nhte->h_lsym = &sym->s_next;
1211		} else {
1212			symp = &sym->s_next;
1213		}
1214	}
1215	for (callp = &hte->h_calls; (call = *callp) != NULL; ) {
1216		if (call->f_pos.p_src == sym1->s_pos.p_src) {
1217			*callp = call->f_next;
1218			if (hte->h_lcall == &call->f_next)
1219				hte->h_lcall = callp;
1220			call->f_next = NULL;
1221			*nhte->h_lcall = call;
1222			nhte->h_lcall = &call->f_next;
1223		} else {
1224			callp = &call->f_next;
1225		}
1226	}
1227	for (usymp = &hte->h_usyms; (usym = *usymp) != NULL; ) {
1228		if (usym->u_pos.p_src == sym1->s_pos.p_src) {
1229			*usymp = usym->u_next;
1230			if (hte->h_lusym == &usym->u_next)
1231				hte->h_lusym = usymp;
1232			usym->u_next = NULL;
1233			*nhte->h_lusym = usym;
1234			nhte->h_lusym = &usym->u_next;
1235		} else {
1236			usymp = &usym->u_next;
1237		}
1238	}
1239
1240	/* h_def must be recalculated for old hte */
1241	hte->h_def = nhte->h_def = false;
1242	for (sym = hte->h_syms; sym != NULL; sym = sym->s_next) {
1243		if (sym->s_def == DEF || sym->s_def == TDEF) {
1244			hte->h_def = true;
1245			break;
1246		}
1247	}
1248
1249	mkstatic(hte);
1250}
1251