Backreferences

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 234 matching lines @@
 
   // Parses and returns a single escaped character.  The character
   // must not be 'b' or 'B' since they are usually handle specially.
   uc32 ParseCharacterEscape(bool* ok);
 
   uc32 ParseHexEscape(int length);
 
   uc32 ParseControlEscape(bool* ok);
   uc32 ParseOctalLiteral(bool* ok);
 
+  // Tries to parse the input as a backreference.  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);
+
   CharacterRange ParseClassAtom(bool* ok);
   RegExpTree* ReportError(Vector<const char> message, bool* ok);
   void Advance();
   void Advance(int dist);
   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_;
   int captures_seen_;
   unibrow::CharacterStream* in_;
   Handle<String>* error_;
+  static const int kMaxPushback = 5;
+  int pushback_count_;
+  uc32 pushback_buffer_[kMaxPushback];
 };
 
 
 // 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 2918 matching lines @@
   }
   ZoneList<Expression*>* args = new ZoneList<Expression*>(2);
   args->Add(new Literal(type));
   args->Add(new Literal(array));
   return new Throw(new CallRuntime(constructor, NULL, args),
                    scanner().location().beg_pos);
 }
 
 
 // ----------------------------------------------------------------------------
-// Regular expressions.
+// Regular expressions
+
 
 RegExpParser::RegExpParser(unibrow::CharacterStream* in, Handle<String>* error)
   : current_(kEndMarker),
     next_(kEndMarker),
     has_more_(true),
     has_next_(true),
     captures_seen_(0),
     in_(in),
-    error_(error) {
+    error_(error),
+    pushback_count_(0) {
   Advance(2);
 }
 
+
 void RegExpParser::Advance() {
   current_ = next_;
   has_more_ = has_next_;
-  if (in()->has_more()) {
+  if (pushback_count_ > 0) {
+    pushback_count_--;
+    next_ = pushback_buffer_[pushback_count_];
+    has_next_ = true;
+  } else if (in()->has_more()) {
     next_ = in()->GetNext();

[Lasse Reichstein, 2008/10/28 10:09:52]

the has_next variable is set to true in the push_back case, but not in the
in()->has_more() case. Is it known to be true in the latter case? If so, why
isn't it known to be true in the former?

[Christian Plesner Hansen, 2008/10/28 11:17:45]

We know it will work because we advance twice after setting up the pushback
buffer.

   } else {
     next_ = kEndMarker;
     has_next_ = false;
   }
 }
 
+
 void RegExpParser::Advance(int dist) {
   for (int i = 0; i < dist; i++)
     Advance();
 }
 
+
 RegExpTree* RegExpParser::ReportError(Vector<const char> message, bool* ok) {
   *ok = false;
   *error_ = Factory::NewStringFromAscii(message, NOT_TENURED);
   return NULL;
 }
 
+
 // Pattern ::
 //   Disjunction
 RegExpTree* RegExpParser::ParsePattern(bool* ok) {
   return ParseDisjunction(ok);
 }
 
+
 // Disjunction ::
 //   Alternative
 //   Alternative | Disjunction
 RegExpTree* RegExpParser::ParseDisjunction(bool* ok) {
   RegExpTree* first = ParseAlternative(CHECK_OK);
   if (current() == '|') {
     ZoneList<RegExpTree*>* nodes = new ZoneList<RegExpTree*>(2);
     nodes->Add(first);
     while (current() == '|') {
       Advance();
       RegExpTree* next = ParseAlternative(CHECK_OK);
       nodes->Add(next);
     }
     return new RegExpDisjunction(nodes);
   } else {
     return first;
   }
 }
 
+
 static bool IsAlternativeTerminator(uc32 c) {
   return c == '|' || c == ')' || c == RegExpParser::kEndMarker;
 }
 
+
 // Alternative ::
 //   [empty]
 //   Alternative Term
 RegExpTree* RegExpParser::ParseAlternative(bool* ok) {
   if (!IsAlternativeTerminator(current())) {
     RegExpTree* first = ParseTerm(CHECK_OK);
     if (!IsAlternativeTerminator(current())) {
       ZoneList<RegExpTree*>* nodes = new ZoneList<RegExpTree*>(2);
       nodes->Add(first);
       while (!IsAlternativeTerminator(current())) {
@@ skipping 40 matching lines @@
   switch (c) {
     case 'b': case 'B': case 'd': case 'D': case 's': case 'S':
     case 'w': case 'W':
       return true;
     default:
       return false;
   }
 }
 
 
+bool RegExpParser::ParseBackreferenceIndex(int* index_out) {
+  ASSERT_EQ('\\', current());
+  ASSERT('1' <= next() && next() <= '9');
+  ASSERT_EQ(0, pushback_count_);
+  if (captures_seen_ == 0)
+    return false;
+  int value = next() - '0';
+  if (value > captures_seen_)
+    return false;
+  static const int kMaxChars = kMaxPushback - 2;
+  EmbeddedVector<uc32, kMaxChars> chars_seen;

[Lasse Reichstein, 2008/10/28 10:09:52]

EmbeddedVector is used instead of array to have range checking in DEBUG mode?

[Christian Plesner Hansen, 2008/10/28 11:17:45]

Bingo

+  chars_seen[0] = next();
+  int char_count = 1;
+  Advance(2);
+  while (true) {
+    uc32 c = current();
+    if (IsDecimalDigit(c)) {
+      int next_value = 10 * value + (c - '0');
+      // To avoid reading past the end of thw stack-allocated pushback

[Lasse Reichstein, 2008/10/28 10:09:52]

"thw" -> "the"

+      // buffers we only read kMaxChars before giving up.
+      if (next_value > captures_seen_ || char_count > kMaxChars) {
+        // If we give up we have to push the characters we read back
+        // onto the pushback buffer in the reverse order.
+        pushback_buffer_[0] = current();
+        for (int i = 0; i < char_count; i++)
+          pushback_buffer_[i + 1] = chars_seen[char_count - i - 1];
+        pushback_buffer_[char_count + 1] = '\\';
+        pushback_count_ = char_count + 2;
+        // Then, once we've filled up the buffer, we read the two
+        // first characters into the lookahead.  This is a roundabout
+        // way of doing it but makes the code simpler.
+        Advance(2);
+        return false;
+      } else {
+        value = next_value;
+        chars_seen[char_count++] = current();
+        Advance();
+      }
+    } else {
+      *index_out = value;
+      return true;
+    }
+  }
+}
+
+
 // Term ::
 //   Assertion
 //   Atom
 //   Atom Quantifier
 RegExpTree* RegExpParser::ParseTerm(bool* ok) {
   RegExpTree* atom = NULL;
   switch (current()) {
     // Assertion ::
     //   ^
     //   $
@@ skipping 32 matching lines @@
           //   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);
             atom = new RegExpCharacterClass(CharacterRange::CharacterClass(c));
             goto has_read_atom;
           }
-          // Todo backreferences
+          case '1': case '2': case '3': case '4': case '5': case '6':
+          case '7': case '8': case '9': {
+            int index = 0;
+            if (ParseBackreferenceIndex(&index)) {
+              atom = new RegExpBackreference(index);
+              goto has_read_atom;
+            } else {
+              // If this is not a backreference we go to the atom parser
+              // which will read it as an octal escape.
+              goto parse_atom;
+            }
+          }
           default:
-            break;
+            goto parse_atom;
         }
       }
       // All other escapes fall through to the default case since
       // they correspond to single characters that can be
       // represented within atoms.
     default: {
+     parse_atom:
       atom = ParseAtom(CHECK_OK);
       break;
     }
   }
  has_read_atom:
   int min;
   int max;
   switch (current()) {
     // QuantifierPrefix ::
     //   *
     //   +
     //   ?

[Lasse Reichstein, 2008/10/28 10:09:52]

and " //  {"  ?

     case '*':
       min = 0;
       max = RegExpQuantifier::kInfinity;
       Advance();
       break;
     case '+':
       min = 1;
       max = RegExpQuantifier::kInfinity;
       Advance();
       break;
@@ skipping 407 matching lines @@
                        start_position,
                        is_expression);
   return result;
 }
 
 
 #undef NEW
 
 
 } }  // namespace v8::internal