regexp_assembler_bytecode.cc

Go to the documentation of this file.

// 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.
 
#include "vm/regexp_assembler_bytecode.h"
 
#include "vm/exceptions.h"
#include "vm/object_store.h"
#include "vm/regexp.h"
#include "vm/regexp_assembler.h"
#include "vm/regexp_assembler_bytecode_inl.h"
#include "vm/regexp_bytecodes.h"
#include "vm/regexp_interpreter.h"
#include "vm/regexp_parser.h"
#include "vm/timeline.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->BindTo(pc_);
}
 
void BytecodeRegExpMacroAssembler::EmitOrLink(BlockLabel* l) {
  if (l == nullptr) l = &backtrack_;
  if (l->is_bound()) {
    Emit32(l->pos());
  } else {
    int pos = 0;
    if (l->is_linked()) {
      pos = l->pos();
    }
    l->LinkTo(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(
    intptr_t cp_offset,
    BlockLabel* on_not_at_start) {
  Emit(BC_CHECK_NOT_AT_START, cp_offset);
  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,
    bool read_backward,
    BlockLabel* on_not_equal) {
  ASSERT(start_reg >= 0);
  ASSERT(start_reg <= kMaxRegister);
  Emit(read_backward ? BC_CHECK_NOT_BACK_REF_BACKWARD : BC_CHECK_NOT_BACK_REF,
       start_reg);
  EmitOrLink(on_not_equal);
}
 
void BytecodeRegExpMacroAssembler::CheckNotBackReferenceIgnoreCase(
    intptr_t start_reg,
    bool read_backward,
    bool unicode,
    BlockLabel* on_not_equal) {
  ASSERT(start_reg >= 0);
  ASSERT(start_reg <= kMaxRegister);
  Emit(read_backward ? (unicode ? BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE_BACKWARD
                                : BC_CHECK_NOT_BACK_REF_NO_CASE_BACKWARD)
                     : (unicode ? BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE
                                : 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);
}
 
TypedDataPtr 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.ptr();
}
 
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 RegExp& regexp,
                        const String& subject,
                        bool sticky,
                        Zone* zone) {
  bool is_one_byte = subject.IsOneByteString();
 
  if (regexp.bytecode(is_one_byte, sticky) == TypedData::null()) {
    const String& pattern = String::Handle(zone, regexp.pattern());
#if defined(SUPPORT_TIMELINE)
    TimelineBeginEndScope tbes(Thread::Current(), Timeline::GetCompilerStream(),
                               "CompileIrregexpBytecode");
    if (tbes.enabled()) {
      tbes.SetNumArguments(1);
      tbes.CopyArgument(0, "pattern", pattern.ToCString());
    }
#endif  // !defined(PRODUCT)
 
    RegExpCompileData* compile_data = new (zone) RegExpCompileData();
 
    // Parsing failures are handled in the RegExp factory constructor.
    RegExpParser::ParseRegExp(pattern, regexp.flags(), compile_data);
 
    regexp.set_num_bracket_expressions(compile_data->capture_count);
    regexp.set_capture_name_map(compile_data->capture_name_map);
    if (compile_data->simple) {
      regexp.set_is_simple();
    } else {
      regexp.set_is_complex();
    }
 
    RegExpEngine::CompilationResult result = RegExpEngine::CompileBytecode(
        compile_data, regexp, is_one_byte, sticky, zone);
    if (result.error_message != nullptr) {
      Exceptions::ThrowUnsupportedError(result.error_message);
    }
    ASSERT(result.bytecode != nullptr);
    ASSERT(regexp.num_registers(is_one_byte) == -1 ||
           regexp.num_registers(is_one_byte) == result.num_registers);
    regexp.set_num_registers(is_one_byte, result.num_registers);
    regexp.set_bytecode(is_one_byte, sticky, *(result.bytecode));
  }
 
  ASSERT(regexp.num_registers(is_one_byte) != -1);
 
  return regexp.num_registers(is_one_byte) +
         (regexp.num_bracket_expressions() + 1) * 2;
}
 
static ObjectPtr ExecRaw(const RegExp& regexp,
                         const String& subject,
                         int32_t index,
                         bool sticky,
                         int32_t* output,
                         intptr_t output_size,
                         Zone* zone) {
  bool is_one_byte = subject.IsOneByteString();
 
  // We must have done EnsureCompiledIrregexp, so we can get the number of
  // registers.
  int number_of_capture_registers = (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, sticky));
  ASSERT(!bytecode.IsNull());
  const Object& result = Object::Handle(
      zone, IrregexpInterpreter::Match(bytecode, subject, raw_output, index));
 
  if (result.ptr() == Bool::True().ptr()) {
    // Copy capture results to the start of the registers array.
    memmove(output, raw_output, number_of_capture_registers * sizeof(int32_t));
  }
  if (result.ptr() == Object::null()) {
    // Exception during regexp processing
    Exceptions::ThrowStackOverflow();
    UNREACHABLE();
  }
  return result.ptr();
}
 
ObjectPtr BytecodeRegExpMacroAssembler::Interpret(const RegExp& regexp,
                                                  const String& subject,
                                                  const Smi& start_index,
                                                  bool sticky,
                                                  Zone* zone) {
  intptr_t required_registers = Prepare(regexp, subject, sticky, 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);
 
  const Object& result =
      Object::Handle(zone, ExecRaw(regexp, subject, start_index.Value(), sticky,
                                   output_registers, required_registers, zone));
  if (result.ptr() == Bool::True().ptr()) {
    intptr_t capture_count = regexp.num_bracket_expressions();
    intptr_t capture_register_count = (capture_count + 1) * 2;
    ASSERT(required_registers >= capture_register_count);
 
    const TypedData& result = 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.ptr();
  }
  if (result.ptr() == Object::null()) {
    // internal exception
    UNREACHABLE();
  }
  if (result.IsError()) {
    Exceptions::PropagateError(Error::Cast(result));
    UNREACHABLE();
  }
  ASSERT(result.ptr() == Bool::False().ptr());
  return Instance::null();
}
 
}  // namespace dart