syntaxmate 0.1.3

use std::collections::VecDeque;

use super::ast::{Ast, CharClass, ClassAtom, LookKind, ParsedRegex};

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum RequiredLiterals {
    None,
    One(String),
    Any(Vec<String>),
}

impl RequiredLiterals {
    fn is_empty(&self) -> bool {
        matches!(self, Self::None)
    }
}

/// Fast rejection prefilter. False positives are allowed; false negatives are not.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Prefilter {
    None,
    Byte(u8),
    ByteSet {
        bytes: Vec<u8>,
        bitmap: [u64; 4],
    },
    Literal(String),
    Any {
        literals: Vec<String>,
        ascii_case_insensitive: bool,
        mixed_width_fold_mask: u8,
        finder: Option<MultiLiteralFinder>,
    },
}

impl Prefilter {
    pub fn from_regex(parsed: &ParsedRegex) -> Self {
        parsed.prefilter().clone()
    }

    pub fn from_pattern(ast: &Ast) -> Self {
        Self::from_required(required_literals(ast), false)
    }

    pub(crate) fn from_required(required: RequiredLiterals, ascii_case_insensitive: bool) -> Self {
        if ascii_case_insensitive {
            let literals = match required {
                RequiredLiterals::None => return Self::None,
                RequiredLiterals::One(literal) => vec![literal],
                RequiredLiterals::Any(literals) => literals,
            };
            if literals.is_empty()
                || literals
                    .iter()
                    .any(|literal| literal.is_empty() || !literal.is_ascii())
            {
                return Self::None;
            }
            let mixed_width_fold_mask = literals.iter().fold(0u8, |mask, literal| {
                literal.bytes().fold(mask, |mask, byte| {
                    mask | u8::from(byte.eq_ignore_ascii_case(&b's'))
                        | (u8::from(byte.eq_ignore_ascii_case(&b'k')) << 1)
                })
            });
            return Self::Any {
                literals,
                ascii_case_insensitive: true,
                mixed_width_fold_mask,
                finder: None,
            };
        }
        match required {
            RequiredLiterals::None => Self::None,
            RequiredLiterals::One(literal) => prefilter_one(literal),
            RequiredLiterals::Any(literals) if literals.is_empty() => Self::None,
            RequiredLiterals::Any(literals) if literals.len() == 1 => {
                prefilter_one(literals.into_iter().next().expect("one literal"))
            }
            RequiredLiterals::Any(literals)
                if literals
                    .iter()
                    .all(|literal| literal.len() == 1 && literal.is_ascii()) =>
            {
                let bytes = literals
                    .into_iter()
                    .map(|literal| literal.as_bytes()[0])
                    .collect::<Vec<_>>();
                let mut bitmap = [0u64; 4];
                for &byte in &bytes {
                    bitmap[byte as usize >> 6] |= 1u64 << (byte & 63);
                }
                Self::ByteSet { bytes, bitmap }
            }
            RequiredLiterals::Any(literals) => Self::Any {
                finder: MultiLiteralFinder::for_literals(&literals),
                literals,
                ascii_case_insensitive: false,
                mixed_width_fold_mask: 0,
            },
        }
    }

    pub fn may_match(&self, haystack: &str, from: usize) -> bool {
        if !haystack.is_char_boundary(from) {
            return false;
        }
        let Some(slice) = haystack.get(from..) else {
            return false;
        };
        match self {
            Self::None => true,
            Self::Byte(byte) => find_byte(slice.as_bytes(), *byte).is_some(),
            Self::ByteSet { bytes, bitmap } => {
                find_byte_set(slice.as_bytes(), bytes, bitmap).is_some()
            }
            Self::Literal(literal) => find_literal(slice, literal).is_some(),
            Self::Any {
                literals,
                ascii_case_insensitive: false,
                finder,
                ..
            } => finder.as_ref().map_or_else(
                || {
                    literals
                        .iter()
                        .any(|literal| find_literal(slice, literal).is_some())
                },
                |finder| finder.find(slice.as_bytes()).is_some(),
            ),
            Self::Any {
                literals,
                ascii_case_insensitive: true,
                mixed_width_fold_mask,
                ..
            } => {
                literals
                    .iter()
                    .any(|literal| contains_ignore_ascii_case(slice, literal))
                    || first_ascii_case_fold_candidate(slice, *mixed_width_fold_mask).is_some()
            }
        }
    }

