gunnar_server/

search.rs

//! **`gunnar search` — a literal string, across one revision's files.**
//!
//! There was no code search anywhere in gunnar before this. This is the
//! smallest honest first version: resolve a ref to its tree, walk the tree, and
//! scan each file's lines for a **literal** substring, returning `path:line`
//! matches.
//!
//! # What it is bounded by, and why the bound is the point
//!
//! A search is a control-plane read, and unlike a clone it has no transfer
//! admission in front of it — so an unbounded walk of the znippy blob store is a
//! way to make one cheap request read every byte the repository holds. It is
//! therefore capped by construction:
//!
//! * **A file-size ceiling** ([`Limits::max_file_bytes`]). A blob larger than it
//!   is skipped *without being read* — the size comes from
//!   [`GitServe::header`], which a backend answers without inflating the object,
//!   so a 2 GiB blob costs a header lookup, not 2 GiB of reads.
//! * **A match ceiling** ([`Limits::max_matches`]). The walk stops as soon as it
//!   is reached; a pattern that is in every file does not stream the whole tree
//!   back.
//!
//! Binary files are skipped by the same NUL probe a diff uses
//! ([`crate::diff::is_binary`]), so "search" means "search text".
//!
//! # The two follow-ups this deliberately is not
//!
//! 1. **A persistent index.** This walks the tree live on every query. A search
//!    index — the trigram/postings store that answers a query in milliseconds
//!    and survives a restart — is a separate, much larger lane: it has to be
//!    built, kept in step with every push, and stored. This does none of that,
//!    and says so.
//! 2. **Regex, and history.** The pattern here is a literal, and the scope is
//!    the *latest* revision of one ref. Regular-expression matching (which would
//!    add the `regex` crate and its tail to an appliance that today links
//!    neither) and searching across history are the next steps, not this one.

use anyhow::{Context, Result};
use gunnar_store::git_storage_trait::{GitServe, ObjType};
use gunnar_store::object::{self, EntryKind, TreeIter};

use crate::stores::ServerStores;

/// A file that is scanned no matter its size would be a way to make one request
/// read the largest blob in the repository; a match ceiling that is missing
/// would let a common word stream the whole tree back. Both are here.
#[derive(Debug, Clone, Copy)]
pub struct Limits {
    /// Files larger than this are skipped without being read.
    pub max_file_bytes: u64,
    /// The walk stops once this many matches have been found.
    pub max_matches: usize,
}

/// 1 MiB per file, 1000 matches — a source-tree search, not a data-lake scan.
pub const DEFAULT_MAX_FILE_BYTES: u64 = 1 << 20;
/// The default match ceiling.
pub const DEFAULT_MAX_MATCHES: usize = 1000;

impl Default for Limits {
    fn default() -> Self {
        Limits {
            max_file_bytes: DEFAULT_MAX_FILE_BYTES,
            max_matches: DEFAULT_MAX_MATCHES,
        }
    }
}

/// One matching line.
#[derive(Debug, Clone)]
pub struct Match {
    /// The file's path within the tree, `/`-joined.
    pub path: String,
    /// The one-based line number, the way an editor and `grep` count.
    pub line_number: usize,
    /// The line's bytes, without its trailing newline.
    pub line: Vec<u8>,
}

/// **The tip's root tree, or `None` if the walk should find nothing.**
fn root_tree(
    git: &dyn GitServe,
    hash: gix_hash::Kind,
    commit: gix_hash::ObjectId,
) -> Result<gix_hash::ObjectId> {
    let (kind, bytes) = git
        .read(commit.as_bytes())?
        .with_context(|| format!("commit {commit} is not in this repository"))?;
    anyhow::ensure!(kind == ObjType::Commit, "{commit} is not a commit");
    Ok(object::commit(&bytes, hash)
        .with_context(|| format!("decoding commit {commit}"))?
        .tree)
}

/// **Search the tree at `commit` for the literal `needle`.**
///
/// The testable core: it takes only a [`GitServe`] and a commit, so a test can
/// plant a known string at a known path and line and assert exactly that — and
/// assert a string that is *not* there returns nothing rather than an error or a
/// false hit.
pub fn search_tree(
    git: &dyn GitServe,
    hash: gix_hash::Kind,
    commit: gix_hash::ObjectId,
    needle: &[u8],
    limits: Limits,
) -> Result<Vec<Match>> {
    // An empty pattern matches every position of every line; that is not a
    // search, it is a dump, and it is refused rather than answered.
    anyhow::ensure!(!needle.is_empty(), "the search pattern is empty");

    let mut out = Vec::new();
    let root = root_tree(git, hash, commit)?;
    walk(git, hash, root, "", needle, &limits, &mut out)?;
    Ok(out)
}

