Symaptic: os/persistentdata/persistentstorage/sqlite3api/TEST/TCL/tcldistribution/generic/regexec.c@bde4ae8d615e (annotated)

sl@0	1	/*
sl@0	2	* re_*exec and friends - match REs
sl@0	3	*
sl@0	4	* Copyright (c) 1998, 1999 Henry Spencer. All rights reserved.
sl@0	5	*
sl@0	6	* Development of this software was funded, in part, by Cray Research Inc.,
sl@0	7	* UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
sl@0	8	* Corporation, none of whom are responsible for the results. The author
sl@0	9	* thanks all of them.
sl@0	10	*
sl@0	11	* Redistribution and use in source and binary forms -- with or without
sl@0	12	* modification -- are permitted for any purpose, provided that
sl@0	13	* redistributions in source form retain this entire copyright notice and
sl@0	14	* indicate the origin and nature of any modifications.
sl@0	15	*
sl@0	16	* I'd appreciate being given credit for this package in the documentation
sl@0	17	* of software which uses it, but that is not a requirement.
sl@0	18	*
sl@0	19	* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
sl@0	20	* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
sl@0	21	* AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
sl@0	22	* HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
sl@0	23	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
sl@0	24	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
sl@0	25	* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
sl@0	26	* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
sl@0	27	* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
sl@0	28	* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
sl@0	29	*
sl@0	30	*/
sl@0	31
sl@0	32	#include "regguts.h"
sl@0	33
sl@0	34
sl@0	35
sl@0	36	/* lazy-DFA representation */
sl@0	37	struct arcp { /* "pointer" to an outarc */
sl@0	38	struct sset *ss;
sl@0	39	color co;
sl@0	40	};
sl@0	41
sl@0	42	struct sset { /* state set */
sl@0	43	unsigned states; / pointer to bitvector */
sl@0	44	unsigned hash; /* hash of bitvector */
sl@0	45	# define HASH(bv, nw) (((nw) == 1) ? *(bv) : hash(bv, nw))
sl@0	46	# define HIT(h,bv,ss,nw) ((ss)->hash == (h) && ((nw) == 1 \|\| \
sl@0	47	memcmp(VS(bv), VS((ss)->states), (nw)*sizeof(unsigned)) == 0))
sl@0	48	int flags;
sl@0	49	# define STARTER 01 /* the initial state set */
sl@0	50	# define POSTSTATE 02 /* includes the goal state */
sl@0	51	# define LOCKED 04 /* locked in cache */
sl@0	52	# define NOPROGRESS 010 /* zero-progress state set */
sl@0	53	struct arcp ins; /* chain of inarcs pointing here */
sl@0	54	chr lastseen; / last entered on arrival here */
sl@0	55	struct sset *outs; / outarc vector indexed by color */
sl@0	56	struct arcp inchain; / chain-pointer vector for outarcs */
sl@0	57	};
sl@0	58
sl@0	59	struct dfa {
sl@0	60	int nssets; /* size of cache */
sl@0	61	int nssused; /* how many entries occupied yet */
sl@0	62	int nstates; /* number of states */
sl@0	63	int ncolors; /* length of outarc and inchain vectors */
sl@0	64	int wordsper; /* length of state-set bitvectors */
sl@0	65	struct sset ssets; / state-set cache */
sl@0	66	unsigned statesarea; / bitvector storage */
sl@0	67	unsigned work; / pointer to work area within statesarea */
sl@0	68	struct sset *outsarea; / outarc-vector storage */
sl@0	69	struct arcp incarea; / inchain storage */
sl@0	70	struct cnfa *cnfa;
sl@0	71	struct colormap *cm;
sl@0	72	chr lastpost; / location of last cache-flushed success */
sl@0	73	chr lastnopr; / location of last cache-flushed NOPROGRESS */
sl@0	74	struct sset search; / replacement-search-pointer memory */
sl@0	75	int cptsmalloced; /* were the areas individually malloced? */
sl@0	76	char mallocarea; / self, or master malloced area, or NULL */
sl@0	77	};
sl@0	78
sl@0	79	#define WORK 1 /* number of work bitvectors needed */
sl@0	80
sl@0	81	/* setup for non-malloc allocation for small cases */
sl@0	82	#define FEWSTATES 20 /* must be less than UBITS */
sl@0	83	#define FEWCOLORS 15
sl@0	84	struct smalldfa {
sl@0	85	struct dfa dfa;
sl@0	86	struct sset ssets[FEWSTATES*2];
sl@0	87	unsigned statesarea[FEWSTATES*2 + WORK];
sl@0	88	struct sset outsarea[FEWSTATES2 * FEWCOLORS];
sl@0	89	struct arcp incarea[FEWSTATES2 FEWCOLORS];
sl@0	90	};
sl@0	91	#define DOMALLOC ((struct smalldfa )NULL) / force malloc */
sl@0	92
sl@0	93
sl@0	94
sl@0	95	/* internal variables, bundled for easy passing around */
sl@0	96	struct vars {
sl@0	97	regex_t *re;
sl@0	98	struct guts *g;
sl@0	99	int eflags; /* copies of arguments */
sl@0	100	size_t nmatch;
sl@0	101	regmatch_t *pmatch;
sl@0	102	rm_detail_t *details;
sl@0	103	chr start; / start of string */
sl@0	104	chr stop; / just past end of string */
sl@0	105	int err; /* error code if any (0 none) */
sl@0	106	regoff_t mem; / memory vector for backtracking */
sl@0	107	struct smalldfa dfa1;
sl@0	108	struct smalldfa dfa2;
sl@0	109	};
sl@0	110	#define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */
sl@0	111	#define ISERR() VISERR(v)
sl@0	112	#define VERR(vv,e) (((vv)->err) ? (vv)->err : ((vv)->err = (e)))
sl@0	113	#define ERR(e) VERR(v, e) /* record an error */
sl@0	114	#define NOERR() {if (ISERR()) return v->err;} /* if error seen, return it */
sl@0	115	#define OFF(p) ((p) - v->start)
sl@0	116	#define LOFF(p) ((long)OFF(p))
sl@0	117
sl@0	118
sl@0	119
sl@0	120	/*
sl@0	121	* forward declarations
sl@0	122	*/
sl@0	123	/* =====^!^===== begin forwards =====^!^===== */
sl@0	124	/* automatically gathered by fwd; do not hand-edit */
sl@0	125	/* === regexec.c === */
sl@0	126	int exec _ANSI_ARGS_((regex_t , CONST chr , size_t, rm_detail_t *, size_t, regmatch_t [], int));
sl@0	127	static int find _ANSI_ARGS_((struct vars , struct cnfa , struct colormap *));
sl@0	128	static int cfind _ANSI_ARGS_((struct vars , struct cnfa , struct colormap *));
sl@0	129	static int cfindloop _ANSI_ARGS_((struct vars , struct cnfa , struct colormap , struct dfa , struct dfa , chr *));
sl@0	130	static VOID zapsubs _ANSI_ARGS_((regmatch_t *, size_t));
sl@0	131	static VOID zapmem _ANSI_ARGS_((struct vars , struct subre ));
sl@0	132	static VOID subset _ANSI_ARGS_((struct vars , struct subre , chr , chr ));
sl@0	133	static int dissect _ANSI_ARGS_((struct vars , struct subre , chr , chr ));
sl@0	134	static int condissect _ANSI_ARGS_((struct vars , struct subre , chr , chr ));
sl@0	135	static int altdissect _ANSI_ARGS_((struct vars , struct subre , chr , chr ));
sl@0	136	static int cdissect _ANSI_ARGS_((struct vars , struct subre , chr , chr ));
sl@0	137	static int ccondissect _ANSI_ARGS_((struct vars , struct subre , chr , chr ));
sl@0	138	static int crevdissect _ANSI_ARGS_((struct vars , struct subre , chr , chr ));
sl@0	139	static int cbrdissect _ANSI_ARGS_((struct vars , struct subre , chr , chr ));
sl@0	140	static int caltdissect _ANSI_ARGS_((struct vars , struct subre , chr , chr ));
sl@0	141	/* === rege_dfa.c === */
sl@0	142	static chr longest _ANSI_ARGS_((struct vars , struct dfa , chr , chr , int ));
sl@0	143	static chr shortest _ANSI_ARGS_((struct vars , struct dfa , chr , chr , chr , chr *, int ));
sl@0	144	static chr lastcold _ANSI_ARGS_((struct vars , struct dfa *));
sl@0	145	static struct dfa newdfa _ANSI_ARGS_((struct vars , struct cnfa , struct colormap , struct smalldfa *));
sl@0	146	static VOID freedfa _ANSI_ARGS_((struct dfa *));
sl@0	147	static unsigned hash _ANSI_ARGS_((unsigned *, int));
sl@0	148	static struct sset initialize _ANSI_ARGS_((struct vars , struct dfa , chr ));
sl@0	149	static struct sset miss _ANSI_ARGS_((struct vars , struct dfa , struct sset , pcolor, chr , chr ));
sl@0	150	static int lacon _ANSI_ARGS_((struct vars , struct cnfa , chr *, pcolor));
sl@0	151	static struct sset getvacant _ANSI_ARGS_((struct vars , struct dfa , chr , chr *));
sl@0	152	static struct sset pickss _ANSI_ARGS_((struct vars , struct dfa , chr , chr *));
sl@0	153	/* automatically gathered by fwd; do not hand-edit */
sl@0	154	/* =====^!^===== end forwards =====^!^===== */
sl@0	155
sl@0	156
sl@0	157
sl@0	158	/*
sl@0	159	- exec - match regular expression
sl@0	160	^ int exec(regex_t , CONST chr , size_t, rm_detail_t *,
sl@0	161	^ size_t, regmatch_t [], int);
sl@0	162	*/
sl@0	163	int
sl@0	164	exec(re, string, len, details, nmatch, pmatch, flags)
sl@0	165	regex_t *re;
sl@0	166	CONST chr *string;
sl@0	167	size_t len;
sl@0	168	rm_detail_t *details;
sl@0	169	size_t nmatch;
sl@0	170	regmatch_t pmatch[];
sl@0	171	int flags;
sl@0	172	{
sl@0	173	struct vars var;
sl@0	174	register struct vars *v = &var;
sl@0	175	int st;
sl@0	176	size_t n;
sl@0	177	int backref;
sl@0	178	# define LOCALMAT 20
sl@0	179	regmatch_t mat[LOCALMAT];
sl@0	180	# define LOCALMEM 40
sl@0	181	regoff_t mem[LOCALMEM];
sl@0	182
sl@0	183	/* sanity checks */
sl@0	184	if (re == NULL \|\| string == NULL \|\| re->re_magic != REMAGIC)
sl@0	185	return REG_INVARG;
sl@0	186	if (re->re_csize != sizeof(chr))
sl@0	187	return REG_MIXED;
sl@0	188
sl@0	189	/* setup */
sl@0	190	v->re = re;
sl@0	191	v->g = (struct guts *)re->re_guts;
sl@0	192	if ((v->g->cflags&REG_EXPECT) && details == NULL)
sl@0	193	return REG_INVARG;
sl@0	194	if (v->g->info&REG_UIMPOSSIBLE)
sl@0	195	return REG_NOMATCH;
sl@0	196	backref = (v->g->info&REG_UBACKREF) ? 1 : 0;
sl@0	197	v->eflags = flags;
sl@0	198	if (v->g->cflags&REG_NOSUB)
sl@0	199	nmatch = 0; /* override client */
sl@0	200	v->nmatch = nmatch;
sl@0	201	if (backref) {
sl@0	202	/* need work area */
sl@0	203	if (v->g->nsub + 1 <= LOCALMAT)
sl@0	204	v->pmatch = mat;
sl@0	205	else
sl@0	206	v->pmatch = (regmatch_t )MALLOC((v->g->nsub + 1)
sl@0	207	sizeof(regmatch_t));
sl@0	208	if (v->pmatch == NULL)
sl@0	209	return REG_ESPACE;
sl@0	210	v->nmatch = v->g->nsub + 1;
sl@0	211	} else
sl@0	212	v->pmatch = pmatch;
sl@0	213	v->details = details;
sl@0	214	v->start = (chr *)string;
sl@0	215	v->stop = (chr *)string + len;
sl@0	216	v->err = 0;
sl@0	217	if (backref) {
sl@0	218	/* need retry memory */
sl@0	219	assert(v->g->ntree >= 0);
sl@0	220	n = (size_t)v->g->ntree;
sl@0	221	if (n <= LOCALMEM)
sl@0	222	v->mem = mem;
sl@0	223	else
sl@0	224	v->mem = (regoff_t )MALLOC(nsizeof(regoff_t));
sl@0	225	if (v->mem == NULL) {
sl@0	226	if (v->pmatch != pmatch && v->pmatch != mat)
sl@0	227	FREE(v->pmatch);
sl@0	228	return REG_ESPACE;
sl@0	229	}
sl@0	230	} else
sl@0	231	v->mem = NULL;
sl@0	232
sl@0	233	/* do it */
sl@0	234	assert(v->g->tree != NULL);
sl@0	235	if (backref)
sl@0	236	st = cfind(v, &v->g->tree->cnfa, &v->g->cmap);
sl@0	237	else
sl@0	238	st = find(v, &v->g->tree->cnfa, &v->g->cmap);
sl@0	239
sl@0	240	/* copy (portion of) match vector over if necessary */
sl@0	241	if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) {
sl@0	242	zapsubs(pmatch, nmatch);
sl@0	243	n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
sl@0	244	memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t));
sl@0	245	}
sl@0	246
sl@0	247	/* clean up */
sl@0	248	if (v->pmatch != pmatch && v->pmatch != mat)
sl@0	249	FREE(v->pmatch);
sl@0	250	if (v->mem != NULL && v->mem != mem)
sl@0	251	FREE(v->mem);
sl@0	252	return st;
sl@0	253	}
sl@0	254
sl@0	255	/*
sl@0	256	- find - find a match for the main NFA (no-complications case)
sl@0	257	^ static int find(struct vars , struct cnfa , struct colormap *);
sl@0	258	*/
sl@0	259	static int
sl@0	260	find(v, cnfa, cm)
sl@0	261	struct vars *v;
sl@0	262	struct cnfa *cnfa;
sl@0	263	struct colormap *cm;
sl@0	264	{
sl@0	265	struct dfa *s;
sl@0	266	struct dfa *d;
sl@0	267	chr *begin;
sl@0	268	chr *end = NULL;
sl@0	269	chr *cold;
sl@0	270	chr open; / open and close of range of possible starts */
sl@0	271	chr *close;
sl@0	272	int hitend;
sl@0	273	int shorter = (v->g->tree->flags&SHORTER) ? 1 : 0;
sl@0	274
sl@0	275	/* first, a shot with the search RE */
sl@0	276	s = newdfa(v, &v->g->search, cm, &v->dfa1);
sl@0	277	assert(!(ISERR() && s != NULL));
sl@0	278	NOERR();
sl@0	279	MDEBUG(("\nsearch at %ld\n", LOFF(v->start)));
sl@0	280	cold = NULL;
sl@0	281	close = shortest(v, s, v->start, v->start, v->stop, &cold, (int *)NULL);
sl@0	282	freedfa(s);
sl@0	283	NOERR();
sl@0	284	if (v->g->cflags&REG_EXPECT) {
sl@0	285	assert(v->details != NULL);
sl@0	286	if (cold != NULL)
sl@0	287	v->details->rm_extend.rm_so = OFF(cold);
sl@0	288	else
sl@0	289	v->details->rm_extend.rm_so = OFF(v->stop);
sl@0	290	v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */
sl@0	291	}
sl@0	292	if (close == NULL) /* not found */
sl@0	293	return REG_NOMATCH;
sl@0	294	if (v->nmatch == 0) /* found, don't need exact location */
sl@0	295	return REG_OKAY;
sl@0	296
sl@0	297	/* find starting point and match */
sl@0	298	assert(cold != NULL);
sl@0	299	open = cold;
sl@0	300	cold = NULL;
sl@0	301	MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close)));
sl@0	302	d = newdfa(v, cnfa, cm, &v->dfa1);
sl@0	303	assert(!(ISERR() && d != NULL));
sl@0	304	NOERR();
sl@0	305	for (begin = open; begin <= close; begin++) {
sl@0	306	MDEBUG(("\nfind trying at %ld\n", LOFF(begin)));
sl@0	307	if (shorter)
sl@0	308	end = shortest(v, d, begin, begin, v->stop,
sl@0	309	(chr **)NULL, &hitend);
sl@0	310	else
sl@0	311	end = longest(v, d, begin, v->stop, &hitend);
sl@0	312	NOERR();
sl@0	313	if (hitend && cold == NULL)
sl@0	314	cold = begin;
sl@0	315	if (end != NULL)
sl@0	316	break; /* NOTE BREAK OUT */
sl@0	317	}
sl@0	318	assert(end != NULL); /* search RE succeeded so loop should */
sl@0	319	freedfa(d);
sl@0	320
sl@0	321	/* and pin down details */
sl@0	322	assert(v->nmatch > 0);
sl@0	323	v->pmatch[0].rm_so = OFF(begin);
sl@0	324	v->pmatch[0].rm_eo = OFF(end);
sl@0	325	if (v->g->cflags&REG_EXPECT) {
sl@0	326	if (cold != NULL)
sl@0	327	v->details->rm_extend.rm_so = OFF(cold);
sl@0	328	else
sl@0	329	v->details->rm_extend.rm_so = OFF(v->stop);
sl@0	330	v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */
sl@0	331	}
sl@0	332	if (v->nmatch == 1) /* no need for submatches */
sl@0	333	return REG_OKAY;
sl@0	334
sl@0	335	/* submatches */
sl@0	336	zapsubs(v->pmatch, v->nmatch);
sl@0	337	return dissect(v, v->g->tree, begin, end);
sl@0	338	}
sl@0	339
sl@0	340	/*
sl@0	341	- cfind - find a match for the main NFA (with complications)
sl@0	342	^ static int cfind(struct vars , struct cnfa , struct colormap *);
sl@0	343	*/
sl@0	344	static int
sl@0	345	cfind(v, cnfa, cm)
sl@0	346	struct vars *v;
sl@0	347	struct cnfa *cnfa;
sl@0	348	struct colormap *cm;
sl@0	349	{
sl@0	350	struct dfa *s;
sl@0	351	struct dfa *d;
sl@0	352	chr cold = NULL; / silence gcc 4 warning */
sl@0	353	int ret;
sl@0	354
sl@0	355	s = newdfa(v, &v->g->search, cm, &v->dfa1);
sl@0	356	NOERR();
sl@0	357	d = newdfa(v, cnfa, cm, &v->dfa2);
sl@0	358	if (ISERR()) {
sl@0	359	assert(d == NULL);
sl@0	360	freedfa(s);
sl@0	361	return v->err;
sl@0	362	}
sl@0	363
sl@0	364	ret = cfindloop(v, cnfa, cm, d, s, &cold);
sl@0	365
sl@0	366	freedfa(d);
sl@0	367	freedfa(s);
sl@0	368	NOERR();
sl@0	369	if (v->g->cflags&REG_EXPECT) {
sl@0	370	assert(v->details != NULL);
sl@0	371	if (cold != NULL)
sl@0	372	v->details->rm_extend.rm_so = OFF(cold);
sl@0	373	else
sl@0	374	v->details->rm_extend.rm_so = OFF(v->stop);
sl@0	375	v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */
sl@0	376	}
sl@0	377	return ret;
sl@0	378	}
sl@0	379
sl@0	380	/*
sl@0	381	- cfindloop - the heart of cfind
sl@0	382	^ static int cfindloop(struct vars , struct cnfa , struct colormap *,
sl@0	383	^ struct dfa , struct dfa , chr **);
sl@0	384	*/
sl@0	385	static int
sl@0	386	cfindloop(v, cnfa, cm, d, s, coldp)
sl@0	387	struct vars *v;
sl@0	388	struct cnfa *cnfa;
sl@0	389	struct colormap *cm;
sl@0	390	struct dfa *d;
sl@0	391	struct dfa *s;
sl@0	392	chr *coldp; / where to put coldstart pointer */
sl@0	393	{
sl@0	394	chr *begin;
sl@0	395	chr *end;
sl@0	396	chr *cold;
sl@0	397	chr open; / open and close of range of possible starts */
sl@0	398	chr *close;
sl@0	399	chr *estart;
sl@0	400	chr *estop;
sl@0	401	int er;
sl@0	402	int shorter = v->g->tree->flags&SHORTER;
sl@0	403	int hitend;
sl@0	404
sl@0	405	assert(d != NULL && s != NULL);
sl@0	406	cold = NULL;
sl@0	407	close = v->start;
sl@0	408	do {
sl@0	409	MDEBUG(("\ncsearch at %ld\n", LOFF(close)));
sl@0	410	close = shortest(v, s, close, close, v->stop, &cold, (int *)NULL);
sl@0	411	if (close == NULL)
sl@0	412	break; /* NOTE BREAK */
sl@0	413	assert(cold != NULL);
sl@0	414	open = cold;
sl@0	415	cold = NULL;
sl@0	416	MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close)));
sl@0	417	for (begin = open; begin <= close; begin++) {
sl@0	418	MDEBUG(("\ncfind trying at %ld\n", LOFF(begin)));
sl@0	419	estart = begin;
sl@0	420	estop = v->stop;
sl@0	421	for (;;) {
sl@0	422	if (shorter)
sl@0	423	end = shortest(v, d, begin, estart,
sl@0	424	estop, (chr **)NULL, &hitend);
sl@0	425	else
sl@0	426	end = longest(v, d, begin, estop,
sl@0	427	&hitend);
sl@0	428	if (hitend && cold == NULL)
sl@0	429	cold = begin;
sl@0	430	if (end == NULL)
sl@0	431	break; /* NOTE BREAK OUT */
sl@0	432	MDEBUG(("tentative end %ld\n", LOFF(end)));
sl@0	433	zapsubs(v->pmatch, v->nmatch);
sl@0	434	zapmem(v, v->g->tree);
sl@0	435	er = cdissect(v, v->g->tree, begin, end);
sl@0	436	if (er == REG_OKAY) {
sl@0	437	if (v->nmatch > 0) {
sl@0	438	v->pmatch[0].rm_so = OFF(begin);
sl@0	439	v->pmatch[0].rm_eo = OFF(end);
sl@0	440	}
sl@0	441	*coldp = cold;
sl@0	442	return REG_OKAY;
sl@0	443	}
sl@0	444	if (er != REG_NOMATCH) {
sl@0	445	ERR(er);
sl@0	446	return er;
sl@0	447	}
sl@0	448	if ((shorter) ? end == estop : end == begin) {
sl@0	449	/* no point in trying again */
sl@0	450	*coldp = cold;
sl@0	451	return REG_NOMATCH;
sl@0	452	}
sl@0	453	/* go around and try again */
sl@0	454	if (shorter)
sl@0	455	estart = end + 1;
sl@0	456	else
sl@0	457	estop = end - 1;
sl@0	458	}
sl@0	459	}
sl@0	460	} while (close < v->stop);
sl@0	461
sl@0	462	*coldp = cold;
sl@0	463	return REG_NOMATCH;
sl@0	464	}
sl@0	465
sl@0	466	/*
sl@0	467	- zapsubs - initialize the subexpression matches to "no match"
sl@0	468	^ static VOID zapsubs(regmatch_t *, size_t);
sl@0	469	*/
sl@0	470	static VOID
sl@0	471	zapsubs(p, n)
sl@0	472	regmatch_t *p;
sl@0	473	size_t n;
sl@0	474	{
sl@0	475	size_t i;
sl@0	476
sl@0	477	for (i = n-1; i > 0; i--) {
sl@0	478	p[i].rm_so = -1;
sl@0	479	p[i].rm_eo = -1;
sl@0	480	}
sl@0	481	}
sl@0	482
sl@0	483	/*
sl@0	484	- zapmem - initialize the retry memory of a subtree to zeros
sl@0	485	^ static VOID zapmem(struct vars , struct subre );
sl@0	486	*/
sl@0	487	static VOID
sl@0	488	zapmem(v, t)
sl@0	489	struct vars *v;
sl@0	490	struct subre *t;
sl@0	491	{
sl@0	492	if (t == NULL)
sl@0	493	return;
sl@0	494
sl@0	495	assert(v->mem != NULL);
sl@0	496	v->mem[t->retry] = 0;
sl@0	497	if (t->op == '(') {
sl@0	498	assert(t->subno > 0);
sl@0	499	v->pmatch[t->subno].rm_so = -1;
sl@0	500	v->pmatch[t->subno].rm_eo = -1;
sl@0	501	}
sl@0	502
sl@0	503	if (t->left != NULL)
sl@0	504	zapmem(v, t->left);
sl@0	505	if (t->right != NULL)
sl@0	506	zapmem(v, t->right);
sl@0	507	}
sl@0	508
sl@0	509	/*
sl@0	510	- subset - set any subexpression relevant to a successful subre
sl@0	511	^ static VOID subset(struct vars , struct subre , chr , chr );
sl@0	512	*/
sl@0	513	static VOID
sl@0	514	subset(v, sub, begin, end)
sl@0	515	struct vars *v;
sl@0	516	struct subre *sub;
sl@0	517	chr *begin;
sl@0	518	chr *end;
sl@0	519	{
sl@0	520	int n = sub->subno;
sl@0	521
sl@0	522	assert(n > 0);
sl@0	523	if ((size_t)n >= v->nmatch)
sl@0	524	return;
sl@0	525
sl@0	526	MDEBUG(("setting %d\n", n));
sl@0	527	v->pmatch[n].rm_so = OFF(begin);
sl@0	528	v->pmatch[n].rm_eo = OFF(end);
sl@0	529	}
sl@0	530
sl@0	531	/*
sl@0	532	- dissect - determine subexpression matches (uncomplicated case)
sl@0	533	^ static int dissect(struct vars , struct subre , chr , chr );
sl@0	534	*/
sl@0	535	static int /* regexec return code */
sl@0	536	dissect(v, t, begin, end)
sl@0	537	struct vars *v;
sl@0	538	struct subre *t;
sl@0	539	chr begin; / beginning of relevant substring */
sl@0	540	chr end; / end of same */
sl@0	541	{
sl@0	542	assert(t != NULL);
sl@0	543	MDEBUG(("dissect %ld-%ld\n", LOFF(begin), LOFF(end)));
sl@0	544
sl@0	545	switch (t->op) {
sl@0	546	case '=': /* terminal node */
sl@0	547	assert(t->left == NULL && t->right == NULL);
sl@0	548	return REG_OKAY; /* no action, parent did the work */
sl@0	549	break;
sl@0	550	case '\|': /* alternation */
sl@0	551	assert(t->left != NULL);
sl@0	552	return altdissect(v, t, begin, end);
sl@0	553	break;
sl@0	554	case 'b': /* back ref -- shouldn't be calling us! */
sl@0	555	return REG_ASSERT;
sl@0	556	break;
sl@0	557	case '.': /* concatenation */
sl@0	558	assert(t->left != NULL && t->right != NULL);
sl@0	559	return condissect(v, t, begin, end);
sl@0	560	break;
sl@0	561	case '(': /* capturing */
sl@0	562	assert(t->left != NULL && t->right == NULL);
sl@0	563	assert(t->subno > 0);
sl@0	564	subset(v, t, begin, end);
sl@0	565	return dissect(v, t->left, begin, end);
sl@0	566	break;
sl@0	567	default:
sl@0	568	return REG_ASSERT;
sl@0	569	break;
sl@0	570	}
sl@0	571	}
sl@0	572
sl@0	573	/*
sl@0	574	- condissect - determine concatenation subexpression matches (uncomplicated)
sl@0	575	^ static int condissect(struct vars , struct subre , chr , chr );
sl@0	576	*/
sl@0	577	static int /* regexec return code */
sl@0	578	condissect(v, t, begin, end)
sl@0	579	struct vars *v;
sl@0	580	struct subre *t;
sl@0	581	chr begin; / beginning of relevant substring */
sl@0	582	chr end; / end of same */
sl@0	583	{
sl@0	584	struct dfa *d;
sl@0	585	struct dfa *d2;
sl@0	586	chr *mid;
sl@0	587	int i;
sl@0	588	int shorter = (t->left->flags&SHORTER) ? 1 : 0;
sl@0	589	chr *stop = (shorter) ? end : begin;
sl@0	590
sl@0	591	assert(t->op == '.');
sl@0	592	assert(t->left != NULL && t->left->cnfa.nstates > 0);
sl@0	593	assert(t->right != NULL && t->right->cnfa.nstates > 0);
sl@0	594
sl@0	595	d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
sl@0	596	NOERR();
sl@0	597	d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &v->dfa2);
sl@0	598	if (ISERR()) {
sl@0	599	assert(d2 == NULL);
sl@0	600	freedfa(d);
sl@0	601	return v->err;
sl@0	602	}
sl@0	603
sl@0	604	/* pick a tentative midpoint */
sl@0	605	if (shorter)
sl@0	606	mid = shortest(v, d, begin, begin, end, (chr **)NULL,
sl@0	607	(int *)NULL);
sl@0	608	else
sl@0	609	mid = longest(v, d, begin, end, (int *)NULL);
sl@0	610	if (mid == NULL) {
sl@0	611	freedfa(d);
sl@0	612	freedfa(d2);
sl@0	613	return REG_ASSERT;
sl@0	614	}
sl@0	615	MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
sl@0	616
sl@0	617	/* iterate until satisfaction or failure */
sl@0	618	while (longest(v, d2, mid, end, (int *)NULL) != end) {
sl@0	619	/* that midpoint didn't work, find a new one */
sl@0	620	if (mid == stop) {
sl@0	621	/* all possibilities exhausted! */
sl@0	622	MDEBUG(("no midpoint!\n"));
sl@0	623	freedfa(d);
sl@0	624	freedfa(d2);
sl@0	625	return REG_ASSERT;
sl@0	626	}
sl@0	627	if (shorter)
sl@0	628	mid = shortest(v, d, begin, mid+1, end, (chr **)NULL,
sl@0	629	(int *)NULL);
sl@0	630	else
sl@0	631	mid = longest(v, d, begin, mid-1, (int *)NULL);
sl@0	632	if (mid == NULL) {
sl@0	633	/* failed to find a new one! */
sl@0	634	MDEBUG(("failed midpoint!\n"));
sl@0	635	freedfa(d);
sl@0	636	freedfa(d2);
sl@0	637	return REG_ASSERT;
sl@0	638	}
sl@0	639	MDEBUG(("new midpoint %ld\n", LOFF(mid)));
sl@0	640	}
sl@0	641
sl@0	642	/* satisfaction */
sl@0	643	MDEBUG(("successful\n"));
sl@0	644	freedfa(d);
sl@0	645	freedfa(d2);
sl@0	646	i = dissect(v, t->left, begin, mid);
sl@0	647	if (i != REG_OKAY)
sl@0	648	return i;
sl@0	649	return dissect(v, t->right, mid, end);
sl@0	650	}
sl@0	651
sl@0	652	/*
sl@0	653	- altdissect - determine alternative subexpression matches (uncomplicated)
sl@0	654	^ static int altdissect(struct vars , struct subre , chr , chr );
sl@0	655	*/
sl@0	656	static int /* regexec return code */
sl@0	657	altdissect(v, t, begin, end)
sl@0	658	struct vars *v;
sl@0	659	struct subre *t;
sl@0	660	chr begin; / beginning of relevant substring */
sl@0	661	chr end; / end of same */
sl@0	662	{
sl@0	663	struct dfa *d;
sl@0	664	int i;
sl@0	665
sl@0	666	assert(t != NULL);
sl@0	667	assert(t->op == '\|');
sl@0	668
sl@0	669	for (i = 0; t != NULL; t = t->right, i++) {
sl@0	670	MDEBUG(("trying %dth\n", i));
sl@0	671	assert(t->left != NULL && t->left->cnfa.nstates > 0);
sl@0	672	d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
sl@0	673	if (ISERR())
sl@0	674	return v->err;
sl@0	675	if (longest(v, d, begin, end, (int *)NULL) == end) {
sl@0	676	MDEBUG(("success\n"));
sl@0	677	freedfa(d);
sl@0	678	return dissect(v, t->left, begin, end);
sl@0	679	}
sl@0	680	freedfa(d);
sl@0	681	}
sl@0	682	return REG_ASSERT; /* none of them matched?!? */
sl@0	683	}
sl@0	684
sl@0	685	/*
sl@0	686	- cdissect - determine subexpression matches (with complications)
sl@0	687	* The retry memory stores the offset of the trial midpoint from begin,
sl@0	688	* plus 1 so that 0 uniquely means "clean slate".
sl@0	689	^ static int cdissect(struct vars , struct subre , chr , chr );
sl@0	690	*/
sl@0	691	static int /* regexec return code */
sl@0	692	cdissect(v, t, begin, end)
sl@0	693	struct vars *v;
sl@0	694	struct subre *t;
sl@0	695	chr begin; / beginning of relevant substring */
sl@0	696	chr end; / end of same */
sl@0	697	{
sl@0	698	int er;
sl@0	699
sl@0	700	assert(t != NULL);
sl@0	701	MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));
sl@0	702
sl@0	703	switch (t->op) {
sl@0	704	case '=': /* terminal node */
sl@0	705	assert(t->left == NULL && t->right == NULL);
sl@0	706	return REG_OKAY; /* no action, parent did the work */
sl@0	707	break;
sl@0	708	case '\|': /* alternation */
sl@0	709	assert(t->left != NULL);
sl@0	710	return caltdissect(v, t, begin, end);
sl@0	711	break;
sl@0	712	case 'b': /* back ref -- shouldn't be calling us! */
sl@0	713	assert(t->left == NULL && t->right == NULL);
sl@0	714	return cbrdissect(v, t, begin, end);
sl@0	715	break;
sl@0	716	case '.': /* concatenation */
sl@0	717	assert(t->left != NULL && t->right != NULL);
sl@0	718	return ccondissect(v, t, begin, end);
sl@0	719	break;
sl@0	720	case '(': /* capturing */
sl@0	721	assert(t->left != NULL && t->right == NULL);
sl@0	722	assert(t->subno > 0);
sl@0	723	er = cdissect(v, t->left, begin, end);
sl@0	724	if (er == REG_OKAY)
sl@0	725	subset(v, t, begin, end);
sl@0	726	return er;
sl@0	727	break;
sl@0	728	default:
sl@0	729	return REG_ASSERT;
sl@0	730	break;
sl@0	731	}
sl@0	732	}
sl@0	733
sl@0	734	/*
sl@0	735	- ccondissect - concatenation subexpression matches (with complications)
sl@0	736	* The retry memory stores the offset of the trial midpoint from begin,
sl@0	737	* plus 1 so that 0 uniquely means "clean slate".
sl@0	738	^ static int ccondissect(struct vars , struct subre , chr , chr );
sl@0	739	*/
sl@0	740	static int /* regexec return code */
sl@0	741	ccondissect(v, t, begin, end)
sl@0	742	struct vars *v;
sl@0	743	struct subre *t;
sl@0	744	chr begin; / beginning of relevant substring */
sl@0	745	chr end; / end of same */
sl@0	746	{
sl@0	747	struct dfa *d;
sl@0	748	struct dfa *d2;
sl@0	749	chr *mid;
sl@0	750	int er;
sl@0	751
sl@0	752	assert(t->op == '.');
sl@0	753	assert(t->left != NULL && t->left->cnfa.nstates > 0);
sl@0	754	assert(t->right != NULL && t->right->cnfa.nstates > 0);
sl@0	755
sl@0	756	if (t->left->flags&SHORTER) /* reverse scan */
sl@0	757	return crevdissect(v, t, begin, end);
sl@0	758
sl@0	759	d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
sl@0	760	if (ISERR())
sl@0	761	return v->err;
sl@0	762	d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
sl@0	763	if (ISERR()) {
sl@0	764	freedfa(d);
sl@0	765	return v->err;
sl@0	766	}
sl@0	767	MDEBUG(("cconcat %d\n", t->retry));
sl@0	768
sl@0	769	/* pick a tentative midpoint */
sl@0	770	if (v->mem[t->retry] == 0) {
sl@0	771	mid = longest(v, d, begin, end, (int *)NULL);
sl@0	772	if (mid == NULL) {
sl@0	773	freedfa(d);
sl@0	774	freedfa(d2);
sl@0	775	return REG_NOMATCH;
sl@0	776	}
sl@0	777	MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
sl@0	778	v->mem[t->retry] = (mid - begin) + 1;
sl@0	779	} else {
sl@0	780	mid = begin + (v->mem[t->retry] - 1);
sl@0	781	MDEBUG(("working midpoint %ld\n", LOFF(mid)));
sl@0	782	}
sl@0	783
sl@0	784	/* iterate until satisfaction or failure */
sl@0	785	for (;;) {
sl@0	786	/* try this midpoint on for size */
sl@0	787	er = cdissect(v, t->left, begin, mid);
sl@0	788	if (er == REG_OKAY &&
sl@0	789	longest(v, d2, mid, end, (int *)NULL) == end &&
sl@0	790	(er = cdissect(v, t->right, mid, end)) ==
sl@0	791	REG_OKAY)
sl@0	792	break; /* NOTE BREAK OUT */
sl@0	793	if (er != REG_OKAY && er != REG_NOMATCH) {
sl@0	794	freedfa(d);
sl@0	795	freedfa(d2);
sl@0	796	return er;
sl@0	797	}
sl@0	798
sl@0	799	/* that midpoint didn't work, find a new one */
sl@0	800	if (mid == begin) {
sl@0	801	/* all possibilities exhausted */
sl@0	802	MDEBUG(("%d no midpoint\n", t->retry));
sl@0	803	freedfa(d);
sl@0	804	freedfa(d2);
sl@0	805	return REG_NOMATCH;
sl@0	806	}
sl@0	807	mid = longest(v, d, begin, mid-1, (int *)NULL);
sl@0	808	if (mid == NULL) {
sl@0	809	/* failed to find a new one */
sl@0	810	MDEBUG(("%d failed midpoint\n", t->retry));
sl@0	811	freedfa(d);
sl@0	812	freedfa(d2);
sl@0	813	return REG_NOMATCH;
sl@0	814	}
sl@0	815	MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
sl@0	816	v->mem[t->retry] = (mid - begin) + 1;
sl@0	817	zapmem(v, t->left);
sl@0	818	zapmem(v, t->right);
sl@0	819	}
sl@0	820
sl@0	821	/* satisfaction */
sl@0	822	MDEBUG(("successful\n"));
sl@0	823	freedfa(d);
sl@0	824	freedfa(d2);
sl@0	825	return REG_OKAY;
sl@0	826	}
sl@0	827
sl@0	828	/*
sl@0	829	- crevdissect - determine backref shortest-first subexpression matches
sl@0	830	* The retry memory stores the offset of the trial midpoint from begin,
sl@0	831	* plus 1 so that 0 uniquely means "clean slate".
sl@0	832	^ static int crevdissect(struct vars , struct subre , chr , chr );
sl@0	833	*/
sl@0	834	static int /* regexec return code */
sl@0	835	crevdissect(v, t, begin, end)
sl@0	836	struct vars *v;
sl@0	837	struct subre *t;
sl@0	838	chr begin; / beginning of relevant substring */
sl@0	839	chr end; / end of same */
sl@0	840	{
sl@0	841	struct dfa *d;
sl@0	842	struct dfa *d2;
sl@0	843	chr *mid;
sl@0	844	int er;
sl@0	845
sl@0	846	assert(t->op == '.');
sl@0	847	assert(t->left != NULL && t->left->cnfa.nstates > 0);
sl@0	848	assert(t->right != NULL && t->right->cnfa.nstates > 0);
sl@0	849	assert(t->left->flags&SHORTER);
sl@0	850
sl@0	851	/* concatenation -- need to split the substring between parts */
sl@0	852	d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
sl@0	853	if (ISERR())
sl@0	854	return v->err;
sl@0	855	d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
sl@0	856	if (ISERR()) {
sl@0	857	freedfa(d);
sl@0	858	return v->err;
sl@0	859	}
sl@0	860	MDEBUG(("crev %d\n", t->retry));
sl@0	861
sl@0	862	/* pick a tentative midpoint */
sl@0	863	if (v->mem[t->retry] == 0) {
sl@0	864	mid = shortest(v, d, begin, begin, end, (chr *)NULL, (int )NULL);
sl@0	865	if (mid == NULL) {
sl@0	866	freedfa(d);
sl@0	867	freedfa(d2);
sl@0	868	return REG_NOMATCH;
sl@0	869	}
sl@0	870	MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
sl@0	871	v->mem[t->retry] = (mid - begin) + 1;
sl@0	872	} else {
sl@0	873	mid = begin + (v->mem[t->retry] - 1);
sl@0	874	MDEBUG(("working midpoint %ld\n", LOFF(mid)));
sl@0	875	}
sl@0	876
sl@0	877	/* iterate until satisfaction or failure */
sl@0	878	for (;;) {
sl@0	879	/* try this midpoint on for size */
sl@0	880	er = cdissect(v, t->left, begin, mid);
sl@0	881	if (er == REG_OKAY &&
sl@0	882	longest(v, d2, mid, end, (int *)NULL) == end &&
sl@0	883	(er = cdissect(v, t->right, mid, end)) ==
sl@0	884	REG_OKAY)
sl@0	885	break; /* NOTE BREAK OUT */
sl@0	886	if (er != REG_OKAY && er != REG_NOMATCH) {
sl@0	887	freedfa(d);
sl@0	888	freedfa(d2);
sl@0	889	return er;
sl@0	890	}
sl@0	891
sl@0	892	/* that midpoint didn't work, find a new one */
sl@0	893	if (mid == end) {
sl@0	894	/* all possibilities exhausted */
sl@0	895	MDEBUG(("%d no midpoint\n", t->retry));
sl@0	896	freedfa(d);
sl@0	897	freedfa(d2);
sl@0	898	return REG_NOMATCH;
sl@0	899	}
sl@0	900	mid = shortest(v, d, begin, mid+1, end, (chr *)NULL, (int )NULL);
sl@0	901	if (mid == NULL) {
sl@0	902	/* failed to find a new one */
sl@0	903	MDEBUG(("%d failed midpoint\n", t->retry));
sl@0	904	freedfa(d);
sl@0	905	freedfa(d2);
sl@0	906	return REG_NOMATCH;
sl@0	907	}
sl@0	908	MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
sl@0	909	v->mem[t->retry] = (mid - begin) + 1;
sl@0	910	zapmem(v, t->left);
sl@0	911	zapmem(v, t->right);
sl@0	912	}
sl@0	913
sl@0	914	/* satisfaction */
sl@0	915	MDEBUG(("successful\n"));
sl@0	916	freedfa(d);
sl@0	917	freedfa(d2);
sl@0	918	return REG_OKAY;
sl@0	919	}
sl@0	920
sl@0	921	/*
sl@0	922	- cbrdissect - determine backref subexpression matches
sl@0	923	^ static int cbrdissect(struct vars , struct subre , chr , chr );
sl@0	924	*/
sl@0	925	static int /* regexec return code */
sl@0	926	cbrdissect(v, t, begin, end)
sl@0	927	struct vars *v;
sl@0	928	struct subre *t;
sl@0	929	chr begin; / beginning of relevant substring */
sl@0	930	chr end; / end of same */
sl@0	931	{
sl@0	932	int i;
sl@0	933	int n = t->subno;
sl@0	934	size_t len;
sl@0	935	chr *paren;
sl@0	936	chr *p;
sl@0	937	chr *stop;
sl@0	938	int min = t->min;
sl@0	939	int max = t->max;
sl@0	940
sl@0	941	assert(t != NULL);
sl@0	942	assert(t->op == 'b');
sl@0	943	assert(n >= 0);
sl@0	944	assert((size_t)n < v->nmatch);
sl@0	945
sl@0	946	MDEBUG(("cbackref n%d %d{%d-%d}\n", t->retry, n, min, max));
sl@0	947
sl@0	948	if (v->pmatch[n].rm_so == -1)
sl@0	949	return REG_NOMATCH;
sl@0	950	paren = v->start + v->pmatch[n].rm_so;
sl@0	951	len = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
sl@0	952
sl@0	953	/* no room to maneuver -- retries are pointless */
sl@0	954	if (v->mem[t->retry])
sl@0	955	return REG_NOMATCH;
sl@0	956	v->mem[t->retry] = 1;
sl@0	957
sl@0	958	/* special-case zero-length string */
sl@0	959	if (len == 0) {
sl@0	960	if (begin == end)
sl@0	961	return REG_OKAY;
sl@0	962	return REG_NOMATCH;
sl@0	963	}
sl@0	964
sl@0	965	/* and too-short string */
sl@0	966	assert(end >= begin);
sl@0	967	if ((size_t)(end - begin) < len)
sl@0	968	return REG_NOMATCH;
sl@0	969	stop = end - len;
sl@0	970
sl@0	971	/* count occurrences */
sl@0	972	i = 0;
sl@0	973	for (p = begin; p <= stop && (i < max \|\| max == INFINITY); p += len) {
sl@0	974	if ((*v->g->compare)(paren, p, len) != 0)
sl@0	975	break;
sl@0	976	i++;
sl@0	977	}
sl@0	978	MDEBUG(("cbackref found %d\n", i));
sl@0	979
sl@0	980	/* and sort it out */
sl@0	981	if (p != end) /* didn't consume all of it */
sl@0	982	return REG_NOMATCH;
sl@0	983	if (min <= i && (i <= max \|\| max == INFINITY))
sl@0	984	return REG_OKAY;
sl@0	985	return REG_NOMATCH; /* out of range */
sl@0	986	}
sl@0	987
sl@0	988	/*
sl@0	989	- caltdissect - determine alternative subexpression matches (w. complications)
sl@0	990	^ static int caltdissect(struct vars , struct subre , chr , chr );
sl@0	991	*/
sl@0	992	static int /* regexec return code */
sl@0	993	caltdissect(v, t, begin, end)
sl@0	994	struct vars *v;
sl@0	995	struct subre *t;
sl@0	996	chr begin; / beginning of relevant substring */
sl@0	997	chr end; / end of same */
sl@0	998	{
sl@0	999	struct dfa *d;
sl@0	1000	int er;
sl@0	1001	# define UNTRIED 0 /* not yet tried at all */
sl@0	1002	# define TRYING 1 /* top matched, trying submatches */
sl@0	1003	# define TRIED 2 /* top didn't match or submatches exhausted */
sl@0	1004
sl@0	1005	if (t == NULL)
sl@0	1006	return REG_NOMATCH;
sl@0	1007	assert(t->op == '\|');
sl@0	1008	if (v->mem[t->retry] == TRIED)
sl@0	1009	return caltdissect(v, t->right, begin, end);
sl@0	1010
sl@0	1011	MDEBUG(("calt n%d\n", t->retry));
sl@0	1012	assert(t->left != NULL);
sl@0	1013
sl@0	1014	if (v->mem[t->retry] == UNTRIED) {
sl@0	1015	d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
sl@0	1016	if (ISERR())
sl@0	1017	return v->err;
sl@0	1018	if (longest(v, d, begin, end, (int *)NULL) != end) {
sl@0	1019	freedfa(d);
sl@0	1020	v->mem[t->retry] = TRIED;
sl@0	1021	return caltdissect(v, t->right, begin, end);
sl@0	1022	}
sl@0	1023	freedfa(d);
sl@0	1024	MDEBUG(("calt matched\n"));
sl@0	1025	v->mem[t->retry] = TRYING;
sl@0	1026	}
sl@0	1027
sl@0	1028	er = cdissect(v, t->left, begin, end);
sl@0	1029	if (er != REG_NOMATCH)
sl@0	1030	return er;
sl@0	1031
sl@0	1032	v->mem[t->retry] = TRIED;
sl@0	1033	return caltdissect(v, t->right, begin, end);
sl@0	1034	}
sl@0	1035
sl@0	1036
sl@0	1037
sl@0	1038	#include "rege_dfa.c"

author	sl@SLION-WIN7.fritz.box
	Fri, 15 Jun 2012 03:10:57 +0200
changeset 0	bde4ae8d615e
permissions	-rw-r--r--