diff options
Diffstat (limited to 'Userland')
| -rw-r--r-- | Userland/Libraries/LibC/regex.h | 31 | ||||
| -rw-r--r-- | Userland/Libraries/LibRegex/RegexByteCode.cpp | 54 | ||||
| -rw-r--r-- | Userland/Libraries/LibRegex/RegexMatch.h | 4 | ||||
| -rw-r--r-- | Userland/Libraries/LibRegex/RegexOptions.h | 34 | ||||
| -rw-r--r-- | Userland/Libraries/LibRegex/RegexParser.cpp | 317 | ||||
| -rw-r--r-- | Userland/Libraries/LibRegex/RegexParser.h | 15 | ||||
| -rw-r--r-- | Userland/Libraries/LibRegex/Tests/Regex.cpp | 18 |
7 files changed, 382 insertions, 91 deletions
diff --git a/Userland/Libraries/LibC/regex.h b/Userland/Libraries/LibC/regex.h index b7e01ae981..0c41a982ad 100644 --- a/Userland/Libraries/LibC/regex.h +++ b/Userland/Libraries/LibC/regex.h @@ -83,21 +83,22 @@ struct regmatch_t { }; enum __RegexAllFlags { - __Regex_Global = 1, // All matches (don't return after first match) - __Regex_Insensitive = __Regex_Global << 1, // Case insensitive match (ignores case of [a-zA-Z]) - __Regex_Ungreedy = __Regex_Global << 2, // The match becomes lazy by default. Now a ? following a quantifier makes it greedy - __Regex_Unicode = __Regex_Global << 3, // Enable all unicode features and interpret all unicode escape sequences as such - __Regex_Extended = __Regex_Global << 4, // Ignore whitespaces. Spaces and text after a # in the pattern are ignored - __Regex_Extra = __Regex_Global << 5, // Disallow meaningless escapes. A \ followed by a letter with no special meaning is faulted - __Regex_MatchNotBeginOfLine = __Regex_Global << 6, // Pattern is not forced to ^ -> search in whole string! - __Regex_MatchNotEndOfLine = __Regex_Global << 7, // Don't Force the dollar sign, $, to always match end of the string, instead of end of the line. This option is ignored if the Multiline-flag is set - __Regex_SkipSubExprResults = __Regex_Global << 8, // Do not return sub expressions in the result - __Regex_StringCopyMatches = __Regex_Global << 9, // Do explicitly copy results into new allocated string instead of StringView to original string. - __Regex_SingleLine = __Regex_Global << 10, // Dot matches newline characters - __Regex_Sticky = __Regex_Global << 11, // Force the pattern to only match consecutive matches from where the previous match ended. - __Regex_Multiline = __Regex_Global << 12, // Handle newline characters. Match each line, one by one. - __Regex_SkipTrimEmptyMatches = __Regex_Global << 13, // Do not remove empty capture group results. - __Regex_Internal_Stateful = __Regex_Global << 14, // Internal flag; enables stateful matches. + __Regex_Global = 1, // All matches (don't return after first match) + __Regex_Insensitive = __Regex_Global << 1, // Case insensitive match (ignores case of [a-zA-Z]) + __Regex_Ungreedy = __Regex_Global << 2, // The match becomes lazy by default. Now a ? following a quantifier makes it greedy + __Regex_Unicode = __Regex_Global << 3, // Enable all unicode features and interpret all unicode escape sequences as such + __Regex_Extended = __Regex_Global << 4, // Ignore whitespaces. Spaces and text after a # in the pattern are ignored + __Regex_Extra = __Regex_Global << 5, // Disallow meaningless escapes. A \ followed by a letter with no special meaning is faulted + __Regex_MatchNotBeginOfLine = __Regex_Global << 6, // Pattern is not forced to ^ -> search in whole string! + __Regex_MatchNotEndOfLine = __Regex_Global << 7, // Don't Force the dollar sign, $, to always match end of the string, instead of end of the line. This option is ignored if the Multiline-flag is set + __Regex_SkipSubExprResults = __Regex_Global << 8, // Do not return sub expressions in the result + __Regex_StringCopyMatches = __Regex_Global << 9, // Do explicitly copy results into new allocated string instead of StringView to original string. + __Regex_SingleLine = __Regex_Global << 10, // Dot matches newline characters + __Regex_Sticky = __Regex_Global << 11, // Force the pattern to only match consecutive matches from where the previous match ended. + __Regex_Multiline = __Regex_Global << 12, // Handle newline characters. Match each line, one by one. + __Regex_SkipTrimEmptyMatches = __Regex_Global << 13, // Do not remove empty capture group results. + __Regex_Internal_Stateful = __Regex_Global << 14, // Internal flag; enables stateful matches. + __Regex_Internal_BrowserExtended = __Regex_Global << 15, // Internal flag; enable browser-specific ECMA262 extensions. __Regex_Last = __Regex_SkipTrimEmptyMatches }; diff --git a/Userland/Libraries/LibRegex/RegexByteCode.cpp b/Userland/Libraries/LibRegex/RegexByteCode.cpp index 0987192af7..d9b91a6ec4 100644 --- a/Userland/Libraries/LibRegex/RegexByteCode.cpp +++ b/Userland/Libraries/LibRegex/RegexByteCode.cpp @@ -701,21 +701,35 @@ const Vector<String> OpCode_Compare::variable_arguments_to_string(Optional<Match for (size_t i = 0; i < arguments_count(); ++i) { auto compare_type = (CharacterCompareType)m_bytecode->at(offset++); - result.empend(String::format("type=%lu [%s]", (size_t)compare_type, character_compare_type_name(compare_type))); + result.empend(String::formatted("type={} [{}]", (size_t)compare_type, character_compare_type_name(compare_type))); auto compared_against_string_start_offset = state().string_position > 0 ? state().string_position - 1 : state().string_position; if (compare_type == CharacterCompareType::Char) { - char ch = m_bytecode->at(offset++); - result.empend(String::format("value='%c'", ch)); - if (!view.is_null() && view.length() > state().string_position) - result.empend(String::format( - "compare against: '%s'", - view.substring_view(compared_against_string_start_offset, state().string_position > view.length() ? 0 : 1).to_string().characters())); + auto ch = m_bytecode->at(offset++); + auto is_ascii = isascii(ch) && isprint(ch); + if (is_ascii) + result.empend(String::formatted("value='{:c}'", static_cast<char>(ch))); + else + result.empend(String::formatted("value={:x}", ch)); + + if (!view.is_null() && view.length() > state().string_position) { + if (is_ascii) { + result.empend(String::formatted( + "compare against: '{}'", + view.substring_view(compared_against_string_start_offset, state().string_position > view.length() ? 0 : 1).to_string())); + } else { + auto str = view.substring_view(compared_against_string_start_offset, state().string_position > view.length() ? 0 : 1).to_string(); + u8 buf[8] { 0 }; + __builtin_memcpy(buf, str.characters(), min(str.length(), sizeof(buf))); + result.empend(String::formatted("compare against: {:x},{:x},{:x},{:x},{:x},{:x},{:x},{:x}", + buf[0], buf[1], buf[2], buf[3], buf[4], buf[5], buf[6], buf[7])); + } + } } else if (compare_type == CharacterCompareType::NamedReference) { auto ptr = (const char*)m_bytecode->at(offset++); auto length = m_bytecode->at(offset++); - result.empend(String::format("name='%.*s'", (int)length, ptr)); + result.empend(String::formatted("name='{}'", StringView { ptr, (size_t)length })); } else if (compare_type == CharacterCompareType::Reference) { auto ref = m_bytecode->at(offset++); result.empend(String::formatted("number={}", ref)); @@ -724,25 +738,25 @@ const Vector<String> OpCode_Compare::variable_arguments_to_string(Optional<Match StringBuilder str_builder; for (size_t i = 0; i < length; ++i) str_builder.append(m_bytecode->at(offset++)); - result.empend(String::format("value=\"%.*s\"", (int)length, str_builder.string_view().characters_without_null_termination())); + result.empend(String::formatted("value=\"{}\"", str_builder.string_view().substring_view(0, length))); if (!view.is_null() && view.length() > state().string_position) - result.empend(String::format( - "compare against: \"%s\"", - input.value().view.substring_view(compared_against_string_start_offset, compared_against_string_start_offset + length > view.length() ? 0 : length).to_string().characters())); + result.empend(String::formatted( + "compare against: \"{}\"", + input.value().view.substring_view(compared_against_string_start_offset, compared_against_string_start_offset + length > view.length() ? 0 : length).to_string())); } else if (compare_type == CharacterCompareType::CharClass) { auto character_class = (CharClass)m_bytecode->at(offset++); - result.empend(String::format("ch_class=%lu [%s]", (size_t)character_class, character_class_name(character_class))); + result.empend(String::formatted("ch_class={} [{}]", (size_t)character_class, character_class_name(character_class))); if (!view.is_null() && view.length() > state().string_position) - result.empend(String::format( - "compare against: '%s'", - input.value().view.substring_view(compared_against_string_start_offset, state().string_position > view.length() ? 0 : 1).to_string().characters())); + result.empend(String::formatted( + "compare against: '{}'", + input.value().view.substring_view(compared_against_string_start_offset, state().string_position > view.length() ? 0 : 1).to_string())); } else if (compare_type == CharacterCompareType::CharRange) { auto value = (CharRange)m_bytecode->at(offset++); - result.empend(String::format("ch_range='%c'-'%c'", value.from, value.to)); + result.empend(String::formatted("ch_range='{:c}'-'{:c}'", value.from, value.to)); if (!view.is_null() && view.length() > state().string_position) - result.empend(String::format( - "compare against: '%s'", - input.value().view.substring_view(compared_against_string_start_offset, state().string_position > view.length() ? 0 : 1).to_string().characters())); + result.empend(String::formatted( + "compare against: '{}'", + input.value().view.substring_view(compared_against_string_start_offset, state().string_position > view.length() ? 0 : 1).to_string())); } } return result; diff --git a/Userland/Libraries/LibRegex/RegexMatch.h b/Userland/Libraries/LibRegex/RegexMatch.h index 73b332ac3e..f5ddf929f7 100644 --- a/Userland/Libraries/LibRegex/RegexMatch.h +++ b/Userland/Libraries/LibRegex/RegexMatch.h @@ -136,7 +136,9 @@ public: u32 operator[](size_t index) const { if (is_u8_view()) { - return u8view()[index]; + i8 ch = u8view()[index]; + u8 value = *reinterpret_cast<u8*>(&ch); + return static_cast<u32>(value); } return u32view().code_points()[index]; } diff --git a/Userland/Libraries/LibRegex/RegexOptions.h b/Userland/Libraries/LibRegex/RegexOptions.h index 5e860215fd..0279b7c803 100644 --- a/Userland/Libraries/LibRegex/RegexOptions.h +++ b/Userland/Libraries/LibRegex/RegexOptions.h @@ -39,22 +39,23 @@ namespace regex { using FlagsUnderlyingType = u16; enum class AllFlags { - Global = __Regex_Global, // All matches (don't return after first match) - Insensitive = __Regex_Insensitive, // Case insensitive match (ignores case of [a-zA-Z]) - Ungreedy = __Regex_Ungreedy, // The match becomes lazy by default. Now a ? following a quantifier makes it greedy - Unicode = __Regex_Unicode, // Enable all unicode features and interpret all unicode escape sequences as such - Extended = __Regex_Extended, // Ignore whitespaces. Spaces and text after a # in the pattern are ignored - Extra = __Regex_Extra, // Disallow meaningless escapes. A \ followed by a letter with no special meaning is faulted - MatchNotBeginOfLine = __Regex_MatchNotBeginOfLine, // Pattern is not forced to ^ -> search in whole string! - MatchNotEndOfLine = __Regex_MatchNotEndOfLine, // Don't Force the dollar sign, $, to always match end of the string, instead of end of the line. This option is ignored if the Multiline-flag is set - SkipSubExprResults = __Regex_SkipSubExprResults, // Do not return sub expressions in the result - StringCopyMatches = __Regex_StringCopyMatches, // Do explicitly copy results into new allocated string instead of StringView to original string. - SingleLine = __Regex_SingleLine, // Dot matches newline characters - Sticky = __Regex_Sticky, // Force the pattern to only match consecutive matches from where the previous match ended. - Multiline = __Regex_Multiline, // Handle newline characters. Match each line, one by one. - SkipTrimEmptyMatches = __Regex_SkipTrimEmptyMatches, // Do not remove empty capture group results. - Internal_Stateful = __Regex_Internal_Stateful, // Make global matches match one result at a time, and further match() calls on the same instance continue where the previous one left off. - Last = Internal_Stateful, + Global = __Regex_Global, // All matches (don't return after first match) + Insensitive = __Regex_Insensitive, // Case insensitive match (ignores case of [a-zA-Z]) + Ungreedy = __Regex_Ungreedy, // The match becomes lazy by default. Now a ? following a quantifier makes it greedy + Unicode = __Regex_Unicode, // Enable all unicode features and interpret all unicode escape sequences as such + Extended = __Regex_Extended, // Ignore whitespaces. Spaces and text after a # in the pattern are ignored + Extra = __Regex_Extra, // Disallow meaningless escapes. A \ followed by a letter with no special meaning is faulted + MatchNotBeginOfLine = __Regex_MatchNotBeginOfLine, // Pattern is not forced to ^ -> search in whole string! + MatchNotEndOfLine = __Regex_MatchNotEndOfLine, // Don't Force the dollar sign, $, to always match end of the string, instead of end of the line. This option is ignored if the Multiline-flag is set + SkipSubExprResults = __Regex_SkipSubExprResults, // Do not return sub expressions in the result + StringCopyMatches = __Regex_StringCopyMatches, // Do explicitly copy results into new allocated string instead of StringView to original string. + SingleLine = __Regex_SingleLine, // Dot matches newline characters + Sticky = __Regex_Sticky, // Force the pattern to only match consecutive matches from where the previous match ended. + Multiline = __Regex_Multiline, // Handle newline characters. Match each line, one by one. + SkipTrimEmptyMatches = __Regex_SkipTrimEmptyMatches, // Do not remove empty capture group results. + Internal_Stateful = __Regex_Internal_Stateful, // Make global matches match one result at a time, and further match() calls on the same instance continue where the previous one left off. + Internal_BrowserExtended = __Regex_Internal_BrowserExtended, // Only for ECMA262, Enable the behaviours defined in section B.1.4. of the ECMA262 spec. + Last = Internal_BrowserExtended, }; enum class PosixFlags : FlagsUnderlyingType { @@ -83,6 +84,7 @@ enum class ECMAScriptFlags : FlagsUnderlyingType { Sticky = (FlagsUnderlyingType)AllFlags::Sticky, Multiline = (FlagsUnderlyingType)AllFlags::Multiline, StringCopyMatches = (FlagsUnderlyingType)AllFlags::StringCopyMatches, + BrowserExtended = (FlagsUnderlyingType)AllFlags::Internal_BrowserExtended, }; template<class T> diff --git a/Userland/Libraries/LibRegex/RegexParser.cpp b/Userland/Libraries/LibRegex/RegexParser.cpp index eacc306975..a8f9b6b6cf 100644 --- a/Userland/Libraries/LibRegex/RegexParser.cpp +++ b/Userland/Libraries/LibRegex/RegexParser.cpp @@ -1,5 +1,6 @@ /* * Copyright (c) 2020, Emanuel Sprung <emanuel.sprung@gmail.com> + * Copyright (c) 2020-2021, the SerenityOS developers. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -51,6 +52,11 @@ ALWAYS_INLINE bool Parser::match(TokenType type) const return m_parser_state.current_token.type() == type; } +ALWAYS_INLINE bool Parser::match(char ch) const +{ + return m_parser_state.current_token.type() == TokenType::Char && m_parser_state.current_token.value().length() == 1 && m_parser_state.current_token.value()[0] == ch; +} + ALWAYS_INLINE Token Parser::consume() { auto old_token = m_parser_state.current_token; @@ -108,6 +114,16 @@ ALWAYS_INLINE bool Parser::try_skip(StringView str) return true; } +ALWAYS_INLINE bool Parser::lookahead_any(StringView str) +{ + for (auto ch : str) { + if (match(ch)) + return true; + } + + return false; +} + ALWAYS_INLINE char Parser::skip() { char ch; @@ -122,6 +138,12 @@ ALWAYS_INLINE char Parser::skip() return ch; } +ALWAYS_INLINE void Parser::back(size_t count) +{ + m_parser_state.lexer.back(count); + m_parser_state.current_token = m_parser_state.lexer.next(); +} + ALWAYS_INLINE void Parser::reset() { m_parser_state.bytecode.clear(); @@ -702,10 +724,25 @@ bool ECMA262Parser::parse_term(ByteCode& stack, size_t& match_length_minimum, bo ByteCode atom_stack; size_t minimum_atom_length = 0; - if (!parse_atom(atom_stack, minimum_atom_length, unicode, named)) - return false; + auto parse_with_quantifier = [&] { + bool did_parse_one = false; + if (m_should_use_browser_extended_grammar) + did_parse_one = parse_extended_atom(atom_stack, minimum_atom_length, named); + + if (!did_parse_one) + did_parse_one = parse_atom(atom_stack, minimum_atom_length, unicode, named); + + if (!did_parse_one) + return false; - if (!parse_quantifier(atom_stack, minimum_atom_length, unicode, named)) + VERIFY(did_parse_one); + if (!parse_quantifier(atom_stack, minimum_atom_length, unicode, named)) + return false; + + return true; + }; + + if (!parse_with_quantifier()) return false; stack.append(move(atom_stack)); @@ -749,35 +786,36 @@ bool ECMA262Parser::parse_assertion(ByteCode& stack, [[maybe_unused]] size_t& ma ByteCode assertion_stack; size_t length_dummy = 0; - auto parse_inner_disjunction = [&] { - auto disjunction_ok = parse_disjunction(assertion_stack, length_dummy, unicode, named); - if (!disjunction_ok) - return false; - consume(TokenType::RightParen, Error::MismatchingParen); - return true; - }; - - if (try_skip("=")) { - if (!parse_inner_disjunction()) + bool should_parse_forward_assertion = m_should_use_browser_extended_grammar ? unicode : true; + if (should_parse_forward_assertion && try_skip("=")) { + if (!parse_inner_disjunction(assertion_stack, length_dummy, unicode, named)) return false; stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::LookAhead); return true; } - if (try_skip("!")) { - if (!parse_inner_disjunction()) + if (should_parse_forward_assertion && try_skip("!")) { + if (!parse_inner_disjunction(assertion_stack, length_dummy, unicode, named)) return false; stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::NegatedLookAhead); return true; } + if (m_should_use_browser_extended_grammar) { + if (!unicode) { + if (parse_quantifiable_assertion(assertion_stack, match_length_minimum, named)) { + stack.append(move(assertion_stack)); + return true; + } + } + } if (try_skip("<=")) { - if (!parse_inner_disjunction()) + if (!parse_inner_disjunction(assertion_stack, length_dummy, unicode, named)) return false; // FIXME: Somehow ensure that this assertion regexp has a fixed length. stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::LookBehind, length_dummy); return true; } if (try_skip("<!")) { - if (!parse_inner_disjunction()) + if (!parse_inner_disjunction(assertion_stack, length_dummy, unicode, named)) return false; stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::NegatedLookBehind, length_dummy); return true; @@ -792,7 +830,40 @@ bool ECMA262Parser::parse_assertion(ByteCode& stack, [[maybe_unused]] size_t& ma return false; } -Optional<unsigned> ECMA262Parser::read_digits(ECMA262Parser::ReadDigitsInitialZeroState initial_zero, ECMA262Parser::ReadDigitFollowPolicy follow_policy, bool hex, int max_count) +bool ECMA262Parser::parse_inner_disjunction(ByteCode& bytecode_stack, size_t& length, bool unicode, bool named) +{ + auto disjunction_ok = parse_disjunction(bytecode_stack, length, unicode, named); + if (!disjunction_ok) + return false; + consume(TokenType::RightParen, Error::MismatchingParen); + return true; +} + +bool ECMA262Parser::parse_quantifiable_assertion(ByteCode& stack, size_t&, bool named) +{ + VERIFY(m_should_use_browser_extended_grammar); + ByteCode assertion_stack; + size_t match_length_minimum = 0; + + if (try_skip("=")) { + if (!parse_inner_disjunction(assertion_stack, match_length_minimum, false, named)) + return false; + + stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::LookAhead); + return true; + } + if (try_skip("!")) { + if (!parse_inner_disjunction(assertion_stack, match_length_minimum, false, named)) + return false; + + stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::NegatedLookAhead); + return true; + } + + return false; +} + +StringView ECMA262Parser::read_digits_as_string(ReadDigitsInitialZeroState initial_zero, ReadDigitFollowPolicy follow_policy, bool hex, int max_count) { if (!match(TokenType::Char)) return {}; @@ -832,10 +903,16 @@ Optional<unsigned> ECMA262Parser::read_digits(ECMA262Parser::ReadDigitsInitialZe ++count; } - StringView str { start_token.value().characters_without_null_termination(), offset }; + return StringView { start_token.value().characters_without_null_termination(), offset }; +} + +Optional<unsigned> ECMA262Parser::read_digits(ECMA262Parser::ReadDigitsInitialZeroState initial_zero, ECMA262Parser::ReadDigitFollowPolicy follow_policy, bool hex, int max_count) +{ + auto str = read_digits_as_string(initial_zero, follow_policy, hex, max_count); + if (str.is_empty()) + return {}; if (hex) return AK::StringUtils::convert_to_uint_from_hex(str); - return str.to_uint(); } @@ -948,12 +1025,12 @@ bool ECMA262Parser::parse_atom(ByteCode& stack, size_t& match_length_minimum, bo if (match(TokenType::LeftBracket)) { // Character class. - return parse_character_class(stack, match_length_minimum, unicode, named); + return parse_character_class(stack, match_length_minimum, unicode && !m_should_use_browser_extended_grammar, named); } if (match(TokenType::LeftParen)) { // Non-capturing group, or a capture group. - return parse_capture_group(stack, match_length_minimum, unicode, named); + return parse_capture_group(stack, match_length_minimum, unicode && !m_should_use_browser_extended_grammar, named); } if (match(TokenType::Period)) { @@ -963,13 +1040,24 @@ bool ECMA262Parser::parse_atom(ByteCode& stack, size_t& match_length_minimum, bo return true; } - if (match(TokenType::Circumflex) || match(TokenType::Dollar) || match(TokenType::RightBracket) - || match(TokenType::RightCurly) || match(TokenType::RightParen) || match(TokenType::Pipe) - || match(TokenType::Plus) || match(TokenType::Asterisk) || match(TokenType::Questionmark)) { + if (match(TokenType::Circumflex) || match(TokenType::Dollar) || match(TokenType::RightParen) + || match(TokenType::Pipe) || match(TokenType::Plus) || match(TokenType::Asterisk) + || match(TokenType::Questionmark)) { return false; } + if (match(TokenType::RightBracket) || match(TokenType::RightCurly) || match(TokenType::LeftCurly)) { + if (m_should_use_browser_extended_grammar) { + auto token = consume(); + match_length_minimum += 1; + stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)token.value()[0] } }); + return true; + } else { + return false; + } + } + if (match_ordinary_characters()) { auto token = consume().value(); match_length_minimum += 1; @@ -981,17 +1069,67 @@ bool ECMA262Parser::parse_atom(ByteCode& stack, size_t& match_length_minimum, bo return false; } +bool ECMA262Parser::parse_extended_atom(ByteCode&, size_t&, bool) +{ + // Note: This includes only rules *not* present in parse_atom() + VERIFY(m_should_use_browser_extended_grammar); + + if (parse_invalid_braced_quantifier()) + return true; // FAIL FAIL FAIL + + return false; +} + +bool ECMA262Parser::parse_invalid_braced_quantifier() +{ + if (!match(TokenType::LeftCurly)) + return false; + consume(); + size_t chars_consumed = 1; + auto low_bound = read_digits_as_string(); + StringView high_bound; + + if (low_bound.is_empty()) { + back(chars_consumed + 1); + return false; + } + chars_consumed += low_bound.length(); + if (match(TokenType::Comma)) { + consume(); + ++chars_consumed; + + high_bound = read_digits_as_string(); + chars_consumed += high_bound.length(); + } + + if (!match(TokenType::RightCurly)) { + back(chars_consumed + 1); + return false; + } + + consume(); + set_error(Error::InvalidPattern); + return true; +} + bool ECMA262Parser::parse_atom_escape(ByteCode& stack, size_t& match_length_minimum, bool unicode, bool named) { - if (auto escape = read_digits(ReadDigitsInitialZeroState::Disallow, ReadDigitFollowPolicy::DisallowNonDigit); escape.has_value()) { - auto maybe_length = m_parser_state.capture_group_minimum_lengths.get(escape.value()); - if (!maybe_length.has_value()) { - set_error(Error::InvalidNumber); - return false; + if (auto escape_str = read_digits_as_string(ReadDigitsInitialZeroState::Disallow, ReadDigitFollowPolicy::DisallowNonDigit); !escape_str.is_empty()) { + if (auto escape = escape_str.to_uint(); escape.has_value()) { + auto maybe_length = m_parser_state.capture_group_minimum_lengths.get(escape.value()); + if (maybe_length.has_value()) { + match_length_minimum += maybe_length.value(); + stack.insert_bytecode_compare_values({ { CharacterCompareType::Reference, (ByteCodeValueType)escape.value() } }); + return true; + } + if (!m_should_use_browser_extended_grammar) { + set_error(Error::InvalidNumber); + return false; + } } - match_length_minimum += maybe_length.value(); - stack.insert_bytecode_compare_values({ { CharacterCompareType::Reference, (ByteCodeValueType)escape.value() } }); - return true; + + // If not, put the characters back. + back(escape_str.length()); } // CharacterEscape > ControlEscape @@ -1030,11 +1168,18 @@ bool ECMA262Parser::parse_atom_escape(ByteCode& stack, size_t& match_length_mini for (auto c = 'A'; c <= 'z'; ++c) { if (try_skip({ &c, 1 })) { match_length_minimum += 1; - stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)(c & 0x3f) } }); + stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)(c % 32) } }); return true; } } + if (m_should_use_browser_extended_grammar) { + back(2); + stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)'\\' } }); + match_length_minimum += 1; + return true; + } + if (unicode) { set_error(Error::InvalidPattern); return false; @@ -1046,6 +1191,17 @@ bool ECMA262Parser::parse_atom_escape(ByteCode& stack, size_t& match_length_mini return true; } + // LegacyOctalEscapeSequence + if (m_should_use_browser_extended_grammar) { + if (!unicode) { + if (auto escape = parse_legacy_octal_escape(); escape.has_value()) { + stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)escape.value() } }); + match_length_minimum += 1; + return true; + } + } + } + // '\0' if (read_digits(ReadDigitsInitialZeroState::Require, ReadDigitFollowPolicy::DisallowDigit).has_value()) { match_length_minimum += 1; @@ -1092,7 +1248,8 @@ bool ECMA262Parser::parse_atom_escape(ByteCode& stack, size_t& match_length_mini } // IdentityEscape - for (auto ch : StringView { "^$\\.*+?()[]{}|" }) { + auto source_characters = m_should_use_browser_extended_grammar ? "^$\\.*+?()[|"sv : "^$\\.*+?()[]{}|"sv; + for (auto ch : source_characters) { if (try_skip({ &ch, 1 })) { match_length_minimum += 1; stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)ch } }); @@ -1162,6 +1319,59 @@ bool ECMA262Parser::parse_atom_escape(ByteCode& stack, size_t& match_length_mini stack.insert_bytecode_compare_values(move(compares)); return true; } +Optional<u8> ECMA262Parser::parse_legacy_octal_escape() +{ + constexpr auto all_octal_digits = "01234567"; + auto read_octal_digit = [&](auto start, auto end, bool should_ensure_no_following_octal_digit) -> Optional<u8> { + for (char c = '0' + start; c <= '0' + end; ++c) { + if (try_skip({ &c, 1 })) { + if (!should_ensure_no_following_octal_digit || !lookahead_any(all_octal_digits)) + return c - '0'; + back(2); + return {}; + } + } + return {}; + }; + + // OctalDigit(1) + if (auto digit = read_octal_digit(0, 7, true); digit.has_value()) { + return digit.value(); + } + + // OctalDigit(2) + if (auto left_digit = read_octal_digit(0, 3, false); left_digit.has_value()) { + if (auto right_digit = read_octal_digit(0, 7, true); right_digit.has_value()) { + return left_digit.value() * 8 + right_digit.value(); + } + + back(2); + } + + // OctalDigit(2) + if (auto left_digit = read_octal_digit(4, 7, false); left_digit.has_value()) { + if (auto right_digit = read_octal_digit(0, 7, false); right_digit.has_value()) { + return left_digit.value() * 8 + right_digit.value(); + } + + back(2); + } + + // OctalDigit(3) + if (auto left_digit = read_octal_digit(0, 3, false); left_digit.has_value()) { + size_t chars_consumed = 1; + if (auto mid_digit = read_octal_digit(0, 7, false); mid_digit.has_value()) { + ++chars_consumed; + if (auto right_digit = read_octal_digit(0, 7, false); right_digit.has_value()) { + return left_digit.value() * 64 + mid_digit.value() * 8 + right_digit.value(); + } + } + + back(chars_consumed); + } + + return {}; +} Optional<CharClass> ECMA262Parser::parse_character_class_escape(bool& negate, bool expect_backslash) { @@ -1260,7 +1470,18 @@ bool ECMA262Parser::parse_nonempty_class_ranges(Vector<CompareTypeAndValuePair>& if (try_skip("c")) { for (auto c = 'A'; c <= 'z'; ++c) { if (try_skip({ &c, 1 })) - return { { .code_point = (u32)(c & 0x3f), .is_character_class = false } }; + return { { .code_point = (u32)(c % 32), .is_character_class = false } }; + } + if (m_should_use_browser_extended_grammar) { + for (auto c = '0'; c <= '9'; ++c) { + if (try_skip({ &c, 1 })) + return { { .code_point = (u32)(c % 32), .is_character_class = false } }; + } + if (try_skip("_")) + return { { .code_point = (u32)('_' % 32), .is_character_class = false } }; + + back(2); + return { { .code_point = '\\', .is_character_class = false } }; } } @@ -1361,8 +1582,28 @@ bool ECMA262Parser::parse_nonempty_class_ranges(Vector<CompareTypeAndValuePair>& return false; if (first_atom.value().is_character_class || second_atom.value().is_character_class) { - set_error(Error::InvalidRange); - return false; + if (m_should_use_browser_extended_grammar) { + if (unicode) { + set_error(Error::InvalidRange); + return false; + } + // CharacterRangeOrUnion > !Unicode > CharClass + if (first_atom->is_character_class) + ranges.empend(CompareTypeAndValuePair { CharacterCompareType::CharClass, (ByteCodeValueType)first_atom->character_class }); + else + ranges.empend(CompareTypeAndValuePair { CharacterCompareType::Char, (ByteCodeValueType)first_atom->code_point }); + + ranges.empend(CompareTypeAndValuePair { CharacterCompareType::Char, (ByteCodeValueType)'-' }); + + if (second_atom->is_character_class) + ranges.empend(CompareTypeAndValuePair { CharacterCompareType::CharClass, (ByteCodeValueType)second_atom->character_class }); + else + ranges.empend(CompareTypeAndValuePair { CharacterCompareType::Char, (ByteCodeValueType)second_atom->code_point }); + continue; + } else { + set_error(Error::InvalidRange); + return false; + } } if (first_atom.value().code_point > second_atom.value().code_point) { diff --git a/Userland/Libraries/LibRegex/RegexParser.h b/Userland/Libraries/LibRegex/RegexParser.h index eb80c6f583..c8f24b094c 100644 --- a/Userland/Libraries/LibRegex/RegexParser.h +++ b/Userland/Libraries/LibRegex/RegexParser.h @@ -95,7 +95,9 @@ protected: ALWAYS_INLINE Token consume(TokenType type, Error error); ALWAYS_INLINE bool consume(const String&); ALWAYS_INLINE bool try_skip(StringView); + ALWAYS_INLINE bool lookahead_any(StringView); ALWAYS_INLINE char skip(); + ALWAYS_INLINE void back(size_t = 1); ALWAYS_INLINE void reset(); ALWAYS_INLINE bool done() const; ALWAYS_INLINE bool set_error(Error error); @@ -165,6 +167,7 @@ public: ECMA262Parser(Lexer& lexer, Optional<typename ParserTraits<ECMA262Parser>::OptionsType> regex_options) : Parser(lexer, regex_options.value_or({})) { + m_should_use_browser_extended_grammar = regex_options.has_value() && regex_options->has_flag_set(ECMAScriptFlags::BrowserExtended); } ~ECMA262Parser() = default; @@ -182,6 +185,7 @@ private: DisallowDigit, DisallowNonDigit, }; + StringView read_digits_as_string(ReadDigitsInitialZeroState initial_zero = ReadDigitsInitialZeroState::Allow, ReadDigitFollowPolicy follow_policy = ReadDigitFollowPolicy::Any, bool hex = false, int max_count = -1); Optional<unsigned> read_digits(ReadDigitsInitialZeroState initial_zero = ReadDigitsInitialZeroState::Allow, ReadDigitFollowPolicy follow_policy = ReadDigitFollowPolicy::Any, bool hex = false, int max_count = -1); StringView read_capture_group_specifier(bool take_starting_angle_bracket = false); @@ -197,6 +201,17 @@ private: bool parse_capture_group(ByteCode&, size_t&, bool unicode, bool named); Optional<CharClass> parse_character_class_escape(bool& out_inverse, bool expect_backslash = false); bool parse_nonempty_class_ranges(Vector<CompareTypeAndValuePair>&, bool unicode); + + // Used only by B.1.4, Regular Expression Patterns (Extended for use in browsers) + bool parse_quantifiable_assertion(ByteCode&, size_t&, bool named); + bool parse_extended_atom(ByteCode&, size_t&, bool named); + bool parse_inner_disjunction(ByteCode& bytecode_stack, size_t& length, bool unicode, bool named); + bool parse_invalid_braced_quantifier(); // Note: This function either parses and *fails*, or doesn't parse anything and returns false. + bool parse_legacy_octal_escape_sequence(ByteCode& bytecode_stack, size_t& length); + Optional<u8> parse_legacy_octal_escape(); + + // Keep the Annex B. behaviour behind a flag, the users can enable it by passing the `ECMAScriptFlags::BrowserExtended` flag. + bool m_should_use_browser_extended_grammar { false }; }; using PosixExtended = PosixExtendedParser; diff --git a/Userland/Libraries/LibRegex/Tests/Regex.cpp b/Userland/Libraries/LibRegex/Tests/Regex.cpp index 93bab8d705..3732d13498 100644 --- a/Userland/Libraries/LibRegex/Tests/Regex.cpp +++ b/Userland/Libraries/LibRegex/Tests/Regex.cpp @@ -501,6 +501,8 @@ TEST_CASE(ECMA262_parse) { "\\u1234", regex::Error::NoError, regex::ECMAScriptFlags::Unicode }, { "[\\u1234]", regex::Error::NoError, regex::ECMAScriptFlags::Unicode }, { ",(?", regex::Error::InvalidCaptureGroup }, // #4583 + { "{1}", regex::Error::InvalidPattern }, + { "{1,2}", regex::Error::InvalidPattern }, }; for (auto& test : tests) { @@ -525,7 +527,7 @@ TEST_CASE(ECMA262_match) bool matches { true }; ECMAScriptFlags options {}; }; - + // clang-format off constexpr _test tests[] { { "^hello.$", "hello1" }, { "^(hello.)$", "hello1" }, @@ -547,7 +549,21 @@ TEST_CASE(ECMA262_match) { "bar.*(?<!foo)", "barbar", true }, { "((...)X)+", "fooXbarXbazX", true }, { "(?:)", "", true }, + // ECMA262, B.1.4. Regular Expression Pattern extensions for browsers + { "{", "{", true, ECMAScriptFlags::BrowserExtended }, + { "\\5", "\5", true, ECMAScriptFlags::BrowserExtended }, + { "\\05", "\5", true, ECMAScriptFlags::BrowserExtended }, + { "\\455", "\45""5", true, ECMAScriptFlags::BrowserExtended }, + { "\\314", "\314", true, ECMAScriptFlags::BrowserExtended }, + { "\\cf", "\06", true, ECMAScriptFlags::BrowserExtended }, + { "\\c1", "\\c1", true, ECMAScriptFlags::BrowserExtended }, + { "[\\c1]", "\x11", true, ECMAScriptFlags::BrowserExtended }, + { "[\\w-\\d]", "-", true, ECMAScriptFlags::BrowserExtended }, + { "^(?:^^\\.?|[!+-]|!=|!==|#|%|%=|&|&&|&&=|&=|\\(|\\*|\\*=|\\+=|,|-=|->|\\/|\\/=|:|::|;|<|<<|<<=|<=|=|==|===|>|>=|>>|>>=|>>>|>>>=|[?@[^]|\\^=|\\^\\^|\\^\\^=|{|\\||\\|=|\\|\\||\\|\\|=|~|break|case|continue|delete|do|else|finally|instanceof|return|throw|try|typeof)\\s*(\\/(?=[^*/])(?:[^/[\\\\]|\\\\[\\S\\s]|\\[(?:[^\\\\\\]]|\\\\[\\S\\s])*(?:]|$))+\\/)", + "return /xx/", true, ECMAScriptFlags::BrowserExtended + }, // #5517, appears to be matching JS expressions that involve regular expressions... }; + // clang-format on for (auto& test : tests) { Regex<ECMA262> re(test.pattern, test.options); |