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-2012 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"
51 #define SET_BIT(c) start_bits[c/8] |= (1 << (c&7))
53 /* Returns from set_start_bits() */
55 enum { SSB_FAIL
, SSB_DONE
, SSB_CONTINUE
, SSB_UNKNOWN
};
59 /*************************************************
60 * Find the minimum subject length for a group *
61 *************************************************/
63 /* Scan a parenthesized group and compute the minimum length of subject that
64 is needed to match it. This is a lower bound; it does not mean there is a
65 string of that length that matches. In UTF8 mode, the result is in characters
69 code pointer to start of group (the bracket)
70 startcode pointer to start of the whole pattern
71 options the compiling options
74 Returns: the minimum length
75 -1 if \C in UTF-8 mode or (*ACCEPT) was encountered
76 -2 internal error (missing capturing bracket)
77 -3 internal error (opcode not listed)
81 find_minlength(const pcre_uchar
*code
, const pcre_uchar
*startcode
, int options
,
85 /* PCRE_UTF16 has the same value as PCRE_UTF8. */
86 BOOL utf
= (options
& PCRE_UTF8
) != 0;
87 BOOL had_recurse
= FALSE
;
88 register int branchlength
= 0;
89 register pcre_uchar
*cc
= (pcre_uchar
*)code
+ 1 + LINK_SIZE
;
91 if (*code
== OP_CBRA
|| *code
== OP_SCBRA
||
92 *code
== OP_CBRAPOS
|| *code
== OP_SCBRAPOS
) cc
+= IMM2_SIZE
;
94 /* Scan along the opcodes for this branch. If we get to the end of the
95 branch, check the length against that of the other branches. */
101 register pcre_uchar op
= *cc
;
108 /* If there is only one branch in a condition, the implied branch has zero
109 length, so we don't add anything. This covers the DEFINE "condition"
112 cs
= cc
+ GET(cc
, 1);
115 cc
= cs
+ 1 + LINK_SIZE
;
119 /* Otherwise we can fall through and treat it the same as any other
132 d
= find_minlength(cc
, startcode
, options
, recurse_depth
);
135 do cc
+= GET(cc
, 1); while (*cc
== OP_ALT
);
139 /* ACCEPT makes things far too complicated; we have to give up. */
142 case OP_ASSERT_ACCEPT
:
145 /* Reached end of a branch; if it's a ket it is the end of a nested
146 call. If it's ALT it is an alternation in a nested call. If it is END it's
147 the end of the outer call. All can be handled by the same code. If an
148 ACCEPT was previously encountered, use the length that was in force at that
149 time, and pass back the shortest ACCEPT length. */
157 if (length
< 0 || (!had_recurse
&& branchlength
< length
))
158 length
= branchlength
;
159 if (op
!= OP_ALT
) return length
;
165 /* Skip over assertive subpatterns */
170 case OP_ASSERTBACK_NOT
:
171 do cc
+= GET(cc
, 1); while (*cc
== OP_ALT
);
174 /* Skip over things that don't match chars */
191 case OP_NOT_WORD_BOUNDARY
:
192 case OP_WORD_BOUNDARY
:
193 cc
+= PRIV(OP_lengths
)[*cc
];
196 /* Skip over a subpattern that has a {0} or {0,x} quantifier */
202 cc
+= PRIV(OP_lengths
)[*cc
];
203 do cc
+= GET(cc
, 1); while (*cc
== OP_ALT
);
207 /* Handle literal characters and + repetitions */
228 if (utf
&& HAS_EXTRALEN(cc
[-1])) cc
+= GET_EXTRALEN(cc
[-1]);
236 cc
+= (cc
[1] == OP_PROP
|| cc
[1] == OP_NOTPROP
)? 4 : 2;
239 /* Handle exact repetitions. The count is already in characters, but we
240 need to skip over a multibyte character in UTF8 mode. */
246 branchlength
+= GET2(cc
,1);
249 if (utf
&& HAS_EXTRALEN(cc
[-1])) cc
+= GET_EXTRALEN(cc
[-1]);
254 branchlength
+= GET2(cc
,1);
255 cc
+= 2 + IMM2_SIZE
+ ((cc
[1 + IMM2_SIZE
] == OP_PROP
256 || cc
[1 + IMM2_SIZE
] == OP_NOTPROP
)? 2 : 0);
259 /* Handle single-char non-literal matchers */
268 case OP_NOT_WHITESPACE
:
270 case OP_NOT_WORDCHAR
:
283 /* "Any newline" might match two characters, but it also might match just
291 /* The single-byte matcher means we can't proceed in UTF-8 mode. (In
292 non-UTF-8 mode \C will actually be turned into OP_ALLANY, so won't ever
293 appear, but leave the code, just in case.) */
303 /* For repeated character types, we have to test for \p and \P, which have
304 an extra two bytes of parameters. */
309 case OP_TYPEMINQUERY
:
311 case OP_TYPEPOSQUERY
:
312 if (cc
[1] == OP_PROP
|| cc
[1] == OP_NOTPROP
) cc
+= 2;
313 cc
+= PRIV(OP_lengths
)[op
];
319 if (cc
[1 + IMM2_SIZE
] == OP_PROP
320 || cc
[1 + IMM2_SIZE
] == OP_NOTPROP
) cc
+= 2;
321 cc
+= PRIV(OP_lengths
)[op
];
324 /* Check a class for variable quantification */
328 #if defined SUPPORT_UTF || defined COMPILE_PCRE16 || defined COMPILE_PCRE32
330 /* The original code caused an unsigned overflow in 64 bit systems,
331 so now we use a conditional statement. */
335 cc
+= PRIV(OP_lengths
)[OP_CLASS
];
337 cc
+= PRIV(OP_lengths
)[OP_CLASS
];
356 branchlength
+= GET2(cc
,1);
357 cc
+= 1 + 2 * IMM2_SIZE
;
366 /* Backreferences and subroutine calls are treated in the same way: we find
367 the minimum length for the subpattern. A recursion, however, causes an
368 a flag to be set that causes the length of this branch to be ignored. The
369 logic is that a recursion can only make sense if there is another
370 alternation that stops the recursing. That will provide the minimum length
371 (when no recursion happens). A backreference within the group that it is
372 referencing behaves in the same way.
374 If PCRE_JAVASCRIPT_COMPAT is set, a backreference to an unset bracket
375 matches an empty string (by default it causes a matching failure), so in
376 that case we must set the minimum length to zero. */
380 if ((options
& PCRE_JAVASCRIPT_COMPAT
) == 0)
382 ce
= cs
= (pcre_uchar
*)PRIV(find_bracket
)(startcode
, utf
, GET2(cc
, 1));
383 if (cs
== NULL
) return -2;
384 do ce
+= GET(ce
, 1); while (*ce
== OP_ALT
);
385 if (cc
> cs
&& cc
< ce
)
392 d
= find_minlength(cs
, startcode
, options
, recurse_depth
);
398 /* Handle repeated back references */
419 cc
+= 1 + 2 * IMM2_SIZE
;
427 branchlength
+= min
* d
;
430 /* We can easily detect direct recursion, but not mutual recursion. This is
431 caught by a recursion depth count. */
434 cs
= ce
= (pcre_uchar
*)startcode
+ GET(cc
, 1);
435 do ce
+= GET(ce
, 1); while (*ce
== OP_ALT
);
436 if ((cc
> cs
&& cc
< ce
) || recurse_depth
> 10)
440 branchlength
+= find_minlength(cs
, startcode
, options
, recurse_depth
+ 1);
445 /* Anything else does not or need not match a character. We can get the
446 item's length from the table, but for those that can match zero occurrences
447 of a character, we must take special action for UTF-8 characters. As it
448 happens, the "NOT" versions of these opcodes are used at present only for
449 ASCII characters, so they could be omitted from this list. However, in
450 future that may change, so we include them here so as not to leave a
451 gotcha for a future maintainer. */
486 case OP_NOTMINQUERYI
:
490 case OP_NOTPOSQUERYI
:
492 cc
+= PRIV(OP_lengths
)[op
];
494 if (utf
&& HAS_EXTRALEN(cc
[-1])) cc
+= GET_EXTRALEN(cc
[-1]);
498 /* Skip these, but we need to add in the name length. */
504 cc
+= PRIV(OP_lengths
)[op
] + cc
[1];
507 /* The remaining opcodes are just skipped over. */
516 cc
+= PRIV(OP_lengths
)[op
];
519 /* This should not occur: we list all opcodes explicitly so that when
520 new ones get added they are properly considered. */
526 /* Control never gets here */
531 /*************************************************
532 * Set a bit and maybe its alternate case *
533 *************************************************/
535 /* Given a character, set its first byte's bit in the table, and also the
536 corresponding bit for the other version of a letter if we are caseless. In
537 UTF-8 mode, for characters greater than 127, we can only do the caseless thing
538 when Unicode property support is available.
541 start_bits points to the bit map
542 p points to the character
543 caseless the caseless flag
544 cd the block with char table pointers
545 utf TRUE for UTF-8 / UTF-16 / UTF-32 mode
547 Returns: pointer after the character
550 static const pcre_uchar
*
551 set_table_bit(pcre_uint8
*start_bits
, const pcre_uchar
*p
, BOOL caseless
,
552 compile_data
*cd
, BOOL utf
)
567 c
= UCD_OTHERCASE(c
);
568 (void)PRIV(ord2utf
)(c
, buff
);
571 #endif /* Not SUPPORT_UCP */
574 #else /* Not SUPPORT_UTF */
575 (void)(utf
); /* Stops warning for unused parameter */
576 #endif /* SUPPORT_UTF */
578 /* Not UTF-8 mode, or character is less than 127. */
580 if (caseless
&& (cd
->ctypes
[c
] & ctype_letter
) != 0) SET_BIT(cd
->fcc
[c
]);
582 #endif /* COMPILE_PCRE8 */
584 #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
599 c
= UCD_OTHERCASE(c
);
604 #endif /* SUPPORT_UCP */
607 #else /* Not SUPPORT_UTF */
608 (void)(utf
); /* Stops warning for unused parameter */
609 #endif /* SUPPORT_UTF */
611 if (caseless
&& (cd
->ctypes
[c
] & ctype_letter
) != 0) SET_BIT(cd
->fcc
[c
]);
618 /*************************************************
619 * Set bits for a positive character type *
620 *************************************************/
622 /* This function sets starting bits for a character type. In UTF-8 mode, we can
623 only do a direct setting for bytes less than 128, as otherwise there can be
624 confusion with bytes in the middle of UTF-8 characters. In a "traditional"
625 environment, the tables will only recognize ASCII characters anyway, but in at
626 least one Windows environment, some higher bytes bits were set in the tables.
627 So we deal with that case by considering the UTF-8 encoding.
630 start_bits the starting bitmap
631 cbit type the type of character wanted
632 table_limit 32 for non-UTF-8; 16 for UTF-8
633 cd the block with char table pointers
639 set_type_bits(pcre_uint8
*start_bits
, int cbit_type
, unsigned int table_limit
,
642 register pcre_uint32 c
;
643 for (c
= 0; c
< table_limit
; c
++) start_bits
[c
] |= cd
->cbits
[c
+cbit_type
];
644 #if defined SUPPORT_UTF && defined COMPILE_PCRE8
645 if (table_limit
== 32) return;
646 for (c
= 128; c
< 256; c
++)
648 if ((cd
->cbits
[c
/8] & (1 << (c
&7))) != 0)
651 (void)PRIV(ord2utf
)(c
, buff
);
659 /*************************************************
660 * Set bits for a negative character type *
661 *************************************************/
663 /* This function sets starting bits for a negative character type such as \D.
664 In UTF-8 mode, we can only do a direct setting for bytes less than 128, as
665 otherwise there can be confusion with bytes in the middle of UTF-8 characters.
666 Unlike in the positive case, where we can set appropriate starting bits for
667 specific high-valued UTF-8 characters, in this case we have to set the bits for
668 all high-valued characters. The lowest is 0xc2, but we overkill by starting at
669 0xc0 (192) for simplicity.
672 start_bits the starting bitmap
673 cbit type the type of character wanted
674 table_limit 32 for non-UTF-8; 16 for UTF-8
675 cd the block with char table pointers
681 set_nottype_bits(pcre_uint8
*start_bits
, int cbit_type
, unsigned int table_limit
,
684 register pcre_uint32 c
;
685 for (c
= 0; c
< table_limit
; c
++) start_bits
[c
] |= ~cd
->cbits
[c
+cbit_type
];
686 #if defined SUPPORT_UTF && defined COMPILE_PCRE8
687 if (table_limit
!= 32) for (c
= 24; c
< 32; c
++) start_bits
[c
] = 0xff;
693 /*************************************************
694 * Create bitmap of starting bytes *
695 *************************************************/
697 /* This function scans a compiled unanchored expression recursively and
698 attempts to build a bitmap of the set of possible starting bytes. As time goes
699 by, we may be able to get more clever at doing this. The SSB_CONTINUE return is
700 useful for parenthesized groups in patterns such as (a*)b where the group
701 provides some optional starting bytes but scanning must continue at the outer
702 level to find at least one mandatory byte. At the outermost level, this
703 function fails unless the result is SSB_DONE.
706 code points to an expression
707 start_bits points to a 32-byte table, initialized to 0
708 utf TRUE if in UTF-8 / UTF-16 / UTF-32 mode
709 cd the block with char table pointers
711 Returns: SSB_FAIL => Failed to find any starting bytes
712 SSB_DONE => Found mandatory starting bytes
713 SSB_CONTINUE => Found optional starting bytes
714 SSB_UNKNOWN => Hit an unrecognized opcode
718 set_start_bits(const pcre_uchar
*code
, pcre_uint8
*start_bits
, BOOL utf
,
721 register pcre_uint32 c
;
722 int yield
= SSB_DONE
;
723 #if defined SUPPORT_UTF && defined COMPILE_PCRE8
724 int table_limit
= utf
? 16:32;
726 int table_limit
= 32;
730 /* ========================================================================= */
731 /* The following comment and code was inserted in January 1999. In May 2006,
732 when it was observed to cause compiler warnings about unused values, I took it
733 out again. If anybody is still using OS/2, they will have to put it back
736 /* This next statement and the later reference to dummy are here in order to
737 trick the optimizer of the IBM C compiler for OS/2 into generating correct
738 code. Apparently IBM isn't going to fix the problem, and we would rather not
739 disable optimization (in this module it actually makes a big difference, and
740 the pcre module can use all the optimization it can get). */
743 /* ========================================================================= */
748 BOOL try_next
= TRUE
;
749 const pcre_uchar
*tcode
= code
+ 1 + LINK_SIZE
;
751 if (*code
== OP_CBRA
|| *code
== OP_SCBRA
||
752 *code
== OP_CBRAPOS
|| *code
== OP_SCBRAPOS
) tcode
+= IMM2_SIZE
;
754 while (try_next
) /* Loop for items in this branch */
760 /* If we reach something we don't understand, it means a new opcode has
761 been created that hasn't been added to this code. Hopefully this problem
762 will be discovered during testing. */
767 /* Fail for a valid opcode that implies no starting bits. */
770 case OP_ASSERT_ACCEPT
:
797 case OP_NOTMINQUERYI
:
807 case OP_NOTPOSQUERYI
:
838 #if defined SUPPORT_UTF || !defined COMPILE_PCRE8
843 /* We can ignore word boundary tests. */
845 case OP_WORD_BOUNDARY
:
846 case OP_NOT_WORD_BOUNDARY
:
850 /* If we hit a bracket or a positive lookahead assertion, recurse to set
851 bits from within the subpattern. If it can't find anything, we have to
852 give up. If it finds some mandatory character(s), we are done for this
853 branch. Otherwise, carry on scanning after the subpattern. */
866 rc
= set_start_bits(tcode
, start_bits
, utf
, cd
);
867 if (rc
== SSB_FAIL
|| rc
== SSB_UNKNOWN
) return rc
;
868 if (rc
== SSB_DONE
) try_next
= FALSE
; else
870 do tcode
+= GET(tcode
, 1); while (*tcode
== OP_ALT
);
871 tcode
+= 1 + LINK_SIZE
;
875 /* If we hit ALT or KET, it means we haven't found anything mandatory in
876 this branch, though we might have found something optional. For ALT, we
877 continue with the next alternative, but we have to arrange that the final
878 result from subpattern is SSB_CONTINUE rather than SSB_DONE. For KET,
879 return SSB_CONTINUE: if this is the top level, that indicates failure,
880 but after a nested subpattern, it causes scanning to continue. */
883 yield
= SSB_CONTINUE
;
893 /* Skip over callout */
896 tcode
+= 2 + 2*LINK_SIZE
;
899 /* Skip over lookbehind and negative lookahead assertions */
903 case OP_ASSERTBACK_NOT
:
904 do tcode
+= GET(tcode
, 1); while (*tcode
== OP_ALT
);
905 tcode
+= 1 + LINK_SIZE
;
908 /* BRAZERO does the bracket, but carries on. */
913 rc
= set_start_bits(++tcode
, start_bits
, utf
, cd
);
914 if (rc
== SSB_FAIL
|| rc
== SSB_UNKNOWN
) return rc
;
915 /* =========================================================================
916 See the comment at the head of this function concerning the next line,
917 which was an old fudge for the benefit of OS/2.
919 ========================================================================= */
920 do tcode
+= GET(tcode
,1); while (*tcode
== OP_ALT
);
921 tcode
+= 1 + LINK_SIZE
;
924 /* SKIPZERO skips the bracket. */
928 do tcode
+= GET(tcode
,1); while (*tcode
== OP_ALT
);
929 tcode
+= 1 + LINK_SIZE
;
932 /* Single-char * or ? sets the bit and tries the next item */
940 tcode
= set_table_bit(start_bits
, tcode
+ 1, FALSE
, cd
, utf
);
949 tcode
= set_table_bit(start_bits
, tcode
+ 1, TRUE
, cd
, utf
);
952 /* Single-char upto sets the bit and tries the next */
957 tcode
= set_table_bit(start_bits
, tcode
+ 1 + IMM2_SIZE
, FALSE
, cd
, utf
);
963 tcode
= set_table_bit(start_bits
, tcode
+ 1 + IMM2_SIZE
, TRUE
, cd
, utf
);
966 /* At least one single char sets the bit and stops */
975 (void)set_table_bit(start_bits
, tcode
+ 1, FALSE
, cd
, utf
);
986 (void)set_table_bit(start_bits
, tcode
+ 1, TRUE
, cd
, utf
);
990 /* Special spacing and line-terminating items. These recognize specific
991 lists of characters. The difference between VSPACE and ANYNL is that the
992 latter can match the two-character CRLF sequence, but that is not
993 relevant for finding the first character, so their code here is
1002 #ifdef COMPILE_PCRE8
1003 SET_BIT(0xC2); /* For U+00A0 */
1004 SET_BIT(0xE1); /* For U+1680, U+180E */
1005 SET_BIT(0xE2); /* For U+2000 - U+200A, U+202F, U+205F */
1006 SET_BIT(0xE3); /* For U+3000 */
1007 #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1009 SET_BIT(0xFF); /* For characters > 255 */
1010 #endif /* COMPILE_PCRE[8|16|32] */
1013 #endif /* SUPPORT_UTF */
1017 #endif /* Not EBCDIC */
1018 #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1019 SET_BIT(0xFF); /* For characters > 255 */
1020 #endif /* COMPILE_PCRE[16|32] */
1034 #ifdef COMPILE_PCRE8
1035 SET_BIT(0xC2); /* For U+0085 */
1036 SET_BIT(0xE2); /* For U+2028, U+2029 */
1037 #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1039 SET_BIT(0xFF); /* For characters > 255 */
1040 #endif /* COMPILE_PCRE[8|16|32] */
1043 #endif /* SUPPORT_UTF */
1046 #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1047 SET_BIT(0xFF); /* For characters > 255 */
1053 /* Single character types set the bits and stop. Note that if PCRE_UCP
1054 is set, we do not see these op codes because \d etc are converted to
1055 properties. Therefore, these apply in the case when only characters less
1056 than 256 are recognized to match the types. */
1059 set_nottype_bits(start_bits
, cbit_digit
, table_limit
, cd
);
1064 set_type_bits(start_bits
, cbit_digit
, table_limit
, cd
);
1068 /* The cbit_space table has vertical tab as whitespace; we have to
1069 ensure it is set as not whitespace. Luckily, the code value is the same
1070 (0x0b) in ASCII and EBCDIC, so we can just adjust the appropriate bit. */
1072 case OP_NOT_WHITESPACE
:
1073 set_nottype_bits(start_bits
, cbit_space
, table_limit
, cd
);
1074 start_bits
[1] |= 0x08;
1078 /* The cbit_space table has vertical tab as whitespace; we have to not
1079 set it from the table. Luckily, the code value is the same (0x0b) in
1080 ASCII and EBCDIC, so we can just adjust the appropriate bit. */
1083 c
= start_bits
[1]; /* Save in case it was already set */
1084 set_type_bits(start_bits
, cbit_space
, table_limit
, cd
);
1085 start_bits
[1] = (start_bits
[1] & ~0x08) | c
;
1089 case OP_NOT_WORDCHAR
:
1090 set_nottype_bits(start_bits
, cbit_word
, table_limit
, cd
);
1095 set_type_bits(start_bits
, cbit_word
, table_limit
, cd
);
1099 /* One or more character type fudges the pointer and restarts, knowing
1100 it will hit a single character type and stop there. */
1103 case OP_TYPEMINPLUS
:
1104 case OP_TYPEPOSPLUS
:
1109 tcode
+= 1 + IMM2_SIZE
;
1112 /* Zero or more repeats of character types set the bits and then
1116 case OP_TYPEMINUPTO
:
1117 case OP_TYPEPOSUPTO
:
1118 tcode
+= IMM2_SIZE
; /* Fall through */
1121 case OP_TYPEMINSTAR
:
1122 case OP_TYPEPOSSTAR
:
1124 case OP_TYPEMINQUERY
:
1125 case OP_TYPEPOSQUERY
:
1135 SET_BIT(CHAR_SPACE
);
1139 #ifdef COMPILE_PCRE8
1140 SET_BIT(0xC2); /* For U+00A0 */
1141 SET_BIT(0xE1); /* For U+1680, U+180E */
1142 SET_BIT(0xE2); /* For U+2000 - U+200A, U+202F, U+205F */
1143 SET_BIT(0xE3); /* For U+3000 */
1144 #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1146 SET_BIT(0xFF); /* For characters > 255 */
1147 #endif /* COMPILE_PCRE[8|16|32] */
1150 #endif /* SUPPORT_UTF */
1153 #endif /* Not EBCDIC */
1165 #ifdef COMPILE_PCRE8
1166 SET_BIT(0xC2); /* For U+0085 */
1167 SET_BIT(0xE2); /* For U+2028, U+2029 */
1168 #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1170 SET_BIT(0xFF); /* For characters > 255 */
1171 #endif /* COMPILE_PCRE16 */
1174 #endif /* SUPPORT_UTF */
1179 set_nottype_bits(start_bits
, cbit_digit
, table_limit
, cd
);
1183 set_type_bits(start_bits
, cbit_digit
, table_limit
, cd
);
1186 /* The cbit_space table has vertical tab as whitespace; we have to
1187 ensure it gets set as not whitespace. Luckily, the code value is the
1188 same (0x0b) in ASCII and EBCDIC, so we can just adjust the appropriate
1191 case OP_NOT_WHITESPACE
:
1192 set_nottype_bits(start_bits
, cbit_space
, table_limit
, cd
);
1193 start_bits
[1] |= 0x08;
1196 /* The cbit_space table has vertical tab as whitespace; we have to
1197 avoid setting it. Luckily, the code value is the same (0x0b) in ASCII
1198 and EBCDIC, so we can just adjust the appropriate bit. */
1201 c
= start_bits
[1]; /* Save in case it was already set */
1202 set_type_bits(start_bits
, cbit_space
, table_limit
, cd
);
1203 start_bits
[1] = (start_bits
[1] & ~0x08) | c
;
1206 case OP_NOT_WORDCHAR
:
1207 set_nottype_bits(start_bits
, cbit_word
, table_limit
, cd
);
1211 set_type_bits(start_bits
, cbit_word
, table_limit
, cd
);
1218 /* Character class where all the information is in a bit map: set the
1219 bits and either carry on or not, according to the repeat count. If it was
1220 a negative class, and we are operating with UTF-8 characters, any byte
1221 with a value >= 0xc4 is a potentially valid starter because it starts a
1222 character with a value > 255. */
1225 #if defined SUPPORT_UTF && defined COMPILE_PCRE8
1228 start_bits
[24] |= 0xf0; /* Bits for 0xc4 - 0xc8 */
1229 memset(start_bits
+25, 0xff, 7); /* Bits for 0xc9 - 0xff */
1232 #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1233 SET_BIT(0xFF); /* For characters > 255 */
1241 map
= (pcre_uint8
*)tcode
;
1243 /* In UTF-8 mode, the bits in a bit map correspond to character
1244 values, not to byte values. However, the bit map we are constructing is
1245 for byte values. So we have to do a conversion for characters whose
1246 value is > 127. In fact, there are only two possible starting bytes for
1247 characters in the range 128 - 255. */
1249 #if defined SUPPORT_UTF && defined COMPILE_PCRE8
1252 for (c
= 0; c
< 16; c
++) start_bits
[c
] |= map
[c
];
1253 for (c
= 128; c
< 256; c
++)
1255 if ((map
[c
/8] && (1 << (c
&7))) != 0)
1257 int d
= (c
>> 6) | 0xc0; /* Set bit for this starter */
1258 start_bits
[d
/8] |= (1 << (d
&7)); /* and then skip on to the */
1259 c
= (c
& 0xc0) + 0x40 - 1; /* next relevant character. */
1266 /* In non-UTF-8 mode, the two bit maps are completely compatible. */
1267 for (c
= 0; c
< 32; c
++) start_bits
[c
] |= map
[c
];
1270 /* Advance past the bit map, and act on what follows. For a zero
1271 minimum repeat, continue; otherwise stop processing. */
1273 tcode
+= 32 / sizeof(pcre_uchar
);
1285 if (GET2(tcode
, 1) == 0) tcode
+= 1 + 2 * IMM2_SIZE
;
1286 else try_next
= FALSE
;
1294 break; /* End of bitmap class handling */
1296 } /* End of switch */
1297 } /* End of try_next loop */
1299 code
+= GET(code
, 1); /* Advance to next branch */
1301 while (*code
== OP_ALT
);
1309 /*************************************************
1310 * Study a compiled expression *
1311 *************************************************/
1313 /* This function is handed a compiled expression that it must study to produce
1314 information that will speed up the matching. It returns a pcre[16]_extra block
1315 which then gets handed back to pcre_exec().
1318 re points to the compiled expression
1319 options contains option bits
1320 errorptr points to where to place error messages;
1321 set NULL unless error
1323 Returns: pointer to a pcre[16]_extra block, with study_data filled in and
1324 the appropriate flags set;
1325 NULL on error or if no optimization possible
1328 #if defined COMPILE_PCRE8
1329 PCRE_EXP_DEFN pcre_extra
* PCRE_CALL_CONVENTION
1330 pcre_study(const pcre
*external_re
, int options
, const char **errorptr
)
1331 #elif defined COMPILE_PCRE16
1332 PCRE_EXP_DEFN pcre16_extra
* PCRE_CALL_CONVENTION
1333 pcre16_study(const pcre16
*external_re
, int options
, const char **errorptr
)
1334 #elif defined COMPILE_PCRE32
1335 PCRE_EXP_DEFN pcre32_extra
* PCRE_CALL_CONVENTION
1336 pcre32_study(const pcre32
*external_re
, int options
, const char **errorptr
)
1340 BOOL bits_set
= FALSE
;
1341 pcre_uint8 start_bits
[32];
1342 PUBL(extra
) *extra
= NULL
;
1343 pcre_study_data
*study
;
1344 const pcre_uint8
*tables
;
1346 compile_data compile_block
;
1347 const REAL_PCRE
*re
= (const REAL_PCRE
*)external_re
;
1351 if (re
== NULL
|| re
->magic_number
!= MAGIC_NUMBER
)
1353 *errorptr
= "argument is not a compiled regular expression";
1357 if ((re
->flags
& PCRE_MODE
) == 0)
1359 #if defined COMPILE_PCRE8
1360 *errorptr
= "argument not compiled in 8 bit mode";
1361 #elif defined COMPILE_PCRE16
1362 *errorptr
= "argument not compiled in 16 bit mode";
1363 #elif defined COMPILE_PCRE32
1364 *errorptr
= "argument not compiled in 32 bit mode";
1369 if ((options
& ~PUBLIC_STUDY_OPTIONS
) != 0)
1371 *errorptr
= "unknown or incorrect option bit(s) set";
1375 code
= (pcre_uchar
*)re
+ re
->name_table_offset
+
1376 (re
->name_count
* re
->name_entry_size
);
1378 /* For an anchored pattern, or an unanchored pattern that has a first char, or
1379 a multiline pattern that matches only at "line starts", there is no point in
1380 seeking a list of starting bytes. */
1382 if ((re
->options
& PCRE_ANCHORED
) == 0 &&
1383 (re
->flags
& (PCRE_FIRSTSET
|PCRE_STARTLINE
)) == 0)
1387 /* Set the character tables in the block that is passed around */
1389 tables
= re
->tables
;
1391 #if defined COMPILE_PCRE8
1393 (void)pcre_fullinfo(external_re
, NULL
, PCRE_INFO_DEFAULT_TABLES
,
1395 #elif defined COMPILE_PCRE16
1397 (void)pcre16_fullinfo(external_re
, NULL
, PCRE_INFO_DEFAULT_TABLES
,
1399 #elif defined COMPILE_PCRE32
1401 (void)pcre32_fullinfo(external_re
, NULL
, PCRE_INFO_DEFAULT_TABLES
,
1405 compile_block
.lcc
= tables
+ lcc_offset
;
1406 compile_block
.fcc
= tables
+ fcc_offset
;
1407 compile_block
.cbits
= tables
+ cbits_offset
;
1408 compile_block
.ctypes
= tables
+ ctypes_offset
;
1410 /* See if we can find a fixed set of initial characters for the pattern. */
1412 memset(start_bits
, 0, 32 * sizeof(pcre_uint8
));
1413 rc
= set_start_bits(code
, start_bits
, (re
->options
& PCRE_UTF8
) != 0,
1415 bits_set
= rc
== SSB_DONE
;
1416 if (rc
== SSB_UNKNOWN
)
1418 *errorptr
= "internal error: opcode not recognized";
1423 /* Find the minimum length of subject string. */
1425 switch(min
= find_minlength(code
, code
, re
->options
, 0))
1427 case -2: *errorptr
= "internal error: missing capturing bracket"; return NULL
;
1428 case -3: *errorptr
= "internal error: opcode not recognized"; return NULL
;
1432 /* If a set of starting bytes has been identified, or if the minimum length is
1433 greater than zero, or if JIT optimization has been requested, or if
1434 PCRE_STUDY_EXTRA_NEEDED is set, get a pcre[16]_extra block and a
1435 pcre_study_data block. The study data is put in the latter, which is pointed to
1436 by the former, which may also get additional data set later by the calling
1437 program. At the moment, the size of pcre_study_data is fixed. We nevertheless
1438 save it in a field for returning via the pcre_fullinfo() function so that if it
1439 becomes variable in the future, we don't have to change that code. */
1441 if (bits_set
|| min
> 0 || (options
& (
1443 PCRE_STUDY_JIT_COMPILE
| PCRE_STUDY_JIT_PARTIAL_SOFT_COMPILE
|
1444 PCRE_STUDY_JIT_PARTIAL_HARD_COMPILE
|
1446 PCRE_STUDY_EXTRA_NEEDED
)) != 0)
1448 extra
= (PUBL(extra
) *)(PUBL(malloc
))
1449 (sizeof(PUBL(extra
)) + sizeof(pcre_study_data
));
1452 *errorptr
= "failed to get memory";
1456 study
= (pcre_study_data
*)((char *)extra
+ sizeof(PUBL(extra
)));
1457 extra
->flags
= PCRE_EXTRA_STUDY_DATA
;
1458 extra
->study_data
= study
;
1460 study
->size
= sizeof(pcre_study_data
);
1463 /* Set the start bits always, to avoid unset memory errors if the
1464 study data is written to a file, but set the flag only if any of the bits
1465 are set, to save time looking when none are. */
1469 study
->flags
|= PCRE_STUDY_MAPPED
;
1470 memcpy(study
->start_bits
, start_bits
, sizeof(start_bits
));
1472 else memset(study
->start_bits
, 0, 32 * sizeof(pcre_uint8
));
1477 pcre_uint8
*ptr
= start_bits
;
1480 printf("Start bits:\n");
1481 for (i
= 0; i
< 32; i
++)
1482 printf("%3d: %02x%s", i
* 8, *ptr
++, ((i
+ 1) & 0x7) != 0? " " : "\n");
1486 /* Always set the minlength value in the block, because the JIT compiler
1487 makes use of it. However, don't set the bit unless the length is greater than
1488 zero - the interpretive pcre_exec() and pcre_dfa_exec() needn't waste time
1489 checking the zero case. */
1493 study
->flags
|= PCRE_STUDY_MINLEN
;
1494 study
->minlength
= min
;
1496 else study
->minlength
= 0;
1498 /* If JIT support was compiled and requested, attempt the JIT compilation.
1499 If no starting bytes were found, and the minimum length is zero, and JIT
1500 compilation fails, abandon the extra block and return NULL, unless
1501 PCRE_STUDY_EXTRA_NEEDED is set. */
1504 extra
->executable_jit
= NULL
;
1505 if ((options
& PCRE_STUDY_JIT_COMPILE
) != 0)
1506 PRIV(jit_compile
)(re
, extra
, JIT_COMPILE
);
1507 if ((options
& PCRE_STUDY_JIT_PARTIAL_SOFT_COMPILE
) != 0)
1508 PRIV(jit_compile
)(re
, extra
, JIT_PARTIAL_SOFT_COMPILE
);
1509 if ((options
& PCRE_STUDY_JIT_PARTIAL_HARD_COMPILE
) != 0)
1510 PRIV(jit_compile
)(re
, extra
, JIT_PARTIAL_HARD_COMPILE
);
1512 if (study
->flags
== 0 && (extra
->flags
& PCRE_EXTRA_EXECUTABLE_JIT
) == 0 &&
1513 (options
& PCRE_STUDY_EXTRA_NEEDED
) == 0)
1515 #if defined COMPILE_PCRE8
1516 pcre_free_study(extra
);
1517 #elif defined COMPILE_PCRE16
1518 pcre16_free_study(extra
);
1519 #elif defined COMPILE_PCRE32
1520 pcre32_free_study(extra
);
1531 /*************************************************
1532 * Free the study data *
1533 *************************************************/
1535 /* This function frees the memory that was obtained by pcre_study().
1537 Argument: a pointer to the pcre[16]_extra block
1541 #if defined COMPILE_PCRE8
1543 pcre_free_study(pcre_extra
*extra
)
1544 #elif defined COMPILE_PCRE16
1546 pcre16_free_study(pcre16_extra
*extra
)
1547 #elif defined COMPILE_PCRE32
1549 pcre32_free_study(pcre32_extra
*extra
)
1555 if ((extra
->flags
& PCRE_EXTRA_EXECUTABLE_JIT
) != 0 &&
1556 extra
->executable_jit
!= NULL
)
1557 PRIV(jit_free
)(extra
->executable_jit
);
1562 /* End of pcre_study.c */