Optimization: The quick check should ignore the negative lookahead instead of...

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 1962 matching lines @@
   return on_success()->EatsAtLeast(recursion_depth + 1);
 }
 
 
 int BackReferenceNode::EatsAtLeast(int recursion_depth) {
   if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
   return on_success()->EatsAtLeast(recursion_depth + 1);
 }
 
 
-
 int TextNode::EatsAtLeast(int recursion_depth) {
   int answer = Length();
   if (answer >= 4) return answer;
   if (recursion_depth > RegExpCompiler::kMaxRecursion) return answer;
   return answer + on_success()->EatsAtLeast(recursion_depth + 1);
 }
 
 
+int NegativeLookaheadChoiceNode:: EatsAtLeast(int recursion_depth) {
+  if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
+  // Alternative 0 is the negative lookahead, alternative 1 is what comes
+  // afterwards.
+  RegExpNode* node = alternatives_->at(1).node();
+  return node->EatsAtLeast(recursion_depth + 1);
+}
+
+
+void NegativeLookaheadChoiceNode::GetQuickCheckDetails(
+    QuickCheckDetails* details,
+    RegExpCompiler* compiler,
+    int filled_in) {
+  // Alternative 0 is the negative lookahead, alternative 1 is what comes
+  // afterwards.
+  RegExpNode* node = alternatives_->at(1).node();
+  return node->GetQuickCheckDetails(details, compiler, filled_in);
+}
+
+
 int ChoiceNode::EatsAtLeastHelper(int recursion_depth,
                                   RegExpNode* ignore_this_node) {
   if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
   int min = 100;
   int choice_count = alternatives_->length();
   for (int i = 0; i < choice_count; i++) {
     RegExpNode* node = alternatives_->at(i).node();
     if (node == ignore_this_node) continue;
     int node_eats_at_least = node->EatsAtLeast(recursion_depth + 1);
     if (node_eats_at_least < min) min = node_eats_at_least;
@@ skipping 1015 matching lines @@
     Trace new_trace(*current_trace);
     new_trace.set_characters_preloaded(preload_is_current ?
                                          preload_characters :
                                          0);
     if (preload_has_checked_bounds) {
       new_trace.set_bound_checked_up_to(preload_characters);
     }
     new_trace.quick_check_performed()->Clear();
     alt_gen->expects_preload = preload_is_current;
     bool generate_full_check_inline = false;
-    if (alternative.node()->EmitQuickCheck(compiler,
+    if (try_to_emit_quick_check_for_alternative(i) &&
+        alternative.node()->EmitQuickCheck(compiler,
                                            &new_trace,
                                            preload_has_checked_bounds,
                                            &alt_gen->possible_success,
                                            &alt_gen->quick_check_details,
                                            i < choice_count - 1)) {
       // Quick check was generated for this choice.
       preload_is_current = true;
       preload_has_checked_bounds = true;
       // On the last choice in the ChoiceNode we generated the quick
       // check to fall through on possible success.  So now we need to
@@ skipping 912 matching lines @@
                                                 position_register,
                                                 on_success)));
   } else {
     // We use a ChoiceNode for a negative lookahead because it has most of
     // the characteristics we need.  It has the body of the lookahead as its
     // first alternative and the expression after the lookahead of the second
     // alternative.  If the first alternative succeeds then the
     // NegativeSubmatchSuccess will unwind the stack including everything the
     // choice node set up and backtrack.  If the first alternative fails then
     // the second alternative is tried, which is exactly the desired result
-    // for a negative lookahead.  In the case where the dispatch table
-    // determines that the first alternative cannot match we will save time
-    // by not trying it.  Things are not quite so well-optimized if the
-    // dispatch table determines that the second alternative cannot match.
-    // In this case we could optimize by immediately backtracking.
-    ChoiceNode* choice_node = new ChoiceNode(2);
+    // for a negative lookahead.  The NegativeLookaheadChoiceNode is a special
+    // ChoiceNode that knows to ignore the first exit when calculating quick
+    // checks.
     GuardedAlternative body_alt(
         body()->ToNode(
             compiler,
             success = new NegativeSubmatchSuccess(stack_pointer_register,
                                                   position_register)));
-    choice_node->AddAlternative(body_alt);
-    choice_node->AddAlternative(GuardedAlternative(on_success));
+    ChoiceNode* choice_node =
+        new NegativeLookaheadChoiceNode(body_alt,
+                                        GuardedAlternative(on_success));
     return ActionNode::BeginSubmatch(stack_pointer_register,
                                      position_register,
                                      choice_node);
   }
 }
 
 
 RegExpNode* RegExpCapture::ToNode(RegExpCompiler* compiler,
                                   RegExpNode* on_success) {
   return ToNode(body(), index(), compiler, on_success);
@@ skipping 680 matching lines @@
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal