greplm_core/

search.rs

//! Query execution: trigram candidate filtering, then exact verification.

use std::collections::{HashMap, HashSet};
use std::path::{Component, Path, PathBuf};
use std::sync::{Arc, Mutex};

use lru::LruCache;
use memchr::memmem;
use rayon::prelude::*;
use regex::bytes::Regex as BytesRegex;
use serde::{Deserialize, Serialize};

use crate::config::Config;
use crate::error::{Error, Result};
use crate::lang::Language;
use crate::meta::Meta;
use crate::paths::Paths;
use crate::segment::{RefKind, Segment};
use crate::trigram::{self, TrigramQuery};

/// A content search request.
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(default)]
pub struct SearchQuery {
    pub pattern: String,
    pub regex: bool,
    pub case_insensitive: bool,
    /// Match only whole identifiers (word boundaries on both sides).
    pub whole_word: bool,
    pub lang: Option<String>,
    pub path: Option<String>,
    pub limit: usize,
    /// Skip the first N ranked results (for pagination).
    pub offset: usize,
    pub max_per_file: usize,
    /// Return EVERY match in deterministic (path, line) order: no ranking, no
    /// global `limit`, and no per-file caps (`max_per_file` and the internal
    /// pathological-input cap are both lifted). This is grep-equivalent
    /// completeness; use it when "find every occurrence" matters more than
    /// relevance ranking. `offset`/`limit` are ignored when set.
    pub exhaustive: bool,
}

impl Default for SearchQuery {
    fn default() -> Self {
        Self {
            pattern: String::new(),
            regex: false,
            case_insensitive: false,
            whole_word: false,
            lang: None,
            path: None,
            limit: 50,
            offset: 0,
            max_per_file: 20,
            exhaustive: false,
        }
    }
}

/// A single content match.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct SearchHit {
    pub path: String,
    pub lang: String,
    pub line: u32,
    pub column: u32,
    pub text: String,
    pub score: f32,
}

/// A symbol lookup request.
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(default)]
pub struct SymbolQuery {
    pub name: String,
    pub kind: Option<String>,
    pub exact: bool,
    pub limit: usize,
    pub offset: usize,
}

impl Default for SymbolQuery {
    fn default() -> Self {
        Self {
            name: String::new(),
            kind: None,
            exact: false,
            limit: 50,
            offset: 0,
        }
    }
}

/// A single symbol match.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct SymbolHit {
    pub path: String,
    pub lang: String,
    pub name: String,
    pub kind: String,
    pub line_start: u32,
    pub line_end: u32,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub container: Option<String>,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub signature: Option<String>,
    pub score: f32,
}

/// A resolved reference to an identifier: a definition, a call site, or an
/// import. Unlike text search, these come from the structural reference index.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct RefHit {
    pub path: String,
    pub lang: String,
    pub name: String,
    /// "definition", "call", or "import".
    pub kind: String,
    pub line: u32,
    pub column: u32,
    /// The enclosing symbol at this location, when known.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub container: Option<String>,
}

/// One edge of the call graph: a call site linking a caller symbol to a callee.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct CallSite {
    /// The enclosing symbol the call is made from (None at file scope).
    #[serde(skip_serializing_if = "Option::is_none")]
    pub caller: Option<String>,
    /// The called identifier.
    pub callee: String,
    pub path: String,
    pub lang: String,
    pub line: u32,
    pub column: u32,
}

/// A symbol affected by a change to a target symbol, with its BFS distance from
/// the target along the reverse call graph.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ImpactNode {
    pub name: String,
    pub kind: String,
    pub path: String,
    pub lang: String,
    pub line_start: u32,
    pub line_end: u32,
    /// Hops along the caller chain from the target (0 = the target itself).
    pub distance: u32,
}

/// A candidate definition for an identifier at a source position, ranked by
/// resolution confidence. `resolved` marks a single high-confidence target.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct DefHit {
    pub path: String,
    pub lang: String,
    pub name: String,
    pub kind: String,
    pub line_start: u32,
    pub line_end: u32,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub container: Option<String>,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub signature: Option<String>,
    pub score: f32,
    /// True when this is the unambiguous resolution target.
    pub resolved: bool,
}

/// The git history of a resolved symbol.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct SymbolHistory {
    pub name: String,
    pub path: String,
    pub line_start: u32,
    pub line_end: u32,
    pub commits: Vec<crate::git::Commit>,
}

/// A changed file annotated with the symbols it defines.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ChangedSymbols {
    pub path: String,
    pub status: String,
    pub symbols: Vec<String>,
}

/// A structural (AST) search match, with its captured meta-variables.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct StructHit {
    pub path: String,
    pub lang: String,
    pub line_start: u32,
    pub line_end: u32,
    /// Kind of the matched node.
    pub kind: String,
    /// First line of the match, for display.
    pub text: String,
    pub captures: Vec<crate::structural::StructCapture>,
}

enum Matcher {
    Literal(Vec<u8>),
    Regex(BytesRegex),
}

impl Matcher {
    fn build(query: &SearchQuery) -> Result<Matcher> {
        if query.regex {
            let re = regex::bytes::RegexBuilder::new(&query.pattern)
                .case_insensitive(query.case_insensitive)
                .build()?;
            Ok(Matcher::Regex(re))
        } else if query.case_insensitive {
            let re = regex::bytes::RegexBuilder::new(&regex::escape(&query.pattern))
                .case_insensitive(true)
                .build()?;
            Ok(Matcher::Regex(re))
        } else {
            Ok(Matcher::Literal(query.pattern.as_bytes().to_vec()))
        }
    }

    /// Collect the byte offsets of matches in `hay`, up to `cap`. Scanning the
    /// whole buffer (rather than line-by-line) lets regex patterns span newlines.
    /// When `whole_word` is set, only matches bounded by non-identifier bytes
    /// count.
    fn match_starts(&self, hay: &[u8], whole_word: bool, cap: usize) -> Vec<(usize, usize)> {
        let mut out = Vec::new();
        match self {
            Matcher::Literal(needle) => {
                if needle.is_empty() {
                    return out;
                }
                for pos in memmem::find_iter(hay, needle) {
                    let end = pos + needle.len();
                    if !whole_word || boundary_ok(hay, pos, end) {
                        out.push((pos, end));
                        if out.len() >= cap {
                            break;
                        }
                    }
                }
            }
            Matcher::Regex(re) => {
                for m in re.find_iter(hay) {
                    // Skip zero-width matches (e.g. `a*`, `^`): they carry no
                    // displayable span and would flag every line.
                    if m.start() == m.end() {
                        continue;
                    }
                    if !whole_word || boundary_ok(hay, m.start(), m.end()) {
                        out.push((m.start(), m.end()));
                        if out.len() >= cap {
                            break;
                        }
                    }
                }
            }
        }
        out
    }
}

/// Fuzz-only entry: build a literal/regex matcher and scan `hay` for matches.
#[doc(hidden)]
pub fn fuzz_match_starts(
    pattern: &str,
    hay: &[u8],
    regex: bool,
    case_insensitive: bool,
    whole_word: bool,
) {
    let query = SearchQuery {
        pattern: pattern.to_string(),
        regex,
        case_insensitive,
        whole_word,
        ..Default::default()
    };
    if let Ok(m) = Matcher::build(&query) {
        let _ = m.match_starts(hay, whole_word, PER_FILE_MATCH_CAP);
    }
}

/// Identifier byte for word-boundary checks. Bytes >= 0x80 are treated as
/// identifier bytes so multibyte UTF-8 (Unicode) identifiers are respected.
fn is_ident_byte(b: u8) -> bool {
    b == b'_' || b.is_ascii_alphanumeric() || b >= 0x80
}

/// True if the byte range `[start, end)` is bounded by non-identifier bytes.
fn boundary_ok(line: &[u8], start: usize, end: usize) -> bool {
    let left = start == 0 || !is_ident_byte(line[start - 1]);
    let right = end >= line.len() || !is_ident_byte(line[end]);
    left && right
}

/// Memory budget (in bytes) for the verification content cache. Eviction is
/// driven by total cached bytes rather than a file count, so a query that
/// touches many large files can't balloon resident memory. The cache is
/// content-addressed by hash, so stale entries fall out when files change and
/// are re-indexed. ~256 MiB.
const CONTENT_CACHE_BYTES: u64 = 256 * 1024 * 1024;

/// Hard cap on matches collected per file before ranking, to bound work on
/// pathological inputs (e.g. a minified file where every line matches).
const PER_FILE_MATCH_CAP: usize = 4096;

struct CacheInner {
    map: LruCache<u64, Arc<[u8]>>,
    bytes: u64,
}

/// A thread-safe, content-addressed, byte-budgeted cache of recently read
/// files. Entries are evicted least-recently-used until total cached bytes fit
/// within the budget.
struct ContentCache {
    inner: Mutex<CacheInner>,
    budget: u64,
}

impl ContentCache {
    fn new(budget_bytes: u64) -> Self {
        Self {
            inner: Mutex::new(CacheInner {
                map: LruCache::unbounded(),
                bytes: 0,
            }),
            budget: budget_bytes.max(1),
        }
    }

    /// Return the bytes for `path`, reusing a cached copy keyed by `hash`. The
    /// file is read outside the lock so concurrent verifiers don't serialize.
    fn get_or_read(&self, hash: u64, path: &Path) -> Option<Arc<[u8]>> {
        if let Ok(mut guard) = self.inner.lock() {
            if let Some(v) = guard.map.get(&hash) {
                return Some(v.clone());
            }
        }
        let data = std::fs::read(path).ok()?;
        let arc: Arc<[u8]> = Arc::from(data.into_boxed_slice());
        let len = arc.len() as u64;
        if let Ok(mut guard) = self.inner.lock() {
            // A single file larger than the whole budget is returned but not
            // cached; storing it would just evict everything else and itself.
            if len <= self.budget {
                if let Some(prev) = guard.map.put(hash, arc.clone()) {
                    guard.bytes = guard.bytes.saturating_sub(prev.len() as u64);
                }
                guard.bytes += len;
                while guard.bytes > self.budget {
                    match guard.map.pop_lru() {
                        Some((_, evicted)) => {
                            guard.bytes = guard.bytes.saturating_sub(evicted.len() as u64);
                        }
                        None => break,
                    }
                }
            }
        }
        Some(arc)
    }
}

