Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

engine.c @ 543

Last change on this file since 543 was 444, checked in by satin@…, 6 years ago
add newlib,libalmos-mkh, restructure shared_syscalls.h and mini-libc
File size: 28.6 KB

Line
1	/*-
2	* Copyright (c) 1992, 1993, 1994 Henry Spencer.
3	* Copyright (c) 1992, 1993, 1994
4	* The Regents of the University of California. All rights reserved.
5	*
6	* This code is derived from software contributed to Berkeley by
7	* Henry Spencer.
8	*
9	* Redistribution and use in source and binary forms, with or without
10	* modification, are permitted provided that the following conditions
11	* are met:
12	* 1. Redistributions of source code must retain the above copyright
13	* notice, this list of conditions and the following disclaimer.
14	* 2. Redistributions in binary form must reproduce the above copyright
15	* notice, this list of conditions and the following disclaimer in the
16	* documentation and/or other materials provided with the distribution.
17	* 4. Neither the name of the University nor the names of its contributors
18	* may be used to endorse or promote products derived from this software
19	* without specific prior written permission.
20	*
21	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31	* SUCH DAMAGE.
32	*
33	* @(#)engine.c 8.5 (Berkeley) 3/20/94
34	*/
35
36	#include <sys/cdefs.h>
37	#include <_ansi.h>
38
39	/*
40	* The matching engine and friends. This file is #included by regexec.c
41	* after suitable #defines of a variety of macros used herein, so that
42	* different state representations can be used without duplicating masses
43	* of code.
44	*/
45
46	#ifdef SNAMES
47	#define matcher smatcher
48	#define fast sfast
49	#define slow sslow
50	#define dissect sdissect
51	#define backref sbackref
52	#define step sstep
53	#define print sprint
54	#define at sat
55	#define match smat
56	#endif
57	#ifdef LNAMES
58	#define matcher lmatcher
59	#define fast lfast
60	#define slow lslow
61	#define dissect ldissect
62	#define backref lbackref
63	#define step lstep
64	#define print lprint
65	#define at lat
66	#define match lmat
67	#endif
68
69	/* another structure passed up and down to avoid zillions of parameters */
70	struct match {
71	struct re_guts *g;
72	int eflags;
73	regmatch_t pmatch; / [nsub+1] (0 element unused) */
74	char offp; / offsets work from here */
75	char beginp; / start of string -- virtual NUL precedes */
76	char endp; / end of string -- virtual NUL here */
77	char coldp; / can be no match starting before here */
78	char *lastpos; / [nplus+1] */
79	STATEVARS;
80	states st; /* current states */
81	states fresh; /* states for a fresh start */
82	states tmp; /* temporary */
83	states empty; /* empty set of states */
84	};
85
86	/* ========= begin header generated by ./mkh ========= */
87	#ifdef __cplusplus
88	extern "C" {
89	#endif
90
91	/* === engine.c === */
92	static int matcher(struct re_guts g, char string, size_t nmatch, regmatch_t pmatch[], int eflags);
93	static char dissect(struct match m, char start, char stop, sopno startst, sopno stopst);
94	static char backref(struct match m, char start, char stop, sopno startst, sopno stopst, sopno lev);
95	static char fast(struct match m, char start, char stop, sopno startst, sopno stopst);
96	static char slow(struct match m, char start, char stop, sopno startst, sopno stopst);
97	static states step(struct re_guts *g, sopno start, sopno stop, states bef, int ch, states aft);
98	#define BOL (OUT+1)
99	#define EOL (BOL+1)
100	#define BOLEOL (BOL+2)
101	#define NOTHING (BOL+3)
102	#define BOW (BOL+4)
103	#define EOW (BOL+5)
104	#define CODEMAX (BOL+5) /* highest code used */
105	#define NONCHAR(c) ((c) > CHAR_MAX)
106	#define NNONCHAR (CODEMAX-CHAR_MAX)
107	#ifdef REDEBUG
108	static void print(struct match m, char caption, states st, int ch, FILE *d);
109	#endif
110	#ifdef REDEBUG
111	static void at(struct match m, char title, char start, char stop, sopno startst, sopno stopst);
112	#endif
113	#ifdef REDEBUG
114	static char *pchar(int ch);
115	#endif
116
117	#ifdef __cplusplus
118	}
119	#endif
120	/* ========= end header generated by ./mkh ========= */
121
122	#ifdef REDEBUG
123	#define SP(t, s, c) print(m, t, s, c, stdout)
124	#define AT(t, p1, p2, s1, s2) at(m, t, p1, p2, s1, s2)
125	#define NOTE(str) { if (m->eflags&REG_TRACE) printf("=%s\n", (str)); }
126	#else
127	#define SP(t, s, c) /* nothing */
128	#define AT(t, p1, p2, s1, s2) /* nothing */
129	#define NOTE(s) /* nothing */
130	#endif
131
132	/*
133	- matcher - the actual matching engine
134	== static int matcher(struct re_guts g, char string, \
135	== size_t nmatch, regmatch_t pmatch[], int eflags);
136	*/
137	static int /* 0 success, REG_NOMATCH failure */
138	matcher(g, string, nmatch, pmatch, eflags)
139	struct re_guts *g;
140	char *string;
141	size_t nmatch;
142	regmatch_t pmatch[];
143	int eflags;
144	{
145	char *endp;
146	int i;
147	struct match mv;
148	struct match *m = &mv;
149	char *dp = NULL;
150	const sopno gf = g->firststate+1; /* +1 for OEND */
151	const sopno gl = g->laststate;
152	char *start;
153	char *stop;
154	/* Boyer-Moore algorithms variables */
155	char *pp;
156	int cj, mj;
157	char *mustfirst;
158	char *mustlast;
159	int *matchjump;
160	int *charjump;
161
162	/* simplify the situation where possible */
163	if (g->cflags&REG_NOSUB)
164	nmatch = 0;
165	if (eflags&REG_STARTEND) {
166	start = string + pmatch[0].rm_so;
167	stop = string + pmatch[0].rm_eo;
168	} else {
169	start = string;
170	stop = start + strlen(start);
171	}
172	if (stop < start)
173	return(REG_INVARG);
174
175	/* prescreening; this does wonders for this rather slow code */
176	if (g->must != NULL) {
177	if (g->charjump != NULL && g->matchjump != NULL) {
178	mustfirst = g->must;
179	mustlast = g->must + g->mlen - 1;
180	charjump = g->charjump;
181	matchjump = g->matchjump;
182	pp = mustlast;
183	for (dp = start+g->mlen-1; dp < stop;) {
184	/* Fast skip non-matches */
185	while (dp < stop && charjump[(unsigned char) *dp])
186	dp += charjump[(unsigned char) *dp];
187
188	if (dp >= stop)
189	break;
190
191	/* Greedy matcher */
192	/* We depend on not being used for
193	* for strings of length 1
194	*/
195	while (--dp == --pp && pp != mustfirst);
196
197	if (dp == pp)
198	break;
199
200	/* Jump to next possible match */
201	mj = matchjump[pp - mustfirst];
202	cj = charjump[(unsigned char) *dp];
203	dp += (cj < mj ? mj : cj);
204	pp = mustlast;
205	}
206	if (pp != mustfirst)
207	return(REG_NOMATCH);
208	} else {
209	for (dp = start; dp < stop; dp++)
210	if (*dp == g->must[0] &&
211	stop - dp >= g->mlen &&
212	memcmp(dp, g->must, (size_t)g->mlen) == 0)
213	break;
214	if (dp == stop) /* we didn't find g->must */
215	return(REG_NOMATCH);
216	}
217	}
218
219	/* match struct setup */
220	m->g = g;
221	m->eflags = eflags;
222	m->pmatch = NULL;
223	m->lastpos = NULL;
224	m->offp = string;
225	m->beginp = start;
226	m->endp = stop;
227	STATESETUP(m, 4);
228	SETUP(m->st);
229	SETUP(m->fresh);
230	SETUP(m->tmp);
231	SETUP(m->empty);
232	CLEAR(m->empty);
233
234	/* Adjust start according to moffset, to speed things up */
235	if (g->moffset > -1)
236	start = ((dp - g->moffset) < start) ? start : dp - g->moffset;
237
238	/* this loop does only one repetition except for backrefs */
239	for (;;) {
240	endp = fast(m, start, stop, gf, gl);
241	if (endp == NULL) { /* a miss */
242	STATETEARDOWN(m);
243	return(REG_NOMATCH);
244	}
245	if (nmatch == 0 && !g->backrefs)
246	break; /* no further info needed */
247
248	/* where? */
249	assert(m->coldp != NULL);
250	for (;;) {
251	NOTE("finding start");
252	endp = slow(m, m->coldp, stop, gf, gl);
253	if (endp != NULL)
254	break;
255	assert(m->coldp < m->endp);
256	m->coldp++;
257	}
258	if (nmatch == 1 && !g->backrefs)
259	break; /* no further info needed */
260
261	/* oh my, he wants the subexpressions... */
262	if (m->pmatch == NULL)
263	m->pmatch = (regmatch_t )malloc((m->g->nsub + 1)
264	sizeof(regmatch_t));
265	if (m->pmatch == NULL) {
266	STATETEARDOWN(m);
267	return(REG_ESPACE);
268	}
269	for (i = 1; i <= m->g->nsub; i++)
270	m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
271	if (!g->backrefs && !(m->eflags&REG_BACKR)) {
272	NOTE("dissecting");
273	dp = dissect(m, m->coldp, endp, gf, gl);
274	} else {
275	if (g->nplus > 0 && m->lastpos == NULL)
276	m->lastpos = (char *)malloc((g->nplus+1)
277	sizeof(char *));
278	if (g->nplus > 0 && m->lastpos == NULL) {
279	free(m->pmatch);
280	STATETEARDOWN(m);
281	return(REG_ESPACE);
282	}
283	NOTE("backref dissect");
284	dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
285	}
286	if (dp != NULL)
287	break;
288
289	/* uh-oh... we couldn't find a subexpression-level match */
290	assert(g->backrefs); /* must be back references doing it */
291	assert(g->nplus == 0 \|\| m->lastpos != NULL);
292	for (;;) {
293	if (dp != NULL \|\| endp <= m->coldp)
294	break; /* defeat */
295	NOTE("backoff");
296	endp = slow(m, m->coldp, endp-1, gf, gl);
297	if (endp == NULL)
298	break; /* defeat */
299	/* try it on a shorter possibility */
300	#ifndef NDEBUG
301	for (i = 1; i <= m->g->nsub; i++) {
302	assert(m->pmatch[i].rm_so == -1);
303	assert(m->pmatch[i].rm_eo == -1);
304	}
305	#endif
306	NOTE("backoff dissect");
307	dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
308	}
309	assert(dp == NULL \|\| dp == endp);
310	if (dp != NULL) /* found a shorter one */
311	break;
312
313	/* despite initial appearances, there is no match here */
314	NOTE("false alarm");
315	start = m->coldp + 1; /* recycle starting later */
316	assert(start <= stop);
317	}
318
319	/* fill in the details if requested */
320	if (nmatch > 0) {
321	pmatch[0].rm_so = m->coldp - m->offp;
322	pmatch[0].rm_eo = endp - m->offp;
323	}
324	if (nmatch > 1) {
325	assert(m->pmatch != NULL);
326	for (i = 1; i < nmatch; i++)
327	if (i <= m->g->nsub)
328	pmatch[i] = m->pmatch[i];
329	else {
330	pmatch[i].rm_so = -1;
331	pmatch[i].rm_eo = -1;
332	}
333	}
334
335	if (m->pmatch != NULL)
336	free((char *)m->pmatch);
337	if (m->lastpos != NULL)
338	free((char *)m->lastpos);
339	STATETEARDOWN(m);
340	return(0);
341	}
342
343	/*
344	- dissect - figure out what matched what, no back references
345	== static char dissect(struct match m, char *start, \
346	== char *stop, sopno startst, sopno stopst);
347	*/
348	static char * /* == stop (success) always */
349	dissect(m, start, stop, startst, stopst)
350	struct match *m;
351	char *start;
352	char *stop;
353	sopno startst;
354	sopno stopst;
355	{
356	int i;
357	sopno ss; /* start sop of current subRE */
358	sopno es; /* end sop of current subRE */
359	char sp; / start of string matched by it */
360	char stp; / string matched by it cannot pass here */
361	char rest; / start of rest of string */
362	char tail; / string unmatched by rest of RE */
363	sopno ssub; /* start sop of subsubRE */
364	sopno esub; /* end sop of subsubRE */
365	char ssp; / start of string matched by subsubRE */
366	char sep; / end of string matched by subsubRE */
367	char oldssp; / previous ssp */
368	#if __GNUC_PREREQ (4, 6)
369	/* dp is only used for assertion testing which, for some reason, is not
370	recognized as usage. */
371	#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
372	#endif
373	char *dp;
374
375	AT("diss", start, stop, startst, stopst);
376	sp = start;
377	for (ss = startst; ss < stopst; ss = es) {
378	/* identify end of subRE */
379	es = ss;
380	switch (OP(m->g->strip[es])) {
381	case OPLUS_:
382	case OQUEST_:
383	es += OPND(m->g->strip[es]);
384	break;
385	case OCH_:
386	while (OP(m->g->strip[es]) != O_CH)
387	es += OPND(m->g->strip[es]);
388	break;
389	}
390	es++;
391
392	/* figure out what it matched */
393	switch (OP(m->g->strip[ss])) {
394	case OEND:
395	assert(nope);
396	break;
397	case OCHAR:
398	sp++;
399	break;
400	case OBOL:
401	case OEOL:
402	case OBOW:
403	case OEOW:
404	break;
405	case OANY:
406	case OANYOF:
407	sp++;
408	break;
409	case OBACK_:
410	case O_BACK:
411	assert(nope);
412	break;
413	/* cases where length of match is hard to find */
414	case OQUEST_:
415	stp = stop;
416	for (;;) {
417	/* how long could this one be? */
418	rest = slow(m, sp, stp, ss, es);
419	assert(rest != NULL); /* it did match */
420	/* could the rest match the rest? */
421	tail = slow(m, rest, stop, es, stopst);
422	if (tail == stop)
423	break; /* yes! */
424	/* no -- try a shorter match for this one */
425	stp = rest - 1;
426	assert(stp >= sp); /* it did work */
427	}
428	ssub = ss + 1;
429	esub = es - 1;
430	/* did innards match? */
431	if (slow(m, sp, rest, ssub, esub) != NULL) {
432	dp = dissect(m, sp, rest, ssub, esub);
433	assert(dp == rest);
434	} else /* no */
435	assert(sp == rest);
436	sp = rest;
437	break;
438	case OPLUS_:
439	stp = stop;
440	for (;;) {
441	/* how long could this one be? */
442	rest = slow(m, sp, stp, ss, es);
443	assert(rest != NULL); /* it did match */
444	/* could the rest match the rest? */
445	tail = slow(m, rest, stop, es, stopst);
446	if (tail == stop)
447	break; /* yes! */
448	/* no -- try a shorter match for this one */
449	stp = rest - 1;
450	assert(stp >= sp); /* it did work */
451	}
452	ssub = ss + 1;
453	esub = es - 1;
454	ssp = sp;
455	oldssp = ssp;
456	for (;;) { /* find last match of innards */
457	sep = slow(m, ssp, rest, ssub, esub);
458	if (sep == NULL \|\| sep == ssp)
459	break; /* failed or matched null */
460	oldssp = ssp; /* on to next try */
461	ssp = sep;
462	}
463	if (sep == NULL) {
464	/* last successful match */
465	sep = ssp;
466	ssp = oldssp;
467	}
468	assert(sep == rest); /* must exhaust substring */
469	assert(slow(m, ssp, sep, ssub, esub) == rest);
470	dp = dissect(m, ssp, sep, ssub, esub);
471	assert(dp == sep);
472	sp = rest;
473	break;
474	case OCH_:
475	stp = stop;
476	for (;;) {
477	/* how long could this one be? */
478	rest = slow(m, sp, stp, ss, es);
479	assert(rest != NULL); /* it did match */
480	/* could the rest match the rest? */
481	tail = slow(m, rest, stop, es, stopst);
482	if (tail == stop)
483	break; /* yes! */
484	/* no -- try a shorter match for this one */
485	stp = rest - 1;
486	assert(stp >= sp); /* it did work */
487	}
488	ssub = ss + 1;
489	esub = ss + OPND(m->g->strip[ss]) - 1;
490	assert(OP(m->g->strip[esub]) == OOR1);
491	for (;;) { /* find first matching branch */
492	if (slow(m, sp, rest, ssub, esub) == rest)
493	break; /* it matched all of it */
494	/* that one missed, try next one */
495	assert(OP(m->g->strip[esub]) == OOR1);
496	esub++;
497	assert(OP(m->g->strip[esub]) == OOR2);
498	ssub = esub + 1;
499	esub += OPND(m->g->strip[esub]);
500	if (OP(m->g->strip[esub]) == OOR2)
501	esub--;
502	else
503	assert(OP(m->g->strip[esub]) == O_CH);
504	}
505	dp = dissect(m, sp, rest, ssub, esub);
506	assert(dp == rest);
507	sp = rest;
508	break;
509	case O_PLUS:
510	case O_QUEST:
511	case OOR1:
512	case OOR2:
513	case O_CH:
514	assert(nope);
515	break;
516	case OLPAREN:
517	i = OPND(m->g->strip[ss]);
518	assert(0 < i && i <= m->g->nsub);
519	m->pmatch[i].rm_so = sp - m->offp;
520	break;
521	case ORPAREN:
522	i = OPND(m->g->strip[ss]);
523	assert(0 < i && i <= m->g->nsub);
524	m->pmatch[i].rm_eo = sp - m->offp;
525	break;
526	default: /* uh oh */
527	assert(nope);
528	break;
529	}
530	}
531
532	assert(sp == stop);
533	return(sp);
534	}
535
536	/*
537	- backref - figure out what matched what, figuring in back references
538	== static char backref(struct match m, char *start, \
539	== char *stop, sopno startst, sopno stopst, sopno lev);
540	*/
541	static char * /* == stop (success) or NULL (failure) */
542	backref(m, start, stop, startst, stopst, lev)
543	struct match *m;
544	char *start;
545	char *stop;
546	sopno startst;
547	sopno stopst;
548	sopno lev; /* PLUS nesting level */
549	{
550	int i;
551	sopno ss; /* start sop of current subRE */
552	char sp; / start of string matched by it */
553	sopno ssub; /* start sop of subsubRE */
554	sopno esub; /* end sop of subsubRE */
555	char ssp; / start of string matched by subsubRE */
556	char *dp;
557	size_t len;
558	int hard;
559	sop s;
560	regoff_t offsave;
561	cset *cs;
562
563	AT("back", start, stop, startst, stopst);
564	sp = start;
565
566	/* get as far as we can with easy stuff */
567	hard = 0;
568	for (ss = startst; !hard && ss < stopst; ss++)
569	switch (OP(s = m->g->strip[ss])) {
570	case OCHAR:
571	if (sp == stop \|\| *sp++ != (char)OPND(s))
572	return(NULL);
573	break;
574	case OANY:
575	if (sp == stop)
576	return(NULL);
577	sp++;
578	break;
579	case OANYOF:
580	cs = &m->g->sets[OPND(s)];
581	if (sp == stop \|\| !CHIN(cs, *sp++))
582	return(NULL);
583	break;
584	case OBOL:
585	if ( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) \|\|
586	(sp < m->endp && *(sp-1) == '\n' &&
587	(m->g->cflags&REG_NEWLINE)) )
588	{ /* yes */ }
589	else
590	return(NULL);
591	break;
592	case OEOL:
593	if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) \|\|
594	(sp < m->endp && *sp == '\n' &&
595	(m->g->cflags&REG_NEWLINE)) )
596	{ /* yes */ }
597	else
598	return(NULL);
599	break;
600	case OBOW:
601	if (( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) \|\|
602	(sp < m->endp && *(sp-1) == '\n' &&
603	(m->g->cflags&REG_NEWLINE)) \|\|
604	(sp > m->beginp &&
605	!ISWORD(*(sp-1))) ) &&
606	(sp < m->endp && ISWORD(*sp)) )
607	{ /* yes */ }
608	else
609	return(NULL);
610	break;
611	case OEOW:
612	if (( (sp == m->endp && !(m->eflags&REG_NOTEOL)) \|\|
613	(sp < m->endp && *sp == '\n' &&
614	(m->g->cflags&REG_NEWLINE)) \|\|
615	(sp < m->endp && !ISWORD(*sp)) ) &&
616	(sp > m->beginp && ISWORD(*(sp-1))) )
617	{ /* yes */ }
618	else
619	return(NULL);
620	break;
621	case O_QUEST:
622	break;
623	case OOR1: /* matches null but needs to skip */
624	ss++;
625	s = m->g->strip[ss];
626	do {
627	assert(OP(s) == OOR2);
628	ss += OPND(s);
629	} while (OP(s = m->g->strip[ss]) != O_CH);
630	/* note that the ss++ gets us past the O_CH */
631	break;
632	default: /* have to make a choice */
633	hard = 1;
634	break;
635	}
636	if (!hard) { /* that was it! */
637	if (sp != stop)
638	return(NULL);
639	return(sp);
640	}
641	ss--; /* adjust for the for's final increment */
642
643	/* the hard stuff */
644	AT("hard", sp, stop, ss, stopst);
645	s = m->g->strip[ss];
646	switch (OP(s)) {
647	case OBACK_: /* the vilest depths */
648	i = OPND(s);
649	assert(0 < i && i <= m->g->nsub);
650	if (m->pmatch[i].rm_eo == -1)
651	return(NULL);
652	assert(m->pmatch[i].rm_so != -1);
653	len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
654	assert(stop - m->beginp >= len);
655	if (sp > stop - len)
656	return(NULL); /* not enough left to match */
657	ssp = m->offp + m->pmatch[i].rm_so;
658	if (memcmp(sp, ssp, len) != 0)
659	return(NULL);
660	while (m->g->strip[ss] != SOP(O_BACK, i))
661	ss++;
662	return(backref(m, sp+len, stop, ss+1, stopst, lev));
663	break;
664	case OQUEST_: /* to null or not */
665	dp = backref(m, sp, stop, ss+1, stopst, lev);
666	if (dp != NULL)
667	return(dp); /* not */
668	return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev));
669	break;
670	case OPLUS_:
671	assert(m->lastpos != NULL);
672	assert(lev+1 <= m->g->nplus);
673	m->lastpos[lev+1] = sp;
674	return(backref(m, sp, stop, ss+1, stopst, lev+1));
675	break;
676	case O_PLUS:
677	if (sp == m->lastpos[lev]) /* last pass matched null */
678	return(backref(m, sp, stop, ss+1, stopst, lev-1));
679	/* try another pass */
680	m->lastpos[lev] = sp;
681	dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev);
682	if (dp == NULL)
683	return(backref(m, sp, stop, ss+1, stopst, lev-1));
684	else
685	return(dp);
686	break;
687	case OCH_: /* find the right one, if any */
688	ssub = ss + 1;
689	esub = ss + OPND(s) - 1;
690	assert(OP(m->g->strip[esub]) == OOR1);
691	for (;;) { /* find first matching branch */
692	dp = backref(m, sp, stop, ssub, esub, lev);
693	if (dp != NULL)
694	return(dp);
695	/* that one missed, try next one */
696	if (OP(m->g->strip[esub]) == O_CH)
697	return(NULL); /* there is none */
698	esub++;
699	assert(OP(m->g->strip[esub]) == OOR2);
700	ssub = esub + 1;
701	esub += OPND(m->g->strip[esub]);
702	if (OP(m->g->strip[esub]) == OOR2)
703	esub--;
704	else
705	assert(OP(m->g->strip[esub]) == O_CH);
706	}
707	break;
708	case OLPAREN: /* must undo assignment if rest fails */
709	i = OPND(s);
710	assert(0 < i && i <= m->g->nsub);
711	offsave = m->pmatch[i].rm_so;
712	m->pmatch[i].rm_so = sp - m->offp;
713	dp = backref(m, sp, stop, ss+1, stopst, lev);
714	if (dp != NULL)
715	return(dp);
716	m->pmatch[i].rm_so = offsave;
717	return(NULL);
718	break;
719	case ORPAREN: /* must undo assignment if rest fails */
720	i = OPND(s);
721	assert(0 < i && i <= m->g->nsub);
722	offsave = m->pmatch[i].rm_eo;
723	m->pmatch[i].rm_eo = sp - m->offp;
724	dp = backref(m, sp, stop, ss+1, stopst, lev);
725	if (dp != NULL)
726	return(dp);
727	m->pmatch[i].rm_eo = offsave;
728	return(NULL);
729	break;
730	default: /* uh oh */
731	assert(nope);
732	break;
733	}
734
735	/* "can't happen" */
736	assert(nope);
737	/* NOTREACHED */
738	return "shut up gcc";
739	}
740
741	/*
742	- fast - step through the string at top speed
743	== static char fast(struct match m, char *start, \
744	== char *stop, sopno startst, sopno stopst);
745	*/
746	static char * /* where tentative match ended, or NULL */
747	fast(m, start, stop, startst, stopst)
748	struct match *m;
749	char *start;
750	char *stop;
751	sopno startst;
752	sopno stopst;
753	{
754	states st = m->st;
755	states fresh = m->fresh;
756	states tmp = m->tmp;
757	char *p = start;
758	int c = (start == m->beginp) ? OUT : *(start-1);
759	int lastc; /* previous c */
760	int flagch;
761	int i;
762	char coldp; / last p after which no match was underway */
763
764	CLEAR(st);
765	SET1(st, startst);
766	st = step(m->g, startst, stopst, st, NOTHING, st);
767	ASSIGN(fresh, st);
768	SP("start", st, *p);
769	coldp = NULL;
770	for (;;) {
771	/* next character */
772	lastc = c;
773	c = (p == m->endp) ? OUT : *p;
774	if (EQ(st, fresh))
775	coldp = p;
776
777	/* is there an EOL and/or BOL between lastc and c? */
778	flagch = '\0';
779	i = 0;
780	if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) \|\|
781	(lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
782	flagch = BOL;
783	i = m->g->nbol;
784	}
785	if ( (c == '\n' && m->g->cflags&REG_NEWLINE) \|\|
786	(c == OUT && !(m->eflags&REG_NOTEOL)) ) {
787	flagch = (flagch == BOL) ? BOLEOL : EOL;
788	i += m->g->neol;
789	}
790	if (i != 0) {
791	for (; i > 0; i--)
792	st = step(m->g, startst, stopst, st, flagch, st);
793	SP("boleol", st, c);
794	}
795
796	/* how about a word boundary? */
797	if ( (flagch == BOL \|\| (lastc != OUT && !ISWORD(lastc))) &&
798	(c != OUT && ISWORD(c)) ) {
799	flagch = BOW;
800	}
801	if ( (lastc != OUT && ISWORD(lastc)) &&
802	(flagch == EOL \|\| (c != OUT && !ISWORD(c))) ) {
803	flagch = EOW;
804	}
805	if (flagch == BOW \|\| flagch == EOW) {
806	st = step(m->g, startst, stopst, st, flagch, st);
807	SP("boweow", st, c);
808	}
809
810	/* are we done? */
811	if (ISSET(st, stopst) \|\| p == stop)
812	break; /* NOTE BREAK OUT */
813
814	/* no, we must deal with this character */
815	ASSIGN(tmp, st);
816	ASSIGN(st, fresh);
817	assert(c != OUT);
818	st = step(m->g, startst, stopst, tmp, c, st);
819	SP("aft", st, c);
820	assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
821	p++;
822	}
823
824	assert(coldp != NULL);
825	m->coldp = coldp;
826	if (ISSET(st, stopst))
827	return(p+1);
828	else
829	return(NULL);
830	}
831
832	/*
833	- slow - step through the string more deliberately
834	== static char slow(struct match m, char *start, \
835	== char *stop, sopno startst, sopno stopst);
836	*/
837	static char * /* where it ended */
838	slow(m, start, stop, startst, stopst)
839	struct match *m;
840	char *start;
841	char *stop;
842	sopno startst;
843	sopno stopst;
844	{
845	states st = m->st;
846	states empty = m->empty;
847	states tmp = m->tmp;
848	char *p = start;
849	int c = (start == m->beginp) ? OUT : *(start-1);
850	int lastc; /* previous c */
851	int flagch;
852	int i;
853	char matchp; / last p at which a match ended */
854
855	AT("slow", start, stop, startst, stopst);
856	CLEAR(st);
857	SET1(st, startst);
858	SP("sstart", st, *p);
859	st = step(m->g, startst, stopst, st, NOTHING, st);
860	matchp = NULL;
861	for (;;) {
862	/* next character */
863	lastc = c;
864	c = (p == m->endp) ? OUT : *p;
865
866	/* is there an EOL and/or BOL between lastc and c? */
867	flagch = '\0';
868	i = 0;
869	if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) \|\|
870	(lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
871	flagch = BOL;
872	i = m->g->nbol;
873	}
874	if ( (c == '\n' && m->g->cflags&REG_NEWLINE) \|\|
875	(c == OUT && !(m->eflags&REG_NOTEOL)) ) {
876	flagch = (flagch == BOL) ? BOLEOL : EOL;
877	i += m->g->neol;
878	}
879	if (i != 0) {
880	for (; i > 0; i--)
881	st = step(m->g, startst, stopst, st, flagch, st);
882	SP("sboleol", st, c);
883	}
884
885	/* how about a word boundary? */
886	if ( (flagch == BOL \|\| (lastc != OUT && !ISWORD(lastc))) &&
887	(c != OUT && ISWORD(c)) ) {
888	flagch = BOW;
889	}
890	if ( (lastc != OUT && ISWORD(lastc)) &&
891	(flagch == EOL \|\| (c != OUT && !ISWORD(c))) ) {
892	flagch = EOW;
893	}
894	if (flagch == BOW \|\| flagch == EOW) {
895	st = step(m->g, startst, stopst, st, flagch, st);
896	SP("sboweow", st, c);
897	}
898
899	/* are we done? */
900	if (ISSET(st, stopst))
901	matchp = p;
902	if (EQ(st, empty) \|\| p == stop)
903	break; /* NOTE BREAK OUT */
904
905	/* no, we must deal with this character */
906	ASSIGN(tmp, st);
907	ASSIGN(st, empty);
908	assert(c != OUT);
909	st = step(m->g, startst, stopst, tmp, c, st);
910	SP("saft", st, c);
911	assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
912	p++;
913	}
914
915	return(matchp);
916	}
917
918
919	/*
920	- step - map set of states reachable before char to set reachable after
921	== static states step(struct re_guts *g, sopno start, sopno stop, \
922	== states bef, int ch, states aft);
923	== #define BOL (OUT+1)
924	== #define EOL (BOL+1)
925	== #define BOLEOL (BOL+2)
926	== #define NOTHING (BOL+3)
927	== #define BOW (BOL+4)
928	== #define EOW (BOL+5)
929	== #define CODEMAX (BOL+5) // highest code used
930	== #define NONCHAR(c) ((c) > CHAR_MAX)
931	== #define NNONCHAR (CODEMAX-CHAR_MAX)
932	*/
933	static states
934	step(g, start, stop, bef, ch, aft)
935	struct re_guts *g;
936	sopno start; /* start state within strip */
937	sopno stop; /* state after stop state within strip */
938	states bef; /* states reachable before */
939	int ch; /* character or NONCHAR code */
940	states aft; /* states already known reachable after */
941	{
942	cset *cs;
943	sop s;
944	sopno pc;
945	onestate here; /* note, macros know this name */
946	sopno look;
947	int i;
948
949	for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
950	s = g->strip[pc];
951	switch (OP(s)) {
952	case OEND:
953	assert(pc == stop-1);
954	break;
955	case OCHAR:
956	/* only characters can match */
957	assert(!NONCHAR(ch) \|\| ch != (char)OPND(s));
958	if (ch == (char)OPND(s))
959	FWD(aft, bef, 1);
960	break;
961	case OBOL:
962	if (ch == BOL \|\| ch == BOLEOL)
963	FWD(aft, bef, 1);
964	break;
965	case OEOL:
966	if (ch == EOL \|\| ch == BOLEOL)
967	FWD(aft, bef, 1);
968	break;
969	case OBOW:
970	if (ch == BOW)
971	FWD(aft, bef, 1);
972	break;
973	case OEOW:
974	if (ch == EOW)
975	FWD(aft, bef, 1);
976	break;
977	case OANY:
978	if (!NONCHAR(ch))
979	FWD(aft, bef, 1);
980	break;
981	case OANYOF:
982	cs = &g->sets[OPND(s)];
983	if (!NONCHAR(ch) && CHIN(cs, ch))
984	FWD(aft, bef, 1);
985	break;
986	case OBACK_: /* ignored here */
987	case O_BACK:
988	FWD(aft, aft, 1);
989	break;
990	case OPLUS_: /* forward, this is just an empty */
991	FWD(aft, aft, 1);
992	break;
993	case O_PLUS: /* both forward and back */
994	FWD(aft, aft, 1);
995	i = ISSETBACK(aft, OPND(s));
996	BACK(aft, aft, OPND(s));
997	if (!i && ISSETBACK(aft, OPND(s))) {
998	/* oho, must reconsider loop body */
999	pc -= OPND(s) + 1;
1000	INIT(here, pc);
1001	}
1002	break;
1003	case OQUEST_: /* two branches, both forward */
1004	FWD(aft, aft, 1);
1005	FWD(aft, aft, OPND(s));
1006	break;
1007	case O_QUEST: /* just an empty */
1008	FWD(aft, aft, 1);
1009	break;
1010	case OLPAREN: /* not significant here */
1011	case ORPAREN:
1012	FWD(aft, aft, 1);
1013	break;
1014	case OCH_: /* mark the first two branches */
1015	FWD(aft, aft, 1);
1016	assert(OP(g->strip[pc+OPND(s)]) == OOR2);
1017	FWD(aft, aft, OPND(s));
1018	break;
1019	case OOR1: /* done a branch, find the O_CH */
1020	if (ISSTATEIN(aft, here)) {
1021	for (look = 1;
1022	OP(s = g->strip[pc+look]) != O_CH;
1023	look += OPND(s))
1024	assert(OP(s) == OOR2);
1025	FWD(aft, aft, look);
1026	}
1027	break;
1028	case OOR2: /* propagate OCH_'s marking */
1029	FWD(aft, aft, 1);
1030	if (OP(g->strip[pc+OPND(s)]) != O_CH) {
1031	assert(OP(g->strip[pc+OPND(s)]) == OOR2);
1032	FWD(aft, aft, OPND(s));
1033	}
1034	break;
1035	case O_CH: /* just empty */
1036	FWD(aft, aft, 1);
1037	break;
1038	default: /* ooooops... */
1039	assert(nope);
1040	break;
1041	}
1042	}
1043
1044	return(aft);
1045	}
1046
1047	#ifdef REDEBUG
1048	/*
1049	- print - print a set of states
1050	== #ifdef REDEBUG
1051	== static void print(struct match m, char caption, states st, \
1052	== int ch, FILE *d);
1053	== #endif
1054	*/
1055	static void
1056	print(m, caption, st, ch, d)
1057	struct match *m;
1058	char *caption;
1059	states st;
1060	int ch;
1061	FILE *d;
1062	{
1063	struct re_guts *g = m->g;
1064	int i;
1065	int first = 1;
1066
1067	if (!(m->eflags&REG_TRACE))
1068	return;
1069
1070	fprintf(d, "%s", caption);
1071	if (ch != '\0')
1072	fprintf(d, " %s", pchar(ch));
1073	for (i = 0; i < g->nstates; i++)
1074	if (ISSET(st, i)) {
1075	fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
1076	first = 0;
1077	}
1078	fprintf(d, "\n");
1079	}
1080
1081	/*
1082	- at - print current situation
1083	== #ifdef REDEBUG
1084	== static void at(struct match m, char title, char start, char stop, \
1085	== sopno startst, sopno stopst);
1086	== #endif
1087	*/
1088	static void
1089	at(m, title, start, stop, startst, stopst)
1090	struct match *m;
1091	char *title;
1092	char *start;
1093	char *stop;
1094	sopno startst;
1095	sopno stopst;
1096	{
1097	if (!(m->eflags&REG_TRACE))
1098	return;
1099
1100	printf("%s %s-", title, pchar(*start));
1101	printf("%s ", pchar(*stop));
1102	printf("%ld-%ld\n", (long)startst, (long)stopst);
1103	}
1104
1105	#ifndef PCHARDONE
1106	#define PCHARDONE /* never again */
1107	/*
1108	- pchar - make a character printable
1109	== #ifdef REDEBUG
1110	== static char *pchar(int ch);
1111	== #endif
1112	*
1113	* Is this identical to regchar() over in debug.c? Well, yes. But a
1114	* duplicate here avoids having a debugging-capable regexec.o tied to
1115	* a matching debug.o, and this is convenient. It all disappears in
1116	* the non-debug compilation anyway, so it doesn't matter much.
1117	*/
1118	static char * /* -> representation */
1119	pchar(ch)
1120	int ch;
1121	{
1122	static char pbuf[10];
1123
1124	if (isprint((uch)ch) \|\| ch == ' ')
1125	sprintf(pbuf, "%c", ch);
1126	else
1127	sprintf(pbuf, "\\%o", ch);
1128	return(pbuf);
1129	}
1130	#endif
1131	#endif
1132
1133	#undef matcher
1134	#undef fast
1135	#undef slow
1136	#undef dissect
1137	#undef backref
1138	#undef step
1139	#undef print
1140	#undef at
1141	#undef match

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: trunk/libs/newlib/src/newlib/libc/posix/engine.c @ 543

Download in other formats: