diff options
Diffstat (limited to 'Source/JavaScriptCore/pcre/pcre_compile.cpp')
| -rw-r--r-- | Source/JavaScriptCore/pcre/pcre_compile.cpp | 2708 |
1 files changed, 0 insertions, 2708 deletions
diff --git a/Source/JavaScriptCore/pcre/pcre_compile.cpp b/Source/JavaScriptCore/pcre/pcre_compile.cpp deleted file mode 100644 index 9d472d8..0000000 --- a/Source/JavaScriptCore/pcre/pcre_compile.cpp +++ /dev/null @@ -1,2708 +0,0 @@ -/* This is JavaScriptCore's variant of the PCRE library. While this library -started out as a copy of PCRE, many of the features of PCRE have been -removed. This library now supports only the regular expression features -required by the JavaScript language specification, and has only the functions -needed by JavaScriptCore and the rest of WebKit. - - Originally written by Philip Hazel - Copyright (c) 1997-2006 University of Cambridge - Copyright (C) 2002, 2004, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved. - Copyright (C) 2007 Eric Seidel <eric@webkit.org> - ------------------------------------------------------------------------------ -Redistribution and use in source and binary forms, with or without -modification, are permitted provided that the following conditions are met: - - * Redistributions of source code must retain the above copyright notice, - this list of conditions and the following disclaimer. - - * Redistributions in binary form must reproduce the above copyright - notice, this list of conditions and the following disclaimer in the - documentation and/or other materials provided with the distribution. - - * Neither the name of the University of Cambridge nor the names of its - contributors may be used to endorse or promote products derived from - this software without specific prior written permission. - -THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" -AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE -IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE -ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE -LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR -CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF -SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS -INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN -CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) -ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE -POSSIBILITY OF SUCH DAMAGE. ------------------------------------------------------------------------------ -*/ - -/* This module contains the external function jsRegExpExecute(), along with -supporting internal functions that are not used by other modules. */ - -#include "config.h" - -#include "pcre_internal.h" - -#include <string.h> -#include <wtf/ASCIICType.h> -#include <wtf/FastMalloc.h> -#include <wtf/FixedArray.h> -#include <wtf/StdLibExtras.h> - -using namespace WTF; - -/* Negative values for the firstchar and reqchar variables */ - -#define REQ_UNSET (-2) -#define REQ_NONE (-1) - -/************************************************* -* Code parameters and static tables * -*************************************************/ - -/* Maximum number of items on the nested bracket stacks at compile time. This -applies to the nesting of all kinds of parentheses. It does not limit -un-nested, non-capturing parentheses. This number can be made bigger if -necessary - it is used to dimension one int and one unsigned char vector at -compile time. */ - -#define BRASTACK_SIZE 200 - -/* Table for handling escaped characters in the range '0'-'z'. Positive returns -are simple data values; negative values are for special things like \d and so -on. Zero means further processing is needed (for things like \x), or the escape -is invalid. */ - -static const short escapes[] = { - 0, 0, 0, 0, 0, 0, 0, 0, /* 0 - 7 */ - 0, 0, ':', ';', '<', '=', '>', '?', /* 8 - ? */ - '@', 0, -ESC_B, 0, -ESC_D, 0, 0, 0, /* @ - G */ - 0, 0, 0, 0, 0, 0, 0, 0, /* H - O */ - 0, 0, 0, -ESC_S, 0, 0, 0, -ESC_W, /* P - W */ - 0, 0, 0, '[', '\\', ']', '^', '_', /* X - _ */ - '`', 7, -ESC_b, 0, -ESC_d, 0, '\f', 0, /* ` - g */ - 0, 0, 0, 0, 0, 0, '\n', 0, /* h - o */ - 0, 0, '\r', -ESC_s, '\t', 0, '\v', -ESC_w, /* p - w */ - 0, 0, 0 /* x - z */ -}; - -/* Error code numbers. They are given names so that they can more easily be -tracked. */ - -enum ErrorCode { - ERR0, ERR1, ERR2, ERR3, ERR4, ERR5, ERR6, ERR7, ERR8, ERR9, - ERR10, ERR11, ERR12, ERR13, ERR14, ERR15, ERR16, ERR17 -}; - -/* The texts of compile-time error messages. These are "char *" because they -are passed to the outside world. */ - -static const char* errorText(ErrorCode code) -{ - static const char errorTexts[] = - /* 1 */ - "\\ at end of pattern\0" - "\\c at end of pattern\0" - "character value in \\x{...} sequence is too large\0" - "numbers out of order in {} quantifier\0" - /* 5 */ - "number too big in {} quantifier\0" - "missing terminating ] for character class\0" - "internal error: code overflow\0" - "range out of order in character class\0" - "nothing to repeat\0" - /* 10 */ - "unmatched parentheses\0" - "internal error: unexpected repeat\0" - "unrecognized character after (?\0" - "failed to get memory\0" - "missing )\0" - /* 15 */ - "reference to non-existent subpattern\0" - "regular expression too large\0" - "parentheses nested too deeply" - ; - - int i = code; - const char* text = errorTexts; - while (i > 1) - i -= !*text++; - return text; -} - -/* Structure for passing "static" information around between the functions -doing the compiling. */ - -struct CompileData { - CompileData() { - topBackref = 0; - backrefMap = 0; - reqVaryOpt = 0; - needOuterBracket = false; - numCapturingBrackets = 0; - } - int topBackref; /* Maximum back reference */ - unsigned backrefMap; /* Bitmap of low back refs */ - int reqVaryOpt; /* "After variable item" flag for reqByte */ - bool needOuterBracket; - int numCapturingBrackets; -}; - -/* Definitions to allow mutual recursion */ - -static bool compileBracket(int, int*, unsigned char**, const UChar**, const UChar*, ErrorCode*, int, int*, int*, CompileData&); -static bool bracketIsAnchored(const unsigned char* code); -static bool bracketNeedsLineStart(const unsigned char* code, unsigned captureMap, unsigned backrefMap); -static int bracketFindFirstAssertedCharacter(const unsigned char* code, bool inassert); - -/************************************************* -* Handle escapes * -*************************************************/ - -/* This function is called when a \ has been encountered. It either returns a -positive value for a simple escape such as \n, or a negative value which -encodes one of the more complicated things such as \d. When UTF-8 is enabled, -a positive value greater than 255 may be returned. On entry, ptr is pointing at -the \. On exit, it is on the final character of the escape sequence. - -Arguments: - ptrPtr points to the pattern position pointer - errorCodePtr points to the errorcode variable - bracount number of previous extracting brackets - options the options bits - isClass true if inside a character class - -Returns: zero or positive => a data character - negative => a special escape sequence - on error, errorPtr is set -*/ - -static int checkEscape(const UChar** ptrPtr, const UChar* patternEnd, ErrorCode* errorCodePtr, int bracount, bool isClass) -{ - const UChar* ptr = *ptrPtr + 1; - - /* If backslash is at the end of the pattern, it's an error. */ - if (ptr == patternEnd) { - *errorCodePtr = ERR1; - *ptrPtr = ptr; - return 0; - } - - int c = *ptr; - - /* Non-alphamerics are literals. For digits or letters, do an initial lookup in - a table. A non-zero result is something that can be returned immediately. - Otherwise further processing may be required. */ - - if (c < '0' || c > 'z') { /* Not alphameric */ - } else if (int escapeValue = escapes[c - '0']) { - c = escapeValue; - if (isClass) { - if (-c == ESC_b) - c = '\b'; /* \b is backslash in a class */ - else if (-c == ESC_B) - c = 'B'; /* and \B is a capital B in a class (in browsers event though ECMAScript 15.10.2.19 says it raises an error) */ - } - /* Escapes that need further processing, or are illegal. */ - - } else { - switch (c) { - case '1': - case '2': - case '3': - case '4': - case '5': - case '6': - case '7': - case '8': - case '9': - /* Escape sequences starting with a non-zero digit are backreferences, - unless there are insufficient brackets, in which case they are octal - escape sequences. Those sequences end on the first non-octal character - or when we overflow 0-255, whichever comes first. */ - - if (!isClass) { - const UChar* oldptr = ptr; - c -= '0'; - while ((ptr + 1 < patternEnd) && isASCIIDigit(ptr[1]) && c <= bracount) - c = c * 10 + *(++ptr) - '0'; - if (c <= bracount) { - c = -(ESC_REF + c); - break; - } - ptr = oldptr; /* Put the pointer back and fall through */ - } - - /* Handle an octal number following \. If the first digit is 8 or 9, - this is not octal. */ - - if ((c = *ptr) >= '8') { - c = '\\'; - ptr -= 1; - break; - } - - /* \0 always starts an octal number, but we may drop through to here with a - larger first octal digit. */ - - case '0': { - c -= '0'; - int i; - for (i = 1; i <= 2; ++i) { - if (ptr + i >= patternEnd || ptr[i] < '0' || ptr[i] > '7') - break; - int cc = c * 8 + ptr[i] - '0'; - if (cc > 255) - break; - c = cc; - } - ptr += i - 1; - break; - } - - case 'x': { - c = 0; - int i; - for (i = 1; i <= 2; ++i) { - if (ptr + i >= patternEnd || !isASCIIHexDigit(ptr[i])) { - c = 'x'; - i = 1; - break; - } - int cc = ptr[i]; - if (cc >= 'a') - cc -= 32; /* Convert to upper case */ - c = c * 16 + cc - ((cc < 'A') ? '0' : ('A' - 10)); - } - ptr += i - 1; - break; - } - - case 'u': { - c = 0; - int i; - for (i = 1; i <= 4; ++i) { - if (ptr + i >= patternEnd || !isASCIIHexDigit(ptr[i])) { - c = 'u'; - i = 1; - break; - } - int cc = ptr[i]; - if (cc >= 'a') - cc -= 32; /* Convert to upper case */ - c = c * 16 + cc - ((cc < 'A') ? '0' : ('A' - 10)); - } - ptr += i - 1; - break; - } - - case 'c': - if (++ptr == patternEnd) { - *errorCodePtr = ERR2; - return 0; - } - - c = *ptr; - - /* To match Firefox, inside a character class, we also accept - numbers and '_' as control characters */ - if ((!isClass && !isASCIIAlpha(c)) || (!isASCIIAlphanumeric(c) && c != '_')) { - c = '\\'; - ptr -= 2; - break; - } - - /* A letter is upper-cased; then the 0x40 bit is flipped. This coding - is ASCII-specific, but then the whole concept of \cx is ASCII-specific. */ - c = toASCIIUpper(c) ^ 0x40; - break; - } - } - - *ptrPtr = ptr; - return c; -} - -/************************************************* -* Check for counted repeat * -*************************************************/ - -/* This function is called when a '{' is encountered in a place where it might -start a quantifier. It looks ahead to see if it really is a quantifier or not. -It is only a quantifier if it is one of the forms {ddd} {ddd,} or {ddd,ddd} -where the ddds are digits. - -Arguments: - p pointer to the first char after '{' - -Returns: true or false -*/ - -static bool isCountedRepeat(const UChar* p, const UChar* patternEnd) -{ - if (p >= patternEnd || !isASCIIDigit(*p)) - return false; - p++; - while (p < patternEnd && isASCIIDigit(*p)) - p++; - if (p < patternEnd && *p == '}') - return true; - - if (p >= patternEnd || *p++ != ',') - return false; - if (p < patternEnd && *p == '}') - return true; - - if (p >= patternEnd || !isASCIIDigit(*p)) - return false; - p++; - while (p < patternEnd && isASCIIDigit(*p)) - p++; - - return (p < patternEnd && *p == '}'); -} - -/************************************************* -* Read repeat counts * -*************************************************/ - -/* Read an item of the form {n,m} and return the values. This is called only -after isCountedRepeat() has confirmed that a repeat-count quantifier exists, -so the syntax is guaranteed to be correct, but we need to check the values. - -Arguments: - p pointer to first char after '{' - minp pointer to int for min - maxp pointer to int for max - returned as -1 if no max - errorCodePtr points to error code variable - -Returns: pointer to '}' on success; - current ptr on error, with errorCodePtr set non-zero -*/ - -static const UChar* readRepeatCounts(const UChar* p, int* minp, int* maxp, ErrorCode* errorCodePtr) -{ - int min = 0; - int max = -1; - - /* Read the minimum value and do a paranoid check: a negative value indicates - an integer overflow. */ - - while (isASCIIDigit(*p)) - min = min * 10 + *p++ - '0'; - if (min < 0 || min > 65535) { - *errorCodePtr = ERR5; - return p; - } - - /* Read the maximum value if there is one, and again do a paranoid on its size. - Also, max must not be less than min. */ - - if (*p == '}') - max = min; - else { - if (*(++p) != '}') { - max = 0; - while (isASCIIDigit(*p)) - max = max * 10 + *p++ - '0'; - if (max < 0 || max > 65535) { - *errorCodePtr = ERR5; - return p; - } - if (max < min) { - *errorCodePtr = ERR4; - return p; - } - } - } - - /* Fill in the required variables, and pass back the pointer to the terminating - '}'. */ - - *minp = min; - *maxp = max; - return p; -} - -/************************************************* -* Find first significant op code * -*************************************************/ - -/* This is called by several functions that scan a compiled expression looking -for a fixed first character, or an anchoring op code etc. It skips over things -that do not influence this. - -Arguments: - code pointer to the start of the group -Returns: pointer to the first significant opcode -*/ - -static const unsigned char* firstSignificantOpcode(const unsigned char* code) -{ - while (*code == OP_BRANUMBER) - code += 3; - return code; -} - -static const unsigned char* firstSignificantOpcodeSkippingAssertions(const unsigned char* code) -{ - while (true) { - switch (*code) { - case OP_ASSERT_NOT: - advanceToEndOfBracket(code); - code += 1 + LINK_SIZE; - break; - case OP_WORD_BOUNDARY: - case OP_NOT_WORD_BOUNDARY: - ++code; - break; - case OP_BRANUMBER: - code += 3; - break; - default: - return code; - } - } -} - -/************************************************* -* Get othercase range * -*************************************************/ - -/* This function is passed the start and end of a class range, in UTF-8 mode -with UCP support. It searches up the characters, looking for internal ranges of -characters in the "other" case. Each call returns the next one, updating the -start address. - -Arguments: - cptr points to starting character value; updated - d end value - ocptr where to put start of othercase range - odptr where to put end of othercase range - -Yield: true when range returned; false when no more -*/ - -static bool getOthercaseRange(int* cptr, int d, int* ocptr, int* odptr) -{ - int c, othercase = 0; - - for (c = *cptr; c <= d; c++) { - if ((othercase = jsc_pcre_ucp_othercase(c)) >= 0) - break; - } - - if (c > d) - return false; - - *ocptr = othercase; - int next = othercase + 1; - - for (++c; c <= d; c++) { - if (jsc_pcre_ucp_othercase(c) != next) - break; - next++; - } - - *odptr = next - 1; - *cptr = c; - - return true; -} - -/************************************************* - * Convert character value to UTF-8 * - *************************************************/ - -/* This function takes an integer value in the range 0 - 0x7fffffff - and encodes it as a UTF-8 character in 0 to 6 bytes. - - Arguments: - cvalue the character value - buffer pointer to buffer for result - at least 6 bytes long - - Returns: number of characters placed in the buffer - */ - -static int encodeUTF8(int cvalue, unsigned char *buffer) -{ - int i; - for (i = 0; i < jsc_pcre_utf8_table1_size; i++) - if (cvalue <= jsc_pcre_utf8_table1[i]) - break; - buffer += i; - for (int j = i; j > 0; j--) { - *buffer-- = 0x80 | (cvalue & 0x3f); - cvalue >>= 6; - } - *buffer = jsc_pcre_utf8_table2[i] | cvalue; - return i + 1; -} - -/************************************************* -* Compile one branch * -*************************************************/ - -/* Scan the pattern, compiling it into the code vector. - -Arguments: - options the option bits - brackets points to number of extracting brackets used - codePtr points to the pointer to the current code point - ptrPtr points to the current pattern pointer - errorCodePtr points to error code variable - firstbyteptr set to initial literal character, or < 0 (REQ_UNSET, REQ_NONE) - reqbyteptr set to the last literal character required, else < 0 - cd contains pointers to tables etc. - -Returns: true on success - false, with *errorCodePtr set non-zero on error -*/ - -static inline bool safelyCheckNextChar(const UChar* ptr, const UChar* patternEnd, UChar expected) -{ - return ((ptr + 1 < patternEnd) && ptr[1] == expected); -} - -static bool -compileBranch(int options, int* brackets, unsigned char** codePtr, - const UChar** ptrPtr, const UChar* patternEnd, ErrorCode* errorCodePtr, int *firstbyteptr, - int* reqbyteptr, CompileData& cd) -{ - int repeatType, opType; - int repeatMin = 0, repeat_max = 0; /* To please picky compilers */ - int bravalue = 0; - int reqvary, tempreqvary; - int c; - unsigned char* code = *codePtr; - unsigned char* tempcode; - bool didGroupSetFirstByte = false; - const UChar* ptr = *ptrPtr; - const UChar* tempptr; - unsigned char* previous = NULL; - unsigned char classbits[32]; - - bool class_utf8; - unsigned char* class_utf8data; - unsigned char utf8_char[6]; - - /* Initialize no first byte, no required byte. REQ_UNSET means "no char - matching encountered yet". It gets changed to REQ_NONE if we hit something that - matches a non-fixed char first char; reqByte just remains unset if we never - find one. - - When we hit a repeat whose minimum is zero, we may have to adjust these values - to take the zero repeat into account. This is implemented by setting them to - zeroFirstByte and zeroReqByte when such a repeat is encountered. The individual - item types that can be repeated set these backoff variables appropriately. */ - - int firstByte = REQ_UNSET; - int reqByte = REQ_UNSET; - int zeroReqByte = REQ_UNSET; - int zeroFirstByte = REQ_UNSET; - - /* The variable reqCaseOpt contains either the REQ_IGNORE_CASE value or zero, - according to the current setting of the ignores-case flag. REQ_IGNORE_CASE is a bit - value > 255. It is added into the firstByte or reqByte variables to record the - case status of the value. This is used only for ASCII characters. */ - - int reqCaseOpt = (options & IgnoreCaseOption) ? REQ_IGNORE_CASE : 0; - - /* Switch on next character until the end of the branch */ - - for (;; ptr++) { - bool negateClass; - bool shouldFlipNegation; /* If a negative special such as \S is used, we should negate the whole class to properly support Unicode. */ - int classCharCount; - int classLastChar; - int skipBytes; - int subReqByte; - int subFirstByte; - int mcLength; - unsigned char mcbuffer[8]; - - /* Next byte in the pattern */ - - c = ptr < patternEnd ? *ptr : 0; - - /* Fill in length of a previous callout, except when the next thing is - a quantifier. */ - - bool isQuantifier = c == '*' || c == '+' || c == '?' || (c == '{' && isCountedRepeat(ptr + 1, patternEnd)); - - switch (c) { - /* The branch terminates at end of string, |, or ). */ - - case 0: - if (ptr < patternEnd) - goto NORMAL_CHAR; - // End of string; fall through - case '|': - case ')': - *firstbyteptr = firstByte; - *reqbyteptr = reqByte; - *codePtr = code; - *ptrPtr = ptr; - return true; - - /* Handle single-character metacharacters. In multiline mode, ^ disables - the setting of any following char as a first character. */ - - case '^': - if (options & MatchAcrossMultipleLinesOption) { - if (firstByte == REQ_UNSET) - firstByte = REQ_NONE; - *code++ = OP_BOL; - } else - *code++ = OP_CIRC; - previous = NULL; - break; - - case '$': - previous = NULL; - if (options & MatchAcrossMultipleLinesOption) - *code++ = OP_EOL; - else - *code++ = OP_DOLL; - break; - - /* There can never be a first char if '.' is first, whatever happens about - repeats. The value of reqByte doesn't change either. */ - - case '.': - if (firstByte == REQ_UNSET) - firstByte = REQ_NONE; - zeroFirstByte = firstByte; - zeroReqByte = reqByte; - previous = code; - *code++ = OP_NOT_NEWLINE; - break; - - /* Character classes. If the included characters are all < 256, we build a - 32-byte bitmap of the permitted characters, except in the special case - where there is only one such character. For negated classes, we build the - map as usual, then invert it at the end. However, we use a different opcode - so that data characters > 255 can be handled correctly. - - If the class contains characters outside the 0-255 range, a different - opcode is compiled. It may optionally have a bit map for characters < 256, - but those above are are explicitly listed afterwards. A flag byte tells - whether the bitmap is present, and whether this is a negated class or not. - */ - - case '[': { - previous = code; - shouldFlipNegation = false; - - /* PCRE supports POSIX class stuff inside a class. Perl gives an error if - they are encountered at the top level, so we'll do that too. */ - - /* If the first character is '^', set the negation flag and skip it. */ - - if (ptr + 1 >= patternEnd) { - *errorCodePtr = ERR6; - return false; - } - - if (ptr[1] == '^') { - negateClass = true; - ++ptr; - } else - negateClass = false; - - /* Keep a count of chars with values < 256 so that we can optimize the case - of just a single character (as long as it's < 256). For higher valued UTF-8 - characters, we don't yet do any optimization. */ - - classCharCount = 0; - classLastChar = -1; - - class_utf8 = false; /* No chars >= 256 */ - class_utf8data = code + LINK_SIZE + 34; /* For UTF-8 items */ - - /* Initialize the 32-char bit map to all zeros. We have to build the - map in a temporary bit of store, in case the class contains only 1 - character (< 256), because in that case the compiled code doesn't use the - bit map. */ - - memset(classbits, 0, 32 * sizeof(unsigned char)); - - /* Process characters until ] is reached. The first pass - through the regex checked the overall syntax, so we don't need to be very - strict here. At the start of the loop, c contains the first byte of the - character. */ - - while ((++ptr < patternEnd) && (c = *ptr) != ']') { - /* Backslash may introduce a single character, or it may introduce one - of the specials, which just set a flag. Escaped items are checked for - validity in the pre-compiling pass. The sequence \b is a special case. - Inside a class (and only there) it is treated as backspace. Elsewhere - it marks a word boundary. Other escapes have preset maps ready to - or into the one we are building. We assume they have more than one - character in them, so set classCharCount bigger than one. */ - - if (c == '\\') { - c = checkEscape(&ptr, patternEnd, errorCodePtr, cd.numCapturingBrackets, true); - if (c < 0) { - classCharCount += 2; /* Greater than 1 is what matters */ - switch (-c) { - case ESC_d: - for (c = 0; c < 32; c++) - classbits[c] |= classBitmapForChar(c + cbit_digit); - continue; - - case ESC_D: - shouldFlipNegation = true; - for (c = 0; c < 32; c++) - classbits[c] |= ~classBitmapForChar(c + cbit_digit); - continue; - - case ESC_w: - for (c = 0; c < 32; c++) - classbits[c] |= classBitmapForChar(c + cbit_word); - continue; - - case ESC_W: - shouldFlipNegation = true; - for (c = 0; c < 32; c++) - classbits[c] |= ~classBitmapForChar(c + cbit_word); - continue; - - case ESC_s: - for (c = 0; c < 32; c++) - classbits[c] |= classBitmapForChar(c + cbit_space); - continue; - - case ESC_S: - shouldFlipNegation = true; - for (c = 0; c < 32; c++) - classbits[c] |= ~classBitmapForChar(c + cbit_space); - continue; - - /* Unrecognized escapes are faulted if PCRE is running in its - strict mode. By default, for compatibility with Perl, they are - treated as literals. */ - - default: - c = *ptr; /* The final character */ - classCharCount -= 2; /* Undo the default count from above */ - } - } - - /* Fall through if we have a single character (c >= 0). This may be - > 256 in UTF-8 mode. */ - - } /* End of backslash handling */ - - /* A single character may be followed by '-' to form a range. However, - Perl does not permit ']' to be the end of the range. A '-' character - here is treated as a literal. */ - - if ((ptr + 2 < patternEnd) && ptr[1] == '-' && ptr[2] != ']') { - ptr += 2; - - int d = *ptr; - - /* The second part of a range can be a single-character escape, but - not any of the other escapes. Perl 5.6 treats a hyphen as a literal - in such circumstances. */ - - if (d == '\\') { - const UChar* oldptr = ptr; - d = checkEscape(&ptr, patternEnd, errorCodePtr, cd.numCapturingBrackets, true); - - /* \X is literal X; any other special means the '-' was literal */ - if (d < 0) { - ptr = oldptr - 2; - goto LONE_SINGLE_CHARACTER; /* A few lines below */ - } - } - - /* The check that the two values are in the correct order happens in - the pre-pass. Optimize one-character ranges */ - - if (d == c) - goto LONE_SINGLE_CHARACTER; /* A few lines below */ - - /* In UTF-8 mode, if the upper limit is > 255, or > 127 for caseless - matching, we have to use an XCLASS with extra data items. Caseless - matching for characters > 127 is available only if UCP support is - available. */ - - if ((d > 255 || ((options & IgnoreCaseOption) && d > 127))) { - class_utf8 = true; - - /* With UCP support, we can find the other case equivalents of - the relevant characters. There may be several ranges. Optimize how - they fit with the basic range. */ - - if (options & IgnoreCaseOption) { - int occ, ocd; - int cc = c; - int origd = d; - while (getOthercaseRange(&cc, origd, &occ, &ocd)) { - if (occ >= c && ocd <= d) - continue; /* Skip embedded ranges */ - - if (occ < c && ocd >= c - 1) /* Extend the basic range */ - { /* if there is overlap, */ - c = occ; /* noting that if occ < c */ - continue; /* we can't have ocd > d */ - } /* because a subrange is */ - if (ocd > d && occ <= d + 1) /* always shorter than */ - { /* the basic range. */ - d = ocd; - continue; - } - - if (occ == ocd) - *class_utf8data++ = XCL_SINGLE; - else { - *class_utf8data++ = XCL_RANGE; - class_utf8data += encodeUTF8(occ, class_utf8data); - } - class_utf8data += encodeUTF8(ocd, class_utf8data); - } - } - - /* Now record the original range, possibly modified for UCP caseless - overlapping ranges. */ - - *class_utf8data++ = XCL_RANGE; - class_utf8data += encodeUTF8(c, class_utf8data); - class_utf8data += encodeUTF8(d, class_utf8data); - - /* With UCP support, we are done. Without UCP support, there is no - caseless matching for UTF-8 characters > 127; we can use the bit map - for the smaller ones. */ - - continue; /* With next character in the class */ - } - - /* We use the bit map for all cases when not in UTF-8 mode; else - ranges that lie entirely within 0-127 when there is UCP support; else - for partial ranges without UCP support. */ - - for (; c <= d; c++) { - classbits[c/8] |= (1 << (c&7)); - if (options & IgnoreCaseOption) { - int uc = flipCase(c); - classbits[uc/8] |= (1 << (uc&7)); - } - classCharCount++; /* in case a one-char range */ - classLastChar = c; - } - - continue; /* Go get the next char in the class */ - } - - /* Handle a lone single character - we can get here for a normal - non-escape char, or after \ that introduces a single character or for an - apparent range that isn't. */ - - LONE_SINGLE_CHARACTER: - - /* Handle a character that cannot go in the bit map */ - - if ((c > 255 || ((options & IgnoreCaseOption) && c > 127))) { - class_utf8 = true; - *class_utf8data++ = XCL_SINGLE; - class_utf8data += encodeUTF8(c, class_utf8data); - - if (options & IgnoreCaseOption) { - int othercase; - if ((othercase = jsc_pcre_ucp_othercase(c)) >= 0) { - *class_utf8data++ = XCL_SINGLE; - class_utf8data += encodeUTF8(othercase, class_utf8data); - } - } - } else { - /* Handle a single-byte character */ - classbits[c/8] |= (1 << (c&7)); - if (options & IgnoreCaseOption) { - c = flipCase(c); - classbits[c/8] |= (1 << (c&7)); - } - classCharCount++; - classLastChar = c; - } - } - - /* If classCharCount is 1, we saw precisely one character whose value is - less than 256. In non-UTF-8 mode we can always optimize. In UTF-8 mode, we - can optimize the negative case only if there were no characters >= 128 - because OP_NOT and the related opcodes like OP_NOTSTAR operate on - single-bytes only. This is an historical hangover. Maybe one day we can - tidy these opcodes to handle multi-byte characters. - - The optimization throws away the bit map. We turn the item into a - 1-character OP_CHAR[NC] if it's positive, or OP_NOT if it's negative. Note - that OP_NOT does not support multibyte characters. In the positive case, it - can cause firstByte to be set. Otherwise, there can be no first char if - this item is first, whatever repeat count may follow. In the case of - reqByte, save the previous value for reinstating. */ - - if (classCharCount == 1 && (!class_utf8 && (!negateClass || classLastChar < 128))) { - zeroReqByte = reqByte; - - /* The OP_NOT opcode works on one-byte characters only. */ - - if (negateClass) { - if (firstByte == REQ_UNSET) - firstByte = REQ_NONE; - zeroFirstByte = firstByte; - *code++ = OP_NOT; - *code++ = classLastChar; - break; - } - - /* For a single, positive character, get the value into c, and - then we can handle this with the normal one-character code. */ - - c = classLastChar; - goto NORMAL_CHAR; - } /* End of 1-char optimization */ - - /* The general case - not the one-char optimization. If this is the first - thing in the branch, there can be no first char setting, whatever the - repeat count. Any reqByte setting must remain unchanged after any kind of - repeat. */ - - if (firstByte == REQ_UNSET) firstByte = REQ_NONE; - zeroFirstByte = firstByte; - zeroReqByte = reqByte; - - /* If there are characters with values > 255, we have to compile an - extended class, with its own opcode. If there are no characters < 256, - we can omit the bitmap. */ - - if (class_utf8 && !shouldFlipNegation) { - *class_utf8data++ = XCL_END; /* Marks the end of extra data */ - *code++ = OP_XCLASS; - code += LINK_SIZE; - *code = negateClass? XCL_NOT : 0; - - /* If the map is required, install it, and move on to the end of - the extra data */ - - if (classCharCount > 0) { - *code++ |= XCL_MAP; - memcpy(code, classbits, 32); - code = class_utf8data; - } - - /* If the map is not required, slide down the extra data. */ - - else { - int len = class_utf8data - (code + 33); - memmove(code + 1, code + 33, len); - code += len + 1; - } - - /* Now fill in the complete length of the item */ - - putLinkValue(previous + 1, code - previous); - break; /* End of class handling */ - } - - /* If there are no characters > 255, negate the 32-byte map if necessary, - and copy it into the code vector. If this is the first thing in the branch, - there can be no first char setting, whatever the repeat count. Any reqByte - setting must remain unchanged after any kind of repeat. */ - - *code++ = (negateClass == shouldFlipNegation) ? OP_CLASS : OP_NCLASS; - if (negateClass) - for (c = 0; c < 32; c++) - code[c] = ~classbits[c]; - else - memcpy(code, classbits, 32); - code += 32; - break; - } - - /* Various kinds of repeat; '{' is not necessarily a quantifier, but this - has been tested above. */ - - case '{': - if (!isQuantifier) - goto NORMAL_CHAR; - ptr = readRepeatCounts(ptr + 1, &repeatMin, &repeat_max, errorCodePtr); - if (*errorCodePtr) - goto FAILED; - goto REPEAT; - - case '*': - repeatMin = 0; - repeat_max = -1; - goto REPEAT; - - case '+': - repeatMin = 1; - repeat_max = -1; - goto REPEAT; - - case '?': - repeatMin = 0; - repeat_max = 1; - - REPEAT: - if (!previous) { - *errorCodePtr = ERR9; - goto FAILED; - } - - if (repeatMin == 0) { - firstByte = zeroFirstByte; /* Adjust for zero repeat */ - reqByte = zeroReqByte; /* Ditto */ - } - - /* Remember whether this is a variable length repeat */ - - reqvary = (repeatMin == repeat_max) ? 0 : REQ_VARY; - - opType = 0; /* Default single-char op codes */ - - /* Save start of previous item, in case we have to move it up to make space - for an inserted OP_ONCE for the additional '+' extension. */ - /* FIXME: Probably don't need this because we don't use OP_ONCE. */ - - tempcode = previous; - - /* If the next character is '+', we have a possessive quantifier. This - implies greediness, whatever the setting of the PCRE_UNGREEDY option. - If the next character is '?' this is a minimizing repeat, by default, - but if PCRE_UNGREEDY is set, it works the other way round. We change the - repeat type to the non-default. */ - - if (safelyCheckNextChar(ptr, patternEnd, '?')) { - repeatType = 1; - ptr++; - } else - repeatType = 0; - - /* If previous was a character match, abolish the item and generate a - repeat item instead. If a char item has a minumum of more than one, ensure - that it is set in reqByte - it might not be if a sequence such as x{3} is - the first thing in a branch because the x will have gone into firstByte - instead. */ - - if (*previous == OP_CHAR || *previous == OP_CHAR_IGNORING_CASE) { - /* Deal with UTF-8 characters that take up more than one byte. It's - easier to write this out separately than try to macrify it. Use c to - hold the length of the character in bytes, plus 0x80 to flag that it's a - length rather than a small character. */ - - if (code[-1] & 0x80) { - unsigned char *lastchar = code - 1; - while((*lastchar & 0xc0) == 0x80) - lastchar--; - c = code - lastchar; /* Length of UTF-8 character */ - memcpy(utf8_char, lastchar, c); /* Save the char */ - c |= 0x80; /* Flag c as a length */ - } - else { - c = code[-1]; - if (repeatMin > 1) - reqByte = c | reqCaseOpt | cd.reqVaryOpt; - } - - goto OUTPUT_SINGLE_REPEAT; /* Code shared with single character types */ - } - - else if (*previous == OP_ASCII_CHAR || *previous == OP_ASCII_LETTER_IGNORING_CASE) { - c = previous[1]; - if (repeatMin > 1) - reqByte = c | reqCaseOpt | cd.reqVaryOpt; - goto OUTPUT_SINGLE_REPEAT; - } - - /* If previous was a single negated character ([^a] or similar), we use - one of the special opcodes, replacing it. The code is shared with single- - character repeats by setting opt_type to add a suitable offset into - repeatType. OP_NOT is currently used only for single-byte chars. */ - - else if (*previous == OP_NOT) { - opType = OP_NOTSTAR - OP_STAR; /* Use "not" opcodes */ - c = previous[1]; - goto OUTPUT_SINGLE_REPEAT; - } - - /* If previous was a character type match (\d or similar), abolish it and - create a suitable repeat item. The code is shared with single-character - repeats by setting opType to add a suitable offset into repeatType. */ - - else if (*previous <= OP_NOT_NEWLINE) { - opType = OP_TYPESTAR - OP_STAR; /* Use type opcodes */ - c = *previous; - - OUTPUT_SINGLE_REPEAT: - int prop_type = -1; - int prop_value = -1; - - unsigned char* oldcode = code; - code = previous; /* Usually overwrite previous item */ - - /* If the maximum is zero then the minimum must also be zero; Perl allows - this case, so we do too - by simply omitting the item altogether. */ - - if (repeat_max == 0) - goto END_REPEAT; - - /* Combine the opType with the repeatType */ - - repeatType += opType; - - /* A minimum of zero is handled either as the special case * or ?, or as - an UPTO, with the maximum given. */ - - if (repeatMin == 0) { - if (repeat_max == -1) - *code++ = OP_STAR + repeatType; - else if (repeat_max == 1) - *code++ = OP_QUERY + repeatType; - else { - *code++ = OP_UPTO + repeatType; - put2ByteValueAndAdvance(code, repeat_max); - } - } - - /* A repeat minimum of 1 is optimized into some special cases. If the - maximum is unlimited, we use OP_PLUS. Otherwise, the original item it - left in place and, if the maximum is greater than 1, we use OP_UPTO with - one less than the maximum. */ - - else if (repeatMin == 1) { - if (repeat_max == -1) - *code++ = OP_PLUS + repeatType; - else { - code = oldcode; /* leave previous item in place */ - if (repeat_max == 1) - goto END_REPEAT; - *code++ = OP_UPTO + repeatType; - put2ByteValueAndAdvance(code, repeat_max - 1); - } - } - - /* The case {n,n} is just an EXACT, while the general case {n,m} is - handled as an EXACT followed by an UPTO. */ - - else { - *code++ = OP_EXACT + opType; /* NB EXACT doesn't have repeatType */ - put2ByteValueAndAdvance(code, repeatMin); - - /* If the maximum is unlimited, insert an OP_STAR. Before doing so, - we have to insert the character for the previous code. For a repeated - Unicode property match, there are two extra bytes that define the - required property. In UTF-8 mode, long characters have their length in - c, with the 0x80 bit as a flag. */ - - if (repeat_max < 0) { - if (c >= 128) { - memcpy(code, utf8_char, c & 7); - code += c & 7; - } else { - *code++ = c; - if (prop_type >= 0) { - *code++ = prop_type; - *code++ = prop_value; - } - } - *code++ = OP_STAR + repeatType; - } - - /* Else insert an UPTO if the max is greater than the min, again - preceded by the character, for the previously inserted code. */ - - else if (repeat_max != repeatMin) { - if (c >= 128) { - memcpy(code, utf8_char, c & 7); - code += c & 7; - } else - *code++ = c; - if (prop_type >= 0) { - *code++ = prop_type; - *code++ = prop_value; - } - repeat_max -= repeatMin; - *code++ = OP_UPTO + repeatType; - put2ByteValueAndAdvance(code, repeat_max); - } - } - - /* The character or character type itself comes last in all cases. */ - - if (c >= 128) { - memcpy(code, utf8_char, c & 7); - code += c & 7; - } else - *code++ = c; - - /* For a repeated Unicode property match, there are two extra bytes that - define the required property. */ - - if (prop_type >= 0) { - *code++ = prop_type; - *code++ = prop_value; - } - } - - /* If previous was a character class or a back reference, we put the repeat - stuff after it, but just skip the item if the repeat was {0,0}. */ - - else if (*previous == OP_CLASS || - *previous == OP_NCLASS || - *previous == OP_XCLASS || - *previous == OP_REF) - { - if (repeat_max == 0) { - code = previous; - goto END_REPEAT; - } - - if (repeatMin == 0 && repeat_max == -1) - *code++ = OP_CRSTAR + repeatType; - else if (repeatMin == 1 && repeat_max == -1) - *code++ = OP_CRPLUS + repeatType; - else if (repeatMin == 0 && repeat_max == 1) - *code++ = OP_CRQUERY + repeatType; - else { - *code++ = OP_CRRANGE + repeatType; - put2ByteValueAndAdvance(code, repeatMin); - if (repeat_max == -1) - repeat_max = 0; /* 2-byte encoding for max */ - put2ByteValueAndAdvance(code, repeat_max); - } - } - - /* If previous was a bracket group, we may have to replicate it in certain - cases. */ - - else if (*previous >= OP_BRA) { - int ketoffset = 0; - int len = code - previous; - unsigned char* bralink = NULL; - - /* If the maximum repeat count is unlimited, find the end of the bracket - by scanning through from the start, and compute the offset back to it - from the current code pointer. There may be an OP_OPT setting following - the final KET, so we can't find the end just by going back from the code - pointer. */ - - if (repeat_max == -1) { - const unsigned char* ket = previous; - advanceToEndOfBracket(ket); - ketoffset = code - ket; - } - - /* The case of a zero minimum is special because of the need to stick - OP_BRAZERO in front of it, and because the group appears once in the - data, whereas in other cases it appears the minimum number of times. For - this reason, it is simplest to treat this case separately, as otherwise - the code gets far too messy. There are several special subcases when the - minimum is zero. */ - - if (repeatMin == 0) { - /* If the maximum is also zero, we just omit the group from the output - altogether. */ - - if (repeat_max == 0) { - code = previous; - goto END_REPEAT; - } - - /* If the maximum is 1 or unlimited, we just have to stick in the - BRAZERO and do no more at this point. However, we do need to adjust - any OP_RECURSE calls inside the group that refer to the group itself or - any internal group, because the offset is from the start of the whole - regex. Temporarily terminate the pattern while doing this. */ - - if (repeat_max <= 1) { - *code = OP_END; - memmove(previous+1, previous, len); - code++; - *previous++ = OP_BRAZERO + repeatType; - } - - /* If the maximum is greater than 1 and limited, we have to replicate - in a nested fashion, sticking OP_BRAZERO before each set of brackets. - The first one has to be handled carefully because it's the original - copy, which has to be moved up. The remainder can be handled by code - that is common with the non-zero minimum case below. We have to - adjust the value of repeat_max, since one less copy is required. */ - - else { - *code = OP_END; - memmove(previous + 2 + LINK_SIZE, previous, len); - code += 2 + LINK_SIZE; - *previous++ = OP_BRAZERO + repeatType; - *previous++ = OP_BRA; - - /* We chain together the bracket offset fields that have to be - filled in later when the ends of the brackets are reached. */ - - int offset = (!bralink) ? 0 : previous - bralink; - bralink = previous; - putLinkValueAllowZeroAndAdvance(previous, offset); - } - - repeat_max--; - } - - /* If the minimum is greater than zero, replicate the group as many - times as necessary, and adjust the maximum to the number of subsequent - copies that we need. If we set a first char from the group, and didn't - set a required char, copy the latter from the former. */ - - else { - if (repeatMin > 1) { - if (didGroupSetFirstByte && reqByte < 0) - reqByte = firstByte; - for (int i = 1; i < repeatMin; i++) { - memcpy(code, previous, len); - code += len; - } - } - if (repeat_max > 0) - repeat_max -= repeatMin; - } - - /* This code is common to both the zero and non-zero minimum cases. If - the maximum is limited, it replicates the group in a nested fashion, - remembering the bracket starts on a stack. In the case of a zero minimum, - the first one was set up above. In all cases the repeat_max now specifies - the number of additional copies needed. */ - - if (repeat_max >= 0) { - for (int i = repeat_max - 1; i >= 0; i--) { - *code++ = OP_BRAZERO + repeatType; - - /* All but the final copy start a new nesting, maintaining the - chain of brackets outstanding. */ - - if (i != 0) { - *code++ = OP_BRA; - int offset = (!bralink) ? 0 : code - bralink; - bralink = code; - putLinkValueAllowZeroAndAdvance(code, offset); - } - - memcpy(code, previous, len); - code += len; - } - - /* Now chain through the pending brackets, and fill in their length - fields (which are holding the chain links pro tem). */ - - while (bralink) { - int offset = code - bralink + 1; - unsigned char* bra = code - offset; - int oldlinkoffset = getLinkValueAllowZero(bra + 1); - bralink = (!oldlinkoffset) ? 0 : bralink - oldlinkoffset; - *code++ = OP_KET; - putLinkValueAndAdvance(code, offset); - putLinkValue(bra + 1, offset); - } - } - - /* If the maximum is unlimited, set a repeater in the final copy. We - can't just offset backwards from the current code point, because we - don't know if there's been an options resetting after the ket. The - correct offset was computed above. */ - - else - code[-ketoffset] = OP_KETRMAX + repeatType; - } - - // A quantifier after an assertion is mostly meaningless, but it - // can nullify the assertion if it has a 0 minimum. - else if (*previous == OP_ASSERT || *previous == OP_ASSERT_NOT) { - if (repeatMin == 0) { - code = previous; - goto END_REPEAT; - } - } - - /* Else there's some kind of shambles */ - - else { - *errorCodePtr = ERR11; - goto FAILED; - } - - /* In all case we no longer have a previous item. We also set the - "follows varying string" flag for subsequently encountered reqbytes if - it isn't already set and we have just passed a varying length item. */ - - END_REPEAT: - previous = NULL; - cd.reqVaryOpt |= reqvary; - break; - - /* Start of nested bracket sub-expression, or comment or lookahead or - lookbehind or option setting or condition. First deal with special things - that can come after a bracket; all are introduced by ?, and the appearance - of any of them means that this is not a referencing group. They were - checked for validity in the first pass over the string, so we don't have to - check for syntax errors here. */ - - case '(': - skipBytes = 0; - - if (*(++ptr) == '?') { - switch (*(++ptr)) { - case ':': /* Non-extracting bracket */ - bravalue = OP_BRA; - ptr++; - break; - - case '=': /* Positive lookahead */ - bravalue = OP_ASSERT; - ptr++; - break; - - case '!': /* Negative lookahead */ - bravalue = OP_ASSERT_NOT; - ptr++; - break; - - /* Character after (? not specially recognized */ - - default: - *errorCodePtr = ERR12; - goto FAILED; - } - } - - /* Else we have a referencing group; adjust the opcode. If the bracket - number is greater than EXTRACT_BASIC_MAX, we set the opcode one higher, and - arrange for the true number to follow later, in an OP_BRANUMBER item. */ - - else { - if (++(*brackets) > EXTRACT_BASIC_MAX) { - bravalue = OP_BRA + EXTRACT_BASIC_MAX + 1; - code[1 + LINK_SIZE] = OP_BRANUMBER; - put2ByteValue(code + 2 + LINK_SIZE, *brackets); - skipBytes = 3; - } - else - bravalue = OP_BRA + *brackets; - } - - /* Process nested bracketed re. We copy code into a non-variable - in order to be able to pass its address because some compilers - complain otherwise. Pass in a new setting for the ims options - if they have changed. */ - - previous = code; - *code = bravalue; - tempcode = code; - tempreqvary = cd.reqVaryOpt; /* Save value before bracket */ - - if (!compileBracket( - options, - brackets, /* Extracting bracket count */ - &tempcode, /* Where to put code (updated) */ - &ptr, /* Input pointer (updated) */ - patternEnd, - errorCodePtr, /* Where to put an error message */ - skipBytes, /* Skip over OP_BRANUMBER */ - &subFirstByte, /* For possible first char */ - &subReqByte, /* For possible last char */ - cd)) /* Tables block */ - goto FAILED; - - /* At the end of compiling, code is still pointing to the start of the - group, while tempcode has been updated to point past the end of the group - and any option resetting that may follow it. The pattern pointer (ptr) - is on the bracket. */ - - /* Handle updating of the required and first characters. Update for normal - brackets of all kinds, and conditions with two branches (see code above). - If the bracket is followed by a quantifier with zero repeat, we have to - back off. Hence the definition of zeroReqByte and zeroFirstByte outside the - main loop so that they can be accessed for the back off. */ - - zeroReqByte = reqByte; - zeroFirstByte = firstByte; - didGroupSetFirstByte = false; - - if (bravalue >= OP_BRA) { - /* If we have not yet set a firstByte in this branch, take it from the - subpattern, remembering that it was set here so that a repeat of more - than one can replicate it as reqByte if necessary. If the subpattern has - no firstByte, set "none" for the whole branch. In both cases, a zero - repeat forces firstByte to "none". */ - - if (firstByte == REQ_UNSET) { - if (subFirstByte >= 0) { - firstByte = subFirstByte; - didGroupSetFirstByte = true; - } - else - firstByte = REQ_NONE; - zeroFirstByte = REQ_NONE; - } - - /* If firstByte was previously set, convert the subpattern's firstByte - into reqByte if there wasn't one, using the vary flag that was in - existence beforehand. */ - - else if (subFirstByte >= 0 && subReqByte < 0) - subReqByte = subFirstByte | tempreqvary; - - /* If the subpattern set a required byte (or set a first byte that isn't - really the first byte - see above), set it. */ - - if (subReqByte >= 0) - reqByte = subReqByte; - } - - /* For a forward assertion, we take the reqByte, if set. This can be - helpful if the pattern that follows the assertion doesn't set a different - char. For example, it's useful for /(?=abcde).+/. We can't set firstByte - for an assertion, however because it leads to incorrect effect for patterns - such as /(?=a)a.+/ when the "real" "a" would then become a reqByte instead - of a firstByte. This is overcome by a scan at the end if there's no - firstByte, looking for an asserted first char. */ - - else if (bravalue == OP_ASSERT && subReqByte >= 0) - reqByte = subReqByte; - - /* Now update the main code pointer to the end of the group. */ - - code = tempcode; - - /* Error if hit end of pattern */ - - if (ptr >= patternEnd || *ptr != ')') { - *errorCodePtr = ERR14; - goto FAILED; - } - break; - - /* Check \ for being a real metacharacter; if not, fall through and handle - it as a data character at the start of a string. Escape items are checked - for validity in the pre-compiling pass. */ - - case '\\': - tempptr = ptr; - c = checkEscape(&ptr, patternEnd, errorCodePtr, cd.numCapturingBrackets, false); - - /* Handle metacharacters introduced by \. For ones like \d, the ESC_ values - are arranged to be the negation of the corresponding OP_values. For the - back references, the values are ESC_REF plus the reference number. Only - back references and those types that consume a character may be repeated. - We can test for values between ESC_b and ESC_w for the latter; this may - have to change if any new ones are ever created. */ - - if (c < 0) { - /* For metasequences that actually match a character, we disable the - setting of a first character if it hasn't already been set. */ - - if (firstByte == REQ_UNSET && -c > ESC_b && -c <= ESC_w) - firstByte = REQ_NONE; - - /* Set values to reset to if this is followed by a zero repeat. */ - - zeroFirstByte = firstByte; - zeroReqByte = reqByte; - - /* Back references are handled specially */ - - if (-c >= ESC_REF) { - int number = -c - ESC_REF; - previous = code; - *code++ = OP_REF; - put2ByteValueAndAdvance(code, number); - } - - /* For the rest, we can obtain the OP value by negating the escape - value */ - - else { - previous = (-c > ESC_b && -c <= ESC_w) ? code : NULL; - *code++ = -c; - } - continue; - } - - /* Fall through. */ - - /* Handle a literal character. It is guaranteed not to be whitespace or # - when the extended flag is set. If we are in UTF-8 mode, it may be a - multi-byte literal character. */ - - default: - NORMAL_CHAR: - - previous = code; - - if (c < 128) { - mcLength = 1; - mcbuffer[0] = c; - - if ((options & IgnoreCaseOption) && (c | 0x20) >= 'a' && (c | 0x20) <= 'z') { - *code++ = OP_ASCII_LETTER_IGNORING_CASE; - *code++ = c | 0x20; - } else { - *code++ = OP_ASCII_CHAR; - *code++ = c; - } - } else { - mcLength = encodeUTF8(c, mcbuffer); - - *code++ = (options & IgnoreCaseOption) ? OP_CHAR_IGNORING_CASE : OP_CHAR; - for (c = 0; c < mcLength; c++) - *code++ = mcbuffer[c]; - } - - /* Set the first and required bytes appropriately. If no previous first - byte, set it from this character, but revert to none on a zero repeat. - Otherwise, leave the firstByte value alone, and don't change it on a zero - repeat. */ - - if (firstByte == REQ_UNSET) { - zeroFirstByte = REQ_NONE; - zeroReqByte = reqByte; - - /* If the character is more than one byte long, we can set firstByte - only if it is not to be matched caselessly. */ - - if (mcLength == 1 || reqCaseOpt == 0) { - firstByte = mcbuffer[0] | reqCaseOpt; - if (mcLength != 1) - reqByte = code[-1] | cd.reqVaryOpt; - } - else - firstByte = reqByte = REQ_NONE; - } - - /* firstByte was previously set; we can set reqByte only the length is - 1 or the matching is caseful. */ - - else { - zeroFirstByte = firstByte; - zeroReqByte = reqByte; - if (mcLength == 1 || reqCaseOpt == 0) - reqByte = code[-1] | reqCaseOpt | cd.reqVaryOpt; - } - - break; /* End of literal character handling */ - } - } /* end of big loop */ - - /* Control never reaches here by falling through, only by a goto for all the - error states. Pass back the position in the pattern so that it can be displayed - to the user for diagnosing the error. */ - -FAILED: - *ptrPtr = ptr; - return false; -} - -/************************************************* -* Compile sequence of alternatives * -*************************************************/ - -/* On entry, ptr is pointing past the bracket character, but on return -it points to the closing bracket, or vertical bar, or end of string. -The code variable is pointing at the byte into which the BRA operator has been -stored. If the ims options are changed at the start (for a (?ims: group) or -during any branch, we need to insert an OP_OPT item at the start of every -following branch to ensure they get set correctly at run time, and also pass -the new options into every subsequent branch compile. - -Argument: - options option bits, including any changes for this subpattern - brackets -> int containing the number of extracting brackets used - codePtr -> the address of the current code pointer - ptrPtr -> the address of the current pattern pointer - errorCodePtr -> pointer to error code variable - skipBytes skip this many bytes at start (for OP_BRANUMBER) - firstbyteptr place to put the first required character, or a negative number - reqbyteptr place to put the last required character, or a negative number - cd points to the data block with tables pointers etc. - -Returns: true on success -*/ - -static bool -compileBracket(int options, int* brackets, unsigned char** codePtr, - const UChar** ptrPtr, const UChar* patternEnd, ErrorCode* errorCodePtr, int skipBytes, - int* firstbyteptr, int* reqbyteptr, CompileData& cd) -{ - const UChar* ptr = *ptrPtr; - unsigned char* code = *codePtr; - unsigned char* lastBranch = code; - unsigned char* start_bracket = code; - int firstByte = REQ_UNSET; - int reqByte = REQ_UNSET; - - /* Offset is set zero to mark that this bracket is still open */ - - putLinkValueAllowZero(code + 1, 0); - code += 1 + LINK_SIZE + skipBytes; - - /* Loop for each alternative branch */ - - while (true) { - /* Now compile the branch */ - - int branchFirstByte; - int branchReqByte; - if (!compileBranch(options, brackets, &code, &ptr, patternEnd, errorCodePtr, - &branchFirstByte, &branchReqByte, cd)) { - *ptrPtr = ptr; - return false; - } - - /* If this is the first branch, the firstByte and reqByte values for the - branch become the values for the regex. */ - - if (*lastBranch != OP_ALT) { - firstByte = branchFirstByte; - reqByte = branchReqByte; - } - - /* If this is not the first branch, the first char and reqByte have to - match the values from all the previous branches, except that if the previous - value for reqByte didn't have REQ_VARY set, it can still match, and we set - REQ_VARY for the regex. */ - - else { - /* If we previously had a firstByte, but it doesn't match the new branch, - we have to abandon the firstByte for the regex, but if there was previously - no reqByte, it takes on the value of the old firstByte. */ - - if (firstByte >= 0 && firstByte != branchFirstByte) { - if (reqByte < 0) - reqByte = firstByte; - firstByte = REQ_NONE; - } - - /* If we (now or from before) have no firstByte, a firstByte from the - branch becomes a reqByte if there isn't a branch reqByte. */ - - if (firstByte < 0 && branchFirstByte >= 0 && branchReqByte < 0) - branchReqByte = branchFirstByte; - - /* Now ensure that the reqbytes match */ - - if ((reqByte & ~REQ_VARY) != (branchReqByte & ~REQ_VARY)) - reqByte = REQ_NONE; - else - reqByte |= branchReqByte; /* To "or" REQ_VARY */ - } - - /* Reached end of expression, either ')' or end of pattern. Go back through - the alternative branches and reverse the chain of offsets, with the field in - the BRA item now becoming an offset to the first alternative. If there are - no alternatives, it points to the end of the group. The length in the - terminating ket is always the length of the whole bracketed item. If any of - the ims options were changed inside the group, compile a resetting op-code - following, except at the very end of the pattern. Return leaving the pointer - at the terminating char. */ - - if (ptr >= patternEnd || *ptr != '|') { - int length = code - lastBranch; - do { - int prevLength = getLinkValueAllowZero(lastBranch + 1); - putLinkValue(lastBranch + 1, length); - length = prevLength; - lastBranch -= length; - } while (length > 0); - - /* Fill in the ket */ - - *code = OP_KET; - putLinkValue(code + 1, code - start_bracket); - code += 1 + LINK_SIZE; - - /* Set values to pass back */ - - *codePtr = code; - *ptrPtr = ptr; - *firstbyteptr = firstByte; - *reqbyteptr = reqByte; - return true; - } - - /* Another branch follows; insert an "or" node. Its length field points back - to the previous branch while the bracket remains open. At the end the chain - is reversed. It's done like this so that the start of the bracket has a - zero offset until it is closed, making it possible to detect recursion. */ - - *code = OP_ALT; - putLinkValue(code + 1, code - lastBranch); - lastBranch = code; - code += 1 + LINK_SIZE; - ptr++; - } - ASSERT_NOT_REACHED(); -} - -/************************************************* -* Check for anchored expression * -*************************************************/ - -/* Try to find out if this is an anchored regular expression. Consider each -alternative branch. If they all start OP_CIRC, or with a bracket -all of whose alternatives start OP_CIRC (recurse ad lib), then -it's anchored. - -Arguments: - code points to start of expression (the bracket) - captureMap a bitmap of which brackets we are inside while testing; this - handles up to substring 31; all brackets after that share - the zero bit - backrefMap the back reference bitmap -*/ - -static bool branchIsAnchored(const unsigned char* code) -{ - const unsigned char* scode = firstSignificantOpcode(code); - int op = *scode; - - /* Brackets */ - if (op >= OP_BRA || op == OP_ASSERT) - return bracketIsAnchored(scode); - - /* Check for explicit anchoring */ - return op == OP_CIRC; -} - -static bool bracketIsAnchored(const unsigned char* code) -{ - do { - if (!branchIsAnchored(code + 1 + LINK_SIZE)) - return false; - code += getLinkValue(code + 1); - } while (*code == OP_ALT); /* Loop for each alternative */ - return true; -} - -/************************************************* -* Check for starting with ^ or .* * -*************************************************/ - -/* This is called to find out if every branch starts with ^ or .* so that -"first char" processing can be done to speed things up in multiline -matching and for non-DOTALL patterns that start with .* (which must start at -the beginning or after \n) - -Except when the .* appears inside capturing parentheses, and there is a -subsequent back reference to those parentheses. By keeping a bitmap of the -first 31 back references, we can catch some of the more common cases more -precisely; all the greater back references share a single bit. - -Arguments: - code points to start of expression (the bracket) - captureMap a bitmap of which brackets we are inside while testing; this - handles up to substring 31; all brackets after that share - the zero bit - backrefMap the back reference bitmap -*/ - -static bool branchNeedsLineStart(const unsigned char* code, unsigned captureMap, unsigned backrefMap) -{ - const unsigned char* scode = firstSignificantOpcode(code); - int op = *scode; - - /* Capturing brackets */ - if (op > OP_BRA) { - int captureNum = op - OP_BRA; - if (captureNum > EXTRACT_BASIC_MAX) - captureNum = get2ByteValue(scode + 2 + LINK_SIZE); - int bracketMask = (captureNum < 32) ? (1 << captureNum) : 1; - return bracketNeedsLineStart(scode, captureMap | bracketMask, backrefMap); - } - - /* Other brackets */ - if (op == OP_BRA || op == OP_ASSERT) - return bracketNeedsLineStart(scode, captureMap, backrefMap); - - /* .* means "start at start or after \n" if it isn't in brackets that - may be referenced. */ - - if (op == OP_TYPESTAR || op == OP_TYPEMINSTAR) - return scode[1] == OP_NOT_NEWLINE && !(captureMap & backrefMap); - - /* Explicit ^ */ - return op == OP_CIRC || op == OP_BOL; -} - -static bool bracketNeedsLineStart(const unsigned char* code, unsigned captureMap, unsigned backrefMap) -{ - do { - if (!branchNeedsLineStart(code + 1 + LINK_SIZE, captureMap, backrefMap)) - return false; - code += getLinkValue(code + 1); - } while (*code == OP_ALT); /* Loop for each alternative */ - return true; -} - -/************************************************* -* Check for asserted fixed first char * -*************************************************/ - -/* During compilation, the "first char" settings from forward assertions are -discarded, because they can cause conflicts with actual literals that follow. -However, if we end up without a first char setting for an unanchored pattern, -it is worth scanning the regex to see if there is an initial asserted first -char. If all branches start with the same asserted char, or with a bracket all -of whose alternatives start with the same asserted char (recurse ad lib), then -we return that char, otherwise -1. - -Arguments: - code points to start of expression (the bracket) - options pointer to the options (used to check casing changes) - inassert true if in an assertion - -Returns: -1 or the fixed first char -*/ - -static int branchFindFirstAssertedCharacter(const unsigned char* code, bool inassert) -{ - const unsigned char* scode = firstSignificantOpcodeSkippingAssertions(code); - int op = *scode; - - if (op >= OP_BRA) - op = OP_BRA; - - switch (op) { - default: - return -1; - - case OP_BRA: - case OP_ASSERT: - return bracketFindFirstAssertedCharacter(scode, op == OP_ASSERT); - - case OP_EXACT: - scode += 2; - /* Fall through */ - - case OP_CHAR: - case OP_CHAR_IGNORING_CASE: - case OP_ASCII_CHAR: - case OP_ASCII_LETTER_IGNORING_CASE: - case OP_PLUS: - case OP_MINPLUS: - if (!inassert) - return -1; - return scode[1]; - } -} - -static int bracketFindFirstAssertedCharacter(const unsigned char* code, bool inassert) -{ - int c = -1; - do { - int d = branchFindFirstAssertedCharacter(code + 1 + LINK_SIZE, inassert); - if (d < 0) - return -1; - if (c < 0) - c = d; - else if (c != d) - return -1; - code += getLinkValue(code + 1); - } while (*code == OP_ALT); - return c; -} - -static inline int multiplyWithOverflowCheck(int a, int b) -{ - if (!a || !b) - return 0; - if (a > MAX_PATTERN_SIZE / b) - return -1; - return a * b; -} - -static int calculateCompiledPatternLength(const UChar* pattern, int patternLength, JSRegExpIgnoreCaseOption ignoreCase, - CompileData& cd, ErrorCode& errorcode) -{ - /* Make a pass over the pattern to compute the - amount of store required to hold the compiled code. This does not have to be - perfect as long as errors are overestimates. */ - - if (patternLength > MAX_PATTERN_SIZE) { - errorcode = ERR16; - return -1; - } - - int length = 1 + LINK_SIZE; /* For initial BRA plus length */ - int branch_extra = 0; - int lastitemlength = 0; - unsigned brastackptr = 0; - FixedArray<int, BRASTACK_SIZE> brastack; - FixedArray<unsigned char, BRASTACK_SIZE> bralenstack; - int bracount = 0; - - const UChar* ptr = (const UChar*)(pattern - 1); - const UChar* patternEnd = (const UChar*)(pattern + patternLength); - - while (++ptr < patternEnd) { - int minRepeats = 0, maxRepeats = 0; - int c = *ptr; - - switch (c) { - /* A backslashed item may be an escaped data character or it may be a - character type. */ - - case '\\': - c = checkEscape(&ptr, patternEnd, &errorcode, cd.numCapturingBrackets, false); - if (errorcode != 0) - return -1; - - lastitemlength = 1; /* Default length of last item for repeats */ - - if (c >= 0) { /* Data character */ - length += 2; /* For a one-byte character */ - - if (c > 127) { - int i; - for (i = 0; i < jsc_pcre_utf8_table1_size; i++) - if (c <= jsc_pcre_utf8_table1[i]) break; - length += i; - lastitemlength += i; - } - - continue; - } - - /* Other escapes need one byte */ - - length++; - - /* A back reference needs an additional 2 bytes, plus either one or 5 - bytes for a repeat. We also need to keep the value of the highest - back reference. */ - - if (c <= -ESC_REF) { - int refnum = -c - ESC_REF; - cd.backrefMap |= (refnum < 32) ? (1 << refnum) : 1; - if (refnum > cd.topBackref) - cd.topBackref = refnum; - length += 2; /* For single back reference */ - if (safelyCheckNextChar(ptr, patternEnd, '{') && isCountedRepeat(ptr + 2, patternEnd)) { - ptr = readRepeatCounts(ptr + 2, &minRepeats, &maxRepeats, &errorcode); - if (errorcode) - return -1; - if ((minRepeats == 0 && (maxRepeats == 1 || maxRepeats == -1)) || - (minRepeats == 1 && maxRepeats == -1)) - length++; - else - length += 5; - if (safelyCheckNextChar(ptr, patternEnd, '?')) - ptr++; - } - } - continue; - - case '^': /* Single-byte metacharacters */ - case '.': - case '$': - length++; - lastitemlength = 1; - continue; - - case '*': /* These repeats won't be after brackets; */ - case '+': /* those are handled separately */ - case '?': - length++; - goto POSSESSIVE; - - /* This covers the cases of braced repeats after a single char, metachar, - class, or back reference. */ - - case '{': - if (!isCountedRepeat(ptr + 1, patternEnd)) - goto NORMAL_CHAR; - ptr = readRepeatCounts(ptr + 1, &minRepeats, &maxRepeats, &errorcode); - if (errorcode != 0) - return -1; - - /* These special cases just insert one extra opcode */ - - if ((minRepeats == 0 && (maxRepeats == 1 || maxRepeats == -1)) || - (minRepeats == 1 && maxRepeats == -1)) - length++; - - /* These cases might insert additional copies of a preceding character. */ - - else { - if (minRepeats != 1) { - length -= lastitemlength; /* Uncount the original char or metachar */ - if (minRepeats > 0) - length += 3 + lastitemlength; - } - length += lastitemlength + ((maxRepeats > 0) ? 3 : 1); - } - - if (safelyCheckNextChar(ptr, patternEnd, '?')) - ptr++; /* Needs no extra length */ - - POSSESSIVE: /* Test for possessive quantifier */ - if (safelyCheckNextChar(ptr, patternEnd, '+')) { - ptr++; - length += 2 + 2 * LINK_SIZE; /* Allow for atomic brackets */ - } - continue; - - /* An alternation contains an offset to the next branch or ket. If any ims - options changed in the previous branch(es), and/or if we are in a - lookbehind assertion, extra space will be needed at the start of the - branch. This is handled by branch_extra. */ - - case '|': - if (brastackptr == 0) - cd.needOuterBracket = true; - length += 1 + LINK_SIZE + branch_extra; - continue; - - /* A character class uses 33 characters provided that all the character - values are less than 256. Otherwise, it uses a bit map for low valued - characters, and individual items for others. Don't worry about character - types that aren't allowed in classes - they'll get picked up during the - compile. A character class that contains only one single-byte character - uses 2 or 3 bytes, depending on whether it is negated or not. Notice this - where we can. (In UTF-8 mode we can do this only for chars < 128.) */ - - case '[': { - int class_optcount; - if (*(++ptr) == '^') { - class_optcount = 10; /* Greater than one */ - ptr++; - } - else - class_optcount = 0; - - bool class_utf8 = false; - - for (; ptr < patternEnd && *ptr != ']'; ++ptr) { - /* Check for escapes */ - - if (*ptr == '\\') { - c = checkEscape(&ptr, patternEnd, &errorcode, cd.numCapturingBrackets, true); - if (errorcode != 0) - return -1; - - /* Handle escapes that turn into characters */ - - if (c >= 0) - goto NON_SPECIAL_CHARACTER; - - /* Escapes that are meta-things. The normal ones just affect the - bit map, but Unicode properties require an XCLASS extended item. */ - - else - class_optcount = 10; /* \d, \s etc; make sure > 1 */ - } - - /* Anything else increments the possible optimization count. We have to - detect ranges here so that we can compute the number of extra ranges for - caseless wide characters when UCP support is available. If there are wide - characters, we are going to have to use an XCLASS, even for single - characters. */ - - else { - c = *ptr; - - /* Come here from handling \ above when it escapes to a char value */ - - NON_SPECIAL_CHARACTER: - class_optcount++; - - int d = -1; - if (safelyCheckNextChar(ptr, patternEnd, '-')) { - const UChar* hyptr = ptr++; - if (safelyCheckNextChar(ptr, patternEnd, '\\')) { - ptr++; - d = checkEscape(&ptr, patternEnd, &errorcode, cd.numCapturingBrackets, true); - if (errorcode != 0) - return -1; - } - else if ((ptr + 1 < patternEnd) && ptr[1] != ']') - d = *++ptr; - if (d < 0) - ptr = hyptr; /* go back to hyphen as data */ - } - - /* If d >= 0 we have a range. In UTF-8 mode, if the end is > 255, or > - 127 for caseless matching, we will need to use an XCLASS. */ - - if (d >= 0) { - class_optcount = 10; /* Ensure > 1 */ - if (d < c) { - errorcode = ERR8; - return -1; - } - - if ((d > 255 || (ignoreCase && d > 127))) { - unsigned char buffer[6]; - if (!class_utf8) /* Allow for XCLASS overhead */ - { - class_utf8 = true; - length += LINK_SIZE + 2; - } - - /* If we have UCP support, find out how many extra ranges are - needed to map the other case of characters within this range. We - have to mimic the range optimization here, because extending the - range upwards might push d over a boundary that makes it use - another byte in the UTF-8 representation. */ - - if (ignoreCase) { - int occ, ocd; - int cc = c; - int origd = d; - while (getOthercaseRange(&cc, origd, &occ, &ocd)) { - if (occ >= c && ocd <= d) - continue; /* Skip embedded */ - - if (occ < c && ocd >= c - 1) /* Extend the basic range */ - { /* if there is overlap, */ - c = occ; /* noting that if occ < c */ - continue; /* we can't have ocd > d */ - } /* because a subrange is */ - if (ocd > d && occ <= d + 1) /* always shorter than */ - { /* the basic range. */ - d = ocd; - continue; - } - - /* An extra item is needed */ - - length += 1 + encodeUTF8(occ, buffer) + - ((occ == ocd) ? 0 : encodeUTF8(ocd, buffer)); - } - } - - /* The length of the (possibly extended) range */ - - length += 1 + encodeUTF8(c, buffer) + encodeUTF8(d, buffer); - } - - } - - /* We have a single character. There is nothing to be done unless we - are in UTF-8 mode. If the char is > 255, or 127 when caseless, we must - allow for an XCL_SINGLE item, doubled for caselessness if there is UCP - support. */ - - else { - if ((c > 255 || (ignoreCase && c > 127))) { - unsigned char buffer[6]; - class_optcount = 10; /* Ensure > 1 */ - if (!class_utf8) /* Allow for XCLASS overhead */ - { - class_utf8 = true; - length += LINK_SIZE + 2; - } - length += (ignoreCase ? 2 : 1) * (1 + encodeUTF8(c, buffer)); - } - } - } - } - - if (ptr >= patternEnd) { /* Missing terminating ']' */ - errorcode = ERR6; - return -1; - } - - /* We can optimize when there was only one optimizable character. - Note that this does not detect the case of a negated single character. - In that case we do an incorrect length computation, but it's not a serious - problem because the computed length is too large rather than too small. */ - - if (class_optcount == 1) - goto NORMAL_CHAR; - - /* Here, we handle repeats for the class opcodes. */ - { - length += 33; - - /* A repeat needs either 1 or 5 bytes. If it is a possessive quantifier, - we also need extra for wrapping the whole thing in a sub-pattern. */ - - if (safelyCheckNextChar(ptr, patternEnd, '{') && isCountedRepeat(ptr + 2, patternEnd)) { - ptr = readRepeatCounts(ptr + 2, &minRepeats, &maxRepeats, &errorcode); - if (errorcode != 0) - return -1; - if ((minRepeats == 0 && (maxRepeats == 1 || maxRepeats == -1)) || - (minRepeats == 1 && maxRepeats == -1)) - length++; - else - length += 5; - if (safelyCheckNextChar(ptr, patternEnd, '+')) { - ptr++; - length += 2 + 2 * LINK_SIZE; - } else if (safelyCheckNextChar(ptr, patternEnd, '?')) - ptr++; - } - } - continue; - } - - /* Brackets may be genuine groups or special things */ - - case '(': { - int branch_newextra = 0; - int bracket_length = 1 + LINK_SIZE; - bool capturing = false; - - /* Handle special forms of bracket, which all start (? */ - - if (safelyCheckNextChar(ptr, patternEnd, '?')) { - switch (c = (ptr + 2 < patternEnd ? ptr[2] : 0)) { - /* Non-referencing groups and lookaheads just move the pointer on, and - then behave like a non-special bracket, except that they don't increment - the count of extracting brackets. Ditto for the "once only" bracket, - which is in Perl from version 5.005. */ - - case ':': - case '=': - case '!': - ptr += 2; - break; - - /* Else loop checking valid options until ) is met. Anything else is an - error. If we are without any brackets, i.e. at top level, the settings - act as if specified in the options, so massage the options immediately. - This is for backward compatibility with Perl 5.004. */ - - default: - errorcode = ERR12; - return -1; - } - } else - capturing = 1; - - /* Capturing brackets must be counted so we can process escapes in a - Perlish way. If the number exceeds EXTRACT_BASIC_MAX we are going to need - an additional 3 bytes of memory per capturing bracket. */ - - if (capturing) { - bracount++; - if (bracount > EXTRACT_BASIC_MAX) - bracket_length += 3; - } - - /* Save length for computing whole length at end if there's a repeat that - requires duplication of the group. Also save the current value of - branch_extra, and start the new group with the new value. If non-zero, this - will either be 2 for a (?imsx: group, or 3 for a lookbehind assertion. */ - - if (brastackptr >= sizeof(brastack)/sizeof(int)) { - errorcode = ERR17; - return -1; - } - - bralenstack[brastackptr] = branch_extra; - branch_extra = branch_newextra; - - brastack[brastackptr++] = length; - length += bracket_length; - continue; - } - - /* Handle ket. Look for subsequent maxRepeats/minRepeats; for certain sets of values we - have to replicate this bracket up to that many times. If brastackptr is - 0 this is an unmatched bracket which will generate an error, but take care - not to try to access brastack[-1] when computing the length and restoring - the branch_extra value. */ - - case ')': { - int duplength; - length += 1 + LINK_SIZE; - if (brastackptr > 0) { - duplength = length - brastack[--brastackptr]; - branch_extra = bralenstack[brastackptr]; - } - else - duplength = 0; - - /* Leave ptr at the final char; for readRepeatCounts this happens - automatically; for the others we need an increment. */ - - if ((ptr + 1 < patternEnd) && (c = ptr[1]) == '{' && isCountedRepeat(ptr + 2, patternEnd)) { - ptr = readRepeatCounts(ptr + 2, &minRepeats, &maxRepeats, &errorcode); - if (errorcode) - return -1; - } else if (c == '*') { - minRepeats = 0; - maxRepeats = -1; - ptr++; - } else if (c == '+') { - minRepeats = 1; - maxRepeats = -1; - ptr++; - } else if (c == '?') { - minRepeats = 0; - maxRepeats = 1; - ptr++; - } else { - minRepeats = 1; - maxRepeats = 1; - } - - /* If the minimum is zero, we have to allow for an OP_BRAZERO before the - group, and if the maximum is greater than zero, we have to replicate - maxval-1 times; each replication acquires an OP_BRAZERO plus a nesting - bracket set. */ - - int repeatsLength; - if (minRepeats == 0) { - length++; - if (maxRepeats > 0) { - repeatsLength = multiplyWithOverflowCheck(maxRepeats - 1, duplength + 3 + 2 * LINK_SIZE); - if (repeatsLength < 0) { - errorcode = ERR16; - return -1; - } - length += repeatsLength; - if (length > MAX_PATTERN_SIZE) { - errorcode = ERR16; - return -1; - } - } - } - - /* When the minimum is greater than zero, we have to replicate up to - minval-1 times, with no additions required in the copies. Then, if there - is a limited maximum we have to replicate up to maxval-1 times allowing - for a BRAZERO item before each optional copy and nesting brackets for all - but one of the optional copies. */ - - else { - repeatsLength = multiplyWithOverflowCheck(minRepeats - 1, duplength); - if (repeatsLength < 0) { - errorcode = ERR16; - return -1; - } - length += repeatsLength; - if (maxRepeats > minRepeats) { /* Need this test as maxRepeats=-1 means no limit */ - repeatsLength = multiplyWithOverflowCheck(maxRepeats - minRepeats, duplength + 3 + 2 * LINK_SIZE); - if (repeatsLength < 0) { - errorcode = ERR16; - return -1; - } - length += repeatsLength - (2 + 2 * LINK_SIZE); - } - if (length > MAX_PATTERN_SIZE) { - errorcode = ERR16; - return -1; - } - } - - /* Allow space for once brackets for "possessive quantifier" */ - - if (safelyCheckNextChar(ptr, patternEnd, '+')) { - ptr++; - length += 2 + 2 * LINK_SIZE; - } - continue; - } - - /* Non-special character. It won't be space or # in extended mode, so it is - always a genuine character. If we are in a \Q...\E sequence, check for the - end; if not, we have a literal. */ - - default: - NORMAL_CHAR: - length += 2; /* For a one-byte character */ - lastitemlength = 1; /* Default length of last item for repeats */ - - if (c > 127) { - int i; - for (i = 0; i < jsc_pcre_utf8_table1_size; i++) - if (c <= jsc_pcre_utf8_table1[i]) - break; - length += i; - lastitemlength += i; - } - - continue; - } - } - - length += 2 + LINK_SIZE; /* For final KET and END */ - - cd.numCapturingBrackets = bracount; - return length; -} - -/************************************************* -* Compile a Regular Expression * -*************************************************/ - -/* This function takes a string and returns a pointer to a block of store -holding a compiled version of the expression. The original API for this -function had no error code return variable; it is retained for backwards -compatibility. The new function is given a new name. - -Arguments: - pattern the regular expression - options various option bits - errorCodePtr pointer to error code variable (pcre_compile2() only) - can be NULL if you don't want a code value - errorPtr pointer to pointer to error text - erroroffset ptr offset in pattern where error was detected - tables pointer to character tables or NULL - -Returns: pointer to compiled data block, or NULL on error, - with errorPtr and erroroffset set -*/ - -static inline JSRegExp* returnError(ErrorCode errorcode, const char** errorPtr) -{ - *errorPtr = errorText(errorcode); - return 0; -} - -JSRegExp* jsRegExpCompile(const UChar* pattern, int patternLength, - JSRegExpIgnoreCaseOption ignoreCase, JSRegExpMultilineOption multiline, - unsigned* numSubpatterns, const char** errorPtr) -{ - /* We can't pass back an error message if errorPtr is NULL; I guess the best we - can do is just return NULL, but we can set a code value if there is a code pointer. */ - if (!errorPtr) - return 0; - *errorPtr = NULL; - - CompileData cd; - - ErrorCode errorcode = ERR0; - /* Call this once just to count the brackets. */ - calculateCompiledPatternLength(pattern, patternLength, ignoreCase, cd, errorcode); - /* Call it again to compute the length. */ - int length = calculateCompiledPatternLength(pattern, patternLength, ignoreCase, cd, errorcode); - if (errorcode) - return returnError(errorcode, errorPtr); - - if (length > MAX_PATTERN_SIZE) - return returnError(ERR16, errorPtr); - - size_t size = length + sizeof(JSRegExp); -#if REGEXP_HISTOGRAM - size_t stringOffset = (size + sizeof(UChar) - 1) / sizeof(UChar) * sizeof(UChar); - size = stringOffset + patternLength * sizeof(UChar); -#endif - JSRegExp* re = reinterpret_cast_ptr<JSRegExp*>(new char[size]); - - if (!re) - return returnError(ERR13, errorPtr); - - re->options = (ignoreCase ? IgnoreCaseOption : 0) | (multiline ? MatchAcrossMultipleLinesOption : 0); - - /* The starting points of the name/number translation table and of the code are - passed around in the compile data block. */ - - const unsigned char* codeStart = (const unsigned char*)(re + 1); - - /* Set up a starting, non-extracting bracket, then compile the expression. On - error, errorcode will be set non-zero, so we don't need to look at the result - of the function here. */ - - const UChar* ptr = (const UChar*)pattern; - const UChar* patternEnd = pattern + patternLength; - unsigned char* code = const_cast<unsigned char*>(codeStart); - int firstByte, reqByte; - int bracketCount = 0; - if (!cd.needOuterBracket) - compileBranch(re->options, &bracketCount, &code, &ptr, patternEnd, &errorcode, &firstByte, &reqByte, cd); - else { - *code = OP_BRA; - compileBracket(re->options, &bracketCount, &code, &ptr, patternEnd, &errorcode, 0, &firstByte, &reqByte, cd); - } - re->topBracket = bracketCount; - re->topBackref = cd.topBackref; - - /* If not reached end of pattern on success, there's an excess bracket. */ - - if (errorcode == 0 && ptr < patternEnd) - errorcode = ERR10; - - /* Fill in the terminating state and check for disastrous overflow, but - if debugging, leave the test till after things are printed out. */ - - *code++ = OP_END; - - ASSERT(code - codeStart <= length); - if (code - codeStart > length) - errorcode = ERR7; - - /* Give an error if there's back reference to a non-existent capturing - subpattern. */ - - if (re->topBackref > re->topBracket) - errorcode = ERR15; - - /* Failed to compile, or error while post-processing */ - - if (errorcode != ERR0) { - delete [] reinterpret_cast<char*>(re); - return returnError(errorcode, errorPtr); - } - - /* If the anchored option was not passed, set the flag if we can determine that - the pattern is anchored by virtue of ^ characters or \A or anything else (such - as starting with .* when DOTALL is set). - - Otherwise, if we know what the first character has to be, save it, because that - speeds up unanchored matches no end. If not, see if we can set the - UseMultiLineFirstByteOptimizationOption flag. This is helpful for multiline matches when all branches - start with ^. and also when all branches start with .* for non-DOTALL matches. - */ - - if (cd.needOuterBracket ? bracketIsAnchored(codeStart) : branchIsAnchored(codeStart)) - re->options |= IsAnchoredOption; - else { - if (firstByte < 0) { - firstByte = (cd.needOuterBracket - ? bracketFindFirstAssertedCharacter(codeStart, false) - : branchFindFirstAssertedCharacter(codeStart, false)) - | ((re->options & IgnoreCaseOption) ? REQ_IGNORE_CASE : 0); - } - if (firstByte >= 0) { - int ch = firstByte & 255; - if (ch < 127) { - re->firstByte = ((firstByte & REQ_IGNORE_CASE) && flipCase(ch) == ch) ? ch : firstByte; - re->options |= UseFirstByteOptimizationOption; - } - } else { - if (cd.needOuterBracket ? bracketNeedsLineStart(codeStart, 0, cd.backrefMap) : branchNeedsLineStart(codeStart, 0, cd.backrefMap)) - re->options |= UseMultiLineFirstByteOptimizationOption; - } - } - - /* For an anchored pattern, we use the "required byte" only if it follows a - variable length item in the regex. Remove the caseless flag for non-caseable - bytes. */ - - if (reqByte >= 0 && (!(re->options & IsAnchoredOption) || (reqByte & REQ_VARY))) { - int ch = reqByte & 255; - if (ch < 127) { - re->reqByte = ((reqByte & REQ_IGNORE_CASE) && flipCase(ch) == ch) ? (reqByte & ~REQ_IGNORE_CASE) : reqByte; - re->options |= UseRequiredByteOptimizationOption; - } - } - -#if REGEXP_HISTOGRAM - re->stringOffset = stringOffset; - re->stringLength = patternLength; - memcpy(reinterpret_cast<char*>(re) + stringOffset, pattern, patternLength * 2); -#endif - - if (numSubpatterns) - *numSubpatterns = re->topBracket; - return re; -} - -void jsRegExpFree(JSRegExp* re) -{ - delete [] reinterpret_cast<char*>(re); -} |