runtime/vm/regexp_ast.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_ast.h"

#include "platform/utils.h"
#include "vm/os.h"

namespace dart {

#define MAKE_ACCEPT(Name)                                                      \
  void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) {             \
    return visitor->Visit##Name(this, data);                                   \
  }
FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
#undef MAKE_ACCEPT

#define MAKE_TYPE_CASE(Name)                                                   \
  RegExp##Name* RegExpTree::As##Name() {                                       \
    return nullptr;                                                            \
  }                                                                            \
  bool RegExpTree::Is##Name() const {                                          \
    return false;                                                              \
  }
FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
#undef MAKE_TYPE_CASE

#define MAKE_TYPE_CASE(Name)                                                   \
  RegExp##Name* RegExp##Name::As##Name() {                                     \
    return this;                                                               \
  }                                                                            \
  bool RegExp##Name::Is##Name() const {                                        \
    return true;                                                               \
  }
FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
#undef MAKE_TYPE_CASE

static Interval ListCaptureRegisters(ZoneGrowableArray<RegExpTree*>* children) {
  Interval result = Interval::Empty();
  for (intptr_t i = 0; i < children->length(); i++)
    result = result.Union(children->At(i)->CaptureRegisters());
  return result;
}

Interval RegExpAlternative::CaptureRegisters() const {
  return ListCaptureRegisters(nodes());
}

Interval RegExpDisjunction::CaptureRegisters() const {
  return ListCaptureRegisters(alternatives());
}

Interval RegExpLookaround::CaptureRegisters() const {
  return body()->CaptureRegisters();
}

Interval RegExpCapture::CaptureRegisters() const {
  Interval self(StartRegister(index()), EndRegister(index()));
  return self.Union(body()->CaptureRegisters());
}

Interval RegExpQuantifier::CaptureRegisters() const {
  return body()->CaptureRegisters();
}

bool RegExpAssertion::IsAnchoredAtStart() const {
  return assertion_type() == RegExpAssertion::START_OF_INPUT;
}

bool RegExpAssertion::IsAnchoredAtEnd() const {
  return assertion_type() == RegExpAssertion::END_OF_INPUT;
}

bool RegExpAlternative::IsAnchoredAtStart() const {
  ZoneGrowableArray<RegExpTree*>* nodes = this->nodes();
  for (intptr_t i = 0; i < nodes->length(); i++) {
    RegExpTree* node = nodes->At(i);
    if (node->IsAnchoredAtStart()) {
      return true;
    }
    if (node->max_match() > 0) {
      return false;
    }
  }
  return false;
}

bool RegExpAlternative::IsAnchoredAtEnd() const {
  ZoneGrowableArray<RegExpTree*>* nodes = this->nodes();
  for (intptr_t i = nodes->length() - 1; i >= 0; i--) {
    RegExpTree* node = nodes->At(i);
    if (node->IsAnchoredAtEnd()) {
      return true;
    }
    if (node->max_match() > 0) {
      return false;
    }
  }
  return false;
}

bool RegExpDisjunction::IsAnchoredAtStart() const {
  ZoneGrowableArray<RegExpTree*>* alternatives = this->alternatives();
  for (intptr_t i = 0; i < alternatives->length(); i++) {
    if (!alternatives->At(i)->IsAnchoredAtStart()) return false;
  }
  return true;
}

bool RegExpDisjunction::IsAnchoredAtEnd() const {
  ZoneGrowableArray<RegExpTree*>* alternatives = this->alternatives();
  for (intptr_t i = 0; i < alternatives->length(); i++) {
    if (!alternatives->At(i)->IsAnchoredAtEnd()) return false;
  }
  return true;
}

bool RegExpLookaround::IsAnchoredAtStart() const {
  return is_positive() && type() == LOOKAHEAD && body()->IsAnchoredAtStart();
}

bool RegExpCapture::IsAnchoredAtStart() const {
  return body()->IsAnchoredAtStart();
}

bool RegExpCapture::IsAnchoredAtEnd() const {
  return body()->IsAnchoredAtEnd();
}

// Convert regular expression trees to a simple sexp representation.
// This representation should be different from the input grammar
// in as many cases as possible, to make it more difficult for incorrect
// parses to look as correct ones which is likely if the input and
// output formats are alike.
class RegExpUnparser : public RegExpVisitor {
 public:
  void VisitCharacterRange(CharacterRange that);
#define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, void* data);
  FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
#undef MAKE_CASE
};

void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) {
  OS::PrintErr("(|");
  for (intptr_t i = 0; i < that->alternatives()->length(); i++) {
    OS::PrintErr(" ");
    (*that->alternatives())[i]->Accept(this, data);
  }
  OS::PrintErr(")");
  return nullptr;
}

void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) {
  OS::PrintErr("(:");
  for (intptr_t i = 0; i < that->nodes()->length(); i++) {
    OS::PrintErr(" ");
    (*that->nodes())[i]->Accept(this, data);
  }
  OS::PrintErr(")");
  return nullptr;
}

