| blob | 222cc16516e09f83dfdfa408d2cb1e54274ca7cb |
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 -----------------------------------------------------------------------------
40 */
43 /* This module contains the external function pcre_compile(), along with
44 supporting internal functions that are not used by other modules. */
56 /* When DEBUG is defined, we need the pcre_printint() function, which is also
57 used by pcretest. DEBUG is not defined when building a production library. */
59 #ifdef PCRE_DEBUG
61 #endif
64 /* Macro for setting individual bits in class bitmaps. */
66 #define SETBIT(a,b) a[b/8] |= (1 << (b%8))
68 /* Maximum length value to check against when making sure that the integer that
69 holds the compiled pattern length does not overflow. We make it a bit less than
70 INT_MAX to allow for adding in group terminating bytes, so that we don't have
71 to check them every time. */
73 #define OFLOW_MAX (INT_MAX - 20)
76 /*************************************************
77 * Code parameters and static tables *
78 *************************************************/
80 /* This value specifies the size of stack workspace that is used during the
81 first pre-compile phase that determines how much memory is required. The regex
82 is partly compiled into this space, but the compiled parts are discarded as
83 soon as they can be, so that hopefully there will never be an overrun. The code
84 does, however, check for an overrun. The largest amount I've seen used is 218,
85 so this number is very generous.
87 The same workspace is used during the second, actual compile phase for
88 remembering forward references to groups so that they can be filled in at the
89 end. Each entry in this list occupies LINK_SIZE bytes, so even when LINK_SIZE
90 is 4 there is plenty of room. */
92 //#define COMPILE_WORK_SIZE (4096)
93 #define COMPILE_WORK_SIZE (2048) //tierney: smaller size to avoid stack overflow when compiling patterns with many nested ()'s
96 /* Table for handling escaped characters in the range '0'-'z'. Positive returns
97 are simple data values; negative values are for special things like \d and so
98 on. Zero means further processing is needed (for things like \x), or the escape
99 is invalid. */
113 };
140 };
141 #endif
144 /* Table of special "verbs" like (*PRUNE) */
160 };
165 /* Tables of names of POSIX character classes and their lengths. The list is
166 terminated by a zero length entry. The first three must be alpha, lower, upper,
167 as this is assumed for handling case independence. */
177 /* Table of class bit maps for each POSIX class. Each class is formed from a
178 base map, with an optional addition or removal of another map. Then, for some
179 classes, there is some additional tweaking: for [:blank:] the vertical space
180 characters are removed, and for [:alpha:] and [:alnum:] the underscore
181 character is removed. The triples in the table consist of the base map offset,
182 second map offset or -1 if no second map, and a non-negative value for map
183 addition or a negative value for map subtraction (if there are two maps). The
184 absolute value of the third field has these meanings: 0 => no tweaking, 1 =>
185 remove vertical space characters, 2 => remove underscore. */
202 };
205 #define STRING(a) # a
206 #define XSTRING(s) STRING(s)
208 /* The texts of compile-time error messages. These are "char *" because they
209 are passed to the outside world. Do not ever re-use any error number, because
210 they are documented. Always add a new error instead. Messages marked DEAD below
211 are no longer used. */
214 #ifdef AVMPLUS_PCRE
220 /* 5 */
226 /* 10 */
232 /* 15 */
238 /* 20 */
244 /* 25 */
250 /* 30 */
256 /* 35 */
262 /* 40 */
268 /* 45 */
274 /* 50 */
280 /* 55 */
286 /* 60 */
288 ""
295 /* 5 */
301 /* 10 */
307 /* 15 */
313 /* 20 */
319 /* 25 */
325 /* 30 */
331 /* 35 */
337 /* 40 */
343 /* 45 */
349 /* 50 */
355 /* 55 */
361 /* 60 */
363 "number is too big"
365 };
368 /* Table to identify digits and hex digits. This is used when compiling
369 patterns. Note that the tables in chartables are dependent on the locale, and
370 may mark arbitrary characters as digits - but the PCRE compiling code expects
371 to handle only 0-9, a-z, and A-Z as digits when compiling. That is why we have
372 a private table here. It costs 256 bytes, but it is a lot faster than doing
373 character value tests (at least in some simple cases I timed), and in some
374 applications one wants PCRE to compile efficiently as well as match
375 efficiently.
377 For convenience, we use the same bit definitions as in chartables:
379 0x04 decimal digit
380 0x08 hexadecimal digit
382 Then we can use ctype_digit and ctype_xdigit in the code. */
386 {
422 {
489 #endif
492 /* Definition to allow mutual recursion */
494 static BOOL
500 /*************************************************
501 * Handle escapes *
502 *************************************************/
504 /* This function is called when a \ has been encountered. It either returns a
505 positive value for a simple escape such as \n, or a negative value which
506 encodes one of the more complicated things such as \d. A backreference to group
507 n is returned as -(ESC_REF + n); ESC_REF is the highest ESC_xxx macro. When
508 UTF-8 is enabled, a positive value greater than 255 may be returned. On entry,
509 ptr is pointing at the \. On exit, it is on the final character of the escape
510 sequence.
512 Arguments:
513 ptrptr points to the pattern position pointer
514 errorcodeptr points to the errorcode variable
515 bracount number of previous extracting brackets
516 options the options bits
517 isclass TRUE if inside a character class
519 Returns: zero or positive => a data character
520 negative => a special escape sequence
521 on error, errorcodeptr is set
522 */
524 static int
527 {
535 /* If backslash is at the end of the pattern, it's an error. */
539 /* Non-alphamerics are literals. For digits or letters, do an initial lookup in
540 a table. A non-zero result is something that can be returned immediately.
541 Otherwise further processing may be required. */
550 #endif
552 /* Escapes that need further processing, or are illegal. */
554 else
555 {
560 {
561 /* A number of Perl escapes are not handled by PCRE. We give an explicit
562 error. */
572 /* \g must be followed by a number, either plain or braced. If positive, it
573 is an absolute backreference. If negative, it is a relative backreference.
574 This is a Perl 5.10 feature. Perl 5.10 also supports \g{name} as a
575 reference to a named group. This is part of Perl's movement towards a
576 unified syntax for back references. As this is synonymous with \k{name}, we
577 fudge it up by pretending it really was \k. */
581 {
586 {
589 }
591 ptr++;
592 }
596 {
598 ptr++;
599 }
607 {
610 }
613 {
616 }
619 {
621 {
624 }
626 }
631 /* The handling of escape sequences consisting of a string of digits
632 starting with one that is not zero is not straightforward. By experiment,
633 the way Perl works seems to be as follows:
635 Outside a character class, the digits are read as a decimal number. If the
636 number is less than 10, or if there are that many previous extracting
637 left brackets, then it is a back reference. Otherwise, up to three octal
638 digits are read to form an escaped byte. Thus \123 is likely to be octal
639 123 (cf \0123, which is octal 012 followed by the literal 3). If the octal
640 value is greater than 377, the least significant 8 bits are taken. Inside a
641 character class, \ followed by a digit is always an octal number. */
647 {
653 {
656 }
658 {
661 }
663 }
665 /* Handle an octal number following \. If the first digit is 8 or 9, Perl
666 generates a binary zero byte and treats the digit as a following literal.
667 Thus we have to pull back the pointer by one. */
670 {
671 ptr--;
674 }
676 /* \0 always starts an octal number, but we may drop through to here with a
677 larger first octal digit. The original code used just to take the least
678 significant 8 bits of octal numbers (I think this is what early Perls used
679 to do). Nowadays we allow for larger numbers in UTF-8 mode, but no more
680 than 3 octal digits. */
689 /* \x is complicated. \x{ddd} is a character number which can be greater
690 than 0xff in utf8 mode, but only if the ddd are hex digits. If not, { is
691 treated as a data character. */
695 {
701 {
704 count++;
712 #endif
713 }
716 {
720 }
722 /* If the sequence of hex digits does not end with '}', then we don't
723 recognize this construct; fall through to the normal \x handling. */
724 }
726 /* Read just a single-byte hex-defined char */
730 {
739 #endif
740 }
743 /* For \c, a following letter is upper-cased; then the 0x40 bit is flipped.
744 This coding is ASCII-specific, but then the whole concept of \cx is
745 ASCII-specific. (However, an EBCDIC equivalent has now been added.) */
750 {
753 }
761 #endif
764 /* PCRE_EXTRA enables extensions to Perl in the matter of escapes. Any
765 other alphameric following \ is an error if PCRE_EXTRA was set; otherwise,
766 for Perl compatibility, it is a literal. This code looks a bit odd, but
767 there used to be some cases other than the default, and there may be again
768 in future, so I haven't "optimized" it. */
771 #ifdef AVMPLUS_PCRE
773 {
775 }
776 #else
778 {
782 }
783 #endif
785 }
786 }
790 }
794 #ifdef SUPPORT_UCP
795 /*************************************************
796 * Handle \P and \p *
797 *************************************************/
799 /* This function is called after \P or \p has been encountered, provided that
800 PCRE is compiled with support for Unicode properties. On entry, ptrptr is
801 pointing at the P or p. On exit, it is pointing at the final character of the
802 escape sequence.
804 Argument:
805 ptrptr points to the pattern position pointer
806 negptr points to a boolean that is set TRUE for negation else FALSE
807 dptr points to an int that is set to the detailed property value
808 errorcodeptr points to the error code variable
810 Returns: type value from ucp_type_table, or -1 for an invalid type
811 */
813 static int
815 {
825 /* \P or \p can be followed by a name in {}, optionally preceded by ^ for
826 negation. */
829 {
831 {
833 ptr++;
834 }
836 {
841 }
844 }
846 /* Otherwise there is just one following character */
848 else
849 {
852 }
856 /* Search for a recognized property name using binary chop */
862 {
866 {
869 }
871 }
877 ERROR_RETURN:
881 }
882 #endif
887 /*************************************************
888 * Check for counted repeat *
889 *************************************************/
891 /* This function is called when a '{' is encountered in a place where it might
892 start a quantifier. It looks ahead to see if it really is a quantifier or not.
893 It is only a quantifier if it is one of the forms {ddd} {ddd,} or {ddd,ddd}
894 where the ddds are digits.
896 Arguments:
897 p pointer to the first char after '{'
899 Returns: TRUE or FALSE
900 */
902 static BOOL
904 {
916 }
920 /*************************************************
921 * Read repeat counts *
922 *************************************************/
924 /* Read an item of the form {n,m} and return the values. This is called only
925 after is_counted_repeat() has confirmed that a repeat-count quantifier exists,
926 so the syntax is guaranteed to be correct, but we need to check the values.
928 Arguments:
929 p pointer to first char after '{'
930 minp pointer to int for min
931 maxp pointer to int for max
932 returned as -1 if no max
933 errorcodeptr points to error code variable
935 Returns: pointer to '}' on success;
936 current ptr on error, with errorcodeptr set non-zero
937 */
941 {
945 /* Read the minimum value and do a paranoid check: a negative value indicates
946 an integer overflow. */
950 {
953 }
955 /* Read the maximum value if there is one, and again do a paranoid on its size.
956 Also, max must not be less than min. */
959 {
961 {
965 {
968 }
970 {
973 }
974 }
975 }
977 /* Fill in the required variables, and pass back the pointer to the terminating
978 '}'. */
983 }
987 /*************************************************
988 * Find forward referenced subpattern *
989 *************************************************/
991 /* This function scans along a pattern's text looking for capturing
992 subpatterns, and counting them. If it finds a named pattern that matches the
993 name it is given, it returns its number. Alternatively, if the name is NULL, it
994 returns when it reaches a given numbered subpattern. This is used for forward
995 references to subpatterns. We know that if (?P< is encountered, the name will
996 be terminated by '>' because that is checked in the first pass.
998 Arguments:
999 ptr current position in the pattern
1000 count current count of capturing parens so far encountered
1001 name name to seek, or NULL if seeking a numbered subpattern
1002 lorn name length, or subpattern number if name is NULL
1003 xmode TRUE if we are in /x mode
1005 Returns: the number of the named subpattern, or -1 if not found
1006 */
1008 static int
1010 BOOL xmode)
1011 {
1015 {
1018 /* Skip over backslashed characters and also entire \Q...\E */
1021 {
1024 {
1028 }
1030 }
1032 /* Skip over character classes */
1035 {
1037 {
1040 {
1043 {
1047 }
1049 }
1050 }
1052 }
1054 /* Skip comments in /x mode */
1057 {
1061 }
1063 /* An opening parens must now be a real metacharacter */
1067 {
1068 count++;
1071 }
1076 /* We have to disambiguate (?<! and (?<= from (?<name> */
1082 count++;
1092 }
1095 }
1099 /*************************************************
1100 * Find first significant op code *
1101 *************************************************/
1103 /* This is called by several functions that scan a compiled expression looking
1104 for a fixed first character, or an anchoring op code etc. It skips over things
1105 that do not influence this. For some calls, a change of option is important.
1106 For some calls, it makes sense to skip negative forward and all backward
1107 assertions, and also the \b assertion; for others it does not.
1109 Arguments:
1110 code pointer to the start of the group
1111 options pointer to external options
1112 optbit the option bit whose changing is significant, or
1113 zero if none are
1114 skipassert TRUE if certain assertions are to be skipped
1116 Returns: pointer to the first significant opcode
1117 */
1121 BOOL skipassert)
1122 {
1124 {
1126 {
1144 /* Fall through */
1155 }
1156 }
1157 /* Control never reaches here */
1158 }
1161 /*****************************************************************************
1162 * Generic stack used by find_fixedlength, is_anchored, is_startline *
1163 * to avoid unbounded recursion *
1164 *****************************************************************************/
1166 #define TYPED_SEGMENT_SIZE 20
1184 };
1193 #ifdef DEBUG
1196 #endif
1197 };
1201 {
1205 }
1212 #ifdef DEBUG
1215 #endif
1216 {
1218 }
1222 {
1223 #if 0 && defined DEBUG
1224 // For the morbidly curious only. See bugzilla 502589 for some data.
1228 #endif
1232 }
1236 {
1238 }
1242 {
1246 }
1250 {
1255 #ifdef DEBUG
1256 depth++;
1259 #endif
1261 }
1265 {
1267 #ifdef DEBUG
1268 depth--;
1269 #endif
1270 top--;
1275 }
1279 {
1287 }
1291 {
1296 {
1299 }
1300 else
1301 {
1304 }
1305 }
1307 /*************************************************
1308 * Find the fixed length of a pattern *
1309 *************************************************/
1311 /* Scan a pattern and compute the fixed length of subject that will match it,
1312 if the length is fixed. This is needed for dealing with backward assertions.
1313 In UTF8 mode, the result is in characters rather than bytes.
1315 Arguments:
1316 code points to the start of the pattern (the bracket)
1317 options the compiling options
1319 Returns: the fixed length, or -1 if there is no fixed length,
1320 or -2 if \C was encountered
1321 */
1323 // processing information for find_fixedlength
1328 /* the work item from which this work item was derived */
1332 #define FFL_NEWITEM(ITEM) \
1333 ITEM.code = 0; \
1334 ITEM.length = -1; \
1335 ITEM.branchlength = 0; \
1336 ITEM.parent = 0
1338 static int
1340 {
1344 pi_ffl work_item;
1346 /* set up the first work item */
1351 /* start the processing loop */
1360 {
1363 {
1368 {
1369 /*
1370 - create a new workitem for the remainder of this item (or alter the
1371 current one)
1372 - create a new workitem with the bracketed code and put it on the stack
1373 - this results in the following stack state: new_item -> work_item -> ...
1374 this way we keep the processing order as if recursion would have been
1375 used
1376 - move the code pointer of work_item after the bracketed code
1377 - start the next iteration (with new_item)
1378 * */
1383 pi_ffl new_item;
1391 // original code added 1 + LINK_SIZE to the pointer
1392 // we don't need this as the processing of an item start with that
1397 }
1399 /* Reached end of a branch; if it's a ket it is the end of a nested
1400 call. If it's ALT it is an alternation in a nested call. If it is
1401 END it's the end of the outer call. All can be handled by the same code.*/
1409 /* clean up the stack and current item and return -1 */
1413 {
1414 /* end of the pattern, clean up and return */
1417 else
1418 /* KET is the end of in internal group, propagate the brenchlength back
1419 to the parent group's branchlength */
1420 {
1424 }
1425 }
1430 /* Skip over assertive subpatterns */
1437 /* Fall through */
1439 /* Skip over things that don't match chars */
1458 /* Handle literal characters */
1463 branchlength++;
1465 #ifdef SUPPORT_UTF8
1467 {
1469 }
1470 #endif
1473 /* Handle exact repetitions. The count is already in characters, but we
1474 need to skip over a multibyte character in UTF8 mode. */
1479 #ifdef SUPPORT_UTF8
1481 {
1483 }
1484 #endif
1493 /* Handle single-char matchers */
1498 /* Fall through */
1507 branchlength++;
1508 cc++;
1511 /* The single-byte matcher isn't allowed */
1514 /* free the proc stack and the current item*/
1517 /* Check a class for variable quantification */
1519 #ifdef SUPPORT_UTF8
1522 /* Fall through */
1523 #endif
1530 {
1535 /* free the proc stack and the current item*/
1546 branchlength++;
1547 }
1550 /* Anything else is variable length */
1553 /* free the proc stack and the current item*/
1555 }
1556 }
1557 }
1558 /* Control never gets here */
1561 }
1563 #undef FFL_NEWITEM
1567 /*************************************************
1568 * Scan compiled regex for numbered bracket *
1569 *************************************************/
1571 /* This little function scans through a compiled pattern until it finds a
1572 capturing bracket with the given number.
1574 Arguments:
1575 code points to start of expression
1576 utf8 TRUE in UTF-8 mode
1577 number the required bracket number
1579 Returns: pointer to the opcode for the bracket, or NULL if not found
1580 */
1584 {
1586 {
1590 /* XCLASS is used for classes that cannot be represented just by a bit
1591 map. This includes negated single high-valued characters. The length in
1592 the table is zero; the actual length is stored in the compiled code. */
1596 /* Handle capturing bracket */
1599 {
1603 }
1605 /* Otherwise, we can get the item's length from the table, except that for
1606 repeated character types, we have to test for \p and \P, which have an extra
1607 two bytes of parameters. */
1609 else
1610 {
1612 {
1631 }
1633 /* Add in the fixed length from the table */
1637 /* In UTF-8 mode, opcodes that are followed by a character may be followed by
1638 a multi-byte character. The length in the table is a minimum, so we have to
1639 arrange to skip the extra bytes. */
1641 #ifdef SUPPORT_UTF8
1643 {
1661 }
1662 #endif
1663 }
1664 }
1665 }
1669 /*************************************************
1670 * Scan compiled regex for recursion reference *
1671 *************************************************/
1673 /* This little function scans through a compiled pattern until it finds an
1674 instance of OP_RECURSE.
1676 Arguments:
1677 code points to start of expression
1678 utf8 TRUE in UTF-8 mode
1680 Returns: pointer to the opcode for OP_RECURSE, or NULL if not found
1681 */
1685 {
1687 {
1692 /* XCLASS is used for classes that cannot be represented just by a bit
1693 map. This includes negated single high-valued characters. The length in
1694 the table is zero; the actual length is stored in the compiled code. */
1698 /* Otherwise, we can get the item's length from the table, except that for
1699 repeated character types, we have to test for \p and \P, which have an extra
1700 two bytes of parameters. */
1702 else
1703 {
1705 {
1724 }
1726 /* Add in the fixed length from the table */
1730 /* In UTF-8 mode, opcodes that are followed by a character may be followed
1731 by a multi-byte character. The length in the table is a minimum, so we have
1732 to arrange to skip the extra bytes. */
1734 #ifdef SUPPORT_UTF8
1736 {
1754 }
1755 #endif
1756 }
1757 }
1758 }
1762 /*************************************************
1763 * Scan compiled branch for non-emptiness *
1764 *************************************************/
1766 /* This function scans through a branch of a compiled pattern to see whether it
1767 can match the empty string or not. It is called from could_be_empty()
1768 below and from compile_branch() when checking for an unlimited repeat of a
1769 group that can match nothing. Note that first_significant_code() skips over
1770 assertions. If we hit an unclosed bracket, we return "empty" - this means we've
1771 struck an inner bracket whose current branch will already have been scanned.
1773 Arguments:
1774 code points to start of search
1775 endcode points to where to stop
1776 utf8 TRUE if in UTF8 mode
1778 Returns: TRUE if what is matched could be empty
1779 */
1781 static BOOL
1783 {
1789 {
1794 /* Groups with zero repeats can of course be empty; skip them. */
1797 {
1802 }
1804 /* For other groups, scan the branches. */
1807 {
1808 BOOL empty_branch;
1811 /* Scan a closed bracket */
1814 do
1815 {
1819 }
1824 }
1826 /* Handle the other opcodes */
1829 {
1830 /* Check for quantifiers after a class. XCLASS is used for classes that
1831 cannot be represented just by a bit map. This includes negated single
1832 high-valued characters. The length in _pcre_OP_lengths[] is zero; the
1833 actual length is stored in the compiled code, so we must update "code"
1834 here. */
1836 #ifdef SUPPORT_UTF8
1840 #endif
1846 #ifdef SUPPORT_UTF8
1847 CHECK_CLASS_REPEAT:
1848 #endif
1851 {
1867 }
1870 /* Opcodes that must match a character */
1900 /* These are going to continue, as they may be empty, but we have to
1901 fudge the length for the \p and \P cases. */
1912 /* Same for these */
1920 /* End of branch */
1928 /* In UTF-8 mode, STAR, MINSTAR, POSSTAR, QUERY, MINQUERY, POSQUERY, UPTO,
1929 MINUPTO, and POSUPTO may be followed by a multibyte character */
1931 #ifdef SUPPORT_UTF8
1943 #endif
1944 }
1945 }
1948 }
1952 /*************************************************
1953 * Scan compiled regex for non-emptiness *
1954 *************************************************/
1956 /* This function is called to check for left recursive calls. We want to check
1957 the current branch of the current pattern to see if it could match the empty
1958 string. If it could, we must look outwards for branches at other levels,
1959 stopping when we pass beyond the bracket which is the subject of the recursion.
1961 Arguments:
1962 code points to start of the recursion
1963 endcode points to where to stop (current RECURSE item)
1964 bcptr points to the chain of current (unclosed) branch starts
1965 utf8 TRUE if in UTF-8 mode
1967 Returns: TRUE if what is matched could be empty
1968 */
1970 static BOOL
1972 BOOL utf8)
1973 {
1975 {
1978 }
1980 }
1984 /*************************************************
1985 * Check for POSIX class syntax *
1986 *************************************************/
1988 /* This function is called when the sequence "[:" or "[." or "[=" is
1989 encountered in a character class. It checks whether this is followed by an
1990 optional ^ and then a sequence of letters, terminated by a matching ":]" or
1991 ".]" or "=]".
1993 Argument:
1994 ptr pointer to the initial [
1995 endptr where to return the end pointer
1996 cd pointer to compile data
1998 Returns: TRUE or FALSE
1999 */
2001 static BOOL
2003 {
2009 {
2012 }
2014 }
2019 /*************************************************
2020 * Check POSIX class name *
2021 *************************************************/
2023 /* This function is called to check the name given in a POSIX-style class entry
2024 such as [:alnum:].
2026 Arguments:
2027 ptr points to the first letter
2028 len the length of the name
2030 Returns: a value representing the name, or -1 if unknown
2031 */
2033 static int
2035 {
2038 {
2041 yield++;
2042 }
2044 }
2047 /*************************************************
2048 * Adjust OP_RECURSE items in repeated group *
2049 *************************************************/
2051 /* OP_RECURSE items contain an offset from the start of the regex to the group
2052 that is referenced. This means that groups can be replicated for fixed
2053 repetition simply by copying (because the recursion is allowed to refer to
2054 earlier groups that are outside the current group). However, when a group is
2055 optional (i.e. the minimum quantifier is zero), OP_BRAZERO is inserted before
2056 it, after it has been compiled. This means that any OP_RECURSE items within it
2057 that refer to the group itself or any contained groups have to have their
2058 offsets adjusted. That one of the jobs of this function. Before it is called,
2059 the partially compiled regex must be temporarily terminated with OP_END.
2061 This function has been extended with the possibility of forward references for
2062 recursions and subroutine calls. It must also check the list of such references
2063 for the group we are dealing with. If it finds that one of the recursions in
2064 the current group is on this list, it adjusts the offset in the list, not the
2065 value in the reference (which is a group number).
2067 Arguments:
2068 group points to the start of the group
2069 adjust the amount by which the group is to be moved
2070 utf8 TRUE in UTF-8 mode
2071 cd contains pointers to tables etc.
2072 save_hwm the hwm forward reference pointer at the start of the group
2074 Returns: nothing
2075 */
2077 static void
2080 {
2084 {
2088 /* See if this recursion is on the forward reference list. If so, adjust the
2089 reference. */
2092 {
2095 {
2098 }
2099 }
2101 /* Otherwise, adjust the recursion offset if it's after the start of this
2102 group. */
2105 {
2108 }
2111 }
2112 }
2116 /*************************************************
2117 * Insert an automatic callout point *
2118 *************************************************/
2120 /* This function is called when the PCRE_AUTO_CALLOUT option is set, to insert
2121 callout points before each pattern item.
2123 Arguments:
2124 code current code pointer
2125 ptr current pattern pointer
2126 cd pointers to tables etc
2128 Returns: new code pointer
2129 */
2133 {
2139 }
2143 /*************************************************
2144 * Complete a callout item *
2145 *************************************************/
2147 /* A callout item contains the length of the next item in the pattern, which
2148 we can't fill in till after we have reached the relevant point. This is used
2149 for both automatic and manual callouts.
2151 Arguments:
2152 previous_callout points to previous callout item
2153 ptr current pattern pointer
2154 cd pointers to tables etc
2156 Returns: nothing
2157 */
2159 static void
2161 {
2164 }
2168 #ifdef SUPPORT_UCP
2169 /*************************************************
2170 * Get othercase range *
2171 *************************************************/
2173 /* This function is passed the start and end of a class range, in UTF-8 mode
2174 with UCP support. It searches up the characters, looking for internal ranges of
2175 characters in the "other" case. Each call returns the next one, updating the
2176 start address.
2178 Arguments:
2179 cptr points to starting character value; updated
2180 d end value
2181 ocptr where to put start of othercase range
2182 odptr where to put end of othercase range
2184 Yield: TRUE when range returned; FALSE when no more
2185 */
2187 static BOOL
2190 {
2202 {
2204 next++;
2205 }
2211 }
2216 /*************************************************
2217 * Check if auto-possessifying is possible *
2218 *************************************************/
2220 /* This function is called for unlimited repeats of certain items, to see
2221 whether the next thing could possibly match the repeated item. If not, it makes
2222 sense to automatically possessify the repeated item.
2224 Arguments:
2225 op_code the repeated op code
2226 this data for this item, depends on the opcode
2227 utf8 TRUE in UTF-8 mode
2228 utf8_char used for utf8 character bytes, NULL if not relevant
2229 ptr next character in pattern
2230 options options bits
2231 cd contains pointers to tables etc.
2233 Returns: TRUE if possessifying is wanted
2234 */
2236 static BOOL
2239 {
2242 /* Skip whitespace and comments in extended mode */
2245 {
2247 {
2248 while ( true ) //(*ptr < 256 && (cd->ctypes[*ptr] & ctype_space) != 0) || (*ptr >= 256 && isUnicodeWhiteSpace(*ptr)) )
2249 {
2251 {
2252 ptr++;
2254 }
2256 }
2258 {
2261 }
2263 }
2264 }
2266 /* If the next item is one that we can handle, get its value. A non-negative
2267 value is a character, a negative value is an escape value. */
2270 {
2275 }
2278 {
2279 #ifdef SUPPORT_UTF8
2281 #endif
2283 }
2287 /* Skip whitespace and comments in extended mode */
2290 {
2292 {
2293 while ( true ) //(*ptr < 256 && (cd->ctypes[*ptr] & ctype_space) != 0) || (*ptr >= 256 && isUnicodeWhiteSpace(*ptr)) )
2294 {
2296 {
2297 ptr++;
2299 }
2301 }
2303 {
2306 }
2308 }
2309 }
2311 /* If the next thing is itself optional, we have to give up. */
2316 /* Now compare the next item with the previous opcode. If the previous is a
2317 positive single character match, "item" either contains the character or, if
2318 "item" is greater than 127 in utf8 mode, the character's bytes are in
2319 utf8_char. */
2322 /* Handle cases when the next item is a character. */
2325 {
2327 #ifdef SUPPORT_UTF8
2329 #endif
2332 /* For CHARNC (caseless character) we must check the other case. If we have
2333 Unicode property support, we can use it to test the other case of
2334 high-valued characters. */
2337 #ifdef SUPPORT_UTF8
2339 #endif
2341 #ifdef SUPPORT_UTF8
2343 {
2346 #ifdef SUPPORT_UCP
2348 #else
2350 #endif
2352 }
2353 else
2357 /* For OP_NOT, "item" must be a single-byte character. */
2363 #ifdef SUPPORT_UTF8
2365 {
2368 #ifdef SUPPORT_UCP
2370 #else
2372 #endif
2374 }
2375 else
2400 {
2423 }
2428 {
2439 }
2443 }
2446 /* Handle the case when the next item is \d, \s, etc. */
2449 {
2452 #ifdef SUPPORT_UTF8
2454 #endif
2456 {
2478 {
2501 }
2506 {
2517 }
2521 }
2542 /* Can't have \S in here because VT matches \S (Perl anomaly) */
2557 }
2559 /* Control does not reach here */
2560 }
2564 /*************************************************
2565 * Compile one branch *
2566 *************************************************/
2568 /* Scan the pattern, compiling it into the a vector. If the options are
2569 changed during the branch, the pointer is used to change the external options
2570 bits. This function is used during the pre-compile phase when we are trying
2571 to find out the amount of memory needed, as well as during the real compile
2572 phase. The value of lengthptr distinguishes the two phases.
2574 Arguments:
2575 optionsptr pointer to the option bits
2576 codeptr points to the pointer to the current code point
2577 ptrptr points to the current pattern pointer
2578 errorcodeptr points to error code variable
2579 firstbyteptr set to initial literal character, or < 0 (REQ_UNSET, REQ_NONE)
2580 reqbyteptr set to the last literal character required, else < 0
2581 bcptr points to current branch chain
2582 cd contains pointers to tables etc.
2583 lengthptr NULL during the real compile phase
2584 points to length accumulator during pre-compile phase
2586 Returns: TRUE on success
2587 FALSE, with *errorcodeptr set non-zero on error
2588 */
2590 static BOOL
2594 {
2619 #ifdef SUPPORT_UTF8
2620 BOOL class_utf8;
2625 #else
2628 #endif
2630 #ifdef PCRE_DEBUG
2632 #endif
2634 /* Set up the default and non-default settings for greediness */
2639 /* Initialize no first byte, no required byte. REQ_UNSET means "no char
2640 matching encountered yet". It gets changed to REQ_NONE if we hit something that
2641 matches a non-fixed char first char; reqbyte just remains unset if we never
2642 find one.
2644 When we hit a repeat whose minimum is zero, we may have to adjust these values
2645 to take the zero repeat into account. This is implemented by setting them to
2646 zerofirstbyte and zeroreqbyte when such a repeat is encountered. The individual
2647 item types that can be repeated set these backoff variables appropriately. */
2651 /* The variable req_caseopt contains either the REQ_CASELESS value or zero,
2652 according to the current setting of the caseless flag. REQ_CASELESS is a bit
2653 value > 255. It is added into the firstbyte or reqbyte variables to record the
2654 case status of the value. This is used only for ASCII characters. */
2658 /* Switch on next character until the end of the branch */
2661 {
2662 BOOL negate_class;
2664 BOOL possessive_quantifier;
2665 BOOL is_quantifier;
2666 BOOL is_recurse;
2667 BOOL reset_bracount;
2680 /* Get next byte in the pattern */
2684 /* If we are in the pre-compile phase, accumulate the length used for the
2685 previous cycle of this loop. */
2688 {
2689 #ifdef PCRE_DEBUG
2691 #endif
2692 if (code > cd->start_workspace + (COMPILE_WORK_SIZE-10)) /* tierney: added -10, since actual overwriting corrupts the stack Check for overrun */
2693 {
2696 }
2698 /* There is at least one situation where code goes backwards: this is the
2699 case of a zero quantifier after a class (e.g. [ab]{0}). At compile time,
2700 the class is simply eliminated. However, it is created first, so we have to
2701 allow memory for it. Therefore, don't ever reduce the length at this point.
2702 */
2706 /* Paranoid check for integer overflow */
2709 {
2712 }
2717 /* If "previous" is set and it is not at the start of the work space, move
2718 it back to there, in order to avoid filling up the work space. Otherwise,
2719 if "previous" is NULL, reset the current code pointer to the start. */
2722 {
2724 {
2728 }
2729 }
2732 /* Remember where this code item starts so we can pick up the length
2733 next time round. */
2736 }
2738 /* In the real compile phase, just check the workspace used by the forward
2739 reference list. */
2741 else if (cd->hwm > cd->start_workspace + (COMPILE_WORK_SIZE-10)) // tierney: added -10, since actual overwriting corrupts the stack
2742 {
2745 }
2747 /* If in \Q...\E, check for the end; if not, we have a literal */
2750 {
2752 {
2754 ptr++;
2756 }
2757 else
2758 {
2760 {
2764 }
2766 {
2769 }
2771 }
2772 }
2774 /* Fill in length of a previous callout, except when the next thing is
2775 a quantifier. */
2782 {
2786 }
2788 /* In extended mode, skip white space and comments */
2791 {
2793 {
2796 }
2798 {
2800 }
2802 {
2804 {
2806 }
2809 /* Else fall through to handle end of string */
2811 }
2812 }
2814 /* No auto callout for quantifiers. */
2817 {
2820 }
2823 {
2824 /* ===================================================================*/
2833 {
2835 {
2838 }
2841 }
2845 /* ===================================================================*/
2846 /* Handle single-character metacharacters. In multiline mode, ^ disables
2847 the setting of any following char as a first character. */
2851 {
2853 }
2863 /* There can never be a first char if '.' is first, whatever happens about
2864 repeats. The value of reqbyte doesn't change either. */
2875 /* ===================================================================*/
2876 /* Character classes. If the included characters are all < 256, we build a
2877 32-byte bitmap of the permitted characters, except in the special case
2878 where there is only one such character. For negated classes, we build the
2879 map as usual, then invert it at the end. However, we use a different opcode
2880 so that data characters > 255 can be handled correctly.
2882 If the class contains characters outside the 0-255 range, a different
2883 opcode is compiled. It may optionally have a bit map for characters < 256,
2884 but those above are are explicitly listed afterwards. A flag byte tells
2885 whether the bitmap is present, and whether this is a negated class or not.
2886 */
2891 /* PCRE supports POSIX class stuff inside a class. Perl gives an error if
2892 they are encountered at the top level, so we'll do that too. */
2896 {
2899 }
2901 /* If the first character is '^', set the negation flag and skip it. Also,
2902 if the first few characters (either before or after ^) are \Q\E or \E we
2903 skip them too. This makes for compatibility with Perl. */
2907 {
2910 {
2914 }
2918 }
2920 /* Keep a count of chars with values < 256 so that we can optimize the case
2921 of just a single character (as long as it's < 256). However, For higher
2922 valued UTF-8 characters, we don't yet do any optimization. */
2927 /* Initialize the 32-char bit map to all zeros. We build the map in a
2928 temporary bit of memory, in case the class contains only 1 character (less
2929 than 256), because in that case the compiled code doesn't use the bit map.
2930 */
2934 #ifdef SUPPORT_UTF8
2938 #endif
2940 /* Process characters until ] is reached. By writing this as a "do" it
2941 means that an initial ] is taken as a data character. At the start of the
2942 loop, c contains the first byte of the character. */
2944 /* cn: Due to bug http://flashqa.macromedia.com/bugapp/detail.asp?ID=110290
2945 we need to handle [^] as matching any character (its not not a character...)
2946 The ^ is already stripped off, so we just need to catch a leading ']'
2947 */
2948 if (c == ']') // [] is still invalid, so we know we must have [^]. [^] means any character other than null
2949 {
2952 }
2954 {
2957 #ifdef SUPPORT_UTF8
2961 }
2963 /* In the pre-compile phase, accumulate the length of any UTF-8 extra
2964 data and reset the pointer, to ensure that large classes that cannot
2965 overwrite the work space. */
2968 {
2971 }
2973 #endif
2975 /* Inside \Q...\E everything is literal except \E */
2978 {
2980 {
2984 }
2986 }
2988 /* Handle POSIX class names. Perl allows a negation extension of the
2989 form [:^name:]. A square bracket that doesn't match the syntax is
2990 treated as a literal. We also recognize the POSIX constructions
2991 [.ch.] and [=ch=] ("collating elements") and fault them, as Perl
2992 5.6 and 5.8 do. */
2997 {
3004 {
3007 }
3011 {
3013 ptr++;
3014 }
3018 {
3021 }
3023 /* If matching is caseless, upper and lower are converted to
3024 alpha. This relies on the fact that the class table starts with
3025 alpha, lower, upper as the first 3 entries. */
3030 /* We build the bit map for the POSIX class in a chunk of local store
3031 because we may be adding and subtracting from it, and we don't want to
3032 subtract bits that may be in the main map already. At the end we or the
3033 result into the bit map that is being built. */
3037 /* Copy in the first table (always present) */
3042 /* If there is a second table, add or remove it as required. */
3048 {
3051 else
3053 }
3055 /* Not see if we need to remove any special characters. An option
3056 value of 1 removes vertical space and 2 removes underscore. */
3062 /* Add the POSIX table or its complement into the main table that is
3063 being built and we are done. */
3067 else
3073 }
3075 /* Backslash may introduce a single character, or it may introduce one
3076 of the specials, which just set a flag. The sequence \b is a special
3077 case. Inside a class (and only there) it is treated as backspace.
3078 Elsewhere it marks a word boundary. Other escapes have preset maps ready
3079 to 'or' into the one we are building. We assume they have more than one
3080 character in them, so set class_charcount bigger than one. */
3083 {
3091 {
3093 {
3095 }
3098 }
3102 {
3106 /* Save time by not doing this in the pre-compile phase. */
3109 {
3144 }
3146 /* In the pre-compile phase, just do the recognition. */
3151 /* We need to deal with \H, \h, \V, and \v in both phases because
3152 they use extra memory. */
3155 {
3159 #ifdef SUPPORT_UTF8
3161 {
3176 }
3177 #endif
3179 }
3182 {
3184 {
3187 {
3192 }
3194 }
3196 #ifdef SUPPORT_UTF8
3198 {
3221 }
3222 #endif
3224 }
3227 {
3233 #ifdef SUPPORT_UTF8
3235 {
3240 }
3241 #endif
3243 }
3246 {
3248 {
3251 {
3259 }
3261 }
3263 #ifdef SUPPORT_UTF8
3265 {
3273 }
3274 #endif
3276 }
3278 /* We need to deal with \P and \p in both phases. */
3280 #ifdef SUPPORT_UCP
3282 {
3283 BOOL negated;
3294 }
3295 #endif
3296 /* Unrecognized escapes are faulted if PCRE is running in its
3297 strict mode. By default, for compatibility with Perl, they are
3298 treated as literals. */
3301 {
3304 }
3308 }
3310 /* Fall through if we have a single character (c >= 0). This may be
3311 greater than 256 in UTF-8 mode. */
3315 /* A single character may be followed by '-' to form a range. However,
3316 Perl does not permit ']' to be the end of the range. A '-' character
3317 at the end is treated as a literal. Perl ignores orphaned \E sequences
3318 entirely. The code for handling \Q and \E is messy. */
3320 CHECK_RANGE:
3322 {
3325 }
3330 {
3335 /* If we hit \Q (not followed by \E) at this point, go into escaped
3336 mode. */
3339 {
3344 }
3347 {
3350 }
3352 #ifdef SUPPORT_UTF8
3356 }
3357 else
3358 #endif
3361 /* The second part of a range can be a single-character escape, but
3362 not any of the other escapes. Perl 5.6 treats a hyphen as a literal
3363 in such circumstances. */
3366 {
3370 /* \b is backslash; \X is literal X; \R is literal R; any other
3371 special means the '-' was literal */
3374 {
3378 {
3381 }
3382 }
3383 }
3385 /* Check that the two values are in the correct order. Optimize
3386 one-character ranges */
3389 {
3392 }
3396 /* In UTF-8 mode, if the upper limit is > 255, or > 127 for caseless
3397 matching, we have to use an XCLASS with extra data items. Caseless
3398 matching for characters > 127 is available only if UCP support is
3399 available. */
3401 #ifdef SUPPORT_UTF8
3403 {
3406 /* With UCP support, we can find the other case equivalents of
3407 the relevant characters. There may be several ranges. Optimize how
3408 they fit with the basic range. */
3410 #ifdef SUPPORT_UCP
3412 {
3417 {
3433 }
3436 {
3438 }
3439 else
3440 {
3443 }
3445 }
3446 }
3449 /* Now record the original range, possibly modified for UCP caseless
3450 overlapping ranges. */
3456 /* With UCP support, we are done. Without UCP support, there is no
3457 caseless matching for UTF-8 characters > 127; we can use the bit map
3458 for the smaller ones. */
3460 #ifdef SUPPORT_UCP
3462 #else
3465 /* Adjust upper limit and fall through to set up the map */
3470 }
3473 /* We use the bit map for all cases when not in UTF-8 mode; else
3474 ranges that lie entirely within 0-127 when there is UCP support; else
3475 for partial ranges without UCP support. */
3480 /* We can save a bit of time by skipping this in the pre-compile. */
3483 {
3486 {
3489 }
3490 }
3493 }
3495 /* Handle a lone single character - we can get here for a normal
3496 non-escape char, or after \ that introduces a single character or for an
3497 apparent range that isn't. */
3499 LONE_SINGLE_CHARACTER:
3501 /* Handle a character that cannot go in the bit map */
3503 #ifdef SUPPORT_UTF8
3505 {
3510 #ifdef SUPPORT_UCP
3512 {
3515 {
3518 }
3519 }
3522 }
3523 else
3526 /* Handle a single-byte character */
3527 {
3530 {
3533 }
3534 class_charcount++;
3536 }
3537 }
3539 /* Loop until ']' reached. This "while" is the end of the "do" above. */
3544 {
3547 }
3549 /* Remember whether \r or \n are in this class */
3552 {
3554 }
3555 else
3556 {
3558 }
3559 /* If class_charcount is 1, we saw precisely one character whose value is
3560 less than 256. As long as there were no characters >= 128 and there was no
3561 use of \p or \P, in other words, no use of any XCLASS features, we can
3562 optimize.
3564 In UTF-8 mode, we can optimize the negative case only if there were no
3565 characters >= 128 because OP_NOT and the related opcodes like OP_NOTSTAR
3566 operate on single-bytes only. This is an historical hangover. Maybe one day
3567 we can tidy these opcodes to handle multi-byte characters.
3569 The optimization throws away the bit map. We turn the item into a
3570 1-character OP_CHAR[NC] if it's positive, or OP_NOT if it's negative. Note
3571 that OP_NOT does not support multibyte characters. In the positive case, it
3572 can cause firstbyte to be set. Otherwise, there can be no first char if
3573 this item is first, whatever repeat count may follow. In the case of
3574 reqbyte, save the previous value for reinstating. */
3576 #ifdef SUPPORT_UTF8
3579 #else
3581 #endif
3582 {
3585 /* The OP_NOT opcode works on one-byte characters only. */
3588 {
3594 }
3596 /* For a single, positive character, get the value into mcbuffer, and
3597 then we can handle this with the normal one-character code. */
3599 #ifdef SUPPORT_UTF8
3602 else
3603 #endif
3604 {
3607 }
3611 /* The general case - not the one-char optimization. If this is the first
3612 thing in the branch, there can be no first char setting, whatever the
3613 repeat count. Any reqbyte setting must remain unchanged after any kind of
3614 repeat. */
3620 /* If there are characters with values > 255, we have to compile an
3621 extended class, with its own opcode. If there are no characters < 256,
3622 we can omit the bitmap in the actual compiled code. */
3624 #ifdef SUPPORT_UTF8
3626 {
3632 /* If the map is required, move up the extra data to make room for it;
3633 otherwise just move the code pointer to the end of the extra data. */
3636 {
3641 }
3644 /* Now fill in the complete length of the item */
3648 }
3649 #endif
3651 /* If there are no characters > 255, negate the 32-byte map if necessary,
3652 and copy it into the code vector. If this is the first thing in the branch,
3653 there can be no first char setting, whatever the repeat count. Any reqbyte
3654 setting must remain unchanged after any kind of repeat. */
3657 {
3661 }
3662 else
3663 {
3664 /* cn: code added here for proper UTF-8 handling of \S (not whitespace char) \D (not a digit char) and \W (not a word char) */
3665 // The class maps for \S \D \W are the inverted maps for \s \d and \w. The class maps only handle comparisions with
3666 // chars < 255, however, and we need successful matches for chars > 255 when comparing to \S \D and \W. The
3667 // interpreter code for OP_CLASS will fail the match for any character > 255, (which is correct for \s \d \w).
3668 // The interpreter code for OP_NCLASS will succeed for any character > 255 (which is correct of ^\s, ^\d, ^\w).
3669 // Since \S is equivalent to ^\s, we need to use OP_NCLASS for \S \D and \W (inverted_class == true in that case).
3670 // Another option would be to create an OP_XCLASS custom bitmap just to handle all chars > 255 for \S \D and \W.
3671 // though that would execute slower.
3673 // original code: *code++ = OP_CLASS;
3676 /* cn: end modified code */
3678 }
3683 /* ===================================================================*/
3684 /* Various kinds of repeat; '{' is not necessarily a quantifier, but this
3685 has been tested above. */
3707 REPEAT:
3709 {
3712 }
3715 {
3718 }
3720 /* Remember whether this is a variable length repeat */
3727 /* Save start of previous item, in case we have to move it up to make space
3728 for an inserted OP_ONCE for the additional '+' extension. */
3732 /* If the next character is '+', we have a possessive quantifier. This
3733 implies greediness, whatever the setting of the PCRE_UNGREEDY option.
3734 If the next character is '?' this is a minimizing repeat, by default,
3735 but if PCRE_UNGREEDY is set, it works the other way round. We change the
3736 repeat type to the non-default. */
3739 {
3742 ptr++;
3743 }
3745 {
3747 ptr++;
3748 }
3751 /* If previous was a character match, abolish the item and generate a
3752 repeat item instead. If a char item has a minumum of more than one, ensure
3753 that it is set in reqbyte - it might not be if a sequence such as x{3} is
3754 the first thing in a branch because the x will have gone into firstbyte
3755 instead. */
3758 {
3759 /* Deal with UTF-8 characters that take up more than one byte. It's
3760 easier to write this out separately than try to macrify it. Use c to
3761 hold the length of the character in bytes, plus 0x80 to flag that it's a
3762 length rather than a small character. */
3764 #ifdef SUPPORT_UTF8
3766 {
3772 }
3773 else
3774 #endif
3776 /* Handle the case of a single byte - either with no UTF8 support, or
3777 with UTF-8 disabled, or for a UTF-8 character < 128. */
3779 {
3782 }
3784 /* If the repetition is unlimited, it pays to see if the next thing on
3785 the line is something that cannot possibly match this character. If so,
3786 automatically possessifying this item gains some performance in the case
3787 where the match fails. */
3793 {
3796 }
3799 }
3801 /* If previous was a single negated character ([^a] or similar), we use
3802 one of the special opcodes, replacing it. The code is shared with single-
3803 character repeats by setting opt_type to add a suitable offset into
3804 repeat_type. We can also test for auto-possessification. OP_NOT is
3805 currently used only for single-byte chars. */
3808 {
3814 {
3817 }
3819 }
3821 /* If previous was a character type match (\d or similar), abolish it and
3822 create a suitable repeat item. The code is shared with single-character
3823 repeats by setting op_type to add a suitable offset into repeat_type. Note
3824 the the Unicode property types will be present only when SUPPORT_UCP is
3825 defined, but we don't wrap the little bits of code here because it just
3826 makes it horribly messy. */
3829 {
3838 {
3841 }
3843 OUTPUT_SINGLE_REPEAT:
3845 {
3848 }
3854 /* If the maximum is zero then the minimum must also be zero; Perl allows
3855 this case, so we do too - by simply omitting the item altogether. */
3859 /* All real repeats make it impossible to handle partial matching (maybe
3860 one day we will be able to remove this restriction). */
3864 /* Combine the op_type with the repeat_type */
3868 /* A minimum of zero is handled either as the special case * or ?, or as
3869 an UPTO, with the maximum given. */
3872 {
3875 else
3876 {
3879 }
3880 }
3882 /* A repeat minimum of 1 is optimized into some special cases. If the
3883 maximum is unlimited, we use OP_PLUS. Otherwise, the original item is
3884 left in place and, if the maximum is greater than 1, we use OP_UPTO with
3885 one less than the maximum. */
3888 {
3891 else
3892 {
3897 }
3898 }
3900 /* The case {n,n} is just an EXACT, while the general case {n,m} is
3901 handled as an EXACT followed by an UPTO. */
3903 else
3904 {
3908 /* If the maximum is unlimited, insert an OP_STAR. Before doing so,
3909 we have to insert the character for the previous code. For a repeated
3910 Unicode property match, there are two extra bytes that define the
3911 required property. In UTF-8 mode, long characters have their length in
3912 c, with the 0x80 bit as a flag. */
3915 {
3916 #ifdef SUPPORT_UTF8
3918 {
3921 }
3922 else
3923 #endif
3924 {
3927 {
3930 }
3931 }
3933 }
3935 /* Else insert an UPTO if the max is greater than the min, again
3936 preceded by the character, for the previously inserted code. If the
3937 UPTO is just for 1 instance, we can use QUERY instead. */
3940 {
3941 #ifdef SUPPORT_UTF8
3943 {
3946 }
3947 else
3948 #endif
3951 {
3954 }
3958 {
3960 }
3961 else
3962 {
3965 }
3966 }
3967 }
3969 /* The character or character type itself comes last in all cases. */
3971 #ifdef SUPPORT_UTF8
3973 {
3976 }
3977 else
3978 #endif
3981 /* For a repeated Unicode property match, there are two extra bytes that
3982 define the required property. */
3984 #ifdef SUPPORT_UCP
3986 {
3989 }
3990 #endif
3991 }
3993 /* If previous was a character class or a back reference, we put the repeat
3994 stuff after it, but just skip the item if the repeat was {0,0}. */
3998 #ifdef SUPPORT_UTF8
4000 #endif
4002 {
4004 {
4007 }
4009 /* All real repeats make it impossible to handle partial matching (maybe
4010 one day we will be able to remove this restriction). */
4020 else
4021 {
4026 }
4027 }
4029 /* If previous was a bracket group, we may have to replicate it in certain
4030 cases. */
4034 {
4040 /* Repeating a DEFINE group is pointless */
4043 {
4046 }
4048 /* If the maximum repeat count is unlimited, find the end of the bracket
4049 by scanning through from the start, and compute the offset back to it
4050 from the current code pointer. There may be an OP_OPT setting following
4051 the final KET, so we can't find the end just by going back from the code
4052 pointer. */
4055 {
4059 }
4061 /* The case of a zero minimum is special because of the need to stick
4062 OP_BRAZERO in front of it, and because the group appears once in the
4063 data, whereas in other cases it appears the minimum number of times. For
4064 this reason, it is simplest to treat this case separately, as otherwise
4065 the code gets far too messy. There are several special subcases when the
4066 minimum is zero. */
4069 {
4070 /* If the maximum is also zero, we just omit the group from the output
4071 altogether. */
4074 {
4077 }
4079 /* If the maximum is 1 or unlimited, we just have to stick in the
4080 BRAZERO and do no more at this point. However, we do need to adjust
4081 any OP_RECURSE calls inside the group that refer to the group itself or
4082 any internal or forward referenced group, because the offset is from
4083 the start of the whole regex. Temporarily terminate the pattern while
4084 doing this. */
4087 {
4091 code++;
4093 }
4095 /* If the maximum is greater than 1 and limited, we have to replicate
4096 in a nested fashion, sticking OP_BRAZERO before each set of brackets.
4097 The first one has to be handled carefully because it's the original
4098 copy, which has to be moved up. The remainder can be handled by code
4099 that is common with the non-zero minimum case below. We have to
4100 adjust the value or repeat_max, since one less copy is required. Once
4101 again, we may have to adjust any OP_RECURSE calls inside the group. */
4103 else
4104 {
4113 /* We chain together the bracket offset fields that have to be
4114 filled in later when the ends of the brackets are reached. */
4119 }
4121 repeat_max--;
4122 }
4124 /* If the minimum is greater than zero, replicate the group as many
4125 times as necessary, and adjust the maximum to the number of subsequent
4126 copies that we need. If we set a first char from the group, and didn't
4127 set a required char, copy the latter from the former. If there are any
4128 forward reference subroutine calls in the group, there will be entries on
4129 the workspace list; replicate these with an appropriate increment. */
4131 else
4132 {
4134 {
4135 /* In the pre-compile phase, we don't actually do the replication. We
4136 just adjust the length as if we had. Do some paranoid checks for
4137 potential integer overflow. */
4140 {
4145 {
4148 }
4150 }
4152 /* This is compiling for real */
4154 else
4155 {
4158 {
4163 {
4166 }
4169 }
4170 }
4171 }
4174 }
4176 /* This code is common to both the zero and non-zero minimum cases. If
4177 the maximum is limited, it replicates the group in a nested fashion,
4178 remembering the bracket starts on a stack. In the case of a zero minimum,
4179 the first one was set up above. In all cases the repeat_max now specifies
4180 the number of additional copies needed. Again, we must remember to
4181 replicate entries on the forward reference list. */
4184 {
4185 /* In the pre-compile phase, we don't actually do the replication. We
4186 just adjust the length as if we had. For each repetition we must add 1
4187 to the length for BRAZERO and for all but the last repetition we must
4188 add 2 + 2*LINKSIZE to allow for the nesting that occurs. Do some
4189 paranoid checks to avoid integer overflow. */
4192 {
4199 {
4202 }
4204 }
4206 /* This is compiling for real */
4209 {
4215 /* All but the final copy start a new nesting, maintaining the
4216 chain of brackets outstanding. */
4219 {
4225 }
4229 {
4232 }
4235 }
4237 /* Now chain through the pending brackets, and fill in their length
4238 fields (which are holding the chain links pro tem). */
4241 {
4250 }
4251 }
4253 /* If the maximum is unlimited, set a repeater in the final copy. We
4254 can't just offset backwards from the current code point, because we
4255 don't know if there's been an options resetting after the ket. The
4256 correct offset was computed above.
4258 Then, when we are doing the actual compile phase, check to see whether
4259 this group is a non-atomic one that could match an empty string. If so,
4260 convert the initial operator to the S form (e.g. OP_BRA -> OP_SBRA) so
4261 that runtime checking can be done. [This check is also applied to
4262 atomic groups at runtime, but in a different way.] */
4264 else
4265 {
4270 {
4272 do
4273 {
4275 {
4278 }
4280 }
4282 }
4283 }
4284 }
4286 /* Else there's some kind of shambles */
4288 else
4289 {
4292 }
4294 /* If the character following a repeat is '+', or if certain optimization
4295 tests above succeeded, possessive_quantifier is TRUE. For some of the
4296 simpler opcodes, there is an special alternative opcode for this. For
4297 anything else, we wrap the entire repeated item inside OP_ONCE brackets.
4298 The '+' notation is just syntactic sugar, taken from Sun's Java package,
4299 but the special opcodes can optimize it a bit. The repeated item starts at
4300 tempcode, not at previous, which might be the first part of a string whose
4301 (former) last char we repeated.
4303 Possessifying an 'exact' quantifier has no effect, so we can ignore it. But
4304 an 'upto' may follow. We skip over an 'exact' item, and then test the
4305 length of what remains before proceeding. */
4308 {
4315 {
4340 }
4341 }
4343 /* In all case we no longer have a previous item. We also set the
4344 "follows varying string" flag for subsequently encountered reqbytes if
4345 it isn't already set and we have just passed a varying length item. */
4347 END_REPEAT:
4353 /* ===================================================================*/
4354 /* Start of nested parenthesized sub-expression, or comment or lookahead or
4355 lookbehind or option setting or condition or all the other extended
4356 parenthesis forms. */
4365 /* First deal with various "verbs" that can be introduced by '*'. */
4368 {
4374 {
4377 }
4379 {
4382 }
4385 {
4388 {
4392 }
4393 }
4397 }
4399 /* Deal with the extended parentheses; all are introduced by '?', and the
4400 appearance of any of them means that this is not a capturing group. */
4403 {
4410 {
4412 ptr++;
4415 {
4418 }
4422 /* ------------------------------------------------------------ */
4425 /* Fall through */
4427 /* ------------------------------------------------------------ */
4430 ptr++;
4434 /* ------------------------------------------------------------ */
4438 /* A condition can be an assertion, a number (referring to a numbered
4439 group), a name (referring to a named group), or 'R', referring to
4440 recursion. R<digits> and R&name are also permitted for recursion tests.
4442 There are several syntaxes for testing a named group: (?(name)) is used
4443 by Python; Perl 5.10 onwards uses (?(<name>) or (?('name')).
4445 There are two unfortunate ambiguities, caused by history. (a) 'R' can
4446 be the recursive thing or the name 'R' (and similarly for 'R' followed
4447 by digits), and (b) a number could be a name that consists of digits.
4448 In both cases, we look for a name first; if not found, we try the other
4449 cases. */
4451 /* For conditions that are assertions, check the syntax, and then exit
4452 the switch. This will take control down to where bracketed groups,
4453 including assertions, are processed. */
4458 /* Most other conditions use OP_CREF (a couple change to OP_RREF
4459 below), and all need to skip 3 bytes at the start of the group. */
4465 /* Check for a test for recursion in a named group. */
4468 {
4472 }
4474 /* Check for a test for a named group's having been set, using the Perl
4475 syntax (?(<name>) or (?('name') */
4478 {
4480 ptr++;
4481 }
4483 {
4485 ptr++;
4486 }
4487 else
4488 {
4491 }
4493 /* We now expect to read a name; any thing else is an error */
4496 {
4500 }
4502 /* Read the name, but also get it as a number if it's all digits */
4507 {
4511 ptr++;
4512 }
4516 {
4520 }
4522 /* Do no further checking in the pre-compile phase. */
4526 /* In the real compile we do the work of looking for the actual
4527 reference. If the string started with "+" or "-" we require the rest to
4528 be digits, in which case recno will be set. */
4531 {
4533 {
4536 }
4538 {
4541 {
4544 }
4545 }
4549 }
4551 /* Otherwise (did not start with "+" or "-"), start by looking for the
4552 name. */
4556 {
4559 }
4561 /* Found a previous named subpattern */
4564 {
4567 }
4569 /* Search the pattern for a forward reference */
4573 {
4575 }
4577 /* If terminator == 0 it means that the name followed directly after
4578 the opening parenthesis [e.g. (?(abc)...] and in this case there are
4579 some further alternatives to try. For the cases where terminator != 0
4580 [things like (?(<name>... or (?('name')... or (?(R&name)... ] we have
4581 now checked all the possibilities, so give an error. */
4584 {
4587 }
4589 /* Check for (?(R) for recursion. Allow digits after R to specify a
4590 specific group number. */
4593 {
4596 {
4598 {
4601 }
4603 }
4607 }
4609 /* Similarly, check for the (?(DEFINE) "condition", which is always
4610 false. */
4613 {
4616 }
4618 /* Check for the "name" actually being a subpattern number. */
4621 {
4623 }
4625 /* Either an unidentified subpattern, or a reference to (?(0) */
4627 else
4628 {
4631 }
4635 /* ------------------------------------------------------------ */
4638 ptr++;
4642 /* ------------------------------------------------------------ */
4644 ptr++;
4646 {
4650 }
4655 /* ------------------------------------------------------------ */
4658 {
4674 }
4678 /* ------------------------------------------------------------ */
4681 ptr++;
4685 /* ------------------------------------------------------------ */
4690 {
4695 {
4698 }
4700 {
4703 }
4708 }
4713 /* ------------------------------------------------------------ */
4716 {
4720 }
4722 {
4725 }
4726 /* Fall through to handle (?P< as (?< is handled */
4729 /* ------------------------------------------------------------ */
4732 {
4739 /* In the pre-compile phase, just do a syntax check. */
4742 {
4744 {
4747 }
4749 {
4752 }
4754 {
4757 {
4760 }
4761 }
4762 }
4764 /* In the real compile, create the entry in the table */
4766 else
4767 {
4770 {
4773 {
4775 {
4777 {
4780 }
4781 }
4783 }
4785 {
4789 }
4791 }
4796 }
4797 }
4799 /* In both cases, count the number of names we've encountered. */
4806 /* ------------------------------------------------------------ */
4810 /* Fall through */
4812 /* We come here from the Python syntax above that handles both
4813 references (?P=name) and recursion (?P>name), as well as falling
4814 through from the Perl recursion syntax (?&name). */
4816 NAMED_REF_OR_RECURSE:
4821 /* In the pre-compile phase, do a syntax check and set a dummy
4822 reference number. */
4825 {
4827 {
4830 }
4832 {
4835 }
4837 }
4839 /* In the real compile, seek the name in the table */
4841 else
4842 {
4845 {
4848 }
4851 {
4853 }
4857 {
4860 }
4861 }
4863 /* In both phases, we can now go to the code than handles numerical
4864 recursion or backreferences. */
4870 /* ------------------------------------------------------------ */
4873 /* Fall through */
4876 /* ------------------------------------------------------------ */
4880 {
4885 {
4888 ptr++;
4889 }
4896 {
4899 }
4902 {
4904 {
4907 }
4910 {
4913 }
4914 }
4916 {
4918 {
4921 }
4923 }
4925 /* Come here from code above that handles a named recursion */
4927 HANDLE_RECURSION:
4932 /* When we are actually compiling, find the bracket that is being
4933 referenced. Temporarily end the regex in case it doesn't exist before
4934 this point. If we end up with a forward reference, first check that
4935 the bracket does occur later so we can give the error (and position)
4936 now. Then remember this forward reference in the workspace so it can
4937 be filled in at the end. */
4940 {
4944 /* Forward reference */
4947 {
4950 {
4953 }
4956 }
4958 /* If not a forward reference, and the subpattern is still open,
4959 this is a recursive call. We check to see if this is a left
4960 recursion that could loop for ever, and diagnose that case. */
4964 {
4967 }
4968 }
4970 /* Insert the recursion/subroutine item, automatically wrapped inside
4971 "once" brackets. Set up a "previous group" length so that a
4972 subsequent quantifier will work. */
4987 }
4989 /* Can't determine a first byte now */
4995 /* ------------------------------------------------------------ */
4997 OTHER_CHAR_AFTER_QUERY:
5002 {
5004 {
5022 }
5023 }
5025 /* Set up the changed option bits, but don't change anything yet. */
5029 /* If the options ended with ')' this is not the start of a nested
5030 group with option changes, so the options change at this level. If this
5031 item is right at the start of the pattern, the options can be
5032 abstracted and made external in the pre-compile phase, and ignored in
5033 the compile phase. This can be helpful when matching -- for instance in
5034 caseless checking of required bytes.
5036 If the code pointer is not (cd->start_code + 1 + LINK_SIZE), we are
5037 definitely *not* at the start of the pattern because something has been
5038 compiled. In the pre-compile phase, however, the code pointer can have
5039 that value after the start, because it gets reset as code is discarded
5040 during the pre-compile. However, this can happen only at top level - if
5041 we are within parentheses, the starting BRA will still be present. At
5042 any parenthesis level, the length value can be used to test if anything
5043 has been compiled at that level. Thus, a test for both these conditions
5044 is necessary to ensure we correctly detect the start of the pattern in
5045 both phases.
5047 If we are not at the pattern start, compile code to change the ims
5048 options if this setting actually changes any of them, and reset the
5049 greedy defaults and the case value for firstbyte and reqbyte. */
5052 {
5055 {
5057 }
5058 else
5059 {
5061 {
5064 }
5068 }
5070 /* Change options at this level, and pass them back for use
5071 in subsequent branches. When not at the start of the pattern, this
5072 information is also necessary so that a resetting item can be
5073 compiled at the end of a group (if we are in a group). */
5078 }
5080 /* If the options ended with ':' we are heading into a nested group
5081 with possible change of options. Such groups are non-capturing and are
5082 not assertions of any kind. All we need to do is skip over the ':';
5083 the newoptions value is handled below. */
5086 ptr++;
5090 /* Opening parenthesis not followed by '?'. If PCRE_NO_AUTO_CAPTURE is set,
5091 all unadorned brackets become non-capturing and behave like (?:...)
5092 brackets. */
5095 {
5097 }
5099 /* Else we have a capturing group. */
5101 else
5102 {
5103 NUMBERED_GROUP:
5107 }
5109 /* Process nested bracketed regex. Assertions may not be repeated, but
5110 other kinds can be. All their opcodes are >= OP_ONCE. We copy code into a
5111 non-register variable in order to be able to pass its address because some
5112 compilers complain otherwise. Pass in a new setting for the ims options if
5113 they have changed. */
5137 ))
5140 /* At the end of compiling, code is still pointing to the start of the
5141 group, while tempcode has been updated to point past the end of the group
5142 and any option resetting that may follow it. The pattern pointer (ptr)
5143 is on the bracket. */
5145 /* If this is a conditional bracket, check that there are no more than
5146 two branches in the group, or just one if it's a DEFINE group. We do this
5147 in the real compile phase, not in the pre-pass, where the whole group may
5148 not be available. */
5151 {
5156 condcount++;
5158 }
5161 /* A DEFINE group is never obeyed inline (the "condition" is always
5162 false). It must have only one branch. */
5165 {
5167 {
5170 }
5172 }
5174 /* A "normal" conditional group. If there is just one branch, we must not
5175 make use of its firstbyte or reqbyte, because this is equivalent to an
5176 empty second branch. */
5178 else
5179 {
5181 {
5184 }
5186 }
5187 }
5189 /* Error if hit end of pattern */
5192 {
5195 }
5197 /* In the pre-compile phase, update the length by the length of the group,
5198 less the brackets at either end. Then reduce the compiled code to just a
5199 set of non-capturing brackets so that it doesn't use much memory if it is
5200 duplicated by a quantifier.*/
5203 {
5205 {
5208 }
5215 }
5217 /* Otherwise update the main code pointer to the end of the group. */
5221 /* For a DEFINE group, required and first character settings are not
5222 relevant. */
5226 /* Handle updating of the required and first characters for other types of
5227 group. Update for normal brackets of all kinds, and conditions with two
5228 branches (see code above). If the bracket is followed by a quantifier with
5229 zero repeat, we have to back off. Hence the definition of zeroreqbyte and
5230 zerofirstbyte outside the main loop so that they can be accessed for the
5231 back off. */
5238 {
5239 /* If we have not yet set a firstbyte in this branch, take it from the
5240 subpattern, remembering that it was set here so that a repeat of more
5241 than one can replicate it as reqbyte if necessary. If the subpattern has
5242 no firstbyte, set "none" for the whole branch. In both cases, a zero
5243 repeat forces firstbyte to "none". */
5246 {
5248 {
5251 }
5254 }
5256 /* If firstbyte was previously set, convert the subpattern's firstbyte
5257 into reqbyte if there wasn't one, using the vary flag that was in
5258 existence beforehand. */
5263 /* If the subpattern set a required byte (or set a first byte that isn't
5264 really the first byte - see above), set it. */
5267 }
5269 /* For a forward assertion, we take the reqbyte, if set. This can be
5270 helpful if the pattern that follows the assertion doesn't set a different
5271 char. For example, it's useful for /(?=abcde).+/. We can't set firstbyte
5272 for an assertion, however because it leads to incorrect effect for patterns
5273 such as /(?=a)a.+/ when the "real" "a" would then become a reqbyte instead
5274 of a firstbyte. This is overcome by a scan at the end if there's no
5275 firstbyte, looking for an asserted first char. */
5281 /* ===================================================================*/
5282 /* Handle metasequences introduced by \. For ones like \d, the ESC_ values
5283 are arranged to be the negation of the corresponding OP_values. For the
5284 back references, the values are ESC_REF plus the reference number. Only
5285 back references and those types that consume a character may be repeated.
5286 We can test for values between ESC_b and ESC_Z for the latter; this may
5287 have to change if any new ones are ever created. */
5295 {
5297 {
5301 }
5305 /* For metasequences that actually match a character, we disable the
5306 setting of a first character if it hasn't already been set. */
5311 /* Set values to reset to if this is followed by a zero repeat. */
5316 /* \k<name> or \k'name' is a back reference by name (Perl syntax).
5317 We also support \k{name} (.NET syntax) */
5320 {
5324 }
5326 /* Back references are handled specially; must disable firstbyte if
5327 not set to cope with cases like (?=(\w+))\1: which would otherwise set
5328 ':' later. */
5331 {
5341 }
5343 /* So are Unicode property matches, if supported. */
5345 #ifdef SUPPORT_UCP
5347 {
5348 BOOL negated;
5356 }
5357 #else
5359 /* If Unicode properties are not supported, \X, \P, and \p are not
5360 allowed. */
5363 {
5366 }
5367 #endif
5369 /* For the rest (including \X when Unicode properties are supported), we
5370 can obtain the OP value by negating the escape value. */
5372 else
5373 {
5376 }
5378 }
5380 /* We have a data character whose value is in c. In UTF-8 mode it may have
5381 a value > 127. We set its representation in the length/buffer, and then
5382 handle it as a data character. */
5384 #ifdef SUPPORT_UTF8
5387 else
5388 #endif
5390 {
5393 }
5397 /* ===================================================================*/
5398 /* Handle a literal character. It is guaranteed not to be whitespace or #
5399 when the extended flag is set. If we are in UTF-8 mode, it may be a
5400 multi-byte literal character. */
5403 NORMAL_CHAR:
5407 #ifdef SUPPORT_UTF8
5409 {
5412 }
5413 #endif
5415 /* At this point we have the character's bytes in mcbuffer, and the length
5416 in mclength. When not in UTF-8 mode, the length is always 1. */
5418 ONE_CHAR:
5423 /* Remember if \r or \n were seen */
5428 /* Set the first and required bytes appropriately. If no previous first
5429 byte, set it from this character, but revert to none on a zero repeat.
5430 Otherwise, leave the firstbyte value alone, and don't change it on a zero
5431 repeat. */
5434 {
5438 /* If the character is more than one byte long, we can set firstbyte
5439 only if it is not to be matched caselessly. */
5442 {
5445 }
5447 }
5449 /* firstbyte was previously set; we can set reqbyte only the length is
5450 1 or the matching is caseful. */
5452 else
5453 {
5458 }
5461 }
5465 /* Control never reaches here by falling through, only by a goto for all the
5466 error states. Pass back the position in the pattern so that it can be displayed
5467 to the user for diagnosing the error. */
5469 FAILED:
5472 }
5477 /*************************************************
5478 * Compile sequence of alternatives *
5479 *************************************************/
5481 /* On entry, ptr is pointing past the bracket character, but on return it
5482 points to the closing bracket, or vertical bar, or end of string. The code
5483 variable is pointing at the byte into which the BRA operator has been stored.
5484 If the ims options are changed at the start (for a (?ims: group) or during any
5485 branch, we need to insert an OP_OPT item at the start of every following branch
5486 to ensure they get set correctly at run time, and also pass the new options
5487 into every subsequent branch compile.
5489 This function is used during the pre-compile phase when we are trying to find
5490 out the amount of memory needed, as well as during the real compile phase. The
5491 value of lengthptr distinguishes the two phases.
5493 Arguments:
5494 options option bits, including any changes for this subpattern
5495 oldims previous settings of ims option bits
5496 codeptr -> the address of the current code pointer
5497 ptrptr -> the address of the current pattern pointer
5498 errorcodeptr -> pointer to error code variable
5499 lookbehind TRUE if this is a lookbehind assertion
5500 reset_bracount TRUE to reset the count for each branch
5501 skipbytes skip this many bytes at start (for brackets and OP_COND)
5502 firstbyteptr place to put the first required character, or a negative number
5503 reqbyteptr place to put the last required character, or a negative number
5504 bcptr pointer to the chain of currently open branches
5505 cd points to the data block with tables pointers etc.
5506 lengthptr NULL during the real compile phase
5507 points to length accumulator during pre-compile phase
5509 Returns: TRUE on success
5510 */
5512 static BOOL
5517 {
5528 branch_chain bc;
5537 /* Accumulate the length for use in the pre-compile phase. Start with the
5538 length of the BRA and KET and any extra bytes that are required at the
5539 beginning. We accumulate in a local variable to save frequent testing of
5540 lenthptr for NULL. We cannot do this by looking at the value of code at the
5541 start and end of each alternative, because compiled items are discarded during
5542 the pre-compile phase so that the work space is not exceeded. */
5546 /* WARNING: If the above line is changed for any reason, you must also change
5547 the code that abstracts option settings at the start of the pattern and makes
5548 them global. It tests the value of length for (2 + 2*LINK_SIZE) in the
5549 pre-compile phase to find out whether anything has yet been compiled or not. */
5551 /* Offset is set zero to mark that this bracket is still open */
5556 /* Loop for each alternative branch */
5560 {
5561 /* For a (?| group, reset the capturing bracket count so that each branch
5562 uses the same numbers. */
5566 /* Handle a change of ims options at the start of the branch */
5569 {
5573 }
5575 /* Set up dummy OP_REVERSE if lookbehind assertion */
5578 {
5583 }
5585 /* Now compile the branch; in the pre-compile phase its length gets added
5586 into the length. */
5590 {
5593 }
5595 /* Keep the highest bracket count in case (?| was used and some branch
5596 has fewer than the rest. */
5600 /* In the real compile phase, there is some post-processing to be done. */
5603 {
5604 /* If this is the first branch, the firstbyte and reqbyte values for the
5605 branch become the values for the regex. */
5608 {
5611 }
5613 /* If this is not the first branch, the first char and reqbyte have to
5614 match the values from all the previous branches, except that if the
5615 previous value for reqbyte didn't have REQ_VARY set, it can still match,
5616 and we set REQ_VARY for the regex. */
5618 else
5619 {
5620 /* If we previously had a firstbyte, but it doesn't match the new branch,
5621 we have to abandon the firstbyte for the regex, but if there was
5622 previously no reqbyte, it takes on the value of the old firstbyte. */
5625 {
5628 }
5630 /* If we (now or from before) have no firstbyte, a firstbyte from the
5631 branch becomes a reqbyte if there isn't a branch reqbyte. */
5636 /* Now ensure that the reqbytes match */
5641 }
5643 /* If lookbehind, check that this branch matches a fixed-length string, and
5644 put the length into the OP_REVERSE item. Temporarily mark the end of the
5645 branch with OP_END. */
5648 {
5654 {
5658 }
5660 }
5661 }
5663 /* Reached end of expression, either ')' or end of pattern. In the real
5664 compile phase, go back through the alternative branches and reverse the chain
5665 of offsets, with the field in the BRA item now becoming an offset to the
5666 first alternative. If there are no alternatives, it points to the end of the
5667 group. The length in the terminating ket is always the length of the whole
5668 bracketed item. If any of the ims options were changed inside the group,
5669 compile a resetting op-code following, except at the very end of the pattern.
5670 Return leaving the pointer at the terminating char. */
5673 {
5675 {
5677 do
5678 {
5683 }
5685 }
5687 /* Fill in the ket */
5693 /* Resetting option if needed */
5696 {
5700 }
5702 /* Retain the highest bracket number, in case resetting was used. */
5706 /* Set values to pass back */
5713 {
5715 {
5718 }
5720 }
5722 }
5724 /* Another branch follows. In the pre-compile phase, we can move the code
5725 pointer back to where it was for the start of the first branch. (That is,
5726 pretend that each branch is the only one.)
5728 In the real compile phase, insert an ALT node. Its length field points back
5729 to the previous branch while the bracket remains open. At the end the chain
5730 is reversed. It's done like this so that the start of the bracket has a
5731 zero offset until it is closed, making it possible to detect recursion. */
5734 {
5737 }
5738 else
5739 {
5744 }
5746 ptr++;
5747 }
5748 /* Control never reaches here */
5749 }
5753 /************************************************************************
5754 * Stack implementation used in is_anchored and is_startline functions. *
5755 ************************************************************************/
5763 /*************************************************
5764 * Check for anchored expression *
5765 *************************************************/
5767 /* Try to find out if this is an anchored regular expression. Consider each
5768 alternative branch. If they all start with OP_SOD or OP_CIRC, or with a bracket
5769 all of whose alternatives start with OP_SOD or OP_CIRC (recurse ad lib), then
5770 it's anchored. However, if this is a multiline pattern, then only OP_SOD
5771 counts, since OP_CIRC can match in the middle.
5773 We can also consider a regex to be anchored if OP_SOM starts all its branches.
5774 This is the code for \G, which means "match at start of match position, taking
5775 into account the match offset".
5777 A branch is also implicitly anchored if it starts with .* and DOTALL is set,
5778 because that will try the rest of the pattern at all possible matching points,
5779 so there is no point trying again.... er ....
5781 .... except when the .* appears inside capturing parentheses, and there is a
5782 subsequent back reference to those parentheses. We haven't enough information
5783 to catch that case precisely.
5785 At first, the best we could do was to detect when .* was in capturing brackets
5786 and the highest back reference was greater than or equal to that level.
5787 However, by keeping a bitmap of the first 31 back references, we can catch some
5788 of the more common cases more precisely.
5790 Arguments:
5791 code points to start of expression (the bracket)
5792 options points to the options setting
5793 bracket_map a bitmap of which brackets we are inside while testing; this
5794 handles up to substring 31; after that we just have to take
5795 the less precise approach
5796 backref_map the back reference bitmap
5798 Returns: TRUE or FALSE
5799 */
5801 static BOOL
5802 is_anchored(register const uschar * const code, int * const options, const unsigned int bracket_map,
5804 {
5806 pi_ia_is work_item;
5808 /* set up the first work item */
5813 /* start the processing loop */
5815 {
5824 /* Non-capturing brackets */
5827 {
5828 pi_ia_is new_item;
5832 }
5834 /* Capturing brackets */
5837 {
5838 pi_ia_is new_item;
5844 }
5846 /* Other brackets */
5849 {
5850 pi_ia_is new_item;
5854 }
5856 /* .* is not anchored unless DOTALL is set and it isn't in brackets that
5857 are or may be referenced. */
5861 {
5863 {
5865 }
5866 }
5868 /* Check for explicit anchoring */
5872 {
5874 }
5881 }
5886 /*************************************************
5887 * Check for starting with ^ or .* *
5888 *************************************************/
5890 /* This is called to find out if every branch starts with ^ or .* so that
5891 "first char" processing can be done to speed things up in multiline
5892 matching and for non-DOTALL patterns that start with .* (which must start at
5893 the beginning or after \n). As in the case of is_anchored() (see above), we
5894 have to take account of back references to capturing brackets that contain .*
5895 because in that case we can't make the assumption.
5897 Arguments:
5898 code points to start of expression (the bracket)
5899 bracket_map a bitmap of which brackets we are inside while testing; this
5900 handles up to substring 31; after that we just have to take
5901 the less precise approach
5902 backref_map the back reference bitmap
5904 Returns: TRUE or FALSE
5905 */
5907 static BOOL
5910 {
5912 pi_ia_is work_item;
5914 /* set up the first work item */
5919 /* start the processing loop */
5921 {
5930 /* Non-capturing brackets */
5933 {
5934 pi_ia_is new_item;
5938 }
5940 /* Capturing brackets */
5943 {
5944 pi_ia_is new_item;
5950 }
5952 /* Other brackets */
5955 {
5956 pi_ia_is new_item;
5960 }
5962 /* .* means "start at start or after \n" if it isn't in brackets that
5963 may be referenced. */
5966 {
5968 {
5970 }
5971 }
5973 /* Check for explicit circumflex */
5976 {
5978 }
5980 /* Move on to the next alternative */
5987 }
5991 /*************************************************
5992 * Check for asserted fixed first char *
5993 *************************************************/
5995 /* During compilation, the "first char" settings from forward assertions are
5996 discarded, because they can cause conflicts with actual literals that follow.
5997 However, if we end up without a first char setting for an unanchored pattern,
5998 it is worth scanning the regex to see if there is an initial asserted first
5999 char. If all branches start with the same asserted char, or with a bracket all
6000 of whose alternatives start with the same asserted char (recurse ad lib), then
6001 we return that char, otherwise -1.
6003 Arguments:
6004 code points to start of expression (the bracket)
6005 options pointer to the options (used to check casing changes)
6006 inassert TRUE if in an assertion
6008 Returns: -1 or the fixed first char
6009 */
6015 static int
6017 {
6022 pi_ffac work_item;
6024 /* set up the first work item */
6028 /* start the processing loop */
6030 {
6040 {
6050 pi_ffac new_item;
6065 {
6067 }
6069 {
6072 }
6075 {
6077 }
6079 }
6083 }
6087 }
6090 /*************************************************
6091 * Compile a Regular Expression *
6092 *************************************************/
6094 /* This function takes a string and returns a pointer to a block of store
6095 holding a compiled version of the expression. The original API for this
6096 function had no error code return variable; it is retained for backwards
6097 compatibility. The new function is given a new name.
6099 Arguments:
6100 pattern the regular expression
6101 options various option bits
6102 errorcodeptr pointer to error code variable (pcre_compile2() only)
6103 can be NULL if you don't want a code value
6104 errorptr pointer to pointer to error text
6105 erroroffset ptr offset in pattern where error was detected
6106 tables pointer to character tables or NULL
6108 Returns: pointer to compiled data block, or NULL on error,
6109 with errorptr and erroroffset set
6110 */
6112 PCRE_EXP_DEFN pcre *
6115 {
6117 }
6120 PCRE_EXP_DEFN pcre *
6123 {
6129 #ifdef SUPPORT_UTF8
6130 BOOL utf8;
6131 #endif
6136 compile_data compile_block;
6139 /* This space is used for "compiling" into during the first phase, when we are
6140 computing the amount of memory that is needed. Compiled items are thrown away
6141 as soon as possible, so that a fairly large buffer should be sufficient for
6142 this purpose. The same space is used in the second phase for remembering where
6143 to fill in forward references to subpatterns. */
6148 /* Set this early so that early errors get offset 0. */
6152 /* We can't pass back an error message if errorptr is NULL; I guess the best we
6153 can do is just return NULL, but we can set a code value if there is a code
6154 pointer. */
6157 {
6160 }
6165 /* However, we can give a message for this error */
6168 {
6171 }
6175 /* Can't support UTF8 unless PCRE has been compiled to include the code. */
6177 #ifdef SUPPORT_UTF8
6181 {
6184 }
6185 #else
6187 {
6190 }
6191 #endif
6194 {
6197 }
6199 /* Set up pointers to the individual character tables */
6207 /* Check for newline settings at the start of the pattern, and remember the
6208 offset for later. */
6211 {
6225 }
6227 /* Handle different types of newline. The three bits give seven cases. The
6228 current code allows for fixed one- or two-byte sequences, plus "any" and
6229 "anycrlf". */
6232 {
6241 }
6244 {
6246 }
6248 {
6250 }
6251 else
6252 {
6255 {
6259 }
6260 else
6261 {
6264 }
6265 }
6267 /* Maximum back reference and backref bitmap. The bitmap records up to 31 back
6268 references to help in deciding whether (.*) can be treated as anchored or not.
6269 */
6274 /* Reflect pattern for debugging output */
6279 /* Pretend to compile the pattern while actually just accumulating the length
6280 of memory required. This behaviour is triggered by passing a non-NULL final
6281 argument to compile_regex(). We pass a block of workspace (cworkspace) for it
6282 to compile parts of the pattern into; the compiled code is discarded when it is
6283 no longer needed, so hopefully this workspace will never overflow, though there
6284 is a test for its doing so. */
6299 /* Now do the pre-compile. On error, errorcode will be set non-zero, so we
6300 don't need to look at the result of the function here. The initial options have
6301 been put into the cd block so that they can be changed if an option setting is
6302 found within the regex right at the beginning. Bringing initial option settings
6303 outside can help speed up starting point checks. */
6317 {
6320 }
6322 /* Compute the size of data block needed and get it, either from malloc or
6323 externally provided function. Integer overflow should no longer be possible
6324 because nowadays we limit the maximum value of cd->names_found and
6325 cd->name_entry_size. */
6331 {
6334 }
6336 /* Put in the magic number, and save the sizes, initial options, and character
6337 table pointer. NULL is used for the default character tables. The nullpad field
6338 is at the end; it's there to help in the case when a regex compiled on a system
6339 with 4-byte pointers is run on another with 8-byte pointers. */
6354 /* The starting points of the name/number translation table and of the code are
6355 passed around in the compile data block. The start/end pattern and initial
6356 options are already set from the pre-compile phase, as is the name_entry_size
6357 field. Reset the bracket count and the names_found field. Also reset the hwm
6358 field; this time it's used for remembering forward references to subpatterns.
6359 */
6371 /* Set up a starting, non-extracting bracket, then compile the expression. On
6372 error, errorcode will be set non-zero, so we don't need to look at the result
6373 of the function here. */
6386 /* If not reached end of pattern on success, there's an excess bracket. */
6390 /* Fill in the terminating state and check for disastrous overflow, but
6391 if debugging, leave the test till after things are printed out. */
6395 #ifndef PCRE_DEBUG
6397 #endif
6399 /* Fill in any forward references that are required. */
6402 {
6411 }
6413 /* Give an error if there's back reference to a non-existent capturing
6414 subpattern. */
6418 /* Failed to compile, or error while post-processing */
6421 {
6423 PCRE_EARLY_ERROR_RETURN:
6425 PCRE_EARLY_ERROR_RETURN2:
6429 }
6431 /* If the anchored option was not passed, set the flag if we can determine that
6432 the pattern is anchored by virtue of ^ characters or \A or anything else (such
6433 as starting with .* when DOTALL is set).
6435 Otherwise, if we know what the first byte has to be, save it, because that
6436 speeds up unanchored matches no end. If not, see if we can set the
6437 PCRE_STARTLINE flag. This is helpful for multiline matches when all branches
6438 start with ^. and also when all branches start with .* for non-DOTALL matches.
6439 */
6442 {
6446 else
6447 {
6451 {
6456 }
6459 }
6460 }
6462 /* For an anchored pattern, we use the "required byte" only if it follows a
6463 variable length item in the regex. Remove the caseless flag for non-caseable
6464 bytes. */
6468 {
6473 }
6475 /* Print out the compiled data if debugging is enabled. This is never the
6476 case when building a production library. */
6478 #ifdef PCRE_DEBUG
6486 {
6492 }
6495 {
6501 }
6505 /* This check is done here in the debugging case so that the code that
6506 was compiled can be seen. */
6509 {
6515 }
6519 }
6521 /* End of pcre_compile.c */