1da2e3ebchin/***********************************************************************
2da2e3ebchin*                                                                      *
3da2e3ebchin*               This software is part of the ast package               *
43e14f97Roger A. Faulkner*          Copyright (c) 1985-2010 AT&T Intellectual Property          *
5da2e3ebchin*                      and is licensed under the                       *
6da2e3ebchin*                  Common Public License, Version 1.0                  *
77c2fbfbApril Chin*                    by AT&T Intellectual Property                     *
8da2e3ebchin*                                                                      *
9da2e3ebchin*                A copy of the License is available at                 *
10da2e3ebchin*            http://www.opensource.org/licenses/cpl1.0.txt             *
11da2e3ebchin*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
12da2e3ebchin*                                                                      *
13da2e3ebchin*              Information and Software Systems Research               *
14da2e3ebchin*                            AT&T Research                             *
15da2e3ebchin*                           Florham Park NJ                            *
16da2e3ebchin*                                                                      *
17da2e3ebchin*                 Glenn Fowler <gsf@research.att.com>                  *
18da2e3ebchin*                  David Korn <dgk@research.att.com>                   *
19da2e3ebchin*                   Phong Vo <kpv@research.att.com>                    *
20da2e3ebchin*                                                                      *
21da2e3ebchin***********************************************************************/
22da2e3ebchin#pragma prototyped
23da2e3ebchin
24da2e3ebchin/*
25da2e3ebchin * posix regex executor
26da2e3ebchin * single sized-record interface
27da2e3ebchin */
28da2e3ebchin
29da2e3ebchin#include "reglib.h"
30da2e3ebchin
31da2e3ebchin#if _AST_REGEX_DEBUG
32da2e3ebchin
33da2e3ebchin#define DEBUG_TEST(f,y,n)	((debug&(debug_flag=f))?(y):(n))
34da2e3ebchin#define DEBUG_CODE(f,y,n)	do if(debug&(f)){y}else{n} while(0)
35da2e3ebchin#define DEBUG_INIT()		do { char* t; if (!debug) { debug = 0x80000000; if (t = getenv("_AST_regex_exec_debug")) debug |= strtoul(t, NiL, 0); } } while (0)
36da2e3ebchin
37da2e3ebchinstatic unsigned long	debug;
38da2e3ebchinstatic unsigned long	debug_flag;
39da2e3ebchin
40da2e3ebchinstatic const char*	rexnames[] =
41da2e3ebchin{
42da2e3ebchin	"REX_NULL",
43da2e3ebchin	"REX_ALT",
44da2e3ebchin	"REX_ALT_CATCH",
45da2e3ebchin	"REX_BACK",
46da2e3ebchin	"REX_BEG",
47da2e3ebchin	"REX_BEG_STR",
48da2e3ebchin	"REX_BM",
49da2e3ebchin	"REX_CAT",
50da2e3ebchin	"REX_CLASS",
51da2e3ebchin	"REX_COLL_CLASS",
52da2e3ebchin	"REX_CONJ",
53da2e3ebchin	"REX_CONJ_LEFT",
54da2e3ebchin	"REX_CONJ_RIGHT",
55da2e3ebchin	"REX_DONE",
56da2e3ebchin	"REX_DOT",
57da2e3ebchin	"REX_END",
58da2e3ebchin	"REX_END_STR",
59da2e3ebchin	"REX_EXEC",
60da2e3ebchin	"REX_FIN_STR",
61da2e3ebchin	"REX_GROUP",
62da2e3ebchin	"REX_GROUP_CATCH",
63da2e3ebchin	"REX_GROUP_AHEAD",
64da2e3ebchin	"REX_GROUP_AHEAD_CATCH",
65da2e3ebchin	"REX_GROUP_AHEAD_NOT",
66da2e3ebchin	"REX_GROUP_BEHIND",
67da2e3ebchin	"REX_GROUP_BEHIND_CATCH",
68da2e3ebchin	"REX_GROUP_BEHIND_NOT",
69da2e3ebchin	"REX_GROUP_BEHIND_NOT_CATCH",
70da2e3ebchin	"REX_GROUP_COND",
71da2e3ebchin	"REX_GROUP_COND_CATCH",
72da2e3ebchin	"REX_GROUP_CUT",
73da2e3ebchin	"REX_GROUP_CUT_CATCH",
74da2e3ebchin	"REX_KMP",
75da2e3ebchin	"REX_NEG",
76da2e3ebchin	"REX_NEG_CATCH",
77da2e3ebchin	"REX_NEST",
78da2e3ebchin	"REX_ONECHAR",
79da2e3ebchin	"REX_REP",
80da2e3ebchin	"REX_REP_CATCH",
81da2e3ebchin	"REX_STRING",
82da2e3ebchin	"REX_TRIE",
83da2e3ebchin	"REX_WBEG",
84da2e3ebchin	"REX_WEND",
85da2e3ebchin	"REX_WORD",
86da2e3ebchin	"REX_WORD_NOT"
87da2e3ebchin};
88da2e3ebchin
89da2e3ebchinstatic const char* rexname(Rex_t* rex)
90da2e3ebchin{
91da2e3ebchin	if (!rex)
92da2e3ebchin		return "NIL";
93da2e3ebchin	if (rex->type >= elementsof(rexnames))
94da2e3ebchin		return "ERROR";
95da2e3ebchin	return rexnames[rex->type];
96da2e3ebchin}
97da2e3ebchin
98da2e3ebchin#else
99da2e3ebchin
100da2e3ebchin#define DEBUG_INIT()
101da2e3ebchin#define DEBUG_TEST(f,y,n)	(n)
102da2e3ebchin#define DEBUG_CODE(f,y,n)	do {n} while(0)
103da2e3ebchin
104da2e3ebchin#endif
105da2e3ebchin
106da2e3ebchin#define BEG_ALT		1	/* beginning of an alt			*/
107da2e3ebchin#define BEG_ONE		2	/* beginning of one iteration of a rep	*/
108da2e3ebchin#define BEG_REP		3	/* beginning of a repetition		*/
109da2e3ebchin#define BEG_SUB		4	/* beginning of a subexpression		*/
110da2e3ebchin#define END_ANY		5	/* end of any of above			*/
111da2e3ebchin
112da2e3ebchin/*
113da2e3ebchin * returns from parse()
114da2e3ebchin */
115da2e3ebchin
116da2e3ebchin#define NONE		0	/* no parse found			*/
117da2e3ebchin#define GOOD		1	/* some parse was found			*/
118da2e3ebchin#define CUT		2	/* no match and no backtrack		*/
119da2e3ebchin#define BEST		3	/* an unbeatable parse was found	*/
120da2e3ebchin#define BAD		4	/* error ocurred			*/
121da2e3ebchin
122da2e3ebchin/*
123da2e3ebchin * REG_SHELL_DOT test
124da2e3ebchin */
125da2e3ebchin
126da2e3ebchin#define LEADING(e,r,s)	(*(s)==(e)->leading&&((s)==(e)->beg||*((s)-1)==(r)->explicit))
127da2e3ebchin
128da2e3ebchin/*
129da2e3ebchin * Pos_t is for comparing parses. An entry is made in the
130da2e3ebchin * array at the beginning and at the end of each Group_t,
131da2e3ebchin * each iteration in a Group_t, and each Binary_t.
132da2e3ebchin */
133da2e3ebchin
134da2e3ebchintypedef struct
135da2e3ebchin{
136da2e3ebchin	unsigned char*	p;		/* where in string		*/
137da2e3ebchin	size_t		length;		/* length in string		*/
138da2e3ebchin	short		serial;		/* preorder subpattern number	*/
139da2e3ebchin	short		be;		/* which end of pair		*/
140da2e3ebchin} Pos_t;
141da2e3ebchin
142da2e3ebchin/* ===== begin library support ===== */
143da2e3ebchin
144da2e3ebchin#define vector(t,v,i)	(((i)<(v)->max)?(t*)((v)->vec+(i)*(v)->siz):(t*)vecseek(&(v),i))
145da2e3ebchin
146da2e3ebchinstatic Vector_t*
147da2e3ebchinvecopen(int inc, int siz)
148da2e3ebchin{
149da2e3ebchin	Vector_t*	v;
150da2e3ebchin	Stk_t*		sp;
151da2e3ebchin
152da2e3ebchin	if (inc <= 0)
153da2e3ebchin		inc = 16;
154da2e3ebchin	if (!(sp = stkopen(STK_SMALL|STK_NULL)))
155da2e3ebchin		return 0;
156da2e3ebchin	if (!(v = (Vector_t*)stkseek(sp, sizeof(Vector_t) + inc * siz)))
157da2e3ebchin	{
158da2e3ebchin		stkclose(sp);
159da2e3ebchin		return 0;
160da2e3ebchin	}
161da2e3ebchin	v->stk = sp;
162da2e3ebchin	v->vec = (char*)v + sizeof(Vector_t);
163da2e3ebchin	v->max = v->inc = inc;
164da2e3ebchin	v->siz = siz;
165da2e3ebchin	v->cur = 0;
166da2e3ebchin	return v;
167da2e3ebchin}
168da2e3ebchin
169da2e3ebchinstatic void*
170da2e3ebchinvecseek(Vector_t** p, int index)
171da2e3ebchin{
172da2e3ebchin	Vector_t*	v = *p;
173da2e3ebchin
174da2e3ebchin	if (index >= v->max)
175da2e3ebchin	{
176da2e3ebchin		while ((v->max += v->inc) <= index);
177da2e3ebchin		if (!(v = (Vector_t*)stkseek(v->stk, sizeof(Vector_t) + v->max * v->siz)))
178da2e3ebchin			return 0;
179da2e3ebchin		*p = v;
180da2e3ebchin		v->vec = (char*)v + sizeof(Vector_t);
181da2e3ebchin	}
182da2e3ebchin	return v->vec + index * v->siz;
183da2e3ebchin}
184da2e3ebchin
185da2e3ebchinstatic void
186da2e3ebchinvecclose(Vector_t* v)
187da2e3ebchin{
188da2e3ebchin	if (v)
189da2e3ebchin		stkclose(v->stk);
190da2e3ebchin}
191da2e3ebchin
192da2e3ebchintypedef struct
193da2e3ebchin{
194da2e3ebchin	Stk_pos_t	pos;
195da2e3ebchin	char		data[1];
196da2e3ebchin} Stk_frame_t;
197da2e3ebchin
198da2e3ebchin#define stknew(s,p)	((p)->offset=stktell(s),(p)->base=stkfreeze(s,0))
199da2e3ebchin#define stkold(s,p)	stkset(s,(p)->base,(p)->offset)
200da2e3ebchin
201da2e3ebchin#define stkframe(s)	(*((Stk_frame_t**)stktop(s)-1))
202da2e3ebchin#define stkdata(s,t)	((t*)stkframe(s)->data)
203da2e3ebchin#define stkpop(s)	stkold(s,&(stkframe(s)->pos))
204da2e3ebchin
205da2e3ebchinstatic void*
206da2e3ebchinstkpush(Stk_t* sp, size_t size)
207da2e3ebchin{
208da2e3ebchin	Stk_frame_t*	f;
209da2e3ebchin	Stk_pos_t	p;
210da2e3ebchin
211da2e3ebchin	stknew(sp, &p);
212da2e3ebchin	size = sizeof(Stk_frame_t) + sizeof(size_t) + size - 1;
213da2e3ebchin	if (!(f = (Stk_frame_t*)stkalloc(sp, sizeof(Stk_frame_t) + sizeof(Stk_frame_t*) + size - 1)))
214da2e3ebchin		return 0;
215da2e3ebchin	f->pos = p;
216da2e3ebchin	stkframe(sp) = f;
217da2e3ebchin	return f->data;
218da2e3ebchin}
219da2e3ebchin
220da2e3ebchin/* ===== end library support ===== */
221da2e3ebchin
222da2e3ebchin/*
223da2e3ebchin * Match_frame_t is for saving and restoring match records
224da2e3ebchin * around alternate attempts, so that fossils will not be
225da2e3ebchin * left in the match array.  These are the only entries in
226da2e3ebchin * the match array that are not otherwise guaranteed to
227da2e3ebchin * have current data in them when they get used.
228da2e3ebchin */
229da2e3ebchin
230da2e3ebchintypedef struct
231da2e3ebchin{
232da2e3ebchin	size_t			size;
233da2e3ebchin	regmatch_t*		match;
234da2e3ebchin	regmatch_t		save[1];
235da2e3ebchin} Match_frame_t;
236da2e3ebchin
237da2e3ebchin#define matchframe	stkdata(stkstd,Match_frame_t)
238da2e3ebchin#define matchpush(e,x)	((x)->re.group.number?_matchpush(e,x):0)
239da2e3ebchin#define matchcopy(e,x)	((x)->re.group.number?memcpy(matchframe->match,matchframe->save,matchframe->size):(void*)0)
240da2e3ebchin#define matchpop(e,x)	((x)->re.group.number?memcpy(matchframe->match,matchframe->save,matchframe->size),stkpop(stkstd):(void*)0)
241da2e3ebchin
242da2e3ebchin#define pospop(e)	(--(e)->pos->cur)
243da2e3ebchin
244da2e3ebchin/*
245da2e3ebchin * allocate a frame and push a match onto the stack
246da2e3ebchin */
247da2e3ebchin
248da2e3ebchinstatic int
249da2e3ebchin_matchpush(Env_t* env, Rex_t* rex)
250da2e3ebchin{
251da2e3ebchin	Match_frame_t*	f;
252da2e3ebchin	regmatch_t*	m;
253da2e3ebchin	regmatch_t*	e;
254da2e3ebchin	regmatch_t*	s;
255da2e3ebchin	int		num;
256da2e3ebchin
257da2e3ebchin	if (rex->re.group.number <= 0 || (num = rex->re.group.last - rex->re.group.number + 1) <= 0)
258da2e3ebchin		num = 0;
259da2e3ebchin	if (!(f = (Match_frame_t*)stkpush(stkstd, sizeof(Match_frame_t) + (num - 1) * sizeof(regmatch_t))))
260da2e3ebchin	{
261da2e3ebchin		env->error = REG_ESPACE;
262da2e3ebchin		return 1;
263da2e3ebchin	}
264da2e3ebchin	f->size = num * sizeof(regmatch_t);
265da2e3ebchin	f->match = m = env->match + rex->re.group.number;
266da2e3ebchin	e = m + num;
267da2e3ebchin	s = f->save;
268da2e3ebchin	while (m < e)
269da2e3ebchin	{
270da2e3ebchin		*s++ = *m;
271da2e3ebchin		*m++ = state.nomatch;
272da2e3ebchin	}
273da2e3ebchin	return 0;
274da2e3ebchin}
275da2e3ebchin
276da2e3ebchin/*
277da2e3ebchin * allocate a frame and push a pos onto the stack
278da2e3ebchin */
279da2e3ebchin
280da2e3ebchinstatic int
281da2e3ebchinpospush(Env_t* env, Rex_t* rex, unsigned char* p, int be)
282da2e3ebchin{
283da2e3ebchin	Pos_t*	pos;
284da2e3ebchin
285da2e3ebchin	if (!(pos = vector(Pos_t, env->pos, env->pos->cur)))
286da2e3ebchin	{
287da2e3ebchin		env->error = REG_ESPACE;
288da2e3ebchin		return 1;
289da2e3ebchin	}
290da2e3ebchin	pos->serial = rex->serial;
291da2e3ebchin	pos->p = p;
292da2e3ebchin	pos->be = be;
293da2e3ebchin	env->pos->cur++;
294da2e3ebchin	return 0;
295da2e3ebchin}
296da2e3ebchin
297da2e3ebchin/*
298da2e3ebchin * two matches are known to have the same length
299da2e3ebchin * os is start of old pos array, ns is start of new,
300da2e3ebchin * oend and nend are end+1 pointers to ends of arrays.
301da2e3ebchin * oe and ne are ends (not end+1) of subarrays.
302da2e3ebchin * returns 1 if new is better, -1 if old, else 0.
303da2e3ebchin */
304da2e3ebchin
305da2e3ebchinstatic int
306da2e3ebchinbetter(Env_t* env, Pos_t* os, Pos_t* ns, Pos_t* oend, Pos_t* nend, int level)
307da2e3ebchin{
308da2e3ebchin	Pos_t*	oe;
309da2e3ebchin	Pos_t*	ne;
310da2e3ebchin	int	k;
311da2e3ebchin	int	n;
312da2e3ebchin
313da2e3ebchin	if (env->error)
314da2e3ebchin		return -1;
315da2e3ebchin	for (;;)
316da2e3ebchin	{
317da2e3ebchin		DEBUG_CODE(0x0080,{sfprintf(sfstdout, "   %-*.*sold ", (level + 3) * 4, (level + 3) * 4, "");for (oe = os; oe < oend; oe++)sfprintf(sfstdout, "<%d,%d,%d>", oe->p - env->beg, oe->serial, oe->be);sfprintf(sfstdout, "\n   %-*.*snew ", (level + 3) * 4, (level + 3) * 4, "");for (oe = ns; oe < nend; oe++)sfprintf(sfstdout, "<%d,%d,%d>", oe->p - env->beg, oe->serial, oe->be);sfprintf(sfstdout, "\n");},{0;});
318da2e3ebchin		if (ns >= nend)
319da2e3ebchin			return DEBUG_TEST(0x8000,(os < oend),(0));
320da2e3ebchin		if (os >= oend)
321da2e3ebchin			return DEBUG_TEST(0x8000,(-1),(1));
322da2e3ebchin		n = os->serial;
323da2e3ebchin		if (ns->serial > n)
324da2e3ebchin			return -1;
325da2e3ebchin		if (n > ns->serial)
326da2e3ebchin		{
327da2e3ebchin			env->error = REG_PANIC;
328da2e3ebchin			return -1;
329da2e3ebchin		}
330da2e3ebchin		if (ns->p > os->p)
331da2e3ebchin			return 1;
332da2e3ebchin		if (os->p > ns->p)
333da2e3ebchin			return -1;
334da2e3ebchin		oe = os;
335da2e3ebchin		k = 0;
336da2e3ebchin		for (;;)
337da2e3ebchin			if ((++oe)->serial == n)
338da2e3ebchin			{
339da2e3ebchin				if (oe->be != END_ANY)
340da2e3ebchin					k++;
341da2e3ebchin				else if (k-- <= 0)
342da2e3ebchin					break;
343da2e3ebchin			}
344da2e3ebchin		ne = ns;
345da2e3ebchin		k = 0;
346da2e3ebchin		for (;;)
347da2e3ebchin			if ((++ne)->serial == n)
348da2e3ebchin			{
349da2e3ebchin				if (ne->be != END_ANY)
350da2e3ebchin					k++;
351da2e3ebchin				else if (k-- <= 0)
352da2e3ebchin					break;
353da2e3ebchin			}
354da2e3ebchin		if (ne->p > oe->p)
355da2e3ebchin			return 1;
356da2e3ebchin		if (oe->p > ne->p)
357da2e3ebchin			return -1;
358da2e3ebchin		if (k = better(env, os + 1, ns + 1, oe, ne, level + 1))
359da2e3ebchin			return k;
360da2e3ebchin		os = oe + 1;
361da2e3ebchin		ns = ne + 1;
362da2e3ebchin	}
363da2e3ebchin}
364da2e3ebchin
3657c2fbfbApril Chin#if _AST_REGEX_DEBUG
3667c2fbfbApril Chin
3677c2fbfbApril Chinstatic void
3687c2fbfbApril Chinshowmatch(regmatch_t* p)
3697c2fbfbApril Chin{
3707c2fbfbApril Chin	sfputc(sfstdout, '(');
3717c2fbfbApril Chin	if (p->rm_so < 0)
3727c2fbfbApril Chin		sfputc(sfstdout, '?');
3737c2fbfbApril Chin	else
3747c2fbfbApril Chin		sfprintf(sfstdout, "%d", p->rm_so);
3757c2fbfbApril Chin	sfputc(sfstdout, ',');
3767c2fbfbApril Chin	if (p->rm_eo < 0)
3777c2fbfbApril Chin		sfputc(sfstdout, '?');
3787c2fbfbApril Chin	else
3797c2fbfbApril Chin		sfprintf(sfstdout, "%d", p->rm_eo);
3807c2fbfbApril Chin	sfputc(sfstdout, ')');
3817c2fbfbApril Chin}
3827c2fbfbApril Chin
3837c2fbfbApril Chinstatic int
3847c2fbfbApril Chin_better(Env_t* env, Pos_t* os, Pos_t* ns, Pos_t* oend, Pos_t* nend, int level)
3857c2fbfbApril Chin{
3867c2fbfbApril Chin	int	i;
3877c2fbfbApril Chin
3887c2fbfbApril Chin	DEBUG_CODE(0x0040,{sfprintf(sfstdout, "AHA better old ");for (i = 0; i <= env->nsub; i++)showmatch(&env->best[i]);sfprintf(sfstdout, "\n           new ");for (i = 0; i <= env->nsub; i++)showmatch(&env->match[i]);sfprintf(sfstdout, "\n");},{0;});
3897c2fbfbApril Chin	i = better(env, os, ns, oend, nend, 0);
3907c2fbfbApril Chin	DEBUG_TEST(0x0040,(sfprintf(sfstdout, "           %s\n", i <= 0 ? "OLD" : "NEW")),(0));
3917c2fbfbApril Chin	return i;
3927c2fbfbApril Chin}
3937c2fbfbApril Chin
3947c2fbfbApril Chin#define better	_better
3957c2fbfbApril Chin
3967c2fbfbApril Chin#endif
397da2e3ebchin
398da2e3ebchin#define follow(e,r,c,s)	((r)->next?parse(e,(r)->next,c,s):(c)?parse(e,c,0,s):BEST)
399da2e3ebchin
400da2e3ebchinstatic int		parse(Env_t*, Rex_t*, Rex_t*, unsigned char*);
401da2e3ebchin
402da2e3ebchinstatic int
403da2e3ebchinparserep(Env_t* env, Rex_t* rex, Rex_t* cont, unsigned char* s, int n)
404da2e3ebchin{
405da2e3ebchin	int	i;
406da2e3ebchin	int	r = NONE;
407da2e3ebchin	Rex_t	catcher;
408da2e3ebchin
40934f9b3eRoland Mainz	DEBUG_TEST(0x0010,(sfprintf(sfstdout, "AHA#%04d 0x%04x parserep %s %d %d %d %d `%-.*s'\n", __LINE__, debug_flag, rexname(rex->re.group.expr.rex), rex->re.group.number, rex->lo, n, rex->hi, env->end - s, s)),(0));
410da2e3ebchin	if ((rex->flags & REG_MINIMAL) && n >= rex->lo && n < rex->hi)
411da2e3ebchin	{
412da2e3ebchin		if (env->stack && pospush(env, rex, s, END_ANY))
413da2e3ebchin			return BAD;
414da2e3ebchin		i = follow(env, rex, cont, s);
415da2e3ebchin		if (env->stack)
416da2e3ebchin			pospop(env);
417da2e3ebchin		switch (i)
418da2e3ebchin		{
419da2e3ebchin		case BAD:
420da2e3ebchin			return BAD;
421da2e3ebchin		case CUT:
422da2e3ebchin			return CUT;
423da2e3ebchin		case BEST:
424da2e3ebchin		case GOOD:
425da2e3ebchin			return BEST;
426da2e3ebchin		}
427da2e3ebchin	}
428da2e3ebchin	if (n < rex->hi)
429da2e3ebchin	{
430da2e3ebchin		catcher.type = REX_REP_CATCH;
431da2e3ebchin		catcher.serial = rex->serial;
432da2e3ebchin		catcher.re.rep_catch.ref = rex;
433da2e3ebchin		catcher.re.rep_catch.cont = cont;
434da2e3ebchin		catcher.re.rep_catch.beg = s;
435da2e3ebchin		catcher.re.rep_catch.n = n + 1;
436da2e3ebchin		catcher.next = rex->next;
437da2e3ebchin		if (n == 0)
438da2e3ebchin			rex->re.rep_catch.beg = s;
439da2e3ebchin		if (env->stack)
440da2e3ebchin		{
441da2e3ebchin			if (matchpush(env, rex))
442da2e3ebchin				return BAD;
443da2e3ebchin			if (pospush(env, rex, s, BEG_ONE))
444da2e3ebchin				return BAD;
44534f9b3eRoland MainzDEBUG_TEST(0x0004,(sfprintf(sfstdout,"AHA#%04d 0x%04x PUSH %d   (%d,%d)(%d,%d)(%d,%d) (%d,%d)(%d,%d)(%d,%d)\n", __LINE__, debug_flag, rex->re.group.number, env->best[0].rm_so, env->best[0].rm_eo, env->best[1].rm_so, env->best[1].rm_eo, env->best[2].rm_so, env->best[2].rm_eo, env->match[0].rm_so, env->match[0].rm_eo, env->match[1].rm_so, env->match[1].rm_eo, env->match[2].rm_so, env->match[2].rm_eo)),(0));
446da2e3ebchin		}
447da2e3ebchin		r = parse(env, rex->re.group.expr.rex, &catcher, s);
44834f9b3eRoland Mainz		DEBUG_TEST(0x0010,(sfprintf(sfstdout, "AHA#%04d 0x%04x parserep parse %d %d `%-.*s'\n", __LINE__, debug_flag, rex->re.group.number, r, env->end - s, s)),(0));
449da2e3ebchin		if (env->stack)
450da2e3ebchin		{
451da2e3ebchin			pospop(env);
452da2e3ebchin			matchpop(env, rex);
45334f9b3eRoland MainzDEBUG_TEST(0x0004,(sfprintf(sfstdout,"AHA#%04d 0x%04x POP  %d %d (%d,%d)(%d,%d)(%d,%d) (%d,%d)(%d,%d)(%d,%d)\n", __LINE__, debug_flag, rex->re.group.number, r, env->best[0].rm_so, env->best[0].rm_eo, env->best[1].rm_so, env->best[1].rm_eo, env->best[2].rm_so, env->best[2].rm_eo, env->match[0].rm_so, env->match[0].rm_eo, env->match[1].rm_so, env->match[1].rm_eo, env->match[2].rm_so, env->match[2].rm_eo)),(0));
454da2e3ebchin		}
455da2e3ebchin		switch (r)
456da2e3ebchin		{
457da2e3ebchin		case BAD:
458da2e3ebchin			return BAD;
459da2e3ebchin		case BEST:
460da2e3ebchin			return BEST;
461da2e3ebchin		case CUT:
462da2e3ebchin			r = NONE;
463da2e3ebchin			break;
464da2e3ebchin		case GOOD:
465da2e3ebchin			if (rex->flags & REG_MINIMAL)
466da2e3ebchin				return BEST;
467da2e3ebchin			r = GOOD;
468da2e3ebchin			break;
469da2e3ebchin		}
470da2e3ebchin	}
471da2e3ebchin	if (n < rex->lo)
472da2e3ebchin		return r;
473da2e3ebchin	if (!(rex->flags & REG_MINIMAL) || n >= rex->hi)
474da2e3ebchin	{
475da2e3ebchin		if (env->stack && pospush(env, rex, s, END_ANY))
476da2e3ebchin			return BAD;
477da2e3ebchin		i = follow(env, rex, cont, s);
478da2e3ebchin		if (env->stack)
479da2e3ebchin			pospop(env);
480da2e3ebchin		switch (i)
481da2e3ebchin		{
482da2e3ebchin		case BAD:
483da2e3ebchin			r = BAD;
484da2e3ebchin			break;
485da2e3ebchin		case CUT:
486da2e3ebchin			r = CUT;
487da2e3ebchin			break;
488da2e3ebchin		case BEST:
489da2e3ebchin			r = BEST;
490da2e3ebchin			break;
491da2e3ebchin		case GOOD:
492da2e3ebchin			r = (rex->flags & REG_MINIMAL) ? BEST : GOOD;
493da2e3ebchin			break;
494da2e3ebchin		}
495da2e3ebchin	}
496da2e3ebchin	return r;
497da2e3ebchin}
498da2e3ebchin
499da2e3ebchinstatic int
500da2e3ebchinparsetrie(Env_t* env, Trie_node_t* x, Rex_t* rex, Rex_t* cont, unsigned char* s)
501da2e3ebchin{
502da2e3ebchin	unsigned char*	p;
503da2e3ebchin	int		r;
504da2e3ebchin
505da2e3ebchin	if (p = rex->map)
506da2e3ebchin	{
507da2e3ebchin		for (;;)
508da2e3ebchin		{
509da2e3ebchin			if (s >= env->end)
510da2e3ebchin				return NONE;
511da2e3ebchin			while (x->c != p[*s])
512da2e3ebchin				if (!(x = x->sib))
513da2e3ebchin					return NONE;
514da2e3ebchin			if (x->end)
515da2e3ebchin				break;
516da2e3ebchin			x = x->son;
517da2e3ebchin			s++;
518da2e3ebchin		}
519da2e3ebchin	}
520da2e3ebchin	else
521da2e3ebchin	{
522da2e3ebchin		for (;;)
523da2e3ebchin		{
524da2e3ebchin			if (s >= env->end)
525da2e3ebchin				return NONE;
526da2e3ebchin			while (x->c != *s)
527da2e3ebchin				if (!(x = x->sib))
528da2e3ebchin					return NONE;
529da2e3ebchin			if (x->end)
530da2e3ebchin				break;
531da2e3ebchin			x = x->son;
532da2e3ebchin			s++;
533da2e3ebchin		}
534da2e3ebchin	}
535da2e3ebchin	s++;
536da2e3ebchin	if (rex->flags & REG_MINIMAL)
537da2e3ebchin		switch (follow(env, rex, cont, s))
538da2e3ebchin		{
539da2e3ebchin		case BAD:
540da2e3ebchin			return BAD;
541da2e3ebchin		case CUT:
542da2e3ebchin			return CUT;
543da2e3ebchin		case BEST:
544da2e3ebchin		case GOOD:
545da2e3ebchin			return BEST;
546da2e3ebchin		}
547da2e3ebchin	if (x->son)
548da2e3ebchin		switch (parsetrie(env, x->son, rex, cont, s))
549da2e3ebchin		{
550da2e3ebchin		case BAD:
551da2e3ebchin			return BAD;
552da2e3ebchin		case CUT:
553da2e3ebchin			return CUT;
554da2e3ebchin		case BEST:
555da2e3ebchin			return BEST;
556da2e3ebchin		case GOOD:
557da2e3ebchin			if (rex->flags & REG_MINIMAL)
558da2e3ebchin				return BEST;
559da2e3ebchin			r = GOOD;
560da2e3ebchin			break;
561da2e3ebchin		default:
562da2e3ebchin			r = NONE;
563da2e3ebchin			break;
564da2e3ebchin		}
565da2e3ebchin	else
566da2e3ebchin		r = NONE;
567da2e3ebchin	if (!(rex->flags & REG_MINIMAL))
568da2e3ebchin		switch (follow(env, rex, cont, s))
569da2e3ebchin		{
570da2e3ebchin		case BAD:
571da2e3ebchin			return BAD;
572