| // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| // A simple interpreter for the Irregexp byte code. |
| |
| #include <memory> |
| #include <utility> |
| |
| #include "heap/safepoint.h" |
| #include "vm/regexp_interpreter.h" |
| |
| #include "platform/unicode.h" |
| #include "vm/object.h" |
| #include "vm/regexp_assembler.h" |
| #include "vm/regexp_bytecodes.h" |
| #include "vm/unibrow-inl.h" |
| #include "vm/unibrow.h" |
| |
| namespace dart { |
| |
| DEFINE_FLAG(bool, trace_regexp_bytecodes, false, "trace_regexp_bytecodes"); |
| DEFINE_FLAG(int, |
| regexp_backtrack_stack_size_kb, |
| 256, |
| "Size of backtracking stack"); |
| |
| typedef unibrow::Mapping<unibrow::Ecma262Canonicalize> Canonicalize; |
| |
| template <typename Char> |
| static bool BackRefMatchesNoCase(Canonicalize* interp_canonicalize, |
| intptr_t from, |
| intptr_t current, |
| intptr_t len, |
| const String& subject, |
| bool unicode); |
| |
| template <> |
| bool BackRefMatchesNoCase<uint16_t>(Canonicalize* interp_canonicalize, |
| intptr_t from, |
| intptr_t current, |
| intptr_t len, |
| const String& subject, |
| bool unicode) { |
| Bool& ret = Bool::Handle(); |
| if (unicode) { |
| ret = static_cast<BoolPtr>(CaseInsensitiveCompareUTF16( |
| static_cast<uword>(subject.ptr()), static_cast<uword>(Smi::New(from)), |
| static_cast<uword>(Smi::New(current)), |
| static_cast<uword>(Smi::New(len)))); |
| } else { |
| ret = static_cast<BoolPtr>(CaseInsensitiveCompareUCS2( |
| static_cast<uword>(subject.ptr()), static_cast<uword>(Smi::New(from)), |
| static_cast<uword>(Smi::New(current)), |
| static_cast<uword>(Smi::New(len)))); |
| } |
| return ret.value(); |
| } |
| |
| template <> |
| bool BackRefMatchesNoCase<uint8_t>(Canonicalize* interp_canonicalize, |
| intptr_t from, |
| intptr_t current, |
| intptr_t len, |
| const String& subject, |
| bool unicode) { |
| // For Latin1 characters the unicode flag makes no difference. |
| for (int i = 0; i < len; i++) { |
| unsigned int old_char = subject.CharAt(from++); |
| unsigned int new_char = subject.CharAt(current++); |
| if (old_char == new_char) continue; |
| // Convert both characters to lower case. |
| old_char |= 0x20; |
| new_char |= 0x20; |
| if (old_char != new_char) return false; |
| // Not letters in the ASCII range and Latin-1 range. |
| if (!(old_char - 'a' <= 'z' - 'a') && |
| !(old_char - 224 <= 254 - 224 && old_char != 247)) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| #ifdef DEBUG |
| static void TraceInterpreter(const uint8_t* code_base, |
| const uint8_t* pc, |
| int stack_depth, |
| int current_position, |
| uint32_t current_char, |
| int bytecode_length, |
| const char* bytecode_name) { |
| if (FLAG_trace_regexp_bytecodes) { |
| bool printable = (current_char < 127 && current_char >= 32); |
| const char* format = |
| printable |
| ? "pc = %02x, sp = %d, curpos = %d, curchar = %08x (%c), bc = %s" |
| : "pc = %02x, sp = %d, curpos = %d, curchar = %08x .%c., bc = %s"; |
| OS::PrintErr(format, pc - code_base, stack_depth, current_position, |
| current_char, printable ? current_char : '.', bytecode_name); |
| for (int i = 0; i < bytecode_length; i++) { |
| OS::PrintErr(", %02x", pc[i]); |
| } |
| OS::PrintErr(" "); |
| for (int i = 1; i < bytecode_length; i++) { |
| unsigned char b = pc[i]; |
| if (b < 127 && b >= 32) { |
| OS::PrintErr("%c", b); |
| } else { |
| OS::PrintErr("."); |
| } |
| } |
| OS::PrintErr("\n"); |
| } |
| } |
| |
| #define BYTECODE(name) \ |
| case BC_##name: \ |
| TraceInterpreter(code_base, pc, \ |
| static_cast<int>(backtrack_sp - backtrack_stack_base), \ |
| current, current_char, BC_##name##_LENGTH, #name); |
| #else |
| #define BYTECODE(name) case BC_##name: |
| #endif |
| |
| static int32_t Load32Aligned(const uint8_t* pc) { |
| ASSERT((reinterpret_cast<intptr_t>(pc) & 3) == 0); |
| return *reinterpret_cast<const int32_t*>(pc); |
| } |
| |
| static int32_t Load16Aligned(const uint8_t* pc) { |
| ASSERT((reinterpret_cast<intptr_t>(pc) & 1) == 0); |
| return *reinterpret_cast<const uint16_t*>(pc); |
| } |
| |
| // A simple abstraction over the backtracking stack used by the interpreter. |
| // This backtracking stack does not grow automatically, but it ensures that the |
| // the memory held by the stack is released or remembered in a cache if the |
| // matching terminates. |
| class BacktrackStack { |
| public: |
| BacktrackStack() { |
| memory_ = Isolate::Current()->TakeRegexpBacktrackStack(); |
| // Note: using malloc here has a potential of triggering jemalloc/tcmalloc |
| // bugs which cause application to leak memory and eventually OOM. |
| // See https://github.com/dart-lang/sdk/issues/38820 and |
| // https://github.com/flutter/flutter/issues/29007 for examples. |
| // So instead we directly ask OS to provide us memory. |
| if (memory_ == nullptr) { |
| const bool executable = false; |
| const bool compressed = false; |
| const intptr_t size_in_bytes = Utils::RoundUp( |
| FLAG_regexp_backtrack_stack_size_kb * KB, VirtualMemory::PageSize()); |
| memory_ = std::unique_ptr<VirtualMemory>(VirtualMemory::Allocate( |
| size_in_bytes, executable, compressed, "regexp-backtrack-stack")); |
| } |
| } |
| |
| ~BacktrackStack() { |
| if (memory_ != nullptr) { |
| Isolate::Current()->CacheRegexpBacktrackStack(std::move(memory_)); |
| } |
| } |
| |
| bool out_of_memory() const { return memory_ == nullptr; } |
| |
| int32_t* data() const { |
| return reinterpret_cast<int32_t*>(memory_->address()); |
| } |
| |
| intptr_t max_size() const { return memory_->size() / sizeof(int32_t); } |
| |
| private: |
| std::unique_ptr<VirtualMemory> memory_; |
| |
| DISALLOW_COPY_AND_ASSIGN(BacktrackStack); |
| }; |
| |
| // Returns True if success, False if failure, Null if internal exception, |
| // Error if VM error needs to be propagated up the callchain. |
| template <typename Char> |
| static ObjectPtr RawMatch(const TypedData& bytecode, |
| const String& subject, |
| int32_t* registers, |
| int32_t current, |
| uint32_t current_char) { |
| // BacktrackStack ensures that the memory allocated for the backtracking stack |
| // is returned to the system or cached if there is no stack being cached at |
| // the moment. |
| BacktrackStack backtrack_stack; |
| if (backtrack_stack.out_of_memory()) { |
| Exceptions::ThrowOOM(); |
| UNREACHABLE(); |
| } |
| int32_t* backtrack_stack_base = backtrack_stack.data(); |
| int32_t* backtrack_sp = backtrack_stack_base; |
| intptr_t backtrack_stack_space = backtrack_stack.max_size(); |
| |
| // TODO(zerny): Optimize as single instance. V8 has this as an |
| // isolate member. |
| unibrow::Mapping<unibrow::Ecma262Canonicalize> canonicalize; |
| |
| intptr_t subject_length = subject.Length(); |
| |
| #ifdef DEBUG |
| if (FLAG_trace_regexp_bytecodes) { |
| OS::PrintErr("Start irregexp bytecode interpreter\n"); |
| } |
| #endif |
| const auto thread = Thread::Current(); |
| const uint8_t* code_base; |
| const uint8_t* pc; |
| { |
| NoSafepointScope no_safepoint; |
| code_base = reinterpret_cast<uint8_t*>(bytecode.DataAddr(0)); |
| pc = code_base; |
| } |
| while (true) { |
| if (UNLIKELY(thread->HasScheduledInterrupts())) { |
| intptr_t pc_offset = pc - code_base; |
| ErrorPtr error = thread->HandleInterrupts(); |
| if (error != Object::null()) { |
| // Needs to be propagated to the Dart native invoking the |
| // regex matcher. |
| return error; |
| } |
| NoSafepointScope no_safepoint; |
| code_base = reinterpret_cast<uint8_t*>(bytecode.DataAddr(0)); |
| pc = code_base + pc_offset; |
| } |
| NoSafepointScope no_safepoint; |
| bool check_for_safepoint_now = false; |
| while (!check_for_safepoint_now) { |
| int32_t insn = Load32Aligned(pc); |
| switch (insn & BYTECODE_MASK) { |
| BYTECODE(BREAK) |
| UNREACHABLE(); |
| return Bool::False().ptr(); |
| BYTECODE(PUSH_CP) |
| if (--backtrack_stack_space < 0) { |
| return Object::null(); |
| } |
| *backtrack_sp++ = current; |
| pc += BC_PUSH_CP_LENGTH; |
| break; |
| BYTECODE(PUSH_BT) |
| if (--backtrack_stack_space < 0) { |
| return Object::null(); |
| } |
| *backtrack_sp++ = Load32Aligned(pc + 4); |
| pc += BC_PUSH_BT_LENGTH; |
| break; |
| BYTECODE(PUSH_REGISTER) |
| if (--backtrack_stack_space < 0) { |
| return Object::null(); |
| } |
| *backtrack_sp++ = registers[insn >> BYTECODE_SHIFT]; |
| pc += BC_PUSH_REGISTER_LENGTH; |
| break; |
| BYTECODE(SET_REGISTER) |
| registers[insn >> BYTECODE_SHIFT] = Load32Aligned(pc + 4); |
| pc += BC_SET_REGISTER_LENGTH; |
| break; |
| BYTECODE(ADVANCE_REGISTER) |
| registers[insn >> BYTECODE_SHIFT] += Load32Aligned(pc + 4); |
| pc += BC_ADVANCE_REGISTER_LENGTH; |
| break; |
| BYTECODE(SET_REGISTER_TO_CP) |
| registers[insn >> BYTECODE_SHIFT] = current + Load32Aligned(pc + 4); |
| pc += BC_SET_REGISTER_TO_CP_LENGTH; |
| break; |
| BYTECODE(SET_CP_TO_REGISTER) |
| current = registers[insn >> BYTECODE_SHIFT]; |
| pc += BC_SET_CP_TO_REGISTER_LENGTH; |
| break; |
| BYTECODE(SET_REGISTER_TO_SP) |
| registers[insn >> BYTECODE_SHIFT] = |
| static_cast<int>(backtrack_sp - backtrack_stack_base); |
| pc += BC_SET_REGISTER_TO_SP_LENGTH; |
| break; |
| BYTECODE(SET_SP_TO_REGISTER) |
| backtrack_sp = backtrack_stack_base + registers[insn >> BYTECODE_SHIFT]; |
| backtrack_stack_space = |
| backtrack_stack.max_size() - |
| static_cast<int>(backtrack_sp - backtrack_stack_base); |
| pc += BC_SET_SP_TO_REGISTER_LENGTH; |
| break; |
| BYTECODE(POP_CP) |
| backtrack_stack_space++; |
| --backtrack_sp; |
| current = *backtrack_sp; |
| pc += BC_POP_CP_LENGTH; |
| break; |
| BYTECODE(POP_BT) |
| backtrack_stack_space++; |
| --backtrack_sp; |
| pc = code_base + *backtrack_sp; |
| // This should match check cadence in JIT irregexp implementation. |
| check_for_safepoint_now = true; |
| break; |
| BYTECODE(POP_REGISTER) |
| backtrack_stack_space++; |
| --backtrack_sp; |
| registers[insn >> BYTECODE_SHIFT] = *backtrack_sp; |
| pc += BC_POP_REGISTER_LENGTH; |
| break; |
| BYTECODE(FAIL) |
| return Bool::False().ptr(); |
| BYTECODE(SUCCEED) |
| return Bool::True().ptr(); |
| BYTECODE(ADVANCE_CP) |
| current += insn >> BYTECODE_SHIFT; |
| pc += BC_ADVANCE_CP_LENGTH; |
| break; |
| BYTECODE(GOTO) |
| pc = code_base + Load32Aligned(pc + 4); |
| break; |
| BYTECODE(ADVANCE_CP_AND_GOTO) |
| current += insn >> BYTECODE_SHIFT; |
| pc = code_base + Load32Aligned(pc + 4); |
| break; |
| BYTECODE(CHECK_GREEDY) |
| if (current == backtrack_sp[-1]) { |
| backtrack_sp--; |
| backtrack_stack_space++; |
| pc = code_base + Load32Aligned(pc + 4); |
| } else { |
| pc += BC_CHECK_GREEDY_LENGTH; |
| } |
| break; |
| BYTECODE(LOAD_CURRENT_CHAR) { |
| int pos = current + (insn >> BYTECODE_SHIFT); |
| if (pos < 0 || pos >= subject_length) { |
| pc = code_base + Load32Aligned(pc + 4); |
| } else { |
| current_char = subject.CharAt(pos); |
| pc += BC_LOAD_CURRENT_CHAR_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(LOAD_CURRENT_CHAR_UNCHECKED) { |
| int pos = current + (insn >> BYTECODE_SHIFT); |
| current_char = subject.CharAt(pos); |
| pc += BC_LOAD_CURRENT_CHAR_UNCHECKED_LENGTH; |
| break; |
| } |
| BYTECODE(LOAD_2_CURRENT_CHARS) { |
| int pos = current + (insn >> BYTECODE_SHIFT); |
| if (pos + 2 > subject_length) { |
| pc = code_base + Load32Aligned(pc + 4); |
| } else { |
| Char next = subject.CharAt(pos + 1); |
| current_char = |
| subject.CharAt(pos) | (next << (kBitsPerByte * sizeof(Char))); |
| pc += BC_LOAD_2_CURRENT_CHARS_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(LOAD_2_CURRENT_CHARS_UNCHECKED) { |
| int pos = current + (insn >> BYTECODE_SHIFT); |
| Char next = subject.CharAt(pos + 1); |
| current_char = |
| subject.CharAt(pos) | (next << (kBitsPerByte * sizeof(Char))); |
| pc += BC_LOAD_2_CURRENT_CHARS_UNCHECKED_LENGTH; |
| break; |
| } |
| BYTECODE(LOAD_4_CURRENT_CHARS) { |
| ASSERT(sizeof(Char) == 1); |
| int pos = current + (insn >> BYTECODE_SHIFT); |
| if (pos + 4 > subject_length) { |
| pc = code_base + Load32Aligned(pc + 4); |
| } else { |
| Char next1 = subject.CharAt(pos + 1); |
| Char next2 = subject.CharAt(pos + 2); |
| Char next3 = subject.CharAt(pos + 3); |
| current_char = (subject.CharAt(pos) | (next1 << 8) | (next2 << 16) | |
| (next3 << 24)); |
| pc += BC_LOAD_4_CURRENT_CHARS_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(LOAD_4_CURRENT_CHARS_UNCHECKED) { |
| ASSERT(sizeof(Char) == 1); |
| int pos = current + (insn >> BYTECODE_SHIFT); |
| Char next1 = subject.CharAt(pos + 1); |
| Char next2 = subject.CharAt(pos + 2); |
| Char next3 = subject.CharAt(pos + 3); |
| current_char = (subject.CharAt(pos) | (next1 << 8) | (next2 << 16) | |
| (next3 << 24)); |
| pc += BC_LOAD_4_CURRENT_CHARS_UNCHECKED_LENGTH; |
| break; |
| } |
| BYTECODE(CHECK_4_CHARS) { |
| uint32_t c = Load32Aligned(pc + 4); |
| if (c == current_char) { |
| pc = code_base + Load32Aligned(pc + 8); |
| } else { |
| pc += BC_CHECK_4_CHARS_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(CHECK_CHAR) { |
| uint32_t c = (insn >> BYTECODE_SHIFT); |
| if (c == current_char) { |
| pc = code_base + Load32Aligned(pc + 4); |
| } else { |
| pc += BC_CHECK_CHAR_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(CHECK_NOT_4_CHARS) { |
| uint32_t c = Load32Aligned(pc + 4); |
| if (c != current_char) { |
| pc = code_base + Load32Aligned(pc + 8); |
| } else { |
| pc += BC_CHECK_NOT_4_CHARS_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(CHECK_NOT_CHAR) { |
| uint32_t c = (insn >> BYTECODE_SHIFT); |
| if (c != current_char) { |
| pc = code_base + Load32Aligned(pc + 4); |
| } else { |
| pc += BC_CHECK_NOT_CHAR_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(AND_CHECK_4_CHARS) { |
| uint32_t c = Load32Aligned(pc + 4); |
| if (c == (current_char & Load32Aligned(pc + 8))) { |
| pc = code_base + Load32Aligned(pc + 12); |
| } else { |
| pc += BC_AND_CHECK_4_CHARS_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(AND_CHECK_CHAR) { |
| uint32_t c = (insn >> BYTECODE_SHIFT); |
| if (c == (current_char & Load32Aligned(pc + 4))) { |
| pc = code_base + Load32Aligned(pc + 8); |
| } else { |
| pc += BC_AND_CHECK_CHAR_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(AND_CHECK_NOT_4_CHARS) { |
| uint32_t c = Load32Aligned(pc + 4); |
| if (c != (current_char & Load32Aligned(pc + 8))) { |
| pc = code_base + Load32Aligned(pc + 12); |
| } else { |
| pc += BC_AND_CHECK_NOT_4_CHARS_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(AND_CHECK_NOT_CHAR) { |
| uint32_t c = (insn >> BYTECODE_SHIFT); |
| if (c != (current_char & Load32Aligned(pc + 4))) { |
| pc = code_base + Load32Aligned(pc + 8); |
| } else { |
| pc += BC_AND_CHECK_NOT_CHAR_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(MINUS_AND_CHECK_NOT_CHAR) { |
| uint32_t c = (insn >> BYTECODE_SHIFT); |
| uint32_t minus = Load16Aligned(pc + 4); |
| uint32_t mask = Load16Aligned(pc + 6); |
| if (c != ((current_char - minus) & mask)) { |
| pc = code_base + Load32Aligned(pc + 8); |
| } else { |
| pc += BC_MINUS_AND_CHECK_NOT_CHAR_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(CHECK_CHAR_IN_RANGE) { |
| uint32_t from = Load16Aligned(pc + 4); |
| uint32_t to = Load16Aligned(pc + 6); |
| if (from <= current_char && current_char <= to) { |
| pc = code_base + Load32Aligned(pc + 8); |
| } else { |
| pc += BC_CHECK_CHAR_IN_RANGE_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(CHECK_CHAR_NOT_IN_RANGE) { |
| uint32_t from = Load16Aligned(pc + 4); |
| uint32_t to = Load16Aligned(pc + 6); |
| if (from > current_char || current_char > to) { |
| pc = code_base + Load32Aligned(pc + 8); |
| } else { |
| pc += BC_CHECK_CHAR_NOT_IN_RANGE_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(CHECK_BIT_IN_TABLE) { |
| int mask = RegExpMacroAssembler::kTableMask; |
| uint8_t b = pc[8 + ((current_char & mask) >> kBitsPerByteLog2)]; |
| int bit = (current_char & (kBitsPerByte - 1)); |
| if ((b & (1 << bit)) != 0) { |
| pc = code_base + Load32Aligned(pc + 4); |
| } else { |
| pc += BC_CHECK_BIT_IN_TABLE_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(CHECK_LT) { |
| uint32_t limit = (insn >> BYTECODE_SHIFT); |
| if (current_char < limit) { |
| pc = code_base + Load32Aligned(pc + 4); |
| } else { |
| pc += BC_CHECK_LT_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(CHECK_GT) { |
| uint32_t limit = (insn >> BYTECODE_SHIFT); |
| if (current_char > limit) { |
| pc = code_base + Load32Aligned(pc + 4); |
| } else { |
| pc += BC_CHECK_GT_LENGTH; |
| } |
| break; |
| } |
| BYTECODE(CHECK_REGISTER_LT) |
| if (registers[insn >> BYTECODE_SHIFT] < Load32Aligned(pc + 4)) { |
| pc = code_base + Load32Aligned(pc + 8); |
| } else { |
| pc += BC_CHECK_REGISTER_LT_LENGTH; |
| } |
| break; |
| BYTECODE(CHECK_REGISTER_GE) |
| if (registers[insn >> BYTECODE_SHIFT] >= Load32Aligned(pc + 4)) { |
| pc = code_base + Load32Aligned(pc + 8); |
| } else { |
| pc += BC_CHECK_REGISTER_GE_LENGTH; |
| } |
| break; |
| BYTECODE(CHECK_REGISTER_EQ_POS) |
| if (registers[insn >> BYTECODE_SHIFT] == current) { |
| pc = code_base + Load32Aligned(pc + 4); |
| } else { |
| pc += BC_CHECK_REGISTER_EQ_POS_LENGTH; |
| } |
| break; |
| BYTECODE(CHECK_NOT_REGS_EQUAL) |
| if (registers[insn >> BYTECODE_SHIFT] == |
| registers[Load32Aligned(pc + 4)]) { |
| pc += BC_CHECK_NOT_REGS_EQUAL_LENGTH; |
| } else { |
| pc = code_base + Load32Aligned(pc + 8); |
| } |
| break; |
| BYTECODE(CHECK_NOT_BACK_REF) { |
| int from = registers[insn >> BYTECODE_SHIFT]; |
| int len = registers[(insn >> BYTECODE_SHIFT) + 1] - from; |
| if (from < 0 || len <= 0) { |
| pc += BC_CHECK_NOT_BACK_REF_LENGTH; |
| break; |
| } |
| if (current + len > subject_length) { |
| pc = code_base + Load32Aligned(pc + 4); |
| break; |
| } else { |
| int i; |
| for (i = 0; i < len; i++) { |
| if (subject.CharAt(from + i) != subject.CharAt(current + i)) { |
| pc = code_base + Load32Aligned(pc + 4); |
| break; |
| } |
| } |
| if (i < len) break; |
| current += len; |
| } |
| pc += BC_CHECK_NOT_BACK_REF_LENGTH; |
| break; |
| } |
| BYTECODE(CHECK_NOT_BACK_REF_NO_CASE_UNICODE) |
| FALL_THROUGH; |
| BYTECODE(CHECK_NOT_BACK_REF_NO_CASE) { |
| const bool unicode = |
| (insn & BYTECODE_MASK) == BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE; |
| int from = registers[insn >> BYTECODE_SHIFT]; |
| int len = registers[(insn >> BYTECODE_SHIFT) + 1] - from; |
| if (from < 0 || len <= 0) { |
| pc += BC_CHECK_NOT_BACK_REF_NO_CASE_LENGTH; |
| break; |
| } |
| if (current + len > subject_length) { |
| pc = code_base + Load32Aligned(pc + 4); |
| break; |
| } else { |
| if (BackRefMatchesNoCase<Char>(&canonicalize, from, current, len, |
| subject, unicode)) { |
| current += len; |
| pc += BC_CHECK_NOT_BACK_REF_NO_CASE_LENGTH; |
| } else { |
| pc = code_base + Load32Aligned(pc + 4); |
| } |
| } |
| break; |
| } |
| BYTECODE(CHECK_NOT_BACK_REF_BACKWARD) { |
| const int from = registers[insn >> BYTECODE_SHIFT]; |
| const int len = registers[(insn >> BYTECODE_SHIFT) + 1] - from; |
| if (from < 0 || len <= 0) { |
| pc += BC_CHECK_NOT_BACK_REF_BACKWARD_LENGTH; |
| break; |
| } |
| if ((current - len) < 0) { |
| pc = code_base + Load32Aligned(pc + 4); |
| break; |
| } else { |
| // When looking behind, the string to match (if it is there) lies |
| // before the current position, so we will check the [len] |
| // characters before the current position, excluding the current |
| // position itself. |
| const int start = current - len; |
| int i; |
| for (i = 0; i < len; i++) { |
| if (subject.CharAt(from + i) != subject.CharAt(start + i)) { |
| pc = code_base + Load32Aligned(pc + 4); |
| break; |
| } |
| } |
| if (i < len) break; |
| current -= len; |
| } |
| pc += BC_CHECK_NOT_BACK_REF_BACKWARD_LENGTH; |
| break; |
| } |
| BYTECODE(CHECK_NOT_BACK_REF_NO_CASE_UNICODE_BACKWARD) |
| FALL_THROUGH; |
| BYTECODE(CHECK_NOT_BACK_REF_NO_CASE_BACKWARD) { |
| bool unicode = (insn & BYTECODE_MASK) == |
| BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE_BACKWARD; |
| int from = registers[insn >> BYTECODE_SHIFT]; |
| int len = registers[(insn >> BYTECODE_SHIFT) + 1] - from; |
| if (from < 0 || len <= 0) { |
| pc += BC_CHECK_NOT_BACK_REF_NO_CASE_BACKWARD_LENGTH; |
| break; |
| } |
| if (current < len) { |
| pc = code_base + Load32Aligned(pc + 4); |
| break; |
| } else { |
| if (BackRefMatchesNoCase<Char>(&canonicalize, from, current - len, |
| len, subject, unicode)) { |
| current -= len; |
| pc += BC_CHECK_NOT_BACK_REF_NO_CASE_BACKWARD_LENGTH; |
| } else { |
| pc = code_base + Load32Aligned(pc + 4); |
| } |
| } |
| break; |
| } |
| BYTECODE(CHECK_AT_START) |
| if (current == 0) { |
| pc = code_base + Load32Aligned(pc + 4); |
| } else { |
| pc += BC_CHECK_AT_START_LENGTH; |
| } |
| break; |
| BYTECODE(CHECK_NOT_AT_START) { |
| const int32_t cp_offset = insn >> BYTECODE_SHIFT; |
| if (current + cp_offset == 0) { |
| pc += BC_CHECK_NOT_AT_START_LENGTH; |
| } else { |
| pc = code_base + Load32Aligned(pc + 4); |
| } |
| break; |
| } |
| BYTECODE(SET_CURRENT_POSITION_FROM_END) { |
| int by = static_cast<uint32_t>(insn) >> BYTECODE_SHIFT; |
| if (subject_length - current > by) { |
| current = subject_length - by; |
| current_char = subject.CharAt(current - 1); |
| } |
| pc += BC_SET_CURRENT_POSITION_FROM_END_LENGTH; |
| break; |
| } |
| default: |
| UNREACHABLE(); |
| break; |
| } |
| } |
| } |
| } |
| |
| // Returns True if success, False if failure, Null if internal exception, |
| // Error if VM error needs to be propagated up the callchain. |
| ObjectPtr IrregexpInterpreter::Match(const TypedData& bytecode, |
| const String& subject, |
| int32_t* registers, |
| int32_t start_position) { |
| uint16_t previous_char = '\n'; |
| if (start_position != 0) { |
| previous_char = subject.CharAt(start_position - 1); |
| } |
| |
| if (subject.IsOneByteString()) { |
| return RawMatch<uint8_t>(bytecode, subject, registers, start_position, |
| previous_char); |
| } else if (subject.IsTwoByteString()) { |
| return RawMatch<uint16_t>(bytecode, subject, registers, start_position, |
| previous_char); |
| } else { |
| UNREACHABLE(); |
| return Bool::False().ptr(); |
| } |
| } |
| |
| } // namespace dart |