/// Depth-first over one tree, appending matches until the ceiling is reached.
fn walk(
    git: &dyn GitServe,
    hash: gix_hash::Kind,
    tree: gix_hash::ObjectId,
    prefix: &str,
    needle: &[u8],
    limits: &Limits,
    out: &mut Vec<Match>,
) -> Result<()> {
    if out.len() >= limits.max_matches {
        return Ok(());
    }
    let (kind, bytes) = match git.read(tree.as_bytes())? {
        Some(pair) => pair,
        None => return Ok(()),
    };
    if kind != ObjType::Tree {
        return Ok(());
    }
    for entry in TreeIter::from_bytes(&bytes, hash).named() {
        let entry = entry.with_context(|| format!("decoding tree {tree}"))?;
        let name = String::from_utf8_lossy(entry.name);
        let path = if prefix.is_empty() {
            name.into_owned()
        } else {
            format!("{prefix}/{name}")
        };
        match entry.kind {
            EntryKind::Tree => walk(git, hash, entry.oid, &path, needle, limits, out)?,
            EntryKind::Blob | EntryKind::BlobExecutable => {
                scan_blob(git, entry.oid, &path, needle, limits, out)?
            }
            // A symlink's blob is a path, not searchable source; a gitlink names
            // a commit in another repository and has no blob here. Neither is a
            // file this search is about.
            EntryKind::Link | EntryKind::Commit => {}
        }
        if out.len() >= limits.max_matches {
            break;
        }
    }
    Ok(())
}

/// Scan one blob's lines, honouring the size ceiling before any bytes are read.
fn scan_blob(
    git: &dyn GitServe,
    oid: gix_hash::ObjectId,
    path: &str,
    needle: &[u8],
    limits: &Limits,
    out: &mut Vec<Match>,
) -> Result<()> {
    // The size FIRST, from the header, so an over-ceiling blob is never
    // inflated. `None` means the store cannot answer without reading; then the
    // read below still enforces the ceiling.
    if let Some((_, size)) = git.header(oid.as_bytes())? {
        if size > limits.max_file_bytes {
            return Ok(());
        }
    }
    let Some((ObjType::Blob, bytes)) = git.read(oid.as_bytes())? else {
        return Ok(());
    };
    // A store that could not size the blob from its header still must not scan a
    // file over the ceiling.
    if bytes.len() as u64 > limits.max_file_bytes {
        return Ok(());
    }
    if crate::diff::is_binary(&bytes) {
        return Ok(());
    }
    for (i, line) in crate::diff::split_lines(&bytes).into_iter().enumerate() {
        if contains(line, needle) {
            out.push(Match {
                path: path.to_owned(),
                line_number: i + 1,
                line: line.to_vec(),
            });
            if out.len() >= limits.max_matches {
                break;
            }
        }
    }
    Ok(())
}

/// Does `haystack` contain `needle` as a contiguous byte run?
fn contains(haystack: &[u8], needle: &[u8]) -> bool {
    if needle.is_empty() || needle.len() > haystack.len() {
        return false;
    }
    haystack
        .windows(needle.len())
        .any(|window| window == needle)
}

/// **Search `rev` in `repo`** for the literal `pattern`, resolving the revision
/// the way `verify` and `Refs.Log` do.
pub fn search(
    stores: &ServerStores,
    plane: &crate::control_plane::CoreControlPlane,
    repo: &gunnar_proto::RepoPath,
    rev: &str,
    pattern: &str,
    limits: Limits,
) -> Result<Vec<Match>> {
    use gunnar_grpc::ControlPlane as _;

    let repo_ref = gunnar_core::RepoRef::new(&repo.namespace, &repo.repo)
        .context("the repository path is not a legal one")?;
    let entry = stores
        .catalog()
        .get(&repo_ref)?
        .with_context(|| format!("no such repository: {repo_ref}"))?;
    let store = stores.repo_store(&entry)?;
    let git = store.serve();
    let hash = store.hash_kind();

    let commits = plane
        .log(repo, rev, 1, "")
        .map_err(|err| anyhow::anyhow!("{err}"))?;
    let head = commits
        .first()
        .with_context(|| format!("{rev} names no commit in {repo_ref}"))?;
    let tip = gix_hash::ObjectId::from_hex(head.oid.as_bytes())
        .map_err(gix_error::Error::from)
        .with_context(|| format!("{} is not an object id", head.oid))?;

    search_tree(git, hash, tip, pattern.as_bytes(), limits)
}

