Irregexp: Added derived knowledge of whether we are at the start of input.

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 1251 matching lines @@
     Handle<String> pattern) {
 #ifdef DEBUG
   if (FLAG_trace_regexp_assembler)
     macro_assembler_ = new RegExpMacroAssemblerTracer(macro_assembler);
   else
 #endif
     macro_assembler_ = macro_assembler;
   List <RegExpNode*> work_list(0);
   work_list_ = &work_list;
   Label fail;
-  macro_assembler->PushBacktrack(&fail);
+  macro_assembler_->PushBacktrack(&fail);
   Trace new_trace;
   start->Emit(this, &new_trace);
   macro_assembler_->Bind(&fail);
   macro_assembler_->Fail();
   while (!work_list.is_empty()) {
     work_list.RemoveLast()->Emit(this, &new_trace);
   }
   if (reg_exp_too_big_) return IrregexpRegExpTooBig(pattern);
   Handle<FixedArray> array =
       Factory::NewFixedArray(RegExpImpl::kIrregexpDataLength);
@@ skipping 778 matching lines @@
   // Alternative 0 is the negative lookahead, alternative 1 is what comes
   // afterwards.
   RegExpNode* node = alternatives_->at(1).node();
   return node->EatsAtLeast(still_to_find, recursion_depth + 1);
 }
 
 
 void NegativeLookaheadChoiceNode::GetQuickCheckDetails(
     QuickCheckDetails* details,
     RegExpCompiler* compiler,
-    int filled_in) {
+    int filled_in,
+    bool not_at_start) {
   // 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);
+  return node->GetQuickCheckDetails(details, compiler, filled_in, not_at_start);
 }
 
 
 int ChoiceNode::EatsAtLeastHelper(int still_to_find,
                                   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++) {
@@ skipping 52 matching lines @@
 }
 
 
 bool RegExpNode::EmitQuickCheck(RegExpCompiler* compiler,
                                 Trace* trace,
                                 bool preload_has_checked_bounds,
                                 Label* on_possible_success,
                                 QuickCheckDetails* details,
                                 bool fall_through_on_failure) {
   if (details->characters() == 0) return false;
-  GetQuickCheckDetails(details, compiler, 0);
+  GetQuickCheckDetails(details, compiler, 0, trace->at_start() == Trace::FALSE);
+  if (details->cannot_match()) return false;
   if (!details->Rationalize(compiler->ascii())) return false;
   uint32_t mask = details->mask();
   uint32_t value = details->value();
 
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
 
   if (trace->characters_preloaded() != details->characters()) {
     assembler->LoadCurrentCharacter(trace->cp_offset(),
                                     trace->backtrack(),
                                     !preload_has_checked_bounds,
@@ skipping 44 matching lines @@
 // Here is the meat of GetQuickCheckDetails (see also the comment on the
 // super-class in the .h file).
 //
 // We iterate along the text object, building up for each character a
 // mask and value that can be used to test for a quick failure to match.
 // The masks and values for the positions will be combined into a single
 // machine word for the current character width in order to be used in
 // generating a quick check.
 void TextNode::GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
-                                    int characters_filled_in) {
+                                    int characters_filled_in,
+                                    bool not_at_start) {
   ASSERT(characters_filled_in < details->characters());
   int characters = details->characters();
   int char_mask;
   int char_shift;
   if (compiler->ascii()) {
     char_mask = String::kMaxAsciiCharCode;
     char_shift = 8;
   } else {
     char_mask = String::kMaxUC16CharCode;
     char_shift = 16;
@@ skipping 91 matching lines @@
         pos->value = bits;
       }
       characters_filled_in++;
       ASSERT(characters_filled_in <= details->characters());
       if (characters_filled_in == details->characters()) {
         return;
       }
     }
   }
   ASSERT(characters_filled_in != details->characters());
-  on_success()-> GetQuickCheckDetails(details, compiler, characters_filled_in);
+  on_success()-> GetQuickCheckDetails(details,
+                                      compiler,
+                                      characters_filled_in,
+                                      true);
 }
 
 
 void QuickCheckDetails::Clear() {
   for (int i = 0; i < characters_; i++) {
     positions_[i].mask = 0;
     positions_[i].value = 0;
     positions_[i].determines_perfectly = false;
   }
   characters_ = 0;
@@ skipping 16 matching lines @@
   }
   characters_ -= by;
   // We could change mask_ and value_ here but we would never advance unless
   // they had already been used in a check and they won't be used again because
   // it would gain us nothing.  So there's no point.
 }
 
 
 void QuickCheckDetails::Merge(QuickCheckDetails* other, int from_index) {
   ASSERT(characters_ == other->characters_);
+  if (other->cannot_match_) {
+    return;
+  }
+  if (cannot_match_) {
+    *this = *other;
+    return;
+  }
   for (int i = from_index; i < characters_; i++) {
     QuickCheckDetails::Position* pos = positions(i);
     QuickCheckDetails::Position* other_pos = other->positions(i);
     if (pos->mask != other_pos->mask ||
         pos->value != other_pos->value ||
         !other_pos->determines_perfectly) {
       // Our mask-compare operation will be approximate unless we have the
       // exact same operation on both sides of the alternation.
       pos->determines_perfectly = false;
     }
@@ skipping 16 matching lines @@
   ~VisitMarker() {
     info_->visited = false;
   }
  private:
   NodeInfo* info_;
 };
 
 
 void LoopChoiceNode::GetQuickCheckDetails(QuickCheckDetails* details,
                                           RegExpCompiler* compiler,
-                                          int characters_filled_in) {
+                                          int characters_filled_in,
+                                          bool not_at_start) {
   if (body_can_be_zero_length_ || info()->visited) return;
   VisitMarker marker(info());
   return ChoiceNode::GetQuickCheckDetails(details,
                                           compiler,
-                                          characters_filled_in);
+                                          characters_filled_in,
+                                          not_at_start);
 }
 
 
 void ChoiceNode::GetQuickCheckDetails(QuickCheckDetails* details,
                                       RegExpCompiler* compiler,
-                                      int characters_filled_in) {
+                                      int characters_filled_in,
+                                      bool not_at_start) {
+  not_at_start = not_at_start || not_at_start_;
   int choice_count = alternatives_->length();
   ASSERT(choice_count > 0);
   alternatives_->at(0).node()->GetQuickCheckDetails(details,
                                                     compiler,
-                                                    characters_filled_in);
+                                                    characters_filled_in,
+                                                    not_at_start);
   for (int i = 1; i < choice_count; i++) {
     QuickCheckDetails new_details(details->characters());
     RegExpNode* node = alternatives_->at(i).node();
-    node->GetQuickCheckDetails(&new_details, compiler, characters_filled_in);
+    node->GetQuickCheckDetails(&new_details, compiler,
+                               characters_filled_in,
+                               not_at_start);
     // Here we merge the quick match details of the two branches.
     details->Merge(&new_details, characters_filled_in);
   }
 }
 
 
 // Check for [0-9A-Z_a-z].
 static void EmitWordCheck(RegExpMacroAssembler* assembler,
                           Label* word,
                           Label* non_word,
@@ skipping 105 matching lines @@
                                   false);
   bool fall_through_on_word = (type == AssertionNode::AT_NON_BOUNDARY);
   EmitWordCheck(assembler, not_boundary, boundary, fall_through_on_word);
 
   assembler->Bind(&ok);
 
   on_success->Emit(compiler, &new_trace);
 }
 
 
