znippy_plugin_git/

index_layout.rs

//! One git object index, **three Arrow IPC layouts**, measured against each other.
//!
//! ## The question
//!
//! A git `.pack` carries no index at all. Git derives several *separate* files
//! from it — `.idx` (oid → offset), `.rev` (offset → length), `.bitmap`,
//! `.midx` — and two of the four facts a server actually needs on the hot path
//! are in **none** of them:
//!
//! | fact | where git keeps it |
//! |---|---|
//! | oid | `.idx` |
//! | byte extent (offset, len) | offset in `.idx`, length only via `.rev` or the next offset |
//! | **type** | nowhere — an entry-header parse per object |
//! | **uncompressed size** | nowhere — the same entry-header parse |
//! | **delta base** | nowhere — the same entry-header parse, plus a varint |
//!
//! ## `delta_base` is an OFFSET, and the arms are named for what they were
//!
//! PLAN §13 settles it: `delta_base` is a `u64` **archive offset**, not a row
//! ordinal into this table. An ordinal would be half the width and would index
//! the very table it sits in — and it would break **silently** the first time
//! the table is rebuilt in a different order, which §14 guarantees will happen
//! because the whole index is a droppable cache. An offset is order-independent
//! because the pack it addresses never moves; `PackWalk::rebased` shifts it with
//! one addition and no table to keep in step. `0` is the sentinel for *no base*:
//! archive offset 0 is a pack's `PACK` magic, so no entry can start there.
//!
//! It joined the schema after the three arms were named and measured, so the
//! names now count **sections and tables, which is the variable under test** —
//! not facts. [`FourTables`] is four IPC sections, [`OneTableFourColumns`] is
//! one; both carry **five** payload columns today, and [`PackedPayload`] still
//! carries one. Every ns figure quoted below was taken on the four-fact,
//! 25-byte schema and is marked where that matters.
//!
//! So `cat-file --batch-check` over a pack is a varint decode per object, and a
//! `have` negotiation of 1000 oids is 1000 of them. Consolidating all four facts
//! into one index is the point of this module. The open question is what
//! *shape* that index should have, and this module answers it by building three
//! shapes behind [`ObjectIndex`] and benchmarking them
//! (`examples/index_layout_bench.rs`).
//!
//! | arm | payload columns | buffers a full-row fetch touches |
//! |---|---:|---:|
//! | [`FourTables`] | 5, in four IPC sections | 5 |
//! | [`OneTableFourColumns`] | 5, in one IPC section | 5 |
//! | [`PackedPayload`] | **1**, in one IPC section | **1** |
//!
//! The first two were the original experiment, and they **tied at every size,
//! batch size and hit rate**. The reason is visible in the table: Arrow is
//! columnar, so "one table with five columns" is *not* row-contiguous. Both
//! arms keep `offset`, `len`, `object_type`, `uncompressed_size` and
//! `delta_base` in five separate buffers whose bases are megabytes apart
//! (measured: 1 737 664 bytes between the `offset` and `size` buffers at
//! 100 000 rows), so a full-row fetch costs five unrelated strides either way.
//! **The number of tables was never the variable. The number of columns is** —
//! which is what the third arm changes, and it is the only one that moves the
//! number.
//!
//! ## What is deliberately shared, so the measurement is of the layout
//!
//! All three arms resolve `oid → ordinal` through the **same** [`crate::oid_index`]
//! `stree` (LAW 5: reuse, do not twin — and a third oid index written by
//! accident would have made the arms incomparable anyway). The two columnar arms
//! share one `ColumnarPayload` holding every read path, so they cannot drift
//! apart in the hot loop and the only thing between them is IPC framing.
//!
//! ## Zero-copy is asserted, not assumed
//!
//! All three arms decode with `StreamDecoder::with_require_alignment(true)`,
//! which makes arrow **error** rather than silently allocate-and-copy when a
//! buffer is misaligned. A layout that quietly copied its columns out of the IPC
//! bytes on open would be a different (and much slower to build) thing than the
//! one being claimed, so the reader refuses to be that thing.
//! [`ObjectIndex::ipc_bytes`] plus each arm's `column_is_inside_ipc` let a test
//! prove each array's data pointer actually lies inside the IPC buffer.
//!
//! # Measured
//!
//! oden, 32 cores, 2026-08-07, `--release --no-default-features`, sha1 oids,
//! 100 000 lookups per cell, 5 runs per cell, 4 sizes × 3 hit rates × 7 access
//! paths + 2 column scans. `/proc/loadavg` 0.96–2.98 (1-min) across the three
//! sweeps — the first rotation started at 2.98, the other two at 1.53 and 1.35,
//! and the reported figures are the geometric mean of all three, so no arm sat
//! disproportionately in the busier one.
//!
//! Position is cancelled by **rotation**: the sweep is run three times with the
//! arm order rotated, so each arm occupies each position exactly once. This
//! matters — in the earlier two-arm work the arm timed second was measurably
//! 1.1% slower at N ≥ 1e6 whichever layout it was, which is enough to invent a
//! result out of nothing.
//!
//! **Noise band: median 8.9% run-to-run spread, p90 32.3%** over 270 cells
//! (excluding the 1e3 scans, whose ns-per-row is below timer resolution). The
//! p90 is carried almost entirely by the 100 000-object rows, where the index
//! fits in L3; at 1e3 and 4e6 the bands are 2–20%. **Nothing below is claimed
//! unless it clears its own cell's band.**
//!
//! ## First: the harness really does read all four facts
//!
//! This has to be established before any of the rest means anything. A harness
//! that resolved the oid and threw the row away would measure the `stree` and
//! nothing else, and would produce a tie no matter what the layouts did.
//!
//! [`ObjectIndex::ordinals_batch`] exists for exactly this: it resolves
//! `oid → ordinal` and stops, touching no payload byte, and it is the same code
//! in all three arms. Subtracting it from the full-row path isolates the payload
//! gather — the only part any of these layouts can change:
//!
//! | objects | mix | stree floor | A payload | B payload | **C payload** | C/B |
//! |---:|---|---:|---:|---:|---:|---:|
//! | 1e3 | 100% hit | 50.3 | 6.3 | 6.1 | **1.5** | 0.24 |
//! | 1e3 | 10% hit | 39.1 | 5.3 | 5.1 | **1.8** | 0.34 |
//! | 1e5 | 50% hit | 58.6 | 15.0 | 14.0 | **10.6** | 0.76 |
//! | 1e6 | 100% hit | 195.8 | 45.0 | 46.2 | **27.7** | 0.60 |
//! | 1e6 | 10% hit | 113.4 | 11.4 | 11.1 | **7.2** | 0.65 |
//! | 4e6 | 100% hit | 247.2 | 39.2 | 43.1 | **29.8** | 0.69 |
//! | 4e6 | 50% hit | 199.6 | 30.9 | 27.9 | **20.9** | 0.75 |
//! | 4e6 | 10% hit | 141.3 | 25.1 | 21.7 | **17.7** | 0.81 |
//!
//! ns per lookup, batch 1000, position-cancelled. The payload column is nowhere
//! near zero and it differs between arms, so the facts are being read. It is
//! **9–28% of a full-row lookup**; the shared `stree` is the other 72–91%.
//!
//! ## Rickard was right: one column IS faster to fetch than four
//!
//! On the part of the work the layout controls, `PackedPayload` cuts the payload
//! gather by **19–76%**, and by **25–40% at every size from 1e6 up**. One
//! 25-byte stride against four strides megabytes apart, exactly as predicted.
//! The single cell that does not show it (1e5, 100% hit, C/B 1.06) sits in the
//! noisiest regime in the sweep, band 44%.
//!
//! Those cells are the **four-fact** schema. `delta_base` makes the packed
//! record 33 bytes and gives the columnar arms a fifth stride, so the mechanism
//! points the same way and the magnitudes are stale until re-measured. See
//! "What the fifth column costs" below for the measurement that was actually
//! taken after the column landed.
//!
//! **But the win is capped by Amdahl**, and this is the honest headline: the
//! payload gather is only 9–28% of a lookup, so a 31% cut in it is a **4–8% cut
//! end to end**. At 4e6 objects, 100% hit, position-cancelled `C/B`:
//!
//! | path | A ns | B ns | C ns | C/B | band | |
//! |---|---:|---:|---:|---:|---:|---|
//! | ordinals only (the floor) | 247.2 | 245.1 | 244.6 | 0.998 | 4.9% | tie, as it must be |
//! | full row, serial `lookup` | 464.8 | 471.8 | 435.2 | **0.922** | 7.7% | **C faster** |
//! | full row, batch 1 | 824.2 | 811.9 | 757.4 | 0.933 | 11.4% | inside band |
//! | full row, batch 100 | 298.6 | 299.0 | 283.4 | **0.948** | 5.2% | **C faster** |
//! | full row, batch 1000 | 286.4 | 288.3 | 274.4 | **0.952** | 2.8% | **C faster** |
//! | full row, batch 10000 | 284.4 | 283.3 | 271.5 | 0.959 | 4.8% | inside band |
//! | extents only, batch 1000 | 261.5 | 263.0 | 264.2 | 1.005 | 4.0% | tie |
//!
//! Three of the four full-row cells clear their band; the direction is the same
//! in all seven and at every size. At 1e3 the win is larger and cleaner (C/B
//! 0.898–0.931 at batch ≥ 100, bands 1.8–2.8%) because there the `stree` floor
//! is small enough not to swamp it.
//!
//! **`extents` is a tie, and that is the mechanism confirming itself.** A
//! partial-row fetch of two facts lets the columnar arms read two columns
//! instead of four, while the packed arm reads the same 25 bytes it always
//! reads. The advantage is exactly proportional to how much of the row you want,
//! and at half a row it is gone.
//!
//! ## What the fifth column costs
//!
//! **Footprint: exactly 8 bytes per object, in every arm.** This is arithmetic,
//! not an estimate, and the byte-exact guards below hold it there: the packed
//! record goes 25 → 33 B, and each columnar arm gains one `u64` buffer of `8n`
//! bytes. 800 kB per 100 000 objects; 32 MB at 4e6. The only *relative* change
//! between arms is that `PackedPayload` now saves four per-column IPC buffers
//! instead of three — MEASURED 50 560 B at 100 000 rows against the 38 016 B it
//! saved before (`the_packed_arm_holds_the_same_payload_but_a_smaller_section`,
//! which asserts the scaling law rather than the constant).
//!
//! **Latency: NOT re-measured, and no claim is made.** Two reasons, and the
//! second is the one that will still be true tomorrow.
//!
//! Load was the first: the harness refuses above 1-minute load 4.0 and oden was
//! carrying another agent's build at 9–26 for most of this change. That one
//! cleared on its own (it fell to 2.1), so it is not the reason this is still
//! unmeasured.
//!
//! **A before/after of a znippy change cannot be built in this tree, and that is
//! structural.** A before/after needs the old and the new source resolved at the
//! same time, which needs two znippy checkouts, and there is nowhere to put the
//! second one — MEASURED by trying all three placements:
//!
//! | where the second checkout goes | what happens |
//! |---|---|
//! | anywhere under `/home/rickard/git` | `package collision in the lockfile: znippy-common v0.9.13 (…/znippy-pre-deltabase) and znippy-common v0.9.13 (…/znippy) are different` |
//! | anywhere outside it | `failed to read …/znippy-zoomies/lbzip2/Cargo.toml` |
//!
//! The cycle is the cause, not the placement: znippy's `xtask` and `tests`
//! depend on `../../nornir`, and `nornir` depends back on
//! `../znippy/znippy-common` — an absolute reference to *the* canonical
//! checkout. So a second checkout drags the canonical one into its own resolve
//! and two different copies of one version land in one lockfile. Move it out of
//! `/home/rickard/git` to escape that and it loses the `../../znippy-zoomies/…`
//! path dependencies instead. Symlinking the siblings back does not help: cargo
//! canonicalises, so `nornir` resolves to the real one and points at the real
//! znippy again.
//!
//! Anyone wanting this number should therefore plan on **one checkout, timed
//! twice** — build the bench, `git checkout` the other revision of these files
//! in place, build again — and should not spend the hour discovering the above.
//! That mutates a shared checkout for as long as it takes to compile, which is
//! why it was not done here while another agent was working in this crate.
//!
//! What can be said without measuring, and is deliberately weaker than a
//! number: the payload gather is 9–28% of a lookup, a columnar full-row fetch
//! goes from four strides to five, and the packed record goes from ~1.4 cache
//! lines to ~1.5. Both arms get slightly worse and the packed arm's *relative*
//! advantage on full-row fetches should narrow a little. An 8-byte-per-row
//! effect is in any case inside the 8.9% median / 32.3% p90 band this sweep
//! already reports, so the honest expectation is a null result rather than a
//! regression. **Re-run `examples/index_layout_bench.rs` on a quiet box before
//! quoting any of the ns tables above as current.**
//!
//! ## …and it loses the scans, by a lot
//!
//! ns per row, full column scan, position-cancelled:
//!
//! | objects | scan | A | B | **C** | C/B |
//! |---:|---|---:|---:|---:|---:|
//! | 4e6 | `sum_uncompressed` (uses 8 B of every row) | 0.36 | 0.36 | **1.19** | **3.3×** |
//! | 4e6 | `count_type` (uses 1 B of every row) | 0.09 | 0.09 | **1.32** | **14.4×** |
//! | 1e6 | `count_type` | 0.09 | 0.09 | **1.27** | **14.0×** |
//! | 1e5 | `count_type` | 0.09 | 0.09 | **0.51** | **5.5×** |
//!
//! The 4e6 rows clear their bands (4.5% and 34.7%) with room to spare, and the
//! direction is identical at every size. This is the trade stated in
//! [`PackedPayload`]'s docs, landing exactly where predicted: `count_type` drags
//! 25 bytes through cache to use one, so it pays ~14× for the privilege of the
//! 5% it won on full-row fetches. A quota gate or a type histogram over a
//! 4-million-object repository is 5 ms on the columnar arms and 5 ms × 3–14 on
//! this one.
//!
//! ## The other figures
//!
//! | | FourTables | OneTableFourColumns | PackedPayload |
//! |---|---:|---:|---:|
//! | resident (IPC + stree), 4e6 | 326.635 MiB | 326.634 MiB | 325.203 MiB |
//! | build, 4e6 objects | 3.956 s | 4.052 s | 3.975 s |
//!
//! * **A vs B is still a tie**, now confirmed with a harness that provably reads
//!   the payload: `A/B` ranges 0.96–1.06 and every cell is inside its band. Four
//!   sections cost exactly **1048 bytes more than one, constant at every size** —
//!   the framing of three extra IPC streams, 0.0003% at 4e6.
//! * **`PackedPayload` is the smallest on disk**, by three per-column IPC
//!   buffers: 38 016 B at 100 000 rows, 75 456 B at 200 000, i.e. `3 · n/8`. Its
//!   *payload* is byte-identical (25 = 8 + 8 + 1 + 8).
//! * **Build is a tie across all three** — within 2.5% at 4e6, inside the band.
//!   Build is the oid sort and the `stree`, not the framing or the packing.
//!
//! ## What this means for the shape of the index
//!
//! Neither the packed arm nor the columnar ones is right everywhere, and the
//! measurement says which is which rather than leaving it to taste:
//!
//! * The negotiation path (`want`/`have`, full row) is **5% faster packed**, and
//!   the ceiling on that is the `stree`, not the payload — the next real win on
//!   that path is in the oid step, not here.
//! * The wire path (`extents`) is **indifferent**.
//! * Analytics (quota gates, type histograms) are **3–14× slower packed**.
//! * The packed arm gives up being four typed Arrow columns. A
//!   `FixedSizeBinary(25)` is opaque to DuckDB / Polars / DataFusion, which can
//!   query the other two arms straight off the IPC bytes with no consumer code.
//!   That is a real cost and it is not a performance one.
//!
//! ## The stree header was the next experiment, and it was a negative result
//!
//! What this sweep *can* say, which the two-arm version could not, is that
//! **the oid step is where the remaining time is**: the `ordinals_batch` floor is
//! 72–91% of every full-row lookup, and it is identical in all three arms. The
//! floor itself grows 39 ns → 247 ns from 1e3 to 4e6 objects, which is cache and
//! TLB behaviour in the `stree`, not in any payload column.
//!
//! That pointed at `oid_index`'s 24-byte header (24 mod 64 = 24, so the key
//! array is off-line by construction). It has now been built and measured —
//! [`crate::oid_index::OidLayout`] and `examples/oid_align_bench.rs`, three arms
//! separating the header offset from the allocator. **A 64-aligned keyspace
//! takes 5.2% off cache-misses, reproducibly, and does not move the clock at
//! all**: 0 of 24 cells clear their band, and 0 of 6 clear it again at 4e6 with
//! the band tightened to 5%. The header is not where the oid step's time is, and
//! the reason is instructive — `stree`'s internal nodes live in the tree's own
//! `Vec`, not in this section, so the header could only ever move the leaf
//! touch, and the pipelined batch walk was already hiding it. The full numbers
//! and the mechanism are in [`crate::oid_index`].

use std::sync::Arc;

use anyhow::{Result, anyhow, bail};
use znippy_common::arrow::array::{
    Array, FixedSizeBinaryArray, UInt8Array, UInt64Array,
};
use znippy_common::arrow::buffer::{Buffer, MutableBuffer, ScalarBuffer};
use znippy_common::arrow::datatypes::{DataType, Field, Schema, SchemaRef};
use znippy_common::arrow::ipc::reader::StreamDecoder;
use znippy_common::arrow::ipc::writer::StreamWriter;
use znippy_common::arrow::record_batch::RecordBatch;

use crate::object::GitHashKind;
use crate::oid_index::{GitOidIndex, OidEntry, OidLayout, build_section_with_layout};

// ── the four facts ────────────────────────────────────────────────────────────

/// Object type, in git's own **pack entry** encoding.
///
/// This is not [`crate::object::GitObjectKind`] and must not be merged with it:
/// that enum is the four *loose* object types, which is all a canonical
/// `"<type> <size>\0…"` header can express. A packed object also comes in the
/// two delta forms. Owned by the `git-storage-trait` contract; re-exported here
/// so `crate::index_layout::ObjType` stays a valid path.
pub use git_storage_trait::ObjType;

/// One object, as the caller hands it to [`ObjectIndex::build`]. Order is
/// irrelevant — every implementation sorts by oid and derives ordinals itself.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct IndexEntry {
    /// 20 bytes (sha1) or 32 (sha256). All entries in one index must agree.
    pub oid: Vec<u8>,
    /// Start of the object's bytes within the archive.
    pub offset: u64,
    /// Length of those bytes as stored (compressed / delta-encoded).
    pub len: u64,
    pub obj_type: ObjType,
    /// Inflated, post-delta-resolution size. The fact `.idx` and `.rev`
    /// together still cannot answer.
    pub uncompressed_size: u64,
    /// `objects.delta_base` — the **archive offset** of the entry this one
    /// deltas against, `0` for none (PLAN §13).
    ///
    /// An offset and not an ordinal, on purpose: it is in the same coordinate
    /// space as [`offset`](Self::offset), so it survives a rebuild of this table
    /// in any order and a rebase of the pack is one addition
    /// ([`crate::pack_walk::PackWalk::rebased`]). `0` cannot collide with a real
    /// base because archive offset 0 is a pack's `PACK` magic. A `REF_DELTA`
    /// records `0` until its oid is resolved to an offset —
    /// [`obj_type`](Self::obj_type) is what distinguishes that from *no base*.
    pub delta_base: u64,
}

/// What a lookup resolves to: the ordinal plus all five facts.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct IndexRow {
    /// Row ordinal — the oid-lexicographic rank, and the join key `FourTables`
    /// uses across its four sections.
    pub ordinal: u32,
    pub offset: u64,
    pub len: u64,
    pub obj_type: ObjType,
    pub uncompressed_size: u64,
    /// See [`IndexEntry::delta_base`]. An archive offset, `0` for none — never
    /// an ordinal, and in particular never *this* row's ordinal space.
    pub delta_base: u64,
}

// ── the trait ─────────────────────────────────────────────────────────────────

/// A git object index over Apache Arrow IPC.
///
/// `build` is `where Self: Sized`, so it stays out of the vtable and
/// `Box<dyn ObjectIndex>` still works — which is how the bench drives both arms
/// through one loop.
pub trait ObjectIndex: Send + Sync {
    fn build(entries: &[IndexEntry]) -> Result<Self>
    where
        Self: Sized;

    /// Resolve one oid. `None` for an absent oid **and** for an oid of the
    /// wrong width.
    fn lookup(&self, oid: &[u8]) -> Option<IndexRow>;

    /// The batch path, and the one that matters: `have` negotiation sends up to
    /// 1000 oids at a time, the push connectivity check sends thousands.
    /// Positional — `out[i]` answers `oids[i]`.
    ///
    /// This is the **full-row** access pattern: all five facts of each object.
    fn lookup_batch(&self, oids: &[&[u8]]) -> Vec<Option<IndexRow>>;

    /// oid → ordinal and **stop**. No payload column is touched at all.
    ///
    /// Identical in every implementation, because every implementation shares
    /// the same `stree`. It is here as the **floor**: whatever this costs is
    /// what no payload layout can remove, and `lookup_batch` minus this is the
    /// only part any of these layouts can change. Without it a three-way tie is
    /// unreadable — it could mean the layouts are equivalent, or it could mean
    /// the harness never read a payload byte.
    fn ordinals_batch(&self, oids: &[&[u8]]) -> Vec<Option<u32>>;

    /// The **partial-row** access pattern: byte extent only, two of the five
    /// facts. This is `extents(&[oid])`, what the wire path actually asks for
    /// when it is about to copy bytes out of a pack.
    fn extents_batch(&self, oids: &[&[u8]]) -> Vec<Option<(u64, u64)>>;

    /// Full **column scan**: total uncompressed bytes over every object. The
    /// quota gate. Reads one 8-byte fact per row and nothing else.
    fn sum_uncompressed(&self) -> u64;

    /// Full **column scan** with a predicate: how many objects of this type.
    /// Reads one *byte* per row and nothing else — the most column-shaped
    /// query there is, and the one a row-packed layout should lose worst.
    fn count_type(&self, t: ObjType) -> usize;

    fn name(&self) -> &'static str;

    fn len(&self) -> usize;

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

    /// Total bytes of Arrow IPC this index holds resident. Four sections or
    /// one, this counts the same payload, so it is comparable across arms.
    fn ipc_bytes(&self) -> usize;

    /// IPC bytes plus the `stree` oid section — everything the index keeps
    /// alive, excluding the handful of `Arc`'d schema/metadata allocations.
    fn resident_bytes(&self) -> usize;
}

// ── shared machinery: both arms are built from exactly this ───────────────────

/// Column names, one place, so the two arms cannot drift apart on spelling.
pub const COL_OID: &str = "oid";
pub const COL_OFFSET: &str = "offset";
pub const COL_LEN: &str = "len";
pub const COL_TYPE: &str = "object_type";
pub const COL_SIZE: &str = "uncompressed_size";
pub const COL_DELTA_BASE: &str = "delta_base";

/// The six Arrow arrays that carry the five facts, in oid-lexicographic order.
/// The byte extent is one fact in two columns because that is what it is —
/// `(offset, len)` — and splitting it lets a scan of just the offsets stay
/// contiguous.
pub struct Columns {
    pub oid: FixedSizeBinaryArray,
    pub offset: UInt64Array,
    pub len: UInt64Array,
    pub obj_type: UInt8Array,
    pub size: UInt64Array,
    /// Archive offset of the base entry, `0` for none. Same coordinate space as
    /// `offset`, which is what makes a whole-column comparison against the
    /// `offset` column meaningful (a delta's base is an entry in this table).
    pub delta_base: UInt64Array,
}

