Module reach 

__gunnar_reach__ — reachability bitmaps.

For each selected commit, the set of objects reachable from it — the commit itself, its ancestors, and every tree and blob those commits point at — recorded as a roaring bitmap over object ordinals.

Two ordinal spaces, one view

A sealed archive numbers its objects in oid-lexicographic order: the order the sorted lookup sub-index is in and the order __gunnar_oid__ records in its ordinal column, so a bitmap position is resolvable with the oid index alone. OrdinalSpace::new is that space.

A live store numbers its objects in an append-only space (OrdinalTable): a sorted base laid down by the first fold, then every object a later push brings in appended behind it in arrival order. The point is that a push never renumbers anything — a bitmap is a fact about an immutable commit, and under the sorted space every push shifted every ordinal above the new oids, so every stored bitmap had to be rewritten bit by bit (carry_reach, 512 entries × every object, after every push). Under the stable space a push appends a few ordinals and the table is untouched. The sorted order is restored only when the store seals or the appended part outgrows the base, both through one remap table (OrdinalTable::remap_to).

No hex on any hot path

Everything below the public builders is in integers: the graph is OrdGraph (rows and ordinals), the table is ReachTable (ordinals and bitmaps), a tree is read by its raw oid and each of its entries is resolved with one OrdinalSpace::ordinal_of_raw — a 16-bit fanout and a short binary search, no decode. GUN-PERF measured the hex form on git.git (402 227 objects): the build took 85 to 150 s and ordinal_of_hex alone was 51 % of a 65 s clone (gunnar 18c10860).

The builder is git’s, not a closure memo

build_reach_table walks the commits parents-before-children, starts each commit’s bitmap from its parents’ and adds the trees with the skip rule (should_include_obj: a set bit means that object AND everything under it is already accounted for). Work is O(objects + commits), and the memory is the frontier — the bitmaps of commits whose children are still to come — not one closure bitmap per distinct tree. The old builder kept the latter and paid a hex String per tree entry on top.

Structs

ObjectFacts

What the builder needs to know about every object in the archive.

OrdGraph

The commit graph in integers: one row per commit, rows in the order the CommitNode list came in (parents before children, as crate::graph::assign_generations guarantees).

OrdinalSpace

oid ⇄ ordinal, as a Copy view that owns nothing.

OrdinalTable

The live store’s ordinal space: a sorted base, then arrivals appended. Owned; Self::view is the lookup. See the module header for why it is append-only.

ReachEntry

One sealed bitmap, in the sealed archive’s spelling (hex commit oid). The live store keeps a ReachTable; this is the __gunnar_reach__ row.

ReachPolicy

Which commits get a bitmap.

ReachTable

The live reachability table: entry i is the closure of the commit at ordinal commits[i].

ReachView

The table, its row index and the graph, paired by the fold that built them so a lookup can never mix a table with another fold’s rows.

Constants

NONE

“No ordinal” / “no row” in the integer tables.

Traits

TreeSource

Where a tree’s bytes come from — a lookup, not a table, keyed by the raw oid.

Functions

accumulate

The bounded walk: OR into acc everything reachable from the commit at row, stopping at every commit that already has a bitmap.

build_reach

The sealed builder: hex nodes in, hex entries out, over a sorted space. Decodes each node once into an OrdGraph and runs build_reach_table.

build_reach_batch

build_reach_table

Build the table from scratch, parents before children, each bitmap started from its parents’ and completed by [fill_tree].

carry_reach

Carry a sealed-spelling table across a renumbering — kept for the sealed builders and the tests that speak hex; the live store uses ReachTable::remapped with one remap table. keep decides which commits survive. None means the carry cannot be exact (a set bit’s object is gone).

decode_live_table

The inverse of encode_live_table, through the IPC guard: hostile bytes are an Err, never a panic or an allocation abort. space_len bounds the ordinals: an entry naming one outside the space is refused.

decode_reach

encode_live_table

The live table as Arrow IPC stream bytes: (commit_ordinal, bitmap).

extend_reach_table

Extend a table after a push: entries for the new tips (and a sample of the other new commits), each computed by the bounded walk down to the entries that already exist. Nothing already in the table is touched or recomputed; the cost is the pushed commits’ trees, whatever the repository’s size. new_rows must be in parents-before-children order (the caller takes them off the generation-ordered graph).

needs_payload

Which objects a repack must hold to make the reachability pass exact.

reach_schema

read_reach

Read the reachability bitmaps out of a sealed archive. Ok(None) when absent.