+void AssertionNode::GetQuickCheckDetails(QuickCheckDetails* details,
+                                         RegExpCompiler* compiler,
+                                         int filled_in,
+                                         bool not_at_start) {
+  if (type_ == AT_START && not_at_start) {
+    details->set_cannot_match();
+    return;
+  }
+  return on_success()->GetQuickCheckDetails(details,
+                                            compiler,
+                                            filled_in,
+                                            not_at_start);
+}
+
+
 void AssertionNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
   switch (type_) {
     case AT_END: {
       Label ok;
       assembler->CheckPosition(trace->cp_offset(), &ok);
       assembler->GoTo(trace->backtrack());
       assembler->Bind(&ok);
       break;
     }
-    case AT_START:
-      assembler->CheckNotAtStart(trace->backtrack());
-      break;
+    case AT_START: {
+      if (trace->at_start() == Trace::FALSE) {
+        assembler->GoTo(trace->backtrack());
+        return;
+      }
+      if (trace->at_start() == Trace::UNKNOWN) {
+        assembler->CheckNotAtStart(trace->backtrack());
+        Trace at_start_trace = *trace;
+        at_start_trace.set_at_start(true);
+        on_success()->Emit(compiler, &at_start_trace);
+        return;
+      }
+    }
+    break;
     case AFTER_NEWLINE:
       EmitHat(compiler, on_success(), trace);
       return;
     case AT_NON_BOUNDARY:
     case AT_BOUNDARY:
       EmitBoundaryCheck(type_, compiler, on_success(), trace);
       return;
   }
   on_success()->Emit(compiler, trace);
 }