/// Sort indices of `entries` into oid-lexicographic order, which is also the
/// ordinal order and the order `oid_index::build_section` puts its keys in.
///
/// Ties on the full oid are impossible in a well-formed index and are checked
/// for in [`validate`] rather than being silently deduplicated.
fn oid_order(entries: &[IndexEntry]) -> Vec<u32> {
    let mut order: Vec<u32> = (0..entries.len() as u32).collect();
    order.sort_unstable_by(|&a, &b| entries[a as usize].oid.cmp(&entries[b as usize].oid));
    order
}

/// Reject the two things that would make an index silently wrong: mixed oid
/// widths, and a duplicate oid (which would give one object two ordinals and
/// make the two arms disagree on which one a lookup returns).
fn validate(entries: &[IndexEntry], order: &[u32]) -> Result<GitHashKind> {
    let Some(first) = entries.first() else {
        // An empty index is legitimate (an empty push) and its hash kind is
        // arbitrary; sha1 keeps the section 20-byte shaped.
        return Ok(GitHashKind::Sha1);
    };
    let hash = match first.oid.len() {
        20 => GitHashKind::Sha1,
        32 => GitHashKind::Sha256,
        n => bail!("oid width {n} is neither sha1 (20) nor sha256 (32)"),
    };
    for e in entries {
        if e.oid.len() != hash.oid_len() {
            bail!(
                "mixed oid widths: {} and {} in one index",
                hash.oid_len(),
                e.oid.len()
            );
        }
    }
    for w in order.windows(2) {
        if entries[w[0] as usize].oid == entries[w[1] as usize].oid {
            bail!(
                "duplicate oid {} — one object cannot hold two ordinals",
                hex::encode(&entries[w[0] as usize].oid)
            );
        }
    }
    Ok(hash)
}

/// The `stree` oid keyspace, shared verbatim by both arms.
///
/// `lookup_row` is set to the ordinal here. That is not a redefinition of the
/// field: [`crate::oid_index::build_section`] is the lower-level API and its
/// contract lets the caller choose what row an oid points at. This index's rows
/// *are* its ordinals, and both arms use the ordinal, so nothing is lost.
pub struct OidResolver {
    tree: GitOidIndex,
    section_bytes: usize,
}

impl OidResolver {
    fn build(entries: &[IndexEntry], order: &[u32], hash: GitHashKind) -> Result<Self> {
        Self::build_with(entries, order, hash, OidLayout::default())
    }

    /// [`build`](Self::build) with the section's cache-line layout chosen by the
    /// caller. Only `PackedPayload::build_with_oid_layout` uses it; see there.
    fn build_with(
        entries: &[IndexEntry],
        order: &[u32],
        hash: GitHashKind,
        layout: OidLayout,
    ) -> Result<Self> {
        let oid_entries: Vec<OidEntry> = order
            .iter()
            .enumerate()
            .map(|(rank, &i)| OidEntry {
                oid: entries[i as usize].oid.clone(),
                lookup_row: rank as u64,
                ordinal: rank as u32,
            })
            .collect();
        let section = build_section_with_layout(&oid_entries, hash, layout)?;
        let section_bytes = section.len();
        // `parse_as`, not `parse`: `Compact64Alloc` is a reader-side allocation
        // choice that the section's bytes cannot express.
        Ok(Self { tree: GitOidIndex::parse_as(section, layout)?, section_bytes })
    }

    #[inline]
    fn ordinal(&self, oid: &[u8]) -> Option<u32> {
        self.tree.lookup(oid).map(|h| h.ordinal)
    }

    #[inline]
    fn ordinals(&self, oids: &[&[u8]]) -> Vec<Option<u32>> {
        self.tree
            .lookup_batch(oids)
            .into_iter()
            .map(|h| h.map(|h| h.ordinal))
            .collect()
    }
}

/// Materialise the five arrays from `entries` in `order`.
///
/// Both arms call this and nothing else, so any difference the bench reports is
/// a difference of IPC packing, not of array construction.
pub fn columns(entries: &[IndexEntry], order: &[u32], oid_len: usize) -> Columns {
    let n = order.len();
    let mut offset: Vec<u64> = Vec::with_capacity(n);
    let mut len: Vec<u64> = Vec::with_capacity(n);
    let mut ty: Vec<u8> = Vec::with_capacity(n);
    let mut size: Vec<u64> = Vec::with_capacity(n);
    let mut delta_base: Vec<u64> = Vec::with_capacity(n);
    for &i in order {
        let e = &entries[i as usize];
        offset.push(e.offset);
        len.push(e.len);
        ty.push(e.obj_type.code());
        size.push(e.uncompressed_size);
        delta_base.push(e.delta_base);
    }
    Columns {
        oid: oid_column(entries, order, oid_len),
        offset: UInt64Array::new(ScalarBuffer::from(offset), None),
        len: UInt64Array::new(ScalarBuffer::from(len), None),
        obj_type: UInt8Array::new(ScalarBuffer::from(ty), None),
        size: UInt64Array::new(ScalarBuffer::from(size), None),
        delta_base: UInt64Array::new(ScalarBuffer::from(delta_base), None),
    }
}

/// The oid column alone. Every arm stores it, and no arm packs it into the
/// payload: the oid is the *key* the stree resolves against, not one of the
/// facts a resolved lookup fetches, so putting it next to the payload would
/// widen every payload read for a field nobody reads at lookup time.
pub fn oid_column(entries: &[IndexEntry], order: &[u32], oid_len: usize) -> FixedSizeBinaryArray {
    let mut bytes: Vec<u8> = Vec::with_capacity(order.len() * oid_len);
    for &i in order {
        bytes.extend_from_slice(&entries[i as usize].oid);
    }
    FixedSizeBinaryArray::new(oid_len as i32, Buffer::from_vec(bytes), None)
}

/// The five facts of one object, packed little-endian into `PACKED_LEN` bytes.
///
/// ```text
///   0  u64 LE  offset               8
///   8  u64 LE  len                  8
///  16  u8      object type code     1
///  17  u64 LE  uncompressed_size    8
///  25  u64 LE  delta_base           8
///                                  ══
///                                  33
/// ```
///
/// Fixed order, fixed width, no padding, no nulls. The type byte sits between
/// the extent and the sizes rather than after them so the record is 33 bytes
/// instead of 40 — the whole point of the arm is how few bytes a full-row fetch
/// drags through cache, and 33 against 40 is 18% of that budget.
///
/// **This was 25 bytes before `delta_base` (PLAN §13) joined the schema.** The
/// column is appended rather than inserted so the first four fields keep the
/// offsets every reader here and every hand-decode in the tests already uses;
/// the width is asserted byte for byte by
/// `the_packed_record_is_the_documented_33_bytes`.
pub const PACKED_LEN: usize = 33;
const P_OFFSET: usize = 0;
const P_LEN: usize = 8;
const P_TYPE: usize = 16;
const P_SIZE: usize = 17;
const P_DELTA_BASE: usize = 25;

/// One `FixedSizeBinary(PACKED_LEN)` element per object, in `order`.
pub fn packed_column(entries: &[IndexEntry], order: &[u32]) -> FixedSizeBinaryArray {
    let mut bytes: Vec<u8> = Vec::with_capacity(order.len() * PACKED_LEN);
    for &i in order {
        let e = &entries[i as usize];
        bytes.extend_from_slice(&e.offset.to_le_bytes());
        bytes.extend_from_slice(&e.len.to_le_bytes());
        bytes.push(e.obj_type.code());
        bytes.extend_from_slice(&e.uncompressed_size.to_le_bytes());
        bytes.extend_from_slice(&e.delta_base.to_le_bytes());
    }
    debug_assert_eq!(bytes.len(), order.len() * PACKED_LEN);
    FixedSizeBinaryArray::new(PACKED_LEN as i32, Buffer::from_vec(bytes), None)
}

#[inline]
fn le64(r: &[u8], at: usize) -> u64 {
    u64::from_le_bytes(r[at..at + 8].try_into().unwrap())
}

fn oid_field(oid_len: usize) -> Field {
    Field::new(COL_OID, DataType::FixedSizeBinary(oid_len as i32), false)
}

/// Serialise one batch as a self-contained Arrow IPC **stream**.
fn to_ipc(batch: &RecordBatch) -> Result<Vec<u8>> {
    let mut out = Vec::with_capacity(64 + batch.get_array_memory_size());
    {
        let mut w = StreamWriter::try_new(&mut out, batch.schema_ref())
            .map_err(|e| anyhow!("ipc writer: {e}"))?;
        w.write(batch).map_err(|e| anyhow!("ipc write: {e}"))?;
        w.finish().map_err(|e| anyhow!("ipc finish: {e}"))?;
    }
    Ok(out)
}

/// Decode an IPC stream **zero-copy**, and return the owning [`Buffer`] with it.
///
/// The `Vec<u8>` a writer produces is only 1-byte aligned, so it is first copied
/// once into a `MutableBuffer` (64-byte aligned). After that every array in the
/// batch is a view into `buffer` — enforced by `with_require_alignment(true)`,
/// which errors instead of quietly re-allocating.
fn decode_ipc(bytes: &[u8]) -> Result<(Buffer, RecordBatch)> {
    let mut mb = MutableBuffer::with_capacity(bytes.len());
    mb.extend_from_slice(bytes);
    decode_ipc_buffer(mb.into())
}

/// The half of [`decode_ipc`] that does not control the buffer's alignment,
/// split out so a test can hand it a deliberately misaligned one and prove
/// `with_require_alignment(true)` is load-bearing rather than decoration.
fn decode_ipc_buffer(owner: Buffer) -> Result<(Buffer, RecordBatch)> {
    let mut cursor = owner.clone();
    let mut decoder = StreamDecoder::new().with_require_alignment(true);
    let mut found: Option<RecordBatch> = None;
    while !cursor.is_empty() {
        match decoder.decode(&mut cursor).map_err(|e| anyhow!("ipc decode: {e}"))? {
            Some(b) if found.is_none() => found = Some(b),
            Some(_) => bail!("index section holds more than one record batch"),
            None => {}
        }
    }
    decoder.finish().map_err(|e| anyhow!("ipc unfinished: {e}"))?;
    found.ok_or_else(|| anyhow!("index section holds no record batch"))
        .map(|b| (owner, b))
}

fn col<T: Array + Clone + 'static>(batch: &RecordBatch, name: &str) -> Result<T> {
    batch
        .column_by_name(name)
        .ok_or_else(|| anyhow!("no `{name}` column"))?
        .as_any()
        .downcast_ref::<T>()
        .cloned()
        .ok_or_else(|| anyhow!("`{name}` has an unexpected type"))
}

/// True when `array`'s value bytes lie inside `ipc` — i.e. the decode really was
/// zero-copy and not an aligned re-allocation behind our back.
fn inside(ipc: &Buffer, values: &[u8]) -> bool {
    if values.is_empty() {
        // Nothing to point at; a zero-length column cannot disprove anything.
        return true;
    }
    let base = ipc.as_ptr() as usize;
    let p = values.as_ptr() as usize;
    p >= base && p + values.len() <= base + ipc.len()
}

// ── shared read paths for the two columnar arms ───────────────────────────────

/// The six arrays and **every** read path over them.
///
/// Both columnar arms hold one of these and neither has a hot path of its own,
/// so they cannot drift apart (LAW 5) and the only thing the bench can see
/// between them is how many IPC streams the arrays were framed into. That the
/// two then tie is a fact about Arrow, not about this struct: `FourTables` and
/// `OneTableFourColumns` both have **five payload columns in five separate
/// buffers**, and a full-row fetch touches five distant strides either way. The
/// number of *tables* was never the variable. The number of *columns* is, which
/// is what [`PackedPayload`] changes.
struct ColumnarPayload {
    oid: FixedSizeBinaryArray,
    offset: UInt64Array,
    len: UInt64Array,
    obj_type: UInt8Array,
    size: UInt64Array,
    delta_base: UInt64Array,
}

impl ColumnarPayload {
    /// Five separate buffer reads, five strides.
    #[inline]
    fn row_at(&self, ordinal: u32) -> IndexRow {
        let i = ordinal as usize;
        IndexRow {
            ordinal,
            offset: self.offset.value(i),
            len: self.len.value(i),
            // A code the writer cannot produce cannot appear here: the column is
            // built from `ObjType`, so the round trip is total. `Blob` is the
            // only defensible fallback and it is unreachable in a section this
            // crate wrote.
            obj_type: ObjType::from_code(self.obj_type.value(i)).unwrap_or(ObjType::Blob),
            uncompressed_size: self.size.value(i),
            delta_base: self.delta_base.value(i),
        }
    }

    /// Two of the five buffers.
    #[inline]
    fn extent_at(&self, ordinal: u32) -> (u64, u64) {
        let i = ordinal as usize;
        (self.offset.value(i), self.len.value(i))
    }

    /// One contiguous `u64` run, start to end — the case columnar is for.
    fn sum_uncompressed(&self) -> u64 {
        self.size.values().iter().copied().fold(0u64, u64::wrapping_add)
    }

    /// One contiguous `u8` run: `n` bytes read to answer a question about `n`
    /// rows, which is the least memory traffic any layout can do here.
    fn count_type(&self, t: ObjType) -> usize {
        let c = t.code();
        self.obj_type.values().iter().filter(|&&x| x == c).count()
    }

    fn inside(&self, oid_ipc: &Buffer, extent_ipc: &Buffer, type_ipc: &Buffer, size_ipc: &Buffer) -> bool {
        inside(oid_ipc, self.oid.value_data())
            && inside(extent_ipc, self.offset.values().inner().as_slice())
            && inside(extent_ipc, self.len.values().inner().as_slice())
            && inside(extent_ipc, self.delta_base.values().inner().as_slice())
            && inside(type_ipc, self.obj_type.values().inner().as_slice())
            && inside(size_ipc, self.size.values().inner().as_slice())
    }
}

/// The three schemas layout A frames its facts into, plus the oid schema.
///
/// `delta_base` rides in the **extent** section rather than in a fifth one, and
/// the reason is what the section means: it is *where the bytes are*, and a
/// delta base is an address in exactly the same coordinate space as `offset` —
/// the two are compared against each other by every guard that proves the base
/// resolves. Keeping it here also keeps layout A what the benchmark named it:
/// **four IPC sections** against layout B's one. The section count is the
/// variable under test, and adding a fifth section would have changed the
/// experiment rather than the schema.
fn extent_schema() -> SchemaRef {
    Arc::new(Schema::new(vec![
        Field::new(COL_OFFSET, DataType::UInt64, false),
        Field::new(COL_LEN, DataType::UInt64, false),
        Field::new(COL_DELTA_BASE, DataType::UInt64, false),
    ]))
}

// ── Impl A — FourTables ───────────────────────────────────────────────────────

/// Four Arrow IPC sections — oid, byte extent, type, size — joined by row
/// ordinal.
///
/// This is git's own shape: `.idx`, `.rev` and the missing type/size files, each
/// an independent artifact. A lookup resolves the oid to an ordinal and then
/// indexes three further sections at that ordinal.
///
/// The name counts **sections**, which is this arm's whole difference from
/// [`OneTableFourColumns`]. It carries five payload columns: `delta_base` joined
/// the schema afterwards and shares the extent section, for the reason given on
/// [`extent_schema`].
pub struct FourTables {
    oids: OidResolver,
    /// Owning IPC buffers, kept alive because every array below is a view into
    /// one of them. Four buffers, four allocations, four distinct page runs.
    ipc: [Buffer; 4],
    cols: ColumnarPayload,
    rows: usize,
}

impl FourTables {
    /// Section order: oid, extent, type, size.
    pub fn ipc_section_lens(&self) -> [usize; 4] {
        [self.ipc[0].len(), self.ipc[1].len(), self.ipc[2].len(), self.ipc[3].len()]
    }

    /// The oid column, straight out of its own section — proof that "four
    /// tables" still gives a contiguous scannable column.
    pub fn oid_column(&self) -> &FixedSizeBinaryArray {
        &self.cols.oid
    }

    /// Every column's bytes lie inside the section they were decoded from.
    pub fn column_is_inside_ipc(&self) -> bool {
        self.cols.inside(&self.ipc[0], &self.ipc[1], &self.ipc[2], &self.ipc[3])
    }
}

impl ObjectIndex for FourTables {
    fn build(entries: &[IndexEntry]) -> Result<Self> {
        let order = oid_order(entries);
        let hash = validate(entries, &order)?;
        let oid_len = hash.oid_len();
        let c = columns(entries, &order, oid_len);
        let oids = OidResolver::build(entries, &order, hash)?;

        let s_oid = Arc::new(Schema::new(vec![oid_field(oid_len)]));
        let s_type = Arc::new(Schema::new(vec![Field::new(COL_TYPE, DataType::UInt8, false)]));
        let s_size = Arc::new(Schema::new(vec![Field::new(COL_SIZE, DataType::UInt64, false)]));

        let b_oid = RecordBatch::try_new(s_oid, vec![Arc::new(c.oid)])?;
        let b_extent = RecordBatch::try_new(
            extent_schema(),
            vec![Arc::new(c.offset), Arc::new(c.len), Arc::new(c.delta_base)],
        )?;
        let b_type = RecordBatch::try_new(s_type, vec![Arc::new(c.obj_type)])?;
        let b_size = RecordBatch::try_new(s_size, vec![Arc::new(c.size)])?;

        let (ipc_oid, r_oid) = decode_ipc(&to_ipc(&b_oid)?)?;
        let (ipc_extent, r_extent) = decode_ipc(&to_ipc(&b_extent)?)?;
        let (ipc_type, r_type) = decode_ipc(&to_ipc(&b_type)?)?;
        let (ipc_size, r_size) = decode_ipc(&to_ipc(&b_size)?)?;

        Ok(Self {
            oids,
            ipc: [ipc_oid, ipc_extent, ipc_type, ipc_size],
            cols: ColumnarPayload {
                oid: col(&r_oid, COL_OID)?,
                offset: col(&r_extent, COL_OFFSET)?,
                len: col(&r_extent, COL_LEN)?,
                obj_type: col(&r_type, COL_TYPE)?,
                size: col(&r_size, COL_SIZE)?,
                delta_base: col(&r_extent, COL_DELTA_BASE)?,
            },
            rows: order.len(),
        })
    }

    fn lookup(&self, oid: &[u8]) -> Option<IndexRow> {
        self.oids.ordinal(oid).map(|o| self.cols.row_at(o))
    }

    fn lookup_batch(&self, oids: &[&[u8]]) -> Vec<Option<IndexRow>> {
        self.oids.ordinals(oids).into_iter().map(|o| o.map(|o| self.cols.row_at(o))).collect()
    }

    fn ordinals_batch(&self, oids: &[&[u8]]) -> Vec<Option<u32>> {
        self.oids.ordinals(oids)
    }

    fn extents_batch(&self, oids: &[&[u8]]) -> Vec<Option<(u64, u64)>> {
        self.oids.ordinals(oids).into_iter().map(|o| o.map(|o| self.cols.extent_at(o))).collect()
    }

    fn sum_uncompressed(&self) -> u64 {
        self.cols.sum_uncompressed()
    }

    fn count_type(&self, t: ObjType) -> usize {
        self.cols.count_type(t)
    }

    fn name(&self) -> &'static str {
        "FourTables"
    }

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

    fn ipc_bytes(&self) -> usize {
        self.ipc.iter().map(|b| b.len()).sum()
    }

    fn resident_bytes(&self) -> usize {
        self.ipc_bytes() + self.oids.section_bytes
    }
}

// ── Impl B — OneTableFourColumns ──────────────────────────────────────────────

/// One Arrow IPC section, one table, the facts one column each.
///
/// Arrow is columnar, so this is **not** row-contiguous: `offset` is its own
/// buffer, `len` is its own buffer, and a full-row fetch still touches five
/// strides that are megabytes apart. What it saves over [`FourTables`] is the
/// framing of three IPC streams and nothing else — which is exactly what the
/// measurement found.
///
/// The name counts the columns it had when it was named and measured; since
/// `delta_base` (PLAN §13) there are five payload columns here and in
/// [`FourTables`] alike, so the two are still separated by section count and
/// nothing else.
pub struct OneTableFourColumns {
    oids: OidResolver,
    ipc: Buffer,
    cols: ColumnarPayload,
    rows: usize,
}

impl OneTableFourColumns {
    pub fn oid_column(&self) -> &FixedSizeBinaryArray {
        &self.cols.oid
    }

    /// All five arrays are views into the one IPC buffer.
    pub fn column_is_inside_ipc(&self) -> bool {
        self.cols.inside(&self.ipc, &self.ipc, &self.ipc, &self.ipc)
    }

    /// **The bytes this index would be persisted as** — the single Arrow IPC
    /// stream every column is a view into, exactly as [`to_ipc`] framed it.
    ///
    /// [`ObjectIndex::ipc_bytes`] reports this buffer's *length*, which is
    /// enough to compare two layouts' footprints and not enough to write one
    /// down. `examples/tail_write_bench.rs` needs the bytes themselves: its
    /// no-tail arm has to rewrite the whole index on every push, and a
    /// measurement of that write is only honest if the bytes going to the file
    /// are the index's own and not a stand-in of the same size.
    ///
    /// A borrowed slice and not a `Vec`: the buffer is already resident and
    /// aligned, and handing out a copy would put an allocation inside the very
    /// write this exists to measure.
    pub fn ipc_slice(&self) -> &[u8] {
        self.ipc.as_slice()
    }
}

impl ObjectIndex for OneTableFourColumns {
    fn build(entries: &[IndexEntry]) -> Result<Self> {
        let order = oid_order(entries);
        let hash = validate(entries, &order)?;
        let oid_len = hash.oid_len();
        let c = columns(entries, &order, oid_len);
        let oids = OidResolver::build(entries, &order, hash)?;

        let schema: SchemaRef = Arc::new(Schema::new(vec![
            oid_field(oid_len),
            Field::new(COL_OFFSET, DataType::UInt64, false),
            Field::new(COL_LEN, DataType::UInt64, false),
            Field::new(COL_TYPE, DataType::UInt8, false),
            Field::new(COL_SIZE, DataType::UInt64, false),
            Field::new(COL_DELTA_BASE, DataType::UInt64, false),
        ]));
        let batch = RecordBatch::try_new(
            schema,
            vec![
                Arc::new(c.oid),
                Arc::new(c.offset),
                Arc::new(c.len),
                Arc::new(c.obj_type),
                Arc::new(c.size),
                Arc::new(c.delta_base),
            ],
        )?;
        let (ipc, r) = decode_ipc(&to_ipc(&batch)?)?;

        Ok(Self {
            oids,
            ipc,
            cols: ColumnarPayload {
                oid: col(&r, COL_OID)?,
                offset: col(&r, COL_OFFSET)?,
                len: col(&r, COL_LEN)?,
                obj_type: col(&r, COL_TYPE)?,
                size: col(&r, COL_SIZE)?,
                delta_base: col(&r, COL_DELTA_BASE)?,
            },
            rows: order.len(),
        })
    }

    fn lookup(&self, oid: &[u8]) -> Option<IndexRow> {
        self.oids.ordinal(oid).map(|o| self.cols.row_at(o))
    }

    fn lookup_batch(&self, oids: &[&[u8]]) -> Vec<Option<IndexRow>> {
        self.oids.ordinals(oids).into_iter().map(|o| o.map(|o| self.cols.row_at(o))).collect()
    }

    fn ordinals_batch(&self, oids: &[&[u8]]) -> Vec<Option<u32>> {
        self.oids.ordinals(oids)
    }

    fn extents_batch(&self, oids: &[&[u8]]) -> Vec<Option<(u64, u64)>> {
        self.oids.ordinals(oids).into_iter().map(|o| o.map(|o| self.cols.extent_at(o))).collect()
    }

    fn sum_uncompressed(&self) -> u64 {
        self.cols.sum_uncompressed()
    }

    fn count_type(&self, t: ObjType) -> usize {
        self.cols.count_type(t)
    }

    fn name(&self) -> &'static str {
        "OneTableFourColumns"
    }

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

    fn ipc_bytes(&self) -> usize {
        self.ipc.len()
    }

    fn resident_bytes(&self) -> usize {
        self.ipc_bytes() + self.oids.section_bytes
    }
}

// ── Impl C — PackedPayload ────────────────────────────────────────────────────

/// **One** payload column: all five facts of one object packed adjacently into
/// a single `FixedSizeBinary(33)` element.
///
/// This is the arm the first two were both missing. `FourTables` and
/// `OneTableFourColumns` differ in how many *tables* they use and agree in
/// having **five payload columns**, so a full-row fetch costs five buffer reads
/// at five unrelated addresses in both. Here it costs one:
///
/// ```text
/// per row, byte for byte (little-endian, no padding, no nulls):
///   0  u64  offset
///   8  u64  len
///  16  u8   object type code (1 commit, 2 tree, 3 blob, 4 tag, 6 ofs-delta, 7 ref-delta)
///  17  u64  uncompressed_size
///  25  u64  delta_base — archive offset of the base entry, 0 for none
///  33  ── next row
/// ```
///
/// **It was 24 bytes narrower before `delta_base` (PLAN §13).** A 33-byte record
/// spans one 64-byte cache line 49% of the time and two the rest, so a full-row
/// fetch is ~1.5 lines against the five the columnar arms touch — where at 25
/// bytes it was ~1.4 against four. The trade moved slightly, in both directions
/// at once, which is why the numbers below were re-taken rather than scaled.
///
/// The oid stays in its own column. It is the key the `stree` resolves
/// *against*, not one of the facts a resolved lookup fetches, so packing it in
/// would grow every payload read by 20 bytes nobody reads at lookup time.
///
/// ## The trade, stated before it is measured
///
/// * **Full-row access should win** — one stride instead of four.
/// * **Column scans should lose, and lose badly.** `count_type` reads one byte
///   per row; the columnar arms stream `n` bytes to answer it, this arm drags
///   `33n` through cache to use `n`. `sum_uncompressed` reads 8 of every 33
///   instead of 8 of every 8.
/// * It is **no longer typed Arrow columns**. A `FixedSizeBinary(33)` is
///   opaque to DuckDB / Polars / DataFusion, which can query the other two arms
///   directly off the IPC bytes. That is a real cost and it is not a
///   performance one.
pub struct PackedPayload {
    oids: OidResolver,
    ipc: Buffer,
    oid: FixedSizeBinaryArray,
    payload: FixedSizeBinaryArray,
    rows: usize,
}

/// Column name of the single packed payload column.
pub const COL_PACKED: &str = "packed";

impl PackedPayload {
    /// [`ObjectIndex::build`] with the `stree` section's [`OidLayout`] chosen
    /// explicitly — the whole apparatus of the alignment experiment
    /// (`examples/oid_align_bench.rs`).
    ///
    /// It lives on this arm alone rather than on the trait because
    /// `ordinals_batch` is **the same code in all three arms** (they share one
    /// [`OidResolver`]), so a second arm would add a second Arrow payload to
    /// keep resident and would measure nothing new. This is the arm the payload
    /// sweep picked.
    pub fn build_with_oid_layout(entries: &[IndexEntry], layout: OidLayout) -> Result<Self> {
        let order = oid_order(entries);
        let hash = validate(entries, &order)?;
        let oid_len = hash.oid_len();
        let oid_arr = oid_column(entries, &order, oid_len);
        let packed = packed_column(entries, &order);
        let oids = OidResolver::build_with(entries, &order, hash, layout)?;
        Self::assemble(oids, oid_arr, packed, oid_len, order.len())
    }

    /// The cache-line phase of this index's `stree` keyspace — 0 for
    /// [`OidLayout::Aligned64`]. The bench asserts on it before quoting a
    /// number, because two arms that landed on the same phase would be one arm
    /// measured twice.
    pub fn keyspace_phase(&self) -> usize {
        self.oids.tree.keyspace_phase()
    }

    /// Everything after the oid resolver: framing the two columns into one IPC
    /// stream and decoding it back zero-copy. Shared with `build` so the two
    /// cannot drift (LAW 5) — the only difference between them must be the
    /// `stree` layout, or the experiment is measuring two indexes.
    fn assemble(
        oids: OidResolver,
        oid_arr: FixedSizeBinaryArray,
        packed: FixedSizeBinaryArray,
        oid_len: usize,
        rows: usize,
    ) -> Result<Self> {
        let schema: SchemaRef = Arc::new(Schema::new(vec![
            oid_field(oid_len),
            Field::new(COL_PACKED, DataType::FixedSizeBinary(PACKED_LEN as i32), false),
        ]));
        let batch = RecordBatch::try_new(schema, vec![Arc::new(oid_arr), Arc::new(packed)])?;
        let (ipc, r) = decode_ipc(&to_ipc(&batch)?)?;
        Ok(Self { oids, ipc, oid: col(&r, COL_OID)?, payload: col(&r, COL_PACKED)?, rows })
    }

    pub fn oid_column(&self) -> &FixedSizeBinaryArray {
        &self.oid
    }

    pub fn column_is_inside_ipc(&self) -> bool {
        inside(&self.ipc, self.oid.value_data()) && inside(&self.ipc, self.payload.value_data())
    }

    /// One buffer read, one stride.
    #[inline]
    fn row_at(&self, ordinal: u32) -> IndexRow {
        let r = self.payload.value(ordinal as usize);
        IndexRow {
            ordinal,
            offset: le64(r, P_OFFSET),
            len: le64(r, P_LEN),
            obj_type: ObjType::from_code(r[P_TYPE]).unwrap_or(ObjType::Blob),
            uncompressed_size: le64(r, P_SIZE),
            delta_base: le64(r, P_DELTA_BASE),
        }
    }

    /// The same one buffer read — a partial row costs a packed layout exactly
    /// what a full row costs, which is half the point of the trade.
    #[inline]
    fn extent_at(&self, ordinal: u32) -> (u64, u64) {
        let r = self.payload.value(ordinal as usize);
        (le64(r, P_OFFSET), le64(r, P_LEN))
    }
}

impl ObjectIndex for PackedPayload {
    fn build(entries: &[IndexEntry]) -> Result<Self> {
        let order = oid_order(entries);
        let hash = validate(entries, &order)?;
        let oid_len = hash.oid_len();
        let oid_arr = oid_column(entries, &order, oid_len);
        let packed = packed_column(entries, &order);
        let oids = OidResolver::build(entries, &order, hash)?;
        Self::assemble(oids, oid_arr, packed, oid_len, order.len())
    }

    fn lookup(&self, oid: &[u8]) -> Option<IndexRow> {
        self.oids.ordinal(oid).map(|o| self.row_at(o))
    }

    fn lookup_batch(&self, oids: &[&[u8]]) -> Vec<Option<IndexRow>> {
        self.oids.ordinals(oids).into_iter().map(|o| o.map(|o| self.row_at(o))).collect()
    }

    fn ordinals_batch(&self, oids: &[&[u8]]) -> Vec<Option<u32>> {
        self.oids.ordinals(oids)
    }

    fn extents_batch(&self, oids: &[&[u8]]) -> Vec<Option<(u64, u64)>> {
        self.oids.ordinals(oids).into_iter().map(|o| o.map(|o| self.extent_at(o))).collect()
    }

    /// Strided: 8 useful bytes out of every 25 touched.
    fn sum_uncompressed(&self) -> u64 {
        let d = self.payload.value_data();
        let mut acc = 0u64;
        let mut i = P_SIZE;
        while i + 8 <= d.len() {
            acc = acc.wrapping_add(le64(d, i));
            i += PACKED_LEN;
        }
        acc
    }

    /// Strided: 1 useful byte out of every 25 touched.
    fn count_type(&self, t: ObjType) -> usize {
        let c = t.code();
        let d = self.payload.value_data();
        let mut n = 0usize;
        let mut i = P_TYPE;
        while i < d.len() {
            if d[i] == c {
                n += 1;
            }
            i += PACKED_LEN;
        }
        n
    }

    fn name(&self) -> &'static str {
        "PackedPayload"
    }

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

    fn ipc_bytes(&self) -> usize {
        self.ipc.len()
    }

    fn resident_bytes(&self) -> usize {
        self.ipc_bytes() + self.oids.section_bytes
    }
}

// ── deterministic workload generation, shared by tests and the bench ──────────

/// splitmix64. Seeded, so a bench run is reproducible and a historized series is
/// comparable at all.
pub struct Rng(pub u64);

impl Rng {
    pub fn next_u64(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        z ^ (z >> 31)
    }

    pub fn fill(&mut self, out: &mut [u8]) {
        for c in out.chunks_mut(8) {
            let w = self.next_u64().to_le_bytes();
            let n = c.len();
            c.copy_from_slice(&w[..n]);
        }
    }
}

/// `n` distinct entries with uniformly random oids.
///
/// Uniform randomness is the property under test, not a convenience: real oids
/// are hashes and share no prefixes, so a generator with structure would give
/// the stree an unrepresentative keyspace.
///
/// **Every `OfsDelta` entry carries a non-zero `delta_base`** — the offset of
/// the entry immediately before it, which is a real row of the same workload —
/// and every other entry carries `0`. LAW 2's identity-value trap is the whole
/// reason: a generator that left `delta_base` at `0` everywhere would let a
/// layout that never wrote the column, or read it from the wrong stride, pass
/// every comparison in this module. It is derived from `out.last()` rather than
/// from `rng`, so oids, offsets, lengths and types are bit-identical to what
/// this generator produced before the column existed and no earlier figure is
/// invalidated by the workload changing under it.
pub fn synthetic_entries(n: usize, oid_len: usize, seed: u64) -> Vec<IndexEntry> {
    let mut rng = Rng(seed);
    let mut seen = std::collections::HashSet::with_capacity(n * 2);
    let mut out: Vec<IndexEntry> = Vec::with_capacity(n);
    let mut off = 12u64; // past a pack header
    while out.len() < n {
        let mut oid = vec![0u8; oid_len];
        rng.fill(&mut oid);
        if !seen.insert(oid.clone()) {
            continue;
        }
        // Length distribution roughly like a real pack: mostly small, a long
        // tail. The exact shape does not affect a point lookup, but it keeps
        // the u64 columns from being all-identical, which would let a compressor
        // or a branch predictor flatter one arm over the other.
        let len = 32 + (rng.next_u64() % 4096);
        let ty = ObjType::ALL[(rng.next_u64() % 6) as usize];
        // An ofs-delta's base is the entry before it: always an offset that some
        // row of this same workload really starts at, never 0, and never a
        // forward reference. A ref-delta's base is named by oid and has no
        // offset until it is resolved, so it records the 0 sentinel — as does
        // every whole object.
        let delta_base = match (ty, out.last()) {
            (ObjType::OfsDelta, Some(prev)) => prev.offset,
            _ => 0,
        };
        out.push(IndexEntry {
            oid,
            offset: off,
            len,
            obj_type: ty,
            uncompressed_size: len * (1 + rng.next_u64() % 5),
            delta_base,
        });
        off += len;
    }
    out
}


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

    /// All three arms over the same entries. Every semantic test runs against
    /// the triple, because "the three layouts are one index" is the claim the
    /// whole comparison rests on.
    fn arms(entries: &[IndexEntry]) -> (FourTables, OneTableFourColumns, PackedPayload) {
        (
            FourTables::build(entries).expect("A builds"),
            OneTableFourColumns::build(entries).expect("B builds"),
            PackedPayload::build(entries).expect("C builds"),
        )
    }

    /// The core correctness claim: **the three layouts are the same index**.
    ///
    /// Asserted on applied output — the five facts of every row, plus the
    /// ordinal — for every present oid, for absent oids, and through the
    /// serial, batch, extent-only and ordinal-only paths. A row-count or an
    /// `is_some()` check would pass for three indexes that disagreed on every
    /// value.
    ///
    /// Seen RED by changing `ColumnarPayload::row_at` to read `self.len.value(i)`
    /// for `offset`: "layouts disagree on 80313d462e6994e9e819193e6fdbd5f8390e92e3
    ///   left: IndexRow { ordinal: 259, offset: 344, len: 344, .. }
    ///  right: IndexRow { ordinal: 259, offset: 12, len: 344, .. }".
    /// Restored.
    ///
    /// Seen RED a second time, for the packed arm specifically, by swapping the
    /// `len` and `uncompressed_size` writes in `packed_column` only, so the
    /// writer and the reader disagree about the record layout:
    /// "C disagrees with A on 80313d462e6994e9e819193e6fdbd5f8390e92e3
    ///   left: IndexRow { offset: 12, len: 344, uncompressed_size: 1720 }
    ///  right: IndexRow { offset: 12, len: 1720, uncompressed_size: 344 }".
    /// Restored. Note that A and B stayed green throughout — only a guard that
    /// compares the packed arm against them can see this class of bug.
    ///
    /// Seen RED a third time, when `delta_base` was added, by dropping
    /// [`FourTables`] read `COL_LEN` into `ColumnarPayload::delta_base` — the
    /// single most plausible way to wire a new column in wrong, since both are
    /// `u64` columns of the same section: "A and B disagree on
    /// 80313d462e6994e9e819193e6fdbd5f8390e92e3 / left: IndexRow { ordinal: 259,
    /// offset: 12, len: 344, obj_type: Tree, uncompressed_size: 1720,
    /// **delta_base: 344** } / right: IndexRow { … **delta_base: 0** }". B and C
    /// were right and A was wrong, and only the row-for-row comparison said so.
    /// Restored.
    #[test]
    fn the_three_layouts_return_identical_rows() {
        for &oid_len in &[20usize, 32] {
            let entries = synthetic_entries(500, oid_len, 0xA11CE);
            let (a, b, c) = arms(&entries);
            assert_eq!(a.len(), 500);
            assert_eq!(b.len(), 500);
            assert_eq!(c.len(), 500);

            // Not a blind guard: the workload has to carry the column at
            // something other than its identity value, or every arm agreeing on
            // `delta_base: 0` would prove nothing about `delta_base` at all.
            let with_base = entries.iter().filter(|e| e.delta_base != 0).count();
            assert!(
                with_base >= 50,
                "only {with_base} of 500 entries carry a non-zero delta_base — this guard would \
                 sit on the identity value and could not see a column that was never written"
            );

            let mut hits = 0usize;
            for e in &entries {
                let ra = a.lookup(&e.oid).unwrap_or_else(|| {
                    panic!("{} missed {}", a.name(), hex::encode(&e.oid))
                });
                let rb = b.lookup(&e.oid).unwrap_or_else(|| {
                    panic!("{} missed {}", b.name(), hex::encode(&e.oid))
                });
                let rc = c.lookup(&e.oid).unwrap_or_else(|| {
                    panic!("{} missed {}", c.name(), hex::encode(&e.oid))
                });
                assert_eq!(ra, rb, "A and B disagree on {}", hex::encode(&e.oid));
                assert_eq!(
                    ra,
                    rc,
                    "C disagrees with A on {}",
                    hex::encode(&e.oid)
                );
                // …and all three agree with the input, not just with each other.
                assert_eq!(rc.offset, e.offset);
                assert_eq!(rc.len, e.len);
                assert_eq!(rc.obj_type, e.obj_type);
                assert_eq!(rc.uncompressed_size, e.uncompressed_size);
                assert_eq!(
                    rc.delta_base,
                    e.delta_base,
                    "delta_base did not survive C for {}",
                    hex::encode(&e.oid)
                );
                assert_eq!(ra.delta_base, e.delta_base, "delta_base did not survive A");
                assert_eq!(rb.delta_base, e.delta_base, "delta_base did not survive B");
                hits += 1;
            }
            assert_eq!(hits, 500, "every entry must resolve");

            // Absent oids: same answer everywhere, and that answer is None.
            let absent = synthetic_entries(200, oid_len, 0xBEEF_0000);
            for e in &absent {
                assert_eq!(a.lookup(&e.oid), None);
                assert_eq!(b.lookup(&e.oid), None);
                assert_eq!(c.lookup(&e.oid), None);
            }

            // Every batch path, on a mix, positionally.
            let mut q: Vec<&[u8]> = Vec::new();
            for (i, e) in entries.iter().enumerate() {
                q.push(&e.oid);
                if i < absent.len() {
                    q.push(&absent[i].oid);
                }
            }
            let ba = a.lookup_batch(&q);
            let bb = b.lookup_batch(&q);
            let bc = c.lookup_batch(&q);
            assert_eq!(ba.len(), q.len());
            assert_eq!(ba, bb, "A/B batch paths disagree at oid_len {oid_len}");
            assert_eq!(ba, bc, "A/C batch paths disagree at oid_len {oid_len}");
            let n_hits = ba.iter().filter(|r| r.is_some()).count();
            assert_eq!(n_hits, 500, "expected exactly the 500 present oids to hit");
            for (i, r) in ba.iter().enumerate() {
                assert_eq!(*r, c.lookup(q[i]), "C batch/serial disagree at {i}");
            }

            // The partial-row and ordinal-only paths agree with the full row.
            let ea = a.extents_batch(&q);
            let ec = c.extents_batch(&q);
            assert_eq!(ea, ec, "extent paths disagree");
            let oa = a.ordinals_batch(&q);
            let oc = c.ordinals_batch(&q);
            assert_eq!(oa, oc, "ordinal paths disagree");
            for i in 0..q.len() {
                assert_eq!(ea[i], ba[i].map(|r| (r.offset, r.len)), "extent != row at {i}");
                assert_eq!(oa[i], ba[i].map(|r| r.ordinal), "ordinal != row at {i}");
            }
        }
    }

    /// **`delta_base` is an offset that locates a row of this very table**, in
    /// all three arms — which is the property an ordinal could not have.
    ///
    /// Read back through the index (never from the input entries), every
    /// non-zero `delta_base` is looked up against the set of `offset`s the index
    /// itself reports, and it has to land on one, earlier in the archive than
    /// the delta that names it. `offset` and `delta_base` are the same
    /// coordinate space, and this is the assertion that says so.
    ///
    /// Seen RED by making `synthetic_entries` write `prev.offset + 1` as the
    /// delta base — a value one byte off a real entry boundary, which is
    /// precisely how an off-by-one in a rebase or in a varint would look:
    /// "A: delta_base 4601 of ordinal 1256 lands on no entry offset in this
    /// index". Restored to `prev.offset`.
    ///
    /// Seen RED a second time, on the ordinal question itself, by writing the
    /// base's *row index* into the column instead of its offset:
    /// "A: delta_base 2 of ordinal 1256 lands on no entry offset in this index"
    /// — a small number that is a perfectly valid row address and an invalid
    /// archive address, which is §13's decision failing loudly rather than
    /// silently. Restored.
    #[test]
    fn delta_base_locates_a_real_entry_in_every_arm() {
        let entries = synthetic_entries(2000, 20, 0xDE17A);
        let (a, b, c) = arms(&entries);

        // The offsets this index reports, taken from the index and not from the
        // input: `lookup` of every stored oid.
        let offsets: std::collections::HashSet<u64> =
            entries.iter().filter_map(|e| a.lookup(&e.oid)).map(|r| r.offset).collect();
        assert_eq!(offsets.len(), 2000, "every row must report a distinct offset");

        let arms: [(&str, &dyn ObjectIndex); 3] = [("A", &a), ("B", &b), ("C", &c)];
        let mut checked = 0usize;
        for (name, idx) in arms {
            let mut with_base = 0usize;
            for e in &entries {
                let row = idx.lookup(&e.oid).expect("stored oid resolves");
                if row.delta_base == 0 {
                    assert_ne!(
                        row.obj_type,
                        ObjType::OfsDelta,
                        "{name}: an ofs-delta with no recorded base is a row that cannot be \
                         resolved at all"
                    );
                    continue;
                }
                with_base += 1;
                assert!(
                    offsets.contains(&row.delta_base),
                    "{name}: delta_base {} of ordinal {} lands on no entry offset in this index",
                    row.delta_base,
                    row.ordinal
                );
                assert!(
                    row.delta_base < row.offset,
                    "{name}: delta_base {} is not earlier in the archive than the delta at {}",
                    row.delta_base,
                    row.offset
                );
            }
            assert!(
                with_base > 100,
                "{name}: only {with_base} of 2000 rows carried a base — nothing was proven"
            );
            checked += with_base;
        }
        assert!(checked > 300, "three arms must each have checked real bases");
    }

    /// The two column scans return the same answer from all three arms, and
    /// that answer is the one computed straight from the input entries.
    ///
    /// This is the guard that makes the scan half of the benchmark meaningful:
    /// a strided reader that skipped rows would be very fast and very wrong.
    ///
    /// Seen RED by advancing `PackedPayload::sum_uncompressed` by `PACKED_LEN + 8`
    /// instead of `PACKED_LEN`: "C sum_uncompressed: left 8826373087920709042,
    /// right 12349770". The stride slipped out of phase, so it summed bytes
    /// straddling field boundaries — a fast, wrong scan that no timing
    /// assertion would ever have noticed. Restored.
    #[test]
    fn column_scans_agree_across_arms_and_with_the_input() {
        let entries = synthetic_entries(2000, 20, 0x5CA7);
        let (a, b, c) = arms(&entries);

        let want: u64 = entries.iter().map(|e| e.uncompressed_size).sum();
        assert_eq!(a.sum_uncompressed(), want, "A sum_uncompressed");
        assert_eq!(b.sum_uncompressed(), want, "B sum_uncompressed");
        assert_eq!(c.sum_uncompressed(), want, "C sum_uncompressed");
        assert!(want > 0, "the workload must actually carry sizes");

        let mut total = 0usize;
        for t in ObjType::ALL {
            let want = entries.iter().filter(|e| e.obj_type == t).count();
            assert_eq!(a.count_type(t), want, "A count_type({})", t.as_str());
            assert_eq!(b.count_type(t), want, "B count_type({})", t.as_str());
            assert_eq!(c.count_type(t), want, "C count_type({})", t.as_str());
            assert!(want > 0, "{} must appear in the workload", t.as_str());
            total += want;
        }
        assert_eq!(total, entries.len(), "the six types must partition the index");
    }

    /// The packed record is 33 bytes laid out exactly as documented, read
    /// straight out of the IPC buffer rather than through the accessor that is
    /// under test. A layout that changed silently would still round-trip
    /// through its own reader; this pins it to the bytes.
    ///
    /// Seen RED by moving the type byte from offset 16 to offset 24 in
    /// `packed_column`: "row 0 byte 16 is 0 but the type code is 6". Restored.
    ///
    /// Seen RED again for the fifth field, by writing `e.offset` where
    /// `packed_column` writes `e.delta_base`: "row 0 bytes 25..33 must be the
    /// delta base / left: 368 / right: 12". Restored. Writing the *offset*
    /// there is the failure mode worth catching: it is a plausible archive
    /// offset, it is even a real entry boundary, so nothing downstream would
    /// look odd — only a comparison against the input entry tells the two
    /// apart.
    #[test]
    fn the_packed_record_is_the_documented_33_bytes() {
        let entries = synthetic_entries(64, 20, 0x9F);
        let c = PackedPayload::build(&entries).unwrap();
        assert_eq!(PACKED_LEN, 33);
        assert_eq!(PACKED_LEN, 8 + 8 + 1 + 8 + 8, "offset+len+type+size+delta_base");

        let mut sorted: Vec<&IndexEntry> = entries.iter().collect();
        sorted.sort_by(|x, y| x.oid.cmp(&y.oid));
        let d = c.payload.value_data();
        assert_eq!(d.len(), 64 * PACKED_LEN, "payload column is not 33 bytes per row");
        assert!(
            sorted.iter().filter(|e| e.delta_base != 0).count() >= 4,
            "the fixture must carry real delta bases or bytes 25..33 are all zero"
        );

        for (i, e) in sorted.iter().enumerate() {
            let r = &d[i * PACKED_LEN..(i + 1) * PACKED_LEN];
            assert_eq!(
                u64::from_le_bytes(r[0..8].try_into().unwrap()),
                e.offset,
                "row {i} bytes 0..8 must be the offset"
            );
            assert_eq!(
                u64::from_le_bytes(r[8..16].try_into().unwrap()),
                e.len,
                "row {i} bytes 8..16 must be the len"
            );
            assert_eq!(
                r[16],
                e.obj_type.code(),
                "row {i} byte 16 is {} but the type code is {}",
                r[16],
                e.obj_type.code()
            );
            assert_eq!(
                u64::from_le_bytes(r[17..25].try_into().unwrap()),
                e.uncompressed_size,
                "row {i} bytes 17..25 must be the uncompressed size"
            );
            assert_eq!(
                u64::from_le_bytes(r[25..33].try_into().unwrap()),
                e.delta_base,
                "row {i} bytes 25..33 must be the delta base"
            );
        }
    }

    /// The whole premise of the third arm, asserted as a byte count rather than
    /// as an argument: a full-row fetch touches **one** payload buffer of 33
    /// bytes per row, where the columnar arms touch five buffers whose bases are
    /// megabytes apart.
    ///
    /// Seen RED by asserting the columnar arm's payload buffers were within 25
    /// bytes of each other: "offset and size buffers are 1737664 bytes apart,
    /// not adjacent" at 100 000 rows. That distance is the fact the packed arm
    /// exists to change. Restored to assert the true distances.
    #[test]
    fn a_packed_row_is_one_stride_and_a_columnar_row_is_five() {
        let entries = synthetic_entries(100_000, 20, 0x0FF5);
        let (_, b, c) = arms(&entries);

        // Columnar: five payload buffers, and consecutive facts of ONE row are
        // ~800 kB apart because each column is 100000 × 8 bytes long.
        let base = |s: &[u8]| s.as_ptr() as usize;
        let off = base(b.cols.offset.values().inner().as_slice());
        let len = base(b.cols.len.values().inner().as_slice());
        let size = base(b.cols.size.values().inner().as_slice());
        let dbase = base(b.cols.delta_base.values().inner().as_slice());
        assert!(
            len.abs_diff(off) >= 800_000,
            "offset and len columns are only {} bytes apart — this arm is supposed to be \
             columnar",
            len.abs_diff(off)
        );
        assert!(size.abs_diff(off) >= 800_000);
        assert!(
            dbase.abs_diff(off) >= 800_000 && dbase.abs_diff(size) >= 800_000,
            "delta_base is {} bytes from offset and {} from size — the fifth fact must be its \
             own stride, not a field inside another column",
            dbase.abs_diff(off),
            dbase.abs_diff(size)
        );

        // Packed: the five facts of one row are inside 33 consecutive bytes.
        let d = c.payload.value_data();
        assert_eq!(d.len(), 100_000 * PACKED_LEN);
        let row7 = &d[7 * PACKED_LEN..8 * PACKED_LEN];
        let r = c.lookup(&entries.iter().min_by_key(|e| e.oid.clone()).unwrap().oid);
        assert!(r.is_some(), "the lexicographically first oid must resolve");
        // Every fact of row 7 is readable from those 33 bytes alone.
        let from_bytes = IndexRow {
            ordinal: 7,
            offset: u64::from_le_bytes(row7[0..8].try_into().unwrap()),
            len: u64::from_le_bytes(row7[8..16].try_into().unwrap()),
            obj_type: ObjType::from_code(row7[16]).unwrap(),
            uncompressed_size: u64::from_le_bytes(row7[17..25].try_into().unwrap()),
            delta_base: u64::from_le_bytes(row7[25..33].try_into().unwrap()),
        };
        assert_eq!(
            from_bytes,
            c.row_at(7),
            "one 33-byte slice must carry the whole row"
        );
    }

    /// The ordinal is the oid-lexicographic rank in **all three** arms, and it
    /// is the join key `FourTables` relies on. Asserted against an
    /// independently sorted copy of the input rather than against another arm.
    ///
    /// Seen RED by making `oid_order` sort by `offset` instead of by `oid`:
    /// "A ordinal is not the rank — left: 206, right: 0" on the first row.
    /// Restored.
    #[test]
    fn ordinals_are_the_oid_lexicographic_rank_in_every_arm() {
        let entries = synthetic_entries(300, 20, 7);
        let (a, b, c) = arms(&entries);
        let mut sorted: Vec<&IndexEntry> = entries.iter().collect();
        sorted.sort_by(|x, y| x.oid.cmp(&y.oid));
        for (rank, e) in sorted.iter().enumerate() {
            let ra = a.lookup(&e.oid).unwrap();
            let rb = b.lookup(&e.oid).unwrap();
            let rc = c.lookup(&e.oid).unwrap();
            assert_eq!(ra.ordinal as usize, rank, "A ordinal is not the rank");
            assert_eq!(rb.ordinal as usize, rank, "B ordinal is not the rank");
            assert_eq!(rc.ordinal as usize, rank, "C ordinal is not the rank");
            // The oid column of each arm, read at that ordinal, is that oid.
            assert_eq!(a.oid_column().value(rank), e.oid.as_slice());
            assert_eq!(b.oid_column().value(rank), e.oid.as_slice());
            assert_eq!(c.oid_column().value(rank), e.oid.as_slice());
        }
    }

    /// Zero-copy, asserted by pointer containment rather than by hope, in all
    /// three arms.
    ///
    /// `decode_ipc` uses `with_require_alignment(true)`, so a misaligned buffer
    /// is an error, not a silent re-allocation. This proves the positive side:
    /// each array's bytes are *inside* the IPC buffer it came from.
    ///
    /// Seen RED by swapping `decode_ipc_buffer`'s `StreamDecoder` for the
    /// high-level `StreamReader` over a `Cursor` (which owns its own
    /// allocations): "FourTables columns were copied out of IPC". Restored.
    ///
    /// A weaker edit did **not** turn it red and is worth recording: replacing
    /// the `MutableBuffer` copy with `Buffer::from_vec(bytes.to_vec())` left the
    /// test green, because glibc happened to hand back an 8-aligned allocation
    /// for a ~57 kB `Vec`. Alignment by luck is not alignment, which is what
    /// [`require_alignment_is_load_bearing`] pins down separately.
    #[test]
    fn every_column_is_a_zero_copy_view_into_its_ipc_section() {
        let entries = synthetic_entries(1000, 32, 11);
        let (a, b, c) = arms(&entries);
        assert!(a.column_is_inside_ipc(), "FourTables columns were copied out of IPC");
        assert!(b.column_is_inside_ipc(), "OneTable columns were copied out of IPC");
        assert!(c.column_is_inside_ipc(), "PackedPayload columns were copied out of IPC");

        // And the payload really is there: 1000 × 32 oid bytes + 1000 × 8 for
        // each of offset/len/size/delta_base + 1000 × 1 type = 65000 bytes
        // minimum.
        assert!(
            b.ipc_bytes() >= 65_000,
            "one-table section is {} bytes, too small to hold the payload",
            b.ipc_bytes()
        );
        assert!(a.ipc_bytes() >= 65_000);
        assert!(c.ipc_bytes() >= 65_000);
    }

    /// `with_require_alignment(true)` is the thing that makes "zero-copy" a
    /// contract instead of a hope: with it off, arrow silently allocates a fresh
    /// aligned buffer and copies, and the only symptom is that opening a large
    /// index got slower and doubled its peak memory.
    ///
    /// The same IPC bytes are decoded twice — once from a 64-byte-aligned
    /// buffer, once from the identical bytes sitting at offset 4 of the same
    /// allocation. The first must succeed and be a view; the second must be
    /// **refused**.
    ///
    /// Seen RED by dropping `.with_require_alignment(true)` from
    /// `decode_ipc_buffer`: the misaligned decode returned `Ok` and the test
    /// panicked with "a misaligned buffer must be refused, not silently
    /// copied". Restored.
    #[test]
    fn require_alignment_is_load_bearing() {
        let entries = synthetic_entries(64, 20, 77);
        let order = oid_order(&entries);
        let c = columns(&entries, &order, 20);
        let batch = RecordBatch::try_new(
            extent_schema(),
            vec![Arc::new(c.offset), Arc::new(c.len), Arc::new(c.delta_base)],
        )
        .unwrap();
        let ipc = to_ipc(&batch).unwrap();

        // Aligned: 64 bytes of padding then the stream, sliced back to the
        // stream's start — the pointer is 64-aligned.
        let mut mb = MutableBuffer::with_capacity(64 + ipc.len());
        mb.extend_from_slice(&[0u8; 64]);
        mb.extend_from_slice(&ipc);
        let padded: Buffer = mb.into();
        let (owner, ok) = decode_ipc_buffer(padded.slice(64)).expect("aligned decode must work");
        assert_eq!(ok.num_rows(), 64, "the aligned decode must yield all 64 rows");
        assert!(inside(&owner, ok.column(0).to_data().buffers()[0].as_slice()));

        // Misaligned by 4: byte-identical stream, 4-byte-offset pointer.
        let mut mb = MutableBuffer::with_capacity(4 + ipc.len());
        mb.extend_from_slice(&[0u8; 4]);
        mb.extend_from_slice(&ipc);
        let skewed: Buffer = mb.into();
        let err = match decode_ipc_buffer(skewed.slice(4)) {
            Ok(_) => panic!("a misaligned buffer must be refused, not silently copied"),
            Err(e) => e.to_string(),
        };
        assert!(
            err.contains("Misaligned"),
            "the refusal must name the misalignment, got: {err}"
        );
    }

    /// Four sections cost strictly more IPC framing than one, and the amount is
    /// asserted as a byte count, not as "greater than".
    ///
    /// Each Arrow IPC stream carries a schema message, a record-batch message
    /// header and an end-of-stream marker. Three extra copies of that is the
    /// entire structural overhead of layout A, and on a tiny index it dominates.
    ///
    /// Seen RED by asserting `>= 900`: "expected ≥900 bytes of extra framing
    /// for three extra sections, got 728 (A=4704 B=3976)". The bound below is
    /// the one the measurement supports — 728 bytes, ~243 per extra section,
    /// which is the schema + batch-header + EOS framing and not payload.
    #[test]
    fn four_sections_pay_three_extra_ipc_frames() {
        let entries = synthetic_entries(64, 20, 3);
        let (a, b, _) = arms(&entries);
        let extra = a.ipc_bytes() as i64 - b.ipc_bytes() as i64;
        assert!(
            (600..1200).contains(&extra),
            "expected 600..1200 bytes of extra framing for three extra sections, got {extra} \
             (A={} B={})",
            a.ipc_bytes(),
            b.ipc_bytes()
        );
        // The four sections are separately sized and the oid one is the biggest.
        let lens = a.ipc_section_lens();
        assert_eq!(lens.len(), 4);
        assert!(lens[0] > lens[2], "oid section {} must exceed type section {}", lens[0], lens[2]);
    }

    /// The packed arm stores the same *payload* bytes — 33 per row against
    /// 8 + 8 + 1 + 8 + 8 — so nothing in the timing comparison is a
    /// memory-footprint effect in disguise. Its IPC **section** is nonetheless
    /// smaller, and the amount is asserted as a scaling law rather than as a
    /// constant, at two sizes, so it is attributed rather than hand-waved.
    ///
    /// Four fewer columns is four fewer per-column IPC buffers, and the
    /// saving grows linearly with row count at about `4 · n/8` bytes. It was
    /// `3 · n/8` — 38 016 B at 100 000 rows — before `delta_base` gave the
    /// columnar arm a fifth payload column. That is the only footprint
    /// difference between the three arms.
    ///
    /// Seen RED by asserting the two sections were within 4096 bytes of each
    /// other: "packed payload is 4525512 bytes against 4563528 columnar", which
    /// is what sent me to count buffers instead of guessing. Seen RED a second
    /// time by asserting the saving was *constant* across the two sizes:
    /// "saving did not scale: 38016 at 100000 rows, 75456 at 200000". Seen RED
    /// a third time by leaving the `3 · n/8` bound in place after the fifth
    /// column landed: "at 100000 rows the saving is 50560 B, not the ~37500 B
    /// that four fewer columns accounts for" — 50 560 B is `4 · n/8` plus
    /// framing, so the bound is counting real buffers rather than tracking a
    /// moving target.
    #[test]
    fn the_packed_arm_holds_the_same_payload_but_a_smaller_section() {
        let mut savings = Vec::new();
        for &n in &[100_000usize, 200_000] {
            let entries = synthetic_entries(n, 20, 0xBEE5);
            let (_, b, c) = arms(&entries);

            // The payload itself is byte-for-byte the same size.
            let payload_bytes = n * (8 + 8 + 1 + 8 + 8);
            assert_eq!(c.payload.value_data().len(), payload_bytes);
            assert_eq!(c.payload.value_data().len(), n * PACKED_LEN);

            let saving = b.ipc_bytes() as i64 - c.ipc_bytes() as i64;
            assert!(
                saving > 0,
                "the two-column section ({}) must not be larger than the six-column one ({})",
                c.ipc_bytes(),
                b.ipc_bytes()
            );
            // Four fewer columns, at roughly n/8 bytes of per-column buffer each.
            let expect = 4 * (n as i64) / 8;
            assert!(
                (expect..expect + 4096).contains(&saving),
                "at {n} rows the saving is {saving} B, not the ~{expect} B that four fewer \
                 columns accounts for"
            );
            savings.push(saving);
        }
        assert!(
            savings[1] > savings[0] * 3 / 2,
            "saving did not scale: {} at 100000 rows, {} at 200000",
            savings[0],
            savings[1]
        );
    }

    /// LAW 2 — the 8-byte prefix collision, carried through all three arms.
    ///
    /// Two oids sharing their first eight bytes share one stree key, so the tree
    /// alone cannot tell them apart. Every arm must still return each oid's own
    /// four facts, and a third oid on the same prefix that was never inserted
    /// must miss.
    ///
    /// Seen RED by replacing `OidResolver::ordinal`'s verified `tree.lookup`
    /// with the unverified `tree.candidate_run(key_for_oid(oid)).start` — i.e.
    /// trusting the 8-byte prefix: "collision resolved to the wrong row —
    /// left: 1000, right: 2000". Both colliding oids came back as the first
    /// candidate. Restored.
    #[test]
    fn a_prefix_collision_resolves_to_the_right_row_in_every_arm() {
        let prefix = [0xde, 0xad, 0xbe, 0xef, 0x01, 0x02, 0x03, 0x04];
        // The two colliding entries carry *different* delta bases, so a column
        // read at the wrong ordinal shows up here too and not only in `offset`.
        let mk = |last: u8, off: u64, ty: ObjType| {
            let mut oid = vec![0u8; 20];
            oid[..8].copy_from_slice(&prefix);
            oid[8] = last;
            IndexEntry {
                oid,
                offset: off,
                len: 10,
                obj_type: ty,
                uncompressed_size: off * 2,
                delta_base: off / 2,
            }
        };
        let mut entries = vec![mk(0xaa, 1000, ObjType::Commit), mk(0xbb, 2000, ObjType::OfsDelta)];
        entries.extend(synthetic_entries(200, 20, 99));
        let (a, b, c) = arms(&entries);

        for (last, off, ty) in [(0xaau8, 1000u64, ObjType::Commit), (0xbb, 2000, ObjType::OfsDelta)]
        {
            let oid = mk(last, off, ty).oid;
            let ra = a.lookup(&oid).expect("colliding oid must resolve in A");
            let rb = b.lookup(&oid).expect("colliding oid must resolve in B");
            let rc = c.lookup(&oid).expect("colliding oid must resolve in C");
            assert_eq!(ra, rb);
            assert_eq!(ra, rc);
            assert_eq!(ra.offset, off, "collision resolved to the wrong row");
            assert_eq!(ra.obj_type, ty);
            assert_eq!(ra.delta_base, off / 2, "collision resolved to the wrong delta base");
        }
        let never = mk(0xcc, 0, ObjType::Blob).oid;
        assert_eq!(a.lookup(&never), None, "unstored oid on a colliding prefix must miss");
        assert_eq!(b.lookup(&never), None);
        assert_eq!(c.lookup(&never), None);
    }

    /// All six pack type codes survive the round trip in every arm, including
    /// the two delta kinds that are the reason this fact is stored at all.
    ///
    /// Seen RED by mapping `ObjType::RefDelta` to code 6 in `code()`, colliding
    /// with `OfsDelta`: "type did not survive the column — left: OfsDelta,
    /// right: RefDelta". Restored.
    #[test]
    fn all_six_pack_types_round_trip_including_the_deltas() {
        let entries: Vec<IndexEntry> = ObjType::ALL
            .iter()
            .enumerate()
            .map(|(i, &t)| {
                let mut oid = vec![0u8; 32];
                oid[0] = i as u8 * 17;
                oid[31] = i as u8;
                IndexEntry {
                    oid,
                    offset: 100 + i as u64,
                    len: 5,
                    obj_type: t,
                    uncompressed_size: 900 + i as u64,
                    // Only the two delta codes carry a base, which is the
                    // relationship the type column exists to express.
                    delta_base: match t {
                        ObjType::OfsDelta => 100,
                        _ => 0,
                    },
                }
            })
            .collect();
        let (a, b, c) = arms(&entries);
        let mut seen: Vec<ObjType> = Vec::new();
        for e in &entries {
            let ra = a.lookup(&e.oid).unwrap();
            assert_eq!(ra, b.lookup(&e.oid).unwrap());
            assert_eq!(ra, c.lookup(&e.oid).unwrap());
            assert_eq!(ra.obj_type, e.obj_type, "type did not survive the column");
            seen.push(ra.obj_type);
        }
        assert_eq!(seen, ObjType::ALL.to_vec(), "all six codes must be distinct");
        assert_eq!(ObjType::from_code(0), None);
        assert_eq!(ObjType::from_code(5), None, "git leaves 5 unused; it must not be mapped");
        assert_eq!(ObjType::from_code(8), None);
    }

    /// An empty index and a one-row index are clean, not panics, in every arm.
    ///
    /// Seen RED by replacing `validate`'s empty-input `Ok(GitHashKind::Sha1)`
    /// with `bail!("an empty index")`: "A builds: an empty index" — every arm
    /// failed to construct at all. Restored.
    #[test]
    fn degenerate_sizes_are_clean_in_every_arm() {
        let (a, b, c) = arms(&[]);
        assert!(a.is_empty() && b.is_empty() && c.is_empty());
        let probe = vec![7u8; 20];
        assert_eq!(a.lookup(&probe), None);
        assert_eq!(b.lookup(&probe), None);
        assert_eq!(c.lookup(&probe), None);
        assert_eq!(c.lookup_batch(&[&probe[..]]), vec![None]);
        assert_eq!(c.extents_batch(&[&probe[..]]), vec![None]);
        // A scan over an empty index is 0, not a panic or a wrap.
        assert_eq!(c.sum_uncompressed(), 0);
        assert_eq!(c.count_type(ObjType::Blob), 0);

        let one = synthetic_entries(1, 20, 5);
        let (a, b, c) = arms(&one);
        assert_eq!(a.lookup(&one[0].oid).unwrap(), b.lookup(&one[0].oid).unwrap());
        assert_eq!(a.lookup(&one[0].oid).unwrap(), c.lookup(&one[0].oid).unwrap());
        assert_eq!(c.lookup(&one[0].oid).unwrap().offset, one[0].offset);
        assert_eq!(c.sum_uncompressed(), one[0].uncompressed_size);
    }

    /// A wrong-width oid is a miss, never a panic and never a wrong row —
    /// the query side of P-4.
    ///
    /// The width check inside `oid_index::lookup` is only a fast path; what
    /// actually makes this true is the **full-oid compare**, because
    /// `key_for_oid` zero-pads and an 8-byte truncation of a stored oid
    /// therefore lands on that oid's key. Seen RED by the same
    /// unverified-`candidate_run` edit as
    /// [`a_prefix_collision_resolves_to_the_right_row_in_every_arm`]:
    /// "a 8-byte oid must miss — left: Some(IndexRow { ordinal: 47, offset: 12,
    /// len: 1505, obj_type: RefDelta, uncompressed_size: 3010 }), right: None".
    /// Restored.
    #[test]
    fn a_wrong_width_oid_misses_in_every_arm() {
        let entries = synthetic_entries(64, 20, 21);
        let (a, b, c) = arms(&entries);
        let short = &entries[0].oid[..8];
        let mut long = entries[0].oid.clone();
        long.extend_from_slice(&[0u8; 12]);
        for q in [short, &long[..]] {
            assert_eq!(a.lookup(q), None, "a {}-byte oid must miss", q.len());
            assert_eq!(b.lookup(q), None);
            assert_eq!(c.lookup(q), None);
        }
        assert_eq!(a.lookup_batch(&[short, &long]), vec![None, None]);
        assert_eq!(b.lookup_batch(&[short, &long]), vec![None, None]);
        assert_eq!(c.lookup_batch(&[short, &long]), vec![None, None]);
    }

    /// A duplicate oid, or a mix of sha1 and sha256, is refused at build.
    /// Silently keeping one of two identical oids would give the arms different
    /// ordinals for the same object and make every later comparison a lie.
    ///
    /// Seen RED by short-circuiting the duplicate scan in `validate` with
    /// `if false && …`: the build succeeded and the test panicked with
    /// "a duplicate oid must be refused at build". Restored.
    #[test]
    fn build_refuses_duplicates_and_mixed_widths() {
        fn why<T>(r: Result<T>, what: &str) -> String {
            match r {
                Ok(_) => panic!("{what} must be refused at build"),
                Err(e) => e.to_string(),
            }
        }
        let mut dup = synthetic_entries(4, 20, 1);
        dup.push(dup[0].clone());
        let err = why(FourTables::build(&dup), "a duplicate oid");
        assert!(err.contains("duplicate oid"), "{err}");
        assert!(OneTableFourColumns::build(&dup).is_err());
        assert!(PackedPayload::build(&dup).is_err());

        let mut mixed = synthetic_entries(4, 20, 2);
        mixed.push(synthetic_entries(1, 32, 3).pop().unwrap());
        let err = why(PackedPayload::build(&mixed), "a mixed-width index");
        assert!(err.contains("mixed oid widths"), "{err}");
        assert!(FourTables::build(&mixed).is_err());
        assert!(OneTableFourColumns::build(&mixed).is_err());
    }

    /// Every arm is `Send + Sync`, which is what lets a server share one index
    /// across connection handlers. A compile-time assertion, plus an actual
    /// cross-thread lookup so it is not only a type-level claim.
    ///
    /// Seen RED by dropping `Send + Sync` from the `ObjectIndex` supertrait
    /// list: "error[E0277]: `dyn index_layout::ObjectIndex` cannot be shared
    /// between threads safely" and the same for `Send` — the crate stopped
    /// compiling. Restored.
    #[test]
    fn an_index_can_be_shared_across_threads() {
        fn assert_send_sync<T: Send + Sync>() {}
        assert_send_sync::<FourTables>();
        assert_send_sync::<OneTableFourColumns>();
        assert_send_sync::<PackedPayload>();

        let entries = synthetic_entries(256, 20, 42);
        let a: Arc<dyn ObjectIndex> = Arc::new(FourTables::build(&entries).unwrap());
        let b: Arc<dyn ObjectIndex> = Arc::new(OneTableFourColumns::build(&entries).unwrap());
        let c: Arc<dyn ObjectIndex> = Arc::new(PackedPayload::build(&entries).unwrap());
        let oids: Vec<Vec<u8>> = entries.iter().map(|e| e.oid.clone()).collect();
        let mut handles = Vec::new();
        for idx in [a, b, c] {
            let oids = oids.clone();
            handles.push(std::thread::spawn(move || {
                let refs: Vec<&[u8]> = oids.iter().map(|o| o.as_slice()).collect();
                idx.lookup_batch(&refs).iter().filter(|r| r.is_some()).count()
            }));
        }
        for h in handles {
            assert_eq!(h.join().unwrap(), 256, "every oid must resolve off-thread");
        }
    }
}