    /// Position of the first viability point at or after `from`, or `None`
    /// when the required literal cannot occur again on this line. `Self::None`
    /// never filters, so it reports `from` itself.
    pub fn next_occurrence(&self, haystack: &str, from: usize) -> Option<usize> {
        if !haystack.is_char_boundary(from) {
            return None;
        }
        let slice = haystack.get(from..)?;
        match self {
            Self::None => Some(from),
            Self::Byte(byte) => find_byte(slice.as_bytes(), *byte).map(|pos| from + pos),
            Self::ByteSet { bytes, bitmap } => {
                find_byte_set(slice.as_bytes(), bytes, bitmap).map(|pos| from + pos)
            }
            Self::Literal(literal) => find_literal(slice, literal).map(|pos| from + pos),
            Self::Any {
                literals,
                ascii_case_insensitive: false,
                finder,
                ..
            } => finder.as_ref().map_or_else(
                || {
                    literals
                        .iter()
                        .filter_map(|literal| find_literal(slice, literal))
                        .min()
                        .map(|pos| from + pos)
                },
                |finder| finder.find(slice.as_bytes()).map(|pos| from + pos),
            ),
            Self::Any {
                literals,
                ascii_case_insensitive: true,
                mixed_width_fold_mask,
                ..
            } => literals
                .iter()
                .filter_map(|literal| find_ignore_ascii_case(slice, literal))
                .chain(first_ascii_case_fold_candidate(
                    slice,
                    *mixed_width_fold_mask,
                ))
                .min()
                .map(|pos| from + pos),
        }
    }

    pub fn is_enabled(&self) -> bool {
        !matches!(self, Self::None)
    }

    pub fn literals(&self) -> &[String] {
        match self {
            Self::Any { literals, .. } => literals,
            Self::None | Self::Byte(_) | Self::ByteSet { .. } | Self::Literal(_) => &[],
        }
    }
}

/// Compact failure-linked trie for large case-sensitive required-literal
/// sets. Small sets retain the standard library's highly tuned two-way
/// search; the trie is reserved for cases where rebuilding and running one
/// searcher per alternative dominates (notably C/C++ keyword inventories).
#[derive(Debug, Clone, PartialEq, Eq)]
#[doc(hidden)]
pub struct MultiLiteralFinder {
    nodes: Vec<FinderNode>,
    /// Every input byte probes the root at least once. A dense root table
    /// avoids a linear scan over the large first-byte fanout while keeping
    /// deeper, usually tiny transition sets compact.
    root_edges: Box<[u32; 256]>,
    max_literal_len: usize,
}

#[derive(Debug, Clone, Default, PartialEq, Eq)]
struct FinderNode {
    edges: Vec<(u8, u32)>,
    failure: u32,
    /// Longest literal ending in this state or one of its failure states.
    /// The longest output has the earliest start for a fixed end position.
    output_len: usize,
}

impl MultiLiteralFinder {
    fn for_literals(literals: &[String]) -> Option<Self> {
        let total_bytes = literals.iter().map(String::len).sum::<usize>();
        (literals.len() >= multi_literal_min_literals()
            && total_bytes >= multi_literal_min_total_bytes())
        .then(|| Self::new(literals))
    }

    fn new(literals: &[String]) -> Self {
        let mut nodes = vec![FinderNode::default()];
        let mut max_literal_len = 0usize;
        for literal in literals {
            debug_assert!(!literal.is_empty());
            max_literal_len = max_literal_len.max(literal.len());
            let mut state = 0usize;
            for byte in literal.bytes() {
                let next = edge(&nodes[state], byte);
                state = if let Some(next) = next {
                    next as usize
                } else {
                    let next = u32::try_from(nodes.len()).expect("prefilter trie exceeds u32");
                    nodes.push(FinderNode::default());
                    nodes[state].edges.push((byte, next));
                    next as usize
                };
            }
            nodes[state].output_len = nodes[state].output_len.max(literal.len());
        }

        let mut queue = VecDeque::new();
        let root_children = nodes[0]
            .edges
            .iter()
            .map(|(_, child)| *child)
            .collect::<Vec<_>>();
        for child in root_children {
            queue.push_back(child);
        }
        while let Some(state) = queue.pop_front() {
            let transitions = nodes[state as usize].edges.clone();
            for (byte, child) in transitions {
                let mut failure = nodes[state as usize].failure;
                while failure != 0 && edge(&nodes[failure as usize], byte).is_none() {
                    failure = nodes[failure as usize].failure;
                }
                if let Some(next) = edge(&nodes[failure as usize], byte)
                    && next != child
                {
                    failure = next;
                }
                nodes[child as usize].failure = failure;
                nodes[child as usize].output_len = nodes[child as usize]
                    .output_len
                    .max(nodes[failure as usize].output_len);
                queue.push_back(child);
            }
        }
        let mut root_edges = Box::new([u32::MAX; 256]);
        for (byte, child) in &nodes[0].edges {
            root_edges[*byte as usize] = *child;
        }
        Self {
            nodes,
            root_edges,
            max_literal_len,
        }
    }

