Add support for \b and ^ and $ in multiline mode, completing Irregexp...

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 1504 matching lines @@
   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);
-  }
-}
-
-
 bool NegativeSubmatchSuccess::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());
   }
-  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;
     case BACKTRACK:
-      ASSERT(!info()->at_end);
       assembler->GoTo(trace->backtrack());
       return true;
     case NEGATIVE_SUBMATCH_SUCCESS:
       // This case is handled in a different virtual method.
       UNREACHABLE();
   }
   UNIMPLEMENTED();
   return false;
 }
 
@@ skipping 348 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 28 matching lines @@
 }
 
 
 int ActionNode::EatsAtLeast(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);
 }
 
 
+int AssertionNode::EatsAtLeast(int recursion_depth) {
+  if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
+  return on_success()->EatsAtLeast(recursion_depth + 1);
+}
+
+
+int BackReferenceNode::EatsAtLeast(int recursion_depth) {
+  if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
+  return on_success()->EatsAtLeast(recursion_depth + 1);
+}
+
+
+
 int TextNode::EatsAtLeast(int recursion_depth) {
   int answer = Length();
   if (answer >= 4) return answer;
   if (recursion_depth > RegExpCompiler::kMaxRecursion) return answer;
   return answer + on_success()->EatsAtLeast(recursion_depth + 1);
 }
 
 
 int ChoiceNode::EatsAtLeastHelper(int recursion_depth,
                                   RegExpNode* ignore_this_node) {
@@ skipping 247 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);
+  }
+}
+
+
+bool AssertionNode::Emit(RegExpCompiler* compiler, Trace* trace) {
+  RegExpMacroAssembler* assembler = compiler->macro_assembler();
+  switch (type_) {
+    case AT_END: {
+      Label ok;
+      assembler->LoadCurrentCharacter(trace->cp_offset(), &ok);
+      assembler->GoTo(trace->backtrack());
+      assembler->Bind(&ok);
+      break;
+    }
+    case AT_START:
+      assembler->CheckNotAtStart(trace->backtrack());
+      break;
+    case AFTER_NEWLINE: {
+      // Check whether we are either at the start or immediately after a
+      // newline.
+      Trace new_trace(*trace);
+      // Invalidate the current character register.
+      new_trace.AdvanceCurrentPositionInTrace(0, compiler->ascii());
+
+      Label ok;
+      if (new_trace.cp_offset() == 0) {
+        assembler->CheckAtStart(&ok);
+      }
+      assembler->LoadCurrentCharacter(-1, new_trace.backtrack(), false);

[Christian Plesner Hansen, 2009/01/19 10:28:59]

Maybe a comment about why this works when you're at character 0?

+      // 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);
+      return on_success()->Emit(compiler, &new_trace);
+    }
+    case AT_NON_BOUNDARY:
+    case AT_BOUNDARY: {
+      Label before_non_word;

[Christian Plesner Hansen, 2009/01/19 10:28:59]

Maybe you could split these huge cases out into separate functions, that way you
could just pass different arguments for the boundary and non-boundary cases.

+      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);
+
+      // Invalidate the current character register.
+      Trace new_trace(*trace);
+      new_trace.AdvanceCurrentPositionInTrace(0, compiler->ascii());
+
+      Label ok;
+      Label* boundary;
+      Label* not_boundary;
+      if (type_ == 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) {
+        assembler->CheckAtStart(not_boundary);
+      }
+      assembler->LoadCurrentCharacter(new_trace.cp_offset() - 1,

[Christian Plesner Hansen, 2009/01/19 10:28:59]

What happens here if we're right at the beginning of the input?

+                                      &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) {
+        assembler->CheckAtStart(boundary);
+      }
+      assembler->LoadCurrentCharacter(new_trace.cp_offset() - 1,
+                                      &ok,  // Unused dummy label in this call.
+                                      false);
+      bool fall_through_on_word = (type_ == AT_NON_BOUNDARY);
+      EmitWordCheck(assembler, not_boundary, boundary, fall_through_on_word);
+
+      assembler->Bind(&ok);
+
+      return on_success()->Emit(compiler, &new_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 125 matching lines @@
 // 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) {
   LimitResult limit_result = LimitVersions(compiler, trace);
   if (limit_result == FAIL) return false;
   if (limit_result == DONE) return true;
   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 (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();
 
   // If a character is preloaded into the current character register then
@@ skipping 44 matching lines @@
                &bound_checked_to);
 
   Trace successor_trace(*trace);
   successor_trace.AdvanceCurrentPositionInTrace(Length(), compiler->ascii());
   RecursionCheck rc(compiler);
   return on_success()->Emit(compiler, &successor_trace);
 }
 
 
 void Trace::AdvanceCurrentPositionInTrace(int by, bool ascii) {
-  ASSERT(by > 0);
+  // We can call this with by == 0.  In that case it just means that the

[Christian Plesner Hansen, 2009/01/19 10:28:59]

Maybe split invalidation out into a separate method?  I was really confused by
the AdvanceCurrentPositionInTrace(0, ...) in EmitWordCheck.

+  // current position register has been invalidated.
+
   // 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);
   cp_offset_ += by;
   bound_checked_up_to_ = Max(0, bound_checked_up_to_ - by);
@@ skipping 33 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;
 }
@@ skipping 454 matching lines @@
       }
       // 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:
       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);
-      }
       assembler->ReadCurrentPositionFromRegister(
           data_.u_submatch.current_position_register);
       assembler->ReadStackPointerFromRegister(
           data_.u_submatch.stack_pointer_register);
       return on_success()->Emit(compiler, trace);
     default:
       UNREACHABLE();
       return false;
   }
 }
 
 
 bool BackReferenceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
   if (!trace->is_trivial()) {
     return trace->Flush(compiler, this);
   }
 
   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);
 
   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);
 }
 
 
 // -------------------------------------------------------------------
 // Dot/dotty output
 
 
 #ifdef DEBUG
@@ skipping 220 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 340 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;
+      return AssertionNode::AtEnd(on_success);
     case END_OF_LINE:
-      // This is wrong but has the effect of making the compiler abort.
-      info.at_end = true;
+      // 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(newline_ranges, false);

[Christian Plesner Hansen, 2009/01/19 10:28:59]

You should be able to just use "new RegExpCharacterClass('n')".

+      ZoneList<TextElement>* elms = new ZoneList<TextElement>(1);
+      elms->Add(TextElement::CharClass(newline_atom));
+      TextNode* newline_matcher = new TextNode(

[Christian Plesner Hansen, 2009/01/19 10:28:59]

You should be able to use "new TextNode(newline_atom, ...)".

+         elms,
+         ActionNode::PositiveSubmatchSuccess(stack_pointer_register,
+                                             position_register,
+                                             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;
   }
-  return on_success->PropagateForward(&info);
+  UNREACHABLE();

[Christian Plesner Hansen, 2009/01/19 10:28:59]

Maybe have this in the 'default' case, that way the compiler will complain if we
forget the return in one of the other cases.

+  return on_success;
 }
 
 
 RegExpNode* RegExpBackReference::ToNode(RegExpCompiler* compiler,
                                         RegExpNode* on_success) {
   return new BackReferenceNode(RegExpCapture::StartRegister(index()),
                                RegExpCapture::EndRegister(index()),
                                on_success);
 }
 
@@ skipping 126 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) {

[Christian Plesner Hansen, 2009/01/19 10:28:59]

O joy, we can get rid of all this cra..., I mean stuff.

-  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 66 matching lines @@
                                               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