Experimental: periodic merge of the bleeding_edge branch to the...

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 280 matching lines @@
 
 
 Handle<Object> RegExpImpl::Exec(Handle<JSRegExp> regexp,
                                 Handle<String> subject,
                                 Handle<Object> index) {
   switch (regexp->TypeTag()) {
     case JSRegExp::ATOM:
       return AtomExec(regexp, subject, index);
     case JSRegExp::IRREGEXP: {
       Handle<Object> result = IrregexpExec(regexp, subject, index);
-      if (!result.is_null() || Top::has_pending_exception()) {
-        return result;
-      }
-      // We couldn't handle the regexp using Irregexp, so fall back
-      // on JSCRE.
-      // Reset the JSRegExp to use JSCRE.
-      JscrePrepare(regexp,
-                   Handle<String>(regexp->Pattern()),
-                   regexp->GetFlags());
-      // Fall-through to JSCRE.
+      if (result.is_null()) ASSERT(Top::has_pending_exception());
+      return result;
     }
     case JSRegExp::JSCRE:
-      if (FLAG_disable_jscre) {
-        UNIMPLEMENTED();
-      }
       return JscreExec(regexp, subject, index);
     default:
       UNREACHABLE();
       return Handle<Object>::null();
   }
 }
 
 
 Handle<Object> RegExpImpl::ExecGlobal(Handle<JSRegExp> regexp,
                                 Handle<String> subject) {
   switch (regexp->TypeTag()) {
     case JSRegExp::ATOM:
       return AtomExecGlobal(regexp, subject);
     case JSRegExp::IRREGEXP: {
       Handle<Object> result = IrregexpExecGlobal(regexp, subject);
-      if (!result.is_null() || Top::has_pending_exception()) {
-        return result;
-      }
-      // Empty handle as result but no exception thrown means that
-      // the regexp contains features not yet handled by the irregexp
-      // compiler.
-      // We have to fall back on JSCRE. Reset the JSRegExp to use JSCRE.
-      JscrePrepare(regexp,
-                   Handle<String>(regexp->Pattern()),
-                   regexp->GetFlags());
-      // Fall-through to JSCRE.
+      if (result.is_null()) ASSERT(Top::has_pending_exception());
+      return result;
     }
     case JSRegExp::JSCRE:
-      if (FLAG_disable_jscre) {
-        UNIMPLEMENTED();
-      }
       return JscreExecGlobal(regexp, subject);
     default:
       UNREACHABLE();
       return Handle<Object>::null();
   }
 }
 
 
 // RegExp Atom implementation: Simple string search using indexOf.
 
@@ skipping 96 matching lines @@
   malloc_failure = Failure::Exception();
   *code = v8::jscre::jsRegExpCompile(pattern->GetTwoByteData(),
                                      pattern->length(),
                                      case_option,
                                      multiline_option,
                                      number_of_captures,
                                      error_message,
                                      &JSREMalloc,
                                      &JSREFree);
   if (*code == NULL && (malloc_failure->IsRetryAfterGC() ||
-                       malloc_failure->IsOutOfMemoryFailure())) {
+                        malloc_failure->IsOutOfMemoryFailure())) {
     return malloc_failure;
   } else {
     // It doesn't matter which object we return here, we just need to return
     // a non-failure to indicate to the GC-retry code that there was no
     // allocation failure.
     return pattern;
   }
 }
 
 
