[unix-history] / usr.bin / sed / compile.c

/*-
 * Copyright (c) 1992 Diomidis Spinellis.
 * Copyright (c) 1992 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Diomidis Spinellis of Imperial College, University of London.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#ifndef lint
static char sccsid[] = "@(#)compile.c	5.6 (Berkeley) 11/2/92";
#endif /* not lint */

#include <sys/types.h>
#include <sys/stat.h>

#include <ctype.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <regex.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "defs.h"
#include "extern.h"

static char	 *compile_addr __P((char *, struct s_addr *));
static char	 *compile_ccl __P((char **, char *));
static char	 *compile_delimited __P((char *, char *));
static char	 *compile_flags __P((char *, struct s_subst *));
static char	 *compile_re __P((char *, regex_t **));
static char	 *compile_subst __P((char *, struct s_subst *));
static char	 *compile_text __P((void));
static char	 *compile_tr __P((char *, char **));
static struct s_command
		**compile_stream __P((char *, struct s_command **, char *));
static char	 *duptoeol __P((char *));
static struct s_command
		 *findlabel __P((struct s_command *, struct s_command *));
static void	  fixuplabel __P((struct s_command *, struct s_command *,
		  	struct s_command *));

/*
 * Command specification.  This is used to drive the command parser.
 */
struct s_format {
	char code;				/* Command code */
	int naddr;				/* Number of address args */
	enum e_args args;			/* Argument type */
};

static struct s_format cmd_fmts[] = {
	{'{', 2, GROUP},
	{'a', 1, TEXT},
	{'b', 2, BRANCH},
	{'c', 2, TEXT},
	{'d', 2, EMPTY},
	{'D', 2, EMPTY},
	{'g', 2, EMPTY},
	{'G', 2, EMPTY},
	{'h', 2, EMPTY},
	{'H', 2, EMPTY},
	{'i', 1, TEXT},
	{'l', 2, EMPTY},
	{'n', 2, EMPTY},
	{'N', 2, EMPTY},
	{'p', 2, EMPTY},
	{'P', 2, EMPTY},
	{'q', 1, EMPTY},
	{'r', 1, RFILE},
	{'s', 2, SUBST},
	{'t', 2, BRANCH},
	{'w', 2, WFILE},
	{'x', 2, EMPTY},
	{'y', 2, TR},
	{'!', 2, NONSEL},
	{':', 0, LABEL},
	{'#', 0, COMMENT},
	{'=', 1, EMPTY},
	{'\0', 0, COMMENT},
};

/* The compiled program. */
struct s_command *prog;

/*
 * Compile the program into prog.
 * Initialise appends.
 */
void
compile()
{
	*compile_stream(NULL, &prog, NULL) = NULL;
	fixuplabel(prog, prog, NULL);
	appends = xmalloc(sizeof(struct s_appends) * appendnum);
	match = xmalloc((maxnsub + 1) * sizeof(regmatch_t));
}

#define EATSPACE() do {							\
	if (p)								\
		while (*p && isascii(*p) && isspace(*p))		\
			p++;						\
	} while (0)

