syntext 2.0.0

//! Query-time covering set extraction.
//!
//! `build_covering` and `build_covering_inner` produce the minimal set of gram
//! hashes needed to query the index for a literal or regex fragment. Moved here
//! from the parent module to keep `mod.rs` under the 400-line limit.

use super::{
    boundary_positions, gram_hash, is_forced_boundary, with_boundary_positions_lower, MAX_GRAM_LEN,
    MIN_GRAM_LEN,
};

// ---------------------------------------------------------------------------
// T013: build_covering -- query-time covering set extraction
// ---------------------------------------------------------------------------

/// Grams classified by boundary reliability.
///
/// When a literal query is verified via `memchr::memmem`, the pattern can
/// match anywhere in a file (substring semantics).  Token-aligned grams
/// anchored only by synthetic position-0 / position-len boundaries cannot
/// capture sub-token matches (e.g. literal `parse` misses `reparse`).
///
/// Splitting grams into two tiers lets the query router widen the candidate
/// set when edge-only grams would produce false negatives.
#[derive(Debug, Clone, Default)]
pub struct CoveringSet {
    /// Grams whose BOTH boundaries are real (interior positions, or a
    /// position-0/len endpoint whose byte is a forced boundary). Fully
    /// anchored, so they can safely narrow the candidate set via AND
    /// semantics. A gram with even one synthetic boundary is `optional`, not
    /// required: e.g. for query `parse_query` the gram `parse` has a real
    /// interior end (`_`) but a synthetic start, so it is optional -- treating
    /// it as required would drop a doc that tokenizes `reparse_query` into
    /// `reparse`/`query` and never emits gram `parse`.
    pub required: Vec<u64>,
    /// Grams with at least one synthetic boundary (a position-0/len endpoint
    /// whose byte is not a forced boundary). Using these alone as an AND
    /// filter risks false negatives on sub-token matches.
    pub optional: Vec<u64>,
}

impl CoveringSet {
    /// All grams (required + optional) in a single flat iterator.
    pub fn all_grams(&self) -> impl Iterator<Item = u64> + '_ {
        self.required.iter().chain(self.optional.iter()).copied()
    }

    /// True when no grams of either tier exist.
    pub fn is_empty(&self) -> bool {
        self.required.is_empty() && self.optional.is_empty()
    }
}

