path: root/libuxre/regnfa.c

/*
 * Changes by Gunnar Ritter, Freiburg i. Br., Germany, November 2002.
 *
 * Sccsid @(#)regnfa.c	1.8 (gritter) 2/6/05
 */
/*  UNIX(R) Regular Expresssion Library
 *
 *  Note: Code is released under the GNU LGPL
 *
 *  Copyright (C) 2001 Caldera International, Inc.
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to:
 *        Free Software Foundation, Inc.
 *        59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

/*	#include "synonyms.h"	*/
#include <string.h>
#include <stdlib.h>
#include "re.h"
#include <stddef.h>
#include <ctype.h>

typedef unsigned char	Uchar;
typedef unsigned short	Ushort;

/*
* Nondeterministic Finite Automata.
*/
typedef struct t_graph	Graph;
struct t_graph
{
	union
	{
		Graph	*ptr;
		Info	info;
	} alt;
	Graph		*next;
	w_type		op;
};

typedef struct t_stack	Stack;
struct t_stack
{
	Stack		*link;	/* simplifies cleanup */
	Stack		*prev;	/* covered states */
	Graph		*wasgp;	/* node associated with this state */
	const Uchar	*str;	/* saved position in the string */
	Ushort		cnt;	/* ROP_BRACE: traversal count */
};

	/*
	* A Context holds all the information needed for each
	* potential path through the NFA graph.
	*/
typedef struct t_ctxt	Context;
struct t_ctxt
{
	Context		*link;	/* simplifies cleanup */
	Context		*next;	/* singly linked */
	Stack		*sp;	/* nested counts */
	Graph		*gp;	/* starting node */
	Graph		*wasgp;	/* node associated with this state */
	const Uchar	*str;	/* saved position in the string */
	Ushort		cnt;	/* ROP_BRACE: traversal count */
	size_t		nset;	/* length of rm[] that is currently set */
	regmatch_t	rm[1];	/* enough to cover re_nsub+1 (np->rmlen) */
};

struct re_nfa_ /*Nfa*/
{
	Graph	*gp;	/* entire NFA */
	Stack	*sp;	/* unused Stacks */
	Stack	*allsp;	/* linked Stacks (for cleanup) */
	Context	*allcp;	/* linked Contexts (for cleanup) */
	Context	*cur;	/* Contexts to be continued now */
	Context	*step;	/* Contexts waiting for a step of the NFA */
	Context	*avail;	/* unused Contexts */
	Context	**ecur;	/* ends cur list of Contexts */
	Context	**estp;	/* ends step list of Contexts */
	size_t	rmlen;	/* length of rm[] in each Context */
	size_t	rmmin;	/* minimum length needed */
	size_t	used;	/* length used for this libuxre_regnfaexec() */
	w_type	beg;	/* nonzero for fixed char initial node NFAs */
};

#define ROP_MTOR	ROP_CAT	/* ROP_OR, except might be empty loop */

	/*
	* Depth first traversal.
	* Make a singly linked list (in alt.ptr) of the graph's nodes.
	* Must toss any ROP_BKTs, too, since "alt" is overwritten.
	*/
static void
deltolist(Graph *gp, Graph **list)
{
	Graph *ptr;

	if ((ptr = gp->next) != 0) /* first time */
	{
		gp->next = 0;
		if (gp->op == ROP_OR || gp->op == ROP_MTOR)
			deltolist(gp->alt.ptr, list);
		deltolist(ptr, list);
		if (gp->op == ROP_BKT)
		{
			libuxre_bktfree(gp->alt.info.bkt);
			free(gp->alt.info.bkt);
		}
	}
	else if (gp->op == ROP_END)
		gp->op = ROP_NOP;
	else
		return;
	gp->alt.ptr = *list;
	*list = gp;
}

	/*
	* After the list is turned into a linked list,
	* walk that list freeing the nodes.
	*/
static void
delgraph(Graph *gp)
{
	Graph *gp2, end;

	gp2 = &end;
	deltolist(gp, &gp2);
	while ((gp = gp2) != &end)
	{
		gp2 = gp->alt.ptr;
		free(gp);
	}
}

	/*
	* Depth first traversal.
	* Look for ROP_NOPs and prune them from the graph.
	* Chain them all together on *nop's list.
	*/
static Graph *
nopskip(Graph *gp, Graph **nop)
{
	Graph *ptr;

	if ((ptr = gp->next) != 0) /* might have yet to do this subgraph */
	{
		if (gp->op == ROP_NOP)
		{
			if (gp->alt.ptr != 0) /* touched */
				return gp->next; /* already did it */
			gp->alt.ptr = *nop;
			*nop = gp;
		}
		gp->next = 0; /* this subgraph's pending */
		if (gp->op == ROP_OR || gp->op == ROP_MTOR)
			gp->alt.ptr = nopskip(gp->alt.ptr, nop);
		gp->next = nopskip(ptr, nop);
		if (gp->op == ROP_NOP)
			return gp->next;
	}
	return gp;
}

	/*
	* Postorder traversal of the parse tree.
	* Build a graph using "Thompson's" algorithm.
	* The only significant modification is the
	* ROP_BRACE->ROP_MTOR construction.
	* Returns 1 => graph might match empty
	*	  0 => graph cannot match empty
	*	 -1 => error (in allocation)
	*/
static int
mkgraph(Tree *tp, Graph **first, Graph **last)
{
	Graph *new = 0, *nop, *lf, *ll, *rf, *rl;
	int lmt, rmt = 0;

	if (tp->op != ROP_CAT)
	{
		if ((new = malloc(sizeof(Graph))) == 0)
			return 0;
		new->op = tp->op;	/* usually */
	}
	switch (tp->op)
	{
	case ROP_REF:
		new->alt.info.sub = tp->right.info.sub;
		*first = new;
		*last = new;
		return 1; /* safe--can't really tell */
	case ROP_BKT:
		tp->op = ROP_BKTCOPY;	/* now graph owns clean up */
		/*FALLTHROUGH*/
	case ROP_BKTCOPY:
		new->alt.info.bkt = tp->right.info.bkt;
		/*FALLTHROUGH*/
	default:
		*first = new;
		*last = new;
		return 0;
	case ROP_EMPTY:
		new->op = ROP_NOP;
		new->alt.ptr = 0;	/* untouched */
		*first = new;
		*last = new;
		return 1;
	case ROP_OR:
	case ROP_CAT:
		lf = 0;	/* in case of error */
		if ((rmt = mkgraph(tp->right.ptr, &rf, &rl)) < 0)
			goto err;
		/*FALLTHROUGH*/
	case ROP_STAR:
	case ROP_PLUS:
	case ROP_QUEST:
	case ROP_BRACE:
	case ROP_LP:
		if ((lmt = mkgraph(tp->left.ptr, &lf, &ll)) < 0)
			goto err;
		break;
	}
	/*
	* Note that ROP_NOP only serves as the node that reconnects
	* the two choices of an incoming ROP_OR or ROP_QUEST.  To
	* prevent rewalking portions of the graph in nopskip(),
	* this code marks all ROP_NOP nodes as currently untouched.
	*/
	switch (tp->op)
	{
	case ROP_OR:
		if ((nop = malloc(sizeof(Graph))) == 0)
			goto err;
		nop->op = ROP_NOP;
		nop->alt.ptr = 0;	/* untouched */
		ll->next = nop;
		rl->next = nop;
		new->next = lf;
		new->alt.ptr = rf;
		*first = new;
		*last = nop;
		return lmt | rmt;
	case ROP_CAT:	/* no "new" */
		ll->next = rf;
		*first = lf;
		*last = rl;
		return lmt & rmt;
	case ROP_QUEST:
		if ((nop = malloc(sizeof(Graph))) == 0)
			goto err;
		nop->op = ROP_NOP;
		nop->alt.ptr = 0;	/* untouched */
		new->op = ROP_OR;
		new->next = lf;
		new->alt.ptr = nop;
		ll->next = nop;
		*first = new;
		*last = nop;
		return 1;
	case ROP_STAR:
		*first = new;
		rmt = 1;
	star:;
		new->op = lmt ? ROP_MTOR : ROP_OR;
		new->alt.ptr = lf;
		ll->next = new;
		*last = new;
		return rmt;
	case ROP_PLUS:
		*first = lf;
		rmt = lmt;
		goto star;
	case ROP_BRACE:
		if ((nop = malloc(sizeof(Graph))) == 0)
			goto err;
		nop->op = ROP_MTOR; /* going to save state anyway... */
		nop->alt.ptr = lf;
		ll->next = new;
		new->next = nop;
		new->alt.info.num[1] = tp->right.info.num[1];
		if ((new->alt.info.num[0] = tp->right.info.num[0]) == 0)
		{
			lmt = 1;
			*first = new;
		}
		else
		{
			new->alt.info.num[0]--;	/* already done 1 */
			if (new->alt.info.num[1] != BRACE_INF)
				new->alt.info.num[1]--;	/* likewise */
			*first = lf;
		}
		*last = nop;
		return lmt;
	case ROP_LP:
		if ((nop = malloc(sizeof(Graph))) == 0)
			goto err;
		nop->op = ROP_RP;
		nop->alt.info.sub = tp->right.info.sub;
		new->alt.info.sub = tp->right.info.sub;
		new->next = lf;
		ll->next = nop;
		*first = new;
		*last = nop;
		return lmt;
	}
err:;
	if (KIND_ROP(tp->op) == BINARY_ROP && rf != 0)
		delgraph(rf);
	if (lf != 0)
		delgraph(lf);
	if (tp->op != ROP_CAT)
		free(new);
	return -1;
}

	/*
	* Semi-preorder traversal.
	* Return zero if there's no simple first character
	* (including the operation ROP_BOL) that must always
	* be at the start of a matching string.
	* This code doesn't attempt to get an answer if the
	* first of the tree many be empty.
	*/
static w_type
firstop(Tree *tp)
{
	w_type op;

	switch (tp->op)
	{
	case ROP_OR:
		if ((op = firstop(tp->left.ptr)) == 0
			|| op != firstop(tp->right.ptr))
		{
			return 0;
		}
		return op;
	case ROP_BRACE:
		if (tp->right.info.num[0] == 0)
			return 0;
		/*FALLTHROUGH*/
	case ROP_CAT:
	case ROP_PLUS:
	case ROP_LP:
		return firstop(tp->left.ptr);
	default:
		if (tp->op < 0)
			return 0;
		/*FALLTHROUGH*/
	case ROP_BOL:
		return tp->op;
	}
}

void
libuxre_regdelnfa(Nfa *np)
{
	Context *cp, *cpn;
	Stack *sp, *spn;

	if (np->gp != 0)
		delgraph(np->gp);
	for (cp = np->allcp; cp != 0; cp = cpn)
	{
		cpn = cp->link;
		free(cp);
	}
	for (sp = np->allsp; sp != 0; sp = spn)
	{
		spn = sp->link;
		free(sp);
	}
	free(np);
}

LIBUXRE_STATIC int
libuxre_regnfacomp(regex_t *ep, Tree *tp, Lex *lxp)
{
	Graph *gp, end;
	Nfa *np;

	if ((np = malloc(sizeof(Nfa))) == 0)
		goto err;
	np->gp = 0; /* in case of error */
	if (mkgraph(tp, &np->gp, &gp) < 0)
		goto err;
	gp->next = 0;	/* nothing follows ROP_END */
	np->rmlen = 0;
	if ((ep->re_flags & REG_NOSUB) == 0)
		np->rmlen = ep->re_nsub + 1;
	np->rmmin = 0;
	if (lxp->maxref != 0 && (np->rmmin = lxp->maxref + 1) > np->rmlen)
		np->rmlen = np->rmmin;
	/*
	* Delete all ROP_NOPs from the graph.
	* nopskip() disconnects them from the graph and
	* links them together through their alt.ptr's.
	*/
	gp = &end;
	np->gp = nopskip(np->gp, &gp);
	while (gp != &end)
	{
		Graph *gp2 = gp;

		gp = gp->alt.ptr;
		free(gp2);
	}
	np->sp = 0;
	np->allsp = 0;
	np->avail = 0;
	np->allcp = 0;
	ep->re_nfa = np;
	np->beg = firstop(tp); 
	return 0;
err:;
	if (np != 0)
	{
		if (np->gp != 0)
			delgraph(np->gp);
		free(np);
	}
	return REG_ESPACE;
}

static Stack *
newstck(Nfa *np)
{
	Stack *sp, **spp;
	int i;

	if ((sp = np->sp) == 0)	/* get more */
	{
		spp = &np->sp;
		i = 4;
		while ((sp = malloc(sizeof(Stack))) != 0)
		{
			sp->link = np->allsp;
			np->allsp = sp;
			*spp = sp;
			spp = &sp->prev;
			if (--i == 0)
				break;
		}
		*spp = 0;
		if ((sp = np->sp) == 0)	/* first malloc failed */
			return 0;
	}
	np->sp = sp->prev;
	return sp;
}

