sley_odb/

lib.rs

// sley#7: untrusted-input parsing crate — fallible ops propagate errors;
// the only retained `expect`s would be documented compile-time invariants.
#![cfg_attr(not(test), deny(clippy::unwrap_used, clippy::expect_used))]

use flate2::Compression;
use flate2::read::ZlibDecoder;
use flate2::write::ZlibEncoder;
use sley_core::{GitError, MissingObjectContext, ObjectFormat, ObjectId, Result};
use sley_formats::{Bundle, BundleReference};
use sley_object::{Commit, EncodedObject, ObjectType, Tag, TreeEntries, parse_framed_object};
use sley_pack::{
    MultiPackIndex, PackBitmapIndex, PackBitmapWriter, PackFile, PackIndex, PackIndexEntry,
    PackInput, PackWrite,
};
use std::collections::{HashMap, HashSet, VecDeque};
use std::io::{Read, Seek, SeekFrom, Write};
use std::path::{Path, PathBuf};
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex, OnceLock};
use std::{env, fs};

static TEMPFILE_COUNTER: AtomicU64 = AtomicU64::new(0);

pub trait ObjectReader {
    fn read_object(&self, oid: &ObjectId) -> Result<Arc<EncodedObject>>;

    /// Graft-points seam (shallow clones today, replace refs/grafts later):
    /// `true` when history is cut at `oid`, so every walk must treat the
    /// commit as parentless even though its raw body still names parents.
    ///
    /// [`FileObjectDatabase`] answers from `$GIT_DIR/shallow`; readers that
    /// are not backed by a repository (in-memory stores, pack overlays)
    /// keep the default "no grafts".
    fn is_shallow_graft(&self, _oid: &ObjectId) -> bool {
        false
    }
}

fn implied_empty_tree_object(format: ObjectFormat, oid: &ObjectId) -> Option<Arc<EncodedObject>> {
    (*oid == ObjectId::empty_tree(format))
        .then(|| Arc::new(EncodedObject::new(ObjectType::Tree, Vec::new())))
}

fn with_missing_object_context(
    err: GitError,
    oid: ObjectId,
    context: MissingObjectContext,
) -> GitError {
    let kind = err
        .not_found_kind()
        .and_then(sley_core::NotFoundKind::missing_object_kind);
    match kind {
        Some(kind) => GitError::object_kind_not_found_in(oid, kind, context),
        None => err,
    }
}

/// Parents of a parsed commit with the graft seam applied: empty when the
/// reader cuts history at `oid` (shallow boundary), the raw parsed parents
/// otherwise.
pub fn grafted_parents<R: ObjectReader + ?Sized>(
    reader: &R,
    oid: &ObjectId,
    parents: Vec<ObjectId>,
) -> Vec<ObjectId> {
    if reader.is_shallow_graft(oid) {
        Vec::new()
    } else {
        parents
    }
}

