1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
|
//! Calls as an idea, a lens on the stack: the tree of every call of one
//! function, which grows as the program runs (the frames themselves are
//! `context.Backtrace` and the stack's words). It reads the recording's
//! index of calls and returns, with what each was given and gave back,
//! and is the last level a step reaches: a node appears after the
//! registers that carried its argument have struck.
const std = @import("std");
const sk = @import("sketch");
const anim = @import("anim");
const ui = @import("ui.zig");
const cursors = @import("cursor.zig");
const Cursor = cursors.Cursor;
const Recording = @import("Recording.zig");
const context = @import("context.zig");
const Stage = @import("stage.zig").Stage;
const ties = @import("ties.zig");
const rows = @import("rows.zig");
const theme = ui.theme;
const time = theme.time;
const Rect = ui.Rect;
const t = theme.color.text;
pub const Tree = struct {
cursor: Cursor,
stage: *const Stage,
/// The function whose calls are the tree.
function: []const u8,
focus: bool = false,
pub fn draw(k: *const Tree, f: *sk.Frame, at: anim.Placed) void {
k.backtrace(f, at);
const box = k.stage.box(at, .band);
if (box.h < theme.metric.context.tag + 24) return;
const u = context.at(f, at, box).faded(at.value(k.stage.drawing));
// A relayout moves the band: what is drawn in it stays inside it.
u.clip(.{ .x = 0, .y = 0, .w = box.w, .h = box.h });
defer u.unclip();
const now = k.cursor.now(at);
const rec = k.cursor.rec;
const m = metric;
const body = u.panel(box.w, box.h, u.print("calls of {s}", .{k.function}), .{ .focus = k.focus, .note = "each call a node \u{00b7} its result on its shoulder" });
const nodes = layout(f.scratch, rec, k.function) catch return;
if (nodes.len == 0) return;
var leaves: f32 = 0;
for (nodes) |n| leaves = @max(leaves, n.x + 1);
// The caller's box left of the root on its level; the leaves spread over the rest.
const caller_room = m.caller[0] + 48;
const left = theme.metric.panel.pad_x + caller_room + m.radius;
// The last leaf's centre 69 in from the drawing's right edge: room for its badge on its shoulder.
const pitch = (box.w - 69 - left) / @max(leaves - 1, 1);
const top = body.y + m.root;
const since = now.since(.idea, 0);
const returned = now.walking() and rec.depths[now.stops[0]] < rec.depths[now.stops[1]];
const moment = if (now.plan.gait == .sprint or since >= (if (returned) @as(f32, time.badge_after) else 0)) now.stops[0] else now.stops[1];
const edge = cursors.standard(now.moving(.idea, time.quick, time.quick));
const appears = now.moving(.idea, 0, time.snap);
const at_of = struct {
fn c(lf: f32, p: f32, tp: f32, n: Node) ui.Vec {
return .{ lf + n.x * p, tp + @as(f32, @floatFromInt(n.level)) * metric.level };
}
}.c;
// The caller: gold until the first call, then waiting, ringed; an edge into the root.
if (nodes[0].call.parent) |p| {
const caller = rec.calls[p];
const root_c = at_of(left, pitch, top, nodes[0]);
const r: Rect = .{ .x = theme.metric.panel.pad_x, .y = root_c[1] - m.caller[1] / 2, .w = m.caller[0], .h = m.caller[1] };
const called = nodes[0].call.enter <= moment;
if (nodes[0].call.enter <= now.stops[0]) {
const to = ui.Vec{ root_c[0] - m.radius, root_c[1] };
const from = ui.Vec{ r.x + r.w, root_c[1] };
const live = nodes[0].call.active(moment) or nodes[0].call.enter > moment;
u.line(from, if (nodes[0].call.enter > now.stops[1]) sk.math.mix(from, to, edge) else to, if (live) ui.rgb(t.primary) else ui.rgb(theme.color.rule), theme.stroke.line);
}
if (!called) {
u.fill(r, theme.mark(.current).solid);
u.label(.mono_bold, theme.size.mono.context, r, .center, rec.name(caller.function), theme.mark(.current).on_solid);
} else {
u.fill(r, theme.color.page);
u.frame(r, t.primary, theme.stroke.line);
u.label(.mono, theme.size.mono.context, r, .center, rec.name(caller.function), t.primary);
}
}
// Edges under nodes: the waiting path in primary.
for (nodes) |n| {
const parent = n.parent orelse continue;
if (n.call.enter > now.stops[0]) continue;
const from = at_of(left, pitch, top, nodes[parent]);
var to = at_of(left, pitch, top, n);
if (n.call.enter > now.stops[1]) to = sk.math.mix(from, to, edge);
const live = n.call.active(moment);
u.line(from, to, if (live or n.call.enter > moment) ui.rgb(t.primary) else ui.rgb(theme.color.rule), theme.stroke.line);
}
const deepest = deepestActive(nodes, moment);
for (nodes, 0..) |n, i| {
const c = at_of(left, pitch, top, n);
// Where a projection from its frame's way back (the word its
// call pushed, at the call's stack pointer) lands: under it,
// there before the node, which comes when it arrives.
if (n.call.enter <= now.stops[0]) ties.anchor(u, .{ .node_address = n.call.sp }, .{ .x = c[0] - m.radius, .y = c[1] - m.radius, .w = 2 * m.radius, .h = 2 * m.radius });
if (n.call.enter > moment) continue;
const v = if (n.call.enter > now.stops[1]) u.faded(appears) else u;
if (deepest == i) {
v.disc(c, m.radius, ui.rgb(theme.mark(.current).solid), null, 0);
} else if (n.call.active(moment)) {
v.disc(c, m.radius - theme.stroke.line / 2, ui.rgb(theme.color.page), ui.rgb(t.primary), theme.stroke.line);
} else v.disc(c, m.radius, ui.rgb(theme.color.raised), null, 0);
}
// Then the words, so shapes and text each go in one run.
const size = theme.size.mono.small;
for (nodes, 0..) |n, i| {
if (n.call.enter > moment) continue;
const c = at_of(left, pitch, top, n);
const active = n.call.active(moment);
const words = if (n.call.arg) |arg| u.print("{d}", .{@as(i64, @bitCast(arg))}) else "?";
const cell: Rect = .{ .x = c[0] - m.radius, .y = c[1] - m.radius, .w = 2 * m.radius, .h = 2 * m.radius };
const v = if (n.call.enter > now.stops[1]) u.faded(appears) else u;
if (deepest == i) {
v.label(.mono_bold, size, cell, .center, words, theme.mark(.current).on_solid);
} else v.label(.mono, size, cell, .center, words, t.primary);
if (active) continue;
// Done: what it returned, on its shoulder; struck as it lands.
const badge: Rect = .{ .x = c[0] + m.badge_at[0], .y = c[1] - m.badge_at[1], .w = m.badge, .h = m.badge };
const heat: ui.Heat = if (n.call.exit.? > now.stops[1]) now.heat(0, null, since - time.badge_after) else .none;
const ink = u.cellWritten(badge, heat, theme.color.page);
// Framed, as every result is, but while the strike's paper is on it.
u.faded(if (heat.level < 1) 1 else 1 - heat.solid * heat.in).frame(badge, t.faint, theme.stroke.rule);
u.label(ink.face, size, badge, .center, u.print("{d}", .{@as(i64, @bitCast(n.call.result))}), if (heat.level >= 1) ink.ink else ui.rgb(t.primary));
}
}
/// Its view: the backtrace, the waiting path read as rows, newest at
/// the bottom, with each call's arguments (`n=4`) and where it is.
fn backtrace(k: *const Tree, f: *sk.Frame, at: anim.Placed) void {
const box = k.stage.box(at, .view);
const cm = theme.metric.context;
if (box.h < cm.tag + cm.row) return;
const u = context.at(f, at, box).faded(at.value(k.stage.view));
u.clip(.{ .x = 0, .y = 0, .w = box.w, .h = box.h });
defer u.unclip();
const now = k.cursor.now(at);
const rec = k.cursor.rec;
// A frame is its words on the stack: the view changes with memory.
const moment = now.stop(.memory);
var buf: [24]context.Frame = undefined;
const chain = context.frames(rec, moment, &buf);
const room = theme.layout.rowsIn(box.h);
const body = u.panel(box.w, box.h, "backtrace", .{ .note = u.print("the calls waiting \u{00b7} {s}", .{context.newestAtBottom(u, chain.len, room)}) });
const open = rec.stack(f.scratch, moment);
// Newest at the bottom, as the tree grows down beside it; the oldest go from the top.
const shown = @min(chain.len, room);
for (chain[0..shown], 0..) |frame, i| {
const y = body.y + cm.pad + @as(f32, @floatFromInt(shown - 1 - i)) * cm.row;
const name = ui.symbol(u, rec.strings.get(frame.pc) orelse u.print("{x}", .{frame.pc}));
// The call this frame is, by its place on the chain: its arguments.
rows.callRow(u, y, box.w, i, name, context.callArguments(u, rec, open, i, frame.pc), context.frameWhere(u, rec, now.marked(), i, frame.pc), i == 0);
}
context.veiled(u, box, now.sprint_veil);
}
};
/// A call's arguments as its backtrace row and its span say them: its
/// parameter's name and value, `n=4`; "" for one that takes nothing.
pub fn arguments(u: ui.Ui, rec: *const Recording, c: Recording.Call) []const u8 {
const f = for (rec.functions) |fun| {
if (std.mem.eql(u8, fun.name, rec.name(c.function))) break fun;
} else return "";
if (!f.takes) return "";
const arg = c.arg orelse return "";
const name = if (c.parameter_name) |id| rec.name(id) else f.param;
// A pointer is an address, hex; a number is its decimal.
if (rows.regionOf(rec.moment(c.enter), arg) != .none) return u.print("{s}={x}", .{ name, arg });
return u.print("{s}={d}", .{ name, @as(i64, @bitCast(arg)) });
}
/// The tree's measures (design/README.md, `calls`): full size.
const metric = theme.metric.calls;
pub const Node = struct {
call: Recording.Call,
parent: ?usize,
level: u32,
/// In leaf slots: a leaf has a whole number, a parent sits over the
/// middle of its children.
x: f32,
};
fn deepestActive(nodes: []const Node, moment: u64) ?usize {
var best: ?usize = null;
for (nodes, 0..) |n, i| {
if (n.call.active(moment) and (best == null or n.level >= nodes[best.?].level)) best = i;
}
return best;
}
/// Every call of `function`, placed as a tidy tree of the whole run, so a
/// node is where it will always be from the moment it appears.
pub fn layout(arena: std.mem.Allocator, rec: *const Recording, function: []const u8) ![]Node {
var nodes: std.ArrayList(Node) = .empty;
// Calls come in the order they were made: a parent before its children.
var index: std.AutoHashMapUnmanaged(u32, usize) = .empty;
for (rec.calls, 0..) |call, i| {
if (!std.mem.eql(u8, rec.name(call.function), function)) continue;
const parent: ?usize = if (call.parent) |p| index.get(p) else null;
try index.put(arena, @intCast(i), nodes.items.len);
try nodes.append(arena, .{ .call = call, .parent = parent, .level = if (parent) |p| nodes.items[p].level + 1 else 0, .x = -1 });
}
// Leaves left to right in call order; then each parent over its children,
// deepest first (children come after their parent, so backwards).
const lo = try arena.alloc(f32, nodes.items.len);
const hi = try arena.alloc(f32, nodes.items.len);
@memset(lo, std.math.inf(f32));
@memset(hi, -std.math.inf(f32));
var next_leaf: f32 = 0;
for (nodes.items, 0..) |*n, i| {
const leaf = for (nodes.items[i + 1 ..]) |other| {
if (other.parent == i) break false;
} else true;
if (!leaf) continue;
n.x = next_leaf;
next_leaf += 1;
}
var i = nodes.items.len;
while (i > 0) {
i -= 1;
const n = &nodes.items[i];
if (n.x < 0) n.x = (lo[i] + hi[i]) / 2;
if (n.parent) |p| {
lo[p] = @min(lo[p], n.x);
hi[p] = @max(hi[p], n.x);
}
}
return nodes.items;
}
|