blob: b3b62d3312ff7b641d43708a25a2c154cf7c059b [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
/// Pool for Regular Expression AST nodes (Implementation).
///
//===----------------------------------------------------------------------===//
#include "src/__support/regex/regex_expr_pool.h"
#include "hdr/regex_macros.h"
#include "src/__support/CPP/algorithm.h"
#include "src/__support/CPP/optional.h"
#include "src/__support/CPP/utility.h"
#include "src/__support/checked_ptr.h"
#include "src/__support/hash.h"
#include "src/__support/macros/config.h"
namespace LIBC_NAMESPACE_DECL {
namespace regex {
namespace {
// Hash an Expr node for hash-consing.
uint32_t hash_expr(const Expr &e) {
// Initialise HashState with a constant seed. The specific value (0x12345678)
// is an arbitrary placeholder; HashState immediately mixes this seed with
// high-entropy constants (derived from aHash) to produce a strong hash, while
// the constant value guarantees deterministic hashing for hash-consing.
internal::HashState hasher(0x12345678);
struct HashKey {
uint64_t kind;
uint64_t payload;
} key = {static_cast<uint64_t>(e.kind), 0};
static_assert(sizeof(HashKey) == 2 * sizeof(uint64_t));
switch (e.kind) {
case ExprKind::Literal:
key.payload = static_cast<uint8_t>(e.ch);
break;
case ExprKind::Anchor:
key.payload = e.anchor_mask;
break;
case ExprKind::ByteSet:
key.payload = e.byte_set_id;
break;
case ExprKind::Star:
key.payload = e.body;
break;
case ExprKind::Repeat:
key.payload = (static_cast<uint64_t>(e.rep.body) << 32) |
(static_cast<uint64_t>(e.rep.min) << 16) | e.rep.max;
break;
case ExprKind::Concat:
case ExprKind::Alt:
key.payload = (static_cast<uint64_t>(e.bin.left) << 32) | e.bin.right;
break;
default:
break;
}
hasher.update(&key, sizeof(key));
uint64_t h = hasher.finish();
return static_cast<uint32_t>(h ^ (h >> 32));
}
// Bounded linear-probing range over a power-of-two open-addressing table.
class BucketProber {
cpp::span<ExprId> table;
size_t start_idx;
constexpr size_t mask() const { return table.size() - 1; }
public:
struct Sentinel {};
struct Iterator {
cpp::span<ExprId> table;
size_t idx;
size_t step;
constexpr size_t mask() const { return table.size() - 1; }
ExprId &operator*() const { return table[idx]; }
Iterator &operator++() {
idx = (idx + 1) & mask();
++step;
return *this;
}
constexpr bool operator!=(Sentinel) const { return step != table.size(); }
};
BucketProber(cpp::span<ExprId> t, uint32_t hash)
: table(t), start_idx(hash & (t.size() - 1)) {
LIBC_ASSERT(!t.empty() && (t.size() & mask()) == 0);
}
Iterator begin() const { return {table, start_idx, 0}; }
Sentinel end() const { return {}; }
};
} // namespace
bool ExprPool::ensure_initialized() {
if (block_count > 0)
return true;
auto table = make_unique<ExprId[]>(INITIAL_HASH_CAPACITY);
if (!table)
return false;
if (!allocate_block())
return false;
hashtable = table.take_unique();
hashtable_capacity = INITIAL_HASH_CAPACITY;
[[maybe_unused]] auto empty_set_id = intern(Expr::make_empty_set());
[[maybe_unused]] auto empty_str_id = intern(Expr::make_empty_str());
LIBC_ASSERT(empty_set_id.has_value() && *empty_set_id == EMPTY_SET_ID);
LIBC_ASSERT(empty_str_id.has_value() && *empty_str_id == EMPTY_STR_ID);
return true;
}
ExprId &ExprPool::find_bucket(cpp::span<ExprId> table, const Expr &e) const {
for (ExprId &slot : BucketProber(table, e.hash)) {
if (slot == INVALID_EXPR_ID)
return slot;
const Expr cand = get(slot);
if (cand.hash == e.hash && cand == e)
return slot;
}
__builtin_unreachable();
}
bool ExprPool::allocate_block() {
if (block_count == block_capacity) {
size_t new_cap = block_capacity == 0 ? INITIAL_BLOCKS_CAPACITY
: block_capacity * GROWTH_FACTOR;
auto new_blocks = make_unique<cpp::unique_ptr<Block>[]>(new_cap);
if (!new_blocks)
return false;
for (size_t i = 0; i < block_count; ++i)
new_blocks[i] = cpp::move(blocks[i]);
blocks = new_blocks.take_unique();
block_capacity = new_cap;
}
auto blk = make_unique<Block>();
if (!blk)
return false;
blocks[block_count] = blk.take_unique();
++block_count;
return true;
}
bool ExprPool::grow_hashtable() {
size_t new_cap = hashtable_capacity * GROWTH_FACTOR;
auto new_table = make_unique<ExprId[]>(new_cap);
if (!new_table)
return false;
cpp::span<ExprId> new_slots(new_table.get(), new_cap);
for (ExprId id : hashtable_slots())
if (id != INVALID_EXPR_ID)
find_bucket(new_slots, get(id)) = id;
hashtable = new_table.take_unique();
hashtable_capacity = new_cap;
return true;
}
ErrorOr<ExprId> ExprPool::intern(Expr e) {
if (!ensure_initialized())
return Error(REG_ESPACE);
// Probe for an existing node with identical content.
e.hash = hash_expr(e);
ExprId *bucket = &find_bucket(hashtable_slots(), e);
if (*bucket != INVALID_EXPR_ID)
return *bucket;
// Admission Control: Check the hard limit on AST nodes.
if (node_count >= MAX_NODE_LIMIT)
return Error(REG_ESPACE);
if (node_count >= max_hashtable_nodes()) {
if (!grow_hashtable())
return Error(REG_ESPACE);
bucket = &find_bucket(hashtable_slots(), e);
}
// Arena Allocation: If no matching node found, allocate a stable slot.
if (node_count == block_count * NODES_PER_BLOCK) {
if (!allocate_block())
return Error(REG_ESPACE);
}
// Node Initialisation: Copy the structural definition into the arena.
++node_count;
ExprId new_id = static_cast<ExprId>(node_count);
slot_at(new_id) = e;
*bucket = new_id;
return new_id;
}
ErrorOr<ExprId> ExprPool::empty_set() {
if (!ensure_initialized())
return Error(REG_ESPACE);
return EMPTY_SET_ID;
}
ErrorOr<ExprId> ExprPool::empty_str() {
if (!ensure_initialized())
return Error(REG_ESPACE);
return EMPTY_STR_ID;
}
ErrorOr<ExprId> ExprPool::make_lit(char c) {
return intern(Expr::make_literal(c));
}
ErrorOr<ExprId> ExprPool::make_anchor(uint8_t mask) {
return intern(Expr::make_anchor(mask));
}
ErrorOr<ExprId> ExprPool::make_byte_set(const ByteSet &bs) {
size_t count = 0;
size_t last_bit = 0;
for (size_t b = 0; b < BYTE_SET_BITS; ++b) {
if (bs.test(b)) {
++count;
last_bit = b;
}
}
if (count == 0)
return empty_set();
if (count == 1)
return make_lit(static_cast<char>(last_bit));
uint32_t bs_id = 0;
for (const ByteSet &existing : active_byte_sets()) {
if (existing == bs)
return intern(Expr::make_byte_set(bs_id));
++bs_id;
}
if (byte_set_count == byte_set_capacity) {
size_t new_cap = byte_set_capacity == 0 ? INITIAL_BYTE_SETS_CAPACITY
: byte_set_capacity * GROWTH_FACTOR;
auto new_sets = make_unique<ByteSet[]>(new_cap);
if (!new_sets)
return Error(REG_ESPACE);
for (size_t i = 0; i < byte_set_count; ++i)
new_sets[i] = byte_sets[i];
byte_sets = new_sets.take_unique();
byte_set_capacity = new_cap;
}
ErrorOr<ExprId> id = intern(Expr::make_byte_set(bs_id));
if (!id.has_value())
return id;
byte_sets[byte_set_count] = bs;
++byte_set_count;
return id;
}
namespace {
// Multiplies a subexpression's repeat expansion factor by an enclosing repeat
// bound, saturating at MAX_REPEAT_EXPANSION + 1 so nested bounds checks never
// overflow uint16_t.
constexpr uint16_t scale_exp(uint16_t base, uint16_t factor) {
if (factor <= 1)
return base;
uint32_t prod = static_cast<uint32_t>(base) * static_cast<uint32_t>(factor);
return static_cast<uint16_t>(
cpp::min<uint32_t>(prod, MAX_REPEAT_EXPANSION + 1));
}
} // namespace
ErrorOr<ExprId> ExprPool::make_star(ExprId body) {
if (body == INVALID_EXPR_ID)
return Error(REG_BADPAT);
// Ø* = ε and ε* = ε
if (body == EMPTY_SET_ID || body == EMPTY_STR_ID)
return empty_str();
// (R*)* = R* and (R{m,n})* = R* iff m <= 1 (since R^1 is in R{m,n} iff
// m <= 1, whereas (a{2,3})* excludes "a").
const Expr be = get(body);
if (be.kind == ExprKind::Star)
return body;
if (be.kind == ExprKind::Repeat && be.rep.min <= 1)
return make_star(be.rep.body);
return intern(
Expr::make_star(body, be.has_anchors, be.has_repeat, be.rep_expansion));
}
ErrorOr<ExprId> ExprPool::make_repeat(ExprId body, uint16_t min, uint16_t max) {
if (body == INVALID_EXPR_ID || min > max || min == REPEAT_INF)
return Error(REG_BADPAT);
// Normalize R{0,0} = ε, ε{m,n} = ε, Ø{m,n}, R{1,1} = R, and
// R{0,REPEAT_INF} = R*.
if (max == 0 || body == EMPTY_STR_ID)
return empty_str();
if (body == EMPTY_SET_ID)
return (min == 0) ? empty_str() : empty_set();
if (min == 1 && max == 1)
return body;
if (min == 0 && max == REPEAT_INF)
return make_star(body);
const Expr be = get(body);
if (be.kind == ExprKind::Star)
return body;
if (be.kind == ExprKind::Repeat && be.rep.min == 1 &&
be.rep.max == REPEAT_INF)
return make_repeat(be.rep.body, min, REPEAT_INF);
uint16_t factor = (max == REPEAT_INF) ? min : max;
return intern(Expr::make_repeat(body, min, max, be.nullable, be.has_anchors,
scale_exp(be.rep_expansion, factor)));
}
ErrorOr<ExprId> ExprPool::make_concat(ExprId l, ExprId r) {
if (l == INVALID_EXPR_ID || r == INVALID_EXPR_ID)
return Error(REG_BADPAT);
// Apply basic algebraic identities for concatenation:
// Ø · R = R · Ø = Ø (Identity: null set)
if (l == EMPTY_SET_ID || r == EMPTY_SET_ID)
return empty_set();
// ε · R = R · ε = R (Identity: empty string)
if (l == EMPTY_STR_ID)
return r;
if (r == EMPTY_STR_ID)
return l;
// (A · B) · C = A · (B · C) (Right-associative canonical form)
const Expr le = get(l);
if (le.kind == ExprKind::Concat) {
ErrorOr<ExprId> tail = make_concat(le.bin.right, r);
if (!tail.has_value())
return tail;
return make_concat(le.bin.left, *tail);
}
const Expr re = get(r);
return intern(Expr::make_concat(
l, r, le.nullable && re.nullable, le.has_anchors || re.has_anchors,
le.has_repeat || re.has_repeat,
cpp::max(le.rep_expansion, re.rep_expansion)));
}
namespace {
// Coalesces R{m1,n1} | R{m2,n2} (and shared-prefix/shared-suffix Concat nodes)
// when their repetition intervals overlap or are adjacent. Returns
// INVALID_EXPR_ID when the pair cannot be coalesced.
ErrorOr<ExprId> coalesce_repeat_pair(ExprId a, ExprId b, ExprPool &pool) {
const Expr ae = pool.get(a);
const Expr be = pool.get(b);
if (!ae.has_repeat && !be.has_repeat)
return INVALID_EXPR_ID;
if (ae.kind == ExprKind::Concat && be.kind == ExprKind::Concat) {
if (ae.bin.right == be.bin.right) {
ErrorOr<ExprId> left =
coalesce_repeat_pair(ae.bin.left, be.bin.left, pool);
if (!left.has_value() || *left == INVALID_EXPR_ID)
return left;
return pool.make_concat(*left, ae.bin.right);
}
if (ae.bin.left == be.bin.left) {
ErrorOr<ExprId> right =
coalesce_repeat_pair(ae.bin.right, be.bin.right, pool);
if (!right.has_value() || *right == INVALID_EXPR_ID)
return right;
return pool.make_concat(ae.bin.left, *right);
}
}
// Handle Concat(X, S) | S and Concat(P, X) | P where R{0,0} normalized to
// EmptyStr on one side.
if (ae.kind == ExprKind::Concat && ae.bin.right == b) {
ErrorOr<ExprId> left =
coalesce_repeat_pair(ae.bin.left, EMPTY_STR_ID, pool);
if (!left.has_value() || *left == INVALID_EXPR_ID)
return left;
return pool.make_concat(*left, b);
}
if (be.kind == ExprKind::Concat && be.bin.right == a) {
ErrorOr<ExprId> left =
coalesce_repeat_pair(EMPTY_STR_ID, be.bin.left, pool);
if (!left.has_value() || *left == INVALID_EXPR_ID)
return left;
return pool.make_concat(*left, a);
}
if (ae.kind == ExprKind::Concat && ae.bin.left == b) {
ErrorOr<ExprId> right =
coalesce_repeat_pair(ae.bin.right, EMPTY_STR_ID, pool);
if (!right.has_value() || *right == INVALID_EXPR_ID)
return right;
return pool.make_concat(b, *right);
}
if (be.kind == ExprKind::Concat && be.bin.left == a) {
ErrorOr<ExprId> right =
coalesce_repeat_pair(EMPTY_STR_ID, be.bin.right, pool);
if (!right.has_value() || *right == INVALID_EXPR_ID)
return right;
return pool.make_concat(a, *right);
}
if (ae.kind != ExprKind::Repeat && be.kind != ExprKind::Repeat)
return INVALID_EXPR_ID;
// When b is Repeat(a, ...) and a is itself a Repeat, pick body = a so
// get_interval(a, ae) matches [1, 1] via `id == body` symmetrically with
// coalesce_repeat_pair(b, a).
ExprId body = (ae.kind == ExprKind::Repeat &&
!(be.kind == ExprKind::Repeat && be.rep.body == a))
? ae.rep.body
: be.rep.body;
struct RepeatInterval {
uint16_t min;
uint16_t max;
};
// Undo make_repeat normalizations: R -> [1,1], EmptyStr -> [0,0], and
// Star(R) -> [0,REPEAT_INF].
auto get_interval = [&](ExprId id,
const Expr &e) -> cpp::optional<RepeatInterval> {
if (e.kind == ExprKind::Repeat && e.rep.body == body)
return RepeatInterval{e.rep.min, e.rep.max};
if (e.kind == ExprKind::Star && e.body == body)
return RepeatInterval{0, REPEAT_INF};
if (id == body)
return RepeatInterval{1, 1};
if (id == EMPTY_STR_ID)
return RepeatInterval{0, 0};
return cpp::nullopt;
};
cpp::optional<RepeatInterval> lhs = get_interval(a, ae);
cpp::optional<RepeatInterval> rhs = get_interval(b, be);
if (!lhs.has_value() || !rhs.has_value())
return INVALID_EXPR_ID;
// Integer intervals [lhs->min, lhs->max] and [rhs->min, rhs->max] coalesce
// iff they overlap or are adjacent (later_min <= earlier_max + 1, e.g.
// [2,3] U [4,5] = [2,5]).
uint16_t later_min = cpp::max(lhs->min, rhs->min);
uint16_t earlier_max = cpp::min(lhs->max, rhs->max);
if (earlier_max != REPEAT_INF && later_min > earlier_max + 1)
return INVALID_EXPR_ID;
return pool.make_repeat(body, cpp::min(lhs->min, rhs->min),
cpp::max(lhs->max, rhs->max));
}
// Attempts to coalesce a single non-Alt branch `item` with any branch in
// `spine`, returning INVALID_EXPR_ID if no branch coalesces.
ErrorOr<ExprId> coalesce_item_into_spine(ExprId item, ExprId spine,
ExprPool &pool) {
const Expr item_e = pool.get(item);
const Expr spine_e = pool.get(spine);
if (!item_e.has_repeat && !spine_e.has_repeat)
return INVALID_EXPR_ID;
if (spine_e.kind != ExprKind::Alt)
return coalesce_repeat_pair(item, spine, pool);
ErrorOr<ExprId> head_c = coalesce_repeat_pair(item, spine_e.bin.left, pool);
if (!head_c.has_value())
return head_c;
if (*head_c != INVALID_EXPR_ID)
return pool.make_alt(*head_c, spine_e.bin.right);
ErrorOr<ExprId> tail_c =
coalesce_item_into_spine(item, spine_e.bin.right, pool);
if (!tail_c.has_value() || *tail_c == INVALID_EXPR_ID)
return tail_c;
return pool.make_alt(spine_e.bin.left, *tail_c);
}
} // namespace
ErrorOr<ExprId> ExprPool::make_alt(ExprId l, ExprId r) {
if (l == INVALID_EXPR_ID || r == INVALID_EXPR_ID)
return Error(REG_BADPAT);
// Apply basic algebraic identities for alternation:
// Ø | R = R | Ø = R (Identity: null set)
if (l == EMPTY_SET_ID)
return r;
if (r == EMPTY_SET_ID)
return l;
// R | R = R (Idempotency)
if (l == r)
return l;
const Expr le = get(l);
const Expr re = get(r);
if (le.kind != ExprKind::Alt && re.kind != ExprKind::Alt) {
ErrorOr<ExprId> coalesced = coalesce_repeat_pair(l, r, *this);
if (!coalesced.has_value() || *coalesced != INVALID_EXPR_ID)
return coalesced;
if (l > r)
cpp::swap(l, r);
return intern(Expr::make_alt(l, r, le.nullable || re.nullable,
le.has_anchors || re.has_anchors,
le.has_repeat || re.has_repeat,
cpp::max(le.rep_expansion, re.rep_expansion)));
}
if (le.has_repeat || re.has_repeat) {
if (le.kind != ExprKind::Alt) {
ErrorOr<ExprId> c = coalesce_item_into_spine(l, r, *this);
if (!c.has_value() || *c != INVALID_EXPR_ID)
return c;
} else if (re.kind != ExprKind::Alt) {
ErrorOr<ExprId> c = coalesce_item_into_spine(r, l, *this);
if (!c.has_value() || *c != INVALID_EXPR_ID)
return c;
}
}
// Merge two right-associated sorted Alt spines in ascending ExprId order so
// multi-way alternations canonicalize to a single deduplicated tree and
// derivative state spaces under '*' and '{m,n}' stay finite.
ExprId hl = (le.kind == ExprKind::Alt) ? le.bin.left : l;
ExprId tl = (le.kind == ExprKind::Alt) ? le.bin.right : EMPTY_SET_ID;
ExprId hr = (re.kind == ExprKind::Alt) ? re.bin.left : r;
ExprId tr = (re.kind == ExprKind::Alt) ? re.bin.right : EMPTY_SET_ID;
ExprId head = hl;
ErrorOr<ExprId> rest = EMPTY_SET_ID;
if (hl == hr) {
rest = make_alt(tl, tr);
} else if (hl < hr) {
rest = make_alt(tl, r);
} else {
head = hr;
rest = make_alt(l, tr);
}
if (!rest.has_value())
return rest;
// When merging two Alt spines, `head` (or a newly coalesced interval in
// `*rest`) may now coalesce across the two spines or out-of-order ExprIds.
const Expr he = get(head);
const Expr re_rest = get(*rest);
if (le.kind == ExprKind::Alt && re.kind == ExprKind::Alt &&
(he.has_repeat || re_rest.has_repeat)) {
ErrorOr<ExprId> c = coalesce_item_into_spine(head, *rest, *this);
if (!c.has_value() || *c != INVALID_EXPR_ID)
return c;
}
ExprId rest_head = (re_rest.kind == ExprKind::Alt) ? re_rest.bin.left : *rest;
if (head >= rest_head)
return make_alt(head, *rest);
return intern(
Expr::make_alt(head, *rest, he.nullable || re_rest.nullable,
he.has_anchors || re_rest.has_anchors,
he.has_repeat || re_rest.has_repeat,
cpp::max(he.rep_expansion, re_rest.rep_expansion)));
}
} // namespace regex
} // namespace LIBC_NAMESPACE_DECL