nordisk/edda

crates/gunnar-bitmap/src/pack_order.rs

//! Turning a bitmap position into something you can look up.
//!
//! # The trap
//!
//! Every **bit inside** a bitmap in a `.bitmap` file is a **pack position**: the
//! object's rank when the pack's objects are ordered by their offset in the
//! `.pack` file. It is *not* the object's position in the `.idx`, which is
//! sorted by object id.
//!
//! Confusingly, the `commit_index_pos` in an entry header *is* an `.idx`
//! position. One file, two spaces; [`crate::file`] documents the measurement.
//!
//! The format documentation says "the position **in the index** for the packfile
//! or multi-pack index", which reads like `.idx` order and is how this crate
//! first implemented it. It is wrong for a packfile. git's own
//! `bitmap_position_packfile()` goes `find_pack_entry_one()` to an offset and
//! then `offset_to_pack_pos()`, which is pack order.
//!
//! Measured on a git-2.53 fixture pack of 4136 objects, 2026-08-04:
//!
//! * sorted by pack offset, objects 0..=198 are all 199 commits, exactly
//!   matching the commits type bitmap (`bit_size` 199, popcount 199);
//! * sorted by object id, position 0 is a *tree*.
//!
//! Reading positions as `.idx` positions therefore does not fail loudly. It
//! returns a set of the right *size* made of the wrong objects, which is the
//! worst possible failure for a fetch: a plausible pack full of things the
//! client did not ask for. The only reason it was caught here is that the tests
//! compare against `git rev-list --objects` rather than against this crate's own
//! encoder.
//!
//! # Why this lives in this crate
//!
//! The permutation is derived from the pack offsets the caller already has in
//! the `.idx`, so it needs no new dependency, and putting it anywhere else means
//! every consumer rediscovers the paragraph above the hard way.

/// The permutation between pack positions and pack index positions.
#[derive(Clone, Debug, Default)]
pub struct PackOrder {
    /// Indexed by pack position, holds the `.idx` position.
    to_index: Vec<u32>,
    /// Indexed by `.idx` position, holds the pack position.
    to_pack: Vec<u32>,
}

impl PackOrder {
    /// Build from the pack offsets of every object, in `.idx` order.
    ///
    /// `offsets[i]` is the offset in the `.pack` of the object at `.idx`
    /// position `i` — exactly what iterating a pack index gives you.
    pub fn from_index_offsets(offsets: &[u64]) -> Self {
        let mut order: Vec<u32> = (0..offsets.len() as u32).collect();
        // Offsets are unique within a pack, so the sort is total and this
        // permutation is the same one git computes for its reverse index.
        order.sort_unstable_by_key(|&i| offsets[i as usize]);
        let mut to_pack = vec![0u32; offsets.len()];
        for (pack_pos, &index_pos) in order.iter().enumerate() {
            to_pack[index_pos as usize] = pack_pos as u32;
        }
        PackOrder {
            to_index: order,
            to_pack,
        }
    }

    /// Number of objects covered.
    pub fn len(&self) -> usize {
        self.to_index.len()
    }

    /// Whether the pack is empty.
    pub fn is_empty(&self) -> bool {
        self.to_index.is_empty()
    }

    /// `.idx` position of the object at bitmap position `pack_pos`.
    pub fn index_position(&self, pack_pos: u32) -> Option<u32> {
        self.to_index.get(pack_pos as usize).copied()
    }

    /// Bitmap position of the object at `.idx` position `index_pos`.
    pub fn pack_position(&self, index_pos: u32) -> Option<u32> {
        self.to_pack.get(index_pos as usize).copied()
    }

    /// Translate a whole set of bitmap positions into `.idx` positions.
    ///
    /// Positions beyond the end of the pack are dropped; a bitmap can carry
    /// trailing bits in its last word that address nothing.
    pub fn index_positions<'a>(&'a self, set: &'a crate::Bitmap) -> impl Iterator<Item = u32> + 'a {
        set.iter_set_bits().filter_map(|p| self.index_position(p))
    }
}