polyc_eventlog_model/

nav.rs

//! Storage-agnostic lexical navigation over a conversation's own history.
//!
//! When compaction folds older turns out of the model's window, they remain in
//! the journal. This module is the pure, storage-agnostic core that lets a turn
//! reach back into that folded-out history on demand: given already-decoded
//! [`HistoryEntry`] slices of *the caller's own* conversation, it ranks them
//! against a query and returns [`HistoryHit`]s. Decoding events into entries and
//! enforcing the caller-boundary scope are the caller's job (control plane); this
//! module never touches storage and never crosses a conversation.
//!
//! Ranking is deliberately lexical (term overlap / frequency), not semantic — no
//! embedding service, no vector index.

/// One decoded, human-readable slice of the caller's own history.
///
/// Projected from the event journal for navigation. `position` is the journal
/// position the source event was assigned (a strictly increasing ordinal within
/// the conversation); `turn_id` identifies the turn it belongs to.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct HistoryEntry {
    /// The turn this slice belongs to.
    pub turn_id: String,
    /// Journal position of the source event (monotonic within the conversation).
    pub position: u64,
    /// The decoded, human-readable text of the slice.
    pub text: String,
}

/// A lexical match against the caller's own history, returned newest-relevant
/// first. Carries enough to let the caller then fetch the full turn.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct HistoryHit {
    /// The turn the match was found in.
    pub turn_id: String,
    /// Journal position of the matched entry.
    pub position: u64,
    /// A short excerpt of the matched text for the model to judge relevance.
    pub snippet: String,
}

/// Returns whether `query` contains at least one searchable term.
///
/// A query made only of punctuation, whitespace, or symbols tokenizes to
/// nothing and can only ever produce an empty result — indistinguishable from
/// a genuine no-match. Callers check this up front and surface an explicit
/// error instead of silently searching nothing.
#[must_use]
pub fn has_searchable_terms(query: &str) -> bool {
    !terms_of(query).is_empty()
}

/// Rank `entries` against a free-text `query`, returning at most `limit` hits,
/// one per turn.
///
/// Lexical only: an entry is a candidate when it shares at least one query
/// term. Each turn surfaces at most once (its best-scoring entry), so a single
/// verbose turn whose every message matches cannot crowd other matching turns
/// out of the `limit` slots.
#[must_use]
pub fn search(entries: &[HistoryEntry], query: &str, limit: usize) -> Vec<HistoryHit> {
    let terms = distinct_terms_of(query);
    if terms.is_empty() {
        return Vec::new();
    }
    // Whole-token matching works for space-separated scripts, but an
    // unsegmented script (Chinese, Japanese, Thai) tokenizes to one run per
    // sentence, so no query could ever whole-token-match it. Any non-ASCII
    // term therefore also matches as a case-insensitive substring; ASCII terms
    // stay whole-token only, so "cat" never matches inside "concatenation".
    let use_substring = terms.iter().any(|t| !t.is_ascii());
    // Best-scoring entry per turn; a same-score tie keeps the newer entry.
    let mut best: std::collections::HashMap<&str, (usize, &HistoryEntry)> =
        std::collections::HashMap::new();
    for e in entries {
        let entry_terms = terms_of(&e.text);
        let lowered = use_substring.then(|| e.text.to_lowercase());
        let overlap = terms
            .iter()
            .filter(|t| {
                entry_terms.contains(t)
                    || (!t.is_ascii() && lowered.as_deref().is_some_and(|l| l.contains(t.as_str())))
            })
            .count();
        if overlap == 0 {
            continue;
        }
        match best.entry(e.turn_id.as_str()) {
            std::collections::hash_map::Entry::Occupied(mut slot) => {
                let (score, prev) = *slot.get();
                if (overlap, e.position) > (score, prev.position) {
                    slot.insert((overlap, e));
                }
            }
            std::collections::hash_map::Entry::Vacant(slot) => {
                slot.insert((overlap, e));
            }
        }
    }
    let mut scored: Vec<(usize, &HistoryEntry)> = best.into_values().collect();
    // Most query-term overlap first; ties broken newest-first (higher position)
    // so a later mention of the same terms surfaces above an older one.
    scored.sort_by(|(a_score, a), (b_score, b)| {
        b_score
            .cmp(a_score)
            .then_with(|| b.position.cmp(&a.position))
    });
    scored
        .into_iter()
        .take(limit)
        .map(|(_, e)| HistoryHit {
            turn_id: e.turn_id.clone(),
            position: e.position,
            snippet: snippet_of(&e.text, &terms),
        })
        .collect()
}

/// Longest excerpt returned per hit, in characters — enough context for the
/// model to judge relevance without pulling the whole (possibly huge) turn back
/// into the window; it can then fetch the full turn if it wants more.
const MAX_SNIPPET_CHARS: usize = 200;

/// The verbatim text of one past turn, assembled for `conversation_read_turn`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct TurnText {
    /// The turn whose text this is.
    pub turn_id: String,
    /// The turn's decoded messages, joined in journal order, middle-elided to
    /// [`MAX_PEEK_CHARS`] when the turn is very long.
    pub text: String,
    /// Whether the text was elided to fit the cap (so the model knows it is
    /// seeing a window, not the whole turn).
    pub truncated: bool,
}

/// Longest peeked turn text returned, in characters.
///
/// Peek pulls a specific past turn back into the window in full, so this is far
/// larger than a search snippet — but still bounded, because a single turn can
/// carry a pasted document that would otherwise blow the window it is meant to
/// conserve. A turn over the cap comes back middle-elided (head + tail, marker
/// between), which keeps both the turn's opening and its conclusion.
pub const MAX_PEEK_CHARS: usize = 8_000;

/// Assemble the verbatim text of the entries belonging to `turn_id`, in journal
/// order, middle-elided to [`MAX_PEEK_CHARS`].
///
/// Returns `None` when no committed entry carries that turn id — the caller
/// surfaces that as an explicit error rather than an empty success, so a peek
/// at a turn that was never committed (or a hallucinated id) can't read as "the
/// turn was empty".
#[must_use]
pub fn peek(entries: &[HistoryEntry], turn_id: &str) -> Option<TurnText> {
    let joined = entries
        .iter()
        .filter(|e| e.turn_id == turn_id)
        .map(|e| e.text.as_str())
        .collect::<Vec<_>>();
    if joined.is_empty() {
        return None;
    }
    let full = joined.join("\n");
    let (text, truncated) = middle_elide(&full, MAX_PEEK_CHARS);
    Some(TurnText {
        turn_id: turn_id.to_owned(),
        text,
        truncated,
    })
}

/// Longest accepted [`grep`] pattern, in characters.
///
/// The pattern is model-authored input; an unbounded one is a cheap way to
/// balloon compile time and the compiled program. Anything a model
/// legitimately greps for — exact wording, an id, a URL — fits well under
/// this.
pub const MAX_PATTERN_CHARS: usize = 512;

/// Compiled-program size cap for [`grep`] patterns, in bytes.
///
/// The regex engine is linear-time in the haystack, so backtracking blowup is
/// not the risk — a pathological pattern (nested counted repetition, huge
/// alternation) ballooning the compiled program is. This is orders of
/// magnitude above any legitimate recall pattern.
const REGEX_SIZE_LIMIT: usize = 1 << 18;

/// Why [`grep`] rejected a pattern.
///
/// Callers surface each of these as a loud tool error — never a silent empty
/// hit list, which the model would read as "never said" — matching the
/// search/peek discipline.
#[derive(Debug, thiserror::Error)]
pub enum GrepError {
    /// The pattern was empty; it would match every entry, which can only
    /// mislead.
    #[error("pattern is empty")]
    EmptyPattern,
    /// The pattern exceeded [`MAX_PATTERN_CHARS`].
    #[error("pattern is longer than {MAX_PATTERN_CHARS} characters")]
    PatternTooLong,
    /// The pattern failed to compile — bad syntax, or a compiled program over
    /// the size cap. Carries the engine's own message so the model can fix
    /// the pattern.
    #[error("pattern does not compile: {0}")]
    InvalidPattern(String),
}

/// Match `entries` against the regular expression `pattern`, returning at most
/// `limit` hits, one per turn, newest first.
///
/// The complement of [`search`]: keyword ranking finds a topic, grep finds
/// exact wording or a shape (an id, a URL, a phrase). Matching is
/// case-insensitive by default; the pattern can opt back out with an inline
/// `(?-i)`. Each turn surfaces at most once — its newest matching entry, with
/// the snippet windowed around that entry's first match — mirroring
/// [`search`]'s newer-wins discipline so a verbose turn cannot crowd others
/// out of the `limit` slots.
///
/// # Errors
///
/// Returns a [`GrepError`] when the pattern is empty, longer than
/// [`MAX_PATTERN_CHARS`], or fails to compile (including a compiled program
/// over the internal size cap). A bad pattern never reads as an empty result.
pub fn grep(
    entries: &[HistoryEntry],
    pattern: &str,
    limit: usize,
) -> Result<Vec<HistoryHit>, GrepError> {
    if pattern.is_empty() {
        return Err(GrepError::EmptyPattern);
    }
    if pattern.chars().count() > MAX_PATTERN_CHARS {
        return Err(GrepError::PatternTooLong);
    }
    let re = regex::RegexBuilder::new(pattern)
        .case_insensitive(true)
        .size_limit(REGEX_SIZE_LIMIT)
        .build()
        .map_err(|e| GrepError::InvalidPattern(e.to_string()))?;
    // Newest matching entry per turn, keyed by turn id; the value keeps the
    // byte offset of that entry's first match for snippet centering.
    let mut best: std::collections::HashMap<&str, (&HistoryEntry, usize)> =
        std::collections::HashMap::new();
    for e in entries {
        let Some(m) = re.find(&e.text) else {
            continue;
        };
        match best.entry(e.turn_id.as_str()) {
            std::collections::hash_map::Entry::Occupied(mut slot) => {
                if e.position > slot.get().0.position {
                    slot.insert((e, m.start()));
                }
            }
            std::collections::hash_map::Entry::Vacant(slot) => {
                slot.insert((e, m.start()));
            }
        }
    }
    let mut hits: Vec<(&HistoryEntry, usize)> = best.into_values().collect();
    // Newest first: recall usually wants the latest place the wording
    // appeared, and there is no overlap score to rank by.
    hits.sort_by_key(|(e, _)| std::cmp::Reverse(e.position));
    Ok(hits
        .into_iter()
        .take(limit)
        .map(|(e, match_start)| HistoryHit {
            turn_id: e.turn_id.clone(),
            position: e.position,
            snippet: snippet_around_byte(&e.text, match_start),
        })
        .collect())
}

/// Marker inserted where [`middle_elide`] removed the middle of an oversized
/// text, so the model can see the cut is deliberate rather than the turn's own
/// content.
const ELISION_MARKER: &str = "\n…[middle elided]…\n";

/// Clamp `text` to at most `max_chars` characters, keeping the head and tail
/// and replacing the middle with [`ELISION_MARKER`] when it overflows. Operates
/// on the char vector, so it never splits a multi-byte boundary. Returns the
/// (possibly shortened) text and whether anything was removed.
fn middle_elide(text: &str, max_chars: usize) -> (String, bool) {
    let chars: Vec<char> = text.chars().collect();
    if chars.len() <= max_chars {
        return (text.to_owned(), false);
    }
    let marker_len = ELISION_MARKER.chars().count();
    // A cap too small to fit the marker plus any content can't show a
    // head-and-tail window, so hard-truncate the head to honor the cap rather
    // than emit a marker that would itself overflow it. (Not reachable at the
    // caller's `MAX_PEEK_CHARS`; this keeps the helper honest for a smaller cap.)
    if max_chars <= marker_len {
        return (chars[..max_chars].iter().collect(), true);
    }
    let budget = max_chars - marker_len;
    let head = budget / 2;
    let tail = budget - head;
    let head_text: String = chars[..head].iter().collect();
    let tail_text: String = chars[chars.len() - tail..].iter().collect();
    (format!("{head_text}{ELISION_MARKER}{tail_text}"), true)
}

