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
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
|
//! 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);
try std.testing.expectEqual(abi.Event.tick(0, 16_666_667).tickDt(), frame[1].tickDt());
}
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);
try std.testing.expectEqual(abi.Event.tick(0, 16_666_667).tickDt(), frame[1].tickDt());
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);
}
}
|