//! 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 } } }); // Open, they are panels of their own on the map too. ctx.map.loupes = .{ near, deeper }; 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, under a caption of their own (the first is up 12 s at most). const first_trip = rec.lineMoment(21, reverse.enter); at.walk(s, .line, rec.lineMoment(19, reverse.enter)); says.line(s, "`cur` takes the head, and the loop begins\nat the first node."); at.walk(s, .line, first_trip); // The loop's caption leads the loop: as long as its step (the rest of the trip has captions of its own). says.line(s, "`next` remembers the way on,\nbefore `cur->next` is turned round."); 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`: the heap round that node opens\nunder it, and from its `next`, the node after."); near.open(s); s.wait(t.beat); deeper.open(s); // Held while the caption is read: 2 s at most without a change. s.wait(2.0); 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)); // The rest of the trip under captions of its own: a caption is up 12 s at most. says.line(s, "`cur->next` takes `prev`, NULL:\nthe first node is now the end of the list."); at.walk(s, .line, rec.lineMoment(23, loaded)); says.line(s, "Then `prev` and `cur` each step one node along,\nand the loop comes round to the second node."); 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,\nback to the node before it."); at.walk(s, .line, rec.lineMoment(23, third_trip)); says.line(s, "`prev` takes the last node, and `cur` runs off the end\nof the list: NULL, so the loop ends."); 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); }