/// A window of at most [`MAX_SNIPPET_CHARS`] characters around the first
/// whole-token `terms` match in `text` (or the head of `text` when nothing
/// matches). Operates purely on the char vector, so it never splits a multi-byte
/// boundary and there is no byte/char offset drift when case-folding changes the
/// character count (e.g. 'İ' lowercasing to two chars).
fn snippet_of(text: &str, terms: &[String]) -> String {
    let chars: Vec<char> = text.chars().collect();
    if chars.len() <= MAX_SNIPPET_CHARS {
        return text.to_owned();
    }
    // Center on the first WHOLE-TOKEN match so a query term can't land inside a
    // longer word (e.g. "cat" inside "concatenation") and produce a window that
    // misses the real token. Unsegmented scripts never token-match, so fall
    // back to the substring hit that made the entry match; then to the head.
    let match_char = first_token_match_char(&chars, terms)
        .or_else(|| first_substring_match_char(&chars, terms))
        .unwrap_or(0);
    window_around(&chars, match_char)
}

/// A window of at most [`MAX_SNIPPET_CHARS`] characters around the match
/// beginning at byte `match_start` of `text` — the [`grep`] counterpart of
/// [`snippet_of`]. Converts the engine's byte offset to a char index first,
/// so the window math shares the never-splits-a-boundary discipline.
fn snippet_around_byte(text: &str, match_start: usize) -> String {
    let chars: Vec<char> = text.chars().collect();
    if chars.len() <= MAX_SNIPPET_CHARS {
        return text.to_owned();
    }
    let match_char = text[..match_start].chars().count();
    window_around(&chars, match_char)
}

/// The [`MAX_SNIPPET_CHARS`]-wide char window centered on `match_char`,
/// clamped to the ends of `chars`.
fn window_around(chars: &[char], match_char: usize) -> String {
    let half = MAX_SNIPPET_CHARS / 2;
    let end = (match_char + half).min(chars.len());
    let start = end.saturating_sub(MAX_SNIPPET_CHARS);
    chars[start..end].iter().collect()
}

/// Char index at which the first whole-token occurrence of any query term begins
/// in `chars`. Uses the same tokenization discipline as [`terms_of`] (split on
/// non-alphanumeric, case-insensitive compare) while tracking each token's start
/// index in the original char vector, so the returned offset maps back onto
/// `chars` with no byte/char mismatch.
fn first_token_match_char(chars: &[char], terms: &[String]) -> Option<usize> {
    let mut i = 0;
    while i < chars.len() {
        if !chars[i].is_alphanumeric() {
            i += 1;
            continue;
        }
        let start = i;
        let mut token = String::new();
        while i < chars.len() && chars[i].is_alphanumeric() {
            token.extend(chars[i].to_lowercase());
            i += 1;
        }
        if terms.contains(&token) {
            return Some(start);
        }
    }
    None
}

