/*

 *      $XConsortium: regexp.c /main/3 1995/07/13 18:30:18 drk $

 *

 *      @(#)regexp.c	1.4 04 Mar 1994

 *

 *      RESTRICTED CONFIDENTIAL INFORMATION:

 *

 *      The information in this document is subject to special

 *      restrictions in a confidential disclosure agreement between

 *      HP, IBM, Sun, USL, SCO and Univel.  Do not distribute this

 *      document outside HP, IBM, Sun, USL, SCO, or Univel without

 *      Sun's specific written approval.  This document and all copies

 *      and derivative works thereof must be returned or destroyed at

 *      Sun's request.

 *

 *      Copyright 1993 Sun Microsystems, Inc.  All rights reserved.

 *

 */

/*

 * _XmRegcomp and _XmRegexec

 *

 *	Copyright (c) 1986 by University of Toronto.

 *	Written by Henry Spencer.  Not derived from licensed software.

 *

 *	Permission is granted to anyone to use this software for any

 *	purpose on any computer system, and to redistribute it freely,

 *	subject to the following restrictions:

 *

 *	1. The author is not responsible for the consequences of use of

 *		this software, no matter how awful, even if they arise

 *		from defects in it.

 *

 *	2. The origin of this software must not be misrepresented, either

 *		by explicit claim or by omission.

 *

 *	3. Altered versions must be plainly marked as such, and must not

 *		be misrepresented as being the original software.

 *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,

 *** hoptoad!gnu, on 27 Dec 1986, to add \n as an alternative to |

 *** to assist in implementing egrep.

 *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,

 *** hoptoad!gnu, on 27 Dec 1986, to add \< and \> for word-matching

 *** as in BSD grep and ex.

 *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,

 *** hoptoad!gnu, on 28 Dec 1986, to optimize characters quoted with \.

 *** THIS IS AN ALTERED VERSION.  It was altered by James A. Woods,

 *** ames!jaw, on 19 June 1987, to quash a regcomp() redundancy.

 *** THIS IS AN ALTERED VERSION.  It was altered by Ajay Vohra,

 *** ajay@eng.sun.com, on 2 March 1994, to make it work in all locales.

 **  The API was altered too.

 *

 * Beware that some of this code is subtly aware of the way operator

 * precedence is structured in regular expressions.  Serious changes in

 * regular-expression syntax might require a total rethink.

 */

#ifdef HAVE_CONFIG_H

#include <config.h>

#endif

#include "regexpI.h"

#include <stdio.h>

#include <ctype.h>

#include <wctype.h>

#include <stdlib.h>

#include <string.h>

/*

 * The "internal use only" fields in regexpI.h are present to pass info from

 * compile to execute that permits the execute phase to run lots faster on

 * simple cases.  They are:

 *

 * regstart	char that must begin a match; '\0' if none obvious

 * reganch	is the match anchored (at beginning-of-line only)?

 * regmust	string (pointer into program) that match must include, or NULL

 * regmlen	length of regmust string

 *

 * Regstart and reganch permit very fast decisions on suitable starting points

 * for a match, cutting down the work a lot.  Regmust permits fast rejection

 * of lines that cannot possibly match.  The regmust tests are costly enough

 * that _XmRegcomp() supplies a regmust only if the r.e. contains something

 * potentially expensive (at present, the only such thing detected is * or +

 * at the start of the r.e., which can involve a lot of backup).  Regmlen is

 * supplied because the test in _XmRegexec() needs it and _XmRegcomp() is computing

 * it anyway.

 */

/*

 * Structure for regexp "program".  This is essentially a linear encoding

 * of a nondeterministic finite-state machine (aka syntax charts or

 * "railroad normal form" in parsing technology).  Each node is an opcode

 * plus a "next" pointer, possibly plus an operand.  "Next" pointers of

 * all nodes except BRANCH implement concatenation; a "next" pointer with

 * a BRANCH on both ends of it is connecting two alternatives.  (Here we

 * have one of the subtle syntax dependencies:  an individual BRANCH (as

 * opposed to a collection of them) is never concatenated with anything

 * because of operator precedence.)  The operand of some types of node is

 * a literal string; for others, it is a node leading into a sub-FSM.  In

 * particular, the operand of a BRANCH node is the first node of the branch.

 * (NB this is *not* a tree structure:  the tail of the branch connects

 * to the thing following the set of BRANCHes.)  The opcodes are:

 */

/* definition	number	opnd?	meaning */

#define	END	0	/* no	End of program. */

#define	BOL	1	/* no	Match "" at beginning of line. */

#define	EOL	2	/* no	Match "" at end of line. */

#define	ANY	3	/* no	Match any one character. */

#define	ANYOF	4	/* str	Match any character in this string. */

#define	ANYBUT	5	/* str	Match any character not in this string. */

#define	BRANCH	6	/* node	Match this alternative, or the next... */

#define	BACK	7	/* no	Match "", "next" ptr points backward. */

#define	EXACTLY	8	/* str	Match this string. */

#define	NOTHING	9	/* no	Match empty string. */

#define	STAR	10	/* node	Match this (simple) thing 0 or more times. */

#define	PLUS	11	/* node	Match this (simple) thing 1 or more times. */

#define	WORDA	12	/* no	Match "" at wordchar, where prev is nonword */

#define	WORDZ	13	/* no	Match "" at nonwordchar, where prev is word */

#define	OPEN	20	/* no	Mark this point in input as start of #n. */

/*	OPEN+1 is number 1, etc. */

#define	CLOSE	30	/* no	Analogous to OPEN. */

/*

 * Opcode notes:

 *

 * BRANCH	The set of branches constituting a single choice are hooked

 *		together with their "next" pointers, since precedence prevents

 *		anything being concatenated to any individual branch.  The

 *		"next" pointer of the last BRANCH in a choice points to the

 *		thing following the whole choice.  This is also where the

 *		final "next" pointer of each individual branch points; each

 *		branch starts with the operand node of a BRANCH node.

 *

 * BACK		Normal "next" pointers all implicitly point forward; BACK

 *		exists to make loop structures possible.

 *

 * STAR,PLUS	'?', and complex '*' and '+', are implemented as circular

 *		BRANCH structures using BACK.  Simple cases (one character

 *		per match) are implemented with STAR and PLUS for speed

 *		and to minimize recursive plunges.

 *

 * OPEN,CLOSE	...are numbered at compile time.

 */

/*

 * A node is one char of opcode followed by two chars of "next" pointer.

 * "Next" pointers are stored as two 8-bit pieces, high order first.  The

 * value is a positive offset from the opcode of the node containing it.

 * An operand, if any, simply follows the node.  (Note that much of the

 * code generation knows about this implicit relationship.)

 *

 * Using two bytes for the "next" pointer is vast overkill for most things,

 * but allows patterns to get big without disasters.

 */

#define	OP(p)	(*(p))

#define	NEXT(p)	(((*((p)+1)&0377)<<8) + (*((p)+2)&0377))

#define	OPERAND(p)	((p) + 3)

/*

 * See regmagic.h for one further detail of program structure.

 */

/*

 * Utility definitions.

 */

#define INCRLEN(l)   (l ? l: 1)

#define CHARLEN(p)	(MB_CUR_MAX > 1 ? (mblen(p, MB_CUR_MAX)): (*p ? 1 : 0))

#ifndef CHARBITS

#define	UCHARAT(p)	((int)*(unsigned char *)(p))

#else

#define	UCHARAT(p)	((int)*(p)&CHARBITS)

#endif

#define	FAIL(m)	{ return(NULL); }

#define	ISMULT(p)	((CHARLEN(p) == 1) &&  ((*p) == '*' || (*p) == '+' || (*p) == '?') )