/// Loaded, searchable index.
pub struct Searcher {
    paths: Paths,
    segments: Vec<Segment>,
    /// Live document lookup by relative path -> (segment index, doc id).
    /// Makes path-keyed queries (outline, imports, changed-since) O(1)
    /// instead of a scan over every doc table.
    ///
    /// Built on first use rather than at open: it owns a copy of every live
    /// document's path, so constructing it costs an allocation per file, and
    /// only three query paths need it. Content search, symbol lookup and
    /// context packs never touch it.
    by_path: std::sync::OnceLock<HashMap<String, (usize, u32)>>,
    /// Shared so a reloaded searcher (daemon hot-swap) keeps its warm,
    /// content-addressed file cache.
    content: Arc<ContentCache>,
}

impl Searcher {
    /// Open the index described by `meta`.
    pub fn open(paths: &Paths) -> Result<Searcher> {
        Self::open_inner(paths, None)
    }

    /// Open the index, reusing as much of `prev` as possible: segments whose
    /// id is unchanged share their parsed tables and lookup maps (only the
    /// live bitmap is re-read), and the verification content cache carries
    /// over warm. Sound because segment ids are never reused, so an id always
    /// names the same immutable content. This is what makes the daemon's
    /// per-save searcher hot-swap cheap on large repositories.
    pub fn open_reusing(paths: &Paths, prev: &Searcher) -> Result<Searcher> {
        Self::open_inner(paths, Some(prev))
    }

    fn open_inner(paths: &Paths, prev: Option<&Searcher>) -> Result<Searcher> {
        if !paths.exists() {
            return Err(Error::IndexMissing(paths.base.clone()));
        }
        let meta = Meta::load(&paths.meta_file())?;
        // Open segments concurrently: each is an independent set of files whose
        // integrity checks dominate the work. `collect` into `Result<Vec<_>>`
        // keeps manifest order, which the doc-id bookkeeping depends on.
        let mut segments: Vec<Segment> = meta
            .segments
            .par_iter()
            .map(|&seg_id| {
                match prev.and_then(|p| p.segments.iter().find(|s| s.id == seg_id)) {
                    // An id always names the same immutable content, so a
                    // reusable segment only re-reads its live bitmap.
                    Some(seg) => seg.reopen(paths),
                    None => Segment::open(paths, seg_id),
                }
            })
            .collect::<Result<_>>()?;
        // Honor deletes that are published in the manifest but not yet applied
        // to the on-disk live bitmaps (the atomic-tombstone window).
        for pt in &meta.pending_tombstones {
            if let Some(seg) = segments.iter_mut().find(|s| s.id == pt.segment_id) {
                seg.subtract_live(&pt.doc_ids);
            }
        }
        let content = match prev {
            Some(p) => p.content.clone(),
            None => Arc::new(ContentCache::new(CONTENT_CACHE_BYTES)),
        };
        Ok(Searcher {
            paths: paths.clone(),
            segments,
            by_path: std::sync::OnceLock::new(),
            content,
        })
    }

    /// The live path -> (segment, doc) lookup, built on first use.
    fn by_path(&self) -> &HashMap<String, (usize, u32)> {
        self.by_path
            .get_or_init(|| build_path_index(&self.segments))
    }

    /// Run a content search.
    pub fn search(&self, query: &SearchQuery) -> Result<Vec<SearchHit>> {
        if query.pattern.is_empty() {
            return Ok(Vec::new());
        }
        let matcher = Matcher::build(query)?;
        let tq: TrigramQuery = if query.regex {
            trigram::regex_trigrams(&query.pattern, query.case_insensitive)
        } else if query.case_insensitive {
            // Fold ASCII case into per-position trigram clauses so we still prune
            // candidates instead of scanning the whole repository.
            TrigramQuery::from_literal_ci(query.pattern.as_bytes())
        } else {
            TrigramQuery::from_literal(query.pattern.as_bytes())
        };

        let path_filter = query.path.as_deref();
        let lang_filter = query.lang.as_deref();

        // Gather candidate (segment, doc) pairs after cheap metadata filters.
        let mut targets: Vec<(usize, u32, f32)> = Vec::new();
        for (si, seg) in self.segments.iter().enumerate() {
            let candidates = seg.candidates(&tq)?;
            for doc_id in candidates.iter() {
                if !seg.is_live(doc_id) {
                    continue;
                }
                let doc = match seg.doc(doc_id) {
                    Some(d) => d,
                    None => continue,
                };
                if let Some(lf) = lang_filter {
                    if doc.lang != lf {
                        continue;
                    }
                }
                if let Some(pf) = path_filter {
                    if !doc.path.contains(pf) {
                        continue;
                    }
                }
                targets.push((si, doc_id, 0.0));
            }
        }

        // Verify candidates in parallel: each reads its file (cache/page-cache
        // backed) and scans the buffer with the real matcher.
        let root = &self.paths.root;
        let segments = &self.segments;
        let content: &ContentCache = &self.content;
        let max_per_file = query.max_per_file;
        let whole_word = query.whole_word;
        let exhaustive = query.exhaustive;
        let verify = |&(si, doc_id, _): &(usize, u32, f32)| {
            verify_doc(
                &segments[si],
                doc_id,
                root,
                content,
                &matcher,
                max_per_file,
                whole_word,
                exhaustive,
            )
            .into_iter()
        };

        if query.exhaustive {
            // Grep-equivalent: every match, deterministic (path, line, column)
            // order, no ranking and no offset/limit truncation.
            let mut hits: Vec<SearchHit> = targets.par_iter().flat_map_iter(verify).collect();
            hits.sort_by(|a, b| {
                a.path
                    .cmp(&b.path)
                    .then_with(|| a.line.cmp(&b.line))
                    .then_with(|| a.column.cmp(&b.column))
            });
            return Ok(hits);
        }

        let need = query.offset.saturating_add(query.limit);
        if need == 0 {
            return Ok(Vec::new());
        }

        // Ranked mode: verify in descending max-possible-score order and stop
        // once `need` collected hits *strictly* outrank everything still
        // unverified — no unverified doc can then reach the returned page,
        // including via tie-breaks. A hit's score is its base path score plus
        // at most 4.0 (the 1.0 match constant + the 3.0 symbol-line bonus).
        // When one batch covers every candidate, early termination can never
        // fire, so skip the per-candidate scoring and sort entirely.
        let chunk = need.saturating_mul(4).clamp(256, 4096);
        let mut hits: Vec<SearchHit>;
        if targets.len() <= chunk {
            hits = targets.par_iter().flat_map_iter(verify).collect();
        } else {
            for t in &mut targets {
                t.2 = self.segments[t.0].doc_path_score(t.1);
            }
            targets.sort_unstable_by(|a, b| {
                b.2.partial_cmp(&a.2).unwrap_or(std::cmp::Ordering::Equal)
            });
            hits = Vec::new();
            let mut start = 0usize;
            while start < targets.len() {
                let end = (start + chunk).min(targets.len());
                let mut batch: Vec<SearchHit> = targets[start..end]
                    .par_iter()
                    .flat_map_iter(verify)
                    .collect();
                hits.append(&mut batch);
                start = end;
                if start < targets.len() {
                    let remaining_max = targets[start].2 + 4.0;
                    let outranking = hits.iter().filter(|h| h.score > remaining_max).count();
                    if outranking >= need {
                        break;
                    }
                }
            }
        }

        let cmp = |a: &SearchHit, b: &SearchHit| {
            b.score
                .partial_cmp(&a.score)
                .unwrap_or(std::cmp::Ordering::Equal)
                .then_with(|| a.path.cmp(&b.path))
                .then_with(|| a.line.cmp(&b.line))
        };
        Ok(rank_paginate(hits, cmp, query.offset, query.limit))
    }

    /// Look up symbols by name. Exact queries go through the per-segment name
    /// index (O(results)); fuzzy queries scan, since prefix/substring/
    /// subsequence matching has no exact key.
    pub fn symbols(&self, query: &SymbolQuery) -> Result<Vec<SymbolHit>> {
        let needle = query.name.to_ascii_lowercase();
        let mut hits: Vec<SymbolHit> = Vec::new();
        // Score a row that already passed the name match: decode it (rows are
        // decoded only for matches), then apply the liveness/kind filters.
        let mut consider = |seg: &Segment, i: u32, score: f32| {
            let sym = match seg.sym(i) {
                Some(s) => s,
                None => return,
            };
            if !seg.is_live(sym.doc_id) {
                return;
            }
            if let Some(k) = &query.kind {
                if &sym.kind != k {
                    return;
                }
            }
            let doc = match seg.doc(sym.doc_id) {
                Some(d) => d,
                None => return,
            };
            hits.push(SymbolHit {
                path: doc.path.clone(),
                lang: doc.lang.clone(),
                name: sym.name,
                kind: sym.kind,
                line_start: sym.line_start,
                line_end: sym.line_end,
                container: sym.container,
                signature: sym.signature,
                score: score + seg.doc_path_score(sym.doc_id),
            });
        };
        for seg in &self.segments {
            if query.exact {
                let rows: Vec<u32> = seg.syms_by_lower(&needle).collect();
                for i in rows {
                    let score =
                        match match_symbol(seg.sym_name(i), seg.sym_name_lower(i), &needle, true) {
                            Some(s) => s,
                            None => continue,
                        };
                    consider(seg, i, score);
                }
            } else {
                // Fuzzy scan: prefix/substring/subsequence matching has no exact
                // key, so every symbol's name has to be looked at. Walk the
                // packed name columns in parallel — the per-row test only reads
                // the mmap, and rayon's `collect` preserves sequence order, so
                // equal-scoring rows keep the deterministic order the ranking
                // tie-breaks rely on. Only matching rows are ever decoded.
                let matches: Vec<(u32, f32)> = (0..seg.sym_count() as u32)
                    .into_par_iter()
                    .filter_map(|i| {
                        match_symbol(seg.sym_name(i), seg.sym_name_lower(i), &needle, false)
                            .map(|s| (i, s))
                    })
                    .collect();
                for (i, score) in matches {
                    consider(seg, i, score);
                }
            }
        }
        let cmp = |a: &SymbolHit, b: &SymbolHit| {
            b.score
                .partial_cmp(&a.score)
                .unwrap_or(std::cmp::Ordering::Equal)
                .then_with(|| a.name.len().cmp(&b.name.len()))
                .then_with(|| a.path.cmp(&b.path))
        };
        Ok(rank_paginate(hits, cmp, query.offset, query.limit))
    }