@@ skipping 198 matching lines @@
                  &bound_checked_to);
   }
   TextEmitPass(compiler,
                CHARACTER_CLASS_MATCH,
                false,
                trace,
                first_elt_done,
                &bound_checked_to);
 
   Trace successor_trace(*trace);
+  successor_trace.set_at_start(false);
   successor_trace.AdvanceCurrentPositionInTrace(Length(), compiler);
   RecursionCheck rc(compiler);
   on_success()->Emit(compiler, &successor_trace);
 }
 
 
 void Trace::InvalidateCurrentCharacter() {
   characters_preloaded_ = 0;
 }
 
@@ skipping 273 matching lines @@
 
   RecursionCheck rc(compiler);
 
   Trace* current_trace = trace;
 
   int text_length = GreedyLoopTextLength(&(alternatives_->at(0)));
   bool greedy_loop = false;
   Label greedy_loop_label;
   Trace counter_backtrack_trace;
   counter_backtrack_trace.set_backtrack(&greedy_loop_label);
+  if (not_at_start()) counter_backtrack_trace.set_at_start(false);
+
   if (choice_count > 1 && text_length != kNodeIsTooComplexForGreedyLoops) {
     // Here we have special handling for greedy loops containing only text nodes
     // and other simple nodes.  These are handled by pushing the current
     // position on the stack and then incrementing the current position each
     // time around the switch.  On backtrack we decrement the current position
     // and check it against the pushed value.  This avoids pushing backtrack
     // information for each iteration of the loop, which could take up a lot of
     // space.
     greedy_loop = true;
     ASSERT(trace->stop_node() == NULL);
     macro_assembler->PushCurrentPosition();
     current_trace = &counter_backtrack_trace;
     Label greedy_match_failed;
     Trace greedy_match_trace;
+    if (not_at_start()) greedy_match_trace.set_at_start(false);
     greedy_match_trace.set_backtrack(&greedy_match_failed);
     Label loop_label;
     macro_assembler->Bind(&loop_label);
     greedy_match_trace.set_stop_node(this);
     greedy_match_trace.set_loop_label(&loop_label);
     alternatives_->at(0).node()->Emit(compiler, &greedy_match_trace);
     macro_assembler->Bind(&greedy_match_failed);
   }
 
   Label second_choice;  // For use in greedy matches.
@@ skipping 40 matching lines @@
       // On the last choice in the ChoiceNode we generated the quick
       // check to fall through on possible success.  So now we need to
       // generate the full check inline.
       if (i == choice_count - 1) {
         macro_assembler->Bind(&alt_gen->possible_success);
         new_trace.set_quick_check_performed(&alt_gen->quick_check_details);
         new_trace.set_characters_preloaded(preload_characters);
         new_trace.set_bound_checked_up_to(preload_characters);
         generate_full_check_inline = true;
       }
