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-2010 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. */
49 #include "pcre_internal.h"
52 /* Returns from set_start_bits() */
54 enum { SSB_FAIL, SSB_DONE, SSB_CONTINUE };
58 /*************************************************
59 * Find the minimum subject length for a group *
60 *************************************************/
62 /* Scan a parenthesized group and compute the minimum length of subject that
63 is needed to match it. This is a lower bound; it does not mean there is a
64 string of that length that matches. In UTF8 mode, the result is in characters
68 code pointer to start of group (the bracket)
69 startcode pointer to start of the whole pattern
70 options the compiling options
72 Returns: the minimum length
73 -1 if \C was encountered
74 -2 internal error (missing capturing bracket)
78 find_minlength(const uschar *code, const uschar *startcode, int options)
81 BOOL utf8 = (options & PCRE_UTF8) != 0;
82 BOOL had_recurse = FALSE;
83 register int branchlength = 0;
84 register uschar *cc = (uschar *)code + 1 + LINK_SIZE;
86 if (*code == OP_CBRA || *code == OP_SCBRA) cc += 2;
88 /* Scan along the opcodes for this branch. If we get to the end of the
89 branch, check the length against that of the other branches. */
95 register int op = *cc;
102 /* If there is only one branch in a condition, the implied branch has zero
103 length, so we don't add anything. This covers the DEFINE "condition"
106 cs = cc + GET(cc, 1);
109 cc = cs + 1 + LINK_SIZE;
113 /* Otherwise we can fall through and treat it the same as any other
121 d = find_minlength(cc, startcode, options);
124 do cc += GET(cc, 1); while (*cc == OP_ALT);
128 /* Reached end of a branch; if it's a ket it is the end of a nested
129 call. If it's ALT it is an alternation in a nested call. If it is
130 END it's the end of the outer call. All can be handled by the same code. */
137 if (length < 0 || (!had_recurse && branchlength < length))
138 length = branchlength;
139 if (*cc != OP_ALT) return length;
145 /* Skip over assertive subpatterns */
150 case OP_ASSERTBACK_NOT:
151 do cc += GET(cc, 1); while (*cc == OP_ALT);
154 /* Skip over things that don't match chars */
170 case OP_NOT_WORD_BOUNDARY:
171 case OP_WORD_BOUNDARY:
172 cc += _pcre_OP_lengths[*cc];
175 /* Skip over a subpattern that has a {0} or {0,x} quantifier */
180 cc += _pcre_OP_lengths[*cc];
181 do cc += GET(cc, 1); while (*cc == OP_ALT);
185 /* Handle literal characters and + repetitions */
199 if (utf8 && cc[-1] >= 0xc0) cc += _pcre_utf8_table4[cc[-1] & 0x3f];
207 cc += (cc[1] == OP_PROP || cc[1] == OP_NOTPROP)? 4 : 2;
210 /* Handle exact repetitions. The count is already in characters, but we
211 need to skip over a multibyte character in UTF8 mode. */
215 branchlength += GET2(cc,1);
218 if (utf8 && cc[-1] >= 0xc0) cc += _pcre_utf8_table4[cc[-1] & 0x3f];
223 branchlength += GET2(cc,1);
224 cc += (cc[3] == OP_PROP || cc[3] == OP_NOTPROP)? 6 : 4;
227 /* Handle single-char non-literal matchers */
236 case OP_NOT_WHITESPACE:
238 case OP_NOT_WORDCHAR:
251 /* "Any newline" might match two characters */
258 /* The single-byte matcher means we can't proceed in UTF-8 mode */
268 /* For repeated character types, we have to test for \p and \P, which have
269 an extra two bytes of parameters. */
274 case OP_TYPEMINQUERY:
276 case OP_TYPEPOSQUERY:
277 if (cc[1] == OP_PROP || cc[1] == OP_NOTPROP) cc += 2;
278 cc += _pcre_OP_lengths[op];
284 if (cc[3] == OP_PROP || cc[3] == OP_NOTPROP) cc += 2;
285 cc += _pcre_OP_lengths[op];
288 /* Check a class for variable quantification */
292 cc += GET(cc, 1) - 33;
316 branchlength += GET2(cc,1);
326 /* Backreferences and subroutine calls are treated in the same way: we find
327 the minimum length for the subpattern. A recursion, however, causes an
328 a flag to be set that causes the length of this branch to be ignored. The
329 logic is that a recursion can only make sense if there is another
330 alternation that stops the recursing. That will provide the minimum length
331 (when no recursion happens). A backreference within the group that it is
332 referencing behaves in the same way.
334 If PCRE_JAVASCRIPT_COMPAT is set, a backreference to an unset bracket
335 matches an empty string (by default it causes a matching failure), so in
336 that case we must set the minimum length to zero. */
339 if ((options & PCRE_JAVASCRIPT_COMPAT) == 0)
341 ce = cs = (uschar *)_pcre_find_bracket(startcode, utf8, GET2(cc, 1));
342 if (cs == NULL) return -2;
343 do ce += GET(ce, 1); while (*ce == OP_ALT);
344 if (cc > cs && cc < ce)
349 else d = find_minlength(cs, startcode, options);
354 /* Handle repeated back references */
377 branchlength += min * d;
381 cs = ce = (uschar *)startcode + GET(cc, 1);
382 if (cs == NULL) return -2;
383 do ce += GET(ce, 1); while (*ce == OP_ALT);
384 if (cc > cs && cc < ce)
387 branchlength += find_minlength(cs, startcode, options);
391 /* Anything else does not or need not match a character. We can get the
392 item's length from the table, but for those that can match zero occurrences
393 of a character, we must take special action for UTF-8 characters. */
410 cc += _pcre_OP_lengths[op];
412 if (utf8 && cc[-1] >= 0xc0) cc += _pcre_utf8_table4[cc[-1] & 0x3f];
416 /* For the record, these are the opcodes that are matched by "default":
417 OP_ACCEPT, OP_CLOSE, OP_COMMIT, OP_FAIL, OP_PRUNE, OP_SET_SOM, OP_SKIP,
421 cc += _pcre_OP_lengths[op];
425 /* Control never gets here */
430 /*************************************************
431 * Set a bit and maybe its alternate case *
432 *************************************************/
434 /* Given a character, set its bit in the table, and also the bit for the other
435 version of a letter if we are caseless.
438 start_bits points to the bit map
440 caseless the caseless flag
441 cd the block with char table pointers
447 set_table_bit(uschar *start_bits, unsigned int c, BOOL caseless,
450 start_bits[c/8] |= (1 << (c&7));
451 if (caseless && (cd->ctypes[c] & ctype_letter) != 0)
452 start_bits[cd->fcc[c]/8] |= (1 << (cd->fcc[c]&7));
457 /*************************************************
458 * Create bitmap of starting bytes *
459 *************************************************/
461 /* This function scans a compiled unanchored expression recursively and
462 attempts to build a bitmap of the set of possible starting bytes. As time goes
463 by, we may be able to get more clever at doing this. The SSB_CONTINUE return is
464 useful for parenthesized groups in patterns such as (a*)b where the group
465 provides some optional starting bytes but scanning must continue at the outer
466 level to find at least one mandatory byte. At the outermost level, this
467 function fails unless the result is SSB_DONE.
470 code points to an expression
471 start_bits points to a 32-byte table, initialized to 0
472 caseless the current state of the caseless flag
473 utf8 TRUE if in UTF-8 mode
474 cd the block with char table pointers
476 Returns: SSB_FAIL => Failed to find any starting bytes
477 SSB_DONE => Found mandatory starting bytes
478 SSB_CONTINUE => Found optional starting bytes
482 set_start_bits(const uschar *code, uschar *start_bits, BOOL caseless,
483 BOOL utf8, compile_data *cd)
486 int yield = SSB_DONE;
489 /* ========================================================================= */
490 /* The following comment and code was inserted in January 1999. In May 2006,
491 when it was observed to cause compiler warnings about unused values, I took it
492 out again. If anybody is still using OS/2, they will have to put it back
495 /* This next statement and the later reference to dummy are here in order to
496 trick the optimizer of the IBM C compiler for OS/2 into generating correct
497 code. Apparently IBM isn't going to fix the problem, and we would rather not
498 disable optimization (in this module it actually makes a big difference, and
499 the pcre module can use all the optimization it can get). */
502 /* ========================================================================= */
507 const uschar *tcode = code + (((int)*code == OP_CBRA)? 3:1) + LINK_SIZE;
508 BOOL try_next = TRUE;
510 while (try_next) /* Loop for items in this branch */
515 /* Fail if we reach something we don't understand */
520 /* If we hit a bracket or a positive lookahead assertion, recurse to set
521 bits from within the subpattern. If it can't find anything, we have to
522 give up. If it finds some mandatory character(s), we are done for this
523 branch. Otherwise, carry on scanning after the subpattern. */
531 rc = set_start_bits(tcode, start_bits, caseless, utf8, cd);
532 if (rc == SSB_FAIL) return SSB_FAIL;
533 if (rc == SSB_DONE) try_next = FALSE; else
535 do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
536 tcode += 1 + LINK_SIZE;
540 /* If we hit ALT or KET, it means we haven't found anything mandatory in
541 this branch, though we might have found something optional. For ALT, we
542 continue with the next alternative, but we have to arrange that the final
543 result from subpattern is SSB_CONTINUE rather than SSB_DONE. For KET,
544 return SSB_CONTINUE: if this is the top level, that indicates failure,
545 but after a nested subpattern, it causes scanning to continue. */
548 yield = SSB_CONTINUE;
557 /* Skip over callout */
560 tcode += 2 + 2*LINK_SIZE;
563 /* Skip over lookbehind and negative lookahead assertions */
567 case OP_ASSERTBACK_NOT:
568 do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
569 tcode += 1 + LINK_SIZE;
572 /* Skip over an option setting, changing the caseless flag */
575 caseless = (tcode[1] & PCRE_CASELESS) != 0;
579 /* BRAZERO does the bracket, but carries on. */
583 if (set_start_bits(++tcode, start_bits, caseless, utf8, cd) == SSB_FAIL)
585 /* =========================================================================
586 See the comment at the head of this function concerning the next line,
587 which was an old fudge for the benefit of OS/2.
589 ========================================================================= */
590 do tcode += GET(tcode,1); while (*tcode == OP_ALT);
591 tcode += 1 + LINK_SIZE;
594 /* SKIPZERO skips the bracket. */
598 do tcode += GET(tcode,1); while (*tcode == OP_ALT);
599 tcode += 1 + LINK_SIZE;
602 /* Single-char * or ? sets the bit and tries the next item */
610 set_table_bit(start_bits, tcode[1], caseless, cd);
613 if (utf8 && tcode[-1] >= 0xc0)
614 tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
618 /* Single-char upto sets the bit and tries the next */
623 set_table_bit(start_bits, tcode[3], caseless, cd);
626 if (utf8 && tcode[-1] >= 0xc0)
627 tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
631 /* At least one single char sets the bit and stops */
633 case OP_EXACT: /* Fall through */
641 set_table_bit(start_bits, tcode[1], caseless, cd);
645 /* Single character type sets the bits and stops */
648 for (c = 0; c < 32; c++)
649 start_bits[c] |= ~cd->cbits[c+cbit_digit];
654 for (c = 0; c < 32; c++)
655 start_bits[c] |= cd->cbits[c+cbit_digit];
659 /* The cbit_space table has vertical tab as whitespace; we have to
662 case OP_NOT_WHITESPACE:
663 for (c = 0; c < 32; c++)
665 int d = cd->cbits[c+cbit_space];
666 if (c == 1) d &= ~0x08;
672 /* The cbit_space table has vertical tab as whitespace; we have to
676 for (c = 0; c < 32; c++)
678 int d = cd->cbits[c+cbit_space];
679 if (c == 1) d &= ~0x08;
685 case OP_NOT_WORDCHAR:
686 for (c = 0; c < 32; c++)
687 start_bits[c] |= ~cd->cbits[c+cbit_word];
692 for (c = 0; c < 32; c++)
693 start_bits[c] |= cd->cbits[c+cbit_word];
697 /* One or more character type fudges the pointer and restarts, knowing
698 it will hit a single character type and stop there. */
709 /* Zero or more repeats of character types set the bits and then
715 tcode += 2; /* Fall through */
721 case OP_TYPEMINQUERY:
722 case OP_TYPEPOSQUERY:
730 for (c = 0; c < 32; c++)
731 start_bits[c] |= ~cd->cbits[c+cbit_digit];
735 for (c = 0; c < 32; c++)
736 start_bits[c] |= cd->cbits[c+cbit_digit];
739 /* The cbit_space table has vertical tab as whitespace; we have to
742 case OP_NOT_WHITESPACE:
743 for (c = 0; c < 32; c++)
745 int d = cd->cbits[c+cbit_space];
746 if (c == 1) d &= ~0x08;
751 /* The cbit_space table has vertical tab as whitespace; we have to
755 for (c = 0; c < 32; c++)
757 int d = cd->cbits[c+cbit_space];
758 if (c == 1) d &= ~0x08;
763 case OP_NOT_WORDCHAR:
764 for (c = 0; c < 32; c++)
765 start_bits[c] |= ~cd->cbits[c+cbit_word];
769 for (c = 0; c < 32; c++)
770 start_bits[c] |= cd->cbits[c+cbit_word];
777 /* Character class where all the information is in a bit map: set the
778 bits and either carry on or not, according to the repeat count. If it was
779 a negative class, and we are operating with UTF-8 characters, any byte
780 with a value >= 0xc4 is a potentially valid starter because it starts a
781 character with a value > 255. */
787 start_bits[24] |= 0xf0; /* Bits for 0xc4 - 0xc8 */
788 memset(start_bits+25, 0xff, 7); /* Bits for 0xc9 - 0xff */
797 /* In UTF-8 mode, the bits in a bit map correspond to character
798 values, not to byte values. However, the bit map we are constructing is
799 for byte values. So we have to do a conversion for characters whose
800 value is > 127. In fact, there are only two possible starting bytes for
801 characters in the range 128 - 255. */
806 for (c = 0; c < 16; c++) start_bits[c] |= tcode[c];
807 for (c = 128; c < 256; c++)
809 if ((tcode[c/8] && (1 << (c&7))) != 0)
811 int d = (c >> 6) | 0xc0; /* Set bit for this starter */
812 start_bits[d/8] |= (1 << (d&7)); /* and then skip on to the */
813 c = (c & 0xc0) + 0x40 - 1; /* next relevant character. */
818 /* In non-UTF-8 mode, the two bit maps are completely compatible. */
823 for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];
826 /* Advance past the bit map, and act on what follows */
840 if (((tcode[1] << 8) + tcode[2]) == 0) tcode += 5;
841 else try_next = FALSE;
849 break; /* End of bitmap class handling */
851 } /* End of switch */
852 } /* End of try_next loop */
854 code += GET(code, 1); /* Advance to next branch */
856 while (*code == OP_ALT);
862 /*************************************************
863 * Study a compiled expression *
864 *************************************************/
866 /* This function is handed a compiled expression that it must study to produce
867 information that will speed up the matching. It returns a pcre_extra block
868 which then gets handed back to pcre_exec().
871 re points to the compiled expression
872 options contains option bits
873 errorptr points to where to place error messages;
874 set NULL unless error
876 Returns: pointer to a pcre_extra block, with study_data filled in and the
877 appropriate flags set;
878 NULL on error or if no optimization possible
881 PCRE_EXP_DEFN pcre_extra * PCRE_CALL_CONVENTION
882 pcre_study(const pcre *external_re, int options, const char **errorptr)
885 BOOL bits_set = FALSE;
886 uschar start_bits[32];
888 pcre_study_data *study;
889 const uschar *tables;
891 compile_data compile_block;
892 const real_pcre *re = (const real_pcre *)external_re;
896 if (re == NULL || re->magic_number != MAGIC_NUMBER)
898 *errorptr = "argument is not a compiled regular expression";
902 if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
904 *errorptr = "unknown or incorrect option bit(s) set";
908 code = (uschar *)re + re->name_table_offset +
909 (re->name_count * re->name_entry_size);
911 /* For an anchored pattern, or an unanchored pattern that has a first char, or
912 a multiline pattern that matches only at "line starts", there is no point in
913 seeking a list of starting bytes. */
915 if ((re->options & PCRE_ANCHORED) == 0 &&
916 (re->flags & (PCRE_FIRSTSET|PCRE_STARTLINE)) == 0)
918 /* Set the character tables in the block that is passed around */
922 (void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
925 compile_block.lcc = tables + lcc_offset;
926 compile_block.fcc = tables + fcc_offset;
927 compile_block.cbits = tables + cbits_offset;
928 compile_block.ctypes = tables + ctypes_offset;
930 /* See if we can find a fixed set of initial characters for the pattern. */
932 memset(start_bits, 0, 32 * sizeof(uschar));
933 bits_set = set_start_bits(code, start_bits,
934 (re->options & PCRE_CASELESS) != 0, (re->options & PCRE_UTF8) != 0,
935 &compile_block) == SSB_DONE;
938 /* Find the minimum length of subject string. */
940 min = find_minlength(code, code, re->options);
942 /* Return NULL if no optimization is possible. */
944 if (!bits_set && min < 0) return NULL;
946 /* Get a pcre_extra block and a pcre_study_data block. The study data is put in
947 the latter, which is pointed to by the former, which may also get additional
948 data set later by the calling program. At the moment, the size of
949 pcre_study_data is fixed. We nevertheless save it in a field for returning via
950 the pcre_fullinfo() function so that if it becomes variable in the future, we
951 don't have to change that code. */
953 extra = (pcre_extra *)(pcre_malloc)
954 (sizeof(pcre_extra) + sizeof(pcre_study_data));
958 *errorptr = "failed to get memory";
962 study = (pcre_study_data *)((char *)extra + sizeof(pcre_extra));
963 extra->flags = PCRE_EXTRA_STUDY_DATA;
964 extra->study_data = study;
966 study->size = sizeof(pcre_study_data);
971 study->flags |= PCRE_STUDY_MAPPED;
972 memcpy(study->start_bits, start_bits, sizeof(start_bits));
977 study->flags |= PCRE_STUDY_MINLEN;
978 study->minlength = min;
984 /* End of pcre_study.c */