    /// Return the symbol outline for a single file (by relative path).
    pub fn outline(&self, rel_path: &str) -> Result<Vec<SymbolHit>> {
        let mut out = Vec::new();
        if let Some(&(si, doc_id)) = self.by_path().get(rel_path) {
            let seg = &self.segments[si];
            if let Some(doc) = seg.doc(doc_id) {
                for sym in seg.doc_syms(doc_id) {
                    out.push(SymbolHit {
                        path: doc.path.clone(),
                        lang: doc.lang.clone(),
                        name: sym.name.clone(),
                        kind: sym.kind.clone(),
                        line_start: sym.line_start,
                        line_end: sym.line_end,
                        container: sym.container.clone(),
                        signature: sym.signature.clone(),
                        score: 1.0,
                    });
                }
            }
        }
        out.sort_by_key(|s| s.line_start);
        Ok(out)
    }

    /// Find references to an identifier (whole-word occurrences across the repo).
    pub fn references(&self, name: &str, limit: usize, offset: usize) -> Result<Vec<SearchHit>> {
        self.search(&SearchQuery {
            pattern: name.to_string(),
            whole_word: true,
            limit,
            offset,
            ..Default::default()
        })
    }

    /// All live symbol definitions whose name matches `name` exactly
    /// (case-sensitive), as `(segment index, symbol index, symbol)` tuples.
    /// O(results) via the per-segment name index — this is the inner loop of
    /// `blast_radius` and `context_pack`, so it must not scan.
    fn defs_by_name(&self, name: &str) -> Vec<(usize, usize, crate::segment::SymbolEntry)> {
        let lower = name.to_ascii_lowercase();
        let mut out = Vec::new();
        for (si, seg) in self.segments.iter().enumerate() {
            for idx in seg.syms_by_lower(&lower) {
                // Cheap exact-case check on the name column before decoding.
                if seg.sym_name(idx) != name {
                    continue;
                }
                if let Some(sym) = seg.sym(idx) {
                    if seg.is_live(sym.doc_id) {
                        out.push((si, idx as usize, sym));
                    }
                }
            }
        }
        out
    }

    /// Number of live call sites targeting `name` (call-graph in-degree),
    /// computed via the per-segment callee-name index (no full ref scan).
    ///
    /// Counts through borrowed row views: the callee name is already known, so
    /// decoding an owned `RefEntry` per site would allocate a `String` only to
    /// drop it. `context_pack` calls this once per surviving candidate.
    fn call_indegree(&self, name: &str) -> u32 {
        let mut n = 0u32;
        for seg in &self.segments {
            for r in seg.ref_views_named(name) {
                if r.kind == RefKind::Call && seg.is_live(r.doc_id) {
                    n += 1;
                }
            }
        }
        n
    }

    /// Resolved references to `name`: its definitions, call sites, and imports,
    /// drawn from the structural reference index (not text matching). Ranked
    /// definitions first, then calls, then imports.
    pub fn references_resolved(&self, name: &str, limit: usize, offset: usize) -> Vec<RefHit> {
        let lower = name.to_ascii_lowercase();
        let mut hits: Vec<RefHit> = Vec::new();
        for seg in &self.segments {
            // Definitions and references are both looked up through the
            // per-segment name indexes (O(results), no table scans).
            let def_rows: Vec<u32> = seg.syms_by_lower(&lower).collect();
            for i in def_rows {
                if seg.sym_name(i) != name {
                    continue;
                }
                let sym = match seg.sym(i) {
                    Some(s) => s,
                    None => continue,
                };
                if seg.is_live(sym.doc_id) {
                    if let Some(doc) = seg.doc(sym.doc_id) {
                        hits.push(RefHit {
                            path: doc.path.clone(),
                            lang: doc.lang.clone(),
                            name: sym.name,
                            kind: "definition".to_string(),
                            line: sym.line_start,
                            column: 1,
                            container: sym.container,
                        });
                    }
                }
            }
            // As in `callers`: references to one name cluster into a few files,
            // so resolve each document's symbol spans once.
            let mut ranges: HashMap<u32, DocSymbolRanges> = HashMap::new();
            let mut container_names: HashMap<u32, Option<String>> = HashMap::new();
            for r in seg.ref_views_named(name) {
                if seg.is_live(r.doc_id) {
                    if let Some(doc) = seg.doc(r.doc_id) {
                        let row = ranges
                            .entry(r.doc_id)
                            .or_insert_with(|| DocSymbolRanges::load(seg, r.doc_id))
                            .enclosing_row(r.line);
                        let container = match row {
                            Some(i) => container_names
                                .entry(i)
                                .or_insert_with(|| seg.sym(i).map(|s| s.name))
                                .clone(),
                            None => None,
                        };
                        hits.push(RefHit {
                            path: doc.path.clone(),
                            lang: doc.lang.clone(),
                            name: r.name.to_string(),
                            kind: r.kind.as_str().to_string(),
                            line: r.line,
                            column: r.column,
                            container,
                        });
                    }
                }
            }
        }
        let rank = |k: &str| match k {
            "definition" => 0,
            "call" => 1,
            _ => 2,
        };
        hits.sort_by(|a, b| {
            rank(&a.kind)
                .cmp(&rank(&b.kind))
                .then_with(|| a.path.cmp(&b.path))
                .then_with(|| a.line.cmp(&b.line))
        });
        paginate(hits, offset, limit)
    }

    /// Call sites *inside* `name`'s body: what `name` calls. Built by locating
    /// the definition(s) of `name` and collecting "call" refs within range.
    pub fn callees(&self, name: &str, limit: usize, offset: usize) -> Vec<CallSite> {
        let mut out: Vec<CallSite> = Vec::new();
        let mut seen: HashSet<(String, String, u32, u32)> = HashSet::new();
        for (si, _, sym) in self.defs_by_name(name) {
            let seg = &self.segments[si];
            let doc = match seg.doc(sym.doc_id) {
                Some(d) => d,
                None => continue,
            };
            for r in seg.doc_ref_views(sym.doc_id) {
                if r.kind == RefKind::Call && r.line >= sym.line_start && r.line <= sym.line_end {
                    let key = (doc.path.clone(), r.name.to_string(), r.line, r.column);
                    if !seen.insert(key) {
                        continue;
                    }
                    out.push(CallSite {
                        caller: Some(name.to_string()),
                        callee: r.name.to_string(),
                        path: doc.path.clone(),
                        lang: doc.lang.clone(),
                        line: r.line,
                        column: r.column,
                    });
                }
            }
        }
        out.sort_by(|a, b| {
            a.callee
                .cmp(&b.callee)
                .then_with(|| a.path.cmp(&b.path))
                .then_with(|| a.line.cmp(&b.line))
        });
        paginate(out, offset, limit)
    }

    /// Call sites that target `name`: who calls it. Each is attributed to its
    /// enclosing caller symbol when one can be determined.
    pub fn callers(&self, name: &str, limit: usize, offset: usize) -> Vec<CallSite> {
        let mut out: Vec<CallSite> = Vec::new();
        for seg in &self.segments {
            // A hot callee's call sites cluster into a few files, so cache each
            // document's symbol spans and each resolved caller name rather than
            // re-deriving them per site.
            let mut ranges: HashMap<u32, DocSymbolRanges> = HashMap::new();
            let mut caller_names: HashMap<u32, Option<String>> = HashMap::new();
            // O(results) via the prebuilt callee-name index instead of a full
            // scan of every ref — this is the inner loop of `blast_radius`.
            for r in seg.ref_views_named(name) {
                if r.kind != RefKind::Call || !seg.is_live(r.doc_id) {
                    continue;
                }
                let doc = match seg.doc(r.doc_id) {
                    Some(d) => d,
                    None => continue,
                };
                let row = ranges
                    .entry(r.doc_id)
                    .or_insert_with(|| DocSymbolRanges::load(seg, r.doc_id))
                    .enclosing_row(r.line);
                let caller = match row {
                    Some(i) => caller_names
                        .entry(i)
                        .or_insert_with(|| seg.sym(i).map(|s| s.name))
                        .clone(),
                    None => None,
                };
                out.push(CallSite {
                    caller,
                    callee: name.to_string(),
                    path: doc.path.clone(),
                    lang: doc.lang.clone(),
                    line: r.line,
                    column: r.column,
                });
            }
        }
        out.sort_by(|a, b| a.path.cmp(&b.path).then_with(|| a.line.cmp(&b.line)));
        paginate(out, offset, limit)
    }

