summaryrefslogtreecommitdiff
path: root/anim/src/graph.zig
diff options
context:
space:
mode:
Diffstat (limited to 'anim/src/graph.zig')
-rw-r--r--anim/src/graph.zig1436
1 files changed, 1436 insertions, 0 deletions
diff --git a/anim/src/graph.zig b/anim/src/graph.zig
new file mode 100644
index 0000000..f4e61ea
--- /dev/null
+++ b/anim/src/graph.zig
@@ -0,0 +1,1436 @@
+//! `graph` (design/README.md, "graph"): the disassembly's other form, a
+//! function as its basic blocks with what the run did on them: how often
+//! each was entered, how often each edge was taken, the edges never taken,
+//! the last three taken (the trail), the block the pc is in. Execution
+//! flows down; the one thing that climbs is a loop's back edge.
+//!
+//! `read` takes a function's blocks from the recording (`zt.telescope.blocks`)
+//! and counts the run over them; `place` lays them out, a pure function of
+//! the blocks, their sizes and the counts of the whole recording (so the
+//! picture does not move as the counts grow): back edges by a walk from the
+//! entry in address order, layers by the longest forward path, in a layer
+//! each block under the predecessor that reached it most often (the hot
+//! path straight down), then under the one it falls from, a taken target
+//! to the right; back edges in their loops' lanes on the left, the
+//! outermost farthest out; an edge that would cross a block in the right
+//! channel. `layout` does both for a form (the map's rows, the lens's
+//! shapes), folding what is too big for its place in the catalogue's
+//! order: the runs of blocks the whole recording never reached, then long
+//! blocks. `Blocks` draws it as the `blocks` lens, `Map` with its rows on
+//! the map, `Rules` its blocks on the linear rows; `leave` (and `turn`) is
+//! the step across one edge.
+const std = @import("std");
+const sk = @import("sketch");
+const anim = @import("anim");
+const zt = @import("ztrace");
+const Recording = @import("Recording.zig");
+const ui = @import("ui.zig");
+const rows = @import("rows.zig");
+const cursors = @import("cursor.zig");
+const context = @import("context.zig");
+const disasm = @import("disasm.zig");
+const Stage = @import("stage.zig").Stage;
+const theme = ui.theme;
+const time = theme.time;
+const t = theme.color.text;
+
+pub const End = zt.Debugger.End;
+
+/// A block, or a fold of blocks never reached, and where it is drawn.
+pub const Node = struct {
+ start: u64,
+ len: u64,
+ end: End,
+ /// Where a tail call or a call that does not return goes (null: none, or not known).
+ out: ?u64 = null,
+ /// Its instructions (a fold's: of all its blocks).
+ rows: u32 = 0,
+ /// The rows drawn: a long block folded to its first four, `more` and its last four.
+ shown: u32 = 0,
+ /// How many blocks the whole recording never reached are folded into it (0: a block of its own).
+ folded: u32 = 0,
+ /// Times the run entered it, by the moment the graph is of; and in the whole recording.
+ visits: u32 = 0,
+ reached: bool = false,
+ layer: u32 = 0,
+ col: u32 = 0,
+ x: f32 = 0,
+ y: f32 = 0,
+ w: f32 = 0,
+ h: f32 = 0,
+
+ pub fn contains(n: Node, addr: u64) bool {
+ return addr -% n.start < n.len;
+ }
+};
+
+pub const Kind = enum { fall, taken, jump };
+
+pub const Edge = struct {
+ from: u32,
+ to: u32,
+ kind: Kind,
+ /// Times taken by the moment the graph is of; in the whole recording (what places the blocks).
+ count: u32 = 0,
+ total: u32 = 0,
+ /// To a block at its own layer or above: a loop's turn, in lane `lane` (0 the outermost).
+ back: bool = false,
+ lane: u32 = 0,
+ /// Its way, out of its block's bottom and into its target.
+ points: [6][2]f32 = undefined,
+ n: u8 = 0,
+
+ pub fn path(e: *const Edge) []const [2]f32 {
+ return e.points[0..e.n];
+ }
+
+ /// Its length along its way.
+ pub fn length(e: *const Edge) f32 {
+ var total: f32 = 0;
+ for (e.path()[0 .. e.n -| 1], e.path()[@min(1, e.n)..]) |a, b| total += @abs(b[0] - a[0]) + @abs(b[1] - a[1]);
+ return total;
+ }
+
+ /// The point `d` units along its way, and which way it goes there.
+ pub fn at(e: *const Edge, d: f32) struct { [2]f32, [2]f32 } {
+ var left = @max(d, 0);
+ const pts = e.path();
+ for (pts[0 .. pts.len - 1], pts[1..]) |a, b| {
+ const l = @abs(b[0] - a[0]) + @abs(b[1] - a[1]);
+ const dir = [2]f32{ std.math.sign(b[0] - a[0]), std.math.sign(b[1] - a[1]) };
+ if (left <= l or b[0] == pts[pts.len - 1][0] and b[1] == pts[pts.len - 1][1]) {
+ const f = if (l > 0) @min(left / l, 1) else 1;
+ return .{ .{ a[0] + (b[0] - a[0]) * f, a[1] + (b[1] - a[1]) * f }, dir };
+ }
+ left -= l;
+ }
+ return .{ pts[pts.len - 1], .{ 0, 1 } };
+ }
+};
+
+/// A function's graph at a moment.
+pub const Graph = struct {
+ start: u64,
+ len: u64,
+ nodes: []Node,
+ edges: []Edge,
+ /// The node the pc is in.
+ here: ?u32,
+ /// The last three edges taken, newest first.
+ trail: [3]?u32 = @splat(null),
+ /// Every instruction's text is recorded (a function of up to 2 048).
+ text: bool,
+ /// The recording stops at every instruction: the edges' counts and the trail are known.
+ exact: bool,
+ /// Its size, from its top left (the lanes' side).
+ w: f32 = 0,
+ h: f32 = 0,
+ /// The right channel's x, and how many lanes the back edges take.
+ channel: f32 = 0,
+ lanes: u32 = 0,
+ /// The blocks the function has, before any fold.
+ blocks: usize = 0,
+ /// How far apart the columns are.
+ pitch: f32 = 0,
+
+ pub fn nodeOf(g: Graph, addr: u64) ?u32 {
+ for (g.nodes, 0..) |n, i| if (n.contains(addr)) return @intCast(i);
+ return null;
+ }
+
+ pub fn edgeOf(g: Graph, from: u32, to: u32) ?u32 {
+ for (g.edges, 0..) |e, i| if (e.from == from and e.to == to) return @intCast(i);
+ return null;
+ }
+
+ /// How many blocks the folds hold.
+ pub fn foldedBlocks(g: Graph) usize {
+ var n: usize = 0;
+ for (g.nodes) |node| n += node.folded;
+ return n;
+ }
+};
+
+/// The sizes a form lays its graph out by (design/README.md, `metric.graph`).
+pub const Metric = struct {
+ layer_gap: f32,
+ block_gap: f32,
+ /// Columns are at least this far apart.
+ pitch: f32 = 0,
+ /// Lanes: the first this far in, then this far apart; the blocks this far right of the last.
+ lane_in: f32 = 24,
+ lane: f32,
+ blocks_in: f32,
+ /// The first layer, under the graph's top.
+ top: f32,
+ /// A port this far in from its block's side; arrivals into one top this far apart.
+ port: f32,
+ arrivals: f32,
+ /// The right channel, right of the widest layer.
+ channel: f32,
+ /// A back edge goes down this far before it turns to its lane, and enters its header this far down.
+ back_down: f32,
+ head_in: f32 = 12,
+ /// Edges sharing a gap run this far apart.
+ track: f32,
+};
+
+/// The disassembly's rows on the map, and the `blocks` lens's shapes.
+pub const Form = enum { map, lens };
+
+pub fn metricOf(form: Form) Metric {
+ const g = theme.metric.graph;
+ return switch (form) {
+ .map => .{ .layer_gap = g.layer_gap, .block_gap = g.block_gap, .pitch = theme.metric.insn.annotation - g.shift + g.note + g.block_gap, .lane = g.lane, .blocks_in = g.lane_in, .top = g.top, .port = g.port, .arrivals = g.arrivals, .channel = g.channel, .back_down = g.back_down, .track = 6 },
+ .lens => .{ .layer_gap = g.lens.layer_gap, .block_gap = g.block_gap, .pitch = g.lens.pitch, .lane = g.lens.lane, .blocks_in = g.lens.blocks_in, .top = g.lens.top, .port = g.lens.port, .arrivals = g.lens.port, .channel = g.lens.channel, .back_down = g.lens.back_down, .track = 4 },
+ };
+}
+
+// ---------------------------------------------------------------- reading
+
+/// The graph of the function that holds `pc`, at moment `i`: its blocks
+/// (padding no edge reaches left out), their edges by how each block ends,
+/// and what the run did on them by then (visits, edge counts, the trail)
+/// and in the whole recording (what it reached; the counts the layout is
+/// by). Unplaced. Null where the recording has no blocks for it.
+pub fn read(arena: std.mem.Allocator, rec: *const Recording, i: u64, pc: u64) ?Graph {
+ return readBlocks(arena, rec, i, pc) catch null;
+}
+
+fn readBlocks(arena: std.mem.Allocator, rec: *const Recording, i: u64, pc: u64) !?Graph {
+ const m = rec.moment(i);
+ const probe = zt.telescope.blocks(m, pc, &.{}) orelse return null;
+ const blocks = try arena.alloc(zt.telescope.Block, probe.count);
+ const found = zt.telescope.blocks(m, pc, blocks) orelse return null;
+ var nodes = try arena.alloc(Node, blocks.len);
+ for (blocks, nodes) |b, *n| n.* = .{ .start = b.start, .len = b.len, .end = b.end, .out = if (b.end == .tail or b.end == .noreturn) b.to else null };
+ // Every instruction's row, where the text is recorded; a block of
+ // padding alone (`nop`s between paths) that nothing goes to is none.
+ var reached_by = try arena.alloc(bool, blocks.len);
+ @memset(reached_by, false);
+ for (blocks) |b| for ([2]?u64{ b.to, b.falls }) |to| if (to) |at| if (blockAt(nodes, at)) |k| {
+ reached_by[k] = true;
+ };
+ var keep: usize = 0;
+ var buf: [256]u8 = undefined;
+ for (nodes, 0..) |*n, k| {
+ var at = n.start;
+ var padding = found.text;
+ while (found.text and at < n.start + n.len) : (n.rows += 1) {
+ const one = rec.instruction(i, at, &buf) orelse break;
+ padding = padding and std.mem.startsWith(u8, one.text, "nop");
+ at += one.len;
+ }
+ if (!found.text or n.rows == 0) n.rows = @intCast(@max(n.len / 4, 1));
+ n.shown = n.rows;
+ if (padding and !reached_by[k] and k > 0) continue;
+ nodes[keep] = n.*;
+ keep += 1;
+ }
+ nodes = nodes[0..keep];
+ var g: Graph = .{ .start = found.start, .len = found.len, .nodes = nodes, .edges = &.{}, .here = blockAt(nodes, pc), .text = found.text, .exact = false, .blocks = keep };
+ var edges: std.ArrayList(Edge) = .empty;
+ for (blocks) |b| {
+ const from = blockAt(nodes, b.start) orelse continue;
+ if (nodes[from].start != b.start) continue;
+ if (b.to) |to| if (b.end == .jump or b.end == .branch) if (blockAt(nodes, to)) |at| try edges.append(arena, .{ .from = from, .to = at, .kind = if (b.end == .jump) .jump else .taken });
+ if (b.falls) |to| if (blockAt(nodes, to)) |at| try edges.append(arena, .{ .from = from, .to = at, .kind = .fall });
+ }
+ g.edges = edges.items;
+ g.exact = stepsEach(rec, g);
+ count(rec, &g, i);
+ return g;
+}
+
+/// Whether the recording stopped at every instruction of the function:
+/// wherever one stop in it follows another in another block, the first was
+/// on the jump that went there, or on the last instruction of a block that
+/// falls into it. (By line a stop is where a line begins.)
+fn stepsEach(rec: *const Recording, g: Graph) bool {
+ var pairs: usize = 0;
+ var k: u64 = 0;
+ while (k + 1 < rec.len()) : (k += 1) {
+ const a = rec.registers[k].rip;
+ const b = rec.registers[k + 1].rip;
+ if (a == b) continue;
+ const from = blockAt(g.nodes, a) orelse continue;
+ const to = blockAt(g.nodes, b) orelse continue;
+ if (from == to and b != g.nodes[to].start) continue;
+ pairs += 1;
+ // A jump, a call of itself, a return into its caller.
+ if (rec.insn_branches[k]) |br| if (br.to == b or br.kind == .jump and !br.taken) continue;
+ const f = g.nodes[from];
+ if (f.end == .fall and b == f.start + f.len) continue;
+ return false;
+ }
+ return pairs > 0;
+}
+
+/// The function's blocks at moment `i` and how often the run had entered
+/// each by then: no rows, no edges. What the linear rows' block rules need.
+pub fn light(arena: std.mem.Allocator, rec: *const Recording, i: u64, pc: u64) ?Graph {
+ const m = rec.moment(i);
+ const probe = zt.telescope.blocks(m, pc, &.{}) orelse return null;
+ const blocks = arena.alloc(zt.telescope.Block, probe.count) catch return null;
+ const found = zt.telescope.blocks(m, pc, blocks) orelse return null;
+ const nodes = arena.alloc(Node, blocks.len) catch return null;
+ for (blocks, nodes) |b, *n| n.* = .{ .start = b.start, .len = b.len, .end = b.end };
+ var g: Graph = .{ .start = found.start, .len = found.len, .nodes = nodes, .edges = &.{}, .here = blockAt(nodes, pc), .text = found.text, .exact = false, .blocks = nodes.len };
+ g.exact = stepsEach(rec, g);
+ count(rec, &g, i);
+ return g;
+}
+
+/// The run over the graph: each block's visits and each edge's count, by
+/// moment `i` and in the whole recording; the blocks it ever reached; the
+/// last three edges taken by `i`. A block is entered at its start (by line,
+/// whenever a stop is in it after one in another block); an edge is
+/// counted where one stop in the function follows another across it (by
+/// instruction only: by line the stops between are not known).
+fn count(rec: *const Recording, g: *Graph, i: u64) void {
+ countBy(rec, g, i, true);
+}
+
+/// `count`; `whole`: the whole recording's too (what it reached, the totals the layout is by).
+fn countBy(rec: *const Recording, g: *Graph, i: u64, whole: bool) void {
+ var prev: ?u32 = null;
+ var prev_pc: u64 = 0;
+ var trail: [3]?u32 = @splat(null);
+ for (rec.registers, 0..) |regs, k| {
+ if (!whole and k > i) break;
+ const pc = regs.rip;
+ if (pc -% g.start >= g.len) continue;
+ const b = blockAt(g.nodes, pc) orelse continue;
+ const n = &g.nodes[b];
+ if (whole) n.reached = true;
+ // The first stop in it (a recording that begins inside it) is an entry too.
+ const entered = prev == null or if (g.exact) pc == n.start and prev_pc != pc else prev.? != b;
+ if (entered) {
+ if (k <= i) n.visits += 1;
+ if (g.exact) if (prev) |p| if (g.edgeOf(p, b)) |e| {
+ if (whole) g.edges[e].total += 1;
+ if (k <= i) {
+ g.edges[e].count += 1;
+ trail = .{ e, trail[0], trail[1] };
+ }
+ };
+ }
+ prev = b;
+ prev_pc = pc;
+ }
+ g.trail = trail;
+}
+
+/// The node holding `addr`, in nodes in address order.
+fn blockAt(nodes: []const Node, addr: u64) ?u32 {
+ var lo: usize = 0;
+ var hi: usize = nodes.len;
+ while (lo < hi) {
+ const mid = (lo + hi) / 2;
+ if (nodes[mid].start <= addr) lo = mid + 1 else hi = mid;
+ }
+ if (lo == 0 or !nodes[lo - 1].contains(addr)) return null;
+ return @intCast(lo - 1);
+}
+
+/// The blocks the whole recording never reached, each connected run of them
+/// (neighbours in address order joined by an edge) one node (`folded` its
+/// blocks, its rows all theirs), the edges to and from them joined. A run
+/// that would make a loop the code does not have (an edge into its middle
+/// from a block its rest cannot reach again) is split there.
+pub fn fold(arena: std.mem.Allocator, g: *Graph) !void {
+ const n = g.nodes.len;
+ // Where a run begins: at every unreached block not joined to the one before it.
+ const begins = try arena.alloc(bool, n);
+ for (begins, 0..) |*b, k| b.* = g.nodes[k].reached or k == 0 or g.nodes[k - 1].reached or !joined(g.*, @intCast(k - 1), @intCast(k));
+ const into = try arena.alloc(u32, n);
+ var folded: Graph = undefined;
+ for (0..8) |_| {
+ folded = try foldRuns(arena, g.*, begins, into);
+ var buf: [1 << 14]u8 = undefined;
+ var fba = std.heap.FixedBufferAllocator.init(&buf);
+ try backEdges(&folded, fba.allocator());
+ var split = false;
+ for (g.edges) |e| {
+ const a = into[e.from];
+ const b = into[e.to];
+ if (a == b or begins[e.to] or folded.nodes[b].folded == 0) continue;
+ const f = folded.edgeOf(a, b) orelse continue;
+ if (!folded.edges[f].back or reaches(g.*, e.to, e.from)) continue;
+ begins[e.to] = true;
+ split = true;
+ }
+ if (!split) break;
+ }
+ g.* = folded;
+}
+
+/// Whether blocks `a` and `b` have an edge between them, either way.
+fn joined(g: Graph, a: u32, b: u32) bool {
+ for (g.edges) |e| if (e.from == a and e.to == b or e.from == b and e.to == a) return true;
+ return false;
+}
+
+/// Whether block `to` can be reached from block `from` along the edges.
+fn reaches(g: Graph, from: u32, to: u32) bool {
+ var buf: [1 << 14]u8 = undefined;
+ var fba = std.heap.FixedBufferAllocator.init(&buf);
+ const seen = fba.allocator().alloc(bool, g.nodes.len) catch return true;
+ @memset(seen, false);
+ var stack: std.ArrayList(u32) = .empty;
+ stack.append(fba.allocator(), from) catch return true;
+ seen[from] = true;
+ while (stack.pop()) |at| {
+ if (at == to) return true;
+ for (g.edges) |e| if (e.from == at and !seen[e.to]) {
+ seen[e.to] = true;
+ stack.append(fba.allocator(), e.to) catch return true;
+ };
+ }
+ return false;
+}
+
+/// `g` with each run of unreached blocks (from a block `begins` to the next) one node; `into` each block's node.
+fn foldRuns(arena: std.mem.Allocator, g: Graph, begins: []const bool, into: []u32) !Graph {
+ var nodes: std.ArrayList(Node) = .empty;
+ for (g.nodes, 0..) |node, k| {
+ if (begins[k]) {
+ into[k] = @intCast(nodes.items.len);
+ var kept = node;
+ if (!node.reached) kept.folded = 1;
+ try nodes.append(arena, kept);
+ continue;
+ }
+ const f = &nodes.items[nodes.items.len - 1];
+ into[k] = @intCast(nodes.items.len - 1);
+ f.len = node.start + node.len - f.start;
+ f.rows += node.rows;
+ f.folded += 1;
+ }
+ for (nodes.items) |*f| if (f.folded > 0) {
+ f.end = .fall;
+ f.out = null;
+ f.shown = 1;
+ };
+ var edges: std.ArrayList(Edge) = .empty;
+ for (g.edges) |e| {
+ const a = into[e.from];
+ const b = into[e.to];
+ if (a == b) continue;
+ const dup = for (edges.items) |*d| {
+ if (d.from == a and d.to == b) break d;
+ } else null;
+ if (dup) |d| {
+ d.count += e.count;
+ d.total += e.total;
+ continue;
+ }
+ var kept = e;
+ kept.from = a;
+ kept.to = b;
+ kept.back = false;
+ try edges.append(arena, kept);
+ }
+ var out = g;
+ out.nodes = nodes.items;
+ out.edges = edges.items;
+ // The trail and the pc's block, renumbered.
+ for (&out.trail) |*tr| if (tr.*) |e| {
+ const old = g.edges[e];
+ tr.* = out.edgeOf(into[old.from], into[old.to]);
+ };
+ if (g.here) |h| out.here = into[h];
+ return out;
+}
+
+/// How far down a graph `room` high is scrolled with the pc in node
+/// `here`: not at all where it fits; else the largest loop the pc's block
+/// is in that fits, in the middle; else the pc's block in the middle.
+pub fn pan(g: Graph, room: f32, m: Metric) f32 {
+ if (g.h <= room) return 0;
+ const h = g.here orelse return 0;
+ const pc = g.nodes[h];
+ var top = pc.y - m.layer_gap / 2;
+ var bottom = pc.y + pc.h + m.layer_gap / 2;
+ var widest: f32 = 0;
+ for (g.edges) |e| if (e.back) {
+ const head = g.nodes[e.to];
+ const tail = g.nodes[e.from];
+ if (pc.layer < head.layer or pc.layer > tail.layer) continue;
+ var lb: f32 = 0;
+ for (g.nodes) |o| if (o.layer >= head.layer and o.layer <= tail.layer) {
+ lb = @max(lb, o.y + o.h);
+ };
+ const lt = head.y - m.layer_gap / 2;
+ lb += m.back_down + m.layer_gap / 2;
+ if (lb - lt <= room and lb - lt > widest) {
+ widest = lb - lt;
+ top = lt;
+ bottom = lb;
+ }
+ };
+ // Whole layers: the top of the one nearest where that would put the view's top.
+ const want = std.math.clamp((top + bottom - room) / 2, 0, g.h - room);
+ var best: f32 = 0;
+ for (g.nodes) |o| {
+ const at = std.math.clamp(o.y - m.top, 0, g.h - room);
+ if (@abs(at - want) < @abs(best - want)) best = at;
+ }
+ return best;
+}
+
+/// The linear rows' blocks (`disasm`, `descent`): a 2-unit rule across
+/// over each block's first row (not its function's), and where the row's
+/// annotation leaves it free the times the run had entered the block,
+/// ranged right, faint (`×11`), crossfading from the moment the mark
+/// leaves to the one it goes to.
+pub const Rules = struct {
+ of: [2]?Graph,
+ going: f32,
+
+ /// The blocks of the functions that hold `pc[0]` at `marks[0]` and `pc[1]` at `marks[1]`, `going` of the way between.
+ pub fn init(arena: std.mem.Allocator, rec: *const Recording, marks: [2]u64, pc: [2]u64, going: f32) Rules {
+ return .{ .of = .{ light(arena, rec, marks[0], pc[0]), light(arena, rec, marks[1], pc[1]) }, .going = going };
+ }
+
+ pub fn draw(r: Rules, u: ui.Ui, addr: u64, y: f32, w: f32, free: bool) void {
+ var visits: [2]?u32 = .{ null, null };
+ for (r.of, &visits) |maybe, *v| if (maybe) |g| if (blockAt(g.nodes, addr)) |k| if (g.nodes[k].start == addr and addr != g.start) {
+ v.* = g.nodes[k].visits;
+ };
+ if (visits[0] == null and visits[1] == null) return;
+ u.fill(.{ .x = theme.stroke.rule, .y = y, .w = w - 2 * theme.stroke.rule, .h = theme.stroke.rule }, theme.color.rule);
+ if (!free) return;
+ const size = theme.size.mono.context;
+ // The count the mark leaves, then the one it goes to; one that does not change, once.
+ const same = (visits[0] orelse 0) == (visits[1] orelse 0);
+ for (visits, [2]f32{ 1 - r.going, r.going }, 0..) |v, shows, k| {
+ const n = v orelse 0;
+ if (n == 0 or (same and k == 0)) continue;
+ const text = u.print("\u{00d7}{d}", .{n});
+ u.faded(if (same) 1 else shows).text(.mono, size, w - theme.metric.context.side - u.width(.mono, size, text), rows.baseline(y), text, theme.color.text.faint);
+ }
+ }
+};
+
+// ---------------------------------------------------------------- layout
+
+/// The graph of the pc's function at moment `i`, laid out for `form` in a
+/// place `room` high: folded first where it does not fit (the runs never
+/// reached, then long blocks: over 16 rows, their first four and last
+/// four, unless the pc is in it). Sizes from the form (`sizes`).
+/// shortcut: a loop the pc is not in and will not enter again is not folded, and nothing pans: a graph still too tall runs past its place.
+pub fn layout(arena: std.mem.Allocator, rec: *const Recording, i: u64, pc: u64, form: Form, room: f32) ?Graph {
+ const start = (zt.telescope.blocks(rec.moment(i), pc, &.{}) orelse return null).start;
+ for (memo) |maybe| if (maybe) |k| if (k.rec == rec and k.start == start and k.form == form and k.room == room) {
+ const here = blockAt(k.g.nodes, pc);
+ const spare: ?u32 = if (here) |h| (if (k.g.nodes[h].rows > theme.metric.graph.long) h else null) else null;
+ if (!k.long or spare == k.spared) return recount(arena, rec, k.g, i, pc) catch null;
+ };
+ var g = read(arena, rec, i, pc) orelse return null;
+ const m = metricOf(form);
+ sizes(rec, i, &g, form);
+ place(&g, m);
+ var long = false;
+ if (g.h > room) {
+ fold(arena, &g) catch return null;
+ sizes(rec, i, &g, form);
+ place(&g, m);
+ }
+ if (g.h > room) {
+ long = true;
+ for (g.nodes, 0..) |*n, k| if (n.folded == 0 and n.rows > theme.metric.graph.long and (g.here == null or g.here.? != k)) {
+ n.shown = 2 * theme.metric.graph.keep + 1;
+ };
+ sizes(rec, i, &g, form);
+ place(&g, m);
+ }
+ remember(.{ .rec = rec, .start = start, .form = form, .room = room, .long = long, .spared = if (g.here) |h| (if (g.nodes[h].rows > theme.metric.graph.long) h else null) else null, .g = g });
+ return g;
+}
+
+/// What `layout` made, kept: the blocks, their sizes and their places are
+/// the function's and the whole recording's, not the moment's (but for a
+/// long block the pc is in, which does not fold); a frame counts its own
+/// moment's visits again (`recount`).
+/// shortcut: process-wide, the last eight kept and never freed (a few KB each); two players at once would only share it.
+const Kept = struct { rec: *const Recording, start: u64, form: Form, room: f32, long: bool, spared: ?u32, g: Graph };
+var memo: [8]?Kept = @splat(null);
+var memo_next: usize = 0;
+var memo_memory: std.heap.ArenaAllocator = .init(std.heap.page_allocator);
+
+fn remember(k: Kept) void {
+ var copy = k;
+ const a = memo_memory.allocator();
+ copy.g.nodes = a.dupe(Node, k.g.nodes) catch return;
+ copy.g.edges = a.dupe(Edge, k.g.edges) catch return;
+ memo[memo_next] = copy;
+ memo_next = (memo_next + 1) % memo.len;
+}
+
+/// A kept graph with the run counted again by moment `i`, the pc at `pc`.
+fn recount(arena: std.mem.Allocator, rec: *const Recording, kept_g: Graph, i: u64, pc: u64) !Graph {
+ var g = kept_g;
+ g.nodes = try arena.dupe(Node, kept_g.nodes);
+ g.edges = try arena.dupe(Edge, kept_g.edges);
+ for (g.nodes) |*n| n.visits = 0;
+ for (g.edges) |*e| e.count = 0;
+ g.here = blockAt(g.nodes, pc);
+ countBy(rec, &g, i, false);
+ return g;
+}
+
+/// Each node's size in `form`: on the map a head and its rows, as wide as
+/// its widest row, 300 at least; in the lens a box 24 high, 10 a row. A
+/// fold: a dashed box of a head and a row.
+pub fn sizes(rec: *const Recording, i: u64, g: *Graph, form: Form) void {
+ const gm = theme.metric.graph;
+ const cm = theme.metric.context;
+ const adv = theme.size.mono.context * 3 / 5;
+ var buf: [256]u8 = undefined;
+ for (g.nodes) |*n| switch (form) {
+ .lens => {
+ n.w = @max(gm.lens.least, gm.lens.lead + gm.lens.per_row * @as(f32, @floatFromInt(n.rows)));
+ n.h = gm.lens.box;
+ },
+ .map => {
+ if (n.folded > 0) {
+ n.w = gm.fold_w;
+ n.h = cm.tag + cm.row + cm.pad;
+ continue;
+ }
+ var widest: usize = 0;
+ var at = n.start;
+ while (g.text and at < n.start + n.len) {
+ const one = rec.instruction(i, at, &buf) orelse break;
+ widest = @max(widest, operandChars(one.text));
+ at += one.len;
+ }
+ n.w = @max(gm.least, gm.operands + @as(f32, @floatFromInt(widest)) * adv + 2 * cm.side);
+ n.h = cm.tag + @as(f32, @floatFromInt(n.shown)) * cm.row + cm.pad;
+ },
+ };
+}
+
+/// How many characters an instruction's operands take as `insn` draws them:
+/// the size words gone, a jump's or call's target its digits, byte cells a few more.
+fn operandChars(text: []const u8) usize {
+ const space = std.mem.indexOfScalar(u8, text, ' ') orelse return 0;
+ var ops = std.mem.trim(u8, text[space..], " ");
+ // A prefix (`rep stosq`, `notrack jmp`): the mnemonic is the next word.
+ for ([_][]const u8{ "rep", "repe", "repz", "repne", "repnz", "lock", "notrack", "bnd" }) |p| if (std.mem.eql(u8, text[0..space], p)) {
+ ops = std.mem.trim(u8, ops[std.mem.indexOfScalar(u8, ops, ' ') orelse ops.len ..], " ");
+ };
+ var n = ops.len;
+ var rest = ops;
+ while (std.mem.indexOf(u8, rest, " ptr ")) |p| {
+ var word = p;
+ while (word > 0 and rest[word - 1] != ' ' and rest[word - 1] != ',') word -= 1;
+ // The word and " ptr " go; the width's cells come.
+ n = n - (p - word + 5) + 5;
+ rest = rest[p + 5 ..];
+ }
+ return n;
+}
+
+/// Lays `g` out (its nodes' `w` and `h` given): layers, columns, every
+/// edge's way. Pure: the same blocks, sizes and whole-recording counts
+/// give the same picture at every moment.
+pub fn place(g: *Graph, m: Metric) void {
+ const nodes = g.nodes;
+ if (nodes.len == 0) return;
+ var buf: [1 << 16]u8 = undefined;
+ var fba = std.heap.FixedBufferAllocator.init(&buf);
+ const tmp = fba.allocator();
+ backEdges(g, tmp) catch return;
+ layers(g, tmp) catch return;
+ columns(g, tmp) catch return;
+ // Lanes: the outermost loop (the longest span) farthest out.
+ var order: [64]u32 = undefined;
+ var nb: u32 = 0;
+ for (g.edges, 0..) |e, k| if (e.back and nb < order.len) {
+ order[nb] = @intCast(k);
+ nb += 1;
+ };
+ std.mem.sort(u32, order[0..nb], g, struct {
+ fn wider(gr: *Graph, a: u32, b: u32) bool {
+ const ea = gr.edges[a];
+ const eb = gr.edges[b];
+ const sa = gr.nodes[ea.from].layer - gr.nodes[ea.to].layer;
+ const sb = gr.nodes[eb.from].layer - gr.nodes[eb.to].layer;
+ return if (sa != sb) sa > sb else ea.to < eb.to;
+ }
+ }.wider);
+ for (order[0..nb], 0..) |e, k| g.edges[e].lane = @intCast(k);
+ g.lanes = nb;
+ // Columns a pitch apart, right of the lanes; layers a gap apart.
+ var widest: f32 = 0;
+ var last_layer: u32 = 0;
+ for (nodes) |n| {
+ widest = @max(widest, n.w);
+ last_layer = @max(last_layer, n.layer);
+ }
+ const pitch = @max(m.pitch, widest + m.block_gap);
+ g.pitch = pitch;
+ const x0 = m.lane_in + @as(f32, @floatFromInt(nb)) * m.lane + m.blocks_in;
+ const tops = tmp.alloc(f32, last_layer + 2) catch return;
+ const heights = tmp.alloc(f32, last_layer + 1) catch return;
+ @memset(heights, 0);
+ for (nodes) |n| heights[n.layer] = @max(heights[n.layer], n.h);
+ tops[0] = m.top;
+ for (heights, 0..) |h, k| tops[k + 1] = tops[k] + h + m.layer_gap;
+ var right: f32 = 0;
+ var bottom: f32 = 0;
+ for (nodes) |*n| {
+ n.x = x0 + @as(f32, @floatFromInt(n.col)) * pitch;
+ n.y = tops[n.layer];
+ right = @max(right, n.x + n.w);
+ bottom = @max(bottom, n.y + n.h);
+ }
+ g.channel = right + m.channel;
+ route(g, m, tops, heights, tmp) catch return;
+ g.w = g.channel + m.lane_in;
+ // Under the last layer the way out: a stub and a bar.
+ g.h = bottom + m.layer_gap;
+}
+
+/// Back edges: those a walk from the entry (then from each block not yet
+/// walked, in address order) finds going to a block on the walk's way.
+fn backEdges(g: *Graph, tmp: std.mem.Allocator) !void {
+ const n = g.nodes.len;
+ const state = try tmp.alloc(u8, n);
+ @memset(state, 0);
+ // Each node's out edges, by their targets' addresses.
+ const outs = try outEdges(g, tmp);
+ const Frame = struct { node: u32, next: u32 };
+ var stack: std.ArrayList(Frame) = .empty;
+ for (0..n) |root| {
+ if (state[root] != 0) continue;
+ state[root] = 1;
+ try stack.append(tmp, .{ .node = @intCast(root), .next = 0 });
+ while (stack.items.len > 0) {
+ const top = &stack.items[stack.items.len - 1];
+ const list = outs[top.node];
+ if (top.next == list.len) {
+ state[top.node] = 2;
+ _ = stack.pop();
+ continue;
+ }
+ const e = list[top.next];
+ top.next += 1;
+ const to = g.edges[e].to;
+ if (state[to] == 1) {
+ g.edges[e].back = true;
+ } else if (state[to] == 0) {
+ state[to] = 1;
+ try stack.append(tmp, .{ .node = to, .next = 0 });
+ }
+ }
+ }
+}
+
+fn outEdges(g: *const Graph, tmp: std.mem.Allocator) ![][]u32 {
+ const outs = try tmp.alloc([]u32, g.nodes.len);
+ const counts = try tmp.alloc(u32, g.nodes.len);
+ @memset(counts, 0);
+ for (g.edges) |e| counts[e.from] += 1;
+ for (outs, counts) |*o, c| o.* = try tmp.alloc(u32, c);
+ @memset(counts, 0);
+ for (g.edges, 0..) |e, k| {
+ outs[e.from][counts[e.from]] = @intCast(k);
+ counts[e.from] += 1;
+ }
+ for (outs) |o| std.mem.sort(u32, o, g, struct {
+ fn first(gr: *const Graph, a: u32, b: u32) bool {
+ return gr.nodes[gr.edges[a].to].start < gr.nodes[gr.edges[b].to].start;
+ }
+ }.first);
+ return outs;
+}
+
+/// Layers by the longest forward path from a block with none into it; the
+/// blocks that return in the last (one more where another is there).
+fn layers(g: *Graph, tmp: std.mem.Allocator) !void {
+ const n = g.nodes.len;
+ const ins = try tmp.alloc(u32, n);
+ @memset(ins, 0);
+ for (g.edges) |e| if (!e.back) {
+ ins[e.to] += 1;
+ };
+ var ready: std.ArrayList(u32) = .empty;
+ for (ins, 0..) |c, k| if (c == 0) try ready.append(tmp, @intCast(k));
+ for (g.nodes) |*node| node.layer = 0;
+ var head: usize = 0;
+ while (head < ready.items.len) : (head += 1) {
+ const a = ready.items[head];
+ for (g.edges) |e| if (!e.back and e.from == a) {
+ g.nodes[e.to].layer = @max(g.nodes[e.to].layer, g.nodes[a].layer + 1);
+ ins[e.to] -= 1;
+ if (ins[e.to] == 0) try ready.append(tmp, e.to);
+ };
+ }
+ var last: u32 = 0;
+ for (g.nodes) |node| if (node.end != .ret) {
+ last = @max(last, node.layer);
+ };
+ var any_ret = false;
+ for (g.nodes) |node| any_ret = any_ret or node.end == .ret;
+ if (!any_ret) return;
+ var deepest_ret: u32 = 0;
+ for (g.nodes) |node| if (node.end == .ret) {
+ deepest_ret = @max(deepest_ret, node.layer);
+ };
+ const others_last = for (g.nodes) |node| {
+ if (node.end != .ret and node.layer == @max(last, deepest_ret)) break true;
+ } else false;
+ const at = @max(last, deepest_ret) + @intFromBool(others_last);
+ for (g.nodes) |*node| if (node.end == .ret) {
+ node.layer = at;
+ };
+}
+
+/// Columns, a layer at a time: a block under the predecessor that reached
+/// it most often in the whole recording; else under the one it falls from;
+/// else (a taken target never taken) right of it. Where two want one
+/// column the more travelled has it, then the fall-through, then the
+/// lower address; the other the next free column to the right.
+fn columns(g: *Graph, tmp: std.mem.Allocator) !void {
+ const n = g.nodes.len;
+ var last: u32 = 0;
+ for (g.nodes) |node| last = @max(last, node.layer);
+ const Want = struct { node: u32, col: u32, total: u32, fall: bool };
+ var wants: std.ArrayList(Want) = .empty;
+ var used: std.ArrayList(u32) = .empty;
+ const placed = try tmp.alloc(bool, n);
+ @memset(placed, false);
+ for (0..last + 1) |layer| {
+ wants.clearRetainingCapacity();
+ for (g.nodes, 0..) |node, k| if (node.layer == layer) {
+ var best: ?Edge = null;
+ for (g.edges) |e| if (!e.back and e.to == k and placed[e.from]) {
+ const better = if (best) |b| e.total > b.total or (e.total == b.total and (e.kind == .fall and b.kind != .fall or (e.kind == .fall) == (b.kind == .fall) and g.nodes[e.from].start < g.nodes[b.from].start)) else true;
+ if (better) best = e;
+ };
+ const col: u32, const total: u32, const fall = if (best) |b|
+ .{ g.nodes[b.from].col + @intFromBool(b.total == 0 and b.kind != .fall), b.total, b.kind == .fall }
+ else
+ .{ 0, 0, false };
+ try wants.append(tmp, .{ .node = @intCast(k), .col = col, .total = total, .fall = fall });
+ };
+ std.mem.sort(Want, wants.items, g, struct {
+ fn first(gr: *Graph, a: Want, b: Want) bool {
+ if (a.total != b.total) return a.total > b.total;
+ if (a.fall != b.fall) return a.fall;
+ return gr.nodes[a.node].start < gr.nodes[b.node].start;
+ }
+ }.first);
+ used.clearRetainingCapacity();
+ for (wants.items) |w| {
+ var col = w.col;
+ while (std.mem.indexOfScalar(u32, used.items, col) != null) col += 1;
+ try used.append(tmp, col);
+ g.nodes[w.node].col = col;
+ placed[w.node] = true;
+ }
+ }
+}
+
+/// Every edge's way. Forward: out of the bottom on the side its target is
+/// on (`port` in from it, or the middle when it is straight below), along
+/// the middle of the gap under its layer, into its target's top (several
+/// into one top `arrivals` apart, in their sources' order); through the
+/// right channel where it would cross a block. Back: down `back_down`, out
+/// to its lane, up it, into its header's head from the left.
+fn route(g: *Graph, m: Metric, tops: []const f32, heights: []const f32, tmp: std.mem.Allocator) !void {
+ const n = g.nodes.len;
+ const tracks = try tmp.alloc(u32, heights.len);
+ @memset(tracks, 0);
+ const back_tracks = try tmp.alloc(u32, heights.len);
+ @memset(back_tracks, 0);
+ // The nodes by layer, then left to right: the edges of one gap take its tracks in that order.
+ const order = try tmp.alloc(u32, n);
+ for (order, 0..) |*o, k| o.* = @intCast(k);
+ std.mem.sort(u32, order, g, struct {
+ fn first(gr: *Graph, a: u32, b: u32) bool {
+ const na = gr.nodes[a];
+ const nb = gr.nodes[b];
+ return if (na.layer != nb.layer) na.layer < nb.layer else na.x < nb.x;
+ }
+ }.first);
+ for (order) |a| for (g.edges) |*e| if (e.from == a) {
+ const src = g.nodes[e.from];
+ const dst = g.nodes[e.to];
+ const under = tops[src.layer] + heights[src.layer];
+ if (e.back) {
+ const lx = m.lane_in + @as(f32, @floatFromInt(e.lane)) * m.lane;
+ const by = under + m.back_down + @as(f32, @floatFromInt(back_tracks[src.layer])) * 8;
+ back_tracks[src.layer] += 1;
+ const sx = src.x + m.port;
+ const hy = dst.y + m.head_in;
+ e.points[0..5].* = .{ .{ sx, src.y + src.h }, .{ sx, by }, .{ lx, by }, .{ lx, hy }, .{ dst.x - 1, hy } };
+ e.n = 5;
+ continue;
+ }
+ // Its place among the arrivals into its target's top.
+ var srcs: usize = 0;
+ var slot: usize = 0;
+ for (g.edges) |o| if (!o.back and o.to == e.to) {
+ srcs += 1;
+ const os = g.nodes[o.from];
+ if (os.x < src.x or (os.x == src.x and o.from < e.from)) slot += 1;
+ };
+ const tx = dst.x + dst.w / 2 + (@as(f32, @floatFromInt(slot)) - @as(f32, @floatFromInt(srcs - 1)) / 2) * m.arrivals;
+ const crosses = for (g.nodes) |o| {
+ if (o.layer > src.layer and o.layer < dst.layer and o.x - 8 < tx and tx < o.x + o.w + 8) break true;
+ } else false;
+ const side = if (crosses) 1 else (dst.x + dst.w / 2) - (src.x + src.w / 2);
+ const sx = if (!crosses and @abs(side) < src.w / 2 - m.port) src.x + src.w / 2 else if (side > 0) src.x + src.w - m.port else src.x + m.port;
+ const gy = under + m.layer_gap / 2 + @as(f32, @floatFromInt(tracks[src.layer])) * m.track;
+ tracks[src.layer] += 1;
+ if (crosses) {
+ const gy2 = tops[dst.layer] - m.layer_gap / 2;
+ e.points = .{ .{ sx, src.y + src.h }, .{ sx, gy }, .{ g.channel, gy }, .{ g.channel, gy2 }, .{ tx, gy2 }, .{ tx, dst.y } };
+ e.n = 6;
+ } else {
+ e.points[0..4].* = .{ .{ sx, src.y + src.h }, .{ sx, gy }, .{ tx, gy }, .{ tx, dst.y } };
+ e.n = 4;
+ }
+ };
+}
+
+// ---------------------------------------------------------------- an instant
+
+/// The graph as a frame shows it: at the stop shown (`g`, where everything
+/// is) and the stop the step came from (`was`, the same function), `p` of
+/// the way from the one to the other; a walked step across one edge is
+/// `leave`'s (or `turn`'s) frames; the panel's scroll.
+pub const Instant = struct {
+ g: Graph,
+ was: Graph,
+ p: f32,
+ leave: ?Leave = null,
+ pan: f32 = 0,
+ now: cursors.Now,
+};
+
+/// A step across one edge, at a walk (`leave`, `turn`): the edge drawn gold
+/// (`draw`, 0 to 1), the mark along it (`travel`), seconds since it landed.
+pub const Leave = struct { edge: u32, draw: f32, travel: f32, landed: f32 };
+
+/// The graph of the function the pc is in, in `form`, in a place `room` high, now.
+pub fn instant(arena: std.mem.Allocator, now: cursors.Now, form: Form, room: f32) ?Instant {
+ const rec = now.rec;
+ const at = [2]u64{ now.stops[1], now.stops[0] };
+ const pc = [2]u64{ rec.register(at[0], "rip"), rec.register(at[1], "rip") };
+ const g = layout(arena, rec, at[1], pc[1], form, room) orelse return null;
+ var was = g;
+ if (at[0] != at[1] and pc[0] -% g.start < g.len) was = layout(arena, rec, at[0], pc[0], form, room) orelse g;
+ // shortcut: a step into another function changes the graph in a frame (no crossfade between two); scenes keep to one.
+ if (was.nodes.len != g.nodes.len or was.edges.len != g.edges.len) was = g;
+ var out: Instant = .{ .g = g, .was = was, .p = now.advancing(), .now = now };
+ const m = metricOf(form);
+ var q = out.p;
+ // One instruction across an edge, walked: its frames are `leave`'s.
+ if (now.walking() and at[1] == at[0] + 1) if (was.here) |a| if (g.here) |b| if (a != b or pc[1] == g.nodes[b].start) if (g.edgeOf(a, b)) |e| {
+ const l = time.leave;
+ const plan = now.plan;
+ out.leave = .{
+ .edge = e,
+ .draw = cursors.standard(clamp01((now.time - (plan.advance - l.edge)) / l.edge)),
+ .travel = cursors.glide(clamp01((now.time - plan.advance) / @max(plan.travel, 1.0 / 60.0))),
+ .landed = now.time - plan.advance - plan.travel,
+ };
+ q = out.leave.?.travel;
+ };
+ out.pan = std.math.lerp(pan(was, room, m), pan(g, room, m), cursors.glide(q));
+ return out;
+}
+
+fn clamp01(v: f32) f32 {
+ return std.math.clamp(v, 0, 1);
+}
+
+/// How long the mark takes along edge `e`: 12 f and 2 f a 100 units, 30 f at most.
+pub fn markTime(e: *const Edge) f32 {
+ const l = time.leave;
+ return @min(l.mark + l.per_100 * e.length() / 100, l.mark_most);
+}
+
+/// `leave` (and `turn`, the same along a loop's lane): from a stop on a
+/// block's last instruction (a jump; or one that falls into the next
+/// block), one step across the edge it takes, to motion.md's frames: fire;
+/// the compare's chips framed as read (the CPU's slot, 18 f), the cause;
+/// the edge drawn gold, head first (24 to 42 f); the mark along it, 12 f
+/// and 2 f a 100 units of the lens's edge (30 f at most); landing, the
+/// advance; the target's count struck 6 f after (a turn's lane count as it
+/// lands); the oldest trail edge cooled (18 f); a rest to 42 f after the landing.
+pub fn leave(c: cursors.Cursor, s: *anim.Frame) void {
+ const from = c.moment(s);
+ const to = from + 1;
+ const l = time.leave;
+ var buf: [1 << 18]u8 = undefined;
+ var fba = std.heap.FixedBufferAllocator.init(&buf);
+ const rec = c.rec;
+ var mark: f32 = l.mark;
+ if (layout(fba.allocator(), rec, to, rec.register(to, "rip"), .lens, std.math.inf(f32))) |g| {
+ if (blockAt(g.nodes, rec.register(from, "rip"))) |a| if (g.here) |b| if (g.edgeOf(a, b)) |e| {
+ mark = markTime(&g.edges[e]);
+ };
+ }
+ const plan: cursors.Plan = .{ .at = @splat(l.chips), .advance = l.sets_off, .travel = mark, .total = l.sets_off + mark + l.rest };
+ c.step(s, to, plan, plan.total);
+}
+
+/// The stop on the last instruction of the block the cursor is in (where
+/// a `leave` sets off): the first moment from `from` at a jump in its
+/// function, or before a stop in another of its blocks.
+pub fn blockEnd(rec: *const Recording, from: u64) u64 {
+ var buf: [1 << 16]u8 = undefined;
+ var fba = std.heap.FixedBufferAllocator.init(&buf);
+ const g = light(fba.allocator(), rec, from, rec.register(from, "rip")) orelse return from;
+ var k = from;
+ while (k + 1 < rec.len()) : (k += 1) {
+ const pc = rec.register(k, "rip");
+ const here = blockAt(g.nodes, pc) orelse continue;
+ if (rec.insn_branches[k]) |b| if (b.kind == .jump or b.kind == .ret) return k;
+ const next = blockAt(g.nodes, rec.register(k + 1, "rip")) orelse continue;
+ if (next != here) return k;
+ }
+ return k;
+}
+
+/// One step from where the cursor is to the end of its block (`blockEnd`), walked: what the block does, as a cascade.
+pub fn toEnd(c: cursors.Cursor, s: *anim.Frame) void {
+ const from = c.moment(s);
+ const to = blockEnd(c.rec, from);
+ if (to == from) return;
+ const plan = c.reading(from, to);
+ c.step(s, to, plan, plan.total);
+}
+
+/// An edge's look in `g`: never taken `rule`, taken `dim`, the last three
+/// taken the trail's golds (the newest 3 wide). By line, all `rule`.
+fn edgeLook(g: Graph, e: u32) struct { ink: u24, w: f32 } {
+ const tr = theme.color.trail;
+ if (!g.exact) return .{ .ink = theme.color.rule, .w = theme.stroke.rule };
+ for (g.trail, 0..) |maybe, k| if (maybe) |te| if (te == e) return .{ .ink = tr[k], .w = if (k == 0) 3 else theme.stroke.rule };
+ return .{ .ink = if (g.edges[e].count > 0) t.dim else theme.color.rule, .w = theme.stroke.rule };
+}
+
+/// A count written as the mark lands: armed 12 f before `s`, struck at
+/// `s` (the fill in over 6 f, its edges out and back over 12 f), solid
+/// 12 f, then cooled to nothing by `end` (the step's end): no corner, the
+/// next step has nothing of it to keep.
+fn landing(now: cursors.Now, s: f32) ui.Heat {
+ const st = time.strike;
+ const tm = now.time;
+ if (tm < s - st.arm) return .none;
+ if (tm < s) return .{ .arm = clamp01((tm - (s - st.arm)) / time.stagger) };
+ const cool_from = s + st.pulse;
+ const end = @max(now.plan.total, cool_from + 6.0 / 60.0);
+ return .{ .level = 1, .solid = 1 - cursors.glide(clamp01((tm - cool_from) / (end - cool_from))), .in = clamp01((tm - s) / st.in), .out = if (tm - s < st.pulse) theme.pulse((tm - s) / st.pulse) else 0, .corner = 0 };
+}
+
+/// What a count shows: the old number until a strike's fill is half in,
+/// then the new; a strike's paper under it, on its `ground` (a box's,
+/// or the page). Crossfading (`p`) where it changes unstruck. `prefix`
+/// before the digits; ranged right of `x` when `right`.
+fn number(u: ui.Ui, face: sk.Face, size: f32, x: f32, base_y: f32, right: bool, was: u32, is: u32, ink: u24, heat: ?ui.Heat, ground: ?u24, p: f32, prefix: []const u8) void {
+ const one = struct {
+ fn draw(v: ui.Ui, fc: sk.Face, sz: f32, xx: f32, by: f32, r: bool, n: u32, c: anytype, pre: []const u8) void {
+ if (n == 0) return;
+ const text = v.print("{s}{d}", .{ pre, n });
+ v.text(fc, sz, if (r) xx - v.width(fc, sz, text) else xx, by, text, c);
+ }
+ }.draw;
+ if (was == is) return one(u, face, size, x, base_y, right, is, ink, prefix);
+ if (heat) |h| {
+ const text = u.print("{s}{d}", .{ prefix, is });
+ const w = u.width(face, size, text);
+ const left = if (right) x - w else x;
+ // Nothing under it but while it is armed or its paper shows: its ground is the box's own, or the page.
+ // Inside its box's frame: the frame never goes under the paper and back.
+ if (h.level > 0 and h.solid > 0 or h.arm > 0) _ = u.cellWritten(.{ .x = left - 3, .y = base_y - size * 0.7, .w = w + 6, .h = size * 0.8 }, h, ground);
+ if (h.level < 1 or h.in < 0.5) return one(u, face, size, x, base_y, right, was, ink, prefix);
+ // Bold and bright on the paper, cooling to its own ink and face with it.
+ const hot = h.solid * h.in;
+ const bold = hot >= 0.5;
+ return one(u, if (bold) (if (face == .sans) .sans_bold else .mono_bold) else face, size, x, base_y, right, is, ui.mix(ink, t.bright, hot), prefix);
+ }
+ one(u.faded(1 - p), face, size, x, base_y, right, was, ink, prefix);
+ one(u.faded(p), face, size, x, base_y, right, is, ink, prefix);
+}
+
+/// The edges of `v`, in `u` (the graph's origin): each in its look, mixed
+/// from the one before as the step lands; the one a leave takes drawn
+/// gold, head first, over its old look, and cooling to the trail's newest
+/// after the landing; each loop's turns under its turn into its header.
+fn drawEdges(u: ui.Ui, v: Instant, form: Form) void {
+ const g = v.g;
+ const lens = form == .lens;
+ const gm = theme.metric.graph;
+ const head: [2]f32 = if (lens) gm.lens.head else gm.head;
+ const radius: f32 = if (lens) gm.lens.corner else gm.corner;
+ // Recoloured with the landing (a leave's 18 f), else with the advance.
+ const q = if (v.leave) |l| clamp01(l.landed / time.leave.trail) else v.p;
+ for (g.edges, 0..) |e, k| {
+ const a = edgeLook(v.was, @intCast(k));
+ const b = edgeLook(g, @intCast(k));
+ const ink = ui.mix(a.ink, b.ink, q);
+ const w = std.math.lerp(a.w, b.w, q);
+ var pts: [6]ui.Vec = undefined;
+ for (e.path(), 0..) |pt, n| pts[n] = .{ pt[0], pt[1] };
+ u.route(pts[0..e.n], ink, .{ .width = if (ui.strokes) 20 else w, .head = if (ui.strokes) null else head, .radius = radius });
+ if (v.leave) |l| if (l.edge == k) {
+ const gold = theme.mark(.current).solid;
+ u.faded(1 - q).route(pts[0..e.n], gold, .{ .width = if (ui.strokes) 20 else 3, .head = if (ui.strokes) null else head, .radius = radius, .progress = l.draw });
+ };
+ // A loop's turns so far, on its lane under the turn into its header; struck as a turn lands.
+ if (e.back and (e.count > 0 or v.was.edges[k].count > 0) and !ui.strokes) {
+ const lx = pts[2][0];
+ const hy = pts[3][1];
+ const strike: ?ui.Heat = if (v.leave) |l| (if (l.edge == k) landing(v.now, v.now.plan.advance + v.now.plan.travel) else null) else null;
+ number(u, .sans, theme.size.sans.micro, lx + 5, hy + 22, false, v.was.edges[k].count, e.count, t.faint, strike, null, v.p, "\u{00d7}");
+ }
+ // On the map a conditional's counts by its ports.
+ if (!lens and !e.back and e.kind != .jump and g.exact and !ui.strokes) {
+ const outs = for (g.edges) |o| {
+ if (o.from == e.from and !o.back and o.to != e.to) break true;
+ } else false;
+ if (outs) number(u, .mono, theme.size.mono.context, pts[0][0] + 8, pts[0][1] + 20, false, v.was.edges[k].count, e.count, t.faint, null, null, v.p, "");
+ }
+ }
+}
+
+/// The mark on its way along the edge a leave takes: a gold plaque (half
+/// size in the lens) with an ink head pointing the way it goes.
+fn drawMark(u: ui.Ui, v: Instant, form: Form) void {
+ const l = v.leave orelse return;
+ if (l.travel <= 0 or l.travel >= 1) return;
+ const e = &v.g.edges[l.edge];
+ const at, const dir = e.at(l.travel * e.length());
+ const side: f32 = if (form == .lens) 12 else theme.metric.plaque.pc;
+ const gold = theme.mark(.current);
+ u.fill(.{ .x = at[0] - side / 2, .y = at[1] - side / 2, .w = side, .h = side }, gold.solid);
+ if (ui.strokes) return;
+ const h = side / 4;
+ const tip: ui.Vec = .{ at[0] + dir[0] * h, at[1] + dir[1] * h };
+ const back: ui.Vec = .{ at[0] - dir[0] * h, at[1] - dir[1] * h };
+ const across: ui.Vec = .{ -dir[1] * h, dir[0] * h };
+ sk.draw.polygon(u.f, &.{ tip, back + across, back - across }, u.at.pen(.{ .fill = ui.rgb(gold.on_solid) }));
+}
+
+/// How much node `k` is the pc's: as the mark leaves it and lands, or with the advance.
+fn golden(v: Instant, k: u32) f32 {
+ const was: f32 = if (v.was.here == k) 1 else 0;
+ const is: f32 = if (v.g.here == k) 1 else 0;
+ if (v.leave) |l| {
+ if (was > is) return 1 - l.travel;
+ if (is > was) return clamp01(l.landed / time.leave.count);
+ return is;
+ }
+ return std.math.lerp(was, is, v.p);
+}
+
+/// The `blocks` lens (design/README.md, `graph`): over the program column
+/// the function's graph without its text, a block a box 24 high, as wide
+/// as its rows (60 and 10 a row, 132 at least), its offset and its visits,
+/// the pc's framed gold 3; the edges, the lanes and the trail at half
+/// measure. Its view is the disassembly itself, over the state column
+/// (the split `blocks`).
+pub const Blocks = struct {
+ cursor: cursors.Cursor,
+ stage: *const Stage,
+ focus: bool = false,
+
+ pub fn draw(b: *const Blocks, f: *sk.Frame, placed: anim.Placed) void {
+ const box = b.stage.box(placed, .band);
+ const m = theme.metric.context;
+ if (box.h < m.tag + 24) return;
+ const u = context.at(f, placed, box).faded(placed.value(b.stage.drawing));
+ u.clip(.{ .x = 0, .y = 0, .w = box.w, .h = box.h });
+ defer u.unclip();
+ const now = b.cursor.now(placed);
+ const room = box.h - m.tag - theme.stroke.rule;
+ const v = instant(f.scratch, now, .lens, room) orelse {
+ _ = u.panel(box.w, box.h, "its blocks", .{ .focus = b.focus });
+ return;
+ };
+ const name = ui.symbol(u, b.cursor.rec.strings.get(v.g.start) orelse "");
+ _ = u.panel(box.w, box.h, u.print("the blocks of {s}", .{name[0 .. std.mem.lastIndexOfScalar(u8, name, '+') orelse name.len]}), .{ .focus = b.focus, .note = "its blocks \u{00b7} the visits \u{00b7} the path" });
+ u.clip(.{ .x = theme.stroke.rule, .y = m.tag, .w = box.w - 2 * theme.stroke.rule, .h = room });
+ const o = u.moved(0, m.tag - v.pan);
+ drawEdges(o, v, .lens);
+ const gm = theme.metric.graph.lens;
+ const size = theme.size.mono.context;
+ for (v.g.nodes, v.was.nodes, 0..) |n, was, k| {
+ const r: ui.Rect = .{ .x = n.x, .y = n.y, .w = n.w, .h = n.h };
+ const gold = golden(v, @intCast(k));
+ const seen = std.math.lerp(@as(f32, if (was.visits > 0) 1 else 0), @as(f32, if (n.visits > 0) 1 else 0), if (v.leave != null) clamp01(v.leave.?.landed / time.leave.count) else v.p);
+ o.fill(r, ui.mix(theme.color.page, theme.color.raised, seen));
+ if (n.folded > 0) o.dashedFrame(r, theme.color.rule, theme.stroke.rule) else o.frame(r, ui.mix(theme.color.rule, theme.mark(.current).solid, gold), std.math.lerp(theme.stroke.rule, gm.gold, gold));
+ const base_y = rows.baseline(n.y);
+ const off = o.print("+{x}", .{n.start - v.g.start});
+ o.text(.mono, size, n.x + 8, base_y, off, ui.mix(t.faint, t.primary, seen));
+ const strike: ?ui.Heat = if (v.leave) |l| (if (v.g.edges[l.edge].to == k) landing(now, now.plan.advance + now.plan.travel + time.leave.count) else null) else null;
+ number(o, .mono, size, n.x + n.w - 8, base_y, true, was.visits, n.visits, t.dim, strike, if (seen >= 0.5) theme.color.raised else theme.color.page, v.p, "\u{00d7}");
+ }
+ drawMark(o, v, .lens);
+ u.unclip();
+ }
+};
+
+/// The disassembly as its graph, on the map (design/README.md, `graph`;
+/// mock 22): two columns wide beside the source. A block is a head (its
+/// first address, its lines, how often the run entered it) over its rows,
+/// `insn`'s with the offset where the address was; the annotation only in
+/// the pc's block, which widens to its column; a call a hook out of the
+/// block's side and back a row down; under a return, the way out. Too tall,
+/// the runs never reached fold, then long blocks, then it pans.
+pub const Map = struct {
+ cursor: cursors.Cursor,
+ stage: *const Stage,
+
+ pub fn draw(gm: *const Map, f: *sk.Frame, placed: anim.Placed) void {
+ const box = gm.stage.box(placed, .disasm);
+ const m = theme.metric.context;
+ if (box.h < m.tag + m.row) return;
+ const u = context.at(f, placed, box);
+ const now = gm.cursor.now(placed);
+ const rec = gm.cursor.rec;
+ const room = box.h - m.tag - theme.stroke.rule;
+ const v = instant(f.scratch, now, .map, room) orelse {
+ _ = u.panel(box.w, box.h, "disassembly", .{});
+ return;
+ };
+ const g = v.g;
+ const full = rec.strings.get(g.start) orelse "";
+ const sym = ui.symbol(u, full);
+ const name = sym[0 .. std.mem.lastIndexOfScalar(u8, sym, '+') orelse sym.len];
+ const module: []const u8 = if (std.mem.indexOfScalar(u8, full, '!')) |bang| full[0..bang] else "";
+ const folded = g.foldedBlocks();
+ const title = if (module.len > 0) u.print("disassembly \u{00b7} {s} \u{00b7} {s}", .{ name, module }) else u.print("disassembly \u{00b7} {s}", .{name});
+ const note = if (folded > 0) u.print("{s}{d} blocks \u{00b7} folded: {d} never reached", .{ if (rec.sourced(now.stops[0])) "" else "no source \u{00b7} ", g.blocks, folded }) else if (g.exact) "its blocks \u{00b7} visits so far \u{00b7} the edges the run took" else "its blocks \u{00b7} visits so far";
+ _ = u.panel(box.w, box.h, title, .{ .note = note });
+ u.clip(.{ .x = theme.stroke.rule, .y = m.tag, .w = box.w - 2 * theme.stroke.rule, .h = room });
+ defer u.unclip();
+ const o = u.moved(0, m.tag - v.pan);
+ drawEdges(o, v, .map);
+ const d: disasm.Disasm = .{ .cursor = gm.cursor, .stage = gm.stage };
+ const body: ui.Rect = .{ .x = theme.stroke.rule, .y = v.pan, .w = box.w - 2 * theme.stroke.rule, .h = room };
+ for (g.nodes, 0..) |_, k| block(o, v, @intCast(k), d, body);
+ drawMark(o, v, .map);
+ }
+
+ /// Block `k`: its head, its rows, its hooks and its way out.
+ fn block(o: ui.Ui, v: Instant, k: u32, d: disasm.Disasm, body: ui.Rect) void {
+ const gm = theme.metric.graph;
+ const m = theme.metric.context;
+ const size = theme.size.mono.context;
+ const adv = size * 3 / 5;
+ const now = v.now;
+ const rec = now.rec;
+ const g = v.g;
+ const n = g.nodes[k];
+ const was = v.was.nodes[k];
+ const here = g.here == k or v.was.here == k;
+ // The pc's block widens to its column for the annotation, never into the channel.
+ const w = if (here and n.folded == 0) @max(n.w, @min(g.pitch - gm.block_gap, g.channel - gm.channel / 2 - n.x)) else n.w;
+ const r: ui.Rect = .{ .x = n.x, .y = n.y, .w = w, .h = n.h };
+ const landing_q = if (v.leave) |l| clamp01(l.landed / time.leave.count) else v.p;
+ const seen = std.math.lerp(@as(f32, if (was.visits > 0) 1 else 0), @as(f32, if (n.visits > 0) 1 else 0), landing_q);
+ const gold = golden(v, k);
+ o.fill(r, theme.color.page);
+ if (n.folded > 0) {
+ // Blocks the whole recording never reached: one dashed box, its offsets and its count.
+ o.dashedFrame(r, theme.color.rule, theme.stroke.rule);
+ const last = n.start + n.len - 1;
+ o.text(.mono, size, n.x + m.side, rows.baseline(n.y), o.print("+{x} to +{x}", .{ n.start - g.start, last - g.start }), t.faint);
+ const words = if (n.folded > 1) o.print("{d} blocks never reached", .{n.folded}) else "never reached";
+ const micro = theme.size.sans.micro;
+ o.text(.sans, micro, n.x + w - m.side - o.width(.sans, micro, words), n.y + m.tag - 6, words, t.faint);
+ return;
+ }
+ o.fill(.{ .x = r.x, .y = r.y, .w = r.w, .h = m.tag }, ui.mix(theme.color.page, theme.color.raised, seen));
+ o.frame(r, ui.mix(theme.color.rule, theme.mark(.current).solid, gold), theme.stroke.rule);
+ // The head: its first address, its lines, its visits.
+ const head_y = rows.baseline(n.y);
+ const end = o.address(n.x + m.side, head_y, n.start, .{ .ink = ui.rgb(theme.color.region.code_) });
+ var buf: [256]u8 = undefined;
+ var first_line: ?u32 = null;
+ var last_line: ?u32 = null;
+ var at = n.start;
+ const i = now.stops[0];
+ // Its rows, as `insn` takes them (a long block: four, `more`, four).
+ var list: std.ArrayList(disasm.Insn) = .empty;
+ while (at < n.start + n.len) {
+ const one = rec.instruction(i, at, &buf) orelse break;
+ list.append(o.f.scratch, .{ .addr = at, .len = one.len, .text = o.print("{s}", .{one.text}), .line = one.line, .params = one.params, .bare = true }) catch break;
+ if (one.line) |l| {
+ first_line = @min(first_line orelse l, l);
+ last_line = @max(last_line orelse l, l);
+ }
+ at += one.len;
+ }
+ const micro = theme.size.sans.micro;
+ if (first_line) |a| o.text(.sans, micro, end + 16, n.y + m.tag - 6, if (a == last_line.?) o.print("line {d}", .{a}) else o.print("lines {d} to {d}", .{ a, last_line.? }), t.faint);
+ const strike: ?ui.Heat = if (v.leave) |l| (if (v.g.edges[l.edge].to == k) landing(now, now.plan.advance + now.plan.travel + time.leave.count) else null) else null;
+ number(o, .mono, size, n.x + w - m.side, head_y, true, was.visits, n.visits, t.primary, strike, if (seen >= 0.5) theme.color.raised else theme.color.page, v.p, "\u{00d7}");
+
+ // Where the mark is, and was: the plaque leaves its row as the mark sets off, and lands with it.
+ const pcs = [2]u64{ rec.register(now.stops[1], "rip"), rec.register(now.stops[0], "rip") };
+ var shows = [2]f32{ 1 - v.p, v.p };
+ if (v.leave) |l| shows = .{ 1 - clamp01((now.time - now.plan.advance) / time.leave.count), clamp01(l.landed / time.leave.count) };
+ if (pcs[0] == pcs[1]) shows = .{ 0, 1 };
+ // What the annotation reads as current (the moment the mark stands for), and the rows that ran in the last three steps.
+ const going = now.advancing();
+ const base: usize = if (going >= 0.5) 0 else 1;
+ const current_line = rec.own[now.marked()];
+ const annotated = g.here == k and now.plan.gait != .sprint;
+ const sprinting = now.plan.gait == .sprint and !now.resting();
+ const echo = disasm.jumpEcho(now, base);
+ var covered: usize = 0;
+ var line_before: ?u32 = null;
+ const long = n.shown < n.rows;
+ // Its rows' annotations stay in it: a call's arguments hang no further than its last row.
+ const top = @max(n.y, body.y);
+ const under = @min(n.y + n.h, body.y + body.h);
+ if (under > top) o.clip(.{ .x = body.x, .y = top, .w = body.w, .h = under - top });
+ var y = n.y + m.tag;
+ for (list.items, 0..) |row, j| {
+ if (long and j >= gm.keep and j < list.items.len - gm.keep) {
+ if (j == gm.keep) {
+ _ = o.arrow(n.x + gm.offset - 36, y + m.row / 2, .more);
+ o.text(.mono, size, n.x + gm.mnemonic, rows.baseline(y), o.print("{d} rows", .{list.items.len - 2 * gm.keep}), t.faint);
+ y += m.row;
+ }
+ continue;
+ }
+ const rr: ui.Rect = .{ .x = n.x, .y = y, .w = w, .h = m.row };
+ @import("map.zig").row(.disasm, row.addr, o, rr);
+ for (pcs, shows) |pc, a| if (pc == row.addr and a > 0) {
+ const lit = o.faded(a);
+ lit.current(.{ .x = n.x + theme.stroke.rule, .y = y, .w = w - 2 * theme.stroke.rule, .h = m.row }, theme.metric.plaque.pc, now.fires(.disasm));
+ sk.draw.polygon(o.f, &.{ .{ n.x + 20, y + m.row / 2 }, .{ n.x + 10, y + 6 }, .{ n.x + 10, y + m.row - 6 } }, lit.at.pen(.{ .fill = ui.rgb(theme.mark(.current).on_solid) }));
+ };
+ const ran = if (annotated) ranAt(now, base, row.addr) else null;
+ if (ran) |rn| if (row.addr != pcs[1]) o.trail(n.x + theme.metric.insn.mark, y, rn.k);
+ // The offset where the address was.
+ const off = o.print("+{x}", .{row.addr - g.start});
+ o.text(.mono, size, n.x + gm.offset - o.width(.mono, size, off), rows.baseline(y), off, t.faint);
+ const lit = o.moved(n.x - gm.shift, 0);
+ if (annotated and !sprinting) {
+ const state: disasm.Disasm.State = if (row.addr == rec.register(now.marks[if (going >= 0.5) 1 else 0], "rip")) .current else if (ran) |rn| .{ .ran = rn } else .ahead;
+ const hangs = d.insn(lit, now, row, y, w + gm.shift, 0, row.line, row.line != line_before, current_line, 0, state, base, covered > 0, .{ g.start, g.start + g.len }, echo);
+ covered = @max(covered -| 1, hangs);
+ } else {
+ if (row.line) |l| if (row.line != line_before) {
+ const num = o.print("{d}", .{l});
+ o.text(.mono, size, n.x + gm.line - o.width(.mono, size, num), rows.baseline(y), num, t.faint);
+ };
+ disasm.bareRow(lit, row, y);
+ }
+ line_before = row.line;
+ // A call that comes back: out of the block's side and in again a row down, the callee named.
+ if (std.mem.eql(u8, row.mnemonic(), "call") and !ui.strokes) if (disasm.target(row)) |to| {
+ const ink = if (n.visits > 0) t.dim else theme.color.rule;
+ const back = !(j + 1 == list.items.len and n.end == .noreturn);
+ const hx = n.x + w;
+ if (back) o.route(&.{ .{ hx, y + m.row / 2 }, .{ hx + gm.hook + 6, y + m.row / 2 }, .{ hx + gm.hook + 6, y + 1.5 * m.row }, .{ hx + 1, y + 1.5 * m.row } }, ink, .{ .width = theme.stroke.rule, .head = .{ 7, 8 }, .radius = 6 }) else o.route(&.{ .{ hx, y + m.row / 2 }, .{ hx + gm.hook + 6, y + m.row / 2 } }, ink, .{ .width = theme.stroke.rule, .head = null });
+ const callee = ui.symbol(o, rec.strings.get(to) orelse "");
+ o.text(.mono, size, hx + gm.hook + 6 + adv, rows.baseline(y) + m.row / 2, callee[0 .. std.mem.lastIndexOfScalar(u8, callee, '+') orelse callee.len], t.primary);
+ };
+ y += m.row;
+ }
+ o.clip(body);
+ // How it ends, under it: the way out (a return, a call that does not return), a tail call, an indirect jump.
+ const ink = if (n.visits > 0) t.dim else theme.color.rule;
+ const cx = n.x + n.w / 2;
+ const bottom = n.y + n.h;
+ switch (n.end) {
+ .ret, .noreturn => {
+ o.fill(.{ .x = cx - 1, .y = bottom, .w = theme.stroke.rule, .h = gm.exit_stub }, ink);
+ o.fill(.{ .x = cx - gm.exit_bar / 2, .y = bottom + gm.exit_stub, .w = gm.exit_bar, .h = 3 }, ink);
+ },
+ .tail => {
+ o.fill(.{ .x = cx - 1, .y = bottom, .w = theme.stroke.rule, .h = 24 }, ink);
+ if (n.out) |to| {
+ const callee = ui.symbol(o, rec.strings.get(to) orelse "");
+ o.text(.mono, size, cx + 8, rows.baseline(bottom + 6), callee[0 .. std.mem.lastIndexOfScalar(u8, callee, '+') orelse callee.len], t.primary);
+ }
+ },
+ .indirect => {
+ o.fill(.{ .x = cx - 1, .y = bottom, .w = theme.stroke.rule, .h = 24 }, ink);
+ _ = o.arrow(cx - 8, bottom + 30, .more);
+ o.text(.sans, micro, cx + 60, bottom + 36, "targets not known", t.faint);
+ },
+ else => {},
+ }
+ }
+};
+
+/// The step (`k` steps ago, 0 newest) a row last ran in, of the three the
+/// mark's trail is (by the stops `base` on), and the moment it ran at.
+fn ranAt(now: cursors.Now, base: usize, addr: u64) ?disasm.Disasm.Ran {
+ for (0..3) |k| {
+ const first = now.stops[@min(base + 1 + k, now.stops.len - 1)];
+ const last = now.stops[base + k];
+ var at = last;
+ while (at > first and last - at < 4096) {
+ at -= 1;
+ if (now.rec.register(at, "rip") == addr) return .{ .k = k, .at = at };
+ }
+ }
+ return null;
+}
+
+test "a loop's back edge climbs, the hot path is straight down, a never-taken target sits right of its block" {
+ // sort's shape: entry, the outer loop's test, its body, the inner test,
+ // the compare, the swap, the outer step, the exit.
+ var nodes = [_]Node{
+ .{ .start = 0x00, .len = 0x17, .end = .jump }, // B0 jmp B6
+ .{ .start = 0x17, .len = 0x08, .end = .jump }, // B1 jmp B3
+ .{ .start = 0x1f, .len = 0x40, .end = .fall }, // B2 (swap) falls B3
+ .{ .start = 0x5f, .len = 0x06, .end = .branch }, // B3 jle B5, falls B4
+ .{ .start = 0x65, .len = 0x35, .end = .branch }, // B4 jg B2, falls B5
+ .{ .start = 0x9a, .len = 0x04, .end = .fall }, // B5 falls B6
+ .{ .start = 0x9e, .len = 0x0c, .end = .branch }, // B6 jl B1, falls B7
+ .{ .start = 0xaa, .len = 0x04, .end = .ret }, // B7
+ };
+ for (&nodes) |*nd| {
+ nd.w = 300;
+ nd.h = 52;
+ }
+ var edges = [_]Edge{
+ .{ .from = 0, .to = 6, .kind = .jump, .total = 1 },
+ .{ .from = 1, .to = 3, .kind = .jump, .total = 7 },
+ .{ .from = 2, .to = 3, .kind = .fall, .total = 10 },
+ .{ .from = 3, .to = 5, .kind = .taken, .total = 0 },
+ .{ .from = 3, .to = 4, .kind = .fall, .total = 17 },
+ .{ .from = 4, .to = 2, .kind = .taken, .total = 10 },
+ .{ .from = 4, .to = 5, .kind = .fall, .total = 7 },
+ .{ .from = 5, .to = 6, .kind = .fall, .total = 7 },
+ .{ .from = 6, .to = 1, .kind = .taken, .total = 7 },
+ .{ .from = 6, .to = 7, .kind = .fall, .total = 1 },
+ };
+ var g: Graph = .{ .start = 0, .len = 0xae, .nodes = &nodes, .edges = &edges, .here = null, .text = true, .exact = true };
+ place(&g, metricOf(.map));
+ // Two loops: the inner turns from the swap, the outer from its step.
+ try std.testing.expect(edges[2].back and edges[7].back);
+ for (edges, 0..) |e, k| if (k != 2 and k != 7) try std.testing.expect(!e.back);
+ // Layers by the longest path; the exit last, alone.
+ const want = [_]u32{ 0, 2, 5, 3, 4, 5, 1, 6 };
+ for (nodes, want) |nd, l| try std.testing.expectEqual(l, nd.layer);
+ // The hot path straight down; the step beside the swap.
+ for ([_]usize{ 0, 1, 2, 3, 4, 6, 7 }) |k| try std.testing.expectEqual(@as(u32, 0), nodes[k].col);
+ try std.testing.expectEqual(@as(u32, 1), nodes[5].col);
+ // The outer loop's lane outermost; a back edge climbs into its header's head from the left.
+ try std.testing.expect(edges[7].lane == 0 and edges[2].lane == 1);
+ const turn = edges[7].path();
+ try std.testing.expect(turn[3][1] < turn[2][1] and turn[4][0] < nodes[6].x);
+ // The exit's edge would cross the loop's blocks: it runs in the right channel.
+ try std.testing.expectEqual(@as(u8, 6), edges[9].n);
+ try std.testing.expectEqual(g.channel, edges[9].points[2][0]);
+ // Every forward edge ends on its target's top.
+ for (edges) |e| if (!e.back) try std.testing.expectEqual(nodes[e.to].y, e.points[e.n - 1][1]);
+}