static int
mkstck(Nfa *np, Context *cp, Graph *gp)
{
	Stack *new, *sp;

	if (gp == 0)	/* copy existing stack tail */
	{
		/*
		* Hoist up top of stack.
		*/
		new = cp->sp;
		cp->wasgp = new->wasgp;
		cp->str = new->str;
		cp->cnt = new->cnt;
		cp->sp = new->prev;
		if ((sp = new->prev) == 0) /* only one below */
		{
			new->prev = np->sp;
			np->sp = new;
			cp->sp = 0;
			return 0;
		}
		for (;;) /* copy the rest; reusing the old top */
		{
			new->wasgp = sp->wasgp;
			new->str = sp->str;
			new->cnt = sp->cnt;
			if ((new->prev = sp->prev) == 0)
				break;
			if ((new->prev = newstck(np)) == 0)
				return REG_ESPACE;
			new = new->prev;
			sp = sp->prev;
		}
		return 0;
	}
	if (cp->wasgp != 0)	/* push current down */
	{
		if ((new = newstck(np)) == 0)
			return REG_ESPACE;
		new->prev = cp->sp;
		cp->sp = new;
		new->wasgp = cp->wasgp;
		new->str = cp->str;
		new->cnt = cp->cnt;
	}
	cp->wasgp = gp;
	cp->str = 0;
	cp->cnt = 0;
	return 0;
}

	/*
	* Allocate a new Context (from np->avail)
	* and add it to the end of the current list.
	*/
static int
newctxt(Nfa *np, Context *cp, Graph *gp)
{
	Context *new;
	size_t n;

	if ((new = np->avail) == 0)	/* need more */
	{
		Context *ncp, **cpp;
		int i;

		/*
		* Can't easily allocate Contexts in one call because
		* the alignments (given the varying length of rm[])
		* are potentially nontrivial.
		*/
		n = offsetof(Context, rm) + np->rmlen * sizeof(regmatch_t);
		i = 4;
		cpp = &np->avail;
		while ((ncp = malloc(n)) != 0)
		{
			ncp->link = np->allcp;
			np->allcp = ncp;
			*cpp = ncp;
			cpp = &ncp->next;
			if (--i == 0)
				break;
		}
		*cpp = 0;
		if ((new = np->avail) == 0)	/* first malloc failed */
			return REG_ESPACE;
	}
	np->avail = new->next;
	new->next = 0;
	new->gp = gp;
	new->sp = 0;
	new->wasgp = 0;
	new->nset = 0;
	if (cp != 0) /* copy existing context information */
	{
		if (cp->sp != 0) /* copy tail of stack */
		{
			new->sp = cp->sp;
			if (mkstck(np, new, 0) != 0)
				return REG_ESPACE;
		}
		new->wasgp = cp->wasgp;
		new->str = cp->str;
		new->cnt = cp->cnt;
		/*
		* Copy any valid subexpression match information
		* from the existing context.
		*/
		if (np->used != 0 && (n = cp->nset) != 0)
		{
			regmatch_t *rmn = new->rm, *rmo = cp->rm;

			new->nset = n;
			for (;; ++rmn, ++rmo)
			{
				rmn->rm_so = rmo->rm_so;
				rmn->rm_eo = rmo->rm_eo;
				if (--n == 0)
					break;
			}
		}
	}
	/*
	* Append it to the end of the current Context list.
	*/
	*np->ecur = new;
	np->ecur = &new->next;
	return 0;
}

	/*
	* Compare two byte string sequences for equality.
	* If REG_ICASE, walk through the strings doing
	* caseless comparisons of the wide characters.
	*/