    /// Blast radius: the symbols transitively affected if `name` changes, found
    /// by walking the reverse call graph (callers, then their callers, ...) up
    /// to `depth` hops. Distance 0 is `name`'s own definition(s).
    ///
    /// Resolution is by name, so results are an approximation that can include
    /// unrelated same-named symbols; it is a guide, not a proof.
    pub fn blast_radius(&self, name: &str, depth: u32, limit: usize) -> Vec<ImpactNode> {
        let mut out: Vec<ImpactNode> = Vec::new();
        let mut visited: HashSet<String> = HashSet::new();
        visited.insert(name.to_string());

        // Distance 0: the target's own definitions.
        for (si, _, sym) in self.defs_by_name(name) {
            if let Some(doc) = self.segments[si].doc(sym.doc_id) {
                out.push(ImpactNode {
                    name: sym.name.clone(),
                    kind: sym.kind.clone(),
                    path: doc.path.clone(),
                    lang: doc.lang.clone(),
                    line_start: sym.line_start,
                    line_end: sym.line_end,
                    distance: 0,
                });
            }
        }

        let mut frontier: Vec<String> = vec![name.to_string()];
        'expand: for dist in 1..=depth {
            let mut next: Vec<String> = Vec::new();
            for target in &frontier {
                for site in self.callers(target, usize::MAX, 0) {
                    let caller = match site.caller {
                        Some(c) => c,
                        None => continue,
                    };
                    if !visited.insert(caller.clone()) {
                        continue;
                    }
                    for (si, _, sym) in self.defs_by_name(&caller) {
                        if let Some(doc) = self.segments[si].doc(sym.doc_id) {
                            out.push(ImpactNode {
                                name: sym.name.clone(),
                                kind: sym.kind.clone(),
                                path: doc.path.clone(),
                                lang: doc.lang.clone(),
                                line_start: sym.line_start,
                                line_end: sym.line_end,
                                distance: dist,
                            });
                        }
                    }
                    next.push(caller);
                }
                // Stop expanding entirely once the limit is reached; deeper
                // levels could only produce nodes that get truncated anyway.
                if out.len() >= limit {
                    break 'expand;
                }
            }
            if next.is_empty() {
                break;
            }
            frontier = next;
        }
        out.truncate(limit);
        out
    }

    /// Typed go-to-definition: resolve the identifier at `rel_path:line:col` to
    /// its most likely definition(s), combining scope/usage context with the
    /// global symbol table. Returns candidates ranked by confidence; the unique
    /// best is flagged `resolved`. Falls back to whole-word text hits (marked
    /// unresolved) when the name has no indexed definition.
    pub fn definition(&self, rel_path: &str, line: u32, col: u32) -> Result<Vec<DefHit>> {
        let full = self.resolve_within_root(rel_path)?;
        let source = std::fs::read(&full).map_err(|e| Error::io(&full, e))?;
        let ext = Path::new(rel_path)
            .extension()
            .and_then(|e| e.to_str())
            .unwrap_or("");
        let lang = crate::lang::Language::from_extension(ext);

        let ident = match crate::resolve::identifier_at(lang, &source, line, col) {
            Some(i) => i,
            None => {
                return Err(Error::other(format!(
                    "no identifier at {rel_path}:{line}:{col}"
                )))
            }
        };

        // Imports referenced by the use-file: a name imported here is likely
        // defined elsewhere, which lets us prefer cross-file definitions.
        let imported_here = self.imported_names(rel_path);

        let mut cands: Vec<DefHit> = Vec::new();
        for (si, _, sym) in self.defs_by_name(&ident.name) {
            let seg = &self.segments[si];
            let doc = match seg.doc(sym.doc_id) {
                Some(d) => d,
                None => continue,
            };
            let mut score = 10.0f32 + seg.doc_path_score(sym.doc_id);
            let same_file = doc.path == rel_path;
            if same_file {
                score += 40.0;
            }
            score += 2.0 * shared_prefix_len(rel_path, &doc.path) as f32;
            // Usage-context preference.
            let method_like = matches!(sym.kind.as_str(), "method" | "field" | "property");
            if ident.is_member && method_like {
                score += 25.0;
            } else if !ident.is_member && !method_like {
                score += 8.0;
            }
            if ident.is_call
                && matches!(
                    sym.kind.as_str(),
                    "function" | "method" | "macro" | "constructor"
                )
            {
                score += 6.0;
            }
            if ident.is_type
                && matches!(
                    sym.kind.as_str(),
                    "struct" | "class" | "interface" | "enum" | "type" | "trait" | "record"
                )
            {
                score += 12.0;
            }
            // If the name is imported into the use-file, a cross-file definition
            // is the likely target.
            if imported_here.contains(&ident.name) && !same_file {
                score += 15.0;
            }
            cands.push(DefHit {
                path: doc.path.clone(),
                lang: doc.lang.clone(),
                name: sym.name.clone(),
                kind: sym.kind.clone(),
                line_start: sym.line_start,
                line_end: sym.line_end,
                container: sym.container.clone(),
                signature: sym.signature.clone(),
                score,
                resolved: false,
            });
        }

        if cands.is_empty() {
            // Fallback: whole-word text occurrences, marked unresolved.
            let hits = self.references(&ident.name, 50, 0)?;
            return Ok(hits
                .into_iter()
                .map(|h| DefHit {
                    path: h.path,
                    lang: h.lang,
                    name: ident.name.clone(),
                    kind: "text".to_string(),
                    line_start: h.line,
                    line_end: h.line,
                    container: None,
                    signature: Some(h.text),
                    score: h.score,
                    resolved: false,
                })
                .collect());
        }

        cands.sort_by(|a, b| {
            b.score
                .partial_cmp(&a.score)
                .unwrap_or(std::cmp::Ordering::Equal)
                .then_with(|| a.path.cmp(&b.path))
                .then_with(|| a.line_start.cmp(&b.line_start))
        });
        // Mark the unique best as resolved when it clears the runner-up.
        let unique_top =
            cands.len() == 1 || (cands.len() >= 2 && cands[0].score - cands[1].score >= 12.0);
        if unique_top {
            cands[0].resolved = true;
        }
        Ok(cands)
    }

    /// Resolved references for the identifier at `rel_path:line:col`: its
    /// definitions, call sites, and imports across the repo.
    pub fn references_of(&self, rel_path: &str, line: u32, col: u32) -> Result<Vec<RefHit>> {
        let full = self.resolve_within_root(rel_path)?;
        let source = std::fs::read(&full).map_err(|e| Error::io(&full, e))?;
        let ext = Path::new(rel_path)
            .extension()
            .and_then(|e| e.to_str())
            .unwrap_or("");
        let lang = crate::lang::Language::from_extension(ext);
        let ident = crate::resolve::identifier_at(lang, &source, line, col)
            .ok_or_else(|| Error::other(format!("no identifier at {rel_path}:{line}:{col}")))?;
        Ok(self.references_resolved(&ident.name, usize::MAX, 0))
    }

    /// The set of names imported into `rel_path` (from the reference index).
    fn imported_names(&self, rel_path: &str) -> HashSet<String> {
        let mut out = HashSet::new();
        if let Some(&(si, doc_id)) = self.by_path().get(rel_path) {
            for r in self.segments[si].doc_ref_views(doc_id) {
                if r.kind == RefKind::Import {
                    out.insert(r.name.to_string());
                }
            }
        }
        out
    }

    /// Resolve a caller-supplied path against the project root, rejecting
    /// anything that would escape it: absolute paths (which would make
    /// `root.join(..)` discard the root entirely), `..` traversal, and symlinks
    /// that resolve outside the tree. Returns the absolute path to read.
    fn resolve_within_root(&self, rel_path: &str) -> Result<PathBuf> {
        let candidate = Path::new(rel_path);
        if candidate.is_absolute() {
            return Err(Error::other(format!(
                "path {rel_path:?} must be relative to the project root"
            )));
        }
        // Reject parent/prefix components before touching the filesystem.
        if candidate
            .components()
            .any(|c| matches!(c, Component::ParentDir | Component::Prefix(_)))
        {
            return Err(Error::other(format!(
                "path {rel_path:?} escapes the project root"
            )));
        }
        // Canonicalize both sides so symlinks can't redirect the read outside
        // the root, then require the resolved path to stay under it.
        let root = self
            .paths
            .root
            .canonicalize()
            .map_err(|e| Error::io(&self.paths.root, e))?;
        let full = root.join(candidate);
        let resolved = full.canonicalize().map_err(|e| Error::io(&full, e))?;
        if !resolved.starts_with(&root) {
            return Err(Error::other(format!(
                "path {rel_path:?} escapes the project root"
            )));
        }
        Ok(resolved)
    }

    /// Read a slice of a file with surrounding context lines.
    pub fn read_snippet(
        &self,
        rel_path: &str,
        start_line: u32,
        end_line: u32,
        context: u32,
    ) -> Result<Snippet> {
        let full = self.resolve_within_root(rel_path)?;
        let data = std::fs::read_to_string(&full).map_err(|e| Error::io(&full, e))?;
        let lines: Vec<&str> = data.lines().collect();
        let total = lines.len() as u32;
        let to = end_line.saturating_add(context).min(total.max(1));
        // Clamp the start into the file as well so an out-of-range request never
        // reports a `start_line` past EOF or an inverted (start > end) range.
        let from = start_line
            .saturating_sub(context)
            .max(1)
            .min(total.max(1))
            .min(to);
        let mut body = String::new();
        let mut last = from;
        for ln in from..=to {
            if let Some(text) = lines.get((ln - 1) as usize) {
                if !body.is_empty() {
                    body.push('\n');
                }
                body.push_str(text);
                last = ln;
            }
        }
        Ok(Snippet {
            path: rel_path.to_string(),
            start_line: from,
            end_line: last,
            total_lines: total,
            text: body,
        })
    }

    /// Build a token-budgeted context pack for `task`: the symbols (with
    /// signatures and code snippets) most relevant to the task, ranked by
    /// lexical relevance and call-graph centrality, plus their immediate
    /// dependency neighborhood. Designed to hand an agent exactly the code it
    /// needs without reading whole files.
    pub fn context_pack(&self, task: &str, budget_tokens: u64) -> crate::context::ContextPack {
        use crate::context::{self, ContextPack, PackItem};

        let terms = context::tokenize(task);

        // A candidate symbol (decoded once) with its location and score.
        struct Cand {
            seg: usize,
            sym: crate::segment::SymbolEntry,
            score: f32,
            reason: String,
        }
        // Scan every live document's symbols, in parallel across documents.
        //
        // This sweep touches every symbol in the repository and keeps only the
        // handful that score above zero, so the per-row work has to be as close
        // to free as possible. Two things make it so:
        //
        //  * rows are *borrowed* from the mmap (`doc_sym_views`) instead of
        //    decoded into owned `SymbolEntry`s — only survivors are
        //    materialized, via `to_entry`;
        //  * the per-document part of the score (the path term bonus and
        //    `path_score`) is computed once per file rather than once per
        //    symbol, and each worker reuses one `ScoreScratch` for the
        //    lowercase/tokenize buffers.
        //
        // A document's path matching a task term lifts *every* symbol in that
        // file above zero, so the name column alone can't prune the scan; the
        // cheap-per-row scoring above is what makes the full sweep affordable.
        // Live (segment, doc) pairs, materialized so the parallel scan runs over
        // an indexed iterator: rayon then preserves input order in the collected
        // output, keeping equal-scoring candidates in a deterministic sequence.
        let mut doc_targets: Vec<(usize, u32)> = Vec::new();
        for (si, seg) in self.segments.iter().enumerate() {
            for doc_id in 0..seg.docs.len() as u32 {
                if seg.is_live(doc_id) {
                    doc_targets.push((si, doc_id));
                }
            }
        }

        let mut cands: Vec<Cand> = doc_targets
            .par_iter()
            .flat_map_iter(|&(si, doc_id)| {
                let seg = &self.segments[si];
                let mut out: Vec<Cand> = Vec::new();
                let doc = match seg.doc(doc_id) {
                    Some(d) => d,
                    None => return out.into_iter(),
                };
                let mut scratch = context::ScoreScratch::default();
                let path_bonus = context::path_term_bonus(&doc.path, &terms, &mut scratch);
                for view in seg.doc_sym_views(doc_id) {
                    let score = context::lexical_score_with(
                        view.name,
                        view.kind,
                        view.signature,
                        view.container,
                        path_bonus,
                        &terms,
                        &mut scratch,
                    );
                    if score <= 0.0 {
                        continue;
                    }
                    out.push(Cand {
                        seg: si,
                        sym: view.to_entry(),
                        score,
                        reason: "match".to_string(),
                    });
                }
                out.into_iter()
            })
            .collect();

        // Call-graph centrality and the path preference, applied only to the
        // symbols that already cleared the lexical filter. Kept in this order
        // (centrality, then path) so the accumulated float score is bit-identical
        // to evaluating it inline, and the ranking below cannot shift.
        //
        // A task whose terms appear in a directory name lifts every symbol in
        // those files above zero, so this can run over thousands of candidates,
        // each doing an independent name-index lookup — worth spreading out.
        cands.par_iter_mut().for_each(|c| {
            let deg = self.call_indegree(&c.sym.name) as f32;
            c.score += (1.0 + deg).ln() * 1.5;
            c.score += self.segments[c.seg].doc_path_score(c.sym.doc_id);
        });

        cands.sort_by(|a, b| {
            b.score
                .partial_cmp(&a.score)
                .unwrap_or(std::cmp::Ordering::Equal)
        });

        // Expand the dependency neighborhood of the strongest seeds: include the
        // callees of the top matches so the agent sees what they depend on.
        let mut seen: HashSet<(String, u32)> = HashSet::new();
        for c in &cands {
            seen.insert((c.sym.name.clone(), c.sym.line_start));
        }
        let mut extra: Vec<Cand> = Vec::new();
        for c in cands.iter().take(8) {
            for callee in self.callees(&c.sym.name, 12, 0) {
                for (si2, _, def) in self.defs_by_name(&callee.callee) {
                    let key = (def.name.clone(), def.line_start);
                    if !seen.insert(key) {
                        continue;
                    }
                    extra.push(Cand {
                        seg: si2,
                        sym: def,
                        score: c.score * 0.3,
                        reason: format!("callee of {}", c.sym.name),
                    });
                }
            }
        }
        cands.extend(extra);
        cands.sort_by(|a, b| {
            b.score
                .partial_cmp(&a.score)
                .unwrap_or(std::cmp::Ordering::Equal)
        });

        // Greedily pack within budget. Lines are read once per file through the
        // content cache and split once (cached by content hash), so multiple
        // packed symbols from the same file don't re-read or re-split it.
        //
        // Sizing a candidate requires its file, and a candidate that does not
        // fit is skipped rather than ending the loop (a smaller one further down
        // may still fit), so in the worst case every candidate's file is
        // touched: on a task whose terms appear in directory names that measured
        // 1,477 files and 55 MB read to fill an 8,000-token budget, and it was
        // 90% of the whole operation. So walk the candidates in chunks and warm
        // each chunk's files concurrently before packing it. The greedy pass
        // still sees candidates in exactly the same order, and stopping early
        // wastes at most one chunk of prefetching.
        let mut items: Vec<PackItem> = Vec::new();
        let mut used: u64 = 0;
        let mut truncated = false;
        let mut file_lines: HashMap<u64, Arc<FileLines>> = HashMap::new();
        const MAX_ITEM_LINES: u32 = 60;
        /// Candidates whose files are warmed per round. Large enough to keep the
        /// prefetch wide, small enough that an early stop wastes little.
        const PACK_PREFETCH_CHUNK: usize = 256;
        'packing: for chunk in cands.chunks(PACK_PREFETCH_CHUNK) {
            let mut wanted: Vec<(u64, &str)> = Vec::new();
            let mut seen_hash: HashSet<u64> = HashSet::new();
            for c in chunk {
                if let Some(doc) = self.segments[c.seg].doc(c.sym.doc_id) {
                    if !file_lines.contains_key(&doc.hash) && seen_hash.insert(doc.hash) {
                        wanted.push((doc.hash, doc.path.as_str()));
                    }
                }
            }
            let loaded: Vec<(u64, Arc<FileLines>)> = wanted
                .par_iter()
                .map(|&(hash, path)| {
                    let full = self.paths.root.join(path);
                    let data = self.content.get_or_read(hash, &full);
                    (
                        hash,
                        Arc::new(FileLines::new(data.as_deref().unwrap_or(&[]))),
                    )
                })
                .collect();
            file_lines.extend(loaded);

            for c in chunk {
                let seg = &self.segments[c.seg];
                let sym = &c.sym;
                let doc = match seg.doc(sym.doc_id) {
                    Some(d) => d,
                    None => continue,
                };
                let end = sym
                    .line_end
                    .min(sym.line_start.saturating_add(MAX_ITEM_LINES));
                // Warmed by the prefetch above; the fallback keeps this correct if a
                // candidate's document went missing between the two passes.
                let lines = match file_lines.get(&doc.hash) {
                    Some(l) => l.clone(),
                    None => {
                        let full = self.paths.root.join(&doc.path);
                        let data = self.content.get_or_read(doc.hash, &full);
                        let l = Arc::new(FileLines::new(data.as_deref().unwrap_or(&[])));
                        file_lines.insert(doc.hash, l.clone());
                        l
                    }
                };
                let from = sym.line_start.max(1);
                let to = end.min(lines.len() as u32);
                // Size the snippet before building it. Once the budget is nearly
                // full most candidates no longer fit, and this loop keeps scanning
                // them (a later, smaller one may still fit), so assembling a
                // `String` per rejected candidate was pure waste. Summing the line
                // lengths gives exactly `code.len()`: a separator is added only
                // when something has already been written, so `code_len > 0` stands
                // in for `!code.is_empty()` — which matters when a leading line is
                // itself empty.
                let mut code_len = 0usize;
                for ln in from..=to {
                    if let Some(text) = lines.get((ln - 1) as usize) {
                        if code_len > 0 {
                            code_len += 1;
                        }
                        code_len += text.len();
                    }
                }
                let chars: u64 =
                    code_len as u64 + sym.signature.as_ref().map(|s| s.len() as u64).unwrap_or(0);
                let cost = context::est_tokens(chars).max(1);
                if used + cost > budget_tokens && !items.is_empty() {
                    truncated = true;
                    continue;
                }
                let mut code = String::with_capacity(code_len);
                for ln in from..=to {
                    if let Some(text) = lines.get((ln - 1) as usize) {
                        if !code.is_empty() {
                            code.push('\n');
                        }
                        code.push_str(text);
                    }
                }
                debug_assert_eq!(code.len(), code_len, "snippet cost estimate must be exact");
                used += cost;
                items.push(PackItem {
                    path: doc.path.clone(),
                    lang: doc.lang.clone(),
                    name: sym.name.clone(),
                    kind: sym.kind.clone(),
                    line_start: sym.line_start,
                    line_end: sym.line_end,
                    signature: sym.signature.clone(),
                    snippet_start: from,
                    code,
                    reason: c.reason.clone(),
                    score: c.score,
                });
                if used >= budget_tokens {
                    truncated = truncated || items.len() < cands.len();
                    break 'packing;
                }
            }
        }

        ContextPack {
            task: task.to_string(),
            budget_tokens,
            used_tokens: used,
            truncated,
            items,
        }
    }

    /// Blame a single line: the commit and author that last touched it.
    pub fn blame(&self, rel_path: &str, line: u32) -> Result<crate::git::BlameLine> {
        // Validate the path stays within the project root.
        self.resolve_within_root(rel_path)?;
        crate::git::blame(&self.paths.root, rel_path, line)
    }

    /// The commit history of a symbol: resolve `name` to its definition and list
    /// the commits that touched that line range, newest first.
    pub fn symbol_history(&self, name: &str, limit: usize) -> Result<SymbolHistory> {
        // Prefer the highest-ranked (non-test/vendor) definition.
        let defs = self.defs_by_name(name);
        let best = defs
            .iter()
            .max_by(|a, b| {
                let pa = self.segments[a.0].doc_path_score(a.2.doc_id);
                let pb = self.segments[b.0].doc_path_score(b.2.doc_id);
                pa.partial_cmp(&pb).unwrap_or(std::cmp::Ordering::Equal)
            })
            .ok_or_else(|| Error::other(format!("no definition found for {name:?}")))?;
        let (si, _, sym) = best;
        let si = *si;
        let doc = self.segments[si]
            .doc(sym.doc_id)
            .ok_or_else(|| Error::other("definition document missing".to_string()))?;
        let commits = crate::git::line_history(
            &self.paths.root,
            &doc.path,
            sym.line_start,
            sym.line_end,
            limit,
        )
        .or_else(|_| crate::git::file_history(&self.paths.root, &doc.path, limit))?;
        Ok(SymbolHistory {
            name: name.to_string(),
            path: doc.path.clone(),
            line_start: sym.line_start,
            line_end: sym.line_end,
            commits,
        })
    }

    /// Files changed since `rev`, annotated with the symbols defined in each
    /// (from the index) so an agent sees the affected API surface at a glance.
    pub fn changed_since(&self, rev: &str) -> Result<Vec<ChangedSymbols>> {
        let changed = crate::git::changed_since(&self.paths.root, rev)?;
        let mut out = Vec::with_capacity(changed.len());
        for cf in changed {
            let mut symbols = Vec::new();
            if let Some(&(si, doc_id)) = self.by_path().get(&cf.path) {
                for s in self.segments[si].doc_syms(doc_id) {
                    symbols.push(s.name.clone());
                }
            }
            symbols.sort();
            symbols.dedup();
            out.push(ChangedSymbols {
                path: cf.path,
                status: cf.status,
                symbols,
            });
        }
        Ok(out)
    }

    /// Structural (AST) search: match a tree-sitter query or `$NAME`
    /// meta-variable pattern across documents of one language. Literal tokens in
    /// the pattern prune candidates via the trigram index before parsing.
    pub fn structural_search(
        &self,
        pattern: &str,
        lang: &str,
        limit: usize,
        offset: usize,
    ) -> Result<Vec<StructHit>> {
        let language = crate::lang::Language::from_id(lang)
            .ok_or_else(|| Error::other(format!("unknown language id: {lang:?}")))?;
        if language.grammar().is_none() {
            return Err(Error::other(format!(
                "language {lang} is not parseable for structural search"
            )));
        }
        let compiled = crate::structural::compile(language, pattern)?;

        // Prefilter on the most selective literal anchor, if any.
        let anchor = compiled.anchors.iter().max_by_key(|a| a.len()).cloned();
        let tq = anchor
            .as_ref()
            .map(|a| TrigramQuery::from_literal(a.as_bytes()));

        let mut targets: Vec<(usize, u32)> = Vec::new();
        for (si, seg) in self.segments.iter().enumerate() {
            let candidates = match &tq {
                Some(q) => seg.candidates(q)?,
                None => seg.all_live(),
            };
            for doc_id in candidates.iter() {
                if !seg.is_live(doc_id) {
                    continue;
                }
                match seg.doc(doc_id) {
                    Some(d) if d.lang == lang => targets.push((si, doc_id)),
                    _ => {}
                }
            }
        }

        let root = &self.paths.root;
        let segments = &self.segments;
        let content = &self.content;
        let compiled_ref = &compiled;
        let hits: Vec<StructHit> = targets
            .par_iter()
            .flat_map_iter(|&(si, doc_id)| {
                let seg = &segments[si];
                let doc = match seg.doc(doc_id) {
                    Some(d) => d,
                    None => return Vec::new().into_iter(),
                };
                let full = root.join(&doc.path);
                let data = match content.get_or_read(doc.hash, &full) {
                    Some(d) => d,
                    None => return Vec::new().into_iter(),
                };
                let matches = crate::structural::run(language, compiled_ref, &data);
                let line_starts = line_starts(&data);
                let out: Vec<StructHit> = matches
                    .into_iter()
                    .map(|m| {
                        let li = (m.line_start.saturating_sub(1)) as usize;
                        let text = line_starts
                            .get(li)
                            .map(|_| snippet(line_slice(&data, &line_starts, li)))
                            .unwrap_or_default();
                        StructHit {
                            path: doc.path.clone(),
                            lang: doc.lang.clone(),
                            line_start: m.line_start,
                            line_end: m.line_end,
                            kind: m.kind,
                            text,
                            captures: m.captures,
                        }
                    })
                    .collect();
                out.into_iter()
            })
            .collect();

        let cmp = |a: &StructHit, b: &StructHit| {
            a.path
                .cmp(&b.path)
                .then_with(|| a.line_start.cmp(&b.line_start))
        };
        let mut hits = hits;
        hits.sort_by(cmp);
        Ok(paginate(hits, offset, limit))
    }

    /// Summarize the indexed repository.
    pub fn summary(&self) -> RepoSummary {
        use std::collections::HashMap;
        let mut by_lang: HashMap<String, LangStat> = HashMap::new();
        let mut by_dir: HashMap<String, u64> = HashMap::new();
        let mut files = 0u64;
        let mut bytes = 0u64;
        let mut symbols = 0u64;
        for seg in &self.segments {
            for (doc_id, doc) in seg.docs.iter().enumerate() {
                if !seg.is_live(doc_id as u32) {
                    continue;
                }
                files += 1;
                bytes += doc.size;
                let e = by_lang.entry(doc.lang.clone()).or_default();
                e.files += 1;
                e.bytes += doc.size;
                let dir = doc.path.split('/').next().unwrap_or("").to_string();
                *by_dir.entry(dir).or_default() += 1;
                // Symbol counts come from the doc CSR — no row is decoded.
                symbols += u64::from(seg.doc_sym_count(doc_id as u32));
            }
        }
        let mut languages: Vec<LangStat> = by_lang
            .into_iter()
            .map(|(lang, mut s)| {
                s.lang = lang;
                s
            })
            .collect();
        // Break count ties by name. Both lists are collected from a `HashMap`,
        // whose iteration order varies per process, and a stable sort preserved
        // it — so `summary` returned a different ordering on every run, and
        // because `top_dirs` is truncated, a different *set* of directories too.
        languages.sort_by(|a, b| b.files.cmp(&a.files).then_with(|| a.lang.cmp(&b.lang)));
        let mut top_dirs: Vec<(String, u64)> = by_dir.into_iter().collect();
        top_dirs.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
        top_dirs.truncate(15);
        RepoSummary {
            files,
            bytes,
            symbols,
            segments: self.segments.len(),
            languages,
            top_dirs: top_dirs
                .into_iter()
                .map(|(name, files)| DirStat { name, files })
                .collect(),
        }
    }
}

/// A file slice with context, returned by [`Searcher::read_snippet`].
///
/// The body is a single `text` blob (lines joined by `\n`) rather than an array
/// of per-line objects: line N is `start_line + i` for the i-th line, so the
/// numbers are implicit and never repeated on the wire. This keeps the payload
/// compact for agents while staying exactly reconstructable.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Snippet {
    pub path: String,
    pub start_line: u32,
    pub end_line: u32,
    pub total_lines: u32,
    pub text: String,
}

/// Repository summary returned by [`Searcher::summary`].
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct RepoSummary {
    pub files: u64,
    pub bytes: u64,
    pub symbols: u64,
    pub segments: usize,
    pub languages: Vec<LangStat>,
    pub top_dirs: Vec<DirStat>,
}

#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct LangStat {
    pub lang: String,
    pub files: u64,
    pub bytes: u64,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct DirStat {
    pub name: String,
    pub files: u64,
}

/// Read a single candidate file and collect matching lines. Matches are found
/// over the whole buffer (so regexes may span lines), mapped to line numbers,
/// then ranked so the highest-scored matches survive `max_per_file` truncation.
#[allow(clippy::too_many_arguments)] // hot path; threading a struct adds churn without clarity
fn verify_doc(
    seg: &Segment,
    doc_id: u32,
    root: &Path,
    content: &ContentCache,
    matcher: &Matcher,
    max_per_file: usize,
    whole_word: bool,
    exhaustive: bool,
) -> Vec<SearchHit> {
    let doc = match seg.doc(doc_id) {
        Some(d) => d,
        None => return Vec::new(),
    };
    let full = root.join(&doc.path);
    let data = match content.get_or_read(doc.hash, &full) {
        Some(d) => d,
        None => return Vec::new(),
    };

    // Exhaustive search lifts the pathological-input cap so no match is dropped.
    let cap = if exhaustive {
        usize::MAX
    } else {
        PER_FILE_MATCH_CAP
    };
    let matches = matcher.match_starts(&data, whole_word, cap);
    if matches.is_empty() {
        return Vec::new();
    }

    let line_starts = line_starts(&data);
    let sym_lines = symbol_lines(seg, doc_id);
    let base = seg.doc_path_score(doc_id);

    let mut out = Vec::new();
    let mut last_line = 0u32;
    for (start, _end) in matches {
        let li = line_of(start, &line_starts);
        let line_no = li as u32 + 1;
        // One hit per line; matches are in ascending offset order.
        if line_no == last_line {
            continue;
        }
        last_line = line_no;
        let col = (start - line_starts[li]) as u32 + 1;
        let line_bytes = line_slice(&data, &line_starts, li);
        let mut score = 1.0 + base;
        if sym_lines.binary_search(&line_no).is_ok() {
            score += 3.0;
        }
        out.push(SearchHit {
            path: doc.path.clone(),
            lang: doc.lang.clone(),
            line: line_no,
            column: col,
            text: snippet(line_bytes),
            score,
        });
    }

    // Keep the highest-scored matches when a file has more than the cap.
    // Exhaustive mode keeps every line.
    if !exhaustive && out.len() > max_per_file {
        out.sort_by(|a, b| {
            b.score
                .partial_cmp(&a.score)
                .unwrap_or(std::cmp::Ordering::Equal)
                .then_with(|| a.line.cmp(&b.line))
        });
        out.truncate(max_per_file);
    }
    out
}

/// A file's text together with the byte span of each of its lines, so snippets
/// can be sliced out without allocating a `String` per line.
///
/// Context packing needs the lines of every candidate file, and a candidate that
/// does not fit the remaining budget is skipped — but the file still had to be
/// split to find that out. Splitting into `Vec<String>` cost one allocation per
/// line of every file touched (thousands per file on a large source tree); this
/// costs one copy of the file plus one span table.
struct FileLines {
    text: String,
    /// `(start, end)` byte offsets within `text`, excluding line terminators.
    spans: Vec<(usize, usize)>,
}

impl FileLines {
    fn new(data: &[u8]) -> FileLines {
        // Source files are almost always valid UTF-8, and validating is the bulk
        // of the conversion for a multi-MB candidate set. `simdutf8` checks that
        // vectorized; lossy conversion of already-valid input yields the same
        // bytes, so the fast path is exactly equivalent.
        let text = match simdutf8::basic::from_utf8(data) {
            Ok(s) => s.to_owned(),
            Err(_) => String::from_utf8_lossy(data).into_owned(),
        };
        // Derive the spans from `str::lines` itself rather than reimplementing
        // its rules (`\n` vs `\r\n`, optional final terminator): each yielded
        // slice points into `text`, so its offset is exact by construction.
        //
        // Offsets are `usize`, not `u32`: `max_file_size` is configurable
        // (`GREPLM_MAX_FILE_SIZE`) and files are re-read at query time, so a
        // 4 GiB+ file is reachable, and truncating an offset would produce an
        // inverted range and panic on the slice.
        let base = text.as_ptr() as usize;
        let spans = text
            .lines()
            .map(|line| {
                let start = line.as_ptr() as usize - base;
                (start, start + line.len())
            })
            .collect();
        FileLines { text, spans }
    }

    fn len(&self) -> usize {
        self.spans.len()
    }

    fn get(&self, i: usize) -> Option<&str> {
        self.spans.get(i).map(|&(s, e)| &self.text[s..e])
    }
}

/// The symbol line spans of one document, in storage order, so that many
/// positions can be resolved against the same document without re-reading its
/// line column each time.
///
/// A hot callee has thousands of call sites concentrated in a few files, and
/// attributing each one to its enclosing caller is the inner loop of `callers`
/// and therefore of `blast_radius`. Reading the document's spans once turns that
/// from O(sites x symbols-per-document) into O(symbols-per-document + sites).
struct DocSymbolRanges {
    /// `(line_start, line_end, row id)`, in storage order.
    rows: Vec<(u32, u32, u32)>,
}

