crates/storage-git-gix/src/bitmap.rs
//! The `.bitmap` reachability index: **writing** one beside a pack, and
//! **reading** it on the serve path instead of walking twice.
//!
//! **Provenance.** Lifted from two quarantined files —
//! `parked-gix-2/gunnar-store-gix/src/bitmap.rs` (the reader pairing and
//! the cache) and `parked-gix-2/gunnar-wire-gix/bitmap.rs` (the
//! `want`/`have` answer). What changed on the lift is named at the bottom.
//!
//! # The three pieces, and why they are three
//!
//! `gunnar-bitmap` is the format and the set algebra, and it is deliberately
//! **blind** (D21, so it stays liftable into gitoxide): it never opens a pack,
//! never resolves an object id and never walks a graph. It can say what bit 4711
//! is set to and not what object that is.
//!
//! [`PackBitmap`] is the pairing that gives the bits names — the parsed
//! `.bitmap`, the `.idx` beside it, and the permutation between the two position
//! spaces. [`select`] is the third piece, the one that needs an object database
//! and therefore the part neither of the others may contain:
//!
//! ```text
//! send = (bitmap(w) | walked(w)) & !(bitmap(h) | walked(h))
//! ```
//!
//! # The miss is a bounded walk, not a full one
//!
//! A `want` whose commit has no stored bitmap is the case every description of
//! this feature waves at. Git's `add_to_include_set` walks down from the
//! unbitmapped commit and **stops at the first commit that has a bitmap**, ORs
//! that bitmap in, and returns — because a stored bitmap is closed under
//! reachability, so reaching one means the entire history behind it is already
//! accounted for. The walk therefore covers only what has been pushed since the
//! last maintenance pass, whatever the size of the repository.
//!
//! Git applies the same rule one level down, in `should_include_obj`: a tree
//! whose bit is already set is not descended into. Without it the *first*
//! unbitmapped commit costs a walk of every tree and blob in the repository and
//! the bounded commit walk buys nothing. [`accumulate`] gets that ordering right
//! by construction: the commit walk runs to completion **first**, so every
//! stored bitmap this request will ever OR in is in place before a single tree
//! is opened.
//!
//! # The extended index
//!
//! A bitmap position names an object **in one pack**. A fetch can perfectly well
//! involve objects that are not in it: anything pushed since the last
//! maintenance pass, or a loose object. Git's answer is `ext_index_add_object` —
//! hand those a position past the end of the pack — and it is the right one,
//! because it keeps *everything* in one position space and so keeps the final
//! subtraction a single `AND NOT`. [`Positions`] is that index.
//!
//! # It never truncates. It declines.
//!
//! Every case a bitmap cannot answer exactly returns `Ok(None)` from [`select`]
//! and the caller walks: a `want` that is not a commit, a tag, a tree or a blob;
//! an extended index that overflowed `u32`. A **wrong** object set is the one
//! failure nothing downstream can see — the pack indexes, `fsck`s and applies,
//! and the client's working tree is wrong — so the fallback is not a nicety.
//!
//! # Changed on the lift
//!
//! * `crate::Error` → `anyhow`, `ObjectStore` → `gix_object::Find`.
//! * **The walk is `crate::graph::walk`, not a second traversal.** The
//! quarantine had `gunnar_wire::Graph::tree_closure` to reuse; this crate has
//! [`crate::graph::walk`], and the [`Seen`] trait is what lets both paths run
//! it (LAW 5).
//! * The 16-bit fanout is **not** carried over. `crate::fanout`'s own record is
//! that the 3–4× on `pack_position` moved a negotiated fetch by 1.0016× against
//! a within-arm spread of 1.009–1.028, so a second copy of the choice here
//! would be 256 KiB per pack and a fork in the code buying nothing measurable.
//! * `Vouch` — the lazy `client_has` that never materialises object ids — is
//! gone, because the frozen contract's `ReachSet::client_has` is
//! `Vec<Vec<u8>>` and there is nowhere to put a bitmap. It is the one thing
//! the quarantine could do that this cannot; on a clone `have` is empty and it
//! costs nothing, on a fetch it costs one `Vec` of what the client holds.
mod write;
pub use write::write_for_pack;
use std::collections::HashMap;
use std::path::{Path, PathBuf};
use anyhow::{anyhow, Context, Result};
use gix_hash::ObjectId;
use gunnar_bitmap::{Bitmap, PackOrder};
use crate::graph::{Commits, Seen, Selection};
/// Where a `.bitmap` goes for a given `.idx`.
///
/// `pack-<id>.bitmap`, beside the pack and named for it, which is what `gix-odb`
/// and stock `git` both look for.
pub fn path_for(index_path: &Path) -> PathBuf {
index_path.with_extension("bitmap")
}
/// A pack's `.bitmap`, paired with the `.idx` that gives its bits names.
///
/// # Two checks at open, and both of them can fail on a live repository
///
/// * the **trailing checksum**, because a truncated `.bitmap` parses clean — the
/// object count is nowhere in the file, so lopping the tail off yields a
/// valid-looking index over fewer objects;
/// * the **pack checksum**, because a `.bitmap` names the pack it describes and
/// nothing stops a stale one sitting beside a rewritten pack. Positions would
/// then resolve against the wrong `.idx`, which is a set of the right size made
/// of the wrong objects — the quietest failure in this whole area.
///
/// Either failure is `Ok(None)`: no bitmap, serve by walking, which is what
/// every repository did before this existed.
pub struct PackBitmap {
index: gunnar_bitmap::Index,
idx: gix_pack::index::File,
order: PackOrder,
/// `.idx` position → row in `gunnar_bitmap::Index::entries`.
///
/// `Index::entry_index_of_commit` is a linear scan over the entries, and it
/// says so; a fetch asks it once per want and once per have, so a map built
/// once at open is the difference between `O(wants × entries)` and
/// `O(wants)`.
entry_of: HashMap<u32, usize>,
}
impl std::fmt::Debug for PackBitmap {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("PackBitmap")
.field("objects", &self.idx.num_objects())
.field("stored_bitmaps", &self.index.entries().len())
.finish()
}
}
impl PackBitmap {
/// Open the `.bitmap` beside `index_path`, if there is a usable one.
pub fn at(index_path: &Path, hash_kind: gix_hash::Kind) -> Result<Option<Self>> {
let bitmap_path = path_for(index_path);
if !bitmap_path.exists() {
return Ok(None);
}
let idx = gix_pack::index::File::at(index_path, hash_kind)
.with_context(|| format!("open pack index {}", index_path.display()))?;
let data = std::fs::read(&bitmap_path)
.with_context(|| format!("read {}", bitmap_path.display()))?;
let index = match gunnar_bitmap::Index::from_bytes(&data, hash_kind) {
Ok(index) => index,
Err(err) => {
tracing::warn!(
event = "bitmap.unparseable",
error = %err,
bitmap = %bitmap_path.display(),
"a .bitmap beside this pack could not be parsed; serving by walking"
);
return Ok(None);
}
};
if let Err(err) = index.verify_checksum() {
tracing::warn!(
event = "bitmap.checksum",
error = %err,
bitmap = %bitmap_path.display(),
"a .bitmap beside this pack failed its own checksum; serving by walking"
);
return Ok(None);
}
if index.pack_checksum() != idx.pack_checksum() {
tracing::warn!(
event = "bitmap.wrong_pack",
bitmap = %bitmap_path.display(),
"a .bitmap beside this pack describes a different pack; serving by walking"
);
return Ok(None);
}
let count = idx.num_objects() as usize;
let mut offsets = vec![0u64; count];
for entry in idx.iter() {
let at = idx.lookup(entry.oid.as_ref()).ok_or_else(|| {
anyhow!("an object the index iterated could not be looked up in it")
})? as usize;
offsets[at] = entry.pack_offset;
}
let order = PackOrder::from_index_offsets(&offsets);
let entry_of = index
.entries()
.iter()
.enumerate()
.map(|(row, e)| (e.commit_index_pos, row))
.collect();
Ok(Some(PackBitmap {
index,
idx,
order,
entry_of,
}))
}
/// Objects in the pack this bitmap describes.
///
/// Also the first position an out-of-pack object may be given; see
/// [`Positions`].
pub fn num_objects(&self) -> u32 {
self.idx.num_objects()
}
/// How many commits have a stored bitmap.
pub fn stored_bitmaps(&self) -> usize {
self.index.entries().len()
}
/// Pack position of `id`, or `None` when it is not in this pack.
pub fn pack_position(&self, id: &gix_hash::oid) -> Option<u32> {
self.order.pack_position(self.idx.lookup(id)?)
}
/// The object at pack position `pos`.
///
/// `None` for a position past the end of the pack: a bitmap's last word can
/// carry trailing bits that address nothing.
pub fn oid_at_pack_position(&self, pos: u32) -> Option<ObjectId> {
let index_pos = self.order.index_position(pos)?;
(index_pos < self.idx.num_objects()).then(|| self.idx.oid_at_index(index_pos).to_owned())
}
/// The stored bitmap for `id`, if it has one.
///
/// The returned bitmap is addressed by **pack** position and is closed under
/// reachability: a set bit means everything beneath that object is set too,
/// which is what lets a walk stop the moment it reaches a commit that has
/// one.
pub fn bitmap_for_commit(&self, id: &gix_hash::oid) -> Option<Bitmap> {
let index_pos = self.idx.lookup(id)?;
self.index.resolve(*self.entry_of.get(&index_pos)?)
}
/// The objects in `set` that are of `kind`.
///
/// Not one object is opened: which of a selection's positions are commits is
/// a fact the `.bitmap`'s four type indexes already carry, which is what
/// lets a caller name the commits in a pack it decided on by set algebra.
/// Positions past the end of the pack — the caller's extended index — are
/// dropped, because the type indexes say nothing about them.
pub fn of_type(&self, set: &Bitmap, kind: gunnar_bitmap::Kind) -> Vec<ObjectId> {
gunnar_bitmap::Reachability::new(&self.index)
.of_type(set, kind)
.iter_set_bits()
.filter_map(|pos| self.oid_at_pack_position(pos))
.collect()
}
}
/// The one [`PackBitmap`] a store hands out, reloaded when the file on disk
/// changes.
///
/// # Why a cache at all
///
/// Opening one means mapping the `.idx`, reading and parsing the whole
/// `.bitmap`, and building the pack-order permutation — `O(objects)` work, and
/// on a million-object repository that is tens of megabytes touched. A fetch
/// asks once. Paying it per fetch would make the bitmap path *slower* than the
/// walk it replaces on everything but a clone, which is the shape of
/// optimisation that ships and then gets reverted.
///
/// # Why it cannot go stale
///
/// The key is `(path, mtime, len)` of the `.bitmap` itself, re-`stat`ed on every
/// call. A maintenance pass writes a new pack under a new name, so the path
/// changes; one that rewrites in place changes both other fields. A stale bitmap
/// is not a slow answer, it is a **wrong** one, so the cheap check is not
/// optional. [`PackBitmap::at`] then checks the pack checksum as well, which is
/// the same question asked of the content rather than of the metadata.
///
/// A `None` is cached too. A repository with no bitmap, or with a damaged one,
/// must not re-`read_dir` and re-parse on every request to rediscover that.
#[derive(Debug, Default)]
pub struct BitmapCache {
inner: std::sync::RwLock<Option<Cached>>,
}
#[derive(Debug)]
struct Cached {
key: Key,
/// `None` means "there is no usable bitmap here", cached deliberately.
bitmap: Option<std::sync::Arc<PackBitmap>>,
}
#[derive(Debug, PartialEq, Eq)]
struct Key {
index_path: PathBuf,
mtime: Option<std::time::SystemTime>,
len: u64,
}
impl BitmapCache {
/// The bitmap for `pack_dir`, loading or reloading it if what is on disk has
/// changed.
///
/// `None` when there is not exactly one `.bitmap` in the directory. Zero is
/// the ordinary case for a repository that has never had a maintenance pass.
/// More than one is a store whose packs were bitmapped separately, and
/// choosing between them is a decision with no right answer here: the two
/// address different position spaces and neither covers the other's objects,
/// which is what a multi-pack index exists to fix.
pub fn get(
&self,
pack_dir: &Path,
hash_kind: gix_hash::Kind,
) -> Option<std::sync::Arc<PackBitmap>> {
let mut found: Option<PathBuf> = None;
for entry in std::fs::read_dir(pack_dir).ok()?.flatten() {
let path = entry.path();
if path.extension().is_some_and(|x| x == "bitmap") {
if found.is_some() {
return None;
}
found = Some(path);
}
}
let bitmap_path = found?;
let meta = std::fs::metadata(&bitmap_path).ok()?;
let key = Key {
index_path: bitmap_path.with_extension("idx"),
mtime: meta.modified().ok(),
len: meta.len(),
};
if let Ok(guard) = self.inner.read() {
if let Some(cached) = guard.as_ref() {
if cached.key == key {
return cached.bitmap.clone();
}
}
}
let loaded = PackBitmap::at(&key.index_path, hash_kind)
.map_err(|err| {
tracing::warn!(
event = "bitmap.unopenable",
error = %err,
pack = %key.index_path.display(),
"a .bitmap beside this pack could not be opened; serving by walking"
);
})
.ok()
.flatten()
.map(std::sync::Arc::new);
if let Ok(mut guard) = self.inner.write() {
*guard = Some(Cached {
key,
bitmap: loaded.clone(),
});
}
loaded
}
/// Forget what is cached, so the next [`BitmapCache::get`] re-reads the
/// directory.
///
/// The `(path, mtime, len)` key already catches a bitmap that moved or was
/// rewritten, but it cannot catch one that was **removed**: with no
/// `.bitmap` in the directory `get` returns before it ever builds a key, so
/// the stale entry would never be compared against anything. A maintenance
/// pass that unlinks a bitmap calls this.
pub fn clear(&self) {
if let Ok(mut guard) = self.inner.write() {
*guard = None;
}
}
}
// ── the query ────────────────────────────────────────────────────────────────
/// The position space a bitmap selection works in.
///
/// The pack's own positions, `0..num_objects`, extended with one position per
/// object the request touched that is not in the pack. Git calls the second half
/// `ext_index`.
struct Positions<'a> {
bitmap: &'a PackBitmap,
/// First position handed out to an object outside the pack.
base: u32,
/// `extra[i]` is the object at position `base + i`.
extra: Vec<ObjectId>,
of: HashMap<ObjectId, u32>,
/// Set if the extended index ran out of `u32`. See [`Positions::intern`].
overflowed: bool,
}
impl<'a> Positions<'a> {
fn new(bitmap: &'a PackBitmap) -> Self {
Positions {
base: bitmap.num_objects(),
bitmap,
extra: Vec::new(),
of: HashMap::new(),
overflowed: false,
}
}
/// The position of `id`, without giving it one.
fn get(&self, id: &gix_hash::oid) -> Option<u32> {
self.bitmap
.pack_position(id)
.or_else(|| self.of.get(id.as_ref()).copied())
}
/// The position of `id`, giving it one past the end of the pack if it has
/// none.
///
/// A position is a `u32` because a bitmap bit is, so an extended index that
/// walked past `u32::MAX` would silently alias two objects onto one bit — a
/// pack of the right size made of the wrong objects, the failure this whole
/// area is prone to. It cannot happen with a `.idx` that already counts its
/// objects in a `u32`, so this **records** the impossible rather than
/// erroring in the hot path; [`select`] abandons the whole selection if it
/// is ever set, and the walk answers instead.
fn intern(&mut self, id: &ObjectId) -> u32 {
if let Some(pos) = self.get(id) {
return pos;
}
match u32::try_from(self.base as u64 + self.extra.len() as u64) {
Ok(pos) => {
self.extra.push(*id);
self.of.insert(*id, pos);
pos
}
Err(_) => {
self.overflowed = true;
u32::MAX
}
}
}
/// The object at `pos`, or `None` for a bit that names nothing.
fn oid(&self, pos: u32) -> Option<ObjectId> {
if pos < self.base {
self.bitmap.oid_at_pack_position(pos)
} else {
self.extra.get((pos - self.base) as usize).copied()
}
}
}
/// A walk that records into a bitmap and stops at anything already covered.
///
/// The `false` return is doing two different jobs, and both matter:
///
/// * *already in this side's set* — the ordinary "visited once" duty every walk
/// has, except that here the bit may have been set not by this walk but by a
/// whole commit bitmap OR'd in earlier. **That is what bounds the walk.**
/// * *in the other side's set* — the client already holds it, so neither send it
/// nor open it. Git's `should_include_obj`, and the reason a fetch does not
/// re-walk shared history.
struct BitSeen<'a, 'b> {
positions: &'a mut Positions<'b>,
base: &'a mut Bitmap,
/// The `have` side, when this is the `want` side. Git's
/// `include_data.seen`.
other: Option<&'a Bitmap>,
}
impl Seen for BitSeen<'_, '_> {
fn seen(&self, id: &ObjectId) -> bool {
self.positions
.get(id)
.is_some_and(|pos| self.base.get(pos) || self.other.is_some_and(|o| o.get(pos)))
}
fn insert(&mut self, id: &ObjectId) -> bool {
let pos = self.positions.intern(id);
if self.base.get(pos) {
return false;
}
if self.other.is_some_and(|other| other.get(pos)) {
return false;
}
self.base.set(pos);
true
}
}
/// One side of the query — the wants, or the haves — as a bitmap.
struct Side {
/// Every position reachable from the roots.
bits: Bitmap,
/// The commits this side had to walk because they had no stored bitmap, in
/// discovery order. Commits *inside* an OR'd bitmap are not here and do not
/// need to be: they are bits, and their type is in the pack's type index.
walked_commits: Vec<ObjectId>,
}
/// What [`select`] did, for a caller that has to be able to tell the two paths
/// apart.
///
/// Both answer identically by construction — that is the whole safety argument —
/// so **no object set, no wire byte and no exit code can say which one ran**.
/// This can, and `crate::GixStore`'s counters expose it, because a bitmap path
/// that silently stopped being taken is `P-027` exactly (*"five instruments
/// measured the walk path and published it as the bitmap path"*).
#[derive(Debug, Clone, Copy, Default)]
pub struct Cost {
/// Commits opened because they had no stored bitmap. `0` on a clone of a
/// fully bitmapped repository.
pub commits_walked: usize,
/// Stored bitmaps OR'd in.
pub bitmaps_or_ed: usize,
}
/// `want` minus `have`, answered from `bitmap`.
///
/// `Ok(None)` means *this request is not one this bitmap can answer exactly* and
/// the caller must walk. See the module doc: it never truncates.
pub fn select(
bitmap: &PackBitmap,
find: &dyn gix_object::Find,
hash_kind: gix_hash::Kind,
want: &[ObjectId],
have: &[ObjectId],
) -> Result<Option<(Selection, Cost)>> {
let mut positions = Positions::new(bitmap);
let mut cost = Cost::default();
// 1. Peel the tips, exactly as the walk does. A `want` may name a tag, a
// tree or a blob, and the tag objects along the way are part of the
// answer — they are in no commit's bitmap, because a bitmap is built by
// walking trees and a tree never points at a tag.
let mut buf = Vec::with_capacity(64 * 1024);
let mut commit_tips = Vec::new();
let mut tree_tips = Vec::new();
let mut loose_tips = Vec::new();
for tip in want {
let Some(peeled) = peel(find, hash_kind, tip, &mut buf, &mut loose_tips)? else {
// A `want` this store does not hold. `crate::serve::select` has
// already refused the request in that case, so reaching here means
// the two disagree — decline rather than answer a short set.
return Ok(None);
};
match peeled.1 {
gix_object::Kind::Commit => commit_tips.push(peeled.0),
gix_object::Kind::Tree => tree_tips.push(peeled.0),
gix_object::Kind::Blob => loose_tips.push(peeled.0),
// `peel` follows tags to something that is not one.
gix_object::Kind::Tag => return Ok(None),
}
}
// 2. The same for the excludes, tolerating gaps: a `have` from a client can
// perfectly well name a commit whose ancestry that client does not hold,
// and an unsubtracted `have` is waste rather than corruption.
let mut exclude_commits = Vec::new();
let mut exclude_loose = Vec::new();
for id in have {
// A `have` naming a tree or a blob subtracts only itself here rather than
// its closure, and one this store does not hold subtracts nothing.
// Over-sending is the safe direction, and the walk path treats such a
// `have` as a full stop-set root — so this is one place the two can
// differ, always by this path sending *more*.
// `tests/bitmap_and_walk_agree.rs` is built on commit haves for exactly
// that reason.
if let Some((peeled, gix_object::Kind::Commit)) =
peel(find, hash_kind, id, &mut buf, &mut exclude_loose)?
{
exclude_commits.push(peeled);
}
}
// 3. What the client already has. This is the half a walk pays
// `O(client history)` for: with a bitmap it is one OR per `have` and no
// object read at all.
let have_side = accumulate(
bitmap,
&mut positions,
find,
hash_kind,
&exclude_commits,
None,
&mut cost,
)?;
// 4. What it is about to be sent, with the haves in hand so the bounded walk
// stops at shared history rather than rediscovering it.
let want_side = accumulate(
bitmap,
&mut positions,
find,
hash_kind,
&commit_tips,
Some(&have_side.bits),
&mut cost,
)?;
let mut want_bits = want_side.bits;
// 5. A `want` that named a tree or a blob outright — a partial clone's lazy
// fetch does exactly this — and every tag object peeled through on the
// way. Both go in after the commit phase, so a bit a stored bitmap
// already set turns the tree walk away at its root.
{
let mut seen = BitSeen {
positions: &mut positions,
base: &mut want_bits,
other: Some(&have_side.bits),
};
crate::graph::walk(find, hash_kind, &tree_tips, &mut seen, &mut Commits::Ignore)?;
for id in &loose_tips {
seen.insert(id);
}
}
for id in &exclude_loose {
// A tag object the client named as a `have`: it is not in any commit
// bitmap, so nothing above subtracted it.
let pos = positions.intern(id);
want_bits.unset(pos);
}
if positions.overflowed {
// Recorded rather than trusted. See `Positions::intern`.
tracing::warn!(
event = "bitmap.ext_index_overflow",
"the extended bitmap index ran out of positions; serving by walking"
);
return Ok(None);
}
// 6. The subtraction the whole path exists for: one `AND NOT` over two
// bitmaps, where the walk needs a set of every object id the client
// holds.
let mut send = want_bits;
send.and_not_with(&have_side.bits);
// 7. Names for the bits.
let mut objects: Vec<ObjectId> = send
.iter_set_bits()
.filter_map(|p| positions.oid(p))
.collect();
// Which of them are commits. The type index answers for everything in the
// pack without opening one object; the bounded walk already named the rest.
let mut commits: Vec<ObjectId> = bitmap.of_type(&send, gunnar_bitmap::Kind::Commit);
for id in want_side
.walked_commits
.iter()
.chain(&have_side.walked_commits)
{
if positions
.get(id)
.is_some_and(|pos| pos >= positions.base && send.get(pos))
{
commits.push(*id);
}
}
let mut client_has: Vec<ObjectId> = have_side
.bits
.iter_set_bits()
.filter_map(|p| positions.oid(p))
.collect();
// Sorted, so the answer is a function of the graph and not of iteration
// order — the same promise `crate::graph::select` makes, and what lets a
// test compare the two vectors rather than two sets.
for v in [&mut objects, &mut commits, &mut client_has] {
v.sort_unstable();
v.dedup();
}
Ok(Some((
Selection {
objects,
commits,
client_has,
},
cost,
)))
}
/// Follow a tag chain to the object underneath, recording the tag objects
/// themselves into `tags`.
///
/// `None` when the object is not here at all. The chain is bounded because a tag
/// pointing at a tag is legal, a *cycle* of them is not, and this is untrusted
/// input.
fn peel(
find: &dyn gix_object::Find,
hash_kind: gix_hash::Kind,
id: &ObjectId,
buf: &mut Vec<u8>,
tags: &mut Vec<ObjectId>,
) -> Result<Option<(ObjectId, gix_object::Kind)>> {
let mut current = *id;
for _ in 0..16 {
let Some(data) = find
.try_find(¤t, buf)
.map_err(|e| anyhow!("read object {current}: {e}"))?
else {
return Ok(None);
};
if data.kind != gix_object::Kind::Tag {
return Ok(Some((current, data.kind)));
}
let target = gix_object::TagRefIter::from_bytes(data.data, hash_kind)
.target_id()
.map_err(|e| anyhow!("tag {current} has no target: {e}"))?;
tags.push(current);
current = target;
}
Ok(None)
}
/// Everything reachable from `roots`, as bits.
///
/// The two phases are the whole algorithm and their **order** is what makes it
/// bounded:
///
/// 1. walk commits, stopping at every commit that has a stored bitmap and ORing
/// that bitmap in. Nothing but commit objects is read.
/// 2. only then, walk the trees of the commits phase 1 actually had to open. By
/// now every bit any stored bitmap contributes is set, so [`BitSeen::insert`]
/// can turn a whole subtree away at its root.
///
/// Interleaving them — walking each commit's tree as the commit is reached —
/// would leave phase 2 opening trees that a bitmap OR'd in one commit later
/// would have covered, which on the first unbitmapped commit is the entire
/// repository.
fn accumulate(
bitmap: &PackBitmap,
positions: &mut Positions<'_>,
find: &dyn gix_object::Find,
hash_kind: gix_hash::Kind,
roots: &[ObjectId],
other: Option<&Bitmap>,
cost: &mut Cost,
) -> Result<Side> {
let mut bits = Bitmap::new();
let mut walked_commits = Vec::new();
let mut trees: Vec<ObjectId> = Vec::new();
let mut buf = Vec::with_capacity(64 * 1024);
let mut stack: Vec<ObjectId> = roots.to_vec();
while let Some(id) = stack.pop() {
let pos = positions.intern(&id);
if bits.get(pos) || other.is_some_and(|o| o.get(pos)) {
continue;
}
// The termination that makes this bounded rather than a full walk.
if let Some(stored) = bitmap.bitmap_for_commit(&id) {
bits.or_with(&stored);
cost.bitmaps_or_ed += 1;
continue;
}
bits.set(pos);
let Some(data) = find
.try_find(&id, &mut buf)
.map_err(|e| anyhow!("read object {id}: {e}"))?
else {
// A `have` naming a commit this store does not hold. The walk path
// skips it too, and over-sending is the safe direction.
continue;
};
if data.kind != gix_object::Kind::Commit {
continue;
}
cost.commits_walked += 1;
walked_commits.push(id);
for token in gix_object::CommitRefIter::from_bytes(data.data, hash_kind) {
match token.with_context(|| format!("parse commit {id}"))? {
gix_object::commit::ref_iter::Token::Tree { id } => trees.push(id),
gix_object::commit::ref_iter::Token::Parent { id } => stack.push(id),
_ => break,
}
}
}
{
let mut seen = BitSeen {
positions,
base: &mut bits,
other,
};
crate::graph::walk(find, hash_kind, &trees, &mut seen, &mut Commits::Ignore)?;
}
Ok(Side {
bits,
walked_commits,
})
}