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