/// Char index of the first case-insensitive substring occurrence of any
/// non-ASCII query term in `chars`. This is the snippet-centering counterpart
/// of the substring match in [`search`]: an unsegmented script never
/// whole-token-matches (the whole sentence is one token), so the window
/// centers on the substring hit instead. ASCII terms are excluded so a short
/// word can't center the window inside a longer one.
fn first_substring_match_char(chars: &[char], terms: &[String]) -> Option<usize> {
    let terms: Vec<Vec<char>> = terms
        .iter()
        .filter(|t| !t.is_ascii())
        .map(|t| t.chars().collect())
        .collect();
    if terms.is_empty() {
        return None;
    }
    (0..chars.len()).find(|&start| {
        terms.iter().any(|term| {
            chars[start..]
                .iter()
                .flat_map(|c| c.to_lowercase())
                .take(term.len())
                .eq(term.iter().copied())
        })
    })
}

/// Lowercase, split on non-alphanumeric runs — the shared lexical tokenizer for
/// both the query and entry text so matching is case- and punctuation-insensitive.
fn terms_of(s: &str) -> Vec<String> {
    s.split(|c: char| !c.is_alphanumeric())
        .filter(|t| !t.is_empty())
        .map(str::to_lowercase)
        .collect()
}

/// The distinct lexical terms of `query`: lowercased, split on non-alphanumeric
/// runs, sorted, and deduplicated.
///
/// Duplicates are removed because a word repeated in the query must count once
/// toward an entry's overlap score, or repetition (of, say, a stop word) would
/// outrank a distinct informative match.
///
/// Public so the participation-scoped search index tokenizes text exactly the
/// way this module does. A maintained index and a live replay that disagreed
/// on what a word is would return different results for the same query, and
/// the difference would surface as missing hits rather than as an error — so
/// there is one tokenizer, here, rather than a second one that starts
/// identical and drifts.
#[must_use]
pub fn distinct_terms_of(query: &str) -> Vec<String> {
    let mut terms = terms_of(query);
    terms.sort_unstable();
    terms.dedup();
    terms
}

#[cfg(test)]
mod tests {
    #![allow(clippy::pedantic, clippy::nursery, missing_docs)]

    use super::*;

    fn entry(turn_id: &str, position: u64, text: &str) -> HistoryEntry {
        HistoryEntry {
            turn_id: turn_id.to_owned(),
            position,
            text: text.to_owned(),
        }
    }

    #[test]
    fn search_returns_only_entries_sharing_a_query_term() {
        let entries = vec![
            entry("t1", 1, "we decided to use BM25 ranking for history"),
            entry("t2", 2, "lunch plans for friday afternoon"),
        ];
        let hits = search(&entries, "BM25", 10);
        assert_eq!(hits.len(), 1);
        assert_eq!(hits[0].turn_id, "t1");
        assert_eq!(hits[0].position, 1);
    }

    #[test]
    fn search_ranks_more_query_term_overlap_first() {
        let entries = vec![
            entry("t1", 1, "the deploy pipeline runs on cloud build"),
            entry(
                "t2",
                2,
                "the deploy pipeline and the release pipeline both matter",
            ),
        ];
        // t2 shares both "deploy" and "pipeline"; t1 shares only "pipeline".
        let hits = search(&entries, "deploy pipeline", 10);
        assert_eq!(hits.len(), 2);
        assert_eq!(hits[0].turn_id, "t2", "more overlap ranks first");
        assert_eq!(hits[1].turn_id, "t1");
    }

    #[test]
    fn snippet_is_bounded_and_contains_the_match() {
        let filler = "padding ".repeat(200); // ~1600 chars of noise
        let text = format!("{filler} the keyword quantum appears here {filler}");
        let hits = search(&[entry("t1", 1, &text)], "quantum", 10);
        assert_eq!(hits.len(), 1);
        assert!(
            hits[0].snippet.len() <= MAX_SNIPPET_CHARS,
            "snippet {} chars exceeds cap",
            hits[0].snippet.len()
        );
        assert!(
            hits[0].snippet.to_lowercase().contains("quantum"),
            "snippet must show the match: {:?}",
            hits[0].snippet
        );
    }

    #[test]
    fn snippet_centers_on_whole_token_not_substring() {
        // "concatenation" contains "cat" as a SUBSTRING near the head; the real
        // whole-token "cat" is a standalone word near the end. The window must
        // land on the standalone token, not the head substring.
        let head = "concatenation ".repeat(30); // > MAX_SNIPPET_CHARS of substring noise
        let tail = "padding ".repeat(30);
        let text = format!("{head}and then a cat sat over there {tail}");
        let hits = search(&[entry("t1", 1, &text)], "cat", 10);
        assert_eq!(hits.len(), 1);
        assert!(
            hits[0].snippet.contains(" cat ")
                || terms_of(&hits[0].snippet).contains(&"cat".to_owned()),
            "snippet must contain the whole-token match, not just the \
             'concatenation' region: {:?}",
            hits[0].snippet
        );
    }

    #[test]
    fn search_returns_one_hit_per_turn() {
        // A verbose turn with several matching entries must not crowd an older
        // matching turn out of the limit: one hit per turn, best entry wins.
        let entries = vec![
            entry("old", 1, "the deploy decision: ship behind a flag"),
            entry("noisy", 2, "kicking off the deploy now"),
            entry("noisy", 3, "deploy is in progress"),
            entry("noisy", 4, "deploy went fine"),
        ];
        let hits = search(&entries, "deploy", 2);
        let turn_ids: Vec<&str> = hits.iter().map(|h| h.turn_id.as_str()).collect();
        assert_eq!(hits.len(), 2);
        assert!(
            turn_ids.contains(&"old"),
            "old turn crowded out: {turn_ids:?}"
        );
        assert!(turn_ids.contains(&"noisy"), "{turn_ids:?}");
    }

    #[test]
    fn repeated_query_words_do_not_inflate_rank() {
        // "the" repeated in the query must count once: the entry matching the
        // informative term ranks at least as well as a stop-word-only entry.
        let entries = vec![
            entry("stopword", 1, "the the the"),
            entry("real", 2, "we agreed on friday"),
        ];
        let hits = search(&entries, "the plan the agreed", 10);
        assert_eq!(hits[0].turn_id, "real", "{hits:?}");
    }

    #[test]
    fn search_matches_unsegmented_scripts_by_substring() {
        // Chinese has no token boundaries for terms_of to split on, so the
        // whole sentence is one token; the non-ASCII substring fallback is
        // what makes the entry findable at all.
        let entries = vec![
            entry("t1", 1, "我们决定了部署计划"),
            entry("t2", 2, "lunch plans for friday"),
        ];
        let hits = search(&entries, "部署计划", 10);
        assert_eq!(hits.len(), 1);
        assert_eq!(hits[0].turn_id, "t1");
    }

    #[test]
    fn ascii_terms_never_match_as_substrings() {
        // The substring fallback is scoped to non-ASCII terms: "cat" inside
        // "concatenation" must stay a non-match.
        let entries = vec![entry("t1", 1, "string concatenation details")];
        assert!(search(&entries, "cat", 10).is_empty());
    }

    #[test]
    fn snippet_centers_on_substring_match_for_unsegmented_scripts() {
        let head = "padding ".repeat(40); // push well past MAX_SNIPPET_CHARS
        let text = format!("{head}我们决定了部署计划就这样");
        let hits = search(&[entry("t1", 1, &text)], "部署计划", 10);
        assert_eq!(hits.len(), 1);
        assert!(
            hits[0].snippet.contains("部署计划"),
            "snippet must contain the substring match: {:?}",
            hits[0].snippet
        );
    }

    #[test]
    fn has_searchable_terms_rejects_symbol_only_queries() {
        assert!(!has_searchable_terms("?!… → ---"));
        assert!(!has_searchable_terms("   "));
        assert!(has_searchable_terms("deploy plan"));
        assert!(has_searchable_terms("部署计划"));
    }

