lean_ctx_server/tools/ctx_search/

implementation.rs

// SPDX-License-Identifier: Apache-2.0
use std::collections::HashSet;
use std::path::Path;
use std::path::PathBuf;
use std::time::{Duration, Instant};

use glob::Pattern;
use ignore::WalkBuilder;
use regex::RegexBuilder;

use crate::tools::CrpMode;
use lean_ctx::core::protocol;
use lean_ctx::core::symbol_map::{self, SymbolMap};
use lean_ctx::core::tokens::count_tokens;

pub(crate) use lean_ctx::core::search_walk::{
    MAX_FILE_SIZE, MAX_WALK_DEPTH, is_binary_ext, is_generated_file,
};
/// Size cap when `path` names one regular file (#1917). [`MAX_FILE_SIZE`]
/// bounds a directory walk; a file the caller named explicitly is the whole
/// question, so skipping it would turn "not searched" into "0 matches". This
/// cap only guards memory against pathological inputs.
const MAX_EXPLICIT_FILE_SIZE: u64 = 64 * 1024 * 1024;
/// How many size-skipped files the notes name before collapsing to `+N more`.
const MAX_NAMED_SKIPS: usize = 3;
const MAX_MATCH_LINE_WIDTH: usize = 150;

/// Modeled baseline for the *estimated* savings series (GL #479 D1): a native
/// agent grep tool ships matches with surrounding context lines, per-file
/// headers and line numbers, which is roughly 2.5x the tokens of the bare
/// match lines lean-ctx observes. This factor is a documented model
/// assumption — it feeds `stats.json` ("estimated") only. The signed savings
/// ledger ("verified") records `observed_tokens` without any factor applied.
pub const NATIVE_GREP_BASELINE_FACTOR: f64 = 2.5;

/// Result of a search: the rendered output plus both baseline figures.
pub struct SearchOutcome {
    /// Rendered, compressed search output.
    pub text: String,
    /// Modeled native-tool baseline (`observed_tokens` x [`NATIVE_GREP_BASELINE_FACTOR`]).
    /// Feeds the estimated stats series.
    pub modeled_baseline: usize,
    /// Tokens actually measured in the raw match lines — no model applied.
    /// Feeds the verified savings ledger.
    pub observed_tokens: usize,
    /// The search itself failed (pattern refused, invalid regex, missing or
    /// refused root) and `text` is its error message. This is the signal
    /// callers act on — never the wording of `text`: a search whose output
    /// merely begins with "ERROR" is a result, and "0 matches" is one too.
    pub failed: bool,
    /// Files the secret-path boundary kept out of the scan (the result names
    /// them). The `ctx_search` handler records the count once per call.
    pub secret_paths_withheld: usize,
}

impl SearchOutcome {
    /// A search that did not run: `text` is the error message.
    fn error(text: String) -> Self {
        Self {
            text,
            modeled_baseline: 0,
            observed_tokens: 0,
            failed: true,
            secret_paths_withheld: 0,
        }
    }

    /// A search that ran and returned no match lines: `text` is the report.
    fn without_matches(text: String) -> Self {
        Self {
            text,
            modeled_baseline: 0,
            observed_tokens: 0,
            failed: false,
            secret_paths_withheld: 0,
        }
    }

    fn from_observed(text: String, observed_tokens: usize) -> Self {
        let modeled = (observed_tokens as f64 * NATIVE_GREP_BASELINE_FACTOR).ceil() as usize;
        Self {
            text,
            modeled_baseline: modeled.max(observed_tokens),
            observed_tokens,
            failed: false,
            secret_paths_withheld: 0,
        }
    }

    fn withholding(mut self, secret_paths: usize) -> Self {
        self.secret_paths_withheld = secret_paths;
        self
    }
}

/// Wall-clock budget for a single `ctx_search` call. The regular-file guard in
/// the read loop removes the known infinite block — `read_to_string` on a
/// FIFO/socket/device (#336) — while this deadline is the backstop for any
/// *other* pathological case (a gigantic corpus, a stuck network mount): the
/// tool returns partial results with a hint instead of appearing to hang.
/// Tunable via `LEAN_CTX_SEARCH_DEADLINE_MS` (`0` disables). Default 10s.
fn search_deadline() -> Option<Duration> {
    const DEFAULT_MS: u64 = 10_000;
    let ms = std::env::var("LEAN_CTX_SEARCH_DEADLINE_MS")
        .ok()
        .and_then(|v| v.trim().parse::<u64>().ok())
        .unwrap_or(DEFAULT_MS);
    (ms > 0).then(|| Duration::from_millis(ms))
}

/// Back-compat shim: the pre-#870 8-arg entry point. Delegates to
/// [`handle_filtered`] with no exclude filters. New callers pass the two
/// `exclude` args directly.
#[allow(clippy::too_many_arguments)]
pub fn handle(
    pattern: &str,
    dir: &str,
    include: Option<&str>,
    max_results: usize,
    crp_mode: CrpMode,
    respect_gitignore: bool,
    allow_secret_paths: bool,
    anchored: bool,
) -> SearchOutcome {
    handle_filtered(
        pattern,
        dir,
        include,
        max_results,
        crp_mode,
        respect_gitignore,
        allow_secret_paths,
        anchored,
        None,
        None,
    )
}

/// Searches files for a regex pattern with compressed output and monorepo scope hints.
///
/// `anchored` (opt-in, #1008) appends a `:hh` line-hash to every match
/// (`path:line:hh content`) so a hit can be edited directly with `ctx_patch`
/// without a separate `ctx_read(mode="anchored")`. Default output is byte-for-byte
/// unchanged (#498).
///
/// `exclude` (path glob, complement of `include`) and `exclude_pattern` (regex
/// on result lines, like `grep -v`) are the negative filters added in #870.
///
/// A pattern that is not valid regex syntax (`foo(`, `a[0`, `fn x(&self`) is
/// almost always code the agent wants to find verbatim, so it is searched
/// literally with a one-line note instead of failing the call. Size-limit
/// errors still fail: escaping cannot make an oversized pattern smaller.
#[allow(clippy::too_many_arguments)]
pub fn handle_filtered(
    pattern: &str,
    dir: &str,
    include: Option<&str>,
    max_results: usize,
    crp_mode: CrpMode,
    respect_gitignore: bool,
    allow_secret_paths: bool,
    anchored: bool,
    exclude: Option<&str>,
    exclude_pattern: Option<&str>,
) -> SearchOutcome {
    let literal = matches!(regex::Regex::new(pattern), Err(regex::Error::Syntax(_)))
        .then(|| regex::escape(pattern));
    let mut outcome = search_compiled_pattern(
        literal.as_deref().unwrap_or(pattern),
        dir,
        include,
        max_results,
        crp_mode,
        respect_gitignore,
        allow_secret_paths,
        anchored,
        exclude,
        exclude_pattern,
    );
    if literal.is_some() && !outcome.text.starts_with("ERROR:") {
        outcome.text = format!(
            "note: '{pattern}' is not valid regex — searched for it literally.\n{}",
            outcome.text
        );
    }
    outcome
}

