znippy_plugin_git/

oid_index.rs

//! `__gunnar_oid__` — the reserved oid index.
//!
//! A raw (non-Arrow) section holding an **`stree`** keyspace over the first eight
//! bytes of every object id, plus, per entry, the full oid, the first lookup row
//! of that object's chunk run, and its object ordinal.
//!
//! ## Why stree and not the stock fst trie
//!
//! Git oids are fixed-width and uniformly random, so they share no prefixes: an
//! fst gets no prefix compression, still walks its automaton byte by byte, and
//! has **no batch path**. `stree` (`znippy-zoomies/src/stree.rs`) is built for
//! sorted fixed-width keys — one cache-line node, branchless AVX2 compare, and a
//! software-pipelined batch traversal. Serving one git pack is thousands of
//! lookups, so the batch path is the whole point.
//!
//! ## The 8-byte prefix is NOT a key — it is a filter
//!
//! Two distinct oids can share their first eight bytes. It is vanishingly
//! unlikely and it is **not impossible**, so the key is treated as what it is: a
//! filter that narrows to a short candidate run, after which the **full oid is
//! compared**. `lookup` is only ever correct because of that comparison;
//! [`GitOidIndex::candidate_run`] exposes the unverified run precisely so a test
//! can prove the verify step is load-bearing rather than decoration.
//!
//! ## Section layout (little-endian; keys are 8-byte aligned for `stree`)
//!
//! ```text
//!   0  magic  b"ZNPYGOID"                8
//!   8  u32 version                       4
//!  12  u8  hash code (1=sha1, 2=sha256)  1
//!  13  u8  oid_len (20 or 32)            1
//!  14  u16 reserved (0)                  2
//!  16  u64 count                         8
//!  24  i64 keys   [count]                8*count   ← sorted ascending, the stree keyspace
//!      u64 rows   [count]                8*count   ← first lookup row of that oid
//!      u32 ords   [count]                4*count   ← object ordinal (oid-lexicographic)
//!      u8  oids   [count * oid_len]                ← full oid, for the verify step
//! ```
//!
//! ## The key is order-preserving, and the sign bit is why
//!
//! `i64::from_be_bytes(oid[..8])` — the literal reading of "the first eight bytes
//! as an i64" — is **not** order-preserving over oid bytes: an oid whose first
//! byte is `0x80` or higher goes negative and sorts before every oid starting
//! `0x00..0x7f`, which is roughly half the keyspace on the wrong side. The key
//! here therefore flips the top bit, `(u64::from_be_bytes(first8) ^ (1 << 63)) as
//! i64`, which maps unsigned order onto signed order exactly. Key rank is then
//! oid-lexicographic rank.
//!
//! ## …and the parallel arrays are still not redundant
//!
//! With an order-preserving key it is tempting to drop both parallel arrays and
//! read them off the rank. Only one of the two can go:
//!
//! * `ords` equals the rank for every index [`crate::sections::GitIndexBuilder`]
//!   builds, because that is where the ordinal is defined and it numbers the same
//!   oid-lexicographic sequence. It is still stored, because [`build_section`] is
//!   the lower-level API and its contract does **not** require the caller's
//!   ordinal to be a rank — the ordinal is the `__gunnar_reach__` bitmap space,
//!   and a caller indexing a subset of a larger archive has ordinals from the
//!   larger space. Dropping the array is 4 bytes per object and a narrower
//!   contract; it is not free, and it is not done here.
//! * `rows` is **not** the rank and cannot become it. A lookup row is a *chunk*
//!   row: an object above `file_split_block_size` occupies several consecutive
//!   rows, and the lookup covers **every** path in the archive, not only git
//!   objects — an archive holding anything besides the object store has git rows
//!   that are not contiguous at all. `rows` is monotonic in rank and equal to it
//!   only in the special case of a single-chunk, git-only archive.

use std::path::Path;

