diff options
Diffstat (limited to 'js/src')
| -rw-r--r-- | js/src/regexp/RegExpTypes.h | 51 | ||||
| -rw-r--r-- | js/src/regexp/moz.build | 1 | ||||
| -rw-r--r-- | js/src/regexp/regexp-macro-assembler-arch.h | 279 | ||||
| -rw-r--r-- | js/src/regexp/regexp-native-macro-assembler.cc | 1215 | ||||
| -rw-r--r-- | js/src/regexp/regexp-shim.cc | 7 | ||||
| -rw-r--r-- | js/src/regexp/regexp-shim.h | 32 |
6 files changed, 1572 insertions, 13 deletions
diff --git a/js/src/regexp/RegExpTypes.h b/js/src/regexp/RegExpTypes.h new file mode 100644 index 000000000..e260b5bb6 --- /dev/null +++ b/js/src/regexp/RegExpTypes.h @@ -0,0 +1,51 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * vim: set ts=8 sts=2 et sw=2 tw=80: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +// This file forward-defines Irregexp classes that need to be visible +// to the rest of Spidermonkey and re-exports them into js::irregexp. + +#ifndef regexp_RegExpTypes_h +#define regexp_RegExpTypes_h + +namespace js { +class MatchPairs; +} + +namespace v8 { +namespace internal { + +struct InputOutputData { + const void* inputStart; + const void* inputEnd; + + // Index into inputStart (in chars) at which to begin matching. + size_t startIndex; + + js::MatchPairs* matches; + + template <typename CharT> + InputOutputData(const CharT* inputStart, const CharT* inputEnd, + size_t startIndex, js::MatchPairs* matches) + : inputStart(inputStart), + inputEnd(inputEnd), + startIndex(startIndex), + matches(matches) + {} +}; + +} // namespace internal +} // namespace v8 + + +namespace js { +namespace irregexp { + +using InputOutputData = v8::internal::InputOutputData; + +} // namespace irregexp +} // namespace js + +#endif // regexp_RegExpTypes_h diff --git a/js/src/regexp/moz.build b/js/src/regexp/moz.build index 1ef280b7f..4caa4589c 100644 --- a/js/src/regexp/moz.build +++ b/js/src/regexp/moz.build @@ -22,6 +22,7 @@ SOURCES += [ 'regexp-interpreter.cc', 'regexp-macro-assembler-tracer.cc', 'regexp-macro-assembler.cc', + 'regexp-native-macro-assembler.cc', 'regexp-parser.cc', 'regexp-shim.cc', 'regexp-stack.cc', diff --git a/js/src/regexp/regexp-macro-assembler-arch.h b/js/src/regexp/regexp-macro-assembler-arch.h index 60b5c94de..1baa5ddd5 100644 --- a/js/src/regexp/regexp-macro-assembler-arch.h +++ b/js/src/regexp/regexp-macro-assembler-arch.h @@ -4,6 +4,10 @@ * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ +// Copyright 2020 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + // This file implements the NativeRegExpMacroAssembler interface for // SpiderMonkey. It provides the same interface as each of V8's // architecture-specific implementations. @@ -11,6 +15,277 @@ #ifndef RegexpMacroAssemblerArch_h #define RegexpMacroAssemblerArch_h -#include "regexp/regexp-shim.h" +#include "jit/MacroAssembler.h" +#include "regexp/regexp-macro-assembler.h" + +namespace v8 { +namespace internal { + +struct FrameData { + // Character position at the start of the input, stored as a + // negative offset from the end of the string (input_end_pointer_). + size_t inputStart; + + // The backtrack_stack_pointer_ register points to the top of the stack. + // This points to the bottom of the backtrack stack. + void* backtrackStackBase; + + // Copy of the input MatchPairs. + int32_t* matches; // pointer to capture array + int32_t numMatches; // size of capture array +}; + +class SMRegExpMacroAssembler final : public NativeRegExpMacroAssembler { + public: + SMRegExpMacroAssembler(JSContext* cx, Isolate* isolate, + js::jit::StackMacroAssembler& masm, Zone* zone, + Mode mode, uint32_t num_capture_registers); + virtual ~SMRegExpMacroAssembler() {} // Nothing to do here + + virtual int stack_limit_slack(); + virtual IrregexpImplementation Implementation(); + + virtual bool Succeed(); + virtual void Fail(); + + virtual void AdvanceCurrentPosition(int by); + virtual void PopCurrentPosition(); + virtual void PushCurrentPosition(); + virtual void SetCurrentPositionFromEnd(int by); + + virtual void Backtrack(); + virtual void Bind(Label* label); + virtual void GoTo(Label* label); + virtual void PushBacktrack(Label* label); + + virtual void CheckCharacter(uint32_t c, Label* on_equal); + virtual void CheckNotCharacter(uint32_t c, Label* on_not_equal); + virtual void CheckCharacterGT(uc16 limit, Label* on_greater); + virtual void CheckCharacterLT(uc16 limit, Label* on_less); + virtual void CheckCharacterAfterAnd(uint32_t c, uint32_t mask, + Label* on_equal); + virtual void CheckNotCharacterAfterAnd(uint32_t c, uint32_t mask, + Label* on_not_equal); + virtual void CheckNotCharacterAfterMinusAnd(uc16 c, uc16 minus, uc16 mask, + Label* on_not_equal); + virtual void CheckGreedyLoop(Label* on_tos_equals_current_position); + virtual void CheckCharacterInRange(uc16 from, uc16 to, Label* on_in_range); + virtual void CheckCharacterNotInRange(uc16 from, uc16 to, + Label* on_not_in_range); + virtual void CheckAtStart(int cp_offset, Label* on_at_start); + virtual void CheckNotAtStart(int cp_offset, Label* on_not_at_start); + virtual void CheckPosition(int cp_offset, Label* on_outside_input); + virtual void CheckBitInTable(Handle<ByteArray> table, Label* on_bit_set); + virtual bool CheckSpecialCharacterClass(uc16 type, Label* on_no_match); + virtual void CheckNotBackReference(int start_reg, bool read_backward, + Label* on_no_match); + virtual void CheckNotBackReferenceIgnoreCase(int start_reg, + bool read_backward, + Label* on_no_match); + + virtual void LoadCurrentCharacterImpl(int cp_offset, Label* on_end_of_input, + bool check_bounds, int characters, + int eats_at_least); + + virtual void AdvanceRegister(int reg, int by); + virtual void IfRegisterGE(int reg, int comparand, Label* if_ge); + virtual void IfRegisterLT(int reg, int comparand, Label* if_lt); + virtual void IfRegisterEqPos(int reg, Label* if_eq); + virtual void PopRegister(int register_index); + virtual void PushRegister(int register_index, + StackCheckFlag check_stack_limit); + virtual void ReadCurrentPositionFromRegister(int reg); + virtual void WriteCurrentPositionToRegister(int reg, int cp_offset); + virtual void ReadStackPointerFromRegister(int reg); + virtual void WriteStackPointerToRegister(int reg); + virtual void SetRegister(int register_index, int to); + virtual void ClearRegisters(int reg_from, int reg_to); + + virtual Handle<HeapObject> GetCode(Handle<String> source); + + private: + size_t frameSize_ = 0; + + void createStackFrame(); + void initFrameAndRegs(); + void successHandler(); + void exitHandler(); + void backtrackHandler(); + void stackOverflowHandler(); + + // Push a register on the backtrack stack. + void Push(js::jit::Register value); + + // Pop a value from the backtrack stack. + void Pop(js::jit::Register target); + + void CheckAtStartImpl(int cp_offset, Label* on_cond, + js::jit::Assembler::Condition cond); + void CheckCharacterImpl(js::jit::Imm32 c, Label* on_cond, + js::jit::Assembler::Condition cond); + void CheckCharacterAfterAndImpl(uint32_t c, uint32_t and_with, Label* on_cond, + bool negate); + void CheckCharacterInRangeImpl(uc16 from, uc16 to, Label* on_cond, + js::jit::Assembler::Condition cond); + void CheckNotBackReferenceImpl(int start_reg, bool read_backward, + Label* on_no_match, bool ignore_case); + + void LoadCurrentCharacterUnchecked(int cp_offset, int characters); + + void JumpOrBacktrack(Label* to); + + // MacroAssembler methods that take a Label can be called with a + // null label, which means that we should backtrack if we would jump + // to that label. This is a helper to avoid writing out the same + // logic a dozen times. + inline js::jit::Label* LabelOrBacktrack(Label* to) { + return to ? to->inner() : &backtrack_label_; + } + + void CheckBacktrackStackLimit(); + + static bool GrowBacktrackStack(RegExpStack* regexp_stack); + + static uint32_t CaseInsensitiveCompareStrings(const char16_t* substring1, + const char16_t* substring2, + size_t byteLength); + static uint32_t CaseInsensitiveCompareUCStrings(const char16_t* substring1, + const char16_t* substring2, + size_t byteLength); + + inline int char_size() { return static_cast<int>(mode_); } + inline js::jit::Scale factor() { + return mode_ == UC16 ? js::jit::TimesTwo : js::jit::TimesOne; + } + + js::jit::Address inputStart() { + return js::jit::Address(masm_.getStackPointer(), + offsetof(FrameData, inputStart)); + } + js::jit::Address backtrackStackBase() { + return js::jit::Address(masm_.getStackPointer(), + offsetof(FrameData, backtrackStackBase)); + } + js::jit::Address matches() { + return js::jit::Address(masm_.getStackPointer(), + offsetof(FrameData, matches)); + } + js::jit::Address numMatches() { + return js::jit::Address(masm_.getStackPointer(), + offsetof(FrameData, numMatches)); + } + + // The stack-pointer-relative location of a regexp register. + js::jit::Address register_location(int register_index) { + return js::jit::Address(masm_.getStackPointer(), + register_offset(register_index)); + } + + int32_t register_offset(int register_index) { + MOZ_ASSERT(register_index >= 0 && register_index <= kMaxRegister); + if (num_registers_ <= register_index) { + num_registers_ = register_index + 1; + } + static_assert(alignof(uintptr_t) <= alignof(FrameData)); + return sizeof(FrameData) + register_index * sizeof(uintptr_t*); + } + + JSContext* cx_; + js::jit::StackMacroAssembler& masm_; + + /* + * This assembler uses the following registers: + * + * - current_character_: + * Contains the character (or characters) currently being examined. + * Must be loaded using LoadCurrentCharacter before using any of the + * dispatch methods. After a matching pass for a global regexp, + * temporarily stores the index of capture start. + * - current_position_: + * Current position in input *as negative byte offset from end of string*. + * - input_end_pointer_: + * Points to byte after last character in the input. current_position_ is + * relative to this. + * - backtrack_stack_pointer_: + * Points to tip of the (heap-allocated) backtrack stack. The stack grows + * downward (like the native stack). + * - temp0_, temp1_, temp2_: + * Scratch registers. + * + * The native stack pointer is used to access arguments (InputOutputData), + * local variables (FrameData), and irregexp's internal virtual registers + * (see register_location). + */ + + js::jit::Register current_character_; + js::jit::Register current_position_; + js::jit::Register input_end_pointer_; + js::jit::Register backtrack_stack_pointer_; + js::jit::Register temp0_, temp1_, temp2_; + + js::jit::Label entry_label_; + js::jit::Label start_label_; + js::jit::Label backtrack_label_; + js::jit::Label success_label_; + js::jit::Label exit_label_; + js::jit::Label stack_overflow_label_; + js::jit::Label exit_with_exception_label_; + + // When we generate the code to push a backtrack label's address + // onto the backtrack stack, we don't know its final address. We + // have to patch it after linking. This is slightly delicate, as the + // Label itself (which is allocated on the stack) may not exist by + // the time we link. The approach is as follows: + // + // 1. When we push a label on the backtrack stack (PushBacktrack), + // we bind the label's patchOffset_ field to the offset within + // the code that should be overwritten. This works because each + // label is only pushed by a single instruction. + // + // 2. When we bind a label (Bind), we check to see if it has a + // bound patchOffset_. If it does, we create a LabelPatch mapping + // its patch offset to the offset of the label itself. + // + // 3. While linking the code, we walk the list of label patches + // and patch the code accordingly. + class LabelPatch { + public: + LabelPatch(js::jit::CodeOffset patchOffset, size_t labelOffset) + : patchOffset_(patchOffset), labelOffset_(labelOffset) {} + + js::jit::CodeOffset patchOffset_; + size_t labelOffset_ = 0; + }; + + js::Vector<LabelPatch, 4, js::SystemAllocPolicy> labelPatches_; + void AddLabelPatch(js::jit::CodeOffset patchOffset, size_t labelOffset) { + js::AutoEnterOOMUnsafeRegion oomUnsafe; + if (!labelPatches_.emplaceBack(patchOffset, labelOffset)) { + oomUnsafe.crash("Irregexp label patch"); + } + } + + Mode mode_; + int num_registers_; + int num_capture_registers_; + js::jit::LiveGeneralRegisterSet savedRegisters_; + + public: + using TableVector = + js::Vector<PseudoHandle<ByteArrayData>, 4, js::SystemAllocPolicy>; + TableVector& tables() { return tables_; } + + private: + TableVector tables_; + void AddTable(PseudoHandle<ByteArrayData> table) { + js::AutoEnterOOMUnsafeRegion oomUnsafe; + if (!tables_.append(std::move(table))) { + oomUnsafe.crash("Irregexp table append"); + } + } +}; + +} // namespace internal +} // namespace v8 -#endif // RegexpMacroAssemblerArch_h +#endif // RegexpMacroAssemblerArch_h diff --git a/js/src/regexp/regexp-native-macro-assembler.cc b/js/src/regexp/regexp-native-macro-assembler.cc new file mode 100644 index 000000000..15182ad71 --- /dev/null +++ b/js/src/regexp/regexp-native-macro-assembler.cc @@ -0,0 +1,1215 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * vim: set ts=8 sts=2 et sw=2 tw=80: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +// Copyright 2020 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "jit/Linker.h" +#include "regexp/regexp-macro-assembler-arch.h" +#include "regexp/regexp-stack.h" +#include "vm/MatchPairs.h" + +#include "jit/MacroAssembler-inl.h" + +namespace v8 { +namespace internal { + +using js::MatchPairs; +using js::jit::AbsoluteAddress; +using js::jit::Address; +using js::jit::AllocatableGeneralRegisterSet; +using js::jit::Assembler; +using js::jit::BaseIndex; +using js::jit::CodeLocationLabel; +using js::jit::GeneralRegisterBackwardIterator; +using js::jit::GeneralRegisterForwardIterator; +using js::jit::GeneralRegisterSet; +using js::jit::Imm32; +using js::jit::ImmPtr; +using js::jit::ImmWord; +using js::jit::JitCode; +using js::jit::Linker; +using js::jit::LiveGeneralRegisterSet; +using js::jit::Register; +using js::jit::Registers; +using js::jit::StackMacroAssembler; + +SMRegExpMacroAssembler::SMRegExpMacroAssembler(JSContext* cx, Isolate* isolate, + StackMacroAssembler& masm, + Zone* zone, Mode mode, + uint32_t num_capture_registers) + : NativeRegExpMacroAssembler(isolate, zone), + cx_(cx), + masm_(masm), + mode_(mode), + num_registers_(num_capture_registers), + num_capture_registers_(num_capture_registers) { + // Each capture has a start and an end register + MOZ_ASSERT(num_capture_registers_ % 2 == 0); + + 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(); + savedRegisters_ = js::jit::SavedNonVolatileRegisters(regs); + + masm_.jump(&entry_label_); // We'll generate the entry code later + masm_.bind(&start_label_); // and continue from here. +} + +int SMRegExpMacroAssembler::stack_limit_slack() { + return RegExpStack::kStackLimitSlack; +} + +void SMRegExpMacroAssembler::AdvanceCurrentPosition(int by) { + if (by != 0) { + masm_.addPtr(Imm32(by * char_size()), current_position_); + } +} + +void SMRegExpMacroAssembler::AdvanceRegister(int reg, int by) { + MOZ_ASSERT(reg >= 0 && reg < num_registers_); + if (by != 0) { + masm_.addPtr(Imm32(by), register_location(reg)); + } +} + +void SMRegExpMacroAssembler::Backtrack() { + // Check for an interrupt. We have to restart from the beginning if we + // are interrupted, so we only check for urgent interrupts. + js::jit::Label noInterrupt; + masm_.branchTest32( + Assembler::Zero, AbsoluteAddress(cx_->addressOfInterruptBits()), + Imm32(uint32_t(js::InterruptReason::CallbackUrgent)), &noInterrupt); + masm_.movePtr(ImmWord(js::RegExpRunStatus_Error), temp0_); + masm_.jump(&exit_label_); + masm_.bind(&noInterrupt); + + // Pop code location from backtrack stack and jump to location. + Pop(temp0_); + masm_.jump(temp0_); +} + +void SMRegExpMacroAssembler::Bind(Label* label) { + masm_.bind(label->inner()); + if (label->patchOffset_.bound()) { + AddLabelPatch(label->patchOffset_, label->pos()); + } +} + +// Check if current_position + cp_offset is the input start +void SMRegExpMacroAssembler::CheckAtStartImpl(int cp_offset, Label* on_cond, + Assembler::Condition cond) { + Address addr(current_position_, cp_offset * char_size()); + masm_.computeEffectiveAddress(addr, temp0_); + + masm_.branchPtr(cond, inputStart(), temp0_, + LabelOrBacktrack(on_cond)); +} + +void SMRegExpMacroAssembler::CheckAtStart(int cp_offset, Label* on_at_start) { + CheckAtStartImpl(cp_offset, on_at_start, Assembler::Equal); +} + +void SMRegExpMacroAssembler::CheckNotAtStart(int cp_offset, + Label* on_not_at_start) { + CheckAtStartImpl(cp_offset, on_not_at_start, Assembler::NotEqual); +} + +void SMRegExpMacroAssembler::CheckCharacterImpl(Imm32 c, Label* on_cond, + Assembler::Condition cond) { + masm_.branch32(cond, current_character_, c, LabelOrBacktrack(on_cond)); +} + +void SMRegExpMacroAssembler::CheckCharacter(uint32_t c, Label* on_equal) { + CheckCharacterImpl(Imm32(c), on_equal, Assembler::Equal); +} + +void SMRegExpMacroAssembler::CheckNotCharacter(uint32_t c, + Label* on_not_equal) { + CheckCharacterImpl(Imm32(c), on_not_equal, Assembler::NotEqual); +} + +void SMRegExpMacroAssembler::CheckCharacterGT(uc16 c, Label* on_greater) { + CheckCharacterImpl(Imm32(c), on_greater, Assembler::GreaterThan); +} + +void SMRegExpMacroAssembler::CheckCharacterLT(uc16 c, Label* on_less) { + CheckCharacterImpl(Imm32(c), on_less, Assembler::LessThan); +} + +// Bitwise-and the current character with mask and then check for a +// match with c. +void SMRegExpMacroAssembler::CheckCharacterAfterAndImpl(uint32_t c, + uint32_t mask, + Label* on_cond, + bool is_not) { + if (c == 0) { + Assembler::Condition cond = is_not ? Assembler::NonZero : Assembler::Zero; + masm_.branchTest32(cond, current_character_, Imm32(mask), + LabelOrBacktrack(on_cond)); + } else { + Assembler::Condition cond = is_not ? Assembler::NotEqual : Assembler::Equal; + masm_.move32(Imm32(mask), temp0_); + masm_.and32(current_character_, temp0_); + masm_.branch32(cond, temp0_, Imm32(c), LabelOrBacktrack(on_cond)); + } +} + +void SMRegExpMacroAssembler::CheckCharacterAfterAnd(uint32_t c, + uint32_t mask, + Label* on_equal) { + CheckCharacterAfterAndImpl(c, mask, on_equal, /*is_not =*/false); +} + +void SMRegExpMacroAssembler::CheckNotCharacterAfterAnd(uint32_t c, + uint32_t mask, + Label* on_not_equal) { + CheckCharacterAfterAndImpl(c, mask, on_not_equal, /*is_not =*/true); +} + + +// Subtract minus from the current character, then bitwise-and the +// result with mask, then check for a match with c. +void SMRegExpMacroAssembler::CheckNotCharacterAfterMinusAnd( + uc16 c, uc16 minus, uc16 mask, Label* on_not_equal) { + masm_.computeEffectiveAddress(Address(current_character_, -minus), temp0_); + if (c == 0) { + masm_.branchTest32(Assembler::NonZero, temp0_, Imm32(mask), + LabelOrBacktrack(on_not_equal)); + } else { + masm_.and32(Imm32(mask), temp0_); + masm_.branch32(Assembler::NotEqual, temp0_, Imm32(c), + LabelOrBacktrack(on_not_equal)); + } +} + +// If the current position matches the position stored on top of the backtrack +// stack, pops the backtrack stack and branches to the given label. +void SMRegExpMacroAssembler::CheckGreedyLoop(Label* on_equal) { + js::jit::Label fallthrough; + masm_.branchPtr(Assembler::NotEqual, Address(backtrack_stack_pointer_, 0), + current_position_, &fallthrough); + masm_.addPtr(Imm32(sizeof(void*)), backtrack_stack_pointer_); // Pop. + JumpOrBacktrack(on_equal); + masm_.bind(&fallthrough); +} + +void SMRegExpMacroAssembler::CheckCharacterInRangeImpl( + uc16 from, uc16 to, Label* on_cond, Assembler::Condition cond) { + // x is in [from,to] if unsigned(x - from) <= to - from + masm_.computeEffectiveAddress(Address(current_character_, -from), temp0_); + masm_.branch32(cond, temp0_, Imm32(to - from), LabelOrBacktrack(on_cond)); +} + +void SMRegExpMacroAssembler::CheckCharacterInRange(uc16 from, uc16 to, + Label* on_in_range) { + CheckCharacterInRangeImpl(from, to, on_in_range, Assembler::BelowOrEqual); +} + +void SMRegExpMacroAssembler::CheckCharacterNotInRange(uc16 from, uc16 to, + Label* on_not_in_range) { + CheckCharacterInRangeImpl(from, to, on_not_in_range, Assembler::Above); +} + +void SMRegExpMacroAssembler::CheckBitInTable(Handle<ByteArray> table, + Label* on_bit_set) { + // Claim ownership of the ByteArray from the current HandleScope. + // ByteArrays are allocated on the C++ heap and are (eventually) + // owned by the RegExpShared. + PseudoHandle<ByteArrayData> rawTable = table->takeOwnership(isolate()); + + masm_.movePtr(ImmPtr(rawTable->data()), temp0_); + + masm_.move32(Imm32(kTableMask), temp1_); + masm_.and32(current_character_, temp1_); + + masm_.load8ZeroExtend(BaseIndex(temp0_, temp1_, js::jit::TimesOne), temp0_); + masm_.branchTest32(Assembler::NonZero, temp0_, temp0_, + LabelOrBacktrack(on_bit_set)); + + // Transfer ownership of |rawTable| to the |tables_| vector. + AddTable(std::move(rawTable)); +} + +void SMRegExpMacroAssembler::CheckNotBackReferenceImpl(int start_reg, + bool read_backward, + Label* on_no_match, + bool ignore_case) { + js::jit::Label fallthrough; + + // 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), // index of start + current_character_); + masm_.loadPtr(register_location(start_reg + 1), temp0_); // index of end + masm_.subPtr(current_character_, temp0_); // length of capture + + // Capture registers are either both set or both cleared. + // If the capture length is zero, then the capture is either empty or cleared. + // Fall through in both cases. + masm_.branchPtr(Assembler::Equal, temp0_, ImmWord(0), &fallthrough); + + // Check that there are sufficient characters left in the input. + if (read_backward) { + // If start + len > current, there isn't enough room for a + // lookbehind backreference. + masm_.loadPtr(inputStart(), temp1_); + masm_.addPtr(temp0_, temp1_); + masm_.branchPtr(Assembler::GreaterThan, temp1_, current_position_, + LabelOrBacktrack(on_no_match)); + } else { + // 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), + LabelOrBacktrack(on_no_match)); + } + + if (mode_ == UC16 && ignore_case) { + // We call a helper function for case-insensitive non-latin1 strings. + + // Save volatile regs. temp1_ and temp2_ don't need to be saved. + LiveGeneralRegisterSet volatileRegs(GeneralRegisterSet::Volatile()); + volatileRegs.takeUnchecked(temp1_); + volatileRegs.takeUnchecked(temp2_); + masm_.PushRegsInMask(volatileRegs); + + // Parameters are + // Address captured - Address of captured substring's start. + // Address current - Address of current character position. + // size_t byte_length - length of capture (in bytes) + + // Compute |captured| + masm_.addPtr(input_end_pointer_, current_character_); + + // Compute |current| + masm_.addPtr(input_end_pointer_, current_position_); + if (read_backward) { + // Offset by length when matching backwards. + masm_.subPtr(temp0_, current_position_); + } + + masm_.setupUnalignedABICall(temp1_); + masm_.passABIArg(current_character_); + masm_.passABIArg(current_position_); + masm_.passABIArg(temp0_); + + bool unicode = true; // TODO: Fix V8 bug + if (unicode) { + uint32_t (*fun)(const char16_t*, const char16_t*, size_t) = + CaseInsensitiveCompareUCStrings; + masm_.callWithABI(JS_FUNC_TO_DATA_PTR(void*, fun)); + } else { + uint32_t (*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); + masm_.branchTest32(Assembler::Zero, temp1_, temp1_, + LabelOrBacktrack(on_no_match)); + + // On success, advance position by length of capture + if (read_backward) { + masm_.subPtr(temp0_, current_position_); + } else { + masm_.addPtr(temp0_, current_position_); + } + + masm_.bind(&fallthrough); + return; + } + + // We will be modifying current_position_. Save it in case the match fails. + masm_.push(current_position_); + + // Compute start of capture string + masm_.addPtr(input_end_pointer_, current_character_); + + // Compute start of match string + masm_.addPtr(input_end_pointer_, current_position_); + if (read_backward) { + // Offset by length when matching backwards. + masm_.subPtr(temp0_, current_position_); + } + + // Compute end of match string + masm_.addPtr(current_position_, temp0_); + + js::jit::Label success; + js::jit::Label fail; + js::jit::Label loop; + masm_.bind(&loop); + + // Load next character from each string. + if (mode_ == LATIN1) { + 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_); + } + + if (ignore_case) { + MOZ_ASSERT(mode_ == LATIN1); + // Try exact match. + js::jit::Label loop_increment; + masm_.branch32(Assembler::Equal, temp1_, temp2_, &loop_increment); + + // Mismatch. Try case-insensitive match. + // Force the match character to lower case (by setting bit 0x20) + // then check to see if it is a letter. + js::jit::Label convert_capture; + masm_.or32(Imm32(0x20), temp1_); + + // Check if it is in [a,z]. + masm_.computeEffectiveAddress(Address(temp1_, -'a'), temp2_); + masm_.branch32(Assembler::BelowOrEqual, temp2_, Imm32('z' - 'a'), + &convert_capture); + // Check for values in range [224,254]. + // Exclude 247 (U+00F7 DIVISION SIGN). + masm_.sub32(Imm32(224 - 'a'), temp2_); + masm_.branch32(Assembler::Above, temp2_, Imm32(254 - 224), &fail); + masm_.branch32(Assembler::Equal, temp2_, Imm32(247 - 224), &fail); + + // Match character is lower case. Convert capture character + // to lower case and compare. + masm_.bind(&convert_capture); + masm_.load8ZeroExtend(Address(current_character_, 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(char_size()), current_character_); + masm_.addPtr(Imm32(char_size()), current_position_); + + // Loop if we have not reached the end of the match string. + masm_.branchPtr(Assembler::Below, current_position_, temp0_, &loop); + masm_.jump(&success); + + // If we fail, restore current_position_ and branch. + masm_.bind(&fail); + masm_.pop(current_position_); + JumpOrBacktrack(on_no_match); + + masm_.bind(&success); + + // current_position_ is a pointer. Convert it back to an offset. + masm_.subPtr(input_end_pointer_, current_position_); + 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_); + } + + // Drop saved value of current_position_ + masm_.addToStackPtr(Imm32(sizeof(uintptr_t))); + + masm_.bind(&fallthrough); +} + +// Branch if a back-reference does not match a previous capture. +void SMRegExpMacroAssembler::CheckNotBackReference(int start_reg, + bool read_backward, + Label* on_no_match) { + CheckNotBackReferenceImpl(start_reg, read_backward, on_no_match, + /*ignore_case = */ false); +} + +void SMRegExpMacroAssembler::CheckNotBackReferenceIgnoreCase( + int start_reg, bool read_backward, Label* on_no_match) { + CheckNotBackReferenceImpl(start_reg, read_backward, on_no_match, + /*ignore_case = */ true); +} + +// Checks whether the given offset from the current position is +// inside the input string. +void SMRegExpMacroAssembler::CheckPosition(int cp_offset, + Label* on_outside_input) { + // Note: current_position_ is a (negative) byte offset relative to + // the end of the input string. + if (cp_offset >= 0) { + // end + current + offset >= end + // <=> current + offset >= 0 + // <=> current >= -offset + masm_.branchPtr(Assembler::GreaterThanOrEqual, current_position_, + ImmWord(-cp_offset * char_size()), + LabelOrBacktrack(on_outside_input)); + } else { + // Compute offset position + masm_.computeEffectiveAddress( + Address(current_position_, cp_offset * char_size()), temp0_); + + // Compare to start of input. + masm_.branchPtr(Assembler::GreaterThanOrEqual, inputStart(), temp0_, + LabelOrBacktrack(on_outside_input)); + } +} + +// This function attempts to generate special case code for character classes. +// Returns true if a special case is generated. +// Otherwise returns false and generates no code. +bool SMRegExpMacroAssembler::CheckSpecialCharacterClass(uc16 type, + Label* on_no_match) { + js::jit::Label* no_match = LabelOrBacktrack(on_no_match); + + // Note: throughout this function, range checks (c in [min, max]) + // are implemented by an unsigned (c - min) <= (max - min) check. + switch (type) { + case 's': { + // Match space-characters + if (mode_ != LATIN1) { + return false; + } + js::jit::Label success; + // One byte space characters are ' ', '\t'..'\r', and '\u00a0' (NBSP). + + // Check ' ' + masm_.branch32(Assembler::Equal, current_character_, Imm32(' '), + &success); + + // Check '\t'..'\r' + masm_.computeEffectiveAddress(Address(current_character_, -'\t'), + temp0_); + masm_.branch32(Assembler::BelowOrEqual, temp0_, Imm32('\r' - '\t'), + &success); + + // Check \u00a0. + masm_.branch32(Assembler::NotEqual, temp0_, Imm32(0x00a0 - '\t'), + no_match); + + masm_.bind(&success); + return true; + } + case 'S': + // The emitted code for generic character classes is good enough. + return false; + case 'd': + // Match latin1 digits ('0'-'9') + masm_.computeEffectiveAddress(Address(current_character_, -'0'), temp0_); + masm_.branch32(Assembler::Above, temp0_, Imm32('9' - '0'), no_match); + return true; + case 'D': + // Match anything except latin1 digits ('0'-'9') + masm_.computeEffectiveAddress(Address(current_character_, -'0'), temp0_); + masm_.branch32(Assembler::BelowOrEqual, temp0_, Imm32('9' - '0'), + no_match); + return true; + case '.': + // Match non-newlines. This excludes '\n' (0x0a), '\r' (0x0d), + // U+2028 LINE SEPARATOR, and U+2029 PARAGRAPH SEPARATOR. + // See https://tc39.es/ecma262/#prod-LineTerminator + + // To test for 0x0a and 0x0d efficiently, we XOR the input with 1. + // This converts 0x0a to 0x0b, and 0x0d to 0x0c, allowing us to + // test for the contiguous range 0x0b..0x0c. + masm_.move32(current_character_, temp0_); + masm_.xor32(Imm32(0x01), temp0_); + masm_.sub32(Imm32(0x0b), temp0_); + masm_.branch32(Assembler::BelowOrEqual, temp0_, Imm32(0x0c - 0x0b), + no_match); + + if (mode_ == UC16) { + // Compare original value to 0x2028 and 0x2029, using the already + // computed (current_char ^ 0x01 - 0x0b). I.e., check for + // 0x201d (0x2028 - 0x0b) or 0x201e. + masm_.sub32(Imm32(0x2028 - 0x0b), temp0_); + masm_.branch32(Assembler::BelowOrEqual, temp0_, Imm32(0x2029 - 0x2028), + no_match); + } + return true; + case 'w': + // \w matches the set of 63 characters defined in Runtime Semantics: + // WordCharacters. We use a static lookup table, which is defined in + // regexp-macro-assembler.cc. + // Note: if both Unicode and IgnoreCase are true, \w matches a + // larger set of characters. That case is handled elsewhere. + if (mode_ != LATIN1) { + masm_.branch32(Assembler::Above, current_character_, Imm32('z'), + no_match); + } + static_assert(arraysize(word_character_map) > unibrow::Latin1::kMaxChar); + masm_.movePtr(ImmPtr(word_character_map), temp0_); + masm_.load8ZeroExtend( + BaseIndex(temp0_, current_character_, js::jit::TimesOne), temp0_); + masm_.branchTest32(Assembler::Zero, temp0_, temp0_, no_match); + return true; + case 'W': { + // See 'w' above. + js::jit::Label done; + if (mode_ != LATIN1) { + masm_.branch32(Assembler::Above, current_character_, Imm32('z'), &done); + } + static_assert(arraysize(word_character_map) > unibrow::Latin1::kMaxChar); + masm_.movePtr(ImmPtr(word_character_map), temp0_); + masm_.load8ZeroExtend( + BaseIndex(temp0_, current_character_, js::jit::TimesOne), temp0_); + masm_.branchTest32(Assembler::NonZero, temp0_, temp0_, no_match); + if (mode_ != LATIN1) { + masm_.bind(&done); + } + return true; + } + //////////////////////////////////////////////////////////////////////// + // Non-standard classes (with no syntactic shorthand) used internally // + //////////////////////////////////////////////////////////////////////// + case '*': + // Match any character + return true; + case 'n': + // Match newlines. The opposite of '.'. See '.' above. + masm_.move32(current_character_, temp0_); + masm_.xor32(Imm32(0x01), temp0_); + masm_.sub32(Imm32(0x0b), temp0_); + if (mode_ == LATIN1) { + masm_.branch32(Assembler::Above, temp0_, Imm32(0x0c - 0x0b), no_match); + } else { + MOZ_ASSERT(mode_ == UC16); + js::jit::Label done; + masm_.branch32(Assembler::BelowOrEqual, temp0_, Imm32(0x0c - 0x0b), + &done); + + // Compare original value to 0x2028 and 0x2029, using the already + // computed (current_char ^ 0x01 - 0x0b). I.e., check for + // 0x201d (0x2028 - 0x0b) or 0x201e. + masm_.sub32(Imm32(0x2028 - 0x0b), temp0_); + masm_.branch32(Assembler::Above, temp0_, Imm32(0x2029 - 0x2028), + no_match); + masm_.bind(&done); + } + return true; + + // No custom implementation + default: + return false; + } +} + +void SMRegExpMacroAssembler::Fail() { + masm_.movePtr(ImmWord(js::RegExpRunStatus_Success_NotFound), temp0_); + masm_.jump(&exit_label_); +} + +void SMRegExpMacroAssembler::GoTo(Label* to) { + masm_.jump(LabelOrBacktrack(to)); +} + +void SMRegExpMacroAssembler::IfRegisterGE(int reg, int comparand, + Label* if_ge) { + masm_.branchPtr(Assembler::GreaterThanOrEqual, register_location(reg), + ImmWord(comparand), LabelOrBacktrack(if_ge)); +} + +void SMRegExpMacroAssembler::IfRegisterLT(int reg, int comparand, + Label* if_lt) { + masm_.branchPtr(Assembler::LessThan, register_location(reg), + ImmWord(comparand), LabelOrBacktrack(if_lt)); +} + +void SMRegExpMacroAssembler::IfRegisterEqPos(int reg, Label* if_eq) { + masm_.branchPtr(Assembler::Equal, register_location(reg), current_position_, + LabelOrBacktrack(if_eq)); +} + +// This is a word-for-word identical copy of the V8 code, which is +// duplicated in at least nine different places in V8 (one per +// supported architecture) with no differences outside of comments and +// formatting. It should be hoisted into the superclass. Once that is +// done upstream, this version can be deleted. +void SMRegExpMacroAssembler::LoadCurrentCharacterImpl(int cp_offset, + Label* on_end_of_input, + bool check_bounds, + int characters, + int eats_at_least) { + // It's possible to preload a small number of characters when each success + // path requires a large number of characters, but not the reverse. + MOZ_ASSERT(eats_at_least >= characters); + MOZ_ASSERT(cp_offset < (1 << 30)); // Be sane! (And ensure negation works) + + if (check_bounds) { + if (cp_offset >= 0) { + CheckPosition(cp_offset + eats_at_least - 1, on_end_of_input); + } else { + CheckPosition(cp_offset, on_end_of_input); + } + } + LoadCurrentCharacterUnchecked(cp_offset, characters); +} + +// Load the character (or characters) at the specified offset from the +// current position. Zero-extend to 32 bits. +void SMRegExpMacroAssembler::LoadCurrentCharacterUnchecked(int cp_offset, + int characters) { + BaseIndex address(input_end_pointer_, current_position_, js::jit::TimesOne, + cp_offset * char_size()); + if (mode_ == LATIN1) { + if (characters == 4) { + masm_.load32(address, current_character_); + } else if (characters == 2) { + masm_.load16ZeroExtend(address, current_character_); + } else { + MOZ_ASSERT(characters == 1); + masm_.load8ZeroExtend(address, current_character_); + } + } else { + MOZ_ASSERT(mode_ == UC16); + if (characters == 2) { + masm_.load32(address, current_character_); + } else { + MOZ_ASSERT(characters == 1); + masm_.load16ZeroExtend(address, current_character_); + } + } +} + +void SMRegExpMacroAssembler::PopCurrentPosition() { Pop(current_position_); } + +void SMRegExpMacroAssembler::PopRegister(int register_index) { + Pop(temp0_); + masm_.storePtr(temp0_, register_location(register_index)); +} + +void SMRegExpMacroAssembler::PushBacktrack(Label* label) { + MOZ_ASSERT(!label->is_bound()); + MOZ_ASSERT(!label->patchOffset_.bound()); + label->patchOffset_ = masm_.movWithPatch(ImmPtr(nullptr), temp0_); + MOZ_ASSERT(label->patchOffset_.bound()); + + Push(temp0_); + + CheckBacktrackStackLimit(); +} + +void SMRegExpMacroAssembler::PushCurrentPosition() { Push(current_position_); } + +void SMRegExpMacroAssembler::PushRegister(int register_index, + StackCheckFlag check_stack_limit) { + masm_.loadPtr(register_location(register_index), temp0_); + Push(temp0_); + if (check_stack_limit) { + CheckBacktrackStackLimit(); + } +} + +void SMRegExpMacroAssembler::ReadCurrentPositionFromRegister(int reg) { + masm_.loadPtr(register_location(reg), current_position_); +} + +void SMRegExpMacroAssembler::WriteCurrentPositionToRegister(int reg, + int cp_offset) { + if (cp_offset == 0) { + masm_.storePtr(current_position_, register_location(reg)); + } else { + Address addr(current_position_, cp_offset * char_size()); + masm_.computeEffectiveAddress(addr, temp0_); + masm_.storePtr(temp0_, register_location(reg)); + } +} + +// Note: The backtrack stack pointer is stored in a register as an +// offset from the stack top, not as a bare pointer, so that it is not +// corrupted if the backtrack stack grows (and therefore moves). +void SMRegExpMacroAssembler::ReadStackPointerFromRegister(int reg) { + masm_.loadPtr(register_location(reg), backtrack_stack_pointer_); + masm_.addPtr(backtrackStackBase(), backtrack_stack_pointer_); +} +void SMRegExpMacroAssembler::WriteStackPointerToRegister(int reg) { + masm_.movePtr(backtrack_stack_pointer_, temp0_); + masm_.subPtr(backtrackStackBase(), temp0_); + masm_.storePtr(temp0_, register_location(reg)); +} + +// When matching a regexp that is anchored at the end, this operation +// is used to try skipping the beginning of long strings. If the +// maximum length of a match is less than the length of the string, we +// can skip the initial len - max_len bytes. +void SMRegExpMacroAssembler::SetCurrentPositionFromEnd(int by) { + js::jit::Label after_position; + masm_.branchPtr(Assembler::GreaterThanOrEqual, current_position_, + ImmWord(-by * char_size()), &after_position); + masm_.movePtr(ImmWord(-by * char_size()), current_position_); + + // On RegExp code entry (where this operation is used), the character before + // the current position is expected to be already loaded. + // We have advanced the position, so it's safe to read backwards. + LoadCurrentCharacterUnchecked(-1, 1); + masm_.bind(&after_position); +} + +void SMRegExpMacroAssembler::SetRegister(int register_index, int to) { + MOZ_ASSERT(register_index >= num_capture_registers_); + masm_.storePtr(ImmWord(to), register_location(register_index)); +} + +// Returns true if a regexp match can be restarted (aka the regexp is global). +// The return value is not used anywhere, but we implement it to be safe. +bool SMRegExpMacroAssembler::Succeed() { + masm_.jump(&success_label_); + return global(); +} + +// Capture registers are initialized to input[-1] +void SMRegExpMacroAssembler::ClearRegisters(int reg_from, int reg_to) { + MOZ_ASSERT(reg_from <= reg_to); + masm_.loadPtr(inputStart(), temp0_); + masm_.subPtr(Imm32(char_size()), temp0_); + for (int reg = reg_from; reg <= reg_to; reg++) { + masm_.storePtr(temp0_, register_location(reg)); + } +} + +void SMRegExpMacroAssembler::Push(Register source) { + MOZ_ASSERT(source != backtrack_stack_pointer_); + + masm_.subPtr(Imm32(sizeof(void*)), backtrack_stack_pointer_); + masm_.storePtr(source, Address(backtrack_stack_pointer_, 0)); +} + +void SMRegExpMacroAssembler::Pop(Register target) { + MOZ_ASSERT(target != backtrack_stack_pointer_); + + masm_.loadPtr(Address(backtrack_stack_pointer_, 0), target); + masm_.addPtr(Imm32(sizeof(void*)), backtrack_stack_pointer_); +} + +void SMRegExpMacroAssembler::JumpOrBacktrack(Label* to) { + if (to) { + masm_.jump(to->inner()); + } else { + Backtrack(); + } +} + +// Generate a quick inline test for backtrack stack overflow. +// If the test fails, call an OOL handler to try growing the stack. +void SMRegExpMacroAssembler::CheckBacktrackStackLimit() { + js::jit::Label no_stack_overflow; + masm_.branchPtr( + Assembler::BelowOrEqual, + AbsoluteAddress(isolate()->regexp_stack()->limit_address_address()), + backtrack_stack_pointer_, &no_stack_overflow); + + masm_.call(&stack_overflow_label_); + + // Exit with an exception if the call failed + masm_.branchTest32(Assembler::Zero, temp0_, temp0_, + &exit_with_exception_label_); + + masm_.bind(&no_stack_overflow); +} + +// This is used to sneak an OOM through the V8 layer. +static Handle<HeapObject> DummyCode() { + return Handle<HeapObject>::fromHandleValue(JS::UndefinedHandleValue); +} + +// Finalize code. This is called last, so that we know how many +// registers we need. +Handle<HeapObject> SMRegExpMacroAssembler::GetCode(Handle<String> source) { + if (!cx_->realm()->ensureJitRealmExists(cx_)) { + return DummyCode(); + } + + masm_.bind(&entry_label_); + + createStackFrame(); + initFrameAndRegs(); + + masm_.jump(&start_label_); + + successHandler(); + exitHandler(); + backtrackHandler(); + stackOverflowHandler(); + + Linker linker(masm_); + JitCode* code = linker.newCode(cx_, js::jit::CodeKind::RegExp); + if (!code) { + return DummyCode(); + } + + for (LabelPatch& lp : labelPatches_) { + Assembler::PatchDataWithValueCheck(CodeLocationLabel(code, lp.patchOffset_), + ImmPtr(code->raw() + lp.labelOffset_), + ImmPtr(nullptr)); + } + + return Handle<HeapObject>(JS::PrivateGCThingValue(code), isolate()); +} + +/* + * The stack will have the following structure: + * sp-> - FrameData + * - inputStart + * - backtrack stack base + * - matches + * - numMatches + * - Registers + * - Capture positions + * - Scratch registers + * --- frame alignment --- + * - Saved register area + * - Return address + */ +void SMRegExpMacroAssembler::createStackFrame() { +#ifdef JS_CODEGEN_ARM64 + // ARM64 communicates stack address via SP, but uses a pseudo-sp (PSP) for + // addressing. The register we use for PSP may however also be used by + // calling code, and it is nonvolatile, so save it. Do this as a special + // case first because the generic save/restore code needs the PSP to be + // initialized already. + MOZ_ASSERT(js::jit::PseudoStackPointer64.Is(masm_.GetStackPointer64())); + masm_.Str(js::jit::PseudoStackPointer64, + vixl::MemOperand(js::jit::sp, -16, vixl::PreIndex)); + + // Initialize the PSP from the SP. + masm_.initPseudoStackPtr(); +#endif + + // Push non-volatile registers which might be modified by jitcode. + size_t pushedNonVolatileRegisters = 0; + for (GeneralRegisterForwardIterator iter(savedRegisters_); iter.more(); + ++iter) { + masm_.Push(*iter); + pushedNonVolatileRegisters++; + } + + // The pointer to InputOutputData is passed as the first argument. + // On x86 we have to load it off the stack into temp0_. + // On other platforms it is already in a register. +#ifdef JS_CODEGEN_X86 + Address ioDataAddr(masm_.getStackPointer(), + (pushedNonVolatileRegisters + 1) * sizeof(void*)); + masm_.loadPtr(ioDataAddr, temp0_); +#else + if (js::jit::IntArgReg0 != temp0_) { + masm_.movePtr(js::jit::IntArgReg0, temp0_); + } +#endif + + // Start a new stack frame. + size_t frameBytes = sizeof(FrameData) + num_registers_ * sizeof(void*); + frameSize_ = js::jit::StackDecrementForCall(js::jit::ABIStackAlignment, + masm_.framePushed(), frameBytes); + masm_.reserveStack(frameSize_); + masm_.checkStackAlignment(); + + // Check if we have space on the stack. Use the *NoInterrupt stack limit to + // avoid failing repeatedly when the regex code is called from Ion JIT code. + // (See bug 1208819) + js::jit::Label stack_ok; + AbsoluteAddress limit_addr(cx_->addressOfJitStackLimitNoInterrupt()); + masm_.branchStackPtrRhs(Assembler::Below, limit_addr, &stack_ok); + + // There is not enough space on the stack. Exit with an exception. + masm_.movePtr(ImmWord(js::RegExpRunStatus_Error), temp0_); + masm_.jump(&exit_label_); + + masm_.bind(&stack_ok); +} + +void SMRegExpMacroAssembler::initFrameAndRegs() { + // At this point, an uninitialized stack frame has been created, + // and the address of the InputOutputData is in temp0_. + Register ioDataReg = temp0_; + + Register matchesReg = temp1_; + masm_.loadPtr(Address(ioDataReg, offsetof(InputOutputData, matches)), + matchesReg); + + // Initialize output registers + masm_.loadPtr(Address(matchesReg, MatchPairs::offsetOfPairs()), temp2_); + masm_.storePtr(temp2_, matches()); + masm_.load32(Address(matchesReg, MatchPairs::offsetOfPairCount()), temp2_); + masm_.store32(temp2_, numMatches()); + +#ifdef DEBUG + // Bounds-check numMatches. + js::jit::Label enoughRegisters; + masm_.branchPtr(Assembler::GreaterThanOrEqual, temp2_, + ImmWord(num_capture_registers_ / 2), &enoughRegisters); + masm_.assumeUnreachable("Not enough output pairs for RegExp"); + masm_.bind(&enoughRegisters); +#endif + + // Load input start pointer. + masm_.loadPtr(Address(ioDataReg, offsetof(InputOutputData, inputStart)), + current_position_); + + // Load input end pointer + masm_.loadPtr(Address(ioDataReg, offsetof(InputOutputData, inputEnd)), + input_end_pointer_); + + // Set up input position to be negative offset from string end. + masm_.subPtr(input_end_pointer_, current_position_); + + // Store inputStart + masm_.storePtr(current_position_, inputStart()); + + // Load start index + Register startIndexReg = temp1_; + masm_.loadPtr(Address(ioDataReg, offsetof(InputOutputData, startIndex)), + startIndexReg); + masm_.computeEffectiveAddress( + BaseIndex(current_position_, startIndexReg, factor()), current_position_); + + // Initialize current_character_. + // Load newline if index is at start, or previous character otherwise. + js::jit::Label start_regexp; + js::jit::Label load_previous_character; + masm_.branchPtr(Assembler::NotEqual, startIndexReg, ImmWord(0), + &load_previous_character); + masm_.movePtr(ImmWord('\n'), current_character_); + masm_.jump(&start_regexp); + + masm_.bind(&load_previous_character); + LoadCurrentCharacterUnchecked(-1, 1); + masm_.bind(&start_regexp); + + // Initialize captured registers with inputStart - 1 + MOZ_ASSERT(num_capture_registers_ > 0); + Register inputStartMinusOneReg = temp2_; + masm_.loadPtr(inputStart(), inputStartMinusOneReg); + masm_.subPtr(Imm32(char_size()), inputStartMinusOneReg); + if (num_capture_registers_ > 8) { + masm_.movePtr(ImmWord(register_offset(0)), temp1_); + js::jit::Label init_loop; + masm_.bind(&init_loop); + masm_.storePtr(inputStartMinusOneReg, BaseIndex(masm_.getStackPointer(), + temp1_, js::jit::TimesOne)); + masm_.addPtr(ImmWord(sizeof(void*)), temp1_); + masm_.branchPtr(Assembler::LessThan, temp1_, + ImmWord(register_offset(num_capture_registers_)), + &init_loop); + } else { + // Unroll the loop + for (int i = 0; i < num_capture_registers_; i++) { + masm_.storePtr(inputStartMinusOneReg, register_location(i)); + } + } + + // Initialize backtrack stack pointer + masm_.loadPtr(AbsoluteAddress(isolate()->top_of_regexp_stack()), + backtrack_stack_pointer_); + masm_.storePtr(backtrack_stack_pointer_, backtrackStackBase()); +} + +void SMRegExpMacroAssembler::successHandler() { + MOZ_ASSERT(success_label_.used()); + masm_.bind(&success_label_); + + // Copy captures to the MatchPairs pointed to by the InputOutputData. + // Captures are stored as positions, which are negative byte offsets + // from the end of the string. We must convert them to actual + // indices. + // + // Index: [ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][END] + // Pos (1-byte): [-6 ][-5 ][-4 ][-3 ][-2 ][-1 ][ 0 ] // IS = -6 + // Pos (2-byte): [-12][-10][-8 ][-6 ][-4 ][-2 ][ 0 ] // IS = -12 + // + // To convert a position to an index, we subtract InputStart, and + // divide the result by char_size. + Register matchesReg = temp1_; + masm_.loadPtr(matches(), matchesReg); + + Register inputStartReg = temp2_; + masm_.loadPtr(inputStart(), inputStartReg); + + for (int i = 0; i < num_capture_registers_; i++) { + masm_.loadPtr(register_location(i), temp0_); + masm_.subPtr(inputStartReg, temp0_); + if (mode_ == UC16) { + masm_.rshiftPtrArithmetic(Imm32(1), temp0_); + } + masm_.store32(temp0_, Address(matchesReg, i * sizeof(int32_t))); + } + + masm_.movePtr(ImmWord(js::RegExpRunStatus_Success), temp0_); + // This falls through to the exit handler. +} + +void SMRegExpMacroAssembler::exitHandler() { + masm_.bind(&exit_label_); + + if (temp0_ != js::jit::ReturnReg) { + masm_.movePtr(temp0_, js::jit::ReturnReg); + } + + masm_.freeStack(frameSize_); + + // Restore registers which were saved on entry + for (GeneralRegisterBackwardIterator iter(savedRegisters_); iter.more(); + ++iter) { + masm_.Pop(*iter); + } + +#ifdef JS_CODEGEN_ARM64 + // Now restore the value that was in the PSP register on entry, and return. + + // Obtain the correct SP from the PSP. + masm_.Mov(js::jit::sp, js::jit::PseudoStackPointer64); + + // Restore the saved value of the PSP register, this value is whatever the + // caller had saved in it, not any actual SP value, and it must not be + // overwritten subsequently. + masm_.Ldr(js::jit::PseudoStackPointer64, + vixl::MemOperand(js::jit::sp, 16, vixl::PostIndex)); + + // Perform a plain Ret(), as abiret() will move SP <- PSP and that is wrong. + masm_.Ret(vixl::lr); +#else + masm_.abiret(); +#endif + + if (exit_with_exception_label_.used()) { + masm_.bind(&exit_with_exception_label_); + + // Exit with an error result to signal thrown exception + masm_.movePtr(ImmWord(js::RegExpRunStatus_Error), temp0_); + masm_.jump(&exit_label_); + } +} + +void SMRegExpMacroAssembler::backtrackHandler() { + if (!backtrack_label_.used()) { + return; + } + masm_.bind(&backtrack_label_); + Backtrack(); +} + +void SMRegExpMacroAssembler::stackOverflowHandler() { + if (!stack_overflow_label_.used()) { + return; + } + + // Called if the backtrack-stack limit has been hit. + // NOTE: depending on architecture, the call may have + // changed the stack pointer. We adjust for that below. + masm_.bind(&stack_overflow_label_); + + // Load argument + masm_.movePtr(ImmPtr(isolate()->regexp_stack()), temp1_); + + // Save registers before calling C function + LiveGeneralRegisterSet volatileRegs(GeneralRegisterSet::Volatile()); + +#ifdef JS_USE_LINK_REGISTER + masm.pushReturnAddress(); +#endif + + // Adjust for the return address on the stack. + size_t frameOffset = sizeof(void*); + + volatileRegs.takeUnchecked(temp0_); + volatileRegs.takeUnchecked(temp1_); + masm_.PushRegsInMask(volatileRegs); + + masm_.setupUnalignedABICall(temp0_); + masm_.passABIArg(temp1_); + masm_.callWithABI(JS_FUNC_TO_DATA_PTR(void*, GrowBacktrackStack)); + masm_.storeCallBoolResult(temp0_); + + masm_.PopRegsInMask(volatileRegs); + + // If GrowBacktrackStack returned false, we have failed to grow the + // stack, and must exit with a stack-overflow exception. Do this in + // the caller so that the stack is adjusted by our return instruction. + js::jit::Label overflow_return; + masm_.branchTest32(Assembler::Zero, temp0_, temp0_, &overflow_return); + + // Otherwise, store the new backtrack stack base and recompute the new + // top of the stack. + Address bsbAddress(masm_.getStackPointer(), + offsetof(FrameData, backtrackStackBase) + frameOffset); + masm_.subPtr(bsbAddress, backtrack_stack_pointer_); + + masm_.loadPtr(AbsoluteAddress(isolate()->top_of_regexp_stack()), temp1_); + masm_.storePtr(temp1_, bsbAddress); + masm_.addPtr(temp1_, backtrack_stack_pointer_); + + // Resume execution in calling code. + masm_.bind(&overflow_return); + masm_.ret(); +} + +// This is only used by tracing code. +// The return value doesn't matter. +RegExpMacroAssembler::IrregexpImplementation +SMRegExpMacroAssembler::Implementation() { + return kBytecodeImplementation; +} + +/*static */ +uint32_t SMRegExpMacroAssembler::CaseInsensitiveCompareStrings( + const char16_t* substring1, const char16_t* substring2, size_t byteLength) { + js::AutoUnsafeCallWithABI unsafe; + + MOZ_ASSERT(byteLength % sizeof(char16_t) == 0); + size_t length = byteLength / sizeof(char16_t); + + for (size_t i = 0; i < length; i++) { + char16_t c1 = substring1[i]; + char16_t c2 = substring2[i]; + if (c1 != c2) { + c1 = js::unicode::ToUpperCase(c1); + c2 = js::unicode::ToUpperCase(c2); + if (c1 != c2) { + return 0; + } + } + } + + return 1; +} + +/*static */ +uint32_t SMRegExpMacroAssembler::CaseInsensitiveCompareUCStrings( + const char16_t* substring1, const char16_t* substring2, size_t byteLength) { + js::AutoUnsafeCallWithABI unsafe; + + MOZ_ASSERT(byteLength % sizeof(char16_t) == 0); + size_t length = byteLength / sizeof(char16_t); + + for (size_t i = 0; i < length; i++) { + char16_t c1 = substring1[i]; + char16_t c2 = substring2[i]; + if (c1 != c2) { + c1 = js::unicode::FoldCase(c1); + c2 = js::unicode::FoldCase(c2); + if (c1 != c2) { + return 0; + } + } + } + + return 1; +} + +/* static */ +bool SMRegExpMacroAssembler::GrowBacktrackStack(RegExpStack* regexp_stack) { + js::AutoUnsafeCallWithABI unsafe; + size_t size = regexp_stack->stack_capacity(); + return !!regexp_stack->EnsureCapacity(size * 2); +} + +} // namespace internal +} // namespace v8 diff --git a/js/src/regexp/regexp-shim.cc b/js/src/regexp/regexp-shim.cc index 773c17ead..3f3fa40eb 100644 --- a/js/src/regexp/regexp-shim.cc +++ b/js/src/regexp/regexp-shim.cc @@ -11,6 +11,7 @@ #include <iostream> #include "regexp/regexp-shim.h" +#include "regexp/regexp-stack.h" namespace v8 { namespace internal { @@ -73,6 +74,8 @@ Handle<T>::Handle(T object, Isolate* isolate) : location_(isolate->getHandleLocation(JS::Value(object))) {} template Handle<ByteArray>::Handle(ByteArray b, Isolate* isolate); +template Handle<HeapObject>::Handle(JS::Value v, Isolate* isolate); +template Handle<JSRegExp>::Handle(JSRegExp re, Isolate* isolate); template Handle<String>::Handle(String s, Isolate* isolate); template <typename T> @@ -150,6 +153,10 @@ std::unique_ptr<char[]> String::ToCString() { return std::unique_ptr<char[]>(); } +byte* Isolate::top_of_regexp_stack() const { + return reinterpret_cast<byte*>(regexpStack_->memory_top_address_address()); +} + Handle<ByteArray> Isolate::NewByteArray(int length, AllocationType alloc) { MOZ_RELEASE_ASSERT(length >= 0); diff --git a/js/src/regexp/regexp-shim.h b/js/src/regexp/regexp-shim.h index 462e396f4..942fcf733 100644 --- a/js/src/regexp/regexp-shim.h +++ b/js/src/regexp/regexp-shim.h @@ -22,7 +22,9 @@ #include <cctype> #include "jit/Label.h" +#include "jit/shared/Assembler-shared.h" #include "js/Value.h" +#include "regexp/RegExpTypes.h" #include "regexp/util/flags.h" #include "regexp/util/vector.h" #include "regexp/util/zone.h" @@ -571,10 +573,8 @@ class ByteArray : public HeapObject { ByteArrayData* inner() const { return static_cast<ByteArrayData*>(value_.toPrivate()); } - PseudoHandle<ByteArrayData> takeOwnership(Isolate* isolate); - - friend class SMRegExpMacroAssembler; public: + PseudoHandle<ByteArrayData> takeOwnership(Isolate* isolate); byte get(uint32_t index) { MOZ_ASSERT(index < length()); return inner()->data()[index]; @@ -674,15 +674,19 @@ class MOZ_NONHEAP_CLASS Handle { }; inline ObjectRef operator->() const { return ObjectRef{**this}; } + static Handle<T> fromHandleValue(JS::HandleValue handle) { + return Handle(handle.address()); + } + private: - Handle(JS::Value* location) : location_(location) {} + Handle(const JS::Value* location) : location_(location) {} template <typename> friend class Handle; template <typename> friend class MaybeHandle; - JS::Value* location_; + const JS::Value* location_; }; // A Handle can be converted into a MaybeHandle. Converting a MaybeHandle @@ -985,9 +989,13 @@ using Factory = Isolate; class Isolate { public: //********** Isolate code **********// - RegExpStack* regexp_stack() const { return regexp_stack_; } - bool has_pending_exception() { return cx()->isExceptionPending(); } - void StackOverflow() { js::ReportOverRecursed(cx()); } + RegExpStack* regexp_stack() const { return regexpStack_; } + byte* top_of_regexp_stack() const; + + // This is called from inside no-GC code. Instead of suppressing GC + // to allocate the error, we return false from Execute and call + // ReportOverRecursed in the caller. + void StackOverflow() {} #ifndef V8_INTL_SUPPORT unibrow::Mapping<unibrow::Ecma262UnCanonicalize>* jsregexp_uncanonicalize() { @@ -1066,7 +1074,7 @@ private: friend class HandleScope; JSContext* cx_; - RegExpStack* regexp_stack_; + RegExpStack* regexpStack_; Counters counters_; }; @@ -1101,7 +1109,6 @@ class Code : public HeapObject { c.value_ = JS::PrivateGCThingValue(JS::Value(object).toGCThing()); return c; } -private: js::jit::JitCode* inner() { return value_.toGCThing()->as<js::jit::JitCode>(); } @@ -1124,7 +1131,7 @@ class Label { public: Label() : inner_(js::jit::Label()) {} - operator js::jit::Label*() { return &inner_; } + js::jit::Label* inner() { return &inner_; } void Unuse() { inner_.reset(); } @@ -1138,6 +1145,9 @@ class Label { private: js::jit::Label inner_; + js::jit::CodeOffset patchOffset_; + + friend class SMRegExpMacroAssembler; }; // TODO: Map flags to jitoptions |