summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--js/src/irregexp/NativeRegExpMacroAssembler.cpp385
-rw-r--r--js/src/irregexp/NativeRegExpMacroAssembler.h8
-rw-r--r--js/src/irregexp/RegExpAST.h10
-rw-r--r--js/src/irregexp/RegExpEngine.cpp75
-rw-r--r--js/src/irregexp/RegExpEngine.h10
-rw-r--r--js/src/irregexp/RegExpInterpreter.cpp2
-rw-r--r--js/src/irregexp/RegExpMacroAssembler.cpp4
-rw-r--r--js/src/irregexp/RegExpMacroAssembler.h4
8 files changed, 255 insertions, 243 deletions
diff --git a/js/src/irregexp/NativeRegExpMacroAssembler.cpp b/js/src/irregexp/NativeRegExpMacroAssembler.cpp
index 2efbf1bf76..41c1951bc2 100644
--- a/js/src/irregexp/NativeRegExpMacroAssembler.cpp
+++ b/js/src/irregexp/NativeRegExpMacroAssembler.cpp
@@ -71,13 +71,13 @@ NativeRegExpMacroAssembler::NativeRegExpMacroAssembler(LifoAlloc* alloc, RegExpS
// Find physical registers for each compiler register.
AllocatableGeneralRegisterSet regs(GeneralRegisterSet::All());
+ temp0 = regs.takeAny();
+ temp1 = regs.takeAny();
+ temp2 = regs.takeAny();
input_end_pointer = regs.takeAny();
current_character = regs.takeAny();
current_position = regs.takeAny();
backtrack_stack_pointer = regs.takeAny();
- temp0 = regs.takeAny();
- temp1 = regs.takeAny();
- temp2 = regs.takeAny();
JitSpew(JitSpew_Codegen,
"Starting RegExp (input_end_pointer %s) (current_character %s)"
@@ -548,23 +548,20 @@ NativeRegExpMacroAssembler::Bind(Label* label)
}
void
-NativeRegExpMacroAssembler::CheckAtStart(Label* on_at_start)
-{
- JitSpew(SPEW_PREFIX "CheckAtStart");
-
- Label not_at_start;
-
- // Did we start the match at the start of the string at all?
- Address startIndex(masm.getStackPointer(), offsetof(FrameData, startIndex));
- masm.branchPtr(Assembler::NotEqual, startIndex, ImmWord(0), &not_at_start);
-
- // If we did, are we still at the start of the input?
- masm.computeEffectiveAddress(BaseIndex(input_end_pointer, current_position, TimesOne), temp0);
+NativeRegExpMacroAssembler::CheckAtStartImpl(int cp_offset, Label* on_cond,
+ Assembler::Condition cond) {
+ masm.computeEffectiveAddress(BaseIndex(input_end_pointer, current_position, TimesOne, cp_offset * char_size()), temp0);
Address inputStart(masm.getStackPointer(), offsetof(FrameData, inputStart));
- masm.branchPtr(Assembler::Equal, inputStart, temp0, BranchOrBacktrack(on_at_start));
+ masm.branchPtr(cond, inputStart, temp0, BranchOrBacktrack(on_cond));
+}
+
+void
+NativeRegExpMacroAssembler::CheckAtStart(int cp_offset, Label* on_at_start)
+{
+ JitSpew(SPEW_PREFIX "CheckAtStart");
- masm.bind(&not_at_start);
+ CheckAtStartImpl(cp_offset, on_at_start, Assembler::Equal);
}
void
@@ -572,15 +569,7 @@ NativeRegExpMacroAssembler::CheckNotAtStart(int cp_offset, Label* on_not_at_star
{
JitSpew(SPEW_PREFIX "CheckNotAtStart");
- // Did we start the match at the start of the string at all?
- Address startIndex(masm.getStackPointer(), offsetof(FrameData, startIndex));
- masm.branchPtr(Assembler::NotEqual, startIndex, ImmWord(0), BranchOrBacktrack(on_not_at_start));
-
- // If we did, are we still at the start of the input?
- masm.computeEffectiveAddress(BaseIndex(input_end_pointer, current_position, TimesOne), temp0);
-
- Address inputStart(masm.getStackPointer(), offsetof(FrameData, inputStart));
- masm.branchPtr(Assembler::NotEqual, inputStart, temp0, BranchOrBacktrack(on_not_at_start));
+ CheckAtStartImpl(cp_offset, on_not_at_start, Assembler::NotEqual);
}
void
@@ -659,211 +648,204 @@ NativeRegExpMacroAssembler::CheckGreedyLoop(Label* on_tos_equals_current_positio
}
void
-NativeRegExpMacroAssembler::CheckNotBackReference(int start_reg, bool read_backward, Label* on_no_match)
+NativeRegExpMacroAssembler::CheckNotBackReferenceImpl(int start_reg, bool read_backward,
+ Label* on_no_match,
+ bool unicode, bool ignore_case)
{
- JitSpew(SPEW_PREFIX "CheckNotBackReference(%d)", start_reg);
-
Label fallthrough;
- Label success;
- Label fail;
-
- // Find length of back-referenced capture.
- masm.loadPtr(register_location(start_reg), current_character);
- masm.loadPtr(register_location(start_reg + 1), temp0);
- masm.subPtr(current_character, temp0); // Length to check.
- // Fail on partial or illegal capture (start of capture after end of capture).
- masm.branchPtr(Assembler::LessThan, temp0, ImmWord(0), BranchOrBacktrack(on_no_match));
+ // Captures are stored as a sequential pair of registers.
+ // Find the length of the back-referenced capture and load the
+ // capture's start index into current_character_
+ masm.loadPtr(register_location(start_reg), current_character); // Index of start of capture
+ masm.loadPtr(register_location(start_reg + 1), temp0); // Index of end of capture
+ masm.subPtr(current_character, temp0); // Length of capture.
- // Succeed on empty capture (including no capture).
+ // If length is zero, either the capture is empty or it is completely
+ // uncaptured. In either case succeed immediately.
masm.branchPtr(Assembler::Equal, temp0, ImmWord(0), &fallthrough);
// Check that there are sufficient characters left in the input.
- masm.movePtr(current_position, temp1);
- masm.addPtr(temp0, temp1);
- masm.branchPtr(Assembler::GreaterThan, temp1, ImmWord(0), BranchOrBacktrack(on_no_match));
-
- // Save register to make it available below.
- masm.push(backtrack_stack_pointer);
-
- // Compute pointers to match string and capture string
- masm.computeEffectiveAddress(BaseIndex(input_end_pointer, current_position, TimesOne), temp1); // Start of match.
- masm.addPtr(input_end_pointer, current_character); // Start of capture.
- masm.computeEffectiveAddress(BaseIndex(temp0, temp1, TimesOne), backtrack_stack_pointer); // End of match.
-
- Label loop;
- masm.bind(&loop);
- if (mode_ == ASCII) {
- masm.load8ZeroExtend(Address(current_character, 0), temp0);
- masm.load8ZeroExtend(Address(temp1, 0), temp2);
+ if (read_backward) {
+ // If start + len > current, there isn't enough room for a
+ // lookbehind backreference.
+ Address inputStart(masm.getStackPointer(), offsetof(FrameData, inputStart));
+ masm.loadPtr(inputStart, temp1);
+ masm.subPtr(input_end_pointer, temp1);
+ masm.addPtr(temp0, temp1);
+ masm.branchPtr(Assembler::GreaterThan, temp1, current_position,
+ BranchOrBacktrack(on_no_match));
} else {
- MOZ_ASSERT(mode_ == CHAR16);
- masm.load16ZeroExtend(Address(current_character, 0), temp0);
- masm.load16ZeroExtend(Address(temp1, 0), temp2);
+ // current_position is the negative offset from the end.
+ // If current + len > 0, there isn't enough room for a backreference.
+ masm.movePtr(current_position, temp1);
+ masm.addPtr(temp0, temp1);
+ masm.branchPtr(Assembler::GreaterThan, temp1, ImmWord(0),
+ BranchOrBacktrack(on_no_match));
}
- masm.branch32(Assembler::NotEqual, temp0, temp2, &fail);
-
- // Increment pointers into capture and match string.
- masm.addPtr(Imm32(char_size()), current_character);
- masm.addPtr(Imm32(char_size()), temp1);
-
- // Check if we have reached end of match area.
- masm.branchPtr(Assembler::Below, temp1, backtrack_stack_pointer, &loop);
- masm.jump(&success);
-
- masm.bind(&fail);
-
- // Restore backtrack stack pointer.
- masm.pop(backtrack_stack_pointer);
- JumpOrBacktrack(on_no_match);
-
- masm.bind(&success);
-
- // Move current character position to position after match.
- masm.movePtr(backtrack_stack_pointer, current_position);
- masm.subPtr(input_end_pointer, current_position);
-
- // Restore backtrack stack pointer.
- masm.pop(backtrack_stack_pointer);
-
- masm.bind(&fallthrough);
-}
-
-void
-NativeRegExpMacroAssembler::CheckNotBackReferenceIgnoreCase(int start_reg, bool read_backward,
- Label* on_no_match, bool unicode)
-{
- JitSpew(SPEW_PREFIX "CheckNotBackReferenceIgnoreCase(%d, %d)", start_reg, unicode);
- Label fallthrough;
+ if (mode_ == CHAR16 && ignore_case) {
+ // We call a helper function for case-insensitive non-latin1 strings.
+ // Save volatile regs. temp1, temp2, and current_character
+ // don't need to be saved. current_position needs to be saved
+ // even if it's non-volatile, because we modify it to use as an argument.
+ LiveGeneralRegisterSet volatileRegs(GeneralRegisterSet::Volatile());
+ volatileRegs.addUnchecked(current_position);
+ volatileRegs.takeUnchecked(temp1);
+ volatileRegs.takeUnchecked(temp2);
+ volatileRegs.takeUnchecked(current_character);
+ masm.PushRegsInMask(volatileRegs);
- masm.loadPtr(register_location(start_reg), current_character); // Index of start of capture
- masm.loadPtr(register_location(start_reg + 1), temp1); // Index of end of capture
- masm.subPtr(current_character, temp1); // Length of capture.
+ // Parameters are
+ // Address byte_offset1 - Address captured substring's start.
+ // Address byte_offset2 - Address of current character position.
+ // size_t byte_length - length of capture in bytes(!)
- // The length of a capture should not be negative. This can only happen
- // if the end of the capture is unrecorded, or at a point earlier than
- // the start of the capture.
- masm.branchPtr(Assembler::LessThan, temp1, ImmWord(0), BranchOrBacktrack(on_no_match));
+ // Set byte_offset1.
+ // Start of capture, where current_character already holds string-end negative offset.
+ masm.addPtr(input_end_pointer, current_character);
- // If length is zero, either the capture is empty or it is completely
- // uncaptured. In either case succeed immediately.
- masm.branchPtr(Assembler::Equal, temp1, ImmWord(0), &fallthrough);
+ // Set byte_offset2.
+ // Found by adding negative string-end offset of current position
+ // to end of string.
+ masm.addPtr(input_end_pointer, current_position);
+ if (read_backward) {
+ // Offset by length when matching backwards.
+ masm.subPtr(temp1, current_position);
+ }
- // Check that there are sufficient characters left in the input.
- masm.movePtr(current_position, temp0);
- masm.addPtr(temp1, temp0);
- masm.branchPtr(Assembler::GreaterThan, temp0, ImmWord(0), BranchOrBacktrack(on_no_match));
+ masm.setupUnalignedABICall(temp1);
+ masm.passABIArg(current_character);
+ masm.passABIArg(current_position);
+ masm.passABIArg(temp0);
+ if (unicode) {
+ int (*fun)(const char16_t*, const char16_t*, size_t) = CaseInsensitiveCompareUCStrings;
+ masm.callWithABI(JS_FUNC_TO_DATA_PTR(void*, fun));
+ } else {
+ int (*fun)(const char16_t*, const char16_t*, size_t) = CaseInsensitiveCompareStrings;
+ masm.callWithABI(JS_FUNC_TO_DATA_PTR(void*, fun));
+ }
+ masm.storeCallInt32Result(temp1);
+ masm.PopRegsInMask(volatileRegs);
+ // Check if function returned non-zero for success or zero for failure.
+ masm.branchTest32(Assembler::Zero, temp1, temp1, BranchOrBacktrack(on_no_match));
- if (mode_ == ASCII) {
- Label success, fail;
+ // On success, advance position by length of capture
+ if (read_backward) {
+ masm.subPtr(temp0, current_position);
+ } else {
+ masm.addPtr(temp0, current_position);
+ }
+ } else {
+ MOZ_ASSERT(mode_ == ASCII || !ignore_case);
// Save register contents to make the registers available below. After
- // this, the temp0, temp2, and current_position registers are available.
+ // this, the temp1, temp2, and current_position registers are available.
masm.push(current_position);
+ // Make offset values into pointers
masm.addPtr(input_end_pointer, current_character); // Start of capture.
masm.addPtr(input_end_pointer, current_position); // Start of text to match against capture.
- masm.addPtr(current_position, temp1); // End of text to match against capture.
-
- Label loop, loop_increment;
- masm.bind(&loop);
- masm.load8ZeroExtend(Address(current_position, 0), temp0);
- masm.load8ZeroExtend(Address(current_character, 0), temp2);
- masm.branch32(Assembler::Equal, temp0, temp2, &loop_increment);
-
- // Mismatch, try case-insensitive match (converting letters to lower-case).
- masm.or32(Imm32(0x20), temp0); // Convert match character to lower-case.
-
- // Is temp0 a lowercase letter?
- Label convert_capture;
- masm.computeEffectiveAddress(Address(temp0, -'a'), temp2);
- masm.branch32(Assembler::BelowOrEqual, temp2, Imm32(static_cast<int32_t>('z' - 'a')),
- &convert_capture);
- // Latin-1: Check for values in range [224,254] but not 247.
- masm.sub32(Imm32(224 - 'a'), temp2);
- masm.branch32(Assembler::Above, temp2, Imm32(254 - 224), &fail);
-
- // Check for 247.
- masm.branch32(Assembler::Equal, temp2, Imm32(247 - 224), &fail);
+ if (read_backward) {
+ // Offset by length when matching backwards.
+ masm.subPtr(temp0, current_position);
+ }
- masm.bind(&convert_capture);
+ // End of text to match against capture (temp0 is pointer now)
+ masm.addPtr(current_position, temp0);
- // Also convert capture character.
- masm.load8ZeroExtend(Address(current_character, 0), temp2);
- masm.or32(Imm32(0x20), temp2);
+ Label success, fail, loop;
+ masm.bind(&loop);
- masm.branch32(Assembler::NotEqual, temp0, temp2, &fail);
+ // Load next character from each string.
+ if (mode_ == ASCII) {
+ masm.load8ZeroExtend(Address(current_character, 0), temp1);
+ masm.load8ZeroExtend(Address(current_position, 0), temp2);
+ } else {
+ masm.load16ZeroExtend(Address(current_character, 0), temp1);
+ masm.load16ZeroExtend(Address(current_position, 0), temp2);
+ }
- masm.bind(&loop_increment);
+ if (ignore_case) {
+ MOZ_ASSERT(mode_ == ASCII);
+ Label loop_increment, convert_match;
+
+ // Try exact match.
+ masm.branch32(Assembler::Equal, temp1, temp2, &loop_increment);
+
+ // Mismatch, try case-insensitive match (converting letters to lower-case).
+ masm.or32(Imm32(0x20), temp1); // Convert match character to lower-case.
+
+ // Is temp1 a lowercase letter [a,z]?
+ masm.computeEffectiveAddress(Address(temp1, -'a'), temp2);
+ masm.branch32(Assembler::BelowOrEqual, temp2, Imm32(static_cast<int32_t>('z' - 'a')),
+ &convert_match);
+ // Latin-1: Check for values in range [224,254] but not 247 (U+00F7 DIVISION SIGN).
+ masm.sub32(Imm32(224 - 'a'), temp2);
+ masm.branch32(Assembler::Above, temp2, Imm32(254 - 224), &fail);
+ // Check for 247.
+ masm.branch32(Assembler::Equal, temp2, Imm32(247 - 224), &fail);
+
+ // Capture character is lower case. Convert match character to lower case and compare
+ masm.bind(&convert_match);
+ // Reload latin1 character since temp2 was clobbered above
+ masm.load8ZeroExtend(Address(current_position, 0), temp2);
+ masm.or32(Imm32(0x20), temp2);
+ masm.branch32(Assembler::NotEqual, temp1, temp2, &fail);
+
+ masm.bind(&loop_increment);
+ } else {
+ // Fail if characters do not match.
+ masm.branch32(Assembler::NotEqual, temp1, temp2, &fail);
+ }
// Increment pointers into match and capture strings.
- masm.addPtr(Imm32(1), current_character);
- masm.addPtr(Imm32(1), current_position);
+ masm.addPtr(Imm32(char_size()), current_character);
+ masm.addPtr(Imm32(char_size()), current_position);
- // Compare to end of match, and loop if not done.
- masm.branchPtr(Assembler::Below, current_position, temp1, &loop);
+ // Loop if we have not reached the end of the match string.
+ masm.branchPtr(Assembler::Below, current_position, temp0, &loop);
masm.jump(&success);
- masm.bind(&fail);
-
// Restore original values before failing.
+ masm.bind(&fail);
masm.pop(current_position);
JumpOrBacktrack(on_no_match);
masm.bind(&success);
-
// Drop original character position value.
- masm.addToStackPtr(Imm32(sizeof(uintptr_t)));
+ masm.pop(temp0);
- // Compute new value of character position after the matched part.
+ // current_position is a pointer (now at the end of the consumed characters). Convert it back to an offset.
masm.subPtr(input_end_pointer, current_position);
- } else {
- MOZ_ASSERT(mode_ == CHAR16);
-
- // Note: temp1 needs to be saved/restored if it is volatile, as it is used after the call.
- LiveGeneralRegisterSet volatileRegs(GeneralRegisterSet::Volatile());
- volatileRegs.takeUnchecked(temp0);
- volatileRegs.takeUnchecked(temp2);
- masm.PushRegsInMask(volatileRegs);
- // Set byte_offset1.
- // Start of capture, where current_character already holds string-end negative offset.
- masm.addPtr(input_end_pointer, current_character);
-
- // Set byte_offset2.
- // Found by adding negative string-end offset of current position
- // to end of string.
- masm.addPtr(input_end_pointer, current_position);
-
- // Parameters are
- // Address byte_offset1 - Address captured substring's start.
- // Address byte_offset2 - Address of current character position.
- // size_t byte_length - length of capture in bytes(!)
- masm.setupUnalignedABICall(temp0);
- masm.passABIArg(current_character);
- masm.passABIArg(current_position);
- masm.passABIArg(temp1);
- if (!unicode) {
- int (*fun)(const char16_t*, const char16_t*, size_t) = CaseInsensitiveCompareStrings;
- masm.callWithABI(JS_FUNC_TO_DATA_PTR(void*, fun));
- } else {
- int (*fun)(const char16_t*, const char16_t*, size_t) = CaseInsensitiveCompareUCStrings;
- masm.callWithABI(JS_FUNC_TO_DATA_PTR(void*, fun));
+ if (read_backward) {
+ // Subtract match length if we matched backward
+ masm.addPtr(register_location(start_reg), current_position);
+ masm.subPtr(register_location(start_reg + 1), current_position);
}
- masm.storeCallInt32Result(temp0);
+ }
- masm.PopRegsInMask(volatileRegs);
+ // Fallthrough if capture length was zero
+ masm.bind(&fallthrough);
+}
- // Check if function returned non-zero for success or zero for failure.
- masm.branchTest32(Assembler::Zero, temp0, temp0, BranchOrBacktrack(on_no_match));
+void
+NativeRegExpMacroAssembler::CheckNotBackReference(int start_reg, bool read_backward, Label* on_no_match)
+{
+ JitSpew(SPEW_PREFIX "CheckNotBackReference(%d)", start_reg);
- // On success, increment position by length of capture.
- masm.addPtr(temp1, current_position);
- }
+ CheckNotBackReferenceImpl(start_reg, read_backward, on_no_match, /*unicode = */ false, /*ignore_case = */ false);
+}
- masm.bind(&fallthrough);
+void
+NativeRegExpMacroAssembler::CheckNotBackReferenceIgnoreCase(int start_reg, bool read_backward,
+ Label* on_no_match, bool unicode)
+{
+ JitSpew(SPEW_PREFIX "CheckNotBackReferenceIgnoreCase(%d, %d)", start_reg, unicode);
+
+ CheckNotBackReferenceImpl(start_reg, read_backward, on_no_match, unicode, /*ignore_case = */ true);
}
void
@@ -961,10 +943,13 @@ NativeRegExpMacroAssembler::LoadCurrentCharacter(int cp_offset, Label* on_end_of
{
JitSpew(SPEW_PREFIX "LoadCurrentCharacter(%d, %d)", cp_offset, characters);
- MOZ_ASSERT(cp_offset >= -1); // ^ and \b can look behind one character.
MOZ_ASSERT(cp_offset < (1<<30)); // Be sane! (And ensure negation works)
if (check_bounds)
- CheckPosition(cp_offset + characters - 1, on_end_of_input);
+ if (cp_offset >= 0) {
+ CheckPosition(cp_offset + characters - 1, on_end_of_input);
+ } else {
+ CheckPosition(cp_offset, on_end_of_input);
+ }
LoadCurrentCharacterUnchecked(cp_offset, characters);
}
@@ -972,9 +957,8 @@ void
NativeRegExpMacroAssembler::LoadCurrentCharacterUnchecked(int cp_offset, int characters)
{
JitSpew(SPEW_PREFIX "LoadCurrentCharacterUnchecked(%d, %d)", cp_offset, characters);
-
+ BaseIndex address(input_end_pointer, current_position, TimesOne, cp_offset * char_size());
if (mode_ == ASCII) {
- BaseIndex address(input_end_pointer, current_position, TimesOne, cp_offset);
if (characters == 4) {
masm.load32(address, current_character);
} else if (characters == 2) {
@@ -986,7 +970,6 @@ NativeRegExpMacroAssembler::LoadCurrentCharacterUnchecked(int cp_offset, int cha
} else {
MOZ_ASSERT(mode_ == CHAR16);
MOZ_ASSERT(characters <= 2);
- BaseIndex address(input_end_pointer, current_position, TimesOne, cp_offset * sizeof(char16_t));
if (characters == 2)
masm.load32(address, current_character);
else
@@ -1096,10 +1079,11 @@ NativeRegExpMacroAssembler::CheckBacktrackStackLimit()
masm.moveStackPtrTo(temp2);
masm.call(&stack_overflow_label_);
- masm.bind(&no_stack_overflow);
// Exit with an exception if the call failed.
masm.branchTest32(Assembler::Zero, temp0, temp0, &exit_with_exception_label_);
+
+ masm.bind(&no_stack_overflow);
}
void
@@ -1213,8 +1197,21 @@ void
NativeRegExpMacroAssembler::CheckPosition(int cp_offset, Label* on_outside_input)
{
JitSpew(SPEW_PREFIX "CheckPosition(%d)", cp_offset);
- masm.branchPtr(Assembler::GreaterThanOrEqual, current_position,
- ImmWord(-cp_offset * char_size()), BranchOrBacktrack(on_outside_input));
+ if (cp_offset >= 0) {
+ // end + current + offset >= end
+ // <=> current + offset >= 0
+ // <=> current >= -offset
+ masm.branchPtr(Assembler::GreaterThanOrEqual, current_position,
+ ImmWord(-cp_offset * char_size()), BranchOrBacktrack(on_outside_input));
+ } else {
+ // negative cp_offset means we're reading backwards, check against start of string
+ // Compute offset address
+ masm.computeEffectiveAddress(BaseIndex(input_end_pointer, current_position, TimesOne, cp_offset * char_size()), temp0);
+
+ // Compare to start of input.
+ Address inputStart(masm.getStackPointer(), offsetof(FrameData, inputStart));
+ masm.branchPtr(Assembler::GreaterThan, inputStart, temp0, BranchOrBacktrack(on_outside_input));
+ }
}
Label*
diff --git a/js/src/irregexp/NativeRegExpMacroAssembler.h b/js/src/irregexp/NativeRegExpMacroAssembler.h
index 3a04a33cf2..857900cabf 100644
--- a/js/src/irregexp/NativeRegExpMacroAssembler.h
+++ b/js/src/irregexp/NativeRegExpMacroAssembler.h
@@ -98,7 +98,7 @@ class MOZ_STACK_CLASS NativeRegExpMacroAssembler final : public RegExpMacroAssem
void AdvanceRegister(int reg, int by);
void Backtrack();
void Bind(jit::Label* label);
- void CheckAtStart(jit::Label* on_at_start);
+ void CheckAtStart(int cp_offset, jit::Label* on_at_start);
void CheckCharacter(unsigned c, jit::Label* on_equal);
void CheckCharacterAfterAnd(unsigned c, unsigned and_with, jit::Label* on_equal);
void CheckCharacterGT(char16_t limit, jit::Label* on_greater);
@@ -203,13 +203,17 @@ class MOZ_STACK_CLASS NativeRegExpMacroAssembler final : public RegExpMacroAssem
Vector<LabelPatch, 4, SystemAllocPolicy> labelPatches;
- // See RegExpMacroAssembler.cpp for the meaning of these registers.
+ // See NativeRegExpMacroAssembler.cpp for the meaning of these registers.
jit::Register input_end_pointer;
jit::Register current_character;
jit::Register current_position;
jit::Register backtrack_stack_pointer;
jit::Register temp0, temp1, temp2;
+ void CheckAtStartImpl(int cp_offset, jit::Label* on_cond, jit::Assembler::Condition cond);
+ void CheckNotBackReferenceImpl(int start_reg, bool read_backward, jit::Label* on_no_match,
+ bool unicode, bool ignore_case);
+
// The frame_pointer-relative location of a regexp register.
jit::Address register_location(int register_index) {
checkRegister(register_index);
diff --git a/js/src/irregexp/RegExpAST.h b/js/src/irregexp/RegExpAST.h
index 2cdf71aad8..37c85b7427 100644
--- a/js/src/irregexp/RegExpAST.h
+++ b/js/src/irregexp/RegExpAST.h
@@ -424,13 +424,9 @@ class RegExpBackReference : public RegExpTree
virtual RegExpBackReference* AsBackReference();
virtual bool IsBackReference();
virtual int min_match() override { return 0; }
- // The capture may not be completely parsed yet, if the reference occurs
- // before the capture. In the ordinary case, nothing has been captured yet,
- // so the back reference must have the length 0. If the back reference is
- // inside a lookbehind, effectively making it a forward reference, we return
- virtual int max_match() override {
- return capture_->body() ? capture_->max_match() : 0;
- }
+ // The back reference may be recursive, e.g. /(\2)(\1)/. To avoid infinite
+ // recursion, we give up. Ignorance is bliss.
+ int max_match() override { return kInfinity; }
int index() { return capture_->index(); }
RegExpCapture* capture() { return capture_; }
private:
diff --git a/js/src/irregexp/RegExpEngine.cpp b/js/src/irregexp/RegExpEngine.cpp
index 42787dc0f0..bf95b59dda 100644
--- a/js/src/irregexp/RegExpEngine.cpp
+++ b/js/src/irregexp/RegExpEngine.cpp
@@ -2010,8 +2010,9 @@ RegExpQuantifier::ToNode(int min,
alternation->AddAlternative(GuardedAlternative(body->ToNode(compiler, answer)));
}
answer = alternation;
- if (not_at_start && !compiler->read_backward())
+ if (not_at_start && !compiler->read_backward()) {
alternation->set_not_at_start();
+ }
}
return answer;
}
@@ -2218,9 +2219,7 @@ RegExpCapture::ToNode(RegExpTree* body,
int start_reg = RegExpCapture::StartRegister(index);
int end_reg = RegExpCapture::EndRegister(index);
if (compiler->read_backward()) {
- // std::swap(start_reg, end_reg);
- start_reg = RegExpCapture::EndRegister(index);
- end_reg = RegExpCapture::StartRegister(index);
+ std::swap(start_reg, end_reg);
}
RegExpNode* store_end = ActionNode::StorePosition(end_reg, true, on_success);
RegExpNode* body_node = body->ToNode(compiler, store_end);
@@ -2604,6 +2603,7 @@ Trace::PerformDeferredActions(LifoAlloc* alloc,
{
// The "+1" is to avoid a push_limit of zero if stack_limit_slack() is 1.
const int push_limit = (assembler->stack_limit_slack() + 1) / 2;
+ static const int kNoStore = INT32_MIN;
// Count pushes performed to force a stack limit check occasionally.
int pushes = 0;
@@ -2620,7 +2620,7 @@ Trace::PerformDeferredActions(LifoAlloc* alloc,
int value = 0;
bool absolute = false;
bool clear = false;
- int store_position = -1;
+ int store_position = kNoStore;
// This is a little tricky because we are scanning the actions in reverse
// historical order (newest first).
for (DeferredAction* action = actions_;
@@ -2641,7 +2641,7 @@ Trace::PerformDeferredActions(LifoAlloc* alloc,
// we can set undo_action to IGNORE if we know there is no value to
// restore.
undo_action = DEFER_RESTORE;
- MOZ_ASSERT(store_position == -1);
+ MOZ_ASSERT(store_position == kNoStore);
MOZ_ASSERT(!clear);
break;
}
@@ -2649,14 +2649,14 @@ Trace::PerformDeferredActions(LifoAlloc* alloc,
if (!absolute) {
value++;
}
- MOZ_ASSERT(store_position == -1);
+ MOZ_ASSERT(store_position == kNoStore);
MOZ_ASSERT(!clear);
undo_action = DEFER_RESTORE;
break;
case ActionNode::STORE_POSITION: {
Trace::DeferredCapture* pc =
static_cast<Trace::DeferredCapture*>(action);
- if (!clear && store_position == -1) {
+ if (!clear && store_position == kNoStore) {
store_position = pc->cp_offset();
}
@@ -2680,7 +2680,7 @@ Trace::PerformDeferredActions(LifoAlloc* alloc,
// Since we're scanning in reverse order, if we've already
// set the position we have to ignore historically earlier
// clearing operations.
- if (store_position == -1) {
+ if (store_position == kNoStore) {
clear = true;
}
undo_action = DEFER_RESTORE;
@@ -2710,7 +2710,7 @@ Trace::PerformDeferredActions(LifoAlloc* alloc,
}
// Perform the chronologically last action (or accumulated increment)
// for the register.
- if (store_position != -1) {
+ if (store_position != kNoStore) {
assembler->WriteCurrentPositionToRegister(reg, store_position);
} else if (clear) {
assembler->ClearRegisters(reg, reg);
@@ -2910,16 +2910,23 @@ EmitHat(RegExpCompiler* compiler, RegExpNode* on_success, Trace* trace)
Trace new_trace(*trace);
new_trace.InvalidateCurrentCharacter();
+ // A positive (> 0) cp_offset means we've already successfully matched a
+ // non-empty-width part of the pattern, and thus cannot be at or before the
+ // start of the subject string. We can thus skip both at-start and
+ // bounds-checks when loading the one-character lookbehind.
+ const bool may_be_at_or_before_subject_string_start = new_trace.cp_offset() <= 0;
+
jit::Label ok;
- if (new_trace.cp_offset() == 0) {
- // The start of input counts as a newline in this context, so skip to
- // ok if we are at the start.
- assembler->CheckAtStart(&ok);
+ if (may_be_at_or_before_subject_string_start) {
+ // The start of input counts as a newline in this context, so skip to ok if
+ // we are at the start.
+ assembler->CheckAtStart(new_trace.cp_offset(), &ok);
}
- // We already checked that we are not at the start of input so it must be
- // OK to load the previous character.
- assembler->LoadCurrentCharacter(new_trace.cp_offset() -1, new_trace.backtrack(), false);
+ // If we've already checked that we are not at the start of input, it's okay
+ // to load the previous character without bounds checks.
+ const bool can_skip_bounds_check = !may_be_at_or_before_subject_string_start;
+ assembler->LoadCurrentCharacter(new_trace.cp_offset() -1, new_trace.backtrack(), can_skip_bounds_check);
if (!assembler->CheckSpecialCharacterClass('n', new_trace.backtrack())) {
// Newline means \n, \r, 0x2028 or 0x2029.
@@ -2944,11 +2951,10 @@ EmitNotAfterLeadSurrogate(RegExpCompiler* compiler, RegExpNode* on_success, Trac
new_trace.InvalidateCurrentCharacter();
jit::Label ok;
- if (new_trace.cp_offset() == 0)
- assembler->CheckAtStart(&ok);
+ if (new_trace.cp_offset() <= 0) {
+ assembler->CheckAtStart(new_trace.cp_offset(), &ok);
+ }
- // We already checked that we are not at the start of input so it must be
- // OK to load the previous character.
assembler->LoadCurrentCharacter(new_trace.cp_offset() - 1, new_trace.backtrack(), false);
assembler->CheckCharacterInRange(unicode::LeadSurrogateMin, unicode::LeadSurrogateMax,
new_trace.backtrack());
@@ -2972,8 +2978,9 @@ EmitNotInSurrogatePair(RegExpCompiler* compiler, RegExpNode* on_success, Trace*
Trace new_trace(*trace);
new_trace.InvalidateCurrentCharacter();
- if (new_trace.cp_offset() == 0)
- assembler->CheckAtStart(&ok);
+ if (new_trace.cp_offset() <= 0) {
+ assembler->CheckAtStart(new_trace.cp_offset(), &ok);
+ }
// First check if next character is a trail surrogate.
assembler->LoadCurrentCharacter(new_trace.cp_offset(), new_trace.backtrack(), false);
@@ -3091,10 +3098,10 @@ AssertionNode::BacktrackIfPrevious(RegExpCompiler* compiler,
jit::Label* non_word = backtrack_if_previous == kIsNonWord ? new_trace.backtrack() : &fall_through;
jit::Label* word = backtrack_if_previous == kIsNonWord ? &fall_through : new_trace.backtrack();
- if (new_trace.cp_offset() == 0) {
+ if (new_trace.cp_offset() <= 0) {
// The start of input counts as a non-word character, so the question is
// decided if we are at the start.
- assembler->CheckAtStart(non_word);
+ assembler->CheckAtStart(new_trace.cp_offset(), non_word);
}
// We already checked that we are not at the start of input so it must be
// OK to load the previous character.
@@ -4152,7 +4159,7 @@ ChoiceNode::CalculatePreloadCharacters(RegExpCompiler* compiler, int eats_at_lea
RegExpNode*
TextNode::GetSuccessorOfOmnivorousTextNode(RegExpCompiler* compiler)
{
- if (read_backward()) return NULL;
+ if (read_backward()) return nullptr;
if (elements().length() != 1)
return nullptr;
@@ -4362,6 +4369,8 @@ ChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace)
// For now we just call all choices one after the other. The idea ultimately
// is to use the Dispatch table to try only the relevant ones.
for (size_t i = first_normal_choice; i < choice_count; i++) {
+ bool is_last = i == choice_count - 1;
+ bool fall_through_on_failure = !is_last;
GuardedAlternative alternative = alternatives()[i];
AlternativeGeneration* alt_gen = alt_gens.at(i);
alt_gen->quick_check_details.set_characters(preload_characters);
@@ -4377,20 +4386,20 @@ ChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace)
if (not_at_start_) new_trace.set_at_start(Trace::FALSE_VALUE);
alt_gen->expects_preload = preload_is_current;
bool generate_full_check_inline = false;
- if (try_to_emit_quick_check_for_alternative(i) &&
+ if (try_to_emit_quick_check_for_alternative(i == 0) &&
alternative.node()->EmitQuickCheck(compiler,
&new_trace,
preload_has_checked_bounds,
&alt_gen->possible_success,
&alt_gen->quick_check_details,
- i < choice_count - 1)) {
+ fall_through_on_failure)) {
// Quick check was generated for this choice.
preload_is_current = true;
preload_has_checked_bounds = true;
// On the last choice in the ChoiceNode we generated the quick
// check to fall through on possible success. So now we need to
// generate the full check inline.
- if (i == choice_count - 1) {
+ if (!fall_through_on_failure) {
macro_assembler->Bind(&alt_gen->possible_success);
new_trace.set_quick_check_performed(&alt_gen->quick_check_details);
new_trace.set_characters_preloaded(preload_characters);
@@ -4398,7 +4407,7 @@ ChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace)
generate_full_check_inline = true;
}
} else if (alt_gen->quick_check_details.cannot_match()) {
- if (i == choice_count - 1 && !greedy_loop) {
+ if (!fall_through_on_failure && !greedy_loop) {
macro_assembler->JumpOrBacktrack(trace->backtrack());
}
continue;
@@ -4412,7 +4421,7 @@ ChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace)
alt_gen->expects_preload = false;
new_trace.InvalidateCurrentCharacter();
}
- if (i < choice_count - 1) {
+ if (!is_last) {
new_trace.set_backtrack(&alt_gen->after);
}
generate_full_check_inline = true;
@@ -4450,12 +4459,14 @@ ChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace)
if (new_trace.actions() != nullptr) {
new_trace.set_flush_budget(new_flush_budget);
}
+ bool next_expects_preload =
+ i == choice_count - 1 ? false : alt_gens.at(i + 1)->expects_preload;
EmitOutOfLineContinuation(compiler,
&new_trace,
alternatives()[i],
alt_gen,
preload_characters,
- alt_gens.at(i + 1)->expects_preload);
+ next_expects_preload);
}
}
diff --git a/js/src/irregexp/RegExpEngine.h b/js/src/irregexp/RegExpEngine.h
index 0d760145f9..c665105d7c 100644
--- a/js/src/irregexp/RegExpEngine.h
+++ b/js/src/irregexp/RegExpEngine.h
@@ -524,7 +524,7 @@ class RegExpNode
int characters_filled_in,
bool not_at_start) = 0;
- static const int kNodeIsTooComplexForGreedyLoops = -1;
+ static const int kNodeIsTooComplexForGreedyLoops = INT32_MIN;
virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
@@ -1060,7 +1060,9 @@ class ChoiceNode : public RegExpNode
bool not_at_start() { return not_at_start_; }
void set_not_at_start() { not_at_start_ = true; }
void set_being_calculated(bool b) { being_calculated_ = b; }
- virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; }
+ virtual bool try_to_emit_quick_check_for_alternative(bool is_first) {
+ return true;
+ }
virtual RegExpNode* FilterASCII(int depth, bool ignore_case, bool unicode);
virtual bool read_backward() { return false; }
@@ -1114,7 +1116,9 @@ class NegativeLookaheadChoiceNode : public ChoiceNode
// starts by loading enough characters for the alternative that takes fewest
// characters, but on a negative lookahead the negative branch did not take
// part in that calculation (EatsAtLeast) so the assumptions don't hold.
- virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; }
+ bool try_to_emit_quick_check_for_alternative(bool is_first) override {
+ return !is_first;
+ }
virtual RegExpNode* FilterASCII(int depth, bool ignore_case, bool unicode);
};
diff --git a/js/src/irregexp/RegExpInterpreter.cpp b/js/src/irregexp/RegExpInterpreter.cpp
index eab428faa9..f53acfb606 100644
--- a/js/src/irregexp/RegExpInterpreter.cpp
+++ b/js/src/irregexp/RegExpInterpreter.cpp
@@ -529,7 +529,7 @@ irregexp::InterpretCode(JSContext* cx, const uint8_t* byteCode, const CharT* cha
}
BYTECODE(CHECK_AT_START)
- if (current == 0)
+ if (current + (insn >> BYTECODE_SHIFT) == 0)
pc = byteCode + Load32Aligned(pc + 4);
else
pc += BC_CHECK_AT_START_LENGTH;
diff --git a/js/src/irregexp/RegExpMacroAssembler.cpp b/js/src/irregexp/RegExpMacroAssembler.cpp
index acb78203bd..2c4ec67ef5 100644
--- a/js/src/irregexp/RegExpMacroAssembler.cpp
+++ b/js/src/irregexp/RegExpMacroAssembler.cpp
@@ -172,9 +172,9 @@ InterpretedRegExpMacroAssembler::Bind(jit::Label* label)
}
void
-InterpretedRegExpMacroAssembler::CheckAtStart(jit::Label* on_at_start)
+InterpretedRegExpMacroAssembler::CheckAtStart(int cp_offset, jit::Label* on_at_start)
{
- Emit(BC_CHECK_AT_START, 0);
+ Emit(BC_CHECK_AT_START, cp_offset);
EmitOrLink(on_at_start);
}
diff --git a/js/src/irregexp/RegExpMacroAssembler.h b/js/src/irregexp/RegExpMacroAssembler.h
index 06784ce853..4fa0ab5630 100644
--- a/js/src/irregexp/RegExpMacroAssembler.h
+++ b/js/src/irregexp/RegExpMacroAssembler.h
@@ -96,7 +96,7 @@ class MOZ_STACK_CLASS RegExpMacroAssembler
virtual void Backtrack() = 0;
virtual void Bind(jit::Label* label) = 0;
- virtual void CheckAtStart(jit::Label* on_at_start) = 0;
+ virtual void CheckAtStart(int cp_offset, jit::Label* on_at_start) = 0;
// Dispatch after looking the current character up in a 2-bits-per-entry
// map. The destinations vector has up to 4 labels.
@@ -238,7 +238,7 @@ class MOZ_STACK_CLASS InterpretedRegExpMacroAssembler final : public RegExpMacro
void AdvanceRegister(int reg, int by);
void Backtrack();
void Bind(jit::Label* label);
- void CheckAtStart(jit::Label* on_at_start);
+ void CheckAtStart(int cp_offset, jit::Label* on_at_start);
void CheckCharacter(unsigned c, jit::Label* on_equal);
void CheckCharacterAfterAnd(unsigned c, unsigned and_with, jit::Label* on_equal);
void CheckCharacterGT(char16_t limit, jit::Label* on_greater);
generated by cgit v1.2.3 (git 2.26.2) at 2024-08-16 01:26:45 +0000