use anyhow::{Result, bail, ensure};
use znippy_common::read_reserved_section_bytes;
use znippy_common::GUNNAR_OID_MODULE;
use znippy_zoomies::stree::STree64Mmap;

use crate::object::GitHashKind;

pub const GIT_OID_MAGIC: [u8; 8] = *b"ZNPYGOID";
/// Bumped 1 → 2 when the key became order-preserving. A v1 section holds the same
/// bytes in the same places but sorted on a different key, so a v2 reader walking
/// it would return wrong rows rather than fail — which is why the reader below
/// requires an **exact** match instead of `<=`.
pub const GIT_OID_VERSION: u32 = 2;
const HEADER_LEN: usize = 24;

/// Number of queries the pipelined batch path keeps in flight. 8 matched the
/// stree bench sweet spot for i64 keys; it is a const-generic on the zoomies
/// side, so changing it here is a one-token edit.
const BATCH_P: usize = 8;

/// One object as the index records it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct OidEntry {
    /// Raw object id.
    pub oid: Vec<u8>,
    /// First row of this object's contiguous chunk run in the sorted lookup
    /// sub-index.
    pub lookup_row: u64,
    /// Position of this object in the archive's oid-lexicographic ordering —
    /// the ordinal space `__gunnar_reach__` bitmaps address.
    pub ordinal: u32,
}

/// The key an oid maps into: its first eight bytes as a big-endian unsigned
/// integer, with the top bit flipped so that unsigned order becomes signed order.
///
/// The flip is the whole point — `stree` compares `i64`, and without it every oid
/// starting `0x80` or higher sorts before every oid starting `0x00..0x7f`. See the
/// module docs.
///
/// Oids shorter than eight bytes cannot occur (sha1 is 20), but the function is
/// total anyway: it zero-pads rather than panicking.
pub fn key_for_oid(oid: &[u8]) -> i64 {
    let mut b = [0u8; 8];
    let n = oid.len().min(8);
    b[..n].copy_from_slice(&oid[..n]);
    (u64::from_be_bytes(b) ^ (1u64 << 63)) as i64
}

/// Serialize the `__gunnar_oid__` section. `entries` may be in any order; they
/// are sorted by key here, which is what `stree` requires.
pub fn build_section(entries: &[OidEntry], hash: GitHashKind) -> Result<Vec<u8>> {
    let oid_len = hash.oid_len();
    for e in entries {
        ensure!(
            e.oid.len() == oid_len,
            "oid length {} does not match hash kind {:?}",
            e.oid.len(),
            hash
        );
    }
    let mut order: Vec<usize> = (0..entries.len()).collect();
    // Sort by (key, full oid) so a duplicate-key run has a deterministic layout.
    order.sort_by(|&a, &b| {
        key_for_oid(&entries[a].oid)
            .cmp(&key_for_oid(&entries[b].oid))
            .then_with(|| entries[a].oid.cmp(&entries[b].oid))
    });

    let n = entries.len();
    let mut out = Vec::with_capacity(HEADER_LEN + n * (8 + 8 + 4 + oid_len));
    out.extend_from_slice(&GIT_OID_MAGIC);
    out.extend_from_slice(&GIT_OID_VERSION.to_le_bytes());
    out.push(hash.code());
    out.push(oid_len as u8);
    out.extend_from_slice(&0u16.to_le_bytes());
    out.extend_from_slice(&(n as u64).to_le_bytes());
    debug_assert_eq!(out.len(), HEADER_LEN);
    for &i in &order {
        out.extend_from_slice(&key_for_oid(&entries[i].oid).to_le_bytes());
    }
    for &i in &order {
        out.extend_from_slice(&entries[i].lookup_row.to_le_bytes());
    }
    for &i in &order {
        out.extend_from_slice(&entries[i].ordinal.to_le_bytes());
    }
    for &i in &order {
        out.extend_from_slice(&entries[i].oid);
    }
    Ok(out)
}

