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 1206 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();
+  return read_backward() ? kNodeIsTooComplexForGreedyLoops : Length();

[erikcorry, 2015/11/11 15:39:04]

This is a case where perhaps we do need a little optimization.  If we have a
very simple loop like:

foo.*bar

or

foo(?:bar)*baz

then the naïve solution can use backtracking stack proportional to the length of
the string.  This is why we recognize greedy loops, which should really be
called "greedy loops with a simple fixed width body". In that case we just use
registers and position counting, instead of pushing a bunch of backtracking
commands that all just decrement the current position.

With this change you can use memory proportional to the string size if you
search for:

(?<=foo.*)bar

as it searches backwards from bar to the start of the string, looking for foo. 
This will overflow the backtracking stack for big strings.

In the Fletch change the greedy loop optimization is taken care of even in
backwards mode.

See the Irregexp slide show for details.  Slides 35 to 57 (skip the interlude in
the middle).

By the way in Unicode mode, .* won't be an optimizable greedy loop in any
direction :-/

[Yang, 2015/11/12 08:25:35]

Done.

 }
 
 
 RegExpNode* TextNode::GetSuccessorOfOmnivorousTextNode(

[erikcorry, 2015/11/11 15:39:04]

Not quite sure, but this optimization may have to be switched off for backwards.
 It's basically there to handle the initial skipping forwards-to-find-the-match
part, which will always be forwards.  You can trigger it in the middle with [^]*
though.

[Yang, 2015/11/12 08:25:35]

I haven't found a test case where this would become an issue. The caller of this
method uses the return value to determine what eats_at_least value to use. But
we already return 0 for nodes that read backward.

I added a line just to be sure.

     RegExpCompiler* compiler) {
-  if (elms_->length() != 1) return NULL;
-  TextElement elm = elms_->at(0);
+  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 454 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, 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(), 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, 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 124 matching lines @@
       for (int j = 1; j < run_length && prefix_length > 1; j++) {
         RegExpAtom* old_atom =
             alternatives->at(j + first_with_prefix)->AsAtom();
         for (int k = 1; k < prefix_length; k++) {
           if (atom->data().at(k) != old_atom->data().at(k)) {
             prefix_length = k;
             break;
           }
         }
       }
-      RegExpAtom* prefix =
-          new (zone) RegExpAtom(atom->data().SubVector(0, prefix_length));
+      RegExpAtom* prefix = new (zone) RegExpAtom(
+          atom->data().SubVector(0, prefix_length), read_direction());
       ZoneList<RegExpTree*>* pair = new (zone) ZoneList<RegExpTree*>(2, zone);
       pair->Add(prefix, zone);
       ZoneList<RegExpTree*>* suffixes =
           new (zone) ZoneList<RegExpTree*>(run_length, zone);
       for (int j = 0; j < run_length; j++) {
         RegExpAtom* old_atom =
             alternatives->at(j + first_with_prefix)->AsAtom();
         int len = old_atom->length();
         if (len == prefix_length) {
           suffixes->Add(new (zone) RegExpEmpty(), zone);
         } else {
           RegExpTree* suffix = new (zone) RegExpAtom(
-              old_atom->data().SubVector(prefix_length, old_atom->length()));
+              old_atom->data().SubVector(prefix_length, old_atom->length()),
+              read_direction());
           suffixes->Add(suffix, zone);
         }
       }
-      pair->Add(new (zone) RegExpDisjunction(suffixes), zone);
-      alternatives->at(write_posn++) = new (zone) RegExpAlternative(pair);
+      pair->Add(new (zone) RegExpDisjunction(suffixes, read_direction()), zone);
+      alternatives->at(write_posn++) =
+          new (zone) RegExpAlternative(pair, read_direction());
     } else {
       // Just copy any non-worthwhile alternatives.
       for (int j = first_with_prefix; j < i; j++) {
         alternatives->at(write_posn++) = alternatives->at(j);
       }
     }
   }
   alternatives->Rewind(write_posn);  // Trim end of array.
 }
 
@@ skipping 33 matching lines @@
       // Found non-trivial run of single-character alternatives.
       int run_length = i - first_in_run;
       ZoneList<CharacterRange>* ranges =
           new (zone) ZoneList<CharacterRange>(2, zone);
       for (int j = 0; j < run_length; j++) {
         RegExpAtom* old_atom = alternatives->at(j + first_in_run)->AsAtom();
         DCHECK_EQ(old_atom->length(), 1);
         ranges->Add(CharacterRange::Singleton(old_atom->data().at(0)), zone);
       }
       alternatives->at(write_posn++) =
-          new (zone) RegExpCharacterClass(ranges, false);
+          new (zone) RegExpCharacterClass(ranges, false, read_direction());
     } else {
       // Just copy any trivial alternatives.
       for (int j = first_in_run; j < i; j++) {
         alternatives->at(write_posn++) = alternatives->at(j);
       }
     }
   }
   alternatives->Rewind(write_posn);  // Trim end of array.
 }
 
@@ skipping 233 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', RegExpTree::READ_FORWARD);

[erikcorry, 2015/11/11 15:39:04]

Yes :-)

Do we have a test of $ and ^ inside lookbehind in a /m regexp?

[Yang, 2015/11/12 08:25:34]

Added a couple of tests.

+      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())
-      BackReferenceNode(RegExpCapture::StartRegister(index()),
-                        RegExpCapture::EndRegister(index()),
-                        on_success);
+  return new (compiler->zone()) BackReferenceNode(
+      RegExpCapture::StartRegister(index()),
+      RegExpCapture::EndRegister(index()), 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;
   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;
   } 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);
   }
 }
 
 
 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 (body->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 (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('*', RegExpTree::READ_FORWARD),
+        &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('*', RegExpTree::READ_FORWARD), 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