blob: 82259ed70d40ebeae0e82bbf2522f229f8f61d1f [file]
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// Regular expression parser implementation.
///
//===----------------------------------------------------------------------===//
#include "src/__support/regex/regex_parser.h"
#include "hdr/limits_macros.h"
#include "hdr/regex_macros.h"
#include "src/__support/CPP/array.h"
#include "src/__support/CPP/optional.h"
#include "src/__support/CPP/span.h"
#include "src/__support/CPP/string_view.h"
#include "src/__support/CPP/unique_ptr.h"
#include "src/__support/checked_ptr.h"
#include "src/__support/ctype_utils.h"
#include "src/__support/error_or.h"
#include "src/__support/libc_assert.h"
#include "src/__support/macros/config.h"
#include "src/__support/regex/regex_ast.h"
#include "src/__support/regex/regex_charclass.h"
#include "src/__support/regex/regex_expr_pool.h"
namespace LIBC_NAMESPACE_DECL {
namespace regex {
namespace {
// Returns true for backslash escape sequences that represent backreferences,
// boundary assertions, or character-class shorthands rather than escaped
// literal characters.
constexpr bool is_unimplemented_ere_escape(char c) {
switch (c) {
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case 'b':
case 'B':
case '<':
case '>':
case 'A':
case 'Z':
case '`':
case '\'':
return true;
default:
return false;
}
}
// Parses a single collating element [[.c.]] or equivalence class [[=c=]].
ErrorOr<uint8_t> parse_coll_elem(cpp::string_view &rem) {
cpp::string_view close_delim = rem.starts_with("[.") ? ".]" : "=]";
rem.remove_prefix(2);
// TODO: Adopt cpp::string_view::find once implemented in
// src/__support/CPP/string_view.h.
size_t delim_pos = 0;
while (delim_pos + 2 <= rem.size() &&
!rem.substr(delim_pos).starts_with(close_delim))
++delim_pos;
if (delim_pos + 2 > rem.size())
return Error(REG_EBRACK);
cpp::string_view elem = rem.substr(0, delim_pos);
rem.remove_prefix(delim_pos + 2);
if (elem.size() == 1)
return static_cast<uint8_t>(elem.front());
if (elem == "one")
return static_cast<uint8_t>('1');
return Error(REG_ECOLLATE);
}
// Parses a single bracket expression item (collating element or single byte).
ErrorOr<uint8_t> parse_bracket_elem(cpp::string_view &rem) {
if (rem.starts_with("[.") || rem.starts_with("[="))
return parse_coll_elem(rem);
uint8_t c = static_cast<uint8_t>(rem.front());
rem.remove_prefix(1);
return c;
}
// Parses a POSIX bracket expression [...], returning a ByteSet node.
ErrorOr<ExprId> parse_bracket_expr(cpp::string_view &rem, int cflags,
ExprPool &pool) {
bool negate = false;
if (rem.starts_with('^')) {
negate = true;
rem.remove_prefix(1);
}
ByteSet bs;
bool first = true;
while (!rem.empty()) {
if (rem.starts_with(']') && !first) {
rem.remove_prefix(1);
if (negate) {
bs.flip();
bs.reset(0);
if (cflags & REG_NEWLINE)
bs.reset('\n');
}
return pool.make_byte_set(bs);
}
first = false;
if (rem.starts_with("[:")) {
rem.remove_prefix(2);
// TODO: Adopt cpp::string_view::find once implemented in
// src/__support/CPP/string_view.h.
size_t delim_pos = 0;
while (delim_pos + 2 <= rem.size() &&
!rem.substr(delim_pos).starts_with(":]"))
++delim_pos;
if (delim_pos + 2 > rem.size())
return Error(REG_EBRACK);
cpp::string_view name = rem.substr(0, delim_pos);
rem.remove_prefix(delim_pos + 2);
if (name == "<" || name == ">")
return Error(REG_BADPAT);
cpp::optional<ByteSet> opt = lookup_posix_class(name);
if (!opt.has_value())
return Error(REG_ECTYPE);
bs |= *opt;
if (rem.starts_with('-') && !rem.starts_with("-]"))
return Error(REG_ERANGE);
continue;
}
ErrorOr<uint8_t> c1 = parse_bracket_elem(rem);
if (!c1.has_value())
return Error(c1.error());
if (rem.starts_with('-') && !rem.starts_with("-]")) {
rem.remove_prefix(1);
if (rem.empty())
return Error(REG_ERANGE);
if (rem.starts_with("[:"))
return Error(REG_ERANGE);
ErrorOr<uint8_t> c2 = parse_bracket_elem(rem);
if (!c2.has_value())
return Error(c2.error());
if (*c1 > *c2)
return Error(REG_ERANGE);
bs.set_range(*c1, *c2);
if (rem.starts_with('-') && !rem.starts_with("-]"))
return Error(REG_ERANGE);
} else {
bs.set(*c1);
}
}
return Error(REG_EBRACK);
}
// Maximum parenthesized group nesting depth to prevent parser stack overflow.
constexpr size_t MAX_GROUP_DEPTH = 128;
// Parses a decimal repetition bound in [0, RE_DUP_MAX] from the prefix of spec.
constexpr cpp::optional<uint16_t> consume_bound(cpp::string_view &spec) {
LIBC_ASSERT(!spec.empty() && internal::isdigit(spec.front()));
uint32_t val = 0;
do {
val = val * 10 + static_cast<uint32_t>(spec.front() - '0');
if (val > RE_DUP_MAX)
return cpp::nullopt;
spec.remove_prefix(1);
} while (!spec.empty() && internal::isdigit(spec.front()));
return static_cast<uint16_t>(val);
}
// Parses a trailing '{m}', '{m,}', or '{m,n}' interval quantifier after '{' has
// been matched with a leading digit.
ErrorOr<ExprId> parse_repeat_bounds(cpp::string_view &rem, ExprId atom,
ExprPool &pool, ExprId &prefix_atom) {
rem.remove_prefix(1);
// Scan for '}' before parsing bounds so unclosed "a{1,x" reports REG_EBRACE.
size_t close_pos = rem.find_first_of('}');
if (close_pos == cpp::string_view::npos)
return Error(REG_EBRACE);
cpp::string_view spec = rem.substr(0, close_pos);
rem.remove_prefix(close_pos + 1);
cpp::optional<uint16_t> min_opt = consume_bound(spec);
if (!min_opt.has_value())
return Error(REG_BADBR);
uint16_t min_val = *min_opt;
uint16_t max_val = min_val;
if (spec.starts_with(',')) {
spec.remove_prefix(1);
if (spec.empty()) {
max_val = REPEAT_INF;
} else if (internal::isdigit(spec.front())) {
cpp::optional<uint16_t> max_opt = consume_bound(spec);
if (!max_opt.has_value() || !spec.empty() || min_val > *max_opt)
return Error(REG_BADBR);
max_val = *max_opt;
} else {
return Error(REG_BADBR);
}
} else if (!spec.empty()) {
return Error(REG_BADBR);
}
uint16_t bound = (max_val == REPEAT_INF) ? min_val : max_val;
if (static_cast<uint32_t>(bound) * pool.get(atom).rep_expansion >
MAX_REPEAT_EXPANSION)
return Error(REG_ESPACE);
if (min_val == 1 && max_val == REPEAT_INF) {
ErrorOr<ExprId> star = pool.make_star(atom);
if (star.has_value())
prefix_atom = atom;
return star;
}
return pool.make_repeat(atom, min_val, max_val);
}
struct ParsedAtomStack;
ErrorOr<ExprId> parse_alt(cpp::string_view &rem, int cflags, ExprPool &pool,
size_t depth, size_t &re_nsub,
ParsedAtomStack &stack);
// Parses a single ERE atom and an optional trailing '*', '+', '?', or '{m,n}'
// quantifier.
ErrorOr<ExprId> parse_quantified_atom(cpp::string_view &rem, int cflags,
ExprPool &pool, size_t depth,
size_t &re_nsub, ParsedAtomStack &stack,
ExprId &prefix_atom) {
char c = rem.front();
rem.remove_prefix(1);
ErrorOr<ExprId> atom = INVALID_EXPR_ID;
bool can_repeat = true;
switch (c) {
case '\\': {
if (rem.empty())
return Error(REG_EESCAPE);
c = rem.front();
rem.remove_prefix(1);
switch (c) {
case 'd':
case 's':
case 'w': {
const ByteSet bs = (c == 'd') ? digit_class_set()
: (c == 's') ? space_class_set()
: word_class_set();
atom = pool.make_byte_set(bs);
break;
}
case 'D':
case 'S':
case 'W': {
ByteSet bs = (c == 'D') ? digit_class_set()
: (c == 'S') ? space_class_set()
: word_class_set();
bs.flip();
bs.reset(0);
if (cflags & REG_NEWLINE)
bs.reset('\n');
atom = pool.make_byte_set(bs);
break;
}
default:
if (is_unimplemented_ere_escape(c))
return Error(REG_BADPAT);
atom = pool.make_lit(c);
break;
}
break;
}
case '.': {
ByteSet bs;
if (cflags & REG_NEWLINE) {
bs.set_range(0, '\n' - 1);
bs.set_range('\n' + 1, BYTE_SET_BITS - 1);
} else {
bs.flip();
}
atom = pool.make_byte_set(bs);
break;
}
case '^':
atom = pool.make_anchor(ANCHOR_BOL);
can_repeat = false;
break;
case '$':
atom = pool.make_anchor(ANCHOR_EOL);
can_repeat = false;
break;
// Valid postfix '*', '+', '?', or '{m,n}' is consumed after a repeatable
// atom below; reaching a quantifier at the start of an atom means it has no
// preceding repeatable atom (e.g. "*a", "^*", or doubled "a**").
case '*':
case '+':
case '?':
return Error(REG_BADRPT);
case '{':
if (!rem.empty() && internal::isdigit(rem.front()))
return Error(REG_BADRPT);
atom = pool.make_lit('{');
break;
case '[':
atom = parse_bracket_expr(rem, cflags, pool);
break;
case '(': {
if (depth >= MAX_GROUP_DEPTH)
return Error(REG_ESPACE);
++re_nsub;
ErrorOr<ExprId> inner =
parse_alt(rem, cflags, pool, depth + 1, re_nsub, stack);
if (!inner.has_value())
return inner;
if (!rem.starts_with(')'))
return Error(REG_EPAREN);
rem.remove_prefix(1);
atom = inner;
break;
}
case ')':
// At depth 0, unmatched ')' is treated as a literal character per
// POSIX.1-2024 9.4.3. At depth > 0, parse_concat stops before ')'.
atom = pool.make_lit(')');
break;
default:
atom = pool.make_lit(c);
break;
}
if (!atom.has_value() || !can_repeat)
return atom;
if (rem.starts_with('*')) {
rem.remove_prefix(1);
return pool.make_star(*atom);
}
// Push r and Star(r) separately rather than Repeat(r, 1, REPEAT_INF) so
// right-to-left folding links r and r* directly into the enclosing Concat
// spine without an extra intermediate Concat(r, r*) node when r is itself a
// Concat (e.g. (ab)+c folds into a . (b . ((ab)* . c))).
if (rem.starts_with('+')) {
rem.remove_prefix(1);
ErrorOr<ExprId> star = pool.make_star(*atom);
if (star.has_value())
prefix_atom = *atom;
return star;
}
if (rem.starts_with('?')) {
rem.remove_prefix(1);
return pool.make_alt(EMPTY_STR_ID, *atom);
}
if (rem.size() >= 2 && rem[0] == '{' && internal::isdigit(rem[1]))
return parse_repeat_bounds(rem, *atom, pool, prefix_atom);
return atom;
}
// Shared stack of parsed ExprId nodes across recursive parse_alt and
// parse_concat frames. Keeps a 64-element (256-byte) inline buffer on the
// top-level parse_ere frame, spilling to the heap only for larger patterns.
// TODO: Replace ParsedAtomStack with an AllocChecker-backed SmallVector once
// available in src/__support/CPP/.
struct ParsedAtomStack {
static constexpr size_t INLINE_ATOM_COUNT = 64;
cpp::array<ExprId, INLINE_ATOM_COUNT> inline_atoms{};
cpp::unique_ptr<ExprId[]> heap_atoms;
cpp::span<ExprId> atoms{inline_atoms};
size_t count = 0;
ParsedAtomStack() = default;
// `atoms` may point into `inline_atoms`, so the implicit move operations
// would leave the destination pointing into the source.
ParsedAtomStack(ParsedAtomStack &&) = delete;
ParsedAtomStack &operator=(ParsedAtomStack &&) = delete;
bool push(ExprId id) {
if (count >= ExprPool::MAX_NODE_LIMIT)
return false;
if (count == atoms.size()) {
size_t new_cap = atoms.size() * 2;
auto new_atoms = make_unique_for_overwrite<ExprId[]>(new_cap);
if (!new_atoms)
return false;
for (size_t i = 0; i < count; ++i)
new_atoms[i] = atoms[i];
heap_atoms = new_atoms.take_unique();
atoms = cpp::span<ExprId>(heap_atoms.get(), new_cap);
}
atoms[count] = id;
++count;
return true;
}
ExprId pop() {
--count;
return atoms[count];
}
};
// Parses a single concatenation branch (sequence of quantified atoms).
ErrorOr<ExprId> parse_concat(cpp::string_view &rem, int cflags, ExprPool &pool,
size_t depth, size_t &re_nsub,
ParsedAtomStack &stack) {
// Collect quantified atoms for this branch on the shared stack, then fold
// right-to-left so non-Concat atoms link in O(1) without re-association.
size_t atom_count = 0;
while (!rem.empty() && !rem.starts_with('|') &&
!(depth > 0 && rem.starts_with(')'))) {
ExprId prefix_atom = INVALID_EXPR_ID;
ErrorOr<ExprId> atom = parse_quantified_atom(rem, cflags, pool, depth,
re_nsub, stack, prefix_atom);
if (!atom.has_value())
return atom;
if (prefix_atom != INVALID_EXPR_ID) {
if (!stack.push(prefix_atom))
return Error(REG_ESPACE);
++atom_count;
}
if (!stack.push(*atom))
return Error(REG_ESPACE);
++atom_count;
}
ErrorOr<ExprId> acc = pool.empty_str();
if (!acc.has_value())
return acc;
for (; atom_count > 0; --atom_count) {
acc = pool.make_concat(stack.pop(), *acc);
if (!acc.has_value())
return acc;
}
return acc;
}
// Parses an alternation expression (branches separated by '|').
ErrorOr<ExprId> parse_alt(cpp::string_view &rem, int cflags, ExprPool &pool,
size_t depth, size_t &re_nsub,
ParsedAtomStack &stack) {
if (rem.starts_with('|'))
return Error(REG_BADPAT);
ErrorOr<ExprId> first =
parse_concat(rem, cflags, pool, depth, re_nsub, stack);
if (!first.has_value() || !rem.starts_with('|'))
return first;
if (!stack.push(*first))
return Error(REG_ESPACE);
size_t branch_count = 1;
while (rem.starts_with('|')) {
rem.remove_prefix(1);
if (rem.empty() || rem.starts_with('|') ||
(depth > 0 && rem.starts_with(')')))
return Error(REG_BADPAT);
ErrorOr<ExprId> branch =
parse_concat(rem, cflags, pool, depth, re_nsub, stack);
if (!branch.has_value())
return branch;
if (!stack.push(*branch))
return Error(REG_ESPACE);
++branch_count;
}
// Fold alternation branches right-to-left so right-associative sorted
// make_alt stays O(1) per branch without orphaned spine nodes.
ErrorOr<ExprId> acc = EMPTY_SET_ID;
for (; branch_count > 0; --branch_count) {
acc = pool.make_alt(stack.pop(), *acc);
if (!acc.has_value())
return acc;
}
return acc;
}
} // namespace
// Top-level entry point: parses an ERE pattern starting from alternation at
// depth 0 and optionally returns the total count of parenthesized
// subexpressions.
ErrorOr<ExprId> parse_ere(cpp::string_view pattern, int cflags, ExprPool &pool,
size_t *out_re_nsub) {
cpp::string_view rem = pattern;
size_t re_nsub = 0;
ParsedAtomStack stack;
ErrorOr<ExprId> res =
parse_alt(rem, cflags, pool, /*depth=*/0, re_nsub, stack);
if (!res.has_value())
return res;
if (out_re_nsub != nullptr)
*out_re_nsub = re_nsub;
return res;
}
} // namespace regex
} // namespace LIBC_NAMESPACE_DECL