Annotation of src/lib/libc/regex/regexec.c, Revision 1.20
1.20 ! junyoung 1: /* $NetBSD: regexec.c,v 1.19 2007/02/08 05:44:18 junyoung Exp $ */
1.6 cgd 2:
1.4 cgd 3: /*-
4: * Copyright (c) 1992, 1993, 1994
5: * The Regents of the University of California. All rights reserved.
6: *
7: * This code is derived from software contributed to Berkeley by
8: * Henry Spencer.
9: *
10: * Redistribution and use in source and binary forms, with or without
11: * modification, are permitted provided that the following conditions
12: * are met:
13: * 1. Redistributions of source code must retain the above copyright
14: * notice, this list of conditions and the following disclaimer.
15: * 2. Redistributions in binary form must reproduce the above copyright
16: * notice, this list of conditions and the following disclaimer in the
17: * documentation and/or other materials provided with the distribution.
1.17 agc 18: * 3. Neither the name of the University nor the names of its contributors
19: * may be used to endorse or promote products derived from this software
20: * without specific prior written permission.
21: *
22: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32: * SUCH DAMAGE.
33: *
34: * @(#)regexec.c 8.3 (Berkeley) 3/20/94
35: */
36:
37: /*-
38: * Copyright (c) 1992, 1993, 1994 Henry Spencer.
39: *
40: * This code is derived from software contributed to Berkeley by
41: * Henry Spencer.
42: *
43: * Redistribution and use in source and binary forms, with or without
44: * modification, are permitted provided that the following conditions
45: * are met:
46: * 1. Redistributions of source code must retain the above copyright
47: * notice, this list of conditions and the following disclaimer.
48: * 2. Redistributions in binary form must reproduce the above copyright
49: * notice, this list of conditions and the following disclaimer in the
50: * documentation and/or other materials provided with the distribution.
1.4 cgd 51: * 3. All advertising materials mentioning features or use of this software
52: * must display the following acknowledgement:
53: * This product includes software developed by the University of
54: * California, Berkeley and its contributors.
55: * 4. Neither the name of the University nor the names of its contributors
56: * may be used to endorse or promote products derived from this software
57: * without specific prior written permission.
58: *
59: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
60: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
61: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
62: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
63: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
64: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
65: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
66: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
67: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
68: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
69: * SUCH DAMAGE.
70: *
71: * @(#)regexec.c 8.3 (Berkeley) 3/20/94
72: */
73:
1.8 christos 74: #include <sys/cdefs.h>
1.4 cgd 75: #if defined(LIBC_SCCS) && !defined(lint)
1.6 cgd 76: #if 0
1.4 cgd 77: static char sccsid[] = "@(#)regexec.c 8.3 (Berkeley) 3/20/94";
1.6 cgd 78: #else
1.20 ! junyoung 79: __RCSID("$NetBSD: regexec.c,v 1.19 2007/02/08 05:44:18 junyoung Exp $");
1.6 cgd 80: #endif
1.4 cgd 81: #endif /* LIBC_SCCS and not lint */
82:
1.1 jtc 83: /*
84: * the outer shell of regexec()
85: *
86: * This file includes engine.c *twice*, after muchos fiddling with the
87: * macros that code uses. This lets the same code operate on two different
88: * representations for state sets.
89: */
1.9 jtc 90: #include "namespace.h"
1.1 jtc 91: #include <sys/types.h>
1.13 lukem 92:
93: #include <assert.h>
94: #include <ctype.h>
95: #include <limits.h>
1.1 jtc 96: #include <stdio.h>
97: #include <stdlib.h>
98: #include <string.h>
1.20 ! junyoung 99: #include <regex.h>
1.9 jtc 100:
101: #ifdef __weak_alias
1.15 mycroft 102: __weak_alias(regexec,_regexec)
1.9 jtc 103: #endif
1.1 jtc 104:
105: #include "utils.h"
106: #include "regex2.h"
107:
108: /* macros for manipulating states, small version */
1.12 drochner 109: #define states unsigned long
110: #define states1 unsigned long /* for later use in regexec() decision */
1.1 jtc 111: #define CLEAR(v) ((v) = 0)
1.12 drochner 112: #define SET0(v, n) ((v) &= ~((unsigned long)1 << (n)))
113: #define SET1(v, n) ((v) |= (unsigned long)1 << (n))
114: #define ISSET(v, n) (((v) & ((unsigned long)1 << (n))) != 0)
1.1 jtc 115: #define ASSIGN(d, s) ((d) = (s))
116: #define EQ(a, b) ((a) == (b))
1.12 drochner 117: #define STATEVARS int dummy /* dummy version */
1.1 jtc 118: #define STATESETUP(m, n) /* nothing */
119: #define STATETEARDOWN(m) /* nothing */
120: #define SETUP(v) ((v) = 0)
1.12 drochner 121: #define onestate unsigned long
122: #define INIT(o, n) ((o) = (unsigned long)1 << (n))
1.7 cgd 123: #define INC(o) ((o) <<= 1)
1.5 cgd 124: #define ISSTATEIN(v, o) (((v) & (o)) != 0)
1.1 jtc 125: /* some abbreviations; note that some of these know variable names! */
126: /* do "if I'm here, I can also be there" etc without branches */
1.12 drochner 127: #define FWD(dst, src, n) ((dst) |= ((unsigned long)(src)&(here)) << (n))
128: #define BACK(dst, src, n) ((dst) |= ((unsigned long)(src)&(here)) >> (n))
129: #define ISSETBACK(v, n) (((v) & ((unsigned long)here >> (n))) != 0)
1.1 jtc 130: /* function names */
131: #define SNAMES /* engine.c looks after details */
132:
133: #include "engine.c"
134:
135: /* now undo things */
136: #undef states
137: #undef CLEAR
138: #undef SET0
139: #undef SET1
140: #undef ISSET
141: #undef ASSIGN
142: #undef EQ
143: #undef STATEVARS
144: #undef STATESETUP
145: #undef STATETEARDOWN
146: #undef SETUP
147: #undef onestate
148: #undef INIT
149: #undef INC
150: #undef ISSTATEIN
151: #undef FWD
152: #undef BACK
153: #undef ISSETBACK
154: #undef SNAMES
155:
156: /* macros for manipulating states, large version */
157: #define states char *
1.11 christos 158: #define CLEAR(v) memset(v, 0, (size_t)m->g->nstates)
1.1 jtc 159: #define SET0(v, n) ((v)[n] = 0)
160: #define SET1(v, n) ((v)[n] = 1)
161: #define ISSET(v, n) ((v)[n])
1.11 christos 162: #define ASSIGN(d, s) memcpy(d, s, (size_t)m->g->nstates)
163: #define EQ(a, b) (memcmp(a, b, (size_t)m->g->nstates) == 0)
1.12 drochner 164: #define STATEVARS int vn; char *space
1.16 christos 165: #define STATESETUP(m, nv) \
166: if (((m)->space = malloc((size_t)((nv)*(m)->g->nstates))) == NULL) \
167: return(REG_ESPACE); \
168: else \
169: (m)->vn = 0
170:
171: #define STATETEARDOWN(m) { free((m)->space); m->space = NULL; }
1.11 christos 172: #define SETUP(v) ((v) = &m->space[(size_t)(m->vn++ * m->g->nstates)])
1.12 drochner 173: #define onestate int
1.1 jtc 174: #define INIT(o, n) ((o) = (n))
175: #define INC(o) ((o)++)
176: #define ISSTATEIN(v, o) ((v)[o])
177: /* some abbreviations; note that some of these know variable names! */
178: /* do "if I'm here, I can also be there" etc without branches */
179: #define FWD(dst, src, n) ((dst)[here+(n)] |= (src)[here])
180: #define BACK(dst, src, n) ((dst)[here-(n)] |= (src)[here])
181: #define ISSETBACK(v, n) ((v)[here - (n)])
182: /* function names */
183: #define LNAMES /* flag */
184:
185: #include "engine.c"
186:
187: /*
188: - regexec - interface for matching
1.2 jtc 189: = extern int regexec(const regex_t *, const char *, size_t, \
190: = regmatch_t [], int);
1.1 jtc 191: = #define REG_NOTBOL 00001
192: = #define REG_NOTEOL 00002
193: = #define REG_STARTEND 00004
194: = #define REG_TRACE 00400 // tracing of execution
195: = #define REG_LARGE 01000 // force large representation
196: = #define REG_BACKR 02000 // force use of backref code
197: *
198: * We put this here so we can exploit knowledge of the state representation
199: * when choosing which matcher to call. Also, by this point the matchers
200: * have been prototyped.
201: */
202: int /* 0 success, REG_NOMATCH failure */
1.19 junyoung 203: regexec(
204: const regex_t *preg,
205: const char *string,
206: size_t nmatch,
207: regmatch_t pmatch[],
208: int eflags)
1.1 jtc 209: {
1.10 perry 210: struct re_guts *g = preg->re_g;
1.11 christos 211: char *s;
1.1 jtc 212: #ifdef REDEBUG
213: # define GOODFLAGS(f) (f)
214: #else
215: # define GOODFLAGS(f) ((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND))
1.13 lukem 216: #endif
217:
218: _DIAGASSERT(preg != NULL);
219: _DIAGASSERT(string != NULL);
1.1 jtc 220:
221: if (preg->re_magic != MAGIC1 || g->magic != MAGIC2)
222: return(REG_BADPAT);
223: assert(!(g->iflags&BAD));
224: if (g->iflags&BAD) /* backstop for no-debug case */
225: return(REG_BADPAT);
1.3 jtc 226: eflags = GOODFLAGS(eflags);
1.1 jtc 227:
1.18 christos 228: s = __UNCONST(string);
1.11 christos 229:
1.1 jtc 230: if (g->nstates <= CHAR_BIT*sizeof(states1) && !(eflags®_LARGE))
1.11 christos 231: return(smatcher(g, s, nmatch, pmatch, eflags));
1.1 jtc 232: else
1.11 christos 233: return(lmatcher(g, s, nmatch, pmatch, eflags));
1.1 jtc 234: }
CVSweb <webmaster@jp.NetBSD.org>