Changed RegExp parser to use a recursive data structure instead of stack-based recursion.

src/parser.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 343 matching lines @@
     }
     return list_;
   }
 
  private:
   ZoneList<T*>* list_;
   T* last_;
 };
 
 // Accumulates RegExp atoms and assertions into lists of terms and alternatives.
-class RegExpBuilder {
+class RegExpBuilder: public ZoneObject {
  public:
   RegExpBuilder();
   void AddCharacter(uc16 character);
   // "Adds" an empty expression. Does nothing except consume a
   // following quantifier
   void AddEmpty();
   void AddAtom(RegExpTree* tree);
   void AddAssertion(RegExpTree* tree);
   void NewAlternative();  // '|'
   void AddQuantifierToAtom(int min, int max, bool is_greedy);
@@ skipping 10 matching lines @@
 #ifdef DEBUG
   enum {ADD_NONE, ADD_CHAR, ADD_TERM, ADD_ASSERT, ADD_ATOM} last_added_;
 #define LAST(x) last_added_ = x;
 #else
 #define LAST(x)
 #endif
 };
 
 
 RegExpBuilder::RegExpBuilder()
-  : pending_empty_(false), characters_(NULL), terms_(), alternatives_()
+  : pending_empty_(false),
+    characters_(NULL),
+    terms_(),
+    alternatives_()
 #ifdef DEBUG
   , last_added_(ADD_NONE)
 #endif
   {}
 
 
 void RegExpBuilder::FlushCharacters() {
   pending_empty_ = false;
   if (characters_ != NULL) {
     RegExpTree* atom = new RegExpAtom(characters_->ToConstVector());
@@ skipping 181 matching lines @@
   bool simple();
   bool contains_anchor() { return contains_anchor_; }
   void set_contains_anchor() { contains_anchor_ = true; }
   int captures_started() { return captures_ == NULL ? 0 : captures_->length(); }
   int position() { return next_pos_ - 1; }
   bool failed() { return failed_; }
 
   static const int kMaxCaptures = 1 << 16;
   static const uc32 kEndMarker = (1 << 21);
  private:
+  enum SubexpressionType {
+    INITIAL,
+    CAPTURE,  // All positive values represent captures.
+    POSITIVE_LOOKAHEAD,
+    NEGATIVE_LOOKAHEAD,
+    GROUPING
+  };
+
+  struct RegExpParserState : public ZoneObject {

[Erik Corry, 2009/07/01 11:29:14]

Please make this a real object.

+    RegExpParserState(RegExpParserState* previous_state,
+                      RegExpBuilder* builder,
+                      int disjunction_capture_index,
+                      SubexpressionType group_type)
+        : previous_state(previous_state),
+          builder(builder),
+          disjunction_capture_index(disjunction_capture_index),
+          group_type(group_type) {}
+    // Linked list implementation of stack of states.
+    RegExpParserState* previous_state;
+    // Builder for the stored disjunction.
+    RegExpBuilder* builder;
+    // Stored disjunction's capture index (if any).
+    int disjunction_capture_index;
+    // Stored disjunction type (capture, look-ahead or grouping), if any.
+    SubexpressionType group_type;
+  };
 
   uc32 current() { return current_; }
   bool has_more() { return has_more_; }
   bool has_next() { return next_pos_ < in()->length(); }
   uc32 Next();
   FlatStringReader* in() { return in_; }
   void ScanForCaptures();
-  bool CaptureAvailable(int index);
   uc32 current_;
   bool has_more_;
   bool multiline_;
   int next_pos_;
   FlatStringReader* in_;
   Handle<String>* error_;
   bool simple_;
   bool contains_anchor_;
   ZoneList<RegExpCapture*>* captures_;
   bool is_scanned_for_captures_;
@@ skipping 3198 matching lines @@
   }
   // 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;
 }
 
 
-bool RegExpParser::CaptureAvailable(int index) {
-  if (captures_ == NULL) return false;
-  if (index >= captures_->length()) return false;
-  RegExpCapture* capture = captures_->at(index);
-  return capture != NULL && capture->available() == CAPTURE_AVAILABLE;
-}
-
-
 // Disjunction ::
 //   Alternative
 //   Alternative | Disjunction
 // Alternative ::
 //   [empty]
 //   Term Alternative
 // Term ::
 //   Assertion
 //   Atom
 //   Atom Quantifier
 RegExpTree* RegExpParser::ParseDisjunction() {
-  RegExpBuilder builder;
-  int capture_start_index = captures_started();
+  // Used to store current state while parsing subexpressions.
+  RegExpParserState* stored_state = NULL;

[Erik Corry, 2009/07/01 11:29:14]

If you initialize this to an initial stored state instead then you can have the
group_type live inside the stored state.  Also the disjunction_capture_index.

+  RegExpBuilder* builder = new RegExpBuilder();
+  SubexpressionType group_type = INITIAL;
+  // Index in captures array of first capture in this sub-expression, if any.
+  // Also the capture index of this sub-expression itself, if group_type
+  // is CAPTURE.
+  int disjunction_capture_index = 0;
   while (true) {
     switch (current()) {
     case kEndMarker:
-    case ')':
-      return builder.ToRegExp();
+      if (stored_state != NULL) {
+        // Inside a parenthesized group when hitting end of input.
+        ReportError(CStrVector("Unterminated group") CHECK_FAILED);
+      }
+      ASSERT_EQ(INITIAL, group_type);
+      // Parsing completed successfully.
+      return builder->ToRegExp();
+    case ')': {
+      if (stored_state == NULL) {
+        ReportError(CStrVector("Unexpected ')'") CHECK_FAILED);
+      }
+      ASSERT_NE(INITIAL, 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 = disjunction_capture_index;
+      SubexpressionType type = group_type;
+
+      // Restore previous state.
+      builder = stored_state->builder;
+      group_type = stored_state->group_type;
+      disjunction_capture_index = stored_state->disjunction_capture_index;
+      stored_state = stored_state->previous_state;
+
+      // Build result of subexpression.
+      if (type == CAPTURE) {
+        RegExpCapture* capture = new RegExpCapture(body, capture_index);
+        captures_->at(capture_index - 1) = capture;
+        body = capture;
+      } else if (type != GROUPING) {
+        ASSERT(type == POSITIVE_LOOKAHEAD || type == NEGATIVE_LOOKAHEAD);
+        bool is_positive = (type == POSITIVE_LOOKAHEAD);
+        body = new RegExpLookahead(body,
+                                   is_positive,
+                                   end_capture_index - capture_index,
+                                   capture_index);
+      }
+      builder->AddAtom(body);
+      break;
+    }
     case '|': {
       Advance();
-      builder.NewAlternative();
-      int capture_new_alt_start_index = captures_started();
-      for (int i = capture_start_index; i < capture_new_alt_start_index; i++) {
-        RegExpCapture* capture = captures_->at(i);
-        if (capture->available() == CAPTURE_AVAILABLE) {
-          capture->set_available(CAPTURE_UNREACHABLE);
-        }
-      }
-      capture_start_index = capture_new_alt_start_index;
+      builder->NewAlternative();
       continue;
     }
     case '*':
     case '+':
     case '?':
       ReportError(CStrVector("Nothing to repeat") CHECK_FAILED);
     case '^': {
       Advance();
       if (multiline_) {
-        builder.AddAssertion(
+        builder->AddAssertion(
             new RegExpAssertion(RegExpAssertion::START_OF_LINE));
       } else {
-        builder.AddAssertion(
+        builder->AddAssertion(
             new RegExpAssertion(RegExpAssertion::START_OF_INPUT));
         set_contains_anchor();
       }
       continue;
     }
     case '$': {
       Advance();
       RegExpAssertion::Type type =
           multiline_ ? RegExpAssertion::END_OF_LINE :
                        RegExpAssertion::END_OF_INPUT;
-      builder.AddAssertion(new RegExpAssertion(type));
+      builder->AddAssertion(new RegExpAssertion(type));
       continue;
     }
     case '.': {
       Advance();
       // everything except \x0a, \x0d, \u2028 and \u2029
       ZoneList<CharacterRange>* ranges = new ZoneList<CharacterRange>(2);
       CharacterRange::AddClassEscape('.', ranges);
       RegExpTree* atom = new RegExpCharacterClass(ranges, false);
-      builder.AddAtom(atom);
+      builder->AddAtom(atom);
       break;
     }
     case '(': {
-      RegExpTree* atom = ParseGroup(CHECK_FAILED);
-      builder.AddAtom(atom);
+      SubexpressionType type = CAPTURE;
+      Advance();
+      if (current() == '?') {
+        switch (Next()) {
+          case ':':
+            type = GROUPING;
+            break;
+          case '=':
+            type = POSITIVE_LOOKAHEAD;
+            break;
+          case '!':
+            type = NEGATIVE_LOOKAHEAD;
+            break;
+          default:
+            ReportError(CStrVector("Invalid group") CHECK_FAILED);
+            break;
+        }
+        Advance(2);
+      } else {
+        if (captures_ == NULL) {
+          captures_ = new ZoneList<RegExpCapture*>(2);
+        }
+        if (captures_started() >= kMaxCaptures) {
+          ReportError(CStrVector("Too many captures") CHECK_FAILED);
+        }
+        captures_->Add(NULL);
+      }
+      // Store current state and begin new disjunction parsing.
+      stored_state = new RegExpParserState(stored_state,
+                                           builder,
+                                           disjunction_capture_index,
+                                           group_type);
+      builder = new RegExpBuilder();
+      group_type = type;
+      if (type == CAPTURE) {
+        disjunction_capture_index = captures_started();
+      }
       break;
     }
     case '[': {
       RegExpTree* atom = ParseCharacterClass(CHECK_FAILED);
-      builder.AddAtom(atom);
+      builder->AddAtom(atom);
       break;
     }
     // Atom ::
     //   \ AtomEscape
     case '\\':
       switch (Next()) {
       case kEndMarker:
         ReportError(CStrVector("\\ at end of pattern") CHECK_FAILED);
       case 'b':
         Advance(2);
-        builder.AddAssertion(
+        builder->AddAssertion(
             new RegExpAssertion(RegExpAssertion::BOUNDARY));
         continue;
       case 'B':
         Advance(2);
-        builder.AddAssertion(
+        builder->AddAssertion(
             new RegExpAssertion(RegExpAssertion::NON_BOUNDARY));
         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 ZoneList<CharacterRange>(2);
         CharacterRange::AddClassEscape(c, ranges);
         RegExpTree* atom = new RegExpCharacterClass(ranges, false);
-        builder.AddAtom(atom);
+        builder->AddAtom(atom);
         goto has_read_atom;  // Avoid setting has_character_escapes_.
       }
       case '1': case '2': case '3': case '4': case '5': case '6':
       case '7': case '8': case '9': {
         int index = 0;
         if (ParseBackReferenceIndex(&index)) {
-          if (!CaptureAvailable(index - 1)) {
-            // Prepare to ignore a following quantifier
-            builder.AddEmpty();
+          RegExpCapture* capture = NULL;
+          if (captures_ != NULL && index <= captures_->length()) {
+            capture = captures_->at(index - 1);
+          }
+          if (capture == NULL) {
+            builder->AddEmpty();
             goto has_read_atom;
           }
-          RegExpCapture* capture = captures_->at(index - 1);
           RegExpTree* atom = new RegExpBackReference(capture);
-          builder.AddAtom(atom);
+          builder->AddAtom(atom);
           goto has_read_atom;  // Avoid setting has_character_escapes_.
         }
         uc32 first_digit = Next();
         if (first_digit == '8' || first_digit == '9') {
           // Treat as identity escape
-          builder.AddCharacter(first_digit);
+          builder->AddCharacter(first_digit);
           Advance(2);
           break;
         }
       }
       // FALLTHROUGH
       case '0': {
         Advance();
         uc32 octal = ParseOctalLiteral();
-        builder.AddCharacter(octal);
+        builder->AddCharacter(octal);
         break;
       }
       // ControlEscape :: one of
       //   f n r t v
       case 'f':
         Advance(2);
-        builder.AddCharacter('\f');
+        builder->AddCharacter('\f');
         break;
       case 'n':
         Advance(2);
-        builder.AddCharacter('\n');
+        builder->AddCharacter('\n');
         break;
       case 'r':
         Advance(2);
-        builder.AddCharacter('\r');
+        builder->AddCharacter('\r');
         break;
       case 't':
         Advance(2);
-        builder.AddCharacter('\t');
+        builder->AddCharacter('\t');
         break;
       case 'v':
         Advance(2);
-        builder.AddCharacter('\v');
+        builder->AddCharacter('\v');
         break;
       case 'c': {
         Advance(2);
         uc32 control = ParseControlLetterEscape();
-        builder.AddCharacter(control);
+        builder->AddCharacter(control);
         break;
       }
       case 'x': {
         Advance(2);
         uc32 value;
         if (ParseHexEscape(2, &value)) {
-          builder.AddCharacter(value);
+          builder->AddCharacter(value);
         } else {
-          builder.AddCharacter('x');
+          builder->AddCharacter('x');
         }
         break;
       }
       case 'u': {
         Advance(2);
         uc32 value;
         if (ParseHexEscape(4, &value)) {
-          builder.AddCharacter(value);
+          builder->AddCharacter(value);
         } else {
-          builder.AddCharacter('u');
+          builder->AddCharacter('u');
         }
         break;
       }
       default:
         // Identity escape.
-        builder.AddCharacter(Next());
+        builder->AddCharacter(Next());
         Advance(2);
         break;
       }
       break;
     case '{': {
       int dummy;
       if (ParseIntervalQuantifier(&dummy, &dummy)) {
         ReportError(CStrVector("Nothing to repeat") CHECK_FAILED);
       }
       // fallthrough
     }
     default:
-      builder.AddCharacter(current());
+      builder->AddCharacter(current());
       Advance();
       break;
     }  // end switch(current())
 
    has_read_atom:
     int min;
     int max;
     switch (current()) {
     // QuantifierPrefix ::
     //   *
@@ skipping 26 matching lines @@
         continue;
       }
     default:
       continue;
     }
     bool is_greedy = true;
     if (current() == '?') {
       is_greedy = false;
       Advance();
     }
-    builder.AddQuantifierToAtom(min, max, is_greedy);
+    builder->AddQuantifierToAtom(min, max, is_greedy);
   }
 }
 
 class SourceCharacter {
  public:
   static bool Is(uc32 c) {
     switch (c) {
       // case ']': case '}':
       // In spidermonkey and jsc these are treated as source characters
       // so we do too.
@@ skipping 290 matching lines @@
       // by the ECMAScript specification.
       uc32 result = current();
       Advance();
       return result;
     }
   }
   return 0;
 }
 
 
-RegExpTree* RegExpParser::ParseGroup() {
-  ASSERT_EQ(current(), '(');
-  char type = '(';
-  Advance();
-  if (current() == '?') {
-    switch (Next()) {
-      case ':': case '=': case '!':
-        type = Next();
-        Advance(2);
-        break;
-      default:
-        ReportError(CStrVector("Invalid group") CHECK_FAILED);
-        break;
-    }
-  } else {
-    if (captures_ == NULL) {
-      captures_ = new ZoneList<RegExpCapture*>(2);
-    }
-    if (captures_started() >= kMaxCaptures) {
-      ReportError(CStrVector("Too many captures") CHECK_FAILED);
-    }
-    captures_->Add(NULL);
-  }
-  int capture_index = captures_started();
-  RegExpTree* body = ParseDisjunction(CHECK_FAILED);
-  if (current() != ')') {
-    ReportError(CStrVector("Unterminated group") CHECK_FAILED);
-  }
-  Advance();
-
-  int end_capture_index = captures_started();
-  if (type == '!') {
-    // Captures inside a negative lookahead are never available outside it.
-    for (int i = capture_index; i < end_capture_index; i++) {
-      RegExpCapture* capture = captures_->at(i);
-      ASSERT(capture != NULL);
-      capture->set_available(CAPTURE_PERMANENTLY_UNREACHABLE);
-    }
-  } else {
-    // Captures temporarily unavailable because they are in different
-    // alternatives are all available after the disjunction.
-    for (int i = capture_index; i < end_capture_index; i++) {
-      RegExpCapture* capture = captures_->at(i);
-      ASSERT(capture != NULL);
-      if (capture->available() == CAPTURE_UNREACHABLE) {
-        capture->set_available(CAPTURE_AVAILABLE);
-      }
-    }
-  }
-
-  if (type == '(') {
-    RegExpCapture* capture = new RegExpCapture(body, capture_index);
-    captures_->at(capture_index - 1) = capture;
-    return capture;
-  } else if (type == ':') {
-    return body;
-  } else {
-    ASSERT(type == '=' || type == '!');
-    bool is_positive = (type == '=');
-    return new RegExpLookahead(body,
-                               is_positive,
-                               end_capture_index - capture_index,
-                               capture_index);
-  }
-}
-
-
 CharacterRange RegExpParser::ParseClassAtom(uc16* char_class) {
   ASSERT_EQ(0, *char_class);
   uc32 first = current();
   if (first == '\\') {
     switch (Next()) {
       case 'w': case 'W': case 'd': case 'D': case 's': case 'S': {
         *char_class = Next();
         Advance(2);
         return CharacterRange::Singleton(0);  // Return dummy value.
       }
@@ skipping 184 matching lines @@
                        start_position,
                        is_expression);
   return result;
 }
 
 
 #undef NEW
 
 
 } }  // namespace v8::internal