* Irregexp: Handle backtrack past look-ahead.

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 1343 matching lines @@
       if (range.to() > max_register) max_register = range.to();
     } else {
       affected_registers->Set(action->reg());
       if (action->reg() > max_register) max_register = action->reg();
     }
   }
   return max_register;
 }
 
 
-void Trace::PushAffectedRegisters(RegExpMacroAssembler* assembler,
-                                  int max_register,
-                                  OutSet& affected_registers) {
-  // Stay safe and check every half times the limit.
-  // (Round up in case the limit is 1).
-  int push_limit = (assembler->stack_limit_slack() + 1) / 2;
-  for (int reg = 0, pushes = 0; reg <= max_register; reg++) {
-    if (affected_registers.Get(reg)) {
-      pushes++;
-      RegExpMacroAssembler::StackCheckFlag check_stack_limit =
-          (pushes % push_limit) == 0 ?
-                RegExpMacroAssembler::kCheckStackLimit :
-                RegExpMacroAssembler::kNoStackLimitCheck;
-      assembler->PushRegister(reg, check_stack_limit);
-    }
-  }
-}
-
-
 void Trace::RestoreAffectedRegisters(RegExpMacroAssembler* assembler,
                                      int max_register,
-                                     OutSet& affected_registers) {
+                                     OutSet& registers_to_pop,
+                                     OutSet& registers_to_clear) {
   for (int reg = max_register; reg >= 0; reg--) {
-    if (affected_registers.Get(reg)) assembler->PopRegister(reg);
+    if (registers_to_pop.Get(reg)) assembler->PopRegister(reg);
+    else if (registers_to_clear.Get(reg)) {
+      int clear_to = reg;
+      while (reg > 0 && registers_to_clear.Get(reg - 1)) {
+        reg--;
+      }
+      assembler->ClearRegisters(reg, clear_to);
+    }
   }
 }
 
 
 void Trace::PerformDeferredActions(RegExpMacroAssembler* assembler,
                                    int max_register,
-                                   OutSet& affected_registers) {
+                                   OutSet& affected_registers,
+                                   OutSet* registers_to_pop,
+                                   OutSet* registers_to_clear) {
+  // The "+1" is to avoid a push_limit of zero if stack_limit_slack() is 1.
+  const int push_limit = (assembler->stack_limit_slack() + 1) / 2;
+
   for (int reg = 0; reg <= max_register; reg++) {
     if (!affected_registers.Get(reg)) {
       continue;
     }
+    // Count pushes performed to force a stack limit check occasionally.
+    int pushes = 0;
+
+    // The chronologically first deferred action in the trace
+    // is used to infer the action needed to restore a register
+    // to its previous state (or not, if it's safe to ignore it).
+    enum DeferredActionUndoType { IGNORE, RESTORE, CLEAR };
+    DeferredActionUndoType undo_action = IGNORE;
+
     int value = 0;
     bool absolute = false;
     bool clear = false;
     int store_position = -1;
     // This is a little tricky because we are scanning the actions in reverse
     // historical order (newest first).
     for (DeferredAction* action = actions_;
          action != NULL;
          action = action->next()) {
       if (action->Mentions(reg)) {
         switch (action->type()) {
           case ActionNode::SET_REGISTER: {
             Trace::DeferredSetRegister* psr =
                 static_cast<Trace::DeferredSetRegister*>(action);
-            value += psr->value();
-            absolute = true;
+            if (!absolute) {
+              value += psr->value();
+              absolute = true;
+            }
+            // SET_REGISTER is currently only used for newly introduced loop
+            // counters. They can have a significant previous value if they
+            // occour in a loop. TODO(lrn): Propagate this information, so
+            // we can set undo_action to IGNORE if we know there is no value to
+            // restore.
+            undo_action = RESTORE;
             ASSERT_EQ(store_position, -1);
             ASSERT(!clear);
             break;
           }
           case ActionNode::INCREMENT_REGISTER:
             if (!absolute) {
               value++;
             }
             ASSERT_EQ(store_position, -1);
             ASSERT(!clear);
+            undo_action = RESTORE;
             break;
           case ActionNode::STORE_POSITION: {
             Trace::DeferredCapture* pc =
                 static_cast<Trace::DeferredCapture*>(action);
             if (!clear && store_position == -1) {
               store_position = pc->cp_offset();
             }
+
+            // For captures we know that stores and clears alternate.
+            // Other register, are never cleared, and if the occur
+            // inside a loop, they might be assigned more than once.
+            if (reg <= 1) {
+              // Registers zero and one, aka "capture zero", is
+              // always set correctly if we succeed. There is no
+              // need to undo a setting on backtrack, because we
+              // will set it again or fail.
+              undo_action = IGNORE;
+            } else {
+              undo_action = pc->is_capture() ? CLEAR : RESTORE;
+            }
             ASSERT(!absolute);
             ASSERT_EQ(value, 0);
             break;
           }
           case ActionNode::CLEAR_CAPTURES: {
             // Since we're scanning in reverse order, if we've already
             // set the position we have to ignore historically earlier
             // clearing operations.
-            if (store_position == -1)
+            if (store_position == -1) {
               clear = true;
+            }
+            undo_action = RESTORE;
             ASSERT(!absolute);
             ASSERT_EQ(value, 0);
             break;
           }
           default:
             UNREACHABLE();
             break;
         }
       }
     }
+    // Prepare for the undo-action (e.g., push if it's going to be popped).
+    if (undo_action == RESTORE) {
+      pushes++;
+      RegExpMacroAssembler::StackCheckFlag stack_check =
+          RegExpMacroAssembler::kNoStackLimitCheck;
+      if (pushes == push_limit) {
+        stack_check = RegExpMacroAssembler::kCheckStackLimit;
+        pushes = 0;
+      }
+
+      assembler->PushRegister(reg, stack_check);
+      registers_to_pop->Set(reg);
+    } else if (undo_action == CLEAR) {
+      registers_to_clear->Set(reg);
+    }
+    // Perform the chronologically last action (or accumulated increment)
+    // for the register.
     if (store_position != -1) {
       assembler->WriteCurrentPositionToRegister(reg, store_position);
     } else if (clear) {
-      assembler->ClearRegister(reg);
+      assembler->ClearRegisters(reg, reg);
     } else if (absolute) {
       assembler->SetRegister(reg, value);
     } else if (value != 0) {
       assembler->AdvanceRegister(reg, value);
     }
   }
 }
 
 
 // This is called as we come into a loop choice node and some other tricky