void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
  PrintUtf16(that.from());
  if (!that.IsSingleton()) {
    OS::PrintErr("-");
    PrintUtf16(that.to());
  }
}

void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that,
                                          void* data) {
  if (that->is_negated()) OS::PrintErr("^");
  OS::PrintErr("[");
  for (intptr_t i = 0; i < that->ranges()->length(); i++) {
    if (i > 0) OS::PrintErr(" ");
    VisitCharacterRange((*that->ranges())[i]);
  }
  OS::PrintErr("]");
  return nullptr;
}

void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) {
  switch (that->assertion_type()) {
    case RegExpAssertion::START_OF_INPUT:
      OS::PrintErr("@^i");
      break;
    case RegExpAssertion::END_OF_INPUT:
      OS::PrintErr("@$i");
      break;
    case RegExpAssertion::START_OF_LINE:
      OS::PrintErr("@^l");
      break;
    case RegExpAssertion::END_OF_LINE:
      OS::PrintErr("@$l");
      break;
    case RegExpAssertion::BOUNDARY:
      OS::PrintErr("@b");
      break;
    case RegExpAssertion::NON_BOUNDARY:
      OS::PrintErr("@B");
      break;
  }
  return nullptr;
}

void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) {
  OS::PrintErr("'");
  ZoneGrowableArray<uint16_t>* chardata = that->data();
  for (intptr_t i = 0; i < chardata->length(); i++) {
    PrintUtf16(chardata->At(i));
  }
  OS::PrintErr("'");
  return nullptr;
}

void* RegExpUnparser::VisitText(RegExpText* that, void* data) {
  if (that->elements()->length() == 1) {
    (*that->elements())[0].tree()->Accept(this, data);
  } else {
    OS::PrintErr("(!");
    for (intptr_t i = 0; i < that->elements()->length(); i++) {
      OS::PrintErr(" ");
      (*that->elements())[i].tree()->Accept(this, data);
    }
    OS::PrintErr(")");
  }
  return nullptr;
}

void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) {
  OS::PrintErr("(# %" Pd " ", that->min());
  if (that->max() == RegExpTree::kInfinity) {
    OS::PrintErr("- ");
  } else {
    OS::PrintErr("%" Pd " ", that->max());
  }
  OS::PrintErr(that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n ");
  that->body()->Accept(this, data);
  OS::PrintErr(")");
  return nullptr;
}

void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
  OS::PrintErr("(^ ");
  that->body()->Accept(this, data);
  OS::PrintErr(")");
  return nullptr;
}

void* RegExpUnparser::VisitLookaround(RegExpLookaround* that, void* data) {
  OS::PrintErr("(");
  OS::PrintErr("(%s %s",
               (that->type() == RegExpLookaround::LOOKAHEAD ? "->" : "<-"),
               (that->is_positive() ? "+ " : "- "));
  that->body()->Accept(this, data);
  OS::PrintErr(")");
  return nullptr;
}

void* RegExpUnparser::VisitBackReference(RegExpBackReference* that, void*) {
  OS::PrintErr("(<- %" Pd ")", that->index());
  return nullptr;
}

void* RegExpUnparser::VisitEmpty(RegExpEmpty*, void*) {
  OS::PrintErr("%%");
  return nullptr;
}

void RegExpTree::Print() {
  RegExpUnparser unparser;
  Accept(&unparser, nullptr);
}

RegExpDisjunction::RegExpDisjunction(
    ZoneGrowableArray<RegExpTree*>* alternatives)
    : alternatives_(alternatives) {
  ASSERT(alternatives->length() > 1);
  RegExpTree* first_alternative = alternatives->At(0);
  min_match_ = first_alternative->min_match();
  max_match_ = first_alternative->max_match();
  for (intptr_t i = 1; i < alternatives->length(); i++) {
    RegExpTree* alternative = alternatives->At(i);
    min_match_ = Utils::Minimum(min_match_, alternative->min_match());
    max_match_ = Utils::Maximum(max_match_, alternative->max_match());
  }
}

static intptr_t IncreaseBy(intptr_t previous, intptr_t increase) {
  if (RegExpTree::kInfinity - previous < increase) {
    return RegExpTree::kInfinity;
  } else {
    return previous + increase;
  }
}

RegExpAlternative::RegExpAlternative(ZoneGrowableArray<RegExpTree*>* nodes)
    : nodes_(nodes) {
  ASSERT(nodes->length() > 1);
  min_match_ = 0;
  max_match_ = 0;
  for (intptr_t i = 0; i < nodes->length(); i++) {
    RegExpTree* node = nodes->At(i);
    intptr_t node_min_match = node->min_match();
    min_match_ = IncreaseBy(min_match_, node_min_match);
    intptr_t node_max_match = node->max_match();
    max_match_ = IncreaseBy(max_match_, node_max_match);
  }
}

}  // namespace dart