crates/gunnar-server/src/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())
.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");
}
}