/// Extract the minimal covering set of grams from a query pattern,
/// classified into required and optional tiers.
///
/// Lowercases `input`, detects the same boundary positions as the original
/// token-aligned query path, and emits one gram hash per
/// consecutive-boundary span with length >= `MIN_GRAM_LEN`.
///
/// Each gram is classified:
/// - **required**: BOTH boundaries are real (interior position, or position
///   0/len with a forced-boundary byte).
/// - **optional**: at least one boundary is synthetic (position 0 or len with
///   a non-forced-boundary endpoint byte).
///
/// Returns `None` if no grams of sufficient length exist (the entire query
/// falls in sub-`MIN_GRAM_LEN` spans). Callers must fall back to full scan.
///
/// # Example
///
/// ```ignore
/// use syntext::__internal::build_covering;
///
/// // "parse_query" has one synthetic boundary for each gram (start/end of query)
/// // so they are optional to prevent false negatives on sub-token matches.
/// let covering = build_covering(b"parse_query").unwrap();
/// assert!(covering.required.is_empty());
/// assert_eq!(covering.optional.len(), 2);
///
/// // "_parse_query_" is fully anchored by forced boundaries at start and end,
/// // so its grams are required.
/// let covering = build_covering(b"_parse_query_").unwrap();
/// assert!(covering.required.len() >= 2);
/// assert!(covering.optional.is_empty());
///
/// // "parse" has no interior boundaries and no forced-edge bytes:
/// // the single gram is optional (unanchored).
/// let covering = build_covering(b"parse").unwrap();
/// assert!(covering.required.is_empty());
/// assert_eq!(covering.optional.len(), 1);
///
/// // Short query: no qualifying grams
/// assert!(build_covering(b"ab").is_none());
/// ```
pub fn build_covering(input: &[u8]) -> Option<CoveringSet> {
    if input.len() < MIN_GRAM_LEN {
        return None;
    }

    // Perf note: the boundary buffer inside with_boundary_positions_lower is a
    // thread-local Vec reused across calls (no per-call allocation). The small
    // `lower` and `hashes` Vecs below are the only allocations, and both callers
    // (route_query, literal_grams) consume the gram data in the Some branch.
    // The early return above already handles the common "too short" case with
    // zero work, so a separate "is indexable?" fast path would only help the
    // rare case where the pattern is long enough but no spans qualify.
    let lower: Vec<u8> = input.iter().map(|b| b.to_ascii_lowercase()).collect();
    with_boundary_positions_lower(&lower, |boundaries| {
        let mut required = Vec::new();
        let mut optional = Vec::new();

        for w in boundaries.windows(2) {
            let (start, end) = (w[0], w[1]);
            let span = end - start;
            if !(MIN_GRAM_LEN..=MAX_GRAM_LEN).contains(&span) {
                continue;
            }
            // Spans outside [MIN_GRAM_LEN, MAX_GRAM_LEN] are not covered.
            // This leaves a gap in coverage (more false positives), but correctness
            // is maintained because the verifier always re-checks each candidate.

            // A boundary at position 0 or len is "real" only when the byte
            // at that position is a forced boundary character. Interior
            // boundaries (start > 0, end < len) are always real.
            let start_is_real = start > 0 || is_forced_boundary(lower[0]);
            let end_is_real = end < lower.len() || is_forced_boundary(lower[lower.len() - 1]);

            let hash = gram_hash(&lower[start..end]);
            if start_is_real && end_is_real {
                required.push(hash);
            } else {
                optional.push(hash);
            }
        }

        if required.is_empty() && optional.is_empty() {
            None
        } else {
            Some(CoveringSet { required, optional })
        }
    })
}

// ---------------------------------------------------------------------------
// T016: build_covering_inner -- regex-safe gram extraction
// ---------------------------------------------------------------------------

/// Extract covering grams from a regex literal fragment.
///
/// Unlike `build_covering` (which treats position 0 and `len` as boundaries),
/// this function refuses spans that rely on synthetic fragment edges. Interior
/// boundaries are safe, because the current tokenizer's boundary decisions are
/// determined by the adjacent bytes at that position.
///
/// For a regex like `parse_quer[yi]`, the HIR literal "parse_quer" ends
/// mid-token. `build_covering` would emit gram "quer" (ending at synthetic
/// `len` boundary), but "quer" is not a gram in documents where the full
/// token is "query". `build_covering_inner` detects that 'r' (the last byte)
/// is not a forced boundary character and skips the partial span.
///
/// Returns `None` if no interior forced-boundary grams exist (caller should
/// fall back to full scan).
pub fn build_covering_inner(input: &[u8]) -> Option<Vec<u64>> {
    if input.len() < MIN_GRAM_LEN {
        return None;
    }

    let lower: Vec<u8> = input.iter().map(|b| b.to_ascii_lowercase()).collect();
    let boundaries = boundary_positions(input);

    let mut hashes = Vec::new();
    for w in boundaries.windows(2) {
        let (start, end) = (w[0], w[1]);
        let span = end - start;
        if !(MIN_GRAM_LEN..=MAX_GRAM_LEN).contains(&span) {
            continue;
        }

        let start_is_real = start > 0 || is_forced_boundary(lower[0]);
        let end_is_real = end < lower.len() || is_forced_boundary(lower[lower.len() - 1]);

        if start_is_real && end_is_real {
            hashes.push(gram_hash(&lower[start..end]));
        }
    }

    if hashes.is_empty() {
        None
    } else {
        Some(hashes)
    }
}