static struct s_command **
compile_stream(terminator, link, p)
	char *terminator;
	struct s_command **link;
	register char *p;
{
	static char lbuf[_POSIX2_LINE_MAX + 1];	/* To save stack */
	struct s_command *cmd, *cmd2;
	struct s_format *fp;
	int naddr;				/* Number of addresses */

	if (p != NULL)
		goto semicolon;
	for (;;) {
		if ((p = cu_fgets(lbuf, sizeof(lbuf))) == NULL) {
			if (terminator != NULL)
				err(COMPILE, "unexpected EOF (pending }'s)");
			return (link);
		}

semicolon:	EATSPACE();
		if (p && (*p == '#' || *p == '\0'))
			continue;
		if (*p == '}') {
			if (terminator == NULL)
				err(COMPILE, "unexpected }");
			return (link);
		}
		*link = cmd = xmalloc(sizeof(struct s_command));
		link = &cmd->next;
		cmd->nonsel = cmd->inrange = 0;
		/* First parse the addresses */
		naddr = 0;
		cmd->a1 = cmd->a2 = NULL;

/* Valid characters to start an address */
#define	addrchar(c)	(strchr("0123456789/\\$", (c)))
		if (addrchar(*p)) {
			naddr++;
			cmd->a1 = xmalloc(sizeof(struct s_addr));
			p = compile_addr(p, cmd->a1);
			EATSPACE();				/* EXTENSION */
			if (*p == ',') {
				naddr++;
				p++;
				EATSPACE();			/* EXTENSION */
				cmd->a2 = xmalloc(sizeof(struct s_addr));
				p = compile_addr(p, cmd->a2);
			}
		}

nonsel:		/* Now parse the command */
		EATSPACE();
		if (!*p)
			err(COMPILE, "command expected");
		cmd->code = *p;
		for (fp = cmd_fmts; fp->code; fp++)
			if (fp->code == *p)
				break;
		if (!fp->code)
			err(COMPILE, "invalid command code %c", *p);
		if (naddr > fp->naddr)
			err(COMPILE,
"command %c expects up to %d address(es), found %d", *p, fp->naddr, naddr);
		switch (fp->args) {
		case NONSEL:			/* ! */
			cmd->nonsel = ! cmd->nonsel;
			p++;
			goto nonsel;
		case GROUP:			/* { */
			p++;
			EATSPACE();
			if (!*p)
				p = NULL;
			cmd2 = xmalloc(sizeof(struct s_command));
			cmd2->code = '}';
			cmd2->a1 = cmd2->a2 = NULL;
			cmd2->nonsel = 0;
			*compile_stream("}", &cmd->u.c, p) = cmd2;
			cmd->next = cmd2;
			link = &cmd2->next;
			break;
		case EMPTY:		/* d D g G h H l n N p P q x = \0 */
			p++;
			EATSPACE();
			if (*p == ';') {
				p++;
				link = &cmd->next;
				goto semicolon;
			}
			if (*p)
				err(COMPILE,
"extra characters at the end of %c command", cmd->code);
			break;
		case TEXT:			/* a c i */
			p++;
			EATSPACE();
			if (*p != '\\')
				err(COMPILE,
"command %c expects \\ followed by text", cmd->code);
			p++;
			EATSPACE();
			if (*p)
				err(COMPILE,
"extra characters after \\ at the end of %c command", cmd->code);
			cmd->t = compile_text();
			break;
		case COMMENT:			/* \0 # */
			break;
		case WFILE:			/* w */
			p++;
			EATSPACE();
			if (*p == '\0')
				err(COMPILE, "filename expected");
			cmd->t = duptoeol(p);
			if (aflag)
				cmd->u.fd = -1;
			else if ((cmd->u.fd = open(p, 
			    O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
			    DEFFILEMODE)) == -1)
				err(FATAL, "%s: %s\n", p, strerror(errno));
			break;
		case RFILE:			/* r */
			p++;
			EATSPACE();
			if (*p == '\0')
				err(COMPILE, "filename expected");
			else
				cmd->t = duptoeol(p);
			break;
		case BRANCH:			/* b t */
			p++;
			EATSPACE();
			if (*p == '\0')
				cmd->t = NULL;
			else
				cmd->t = duptoeol(p);
			break;
		case LABEL:			/* : */
			p++;
			EATSPACE();
			cmd->t = duptoeol(p);
			if (strlen(p) == 0)
				err(COMPILE, "empty label");
			break;
		case SUBST:			/* s */
			p++;
			if (*p == '\0' || *p == '\\')
				err(COMPILE,
"substitute pattern can not be delimited by newline or backslash");
			cmd->u.s = xmalloc(sizeof(struct s_subst));
			p = compile_re(p, &cmd->u.s->re);
			if (p == NULL)
				err(COMPILE, "unterminated substitute pattern");
			--p;
			p = compile_subst(p, cmd->u.s);
			p = compile_flags(p, cmd->u.s);
			EATSPACE();
			if (*p == ';') {
				p++;
				link = &cmd->next;
				goto semicolon;
			}
			break;
		case TR:			/* y */
			p++;
			p = compile_tr(p, (char **)&cmd->u.y);
			EATSPACE();
			if (*p == ';') {
				p++;
				link = &cmd->next;
				goto semicolon;
			}
			if (*p)
				err(COMPILE,
"extra text at the end of a transform command");
			break;
		}
	}
}

