diff options
Diffstat (limited to 'js/src/irregexp/RegExpParser.cpp')
| -rw-r--r-- | js/src/irregexp/RegExpParser.cpp | 1905 |
1 files changed, 1905 insertions, 0 deletions
diff --git a/js/src/irregexp/RegExpParser.cpp b/js/src/irregexp/RegExpParser.cpp new file mode 100644 index 000000000..ccc6ae3eb --- /dev/null +++ b/js/src/irregexp/RegExpParser.cpp @@ -0,0 +1,1905 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: */ + +// Copyright 2012 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 +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include "irregexp/RegExpParser.h" + +#include "frontend/TokenStream.h" + +using namespace js; +using namespace js::irregexp; + +// ---------------------------------------------------------------------------- +// RegExpBuilder + +RegExpBuilder::RegExpBuilder(LifoAlloc* alloc) + : alloc(alloc), + pending_empty_(false), + characters_(nullptr) +#ifdef DEBUG + , last_added_(ADD_NONE) +#endif +{} + +void +RegExpBuilder::FlushCharacters() +{ + pending_empty_ = false; + if (characters_ != nullptr) { + RegExpTree* atom = alloc->newInfallible<RegExpAtom>(characters_); + characters_ = nullptr; + text_.Add(alloc, atom); +#ifdef DEBUG + last_added_ = ADD_ATOM; +#endif + } +} + +void +RegExpBuilder::FlushText() +{ + FlushCharacters(); + int num_text = text_.length(); + if (num_text == 0) + return; + if (num_text == 1) { + terms_.Add(alloc, text_.last()); + } else { + RegExpText* text = alloc->newInfallible<RegExpText>(alloc); + for (int i = 0; i < num_text; i++) + text_.Get(i)->AppendToText(text); + terms_.Add(alloc, text); + } + text_.Clear(); +} + +void +RegExpBuilder::AddCharacter(char16_t c) +{ + pending_empty_ = false; + if (characters_ == nullptr) + characters_ = alloc->newInfallible<CharacterVector>(*alloc); + characters_->append(c); +#ifdef DEBUG + last_added_ = ADD_CHAR; +#endif +} + +void +RegExpBuilder::AddEmpty() +{ + pending_empty_ = true; +} + +void +RegExpBuilder::AddAtom(RegExpTree* term) +{ + if (term->IsEmpty()) { + AddEmpty(); + return; + } + if (term->IsTextElement()) { + FlushCharacters(); + text_.Add(alloc, term); + } else { + FlushText(); + terms_.Add(alloc, term); + } +#ifdef DEBUG + last_added_ = ADD_ATOM; +#endif +} + +void +RegExpBuilder::AddAssertion(RegExpTree* assert) +{ + FlushText(); + terms_.Add(alloc, assert); +#ifdef DEBUG + last_added_ = ADD_ASSERT; +#endif +} + +void +RegExpBuilder::NewAlternative() +{ + FlushTerms(); +} + +void +RegExpBuilder::FlushTerms() +{ + FlushText(); + int num_terms = terms_.length(); + RegExpTree* alternative; + if (num_terms == 0) + alternative = RegExpEmpty::GetInstance(); + else if (num_terms == 1) + alternative = terms_.last(); + else + alternative = alloc->newInfallible<RegExpAlternative>(terms_.GetList(alloc)); + alternatives_.Add(alloc, alternative); + terms_.Clear(); +#ifdef DEBUG + last_added_ = ADD_NONE; +#endif +} + +RegExpTree* +RegExpBuilder::ToRegExp() +{ + FlushTerms(); + int num_alternatives = alternatives_.length(); + if (num_alternatives == 0) { + return RegExpEmpty::GetInstance(); + } + if (num_alternatives == 1) { + return alternatives_.last(); + } + return alloc->newInfallible<RegExpDisjunction>(alternatives_.GetList(alloc)); +} + +void +RegExpBuilder::AddQuantifierToAtom(int min, int max, + RegExpQuantifier::QuantifierType quantifier_type) +{ + if (pending_empty_) { + pending_empty_ = false; + return; + } + RegExpTree* atom; + if (characters_ != nullptr) { + MOZ_ASSERT(last_added_ == ADD_CHAR); + // Last atom was character. + CharacterVector* char_vector = characters_; + int num_chars = char_vector->length(); + if (num_chars > 1) { + CharacterVector* prefix = alloc->newInfallible<CharacterVector>(*alloc); + prefix->append(char_vector->begin(), num_chars - 1); + text_.Add(alloc, alloc->newInfallible<RegExpAtom>(prefix)); + char_vector = alloc->newInfallible<CharacterVector>(*alloc); + char_vector->append((*characters_)[num_chars - 1]); + } + characters_ = nullptr; + atom = alloc->newInfallible<RegExpAtom>(char_vector); + FlushText(); + } else if (text_.length() > 0) { + MOZ_ASSERT(last_added_ == ADD_ATOM); + atom = text_.RemoveLast(); + FlushText(); + } else if (terms_.length() > 0) { + MOZ_ASSERT(last_added_ == ADD_ATOM); + atom = terms_.RemoveLast(); + if (atom->max_match() == 0) { + // Guaranteed to only match an empty string. +#ifdef DEBUG + last_added_ = ADD_TERM; +#endif + if (min == 0) + return; + terms_.Add(alloc, atom); + return; + } + } else { + // Only call immediately after adding an atom or character! + MOZ_CRASH("Bad call"); + } + terms_.Add(alloc, alloc->newInfallible<RegExpQuantifier>(min, max, quantifier_type, atom)); +#ifdef DEBUG + last_added_ = ADD_TERM; +#endif +} + +// ---------------------------------------------------------------------------- +// RegExpParser + +template <typename CharT> +RegExpParser<CharT>::RegExpParser(frontend::TokenStream& ts, LifoAlloc* alloc, + const CharT* chars, const CharT* end, bool multiline_mode, + bool unicode, bool ignore_case) + : ts(ts), + alloc(alloc), + captures_(nullptr), + next_pos_(chars), + end_(end), + current_(kEndMarker), + capture_count_(0), + has_more_(true), + multiline_(multiline_mode), + unicode_(unicode), + ignore_case_(ignore_case), + simple_(false), + contains_anchor_(false), + is_scanned_for_captures_(false) +{ + Advance(); +} + +template <typename CharT> +RegExpTree* +RegExpParser<CharT>::ReportError(unsigned errorNumber) +{ + gc::AutoSuppressGC suppressGC(ts.context()); + ts.reportError(errorNumber); + return nullptr; +} + +template <typename CharT> +void +RegExpParser<CharT>::Advance() +{ + if (next_pos_ < end_) { + current_ = *next_pos_; + next_pos_++; + } else { + current_ = kEndMarker; + has_more_ = false; + } +} + +// Returns the value (0 .. 15) of a hexadecimal character c. +// If c is not a legal hexadecimal character, returns a value < 0. +inline int +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; +} + +template <typename CharT> +widechar +RegExpParser<CharT>::ParseOctalLiteral() +{ + MOZ_ASSERT('0' <= current() && current() <= '7'); + // For compatibility with some other browsers (not all), we parse + // up to three octal digits with a value below 256. + widechar 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; +} + +template <typename CharT> +bool +RegExpParser<CharT>::ParseHexEscape(int length, widechar* value) +{ + const CharT* start = position(); + uint32_t val = 0; + bool done = false; + for (int i = 0; !done; i++) { + widechar c = current(); + int 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; +} + +template <typename CharT> +bool +RegExpParser<CharT>::ParseBracedHexEscape(widechar* value) +{ + MOZ_ASSERT(current() == '{'); + Advance(); + + bool first = true; + uint32_t code = 0; + while (true) { + widechar c = current(); + if (c == kEndMarker) { + ReportError(JSMSG_INVALID_UNICODE_ESCAPE); + return false; + } + if (c == '}') { + if (first) { + ReportError(JSMSG_INVALID_UNICODE_ESCAPE); + return false; + } + Advance(); + break; + } + + int d = HexValue(c); + if (d < 0) { + ReportError(JSMSG_INVALID_UNICODE_ESCAPE); + return false; + } + code = (code << 4) | d; + if (code > unicode::NonBMPMax) { + ReportError(JSMSG_UNICODE_OVERFLOW); + return false; + } + Advance(); + first = false; + } + + *value = code; + return true; +} + +template <typename CharT> +bool +RegExpParser<CharT>::ParseTrailSurrogate(widechar* value) +{ + if (current() != '\\') + return false; + + const CharT* start = position(); + Advance(); + if (current() != 'u') { + Reset(start); + return false; + } + Advance(); + if (!ParseHexEscape(4, value)) { + Reset(start); + return false; + } + if (!unicode::IsTrailSurrogate(*value)) { + Reset(start); + return false; + } + return true; +} + +template <typename CharT> +bool +RegExpParser<CharT>::ParseRawSurrogatePair(char16_t* lead, char16_t* trail) +{ + widechar c1 = current(); + if (!unicode::IsLeadSurrogate(c1)) + return false; + + const CharT* start = position(); + Advance(); + widechar c2 = current(); + if (!unicode::IsTrailSurrogate(c2)) { + Reset(start); + return false; + } + Advance(); + *lead = c1; + *trail = c2; + return true; +} + +static inline RegExpTree* +RangeAtom(LifoAlloc* alloc, char16_t from, char16_t to) +{ + CharacterRangeVector* ranges = alloc->newInfallible<CharacterRangeVector>(*alloc); + ranges->append(CharacterRange::Range(from, to)); + return alloc->newInfallible<RegExpCharacterClass>(ranges, false); +} + +static inline RegExpTree* +NegativeLookahead(LifoAlloc* alloc, char16_t from, char16_t to) +{ + return alloc->newInfallible<RegExpLookahead>(RangeAtom(alloc, from, to), false, 0, 0); +} + +static bool +IsSyntaxCharacter(widechar c) +{ + switch (c) { + case '^': + case '$': + case '\\': + case '.': + case '*': + case '+': + case '?': + case '(': + case ')': + case '[': + case ']': + case '{': + case '}': + case '|': + case '/': + return true; + default: + return false; + } +} + +#ifdef DEBUG +// Currently only used in an assert.kASSERT. +static bool +IsSpecialClassEscape(widechar c) +{ + switch (c) { + case 'd': case 'D': + case 's': case 'S': + case 'w': case 'W': + return true; + default: + return false; + } +} +#endif + +template <typename CharT> +bool +RegExpParser<CharT>::ParseClassCharacterEscape(widechar* code) +{ + MOZ_ASSERT(current() == '\\'); + MOZ_ASSERT(has_next() && !IsSpecialClassEscape(Next())); + Advance(); + switch (current()) { + case 'b': + Advance(); + *code = '\b'; + return true; + // ControlEscape :: one of + // f n r t v + case 'f': + Advance(); + *code = '\f'; + return true; + case 'n': + Advance(); + *code = '\n'; + return true; + case 'r': + Advance(); + *code = '\r'; + return true; + case 't': + Advance(); + *code = '\t'; + return true; + case 'v': + Advance(); + *code = '\v'; + return true; + case 'c': { + widechar controlLetter = Next(); + widechar letter = controlLetter & ~('A' ^ 'a'); + // For compatibility with JSC, inside a character class + // we also accept digits and underscore as control characters, + // but only in non-unicode mode + if ((!unicode_ && + ((controlLetter >= '0' && controlLetter <= '9') || + controlLetter == '_')) || + (letter >= 'A' && letter <= 'Z')) + { + Advance(2); + // Control letters mapped to ASCII control characters in the range + // 0x00-0x1f. + *code = controlLetter & 0x1f; + return true; + } + if (unicode_) { + ReportError(JSMSG_INVALID_IDENTITY_ESCAPE); + return false; + } + // We match JSC in reading the backslash as a literal + // character instead of as starting an escape. + *code = '\\'; + return true; + } + case '0': case '1': case '2': case '3': case '4': case '5': + case '6': case '7': + if (unicode_) { + if (current() == '0') { + Advance(); + *code = 0; + return true; + } + ReportError(JSMSG_INVALID_IDENTITY_ESCAPE); + return false; + } + // For compatibility, outside of unicode mode, 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. + *code = ParseOctalLiteral(); + return true; + case 'x': { + Advance(); + widechar value; + if (ParseHexEscape(2, &value)) { + *code = value; + return true; + } + if (unicode_) { + ReportError(JSMSG_INVALID_IDENTITY_ESCAPE); + return false; + } + // If \x is not followed by a two-digit hexadecimal, treat it + // as an identity escape in non-unicode mode. + *code = 'x'; + return true; + } + case 'u': { + Advance(); + widechar value; + if (unicode_) { + if (current() == '{') { + if (!ParseBracedHexEscape(&value)) + return false; + *code = value; + return true; + } + if (ParseHexEscape(4, &value)) { + if (unicode::IsLeadSurrogate(value)) { + widechar trail; + if (ParseTrailSurrogate(&trail)) { + *code = unicode::UTF16Decode(value, trail); + return true; + } + } + *code = value; + return true; + } + ReportError(JSMSG_INVALID_UNICODE_ESCAPE); + return false; + } + if (ParseHexEscape(4, &value)) { + *code = value; + return true; + } + // If \u is not followed by a four-digit or braced hexadecimal, treat it + // as an identity escape. + *code = 'u'; + return true; + } + default: { + // Extended identity escape (non-unicode only). We accept any character + // that hasn't been matched by a more specific case, not just the subset + // required by the ECMAScript specification. + widechar result = current(); + if (unicode_ && result != '-' && !IsSyntaxCharacter(result)) { + ReportError(JSMSG_INVALID_IDENTITY_ESCAPE); + return false; + } + Advance(); + *code = result; + return true; + } + } + return true; +} + +class WideCharRange +{ + public: + WideCharRange() + : from_(0), to_(0) + {} + + WideCharRange(widechar from, widechar to) + : from_(from), to_(to) + {} + + static inline WideCharRange Singleton(widechar value) { + return WideCharRange(value, value); + } + static inline WideCharRange Range(widechar from, widechar to) { + MOZ_ASSERT(from <= to); + return WideCharRange(from, to); + } + + bool Contains(widechar i) const { return from_ <= i && i <= to_; } + widechar from() const { return from_; } + widechar to() const { return to_; } + + private: + widechar from_; + widechar to_; +}; + +typedef InfallibleVector<WideCharRange, 1> WideCharRangeVector; + +static inline CharacterRange +LeadSurrogateRange() +{ + return CharacterRange::Range(unicode::LeadSurrogateMin, unicode::LeadSurrogateMax); +} + +static inline CharacterRange +TrailSurrogateRange() +{ + return CharacterRange::Range(unicode::TrailSurrogateMin, unicode::TrailSurrogateMax); +} + +static inline WideCharRange +NonBMPRange() +{ + return WideCharRange::Range(unicode::NonBMPMin, unicode::NonBMPMax); +} + +static const char16_t kNoCharClass = 0; + +// Adds a character 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 +AddCharOrEscape(LifoAlloc* alloc, + CharacterRangeVector* ranges, + char16_t char_class, + widechar c) +{ + if (char_class != kNoCharClass) + CharacterRange::AddClassEscape(alloc, char_class, ranges); + else + ranges->append(CharacterRange::Singleton(c)); +} + +static inline void +AddCharOrEscapeUnicode(LifoAlloc* alloc, + CharacterRangeVector* ranges, + CharacterRangeVector* lead_ranges, + CharacterRangeVector* trail_ranges, + WideCharRangeVector* wide_ranges, + char16_t char_class, + widechar c, + bool ignore_case) +{ + if (char_class != kNoCharClass) { + CharacterRange::AddClassEscapeUnicode(alloc, char_class, ranges, ignore_case); + switch (char_class) { + case 'S': + case 'W': + case 'D': + lead_ranges->append(LeadSurrogateRange()); + trail_ranges->append(TrailSurrogateRange()); + wide_ranges->append(NonBMPRange()); + break; + case '.': + MOZ_CRASH("Bad char_class!"); + } + return; + } + + if (unicode::IsLeadSurrogate(c)) + lead_ranges->append(CharacterRange::Singleton(c)); + else if (unicode::IsTrailSurrogate(c)) + trail_ranges->append(CharacterRange::Singleton(c)); + else if (c >= unicode::NonBMPMin) + wide_ranges->append(WideCharRange::Singleton(c)); + else + ranges->append(CharacterRange::Singleton(c)); +} + +static inline void +AddUnicodeRange(LifoAlloc* alloc, + CharacterRangeVector* ranges, + CharacterRangeVector* lead_ranges, + CharacterRangeVector* trail_ranges, + WideCharRangeVector* wide_ranges, + widechar first, + widechar next) +{ + MOZ_ASSERT(first <= next); + if (first < unicode::LeadSurrogateMin) { + if (next < unicode::LeadSurrogateMin) { + ranges->append(CharacterRange::Range(first, next)); + return; + } + ranges->append(CharacterRange::Range(first, unicode::LeadSurrogateMin - 1)); + first = unicode::LeadSurrogateMin; + } + if (first <= unicode::LeadSurrogateMax) { + if (next <= unicode::LeadSurrogateMax) { + lead_ranges->append(CharacterRange::Range(first, next)); + return; + } + lead_ranges->append(CharacterRange::Range(first, unicode::LeadSurrogateMax)); + first = unicode::LeadSurrogateMax + 1; + } + MOZ_ASSERT(unicode::LeadSurrogateMax + 1 == unicode::TrailSurrogateMin); + if (first <= unicode::TrailSurrogateMax) { + if (next <= unicode::TrailSurrogateMax) { + trail_ranges->append(CharacterRange::Range(first, next)); + return; + } + trail_ranges->append(CharacterRange::Range(first, unicode::TrailSurrogateMax)); + first = unicode::TrailSurrogateMax + 1; + } + if (first <= unicode::UTF16Max) { + if (next <= unicode::UTF16Max) { + ranges->append(CharacterRange::Range(first, next)); + return; + } + ranges->append(CharacterRange::Range(first, unicode::UTF16Max)); + first = unicode::NonBMPMin; + } + MOZ_ASSERT(unicode::UTF16Max + 1 == unicode::NonBMPMin); + wide_ranges->append(WideCharRange::Range(first, next)); +} + +// Negate a vector of ranges by subtracting its ranges from a range +// encompassing the full range of possible values. +template <typename RangeType> +static inline void +NegateUnicodeRanges(LifoAlloc* alloc, InfallibleVector<RangeType, 1>** ranges, + RangeType full_range) +{ + typedef InfallibleVector<RangeType, 1> RangeVector; + RangeVector* tmp_ranges = alloc->newInfallible<RangeVector>(*alloc); + tmp_ranges->append(full_range); + RangeVector* result_ranges = alloc->newInfallible<RangeVector>(*alloc); + + // Perform the following calculation: + // result_ranges = tmp_ranges - ranges + // with the following steps: + // result_ranges = tmp_ranges - ranges[0] + // SWAP(result_ranges, tmp_ranges) + // result_ranges = tmp_ranges - ranges[1] + // SWAP(result_ranges, tmp_ranges) + // ... + // result_ranges = tmp_ranges - ranges[N-1] + // SWAP(result_ranges, tmp_ranges) + // The last SWAP is just for simplicity of the loop. + for (size_t i = 0; i < (*ranges)->length(); i++) { + result_ranges->clear(); + + const RangeType& range = (**ranges)[i]; + for (size_t j = 0; j < tmp_ranges->length(); j++) { + const RangeType& tmpRange = (*tmp_ranges)[j]; + auto from1 = tmpRange.from(); + auto to1 = tmpRange.to(); + auto from2 = range.from(); + auto to2 = range.to(); + + if (from1 < from2) { + if (to1 < from2) { + result_ranges->append(tmpRange); + } else if (to1 <= to2) { + result_ranges->append(RangeType::Range(from1, from2 - 1)); + } else { + result_ranges->append(RangeType::Range(from1, from2 - 1)); + result_ranges->append(RangeType::Range(to2 + 1, to1)); + } + } else if (from1 <= to2) { + if (to1 > to2) + result_ranges->append(RangeType::Range(to2 + 1, to1)); + } else { + result_ranges->append(tmpRange); + } + } + + auto tmp = tmp_ranges; + tmp_ranges = result_ranges; + result_ranges = tmp; + } + + // After the loop, result is pointed at by tmp_ranges, instead of + // result_ranges. + *ranges = tmp_ranges; +} + +static bool +WideCharRangesContain(WideCharRangeVector* wide_ranges, widechar c) +{ + for (size_t i = 0; i < wide_ranges->length(); i++) { + const WideCharRange& range = (*wide_ranges)[i]; + if (range.Contains(c)) + return true; + } + return false; +} + +static void +CalculateCaseInsensitiveRanges(LifoAlloc* alloc, widechar from, widechar to, int32_t diff, + WideCharRangeVector* wide_ranges, + WideCharRangeVector** tmp_wide_ranges) +{ + widechar contains_from = 0; + widechar contains_to = 0; + for (widechar c = from; c <= to; c++) { + if (WideCharRangesContain(wide_ranges, c) && + !WideCharRangesContain(wide_ranges, c + diff)) + { + if (contains_from == 0) + contains_from = c; + contains_to = c; + } else if (contains_from != 0) { + if (!*tmp_wide_ranges) + *tmp_wide_ranges = alloc->newInfallible<WideCharRangeVector>(*alloc); + + (*tmp_wide_ranges)->append(WideCharRange::Range(contains_from + diff, + contains_to + diff)); + contains_from = 0; + } + } + + if (contains_from != 0) { + if (!*tmp_wide_ranges) + *tmp_wide_ranges = alloc->newInfallible<WideCharRangeVector>(*alloc); + + (*tmp_wide_ranges)->append(WideCharRange::Range(contains_from + diff, + contains_to + diff)); + } +} + +static RegExpTree* +UnicodeRangesAtom(LifoAlloc* alloc, + CharacterRangeVector* ranges, + CharacterRangeVector* lead_ranges, + CharacterRangeVector* trail_ranges, + WideCharRangeVector* wide_ranges, + bool is_negated, + bool ignore_case) +{ + // Calculate case folding for non-BMP first and negate the range if needed. + if (ignore_case) { + WideCharRangeVector* tmp_wide_ranges = nullptr; +#define CALL_CALC(FROM, TO, LEAD, TRAIL_FROM, TRAIL_TO, DIFF) \ + CalculateCaseInsensitiveRanges(alloc, FROM, TO, DIFF, wide_ranges, &tmp_wide_ranges); + FOR_EACH_NON_BMP_CASE_FOLDING(CALL_CALC) + FOR_EACH_NON_BMP_REV_CASE_FOLDING(CALL_CALC) +#undef CALL_CALC + + if (tmp_wide_ranges) { + for (size_t i = 0; i < tmp_wide_ranges->length(); i++) + wide_ranges->append((*tmp_wide_ranges)[i]); + } + } + + if (is_negated) { + NegateUnicodeRanges(alloc, &lead_ranges, LeadSurrogateRange()); + NegateUnicodeRanges(alloc, &trail_ranges, TrailSurrogateRange()); + NegateUnicodeRanges(alloc, &wide_ranges, NonBMPRange()); + } + + RegExpBuilder* builder = alloc->newInfallible<RegExpBuilder>(alloc); + + bool added = false; + + if (is_negated) { + ranges->append(LeadSurrogateRange()); + ranges->append(TrailSurrogateRange()); + } + if (ranges->length() > 0) { + builder->AddAtom(alloc->newInfallible<RegExpCharacterClass>(ranges, is_negated)); + added = true; + } + + if (lead_ranges->length() > 0) { + if (added) + builder->NewAlternative(); + builder->AddAtom(alloc->newInfallible<RegExpCharacterClass>(lead_ranges, false)); + builder->AddAtom(NegativeLookahead(alloc, unicode::TrailSurrogateMin, + unicode::TrailSurrogateMax)); + added = true; + } + + if (trail_ranges->length() > 0) { + if (added) + builder->NewAlternative(); + builder->AddAssertion(alloc->newInfallible<RegExpAssertion>( + RegExpAssertion::NOT_AFTER_LEAD_SURROGATE)); + builder->AddAtom(alloc->newInfallible<RegExpCharacterClass>(trail_ranges, false)); + added = true; + } + + for (size_t i = 0; i < wide_ranges->length(); i++) { + if (added) + builder->NewAlternative(); + + const WideCharRange& range = (*wide_ranges)[i]; + widechar from = range.from(); + widechar to = range.to(); + char16_t from_lead, from_trail; + char16_t to_lead, to_trail; + + unicode::UTF16Encode(from, &from_lead, &from_trail); + if (from == to) { + builder->AddCharacter(from_lead); + builder->AddCharacter(from_trail); + } else { + unicode::UTF16Encode(to, &to_lead, &to_trail); + if (from_lead == to_lead) { + MOZ_ASSERT(from_trail != to_trail); + builder->AddCharacter(from_lead); + builder->AddAtom(RangeAtom(alloc, from_trail, to_trail)); + } else if (from_trail == unicode::TrailSurrogateMin && + to_trail == unicode::TrailSurrogateMax) + { + builder->AddAtom(RangeAtom(alloc, from_lead, to_lead)); + builder->AddAtom(RangeAtom(alloc, unicode::TrailSurrogateMin, + unicode::TrailSurrogateMax)); + } else if (from_lead + 1 == to_lead) { + builder->AddCharacter(from_lead); + builder->AddAtom(RangeAtom(alloc, from_trail, unicode::TrailSurrogateMax)); + + builder->NewAlternative(); + + builder->AddCharacter(to_lead); + builder->AddAtom(RangeAtom(alloc, unicode::TrailSurrogateMin, to_trail)); + } else if (from_lead + 2 == to_lead) { + builder->AddCharacter(from_lead); + builder->AddAtom(RangeAtom(alloc, from_trail, unicode::TrailSurrogateMax)); + + builder->NewAlternative(); + + builder->AddCharacter(from_lead + 1); + builder->AddAtom(RangeAtom(alloc, unicode::TrailSurrogateMin, + unicode::TrailSurrogateMax)); + + builder->NewAlternative(); + + builder->AddCharacter(to_lead); + builder->AddAtom(RangeAtom(alloc, unicode::TrailSurrogateMin, to_trail)); + } else { + builder->AddCharacter(from_lead); + builder->AddAtom(RangeAtom(alloc, from_trail, unicode::TrailSurrogateMax)); + + builder->NewAlternative(); + + builder->AddAtom(RangeAtom(alloc, from_lead + 1, to_lead - 1)); + builder->AddAtom(RangeAtom(alloc, unicode::TrailSurrogateMin, + unicode::TrailSurrogateMax)); + + builder->NewAlternative(); + + builder->AddCharacter(to_lead); + builder->AddAtom(RangeAtom(alloc, unicode::TrailSurrogateMin, to_trail)); + } + } + added = true; + } + + return builder->ToRegExp(); +} + +template <typename CharT> +RegExpTree* +RegExpParser<CharT>::ParseCharacterClass() +{ + MOZ_ASSERT(current() == '['); + Advance(); + bool is_negated = false; + if (current() == '^') { + is_negated = true; + Advance(); + } + CharacterRangeVector* ranges = alloc->newInfallible<CharacterRangeVector>(*alloc); + CharacterRangeVector* lead_ranges = nullptr; + CharacterRangeVector* trail_ranges = nullptr; + WideCharRangeVector* wide_ranges = nullptr; + + if (unicode_) { + lead_ranges = alloc->newInfallible<CharacterRangeVector>(*alloc); + trail_ranges = alloc->newInfallible<CharacterRangeVector>(*alloc); + wide_ranges = alloc->newInfallible<WideCharRangeVector>(*alloc); + } + + while (has_more() && current() != ']') { + char16_t char_class = kNoCharClass; + widechar first = 0; + if (!ParseClassAtom(&char_class, &first)) + return nullptr; + 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() == ']') { + if (unicode_) { + AddCharOrEscapeUnicode(alloc, ranges, lead_ranges, trail_ranges, wide_ranges, + char_class, first, ignore_case_); + } else { + AddCharOrEscape(alloc, ranges, char_class, first); + } + ranges->append(CharacterRange::Singleton('-')); + break; + } + char16_t char_class_2 = kNoCharClass; + widechar next = 0; + if (!ParseClassAtom(&char_class_2, &next)) + return nullptr; + if (char_class != kNoCharClass || char_class_2 != kNoCharClass) { + if (unicode_) + return ReportError(JSMSG_RANGE_WITH_CLASS_ESCAPE); + + // Either end is an escaped character class. Treat the '-' verbatim. + AddCharOrEscape(alloc, ranges, char_class, first); + ranges->append(CharacterRange::Singleton('-')); + AddCharOrEscape(alloc, ranges, char_class_2, next); + continue; + } + if (first > next) + return ReportError(JSMSG_BAD_CLASS_RANGE); + if (unicode_) + AddUnicodeRange(alloc, ranges, lead_ranges, trail_ranges,wide_ranges, first, next); + else + ranges->append(CharacterRange::Range(first, next)); + } else { + if (unicode_) { + AddCharOrEscapeUnicode(alloc, ranges, lead_ranges, trail_ranges, wide_ranges, + char_class, first, ignore_case_); + } else { + AddCharOrEscape(alloc, ranges, char_class, first); + } + } + } + if (!has_more()) + return ReportError(JSMSG_UNTERM_CLASS); + Advance(); + if (!unicode_) { + if (ranges->length() == 0) { + ranges->append(CharacterRange::Everything()); + is_negated = !is_negated; + } + return alloc->newInfallible<RegExpCharacterClass>(ranges, is_negated); + } + + if (!is_negated && ranges->length() == 0 && lead_ranges->length() == 0 && + trail_ranges->length() == 0 && wide_ranges->length() == 0) + { + ranges->append(CharacterRange::Everything()); + return alloc->newInfallible<RegExpCharacterClass>(ranges, true); + } + + return UnicodeRangesAtom(alloc, ranges, lead_ranges, trail_ranges, wide_ranges, is_negated, + ignore_case_); +} + +template <typename CharT> +bool +RegExpParser<CharT>::ParseClassAtom(char16_t* char_class, widechar* value) +{ + MOZ_ASSERT(*char_class == kNoCharClass); + widechar first = current(); + if (first == '\\') { + switch (Next()) { + case 'w': case 'W': case 'd': case 'D': case 's': case 'S': { + *char_class = Next(); + Advance(2); + return true; + } + case kEndMarker: + return ReportError(JSMSG_ESCAPE_AT_END_OF_REGEXP); + default: + if (!ParseClassCharacterEscape(value)) + return false; + return true; + } + } else { + if (unicode_) { + char16_t lead, trail; + if (ParseRawSurrogatePair(&lead, &trail)) { + *value = unicode::UTF16Decode(lead, trail); + return true; + } + } + Advance(); + *value = first; + return true; + } +} + +// 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. +template <typename CharT> +void +RegExpParser<CharT>::ScanForCaptures() +{ + // Start with captures started previous to current position + int capture_count = captures_started(); + // Add count of captures after this position. + widechar n; + while ((n = current()) != kEndMarker) { + Advance(); + switch (n) { + case '\\': + Advance(); + break; + case '[': { + widechar 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; +} + +inline bool +IsInRange(int value, int lower_limit, int higher_limit) +{ + MOZ_ASSERT(lower_limit <= higher_limit); + return static_cast<unsigned int>(value - lower_limit) <= + static_cast<unsigned int>(higher_limit - lower_limit); +} + +inline bool +IsDecimalDigit(widechar c) +{ + // ECMA-262, 3rd, 7.8.3 (p 16) + return IsInRange(c, '0', '9'); +} + +template <typename CharT> +bool +RegExpParser<CharT>::ParseBackReferenceIndex(int* index_out) +{ + MOZ_ASSERT('\\' == current()); + MOZ_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. + const CharT* start = position(); + int value = Next() - '0'; + Advance(2); + while (true) { + widechar 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_) { + const CharT* 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. +template <typename CharT> +bool +RegExpParser<CharT>::ParseIntervalQuantifier(int* min_out, int* max_out) +{ + MOZ_ASSERT(current() == '{'); + const CharT* start = position(); + Advance(); + int min = 0; + if (!IsDecimalDigit(current())) { + Reset(start); + return false; + } + while (IsDecimalDigit(current())) { + int 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(); + } + int max = 0; + if (current() == '}') { + max = min; + Advance(); + } else if (current() == ',') { + Advance(); + if (current() == '}') { + max = RegExpTree::kInfinity; + Advance(); + } else { + while (IsDecimalDigit(current())) { + int 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; +} + +// Pattern :: +// Disjunction +template <typename CharT> +RegExpTree* +RegExpParser<CharT>::ParsePattern() +{ + RegExpTree* result = ParseDisjunction(); + MOZ_ASSERT_IF(result, !has_more()); + return result; +} + +static inline RegExpTree* +CaseFoldingSurrogatePairAtom(LifoAlloc* alloc, char16_t lead, char16_t trail, int32_t diff) +{ + RegExpBuilder* builder = alloc->newInfallible<RegExpBuilder>(alloc); + + builder->AddCharacter(lead); + CharacterRangeVector* ranges = alloc->newInfallible<CharacterRangeVector>(*alloc); + ranges->append(CharacterRange::Range(trail, trail)); + ranges->append(CharacterRange::Range(trail + diff, trail + diff)); + builder->AddAtom(alloc->newInfallible<RegExpCharacterClass>(ranges, false)); + + return builder->ToRegExp(); +} + +static inline RegExpTree* +SurrogatePairAtom(LifoAlloc* alloc, char16_t lead, char16_t trail, bool ignore_case) +{ + if (ignore_case) { +#define CALL_ATOM(FROM, TO, LEAD, TRAIL_FROM, TRAIL_TO, DIFF) \ + if (lead == LEAD &&trail >= TRAIL_FROM && trail <= TRAIL_TO) \ + return CaseFoldingSurrogatePairAtom(alloc, lead, trail, DIFF); + FOR_EACH_NON_BMP_CASE_FOLDING(CALL_ATOM) + FOR_EACH_NON_BMP_REV_CASE_FOLDING(CALL_ATOM) +#undef CALL_ATOM + } + + RegExpBuilder* builder = alloc->newInfallible<RegExpBuilder>(alloc); + builder->AddCharacter(lead); + builder->AddCharacter(trail); + return builder->ToRegExp(); +} + +static inline RegExpTree* +LeadSurrogateAtom(LifoAlloc* alloc, char16_t value) +{ + RegExpBuilder* builder = alloc->newInfallible<RegExpBuilder>(alloc); + builder->AddCharacter(value); + builder->AddAtom(NegativeLookahead(alloc, unicode::TrailSurrogateMin, + unicode::TrailSurrogateMax)); + return builder->ToRegExp(); +} + +static inline RegExpTree* +TrailSurrogateAtom(LifoAlloc* alloc, char16_t value) +{ + RegExpBuilder* builder = alloc->newInfallible<RegExpBuilder>(alloc); + builder->AddAssertion(alloc->newInfallible<RegExpAssertion>( + RegExpAssertion::NOT_AFTER_LEAD_SURROGATE)); + builder->AddCharacter(value); + return builder->ToRegExp(); +} + +static inline RegExpTree* +UnicodeEverythingAtom(LifoAlloc* alloc) +{ + RegExpBuilder* builder = alloc->newInfallible<RegExpBuilder>(alloc); + + // everything except \x0a, \x0d, \u2028 and \u2029 + + CharacterRangeVector* ranges = alloc->newInfallible<CharacterRangeVector>(*alloc); + ranges->append(CharacterRange::Range(0x0, 0x09)); + ranges->append(CharacterRange::Range(0x0b, 0x0c)); + ranges->append(CharacterRange::Range(0x0e, 0x2027)); + ranges->append(CharacterRange::Range(0x202A, unicode::LeadSurrogateMin - 1)); + ranges->append(CharacterRange::Range(unicode::TrailSurrogateMax + 1, unicode::UTF16Max)); + builder->AddAtom(alloc->newInfallible<RegExpCharacterClass>(ranges, false)); + + builder->NewAlternative(); + + builder->AddAtom(RangeAtom(alloc, unicode::LeadSurrogateMin, unicode::LeadSurrogateMax)); + builder->AddAtom(NegativeLookahead(alloc, unicode::TrailSurrogateMin, + unicode::TrailSurrogateMax)); + + builder->NewAlternative(); + + builder->AddAssertion(alloc->newInfallible<RegExpAssertion>( + RegExpAssertion::NOT_AFTER_LEAD_SURROGATE)); + builder->AddAtom(RangeAtom(alloc, unicode::TrailSurrogateMin, unicode::TrailSurrogateMax)); + + builder->NewAlternative(); + + builder->AddAtom(RangeAtom(alloc, unicode::LeadSurrogateMin, unicode::LeadSurrogateMax)); + builder->AddAtom(RangeAtom(alloc, unicode::TrailSurrogateMin, unicode::TrailSurrogateMax)); + + return builder->ToRegExp(); +} + +RegExpTree* +UnicodeCharacterClassEscapeAtom(LifoAlloc* alloc, char16_t char_class, bool ignore_case) +{ + CharacterRangeVector* ranges = alloc->newInfallible<CharacterRangeVector>(*alloc); + CharacterRangeVector* lead_ranges = alloc->newInfallible<CharacterRangeVector>(*alloc); + CharacterRangeVector* trail_ranges = alloc->newInfallible<CharacterRangeVector>(*alloc); + WideCharRangeVector* wide_ranges = alloc->newInfallible<WideCharRangeVector>(*alloc); + AddCharOrEscapeUnicode(alloc, ranges, lead_ranges, trail_ranges, wide_ranges, char_class, 0, + ignore_case); + + return UnicodeRangesAtom(alloc, ranges, lead_ranges, trail_ranges, wide_ranges, false, false); +} + +static inline RegExpTree* +UnicodeBackReferenceAtom(LifoAlloc* alloc, RegExpTree* atom) +{ + // If a back reference has a standalone lead surrogate as its last + // character, then that lead surrogate shouldn't match lead surrogates that + // are paired with a corresponding trail surrogate. + RegExpBuilder* builder = alloc->newInfallible<RegExpBuilder>(alloc); + + builder->AddAtom(atom); + builder->AddAssertion(alloc->newInfallible<RegExpAssertion>( + RegExpAssertion::NOT_IN_SURROGATE_PAIR)); + + return builder->ToRegExp(); +} + +// Disjunction :: +// Alternative +// Alternative | Disjunction +// Alternative :: +// [empty] +// Term Alternative +// Term :: +// Assertion +// Atom +// Atom Quantifier +template <typename CharT> +RegExpTree* +RegExpParser<CharT>::ParseDisjunction() +{ + // Used to store current state while parsing subexpressions. + RegExpParserState initial_state(alloc, nullptr, INITIAL, 0); + 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. + return ReportError(JSMSG_MISSING_PAREN); + } + MOZ_ASSERT(INITIAL == stored_state->group_type()); + // Parsing completed successfully. + return builder->ToRegExp(); + case ')': { + if (!stored_state->IsSubexpression()) + return ReportError(JSMSG_UNMATCHED_RIGHT_PAREN); + MOZ_ASSERT(INITIAL != stored_state->group_type()); + + Advance(); + // End disjunction parsing and convert builder content to new single + // regexp atom. + RegExpTree* body = builder->ToRegExp(); + + int end_capture_index = captures_started(); + + int 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 = alloc->newInfallible<RegExpCapture>(body, capture_index); + (*captures_)[capture_index - 1] = capture; + body = capture; + } else if (group_type != GROUPING) { + MOZ_ASSERT(group_type == POSITIVE_LOOKAHEAD || + group_type == NEGATIVE_LOOKAHEAD); + bool is_positive = (group_type == POSITIVE_LOOKAHEAD); + body = alloc->newInfallible<RegExpLookahead>(body, + is_positive, + end_capture_index - capture_index, + capture_index); + } + builder->AddAtom(body); + if (unicode_ && (group_type == POSITIVE_LOOKAHEAD || group_type == NEGATIVE_LOOKAHEAD)) + continue; + // For compatability with JSC and ES3, we allow quantifiers after + // lookaheads, and break in all cases. + break; + } + case '|': { + Advance(); + builder->NewAlternative(); + continue; + } + case '*': + case '+': + case '?': + return ReportError(JSMSG_NOTHING_TO_REPEAT); + case '^': { + Advance(); + if (multiline_) { + builder->AddAssertion(alloc->newInfallible<RegExpAssertion>(RegExpAssertion::START_OF_LINE)); + } else { + builder->AddAssertion(alloc->newInfallible<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(alloc->newInfallible<RegExpAssertion>(assertion_type)); + continue; + } + case '.': { + Advance(); + // everything except \x0a, \x0d, \u2028 and \u2029 + if (unicode_) { + builder->AddAtom(UnicodeEverythingAtom(alloc)); + break; + } + CharacterRangeVector* ranges = alloc->newInfallible<CharacterRangeVector>(*alloc); + CharacterRange::AddClassEscape(alloc, '.', ranges); + RegExpTree* atom = alloc->newInfallible<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: + return ReportError(JSMSG_INVALID_GROUP); + } + Advance(2); + } else { + if (captures_ == nullptr) + captures_ = alloc->newInfallible<RegExpCaptureVector>(*alloc); + if (captures_started() >= kMaxCaptures) + return ReportError(JSMSG_TOO_MANY_PARENS); + captures_->append((RegExpCapture*) nullptr); + } + // Store current state and begin new disjunction parsing. + stored_state = alloc->newInfallible<RegExpParserState>(alloc, stored_state, subexpr_type, + captures_started()); + builder = stored_state->builder(); + continue; + } + case '[': { + RegExpTree* atom = ParseCharacterClass(); + if (!atom) + return nullptr; + builder->AddAtom(atom); + break; + } + // Atom :: + // \ AtomEscape + case '\\': + switch (Next()) { + case kEndMarker: + return ReportError(JSMSG_ESCAPE_AT_END_OF_REGEXP); + case 'b': + Advance(2); + builder->AddAssertion(alloc->newInfallible<RegExpAssertion>(RegExpAssertion::BOUNDARY)); + continue; + case 'B': + Advance(2); + builder->AddAssertion(alloc->newInfallible<RegExpAssertion>(RegExpAssertion::NON_BOUNDARY)); + continue; + // AtomEscape :: + // CharacterClassEscape + // + // CharacterClassEscape :: one of + // d D s S w W + case 'D': case 'S': case 'W': + if (unicode_) { + Advance(); + builder->AddAtom(UnicodeCharacterClassEscapeAtom(alloc, current(), + ignore_case_)); + Advance(); + break; + } + MOZ_FALLTHROUGH; + case 'd': case 's': case 'w': { + widechar c = Next(); + Advance(2); + CharacterRangeVector* ranges = + alloc->newInfallible<CharacterRangeVector>(*alloc); + if (unicode_) + CharacterRange::AddClassEscapeUnicode(alloc, c, ranges, ignore_case_); + else + CharacterRange::AddClassEscape(alloc, c, ranges); + RegExpTree* atom = alloc->newInfallible<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': { + int index = 0; + if (ParseBackReferenceIndex(&index)) { + RegExpCapture* capture = nullptr; + if (captures_ != nullptr && index <= (int) captures_->length()) { + capture = (*captures_)[index - 1]; + } + if (capture == nullptr) { + builder->AddEmpty(); + break; + } + RegExpTree* atom = alloc->newInfallible<RegExpBackReference>(capture); + if (unicode_) + builder->AddAtom(UnicodeBackReferenceAtom(alloc, atom)); + else + builder->AddAtom(atom); + break; + } + if (unicode_) + return ReportError(JSMSG_BACK_REF_OUT_OF_RANGE); + widechar first_digit = Next(); + if (first_digit == '8' || first_digit == '9') { + // Treat as identity escape + builder->AddCharacter(first_digit); + Advance(2); + break; + } + MOZ_FALLTHROUGH; + } + case '0': { + if (unicode_) { + Advance(2); + if (IsDecimalDigit(current())) + return ReportError(JSMSG_INVALID_DECIMAL_ESCAPE); + builder->AddCharacter(0); + break; + } + + Advance(); + widechar 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(); + widechar controlLetter = Next(); + // Special case if it is an ASCII letter. + // Convert lower case letters to uppercase. + widechar letter = controlLetter & ~('a' ^ 'A'); + if (letter < 'A' || 'Z' < letter) { + if (unicode_) + return ReportError(JSMSG_INVALID_IDENTITY_ESCAPE); + // 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); + widechar value; + if (ParseHexEscape(2, &value)) { + builder->AddCharacter(value); + } else { + if (unicode_) + return ReportError(JSMSG_INVALID_IDENTITY_ESCAPE); + builder->AddCharacter('x'); + } + break; + } + case 'u': { + Advance(2); + widechar value; + if (unicode_) { + if (current() == '{') { + if (!ParseBracedHexEscape(&value)) + return nullptr; + if (unicode::IsLeadSurrogate(value)) { + builder->AddAtom(LeadSurrogateAtom(alloc, value)); + } else if (unicode::IsTrailSurrogate(value)) { + builder->AddAtom(TrailSurrogateAtom(alloc, value)); + } else if (value >= unicode::NonBMPMin) { + char16_t lead, trail; + unicode::UTF16Encode(value, &lead, &trail); + builder->AddAtom(SurrogatePairAtom(alloc, lead, trail, + ignore_case_)); + } else { + builder->AddCharacter(value); + } + } else if (ParseHexEscape(4, &value)) { + if (unicode::IsLeadSurrogate(value)) { + widechar trail; + if (ParseTrailSurrogate(&trail)) { + builder->AddAtom(SurrogatePairAtom(alloc, value, trail, + ignore_case_)); + } else { + builder->AddAtom(LeadSurrogateAtom(alloc, value)); + } + } else if (unicode::IsTrailSurrogate(value)) { + builder->AddAtom(TrailSurrogateAtom(alloc, value)); + } else { + builder->AddCharacter(value); + } + } else { + return ReportError(JSMSG_INVALID_UNICODE_ESCAPE); + } + break; + } + if (ParseHexEscape(4, &value)) { + builder->AddCharacter(value); + } else { + builder->AddCharacter('u'); + } + break; + } + default: + // Identity escape. + if (unicode_ && !IsSyntaxCharacter(Next())) + return ReportError(JSMSG_INVALID_IDENTITY_ESCAPE); + builder->AddCharacter(Next()); + Advance(2); + break; + } + break; + case '{': { + if (unicode_) + return ReportError(JSMSG_RAW_BRACE_IN_REGEP); + int dummy; + if (ParseIntervalQuantifier(&dummy, &dummy)) + return ReportError(JSMSG_NOTHING_TO_REPEAT); + MOZ_FALLTHROUGH; + } + default: + if (unicode_) { + char16_t lead, trail; + if (ParseRawSurrogatePair(&lead, &trail)) { + builder->AddAtom(SurrogatePairAtom(alloc, lead, trail, ignore_case_)); + } else { + widechar c = current(); + if (unicode::IsLeadSurrogate(c)) + builder->AddAtom(LeadSurrogateAtom(alloc, c)); + else if (unicode::IsTrailSurrogate(c)) + builder->AddAtom(TrailSurrogateAtom(alloc, c)); + else if (c == ']') + return ReportError(JSMSG_RAW_BRACKET_IN_REGEP); + else if (c == '}') + return ReportError(JSMSG_RAW_BRACE_IN_REGEP); + else + builder->AddCharacter(c); + Advance(); + } + break; + } + builder->AddCharacter(current()); + Advance(); + break; + } // end switch(current()) + + int min; + int 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) + return ReportError(JSMSG_NUMBERS_OUT_OF_ORDER); + break; + } else { + continue; + } + default: + continue; + } + RegExpQuantifier::QuantifierType quantifier_type = RegExpQuantifier::GREEDY; + if (current() == '?') { + quantifier_type = RegExpQuantifier::NON_GREEDY; + Advance(); + } + builder->AddQuantifierToAtom(min, max, quantifier_type); + } +} + +template class irregexp::RegExpParser<Latin1Char>; +template class irregexp::RegExpParser<char16_t>; + +template <typename CharT> +static bool +ParsePattern(frontend::TokenStream& ts, LifoAlloc& alloc, const CharT* chars, size_t length, + bool multiline, bool match_only, bool unicode, bool ignore_case, + bool global, bool sticky, RegExpCompileData* data) +{ + if (match_only) { + // Try to strip a leading '.*' from the RegExp, but only if it is not + // followed by a '?' (which will affect how the .* is parsed). This + // pattern will affect the captures produced by the RegExp, but not + // whether there is a match or not. + if (length >= 3 && chars[0] == '.' && chars[1] == '*' && chars[2] != '?') { + chars += 2; + length -= 2; + } + + // Try to strip a trailing '.*' from the RegExp, which as above will + // affect the captures but not whether there is a match. Only do this + // when the following conditions are met: + // 1. there are no other meta characters in the RegExp, so that we + // are sure this will not affect how the RegExp is parsed + // 2. global and sticky flags are not set, as lastIndex needs to be + // set properly on global or sticky match + if (length >= 3 && !HasRegExpMetaChars(chars, length - 2) && + !global && !sticky && + chars[length - 2] == '.' && chars[length - 1] == '*') + { + length -= 2; + } + } + + RegExpParser<CharT> parser(ts, &alloc, chars, chars + length, multiline, unicode, ignore_case); + data->tree = parser.ParsePattern(); + if (!data->tree) + return false; + + data->simple = parser.simple(); + data->contains_anchor = parser.contains_anchor(); + data->capture_count = parser.captures_started(); + return true; +} + +bool +irregexp::ParsePattern(frontend::TokenStream& ts, LifoAlloc& alloc, JSAtom* str, + bool multiline, bool match_only, bool unicode, bool ignore_case, + bool global, bool sticky, RegExpCompileData* data) +{ + JS::AutoCheckCannotGC nogc; + return str->hasLatin1Chars() + ? ::ParsePattern(ts, alloc, str->latin1Chars(nogc), str->length(), + multiline, match_only, unicode, ignore_case, global, sticky, data) + : ::ParsePattern(ts, alloc, str->twoByteChars(nogc), str->length(), + multiline, match_only, unicode, ignore_case, global, sticky, data); +} + +template <typename CharT> +static bool +ParsePatternSyntax(frontend::TokenStream& ts, LifoAlloc& alloc, const CharT* chars, size_t length, + bool unicode) +{ + LifoAllocScope scope(&alloc); + + RegExpParser<CharT> parser(ts, &alloc, chars, chars + length, false, unicode, false); + return parser.ParsePattern() != nullptr; +} + +bool +irregexp::ParsePatternSyntax(frontend::TokenStream& ts, LifoAlloc& alloc, JSAtom* str, + bool unicode) +{ + JS::AutoCheckCannotGC nogc; + return str->hasLatin1Chars() + ? ::ParsePatternSyntax(ts, alloc, str->latin1Chars(nogc), str->length(), unicode) + : ::ParsePatternSyntax(ts, alloc, str->twoByteChars(nogc), str->length(), unicode); +} |