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
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
|
//! Data structures as nodes and arrows: the structs the program's pointers
//! reach from a root variable (`objects.reach`: no offsets are given by
//! hand, the recording's type descriptions say which fields are pointers
//! and which is the value). A node's place is its allocation's (the order
//! it was made in), so nodes stay where they are while pointers change: a
//! list reversing is its arrows turning round. Variables that point at a
//! node are tags under it, tracked ones in their pigment, and slide from
//! node to node as they change; one that holds NULL waits at the row's
//! end. A node whose memory was freed is hollow and dashed.
//! This is the idea drawn from memory: it changes a beat after the bytes do.
//! Reads `Moment.variables`, `Moment.read`, `Moment.allocation`.
const std = @import("std");
const sk = @import("sketch");
const anim = @import("anim");
const ui = @import("ui.zig");
const cursors = @import("cursor.zig");
const Recording = @import("Recording.zig");
const objects = @import("objects.zig");
const theme = ui.theme;
const time = theme.time;
const Rect = ui.Rect;
const t = theme.color.text;
/// A node of a lens beside the context.
const size = struct {
const w = 116;
const h = 44;
const pointer_w = 44;
};
pub const Nodes = struct {
cursor: cursors.Cursor,
box: Rect,
title: []const u8 = "the list",
note: []const u8 = "what the code means",
/// The variable the structure hangs from.
root: []const u8,
/// Variables each with a pigment (by its place here): the same list a
/// memory grid of them is given.
track: []const []const u8 = &.{},
/// How nodes are placed: in a row (a list), or a row for each distance
/// from the root (a tree, a graph). Either way a node's column is its own.
arrange: enum { row, levels } = .row,
focus: bool = false,
pub fn draw(g: *const Nodes, f: *sk.Frame, at: anim.Placed) void {
const u: ui.Ui = .{ .f = f, .at = at };
const now = g.cursor.now(at);
const rec = g.cursor.rec;
const moment = now.shown(.idea);
const body = u.panel(g.box.w, g.box.h, g.title, .{ .focus = g.focus, .note = g.note });
const things = objects.reach(f.scratch, rec, moment, null);
const before = objects.reach(f.scratch, rec, now.before(), null);
if (things.len == 0) {
const root = rec.variable(f.scratch, moment, g.root);
const empty = root != null and (Recording.word(moment, root.?.addr, 8) catch null) == 0;
return u.text(.sans, theme.size.sans.note, theme.metric.panel.pad_x, body.y + 52, if (empty) u.print("empty: {s} is NULL", .{g.root}) else "nothing yet", t.faint);
}
// Columns: one for every node the program will ever make, so no
// node moves when another comes or goes. And one more, where a
// variable that holds NULL waits.
var slots: usize = 0;
for (rec.allocations) |a| slots += @intFromBool(a.size == things[0].type.record.size);
slots = @max(slots, 1);
const count: f32 = @floatFromInt(slots);
const park_w = 76;
// As a lens beside the context a node is 116 by 44; a gap for an arrow.
const node_w = @min(size.w, @floor((body.w - 2 * 20 - park_w) / count) - 28);
const gap = @min(56, (body.w - 2 * 20 - park_w - count * node_w) / count);
const left: f32 = 24;
const row_y = body.y + 36;
const park: ui.Vec = .{ left + count * (node_w + gap), row_y - 12 };
const places = f.scratch.alloc(Rect, things.len) catch return;
for (things, places, 0..) |o, *place, i| {
const level: f32 = if (g.arrange == .levels) @floatFromInt(distance(f.scratch, rec, moment, things, g.root, i)) else 0;
place.* = .{ .x = left + @as(f32, @floatFromInt(o.slot orelse i)) * (node_w + gap), .y = if (g.arrange == .levels) body.y + 40 + level * (size.h + 56) else row_y, .w = node_w, .h = size.h };
@import("ties.zig").anchor(u, .{ .node = o.addr }, place.*);
// Where it is in the heap, under it: the address the registers' chains to it show, in heap's ink.
_ = u.value(place.x, place.y + place.h + 20, o.addr, true, .{ .ink = ui.rgb(theme.color.region.heap) });
}
// Arrows under the nodes they leave.
const since = now.since(.idea, 0);
var lane: f32 = 0;
for (things, places) |o, place| for (o.type.record.fields) |field| {
if (field.type != .pointer) continue;
const from_addr = o.addr + field.offset;
const start = ui.Vec{ place.x + place.w - pointerW(place.w) / 2, place.y + size.h / 2 };
const new = if (Recording.word(now.moment(), from_addr, 8) catch null) |target| placeOf(things, places, target) else null;
const old = if (Recording.word(now.before(), from_addr, 8) catch null) |target| placeOf(things, places, target) else null;
const fresh = now.writeAge(from_addr, 8) == 0;
lane += 1;
const purple = theme.color.region.heap;
if (!fresh or !now.walking()) {
// As it stands; at a run a new arrow still grows to its node.
if (if (now.landed(.idea, 0)) new else old) |to| u.arrow(route(u, start, place, to, lane), purple, .{ .progress = if (fresh) cursors.standard(now.moving(.idea, 0, time.redirect.head)) else 1 });
continue;
}
// A pointer rewritten, a beat after its word in memory.
// Anticipation: as the square is armed the old arrow goes
// dashed and faint. Follow-through: the square strikes, the
// new arrow grows to the node it now points at, and that
// node answers with a bright frame. The old one lingers.
const armed = since >= -time.strike.arm;
if (old) |to| {
const ghost = if (armed) u.faded(1 - std.math.clamp((since - time.redirect.ghost_hold) / time.redirect.ghost_out, 0, 1)) else u;
ghost.arrow(route(u, start, place, to, 0), if (armed) ui.rgb(t.faint) else ui.rgb(purple), .{ .dashed = armed, .head = if (armed) null else theme.stroke.head, .width = if (armed) theme.stroke.line else theme.stroke.arrow });
}
if (new) |to| {
u.arrow(route(u, start, place, to, lane), purple, .{ .progress = cursors.standard(std.math.clamp((since - time.snap) / time.redirect.head, 0, 1)) });
const landed = since - time.snap - time.redirect.head;
const out = theme.metric.pointer_frame_outset;
if (landed >= 0 and landed < time.redirect.landing) u.faded(1 - landed / time.redirect.landing).frame(.{ .x = to.x - out, .y = to.y - out, .w = to.w + 2 * out, .h = to.h + 2 * out }, theme.mark(.attention).solid, theme.stroke.line);
}
};
for (things, places) |o, place| {
const new = for (before) |b| {
if (b.addr == o.addr) break false;
} else true;
// What begins fades in; it does not pop.
g.node(if (new) u.faded(now.moving(.idea, 0, time.quick)) else u, now, o, place);
}
g.tags(u, now, things, places, park);
}
fn node(g: *const Nodes, u: ui.Ui, now: cursors.Now, o: objects.Object, r: Rect) void {
_ = g;
const moment = now.shown(.idea);
const value_w = r.w - pointerW(r.w);
const value: Rect = .{ .x = r.x, .y = r.y, .w = value_w, .h = r.h };
const pointer: Rect = .{ .x = r.x + value_w, .y = r.y, .w = pointerW(r.w), .h = r.h };
if (o.freed) {
// Handed back: its bytes are still there, and nobody owns them.
u.dashedFrame(r, theme.mark(.freed).solid, theme.stroke.line);
} else {
// A node is its own colour whoever points at it: pigment is for the names.
u.fill(value, theme.color.raised);
u.fill(pointer, ui.mix(theme.color.raised, theme.color.page, 0.45));
u.fill(.{ .x = pointer.x, .y = r.y, .w = theme.stroke.rule, .h = r.h }, theme.color.page);
}
if (o.valueField()) |field| {
const bytes: usize = @intCast(@min(8, field.type.size() orelse 8));
var ink: ui.Ink = .{};
if (!o.freed) ink = u.written(value, now.written(o.addr + field.offset, bytes, .idea, 0), null);
if (Recording.word(moment, o.addr + field.offset, bytes) catch null) |n| {
const shift: u6 = @intCast(64 - 8 * bytes);
const signed = @as(i64, @bitCast(n << shift)) >> shift;
u.label(ink.face, theme.size.mono.small, value, .center, u.print("{d}", .{signed}), if (o.freed) ui.rgb(t.faint) else ink.ink);
} else u.unknown(value);
}
// The first pointer field: the square its arrow leaves from, or a slash for null.
for (o.type.record.fields) |field| {
if (field.type != .pointer) continue;
const held = Recording.word(moment, o.addr + field.offset, 8) catch null;
// On the solid of a strike the square is ink, like digits.
const struck = !o.freed and u.written(pointer, now.written(o.addr + field.offset, 8, .idea, 0), null).face == .mono_bold;
if (held == null) {
u.unknown(pointer);
} else if (held.? == 0) {
u.line(.{ pointer.x + 12, pointer.y + pointer.h - 10 }, .{ pointer.x + pointer.w - 12, pointer.y + 10 }, if (struck) t.ink else t.dim, theme.stroke.line);
} else u.fill(.{ .x = pointer.x + pointer.w / 2 - 7, .y = pointer.y + pointer.h / 2 - 7, .w = 14, .h = 14 }, if (struck) t.ink else theme.color.region.heap);
break;
}
}
/// The names: the root and the tracked variables, each a tag under
/// the node it points at, or at the row's end when it holds NULL.
/// What persists slides: a tag goes to its new place as the idea
/// strikes, and fades only where it has nowhere to come from.
fn tags(g: *const Nodes, u: ui.Ui, now: cursors.Now, things: []const objects.Object, places: []const Rect, park: ui.Vec) void {
const rec = g.cursor.rec;
const small = theme.size.mono.context;
const h = 22;
const states = [2]Recording.Moment{ now.before(), now.moment() };
const count = 1 + g.track.len;
// In each state, where each name points: an address, 0 for NULL, null for nowhere to draw.
const held = u.f.scratch.alloc([2]?u64, count) catch return;
var parked = false;
for (0..count) |i| for (states, 0..) |state, k| {
held[i][k] = null;
const v = rec.variable(u.f.scratch, state, if (i == 0) g.root else g.track[i - 1]) orelse continue;
if (!rec.assigned(v, state.index)) continue;
const to = (Recording.word(state, v.addr, 8) catch null) orelse continue;
if (to == 0 or placeOf(things, places, to) != null) held[i][k] = to;
if (to == 0) parked = true;
};
if (parked) u.text(.mono, small, park[0], park[1] + 16, "NULL", t.faint);
const p = cursors.glide(now.moving(.idea, 0, time.move));
for (0..count) |i| {
const name = if (i == 0) g.root else g.track[i - 1];
var at_place: [2]?ui.Vec = .{ null, null };
for (&at_place, 0..) |*place, k| {
const to = held[i][k] orelse continue;
// Under the names already at the same place.
var above: f32 = 0;
for (0..i) |other| above += @floatFromInt(@intFromBool(held[other][k] == to));
// Beside the names already at the same place: under the node's address, or at the row's end.
var width: f32 = 0;
for (0..i) |other| if (held[other][k] == to) {
width += u.width(.mono, small, if (other == 0) g.root else g.track[other - 1]) + 16 + 4;
};
place.* = if (to == 0) .{ park[0], park[1] + 24 + above * (h + 2) } else if (placeOf(things, places, to)) |r| .{ r.x + width, r.y + r.h + 28 } else null;
}
const xy = if (at_place[0] != null and at_place[1] != null) sk.math.mix(at_place[0].?, at_place[1].?, p) else at_place[1] orelse at_place[0] orelse continue;
const v = if (at_place[0] == null) u.faded(p) else if (at_place[1] == null) u.faded(1 - p) else u;
const tag: Rect = .{ .x = xy[0], .y = xy[1], .w = u.width(.mono, small, name) + 16, .h = h };
if (i > 0) v.fill(tag, theme.color.pigment[(i - 1) % theme.color.pigment.len]) else v.frame(tag, t.faint, theme.stroke.rule);
v.label(.mono, small, tag, .center, name, t.primary);
}
}
};
/// The pointer's square, of a node `w` wide.
fn pointerW(w: f32) f32 {
return @min(size.pointer_w, @round(w * 0.4));
}
fn placeOf(things: []const objects.Object, places: []const Rect, addr: u64) ?Rect {
for (things, places) |o, place| if (o.addr == addr) return place;
return null;
}
/// From the pointer square at `start` (in the node at `from`) to the left
/// edge of the node at `to`: straight to the neighbour on the right, else
/// up and over, in a lane of its own.
fn route(u: ui.Ui, start: ui.Vec, from: Rect, to: Rect, lane: f32) []const ui.Vec {
const enter = ui.Vec{ to.x - 2, to.y + to.h / 2 };
const out = u.f.scratch.alloc(ui.Vec, 5) catch return &.{};
if (@abs(to.y - from.y) < 1 and to.x > from.x and to.x - (from.x + from.w) < 100) {
out[0] = start;
out[1] = enter;
return out[0..2];
}
// Over the top when going back, under when going on past a neighbour.
const over = to.x < from.x or @abs(to.y - from.y) > 1;
const y = if (over) @min(from.y, to.y) - 12 - @mod(lane, 2) * 8 else @max(from.y + from.h, to.y + to.h) + 64 + @mod(lane, 2) * theme.stroke.lane_pitch;
out[0] = .{ start[0], if (over) from.y else from.y + from.h };
out[1] = .{ start[0], y };
out[2] = .{ to.x - 26, y };
out[3] = .{ to.x - 26, enter[1] };
out[4] = enter;
return out;
}
/// How many pointers from the root variable to `things[i]`, at least.
fn distance(scratch: std.mem.Allocator, rec: *const Recording, moment: Recording.Moment, things: []const objects.Object, root: []const u8, i: usize) usize {
const dist = scratch.alloc(usize, things.len) catch return 0;
@memset(dist, things.len);
if (rec.variable(scratch, moment, root)) |v| if (Recording.word(moment, v.addr, 8) catch null) |first| {
for (things, 0..) |o, k| if (o.addr == first) {
dist[k] = 0;
};
};
// Few nodes: relax until nothing changes.
var changed = true;
while (changed) {
changed = false;
for (things, 0..) |o, k| {
if (dist[k] == things.len) continue;
for (o.type.record.fields) |field| {
if (field.type != .pointer) continue;
const target = (Recording.word(moment, o.addr + field.offset, 8) catch null) orelse continue;
for (things, 0..) |other, j| if (other.addr == target and dist[j] > dist[k] + 1) {
dist[j] = dist[k] + 1;
changed = true;
};
}
}
}
return if (dist[i] == things.len) 0 else dist[i];
}
|