+    } else if (alt_gen->quick_check_details.cannot_match()) {
+      if (i == choice_count - 1 && !greedy_loop) {
+        macro_assembler->GoTo(trace->backtrack());
+      }
+      continue;
     } else {
       // No quick check was generated.  Put the full code here.
       // If this is not the first choice then there could be slow checks from
       // previous cases that go here when they fail.  There's no reason to
       // insist that they preload characters since the slow check we are about
       // to generate probably can't use it.
       if (i != first_normal_choice) {
         alt_gen->expects_preload = false;
         new_trace.set_characters_preloaded(0);
       }
@@ skipping 709 matching lines @@
                 compiler,
                 on_success);
 }
 
 
 RegExpNode* RegExpQuantifier::ToNode(int min,
                                      int max,
                                      bool is_greedy,
                                      RegExpTree* body,
                                      RegExpCompiler* compiler,
-                                     RegExpNode* on_success) {
+                                     RegExpNode* on_success,
+                                     bool not_at_start) {
   // x{f, t} becomes this:
   //
   //             (r++)<-.
   //               |     `
   //               |     (x)
   //               v     ^
   //      (r=0)-->(?)---/ [if r < t]
   //               |
   //   [if r >= f] \----> ...
   //
@@ skipping 18 matching lines @@
   Interval capture_registers = body->CaptureRegisters();
   bool needs_capture_clearing = !capture_registers.is_empty();
   if (body_can_be_empty) {
     body_start_reg = compiler->AllocateRegister();
   } else if (FLAG_irregexp_optimization && !needs_capture_clearing) {
     // Only unroll if there are no captures and the body can't be
     // empty.
     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);
+      RegExpNode* answer = ToNode(
+          0, new_max, is_greedy, body, compiler, on_success, true);
       // 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);
       }
       return answer;
     }
     if (max <= kMaxUnrolledMaxMatches) {
       ASSERT(min == 0);
       // Unroll the optional matches up to max.
       RegExpNode* answer = on_success;
       for (int i = 0; i < max; i++) {
         ChoiceNode* alternation = new ChoiceNode(2);
         if (is_greedy) {
           alternation->AddAlternative(GuardedAlternative(body->ToNode(compiler,
                                                                       answer)));
           alternation->AddAlternative(GuardedAlternative(on_success));
         } else {
           alternation->AddAlternative(GuardedAlternative(on_success));
           alternation->AddAlternative(GuardedAlternative(body->ToNode(compiler,
                                                                       answer)));
         }
         answer = alternation;
+        if (not_at_start) alternation->set_not_at_start();
       }
       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()
       : RegExpCompiler::kNoRegister;
   LoopChoiceNode* center = new LoopChoiceNode(body->min_match() == 0);
+  if (not_at_start) center->set_not_at_start();
   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);
@@ skipping 800 matching lines @@
   RegExpCompiler compiler(data->capture_count, ignore_case, is_ascii);
   // Wrap the body of the regexp in capture #0.
   RegExpNode* captured_body = RegExpCapture::ToNode(data->tree,
                                                     0,
                                                     &compiler,
                                                     compiler.accept());
   RegExpNode* node = captured_body;
   if (!data->tree->IsAnchored()) {
     // Add a .*? at the beginning, outside the body capture, unless
     // this expression is anchored at the beginning.
-    node = RegExpQuantifier::ToNode(0,
-                                    RegExpTree::kInfinity,
-                                    false,
-                                    new RegExpCharacterClass('*'),
-                                    &compiler,
-                                    captured_body);
+    RegExpNode* loop_node =
+        RegExpQuantifier::ToNode(0,
+                                 RegExpTree::kInfinity,
+                                 false,
+                                 new RegExpCharacterClass('*'),
+                                 &compiler,
+                                 captured_body,
+                                 data->contains_anchor);
+
+    if (data->contains_anchor) {
+      // Unroll once, and tell the loop that it's not at the start of the input.
+      ChoiceNode* first_step_node = new ChoiceNode(2);
+      first_step_node->AddAlternative(GuardedAlternative(captured_body));
+      first_step_node->AddAlternative(GuardedAlternative(
+          new TextNode(new RegExpCharacterClass('*'), loop_node)));
+      node = first_step_node;
+    } else {
+      node = loop_node;
+    }
   }
   data->node = node;
   Analysis analysis(ignore_case);
   analysis.EnsureAnalyzed(node);
 
   NodeInfo info = *node->info();
 
   if (FLAG_irregexp_native) {
 #ifdef ARM
     // Unimplemented, fall-through to bytecode implementation.
@@ skipping 15 matching lines @@
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal