Interest propagation bugfix.

src/jsregexp.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1578 matching lines @@
 
 
 #define DEFINE_ACCEPT(Type)                                          \
   void Type##Node::Accept(NodeVisitor* visitor) {                    \
     visitor->Visit##Type(this);                                      \
   }
 FOR_EACH_NODE_TYPE(DEFINE_ACCEPT)
 #undef DEFINE_ACCEPT
 
 
+void LoopChoiceNode::Accept(NodeVisitor* visitor) {
+  visitor->VisitLoopChoice(this);
+}
+
+
 // -------------------------------------------------------------------
 // Emit code.
 
 
 void ChoiceNode::GenerateGuard(RegExpMacroAssembler* macro_assembler,
                                Guard* guard,
                                GenerationVariant* variant) {
   switch (guard->op()) {
     case Guard::LT:
       ASSERT(!variant->mentions_reg(guard->reg()));
@@ skipping 454 matching lines @@
       return kNodeIsTooComplexForGreedyLoops;
     }
     length += node_length;
     SeqRegExpNode* seq_node = static_cast<SeqRegExpNode*>(node);
     node = seq_node->on_success();
   }
   return length;
 }
 
 
+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();
   if (variant->stop_node() == this) {
     int text_length = GreedyLoopTextLength(&(alternatives_->at(0)));
     ASSERT(text_length != kNodeIsTooComplexForGreedyLoops);
     // Update the counter-based backtracking info on the stack.  This is an
     // optimization for greedy loops (see below).
     ASSERT(variant->cp_offset() == text_length);
     macro_assembler->AdvanceCurrentPosition(text_length);
@@ skipping 581 matching lines @@
                                      RegExpCompiler* compiler,
                                      RegExpNode* on_success) {
   // x{f, t} becomes this:
   //
   //             (r++)<-.
   //               |     `
   //               |     (x)
   //               v     ^
   //      (r=0)-->(?)---/ [if r < t]
   //               |
   //   [if r >= f] \----> ...

[Erik Corry, 2008/12/17 13:14:41]

Someone should build this in wrought iron and you could use it as an "Irregexp
Christmas tree".

   //
   //
   // TODO(someone): clear captures on repetition and handle empty
   //   matches.
   bool has_min = min > 0;
   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);
   RegExpNode* body_node = body->ToNode(compiler, loop_return);
   GuardedAlternative body_alt(body_node);
   if (has_max) {
     Guard* body_guard = new Guard(reg_ctr, Guard::LT, max);
     body_alt.AddGuard(body_guard);
   }
   GuardedAlternative rest_alt(on_success);
   if (has_min) {
     Guard* rest_guard = new Guard(reg_ctr, Guard::GEQ, 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);
   } else {
     return center;
   }
 }
 
 
 RegExpNode* RegExpAssertion::ToNode(RegExpCompiler* compiler,
@@ skipping 637 matching lines @@
   for (int i = 0; i < that->alternatives()->length(); i++) {
     RegExpNode* node = that->alternatives()->at(i).node();
     EnsureAnalyzed(node);
     // Anything the following nodes need to know has to be known by
     // this node also, so it can pass it on.
     info->AddFromFollowing(node->info());
   }
 }
 
 
+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());
 }
 
 
 // -------------------------------------------------------------------
 // Assumption expansion
 
 
 RegExpNode* RegExpNode::EnsureExpanded(NodeInfo* info) {
@@ skipping 486 matching lines @@
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal