Check for empty repetitions.

src/jsregexp.cc

Index: src/jsregexp.cc
diff --git a/src/jsregexp.cc b/src/jsregexp.cc
index 6cca7fc35c35a91e7f1fdd209a8297402d86b8e0..58709e6e1ab1bec64cf4c8d6176aaceeed599a4b 100644
--- a/src/jsregexp.cc
+++ b/src/jsregexp.cc
@@ -1222,6 +1222,7 @@ class RegExpCompiler {
   inline bool ignore_case() { return ignore_case_; }
   inline bool ascii() { return ascii_; }
 
+  static const int kNoRegister = -1;
  private:
   EndNode* accept_;
   int next_register_;
@@ -1313,8 +1314,26 @@ bool GenerationVariant::mentions_reg(int reg) {
 }
 
 
+bool GenerationVariant::GetStoredPosition(int reg, int* cp_offset) {
+  ASSERT_EQ(0, *cp_offset);
+  for (DeferredAction* action = actions_;
+       action != NULL;
+       action = action->next()) {
+    if (reg == action->reg()) {
+      if (action->type() == ActionNode::STORE_POSITION) {
+        *cp_offset = static_cast<DeferredCapture*>(action)->cp_offset();
+        return true;
+      } else {
+        return false;
+      }
+    }
+  }
+  return false;
+}
+
+
 int GenerationVariant::FindAffectedRegisters(OutSet* affected_registers) {
-  int max_register = -1;
+  int max_register = RegExpCompiler::kNoRegister;
   for (DeferredAction* action = actions_;
        action != NULL;
        action = action->next()) {
@@ -1576,6 +1595,18 @@ ActionNode* ActionNode::PositiveSubmatchSuccess(int stack_reg,
 }
 
 
+ActionNode* ActionNode::EmptyMatchCheck(int start_register,
+                                        int repetition_register,
+                                        int repetition_limit,
+                                        RegExpNode* on_success) {
+  ActionNode* result = new ActionNode(EMPTY_MATCH_CHECK, on_success);
+  result->data_.u_empty_match_check.start_register = start_register;
+  result->data_.u_empty_match_check.repetition_register = repetition_register;
+  result->data_.u_empty_match_check.repetition_limit = repetition_limit;
+  return result;
+}
+
+
 #define DEFINE_ACCEPT(Type)                                          \
   void Type##Node::Accept(NodeVisitor* visitor) {                    \
     visitor->Visit##Type(this);                                      \
@@ -2967,6 +2998,38 @@ bool ActionNode::Emit(RegExpCompiler* compiler, GenerationVariant* variant) {
       assembler->WriteStackPointerToRegister(
           data_.u_submatch.stack_pointer_register);
       return on_success()->Emit(compiler, variant);
+    case EMPTY_MATCH_CHECK: {
+      int start_pos_reg = data_.u_empty_match_check.start_register;
+      int stored_pos = 0;
+      int rep_reg = data_.u_empty_match_check.repetition_register;
+      bool has_minimum = (rep_reg != RegExpCompiler::kNoRegister);
+      if (!has_minimum &&

[Erik Corry, 2009/01/08 11:10:16]

If we have a minimum but we know that we didn't match zero length then we want
to emit the on_success node now with no further checks.  This seems to miss that
case.

[Christian Plesner Hansen, 2009/01/08 12:40:49]

Good point, fixed.

+          variant->GetStoredPosition(start_pos_reg, &stored_pos)) {
+        // If we know the position offset stored in the start register
+        // and the current position offset we can just bactrack or
+        // proceed immediately without checking.
+        if (stored_pos == variant->cp_offset()) {
+          assembler->GoTo(variant->backtrack());
+          return true;
+        } else {
+          return on_success()->Emit(compiler, variant);
+        }
+      }
+      if (!variant->is_trivial()) return variant->Flush(compiler, this);
+      Label skip_empty_check;
+      // If we have a minimum number of repetitions we check the current
+      // number first and skip the empty check if it's not enough.

[Erik Corry, 2009/01/08 11:10:16]

Ideally if we matched empty we should 'zoom' up to the minimum, right?  I guess
that's just an optimization.

[Christian Plesner Hansen, 2009/01/08 12:40:49]

We should but I'm not quite sure how to do that.  We may have to push a
backtrack for each of the remaining repetition, if not in practice then at least
in effect.

+      if (has_minimum) {
+        int limit = data_.u_empty_match_check.repetition_limit;
+        assembler->IfRegisterLT(rep_reg, limit, &skip_empty_check);
+      }
+      // If the match is empty we bail out, otherwise we fall through
+      // to the on-success continuation.
+      assembler->IfRegisterEqPos(data_.u_empty_match_check.start_register,
+                                 variant->backtrack());
+      assembler->Bind(&skip_empty_check);
+      return on_success()->Emit(compiler, variant);
+    }
     case POSITIVE_SUBMATCH_SUCCESS:
       if (!variant->is_trivial()) return variant->Flush(compiler, this);
       // TODO(erikcorry): Implement support.
@@ -3286,6 +3349,12 @@ void DotPrinter::VisitAction(ActionNode* that) {
     case ActionNode::POSITIVE_SUBMATCH_SUCCESS:
       stream()->Add("label=\"escape\", shape=septagon");
       break;
+    case ActionNode::EMPTY_MATCH_CHECK:
+      stream()->Add("label=\"$%i=$pos?,$%i<%i?\", shape=septagon",
+                    that->data_.u_empty_match_check.start_register,
+                    that->data_.u_empty_match_check.repetition_register,
+                    that->data_.u_empty_match_check.repetition_limit);
+      break;
   }
   stream()->Add("];\n");
   PrintAttributes(that);
@@ -3511,7 +3580,11 @@ RegExpNode* RegExpQuantifier::ToNode(int min,
   static const int kMaxUnrolledMinMatches = 3;  // Unroll (foo)+ and (foo){3,}
   static const int kMaxUnrolledMaxMatches = 3;  // Unroll (foo)? and (foo){x,3}
   if (max == 0) return on_success;  // This can happen due to recursion.
-  if (body->min_match() > 0) {
+  bool body_can_be_empty = (body->min_match() == 0);
+  int body_start_reg = RegExpCompiler::kNoRegister;
+  if (body_can_be_empty) {
+    body_start_reg = compiler->AllocateRegister();
+  } else {
     if (min > 0 && min <= kMaxUnrolledMinMatches) {
       int new_max = (max == kInfinity) ? max : max - min;
       // Recurse once to get the loop or optional matches after the fixed ones.
@@ -3548,12 +3621,27 @@ RegExpNode* RegExpQuantifier::ToNode(int min,
   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;
+  int reg_ctr = needs_counter
+      ? compiler->AllocateRegister()
+      : RegExpCompiler::kNoRegister;
   LoopChoiceNode* center = new LoopChoiceNode(body->min_match() == 0);
   RegExpNode* loop_return = needs_counter
       ? static_cast<RegExpNode*>(ActionNode::IncrementRegister(reg_ctr, center))
       : static_cast<RegExpNode*>(center);
+  if (body_can_be_empty) {
+    // If the body can be empty we need to check if it was and then
+    // backtrack.
+    loop_return = ActionNode::EmptyMatchCheck(body_start_reg,
+                                              reg_ctr,
+                                              min,
+                                              loop_return);
+  }
   RegExpNode* body_node = body->ToNode(compiler, loop_return);
+  if (body_can_be_empty) {
+    // If the body can be empty we need to store the start position
+    // so we can bail out if it was empty.
+    body_node = ActionNode::StorePosition(body_start_reg, body_node);
+  }
   GuardedAlternative body_alt(body_node);
   if (has_max) {
     Guard* body_guard = new Guard(reg_ctr, Guard::LT, max);