RegExp stack and zone limits.

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 477 matching lines @@
   terms_.Add(new RegExpQuantifier(min, max, is_greedy, atom));
   LAST(ADD_TERM);
 }
 
 
 class RegExpParser {
  public:
   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);
+  RegExpTree* ParsePattern();
+  RegExpTree* ParseDisjunction();
+  RegExpTree* ParseGroup();
+  RegExpTree* ParseCharacterClass();
 
   // Parses a {...,...} quantifier and stores the range in the given
   // out parameters.
   bool ParseIntervalQuantifier(int* min_out, int* max_out);
 
   // Parses and returns a single escaped character.  The character
   // must not be 'b' or 'B' since they are usually handle specially.
-  uc32 ParseClassCharacterEscape(bool* ok);
+  uc32 ParseClassCharacterEscape();
 
   // 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 ParseControlLetterEscape();
   uc32 ParseOctalLiteral();
 
   // 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);
 
-  CharacterRange ParseClassAtom(uc16* char_class,
-                                bool* ok);
-  RegExpTree* ReportError(Vector<const char> message, bool* ok);
+  CharacterRange ParseClassAtom(uc16* char_class);
+  RegExpTree* ReportError(Vector<const char> message);
   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; }
+  bool failed() { return failed_; }
 
   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_;
   int next_pos_;
   FlatStringReader* in_;
   Handle<String>* error_;
   bool has_character_escapes_;
   ZoneList<RegExpCapture*>* captures_;
   bool is_scanned_for_captures_;
   // The capture count is only valid after we have scanned for captures.
   int capture_count_;
