Port irregexp bytecode compiler and interpreter from V8 r24065.

runtime/vm/regexp_assembler_bytecode.cc

+// Copyright (c) 2014, 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.
+
+#include "vm/regexp_assembler_bytecode.h"
+
+#include "vm/regexp_assembler_bytecode_inl.h"
+#include "vm/exceptions.h"
+#include "vm/object_store.h"
+#include "vm/regexp_bytecodes.h"
+#include "vm/regexp_assembler.h"
+#include "vm/regexp.h"
+#include "vm/regexp_parser.h"
+#include "vm/regexp_interpreter.h"
+
+namespace dart {
+
+BytecodeRegExpMacroAssembler::BytecodeRegExpMacroAssembler(
+    ZoneGrowableArray<uint8_t>* buffer,
+    Zone* zone)
+    : RegExpMacroAssembler(zone),
+      buffer_(buffer),
+      pc_(0),
+      advance_current_end_(kInvalidPC) { }
+
+
+BytecodeRegExpMacroAssembler::~BytecodeRegExpMacroAssembler() {
+  if (backtrack_.is_linked()) backtrack_.Unuse();
+}
+
+
+BytecodeRegExpMacroAssembler::IrregexpImplementation
+BytecodeRegExpMacroAssembler::Implementation() {
+  return kBytecodeImplementation;
+}
+
+
+void BytecodeRegExpMacroAssembler::BindBlock(BlockLabel* l) {
+  advance_current_end_ = kInvalidPC;
+  ASSERT(!l->is_bound());
+  if (l->is_linked()) {
+    intptr_t pos = l->pos();
+    while (pos != 0) {
+      intptr_t fixup = pos;
+      pos = *reinterpret_cast<int32_t*>(buffer_->data() + fixup);
+      *reinterpret_cast<uint32_t*>(buffer_->data() + fixup) = pc_;
+    }
+  }
+  l->bind_to(pc_);
+}
+
+
+void BytecodeRegExpMacroAssembler::EmitOrLink(BlockLabel* l) {
+  if (l == NULL) l = &backtrack_;
+  if (l->is_bound()) {
+    Emit32(l->pos());
+  } else {
+    int pos = 0;
+    if (l->is_linked()) {
+      pos = l->pos();
+    }
+    l->link_to(pc_);
+    Emit32(pos);
+  }
+}
+
+
+void BytecodeRegExpMacroAssembler::PopRegister(intptr_t register_index) {
+  ASSERT(register_index >= 0);
+  ASSERT(register_index <= kMaxRegister);
+  Emit(BC_POP_REGISTER, register_index);
+}
+
+
+void BytecodeRegExpMacroAssembler::PushRegister(intptr_t register_index) {
+  ASSERT(register_index >= 0);
+  ASSERT(register_index <= kMaxRegister);
+  Emit(BC_PUSH_REGISTER, register_index);
+}
+
+
+void BytecodeRegExpMacroAssembler::WriteCurrentPositionToRegister(
+    intptr_t register_index, intptr_t cp_offset) {
+  ASSERT(register_index >= 0);
+  ASSERT(register_index <= kMaxRegister);
+  Emit(BC_SET_REGISTER_TO_CP, register_index);
+  Emit32(cp_offset);  // Current position offset.
+}
+
+
+void BytecodeRegExpMacroAssembler::ClearRegisters(intptr_t reg_from,
+                                                  intptr_t reg_to) {
+  ASSERT(reg_from <= reg_to);
+  for (int reg = reg_from; reg <= reg_to; reg++) {
+    SetRegister(reg, -1);
+  }
+}
+
+
+void BytecodeRegExpMacroAssembler::ReadCurrentPositionFromRegister(
+    intptr_t register_index) {
+  ASSERT(register_index >= 0);
+  ASSERT(register_index <= kMaxRegister);
+  Emit(BC_SET_CP_TO_REGISTER, register_index);
+}
+
+
+void BytecodeRegExpMacroAssembler::WriteStackPointerToRegister(
+    intptr_t register_index) {
+  ASSERT(register_index >= 0);
+  ASSERT(register_index <= kMaxRegister);
+  Emit(BC_SET_REGISTER_TO_SP, register_index);
+}
+
+
+void BytecodeRegExpMacroAssembler::ReadStackPointerFromRegister(
+    intptr_t register_index) {
+  ASSERT(register_index >= 0);
+  ASSERT(register_index <= kMaxRegister);
+  Emit(BC_SET_SP_TO_REGISTER, register_index);
+}
+
+
+void BytecodeRegExpMacroAssembler::SetCurrentPositionFromEnd(intptr_t by) {
+  ASSERT(Utils::IsUint(24, by));
+  Emit(BC_SET_CURRENT_POSITION_FROM_END, by);
+}
+
+
+void BytecodeRegExpMacroAssembler::SetRegister(intptr_t register_index,
+                                               intptr_t to) {
+  ASSERT(register_index >= 0);
+  ASSERT(register_index <= kMaxRegister);
+  Emit(BC_SET_REGISTER, register_index);
+  Emit32(to);
+}
+
+
+void BytecodeRegExpMacroAssembler::AdvanceRegister(intptr_t register_index,
+                                                   intptr_t by) {
+  ASSERT(register_index >= 0);
+  ASSERT(register_index <= kMaxRegister);
+  Emit(BC_ADVANCE_REGISTER, register_index);
+  Emit32(by);
+}
+
+
+void BytecodeRegExpMacroAssembler::PopCurrentPosition() {
+  Emit(BC_POP_CP, 0);
+}
+
+
+void BytecodeRegExpMacroAssembler::PushCurrentPosition() {
+  Emit(BC_PUSH_CP, 0);
+}
+
+
+void BytecodeRegExpMacroAssembler::Backtrack() {
+  Emit(BC_POP_BT, 0);
+}
+
+
+void BytecodeRegExpMacroAssembler::GoTo(BlockLabel* l) {
+  if (advance_current_end_ == pc_) {
+    // Combine advance current and goto.
+    pc_ = advance_current_start_;
+    Emit(BC_ADVANCE_CP_AND_GOTO, advance_current_offset_);
+    EmitOrLink(l);
+    advance_current_end_ = kInvalidPC;
+  } else {
+    // Regular goto.
+    Emit(BC_GOTO, 0);
+    EmitOrLink(l);
+  }
+}
+
+
+void BytecodeRegExpMacroAssembler::PushBacktrack(BlockLabel* l) {
+  Emit(BC_PUSH_BT, 0);
+  EmitOrLink(l);
+}
+
+
+bool BytecodeRegExpMacroAssembler::Succeed() {
+  Emit(BC_SUCCEED, 0);
+  return false;  // Restart matching for global regexp not supported.
+}
+
+
+void BytecodeRegExpMacroAssembler::Fail() {
+  Emit(BC_FAIL, 0);
+}
+
+
+void BytecodeRegExpMacroAssembler::AdvanceCurrentPosition(intptr_t by) {
+  ASSERT(by >= kMinCPOffset);
+  ASSERT(by <= kMaxCPOffset);
+  advance_current_start_ = pc_;
+  advance_current_offset_ = by;
+  Emit(BC_ADVANCE_CP, by);
+  advance_current_end_ = pc_;
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckGreedyLoop(
+      BlockLabel* on_tos_equals_current_position) {
+  Emit(BC_CHECK_GREEDY, 0);
+  EmitOrLink(on_tos_equals_current_position);
+}
+
+
+void BytecodeRegExpMacroAssembler::LoadCurrentCharacter(intptr_t cp_offset,
+                                                        BlockLabel* on_failure,
+                                                        bool check_bounds,
+                                                        intptr_t characters) {
+  ASSERT(cp_offset >= kMinCPOffset);
+  ASSERT(cp_offset <= kMaxCPOffset);
+  int bytecode;
+  if (check_bounds) {
+    if (characters == 4) {
+      bytecode = BC_LOAD_4_CURRENT_CHARS;
+    } else if (characters == 2) {
+      bytecode = BC_LOAD_2_CURRENT_CHARS;
+    } else {
+      ASSERT(characters == 1);
+      bytecode = BC_LOAD_CURRENT_CHAR;
+    }
+  } else {
+    if (characters == 4) {
+      bytecode = BC_LOAD_4_CURRENT_CHARS_UNCHECKED;
+    } else if (characters == 2) {
+      bytecode = BC_LOAD_2_CURRENT_CHARS_UNCHECKED;
+    } else {
+      ASSERT(characters == 1);
+      bytecode = BC_LOAD_CURRENT_CHAR_UNCHECKED;
+    }
+  }
+  Emit(bytecode, cp_offset);
+  if (check_bounds) EmitOrLink(on_failure);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckCharacterLT(uint16_t limit,
+                                                    BlockLabel* on_less) {
+  Emit(BC_CHECK_LT, limit);
+  EmitOrLink(on_less);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckCharacterGT(uint16_t limit,
+                                                    BlockLabel* on_greater) {
+  Emit(BC_CHECK_GT, limit);
+  EmitOrLink(on_greater);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckCharacter(uint32_t c,
+                                                  BlockLabel* on_equal) {
+  if (c > MAX_FIRST_ARG) {
+    Emit(BC_CHECK_4_CHARS, 0);
+    Emit32(c);
+  } else {
+    Emit(BC_CHECK_CHAR, c);
+  }
+  EmitOrLink(on_equal);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckAtStart(BlockLabel* on_at_start) {
+  Emit(BC_CHECK_AT_START, 0);
+  EmitOrLink(on_at_start);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckNotAtStart(
+    BlockLabel* on_not_at_start) {
+  Emit(BC_CHECK_NOT_AT_START, 0);
+  EmitOrLink(on_not_at_start);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckNotCharacter(uint32_t c,
+                                                     BlockLabel* on_not_equal) {
+  if (c > MAX_FIRST_ARG) {
+    Emit(BC_CHECK_NOT_4_CHARS, 0);
+    Emit32(c);
+  } else {
+    Emit(BC_CHECK_NOT_CHAR, c);
+  }
+  EmitOrLink(on_not_equal);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckCharacterAfterAnd(
+    uint32_t c,
+    uint32_t mask,
+    BlockLabel* on_equal) {
+  if (c > MAX_FIRST_ARG) {
+    Emit(BC_AND_CHECK_4_CHARS, 0);
+    Emit32(c);
+  } else {
+    Emit(BC_AND_CHECK_CHAR, c);
+  }
+  Emit32(mask);
+  EmitOrLink(on_equal);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckNotCharacterAfterAnd(
+    uint32_t c,
+    uint32_t mask,
+    BlockLabel* on_not_equal) {
+  if (c > MAX_FIRST_ARG) {
+    Emit(BC_AND_CHECK_NOT_4_CHARS, 0);
+    Emit32(c);
+  } else {
+    Emit(BC_AND_CHECK_NOT_CHAR, c);
+  }
+  Emit32(mask);
+  EmitOrLink(on_not_equal);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckNotCharacterAfterMinusAnd(
+    uint16_t c,
+    uint16_t minus,
+    uint16_t mask,
+    BlockLabel* on_not_equal) {
+  Emit(BC_MINUS_AND_CHECK_NOT_CHAR, c);
+  Emit16(minus);
+  Emit16(mask);
+  EmitOrLink(on_not_equal);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckCharacterInRange(
+    uint16_t from,
+    uint16_t to,
+    BlockLabel* on_in_range) {
+  Emit(BC_CHECK_CHAR_IN_RANGE, 0);
+  Emit16(from);
+  Emit16(to);
+  EmitOrLink(on_in_range);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckCharacterNotInRange(
+    uint16_t from,
+    uint16_t to,
+    BlockLabel* on_not_in_range) {
+  Emit(BC_CHECK_CHAR_NOT_IN_RANGE, 0);
+  Emit16(from);
+  Emit16(to);
+  EmitOrLink(on_not_in_range);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckBitInTable(
+    const TypedData& table, BlockLabel* on_bit_set) {
+  Emit(BC_CHECK_BIT_IN_TABLE, 0);
+  EmitOrLink(on_bit_set);
+  for (int i = 0; i < kTableSize; i += kBitsPerByte) {
+    int byte = 0;
+    for (int j = 0; j < kBitsPerByte; j++) {
+      if (table.GetUint8(i + j) != 0) byte |= 1 << j;
+    }
+    Emit8(byte);
+  }
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckNotBackReference(
+    intptr_t start_reg,
+    BlockLabel* on_not_equal) {
+  ASSERT(start_reg >= 0);
+  ASSERT(start_reg <= kMaxRegister);
+  Emit(BC_CHECK_NOT_BACK_REF, start_reg);
+  EmitOrLink(on_not_equal);
+}
+
+
+void BytecodeRegExpMacroAssembler::CheckNotBackReferenceIgnoreCase(
+    intptr_t start_reg,
+    BlockLabel* on_not_equal) {
+  ASSERT(start_reg >= 0);
+  ASSERT(start_reg <= kMaxRegister);
+  Emit(BC_CHECK_NOT_BACK_REF_NO_CASE, start_reg);
+  EmitOrLink(on_not_equal);
+}
+
+
+void BytecodeRegExpMacroAssembler::IfRegisterLT(intptr_t register_index,
+                                                intptr_t comparand,
+                                                BlockLabel* on_less_than) {
+  ASSERT(register_index >= 0);
+  ASSERT(register_index <= kMaxRegister);
+  Emit(BC_CHECK_REGISTER_LT, register_index);
+  Emit32(comparand);
+  EmitOrLink(on_less_than);
+}
+
+
+void BytecodeRegExpMacroAssembler::IfRegisterGE(
+    intptr_t register_index,
+    intptr_t comparand,
+    BlockLabel* on_greater_or_equal) {
+  ASSERT(register_index >= 0);
+  ASSERT(register_index <= kMaxRegister);
+  Emit(BC_CHECK_REGISTER_GE, register_index);
+  Emit32(comparand);
+  EmitOrLink(on_greater_or_equal);
+}
+
+
+void BytecodeRegExpMacroAssembler::IfRegisterEqPos(intptr_t register_index,
+                                                   BlockLabel* on_eq) {
+  ASSERT(register_index >= 0);
+  ASSERT(register_index <= kMaxRegister);
+  Emit(BC_CHECK_REGISTER_EQ_POS, register_index);
+  EmitOrLink(on_eq);
+}
+
+
+RawTypedData* BytecodeRegExpMacroAssembler::GetBytecode() {
+  BindBlock(&backtrack_);
+  Emit(BC_POP_BT, 0);
+
+  intptr_t len = length();
+  const TypedData& bytecode =
+      TypedData::Handle(TypedData::New(kTypedDataUint8ArrayCid, len));
+
+  NoSafepointScope no_safepoint;
+  memmove(bytecode.DataAddr(0), buffer_->data(), len);
+
+  return bytecode.raw();
+}
+
+
+intptr_t BytecodeRegExpMacroAssembler::length() {
+  return pc_;
+}
+
+
+void BytecodeRegExpMacroAssembler::Expand() {
+  // BOGUS
+  buffer_->Add(0);
+  buffer_->Add(0);
+  buffer_->Add(0);
+  buffer_->Add(0);
+  intptr_t x = buffer_->length();
+  for (intptr_t i = 0; i < x; i++) buffer_->Add(0);
+}
+
+
+static intptr_t Prepare(const JSRegExp& regexp,
+                        const String& subject,
+                        Zone* zone) {
+  bool is_one_byte = subject.IsOneByteString() ||
+                     subject.IsExternalOneByteString();
+
+  if (regexp.bytecode(is_one_byte) == TypedData::null()) {
+    const String& pattern = String::Handle(zone, regexp.pattern());
+
+    const bool multiline = regexp.is_multi_line();
+    RegExpCompileData* compile_data = new(zone) RegExpCompileData();
+    if (!RegExpParser::ParseRegExp(pattern, multiline, compile_data)) {
+      // Parsing failures are handled in the JSRegExp factory constructor.
+      UNREACHABLE();
+    }
+
+    regexp.set_num_bracket_expressions(compile_data->capture_count);
+    if (compile_data->simple) {
+      regexp.set_is_simple();
+    } else {
+      regexp.set_is_complex();
+    }
+
+    RegExpEngine::CompilationResult result =
+        RegExpEngine::CompileBytecode(compile_data, regexp, is_one_byte, zone);
+    ASSERT(result.bytecode != NULL);
+    ASSERT((regexp.num_registers() == -1) ||
+           (regexp.num_registers() == result.num_registers));
+    regexp.set_num_registers(result.num_registers);
+    regexp.set_bytecode(is_one_byte, *(result.bytecode));
+  }
+
+  ASSERT(regexp.num_registers() != -1);
+
+  return regexp.num_registers() +
+         (Smi::Value(regexp.num_bracket_expressions()) + 1) * 2;
+}
+
+
+static IrregexpInterpreter::IrregexpResult ExecRaw(const JSRegExp& regexp,
+                                                   const String& subject,
+                                                   intptr_t index,
+                                                   int32_t* output,
+                                                   intptr_t output_size,
+                                                   Zone* zone) {
+  bool is_one_byte = subject.IsOneByteString() ||
+                     subject.IsExternalOneByteString();
+
+  ASSERT(regexp.num_bracket_expressions() != Smi::null());
+
+  // We must have done EnsureCompiledIrregexp, so we can get the number of
+  // registers.
+  int number_of_capture_registers =
+     (Smi::Value(regexp.num_bracket_expressions()) + 1) * 2;
+  int32_t* raw_output = &output[number_of_capture_registers];
+
+  // We do not touch the actual capture result registers until we know there
+  // has been a match so that we can use those capture results to set the
+  // last match info.
+  for (int i = number_of_capture_registers - 1; i >= 0; i--) {
+    raw_output[i] = -1;
+  }
+
+  const TypedData& bytecode =
+      TypedData::Handle(zone, regexp.bytecode(is_one_byte));
+  ASSERT(!bytecode.IsNull());
+  IrregexpInterpreter::IrregexpResult result =
+      IrregexpInterpreter::Match(bytecode, subject, raw_output, index, zone);
+
+  if (result == IrregexpInterpreter::RE_SUCCESS) {
+    // Copy capture results to the start of the registers array.
+    memmove(output, raw_output, number_of_capture_registers * sizeof(int32_t));
+  }
+  if (result == IrregexpInterpreter::RE_EXCEPTION) {
+    Thread* thread = Thread::Current();
+    Isolate* isolate = thread->isolate();
+    const Instance& exception =
+        Instance::Handle(isolate->object_store()->stack_overflow());
+    Exceptions::Throw(thread, exception);
+    UNREACHABLE();
+  }
+  return result;
+}
+
+
+RawInstance* BytecodeRegExpMacroAssembler::Interpret(const JSRegExp& regexp,
+                                                     const String& subject,
+                                                     const Smi& start_index,
+                                                     Zone* zone) {
+  intptr_t required_registers = Prepare(regexp, subject, zone);
+  if (required_registers < 0) {
+    // Compiling failed with an exception.
+    UNREACHABLE();
+  }
+
+  // V8 uses a shared copy on the isolate when smaller than some threshold.
+  int32_t* output_registers = zone->Alloc<int32_t>(required_registers);
+
+  IrregexpInterpreter::IrregexpResult result = ExecRaw(regexp,
+                                                       subject,
+                                                       start_index.Value(),
+                                                       output_registers,
+                                                       required_registers,
+                                                       zone);
+
+  if (result == IrregexpInterpreter::RE_SUCCESS) {
+    intptr_t capture_count = Smi::Value(regexp.num_bracket_expressions());
+    intptr_t capture_register_count = (capture_count + 1) * 2;
+    ASSERT(required_registers >= capture_register_count);
+
+    const TypedData& result =

[rmacnak, 2015/06/25 00:14:47]

In V8, the result array is provided by the caller and reused.

+        TypedData::Handle(TypedData::New(kTypedDataInt32ArrayCid,
+                                         capture_register_count));
+    {
+#ifdef DEBUG
+      // These indices will be used with substring operations that don't check
+      // bounds, so sanity check them here.
+      for (intptr_t i = 0; i < capture_register_count; i++) {
+        int32_t val = output_registers[i];
+        ASSERT(val == -1 || (val >= 0 && val <= subject.Length()));
+      }
+#endif
+
+      NoSafepointScope no_safepoint;
+      memmove(result.DataAddr(0),
+              output_registers,
+              capture_register_count * sizeof(int32_t));
+    }
+
+    return result.raw();
+  }
+  if (result == IrregexpInterpreter::RE_EXCEPTION) {
+    UNREACHABLE();
+  }
+  ASSERT(result == IrregexpInterpreter::RE_FAILURE);
+  return Instance::null();
+}
+
+
+}  // namespace dart