pub trait ObjectWriter {
    /// Write `object`, returning its id. Takes `&self`: every implementation's
    /// write state (in-memory map, loose-object cache) is behind interior
    /// mutability, so a single handle can interleave reads and writes without a
    /// `&mut` borrow. This lets the merge engine read and write through one `db`
    /// instead of opening a second read-only handle that re-warms the caches.
    fn write_object(&self, object: EncodedObject) -> Result<ObjectId>;
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BundleUnbundleResult {
    pub written_objects: Vec<ObjectId>,
    pub references: Vec<BundleReference>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PackUnpackResult {
    pub written_objects: Vec<ObjectId>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PackInstallResult {
    pub pack_name: String,
    pub pack_path: PathBuf,
    pub index_path: PathBuf,
    pub promisor_path: Option<PathBuf>,
    pub object_ids: Vec<ObjectId>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RawPackInstallResult {
    pub object_ids: Vec<ObjectId>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct RawPackInstallOptions {
    pub promisor: bool,
}

pub trait RawPackInstaller {
    fn install_raw_pack(&self, pack_bytes: &[u8]) -> Result<RawPackInstallResult>;
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ObjectPrefixResolution {
    Missing,
    Unique(ObjectId),
    Ambiguous(Vec<ObjectId>),
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ObjectStorageInfo {
    pub disk_size: u64,
    pub deltabase: ObjectId,
}

impl RawPackInstaller for FileObjectDatabase {
    fn install_raw_pack(&self, pack_bytes: &[u8]) -> Result<RawPackInstallResult> {
        let result = FileObjectDatabase::install_raw_pack(self, pack_bytes)?;
        Ok(RawPackInstallResult {
            object_ids: result.object_ids,
        })
    }
}

impl RawPackInstaller for ObjectDatabase {
    fn install_raw_pack(&self, pack_bytes: &[u8]) -> Result<RawPackInstallResult> {
        let result = unpack_packfile_objects(pack_bytes, self.format, self)?;
        Ok(RawPackInstallResult {
            object_ids: result.written_objects,
        })
    }
}

pub fn verify_bundle_prerequisites<R: ObjectReader>(bundle: &Bundle, reader: &R) -> Result<()> {
    let mut missing = Vec::new();
    for prerequisite in &bundle.prerequisites {
        match reader.read_object(&prerequisite.oid) {
            Ok(object) => {
                let actual = object.object_id(bundle.format)?;
                if actual != prerequisite.oid {
                    return Err(GitError::InvalidObject(format!(
                        "bundle prerequisite {} hashes to {actual}",
                        prerequisite.oid
                    )));
                }
            }
            Err(GitError::NotFound(_)) => missing.push(prerequisite.oid),
            Err(err) => return Err(err),
        }
    }
    if missing.is_empty() {
        return Ok(());
    }
    Err(GitError::object_not_found_in(
        missing[0],
        MissingObjectContext::PackInstall,
    ))
}

pub fn unbundle_objects<R, W>(
    bundle: &Bundle,
    prerequisite_reader: &R,
    writer: &mut W,
) -> Result<BundleUnbundleResult>
where
    R: ObjectReader,
    W: ObjectWriter,
{
    verify_bundle_prerequisites(bundle, prerequisite_reader)?;
    let pack = PackFile::parse_bundle(bundle)?;
    let written_objects = write_pack_objects(pack, writer, "bundle")?.written_objects;
    Ok(BundleUnbundleResult {
        written_objects,
        references: bundle.references.clone(),
    })
}

pub fn install_bundle_pack<R>(
    bundle: &Bundle,
    prerequisite_reader: &R,
    destination: &impl RawPackInstaller,
) -> Result<BundleUnbundleResult>
where
    R: ObjectReader,
{
    verify_bundle_prerequisites(bundle, prerequisite_reader)?;
    let install = destination.install_raw_pack(&bundle.pack)?;
    Ok(BundleUnbundleResult {
        written_objects: install.object_ids,
        references: bundle.references.clone(),
    })
}

pub fn unpack_packfile_objects<W>(
    pack_bytes: &[u8],
    format: ObjectFormat,
    writer: &W,
) -> Result<PackUnpackResult>
where
    W: ObjectWriter,
{
    let pack = PackFile::parse(pack_bytes, format)?;
    write_pack_objects(pack, writer, "pack")
}

fn write_pack_objects<W>(pack: PackFile, writer: &W, source: &str) -> Result<PackUnpackResult>
where
    W: ObjectWriter,
{
    let mut written_objects = Vec::with_capacity(pack.entries.len());
    for entry in pack.entries {
        let expected = entry.entry.oid;
        let actual = writer.write_object(entry.object)?;
        if actual != expected {
            return Err(GitError::InvalidObject(format!(
                "{source} object id mismatch: expected {expected}, wrote {actual}"
            )));
        }
        written_objects.push(actual);
    }
    Ok(PackUnpackResult { written_objects })
}

pub fn collect_reachable_object_ids<R, I>(
    reader: &R,
    format: ObjectFormat,
    starts: I,
) -> Result<HashSet<ObjectId>>
where
    R: ObjectReader,
    I: IntoIterator<Item = ObjectId>,
{
    walk_reachable_objects(reader, format, starts, &HashSet::new(), |_, _| {})
}

/// [`collect_reachable_object_ids`] with a cut set: commits in `cut` are
/// collected, but the walk does not continue to their parents — the view a
/// shallow repository has of its own refs (`$GIT_DIR/shallow` of the *other*
/// side, threaded explicitly because `reader` belongs to this side).
pub fn collect_reachable_object_ids_with_cut<R, I>(
    reader: &R,
    format: ObjectFormat,
    starts: I,
    cut: &HashSet<ObjectId>,
) -> Result<HashSet<ObjectId>>
where
    R: ObjectReader,
    I: IntoIterator<Item = ObjectId>,
{
    walk_reachable_objects_with_cut(reader, format, starts, &HashSet::new(), cut, |_, _| {})
}

/// [`collect_reachable_object_ids`] with a stop set: objects in `excluded` are
/// not visited and not expanded, so the walk never sees anything reachable only
/// through them (used to truncate history at a shallow boundary).
pub fn collect_reachable_object_ids_excluding<R, I>(
    reader: &R,
    format: ObjectFormat,
    starts: I,
    excluded: &HashSet<ObjectId>,
) -> Result<HashSet<ObjectId>>
where
    R: ObjectReader,
    I: IntoIterator<Item = ObjectId>,
{
    walk_reachable_objects(reader, format, starts, excluded, |_, _| {})
}

pub fn collect_reachable_objects<R, I>(
    reader: &R,
    format: ObjectFormat,
    starts: I,
    excluded: &HashSet<ObjectId>,
) -> Result<Vec<Arc<EncodedObject>>>
where
    R: ObjectReader,
    I: IntoIterator<Item = ObjectId>,
{
    let mut objects = Vec::new();
    walk_reachable_objects(reader, format, starts, excluded, |_, object| {
        objects.push(Arc::clone(object));
    })?;
    Ok(objects)
}

#[derive(Debug, Clone)]
struct ReachablePackObject {
    oid: ObjectId,
    object: Arc<EncodedObject>,
}

fn collect_reachable_pack_objects<R, I>(
    reader: &R,
    format: ObjectFormat,
    starts: I,
    excluded: &HashSet<ObjectId>,
) -> Result<Vec<ReachablePackObject>>
where
    R: ObjectReader,
    I: IntoIterator<Item = ObjectId>,
{
    let mut objects = Vec::new();
    walk_reachable_objects(reader, format, starts, excluded, |oid, object| {
        objects.push(ReachablePackObject {
            oid: *oid,
            object: Arc::clone(object),
        });
    })?;
    Ok(objects)
}

fn pack_inputs(objects: &[ReachablePackObject]) -> Vec<PackInput<'_>> {
    objects
        .iter()
        .map(|entry| PackInput {
            oid: &entry.oid,
            object: &entry.object,
        })
        .collect()
}

pub fn install_reachable_pack<I>(
    source: &impl ObjectReader,
    destination: &impl RawPackInstaller,
    format: ObjectFormat,
    starts: I,
) -> Result<Option<RawPackInstallResult>>
where
    I: IntoIterator<Item = ObjectId>,
{
    install_reachable_pack_excluding(source, destination, format, starts, &HashSet::new())
}

pub fn install_reachable_pack_excluding<I>(
    source: &impl ObjectReader,
    destination: &impl RawPackInstaller,
    format: ObjectFormat,
    starts: I,
    excluded: &HashSet<ObjectId>,
) -> Result<Option<RawPackInstallResult>>
where
    I: IntoIterator<Item = ObjectId>,
{
    let pack = match build_reachable_pack(source, format, starts, excluded)? {
        Some(pack) => pack,
        None => return Ok(None),
    };
    destination.install_raw_pack(&pack.pack).map(Some)
}

pub fn build_reachable_pack<R, I>(
    reader: &R,
    format: ObjectFormat,
    starts: I,
    excluded: &HashSet<ObjectId>,
) -> Result<Option<PackWrite>>
where
    R: ObjectReader,
    I: IntoIterator<Item = ObjectId>,
{
    let objects = collect_reachable_pack_objects(reader, format, starts, excluded)?;
    if objects.is_empty() {
        return Ok(None);
    }
    // Delta-compress reachable packs (used by install/push/fetch) via git-pack's
    // sliding-window selection. Self-contained, ofs-delta by default; round-trips
    // through the existing parser. PackWrite shape is unchanged, so callers are
    // unaffected.
    let inputs = pack_inputs(&objects);
    PackFile::write_packed_with_known_ids(&inputs, format).map(Some)
}

pub fn build_and_install_reachable_pack<R, I>(
    source: &R,
    destination: &FileObjectDatabase,
    format: ObjectFormat,
    starts: I,
    excluded: &HashSet<ObjectId>,
    options: RawPackInstallOptions,
) -> Result<Option<PackInstallResult>>
where
    R: ObjectReader,
    I: IntoIterator<Item = ObjectId>,
{
    build_and_install_reachable_pack_filtered(
        source,
        destination,
        format,
        starts,
        excluded,
        options,
        None,
        None,
    )
}

/// A partial-clone object filter applied while building a transfer pack.
///
/// Mirrors the subset of upstream's `list-objects-filter` the in-process local
/// server supports: directly-wanted tips are always packed; the filter only
/// prunes objects reached *through* the traversal (upstream's
/// `filter_blobs_none` runs on traversed blobs, never on wanted tips).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PackObjectFilter {
    /// `blob:none`: omit every blob reached through tree traversal.
    BlobNone,
}

/// [`build_and_install_reachable_pack`] with an optional partial-clone
/// `filter`. With `Some(BlobNone)`, blobs are dropped from the pack unless
/// they are directly wanted (named in `starts`).
#[allow(clippy::too_many_arguments)]
pub fn build_and_install_reachable_pack_filtered<R, I>(
    source: &R,
    destination: &FileObjectDatabase,
    format: ObjectFormat,
    starts: I,
    excluded: &HashSet<ObjectId>,
    options: RawPackInstallOptions,
    filter: Option<PackObjectFilter>,
    unpack_limit: Option<usize>,
) -> Result<Option<PackInstallResult>>
where
    R: ObjectReader,
    I: IntoIterator<Item = ObjectId>,
{
    let starts: Vec<ObjectId> = starts.into_iter().collect();
    let wanted: HashSet<ObjectId> = starts.iter().copied().collect();
    let mut objects = collect_reachable_pack_objects(source, format, starts, excluded)?;
    match filter {
        Some(PackObjectFilter::BlobNone) => {
            objects.retain(|entry| {
                entry.object.object_type != ObjectType::Blob || wanted.contains(&entry.oid)
            });
        }
        None => {}
    }
    if objects.is_empty() {
        return Ok(None);
    }
    // Mirror fetch-pack's unpack-limit: small transfers are exploded into
    // loose objects instead of landing as a pack (upstream `get_pack` picks
    // unpack-objects when the header count is below fetch/transfer.unpackLimit).
    if let Some(limit) = unpack_limit
        && objects.len() < limit
    {
        for entry in &objects {
            destination.loose().write_object((*entry.object).clone())?;
        }
        return Ok(None);
    }
    let inputs = pack_inputs(&objects);
    let pack = PackFile::write_packed_with_known_ids(&inputs, format)?;
    destination
        .install_generated_pack_unchecked(&pack, options)
        .map(Some)
}

/// Assemble a pack stream that reuses an existing pack's object data verbatim
/// (upstream pack-objects' "pack reuse" fast path, full-pack case) and appends
/// `appended` as freshly encoded undeltified entries.
///
/// The reused pack's entry bytes are copied as-is between our own header and
/// trailer: a full-pack copy preserves every relative distance, so internal
/// `OFS_DELTA` bases stay valid. The header object count covers both the
/// reused and appended entries, and the trailing pack checksum is recomputed
/// over the assembled stream.
pub fn assemble_pack_with_verbatim_reuse(
    format: ObjectFormat,
    reused_pack_bytes: &[u8],
    appended: &[PackInput<'_>],
) -> Result<(Vec<u8>, u32)> {
    assemble_pack_with_verbatim_reuses(format, &[reused_pack_bytes], appended)
}

/// Like [`assemble_pack_with_verbatim_reuse`], but concatenates multiple whole
/// packs before appending fresh entries.
pub fn assemble_pack_with_verbatim_reuses(
    format: ObjectFormat,
    reused_packs: &[&[u8]],
    appended: &[PackInput<'_>],
) -> Result<(Vec<u8>, u32)> {
    let hash_len = format.raw_len();
    let mut reused_count = 0u32;
    let mut capacity = 12 + hash_len + 64 * appended.len();
    for reused_pack_bytes in reused_packs {
        if reused_pack_bytes.len() < 12 + hash_len {
            return Err(GitError::InvalidFormat("reused pack too short".into()));
        }
        if &reused_pack_bytes[..4] != b"PACK" {
            return Err(GitError::InvalidFormat(
                "reused pack has no signature".into(),
            ));
        }
        let version = u32::from_be_bytes([
            reused_pack_bytes[4],
            reused_pack_bytes[5],
            reused_pack_bytes[6],
            reused_pack_bytes[7],
        ]);
        if version != 2 {
            return Err(GitError::Unsupported(format!(
                "reused pack version {version}"
            )));
        }
        let count = u32::from_be_bytes([
            reused_pack_bytes[8],
            reused_pack_bytes[9],
            reused_pack_bytes[10],
            reused_pack_bytes[11],
        ]);
        reused_count = reused_count
            .checked_add(count)
            .ok_or_else(|| GitError::InvalidFormat("too many pack objects".into()))?;
        capacity = capacity.saturating_add(reused_pack_bytes.len().saturating_sub(12 + hash_len));
    }
    let total = reused_count
        .checked_add(appended.len() as u32)
        .ok_or_else(|| GitError::InvalidFormat("too many pack objects".into()))?;

    let mut out = Vec::with_capacity(capacity);
    out.extend_from_slice(b"PACK");
    out.extend_from_slice(&2u32.to_be_bytes());
    out.extend_from_slice(&total.to_be_bytes());
    for reused_pack_bytes in reused_packs {
        out.extend_from_slice(&reused_pack_bytes[12..reused_pack_bytes.len() - hash_len]);
    }
    for input in appended {
        write_undeltified_pack_entry(&mut out, input.object)?;
    }
    let checksum = sley_core::digest_bytes(format, &out)?;
    out.extend_from_slice(checksum.as_bytes());
    Ok((out, reused_count))
}

/// Assemble a pack stream by copying already-encoded pack entries verbatim and
/// appending freshly encoded undeltified entries.
pub fn assemble_pack_with_verbatim_entries(
    format: ObjectFormat,
    reused_entries: &[&[u8]],
    appended: &[PackInput<'_>],
) -> Result<(Vec<u8>, u32)> {
    let reused_count = u32::try_from(reused_entries.len())
        .map_err(|_| GitError::InvalidFormat("too many pack objects".into()))?;
    let total = reused_count
        .checked_add(appended.len() as u32)
        .ok_or_else(|| GitError::InvalidFormat("too many pack objects".into()))?;

    let mut capacity = 12 + format.raw_len() + 64 * appended.len();
    for entry in reused_entries {
        capacity = capacity.saturating_add(entry.len());
    }
    let mut out = Vec::with_capacity(capacity);
    out.extend_from_slice(b"PACK");
    out.extend_from_slice(&2u32.to_be_bytes());
    out.extend_from_slice(&total.to_be_bytes());
    for entry in reused_entries {
        out.extend_from_slice(entry);
    }
    for input in appended {
        write_undeltified_pack_entry(&mut out, input.object)?;
    }
    let checksum = sley_core::digest_bytes(format, &out)?;
    out.extend_from_slice(checksum.as_bytes());
    Ok((out, reused_count))
}

/// Append one undeltified pack entry (type/size varint header + zlib body).
fn write_undeltified_pack_entry(out: &mut Vec<u8>, object: &EncodedObject) -> Result<()> {
    let type_bits: u8 = match object.object_type {
        ObjectType::Commit => 1,
        ObjectType::Tree => 2,
        ObjectType::Blob => 3,
        ObjectType::Tag => 4,
    };
    let mut size = object.body.len() as u64;
    let mut byte = (type_bits << 4) | (size & 0x0f) as u8;
    size >>= 4;
    while size > 0 {
        out.push(byte | 0x80);
        byte = (size & 0x7f) as u8;
        size >>= 7;
    }
    out.push(byte);
    let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
    encoder.write_all(&object.body)?;
    out.extend_from_slice(&encoder.finish()?);
    Ok(())
}

/// Outcome of consolidating every object in a repository into a single pack.
///
/// This is the engine for `git gc` / `git repack`: [`repack_all_objects`]
/// produces the bytes for one new delta-compressed pack plus its index, and
/// reports which on-disk artifacts the caller could now remove. No deletions
/// are performed by the engine itself; the CLI decides reachability policy and
/// performs any pruning (see [`install_repack_result`]).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RepackResult {
    /// Bytes of the freshly written `.pack` file.
    pub pack: Vec<u8>,
    /// Bytes of the matching `.idx` file for [`RepackResult::pack`].
    pub idx: Vec<u8>,
    /// Number of distinct objects contained in the new pack.
    pub object_count: usize,
    /// Absolute paths of pre-existing `*.pack` files now superseded by the new
    /// pack (every object they hold is present in [`RepackResult::pack`]).
    pub obsolete_packs: Vec<PathBuf>,
    /// Loose object ids that are now also present in the new pack and therefore
    /// redundant on disk.
    pub packed_loose: Vec<ObjectId>,
    pack_checksum: ObjectId,
    index_entries: Vec<PackIndexEntry>,
}

/// Gather every object in `git_dir` (loose objects and every existing pack) and
/// write them into a single new delta-compressed pack.
///
/// Returns the new pack/index bytes, the count of packed objects, the list of
/// pre-existing pack files that the new pack supersedes, and the loose object
/// ids that are now packed. Nothing is deleted: the caller (CLI) decides
/// reachability policy and performs any pruning, optionally via
/// [`install_repack_result`].
///
/// Returns `Ok(None)` when the repository contains no objects at all.
/// `git repack -a`'s gathering rule: pack the reachability closure of `roots`
/// (ref tips, `HEAD`, reflog entries, indexed objects) instead of everything
/// on disk. Borrowed objects (alternates) reachable from the roots are packed
/// into the new local pack like upstream `pack-objects --all` without
/// `--local`; previously-packed objects that are no longer reachable are NOT
/// carried forward (that is how `repack -a -d` drops them). Missing objects
/// are tolerated (stale reflog entries may reference pruned history).
///
/// Returns `Ok(None)` when no roots resolve to any object.
pub fn repack_reachable_objects(
    git_dir: &Path,
    format: ObjectFormat,
    roots: &[ObjectId],
) -> Result<Option<RepackResult>> {
    let objects_dir = repository_objects_dir(git_dir);
    let database = FileObjectDatabase::new(objects_dir.clone(), format);

    let mut seen: HashSet<ObjectId> = HashSet::new();
    let mut objects: Vec<ReachablePackObject> = Vec::new();
    let mut pending: Vec<ObjectId> = roots.to_vec();
    while let Some(oid) = pending.pop() {
        if !seen.insert(oid) {
            continue;
        }
        let object = match database.read_object(&oid) {
            Ok(object) => object,
            Err(GitError::NotFound(_)) => continue,
            Err(err) => return Err(err),
        };
        match object.object_type {
            ObjectType::Commit => {
                let commit = Commit::parse_ref(format, &object.body)?;
                pending.extend(grafted_parents(&database, &oid, commit.parents));
                pending.push(commit.tree);
            }
            ObjectType::Tree => {
                for entry in TreeEntries::new(format, &object.body) {
                    let entry = entry?;
                    if !entry.is_gitlink() {
                        pending.push(entry.oid);
                    }
                }
            }
            ObjectType::Tag => {
                let tag = Tag::parse_ref(format, &object.body)?;
                pending.push(tag.object);
            }
            ObjectType::Blob => {}
        }
        objects.push(ReachablePackObject { oid, object });
    }
    if objects.is_empty() {
        return Ok(None);
    }

    let inputs = pack_inputs(&objects);
    let written = PackFile::write_packed_with_known_ids(&inputs, format)?;
    let object_count = written.entries.len();

    // Every pre-existing local pack is superseded under `-a` (their reachable
    // objects are in the new pack; their unreachable ones are being dropped).
    let new_pack_file_name = format!("pack-{}.pack", written.checksum.to_hex());
    let obsolete_packs = existing_pack_files(&objects_dir.join("pack"))?
        .into_iter()
        .filter(|path| path.file_name().and_then(|name| name.to_str()) != Some(&new_pack_file_name))
        .collect();

    let packed_oid_set: HashSet<&ObjectId> = written.entries.iter().map(|e| &e.oid).collect();
    let mut packed_loose: Vec<ObjectId> = loose_object_ids(&objects_dir, format)?
        .into_iter()
        .filter(|oid| packed_oid_set.contains(oid))
        .collect();
    packed_loose.sort_by(|left, right| left.as_bytes().cmp(right.as_bytes()));

    let pack_checksum = written.checksum;
    let index_entries = written.entries.clone();
    Ok(Some(RepackResult {
        pack: written.pack,
        idx: written.index,
        object_count,
        obsolete_packs,
        packed_loose,
        pack_checksum,
        index_entries,
    }))
}

pub fn repack_all_objects(git_dir: &Path, format: ObjectFormat) -> Result<Option<RepackResult>> {
    let objects_dir = repository_objects_dir(git_dir);
    let database = FileObjectDatabase::new(objects_dir.clone(), format);

    // Enumerate every object id reachable on disk: loose objects, every pack
    // index, and any multi-pack-index. `object_ids_in_objects_dir` already
    // unions all of these and de-duplicates them.
    let all_oids = object_ids_in_objects_dir(&objects_dir, format)?;
    if all_oids.is_empty() {
        return Ok(None);
    }

    // Read each object's canonical encoding so the new pack stores byte-for-byte
    // identical payloads. Loose objects take precedence over packed copies in
    // `FileObjectDatabase::read_object`, but both decode to the same bytes.
    let mut objects = Vec::with_capacity(all_oids.len());
    for oid in &all_oids {
        objects.push(ReachablePackObject {
            oid: *oid,
            object: database.read_object(oid)?,
        });
    }

    let inputs = pack_inputs(&objects);
    let written = PackFile::write_packed_with_known_ids(&inputs, format)?;
    let object_count = written.entries.len();

    // The new pack contains every object on disk, so every pre-existing pack is
    // fully superseded. We still record the exact pack paths (not the index
    // paths) so the caller can delete the right files. The pack we are about to
    // write is excluded by name in case its checksum collides with an existing
    // pack (identical contents).
    let new_pack_file_name = format!("pack-{}.pack", written.checksum.to_hex());
    let obsolete_packs = existing_pack_files(&objects_dir.join("pack"))?
        .into_iter()
        .filter(|path| path.file_name().and_then(|name| name.to_str()) != Some(&new_pack_file_name))
        .collect();

    // Loose object ids that the new pack now also holds (which is all of them,
    // since they were gathered into it).
    let packed_oid_set: HashSet<&ObjectId> = written.entries.iter().map(|e| &e.oid).collect();
    let mut packed_loose: Vec<ObjectId> = loose_object_ids(&objects_dir, format)?
        .into_iter()
        .filter(|oid| packed_oid_set.contains(oid))
        .collect();
    packed_loose.sort_by(|left, right| left.as_bytes().cmp(right.as_bytes()));

    Ok(Some(RepackResult {
        pack: written.pack,
        idx: written.index,
        object_count,
        obsolete_packs,
        packed_loose,
        pack_checksum: written.checksum,
        index_entries: written.entries,
    }))
}

/// Gather only loose objects in `git_dir` and write them into a new pack.
///
/// This is the engine for plain `git repack -d` (without `-a`): existing packs
/// remain in place, and pruning removes only the loose copies that the new pack
/// now serves.
pub fn repack_loose_objects(git_dir: &Path, format: ObjectFormat) -> Result<Option<RepackResult>> {
    let objects_dir = repository_objects_dir(git_dir);
    let database = FileObjectDatabase::new(objects_dir.clone(), format);
    let loose_oids = loose_object_ids(&objects_dir, format)?;
    if loose_oids.is_empty() {
        return Ok(None);
    }

    let mut objects = Vec::with_capacity(loose_oids.len());
    for oid in &loose_oids {
        objects.push(ReachablePackObject {
            oid: *oid,
            object: database.read_object(oid)?,
        });
    }

    let inputs = pack_inputs(&objects);
    let written = PackFile::write_packed_with_known_ids(&inputs, format)?;
    let object_count = written.entries.len();
    let packed_oid_set: HashSet<&ObjectId> = written.entries.iter().map(|e| &e.oid).collect();
    let mut packed_loose: Vec<ObjectId> = loose_oids
        .into_iter()
        .filter(|oid| packed_oid_set.contains(oid))
        .collect();
    packed_loose.sort_by(|left, right| left.as_bytes().cmp(right.as_bytes()));

    let pack_checksum = written.checksum;
    let index_entries = written.entries.clone();
    Ok(Some(RepackResult {
        pack: written.pack,
        idx: written.index,
        object_count,
        obsolete_packs: Vec::new(),
        packed_loose,
        pack_checksum,
        index_entries,
    }))
}

/// Write the consolidated pack from a [`RepackResult`] into
/// `objects/pack/` and, when `prune` is set, remove the now-redundant
/// pre-existing packs and packed loose objects.
///
/// Pruning is opt-in and deliberately conservative: an object or pack is only
/// removed after verifying it is actually present in the freshly written pack
/// on disk. Concretely:
///
/// * a loose object is removed only if its id appears in the new pack;
/// * a pre-existing pack is removed only if it is not the pack we just wrote
///   *and* every object listed in its `.idx` is present in the new pack (its
///   `.idx` and known sidecars are removed alongside it);
/// * a stale `multi-pack-index` is removed only if every pack it references is
///   being removed, so no reader is ever left pointing at a deleted pack.
pub fn install_repack_result(
    git_dir: &Path,
    format: ObjectFormat,
    result: &RepackResult,
    prune: bool,
) -> Result<()> {
    install_repack_result_with_bitmap(git_dir, format, result, prune, None)
}

/// [`install_repack_result`] that additionally writes a `pack-<checksum>.bitmap`
/// reachability bitmap alongside the new pack when `bitmap_tips` is `Some`.
/// `bitmap_tips` carries the repository's ref tips (peeled to commits): they
/// receive selection preference, mirroring upstream's `NEEDS_BITMAP` flagging of
/// ref tips in `git repack -b` / `pack-objects --write-bitmap-index`.
pub fn install_repack_result_with_bitmap(
    git_dir: &Path,
    format: ObjectFormat,
    result: &RepackResult,
    prune: bool,
    bitmap_tips: Option<&HashSet<ObjectId>>,
) -> Result<()> {
    let objects_dir = repository_objects_dir(git_dir);
    let pack_dir = objects_dir.join("pack");
    fs::create_dir_all(&pack_dir)?;

    // Validate the public bytes against the private provenance that
    // `repack_all_objects` captured from `PackFile::write_packed`. This avoids
    // inflating and resolving the freshly-written pack a second time while still
    // catching caller mutations before anything is written or pruned.
    validate_pack_checksum(&result.pack, format, &result.pack_checksum, "repack")?;
    let parsed_index = PackIndex::parse(&result.idx, format)?;
    if parsed_index.pack_checksum != result.pack_checksum {
        return Err(GitError::InvalidFormat(
            "repack index checksum does not match the new pack".into(),
        ));
    }
    if !pack_index_entries_match_writer(&parsed_index.entries, &result.index_entries) {
        return Err(GitError::InvalidFormat(
            "repack index does not match the new pack contents".into(),
        ));
    }
    let pack_name = format!("pack-{}", result.pack_checksum.to_hex());
    let new_pack_path = pack_dir.join(format!("{pack_name}.pack"));
    let new_rev_path = pack_dir.join(format!("{pack_name}.rev"));
    let new_index_path = pack_dir.join(format!("{pack_name}.idx"));
    // git writes a `.rev` alongside every repacked pack (`pack.writeReverseIndex`
    // defaults to true). Write it before the `.idx` so the index never becomes
    // visible ahead of its companions, mirroring upstream's finalize order.
    let reverse_index = sley_pack::PackReverseIndex::write(
        format,
        &sley_pack::pack_order_index_positions(&parsed_index.entries),
        &result.pack_checksum,
    )?;
    write_pack_component(&new_pack_path, &result.pack)?;
    write_pack_component(&new_rev_path, &reverse_index)?;
    write_pack_component(&new_index_path, &result.idx)?;

    if let Some(tips) = bitmap_tips {
        // Build before pruning: the closure walk reads objects through the
        // pre-existing packs/loose store (the new pack holds the same bytes).
        let database = FileObjectDatabase::new(objects_dir.clone(), format);
        if let Some(bitmap) = build_pack_bitmap(
            &database,
            format,
            &result.index_entries,
            &result.pack_checksum,
            tips,
        )? {
            // Unlike the pack/idx/rev (content-addressed by the pack
            // checksum), the bitmap depends on selection inputs (e.g.
            // pack.preferBitmapTips), so an existing file must be replaced —
            // write_pack_component's exists-skip would keep a stale selection.
            let bitmap_path = pack_dir.join(format!("{pack_name}.bitmap"));
            remove_file_if_exists(&bitmap_path)?;
            write_pack_component(&bitmap_path, &bitmap)?;
        }
    }

    if !prune {
        return Ok(());
    }

    // Prune based on the objects the new pack's *index* can resolve (what reads use
    // once the old packs are gone), not just what the pack contains — so a stale
    // pack is never removed for an object the new index cannot serve.
    let present: HashSet<ObjectId> = parsed_index.entries.iter().map(|entry| entry.oid).collect();

    prune_packs_contained_in(&objects_dir, format, &present, &new_pack_path)?;
    prune_loose_objects(&objects_dir, format, result.packed_loose.iter(), &present)?;
    Ok(())
}

fn validate_pack_checksum(
    pack: &[u8],
    format: ObjectFormat,
    expected: &ObjectId,
    context: &str,
) -> Result<()> {
    if expected.format() != format {
        return Err(GitError::InvalidObjectId(format!(
            "{context} checksum format does not match object format"
        )));
    }
    let hash_len = format.raw_len();
    if pack.len() < 12 + hash_len {
        return Err(GitError::InvalidFormat(format!(
            "{context} pack file too short"
        )));
    }
    if &pack[..4] != b"PACK" {
        return Err(GitError::InvalidFormat(format!(
            "{context} pack file missing PACK signature"
        )));
    }
    let trailer_offset = pack.len() - hash_len;
    let actual = sley_core::digest_bytes(format, &pack[..trailer_offset])?;
    let trailer = ObjectId::from_raw(format, &pack[trailer_offset..])?;
    if &actual != expected || trailer != *expected {
        return Err(GitError::InvalidFormat(format!(
            "{context} pack checksum does not match generated pack"
        )));
    }
    Ok(())
}

fn pack_index_entries_match_writer(
    parsed: &[PackIndexEntry],
    writer_entries: &[PackIndexEntry],
) -> bool {
    if parsed.len() != writer_entries.len() {
        return false;
    }
    let mut writer_entries = writer_entries.iter().collect::<Vec<_>>();
    writer_entries.sort_by(|left, right| left.oid.as_bytes().cmp(right.oid.as_bytes()));
    parsed.iter().zip(writer_entries).all(|(left, right)| {
        left.oid == right.oid && left.crc32 == right.crc32 && left.offset == right.offset
    })
}

/// List loose objects under `git_dir` that are *not* reachable from `roots`,
/// optionally deleting them.
///
/// Reachability is computed with [`collect_reachable_object_ids`] over the
/// repository's object database, so trees, parents, and tag targets are all
/// followed. When `delete` is `false` the returned ids are merely reported;
/// when `true` each unreachable loose object file is removed (packed copies are
/// never touched). Deletion is therefore opt-in.
pub fn prune_unreachable_loose<I>(
    git_dir: &Path,
    format: ObjectFormat,
    roots: I,
    delete: bool,
) -> Result<Vec<ObjectId>>
where
    I: IntoIterator<Item = ObjectId>,
{
    let objects_dir = repository_objects_dir(git_dir);
    let database = FileObjectDatabase::new(objects_dir.clone(), format);
    let reachable = collect_reachable_object_ids(&database, format, roots)?;

    let store = LooseObjectStore::new(objects_dir.clone(), format);
    let mut pruned: Vec<ObjectId> = loose_object_ids(&objects_dir, format)?
        .into_iter()
        .filter(|oid| !reachable.contains(oid))
        .collect();
    pruned.sort_by(|left, right| left.as_bytes().cmp(right.as_bytes()));

    if delete {
        for oid in &pruned {
            let path = store.object_path(oid)?;
            match fs::remove_file(&path) {
                Ok(()) => {}
                Err(err) if err.kind() == std::io::ErrorKind::NotFound => {}
                Err(err) => return Err(GitError::Io(err.to_string())),
            }
        }
    }
    Ok(pruned)
}

/// Loose object ids under `objects_dir`, sorted by hex, with packed objects
/// excluded.
fn loose_object_ids(objects_dir: &Path, format: ObjectFormat) -> Result<Vec<ObjectId>> {
    let oids = loose_object_id_set(objects_dir, format)?;
    let mut oids = oids.into_iter().collect::<Vec<_>>();
    oids.sort_by(|left, right| left.as_bytes().cmp(right.as_bytes()));
    Ok(oids)
}

fn loose_object_id_set(objects_dir: &Path, format: ObjectFormat) -> Result<HashSet<ObjectId>> {
    let mut oids = HashSet::new();
    collect_loose_object_ids(objects_dir, format, &mut oids)?;
    Ok(oids)
}

/// Absolute paths of every `*.pack` file directly inside `pack_dir`, sorted for
/// deterministic output.
fn existing_pack_files(pack_dir: &Path) -> Result<Vec<PathBuf>> {
    if !pack_dir.exists() {
        return Ok(Vec::new());
    }
    let mut packs = Vec::new();
    for entry in fs::read_dir(pack_dir)? {
        let path = entry?.path();
        if path.extension().and_then(|ext| ext.to_str()) == Some("pack") && path.is_file() {
            packs.push(path);
        }
    }
    packs.sort();
    Ok(packs)
}

/// Remove pre-existing packs whose every object is contained in `present`,
/// skipping `keep` (the pack just written), `.keep` packs, and `.promisor` packs.
/// A stale multi-pack-index that references any removed pack is removed too.
fn prune_packs_contained_in(
    objects_dir: &Path,
    format: ObjectFormat,
    present: &HashSet<ObjectId>,
    keep: &Path,
) -> Result<()> {
    let pack_dir = objects_dir.join("pack");
    let keep_stem = keep.file_stem().map(|stem| stem.to_owned());
    let mut removed_stems: HashSet<String> = HashSet::new();

    for pack_path in existing_pack_files(&pack_dir)? {
        if pack_path == keep {
            continue;
        }
        let Some(stem) = pack_path.file_stem() else {
            continue;
        };
        if Some(stem) == keep_stem.as_deref() {
            continue;
        }
        if pack_path.with_extension("keep").exists()
            || pack_path.with_extension("promisor").exists()
        {
            continue;
        }
        let index_path = pack_path.with_extension("idx");
        if !index_path.exists() {
            // Without an index we cannot prove containment; leave it alone.
            continue;
        }
        let index = PackIndex::parse(&fs::read(&index_path)?, format)?;
        if !index
            .entries
            .iter()
            .all(|entry| present.contains(&entry.oid))
        {
            continue;
        }
        // Every object in this pack is safely in the new pack and it has no Git
        // policy sidecar that says to keep it: remove the pack, its index, and
        // cache sidecars derived from them.
        remove_file_if_exists(&pack_path)?;
        remove_file_if_exists(&index_path)?;
        for ext in ["rev", "mtimes", "bitmap"] {
            remove_file_if_exists(&pack_path.with_extension(ext))?;
        }
        removed_stems.insert(stem.to_string_lossy().into_owned());
    }

    prune_stale_multi_pack_index(&pack_dir, format, &removed_stems)?;
    Ok(())
}

/// Remove a `multi-pack-index` if it names *any* pack that was removed.
///
/// A MIDX that still references a deleted pack makes reads fail (the lookup
/// resolves to a pack that is gone) before any fallback. Removing the whole MIDX
/// when even one of its packs is pruned forces readers back to the individual pack
/// indexes, which are correct; `multi-pack-index write` can rebuild it later.
fn prune_stale_multi_pack_index(
    pack_dir: &Path,
    format: ObjectFormat,
    removed_stems: &HashSet<String>,
) -> Result<()> {
    if removed_stems.is_empty() {
        return Ok(());
    }
    let midx_path = pack_dir.join("multi-pack-index");
    if !midx_path.exists() {
        return Ok(());
    }
    let midx = MultiPackIndex::parse(&fs::read(&midx_path)?, format)?;
    let references_removed_pack = midx.pack_names.iter().any(|name| {
        let stem = name.strip_suffix(".idx").unwrap_or(name);
        removed_stems.contains(stem)
    });
    if references_removed_pack {
        remove_file_if_exists(&midx_path)?;
    }
    Ok(())
}

/// Remove each loose object in `candidates` whose id is in `present`, leaving
/// any object not actually packed untouched.
fn prune_loose_objects<'a, I>(
    objects_dir: &Path,
    format: ObjectFormat,
    candidates: I,
    present: &HashSet<ObjectId>,
) -> Result<()>
where
    I: IntoIterator<Item = &'a ObjectId>,
{
    let store = LooseObjectStore::new(objects_dir.to_path_buf(), format);
    for oid in candidates {
        if !present.contains(oid) {
            continue;
        }
        remove_file_if_exists(&store.object_path(oid)?)?;
    }
    Ok(())
}

enum PackDeltaBase {
    Offset(u64),
    Ref(ObjectId),
}

struct PackIndexOffsetInfo {
    end_offset: u64,
    delta_base_oid: Option<ObjectId>,
}

fn scan_pack_index_offsets(
    index: &PackIndex,
    target_offset: u64,
    trailer_offset: u64,
    delta_base_offset: Option<u64>,
) -> Result<PackIndexOffsetInfo> {
    let mut target_count = 0usize;
    let mut next_offset = None;
    let mut delta_base_oid = None;

    for entry in &index.entries {
        if entry.offset == target_offset {
            target_count += 1;
        } else if entry.offset > target_offset {
            match next_offset {
                Some(current) if current <= entry.offset => {}
                _ => next_offset = Some(entry.offset),
            }
        }
        if Some(entry.offset) == delta_base_offset {
            delta_base_oid = Some(entry.oid);
        }
    }

    if target_count == 0 {
        return Err(GitError::InvalidFormat(format!(
            "pack index offset {target_offset} not found"
        )));
    }
    if let Some(offset) = delta_base_offset
        && delta_base_oid.is_none()
    {
        return Err(GitError::InvalidFormat(format!(
            "ofs-delta base offset {offset} not found"
        )));
    }

    Ok(PackIndexOffsetInfo {
        // Preserve the old sorted-vector behavior for malformed indexes with
        // duplicate offsets: the next sorted entry has the same offset.
        end_offset: if target_count > 1 {
            target_offset
        } else {
            next_offset.unwrap_or(trailer_offset)
        },
        delta_base_oid,
    })
}

fn pack_entry_delta_base(
    format: ObjectFormat,
    pack: &[u8],
    entry_offset: u64,
) -> Result<Option<PackDeltaBase>> {
    let mut cursor = usize::try_from(entry_offset)
        .map_err(|_| GitError::InvalidFormat("pack entry offset overflows usize".into()))?;
    let first = pack_next_byte(pack, &mut cursor)?;
    let kind = (first >> 4) & 0x07;
    let mut byte = first;
    while byte & 0x80 != 0 {
        byte = pack_next_byte(pack, &mut cursor)?;
    }
    match kind {
        6 => Ok(Some(PackDeltaBase::Offset(parse_ofs_delta_base_offset(
            pack,
            &mut cursor,
            entry_offset,
        )?))),
        7 => Ok(Some(PackDeltaBase::Ref(parse_ref_delta_base_oid(
            format,
            pack,
            &mut cursor,
        )?))),
        _ => Ok(None),
    }
}

fn parse_ref_delta_base_oid(
    format: ObjectFormat,
    pack: &[u8],
    cursor: &mut usize,
) -> Result<ObjectId> {
    let raw_len = format.raw_len();
    if *cursor + raw_len > pack.len() {
        return Err(GitError::InvalidFormat(
            "truncated ref-delta base object id".into(),
        ));
    }
    let oid = ObjectId::from_raw(format, &pack[*cursor..*cursor + raw_len])?;
    *cursor += raw_len;
    Ok(oid)
}

fn parse_ofs_delta_base_offset(pack: &[u8], cursor: &mut usize, entry_offset: u64) -> Result<u64> {
    let mut byte = pack_next_byte(pack, cursor)?;
    let mut relative = u64::from(byte & 0x7f);
    while byte & 0x80 != 0 {
        byte = pack_next_byte(pack, cursor)?;
        relative = relative
            .checked_add(1)
            .and_then(|value| value.checked_shl(7))
            .and_then(|value| value.checked_add(u64::from(byte & 0x7f)))
            .ok_or_else(|| GitError::InvalidFormat("ofs-delta offset overflow".into()))?;
    }
    entry_offset
        .checked_sub(relative)
        .ok_or_else(|| GitError::InvalidFormat("ofs-delta points before pack start".into()))
}

fn pack_next_byte(pack: &[u8], cursor: &mut usize) -> Result<u8> {
    let Some(byte) = pack.get(*cursor).copied() else {
        return Err(GitError::InvalidFormat("truncated pack entry".into()));
    };
    *cursor += 1;
    Ok(byte)
}

fn zero_oid(format: ObjectFormat) -> Result<ObjectId> {
    Ok(ObjectId::null(format))
}

/// Remove `path` if it exists, treating a missing file as success.
fn remove_file_if_exists(path: &Path) -> Result<()> {
    match fs::remove_file(path) {
        Ok(()) => Ok(()),
        Err(err) if err.kind() == std::io::ErrorKind::NotFound => Ok(()),
        Err(err) => Err(GitError::Io(err.to_string())),
    }
}

fn walk_reachable_objects<R, I, F>(
    reader: &R,
    format: ObjectFormat,
    starts: I,
    excluded: &HashSet<ObjectId>,
    visit: F,
) -> Result<HashSet<ObjectId>>
where
    R: ObjectReader,
    I: IntoIterator<Item = ObjectId>,
    F: FnMut(&ObjectId, &Arc<EncodedObject>),
{
    walk_reachable_objects_with_cut(reader, format, starts, excluded, &HashSet::new(), visit)
}

/// [`walk_reachable_objects`] with an additional `cut` set: commits in `cut`
/// are visited (their trees and blobs too) but their parents are not followed,
/// mirroring a shallow client's view of its own history during negotiation.
fn walk_reachable_objects_with_cut<R, I, F>(
    reader: &R,
    format: ObjectFormat,
    starts: I,
    excluded: &HashSet<ObjectId>,
    cut: &HashSet<ObjectId>,
    mut visit: F,
) -> Result<HashSet<ObjectId>>
where
    R: ObjectReader,
    I: IntoIterator<Item = ObjectId>,
    F: FnMut(&ObjectId, &Arc<EncodedObject>),
{
    let mut seen = HashSet::new();
    let mut pending = Vec::new();
    for start in starts {
        pending.push(start);
        while let Some(oid) = pending.pop() {
            if excluded.contains(&oid) {
                continue;
            }
            if !seen.insert(oid) {
                continue;
            }
            let object = reader.read_object(&oid).map_err(|err| {
                with_missing_object_context(err, oid, MissingObjectContext::Traversal)
            })?;
            match object.object_type {
                ObjectType::Commit => {
                    let (tree, parents) = {
                        let commit = Commit::parse_ref(format, &object.body)?;
                        (commit.tree, commit.parents)
                    };
                    visit(&oid, &object);
                    if !cut.contains(&oid) {
                        for parent in grafted_parents(reader, &oid, parents).into_iter().rev() {
                            pending.push(parent);
                        }
                    }
                    pending.push(tree);
                }
                ObjectType::Tree => {
                    let mut child_oids = Vec::new();
                    for entry in TreeEntries::new(format, &object.body) {
                        let entry = entry?;
                        if entry.is_gitlink() {
                            continue;
                        }
                        child_oids.push(entry.oid);
                    }
                    visit(&oid, &object);
                    pending.extend(child_oids.into_iter().rev());
                }
                ObjectType::Tag => {
                    let target = {
                        let tag = Tag::parse_ref(format, &object.body)?;
                        tag.object
                    };
                    visit(&oid, &object);
                    pending.push(target);
                }
                ObjectType::Blob => visit(&oid, &object),
            }
        }
    }
    Ok(seen)
}

// ===== reachability bitmaps (.bitmap write + consult) =====

/// Bit accessors over a `Vec<u64>` bitset using git's bitmap convention:
/// bit `i` lives in word `i / 64` at bit `i % 64` (LSB-first within a word).
fn bitset_get(words: &[u64], position: u32) -> bool {
    let word = (position / 64) as usize;
    word < words.len() && words[word] & (1u64 << (position % 64)) != 0
}

fn bitset_set(words: &mut [u64], position: u32) {
    let word = (position / 64) as usize;
    if word < words.len() {
        words[word] |= 1u64 << (position % 64);
    }
}

fn bitset_or(acc: &mut [u64], other: &[u64]) {
    for (dst, src) in acc.iter_mut().zip(other) {
        *dst |= *src;
    }
}

/// Sorted set-bit positions of a bitset (the inverse of repeated [`bitset_set`]).
fn bitset_positions(words: &[u64]) -> Vec<u32> {
    let mut positions = Vec::new();
    for (word_index, word) in words.iter().enumerate() {
        let mut remaining = *word;
        while remaining != 0 {
            let bit = remaining.trailing_zeros();
            positions.push(word_index as u32 * 64 + bit);
            remaining &= remaining - 1;
        }
    }
    positions
}

/// Committer timestamp (epoch seconds) of a commit identity line
/// (`Name <email> <timestamp> <tz>`); 0 when unparseable, matching git's
/// tolerance for bogus dates during bitmap commit selection.
fn commit_identity_timestamp(identity: &[u8]) -> i64 {
    let mut fields = identity.rsplitn(3, |byte| *byte == b' ');
    let _tz = fields.next();
    fields
        .next()
        .and_then(|raw| std::str::from_utf8(raw).ok())
        .and_then(|raw| raw.parse::<i64>().ok())
        .unwrap_or(0)
}

/// Upstream `next_commit_index` (pack-bitmap-write.c): the spacing schedule for
/// bitmap commit selection over the date-descending commit list.
fn bitmap_next_commit_index(idx: u32) -> u32 {
    const MIN_COMMITS: u32 = 100;
    const MAX_COMMITS: u32 = 5000;
    const MUST_REGION: u32 = 100;
    const MIN_REGION: u32 = 20000;

    if idx <= MUST_REGION {
        return 0;
    }
    if idx <= MIN_REGION {
        let offset = idx - MUST_REGION;
        return offset.min(MIN_COMMITS);
    }
    let offset = idx - MIN_REGION;
    offset.clamp(MIN_COMMITS, MAX_COMMITS)
}

/// Builds a serialised `.bitmap` for the pack described by `index_entries` /
/// `pack_checksum`, mirroring upstream pack-bitmap-write.c:
///
/// * commit selection walks the pack's commits in committer-date-descending
///   order through [`bitmap_next_commit_index`]'s spacing schedule, preferring
///   `preferred_tips` (ref tips — upstream's `NEEDS_BITMAP`) and merge commits
///   inside each window;
/// * each selected commit stores its full reachability closure (commits, trees,
///   blobs) as pack-order bit positions (no XOR compression — `xor_offset` 0 is
///   valid on disk and what readers see after resolution anyway).
///
/// Returns `Ok(None)` — mirroring upstream's warn-and-skip — when the pack
/// lacks full closure (a reachable object is missing from it).
pub fn build_pack_bitmap(
    db: &FileObjectDatabase,
    format: ObjectFormat,
    index_entries: &[PackIndexEntry],
    pack_checksum: &ObjectId,
    preferred_tips: &HashSet<ObjectId>,
) -> Result<Option<Vec<u8>>> {
    // `index_entries` carries no ordering guarantee (writer provenance is in
    // pack-write order); bit numbering follows pack (offset) order.
    let mut by_offset: Vec<usize> = (0..index_entries.len()).collect();
    by_offset.sort_by_key(|&slot| index_entries[slot].offset);
    let bit_order: Vec<ObjectId> = by_offset
        .into_iter()
        .map(|slot| index_entries[slot].oid)
        .collect();
    build_reachability_bitmap(db, format, pack_checksum, &bit_order, preferred_tips)
}

/// [`build_pack_bitmap`]'s multi-pack sibling: builds the serialised
/// `multi-pack-index-<checksum>.bitmap` for `midx_entries`, with bits in
/// pseudo-pack order (preferred pack first, then pack id, then offset — the
/// same order [`MultiPackIndex::write_with_reverse_index`] records in `RIDX`)
/// and the midx checksum in the BITM checksum field.
pub fn build_midx_bitmap(
    db: &FileObjectDatabase,
    format: ObjectFormat,
    midx_entries: &[sley_pack::MultiPackIndexEntry],
    midx_checksum: &ObjectId,
    preferred_pack: u32,
    preferred_tips: &HashSet<ObjectId>,
) -> Result<Option<Vec<u8>>> {
    let mut pseudo: Vec<usize> = (0..midx_entries.len()).collect();
    pseudo.sort_by_key(|&slot| {
        let entry = &midx_entries[slot];
        (
            entry.pack_int_id != preferred_pack,
            entry.pack_int_id,
            entry.offset,
        )
    });
    let bit_order: Vec<ObjectId> = pseudo
        .into_iter()
        .map(|slot| midx_entries[slot].oid)
        .collect();
    build_reachability_bitmap(db, format, midx_checksum, &bit_order, preferred_tips)
}

/// Upstream `bitmap_builder_init`'s `num_maximal` counter (pack-bitmap-write.c):
/// walk the first-parent ancestry of the selected commits, children before
/// parents, propagating per-commit "which selected commits reach me" masks.
/// A commit counts as maximal when it is selected, or when distinct selected
/// lineages converge on it (its mask gains bits its last contributing child
/// did not carry). Only the count is needed (for the trace2 data event), so no
/// reverse-edge bookkeeping is kept.
fn bitmap_num_maximal_commits(
    db: &FileObjectDatabase,
    format: ObjectFormat,
    selected: &[ObjectId],
) -> Result<usize> {
    // First-parent subgraph reachable from the selected commits.
    let mut first_parent: HashMap<ObjectId, Option<ObjectId>> = HashMap::new();
    let mut stack: Vec<ObjectId> = selected.to_vec();
    while let Some(oid) = stack.pop() {
        if first_parent.contains_key(&oid) {
            continue;
        }
        let object = db.read_object(&oid)?;
        let commit = Commit::parse_ref(format, &object.body)?;
        let parent = grafted_parents(db, &oid, commit.parents).first().copied();
        first_parent.insert(oid, parent);
        if let Some(parent) = parent {
            stack.push(parent);
        }
    }
    // Children-before-parents order (Kahn over the single first-parent edge).
    let mut pending_children: HashMap<ObjectId, usize> = HashMap::new();
    for parent in first_parent.values().flatten() {
        *pending_children.entry(*parent).or_default() += 1;
    }
    let word_count = selected.len().div_ceil(64);
    struct MaximalEnt {
        mask: Vec<u64>,
        maximal: bool,
    }
    let mut ents: HashMap<ObjectId, MaximalEnt> = HashMap::new();
    for (bit, oid) in selected.iter().enumerate() {
        let ent = ents.entry(*oid).or_insert_with(|| MaximalEnt {
            mask: vec![0u64; word_count],
            maximal: true,
        });
        ent.mask[bit / 64] |= 1u64 << (bit % 64);
        ent.maximal = true;
    }
    let mut queue: Vec<ObjectId> = first_parent
        .keys()
        .filter(|oid| pending_children.get(*oid).copied().unwrap_or(0) == 0)
        .copied()
        .collect();
    let mut num_maximal = 0usize;
    while let Some(oid) = queue.pop() {
        if let Some(ent) = ents.remove(&oid) {
            if ent.maximal {
                num_maximal += 1;
            }
            if let Some(Some(parent)) = first_parent.get(&oid) {
                match ents.entry(*parent) {
                    std::collections::hash_map::Entry::Vacant(vacant) => {
                        // Fresh parent mask: c_not_p, !p_not_c -> not maximal.
                        vacant.insert(MaximalEnt {
                            mask: ent.mask.clone(),
                            maximal: false,
                        });
                    }
                    std::collections::hash_map::Entry::Occupied(mut occupied) => {
                        let parent_ent = occupied.get_mut();
                        let c_not_p = ent
                            .mask
                            .iter()
                            .zip(&parent_ent.mask)
                            .any(|(child, parent)| child & !parent != 0);
                        if c_not_p {
                            let p_not_c = parent_ent
                                .mask
                                .iter()
                                .zip(&ent.mask)
                                .any(|(parent, child)| parent & !child != 0);
                            for (parent, child) in parent_ent.mask.iter_mut().zip(&ent.mask) {
                                *parent |= child;
                            }
                            parent_ent.maximal = p_not_c;
                        }
                    }
                }
            }
        }
        if let Some(Some(parent)) = first_parent.get(&oid)
            && let Some(remaining) = pending_children.get_mut(parent)
        {
            *remaining -= 1;
            if *remaining == 0 {
                queue.push(*parent);
            }
        }
    }
    Ok(num_maximal)
}

/// Shared write half: `bit_order` lists every covered object's oid in bit
/// order (pack order for a single pack, pseudo-pack order for a midx);
/// `checksum` fills the BITM checksum field (pack checksum / midx checksum).
fn build_reachability_bitmap(
    db: &FileObjectDatabase,
    format: ObjectFormat,
    checksum: &ObjectId,
    bit_order: &[ObjectId],
    preferred_tips: &HashSet<ObjectId>,
) -> Result<Option<Vec<u8>>> {
    if bit_order.is_empty() || bit_order.len() > u32::MAX as usize {
        return Ok(None);
    }
    let object_count = bit_order.len();

    // The on-disk entry position space is the oid-sorted lookup order (.idx /
    // midx OIDL); derive each bit-order slot's rank there.
    let mut oid_sorted: Vec<u32> = (0..object_count as u32).collect();
    oid_sorted.sort_by(|&left, &right| {
        bit_order[left as usize]
            .as_bytes()
            .cmp(bit_order[right as usize].as_bytes())
    });
    let mut index_position = vec![0u32; object_count];
    for (position, &slot) in oid_sorted.iter().enumerate() {
        index_position[slot as usize] = position as u32;
    }
    let mut oid_to_pack = HashMap::with_capacity(object_count);
    for (pack_pos, oid) in bit_order.iter().enumerate() {
        oid_to_pack.insert(*oid, pack_pos as u32);
    }

    // Object types in bit order; commits also collect (date, parent count).
    let mut object_types = Vec::with_capacity(object_count);
    struct IndexedCommit {
        oid: ObjectId,
        pack_pos: u32,
        index_pos: u32,
        date: i64,
        parent_count: usize,
    }
    let mut indexed_commits = Vec::new();
    for (pack_pos, oid) in bit_order.iter().enumerate() {
        // Type via the header fast path: blobs (the bulk of most packs) never
        // need their bodies inflated here.
        let object_type = match db.read_object_header(oid)? {
            Some((object_type, _)) => object_type,
            None => db.read_object(oid)?.object_type,
        };
        object_types.push(object_type);
        if object_type == ObjectType::Commit {
            let object = db.read_object(oid)?;
            let commit = Commit::parse_ref(format, &object.body)?;
            indexed_commits.push(IndexedCommit {
                oid: *oid,
                pack_pos: pack_pos as u32,
                index_pos: index_position[pack_pos],
                date: commit_identity_timestamp(commit.committer),
                parent_count: grafted_parents(db, oid, commit.parents).len(),
            });
        }
    }

    // Selection: date-descending, then the spacing schedule.
    indexed_commits.sort_by_key(|commit| std::cmp::Reverse(commit.date));
    let mut selected: Vec<&IndexedCommit> = Vec::new();
    let commit_count = indexed_commits.len() as u32;
    if commit_count < 100 {
        selected.extend(indexed_commits.iter());
    } else {
        let mut i = 0u32;
        loop {
            let next = bitmap_next_commit_index(i);
            if i + next >= commit_count {
                break;
            }
            let mut chosen = &indexed_commits[(i + next) as usize];
            if next > 0 {
                for j in 0..=next {
                    let candidate = &indexed_commits[(i + j) as usize];
                    if preferred_tips.contains(&candidate.oid) {
                        chosen = candidate;
                        break;
                    }
                    if candidate.parent_count >= 2 {
                        chosen = candidate;
                    }
                }
            }
            selected.push(chosen);
            i += next + 1;
        }
    }

    // Trace2 selection counters (upstream bitmap_builder_init): emitted before
    // the closure walk, like upstream emits them before building the ewah
    // bitmaps. Computing num_maximal_commits needs its own first-parent walk,
    // so it only runs when the trace2 event target is active.
    if std::env::var_os("GIT_TRACE2_EVENT").is_some() {
        let selected_oids: Vec<ObjectId> = selected.iter().map(|commit| commit.oid).collect();
        let num_maximal = bitmap_num_maximal_commits(db, format, &selected_oids)?;
        sley_core::trace2::data("pack-bitmap-write", "num_selected_commits", selected.len());
        sley_core::trace2::data("pack-bitmap-write", "num_maximal_commits", num_maximal);
    }

    // Reachability closures, oldest-first so newer walks stop at memoised
    // older selected commits.
    let word_count = object_count.div_ceil(64);
    let mut memo: HashMap<ObjectId, Arc<Vec<u64>>> = HashMap::new();
    for commit in selected.iter().rev() {
        let mut acc = vec![0u64; word_count];
        let mut pending = vec![commit.oid];
        while let Some(oid) = pending.pop() {
            let Some(&pack_pos) = oid_to_pack.get(&oid) else {
                // Mirrors upstream's "Packfile doesn't have full closure".
                eprintln!(
                    "warning: Failed to write bitmap index. Packfile doesn't have full closure (object {oid} is missing)"
                );
                return Ok(None);
            };
            if bitset_get(&acc, pack_pos) {
                continue;
            }
            if let Some(stored) = memo.get(&oid) {
                bitset_or(&mut acc, stored);
                continue;
            }
            bitset_set(&mut acc, pack_pos);
            let object = db.read_object(&oid)?;
            let tree = {
                let parsed = Commit::parse_ref(format, &object.body)?;
                pending.extend(grafted_parents(db, &oid, parsed.parents));
                parsed.tree
            };
            if !bitmap_mark_tree(db, format, &tree, &oid_to_pack, &mut acc)? {
                return Ok(None);
            }
        }
        memo.insert(commit.oid, Arc::new(acc));
    }

    let mut writer = PackBitmapWriter::new(format, *checksum, &object_types)?;
    for commit in &selected {
        let words = match memo.get(&commit.oid) {
            Some(words) => words,
            None => continue,
        };
        writer.add_commit(commit.pack_pos, commit.index_pos, &bitset_positions(words))?;
    }
    writer.write().map(Some)
}

/// Marks `tree` and everything below it (sub-trees, blobs) in `acc`, skipping
/// already-set bits (their closure is already covered). Returns `false` when an
/// object is missing from the pack (no full closure), after warning.
fn bitmap_mark_tree(
    db: &impl ObjectReader,
    format: ObjectFormat,
    tree: &ObjectId,
    oid_to_pack: &HashMap<ObjectId, u32>,
    acc: &mut [u64],
) -> Result<bool> {
    let Some(&pack_pos) = oid_to_pack.get(tree) else {
        eprintln!(
            "warning: Failed to write bitmap index. Packfile doesn't have full closure (object {tree} is missing)"
        );
        return Ok(false);
    };
    if bitset_get(acc, pack_pos) {
        return Ok(true);
    }
    bitset_set(acc, pack_pos);
    let object = db.read_object(tree)?;
    for entry in TreeEntries::new(format, &object.body) {
        let entry = entry?;
        if entry.is_gitlink() {
            continue;
        }
        if entry.is_tree() {
            if !bitmap_mark_tree(db, format, &entry.oid, oid_to_pack, acc)? {
                return Ok(false);
            }
        } else {
            let Some(&blob_pos) = oid_to_pack.get(&entry.oid) else {
                eprintln!(
                    "warning: Failed to write bitmap index. Packfile doesn't have full closure (object {} is missing)",
                    entry.oid
                );
                return Ok(false);
            };
            bitset_set(acc, blob_pos);
        }
    }
    Ok(true)
}

/// A pack's `.bitmap` loaded for consultation: oid <-> pack-position mappings,
/// resolved (XOR-expanded) per-commit reachability bitsets, and the four object
/// type bitmaps. Bit numbering follows pack order throughout.
pub struct LoadedPackBitmap {
    object_count: u32,
    oid_to_pack: HashMap<ObjectId, u32>,
    pack_to_oid: Vec<ObjectId>,
    commit_words: HashMap<ObjectId, Arc<Vec<u64>>>,
    commits: Vec<u64>,
    trees: Vec<u64>,
    blobs: Vec<u64>,
    tags: Vec<u64>,
}

impl LoadedPackBitmap {
    pub fn object_count(&self) -> u32 {
        self.object_count
    }

    /// Pack-order position of `oid`, when the object is in the bitmapped pack.
    pub fn pack_position(&self, oid: &ObjectId) -> Option<u32> {
        self.oid_to_pack.get(oid).copied()
    }

    pub fn oid_at(&self, position: u32) -> Option<&ObjectId> {
        self.pack_to_oid.get(position as usize)
    }

    /// The resolved reachability bitset stored for `oid`, when it was one of
    /// the writer's selected commits.
    pub fn bitmap_for_commit(&self, oid: &ObjectId) -> Option<&Arc<Vec<u64>>> {
        self.commit_words.get(oid)
    }

    /// Oids of every commit with a stored bitmap entry (unordered).
    pub fn bitmapped_commits(&self) -> impl Iterator<Item = &ObjectId> {
        self.commit_words.keys()
    }

    /// The type bitmap for `object_type` (bit per pack position).
    pub fn type_words(&self, object_type: ObjectType) -> &[u64] {
        match object_type {
            ObjectType::Commit => &self.commits,
            ObjectType::Tree => &self.trees,
            ObjectType::Blob => &self.blobs,
            ObjectType::Tag => &self.tags,
        }
    }

    fn word_count(&self) -> usize {
        (self.object_count as usize).div_ceil(64)
    }
}

/// Loads the single-pack `.bitmap` of `objects_dir/pack`, if a valid one
/// exists. Scans `pack-*.bitmap` files (sorted, first valid wins, like
/// upstream's "first bitmap" behaviour), requires the sibling `.idx`, and
/// verifies the recorded pack checksum. Any unreadable/corrupt bitmap yields
/// `Ok(None)` — consumers fall back to a regular object walk, mirroring
/// upstream's warn-and-ignore on bitmap load failure.
pub fn load_pack_bitmap(
    objects_dir: &Path,
    format: ObjectFormat,
) -> Result<Option<LoadedPackBitmap>> {
    let pack_dir = objects_dir.join("pack");
    if !pack_dir.exists() {
        return Ok(None);
    }
    // A multi-pack bitmap wins over single-pack bitmaps, like upstream's
    // open_bitmap trying the midx first.
    if let Some(bitmap) = load_midx_bitmap(&pack_dir, format)? {
        return Ok(Some(bitmap));
    }
    let mut bitmap_paths = Vec::new();
    for entry in fs::read_dir(&pack_dir)? {
        let path = entry?.path();
        if path.extension().and_then(|ext| ext.to_str()) == Some("bitmap")
            && path
                .file_name()
                .and_then(|name| name.to_str())
                .is_some_and(|name| name.starts_with("pack-"))
        {
            bitmap_paths.push(path);
        }
    }
    bitmap_paths.sort();
    for bitmap_path in bitmap_paths {
        match load_pack_bitmap_file(&bitmap_path, format) {
            Ok(Some(bitmap)) => return Ok(Some(bitmap)),
            Ok(None) | Err(_) => continue,
        }
    }
    Ok(None)
}

/// Loads `multi-pack-index-<checksum>.bitmap` when the pack directory has a
/// multi-pack-index with a `RIDX` chunk (the bit-order permutation) and a
/// matching bitmap file. Returns `Ok(None)` — never an error — on any missing
/// or unusable piece, so callers fall through to single-pack bitmaps.
fn load_midx_bitmap(pack_dir: &Path, format: ObjectFormat) -> Result<Option<LoadedPackBitmap>> {
    let midx_path = pack_dir.join("multi-pack-index");
    if !midx_path.exists() {
        return Ok(None);
    }
    let Ok(midx_bytes) = fs::read(&midx_path) else {
        return Ok(None);
    };
    let Ok(midx) = MultiPackIndex::parse(&midx_bytes, format) else {
        return Ok(None);
    };
    let bitmap_path = pack_dir.join(format!(
        "multi-pack-index-{}.bitmap",
        midx.checksum.to_hex()
    ));
    if !bitmap_path.exists() {
        return Ok(None);
    }
    let object_count = midx.objects.len();
    // Upstream `load_midx_revindex`: prefer the midx's own RIDX chunk unless
    // GIT_TEST_MIDX_READ_RIDX=0 disables it, else fall back to the separate
    // `multi-pack-index-<checksum>.rev` file; a trace2 data event records
    // which source supplied the permutation.
    let read_ridx_chunk = env::var("GIT_TEST_MIDX_READ_RIDX")
        .map(|value| value != "0" && !value.eq_ignore_ascii_case("false"))
        .unwrap_or(true);
    let reverse_index: Vec<u32> = match (&midx.reverse_index, read_ridx_chunk) {
        (Some(chunk), true) => {
            sley_core::trace2::data("load_midx_revindex", "source", "midx");
            chunk.clone()
        }
        _ => {
            let rev_path =
                pack_dir.join(format!("multi-pack-index-{}.rev", midx.checksum.to_hex()));
            let Ok(rev_bytes) = fs::read(&rev_path) else {
                // Without the RIDX permutation the bit numbering is unknown.
                return Ok(None);
            };
            let Ok(parsed_rev) =
                sley_pack::PackReverseIndex::parse(&rev_bytes, format, object_count)
            else {
                return Ok(None);
            };
            sley_core::trace2::data("load_midx_revindex", "source", "rev");
            parsed_rev.positions
        }
    };
    let Ok(bitmap_bytes) = fs::read(&bitmap_path) else {
        return Ok(None);
    };
    let parsed = match PackBitmapIndex::parse(&bitmap_bytes, format, object_count) {
        Ok(parsed) => parsed,
        Err(_) => return Ok(None),
    };
    if parsed.pack_checksum != midx.checksum {
        return Ok(None);
    }

    // midx.objects is in lookup (oid-sorted) order; RIDX maps bit positions
    // to lookup positions.
    let mut pack_to_oid = Vec::with_capacity(object_count);
    for &midx_pos in &reverse_index {
        let Some(entry) = midx.objects.get(midx_pos as usize) else {
            return Ok(None);
        };
        pack_to_oid.push(entry.oid);
    }
    let mut oid_to_pack = HashMap::with_capacity(object_count);
    for (pack_pos, oid) in pack_to_oid.iter().enumerate() {
        oid_to_pack.insert(*oid, pack_pos as u32);
    }
    match assemble_loaded_bitmap(parsed, object_count, pack_to_oid, oid_to_pack, |position| {
        midx.objects.get(position).map(|entry| entry.oid)
    }) {
        Ok(loaded) => Ok(Some(loaded)),
        Err(_) => Ok(None),
    }
}

fn load_pack_bitmap_file(
    bitmap_path: &Path,
    format: ObjectFormat,
) -> Result<Option<LoadedPackBitmap>> {
    let index_path = bitmap_path.with_extension("idx");
    if !index_path.exists() {
        return Ok(None);
    }
    let index = PackIndex::parse(&fs::read(&index_path)?, format)?;
    let object_count = index.entries.len();
    let parsed = PackBitmapIndex::parse(&fs::read(bitmap_path)?, format, object_count)?;
    if parsed.pack_checksum != index.pack_checksum {
        return Ok(None);
    }

    let mut pack_order: Vec<u32> = (0..object_count as u32).collect();
    pack_order.sort_by_key(|index_pos| index.entries[*index_pos as usize].offset);
    let mut pack_to_oid = Vec::with_capacity(object_count);
    for index_pos in &pack_order {
        pack_to_oid.push(index.entries[*index_pos as usize].oid);
    }
    let mut oid_to_pack = HashMap::with_capacity(object_count);
    for (pack_pos, oid) in pack_to_oid.iter().enumerate() {
        oid_to_pack.insert(*oid, pack_pos as u32);
    }

    assemble_loaded_bitmap(parsed, object_count, pack_to_oid, oid_to_pack, |position| {
        index.entries.get(position).map(|entry| entry.oid)
    })
    .map(Some)
}

/// Shared tail of the bitmap loaders: expands the type bitmaps, resolves the
/// per-commit entries (XOR offsets reference earlier entries in file order),
/// and maps each entry's lookup-order position back to a commit oid via
/// `lookup_oid`.
fn assemble_loaded_bitmap(
    parsed: PackBitmapIndex,
    object_count: usize,
    pack_to_oid: Vec<ObjectId>,
    oid_to_pack: HashMap<ObjectId, u32>,
    lookup_oid: impl Fn(usize) -> Option<ObjectId>,
) -> Result<LoadedPackBitmap> {
    let word_count = object_count.div_ceil(64);
    let expand = |bitmap: &sley_pack::EwahBitmap| -> Result<Vec<u64>> {
        let mut words = bitmap.to_words()?;
        words.resize(word_count, 0);
        Ok(words)
    };

    let mut resolved: Vec<Arc<Vec<u64>>> = Vec::with_capacity(parsed.entries.len());
    let mut commit_words = HashMap::with_capacity(parsed.entries.len());
    for (entry_index, entry) in parsed.entries.iter().enumerate() {
        let mut words = expand(&entry.bitmap)?;
        if entry.xor_offset > 0 {
            let base_index = entry_index - entry.xor_offset as usize;
            let base = &resolved[base_index];
            for (dst, src) in words.iter_mut().zip(base.iter()) {
                *dst ^= *src;
            }
        }
        let words = Arc::new(words);
        resolved.push(Arc::clone(&words));
        let commit_oid = lookup_oid(entry.object_position as usize)
            .ok_or_else(|| GitError::InvalidFormat("bitmap entry position out of range".into()))?;
        commit_words.insert(commit_oid, words);
    }

    Ok(LoadedPackBitmap {
        object_count: object_count as u32,
        oid_to_pack,
        pack_to_oid,
        commit_words,
        commits: expand(&parsed.type_bitmaps.commits)?,
        trees: expand(&parsed.type_bitmaps.trees)?,
        blobs: expand(&parsed.type_bitmaps.blobs)?,
        tags: expand(&parsed.type_bitmaps.tags)?,
    })
}

/// Result of a bitmap-assisted reachability walk: pack-position bits for
/// in-pack objects plus the "extended" objects encountered outside the
/// bitmapped pack (in first-seen order, like upstream's extended index).
pub struct BitmapWalkResult {
    pub words: Vec<u64>,
    pub extended: Vec<(ObjectId, ObjectType)>,
}

impl BitmapWalkResult {
    /// Removes everything reachable in `haves` from this result.
    pub fn subtract(&mut self, haves: &BitmapWalkResult) {
        for (dst, src) in self.words.iter_mut().zip(haves.words.iter()) {
            *dst &= !*src;
        }
        let have_ext: HashSet<ObjectId> = haves.extended.iter().map(|(oid, _)| *oid).collect();
        self.extended.retain(|(oid, _)| !have_ext.contains(oid));
    }
}

/// Computes the set of objects reachable from `roots` using stored bitmaps
/// where available and a fill-in object walk where not — the consult half of
/// the bitmap engine (upstream `find_objects` + `fill_in_bitmap`).
///
/// Roots may be any object type; tag chains are peeled with every tag object
/// itself included, like the pending-object handling in
/// `prepare_bitmap_walk`. When `include_objects` is false only commits are
/// walked (tree contents of fill-in commits are not marked) — callers that
/// only count/enumerate commits mask with the commit type bitmap, so the
/// extra non-commit bits OR-ed in from stored (closed) bitmaps are harmless.
pub fn bitmap_reachable(
    bitmap: &LoadedPackBitmap,
    db: &impl ObjectReader,
    format: ObjectFormat,
    roots: &[ObjectId],
    include_objects: bool,
) -> Result<BitmapWalkResult> {
    let mut walk = BitmapFillWalk {
        bitmap,
        words: vec![0u64; bitmap.word_count()],
        extended: Vec::new(),
        extended_seen: HashSet::new(),
    };
    let mut commit_stack: Vec<ObjectId> = Vec::new();

    for root in roots {
        let mut oid = *root;
        // Peel tag chains, marking each tag object on the way.
        loop {
            let object = db.read_object(&oid)?;
            match object.object_type {
                ObjectType::Tag => {
                    walk.mark(&oid, ObjectType::Tag);
                    let tag = Tag::parse_ref(format, &object.body)?;
                    oid = tag.object;
                }
                ObjectType::Commit => {
                    commit_stack.push(oid);
                    break;
                }
                ObjectType::Tree => {
                    walk.mark_tree_closure(db, format, &oid)?;
                    break;
                }
                ObjectType::Blob => {
                    walk.mark(&oid, ObjectType::Blob);
                    break;
                }
            }
        }
    }

    while let Some(oid) = commit_stack.pop() {
        if let Some(position) = bitmap.pack_position(&oid) {
            if bitset_get(&walk.words, position) {
                continue;
            }
            if let Some(stored) = bitmap.bitmap_for_commit(&oid) {
                bitset_or(&mut walk.words, stored);
                continue;
            }
            bitset_set(&mut walk.words, position);
        } else {
            if walk.extended_seen.contains(&oid) {
                continue;
            }
            walk.extended_seen.insert(oid);
            walk.extended.push((oid, ObjectType::Commit));
        }
        let object = db.read_object(&oid)?;
        let commit = Commit::parse_ref(format, &object.body)?;
        commit_stack.extend(grafted_parents(db, &oid, commit.parents));
        if include_objects {
            walk.mark_tree_closure(db, format, &commit.tree)?;
        }
    }

    Ok(BitmapWalkResult {
        words: walk.words,
        extended: walk.extended,
    })
}

struct BitmapFillWalk<'a> {
    bitmap: &'a LoadedPackBitmap,
    words: Vec<u64>,
    extended: Vec<(ObjectId, ObjectType)>,
    extended_seen: HashSet<ObjectId>,
}

impl BitmapFillWalk<'_> {
    /// Marks one object; returns false when it was already marked.
    fn mark(&mut self, oid: &ObjectId, object_type: ObjectType) -> bool {
        if let Some(position) = self.bitmap.pack_position(oid) {
            if bitset_get(&self.words, position) {
                return false;
            }
            bitset_set(&mut self.words, position);
            true
        } else {
            if !self.extended_seen.insert(*oid) {
                return false;
            }
            self.extended.push((*oid, object_type));
            true
        }
    }

    /// Marks `tree` and everything below it, skipping subtrees already marked
    /// (a set in-pack bit means its closure is covered: either it came from a
    /// stored — closed — bitmap, or this walk already expanded it).
    fn mark_tree_closure(
        &mut self,
        db: &impl ObjectReader,
        format: ObjectFormat,
        tree: &ObjectId,
    ) -> Result<()> {
        if !self.mark(tree, ObjectType::Tree) {
            return Ok(());
        }
        let object = db.read_object(tree)?;
        for entry in TreeEntries::new(format, &object.body) {
            let entry = entry?;
            if entry.is_gitlink() {
                continue;
            }
            if entry.is_tree() {
                self.mark_tree_closure(db, format, &entry.oid)?;
            } else {
                self.mark(&entry.oid, ObjectType::Blob);
            }
        }
        Ok(())
    }
}

#[derive(Debug)]
pub struct ObjectDatabase {
    format: ObjectFormat,
    // Behind a `Mutex` so `write_object` can take `&self` (matching the
    // `ObjectWriter` trait) and a single handle can interleave reads and writes
    // without a `&mut` borrow — the same shared-by-`&` shape the file-backed
    // database uses for its caches. Removes the need for callers to wrap this in
    // a `RefCell`/`&mut` just to write (see sley-fetch's former `RefCell` dance).
    objects: Mutex<HashMap<ObjectId, Arc<EncodedObject>>>,
    promisor: bool,
}

impl ObjectDatabase {
    pub fn new(format: ObjectFormat) -> Self {
        Self {
            format,
            objects: Mutex::new(HashMap::new()),
            promisor: false,
        }
    }

    pub fn with_promisor(mut self, promisor: bool) -> Self {
        self.promisor = promisor;
        self
    }

    pub fn contains(&self, oid: &ObjectId) -> bool {
        self.objects
            .lock()
            .map(|objects| objects.contains_key(oid))
            .unwrap_or(false)
    }

    pub fn validate(&self, oid: &ObjectId) -> Result<()> {
        let object = self.read_object(oid)?;
        let actual = object.object_id(self.format)?;
        if &actual == oid {
            Ok(())
        } else {
            Err(GitError::InvalidObject(format!(
                "object id mismatch: expected {oid}, got {actual}"
            )))
        }
    }
}

impl ObjectReader for ObjectDatabase {
    fn read_object(&self, oid: &ObjectId) -> Result<Arc<EncodedObject>> {
        self.objects
            .lock()
            .map_err(|_| GitError::object_not_found_in(*oid, MissingObjectContext::Read))?
            .get(oid)
            .map(Arc::clone)
            .or_else(|| implied_empty_tree_object(self.format, oid))
            .ok_or_else(|| GitError::object_not_found_in(*oid, MissingObjectContext::Read))
    }
}

impl ObjectWriter for ObjectDatabase {
    fn write_object(&self, object: EncodedObject) -> Result<ObjectId> {
        let oid = object.object_id(self.format)?;
        self.objects
            .lock()
            .map_err(|_| GitError::Io("object cache lock poisoned".into()))?
            .entry(oid)
            .or_insert_with(|| Arc::new(object));
        Ok(oid)
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Alternate {
    pub path: std::path::PathBuf,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PartialClonePolicy {
    pub promisor_remote: Option<String>,
    pub allow_missing_promised_objects: bool,
}

/// Raw pack-file bytes keyed by pack path, shared across cloned handles. Loaded
/// once so individual objects can be decoded at their offsets (see
/// [`sley_pack::read_object_at`]) without re-reading the whole file per read.
type PackBytesCache = Arc<Mutex<HashMap<PathBuf, Arc<PackData>>>>;

/// Backing bytes of a pack file: either memory-mapped (under the `mmap` feature)
/// or read into the heap. Both deref to `&[u8]`, so the decode path is identical.
#[derive(Debug)]
enum PackData {
    #[cfg(feature = "mmap")]
    Mapped(sley_mmap::MappedFile),
    Heap(Vec<u8>),
}

impl std::ops::Deref for PackData {
    type Target = [u8];

    fn deref(&self) -> &[u8] {
        match self {
            #[cfg(feature = "mmap")]
            Self::Mapped(mapped) => mapped,
            Self::Heap(bytes) => bytes,
        }
    }
}

/// Load a pack file's bytes: memory-mapped when the `mmap` feature is on (falling
/// back to a heap read if the map fails), otherwise read into the heap.
#[cfg(feature = "mmap")]
fn load_pack_data(pack_path: &Path) -> Result<PackData> {
    match sley_mmap::MappedFile::open_pack(pack_path) {
        Ok(mapped) => Ok(PackData::Mapped(mapped)),
        Err(_) => Ok(PackData::Heap(fs::read(pack_path)?)),
    }
}

#[cfg(not(feature = "mmap"))]
fn load_pack_data(pack_path: &Path) -> Result<PackData> {
    Ok(PackData::Heap(fs::read(pack_path)?))
}

/// Memory-capped LRU of recently decoded objects, shared across cloned handles,
/// so hot delta bases and repeated reads during a walk aren't re-decoded. The
/// cache is bounded by an approximate byte budget (not a fixed object count) so
/// it neither thrashes on bulk reads of small objects nor blows up on a few
/// large ones.
type DecodedObjectCache = Arc<Mutex<LruObjectCache>>;

/// Per-pack caches of objects decoded from a pack, keyed by pack path and then by
/// the in-pack byte offset of each object's entry. Shared across cloned handles.
/// This is the delta-base cache: resolving a delta chain by offset reuses already
/// decoded bases instead of re-inflating the whole chain on every read.
type PackDeltaCaches = Arc<Mutex<HashMap<PathBuf, Arc<Mutex<LruOffsetCache>>>>>;

/// Per-pack memo of `in-pack offset -> end-of-chain object type` for the
/// `cat-file --batch-check` header fast path. Resolving a packed delta's *type*
/// walks the delta chain to its base; without this memo every header read
/// re-walks (and re-inflates) the whole chain, so reading every object in a
/// deeply-deltified pack is super-linear (sley#26). The type only depends on the
/// chain base, so memoizing `offset -> type` lets each chain be walked at most
/// once across a batch. Keyed by pack path so an offset key is never applied to
/// the wrong pack's bytes; shared across cloned handles.
/// One pack's offset-keyed header memo (see [`PackHeaderTypeCaches`]).
type PackHeaderTypeCache = Arc<Mutex<HashMap<u64, (ObjectType, u64)>>>;

type PackHeaderTypeCaches = Arc<Mutex<HashMap<PathBuf, PackHeaderTypeCache>>>;

/// Default approximate byte budget for the decoded-object LRU. Sized to comfortably
/// hold the working set of a history walk (commits/trees/blobs and their delta
/// bases) without growing without bound on large repositories. Overridable via the
/// `SLEY_OBJECT_CACHE_BYTES` environment variable; there is currently no git-config
/// hook threaded into the object database, so this constant is the default.
const DEFAULT_OBJECT_CACHE_BYTES: usize = 96 * 1024 * 1024;

/// Default approximate byte budget for each per-pack delta-base cache. Holds the
/// decoded bases of the delta chains being walked so neighboring reads stay warm.
/// Overridable via `SLEY_DELTA_BASE_CACHE_BYTES`.
const DEFAULT_DELTA_BASE_CACHE_BYTES: usize = 96 * 1024 * 1024;

/// Approximate heap cost of caching one [`EncodedObject`]: its body plus a fixed
/// allowance for the key, enum/`Vec` headers, and per-entry map overhead. Used
/// only to drive eviction, so an estimate is fine.
fn cached_object_cost(object: &EncodedObject) -> usize {
    object.body.len().saturating_add(64)
}

/// Read an approximate byte budget from `var`, falling back to `default` when the
/// variable is unset or unparseable. A value of `0` disables the cache.
fn cache_budget_from_env(var: &str, default: usize) -> usize {
    match env::var(var) {
        Ok(value) => value.trim().parse::<usize>().unwrap_or(default),
        Err(_) => default,
    }
}

/// Approximate byte budget for the decoded-object LRU (see
/// [`DEFAULT_OBJECT_CACHE_BYTES`], `SLEY_OBJECT_CACHE_BYTES`).
///
/// Resolved once per process: the environment does not change under us, and a new
/// `FileObjectDatabase` is built often enough (e.g. once per revision resolved)
/// that re-reading the variable each time showed up as per-object overhead.
fn object_cache_budget() -> usize {
    static BUDGET: OnceLock<usize> = OnceLock::new();
    *BUDGET.get_or_init(|| {
        cache_budget_from_env("SLEY_OBJECT_CACHE_BYTES", DEFAULT_OBJECT_CACHE_BYTES)
    })
}

/// Approximate byte budget for each per-pack delta-base cache (see
/// [`DEFAULT_DELTA_BASE_CACHE_BYTES`], `SLEY_DELTA_BASE_CACHE_BYTES`). Resolved
/// once per process for the same reason as [`object_cache_budget`].
fn delta_base_cache_budget() -> usize {
    static BUDGET: OnceLock<usize> = OnceLock::new();
    *BUDGET.get_or_init(|| {
        cache_budget_from_env(
            "SLEY_DELTA_BASE_CACHE_BYTES",
            DEFAULT_DELTA_BASE_CACHE_BYTES,
        )
    })
}

/// Whether to re-hash every object on read and compare it to the requested id.
///
/// Off by default, matching git: reads trust the pack index → offset mapping and
/// the loose object's on-disk name, and object ids are verified where git verifies
/// them — when a pack is received (the index build re-hashes every object) and on
/// demand via [`FileObjectDatabase`]'s `validate`/fsck. Re-hashing on *every* read
/// dominated bulk-read cost (a scalar pure-Rust SHA-1 over each object's full
/// body), so it is opt-in via `SLEY_VERIFY_READS` (any value other than unset, ``,
/// or `0`) for callers that want the paranoid check back. Read once and cached, so
/// the default path pays only a single relaxed atomic load per read.
fn verify_reads_enabled() -> bool {
    static VERIFY: OnceLock<bool> = OnceLock::new();
    *VERIFY.get_or_init(|| match env::var("SLEY_VERIFY_READS") {
        Ok(value) => !matches!(value.trim(), "" | "0"),
        Err(_) => false,
    })
}

/// A memory-capped LRU map from a key `K` to a decoded [`EncodedObject`].
///
/// Eviction is by approximate byte budget (gix-style), not object count, so the
/// cache adapts to object size. On access an entry is moved to most-recently-used;
/// on insert, least-recently-used entries are dropped until the budget holds. A
/// budget of `0` makes the cache inert. Generic over the key so it backs both the
/// oid-keyed decoded-object cache and the offset-keyed delta-base cache.
#[derive(Debug)]
struct LruCache<K: std::hash::Hash + Eq + Clone> {
    budget: usize,
    used: usize,
    map: HashMap<K, Arc<EncodedObject>>,
    order: VecDeque<K>,
}

impl<K: std::hash::Hash + Eq + Clone> LruCache<K> {
    fn new(budget: usize) -> Self {
        Self {
            budget,
            used: 0,
            map: HashMap::new(),
            order: VecDeque::new(),
        }
    }

    fn get(&mut self, key: &K) -> Option<Arc<EncodedObject>> {
        let object = Arc::clone(self.map.get(key)?);
        self.touch(key);
        Some(object)
    }

    /// Move `key` to the most-recently-used end. Linear in the recency queue, but
    /// the queue is bounded by the byte budget and this only runs on cache hits.
    fn touch(&mut self, key: &K) {
        if let Some(position) = self.order.iter().position(|existing| existing == key)
            && let Some(found) = self.order.remove(position)
        {
            self.order.push_back(found);
        }
    }

    /// Drop `key` from both the map and the recency queue, releasing its budget.
    fn remove(&mut self, key: &K) {
        if let Some(object) = self.map.remove(key) {
            self.used = self.used.saturating_sub(cached_object_cost(&object));
        }
        if let Some(position) = self.order.iter().position(|existing| existing == key) {
            self.order.remove(position);
        }
    }

    fn clear(&mut self) {
        self.map.clear();
        self.order.clear();
        self.used = 0;
    }

    fn put(&mut self, key: K, object: Arc<EncodedObject>) {
        if self.budget == 0 {
            return;
        }
        let cost = cached_object_cost(&object);
        // A single object larger than the whole budget is not worth caching; it
        // would immediately evict everything including itself. Drop any stale
        // smaller entry stored under the same key so accounting stays exact.
        if cost > self.budget {
            self.remove(&key);
            return;
        }
        if let Some(previous) = self.map.insert(key.clone(), object) {
            // Replacing an existing entry: adjust accounting and refresh recency.
            self.used = self
                .used
                .saturating_sub(cached_object_cost(&previous))
                .saturating_add(cost);
            self.touch(&key);
        } else {
            self.used = self.used.saturating_add(cost);
            self.order.push_back(key);
        }
        while self.used > self.budget {
            let Some(evicted) = self.order.pop_front() else {
                break;
            };
            if let Some(object) = self.map.remove(&evicted) {
                self.used = self.used.saturating_sub(cached_object_cost(&object));
            }
        }
    }
}

/// Decoded-object cache keyed by object id (loose + packed reads share it).
type LruObjectCache = LruCache<ObjectId>;
/// Delta-base cache keyed by in-pack byte offset, scoped to one pack.
type LruOffsetCache = LruCache<u64>;

/// Bridges the offset-keyed [`LruOffsetCache`] to [`sley_pack::PackDeltaCache`]
/// so the pack decoder can reuse decoded delta bases. Holds the shared cache
/// behind its mutex; a poisoned lock simply behaves as a cache miss/no-op, so a
/// decode still completes correctly (just without reuse).
struct PackDeltaCacheAdapter<'a>(&'a Arc<Mutex<LruOffsetCache>>);

impl sley_pack::PackDeltaCache for PackDeltaCacheAdapter<'_> {
    fn get(&self, offset: u64) -> Option<Arc<EncodedObject>> {
        self.0.lock().ok()?.get(&offset)
    }

    fn insert(&self, offset: u64, object: Arc<EncodedObject>) {
        if let Ok(mut cache) = self.0.lock() {
            cache.put(offset, object);
        }
    }
}

/// Bridges a per-pack `offset -> ObjectType` memo into the header fast path so
/// the ofs-delta chain walk is performed at most once per chain across a batch
/// of `read_object_header` calls (sley#26).
struct PackHeaderTypeCacheAdapter<'a>(&'a PackHeaderTypeCache);

impl sley_pack::HeaderTypeCache for PackHeaderTypeCacheAdapter<'_> {
    fn get(&self, pack_offset: u64) -> Option<(ObjectType, u64)> {
        self.0.lock().ok()?.get(&pack_offset).copied()
    }

    fn put(&mut self, pack_offset: u64, header: (ObjectType, u64)) {
        if let Ok(mut cache) = self.0.lock() {
            cache.insert(pack_offset, header);
        }
    }
}

/// Parsed pack indexes keyed by `.idx` path, shared across cloned handles. Caches
/// the index parse so locating a packed object doesn't re-parse every `.idx` on
/// each read.
type PackIndexCache = Arc<Mutex<HashMap<PathBuf, Arc<PackIndex>>>>;

/// Parsed multi-pack-index files keyed by path, shared across cloned handles.
/// Caches the MIDX parse so object lookups in repositories with a MIDX avoid
/// reparsing the same fanout/object tables for every read.
type MultiPackIndexCache = Arc<Mutex<HashMap<PathBuf, Arc<MultiPackIndex>>>>;

/// A `.idx`/`.pack` pair discovered in a pack directory.
#[derive(Debug, Clone)]
struct DiscoveredPack {
    idx: PathBuf,
    pack: PathBuf,
}

/// The discovered `.idx`/`.pack` pairs in each pack directory, keyed by the pack
/// directory and shared across cloned handles. Caches the directory scan so a
/// bulk read (e.g. `cat-file --batch`) does not `read_dir` the pack directory on
/// every object lookup. New packs are still found: a lookup that misses every
/// cached pack re-scans the directory once before concluding the object is absent
/// (see [`FileObjectDatabase::find_pack_containing`]).
type PackListingCache = Arc<Mutex<HashMap<PathBuf, Arc<Vec<DiscoveredPack>>>>>;

#[derive(Debug, Clone)]
pub struct FileObjectDatabase {
    loose: LooseObjectStore,
    objects_dir: PathBuf,
    alternates: Vec<PathBuf>,
    format: ObjectFormat,
    pack_bytes: PackBytesCache,
    pack_indexes: PackIndexCache,
    multi_pack_indexes: MultiPackIndexCache,
    pack_listing: PackListingCache,
    decoded: DecodedObjectCache,
    pack_deltas: PackDeltaCaches,
    pack_header_types: PackHeaderTypeCaches,
    /// Graft points (`$GIT_DIR/shallow`), loaded lazily on the first
    /// [`ObjectReader::is_shallow_graft`] query. `$GIT_DIR` is taken to be
    /// the parent of `objects_dir`, matching the standard layout.
    shallow_grafts: Arc<std::sync::OnceLock<HashSet<ObjectId>>>,
}

/// Parse `$GIT_DIR/shallow`: one hex object id per line. A missing file is an
/// empty set (the repository is not shallow); unparsable lines are ignored so
/// a torn write never poisons walks.
fn read_shallow_grafts(shallow_file: &Path, format: ObjectFormat) -> HashSet<ObjectId> {
    let Ok(contents) = std::fs::read_to_string(shallow_file) else {
        return HashSet::new();
    };
    contents
        .lines()
        .filter_map(|line| ObjectId::from_hex(format, line.trim()).ok())
        .collect()
}

pub fn repository_objects_dir(git_dir: impl AsRef<Path>) -> PathBuf {
    env::var_os("GIT_OBJECT_DIRECTORY")
        .map(PathBuf::from)
        .unwrap_or_else(|| repository_common_dir(git_dir).join("objects"))
}

pub fn repository_common_dir(git_dir: impl AsRef<Path>) -> PathBuf {
    if let Some(common_dir) = env::var_os("GIT_COMMON_DIR") {
        return PathBuf::from(common_dir);
    }
    let git_dir = git_dir.as_ref();
    let commondir = git_dir.join("commondir");
    if let Ok(value) = fs::read_to_string(&commondir) {
        let path = PathBuf::from(value.trim());
        let common = if path.is_absolute() {
            path
        } else {
            git_dir.join(path)
        };
        return fs::canonicalize(&common).unwrap_or(common);
    }
    git_dir.to_path_buf()
}

pub fn repository_object_ids(
    git_dir: impl AsRef<Path>,
    format: ObjectFormat,
) -> Result<Vec<ObjectId>> {
    object_ids_in_objects_dir(repository_objects_dir(git_dir), format)
}

pub fn object_ids_in_objects_dir(
    objects_dir: impl AsRef<Path>,
    format: ObjectFormat,
) -> Result<Vec<ObjectId>> {
    let objects_dir = objects_dir.as_ref();
    let mut oids = HashSet::new();
    collect_loose_object_ids(objects_dir, format, &mut oids)?;
    collect_packed_object_ids(&objects_dir.join("pack"), format, &mut oids)?;
    let mut oids = oids.into_iter().collect::<Vec<_>>();
    oids.sort_by_key(ObjectId::to_hex);
    Ok(oids)
}

fn collect_loose_object_ids(
    objects_dir: &Path,
    format: ObjectFormat,
    oids: &mut HashSet<ObjectId>,
) -> Result<()> {
    if !objects_dir.exists() {
        return Ok(());
    }
    let hex_len = format.hex_len();
    for entry in fs::read_dir(objects_dir)? {
        let entry = entry?;
        if !entry.file_type()?.is_dir() {
            continue;
        }
        let name = entry.file_name();
        let Some(fanout) = name.to_str() else {
            continue;
        };
        if fanout.len() != 2 || !fanout.bytes().all(|byte| byte.is_ascii_hexdigit()) {
            continue;
        }
        for object_entry in fs::read_dir(entry.path())? {
            let object_entry = object_entry?;
            if !object_entry.file_type()?.is_file() {
                continue;
            }
            let name = object_entry.file_name();
            let Some(suffix) = name.to_str() else {
                continue;
            };
            if suffix.len() != hex_len - 2 || !suffix.bytes().all(|byte| byte.is_ascii_hexdigit()) {
                continue;
            }
            oids.insert(ObjectId::from_hex(format, &format!("{fanout}{suffix}"))?);
        }
    }
    Ok(())
}

fn collect_loose_fanout_object_ids(
    objects_dir: &Path,
    format: ObjectFormat,
    fanout: u8,
    oids: &mut HashSet<ObjectId>,
) -> Result<()> {
    let fanout_hex = format!("{fanout:02x}");
    let fanout_dir = objects_dir.join(&fanout_hex);
    let entries = match fs::read_dir(&fanout_dir) {
        Ok(entries) => entries,
        Err(err) if err.kind() == std::io::ErrorKind::NotFound => return Ok(()),
        Err(err) => return Err(GitError::Io(err.to_string())),
    };
    let hex_len = format.hex_len();
    for object_entry in entries {
        let object_entry = object_entry?;
        let name = object_entry.file_name();
        let Some(suffix) = name.to_str() else {
            continue;
        };
        if suffix.len() != hex_len - 2 || !suffix.bytes().all(|byte| byte.is_ascii_hexdigit()) {
            continue;
        }
        oids.insert(ObjectId::from_hex(format, &format!("{fanout_hex}{suffix}"))?);
    }
    Ok(())
}

#[derive(Debug, Default)]
struct LoosePresenceCache {
    loaded_fanouts: HashSet<u8>,
    objects: HashSet<ObjectId>,
}

/// Every object id resolvable through a pack (any `.idx` or the
/// multi-pack-index) under `objects_dir/pack`. Used by `--unpacked`
/// filtering: an object is "unpacked" when absent from this set, regardless
/// of a loose copy also existing.
pub fn packed_object_ids(
    objects_dir: impl AsRef<Path>,
    format: ObjectFormat,
) -> Result<HashSet<ObjectId>> {
    let mut oids = HashSet::new();
    collect_packed_object_ids(&objects_dir.as_ref().join("pack"), format, &mut oids)?;
    Ok(oids)
}

fn collect_packed_object_ids(
    pack_dir: &Path,
    format: ObjectFormat,
    oids: &mut HashSet<ObjectId>,
) -> Result<()> {
    if !pack_dir.exists() {
        return Ok(());
    }
    let midx_path = pack_dir.join("multi-pack-index");
    if midx_path.exists() {
        let midx = MultiPackIndex::parse(&fs::read(&midx_path)?, format)?;
        oids.extend(midx.objects.into_iter().map(|entry| entry.oid));
    }
    for entry in fs::read_dir(pack_dir)? {
        let path = entry?.path();
        if path.extension().and_then(|ext| ext.to_str()) != Some("idx") {
            continue;
        }
        let index = PackIndex::parse(&fs::read(path)?, format)?;
        oids.extend(index.entries.into_iter().map(|entry| entry.oid));
    }
    Ok(())
}

impl FileObjectDatabase {
    /// The object-id format (hash algorithm) this database was opened with.
    pub fn object_format(&self) -> ObjectFormat {
        self.format
    }

    /// The repository object directory this database reads from.
    pub fn objects_dir(&self) -> &Path {
        &self.objects_dir
    }

    pub fn new(objects_dir: impl Into<PathBuf>, format: ObjectFormat) -> Self {
        let objects_dir = objects_dir.into();
        Self {
            loose: LooseObjectStore::new(objects_dir.clone(), format),
            alternates: alternate_object_dirs(&objects_dir),
            objects_dir,
            format,
            pack_bytes: Arc::new(Mutex::new(HashMap::new())),
            pack_indexes: Arc::new(Mutex::new(HashMap::new())),
            multi_pack_indexes: Arc::new(Mutex::new(HashMap::new())),
            pack_listing: Arc::new(Mutex::new(HashMap::new())),
            decoded: Arc::new(Mutex::new(LruObjectCache::new(object_cache_budget()))),
            pack_deltas: Arc::new(Mutex::new(HashMap::new())),
            pack_header_types: Arc::new(Mutex::new(HashMap::new())),
            shallow_grafts: Arc::new(std::sync::OnceLock::new()),
        }
    }

    fn without_alternates(objects_dir: impl Into<PathBuf>, format: ObjectFormat) -> Self {
        let objects_dir = objects_dir.into();
        Self {
            loose: LooseObjectStore::new(objects_dir.clone(), format),
            alternates: Vec::new(),
            objects_dir,
            format,
            pack_bytes: Arc::new(Mutex::new(HashMap::new())),
            pack_indexes: Arc::new(Mutex::new(HashMap::new())),
            multi_pack_indexes: Arc::new(Mutex::new(HashMap::new())),
            pack_listing: Arc::new(Mutex::new(HashMap::new())),
            decoded: Arc::new(Mutex::new(LruObjectCache::new(object_cache_budget()))),
            pack_deltas: Arc::new(Mutex::new(HashMap::new())),
            pack_header_types: Arc::new(Mutex::new(HashMap::new())),
            shallow_grafts: Arc::new(std::sync::OnceLock::new()),
        }
    }

    pub fn from_git_dir(git_dir: impl AsRef<Path>, format: ObjectFormat) -> Self {
        Self::new(repository_objects_dir(git_dir), format)
    }

    /// Drop cached pack listings, indexes, and decoded objects so the next read
    /// sees packs/objects installed after this handle was created (e.g. after
    /// `fetch` or `install_pack`). Long-lived [`Repository`] sessions call this
    /// via the owning repository's `refresh_objects` hook.
    pub fn refresh_read_cache(&self) {
        if let Ok(mut cache) = self.pack_listing.lock() {
            cache.clear();
        }
        if let Ok(mut cache) = self.pack_indexes.lock() {
            cache.clear();
        }
        if let Ok(mut cache) = self.multi_pack_indexes.lock() {
            cache.clear();
        }
        if let Ok(mut cache) = self.pack_bytes.lock() {
            cache.clear();
        }
        if let Ok(mut cache) = self.pack_deltas.lock() {
            cache.clear();
        }
        if let Ok(mut cache) = self.pack_header_types.lock() {
            cache.clear();
        }
        if let Ok(mut cache) = self.decoded.lock() {
            cache.clear();
        }
        self.loose.invalidate_cache();
    }

    pub fn loose(&self) -> &LooseObjectStore {
        &self.loose
    }

    pub fn install_pack(&self, pack: &PackWrite) -> Result<PackInstallResult> {
        self.install_pack_with_options(pack, RawPackInstallOptions::default())
    }

    pub fn install_pack_with_options(
        &self,
        pack: &PackWrite,
        options: RawPackInstallOptions,
    ) -> Result<PackInstallResult> {
        if pack.checksum.format() != self.format {
            return Err(GitError::InvalidObjectId(format!(
                "pack checksum uses {}, store uses {}",
                pack.checksum.format().name(),
                self.format.name()
            )));
        }
        for entry in &pack.entries {
            if entry.oid.format() != self.format {
                return Err(GitError::InvalidObjectId(format!(
                    "pack entry {} uses {}, store uses {}",
                    entry.oid,
                    entry.oid.format().name(),
                    self.format.name()
                )));
            }
        }
        let canonical_index = PackIndex::write_v2_for_pack(&pack.pack, self.format)?;
        let parsed_index = PackIndex::parse(&pack.index, self.format)?;
        if canonical_index.pack_checksum != pack.checksum
            || parsed_index.pack_checksum != pack.checksum
        {
            return Err(GitError::InvalidFormat(
                "pack and index checksums do not match pack write".into(),
            ));
        }
        if pack.index != canonical_index.index {
            return Err(GitError::InvalidFormat(
                "pack index does not match pack contents".into(),
            ));
        }

        let pack_dir = self.objects_dir.join("pack");
        fs::create_dir_all(&pack_dir)?;
        let pack_name = format!("pack-{}", pack.checksum.to_hex());
        let pack_path = pack_dir.join(format!("{pack_name}.pack"));
        let index_path = pack_dir.join(format!("{pack_name}.idx"));
        if !pack_path.exists() || !index_path.exists() {
            write_pack_component(&pack_path, &pack.pack)?;
            write_pack_component(&index_path, &pack.index)?;
        }
        let promisor_path = write_promisor_pack_sidecar(&pack_dir, &pack_name, options.promisor)?;
        Ok(PackInstallResult {
            pack_name,
            pack_path,
            index_path,
            promisor_path,
            object_ids: canonical_index
                .entries
                .iter()
                .map(|entry| entry.oid)
                .collect(),
        })
    }

    /// Install a pack that was produced in this process by [`PackFile::write_packed`].
    ///
    /// Unlike [`Self::install_raw_pack_with_options`], this does not re-inflate
    /// every pack entry to rebuild the index. It validates the generated pack
    /// trailer and generated index against the writer's object ids, CRCs, and
    /// offsets, then writes those bytes directly. Use the raw installer for
    /// arbitrary pack bytes received from an untrusted transport.
    pub fn install_written_pack(&self, pack: &PackWrite) -> Result<PackInstallResult> {
        self.install_written_pack_with_options(pack, RawPackInstallOptions::default())
    }

    pub fn install_written_pack_with_options(
        &self,
        pack: &PackWrite,
        options: RawPackInstallOptions,
    ) -> Result<PackInstallResult> {
        validate_pack_checksum(&pack.pack, self.format, &pack.checksum, "pack write")?;
        let parsed_index = PackIndex::parse(&pack.index, self.format)?;
        if parsed_index.pack_checksum != pack.checksum {
            return Err(GitError::InvalidFormat(
                "pack write index checksum does not match pack".into(),
            ));
        }
        if !pack_index_entries_match_writer(&parsed_index.entries, &pack.entries) {
            return Err(GitError::InvalidFormat(
                "pack write index does not match generated entries".into(),
            ));
        }
        self.install_generated_pack_unchecked(pack, options)
    }

    fn install_generated_pack_unchecked(
        &self,
        pack: &PackWrite,
        options: RawPackInstallOptions,
    ) -> Result<PackInstallResult> {
        let pack_dir = self.objects_dir.join("pack");
        fs::create_dir_all(&pack_dir)?;
        let pack_name = format!("pack-{}", pack.checksum.to_hex());
        let pack_path = pack_dir.join(format!("{pack_name}.pack"));
        let index_path = pack_dir.join(format!("{pack_name}.idx"));
        if !pack_path.exists() || !index_path.exists() {
            write_pack_component(&pack_path, &pack.pack)?;
            write_pack_component(&index_path, &pack.index)?;
        }
        let promisor_path = write_promisor_pack_sidecar(&pack_dir, &pack_name, options.promisor)?;
        Ok(PackInstallResult {
            pack_name,
            pack_path,
            index_path,
            promisor_path,
            object_ids: pack.entries.iter().map(|entry| entry.oid).collect(),
        })
    }

    pub fn install_raw_pack(&self, pack_bytes: &[u8]) -> Result<PackInstallResult> {
        self.install_raw_pack_with_options(pack_bytes, RawPackInstallOptions::default())
    }

    pub fn install_raw_pack_with_options(
        &self,
        pack_bytes: &[u8],
        options: RawPackInstallOptions,
    ) -> Result<PackInstallResult> {
        let built = PackIndex::write_v2_for_pack(pack_bytes, self.format)?;
        let pack_dir = self.objects_dir.join("pack");
        fs::create_dir_all(&pack_dir)?;
        let pack_name = format!("pack-{}", built.pack_checksum.to_hex());
        let pack_path = pack_dir.join(format!("{pack_name}.pack"));
        let index_path = pack_dir.join(format!("{pack_name}.idx"));
        if !pack_path.exists() || !index_path.exists() {
            write_pack_component(&pack_path, pack_bytes)?;
            write_pack_component(&index_path, &built.index)?;
        }
        let promisor_path = write_promisor_pack_sidecar(&pack_dir, &pack_name, options.promisor)?;
        Ok(PackInstallResult {
            pack_name,
            pack_path,
            index_path,
            promisor_path,
            object_ids: built.entries.iter().map(|entry| entry.oid).collect(),
        })
    }

    pub fn contains(&self, oid: &ObjectId) -> Result<bool> {
        if self.loose.exists(oid)? {
            return Ok(true);
        }
        if self.find_pack_containing(oid)?.is_some() {
            return Ok(true);
        }
        for alternate in &self.alternates {
            if Self::without_alternates(alternate, self.format).contains(oid)? {
                return Ok(true);
            }
        }
        // Reprepare-on-miss: a cached negative loose verdict may predate a
        // sibling write. Drop it and exact-probe once before reporting absence.
        self.loose.invalidate_cache();
        self.loose.exists(oid)
    }

    pub fn object_ids(&self) -> Result<Vec<ObjectId>> {
        let mut oids = object_ids_in_objects_dir(&self.objects_dir, self.format)?
            .into_iter()
            .collect::<HashSet<_>>();
        for alternate in &self.alternates {
            oids.extend(Self::without_alternates(alternate, self.format).object_ids()?);
        }
        let mut oids = oids.into_iter().collect::<Vec<_>>();
        oids.sort_by_key(ObjectId::to_hex);
        Ok(oids)
    }

    pub fn object_storage_info(&self, oid: &ObjectId) -> Result<Option<ObjectStorageInfo>> {
        if let Some(disk_size) = self.loose.disk_size(oid)? {
            return Ok(Some(ObjectStorageInfo {
                disk_size,
                deltabase: zero_oid(self.format)?,
            }));
        }
        if let Some(info) = self.packed_object_storage_info(oid)? {
            return Ok(Some(info));
        }
        for alternate in &self.alternates {
            if let Some(info) =
                Self::without_alternates(alternate, self.format).object_storage_info(oid)?
            {
                return Ok(Some(info));
            }
        }
        // Reprepare-on-miss: drop any stale negative loose cache and exact-probe
        // once before reporting absence (see `read_object`).
        self.loose.invalidate_cache();
        if let Some(disk_size) = self.loose.disk_size(oid)? {
            return Ok(Some(ObjectStorageInfo {
                disk_size,
                deltabase: zero_oid(self.format)?,
            }));
        }
        Ok(None)
    }

    pub fn resolve_prefix(&self, prefix: &str) -> Result<ObjectPrefixResolution> {
        validate_object_id_prefix(self.format, prefix)?;
        let mut matches = Vec::new();
        for oid in self.object_ids()? {
            if object_id_matches_prefix(&oid, prefix) {
                matches.push(oid);
            }
        }
        Ok(match matches.len() {
            0 => ObjectPrefixResolution::Missing,
            1 => ObjectPrefixResolution::Unique(matches.remove(0)),
            _ => ObjectPrefixResolution::Ambiguous(matches),
        })
    }

    /// The object type and content size of `oid` without decoding its full body —
    /// git's `cat-file --batch-check` fast path. Tries the decoded-object cache,
    /// then loose storage (inflating only the framing header), then packs (reading
    /// the entry header and, for deltas, only the delta's leading varints), then
    /// alternates. Returns `Ok(None)` if the object is not present.
    ///
    /// Unlike [`ObjectReader::read_object`], this never materializes the body, so it
    /// stays cheap on huge blobs and deep delta chains. It does not populate the
    /// decoded-object cache (nothing is decoded).
    pub fn read_object_header(&self, oid: &ObjectId) -> Result<Option<(ObjectType, u64)>> {
        if implied_empty_tree_object(self.format, oid).is_some() {
            return Ok(Some((ObjectType::Tree, 0)));
        }
        if let Ok(mut cache) = self.decoded.lock()
            && let Some(object) = cache.get(oid)
        {
            return Ok(Some((object.object_type, object.body.len() as u64)));
        }
        if let Some(header) = self.loose.read_header(oid)? {
            return Ok(Some(header));
        }
        if let Some(pack_paths) = self.find_pack_containing(oid)? {
            let bytes = self.cached_pack_bytes(&pack_paths.pack)?;
            // Per-pack offset->type memo so the ofs-delta chain walk that resolves
            // a packed object's type runs at most once per chain across the batch,
            // instead of re-walking (and re-inflating each link's leading varints)
            // on every header read — the sley#26 super-linear cat-file --batch-check.
            let type_cache = self.pack_header_type_cache(&pack_paths.pack);
            let resolve_ref_base = |base: &ObjectId| {
                self.read_object_header(base)
                    .map(|header| header.map(|(t, _)| t))
            };
            let header = match &type_cache {
                Some(cache) => {
                    let mut adapter = PackHeaderTypeCacheAdapter(cache);
                    sley_pack::read_object_header_at_with_cache(
                        &bytes,
                        pack_paths.offset,
                        self.format,
                        resolve_ref_base,
                        &mut adapter,
                    )?
                }
                None => sley_pack::read_object_header_at(
                    &bytes,
                    pack_paths.offset,
                    self.format,
                    resolve_ref_base,
                )?,
            };
            return Ok(Some(header));
        }
        for alternate in &self.alternates {
            if let Some(header) =
                Self::without_alternates(alternate, self.format).read_object_header(oid)?
            {
                return Ok(Some(header));
            }
        }
        // Reprepare-on-miss: discard any stale negative loose cache and retry an
        // exact path probe once before reporting absence (see `read_object`).
        self.loose.invalidate_cache();
        if let Some(header) = self.loose.read_header(oid)? {
            return Ok(Some(header));
        }
        Ok(None)
    }

    fn read_packed_object(&self, oid: &ObjectId) -> Result<Option<Arc<EncodedObject>>> {
        // Memory-capped decoded-object cache first (delta-base reuse for ref-delta
        // bases that resolve back through the store + repeated whole-object reads).
        if let Ok(mut cache) = self.decoded.lock()
            && let Some(object) = cache.get(oid)
        {
            return Ok(Some(object));
        }
        let Some(pack_paths) = self.find_pack_containing(oid)? else {
            return Ok(None);
        };
        let bytes = self.cached_pack_bytes(&pack_paths.pack)?;
        // Per-pack delta-base cache (keyed by in-pack offset). Resolving an
        // ofs-delta chain reuses already-decoded bases instead of re-inflating the
        // whole chain on every read. Scoped to this pack's path so an offset key is
        // never applied to the wrong pack's bytes.
        let delta_cache = self.pack_delta_cache(&pack_paths.pack);
        let delta_adapter = delta_cache.as_ref().map(PackDeltaCacheAdapter);
        // Decode only this object at its offset (plus its delta-base chain). A
        // ref-delta base resolves through the full store (loose / other packs) and
        // reuses the decoded-object cache. No cache lock is held across the decode,
        // so the recursive resolver re-entry (which may re-enter read_object) is
        // safe.
        let resolve_ref_base = |base: &ObjectId| self.read_object(base).map(Some);
        let object = match &delta_adapter {
            Some(adapter) => sley_pack::read_object_at_with_cache_arc(
                &bytes,
                pack_paths.offset,
                self.format,
                resolve_ref_base,
                adapter,
            )?,
            None => sley_pack::read_object_at_arc(
                &bytes,
                pack_paths.offset,
                self.format,
                resolve_ref_base,
            )?,
        };
        // Trust the index → offset mapping rather than re-hashing every decoded
        // object on read (see `verify_reads_enabled`); this re-hash dominated
        // bulk-read cost. Opt back in with `SLEY_VERIFY_READS` for a paranoid check.
        if verify_reads_enabled() {
            let actual = object.object_id(self.format)?;
            if actual != *oid {
                return Err(GitError::InvalidObject(format!(
                    "pack object id mismatch: index says {oid}, decoded {actual}"
                )));
            }
        }
        if let Ok(mut cache) = self.decoded.lock() {
            cache.put(*oid, Arc::clone(&object));
        }
        Ok(Some(object))
    }

    /// The per-pack delta-base cache for `pack_path`, creating it on first use.
    /// Returns `None` only if the shared map's lock is poisoned, in which case the
    /// caller falls back to an uncached decode (correctness preserved).
    fn pack_delta_cache(&self, pack_path: &Path) -> Option<Arc<Mutex<LruOffsetCache>>> {
        let mut caches = self.pack_deltas.lock().ok()?;
        let cache = caches.entry(pack_path.to_path_buf()).or_insert_with(|| {
            Arc::new(Mutex::new(LruOffsetCache::new(delta_base_cache_budget())))
        });
        Some(Arc::clone(cache))
    }

    /// The per-pack header-type memo for `pack_path`, creating it on first use.
    /// Returns `None` only if the shared map's lock is poisoned, in which case the
    /// caller falls back to an unmemoized header walk (correctness preserved).
    fn pack_header_type_cache(&self, pack_path: &Path) -> Option<PackHeaderTypeCache> {
        let mut caches = self.pack_header_types.lock().ok()?;
        let cache = caches
            .entry(pack_path.to_path_buf())
            .or_insert_with(|| Arc::new(Mutex::new(HashMap::new())));
        Some(Arc::clone(cache))
    }

    /// Backing bytes of the pack at `pack_path`, loaded at most once per database
    /// handle (cached, shared across clones). Memory-mapped under the `mmap` feature,
    /// otherwise read into the heap. On a poisoned lock it falls back to loading
    /// without caching, preserving correctness.
    fn cached_pack_bytes(&self, pack_path: &Path) -> Result<Arc<PackData>> {
        if let Ok(cache) = self.pack_bytes.lock()
            && let Some(bytes) = cache.get(pack_path)
        {
            return Ok(Arc::clone(bytes));
        }
        let bytes = Arc::new(load_pack_data(pack_path)?);
        if let Ok(mut cache) = self.pack_bytes.lock() {
            cache.insert(pack_path.to_path_buf(), Arc::clone(&bytes));
        }
        Ok(bytes)
    }

    /// Parsed index for the `.idx` at `index_path`, parsed at most once per
    /// database handle. On a poisoned lock it falls back to parsing without
    /// caching, preserving correctness.
    fn cached_pack_index(&self, index_path: &Path) -> Result<Arc<PackIndex>> {
        if let Ok(cache) = self.pack_indexes.lock()
            && let Some(index) = cache.get(index_path)
        {
            return Ok(Arc::clone(index));
        }
        let index = Arc::new(PackIndex::parse(&fs::read(index_path)?, self.format)?);
        if let Ok(mut cache) = self.pack_indexes.lock() {
            cache.insert(index_path.to_path_buf(), Arc::clone(&index));
        }
        Ok(index)
    }

    /// Parsed multi-pack-index at `midx_path`, parsed at most once per database
    /// handle. Returns `Ok(None)` when no MIDX exists. On a poisoned lock it
    /// falls back to parsing without caching, preserving correctness.
    fn cached_multi_pack_index(&self, midx_path: &Path) -> Result<Option<Arc<MultiPackIndex>>> {
        if !midx_path.exists() {
            return Ok(None);
        }
        if let Ok(cache) = self.multi_pack_indexes.lock()
            && let Some(midx) = cache.get(midx_path)
        {
            return Ok(Some(Arc::clone(midx)));
        }
        let midx = Arc::new(MultiPackIndex::parse(&fs::read(midx_path)?, self.format)?);
        if let Ok(mut cache) = self.multi_pack_indexes.lock() {
            cache.insert(midx_path.to_path_buf(), Arc::clone(&midx));
        }
        Ok(Some(midx))
    }

    /// The discovered `.idx`/`.pack` pairs in `pack_dir`, cached and shared across
    /// clones. With `force_rescan`, the directory is re-read; the freshly scanned
    /// listing is only stored (and returned as a new `Arc`) when its set of `.idx`
    /// files actually differs from the cached one, so an unchanged directory keeps
    /// the same `Arc` (letting callers detect "nothing new" cheaply). On a poisoned
    /// lock it scans without caching, preserving correctness.
    fn cached_pack_listing(
        &self,
        pack_dir: &Path,
        force_rescan: bool,
    ) -> Result<Arc<Vec<DiscoveredPack>>> {
        if !force_rescan
            && let Ok(cache) = self.pack_listing.lock()
            && let Some(listing) = cache.get(pack_dir)
        {
            return Ok(Arc::clone(listing));
        }
        let scanned = Arc::new(scan_pack_listing(pack_dir)?);
        if let Ok(mut cache) = self.pack_listing.lock() {
            match cache.get(pack_dir) {
                // Keep the existing Arc when the scan found the same set of packs,
                // so repeated misses don't churn the cache or callers' pointers.
                Some(existing) if same_pack_set(existing, &scanned) => {
                    return Ok(Arc::clone(existing));
                }
                _ => {
                    cache.insert(pack_dir.to_path_buf(), Arc::clone(&scanned));
                }
            }
        }
        Ok(scanned)
    }

    /// Find `oid` among a cached pack listing, returning its pack path and offset.
    /// Uses the parsed-index cache, so this performs no directory I/O.
    fn find_in_pack_listing(
        &self,
        listing: &[DiscoveredPack],
        oid: &ObjectId,
    ) -> Result<Option<PackPaths>> {
        for pack in listing {
            let index = self.cached_pack_index(&pack.idx)?;
            if let Some(entry) = index.find(oid) {
                return Ok(Some(PackPaths {
                    pack: pack.pack.clone(),
                    offset: entry.offset,
                }));
            }
        }
        Ok(None)
    }

    fn find_pack_containing(&self, oid: &ObjectId) -> Result<Option<PackPaths>> {
        if oid.format() != self.format {
            return Err(GitError::InvalidObjectId(format!(
                "object {oid} uses {}, store uses {}",
                oid.format().name(),
                self.format.name()
            )));
        }
        let pack_dir = self.objects_dir.join("pack");
        // Hot path: a previously cached pack listing or multi-pack-index already
        // names every pack, and locating `oid` in them is pure in-memory index
        // work (no directory I/O). Try that first so a warm handle doesn't stat
        // the pack dir / multi-pack-index on every single lookup — that redundant
        // per-object FS probing is what made `cat-file --batch-check` scale poorly
        // versus git, which resolves through its in-memory index (sley#26).
        if let Some(midx) = self.cached_loaded_multi_pack_index()
            && let Some(pack_paths) = self.midx_pack_paths(&pack_dir, &midx, oid)?
        {
            return Ok(Some(pack_paths));
        }
        if let Some(listing) = self.cached_loaded_pack_listing(&pack_dir)
            && let Some(pack_paths) = self.find_in_pack_listing(&listing, oid)?
        {
            return Ok(Some(pack_paths));
        }

        if !pack_dir.exists() {
            return Ok(None);
        }
        if let Some(pack_paths) = self.find_midx_pack_containing(&pack_dir, oid)? {
            return Ok(Some(pack_paths));
        }
        // Search the cached directory listing first. On a complete miss, re-scan
        // the directory once (picking up any pack added since the listing was
        // cached) and search again, so newly written packs are still found.
        let listing = self.cached_pack_listing(&pack_dir, false)?;
        if let Some(pack_paths) = self.find_in_pack_listing(&listing, oid)? {
            return Ok(Some(pack_paths));
        }
        let refreshed = self.cached_pack_listing(&pack_dir, true)?;
        if Arc::ptr_eq(&listing, &refreshed) {
            // The re-scan produced the same listing, so nothing new appeared.
            return Ok(None);
        }
        self.find_in_pack_listing(&refreshed, oid)
    }

    fn packed_object_storage_info(&self, oid: &ObjectId) -> Result<Option<ObjectStorageInfo>> {
        let Some(pack_paths) = self.find_pack_containing(oid)? else {
            return Ok(None);
        };
        let pack_len = fs::metadata(&pack_paths.pack)?.len();
        let trailer_offset = pack_len
            .checked_sub(self.format.raw_len() as u64)
            .ok_or_else(|| GitError::InvalidFormat("pack file shorter than checksum".into()))?;
        let index_path = pack_paths.pack.with_extension("idx");
        let index = self.cached_pack_index(&index_path)?;
        let pack = self.cached_pack_bytes(&pack_paths.pack)?;
        let delta_base = pack_entry_delta_base(self.format, &pack, pack_paths.offset)?;
        let delta_base_offset = match &delta_base {
            Some(PackDeltaBase::Offset(offset)) => Some(*offset),
            Some(PackDeltaBase::Ref(_)) | None => None,
        };
        let offset_info =
            scan_pack_index_offsets(&index, pack_paths.offset, trailer_offset, delta_base_offset)?;
        let disk_size = offset_info
            .end_offset
            .checked_sub(pack_paths.offset)
            .ok_or_else(|| GitError::InvalidFormat("pack index offsets are not sorted".into()))?;
        let deltabase = match delta_base {
            Some(PackDeltaBase::Offset(_)) => offset_info.delta_base_oid.ok_or_else(|| {
                // scan_pack_index_offsets returns Err when delta_base_offset is
                // Some but no matching entry is found, so this is unreachable for
                // valid packs; propagate as an error rather than panic to keep a
                // malformed pack from taking down the process if that invariant
                // ever drifts.
                GitError::InvalidFormat("ofs-delta base oid missing from pack index".into())
            })?,
            Some(PackDeltaBase::Ref(oid)) => oid,
            None => zero_oid(self.format)?,
        };
        Ok(Some(ObjectStorageInfo {
            disk_size,
            deltabase,
        }))
    }

    fn find_midx_pack_containing(
        &self,
        pack_dir: &Path,
        oid: &ObjectId,
    ) -> Result<Option<PackPaths>> {
        let midx_path = pack_dir.join("multi-pack-index");
        let Some(midx) = self.cached_multi_pack_index(&midx_path)? else {
            return Ok(None);
        };
        self.midx_pack_paths(pack_dir, &midx, oid)
    }

    /// Resolve `oid` against an already-loaded multi-pack-index, returning the pack
    /// path and in-pack offset. Pure in-memory index work; performs no filesystem
    /// access. The named pack's existence was established when the midx was parsed
    /// and cached, so the hot lookup path no longer re-`stat()`s it on every call —
    /// a missing pack surfaces as an `open()` failure when the bytes are actually
    /// read (`cached_pack_bytes`), not as a redundant per-lookup existence probe.
    fn midx_pack_paths(
        &self,
        pack_dir: &Path,
        midx: &MultiPackIndex,
        oid: &ObjectId,
    ) -> Result<Option<PackPaths>> {
        let Some(entry) = midx.find(oid) else {
            return Ok(None);
        };
        let Some(pack_name) = midx.pack_names.get(entry.pack_int_id as usize) else {
            return Err(GitError::InvalidFormat(
                "multi-pack-index object points past pack table".into(),
            ));
        };
        let pack_file_name = pack_name
            .strip_suffix(".idx")
            .map(|stem| format!("{stem}.pack"))
            .unwrap_or_else(|| pack_name.clone());
        let pack = pack_dir.join(pack_file_name);
        Ok(Some(PackPaths {
            pack,
            offset: entry.offset,
        }))
    }

    /// The multi-pack-index for this object store *only if already parsed and
    /// cached* — never touches the filesystem. Used by the lookup hot path to skip
    /// the per-call `multi-pack-index` existence stat when a handle is warm.
    fn cached_loaded_multi_pack_index(&self) -> Option<Arc<MultiPackIndex>> {
        let midx_path = self.objects_dir.join("pack").join("multi-pack-index");
        let cache = self.multi_pack_indexes.lock().ok()?;
        cache.get(&midx_path).map(Arc::clone)
    }

    /// The discovered pack listing for `pack_dir` *only if already scanned and
    /// cached* — never touches the filesystem. Used by the lookup hot path to skip
    /// the per-call pack-dir existence stat when a handle is warm. A cold cache (or
    /// a poisoned lock) returns `None`, so the caller falls back to the scanning
    /// path that establishes the cache and preserves the new-pack rescan semantics.
    fn cached_loaded_pack_listing(&self, pack_dir: &Path) -> Option<Arc<Vec<DiscoveredPack>>> {
        let cache = self.pack_listing.lock().ok()?;
        cache.get(pack_dir).map(Arc::clone)
    }
}

fn validate_object_id_prefix(format: ObjectFormat, prefix: &str) -> Result<()> {
    if prefix.len() < 4 || prefix.len() > format.hex_len() {
        return Err(GitError::InvalidObjectId(format!(
            "expected 4 to {} hex digits for {}, got {}",
            format.hex_len(),
            format.name(),
            prefix.len()
        )));
    }
    if !prefix.bytes().all(|byte| byte.is_ascii_hexdigit()) {
        return Err(GitError::InvalidObjectId(format!(
            "non-hex object id prefix {prefix}"
        )));
    }
    Ok(())
}

fn object_id_matches_prefix(oid: &ObjectId, prefix: &str) -> bool {
    oid.to_hex()
        .as_bytes()
        .iter()
        .zip(prefix.as_bytes())
        .all(|(actual, expected)| actual.eq_ignore_ascii_case(expected))
}

/// Scan `pack_dir` for `.idx` files that have a matching `.pack` sibling,
/// returning the discovered pairs. An `.idx` without its `.pack` is skipped (an
/// orphan index cannot serve objects), matching the prior per-read behavior.
fn scan_pack_listing(pack_dir: &Path) -> Result<Vec<DiscoveredPack>> {
    let mut packs = Vec::new();
    for entry in fs::read_dir(pack_dir)? {
        let entry = entry?;
        let idx = entry.path();
        if idx.extension().and_then(|ext| ext.to_str()) != Some("idx") {
            continue;
        }
        let Some(stem) = idx.file_stem() else {
            continue;
        };
        let pack = idx.with_file_name(format!("{}.pack", stem.to_string_lossy()));
        if !pack.exists() {
            continue;
        }
        packs.push(DiscoveredPack { idx, pack });
    }
    // Deterministic order so lookups and set comparison are stable.
    packs.sort_by(|left, right| left.idx.cmp(&right.idx));
    Ok(packs)
}

/// Whether two pack listings reference the same set of `.idx` files (order is
/// already normalized by [`scan_pack_listing`]).
fn same_pack_set(left: &[DiscoveredPack], right: &[DiscoveredPack]) -> bool {
    left.len() == right.len()
        && left
            .iter()
            .zip(right.iter())
            .all(|(a, b)| a.idx == b.idx && a.pack == b.pack)
}

fn alternate_object_dirs(objects_dir: &Path) -> Vec<PathBuf> {
    let mut alternates = Vec::new();
    if let Some(value) = env::var_os("GIT_ALTERNATE_OBJECT_DIRECTORIES") {
        for raw in value.to_string_lossy().split(':') {
            if !raw.is_empty() {
                alternates.push(PathBuf::from(raw));
            }
        }
    }
    let alternates_path = objects_dir.join("info").join("alternates");
    if let Ok(contents) = fs::read(&alternates_path) {
        for raw in contents.split(|byte| *byte == b'\n') {
            let line = raw.strip_suffix(b"\r").unwrap_or(raw);
            if line.is_empty() || line.starts_with(b"#") {
                continue;
            }
            let Ok(value) = std::str::from_utf8(line) else {
                continue;
            };
            let path = Path::new(value);
            let absolute = if path.is_absolute() {
                path.to_path_buf()
            } else {
                objects_dir.join(path)
            };
            alternates.push(absolute);
        }
    }
    alternates
}

impl ObjectReader for FileObjectDatabase {
    fn is_shallow_graft(&self, oid: &ObjectId) -> bool {
        self.shallow_grafts
            .get_or_init(|| {
                let shallow_file = self
                    .objects_dir
                    .parent()
                    .map(|git_dir| git_dir.join("shallow"));
                match shallow_file {
                    Some(path) => read_shallow_grafts(&path, self.format),
                    None => HashSet::new(),
                }
            })
            .contains(oid)
    }

    fn read_object(&self, oid: &ObjectId) -> Result<Arc<EncodedObject>> {
        if let Some(object) = implied_empty_tree_object(self.format, oid) {
            return Ok(object);
        }
        match self.loose.read_object(oid) {
            Ok(object) => return Ok(object),
            Err(GitError::NotFound(_)) => {}
            Err(err) => return Err(err),
        }
        if let Some(object) = self.read_packed_object(oid)? {
            return Ok(object);
        }
        for alternate in &self.alternates {
            match Self::without_alternates(alternate, self.format).read_object(oid) {
                Ok(object) => return Ok(object),
                Err(GitError::NotFound(_)) => {}
                Err(err) => return Err(err),
            }
        }
        // Hard miss against every store. If an earlier enumeration built a loose
        // cache, an object written loose afterward by a sibling handle could have
        // been skipped above. Mirror git's `oid_object_info_extended`
        // reprepare-on-miss: drop stale cache state and retry an exact loose path
        // probe once before declaring the object missing.
        self.loose.invalidate_cache();
        match self.loose.read_object(oid) {
            Ok(object) => return Ok(object),
            Err(GitError::NotFound(_)) => {}
            Err(err) => return Err(err),
        }
        Err(GitError::object_not_found_in(
            *oid,
            MissingObjectContext::Read,
        ))
    }
}

impl ObjectWriter for FileObjectDatabase {
    fn write_object(&self, object: EncodedObject) -> Result<ObjectId> {
        // Mirror git's freshen semantics (`write_object_file`:
        // `freshen_packed_object || freshen_loose_object`): an object already
        // present anywhere in the database — loose, packed, or through an
        // alternate — is not written again, so e.g. `git add` after
        // `git repack -ad` does not resurrect a loose copy of a packed object.
        let oid = object.object_id(self.format)?;
        if self.contains(&oid)? {
            return Ok(oid);
        }
        self.loose.write_object(object)
    }
}

#[derive(Debug, Clone)]
struct PackPaths {
    pack: PathBuf,
    offset: u64,
}

fn write_pack_component(path: &Path, bytes: &[u8]) -> Result<()> {
    if path.exists() {
        return Ok(());
    }
    let parent = path
        .parent()
        .ok_or_else(|| GitError::InvalidPath("pack component path has no parent".into()))?;
    fs::create_dir_all(parent)?;
    let temp_path = unique_temp_path(parent);
    let write_result = (|| -> Result<()> {
        {
            let mut file = fs::OpenOptions::new()
                .write(true)
                .create_new(true)
                .open(&temp_path)?;
            file.write_all(bytes)?;
            file.sync_all()?;
        }
        match fs::rename(&temp_path, path) {
            Ok(()) => Ok(()),
            Err(_) if path.exists() => {
                let _ = fs::remove_file(&temp_path);
                Ok(())
            }
            Err(err) => Err(GitError::Io(err.to_string())),
        }
    })();
    if write_result.is_err() {
        let _ = fs::remove_file(&temp_path);
    }
    write_result
}

fn write_promisor_pack_sidecar(
    pack_dir: &Path,
    pack_name: &str,
    promisor: bool,
) -> Result<Option<PathBuf>> {
    if !promisor {
        return Ok(None);
    }
    let path = pack_dir.join(format!("{pack_name}.promisor"));
    write_pack_component(&path, b"")?;
    Ok(Some(path))
}

/// Maximum number of bytes git will inflate when reading a loose object's
/// `"<type> <size>\0"` header (git's `MAX_HEADER_LEN` in object-file.c). The NUL
/// terminator must land within this window, so a header of 32 or more non-NUL
/// bytes is rejected as too long.
const MAX_LOOSE_HEADER_LEN: usize = 32;

/// git's exact `error:`-level diagnostic for a loose object whose header overflows
/// `MAX_LOOSE_HEADER_LEN` (object-file.c: `error(_("header for %s too long, exceeds
/// %d bytes"), ...)`). Shared by the header-only and full-read paths so both surface
/// byte-identical text.
fn loose_header_too_long(oid: &ObjectId) -> GitError {
    GitError::InvalidObject(format!(
        "header for {oid} too long, exceeds {MAX_LOOSE_HEADER_LEN} bytes"
    ))
}

/// git's `error:`-level diagnostic when the loose framing header cannot be inflated at
/// all (object-file.c `loose_object_info`, the `ULHR_BAD` arm: `error(_("unable to
/// unpack %s header"), ...)`).
fn loose_unpack_header_failed(oid: &ObjectId) -> GitError {
    GitError::InvalidObject(format!("unable to unpack {oid} header"))
}

/// git-zlib.c's `error("inflate: %s (%s)", ...)` text for an inflate failure whose
/// cause is identifiable from the zlib stream header. The checks mirror zlib's own
/// `inflate()` HEAD-state validation, in order: the FCHECK checksum over CMF+FLG,
/// the compression method, the window size, and the FDICT preset-dictionary bit
/// (zlib reports `Z_NEED_DICT` with a NULL `msg`, which git renders as
/// "(no message)"). Failures past the stream header return `None`: flate2 does not
/// surface zlib's per-case `msg` strings, so no diagnostic is fabricated for them.
fn inflate_header_diagnostic(input: &[u8]) -> Option<&'static str> {
    let [cmf, flg, ..] = *input else { return None };
    if ((u16::from(cmf) << 8) | u16::from(flg)) % 31 != 0 {
        return Some("inflate: data stream error (incorrect header check)");
    }
    if cmf & 0x0f != 8 {
        return Some("inflate: data stream error (unknown compression method)");
    }
    if cmf >> 4 > 7 {
        return Some("inflate: data stream error (invalid window size)");
    }
    if flg & 0x20 != 0 {
        return Some("inflate: needs dictionary (no message)");
    }
    None
}

/// Print the `error: inflate: ...` line git's zlib wrapper emits the moment
/// `inflate()` fails, when the failure is classifiable from the stream header.
fn emit_inflate_diagnostic(input: &[u8]) {
    if let Some(diagnostic) = inflate_header_diagnostic(input) {
        eprintln!("error: {diagnostic}");
    }
}

/// Integrity verdict for a single loose object file, as classified by
/// [`LooseObjectStore::verify_object`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum LooseObjectIntegrity {
    /// Inflated, parsed, and re-hashed to its path-derived oid.
    Ok,
    /// Readable and well-formed, but its content hashes to a different oid
    /// (a loose file stored under the wrong path).
    HashMismatch { actual: ObjectId },
    /// Unreadable: corrupt zlib stream, truncated content, or unparseable header.
    /// The `error:`-level diagnostics were already printed to stderr.
    Corrupt,
}

#[derive(Debug, Clone)]
pub struct LooseObjectStore {
    objects_dir: PathBuf,
    format: ObjectFormat,
    /// Lazily-populated set of loose object ids present on disk, mirroring git's
    /// `loose_objects_cache` (object-file.c). A lookup scans the queried
    /// `objects/XX/` fanout once; afterward misses in that fanout are in-memory
    /// checks instead of failed exact-path opens. Shared across
    /// `FileObjectDatabase` clones via `Arc` so a write through one handle is
    /// visible to reads through another; cleared by `refresh_read_cache` so
    /// objects installed out-of-band (fetch, repack) become visible. Writes
    /// extend the set in place rather than invalidating it.
    loose_cache: Arc<Mutex<LoosePresenceCache>>,
}

impl LooseObjectStore {
    pub fn new(objects_dir: impl Into<PathBuf>, format: ObjectFormat) -> Self {
        Self {
            objects_dir: objects_dir.into(),
            format,
            loose_cache: Arc::new(Mutex::new(LoosePresenceCache::default())),
        }
    }

