Check for empty repetitions.

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 1204 matching lines @@
   EndNode* accept() { return accept_; }
 
   static const int kMaxRecursion = 100;
   inline int recursion_depth() { return recursion_depth_; }
   inline void IncrementRecursionDepth() { recursion_depth_++; }
   inline void DecrementRecursionDepth() { recursion_depth_--; }
 
   inline bool ignore_case() { return ignore_case_; }
   inline bool ascii() { return ascii_; }
 
+  static const int kNoRegister = -1;
  private:
   EndNode* accept_;
   int next_register_;
   List<RegExpNode*>* work_list_;
   int recursion_depth_;
   RegExpMacroAssembler* macro_assembler_;
   bool ignore_case_;
   bool ascii_;
 };
 
@@ skipping 71 matching lines @@
 bool GenerationVariant::mentions_reg(int reg) {
   for (DeferredAction* action = actions_;
        action != NULL;
        action = action->next()) {
     if (reg == action->reg()) return true;
   }
   return false;
 }
 
 
+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()) {
     affected_registers->Set(action->reg());
     if (action->reg() > max_register) max_register = action->reg();
   }
   return max_register;
 }
 
 
@@ skipping 241 matching lines @@
 ActionNode* ActionNode::PositiveSubmatchSuccess(int stack_reg,
                                                 int position_reg,
                                                 RegExpNode* on_success) {
   ActionNode* result = new ActionNode(POSITIVE_SUBMATCH_SUCCESS, on_success);
   result->data_.u_submatch.stack_pointer_register = stack_reg;
   result->data_.u_submatch.current_position_register = position_reg;
   return result;
 }
 
 
+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);                                      \
   }
 FOR_EACH_NODE_TYPE(DEFINE_ACCEPT)
 #undef DEFINE_ACCEPT
 
 
 void LoopChoiceNode::Accept(NodeVisitor* visitor) {
   visitor->VisitLoopChoice(this);
@@ skipping 1371 matching lines @@
       new_variant.add_action(&new_set);
       return on_success()->Emit(compiler, &new_variant);
     }
     case BEGIN_SUBMATCH:
       if (!variant->is_trivial()) return variant->Flush(compiler, this);
       assembler->WriteCurrentPositionToRegister(
           data_.u_submatch.current_position_register, 0);
       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.
       if (info()->follows_word_interest ||
           info()->follows_newline_interest ||
           info()->follows_start_interest) {
         return false;
       }
       if (info()->at_end) {
         Label at_end;
@@ skipping 299 matching lines @@
       stream()->Add("label=\"$%i:=$pos\", shape=octagon",
                     that->data_.u_position_register.reg);
       break;
     case ActionNode::BEGIN_SUBMATCH:
       stream()->Add("label=\"$%i:=$pos,begin\", shape=septagon",
                     that->data_.u_submatch.current_position_register);
       break;
     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);
   RegExpNode* successor = that->on_success();
   stream()->Add("  n%p -> n%p;\n", that, successor);
   Visit(successor);
 }
 
 
 class DispatchTableDumper {
@@ skipping 205 matching lines @@
   // where max_match is zero the parser has removed the quantifier if min was
   // > 0 and removed the atom if min was 0.  See AddQuantifierToAtom.
 
   // If we know that we cannot match zero length then things are a little
   // simpler since we don't need to make the special zero length match check
   // from step 2.1.  If the min and max are small we can unroll a little in
   // this case.
   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.
       RegExpNode* answer =
           ToNode(0, new_max, is_greedy, body, compiler, on_success);
       // Unroll the forced matches from 0 to min.  This can cause chains of
       // TextNodes (which the parser does not generate).  These should be
       // combined if it turns out they hinder good code generation.
       for (int i = 0; i < min; i++) {
         answer = body->ToNode(compiler, answer);
@@ skipping 16 matching lines @@
                                                                       answer)));
         }
         answer = alternation;
       }
       return answer;
     }
   }
   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);
     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);
   }
@@ skipping 820 matching lines @@
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal