Experimental support for RegExp lookbehind.

src/regexp/jsregexp.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/regexp/jsregexp.h"
 
 #include "src/ast.h"
 #include "src/base/platform/platform.h"
 #include "src/compilation-cache.h"
 #include "src/compiler.h"
@@ skipping 984 matching lines @@
   void SetRegExpTooBig() { reg_exp_too_big_ = true; }
 
   inline bool ignore_case() { return ignore_case_; }
   inline bool one_byte() { return one_byte_; }
   inline bool optimize() { return optimize_; }
   inline void set_optimize(bool value) { optimize_ = value; }
   inline bool limiting_recursion() { return limiting_recursion_; }
   inline void set_limiting_recursion(bool value) {
     limiting_recursion_ = value;
   }
+  bool read_backward() { return read_backward_; }
+  void set_read_backward(bool value) { read_backward_ = value; }
   FrequencyCollator* frequency_collator() { return &frequency_collator_; }
 
   int current_expansion_factor() { return current_expansion_factor_; }
   void set_current_expansion_factor(int value) {
     current_expansion_factor_ = value;
   }
 
   Isolate* isolate() const { return isolate_; }
   Zone* zone() const { return zone_; }
 
   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 one_byte_;
   bool reg_exp_too_big_;
   bool limiting_recursion_;
   bool optimize_;
+  bool read_backward_;
   int current_expansion_factor_;
   FrequencyCollator frequency_collator_;
   Isolate* isolate_;
   Zone* zone_;
 };
 
 
 class RecursionCheck {
  public:
   explicit RecursionCheck(RegExpCompiler* compiler) : compiler_(compiler) {
@@ skipping 15 matching lines @@
 RegExpCompiler::RegExpCompiler(Isolate* isolate, Zone* zone, int capture_count,
                                bool ignore_case, bool one_byte)
     : next_register_(2 * (capture_count + 1)),
       work_list_(NULL),
       recursion_depth_(0),
       ignore_case_(ignore_case),
       one_byte_(one_byte),
       reg_exp_too_big_(false),
       limiting_recursion_(false),
       optimize_(FLAG_regexp_optimization),
+      read_backward_(false),
       current_expansion_factor_(1),
       frequency_collator_(),
       isolate_(isolate),
       zone_(zone) {
   accept_ = new(zone) EndNode(EndNode::ACCEPT, zone);
   DCHECK(next_register_ - 1 <= RegExpMacroAssembler::kMaxRegister);
 }
 
 
 RegExpEngine::CompilationResult RegExpCompiler::Assemble(
@@ skipping 144 matching lines @@
 
     // 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;
+    static const int kNoStore = kMinInt;
+    int store_position = kNoStore;
     // 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->action_type()) {
           case ActionNode::SET_REGISTER: {
             Trace::DeferredSetRegister* psr =
                 static_cast<Trace::DeferredSetRegister*>(action);
             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;
-            DCHECK_EQ(store_position, -1);
+            DCHECK_EQ(store_position, kNoStore);
             DCHECK(!clear);
             break;
           }
           case ActionNode::INCREMENT_REGISTER:
             if (!absolute) {
               value++;
             }
-            DCHECK_EQ(store_position, -1);
+            DCHECK_EQ(store_position, kNoStore);
             DCHECK(!clear);
             undo_action = RESTORE;
             break;
           case ActionNode::STORE_POSITION: {
             Trace::DeferredCapture* pc =
                 static_cast<Trace::DeferredCapture*>(action);
-            if (!clear && store_position == -1) {
+            if (!clear && store_position == kNoStore) {
               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;
             }
             DCHECK(!absolute);
             DCHECK_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 == kNoStore) {
               clear = true;
             }
             undo_action = RESTORE;
             DCHECK(!absolute);
             DCHECK_EQ(value, 0);
             break;
           }
           default:
             UNREACHABLE();
             break;
@@ skipping 10 matching lines @@
         pushes = 0;
       }
 
       assembler->PushRegister(reg, stack_check);
       registers_to_pop->Set(reg, zone);
     } else if (undo_action == CLEAR) {
       registers_to_clear->Set(reg, zone);
     }
     // Perform the chronologically last action (or accumulated increment)
     // for the register.
-    if (store_position != -1) {
+    if (store_position != kNoStore) {
       assembler->WriteCurrentPositionToRegister(reg, store_position);
     } else if (clear) {
       assembler->ClearRegisters(reg, reg);
     } else if (absolute) {
       assembler->SetRegister(reg, value);
     } else if (value != 0) {
       assembler->AdvanceRegister(reg, value);
     }
   }
 }
@@ skipping 977 matching lines @@
   // Match the behaviour of EatsAtLeast on this node.
   if (assertion_type() == AT_START && not_at_start) return;
   on_success()->FillInBMInfo(isolate, offset, budget - 1, bm, not_at_start);
   SaveBMInfo(bm, not_at_start, offset);
 }
 
 
 int BackReferenceNode::EatsAtLeast(int still_to_find,
                                    int budget,
                                    bool not_at_start) {
+  if (read_backward()) return 0;
   if (budget <= 0) return 0;
   return on_success()->EatsAtLeast(still_to_find,
                                    budget - 1,
                                    not_at_start);
 }
 
 
 int TextNode::EatsAtLeast(int still_to_find,
                           int budget,
                           bool not_at_start) {
+  if (read_backward()) return 0;
   int answer = Length();
   if (answer >= still_to_find) return answer;
   if (budget <= 0) return answer;
   // We are not at start after this node so we set the last argument to 'true'.
   return answer + on_success()->EatsAtLeast(still_to_find - answer,
                                             budget - 1,
                                             true);
 }
 
 
@@ skipping 183 matching lines @@
                                     bool not_at_start) {
   Isolate* isolate = compiler->macro_assembler()->isolate();
   DCHECK(characters_filled_in < details->characters());
   int characters = details->characters();
   int char_mask;
   if (compiler->one_byte()) {
     char_mask = String::kMaxOneByteCharCode;
   } else {
     char_mask = String::kMaxUtf16CodeUnit;
   }
-  for (int k = 0; k < elms_->length(); k++) {
-    TextElement elm = elms_->at(k);
+  for (int k = 0; k < elements()->length(); k++) {
+    TextElement elm = elements()->at(k);
     if (elm.text_type() == TextElement::ATOM) {
       Vector<const uc16> quarks = elm.atom()->data();
       for (int i = 0; i < characters && i < quarks.length(); i++) {
         QuickCheckDetails::Position* pos =
             details->positions(characters_filled_in);
         uc16 c = quarks[i];
         if (compiler->ignore_case()) {
           unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
           int length = GetCaseIndependentLetters(isolate, c,
                                                  compiler->one_byte(), chars);
@@ skipping 130 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 one_byte) {
-  DCHECK(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 81 matching lines @@
   }
   return false;
 }
 
 
 RegExpNode* TextNode::FilterOneByte(int depth, bool ignore_case) {
   if (info()->replacement_calculated) return replacement();
   if (depth < 0) return this;
   DCHECK(!info()->visited);
   VisitMarker marker(info());
-  int element_count = elms_->length();
+  int element_count = elements()->length();
   for (int i = 0; i < element_count; i++) {
-    TextElement elm = elms_->at(i);
+    TextElement elm = elements()->at(i);
     if (elm.text_type() == TextElement::ATOM) {
       Vector<const uc16> quarks = elm.atom()->data();
       for (int j = 0; j < quarks.length(); j++) {
         uint16_t c = quarks[j];
         if (c <= String::kMaxOneByteCharCode) continue;
         if (!ignore_case) return set_replacement(NULL);
         // Here, we need to check for characters whose upper and lower cases
         // are outside the Latin-1 range.
         uint16_t converted = unibrow::Latin1::ConvertNonLatin1ToLatin1(c);
         // Character is outside Latin-1 completely
@@ skipping 343 matching lines @@
       assembler->GoTo(trace->backtrack());
       assembler->Bind(&ok);
       break;
     }
     case AT_START: {
       if (trace->at_start() == Trace::FALSE_VALUE) {
         assembler->GoTo(trace->backtrack());
         return;
       }
       if (trace->at_start() == Trace::UNKNOWN) {
-        assembler->CheckNotAtStart(trace->backtrack());
+        assembler->CheckNotAtStart(trace->cp_offset(), trace->backtrack());
         Trace at_start_trace = *trace;
-        at_start_trace.set_at_start(true);
+        at_start_trace.set_at_start(Trace::TRUE_VALUE);
         on_success()->Emit(compiler, &at_start_trace);
         return;
       }
     }
     break;
     case AFTER_NEWLINE:
       EmitHat(compiler, on_success(), trace);
       return;
     case AT_BOUNDARY:
     case AT_NON_BOUNDARY: {
@@ skipping 52 matching lines @@
                             TextEmitPassType pass,
                             bool preloaded,
                             Trace* trace,
                             bool first_element_checked,
                             int* checked_up_to) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
   Isolate* isolate = assembler->isolate();
   bool one_byte = compiler->one_byte();
   Label* backtrack = trace->backtrack();
   QuickCheckDetails* quick_check = trace->quick_check_performed();
-  int element_count = elms_->length();
+  int element_count = elements()->length();
+  int backward_offset = read_backward() ? -Length() : 0;
   for (int i = preloaded ? 0 : element_count - 1; i >= 0; i--) {
-    TextElement elm = elms_->at(i);
-    int cp_offset = trace->cp_offset() + elm.cp_offset();
+    TextElement elm = elements()->at(i);
+    int cp_offset = trace->cp_offset() + elm.cp_offset() + backward_offset;
     if (elm.text_type() == TextElement::ATOM) {
       Vector<const uc16> quarks = elm.atom()->data();
       for (int j = preloaded ? 0 : quarks.length() - 1; j >= 0; j--) {
         if (first_element_checked && i == 0 && j == 0) continue;
         if (DeterminedAlready(quick_check, elm.cp_offset() + j)) continue;
         EmitCharacterFunction* emit_function = NULL;
         switch (pass) {
           case NON_LATIN1_MATCH:
             DCHECK(one_byte);
             if (quarks[j] > String::kMaxOneByteCharCode) {
               assembler->GoTo(backtrack);
               return;
             }
             break;
           case NON_LETTER_CHARACTER_MATCH:
             emit_function = &EmitAtomNonLetter;
             break;
           case SIMPLE_CHARACTER_MATCH:
             emit_function = &EmitSimpleCharacter;
             break;
           case CASE_CHARACTER_MATCH:
             emit_function = &EmitAtomLetter;
             break;
           default:
             break;
         }
         if (emit_function != NULL) {
-          bool bound_checked = emit_function(isolate,
-                                             compiler,
-                                             quarks[j],
-                                             backtrack,
-                                             cp_offset + j,
-                                             *checked_up_to < cp_offset + j,
-                                             preloaded);
+          bool bounds_check = *checked_up_to < cp_offset + j || read_backward();
+          bool bound_checked =
+              emit_function(isolate, compiler, quarks[j], backtrack,
+                            cp_offset + j, bounds_check, preloaded);
           if (bound_checked) UpdateBoundsCheck(cp_offset + j, checked_up_to);
         }
       }
     } else {
       DCHECK_EQ(TextElement::CHAR_CLASS, elm.text_type());
       if (pass == CHARACTER_CLASS_MATCH) {
         if (first_element_checked && i == 0) continue;
         if (DeterminedAlready(quick_check, elm.cp_offset())) continue;
         RegExpCharacterClass* cc = elm.char_class();
+        bool bounds_check = *checked_up_to < cp_offset || read_backward();
         EmitCharClass(assembler, cc, one_byte, backtrack, cp_offset,
-                      *checked_up_to < cp_offset, preloaded, zone());
+                      bounds_check, preloaded, zone());
         UpdateBoundsCheck(cp_offset, checked_up_to);
       }
     }
   }
 }
 
 
 int TextNode::Length() {
-  TextElement elm = elms_->last();
+  TextElement elm = elements()->last();
   DCHECK(elm.cp_offset() >= 0);
   return elm.cp_offset() + elm.length();
 }
 
 
 bool TextNode::SkipPass(int int_pass, bool ignore_case) {
   TextEmitPassType pass = static_cast<TextEmitPassType>(int_pass);
   if (ignore_case) {
     return pass == SIMPLE_CHARACTER_MATCH;
   } else {
@@ skipping 48 matching lines @@
       TextEmitPass(compiler,
                    static_cast<TextEmitPassType>(pass),
                    false,
                    trace,
                    first_elt_done,
                    &bound_checked_to);
     }
   }
 
   Trace successor_trace(*trace);
-  successor_trace.set_at_start(false);
-  successor_trace.AdvanceCurrentPositionInTrace(Length(), compiler);
+  // If we advance backward, we may end up at the start.
+  successor_trace.AdvanceCurrentPositionInTrace(
+      read_backward() ? -Length() : Length(), compiler);
+  successor_trace.set_at_start(read_backward() ? Trace::UNKNOWN
+                                               : Trace::FALSE_VALUE);
   RecursionCheck rc(compiler);
   on_success()->Emit(compiler, &successor_trace);
 }
 
 
 void Trace::InvalidateCurrentCharacter() {
   characters_preloaded_ = 0;
 }
 
 
 void Trace::AdvanceCurrentPositionInTrace(int by, RegExpCompiler* compiler) {
-  DCHECK(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, compiler->one_byte());
   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(Isolate* isolate, bool is_one_byte) {
-  int element_count = elms_->length();
+  int element_count = elements()->length();
   for (int i = 0; i < element_count; i++) {
-    TextElement elm = elms_->at(i);
+    TextElement elm = elements()->at(i);
     if (elm.text_type() == TextElement::CHAR_CLASS) {
       RegExpCharacterClass* cc = elm.char_class();
       // None of the standard character classes is different in the case
       // independent case and it slows us down if we don't know that.
       if (cc->is_standard(zone())) continue;
       ZoneList<CharacterRange>* ranges = cc->ranges(zone());
       int range_count = ranges->length();
       for (int j = 0; j < range_count; j++) {
         ranges->at(j).AddCaseEquivalents(isolate, zone(), ranges, is_one_byte);
       }
     }
   }
 }
 
 
-int TextNode::GreedyLoopTextLength() {
-  TextElement elm = elms_->at(elms_->length() - 1);
-  return elm.cp_offset() + elm.length();
-}
+int TextNode::GreedyLoopTextLength() { return Length(); }
 
 
 RegExpNode* TextNode::GetSuccessorOfOmnivorousTextNode(
     RegExpCompiler* compiler) {
-  if (elms_->length() != 1) return NULL;
-  TextElement elm = elms_->at(0);
+  if (read_backward()) return NULL;
+  if (elements()->length() != 1) return NULL;
+  TextElement elm = elements()->at(0);
   if (elm.text_type() != TextElement::CHAR_CLASS) return NULL;
   RegExpCharacterClass* node = elm.char_class();
   ZoneList<CharacterRange>* ranges = node->ranges(zone());
   if (!CharacterRange::IsCanonical(ranges)) {
     CharacterRange::Canonicalize(ranges);
   }
   if (node->is_negated()) {
     return ranges->length() == 0 ? on_success() : NULL;
   }
   if (ranges->length() != 1) return NULL;
@@ skipping 23 matching lines @@
       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;
+  return read_backward() ? -length : length;
 }
 
 
 void LoopChoiceNode::AddLoopAlternative(GuardedAlternative alt) {
   DCHECK_NULL(loop_node_);
   AddAlternative(alt);
   loop_node_ = alt.node();
 }
 
 
@@ skipping 410 matching lines @@
  *        V       |S
  *        Q2 ---> U----->backtrack
  *        |  F   /
  *       S|     /
  *        V  F /
  *        S2--/
  */
 
 GreedyLoopState::GreedyLoopState(bool not_at_start) {
   counter_backtrack_trace_.set_backtrack(&label_);
-  if (not_at_start) counter_backtrack_trace_.set_at_start(false);
+  if (not_at_start) counter_backtrack_trace_.set_at_start(Trace::FALSE_VALUE);
 }
 
 
 void ChoiceNode::AssertGuardsMentionRegisters(Trace* trace) {
 #ifdef DEBUG
   int choice_count = alternatives_->length();
   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();
@@ skipping 106 matching lines @@
   // and other simple nodes.  These are handled by pushing the current
   // position on the stack and then incrementing the current position each
   // time around the switch.  On backtrack we decrement the current position
   // and check it against the pushed value.  This avoids pushing backtrack
   // information for each iteration of the loop, which could take up a lot of
   // space.
   DCHECK(trace->stop_node() == NULL);
   macro_assembler->PushCurrentPosition();
   Label greedy_match_failed;
   Trace greedy_match_trace;
-  if (not_at_start()) greedy_match_trace.set_at_start(false);
+  if (not_at_start()) greedy_match_trace.set_at_start(Trace::FALSE_VALUE);
   greedy_match_trace.set_backtrack(&greedy_match_failed);
   Label loop_label;
   macro_assembler->Bind(&loop_label);
   greedy_match_trace.set_stop_node(this);
   greedy_match_trace.set_loop_label(&loop_label);
   alternatives_->at(0).node()->Emit(compiler, &greedy_match_trace);
   macro_assembler->Bind(&greedy_match_failed);
 
   Label second_choice;  // For use in greedy matches.
   macro_assembler->Bind(&second_choice);
@@ skipping 325 matching lines @@
   }
 
   LimitResult limit_result = LimitVersions(compiler, trace);
   if (limit_result == DONE) return;
   DCHECK(limit_result == CONTINUE);
 
   RecursionCheck rc(compiler);
 
   DCHECK_EQ(start_reg_ + 1, end_reg_);
   if (compiler->ignore_case()) {
-    assembler->CheckNotBackReferenceIgnoreCase(start_reg_,
+    assembler->CheckNotBackReferenceIgnoreCase(start_reg_, read_backward(),
                                                trace->backtrack());
   } else {
-    assembler->CheckNotBackReference(start_reg_, trace->backtrack());
+    assembler->CheckNotBackReference(start_reg_, read_backward(),
+                                     trace->backtrack());
   }
+  // We are going to advance backward, so we may end up at the start.
+  if (read_backward()) trace->set_at_start(Trace::UNKNOWN);
   on_success()->Emit(compiler, trace);
 }
 
 
 // -------------------------------------------------------------------
 // Dot/dotty output
 
 
 #ifdef DEBUG
 
@@ skipping 340 matching lines @@
 
 
 // -------------------------------------------------------------------
 // Tree to graph conversion
 
 RegExpNode* RegExpAtom::ToNode(RegExpCompiler* compiler,
                                RegExpNode* on_success) {
   ZoneList<TextElement>* elms =
       new(compiler->zone()) ZoneList<TextElement>(1, compiler->zone());
   elms->Add(TextElement::Atom(this), compiler->zone());
-  return new(compiler->zone()) TextNode(elms, on_success);
+  return new (compiler->zone())
+      TextNode(elms, compiler->read_backward(), on_success);
 }
 
 
 RegExpNode* RegExpText::ToNode(RegExpCompiler* compiler,
                                RegExpNode* on_success) {
-  return new(compiler->zone()) TextNode(elements(), on_success);
+  return new (compiler->zone())
+      TextNode(elements(), compiler->read_backward(), on_success);
 }
 
 
 static bool CompareInverseRanges(ZoneList<CharacterRange>* ranges,
                                  const int* special_class,
                                  int length) {
   length--;  // Remove final 0x10000.
   DCHECK(special_class[length] == 0x10000);
   DCHECK(ranges->length() != 0);
   DCHECK(length != 0);
@@ skipping 76 matching lines @@
   if (CompareInverseRanges(set_.ranges(zone), kWordRanges, kWordRangeCount)) {
     set_.set_standard_set_type('W');
     return true;
   }
   return false;
 }
 
 
 RegExpNode* RegExpCharacterClass::ToNode(RegExpCompiler* compiler,
                                          RegExpNode* on_success) {
-  return new(compiler->zone()) TextNode(this, on_success);
+  return new (compiler->zone())
+      TextNode(this, compiler->read_backward(), on_success);
 }
 
 
 int CompareFirstChar(RegExpTree* const* a, RegExpTree* const* b) {
   RegExpAtom* atom1 = (*a)->AsAtom();
   RegExpAtom* atom2 = (*b)->AsAtom();
   uc16 character1 = atom1->data().at(0);
   uc16 character2 = atom2->data().at(0);
   if (character1 < character2) return -1;
   if (character1 > character2) return 1;
@@ skipping 361 matching lines @@
           if (is_greedy) {
             alternation->AddAlternative(
                 GuardedAlternative(body->ToNode(compiler, answer)));
             alternation->AddAlternative(GuardedAlternative(on_success));
           } else {
             alternation->AddAlternative(GuardedAlternative(on_success));
             alternation->AddAlternative(
                 GuardedAlternative(body->ToNode(compiler, answer)));
           }
           answer = alternation;
-          if (not_at_start) alternation->set_not_at_start();
+          if (not_at_start && !compiler->read_backward()) {
+            alternation->set_not_at_start();
+          }
         }
         return answer;
       }
     }
   }
   bool has_min = min > 0;
   bool has_max = max < RegExpTree::kInfinity;
   bool needs_counter = has_min || has_max;
   int reg_ctr = needs_counter
       ? compiler->AllocateRegister()
       : RegExpCompiler::kNoRegister;
-  LoopChoiceNode* center = new(zone) LoopChoiceNode(body->min_match() == 0,
-                                                    zone);
-  if (not_at_start) center->set_not_at_start();
+  LoopChoiceNode* center = new (zone)
+      LoopChoiceNode(body->min_match() == 0, compiler->read_backward(), zone);
+  if (not_at_start && !compiler->read_backward()) center->set_not_at_start();
   RegExpNode* loop_return = needs_counter
       ? static_cast<RegExpNode*>(ActionNode::IncrementRegister(reg_ctr, center))
       : static_cast<RegExpNode*>(center);
   if (body_can_be_empty) {
     // If the body can be empty we need to check if it was and then
     // backtrack.
     loop_return = ActionNode::EmptyMatchCheck(body_start_reg,
                                               reg_ctr,
                                               min,
                                               loop_return);
@@ skipping 55 matching lines @@
       // 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(zone) ChoiceNode(2, zone);
       // Create a newline atom.
       ZoneList<CharacterRange>* newline_ranges =
           new(zone) ZoneList<CharacterRange>(3, zone);
       CharacterRange::AddClassEscape('n', newline_ranges, zone);
-      RegExpCharacterClass* newline_atom = new(zone) RegExpCharacterClass('n');
-      TextNode* newline_matcher = new(zone) TextNode(
-         newline_atom,
-         ActionNode::PositiveSubmatchSuccess(stack_pointer_register,
-                                             position_register,
-                                             0,  // No captures inside.
-                                             -1,  // Ignored if no captures.
-                                             on_success));
+      RegExpCharacterClass* newline_atom = new (zone) RegExpCharacterClass('n');
+      TextNode* newline_matcher = new (zone) TextNode(
+          newline_atom, false, 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;
 }
 
 
 RegExpNode* RegExpBackReference::ToNode(RegExpCompiler* compiler,
                                         RegExpNode* on_success) {
-  return new(compiler->zone())
+  return new (compiler->zone())
       BackReferenceNode(RegExpCapture::StartRegister(index()),
                         RegExpCapture::EndRegister(index()),
-                        on_success);
+                        compiler->read_backward(), on_success);
 }
 
 
 RegExpNode* RegExpEmpty::ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success) {
   return on_success;
 }
 
 
-RegExpNode* RegExpLookahead::ToNode(RegExpCompiler* compiler,
-                                    RegExpNode* on_success) {
+RegExpNode* RegExpLookaround::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;
+  RegExpNode* result;
+  bool was_reading_backward = compiler->read_backward();
+  compiler->set_read_backward(type() == LOOKBEHIND);
   if (is_positive()) {
-    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;
+    result = ActionNode::BeginSubmatch(
+        stack_pointer_register, position_register,
+        body()->ToNode(compiler,
+                       ActionNode::PositiveSubmatchSuccess(
+                           stack_pointer_register, position_register,
+                           register_count, register_start, on_success)));
   } else {
     // We use a ChoiceNode for a negative lookahead because it has most of
     // the characteristics we need.  It has the body of the lookahead as its
     // first alternative and the expression after the lookahead of the second
     // alternative.  If the first alternative succeeds then the
     // NegativeSubmatchSuccess will unwind the stack including everything the
     // choice node set up and backtrack.  If the first alternative fails then
     // the second alternative is tried, which is exactly the desired result
     // for a negative lookahead.  The NegativeLookaheadChoiceNode is a special
     // ChoiceNode that knows to ignore the first exit when calculating quick
     // checks.
     Zone* zone = compiler->zone();
 
     GuardedAlternative body_alt(
-        body()->ToNode(
-            compiler,
-            success = new(zone) NegativeSubmatchSuccess(stack_pointer_register,
-                                                        position_register,
-                                                        register_count,
-                                                        register_start,
-                                                        zone)));
+        body()->ToNode(compiler, new (zone) NegativeSubmatchSuccess(
+                                     stack_pointer_register, position_register,
+                                     register_count, register_start, zone)));
     ChoiceNode* choice_node =
         new(zone) NegativeLookaheadChoiceNode(body_alt,
                                               GuardedAlternative(on_success),
                                               zone);
-    return ActionNode::BeginSubmatch(stack_pointer_register,
-                                     position_register,
-                                     choice_node);
+    result = ActionNode::BeginSubmatch(stack_pointer_register,
+                                       position_register, choice_node);
   }
+  compiler->set_read_backward(was_reading_backward);
+  return result;
 }
 
 
 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) {
+  DCHECK_NOT_NULL(body);
   int start_reg = RegExpCapture::StartRegister(index);
   int end_reg = RegExpCapture::EndRegister(index);
+  if (compiler->read_backward()) std::swap(start_reg, end_reg);
   RegExpNode* store_end = ActionNode::StorePosition(end_reg, true, on_success);
   RegExpNode* body_node = body->ToNode(compiler, store_end);
   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);
+  if (compiler->read_backward()) {
+    for (int i = 0; i < children->length(); i++) {
+      current = children->at(i)->ToNode(compiler, current);
+    }
+  } else {
+    for (int i = children->length() - 1; i >= 0; i--) {
+      current = children->at(i)->ToNode(compiler, current);
+    }
   }
   return current;
 }
 
 
 static void AddClass(const int* elmv,
                      int elmc,
                      ZoneList<CharacterRange>* ranges,
                      Zone* zone) {
   elmc--;
@@ skipping 855 matching lines @@
                                                     0,
                                                     &compiler,
                                                     compiler.accept());
   RegExpNode* node = captured_body;
   bool is_end_anchored = data->tree->IsAnchoredAtEnd();
   bool is_start_anchored = data->tree->IsAnchoredAtStart();
   int max_length = data->tree->max_match();
   if (!is_start_anchored && !is_sticky) {
     // Add a .*? at the beginning, outside the body capture, unless
     // this expression is anchored at the beginning or sticky.
-    RegExpNode* loop_node =
-        RegExpQuantifier::ToNode(0,
-                                 RegExpTree::kInfinity,
-                                 false,
-                                 new(zone) RegExpCharacterClass('*'),
-                                 &compiler,
-                                 captured_body,
-                                 data->contains_anchor);
+    RegExpNode* loop_node = RegExpQuantifier::ToNode(
+        0, RegExpTree::kInfinity, false, new (zone) RegExpCharacterClass('*'),
+        &compiler, captured_body, data->contains_anchor);
 
     if (data->contains_anchor) {
       // Unroll loop once, to take care of the case that might start
       // at the start of input.
       ChoiceNode* first_step_node = new(zone) ChoiceNode(2, zone);
       first_step_node->AddAlternative(GuardedAlternative(captured_body));
-      first_step_node->AddAlternative(GuardedAlternative(
-          new(zone) TextNode(new(zone) RegExpCharacterClass('*'), loop_node)));
+      first_step_node->AddAlternative(GuardedAlternative(new (zone) TextNode(
+          new (zone) RegExpCharacterClass('*'), false, loop_node)));
       node = first_step_node;
     } else {
       node = loop_node;
     }
   }
   if (is_one_byte) {
     node = node->FilterOneByte(RegExpCompiler::kMaxRecursion, ignore_case);
     // Do it again to propagate the new nodes to places where they were not
     // put because they had not been calculated yet.
     if (node != NULL) {
@@ skipping 183 matching lines @@
 
 
 void RegExpResultsCache::Clear(FixedArray* cache) {
   for (int i = 0; i < kRegExpResultsCacheSize; i++) {
     cache->set(i, Smi::FromInt(0));
   }
 }
 
 }  // namespace internal
 }  // namespace v8