    /// Returns the leftmost literal start. Scanning may stop once the maximum
    /// literal length proves that no future match can begin earlier.
    fn find(&self, haystack: &[u8]) -> Option<usize> {
        let mut state = 0u32;
        let mut best = None;
        for (index, byte) in haystack.iter().copied().enumerate() {
            state = self.step(state, byte);
            let output_len = self.nodes[state as usize].output_len;
            if output_len != 0 {
                let start = index + 1 - output_len;
                best = Some(best.map_or(start, |current: usize| current.min(start)));
            }
            if let Some(best) = best
                && index.saturating_add(2) >= best.saturating_add(self.max_literal_len)
            {
                break;
            }
        }
        best
    }

    fn step(&self, mut state: u32, byte: u8) -> u32 {
        loop {
            if state == 0 {
                let next = self.root_edges[byte as usize];
                return if next == u32::MAX { 0 } else { next };
            }
            if let Some(next) = edge(&self.nodes[state as usize], byte) {
                return next;
            }
            state = self.nodes[state as usize].failure;
        }
    }
}

fn multi_literal_min_literals() -> usize {
    4
}

fn multi_literal_min_total_bytes() -> usize {
    32
}

fn edge(node: &FinderNode, byte: u8) -> Option<u32> {
    let edges = &node.edges;
    match edges.len() {
        0 => None,
        1 => (edges[0].0 == byte).then_some(edges[0].1),
        _ => edges
            .iter()
            .find_map(|(candidate, next)| (*candidate == byte).then_some(*next)),
    }
}

fn prefilter_one(literal: String) -> Prefilter {
    if literal.len() == 1 && literal.is_ascii() {
        Prefilter::Byte(literal.as_bytes()[0])
    } else {
        Prefilter::Literal(literal)
    }
}

/// Native single-byte search (memchr substitute).
fn find_byte(haystack: &[u8], needle: u8) -> Option<usize> {
    memchr::memchr(needle, haystack)
}

#[inline]
pub(crate) fn find_byte_set(haystack: &[u8], bytes: &[u8], bitmap: &[u64; 4]) -> Option<usize> {
    match bytes {
        [] => None,
        [byte] => memchr::memchr(*byte, haystack),
        [a, b] => memchr::memchr2(*a, *b, haystack),
        [a, b, c] => memchr::memchr3(*a, *b, *c, haystack),
        _ => find_byte_set_bitmap(haystack, bitmap),
    }
}

#[inline]
fn byte_in_set(bitmap: &[u64; 4], byte: u8) -> bool {
    bitmap[byte as usize >> 6] & (1u64 << (byte & 63)) != 0
}

pub(crate) fn find_byte_set_bitmap(haystack: &[u8], bitmap: &[u64; 4]) -> Option<usize> {
    let mut index = 0;
    let len = haystack.len();
    while index + 8 <= len {
        if byte_in_set(bitmap, haystack[index]) {
            return Some(index);
        }
        if byte_in_set(bitmap, haystack[index + 1]) {
            return Some(index + 1);
        }
        if byte_in_set(bitmap, haystack[index + 2]) {
            return Some(index + 2);
        }
        if byte_in_set(bitmap, haystack[index + 3]) {
            return Some(index + 3);
        }
        if byte_in_set(bitmap, haystack[index + 4]) {
            return Some(index + 4);
        }
        if byte_in_set(bitmap, haystack[index + 5]) {
            return Some(index + 5);
        }
        if byte_in_set(bitmap, haystack[index + 6]) {
            return Some(index + 6);
        }
        if byte_in_set(bitmap, haystack[index + 7]) {
            return Some(index + 7);
        }
        index += 8;
    }
    while index < len {
        if byte_in_set(bitmap, haystack[index]) {
            return Some(index);
        }
        index += 1;
    }
    None
}

fn find_literal(haystack: &str, needle: &str) -> Option<usize> {
    memchr::memmem::find(haystack.as_bytes(), needle.as_bytes())
}

