Flat string reader

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 478 matching lines @@
     UNREACHABLE();
     return;
   }
   terms_.Add(new RegExpQuantifier(min, max, is_greedy, atom));
   LAST(ADD_TERM);
 }
 
 
 class RegExpParser {
  public:
-  RegExpParser(unibrow::CharacterStream* in,
+  RegExpParser(FlatStringReader* in,
                Handle<String>* error,
                bool multiline_mode);
   RegExpTree* ParsePattern(bool* ok);
   RegExpTree* ParseDisjunction(bool* ok);
   RegExpTree* ParseGroup(bool* ok);
   RegExpTree* ParseCharacterClass(bool* ok);
 
   // Parses a {...,...} quantifier and stores the range in the given
   // out parameters.
   void* ParseIntervalQuantifier(int* min_out, int* max_out, bool* ok);
@@ skipping 14 matching lines @@
   // it fails it will push back the characters read so the same characters
   // can be reparsed.
   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);
-  // Pushes a read character (or potentially some other character) back
-  // 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();
+  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 = 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_; }
+  bool has_next() { return next_pos_ < in()->length(); }
+  uc32 Next();
+  FlatStringReader* in() { return in_; }
   uc32 current_;
-  uc32 next_;
   bool has_more_;
-  bool has_next_;
   bool multiline_mode_;
-  unibrow::CharacterStream* in_;
+  int next_pos_;
+  FlatStringReader* 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 {
@@ skipping 2925 matching lines @@
   args->Add(new Literal(array));
   return new Throw(new CallRuntime(constructor, NULL, args),
                    scanner().location().beg_pos);
 }
 
 
 // ----------------------------------------------------------------------------
 // Regular expressions
 
 
-RegExpParser::RegExpParser(unibrow::CharacterStream* in,
+RegExpParser::RegExpParser(FlatStringReader* in,
                            Handle<String>* error,
                            bool multiline_mode)
   : current_(kEndMarker),
-    next_(kEndMarker),
     has_more_(true),
-    has_next_(true),
     multiline_mode_(multiline_mode),
+    next_pos_(0),
     in_(in),
     error_(error),
-    pushback_count_(0),
     has_character_escapes_(false),
     captures_(NULL) {
-  Advance(2);
+  Advance(1);
+}
+
+
+uc32 RegExpParser::Next() {
+  if (has_next()) {
+    return in()->Get(next_pos_);
+  } else {
+    return kEndMarker;
+  }
 }
 
 
 void RegExpParser::Advance() {
-  current_ = next_;
-  has_more_ = has_next_;
-  if (pushback_count_ > 0) {
-    pushback_count_--;
-    next_ = pushback_buffer_[pushback_count_];
-  } else if (in()->has_more()) {
-    next_ = in()->GetNext();
+  if (next_pos_ < in()->length()) {
+    current_ = in()->Get(next_pos_);
+    next_pos_++;
   } else {
-    next_ = kEndMarker;
-    has_next_ = false;
+    current_ = kEndMarker;
+    has_more_ = false;
   }
 }
 
 
+void RegExpParser::Reset(int pos) {
+  next_pos_ = pos;
+  Advance();
+}
+
+
 void RegExpParser::Advance(int dist) {
   for (int i = 0; i < dist; i++)
     Advance();
 }
 
 
-void RegExpParser::PushBack(uc32 character) {
-  if (has_next_) {
-    ASSERT(pushback_count_ < kMaxPushback);
-    pushback_buffer_[pushback_count_] = next_;
-    pushback_count_++;
-  }
-
-  next_ = current_;
-  has_next_ = has_more_;
-
-  current_ = character;
-  has_more_ = true;
-}
-
-
-bool RegExpParser::CanPushBack() {
-  return (pushback_count_ < kMaxPushback);
-}
-
 // Reports whether the parsed string atoms contain any characters that were
 // escaped in the original pattern. If not, all atoms are proper substrings
 // of the original pattern.
 bool RegExpParser::HasCharacterEscapes() {
   return has_character_escapes_;
 }
 
 RegExpTree* RegExpParser::ReportError(Vector<const char> message, bool* ok) {
   *ok = false;
   *error_ = Factory::NewStringFromAscii(message, NOT_TENURED);
@@ skipping 79 matching lines @@
       break;
     }
     case '[': {
       RegExpTree* atom = ParseCharacterClass(CHECK_OK);
       builder.AddAtom(atom);
       break;
     }
     // Atom ::
     //   \ AtomEscape
     case '\\':
-      switch (next()) {
+      switch (Next()) {
       case kEndMarker:
         ReportError(CStrVector("\\ at end of pattern"), CHECK_OK);
       case 'b':
         Advance(2);
         builder.AddAssertion(
             new RegExpAssertion(RegExpAssertion::BOUNDARY));
         continue;
       case 'B':
         Advance(2);
         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();
+        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);
         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) {
             // 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();
+        uc32 first_digit = Next();
         if (first_digit == '8' || first_digit == '9') {
           // Treat as identity escape
           builder.AddCharacter(first_digit);
           Advance(2);
           break;
         }
       }
       // FALLTHROUGH
       case '0': {
         Advance();
@@ skipping 44 matching lines @@
         uc32 value;
         if (ParseHexEscape(4, &value)) {
           builder.AddCharacter(value);
         } else {
           builder.AddCharacter('u');
         }
         break;
       }
       default:
         // Identity escape.
-        builder.AddCharacter(next());
+        builder.AddCharacter(Next());
         Advance(2);
         break;
       }
       has_character_escapes_ = true;
       break;
     default:
       builder.AddCharacter(current());
       Advance();
       break;
     }  // end switch(current())
