diff options
| author | Gabriel Schneider <[email protected]> | 2026-11-11 17:42:07 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-11-11 19:11:00 -0300 |
| commit | b54c6776953d3243ab5b8e676e747713827ab320 (patch) | |
| tree | d53be6cef4587b94531880af6479a1b5fa1aac39 /anim/src/graph.zig | |
| parent | 3093eb55ac4a7054f51f06ea2786b5f9c9ec73f6 (diff) | |
| download | computeranim-b54c6776953d3243ab5b8e676e747713827ab320.tar.gz computeranim-b54c6776953d3243ab5b8e676e747713827ab320.zip | |
canim: the disassembly under the source everywhere; rings
From the user. In every split the disassembly stays under the source;
registers a scene never changes fold three to a row, and the stack takes
the room: nine to twenty slots where it had six. The graph's first form
is rings: a loop a ring its blocks sit on, an inner loop a smaller ring
touching its parent, a way out leaving along the tangent; layers stay
for functions without loops. Its layout comes from the code alone and it
shows nothing from after the moment: a block not reached yet is quiet
and is reached, a fold of what is not reached yet opens when the run
arrives. A pane unrolls from its strip into its whole column and rolls
back. The sqlite scene's strips move before their panes.
Co-Authored-By: Claude Fable 5.2 <[email protected]>
Claude-Session: https://claude.ai/code/session_016Y9MNCKgYCGiANnEwcEQxa
Diffstat (limited to 'anim/src/graph.zig')
| -rw-r--r-- | anim/src/graph.zig | 2290 |
1 files changed, 1478 insertions, 812 deletions
diff --git a/anim/src/graph.zig b/anim/src/graph.zig index fa91adb..7066580 100644 --- a/anim/src/graph.zig +++ b/anim/src/graph.zig @@ -1,24 +1,22 @@ //! `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. +//! function as its basic blocks with what the run has done on them by the +//! moment shown, and nothing after: how often each was entered, how often +//! each edge was taken, the last three taken (the trail), the block the pc +//! is in; what the run has not reached yet is quiet until it does. //! //! `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. +//! and counts the run over them by a moment. `place` lays them out from the +//! code alone (its blocks, their edges, their pills' words), never from the +//! run: in `rings` each loop a ring its blocks sit on, a nested loop a +//! smaller ring outside its parent touching it at its header, what is +//! outside every loop as `layers` lays it; in `layers` the blocks in layers +//! by the longest path, the back edges up lanes on the left. `layout` +//! folds a function too big for its pane: the blocks not reached by the +//! scene's first moment, the code beyond each way the run had not taken, +//! one dashed pill each; a fold opens when the run reaches a block of it, +//! and never closes. `Blocks` draws it (the `blocks` lens, and the map's +//! drawing), `Rules` its blocks on the linear rows; `leave` (and `turn`) is +//! the step across one edge, and a first time is a `reach`, or an `unfold`. const std = @import("std"); const sk = @import("sketch"); const anim = @import("anim"); @@ -32,28 +30,29 @@ const disasm = @import("disasm.zig"); const Stage = @import("stage.zig").Stage; const theme = ui.theme; const time = theme.time; +const gm = theme.metric.graph; const t = theme.color.text; +const pi: f32 = std.math.pi; pub const End = zt.Debugger.End; -/// A block, or a fold of blocks never reached, and where it is drawn. +/// A block, or a fold of blocks not reached yet, and where its pill is. 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). + /// The functions it calls that come back, the program's (not the tracer's): the first two, and whether there are more. + calls: [2]u64 = .{ 0, 0 }, + more_calls: bool = false, + /// How many blocks not reached yet 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. + /// Times the run entered it, by the moment the graph is of. visits: u32 = 0, - reached: bool = false, layer: u32 = 0, col: u32 = 0, + /// Its pill: its top left and its size. x: f32 = 0, y: f32 = 0, w: f32 = 0, @@ -62,22 +61,45 @@ pub const Node = struct { pub fn contains(n: Node, addr: u64) bool { return addr -% n.start < n.len; } + + fn cx(n: Node) f32 { + return n.x + n.w / 2; + } + + fn cy(n: Node) f32 { + return n.y + n.h / 2; + } + + fn box(n: Node) Box { + return .{ n.x, n.y, n.x + n.w, n.y + n.h }; + } + + /// Whether `p` is inside its pill, its ends half circles. + fn has(n: Node, p: [2]f32) bool { + const r = n.h / 2; + const y = n.y + r; + if (p[0] >= n.x + r and p[0] <= n.x + n.w - r) return @abs(p[1] - y) <= r; + const x = if (p[0] < n.x + r) n.x + r else n.x + n.w - r; + return (p[0] - x) * (p[0] - x) + (p[1] - y) * (p[1] - y) <= r * r; + } }; pub const Kind = enum { fall, taken, jump }; +/// The points an edge's way is sampled at, at most: arcs and quarter circles as short chords. +const most = 96; + 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). + /// Times taken, by the moment the graph is of. 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). + /// To a block on the walk's way: a loop's turn (in `layers`, up 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, + /// Its way, from its source's frame to its target's: straight runs, arcs and quarter circles, sampled. + points: [most][2]f32 = undefined, n: u8 = 0, pub fn path(e: *const Edge) []const [2]f32 { @@ -87,33 +109,49 @@ pub const Edge = struct { /// 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]); + for (e.path()[0 .. e.n -| 1], e.path()[@min(1, e.n)..]) |a, b| total += dist(a, b); return total; } - /// The point `d` units along its way, and which way it goes there. + /// The point `d` units along its way, and which way it goes there (a unit vector). 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; + if (pts.len < 2) return .{ if (pts.len > 0) pts[0] else .{ 0, 0 }, .{ 0, 1 } }; + var left = @max(d, 0); + var dir: [2]f32 = .{ 0, 1 }; + for (pts[0 .. pts.len - 1], pts[1..], 0..) |a, b, k| { + const l = dist(a, b); + if (l == 0) continue; + dir = .{ (b[0] - a[0]) / l, (b[1] - a[1]) / l }; + if (left <= l or k + 2 == pts.len) { + const f = @min(left / l, 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 } }; + return .{ pts[pts.len - 1], dir }; + } + + fn set(e: *Edge, p: *const Path) void { + e.n = @intCast(p.n); + @memcpy(e.points[0..p.n], p.pts[0..p.n]); } }; +/// A block of the function and the node it is drawn in (itself, or its fold). +pub const Span = struct { start: u64, len: u64, node: u32 }; + +/// A loop's ring, where it is drawn: its centre, its radius, its header. +pub const Ring = struct { c: [2]f32, r: f32, header: u32 }; + /// A function's graph at a moment. pub const Graph = struct { start: u64, len: u64, nodes: []Node, edges: []Edge, + /// Every block, in address order, and the node it is in. + spans: []Span, /// The node the pc is in. here: ?u32, /// The last three edges taken, newest first. @@ -122,20 +160,22 @@ pub const Graph = struct { 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). + /// Its size, from its top left. w: f32 = 0, h: f32 = 0, - /// The right channel's x, and how many lanes the back edges take. + /// `layers`: 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, + /// `rings`: each loop's ring. + rings: []Ring = &.{}, + /// Which of the folds of its layout are open (`layout`). + open: u64 = 0, pub fn nodeOf(g: Graph, addr: u64) ?u32 { - for (g.nodes, 0..) |n, i| if (n.contains(addr)) return @intCast(i); - return null; + const k = spanAt(g.spans, addr) orelse return null; + return g.spans[k].node; } pub fn edgeOf(g: Graph, from: u32, to: u32) ?u32 { @@ -151,48 +191,17 @@ pub const Graph = struct { } }; -/// 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 }, - }; -} +/// The graph's two forms (a scene names the one it wants): `rings`, each +/// loop a ring (a function with no loop drawn as `layers`); `layers`. +pub const Form = enum { rings, layers }; // ---------------------------------------------------------------- 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. +/// the functions each calls, and what the run did on them by then (visits, +/// edge counts, the trail). 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; } @@ -204,8 +213,8 @@ fn readBlocks(arena: std.mem.Allocator, rec: *const Recording, i: u64, pc: u64) 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. + // Every instruction, 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| { @@ -216,19 +225,27 @@ fn readBlocks(arena: std.mem.Allocator, rec: *const Recording, i: u64, pc: u64) 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) { + var calls: usize = 0; + while (found.text and at < n.start + n.len) { const one = rec.instruction(i, at, &buf) orelse break; padding = padding and std.mem.startsWith(u8, one.text, "nop"); + // A call that comes back, of the program's: named in its pill (a call is not an edge). + const row: disasm.Insn = .{ .addr = at, .len = one.len, .text = one.text }; + const last = at + one.len >= n.start + n.len; + if (std.mem.eql(u8, row.mnemonic(), "call") and !(last and n.end == .noreturn)) if (disasm.target(row)) |to| if (callee(rec, to) != null) { + if (calls < 2) n.calls[calls] = to else n.more_calls = true; + calls += 1; + }; 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 }; + const spans = try arena.alloc(Span, keep); + for (nodes, spans, 0..) |n, *s, k| s.* = .{ .start = n.start, .len = n.len, .node = @intCast(k) }; + var g: Graph = .{ .start = found.start, .len = found.len, .nodes = nodes, .edges = &.{}, .spans = spans, .here = null, .text = found.text, .exact = false, .blocks = keep }; var edges: std.ArrayList(Edge) = .empty; for (blocks) |b| { const from = blockAt(nodes, b.start) orelse continue; @@ -239,9 +256,21 @@ fn readBlocks(arena: std.mem.Allocator, rec: *const Recording, i: u64, pc: u64) g.edges = edges.items; g.exact = stepsEach(rec, g); count(rec, &g, i); + g.here = g.nodeOf(pc); return g; } +/// A callee's name as its caller's pill says it (`swap`); null for one with +/// none, and for the tracer's own (`__zt_var`): the instrumentation's +/// calls are not the program's. +fn callee(rec: *const Recording, addr: u64) ?[]const u8 { + const full = rec.strings.get(addr) orelse return null; + var name = if (std.mem.indexOfScalar(u8, full, '!')) |bang| full[bang + 1 ..] else full; + name = name[0 .. std.mem.lastIndexOfScalar(u8, name, '+') orelse name.len]; + if (name.len == 0 or std.mem.startsWith(u8, name, "__zt_")) return null; + return name; +} + /// 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 @@ -267,52 +296,49 @@ fn stepsEach(rec: *const Recording, g: Graph) bool { } /// 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. +/// each by then: 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 }; + const spans = arena.alloc(Span, blocks.len) catch return null; + for (blocks, nodes, spans, 0..) |b, *n, *s, k| { + n.* = .{ .start = b.start, .len = b.len, .end = b.end }; + s.* = .{ .start = b.start, .len = b.len, .node = @intCast(k) }; + } + var g: Graph = .{ .start = found.start, .len = found.len, .nodes = nodes, .edges = &.{}, .spans = spans, .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). +/// The run over the graph by moment `i`: each node's visits and each +/// edge's count, the last three edges taken. 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 { + for (g.nodes) |*n| n.visits = 0; + for (g.edges) |*e| e.count = 0; 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; + for (rec.registers[0..@min(i + 1, rec.registers.len)]) |regs| { 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; + const s = spanAt(g.spans, pc) orelse continue; + const b = g.spans[s].node; // 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; + const entered = prev == null or if (g.exact) pc == g.spans[s].start and prev_pc != pc else prev.? != b; if (entered) { - if (k <= i) n.visits += 1; + g.nodes[b].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] }; - } + g.edges[e].count += 1; + // Through a copy: the literal is written in place, its first element before the others are read. + const old = trail; + trail = .{ e, old[0], old[1] }; }; } prev = b; @@ -321,7 +347,7 @@ fn countBy(rec: *const Recording, g: *Graph, i: u64, whole: bool) void { g.trail = trail; } -/// The node holding `addr`, in nodes in address order. +/// The node holding `addr`, in nodes that are blocks in address order. fn blockAt(nodes: []const Node, addr: u64) ?u32 { var lo: usize = 0; var hi: usize = nodes.len; @@ -333,232 +359,199 @@ fn blockAt(nodes: []const Node, addr: u64) ?u32 { 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; +/// The span holding `addr`. +fn spanAt(spans: []const Span, addr: u64) ?usize { + var lo: usize = 0; + var hi: usize = spans.len; + while (lo < hi) { + const mid = (lo + hi) / 2; + if (spans[mid].start <= addr) lo = mid + 1 else hi = mid; } - g.* = folded; + if (lo == 0 or addr -% spans[lo - 1].start >= spans[lo - 1].len) return null; + return lo - 1; } -/// 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; -} +// ---------------------------------------------------------------- folds -/// 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); +/// The blocks of `g` (its nodes, unfolded and laid out, so with their +/// layers) not reached by the moment its counts are of, folded: the code +/// beyond each way the run has not taken, as far as it leads without +/// crossing into another way's (the deepest way first), each run of two +/// blocks or more; a block alone stays a quiet pill. As spans, address order. +fn notReached(arena: std.mem.Allocator, g: *const Graph) ![]const []const Span { + const n = g.nodes.len; + const quiet = try arena.alloc(bool, n); + for (g.nodes, quiet) |node, *q| q.* = node.visits == 0; + // The ways not taken: a quiet block an edge from a reached one goes to. + const entry = try arena.alloc(bool, n); + @memset(entry, false); + for (g.edges) |e| if (!quiet[e.from] and quiet[e.to]) { + entry[e.to] = true; + }; + var order: std.ArrayList(u32) = .empty; + for (entry, 0..) |is, k| if (is) try order.append(arena, @intCast(k)); + std.mem.sort(u32, order.items, g, struct { + fn deeper(gr: *const 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.start > nb.start; + } + }.deeper); + // Then what no way the run had leads to, from its first block. + for (quiet, 0..) |q, k| if (q and !entry[k]) try order.append(arena, @intCast(k)); + const claimed = try arena.alloc(bool, n); + @memset(claimed, false); + var groups: std.ArrayList([]const Span) = .empty; 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; - }; + var group: std.ArrayList(u32) = .empty; + for (order.items) |first| { + if (claimed[first]) continue; + group.clearRetainingCapacity(); + claimed[first] = true; + try stack.append(arena, first); + while (stack.pop()) |x| { + try group.append(arena, x); + for (g.edges) |e| if (e.from == x and quiet[e.to] and !claimed[e.to] and !entry[e.to]) { + claimed[e.to] = true; + try stack.append(arena, e.to); + }; + } + if (group.items.len < 2) continue; + std.mem.sort(u32, group.items, {}, std.sort.asc(u32)); + const spans = try arena.alloc(Span, group.items.len); + for (group.items, spans) |k, *s| s.* = .{ .start = g.nodes[k].start, .len = g.nodes[k].len, .node = 0 }; + try groups.append(arena, spans); } - return false; + return groups.items; } -/// `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 { +/// `g` (unfolded) with each fold of `groups` that `open` does not name one +/// node in the place of its first block (`folded` its blocks), the edges +/// to and from them joined. +fn fold(arena: std.mem.Allocator, g: *Graph, groups: []const []const Span, open: u64) !void { + const n = g.nodes.len; + const group_of = try arena.alloc(?usize, n); + @memset(group_of, null); + for (groups, 0..) |grp, k| if (k >= 64 or open & (@as(u64, 1) << @intCast(k)) == 0) for (grp) |s| if (g.nodeOf(s.start)) |x| { + group_of[x] = k; + }; + const into = try arena.alloc(u32, n); + const first_of = try arena.alloc(?u32, groups.len); + @memset(first_of, null); 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); + for (g.nodes, 0..) |node, x| { + if (group_of[x]) |k| if (first_of[k]) |f| { + into[x] = f; + nodes.items[f].folded += 1; continue; + }; + into[x] = @intCast(nodes.items.len); + var kept = node; + if (group_of[x]) |k| { + first_of[k] = into[x]; + kept = .{ .start = node.start, .len = node.len, .end = .fall, .folded = 1, .layer = node.layer }; } - 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; + try nodes.append(arena, kept); } - 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; + if (a == b and group_of[e.from] != null) 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; + if (e.kind == .fall) d.kind = .fall; 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; + const spans = try arena.dupe(Span, g.spans); + for (spans) |*s| s.node = into[s.node]; + g.nodes = nodes.items; + g.edges = edges.items; + g.spans = spans; + if (g.here) |h| g.here = into[h]; } -/// 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 }; +/// Whether the run had entered a block of `grp` by moment `i`. +fn reachedBy(rec: *const Recording, grp: []const Span, i: u64) bool { + var lo: u64 = std.math.maxInt(u64); + var hi: u64 = 0; + for (grp) |s| { + lo = @min(lo, s.start); + hi = @max(hi, s.start + s.len); } - - 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; - // For a strip: a tick at the row's top. - if (ui.strokes) return ui.collectMark(u, 0, y, .tick, 1); - 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); - } + for (rec.registers[0..@min(i + 1, rec.registers.len)]) |regs| { + if (regs.rip < lo or regs.rip >= hi) continue; + for (grp) |s| if (regs.rip -% s.start < s.len) return true; } -}; + return false; +} // ---------------------------------------------------------------- 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 { +/// The graph of the pc's function at moment `i`, laid out in `form` for a +/// pane `room` (its body's width and height) in a scene whose first moment +/// is `ref`: where it does not fit, folded as at `ref` (`notReached`), the +/// folds the run has reached a block of by `i` open. The layout is kept +/// per function, form, room, reference and open folds (`memo`); a frame +/// counts its own moment's visits again. +pub fn layout(arena: std.mem.Allocator, rec: *const Recording, i: u64, pc: u64, form: Form, room: [2]f32, ref: u64) ?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; + const groups = foldsOf(arena, rec, i, pc, start, form, room, ref) orelse return null; + var open: u64 = 0; + for (groups, 0..) |grp, k| if (k < 64 and reachedBy(rec, grp, i)) { + open |= @as(u64, 1) << @intCast(k); + }; + for (memo) |maybe| if (maybe) |k| if (k.rec == rec and k.start == start and k.form == form and k.room[0] == room[0] and k.room[1] == room[1] and k.ref == ref and k.open == open) { + 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 }); + fold(arena, &g, groups, open) catch return null; + sizes(rec, &g); + place(arena, &g, form) catch return null; + g.open = open; + remember(.{ .rec = rec, .start = start, .form = form, .room = room, .ref = ref, .open = open, .g = g }); + count(rec, &g, i); + g.here = g.nodeOf(pc); 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); +/// The folds of a function's layout: none where it fits its pane whole. +fn foldsOf(arena: std.mem.Allocator, rec: *const Recording, i: u64, pc: u64, start: u64, form: Form, room: [2]f32, ref: u64) ?[]const []const Span { + for (kept_folds) |maybe| if (maybe) |k| if (k.rec == rec and k.start == start and k.form == form and k.room[0] == room[0] and k.room[1] == room[1] and k.ref == ref) return k.groups; + var g = read(arena, rec, i, pc) orelse return null; + sizes(rec, &g); + place(arena, &g, form) catch return null; + var groups: []const []const Span = &.{}; + if (g.w > room[0] or g.h > room[1]) { + count(rec, &g, ref); + groups = notReached(arena, &g) catch return null; + } + const a = memo_memory.allocator(); + const copy = a.alloc([]const Span, groups.len) catch return null; + for (groups, copy) |grp, *c| c.* = a.dupe(Span, grp) catch return null; + kept_folds[folds_next] = .{ .rec = rec, .start = start, .form = form, .room = room, .ref = ref, .groups = copy }; + folds_next = (folds_next + 1) % kept_folds.len; + if (groups.len == 0) remember(.{ .rec = rec, .start = start, .form = form, .room = room, .ref = ref, .open = 0, .g = g }); + return copy; +} + +/// What `layout` made, kept: the blocks, their pills and their places are +/// the code's, not the moment's; a frame counts its own moment's visits +/// again (`recount`). +/// shortcut: process-wide, the last 32 layouts and 16 sets of folds kept and never freed (tens of KB each); two players at once would only share it. +const Kept = struct { rec: *const Recording, start: u64, form: Form, room: [2]f32, ref: u64, open: u64, g: Graph }; +var memo: [32]?Kept = @splat(null); var memo_next: usize = 0; +const Folds = struct { rec: *const Recording, start: u64, form: Form, room: [2]f32, ref: u64, groups: []const []const Span }; +var kept_folds: [16]?Folds = @splat(null); +var folds_next: usize = 0; var memo_memory: std.heap.ArenaAllocator = .init(std.heap.page_allocator); fn remember(k: Kept) void { @@ -566,6 +559,8 @@ fn remember(k: Kept) void { 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; + copy.g.spans = a.dupe(Span, k.g.spans) catch return; + copy.g.rings = a.dupe(Ring, k.g.rings) catch return; memo[memo_next] = copy; memo_next = (memo_next + 1) % memo.len; } @@ -575,125 +570,49 @@ fn recount(arena: std.mem.Allocator, rec: *const Recording, kept_g: Graph, i: u6 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); + count(rec, &g, i); + g.here = g.nodeOf(pc); 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; - }, - }; +/// Each node's pill: 24 high, as wide as its words (its offset, the +/// functions it calls) and its visits, with room kept for `×99` so that it +/// never widens as the run counts; a fold as wide as its words, `+5b … · 7`. +pub fn sizes(rec: *const Recording, g: *Graph) void { + const adv = ui.advance(theme.size.mono.context); + for (g.nodes) |*n| { + const chars: f32 = @floatFromInt(if (n.folded > 0) foldChars(g.*, n.*) else wordsLen(rec, g.*, n.*) + 1 + gm.count_chars); + n.w = 2 * gm.pill_in + chars * adv + gm.spare; + n.h = gm.pill; + } } -/// 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; +/// The characters of a fold's words, `+5b … · 7`. +fn foldChars(g: Graph, n: Node) usize { + return std.fmt.count("+{x}", .{n.start - g.start}) + 5 + std.fmt.count("{d}", .{n.folded}); } -/// 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; +/// The characters of a block's words: its offset, then each callee after a space (two, then `…`). +fn wordsLen(rec: *const Recording, g: Graph, n: Node) usize { + var len = std.fmt.count("+{x}", .{n.start - g.start}); + for (n.calls) |c| if (c != 0) { + len += 1 + if (callee(rec, c)) |name| name.len else 0; }; - 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; + if (n.more_calls) len += 2; + return len; +} + +/// Lays `g` out (its pills' sizes given) in `form`: where every pill is and +/// every edge's way. Pure: the code alone (its blocks, its edges, its +/// pills), never the run, so the picture is the same at every moment. +pub fn place(arena: std.mem.Allocator, g: *Graph, form: Form) std.mem.Allocator.Error!void { + if (g.nodes.len == 0) return; + for (g.edges) |*e| e.back = false; + try backEdges(g, arena); + try layers(g, arena); + g.rings = &.{}; + if (form == .rings and try placeRings(arena, g)) return; + try placeLayers(arena, g); } /// Back edges: those a walk from the entry (then from each block not yet @@ -772,16 +691,15 @@ fn layers(g: *Graph, tmp: std.mem.Allocator) !void { }; } 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); - }; + for (g.nodes) |node| { + if (node.end == .ret) { + any_ret = true; + deepest_ret = @max(deepest_ret, node.layer); + } else last = @max(last, node.layer); + } + if (!any_ret) return; const others_last = for (g.nodes) |node| { if (node.end != .ret and node.layer == @max(last, deepest_ret)) break true; } else false; @@ -791,16 +709,62 @@ fn layers(g: *Graph, tmp: std.mem.Allocator) !void { }; } -/// 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. +// ---------------------------------------------------------------- layers + +/// `layers`: a layer at a time, a block under its fall-through predecessor +/// (else the one it is jumped to from), a taken target right of its +/// branch; where two want one column the fall-through has it, then the +/// lower address, the other the next free column to the right. Columns +/// 300 apart, layers 12; the back edges in lanes on the left, the +/// outermost loop farthest out. +fn placeLayers(arena: std.mem.Allocator, g: *Graph) std.mem.Allocator.Error!void { + const nodes = g.nodes; + try columns(g, arena); + var order: std.ArrayList(u32) = .empty; + for (g.edges, 0..) |e, k| if (e.back) try order.append(arena, @intCast(k)); + std.mem.sort(u32, order.items, 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.items, 0..) |e, k| g.edges[e].lane = @intCast(k); + const nb: u32 = @intCast(order.items.len); + g.lanes = nb; + 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(gm.pitch, widest + 2 * gm.apart); + const x0: f32 = if (nb > 0) gm.lane_in + @as(f32, @floatFromInt(nb)) * gm.lane + gm.blocks_in else 0; + const tops = try arena.alloc(f32, last_layer + 2); + const heights = try arena.alloc(f32, last_layer + 1); + @memset(heights, 0); + for (nodes) |n| heights[n.layer] = @max(heights[n.layer], n.h); + tops[0] = gm.top; + for (heights, 0..) |h, k| tops[k + 1] = tops[k] + h + gm.layer_gap; + var right: 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); + } + g.channel = right + gm.channel; + try route(g, tops, heights, arena); + normalize(g); +} + +/// Columns, a layer at a time (`placeLayers`), from the code alone. 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 }; + const Want = struct { node: u32, col: u32, fall: bool }; var wants: std.ArrayList(Want) = .empty; var used: std.ArrayList(u32) = .empty; const placed = try tmp.alloc(bool, n); @@ -810,18 +774,20 @@ fn columns(g: *Graph, tmp: std.mem.Allocator) !void { 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; + // The fall-through, then a block's (not a fold's), then the lower address. + const better = if (best) |b| blk: { + if ((e.kind == .fall) != (b.kind == .fall)) break :blk e.kind == .fall; + const own = g.nodes[e.from].folded == 0; + if (own != (g.nodes[b.from].folded == 0)) break :blk own; + break :blk 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 }); + const col: u32, const fall = if (best) |b| .{ g.nodes[b.from].col + @intFromBool(b.kind == .taken), b.kind == .fall } else .{ 0, false }; + try wants.append(tmp, .{ .node = @intCast(k), .col = col, .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; } @@ -837,13 +803,13 @@ fn columns(g: *Graph, tmp: std.mem.Allocator) !void { } } -/// 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 { +/// Every edge's way in `layers`. Forward: out of the foot on the side its +/// target is on (16 in from the end, 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 16 apart); through the right channel where it +/// would cross a block. Back: down 8, out to its lane, up it, into its +/// header's end. Every corner a quarter circle of 12. +fn route(g: *Graph, 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); @@ -864,13 +830,13 @@ fn route(g: *Graph, m: Metric, tops: []const f32, heights: []const f32, tmp: std 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; + const lx = gm.lane_in + @as(f32, @floatFromInt(e.lane)) * gm.lane; + const by = under + gm.back_down + @as(f32, @floatFromInt(back_tracks[src.layer])) * gm.track; 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; + const sx = src.x + gm.port; + const hy = dst.cy(); + const p = rounded(&.{ .{ sx, src.y + src.h }, .{ sx, by }, .{ lx, by }, .{ lx, hy }, .{ dst.x, hy } }, gm.corner); + e.set(&p); continue; } // Its place among the arrivals into its target's top. @@ -881,103 +847,843 @@ fn route(g: *Graph, m: Metric, tops: []const f32, heights: []const f32, tmp: std 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 tx = dst.cx() + (@as(f32, @floatFromInt(slot)) - @as(f32, @floatFromInt(srcs - 1)) / 2) * gm.port; 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; + const side = if (crosses) 1 else dst.cx() - src.cx(); + const sx = if (!crosses and @abs(side) < src.w / 2 - gm.port) src.cx() else if (side > 0) src.x + src.w - gm.port else src.x + gm.port; + const gy = under + gm.layer_gap / 2 + @as(f32, @floatFromInt(tracks[src.layer] % 2)) * gm.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; + const p = if (crosses) blk: { + const gy2 = tops[dst.layer] - gm.layer_gap / 2; + break :blk rounded(&.{ .{ sx, src.y + src.h }, .{ sx, gy }, .{ g.channel, gy }, .{ g.channel, gy2 }, .{ tx, gy2 }, .{ tx, dst.y } }, gm.corner); + } else rounded(&.{ .{ sx, src.y + src.h }, .{ sx, gy }, .{ tx, gy }, .{ tx, dst.y } }, gm.corner); + e.set(&p); + }; +} + +/// How far down a drawing too tall for its pane (`room` high) is scrolled: +/// by thirds of the pane, so that the pc's pill is in its middle third. +fn pan(g: Graph, room: f32) f32 { + if (g.h <= room) return 0; + const h = g.here orelse return 0; + const third = room / 3; + return std.math.clamp(@floor((g.nodes[h].cy() - third) / third) * third, 0, g.h - room); +} + +// ---------------------------------------------------------------- rings + +/// A loop: its header, its body (the blocks that reach its latches without +/// passing the header, merged by header), the loop it is nested in, and its +/// ring: its members (its blocks not in a loop nested in it, and those +/// loops' headers) clockwise in the order they run, their angles, its +/// radius, its centre. +const Loop = struct { + header: u32, + body: []bool, + size: u32 = 0, + parent: ?usize = null, + members: []u32 = &.{}, + /// Radians, clockwise on the screen from 3 o'clock: the header at π. + angles: []f32 = &.{}, + r: f32 = 0, + /// Its centre from its parent's (a top-level loop's: from its header's), and where it is in the drawing. + c: [2]f32 = .{ 0, 0 }, + abs: [2]f32 = .{ 0, 0 }, +}; + +/// The natural loops of `g` (its back edges known), merged by header, each with its parent and its ring's members. +fn loopsOf(arena: std.mem.Allocator, g: *const Graph) ![]Loop { + var loops: std.ArrayList(Loop) = .empty; + var stack: std.ArrayList(u32) = .empty; + for (g.edges) |e| if (e.back) { + const li = for (loops.items, 0..) |l, i| { + if (l.header == e.to) break i; + } else blk: { + const body = try arena.alloc(bool, g.nodes.len); + @memset(body, false); + body[e.to] = true; + try loops.append(arena, .{ .header = e.to, .body = body }); + break :blk loops.items.len - 1; + }; + const body = loops.items[li].body; + if (!body[e.from]) { + body[e.from] = true; + try stack.append(arena, e.from); + } + while (stack.pop()) |x| for (g.edges) |f| if (f.to == x and !body[f.from]) { + body[f.from] = true; + try stack.append(arena, f.from); + }; + }; + const ls = loops.items; + for (ls) |*l| for (l.body) |b| { + l.size += @intFromBool(b); + }; + for (ls, 0..) |*l, i| { + var best: ?usize = null; + for (ls, 0..) |o, j| if (j != i and o.body[l.header] and o.size > l.size and (best == null or o.size < ls[best.?].size)) { + best = j; + }; + l.parent = best; + } + for (ls, 0..) |*l, i| { + var list: std.ArrayList(u32) = .empty; + try list.append(arena, l.header); + for (l.body, 0..) |in, k| if (in and k != l.header) { + const deeper = for (ls) |o| { + if (o.parent == i and o.body[k] and o.header != k) break true; + } else false; + if (!deeper) try list.append(arena, @intCast(k)); + }; + std.mem.sort(u32, list.items[1..], g, struct { + fn first(gr: *const 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.start < nb.start; + } + }.first); + l.members = list.items; + l.angles = try arena.alloc(f32, list.items.len); + } + return ls; +} + +const Box = [4]f32; + +fn dist(a: [2]f32, b: [2]f32) f32 { + return @sqrt((b[0] - a[0]) * (b[0] - a[0]) + (b[1] - a[1]) * (b[1] - a[1])); +} + +/// How far apart two boxes are (0 where they meet). +fn gap(a: Box, b: Box) f32 { + const dx = @max(b[0] - a[2], a[0] - b[2], 0); + const dy = @max(b[1] - a[3], a[1] - b[3], 0); + return @sqrt(dx * dx + dy * dy); +} + +fn shifted(b: Box, d: [2]f32) Box { + return .{ b[0] + d[0], b[1] + d[1], b[2] + d[0], b[3] + d[1] }; +} + +/// A pill `w` wide on a ring of radius `r` round the origin at angle `a`. +fn pillAt(r: f32, a: f32, w: f32) Box { + const x = r * @cos(a); + const y = r * @sin(a); + return .{ x - w / 2, y - gm.pill / 2, x + w / 2, y + gm.pill / 2 }; +} + +/// A way out of a loop as it leaves a pill at angle `a` on its ring: down +/// from its foot, 30 in from the end farther from the ring's centre, as far as anything can be. +fn exitLine(p: Box, a: f32) Box { + const x = if (@cos(a) < 0) p[0] + gm.exit_in else p[2] - gm.exit_in; + return .{ x - 1, p[3], x + 1, 1e6 }; +} + +/// Where a ring leaves a pill at angle `a`, along the ring from its centre (on the tangent, near enough). +fn cutLen(a: f32, w: f32) f32 { + const s = @abs(@sin(a)); + const c = @abs(@cos(a)); + return @min(if (s > 1e-4) w / 2 / s else 1e9, if (c > 1e-4) gm.pill / 2 / c else 1e9); +} + +/// The fitting of one ring: its members' widths, which have a way out of +/// the loop, which gaps are edges (arcs), the member at 3 o'clock and the +/// child loop there (its pills and ways out the others keep clear of; the +/// blocks its ways out go to under its foot). +const Fit = struct { + w: []f32, + exits: []bool, + arcs: []bool, + three: ?usize, + child_r: f32, + pills: []Box, + lines: []Box, + below: []f32, + cur: []?f32, + fwd: []?f32, + bwd: []?f32, + + const step = std.math.degreesToRadians(0.5); + + /// Whether member `k` at angle `a` on a ring of radius `r` keeps clear of everything placed in `at`. + fn clear(f: *const Fit, r: f32, placed: []const ?f32, k: usize, a: f32) bool { + const p = pillAt(r, a, f.w[k]); + if (r * @sin(a) < f.below[k]) return false; + const off: [2]f32 = .{ r + f.child_r, 0 }; + const line: ?Box = if (f.exits[k]) exitLine(p, a) else null; + for (f.pills) |o| { + if (gap(p, shifted(o, off)) < gm.apart) return false; + if (line) |l| if (gap(l, shifted(o, off)) < gm.apart) return false; + } + for (f.lines) |o| if (gap(p, shifted(o, off)) < gm.apart) return false; + for (placed, 0..) |maybe, j| if (j != k) if (maybe) |b| { + const q = pillAt(r, b, f.w[j]); + if (gap(p, q) < gm.apart) return false; + if (f.exits[j] and gap(p, exitLine(q, b)) < gm.apart) return false; + if (line) |l| if (gap(q, l) < gm.apart) return false; + }; + return true; + } + + /// Whether the arc from member `j` at `a` to the next, `k` at `b`, is long enough to read (where it is an edge). + fn arcOk(f: *const Fit, r: f32, j: usize, a: f32, k: usize, b: f32) bool { + if (!f.arcs[j]) return true; + return r * (b - a) - cutLen(a, f.w[j]) - cutLen(b, f.w[k]) >= gm.arc_least; + } + + /// Fits the ring at radius `r`: the header at π, the member at 3 + /// o'clock at 2π, each run of members between two fixed ones from as + /// early as it can be to as late, halfway. False where they do not fit. + fn fit(f: *Fit, r: f32) bool { + const n = f.w.len; + @memset(f.cur, null); + f.cur[0] = pi; + if (f.three) |k| { + f.cur[k] = 2 * pi; + if (!f.clear(r, f.cur, k, 2 * pi)) return false; + } + var a: usize = 0; + while (a < n) { + var b = a + 1; + while (b < n and f.cur[b] == null) b += 1; + const from = f.cur[a].?; + const to = if (b < n) f.cur[b].? else 3 * pi; + // As early as each can be, then as late. + @memcpy(f.fwd, f.cur); + var prev = a; + for (a + 1..b) |k| { + var th = f.fwd[prev].? + step; + while (th < to and !(f.clear(r, f.fwd, k, th) and f.arcOk(r, prev, f.fwd[prev].?, k, th))) th += step; + if (th >= to) return false; + f.fwd[k] = th; + prev = k; + } + if (!f.arcOk(r, prev, f.fwd[prev].?, b % n, to)) return false; + @memcpy(f.bwd, f.cur); + var next = b; + var k = b; + while (k > a + 1) { + k -= 1; + const next_th = if (next < n) f.bwd[next].? else to; + var th = next_th - step; + while (th > from and !(f.clear(r, f.bwd, k, th) and f.arcOk(r, k, th, next % n, next_th))) th -= step; + f.bwd[k] = if (th > f.fwd[k].?) th else f.fwd[k]; + next = k; + } + for (a + 1..b) |j| f.cur[j] = (f.fwd[j].? + f.bwd[j].?) / 2; + // Halfway may not hold where the two ways differ much: then as early as each can be. + const holds = for (a + 1..b) |j| { + if (!f.clear(r, f.cur, j, f.cur[j].?) or !f.arcOk(r, j - 1, f.cur[j - 1].?, j, f.cur[j].?)) break false; + } else f.arcOk(r, b - 1, f.cur[b - 1].?, b % n, to); + if (!holds) for (a + 1..b) |j| { + f.cur[j] = f.fwd[j]; + }; + a = b; + } + return true; + } +}; + +/// The pills and the ways out of loop `li`'s cluster (its ring and the +/// rings nested in it), round its centre at `o`, but its own header's pill. +fn cluster(arena: std.mem.Allocator, g: *const Graph, loops: []const Loop, li: usize, o: [2]f32, pills: *std.ArrayList(Box), lines: *std.ArrayList(Box)) !void { + const l = loops[li]; + for (l.members, l.angles, 0..) |m, a, k| { + const p = shifted(pillAt(l.r, a, g.nodes[m].w), o); + if (k > 0) try pills.append(arena, p); + if (leavesLoop(g, l, m)) try lines.append(arena, exitLine(p, a)); + } + for (loops, 0..) |c, ci| if (c.parent == li) try cluster(arena, g, loops, ci, .{ o[0] + c.c[0], o[1] + c.c[1] }, pills, lines); +} + +/// Whether block `m` of loop `l` has an edge out of it. +fn leavesLoop(g: *const Graph, l: Loop, m: u32) bool { + for (g.edges) |e| if (e.from == m and !l.body[e.to]) return true; + return false; +} + +/// Fits loop `li`'s ring, its children's fitted: the least radius at which +/// its pills (on it at their centres, upright) are 12 apart from each +/// other and from those of the rings nested in it, an arc between two that +/// is an edge is long enough to read, no way out down from one crosses +/// another, and the blocks a nested loop's ways out go to are under its +/// foot; the header at 9 o'clock, the first nested loop's header (or else +/// the first block with a way out) at 3 o'clock, the nested ring outside, +/// touching there. +/// shortcut: only the first nested loop sits at 3 o'clock; any other hangs out from its header's angle, turned with it, and is not kept clear of; upgrade when a recording has two loops in one. +fn fitRing(arena: std.mem.Allocator, g: *const Graph, loops: []Loop, li: usize) !bool { + const l = &loops[li]; + const ms = l.members; + const n = ms.len; + var f: Fit = .{ .w = try arena.alloc(f32, n), .exits = try arena.alloc(bool, n), .arcs = try arena.alloc(bool, n), .three = null, .child_r = 0, .pills = &.{}, .lines = &.{}, .below = try arena.alloc(f32, n), .cur = try arena.alloc(?f32, n), .fwd = try arena.alloc(?f32, n), .bwd = try arena.alloc(?f32, n) }; + for (ms, 0..) |m, k| { + f.w[k] = g.nodes[m].w; + f.exits[k] = leavesLoop(g, l.*, m); + f.arcs[k] = g.edgeOf(m, ms[(k + 1) % n]) != null; + f.below[k] = -std.math.inf(f32); + } + var child: ?usize = null; + for (ms[1..], 1..) |m, k| { + const c = for (loops, 0..) |o, ci| { + if (o.parent == li and o.header == m) break ci; + } else null; + if (c != null or f.exits[k]) { + f.three = k; + child = c; + break; + } + } + if (child) |ci| { + const c = loops[ci]; + var pills: std.ArrayList(Box) = .empty; + var lines: std.ArrayList(Box) = .empty; + try cluster(arena, g, loops, ci, .{ 0, 0 }, &pills, &lines); + f.pills = pills.items; + f.lines = lines.items; + f.child_r = c.r; + var foot: f32 = c.r * @sin(c.angles[0]) + gm.pill / 2; + for (pills.items) |p| foot = @max(foot, p[3]); + for (ms, 0..) |m, k| for (g.edges) |e| if (e.to == m and c.body[e.from] and !c.body[m]) { + f.below[k] = foot + gm.apart + gm.pill / 2; + }; + } + // The least radius: coarse, then fine. + var r: f32 = gm.pill; + while (!f.fit(r)) { + r += 16; + if (r > 2000) return false; + } + if (r > gm.pill) { + r -= 14; + while (!f.fit(r)) r += 2; + } + l.r = r; + for (l.angles, f.cur) |*a, c| a.* = c.?; + if (child) |ci| loops[ci].c = .{ r + loops[ci].r, 0 }; + for (loops, 0..) |*c, ci| if (c.parent == li and ci != child) { + const a = l.angles[std.mem.indexOfScalar(u32, ms, c.header).?]; + turnBy(loops, ci, a); + c.c = .{ (r + c.r) * @cos(a), (r + c.r) * @sin(a) }; + }; + return true; +} + +/// Turns loop `li`'s ring (and those nested in it) by `a` about its centre. +fn turnBy(loops: []Loop, li: usize, a: f32) void { + for (loops[li].angles) |*x| x.* += a; + for (loops, 0..) |*c, ci| if (c.parent == li) { + const was = c.c; + c.c = .{ was[0] * @cos(a) - was[1] * @sin(a), was[0] * @sin(a) + was[1] * @cos(a) }; + turnBy(loops, ci, a); + }; +} + +/// Puts loop `li`'s pills (and its nested loops') round its centre at `o`. +fn putCluster(g: *Graph, loops: []Loop, li: usize, o: [2]f32) void { + const l = &loops[li]; + l.abs = o; + for (l.members, l.angles) |m, a| { + const n = &g.nodes[m]; + n.x = o[0] + l.r * @cos(a) - n.w / 2; + n.y = o[1] + l.r * @sin(a) - n.h / 2; + } + for (loops, 0..) |c, ci| if (c.parent == li) putCluster(g, loops, ci, .{ o[0] + c.c[0], o[1] + c.c[1] }); +} + +/// A part of `g`, its nodes those `in` names (renumbered; `of` each one's +/// in `g`), with the edges between them. +const Sub = struct { g: Graph, of: []u32 }; + +fn subgraph(arena: std.mem.Allocator, g: *const Graph, in: []const bool) !Sub { + var of: std.ArrayList(u32) = .empty; + const idx = try arena.alloc(u32, g.nodes.len); + for (in, 0..) |x, k| if (x) { + idx[k] = @intCast(of.items.len); + try of.append(arena, @intCast(k)); + }; + const nodes = try arena.alloc(Node, of.items.len); + for (of.items, nodes) |k, *n| n.* = g.nodes[k]; + var edges: std.ArrayList(Edge) = .empty; + for (g.edges) |e| if (in[e.from] and in[e.to]) { + var c = e; + c.from = idx[e.from]; + c.to = idx[e.to]; + try edges.append(arena, c); + }; + return .{ .g = .{ .start = g.start, .len = g.len, .nodes = nodes, .edges = edges.items, .spans = &.{}, .here = null, .text = g.text, .exact = g.exact }, .of = of.items }; +} + +/// Takes a placed part's places and ways into `g`, moved by `d`; marks the ways it brings. +fn adopt(g: *Graph, s: Sub, d: [2]f32, routed: []bool) void { + for (s.g.nodes, s.of) |n, k| { + g.nodes[k].x = n.x + d[0]; + g.nodes[k].y = n.y + d[1]; + } + for (s.g.edges) |e| { + const k = g.edgeOf(s.of[e.from], s.of[e.to]) orelse continue; + var moved = e; + for (moved.points[0..e.n]) |*p| p.* = .{ p[0] + d[0], p[1] + d[1] }; + g.edges[k].points = moved.points; + g.edges[k].n = e.n; + routed[k] = true; + } +} + +/// `rings`: each loop a ring, the first loop's rings in the middle (its +/// header at the origin), the blocks before it laid as `layers` lays them +/// left of its header (the one that comes in on its line), those after it +/// as this form lays them under its header, as high as they clear the +/// rings. False where the function has no loop (or no ring fits). +/// shortcut: a second loop that is no other's is laid among the blocks after the first (rings) or before it (layers); a way between the blocks before and after a loop goes round no ring; upgrade when a recording has one. +fn placeRings(arena: std.mem.Allocator, g: *Graph) std.mem.Allocator.Error!bool { + const loops = try loopsOf(arena, g); + if (loops.len == 0) return false; + // The rings nested deepest first. + const order = try arena.alloc(usize, loops.len); + for (order, 0..) |*o, k| o.* = k; + std.mem.sort(usize, order, loops, struct { + fn smaller(ls: []Loop, a: usize, b: usize) bool { + return ls[a].size < ls[b].size; + } + }.smaller); + for (order) |li| if (!try fitRing(arena, g, loops, li)) return false; + var top: usize = undefined; + var found = false; + for (loops, 0..) |l, i| if (l.parent == null and (!found or g.nodes[l.header].layer < g.nodes[loops[top].header].layer)) { + top = i; + found = true; + }; + const lt = &loops[top]; + putCluster(g, loops, top, .{ lt.r, 0 }); + const header = g.nodes[lt.header]; + const n = g.nodes.len; + // Its parts: before it, it, after it. + const part = try arena.alloc(u8, n); + for (part, lt.body) |*p, in| p.* = if (in) 1 else 0; + var stack: std.ArrayList(u32) = .empty; + for (lt.body, 0..) |in, k| if (in) try stack.append(arena, @intCast(k)); + while (stack.pop()) |x| for (g.edges) |e| if (e.from == x and part[e.to] == 0) { + part[e.to] = 2; + try stack.append(arena, e.to); + }; + const routed = try arena.alloc(bool, g.edges.len); + @memset(routed, false); + const in = try arena.alloc(bool, n); + var way_in: ?u32 = null; + var pills: std.ArrayList(Box) = .empty; + for (g.nodes, part) |node, p| if (p == 1) try pills.append(arena, node.box()); + // Before it: left of the header, the block that comes in on its line. + for (part, in) |p, *x| x.* = p == 0; + if (std.mem.indexOfScalar(bool, in, true) != null) { + var s = try subgraph(arena, g, in); + try place(arena, &s.g, .layers); + var right: f32 = 0; + for (s.g.nodes) |node| right = @max(right, node.x + node.w); + var anchor: ?usize = null; + for (s.of, 0..) |k, j| if (g.edgeOf(k, lt.header) != null and (anchor == null or g.nodes[k].layer > g.nodes[s.of[anchor.?]].layer)) { + anchor = j; + }; + const dy = if (anchor) |j| header.cy() - s.g.nodes[j].cy() else header.y - gm.apart - s.g.h; + adopt(g, s, .{ header.x - gm.way_in - right, dy }, routed); + if (anchor) |j| way_in = s.of[j]; + for (s.of) |k| try pills.append(arena, g.nodes[k].box()); + } + // After it: under the header, the block its way out goes to on that way, as high as all clear the rings. + for (part, in) |p, *x| x.* = p == 2; + if (std.mem.indexOfScalar(bool, in, true) != null) { + var s = try subgraph(arena, g, in); + try place(arena, &s.g, .rings); + var anchor: usize = 0; + var best: ?u32 = null; + for (s.of, 0..) |k, j| for (g.edges) |e| if (e.to == k and lt.body[e.from]) { + const rank: u32 = if (e.from == lt.header) 0 else 1 + g.nodes[k].layer; + if (best == null or rank < best.?) { + best = rank; + anchor = j; + } + }; + const a = s.g.nodes[anchor]; + const dx = header.x + gm.exit_in - a.cx(); + var dy = header.y + header.h + gm.apart - a.y; + while (dy < 1e5) : (dy += 2) { + const fits = for (s.g.nodes) |node| { + const b = shifted(node.box(), .{ dx, dy }); + const near = for (pills.items) |p| { + if (gap(b, p) < gm.apart) break true; + } else false; + if (near) break false; + const crosses = for (loops) |l| { + const q: [2]f32 = .{ std.math.clamp(l.abs[0], b[0], b[2]), std.math.clamp(l.abs[1], b[1], b[3]) }; + if (dist(q, l.abs) < l.r + gm.apart) break true; + } else false; + if (crosses) break false; + } else true; + if (fits) break; + } + adopt(g, s, .{ dx, dy }, routed); + } + // The ways the parts did not bring. + for (g.edges, 0..) |*e, k| if (!routed[k]) { + var p: Path = .{}; + const a = g.nodes[e.from]; + const b = g.nodes[e.to]; + if (sharedRing(loops, e.from, e.to)) |sr| { + // Round the ring: to the next block on it an arc of it; past blocks of it an arc 30 inside. + const l = loops[sr[0]]; + const a0 = l.angles[sr[1]]; + var a1 = l.angles[sr[2]]; + while (a1 <= a0 + 1e-4) a1 += 2 * pi; + const next = (sr[1] + 1) % l.members.len == sr[2]; + if (!next) p.to(a.cx(), a.cy()); + p.arc(l.abs, if (next) l.r else l.r - gm.fork_in, a0, a1); + if (!next) p.to(b.cx(), b.cy()); + p.trim(a, b); + } else if (ringOf(loops, e.from, e.to)) |ra| { + wayOut(&p, a, ra, b); + } else if (way_in == e.from and e.to == lt.header and @abs(a.cy() - b.cy()) < 0.5) { + p.to(a.x + a.w, a.cy()); + p.to(b.x, b.cy()); + } else elbow(&p, a, b); + e.set(&p); + }; + var ring_list: std.ArrayList(Ring) = .empty; + for (loops) |l| try ring_list.append(arena, .{ .c = l.abs, .r = l.r, .header = l.header }); + g.rings = ring_list.items; + normalize(g); + return true; +} + +/// The ring two blocks are both on (the deepest), and where each is on it. +fn sharedRing(loops: []const Loop, a: u32, b: u32) ?[3]usize { + var best: ?[3]usize = null; + for (loops, 0..) |l, i| { + const ia = std.mem.indexOfScalar(u32, l.members, a) orelse continue; + const ib = std.mem.indexOfScalar(u32, l.members, b) orelse continue; + if (best == null or l.size < loops[best.?[0]].size) best = .{ i, ia, ib }; + } + return best; +} + +/// For an edge out of a loop (from `a` in one whose body `b` is not in): +/// where `a` is on its own ring (the deepest it is on). +fn ringOf(loops: []const Loop, a: u32, b: u32) ?f32 { + const leaves = for (loops) |l| { + if (l.body[a] and !l.body[b]) break true; + } else false; + if (!leaves) return null; + var best: ?usize = null; + var at: f32 = 0; + for (loops, 0..) |l, i| if (std.mem.indexOfScalar(u32, l.members, a)) |k| if (best == null or l.size < loops[best.?].size) { + best = i; + at = l.angles[k]; + }; + return if (best != null) at else null; +} + +/// A loop's way out, from `a` at angle `angle` on its ring to `b`: out of +/// its foot 30 in from the end farther from the ring's centre, straight +/// down, then a quarter circle of 16 into `b`'s near end, or straight +/// into its top where it is under. +fn wayOut(p: *Path, a: Node, angle: f32, b: Node) void { + const x = if (@cos(angle) < 0) a.x + gm.exit_in else a.x + a.w - gm.exit_in; + const y = a.y + a.h; + if (b.y >= y + gm.bend and x >= b.x + b.h / 2 and x <= b.x + b.w - b.h / 2) { + p.to(x, y); + p.to(x, b.y); + } else if (b.cy() >= y + gm.bend) { + const tx = if (b.cx() < x) b.x + b.w else b.x; + p.* = rounded(&.{ .{ x, y }, .{ x, b.cy() }, .{ tx, b.cy() } }, gm.bend); + } else elbow(p, a, b); +} + +/// Any other way: down from `a`'s foot, across, down into `b`'s top, its +/// bends quarter circles of 16. +/// shortcut: to a block not under its source the way is a straight line, which may cross a ring; upgrade when a recording has one. +fn elbow(p: *Path, a: Node, b: Node) void { + const sy = a.y + a.h; + if (b.y > sy + 2 * gm.bend) { + const my = (sy + b.y) / 2; + p.* = rounded(&.{ .{ a.cx(), sy }, .{ a.cx(), my }, .{ b.cx(), my }, .{ b.cx(), b.y } }, gm.bend); + return; + } + p.to(a.cx(), a.cy()); + p.to(b.cx(), b.cy()); + p.trim(a, b); +} + +/// Moves the drawing to the origin: its pills, its ways, its rings and their turns; its size. +fn normalize(g: *Graph) void { + var lo: [2]f32 = .{ std.math.inf(f32), std.math.inf(f32) }; + var hi: [2]f32 = .{ -std.math.inf(f32), -std.math.inf(f32) }; + const grow = struct { + fn by(l: *[2]f32, h: *[2]f32, b: Box) void { + l.* = .{ @min(l[0], b[0]), @min(l[1], b[1]) }; + h.* = .{ @max(h[0], b[2]), @max(h[1], b[3]) }; } + }.by; + for (g.nodes) |n| grow(&lo, &hi, n.box()); + for (g.edges) |e| for (e.path()) |p| grow(&lo, &hi, .{ p[0] - 4, p[1] - 4, p[0] + 4, p[1] + 4 }); + for (g.rings) |r| grow(&lo, &hi, .{ r.c[0] - 60, r.c[1], r.c[0] + 60, r.c[1] + gm.turns_down + 12 }); + if (lo[0] > hi[0]) return; + for (g.nodes) |*n| { + n.x -= lo[0]; + n.y -= lo[1]; + } + for (g.edges) |*e| for (e.points[0..e.n]) |*p| { + p.* = .{ p[0] - lo[0], p[1] - lo[1] }; }; + for (g.rings) |*r| r.c = .{ r.c[0] - lo[0], r.c[1] - lo[1] }; + g.channel -= lo[0]; + g.w = hi[0] - lo[0]; + g.h = hi[1] - lo[1]; } +// ---------------------------------------------------------------- paths + +/// A way being made: straight runs and arcs, as points. +const Path = struct { + pts: [most][2]f32 = undefined, + n: usize = 0, + + fn to(p: *Path, x: f32, y: f32) void { + if (p.n > 0 and @abs(p.pts[p.n - 1][0] - x) < 0.01 and @abs(p.pts[p.n - 1][1] - y) < 0.01) return; + if (p.n == most) return; + p.pts[p.n] = .{ x, y }; + p.n += 1; + } + + /// Round the circle at `c` of radius `r` from angle `a0` to `a1` (clockwise on the screen as the angle grows). + fn arc(p: *Path, c: [2]f32, r: f32, a0: f32, a1: f32) void { + // Chords of 5 units or so: smooth at any radius, and few. + const steps: usize = @intFromFloat(std.math.clamp(@ceil(@abs(a1 - a0) * r / 5), 2, 40)); + for (0..steps + 1) |k| { + const a = std.math.lerp(a0, a1, @as(f32, @floatFromInt(k)) / @as(f32, @floatFromInt(steps))); + p.to(c[0] + r * @cos(a), c[1] + r * @sin(a)); + } + } + + /// Cut where the way leaves `a`'s pill and where it enters `b`'s: it runs frame to frame. + fn trim(p: *Path, a: Node, b: Node) void { + if (p.n < 2) return; + var first: usize = 0; + while (first < p.n and a.has(p.pts[first])) first += 1; + var last: usize = p.n; + while (last > first and b.has(p.pts[last - 1])) last -= 1; + if (first == p.n or last == first) return; + var out: Path = .{}; + if (first > 0) out.to2(frameOf(a, p.pts[first - 1], p.pts[first])); + for (p.pts[first..last]) |q| out.to2(q); + if (last < p.n) out.to2(frameOf(b, p.pts[last], p.pts[last - 1])); + p.* = out; + } + + fn to2(p: *Path, q: [2]f32) void { + p.to(q[0], q[1]); + } + + /// Where the segment from `in` (inside `n`'s pill) to `out` crosses its frame. + fn frameOf(n: Node, in: [2]f32, out: [2]f32) [2]f32 { + var lo = in; + var hi = out; + for (0..16) |_| { + const mid: [2]f32 = .{ (lo[0] + hi[0]) / 2, (lo[1] + hi[1]) / 2 }; + if (n.has(mid)) lo = mid else hi = mid; + } + return hi; + } +}; + +/// The polyline through `pts` (each turn a right angle), every corner a +/// quarter circle of `r` (less where a leg is shorter than twice that). +fn rounded(pts: []const [2]f32, r: f32) Path { + var p: Path = .{}; + if (pts.len == 0) return p; + p.to(pts[0][0], pts[0][1]); + for (1..pts.len -| 1) |i| { + const a = pts[i - 1]; + const b = pts[i]; + const c = pts[i + 1]; + const la = dist(a, b); + const lc = dist(b, c); + if (la < 0.01 or lc < 0.01) continue; + const k = @min(r, la / 2, lc / 2); + const da: [2]f32 = .{ (a[0] - b[0]) / la, (a[1] - b[1]) / la }; + const dc: [2]f32 = .{ (c[0] - b[0]) / lc, (c[1] - b[1]) / lc }; + if (@abs(da[0] * dc[0] + da[1] * dc[1]) > 0.99) { + p.to(b[0], b[1]); + continue; + } + const o: [2]f32 = .{ b[0] + (da[0] + dc[0]) * k, b[1] + (da[1] + dc[1]) * k }; + const a0 = std.math.atan2(b[1] + da[1] * k - o[1], b[0] + da[0] * k - o[0]); + var a1 = std.math.atan2(b[1] + dc[1] * k - o[1], b[0] + dc[0] * k - o[0]); + if (a1 - a0 > pi) a1 -= 2 * pi; + if (a0 - a1 > pi) a1 += 2 * pi; + p.arc(o, k, a0, a1); + } + p.to(pts[pts.len - 1][0], pts[pts.len - 1][1]); + return p; +} + +// ---------------------------------------------------------------- the linear rows + +/// 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; + // For a strip: a tick at the row's top. + if (ui.strokes) return ui.collectMark(u, 0, y, .tick, 1); + 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); + } + } +}; + // ---------------------------------------------------------------- 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. +/// is) and the stop the step came from (`was`, the same function; another +/// layout of it while a fold opens), `p` of the way from the one to the +/// other; a step across one edge is `leave`'s (or `turn`'s) frames; where +/// the drawing is in its pane. pub const Instant = struct { g: Graph, was: Graph, p: f32, leave: ?Leave = null, - pan: f32 = 0, + /// A fold opening: how far the pills have made room (eased), and seconds since it began. + unfold: ?struct { q: f32, t: f32 } = null, + /// The drawing's top left in its pane's body: centred, or scrolled where it is taller. + at: [2]f32, 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 }; +/// A step across one edge: the edge drawn gold (`draw`, 0 to 1), the mark +/// along it (`travel`), seconds since it landed; walked, or at a run (the +/// edge flashing gold under the mark and cooling in 8 f). +pub const Leave = struct { edge: u32, draw: f32, travel: f32, landed: f32, walk: bool = true }; -/// 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 { +/// The graph of the function the pc is in, in `form`, in a pane's body `room` (width, height), now. +pub fn instant(arena: std.mem.Allocator, now: cursors.Now, form: Form, room: [2]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; + const ref = now.way[0]; + const g = layout(arena, rec, at[1], pc[1], form, room, ref) 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; + if (at[0] != at[1] and pc[0] -% g.start < g.len) was = layout(arena, rec, at[0], pc[0], form, room, ref) 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); + if (was.start != g.start) was = g; + var out: Instant = .{ .g = g, .was = was, .p = now.advancing(), .now = now, .at = .{ 0, 0 } }; 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| { + // One edge crossed: walked, `leave`'s frames; at a run the mark along it with the advance. + if (!now.resting() and now.plan.gait != .sprint and crossed(was, g) == 1) if (g.trail[0]) |e| { const l = time.leave; const plan = now.plan; + const walk = now.walking(); + const travel = cursors.glide(clamp01((now.time - plan.advance) / @max(plan.travel, 1.0 / 60.0))); 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))), + .draw = if (walk) cursors.standard(clamp01((now.time - (plan.advance - l.edge)) / l.edge)) else travel, + .travel = travel, .landed = now.time - plan.advance - plan.travel, + .walk = walk, }; - q = out.leave.?.travel; + q = travel; }; - out.pan = std.math.lerp(pan(was, room, m), pan(g, room, m), cursors.glide(q)); + // A fold opening: the pills make room from the mark setting off (with the advance where no mark goes). + if (was.open != g.open) { + const since = if (now.resting()) std.math.inf(f32) else if (out.leave != null) now.time - now.plan.advance else out.p * time.unfold.room; + out.unfold = .{ .q = cursors.glide(clamp01(since / time.unfold.room)), .t = since }; + } + // Across, the entry where the scene's first layout (every fold shut) has it: a fold opening moves nothing sideways. + const first = if (g.open == 0) g else layout(arena, rec, ref, pc[1], form, room, ref) orelse g; + const a = place0(was, first, room); + const b = place0(g, first, room); + const k = if (out.unfold) |u| u.q else cursors.glide(q); + out.at = .{ std.math.lerp(a[0], b[0], k), std.math.lerp(a[1], b[1], k) }; return out; } +/// Where a drawing sits in a pane's body: centred, across as its first +/// layout (`first`, every fold shut) is, as far as it fits; down, scrolled +/// where it is taller (`pan`). +fn place0(g: Graph, first: Graph, room: [2]f32) [2]f32 { + const x = (room[0] - first.w) / 2 + first.nodes[0].x - g.nodes[0].x; + return .{ if (g.w <= room[0]) std.math.clamp(x, 0, room[0] - g.w) else std.math.clamp(x, room[0] - g.w, 0), if (g.h <= room[1]) (room[1] - g.h) / 2 else -pan(g, room[1]) }; +} + +/// How many edges the run took between the two moments (by their counts). +fn crossed(was: Graph, g: Graph) u32 { + var a: u32 = 0; + var b: u32 = 0; + for (was.edges) |e| a += e.count; + for (g.edges) |e| b += e.count; + return b -| a; +} + 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. +/// How long the mark takes along edge `e`: 12 f and 2 f a 100 units, 42 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 +/// `leave` (and `turn`, round a ring's foot into its header): 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. +/// and 2 f a 100 units (42 f at most; into a fold that opens, no sooner +/// than the room is made); landing, the advance; the target's count struck +/// 6 f after (a ring's turns as it lands); the oldest trail edge cooled +/// (18 f); a rest to 42 f after the landing. Measured on the `blocks` +/// lens's pane. 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); + var arena: std.heap.ArenaAllocator = .init(std.heap.page_allocator); + defer arena.deinit(); const rec = c.rec; + const band = theme.layout.split.blocks.band; + const room: [2]f32 = .{ band.w - 2 * theme.stroke.rule, band.h - theme.metric.context.tag - theme.stroke.rule }; 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| { + if (layout(arena.allocator(), rec, to, rec.register(to, "rip"), .rings, room, c.first)) |g| { + if (g.nodeOf(rec.register(from, "rip"))) |a| if (g.here) |b| if (g.edgeOf(a, b)) |e| { mark = markTime(&g.edges[e]); }; + if (layout(arena.allocator(), rec, from, rec.register(from, "rip"), .rings, room, c.first)) |was| if (was.start == g.start and was.open != g.open) { + mark = @max(mark, time.unfold.room); + }; } 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); @@ -1010,13 +1716,32 @@ pub fn toEnd(c: cursors.Cursor, s: *anim.Frame) void { 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 } { +// ---------------------------------------------------------------- drawing + +/// An edge's look in `g`: not taken yet `rule`, taken `dim`, the last +/// three taken the trail's golds (the newest 3 wide). By line, all `rule`. +const Look = struct { ink: ui.Color, w: f32 }; + +fn edgeLook(g: Graph, e: u32) Look { 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 }; + if (!g.exact) return .{ .ink = ui.rgb(theme.color.rule), .w = theme.stroke.rule }; + for (g.trail, 0..) |maybe, k| if (maybe) |te| if (te == e) return .{ .ink = ui.rgb(tr[k]), .w = if (k == 0) 3 else theme.stroke.rule }; + return .{ .ink = ui.rgb(if (g.edges[e].count > 0) t.dim else theme.color.rule), .w = theme.stroke.rule }; +} + +/// The same edge (by its blocks) in the layout the step came from, if it is there. +fn wasEdge(v: Instant, e: u32) ?u32 { + const g = v.g; + if (v.was.open == g.open) return e; + const a = v.was.nodeOf(g.nodes[g.edges[e].from].start) orelse return null; + const b = v.was.nodeOf(g.nodes[g.edges[e].to].start) orelse return null; + return v.was.edgeOf(a, b); +} + +/// The node holding node `k`'s block in the layout the step came from. +fn wasNode(v: Instant, k: u32) ?Node { + const i = v.was.nodeOf(v.g.nodes[k].start) orelse return null; + return v.was.nodes[i]; } /// A count written as the mark lands: armed 12 f before `s`, struck at @@ -1034,10 +1759,11 @@ fn landing(now: cursors.Now, s: f32) ui.Heat { } /// 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 { +/// then the new; a strike's paper under it, on its `ground` (a pill's, or +/// the page). Crossfading (`p`) where it changes unstruck. One that +/// appears (from none) fades in, `appear` of it, until its strike. +/// `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, appear: f32) 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; @@ -1050,10 +1776,12 @@ fn number(u: ui.Ui, face: sk.Face, size: f32, x: f32, base_y: f32, right: bool, 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. + // Nothing under it but while it is armed or its paper shows: its ground is the pill's own, or the page. 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); + if (h.level < 1 or h.in < 0.5) { + if (was == 0) return one(u.faded(appear), face, size, x, base_y, right, is, ink, prefix); + 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; @@ -1063,331 +1791,259 @@ fn number(u: ui.Ui, face: sk.Face, size: f32, x: f32, base_y: f32, right: bool, 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 { +/// A pill: `r` with ends half circles, filled `fill` (null: none), framed +/// inside in `frame` `w` wide, or dashed 12 on 8. +fn pill(u: ui.Ui, r: ui.Rect, fill: ?ui.Color, frame: ui.Color, w: f32, dashed: bool) void { + var pts: [2 * 13 + 1]ui.Vec = undefined; + const outline = struct { + fn of(out: []ui.Vec, rr: ui.Rect, inset: f32) void { + const rad = rr.h / 2 - inset; + const cy = rr.y + rr.h / 2; + for (0..13) |k| { + const a = pi / 2 + pi * @as(f32, @floatFromInt(k)) / 12; + out[k] = .{ rr.x + rr.h / 2 + rad * @cos(a), cy + rad * @sin(a) }; + out[13 + k] = .{ rr.x + rr.w - rr.h / 2 + rad * @cos(a + pi), cy + rad * @sin(a + pi) }; + } + out[26] = out[0]; + } + }.of; + if (fill) |c| { + outline(&pts, r, 0); + sk.draw.polygon(u.f, pts[0..26], u.at.pen(.{ .fill = c })); + } + outline(&pts, r, w / 2); + const pen = u.at.pen(.{ .stroke = frame, .width = w, .cap = .butt, .join = .round }); + if (dashed) sk.draw.dashed(u.f, &pts, theme.stroke.dash, pen) else sk.draw.polygon(u.f, pts[0..26], pen); +} + +/// The edges, in `u` (the drawing's origin): each in its look, mixed from +/// the one before as the step lands (the trail drawn last, the newest +/// over all); the one a leave takes drawn gold head first over its old +/// look, cooling to the trail's newest after the landing. While a fold +/// opens, the old layout's edges go as the new one's come. +/// shortcut: during an unfold the edges crossfade between the two layouts rather than following the pills as they make room; no recording has pills beyond a fold that move far. +fn drawEdges(u: ui.Ui, v: Instant) 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 }); + const head = gm.head; + const q = recolour(v); + const sets = [2]Graph{ v.was, g }; + var buf: [most]ui.Vec = undefined; + for (sets, 0..) |set, si| { + const shows: f32 = if (v.unfold) |uf| (if (si == 0) 1 - uf.q else uf.q) else if (si == 0) 0 else 1; + if (shows <= 0) continue; + const uu = u.faded(shows); + // Not in the trail first, then the trail from its oldest. + for (0..4) |pass| for (set.edges, 0..) |e, k| { + const rank: usize = for (set.trail, 0..) |maybe, tk| { + if (maybe != null and maybe.? == k) break 3 - tk; + } else 0; + if (rank != pass) continue; + var look = edgeLook(set, @intCast(k)); + if (v.unfold == null) { + const a = edgeLook(v.was, @intCast(k)); + look = .{ .ink = ui.mix(a.ink, look.ink, q), .w = std.math.lerp(a.w, look.w, q) }; + } + uu.route(vecs(&buf, e.path()), look.ink, .{ .width = look.w, .head = head, .radius = 0 }); }; - // 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, ""); - } + } + if (v.leave) |l| { + u.faded(1 - q).route(vecs(&buf, g.edges[l.edge].path()), theme.mark(.current).solid, .{ .width = 3, .head = head, .radius = 0, .progress = l.draw }); } } -/// 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 far the edges have taken their new looks: walked, over 18 f from the +/// landing; at a run, from the mark setting off to the step's end (the +/// flash cooled within it); else with the advance. +fn recolour(v: Instant) f32 { + const l = v.leave orelse return v.p; + if (l.walk) return clamp01(l.landed / time.leave.trail); + const plan = v.now.plan; + return clamp01((v.now.time - plan.advance) / @max(plan.total - plan.advance, 1.0 / 60.0)); +} + +/// A way's points as the drawing takes them. +fn vecs(buf: *[most]ui.Vec, pts: []const [2]f32) []const ui.Vec { + for (pts, buf[0..pts.len]) |p, *v| v.* = .{ p[0], p[1] }; + return buf[0..pts.len]; +} + +/// Each ring's turns, 30 under its centre, `5 turns` (the number mono 20, +/// the word Go 18 dim), nothing before the first; struck as a turn lands. +fn drawTurns(u: ui.Ui, v: Instant) void { + const g = v.g; + const size = theme.size.mono.context; + const micro = theme.size.sans.micro; + for (g.rings) |ring| { + var n: u32 = 0; + var was: u32 = 0; + var heat: ?ui.Heat = null; + for (g.edges, 0..) |e, k| if (e.back and e.to == ring.header) { + n += e.count; + if (wasEdge(v, @intCast(k))) |w| was += v.was.edges[w].count; + if (v.leave) |l| if (l.edge == k and l.walk) { + heat = landing(v.now, v.now.plan.advance + v.now.plan.travel); + }; + }; + if (n == 0 and was == 0) continue; + // The first: nothing until it is struck (or, unstruck, as the advance brings it). + const in = if (heat) |h| (if (h.level >= 1) clamp01(h.in * 2) else 0) else v.p; + const shown = if (in >= 1) n else was; + const word = if (@max(shown, 1) == 1) " turn" else " turns"; + const digits = u.print("{d}", .{@max(n, was)}); + const w = u.width(.mono, size, digits) + u.width(.sans, micro, word); + const x = ring.c[0] - w / 2; + const by = ring.c[1] + gm.turns_down + 7; + number(u, .mono, size, x, by, false, was, n, t.primary, heat, null, v.p, "", 0); + u.faded(if (was == 0) in else 1).text(.sans, micro, x + u.width(.mono, size, digits), by, word, t.dim); + } } /// 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 was: f32 = if (v.was.here) |h| (if (v.g.nodeOf(v.was.nodes[h].start) == k) 1 else 0) 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); + if (is > was) return if (l.walk) clamp01(l.landed / time.leave.count) else l.travel; 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`). +/// The pills: not reached yet on the page, framed `rule`, the offset faint, +/// no count; reached on `raised`, the offset primary, the visits; the pc's +/// framed gold 3; a fold dashed. A first entry fills as the mark lands +/// (`reach`); a fold opening fades into its blocks, quiet, in their places, +/// as the pills beyond make room (`unfold`). +fn drawPills(u: ui.Ui, v: Instant) void { + const g = v.g; + const size = theme.size.mono.context; + const adv = ui.advance(size); + const rec = v.now.rec; + const now = v.now; + for (g.nodes, 0..) |n, k| { + const w = wasNode(v, @intCast(k)); + const opening = v.unfold != null and w != null and w.?.folded > 0 and n.folded == 0; + var x = n.x; + var y = n.y; + var shows: f32 = 1; + if (v.unfold) |uf| { + if (opening) { + // Its place in the fold's blocks, in address order. + var rank: f32 = 0; + for (g.nodes, 0..) |o, j| if (o.folded == 0 and o.start < n.start) if (wasNode(v, @intCast(j))) |ow| if (ow.folded > 0 and ow.start == w.?.start) { + rank += 1; + }; + shows = clamp01((uf.t - rank * time.unfold.apart) / time.unfold.fade); + } else if (w) |ow| { + x = std.math.lerp(ow.x, n.x, uf.q); + y = std.math.lerp(ow.y, n.y, uf.q); + } + } + const o = u.faded(shows); + const r: ui.Rect = .{ .x = x, .y = y, .w = n.w, .h = n.h }; + const base_y = rows.baseline(y); + if (n.folded > 0) { + pill(o, r, ui.rgb(theme.color.page), ui.rgb(theme.color.rule), theme.stroke.rule, true); + o.text(.mono, size, x + gm.pill_in, base_y, o.print("+{x} \u{2026}", .{n.start - g.start}), t.faint); + const words = o.print("\u{00b7} {d}", .{n.folded}); + o.text(.mono, size, x + n.w - gm.pill_in - o.width(.mono, size, words), base_y, words, t.faint); + continue; + } + const was_visits: u32 = if (w) |ow| (if (ow.folded > 0) 0 else ow.visits) else 0; + const gold = golden(v, @intCast(k)); + const filled = if (v.leave) |l| (if (l.walk) clamp01(l.landed / time.reach.fill) else l.travel) 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), filled); + pill(o, r, ui.mix(theme.color.page, theme.color.raised, seen), ui.mix(theme.color.rule, theme.mark(.current).solid, gold), std.math.lerp(theme.stroke.rule, gm.gold, gold), false); + // The pc's pill's gold frame pulses with the fire on its last row. + const out = if (gold > 0) now.fire() else 0; + if (out > 0) pill(o, .{ .x = x - out, .y = y - out, .w = n.w + 2 * out, .h = n.h + 2 * out }, null, ui.rgb(theme.mark(.current).solid), gm.gold * gold + out, false); + const off = o.print("+{x}", .{n.start - g.start}); + o.text(.mono, size, x + gm.pill_in, base_y, off, ui.mix(t.faint, t.primary, seen)); + var cx = x + gm.pill_in + o.width(.mono, size, off); + for (n.calls) |c| if (c != 0) { + const name = callee(rec, c) orelse ""; + o.text(.mono, size, cx + adv, base_y, name, t.faint); + cx += adv + o.width(.mono, size, name); + }; + if (n.more_calls) o.text(.mono, size, cx + adv, base_y, "\u{2026}", t.faint); + const strike: ?ui.Heat = if (v.leave) |l| (if (l.walk and g.edges[l.edge].to == k) landing(now, now.plan.advance + now.plan.travel + time.leave.count) else null) else null; + const appear = if (v.leave) |l| clamp01(l.landed / time.reach.count) else 1; + number(o, .mono, size, x + n.w - gm.pill_in, 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}", appear); + } + // The folds that open: their dashed pills going as their blocks come. + if (v.unfold) |uf| for (v.was.nodes) |wn| if (wn.folded > 0) if (g.nodeOf(wn.start)) |k| if (g.nodes[k].folded == 0) { + const o = u.faded(1 - clamp01(uf.t / time.unfold.fade)); + pill(o, .{ .x = wn.x, .y = wn.y, .w = wn.w, .h = wn.h }, null, ui.rgb(theme.color.rule), theme.stroke.rule, true); + o.text(.mono, size, wn.x + gm.pill_in, rows.baseline(wn.y), o.print("+{x} \u{2026}", .{wn.start - g.start}), t.faint); + }; +} + +/// The mark on its way along the edge a leave takes: a gold plaque 22 with +/// an ink point 12 by 10 the way it goes. +fn drawMark(u: ui.Ui, v: Instant) void { + const l = v.leave orelse return; + if (l.travel <= 0 or l.travel >= 1) return; + const e = &v.g.edges[l.edge]; + const side = gm.mark; + // Its point the way it goes over its own length: a small jog in the way does not turn it. + const d = l.travel * e.length(); + const at, const tangent = e.at(d); + const ahead, _ = e.at(@min(d + side / 2, e.length())); + const behind, _ = e.at(@max(d - side / 2, 0)); + const span = dist(ahead, behind); + const dir: [2]f32 = if (span > 1) .{ (ahead[0] - behind[0]) / span, (ahead[1] - behind[1]) / span } else tangent; + const gold = theme.mark(.current); + u.fill(.{ .x = at[0] - side / 2, .y = at[1] - side / 2, .w = side, .h = side }, gold.solid); + const h = gm.mark_point[0] / 2; + 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] * gm.mark_point[1] / 2, dir[0] * gm.mark_point[1] / 2 }; + sk.draw.polygon(u.f, &.{ tip, back + across, back - across }, u.at.pen(.{ .fill = ui.rgb(gold.on_solid) })); +} + +/// The `blocks` lens (design/README.md, `graph`), and the map's drawing at +/// its size: over the program column the function's graph in the form +/// the scene names (`rings`; `layers` where it has no loop), centred in +/// its pane, a block a pill. Its rows are the disassembly under the source. pub const Blocks = struct { cursor: cursors.Cursor, stage: *const Stage, focus: bool = false, + form: Form = .rings, pub fn draw(b: *const Blocks, f: *sk.Frame, placed: anim.Placed) void { + // Nothing of it on a strip: the band has none. + if (ui.strokes) return; const box = b.stage.box(placed, .band); const m = theme.metric.context; - if (box.h < m.tag + 24) return; + if (box.h < m.tag + gm.pill) 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 { + const rule = theme.stroke.rule; + const room: [2]f32 = .{ box.w - 2 * rule, box.h - m.tag - rule }; + const v = instant(f.scratch, now, b.form, 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); + const full = b.cursor.rec.strings.get(v.g.start) orelse ""; + const name = ui.symbol(u, full); + const short = name[0 .. std.mem.lastIndexOfScalar(u8, name, '+') orelse name.len]; + const title = if (std.mem.indexOfScalar(u8, full, '!')) |bang| u.print("the blocks of {s} \u{00b7} {s}", .{ short, full[0..bang] }) else u.print("the blocks of {s}", .{short}); + _ = u.panel(box.w, box.h, title, .{ .focus = b.focus, .note = if (v.g.rings.len > 0) "its blocks \u{00b7} the visits so far \u{00b7} the path \u{00b7} the loops' turns" else "its blocks \u{00b7} the visits so far \u{00b7} the path" }); + u.clip(.{ .x = rule, .y = m.tag, .w = room[0], .h = room[1] }); + const o = u.moved(rule + v.at[0], m.tag + v.at[1]); + drawEdges(o, v); + drawTurns(o, v); + drawPills(o, v); + drawMark(o, v); 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} not 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, - // said of the run so far (a graph says what has happened by the moment shown, never what will not). - 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 not reached", .{n.folded}) else "not 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" { +test "a loop's back edge climbs its lane in layers, the fall-through straight down, a taken target right of its branch" { // 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{ @@ -1401,39 +2057,49 @@ test "a loop's back edge climbs, the hot path is straight down, a never-taken ta .{ .start = 0xaa, .len = 0x04, .end = .ret }, // B7 }; for (&nodes) |*nd| { - nd.w = 300; - nd.h = 52; + nd.w = 116; + nd.h = 24; } 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 }, + .{ .from = 0, .to = 6, .kind = .jump }, + .{ .from = 1, .to = 3, .kind = .jump }, + .{ .from = 2, .to = 3, .kind = .fall }, + .{ .from = 3, .to = 5, .kind = .taken }, + .{ .from = 3, .to = 4, .kind = .fall }, + .{ .from = 4, .to = 2, .kind = .taken }, + .{ .from = 4, .to = 5, .kind = .fall }, + .{ .from = 5, .to = 6, .kind = .fall }, + .{ .from = 6, .to = 1, .kind = .taken }, + .{ .from = 6, .to = 7, .kind = .fall }, }; - var g: Graph = .{ .start = 0, .len = 0xae, .nodes = &nodes, .edges = &edges, .here = null, .text = true, .exact = true }; - place(&g, metricOf(.map)); + var g: Graph = .{ .start = 0, .len = 0xae, .nodes = &nodes, .edges = &edges, .spans = &.{}, .here = null, .text = true, .exact = true }; + var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); + defer arena.deinit(); + try place(arena.allocator(), &g, .layers); // 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. + // The outer loop's lane outermost; a back edge climbs into its header's end 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]); + try std.testing.expect(turn[turn.len - 1][0] <= nodes[6].x + 0.5 and @abs(turn[turn.len - 1][1] - (nodes[6].y + 12)) < 0.01); + // A taken target right of its branch; a fall-through under it. + try std.testing.expect(nodes[2].col == nodes[4].col + 1 and nodes[4].col == nodes[3].col); // 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]); + for (edges) |e| if (!e.back) try std.testing.expectApproxEqAbs(nodes[e.to].y, e.points[e.n - 1][1], 0.01); +} + +test "a way's corners are quarter circles, and its length is along them" { + const p = rounded(&.{ .{ 0, 0 }, .{ 0, 100 }, .{ 100, 100 } }, 16); + var e: Edge = .{ .from = 0, .to = 0, .kind = .fall }; + e.set(&p); + // Two straights of 84 and a quarter of a circle of 16. + try std.testing.expectApproxEqAbs(2 * 84 + pi * 8, e.length(), 0.2); + const mid, const dir = e.at(e.length() / 2); + try std.testing.expect(mid[0] > 0 and mid[1] > 84 and dir[0] > 0 and dir[1] > 0); + // Every point on the bend is 16 from its centre. + for (e.path()) |q| if (q[1] > 84 and q[0] < 16) try std.testing.expectApproxEqAbs(@as(f32, 16), dist(q, .{ 16, 84 }), 0.01); } |