fn contains_ignore_ascii_case(haystack: &str, needle: &str) -> bool {
    find_ignore_ascii_case(haystack, needle).is_some()
}

fn first_ascii_case_fold_candidate(haystack: &str, mask: u8) -> Option<usize> {
    if mask == 0 {
        return None;
    }
    let bytes = haystack.as_bytes();
    let mut from = 0usize;
    loop {
        let relative = match mask {
            1 => memchr::memchr(0xc5, bytes.get(from..)?),
            2 => memchr::memchr(0xe2, bytes.get(from..)?),
            _ => memchr::memchr2(0xc5, 0xe2, bytes.get(from..)?),
        }?;
        let offset = from + relative;
        if (mask & 1 != 0 && matches!(bytes.get(offset..), Some([0xc5, 0xbf, ..])))
            || (mask & 2 != 0 && matches!(bytes.get(offset..), Some([0xe2, 0x84, 0xaa, ..])))
        {
            return Some(offset);
        }
        from = offset + 1;
    }
}

fn find_ignore_ascii_case(haystack: &str, needle: &str) -> Option<usize> {
    if needle.is_empty() {
        return Some(0);
    }
    let hay = haystack.as_bytes();
    let needle = needle.as_bytes();
    if needle.len() > hay.len() {
        return None;
    }
    let first = needle[0];
    let lower = first.to_ascii_lowercase();
    let upper = first.to_ascii_uppercase();
    let mut from = 0usize;
    loop {
        let rest = hay.get(from..)?;
        let relative = if lower == upper {
            memchr::memchr(first, rest)?
        } else {
            memchr::memchr2(lower, upper, rest)?
        };
        let pos = from + relative;
        if hay
            .get(pos..pos + needle.len())
            .is_some_and(|window| window.eq_ignore_ascii_case(needle))
        {
            return Some(pos);
        }
        from = pos + 1;
    }
}

/// Scan-local memo of required-literal occurrences, keyed by compiled-pattern
/// slot. Anchored pattern-set attempts ask the same rejection question at
/// monotonically increasing positions; remembering the next occurrence turns
/// the per-position tail search into an O(1) check. Process-global matcher IDs
/// above the dense prefix are folded into a bounded direct-mapped overflow
/// table and retained in each entry, so collisions become safe cache misses
/// instead of growing tokenizer memory. Rejection-only: a stale or missing
/// entry falls back to a fresh search, so false negatives are impossible by
/// construction.
const MAX_PREFILTER_CURSOR_SLOTS: usize = 1024;

#[derive(Debug, Clone, Default)]
pub(crate) struct PrefilterCursors {
    line_ptr: usize,
    line_len: usize,
    generation: u64,
    slots: Vec<CursorSlot>,
    overflow_slots: Vec<OverflowCursorSlot>,
}

#[derive(Debug, Clone, Copy, Default)]
struct CursorSlot {
    generation: u64,
    searched_from: usize,
    next_occurrence: Option<usize>,
}

#[derive(Debug, Clone, Copy, Default)]
struct OverflowCursorSlot {
    matcher_slot: u32,
    cursor: CursorSlot,
}

impl PrefilterCursors {
    pub(crate) fn begin_line(&mut self, line: &str) {
        self.line_ptr = line.as_ptr() as usize;
        self.line_len = line.len();
        self.generation = self.generation.wrapping_add(1).max(1);
    }

    pub(crate) fn may_match(
        &mut self,
        slot: u32,
        prefilter: &Prefilter,
        line: &str,
        start: usize,
    ) -> bool {
        if !prefilter.is_enabled() {
            return true;
        }
        self.next_occurrence(slot, prefilter, line, start).is_some()
    }

    pub(crate) fn next_occurrence(
        &mut self,
        slot: u32,
        prefilter: &Prefilter,
        line: &str,
        start: usize,
    ) -> Option<usize> {
        if !prefilter.is_enabled() {
            return Some(start);
        }
        if slot == u32::MAX {
            return prefilter.next_occurrence(line, start);
        }
        let (line_ptr, line_len) = (line.as_ptr() as usize, line.len());
        if self.line_ptr != line_ptr || self.line_len != line_len {
            self.line_ptr = line_ptr;
            self.line_len = line_len;
            self.generation = self.generation.wrapping_add(1);
        }
        // Generation zero marks never-written slots; never treat it as bound.
        if self.generation == 0 {
            self.generation = 1;
        }
        let generation = self.generation;
        if (slot as usize) < MAX_PREFILTER_CURSOR_SLOTS {
            let slot = slot as usize;
            if slot >= self.slots.len() {
                self.slots.resize(slot + 1, CursorSlot::default());
            }
            return cached_next_occurrence(
                &mut self.slots[slot],
                true,
                generation,
                prefilter,
                line,
                start,
            );
        }

        let overflow_index = slot as usize % MAX_PREFILTER_CURSOR_SLOTS;
        if overflow_index >= self.overflow_slots.len() {
            self.overflow_slots
                .resize(overflow_index + 1, OverflowCursorSlot::default());
        }
        let entry = &mut self.overflow_slots[overflow_index];
        let same_matcher = entry.matcher_slot == slot;
        entry.matcher_slot = slot;
        cached_next_occurrence(
            &mut entry.cursor,
            same_matcher,
            generation,
            prefilter,
            line,
            start,
        )
    }
}

#[inline]
fn cached_next_occurrence(
    entry: &mut CursorSlot,
    same_matcher: bool,
    generation: u64,
    prefilter: &Prefilter,
    line: &str,
    start: usize,
) -> Option<usize> {
    let stale = !same_matcher || entry.generation != generation || entry.searched_from > start;
    if !stale {
        match entry.next_occurrence {
            None => return None,
            Some(occurrence) if occurrence >= start => return Some(occurrence),
            Some(_) => {}
        }
    }
    let next = prefilter.next_occurrence(line, start);
    *entry = CursorSlot {
        generation,
        searched_from: start,
        next_occurrence: next,
    };
    next
}

pub fn required_literal(pattern: &str) -> Option<String> {
    let parsed = super::ast::parse(pattern);
    match required_literals(&parsed.ast) {
        RequiredLiterals::One(literal) => Some(literal),
        RequiredLiterals::Any(literals) => literals.into_iter().max_by_key(|literal| literal.len()),
        RequiredLiterals::None => literal_prefix(pattern),
    }
}

pub fn required_literals(ast: &Ast) -> RequiredLiterals {
    if let Some(literal) = exact_literal(ast).filter(|literal| !literal.is_empty()) {
        return RequiredLiterals::One(literal);
    }
    match ast {
        Ast::Literal(literal) if !literal.is_empty() => RequiredLiterals::One(literal.clone()),
        Ast::Concat(nodes) => sequence_required_literals(nodes),
        Ast::Alternation(branches) => alternation_required_literals(branches),
        Ast::Group { child, .. } | Ast::Flags { child, .. } => required_literals(child),
        Ast::Look {
            kind: LookKind::Ahead,
            child,
        } => required_literals(child),
        Ast::Repeat { node, min, .. } if *min > 0 => required_literals(node),
        Ast::Class(class) => class_required_literals(class),
        _ => RequiredLiterals::None,
    }
}

fn sequence_required_literals(nodes: &[Ast]) -> RequiredLiterals {
    let mut best = RequiredLiterals::None;
    let mut run = String::new();
    for node in nodes {
        if let Some(literal) = exact_literal(node) {
            run.push_str(&literal);
            continue;
        }
        if !run.is_empty() {
            best = choose_more_selective(best, RequiredLiterals::One(std::mem::take(&mut run)));
        }
        let candidate = required_literals(node);
        best = choose_more_selective(best, candidate);
    }
    if !run.is_empty() {
        best = choose_more_selective(best, RequiredLiterals::One(run));
    }
    best
}

fn exact_literal(ast: &Ast) -> Option<String> {
    match ast {
        Ast::Empty => Some(String::new()),
        Ast::Literal(literal) => Some(literal.clone()),
        Ast::Concat(nodes) => {
            let mut out = String::new();
            for node in nodes {
                out.push_str(&exact_literal(node)?);
            }
            Some(out)
        }
        Ast::Group { child, .. } | Ast::Flags { child, .. } => exact_literal(child),
        _ => None,
    }
}

fn alternation_required_literals(branches: &[Ast]) -> RequiredLiterals {
    let mut literals = Vec::new();
    for branch in branches {
        match required_literals(branch) {
            RequiredLiterals::One(literal) => literals.push(literal),
            RequiredLiterals::Any(mut branch_literals) => literals.append(&mut branch_literals),
            RequiredLiterals::None => return RequiredLiterals::None,
        }
    }
    literals.sort();
    literals.dedup();
    RequiredLiterals::Any(literals)
}

fn choose_more_selective(left: RequiredLiterals, right: RequiredLiterals) -> RequiredLiterals {
    if left.is_empty() {
        return right;
    }
    if right.is_empty() {
        return left;
    }
    let left_len = max_literal_len(&left);
    let right_len = max_literal_len(&right);
    if right_len > left_len {
        return right;
    }
    if right_len < left_len {
        return left;
    }
    if literal_cardinality(&right) < literal_cardinality(&left) {
        right
    } else {
        left
    }
}

fn max_literal_len(literals: &RequiredLiterals) -> usize {
    match literals {
        RequiredLiterals::None => 0,
        RequiredLiterals::One(literal) => literal.len(),
        RequiredLiterals::Any(literals) => literals.iter().map(String::len).max().unwrap_or(0),
    }
}

fn literal_cardinality(literals: &RequiredLiterals) -> usize {
    match literals {
        RequiredLiterals::None => usize::MAX,
        RequiredLiterals::One(_) => 1,
        RequiredLiterals::Any(literals) => literals.len(),
    }
}

fn class_required_literals(class: &CharClass) -> RequiredLiterals {
    if class.negated || class.atoms.is_empty() {
        return RequiredLiterals::None;
    }
    // Every intersection result is a subset of the first union. Its finite
    // literals therefore remain a safe (possibly broader) prefilter set.
    let mut literals = Vec::new();
    for atom in &class.atoms {
        match atom {
            ClassAtom::Char(ch) => literals.push(ch.to_string()),
            ClassAtom::Range(..)
            | ClassAtom::Perl(_)
            | ClassAtom::Posix { .. }
            | ClassAtom::Unicode { .. }
            | ClassAtom::Nested(_) => return RequiredLiterals::None,
        }
    }
    literals.sort();
    literals.dedup();
    match literals.len() {
        0 => RequiredLiterals::None,
        1 => RequiredLiterals::One(literals.remove(0)),
        _ => RequiredLiterals::Any(literals),
    }
}

fn literal_prefix(pattern: &str) -> Option<String> {
    let mut literal = String::new();
    let mut escaped = false;
    for ch in pattern.chars() {
        if escaped {
            if ch.is_ascii_alphanumeric() {
                return None;
            }
            literal.push(ch);
            escaped = false;
            continue;
        }
        match ch {
            '\\' => escaped = true,
            '(' | ')' | '[' | ']' | '{' | '}' | '|' | '?' | '*' | '+' | '.' | '^' | '$' => break,
            ch => literal.push(ch),
        }
    }
    (!literal.is_empty()).then_some(literal)
}

/// Native multi-literal leftmost search used by pattern sets.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LiteralSet {
    literals: Vec<String>,
    trie: Vec<LiteralTrieNode>,
    empty_pattern: Option<usize>,
}

#[derive(Debug, Clone, Default, PartialEq, Eq)]
struct LiteralTrieNode {
    edges: Vec<(u8, usize)>,
    terminal_patterns: Vec<usize>,
}

impl LiteralSet {
    pub(crate) fn retained_heap_bytes(&self) -> usize {
        let mut bytes = self
            .literals
            .capacity()
            .saturating_mul(std::mem::size_of::<String>())
            .saturating_add(
                self.trie
                    .capacity()
                    .saturating_mul(std::mem::size_of::<LiteralTrieNode>()),
            );
        for literal in &self.literals {
            bytes = bytes.saturating_add(literal.capacity());
        }
        for node in &self.trie {
            bytes = bytes
                .saturating_add(
                    node.edges
                        .capacity()
                        .saturating_mul(std::mem::size_of::<(u8, usize)>()),
                )
                .saturating_add(
                    node.terminal_patterns
                        .capacity()
                        .saturating_mul(std::mem::size_of::<usize>()),
                );
        }
        bytes
    }

    pub fn new(literals: Vec<String>) -> Self {
        let mut trie = vec![LiteralTrieNode::default()];
        let mut empty_pattern = None;
        for (pattern, literal) in literals.iter().enumerate() {
            if literal.is_empty() {
                empty_pattern =
                    Some(empty_pattern.map_or(pattern, |best: usize| best.min(pattern)));
                continue;
            }
            let mut node = 0usize;
            for byte in literal.bytes() {
                let next = trie[node]
                    .edges
                    .iter()
                    .find_map(|(edge, next)| (*edge == byte).then_some(*next));
                node = if let Some(next) = next {
                    next
                } else {
                    let next = trie.len();
                    trie.push(LiteralTrieNode::default());
                    trie[node].edges.push((byte, next));
                    next
                };
            }
            trie[node].terminal_patterns.push(pattern);
        }
        Self {
            literals,
            trie,
            empty_pattern,
        }
    }