@@ skipping 14 matching lines @@
     // a normal situation.  We may also have to forget some information gained
     // through a quick check that was already performed.
     if (cp_offset_ != 0) assembler->AdvanceCurrentPosition(cp_offset_);
     // Create a new trivial state and generate the node with that.
     Trace new_state;
     return successor->Emit(compiler, &new_state);
   }
 
   // Generate deferred actions here along with code to undo them again.
   OutSet affected_registers;
+
   int max_register = FindAffectedRegisters(&affected_registers);
-  PushAffectedRegisters(assembler, max_register, affected_registers);
-  PerformDeferredActions(assembler, max_register, affected_registers);
+  OutSet registers_to_pop;
+  OutSet registers_to_clear;
+  PerformDeferredActions(assembler,
+                         max_register,
+                         affected_registers,
+                         &registers_to_pop,
+                         &registers_to_clear);
   if (backtrack() != NULL) {
     // Here we have a concrete backtrack location.  These are set up by choice
     // nodes and so they indicate that we have a deferred save of the current
     // position which we may need to emit here.
     assembler->PushCurrentPosition();
   }
   if (cp_offset_ != 0) {
     assembler->AdvanceCurrentPosition(cp_offset_);
   }
 
   // Create a new trivial state and generate the node with that.
   Label undo;
   assembler->PushBacktrack(&undo);
   Trace new_state;
   bool ok = successor->Emit(compiler, &new_state);
 
   // On backtrack we need to restore state.
   assembler->Bind(&undo);
   if (!ok) return false;
   if (backtrack() != NULL) {
     assembler->PopCurrentPosition();
   }
-  RestoreAffectedRegisters(assembler, max_register, affected_registers);
+  RestoreAffectedRegisters(assembler,
+                           max_register,
+                           registers_to_pop,
+                           registers_to_clear);
   if (backtrack() == NULL) {
     assembler->Backtrack();
   } else {
     assembler->GoTo(backtrack());
   }
 
   return true;
 }
 
 
 bool NegativeSubmatchSuccess::Emit(RegExpCompiler* compiler, Trace* trace) {
-  if (!trace->is_trivial()) {
-    return trace->Flush(compiler, this);
-  }
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
+
+  // Omit flushing the trace. We discard the entire stack frame anyway.
+
   if (!label()->is_bound()) {
+    // We are completely independent of the trace, since we ignore it,
+    // so this code can be used as the generic version.
     assembler->Bind(label());
   }
+
+  // Throw away everything on the backtrack stack since the start
+  // of the negative submatch and restore the character position.
   assembler->ReadCurrentPositionFromRegister(current_position_register_);
   assembler->ReadStackPointerFromRegister(stack_pointer_register_);
+  if (clear_capture_count_ > 0) {
+    // Clear any captures that might have been performed during the success
+    // of the body of the negative look-ahead.
+    int clear_capture_end = clear_capture_start_ + clear_capture_count_ - 1;
+    assembler->ClearRegisters(clear_capture_start_, clear_capture_end);
+  }
   // Now that we have unwound the stack we find at the top of the stack the
   // backtrack that the BeginSubmatch node got.
   assembler->Backtrack();
   return true;
 }
 
 
 bool EndNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   if (!trace->is_trivial()) {
     return trace->Flush(compiler, this);
@@ skipping 35 matching lines @@
 }
 
 
 ActionNode* ActionNode::IncrementRegister(int reg, RegExpNode* on_success) {
   ActionNode* result = new ActionNode(INCREMENT_REGISTER, on_success);
   result->data_.u_increment_register.reg = reg;
   return result;
 }
 
 
-ActionNode* ActionNode::StorePosition(int reg, RegExpNode* on_success) {
+ActionNode* ActionNode::StorePosition(int reg,
+                                      bool is_capture,
+                                      RegExpNode* on_success) {
   ActionNode* result = new ActionNode(STORE_POSITION, on_success);
   result->data_.u_position_register.reg = reg;
+  result->data_.u_position_register.is_capture = is_capture;
   return result;
 }
 
 
 ActionNode* ActionNode::ClearCaptures(Interval range,
                                       RegExpNode* on_success) {
   ActionNode* result = new ActionNode(CLEAR_CAPTURES, on_success);
   result->data_.u_clear_captures.range_from = range.from();
   result->data_.u_clear_captures.range_to = range.to();
   return result;
 }
 
 
 ActionNode* ActionNode::BeginSubmatch(int stack_reg,
                                       int position_reg,
                                       RegExpNode* on_success) {
   ActionNode* result = new ActionNode(BEGIN_SUBMATCH, on_success);
   result->data_.u_submatch.stack_pointer_register = stack_reg;
   result->data_.u_submatch.current_position_register = position_reg;
   return result;
 }
 
 
 ActionNode* ActionNode::PositiveSubmatchSuccess(int stack_reg,
                                                 int position_reg,
+                                                int clear_register_count,
+                                                int clear_register_from,
                                                 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;
+  result->data_.u_submatch.clear_register_count = clear_register_count;
+  result->data_.u_submatch.clear_register_from = clear_register_from;
   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;
@@ skipping 1531 matching lines @@
   LimitResult limit_result = LimitVersions(compiler, trace);
   if (limit_result == DONE) return true;
   if (limit_result == FAIL) return false;
   ASSERT(limit_result == CONTINUE);
 
   RecursionCheck rc(compiler);
 
   switch (type_) {
     case STORE_POSITION: {
       Trace::DeferredCapture
-          new_capture(data_.u_position_register.reg, trace);
+          new_capture(data_.u_position_register.reg,
+                      data_.u_position_register.is_capture,
+                      trace);
       Trace new_trace = *trace;
       new_trace.add_action(&new_capture);
       return on_success()->Emit(compiler, &new_trace);
     }
     case INCREMENT_REGISTER: {
       Trace::DeferredIncrementRegister
           new_increment(data_.u_increment_register.reg);
       Trace new_trace = *trace;
       new_trace.add_action(&new_increment);
       return on_success()->Emit(compiler, &new_trace);
@@ skipping 44 matching lines @@
         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,
                                  trace->backtrack());
       assembler->Bind(&skip_empty_check);
       return on_success()->Emit(compiler, trace);
     }
-    case POSITIVE_SUBMATCH_SUCCESS:
+    case POSITIVE_SUBMATCH_SUCCESS: {
       if (!trace->is_trivial()) return trace->Flush(compiler, this);
       assembler->ReadCurrentPositionFromRegister(
           data_.u_submatch.current_position_register);
       assembler->ReadStackPointerFromRegister(
           data_.u_submatch.stack_pointer_register);
-      return on_success()->Emit(compiler, trace);
+      int clear_register_count = data_.u_submatch.clear_register_count;
+      if (clear_register_count == 0) {
+        return on_success()->Emit(compiler, trace);
+      }
+      int clear_registers_from = data_.u_submatch.clear_register_from;
+      Label clear_registers_backtrack;
+      Trace new_trace = *trace;
+      new_trace.set_backtrack(&clear_registers_backtrack);
+      bool ok = on_success()->Emit(compiler, &new_trace);
+      if (!ok) { return false; }
+
+      assembler->Bind(&clear_registers_backtrack);
+      int clear_registers_to = clear_registers_from + clear_register_count - 1;
+      assembler->ClearRegisters(clear_registers_from, clear_registers_to);
+
+      ASSERT(trace->backtrack() == NULL);
+      assembler->Backtrack();
+      return true;
+    }
     default:
       UNREACHABLE();
       return false;
   }
 }
 
 
 bool BackReferenceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
   if (!trace->is_trivial()) {
@@ skipping 597 matching lines @@
     // 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);
+    body_node = ActionNode::StorePosition(body_start_reg, false, body_node);
   }
   if (needs_capture_clearing) {
     // Before entering the body of this loop we need to clear captures.
     body_node = ActionNode::ClearCaptures(capture_registers, 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);
   }