@@ skipping 216 matching lines @@
   }
 
   // Compile the RegExp.
   ZoneScope zone_scope(DELETE_ON_EXIT);
 
   JSRegExp::Flags flags = re->GetFlags();
 
   Handle<String> pattern(re->Pattern());
   StringShape shape(*pattern);
   if (!pattern->IsFlat(shape)) {
-    pattern->Flatten(shape);
+    FlattenString(pattern);
   }
 
   RegExpCompileData compile_data;
   FlatStringReader reader(pattern);
   if (!ParseRegExp(&reader, flags.is_multiline(), &compile_data)) {
     // Throw an exception if we fail to parse the pattern.
     // THIS SHOULD NOT HAPPEN. We already parsed it successfully once.
     ThrowRegExpException(re,
                          pattern,
                          compile_data.error,
@@ skipping 106 matching lines @@
   int number_of_registers = IrregexpNumberOfRegisters(irregexp);
   OffsetsVector offsets(number_of_registers);
 
   int previous_index = 0;
 
   Handle<JSArray> result = Factory::NewJSArray(0);
   int i = 0;
   Handle<Object> matches;
 
   if (!subject->IsFlat(shape)) {
-    subject->Flatten(shape);
+    FlattenString(subject);
   }
 
   while (true) {
     if (previous_index > subject->length() || previous_index < 0) {
       // Per ECMA-262 15.10.6.2, if the previous index is greater than the
       // string length, there is no match.
       matches = Factory::null_value();
       return result;
     } else {
 #ifdef DEBUG
@@ skipping 75 matching lines @@
           address = reinterpret_cast<const byte*>(ext->resource()->data());
         }
         res = RegExpMacroAssemblerIA32::Execute(
             *code,
             const_cast<Address*>(&address),
             start_offset << char_size_shift,
             end_offset << char_size_shift,
             offsets_vector,
             previous_index == 0);
       } else {  // Sequential string
+        ASSERT(StringShape(*subject).IsSequential());
         Address char_address =
             is_ascii ? SeqAsciiString::cast(*subject)->GetCharsAddress()
                      : SeqTwoByteString::cast(*subject)->GetCharsAddress();
         int byte_offset = char_address - reinterpret_cast<Address>(*subject);
         res = RegExpMacroAssemblerIA32::Execute(
             *code,
             reinterpret_cast<Address*>(subject.location()),
             byte_offset + (start_offset << char_size_shift),
             byte_offset + (end_offset << char_size_shift),
             offsets_vector,
@@ skipping 257 matching lines @@
     cons.BuildTable(this);
   }
   return table_;
 }
 
 
 class RegExpCompiler {
  public:
   RegExpCompiler(int capture_count, bool ignore_case, bool is_ascii);
 
-  int AllocateRegister() { return next_register_++; }
+  int AllocateRegister() {
+    if (next_register_ >= RegExpMacroAssembler::kMaxRegister) {
+      reg_exp_too_big_ = true;
+      return next_register_;
+    }
+    return next_register_++;
+  }
 
   Handle<FixedArray> Assemble(RegExpMacroAssembler* assembler,
                               RegExpNode* start,
                               int capture_count,
                               Handle<String> pattern);
 
   inline void AddWork(RegExpNode* node) { work_list_->Add(node); }
 
   static const int kImplementationOffset = 0;
   static const int kNumberOfRegistersOffset = 0;
   static const int kCodeOffset = 1;
 
   RegExpMacroAssembler* macro_assembler() { return macro_assembler_; }
   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_--; }
 
+  void SetRegExpTooBig() { reg_exp_too_big_ = true; }
+
   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_;
+  bool reg_exp_too_big_;
 };
 
 
 class RecursionCheck {
  public:
   explicit RecursionCheck(RegExpCompiler* compiler) : compiler_(compiler) {
     compiler->IncrementRecursionDepth();
   }
   ~RecursionCheck() { compiler_->DecrementRecursionDepth(); }
  private:
   RegExpCompiler* compiler_;
 };
 
 
+static Handle<FixedArray> IrregexpRegExpTooBig(Handle<String> pattern) {
+  Handle<JSArray> array = Factory::NewJSArray(2);
+  SetElement(array, 0, pattern);
+  const char* message = "RegExp too big";
+  SetElement(array, 1, Factory::NewStringFromUtf8(CStrVector(message)));
+  Handle<Object> regexp_err =
+      Factory::NewSyntaxError("malformed_regexp", array);
+  Top::Throw(*regexp_err);
+  return Handle<FixedArray>();
+}
+
+
 // Attempts to compile the regexp using an Irregexp code generator.  Returns
 // a fixed array or a null handle depending on whether it succeeded.
 RegExpCompiler::RegExpCompiler(int capture_count, bool ignore_case, bool ascii)
     : next_register_(2 * (capture_count + 1)),
       work_list_(NULL),
       recursion_depth_(0),
       ignore_case_(ignore_case),
-      ascii_(ascii) {
+      ascii_(ascii),
+      reg_exp_too_big_(false) {
   accept_ = new EndNode(EndNode::ACCEPT);
+  ASSERT(next_register_ - 1 <= RegExpMacroAssembler::kMaxRegister);
 }
 
 
 Handle<FixedArray> RegExpCompiler::Assemble(
     RegExpMacroAssembler* macro_assembler,
     RegExpNode* start,
     int capture_count,
     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);
   Trace new_trace;
-  if (!start->Emit(this, &new_trace)) {
-    fail.Unuse();
-    return Handle<FixedArray>::null();
-  }
+  start->Emit(this, &new_trace);
   macro_assembler_->Bind(&fail);
   macro_assembler_->Fail();
   while (!work_list.is_empty()) {
-    if (!work_list.RemoveLast()->Emit(this, &new_trace)) {
-      return Handle<FixedArray>::null();
-    }
+    work_list.RemoveLast()->Emit(this, &new_trace);
   }
+  if (reg_exp_too_big_) return IrregexpRegExpTooBig(pattern);
   Handle<FixedArray> array =
       Factory::NewFixedArray(RegExpImpl::kIrregexpDataLength);
   array->set(RegExpImpl::kIrregexpImplementationIndex,
              Smi::FromInt(macro_assembler_->Implementation()));
   array->set(RegExpImpl::kIrregexpNumberOfRegistersIndex,
              Smi::FromInt(next_register_));
   array->set(RegExpImpl::kIrregexpNumberOfCapturesIndex,
              Smi::FromInt(capture_count));
   Handle<Object> code = macro_assembler_->GetCode(pattern);
   array->set(RegExpImpl::kIrregexpCodeIndex, *code);
   work_list_ = NULL;
 #ifdef DEBUG
   if (FLAG_trace_regexp_assembler) {
     delete macro_assembler_;
   }
 #endif
   return array;
 }
 
+
 bool Trace::DeferredAction::Mentions(int that) {
   if (type() == ActionNode::CLEAR_CAPTURES) {
     Interval range = static_cast<DeferredClearCaptures*>(this)->range();
     return range.Contains(that);
   } else {
     return reg() == that;
   }
 }
 
 
@@ skipping 38 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
-// nodes.  It normalises the state of the code generator to ensure we can
+// nodes.  It normalizes the state of the code generator to ensure we can
 // generate generic code.
-bool Trace::Flush(RegExpCompiler* compiler, RegExpNode* successor) {
+void Trace::Flush(RegExpCompiler* compiler, RegExpNode* successor) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
 
   ASSERT(actions_ != NULL ||
          cp_offset_ != 0 ||
          backtrack() != NULL ||
          characters_preloaded_ != 0 ||
          quick_check_performed_.characters() != 0 ||
          bound_checked_up_to_ != 0);
 
   if (actions_ == NULL && backtrack() == NULL) {
     // Here we just have some deferred cp advances to fix and we are back to
     // 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);
+    successor->Emit(compiler, &new_state);
+    return;
   }
 
   // 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);
+  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;
 }
 
 
-void EndNode::EmitInfoChecks(RegExpMacroAssembler* assembler, Trace* trace) {
-  if (info()->at_end) {
-    Label succeed;
-    // LoadCurrentCharacter will go to the label if we are at the end of the
-    // input string.
-    assembler->LoadCurrentCharacter(0, &succeed);
-    assembler->GoTo(trace->backtrack());
-    assembler->Bind(&succeed);
+void NegativeSubmatchSuccess::Emit(RegExpCompiler* compiler, Trace* trace) {
+  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();
 }
 
 
-bool NegativeSubmatchSuccess::Emit(RegExpCompiler* compiler, Trace* trace) {
+void EndNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   if (!trace->is_trivial()) {
-    return trace->Flush(compiler, this);
+    trace->Flush(compiler, this);
+    return;
   }
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
   if (!label()->is_bound()) {
-    assembler->Bind(label());
-  }
-  EmitInfoChecks(assembler, trace);
-  assembler->ReadCurrentPositionFromRegister(current_position_register_);
-  assembler->ReadStackPointerFromRegister(stack_pointer_register_);
-  // 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);
-  }
-  RegExpMacroAssembler* assembler = compiler->macro_assembler();
-  if (!label()->is_bound()) {
     assembler->Bind(label());
   }
   switch (action_) {
     case ACCEPT:
-      EmitInfoChecks(assembler, trace);
       assembler->Succeed();
-      return true;
+      return;
     case BACKTRACK:
-      ASSERT(!info()->at_end);
       assembler->GoTo(trace->backtrack());
-      return true;
+      return;
     case NEGATIVE_SUBMATCH_SUCCESS:
       // This case is handled in a different virtual method.
       UNREACHABLE();
   }
   UNIMPLEMENTED();
-  return false;
 }
 
 
 void GuardedAlternative::AddGuard(Guard* guard) {
   if (guards_ == NULL)
     guards_ = new ZoneList<Guard*>(1);
   guards_->Add(guard);
 }
 
 
 ActionNode* ActionNode::SetRegister(int reg,
                                     int val,
                                     RegExpNode* on_success) {
   ActionNode* result = new ActionNode(SET_REGISTER, on_success);
   result->data_.u_store_register.reg = reg;
   result->data_.u_store_register.value = val;
   return result;
 }
 
 
 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 195 matching lines @@
     }
     last_valid_range--;
   }
 
   if (last_valid_range < 0) {
     if (!cc->is_negated()) {
       // TODO(plesner): We can remove this when the node level does our
       // ASCII optimizations for us.
       macro_assembler->GoTo(on_failure);
     }
+    if (check_offset) {
+      macro_assembler->CheckPosition(cp_offset, on_failure);
+    }
     return;
   }
 
   if (last_valid_range == 0 &&
       !cc->is_negated() &&
       ranges->at(0).IsEverything(max_char)) {
     // This is a common case hit by non-anchored expressions.
-    // TODO(erikcorry): We should have a macro assembler instruction that just
-    // checks for end of string without loading the character.
     if (check_offset) {
-      macro_assembler->LoadCurrentCharacter(cp_offset, on_failure);
+      macro_assembler->CheckPosition(cp_offset, on_failure);
     }
     return;
   }
 
   if (!preloaded) {
     macro_assembler->LoadCurrentCharacter(cp_offset, on_failure, check_offset);
   }
 
   for (int i = 0; i < last_valid_range; i++) {
     CharacterRange& range = ranges->at(i);
@@ skipping 55 matching lines @@
   macro_assembler->Bind(&success);
 }
 
 
 RegExpNode::~RegExpNode() {
 }
 
 
 RegExpNode::LimitResult RegExpNode::LimitVersions(RegExpCompiler* compiler,
                                                   Trace* trace) {
-  // TODO(erikcorry): Implement support.
-  if (info_.follows_word_interest ||
-      info_.follows_newline_interest ||
-      info_.follows_start_interest) {
-    return FAIL;
-  }
-
   // If we are generating a greedy loop then don't stop and don't reuse code.
   if (trace->stop_node() != NULL) {
     return CONTINUE;
   }
 
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   if (trace->is_trivial()) {
     if (label_.is_bound()) {
       // We are being asked to generate a generic version, but that's already
       // been done so just go to it.
@@ skipping 16 matching lines @@
   // non-generic versions we generate so as not to overdo it.
   trace_count_++;
   if (trace_count_ < kMaxCopiesCodeGenerated &&
       compiler->recursion_depth() <= RegExpCompiler::kMaxRecursion) {
     return CONTINUE;
   }
 
   // If we get here code has been generated for this node too many times or
   // recursion is too deep.  Time to switch to a generic version.  The code for
   // generic versions above can handle deep recursion properly.
-  bool ok = trace->Flush(compiler, this);
-  return ok ? DONE : FAIL;
+  trace->Flush(compiler, this);
+  return DONE;
 }
 
 
-int ActionNode::EatsAtLeast(int recursion_depth) {
+int ActionNode::EatsAtLeast(int still_to_find, int recursion_depth) {
   if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
   if (type_ == POSITIVE_SUBMATCH_SUCCESS) return 0;  // Rewinds input!
-  return on_success()->EatsAtLeast(recursion_depth + 1);
+  return on_success()->EatsAtLeast(still_to_find, 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 AssertionNode::EatsAtLeast(int still_to_find, int recursion_depth) {
+  if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
+  return on_success()->EatsAtLeast(still_to_find, recursion_depth + 1);
 }
 
 
-int ChoiceNode::EatsAtLeastHelper(int recursion_depth,
+int BackReferenceNode::EatsAtLeast(int still_to_find, int recursion_depth) {
+  if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
+  return on_success()->EatsAtLeast(still_to_find, recursion_depth + 1);
+}
+
+
+int TextNode::EatsAtLeast(int still_to_find, int recursion_depth) {
+  int answer = Length();
+  if (answer >= still_to_find) return answer;
+  if (recursion_depth > RegExpCompiler::kMaxRecursion) return answer;
+  return answer + on_success()->EatsAtLeast(still_to_find - answer,
+                                            recursion_depth + 1);
+}
+
+
+int NegativeLookaheadChoiceNode:: EatsAtLeast(int still_to_find,
+                                              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(still_to_find, 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 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++) {
     RegExpNode* node = alternatives_->at(i).node();
     if (node == ignore_this_node) continue;
-    int node_eats_at_least = node->EatsAtLeast(recursion_depth + 1);
+    int node_eats_at_least = node->EatsAtLeast(still_to_find,
+                                               recursion_depth + 1);
     if (node_eats_at_least < min) min = node_eats_at_least;
   }
   return min;
 }
 
 
-int LoopChoiceNode::EatsAtLeast(int recursion_depth) {
-  return EatsAtLeastHelper(recursion_depth, loop_node_);
+int LoopChoiceNode::EatsAtLeast(int still_to_find, int recursion_depth) {
+  return EatsAtLeastHelper(still_to_find, recursion_depth, loop_node_);
 }
 
 
-int ChoiceNode::EatsAtLeast(int recursion_depth) {
-  return EatsAtLeastHelper(recursion_depth, NULL);
+int ChoiceNode::EatsAtLeast(int still_to_find, int recursion_depth) {
+  return EatsAtLeastHelper(still_to_find, recursion_depth, NULL);
 }
 
 
 // Takes the left-most 1-bit and smears it out, setting all bits to its right.
 static inline uint32_t SmearBitsRight(uint32_t v) {
   v |= v >> 1;
   v |= v >> 2;
   v |= v >> 4;
   v |= v >> 8;
   v |= v >> 16;
@@ skipping 217 matching lines @@
   for (int i = 0; i < characters_; i++) {
     positions_[i].mask = 0;
     positions_[i].value = 0;
     positions_[i].determines_perfectly = false;
   }
   characters_ = 0;
 }
 
 
 void QuickCheckDetails::Advance(int by, bool ascii) {
-  ASSERT(by > 0);
+  ASSERT(by >= 0);
   if (by >= characters_) {
     Clear();
     return;
   }
   for (int i = 0; i < characters_ - by; i++) {
     positions_[i] = positions_[by + i];
   }
   for (int i = characters_ - by; i < characters_; i++) {
     positions_[i].mask = 0;
     positions_[i].value = 0;
@@ skipping 64 matching lines @@
   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);
     // 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,
+                          bool fall_through_on_word) {
+  assembler->CheckCharacterGT('z', non_word);
+  assembler->CheckCharacterLT('0', non_word);
+  assembler->CheckCharacterGT('a' - 1, word);
+  assembler->CheckCharacterLT('9' + 1, word);
+  assembler->CheckCharacterLT('A', non_word);
+  assembler->CheckCharacterLT('Z' + 1, word);
+  if (fall_through_on_word) {
+    assembler->CheckNotCharacter('_', non_word);
+  } else {
+    assembler->CheckCharacter('_', word);
+  }
+}
+
+
+// Emit the code to check for a ^ in multiline mode (1-character lookbehind
+// that matches newline or the start of input).
+static void EmitHat(RegExpCompiler* compiler,
+                    RegExpNode* on_success,
+                    Trace* trace) {
+  RegExpMacroAssembler* assembler = compiler->macro_assembler();
+  // We will be loading the previous character into the current character
+  // register.
+  Trace new_trace(*trace);
+  new_trace.InvalidateCurrentCharacter();
+
+  Label ok;
+  if (new_trace.cp_offset() == 0) {
+    // The start of input counts as a newline in this context, so skip to
+    // ok if we are at the start.
+    assembler->CheckAtStart(&ok);
+  }
+  // We already checked that we are not at the start of input so it must be
+  // OK to load the previous character.
+  assembler->LoadCurrentCharacter(new_trace.cp_offset() -1,
+                                  new_trace.backtrack(),
+                                  false);
+  // Newline means \n, \r, 0x2028 or 0x2029.
+  if (!compiler->ascii()) {
+    assembler->CheckCharacterAfterAnd(0x2028, 0xfffe, &ok);
+  }
+  assembler->CheckCharacter('\n', &ok);
+  assembler->CheckNotCharacter('\r', new_trace.backtrack());
+  assembler->Bind(&ok);
+  on_success->Emit(compiler, &new_trace);
+}
+
+
+// Emit the code to handle \b and \B (word-boundary or non-word-boundary).
+static void EmitBoundaryCheck(AssertionNode::AssertionNodeType type,
+                              RegExpCompiler* compiler,
+                              RegExpNode* on_success,
+                              Trace* trace) {
+  RegExpMacroAssembler* assembler = compiler->macro_assembler();
+  Label before_non_word;
+  Label before_word;
+  if (trace->characters_preloaded() != 1) {
+    assembler->LoadCurrentCharacter(trace->cp_offset(), &before_non_word);
+  }
+  // Fall through on non-word.
+  EmitWordCheck(assembler, &before_word, &before_non_word, false);
+
+  // We will be loading the previous character into the current character
+  // register.
+  Trace new_trace(*trace);
+  new_trace.InvalidateCurrentCharacter();
+
+  Label ok;
+  Label* boundary;
+  Label* not_boundary;
+  if (type == AssertionNode::AT_BOUNDARY) {
+    boundary = &ok;
+    not_boundary = new_trace.backtrack();
+  } else {
+    not_boundary = &ok;
+    boundary = new_trace.backtrack();
+  }
+
+  // Next character is not a word character.
+  assembler->Bind(&before_non_word);
+  if (new_trace.cp_offset() == 0) {
+    // The start of input counts as a non-word character, so the question is
+    // decided if we are at the start.
+    assembler->CheckAtStart(not_boundary);
+  }
+  // We already checked that we are not at the start of input so it must be
+  // OK to load the previous character.
+  assembler->LoadCurrentCharacter(new_trace.cp_offset() - 1,
+                                  &ok,  // Unused dummy label in this call.
+                                  false);
+  // Fall through on non-word.
+  EmitWordCheck(assembler, boundary, not_boundary, false);
+  assembler->GoTo(not_boundary);
+
+  // Next character is a word character.
+  assembler->Bind(&before_word);
+  if (new_trace.cp_offset() == 0) {
+    // The start of input counts as a non-word character, so the question is
+    // decided if we are at the start.
+    assembler->CheckAtStart(boundary);
+  }
+  // We already checked that we are not at the start of input so it must be
+  // OK to load the previous character.
+  assembler->LoadCurrentCharacter(new_trace.cp_offset() - 1,
+                                  &ok,  // Unused dummy label in this call.
+                                  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::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 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);
+}
+
+
 // We call this repeatedly to generate code for each pass over the text node.
 // The passes are in increasing order of difficulty because we hope one
 // of the first passes will fail in which case we are saved the work of the
 // later passes.  for example for the case independent regexp /%[asdfghjkl]a/
 // we will check the '%' in the first pass, the case independent 'a' in the
 // second pass and the character class in the last pass.
 //
 // The passes are done from right to left, so for example to test for /bar/
 // we will first test for an 'r' with offset 2, then an 'a' with offset 1
 // and then a 'b' with offset 0.  This means we can avoid the end-of-input
@@ skipping 119 matching lines @@
   }
 }
 
 
 // This generates the code to match a text node.  A text node can contain
 // straight character sequences (possibly to be matched in a case-independent
 // way) and character classes.  For efficiency we do not do this in a single
 // pass from left to right.  Instead we pass over the text node several times,
 // emitting code for some character positions every time.  See the comment on
 // TextEmitPass for details.
-bool TextNode::Emit(RegExpCompiler* compiler, Trace* trace) {
+void TextNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   LimitResult limit_result = LimitVersions(compiler, trace);
-  if (limit_result == FAIL) return false;
-  if (limit_result == DONE) return true;
+  if (limit_result == DONE) return;
   ASSERT(limit_result == CONTINUE);
 
-  if (info()->follows_word_interest ||
-      info()->follows_newline_interest ||
-      info()->follows_start_interest) {
-    return false;
-  }
-
-  if (info()->at_end) {
-    compiler->macro_assembler()->GoTo(trace->backtrack());
-    return true;
+  if (trace->cp_offset() + Length() > RegExpMacroAssembler::kMaxCPOffset) {
+    compiler->SetRegExpTooBig();
+    return;
   }
 
   if (compiler->ascii()) {
     int dummy = 0;
     TextEmitPass(compiler, NON_ASCII_MATCH, false, trace, false, &dummy);
   }
 
   bool first_elt_done = false;
   int bound_checked_to = trace->cp_offset() - 1;
   bound_checked_to += trace->bound_checked_up_to();
@@ skipping 39 matching lines @@
                  &bound_checked_to);
   }
   TextEmitPass(compiler,
                CHARACTER_CLASS_MATCH,
                false,
                trace,
                first_elt_done,
                &bound_checked_to);
 
   Trace successor_trace(*trace);
-  successor_trace.AdvanceCurrentPositionInTrace(Length(), compiler->ascii());
+  successor_trace.AdvanceCurrentPositionInTrace(Length(), compiler);
   RecursionCheck rc(compiler);
-  return on_success()->Emit(compiler, &successor_trace);
+  on_success()->Emit(compiler, &successor_trace);
 }
 
 
-void Trace::AdvanceCurrentPositionInTrace(int by, bool ascii) {
+void Trace::InvalidateCurrentCharacter() {
+  characters_preloaded_ = 0;
+}
+
+
+void Trace::AdvanceCurrentPositionInTrace(int by, RegExpCompiler* compiler) {
   ASSERT(by > 0);
   // We don't have an instruction for shifting the current character register
   // down or for using a shifted value for anything so lets just forget that
   // we preloaded any characters into it.
   characters_preloaded_ = 0;
   // Adjust the offsets of the quick check performed information.  This
   // information is used to find out what we already determined about the
   // characters by means of mask and compare.
-  quick_check_performed_.Advance(by, ascii);
+  quick_check_performed_.Advance(by, compiler->ascii());
   cp_offset_ += by;
+  if (cp_offset_ > RegExpMacroAssembler::kMaxCPOffset) {
+    compiler->SetRegExpTooBig();
+    cp_offset_ = 0;
+  }
   bound_checked_up_to_ = Max(0, bound_checked_up_to_ - by);
 }
 
 
 void TextNode::MakeCaseIndependent() {
   int element_count = elms_->length();
   for (int i = 0; i < element_count; i++) {
     TextElement elm = elms_->at(i);
     if (elm.type == TextElement::CHAR_CLASS) {
       RegExpCharacterClass* cc = elm.data.u_char_class;
@@ skipping 24 matching lines @@
 int ChoiceNode::GreedyLoopTextLength(GuardedAlternative* alternative) {
   int length = 0;
   RegExpNode* node = alternative->node();
   // Later we will generate code for all these text nodes using recursion
   // so we have to limit the max number.
   int recursion_depth = 0;
   while (node != this) {
     if (recursion_depth++ > RegExpCompiler::kMaxRecursion) {
       return kNodeIsTooComplexForGreedyLoops;
     }
-    NodeInfo* info = node->info();
-    if (info->follows_word_interest ||
-        info->follows_newline_interest ||
-        info->follows_start_interest) {
-      return kNodeIsTooComplexForGreedyLoops;
-    }
     int node_length = node->GreedyLoopTextLength();
     if (node_length == kNodeIsTooComplexForGreedyLoops) {
       return kNodeIsTooComplexForGreedyLoops;
     }
     length += node_length;
     SeqRegExpNode* seq_node = static_cast<SeqRegExpNode*>(node);
     node = seq_node->on_success();
   }
   return length;
 }
 
 
 void LoopChoiceNode::AddLoopAlternative(GuardedAlternative alt) {
   ASSERT_EQ(loop_node_, NULL);
   AddAlternative(alt);
   loop_node_ = alt.node();
 }
 
 
 void LoopChoiceNode::AddContinueAlternative(GuardedAlternative alt) {
   ASSERT_EQ(continue_node_, NULL);
   AddAlternative(alt);
   continue_node_ = alt.node();
 }
 
 
-bool LoopChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
+void LoopChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   if (trace->stop_node() == this) {
     int text_length = GreedyLoopTextLength(&(alternatives_->at(0)));
     ASSERT(text_length != kNodeIsTooComplexForGreedyLoops);
     // Update the counter-based backtracking info on the stack.  This is an
     // optimization for greedy loops (see below).
     ASSERT(trace->cp_offset() == text_length);
     macro_assembler->AdvanceCurrentPosition(text_length);
     macro_assembler->GoTo(trace->loop_label());
-    return true;
+    return;
   }
   ASSERT(trace->stop_node() == NULL);
   if (!trace->is_trivial()) {
-    return trace->Flush(compiler, this);
+    trace->Flush(compiler, this);
+    return;
   }
-  return ChoiceNode::Emit(compiler, trace);
+  ChoiceNode::Emit(compiler, trace);
 }
 
 
 int ChoiceNode::CalculatePreloadCharacters(RegExpCompiler* compiler) {
-  int preload_characters = EatsAtLeast(0);
+  int preload_characters = EatsAtLeast(4, 0);
 #ifdef CAN_READ_UNALIGNED
   bool ascii = compiler->ascii();
   if (ascii) {
     if (preload_characters > 4) preload_characters = 4;
     // We can't preload 3 characters because there is no machine instruction
     // to do that.  We can't just load 4 because we could be reading
     // beyond the end of the string, which could cause a memory fault.
     if (preload_characters == 3) preload_characters = 2;
   } else {
     if (preload_characters > 2) preload_characters = 2;
@@ skipping 127 matching lines @@
  *        |   /          |
  *        |  R           |
  *        | /            |
  *   F    VL             |
  * <------U              |
  * back   |S             |
  *        \______________/
  */
 
 
-bool ChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
+void ChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   int choice_count = alternatives_->length();
 #ifdef DEBUG
   for (int i = 0; i < choice_count - 1; i++) {
     GuardedAlternative alternative = alternatives_->at(i);
     ZoneList<Guard*>* guards = alternative.guards();
     int guard_count = (guards == NULL) ? 0 : guards->length();
     for (int j = 0; j < guard_count; j++) {
       ASSERT(!trace->mentions_reg(guards->at(j)->reg()));
     }
   }
 #endif
 
   LimitResult limit_result = LimitVersions(compiler, trace);
-  if (limit_result == DONE) return true;
-  if (limit_result == FAIL) return false;
+  if (limit_result == DONE) return;
   ASSERT(limit_result == CONTINUE);
 
   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;
@@ skipping 10 matching lines @@
     ASSERT(trace->stop_node() == NULL);
     macro_assembler->PushCurrentPosition();
     current_trace = &counter_backtrack_trace;
     Label greedy_match_failed;
     Trace greedy_match_trace;
     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);
-    bool ok = alternatives_->at(0).node()->Emit(compiler,
-                                                &greedy_match_trace);
+    alternatives_->at(0).node()->Emit(compiler, &greedy_match_trace);
     macro_assembler->Bind(&greedy_match_failed);
-    if (!ok) {
-      greedy_loop_label.Unuse();
-      return false;
-    }
   }
 
   Label second_choice;  // For use in greedy matches.
   macro_assembler->Bind(&second_choice);
 
   int first_normal_choice = greedy_loop ? 1 : 0;
 
   int preload_characters = CalculatePreloadCharacters(compiler);
   bool preload_is_current =
       (current_trace->characters_preloaded() == preload_characters);
@@ skipping 12 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 17 matching lines @@
       }
       if (i < choice_count - 1) {
         new_trace.set_backtrack(&alt_gen->after);
       }
       generate_full_check_inline = true;
     }
     if (generate_full_check_inline) {
       for (int j = 0; j < guard_count; j++) {
         GenerateGuard(macro_assembler, guards->at(j), &new_trace);
       }
-      if (!alternative.node()->Emit(compiler, &new_trace)) {
-        greedy_loop_label.Unuse();
-        return false;
-      }
+      alternative.node()->Emit(compiler, &new_trace);
       preload_is_current = false;
     }
     macro_assembler->Bind(&alt_gen->after);
   }
   if (greedy_loop) {
     macro_assembler->Bind(&greedy_loop_label);
     // If we have unwound to the bottom then backtrack.
     macro_assembler->CheckGreedyLoop(trace->backtrack());
     // Otherwise try the second priority at an earlier position.
     macro_assembler->AdvanceCurrentPosition(-text_length);
     macro_assembler->GoTo(&second_choice);
   }
   // At this point we need to generate slow checks for the alternatives where
   // the quick check was inlined.  We can recognize these because the associated
   // label was bound.
   for (int i = first_normal_choice; i < choice_count - 1; i++) {
     AlternativeGeneration* alt_gen = alt_gens.at(i);
-    if (!EmitOutOfLineContinuation(compiler,
-                                   current_trace,
-                                   alternatives_->at(i),
-                                   alt_gen,
-                                   preload_characters,
-                                   alt_gens.at(i + 1)->expects_preload)) {
-      return false;
-    }
+    EmitOutOfLineContinuation(compiler,
+                              current_trace,
+                              alternatives_->at(i),
+                              alt_gen,
+                              preload_characters,
+                              alt_gens.at(i + 1)->expects_preload);
   }
-  return true;
 }
 
 
-bool ChoiceNode::EmitOutOfLineContinuation(RegExpCompiler* compiler,
+void ChoiceNode::EmitOutOfLineContinuation(RegExpCompiler* compiler,
                                            Trace* trace,
                                            GuardedAlternative alternative,
                                            AlternativeGeneration* alt_gen,
                                            int preload_characters,
                                            bool next_expects_preload) {
-  if (!alt_gen->possible_success.is_linked()) return true;
+  if (!alt_gen->possible_success.is_linked()) return;
 
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   macro_assembler->Bind(&alt_gen->possible_success);
   Trace out_of_line_trace(*trace);
   out_of_line_trace.set_characters_preloaded(preload_characters);
   out_of_line_trace.set_quick_check_performed(&alt_gen->quick_check_details);
   ZoneList<Guard*>* guards = alternative.guards();
   int guard_count = (guards == NULL) ? 0 : guards->length();
   if (next_expects_preload) {
     Label reload_current_char;
     out_of_line_trace.set_backtrack(&reload_current_char);
     for (int j = 0; j < guard_count; j++) {
       GenerateGuard(macro_assembler, guards->at(j), &out_of_line_trace);
     }
-    bool ok = alternative.node()->Emit(compiler, &out_of_line_trace);
+    alternative.node()->Emit(compiler, &out_of_line_trace);
     macro_assembler->Bind(&reload_current_char);
     // Reload the current character, since the next quick check expects that.
     // We don't need to check bounds here because we only get into this
     // code through a quick check which already did the checked load.
     macro_assembler->LoadCurrentCharacter(trace->cp_offset(),
                                           NULL,
                                           false,
                                           preload_characters);
     macro_assembler->GoTo(&(alt_gen->after));
-    return ok;
   } else {
     out_of_line_trace.set_backtrack(&(alt_gen->after));
     for (int j = 0; j < guard_count; j++) {
       GenerateGuard(macro_assembler, guards->at(j), &out_of_line_trace);
     }
-    return alternative.node()->Emit(compiler, &out_of_line_trace);
+    alternative.node()->Emit(compiler, &out_of_line_trace);
   }
 }
 
 
-bool ActionNode::Emit(RegExpCompiler* compiler, Trace* trace) {
+void ActionNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
   LimitResult limit_result = LimitVersions(compiler, trace);
-  if (limit_result == DONE) return true;
-  if (limit_result == FAIL) return false;
+  if (limit_result == DONE) return;
   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);
+      on_success()->Emit(compiler, &new_trace);
+      break;
     }
     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);
+      on_success()->Emit(compiler, &new_trace);
+      break;
     }
     case SET_REGISTER: {
       Trace::DeferredSetRegister
           new_set(data_.u_store_register.reg, data_.u_store_register.value);
       Trace new_trace = *trace;
       new_trace.add_action(&new_set);
-      return on_success()->Emit(compiler, &new_trace);
+      on_success()->Emit(compiler, &new_trace);
+      break;
     }
     case CLEAR_CAPTURES: {
       Trace::DeferredClearCaptures
         new_capture(Interval(data_.u_clear_captures.range_from,
                              data_.u_clear_captures.range_to));
       Trace new_trace = *trace;
       new_trace.add_action(&new_capture);
-      return on_success()->Emit(compiler, &new_trace);
+      on_success()->Emit(compiler, &new_trace);
+      break;
     }
     case BEGIN_SUBMATCH:
-      if (!trace->is_trivial()) return trace->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, trace);
+      if (!trace->is_trivial()) {
+        trace->Flush(compiler, this);
+      } else {
+        assembler->WriteCurrentPositionToRegister(
+            data_.u_submatch.current_position_register, 0);
+        assembler->WriteStackPointerToRegister(
+            data_.u_submatch.stack_pointer_register);
+        on_success()->Emit(compiler, trace);
+      }
+      break;
     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);
       bool know_dist = trace->GetStoredPosition(start_pos_reg, &stored_pos);
       if (know_dist && !has_minimum && stored_pos == trace->cp_offset()) {
         // If we know we haven't advanced and there is no minimum we
         // can just backtrack immediately.
         assembler->GoTo(trace->backtrack());
-        return true;
       } else if (know_dist && stored_pos < trace->cp_offset()) {
         // If we know we've advanced we can generate the continuation
         // immediately.
-        return on_success()->Emit(compiler, trace);
+        on_success()->Emit(compiler, trace);
+      } else if (!trace->is_trivial()) {
+        trace->Flush(compiler, this);
+      } else {
+        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.
+        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,
+                                   trace->backtrack());
+        assembler->Bind(&skip_empty_check);
+        on_success()->Emit(compiler, trace);
       }
