gunnar_wire/

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,
    })
}