Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(151)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: runtime/vm/regexp_parser.cc

Issue 539153002: Port and integrate the irregexp engine from V8 (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Addressed Ivan's comments. Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « runtime/vm/regexp_parser.h ('k') | runtime/vm/symbols.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: runtime/vm/regexp_parser.cc
diff --git a/runtime/vm/regexp_parser.cc b/runtime/vm/regexp_parser.cc
new file mode 100644
index 0000000000000000000000000000000000000000..1b2df30ede8e0f975d76892182c6bad062b08fdf
--- /dev/null
+++ b/runtime/vm/regexp_parser.cc
@@ -0,0 +1,1070 @@
+// Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+#include "vm/longjump.h"
+#include "vm/object_store.h"
+#include "vm/regexp_parser.h"
+
+namespace dart {
+
+#define I isolate()
+
+// Enables possessive quantifier syntax for testing.
+static const bool FLAG_regexp_possessive_quantifier = false;
+
+RegExpBuilder::RegExpBuilder()
+ : isolate_(Isolate::Current()),
+ pending_empty_(false),
+ characters_(NULL),
+ terms_(),
+ text_(),
+ alternatives_()
+#ifdef DEBUG
+ , last_added_(ADD_NONE)
+#endif
+ {}
+
+
+void RegExpBuilder::FlushCharacters() {
+ pending_empty_ = false;
+ if (characters_ != NULL) {
+ RegExpTree* atom = new(I) RegExpAtom(characters_);
+ characters_ = NULL;
+ text_.Add(atom);
+ LAST(ADD_ATOM);
+ }
+}
+
+
+void RegExpBuilder::FlushText() {
+ FlushCharacters();
+ intptr_t num_text = text_.length();
+ if (num_text == 0) {
+ return;
+ } else if (num_text == 1) {
+ terms_.Add(text_.Last());
+ } else {
+ RegExpText* text = new(I) RegExpText();
+ for (intptr_t i = 0; i < num_text; i++)
+ text_[i]->AppendToText(text);
+ terms_.Add(text);
+ }
+ text_.Clear();
+}
+
+
+void RegExpBuilder::AddCharacter(uint16_t c) {
+ pending_empty_ = false;
+ if (characters_ == NULL) {
+ characters_ = new(I) ZoneGrowableArray<uint16_t>(4);
+ }
+ characters_->Add(c);
+ LAST(ADD_CHAR);
+}
+
+
+void RegExpBuilder::AddEmpty() {
+ pending_empty_ = true;
+}
+
+
+void RegExpBuilder::AddAtom(RegExpTree* term) {
+ if (term->IsEmpty()) {
+ AddEmpty();
+ return;
+ }
+ if (term->IsTextElement()) {
+ FlushCharacters();
+ text_.Add(term);
+ } else {
+ FlushText();
+ terms_.Add(term);
+ }
+ LAST(ADD_ATOM);
+}
+
+
+void RegExpBuilder::AddAssertion(RegExpTree* assert) {
+ FlushText();
+ terms_.Add(assert);
+ LAST(ADD_ASSERT);
+}
+
+
+void RegExpBuilder::NewAlternative() {
+ FlushTerms();
+}
+
+
+void RegExpBuilder::FlushTerms() {
+ FlushText();
+ intptr_t num_terms = terms_.length();
+ RegExpTree* alternative;
+ if (num_terms == 0) {
+ alternative = RegExpEmpty::GetInstance();
+ } else if (num_terms == 1) {
+ alternative = terms_.Last();
+ } else {
+ ZoneGrowableArray<RegExpTree*>* terms =
+ new(I) ZoneGrowableArray<RegExpTree*>();
+ for (intptr_t i = 0; i < terms_.length(); i++) {
+ terms->Add(terms_[i]);
+ }
+ alternative = new(I) RegExpAlternative(terms);
+ }
+ alternatives_.Add(alternative);
+ terms_.Clear();
+ LAST(ADD_NONE);
+}
+
+
+RegExpTree* RegExpBuilder::ToRegExp() {
+ FlushTerms();
+ intptr_t num_alternatives = alternatives_.length();
+ if (num_alternatives == 0) {
+ return RegExpEmpty::GetInstance();
+ }
+ if (num_alternatives == 1) {
+ return alternatives_.Last();
+ }
+ ZoneGrowableArray<RegExpTree*>* alternatives =
+ new(I) ZoneGrowableArray<RegExpTree*>();
+ for (intptr_t i = 0; i < alternatives_.length(); i++) {
+ alternatives->Add(alternatives_[i]);
+ }
+ return new(I) RegExpDisjunction(alternatives);
+}
+
+
+void RegExpBuilder::AddQuantifierToAtom(
+ intptr_t min,
+ intptr_t max,
+ RegExpQuantifier::QuantifierType quantifier_type) {
+ if (pending_empty_) {
+ pending_empty_ = false;
+ return;
+ }
+ RegExpTree* atom;
+ if (characters_ != NULL) {
+ DEBUG_ASSERT(last_added_ == ADD_CHAR);
+ // Last atom was character.
+
+ ZoneGrowableArray<uint16_t> *char_vector =
+ new(I) ZoneGrowableArray<uint16_t>();
+ char_vector->AddArray(*characters_);
+ intptr_t num_chars = char_vector->length();
+ if (num_chars > 1) {
+ ZoneGrowableArray<uint16_t> *prefix =
+ new(I) ZoneGrowableArray<uint16_t>();
+ for (intptr_t i = 0; i < num_chars - 1; i++) {
+ prefix->Add(char_vector->At(i));
+ }
+ text_.Add(new(I) RegExpAtom(prefix));
+ ZoneGrowableArray<uint16_t> *tail = new(I) ZoneGrowableArray<uint16_t>();
+ tail->Add(char_vector->At(num_chars - 1));
+ char_vector = tail;
+ }
+ characters_ = NULL;
+ atom = new(I) RegExpAtom(char_vector);
+ FlushText();
+ } else if (text_.length() > 0) {
+ DEBUG_ASSERT(last_added_ == ADD_ATOM);
+ atom = text_.RemoveLast();
+ FlushText();
+ } else if (terms_.length() > 0) {
+ DEBUG_ASSERT(last_added_ == ADD_ATOM);
+ atom = terms_.RemoveLast();
+ if (atom->max_match() == 0) {
+ // Guaranteed to only match an empty string.
+ LAST(ADD_TERM);
+ if (min == 0) {
+ return;
+ }
+ terms_.Add(atom);
+ return;
+ }
+ } else {
+ // Only call immediately after adding an atom or character!
+ UNREACHABLE();
+ return;
+ }
+ terms_.Add(new(I) RegExpQuantifier(min, max, quantifier_type, atom));
+ LAST(ADD_TERM);
+}
+
+// ----------------------------------------------------------------------------
+// Implementation of Parser
+
+RegExpParser::RegExpParser(const String& in,
+ String* error,
+ bool multiline)
+ : isolate_(Isolate::Current()),
+ error_(error),
+ captures_(NULL),
+ in_(in),
+ current_(kEndMarker),
+ next_pos_(0),
+ capture_count_(0),
+ has_more_(true),
+ multiline_(multiline),
+ simple_(false),
+ contains_anchor_(false),
+ is_scanned_for_captures_(false),
+ failed_(false) {
+ Advance();
+}
+
+
+uint32_t RegExpParser::Next() {
+ if (has_next()) {
+ return in().CharAt(next_pos_);
+ } else {
+ return kEndMarker;
+ }
+}
+
+
+void RegExpParser::Advance() {
+ if (next_pos_ < in().Length()) {
+ current_ = in().CharAt(next_pos_);
+ next_pos_++;
+ } else {
+ current_ = kEndMarker;
+ has_more_ = false;
+ }
+}
+
+
+void RegExpParser::Advance(intptr_t dist) {
+ next_pos_ += dist - 1;
+ Advance();
+}
+
+
+void RegExpParser::Reset(intptr_t pos) {
+ next_pos_ = pos;
+ has_more_ = (pos < in().Length());
+ Advance();
+}
+
+
+bool RegExpParser::ParseFunction(ParsedFunction *parsed_function) {
+ Isolate* isolate = parsed_function->isolate();
+ JSRegExp& regexp = JSRegExp::Handle(parsed_function->function().regexp());
+
+ const String& pattern = String::Handle(regexp.pattern());
+ const bool multiline = regexp.is_multi_line();
+
+ RegExpCompileData* compile_data = new(isolate) RegExpCompileData();
+ if (!RegExpParser::ParseRegExp(pattern, multiline, compile_data)) {
+ // Parsing failures are handled in the JSRegExp factory constructor.
+ UNREACHABLE();
+ }
+
+ regexp.set_num_bracket_expressions(compile_data->capture_count);
+ if (compile_data->simple) {
+ regexp.set_is_simple();
+ } else {
+ regexp.set_is_complex();
+ }
+
+ parsed_function->SetRegExpCompileData(compile_data);
+
+ return true;
+}
+
+
+bool RegExpParser::ParseRegExp(const String& input,
+ bool multiline,
+ RegExpCompileData* result) {
+ ASSERT(result != NULL);
+ LongJumpScope jump;
+ RegExpParser parser(input, &result->error, multiline);
+ if (setjmp(*jump.Set()) == 0) {
+ RegExpTree* tree = parser.ParsePattern();
+ ASSERT(tree != NULL);
+ ASSERT(result->error.IsNull());
+ result->tree = tree;
+ intptr_t capture_count = parser.captures_started();
+ result->simple = tree->IsAtom() && parser.simple() && capture_count == 0;
+ result->contains_anchor = parser.contains_anchor();
+ result->capture_count = capture_count;
+ } else {
+ ASSERT(!result->error.IsNull());
+ Isolate::Current()->object_store()->clear_sticky_error();
+
+ // Throw a FormatException on parsing failures.
+ const String& message = String::Handle(
+ String::Concat(result->error, input));
+ const Array& args = Array::Handle(Array::New(1));
+ args.SetAt(0, message);
+
+ Exceptions::ThrowByType(Exceptions::kFormat, args);
+ }
+ return !parser.failed();
+}
+
+
+void RegExpParser::ReportError(const char* message) {
+ failed_ = true;
+ *error_ = String::New(message);
+ // Zip to the end to make sure the no more input is read.
+ current_ = kEndMarker;
+ next_pos_ = in().Length();
+
+ const Error& error = Error::Handle(LanguageError::New(*error_));
+ Report::LongJump(error);
+ UNREACHABLE();
+}
+
+
+// Pattern ::
+// Disjunction
+RegExpTree* RegExpParser::ParsePattern() {
+ RegExpTree* result = ParseDisjunction();
+ ASSERT(!has_more());
+ // If the result of parsing is a literal string atom, and it has the
+ // same length as the input, then the atom is identical to the input.
+ if (result->IsAtom() && result->AsAtom()->length() == in().Length()) {
+ simple_ = true;
+ }
+ return result;
+}
+
+
+// Disjunction ::
+// Alternative
+// Alternative | Disjunction
+// Alternative ::
+// [empty]
+// Term Alternative
+// Term ::
+// Assertion
+// Atom
+// Atom Quantifier
+RegExpTree* RegExpParser::ParseDisjunction() {
+ // Used to store current state while parsing subexpressions.
+ RegExpParserState initial_state(NULL, INITIAL, 0, I);
+ RegExpParserState* stored_state = &initial_state;
+ // Cache the builder in a local variable for quick access.
+ RegExpBuilder* builder = initial_state.builder();
+ while (true) {
+ switch (current()) {
+ case kEndMarker:
+ if (stored_state->IsSubexpression()) {
+ // Inside a parenthesized group when hitting end of input.
+ ReportError("Unterminated group");
+ UNREACHABLE();
+ }
+ ASSERT(INITIAL == stored_state->group_type());
+ // Parsing completed successfully.
+ return builder->ToRegExp();
+ case ')': {
+ if (!stored_state->IsSubexpression()) {
+ ReportError("Unmatched ')'");
+ UNREACHABLE();
+ }
+ ASSERT(INITIAL != stored_state->group_type());
+
+ Advance();
+ // End disjunction parsing and convert builder content to new single
+ // regexp atom.
+ RegExpTree* body = builder->ToRegExp();
+
+ intptr_t end_capture_index = captures_started();
+
+ intptr_t capture_index = stored_state->capture_index();
+ SubexpressionType group_type = stored_state->group_type();
+
+ // Restore previous state.
+ stored_state = stored_state->previous_state();
+ builder = stored_state->builder();
+
+ // Build result of subexpression.
+ if (group_type == CAPTURE) {
+ RegExpCapture* capture = new(I) RegExpCapture(body, capture_index);
+ (*captures_)[capture_index - 1] = capture;
+ body = capture;
+ } else if (group_type != GROUPING) {
+ ASSERT(group_type == POSITIVE_LOOKAHEAD ||
+ group_type == NEGATIVE_LOOKAHEAD);
+ bool is_positive = (group_type == POSITIVE_LOOKAHEAD);
+ body = new(I) RegExpLookahead(body,
+ is_positive,
+ end_capture_index - capture_index,
+ capture_index);
+ }
+ builder->AddAtom(body);
+ // For compatibility with JSC and ES3, we allow quantifiers after
+ // lookaheads, and break in all cases.
+ break;
+ }
+ case '|': {
+ Advance();
+ builder->NewAlternative();
+ continue;
+ }
+ case '*':
+ case '+':
+ case '?':
+ ReportError("Nothing to repeat");
+ UNREACHABLE();
+ case '^': {
+ Advance();
+ if (multiline_) {
+ builder->AddAssertion(
+ new(I) RegExpAssertion(RegExpAssertion::START_OF_LINE));
+ } else {
+ builder->AddAssertion(
+ new(I) RegExpAssertion(RegExpAssertion::START_OF_INPUT));
+ set_contains_anchor();
+ }
+ continue;
+ }
+ case '$': {
+ Advance();
+ RegExpAssertion::AssertionType assertion_type =
+ multiline_ ? RegExpAssertion::END_OF_LINE :
+ RegExpAssertion::END_OF_INPUT;
+ builder->AddAssertion(new RegExpAssertion(assertion_type));
+ continue;
+ }
+ case '.': {
+ Advance();
+ // everything except \x0a, \x0d, \u2028 and \u2029
+ ZoneGrowableArray<CharacterRange>* ranges =
+ new ZoneGrowableArray<CharacterRange>(2);
+ CharacterRange::AddClassEscape('.', ranges);
+ RegExpTree* atom = new RegExpCharacterClass(ranges, false);
+ builder->AddAtom(atom);
+ break;
+ }
+ case '(': {
+ SubexpressionType subexpr_type = CAPTURE;
+ Advance();
+ if (current() == '?') {
+ switch (Next()) {
+ case ':':
+ subexpr_type = GROUPING;
+ break;
+ case '=':
+ subexpr_type = POSITIVE_LOOKAHEAD;
+ break;
+ case '!':
+ subexpr_type = NEGATIVE_LOOKAHEAD;
+ break;
+ default:
+ ReportError("Invalid group");
+ UNREACHABLE();
+ }
+ Advance(2);
+ } else {
+ if (captures_ == NULL) {
+ captures_ = new ZoneGrowableArray<RegExpCapture*>(2);
+ }
+ if (captures_started() >= kMaxCaptures) {
+ ReportError("Too many captures");
+ UNREACHABLE();
+ }
+ captures_->Add(NULL);
+ }
+ // Store current state and begin new disjunction parsing.
+ stored_state = new RegExpParserState(stored_state, subexpr_type,
+ captures_started(), I);
+ builder = stored_state->builder();
+ continue;
+ }
+ case '[': {
+ RegExpTree* atom = ParseCharacterClass();
+ builder->AddAtom(atom);
+ break;
+ }
+ // Atom ::
+ // \ AtomEscape
+ case '\\':
+ switch (Next()) {
+ case kEndMarker:
+ ReportError("\\ at end of pattern");
+ UNREACHABLE();
+ 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': {
+ uint32_t c = Next();
+ Advance(2);
+ ZoneGrowableArray<CharacterRange>* ranges =
+ new ZoneGrowableArray<CharacterRange>(2);
+ CharacterRange::AddClassEscape(c, ranges);
+ RegExpTree* atom = new RegExpCharacterClass(ranges, false);
+ builder->AddAtom(atom);
+ break;
+ }
+ case '1': case '2': case '3': case '4': case '5': case '6':
+ case '7': case '8': case '9': {
+ intptr_t index = 0;
+ if (ParseBackReferenceIndex(&index)) {
+ RegExpCapture* capture = NULL;
+ if (captures_ != NULL && index <= captures_->length()) {
+ capture = captures_->At(index - 1);
+ }
+ if (capture == NULL) {
+ builder->AddEmpty();
+ break;
+ }
+ RegExpTree* atom = new RegExpBackReference(capture);
+ builder->AddAtom(atom);
+ break;
+ }
+ uint32_t 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();
+ uint32_t octal = ParseOctalLiteral();
+ builder->AddCharacter(octal);
+ break;
+ }
+ // ControlEscape :: one of
+ // f n r t v
+ case 'f':
+ Advance(2);
+ builder->AddCharacter('\f');
+ break;
+ case 'n':
+ Advance(2);
+ builder->AddCharacter('\n');
+ break;
+ case 'r':
+ Advance(2);
+ builder->AddCharacter('\r');
+ break;
+ case 't':
+ Advance(2);
+ builder->AddCharacter('\t');
+ break;
+ case 'v':
+ Advance(2);
+ builder->AddCharacter('\v');
+ break;
+ case 'c': {
+ Advance();
+ uint32_t controlLetter = Next();
+ // Special case if it is an ASCII letter.
+ // Convert lower case letters to uppercase.
+ uint32_t letter = controlLetter & ~('a' ^ 'A');
+ if (letter < 'A' || 'Z' < letter) {
+ // controlLetter is not in range 'A'-'Z' or 'a'-'z'.
+ // This is outside the specification. We match JSC in
+ // reading the backslash as a literal character instead
+ // of as starting an escape.
+ builder->AddCharacter('\\');
+ } else {
+ Advance(2);
+ builder->AddCharacter(controlLetter & 0x1f);
+ }
+ break;
+ }
+ case 'x': {
+ Advance(2);
+ uint32_t value;
+ if (ParseHexEscape(2, &value)) {
+ builder->AddCharacter(value);
+ } else {
+ builder->AddCharacter('x');
+ }
+ break;
+ }
+ case 'u': {
+ Advance(2);
+ uint32_t value;
+ if (ParseHexEscape(4, &value)) {
+ builder->AddCharacter(value);
+ } else {
+ builder->AddCharacter('u');
+ }
+ break;
+ }
+ default:
+ // Identity escape.
+ builder->AddCharacter(Next());
+ Advance(2);
+ break;
+ }
+ break;
+ case '{': {
+ intptr_t dummy;
+ if (ParseIntervalQuantifier(&dummy, &dummy)) {
+ ReportError("Nothing to repeat");
+ UNREACHABLE();
+ }
+ // fallthrough
+ }
+ default:
+ builder->AddCharacter(current());
+ Advance();
+ break;
+ } // end switch(current())
+
+ intptr_t min;
+ intptr_t max;
+ switch (current()) {
+ // QuantifierPrefix ::
+ // *
+ // +
+ // ?
+ // {
+ case '*':
+ min = 0;
+ max = RegExpTree::kInfinity;
+ Advance();
+ break;
+ case '+':
+ min = 1;
+ max = RegExpTree::kInfinity;
+ Advance();
+ break;
+ case '?':
+ min = 0;
+ max = 1;
+ Advance();
+ break;
+ case '{':
+ if (ParseIntervalQuantifier(&min, &max)) {
+ if (max < min) {
+ ReportError("numbers out of order in {} quantifier.");
+ UNREACHABLE();
+ }
+ break;
+ } else {
+ continue;
+ }
+ default:
+ continue;
+ }
+ RegExpQuantifier::QuantifierType quantifier_type = RegExpQuantifier::GREEDY;
+ if (current() == '?') {
+ quantifier_type = RegExpQuantifier::NON_GREEDY;
+ Advance();
+ } else if (FLAG_regexp_possessive_quantifier && current() == '+') {
+ // FLAG_regexp_possessive_quantifier is a debug-only flag.
+ quantifier_type = RegExpQuantifier::POSSESSIVE;
+ Advance();
+ }
+ builder->AddQuantifierToAtom(min, max, quantifier_type);
+ }
+}
+
+
+static const uint16_t kNoCharClass = 0;
+
+// Adds range or pre-defined character class to character ranges.
+// If char_class is not kInvalidClass, it's interpreted as a class
+// escape (i.e., 's' means whitespace, from '\s').
+static inline void AddRangeOrEscape(ZoneGrowableArray<CharacterRange>* ranges,
+ uint16_t char_class,
+ CharacterRange range) {
+ if (char_class != kNoCharClass) {
+ CharacterRange::AddClassEscape(char_class, ranges);
+ } else {
+ ranges->Add(range);
+ }
+}
+
+
+RegExpTree* RegExpParser::ParseCharacterClass() {
+ static const char* kUnterminated = "Unterminated character class";
+ static const char* kRangeOutOfOrder = "Range out of order in character class";
+
+ ASSERT(current() == '[');
+ Advance();
+ bool is_negated = false;
+ if (current() == '^') {
+ is_negated = true;
+ Advance();
+ }
+ ZoneGrowableArray<CharacterRange>* ranges =
+ new(I) ZoneGrowableArray<CharacterRange>(2);
+ while (has_more() && current() != ']') {
+ uint16_t char_class = kNoCharClass;
+ CharacterRange first = ParseClassAtom(&char_class);
+ 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() == ']') {
+ AddRangeOrEscape(ranges, char_class, first);
+ ranges->Add(CharacterRange::Singleton('-'));
+ break;
+ }
+ uint16_t char_class_2 = kNoCharClass;
+ CharacterRange next = ParseClassAtom(&char_class_2);
+ if (char_class != kNoCharClass || char_class_2 != kNoCharClass) {
+ // Either end is an escaped character class. Treat the '-' verbatim.
+ AddRangeOrEscape(ranges, char_class, first);
+ ranges->Add(CharacterRange::Singleton('-'));
+ AddRangeOrEscape(ranges, char_class_2, next);
+ continue;
+ }
+ if (first.from() > next.to()) {
+ ReportError(kRangeOutOfOrder);
+ UNREACHABLE();
+ }
+ ranges->Add(CharacterRange::Range(first.from(), next.to()));
+ } else {
+ AddRangeOrEscape(ranges, char_class, first);
+ }
+ }
+ if (!has_more()) {
+ ReportError(kUnterminated);
+ UNREACHABLE();
+ }
+ Advance();
+ if (ranges->length() == 0) {
+ ranges->Add(CharacterRange::Everything());
+ is_negated = !is_negated;
+ }
+ return new(I) RegExpCharacterClass(ranges, is_negated);
+}
+
+
+#ifdef DEBUG
+// Currently only used in an ASSERT.
+static bool IsSpecialClassEscape(uint32_t c) {
+ switch (c) {
+ case 'd': case 'D':
+ case 's': case 'S':
+ case 'w': case 'W':
+ return true;
+ default:
+ return false;
+ }
+}
+#endif
+
+
+// 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() {
+ // Start with captures started previous to current position
+ intptr_t capture_count = captures_started();
+ // Add count of captures after this position.
+ intptr_t n;
+ while ((n = current()) != kEndMarker) {
+ Advance();
+ switch (n) {
+ case '\\':
+ Advance();
+ break;
+ case '[': {
+ intptr_t c;
+ while ((c = current()) != kEndMarker) {
+ Advance();
+ if (c == '\\') {
+ Advance();
+ } else {
+ if (c == ']') break;
+ }
+ }
+ break;
+ }
+ case '(':
+ if (current() != '?') capture_count++;
+ break;
+ }
+ }
+ capture_count_ = capture_count;
+ is_scanned_for_captures_ = true;
+}
+
+
+static inline bool IsDecimalDigit(int32_t c) {
+ return '0' <= c && c <= '9';
+}
+
+
+bool RegExpParser::ParseBackReferenceIndex(intptr_t* index_out) {
+ ASSERT('\\' == current());
+ ASSERT('1' <= Next() && Next() <= '9');
+ // Try to parse a decimal literal that is no greater than the total number
+ // of left capturing parentheses in the input.
+ intptr_t start = position();
+ intptr_t value = Next() - '0';
+ Advance(2);
+ while (true) {
+ uint32_t c = current();
+ if (IsDecimalDigit(c)) {
+ value = 10 * value + (c - '0');
+ if (value > kMaxCaptures) {
+ Reset(start);
+ return false;
+ }
+ Advance();
+ } else {
+ break;
+ }
+ }
+ if (value > captures_started()) {
+ if (!is_scanned_for_captures_) {
+ intptr_t saved_position = position();
+ ScanForCaptures();
+ Reset(saved_position);
+ }
+ if (value > capture_count_) {
+ Reset(start);
+ return false;
+ }
+ }
+ *index_out = value;
+ return true;
+}
+
+
+// QuantifierPrefix ::
+// { DecimalDigits }
+// { DecimalDigits , }
+// { DecimalDigits , DecimalDigits }
+//
+// Returns true if parsing succeeds, and set the min_out and max_out
+// values. Values are truncated to RegExpTree::kInfinity if they overflow.
+bool RegExpParser::ParseIntervalQuantifier(intptr_t* min_out,
+ intptr_t* max_out) {
+ ASSERT(current() == '{');
+ intptr_t start = position();
+ Advance();
+ intptr_t min = 0;
+ if (!IsDecimalDigit(current())) {
+ Reset(start);
+ return false;
+ }
+ while (IsDecimalDigit(current())) {
+ intptr_t next = current() - '0';
+ if (min > (RegExpTree::kInfinity - next) / 10) {
+ // Overflow. Skip past remaining decimal digits and return -1.
+ do {
+ Advance();
+ } while (IsDecimalDigit(current()));
+ min = RegExpTree::kInfinity;
+ break;
+ }
+ min = 10 * min + next;
+ Advance();
+ }
+ intptr_t max = 0;
+ if (current() == '}') {
+ max = min;
+ Advance();
+ } else if (current() == ',') {
+ Advance();
+ if (current() == '}') {
+ max = RegExpTree::kInfinity;
+ Advance();
+ } else {
+ while (IsDecimalDigit(current())) {
+ intptr_t next = current() - '0';
+ if (max > (RegExpTree::kInfinity - next) / 10) {
+ do {
+ Advance();
+ } while (IsDecimalDigit(current()));
+ max = RegExpTree::kInfinity;
+ break;
+ }
+ max = 10 * max + next;
+ Advance();
+ }
+ if (current() != '}') {
+ Reset(start);
+ return false;
+ }
+ Advance();
+ }
+ } else {
+ Reset(start);
+ return false;
+ }
+ *min_out = min;
+ *max_out = max;
+ return true;
+}
+
+
+uint32_t RegExpParser::ParseOctalLiteral() {
+ ASSERT(('0' <= current() && current() <= '7') || current() == kEndMarker);
+ // For compatibility with some other browsers (not all), we parse
+ // up to three octal digits with a value below 256.
+ uint32_t value = current() - '0';
+ Advance();
+ if ('0' <= current() && current() <= '7') {
+ value = value * 8 + current() - '0';
+ Advance();
+ if (value < 32 && '0' <= current() && current() <= '7') {
+ value = value * 8 + current() - '0';
+ Advance();
+ }
+ }
+ return value;
+}
+
+
+// Returns the value (0 .. 15) of a hexadecimal character c.
+// If c is not a legal hexadecimal character, returns a value < 0.
+static inline intptr_t HexValue(uint32_t c) {
+ c -= '0';
+ if (static_cast<unsigned>(c) <= 9) return c;
+ c = (c | 0x20) - ('a' - '0'); // detect 0x11..0x16 and 0x31..0x36.
+ if (static_cast<unsigned>(c) <= 5) return c + 10;
+ return -1;
+}
+
+
+bool RegExpParser::ParseHexEscape(intptr_t length, uint32_t *value) {
+ intptr_t start = position();
+ uint32_t val = 0;
+ bool done = false;
+ for (intptr_t i = 0; !done; i++) {
+ uint32_t c = current();
+ intptr_t d = HexValue(c);
+ if (d < 0) {
+ Reset(start);
+ return false;
+ }
+ val = val * 16 + d;
+ Advance();
+ if (i == length - 1) {
+ done = true;
+ }
+ }
+ *value = val;
+ return true;
+}
+
+
+uint32_t RegExpParser::ParseClassCharacterEscape() {
+ ASSERT(current() == '\\');
+ DEBUG_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': {
+ uint32_t controlLetter = Next();
+ uint32_t letter = controlLetter & ~('A' ^ 'a');
+ // For compatibility with JSC, inside a character class
+ // we also accept digits and underscore as control characters.
+ if ((controlLetter >= '0' && controlLetter <= '9') ||
+ controlLetter == '_' ||
+ (letter >= 'A' && letter <= 'Z')) {
+ Advance(2);
+ // Control letters mapped to ASCII control characters in the range
+ // 0x00-0x1f.
+ return controlLetter & 0x1f;
+ }
+ // We match JSC in reading the backslash as a literal
+ // character instead of as starting an escape.
+ return '\\';
+ }
+ 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();
+ uint32_t value;
+ if (ParseHexEscape(2, &value)) {
+ return value;
+ }
+ // If \x is not followed by a two-digit hexadecimal, treat it
+ // as an identity escape.
+ return 'x';
+ }
+ case 'u': {
+ Advance();
+ uint32_t value;
+ if (ParseHexEscape(4, &value)) {
+ return value;
+ }
+ // If \u is not followed by a four-digit hexadecimal, treat it
+ // as an identity escape.
+ return 'u';
+ }
+ default: {
+ // Extended identity escape. We accept any character that hasn't
+ // been matched by a more specific case, not just the subset required
+ // by the ECMAScript specification.
+ uint32_t result = current();
+ Advance();
+ return result;
+ }
+ }
+ return 0;
+}
+
+
+CharacterRange RegExpParser::ParseClassAtom(uint16_t* char_class) {
+ ASSERT(0 == *char_class);
+ uint32_t 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.
+ }
+ case kEndMarker:
+ ReportError("\\ at end of pattern");
+ UNREACHABLE();
+ default:
+ uint32_t c = ParseClassCharacterEscape();
+ return CharacterRange::Singleton(c);
+ }
+ } else {
+ Advance();
+ return CharacterRange::Singleton(first);
+ }
+}
+
+} // namespace dart
« no previous file with comments | « runtime/vm/regexp_parser.h ('k') | runtime/vm/symbols.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698