+++ /dev/null
-/* 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(short 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
projects / apple / javascriptcore.git / blobdiff