1 /* $Cambridge: exim/src/src/pcre/pcre_study.c,v 1.5 2007/06/26 11:16:54 ph10 Exp $ */
3 /*************************************************
4 * Perl-Compatible Regular Expressions *
5 *************************************************/
7 /* PCRE is a library of functions to support regular expressions whose syntax
8 and semantics are as close as possible to those of the Perl 5 language.
10 Written by Philip Hazel
11 Copyright (c) 1997-2007 University of Cambridge
13 -----------------------------------------------------------------------------
14 Redistribution and use in source and binary forms, with or without
15 modification, are permitted provided that the following conditions are met:
17 * Redistributions of source code must retain the above copyright notice,
18 this list of conditions and the following disclaimer.
20 * Redistributions in binary form must reproduce the above copyright
21 notice, this list of conditions and the following disclaimer in the
22 documentation and/or other materials provided with the distribution.
24 * Neither the name of the University of Cambridge nor the names of its
25 contributors may be used to endorse or promote products derived from
26 this software without specific prior written permission.
28 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
29 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
32 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
33 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
34 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
35 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
36 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
37 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
38 POSSIBILITY OF SUCH DAMAGE.
39 -----------------------------------------------------------------------------
43 /* This module contains the external function pcre_study(), along with local
44 supporting functions. */
47 #include "pcre_internal.h"
50 /* Returns from set_start_bits() */
52 enum { SSB_FAIL, SSB_DONE, SSB_CONTINUE };
55 /*************************************************
56 * Set a bit and maybe its alternate case *
57 *************************************************/
59 /* Given a character, set its bit in the table, and also the bit for the other
60 version of a letter if we are caseless.
63 start_bits points to the bit map
65 caseless the caseless flag
66 cd the block with char table pointers
72 set_bit(uschar *start_bits, unsigned int c, BOOL caseless, compile_data *cd)
74 start_bits[c/8] |= (1 << (c&7));
75 if (caseless && (cd->ctypes[c] & ctype_letter) != 0)
76 start_bits[cd->fcc[c]/8] |= (1 << (cd->fcc[c]&7));
81 /*************************************************
82 * Create bitmap of starting bytes *
83 *************************************************/
85 /* This function scans a compiled unanchored expression recursively and
86 attempts to build a bitmap of the set of possible starting bytes. As time goes
87 by, we may be able to get more clever at doing this. The SSB_CONTINUE return is
88 useful for parenthesized groups in patterns such as (a*)b where the group
89 provides some optional starting bytes but scanning must continue at the outer
90 level to find at least one mandatory byte. At the outermost level, this
91 function fails unless the result is SSB_DONE.
94 code points to an expression
95 start_bits points to a 32-byte table, initialized to 0
96 caseless the current state of the caseless flag
97 utf8 TRUE if in UTF-8 mode
98 cd the block with char table pointers
100 Returns: SSB_FAIL => Failed to find any starting bytes
101 SSB_DONE => Found mandatory starting bytes
102 SSB_CONTINUE => Found optional starting bytes
106 set_start_bits(const uschar *code, uschar *start_bits, BOOL caseless,
107 BOOL utf8, compile_data *cd)
110 int yield = SSB_DONE;
113 /* ========================================================================= */
114 /* The following comment and code was inserted in January 1999. In May 2006,
115 when it was observed to cause compiler warnings about unused values, I took it
116 out again. If anybody is still using OS/2, they will have to put it back
119 /* This next statement and the later reference to dummy are here in order to
120 trick the optimizer of the IBM C compiler for OS/2 into generating correct
121 code. Apparently IBM isn't going to fix the problem, and we would rather not
122 disable optimization (in this module it actually makes a big difference, and
123 the pcre module can use all the optimization it can get). */
126 /* ========================================================================= */
131 const uschar *tcode = code + (((int)*code == OP_CBRA)? 3:1) + LINK_SIZE;
132 BOOL try_next = TRUE;
134 while (try_next) /* Loop for items in this branch */
139 /* Fail if we reach something we don't understand */
144 /* If we hit a bracket or a positive lookahead assertion, recurse to set
145 bits from within the subpattern. If it can't find anything, we have to
146 give up. If it finds some mandatory character(s), we are done for this
147 branch. Otherwise, carry on scanning after the subpattern. */
155 rc = set_start_bits(tcode, start_bits, caseless, utf8, cd);
156 if (rc == SSB_FAIL) return SSB_FAIL;
157 if (rc == SSB_DONE) try_next = FALSE; else
159 do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
160 tcode += 1 + LINK_SIZE;
164 /* If we hit ALT or KET, it means we haven't found anything mandatory in
165 this branch, though we might have found something optional. For ALT, we
166 continue with the next alternative, but we have to arrange that the final
167 result from subpattern is SSB_CONTINUE rather than SSB_DONE. For KET,
168 return SSB_CONTINUE: if this is the top level, that indicates failure,
169 but after a nested subpattern, it causes scanning to continue. */
172 yield = SSB_CONTINUE;
181 /* Skip over callout */
184 tcode += 2 + 2*LINK_SIZE;
187 /* Skip over lookbehind and negative lookahead assertions */
191 case OP_ASSERTBACK_NOT:
192 do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
193 tcode += 1 + LINK_SIZE;
196 /* Skip over an option setting, changing the caseless flag */
199 caseless = (tcode[1] & PCRE_CASELESS) != 0;
203 /* BRAZERO does the bracket, but carries on. */
207 if (set_start_bits(++tcode, start_bits, caseless, utf8, cd) == SSB_FAIL)
209 /* =========================================================================
210 See the comment at the head of this function concerning the next line,
211 which was an old fudge for the benefit of OS/2.
213 ========================================================================= */
214 do tcode += GET(tcode,1); while (*tcode == OP_ALT);
215 tcode += 1 + LINK_SIZE;
218 /* Single-char * or ? sets the bit and tries the next item */
226 set_bit(start_bits, tcode[1], caseless, cd);
229 if (utf8 && tcode[-1] >= 0xc0)
230 tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
234 /* Single-char upto sets the bit and tries the next */
239 set_bit(start_bits, tcode[3], caseless, cd);
242 if (utf8 && tcode[-1] >= 0xc0)
243 tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
247 /* At least one single char sets the bit and stops */
249 case OP_EXACT: /* Fall through */
257 set_bit(start_bits, tcode[1], caseless, cd);
261 /* Single character type sets the bits and stops */
264 for (c = 0; c < 32; c++)
265 start_bits[c] |= ~cd->cbits[c+cbit_digit];
270 for (c = 0; c < 32; c++)
271 start_bits[c] |= cd->cbits[c+cbit_digit];
275 /* The cbit_space table has vertical tab as whitespace; we have to
278 case OP_NOT_WHITESPACE:
279 for (c = 0; c < 32; c++)
281 int d = cd->cbits[c+cbit_space];
282 if (c == 1) d &= ~0x08;
288 /* The cbit_space table has vertical tab as whitespace; we have to
292 for (c = 0; c < 32; c++)
294 int d = cd->cbits[c+cbit_space];
295 if (c == 1) d &= ~0x08;
301 case OP_NOT_WORDCHAR:
302 for (c = 0; c < 32; c++)
303 start_bits[c] |= ~cd->cbits[c+cbit_word];
308 for (c = 0; c < 32; c++)
309 start_bits[c] |= cd->cbits[c+cbit_word];
313 /* One or more character type fudges the pointer and restarts, knowing
314 it will hit a single character type and stop there. */
325 /* Zero or more repeats of character types set the bits and then
331 tcode += 2; /* Fall through */
337 case OP_TYPEMINQUERY:
338 case OP_TYPEPOSQUERY:
345 for (c = 0; c < 32; c++)
346 start_bits[c] |= ~cd->cbits[c+cbit_digit];
350 for (c = 0; c < 32; c++)
351 start_bits[c] |= cd->cbits[c+cbit_digit];
354 /* The cbit_space table has vertical tab as whitespace; we have to
357 case OP_NOT_WHITESPACE:
358 for (c = 0; c < 32; c++)
360 int d = cd->cbits[c+cbit_space];
361 if (c == 1) d &= ~0x08;
366 /* The cbit_space table has vertical tab as whitespace; we have to
370 for (c = 0; c < 32; c++)
372 int d = cd->cbits[c+cbit_space];
373 if (c == 1) d &= ~0x08;
378 case OP_NOT_WORDCHAR:
379 for (c = 0; c < 32; c++)
380 start_bits[c] |= ~cd->cbits[c+cbit_word];
384 for (c = 0; c < 32; c++)
385 start_bits[c] |= cd->cbits[c+cbit_word];
392 /* Character class where all the information is in a bit map: set the
393 bits and either carry on or not, according to the repeat count. If it was
394 a negative class, and we are operating with UTF-8 characters, any byte
395 with a value >= 0xc4 is a potentially valid starter because it starts a
396 character with a value > 255. */
402 start_bits[24] |= 0xf0; /* Bits for 0xc4 - 0xc8 */
403 memset(start_bits+25, 0xff, 7); /* Bits for 0xc9 - 0xff */
412 /* In UTF-8 mode, the bits in a bit map correspond to character
413 values, not to byte values. However, the bit map we are constructing is
414 for byte values. So we have to do a conversion for characters whose
415 value is > 127. In fact, there are only two possible starting bytes for
416 characters in the range 128 - 255. */
421 for (c = 0; c < 16; c++) start_bits[c] |= tcode[c];
422 for (c = 128; c < 256; c++)
424 if ((tcode[c/8] && (1 << (c&7))) != 0)
426 int d = (c >> 6) | 0xc0; /* Set bit for this starter */
427 start_bits[d/8] |= (1 << (d&7)); /* and then skip on to the */
428 c = (c & 0xc0) + 0x40 - 1; /* next relevant character. */
433 /* In non-UTF-8 mode, the two bit maps are completely compatible. */
438 for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];
441 /* Advance past the bit map, and act on what follows */
455 if (((tcode[1] << 8) + tcode[2]) == 0) tcode += 5;
456 else try_next = FALSE;
464 break; /* End of bitmap class handling */
466 } /* End of switch */
467 } /* End of try_next loop */
469 code += GET(code, 1); /* Advance to next branch */
471 while (*code == OP_ALT);
477 /*************************************************
478 * Study a compiled expression *
479 *************************************************/
481 /* This function is handed a compiled expression that it must study to produce
482 information that will speed up the matching. It returns a pcre_extra block
483 which then gets handed back to pcre_exec().
486 re points to the compiled expression
487 options contains option bits
488 errorptr points to where to place error messages;
489 set NULL unless error
491 Returns: pointer to a pcre_extra block, with study_data filled in and the
492 appropriate flag set;
493 NULL on error or if no optimization possible
496 PCRE_EXP_DEFN pcre_extra *
497 pcre_study(const pcre *external_re, int options, const char **errorptr)
499 uschar start_bits[32];
501 pcre_study_data *study;
502 const uschar *tables;
504 compile_data compile_block;
505 const real_pcre *re = (const real_pcre *)external_re;
509 if (re == NULL || re->magic_number != MAGIC_NUMBER)
511 *errorptr = "argument is not a compiled regular expression";
515 if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
517 *errorptr = "unknown or incorrect option bit(s) set";
521 code = (uschar *)re + re->name_table_offset +
522 (re->name_count * re->name_entry_size);
524 /* For an anchored pattern, or an unanchored pattern that has a first char, or
525 a multiline pattern that matches only at "line starts", no further processing
528 if ((re->options & (PCRE_ANCHORED|PCRE_FIRSTSET|PCRE_STARTLINE)) != 0)
531 /* Set the character tables in the block that is passed around */
535 (void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
538 compile_block.lcc = tables + lcc_offset;
539 compile_block.fcc = tables + fcc_offset;
540 compile_block.cbits = tables + cbits_offset;
541 compile_block.ctypes = tables + ctypes_offset;
543 /* See if we can find a fixed set of initial characters for the pattern. */
545 memset(start_bits, 0, 32 * sizeof(uschar));
546 if (set_start_bits(code, start_bits, (re->options & PCRE_CASELESS) != 0,
547 (re->options & PCRE_UTF8) != 0, &compile_block) != SSB_DONE) return NULL;
549 /* Get a pcre_extra block and a pcre_study_data block. The study data is put in
550 the latter, which is pointed to by the former, which may also get additional
551 data set later by the calling program. At the moment, the size of
552 pcre_study_data is fixed. We nevertheless save it in a field for returning via
553 the pcre_fullinfo() function so that if it becomes variable in the future, we
554 don't have to change that code. */
556 extra = (pcre_extra *)(pcre_malloc)
557 (sizeof(pcre_extra) + sizeof(pcre_study_data));
561 *errorptr = "failed to get memory";
565 study = (pcre_study_data *)((char *)extra + sizeof(pcre_extra));
566 extra->flags = PCRE_EXTRA_STUDY_DATA;
567 extra->study_data = study;
569 study->size = sizeof(pcre_study_data);
570 study->options = PCRE_STUDY_MAPPED;
571 memcpy(study->start_bits, start_bits, sizeof(start_bits));
576 /* End of pcre_study.c */