/*

 * Flags to be passed up and down.

 */

#define	HASWIDTH	01	/* Known never to match null string. */

#define	SIMPLE		02	/* Simple enough to be STAR/PLUS operand. */

#define	SPSTART		04	/* Starts with * or +. */

#define	WORST		0	/* Worst case. */

/*

 * Global work variables for _XmRegcomp().

 */

static char	*regparse;		/* Input-scan pointer. */

static int	regnpar;		/* () count. */

static char	regdummy;

static char	*regcode;		/* Code-emit pointer; &regdummy = don't. */

static long	regsize;		/* Code size. */

/*

 * Forward declarations for _XmRegcomp()'s friends.

 */

static int	inclass(char *set, char *s);

static char	*reg(int paren, int *flagp);

static char	*regbranch(int *flagp);

static char	*regatom(int *flagp);

static char	*regpiece(int *flagp);

static char	*regnode(char op);

static void	regp(char *p);

static void	regc(char b);

static void	reginsert(char op, char *opnd);

static void	regtail(char *p, char *val);

static void	regoptail(char *p, char *val);

static char	*regnext(char *p);

/*

 - inclass - find if a char* 's' is within the collation sequence defined by 'set' 

 * of characters. This replaces the original code where all the characters 

 * were explicitly enumerated after the ANYOF regnode and where strchr was used

 * to determine if the given character belonged to the character class or not.

 * In asian locales, enumerating all the characters between two characters

 * is neither possible nor feasible (there could be thousands of character

 * between two characters. Hence this new function. It returns 1 if 

 * char *s does belong to the class 'set'; else 0.

 */

static int	

inclass(char *set, char *s)

{

	char	*p = set;

	int	len = 0, plen = 0;

	while ((len = CHARLEN(p))) {

		switch (len) {

		case 1:

			if (*p == '-' 	 &&  

				p != set	 &&  

					CHARLEN((p + 1))) {

				char	*begin = p -plen;

				char	*end = p + 1;

				if (strcoll(s, begin) >= 0 &&  

					strcoll(s, end) <= 0)

					return 1;

			}

			if (*p == *s)

				return 1;

			break;

		default:

			if (!strncmp(p, s, len))

				return 1;

		}

		plen = len;

		p += len;

	}

	return 0;

}

/*

 - _XmRegcomp - compile a regular expression into internal code

 *

 * We can't allocate space until we know how big the compiled form will be,

 * but we can't compile it (and thus know how big it is) until we've got a

 * place to put the code.  So we cheat:  we compile it twice, once with code

 * generation turned off and size counting turned on, and once "for real".

 * This also means that we don't allocate space until we are sure that the

 * thing really will compile successfully, and we never have to move the

 * code and thus invalidate pointers into it.  (Note that it has to be in

 * one piece because free() must be able to free it all.)

 *

 * Beware that the optimization-preparation code in here knows about some

 * of the structure of the compiled regexp.

 */

XmRegexpRec *

_XmRegcomp(char *exp)

{

	register XmRegexpRec *r;

	register char	*scan;

	register char	*longest;

	register int	len;

	int	flags;

	if (exp == NULL)

		FAIL("NULL argument");

	/* First pass: determine size, legality. */

#ifdef notdef

	if (exp[0] == '.' && exp[1] == '*')

		exp += 2;  /* aid grep */

#endif

	regparse = (char *)exp;

	regnpar = 1;

	regsize = 0L;

	regcode = &regdummy;

	regc(MAGIC);

	if (reg(0, &flags) == NULL)

		return(NULL);

	/* Small enough for pointer-storage convention? */

	if (regsize >= 32767L)		/* Probably could be 65535L. */

		FAIL("regexp too big");

	/* Allocate space. */

	r = (XmRegexpRec * )malloc(sizeof(XmRegexpRec) + (unsigned)regsize);

	if (r == NULL)

		FAIL("out of space");

	/* Second pass: emit code. */

	regparse = (char *)exp;

	regnpar = 1;

	regcode = r->program;

	regc(MAGIC);

	if (reg(0, &flags) == NULL)

		return(NULL);

	/* Dig out information for optimizations. */

	r->regstart = '\0';	/* Worst-case defaults. */

	r->reganch = 0;

	r->regmust = NULL;

	r->regmlen = 0;

	scan = r->program + 1;			/* First BRANCH. */

	if (OP(regnext(scan)) == END) {		/* Only one top-level choice. */

		scan = OPERAND(scan);

		/* Starting-point info. */

		if (OP(scan) == EXACTLY)

			r->regstart = *OPERAND(scan);

		else if (OP(scan) == BOL)

			r->reganch++;

		/*

		 * If there's something expensive in the r.e., find the

		 * longest literal string that must appear and make it the

		 * regmust.  Resolve ties in favor of later strings, since

		 * the regstart check works with the beginning of the r.e.

		 * and avoiding duplication strengthens checking.  Not a

		 * strong reason, but sufficient in the absence of others.

		 */

		if (flags & SPSTART) {

			longest = NULL;

			len = 0;

			for (; scan != NULL; scan = regnext(scan))

				if (OP(scan) == EXACTLY 	 &&  

					(int)strlen(OPERAND(scan)) >= (int)len) {

					longest = OPERAND(scan);

					len = strlen(OPERAND(scan));

				}

			r->regmust = longest;

			r->regmlen = len;

		}

	}

	return(r);

}

/*

 - reg - regular expression, i.e. main body or parenthesized thing

 *

 * Caller must absorb opening parenthesis.

 *

 * Combining parenthesis handling with the base level of regular expression

 * is a trifle forced, but the need to tie the tails of the branches to what

 * follows makes it hard to avoid.

 */

static char	*

reg(int paren, int *flagp)

{

	register char	*ret;

	register char	*br;

	register char	*ender;

	register int	parno;

	int	flags;

	int	len = 0;

	*flagp = HASWIDTH;	/* Tentatively. */

	/* Make an OPEN node, if parenthesized. */

	if (paren) {

		if (regnpar >= NSUBEXP)

			FAIL("too many ()");

		parno = regnpar;

		regnpar++;

		ret = regnode(OPEN + parno);

	} else

		ret = NULL;

	/* Pick up the branches, linking them together. */

	br = regbranch(&flags);

	if (br == NULL)

		return(NULL);

	if (ret != NULL)

		regtail(ret, br);	/* OPEN -> first. */

		else

		ret = br;

	if (!(flags & HASWIDTH))

		*flagp &= ~HASWIDTH;

	*flagp |= flags & SPSTART;

	while (  ((len = CHARLEN(regparse)) == 1) &&  

			(*regparse == '|' || *regparse == '\n')) {

		regparse++;

		br = regbranch(&flags);

		if (br == NULL)

			return(NULL);

		regtail(ret, br);	/* BRANCH -> BRANCH. */

		if (!(flags & HASWIDTH))

			*flagp &= ~HASWIDTH;

		*flagp |= flags & SPSTART;

	}

	/* Make a closing node, and hook it on the end. */

	ender = regnode((paren) ? CLOSE + parno : END);

	regtail(ret, ender);

	/* Hook the tails of the branches to the closing node. */

	for (br = ret; br != NULL; br = regnext(br))

		regoptail(br, ender);

	/* Check for proper termination. */

	if (paren && (len != 1 || *regparse++ != ')')) {

		FAIL("unmatched ()");

	} else if (!paren && (len != 0)) {

		if ((len == 1) && *regparse == ')') {

			FAIL("unmatched ()");

		} else

			FAIL("junk on end");	/* "Can't happen". */

		/* NOTREACHED */

	}

	return(ret);

}

