1 files changed, 432 insertions, 0 deletions
diff --git a/js/src/irregexp/imported/regexp-ast.cc b/js/src/irregexp/imported/regexp-ast.cc
new file mode 100644
index 0000000000..63eeb5c05d
--- /dev/null
+++ b/js/src/irregexp/imported/regexp-ast.cc
@@ -0,0 +1,432 @@
+// Copyright 2016 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "irregexp/imported/regexp-ast.h"
+
+
+namespace v8 {
+namespace internal {
+
+#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() { 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() { return true; }
+FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
+#undef MAKE_TYPE_CASE
+
+namespace {
+
+Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) {
+  Interval result = Interval::Empty();
+  for (int i = 0; i < children->length(); i++)
+    result = result.Union(children->at(i)->CaptureRegisters());
+  return result;
+}
+
+}  // namespace
+
+Interval RegExpAlternative::CaptureRegisters() {
+  return ListCaptureRegisters(nodes());
+}
+
+
+Interval RegExpDisjunction::CaptureRegisters() {
+  return ListCaptureRegisters(alternatives());
+}
+
+
+Interval RegExpLookaround::CaptureRegisters() {
+  return body()->CaptureRegisters();
+}
+
+
+Interval RegExpCapture::CaptureRegisters() {
+  Interval self(StartRegister(index()), EndRegister(index()));
+  return self.Union(body()->CaptureRegisters());
+}
+
+
+Interval RegExpQuantifier::CaptureRegisters() {
+  return body()->CaptureRegisters();
+}
+
+
+bool RegExpAssertion::IsAnchoredAtStart() {
+  return assertion_type() == RegExpAssertion::Type::START_OF_INPUT;
+}
+
+
+bool RegExpAssertion::IsAnchoredAtEnd() {
+  return assertion_type() == RegExpAssertion::Type::END_OF_INPUT;
+}
+
+
+bool RegExpAlternative::IsAnchoredAtStart() {
+  ZoneList<RegExpTree*>* nodes = this->nodes();
+  for (int 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() {
+  ZoneList<RegExpTree*>* nodes = this->nodes();
+  for (int 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() {
+  ZoneList<RegExpTree*>* alternatives = this->alternatives();
+  for (int i = 0; i < alternatives->length(); i++) {
+    if (!alternatives->at(i)->IsAnchoredAtStart()) return false;
+  }
+  return true;
+}
+
+
+bool RegExpDisjunction::IsAnchoredAtEnd() {
+  ZoneList<RegExpTree*>* alternatives = this->alternatives();
+  for (int i = 0; i < alternatives->length(); i++) {
+    if (!alternatives->at(i)->IsAnchoredAtEnd()) return false;
+  }
+  return true;
+}
+
+
+bool RegExpLookaround::IsAnchoredAtStart() {
+  return is_positive() && type() == LOOKAHEAD && body()->IsAnchoredAtStart();
+}
+
+
+bool RegExpCapture::IsAnchoredAtStart() { return body()->IsAnchoredAtStart(); }
+
+
+bool RegExpCapture::IsAnchoredAtEnd() { return body()->IsAnchoredAtEnd(); }
+
+namespace {
+
+// 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 final : public RegExpVisitor {
+ public:
+  RegExpUnparser(std::ostream& os, Zone* zone) : os_(os), zone_(zone) {}
+  void VisitCharacterRange(CharacterRange that);
+#define MAKE_CASE(Name) void* Visit##Name(RegExp##Name*, void* data) override;
+  FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
+#undef MAKE_CASE
+ private:
+  std::ostream& os_;
+  Zone* zone_;
+};
+
+}  // namespace
+
+void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) {
+  os_ << "(|";
+  for (int i = 0; i < that->alternatives()->length(); i++) {
+    os_ << " ";
+    that->alternatives()->at(i)->Accept(this, data);
+  }
+  os_ << ")";
+  return nullptr;
+}
+
+
+void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) {
+  os_ << "(:";
+  for (int i = 0; i < that->nodes()->length(); i++) {
+    os_ << " ";
+    that->nodes()->at(i)->Accept(this, data);
+  }
+  os_ << ")";
+  return nullptr;
+}
+
+
+void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
+  os_ << AsUC32(that.from());
+  if (!that.IsSingleton()) {
+    os_ << "-" << AsUC32(that.to());
+  }
+}
+
+void* RegExpUnparser::VisitClassRanges(RegExpClassRanges* that, void* data) {
+  if (that->is_negated()) os_ << "^";
+  os_ << "[";
+  for (int i = 0; i < that->ranges(zone_)->length(); i++) {
+    if (i > 0) os_ << " ";
+    VisitCharacterRange(that->ranges(zone_)->at(i));
+  }
+  os_ << "]";
+  return nullptr;
+}
+
+void* RegExpUnparser::VisitClassSetOperand(RegExpClassSetOperand* that,
+                                           void* data) {
+  os_ << "![";
+  for (int i = 0; i < that->ranges()->length(); i++) {
+    if (i > 0) os_ << " ";
+    VisitCharacterRange(that->ranges()->at(i));
+  }
+  if (that->has_strings()) {
+    for (auto iter : *that->strings()) {
+      os_ << " '";
+      os_ << std::string(iter.first.begin(), iter.first.end());
+      os_ << "'";
+    }
+  }
+  os_ << "]";
+  return nullptr;
+}
+
+void* RegExpUnparser::VisitClassSetExpression(RegExpClassSetExpression* that,
+                                              void* data) {
+  switch (that->operation()) {
+    case RegExpClassSetExpression::OperationType::kUnion:
+      os_ << "++";
+      break;
+    case RegExpClassSetExpression::OperationType::kIntersection:
+      os_ << "&&";
+      break;
+    case RegExpClassSetExpression::OperationType::kSubtraction:
+      os_ << "--";
+      break;
+  }
+  if (that->is_negated()) os_ << "^";
+  os_ << "[";
+  for (int i = 0; i < that->operands()->length(); i++) {
+    if (i > 0) os_ << " ";
+    that->operands()->at(i)->Accept(this, data);
+  }
+  os_ << "]";
+  return nullptr;
+}
+
+void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) {
+  switch (that->assertion_type()) {
+    case RegExpAssertion::Type::START_OF_INPUT:
+      os_ << "@^i";
+      break;
+    case RegExpAssertion::Type::END_OF_INPUT:
+      os_ << "@$i";
+      break;
+    case RegExpAssertion::Type::START_OF_LINE:
+      os_ << "@^l";
+      break;
+    case RegExpAssertion::Type::END_OF_LINE:
+      os_ << "@$l";
+      break;
+    case RegExpAssertion::Type::BOUNDARY:
+      os_ << "@b";
+      break;
+    case RegExpAssertion::Type::NON_BOUNDARY:
+      os_ << "@B";
+      break;
+  }
+  return nullptr;
+}
+
+
+void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) {
+  os_ << "'";
+  base::Vector<const base::uc16> chardata = that->data();
+  for (int i = 0; i < chardata.length(); i++) {
+    os_ << AsUC16(chardata[i]);
+  }
+  os_ << "'";
+  return nullptr;
+}
+
+
+void* RegExpUnparser::VisitText(RegExpText* that, void* data) {
+  if (that->elements()->length() == 1) {
+    that->elements()->at(0).tree()->Accept(this, data);
+  } else {
+    os_ << "(!";
+    for (int i = 0; i < that->elements()->length(); i++) {
+      os_ << " ";
+      that->elements()->at(i).tree()->Accept(this, data);
+    }
+    os_ << ")";
+  }
+  return nullptr;
+}
+
+
+void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) {
+  os_ << "(# " << that->min() << " ";
+  if (that->max() == RegExpTree::kInfinity) {
+    os_ << "- ";
+  } else {
+    os_ << that->max() << " ";
+  }
+  os_ << (that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n ");
+  that->body()->Accept(this, data);
+  os_ << ")";
+  return nullptr;
+}
+
+
+void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
+  os_ << "(^ ";
+  that->body()->Accept(this, data);
+  os_ << ")";
+  return nullptr;
+}
+
+void* RegExpUnparser::VisitGroup(RegExpGroup* that, void* data) {
+  os_ << "(?: ";
+  that->body()->Accept(this, data);
+  os_ << ")";
+  return nullptr;
+}
+
+void* RegExpUnparser::VisitLookaround(RegExpLookaround* that, void* data) {
+  os_ << "(";
+  os_ << (that->type() == RegExpLookaround::LOOKAHEAD ? "->" : "<-");
+  os_ << (that->is_positive() ? " + " : " - ");
+  that->body()->Accept(this, data);
+  os_ << ")";
+  return nullptr;
+}
+
+
+void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
+                                         void* data) {
+  os_ << "(<- " << that->index() << ")";
+  return nullptr;
+}
+
+
+void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) {
+  os_ << '%';
+  return nullptr;
+}
+
+std::ostream& RegExpTree::Print(std::ostream& os, Zone* zone) {
+  RegExpUnparser unparser(os, zone);
+  Accept(&unparser, nullptr);
+  return os;
+}
+
+RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
+    : alternatives_(alternatives) {
+  DCHECK_LT(1, alternatives->length());
+  RegExpTree* first_alternative = alternatives->at(0);
+  min_match_ = first_alternative->min_match();
+  max_match_ = first_alternative->max_match();
+  for (int i = 1; i < alternatives->length(); i++) {
+    RegExpTree* alternative = alternatives->at(i);
+    min_match_ = std::min(min_match_, alternative->min_match());
+    max_match_ = std::max(max_match_, alternative->max_match());
+  }
+}
+
+namespace {
+
+int IncreaseBy(int previous, int increase) {
+  if (RegExpTree::kInfinity - previous < increase) {
+    return RegExpTree::kInfinity;
+  } else {
+    return previous + increase;
+  }
+}
+
+}  // namespace
+
+RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes)
+    : nodes_(nodes) {
+  DCHECK_LT(1, nodes->length());
+  min_match_ = 0;
+  max_match_ = 0;
+  for (int i = 0; i < nodes->length(); i++) {
+    RegExpTree* node = nodes->at(i);
+    int node_min_match = node->min_match();
+    min_match_ = IncreaseBy(min_match_, node_min_match);
+    int node_max_match = node->max_match();
+    max_match_ = IncreaseBy(max_match_, node_max_match);
+  }
+}
+
+RegExpClassSetOperand::RegExpClassSetOperand(ZoneList<CharacterRange>* ranges,
+                                             CharacterClassStrings* strings)
+    : ranges_(ranges), strings_(strings) {
+  DCHECK_NOT_NULL(ranges);
+  min_match_ = 0;
+  max_match_ = 0;
+  if (!ranges->is_empty()) {
+    min_match_ = 1;
+    max_match_ = 2;
+  }
+  if (has_strings()) {
+    for (auto string : *strings) {
+      min_match_ = std::min(min_match_, string.second->min_match());
+      max_match_ = std::max(max_match_, string.second->max_match());
+    }
+  }
+}
+
+RegExpClassSetExpression::RegExpClassSetExpression(
+    OperationType op, bool is_negated, bool may_contain_strings,
+    ZoneList<RegExpTree*>* operands)
+    : operation_(op),
+      is_negated_(is_negated),
+      may_contain_strings_(may_contain_strings),
+      operands_(operands) {
+  DCHECK_NOT_NULL(operands);
+  DCHECK_IMPLIES(is_negated_, !may_contain_strings_);
+  max_match_ = 0;
+  for (auto op : *operands) {
+    max_match_ = std::max(max_match_, op->max_match());
+  }
+}
+
+// static
+RegExpClassSetExpression* RegExpClassSetExpression::Empty(Zone* zone,
+                                                          bool is_negated) {
+  ZoneList<CharacterRange>* ranges =
+      zone->template New<ZoneList<CharacterRange>>(0, zone);
+  RegExpClassSetOperand* op =
+      zone->template New<RegExpClassSetOperand>(ranges, nullptr);
+  ZoneList<RegExpTree*>* operands =
+      zone->template New<ZoneList<RegExpTree*>>(1, zone);
+  operands->Add(op, zone);
+  return zone->template New<RegExpClassSetExpression>(
+      RegExpClassSetExpression::OperationType::kUnion, is_negated, false,
+      operands);
+}
+
+}  // namespace internal
+}  // namespace v8