//! Snapshots, input recordings and replay: generic over state bytes and //! `abi.Event`s, so any sketch gets time travel for free. //! //! Playback is host state, not sketch state: wall clocks, modes and cursors //! must not contaminate byte comparisons between two runs of a sketch. //! //! Recordings are frames: each frame's events, then its `tick`. Playback, //! seek and step only ever stop between frames, and `frames` cuts a run of //! events into them, so `update` sees exactly the frames it saw live, one //! call each. const std = @import("std"); const posix = std.posix; const abi = @import("abi"); const memory = @import("memory.zig"); pub const recording_len = 4 * 1024 * 1024; pub const recording_count = 16; pub const recordings_len = recording_len * recording_count; const recording_magic = 0x52454305; pub const capacity = (recording_len - 32) / @sizeOf(abi.Event); pub const Recording = extern struct { duration: u64, count: u32, snapshot: u32, magic: u32, /// The build that recorded it (`build`, two halves), 0 when unknown. build_low: u32, build_high: u32, reserved: u32, events: [capacity]abi.Event, slack: [recording_len - 32 - capacity * @sizeOf(abi.Event)]u8, pub fn slice(r: *const Recording) []const abi.Event { return r.events[0..r.count]; } pub fn build(r: *const Recording) u64 { return @as(u64, r.build_high) << 32 | r.build_low; } /// Events up to the end of the last whole frame. pub fn whole(r: *const Recording) usize { return frameStart(r.slice(), r.count); } }; /// The largest frame boundary at or before `index`: 0, or just after a tick. pub fn frameStart(events: []const abi.Event, index: usize) usize { var i = @min(index, events.len); while (i > 0 and events[i - 1].kind != .tick) i -= 1; return i; } /// Cuts events into frames, each ending with its tick. Events after the /// last tick (a frame not finished) are never returned. pub fn frames(events: []const abi.Event) Frames { return .{ .events = events }; } pub const Frames = struct { events: []const abi.Event, start: usize = 0, pub fn next(f: *Frames) ?[]const abi.Event { var i = f.start; while (i < f.events.len) : (i += 1) { if (f.events[i].kind != .tick) continue; const frame = f.events[f.start .. i + 1]; f.start = i + 1; return frame; } return null; } }; comptime { std.debug.assert(@sizeOf(Recording) == recording_len); } /// Snapshot slots of a state file, and the recordings that start from them. pub const Bank = struct { state: *memory.StateFile, inputs: []align(memory.page) u8, pub fn slot(self: Bank, index: usize) []u8 { return self.state.slot(index); } pub fn recording(self: Bank, index: usize) *Recording { std.debug.assert(index < recording_count); return @ptrCast(@alignCast(self.inputs[index * recording_len ..].ptr)); } pub fn hasSnapshot(self: Bank, index: usize) bool { return index > 0 and index < memory.slot_count and self.state.used(index); } pub fn save(self: Bank, index: usize) void { std.debug.assert(index > 0 and index < memory.slot_count); for (0..recording_count) |i| { const r = self.recording(i); if (r.snapshot == index) r.magic = 0; } @memcpy(self.slot(index), self.slot(0)); self.state.markUsed(index, true); } pub fn restore(self: Bank, index: usize) !void { if (!self.hasSnapshot(index)) return error.EmptySnapshot; @memcpy(self.slot(0), self.slot(index)); } pub fn get(self: Bank, index: usize) !*Recording { const r = self.recording(index); if (r.magic != recording_magic or r.count > capacity or !self.hasSnapshot(r.snapshot)) return error.EmptyRecording; return r; } /// Leaf by leaf (`memory.compare`): padding never differs. pub fn compare(self: Bank, a: usize, b: usize) memory.Diff { return memory.compare(self.state.layout, self.slot(a), self.slot(b)); } }; pub const Timeline = struct { bank: Bank, mode: abi.Mode = .live, selected: usize = 0, cursor: usize = 0, position: u64 = 0, clock: u64 = 0, /// Set whenever live state is restored from a snapshot, for the host /// to reset the input state that went with the old bytes. restored: bool = false, /// Restores a snapshot into live state. pub fn restore(self: *Timeline, index: usize) !void { try self.bank.restore(index); self.restored = true; } /// `build` identifies the code recording (0: unknown); `play` warns /// when it differs. pub fn startRecording(self: *Timeline, index: usize, snapshot: usize, now: u64, build: u64) !void { // An unused snapshot captures the current state; an existing one is // restored, so several recordings can branch from exactly those bytes. if (!self.bank.hasSnapshot(snapshot)) self.bank.save(snapshot); try self.restore(snapshot); const r = self.bank.recording(index); @memset(std.mem.asBytes(r)[0..32], 0); r.magic = recording_magic; r.snapshot = @intCast(snapshot); r.build_low = @truncate(build); r.build_high = @truncate(build >> 32); self.selected = index; self.cursor = 0; self.position = 0; self.clock = now; self.mode = .recording; } /// Records one frame (its events, then its tick) and rewrites their /// times as recorded, so live `update` sees exactly what a replay will. /// A frame that does not fit ends the recording before it. pub fn capture(self: *Timeline, frame: []abi.Event) !void { if (self.mode != .recording) return; const r = self.bank.recording(self.selected); if (frame.len > capacity - r.count) { self.mode = .live; return error.RecordingFull; } for (frame) |*e| { // Queued events can predate the start command. Keep insertion // order and nondecreasing times, including several events at the // same timestamp. e.time = @max(e.time -| self.clock, r.duration); r.events[r.count] = e.*; r.count += 1; r.duration = e.time; } self.position = r.duration; self.cursor = r.count; } pub fn stop(self: *Timeline, now: u64) void { if (self.mode == .recording) { const r = self.bank.recording(self.selected); r.duration = @max(r.duration, now -| self.clock); self.position = r.duration; } self.mode = .live; } pub fn play(self: *Timeline, index: usize, now: u64) !void { const r = try self.bank.get(index); try self.restore(r.snapshot); self.selected = index; self.cursor = 0; self.position = 0; self.clock = now; self.mode = .playing; } pub fn pause(self: *Timeline, now: u64) void { if (self.mode == .playing) { self.mode = .paused; } else if (self.mode == .paused) { self.clock = now; self.mode = .playing; } } /// The recorded frames due by `now`: whole frames, whose ticks are due /// (a frame's input comes before its tick, so input alone is never /// due). Feed them to the same `update` that live input goes through. pub fn tick(self: *Timeline, now: u64) []const abi.Event { if (self.mode != .playing) return &.{}; const r = self.bank.recording(self.selected); self.position = @min(r.duration, self.position +| (now -| self.clock)); self.clock = now; const start = self.cursor; var i = self.cursor; while (i < r.count and r.events[i].time <= self.position) : (i += 1) { if (r.events[i].kind == .tick) self.cursor = i + 1; } if (self.position == r.duration) self.mode = .paused; return r.events[start..self.cursor]; } /// Restores the snapshot and returns the frames that make up the first /// `count` events (rounded down to a whole frame) to replay, so seeking /// backwards works too. pub fn seekCount(self: *Timeline, count: usize) ![]const abi.Event { const r = try self.bank.get(self.selected); try self.restore(r.snapshot); self.cursor = frameStart(r.slice(), count); self.position = if (self.cursor == 0) 0 else r.events[self.cursor - 1].time; self.mode = .paused; return r.events[0..self.cursor]; } /// To the last frame whose tick is at or before `time`. pub fn seekTime(self: *Timeline, time: u64) ![]const abi.Event { const r = try self.bank.get(self.selected); const position = @min(time, r.duration); var count: usize = 0; for (r.slice(), 0..) |e, i| { if (e.time > position) break; if (e.kind == .tick) count = i + 1; } const events = try self.seekCount(count); self.position = position; return events; } /// Moves by `steps` frames, forwards or back. pub fn step(self: *Timeline, steps: i64) ![]const abi.Event { const r = try self.bank.get(self.selected); const events = r.slice(); var cursor = frameStart(events, self.cursor); var remaining = @abs(steps); while (remaining > 0) : (remaining -= 1) { if (steps > 0) { const end = r.whole(); if (cursor == end) break; cursor += 1; while (cursor < end and events[cursor - 1].kind != .tick) cursor += 1; } else { if (cursor == 0) break; cursor = frameStart(events, cursor - 1); } } return self.seekCount(cursor); } }; /// Maps the recordings file next to a state file, creating it when missing. pub fn mapRecordings(path: []const u8) ![]align(memory.page) u8 { const fd = try posix.openat(posix.AT.FDCWD, path, .{ .ACCMODE = .RDWR, .CREAT = true }, 0o600); defer _ = posix.system.close(fd); if (try memory.fileSize(fd) != recordings_len) switch (posix.errno(posix.system.ftruncate(fd, recordings_len))) { .SUCCESS => {}, else => |err| return posix.unexpectedErrno(err), }; return memory.mapFile(fd, recordings_len, .{ .READ = true, .WRITE = true }); } test "frames are whole: input waits for its tick, live and in playback" { var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); defer arena.deinit(); const a = arena.allocator(); // A bank on plain memory: one slot of 8 bytes, snapshot 1 used. var file: memory.StateFile = undefined; file.map = try a.alignedAlloc(u8, .fromByteUnits(memory.page), memory.header_len + memory.slot_count * memory.page); @memset(file.map, 0); file.header().* = .{ .size = 8, .alignment = 1, .hash = 1, .stride = memory.page, .used = 0b11, .field_count = 0, .strings_len = 0 }; file.layout = .{}; const inputs = try a.alignedAlloc(u8, .fromByteUnits(memory.page), recording_len); @memset(inputs, 0); var t: Timeline = .{ .bank = .{ .state = &file, .inputs = inputs } }; // Frame k: a move at 10k ms, its tick at 10k + 5 ms; then a move with // no tick (a frame cut off). try t.startRecording(0, 1, 1000, 7); try std.testing.expect(t.restored); for (0..4) |k| { var frame = [_]abi.Event{ .{ .kind = .mouse_move, .time = 1000 + k * 10_000_000, .x = @floatFromInt(k) }, abi.Event.tick(1000 + k * 10_000_000 + 5_000_000, 16_666_667), }; try t.capture(&frame); // Live update sees the recorded times. try std.testing.expectEqual(@as(u64, k * 10_000_000 + 5_000_000), frame[1].time); } const r = t.bank.recording(0); r.events[r.count] = .{ .kind = .mouse_move, .time = 40_000_000 }; r.count += 1; t.stop(1000 + 41_000_000); try std.testing.expectEqual(@as(u64, 7), r.build()); try t.play(0, 0); var delivered: usize = 0; // Every moment between 0 and the end, 1 ms apart. var now: u64 = 0; while (t.mode == .playing) : (now += 1_000_000) { const events = t.tick(now); if (events.len == 0) continue; try std.testing.expectEqual(abi.Event.Kind.tick, events[events.len - 1].kind); var it = frames(events); while (it.next()) |frame| { try std.testing.expectEqual(@as(usize, 2), frame.len); delivered += 1; } } try std.testing.expectEqual(@as(usize, 4), delivered); try std.testing.expectEqual(@as(usize, 8), t.cursor); // A seek between a frame's input and its tick stops before the frame. try std.testing.expectEqual(@as(usize, 4), (try t.seekTime(22_000_000)).len); try std.testing.expectEqual(@as(usize, 8), (try t.seekCount(r.count)).len); try std.testing.expectEqual(@as(usize, 6), (try t.step(-1)).len); try std.testing.expectEqual(@as(usize, 8), (try t.step(5)).len); try std.testing.expectEqual(@as(usize, 2), (try t.step(-3)).len); // The cut-off frame is never fed. var it = frames(r.slice()); var n: usize = 0; while (it.next()) |_| n += 1; try std.testing.expectEqual(@as(usize, 4), n); } test "a tick's dt reads back the same live and replayed" { // E4: nanoseconds do not survive f32 seconds; both sides read the f32. for ([_]u64{ 16_666_667, 16_666_666, 15_000_001, 33_333_333, 0, 1 }) |dt| { const live = abi.Event.tick(5, dt); var recorded = live; recorded.time = 0; try std.testing.expectEqual(live.tickDt(), recorded.tickDt()); try std.testing.expect(@abs(@as(i64, @intCast(live.tickDt())) - @as(i64, @intCast(dt))) < 8); } }