Port and integrate the irregexp engine from V8

runtime/vm/regexp_ast.cc

Index: runtime/vm/regexp_ast.cc
diff --git a/runtime/vm/regexp_ast.cc b/runtime/vm/regexp_ast.cc
new file mode 100644
index 0000000000000000000000000000000000000000..83d30024f12131f026f4670aecf7956be121b672
--- /dev/null
+++ b/runtime/vm/regexp_ast.cc
@@ -0,0 +1,363 @@
+// 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 {
+
+
+// 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
+};
+
+
+static inline void PrintUtf16(uint16_t c) {
+  const char* format = (0x20 <= c && c <= 0x7F)
+                           ? "%c"
+                           : (c <= 0xff) ? "\\x%02x" : "\\u%04x";
+  OS::Print(format, c);
+}
+
+
+void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) {
+  OS::Print("(|");
+  for (intptr_t i = 0; i <  that->alternatives()->length(); i++) {
+    OS::Print(" ");
+    (*that->alternatives())[i]->Accept(this, data);
+  }
+  OS::Print(")");
+  return NULL;
+}
+
+
+void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) {
+  OS::Print("(:");
+  for (intptr_t i = 0; i < that->nodes()->length(); i++) {
+    OS::Print(" ");
+    (*that->nodes())[i]->Accept(this, data);
+  }
+  OS::Print(")");
+  return NULL;
+}
+
+
+void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
+  PrintUtf16(that.from());
+  if (!that.IsSingleton()) {
+    OS::Print("-");
+    PrintUtf16(that.to());
+  }
+}
+
+
+
+void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that,
+                                          void* data) {
+  if (that->is_negated()) OS::Print("^");
+  OS::Print("[");
+  for (intptr_t i = 0; i < that->ranges()->length(); i++) {
+    if (i > 0) OS::Print(" ");
+    VisitCharacterRange((*that->ranges())[i]);
+  }
+  OS::Print("]");
+  return NULL;
+}
+
+
+void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) {
+  switch (that->assertion_type()) {
+    case RegExpAssertion::START_OF_INPUT:
+      OS::Print("@^i");
+      break;
+    case RegExpAssertion::END_OF_INPUT:
+      OS::Print("@$i");
+      break;
+    case RegExpAssertion::START_OF_LINE:
+      OS::Print("@^l");
+      break;
+    case RegExpAssertion::END_OF_LINE:
+      OS::Print("@$l");
+       break;
+    case RegExpAssertion::BOUNDARY:
+      OS::Print("@b");
+      break;
+    case RegExpAssertion::NON_BOUNDARY:
+      OS::Print("@B");
+      break;
+  }
+  return NULL;
+}
+
+
+void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) {
+  OS::Print("'");
+  ZoneGrowableArray<uint16_t>* chardata = that->data();
+  for (intptr_t i = 0; i < chardata->length(); i++) {
+    PrintUtf16(chardata->At(i));
+  }
+  OS::Print("'");
+  return NULL;
+}
+
+
+void* RegExpUnparser::VisitText(RegExpText* that, void* data) {
+  if (that->elements()->length() == 1) {
+    (*that->elements())[0].tree()->Accept(this, data);
+  } else {
+    OS::Print("(!");
+    for (intptr_t i = 0; i < that->elements()->length(); i++) {
+      OS::Print(" ");
+      (*that->elements())[i].tree()->Accept(this, data);
+    }
+    OS::Print(")");
+  }
+  return NULL;
+}
+
+
+void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) {
+  OS::Print("(# %" Pd " ", that->min());
+  if (that->max() == RegExpTree::kInfinity) {
+    OS::Print("- ");
+  } else {
+    OS::Print("%" Pd " ", that->max());
+  }
+  OS::Print(that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n ");
+  that->body()->Accept(this, data);
+  OS::Print(")");
+  return NULL;
+}
+
+
+void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
+  OS::Print("(^ ");
+  that->body()->Accept(this, data);
+  OS::Print(")");
+  return NULL;
+}
+
+
+void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) {
+  OS::Print("(-> %s", (that->is_positive() ? "+ " : "- "));
+  that->body()->Accept(this, data);
+  OS::Print(")");
+  return NULL;
+}
+
+
+void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
+                                         void*) {
+  OS::Print("(<- %" Pd ")", that->index());
+  return NULL;
+}
+
+
+void* RegExpUnparser::VisitEmpty(RegExpEmpty*, void*) {
+  OS::Print("%%");
+  return NULL;
+}
+
+
+#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 NULL;                                                     \
+  }                                                                  \
+  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
+
+void RegExpTree::Print() {
+  RegExpUnparser unparser;
+  Accept(&unparser, NULL);
+}
+
+
+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 RegExpQuantifier::CaptureRegisters() const {
+  return body()->CaptureRegisters();
+}
+
+
+bool RegExpCapture::IsAnchoredAtStart() const {
+  return body()->IsAnchoredAtStart();
+}
+
+
+bool RegExpCapture::IsAnchoredAtEnd() const {
+  return body()->IsAnchoredAtEnd();
+}
+
+
+Interval RegExpCapture::CaptureRegisters() const {
+  Interval self(StartRegister(index()), EndRegister(index()));
+  return self.Union(body()->CaptureRegisters());
+}
+
+
+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());
+  }
+}
+
+
+Interval RegExpDisjunction::CaptureRegisters() const {
+  return ListCaptureRegisters(alternatives());
+}
+
+
+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;
+}
+
+
+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);
+  }
+}
+
+
+Interval RegExpAlternative::CaptureRegisters() const {
+  return ListCaptureRegisters(nodes());
+}
+
+
+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 RegExpAssertion::IsAnchoredAtStart() const {
+  return assertion_type() == RegExpAssertion::START_OF_INPUT;
+}
+
+
+bool RegExpAssertion::IsAnchoredAtEnd() const {
+  return assertion_type() == RegExpAssertion::END_OF_INPUT;
+}
+
+
+void RegExpTree::AppendToText(RegExpText* text) {
+  UNREACHABLE();
+}
+
+
+void RegExpAtom::AppendToText(RegExpText* text) {
+  text->AddElement(TextElement::Atom(this));
+}
+
+
+void RegExpCharacterClass::AppendToText(RegExpText* text) {
+  text->AddElement(TextElement::CharClass(this));
+}
+
+
+void RegExpText::AppendToText(RegExpText* text) {
+  for (intptr_t i = 0; i < elements()->length(); i++)
+    text->AddElement((*elements())[i]);
+}
+
+
+Interval RegExpLookahead::CaptureRegisters() const {
+  return body()->CaptureRegisters();
+}
+
+
+bool RegExpLookahead::IsAnchoredAtStart() const {
+  return is_positive() && body()->IsAnchoredAtStart();
+}
+
+}  // namespace dart