#pragma once
#include "Yarr.h"
#include "YarrPattern.h"
#include "YarrUnicodeProperties.h"
#include <wtf/ASCIICType.h>
#include <wtf/HashSet.h>
#include <wtf/Optional.h>
#include <wtf/text/StringBuilder.h>
#include <wtf/text/WTFString.h>
namespace JSC { namespace Yarr {
template<class Delegate, typename CharType>
class Parser {
private:
template<class FriendDelegate>
friend ErrorCode parse(FriendDelegate&, const String& pattern, bool isUnicode, unsigned backReferenceLimit);
class CharacterClassParserDelegate {
public:
CharacterClassParserDelegate(Delegate& delegate, ErrorCode& err)
: m_delegate(delegate)
, m_errorCode(err)
, m_state(Empty)
, m_character(0)
{
}
void begin(bool invert)
{
m_delegate.atomCharacterClassBegin(invert);
}
void atomPatternCharacter(UChar32 ch, bool hyphenIsRange = false)
{
switch (m_state) {
case AfterCharacterClass:
if (hyphenIsRange && ch == '-') {
m_delegate.atomCharacterClassAtom('-');
m_state = AfterCharacterClassHyphen;
return;
}
FALLTHROUGH;
case Empty:
m_character = ch;
m_state = CachedCharacter;
return;
case CachedCharacter:
if (hyphenIsRange && ch == '-')
m_state = CachedCharacterHyphen;
else {
m_delegate.atomCharacterClassAtom(m_character);
m_character = ch;
}
return;
case CachedCharacterHyphen:
if (ch < m_character) {
m_errorCode = ErrorCode::CharacterClassOutOfOrder;
return;
}
m_delegate.atomCharacterClassRange(m_character, ch);
m_state = Empty;
return;
case AfterCharacterClassHyphen:
m_delegate.atomCharacterClassAtom(ch);
m_state = Empty;
return;
}
}
void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert)
{
switch (m_state) {
case CachedCharacter:
m_delegate.atomCharacterClassAtom(m_character);
FALLTHROUGH;
case Empty:
case AfterCharacterClass:
m_state = AfterCharacterClass;
m_delegate.atomCharacterClassBuiltIn(classID, invert);
return;
case CachedCharacterHyphen:
m_delegate.atomCharacterClassAtom(m_character);
m_delegate.atomCharacterClassAtom('-');
FALLTHROUGH;
case AfterCharacterClassHyphen:
m_delegate.atomCharacterClassBuiltIn(classID, invert);
m_state = Empty;
return;
}
}
void end()
{
if (m_state == CachedCharacter)
m_delegate.atomCharacterClassAtom(m_character);
else if (m_state == CachedCharacterHyphen) {
m_delegate.atomCharacterClassAtom(m_character);
m_delegate.atomCharacterClassAtom('-');
}
m_delegate.atomCharacterClassEnd();
}
NO_RETURN_DUE_TO_ASSERT void assertionWordBoundary(bool) { RELEASE_ASSERT_NOT_REACHED(); }
NO_RETURN_DUE_TO_ASSERT void atomBackReference(unsigned) { RELEASE_ASSERT_NOT_REACHED(); }
NO_RETURN_DUE_TO_ASSERT void atomNamedBackReference(const String&) { RELEASE_ASSERT_NOT_REACHED(); }
NO_RETURN_DUE_TO_ASSERT bool isValidNamedForwardReference(const String&) { RELEASE_ASSERT_NOT_REACHED(); }
NO_RETURN_DUE_TO_ASSERT void atomNamedForwardReference(const String&) { RELEASE_ASSERT_NOT_REACHED(); }
private:
Delegate& m_delegate;
ErrorCode& m_errorCode;
enum CharacterClassConstructionState {
Empty,
CachedCharacter,
CachedCharacterHyphen,
AfterCharacterClass,
AfterCharacterClassHyphen,
} m_state;
UChar32 m_character;
};
Parser(Delegate& delegate, const String& pattern, bool isUnicode, unsigned backReferenceLimit)
: m_delegate(delegate)
, m_backReferenceLimit(backReferenceLimit)
, m_data(pattern.characters<CharType>())
, m_size(pattern.length())
, m_isUnicode(isUnicode)
{
}
bool isIdentityEscapeAnError(int ch)
{
if (m_isUnicode && !strchr("^$\\.*+?()[]{}|/", ch)) {
m_errorCode = ErrorCode::InvalidIdentityEscape;
return true;
}
return false;
}
template<bool inCharacterClass, class EscapeDelegate>
bool parseEscape(EscapeDelegate& delegate)
{
ASSERT(!hasError(m_errorCode));
ASSERT(peek() == '\\');
consume();
if (atEndOfPattern()) {
m_errorCode = ErrorCode::EscapeUnterminated;
return false;
}
switch (peek()) {
case 'b':
consume();
if (inCharacterClass) {
if (isIdentityEscapeAnError('b'))
break;
delegate.atomPatternCharacter('\b');
} else {
delegate.assertionWordBoundary(false);
return false;
}
break;
case 'B':
consume();
if (inCharacterClass) {
if (isIdentityEscapeAnError('B'))
break;
delegate.atomPatternCharacter('B');
} else {
delegate.assertionWordBoundary(true);
return false;
}
break;
case 'd':
consume();
delegate.atomBuiltInCharacterClass(BuiltInCharacterClassID::DigitClassID, false);
break;
case 's':
consume();
delegate.atomBuiltInCharacterClass(BuiltInCharacterClassID::SpaceClassID, false);
break;
case 'w':
consume();
delegate.atomBuiltInCharacterClass(BuiltInCharacterClassID::WordClassID, false);
break;
case 'D':
consume();
delegate.atomBuiltInCharacterClass(BuiltInCharacterClassID::DigitClassID, true);
break;
case 'S':
consume();
delegate.atomBuiltInCharacterClass(BuiltInCharacterClassID::SpaceClassID, true);
break;
case 'W':
consume();
delegate.atomBuiltInCharacterClass(BuiltInCharacterClassID::WordClassID, true);
break;
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9': {
if (!inCharacterClass) {
ParseState state = saveState();
unsigned backReference = consumeNumber();
if (backReference <= m_backReferenceLimit) {
delegate.atomBackReference(backReference);
break;
}
restoreState(state);
if (m_isUnicode) {
m_errorCode = ErrorCode::InvalidBackreference;
return false;
}
}
if (peek() >= '8') {
delegate.atomPatternCharacter(consume());
break;
}
FALLTHROUGH;
}
case '0':
delegate.atomPatternCharacter(consumeOctal());
break;
case 'f':
consume();
delegate.atomPatternCharacter('\f');
break;
case 'n':
consume();
delegate.atomPatternCharacter('\n');
break;
case 'r':
consume();
delegate.atomPatternCharacter('\r');
break;
case 't':
consume();
delegate.atomPatternCharacter('\t');
break;
case 'v':
consume();
delegate.atomPatternCharacter('\v');
break;
case 'c': {
ParseState state = saveState();
consume();
if (!atEndOfPattern()) {
int control = consume();
if (inCharacterClass ? WTF::isASCIIAlphanumeric(control) || (control == '_') : WTF::isASCIIAlpha(control)) {
delegate.atomPatternCharacter(control & 0x1f);
break;
}
}
restoreState(state);
delegate.atomPatternCharacter('\\');
break;
}
case 'x': {
consume();
int x = tryConsumeHex(2);
if (x == -1) {
if (isIdentityEscapeAnError('x'))
break;
delegate.atomPatternCharacter('x');
} else
delegate.atomPatternCharacter(x);
break;
}
case 'k': {
consume();
ParseState state = saveState();
if (!atEndOfPattern() && !inCharacterClass) {
if (consume() == '<') {
auto groupName = tryConsumeGroupName();
if (groupName) {
if (m_captureGroupNames.contains(groupName.value())) {
delegate.atomNamedBackReference(groupName.value());
break;
}
if (delegate.isValidNamedForwardReference(groupName.value())) {
delegate.atomNamedForwardReference(groupName.value());
break;
}
}
if (m_isUnicode) {
m_errorCode = ErrorCode::InvalidBackreference;
break;
}
}
}
restoreState(state);
delegate.atomPatternCharacter('k');
break;
}
case 'p':
case 'P': {
int escapeChar = consume();
if (!m_isUnicode) {
if (isIdentityEscapeAnError(escapeChar))
break;
delegate.atomPatternCharacter(escapeChar);
break;
}
if (!atEndOfPattern() && peek() == '{') {
consume();
auto optClassID = tryConsumeUnicodePropertyExpression();
if (!optClassID) {
break;
}
delegate.atomBuiltInCharacterClass(optClassID.value(), escapeChar == 'P');
} else
m_errorCode = ErrorCode::InvalidUnicodePropertyExpression;
break;
}
case 'u': {
consume();
if (atEndOfPattern()) {
if (isIdentityEscapeAnError('u'))
break;
delegate.atomPatternCharacter('u');
break;
}
if (m_isUnicode && peek() == '{') {
consume();
UChar32 codePoint = 0;
do {
if (atEndOfPattern() || !isASCIIHexDigit(peek())) {
m_errorCode = ErrorCode::InvalidUnicodeEscape;
break;
}
codePoint = (codePoint << 4) | toASCIIHexValue(consume());
if (codePoint > UCHAR_MAX_VALUE)
m_errorCode = ErrorCode::InvalidUnicodeEscape;
} while (!atEndOfPattern() && peek() != '}');
if (!atEndOfPattern() && peek() == '}')
consume();
else if (!hasError(m_errorCode))
m_errorCode = ErrorCode::InvalidUnicodeEscape;
if (hasError(m_errorCode))
return false;
delegate.atomPatternCharacter(codePoint);
break;
}
int u = tryConsumeHex(4);
if (u == -1) {
if (isIdentityEscapeAnError('u'))
break;
delegate.atomPatternCharacter('u');
} else {
if (U16_IS_LEAD(u) && m_isUnicode && (patternRemaining() >= 6) && peek() == '\\') {
ParseState state = saveState();
consume();
if (tryConsume('u')) {
int surrogate2 = tryConsumeHex(4);
if (U16_IS_TRAIL(surrogate2)) {
u = U16_GET_SUPPLEMENTARY(u, surrogate2);
delegate.atomPatternCharacter(u);
break;
}
}
restoreState(state);
}
delegate.atomPatternCharacter(u);
}
break;
}
default:
int ch = peek();
if (ch == '-' && m_isUnicode && inCharacterClass) {
delegate.atomPatternCharacter(consume());
break;
}
if (isIdentityEscapeAnError(ch))
break;
delegate.atomPatternCharacter(consume());
}
return true;
}
UChar32 consumePossibleSurrogatePair()
{
UChar32 ch = consume();
if (U16_IS_LEAD(ch) && m_isUnicode && (patternRemaining() > 0)) {
ParseState state = saveState();
UChar32 surrogate2 = consume();
if (U16_IS_TRAIL(surrogate2))
ch = U16_GET_SUPPLEMENTARY(ch, surrogate2);
else
restoreState(state);
}
return ch;
}
bool parseAtomEscape()
{
return parseEscape<false>(m_delegate);
}
void parseCharacterClassEscape(CharacterClassParserDelegate& delegate)
{
parseEscape<true>(delegate);
}
void parseCharacterClass()
{
ASSERT(!hasError(m_errorCode));
ASSERT(peek() == '[');
consume();
CharacterClassParserDelegate characterClassConstructor(m_delegate, m_errorCode);
characterClassConstructor.begin(tryConsume('^'));
while (!atEndOfPattern()) {
switch (peek()) {
case ']':
consume();
characterClassConstructor.end();
return;
case '\\':
parseCharacterClassEscape(characterClassConstructor);
break;
default:
characterClassConstructor.atomPatternCharacter(consumePossibleSurrogatePair(), true);
}
if (hasError(m_errorCode))
return;
}
m_errorCode = ErrorCode::CharacterClassUnmatched;
}
void parseParenthesesBegin()
{
ASSERT(!hasError(m_errorCode));
ASSERT(peek() == '(');
consume();
if (tryConsume('?')) {
if (atEndOfPattern()) {
m_errorCode = ErrorCode::ParenthesesTypeInvalid;
return;
}
switch (consume()) {
case ':':
m_delegate.atomParenthesesSubpatternBegin(false);
break;
case '=':
m_delegate.atomParentheticalAssertionBegin();
break;
case '!':
m_delegate.atomParentheticalAssertionBegin(true);
break;
case '<': {
auto groupName = tryConsumeGroupName();
if (groupName) {
auto setAddResult = m_captureGroupNames.add(groupName.value());
if (setAddResult.isNewEntry)
m_delegate.atomParenthesesSubpatternBegin(true, groupName);
else
m_errorCode = ErrorCode::DuplicateGroupName;
} else
m_errorCode = ErrorCode::InvalidGroupName;
break;
}
default:
m_errorCode = ErrorCode::ParenthesesTypeInvalid;
}
} else
m_delegate.atomParenthesesSubpatternBegin();
++m_parenthesesNestingDepth;
}
void parseParenthesesEnd()
{
ASSERT(!hasError(m_errorCode));
ASSERT(peek() == ')');
consume();
if (m_parenthesesNestingDepth > 0)
m_delegate.atomParenthesesEnd();
else
m_errorCode = ErrorCode::ParenthesesUnmatched;
--m_parenthesesNestingDepth;
}
void parseQuantifier(bool lastTokenWasAnAtom, unsigned min, unsigned max)
{
ASSERT(!hasError(m_errorCode));
ASSERT(min <= max);
if (min == UINT_MAX) {
m_errorCode = ErrorCode::QuantifierTooLarge;
return;
}
if (lastTokenWasAnAtom)
m_delegate.quantifyAtom(min, max, !tryConsume('?'));
else
m_errorCode = ErrorCode::QuantifierWithoutAtom;
}
void parseTokens()
{
bool lastTokenWasAnAtom = false;
while (!atEndOfPattern()) {
switch (peek()) {
case '|':
consume();
m_delegate.disjunction();
lastTokenWasAnAtom = false;
break;
case '(':
parseParenthesesBegin();
lastTokenWasAnAtom = false;
break;
case ')':
parseParenthesesEnd();
lastTokenWasAnAtom = true;
break;
case '^':
consume();
m_delegate.assertionBOL();
lastTokenWasAnAtom = false;
break;
case '$':
consume();
m_delegate.assertionEOL();
lastTokenWasAnAtom = false;
break;
case '.':
consume();
m_delegate.atomBuiltInCharacterClass(BuiltInCharacterClassID::DotClassID, false);
lastTokenWasAnAtom = true;
break;
case '[':
parseCharacterClass();
lastTokenWasAnAtom = true;
break;
case '\\':
lastTokenWasAnAtom = parseAtomEscape();
break;
case '*':
consume();
parseQuantifier(lastTokenWasAnAtom, 0, quantifyInfinite);
lastTokenWasAnAtom = false;
break;
case '+':
consume();
parseQuantifier(lastTokenWasAnAtom, 1, quantifyInfinite);
lastTokenWasAnAtom = false;
break;
case '?':
consume();
parseQuantifier(lastTokenWasAnAtom, 0, 1);
lastTokenWasAnAtom = false;
break;
case '{': {
ParseState state = saveState();
consume();
if (peekIsDigit()) {
unsigned min = consumeNumber();
unsigned max = min;
if (tryConsume(','))
max = peekIsDigit() ? consumeNumber() : quantifyInfinite;
if (tryConsume('}')) {
if (min <= max)
parseQuantifier(lastTokenWasAnAtom, min, max);
else
m_errorCode = ErrorCode::QuantifierOutOfOrder;
lastTokenWasAnAtom = false;
break;
}
}
restoreState(state);
}
FALLTHROUGH;
default:
m_delegate.atomPatternCharacter(consumePossibleSurrogatePair());
lastTokenWasAnAtom = true;
}
if (hasError(m_errorCode))
return;
}
if (m_parenthesesNestingDepth > 0)
m_errorCode = ErrorCode::MissingParentheses;
}
ErrorCode parse()
{
if (m_size > MAX_PATTERN_SIZE)
m_errorCode = ErrorCode::PatternTooLarge;
else
parseTokens();
ASSERT(atEndOfPattern() || hasError(m_errorCode));
return m_errorCode;
}
typedef unsigned ParseState;
ParseState saveState()
{
return m_index;
}
void restoreState(ParseState state)
{
m_index = state;
}
bool atEndOfPattern()
{
ASSERT(m_index <= m_size);
return m_index == m_size;
}
unsigned patternRemaining()
{
ASSERT(m_index <= m_size);
return m_size - m_index;
}
int peek()
{
ASSERT(m_index < m_size);
return m_data[m_index];
}
bool peekIsDigit()
{
return !atEndOfPattern() && WTF::isASCIIDigit(peek());
}
unsigned peekDigit()
{
ASSERT(peekIsDigit());
return peek() - '0';
}
int tryConsumeUnicodeEscape()
{
if (!tryConsume('u'))
return -1;
if (m_isUnicode && tryConsume('{')) {
int codePoint = 0;
do {
if (atEndOfPattern() || !isASCIIHexDigit(peek())) {
m_errorCode = ErrorCode::InvalidUnicodeEscape;
return -1;
}
codePoint = (codePoint << 4) | toASCIIHexValue(consume());
if (codePoint > UCHAR_MAX_VALUE) {
m_errorCode = ErrorCode::InvalidUnicodeEscape;
return -1;
}
} while (!atEndOfPattern() && peek() != '}');
if (!atEndOfPattern() && peek() == '}')
consume();
else if (!hasError(m_errorCode))
m_errorCode = ErrorCode::InvalidUnicodeEscape;
if (hasError(m_errorCode))
return -1;
return codePoint;
}
int u = tryConsumeHex(4);
if (u == -1)
return -1;
if (U16_IS_LEAD(u) && m_isUnicode && (patternRemaining() >= 6) && peek() == '\\') {
ParseState state = saveState();
consume();
if (tryConsume('u')) {
int surrogate2 = tryConsumeHex(4);
if (U16_IS_TRAIL(surrogate2)) {
u = U16_GET_SUPPLEMENTARY(u, surrogate2);
return u;
}
}
restoreState(state);
}
return u;
}
int tryConsumeIdentifierCharacter()
{
int ch = peek();
if (ch == '\\') {
consume();
ch = tryConsumeUnicodeEscape();
} else
consume();
return ch;
}
bool isIdentifierStart(int ch)
{
return (WTF::isASCII(ch) && (WTF::isASCIIAlpha(ch) || ch == '_' || ch == '$')) || (U_GET_GC_MASK(ch) & U_GC_L_MASK);
}
bool isIdentifierPart(int ch)
{
return (WTF::isASCII(ch) && (WTF::isASCIIAlpha(ch) || ch == '_' || ch == '$')) || (U_GET_GC_MASK(ch) & (U_GC_L_MASK | U_GC_MN_MASK | U_GC_MC_MASK | U_GC_ND_MASK | U_GC_PC_MASK)) || ch == 0x200C || ch == 0x200D;
}
bool isUnicodePropertyValueExpressionChar(int ch)
{
return WTF::isASCIIAlphanumeric(ch) || ch == '_' || ch == '=';
}
int consume()
{
ASSERT(m_index < m_size);
return m_data[m_index++];
}
unsigned consumeDigit()
{
ASSERT(peekIsDigit());
return consume() - '0';
}
unsigned consumeNumber()
{
Checked<unsigned, RecordOverflow> n = consumeDigit();
while (peekIsDigit())
n = n * 10 + consumeDigit();
return n.hasOverflowed() ? quantifyInfinite : n.unsafeGet();
}
unsigned consumeOctal()
{
ASSERT(WTF::isASCIIOctalDigit(peek()));
unsigned n = consumeDigit();
while (n < 32 && !atEndOfPattern() && WTF::isASCIIOctalDigit(peek()))
n = n * 8 + consumeDigit();
return n;
}
bool tryConsume(UChar ch)
{
if (atEndOfPattern() || (m_data[m_index] != ch))
return false;
++m_index;
return true;
}
int tryConsumeHex(int count)
{
ParseState state = saveState();
int n = 0;
while (count--) {
if (atEndOfPattern() || !WTF::isASCIIHexDigit(peek())) {
restoreState(state);
return -1;
}
n = (n << 4) | WTF::toASCIIHexValue(consume());
}
return n;
}
Optional<String> tryConsumeGroupName()
{
if (atEndOfPattern())
return WTF::nullopt;
ParseState state = saveState();
int ch = tryConsumeIdentifierCharacter();
if (isIdentifierStart(ch)) {
StringBuilder identifierBuilder;
identifierBuilder.append(ch);
while (!atEndOfPattern()) {
ch = tryConsumeIdentifierCharacter();
if (ch == '>')
return Optional<String>(identifierBuilder.toString());
if (!isIdentifierPart(ch))
break;
identifierBuilder.append(ch);
}
}
restoreState(state);
return WTF::nullopt;
}
Optional<BuiltInCharacterClassID> tryConsumeUnicodePropertyExpression()
{
if (atEndOfPattern() || !isUnicodePropertyValueExpressionChar(peek())) {
m_errorCode = ErrorCode::InvalidUnicodePropertyExpression;
return WTF::nullopt;
}
StringBuilder expressionBuilder;
String unicodePropertyName;
bool foundEquals = false;
unsigned errors = 0;
expressionBuilder.append(consume());
while (!atEndOfPattern()) {
int ch = peek();
if (ch == '}') {
consume();
if (errors) {
m_errorCode = ErrorCode::InvalidUnicodePropertyExpression;
return WTF::nullopt;
}
if (foundEquals) {
auto result = unicodeMatchPropertyValue(unicodePropertyName, expressionBuilder.toString());
if (!result)
m_errorCode = ErrorCode::InvalidUnicodePropertyExpression;
return result;
}
auto result = unicodeMatchProperty(expressionBuilder.toString());
if (!result)
m_errorCode = ErrorCode::InvalidUnicodePropertyExpression;
return result;
}
consume();
if (ch == '=') {
if (!foundEquals) {
foundEquals = true;
unicodePropertyName = expressionBuilder.toString();
expressionBuilder.clear();
} else
errors++;
} else if (!isUnicodePropertyValueExpressionChar(ch))
errors++;
else
expressionBuilder.append(ch);
}
m_errorCode = ErrorCode::InvalidUnicodePropertyExpression;
return WTF::nullopt;
}
Delegate& m_delegate;
unsigned m_backReferenceLimit;
ErrorCode m_errorCode { ErrorCode::NoError };
const CharType* m_data;
unsigned m_size;
unsigned m_index { 0 };
bool m_isUnicode;
unsigned m_parenthesesNestingDepth { 0 };
HashSet<String> m_captureGroupNames;
static const unsigned MAX_PATTERN_SIZE = 1024 * 1024;
};
template<class Delegate>
ErrorCode parse(Delegate& delegate, const String& pattern, bool isUnicode, unsigned backReferenceLimit = quantifyInfinite)
{
if (pattern.is8Bit())
return Parser<Delegate, LChar>(delegate, pattern, isUnicode, backReferenceLimit).parse();
return Parser<Delegate, UChar>(delegate, pattern, isUnicode, backReferenceLimit).parse();
}
} }