#[allow(clippy::too_many_arguments)]
fn search_compiled_pattern(
    pattern: &str,
    dir: &str,
    include: Option<&str>,
    max_results: usize,
    _crp_mode: CrpMode,
    respect_gitignore: bool,
    allow_secret_paths: bool,
    anchored: bool,
    exclude: Option<&str>,
    exclude_pattern: Option<&str>,
) -> SearchOutcome {
    // `include` is a glob matched against each file's path *relative to* `dir`
    // (e.g. `*.ts`, `*.{rs,ts}`, `src/**/*.tsx`). Bare globs without `/` match
    // at any directory depth (like `rg --glob`), so `*.ts` finds `a/b.ts` too.
    // Brace alternation is expanded here because the `glob` crate has no native
    // support for it. An empty result (no `include`, or only unparsable globs)
    // means "no filter", so a typo never silently drops every match.
    let include_patterns = compile_include(include);
    // `exclude` is the negative complement of `include`: a file matching any
    // exclude glob is dropped, even when it also matches `include` (#870).
    let exclude_patterns = compile_include(exclude);
    const MAX_PATTERN_LEN: usize = 1024;
    const MAX_REGEX_SIZE: usize = 1 << 20; // 1 MiB DFA limit

    let redact = lean_ctx::core::redaction::redaction_enabled_for_active_role();
    let protected = lean_ctx::core::policy::runtime::active().is_some();
    let protected_root = lean_ctx::core::policy::diagnostics::project();
    // Observed before any resident store is consulted: a changed admission
    // policy drops the content cache and trigram index first (G5).
    let admission = lean_ctx::core::context_admission::stores::StoreAdmission::current();
    let mut protected_budget = lean_ctx::core::limits::max_read_bytes()
        .min(lean_ctx::core::policy::content::MAX_PROTECTED_CONTENT_BYTES);
    // Files that contributed at least one returned match, in scan order.
    let mut matched_sources: Vec<std::path::PathBuf> = Vec::new();
    if pattern.len() > MAX_PATTERN_LEN {
        return SearchOutcome::error(format!(
            "ERROR: pattern too long ({} > {MAX_PATTERN_LEN} chars)",
            pattern.len()
        ));
    }
    let re = match RegexBuilder::new(pattern)
        .size_limit(MAX_REGEX_SIZE)
        .dfa_size_limit(MAX_REGEX_SIZE)
        .build()
    {
        Ok(r) => r,
        Err(e) => return SearchOutcome::error(format!("ERROR: invalid regex: {e}")),
    };
    // #870: `exclude_pattern` drops any *result line* matching this regex — the
    // in-pipeline equivalent of `grep -v`. An unparsable pattern is ignored
    // (no exclusion), so a typo never silently hides every match.
    let exclude_re = exclude_pattern.and_then(|p| {
        RegexBuilder::new(p)
            .size_limit(MAX_REGEX_SIZE)
            .dfa_size_limit(MAX_REGEX_SIZE)
            .build()
            .ok()
    });

    let root = Path::new(dir);
    if !root.exists() {
        let hint = lean_ctx::core::path_suggest::hint(root);
        return SearchOutcome::error(format!("ERROR: {dir} does not exist{hint}"));
    }
    // Broad-root guard (#356 class): with cwd == $HOME a defaulted `path`
    // would walk the whole home dir and trip macOS TCC privacy prompts.
    if let Some(err) = crate::tools::walk_guard::deny_unsafe_walk_root(dir) {
        return SearchOutcome::error(err);
    }
    let size_limit = if std::fs::metadata(root).is_ok_and(|m| m.is_file()) {
        MAX_EXPLICIT_FILE_SIZE
    } else {
        MAX_FILE_SIZE
    };

    let mut files: Vec<PathBuf> = Vec::new();
    let mut matches = Vec::new();
    let mut raw_tokens_accum: usize = 0;
    let mut files_searched = 0u32;
    let mut files_skipped_size = 0u32;
    // Which files the size cap skipped, so the note names them instead of only
    // counting them (#1917).
    let mut skipped_size_files: Vec<String> = Vec::new();
    let mut files_skipped_encoding = 0u32;
    let mut files_withheld = 0u32;
    let mut skipped_boundary_files: Vec<(String, &'static str)> = Vec::new();
    let mut files_skipped_special = 0u32;
    let mut deadline_hit = false;
    // #1625: whether the result cap stopped the scan. Without this, a search
    // that quit after one file reported "10 matches in 1 files (scanned 1)" —
    // indistinguishable from an exhaustive scan that genuinely found ten.
    let mut cap_hit = false;
    // Under a policy every scanned original is charged to one byte budget. When
    // it cannot cover the next file the scan stops and says so; the files left
    // unscanned were not withheld by the policy and must not be counted as such.
    let mut budget_hit = false;

    // Fast path: a warm resident trigram index narrows the candidate files in
    // memory, eliminating the per-call directory walk + full-corpus read. The
    // index covers the exact same file universe as the walk below, and matches
    // are still verified line-by-line with the same regex — so results are
    // identical. Missing/stale index → returns None and triggers a background
    // (re)build; this call uses the walk fallback.
    // Files the filters admit when the index narrowed candidates; the walk
    // path scans its whole scope, so `None` there. Protected searches bypass
    // legacy unbound indexes and admit original source before matching.
    let mut narrowed_scope: Option<usize> = None;
    let used_index = if !protected
        && let Some(idx) =
            lean_ctx::core::search_index::get_fresh(dir, respect_gitignore, allow_secret_paths)
    {
        let candidates = idx.candidate_paths(pattern, &include_patterns, root);
        if matches!(
            candidates,
            lean_ctx::core::search_index::CandidateSet::Narrowed(_)
        ) {
            narrowed_scope = Some(idx.scope_count(&include_patterns, &exclude_patterns, root));
        }
        files = candidates.into_paths();
        if !allow_secret_paths {
            skipped_boundary_files = lean_ctx::core::search_index::boundary_skipped_files(
                dir,
                respect_gitignore,
                &include_patterns,
            );
        }
        true
    } else {
        false
    };

    if !used_index {
        // Vendor dirs (node_modules, …) follow the gitignore toggle: explicitly
        // disabling gitignore is the escape hatch to look inside them (#400).
        // GH #1431: hidden(false) for consistency with ctx_glob — dot-dirs
        // must be searchable; gitignore + is_secret_like guard the rest.
        let walker = WalkBuilder::new(root)
            .hidden(false)
            .max_depth(Some(MAX_WALK_DEPTH))
            .git_ignore(respect_gitignore)
            .git_global(respect_gitignore)
            .git_exclude(respect_gitignore)
            .require_git(false)
            .filter_entry(move |e| {
                if respect_gitignore {
                    lean_ctx::core::walk_filter::keep_entry(e)
                } else {
                    lean_ctx::core::cloud_files::keep_entry(e)
                }
            })
            .build();

        for entry in walker.filter_map(std::result::Result::ok) {
            if entry.file_type().is_none_or(|ft| ft.is_dir()) {
                continue;
            }

            if entry.file_type().is_some_and(|ft| ft.is_symlink()) {
                continue;
            }

            let path = entry.path();

            if is_binary_ext(path) || is_generated_file(path) {
                continue;
            }

            if !include_patterns.is_empty() {
                let rel_str = filter_rel(path, root);
                if !include_patterns.iter().any(|p| p.matches(&rel_str)) {
                    continue;
                }
            }

            if !allow_secret_paths {
                if let Some(reason) = lean_ctx::core::io_boundary::is_secret_like(path) {
                    skipped_boundary_files.push((filter_rel(path, root).into_owned(), reason));
                    continue;
                }
            }

            // Size / regular-file filtering happens once in the shared read loop
            // below, so the walk path and the trigram-index fast path apply the
            // exact same eligibility rules.
            files.push(path.to_path_buf());
        }
        skipped_boundary_files.sort_unstable();
    }

    // #870: drop excluded paths after both the index and walk populate `files`,
    // so the negative glob filter applies uniformly to either collection path.
    if !exclude_patterns.is_empty() {
        files.retain(|path| {
            let rel_str = filter_rel(path, root);
            !exclude_patterns.iter().any(|p| p.matches(&rel_str))
        });
    }

    // ent2-3: the Hive policy's readable roots and never-send patterns apply
    // to every file the scan would read, from either collection path; a policy
    // that cannot be trusted refuses the search (fail closed).
    match lean_ctx::core::io_boundary::hive_io_rules(None) {
        Ok(None) => {}
        Ok(Some(rules)) => {
            files.retain(|path| match rules.refusal(path) {
                None => true,
                Some(refusal) => {
                    let reason = match refusal {
                        lean_ctx::core::policy::hive_io::Refusal::OutsideRoots => {
                            "outside the Hive readable roots"
                        }
                        lean_ctx::core::policy::hive_io::Refusal::NeverSend(_) => "Hive never_send",
                    };
                    skipped_boundary_files.push((filter_rel(path, root).into_owned(), reason));
                    false
                }
            });
            skipped_boundary_files.sort_unstable();
        }
        Err(e) => {
            return SearchOutcome::error(format!(
                "ERROR: [I/O BOUNDARY] search refused: {e}; reads stay refused until a valid \
                 Hive policy is installed."
            ));
        }
    }

    // Deterministic search: stable file ordering makes max_results truncation reproducible.
    files.sort_unstable_by(|a, b| a.as_os_str().cmp(b.as_os_str()));

    // #1994: the scope is every file the filters admit. Files the trigram
    // index ruled out provably lack the literal, so they count as covered:
    // "scanned" then means the same thing with or without a warm index, and
    // `scanned 0` can only mean the filters left nothing to search.
    let files_in_scope = narrowed_scope.unwrap_or(files.len());
    let index_pruned =
        u32::try_from(files_in_scope.saturating_sub(files.len())).unwrap_or(u32::MAX);

    let root_str = root.to_string_lossy();
    let deadline = search_deadline().map(|budget| Instant::now() + budget);
    for path in &files {
        if matches.len() >= max_results {
            cap_hit = true;
            break;
        }

        // Stop gracefully instead of appearing to hang on a pathological corpus
        // or a stuck read (#336): once the wall-clock budget is spent, return
        // the partial results gathered so far with a hint to narrow the search.
        if deadline.is_some_and(|dl| Instant::now() >= dl) {
            deadline_hit = true;
            break;
        }

        // Only ever read regular files within the size budget. A FIFO, socket or
        // device node would block `read_to_string` forever — the root cause of
        // #336 — and oversized or unstatable files are skipped. `metadata`
        // (stat) never opens the file, so it cannot block on a special file.
        let file_len: u64;
        let state = match std::fs::metadata(path) {
            Ok(meta) if !meta.file_type().is_file() => {
                files_skipped_special += 1;
                continue;
            }
            Ok(meta) if meta.len() > size_limit => {
                files_skipped_size += 1;
                if skipped_size_files.len() < MAX_NAMED_SKIPS {
                    skipped_size_files.push(protocol::shorten_path_relative(
                        &path.to_string_lossy(),
                        &root_str,
                    ));
                }
                continue;
            }
            Ok(meta) => {
                file_len = meta.len();
                lean_ctx::core::content_cache::FileState::from_metadata(&meta)
            }
            Err(_) => {
                files_skipped_encoding += 1;
                continue;
            }
        };

        // Reuse the copy the trigram-index build already read (issue #148): the
        // corpus is read from disk once and the regex-verify pass here is an
        // in-memory hit. On a miss (cold cache / evicted) read once and publish
        // it for the next caller. `(mtime, size)` validation guarantees we never
        // verify against stale bytes.
        let content: std::sync::Arc<str> = if protected {
            // The budget decision rests on the file size alone, never on its
            // content, so stopping here discloses nothing about any source.
            if (protected_budget as u64) < file_len {
                budget_hit = true;
                break;
            }
            // Scanning a file does not make it a source of the result: only a
            // file that contributes a match is published (below, after the
            // scan). Publishing every scanned file would bind the result to
            // the whole tree.
            let admitted = protected_root.as_ref().and_then(|root| {
                lean_ctx::core::archive::authority::without_capture(|| {
                    crate::tools::ctx_read::read_file_for_tool_rooted_budgeted(
                        path.to_str()?,
                        root.to_str()?,
                        "ctx_search",
                        &mut protected_budget,
                    )
                    .ok()
                })
            });
            if let Some(text) = admitted {
                std::sync::Arc::from(text)
            } else {
                // No source path or diagnostic payload is disclosed for
                // an unreadable or policy-withheld original.
                files_withheld += 1;
                continue;
            }
        } else if let Some(cached) = state.and_then(|s| lean_ctx::core::content_cache::get(path, s))
        {
            lean_ctx::core::cache::record_search_content_read(true);
            cached
        } else {
            if state.is_some() {
                lean_ctx::core::cache::record_search_content_read(false);
            }
            let Ok(decoded) = lean_ctx::core::text_decode::read_text_checked(path) else {
                files_skipped_encoding += 1;
                continue;
            };
            // Replaced or dropped bytes mean the text is not the whole source.
            // Governed and sovereign mode demand full inspection: the file is
            // withheld from the search. Developer mode still searches it, but
            // it is never published to the shared content cache.
            let complete = decoded.complete();
            if !complete
                && admission.admission_policy().gateway.mode
                    != lean_ctx_protocol::context_gateway::GatewayModeV1::Developer
            {
                files_withheld += 1;
                continue;
            }
            let text = decoded.text;
            // Search matches only ever come from admitted text: a masked value
            // cannot be found, and a withheld or restricted source is skipped
            // without disclosing it (G5).
            let Some(text) = admission.admit(&text, path, None) else {
                files_withheld += 1;
                continue;
            };
            let arc: std::sync::Arc<str> = std::sync::Arc::from(text);
            // An explicitly named file above the walk cap is read once and
            // not published: it would evict the whole shared cache.
            if complete
                && let Some(s) = state
                && arc.len() as u64 <= MAX_FILE_SIZE
            {
                lean_ctx::core::content_cache::insert(
                    path,
                    s,
                    std::sync::Arc::clone(&arc),
                    &admission,
                );
            }
            arc
        };

        files_searched += 1;
        // Enclosing-symbol spans for this file, computed lazily on the first hit
        // (never for non-matching files) and reused for every later hit here.
        let mut file_enclosing: Option<EnclosingIndex> = None;

        for (i, line) in content.lines().enumerate() {
            // #870: `exclude_pattern` filters out matching lines (grep -v).
            if re.is_match(line) && !exclude_re.as_ref().is_some_and(|ex| ex.is_match(line)) {
                let short_path =
                    protocol::shorten_path_relative(&path.to_string_lossy(), &root_str);
                let source: &Path = path.as_ref();
                if matched_sources
                    .last()
                    .is_none_or(|last| last.as_path() != source)
                {
                    matched_sources.push(source.to_path_buf());
                }
                // Count raw tokens incrementally (avoids separate Vec + join)
                raw_tokens_accum += count_tokens(line.trim()) + 2;
                let mut shown = if redact {
                    lean_ctx::core::redaction::redact_text(line.trim())
                } else {
                    line.trim().to_string()
                };
                if shown.len() > MAX_MATCH_LINE_WIDTH {
                    shown.truncate(shown.floor_char_boundary(MAX_MATCH_LINE_WIDTH));
                    shown.push_str("...");
                }
                // grep-ast enrichment (#608): name the enclosing symbol + its
                // handle anchor so the hit is actionable without a follow-up
                // read. Appended after `shown`, so the `path:line content` prefix
                // every caller/test relies on is untouched.
                let tag = file_enclosing
                    .get_or_insert_with(|| EnclosingIndex::for_file(path, content.as_ref()))
                    .tag_for(i + 1)
                    .unwrap_or_default();
                // The anchor hash is over the RAW line (matching ctx_read/ctx_patch
                // which both hash `content.lines()`), never the trimmed/truncated
                // display text — otherwise ctx_patch would always see a mismatch.
                if anchored {
                    matches.push(format!(
                        "{short_path}:{}:{} {}{}",
                        i + 1,
                        lean_ctx::core::anchor::line_hash(line),
                        shown,
                        tag
                    ));
                } else {
                    matches.push(format!("{short_path}:{} {}{}", i + 1, shown, tag));
                }
                if matches.len() >= max_results {
                    cap_hit = true;
                    break;
                }
            }
        }
    }

    // Source lineage of the result (G04): every file that contributed a match,
    // and nothing else. Each is read once through the admitted rooted reader,
    // which publishes it bound to what is on disk now; a file that cannot be
    // bound makes the set unknown. A no-op without a capture or protection.
    // A result WITHOUT matches names no source and stays of unknown lineage:
    // "nothing matched" is a statement about every scanned file.
    let lineage_root = lean_ctx::core::policy::diagnostics::project().map_or_else(
        || dir.to_owned(),
        |root| root.to_string_lossy().into_owned(),
    );
    for source in &matched_sources {
        crate::tools::ctx_read::publish_requested_source(
            &source.to_string_lossy(),
            &lineage_root,
            "ctx_search",
        );
    }

    // #883: sort matches by file match-density — files with more hits surface
    // first, which is a proxy for relevance when the pattern contains common tokens.
    if matches.len() > 1 {
        use std::collections::HashMap;
        let mut file_counts: HashMap<String, usize> = HashMap::new();
        for m in &matches {
            let file = extract_file_from_match(m).to_string();
            *file_counts.entry(file).or_default() += 1;
        }
        matches.sort_by(|a, b| {
            let fa = extract_file_from_match(a);
            let fb = extract_file_from_match(b);
            let ca = file_counts.get(fa).copied().unwrap_or(0);
            let cb = file_counts.get(fb).copied().unwrap_or(0);
            cb.cmp(&ca).then_with(|| fa.cmp(fb))
        });
    }

    let files_covered = files_searched.saturating_add(index_pruned);

    if matches.is_empty() {
        // Match the hit response's scoped scan count, including candidates the
        // index ruled out, while retaining policy-withheld visibility.
        let mut msg = format!("0 matches for '{pattern}' (scanned {files_covered} files)");
        if files_withheld > 0 {
            msg.push_str(&format!(
                " ({files_withheld} sources withheld under policy)"
            ));
        }
        if files_in_scope == 0 {
            msg.push_str(&empty_scope_note(dir, include, exclude));
        }
        if files_skipped_size > 0 {
            msg.push_str(&format!(
                " ({files_skipped_size} large files skipped: {})",
                name_skipped(&skipped_size_files, files_skipped_size)
            ));
        }
        if files_skipped_encoding > 0 {
            msg.push_str(&format!(
                " ({files_skipped_encoding} files skipped: binary/encoding)"
            ));
        }
        if let Some(note) = format_boundary_skips(&skipped_boundary_files, false) {
            msg.push_str(&note);
        }
        if files_skipped_special > 0 {
            msg.push_str(&format!(
                " ({files_skipped_special} special files skipped: not regular files)"
            ));
        }
        if deadline_hit {
            msg.push_str(
                " (search stopped at the time budget — refine the pattern or scope with path=)",
            );
        }
        if budget_hit {
            msg.push_str(&budget_note(files_covered));
        }
        return SearchOutcome::without_matches(msg).withholding(skipped_boundary_files.len());
    }

    // Prefix-cache-friendly: structural file list before per-query match content
    let matched_files: Vec<&str> = {
        let mut seen = HashSet::new();
        matches
            .iter()
            .filter_map(|m| {
                let file = extract_file_from_match(m);
                if seen.insert(file) { Some(file) } else { None }
            })
            .collect()
    };

    // #1591: "N matches in M files" read as "M files matched" — but `M` was the
    // number of files *searched*. Report what matched; keep the scanned count as
    // a clearly-labelled secondary number so scope is still visible.
    let mut result = format!(
        "{} matches in {} files (scanned {files_covered})",
        matches.len(),
        matched_files.len()
    );
    if matched_files.len() > 1 {
        if matched_files.len() <= 10 {
            result.push_str(" [");
            result.push_str(&matched_files.join(", "));
            result.push(']');
        } else {
            let shown: Vec<&str> = matched_files.iter().take(8).copied().collect();
            result.push_str(&format!(
                " [{}, +{} more]",
                shown.join(", "),
                matched_files.len() - 8
            ));
        }
    }
    result.push_str(":\n");
    // Self-describing output (GL #580): the anchor notation ships its own legend.
    if anchored {
        result.push_str("[anchored: path:line:hh → edit via ctx_patch]\n");
    }
    // The `∈name@Lstart` tags carry no legend line: in the Dispatch benchmark
    // transcripts agents used the tag names (`ctx_read symbol=`) and start
    // lines, and never the `handle=` form the legend advertised (0 of 244
    // tagged results, 2026-11-01); it cost ~30 tokens per run.
    result.push_str(&matches.join("\n"));
    if files_withheld > 0 {
        result.push_str(&format!(
            "\n({files_withheld} sources withheld under policy)"
        ));
    }

    if files_skipped_size > 0 {
        result.push_str(&format!(
            "\n({files_skipped_size} files >512KB skipped: {})",
            name_skipped(&skipped_size_files, files_skipped_size)
        ));
    }
    if files_skipped_encoding > 0 {
        result.push_str(&format!(
            "\n({files_skipped_encoding} files skipped: binary/encoding)"
        ));
    }
    if let Some(note) = format_boundary_skips(&skipped_boundary_files, true) {
        result.push_str(&note);
    }
    if files_skipped_special > 0 {
        result.push_str(&format!(
            "\n({files_skipped_special} special files skipped: not regular files)"
        ));
    }
    if deadline_hit {
        result.push_str(&format!(
            "\n(search stopped after the {}s budget — {files_covered} files scanned; \
             refine the pattern or scope with path= for full coverage)",
            search_deadline().map_or(0, |d| d.as_secs())
        ));
    }
    if budget_hit {
        result.push('\n');
        result.push_str(budget_note(files_covered).trim_start());
    }
    // #1625: the cap stopping the scan is the same class of event as the
    // deadline above, and it was silent. A caller auditing a codebase read
    // "10 matches in 1 files (scanned 1)" as an exhaustive answer when the
    // scan had in fact stopped after the first file of 32.
    if cap_hit {
        result.push_str(&format!(
            "\n(stopped at max_results={max_results}: {files_covered} of {files_in_scope} \
             files scanned; counts are a floor, not a total)"
        ));
    }

    if let Some(delta) = lean_ctx::core::search_delta::compute_delta(pattern, &matches) {
        return SearchOutcome::from_observed(delta, raw_tokens_accum)
            .withholding(skipped_boundary_files.len());
    }

    if symbol_map::substitution_enabled() {
        let exts = extract_extensions(include);
        let ext_refs: Vec<&str> = exts.iter().map(String::as_str).collect();
        let mut sym = SymbolMap::new();
        let idents = symbol_map::extract_identifiers(&result, &ext_refs);
        for ident in &idents {
            sym.register(ident);
        }
        if sym.len() >= 3 {
            let sym_table = sym.format_table();
            let compressed = sym.apply(&result);
            let original_tok = count_tokens(&result);
            let compressed_tok = count_tokens(&compressed) + count_tokens(&sym_table);
            let net_saving = original_tok.saturating_sub(compressed_tok);
            if original_tok > 0 && net_saving * 100 / original_tok >= 5 {
                result = format!("{compressed}{sym_table}");
            }
        }
    }

    SearchOutcome::from_observed(result, raw_tokens_accum).withholding(skipped_boundary_files.len())
}

/// `a.log, b.log, +3 more` — the size-skipped files by name (#1917), so a
/// skipped target is never mistaken for a searched one.
fn name_skipped(named: &[String], total: u32) -> String {
    let mut out = named.join(", ");
    let rest = (total as usize).saturating_sub(named.len());
    if rest > 0 {
        out.push_str(&format!(", +{rest} more"));
    }
    out
}

/// Render boundary-skip audit note (#1481): paths + reason codes, capped at 10.
fn format_boundary_skips(skipped: &[(String, &'static str)], newline: bool) -> Option<String> {
    if skipped.is_empty() {
        return None;
    }
    const MAX_SHOW: usize = 10;
    let n = skipped.len();
    let details: Vec<String> = skipped
        .iter()
        .take(MAX_SHOW)
        .map(|(p, r)| format!("{p} [{r}]"))
        .collect();
    let prefix = if newline { "\n(" } else { " (" };
    let mut msg = format!(
        "{prefix}{n} secret-like files skipped by boundary policy: {}",
        details.join(", ")
    );
    if n > MAX_SHOW {
        msg.push_str(&format!(", and {} more...", n - MAX_SHOW));
    }
    msg.push(')');
    Some(msg)
}

/// Per-file map from a line number to its narrowest enclosing symbol, built
/// once per matched file from the signature spans. Powers the `∈name@Lstart`
/// tag on each `ctx_search` hit (grep-ast pattern): the agent sees which
/// function/class a match lives in — and the handle to fetch it — without a
/// follow-up read. Tree-sitter-gated by construction: the regex-fallback
/// extractor yields single-line spans (`end == start`), which are filtered out
/// here, so a non-tree-sitter build emits byte-identical output (#498).
struct EnclosingIndex {
    /// `(start_line, end_line, name)` for multi-line symbols, sorted by start.
    spans: Vec<(usize, usize, String)>,
}

impl EnclosingIndex {
    fn for_file(path: &Path, content: &str) -> Self {
        let ext = path.extension().and_then(|e| e.to_str()).unwrap_or("");
        let mut spans: Vec<(usize, usize, String)> =
            lean_ctx::core::signatures::extract_signatures(content, ext)
                .into_iter()
                .filter_map(|s| match (s.start_line, s.end_line) {
                    (Some(a), Some(b)) if b > a => Some((a, b, s.name)),
                    _ => None,
                })
                .collect();
        spans.sort_by(|x, y| x.0.cmp(&y.0).then(x.1.cmp(&y.1)));
        Self { spans }
    }

    /// The narrowest span containing `line`, rendered as the compact
    /// ` ∈name@Lstart` tag, or `None` when no multi-line symbol encloses it.
    fn tag_for(&self, line: usize) -> Option<String> {
        let mut best: Option<&(usize, usize, String)> = None;
        for sp in &self.spans {
            if line >= sp.0 && line <= sp.1 {
                match best {
                    None => best = Some(sp),
                    Some(b) if (sp.1 - sp.0) < (b.1 - b.0) => best = Some(sp),
                    _ => {}
                }
            }
        }
        best.map(|(start, _, name)| format!(" ∈{name}@L{start}"))
    }
}

/// Upper bound on the number of globs a single `include` may expand to, so a
/// pathological brace pattern (`{a,b}{c,d}{e,f}…`) can never blow up.
const MAX_INCLUDE_GLOBS: usize = 64;

/// Compile an `include` filter into one or more matchers.
///
/// Brace alternation (`*.{rs,ts}`) is expanded to multiple globs (`*.rs`,
/// `*.ts`) because the `glob` crate matches `{` / `}` literally. A file is
/// included when it matches *any* of the returned patterns. An empty vec means
/// "no filter": `include` was `None`, or every expansion failed to parse.
///
/// Bare globs without a `/` (e.g. `pathjail.rs`, `*.rs`) are auto-prefixed
/// with `**/` to match at any directory depth — matching `rg --glob` and
/// `git grep` behaviour. Globs that already contain `/` are used as-is, so
/// `src/**/*.rs` only matches under `src/`.
///
/// A comma outside braces separates globs (`*.go,*.yaml`), the list form
/// callers reach for first (#1994). It used to compile to one glob no file
/// could match, so the search reported a clean miss over an empty scope.
fn compile_include(include: Option<&str>) -> Vec<Pattern> {
    let Some(raw) = include else {
        return Vec::new();
    };
    split_top_level_commas(raw)
        .into_iter()
        .flat_map(expand_braces)
        .take(MAX_INCLUDE_GLOBS)
        .filter(|g| !g.is_empty())
        .map(|g| {
            if g.contains('/') {
                g
            } else {
                format!("**/{g}")
            }
        })
        .filter_map(|g| Pattern::new(&g).ok())
        .collect()
}

/// Split a glob list at commas outside `{…}` groups, trimming each piece.
fn split_top_level_commas(raw: &str) -> Vec<&str> {
    let mut pieces = Vec::new();
    let mut depth = 0usize;
    let mut start = 0;
    for (i, c) in raw.char_indices() {
        match c {
            '{' => depth += 1,
            '}' => depth = depth.saturating_sub(1),
            ',' if depth == 0 => {
                pieces.push(raw[start..i].trim());
                start = i + 1;
            }
            _ => {}
        }
    }
    pieces.push(raw[start..].trim());
    pieces
}

/// Why a policy-protected search stopped early: every scanned original is
/// charged to one byte budget per search (`LEAN_CTX_MAX_READ_BYTES`, at most the
/// protected-content cap). The unscanned rest was not withheld by the policy.
fn budget_note(files_covered: u32) -> String {
    format!(
        " (search stopped after {files_covered} files: the protected-content read budget of this \
         search is spent; the remaining files were not scanned, not withheld — narrow with \
         path= or include= for full coverage)"
    )
}

/// The path include/exclude globs are matched against: relative to the search
/// root, or the file name when the root is the file itself (#2059) — there
/// `strip_prefix` yields the empty string, which no glob admits.
fn filter_rel<'a>(path: &'a Path, root: &Path) -> std::borrow::Cow<'a, str> {
    match path.strip_prefix(root) {
        Ok(rel) if !rel.as_os_str().is_empty() => rel.to_string_lossy(),
        _ => path
            .file_name()
            .map_or_else(|| path.to_string_lossy(), |name| name.to_string_lossy()),
    }
}

/// Why a search had nothing to scan (#1994), appended to a zero-hit result so
/// it cannot be read as "the pattern is not in the codebase".
fn empty_scope_note(dir: &str, include: Option<&str>, exclude: Option<&str>) -> String {
    match (include, exclude) {
        (Some(include), _) => format!(
            " — include=`{include}` admits no file under {dir}, so nothing was searched. \
             Check the glob; a list is `*.{{go,yaml}}` or `*.go,*.yaml`."
        ),
        (None, Some(exclude)) => format!(
            " — exclude=`{exclude}` removes every file under {dir}, so nothing was searched."
        ),
        (None, None) => format!(" — {dir} holds no searchable text file."),
    }
}

/// Expand one or more `{a,b,c}` brace groups into the cartesian set of concrete
/// globs. Patterns without braces (or with an unbalanced brace) are returned
/// unchanged, so this is safe to call on any input.
fn expand_braces(pattern: &str) -> Vec<String> {
    let Some(open) = pattern.find('{') else {
        return vec![pattern.to_string()];
    };
    let Some(close_rel) = pattern[open..].find('}') else {
        return vec![pattern.to_string()];
    };
    let close = open + close_rel;
    let prefix = &pattern[..open];
    let inner = &pattern[open + 1..close];
    let suffix = &pattern[close + 1..];

    let mut out = Vec::new();
    for alt in inner.split(',') {
        let alt = alt.trim();
        for expanded_suffix in expand_braces(suffix) {
            out.push(format!("{prefix}{alt}{expanded_suffix}"));
            if out.len() >= MAX_INCLUDE_GLOBS {
                return out;
            }
        }
    }
    out
}

/// Extract the file extensions referenced by an `include` glob, used by the
/// symbol-substitution pass (which keyword-filters per language).
///
/// Only the final path component is inspected, so dots inside directory
/// segments never leak in. Handles a single trailing extension (`*.rs` → `rs`)
/// and brace expansion (`*.{rs,ts}` → `rs`, `ts`); a glob without an extension
/// (`src/**/*`) yields an empty list. Unknown extensions are returned verbatim —
/// `symbol_map::is_keyword` simply treats them as "no keywords", so no allowlist
/// has to be kept in sync here.
fn extract_extensions(include: Option<&str>) -> Vec<String> {
    let Some(list) = include else {
        return Vec::new();
    };
    split_top_level_commas(list)
        .into_iter()
        .flat_map(extensions_of_glob)
        .collect()
}

fn extensions_of_glob(pattern: &str) -> Vec<String> {
    let filename = pattern.rsplit('/').next().unwrap_or(pattern);
    let Some(dot) = filename.rfind('.') else {
        return Vec::new();
    };
    let ext_part = &filename[dot + 1..];

    if let Some(inner) = ext_part.strip_prefix('{').and_then(|s| s.strip_suffix('}')) {
        return inner
            .split(',')
            .map(|e| e.trim().to_string())
            .filter(|e| !e.is_empty())
            .collect();
    }

    if ext_part.is_empty() {
        return Vec::new();
    }
    vec![ext_part.to_string()]
}

/// Extract file path from a grep match line, handling Windows drive letters (e.g. "C:").
fn extract_file_from_match(line: &str) -> &str {
    let start = if line.len() >= 2
        && line.as_bytes().first().is_some_and(u8::is_ascii_alphabetic)
        && line.as_bytes().get(1) == Some(&b':')
    {
        2
    } else {
        0
    };
    match line[start..].find(':') {
        Some(pos) => &line[..start + pos],
        None => line,
    }
}

#[cfg(test)]
#[path = "tests.rs"]
mod tests;