//! `graph` (design/README.md, "graph"): the disassembly's other form, a //! 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 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"); const zt = @import("ztrace"); const Recording = @import("Recording.zig"); const ui = @import("ui.zig"); const rows = @import("rows.zig"); const cursors = @import("cursor.zig"); const context = @import("context.zig"); const disasm = @import("disasm.zig"); const Stage = @import("stage.zig").Stage; const theme = ui.theme; const time = theme.time; const 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 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, /// 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. visits: u32 = 0, layer: u32 = 0, col: u32 = 0, /// Its pill: its top left and its size. x: f32 = 0, y: f32 = 0, w: f32 = 0, h: f32 = 0, pub fn contains(n: Node, addr: u64) bool { return addr -% n.start < n.len; } 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. count: u32 = 0, /// 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, 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 { return e.points[0..e.n]; } /// Its length along its way. pub fn length(e: *const Edge) f32 { var total: f32 = 0; for (e.path()[0 .. e.n -| 1], e.path()[@min(1, e.n)..]) |a, b| total += dist(a, b); return total; } /// 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 } { const pts = e.path(); 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], 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. trail: [3]?u32 = @splat(null), /// Every instruction's text is recorded (a function of up to 2 048). text: bool, /// The recording stops at every instruction: the edges' counts and the trail are known. exact: bool, /// Its size, from its top left. w: f32 = 0, h: f32 = 0, /// `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, /// `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 { const k = spanAt(g.spans, addr) orelse return null; return g.spans[k].node; } pub fn edgeOf(g: Graph, from: u32, to: u32) ?u32 { for (g.edges, 0..) |e, i| if (e.from == from and e.to == to) return @intCast(i); return null; } /// How many blocks the folds hold. pub fn foldedBlocks(g: Graph) usize { var n: usize = 0; for (g.nodes) |node| n += node.folded; return n; } }; /// The 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, /// 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; } fn readBlocks(arena: std.mem.Allocator, rec: *const Recording, i: u64, pc: u64) !?Graph { const m = rec.moment(i); const probe = zt.telescope.blocks(m, pc, &.{}) orelse return null; const blocks = try arena.alloc(zt.telescope.Block, probe.count); const found = zt.telescope.blocks(m, pc, blocks) orelse return null; var nodes = try arena.alloc(Node, blocks.len); for (blocks, nodes) |b, *n| n.* = .{ .start = b.start, .len = b.len, .end = b.end, .out = if (b.end == .tail or b.end == .noreturn) b.to else null }; // Every instruction, where the text is recorded; a block of padding // alone (`nop`s between paths) that nothing goes to is none. var reached_by = try arena.alloc(bool, blocks.len); @memset(reached_by, false); for (blocks) |b| for ([2]?u64{ b.to, b.falls }) |to| if (to) |at| if (blockAt(nodes, at)) |k| { reached_by[k] = true; }; var keep: usize = 0; var buf: [256]u8 = undefined; for (nodes, 0..) |*n, k| { var at = n.start; var padding = found.text; 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 (padding and !reached_by[k] and k > 0) continue; nodes[keep] = n.*; keep += 1; } nodes = nodes[0..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; if (nodes[from].start != b.start) continue; if (b.to) |to| if (b.end == .jump or b.end == .branch) if (blockAt(nodes, to)) |at| try edges.append(arena, .{ .from = from, .to = at, .kind = if (b.end == .jump) .jump else .taken }); if (b.falls) |to| if (blockAt(nodes, to)) |at| try edges.append(arena, .{ .from = from, .to = at, .kind = .fall }); } g.edges = edges.items; g.exact = stepsEach(rec, g); count(rec, &g, i); 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 /// falls into it. (By line a stop is where a line begins.) fn stepsEach(rec: *const Recording, g: Graph) bool { var pairs: usize = 0; var k: u64 = 0; while (k + 1 < rec.len()) : (k += 1) { const a = rec.registers[k].rip; const b = rec.registers[k + 1].rip; if (a == b) continue; const from = blockAt(g.nodes, a) orelse continue; const to = blockAt(g.nodes, b) orelse continue; if (from == to and b != g.nodes[to].start) continue; pairs += 1; // A jump, a call of itself, a return into its caller. if (rec.insn_branches[k]) |br| if (br.to == b or br.kind == .jump and !br.taken) continue; const f = g.nodes[from]; if (f.end == .fall and b == f.start + f.len) continue; return false; } return pairs > 0; } /// The function's blocks at moment `i` and how often the run had entered /// each by then: no 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; 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 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 { 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..@min(i + 1, rec.registers.len)]) |regs| { const pc = regs.rip; if (pc -% g.start >= g.len) continue; 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 == g.spans[s].start and prev_pc != pc else prev.? != b; if (entered) { g.nodes[b].visits += 1; if (g.exact) if (prev) |p| if (g.edgeOf(p, b)) |e| { 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; prev_pc = pc; } g.trail = trail; } /// 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; while (lo < hi) { const mid = (lo + hi) / 2; if (nodes[mid].start <= addr) lo = mid + 1 else hi = mid; } if (lo == 0 or !nodes[lo - 1].contains(addr)) return null; return @intCast(lo - 1); } /// The 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; } if (lo == 0 or addr -% spans[lo - 1].start >= spans[lo - 1].len) return null; return lo - 1; } // ---------------------------------------------------------------- folds /// 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; 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 groups.items; } /// `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, 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 }; } try nodes.append(arena, kept); } var edges: std.ArrayList(Edge) = .empty; for (g.edges) |e| { const a = into[e.from]; const b = into[e.to]; 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| { if (e.kind == .fall) d.kind = .fall; continue; } var kept = e; kept.from = a; kept.to = b; try edges.append(arena, kept); } 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]; } /// 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); } 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 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; 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; 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; } /// 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 { var copy = k; const a = memo_memory.allocator(); copy.g.nodes = a.dupe(Node, k.g.nodes) catch return; copy.g.edges = a.dupe(Edge, k.g.edges) catch return; 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; } /// A kept graph with the run counted again by moment `i`, the pc at `pc`. fn recount(arena: std.mem.Allocator, rec: *const Recording, kept_g: Graph, i: u64, pc: u64) !Graph { var g = kept_g; g.nodes = try arena.dupe(Node, kept_g.nodes); g.edges = try arena.dupe(Edge, kept_g.edges); count(rec, &g, i); g.here = g.nodeOf(pc); return g; } /// 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; } } /// 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}); } /// 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; }; 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 /// walked, in address order) finds going to a block on the walk's way. fn backEdges(g: *Graph, tmp: std.mem.Allocator) !void { const n = g.nodes.len; const state = try tmp.alloc(u8, n); @memset(state, 0); // Each node's out edges, by their targets' addresses. const outs = try outEdges(g, tmp); const Frame = struct { node: u32, next: u32 }; var stack: std.ArrayList(Frame) = .empty; for (0..n) |root| { if (state[root] != 0) continue; state[root] = 1; try stack.append(tmp, .{ .node = @intCast(root), .next = 0 }); while (stack.items.len > 0) { const top = &stack.items[stack.items.len - 1]; const list = outs[top.node]; if (top.next == list.len) { state[top.node] = 2; _ = stack.pop(); continue; } const e = list[top.next]; top.next += 1; const to = g.edges[e].to; if (state[to] == 1) { g.edges[e].back = true; } else if (state[to] == 0) { state[to] = 1; try stack.append(tmp, .{ .node = to, .next = 0 }); } } } } fn outEdges(g: *const Graph, tmp: std.mem.Allocator) ![][]u32 { const outs = try tmp.alloc([]u32, g.nodes.len); const counts = try tmp.alloc(u32, g.nodes.len); @memset(counts, 0); for (g.edges) |e| counts[e.from] += 1; for (outs, counts) |*o, c| o.* = try tmp.alloc(u32, c); @memset(counts, 0); for (g.edges, 0..) |e, k| { outs[e.from][counts[e.from]] = @intCast(k); counts[e.from] += 1; } for (outs) |o| std.mem.sort(u32, o, g, struct { fn first(gr: *const Graph, a: u32, b: u32) bool { return gr.nodes[gr.edges[a].to].start < gr.nodes[gr.edges[b].to].start; } }.first); return outs; } /// Layers by the longest forward path from a block with none into it; the /// blocks that return in the last (one more where another is there). fn layers(g: *Graph, tmp: std.mem.Allocator) !void { const n = g.nodes.len; const ins = try tmp.alloc(u32, n); @memset(ins, 0); for (g.edges) |e| if (!e.back) { ins[e.to] += 1; }; var ready: std.ArrayList(u32) = .empty; for (ins, 0..) |c, k| if (c == 0) try ready.append(tmp, @intCast(k)); for (g.nodes) |*node| node.layer = 0; var head: usize = 0; while (head < ready.items.len) : (head += 1) { const a = ready.items[head]; for (g.edges) |e| if (!e.back and e.from == a) { g.nodes[e.to].layer = @max(g.nodes[e.to].layer, g.nodes[a].layer + 1); ins[e.to] -= 1; if (ins[e.to] == 0) try ready.append(tmp, e.to); }; } var last: u32 = 0; var any_ret = false; var deepest_ret: u32 = 0; 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; const at = @max(last, deepest_ret) + @intFromBool(others_last); for (g.nodes) |*node| if (node.end == .ret) { node.layer = at; }; } // ---------------------------------------------------------------- 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, fall: bool }; var wants: std.ArrayList(Want) = .empty; var used: std.ArrayList(u32) = .empty; const placed = try tmp.alloc(bool, n); @memset(placed, false); for (0..last + 1) |layer| { wants.clearRetainingCapacity(); for (g.nodes, 0..) |node, k| if (node.layer == layer) { var best: ?Edge = null; for (g.edges) |e| if (!e.back and e.to == k and placed[e.from]) { // 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 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.fall != b.fall) return a.fall; return gr.nodes[a.node].start < gr.nodes[b.node].start; } }.first); used.clearRetainingCapacity(); for (wants.items) |w| { var col = w.col; while (std.mem.indexOfScalar(u32, used.items, col) != null) col += 1; try used.append(tmp, col); g.nodes[w.node].col = col; placed[w.node] = true; } } } /// Every edge's way 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); const back_tracks = try tmp.alloc(u32, heights.len); @memset(back_tracks, 0); // The nodes by layer, then left to right: the edges of one gap take its tracks in that order. const order = try tmp.alloc(u32, n); for (order, 0..) |*o, k| o.* = @intCast(k); std.mem.sort(u32, order, g, struct { fn first(gr: *Graph, a: u32, b: u32) bool { const na = gr.nodes[a]; const nb = gr.nodes[b]; return if (na.layer != nb.layer) na.layer < nb.layer else na.x < nb.x; } }.first); for (order) |a| for (g.edges) |*e| if (e.from == a) { const src = g.nodes[e.from]; const dst = g.nodes[e.to]; const under = tops[src.layer] + heights[src.layer]; if (e.back) { const lx = 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 + 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. var srcs: usize = 0; var slot: usize = 0; for (g.edges) |o| if (!o.back and o.to == e.to) { srcs += 1; const os = g.nodes[o.from]; if (os.x < src.x or (os.x == src.x and o.from < e.from)) slot += 1; }; const tx = dst.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.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; 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; 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, /// 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: 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 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 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, 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.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 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 = 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 = travel; }; // 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, 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`, 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 (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 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(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); } /// The stop on the last instruction of the block the cursor is in (where /// a `leave` sets off): the first moment from `from` at a jump in its /// function, or before a stop in another of its blocks. pub fn blockEnd(rec: *const Recording, from: u64) u64 { var buf: [1 << 16]u8 = undefined; var fba = std.heap.FixedBufferAllocator.init(&buf); const g = light(fba.allocator(), rec, from, rec.register(from, "rip")) orelse return from; var k = from; while (k + 1 < rec.len()) : (k += 1) { const pc = rec.register(k, "rip"); const here = blockAt(g.nodes, pc) orelse continue; if (rec.insn_branches[k]) |b| if (b.kind == .jump or b.kind == .ret) return k; const next = blockAt(g.nodes, rec.register(k + 1, "rip")) orelse continue; if (next != here) return k; } return k; } /// One step from where the cursor is to the end of its block (`blockEnd`), walked: what the block does, as a cascade. pub fn toEnd(c: cursors.Cursor, s: *anim.Frame) void { const from = c.moment(s); const to = blockEnd(c.rec, from); if (to == from) return; const plan = c.reading(from, to); c.step(s, to, plan, plan.total); } // ---------------------------------------------------------------- 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 = 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 /// `s` (the fill in over 6 f, its edges out and back over 12 f), solid /// 12 f, then cooled to nothing by `end` (the step's end): no corner, the /// next step has nothing of it to keep. fn landing(now: cursors.Now, s: f32) ui.Heat { const st = time.strike; const tm = now.time; if (tm < s - st.arm) return .none; if (tm < s) return .{ .arm = clamp01((tm - (s - st.arm)) / time.stagger) }; const cool_from = s + st.pulse; const end = @max(now.plan.total, cool_from + 6.0 / 60.0); return .{ .level = 1, .solid = 1 - cursors.glide(clamp01((tm - cool_from) / (end - cool_from))), .in = clamp01((tm - s) / st.in), .out = if (tm - s < st.pulse) theme.pulse((tm - s) / st.pulse) else 0, .corner = 0 }; } /// What a count shows: the old number until a strike's fill is half in, /// then the new; a strike's paper under it, on its `ground` (a 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; const text = v.print("{s}{d}", .{ pre, n }); v.text(fc, sz, if (r) xx - v.width(fc, sz, text) else xx, by, text, c); } }.draw; if (was == is) return one(u, face, size, x, base_y, right, is, ink, prefix); if (heat) |h| { const text = u.print("{s}{d}", .{ prefix, is }); const w = u.width(face, size, text); const left = if (right) x - w else x; // Nothing under it but while it is armed or its paper shows: its ground is the 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) { 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; return one(u, if (bold) (if (face == .sans) .sans_bold else .mono_bold) else face, size, x, base_y, right, is, ui.mix(ink, t.bright, hot), prefix); } one(u.faded(1 - p), face, size, x, base_y, right, was, ink, prefix); one(u.faded(p), face, size, x, base_y, right, is, ink, prefix); } /// 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 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 }); }; } 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 }); } } /// 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) |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 if (l.walk) clamp01(l.landed / time.leave.count) else l.travel; return is; } return std.math.lerp(was, is, v.p); } /// 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 }; @import("ties.zig").anchor(u, .{ .block = n.start }, r); 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 + 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 rule = theme.stroke.rule; // Drawn larger (a column's drawing across both columns): laid out in its room at its own size, then scaled. const z = placed.value(b.stage.zoom); const room: [2]f32 = .{ (box.w - 2 * rule) / z, (box.h - m.tag - rule) / z }; const v = instant(f.scratch, now, b.form, room) orelse { _ = u.panel(box.w, box.h, "its blocks", .{ .focus = b.focus }); return; }; 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] * z, .h = room[1] * z }); var big = u.moved(rule, m.tag); big.at.xf = big.at.xf.mul(.scale(z, z)); big.at.scale *= z; const o = big.moved(v.at[0], v.at[1]); drawEdges(o, v); drawTurns(o, v); drawPills(o, v); drawMark(o, v); u.unclip(); } }; 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{ .{ .start = 0x00, .len = 0x17, .end = .jump }, // B0 jmp B6 .{ .start = 0x17, .len = 0x08, .end = .jump }, // B1 jmp B3 .{ .start = 0x1f, .len = 0x40, .end = .fall }, // B2 (swap) falls B3 .{ .start = 0x5f, .len = 0x06, .end = .branch }, // B3 jle B5, falls B4 .{ .start = 0x65, .len = 0x35, .end = .branch }, // B4 jg B2, falls B5 .{ .start = 0x9a, .len = 0x04, .end = .fall }, // B5 falls B6 .{ .start = 0x9e, .len = 0x0c, .end = .branch }, // B6 jl B1, falls B7 .{ .start = 0xaa, .len = 0x04, .end = .ret }, // B7 }; for (&nodes) |*nd| { nd.w = 116; nd.h = 24; } var edges = [_]Edge{ .{ .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, .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 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[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.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); }