    #[test]
    fn snippet_is_unicode_safe_when_case_folding_grows_char_count() {
        // 'İ' (U+0130) lowercases to TWO chars, so a byte-offset-on-lowercased
        // approach drifts. Several before a near-start match must not panic and
        // the snippet must still contain the matched token.
        let prefix = "İ".repeat(20);
        let tail = "padding ".repeat(40); // push well past MAX_SNIPPET_CHARS
        let text = format!("{prefix} the marker quantum here {tail}");
        let hits = search(&[entry("t1", 1, &text)], "quantum", 10);
        assert_eq!(hits.len(), 1);
        assert!(
            hits[0].snippet.to_lowercase().contains("quantum"),
            "unicode snippet must contain the match: {:?}",
            hits[0].snippet
        );
    }

    #[test]
    fn grep_matches_by_pattern_and_returns_the_turn() {
        let entries = vec![
            entry("t1", 1, "the incident id was INC-4521 that night"),
            entry("t2", 2, "lunch plans for friday afternoon"),
        ];
        let hits = grep(&entries, r"INC-\d+", 10).expect("valid pattern");
        assert_eq!(hits.len(), 1);
        assert_eq!(hits[0].turn_id, "t1");
        assert_eq!(hits[0].position, 1);
        assert!(
            hits[0].snippet.contains("INC-4521"),
            "{:?}",
            hits[0].snippet
        );
    }

    #[test]
    fn grep_is_case_insensitive_unless_the_pattern_opts_out() {
        let entries = vec![entry("t1", 1, "we shipped the Deploy Plan")];
        assert_eq!(grep(&entries, "deploy plan", 10).unwrap().len(), 1);
        assert!(
            grep(&entries, "(?-i)deploy plan", 10).unwrap().is_empty(),
            "an inline (?-i) restores case sensitivity"
        );
    }

    #[test]
    fn grep_returns_one_hit_per_turn_newest_first() {
        let entries = vec![
            entry("old", 1, "deploy the flag"),
            entry("noisy", 2, "deploy one"),
            entry("noisy", 3, "deploy two"),
            entry("new", 4, "deploy again"),
        ];
        let hits = grep(&entries, "deploy", 10).unwrap();
        let ids: Vec<&str> = hits.iter().map(|h| h.turn_id.as_str()).collect();
        assert_eq!(ids, vec!["new", "noisy", "old"], "newest turn first");
        assert_eq!(
            hits[1].position, 3,
            "a turn surfaces once, via its newest matching entry"
        );
    }

    #[test]
    fn grep_limit_caps_the_hits() {
        let entries = vec![
            entry("t1", 1, "deploy a"),
            entry("t2", 2, "deploy b"),
            entry("t3", 3, "deploy c"),
        ];
        let hits = grep(&entries, "deploy", 2).unwrap();
        assert_eq!(hits.len(), 2);
        assert_eq!(hits[0].turn_id, "t3", "the newest survive the cap");
    }

    #[test]
    fn grep_snippet_is_bounded_and_contains_the_match() {
        let filler = "padding ".repeat(200); // ~1600 chars of noise
        let text = format!("{filler}the marker INC-99 appears here {filler}");
        let hits = grep(&[entry("t1", 1, &text)], r"INC-\d+", 10).unwrap();
        assert_eq!(hits.len(), 1);
        assert!(
            hits[0].snippet.chars().count() <= MAX_SNIPPET_CHARS,
            "snippet {} chars exceeds cap",
            hits[0].snippet.chars().count()
        );
        assert!(
            hits[0].snippet.contains("INC-99"),
            "snippet must show the match: {:?}",
            hits[0].snippet
        );
    }

    #[test]
    fn grep_is_unicode_safe_when_windowing() {
        // Multi-byte chars before the match: the byte→char conversion must not
        // drift or split a boundary when the window lands mid-text.
        let head = "🚀".repeat(500); // well past MAX_SNIPPET_CHARS, 4 bytes each
        let text = format!("{head} 部署计划 done");
        let hits = grep(&[entry("t1", 1, &text)], "部署计划", 10).unwrap();
        assert_eq!(hits.len(), 1);
        assert!(
            hits[0].snippet.contains("部署计划"),
            "snippet must contain the match: {:?}",
            hits[0].snippet
        );
    }

