1 /* $Cambridge: exim/src/src/pcre/study.c,v 1.2 2005/06/15 08:57:10 ph10 Exp $ */
3 /*************************************************
4 * Perl-Compatible Regular Expressions *
5 *************************************************/
8 This is a library of functions to support regular expressions whose syntax
9 and semantics are as close as possible to those of the Perl 5 language. See
10 the file Tech.Notes for some information on the internals.
12 Written by: Philip Hazel <ph10@cam.ac.uk>
14 Copyright (c) 1997-2004 University of Cambridge
16 -----------------------------------------------------------------------------
17 Redistribution and use in source and binary forms, with or without
18 modification, are permitted provided that the following conditions are met:
20 * Redistributions of source code must retain the above copyright notice,
21 this list of conditions and the following disclaimer.
23 * Redistributions in binary form must reproduce the above copyright
24 notice, this list of conditions and the following disclaimer in the
25 documentation and/or other materials provided with the distribution.
27 * Neither the name of the University of Cambridge nor the names of its
28 contributors may be used to endorse or promote products derived from
29 this software without specific prior written permission.
31 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
32 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
33 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
34 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
35 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
36 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
37 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
38 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
39 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
41 POSSIBILITY OF SUCH DAMAGE.
42 -----------------------------------------------------------------------------
46 /* Include the internals header, which itself includes Standard C headers plus
47 the external pcre header. */
53 /*************************************************
54 * Set a bit and maybe its alternate case *
55 *************************************************/
57 /* Given a character, set its bit in the table, and also the bit for the other
58 version of a letter if we are caseless.
61 start_bits points to the bit map
63 caseless the caseless flag
64 cd the block with char table pointers
70 set_bit(uschar *start_bits, unsigned int c, BOOL caseless, compile_data *cd)
72 start_bits[c/8] |= (1 << (c&7));
73 if (caseless && (cd->ctypes[c] & ctype_letter) != 0)
74 start_bits[cd->fcc[c]/8] |= (1 << (cd->fcc[c]&7));
79 /*************************************************
80 * Create bitmap of starting chars *
81 *************************************************/
83 /* This function scans a compiled unanchored expression and attempts to build a
84 bitmap of the set of initial characters. If it can't, it returns FALSE. As time
85 goes by, we may be able to get more clever at doing this.
88 code points to an expression
89 start_bits points to a 32-byte table, initialized to 0
90 caseless the current state of the caseless flag
91 utf8 TRUE if in UTF-8 mode
92 cd the block with char table pointers
94 Returns: TRUE if table built, FALSE otherwise
98 set_start_bits(const uschar *code, uschar *start_bits, BOOL caseless,
99 BOOL utf8, compile_data *cd)
103 /* This next statement and the later reference to dummy are here in order to
104 trick the optimizer of the IBM C compiler for OS/2 into generating correct
105 code. Apparently IBM isn't going to fix the problem, and we would rather not
106 disable optimization (in this module it actually makes a big difference, and
107 the pcre module can use all the optimization it can get). */
113 const uschar *tcode = code + 1 + LINK_SIZE;
114 BOOL try_next = TRUE;
118 /* If a branch starts with a bracket or a positive lookahead assertion,
119 recurse to set bits from within them. That's all for this branch. */
121 if ((int)*tcode >= OP_BRA || *tcode == OP_ASSERT)
123 if (!set_start_bits(tcode, start_bits, caseless, utf8, cd))
133 /* Skip over callout */
136 tcode += 2 + 2*LINK_SIZE;
139 /* Skip over extended extraction bracket number */
145 /* Skip over lookbehind and negative lookahead assertions */
149 case OP_ASSERTBACK_NOT:
150 do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
151 tcode += 1+LINK_SIZE;
154 /* Skip over an option setting, changing the caseless flag */
157 caseless = (tcode[1] & PCRE_CASELESS) != 0;
161 /* BRAZERO does the bracket, but carries on. */
165 if (!set_start_bits(++tcode, start_bits, caseless, utf8, cd))
168 do tcode += GET(tcode,1); while (*tcode == OP_ALT);
169 tcode += 1+LINK_SIZE;
172 /* Single-char * or ? sets the bit and tries the next item */
178 set_bit(start_bits, tcode[1], caseless, cd);
181 if (utf8) while ((*tcode & 0xc0) == 0x80) tcode++;
185 /* Single-char upto sets the bit and tries the next */
189 set_bit(start_bits, tcode[3], caseless, cd);
192 if (utf8) while ((*tcode & 0xc0) == 0x80) tcode++;
196 /* At least one single char sets the bit and stops */
198 case OP_EXACT: /* Fall through */
205 set_bit(start_bits, tcode[1], caseless, cd);
209 /* Single character type sets the bits and stops */
212 for (c = 0; c < 32; c++)
213 start_bits[c] |= ~cd->cbits[c+cbit_digit];
218 for (c = 0; c < 32; c++)
219 start_bits[c] |= cd->cbits[c+cbit_digit];
223 case OP_NOT_WHITESPACE:
224 for (c = 0; c < 32; c++)
225 start_bits[c] |= ~cd->cbits[c+cbit_space];
230 for (c = 0; c < 32; c++)
231 start_bits[c] |= cd->cbits[c+cbit_space];
235 case OP_NOT_WORDCHAR:
236 for (c = 0; c < 32; c++)
237 start_bits[c] |= ~cd->cbits[c+cbit_word];
242 for (c = 0; c < 32; c++)
243 start_bits[c] |= cd->cbits[c+cbit_word];
247 /* One or more character type fudges the pointer and restarts, knowing
248 it will hit a single character type and stop there. */
259 /* Zero or more repeats of character types set the bits and then
264 tcode += 2; /* Fall through */
269 case OP_TYPEMINQUERY:
276 for (c = 0; c < 32; c++)
277 start_bits[c] |= ~cd->cbits[c+cbit_digit];
281 for (c = 0; c < 32; c++)
282 start_bits[c] |= cd->cbits[c+cbit_digit];
285 case OP_NOT_WHITESPACE:
286 for (c = 0; c < 32; c++)
287 start_bits[c] |= ~cd->cbits[c+cbit_space];
291 for (c = 0; c < 32; c++)
292 start_bits[c] |= cd->cbits[c+cbit_space];
295 case OP_NOT_WORDCHAR:
296 for (c = 0; c < 32; c++)
297 start_bits[c] |= ~cd->cbits[c+cbit_word];
301 for (c = 0; c < 32; c++)
302 start_bits[c] |= cd->cbits[c+cbit_word];
309 /* Character class where all the information is in a bit map: set the
310 bits and either carry on or not, according to the repeat count. If it was
311 a negative class, and we are operating with UTF-8 characters, any byte
312 with a value >= 0xc4 is a potentially valid starter because it starts a
313 character with a value > 255. */
318 start_bits[24] |= 0xf0; /* Bits for 0xc4 - 0xc8 */
319 memset(start_bits+25, 0xff, 7); /* Bits for 0xc9 - 0xff */
327 /* In UTF-8 mode, the bits in a bit map correspond to character
328 values, not to byte values. However, the bit map we are constructing is
329 for byte values. So we have to do a conversion for characters whose
330 value is > 127. In fact, there are only two possible starting bytes for
331 characters in the range 128 - 255. */
335 for (c = 0; c < 16; c++) start_bits[c] |= tcode[c];
336 for (c = 128; c < 256; c++)
338 if ((tcode[c/8] && (1 << (c&7))) != 0)
340 int d = (c >> 6) | 0xc0; /* Set bit for this starter */
341 start_bits[d/8] |= (1 << (d&7)); /* and then skip on to the */
342 c = (c & 0xc0) + 0x40 - 1; /* next relevant character. */
347 /* In non-UTF-8 mode, the two bit maps are completely compatible. */
351 for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];
354 /* Advance past the bit map, and act on what follows */
368 if (((tcode[1] << 8) + tcode[2]) == 0) tcode += 5;
369 else try_next = FALSE;
377 break; /* End of bitmap class handling */
379 } /* End of switch */
380 } /* End of try_next loop */
382 code += GET(code, 1); /* Advance to next branch */
384 while (*code == OP_ALT);
390 /*************************************************
391 * Study a compiled expression *
392 *************************************************/
394 /* This function is handed a compiled expression that it must study to produce
395 information that will speed up the matching. It returns a pcre_extra block
396 which then gets handed back to pcre_exec().
399 re points to the compiled expression
400 options contains option bits
401 errorptr points to where to place error messages;
402 set NULL unless error
404 Returns: pointer to a pcre_extra block, with study_data filled in and the
405 appropriate flag set;
406 NULL on error or if no optimization possible
410 pcre_study(const pcre *external_re, int options, const char **errorptr)
412 uschar start_bits[32];
414 pcre_study_data *study;
415 const uschar *tables;
416 const real_pcre *re = (const real_pcre *)external_re;
417 uschar *code = (uschar *)re + re->name_table_offset +
418 (re->name_count * re->name_entry_size);
419 compile_data compile_block;
423 if (re == NULL || re->magic_number != MAGIC_NUMBER)
425 *errorptr = "argument is not a compiled regular expression";
429 if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
431 *errorptr = "unknown or incorrect option bit(s) set";
435 /* For an anchored pattern, or an unanchored pattern that has a first char, or
436 a multiline pattern that matches only at "line starts", no further processing
439 if ((re->options & (PCRE_ANCHORED|PCRE_FIRSTSET|PCRE_STARTLINE)) != 0)
442 /* Set the character tables in the block that is passed around */
446 (void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES, &tables);
448 compile_block.lcc = tables + lcc_offset;
449 compile_block.fcc = tables + fcc_offset;
450 compile_block.cbits = tables + cbits_offset;
451 compile_block.ctypes = tables + ctypes_offset;
453 /* See if we can find a fixed set of initial characters for the pattern. */
455 memset(start_bits, 0, 32 * sizeof(uschar));
456 if (!set_start_bits(code, start_bits, (re->options & PCRE_CASELESS) != 0,
457 (re->options & PCRE_UTF8) != 0, &compile_block)) return NULL;
459 /* Get a pcre_extra block and a pcre_study_data block. The study data is put in
460 the latter, which is pointed to by the former, which may also get additional
461 data set later by the calling program. At the moment, the size of
462 pcre_study_data is fixed. We nevertheless save it in a field for returning via
463 the pcre_fullinfo() function so that if it becomes variable in the future, we
464 don't have to change that code. */
466 extra = (pcre_extra *)(pcre_malloc)
467 (sizeof(pcre_extra) + sizeof(pcre_study_data));
471 *errorptr = "failed to get memory";
475 study = (pcre_study_data *)((char *)extra + sizeof(pcre_extra));
476 extra->flags = PCRE_EXTRA_STUDY_DATA;
477 extra->study_data = study;
479 study->size = sizeof(pcre_study_data);
480 study->options = PCRE_STUDY_MAPPED;
481 memcpy(study->start_bits, start_bits, sizeof(start_bits));