Add back references. Since "back references" is two words...

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 497 matching lines @@
   // must not be 'b' or 'B' since they are usually handle specially.
   uc32 ParseClassCharacterEscape(bool* ok);
 
   // Checks whether the following is a length-digit hexadecimal number,
   // and sets the value if it is.
   bool ParseHexEscape(int length, uc32* value);
 
   uc32 ParseControlLetterEscape(bool* ok);
   uc32 ParseOctalLiteral();
 
-  // Tries to parse the input as a backreference.  If successful it
+  // Tries to parse the input as a back reference.  If successful it
   // stores the result in the output parameter and returns true.  If
   // it fails it will push back the characters read so the same characters
   // can be reparsed.
-  bool ParseBackreferenceIndex(int* index_out);
+  bool ParseBackReferenceIndex(int* index_out);
 
   CharacterRange ParseClassAtom(bool* is_char_class,
                                 ZoneList<CharacterRange>* ranges,
                                 bool* ok);
   RegExpTree* ReportError(Vector<const char> message, bool* ok);
   void Advance();
   void Advance(int dist);
   void Reset(int pos);
 
   bool HasCharacterEscapes();
 
   int captures_started() { return captures_ == NULL ? 0 : captures_->length(); }
   int position() { return next_pos_ - 1; }
 
   static const uc32 kEndMarker = (1 << 21);
  private:
   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_mode_;
   int next_pos_;
   FlatStringReader* in_;
   Handle<String>* error_;
   bool has_character_escapes_;
+  bool is_scanned_for_captures_;
   ZoneList<RegExpCapture*>* captures_;
+  int capture_count_;

[Christian Plesner Hansen, 2008/11/21 11:16:39]

This name could be misleading but I can't think of a better one.

 };
 
 
 // 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 2933 matching lines @@
 RegExpParser::RegExpParser(FlatStringReader* in,
                            Handle<String>* error,
                            bool multiline_mode)
   : current_(kEndMarker),
     has_more_(true),
     multiline_mode_(multiline_mode),
     next_pos_(0),
     in_(in),
     error_(error),
     has_character_escapes_(false),
-    captures_(NULL) {
+    is_scanned_for_captures_(false),
+    captures_(NULL),
+    capture_count_(0) {
   Advance(1);
 }
 
 
 uc32 RegExpParser::Next() {
   if (has_next()) {
     return in()->Get(next_pos_);
   } else {
     return kEndMarker;
   }
@@ skipping 41 matching lines @@
 //   Disjunction
 RegExpTree* RegExpParser::ParsePattern(bool* ok) {
   RegExpTree* result = ParseDisjunction(CHECK_OK);
   if (has_more()) {
     ReportError(CStrVector("Unmatched ')'"), CHECK_OK);
   }
   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
@@ skipping 83 matching lines @@
         Advance(2);
         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)) {
-          RegExpCapture* capture = captures_->at(index - 1);
-          if (capture == NULL || capture->available() != CAPTURE_AVAILABLE) {
+        if (ParseBackReferenceIndex(&index)) {
+          if (!CaptureAvailable(index - 1)) {
             // Prepare to ignore a following quantifier
             builder.AddEmpty();
             goto has_read_atom;
           }
-          RegExpTree* atom = new RegExpBackreference(capture);
+          RegExpCapture* capture = captures_->at(index - 1);
+          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 149 matching lines @@
     case 's': case 'S':
     case 'w': case 'W':
       return true;
     default:
       return false;
   }
 }
 #endif
 
 
-bool RegExpParser::ParseBackreferenceIndex(int* index_out) {
+// 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() {
+  int n;
+  while ((n = current()) != kEndMarker) {
+    Advance();
+    switch (n) {
+      case '\\':
+        Advance();
+        break;
+      case '[': {
+        int c;
+        while ((c = current()) != kEndMarker) {
+          Advance();
+          if (c == '\\') {
+            Advance();
+          } else {
+            if (c == ']') break;
+          }
+        }
+        break;
+      }
+      case '(':
+        if (current() != '?') capture_count_++;
+        break;
+    }
+  }
+  is_scanned_for_captures_ = true;
+}
+
+
+bool RegExpParser::ParseBackReferenceIndex(int* index_out) {
   ASSERT_EQ('\\', current());
   ASSERT('1' <= Next() && Next() <= '9');
   // 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_ == NULL)
-    return false;
+  if (!is_scanned_for_captures_) {
+    int saved_position = position();
+    ScanForCaptures();
+    Reset(saved_position);
+  }
+  if (capture_count_ == 0) return false;
   int start = position();
   int value = Next() - '0';
-  if (value > captures_->length())
-    return false;
+  if (value > capture_count_) return false;
   Advance(2);
   while (true) {
     uc32 c = current();
     if (IsDecimalDigit(c)) {
       value = 10 * value + (c - '0');
-      if (value > captures_->length()) {
+      if (value > capture_count_) {
         Reset(start);
         return false;
       }
       Advance();
     } else {
       break;
     }
   }
   *index_out = value;
   return true;
@@ skipping 184 matching lines @@
         break;
       default:
         ReportError(CStrVector("Invalid group"), CHECK_OK);
         break;
     }
   } else {
     if (captures_ == NULL) {
       captures_ = new ZoneList<RegExpCapture*>(2);
     }
     captures_->Add(NULL);
+    if (!is_scanned_for_captures_) capture_count_++;
   }
   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 == '!') {
@@ skipping 222 matching lines @@
                        start_position,
                        is_expression);
   return result;
 }
 
 
 #undef NEW
 
 
 } }  // namespace v8::internal