    /// Whether `oid` is present according to the loose-object cache, populating
    /// the cache on first use. Returns `None` when the lock cannot be trusted or
    /// the scan fails; callers should fall back to an exact filesystem probe in
    /// that case so a cache-building problem cannot change read semantics.
    fn cached_loose_presence(&self, oid: &ObjectId) -> Option<bool> {
        let mut guard = self.loose_cache.lock().ok()?;
        let fanout = oid.as_bytes()[0];
        if !guard.loaded_fanouts.contains(&fanout) {
            collect_loose_fanout_object_ids(
                &self.objects_dir,
                self.format,
                fanout,
                &mut guard.objects,
            )
            .ok()?;
            guard.loaded_fanouts.insert(fanout);
        }
        Some(guard.objects.contains(oid))
    }

    /// Populate the loose-object cache and return the sorted ids. This mirrors
    /// git's `odb_loose_cache` lazy fill and is reserved for operations that
    /// really need loose-object enumeration.
    fn loose_object_ids_cached(&self) -> Result<Vec<ObjectId>> {
        if let Ok(mut guard) = self.loose_cache.lock() {
            guard.objects = loose_object_id_set(&self.objects_dir, self.format)?;
            guard.loaded_fanouts = (0..=u8::MAX).collect();
            let mut ids = guard.objects.iter().copied().collect::<Vec<_>>();
            ids.sort_by(|left, right| left.as_bytes().cmp(right.as_bytes()));
            return Ok(ids);
        }
        loose_object_ids(&self.objects_dir, self.format)
    }