/// What a successful lookup resolved to.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct OidHit {
    /// Index of the entry within the index (its position in key order).
    pub entry: usize,
    /// First lookup row of the object's chunk run.
    pub lookup_row: u64,
    /// Object ordinal (the `__gunnar_reach__` bitmap space).
    pub ordinal: u32,
}

/// Reader over a `__gunnar_oid__` section.
pub struct GitOidIndex {
    bytes: Vec<u8>,
    count: usize,
    oid_len: usize,
    hash: GitHashKind,
    /// `None` for an empty index — `STree64Mmap` requires `count > 0`.
    tree: Option<STree64Mmap>,
}

impl GitOidIndex {
    /// Parse a section produced by [`build_section`].
    pub fn parse(bytes: Vec<u8>) -> Result<Self> {
        ensure!(bytes.len() >= HEADER_LEN, "__gunnar_oid__ section truncated");
        ensure!(bytes[..8] == GIT_OID_MAGIC, "__gunnar_oid__ bad magic");
        let version = u32::from_le_bytes(bytes[8..12].try_into().unwrap());
        ensure!(
            version == GIT_OID_VERSION,
            "__gunnar_oid__ is version {version}, this reader speaks {GIT_OID_VERSION} \
             only — v1 sorted its keys on a non-order-preserving key, so reading one \
             here would return wrong rows instead of failing"
        );
        let Some(hash) = GitHashKind::from_code(bytes[12]) else {
            bail!("__gunnar_oid__ unknown hash code {}", bytes[12]);
        };
        let oid_len = bytes[13] as usize;
        ensure!(
            oid_len == hash.oid_len(),
            "__gunnar_oid__ oid_len {oid_len} disagrees with hash {hash:?}"
        );
        let count = u64::from_le_bytes(bytes[16..24].try_into().unwrap()) as usize;
        let need = HEADER_LEN
            .checked_add(count.checked_mul(8 + 8 + 4 + oid_len).unwrap_or(usize::MAX))
            .unwrap_or(usize::MAX);
        ensure!(
            bytes.len() >= need,
            "__gunnar_oid__ declares {count} entries but section is {} bytes (needs {need})",
            bytes.len()
        );

        let tree = if count == 0 {
            None
        } else {
            let keys = &bytes[HEADER_LEN..HEADER_LEN + count * 8];
            Some(STree64Mmap::new_with_stride(keys, count, 8))
        };
        Ok(Self { bytes, count, oid_len, hash, tree })
    }

    /// Read the section out of a sealed archive. `Ok(None)` when the archive
    /// carries no oid index (i.e. it is not a `git`-format archive).
    pub fn open(archive: &Path) -> Result<Option<Self>> {
        match read_reserved_section_bytes(archive, GUNNAR_OID_MODULE)? {
            Some(b) => Ok(Some(Self::parse(b)?)),
            None => Ok(None),
        }
    }

    pub fn len(&self) -> usize {
        self.count
    }

    pub fn is_empty(&self) -> bool {
        self.count == 0
    }

    pub fn hash_kind(&self) -> GitHashKind {
        self.hash
    }

    fn keys(&self) -> &[u8] {
        &self.bytes[HEADER_LEN..HEADER_LEN + self.count * 8]
    }

    /// The key of entry `i`.
    pub fn key_at(&self, i: usize) -> i64 {
        let off = HEADER_LEN + i * 8;
        i64::from_le_bytes(self.bytes[off..off + 8].try_into().unwrap())
    }

    /// The full oid of entry `i`.
    pub fn oid_at(&self, i: usize) -> &[u8] {
        let base = HEADER_LEN + self.count * (8 + 8 + 4) + i * self.oid_len;
        &self.bytes[base..base + self.oid_len]
    }

    fn row_at(&self, i: usize) -> u64 {
        let off = HEADER_LEN + self.count * 8 + i * 8;
        u64::from_le_bytes(self.bytes[off..off + 8].try_into().unwrap())
    }