-      if (!trace->is_trivial()) return trace->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.
-      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,
-                                 trace->backtrack());
-      assembler->Bind(&skip_empty_check);
-      return on_success()->Emit(compiler, trace);
+      break;
     }
-    case POSITIVE_SUBMATCH_SUCCESS:
-      if (!trace->is_trivial()) return trace->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;
-        // Load current character jumps to the label if we are beyond the string
-        // end.
-        assembler->LoadCurrentCharacter(0, &at_end);
-        assembler->GoTo(trace->backtrack());
-        assembler->Bind(&at_end);
+    case POSITIVE_SUBMATCH_SUCCESS: {
+      if (!trace->is_trivial()) {
+        trace->Flush(compiler, this);
+        return;
       }
       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) {
+        on_success()->Emit(compiler, trace);
+        return;
+      }
+      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);
+      on_success()->Emit(compiler, &new_trace);
+
+      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;
+    }
     default:
       UNREACHABLE();
-      return false;
   }
 }
 
 
-bool BackReferenceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
+void BackReferenceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
   if (!trace->is_trivial()) {
-    return trace->Flush(compiler, this);
+    trace->Flush(compiler, this);
+    return;
   }
 
   LimitResult limit_result = LimitVersions(compiler, trace);
-  if (limit_result == DONE) return true;
-  if (limit_result == FAIL) return false;
+  if (limit_result == DONE) return;
   ASSERT(limit_result == CONTINUE);
 
   RecursionCheck rc(compiler);
 
   ASSERT_EQ(start_reg_ + 1, end_reg_);
