Experimental support for RegExp lookbehind.

src/parser.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/parser.h"
 
 #include "src/api.h"
 #include "src/ast.h"
 #include "src/ast-literal-reindexer.h"
 #include "src/bailout-reason.h"
@@ skipping 76 matching lines @@
   set_stack_limit(isolate_->stack_guard()->real_climit());
   set_unicode_cache(isolate_->unicode_cache());
   set_script(script);
 
   if (script->type() == Script::TYPE_NATIVE) {
     set_native();
   }
 }
 
 
-RegExpBuilder::RegExpBuilder(Zone* zone)
+RegExpBuilder::RegExpBuilder(Zone* zone,
+                             RegExpTree::ReadDirection read_direction)
     : zone_(zone),
       pending_empty_(false),
       characters_(NULL),
       terms_(),
-      alternatives_()
+      alternatives_(),
+      read_direction_(read_direction)
 #ifdef DEBUG
     , last_added_(ADD_NONE)
 #endif
   {}
 
 
 void RegExpBuilder::FlushCharacters() {
   pending_empty_ = false;
   if (characters_ != NULL) {
-    RegExpTree* atom = new(zone()) RegExpAtom(characters_->ToConstVector());
+    RegExpTree* atom =
+        new (zone()) RegExpAtom(characters_->ToConstVector(), read_direction_);
     characters_ = NULL;
     text_.Add(atom, zone());
     LAST(ADD_ATOM);
   }
 }
 
 
 void RegExpBuilder::FlushText() {
   FlushCharacters();
   int num_text = text_.length();
   if (num_text == 0) {
     return;
   } else if (num_text == 1) {
     terms_.Add(text_.last(), zone());
   } else {
-    RegExpText* text = new(zone()) RegExpText(zone());
+    RegExpText* text = new (zone()) RegExpText(zone(), read_direction_);
     for (int i = 0; i < num_text; i++)
       text_.Get(i)->AppendToText(text, zone());
     terms_.Add(text, zone());
   }
   text_.Clear();
 }
 
 
 void RegExpBuilder::AddCharacter(uc16 c) {
   pending_empty_ = false;
@@ skipping 40 matching lines @@
 
 void RegExpBuilder::FlushTerms() {
   FlushText();
   int num_terms = terms_.length();
   RegExpTree* alternative;
   if (num_terms == 0) {
     alternative = new (zone()) RegExpEmpty();
   } else if (num_terms == 1) {
     alternative = terms_.last();
   } else {
-    alternative = new(zone()) RegExpAlternative(terms_.GetList(zone()));
+    alternative =
+        new (zone()) RegExpAlternative(terms_.GetList(zone()), read_direction_);
   }
   alternatives_.Add(alternative, zone());
   terms_.Clear();
   LAST(ADD_NONE);
 }
 
 
 RegExpTree* RegExpBuilder::ToRegExp() {
   FlushTerms();
   int num_alternatives = alternatives_.length();
   if (num_alternatives == 0) return new (zone()) RegExpEmpty();
   if (num_alternatives == 1) return alternatives_.last();
-  return new(zone()) RegExpDisjunction(alternatives_.GetList(zone()));
+  return new (zone())
+      RegExpDisjunction(alternatives_.GetList(zone()), read_direction_);
 }
 
 
 void RegExpBuilder::AddQuantifierToAtom(
     int min, int max, RegExpQuantifier::QuantifierType quantifier_type) {
   if (pending_empty_) {
     pending_empty_ = false;
     return;
   }
   RegExpTree* atom;
   if (characters_ != NULL) {
     DCHECK(last_added_ == ADD_CHAR);
     // Last atom was character.
     Vector<const uc16> char_vector = characters_->ToConstVector();
     int num_chars = char_vector.length();
     if (num_chars > 1) {
       Vector<const uc16> prefix = char_vector.SubVector(0, num_chars - 1);
-      text_.Add(new(zone()) RegExpAtom(prefix), zone());
+      text_.Add(new (zone()) RegExpAtom(prefix, read_direction_), zone());
       char_vector = char_vector.SubVector(num_chars - 1, num_chars);
     }
     characters_ = NULL;
-    atom = new(zone()) RegExpAtom(char_vector);
+    atom = new (zone()) RegExpAtom(char_vector, read_direction_);
     FlushText();
   } else if (text_.length() > 0) {
     DCHECK(last_added_ == ADD_ATOM);
     atom = text_.RemoveLast();
     FlushText();
   } else if (terms_.length() > 0) {
     DCHECK(last_added_ == ADD_ATOM);
     atom = terms_.RemoveLast();
     if (atom->max_match() == 0) {
       // Guaranteed to only match an empty string.
       LAST(ADD_TERM);
       if (min == 0) {
         return;
       }
       terms_.Add(atom, zone());
       return;
     }
   } else {
     // Only call immediately after adding an atom or character!
     UNREACHABLE();
     return;
   }
-  terms_.Add(
-      new(zone()) RegExpQuantifier(min, max, quantifier_type, atom), zone());
+  terms_.Add(new (zone()) RegExpQuantifier(min, max, quantifier_type, atom,
+                                           read_direction_),
+             zone());
   LAST(ADD_TERM);
 }
 
 
 FunctionEntry ParseData::GetFunctionEntry(int start) {
   // The current pre-data entry must be a FunctionEntry with the given
   // start position.
   if ((function_index_ + FunctionEntry::kSize <= Length()) &&
       (static_cast<int>(Data()[function_index_]) == start)) {
     int index = function_index_;
@@ skipping 4955 matching lines @@
 RegExpParser::RegExpParser(FlatStringReader* in, Handle<String>* error,
                            bool multiline, bool unicode, Isolate* isolate,
                            Zone* zone)
     : isolate_(isolate),
       zone_(zone),
       error_(error),
       captures_(NULL),
       in_(in),
       current_(kEndMarker),
       next_pos_(0),
+      captures_started_(0),
       capture_count_(0),
       has_more_(true),
       multiline_(multiline),
       unicode_(unicode),
       simple_(false),
       contains_anchor_(false),
       is_scanned_for_captures_(false),
       failed_(false) {
   Advance();
 }
@@ skipping 61 matching lines @@
   current_ = kEndMarker;
   next_pos_ = in()->length();
   return NULL;
 }
 
 
 // Pattern ::
 //   Disjunction
 RegExpTree* RegExpParser::ParsePattern() {
   RegExpTree* result = ParseDisjunction(CHECK_FAILED);
+
   DCHECK(!has_more());
   // If the result of parsing is a literal string atom, and it has the
   // same length as the input, then the atom is identical to the input.
   if (result->IsAtom() && result->AsAtom()->length() == in()->length()) {
     simple_ = true;
   }
   return result;
 }
 
 
 // Disjunction ::
 //   Alternative
 //   Alternative | Disjunction
 // Alternative ::
 //   [empty]
 //   Term Alternative
 // Term ::
 //   Assertion
 //   Atom
 //   Atom Quantifier
 RegExpTree* RegExpParser::ParseDisjunction() {
   // Used to store current state while parsing subexpressions.
-  RegExpParserState initial_state(NULL, INITIAL, 0, zone());
-  RegExpParserState* stored_state = &initial_state;
+  RegExpParserState initial_state(NULL, INITIAL, RegExpTree::READ_FORWARD, 0,
+                                  zone());
+  RegExpParserState* state = &initial_state;
   // Cache the builder in a local variable for quick access.
   RegExpBuilder* builder = initial_state.builder();
   while (true) {
     switch (current()) {
     case kEndMarker:
-      if (stored_state->IsSubexpression()) {
+      if (state->IsSubexpression()) {
         // Inside a parenthesized group when hitting end of input.
         ReportError(CStrVector("Unterminated group") CHECK_FAILED);
       }
-      DCHECK_EQ(INITIAL, stored_state->group_type());
+      DCHECK_EQ(INITIAL, state->group_type());
       // Parsing completed successfully.
       return builder->ToRegExp();
     case ')': {
-      if (!stored_state->IsSubexpression()) {
+      if (!state->IsSubexpression()) {
         ReportError(CStrVector("Unmatched ')'") CHECK_FAILED);
       }
-      DCHECK_NE(INITIAL, stored_state->group_type());
+      DCHECK_NE(INITIAL, state->group_type());
 
       Advance();
       // End disjunction parsing and convert builder content to new single
       // regexp atom.
       RegExpTree* body = builder->ToRegExp();
 
-      int end_capture_index = captures_started();
+      int end_capture_index = captures_started_;
 
-      int capture_index = stored_state->capture_index();
-      SubexpressionType group_type = stored_state->group_type();
-
-      // Restore previous state.
-      stored_state = stored_state->previous_state();
-      builder = stored_state->builder();
+      int capture_index = state->capture_index();
+      SubexpressionType group_type = state->group_type();
 
       // Build result of subexpression.
       if (group_type == CAPTURE) {
-        RegExpCapture* capture = new(zone()) RegExpCapture(body, capture_index);
-        captures_->at(capture_index - 1) = capture;
+        RegExpCapture* capture = GetCapture(capture_index);
+        capture->set_body(body);
+        capture->set_read_direction(state->read_direction());
         body = capture;
       } else if (group_type != GROUPING) {
         DCHECK(group_type == POSITIVE_LOOKAHEAD ||
                group_type == NEGATIVE_LOOKAHEAD);
         bool is_positive = (group_type == POSITIVE_LOOKAHEAD);
-        body = new(zone()) RegExpLookahead(body,
-                                   is_positive,
-                                   end_capture_index - capture_index,
-                                   capture_index);
+        body = new (zone()) RegExpLookaround(
+            body, is_positive, end_capture_index - capture_index, capture_index,
+            state->read_direction());
       }
+
+      // Restore previous state.
+      state = state->previous_state();
+      builder = state->builder();
+
       builder->AddAtom(body);
       // For compatability with JSC and ES3, we allow quantifiers after
       // lookaheads, and break in all cases.
       break;
     }
     case '|': {
       Advance();
       builder->NewAlternative();
       continue;
     }
     case '*':
     case '+':
     case '?':
       return ReportError(CStrVector("Nothing to repeat"));
     case '^': {
       Advance();
       if (multiline_) {
-        builder->AddAssertion(
-            new(zone()) RegExpAssertion(RegExpAssertion::START_OF_LINE));
+        builder->AddAssertion(new (zone()) RegExpAssertion(
+            RegExpAssertion::START_OF_LINE, state->read_direction()));
       } else {
-        builder->AddAssertion(
-            new(zone()) RegExpAssertion(RegExpAssertion::START_OF_INPUT));
+        builder->AddAssertion(new (zone()) RegExpAssertion(
+            RegExpAssertion::START_OF_INPUT, state->read_direction()));
         set_contains_anchor();
       }
       continue;
     }
     case '$': {
       Advance();
       RegExpAssertion::AssertionType assertion_type =
           multiline_ ? RegExpAssertion::END_OF_LINE :
                        RegExpAssertion::END_OF_INPUT;
-      builder->AddAssertion(new(zone()) RegExpAssertion(assertion_type));
+      builder->AddAssertion(new (zone()) RegExpAssertion(
+          assertion_type, state->read_direction()));
       continue;
     }
     case '.': {
       Advance();
       // everything except \x0a, \x0d, \u2028 and \u2029
       ZoneList<CharacterRange>* ranges =
           new(zone()) ZoneList<CharacterRange>(2, zone());
       CharacterRange::AddClassEscape('.', ranges, zone());
-      RegExpTree* atom = new(zone()) RegExpCharacterClass(ranges, false);
+      RegExpTree* atom = new (zone())
+          RegExpCharacterClass(ranges, false, state->read_direction());
       builder->AddAtom(atom);
       break;
     }
     case '(': {
       SubexpressionType subexpr_type = CAPTURE;
+      RegExpTree::ReadDirection read_direction = state->read_direction();
       Advance();
       if (current() == '?') {
         switch (Next()) {
           case ':':
             subexpr_type = GROUPING;
             break;
           case '=':
+            read_direction = RegExpTree::READ_FORWARD;
             subexpr_type = POSITIVE_LOOKAHEAD;
             break;
           case '!':
+            read_direction = RegExpTree::READ_FORWARD;
             subexpr_type = NEGATIVE_LOOKAHEAD;
             break;
+          case '<':
+            if (FLAG_harmony_regexp_lookbehind) {
+              Advance();
+              read_direction = RegExpTree::READ_BACKWARD;
+              if (Next() == '=') {
+                subexpr_type = POSITIVE_LOOKAHEAD;
+                break;
+              } else if (Next() == '!') {
+                subexpr_type = NEGATIVE_LOOKAHEAD;
+                break;
+              }
+            }
+          // Fall through.
           default:
             ReportError(CStrVector("Invalid group") CHECK_FAILED);
             break;
         }
         Advance(2);
       } else {
-        if (captures_ == NULL) {
-          captures_ = new(zone()) ZoneList<RegExpCapture*>(2, zone());
-        }
-        if (captures_started() >= kMaxCaptures) {
+        if (captures_started_ >= kMaxCaptures) {
           ReportError(CStrVector("Too many captures") CHECK_FAILED);
         }
-        captures_->Add(NULL, zone());
+        captures_started_++;
       }
       // Store current state and begin new disjunction parsing.
-      stored_state = new(zone()) RegExpParserState(stored_state, subexpr_type,
-                                                   captures_started(), zone());
-      builder = stored_state->builder();
+      state = new (zone()) RegExpParserState(
+          state, subexpr_type, read_direction, captures_started_, zone());
+      builder = state->builder();
       continue;
     }
     case '[': {
-      RegExpTree* atom = ParseCharacterClass(CHECK_FAILED);
+      RegExpTree* atom =
+          ParseCharacterClass(state->read_direction() CHECK_FAILED);
       builder->AddAtom(atom);
       break;
     }
     // Atom ::
     //   \ AtomEscape
     case '\\':
       switch (Next()) {
       case kEndMarker:
         return ReportError(CStrVector("\\ at end of pattern"));
       case 'b':
         Advance(2);
-        builder->AddAssertion(
-            new(zone()) RegExpAssertion(RegExpAssertion::BOUNDARY));
+        builder->AddAssertion(new (zone()) RegExpAssertion(
+            RegExpAssertion::BOUNDARY, state->read_direction()));
         continue;
       case 'B':
         Advance(2);
-        builder->AddAssertion(
-            new(zone()) RegExpAssertion(RegExpAssertion::NON_BOUNDARY));
+        builder->AddAssertion(new (zone()) RegExpAssertion(
+            RegExpAssertion::NON_BOUNDARY, state->read_direction()));
         continue;
       // AtomEscape ::
       //   CharacterClassEscape
       //
       // CharacterClassEscape :: one of
       //   d D s S w W
       case 'd': case 'D': case 's': case 'S': case 'w': case 'W': {
         uc32 c = Next();
         Advance(2);
         ZoneList<CharacterRange>* ranges =
             new(zone()) ZoneList<CharacterRange>(2, zone());
         CharacterRange::AddClassEscape(c, ranges, zone());
-        RegExpTree* atom = new(zone()) RegExpCharacterClass(ranges, false);
+        RegExpTree* atom = new (zone())
+            RegExpCharacterClass(ranges, false, state->read_direction());
         builder->AddAtom(atom);
         break;
       }
       case '1': case '2': case '3': case '4': case '5': case '6':
       case '7': case '8': case '9': {
         int index = 0;
         if (ParseBackReferenceIndex(&index)) {
-          RegExpCapture* capture = NULL;
-          if (captures_ != NULL && index <= captures_->length()) {
-            capture = captures_->at(index - 1);
-          }
-          if (capture == NULL) {
-            builder->AddEmpty();
-            break;
-          }
-          RegExpTree* atom = new(zone()) RegExpBackReference(capture);
+          RegExpCapture* capture = GetCapture(index);
+          RegExpTree* atom = new (zone())
+              RegExpBackReference(capture, state->read_direction());
           builder->AddAtom(atom);
           break;
         }
         uc32 first_digit = Next();
         if (first_digit == '8' || first_digit == '9') {
           // If the 'u' flag is present, only syntax characters can be escaped,
           // no other identity escapes are allowed. If the 'u' flag is not
           // present, all identity escapes are allowed.
           if (!FLAG_harmony_unicode_regexps || !unicode_) {
             builder->AddCharacter(first_digit);
@@ skipping 173 matching lines @@
 
 
 // In order to know whether an escape is a backreference or not we have to scan
 // the entire regexp and find the number of capturing parentheses.  However we
 // don't want to scan the regexp twice unless it is necessary.  This mini-parser
 // is called when needed.  It can see the difference between capturing and
 // noncapturing parentheses and can skip character classes and backslash-escaped
 // characters.
 void RegExpParser::ScanForCaptures() {
   // Start with captures started previous to current position
-  int capture_count = captures_started();
+  int capture_count = captures_started_;
   // Add count of captures after this position.
   int n;
   while ((n = current()) != kEndMarker) {
     Advance();
     switch (n) {
       case '\\':
         Advance();
         break;
       case '[': {
         int c;
@@ skipping 31 matching lines @@
       value = 10 * value + (c - '0');
       if (value > kMaxCaptures) {
         Reset(start);
         return false;
       }
       Advance();
     } else {
       break;
     }
   }
-  if (value > captures_started()) {
+  if (value > captures_started_) {
     if (!is_scanned_for_captures_) {
       int saved_position = position();
       ScanForCaptures();
       Reset(saved_position);
     }
     if (value > capture_count_) {
       Reset(start);
       return false;
     }
   }
   *index_out = value;
   return true;
 }
 
 
+RegExpCapture* RegExpParser::GetCapture(int index) {
+  // The index for the capture groups are one-based. Its index in the list is
+  // zero-based.
+  int know_captures =
+      is_scanned_for_captures_ ? capture_count_ : captures_started_;
+  DCHECK(index <= know_captures);
+  if (captures_ == NULL) {
+    captures_ = new (zone()) ZoneList<RegExpCapture*>(know_captures, zone());
+  }
+  while (captures_->length() < know_captures) {
+    captures_->Add(new (zone()) RegExpCapture(captures_->length() + 1), zone());
+  }
+  return captures_->at(index - 1);
+}
+
+
 // QuantifierPrefix ::
 //   { DecimalDigits }
 //   { DecimalDigits , }
 //   { DecimalDigits , DecimalDigits }
 //
 // Returns true if parsing succeeds, and set the min_out and max_out
 // values. Values are truncated to RegExpTree::kInfinity if they overflow.
 bool RegExpParser::ParseIntervalQuantifier(int* min_out, int* max_out) {
   DCHECK_EQ(current(), '{');
   int start = position();
@@ skipping 259 matching lines @@
                                     CharacterRange range,
                                     Zone* zone) {
   if (char_class != kNoCharClass) {
     CharacterRange::AddClassEscape(char_class, ranges, zone);
   } else {
     ranges->Add(range, zone);
   }
 }
 
 
-RegExpTree* RegExpParser::ParseCharacterClass() {
+RegExpTree* RegExpParser::ParseCharacterClass(
+    RegExpTree::ReadDirection read_direction) {
   static const char* kUnterminated = "Unterminated character class";
   static const char* kRangeOutOfOrder = "Range out of order in character class";
 
   DCHECK_EQ(current(), '[');
   Advance();
   bool is_negated = false;
   if (current() == '^') {
     is_negated = true;
     Advance();
   }
@@ skipping 31 matching lines @@
     }
   }
   if (!has_more()) {
     return ReportError(CStrVector(kUnterminated) CHECK_FAILED);
   }
   Advance();
   if (ranges->length() == 0) {
     ranges->Add(CharacterRange::Everything(), zone());
     is_negated = !is_negated;
   }
-  return new(zone()) RegExpCharacterClass(ranges, is_negated);
+  return new (zone()) RegExpCharacterClass(ranges, is_negated, read_direction);
 }
 
 
 // ----------------------------------------------------------------------------
 // The Parser interface.
 
 bool RegExpParser::ParseRegExp(Isolate* isolate, Zone* zone,
                                FlatStringReader* input, bool multiline,
                                bool unicode, RegExpCompileData* result) {
   DCHECK(result != NULL);
@@ skipping 348 matching lines @@
 }
 
 
 void Parser::RaiseLanguageMode(LanguageMode mode) {
   SetLanguageMode(scope_,
                   static_cast<LanguageMode>(scope_->language_mode() | mode));
 }
 
 }  // namespace internal
 }  // namespace v8