1 /*************************************************
2 * Perl-Compatible Regular Expressions *
3 *************************************************/
5 /* PCRE is a library of functions to support regular expressions whose syntax
6 and semantics are as close as possible to those of the Perl 5 language.
8 Written by Philip Hazel
9 Copyright (c) 1997-2007 University of Cambridge
11 -----------------------------------------------------------------------------
12 Redistribution and use in source and binary forms, with or without
13 modification, are permitted provided that the following conditions are met:
15 * Redistributions of source code must retain the above copyright notice,
16 this list of conditions and the following disclaimer.
18 * Redistributions in binary form must reproduce the above copyright
19 notice, this list of conditions and the following disclaimer in the
20 documentation and/or other materials provided with the distribution.
22 * Neither the name of the University of Cambridge nor the names of its
23 contributors may be used to endorse or promote products derived from
24 this software without specific prior written permission.
26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
27 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
30 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
31 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
32 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
33 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
34 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
35 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36 POSSIBILITY OF SUCH DAMAGE.
37 -----------------------------------------------------------------------------
41 /* This module contains the external function pcre_study(), along with local
42 supporting functions. */
45 #include "pcre_internal.h"
48 /* Returns from set_start_bits() */
50 enum { SSB_FAIL, SSB_DONE, SSB_CONTINUE };
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 bytes *
81 *************************************************/
83 /* This function scans a compiled unanchored expression recursively and
84 attempts to build a bitmap of the set of possible starting bytes. As time goes
85 by, we may be able to get more clever at doing this. The SSB_CONTINUE return is
86 useful for parenthesized groups in patterns such as (a*)b where the group
87 provides some optional starting bytes but scanning must continue at the outer
88 level to find at least one mandatory byte. At the outermost level, this
89 function fails unless the result is SSB_DONE.
92 code points to an expression
93 start_bits points to a 32-byte table, initialized to 0
94 caseless the current state of the caseless flag
95 utf8 TRUE if in UTF-8 mode
96 cd the block with char table pointers
98 Returns: SSB_FAIL => Failed to find any starting bytes
99 SSB_DONE => Found mandatory starting bytes
100 SSB_CONTINUE => Found optional starting bytes
104 set_start_bits(const uschar *code, uschar *start_bits, BOOL caseless,
105 BOOL utf8, compile_data *cd)
108 int yield = SSB_DONE;
111 /* ========================================================================= */
112 /* The following comment and code was inserted in January 1999. In May 2006,
113 when it was observed to cause compiler warnings about unused values, I took it
114 out again. If anybody is still using OS/2, they will have to put it back
117 /* This next statement and the later reference to dummy are here in order to
118 trick the optimizer of the IBM C compiler for OS/2 into generating correct
119 code. Apparently IBM isn't going to fix the problem, and we would rather not
120 disable optimization (in this module it actually makes a big difference, and
121 the pcre module can use all the optimization it can get). */
124 /* ========================================================================= */
129 const uschar *tcode = code + (((int)*code == OP_CBRA)? 3:1) + LINK_SIZE;
130 BOOL try_next = TRUE;
132 while (try_next) /* Loop for items in this branch */
137 /* Fail if we reach something we don't understand */
142 /* If we hit a bracket or a positive lookahead assertion, recurse to set
143 bits from within the subpattern. If it can't find anything, we have to
144 give up. If it finds some mandatory character(s), we are done for this
145 branch. Otherwise, carry on scanning after the subpattern. */
153 rc = set_start_bits(tcode, start_bits, caseless, utf8, cd);
154 if (rc == SSB_FAIL) return SSB_FAIL;
155 if (rc == SSB_DONE) try_next = FALSE; else
157 do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
158 tcode += 1 + LINK_SIZE;
162 /* If we hit ALT or KET, it means we haven't found anything mandatory in
163 this branch, though we might have found something optional. For ALT, we
164 continue with the next alternative, but we have to arrange that the final
165 result from subpattern is SSB_CONTINUE rather than SSB_DONE. For KET,
166 return SSB_CONTINUE: if this is the top level, that indicates failure,
167 but after a nested subpattern, it causes scanning to continue. */
170 yield = SSB_CONTINUE;
179 /* Skip over callout */
182 tcode += 2 + 2*LINK_SIZE;
185 /* Skip over lookbehind and negative lookahead assertions */
189 case OP_ASSERTBACK_NOT:
190 do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
191 tcode += 1 + LINK_SIZE;
194 /* Skip over an option setting, changing the caseless flag */
197 caseless = (tcode[1] & PCRE_CASELESS) != 0;
201 /* BRAZERO does the bracket, but carries on. */
205 if (set_start_bits(++tcode, start_bits, caseless, utf8, cd) == SSB_FAIL)
207 /* =========================================================================
208 See the comment at the head of this function concerning the next line,
209 which was an old fudge for the benefit of OS/2.
211 ========================================================================= */
212 do tcode += GET(tcode,1); while (*tcode == OP_ALT);
213 tcode += 1 + LINK_SIZE;
216 /* Single-char * or ? sets the bit and tries the next item */
224 set_bit(start_bits, tcode[1], caseless, cd);
227 if (utf8 && tcode[-1] >= 0xc0)
228 tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
232 /* Single-char upto sets the bit and tries the next */
237 set_bit(start_bits, tcode[3], caseless, cd);
240 if (utf8 && tcode[-1] >= 0xc0)
241 tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
245 /* At least one single char sets the bit and stops */
247 case OP_EXACT: /* Fall through */
255 set_bit(start_bits, tcode[1], caseless, cd);
259 /* Single character type sets the bits and stops */
262 for (c = 0; c < 32; c++)
263 start_bits[c] |= ~cd->cbits[c+cbit_digit];
268 for (c = 0; c < 32; c++)
269 start_bits[c] |= cd->cbits[c+cbit_digit];
273 /* The cbit_space table has vertical tab as whitespace; we have to
276 case OP_NOT_WHITESPACE:
277 for (c = 0; c < 32; c++)
279 int d = cd->cbits[c+cbit_space];
280 if (c == 1) d &= ~0x08;
286 /* The cbit_space table has vertical tab as whitespace; we have to
290 for (c = 0; c < 32; c++)
292 int d = cd->cbits[c+cbit_space];
293 if (c == 1) d &= ~0x08;
299 case OP_NOT_WORDCHAR:
300 for (c = 0; c < 32; c++)
301 start_bits[c] |= ~cd->cbits[c+cbit_word];
306 for (c = 0; c < 32; c++)
307 start_bits[c] |= cd->cbits[c+cbit_word];
311 /* One or more character type fudges the pointer and restarts, knowing
312 it will hit a single character type and stop there. */
323 /* Zero or more repeats of character types set the bits and then
329 tcode += 2; /* Fall through */
335 case OP_TYPEMINQUERY:
336 case OP_TYPEPOSQUERY:
343 for (c = 0; c < 32; c++)
344 start_bits[c] |= ~cd->cbits[c+cbit_digit];
348 for (c = 0; c < 32; c++)
349 start_bits[c] |= cd->cbits[c+cbit_digit];
352 /* The cbit_space table has vertical tab as whitespace; we have to
355 case OP_NOT_WHITESPACE:
356 for (c = 0; c < 32; c++)
358 int d = cd->cbits[c+cbit_space];
359 if (c == 1) d &= ~0x08;
364 /* The cbit_space table has vertical tab as whitespace; we have to
368 for (c = 0; c < 32; c++)
370 int d = cd->cbits[c+cbit_space];
371 if (c == 1) d &= ~0x08;
376 case OP_NOT_WORDCHAR:
377 for (c = 0; c < 32; c++)
378 start_bits[c] |= ~cd->cbits[c+cbit_word];
382 for (c = 0; c < 32; c++)
383 start_bits[c] |= cd->cbits[c+cbit_word];
390 /* Character class where all the information is in a bit map: set the
391 bits and either carry on or not, according to the repeat count. If it was
392 a negative class, and we are operating with UTF-8 characters, any byte
393 with a value >= 0xc4 is a potentially valid starter because it starts a
394 character with a value > 255. */
400 start_bits[24] |= 0xf0; /* Bits for 0xc4 - 0xc8 */
401 memset(start_bits+25, 0xff, 7); /* Bits for 0xc9 - 0xff */
410 /* In UTF-8 mode, the bits in a bit map correspond to character
411 values, not to byte values. However, the bit map we are constructing is
412 for byte values. So we have to do a conversion for characters whose
413 value is > 127. In fact, there are only two possible starting bytes for
414 characters in the range 128 - 255. */
419 for (c = 0; c < 16; c++) start_bits[c] |= tcode[c];
420 for (c = 128; c < 256; c++)
422 if ((tcode[c/8] && (1 << (c&7))) != 0)
424 int d = (c >> 6) | 0xc0; /* Set bit for this starter */
425 start_bits[d/8] |= (1 << (d&7)); /* and then skip on to the */
426 c = (c & 0xc0) + 0x40 - 1; /* next relevant character. */
431 /* In non-UTF-8 mode, the two bit maps are completely compatible. */
436 for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];
439 /* Advance past the bit map, and act on what follows */
453 if (((tcode[1] << 8) + tcode[2]) == 0) tcode += 5;
454 else try_next = FALSE;
462 break; /* End of bitmap class handling */
464 } /* End of switch */
465 } /* End of try_next loop */
467 code += GET(code, 1); /* Advance to next branch */
469 while (*code == OP_ALT);
475 /*************************************************
476 * Study a compiled expression *
477 *************************************************/
479 /* This function is handed a compiled expression that it must study to produce
480 information that will speed up the matching. It returns a pcre_extra block
481 which then gets handed back to pcre_exec().
484 re points to the compiled expression
485 options contains option bits
486 errorptr points to where to place error messages;
487 set NULL unless error
489 Returns: pointer to a pcre_extra block, with study_data filled in and the
490 appropriate flag set;
491 NULL on error or if no optimization possible
494 PCRE_EXP_DEFN pcre_extra *
495 pcre_study(const pcre *external_re, int options, const char **errorptr)
497 uschar start_bits[32];
499 pcre_study_data *study;
500 const uschar *tables;
502 compile_data compile_block;
503 const real_pcre *re = (const real_pcre *)external_re;
507 if (re == NULL || re->magic_number != MAGIC_NUMBER)
509 *errorptr = "argument is not a compiled regular expression";
513 if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
515 *errorptr = "unknown or incorrect option bit(s) set";
519 code = (uschar *)re + re->name_table_offset +
520 (re->name_count * re->name_entry_size);
522 /* For an anchored pattern, or an unanchored pattern that has a first char, or
523 a multiline pattern that matches only at "line starts", no further processing
526 if ((re->options & (PCRE_ANCHORED|PCRE_FIRSTSET|PCRE_STARTLINE)) != 0)
529 /* Set the character tables in the block that is passed around */
533 (void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
536 compile_block.lcc = tables + lcc_offset;
537 compile_block.fcc = tables + fcc_offset;
538 compile_block.cbits = tables + cbits_offset;
539 compile_block.ctypes = tables + ctypes_offset;
541 /* See if we can find a fixed set of initial characters for the pattern. */
543 memset(start_bits, 0, 32 * sizeof(uschar));
544 if (set_start_bits(code, start_bits, (re->options & PCRE_CASELESS) != 0,
545 (re->options & PCRE_UTF8) != 0, &compile_block) != SSB_DONE) return NULL;
547 /* Get a pcre_extra block and a pcre_study_data block. The study data is put in
548 the latter, which is pointed to by the former, which may also get additional
549 data set later by the calling program. At the moment, the size of
550 pcre_study_data is fixed. We nevertheless save it in a field for returning via
551 the pcre_fullinfo() function so that if it becomes variable in the future, we
552 don't have to change that code. */
554 extra = (pcre_extra *)(pcre_malloc)
555 (sizeof(pcre_extra) + sizeof(pcre_study_data));
559 *errorptr = "failed to get memory";
563 study = (pcre_study_data *)((char *)extra + sizeof(pcre_extra));
564 extra->flags = PCRE_EXTRA_STUDY_DATA;
565 extra->study_data = study;
567 study->size = sizeof(pcre_study_data);
568 study->options = PCRE_STUDY_MAPPED;
569 memcpy(study->start_bits, start_bits, sizeof(start_bits));
574 /* End of pcre_study.c */