Home | History | Annotate | Line # | Download | only in sed
compile.c revision 1.9
      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_delimited __P((char *, char *));
     68 static char	 *compile_flags __P((char *, struct s_subst *));
     69 static char	 *compile_re __P((char *, regex_t **));
     70 static char	 *compile_subst __P((char *, struct s_subst *));
     71 static char	 *compile_text __P((void));
     72 static char	 *compile_tr __P((char *, char **));
     73 static struct s_command
     74 		**compile_stream __P((char *, struct s_command **, char *));
     75 static char	 *duptoeol __P((char *, char *));
     76 static void	  enterlabel __P((struct s_command *));
     77 static struct s_command
     78 		 *findlabel __P((char *));
     79 static void	  fixuplabel __P((struct s_command *, struct s_command *));
     80 static void	  uselabel __P((void));
     81 
     82 /*
     83  * Command specification.  This is used to drive the command parser.
     84  */
     85 struct s_format {
     86 	char code;				/* Command code */
     87 	int naddr;				/* Number of address args */
     88 	enum e_args args;			/* Argument type */
     89 };
     90 
     91 static struct s_format cmd_fmts[] = {
     92 	{'{', 2, GROUP},
     93 	{'a', 1, TEXT},
     94 	{'b', 2, BRANCH},
     95 	{'c', 2, TEXT},
     96 	{'d', 2, EMPTY},
     97 	{'D', 2, EMPTY},
     98 	{'g', 2, EMPTY},
     99 	{'G', 2, EMPTY},
    100 	{'h', 2, EMPTY},
    101 	{'H', 2, EMPTY},
    102 	{'i', 1, TEXT},
    103 	{'l', 2, EMPTY},
    104 	{'n', 2, EMPTY},
    105 	{'N', 2, EMPTY},
    106 	{'p', 2, EMPTY},
    107 	{'P', 2, EMPTY},
    108 	{'q', 1, EMPTY},
    109 	{'r', 1, RFILE},
    110 	{'s', 2, SUBST},
    111 	{'t', 2, BRANCH},
    112 	{'w', 2, WFILE},
    113 	{'x', 2, EMPTY},
    114 	{'y', 2, TR},
    115 	{'!', 2, NONSEL},
    116 	{':', 0, LABEL},
    117 	{'#', 0, COMMENT},
    118 	{'=', 1, EMPTY},
    119 	{'\0', 0, COMMENT},
    120 };
    121 
    122 /* The compiled program. */
    123 struct s_command *prog;
    124 
    125 /*
    126  * Compile the program into prog.
    127  * Initialise appends.
    128  */
    129 void
    130 compile()
    131 {
    132 	*compile_stream(NULL, &prog, NULL) = NULL;
    133 	fixuplabel(prog, NULL);
    134 	uselabel();
    135 	appends = xmalloc(sizeof(struct s_appends) * appendnum);
    136 	match = xmalloc((maxnsub + 1) * sizeof(regmatch_t));
    137 }
    138 
    139 #define EATSPACE() do {							\
    140 	if (p)								\
    141 		while (*p && isascii(*p) && isspace(*p))		\
    142 			p++;						\
    143 	} while (0)
    144 
    145 static struct s_command **
    146 compile_stream(terminator, link, p)
    147 	char *terminator;
    148 	struct s_command **link;
    149 	register char *p;
    150 {
    151 	static char lbuf[_POSIX2_LINE_MAX + 1];	/* To save stack */
    152 	struct s_command *cmd, *cmd2;
    153 	struct s_format *fp;
    154 	int naddr;				/* Number of addresses */
    155 
    156 	if (p != NULL)
    157 		goto semicolon;
    158 	for (;;) {
    159 		if ((p = cu_fgets(lbuf, sizeof(lbuf))) == NULL) {
    160 			if (terminator != NULL)
    161 				err(COMPILE, "unexpected EOF (pending }'s)");
    162 			return (link);
    163 		}
    164 
    165 semicolon:	EATSPACE();
    166 		if (p && (*p == '#' || *p == '\0'))
    167 			continue;
    168 		if (*p == '}') {
    169 			if (terminator == NULL)
    170 				err(COMPILE, "unexpected }");
    171 			return (link);
    172 		}
    173 		*link = cmd = xmalloc(sizeof(struct s_command));
    174 		link = &cmd->next;
    175 		cmd->nonsel = cmd->inrange = 0;
    176 		/* First parse the addresses */
    177 		naddr = 0;
    178 		cmd->a1 = cmd->a2 = NULL;
    179 
    180 /* Valid characters to start an address */
    181 #define	addrchar(c)	(strchr("0123456789/\\$", (c)))
    182 		if (addrchar(*p)) {
    183 			naddr++;
    184 			cmd->a1 = xmalloc(sizeof(struct s_addr));
    185 			p = compile_addr(p, cmd->a1);
    186 			EATSPACE();				/* EXTENSION */
    187 			if (*p == ',') {
    188 				naddr++;
    189 				p++;
    190 				EATSPACE();			/* EXTENSION */
    191 				cmd->a2 = xmalloc(sizeof(struct s_addr));
    192 				p = compile_addr(p, cmd->a2);
    193 			}
    194 		}
    195 
    196 nonsel:		/* Now parse the command */
    197 		EATSPACE();
    198 		if (!*p)
    199 			err(COMPILE, "command expected");
    200 		cmd->code = *p;
    201 		for (fp = cmd_fmts; fp->code; fp++)
    202 			if (fp->code == *p)
    203 				break;
    204 		if (!fp->code)
    205 			err(COMPILE, "invalid command code %c", *p);
    206 		if (naddr > fp->naddr)
    207 			err(COMPILE,
    208 "command %c expects up to %d address(es), found %d", *p, fp->naddr, naddr);
    209 		switch (fp->args) {
    210 		case NONSEL:			/* ! */
    211 			cmd->nonsel = ! cmd->nonsel;
    212 			p++;
    213 			goto nonsel;
    214 		case GROUP:			/* { */
    215 			p++;
    216 			EATSPACE();
    217 			if (!*p)
    218 				p = NULL;
    219 			cmd2 = xmalloc(sizeof(struct s_command));
    220 			cmd2->code = '}';
    221 			*compile_stream("}", &cmd->u.c, p) = cmd2;
    222 			cmd->next = cmd2;
    223 			link = &cmd2->next;
    224 			break;
    225 		case EMPTY:		/* d D g G h H l n N p P q x = \0 */
    226 			p++;
    227 			EATSPACE();
    228 			if (*p == ';') {
    229 				p++;
    230 				link = &cmd->next;
    231 				goto semicolon;
    232 			}
    233 			if (*p)
    234 				err(COMPILE,
    235 "extra characters at the end of %c command", cmd->code);
    236 			break;
    237 		case TEXT:			/* a c i */
    238 			p++;
    239 			EATSPACE();
    240 			if (*p != '\\')
    241 				err(COMPILE,
    242 "command %c expects \\ followed by text", cmd->code);
    243 			p++;
    244 			EATSPACE();
    245 			if (*p)
    246 				err(COMPILE,
    247 "extra characters after \\ at the end of %c command", cmd->code);
    248 			cmd->t = compile_text();
    249 			break;
    250 		case COMMENT:			/* \0 # */
    251 			break;
    252 		case WFILE:			/* w */
    253 			p++;
    254 			EATSPACE();
    255 			if (*p == '\0')
    256 				err(COMPILE, "filename expected");
    257 			cmd->t = duptoeol(p, "w command");
    258 			if (aflag)
    259 				cmd->u.fd = -1;
    260 			else if ((cmd->u.fd = open(p,
    261 			    O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
    262 			    DEFFILEMODE)) == -1)
    263 				err(FATAL, "%s: %s\n", p, strerror(errno));
    264 			break;
    265 		case RFILE:			/* r */
    266 			p++;
    267 			EATSPACE();
    268 			if (*p == '\0')
    269 				err(COMPILE, "filename expected");
    270 			else
    271 				cmd->t = duptoeol(p, "read command");
    272 			break;
    273 		case BRANCH:			/* b t */
    274 			p++;
    275 			EATSPACE();
    276 			if (*p == '\0')
    277 				cmd->t = NULL;
    278 			else
    279 				cmd->t = duptoeol(p, "branch");
    280 			break;
    281 		case LABEL:			/* : */
    282 			p++;
    283 			EATSPACE();
    284 			cmd->t = duptoeol(p, "label");
    285 			if (strlen(p) == 0)
    286 				err(COMPILE, "empty label");
    287 			enterlabel(cmd);
    288 			break;
    289 		case SUBST:			/* s */
    290 			p++;
    291 			if (*p == '\0' || *p == '\\')
    292 				err(COMPILE,
    293 "substitute pattern can not be delimited by newline or backslash");
    294 			cmd->u.s = xmalloc(sizeof(struct s_subst));
    295 			p = compile_re(p, &cmd->u.s->re);
    296 			if (p == NULL)
    297 				err(COMPILE, "unterminated substitute pattern");
    298 			--p;
    299 			p = compile_subst(p, cmd->u.s);
    300 			p = compile_flags(p, cmd->u.s);
    301 			EATSPACE();
    302 			if (*p == ';') {
    303 				p++;
    304 				link = &cmd->next;
    305 				goto semicolon;
    306 			}
    307 			break;
    308 		case TR:			/* y */
    309 			p++;
    310 			p = compile_tr(p, (char **)&cmd->u.y);
    311 			EATSPACE();
    312 			if (*p == ';') {
    313 				p++;
    314 				link = &cmd->next;
    315 				goto semicolon;
    316 			}
    317 			if (*p)
    318 				err(COMPILE,
    319 "extra text at the end of a transform command");
    320 			break;
    321 		}
    322 	}
    323 }
    324 
    325 /*
    326  * Get a delimited string.  P points to the delimeter of the string; d points
    327  * to a buffer area.  Newline and delimiter escapes are processed; other
    328  * escapes are ignored.
    329  *
    330  * Returns a pointer to the first character after the final delimiter or NULL
    331  * in the case of a non-terminated string.  The character array d is filled
    332  * with the processed string.
    333  */
    334 static char *
    335 compile_delimited(p, d)
    336 	char *p, *d;
    337 {
    338 	char c;
    339 
    340 	c = *p++;
    341 	if (c == '\0')
    342 		return (NULL);
    343 	else if (c == '\\')
    344 		err(COMPILE, "\\ can not be used as a string delimiter");
    345 	else if (c == '\n')
    346 		err(COMPILE, "newline can not be used as a string delimiter");
    347 	while (*p) {
    348 		if (*p == '\\' && p[1] == c)
    349 			p++;
    350 		else if (*p == '\\' && p[1] == 'n') {
    351 			*d++ = '\n';
    352 			p += 2;
    353 			continue;
    354 		} else if (*p == '\\' && p[1] == '\\')
    355 			*d++ = *p++;
    356 		else if (*p == c) {
    357 			*d = '\0';
    358 			return (p + 1);
    359 		}
    360 		*d++ = *p++;
    361 	}
    362 	return (NULL);
    363 }
    364 
    365 /*
    366  * Get a regular expression.  P points to the delimiter of the regular
    367  * expression; repp points to the address of a regexp pointer.  Newline
    368  * and delimiter escapes are processed; other escapes are ignored.
    369  * Returns a pointer to the first character after the final delimiter
    370  * or NULL in the case of a non terminated regular expression.  The regexp
    371  * pointer is set to the compiled regular expression.
    372  * Cflags are passed to regcomp.
    373  */
    374 static char *
    375 compile_re(p, repp)
    376 	char *p;
    377 	regex_t **repp;
    378 {
    379 	int eval;
    380 	char re[_POSIX2_LINE_MAX + 1];
    381 
    382 	p = compile_delimited(p, re);
    383 	if (p && strlen(re) == 0) {
    384 		*repp = NULL;
    385 		return (p);
    386 	}
    387 	*repp = xmalloc(sizeof(regex_t));
    388 	if (p && (eval = regcomp(*repp, re, 0)) != 0)
    389 		err(COMPILE, "RE error: %s", strregerror(eval, *repp));
    390 	if (maxnsub < (*repp)->re_nsub)
    391 		maxnsub = (*repp)->re_nsub;
    392 	return (p);
    393 }
    394 
    395 /*
    396  * Compile the substitution string of a regular expression and set res to
    397  * point to a saved copy of it.  Nsub is the number of parenthesized regular
    398  * expressions.
    399  */
    400 static char *
    401 compile_subst(p, s)
    402 	char *p;
    403 	struct s_subst *s;
    404 {
    405 	static char lbuf[_POSIX2_LINE_MAX + 1];
    406 	int asize, ref, size;
    407 	char c, *text, *op, *sp;
    408 
    409 	c = *p++;			/* Terminator character */
    410 	if (c == '\0')
    411 		return (NULL);
    412 
    413 	s->maxbref = 0;
    414 	s->linenum = linenum;
    415 	asize = 2 * _POSIX2_LINE_MAX + 1;
    416 	text = xmalloc(asize);
    417 	size = 0;
    418 	do {
    419 		op = sp = text + size;
    420 		for (; *p; p++) {
    421 			if (*p == '\\') {
    422 				p++;
    423 				if (strchr("123456789", *p) != NULL) {
    424 					*sp++ = '\\';
    425 					ref = *p - '0';
    426 					if (s->re != NULL &&
    427 					    ref > s->re->re_nsub)
    428 						err(COMPILE,
    429 "\\%c not defined in the RE", *p);
    430 					if (s->maxbref < ref)
    431 						s->maxbref = ref;
    432 				} else if (*p == '&' || *p == '\\')
    433 					*sp++ = '\\';
    434 			} else if (*p == c) {
    435 				p++;
    436 				*sp++ = '\0';
    437 				size += sp - op;
    438 				s->new = xrealloc(text, size);
    439 				return (p);
    440 			} else if (*p == '\n') {
    441 				err(COMPILE,
    442 "unescaped newline inside substitute pattern");
    443 				/* NOTREACHED */
    444 			}
    445 			*sp++ = *p;
    446 		}
    447 		size += sp - op;
    448 		if (asize - size < _POSIX2_LINE_MAX + 1) {
    449 			asize *= 2;
    450 			text = xmalloc(asize);
    451 		}
    452 	} while (cu_fgets(p = lbuf, sizeof(lbuf)));
    453 	err(COMPILE, "unterminated substitute in regular expression");
    454 	/* NOTREACHED */
    455 }
    456 
    457 /*
    458  * Compile the flags of the s command
    459  */
    460 static char *
    461 compile_flags(p, s)
    462 	char *p;
    463 	struct s_subst *s;
    464 {
    465 	int gn;			/* True if we have seen g or n */
    466 	char wfile[_POSIX2_LINE_MAX + 1], *q;
    467 
    468 	s->n = 1;				/* Default */
    469 	s->p = 0;
    470 	s->wfile = NULL;
    471 	s->wfd = -1;
    472 	for (gn = 0;;) {
    473 		EATSPACE();			/* EXTENSION */
    474 		switch (*p) {
    475 		case 'g':
    476 			if (gn)
    477 				err(COMPILE,
    478 "more than one number or 'g' in substitute flags");
    479 			gn = 1;
    480 			s->n = 0;
    481 			break;
    482 		case '\0':
    483 		case '\n':
    484 		case ';':
    485 			return (p);
    486 		case 'p':
    487 			s->p = 1;
    488 			break;
    489 		case '1': case '2': case '3':
    490 		case '4': case '5': case '6':
    491 		case '7': case '8': case '9':
    492 			if (gn)
    493 				err(COMPILE,
    494 "more than one number or 'g' in substitute flags");
    495 			gn = 1;
    496 			/* XXX Check for overflow */
    497 			s->n = (int)strtol(p, &p, 10);
    498 			break;
    499 		case 'w':
    500 			p++;
    501 #ifdef HISTORIC_PRACTICE
    502 			if (*p != ' ') {
    503 				err(WARNING, "space missing before w wfile");
    504 				return (p);
    505 			}
    506 #endif
    507 			EATSPACE();
    508 			q = wfile;
    509 			while (*p) {
    510 				if (*p == '\n')
    511 					break;
    512 				*q++ = *p++;
    513 			}
    514 			*q = '\0';
    515 			if (q == wfile)
    516 				err(COMPILE, "no wfile specified");
    517 			s->wfile = strdup(wfile);
    518 			if (!aflag && (s->wfd = open(wfile,
    519 			    O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
    520 			    DEFFILEMODE)) == -1)
    521 				err(FATAL, "%s: %s\n", wfile, strerror(errno));
    522 			return (p);
    523 		default:
    524 			err(COMPILE,
    525 			    "bad flag in substitute command: '%c'", *p);
    526 			break;
    527 		}
    528 		p++;
    529 	}
    530 }
    531 
    532 /*
    533  * Compile a translation set of strings into a lookup table.
    534  */
    535 static char *
    536 compile_tr(p, transtab)
    537 	char *p;
    538 	char **transtab;
    539 {
    540 	int i;
    541 	char *lt, *op, *np;
    542 	char old[_POSIX2_LINE_MAX + 1];
    543 	char new[_POSIX2_LINE_MAX + 1];
    544 
    545 	if (*p == '\0' || *p == '\\')
    546 		err(COMPILE,
    547 "transform pattern can not be delimited by newline or backslash");
    548 	p = compile_delimited(p, old);
    549 	if (p == NULL) {
    550 		err(COMPILE, "unterminated transform source string");
    551 		return (NULL);
    552 	}
    553 	p = compile_delimited(--p, new);
    554 	if (p == NULL) {
    555 		err(COMPILE, "unterminated transform target string");
    556 		return (NULL);
    557 	}
    558 	EATSPACE();
    559 	if (strlen(new) != strlen(old)) {
    560 		err(COMPILE, "transform strings are not the same length");
    561 		return (NULL);
    562 	}
    563 	/* We assume characters are 8 bits */
    564 	lt = xmalloc(UCHAR_MAX);
    565 	for (i = 0; i <= UCHAR_MAX; i++)
    566 		lt[i] = (char)i;
    567 	for (op = old, np = new; *op; op++, np++)
    568 		lt[(u_char)*op] = *np;
    569 	*transtab = lt;
    570 	return (p);
    571 }
    572 
    573 /*
    574  * Compile the text following an a or i command.
    575  */
    576 static char *
    577 compile_text()
    578 {
    579 	int asize, size;
    580 	char *text, *p, *op, *s;
    581 	char lbuf[_POSIX2_LINE_MAX + 1];
    582 
    583 	asize = 2 * _POSIX2_LINE_MAX + 1;
    584 	text = xmalloc(asize);
    585 	size = 0;
    586 	while (cu_fgets(lbuf, sizeof(lbuf))) {
    587 		op = s = text + size;
    588 		p = lbuf;
    589 		EATSPACE();
    590 		for (; *p; p++) {
    591 			if (*p == '\\')
    592 				p++;
    593 			*s++ = *p;
    594 		}
    595 		size += s - op;
    596 		if (p[-2] != '\\') {
    597 			*s = '\0';
    598 			break;
    599 		}
    600 		if (asize - size < _POSIX2_LINE_MAX + 1) {
    601 			asize *= 2;
    602 			text = xmalloc(asize);
    603 		}
    604 	}
    605 	return (xrealloc(text, size + 1));
    606 }
    607 
    608 /*
    609  * Get an address and return a pointer to the first character after
    610  * it.  Fill the structure pointed to according to the address.
    611  */
    612 static char *
    613 compile_addr(p, a)
    614 	char *p;
    615 	struct s_addr *a;
    616 {
    617 	char *end;
    618 
    619 	switch (*p) {
    620 	case '\\':				/* Context address */
    621 		++p;
    622 		/* FALLTHROUGH */
    623 	case '/':				/* Context address */
    624 		p = compile_re(p, &a->u.r);
    625 		if (p == NULL)
    626 			err(COMPILE, "unterminated regular expression");
    627 		a->type = AT_RE;
    628 		return (p);
    629 
    630 	case '$':				/* Last line */
    631 		a->type = AT_LAST;
    632 		return (p + 1);
    633 						/* Line number */
    634 	case '0': case '1': case '2': case '3': case '4':
    635 	case '5': case '6': case '7': case '8': case '9':
    636 		a->type = AT_LINE;
    637 		a->u.l = strtol(p, &end, 10);
    638 		return (end);
    639 	default:
    640 		err(COMPILE, "expected context address");
    641 		return (NULL);
    642 	}
    643 }
    644 
    645 /*
    646  * duptoeol --
    647  *	Return a copy of all the characters up to \n or \0.
    648  */
    649 static char *
    650 duptoeol(s, ctype)
    651 	register char *s;
    652 	char *ctype;
    653 {
    654 	size_t len;
    655 	int ws;
    656 	char *start;
    657 
    658 	ws = 0;
    659 	for (start = s; *s != '\0' && *s != '\n'; ++s)
    660 		ws = isspace(*s);
    661 	*s = '\0';
    662 	if (ws)
    663 		err(WARNING, "whitespace after %s", ctype);
    664 	len = s - start + 1;
    665 	return (memmove(xmalloc(len), start, len));
    666 }
    667 
    668 /*
    669  * Convert goto label names to addresses, and count a and r commands, in
    670  * the given subset of the script.  Free the memory used by labels in b
    671  * and t commands (but not by :).
    672  *
    673  * TODO: Remove } nodes
    674  */
    675 static void
    676 fixuplabel(cp, end)
    677 	struct s_command *cp, *end;
    678 {
    679 
    680 	for (; cp != end; cp = cp->next)
    681 		switch (cp->code) {
    682 		case 'a':
    683 		case 'r':
    684 			appendnum++;
    685 			break;
    686 		case 'b':
    687 		case 't':
    688 			/* Resolve branch target. */
    689 			if (cp->t == NULL) {
    690 				cp->u.c = NULL;
    691 				break;
    692 			}
    693 			if ((cp->u.c = findlabel(cp->t)) == NULL)
    694 				err(COMPILE2, "undefined label '%s'", cp->t);
    695 			free(cp->t);
    696 			break;
    697 		case '{':
    698 			/* Do interior commands. */
    699 			fixuplabel(cp->u.c, cp->next);
    700 			break;
    701 		}
    702 }
    703 
    704 /*
    705  * Associate the given command label for later lookup.
    706  */
    707 static void
    708 enterlabel(cp)
    709 	struct s_command *cp;
    710 {
    711 	register struct labhash **lhp, *lh;
    712 	register u_char *p;
    713 	register u_int h, c;
    714 
    715 	for (h = 0, p = (u_char *)cp->t; (c = *p) != 0; p++)
    716 		h = (h << 5) + h + c;
    717 	lhp = &labels[h & LHMASK];
    718 	for (lh = *lhp; lh != NULL; lh = lh->lh_next)
    719 		if (lh->lh_hash == h && strcmp(cp->t, lh->lh_cmd->t) == 0)
    720 			err(COMPILE2, "duplicate label '%s'", cp->t);
    721 	lh = xmalloc(sizeof *lh);
    722 	lh->lh_next = *lhp;
    723 	lh->lh_hash = h;
    724 	lh->lh_cmd = cp;
    725 	lh->lh_ref = 0;
    726 	*lhp = lh;
    727 }
    728 
    729 /*
    730  * Find the label contained in the command l in the command linked
    731  * list cp.  L is excluded from the search.  Return NULL if not found.
    732  */
    733 static struct s_command *
    734 findlabel(name)
    735 	char *name;
    736 {
    737 	register struct labhash *lh;
    738 	register u_char *p;
    739 	register u_int h, c;
    740 
    741 	for (h = 0, p = (u_char *)name; (c = *p) != 0; p++)
    742 		h = (h << 5) + h + c;
    743 	for (lh = labels[h & LHMASK]; lh != NULL; lh = lh->lh_next) {
    744 		if (lh->lh_hash == h && strcmp(name, lh->lh_cmd->t) == 0) {
    745 			lh->lh_ref = 1;
    746 			return (lh->lh_cmd);
    747 		}
    748 	}
    749 	return (NULL);
    750 }
    751 
    752 /*
    753  * Warn about any unused labels.  As a side effect, release the label hash
    754  * table space.
    755  */
    756 static void
    757 uselabel()
    758 {
    759 	register struct labhash *lh, *next;
    760 	register int i;
    761 
    762 	for (i = 0; i < LHSZ; i++) {
    763 		for (lh = labels[i]; lh != NULL; lh = next) {
    764 			next = lh->lh_next;
    765 			if (!lh->lh_ref)
    766 				err(WARNING, "unused label '%s'",
    767 				    lh->lh_cmd->t);
    768 			free(lh);
    769 		}
    770 	}
    771 }
    772