/*

 - regbranch - one alternative of an | operator

 *

 * Implements the concatenation operator.

 */

static char	*

regbranch(int *flagp)

{

	register char	*ret;

	register char	*chain;

	register char	*latest;

	int	flags;

	int	len = 0;

	*flagp = WORST;		/* Tentatively. */

	ret = regnode(BRANCH);

	chain = NULL;

	while ((len = CHARLEN(regparse))  &&  

		(len != 1 || (*regparse != ')' &&  

			*regparse != '\n' && *regparse != '|'))) {

		latest = regpiece(&flags);

		if (latest == NULL)

			return(NULL);

		*flagp |= flags & HASWIDTH;

		if (chain == NULL)	/* First piece. */

			*flagp |= flags & SPSTART;

			else

			regtail(chain, latest);

		chain = latest;

	}

	if (chain == NULL)	/* Loop ran zero times. */

		(void) regnode(NOTHING);

	return(ret);

}

/*

 - regpiece - something followed by possible [*+?]

 *

 * Note that the branching code sequences used for ? and the general cases

 * of * and + are somewhat optimized:  they use the same NOTHING node as

 * both the endmarker for their branch list and the body of the last branch.

 * It might seem that this node could be dispensed with entirely, but the

 * endmarker role is not redundant.

 */

static char	*

regpiece(int *flagp)

{

	register char	*ret;

	register char	*op;

	register char	*next;

	int	flags;

	int	len = 0;

	ret = regatom(&flags);

	if (ret == NULL)

		return(NULL);

	op = regparse;

	if (!ISMULT(op)) {

		*flagp = flags;

		return(ret);

	}

	len = CHARLEN(op);

	if (!(flags & HASWIDTH) && ((len != 1) || (*op != '?')) )

		FAIL("*+ operand could be empty");

	*flagp = ((len != 1) || (*op != '+')) ?  (WORST | SPSTART) : (WORST | HASWIDTH);

	if ((len == 1) && (*op == '*') && (flags & SIMPLE))

		reginsert(STAR, ret);

	else if ((len == 1) && 

			(*op == '*')) {

		/* Emit x* as (x&|), where & means "self". */

		reginsert(BRANCH, ret);			/* Either x */

		regoptail(ret, regnode(BACK));		/* and loop */

		regoptail(ret, ret);			/* back */

		regtail(ret, regnode(BRANCH));		/* or */

		regtail(ret, regnode(NOTHING));		/* null. */

	} else if ((len == 1) && (*op == '+') && (flags & SIMPLE))

		reginsert(PLUS, ret);

	else if ((len == 1) && (*op == '+')) {

		/* Emit x+ as x(&|), where & means "self". */

		next = regnode(BRANCH);			/* Either */

		regtail(ret, next);

		regtail(regnode(BACK), ret);		/* loop back */

		regtail(next, regnode(BRANCH));		/* or */

		regtail(ret, regnode(NOTHING));		/* null. */

	} else if ((len == 1) && (*op == '?')) {

		/* Emit x? as (x|) */

		reginsert(BRANCH, ret);			/* Either x */

		regtail(ret, regnode(BRANCH));		/* or */

		next = regnode(NOTHING);		/* null. */

		regtail(ret, next);

		regoptail(ret, next);

	}

	regparse += INCRLEN(len);

	if (ISMULT(regparse))

		FAIL("nested *?+");

	return(ret);

}

/*

 - regatom - the lowest level

 *

 * Optimization:  gobbles an entire sequence of ordinary characters so that

 * it can turn them into a single node, which is smaller to store and

 * faster to run.  Backslashed characters are exceptions, each becoming a

 * separate node; the code is simpler that way and it's not worth fixing.

 */

static char	*

regatom(int *flagp)

{

	register char	*ret;

	int	flags;

	int	len = 0, plen = 0;

	char	*cp = NULL;

	*flagp = WORST;		/* Tentatively. */

	len = CHARLEN(regparse);

	cp = regparse;

	regparse += INCRLEN(len);

	switch (len) {

		/* FIXME: these chars only have meaning at beg/end of pat? */

	case 0:

	case 1:

		switch (*cp) {

		case '^':

			ret = regnode(BOL);

			break;

		case '$':

			ret = regnode(EOL);

			break;

		case '.':

			ret = regnode(ANY);

			*flagp |= HASWIDTH | SIMPLE;

			break;

		case '[':

			 {

				register char	*classbegin;

				register char	*classend;

				len = CHARLEN(regparse);

				if (len == 1 && *regparse == '^') {	/* Complement of range. */

					ret = regnode(ANYBUT);

					regparse++;

				} else

					ret = regnode(ANYOF);

				if (len == 1 && (*regparse == ']' || *regparse == '-'))

					regc(*regparse++);

				while ((len = CHARLEN(regparse))  &&  

						(len != 1 || *regparse != ']')) {

					if (len == 1 && *regparse == '-') {

						regparse++;

						regc('-');

						if (((len = CHARLEN(regparse)) == 1)  &&  

							(*regparse == ']' || *regparse == '\0'))

								;

						else {

							classbegin = regparse - 1 - plen ;

							classend = regparse;

							if (strcoll(classbegin, classend) > 0)

								FAIL("invalid [] range");

							regp(classend);

							regparse += len;

						}

					plen = len;

					} else {

						regp(regparse);

						regparse += len;

						plen = len;

					}

				}

				regc('\0');

				if (len != 1 || *regparse != ']')

					FAIL("unmatched []");

				regparse++;

				*flagp |= HASWIDTH | SIMPLE;

			}

			break;

		case '(':

			ret = reg(1, &flags);

			if (ret == NULL)

				return(NULL);

			*flagp |= flags & (HASWIDTH | SPSTART);

			break;

		case '\0':

		case '|':

		case '\n':

		case ')':

			FAIL("internal urp");	/* Supposed to be caught earlier. */

			break;

		case '?':

		case '+':

		case '*':

			FAIL("?+* follows nothing");

			break;

		case '\\':

			cp = regparse;

			len = CHARLEN(regparse);

			regparse += INCRLEN(len);

			switch (len) {

			case 1:

			case 0:

				switch (*cp) {

				case '\0':

					FAIL("trailing \\");

					break;

				case '<':

					ret = regnode(WORDA);

					break;

				case '>':

					ret = regnode(WORDZ);

					break;

					/* FIXME: Someday handle \1, \2, ... */

				default:

					goto de_fault;

				}

			default:

				/* Handle general quoted chars in exact-match routine */

				goto de_fault;

			}

			break;

		default:

			goto de_fault;

		}

		break;

de_fault:

	default:

		/*

		 * Encode a string of characters to be matched exactly.

		 *

		 * This is a bit tricky due to quoted chars and due to

		 * '*', '+', and '?' taking the SINGLE char previous

		 * as their operand.

		 *

		 * On entry, the char at regparse[-1] is going to go

		 * into the string, no matter what it is.  (It could be

		 * following a \ if we are entered from the '\' case.)

		 * 

		 * Basic idea is to pick up a good char in  ch  and

		 * examine the next char.  If it's *+? then we twiddle.

		 * If it's \ then we frozzle.  If it's other magic char

		 * we push  ch  and terminate the string.  If none of the

		 * above, we push  ch  on the string and go around again.

		 *

		 *  regprev  is used to remember where "the current char"

		 * starts in the string, if due to a *+? we need to back

		 * up and put the current char in a separate, 1-char, string.

		 * When  regprev  is NULL,  ch  is the only char in the

		 * string; this is used in *+? handling, and in setting

		 * flags |= SIMPLE at the end.

		 */

		 {

			char	*regprev;

			register char	*ch = 0, *nextc = 0;

			int	nextlen = 0;

			regparse -= INCRLEN(len);			/* Look at cur char */

			ret = regnode(EXACTLY);

			for ( regprev = 0 ; ; ) {

				ch = regparse;

				len = CHARLEN(regparse);

				regparse += INCRLEN(len);

				len = CHARLEN(regparse);

				switch (len) { /* look at length of the next one */

				default:

					regp(ch); /* add cur to string */

					break;

				case 0:

				case 1:

					switch (*regparse) {	/* look at next one */

					default:

						regp(ch); /* add cur to string */

						break;

					case '.':

					case '[':

					case '(':

					case ')':

					case '|':

					case '\n':

					case '$':

					case '^':

					case '\0':

						/* FIXME, $ and ^ should not always be magic */

magic:

						regp(ch);	/* dump cur char */

						goto done;	/* and we are done */

					case '?':

					case '+':

					case '*':

						if (!regprev) 	/* If just ch in str, */

							goto magic;	/* use it */

						/* End mult-char string one early */

						regparse = regprev; /* Back up parse */

						goto done;

					case '\\':

						regp(ch);	/* Cur char OK */

						nextc = regparse + len;

						nextlen = CHARLEN(nextc);

						switch (nextlen) {

						case 0:

						case 1:

							switch (*nextc) { /* Look after \ */

							case '\0':

							case '<':

							case '>':

								/* FIXME: Someday handle \1, \2, ... */

								goto done; /* Not quoted */

							default:

								/* Backup point is \, scan							 * point is

																								    after it. */

								regprev = regparse;

								regparse += INCRLEN(len);

								continue;	/* NOT break; */

							}

						default:

							/* Backup point is \, scan

																					                         * point is aft

							    er it. */

							regprev = regparse;

							regparse += INCRLEN(len);

							continue;       /* NOT break; */

						}

					}

				}

				regprev = regparse;	/* Set backup point */

			}

done:

			regc('\0');

			*flagp |= HASWIDTH;

			if (!regprev)		/* One char? */

				*flagp |= SIMPLE;

		}

		break;

	}

	return(ret);

}

