xref: /freebsd/usr.bin/sed/compile.c (revision 8e6b01171e30297084bb0b4457c4183c2746aacc)
1 /*-
2  * Copyright (c) 1992 Diomidis Spinellis.
3  * Copyright (c) 1992, 1993
4  *	The Regents of the University of California.  All rights reserved.
5  *
6  * This code is derived from software contributed to Berkeley by
7  * Diomidis Spinellis of Imperial College, University of London.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  * 1. Redistributions of source code must retain the above copyright
13  *    notice, this list of conditions and the following disclaimer.
14  * 2. Redistributions in binary form must reproduce the above copyright
15  *    notice, this list of conditions and the following disclaimer in the
16  *    documentation and/or other materials provided with the distribution.
17  * 3. All advertising materials mentioning features or use of this software
18  *    must display the following acknowledgement:
19  *	This product includes software developed by the University of
20  *	California, Berkeley and its contributors.
21  * 4. Neither the name of the University nor the names of its contributors
22  *    may be used to endorse or promote products derived from this software
23  *    without specific prior written permission.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35  * SUCH DAMAGE.
36  */
37 
38 #ifndef lint
39 static char sccsid[] = "@(#)compile.c	8.1 (Berkeley) 6/6/93";
40 #endif /* not lint */
41 
42 #include <sys/types.h>
43 #include <sys/stat.h>
44 
45 #include <ctype.h>
46 #include <errno.h>
47 #include <fcntl.h>
48 #include <limits.h>
49 #include <regex.h>
50 #include <stdio.h>
51 #include <stdlib.h>
52 #include <string.h>
53 
54 #include "defs.h"
55 #include "extern.h"
56 
57 #define LHSZ	128
58 #define	LHMASK	(LHSZ - 1)
59 static struct labhash {
60 	struct	labhash *lh_next;
61 	u_int	lh_hash;
62 	struct	s_command *lh_cmd;
63 	int	lh_ref;
64 } *labels[LHSZ];
65 
66 static char	 *compile_addr __P((char *, struct s_addr *));
67 static char	 *compile_ccl __P((char **, char *));
68 static char	 *compile_delimited __P((char *, char *));
69 static char	 *compile_flags __P((char *, struct s_subst *));
70 static char	 *compile_re __P((char *, regex_t **));
71 static char	 *compile_subst __P((char *, struct s_subst *));
72 static char	 *compile_text __P((void));
73 static char	 *compile_tr __P((char *, char **));
74 static struct s_command
75 		**compile_stream __P((struct s_command **));
76 static char	 *duptoeol __P((char *, char *));
77 static void	  enterlabel __P((struct s_command *));
78 static struct s_command
79 		 *findlabel __P((char *));
80 static void	  fixuplabel __P((struct s_command *, struct s_command *));
81 static void	  uselabel __P((void));
82 
83 /*
84  * Command specification.  This is used to drive the command parser.
85  */
86 struct s_format {
87 	char code;				/* Command code */
88 	int naddr;				/* Number of address args */
89 	enum e_args args;			/* Argument type */
90 };
91 
92 static struct s_format cmd_fmts[] = {
93 	{'{', 2, GROUP},
94 	{'}', 0, ENDGROUP},
95 	{'a', 1, TEXT},
96 	{'b', 2, BRANCH},
97 	{'c', 2, TEXT},
98 	{'d', 2, EMPTY},
99 	{'D', 2, EMPTY},
100 	{'g', 2, EMPTY},
101 	{'G', 2, EMPTY},
102 	{'h', 2, EMPTY},
103 	{'H', 2, EMPTY},
104 	{'i', 1, TEXT},
105 	{'l', 2, EMPTY},
106 	{'n', 2, EMPTY},
107 	{'N', 2, EMPTY},
108 	{'p', 2, EMPTY},
109 	{'P', 2, EMPTY},
110 	{'q', 1, EMPTY},
111 	{'r', 1, RFILE},
112 	{'s', 2, SUBST},
113 	{'t', 2, BRANCH},
114 	{'w', 2, WFILE},
115 	{'x', 2, EMPTY},
116 	{'y', 2, TR},
117 	{'!', 2, NONSEL},
118 	{':', 0, LABEL},
119 	{'#', 0, COMMENT},
120 	{'=', 1, EMPTY},
121 	{'\0', 0, COMMENT},
122 };
123 
124 /* The compiled program. */
125 struct s_command *prog;
126 
127 /*
128  * Compile the program into prog.
129  * Initialise appends.
130  */
131 void
132 compile()
133 {
134 	*compile_stream(&prog) = NULL;
135 	fixuplabel(prog, NULL);
136 	uselabel();
137 	appends = xmalloc(sizeof(struct s_appends) * appendnum);
138 	match = xmalloc((maxnsub + 1) * sizeof(regmatch_t));
139 }
140 
141 #define EATSPACE() do {							\
142 	if (p)								\
143 		while (*p && isascii(*p) && isspace(*p))		\
144 			p++;						\
145 	} while (0)
146 
147 static struct s_command **
148 compile_stream(link)
149 	struct s_command **link;
150 {
151 	register char *p;
152 	static char lbuf[_POSIX2_LINE_MAX + 1];	/* To save stack */
153 	struct s_command *cmd, *cmd2, *stack;
154 	struct s_format *fp;
155 	int naddr;				/* Number of addresses */
156 
157 	stack = 0;
158 	for (;;) {
159 		if ((p = cu_fgets(lbuf, sizeof(lbuf))) == NULL) {
160 			if (stack != 0)
161 				err(COMPILE, "unexpected EOF (pending }'s)");
162 			return (link);
163 		}
164 
165 semicolon:	EATSPACE();
166 		if (p && (*p == '#' || *p == '\0'))
167 			continue;
168 		*link = cmd = xmalloc(sizeof(struct s_command));
169 		link = &cmd->next;
170 		cmd->nonsel = cmd->inrange = 0;
171 		/* First parse the addresses */
172 		naddr = 0;
173 
174 /* Valid characters to start an address */
175 #define	addrchar(c)	(strchr("0123456789/\\$", (c)))
176 		if (addrchar(*p)) {
177 			naddr++;
178 			cmd->a1 = xmalloc(sizeof(struct s_addr));
179 			p = compile_addr(p, cmd->a1);
180 			EATSPACE();				/* EXTENSION */
181 			if (*p == ',') {
182 				p++;
183 				EATSPACE();			/* EXTENSION */
184 				naddr++;
185 				cmd->a2 = xmalloc(sizeof(struct s_addr));
186 				p = compile_addr(p, cmd->a2);
187 				EATSPACE();
188 			} else
189 				cmd->a2 = 0;
190 		} else
191 			cmd->a1 = cmd->a2 = 0;
192 
193 nonsel:		/* Now parse the command */
194 		if (!*p)
195 			err(COMPILE, "command expected");
196 		cmd->code = *p;
197 		for (fp = cmd_fmts; fp->code; fp++)
198 			if (fp->code == *p)
199 				break;
200 		if (!fp->code)
201 			err(COMPILE, "invalid command code %c", *p);
202 		if (naddr > fp->naddr)
203 			err(COMPILE,
204 "command %c expects up to %d address(es), found %d", *p, fp->naddr, naddr);
205 		switch (fp->args) {
206 		case NONSEL:			/* ! */
207 			p++;
208 			EATSPACE();
209 			cmd->nonsel = ! cmd->nonsel;
210 			goto nonsel;
211 		case GROUP:			/* { */
212 			p++;
213 			EATSPACE();
214 			cmd->next = stack;
215 			stack = cmd;
216 			link = &cmd->u.c;
217 			if (*p)
218 				goto semicolon;
219 			break;
220 		case ENDGROUP:
221 			/*
222 			 * Short-circuit command processing, since end of
223 			 * group is really just a noop.
224 			 */
225 			cmd->nonsel = 1;
226 			if (stack == 0)
227 				err(COMPILE, "unexpected }");
228 			cmd2 = stack;
229 			stack = cmd2->next;
230 			cmd2->next = cmd;
231 			/*FALLTHROUGH*/
232 		case EMPTY:		/* d D g G h H l n N p P q x = \0 */
233 			p++;
234 			EATSPACE();
235 			if (*p == ';') {
236 				p++;
237 				link = &cmd->next;
238 				goto semicolon;
239 			}
240 			if (*p)
241 				err(COMPILE,
242 "extra characters at the end of %c command", cmd->code);
243 			break;
244 		case TEXT:			/* a c i */
245 			p++;
246 			EATSPACE();
247 			if (*p != '\\')
248 				err(COMPILE,
249 "command %c expects \\ followed by text", cmd->code);
250 			p++;
251 			EATSPACE();
252 			if (*p)
253 				err(COMPILE,
254 "extra characters after \\ at the end of %c command", cmd->code);
255 			cmd->t = compile_text();
256 			break;
257 		case COMMENT:			/* \0 # */
258 			break;
259 		case WFILE:			/* w */
260 			p++;
261 			EATSPACE();
262 			if (*p == '\0')
263 				err(COMPILE, "filename expected");
264 			cmd->t = duptoeol(p, "w command");
265 			if (aflag)
266 				cmd->u.fd = -1;
267 			else if ((cmd->u.fd = open(p,
268 			    O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
269 			    DEFFILEMODE)) == -1)
270 				err(FATAL, "%s: %s\n", p, strerror(errno));
271 			break;
272 		case RFILE:			/* r */
273 			p++;
274 			EATSPACE();
275 			if (*p == '\0')
276 				err(COMPILE, "filename expected");
277 			else
278 				cmd->t = duptoeol(p, "read command");
279 			break;
280 		case BRANCH:			/* b t */
281 			p++;
282 			EATSPACE();
283 			if (*p == '\0')
284 				cmd->t = NULL;
285 			else
286 				cmd->t = duptoeol(p, "branch");
287 			break;
288 		case LABEL:			/* : */
289 			p++;
290 			EATSPACE();
291 			cmd->t = duptoeol(p, "label");
292 			if (strlen(p) == 0)
293 				err(COMPILE, "empty label");
294 			enterlabel(cmd);
295 			break;
296 		case SUBST:			/* s */
297 			p++;
298 			if (*p == '\0' || *p == '\\')
299 				err(COMPILE,
300 "substitute pattern can not be delimited by newline or backslash");
301 			cmd->u.s = xmalloc(sizeof(struct s_subst));
302 			p = compile_re(p, &cmd->u.s->re);
303 			if (p == NULL)
304 				err(COMPILE, "unterminated substitute pattern");
305 			--p;
306 			p = compile_subst(p, cmd->u.s);
307 			p = compile_flags(p, cmd->u.s);
308 			EATSPACE();
309 			if (*p == ';') {
310 				p++;
311 				link = &cmd->next;
312 				goto semicolon;
313 			}
314 			break;
315 		case TR:			/* y */
316 			p++;
317 			p = compile_tr(p, (char **)&cmd->u.y);
318 			EATSPACE();
319 			if (*p == ';') {
320 				p++;
321 				link = &cmd->next;
322 				goto semicolon;
323 			}
324 			if (*p)
325 				err(COMPILE,
326 "extra text at the end of a transform command");
327 			break;
328 		}
329 	}
330 }
331 
332 /*
333  * Get a delimited string.  P points to the delimeter of the string; d points
334  * to a buffer area.  Newline and delimiter escapes are processed; other
335  * escapes are ignored.
336  *
337  * Returns a pointer to the first character after the final delimiter or NULL
338  * in the case of a non-terminated string.  The character array d is filled
339  * with the processed string.
340  */
341 static char *
342 compile_delimited(p, d)
343 	char *p, *d;
344 {
345 	char c;
346 
347 	c = *p++;
348 	if (c == '\0')
349 		return (NULL);
350 	else if (c == '\\')
351 		err(COMPILE, "\\ can not be used as a string delimiter");
352 	else if (c == '\n')
353 		err(COMPILE, "newline can not be used as a string delimiter");
354 	while (*p) {
355 		if (*p == '[') {
356 			if ((d = compile_ccl(&p, d)) == NULL)
357 				err(COMPILE, "unbalanced brackets ([])");
358 			continue;
359 		} else if (*p == '\\' && p[1] == '[') {
360 			*d++ = *p++;
361 		} else if (*p == '\\' && p[1] == c)
362 			p++;
363 		else if (*p == '\\' && p[1] == 'n') {
364 			*d++ = '\n';
365 			p += 2;
366 			continue;
367 		} else if (*p == '\\' && p[1] == '\\')
368 			*d++ = *p++;
369 		else if (*p == c) {
370 			*d = '\0';
371 			return (p + 1);
372 		}
373 		*d++ = *p++;
374 	}
375 	return (NULL);
376 }
377 
378 
379 /* compile_ccl: expand a POSIX character class */
380 static char *
381 compile_ccl(sp, t)
382 	char **sp;
383 	char *t;
384 {
385 	int c, d;
386 	char *s = *sp;
387 
388 	*t++ = *s++;
389 	if (*s == '^')
390 		*t++ = *s++;
391 	if (*s == ']')
392 		*t++ = *s++;
393 	for (; *s && (*t = *s) != ']'; s++, t++)
394 		if (*s == '[' && ((d = *(s+1)) == '.' || d == ':' || d == '=')) {
395 			*++t = *++s, t++, s++;
396 			for (c = *s; (*t = *s) != ']' || c != d; s++, t++)
397 				if ((c = *s) == '\0')
398 					return NULL;
399 		} else if (*s == '\\' && s[1] == 'n')
400 			    *t = '\n', s++;
401 	return (*s == ']') ? *sp = ++s, ++t : NULL;
402 }
403 
404 /*
405  * Get a regular expression.  P points to the delimiter of the regular
406  * expression; repp points to the address of a regexp pointer.  Newline
407  * and delimiter escapes are processed; other escapes are ignored.
408  * Returns a pointer to the first character after the final delimiter
409  * or NULL in the case of a non terminated regular expression.  The regexp
410  * pointer is set to the compiled regular expression.
411  * Cflags are passed to regcomp.
412  */
413 static char *
414 compile_re(p, repp)
415 	char *p;
416 	regex_t **repp;
417 {
418 	int eval;
419 	char re[_POSIX2_LINE_MAX + 1];
420 
421 	p = compile_delimited(p, re);
422 	if (p && strlen(re) == 0) {
423 		*repp = NULL;
424 		return (p);
425 	}
426 	*repp = xmalloc(sizeof(regex_t));
427 	if (p && (eval = regcomp(*repp, re, 0)) != 0)
428 		err(COMPILE, "RE error: %s", strregerror(eval, *repp));
429 	if (maxnsub < (*repp)->re_nsub)
430 		maxnsub = (*repp)->re_nsub;
431 	return (p);
432 }
433 
434 /*
435  * Compile the substitution string of a regular expression and set res to
436  * point to a saved copy of it.  Nsub is the number of parenthesized regular
437  * expressions.
438  */
439 static char *
440 compile_subst(p, s)
441 	char *p;
442 	struct s_subst *s;
443 {
444 	static char lbuf[_POSIX2_LINE_MAX + 1];
445 	int asize, ref, size;
446 	char c, *text, *op, *sp;
447 
448 	c = *p++;			/* Terminator character */
449 	if (c == '\0')
450 		return (NULL);
451 
452 	s->maxbref = 0;
453 	s->linenum = linenum;
454 	asize = 2 * _POSIX2_LINE_MAX + 1;
455 	text = xmalloc(asize);
456 	size = 0;
457 	do {
458 		op = sp = text + size;
459 		for (; *p; p++) {
460 			if (*p == '\\') {
461 				p++;
462 				if (strchr("123456789", *p) != NULL) {
463 					*sp++ = '\\';
464 					ref = *p - '0';
465 					if (s->re != NULL &&
466 					    ref > s->re->re_nsub)
467 						err(COMPILE,
468 "\\%c not defined in the RE", *p);
469 					if (s->maxbref < ref)
470 						s->maxbref = ref;
471 				} else if (*p == '&' || *p == '\\')
472 					*sp++ = '\\';
473 			} else if (*p == c) {
474 				p++;
475 				*sp++ = '\0';
476 				size += sp - op;
477 				s->new = xrealloc(text, size);
478 				return (p);
479 			} else if (*p == '\n') {
480 				err(COMPILE,
481 "unescaped newline inside substitute pattern");
482 				/* NOTREACHED */
483 			}
484 			*sp++ = *p;
485 		}
486 		size += sp - op;
487 		if (asize - size < _POSIX2_LINE_MAX + 1) {
488 			asize *= 2;
489 			text = xmalloc(asize);
490 		}
491 	} while (cu_fgets(p = lbuf, sizeof(lbuf)));
492 	err(COMPILE, "unterminated substitute in regular expression");
493 	/* NOTREACHED */
494 }
495 
496 /*
497  * Compile the flags of the s command
498  */
499 static char *
500 compile_flags(p, s)
501 	char *p;
502 	struct s_subst *s;
503 {
504 	int gn;			/* True if we have seen g or n */
505 	char wfile[_POSIX2_LINE_MAX + 1], *q;
506 
507 	s->n = 1;				/* Default */
508 	s->p = 0;
509 	s->wfile = NULL;
510 	s->wfd = -1;
511 	for (gn = 0;;) {
512 		EATSPACE();			/* EXTENSION */
513 		switch (*p) {
514 		case 'g':
515 			if (gn)
516 				err(COMPILE,
517 "more than one number or 'g' in substitute flags");
518 			gn = 1;
519 			s->n = 0;
520 			break;
521 		case '\0':
522 		case '\n':
523 		case ';':
524 			return (p);
525 		case 'p':
526 			s->p = 1;
527 			break;
528 		case '1': case '2': case '3':
529 		case '4': case '5': case '6':
530 		case '7': case '8': case '9':
531 			if (gn)
532 				err(COMPILE,
533 "more than one number or 'g' in substitute flags");
534 			gn = 1;
535 			/* XXX Check for overflow */
536 			s->n = (int)strtol(p, &p, 10);
537 			break;
538 		case 'w':
539 			p++;
540 #ifdef HISTORIC_PRACTICE
541 			if (*p != ' ') {
542 				err(WARNING, "space missing before w wfile");
543 				return (p);
544 			}
545 #endif
546 			EATSPACE();
547 			q = wfile;
548 			while (*p) {
549 				if (*p == '\n')
550 					break;
551 				*q++ = *p++;
552 			}
553 			*q = '\0';
554 			if (q == wfile)
555 				err(COMPILE, "no wfile specified");
556 			s->wfile = strdup(wfile);
557 			if (!aflag && (s->wfd = open(wfile,
558 			    O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
559 			    DEFFILEMODE)) == -1)
560 				err(FATAL, "%s: %s\n", wfile, strerror(errno));
561 			return (p);
562 		default:
563 			err(COMPILE,
564 			    "bad flag in substitute command: '%c'", *p);
565 			break;
566 		}
567 		p++;
568 	}
569 }
570 
571 /*
572  * Compile a translation set of strings into a lookup table.
573  */
574 static char *
575 compile_tr(p, transtab)
576 	char *p;
577 	char **transtab;
578 {
579 	int i;
580 	char *lt, *op, *np;
581 	char old[_POSIX2_LINE_MAX + 1];
582 	char new[_POSIX2_LINE_MAX + 1];
583 
584 	if (*p == '\0' || *p == '\\')
585 		err(COMPILE,
586 "transform pattern can not be delimited by newline or backslash");
587 	p = compile_delimited(p, old);
588 	if (p == NULL) {
589 		err(COMPILE, "unterminated transform source string");
590 		return (NULL);
591 	}
592 	p = compile_delimited(--p, new);
593 	if (p == NULL) {
594 		err(COMPILE, "unterminated transform target string");
595 		return (NULL);
596 	}
597 	EATSPACE();
598 	if (strlen(new) != strlen(old)) {
599 		err(COMPILE, "transform strings are not the same length");
600 		return (NULL);
601 	}
602 	/* We assume characters are 8 bits */
603 	lt = xmalloc(UCHAR_MAX);
604 	for (i = 0; i <= UCHAR_MAX; i++)
605 		lt[i] = (char)i;
606 	for (op = old, np = new; *op; op++, np++)
607 		lt[(u_char)*op] = *np;
608 	*transtab = lt;
609 	return (p);
610 }
611 
612 /*
613  * Compile the text following an a or i command.
614  */
615 static char *
616 compile_text()
617 {
618 	int asize, size;
619 	char *text, *p, *op, *s;
620 	char lbuf[_POSIX2_LINE_MAX + 1];
621 
622 	asize = 2 * _POSIX2_LINE_MAX + 1;
623 	text = xmalloc(asize);
624 	size = 0;
625 	while (cu_fgets(lbuf, sizeof(lbuf))) {
626 		op = s = text + size;
627 		p = lbuf;
628 		EATSPACE();
629 		for (; *p; p++) {
630 			if (*p == '\\')
631 				p++;
632 			*s++ = *p;
633 		}
634 		size += s - op;
635 		if (p[-2] != '\\') {
636 			*s = '\0';
637 			break;
638 		}
639 		if (asize - size < _POSIX2_LINE_MAX + 1) {
640 			asize *= 2;
641 			text = xmalloc(asize);
642 		}
643 	}
644 	return (xrealloc(text, size + 1));
645 }
646 
647 /*
648  * Get an address and return a pointer to the first character after
649  * it.  Fill the structure pointed to according to the address.
650  */
651 static char *
652 compile_addr(p, a)
653 	char *p;
654 	struct s_addr *a;
655 {
656 	char *end;
657 
658 	switch (*p) {
659 	case '\\':				/* Context address */
660 		++p;
661 		/* FALLTHROUGH */
662 	case '/':				/* Context address */
663 		p = compile_re(p, &a->u.r);
664 		if (p == NULL)
665 			err(COMPILE, "unterminated regular expression");
666 		a->type = AT_RE;
667 		return (p);
668 
669 	case '$':				/* Last line */
670 		a->type = AT_LAST;
671 		return (p + 1);
672 						/* Line number */
673 	case '0': case '1': case '2': case '3': case '4':
674 	case '5': case '6': case '7': case '8': case '9':
675 		a->type = AT_LINE;
676 		a->u.l = strtol(p, &end, 10);
677 		return (end);
678 	default:
679 		err(COMPILE, "expected context address");
680 		return (NULL);
681 	}
682 }
683 
684 /*
685  * duptoeol --
686  *	Return a copy of all the characters up to \n or \0.
687  */
688 static char *
689 duptoeol(s, ctype)
690 	register char *s;
691 	char *ctype;
692 {
693 	size_t len;
694 	int ws;
695 	char *start;
696 
697 	ws = 0;
698 	for (start = s; *s != '\0' && *s != '\n'; ++s)
699 		ws = isspace(*s);
700 	*s = '\0';
701 	if (ws)
702 		err(WARNING, "whitespace after %s", ctype);
703 	len = s - start + 1;
704 	return (memmove(xmalloc(len), start, len));
705 }
706 
707 /*
708  * Convert goto label names to addresses, and count a and r commands, in
709  * the given subset of the script.  Free the memory used by labels in b
710  * and t commands (but not by :).
711  *
712  * TODO: Remove } nodes
713  */
714 static void
715 fixuplabel(cp, end)
716 	struct s_command *cp, *end;
717 {
718 
719 	for (; cp != end; cp = cp->next)
720 		switch (cp->code) {
721 		case 'a':
722 		case 'r':
723 			appendnum++;
724 			break;
725 		case 'b':
726 		case 't':
727 			/* Resolve branch target. */
728 			if (cp->t == NULL) {
729 				cp->u.c = NULL;
730 				break;
731 			}
732 			if ((cp->u.c = findlabel(cp->t)) == NULL)
733 				err(COMPILE2, "undefined label '%s'", cp->t);
734 			free(cp->t);
735 			break;
736 		case '{':
737 			/* Do interior commands. */
738 			fixuplabel(cp->u.c, cp->next);
739 			break;
740 		}
741 }
742 
743 /*
744  * Associate the given command label for later lookup.
745  */
746 static void
747 enterlabel(cp)
748 	struct s_command *cp;
749 {
750 	register struct labhash **lhp, *lh;
751 	register u_char *p;
752 	register u_int h, c;
753 
754 	for (h = 0, p = (u_char *)cp->t; (c = *p) != 0; p++)
755 		h = (h << 5) + h + c;
756 	lhp = &labels[h & LHMASK];
757 	for (lh = *lhp; lh != NULL; lh = lh->lh_next)
758 		if (lh->lh_hash == h && strcmp(cp->t, lh->lh_cmd->t) == 0)
759 			err(COMPILE2, "duplicate label '%s'", cp->t);
760 	lh = xmalloc(sizeof *lh);
761 	lh->lh_next = *lhp;
762 	lh->lh_hash = h;
763 	lh->lh_cmd = cp;
764 	lh->lh_ref = 0;
765 	*lhp = lh;
766 }
767 
768 /*
769  * Find the label contained in the command l in the command linked
770  * list cp.  L is excluded from the search.  Return NULL if not found.
771  */
772 static struct s_command *
773 findlabel(name)
774 	char *name;
775 {
776 	register struct labhash *lh;
777 	register u_char *p;
778 	register u_int h, c;
779 
780 	for (h = 0, p = (u_char *)name; (c = *p) != 0; p++)
781 		h = (h << 5) + h + c;
782 	for (lh = labels[h & LHMASK]; lh != NULL; lh = lh->lh_next) {
783 		if (lh->lh_hash == h && strcmp(name, lh->lh_cmd->t) == 0) {
784 			lh->lh_ref = 1;
785 			return (lh->lh_cmd);
786 		}
787 	}
788 	return (NULL);
789 }
790 
791 /*
792  * Warn about any unused labels.  As a side effect, release the label hash
793  * table space.
794  */
795 static void
796 uselabel()
797 {
798 	register struct labhash *lh, *next;
799 	register int i;
800 
801 	for (i = 0; i < LHSZ; i++) {
802 		for (lh = labels[i]; lh != NULL; lh = next) {
803 			next = lh->lh_next;
804 			if (!lh->lh_ref)
805 				err(WARNING, "unused label '%s'",
806 				    lh->lh_cmd->t);
807 			free(lh);
808 		}
809 	}
810 }
811