--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/JavaScriptCore/pcre/pcre_compile.cpp Fri Sep 17 09:02:29 2010 +0300
@@ -0,0 +1,2707 @@
+/* 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>
+
+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<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);
+}