nordisk/gunnar

crates/gunnar-client/src/objects.rs

//! Which objects a push has to carry.
//!
//! `send-pack` sends `want − have`: everything reachable from the new tips that
//! is not already reachable from what the remote advertised. Getting this wrong
//! in the two directions is not symmetric:
//!
//! * **too few**: the remote's connectivity check fails and the push is
//!   rejected with `missing necessary objects`. Loud, but only at the far end.
//! * **too many**: the push is larger than it needed to be, and completely
//!   correct. `receive-pack` accepts a pack containing objects it already has.
//!
//! So every approximation here is taken on the *over*-sending side, deliberately.
//!
//! # The shape
//!
//! Commits are subtracted exactly, with `gix`'s own hidden-tip revision walk.
//! Trees and blobs are subtracted by **boundary**: the trees reachable from the
//! commits at the edge of the new history (the remote's tips, and the parents
//! of new commits that the remote already had) are marked as present, and
//! everything else under the new commits is sent. In the ordinary case (new work
//! on top of what the remote has) the boundary tree shares almost everything
//! with the new ones, so this sends the changed paths and nothing more; in the
//! pathological case it sends more than git would, and is still correct.
//!
//! **Deltas are not produced.** The pack is whole objects. That is a legal pack
//! every git reads, and the open question on delta compression says measure
//! before assuming deltas
//! are needed at all. This is the honest starting point, not an oversight.

use std::collections::HashSet;

use gix::hash::ObjectId;
use gix::objs::{Exists, Find, FindHeader, Kind};

use crate::error::{Error, Result};

/// What a push will carry, and the reasoning that produced it.
#[derive(Debug, Clone, Default)]
pub struct ObjectPlan {
    /// Every object to put in the pack, in an order safe for a non-delta pack
    /// (any order is, but this one puts a commit before the tree it names).
    pub ids: Vec<ObjectId>,
    /// The commits that are new to the remote.
    pub new_commits: Vec<ObjectId>,
    /// The commits treated as already present, the subtraction's basis.
    pub boundary: Vec<ObjectId>,
}

impl ObjectPlan {
    /// Nothing to send. A push whose every command is already at its target.
    pub fn is_empty(&self) -> bool {
        self.ids.is_empty()
    }
}

/// Plan the pack for `wants`, subtracting everything reachable from `haves`.
///
/// `haves` that the local repository does not have are dropped. An oid the
/// client has never seen cannot bound a traversal, and treating it as a boundary
/// would silently under-send.
pub fn plan_objects(
    repo: &gix::Repository,
    wants: &[ObjectId],
    haves: &[ObjectId],
) -> Result<ObjectPlan> {
    let mut want_commits: Vec<ObjectId> = Vec::new();
    // Objects named by a ref that are not commits: annotated tags (very common)
    // and, legally if rarely, a tree or a blob.
    let mut extra_roots: Vec<ObjectId> = Vec::new();

    for want in wants {
        if want.is_null() {
            continue;
        }
        peel_root(repo, *want, &mut want_commits, &mut extra_roots)?;
    }

    let mut have_commits: Vec<ObjectId> = Vec::new();
    for have in haves {
        if have.is_null() || !repo.objects.exists(have) {
            continue;
        }
        // A `have` that peels to nothing useful is simply not a boundary.
        let mut sink = Vec::new();
        let _ = peel_root(repo, *have, &mut have_commits, &mut sink);
    }
    want_commits.sort();
    want_commits.dedup();
    have_commits.sort();
    have_commits.dedup();

    if want_commits.is_empty() && extra_roots.is_empty() {
        return Ok(ObjectPlan::default());
    }

    // ── commits: subtracted exactly ─────────────────────────────────────────
    let mut new_commits: Vec<ObjectId> = Vec::new();
    let mut new_set: HashSet<ObjectId> = HashSet::new();
    let mut parents_of_new: Vec<ObjectId> = Vec::new();
    if !want_commits.is_empty() {
        let walk = repo
            .rev_walk(want_commits.iter().copied())
            .with_hidden(have_commits.iter().copied())
            .all()
            .map_err(|e| Error::repo("walk the commits being pushed", e))?;
        for info in walk {
            let info = info.map_err(|e| Error::repo("read a commit during the push walk", e))?;
            new_set.insert(info.id);
            new_commits.push(info.id);
            parents_of_new.extend(info.parent_ids.iter().copied());
        }
    }

    // ── the boundary: what the remote is assumed to already hold ────────────
    let mut boundary: Vec<ObjectId> = have_commits.clone();
    for p in parents_of_new {
        if !new_set.contains(&p) {
            boundary.push(p);
        }
    }
    boundary.sort();
    boundary.dedup();

    let mut seen: HashSet<ObjectId> = HashSet::new();
    for b in &boundary {
        if !repo.objects.exists(b) {
            continue;
        }
        if let Some(tree) = commit_tree(repo, *b)? {
            mark_reachable(repo, tree, &mut seen)?;
        }
    }

    // ── what to send ────────────────────────────────────────────────────────
    let mut ids: Vec<ObjectId> = Vec::new();
    let mut emitted: HashSet<ObjectId> = HashSet::new();
    for commit in &new_commits {
        if emitted.insert(*commit) {
            ids.push(*commit);
        }
        if let Some(tree) = commit_tree(repo, *commit)? {
            collect_reachable(repo, tree, &mut seen, &mut emitted, &mut ids)?;
        }
    }
    for root in &extra_roots {
        // Tag objects, and the odd ref that points straight at a tree or blob.
        if !emitted.insert(*root) {
            continue;
        }
        ids.push(*root);
        let kind = object_kind(repo, *root)?;
        if matches!(kind, Kind::Tree) {
            collect_reachable(repo, *root, &mut seen, &mut emitted, &mut ids)?;
        }
    }

    Ok(ObjectPlan {
        ids,
        new_commits,
        boundary,
    })
}

/// Follow a ref's target down to the commit(s) it stands for, recording any
/// non-commit objects passed through (annotated tags) so they get packed too.
///
/// An annotated tag that is not itself sent leaves the remote with a ref
/// pointing at an object it does not have, a broken push that the connectivity
/// check catches, but only after the pack has been transferred.
fn peel_root(
    repo: &gix::Repository,
    id: ObjectId,
    commits: &mut Vec<ObjectId>,
    extra: &mut Vec<ObjectId>,
) -> Result<()> {
    let mut current = id;
    // Tag chains are legal and are bounded in practice; the counter stops a
    // corrupt repository from looping forever rather than expressing a limit.
    for _ in 0..32 {
        match object_kind(repo, current)? {
            Kind::Commit => {
                commits.push(current);
                return Ok(());
            }
            Kind::Tag => {
                extra.push(current);
                let mut buf = Vec::new();
                let obj = repo
                    .objects
                    .try_find(&current, &mut buf)
                    .map_err(|e| Error::repo(format!("read tag {current}"), e))?
                    .ok_or_else(|| Error::repo_msg(format!("tag {current} is missing")))?;
                let tag = gix::objs::TagRef::from_bytes(obj.data, repo.object_hash())
                    .map_err(|e| Error::repo(format!("parse tag {current}"), e))?;
                current = tag.target();
            }
            Kind::Tree | Kind::Blob => {
                extra.push(current);
                return Ok(());
            }
        }
    }
    Err(Error::repo_msg(format!(
        "tag chain from {id} is more than 32 deep; refusing to follow it further"
    )))
}

fn object_kind(repo: &gix::Repository, id: ObjectId) -> Result<Kind> {
    repo.objects
        .try_header(&id)
        .map_err(|e| Error::repo(format!("read the header of {id}"), e))?
        .map(|h| h.kind)
        .ok_or_else(|| {
            Error::repo_msg(format!(
                "object {id} is named by a ref being pushed but is not in this repository"
            ))
        })
}

/// The tree of a commit, or `None` if `id` is not a commit.
fn commit_tree(repo: &gix::Repository, id: ObjectId) -> Result<Option<ObjectId>> {
    let mut buf = Vec::new();
    let Some(obj) = repo
        .objects
        .try_find(&id, &mut buf)
        .map_err(|e| Error::repo(format!("read commit {id}"), e))?
    else {
        return Ok(None);
    };
    if obj.kind != Kind::Commit {
        return Ok(None);
    }
    let commit = gix::objs::CommitRef::from_bytes(obj.data, repo.object_hash())
        .map_err(|e| Error::repo(format!("parse commit {id}"), e))?;
    Ok(Some(commit.tree()))
}

/// Record every tree and blob under `tree` in `seen`, without collecting them.
fn mark_reachable(
    repo: &gix::Repository,
    tree: ObjectId,
    seen: &mut HashSet<ObjectId>,
) -> Result<()> {
    let mut ignored_ids = Vec::new();
    let mut ignored_emitted = HashSet::new();
    walk_tree(
        repo,
        tree,
        seen,
        &mut ignored_emitted,
        &mut ignored_ids,
        false,
    )
}

/// Collect every tree and blob under `tree` that is not already in `seen`.
fn collect_reachable(
    repo: &gix::Repository,
    tree: ObjectId,
    seen: &mut HashSet<ObjectId>,
    emitted: &mut HashSet<ObjectId>,
    out: &mut Vec<ObjectId>,
) -> Result<()> {
    walk_tree(repo, tree, seen, emitted, out, true)
}

/// The one tree walk both directions share (one implementation): mark-only and
/// collect differ by a boolean, not by a second copy of the traversal.
///
/// Submodule entries (`Kind::Commit` in a tree) are **skipped**: the object is in
/// another repository by definition, and packing it is impossible rather than
/// merely wasteful.
fn walk_tree(
    repo: &gix::Repository,
    tree: ObjectId,
    seen: &mut HashSet<ObjectId>,
    emitted: &mut HashSet<ObjectId>,
    out: &mut Vec<ObjectId>,
    collect: bool,
) -> Result<()> {
    let mut stack = vec![tree];
    let mut buf = Vec::new();
    while let Some(id) = stack.pop() {
        if !seen.insert(id) {
            continue;
        }
        if collect && emitted.insert(id) {
            out.push(id);
        }
        let Some(obj) = repo
            .objects
            .try_find(&id, &mut buf)
            .map_err(|e| Error::repo(format!("read tree {id}"), e))?
        else {
            // A missing tree under a commit that is being pushed is a corrupt
            // repository, but the honest place to report it is the pack writer,
            // which names the object. Skipping here would send a pack that fails
            // the remote's connectivity check with no local diagnosis at all.
            return Err(Error::repo_msg(format!(
                "object {id} is reachable from a commit being pushed but is missing locally"
            )));
        };
        if obj.kind != Kind::Tree {
            continue;
        }
        for entry in gix::objs::TreeRefIter::from_bytes(obj.data, repo.object_hash()) {
            let entry = entry.map_err(|e| Error::repo(format!("parse tree {id}"), e))?;
            let child = entry.oid.to_owned();
            if entry.mode.is_commit() {
                continue; // submodule gitlink, not ours to pack
            }
            if entry.mode.is_tree() {
                stack.push(child);
            } else if seen.insert(child) && collect && emitted.insert(child) {
                out.push(child);
            }
        }
    }
    Ok(())
}