    /// Record `oid` as present in loose storage so subsequent reads find it
    /// without a rescan. A no-op when the cache has not been populated yet (the
    /// eventual lazy scan will pick the object up) or the lock is poisoned.
    fn note_loose_write(&self, oid: ObjectId) {
        if let Ok(mut guard) = self.loose_cache.lock() {
            guard.objects.insert(oid);
        }
    }

    /// Drop the in-memory loose set so the next access rescans the fanout. Called
    /// by `FileObjectDatabase::refresh_read_cache` after out-of-band installs.
    pub(crate) fn invalidate_cache(&self) {
        if let Ok(mut guard) = self.loose_cache.lock() {
            *guard = LoosePresenceCache::default();
        }
    }

    pub fn from_git_dir(git_dir: impl AsRef<Path>, format: ObjectFormat) -> Self {
        Self::new(repository_objects_dir(git_dir), format)
    }

    pub fn object_path(&self, oid: &ObjectId) -> Result<PathBuf> {
        if oid.format() != self.format {
            return Err(GitError::InvalidObjectId(format!(
                "object {oid} uses {}, store uses {}",
                oid.format().name(),
                self.format.name()
            )));
        }
        let hex = oid.to_hex();
        Ok(self.objects_dir.join(&hex[..2]).join(&hex[2..]))
    }