/*
 * Get a delimited string.  P points to the delimeter of the string; d points
 * to a buffer area.  Newline and delimiter escapes are processed; other
 * escapes are ignored.
 *
 * Returns a pointer to the first character after the final delimiter or NULL
 * in the case of a non-terminated string.  The character array d is filled
 * with the processed string.
 */
static char *
compile_delimited(p, d)
	char *p, *d;
{
	char c;

	c = *p++;
	if (c == '\0')
		return (NULL);
	else if (c == '\\')
		err(COMPILE, "\\ can not be used as a string delimiter");
	else if (c == '\n')
		err(COMPILE, "newline can not be used as a string delimiter");
	while (*p) {
		if (*p == '[') {
			if ((d = compile_ccl(&p, d)) == NULL)
				err(COMPILE, "unbalanced brackets ([])");
			continue;
		} else if (*p == '\\' && p[1] == c)
			p++;
		else if (*p == '\\' && p[1] == 'n') {
			*d++ = '\n';
			p += 2;
			continue;
		} else if (*p == '\\' && p[1] == '\\')
			*d++ = *p++;
		else if (*p == c) {
			*d = '\0';
			return (p + 1);
		}
		*d++ = *p++;
	}
	return (NULL);
}


/* compile_ccl: expand a POSIX character class */
static char *
compile_ccl(sp, t)
	char **sp;
	char *t;
{
	int c, d;
	char *s = *sp;

	*t++ = *s++;
	if (*s == '^')
		*t++ = *s++;
	if (*s == ']')
		*t++ = *s++;
	for (; *s && (*t = *s) != ']'; s++, t++)
		if (*s == '[' && ((d = *(s+1)) == '.' || d == ':' || d == '=')) {
			*++t = *++s, t++, s++;
			for (c = *s; (*t = *s) != ']' || c != d; s++, t++)
				if ((c = *s) == '\0')
					return NULL;
		} else if (*s == '\\' && s[1] == 'n')
			    *t = '\n', s++;
	return (*s == ']') ? *sp = ++s, ++t : NULL;
}

/*
 * Get a regular expression.  P points to the delimiter of the regular
 * expression; repp points to the address of a regexp pointer.  Newline
 * and delimiter escapes are processed; other escapes are ignored.
 * Returns a pointer to the first character after the final delimiter
 * or NULL in the case of a non terminated regular expression.  The regexp
 * pointer is set to the compiled regular expression.
 * Cflags are passed to regcomp.
 */
static char *
compile_re(p, repp)
	char *p;
	regex_t **repp;
{
	int eval;
	char re[_POSIX2_LINE_MAX + 1];

	p = compile_delimited(p, re);
	if (p && strlen(re) == 0) {
		*repp = NULL;
		return (p);
	}
	*repp = xmalloc(sizeof(regex_t));
	if (p && (eval = regcomp(*repp, re, 0)) != 0)
		err(COMPILE, "RE error: %s", strregerror(eval, *repp));
	if (maxnsub < (*repp)->re_nsub)
		maxnsub = (*repp)->re_nsub;
	return (p);
}

/*
 * Compile the substitution string of a regular expression and set res to
 * point to a saved copy of it.  Nsub is the number of parenthesized regular
 * expressions.
 */
static char *
compile_subst(p, s)
	char *p;
	struct s_subst *s;
{
	static char lbuf[_POSIX2_LINE_MAX + 1];
	int asize, ref, size;
	char c, *text, *op, *sp;

	c = *p++;			/* Terminator character */
	if (c == '\0')
		return (NULL);

	s->maxbref = 0;
	s->linenum = linenum;
	asize = 2 * _POSIX2_LINE_MAX + 1;
	text = xmalloc(asize);
	size = 0;
	do {
		op = sp = text + size;
		for (; *p; p++) {
			if (*p == '\\') {
				p++;
				if (strchr("123456789", *p) != NULL) {
					*sp++ = '\\';
					ref = *p - '0';
					if (s->re != NULL &&
					    ref > s->re->re_nsub)
						err(COMPILE,
"\\%c not defined in the RE", *p);
					if (s->maxbref < ref)
						s->maxbref = ref;
				} else if (*p == '&' || *p == '\\')
					*sp++ = '\\';
			} else if (*p == c) {
				p++;
				*sp++ = '\0';
				size += sp - op;
				s->new = xrealloc(text, size);
				return (p);
			} else if (*p == '\n') {
				err(COMPILE,
"unescaped newline inside substitute pattern");
				/* NOTREACHED */
			}
			*sp++ = *p;
		}
		size += sp - op;
		if (asize - size < _POSIX2_LINE_MAX + 1) {
			asize *= 2;
			text = xmalloc(asize);
		}
	} while (cu_fgets(p = lbuf, sizeof(lbuf)));
	err(COMPILE, "unterminated substitute in regular expression");
	/* NOTREACHED */
}

/*
 * Compile the flags of the s command
 */
static char *
compile_flags(p, s)
	char *p;
	struct s_subst *s;
{
	int gn;			/* True if we have seen g or n */
	char wfile[_POSIX2_LINE_MAX + 1], *q;

	s->n = 1;				/* Default */
	s->p = 0;
	s->wfile = NULL;
	s->wfd = -1;
	for (gn = 0;;) {
		EATSPACE();			/* EXTENSION */
		switch (*p) {
		case 'g':
			if (gn)
				err(COMPILE,
"more than one number or 'g' in substitute flags");
			gn = 1;
			s->n = 0;
			break;
		case '\0':
		case '\n':
		case ';':
			return (p);
		case 'p':
			s->p = 1;
			break;
		case '1': case '2': case '3':
		case '4': case '5': case '6':
		case '7': case '8': case '9':
			if (gn)
				err(COMPILE,
"more than one number or 'g' in substitute flags");
			gn = 1;
			/* XXX Check for overflow */
			s->n = (int)strtol(p, &p, 10);
			break;
		case 'w':
			p++;
#ifdef HISTORIC_PRACTICE
			if (*p != ' ') {
				err(WARNING, "space missing before w wfile");
				return (p);
			}
#endif
			EATSPACE();
			q = wfile;
			while (*p) {
				if (*p == '\n')
					break;
				*q++ = *p++;
			}
			*q = '\0';
			if (q == wfile)
				err(COMPILE, "no wfile specified");
			s->wfile = strdup(wfile);
			if (!aflag && (s->wfd = open(wfile,
			    O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
			    DEFFILEMODE)) == -1)
				err(FATAL, "%s: %s\n", wfile, strerror(errno));
			return (p);
		default:
			err(COMPILE,
			    "bad flag in substitute command: '%c'", *p);
			break;
		}
		p++;
	}
}

/*
 * Compile a translation set of strings into a lookup table.
 */
