xref: /freebsd/lib/libc/regex/regexec.c (revision 85999a0155e389415cc476110fd5614baf543a55)
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  *	@(#)regexec.c	8.3 (Berkeley) 3/20/94
34  */
35 
36 #if defined(LIBC_SCCS) && !defined(lint)
37 static char sccsid[] = "@(#)regexec.c	8.3 (Berkeley) 3/20/94";
38 #endif /* LIBC_SCCS and not lint */
39 #include <sys/cdefs.h>
40 __FBSDID("$FreeBSD$");
41 
42 /*
43  * the outer shell of regexec()
44  *
45  * This file includes engine.c three times, after muchos fiddling with the
46  * macros that code uses.  This lets the same code operate on two different
47  * representations for state sets and characters.
48  */
49 #include <sys/types.h>
50 #include <stdio.h>
51 #include <stdlib.h>
52 #include <string.h>
53 #include <limits.h>
54 #include <ctype.h>
55 #include <regex.h>
56 #include <wchar.h>
57 #include <wctype.h>
58 
59 #include "utils.h"
60 #include "regex2.h"
61 
62 static int nope __unused = 0;	/* for use in asserts; shuts lint up */
63 
64 static __inline size_t
65 xmbrtowc(wi, s, n, mbs, dummy)
66 wint_t *wi;
67 const char *s;
68 size_t n;
69 mbstate_t *mbs;
70 wint_t dummy;
71 {
72 	size_t nr;
73 	wchar_t wc;
74 
75 	nr = mbrtowc(&wc, s, n, mbs);
76 	if (wi != NULL)
77 		*wi = wc;
78 	if (nr == 0)
79 		return (1);
80 	else if (nr == (size_t)-1 || nr == (size_t)-2) {
81 		memset(mbs, 0, sizeof(*mbs));
82 		if (wi != NULL)
83 			*wi = dummy;
84 		return (1);
85 	} else
86                 return (nr);
87 }
88 
89 static __inline size_t
90 xmbrtowc_dummy(wi, s, n, mbs, dummy)
91 wint_t *wi;
92 const char *s;
93 size_t n __unused;
94 mbstate_t *mbs __unused;
95 wint_t dummy __unused;
96 {
97 
98 	if (wi != NULL)
99 		*wi = (unsigned char)*s;
100 	return (1);
101 }
102 
103 /* macros for manipulating states, small version */
104 #define	states	long
105 #define	states1	states		/* for later use in regexec() decision */
106 #define	CLEAR(v)	((v) = 0)
107 #define	SET0(v, n)	((v) &= ~((unsigned long)1 << (n)))
108 #define	SET1(v, n)	((v) |= (unsigned long)1 << (n))
109 #define	ISSET(v, n)	(((v) & ((unsigned long)1 << (n))) != 0)
110 #define	ASSIGN(d, s)	((d) = (s))
111 #define	EQ(a, b)	((a) == (b))
112 #define	STATEVARS	long dummy	/* dummy version */
113 #define	STATESETUP(m, n)	/* nothing */
114 #define	STATETEARDOWN(m)	/* nothing */
115 #define	SETUP(v)	((v) = 0)
116 #define	onestate	long
117 #define	INIT(o, n)	((o) = (unsigned long)1 << (n))
118 #define	INC(o)	((o) <<= 1)
119 #define	ISSTATEIN(v, o)	(((v) & (o)) != 0)
120 /* some abbreviations; note that some of these know variable names! */
121 /* do "if I'm here, I can also be there" etc without branches */
122 #define	FWD(dst, src, n)	((dst) |= ((unsigned long)(src)&(here)) << (n))
123 #define	BACK(dst, src, n)	((dst) |= ((unsigned long)(src)&(here)) >> (n))
124 #define	ISSETBACK(v, n)	(((v) & ((unsigned long)here >> (n))) != 0)
125 /* no multibyte support */
126 #define	XMBRTOWC	xmbrtowc_dummy
127 #define	ZAPSTATE(mbs)	((void)(mbs))
128 /* function names */
129 #define SNAMES			/* engine.c looks after details */
130 
131 #include "engine.c"
132 
133 /* now undo things */
134 #undef	states
135 #undef	CLEAR
136 #undef	SET0
137 #undef	SET1
138 #undef	ISSET
139 #undef	ASSIGN
140 #undef	EQ
141 #undef	STATEVARS
142 #undef	STATESETUP
143 #undef	STATETEARDOWN
144 #undef	SETUP
145 #undef	onestate
146 #undef	INIT
147 #undef	INC
148 #undef	ISSTATEIN
149 #undef	FWD
150 #undef	BACK
151 #undef	ISSETBACK
152 #undef	SNAMES
153 #undef	XMBRTOWC
154 #undef	ZAPSTATE
155 
156 /* macros for manipulating states, large version */
157 #define	states	char *
158 #define	CLEAR(v)	memset(v, 0, m->g->nstates)
159 #define	SET0(v, n)	((v)[n] = 0)
160 #define	SET1(v, n)	((v)[n] = 1)
161 #define	ISSET(v, n)	((v)[n])
162 #define	ASSIGN(d, s)	memcpy(d, s, m->g->nstates)
163 #define	EQ(a, b)	(memcmp(a, b, m->g->nstates) == 0)
164 #define	STATEVARS	long vn; char *space
165 #define	STATESETUP(m, nv)	{ (m)->space = malloc((nv)*(m)->g->nstates); \
166 				if ((m)->space == NULL) return(REG_ESPACE); \
167 				(m)->vn = 0; }
168 #define	STATETEARDOWN(m)	{ free((m)->space); }
169 #define	SETUP(v)	((v) = &m->space[m->vn++ * m->g->nstates])
170 #define	onestate	long
171 #define	INIT(o, n)	((o) = (n))
172 #define	INC(o)	((o)++)
173 #define	ISSTATEIN(v, o)	((v)[o])
174 /* some abbreviations; note that some of these know variable names! */
175 /* do "if I'm here, I can also be there" etc without branches */
176 #define	FWD(dst, src, n)	((dst)[here+(n)] |= (src)[here])
177 #define	BACK(dst, src, n)	((dst)[here-(n)] |= (src)[here])
178 #define	ISSETBACK(v, n)	((v)[here - (n)])
179 /* no multibyte support */
180 #define	XMBRTOWC	xmbrtowc_dummy
181 #define	ZAPSTATE(mbs)	((void)(mbs))
182 /* function names */
183 #define	LNAMES			/* flag */
184 
185 #include "engine.c"
186 
187 /* multibyte character & large states version */
188 #undef	LNAMES
189 #undef	XMBRTOWC
190 #undef	ZAPSTATE
191 #define	XMBRTOWC	xmbrtowc
192 #define	ZAPSTATE(mbs)	memset((mbs), 0, sizeof(*(mbs)))
193 #define	MNAMES
194 
195 #include "engine.c"
196 
197 /*
198  - regexec - interface for matching
199  = extern int regexec(const regex_t *, const char *, size_t, \
200  =					regmatch_t [], int);
201  = #define	REG_NOTBOL	00001
202  = #define	REG_NOTEOL	00002
203  = #define	REG_STARTEND	00004
204  = #define	REG_TRACE	00400	// tracing of execution
205  = #define	REG_LARGE	01000	// force large representation
206  = #define	REG_BACKR	02000	// force use of backref code
207  *
208  * We put this here so we can exploit knowledge of the state representation
209  * when choosing which matcher to call.  Also, by this point the matchers
210  * have been prototyped.
211  */
212 int				/* 0 success, REG_NOMATCH failure */
213 regexec(preg, string, nmatch, pmatch, eflags)
214 const regex_t * __restrict preg;
215 const char * __restrict string;
216 size_t nmatch;
217 regmatch_t pmatch[__restrict];
218 int eflags;
219 {
220 	struct re_guts *g = preg->re_g;
221 #ifdef REDEBUG
222 #	define	GOODFLAGS(f)	(f)
223 #else
224 #	define	GOODFLAGS(f)	((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND))
225 #endif
226 
227 	if (preg->re_magic != MAGIC1 || g->magic != MAGIC2)
228 		return(REG_BADPAT);
229 	assert(!(g->iflags&BAD));
230 	if (g->iflags&BAD)		/* backstop for no-debug case */
231 		return(REG_BADPAT);
232 	eflags = GOODFLAGS(eflags);
233 
234 	if (MB_CUR_MAX > 1)
235 		return(mmatcher(g, (char *)string, nmatch, pmatch, eflags));
236 	else if (g->nstates <= CHAR_BIT*sizeof(states1) && !(eflags&REG_LARGE))
237 		return(smatcher(g, (char *)string, nmatch, pmatch, eflags));
238 	else
239 		return(lmatcher(g, (char *)string, nmatch, pmatch, eflags));
240 }
241