    fn ordinal_at(&self, i: usize) -> u32 {
        let off = HEADER_LEN + self.count * 16 + i * 4;
        u32::from_le_bytes(self.bytes[off..off + 4].try_into().unwrap())
    }

    /// The **unverified** candidate run for a key: every entry sharing that
    /// 8-byte prefix, as `start..end`. Normally length 1; length > 1 is a real
    /// prefix collision.
    ///
    /// Exposed so a test can assert that a collision actually produces a run of
    /// two and that the verify step is what tells the two oids apart. A caller
    /// resolving an oid should use [`lookup`](Self::lookup), never this.
    pub fn candidate_run(&self, key: i64) -> std::ops::Range<usize> {
        let Some(tree) = self.tree.as_ref() else { return 0..0 };
        let Some(pos) = tree.find_exact(key, self.keys()) else { return 0..0 };
        self.expand_run(pos, key)
    }

    /// Widen a hit to the whole run of equal keys. `stree` routes to *a* member
    /// of the run; which member is an implementation detail, so both directions
    /// are walked rather than assumed.
    fn expand_run(&self, pos: usize, key: i64) -> std::ops::Range<usize> {
        let mut lo = pos;
        while lo > 0 && self.key_at(lo - 1) == key {
            lo -= 1;
        }
        let mut hi = pos + 1;
        while hi < self.count && self.key_at(hi) == key {
            hi += 1;
        }
        lo..hi
    }

    /// Resolve a raw oid. `None` when absent.
    ///
    /// stree narrows to a candidate run; the full oid is then compared against
    /// every candidate. Skipping that comparison would return a *different*
    /// object's row whenever two oids share their first eight bytes.
    pub fn lookup(&self, oid: &[u8]) -> Option<OidHit> {
        if oid.len() != self.oid_len {
            return None;
        }
        let tree = self.tree.as_ref()?;
        let key = key_for_oid(oid);
        let pos = tree.find_exact(key, self.keys())?;
        self.verify(pos, key, oid)
    }

    /// Resolve a hex oid.
    pub fn lookup_hex(&self, hex_oid: &str) -> Option<OidHit> {
        if hex_oid.len() != self.oid_len * 2 {
            return None;
        }
        let raw = hex::decode(hex_oid).ok()?;
        self.lookup(&raw)
    }

    fn verify(&self, pos: usize, key: i64, oid: &[u8]) -> Option<OidHit> {
        for i in self.expand_run(pos, key) {
            if self.oid_at(i) == oid {
                return Some(OidHit {
                    entry: i,
                    lookup_row: self.row_at(i),
                    ordinal: self.ordinal_at(i),
                });
            }
        }
        None
    }

    /// Resolve many oids at once through stree's software-pipelined batch
    /// traversal. This is the path that matters: serving one pack is hundreds to
    /// thousands of lookups, and the pipelined walk overlaps their memory
    /// latency instead of paying it serially.
    ///
    /// Results are positional — `out[i]` corresponds to `oids[i]`. Every hit is
    /// full-oid verified, exactly as in [`lookup`](Self::lookup).
    pub fn lookup_batch(&self, oids: &[&[u8]]) -> Vec<Option<OidHit>> {
        let Some(tree) = self.tree.as_ref() else { return vec![None; oids.len()] };
        let keys: Vec<i64> = oids.iter().map(|o| key_for_oid(o)).collect();
        let raw = tree.lookup_batch_pipeline::<BATCH_P>(&keys, self.keys());
        raw.into_iter()
            .zip(oids.iter())
            .enumerate()
            .map(|(i, (pos, oid))| {
                if oid.len() != self.oid_len {
                    return None;
                }
                self.verify(pos?, keys[i], oid)
            })
            .collect()
    }

