typedef void* ReturnLocation;
#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 {
ReturnLocation returnLocation;
struct MatchFrame* previousFrame;
const UChar* subjectPtr;
const unsigned char* instructionPtr;
int offsetTop;
- const UChar* subpatternStart;
+ BracketChainNode* bracketChain;
} args;
int saveOffset2;
int saveOffset3;
- const UChar* subpatternStart;
+ BracketChainNode bracketChainNode;
} locals;
};
return new MatchFrame;
}
- inline void pushNewFrame(const unsigned char* instructionPtr, const UChar* subpatternStart, ReturnLocation returnLocation)
+ 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.subpatternStart = subpatternStart;
+ newframe->args.bracketChain = bracketChain;
newframe->returnLocation = returnLocation;
size++;
the closing ket. When match() is called in other circumstances, we don't add to
this stack. */
- currentFrame->locals.subpatternStart = currentFrame->args.subpatternStart;
+ 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
stack.currentFrame->args.subjectPtr = subjectPtr;
stack.currentFrame->args.instructionPtr = instructionPtr;
stack.currentFrame->args.offsetTop = offsetTop;
- stack.currentFrame->args.subpatternStart = 0;
+ stack.currentFrame->args.bracketChain = 0;
startNewGroup(stack.currentFrame);
/* This is where control jumps back to to effect "recursion" */
NON_CAPTURING_BRACKET:
DPRINTF(("start bracket 0\n"));
do {
- RECURSIVE_MATCH_STARTNG_NEW_GROUP(2, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH_STARTNG_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);
BEGIN_OPCODE(BRAZERO): {
stack.currentFrame->locals.startOfRepeatingBracket = stack.currentFrame->args.instructionPtr + 1;
- RECURSIVE_MATCH_STARTNG_NEW_GROUP(14, stack.currentFrame->locals.startOfRepeatingBracket, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH_STARTNG_NEW_GROUP(14, stack.currentFrame->locals.startOfRepeatingBracket, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
advanceToEndOfBracket(stack.currentFrame->locals.startOfRepeatingBracket);
BEGIN_OPCODE(BRAMINZERO): {
stack.currentFrame->locals.startOfRepeatingBracket = stack.currentFrame->args.instructionPtr + 1;
advanceToEndOfBracket(stack.currentFrame->locals.startOfRepeatingBracket);
- RECURSIVE_MATCH_STARTNG_NEW_GROUP(15, stack.currentFrame->locals.startOfRepeatingBracket + 1 + LINK_SIZE, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH_STARTNG_NEW_GROUP(15, stack.currentFrame->locals.startOfRepeatingBracket + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
stack.currentFrame->args.instructionPtr++;
BEGIN_OPCODE(KETRMIN):
BEGIN_OPCODE(KETRMAX):
stack.currentFrame->locals.instructionPtrAtStartOfOnce = stack.currentFrame->args.instructionPtr - getLinkValue(stack.currentFrame->args.instructionPtr + 1);
- stack.currentFrame->args.subpatternStart = stack.currentFrame->locals.subpatternStart;
- stack.currentFrame->locals.subpatternStart = stack.currentFrame->previousFrame->args.subpatternStart;
+ 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;
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.subpatternStart);
+ RECURSIVE_MATCH(16, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
- RECURSIVE_MATCH_STARTNG_NEW_GROUP(17, stack.currentFrame->locals.instructionPtrAtStartOfOnce, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH_STARTNG_NEW_GROUP(17, stack.currentFrame->locals.instructionPtrAtStartOfOnce, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
} else { /* OP_KETRMAX */
- RECURSIVE_MATCH_STARTNG_NEW_GROUP(18, stack.currentFrame->locals.instructionPtrAtStartOfOnce, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH_STARTNG_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.subpatternStart);
+ RECURSIVE_MATCH(19, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
}
if (minimize) {
for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
- RECURSIVE_MATCH(20, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ 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))
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.subpatternStart);
+ RECURSIVE_MATCH(21, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
stack.currentFrame->args.subjectPtr -= stack.currentFrame->locals.length;
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.subpatternStart);
+ 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)
++stack.currentFrame->args.subjectPtr;
}
for (;;) {
- RECURSIVE_MATCH(24, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH(24, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
if (stack.currentFrame->args.subjectPtr-- == stack.currentFrame->locals.subjectPtrAtStartOfInstruction)
if (minimize) {
for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
- RECURSIVE_MATCH(26, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ 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)
++stack.currentFrame->args.subjectPtr;
}
for(;;) {
- RECURSIVE_MATCH(27, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH(27, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
if (stack.currentFrame->args.subjectPtr-- == stack.currentFrame->locals.subjectPtrAtStartOfInstruction)
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.subpatternStart);
+ 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)
++stack.currentFrame->args.subjectPtr;
}
while (stack.currentFrame->args.subjectPtr >= stack.currentFrame->locals.subjectPtrAtStartOfInstruction) {
- RECURSIVE_MATCH(29, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH(29, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
--stack.currentFrame->args.subjectPtr;
if (minimize) {
for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
- RECURSIVE_MATCH(30, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ 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)
stack.currentFrame->args.subjectPtr += 2;
}
while (stack.currentFrame->args.subjectPtr >= stack.currentFrame->locals.subjectPtrAtStartOfInstruction) {
- RECURSIVE_MATCH(31, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH(31, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
stack.currentFrame->args.subjectPtr -= 2;
if (minimize) {
for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
- RECURSIVE_MATCH(38, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH(38, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
int d = *stack.currentFrame->args.subjectPtr++;
++stack.currentFrame->args.subjectPtr;
}
for (;;) {
- RECURSIVE_MATCH(40, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH(40, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
if (stack.currentFrame->args.subjectPtr-- == stack.currentFrame->locals.subjectPtrAtStartOfInstruction)
if (minimize) {
for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
- RECURSIVE_MATCH(42, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH(42, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
int d = *stack.currentFrame->args.subjectPtr++;
++stack.currentFrame->args.subjectPtr;
}
for (;;) {
- RECURSIVE_MATCH(44, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH(44, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
if (stack.currentFrame->args.subjectPtr-- == stack.currentFrame->locals.subjectPtrAtStartOfInstruction)
if (minimize) {
for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
- RECURSIVE_MATCH(48, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ 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)
/* stack.currentFrame->args.subjectPtr is now past the end of the maximum run */
for (;;) {
- RECURSIVE_MATCH(52, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH(52, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
if (isMatch)
RRETURN;
if (stack.currentFrame->args.subjectPtr-- == stack.currentFrame->locals.subjectPtrAtStartOfInstruction)
md.offsetVector[md.offsetEnd - stack.currentFrame->locals.number] = stack.currentFrame->args.subjectPtr - md.startSubject;
do {
- RECURSIVE_MATCH_STARTNG_NEW_GROUP(1, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.subpatternStart);
+ RECURSIVE_MATCH_STARTNG_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);
FAILED TO COMPILE
/(abc|)+/
- abc: FAIL. Actual results: "null"
- abcabc: FAIL. Actual results: "null"
- abcabcabc: FAIL. Actual results: "null"
- xyz : FAIL. Actual results: "null"
+ abc: PASS
+ abcabc: PASS
+ abcabcabc: PASS
+ xyz : PASS
/([a]*)*/
- a: FAIL. Actual results: "null"
- aaaaa : FAIL. Actual results: "null"
+ a: PASS
+ aaaaa : PASS
/([ab]*)*/
- a: FAIL. Actual results: "null"
- b: FAIL. Actual results: "null"
- ababab: FAIL. Actual results: "null"
- aaaabcde: FAIL. Actual results: "null"
- bbbb : FAIL. Actual results: "null"
+ a: PASS
+ b: PASS
+ ababab: PASS
+ aaaabcde: PASS
+ bbbb : PASS
/([^a]*)*/
- b: FAIL. Actual results: "null"
- bbbb: FAIL. Actual results: "null"
- aaa : FAIL. Actual results: "null"
+ b: PASS
+ bbbb: PASS
+ aaa : PASS
/([^ab]*)*/
- cccc: FAIL. Actual results: "null"
- abab : FAIL. Actual results: "null"
+ cccc: PASS
+ abab : PASS
/([a]*?)*/
- a: FAIL. Actual results: "null"
- aaaa : FAIL. Actual results: "null"
+ a: PASS
+ aaaa : PASS
/([ab]*?)*/
- a: FAIL. Actual results: "null"
- b: FAIL. Actual results: "null"
- abab: FAIL. Actual results: "null"
- baba : FAIL. Actual results: "null"
+ a: PASS
+ b: PASS
+ abab: PASS
+ baba : PASS
/([^a]*?)*/
- b: FAIL. Actual results: "null"
- bbbb: FAIL. Actual results: "null"
- aaa : FAIL. Actual results: "null"
+ b: PASS
+ bbbb: PASS
+ aaa : PASS
/([^ab]*?)*/
- c: FAIL. Actual results: "null"
- cccc: FAIL. Actual results: "null"
- baba : FAIL. Actual results: "null"
+ c: PASS
+ cccc: PASS
+ baba : PASS
/(?>a*)*/
FAILED TO COMPILE
/^(?:a?b?)*$/
\: FAIL. Actual results: "null"
- a: FAIL. Actual results: "null"
- ab: FAIL. Actual results: "null"
+ a: PASS
+ ab: PASS
aaa : FAIL. Actual results: "null"
*** Failers
dbcb: PASS
FAILED TO COMPILE
/^(a()*)*/
- aaaa: FAIL. Actual results: "null"
+ aaaa: FAIL. Actual results: "a,a,"
/^(?:a(?:(?:))*)*/
- aaaa: FAIL. Actual results: "null"
+ aaaa: FAIL. Actual results: "a"
/^(a()+)+/
- aaaa: FAIL. Actual results: "null"
+ aaaa: PASS
/^(?:a(?:(?:))+)+/
- aaaa: FAIL. Actual results: "null"
+ aaaa: PASS
/(a){0,3}(?(1)b|(c|))*D/
FAILED TO COMPILE
/(a|)*\d/
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa: PASS
- aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa4: FAIL. Actual results: "null"
+ aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa4: PASS
/(?>a|)*\d/
FAILED TO COMPILE
/(?:a|)*\d/
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa: PASS
- aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa4: FAIL. Actual results: "null"
+ aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa4: PASS
/\Z/g
Global regex, cannot test matching via JS
FAILED TO COMPILE
/(.*(.)?)*/
- abcd: FAIL. Actual results: "null"
+ abcd: FAIL. Actual results: "abcd,,"
/( (A | (?(1)0|) )* )/x
Unsupported modifiers: x