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 5164 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 83 matching lines @@
 //   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, RegExpLookaround::LOOKAHEAD, 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 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);
         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);
+        DCHECK(group_type == POSITIVE_LOOKAROUND ||
+               group_type == NEGATIVE_LOOKAROUND);
+        bool is_positive = (group_type == POSITIVE_LOOKAROUND);
+        body = new (zone()) RegExpLookaround(
+            body, is_positive, end_capture_index - capture_index, capture_index,
+            state->lookaround_type());
       }
+
+      // 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;
     }
@@ skipping 26 matching lines @@
       // 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);
       builder->AddAtom(atom);
       break;
     }
     case '(': {
       SubexpressionType subexpr_type = CAPTURE;
+      RegExpLookaround::Type lookaround_type = state->lookaround_type();
       Advance();
       if (current() == '?') {
         switch (Next()) {
           case ':':
             subexpr_type = GROUPING;
             break;
           case '=':
-            subexpr_type = POSITIVE_LOOKAHEAD;
+            lookaround_type = RegExpLookaround::LOOKAHEAD;
+            subexpr_type = POSITIVE_LOOKAROUND;
             break;
           case '!':
-            subexpr_type = NEGATIVE_LOOKAHEAD;
+            lookaround_type = RegExpLookaround::LOOKAHEAD;
+            subexpr_type = NEGATIVE_LOOKAROUND;
             break;
+          case '<':
+            if (FLAG_harmony_regexp_lookbehind) {
+              Advance();
+              lookaround_type = RegExpLookaround::LOOKBEHIND;
+              if (Next() == '=') {
+                subexpr_type = POSITIVE_LOOKAROUND;
+                break;
+              } else if (Next() == '!') {
+                subexpr_type = NEGATIVE_LOOKAROUND;
+                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, lookaround_type, captures_started_, zone());
+      builder = state->builder();
       continue;
     }
     case '[': {
       RegExpTree* atom = ParseCharacterClass(CHECK_FAILED);
       builder->AddAtom(atom);
       break;
     }
     // Atom ::
     //   \ AtomEscape
     case '\\':
@@ skipping 22 matching lines @@
             new(zone()) ZoneList<CharacterRange>(2, zone());
         CharacterRange::AddClassEscape(c, ranges, zone());
         RegExpTree* atom = new(zone()) RegExpCharacterClass(ranges, false);
         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 (state->IsInsideCaptureGroup(index)) {
+            // The backreference is inside the capture group it refers to.
+            // Nothing can possibly have been captured yet.
+            builder->AddEmpty();
+          } else {
+            RegExpCapture* capture = GetCapture(index);
+            RegExpTree* atom = new (zone()) RegExpBackReference(capture);
+            builder->AddAtom(atom);
           }
-          if (capture == NULL) {
-            builder->AddEmpty();
-            break;
-          }
-          RegExpTree* atom = new(zone()) RegExpBackReference(capture);
-          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);
             Advance(2);
@@ skipping 240 matching lines @@
     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);
+}
+
+
+bool RegExpParser::RegExpParserState::IsInsideCaptureGroup(int index) {
+  for (RegExpParserState* s = this; s != NULL; s = s->previous_state()) {
+    if (s->group_type() != CAPTURE) continue;
+    // Return true if we found the matching capture index.
+    if (index == s->capture_index()) return true;
+    // Abort if index is larger than what has been parsed up till this state.
+    if (index > s->capture_index()) return false;
+  }
+  return false;
+}
+
+
 // 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 311 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);
 }
 
 
 // ----------------------------------------------------------------------------
 // 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