static char *
compile_tr(p, transtab)
	char *p;
	char **transtab;
{
	int i;
	char *lt, *op, *np;
	char old[_POSIX2_LINE_MAX + 1];
	char new[_POSIX2_LINE_MAX + 1];

	if (*p == '\0' || *p == '\\')
		err(COMPILE,
"transform pattern can not be delimited by newline or backslash");
	p = compile_delimited(p, old);
	if (p == NULL) {
		err(COMPILE, "unterminated transform source string");
		return (NULL);
	}
	p = compile_delimited(--p, new);
	if (p == NULL) {
		err(COMPILE, "unterminated transform target string");
		return (NULL);
	}
	EATSPACE();
	if (strlen(new) != strlen(old)) {
		err(COMPILE, "transform strings are not the same length");
		return (NULL);
	}
	/* We assume characters are 8 bits */
	lt = xmalloc(UCHAR_MAX);
	for (i = 0; i <= UCHAR_MAX; i++)
		lt[i] = (char)i;
	for (op = old, np = new; *op; op++, np++)
		lt[(u_char)*op] = *np;
	*transtab = lt;
	return (p);
}

/*
 * Compile the text following an a or i command.
 */
static char *
compile_text()
{
	int asize, size;
	char *text, *p, *op, *s;
	char lbuf[_POSIX2_LINE_MAX + 1];

	asize = 2 * _POSIX2_LINE_MAX + 1;
	text = xmalloc(asize);
	size = 0;
	while (cu_fgets(lbuf, sizeof(lbuf))) {
		op = s = text + size;
		p = lbuf;
		EATSPACE();
		for (; *p; p++) {
			if (*p == '\\')
				p++;
			*s++ = *p;
		}
		size += s - op;
		if (p[-2] != '\\') {
			*s = '\0';
			break;
		}
		if (asize - size < _POSIX2_LINE_MAX + 1) {
			asize *= 2;
			text = xmalloc(asize);
		}
	}
	return (xrealloc(text, size + 1));
}

/*
 * Get an address and return a pointer to the first character after
 * it.  Fill the structure pointed to according to the address.
 */
static char *
compile_addr(p, a)
	char *p;
	struct s_addr *a;
{
	char *end;

	switch (*p) {
	case '\\':				/* Context address */
		++p;
		/* FALLTHROUGH */
	case '/':				/* Context address */
		p = compile_re(p, &a->u.r);
		if (p == NULL)
			err(COMPILE, "unterminated regular expression");
		a->type = AT_RE;
		return (p);

	case '$':				/* Last line */
		a->type = AT_LAST;
		return (p + 1);
						/* Line number */
	case '0': case '1': case '2': case '3': case '4': 
	case '5': case '6': case '7': case '8': case '9':
		a->type = AT_LINE;
		a->u.l = strtol(p, &end, 10);
		return (end);
	default:
		err(COMPILE, "expected context address");
		return (NULL);
	}
}

/*
 * Return a copy of all the characters up to \n or \0
 */
static char *
duptoeol(s)
	register char *s;
{
	size_t len;
	char *start;

	for (start = s; *s != '\0' && *s != '\n'; ++s);
	*s = '\0';
	len = s - start + 1;
	return (memmove(xmalloc(len), start, len));
}

/*
 * Find the label contained in the command l in the command linked list cp.
 * L is excluded from the search.  Return NULL if not found.
 */
static struct s_command *
findlabel(l, cp)
	struct s_command *l, *cp;
{
	struct s_command *r;

	for (; cp; cp = cp->next)
		if (cp->code == ':' && cp != l && strcmp(l->t, cp->t) == 0)
			return (cp);
		else if (cp->code == '{' && (r = findlabel(l, cp->u.c)))
			return (r);
	return (NULL);
}

/*
 * Convert goto label names to addresses.
 * Detect duplicate labels.
 * Set appendnum to the number of a and r commands in the script.
 * Free the memory used by labels in b and t commands (but not by :)
 * Root is a pointer to the script linked list; cp points to the
 * search start.
 * TODO: Remove } nodes
 */
static void
fixuplabel(root, cp, end)
	struct s_command *root, *cp, *end;
{
	struct s_command *cp2;

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