Annotation of parser3/src/lib/pcre/study.c, revision 1.1.14.1
1.1 paf 1: /*************************************************
2: * Perl-Compatible Regular Expressions *
3: *************************************************/
4:
5: /*
6: This is a library of functions to support regular expressions whose syntax
7: and semantics are as close as possible to those of the Perl 5 language. See
8: the file Tech.Notes for some information on the internals.
9:
10: Written by: Philip Hazel <ph10@cam.ac.uk>
11:
12: Copyright (c) 1997-1999 University of Cambridge
13:
14: -----------------------------------------------------------------------------
15: Permission is granted to anyone to use this software for any purpose on any
16: computer system, and to redistribute it freely, subject to the following
17: restrictions:
18:
19: 1. This software is distributed in the hope that it will be useful,
20: but WITHOUT ANY WARRANTY; without even the implied warranty of
21: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
22:
23: 2. The origin of this software must not be misrepresented, either by
24: explicit claim or by omission.
25:
26: 3. Altered versions must be plainly marked as such, and must not be
27: misrepresented as being the original software.
28:
29: 4. If PCRE is embedded in any software that is released under the GNU
30: General Purpose Licence (GPL), then the terms of that licence shall
31: supersede any condition above with which it is incompatible.
32: -----------------------------------------------------------------------------
33: */
34:
35:
36: /* Include the internals header, which itself includes Standard C headers plus
37: the external pcre header. */
38:
39: #include "internal.h"
40:
41:
42:
43: /*************************************************
44: * Set a bit and maybe its alternate case *
45: *************************************************/
46:
47: /* Given a character, set its bit in the table, and also the bit for the other
48: version of a letter if we are caseless.
49:
50: Arguments:
51: start_bits points to the bit map
52: c is the character
53: caseless the caseless flag
54: cd the block with char table pointers
55:
56: Returns: nothing
57: */
58:
59: static void
60: set_bit(uschar *start_bits, int c, BOOL caseless, compile_data *cd)
61: {
62: start_bits[c/8] |= (1 << (c&7));
63: if (caseless && (cd->ctypes[c] & ctype_letter) != 0)
64: start_bits[cd->fcc[c]/8] |= (1 << (cd->fcc[c]&7));
65: }
66:
67:
68:
69: /*************************************************
70: * Create bitmap of starting chars *
71: *************************************************/
72:
73: /* This function scans a compiled unanchored expression and attempts to build a
74: bitmap of the set of initial characters. If it can't, it returns FALSE. As time
75: goes by, we may be able to get more clever at doing this.
76:
77: Arguments:
78: code points to an expression
79: start_bits points to a 32-byte table, initialized to 0
80: caseless the current state of the caseless flag
81: cd the block with char table pointers
82:
83: Returns: TRUE if table built, FALSE otherwise
84: */
85:
86: static BOOL
87: set_start_bits(const uschar *code, uschar *start_bits, BOOL caseless,
88: compile_data *cd)
89: {
90: register int c;
91:
92: /* This next statement and the later reference to dummy are here in order to
93: trick the optimizer of the IBM C compiler for OS/2 into generating correct
94: code. Apparently IBM isn't going to fix the problem, and we would rather not
95: disable optimization (in this module it actually makes a big difference, and
96: the pcre module can use all the optimization it can get). */
97:
98: volatile int dummy;
99:
100: do
101: {
102: const uschar *tcode = code + 3;
103: BOOL try_next = TRUE;
104:
105: while (try_next)
106: {
107: try_next = FALSE;
108:
109: /* If a branch starts with a bracket or a positive lookahead assertion,
110: recurse to set bits from within them. That's all for this branch. */
111:
112: if ((int)*tcode >= OP_BRA || *tcode == OP_ASSERT)
113: {
114: if (!set_start_bits(tcode, start_bits, caseless, cd))
115: return FALSE;
116: }
117:
118: else switch(*tcode)
119: {
120: default:
121: return FALSE;
122:
123: /* Skip over lookbehind and negative lookahead assertions */
124:
125: case OP_ASSERT_NOT:
126: case OP_ASSERTBACK:
127: case OP_ASSERTBACK_NOT:
128: try_next = TRUE;
129: do tcode += (tcode[1] << 8) + tcode[2]; while (*tcode == OP_ALT);
130: tcode += 3;
131: break;
132:
133: /* Skip over an option setting, changing the caseless flag */
134:
135: case OP_OPT:
136: caseless = (tcode[1] & PCRE_CASELESS) != 0;
137: tcode += 2;
138: try_next = TRUE;
139: break;
140:
141: /* BRAZERO does the bracket, but carries on. */
142:
143: case OP_BRAZERO:
144: case OP_BRAMINZERO:
145: if (!set_start_bits(++tcode, start_bits, caseless, cd))
146: return FALSE;
147: dummy = 1;
148: do tcode += (tcode[1] << 8) + tcode[2]; while (*tcode == OP_ALT);
149: tcode += 3;
150: try_next = TRUE;
151: break;
152:
153: /* Single-char * or ? sets the bit and tries the next item */
154:
155: case OP_STAR:
156: case OP_MINSTAR:
157: case OP_QUERY:
158: case OP_MINQUERY:
159: set_bit(start_bits, tcode[1], caseless, cd);
160: tcode += 2;
161: try_next = TRUE;
162: break;
163:
164: /* Single-char upto sets the bit and tries the next */
165:
166: case OP_UPTO:
167: case OP_MINUPTO:
168: set_bit(start_bits, tcode[3], caseless, cd);
169: tcode += 4;
170: try_next = TRUE;
171: break;
172:
173: /* At least one single char sets the bit and stops */
174:
175: case OP_EXACT: /* Fall through */
176: tcode++;
177:
178: case OP_CHARS: /* Fall through */
179: tcode++;
180:
181: case OP_PLUS:
182: case OP_MINPLUS:
183: set_bit(start_bits, tcode[1], caseless, cd);
184: break;
185:
186: /* Single character type sets the bits and stops */
187:
188: case OP_NOT_DIGIT:
189: for (c = 0; c < 32; c++)
190: start_bits[c] |= ~cd->cbits[c+cbit_digit];
191: break;
192:
193: case OP_DIGIT:
194: for (c = 0; c < 32; c++)
195: start_bits[c] |= cd->cbits[c+cbit_digit];
196: break;
197:
198: case OP_NOT_WHITESPACE:
199: for (c = 0; c < 32; c++)
200: start_bits[c] |= ~cd->cbits[c+cbit_space];
201: break;
202:
203: case OP_WHITESPACE:
204: for (c = 0; c < 32; c++)
205: start_bits[c] |= cd->cbits[c+cbit_space];
206: break;
207:
208: case OP_NOT_WORDCHAR:
209: for (c = 0; c < 32; c++)
210: start_bits[c] |= ~(cd->cbits[c] | cd->cbits[c+cbit_word]);
211: break;
212:
213: case OP_WORDCHAR:
214: for (c = 0; c < 32; c++)
215: start_bits[c] |= (cd->cbits[c] | cd->cbits[c+cbit_word]);
216: break;
217:
218: /* One or more character type fudges the pointer and restarts, knowing
219: it will hit a single character type and stop there. */
220:
221: case OP_TYPEPLUS:
222: case OP_TYPEMINPLUS:
223: tcode++;
224: try_next = TRUE;
225: break;
226:
227: case OP_TYPEEXACT:
228: tcode += 3;
229: try_next = TRUE;
230: break;
231:
232: /* Zero or more repeats of character types set the bits and then
233: try again. */
234:
235: case OP_TYPEUPTO:
236: case OP_TYPEMINUPTO:
237: tcode += 2; /* Fall through */
238:
239: case OP_TYPESTAR:
240: case OP_TYPEMINSTAR:
241: case OP_TYPEQUERY:
242: case OP_TYPEMINQUERY:
243: switch(tcode[1])
244: {
245: case OP_NOT_DIGIT:
246: for (c = 0; c < 32; c++)
247: start_bits[c] |= ~cd->cbits[c+cbit_digit];
248: break;
249:
250: case OP_DIGIT:
251: for (c = 0; c < 32; c++)
252: start_bits[c] |= cd->cbits[c+cbit_digit];
253: break;
254:
255: case OP_NOT_WHITESPACE:
256: for (c = 0; c < 32; c++)
257: start_bits[c] |= ~cd->cbits[c+cbit_space];
258: break;
259:
260: case OP_WHITESPACE:
261: for (c = 0; c < 32; c++)
262: start_bits[c] |= cd->cbits[c+cbit_space];
263: break;
264:
265: case OP_NOT_WORDCHAR:
266: for (c = 0; c < 32; c++)
267: start_bits[c] |= ~(cd->cbits[c] | cd->cbits[c+cbit_word]);
268: break;
269:
270: case OP_WORDCHAR:
271: for (c = 0; c < 32; c++)
272: start_bits[c] |= (cd->cbits[c] | cd->cbits[c+cbit_word]);
273: break;
274: }
275:
276: tcode += 2;
277: try_next = TRUE;
278: break;
279:
280: /* Character class: set the bits and either carry on or not,
281: according to the repeat count. */
282:
283: case OP_CLASS:
284: {
285: tcode++;
286: for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];
287: tcode += 32;
288: switch (*tcode)
289: {
290: case OP_CRSTAR:
291: case OP_CRMINSTAR:
292: case OP_CRQUERY:
293: case OP_CRMINQUERY:
294: tcode++;
295: try_next = TRUE;
296: break;
297:
298: case OP_CRRANGE:
299: case OP_CRMINRANGE:
300: if (((tcode[1] << 8) + tcode[2]) == 0)
301: {
302: tcode += 5;
303: try_next = TRUE;
304: }
305: break;
306: }
307: }
308: break; /* End of class handling */
309:
310: } /* End of switch */
311: } /* End of try_next loop */
312:
313: code += (code[1] << 8) + code[2]; /* Advance to next branch */
314: }
315: while (*code == OP_ALT);
316: return TRUE;
317: }
318:
319:
320:
321: /*************************************************
322: * Study a compiled expression *
323: *************************************************/
324:
325: /* This function is handed a compiled expression that it must study to produce
326: information that will speed up the matching. It returns a pcre_extra block
327: which then gets handed back to pcre_exec().
328:
329: Arguments:
330: re points to the compiled expression
331: options contains option bits
332: errorptr points to where to place error messages;
333: set NULL unless error
334:
335: Returns: pointer to a pcre_extra block,
336: NULL on error or if no optimization possible
337: */
338:
339: pcre_extra *
1.1.14.1! paf 340: pcre_study(const pcre *external_re, int options, const char* *errorptr)
1.1 paf 341: {
342: uschar start_bits[32];
343: real_pcre_extra *extra;
344: const real_pcre *re = (const real_pcre *)external_re;
345: compile_data compile_block;
346:
347: *errorptr = NULL;
348:
349: if (re == NULL || re->magic_number != MAGIC_NUMBER)
350: {
351: *errorptr = "argument is not a compiled regular expression";
352: return NULL;
353: }
354:
355: if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
356: {
357: *errorptr = "unknown or incorrect option bit(s) set";
358: return NULL;
359: }
360:
361: /* For an anchored pattern, or an unchored pattern that has a first char, or a
362: multiline pattern that matches only at "line starts", no further processing at
363: present. */
364:
365: if ((re->options & (PCRE_ANCHORED|PCRE_FIRSTSET|PCRE_STARTLINE)) != 0)
366: return NULL;
367:
368: /* Set the character tables in the block which is passed around */
369:
370: compile_block.lcc = re->tables + lcc_offset;
371: compile_block.fcc = re->tables + fcc_offset;
372: compile_block.cbits = re->tables + cbits_offset;
373: compile_block.ctypes = re->tables + ctypes_offset;
374:
375: /* See if we can find a fixed set of initial characters for the pattern. */
376:
377: memset(start_bits, 0, 32 * sizeof(uschar));
378: if (!set_start_bits(re->code, start_bits, (re->options & PCRE_CASELESS) != 0,
379: &compile_block)) return NULL;
380:
381: /* Get an "extra" block and put the information therein. */
382:
383: extra = (real_pcre_extra *)(pcre_malloc)(sizeof(real_pcre_extra));
384:
385: if (extra == NULL)
386: {
387: *errorptr = "failed to get memory";
388: return NULL;
389: }
390:
391: extra->options = PCRE_STUDY_MAPPED;
392: memcpy(extra->start_bits, start_bits, sizeof(start_bits));
393:
394: return (pcre_extra *)extra;
395: }
396:
397: /* End of study.c */
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to study.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / parser3 / src / lib / pcre