//! 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); }