    /// The **baseline** the stree keyspace has to beat: `std::binary_search` over
    /// the very same sorted key array, followed by the very same full-oid verify.
    ///
    /// It exists only under `bench-kernels`, and it exists so the choice of stree
    /// is a measurement rather than an argument. Anything cheaper than this would
    /// not be the same question: it derives the key the same way, expands the
    /// equal-key run the same way, and compares the same 20 or 32 bytes — the
    /// only difference is how it finds the run.
    #[cfg(feature = "bench-kernels")]
    pub fn lookup_binary_search(&self, oid: &[u8]) -> Option<OidHit> {
        if oid.len() != self.oid_len || self.count == 0 {
            return None;
        }
        let key = key_for_oid(oid);
        // The keys live little-endian in `bytes`; read them through `key_at` so
        // there is one decoder, not two.
        let mut lo = 0usize;
        let mut hi = self.count;
        while lo < hi {
            let mid = lo + (hi - lo) / 2;
            if self.key_at(mid) < key { lo = mid + 1 } else { hi = mid }
        }
        if lo >= self.count || self.key_at(lo) != key {
            return None;
        }
        self.verify(lo, key, oid)
    }

    /// Hex convenience over [`lookup_batch`](Self::lookup_batch).
    pub fn lookup_batch_hex(&self, hex_oids: &[&str]) -> Vec<Option<OidHit>> {
        let raw: Vec<Vec<u8>> = hex_oids.iter().map(|h| hex::decode(h).unwrap_or_default()).collect();
        let refs: Vec<&[u8]> = raw.iter().map(|v| v.as_slice()).collect();
        self.lookup_batch(&refs)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn oid(bytes: &[u8], len: usize) -> Vec<u8> {
        let mut v = bytes.to_vec();
        v.resize(len, 0);
        v
    }

    fn idx(entries: Vec<OidEntry>, hash: GitHashKind) -> GitOidIndex {
        GitOidIndex::parse(build_section(&entries, hash).unwrap()).unwrap()
    }

    #[test]
    fn resolves_every_entry_it_was_built_from() {
        // 300 entries → tall enough that stree has real internal layers.
        let n = 300usize;
        let entries: Vec<OidEntry> = (0..n)
            .map(|i| {
                let mut o = [0u8; 32];
                o[..8].copy_from_slice(&(i as u64).wrapping_mul(0x0123_4567_89ab_cdef).to_be_bytes());
                o[8] = (i % 251) as u8;
                OidEntry { oid: o.to_vec(), lookup_row: (i * 3) as u64, ordinal: i as u32 }
            })
            .collect();
        let index = idx(entries.clone(), GitHashKind::Sha256);
        assert_eq!(index.len(), n);
        for e in &entries {
            let hit = index.lookup(&e.oid).unwrap_or_else(|| panic!("miss for {}", hex::encode(&e.oid)));
            assert_eq!(hit.lookup_row, e.lookup_row);
            assert_eq!(hit.ordinal, e.ordinal);
        }
        // And an oid that is NOT in the index must miss.
        let mut absent = entries[0].oid.clone();
        absent[31] ^= 0xff;
        assert!(index.lookup(&absent).is_none());
    }

    /// LAW 2 — the collision case, constructed rather than hoped for.
    ///
    /// Two oids that agree on their first eight bytes and differ after. They
    /// share one stree key, so the tree alone cannot tell them apart; only the
    /// full-oid comparison can. The assertions below are on the *applied
    /// output* (the two rows resolved), so an implementation that dropped the
    /// verify and returned the first candidate would return the same row twice
    /// and fail here.
    #[test]
    fn eight_byte_prefix_collision_is_resolved_by_the_full_oid() {
        let prefix = [0xde, 0xad, 0xbe, 0xef, 0x01, 0x02, 0x03, 0x04];
        let mut a = oid(&prefix, 32);
        let mut b = oid(&prefix, 32);
        a[8] = 0xaa;
        b[8] = 0xbb;
        assert_eq!(key_for_oid(&a), key_for_oid(&b), "test premise: keys must collide");
        assert_ne!(a, b);

        // Some filler so the tree is not a single leaf block.
        let mut entries = vec![
            OidEntry { oid: a.clone(), lookup_row: 100, ordinal: 7 },
            OidEntry { oid: b.clone(), lookup_row: 200, ordinal: 9 },
        ];
        for i in 0..64u64 {
            let mut o = [0u8; 32];
            o[..8].copy_from_slice(&i.wrapping_mul(0x1111_1111_1111_1111).to_be_bytes());
            o[9] = 1;
            entries.push(OidEntry { oid: o.to_vec(), lookup_row: 900 + i, ordinal: 100 + i as u32 });
        }
        let index = idx(entries, GitHashKind::Sha256);

        // The collision is real in the built index: one key, two candidates.
        let run = index.candidate_run(key_for_oid(&a));
        assert_eq!(run.len(), 2, "expected a 2-entry candidate run, got {run:?}");
        assert_eq!(index.key_at(run.start), index.key_at(run.start + 1));

        // Applied output: the two oids resolve to their OWN rows.
        let ha = index.lookup(&a).expect("a must resolve");
        let hb = index.lookup(&b).expect("b must resolve");
        assert_eq!(ha.lookup_row, 100);
        assert_eq!(hb.lookup_row, 200);
        assert_eq!(ha.ordinal, 7);
        assert_eq!(hb.ordinal, 9);
        assert_ne!(ha.lookup_row, hb.lookup_row);

        // A third oid on the same prefix that was never inserted must MISS —
        // a verify-less lookup would happily hand back a candidate's row.
        let mut c = oid(&prefix, 32);
        c[8] = 0xcc;
        assert!(index.lookup(&c).is_none(), "unstored oid on a colliding prefix must miss");
    }

    #[test]
    fn batch_path_agrees_with_the_serial_path_including_on_a_collision() {
        let prefix = [0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff];
        let mut a = oid(&prefix, 20);
        let mut b = oid(&prefix, 20);
        a[8] = 1;
        b[8] = 2;
        let mut entries = vec![
            OidEntry { oid: a.clone(), lookup_row: 11, ordinal: 1 },
            OidEntry { oid: b.clone(), lookup_row: 22, ordinal: 2 },
        ];
        for i in 0..200u64 {
            let mut o = [0u8; 20];
            o[..8].copy_from_slice(&(i.wrapping_mul(0x9e37_79b9_7f4a_7c15)).to_be_bytes());
            o[10] = (i % 97) as u8;
            entries.push(OidEntry { oid: o.to_vec(), lookup_row: 1000 + i, ordinal: 500 + i as u32 });
        }
        let index = idx(entries.clone(), GitHashKind::Sha1);

        let mut queries: Vec<&[u8]> = entries.iter().map(|e| e.oid.as_slice()).collect();
        let absent = oid(&[0xab, 0xcd, 0xef, 0x00, 0x11, 0x22, 0x33, 0x44], 20);
        queries.push(&absent);

        let batched = index.lookup_batch(&queries);
        assert_eq!(batched.len(), queries.len());
        for (i, q) in queries.iter().enumerate() {
            assert_eq!(batched[i], index.lookup(q), "batch/serial disagree at {i}");
        }
        assert!(batched.last().unwrap().is_none(), "absent oid must miss in the batch path too");
        assert_eq!(batched[0].unwrap().lookup_row, 11);
        assert_eq!(batched[1].unwrap().lookup_row, 22);
    }

    #[test]
    fn empty_index_is_a_clean_miss_not_a_panic() {
        let index = idx(Vec::new(), GitHashKind::Sha256);
        assert!(index.is_empty());
        assert!(index.lookup(&oid(&[1], 32)).is_none());
        assert_eq!(index.lookup_batch(&[&oid(&[1], 32)[..]]), vec![None]);
    }

    #[test]
    fn truncated_or_mislabelled_sections_are_rejected() {
        let entries = vec![OidEntry { oid: oid(&[9], 20), lookup_row: 0, ordinal: 0 }];
        let good = build_section(&entries, GitHashKind::Sha1).unwrap();
        assert!(GitOidIndex::parse(good.clone()).is_ok());

        let mut bad_magic = good.clone();
        bad_magic[0] = b'X';
        assert!(GitOidIndex::parse(bad_magic).is_err());

        let mut newer = good.clone();
        newer[8..12].copy_from_slice(&(GIT_OID_VERSION + 1).to_le_bytes());
        assert!(GitOidIndex::parse(newer).is_err());

        assert!(GitOidIndex::parse(good[..HEADER_LEN + 4].to_vec()).is_err());
        assert!(GitOidIndex::parse(Vec::new()).is_err());
    }

    /// LAW 2 — the sign-bit trap, asserted on applied output.
    ///
    /// Half of all oids start `0x80..0xff`. Under the literal
    /// `i64::from_be_bytes` key those sort *before* every oid starting
    /// `0x00..0x7f`, so entry order is not oid order. This asserts entry `i` holds
    /// the `i`-th oid lexicographically — which is exactly what fails if the top-
    /// bit flip in [`key_for_oid`] is removed, and which a test built only from
    /// low-byte oids could never see.
    #[test]
    fn entry_order_is_oid_lexicographic_across_the_sign_boundary() {
        let firsts: [u8; 8] = [0x00, 0x7f, 0x80, 0xff, 0x01, 0xfe, 0x81, 0x7e];
        let entries: Vec<OidEntry> = firsts
            .iter()
            .enumerate()
            .map(|(i, &f)| {
                let mut o = [0u8; 32];
                o[0] = f;
                o[1] = i as u8;
                OidEntry { oid: o.to_vec(), lookup_row: i as u64, ordinal: i as u32 }
            })
            .collect();
        let index = idx(entries.clone(), GitHashKind::Sha256);

        let mut want: Vec<Vec<u8>> = entries.iter().map(|e| e.oid.clone()).collect();
        want.sort();
        for (i, w) in want.iter().enumerate() {
            assert_eq!(
                index.oid_at(i),
                w.as_slice(),
                "entry {i} is {} but the {i}-th oid lexicographically is {}",
                hex::encode(index.oid_at(i)),
                hex::encode(w)
            );
        }
        // And the keys themselves must be ascending — stree requires it, and an
        // unsorted keyspace is the failure that would otherwise surface as an
        // occasional wrong row rather than an error.
        for i in 1..index.len() {
            assert!(
                index.key_at(i - 1) < index.key_at(i),
                "keys not ascending at {i}: {} then {}",
                index.key_at(i - 1),
                index.key_at(i)
            );
        }
        // Every oid still resolves to its own row, sign bit or not.
        for e in &entries {
            assert_eq!(index.lookup(&e.oid).unwrap().lookup_row, e.lookup_row);
        }
    }

    /// A v1 section must be refused, not silently misread: the layout is
    /// identical and only the key ordering changed, so a `<=` version check would
    /// hand back wrong rows without erroring.
    #[test]
    fn a_v1_section_is_refused_rather_than_misread() {
        let entries = vec![OidEntry { oid: oid(&[0x80], 20), lookup_row: 3, ordinal: 0 }];
        let mut v1 = build_section(&entries, GitHashKind::Sha1).unwrap();
        v1[8..12].copy_from_slice(&1u32.to_le_bytes());
        let err = match GitOidIndex::parse(v1) {
            Ok(_) => panic!("a v1 section must be refused"),
            Err(e) => e.to_string(),
        };
        assert!(err.contains("version 1"), "error must name the version: {err}");
    }

    #[test]
    fn build_rejects_an_oid_of_the_wrong_width() {
        let entries = vec![OidEntry { oid: oid(&[1], 20), lookup_row: 0, ordinal: 0 }];
        assert!(build_section(&entries, GitHashKind::Sha256).is_err());
    }
}