pub fn topological_order(entries: Vec<EmitEntry>) -> (Vec<EmitEntry>, Vec<u64>)Expand description
Order entries so that every delta follows the base it names.
§Why a topological order and not the input order
OFS_DELTA names its base by backwards distance. A base that has not
been written yet has no distance to name, so an order that puts a delta first
is not merely inefficient — it cannot be encoded at all.
The edges are already data: delta_base is an absolute archive offset, and
offset is what an entry is named by. So this is a sort over facts the index
holds, not a graph anyone has to build.
§An entry whose base is not in the set
Left where it is, and reported. The caller decides: add the base (right for a
clone, where the base is reachable anyway) or rewrite the entry as a
REF_DELTA naming the base by oid (right for a thin fetch, where the client
consented and already holds it). Deciding here would make one of those two
impossible.
Returns the ordered entries and the offsets that were named but absent.