impl DocSymbolRanges {
    fn load(seg: &Segment, doc_id: u32) -> DocSymbolRanges {
        let rows = seg
            .doc_sym_rows(doc_id)
            .filter_map(|i| seg.sym_view(i).map(|v| (v.line_start, v.line_end, i)))
            .collect();
        DocSymbolRanges { rows }
    }

    /// Row id of the innermost symbol whose range contains `line`.
    ///
    /// Among equally tight ranges the earliest row in storage order wins, which
    /// is the tie-break the original per-call scan had.
    fn enclosing_row(&self, line: u32) -> Option<u32> {
        let mut best: Option<(u32, u32)> = None; // (row id, span)
        for &(start, end, i) in &self.rows {
            if start <= line && line <= end {
                let span = end - start;
                match best {
                    Some((_, best_span)) if best_span <= span => {}
                    _ => best = Some((i, span)),
                }
            }
        }
        best.map(|(i, _)| i)
    }
}

/// Build the path -> (segment index, doc id) lookup over live documents.
/// A path is live in exactly one segment (changed files tombstone the old
/// copy), so the map is unambiguous.
fn build_path_index(segments: &[Segment]) -> HashMap<String, (usize, u32)> {
    let mut map = HashMap::new();
    for (si, seg) in segments.iter().enumerate() {
        for (doc_id, doc) in seg.docs.iter().enumerate() {
            let doc_id = doc_id as u32;
            if seg.is_live(doc_id) {
                map.insert(doc.path.clone(), (si, doc_id));
            }
        }
    }
    map
}

/// Byte offsets at which each line begins (index 0 is the start of the file).
fn line_starts(data: &[u8]) -> Vec<usize> {
    let mut starts = Vec::with_capacity(64);
    starts.push(0usize);
    for p in memchr::memchr_iter(b'\n', data) {
        starts.push(p + 1);
    }
    starts
}

/// Zero-based line index containing byte offset `off`.
fn line_of(off: usize, starts: &[usize]) -> usize {
    // Greatest line start that is <= off.
    starts.partition_point(|&s| s <= off).saturating_sub(1)
}

/// The bytes of line `li` (without the trailing newline).
fn line_slice<'a>(data: &'a [u8], starts: &[usize], li: usize) -> &'a [u8] {
    let begin = starts[li];
    let end = if li + 1 < starts.len() {
        starts[li + 1].saturating_sub(1)
    } else {
        data.len()
    };
    &data[begin..end.min(data.len())]
}

/// ASCII-case-insensitive substring test. `needle` must already be ASCII
/// lowercase. Avoids materializing a lowercased copy of `hay`, which is what
/// made [`path_score`] too expensive to call per hit.
///
/// Naive offset scan: both strings are short (a repo-relative path and a
/// handful of literals), so this beats any setup cost.
fn contains_ascii_ci(hay: &str, needle: &[u8]) -> bool {
    let h = hay.as_bytes();
    if needle.len() > h.len() {
        return false;
    }
    (0..=h.len() - needle.len()).any(|i| {
        h[i..i + needle.len()]
            .iter()
            .zip(needle)
            .all(|(a, b)| a.to_ascii_lowercase() == *b)
    })
}

/// Ranking adjustment based on the file path: prefer shallow paths and
/// non-generated/non-test files.
///
/// Called once per hit, per ranked candidate and per scored symbol, so it must
/// not allocate — it used to build a lowercased copy of the path.
///
/// The test-path check needs just two probes, not five: `/tests/`, `__tests__`
/// and `.test.` all contain `test`, so they can only match when `test` does.
pub(crate) fn path_score(path: &str) -> f32 {
    let mut s = 0.0f32;
    let depth = memchr::memchr_iter(b'/', path.as_bytes()).count() as f32;
    s -= depth * 0.05;
    if contains_ascii_ci(path, b"test") || contains_ascii_ci(path, b".spec.") {
        s -= 1.0;
    }
    if contains_ascii_ci(path, b"/vendor/")
        || contains_ascii_ci(path, b"/generated/")
        || contains_ascii_ci(path, b".min.")
    {
        s -= 1.5;
    }
    s
}

/// Sorted, deduplicated set of lines on which `doc_id` defines a symbol, used
/// to bonus-score matches that land on a definition.
///
/// Runs for every file that produced a match, so it reads the line column
/// through borrowed views rather than materializing each symbol's strings. A
/// sorted `Vec` beats a `HashSet` here: the counts are small and it is one
/// allocation instead of a table plus hashing per row.
fn symbol_lines(seg: &Segment, doc_id: u32) -> Vec<u32> {
    let mut lines: Vec<u32> = seg.doc_sym_views(doc_id).map(|s| s.line_start).collect();
    lines.sort_unstable();
    lines.dedup();
    lines
}

fn match_symbol(name: &str, lower: &str, needle: &str, exact: bool) -> Option<f32> {
    if exact {
        return if lower == needle { Some(100.0) } else { None };
    }
    if lower == needle {
        Some(100.0)
    } else if lower.starts_with(needle) {
        Some(70.0)
    } else if acronym_eq(name, needle) {
        // e.g. "lc" matches loadConfig / load_config.
        Some(60.0)
    } else if lower.contains(needle) {
        Some(50.0)
    } else if is_subsequence(needle, lower) {
        Some(30.0)
    } else {
        None
    }
}

/// True when `needle` equals the acronym of `name` — the lowercased first
/// letter of each identifier token, split on camelCase and snake/kebab (so "lc"
/// matches `loadConfig` and `load_config`).
///
/// Streams the comparison instead of building the acronym. The fuzzy symbol
/// scan reaches this branch for nearly every symbol in the repository (only
/// exact and prefix matches short-circuit before it), so the old version's
/// `Vec<String>` of tokens per symbol dominated that path.
fn acronym_eq(name: &str, needle: &str) -> bool {
    let mut want = needle.chars();
    let mut prev_lower = false;
    // Whether we are inside a token; mirrors the tokenizer's `!cur.is_empty()`.
    let mut open = false;
    for ch in name.chars() {
        if ch == '_' || ch == '-' || ch == ' ' {
            open = false;
            prev_lower = false;
            continue;
        }
        if ch.is_uppercase() && prev_lower && open {
            open = false;
        }
        if !open {
            open = true;
            // This character starts a token, so the first `char` of its
            // lowercased form is the acronym letter this token contributes.
            let c = match ch.to_lowercase().next() {
                Some(c) => c,
                None => continue,
            };
            if want.next() != Some(c) {
                return false;
            }
        }
        prev_lower = ch.is_lowercase() || ch.is_numeric();
    }
    // Every token consumed exactly one needle character, and none are left.
    want.next().is_none()
}

/// Rank `items` best-first and apply offset/limit. Uses a partial selection so
/// we only fully sort the `offset + limit` items we actually return.
fn rank_paginate<T, F>(mut items: Vec<T>, cmp: F, offset: usize, limit: usize) -> Vec<T>
where
    F: Fn(&T, &T) -> std::cmp::Ordering,
{
    let need = offset.saturating_add(limit);
    if need == 0 {
        return Vec::new();
    }
    if need < items.len() {
        items.select_nth_unstable_by(need - 1, |a, b| cmp(a, b));
        items.truncate(need);
    }
    items.sort_by(|a, b| cmp(a, b));
    if offset >= items.len() {
        return Vec::new();
    }
    items.drain(0..offset);
    items.truncate(limit);
    items
}

/// Index-free fallback search: walk the working tree and scan every file with
/// the matcher, with no trigram prefilter. Used when the index is missing or
/// errors, so `search` still returns grep-equivalent results instead of failing.
/// Honors the same `lang`/`path` filters, `exhaustive` mode, and ordering as the
/// indexed path. Slower (reads every candidate file) but correct and complete.
pub fn grep_walk(paths: &Paths, config: &Config, query: &SearchQuery) -> Result<Vec<SearchHit>> {
    if query.pattern.is_empty() {
        return Ok(Vec::new());
    }
    let matcher = Matcher::build(query)?;
    let walked = crate::walk::walk(paths, config)?;
    let path_filter = query.path.as_deref();
    let lang_filter = query.lang.as_deref();
    let max_per_file = query.max_per_file;
    let whole_word = query.whole_word;
    let exhaustive = query.exhaustive;
    let index_binary = config.index_binary;
    let cap = if exhaustive {
        usize::MAX
    } else {
        PER_FILE_MATCH_CAP
    };

    let mut hits: Vec<SearchHit> = walked
        .entries
        .par_iter()
        .flat_map_iter(|e| {
            if path_filter.is_some_and(|pf| !e.rel.contains(pf)) {
                return Vec::new().into_iter();
            }
            let ext = e
                .path
                .extension()
                .and_then(|x| x.to_str())
                .unwrap_or("")
                .to_ascii_lowercase();
            let lang_id = Language::from_extension(&ext).id().to_string();
            if lang_filter.is_some_and(|lf| lang_id != lf) {
                return Vec::new().into_iter();
            }
            let data = match std::fs::read(&e.path) {
                Ok(d) => d,
                Err(_) => return Vec::new().into_iter(),
            };
            if !index_binary && memchr::memchr(0, &data).is_some() {
                return Vec::new().into_iter();
            }
            let matches = matcher.match_starts(&data, whole_word, cap);
            if matches.is_empty() {
                return Vec::new().into_iter();
            }
            let starts = line_starts(&data);
            let base = path_score(&e.rel);
            let mut out = Vec::new();
            let mut last_line = 0u32;
            for (start, _end) in matches {
                let li = line_of(start, &starts);
                let line_no = li as u32 + 1;
                if line_no == last_line {
                    continue;
                }
                last_line = line_no;
                let col = (start - starts[li]) as u32 + 1;
                out.push(SearchHit {
                    path: e.rel.clone(),
                    lang: lang_id.clone(),
                    line: line_no,
                    column: col,
                    text: snippet(line_slice(&data, &starts, li)),
                    score: 1.0 + base,
                });
            }
            if !exhaustive && out.len() > max_per_file {
                out.sort_by(|a, b| {
                    b.score
                        .partial_cmp(&a.score)
                        .unwrap_or(std::cmp::Ordering::Equal)
                        .then_with(|| a.line.cmp(&b.line))
                });
                out.truncate(max_per_file);
            }
            out.into_iter()
        })
        .collect();

    if exhaustive {
        hits.sort_by(|a, b| {
            a.path
                .cmp(&b.path)
                .then_with(|| a.line.cmp(&b.line))
                .then_with(|| a.column.cmp(&b.column))
        });
        return Ok(hits);
    }
    let cmp = |a: &SearchHit, b: &SearchHit| {
        b.score
            .partial_cmp(&a.score)
            .unwrap_or(std::cmp::Ordering::Equal)
            .then_with(|| a.path.cmp(&b.path))
            .then_with(|| a.line.cmp(&b.line))
    };
    Ok(rank_paginate(hits, cmp, query.offset, query.limit))
}

/// Number of leading path components shared by two relative paths.
fn shared_prefix_len(a: &str, b: &str) -> usize {
    a.split('/')
        .zip(b.split('/'))
        .take_while(|(x, y)| x == y)
        .count()
}

/// Apply offset/limit to an already-ordered vector.
fn paginate<T>(mut items: Vec<T>, offset: usize, limit: usize) -> Vec<T> {
    if offset >= items.len() {
        return Vec::new();
    }
    items.drain(0..offset);
    items.truncate(limit);
    items
}

fn is_subsequence(needle: &str, haystack: &str) -> bool {
    if needle.is_empty() {
        return true;
    }
    let mut chars = needle.chars();
    let mut cur = chars.next();
    for h in haystack.chars() {
        if let Some(c) = cur {
            if c == h {
                cur = chars.next();
            }
        } else {
            break;
        }
    }
    cur.is_none()
}

/// Trim and bound a matched line for display.
fn snippet(line: &[u8]) -> String {
    let s = String::from_utf8_lossy(line);
    let trimmed = s.trim_end();
    const MAX: usize = 320;
    if trimmed.len() > MAX {
        let mut end = MAX;
        while !trimmed.is_char_boundary(end) {
            end -= 1;
        }
        format!("{}…", &trimmed[..end])
    } else {
        trimmed.to_string()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// The allocating acronym the fuzzy matcher used before `acronym_eq`, kept
    /// as the reference definition of the behavior.
    fn reference_acronym(s: &str) -> String {
        crate::context::split_identifier(s)
            .iter()
            .filter_map(|t| t.chars().next())
            .collect()
    }

    /// Identifiers covering every tokenizer branch, plus the non-ASCII cases
    /// where `to_lowercase` can expand a single `char`.
    const NAMES: &[&str] = &[
        "",
        "x",
        "flush",
        "loadConfig",
        "load_config",
        "LoadConfig",
        "HTTPServer",
        "parseHTTP2Frame",
        "v2Handler",
        "vfs_read",
        "__init_waitqueue_head",
        "trailing__",
        "a__b",
        "kebab-case-name",
        "with space",
        "snake_And_Camel",
        "ALLCAPS",
        "ÄÖÜ_grüß",
        "İstanbul",
        "page_cache_sync_readahead",
    ];

    /// `acronym_eq` must agree with the allocating implementation for every
    /// name, both on its own acronym and on near-miss needles.
    #[test]
    fn acronym_eq_matches_reference() {
        for name in NAMES {
            let want = reference_acronym(name);
            assert!(
                acronym_eq(name, &want),
                "{name:?} should match its own acronym {want:?}"
            );
            // Perturbations that must not match.
            let mut wrong = vec![format!("{want}z"), format!("z{want}")];
            if !want.is_empty() {
                wrong.push(want[..want.len() - 1].to_string());
                wrong.push(want.to_uppercase());
            }
            for w in wrong {
                if w == want {
                    continue;
                }
                assert_eq!(
                    acronym_eq(name, &w),
                    reference_acronym(name) == w,
                    "{name:?} vs needle {w:?}"
                );
            }
        }
    }

    /// Cross-check against every other name's acronym, so a needle that happens
    /// to collide is treated identically by both implementations.
    #[test]
    fn acronym_eq_agrees_on_all_pairs() {
        for name in NAMES {
            for other in NAMES {
                let needle = reference_acronym(other);
                assert_eq!(
                    acronym_eq(name, &needle),
                    reference_acronym(name) == needle,
                    "name {name:?} vs needle {needle:?}"
                );
            }
        }
    }

    /// The original `path_score`: one lowercased copy, five test-path probes,
    /// three vendor probes. Kept as the reference definition of the scoring.
    fn reference_path_score(path: &str) -> f32 {
        let mut s = 0.0f32;
        let depth = path.matches('/').count() as f32;
        s -= depth * 0.05;
        let lower = path.to_ascii_lowercase();
        if lower.contains("test")
            || lower.contains("/tests/")
            || lower.contains("__tests__")
            || lower.contains(".test.")
            || lower.contains(".spec.")
        {
            s -= 1.0;
        }
        if lower.contains("/vendor/") || lower.contains("/generated/") || lower.contains(".min.") {
            s -= 1.5;
        }
        s
    }

    /// The allocation-free rewrite must score every path exactly as before,
    /// including the collapsed test-path disjunction and ASCII case folding.
    #[test]
    fn path_score_matches_reference() {
        let paths = [
            "",
            "a.c",
            "fs/read_write.c",
            "a/b/c/d/e/f/g.rs",
            "src/tests/mod.rs",
            "src/TESTS/mod.rs",
            "Test.java",
            "TEST.java",
            "foo/__tests__/bar.js",
            "foo/bar.test.ts",
            "foo/bar.spec.ts",
            "foo/bar.SPEC.ts",
            "protest/attestation.c",
            "third_party/vendor/lib.go",
            "third_party/VENDOR/lib.go",
            "out/generated/api.rs",
            "web/app.min.js",
            "web/app.MIN.js",
            "vendor/nested/test/.spec.x",
            "no_slashes_or_markers",
            "spec.rs",
            ".spec.",
            "tes",
            "t",
        ];
        for p in paths {
            assert_eq!(
                path_score(p),
                reference_path_score(p),
                "path_score mismatch for {p:?}"
            );
        }
    }

    /// `contains_ascii_ci` must agree with lowercase-then-`contains`.
    #[test]
    fn contains_ascii_ci_matches_std() {
        let hays = [
            "", "a", "Test", "tEsT", "xxtestxx", "TES", "/Vendor/", ".MIN.", "aaa",
        ];
        for h in hays {
            for n in [
                &b"test"[..],
                b".spec.",
                b"/vendor/",
                b"/generated/",
                b".min.",
                b"a",
            ] {
                let needle = std::str::from_utf8(n).unwrap();
                assert_eq!(
                    contains_ascii_ci(h, n),
                    h.to_ascii_lowercase().contains(needle),
                    "{h:?} contains {needle:?}"
                );
            }
        }
    }

    /// `FileLines` must be indistinguishable from the
    /// `String::from_utf8_lossy(..).lines().map(to_string).collect()` it
    /// replaced — including CRLF, blank lines, a missing final terminator, and
    /// invalid UTF-8 (which lossy conversion turns into U+FFFD, changing byte
    /// lengths and therefore the packing cost).
    #[test]
    fn file_lines_match_str_lines() {
        let cases: &[&[u8]] = &[
            b"",
            b"\n",
            b"a",
            b"a\n",
            b"a\nb",
            b"a\nb\n",
            b"\na",
            b"a\n\nb\n",
            b"a\r\nb\r\n",
            b"a\r\nb",
            b"a\r",
            b"\r\n\r\n",
            b"no terminator at all",
            b"trailing blank lines\n\n\n",
            b"tabs\tand  spaces\n  indented\n",
            &[0xC3, 0x28, b'\n', b'o', b'k'],        // invalid UTF-8
            &[b'a', b'\n', 0xFF, 0xFE, b'\n', b'z'], // invalid UTF-8
            "héllo\nwörld\n".as_bytes(),             // multibyte
        ];
        for data in cases {
            let want: Vec<String> = String::from_utf8_lossy(data)
                .lines()
                .map(|s| s.to_string())
                .collect();
            let got = FileLines::new(data);
            assert_eq!(got.len(), want.len(), "line count for {data:?}");
            for (i, line) in want.iter().enumerate() {
                assert_eq!(got.get(i), Some(line.as_str()), "line {i} of {data:?}");
            }
            assert_eq!(got.get(want.len()), None, "past-the-end for {data:?}");
        }
    }

    /// The enclosing-symbol rule: innermost (tightest) range wins, and among
    /// equally tight ranges the earliest row in storage order wins. Both
    /// `callers` and `references_resolved` attribute references with this, so
    /// its tie-break decides user-visible output.
    #[test]
    fn enclosing_row_picks_innermost_then_earliest() {
        // Row 0 spans the whole file, row 1 is a method inside it, rows 2 and 3
        // are equally tight and overlapping, row 4 is a single line.
        let r = DocSymbolRanges {
            rows: vec![
                (1, 100, 0),
                (10, 20, 1),
                (30, 40, 2),
                (30, 40, 3),
                (50, 50, 4),
            ],
        };
        assert_eq!(
            r.enclosing_row(5),
            Some(0),
            "only the outer range contains it"
        );
        assert_eq!(
            r.enclosing_row(15),
            Some(1),
            "innermost wins over the outer"
        );
        assert_eq!(r.enclosing_row(35), Some(2), "earliest of two equal spans");
        assert_eq!(
            r.enclosing_row(50),
            Some(4),
            "single-line range is tightest"
        );
        assert_eq!(r.enclosing_row(200), None, "outside every range");
        assert_eq!(DocSymbolRanges { rows: vec![] }.enclosing_row(1), None);
        // Boundaries are inclusive on both ends.
        assert_eq!(r.enclosing_row(10), Some(1));
        assert_eq!(r.enclosing_row(20), Some(1));
        assert_eq!(r.enclosing_row(9), Some(0));
    }

    /// The documented behavior of the acronym branch.
    #[test]
    fn acronym_matches_camel_and_snake() {
        assert!(acronym_eq("loadConfig", "lc"));
        assert!(acronym_eq("load_config", "lc"));
        assert!(acronym_eq("vfs_read", "vr"));
        assert!(!acronym_eq("loadConfig", "l"));
        assert!(!acronym_eq("loadConfig", "lcx"));
    }
}