crates/gunnar-wire/src/shallow.rs
//! Shallow and deepening: `--depth`, `--shallow-since`, `--shallow-exclude`.
//!
//! All five wire arguments (`shallow`, `deepen`, `deepen-relative`,
//! `deepen-since`, `deepen-not`) are gated on the single advertised `shallow`
//! feature, so advertising it is a promise to accept all five. They are
//! therefore implemented rather than rejected. See [`crate::caps`] for why
//! that is not optional.
//!
//! Everything reduces to one traversal that assigns each commit a depth and
//! cuts where the depth, the date, or an excluded ref says to. The cut set is
//! the **boundary**: commits that go in the pack but whose parents do not.
use std::collections::{HashMap, HashSet, VecDeque};
use crate::refs::RefSnapshot;
use gix_hash::ObjectId;
use crate::graph::{Graph, Missing};
use crate::{Error, Result};
/// The shallow-related arguments of one fetch request.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct ShallowRequest {
/// Where the client's history is already cut, from `shallow <oid>`.
pub client_shallow: Vec<ObjectId>,
/// `deepen <n>`.
pub depth: Option<usize>,
/// `deepen-relative`: count `depth` from the client's existing boundary
/// rather than from the wants.
pub relative: bool,
/// `deepen-since <unix seconds>`.
pub since: Option<i64>,
/// `deepen-not <ref>`.
pub not: Vec<String>,
}
impl ShallowRequest {
/// Does this request say anything about shallowness at all?
pub fn is_active(&self) -> bool {
!self.client_shallow.is_empty()
|| self.depth.is_some()
|| self.since.is_some()
|| !self.not.is_empty()
}
/// Does it ask for a *change* to the boundary, as opposed to merely
/// declaring where the client's is?
pub fn is_deepening(&self) -> bool {
self.depth.is_some() || self.since.is_some() || !self.not.is_empty()
}
}
/// What the server decided about the boundary.
#[derive(Debug, Clone, Default)]
pub struct ShallowOutcome {
/// Commits the client declared shallow, whose parents are not traversed
/// at all.
pub boundary: HashSet<ObjectId>,
/// Where the **client's own** history stops, verbatim from its `shallow
/// <oid>` lines.
///
/// Not the same field as `boundary` and not redundant with it, because the
/// two bound different walks. `boundary` bounds the walk that decides what
/// to *send*, and a deepening request deliberately walks past the client's
/// cut, which is what it asked for. This one bounds the walk over the
/// client's `have`s, which may never walk past the cut: a client that said
/// `shallow X` holds `X` and none of `X`'s ancestors, so treating a `have
/// X` as proof it holds them subtracts the whole history from the pack.
pub client_boundary: HashSet<ObjectId>,
/// When a deepening was requested, exactly the commits this fetch may
/// send. Empty when the request only declared an existing boundary.
///
/// Separate from `boundary` because a merge can be cut off from one parent
/// and keep the other (`deepen-not` does exactly that), and a boundary
/// cannot express it.
pub include: HashSet<ObjectId>,
/// `shallow <oid>` lines to send: new cut points the client does not know.
pub newly_shallow: Vec<ObjectId>,
/// `unshallow <oid>` lines to send: commits that used to be cut and are
/// now complete because this fetch sends their parents.
pub unshallow: Vec<ObjectId>,
/// The parents of every commit in `unshallow`: extra tips the pack walk
/// must start from.
///
/// An `unshallow <oid>` line is a promise that the pack carries that
/// commit's parents, and the wants alone cannot deliver it. The client
/// offers its shallow tip as a `have` in the very same request, so the tip
/// is correctly excluded from the pack, and a walk seeded only with the
/// wants stops there and sends nothing, having already promised otherwise.
/// Seeding the parents is how `git-upload-pack` closes the same gap (see
/// `send_unshallow` in its `upload-pack.c`).
pub unshallow_parents: Vec<ObjectId>,
}
impl ShallowOutcome {
/// Is there a `shallow-info` section worth sending?
pub fn has_info(&self) -> bool {
!self.newly_shallow.is_empty() || !self.unshallow.is_empty()
}
}
/// git's `ref_rev_parse_rules`, which is how `deepen-not` turns the name a
/// person typed into a reference.
///
/// Copied from git's table rather than shortened: the last rule is the one a
/// mirror needs, and `{}` stands where git writes `%.*s`.
const DEEPEN_NOT_RULES: &[&str] = &[
"{}",
"refs/{}",
"refs/tags/{}",
"refs/heads/{}",
"refs/remotes/{}",
"refs/remotes/{}/HEAD",
];
/// Resolve one `deepen-not <name>` the way `git-upload-pack` does.
///
/// # The bug this replaces, and it was silent on both sides
///
/// This used to be `FullName::new(name)` followed by `refs.resolve`, with
/// `continue` on either failure. `--shallow-exclude` takes a **revision**, and
/// git's own `expand_ref` walks `ref_rev_parse_rules`, so `--shallow-exclude=side`
/// is the ordinary spelling — it is the spelling `Scene::dated`'s own table in
/// the interop suite is written in. `FullName` requires `HEAD` or `refs/…`, so
/// the short form parsed as nothing, was discarded, and the deepening ran with
/// **no exclusion at all**.
///
/// MEASURED 2026-08-05, `Scene::dated` (A─B─M─D with a side branch C),
/// `clone --shallow-exclude=side`, stock git 2.53.0 as the client:
///
/// | server | commits | `.git/shallow` |
/// |---|---|---|
/// | stock `git-upload-pack` | 2 | 2 cut points |
/// | gunnar, before | **5** | **empty** |
///
/// The client asked for a shallow clone excluding a branch and got the whole
/// history, not shallow, with no error on either end. That is the worst shape a
/// refusal can take: it is not a refusal, it is a different answer.
///
/// The unresolvable case is the same defect wearing the other face. git dies
/// with `ambiguous deepen-not: <name>`; gunnar discarded it, so
/// `--shallow-exclude=typo` silently became "exclude nothing".
///
/// # Ambiguity is an error, as it is in git
///
/// `expand_ref` counts **every** rule that matches (it only stops early when
/// `core.warnAmbiguousRefs` is off, which is not the default) and
/// `upload-pack.c` dies unless exactly one did. So a repository holding both
/// `refs/heads/x` and `refs/tags/x` refuses `deepen-not x` rather than picking
/// one, and gunnar refuses it too — silently picking would make the answer
/// depend on the order of a table.
fn resolve_deepen_not(refs: &RefSnapshot, name: &str) -> Result<ObjectId> {
let mut found: Vec<(String, ObjectId)> = Vec::new();
for rule in DEEPEN_NOT_RULES {
let candidate = rule.replace("{}", name);
// `FullName::new` was the validator here and it is gone; the rules it
// enforced live on in `refname::validate`, which is the same rule set
// in the place `locked_on_target.md`'s checklist names. The name comes from a
// fixed table with one client-supplied component, so an invalid one
// means the client's revision was not a legal ref component — skip the
// rule, exactly as before, and let the count below decide.
if gunnar_store::refname::validate(candidate.as_bytes()).is_err() {
continue;
}
if found.iter().any(|(seen, _)| seen == &candidate) {
continue;
}
if let Some(id) = refs.resolve(&candidate)? {
found.push((candidate, id));
}
}
match found.len() {
1 => Ok(found[0].1),
// Named, and reaching the client: `serve_session` turns this into an
// `ERR` pkt-line. A `deepen-not` nobody can resolve is not a detail to
// log — it is the difference between the history the client asked for
// and the one it would otherwise be given.
0 => Err(crate::Error::protocol(format!(
"deepen-not {name:?} names no reference in this repository"
))),
n => Err(crate::Error::protocol(format!(
"ambiguous deepen-not {name:?}: it names {n} references ({})",
found
.iter()
.map(|(full, _)| full.clone())
.collect::<Vec<_>>()
.join(", ")
))),
}
}
/// Work out the boundary for a request.
pub(crate) fn compute(
graph: &Graph<'_>,
refs: &RefSnapshot,
want_commits: &[ObjectId],
request: &ShallowRequest,
) -> Result<ShallowOutcome> {
let client_shallow: HashSet<ObjectId> = request.client_shallow.iter().copied().collect();
if !request.is_deepening() {
// The client is only telling us where it is already cut. Traversal
// stops there so the pack neither contains nor requires the ancestors
// it grafted away.
return Ok(ShallowOutcome {
boundary: client_shallow.clone(),
client_boundary: client_shallow,
include: HashSet::new(),
newly_shallow: Vec::new(),
unshallow: Vec::new(),
unshallow_parents: Vec::new(),
});
}
// `deepen-not <ref>` excludes a ref's whole ancestry.
let mut excluded: HashSet<ObjectId> = HashSet::new();
for name in &request.not {
let tip = resolve_deepen_not(refs, name)?;
let closure = graph.commit_closure(
&[tip],
&HashSet::new(),
&HashSet::new(),
None,
Missing::Skip,
)?;
excluded.extend(closure.ids);
}
let max_depth = request.depth;
let mut depth_of: HashMap<ObjectId, usize> = HashMap::new();
let mut queue: VecDeque<ObjectId> = VecDeque::new();
let mut boundary: HashSet<ObjectId> = HashSet::new();
let mut reached: HashSet<ObjectId> = HashSet::new();
// With `deepen-relative` the wants start at depth 0 and the counter only
// starts once the walk crosses the client's existing boundary; without it
// the wants themselves are depth 1, which is what makes `--depth=1` send
// exactly the tips. Both are the same rule with a different seed.
let seed_depth = if request.relative { 0 } else { 1 };
for want in want_commits {
if excluded.contains(want) {
continue;
}
// **The date cut applies to the WANT itself, not only to its parents.**
//
// `deepen-since` is `rev-list --max-age=<since>` in git, and a commit
// older than the cutoff is not *listed* — being a tip does not exempt
// it. gunnar seeded every want unconditionally and tested only parents'
// dates, so a request whose tip predates the cutoff was answered with
// that tip: the client asked for commits newer than a date and was
// handed one older than it, cut as shallow, with no error at either
// end.
//
// MEASURED 2026-08-05, git 2.53.0, three commits dated
// 1700001000/2000/3000 and `--shallow-since=@1700009000`:
//
// | server | result |
// |---|---|
// | stock `git-upload-pack` | `fatal: no commits selected for shallow requests` |
// | gunnar, before | a 1-commit clone of a commit older than the cutoff |
//
// The refusal below is the other half: with every want cut away there
// is nothing to select, and that is precisely when git dies rather
// than serving a smaller answer.
if let Some(since) = request.since {
match graph.commit(want) {
Ok(facts) if facts.committed_at < since => continue,
Ok(_) => {}
Err(crate::Error::ObjectMissing { .. }) => continue,
Err(err) => return Err(err),
}
}
if depth_of.insert(*want, seed_depth).is_none() {
queue.push_back(*want);
}
}
// git's `deepen_by_rev_list` dies when its rev-list comes back empty, and
// says so by name. Serving an empty pack instead would tell the client the
// request succeeded and it already has everything, which is a wrong answer
// it cannot detect — the silent half of the same defect as the seeding
// above. Only reachable when a date or an exclusion removed every want;
// `--depth` cannot, because it cuts below the wants and never at them.
if queue.is_empty() && !want_commits.is_empty() {
return Err(Error::protocol(
"no commits selected for shallow requests: deepen-since and deepen-not between them \
exclude every requested tip",
));
}
while let Some(id) = queue.pop_front() {
reached.insert(id);
let depth = depth_of[&id];
if max_depth.is_some_and(|max| depth >= max) {
boundary.insert(id);
continue;
}
let facts = match graph.commit(&id) {
Ok(facts) => facts,
Err(crate::Error::ObjectMissing { .. }) => {
boundary.insert(id);
continue;
}
Err(err) => return Err(err),
};
let mut cut_here = false;
let child_depth = if request.relative && depth == 0 && !client_shallow.contains(&id) {
0
} else {
depth + 1
};
for parent in facts.parents {
if excluded.contains(&parent) {
cut_here = true;
continue;
}
if let Some(since) = request.since {
match graph.commit(&parent) {
Ok(parent_facts) if parent_facts.committed_at < since => {
cut_here = true;
continue;
}
Ok(_) => {}
Err(crate::Error::ObjectMissing { .. }) => {
cut_here = true;
continue;
}
Err(err) => return Err(err),
}
}
if !graph.contains(&parent)? {
cut_here = true;
continue;
}
if let std::collections::hash_map::Entry::Vacant(slot) = depth_of.entry(parent) {
slot.insert(child_depth);
queue.push_back(parent);
}
}
if cut_here {
boundary.insert(id);
}
}
// A boundary commit with no parents is not shallow. It is a root, and
// telling the client its root is grafted makes every later fetch of that
// repository ask for a parent that does not exist.
let mut newly_shallow: Vec<ObjectId> = boundary
.iter()
.filter(|id| !client_shallow.contains(*id))
.filter(|id| {
graph
.commit(id)
.map(|facts| !facts.parents.is_empty())
.unwrap_or(false)
})
.copied()
.collect();
newly_shallow.sort();
let mut unshallow: Vec<ObjectId> = client_shallow
.iter()
.filter(|id| reached.contains(*id) && !boundary.contains(*id))
.copied()
.collect();
unshallow.sort();
// The parents of everything being unshallowed. Bounded by `reached`
// because that is what this request decided it may send: a commit is only
// in `unshallow` when none of its parents was cut, so this loop finds them
// all there, and the filter is a guard rather than a narrowing.
let mut unshallow_parents: Vec<ObjectId> = Vec::new();
for id in &unshallow {
for parent in graph.commit(id)?.parents {
if reached.contains(&parent) && !unshallow_parents.contains(&parent) {
unshallow_parents.push(parent);
}
}
}
Ok(ShallowOutcome {
// Deliberately empty: `include` already says exactly which commits this
// fetch may send, and `boundary` stops *every* parent of the commits
// in it. Returning the cut set here as well would drop the surviving
// parent of a merge that `deepen-not` only half-cut, the same
// conflation `Graph::commit_closure` warns about.
boundary: HashSet::new(),
client_boundary: client_shallow,
include: reached,
newly_shallow,
unshallow,
unshallow_parents,
})
}