//! The structural graph of a store, independent of any horizon or cone: for
//! every held artifact that parses as structural, its kind and the rids its
//! P, B, S, F and A cards name. Classifying a store under a horizon
//! (draft-fossil-horizon section 4) needs exactly this and nothing else from
//! the artifacts, and reading it is where the whole cost of a first
//! classification goes: every structural artifact inflated and parsed once,
//! minutes on a store of a few hundred thousand check-ins. The graph is read
//! once per store, extended by the artifacts appended since (the log is
//! append-only, so rids below the recorded count never change), and kept in
//! a `.zit-cache` sidecar keyed to the log prefix it covers. A classification
//! over the graph is a walk over arrays.
//!
//! What it does NOT carry: filenames, and F-card targets. A cone with path
//! members needs filenames for `covers`, and such a classification parses
//! as before; the horizon alone, which is what a structural clone and the
//! CI loop over it use, never does. F-card targets are the bulk of a store's
//! references (a sub-manifest store of a few hundred thousand check-ins has
//! tens of millions) and the classification needs them for exactly two
//! things: the blobs of the check-ins K reaches, read from those few
//! artifacts on demand, and whether a blob is cited by ANY held structural
//! artifact, which is one bitset kept here.
const std = @import("std");
const artifact = @import("artifact.zig");
const repostate = @import("repostate.zig");
const logstore = @import("logstore.zig");
const repocache = @import("repocache.zig");
const codec = @import("container.zig");
const crc32 = @import("crc32.zig");
const Rid = repostate.Rid;
pub const Kind = enum(u8) {
/// Not structural: a content blob, or not held.
blob = 0,
manifest = 1,
submanifest = 2,
cluster = 3,
/// Control, wiki, ticket, technote, forum, attachment: kept whatever
/// the horizon says.
other = 4,
};
/// One structural artifact's graph references, as rids. Slices borrow the
/// graph and stay valid until it is extended or freed.
pub const Record = struct {
kind: Kind,
parents: []const u32,
baseline: ?u32,
nodes: []const u32,
attachment_source: ?u32,
};
pub const Graph = struct {
/// Rids covered: every held rid in 1..=n has a record (possibly `blob`).
n: u32 = 0,
/// `kind[rid]` for rid in 0..=n (index 0 unused).
kind: std.ArrayListUnmanaged(u8) = .empty,
/// `start[rid]`..`start[rid+1]` is rid's span in `refs`; len n+2.
start: std.ArrayListUnmanaged(u32) = .empty,
/// Spans: n_p, p..., baseline-or-0, n_s, s..., attachment-or-0.
refs: std.ArrayListUnmanaged(u32) = .empty,
/// Rids some held structural artifact's F card names (held targets only).
/// A held blob not in here is referenced by nothing and is kept whatever
/// the horizon; one in here is kept only when a kept manifest names it.
cited: std.DynamicBitSetUnmanaged = .{},
/// P, B and S names cited by a held artifact that the store did not hold
/// when it was read, each with the `refs` slots that cite it, 0 until the
/// name arrives. `extend` fills the slots when it does, so a parent that
/// arrives after its children leaves them connected rather than orphaned
/// for good. Such an arrival also changes what older check-ins mean (see
/// sparse.ClassifyState), so a classifier that extended from an older
/// state must start over. Keys and lists owned.
dangling: std.StringHashMapUnmanaged(std.ArrayListUnmanaged(u32)) = .empty,
pub fn deinit(self: *Graph, gpa: std.mem.Allocator) void {
self.kind.deinit(gpa);
self.start.deinit(gpa);
self.refs.deinit(gpa);
self.cited.deinit(gpa);
var it = self.dangling.iterator();
while (it.next()) |kv| {
gpa.free(kv.key_ptr.*);
kv.value_ptr.deinit(gpa);
}
self.dangling.deinit(gpa);
self.* = .{};
}
/// A 0 among `parents` or `nodes` is a citation the store did not hold
/// when the artifact was read and has not held since; readers skip it.
pub fn record(self: *const Graph, rid: Rid) ?Record {
if (rid == 0 or rid > self.n) return null;
const r: usize = @intCast(rid);
const kind: Kind = @fromBackingInt(@intCast(self.kind.items[r]));
if (kind == .blob) return null;
var pos: usize = self.start.items[r];
const refs = self.refs.items;
const n_p = refs[pos];
pos += 1;
const parents = refs[pos .. pos + n_p];
pos += n_p;
const b = refs[pos];
pos += 1;
const n_s = refs[pos];
pos += 1;
const nodes = refs[pos .. pos + n_s];
pos += n_s;
const a = refs[pos];
return .{
.kind = kind,
.parents = parents,
.baseline = if (b == 0) null else b,
.nodes = nodes,
.attachment_source = if (a == 0) null else a,
};
}
fn dangle(self: *Graph, gpa: std.mem.Allocator, name: []const u8, slot: ?u32) error{OutOfMemory}!void {
const gop = try self.dangling.getOrPut(gpa, name);
if (!gop.found_existing) {
gop.value_ptr.* = .empty;
gop.key_ptr.* = gpa.dupe(u8, name) catch |e| {
self.dangling.removeByPtr(gop.key_ptr);
return e;
};
}
if (slot) |s| try gop.value_ptr.append(gpa, s);
}
/// Append one P/B/S citation as a `refs` slot: the held rid it names, or
/// 0 recorded under the name for `extend` to fill when it arrives. Never
/// interns: the graph describes what is held.
fn appendRef(self: *Graph, gpa: std.mem.Allocator, store: repostate.ArtifactStore, name: []const u8) error{OutOfMemory}!void {
const slot: u32 = @intCast(self.refs.items.len);
try self.refs.append(gpa, 0);
if (store.lookup(name)) |rid| {
if (store.held(rid)) {
self.refs.items[slot] = @intCast(rid);
return;
}
}
try self.dangle(gpa, name, slot);
}
/// Fill every slot that cited `rid`'s name before it was held.
fn resolveArrival(self: *Graph, gpa: std.mem.Allocator, store: repostate.ArtifactStore, rid: Rid) void {
if (self.dangling.count() == 0) return;
var kv = self.dangling.fetchRemove(store.hashOf(rid)) orelse return;
for (kv.value.items) |slot| self.refs.items[slot] = @intCast(rid);
kv.value.deinit(gpa);
gpa.free(kv.key);
}
/// Does an artifact in `from..=count` carry a name a held artifact cited
/// before it arrived?
pub fn arrivalWasCited(self: *const Graph, store: repostate.ArtifactStore, from: Rid) bool {
if (self.dangling.count() == 0) return false;
const n = store.count();
var rid = from;
while (rid <= n) : (rid += 1) {
if (!store.held(rid)) continue;
if (self.dangling.contains(store.hashOf(rid))) return true;
}
return false;
}
/// Read the held rids in `n+1..=count()` into the graph. Rids must fit
/// 32 bits.
pub fn extend(self: *Graph, gpa: std.mem.Allocator, store: repostate.ArtifactStore) error{OutOfMemory}!void {
const count = store.count();
if (count >= std.math.maxInt(u32)) return error.OutOfMemory;
const n_new: u32 = @intCast(count);
if (self.cited.capacity() < count + 1) try self.cited.resize(gpa, count + 1, false);
if (self.kind.items.len == 0) {
try self.kind.append(gpa, 0);
try self.start.append(gpa, 0);
try self.start.append(gpa, 0);
}
try self.kind.ensureTotalCapacity(gpa, n_new + 1);
try self.start.ensureTotalCapacity(gpa, n_new + 2);
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
var rid: Rid = self.n + 1;
while (rid <= n_new) : (rid += 1) {
// Every rid gets a kind and a (possibly empty) span, so `record`
// indexes by rid alone.
const span_start: u32 = @intCast(self.refs.items.len);
var kind: Kind = .blob;
if (store.held(rid)) self.resolveArrival(gpa, store, rid);
if (store.held(rid) and mayBeStructural(gpa, store, rid)) {
if (store.content(rid)) |plain| {
if (looksStructural(plain)) {
_ = arena_state.reset(.retain_capacity);
const aa = arena_state.allocator();
if (artifact.parseForImport(aa, plain)) |im| {
kind = switch (im.manifest.kind) {
.manifest => .manifest,
.submanifest => .submanifest,
.cluster => .cluster,
else => .other,
};
try self.appendRefs(gpa, store, &im.manifest);
} else |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => {}, // a content blob that began like a card
}
}
}
}
self.kind.appendAssumeCapacity(@backingInt(kind));
// start[rid] was appended as the previous span's end; append this
// span's end as start[rid+1].
std.debug.assert(self.start.items[@intCast(rid)] == span_start);
self.start.appendAssumeCapacity(@intCast(self.refs.items.len));
}
self.n = n_new;
}
fn appendRefs(self: *Graph, gpa: std.mem.Allocator, store: repostate.ArtifactStore, m: *const artifact.Manifest) error{OutOfMemory}!void {
const refs = &self.refs;
const n_p_at = refs.items.len;
try refs.append(gpa, 0);
var n_p: u32 = 0;
for (m.p) |pc| {
var it = pc.hashes();
while (it.next()) |ph| {
try self.appendRef(gpa, store, ph);
n_p += 1;
}
}
refs.items[n_p_at] = n_p;
if (m.b) |b| try self.appendRef(gpa, store, b.hash) else try refs.append(gpa, 0);
const n_s_at = refs.items.len;
try refs.append(gpa, 0);
var n_s: u32 = 0;
for (m.s) |sc| {
try self.appendRef(gpa, store, sc.hash);
n_s += 1;
}
refs.items[n_s_at] = n_s;
for (m.f) |fc| {
const h = fc.hash orelse continue;
const rid = store.lookup(h) orelse continue;
if (!store.held(rid)) continue;
if (rid >= self.cited.capacity()) try self.cited.resize(gpa, rid + 1, false);
self.cited.set(rid);
}
var a: u32 = 0;
if (m.a) |ac| {
if (ac.source) |src| {
if (store.lookup(src)) |rid| {
if (store.held(rid)) a = @intCast(rid);
}
}
}
try refs.append(gpa, a);
}
// -- sidecar --------------------------------------------------------------
const magic: *const [8]u8 = "ZITSGRPH";
/// 2: a dangling name carries the slots that cite it; a cited name that
/// was unresolved holds a 0 slot instead of being dropped.
const version: u16 = 2;
pub const member = "graph";
fn putInt(out: *std.ArrayListUnmanaged(u8), gpa: std.mem.Allocator, comptime T: type, v: T) error{OutOfMemory}!void {
var buf: [@sizeOf(T)]u8 = undefined;
std.mem.writeInt(T, &buf, v, .little);
try out.appendSlice(gpa, &buf);
}
fn putU32s(out: *std.ArrayListUnmanaged(u8), gpa: std.mem.Allocator, items: []const u32) error{OutOfMemory}!void {
try putInt(out, gpa, u64, items.len);
const bytes = std.mem.sliceAsBytes(items);
if (@import("builtin").cpu.arch.endian() == .little) {
try out.appendSlice(gpa, bytes);
} else {
for (items) |v| try putInt(out, gpa, u32, v);
}
}
/// The graph for a store whose first `n` rids are the log's frames under
/// `key`. Null when the graph covers more than the log (session rids).
pub fn serialize(self: *const Graph, gpa: std.mem.Allocator, key: logstore.LogStore.LogKey, n_log: u64) error{OutOfMemory}!?[]u8 {
if (self.n != n_log) return null;
var out: std.ArrayListUnmanaged(u8) = .empty;
errdefer out.deinit(gpa);
try out.appendSlice(gpa, magic);
try putInt(&out, gpa, u16, version);
try putInt(&out, gpa, u64, key.end);
try putInt(&out, gpa, u64, key.frame_count);
try putInt(&out, gpa, u64, key.last_frame_offset);
try putInt(&out, gpa, u32, key.last_header_crc);
try putInt(&out, gpa, u32, self.n);
try putInt(&out, gpa, u64, self.kind.items.len);
try out.appendSlice(gpa, self.kind.items);
try putU32s(&out, gpa, self.start.items);
try putU32s(&out, gpa, self.refs.items);
// The cited set, as 64-bit words over 0..=n.
const n_bits: usize = @as(usize, self.n) + 1;
try putInt(&out, gpa, u64, n_bits);
var w: usize = 0;
while (w * 64 < n_bits) : (w += 1) {
var word: u64 = 0;
var i: usize = 0;
while (i < 64 and w * 64 + i < n_bits) : (i += 1) {
const bit = w * 64 + i;
if (bit < self.cited.capacity() and self.cited.isSet(bit)) word |= @as(u64, 1) << @intCast(i);
}
try putInt(&out, gpa, u64, word);
}
try putInt(&out, gpa, u32, @intCast(self.dangling.count()));
var it = self.dangling.iterator();
while (it.next()) |kv| {
if (kv.key_ptr.len > 255) return null;
try out.append(gpa, @intCast(kv.key_ptr.len));
try out.appendSlice(gpa, kv.key_ptr.*);
try putU32s(&out, gpa, kv.value_ptr.items);
}
var crc = crc32.Crc32.init();
crc.update(out.items);
try putInt(&out, gpa, u32, crc.final());
return try out.toOwnedSlice(gpa);
}
const Reader = struct {
buf: []const u8,
pos: usize = 0,
fn int(self: *Reader, comptime T: type) ?T {
if (self.pos + @sizeOf(T) > self.buf.len) return null;
const v = std.mem.readInt(T, self.buf[self.pos..][0..@sizeOf(T)], .little);
self.pos += @sizeOf(T);
return v;
}
fn bytes(self: *Reader, len: usize) ?[]const u8 {
if (self.pos + len > self.buf.len) return null;
const s = self.buf[self.pos..][0..len];
self.pos += len;
return s;
}
fn u32s(self: *Reader, gpa: std.mem.Allocator, out: *std.ArrayListUnmanaged(u32)) error{OutOfMemory}!bool {
const len: usize = std.math.cast(usize, self.int(u64) orelse return false) orelse return false;
const raw = self.bytes(len * 4) orelse return false;
try out.ensureTotalCapacityPrecise(gpa, len);
var i: usize = 0;
while (i < len) : (i += 1) out.appendAssumeCapacity(std.mem.readInt(u32, raw[i * 4 ..][0..4], .little));
return true;
}
};
pub const Parsed = struct { key: logstore.LogStore.LogKey, graph: Graph };
/// Parse a sidecar: magic, version and CRC must hold, or null.
pub fn parse(gpa: std.mem.Allocator, blob: []const u8) error{OutOfMemory}!?Parsed {
if (blob.len < 8 + 2 + 4) return null;
if (!std.mem.eql(u8, blob[0..8], magic)) return null;
var crc = crc32.Crc32.init();
crc.update(blob[0 .. blob.len - 4]);
if (std.mem.readInt(u32, blob[blob.len - 4 ..][0..4], .little) != crc.final()) return null;
var r: Reader = .{ .buf = blob[0 .. blob.len - 4], .pos = 8 };
if ((r.int(u16) orelse return null) != version) return null;
const key = logstore.LogStore.LogKey{
.end = r.int(u64) orelse return null,
.frame_count = r.int(u64) orelse return null,
.last_frame_offset = r.int(u64) orelse return null,
.last_header_crc = r.int(u32) orelse return null,
};
var g: Graph = .{};
errdefer g.deinit(gpa);
g.n = r.int(u32) orelse return null;
const kind_len: usize = std.math.cast(usize, r.int(u64) orelse return null) orelse return null;
try g.kind.appendSlice(gpa, r.bytes(kind_len) orelse return null);
if (!try r.u32s(gpa, &g.start)) return null;
if (!try r.u32s(gpa, &g.refs)) return null;
if (g.kind.items.len != @as(usize, g.n) + 1 or g.start.items.len != @as(usize, g.n) + 2) return null;
if (g.start.items[g.start.items.len - 1] != g.refs.items.len) return null;
const n_bits: usize = std.math.cast(usize, r.int(u64) orelse return null) orelse return null;
if (n_bits != @as(usize, g.n) + 1) return null;
try g.cited.resize(gpa, n_bits, false);
var w: usize = 0;
while (w * 64 < n_bits) : (w += 1) {
const word = r.int(u64) orelse return null;
var i: usize = 0;
while (i < 64 and w * 64 + i < n_bits) : (i += 1) {
if ((word >> @intCast(i)) & 1 != 0) g.cited.set(w * 64 + i);
}
}
const n_dangling = r.int(u32) orelse return null;
var i: u32 = 0;
while (i < n_dangling) : (i += 1) {
const len = (r.bytes(1) orelse return null)[0];
const nm = r.bytes(len) orelse return null;
var slots: std.ArrayListUnmanaged(u32) = .empty;
defer slots.deinit(gpa);
if (!try r.u32s(gpa, &slots)) return null;
try g.dangle(gpa, nm, null);
for (slots.items) |slot| {
if (slot >= g.refs.items.len) return null;
try g.dangle(gpa, nm, slot);
}
}
if (r.pos != r.buf.len) return null;
return .{ .key = key, .graph = g };
}
/// Load the graph sidecar for `log` when it is still a prefix, extend it
/// over `store` (reading only the rids appended since), and write it back.
/// Any sidecar trouble is a fresh read of the whole store.
pub fn loadOrBuild(gpa: std.mem.Allocator, io: std.Io, cache_dir: std.Io.Dir, log: *const logstore.LogStore, store: repostate.ArtifactStore) error{OutOfMemory}!Graph {
var g: ?Graph = null;
errdefer if (g) |*x| x.deinit(gpa);
const n_log: u64 = log.entryCount();
if (try repocache.loadMember(gpa, io, cache_dir, member)) |blob| {
defer gpa.free(blob);
if (try parse(gpa, blob)) |p_const| {
var p = p_const;
if (p.graph.n <= n_log and logstore.LogStore.validatePrefix(log.file, p.key)) {
g = p.graph;
} else {
p.graph.deinit(gpa);
}
}
}
if (g == null) g = .{};
try g.?.extend(gpa, store);
if (log.logKey()) |key| {
if (try g.?.serialize(gpa, key, n_log)) |blob| {
defer gpa.free(blob);
repocache.storeNamedMember(io, cache_dir, member, blob);
}
} else |_| {}
return g.?;
}
};
/// The cheap half of `looksStructural`: for an artifact the store holds as a
/// FULL container, inflate only the first two bytes and apply the same test.
/// A delta-stored artifact or a store with no wire form answers true and
/// falls through to the full read.
pub fn mayBeStructural(gpa: std.mem.Allocator, store: repostate.ArtifactStore, rid: Rid) bool {
const wf = store.wire(rid) orelse return true;
if (wf.delta != null) return true;
const head = codec.decodePrefix(gpa, wf.container, 2) catch return true;
defer gpa.free(head);
return looksStructural(head);
}
/// Could these bytes be a structural artifact at all? Every artifact begins
/// with a card -- an upper-case letter, a space -- or with the PGP or SSH
/// signature envelope the format admits around one, which begins with `-`.
pub fn looksStructural(plain: []const u8) bool {
if (plain.len < 2) return false;
if (plain[0] == '-') return true;
return std.ascii.isUpper(plain[0]) and plain[1] == ' ';
}
test "graph: records round-trip through the sidecar and extend reads only the tail" {
const gpa = std.testing.allocator;
var ms = repostate.MemStore.init(gpa);
defer ms.deinit();
const s = ms.store();
const blob_a = "1111111111111111111111111111111111111111111111111111111111111111";
_ = try s.put(blob_a, "hello");
// A minimal check-in manifest naming blob_a.
var m = artifact.Manifest{
.arena_state = std.heap.ArenaAllocator.init(gpa),
.kind = .manifest,
.b = null,
.c = .{ .comment = "c" },
.d = .{ .timestamp = "2026-01-01T00:00:00" },
.a = null,
.e = null,
.g = null,
.h = null,
.i = null,
.k = null,
.l = null,
.n = null,
.r = null,
.u = .{ .login = "u" },
.z = null,
.w = null,
.f = &.{.{ .filename = "a.txt", .hash = blob_a, .perm = null, .old_name = null, .mode = .regular }},
.j = &.{},
.m = &.{},
.p = &.{},
.q = &.{},
.s = &.{},
.t = &.{},
};
defer m.deinit();
const bytes = try artifact.create(&m, gpa);
defer gpa.free(bytes);
var name: [64]u8 = undefined;
const nm = artifact.artifactName(.sha3_256, bytes, &name);
var g: Graph = .{};
defer g.deinit(gpa);
try g.extend(gpa, s);
try std.testing.expectEqual(@as(u32, 1), g.n);
try std.testing.expect(g.record(1) == null); // the blob
_ = try s.put(nm, bytes);
try g.extend(gpa, s);
const rec = g.record(2).?;
try std.testing.expectEqual(Kind.manifest, rec.kind);
try std.testing.expect(g.cited.isSet(1));
try std.testing.expectEqual(@as(usize, 0), rec.parents.len);
const key = logstore.LogStore.LogKey{ .end = 1, .frame_count = 2, .last_frame_offset = 3, .last_header_crc = 4 };
const blob = (try g.serialize(gpa, key, 2)).?;
defer gpa.free(blob);
var p = (try Graph.parse(gpa, blob)).?;
defer p.graph.deinit(gpa);
try std.testing.expectEqual(key, p.key);
try std.testing.expectEqual(g.n, p.graph.n);
try std.testing.expectEqualSlices(u32, g.refs.items, p.graph.refs.items);
try std.testing.expect(p.graph.cited.isSet(1));
try std.testing.expect(!p.graph.cited.isSet(2));
try std.testing.expectEqual(Kind.manifest, p.graph.record(2).?.kind);
}
test "graph: a parent that arrives after its child fills the child's slot, through the sidecar too" {
const gpa = std.testing.allocator;
var ms = repostate.MemStore.init(gpa);
defer ms.deinit();
const s = ms.store();
const blob_a = "1111111111111111111111111111111111111111111111111111111111111111";
_ = try s.put(blob_a, "hello");
var parent = artifact.Manifest{
.arena_state = std.heap.ArenaAllocator.init(gpa),
.kind = .manifest,
.b = null,
.c = .{ .comment = "parent" },
.d = .{ .timestamp = "2026-01-01T00:00:00" },
.a = null,
.e = null,
.g = null,
.h = null,
.i = null,
.k = null,
.l = null,
.n = null,
.r = null,
.u = .{ .login = "u" },
.z = null,
.w = null,
.f = &.{.{ .filename = "a.txt", .hash = blob_a, .perm = null, .old_name = null, .mode = .regular }},
.j = &.{},
.m = &.{},
.p = &.{},
.q = &.{},
.s = &.{},
.t = &.{},
};
defer parent.deinit();
const parent_bytes = try artifact.create(&parent, gpa);
defer gpa.free(parent_bytes);
var parent_name: [64]u8 = undefined;
const pn = artifact.artifactName(.sha3_256, parent_bytes, &parent_name);
var child = artifact.Manifest{
.arena_state = std.heap.ArenaAllocator.init(gpa),
.kind = .manifest,
.b = null,
.c = .{ .comment = "child" },
.d = .{ .timestamp = "2026-01-02T00:00:00" },
.a = null,
.e = null,
.g = null,
.h = null,
.i = null,
.k = null,
.l = null,
.n = null,
.r = null,
.u = .{ .login = "u" },
.z = null,
.w = null,
.f = &.{.{ .filename = "a.txt", .hash = blob_a, .perm = null, .old_name = null, .mode = .regular }},
.j = &.{},
.m = &.{},
.p = &.{.{ .parents = pn, .count = 1 }},
.q = &.{},
.s = &.{},
.t = &.{},
};
defer child.deinit();
const child_bytes = try artifact.create(&child, gpa);
defer gpa.free(child_bytes);
var child_name: [64]u8 = undefined;
const cn = artifact.artifactName(.sha3_256, child_bytes, &child_name);
// The child arrives first: its one parent slot is 0 and the name dangles.
_ = try s.put(cn, child_bytes);
var g: Graph = .{};
defer g.deinit(gpa);
try g.extend(gpa, s);
try std.testing.expectEqualSlices(u32, &.{0}, g.record(2).?.parents);
try std.testing.expectEqual(@as(usize, 1), g.dangling.count());
// Through the sidecar the slot survives.
const key = logstore.LogStore.LogKey{ .end = 1, .frame_count = 2, .last_frame_offset = 3, .last_header_crc = 4 };
const blob = (try g.serialize(gpa, key, 2)).?;
defer gpa.free(blob);
var p = (try Graph.parse(gpa, blob)).?;
defer p.graph.deinit(gpa);
try std.testing.expectEqual(@as(usize, 1), p.graph.dangling.count());
try std.testing.expectEqualSlices(u32, g.dangling.get(pn).?.items, p.graph.dangling.get(pn).?.items);
// The parent arrives: both graphs link the child to it and nothing dangles.
_ = try s.put(pn, parent_bytes);
try g.extend(gpa, s);
try p.graph.extend(gpa, s);
try std.testing.expectEqualSlices(u32, &.{3}, g.record(2).?.parents);
try std.testing.expectEqualSlices(u32, &.{3}, p.graph.record(2).?.parents);
try std.testing.expectEqual(@as(usize, 0), g.dangling.count());
try std.testing.expectEqual(@as(usize, 0), p.graph.dangling.count());
try std.testing.expect(!g.arrivalWasCited(s, 3));
}