summaryrefslogtreecommitdiff
path: root/anim/scenes/list.zig
blob: b7e6c4af362850267188d7072e4f7f2022018447 (plain) (blame)
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
//! A linked list reversed in place: no node moves, each `next` is rewritten
//! to point the other way. The debugger's context, and beside it the lens:
//! the nodes and their arrows over a hexdump of the heap they are made of.
//!
//! How it moves (design/motion.md): the picture is established; the first
//! trip round the loop is walked (each local strikes on the stack and in
//! the table, then its tag slides to its node; the pointer's rewrite is
//! armed with its old arrow going dashed, strikes, and the new arrow grows
//! to the node it lands on); after its first load the pointer loaded is
//! opened in a loupe, and the `next` in it one deeper; the second trip is
//! hurried, with a rest; the third is walked again, and `head` takes the
//! last node.
const anim = @import("anim");
const canim = @import("canim");
const recordings = @import("recordings");

pub const background = canim.background;
pub const scene = anim.Live(frame, struct {});

/// The variables whose tags the nodes carry: the three the loop moves, and `head`.
const tracked = [_][]const u8{ "prev", "cur", "next", "head" };

fn frame(s: *anim.Frame) void {
    const rec = canim.open(recordings.list);
    const t = canim.theme.time;
    const reverse = rec.call("reverse", 0);
    // From reverse's first line (the list of three is built) to its last.
    var at = canim.cursor(s, rec, rec.lineMoment(18, reverse.enter));
    // The nodes are the idea; a tag slides and an arrow grows after its strike.
    at.levels = .{ .idea = .data, .follow = t.move, .source_rows = 10 };
    const end = rec.lineMoment(27, reverse.enter);
    at.journey(.line, end);
    // The idea is the subject: the lens a size up, the nodes over the bytes they are.
    const split = canim.layout.split.subject;
    const ctx = canim.context(s, at, .{ .split = split });
    const list = canim.nodes(s, .{ .cursor = at, .stage = ctx.stage, .root = "head", .track = &tracked });
    ctx.map.add(s, canim.Nodes{ .cursor = at, .stage = ctx.map.stage, .root = "head", .track = &tracked });
    var says: canim.Narrator = .{};

    // The pointer just loaded, opened: rax holds `cur->next` after the
    // first trip's line 21; a loupe under it, and one from that node's `next`.
    const loaded = rec.lineMoment(22, rec.lineMoment(21, reverse.enter));
    const near = canim.loupe(s, .{ .cursor = at, .stage = ctx.stage, .from = .{ .register = "rax" } });
    const deeper = canim.loupe(s, .{ .cursor = at, .stage = ctx.stage, .from = .{ .field = .{ .loupe = near, .at = rec.register(loaded, "rax") + 8 } } });
    const joins = ctx.ties(s);
    // It opens on the map, the whole context unfolded: the first caption at
    // 1 s, the dive into the working frame at 2.5 s, the first step at 5 s.
    ctx.map.show(s, .{ ctx.clock, ctx.registers, ctx.stack, ctx.source, ctx.disasm, list, joins });
    s.wait(@max(t.establish - s.cursor, 0));
    says.line(s, "A list is nodes on the heap, each holding the address of the next.\nReversing it moves no node: it rewrites every `next`.");
    s.cursor = 2.5;
    ctx.map.dive(s);
    // Three names are set up.
    const first_trip = rec.lineMoment(21, reverse.enter);
    at.walk(s, .line, first_trip);
    // The loop's caption leads the loop.
    says.line(s, "`next` remembers the way on, `cur->next` is turned round,\nand `prev` and `cur` each step along.");
    at.walk(s, .line, loaded);
    // A beat of its own: the pointer just loaded is opened, and the one in it.
    says.line(s, "`rax` holds `cur->next`: under it opens the heap round that node,\nand from its `next`, one deeper, the node after it.");
    near.open(s);
    s.wait(t.beat);
    deeper.open(s);
    s.wait(2 * t.beat + t.loupe.open);
    deeper.close(s);
    s.wait(t.stagger * 3);
    near.close(s);
    s.wait(t.beat);
    const second_trip = rec.lineMoment(21, rec.lineMoment(24, first_trip));
    at.walk(s, .line, second_trip);
    // Pacing: the second trip is the same, so hurried; it keeps its rest.
    says.line(s, "The second node, the same way, faster:\nits `next` turns back to the first.");
    const third_trip = rec.lineMoment(21, rec.lineMoment(24, second_trip));
    at.hurry(s, .line, third_trip, .{});
    // The third in full again: the last `next` turns, and `cur` runs off the end.
    says.line(s, "The last node: its `next` turns too,\nand `cur` runs off the end of the list.");
    at.walk(s, .line, rec.lineMoment(26, third_trip));
    says.line(s, "`head` takes the last node: the same three nodes,\nin the same places, read the other way.");
    at.walk(s, .line, end);
    says.close(s);
}