* Update to RegExp parsing and AST.

regexp2000/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 273 matching lines @@
  private:
   ZoneList<T*>* list_;
   T* last_;
 };
 
 // Accumulates RegExp atoms and assertions into lists of terms and alternatives.
 class RegExpBuilder {
  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);
   RegExpTree* ToRegExp();
  private:
   void FlushCharacters();
   bool FlushTerms();
+  bool pending_empty_;
   ZoneList<uc16>* characters_;
   BufferedZoneList<RegExpTree, 2> terms_;
   BufferedZoneList<RegExpTree, 2> alternatives_;
 #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() : characters_(NULL), terms_(), alternatives_()
+RegExpBuilder::RegExpBuilder()
+  : 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());
     characters_ = NULL;
     terms_.Add(atom);
     LAST(ADD_ATOM);
   }
 }
 
 
 void RegExpBuilder::AddCharacter(uc16 c) {
+  pending_empty_ = false;
   if (characters_ == NULL) {
     characters_ = new ZoneList<uc16>(4);
   }
   characters_->Add(c);
   LAST(ADD_CHAR);
 }
 
 
+void RegExpBuilder::AddEmpty() {
+  pending_empty_ = true;
+}
+
+
 void RegExpBuilder::AddAtom(RegExpTree* atom) {
   FlushCharacters();
   terms_.Add(atom);
   LAST(ADD_ATOM);
 }
 
 
 void RegExpBuilder::AddAssertion(RegExpTree* assert) {
   FlushCharacters();
   terms_.Add(assert);
@@ skipping 34 matching lines @@
     return RegExpEmpty::GetInstance();
   }
   if (num_alternatives == 1) {
     return alternatives_.last();
   }
   return new RegExpDisjunction(alternatives_.GetList());
 }
 
 
 void RegExpBuilder::AddQuantifierToAtom(int min, int max, bool is_greedy) {
+  if (pending_empty_) {
+    pending_empty_ = false;
+    return;
+  }
   RegExpTree* atom;
   if (characters_ != NULL) {
     ASSERT(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);
       terms_.Add(new RegExpAtom(prefix));
       char_vector = char_vector.SubVector(num_chars - 1, num_chars);
@@ skipping 54 matching lines @@
   // on the input stream. After pushing it back, it becomes the character
   // returned by current(). There is a limited amount of push-back buffer.
   // A function using PushBack should check that it doesn't push back more
   // than kMaxPushback characters, and it should not push back more characters
   // than it has read.
   void PushBack(uc32 character);
   bool CanPushBack();
 
   bool HasCharacterEscapes();
 
-  int captures_started() { return captures_started_; }
+  int captures_started() { return captures_ == NULL ? 0 : captures_->length(); }
 
   static const uc32 kEndMarker = unibrow::Utf8::kBadChar;
  private:
   uc32 current() { return current_; }
   uc32 next() { return next_; }
   bool has_more() { return has_more_; }
   bool has_next() { return has_next_; }
   unibrow::CharacterStream* in() { return in_; }
   uc32 current_;
   uc32 next_;
   bool has_more_;
   bool has_next_;
   bool multiline_mode_;
-  int captures_started_;
   unibrow::CharacterStream* in_;
   Handle<String>* error_;
   static const int kMaxPushback = 5;
   int pushback_count_;
   uc32 pushback_buffer_[kMaxPushback];
   bool has_character_escapes_;
+  ZoneList<RegExpCapture*>* captures_;
 };
 
 
 // A temporary scope stores information during parsing, just like
 // a plain scope.  However, temporary scopes are not kept around
 // after parsing or referenced by syntax trees so they can be stack-
 // allocated and hence used by the pre-parser.
 class TemporaryScope BASE_EMBEDDED {
  public:
   explicit TemporaryScope(Parser* parser);
@@ skipping 2931 matching lines @@
 
 
 RegExpParser::RegExpParser(unibrow::CharacterStream* in,
                            Handle<String>* error,
                            bool multiline_mode)
   : current_(kEndMarker),
     next_(kEndMarker),
     has_more_(true),
     has_next_(true),
     multiline_mode_(multiline_mode),
-    captures_started_(0),
     in_(in),
     error_(error),
     pushback_count_(0),
-    has_character_escapes_(false) {
+    has_character_escapes_(false),
+    captures_(NULL) {
   Advance(2);
 }
 
 
 void RegExpParser::Advance() {
   current_ = next_;
   has_more_ = has_next_;
   if (pushback_count_ > 0) {
     pushback_count_--;
     next_ = pushback_buffer_[pushback_count_];
@@ skipping 61 matching lines @@
 //   Alternative | Disjunction
 // Alternative ::
 //   [empty]
 //   Term Alternative
 // Term ::
 //   Assertion
 //   Atom
 //   Atom Quantifier
 RegExpTree* RegExpParser::ParseDisjunction(bool* ok) {
   RegExpBuilder builder;
+  int capture_start_index = captures_started();
   while (true) {
     switch (current()) {
     case kEndMarker:
     case ')':
       return builder.ToRegExp();
-    case '|':
+    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;
       continue;
+    }
     case '*':
     case '+':
     case '?':
     case '{':
       ReportError(CStrVector("Nothing to repeat."), CHECK_OK);
     case '^': {
       Advance();
       RegExpAssertion::Type type =
           multiline_mode_ ? RegExpAssertion::START_OF_LINE :
                             RegExpAssertion::START_OF_INPUT;
@@ skipping 54 matching lines @@
         ZoneList<CharacterRange>* ranges = new ZoneList<CharacterRange>(2);
         CharacterRange::AddClassEscape(c, ranges);
         RegExpTree* atom = new RegExpCharacterClass(ranges, false);
         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)) {
-          RegExpTree* atom = new RegExpBackreference(index);
+          RegExpCapture* capture = captures_->at(index - 1);
+          if (capture == NULL || capture->available() != CAPTURE_AVAILABLE) {
+            // Prepare to ignore a following quantifier
+            builder.AddEmpty();
+            goto has_read_atom;
+          }
+          RegExpTree* atom = new RegExpBackreference(capture);
           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);
           Advance(2);
           break;
         }
@@ skipping 148 matching lines @@
 
 bool RegExpParser::ParseBackreferenceIndex(int* index_out) {
   ASSERT_EQ('\\', current());
   ASSERT('1' <= next() && next() <= '9');
   ASSERT_EQ(0, pushback_count_);
   // Try to parse a decimal literal that is no greater than the number
   // of previously encountered left capturing parentheses.
   // This is a not according the the ECMAScript specification. According to
   // that, one must accept values up to the total number of left capturing
   // parentheses in the entire input, even if they are meaningless.
-  if (captures_started_ == 0)
+  if (captures_ == NULL)
     return false;
   int value = next() - '0';
-  if (value > captures_started_)
+  if (value > captures_->length())
     return false;
   static const int kMaxChars = kMaxPushback - 2;
   EmbeddedVector<uc32, kMaxChars> chars_seen;
   chars_seen[0] = next();
   int char_count = 1;
   Advance(2);
   while (true) {
     uc32 c = current();
     if (IsDecimalDigit(c)) {
       value = 10 * value + (c - '0');
       // To avoid reading past the end of the stack-allocated pushback
       // buffers we only read kMaxChars before giving up.
-      if (value > captures_started_ || char_count > kMaxChars) {
+      if (value > captures_->length() || char_count > kMaxChars) {
         // If we give up we have to push the characters we read back
         // onto the pushback buffer in the reverse order.
         for (int i = 0; i < char_count; i++) {
           PushBack(chars_seen[char_count - i - 1]);
         }
         PushBack('\\');
         return false;
       }
       chars_seen[char_count++] = current();
       Advance();
@@ skipping 193 matching lines @@
     switch (next()) {
       case ':': case '=': case '!':
         type = next();
         Advance(2);
         break;
       default:
         ReportError(CStrVector("Invalid group"), CHECK_OK);
         break;
     }
   } else {
-    captures_started_++;
+    if (captures_ == NULL) {
+      captures_ = new ZoneList<RegExpCapture*>(2);
+    }
+    captures_->Add(NULL);
   }
-  int capture_index = captures_started_;
+  int capture_index = captures_started();
   RegExpTree* body = ParseDisjunction(CHECK_OK);
   if (current() != ')') {
     ReportError(CStrVector("Unterminated group"), CHECK_OK);
   }
   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 == '(') {
-    return new RegExpCapture(body, capture_index);
+    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);
   }
 }
 
 
@@ skipping 58 matching lines @@
       } else {
         ranges->Add(first);
       }
     }
   }
   if (!has_more()) {
     return ReportError(CStrVector(kUnterminated), CHECK_OK);
   }
   Advance();
   if (ranges->length() == 0) {
-    return RegExpEmpty::GetInstance();
-  } else {
-    return new RegExpCharacterClass(ranges, is_negated);
+    ranges->Add(CharacterRange::Range(0, 0xffff));
+    is_negated = !is_negated;
   }
+  return new RegExpCharacterClass(ranges, is_negated);
 }
 
 
 // ----------------------------------------------------------------------------
 // The Parser interface.
 
 // MakeAST() is just a wrapper for the corresponding Parser calls
 // so we don't have to expose the entire Parser class in the .h file.
 
 static bool always_allow_natives_syntax = false;
@@ skipping 104 matching lines @@
                        start_position,
                        is_expression);
   return result;
 }
 
 
 #undef NEW
 
 
 } }  // namespace v8::internal