/// [`search`] over a data root, opening the stores itself — the CLI verb's entry.
pub fn search_at(
    data_root: &std::path::Path,
    repo: &gunnar_proto::RepoPath,
    rev: &str,
    pattern: &str,
    limits: Limits,
) -> Result<Vec<Match>> {
    let stores = std::sync::Arc::new(ServerStores::open(data_root)?);
    let plane = crate::control_plane::CoreControlPlane::new(std::sync::Arc::clone(&stores));
    search(&stores, &plane, repo, rev, pattern, limits)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::testgit::{Repo, TREE_MODE_BLOB, TREE_MODE_TREE};

    /// **A present string is found at its exact file and line; an absent one
    /// returns nothing.**
    ///
    /// Both halves are the guard. The red the "present" half is written against
    /// is a search that returns everything (or the wrong line); the red the
    /// "absent" half is written against is a search that errors, or matches a
    /// substring that is not really there. Proven red on 2026-08-31 by making
    /// `contains` always return `true`: the absent-string assertion then found
    /// hits and failed.
    #[test]
    fn a_present_string_is_found_at_its_line_and_an_absent_one_is_not() {
        let repo = Repo::new();
        let readme = repo.blob(b"hello world\nthe needle is here\ngoodbye\n");
        let other = repo.blob(b"nothing to see\nmove along\n");
        let src = repo.tree(&[(TREE_MODE_BLOB, "main.rs", other)]);
        let root = repo.tree(&[
            (TREE_MODE_BLOB, "README.md", readme),
            (TREE_MODE_TREE, "src", src),
        ]);
        let commit = repo.commit(root, &[], "Ada", "seed");

        let hits = search_tree(
            repo.serve(),
            repo.hash_kind(),
            commit,
            b"needle",
            Limits::default(),
        )
        .expect("search");
        assert_eq!(
            hits.len(),
            1,
            "the needle is on exactly one line of one file"
        );
        assert_eq!(hits[0].path, "README.md");
        assert_eq!(hits[0].line_number, 2);
        assert_eq!(hits[0].line, b"the needle is here");

        // A string that is nowhere returns an EMPTY result — not an error, and
        // not a false match on a near-miss.
        let none = search_tree(
            repo.serve(),
            repo.hash_kind(),
            commit,
            b"haystackk",
            Limits::default(),
        )
        .expect("search for an absent string is not an error");
        assert!(
            none.is_empty(),
            "an absent string must yield zero hits, got {none:?}"
        );
    }

    /// The size ceiling skips a file without letting it match, and the match
    /// ceiling stops the walk — both are asserted so neither can silently do
    /// nothing.
    #[test]
    fn the_ceilings_bind() {
        let repo = Repo::new();
        // A file over the size ceiling holds the needle and must be skipped.
        let big = {
            let mut body = vec![b'x'; 64];
            body.extend_from_slice(b"\nneedle\n");
            repo.blob(&body)
        };
        let small = repo.blob(b"needle\nneedle\nneedle\n");
        let root = repo.tree(&[
            (TREE_MODE_BLOB, "big.txt", big),
            (TREE_MODE_BLOB, "small.txt", small),
        ]);
        let commit = repo.commit(root, &[], "Ada", "seed");

        let tight = Limits {
            max_file_bytes: 8,
            max_matches: DEFAULT_MAX_MATCHES,
        };
        let hits =
            search_tree(repo.serve(), repo.hash_kind(), commit, b"needle", tight).expect("search");
        assert!(
            hits.iter().all(|m| m.path == "small.txt"),
            "the over-ceiling big.txt must be skipped, got {hits:?}"
        );

        // The match ceiling stops the walk at two, though three lines match.
        let capped = Limits {
            max_file_bytes: DEFAULT_MAX_FILE_BYTES,
            max_matches: 2,
        };
        let two =
            search_tree(repo.serve(), repo.hash_kind(), commit, b"needle", capped).expect("search");
        assert_eq!(two.len(), 2, "the match ceiling caps the result at two");
    }
}