static int
casecmp(const Uchar *s, Exec *xp, ssize_t i, ssize_t n, int mb_cur_max)
{
	const Uchar *p = &xp->str[i];
	const Uchar *end;
	w_type wc1, wc2;
	int k;

	if (strncmp((char *)s, (char *)p, n) == 0) /* try for exact match */
		return 1;
	if ((xp->flags & REG_ICASE) == 0)
		return 0;
	/*
	* Walk through each testing for a match, ignoring case,
	* of the resulting wide characters.
	* Note that only "s" can run out of characters.
	*/
	end = &p[n];
	do
	{
		if ((wc1 = *s++) == '\0')
			return 0;
		if (!ISONEBYTE(wc1) && (k = libuxre_mb2wc(&wc1, s)) > 0)
			s += k;
		if (!ISONEBYTE(wc2 = *p++) && (k = libuxre_mb2wc(&wc2, p)) > 0)
			p += k;
		if (wc1 != wc2)
		{
			wc1 = to_lower(wc1);
			wc2 = to_lower(wc2);
			if (wc1 != wc2)
				return 0;
		}
	} while (p < end);
	return 1;
}

LIBUXRE_STATIC int
libuxre_regnfaexec(Nfa *np, Exec *xp)
{
	const Uchar *s, *s1, *s2;
	Context *cp, *cpn;
	Graph *gp, *brace;
	Stack *sp, *spn;
	ssize_t rmso, len;
	int i, ret, mb_cur_max;
	w_type wc;
	size_t n;

	ret = 0;	/* assume it matches */
	rmso = -1;	/* but no match yet */
	np->cur = 0;
	np->step = 0;
	np->ecur = &np->cur;
	np->estp = &np->step;
	if ((np->used = xp->nmatch) < np->rmmin)
		np->used = np->rmmin;
	s1 = 0;		/* one char back */
	s = xp->str;	/* current high water in string */
	mb_cur_max = xp->mb_cur_max;
	for (;;)
	{
		/*
		* Get next character from string.
		* If the engine proper hasn't started and the engine
		* requires a particular character to start and this
		* character isn't it, try the next one.
		*/
		for (;;)
		{
			s2 = s1;
			s1 = s;
			if (!ISONEBYTE(wc = *s++) &&
					(i = libuxre_mb2wc(&wc, s)) > 0)
				s += i;
			if (np->cur != 0 || np->beg == wc || np->beg == 0)
				break;
			if (np->beg == ROP_BOL)
			{
				if (s2 == 0 && (xp->flags & REG_NOTBOL) == 0)
					break;
				if ((xp->flags & REG_NEWLINE) == 0)
					goto nomatch;
				if (s2 != 0 && *s2 == '\n')
					break;
			}
			if (wc == '\0')
				goto nomatch;
		}
		/*
		* Start the engine by inserting a fresh initial context
		* if there's no known match as yet.  (Once some match
		* has been found, the end is near.)
		*/
		if (rmso < 0 && newctxt(np, 0, np->gp) != 0)
			goto err;
		/*
		* Walk the current Contexts list, trying each.
		* "loop" is when a new Context is to be tried,
		* "again" is when the same Context continues,
		* but wc was not yet matched.
		*/
		cp = np->cur;
	loop:;
		gp = cp->gp;
	again:;
		switch (gp->op)
		{
		case ROP_BRACE: /* gp->next->op == ROP_MTOR */
			brace = gp;
			gp = gp->next;
			goto mtor;
		case ROP_MTOR:
			brace = 0;
		mtor:;
			if (cp->wasgp != gp) /* first time */
			{
				if (mkstck(np, cp, gp) != 0)
					goto err;
			}
			else if (cp->str == s) /* spinning */
				goto poptonext;
			cp->str = s;
			if (brace != 0)
			{
				if (cp->cnt >= brace->alt.info.num[1])
					goto poptonext;
				if (++cp->cnt <= brace->alt.info.num[0])
				{
					gp = gp->alt.ptr;
					goto again;
				}
				if (cp->cnt > BRACE_MAX)
					cp->cnt = BRACE_MAX;
			}
			if (newctxt(np, cp, gp->alt.ptr) != 0)
				goto err;
		poptonext:;
			cp->wasgp = 0;
			if ((sp = cp->sp) != 0) /* pop stack */
			{
				cp->sp = sp->prev;
				cp->wasgp = sp->wasgp;
				cp->str = sp->str;
				cp->cnt = sp->cnt;
				sp->prev = np->sp;
				np->sp = sp;
			}
			/*FALLTHROUGH*/
		case ROP_EMPTY:
		tonext:;
			gp = gp->next;
			goto again;
		case ROP_OR:
			if (newctxt(np, cp, gp->alt.ptr) != 0)
				goto err;
			goto tonext;
		case ROP_LP:
			if ((n = gp->alt.info.sub) < np->used)
			{
				size_t k;

				cp->rm[n].rm_so = s1 - xp->str;
				cp->rm[n].rm_eo = -1;
				/*
				* Mark any skipped subexpressions as
				* failing to participate in the match.
				*/
				if ((k = cp->nset) < n)
				{
					regmatch_t *rmp = &cp->rm[k];

					for (;; rmp++)
					{
						rmp->rm_so = -1;
						rmp->rm_eo = -1;
						if (++k >= n)
							break;
					}
				}
				cp->nset = n + 1;
			}
			goto tonext;
		case ROP_RP:
			if ((n = gp->alt.info.sub) < np->used)
				cp->rm[n].rm_eo = s1 - xp->str;
			goto tonext;
		case ROP_BOL:
			if (s2 == 0)
			{
				if (xp->flags & REG_NOTBOL)
					goto failed;
			}
			else if ((xp->flags & REG_NEWLINE) == 0 || *s2 != '\n')
				goto failed;
			goto tonext;
		case ROP_EOL:
			if (wc == '\0')
			{
				if (xp->flags & REG_NOTEOL)
					goto failed;
			}
			else if ((xp->flags & REG_NEWLINE) == 0 || wc != '\n')
				goto failed;
			goto tonext;
		default:	/* character match */
			if (gp->op != wc)
			{
				if ((xp->flags & REG_ICASE) == 0
					|| gp->op != to_lower(wc))
				{
					goto failed;
				}
			}
		nextwc:;
			cp->gp = gp->next;
		tostep:;
			cpn = cp->next;
			cp->next = 0;
			*np->estp = cp;
			np->estp = &cp->next;
			if ((cp = cpn) == 0)
				break;
			goto loop;
		case ROP_NOTNL:
			if (wc == '\n')
				goto failed;
			/*FALLTHROUGH*/
		case ROP_ANYCH:
			if (wc > '\0')
				goto nextwc;
			/*FALLTHROUGH*/
		case ROP_NONE:
		failed:;
			cpn = cp->next;
			cp->next = np->avail;
			np->avail = cp;
			if ((cp = cpn) == 0)
				break;
			goto loop;
		case ROP_LT:
			if (s2 == 0)
			{
				if (xp->flags & REG_NOTBOL)
					goto failed;
			}
			else
			{
				w_type pwc;

				if (wc != '_' &&
				    !iswalnum(mb_cur_max == 1 ? btowc(wc) : wc))
					goto failed;
				if (!ISONEBYTE(pwc = *s2))
					libuxre_mb2wc(&pwc, &s2[1]);
				if (pwc == '_' ||
				    iswalnum(mb_cur_max== 1 ? btowc(pwc) : pwc))
					goto failed;
			}
			goto tonext;
		case ROP_GT:
			if (wc == '_' ||
			    iswalnum(mb_cur_max == 1 ? btowc(wc) : wc))
				goto failed;
			goto tonext;
		case ROP_BKT:
		case ROP_BKTCOPY:
			if (cp->wasgp == gp) /* rest of MCCE */
			{
			checkspin:;
				if (s1 >= cp->str) /* got it all */
					goto poptonext;
				goto tostep;
			}
			if ((i = libuxre_bktmbexec(gp->alt.info.bkt, wc, s,
							mb_cur_max)) < 0)
				goto failed;
			if ((n = i) == 0)	/* only matched wc */
				goto nextwc;
		spin:;
			if (mkstck(np, cp, gp) != 0)
				goto err;
			cp->gp = gp;	/* stay here until reach past s+n */
			cp->str = s + n;
			goto tostep;
		case ROP_REF:
			if (cp->wasgp == gp)	/* rest of matched string */
				goto checkspin;
			if ((n = gp->alt.info.sub) >= cp->nset)
				goto failed;
			if ((len = cp->rm[n].rm_eo) < 0)
				goto failed;
			if ((len -= n = cp->rm[n].rm_so) == 0)
				goto tonext;
			if (casecmp(s1, xp, n, len, mb_cur_max) == 0)
				goto failed;
			if ((n = s - s1) >= len)
				goto nextwc;
			n = len - n;
			goto spin;
		case ROP_END:	/* success! */
			if (xp->flags & REG_NONEMPTY)
			{
				if (s2 == 0)
					goto failed;
			}
			if (xp->nmatch == 0)
				goto match;
			/*
			* Mark any skipped subexpressions as failing to match.
			*/
			if ((n = cp->nset) < xp->nmatch)
			{
				do
				{
					cp->rm[n].rm_so = -1;
					cp->rm[n].rm_eo = -1;
				} while (++n < xp->nmatch);
			}
			/*
			* Note the left-most match that's longest.
			*/
			n = cp->rm[0].rm_so;
			if (rmso < 0 || n < rmso)
			{
				rmso = n;
			record:;
				memcpy(xp->match, cp->rm,
					xp->nmatch * sizeof(regmatch_t));
				goto failed;
			}
			if (rmso < n || xp->match[0].rm_eo > cp->rm[0].rm_eo)
				goto failed;
			if (xp->match[0].rm_eo < cp->rm[0].rm_eo)
				goto record;
#if 0 /* maximize the lengths of earlier LP...RPs */
			/*
			* If both are of the same length and start
			* at the same point, choose the one with
			* a "longest submatch from left to right"
			* where an empty string wins over a nonmatch.
			*/
			for (n = 1; n < xp->nmatch; n++)
			{
				ssize_t nlen;

				/*
				* First, go with the choice that has any
				* match for subexpr n.
				*/
				len = xp->match[n].rm_eo;
				nlen = cp->rm[n].rm_eo;
				if (nlen < 0)
				{
					if (len >= 0)
						break;
				}
				else if (len < 0)
					goto record;
				/*
				* Both have a match; go with the longer.
				*/
				len -= xp->match[n].rm_so;
				nlen -= cp->rm[n].rm_so;
				if (nlen < len)
					break;
				if (nlen > len)
					goto record;
			}
#else /* take LP and RP as "fence posts" and maximize earlier gaps */
			/*
			* If both are of the same length and start
			* at the same point, choose the one with
			* the larger earlier subpatterns, in which
			* each rm_so and rm_eo serves as a separator.
			*/
			for (n = 1; n < xp->nmatch; n++)
			{
				ssize_t nlen;
				int	use;

				if (xp->flags & REG_AVOIDNULL) {
					/*
					* This is to to satisfy POSIX.1-2001
					* XBD pp. 172-173 ll. 6127-6129, whose
					* translation is "do not match null
					* expressions if there is a choice".
					* See also POSIX.2 interpretation #43
					* in which the question was raised.
					*
					* The first subexpression of "\(x*\)*"
					* must thus match the string "xxx".
					*/
					use = cp->rm[n].rm_eo -
							cp->rm[n].rm_so >=
						xp->match[n].rm_eo -
							xp->match[n].rm_so ||
						xp->match[n].rm_so < 0;
				} else
					use = 1;
				/*
				* Choose the rightmost ROP_LP as that
				* maximizes the gap from before.
				*/
				len = xp->match[n].rm_so;
				nlen = cp->rm[n].rm_so;
				if (len < nlen && use)
					goto record;
				if (len > nlen)
					break;
				/*
				* The ROP_LPs are at the same point:
				* Choose the rightmost ROP_RP.
				*/
				len = xp->match[n].rm_eo;
				nlen = cp->rm[n].rm_eo;
				if (len < nlen && use)
					goto record;
				if (len > nlen)
					break;
			}
#endif
			goto failed;
		}
		/*
		* Finished the current Context list.  If the input string
		* has been entirely scanned, we're done.  Otherwise, make
		* the next step list current for the next character.
		* If the next step list was empty and there's an existing
		* match, that's the left-most longest.
		*/
		if (wc == '\0')
		{
			if (rmso >= 0)
				goto match;
			goto nomatch;
		}
		np->ecur = np->estp;
		if ((np->cur = np->step) == 0)
		{
			if (rmso >= 0)
				goto match;
			np->ecur = &np->cur; /* was pointing at step */
		}
		np->step = 0;
		np->estp = &np->step;
	}
nomatch:;
	ret = REG_NOMATCH;
match:;
	np->avail = 0;
	for (cp = np->allcp; cp != 0; cp = cpn)
	{
		cpn = cp->link;
		cp->next = np->avail;
		np->avail = cp;
	}
	np->sp = 0;
	for (sp = np->allsp; sp != 0; sp = spn)
	{
		spn = sp->link;
		sp->prev = np->sp;
		np->sp = sp;
	}
	return ret;
err:;
	ret = REG_ESPACE;
	goto match;
}