@@ skipping 72 matching lines @@
       return true;
     default:
       return false;
   }
 }
 #endif
 
 
 bool RegExpParser::ParseBackreferenceIndex(int* index_out) {
   ASSERT_EQ('\\', current());
-  ASSERT('1' <= next() && next() <= '9');
-  ASSERT_EQ(0, pushback_count_);
+  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;
-  int value = next() - '0';
+  int start = position();
+  int value = Next() - '0';
   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_->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('\\');
+      if (value > captures_->length()) {
+        Reset(start);
         return false;
       }
-      chars_seen[char_count++] = current();
       Advance();
     } else {
       break;
     }
   }
   *index_out = value;
   return true;
 }
 
 
@@ skipping 78 matching lines @@
     if (value < 32 && '0' <= current() && current() <= '7') {
       value = value * 8 + current() - '0';
       Advance();
     }
   }
   return value;
 }
 
 
 bool RegExpParser::ParseHexEscape(int length, uc32 *value) {
-  static const int kMaxChars = kMaxPushback;
-  EmbeddedVector<uc32, kMaxChars> chars_seen;
-  ASSERT(length <= kMaxChars);
+  int start = position();
   uc32 val = 0;
   bool done = false;
   for (int i = 0; !done; i++) {
     uc32 c = current();
     int d = HexValue(c);
     if (d < 0) {
-      while (i > 0) {
-        i--;
-        PushBack(chars_seen[i]);
-      }
+      Reset(start);
       return false;
     }
     val = val * 16 + d;
     Advance();
-    if (i < length - 1) {
-      chars_seen[i] = c;
-    } else {
+    if (i == length - 1) {
       done = true;
     }
   }
   *value = val;
   return true;
 }
 
 
 uc32 RegExpParser::ParseClassCharacterEscape(bool* ok) {
   ASSERT(current() == '\\');
-  ASSERT(has_next() && !IsSpecialClassEscape(next()));
+  ASSERT(has_next() && !IsSpecialClassEscape(Next()));
   Advance();
   switch (current()) {
     // ControlEscape :: one of
     //   f n r t v
     case 'f':
       Advance();
       return '\f';
     case 'n':
       Advance();
       return '\n';
@@ skipping 45 matching lines @@
   }
   return 0;
 }
 
 
 RegExpTree* RegExpParser::ParseGroup(bool* ok) {
   ASSERT_EQ(current(), '(');
   char type = '(';
   Advance();
   if (current() == '?') {
-    switch (next()) {
+    switch (Next()) {
       case ':': case '=': case '!':
-        type = next();
+        type = Next();
         Advance(2);
         break;
       default:
         ReportError(CStrVector("Invalid group"), CHECK_OK);
         break;
     }
   } else {
     if (captures_ == NULL) {
       captures_ = new ZoneList<RegExpCapture*>(2);
     }
@@ skipping 39 matching lines @@
   }
 }
 
 
 CharacterRange RegExpParser::ParseClassAtom(bool* is_char_class,
                                             ZoneList<CharacterRange>* ranges,
                                             bool* ok) {
   ASSERT_EQ(false, *is_char_class);
   uc32 first = current();
   if (first == '\\') {
-    switch (next()) {
+    switch (Next()) {
       case 'w': case 'W': case 'd': case 'D': case 's': case 'S': {
         *is_char_class = true;
-        uc32 c = next();
+        uc32 c = Next();
         CharacterRange::AddClassEscape(c, ranges);
         Advance(2);
         return NULL;
       }
       default:
         uc32 c = ParseClassCharacterEscape(CHECK_OK);
         return CharacterRange::Singleton(c);
     }
   } else {
     Advance();
@@ skipping 93 matching lines @@
   PreParser parser(no_script, allow_natives_syntax, extension);
   if (!parser.PreParseProgram(stream)) return NULL;
   // The list owns the backing store so we need to clone the vector.
   // That way, the result will be exactly the right size rather than
   // the expected 50% too large.
   Vector<unsigned> store = parser.recorder()->store()->ToVector().Clone();
   return new ScriptDataImpl(store);
 }
 
 
-bool ParseRegExp(unibrow::CharacterStream* stream, RegExpParseResult* result) {
+bool ParseRegExp(FlatStringReader* input, RegExpParseResult* result) {
   ASSERT(result != NULL);
   // Get multiline flag somehow
-  RegExpParser parser(stream, &result->error, false);
+  RegExpParser parser(input, &result->error, false);
   bool ok = true;
   result->tree = parser.ParsePattern(&ok);
   if (!ok) {
     ASSERT(result->tree == NULL);
     ASSERT(!result->error.is_null());
   } else {
     ASSERT(result->tree != NULL);
     ASSERT(result->error.is_null());
   }
   if (ok) {
@@ skipping 49 matching lines @@
                        start_position,
                        is_expression);
   return result;
 }
 
 
 #undef NEW
 
 
 } }  // namespace v8::internal