-  if (info()->at_end) {
-    // If we are constrained to match at the end of the input then succeed
-    // iff the back reference is empty.
-    assembler->CheckNotRegistersEqual(start_reg_,
-                                      end_reg_,
-                                      trace->backtrack());
+  if (compiler->ignore_case()) {
+    assembler->CheckNotBackReferenceIgnoreCase(start_reg_,
+                                               trace->backtrack());
   } else {
-    if (compiler->ignore_case()) {
-      assembler->CheckNotBackReferenceIgnoreCase(start_reg_,
-                                                 trace->backtrack());
-    } else {
-      assembler->CheckNotBackReference(start_reg_, trace->backtrack());
-    }
+    assembler->CheckNotBackReference(start_reg_, trace->backtrack());
   }
-  return on_success()->Emit(compiler, trace);
+  on_success()->Emit(compiler, trace);
 }
 
 
 // -------------------------------------------------------------------
 // Dot/dotty output
 
 
 #ifdef DEBUG
 
 
@@ skipping 218 matching lines @@
   Visit(that->on_success());
 }
 
 
 void DotPrinter::VisitEnd(EndNode* that) {
   stream()->Add("  n%p [style=bold, shape=point];\n", that);
   PrintAttributes(that);
 }
 
 
+void DotPrinter::VisitAssertion(AssertionNode* that) {
+  stream()->Add("  n%p [", that);
+  switch (that->type()) {
+    case AssertionNode::AT_END:
+      stream()->Add("label=\"$\", shape=septagon");
+      break;
+    case AssertionNode::AT_START:
+      stream()->Add("label=\"^\", shape=septagon");
+      break;
+    case AssertionNode::AT_BOUNDARY:
+      stream()->Add("label=\"\\b\", shape=septagon");
+      break;
+    case AssertionNode::AT_NON_BOUNDARY:
+      stream()->Add("label=\"\\B\", shape=septagon");
+      break;
+    case AssertionNode::AFTER_NEWLINE:
+      stream()->Add("label=\"(?<=\\n)\", shape=septagon");
+      break;
+  }
+  stream()->Add("];\n");
+  PrintAttributes(that);
+  RegExpNode* successor = that->on_success();
+  stream()->Add("  n%p -> n%p;\n", that, successor);
+  Visit(successor);
+}
+
+
 void DotPrinter::VisitAction(ActionNode* that) {
   stream()->Add("  n%p [", that);
   switch (that->type_) {
     case ActionNode::SET_REGISTER:
       stream()->Add("label=\"$%i:=%i\", shape=octagon",
                     that->data_.u_store_register.reg,
                     that->data_.u_store_register.value);
       break;
     case ActionNode::INCREMENT_REGISTER:
       stream()->Add("label=\"$%i++\", shape=octagon",
@@ skipping 304 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 15 matching lines @@
     return center;
   }
 }
 
 
 RegExpNode* RegExpAssertion::ToNode(RegExpCompiler* compiler,
                                     RegExpNode* on_success) {
   NodeInfo info;
   switch (type()) {
     case START_OF_LINE:
-      info.follows_newline_interest = true;
-      break;
+      return AssertionNode::AfterNewline(on_success);
     case START_OF_INPUT:
-      info.follows_start_interest = true;
-      break;
-    case BOUNDARY: case NON_BOUNDARY:
-      info.follows_word_interest = true;
-      break;
+      return AssertionNode::AtStart(on_success);
+    case BOUNDARY:
+      return AssertionNode::AtBoundary(on_success);
+    case NON_BOUNDARY:
+      return AssertionNode::AtNonBoundary(on_success);
     case END_OF_INPUT:
-      info.at_end = true;
-      break;
-    case END_OF_LINE:
-      // This is wrong but has the effect of making the compiler abort.
-      info.at_end = true;
+      return AssertionNode::AtEnd(on_success);
+    case END_OF_LINE: {
+      // Compile $ in multiline regexps as an alternation with a positive
+      // lookahead in one side and an end-of-input on the other side.
+      // We need two registers for the lookahead.
+      int stack_pointer_register = compiler->AllocateRegister();
+      int position_register = compiler->AllocateRegister();
+      // The ChoiceNode to distinguish between a newline and end-of-input.
+      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));
+      result->AddAlternative(end_alternative);
+      return result;
+    }
+    default:
+      UNREACHABLE();
   }
-  return on_success->PropagateForward(&info);
+  return on_success;
 }
 
 
 RegExpNode* RegExpBackReference::ToNode(RegExpCompiler* compiler,
                                         RegExpNode* on_success) {
   return new BackReferenceNode(RegExpCapture::StartRegister(index()),
                                RegExpCapture::EndRegister(index()),
                                on_success);
 }
 
 
 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.  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));
+                                                  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 52 matching lines @@
       AddClassNegated(kLineTerminatorRanges,
                       kLineTerminatorRangeCount,
                       ranges);
       break;
     // This is not a character range as defined by the spec but a
     // convenient shorthand for a character class that matches any
     // character.
     case '*':
       ranges->Add(CharacterRange::Everything());
       break;
+    // This is the set of characters matched by the $ and ^ symbols
+    // in multiline mode.
+    case 'n':
+      AddClass(kLineTerminatorRanges,
+               kLineTerminatorRangeCount,
+               ranges);
+      break;
     default:
       UNREACHABLE();
   }
 }
 
 
 Vector<const uc16> CharacterRange::GetWordBounds() {
   return Vector<const uc16>(kWordRanges, kWordRangeCount);
 }
 
@@ skipping 165 matching lines @@
 
 template <class C>
 static RegExpNode* PropagateToEndpoint(C* node, NodeInfo* info) {
   NodeInfo full_info(*node->info());
   full_info.AddFromPreceding(info);
   bool cloned = false;
   return RegExpNode::EnsureSibling(node, &full_info, &cloned);
 }
 
 
-RegExpNode* ActionNode::PropagateForward(NodeInfo* info) {
-  NodeInfo full_info(*this->info());
-  full_info.AddFromPreceding(info);
-  bool cloned = false;
-  ActionNode* action = EnsureSibling(this, &full_info, &cloned);
-  action->set_on_success(action->on_success()->PropagateForward(info));
-  return action;
-}
-
-
-RegExpNode* ChoiceNode::PropagateForward(NodeInfo* info) {
-  NodeInfo full_info(*this->info());
-  full_info.AddFromPreceding(info);
-  bool cloned = false;
-  ChoiceNode* choice = EnsureSibling(this, &full_info, &cloned);
-  if (cloned) {
-    ZoneList<GuardedAlternative>* old_alternatives = alternatives();
-    int count = old_alternatives->length();
-    choice->alternatives_ = new ZoneList<GuardedAlternative>(count);
-    for (int i = 0; i < count; i++) {
-      GuardedAlternative alternative = old_alternatives->at(i);
-      alternative.set_node(alternative.node()->PropagateForward(info));
-      choice->alternatives()->Add(alternative);
-    }
-  }
-  return choice;
-}
-
-
-RegExpNode* EndNode::PropagateForward(NodeInfo* info) {
-  return PropagateToEndpoint(this, info);
-}
-
-
-RegExpNode* BackReferenceNode::PropagateForward(NodeInfo* info) {
-  NodeInfo full_info(*this->info());
-  full_info.AddFromPreceding(info);
-  bool cloned = false;
-  BackReferenceNode* back_ref = EnsureSibling(this, &full_info, &cloned);
-  if (cloned) {
-    // TODO(erikcorry): A back reference has to have two successors (by default
-    // the same node).  The first is used if the back reference matches a non-
-    // empty back reference, the second if it matches an empty one.  This
-    // doesn't matter for at_end, which is the only one implemented right now,
-    // but it will matter for other pieces of info.
-    back_ref->set_on_success(back_ref->on_success()->PropagateForward(info));
-  }
-  return back_ref;
-}
-
-
-RegExpNode* TextNode::PropagateForward(NodeInfo* info) {
-  return PropagateToEndpoint(this, info);
-}
-
-
 // -------------------------------------------------------------------
 // Splay tree
 
 
 OutSet* OutSet::Extend(unsigned value) {
   if (Get(value))
     return this;
   if (successors() != NULL) {
     for (int i = 0; i < successors()->length(); i++) {
       OutSet* successor = successors()->at(i);
@@ skipping 217 matching lines @@
   EnsureAnalyzed(that->loop_node());
   info->AddFromFollowing(that->loop_node()->info());
 }
 
 
 void Analysis::VisitBackReference(BackReferenceNode* that) {
   EnsureAnalyzed(that->on_success());
 }
 
 
+void Analysis::VisitAssertion(AssertionNode* that) {
+  EnsureAnalyzed(that->on_success());
+}
+
+
 // -------------------------------------------------------------------
 // Dispatch table construction
 
 
 void DispatchTableConstructor::VisitEnd(EndNode* that) {
   AddRange(CharacterRange::Everything());
 }
 
 
 void DispatchTableConstructor::BuildTable(ChoiceNode* node) {
@@ skipping 32 matching lines @@
 }
 
 
 void DispatchTableConstructor::VisitBackReference(BackReferenceNode* that) {
   // TODO(160): Find the node that we refer back to and propagate its start
   // set back to here.  For now we just accept anything.
   AddRange(CharacterRange::Everything());
 }
 
 
+void DispatchTableConstructor::VisitAssertion(AssertionNode* that) {
+  RegExpNode* target = that->on_success();
+  target->Accept(this);
+}
+
+
 
 static int CompareRangeByFrom(const CharacterRange* a,
                               const CharacterRange* b) {
   return Compare<uc16>(a->from(), b->from());
 }
 
 
 void DispatchTableConstructor::AddInverse(ZoneList<CharacterRange>* ranges) {
   ranges->Sort(CompareRangeByFrom);
   uc16 last = 0;
@@ skipping 43 matching lines @@
   RegExpNode* target = that->on_success();
   target->Accept(this);
 }
 
 
 Handle<FixedArray> RegExpEngine::Compile(RegExpCompileData* data,
                                          bool ignore_case,
                                          bool is_multiline,
                                          Handle<String> pattern,
                                          bool is_ascii) {
+  if ((data->capture_count + 1) * 2 - 1 > RegExpMacroAssembler::kMaxRegister) {
+    return IrregexpRegExpTooBig(pattern);
+  }
   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());
-  // Add a .*? at the beginning, outside the body capture.
-  // Note: We could choose to not add this if the regexp is anchored at
-  //   the start of the input but I'm not sure how best to do that and
-  //   since we don't even handle ^ yet I'm saving that optimization for
-  //   later.
-  RegExpNode* node = RegExpQuantifier::ToNode(0,
-                                              RegExpTree::kInfinity,
-                                              false,
-                                              new RegExpCharacterClass('*'),
-                                              &compiler,
-                                              captured_body);
+  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);
+  }
   data->node = node;
   Analysis analysis(ignore_case);
   analysis.EnsureAnalyzed(node);
 
   NodeInfo info = *node->info();
 
-  if (is_multiline && !FLAG_attempt_multiline_irregexp) {
-    return Handle<FixedArray>::null();
-  }
-
   if (FLAG_irregexp_native) {
 #ifdef ARM
     // Unimplemented, fall-through to bytecode implementation.
 #else  // IA32
     RegExpMacroAssemblerIA32::Mode mode;
     if (is_ascii) {
       mode = RegExpMacroAssemblerIA32::ASCII;
     } else {
       mode = RegExpMacroAssemblerIA32::UC16;
     }
     RegExpMacroAssemblerIA32 macro_assembler(mode,
                                              (data->capture_count + 1) * 2);
     return compiler.Assemble(&macro_assembler,
                              node,
                              data->capture_count,
                              pattern);
 #endif
   }
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal