nordisk/edda

crates/gunnar-bitmap/src/reachability.rs

//! The reachability half: `want`/`have` as set arithmetic.
//!
//! This is the point of the whole crate. Answering a fetch normally means
//! walking the commit graph from every `want`, then walking again from every
//! `have` to subtract. With a bitmap index it is:
//!
//! ```text
//! send = (bitmap(w1) | bitmap(w2) | ...) & !(bitmap(h1) | bitmap(h2) | ...)
//! ```
//!
//! which touches each commit's bitmap once and never reads an object.
//!
//! # Which positions go in, which come out
//!
//! `wants` and `haves` are commit positions in the **`.idx`** — the same space
//! as [`crate::Entry::commit_index_pos`]. The [`Selection::objects`] that comes
//! back is addressed by **pack** position. Converting the result needs
//! [`crate::PackOrder`]; see [`crate::file`] for why the format mixes the two.
//!
//! # What this module deliberately does not do
//!
//! git falls back to a partial graph walk when a `want` has no stored bitmap:
//! it walks down from that commit until it reaches commits that *do* have one,
//! adding the objects it passes by hand. That fallback needs an object database,
//! and an object database is precisely the dependency that would stop this crate
//! from being liftable. So [`Reachability::objects_to_send`] reports the
//! positions it could not satisfy instead of guessing, and the caller — who has
//! the odb — completes them.
//!
//! Silently returning the bitmapped part would be the dangerous shape: a
//! *smaller* object set that looks like a successful answer, and a fetch that
//! ships a pack the client cannot use.

use crate::{Bitmap, Index};

/// Set operations over a parsed bitmap index.
#[derive(Clone, Copy, Debug)]
pub struct Reachability<'a> {
    index: &'a Index,
}

/// What a `want`/`have` query produced.
#[derive(Clone, Debug)]
pub struct Selection {
    /// Objects to send: reachable from the wants, not from the haves.
    pub objects: Bitmap,
    /// Want positions with no stored bitmap. Empty means the answer is complete.
    pub unsatisfied_wants: Vec<u32>,
    /// Have positions with no stored bitmap.
    ///
    /// These are the dangerous ones in the other direction: an unsubtracted
    /// `have` means sending objects the client already has. That is waste, not
    /// corruption, so it is reported rather than refused.
    pub unsatisfied_haves: Vec<u32>,
}

impl Selection {
    /// Whether every want and have was answered from the index alone.
    pub fn is_complete(&self) -> bool {
        self.unsatisfied_wants.is_empty() && self.unsatisfied_haves.is_empty()
    }
}

impl<'a> Reachability<'a> {
    /// Borrow an index for querying.
    pub fn new(index: &'a Index) -> Self {
        Reachability { index }
    }

    /// Union of the bitmaps of the given `.idx` commit positions, plus the ones
    /// that had no stored bitmap.
    pub fn union(&self, positions: impl IntoIterator<Item = u32>) -> (Bitmap, Vec<u32>) {
        let mut acc = Bitmap::new();
        let mut missing = Vec::new();
        for pos in positions {
            match self.index.bitmap_for_commit(pos) {
                Some(b) => acc.or_with(&b),
                None => missing.push(pos),
            }
        }
        (acc, missing)
    }

    /// `wants` minus `haves`, both given as `.idx` positions of commits.
    ///
    /// The resulting bitmap is addressed by pack position.
    pub fn objects_to_send(
        &self,
        wants: impl IntoIterator<Item = u32>,
        haves: impl IntoIterator<Item = u32>,
    ) -> Selection {
        let (mut objects, unsatisfied_wants) = self.union(wants);
        let (excluded, unsatisfied_haves) = self.union(haves);
        objects.and_not_with(&excluded);
        Selection {
            objects,
            unsatisfied_wants,
            unsatisfied_haves,
        }
    }

    /// Restrict a set to one object type, using the index's type bitmaps.
    ///
    /// This is how a pack writer learns which of the selected positions are
    /// commits, trees, blobs or tags without reading a single object header.
    pub fn of_type(&self, set: &Bitmap, kind: crate::kind::Kind) -> Bitmap {
        let mut out = set.clone();
        let mut keep = Bitmap::new();
        keep.or_ewah(self.index.type_bitmap(kind));
        out.and_with(&keep);
        out
    }

    /// Count the selection per object type: commits, trees, blobs, tags.
    pub fn counts_by_type(&self, set: &Bitmap) -> [u64; 4] {
        use crate::kind::Kind::*;
        [Commit, Tree, Blob, Tag].map(|k| self.of_type(set, k).count_ones())
    }
}