summaryrefslogtreecommitdiff
path: root/anim/src/relations.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-11-11 23:46:02 -0300
committerGabriel Schneider <[email protected]>2026-11-12 01:40:04 -0300
commit60e07feef401d9044db3a1c925cb9d1f6d20dac9 (patch)
tree98957ba8425193f686c8e8692cd10a10f27dbf4b /anim/src/relations.zig
parent9c0696447dbc5cf37e56aee562c7ebba4f4d4e6b (diff)
downloadcomputeranim-60e07feef401d9044db3a1c925cb9d1f6d20dac9.tar.gz
computeranim-60e07feef401d9044db3a1c925cb9d1f6d20dac9.zip
canim: relations as one data-oriented subsystem; aim; the ASan pair; the introduction's chapters
From the user. Relations between panes are one subsystem: per-frame tables of places and values in struct-of-arrays, owned by the frame; the kinds one table of data; a resolver of pure passes (join, filter, priority, cut) unit-tested on hand-written tables. Ported kinds draw byte-identical frames; a synthetic map of 4000 places and 6000 values resolves in 0.56 ms against the old table's 5.7. aim, a word holding a code address tied to its row, is the first new kind, off unless a scene turns it on. The ASan pair: one overflow built plain and with ASan, recorded by instruction; the frame as bytes eight a row; the plain run goes on alone in the column, its return address aimed at main's row until the letters reach it; the fault at ret. The introduction's three chapters are built and tested, not yet exported. Annotations, rows and scrolls that changed in one frame now fade; captions stand twelve seconds at most. Co-Authored-By: Claude Opus 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_016Y9MNCKgYCGiANnEwcEQxa
Diffstat (limited to 'anim/src/relations.zig')
-rw-r--r--anim/src/relations.zig341
1 files changed, 341 insertions, 0 deletions
diff --git a/anim/src/relations.zig b/anim/src/relations.zig
new file mode 100644
index 0000000..03165d5
--- /dev/null
+++ b/anim/src/relations.zig
@@ -0,0 +1,341 @@
+//! The relations' data (design/README.md, "4. Ties"), one table set a
+//! frame, and the passes over it. The panels say, as they draw, where each
+//! of their things is (`places`: a key, the kind of thing and its address
+//! packed in one integer, a box, a pane) and which values they show that
+//! could be addresses (`values`: the value, its box, its pane, a reference
+//! such as a register's index). A relation is a join of the two on
+//! address, or a step's own fact (a touch, a carry, the thread), and the
+//! resolver (`ties.zig`) runs it as a pipeline of passes over slices:
+//! candidates, `filter` by the knobs, `order` by priority, `cut` to the
+//! budget, route, draw. `filter`, `order`, `cut` and `join` are pure, and
+//! tested here with tables written by hand.
+//!
+//! Memory: the tables live in the frame's scratch arena (`sk.Frame.user`),
+//! made at the frame's first place and gone with it: no process globals,
+//! no allocation per relation, indices rather than pointers.
+const std = @import("std");
+
+/// The pane a place or a value is drawn in.
+pub const Pane = enum(u8) { other, source, disasm, registers, stack, view, drawing, loupe };
+
+/// A key: the kind of thing in its top byte, an address (or an index) in the rest.
+pub const Key = u64;
+pub const kind_shift = 56;
+pub const address_mask: u64 = (1 << kind_shift) - 1;
+
+pub fn keyOf(kind: u8, address: u64) Key {
+ return @as(u64, kind) << kind_shift | (address & address_mask);
+}
+
+pub fn kindOf(key: Key) u8 {
+ return @intCast(key >> kind_shift);
+}
+
+pub const Place = struct { key: Key, box: [4]f32, pane: Pane };
+/// `at`: the address of the word that holds it (0: a register's); `ref`: a
+/// register's index; `rules`: its panel's left and right rules.
+pub const Value = struct { value: u64, box: [4]f32, pane: Pane, ref: u32 = 0, at: u64 = 0, rules: [2]f32 = .{ 0, 0 } };
+
+/// One layer's tables: the working frame's, or the map's.
+pub const Tables = struct {
+ places: std.MultiArrayList(Place) = .{},
+ values: std.MultiArrayList(Value) = .{},
+ /// `places` by key (then by the order they were said), and `values` by
+ /// value: built once, on the first lookup after a change.
+ places_by_key: std.ArrayList(u32) = .empty,
+ values_by_value: std.ArrayList(u32) = .empty,
+ places_sorted: bool = true,
+ values_sorted: bool = true,
+ /// Nanoseconds this frame spent sorting.
+ sort_ns: u64 = 0,
+
+ pub fn add(t: *Tables, gpa: std.mem.Allocator, place: Place) void {
+ t.places.append(gpa, place) catch return;
+ t.places_sorted = false;
+ }
+
+ pub fn show(t: *Tables, gpa: std.mem.Allocator, value: Value) void {
+ t.values.append(gpa, value) catch return;
+ t.values_sorted = false;
+ }
+
+ /// The index of places by key: sorted once after a change.
+ pub fn byKey(t: *Tables, gpa: std.mem.Allocator) []const u32 {
+ if (!t.places_sorted) {
+ const start = clock();
+ sortIndex(gpa, &t.places_by_key, t.places.items(.key));
+ t.places_sorted = true;
+ t.sort_ns += clock() - start;
+ }
+ return t.places_by_key.items;
+ }
+
+ pub fn byValue(t: *Tables, gpa: std.mem.Allocator) []const u32 {
+ if (!t.values_sorted) {
+ const start = clock();
+ sortIndex(gpa, &t.values_by_value, t.values.items(.value));
+ t.values_sorted = true;
+ t.sort_ns += clock() - start;
+ }
+ return t.values_by_value.items;
+ }
+
+ /// The box of the first place said with `key`: a binary search.
+ pub fn find(t: *Tables, gpa: std.mem.Allocator, key: Key) ?[4]f32 {
+ const order = t.byKey(gpa);
+ const keys = t.places.items(.key);
+ const i = lowerBound(order, keys, key);
+ if (i == order.len or keys[order[i]] != key) return null;
+ return t.places.items(.box)[order[i]];
+ }
+
+ /// The indices (into `places`) of the keys in `[lo, hi)`, in key order.
+ pub fn range(t: *Tables, gpa: std.mem.Allocator, lo: Key, hi: Key) []const u32 {
+ const order = t.byKey(gpa);
+ const keys = t.places.items(.key);
+ return order[lowerBound(order, keys, lo)..lowerBound(order, keys, hi)];
+ }
+
+ /// The greatest key of kind `kind` at or below `address`, within `within` of it.
+ pub fn atOrBelow(t: *Tables, gpa: std.mem.Allocator, kind: u8, address: u64, within: u64) ?u64 {
+ const order = t.byKey(gpa);
+ const keys = t.places.items(.key);
+ const i = lowerBound(order, keys, keyOf(kind, address) + 1);
+ if (i == 0) return null;
+ const k = keys[order[i - 1]];
+ if (kindOf(k) != kind) return null;
+ const a = k & address_mask;
+ return if (address - a < within) a else null;
+ }
+};
+
+/// `index` made the permutation of `keys` that sorts them, ties in their order.
+fn sortIndex(gpa: std.mem.Allocator, index: *std.ArrayList(u32), keys: []const u64) void {
+ index.resize(gpa, keys.len) catch return;
+ for (index.items, 0..) |*v, i| v.* = @intCast(i);
+ std.sort.pdq(u32, index.items, keys, struct {
+ fn less(k: []const u64, a: u32, b: u32) bool {
+ return k[a] < k[b] or (k[a] == k[b] and a < b);
+ }
+ }.less);
+}
+
+/// The first position in `order` whose key is not below `key`.
+fn lowerBound(order: []const u32, keys: []const u64, key: u64) usize {
+ var lo: usize = 0;
+ var hi: usize = order.len;
+ while (lo < hi) {
+ const mid = (lo + hi) / 2;
+ if (keys[order[mid]] < key) lo = mid + 1 else hi = mid;
+ }
+ return lo;
+}
+
+/// A value shown and the place of kind `kind` at its address (masked by
+/// `mask`: a view's row is its first byte's): indices into the tables.
+pub const Pair = struct { value: u32, place: u32 };
+
+/// The join of `values` (by value, `by_value` their order) with the
+/// places of kind `kind` (by key, `by_key` their order) on address: a merge
+/// of the two sorted sides, each value with the first place said at its
+/// address. Appends to `out`; a value that is no place's address has none.
+pub fn join(values: []const u64, by_value: []const u32, keys: []const Key, by_key: []const u32, kind: u8, mask: u64, out: *std.ArrayList(Pair), gpa: std.mem.Allocator) void {
+ // The places of the kind: one run of the key order.
+ const lo = lowerBound(by_key, keys, keyOf(kind, 0));
+ const hi = lowerBound(by_key, keys, keyOf(kind + 1, 0));
+ const run = by_key[lo..hi];
+ // Masking keeps the values' order (a mask clears low bits): one walk.
+ var p: usize = 0;
+ for (by_value) |v| {
+ const want = values[v] & mask & address_mask;
+ while (p < run.len and keys[run[p]] & address_mask < want) p += 1;
+ if (p == run.len) break;
+ if (keys[run[p]] & address_mask == want) out.append(gpa, .{ .value = v, .place = run[p] }) catch return;
+ }
+}
+
+// ---- The resolver's pure passes.
+
+/// The kinds of relation, in the order they are drawn.
+pub const Kind = enum(u8) { thread, beat, link, projection, touch, carry, code };
+
+/// What turns a kind on. `always`: whenever the step has one (the scene's
+/// beat, its own facts); the rest only where the author has turned it on
+/// (or, for the thread and links, has not turned it off).
+pub const Knob = enum(u8) { thread, links, carry, code, always };
+
+/// A budget's class: how many of it a frame draws at most.
+pub const Class = enum(u8) { standing, beat, step, carry, code };
+
+/// A kind's row of data: its knob, its class, its priority (lower first)
+/// and how many of it a frame draws at most.
+pub const Spec = struct { knob: Knob, class: Class, priority: u8, most: u8 };
+
+pub const specs = std.enums.EnumArray(Kind, Spec).init(.{
+ .thread = .{ .knob = .thread, .class = .standing, .priority = 0, .most = 1 },
+ .beat = .{ .knob = .always, .class = .beat, .priority = 1, .most = 1 },
+ .link = .{ .knob = .links, .class = .step, .priority = 2, .most = 1 },
+ .projection = .{ .knob = .always, .class = .step, .priority = 3, .most = 1 },
+ // The first to give way: three lines at most, so not with a link and a projection.
+ .touch = .{ .knob = .always, .class = .step, .priority = 4, .most = 1 },
+ .carry = .{ .knob = .carry, .class = .carry, .priority = 5, .most = 1 },
+ // One at a time: a standing row across panes, or the step's.
+ .code = .{ .knob = .code, .class = .code, .priority = 6, .most = 1 },
+});
+
+/// How many of a class a frame draws at most.
+pub const budget = std.enums.EnumArray(Class, u8).init(.{ .standing = 1, .beat = 1, .step = 2, .carry = 1, .code = 1 });
+
+/// The knobs as the scene has them this frame.
+pub const Knobs = std.enums.EnumSet(Knob);
+
+/// A relation that could be drawn: its kind, its rank within its kind (a
+/// register's place in pwndbg's order, a span's in the step), and the
+/// indices of what it ties (`from`, `to`: into a table, or a kind's own).
+pub const Candidate = struct { kind: Kind, rank: u32 = 0, from: u32 = 0, to: u32 = 0 };
+
+/// Those whose kind's knob is on, in place.
+pub fn filter(cands: []Candidate, knobs: Knobs) []Candidate {
+ var n: usize = 0;
+ for (cands) |c| if (knobs.contains(specs.get(c.kind).knob)) {
+ cands[n] = c;
+ n += 1;
+ };
+ return cands[0..n];
+}
+
+/// By priority, then rank, then as they came (`from`, each its own).
+pub fn byPriority(cands: []Candidate) void {
+ std.sort.pdq(Candidate, cands, {}, struct {
+ fn less(_: void, a: Candidate, b: Candidate) bool {
+ const pa = specs.get(a.kind).priority;
+ const pb = specs.get(b.kind).priority;
+ if (pa != pb) return pa < pb;
+ if (a.rank != b.rank) return a.rank < b.rank;
+ return a.from < b.from;
+ }
+ }.less);
+}
+
+/// The first of each kind up to its most, and of each class up to its
+/// budget, in place: what is cut is the least urgent.
+pub fn cut(cands: []Candidate) []Candidate {
+ var per_kind = std.enums.EnumArray(Kind, u8).initFill(0);
+ var per_class = std.enums.EnumArray(Class, u8).initFill(0);
+ var n: usize = 0;
+ for (cands) |c| {
+ const spec = specs.get(c.kind);
+ if (per_kind.get(c.kind) >= spec.most or per_class.get(spec.class) >= budget.get(spec.class)) continue;
+ per_kind.set(c.kind, per_kind.get(c.kind) + 1);
+ per_class.set(spec.class, per_class.get(spec.class) + 1);
+ cands[n] = c;
+ n += 1;
+ }
+ return cands[0..n];
+}
+
+/// Counts and nanoseconds of a frame's relations (`CANIM_RELATIONS=1`: a line a frame on stderr).
+pub const Stats = struct {
+ places: usize = 0,
+ values: usize = 0,
+ candidates: usize = 0,
+ kept: usize = 0,
+ drawn: usize = 0,
+ map_places: usize = 0,
+ map_values: usize = 0,
+ map_pairs: usize = 0,
+ ns: struct { sort: u64 = 0, candidates: u64 = 0, passes: u64 = 0, draw: u64 = 0, map: u64 = 0 } = .{},
+};
+
+/// Whether to say each frame's counts and times on stderr (`CANIM_RELATIONS=1`), read once.
+pub fn reporting() bool {
+ if (report_on == null) report_on = if (comptime @import("builtin").link_libc) std.c.getenv("CANIM_RELATIONS") != null else false;
+ return report_on.?;
+}
+var report_on: ?bool = null;
+
+pub fn clock() u64 {
+ var ts: std.os.linux.timespec = undefined;
+ _ = std.os.linux.clock_gettime(.MONOTONIC, &ts);
+ return @as(u64, @intCast(ts.sec)) * std.time.ns_per_s + @as(u64, @intCast(ts.nsec));
+}
+
+// ---- Tests: hand-written tables in, tables out.
+
+test "a lookup is the first place said with its key, by binary search" {
+ const gpa = std.testing.allocator;
+ var t: Tables = .{};
+ defer {
+ t.places.deinit(gpa);
+ t.places_by_key.deinit(gpa);
+ }
+ t.add(gpa, .{ .key = keyOf(3, 0x30), .box = .{ 1, 0, 0, 0 }, .pane = .stack });
+ t.add(gpa, .{ .key = keyOf(1, 0x10), .box = .{ 2, 0, 0, 0 }, .pane = .registers });
+ t.add(gpa, .{ .key = keyOf(3, 0x30), .box = .{ 3, 0, 0, 0 }, .pane = .stack });
+ try std.testing.expectEqual(@as(f32, 1), t.find(gpa, keyOf(3, 0x30)).?[0]);
+ try std.testing.expectEqual(@as(f32, 2), t.find(gpa, keyOf(1, 0x10)).?[0]);
+ try std.testing.expect(t.find(gpa, keyOf(3, 0x38)) == null);
+ // Said after a lookup: the order is made again.
+ t.add(gpa, .{ .key = keyOf(2, 0x20), .box = .{ 4, 0, 0, 0 }, .pane = .view });
+ try std.testing.expectEqual(@as(f32, 4), t.find(gpa, keyOf(2, 0x20)).?[0]);
+ // A range of one kind, and the nearest at or below an address.
+ t.add(gpa, .{ .key = keyOf(3, 0x50), .box = .{ 5, 0, 0, 0 }, .pane = .stack });
+ try std.testing.expectEqual(@as(usize, 3), t.range(gpa, keyOf(3, 0), keyOf(4, 0)).len);
+ try std.testing.expectEqual(@as(?u64, 0x30), t.atOrBelow(gpa, 3, 0x48, 64));
+ try std.testing.expectEqual(@as(?u64, null), t.atOrBelow(gpa, 3, 0x48, 8));
+ try std.testing.expectEqual(@as(?u64, null), t.atOrBelow(gpa, 3, 0x10, 64));
+}
+
+test "a join pairs each value with the first place at its address, of one kind" {
+ const gpa = std.testing.allocator;
+ // Places: rows (kind 14) at 401000, 401004 (twice), 401010; a word (kind 3) at 401004.
+ const keys = [_]Key{ keyOf(14, 0x401004), keyOf(3, 0x401004), keyOf(14, 0x401000), keyOf(14, 0x401010), keyOf(14, 0x401004) };
+ var by_key: std.ArrayList(u32) = .empty;
+ defer by_key.deinit(gpa);
+ sortIndex(gpa, &by_key, &keys);
+ // Values: 401004 (twice), 7fff0000, 401010, 401008.
+ const values = [_]u64{ 0x401004, 0x7fff0000, 0x401010, 0x401004, 0x401008 };
+ var by_value: std.ArrayList(u32) = .empty;
+ defer by_value.deinit(gpa);
+ sortIndex(gpa, &by_value, &values);
+ var out: std.ArrayList(Pair) = .empty;
+ defer out.deinit(gpa);
+ join(&values, by_value.items, &keys, by_key.items, 14, ~@as(u64, 0), &out, gpa);
+ try std.testing.expectEqualSlices(Pair, &.{ .{ .value = 0, .place = 0 }, .{ .value = 3, .place = 0 }, .{ .value = 2, .place = 3 } }, out.items);
+ // Masked: a view's row is its first byte's (sixteen-aligned).
+ out.clearRetainingCapacity();
+ join(&values, by_value.items, &keys, by_key.items, 14, ~@as(u64, 15), &out, gpa);
+ try std.testing.expectEqualSlices(Pair, &.{ .{ .value = 0, .place = 2 }, .{ .value = 3, .place = 2 }, .{ .value = 4, .place = 2 }, .{ .value = 2, .place = 3 } }, out.items);
+}
+
+test "the passes: off unless its knob is on, by priority, cut to the budget" {
+ var cands = [_]Candidate{
+ .{ .kind = .touch },
+ .{ .kind = .code, .rank = 2 },
+ .{ .kind = .link, .rank = 5 },
+ .{ .kind = .projection },
+ .{ .kind = .link, .rank = 1 },
+ .{ .kind = .thread },
+ .{ .kind = .code, .rank = 0 },
+ };
+ // The code kind is off by default: it goes; the rest are on.
+ var knobs = Knobs.initMany(&.{ .thread, .links, .always });
+ var kept = filter(&cands, knobs);
+ try std.testing.expectEqual(@as(usize, 5), kept.len);
+ byPriority(kept);
+ try std.testing.expectEqual(Kind.thread, kept[0].kind);
+ try std.testing.expectEqual(@as(u32, 1), kept[1].rank);
+ kept = cut(kept);
+ // One thread, one link (the first in the registers' order), one projection; the touch gives way.
+ try std.testing.expectEqual(@as(usize, 3), kept.len);
+ try std.testing.expectEqualSlices(Kind, &.{ .thread, .link, .projection }, &.{ kept[0].kind, kept[1].kind, kept[2].kind });
+ try std.testing.expectEqual(@as(u32, 1), kept[1].rank);
+ // With no projection the touch is drawn; with the knob on, one code pointer, the first in rank.
+ var more = [_]Candidate{ .{ .kind = .touch }, .{ .kind = .link }, .{ .kind = .code, .rank = 3 }, .{ .kind = .code, .rank = 1 } };
+ knobs.insert(.code);
+ kept = filter(&more, knobs);
+ byPriority(kept);
+ kept = cut(kept);
+ try std.testing.expectEqualSlices(Kind, &.{ .link, .touch, .code }, &.{ kept[0].kind, kept[1].kind, kept[2].kind });
+ try std.testing.expectEqual(@as(u32, 1), kept[2].rank);
+}