    pub fn exists(&self, oid: &ObjectId) -> Result<bool> {
        let path = self.object_path(oid)?;
        if self.cached_loose_presence(oid) == Some(false) {
            return Ok(false);
        }
        Ok(path.exists())
    }

    pub fn disk_size(&self, oid: &ObjectId) -> Result<Option<u64>> {
        let path = self.object_path(oid)?;
        if self.cached_loose_presence(oid) == Some(false) {
            return Ok(None);
        }
        match fs::metadata(path) {
            Ok(metadata) => Ok(Some(metadata.len())),
            Err(err) if err.kind() == std::io::ErrorKind::NotFound => Ok(None),
            Err(err) => Err(GitError::Io(err.to_string())),
        }
    }

    /// The object type and content size of `oid` from loose storage, inflating only
    /// the framing header (`"<type> <size>\0"`) and not the body. Output-limited
    /// reads keep miniz from inflating past the header even for large objects.
    /// Returns `Ok(None)` when the loose object is absent.
    pub fn read_header(&self, oid: &ObjectId) -> Result<Option<(ObjectType, u64)>> {
        let path = self.object_path(oid)?;
        if self.cached_loose_presence(oid) == Some(false) {
            return Ok(None);
        }
        let mut file = match fs::File::open(&path) {
            Ok(file) => file,
            Err(err) if err.kind() == std::io::ErrorKind::NotFound => return Ok(None),
            Err(err) => return Err(GitError::Io(err.to_string())),
        };
        // Capture the zlib stream's 2-byte header before inflating: when the stream
        // is corrupt, those bytes identify zlib's diagnostic (incorrect header
        // check, needs dictionary, ...) exactly as zlib's `inflate()` would report
        // it through git's wrapper.
        let mut stream_prefix = [0u8; 2];
        let prefix_len = read_full_prefix(&mut file, &mut stream_prefix)?;
        file.seek(SeekFrom::Start(0))
            .map_err(|err| GitError::Io(err.to_string()))?;
        let mut decoder = ZlibDecoder::new(file);
        let mut header = Vec::new();
        let mut byte = [0u8; 1];
        loop {
            // git inflates only the first `MAX_LOOSE_HEADER_LEN` bytes
            // (object-file.c `unpack_loose_header`) and reports ULHR_TOO_LONG when no
            // NUL terminator lands within them — whether the stream simply ends early
            // or overflows the window. Both collapse to the same `error:`-level
            // diagnostic, so a header that ends before its NUL is "too long" too.
            // A stream that won't inflate at all is git's ULHR_BAD instead: the
            // zlib wrapper's `error: inflate: ...` line, then "unable to unpack
            // <oid> header".
            let read = match decoder.read(&mut byte) {
                Ok(read) => read,
                Err(_) => {
                    emit_inflate_diagnostic(&stream_prefix[..prefix_len]);
                    return Err(loose_unpack_header_failed(oid));
                }
            };
            if read == 0 {
                return Err(loose_header_too_long(oid));
            }
            if byte[0] == 0 {
                break;
            }
            header.push(byte[0]);
            // A 31-byte header (NUL at the 32nd byte) is the longest that fits; 32
            // non-NUL bytes overflow the window.
            if header.len() >= MAX_LOOSE_HEADER_LEN {
                return Err(loose_header_too_long(oid));
            }
        }
        let header =
            std::str::from_utf8(&header).map_err(|err| GitError::InvalidObject(err.to_string()))?;
        let (kind, size) = header
            .split_once(' ')
            .ok_or_else(|| GitError::InvalidObject("missing object size".into()))?;
        let object_type = kind.parse::<ObjectType>()?;
        let size = size
            .parse::<u64>()
            .map_err(|_| GitError::InvalidObject("invalid object size".into()))?;
        Ok(Some((object_type, size)))
    }

    /// Loose object ids in this store, sorted by hex.
    pub fn object_ids(&self) -> Result<Vec<ObjectId>> {
        self.loose_object_ids_cached()
    }

    /// fsck's loose-object integrity probe, mirroring C git's `read_loose_object`
    /// (object-file.c) as called from `fsck_loose` (builtin/fsck.c): inflate and
    /// parse the file at `oid`'s loose path, then re-hash its content against the
    /// path-derived oid. `display_path` appears verbatim in the `error:`-level
    /// diagnostics — the path-form messages of `read_loose_object` ("unable to
    /// unpack header of <path>"), unlike the oid-form messages of the normal read
    /// path. Returns `Ok(None)` when no loose file exists for `oid`.
    pub fn verify_object(
        &self,
        oid: &ObjectId,
        display_path: &str,
    ) -> Result<Option<LooseObjectIntegrity>> {
        let path = self.object_path(oid)?;
        let compressed = match fs::read(&path) {
            Ok(compressed) => compressed,
            Err(err) if err.kind() == std::io::ErrorKind::NotFound => return Ok(None),
            Err(err) => return Err(GitError::Io(err.to_string())),
        };
        let mut decoder = ZlibDecoder::new(compressed.as_slice());
        let mut framed = Vec::new();
        if decoder.read_to_end(&mut framed).is_err() {
            emit_inflate_diagnostic(&compressed);
            // No NUL inside the header window means inflation died before the
            // framing header materialized (`unpack_loose_header` != ULHR_OK);
            // with the header intact it is the body that broke
            // (`unpack_loose_rest`).
            if framed_loose_header_terminated(&framed) {
                eprintln!("error: unable to unpack contents of {display_path}");
            } else {
                eprintln!("error: unable to unpack header of {display_path}");
            }
            return Ok(Some(LooseObjectIntegrity::Corrupt));
        }
        if !framed_loose_header_terminated(&framed) {
            // ULHR_TOO_LONG collapses into the same path-form message here: C's
            // `read_loose_object` treats every non-OK `unpack_loose_header` alike.
            eprintln!("error: unable to unpack header of {display_path}");
            return Ok(Some(LooseObjectIntegrity::Corrupt));
        }
        let Ok(object) = parse_framed_object(&framed) else {
            eprintln!("error: unable to parse header of {display_path}");
            return Ok(Some(LooseObjectIntegrity::Corrupt));
        };
        let actual = object.object_id(self.format)?;
        if &actual != oid {
            return Ok(Some(LooseObjectIntegrity::HashMismatch { actual }));
        }
        Ok(Some(LooseObjectIntegrity::Ok))
    }
}

/// Whether the inflated framing bytes contain the header's NUL terminator within
/// git's `MAX_HEADER_LEN` window (object-file.c `unpack_loose_header`'s success
/// condition).
fn framed_loose_header_terminated(framed: &[u8]) -> bool {
    framed
        .iter()
        .take(MAX_LOOSE_HEADER_LEN)
        .any(|byte| *byte == 0)
}

/// Read up to `prefix.len()` bytes from the start of `file`, returning how many
/// were available (short only when the file itself is shorter).
fn read_full_prefix(file: &mut fs::File, prefix: &mut [u8]) -> Result<usize> {
    let mut len = 0;
    while len < prefix.len() {
        let read = file
            .read(&mut prefix[len..])
            .map_err(|err| GitError::Io(err.to_string()))?;
        if read == 0 {
            break;
        }
        len += read;
    }
    Ok(len)
}

impl ObjectReader for LooseObjectStore {
    fn read_object(&self, oid: &ObjectId) -> Result<Arc<EncodedObject>> {
        let path = self.object_path(oid)?;
        // Skip the `open()` (and its ENOENT) when an already-built loose cache
        // knows the id is absent. Without a cache, use an exact path probe; a
        // full fanout scan is far more expensive for one-shot packed-object reads.
        if self.cached_loose_presence(oid) == Some(false) {
            return Err(GitError::object_not_found_in(
                *oid,
                MissingObjectContext::Read,
            ));
        }
        let compressed = match fs::read(&path) {
            Ok(compressed) => compressed,
            Err(err) if err.kind() == std::io::ErrorKind::NotFound => {
                return Err(GitError::object_not_found_in(
                    *oid,
                    MissingObjectContext::Read,
                ));
            }
            Err(err) => return Err(GitError::Io(err.to_string())),
        };
        let mut decoder = ZlibDecoder::new(compressed.as_slice());
        let mut framed = Vec::new();
        if decoder.read_to_end(&mut framed).is_err() {
            emit_inflate_diagnostic(&compressed);
            // A stream that dies before the framing header materializes is git's
            // ULHR_BAD ("unable to unpack <oid> header"); with the header intact,
            // the body is what broke (`unpack_loose_rest`'s "corrupt loose
            // object").
            if !framed_loose_header_terminated(&framed) {
                return Err(loose_unpack_header_failed(oid));
            }
            return Err(GitError::InvalidObject(format!(
                "corrupt loose object '{oid}'"
            )));
        }
        // git only inflates the first `MAX_LOOSE_HEADER_LEN` bytes looking for the
        // header's NUL terminator before parsing the type; an over-long header is
        // rejected here (with git's diagnostic) rather than failing later as an
        // "unknown object type". Mirror that so `cat-file -p` matches upstream.
        if framed
            .iter()
            .take(MAX_LOOSE_HEADER_LEN)
            .all(|byte| *byte != 0)
        {
            return Err(loose_header_too_long(oid));
        }
        let object = parse_framed_object(&framed)?;
        // Trust the loose object's on-disk name rather than re-hashing its full body
        // on every read (see `verify_reads_enabled`); use `validate`/fsck or
        // `SLEY_VERIFY_READS` for an explicit integrity check.
        if verify_reads_enabled() {
            let actual = object.object_id(self.format)?;
            if &actual != oid {
                return Err(GitError::InvalidObject(format!(
                    "loose object {} hashes to {actual}",
                    path.display()
                )));
            }
        }
        Ok(Arc::new(object))
    }
}

impl ObjectWriter for LooseObjectStore {
    fn write_object(&self, object: EncodedObject) -> Result<ObjectId> {
        let oid = object.object_id(self.format)?;
        let path = self.object_path(&oid)?;
        if path.exists() {
            self.note_loose_write(oid);
            return Ok(oid);
        }
        let parent = path
            .parent()
            .ok_or_else(|| GitError::InvalidPath("loose object path has no parent".into()))?;
        fs::create_dir_all(parent)?;
        let temp_path = unique_temp_path(parent);
        let write_result = (|| -> Result<()> {
            let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
            encoder.write_all(&object.framed_bytes())?;
            let compressed = encoder.finish()?;
            {
                let mut file = fs::OpenOptions::new()
                    .write(true)
                    .create_new(true)
                    .open(&temp_path)?;
                file.write_all(&compressed)?;
                // No fsync: git's default `core.fsync=none` fsyncs nothing on the
                // loose-object write path (object-file.c writes the temp file and
                // renames it without syncing unless `core.fsync` names
                // `loose-object`/`objects`/`all`, which it does not by default).
                // A per-object sync_all() here made `git add` of N files cost N
                // fsyncs — the dominant term in sley#27's 10x `add -u` slowdown —
                // for durability git itself does not provide by default. The
                // create_new temp + atomic rename below still guarantees the
                // object never appears half-written under its final name.
            }
            match fs::rename(&temp_path, &path) {
                Ok(()) => Ok(()),
                Err(_) if path.exists() => {
                    let _ = fs::remove_file(&temp_path);
                    Ok(())
                }
                Err(err) => Err(GitError::Io(err.to_string())),
            }
        })();
        if write_result.is_err() {
            let _ = fs::remove_file(&temp_path);
        }
        write_result?;
        self.note_loose_write(oid);
        Ok(oid)
    }
}

fn unique_temp_path(parent: &Path) -> PathBuf {
    let id = TEMPFILE_COUNTER.fetch_add(1, Ordering::Relaxed);
    parent.join(format!("tmp_obj_{}_{}", std::process::id(), id))
}

#[cfg(test)]
mod tests {
    use super::*;
    use sley_core::BString;
    use sley_object::{Commit, EncodedObject, ObjectType, Tag, Tree, TreeEntry};
    use sley_pack::{PackFile, PackWriteOptions};

    fn blob_of(byte: u8, len: usize) -> EncodedObject {
        EncodedObject::new(ObjectType::Blob, vec![byte; len])
    }

    fn cached_blob_of(byte: u8, len: usize) -> Arc<EncodedObject> {
        Arc::new(blob_of(byte, len))
    }

    fn read_object_for_assert(reader: &impl ObjectReader, oid: &ObjectId) -> EncodedObject {
        reader
            .read_object(oid)
            .expect("test operation should succeed")
            .as_ref()
            .clone()
    }

    #[test]
    fn lru_cache_evicts_by_byte_budget_least_recently_used_first() {
        // Budget holds two ~1 KiB objects but not three.
        let one = cached_object_cost(&blob_of(0, 1000));
        let mut cache = LruCache::<u32>::new(one * 2 + 8);
        cache.put(1, cached_blob_of(b'a', 1000));
        cache.put(2, cached_blob_of(b'b', 1000));
        // Touch key 1 so key 2 becomes least-recently-used.
        assert!(cache.get(&1).is_some());
        cache.put(3, cached_blob_of(b'c', 1000));
        // Key 2 (LRU) is evicted; 1 and 3 remain.
        assert!(cache.get(&1).is_some());
        assert!(cache.get(&2).is_none());
        assert!(cache.get(&3).is_some());
    }

    #[test]
    fn lru_cache_zero_budget_is_inert() {
        let mut cache = LruCache::<u32>::new(0);
        cache.put(1, cached_blob_of(b'a', 16));
        assert!(cache.get(&1).is_none());
    }

    #[test]
    fn lru_cache_skips_object_larger_than_budget_and_clears_stale_entry() {
        let mut cache = LruCache::<u32>::new(cached_object_cost(&blob_of(0, 100)));
        cache.put(1, cached_blob_of(b'a', 50));
        assert!(cache.get(&1).is_some());
        // An object that cannot fit is not cached, and it evicts the prior entry
        // stored under the same key (so we never serve a stale value for it).
        cache.put(1, cached_blob_of(b'b', 10_000));
        assert!(cache.get(&1).is_none());
        // A subsequent fitting insert under another key still works and accounting
        // is not corrupted by the oversized insert.
        cache.put(2, cached_blob_of(b'c', 50));
        assert!(cache.get(&2).is_some());
    }

    #[test]
    fn lru_cache_replacing_entry_updates_byte_accounting() {
        // Budget holds two 500-byte objects (plus headroom) but not a 500 + a
        // ~1900-byte object.
        let small = cached_object_cost(&blob_of(0, 500));
        let mut cache = LruCache::<u32>::new(small * 2 + 200);
        cache.put(1, cached_blob_of(b'a', 500));
        cache.put(2, cached_blob_of(b'b', 500));
        assert!(cache.get(&1).is_some());
        assert!(cache.get(&2).is_some());
        // Replace key 2 (now MRU after the gets above re-ordered 1 then 2) with a
        // bigger value that still fits the budget alone but makes the running total
        // exceed it; the LRU (key 1) is evicted while the replaced key 2 stays.
        // This exercises the replace-path accounting.
        cache.put(2, cached_blob_of(b'b', 1000));
        assert!(cache.get(&2).is_some());
        assert!(cache.get(&1).is_none());
    }

    #[test]
    fn write_and_validate_blob() {
        let db = ObjectDatabase::new(ObjectFormat::Sha1);
        let oid = db
            .write_object(EncodedObject::new(ObjectType::Blob, b"hello\n".to_vec()))
            .expect("test operation should succeed");
        assert_eq!(oid.to_hex(), "ce013625030ba8dba906f756967f9e9ca394464a");
        db.validate(&oid).expect("test operation should succeed");
    }