    #[test]
    fn grep_rejects_an_empty_pattern() {
        let entries = vec![entry("t1", 1, "anything")];
        assert!(matches!(
            grep(&entries, "", 10),
            Err(GrepError::EmptyPattern)
        ));
    }

    #[test]
    fn grep_rejects_an_oversized_pattern() {
        let pattern = "a".repeat(MAX_PATTERN_CHARS + 1);
        assert!(matches!(
            grep(&[], &pattern, 10),
            Err(GrepError::PatternTooLong)
        ));
    }

    #[test]
    fn grep_rejects_a_pattern_that_does_not_compile() {
        let err = grep(&[], "[unclosed", 10).unwrap_err();
        assert!(
            matches!(&err, GrepError::InvalidPattern(msg) if !msg.is_empty()),
            "{err:?}"
        );
    }

    #[test]
    fn grep_rejects_a_pattern_whose_program_would_balloon() {
        // Nested counted repetition multiplies the compiled program (a million
        // copies of `a` here) far past the size cap. The engine is linear-time
        // in the haystack, so program size is the guarded resource.
        let err = grep(&[], "(?:a{1000}){1000}", 10).unwrap_err();
        assert!(matches!(err, GrepError::InvalidPattern(_)), "{err:?}");
    }

    #[test]
    fn peek_joins_a_turns_entries_in_order() {
        let entries = vec![
            entry("t1", 1, "the user asked about deploys"),
            entry("t1", 2, "the assistant explained the pipeline"),
            entry("t2", 3, "an unrelated later turn"),
        ];
        let peeked = peek(&entries, "t1").expect("t1 present");
        assert_eq!(peeked.turn_id, "t1");
        assert!(!peeked.truncated);
        assert_eq!(
            peeked.text,
            "the user asked about deploys\nthe assistant explained the pipeline"
        );
    }

    #[test]
    fn peek_of_an_unknown_turn_is_none_not_empty() {
        let entries = vec![entry("t1", 1, "only turn")];
        assert!(
            peek(&entries, "does-not-exist").is_none(),
            "a peek at a turn that isn't in history must fail loud, not read as empty"
        );
    }

    #[test]
    fn peek_middle_elides_an_oversized_turn_keeping_head_and_tail() {
        let head = "HEAD ".repeat(1_000); // ~5000 chars
        let tail = "TAIL ".repeat(1_000);
        let text = format!("{head}MIDDLE-SECRET{tail}");
        let peeked = peek(&[entry("t1", 1, &text)], "t1").expect("t1");
        assert!(peeked.truncated, "an oversized turn is elided");
        assert!(peeked.text.chars().count() <= MAX_PEEK_CHARS);
        assert!(peeked.text.starts_with("HEAD "), "head kept");
        assert!(peeked.text.trim_end().ends_with("TAIL"), "tail kept");
        assert!(peeked.text.contains("elided"), "the cut is marked");
    }

    #[test]
    fn middle_elide_honors_a_cap_smaller_than_the_marker() {
        // Degenerate cap: the output must still fit the cap (hard head
        // truncation), never emit a marker that overflows it.
        let (out, truncated) = middle_elide("abcdefghijklmnop", 4);
        assert!(truncated);
        assert_eq!(out.chars().count(), 4);
        assert_eq!(out, "abcd");
    }

    #[test]
    fn peek_is_unicode_safe_when_eliding() {
        // A turn of multi-byte chars over the cap must elide without panicking
        // on a byte boundary.
        let text = "🚀".repeat(MAX_PEEK_CHARS + 500);
        let peeked = peek(&[entry("t1", 1, &text)], "t1").expect("t1");
        assert!(peeked.truncated);
        assert!(peeked.text.chars().count() <= MAX_PEEK_CHARS);
    }
}