+  bool failed_;
 };
 
 
 // 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 454 matching lines @@
 // CAUTION: This macro appends extra statements after a call,
 // thus it must never be used where only a single statement
 // is correct (e.g. an if statement branch w/o braces)!
 
 #define CHECK_OK  ok);   \
   if (!*ok) return NULL; \
   ((void)0
 #define DUMMY )  // to make indentation work
 #undef DUMMY
 
+#define CHECK_FAILED  );   \
+  if (failed_) return NULL; \
+  ((void)0

[Mads Ager (chromium), 2008/12/01 15:29:09]

Maybe we should add a dummy parenthesis as above so editor indentation does not
break?

[Christian Plesner Hansen, 2008/12/01 15:52:55]

Aah, so that's what DUMMY was for.

+
 
 // ----------------------------------------------------------------------------
 // Implementation of Parser
 
 Parser::Parser(Handle<Script> script,
                bool allow_natives_syntax,
                v8::Extension* extension,
                bool is_pre_parsing,
                ParserFactory* factory,
                ParserLog* log,
@@ skipping 2452 matching lines @@
                            bool multiline)
   : current_(kEndMarker),
     has_more_(true),
     multiline_(multiline),
     next_pos_(0),
     in_(in),
     error_(error),
     has_character_escapes_(false),
     captures_(NULL),
     is_scanned_for_captures_(false),
-    capture_count_(0) {
+    capture_count_(0),
+    failed_(false) {
   Advance(1);
 }
 
 
 uc32 RegExpParser::Next() {
   if (has_next()) {
     return in()->Get(next_pos_);
   } else {
     return kEndMarker;
   }
 }
 
 
 void RegExpParser::Advance() {
   if (next_pos_ < in()->length()) {
-    current_ = in()->Get(next_pos_);
-    next_pos_++;
+    StackLimitCheck check;
+    if (check.HasOverflowed()) {
+      ReportError(CStrVector(Top::kStackOverflowMessage));
+    } else if (Zone::excess_allocation()) {
+      ReportError(CStrVector("Regular expression too large"));
+    } else {
+      current_ = in()->Get(next_pos_);
+      next_pos_++;
+    }
   } else {
     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();
 }
 
 
 // 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;
+RegExpTree* RegExpParser::ReportError(Vector<const char> message) {
+  failed_ = true;
   *error_ = Factory::NewStringFromAscii(message, NOT_TENURED);
+  // Zip to the end to make sure the no more input is read.
+  current_ = kEndMarker;
+  next_pos_ = in()->length();
   return NULL;
 }
 
 
 // Pattern ::
 //   Disjunction
-RegExpTree* RegExpParser::ParsePattern(bool* ok) {
-  RegExpTree* result = ParseDisjunction(CHECK_OK);
+RegExpTree* RegExpParser::ParsePattern() {
+  RegExpTree* result = ParseDisjunction(CHECK_FAILED);
   if (has_more()) {
-    ReportError(CStrVector("Unmatched ')'"), CHECK_OK);
+    ReportError(CStrVector("Unmatched ')'") CHECK_FAILED);
   }
   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(bool* ok) {
+RegExpTree* RegExpParser::ParseDisjunction() {
   RegExpBuilder builder;
   int capture_start_index = captures_started();
   while (true) {
     switch (current()) {
     case kEndMarker:
     case ')':
       return builder.ToRegExp();
     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 '?':
-      ReportError(CStrVector("Nothing to repeat"), CHECK_OK);
+      ReportError(CStrVector("Nothing to repeat") CHECK_FAILED);
     case '^': {
       Advance();
       RegExpAssertion::Type type =
           multiline_ ? RegExpAssertion::START_OF_LINE :
                        RegExpAssertion::START_OF_INPUT;
       builder.AddAssertion(new RegExpAssertion(type));
       continue;
     }
     case '$': {
       Advance();
       RegExpAssertion::Type type =
           multiline_ ? RegExpAssertion::END_OF_LINE :
                        RegExpAssertion::END_OF_INPUT;
       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);
       break;
     }
     case '(': {
-      RegExpTree* atom = ParseGroup(CHECK_OK);
+      RegExpTree* atom = ParseGroup(CHECK_FAILED);
       builder.AddAtom(atom);
       break;
     }
     case '[': {
-      RegExpTree* atom = ParseCharacterClass(CHECK_OK);
+      RegExpTree* atom = ParseCharacterClass(CHECK_FAILED);
       builder.AddAtom(atom);
       break;
     }
     // Atom ::
     //   \ AtomEscape
     case '\\':
       switch (Next()) {
       case kEndMarker:
-        ReportError(CStrVector("\\ at end of pattern"), CHECK_OK);
+        ReportError(CStrVector("\\ at end of pattern") CHECK_FAILED);
       case 'b':
         Advance(2);
         builder.AddAssertion(
             new RegExpAssertion(RegExpAssertion::BOUNDARY));
         continue;
       case 'B':
         Advance(2);
         builder.AddAssertion(
             new RegExpAssertion(RegExpAssertion::NON_BOUNDARY));
         continue;
@@ skipping 57 matching lines @@
       case 't':
         Advance(2);
         builder.AddCharacter('\t');
         break;
       case 'v':
         Advance(2);
         builder.AddCharacter('\v');
         break;
       case 'c': {
         Advance(2);
-        uc32 control = ParseControlLetterEscape(ok);
+        uc32 control = ParseControlLetterEscape();
         builder.AddCharacter(control);
         break;
       }
       case 'x': {
         Advance(2);
         uc32 value;
         if (ParseHexEscape(2, &value)) {
           builder.AddCharacter(value);
         } else {
           builder.AddCharacter('x');
@@ skipping 14 matching lines @@
         // Identity escape.
         builder.AddCharacter(Next());
         Advance(2);
         break;
       }
       has_character_escapes_ = true;
       break;
     case '{': {
       int dummy;
       if (ParseIntervalQuantifier(&dummy, &dummy)) {
-        ReportError(CStrVector("Nothing to repeat"), CHECK_OK);
+        ReportError(CStrVector("Nothing to repeat") CHECK_FAILED);
       }
       // fallthrough
     }
     default:
       builder.AddCharacter(current());
       Advance();
       break;
     }  // end switch(current())
 
    has_read_atom:
@@ skipping 196 matching lines @@
   }
   *min_out = min;
   *max_out = max;
   return true;
 }
 
 
 // Upper and lower case letters differ by one bit.
 STATIC_CHECK(('a' ^ 'A') == 0x20);
 
-uc32 RegExpParser::ParseControlLetterEscape(bool* ok) {
+uc32 RegExpParser::ParseControlLetterEscape() {
   if (!has_more()) {
-    ReportError(CStrVector("\\c at end of pattern"), ok);
+    ReportError(CStrVector("\\c at end of pattern"));
     return '\0';
   }
   uc32 letter = current() & ~(0x20);  // Collapse upper and lower case letters.
   if (letter < 'A' || 'Z' < letter) {
     // Non-spec error-correction: "\c" followed by non-control letter is
     // interpreted as an IdentityEscape of 'c'.
     return 'c';
   }
   Advance();
   return letter & 0x1f;  // Remainder modulo 32, per specification.
@@ skipping 33 matching lines @@
     Advance();
     if (i == length - 1) {
       done = true;
     }
   }
   *value = val;
   return true;
 }
 
 
-uc32 RegExpParser::ParseClassCharacterEscape(bool* ok) {
+uc32 RegExpParser::ParseClassCharacterEscape() {
   ASSERT(current() == '\\');
   ASSERT(has_next() && !IsSpecialClassEscape(Next()));
   Advance();
   switch (current()) {
     case 'b':
       Advance();
       return '\b';
     // ControlEscape :: one of
     //   f n r t v
     case 'f':
       Advance();
       return '\f';
     case 'n':
       Advance();
       return '\n';
     case 'r':
       Advance();
       return '\r';
     case 't':
       Advance();
       return '\t';
     case 'v':
       Advance();
       return '\v';
     case 'c':
-      return ParseControlLetterEscape(ok);
+      return ParseControlLetterEscape();
     case '0': case '1': case '2': case '3': case '4': case '5':
     case '6': case '7':
       // For compatibility, we interpret a decimal escape that isn't
       // a back reference (and therefore either \0 or not valid according
       // to the specification) as a 1..3 digit octal character code.
       return ParseOctalLiteral();
     case 'x': {
       Advance();
       uc32 value;
       if (ParseHexEscape(2, &value)) {
@@ skipping 19 matching lines @@
       // by the ECMAScript specification.
       uc32 result = current();
       Advance();
       return result;
     }
   }
   return 0;
 }
 
 
-RegExpTree* RegExpParser::ParseGroup(bool* ok) {
+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_OK);
+        ReportError(CStrVector("Invalid group") CHECK_FAILED);
         break;
     }
   } else {
     if (captures_ == NULL) {
       captures_ = new ZoneList<RegExpCapture*>(2);
     }
     captures_->Add(NULL);
   }
   int capture_index = captures_started();
-  RegExpTree* body = ParseDisjunction(CHECK_OK);
+  RegExpTree* body = ParseDisjunction(CHECK_FAILED);
   if (current() != ')') {
-    ReportError(CStrVector("Unterminated group"), CHECK_OK);
+    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);
@@ skipping 17 matching lines @@
   } else if (type == ':') {
     return body;
   } else {
     ASSERT(type == '=' || type == '!');
     bool is_positive = (type == '=');
     return new RegExpLookahead(body, is_positive);
   }
 }
 
 
-CharacterRange RegExpParser::ParseClassAtom(uc16* char_class, bool* ok) {
+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.
       }
       default:
-        uc32 c = ParseClassCharacterEscape(CHECK_OK);
+        uc32 c = ParseClassCharacterEscape(CHECK_FAILED);
         return CharacterRange::Singleton(c);
     }
   } else {
     Advance();
     return CharacterRange::Singleton(first);
   }
 }
 
 
-RegExpTree* RegExpParser::ParseCharacterClass(bool* ok) {
+RegExpTree* RegExpParser::ParseCharacterClass() {
   static const char* kUnterminated = "Unterminated character class";
   static const char* kRangeOutOfOrder = "Range out of order in character class";
 
   ASSERT_EQ(current(), '[');
   Advance();
   bool is_negated = false;
   if (current() == '^') {
     is_negated = true;
     Advance();
   }
   ZoneList<CharacterRange>* ranges = new ZoneList<CharacterRange>(2);
   while (has_more() && current() != ']') {
     uc16 char_class = 0;
-    CharacterRange first = ParseClassAtom(&char_class, CHECK_OK);
+    CharacterRange first = ParseClassAtom(&char_class CHECK_FAILED);
     if (char_class) {
       CharacterRange::AddClassEscape(char_class, ranges);
       continue;
     }
     if (current() == '-') {
       Advance();
       if (current() == kEndMarker) {
         // If we reach the end we break out of the loop and let the
         // following code report an error.
         break;
       } else if (current() == ']') {
         ranges->Add(first);
         ranges->Add(CharacterRange::Singleton('-'));
         break;
       }
-      CharacterRange next = ParseClassAtom(&char_class, CHECK_OK);
+      CharacterRange next = ParseClassAtom(&char_class CHECK_FAILED);
       if (char_class) {
         ranges->Add(first);
         ranges->Add(CharacterRange::Singleton('-'));
         CharacterRange::AddClassEscape(char_class, ranges);
         continue;
       }
       if (first.from() > next.to()) {
-        return ReportError(CStrVector(kRangeOutOfOrder), CHECK_OK);
+        return ReportError(CStrVector(kRangeOutOfOrder) CHECK_FAILED);
       }
       ranges->Add(CharacterRange::Range(first.from(), next.to()));
     } else {
       ranges->Add(first);
     }
   }
   if (!has_more()) {
-    return ReportError(CStrVector(kUnterminated), CHECK_OK);
+    return ReportError(CStrVector(kUnterminated) CHECK_FAILED);
   }
   Advance();
   if (ranges->length() == 0) {
     ranges->Add(CharacterRange::Everything());
     is_negated = !is_negated;
   }
   return new RegExpCharacterClass(ranges, is_negated);
 }
 
 
@@ skipping 42 matching lines @@
   // the expected 50% too large.
   Vector<unsigned> store = parser.recorder()->store()->ToVector().Clone();
   return new ScriptDataImpl(store);
 }
 
 
 bool ParseRegExp(FlatStringReader* input,
                  bool multiline,
                  RegExpParseResult* result) {
   ASSERT(result != NULL);
+  // Make sure we have a stack guard.
+  StackGuard guard;
   RegExpParser parser(input, &result->error, multiline);
-  bool ok = true;
-  result->tree = parser.ParsePattern(&ok);
-  if (!ok) {
+  result->tree = parser.ParsePattern();
+  if (parser.failed()) {
     ASSERT(result->tree == NULL);
     ASSERT(!result->error.is_null());
   } else {
     ASSERT(result->tree != NULL);
     ASSERT(result->error.is_null());
-  }
-  if (ok) {
     result->has_character_escapes = parser.HasCharacterEscapes();
     result->capture_count = parser.captures_started();
   }
-  return ok;
+  return !parser.failed();
 }
 
 
 FunctionLiteral* MakeAST(bool compile_in_global_context,
                          Handle<Script> script,
                          v8::Extension* extension,
                          ScriptDataImpl* pre_data) {
   bool allow_natives_syntax =
       always_allow_natives_syntax ||
       FLAG_allow_natives_syntax ||
@@ skipping 35 matching lines @@
                        start_position,
                        is_expression);
   return result;
 }
 
 
 #undef NEW
 
 
 } }  // namespace v8::internal