    #[test]
    fn loose_store_writes_and_reads_object() {
        let root = std::env::temp_dir().join(format!(
            "sley-loose-store-{}-{}",
            std::process::id(),
            TEMPFILE_COUNTER.fetch_add(1, Ordering::Relaxed)
        ));
        let store = LooseObjectStore::new(root.join("objects"), ObjectFormat::Sha1);
        let object = EncodedObject::new(ObjectType::Blob, b"hello\n".to_vec());
        let oid = store
            .write_object(object.clone())
            .expect("test operation should succeed");
        assert_eq!(read_object_for_assert(&store, &oid), object);
        assert!(
            store
                .object_path(&oid)
                .expect("test operation should succeed")
                .exists()
        );
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_reads_object_from_pack_index() {
        let root = temp_root("sley-file-odb-pack");
        let git_dir = root.join(".git");
        let pack_dir = git_dir.join("objects").join("pack");
        fs::create_dir_all(&pack_dir).expect("test operation should succeed");
        let object = EncodedObject::new(ObjectType::Blob, b"packed\n".to_vec());
        let oid = object
            .object_id(ObjectFormat::Sha1)
            .expect("test operation should succeed");
        let written = PackFile::write_undeltified_sha1(std::slice::from_ref(&object))
            .expect("test operation should succeed");
        let pack_name = written.checksum.to_hex();
        fs::write(
            pack_dir.join(format!("pack-{pack_name}.pack")),
            written.pack,
        )
        .expect("test operation should succeed");
        fs::write(
            pack_dir.join(format!("pack-{pack_name}.idx")),
            written.index,
        )
        .expect("test operation should succeed");

        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
        assert!(db.contains(&oid).expect("test operation should succeed"));
        assert_eq!(read_object_for_assert(&db, &oid), object);
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_loose_cache_observes_same_process_write_after_miss() {
        let root = temp_root("sley-file-odb-loose-cache-write");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);

        let object = EncodedObject::new(ObjectType::Blob, b"written after miss\n".to_vec());
        let oid = object
            .object_id(ObjectFormat::Sha1)
            .expect("test operation should succeed");

        assert!(matches!(db.read_object(&oid), Err(GitError::NotFound(_))));
        db.loose()
            .write_object(object.clone())
            .expect("test operation should succeed");

        assert_eq!(read_object_for_assert(&db, &oid), object);
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn read_object_header_matches_full_read_for_loose_and_packed_and_delta() {
        let root = temp_root("sley-read-object-header");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let db = FileObjectDatabase::from_git_dir(&git_dir, format);

        // Loose object: the header read inflates only the framing, not the body.
        let loose = EncodedObject::new(ObjectType::Blob, b"loose header object\n".to_vec());
        let loose_oid = db
            .write_object(loose.clone())
            .expect("test operation should succeed");

        // Packed objects, including an ofs-delta whose *result* size lives in the
        // delta stream (not the pack entry header) and whose type is inherited from
        // its base at the end of the chain.
        let base = EncodedObject::new(ObjectType::Blob, vec![b'a'; 4096]);
        let mut child_body = vec![b'a'; 4096];
        child_body.extend_from_slice(b" plus a deltified tail\n");
        let child = EncodedObject::new(ObjectType::Blob, child_body);
        let commitish =
            EncodedObject::new(ObjectType::Commit, b"header-only type probe\n".to_vec());
        let base_oid = base
            .object_id(format)
            .expect("test operation should succeed");
        let child_oid = child
            .object_id(format)
            .expect("test operation should succeed");
        let commit_oid = commitish
            .object_id(format)
            .expect("test operation should succeed");
        let options = PackWriteOptions::new()
            .with_prefer_ofs_delta(true)
            .with_reorder(false);
        let pack = PackFile::write_packed_with_options(
            &[base.clone(), child.clone(), commitish.clone()],
            format,
            &options,
        )
        .expect("test operation should succeed");
        db.install_pack(&pack)
            .expect("test operation should succeed");

        // The header read agrees with a full decode for every object and storage
        // class, without ever materializing the body.
        for (oid, want_type, want_len) in [
            (&loose_oid, ObjectType::Blob, loose.body.len()),
            (&base_oid, ObjectType::Blob, base.body.len()),
            (&child_oid, ObjectType::Blob, child.body.len()),
            (&commit_oid, ObjectType::Commit, commitish.body.len()),
        ] {
            assert_eq!(
                db.read_object_header(oid)
                    .expect("test operation should succeed"),
                Some((want_type, want_len as u64)),
                "header for {oid}"
            );
            let full = db.read_object(oid).expect("test operation should succeed");
            assert_eq!(
                db.read_object_header(oid)
                    .expect("test operation should succeed"),
                Some((full.object_type, full.body.len() as u64))
            );
        }

        let missing = ObjectId::from_hex(format, "0000000000000000000000000000000000000001")
            .expect("test operation should succeed");
        assert_eq!(
            db.read_object_header(&missing)
                .expect("test operation should succeed"),
            None
        );
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn object_storage_info_reports_loose_packed_and_delta_metadata() {
        let root = temp_root("sley-object-storage-info");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let db = FileObjectDatabase::from_git_dir(&git_dir, format);

        let loose = EncodedObject::new(ObjectType::Blob, b"loose storage object\n".to_vec());
        let loose_oid = db
            .write_object(loose)
            .expect("test operation should succeed");
        let loose_size = fs::metadata(
            db.loose()
                .object_path(&loose_oid)
                .expect("test operation should succeed"),
        )
        .expect("test operation should succeed")
        .len();
        let loose_info = db
            .object_storage_info(&loose_oid)
            .expect("test operation should succeed")
            .expect("test operation should succeed");
        assert_eq!(loose_info.disk_size, loose_size);
        assert_eq!(
            loose_info.deltabase,
            zero_oid(format).expect("test operation should succeed")
        );

        let base = EncodedObject::new(ObjectType::Blob, vec![b'a'; 4096]);
        let mut child_body = vec![b'a'; 4096];
        child_body.extend_from_slice(b" changed tail\n");
        let child = EncodedObject::new(ObjectType::Blob, child_body);
        let base_oid = base
            .object_id(format)
            .expect("test operation should succeed");
        let child_oid = child
            .object_id(format)
            .expect("test operation should succeed");
        let options = PackWriteOptions::new()
            .with_prefer_ofs_delta(true)
            .with_reorder(false);
        let pack = PackFile::write_packed_with_options(&[base, child], format, &options)
            .expect("test operation should succeed");
        db.install_pack(&pack)
            .expect("test operation should succeed");

        let base_info = db
            .object_storage_info(&base_oid)
            .expect("test operation should succeed")
            .expect("test operation should succeed");
        assert!(base_info.disk_size > 0);
        assert_eq!(
            base_info.deltabase,
            zero_oid(format).expect("test operation should succeed")
        );

        let child_info = db
            .object_storage_info(&child_oid)
            .expect("test operation should succeed")
            .expect("test operation should succeed");
        assert!(child_info.disk_size > 0);
        assert_eq!(child_info.deltabase, base_oid);

        let missing = ObjectId::from_hex(format, "0000000000000000000000000000000000000001")
            .expect("test operation should succeed");
        assert_eq!(
            db.object_storage_info(&missing)
                .expect("test operation should succeed"),
            None
        );
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_resolves_unique_loose_object_prefix() {
        let root = temp_root("sley-file-odb-prefix-loose");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
        let object = EncodedObject::new(ObjectType::Blob, b"prefix loose\n".to_vec());
        let oid = db
            .write_object(object)
            .expect("test operation should succeed");
        let prefix = &oid.to_hex()[..8];

        assert_eq!(
            db.resolve_prefix(prefix)
                .expect("test operation should succeed"),
            ObjectPrefixResolution::Unique(oid)
        );
        assert!(
            db.object_ids()
                .expect("test operation should succeed")
                .contains(&oid)
        );
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_resolves_unique_packed_object_prefix() {
        let root = temp_root("sley-file-odb-prefix-packed");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
        let object = EncodedObject::new(ObjectType::Blob, b"prefix packed\n".to_vec());
        let oid = object
            .object_id(ObjectFormat::Sha1)
            .expect("test operation should succeed");
        let pack = PackFile::write_undeltified_sha1(std::slice::from_ref(&object))
            .expect("test operation should succeed");
        db.install_pack(&pack)
            .expect("test operation should succeed");
        let prefix = &oid.to_hex()[..8];

        assert_eq!(
            db.resolve_prefix(prefix)
                .expect("test operation should succeed"),
            ObjectPrefixResolution::Unique(oid)
        );
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_reports_ambiguous_object_prefix() {
        let root = temp_root("sley-file-odb-prefix-ambiguous");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
        let mut seen = HashMap::new();
        let (prefix, first, second) = (0..10_000)
            .find_map(|idx| {
                let object =
                    EncodedObject::new(ObjectType::Blob, format!("ambiguous {idx}\n").into_bytes());
                let oid = db
                    .write_object(object)
                    .expect("test operation should succeed");
                let prefix = oid.to_hex()[..4].to_string();
                seen.insert(prefix.clone(), oid)
                    .map(|first| (prefix, first, oid))
            })
            .expect("test should find a 4-hex collision");

        let ObjectPrefixResolution::Ambiguous(mut matches) = db
            .resolve_prefix(&prefix)
            .expect("test operation should succeed")
        else {
            panic!("expected ambiguous prefix {prefix}");
        };
        matches.sort_by_key(ObjectId::to_hex);
        let mut expected = vec![first, second];
        expected.sort_by_key(ObjectId::to_hex);
        assert_eq!(matches, expected);
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_rejects_too_short_object_prefix() {
        let root = temp_root("sley-file-odb-prefix-short");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);

        assert!(matches!(
            db.resolve_prefix("abc"),
            Err(GitError::InvalidObjectId(_))
        ));
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_reads_sha256_object_from_pack_index() {
        let root = temp_root("sley-file-odb-pack-sha256");
        let git_dir = root.join(".git");
        let pack_dir = git_dir.join("objects").join("pack");
        fs::create_dir_all(&pack_dir).expect("test operation should succeed");
        let object = EncodedObject::new(ObjectType::Blob, b"packed sha256\n".to_vec());
        let oid = object
            .object_id(ObjectFormat::Sha256)
            .expect("test operation should succeed");
        let written =
            PackFile::write_undeltified(std::slice::from_ref(&object), ObjectFormat::Sha256)
                .expect("test operation should succeed");
        let pack_name = written.checksum.to_hex();
        fs::write(
            pack_dir.join(format!("pack-{pack_name}.pack")),
            written.pack,
        )
        .expect("test operation should succeed");
        fs::write(
            pack_dir.join(format!("pack-{pack_name}.idx")),
            written.index,
        )
        .expect("test operation should succeed");

        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha256);
        assert!(db.contains(&oid).expect("test operation should succeed"));
        assert_eq!(read_object_for_assert(&db, &oid), object);
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_installs_sha256_pack_without_loose_objects() {
        let root = temp_root("sley-file-odb-install-pack");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let object = EncodedObject::new(ObjectType::Blob, b"installed sha256 pack\n".to_vec());
        let oid = object
            .object_id(ObjectFormat::Sha256)
            .expect("test operation should succeed");
        let pack = PackFile::write_undeltified(std::slice::from_ref(&object), ObjectFormat::Sha256)
            .expect("test operation should succeed");
        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha256);

        let result = db
            .install_pack(&pack)
            .expect("test operation should succeed");

        assert_eq!(result.pack_name, format!("pack-{}", pack.checksum.to_hex()));
        assert_eq!(result.object_ids, vec![oid]);
        assert!(result.pack_path.exists());
        assert!(result.index_path.exists());
        assert_eq!(result.promisor_path, None);
        assert!(
            !db.loose()
                .object_path(&oid)
                .expect("test operation should succeed")
                .exists()
        );
        assert!(db.contains(&oid).expect("test operation should succeed"));
        assert_eq!(read_object_for_assert(&db, &oid), object);
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_installs_raw_sha256_pack_without_loose_objects() {
        let root = temp_root("sley-file-odb-install-raw-pack");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let object = EncodedObject::new(ObjectType::Blob, b"installed raw sha256 pack\n".to_vec());
        let oid = object
            .object_id(ObjectFormat::Sha256)
            .expect("test operation should succeed");
        let pack = PackFile::write_undeltified(std::slice::from_ref(&object), ObjectFormat::Sha256)
            .expect("test operation should succeed");
        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha256);

        let result = db
            .install_raw_pack(&pack.pack)
            .expect("test operation should succeed");

        assert_eq!(result.pack_name, format!("pack-{}", pack.checksum.to_hex()));
        assert_eq!(result.object_ids, vec![oid]);
        assert!(result.pack_path.exists());
        assert!(result.index_path.exists());
        assert_eq!(result.promisor_path, None);
        assert!(
            !db.loose()
                .object_path(&oid)
                .expect("test operation should succeed")
                .exists()
        );
        assert!(db.contains(&oid).expect("test operation should succeed"));
        assert_eq!(read_object_for_assert(&db, &oid), object);
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_rejects_noncanonical_pack_index() {
        let root = temp_root("sley-file-odb-install-bad-index");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let object = EncodedObject::new(ObjectType::Blob, b"bad index crc\n".to_vec());
        let pack = PackFile::write_undeltified(std::slice::from_ref(&object), ObjectFormat::Sha1)
            .expect("test operation should succeed");
        let mut entries = pack.entries.clone();
        entries[0].crc32 ^= 1;
        let mut bad_pack = pack.clone();
        bad_pack.index = PackIndex::write_v2(ObjectFormat::Sha1, &entries, &pack.checksum)
            .expect("test operation should succeed");
        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);

        assert!(db.install_pack(&bad_pack).is_err());

        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_installs_raw_promisor_pack_with_sidecar() {
        let root = temp_root("sley-file-odb-install-raw-promisor-pack");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let object = EncodedObject::new(ObjectType::Blob, b"installed promisor pack\n".to_vec());
        let oid = object
            .object_id(ObjectFormat::Sha1)
            .expect("test operation should succeed");
        let pack = PackFile::write_undeltified(std::slice::from_ref(&object), ObjectFormat::Sha1)
            .expect("test operation should succeed");
        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);

        let result = db
            .install_raw_pack_with_options(&pack.pack, RawPackInstallOptions { promisor: true })
            .expect("test operation should succeed");

        let promisor_path = result.promisor_path.expect("promisor sidecar");
        assert_eq!(promisor_path.file_stem(), result.pack_path.file_stem());
        assert_eq!(
            promisor_path.extension().and_then(|ext| ext.to_str()),
            Some("promisor")
        );
        assert!(promisor_path.exists());
        assert_eq!(
            fs::read(&promisor_path).expect("test operation should succeed"),
            b""
        );
        assert!(result.pack_path.exists());
        assert!(result.index_path.exists());
        assert!(
            !db.loose()
                .object_path(&oid)
                .expect("test operation should succeed")
                .exists()
        );
        assert_eq!(read_object_for_assert(&db, &oid), object);
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn repository_objects_dir_uses_linked_worktree_common_dir() {
        let root = temp_root("sley-odb-common-dir");
        let common = root.join(".git");
        let admin = common.join("worktrees").join("linked");
        fs::create_dir_all(&admin).expect("test operation should succeed");
        fs::write(admin.join("commondir"), "../..\n").expect("test operation should succeed");

        let common = fs::canonicalize(common).expect("test operation should succeed");
        assert_eq!(repository_common_dir(&admin), common);
        assert_eq!(repository_objects_dir(&admin), common.join("objects"));

        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn reachable_object_helpers_walk_graph_and_install_pack() {
        let root = temp_root("sley-reachable-pack");
        let source_git_dir = root.join("source.git");
        let destination_git_dir = root.join("destination.git");
        fs::create_dir_all(source_git_dir.join("objects")).expect("test operation should succeed");
        fs::create_dir_all(destination_git_dir.join("objects"))
            .expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let source = FileObjectDatabase::from_git_dir(&source_git_dir, format);
        let destination = FileObjectDatabase::from_git_dir(&destination_git_dir, format);

        let blob = EncodedObject::new(ObjectType::Blob, b"reachable payload\n".to_vec());
        let blob_oid = source
            .write_object(blob.clone())
            .expect("test operation should succeed");
        let tree = EncodedObject::new(
            ObjectType::Tree,
            Tree {
                entries: vec![TreeEntry {
                    mode: 0o100644,
                    name: BString::from(b"payload.txt"),
                    oid: blob_oid,
                }],
            }
            .write(),
        );
        let tree_oid = source
            .write_object(tree.clone())
            .expect("test operation should succeed");
        let identity = b"Example <example@example.invalid> 0 +0000".to_vec();
        let commit = EncodedObject::new(
            ObjectType::Commit,
            Commit {
                tree: tree_oid,
                parents: Vec::new(),
                author: identity.clone(),
                committer: identity,
                encoding: None,
                message: b"initial\n".to_vec(),
            }
            .write(),
        );
        let commit_oid = source
            .write_object(commit.clone())
            .expect("test operation should succeed");

        let reachable = collect_reachable_object_ids(&source, format, std::iter::once(commit_oid))
            .expect("test operation should succeed");
        assert!(reachable.contains(&commit_oid));
        assert!(reachable.contains(&tree_oid));
        assert!(reachable.contains(&blob_oid));

        let install =
            install_reachable_pack(&source, &destination, format, std::iter::once(commit_oid))
                .expect("test operation should succeed")
                .expect("reachable pack should be written");
        assert_eq!(install.object_ids.len(), 3);
        for (oid, object) in [
            (&commit_oid, &commit),
            (&tree_oid, &tree),
            (&blob_oid, &blob),
        ] {
            assert!(
                !destination
                    .loose()
                    .object_path(oid)
                    .expect("test operation should succeed")
                    .exists()
            );
            assert!(
                destination
                    .contains(oid)
                    .expect("test operation should succeed")
            );
            assert_eq!(read_object_for_assert(&destination, oid), *object);
        }
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn reachable_object_helpers_respect_exclusions_and_duplicate_starts() {
        let root = temp_root("sley-reachable-exclusions");
        let git_dir = root.join("repo.git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let db = FileObjectDatabase::from_git_dir(&git_dir, format);

        let blob = EncodedObject::new(ObjectType::Blob, b"excluded payload\n".to_vec());
        let blob_oid = db
            .write_object(blob)
            .expect("test operation should succeed");
        let tree = EncodedObject::new(
            ObjectType::Tree,
            Tree {
                entries: vec![TreeEntry {
                    mode: 0o100644,
                    name: BString::from(b"payload.txt"),
                    oid: blob_oid,
                }],
            }
            .write(),
        );
        let tree_oid = db
            .write_object(tree)
            .expect("test operation should succeed");
        let identity = b"Example <example@example.invalid> 0 +0000".to_vec();
        let commit = EncodedObject::new(
            ObjectType::Commit,
            Commit {
                tree: tree_oid,
                parents: Vec::new(),
                author: identity.clone(),
                committer: identity,
                encoding: None,
                message: b"initial\n".to_vec(),
            }
            .write(),
        );
        let commit_oid = db
            .write_object(commit)
            .expect("test operation should succeed");
        let excluded = HashSet::from([tree_oid]);

        let objects = collect_reachable_objects(&db, format, [commit_oid, commit_oid], &excluded)
            .expect("test operation should succeed");

        assert_eq!(objects.len(), 1);
        assert_eq!(
            objects[0]
                .object_id(format)
                .expect("test operation should succeed"),
            commit_oid
        );
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn build_reachable_pack_returns_raw_pack_and_respects_empty_exclusions() {
        let root = temp_root("sley-build-reachable-pack");
        let git_dir = root.join("repo.git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let db = FileObjectDatabase::from_git_dir(&git_dir, format);

        let object = EncodedObject::new(ObjectType::Blob, b"raw reachable pack\n".to_vec());
        let oid = db
            .write_object(object.clone())
            .expect("test operation should succeed");
        let pack = build_reachable_pack(&db, format, std::iter::once(oid), &HashSet::new())
            .expect("test operation should succeed")
            .expect("reachable pack should be built");
        assert!(pack.pack.starts_with(b"PACK"));
        assert_eq!(pack.entries.len(), 1);
        assert_eq!(pack.entries[0].oid, oid);

        let excluded = HashSet::from([oid]);
        assert!(
            build_reachable_pack(
                &db,
                format,
                pack.entries.into_iter().map(|entry| entry.oid),
                &excluded
            )
            .expect("test operation should succeed")
            .is_none()
        );
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn reachable_object_helpers_follow_tags_and_report_missing_objects() {
        let root = temp_root("sley-reachable-tags");
        let git_dir = root.join("repo.git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let db = FileObjectDatabase::from_git_dir(&git_dir, format);

        let blob = EncodedObject::new(ObjectType::Blob, b"tagged payload\n".to_vec());
        let blob_oid = db
            .write_object(blob)
            .expect("test operation should succeed");
        let tag = EncodedObject::new(
            ObjectType::Tag,
            Tag {
                object: blob_oid,
                object_type: ObjectType::Blob,
                name: b"v1".to_vec(),
                tagger: Some(b"Example <example@example.invalid> 0 +0000".to_vec()),
                message: b"tag message\n".to_vec(),
                raw_body: None,
            }
            .write(),
        );
        let tag_oid = db.write_object(tag).expect("test operation should succeed");

        let reachable = collect_reachable_object_ids(&db, format, std::iter::once(tag_oid))
            .expect("test operation should succeed");
        assert!(reachable.contains(&tag_oid));
        assert!(reachable.contains(&blob_oid));

        let missing = ObjectId::from_hex(format, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
            .expect("test operation should succeed");
        let err = collect_reachable_object_ids(&db, format, std::iter::once(missing))
            .expect_err("missing traversal root should error");
        let kind = err.not_found_kind().expect("typed not found");
        assert_eq!(kind.object_id(), Some(missing));
        assert_eq!(
            kind.missing_object_context(),
            Some(MissingObjectContext::Traversal)
        );
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn install_reachable_pack_empty_starts_create_no_pack() {
        let root = temp_root("sley-reachable-empty");
        let source_git_dir = root.join("source.git");
        let destination_git_dir = root.join("destination.git");
        fs::create_dir_all(source_git_dir.join("objects")).expect("test operation should succeed");
        fs::create_dir_all(destination_git_dir.join("objects"))
            .expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let source = FileObjectDatabase::from_git_dir(&source_git_dir, format);
        let destination = FileObjectDatabase::from_git_dir(&destination_git_dir, format);

        let result = install_reachable_pack(&source, &destination, format, Vec::<ObjectId>::new())
            .expect("test operation should succeed");

        assert!(result.is_none());
        assert!(!destination_git_dir.join("objects").join("pack").exists());
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn install_reachable_pack_excluding_skips_fully_excluded_starts() {
        let root = temp_root("sley-reachable-install-excluding");
        let source_git_dir = root.join("source.git");
        let destination_git_dir = root.join("destination.git");
        fs::create_dir_all(source_git_dir.join("objects")).expect("test operation should succeed");
        fs::create_dir_all(destination_git_dir.join("objects"))
            .expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let source = FileObjectDatabase::from_git_dir(&source_git_dir, format);
        let destination = FileObjectDatabase::from_git_dir(&destination_git_dir, format);
        let object = EncodedObject::new(ObjectType::Blob, b"excluded install\n".to_vec());
        let oid = source
            .write_object(object)
            .expect("test operation should succeed");
        let excluded = HashSet::from([oid]);

        let result = install_reachable_pack_excluding(
            &source,
            &destination,
            format,
            std::iter::once(oid),
            &excluded,
        )
        .expect("test operation should succeed");

        assert!(result.is_none());
        assert!(!destination_git_dir.join("objects").join("pack").exists());
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn install_reachable_pack_supports_sha256() {
        let root = temp_root("sley-reachable-pack-sha256");
        let source_git_dir = root.join("source.git");
        let destination_git_dir = root.join("destination.git");
        fs::create_dir_all(source_git_dir.join("objects")).expect("test operation should succeed");
        fs::create_dir_all(destination_git_dir.join("objects"))
            .expect("test operation should succeed");
        let format = ObjectFormat::Sha256;
        let source = FileObjectDatabase::from_git_dir(&source_git_dir, format);
        let destination = FileObjectDatabase::from_git_dir(&destination_git_dir, format);
        let object = EncodedObject::new(ObjectType::Blob, b"sha256 reachable pack\n".to_vec());
        let oid = source
            .write_object(object.clone())
            .expect("test operation should succeed");

        let pack = build_reachable_pack(&source, format, std::iter::once(oid), &HashSet::new())
            .expect("test operation should succeed")
            .expect("sha256 reachable pack should be built");
        assert!(pack.pack.starts_with(b"PACK"));
        assert_eq!(pack.entries[0].oid, oid);

        let result = install_reachable_pack(&source, &destination, format, std::iter::once(oid))
            .expect("test operation should succeed")
            .expect("sha256 reachable pack should be written");

        assert_eq!(result.object_ids, vec![oid]);
        assert!(
            !destination
                .loose()
                .object_path(&oid)
                .expect("test operation should succeed")
                .exists()
        );
        assert_eq!(read_object_for_assert(&destination, &oid), object);
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn install_helpers_accept_custom_raw_pack_installer() {
        #[derive(Default)]
        struct RecordingInstaller {
            packs: std::cell::RefCell<Vec<Vec<u8>>>,
            installed: std::cell::RefCell<Vec<ObjectId>>,
        }

        impl RawPackInstaller for RecordingInstaller {
            fn install_raw_pack(&self, pack_bytes: &[u8]) -> Result<RawPackInstallResult> {
                self.packs.borrow_mut().push(pack_bytes.to_vec());
                let object_ids = self.installed.borrow().clone();
                Ok(RawPackInstallResult { object_ids })
            }
        }

        let format = ObjectFormat::Sha1;
        let source = ObjectDatabase::new(format);
        let object = EncodedObject::new(ObjectType::Blob, b"custom raw installer\n".to_vec());
        let oid = source
            .write_object(object)
            .expect("test operation should succeed");
        let installer = RecordingInstaller::default();
        installer.installed.borrow_mut().push(oid);

        let result = install_reachable_pack(&source, &installer, format, std::iter::once(oid))
            .expect("test operation should succeed")
            .expect("custom installer should receive pack");

        assert_eq!(result.object_ids, installer.installed.into_inner());
        let packs = installer.packs.into_inner();
        assert_eq!(packs.len(), 1);
        assert!(packs[0].starts_with(b"PACK"));
    }

    #[test]
    fn file_database_reads_object_from_multi_pack_index() {
        let root = temp_root("sley-file-odb-midx");
        let git_dir = root.join(".git");
        let pack_dir = git_dir.join("objects").join("pack");
        fs::create_dir_all(&pack_dir).expect("test operation should succeed");
        let first = EncodedObject::new(ObjectType::Blob, b"first packed\n".to_vec());
        let second = EncodedObject::new(ObjectType::Blob, b"second packed\n".to_vec());
        let first_oid = first
            .object_id(ObjectFormat::Sha1)
            .expect("test operation should succeed");
        let second_oid = second
            .object_id(ObjectFormat::Sha1)
            .expect("test operation should succeed");
        let first_pack = PackFile::write_undeltified_sha1(std::slice::from_ref(&first))
            .expect("test operation should succeed");
        let second_pack = PackFile::write_undeltified_sha1(std::slice::from_ref(&second))
            .expect("test operation should succeed");
        let first_pack_name = format!("pack-{}.idx", first_pack.checksum.to_hex());
        let second_pack_name = format!("pack-{}.idx", second_pack.checksum.to_hex());
        fs::write(
            pack_dir.join(first_pack_name.replace(".idx", ".pack")),
            first_pack.pack,
        )
        .expect("test operation should succeed");
        fs::write(
            pack_dir.join(second_pack_name.replace(".idx", ".pack")),
            second_pack.pack,
        )
        .expect("test operation should succeed");
        let midx = MultiPackIndex::write(
            ObjectFormat::Sha1,
            2,
            &[first_pack_name, second_pack_name],
            &[
                sley_pack::MultiPackIndexEntry {
                    oid: first_oid,
                    pack_int_id: 0,
                    offset: first_pack.entries[0].offset,
                },
                sley_pack::MultiPackIndexEntry {
                    oid: second_oid,
                    pack_int_id: 1,
                    offset: second_pack.entries[0].offset,
                },
            ],
        )
        .expect("test operation should succeed");
        fs::write(pack_dir.join("multi-pack-index"), midx).expect("test operation should succeed");

        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
        assert!(
            db.contains(&second_oid)
                .expect("test operation should succeed")
        );
        assert_eq!(
            db.resolve_prefix(&second_oid.to_hex()[..8])
                .expect("test operation should succeed"),
            ObjectPrefixResolution::Unique(second_oid)
        );
        assert_eq!(read_object_for_assert(&db, &second_oid), second);
        assert_eq!(read_object_for_assert(&db, &first_oid), first);
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_finds_pack_added_after_listing_was_cached() {
        // Regression guard for the cached pack-directory listing: a pack written
        // after the listing was first cached (via a prior read) must still be
        // discovered by the same handle, because a miss triggers a re-scan.
        let root = temp_root("sley-file-odb-pack-added-late");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);

        // First pack + object; reading it populates the listing cache.
        let first = EncodedObject::new(ObjectType::Blob, b"first late\n".to_vec());
        let first_oid = first
            .object_id(ObjectFormat::Sha1)
            .expect("test operation should succeed");
        let first_pack = PackFile::write_undeltified_sha1(std::slice::from_ref(&first))
            .expect("test operation should succeed");
        db.install_pack(&first_pack)
            .expect("test operation should succeed");
        assert_eq!(read_object_for_assert(&db, &first_oid), first);

        // A second object that the cached listing does not yet know about.
        let second = EncodedObject::new(ObjectType::Blob, b"second late\n".to_vec());
        let second_oid = second
            .object_id(ObjectFormat::Sha1)
            .expect("test operation should succeed");
        // It is genuinely absent right now.
        assert!(matches!(
            db.read_object(&second_oid),
            Err(GitError::NotFound(_))
        ));

        // Install its pack through the same handle; the next read must find it via
        // a re-scan, not be masked by the stale listing.
        let second_pack = PackFile::write_undeltified_sha1(std::slice::from_ref(&second))
            .expect("test operation should succeed");
        db.install_pack(&second_pack)
            .expect("test operation should succeed");
        assert!(
            db.contains(&second_oid)
                .expect("test operation should succeed")
        );
        assert_eq!(read_object_for_assert(&db, &second_oid), second);
        // The original object still resolves too.
        assert_eq!(read_object_for_assert(&db, &first_oid), first);

        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn file_database_prefers_loose_object_over_packed_object() {
        let root = temp_root("sley-file-odb-prefer-loose");
        let git_dir = root.join(".git");
        let pack_dir = git_dir.join("objects").join("pack");
        fs::create_dir_all(&pack_dir).expect("test operation should succeed");
        let object = EncodedObject::new(ObjectType::Blob, b"same\n".to_vec());
        let written = PackFile::write_undeltified_sha1(std::slice::from_ref(&object))
            .expect("test operation should succeed");
        let pack_name = written.checksum.to_hex();
        fs::write(
            pack_dir.join(format!("pack-{pack_name}.pack")),
            written.pack,
        )
        .expect("test operation should succeed");
        fs::write(
            pack_dir.join(format!("pack-{pack_name}.idx")),
            written.index,
        )
        .expect("test operation should succeed");

        let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
        let oid = db
            .write_object(object.clone())
            .expect("test operation should succeed");
        assert_eq!(read_object_for_assert(&db, &oid), object);
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn bundle_prerequisite_verification_reads_existing_objects() {
        let db = ObjectDatabase::new(ObjectFormat::Sha1);
        let oid = db
            .write_object(EncodedObject::new(ObjectType::Blob, b"base\n".to_vec()))
            .expect("test operation should succeed");
        let bundle_bytes = format!("# v2 git bundle\n-{oid} base\n\n").into_bytes();
        let bundle = Bundle::parse(&bundle_bytes, ObjectFormat::Sha1)
            .expect("test operation should succeed");

        verify_bundle_prerequisites(&bundle, &db).expect("test operation should succeed");
    }

    #[test]
    fn bundle_prerequisite_verification_reports_missing_objects() {
        let db = ObjectDatabase::new(ObjectFormat::Sha1);
        let missing = sley_core::object_id_for_bytes(ObjectFormat::Sha1, "blob", b"missing\n")
            .expect("test operation should succeed");
        let bundle_bytes = format!("# v2 git bundle\n-{missing} missing\n\n").into_bytes();
        let bundle = Bundle::parse(&bundle_bytes, ObjectFormat::Sha1)
            .expect("test operation should succeed");

        assert!(verify_bundle_prerequisites(&bundle, &db).is_err());
    }

    #[test]
    fn unbundle_objects_writes_pack_entries_and_returns_refs() {
        let prerequisite_reader = ObjectDatabase::new(ObjectFormat::Sha1);
        let mut writer = ObjectDatabase::new(ObjectFormat::Sha1);
        let object = EncodedObject::new(ObjectType::Blob, b"bundle object\n".to_vec());
        let oid = object
            .object_id(ObjectFormat::Sha1)
            .expect("test operation should succeed");
        let pack = PackFile::write_undeltified_sha1(std::slice::from_ref(&object))
            .expect("test operation should succeed");
        let bundle_bytes = format!("# v2 git bundle\n{oid} refs/heads/main\n\n")
            .into_bytes()
            .into_iter()
            .chain(pack.pack)
            .collect::<Vec<_>>();
        let bundle = Bundle::parse(&bundle_bytes, ObjectFormat::Sha1)
            .expect("test operation should succeed");

        let result = unbundle_objects(&bundle, &prerequisite_reader, &mut writer)
            .expect("test operation should succeed");
        assert_eq!(result.written_objects, vec![oid]);
        assert_eq!(result.references, bundle.references);
        assert_eq!(read_object_for_assert(&writer, &oid), object);
    }

    #[test]
    fn install_bundle_pack_writes_pack_and_returns_refs() {
        let root = temp_root("sley-install-bundle-pack");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let prerequisite_reader = ObjectDatabase::new(ObjectFormat::Sha1);
        let database = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
        let object = EncodedObject::new(ObjectType::Blob, b"bundle pack object\n".to_vec());
        let oid = object
            .object_id(ObjectFormat::Sha1)
            .expect("test operation should succeed");
        let pack = PackFile::write_undeltified_sha1(std::slice::from_ref(&object))
            .expect("test operation should succeed");
        let bundle_bytes = format!("# v2 git bundle\n{oid} refs/heads/main\n\n")
            .into_bytes()
            .into_iter()
            .chain(pack.pack)
            .collect::<Vec<_>>();
        let bundle = Bundle::parse(&bundle_bytes, ObjectFormat::Sha1)
            .expect("test operation should succeed");

        let result = install_bundle_pack(&bundle, &prerequisite_reader, &database)
            .expect("test operation should succeed");

        assert_eq!(result.written_objects, vec![oid]);
        assert_eq!(result.references, bundle.references);
        assert!(
            database
                .contains(&oid)
                .expect("test operation should succeed")
        );
        assert_eq!(read_object_for_assert(&database, &oid), object);
        assert!(
            !database
                .loose()
                .object_path(&oid)
                .expect("test operation should succeed")
                .exists()
        );
        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn unpack_packfile_objects_writes_sha256_pack_entries() {
        let writer = ObjectDatabase::new(ObjectFormat::Sha256);
        let object = EncodedObject::new(ObjectType::Blob, b"transport pack object\n".to_vec());
        let oid = object
            .object_id(ObjectFormat::Sha256)
            .expect("test operation should succeed");
        let pack = PackFile::write_undeltified(std::slice::from_ref(&object), ObjectFormat::Sha256)
            .expect("test operation should succeed");

        let result = unpack_packfile_objects(&pack.pack, ObjectFormat::Sha256, &writer)
            .expect("test operation should succeed");

        assert_eq!(result.written_objects, vec![oid]);
        assert_eq!(read_object_for_assert(&writer, &oid), object);
    }

    #[test]
    fn unbundle_objects_rejects_missing_prerequisites_before_writing() {
        let prerequisite_reader = ObjectDatabase::new(ObjectFormat::Sha1);
        let mut writer = ObjectDatabase::new(ObjectFormat::Sha1);
        let missing = sley_core::object_id_for_bytes(ObjectFormat::Sha1, "blob", b"missing\n")
            .expect("test operation should succeed");
        let object = EncodedObject::new(ObjectType::Blob, b"bundle object\n".to_vec());
        let oid = object
            .object_id(ObjectFormat::Sha1)
            .expect("test operation should succeed");
        let pack = PackFile::write_undeltified_sha1(std::slice::from_ref(&object))
            .expect("test operation should succeed");
        let bundle_bytes =
            format!("# v2 git bundle\n-{missing} missing\n{oid} refs/heads/main\n\n")
                .into_bytes()
                .into_iter()
                .chain(pack.pack)
                .collect::<Vec<_>>();
        let bundle = Bundle::parse(&bundle_bytes, ObjectFormat::Sha1)
            .expect("test operation should succeed");

        assert!(unbundle_objects(&bundle, &prerequisite_reader, &mut writer).is_err());
        assert!(!writer.contains(&oid));
    }

    /// Build a commit -> tree -> blob graph in `db`, returning the three object
    /// ids and their canonical encodings as `(oid, object)` pairs.
    fn write_commit_graph(
        db: &mut FileObjectDatabase,
        payload: &[u8],
    ) -> Vec<(ObjectId, EncodedObject)> {
        let blob = EncodedObject::new(ObjectType::Blob, payload.to_vec());
        let blob_oid = db
            .write_object(blob.clone())
            .expect("test operation should succeed");
        let tree = EncodedObject::new(
            ObjectType::Tree,
            Tree {
                entries: vec![TreeEntry {
                    mode: 0o100644,
                    name: BString::from(b"payload.txt"),
                    oid: blob_oid,
                }],
            }
            .write(),
        );
        let tree_oid = db
            .write_object(tree.clone())
            .expect("test operation should succeed");
        let identity = b"Example <example@example.invalid> 0 +0000".to_vec();
        let commit = EncodedObject::new(
            ObjectType::Commit,
            Commit {
                tree: tree_oid,
                parents: Vec::new(),
                author: identity.clone(),
                committer: identity,
                encoding: None,
                message: b"initial\n".to_vec(),
            }
            .write(),
        );
        let commit_oid = db
            .write_object(commit.clone())
            .expect("test operation should succeed");
        vec![(commit_oid, commit), (tree_oid, tree), (blob_oid, blob)]
    }

    fn repack_all_objects_consolidates_loose_and_pack(format: ObjectFormat) {
        let root = temp_root("sley-repack-all");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let mut db = FileObjectDatabase::from_git_dir(&git_dir, format);

        // A pre-existing pack holds one blob; the rest of the graph is loose.
        let packed_blob = EncodedObject::new(ObjectType::Blob, b"already packed\n".to_vec());
        let packed_oid = packed_blob
            .object_id(format)
            .expect("test operation should succeed");
        let existing_pack = PackFile::write_undeltified(std::slice::from_ref(&packed_blob), format)
            .expect("test operation should succeed");
        let existing = db
            .install_pack(&existing_pack)
            .expect("test operation should succeed");

        let graph = write_commit_graph(&mut db, b"repack payload\n");

        let mut expected: HashMap<ObjectId, EncodedObject> = graph.iter().cloned().collect();
        expected.insert(packed_oid, packed_blob.clone());

        let result = repack_all_objects(&git_dir, format)
            .expect("test operation should succeed")
            .expect("repository has objects");

        // The new pack round-trips and contains every original object byte-for-byte.
        assert_eq!(result.object_count, expected.len());
        let parsed = PackFile::parse(&result.pack, format).expect("test operation should succeed");
        assert_eq!(parsed.entries.len(), expected.len());
        for entry in &parsed.entries {
            let want = expected
                .get(&entry.entry.oid)
                .expect("packed object was in the repository");
            assert_eq!(&entry.object, want);
            assert_eq!(
                entry
                    .object
                    .object_id(format)
                    .expect("test operation should succeed"),
                entry.entry.oid
            );
        }
        // The generated index parses and agrees with the pack checksum.
        let idx = PackIndex::parse(&result.idx, format).expect("test operation should succeed");
        assert_eq!(idx.pack_checksum, parsed.checksum);
        assert_eq!(idx.entries.len(), expected.len());

        // The pre-existing pack is reported obsolete (by its .pack path).
        assert_eq!(result.obsolete_packs, vec![existing.pack_path.clone()]);
        // Every loose object id is reported as now packed.
        let mut want_loose: Vec<ObjectId> = graph.iter().map(|(oid, _)| *oid).collect();
        want_loose.sort_by_key(ObjectId::to_hex);
        assert_eq!(result.packed_loose, want_loose);
        assert!(!result.packed_loose.contains(&packed_oid));

        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn repack_all_objects_consolidates_loose_and_pack_sha1() {
        repack_all_objects_consolidates_loose_and_pack(ObjectFormat::Sha1);
    }

    #[test]
    fn repack_all_objects_consolidates_loose_and_pack_sha256() {
        repack_all_objects_consolidates_loose_and_pack(ObjectFormat::Sha256);
    }

    #[test]
    fn repack_all_objects_returns_none_for_empty_repository() {
        let root = temp_root("sley-repack-empty");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");

        assert!(
            repack_all_objects(&git_dir, ObjectFormat::Sha1)
                .expect("test operation should succeed")
                .is_none()
        );

        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn install_repack_result_writes_pack_without_pruning_by_default() {
        let root = temp_root("sley-repack-install-nodelete");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let mut db = FileObjectDatabase::from_git_dir(&git_dir, format);
        let graph = write_commit_graph(&mut db, b"install no prune\n");

        let result = repack_all_objects(&git_dir, format)
            .expect("test operation should succeed")
            .expect("test operation should succeed");
        install_repack_result(&git_dir, format, &result, false)
            .expect("test operation should succeed");

        // New pack is on disk and readable.
        let parsed = PackFile::parse(&result.pack, format).expect("test operation should succeed");
        let pack_dir = git_dir.join("objects").join("pack");
        let pack_path = pack_dir.join(format!("pack-{}.pack", parsed.checksum.to_hex()));
        let idx_path = pack_dir.join(format!("pack-{}.idx", parsed.checksum.to_hex()));
        assert!(pack_path.exists());
        assert!(idx_path.exists());
        // Loose objects survive because prune was not requested.
        for (oid, object) in &graph {
            assert!(
                db.loose()
                    .object_path(oid)
                    .expect("test operation should succeed")
                    .exists()
            );
            assert_eq!(read_object_for_assert(&db, oid), *object);
        }

        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn install_repack_result_prunes_obsolete_packs_and_loose_objects() {
        let root = temp_root("sley-repack-install-prune");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let mut db = FileObjectDatabase::from_git_dir(&git_dir, format);

        let packed_blob = EncodedObject::new(ObjectType::Blob, b"prune packed\n".to_vec());
        let existing_pack = PackFile::write_undeltified(std::slice::from_ref(&packed_blob), format)
            .expect("test operation should succeed");
        let existing = db
            .install_pack(&existing_pack)
            .expect("test operation should succeed");
        let graph = write_commit_graph(&mut db, b"prune payload\n");

        let result = repack_all_objects(&git_dir, format)
            .expect("test operation should succeed")
            .expect("test operation should succeed");
        let new_pack_checksum = PackFile::parse(&result.pack, format)
            .expect("test operation should succeed")
            .checksum;
        install_repack_result(&git_dir, format, &result, true)
            .expect("test operation should succeed");

        // Obsolete pack and its index are gone.
        assert!(!existing.pack_path.exists());
        assert!(!existing.index_path.exists());
        // Packed loose objects are gone from disk.
        for (oid, _) in &graph {
            assert!(
                !db.loose()
                    .object_path(oid)
                    .expect("test operation should succeed")
                    .exists()
            );
        }
        // The new consolidated pack remains and still serves every object.
        let pack_dir = git_dir.join("objects").join("pack");
        assert!(
            pack_dir
                .join(format!("pack-{}.pack", new_pack_checksum.to_hex()))
                .exists()
        );
        let reopened = FileObjectDatabase::from_git_dir(&git_dir, format);
        for (oid, object) in &graph {
            assert!(
                reopened
                    .contains(oid)
                    .expect("test operation should succeed")
            );
            assert_eq!(read_object_for_assert(&reopened, oid), *object);
        }
        let packed_oid = packed_blob
            .object_id(format)
            .expect("test operation should succeed");
        assert_eq!(read_object_for_assert(&reopened, &packed_oid), packed_blob);

        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn install_repack_result_preserves_keep_and_promisor_packs() {
        let root = temp_root("sley-repack-install-keep-promisor");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let mut db = FileObjectDatabase::from_git_dir(&git_dir, format);

        let keep_blob = EncodedObject::new(ObjectType::Blob, b"keep protected\n".to_vec());
        let keep_pack = PackFile::write_undeltified(std::slice::from_ref(&keep_blob), format)
            .expect("test operation should succeed");
        let keep_install = db
            .install_pack(&keep_pack)
            .expect("test operation should succeed");
        let keep_sidecar = keep_install.pack_path.with_extension("keep");
        fs::write(&keep_sidecar, b"").expect("test operation should succeed");

        let promisor_blob = EncodedObject::new(ObjectType::Blob, b"promisor protected\n".to_vec());
        let promisor_pack =
            PackFile::write_undeltified(std::slice::from_ref(&promisor_blob), format)
                .expect("test operation should succeed");
        let promisor_install = db
            .install_pack_with_options(&promisor_pack, RawPackInstallOptions { promisor: true })
            .expect("test operation should succeed");
        let promisor_sidecar = promisor_install
            .promisor_path
            .clone()
            .expect("promisor sidecar");

        let graph = write_commit_graph(&mut db, b"new consolidated payload\n");
        let result = repack_all_objects(&git_dir, format)
            .expect("test operation should succeed")
            .expect("test operation should succeed");
        assert!(result.obsolete_packs.contains(&keep_install.pack_path));
        assert!(result.obsolete_packs.contains(&promisor_install.pack_path));

        install_repack_result(&git_dir, format, &result, true)
            .expect("test operation should succeed");

        for path in [
            &keep_install.pack_path,
            &keep_install.index_path,
            &keep_sidecar,
            &promisor_install.pack_path,
            &promisor_install.index_path,
            &promisor_sidecar,
        ] {
            assert!(path.exists(), "{} should be preserved", path.display());
        }
        for (oid, _) in &graph {
            assert!(
                !db.loose()
                    .object_path(oid)
                    .expect("test operation should succeed")
                    .exists()
            );
        }

        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn install_repack_result_keeps_loose_object_absent_from_new_pack() {
        // Safety: a loose object whose id is not in the new pack must survive
        // pruning even if the caller lists it in `packed_loose`.
        let root = temp_root("sley-repack-install-safety");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let mut db = FileObjectDatabase::from_git_dir(&git_dir, format);
        let graph = write_commit_graph(&mut db, b"safety packed\n");

        let mut result = repack_all_objects(&git_dir, format)
            .expect("test operation should succeed")
            .expect("test operation should succeed");

        // A loose object that is NOT in the new pack, but mislabeled as packed.
        let stray = EncodedObject::new(ObjectType::Blob, b"never packed\n".to_vec());
        let stray_oid = db
            .write_object(stray.clone())
            .expect("test operation should succeed");
        assert!(!result.packed_loose.contains(&stray_oid));
        result.packed_loose.push(stray_oid);

        install_repack_result(&git_dir, format, &result, true)
            .expect("test operation should succeed");

        // The stray loose object is untouched because it is not in the new pack.
        assert!(
            db.loose()
                .object_path(&stray_oid)
                .expect("test operation should succeed")
                .exists()
        );
        assert_eq!(read_object_for_assert(&db, &stray_oid), stray);
        // Genuinely packed loose objects were still removed.
        for (oid, _) in &graph {
            assert!(
                !db.loose()
                    .object_path(oid)
                    .expect("test operation should succeed")
                    .exists()
            );
        }

        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn prune_unreachable_loose_reports_and_deletes_only_unreachable() {
        let root = temp_root("sley-prune-unreachable");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let mut db = FileObjectDatabase::from_git_dir(&git_dir, format);
        let graph = write_commit_graph(&mut db, b"reachable payload\n");
        let commit_oid = graph[0].0.clone();

        // A dangling loose blob not referenced by the commit graph.
        let dangling = EncodedObject::new(ObjectType::Blob, b"dangling\n".to_vec());
        let dangling_oid = db
            .write_object(dangling)
            .expect("test operation should succeed");

        // Report-only pass leaves everything on disk.
        let reported = prune_unreachable_loose(&git_dir, format, [commit_oid], false)
            .expect("test operation should succeed");
        assert_eq!(reported, vec![dangling_oid]);
        assert!(
            db.loose()
                .object_path(&dangling_oid)
                .expect("test operation should succeed")
                .exists()
        );

        // Deleting pass removes only the unreachable object.
        let deleted = prune_unreachable_loose(&git_dir, format, [commit_oid], true)
            .expect("test operation should succeed");
        assert_eq!(deleted, vec![dangling_oid]);
        assert!(
            !db.loose()
                .object_path(&dangling_oid)
                .expect("test operation should succeed")
                .exists()
        );
        for (oid, object) in &graph {
            assert!(
                db.loose()
                    .object_path(oid)
                    .expect("test operation should succeed")
                    .exists()
            );
            assert_eq!(read_object_for_assert(&db, oid), *object);
        }

        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    #[test]
    fn prune_unreachable_loose_ignores_gitlink_targets() {
        let root = temp_root("sley-prune-gitlink");
        let git_dir = root.join(".git");
        fs::create_dir_all(git_dir.join("objects")).expect("test operation should succeed");
        let format = ObjectFormat::Sha1;
        let db = FileObjectDatabase::from_git_dir(&git_dir, format);

        let submodule_oid = ObjectId::from_hex(format, "1111111111111111111111111111111111111111")
            .expect("test operation should succeed");
        let tree = EncodedObject::new(
            ObjectType::Tree,
            Tree {
                entries: vec![TreeEntry {
                    mode: 0o160000,
                    name: BString::from(b"submodule"),
                    oid: submodule_oid,
                }],
            }
            .write(),
        );
        let tree_oid = db
            .write_object(tree)
            .expect("test operation should succeed");
        let identity = b"Example <example@example.invalid> 0 +0000".to_vec();
        let commit = EncodedObject::new(
            ObjectType::Commit,
            Commit {
                tree: tree_oid,
                parents: Vec::new(),
                author: identity.clone(),
                committer: identity,
                encoding: None,
                message: b"gitlink\n".to_vec(),
            }
            .write(),
        );
        let commit_oid = db
            .write_object(commit)
            .expect("test operation should succeed");
        let dangling = EncodedObject::new(ObjectType::Blob, b"dangling with gitlink\n".to_vec());
        let dangling_oid = db
            .write_object(dangling)
            .expect("test operation should succeed");

        let deleted = prune_unreachable_loose(&git_dir, format, [commit_oid], true)
            .expect("test operation should succeed");

        assert_eq!(deleted, vec![dangling_oid]);
        assert!(
            !db.loose()
                .object_path(&dangling_oid)
                .expect("test operation should succeed")
                .exists()
        );

        fs::remove_dir_all(root).expect("test operation should succeed");
    }

    fn temp_root(prefix: &str) -> PathBuf {
        std::env::temp_dir().join(format!(
            "{prefix}-{}-{}",
            std::process::id(),
            TEMPFILE_COUNTER.fetch_add(1, Ordering::Relaxed)
        ))
    }
}