From 5d3cc28967e4d1db5ba9e564adbf55af48bb8055 Mon Sep 17 00:00:00 2001
From: "christian.plesner.hansen@gmail.com"
 <christian.plesner.hansen@gmail.com@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Wed, 17 Dec 2008 13:16:38 +0000
Subject: [PATCH] Fixed bug in interest propagation caused by following the
 loop edge out of a loop choice node before the continuation edge.

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@990 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/jsregexp.cc            | 45 +++++++++++++++++++++++++++++++++-----
 src/jsregexp.h             | 23 ++++++++++++++++++-
 test/cctest/test-regexp.cc |  2 +-
 3 files changed, 63 insertions(+), 7 deletions(-)

diff --git a/src/jsregexp.cc b/src/jsregexp.cc
index fe5bf05d2..4855443de 100644
--- a/src/jsregexp.cc
+++ b/src/jsregexp.cc
@@ -1596,6 +1596,11 @@ FOR_EACH_NODE_TYPE(DEFINE_ACCEPT)
 #undef DEFINE_ACCEPT
 
 
+void LoopChoiceNode::Accept(NodeVisitor* visitor) {
+  visitor->VisitLoopChoice(this);
+}
+
+
 // -------------------------------------------------------------------
 // Emit code.
 
@@ -2070,6 +2075,20 @@ int ChoiceNode::GreedyLoopTextLength(GuardedAlternative* alternative) {
 }
 
 
+void LoopChoiceNode::AddLoopAlternative(GuardedAlternative alt) {
+  ASSERT_EQ(loop_node_, NULL);
+  AddAlternative(alt);
+  loop_node_ = alt.node();
+}
+
+
+void LoopChoiceNode::AddContinueAlternative(GuardedAlternative alt) {
+  ASSERT_EQ(continue_node_, NULL);
+  AddAlternative(alt);
+  continue_node_ = alt.node();
+}
+
+
 bool LoopChoiceNode::Emit(RegExpCompiler* compiler,
                           GenerationVariant* variant) {
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
@@ -2680,7 +2699,7 @@ RegExpNode* RegExpQuantifier::ToNode(int min,
   bool has_max = max < RegExpTree::kInfinity;
   bool needs_counter = has_min || has_max;
   int reg_ctr = needs_counter ? compiler->AllocateRegister() : -1;
-  ChoiceNode* center = new LoopChoiceNode(2);
+  LoopChoiceNode* center = new LoopChoiceNode();
   RegExpNode* loop_return = needs_counter
       ? static_cast<RegExpNode*>(ActionNode::IncrementRegister(reg_ctr, center))
       : static_cast<RegExpNode*>(center);
@@ -2696,11 +2715,11 @@ RegExpNode* RegExpQuantifier::ToNode(int min,
     rest_alt.AddGuard(rest_guard);
   }
   if (is_greedy) {
-    center->AddAlternative(body_alt);
-    center->AddAlternative(rest_alt);
+    center->AddLoopAlternative(body_alt);
+    center->AddContinueAlternative(rest_alt);
   } else {
-    center->AddAlternative(rest_alt);
-    center->AddAlternative(body_alt);
+    center->AddContinueAlternative(rest_alt);
+    center->AddLoopAlternative(body_alt);
   }
   if (needs_counter) {
     return ActionNode::SetRegister(reg_ctr, 0, center);
@@ -3358,6 +3377,22 @@ void AssertionPropagation::VisitChoice(ChoiceNode* that) {
 }
 
 
+void AssertionPropagation::VisitLoopChoice(LoopChoiceNode* that) {
+  NodeInfo* info = that->info();
+  for (int i = 0; i < that->alternatives()->length(); i++) {
+    RegExpNode* node = that->alternatives()->at(i).node();
+    if (node != that->loop_node()) {
+      EnsureAnalyzed(node);
+      info->AddFromFollowing(node->info());
+    }
+  }
+  // Check the loop last since it may need the value of this node
+  // to get a correct result.
+  EnsureAnalyzed(that->loop_node());
+  info->AddFromFollowing(that->loop_node()->info());
+}
+
+
 void AssertionPropagation::VisitBackReference(BackReferenceNode* that) {
   EnsureAnalyzed(that->on_success());
 }
diff --git a/src/jsregexp.h b/src/jsregexp.h
index 0cac1724a..5280a2225 100644
--- a/src/jsregexp.h
+++ b/src/jsregexp.h
@@ -912,9 +912,28 @@ class ChoiceNode: public RegExpNode {
 
 class LoopChoiceNode: public ChoiceNode {
  public:
-  explicit LoopChoiceNode(int expected_size) : ChoiceNode(expected_size) { }
+  explicit LoopChoiceNode()
+      : ChoiceNode(2),
+        loop_node_(NULL),
+        continue_node_(NULL) { }
+  void AddLoopAlternative(GuardedAlternative alt);
+  void AddContinueAlternative(GuardedAlternative alt);
   virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
   virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); }
+  RegExpNode* loop_node() { return loop_node_; }
+  RegExpNode* continue_node() { return continue_node_; }
+  virtual void Accept(NodeVisitor* visitor);
+
+ private:
+  // AddAlternative is made private for loop nodes because alternatives
+  // should not be added freely, we need to keep track of which node
+  // goes back to the node itself.
+  void AddAlternative(GuardedAlternative node) {
+    ChoiceNode::AddAlternative(node);
+  }
+
+  RegExpNode* loop_node_;
+  RegExpNode* continue_node_;
 };
 
 
@@ -1024,6 +1043,7 @@ class NodeVisitor {
   virtual void Visit##Type(Type##Node* that) = 0;
 FOR_EACH_NODE_TYPE(DECLARE_VISIT)
 #undef DECLARE_VISIT
+  virtual void VisitLoopChoice(LoopChoiceNode* that) { VisitChoice(that); }
 };
 
 
@@ -1105,6 +1125,7 @@ class AssertionPropagation: public NodeVisitor {
   virtual void Visit##Type(Type##Node* that);
 FOR_EACH_NODE_TYPE(DECLARE_VISIT)
 #undef DECLARE_VISIT
+  virtual void VisitLoopChoice(LoopChoiceNode* that);
 
  private:
   bool ignore_case_;
diff --git a/test/cctest/test-regexp.cc b/test/cctest/test-regexp.cc
index b89c03798..19ced1615 100644
--- a/test/cctest/test-regexp.cc
+++ b/test/cctest/test-regexp.cc
@@ -1466,5 +1466,5 @@ TEST(CharClassDifference) {
 
 TEST(Graph) {
   V8::Initialize(NULL);
-  Execute("\\bboy\\b", false, true, true);
+  Execute("\\b\\w+\\b", false, true, true);
 }
-- 
2.34.1