    pub fn literals(&self) -> &[String] {
        &self.literals
    }

    /// Leftmost match; on equal start offset the lowest pattern index wins.
    pub fn find(&self, haystack: &str, from: usize) -> Option<(usize, usize, usize)> {
        if !haystack.is_char_boundary(from) {
            return None;
        }
        for start in haystack[from..]
            .char_indices()
            .map(|(offset, _)| from + offset)
            .chain(std::iter::once(haystack.len()))
        {
            let mut best = self.empty_pattern.map(|pattern| (pattern, start));
            let mut node = 0usize;
            let mut end = start;
            while let Some(byte) = haystack.as_bytes().get(end) {
                let Some(next) = self.trie[node]
                    .edges
                    .iter()
                    .find_map(|(edge, next)| (*edge == *byte).then_some(*next))
                else {
                    break;
                };
                node = next;
                end += 1;
                for pattern in &self.trie[node].terminal_patterns {
                    if best.is_none_or(|(best, _)| *pattern < best) {
                        best = Some((*pattern, end));
                    }
                }
            }
            if let Some((pattern, end)) = best {
                return Some((pattern, start, end));
            }
        }
        None
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::engine::regex::ast::parse;

    #[test]
    fn extracts_safe_literal_prefix() {
        assert_eq!(required_literal("foo|bar"), Some("foo".to_owned()));
        assert_eq!(required_literal(r"\w+"), None);
    }

    #[test]
    fn extracts_alternation_literals() {
        let parsed = parse("foo|bar");
        assert_eq!(
            required_literals(&parsed.ast),
            RequiredLiterals::Any(vec!["bar".to_owned(), "foo".to_owned()])
        );
    }

    #[test]
    fn extracts_positive_lookahead_literals() {
        let parsed = parse(r"(?<=return)\s*(?=(<)\s*([A-Za-z]+))");
        assert_eq!(
            required_literals(&parsed.ast),
            RequiredLiterals::One("<".to_owned())
        );

        let parsed = parse(r"(?<!\\)(?=;)");
        assert_eq!(
            required_literals(&parsed.ast),
            RequiredLiterals::One(";".to_owned())
        );

        let parsed = parse(r"(?<=return)");
        assert_eq!(required_literals(&parsed.ast), RequiredLiterals::None);
    }

    #[test]
    fn extracts_positive_class_literals() {
        let parsed = parse(r"(?=[;)])(?<!\\)");
        assert_eq!(
            required_literals(&parsed.ast),
            RequiredLiterals::Any(vec![")".to_owned(), ";".to_owned()])
        );

        let parsed = parse(r"(?=[A-Z])");
        assert_eq!(required_literals(&parsed.ast), RequiredLiterals::None);
    }

    #[test]
    fn enables_ascii_literal_prefilter_for_case_insensitive_patterns() {
        let parsed = parse(r"(?i)foo");
        let prefilter = Prefilter::from_regex(&parsed);
        assert!(prefilter.is_enabled());
        assert!(prefilter.may_match("xxFOO", 0));
        assert!(!prefilter.may_match("xxbar", 0));

        let parsed = parse(r"(?i)k");
        let prefilter = Prefilter::from_regex(&parsed);
        assert!(prefilter.may_match("K", 0));
        assert_eq!(prefilter.next_occurrence("xxK", 0), Some(2));

        let parsed = parse(r"(?i)café");
        assert!(!Prefilter::from_regex(&parsed).is_enabled());

        let parsed = parse(r"foo");
        assert!(Prefilter::from_regex(&parsed).is_enabled());
    }

    #[test]
    fn prefilter_uses_byte_scan_for_single_byte() {
        let parsed = parse("x+");
        let prefilter = Prefilter::from_pattern(&parsed.ast);
        assert!(prefilter.may_match("abcx", 0));
        assert!(!prefilter.may_match("abc", 0));
    }

    #[test]
    fn byte_set_prefilter_finds_first_of_many_bytes() {
        let parsed = parse("a|e|i|o|u");
        let prefilter = Prefilter::from_pattern(&parsed.ast);
        assert_eq!(prefilter.next_occurrence("xxxyz o", 0), Some(6));
        assert_eq!(prefilter.next_occurrence("xxxyz o", 6), Some(6));
        assert_eq!(prefilter.next_occurrence("xxxyz o", 7), None);
        assert!(!prefilter.may_match("bcdfg", 0));
    }

    #[test]
    fn ignore_ascii_case_search_finds_first_folded_needle() {
        assert_eq!(find_ignore_ascii_case("xxSELECT", "select"), Some(2));
        assert_eq!(find_ignore_ascii_case("Select", "SELECT"), Some(0));
        assert_eq!(find_ignore_ascii_case("nope", "SELECT"), None);
        assert_eq!(find_ignore_ascii_case("ssssSELECT", "select"), Some(4));
    }

    #[test]
    fn multi_literal_finder_preserves_leftmost_and_failure_outputs() {
        let literals = [
            "bc", "abcd", "suffix", "hers", "his", "she", "he", "keyword",
        ]
        .into_iter()
        .map(str::to_owned)
        .collect::<Vec<_>>();
        let finder = MultiLiteralFinder::new(&literals);
        // `bc` ends before `abcd`, but the longer literal starts earlier.
        assert_eq!(finder.find(b"zabcd"), Some(1));
        // `he` is reached through the failure link after scanning `she`.
        assert_eq!(finder.find(b"ushers"), Some(1));
        assert_eq!(finder.find(b"nothing"), None);
    }

    #[test]
    fn high_process_global_slots_use_a_bounded_collision_safe_memo() {
        let keyword = parse("keyword");
        let keyword = Prefilter::from_pattern(&keyword.ast);
        let missing = parse("missing");
        let missing = Prefilter::from_pattern(&missing.ast);
        let mut cursors = PrefilterCursors::default();
        let line = "keyword";
        let high_slot = 1_000_000;
        let colliding_slot = high_slot + MAX_PREFILTER_CURSOR_SLOTS as u32;
        cursors.begin_line(line);

        assert!(cursors.may_match(high_slot, &keyword, line, 0));
        assert!(!cursors.may_match(colliding_slot, &missing, line, 0));
        assert!(cursors.may_match(high_slot, &keyword, line, 0));
        assert!(cursors.slots.is_empty());
        assert!(!cursors.overflow_slots.is_empty());
        assert!(cursors.overflow_slots.len() <= MAX_PREFILTER_CURSOR_SLOTS);
    }

    #[test]
    fn explicit_line_boundary_invalidates_reused_string_storage() {
        let parsed = parse("keyword");
        let prefilter = Prefilter::from_pattern(&parsed.ast);
        let mut cursors = PrefilterCursors::default();
        let mut line = String::from("no-match");
        cursors.begin_line(&line);
        assert!(!cursors.may_match(7, &prefilter, &line, 0));

        line.clear();
        line.push_str("keyword!");
        cursors.begin_line(&line);
        assert!(cursors.may_match(7, &prefilter, &line, 0));
    }

    #[test]
    fn large_any_prefilter_uses_compiled_finder_without_changing_answers() {
        let parsed = parse(concat!(
            "alpha_long|beta_long|gamma_long|delta_long|epsilon_long|zeta_long|theta_long|keyword_long|",
            "iota_long|kappa_long|lambda_long|mu_long_value|nu_long_value|xi_long_value|omicron_long|pi_long_value",
        ));
        let prefilter = Prefilter::from_pattern(&parsed.ast);
        let Prefilter::Any { finder, .. } = &prefilter else {
            panic!("expected Any prefilter");
        };
        assert!(finder.is_some());
        assert_eq!(
            prefilter.next_occurrence("xx keyword_long alpha", 0),
            Some(3)
        );
        assert!(prefilter.may_match("xx keyword_long alpha", 3));
        assert!(!prefilter.may_match("xx keyword_long alpha", 4));
        assert!(!prefilter.may_match("unrelated", 0));
    }

    #[test]
    fn literal_set_leftmost_lowest_index() {
        let set = LiteralSet::new(vec!["bb".into(), "b".into(), "a".into()]);
        assert_eq!(set.find("abb", 0), Some((2, 0, 1)));
        assert_eq!(set.find("abb", 1), Some((0, 1, 3)));
    }

    #[test]
    fn literal_trie_preserves_empty_prefix_and_utf8_order() {
        let set = LiteralSet::new(vec!["éx".into(), "é".into(), "".into()]);
        assert_eq!(set.find("zéx", 1), Some((0, 1, 4)));

        let set = LiteralSet::new(vec!["".into(), "é".into()]);
        assert_eq!(set.find("é", 0), Some((0, 0, 0)));
        assert_eq!(set.find("é", 1), None);
    }
}