/*

 - regnode - emit a node

 */

static char	*			/* Location. */

regnode(char op)

{

	register char	*ret;

	register char	*ptr;

	ret = regcode;

	if (ret == &regdummy) {

		regsize += 3;

		return(ret);

	}

	ptr = ret;

	*ptr++ = op;

	*ptr++ = '\0';		/* Null "next" pointer. */

	*ptr++ = '\0';

	regcode = ptr;

	return(ret);

}

/*

 - regc - emit (if appropriate) a character of code

 */

static void	

regp(char *p)

{

	int	len = CHARLEN(p);

	if (regcode != &regdummy)  {

		memcpy(regcode, p, len);

		regcode += INCRLEN(len);

	} else

		regsize += INCRLEN(len);

}

/*

 - regc - emit (if appropriate) a byte of code

 */

static void	

regc(char b)

{

	if (regcode != &regdummy)

		*regcode++ = b;

	else

		regsize++;

}

/*

 - reginsert - insert an operator in front of already-emitted operand

 *

 * Means relocating the operand.

 */

static void	

reginsert(char op, char *opnd)

{

	register char	*src;

	register char	*dst;

	register char	*place;

	if (regcode == &regdummy) {

		regsize += 3;

		return;

	}

	src = regcode;

	regcode += 3;

	dst = regcode;

	while (src > opnd)

		*--dst = *--src;

	place = opnd;		/* Op node, where operand used to be. */

	*place++ = op;

	*place++ = '\0';

	*place++ = '\0';

}

/*

 - regtail - set the next-pointer at the end of a node chain

 */

static void	

regtail(char *p, char *val)

{

	register char	*scan;

	register char	*temp;

	register int	offset;

	if (p == &regdummy)

		return;

	/* Find last node. */

	scan = p;

	for (; ; ) {