--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/JavaScriptCore/pcre/pcre_exec.cpp Fri Sep 17 09:02:29 2010 +0300
@@ -0,0 +1,2177 @@
+/* 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 jsRegExpExecute(), the externally visible function
+that does pattern matching using an NFA algorithm, following the rules from
+the JavaScript specification. There are also some supporting functions. */
+
+#include "config.h"
+#include "pcre_internal.h"
+
+#include <limits.h>
+#include <wtf/ASCIICType.h>
+#include <wtf/Vector.h>
+
+#if REGEXP_HISTOGRAM
+#include <wtf/DateMath.h>
+#include <runtime/UString.h>
+#endif
+
+using namespace WTF;
+
+#if COMPILER(GCC)
+#define USE_COMPUTED_GOTO_FOR_MATCH_RECURSION
+//#define USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
+#endif
+
+/* Avoid warnings on Windows. */
+#undef min
+#undef max
+
+#ifndef USE_COMPUTED_GOTO_FOR_MATCH_RECURSION
+typedef int ReturnLocation;
+#else
+typedef void* ReturnLocation;
+#endif
+
+#if !REGEXP_HISTOGRAM
+
+class HistogramTimeLogger {
+public:
+ HistogramTimeLogger(const JSRegExp*) { }
+};
+
+#else
+
+using namespace JSC;
+
+class Histogram {
+public:
+ ~Histogram();
+ void add(const JSRegExp*, double);
+
+private:
+ typedef HashMap<RefPtr<UString::Rep>, double> Map;
+ Map times;
+};
+
+class HistogramTimeLogger {
+public:
+ HistogramTimeLogger(const JSRegExp*);
+ ~HistogramTimeLogger();
+
+private:
+ const JSRegExp* m_re;
+ double m_startTime;
+};
+
+#endif
+
+/* Structure for building a chain of data for holding the values of
+the subject pointer at the start of each bracket, used to detect when
+an empty string has been matched by a bracket to break infinite loops. */
+struct BracketChainNode {
+ BracketChainNode* previousBracket;
+ const UChar* bracketStart;
+};
+
+struct MatchFrame : FastAllocBase {
+ ReturnLocation returnLocation;
+ struct MatchFrame* previousFrame;
+
+ /* Function arguments that may change */
+ struct {
+ const UChar* subjectPtr;
+ const unsigned char* instructionPtr;
+ int offsetTop;
+ BracketChainNode* bracketChain;
+ } args;
+
+
+ /* PCRE uses "fake" recursion built off of gotos, thus
+ stack-based local variables are not safe to use. Instead we have to
+ store local variables on the current MatchFrame. */
+ struct {
+ const unsigned char* data;
+ const unsigned char* startOfRepeatingBracket;
+ const UChar* subjectPtrAtStartOfInstruction; // Several instrutions stash away a subjectPtr here for later compare
+ const unsigned char* instructionPtrAtStartOfOnce;
+
+ int repeatOthercase;
+
+ int ctype;
+ int fc;
+ int fi;
+ int length;
+ int max;
+ int number;
+ int offset;
+ int saveOffset1;
+ int saveOffset2;
+ int saveOffset3;
+
+ BracketChainNode bracketChainNode;
+ } locals;
+};
+
+/* Structure for passing "static" information around between the functions
+doing traditional NFA matching, so that they are thread-safe. */
+
+struct MatchData {
+ int* offsetVector; /* Offset vector */
+ int offsetEnd; /* One past the end */
+ int offsetMax; /* The maximum usable for return data */
+ bool offsetOverflow; /* Set if too many extractions */
+ const UChar* startSubject; /* Start of the subject string */
+ const UChar* endSubject; /* End of the subject string */
+ const UChar* endMatchPtr; /* Subject position at end match */
+ int endOffsetTop; /* Highwater mark at end of match */
+ bool multiline;
+ bool ignoreCase;
+};
+
+/* The maximum remaining length of subject we are prepared to search for a
+reqByte match. */
+
+#define REQ_BYTE_MAX 1000
+
+/* The below limit restricts the number of "recursive" match calls in order to
+avoid spending exponential time on complex regular expressions. */
+
+static const unsigned matchLimit = 1000000;
+
+#ifdef DEBUG
+/*************************************************
+* Debugging function to print chars *
+*************************************************/
+
+/* Print a sequence of chars in printable format, stopping at the end of the
+subject if the requested.
+
+Arguments:
+ p points to characters
+ length number to print
+ isSubject true if printing from within md.startSubject
+ md pointer to matching data block, if isSubject is true
+*/
+
+static void pchars(const UChar* p, int length, bool isSubject, const MatchData& md)
+{
+ if (isSubject && length > md.endSubject - p)
+ length = md.endSubject - p;
+ while (length-- > 0) {
+ int c;
+ if (isASCIIPrintable(c = *(p++)))
+ printf("%c", c);
+ else if (c < 256)
+ printf("\\x%02x", c);
+ else
+ printf("\\x{%x}", c);
+ }
+}
+#endif
+
+/*************************************************
+* Match a back-reference *
+*************************************************/
+
+/* If a back reference hasn't been set, the length that is passed is greater
+than the number of characters left in the string, so the match fails.
+
+Arguments:
+ offset index into the offset vector
+ subjectPtr points into the subject
+ length length to be matched
+ md points to match data block
+
+Returns: true if matched
+*/
+
+static bool matchRef(int offset, const UChar* subjectPtr, int length, const MatchData& md)
+{
+ const UChar* p = md.startSubject + md.offsetVector[offset];
+
+#ifdef DEBUG
+ if (subjectPtr >= md.endSubject)
+ printf("matching subject <null>");
+ else {
+ printf("matching subject ");
+ pchars(subjectPtr, length, true, md);
+ }
+ printf(" against backref ");
+ pchars(p, length, false, md);
+ printf("\n");
+#endif
+
+ /* Always fail if not enough characters left */
+
+ if (length > md.endSubject - subjectPtr)
+ return false;
+
+ /* Separate the caselesss case for speed */
+
+ if (md.ignoreCase) {
+ while (length-- > 0) {
+ UChar c = *p++;
+ int othercase = jsc_pcre_ucp_othercase(c);
+ UChar d = *subjectPtr++;
+ if (c != d && othercase != d)
+ return false;
+ }
+ }
+ else {
+ while (length-- > 0)
+ if (*p++ != *subjectPtr++)
+ return false;
+ }
+
+ return true;
+}
+
+#ifndef USE_COMPUTED_GOTO_FOR_MATCH_RECURSION
+
+/* Use numbered labels and switch statement at the bottom of the match function. */
+
+#define RMATCH_WHERE(num) num
+#define RRETURN_LABEL RRETURN_SWITCH
+
+#else
+
+/* Use GCC's computed goto extension. */
+
+/* For one test case this is more than 40% faster than the switch statement.
+We could avoid the use of the num argument entirely by using local labels,
+but using it for the GCC case as well as the non-GCC case allows us to share
+a bit more code and notice if we use conflicting numbers.*/
+
+#define RMATCH_WHERE(num) &&RRETURN_##num
+#define RRETURN_LABEL *stack.currentFrame->returnLocation
+
+#endif
+
+#define RECURSIVE_MATCH_COMMON(num) \
+ goto RECURSE;\
+ RRETURN_##num: \
+ stack.popCurrentFrame();
+
+#define RECURSIVE_MATCH(num, ra, rb) \
+ do { \
+ stack.pushNewFrame((ra), (rb), RMATCH_WHERE(num)); \
+ RECURSIVE_MATCH_COMMON(num) \
+ } while (0)
+
+#define RECURSIVE_MATCH_NEW_GROUP(num, ra, rb) \
+ do { \
+ stack.pushNewFrame((ra), (rb), RMATCH_WHERE(num)); \
+ startNewGroup(stack.currentFrame); \
+ RECURSIVE_MATCH_COMMON(num) \
+ } while (0)
+
+#define RRETURN goto RRETURN_LABEL
+
+#define RRETURN_NO_MATCH do { isMatch = false; RRETURN; } while (0)
+
+/*************************************************
+* Match from current position *
+*************************************************/
+
+/* On entry instructionPtr points to the first opcode, and subjectPtr to the first character
+in the subject string, while substringStart holds the value of subjectPtr at the start of the
+last bracketed group - used for breaking infinite loops matching zero-length
+strings. This function is called recursively in many circumstances. Whenever it
+returns a negative (error) response, the outer match() call must also return the
+same response.
+
+Arguments:
+ subjectPtr pointer in subject
+ instructionPtr position in code
+ offsetTop current top pointer
+ md pointer to "static" info for the match
+
+Returns: 1 if matched ) these values are >= 0
+ 0 if failed to match )
+ a negative error value if aborted by an error condition
+ (e.g. stopped by repeated call or recursion limit)
+*/
+
+static const unsigned numFramesOnStack = 16;
+
+struct MatchStack {
+ MatchStack()
+ : framesEnd(frames + numFramesOnStack)
+ , currentFrame(frames)
+ , size(1) // match() creates accesses the first frame w/o calling pushNewFrame
+ {
+ ASSERT((sizeof(frames) / sizeof(frames[0])) == numFramesOnStack);
+ }
+
+ MatchFrame frames[numFramesOnStack];
+ MatchFrame* framesEnd;
+ MatchFrame* currentFrame;
+ unsigned size;
+
+ inline bool canUseStackBufferForNextFrame()
+ {
+ return size < numFramesOnStack;
+ }
+
+ inline MatchFrame* allocateNextFrame()
+ {
+ if (canUseStackBufferForNextFrame())
+ return currentFrame + 1;
+ return new MatchFrame;
+ }
+
+ inline void pushNewFrame(const unsigned char* instructionPtr, BracketChainNode* bracketChain, ReturnLocation returnLocation)
+ {
+ MatchFrame* newframe = allocateNextFrame();
+ newframe->previousFrame = currentFrame;
+
+ newframe->args.subjectPtr = currentFrame->args.subjectPtr;
+ newframe->args.offsetTop = currentFrame->args.offsetTop;
+ newframe->args.instructionPtr = instructionPtr;
+ newframe->args.bracketChain = bracketChain;
+ newframe->returnLocation = returnLocation;
+ size++;
+
+ currentFrame = newframe;
+ }
+
+ inline void popCurrentFrame()
+ {
+ MatchFrame* oldFrame = currentFrame;
+ currentFrame = currentFrame->previousFrame;
+ if (size > numFramesOnStack)
+ delete oldFrame;
+ size--;
+ }
+
+ void popAllFrames()
+ {
+ while (size)
+ popCurrentFrame();
+ }
+};
+
+static int matchError(int errorCode, MatchStack& stack)
+{
+ stack.popAllFrames();
+ return errorCode;
+}
+
+/* Get the next UTF-8 character, not advancing the pointer, incrementing length
+ if there are extra bytes. This is called when we know we are in UTF-8 mode. */
+
+static inline void getUTF8CharAndIncrementLength(int& c, const unsigned char* subjectPtr, int& len)
+{
+ c = *subjectPtr;
+ if ((c & 0xc0) == 0xc0) {
+ int gcaa = jsc_pcre_utf8_table4[c & 0x3f]; /* Number of additional bytes */
+ int gcss = 6 * gcaa;
+ c = (c & jsc_pcre_utf8_table3[gcaa]) << gcss;
+ for (int gcii = 1; gcii <= gcaa; gcii++) {
+ gcss -= 6;
+ c |= (subjectPtr[gcii] & 0x3f) << gcss;
+ }
+ len += gcaa;
+ }
+}
+
+static inline void startNewGroup(MatchFrame* currentFrame)
+{
+ /* At the start of a bracketed group, add the current subject pointer to the
+ stack of such pointers, to be re-instated at the end of the group when we hit
+ the closing ket. When match() is called in other circumstances, we don't add to
+ this stack. */
+
+ currentFrame->locals.bracketChainNode.previousBracket = currentFrame->args.bracketChain;
+ currentFrame->locals.bracketChainNode.bracketStart = currentFrame->args.subjectPtr;
+ currentFrame->args.bracketChain = ¤tFrame->locals.bracketChainNode;
+}
+
+// FIXME: "minimize" means "not greedy", we should invert the callers to ask for "greedy" to be less confusing
+static inline void repeatInformationFromInstructionOffset(int instructionOffset, bool& minimize, int& minimumRepeats, int& maximumRepeats)
+{
+ // Instruction offsets are based off of OP_CRSTAR, OP_STAR, OP_TYPESTAR, OP_NOTSTAR
+ static const char minimumRepeatsFromInstructionOffset[] = { 0, 0, 1, 1, 0, 0 };
+ static const int maximumRepeatsFromInstructionOffset[] = { INT_MAX, INT_MAX, INT_MAX, INT_MAX, 1, 1 };
+
+ ASSERT(instructionOffset >= 0);
+ ASSERT(instructionOffset <= (OP_CRMINQUERY - OP_CRSTAR));
+
+ minimize = (instructionOffset & 1); // this assumes ordering: Instruction, MinimizeInstruction, Instruction2, MinimizeInstruction2
+ minimumRepeats = minimumRepeatsFromInstructionOffset[instructionOffset];
+ maximumRepeats = maximumRepeatsFromInstructionOffset[instructionOffset];
+}
+
+static int match(const UChar* subjectPtr, const unsigned char* instructionPtr, int offsetTop, MatchData& md)
+{
+ bool isMatch = false;
+ int min;
+ bool minimize = false; /* Initialization not really needed, but some compilers think so. */
+ unsigned remainingMatchCount = matchLimit;
+ int othercase; /* Declare here to avoid errors during jumps */
+
+ MatchStack stack;
+
+ /* The opcode jump table. */
+#ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
+#define EMIT_JUMP_TABLE_ENTRY(opcode) &&LABEL_OP_##opcode,
+ static void* opcodeJumpTable[256] = { FOR_EACH_OPCODE(EMIT_JUMP_TABLE_ENTRY) };
+#undef EMIT_JUMP_TABLE_ENTRY
+#endif
+
+ /* One-time setup of the opcode jump table. */
+#ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
+ for (int i = 255; !opcodeJumpTable[i]; i--)
+ opcodeJumpTable[i] = &&CAPTURING_BRACKET;
+#endif
+
+#ifdef USE_COMPUTED_GOTO_FOR_MATCH_RECURSION
+ // Shark shows this as a hot line
+ // Using a static const here makes this line disappear, but makes later access hotter (not sure why)
+ stack.currentFrame->returnLocation = &&RETURN;
+#else
+ stack.currentFrame->returnLocation = 0;
+#endif
+ stack.currentFrame->args.subjectPtr = subjectPtr;
+ stack.currentFrame->args.instructionPtr = instructionPtr;
+ stack.currentFrame->args.offsetTop = offsetTop;
+ stack.currentFrame->args.bracketChain = 0;
+ startNewGroup(stack.currentFrame);
+
+ /* This is where control jumps back to to effect "recursion" */
+
+RECURSE:
+ if (!--remainingMatchCount)
+ return matchError(JSRegExpErrorHitLimit, stack);
+
+ /* Now start processing the operations. */
+
+#ifndef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
+ while (true)
+#endif
+ {
+
+#ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
+#define BEGIN_OPCODE(opcode) LABEL_OP_##opcode
+#define NEXT_OPCODE goto *opcodeJumpTable[*stack.currentFrame->args.instructionPtr]
+#else
+#define BEGIN_OPCODE(opcode) case OP_##opcode
+#define NEXT_OPCODE continue
+#endif
+
+#ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
+ NEXT_OPCODE;
+#else
+ switch (*stack.currentFrame->args.instructionPtr)
+#endif
+ {
+ /* Non-capturing bracket: optimized */
+
+ BEGIN_OPCODE(BRA):
+ NON_CAPTURING_BRACKET:
+ DPRINTF(("start bracket 0\n"));
+ do {
+ RECURSIVE_MATCH_NEW_GROUP(2, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ stack.currentFrame->args.instructionPtr += getLinkValue(stack.currentFrame->args.instructionPtr + 1);
+ } while (*stack.currentFrame->args.instructionPtr == OP_ALT);
+ DPRINTF(("bracket 0 failed\n"));
+ RRETURN;
+
+ /* Skip over large extraction number data if encountered. */
+
+ BEGIN_OPCODE(BRANUMBER):
+ stack.currentFrame->args.instructionPtr += 3;
+ NEXT_OPCODE;
+
+ /* End of the pattern. */
+
+ BEGIN_OPCODE(END):
+ md.endMatchPtr = stack.currentFrame->args.subjectPtr; /* Record where we ended */
+ md.endOffsetTop = stack.currentFrame->args.offsetTop; /* and how many extracts were taken */
+ isMatch = true;
+ RRETURN;
+
+ /* Assertion brackets. Check the alternative branches in turn - the
+ matching won't pass the KET for an assertion. If any one branch matches,
+ the assertion is true. Lookbehind assertions have an OP_REVERSE item at the
+ start of each branch to move the current point backwards, so the code at
+ this level is identical to the lookahead case. */
+
+ BEGIN_OPCODE(ASSERT):
+ do {
+ RECURSIVE_MATCH_NEW_GROUP(6, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, NULL);
+ if (isMatch)
+ break;
+ stack.currentFrame->args.instructionPtr += getLinkValue(stack.currentFrame->args.instructionPtr + 1);
+ } while (*stack.currentFrame->args.instructionPtr == OP_ALT);
+ if (*stack.currentFrame->args.instructionPtr == OP_KET)
+ RRETURN_NO_MATCH;
+
+ /* Continue from after the assertion, updating the offsets high water
+ mark, since extracts may have been taken during the assertion. */
+
+ advanceToEndOfBracket(stack.currentFrame->args.instructionPtr);
+ stack.currentFrame->args.instructionPtr += 1 + LINK_SIZE;
+ stack.currentFrame->args.offsetTop = md.endOffsetTop;
+ NEXT_OPCODE;
+
+ /* Negative assertion: all branches must fail to match */
+
+ BEGIN_OPCODE(ASSERT_NOT):
+ do {
+ RECURSIVE_MATCH_NEW_GROUP(7, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, NULL);
+ if (isMatch)
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr += getLinkValue(stack.currentFrame->args.instructionPtr + 1);
+ } while (*stack.currentFrame->args.instructionPtr == OP_ALT);
+
+ stack.currentFrame->args.instructionPtr += 1 + LINK_SIZE;
+ NEXT_OPCODE;
+
+ /* An alternation is the end of a branch; scan along to find the end of the
+ bracketed group and go to there. */
+
+ BEGIN_OPCODE(ALT):
+ advanceToEndOfBracket(stack.currentFrame->args.instructionPtr);
+ NEXT_OPCODE;
+
+ /* BRAZERO and BRAMINZERO occur just before a bracket group, indicating
+ that it may occur zero times. It may repeat infinitely, or not at all -
+ i.e. it could be ()* or ()? in the pattern. Brackets with fixed upper
+ repeat limits are compiled as a number of copies, with the optional ones
+ preceded by BRAZERO or BRAMINZERO. */
+
+ BEGIN_OPCODE(BRAZERO): {
+ stack.currentFrame->locals.startOfRepeatingBracket = stack.currentFrame->args.instructionPtr + 1;
+ RECURSIVE_MATCH_NEW_GROUP(14, stack.currentFrame->locals.startOfRepeatingBracket, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ advanceToEndOfBracket(stack.currentFrame->locals.startOfRepeatingBracket);
+ stack.currentFrame->args.instructionPtr = stack.currentFrame->locals.startOfRepeatingBracket + 1 + LINK_SIZE;
+ NEXT_OPCODE;
+ }
+
+ BEGIN_OPCODE(BRAMINZERO): {
+ stack.currentFrame->locals.startOfRepeatingBracket = stack.currentFrame->args.instructionPtr + 1;
+ advanceToEndOfBracket(stack.currentFrame->locals.startOfRepeatingBracket);
+ RECURSIVE_MATCH_NEW_GROUP(15, stack.currentFrame->locals.startOfRepeatingBracket + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+ }
+
+ /* End of a group, repeated or non-repeating. If we are at the end of
+ an assertion "group", stop matching and return 1, but record the
+ current high water mark for use by positive assertions. Do this also
+ for the "once" (not-backup up) groups. */
+
+ BEGIN_OPCODE(KET):
+ BEGIN_OPCODE(KETRMIN):
+ BEGIN_OPCODE(KETRMAX):
+ stack.currentFrame->locals.instructionPtrAtStartOfOnce = stack.currentFrame->args.instructionPtr - getLinkValue(stack.currentFrame->args.instructionPtr + 1);
+ stack.currentFrame->locals.subjectPtrAtStartOfInstruction = stack.currentFrame->args.bracketChain->bracketStart;
+
+ /* Back up the stack of bracket start pointers. */
+
+ stack.currentFrame->args.bracketChain = stack.currentFrame->args.bracketChain->previousBracket;
+
+ if (*stack.currentFrame->locals.instructionPtrAtStartOfOnce == OP_ASSERT || *stack.currentFrame->locals.instructionPtrAtStartOfOnce == OP_ASSERT_NOT) {
+ md.endOffsetTop = stack.currentFrame->args.offsetTop;
+ isMatch = true;
+ RRETURN;
+ }
+
+ /* In all other cases except a conditional group we have to check the
+ group number back at the start and if necessary complete handling an
+ extraction by setting the offsets and bumping the high water mark. */
+
+ stack.currentFrame->locals.number = *stack.currentFrame->locals.instructionPtrAtStartOfOnce - OP_BRA;
+
+ /* For extended extraction brackets (large number), we have to fish out
+ the number from a dummy opcode at the start. */
+
+ if (stack.currentFrame->locals.number > EXTRACT_BASIC_MAX)
+ stack.currentFrame->locals.number = get2ByteValue(stack.currentFrame->locals.instructionPtrAtStartOfOnce + 2 + LINK_SIZE);
+ stack.currentFrame->locals.offset = stack.currentFrame->locals.number << 1;
+
+#ifdef DEBUG
+ printf("end bracket %d", stack.currentFrame->locals.number);
+ printf("\n");
+#endif
+
+ /* Test for a numbered group. This includes groups called as a result
+ of recursion. Note that whole-pattern recursion is coded as a recurse
+ into group 0, so it won't be picked up here. Instead, we catch it when
+ the OP_END is reached. */
+
+ if (stack.currentFrame->locals.number > 0) {
+ if (stack.currentFrame->locals.offset >= md.offsetMax)
+ md.offsetOverflow = true;
+ else {
+ md.offsetVector[stack.currentFrame->locals.offset] =
+ md.offsetVector[md.offsetEnd - stack.currentFrame->locals.number];
+ md.offsetVector[stack.currentFrame->locals.offset+1] = stack.currentFrame->args.subjectPtr - md.startSubject;
+ if (stack.currentFrame->args.offsetTop <= stack.currentFrame->locals.offset)
+ stack.currentFrame->args.offsetTop = stack.currentFrame->locals.offset + 2;
+ }
+ }
+
+ /* For a non-repeating ket, just continue at this level. This also
+ happens for a repeating ket if no characters were matched in the group.
+ This is the forcible breaking of infinite loops as implemented in Perl
+ 5.005. If there is an options reset, it will get obeyed in the normal
+ course of events. */
+
+ if (*stack.currentFrame->args.instructionPtr == OP_KET || stack.currentFrame->args.subjectPtr == stack.currentFrame->locals.subjectPtrAtStartOfInstruction) {
+ stack.currentFrame->args.instructionPtr += 1 + LINK_SIZE;
+ NEXT_OPCODE;
+ }
+
+ /* The repeating kets try the rest of the pattern or restart from the
+ preceding bracket, in the appropriate order. */
+
+ if (*stack.currentFrame->args.instructionPtr == OP_KETRMIN) {
+ RECURSIVE_MATCH(16, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ RECURSIVE_MATCH_NEW_GROUP(17, stack.currentFrame->locals.instructionPtrAtStartOfOnce, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ } else { /* OP_KETRMAX */
+ RECURSIVE_MATCH_NEW_GROUP(18, stack.currentFrame->locals.instructionPtrAtStartOfOnce, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ RECURSIVE_MATCH(19, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ }
+ RRETURN;
+
+ /* Start of subject. */
+
+ BEGIN_OPCODE(CIRC):
+ if (stack.currentFrame->args.subjectPtr != md.startSubject)
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+
+ /* After internal newline if multiline. */
+
+ BEGIN_OPCODE(BOL):
+ if (stack.currentFrame->args.subjectPtr != md.startSubject && !isNewline(stack.currentFrame->args.subjectPtr[-1]))
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+
+ /* End of subject. */
+
+ BEGIN_OPCODE(DOLL):
+ if (stack.currentFrame->args.subjectPtr < md.endSubject)
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+
+ /* Before internal newline if multiline. */
+
+ BEGIN_OPCODE(EOL):
+ if (stack.currentFrame->args.subjectPtr < md.endSubject && !isNewline(*stack.currentFrame->args.subjectPtr))
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+
+ /* Word boundary assertions */
+
+ BEGIN_OPCODE(NOT_WORD_BOUNDARY):
+ BEGIN_OPCODE(WORD_BOUNDARY): {
+ bool currentCharIsWordChar = false;
+ bool previousCharIsWordChar = false;
+
+ if (stack.currentFrame->args.subjectPtr > md.startSubject)
+ previousCharIsWordChar = isWordChar(stack.currentFrame->args.subjectPtr[-1]);
+ if (stack.currentFrame->args.subjectPtr < md.endSubject)
+ currentCharIsWordChar = isWordChar(*stack.currentFrame->args.subjectPtr);
+
+ /* Now see if the situation is what we want */
+ bool wordBoundaryDesired = (*stack.currentFrame->args.instructionPtr++ == OP_WORD_BOUNDARY);
+ if (wordBoundaryDesired ? currentCharIsWordChar == previousCharIsWordChar : currentCharIsWordChar != previousCharIsWordChar)
+ RRETURN_NO_MATCH;
+ NEXT_OPCODE;
+ }
+
+ /* Match a single character type; inline for speed */
+
+ BEGIN_OPCODE(NOT_NEWLINE):
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ if (isNewline(*stack.currentFrame->args.subjectPtr++))
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+
+ BEGIN_OPCODE(NOT_DIGIT):
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ if (isASCIIDigit(*stack.currentFrame->args.subjectPtr++))
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+
+ BEGIN_OPCODE(DIGIT):
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ if (!isASCIIDigit(*stack.currentFrame->args.subjectPtr++))
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+
+ BEGIN_OPCODE(NOT_WHITESPACE):
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ if (isSpaceChar(*stack.currentFrame->args.subjectPtr++))
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+
+ BEGIN_OPCODE(WHITESPACE):
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ if (!isSpaceChar(*stack.currentFrame->args.subjectPtr++))
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+
+ BEGIN_OPCODE(NOT_WORDCHAR):
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ if (isWordChar(*stack.currentFrame->args.subjectPtr++))
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+
+ BEGIN_OPCODE(WORDCHAR):
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ if (!isWordChar(*stack.currentFrame->args.subjectPtr++))
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr++;
+ NEXT_OPCODE;
+
+ /* Match a back reference, possibly repeatedly. Look past the end of the
+ item to see if there is repeat information following. The code is similar
+ to that for character classes, but repeated for efficiency. Then obey
+ similar code to character type repeats - written out again for speed.
+ However, if the referenced string is the empty string, always treat
+ it as matched, any number of times (otherwise there could be infinite
+ loops). */
+
+ BEGIN_OPCODE(REF):
+ stack.currentFrame->locals.offset = get2ByteValue(stack.currentFrame->args.instructionPtr + 1) << 1; /* Doubled ref number */
+ stack.currentFrame->args.instructionPtr += 3; /* Advance past item */
+
+ /* If the reference is unset, set the length to be longer than the amount
+ of subject left; this ensures that every attempt at a match fails. We
+ can't just fail here, because of the possibility of quantifiers with zero
+ minima. */
+
+ if (stack.currentFrame->locals.offset >= stack.currentFrame->args.offsetTop || md.offsetVector[stack.currentFrame->locals.offset] < 0)
+ stack.currentFrame->locals.length = 0;
+ else
+ stack.currentFrame->locals.length = md.offsetVector[stack.currentFrame->locals.offset+1] - md.offsetVector[stack.currentFrame->locals.offset];
+
+ /* Set up for repetition, or handle the non-repeated case */
+
+ switch (*stack.currentFrame->args.instructionPtr) {
+ case OP_CRSTAR:
+ case OP_CRMINSTAR:
+ case OP_CRPLUS:
+ case OP_CRMINPLUS:
+ case OP_CRQUERY:
+ case OP_CRMINQUERY:
+ repeatInformationFromInstructionOffset(*stack.currentFrame->args.instructionPtr++ - OP_CRSTAR, minimize, min, stack.currentFrame->locals.max);
+ break;
+
+ case OP_CRRANGE:
+ case OP_CRMINRANGE:
+ minimize = (*stack.currentFrame->args.instructionPtr == OP_CRMINRANGE);
+ min = get2ByteValue(stack.currentFrame->args.instructionPtr + 1);
+ stack.currentFrame->locals.max = get2ByteValue(stack.currentFrame->args.instructionPtr + 3);
+ if (stack.currentFrame->locals.max == 0)
+ stack.currentFrame->locals.max = INT_MAX;
+ stack.currentFrame->args.instructionPtr += 5;
+ break;
+
+ default: /* No repeat follows */
+ if (!matchRef(stack.currentFrame->locals.offset, stack.currentFrame->args.subjectPtr, stack.currentFrame->locals.length, md))
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.subjectPtr += stack.currentFrame->locals.length;
+ NEXT_OPCODE;
+ }
+
+ /* If the length of the reference is zero, just continue with the
+ main loop. */
+
+ if (stack.currentFrame->locals.length == 0)
+ NEXT_OPCODE;
+
+ /* First, ensure the minimum number of matches are present. */
+
+ for (int i = 1; i <= min; i++) {
+ if (!matchRef(stack.currentFrame->locals.offset, stack.currentFrame->args.subjectPtr, stack.currentFrame->locals.length, md))
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.subjectPtr += stack.currentFrame->locals.length;
+ }
+
+ /* If min = max, continue at the same level without recursion.
+ They are not both allowed to be zero. */
+
+ if (min == stack.currentFrame->locals.max)
+ NEXT_OPCODE;
+
+ /* If minimizing, keep trying and advancing the pointer */
+
+ if (minimize) {
+ for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
+ RECURSIVE_MATCH(20, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ if (stack.currentFrame->locals.fi >= stack.currentFrame->locals.max || !matchRef(stack.currentFrame->locals.offset, stack.currentFrame->args.subjectPtr, stack.currentFrame->locals.length, md))
+ RRETURN;
+ stack.currentFrame->args.subjectPtr += stack.currentFrame->locals.length;
+ }
+ /* Control never reaches here */
+ }
+
+ /* If maximizing, find the longest string and work backwards */
+
+ else {
+ stack.currentFrame->locals.subjectPtrAtStartOfInstruction = stack.currentFrame->args.subjectPtr;
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (!matchRef(stack.currentFrame->locals.offset, stack.currentFrame->args.subjectPtr, stack.currentFrame->locals.length, md))
+ break;
+ stack.currentFrame->args.subjectPtr += stack.currentFrame->locals.length;
+ }
+ while (stack.currentFrame->args.subjectPtr >= stack.currentFrame->locals.subjectPtrAtStartOfInstruction) {
+ RECURSIVE_MATCH(21, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ stack.currentFrame->args.subjectPtr -= stack.currentFrame->locals.length;
+ }
+ RRETURN_NO_MATCH;
+ }
+ /* Control never reaches here */
+
+ /* Match a bit-mapped character class, possibly repeatedly. This op code is
+ used when all the characters in the class have values in the range 0-255,
+ and either the matching is caseful, or the characters are in the range
+ 0-127 when UTF-8 processing is enabled. The only difference between
+ OP_CLASS and OP_NCLASS occurs when a data character outside the range is
+ encountered.
+
+ First, look past the end of the item to see if there is repeat information
+ following. Then obey similar code to character type repeats - written out
+ again for speed. */
+
+ BEGIN_OPCODE(NCLASS):
+ BEGIN_OPCODE(CLASS):
+ stack.currentFrame->locals.data = stack.currentFrame->args.instructionPtr + 1; /* Save for matching */
+ stack.currentFrame->args.instructionPtr += 33; /* Advance past the item */
+
+ switch (*stack.currentFrame->args.instructionPtr) {
+ case OP_CRSTAR:
+ case OP_CRMINSTAR:
+ case OP_CRPLUS:
+ case OP_CRMINPLUS:
+ case OP_CRQUERY:
+ case OP_CRMINQUERY:
+ repeatInformationFromInstructionOffset(*stack.currentFrame->args.instructionPtr++ - OP_CRSTAR, minimize, min, stack.currentFrame->locals.max);
+ break;
+
+ case OP_CRRANGE:
+ case OP_CRMINRANGE:
+ minimize = (*stack.currentFrame->args.instructionPtr == OP_CRMINRANGE);
+ min = get2ByteValue(stack.currentFrame->args.instructionPtr + 1);
+ stack.currentFrame->locals.max = get2ByteValue(stack.currentFrame->args.instructionPtr + 3);
+ if (stack.currentFrame->locals.max == 0)
+ stack.currentFrame->locals.max = INT_MAX;
+ stack.currentFrame->args.instructionPtr += 5;
+ break;
+
+ default: /* No repeat follows */
+ min = stack.currentFrame->locals.max = 1;
+ break;
+ }
+
+ /* First, ensure the minimum number of matches are present. */
+
+ for (int i = 1; i <= min; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ int c = *stack.currentFrame->args.subjectPtr++;
+ if (c > 255) {
+ if (stack.currentFrame->locals.data[-1] == OP_CLASS)
+ RRETURN_NO_MATCH;
+ } else {
+ if (!(stack.currentFrame->locals.data[c / 8] & (1 << (c & 7))))
+ RRETURN_NO_MATCH;
+ }
+ }
+
+ /* If max == min we can continue with the main loop without the
+ need to recurse. */
+
+ if (min == stack.currentFrame->locals.max)
+ NEXT_OPCODE;
+
+ /* If minimizing, keep testing the rest of the expression and advancing
+ the pointer while it matches the class. */
+ if (minimize) {
+ for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
+ RECURSIVE_MATCH(22, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ if (stack.currentFrame->locals.fi >= stack.currentFrame->locals.max || stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN;
+ int c = *stack.currentFrame->args.subjectPtr++;
+ if (c > 255) {
+ if (stack.currentFrame->locals.data[-1] == OP_CLASS)
+ RRETURN;
+ } else {
+ if ((stack.currentFrame->locals.data[c/8] & (1 << (c&7))) == 0)
+ RRETURN;
+ }
+ }
+ /* Control never reaches here */
+ }
+ /* If maximizing, find the longest possible run, then work backwards. */
+ else {
+ stack.currentFrame->locals.subjectPtrAtStartOfInstruction = stack.currentFrame->args.subjectPtr;
+
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ break;
+ int c = *stack.currentFrame->args.subjectPtr;
+ if (c > 255) {
+ if (stack.currentFrame->locals.data[-1] == OP_CLASS)
+ break;
+ } else {
+ if (!(stack.currentFrame->locals.data[c / 8] & (1 << (c & 7))))
+ break;
+ }
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ for (;;) {
+ RECURSIVE_MATCH(24, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ if (stack.currentFrame->args.subjectPtr-- == stack.currentFrame->locals.subjectPtrAtStartOfInstruction)
+ break; /* Stop if tried at original pos */
+ }
+
+ RRETURN;
+ }
+ /* Control never reaches here */
+
+ /* Match an extended character class. */
+
+ BEGIN_OPCODE(XCLASS):
+ stack.currentFrame->locals.data = stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE; /* Save for matching */
+ stack.currentFrame->args.instructionPtr += getLinkValue(stack.currentFrame->args.instructionPtr + 1); /* Advance past the item */
+
+ switch (*stack.currentFrame->args.instructionPtr) {
+ case OP_CRSTAR:
+ case OP_CRMINSTAR:
+ case OP_CRPLUS:
+ case OP_CRMINPLUS:
+ case OP_CRQUERY:
+ case OP_CRMINQUERY:
+ repeatInformationFromInstructionOffset(*stack.currentFrame->args.instructionPtr++ - OP_CRSTAR, minimize, min, stack.currentFrame->locals.max);
+ break;
+
+ case OP_CRRANGE:
+ case OP_CRMINRANGE:
+ minimize = (*stack.currentFrame->args.instructionPtr == OP_CRMINRANGE);
+ min = get2ByteValue(stack.currentFrame->args.instructionPtr + 1);
+ stack.currentFrame->locals.max = get2ByteValue(stack.currentFrame->args.instructionPtr + 3);
+ if (stack.currentFrame->locals.max == 0)
+ stack.currentFrame->locals.max = INT_MAX;
+ stack.currentFrame->args.instructionPtr += 5;
+ break;
+
+ default: /* No repeat follows */
+ min = stack.currentFrame->locals.max = 1;
+ }
+
+ /* First, ensure the minimum number of matches are present. */
+
+ for (int i = 1; i <= min; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ int c = *stack.currentFrame->args.subjectPtr++;
+ if (!jsc_pcre_xclass(c, stack.currentFrame->locals.data))
+ RRETURN_NO_MATCH;
+ }
+
+ /* If max == min we can continue with the main loop without the
+ need to recurse. */
+
+ if (min == stack.currentFrame->locals.max)
+ NEXT_OPCODE;
+
+ /* If minimizing, keep testing the rest of the expression and advancing
+ the pointer while it matches the class. */
+
+ if (minimize) {
+ for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
+ RECURSIVE_MATCH(26, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ if (stack.currentFrame->locals.fi >= stack.currentFrame->locals.max || stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN;
+ int c = *stack.currentFrame->args.subjectPtr++;
+ if (!jsc_pcre_xclass(c, stack.currentFrame->locals.data))
+ RRETURN;
+ }
+ /* Control never reaches here */
+ }
+
+ /* If maximizing, find the longest possible run, then work backwards. */
+
+ else {
+ stack.currentFrame->locals.subjectPtrAtStartOfInstruction = stack.currentFrame->args.subjectPtr;
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ break;
+ int c = *stack.currentFrame->args.subjectPtr;
+ if (!jsc_pcre_xclass(c, stack.currentFrame->locals.data))
+ break;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ for(;;) {
+ RECURSIVE_MATCH(27, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ if (stack.currentFrame->args.subjectPtr-- == stack.currentFrame->locals.subjectPtrAtStartOfInstruction)
+ break; /* Stop if tried at original pos */
+ }
+ RRETURN;
+ }
+
+ /* Control never reaches here */
+
+ /* Match a single character, casefully */
+
+ BEGIN_OPCODE(CHAR):
+ stack.currentFrame->locals.length = 1;
+ stack.currentFrame->args.instructionPtr++;
+ getUTF8CharAndIncrementLength(stack.currentFrame->locals.fc, stack.currentFrame->args.instructionPtr, stack.currentFrame->locals.length);
+ stack.currentFrame->args.instructionPtr += stack.currentFrame->locals.length;
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ if (stack.currentFrame->locals.fc != *stack.currentFrame->args.subjectPtr++)
+ RRETURN_NO_MATCH;
+ NEXT_OPCODE;
+
+ /* Match a single character, caselessly */
+
+ BEGIN_OPCODE(CHAR_IGNORING_CASE): {
+ stack.currentFrame->locals.length = 1;
+ stack.currentFrame->args.instructionPtr++;
+ getUTF8CharAndIncrementLength(stack.currentFrame->locals.fc, stack.currentFrame->args.instructionPtr, stack.currentFrame->locals.length);
+ stack.currentFrame->args.instructionPtr += stack.currentFrame->locals.length;
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ int dc = *stack.currentFrame->args.subjectPtr++;
+ if (stack.currentFrame->locals.fc != dc && jsc_pcre_ucp_othercase(stack.currentFrame->locals.fc) != dc)
+ RRETURN_NO_MATCH;
+ NEXT_OPCODE;
+ }
+
+ /* Match a single ASCII character. */
+
+ BEGIN_OPCODE(ASCII_CHAR):
+ if (md.endSubject == stack.currentFrame->args.subjectPtr)
+ RRETURN_NO_MATCH;
+ if (*stack.currentFrame->args.subjectPtr != stack.currentFrame->args.instructionPtr[1])
+ RRETURN_NO_MATCH;
+ ++stack.currentFrame->args.subjectPtr;
+ stack.currentFrame->args.instructionPtr += 2;
+ NEXT_OPCODE;
+
+ /* Match one of two cases of an ASCII letter. */
+
+ BEGIN_OPCODE(ASCII_LETTER_IGNORING_CASE):
+ if (md.endSubject == stack.currentFrame->args.subjectPtr)
+ RRETURN_NO_MATCH;
+ if ((*stack.currentFrame->args.subjectPtr | 0x20) != stack.currentFrame->args.instructionPtr[1])
+ RRETURN_NO_MATCH;
+ ++stack.currentFrame->args.subjectPtr;
+ stack.currentFrame->args.instructionPtr += 2;
+ NEXT_OPCODE;
+
+ /* Match a single character repeatedly; different opcodes share code. */
+
+ BEGIN_OPCODE(EXACT):
+ min = stack.currentFrame->locals.max = get2ByteValue(stack.currentFrame->args.instructionPtr + 1);
+ minimize = false;
+ stack.currentFrame->args.instructionPtr += 3;
+ goto REPEATCHAR;
+
+ BEGIN_OPCODE(UPTO):
+ BEGIN_OPCODE(MINUPTO):
+ min = 0;
+ stack.currentFrame->locals.max = get2ByteValue(stack.currentFrame->args.instructionPtr + 1);
+ minimize = *stack.currentFrame->args.instructionPtr == OP_MINUPTO;
+ stack.currentFrame->args.instructionPtr += 3;
+ goto REPEATCHAR;
+
+ BEGIN_OPCODE(STAR):
+ BEGIN_OPCODE(MINSTAR):
+ BEGIN_OPCODE(PLUS):
+ BEGIN_OPCODE(MINPLUS):
+ BEGIN_OPCODE(QUERY):
+ BEGIN_OPCODE(MINQUERY):
+ repeatInformationFromInstructionOffset(*stack.currentFrame->args.instructionPtr++ - OP_STAR, minimize, min, stack.currentFrame->locals.max);
+
+ /* Common code for all repeated single-character matches. We can give
+ up quickly if there are fewer than the minimum number of characters left in
+ the subject. */
+
+ REPEATCHAR:
+
+ stack.currentFrame->locals.length = 1;
+ getUTF8CharAndIncrementLength(stack.currentFrame->locals.fc, stack.currentFrame->args.instructionPtr, stack.currentFrame->locals.length);
+ if (min * (stack.currentFrame->locals.fc > 0xFFFF ? 2 : 1) > md.endSubject - stack.currentFrame->args.subjectPtr)
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.instructionPtr += stack.currentFrame->locals.length;
+
+ if (stack.currentFrame->locals.fc <= 0xFFFF) {
+ othercase = md.ignoreCase ? jsc_pcre_ucp_othercase(stack.currentFrame->locals.fc) : -1;
+
+ for (int i = 1; i <= min; i++) {
+ if (*stack.currentFrame->args.subjectPtr != stack.currentFrame->locals.fc && *stack.currentFrame->args.subjectPtr != othercase)
+ RRETURN_NO_MATCH;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+
+ if (min == stack.currentFrame->locals.max)
+ NEXT_OPCODE;
+
+ if (minimize) {
+ stack.currentFrame->locals.repeatOthercase = othercase;
+ for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
+ RECURSIVE_MATCH(28, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ if (stack.currentFrame->locals.fi >= stack.currentFrame->locals.max || stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN;
+ if (*stack.currentFrame->args.subjectPtr != stack.currentFrame->locals.fc && *stack.currentFrame->args.subjectPtr != stack.currentFrame->locals.repeatOthercase)
+ RRETURN;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ /* Control never reaches here */
+ } else {
+ stack.currentFrame->locals.subjectPtrAtStartOfInstruction = stack.currentFrame->args.subjectPtr;
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ break;
+ if (*stack.currentFrame->args.subjectPtr != stack.currentFrame->locals.fc && *stack.currentFrame->args.subjectPtr != othercase)
+ break;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ while (stack.currentFrame->args.subjectPtr >= stack.currentFrame->locals.subjectPtrAtStartOfInstruction) {
+ RECURSIVE_MATCH(29, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ --stack.currentFrame->args.subjectPtr;
+ }
+ RRETURN_NO_MATCH;
+ }
+ /* Control never reaches here */
+ } else {
+ /* No case on surrogate pairs, so no need to bother with "othercase". */
+
+ for (int i = 1; i <= min; i++) {
+ if (*stack.currentFrame->args.subjectPtr != stack.currentFrame->locals.fc)
+ RRETURN_NO_MATCH;
+ stack.currentFrame->args.subjectPtr += 2;
+ }
+
+ if (min == stack.currentFrame->locals.max)
+ NEXT_OPCODE;
+
+ if (minimize) {
+ for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
+ RECURSIVE_MATCH(30, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ if (stack.currentFrame->locals.fi >= stack.currentFrame->locals.max || stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN;
+ if (*stack.currentFrame->args.subjectPtr != stack.currentFrame->locals.fc)
+ RRETURN;
+ stack.currentFrame->args.subjectPtr += 2;
+ }
+ /* Control never reaches here */
+ } else {
+ stack.currentFrame->locals.subjectPtrAtStartOfInstruction = stack.currentFrame->args.subjectPtr;
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr > md.endSubject - 2)
+ break;
+ if (*stack.currentFrame->args.subjectPtr != stack.currentFrame->locals.fc)
+ break;
+ stack.currentFrame->args.subjectPtr += 2;
+ }
+ while (stack.currentFrame->args.subjectPtr >= stack.currentFrame->locals.subjectPtrAtStartOfInstruction) {
+ RECURSIVE_MATCH(31, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ stack.currentFrame->args.subjectPtr -= 2;
+ }
+ RRETURN_NO_MATCH;
+ }
+ /* Control never reaches here */
+ }
+ /* Control never reaches here */
+
+ /* Match a negated single one-byte character. */
+
+ BEGIN_OPCODE(NOT): {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN_NO_MATCH;
+ int b = stack.currentFrame->args.instructionPtr[1];
+ int c = *stack.currentFrame->args.subjectPtr++;
+ stack.currentFrame->args.instructionPtr += 2;
+ if (md.ignoreCase) {
+ if (c < 128)
+ c = toLowerCase(c);
+ if (toLowerCase(b) == c)
+ RRETURN_NO_MATCH;
+ } else {
+ if (b == c)
+ RRETURN_NO_MATCH;
+ }
+ NEXT_OPCODE;
+ }
+
+ /* Match a negated single one-byte character repeatedly. This is almost a
+ repeat of the code for a repeated single character, but I haven't found a
+ nice way of commoning these up that doesn't require a test of the
+ positive/negative option for each character match. Maybe that wouldn't add
+ very much to the time taken, but character matching *is* what this is all
+ about... */
+
+ BEGIN_OPCODE(NOTEXACT):
+ min = stack.currentFrame->locals.max = get2ByteValue(stack.currentFrame->args.instructionPtr + 1);
+ minimize = false;
+ stack.currentFrame->args.instructionPtr += 3;
+ goto REPEATNOTCHAR;
+
+ BEGIN_OPCODE(NOTUPTO):
+ BEGIN_OPCODE(NOTMINUPTO):
+ min = 0;
+ stack.currentFrame->locals.max = get2ByteValue(stack.currentFrame->args.instructionPtr + 1);
+ minimize = *stack.currentFrame->args.instructionPtr == OP_NOTMINUPTO;
+ stack.currentFrame->args.instructionPtr += 3;
+ goto REPEATNOTCHAR;
+
+ BEGIN_OPCODE(NOTSTAR):
+ BEGIN_OPCODE(NOTMINSTAR):
+ BEGIN_OPCODE(NOTPLUS):
+ BEGIN_OPCODE(NOTMINPLUS):
+ BEGIN_OPCODE(NOTQUERY):
+ BEGIN_OPCODE(NOTMINQUERY):
+ repeatInformationFromInstructionOffset(*stack.currentFrame->args.instructionPtr++ - OP_NOTSTAR, minimize, min, stack.currentFrame->locals.max);
+
+ /* Common code for all repeated single-byte matches. We can give up quickly
+ if there are fewer than the minimum number of bytes left in the
+ subject. */
+
+ REPEATNOTCHAR:
+ if (min > md.endSubject - stack.currentFrame->args.subjectPtr)
+ RRETURN_NO_MATCH;
+ stack.currentFrame->locals.fc = *stack.currentFrame->args.instructionPtr++;
+
+ /* The code is duplicated for the caseless and caseful cases, for speed,
+ since matching characters is likely to be quite common. First, ensure the
+ minimum number of matches are present. If min = max, continue at the same
+ level without recursing. Otherwise, if minimizing, keep trying the rest of
+ the expression and advancing one matching character if failing, up to the
+ maximum. Alternatively, if maximizing, find the maximum number of
+ characters and work backwards. */
+
+ DPRINTF(("negative matching %c{%d,%d}\n", stack.currentFrame->locals.fc, min, stack.currentFrame->locals.max));
+
+ if (md.ignoreCase) {
+ if (stack.currentFrame->locals.fc < 128)
+ stack.currentFrame->locals.fc = toLowerCase(stack.currentFrame->locals.fc);
+
+ for (int i = 1; i <= min; i++) {
+ int d = *stack.currentFrame->args.subjectPtr++;
+ if (d < 128)
+ d = toLowerCase(d);
+ if (stack.currentFrame->locals.fc == d)
+ RRETURN_NO_MATCH;
+ }
+
+ if (min == stack.currentFrame->locals.max)
+ NEXT_OPCODE;
+
+ if (minimize) {
+ for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
+ RECURSIVE_MATCH(38, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ int d = *stack.currentFrame->args.subjectPtr++;
+ if (d < 128)
+ d = toLowerCase(d);
+ if (stack.currentFrame->locals.fi >= stack.currentFrame->locals.max || stack.currentFrame->args.subjectPtr >= md.endSubject || stack.currentFrame->locals.fc == d)
+ RRETURN;
+ }
+ /* Control never reaches here */
+ }
+
+ /* Maximize case */
+
+ else {
+ stack.currentFrame->locals.subjectPtrAtStartOfInstruction = stack.currentFrame->args.subjectPtr;
+
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ break;
+ int d = *stack.currentFrame->args.subjectPtr;
+ if (d < 128)
+ d = toLowerCase(d);
+ if (stack.currentFrame->locals.fc == d)
+ break;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ for (;;) {
+ RECURSIVE_MATCH(40, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ if (stack.currentFrame->args.subjectPtr-- == stack.currentFrame->locals.subjectPtrAtStartOfInstruction)
+ break; /* Stop if tried at original pos */
+ }
+
+ RRETURN;
+ }
+ /* Control never reaches here */
+ }
+
+ /* Caseful comparisons */
+
+ else {
+ for (int i = 1; i <= min; i++) {
+ int d = *stack.currentFrame->args.subjectPtr++;
+ if (stack.currentFrame->locals.fc == d)
+ RRETURN_NO_MATCH;
+ }
+
+ if (min == stack.currentFrame->locals.max)
+ NEXT_OPCODE;
+
+ if (minimize) {
+ for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
+ RECURSIVE_MATCH(42, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ int d = *stack.currentFrame->args.subjectPtr++;
+ if (stack.currentFrame->locals.fi >= stack.currentFrame->locals.max || stack.currentFrame->args.subjectPtr >= md.endSubject || stack.currentFrame->locals.fc == d)
+ RRETURN;
+ }
+ /* Control never reaches here */
+ }
+
+ /* Maximize case */
+
+ else {
+ stack.currentFrame->locals.subjectPtrAtStartOfInstruction = stack.currentFrame->args.subjectPtr;
+
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ break;
+ int d = *stack.currentFrame->args.subjectPtr;
+ if (stack.currentFrame->locals.fc == d)
+ break;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ for (;;) {
+ RECURSIVE_MATCH(44, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ if (stack.currentFrame->args.subjectPtr-- == stack.currentFrame->locals.subjectPtrAtStartOfInstruction)
+ break; /* Stop if tried at original pos */
+ }
+
+ RRETURN;
+ }
+ }
+ /* Control never reaches here */
+
+ /* Match a single character type repeatedly; several different opcodes
+ share code. This is very similar to the code for single characters, but we
+ repeat it in the interests of efficiency. */
+
+ BEGIN_OPCODE(TYPEEXACT):
+ min = stack.currentFrame->locals.max = get2ByteValue(stack.currentFrame->args.instructionPtr + 1);
+ minimize = true;
+ stack.currentFrame->args.instructionPtr += 3;
+ goto REPEATTYPE;
+
+ BEGIN_OPCODE(TYPEUPTO):
+ BEGIN_OPCODE(TYPEMINUPTO):
+ min = 0;
+ stack.currentFrame->locals.max = get2ByteValue(stack.currentFrame->args.instructionPtr + 1);
+ minimize = *stack.currentFrame->args.instructionPtr == OP_TYPEMINUPTO;
+ stack.currentFrame->args.instructionPtr += 3;
+ goto REPEATTYPE;
+
+ BEGIN_OPCODE(TYPESTAR):
+ BEGIN_OPCODE(TYPEMINSTAR):
+ BEGIN_OPCODE(TYPEPLUS):
+ BEGIN_OPCODE(TYPEMINPLUS):
+ BEGIN_OPCODE(TYPEQUERY):
+ BEGIN_OPCODE(TYPEMINQUERY):
+ repeatInformationFromInstructionOffset(*stack.currentFrame->args.instructionPtr++ - OP_TYPESTAR, minimize, min, stack.currentFrame->locals.max);
+
+ /* Common code for all repeated single character type matches. Note that
+ in UTF-8 mode, '.' matches a character of any length, but for the other
+ character types, the valid characters are all one-byte long. */
+
+ REPEATTYPE:
+ stack.currentFrame->locals.ctype = *stack.currentFrame->args.instructionPtr++; /* Code for the character type */
+
+ /* First, ensure the minimum number of matches are present. Use inline
+ code for maximizing the speed, and do the type test once at the start
+ (i.e. keep it out of the loop). Also we can test that there are at least
+ the minimum number of characters before we start. */
+
+ if (min > md.endSubject - stack.currentFrame->args.subjectPtr)
+ RRETURN_NO_MATCH;
+ if (min > 0) {
+ switch (stack.currentFrame->locals.ctype) {
+ case OP_NOT_NEWLINE:
+ for (int i = 1; i <= min; i++) {
+ if (isNewline(*stack.currentFrame->args.subjectPtr))
+ RRETURN_NO_MATCH;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ case OP_NOT_DIGIT:
+ for (int i = 1; i <= min; i++) {
+ if (isASCIIDigit(*stack.currentFrame->args.subjectPtr))
+ RRETURN_NO_MATCH;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ case OP_DIGIT:
+ for (int i = 1; i <= min; i++) {
+ if (!isASCIIDigit(*stack.currentFrame->args.subjectPtr))
+ RRETURN_NO_MATCH;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ case OP_NOT_WHITESPACE:
+ for (int i = 1; i <= min; i++) {
+ if (isSpaceChar(*stack.currentFrame->args.subjectPtr))
+ RRETURN_NO_MATCH;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ case OP_WHITESPACE:
+ for (int i = 1; i <= min; i++) {
+ if (!isSpaceChar(*stack.currentFrame->args.subjectPtr))
+ RRETURN_NO_MATCH;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ case OP_NOT_WORDCHAR:
+ for (int i = 1; i <= min; i++) {
+ if (isWordChar(*stack.currentFrame->args.subjectPtr))
+ RRETURN_NO_MATCH;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ case OP_WORDCHAR:
+ for (int i = 1; i <= min; i++) {
+ if (!isWordChar(*stack.currentFrame->args.subjectPtr))
+ RRETURN_NO_MATCH;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ default:
+ ASSERT_NOT_REACHED();
+ return matchError(JSRegExpErrorInternal, stack);
+ } /* End switch(stack.currentFrame->locals.ctype) */
+ }
+
+ /* If min = max, continue at the same level without recursing */
+
+ if (min == stack.currentFrame->locals.max)
+ NEXT_OPCODE;
+
+ /* If minimizing, we have to test the rest of the pattern before each
+ subsequent match. */
+
+ if (minimize) {
+ for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
+ RECURSIVE_MATCH(48, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ if (stack.currentFrame->locals.fi >= stack.currentFrame->locals.max || stack.currentFrame->args.subjectPtr >= md.endSubject)
+ RRETURN;
+
+ int c = *stack.currentFrame->args.subjectPtr++;
+ switch (stack.currentFrame->locals.ctype) {
+ case OP_NOT_NEWLINE:
+ if (isNewline(c))
+ RRETURN;
+ break;
+
+ case OP_NOT_DIGIT:
+ if (isASCIIDigit(c))
+ RRETURN;
+ break;
+
+ case OP_DIGIT:
+ if (!isASCIIDigit(c))
+ RRETURN;
+ break;
+
+ case OP_NOT_WHITESPACE:
+ if (isSpaceChar(c))
+ RRETURN;
+ break;
+
+ case OP_WHITESPACE:
+ if (!isSpaceChar(c))
+ RRETURN;
+ break;
+
+ case OP_NOT_WORDCHAR:
+ if (isWordChar(c))
+ RRETURN;
+ break;
+
+ case OP_WORDCHAR:
+ if (!isWordChar(c))
+ RRETURN;
+ break;
+
+ default:
+ ASSERT_NOT_REACHED();
+ return matchError(JSRegExpErrorInternal, stack);
+ }
+ }
+ /* Control never reaches here */
+ }
+
+ /* If maximizing it is worth using inline code for speed, doing the type
+ test once at the start (i.e. keep it out of the loop). */
+
+ else {
+ stack.currentFrame->locals.subjectPtrAtStartOfInstruction = stack.currentFrame->args.subjectPtr; /* Remember where we started */
+
+ switch (stack.currentFrame->locals.ctype) {
+ case OP_NOT_NEWLINE:
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject || isNewline(*stack.currentFrame->args.subjectPtr))
+ break;
+ stack.currentFrame->args.subjectPtr++;
+ }
+ break;
+
+ case OP_NOT_DIGIT:
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ break;
+ int c = *stack.currentFrame->args.subjectPtr;
+ if (isASCIIDigit(c))
+ break;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ case OP_DIGIT:
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ break;
+ int c = *stack.currentFrame->args.subjectPtr;
+ if (!isASCIIDigit(c))
+ break;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ case OP_NOT_WHITESPACE:
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ break;
+ int c = *stack.currentFrame->args.subjectPtr;
+ if (isSpaceChar(c))
+ break;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ case OP_WHITESPACE:
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ break;
+ int c = *stack.currentFrame->args.subjectPtr;
+ if (!isSpaceChar(c))
+ break;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ case OP_NOT_WORDCHAR:
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ break;
+ int c = *stack.currentFrame->args.subjectPtr;
+ if (isWordChar(c))
+ break;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ case OP_WORDCHAR:
+ for (int i = min; i < stack.currentFrame->locals.max; i++) {
+ if (stack.currentFrame->args.subjectPtr >= md.endSubject)
+ break;
+ int c = *stack.currentFrame->args.subjectPtr;
+ if (!isWordChar(c))
+ break;
+ ++stack.currentFrame->args.subjectPtr;
+ }
+ break;
+
+ default:
+ ASSERT_NOT_REACHED();
+ return matchError(JSRegExpErrorInternal, stack);
+ }
+
+ /* stack.currentFrame->args.subjectPtr is now past the end of the maximum run */
+
+ for (;;) {
+ RECURSIVE_MATCH(52, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ if (stack.currentFrame->args.subjectPtr-- == stack.currentFrame->locals.subjectPtrAtStartOfInstruction)
+ break; /* Stop if tried at original pos */
+ }
+
+ /* Get here if we can't make it match with any permitted repetitions */
+
+ RRETURN;
+ }
+ /* Control never reaches here */
+
+ BEGIN_OPCODE(CRMINPLUS):
+ BEGIN_OPCODE(CRMINQUERY):
+ BEGIN_OPCODE(CRMINRANGE):
+ BEGIN_OPCODE(CRMINSTAR):
+ BEGIN_OPCODE(CRPLUS):
+ BEGIN_OPCODE(CRQUERY):
+ BEGIN_OPCODE(CRRANGE):
+ BEGIN_OPCODE(CRSTAR):
+ ASSERT_NOT_REACHED();
+ return matchError(JSRegExpErrorInternal, stack);
+
+#ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
+ CAPTURING_BRACKET:
+#else
+ default:
+#endif
+ /* Opening capturing bracket. If there is space in the offset vector, save
+ the current subject position in the working slot at the top of the vector. We
+ mustn't change the current values of the data slot, because they may be set
+ from a previous iteration of this group, and be referred to by a reference
+ inside the group.
+
+ If the bracket fails to match, we need to restore this value and also the
+ values of the final offsets, in case they were set by a previous iteration of
+ the same bracket.
+
+ If there isn't enough space in the offset vector, treat this as if it were a
+ non-capturing bracket. Don't worry about setting the flag for the error case
+ here; that is handled in the code for KET. */
+
+ ASSERT(*stack.currentFrame->args.instructionPtr > OP_BRA);
+
+ stack.currentFrame->locals.number = *stack.currentFrame->args.instructionPtr - OP_BRA;
+
+ /* For extended extraction brackets (large number), we have to fish out the
+ number from a dummy opcode at the start. */
+
+ if (stack.currentFrame->locals.number > EXTRACT_BASIC_MAX)
+ stack.currentFrame->locals.number = get2ByteValue(stack.currentFrame->args.instructionPtr + 2 + LINK_SIZE);
+ stack.currentFrame->locals.offset = stack.currentFrame->locals.number << 1;
+
+#ifdef DEBUG
+ printf("start bracket %d subject=", stack.currentFrame->locals.number);
+ pchars(stack.currentFrame->args.subjectPtr, 16, true, md);
+ printf("\n");
+#endif
+
+ if (stack.currentFrame->locals.offset < md.offsetMax) {
+ stack.currentFrame->locals.saveOffset1 = md.offsetVector[stack.currentFrame->locals.offset];
+ stack.currentFrame->locals.saveOffset2 = md.offsetVector[stack.currentFrame->locals.offset + 1];
+ stack.currentFrame->locals.saveOffset3 = md.offsetVector[md.offsetEnd - stack.currentFrame->locals.number];
+
+ DPRINTF(("saving %d %d %d\n", stack.currentFrame->locals.saveOffset1, stack.currentFrame->locals.saveOffset2, stack.currentFrame->locals.saveOffset3));
+ md.offsetVector[md.offsetEnd - stack.currentFrame->locals.number] = stack.currentFrame->args.subjectPtr - md.startSubject;
+
+ do {
+ RECURSIVE_MATCH_NEW_GROUP(1, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
+ if (isMatch)
+ RRETURN;
+ stack.currentFrame->args.instructionPtr += getLinkValue(stack.currentFrame->args.instructionPtr + 1);
+ } while (*stack.currentFrame->args.instructionPtr == OP_ALT);
+
+ DPRINTF(("bracket %d failed\n", stack.currentFrame->locals.number));
+
+ md.offsetVector[stack.currentFrame->locals.offset] = stack.currentFrame->locals.saveOffset1;
+ md.offsetVector[stack.currentFrame->locals.offset + 1] = stack.currentFrame->locals.saveOffset2;
+ md.offsetVector[md.offsetEnd - stack.currentFrame->locals.number] = stack.currentFrame->locals.saveOffset3;
+
+ RRETURN;
+ }
+
+ /* Insufficient room for saving captured contents */
+
+ goto NON_CAPTURING_BRACKET;
+ }
+
+ /* Do not stick any code in here without much thought; it is assumed
+ that "continue" in the code above comes out to here to repeat the main
+ loop. */
+
+ } /* End of main loop */
+
+ ASSERT_NOT_REACHED();
+
+#ifndef USE_COMPUTED_GOTO_FOR_MATCH_RECURSION
+
+RRETURN_SWITCH:
+ switch (stack.currentFrame->returnLocation) {
+ case 0: goto RETURN;
+ case 1: goto RRETURN_1;
+ case 2: goto RRETURN_2;
+ case 6: goto RRETURN_6;
+ case 7: goto RRETURN_7;
+ case 14: goto RRETURN_14;
+ case 15: goto RRETURN_15;
+ case 16: goto RRETURN_16;
+ case 17: goto RRETURN_17;
+ case 18: goto RRETURN_18;
+ case 19: goto RRETURN_19;
+ case 20: goto RRETURN_20;
+ case 21: goto RRETURN_21;
+ case 22: goto RRETURN_22;
+ case 24: goto RRETURN_24;
+ case 26: goto RRETURN_26;
+ case 27: goto RRETURN_27;
+ case 28: goto RRETURN_28;
+ case 29: goto RRETURN_29;
+ case 30: goto RRETURN_30;
+ case 31: goto RRETURN_31;
+ case 38: goto RRETURN_38;
+ case 40: goto RRETURN_40;
+ case 42: goto RRETURN_42;
+ case 44: goto RRETURN_44;
+ case 48: goto RRETURN_48;
+ case 52: goto RRETURN_52;
+ }
+
+ ASSERT_NOT_REACHED();
+ return matchError(JSRegExpErrorInternal, stack);
+
+#endif
+
+RETURN:
+ return isMatch;
+}
+
+
+/*************************************************
+* Execute a Regular Expression *
+*************************************************/
+
+/* This function applies a compiled re to a subject string and picks out
+portions of the string if it matches. Two elements in the vector are set for
+each substring: the offsets to the start and end of the substring.
+
+Arguments:
+ re points to the compiled expression
+ extra_data points to extra data or is NULL
+ subject points to the subject string
+ length length of subject string (may contain binary zeros)
+ start_offset where to start in the subject string
+ options option bits
+ offsets points to a vector of ints to be filled in with offsets
+ offsetCount the number of elements in the vector
+
+Returns: > 0 => success; value is the number of elements filled in
+ = 0 => success, but offsets is not big enough
+ -1 => failed to match
+ < -1 => some kind of unexpected problem
+*/
+
+static void tryFirstByteOptimization(const UChar*& subjectPtr, const UChar* endSubject, int firstByte, bool firstByteIsCaseless, bool useMultiLineFirstCharOptimization, const UChar* originalSubjectStart)
+{
+ // If firstByte is set, try scanning to the first instance of that byte
+ // no need to try and match against any earlier part of the subject string.
+ if (firstByte >= 0) {
+ UChar firstChar = firstByte;
+ if (firstByteIsCaseless)
+ while (subjectPtr < endSubject) {
+ int c = *subjectPtr;
+ if (c > 127)
+ break;
+ if (toLowerCase(c) == firstChar)
+ break;
+ subjectPtr++;
+ }
+ else {
+ while (subjectPtr < endSubject && *subjectPtr != firstChar)
+ subjectPtr++;
+ }
+ } else if (useMultiLineFirstCharOptimization) {
+ /* Or to just after \n for a multiline match if possible */
+ // I'm not sure why this != originalSubjectStart check is necessary -- ecs 11/18/07
+ if (subjectPtr > originalSubjectStart) {
+ while (subjectPtr < endSubject && !isNewline(subjectPtr[-1]))
+ subjectPtr++;
+ }
+ }
+}
+
+static bool tryRequiredByteOptimization(const UChar*& subjectPtr, const UChar* endSubject, int reqByte, int reqByte2, bool reqByteIsCaseless, bool hasFirstByte, const UChar*& reqBytePtr)
+{
+ /* If reqByte is set, we know that that character must appear in the subject
+ for the match to succeed. If the first character is set, reqByte must be
+ later in the subject; otherwise the test starts at the match point. This
+ optimization can save a huge amount of backtracking in patterns with nested
+ unlimited repeats that aren't going to match. Writing separate code for
+ cased/caseless versions makes it go faster, as does using an autoincrement
+ and backing off on a match.
+
+ HOWEVER: when the subject string is very, very long, searching to its end can
+ take a long time, and give bad performance on quite ordinary patterns. This
+ showed up when somebody was matching /^C/ on a 32-megabyte string... so we
+ don't do this when the string is sufficiently long.
+ */
+
+ if (reqByte >= 0 && endSubject - subjectPtr < REQ_BYTE_MAX) {
+ const UChar* p = subjectPtr + (hasFirstByte ? 1 : 0);
+
+ /* We don't need to repeat the search if we haven't yet reached the
+ place we found it at last time. */
+
+ if (p > reqBytePtr) {
+ if (reqByteIsCaseless) {
+ while (p < endSubject) {
+ int pp = *p++;
+ if (pp == reqByte || pp == reqByte2) {
+ p--;
+ break;
+ }
+ }
+ } else {
+ while (p < endSubject) {
+ if (*p++ == reqByte) {
+ p--;
+ break;
+ }
+ }
+ }
+
+ /* If we can't find the required character, break the matching loop */
+
+ if (p >= endSubject)
+ return true;
+
+ /* If we have found the required character, save the point where we
+ found it, so that we don't search again next time round the loop if
+ the start hasn't passed this character yet. */
+
+ reqBytePtr = p;
+ }
+ }
+ return false;
+}
+
+int jsRegExpExecute(const JSRegExp* re,
+ const UChar* subject, int length, int start_offset, int* offsets,
+ int offsetCount)
+{
+ ASSERT(re);
+ ASSERT(subject || !length);
+ ASSERT(offsetCount >= 0);
+ ASSERT(offsets || offsetCount == 0);
+
+ HistogramTimeLogger logger(re);
+
+ MatchData matchBlock;
+ matchBlock.startSubject = subject;
+ matchBlock.endSubject = matchBlock.startSubject + length;
+ const UChar* endSubject = matchBlock.endSubject;
+
+ matchBlock.multiline = (re->options & MatchAcrossMultipleLinesOption);
+ matchBlock.ignoreCase = (re->options & IgnoreCaseOption);
+
+ /* If the expression has got more back references than the offsets supplied can
+ hold, we get a temporary chunk of working store to use during the matching.
+ Otherwise, we can use the vector supplied, rounding down its size to a multiple
+ of 3. */
+
+ int ocount = offsetCount - (offsetCount % 3);
+
+ // FIXME: This is lame that we have to second-guess our caller here.
+ // The API should change to either fail-hard when we don't have enough offset space
+ // or that we shouldn't ask our callers to pre-allocate in the first place.
+ bool usingTemporaryOffsets = false;
+ if (re->topBackref > 0 && re->topBackref >= ocount/3) {
+ ocount = re->topBackref * 3 + 3;
+ matchBlock.offsetVector = new int[ocount];
+ if (!matchBlock.offsetVector)
+ return JSRegExpErrorNoMemory;
+ usingTemporaryOffsets = true;
+ } else
+ matchBlock.offsetVector = offsets;
+
+ matchBlock.offsetEnd = ocount;
+ matchBlock.offsetMax = (2*ocount)/3;
+ matchBlock.offsetOverflow = false;
+
+ /* Compute the minimum number of offsets that we need to reset each time. Doing
+ this makes a huge difference to execution time when there aren't many brackets
+ in the pattern. */
+
+ int resetCount = 2 + re->topBracket * 2;
+ if (resetCount > offsetCount)
+ resetCount = ocount;
+
+ /* Reset the working variable associated with each extraction. These should
+ never be used unless previously set, but they get saved and restored, and so we
+ initialize them to avoid reading uninitialized locations. */
+
+ if (matchBlock.offsetVector) {
+ int* iptr = matchBlock.offsetVector + ocount;
+ int* iend = iptr - resetCount/2 + 1;
+ while (--iptr >= iend)
+ *iptr = -1;
+ }
+
+ /* Set up the first character to match, if available. The firstByte value is
+ never set for an anchored regular expression, but the anchoring may be forced
+ at run time, so we have to test for anchoring. The first char may be unset for
+ an unanchored pattern, of course. If there's no first char and the pattern was
+ studied, there may be a bitmap of possible first characters. */
+
+ bool firstByteIsCaseless = false;
+ int firstByte = -1;
+ if (re->options & UseFirstByteOptimizationOption) {
+ firstByte = re->firstByte & 255;
+ if ((firstByteIsCaseless = (re->firstByte & REQ_IGNORE_CASE)))
+ firstByte = toLowerCase(firstByte);
+ }
+
+ /* For anchored or unanchored matches, there may be a "last known required
+ character" set. */
+
+ bool reqByteIsCaseless = false;
+ int reqByte = -1;
+ int reqByte2 = -1;
+ if (re->options & UseRequiredByteOptimizationOption) {
+ reqByte = re->reqByte & 255; // FIXME: This optimization could be made to work for UTF16 chars as well...
+ reqByteIsCaseless = (re->reqByte & REQ_IGNORE_CASE);
+ reqByte2 = flipCase(reqByte);
+ }
+
+ /* Loop for handling unanchored repeated matching attempts; for anchored regexs
+ the loop runs just once. */
+
+ const UChar* startMatch = subject + start_offset;
+ const UChar* reqBytePtr = startMatch - 1;
+ bool useMultiLineFirstCharOptimization = re->options & UseMultiLineFirstByteOptimizationOption;
+
+ do {
+ /* Reset the maximum number of extractions we might see. */
+ if (matchBlock.offsetVector) {
+ int* iptr = matchBlock.offsetVector;
+ int* iend = iptr + resetCount;
+ while (iptr < iend)
+ *iptr++ = -1;
+ }
+
+ tryFirstByteOptimization(startMatch, endSubject, firstByte, firstByteIsCaseless, useMultiLineFirstCharOptimization, matchBlock.startSubject + start_offset);
+ if (tryRequiredByteOptimization(startMatch, endSubject, reqByte, reqByte2, reqByteIsCaseless, firstByte >= 0, reqBytePtr))
+ break;
+
+ /* When a match occurs, substrings will be set for all internal extractions;
+ we just need to set up the whole thing as substring 0 before returning. If
+ there were too many extractions, set the return code to zero. In the case
+ where we had to get some local store to hold offsets for backreferences, copy
+ those back references that we can. In this case there need not be overflow
+ if certain parts of the pattern were not used. */
+
+ /* The code starts after the JSRegExp block and the capture name table. */
+ const unsigned char* start_code = (const unsigned char*)(re + 1);
+
+ int returnCode = match(startMatch, start_code, 2, matchBlock);
+
+ /* When the result is no match, advance the pointer to the next character
+ and continue. */
+ if (returnCode == 0) {
+ startMatch++;
+ continue;
+ }
+
+ if (returnCode != 1) {
+ ASSERT(returnCode == JSRegExpErrorHitLimit || returnCode == JSRegExpErrorNoMemory);
+ DPRINTF((">>>> error: returning %d\n", returnCode));
+ return returnCode;
+ }
+
+ /* We have a match! Copy the offset information from temporary store if
+ necessary */
+
+ if (usingTemporaryOffsets) {
+ if (offsetCount >= 4) {
+ memcpy(offsets + 2, matchBlock.offsetVector + 2, (offsetCount - 2) * sizeof(int));
+ DPRINTF(("Copied offsets from temporary memory\n"));
+ }
+ if (matchBlock.endOffsetTop > offsetCount)
+ matchBlock.offsetOverflow = true;
+
+ DPRINTF(("Freeing temporary memory\n"));
+ delete [] matchBlock.offsetVector;
+ }
+
+ returnCode = matchBlock.offsetOverflow ? 0 : matchBlock.endOffsetTop / 2;
+
+ if (offsetCount < 2)
+ returnCode = 0;
+ else {
+ offsets[0] = startMatch - matchBlock.startSubject;
+ offsets[1] = matchBlock.endMatchPtr - matchBlock.startSubject;
+ }
+
+ DPRINTF((">>>> returning %d\n", returnCode));
+ return returnCode;
+ } while (!(re->options & IsAnchoredOption) && startMatch <= endSubject);
+
+ if (usingTemporaryOffsets) {
+ DPRINTF(("Freeing temporary memory\n"));
+ delete [] matchBlock.offsetVector;
+ }
+
+ DPRINTF((">>>> returning PCRE_ERROR_NOMATCH\n"));
+ return JSRegExpErrorNoMatch;
+}
+
+#if REGEXP_HISTOGRAM
+
+class CompareHistogramEntries {
+public:
+ bool operator()(const pair<UString, double>& a, const pair<UString, double>& b)
+ {
+ if (a.second == b.second)
+ return a.first < b.first;
+ return a.second < b.second;
+ }
+};
+
+Histogram::~Histogram()
+{
+ Vector<pair<UString, double> > values;
+ Map::iterator end = times.end();
+ for (Map::iterator it = times.begin(); it != end; ++it)
+ values.append(*it);
+ sort(values.begin(), values.end(), CompareHistogramEntries());
+ size_t size = values.size();
+ printf("Regular Expressions, sorted by time spent evaluating them:\n");
+ for (size_t i = 0; i < size; ++i)
+ printf(" %f - %s\n", values[size - i - 1].second, values[size - i - 1].first.UTF8String().c_str());
+}
+
+void Histogram::add(const JSRegExp* re, double elapsedTime)
+{
+ UString string(reinterpret_cast<const UChar*>(reinterpret_cast<const char*>(re) + re->stringOffset), re->stringLength);
+ if (re->options & IgnoreCaseOption && re->options & MatchAcrossMultipleLinesOption)
+ string += " (multi-line, ignore case)";
+ else {
+ if (re->options & IgnoreCaseOption)
+ string += " (ignore case)";
+ if (re->options & MatchAcrossMultipleLinesOption)
+ string += " (multi-line)";
+ }
+ pair<Map::iterator, bool> result = times.add(string.rep(), elapsedTime);
+ if (!result.second)
+ result.first->second += elapsedTime;
+}
+
+HistogramTimeLogger::HistogramTimeLogger(const JSRegExp* re)
+ : m_re(re)
+ , m_startTime(currentTimeMS())
+{
+}
+
+HistogramTimeLogger::~HistogramTimeLogger()
+{
+ static Histogram histogram;
+ histogram.add(m_re, currentTimeMS() - m_startTime);
+}
+
+#endif