@@ skipping 41 matching lines @@
       ChoiceNode* result = new ChoiceNode(2);
       // Create a newline atom.
       ZoneList<CharacterRange>* newline_ranges =
           new ZoneList<CharacterRange>(3);
       CharacterRange::AddClassEscape('n', newline_ranges);
       RegExpCharacterClass* newline_atom = new RegExpCharacterClass('n');
       TextNode* newline_matcher = new TextNode(
          newline_atom,
          ActionNode::PositiveSubmatchSuccess(stack_pointer_register,
                                              position_register,
+                                             0,  // No captures inside.
+                                             -1,  // Ignored if no captures.
                                              on_success));
       // Create an end-of-input matcher.
       RegExpNode* end_of_line = ActionNode::BeginSubmatch(
           stack_pointer_register,
           position_register,
           newline_matcher);
       // Add the two alternatives to the ChoiceNode.
       GuardedAlternative eol_alternative(end_of_line);
       result->AddAlternative(eol_alternative);
       GuardedAlternative end_alternative(AssertionNode::AtEnd(on_success));
@@ skipping 18 matching lines @@
 RegExpNode* RegExpEmpty::ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success) {
   return on_success;
 }
 
 
 RegExpNode* RegExpLookahead::ToNode(RegExpCompiler* compiler,
                                     RegExpNode* on_success) {
   int stack_pointer_register = compiler->AllocateRegister();
   int position_register = compiler->AllocateRegister();
+
+  const int registers_per_capture = 2;
+  const int register_of_first_capture = 2;
+  int register_count = capture_count_ * registers_per_capture;
+  int register_start =
+    register_of_first_capture + capture_from_ * registers_per_capture;
+
   RegExpNode* success;
   if (is_positive()) {
-    return ActionNode::BeginSubmatch(
+    RegExpNode* node = ActionNode::BeginSubmatch(
         stack_pointer_register,
         position_register,
         body()->ToNode(
             compiler,
             ActionNode::PositiveSubmatchSuccess(stack_pointer_register,
                                                 position_register,
+                                                register_count,
+                                                register_start,
                                                 on_success)));
+    return node;
   } 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.  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)));
+                                                  position_register,
+                                                  register_count,
+                                                  register_start)));
     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);
 }
 
 
 RegExpNode* RegExpCapture::ToNode(RegExpTree* body,
                                   int index,
                                   RegExpCompiler* compiler,
                                   RegExpNode* on_success) {
   int start_reg = RegExpCapture::StartRegister(index);
   int end_reg = RegExpCapture::EndRegister(index);
-  RegExpNode* store_end = ActionNode::StorePosition(end_reg, on_success);
+  RegExpNode* store_end = ActionNode::StorePosition(end_reg, true, on_success);
   RegExpNode* body_node = body->ToNode(compiler, store_end);
-  return ActionNode::StorePosition(start_reg, body_node);
+  return ActionNode::StorePosition(start_reg, true, body_node);
 }
 
 
 RegExpNode* RegExpAlternative::ToNode(RegExpCompiler* compiler,
                                       RegExpNode* on_success) {
   ZoneList<RegExpTree*>* children = nodes();
   RegExpNode* current = on_success;
   for (int i = children->length() - 1; i >= 0; i--) {
     current = children->at(i)->ToNode(compiler, current);
   }
@@ skipping 658 matching lines @@
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal