diff options
Diffstat (limited to 'src/host/Sessions.zig')
| -rw-r--r-- | src/host/Sessions.zig | 1599 |
1 files changed, 1599 insertions, 0 deletions
diff --git a/src/host/Sessions.zig b/src/host/Sessions.zig new file mode 100644 index 0000000..d6caf9c --- /dev/null +++ b/src/host/Sessions.zig @@ -0,0 +1,1599 @@ +//! A sketch's save: one xitdb database holding every run of it, an +//! append-only log of the frames live `update` was fed, and the State at +//! the moments that matter (keyframes). The newest keyframe and the frames +//! after it are the present a run starts from (`present`). Nothing in it +//! is ever overwritten: marks and clips are names pointing into it. +//! +//! root = map { +//! version 1 +//! sessions list of session, one a run +//! marks list of { name, session, key }: a named keyframe (the newest of a name wins) +//! clips list of { name, session, key, start, end }: frames start..end of a +//! session, played from keyframe `key`; `end` 0 while recording +//! } +//! session = map { +//! started wall-clock ns at open ended ns at a clean exit, else 0 +//! from "" or where it came from ("import <file>") +//! stretches list of { frame, build, source, layout }: one a load (start, reloads); +//! `layout` is State's header (memory.State.header, read by memory.layoutOf) +//! batches list of bytes: a little-endian u64, the first frame's index, then +//! whole frames of raw `abi.Event`s, each frame ending with its tick +//! keys list of { frame, batch, stretch, why, time, size, pages, written, line }: +//! the State before frame `frame` is fed, in stretch `stretch`'s +//! layout; `batch` is where reading frames from it starts +//! frames frames committed +//! } +//! +//! A keyframe's State is `size` bytes in `pages`, a list of `page`-byte +//! blobs (the last one shorter), an all-zero page an empty slot. A keyframe +//! starts from the list of the one before it and writes only the pages +//! whose hash changed (`written` bytes), so every page another keyframe +//! holds unchanged is shared, never written twice. (Keyframes from before +//! pages hold their State whole, as `state` bytes; `load` reads both.) +//! +//! One transaction (`commit`) a second of session time, and at once for a +//! reload, a mark, a clip's start or end, and exit: a crash loses less than +//! a second of play; fsync only at exit and for a mark. A file a crash or +//! power loss tore opens at its last whole commit (`mend`). +//! +//! A save is at most `max_save`: a commit that leaves the file past it +//! drops history oldest first and compacts the file to three quarters of +//! it (`trim`); the present, the newest mark of each name and the newest +//! clip of each name are never dropped. A build that does not record +//! (`history` false) drops all it may at every keyframe, and compacts at +//! exit: what it keeps is the present and the marks. +const Sessions = @This(); +const std = @import("std"); +const xitdb = @import("xitdb"); +const abi = @import("abi"); + +pub const Disk = xitdb.Database(.buffered_file, u64); +pub const Memory = xitdb.Database(.memory, u64); + +/// `file` for every run but two: `memory` for a scripted run from fresh +/// state (time travel, nothing on disk), `off` for an export. +pub const Mode = enum { off, memory, file }; +pub const Why = enum(u64) { start, periodic, jump, before_reload, after_reload, mark, exit, import }; + +/// Pending frames are committed once they span a second of session time +/// (less a millisecond: 60 ticks of a 60 Hz clock that rounds down are one). +pub const commit_ns: u64 = std.time.ns_per_s - std.time.ns_per_ms; +/// A keyframe at least this often while the State changes. +pub const periodic_ns: u64 = 60 * std.time.ns_per_s; +/// Mark and clip names: no spaces, at most this long. +pub const max_name = 32; +/// A memory database (a scripted run's) stops recording at this size: ten +/// hours or more of play at 60 Hz. What it holds stays readable. +pub const memory_max: u64 = 256 << 20; +/// The most a save's file holds (State is at most half of it, +/// `abi.layout.max_state`, so history has room). +pub const max_save: u64 = 64 << 20; + +pub const K = enum(u64) { version = 1, sessions, marks, clips, started, ended, from, stretches, batches, keys, frames, frame, build, source, layout, batch, stretch, why, time, state, line, name, session, key, start, end, pages, size, written }; +fn key(k: K) u64 { + return @intFromEnum(k); +} + +pub const Stretch = struct { frame: u64 = 0, build: u64, source: []const u8, layout: []const u8 }; + +/// A keyframe's page: the OS page, the grain of sharing. +pub const page = 4096; + +/// A keyframe: `session`'s keyframe `key`. +const At = struct { session: u64, key: u64 }; + +/// A keyframe queued: the pages of its State that differ from keyframe +/// `from`'s (`indices`, ascending; their bytes one after the other in +/// `pages`, `page` apart). +const Keyframe = struct { frame: u64, batch: u64, stretch: u64, why: Why, time: u64, size: u64, from: ?At, indices: []u64, pages: []u8, line: []u8 }; + +gpa: std.mem.Allocator, +/// Files and the wall clock; a memory database runs on `std.Io.failing`. +io: std.Io, +db: union(Mode) { off, memory: Memory, file: Disk } = .off, +file: ?std.Io.File = null, +/// The database's write buffer, an allocation of its own: the database +/// points at it. +buffer: ?*std.Io.Writer.Allocating = null, +/// The database's path (file mode), owned. +path: []const u8 = "", +/// This run's index in `sessions`. +session: u64 = 0, +/// Frames logged, committed or not, and committed. +frames: u64 = 0, +committed: u64 = 0, +/// This session's committed batches, its stretches and its keyframes +/// (queued ones too). +batches: u64 = 0, +stretches: u64 = 0, +keys: u64 = 0, +/// The frames since the last commit, as the batch they become. +batch: std.ArrayList(u8) = .empty, +/// The first pending frame's tick. +batch_time: u64 = 0, +/// The first and latest event time logged: times never go back. +first_time: u64 = 0, +last_time: u64 = 0, +/// The last keyframe's time and stretch. +key_time: u64 = 0, +key_stretch: u64 = 0, +/// The keyframe the next one starts from (the last one, or the one a run +/// started from), and the hashes of its pages. +last: ?At = null, +hashes: []u64 = &.{}, +queued: std.ArrayList(Keyframe) = .empty, +/// The clip being recorded, an index into `clips`. +recording: ?u64 = null, +/// State may have changed other than by a logged live frame (a replay ran): +/// the next live frame starts with a keyframe. +away: bool = false, +/// A memory database reached `memory_max`: nothing more is logged. +full: bool = false, +/// The console line that last changed State, for the next keyframe. +line: [256]u8 = undefined, +line_len: usize = 0, +/// Keep history, up to `max_save`; else only the present and the marks. +history: bool = true, + +/// Opens the database at `path` (file mode: created with its directory when +/// missing; one a crash or power loss tore is opened at its last whole +/// commit (`mend`); one still refused is renamed aside, never deleted) and +/// starts this run's session in it. +pub fn open(gpa: std.mem.Allocator, io: std.Io, want: Mode, path: []const u8, first: Stretch, started: u64) !Sessions { + var s: Sessions = .{ .gpa = gpa, .io = io }; + if (want == .off) return s; + errdefer s.deinit(); + const buffer = try gpa.create(std.Io.Writer.Allocating); + buffer.* = .init(gpa); + s.buffer = buffer; + switch (want) { + .off => unreachable, + .memory => s.db = .{ .memory = try Memory.init(std.Io.failing, .{ .buffer = buffer, .file_id = 0, .max_size = memory_max }) }, + .file => { + s.path = try gpa.dupe(u8, path); + const cwd = std.Io.Dir.cwd(); + if (std.fs.path.dirname(path)) |dir| try cwd.createDirPath(io, dir); + var aside = false; + while (true) { + const file = try cwd.createFile(io, path, .{ .read = true, .truncate = false }); + if (Disk.init(io, .{ .file = file, .buffer = buffer, .fsync = false })) |db| { + s.db = .{ .file = db }; + s.file = file; + break; + } else |err| { + switch (err) { + error.InvalidDatabase, error.InvalidVersion, error.InvalidHashSize, error.TruncatedDatabase, error.InvalidEnumTag, error.EndOfStream => {}, + else => { + file.close(io); + return err; + }, + } + if (mend(io, file, buffer)) |db| { + s.db = .{ .file = db }; + s.file = file; + std.log.warn("{s} was torn after its last whole commit: opened at it", .{path}); + break; + } + file.close(io); + if (aside) return err; + aside = true; + var buf: [std.fs.max_path_bytes + 32]u8 = undefined; + const to = try std.fmt.bufPrint(&buf, "{s}.broken.{d}", .{ path, started / std.time.ns_per_s }); + try cwd.rename(path, cwd, to, io); + std.log.warn("{s} is no sessions database this host reads: moved to {s}", .{ path, to }); + } + } + }, + } + s.session = try s.count(.sessions); + try s.commit(.{ .open = .{ .started = started, .first = first } }); + s.stretches = 1; + return s; +} + +/// The database at `path`, read only and no session started in it: for +/// its `present` with no run of the sketch (`fs` with the sketch closed). +pub fn openRead(gpa: std.mem.Allocator, io: std.Io, path: []const u8) !Sessions { + var s: Sessions = .{ .gpa = gpa, .io = io }; + errdefer s.deinit(); + s.file = try std.Io.Dir.cwd().openFile(io, path, .{}); + s.buffer = try gpa.create(std.Io.Writer.Allocating); + s.buffer.?.* = .init(gpa); + s.db = .{ .file = try Disk.init(io, .{ .file = s.file.?, .buffer = s.buffer.?, .fsync = false }) }; + s.session = try s.count(.sessions); + return s; +} + +pub fn deinit(s: *Sessions) void { + s.dropQueued(); + s.queued.deinit(s.gpa); + s.batch.deinit(s.gpa); + s.gpa.free(s.hashes); + if (s.file) |f| f.close(s.io); + if (s.buffer) |b| { + b.deinit(); + s.gpa.destroy(b); + } + s.gpa.free(s.path); + s.* = .{ .gpa = s.gpa, .io = s.io }; +} + +/// The last frames, an exit keyframe of `state`, and the session's end, in +/// one transaction synced to disk; then closed. Without history the file is +/// compacted, so the frames it dropped are gone from the disk too. +pub fn close(s: *Sessions, state: []const u8, ended: u64) void { + defer s.deinit(); + if (s.db == .off) return; + s.stopClip() catch {}; + _ = s.keyframe(.exit, state) catch {}; + s.commitSynced(.{ .end = ended }) catch |err| std.log.warn("sessions: last commit failed: {t}", .{err}); + if (s.db == .file and !s.history) s.compact() catch |err| std.log.warn("sessions: not compacted: {t}", .{err}); +} + +/// Writes what the database holds now, without the nodes commits left +/// behind, to `<path>.new`, synced, renames it over the file, and goes on +/// in it. +fn compact(s: *Sessions) !void { + const cwd = std.Io.Dir.cwd(); + var buf: [std.fs.max_path_bytes + 8]u8 = undefined; + const new = try std.fmt.bufPrint(&buf, "{s}.new", .{s.path}); + const file = try cwd.createFile(s.io, new, .{ .read = true, .truncate = true }); + errdefer { + file.close(s.io); + cwd.deleteFile(s.io, new) catch {}; + } + const buffer = try s.gpa.create(std.Io.Writer.Allocating); + buffer.* = .init(s.gpa); + errdefer { + buffer.deinit(); + s.gpa.destroy(buffer); + } + var offsets: std.AutoHashMap(u64, u64) = .init(s.gpa); + defer offsets.deinit(); + var db = try s.db.file.compact(.buffered_file, .{ .file = file, .buffer = buffer, .fsync = true }, &offsets); + db.core.file.fsync = false; + try cwd.rename(new, cwd, s.path, s.io); + s.file.?.close(s.io); + s.buffer.?.deinit(); + s.gpa.destroy(s.buffer.?); + s.file = file; + s.buffer = buffer; + s.db = .{ .file = db }; +} + +/// Drops history oldest first, then compacts the file: until its keyframes' +/// pages and frames are under three quarters of `max_save`, or, without +/// history, all it may (compacted only past `max_save`; `close` does it +/// at exit). A few rounds at most: what a dropped keyframe wrote may still +/// be shared by one kept, so a round can free less than it counted. +fn trim(s: *Sessions) !void { + const goal = max_save / 4 * 3; + var keep: u64 = if (s.history) goal else 0; + for (0..4) |_| { + var dropped: u64 = 0; + var left: u64 = 0; + try s.db.file.runContext(Trim(Disk){ .s = s, .keep = keep, .dropped = &dropped, .left = &left }); + var size = try s.file.?.length(s.io); + if (!s.history and size <= max_save) return; + try s.compact(); + size = try s.file.?.length(s.io); + if (size <= goal or dropped == 0) return; + // What the count leaves out (lists, maps, stretches) is the rest. + keep = left -| (size - goal); + } +} + +/// A keyframe's pages or a batch of frames, for `trim`. +const Item = struct { session: u64, index: u64, frame: u64, bytes: u64, batch: bool, keep: bool }; + +/// The transaction of `trim`: drops a keyframe by removing its pages (its +/// fields stay, so keyframe numbers and searches by frame still work) and +/// a batch by emptying its slot, oldest first, until what is left counts at +/// most `keep` bytes; a session left with nothing loses its keyframes, +/// batches and stretches. Never the present (the newest keyframe and the +/// batches from its own on), the keyframe of the newest mark or clip of a +/// name, or a batch holding a frame of such a clip. +fn Trim(comptime DB: type) type { + return struct { + s: *Sessions, + keep: u64, + /// Bytes dropped, and counted after. + dropped: *u64, + left: *u64, + + const R = Read(DB); + const Map = DB.HashMap(.read_write); + const List = DB.ArrayList(.read_write); + + pub fn run(ctx: @This(), cursor: *DB.Cursor(.read_write)) !void { + var arena: std.heap.ArenaAllocator = .init(ctx.s.gpa); + defer arena.deinit(); + const a = arena.allocator(); + const root = try Map.init(cursor.*); + const all = try R.list(root.readOnly(), .sessions) orelse return; + const n = try all.count(); + var pinned: std.AutoHashMapUnmanaged(At, void) = .empty; + const Clip = struct { session: u64, start: u64, end: u64 }; + var clips: std.ArrayList(Clip) = .empty; + for ([_]K{ .marks, .clips }) |which| { + const list = try R.list(root.readOnly(), which) orelse continue; + var names: std.StringHashMapUnmanaged(void) = .empty; + var i = try list.count(); + while (i > 0) { + i -= 1; + const e = try R.at(list, i); + var buf: [max_name]u8 = undefined; + const name = (try R.field(e, .name)).readBytes(&buf) catch return error.CorruptSession; + if ((try names.getOrPut(a, try a.dupe(u8, name))).found_existing) continue; + const at: At = .{ .session = try R.uint(e, .session), .key = try R.uint(e, .key) }; + try pinned.put(a, at, {}); + const end = if (which == .clips) try R.uint(e, .end) else continue; + try clips.append(a, .{ .session = at.session, .start = try R.uint(e, .start), .end = if (end == 0) std.math.maxInt(u64) else end }); + } + } + // The present: the newest keyframe, and the batches from its own on. + var now: At = undefined; + var now_batch: u64 = 0; + var i = n; + while (true) { + if (i == 0) return; + i -= 1; + const keys = try R.list(try R.at(all, i), .keys) orelse continue; + const n_keys = try keys.count(); + if (n_keys == 0) continue; + now = .{ .session = i, .key = n_keys - 1 }; + now_batch = try R.uint(try R.at(keys, n_keys - 1), .batch); + break; + } + try pinned.put(a, now, {}); + // What is not dropped yet, each session's in frame order. + var items: std.ArrayList(Item) = .empty; + var total: u64 = 0; + for (0..n) |si| { + const ses = try R.at(all, si); + const start = items.items.len; + if (try R.list(ses, .keys)) |keys| for (0..try keys.count()) |k| { + const e = try R.at(keys, k); + if (try e.getCursor(key(.pages)) == null) continue; + const written = if (try e.getCursor(key(.written))) |w| try w.readUint() else 0; + try items.append(a, .{ .session = si, .index = k, .frame = try R.uint(e, .frame), .bytes = written, .batch = false, .keep = pinned.contains(.{ .session = si, .key = k }) }); + }; + if (try R.list(ses, .batches)) |batches| for (0..try batches.count()) |b| { + var c = try batches.getCursor(@intCast(b)) orelse continue; + if ((try c.slot()).tag == .none) continue; + var buf: [8]u8 = undefined; + var reader = try c.reader(&buf); + var head: [8]u8 = undefined; + try reader.interface.readSliceAll(&head); + try items.append(a, .{ .session = si, .index = b, .frame = std.mem.readInt(u64, &head, .little), .bytes = reader.size, .batch = true, .keep = si == now.session and b >= now_batch }); + }; + const mine = items.items[start..]; + std.mem.sort(Item, mine, {}, struct { + fn lessThan(_: void, x: Item, y: Item) bool { + return x.frame < y.frame or (x.frame == y.frame and !x.batch and y.batch); + } + }.lessThan); + // A batch holds frames up to the next batch's first. + const frames = try R.uint(ses, .frames); + var end: u64 = std.math.maxInt(u64); + var j = mine.len; + while (j > 0) { + j -= 1; + const it = &mine[j]; + if (!it.batch) continue; + const last = @min(end, frames); + for (clips.items) |clip| if (clip.session == si and clip.start < last and it.frame < clip.end) { + it.keep = true; + }; + end = it.frame; + } + for (mine) |it| total += it.bytes; + } + // Dropped oldest first. + const sessions = try List.init(try root.putCursor(key(.sessions))); + var left: std.ArrayList(u64) = .empty; + try left.appendNTimes(a, 0, n); + for (items.items) |it| { + if (it.keep or total <= ctx.keep) { + left.items[it.session] += 1; + continue; + } + const ses = try Map.init(try sessions.putCursor(@intCast(it.session))); + if (it.batch) { + try (try List.init(try ses.putCursor(key(.batches)))).put(@intCast(it.index), .{ .slot = null }); + } else { + const k = try Map.init(try (try List.init(try ses.putCursor(key(.keys)))).putCursor(@intCast(it.index))); + _ = try k.remove(key(.pages)); + try k.put(key(.written), .{ .uint = 0 }); + } + total -= it.bytes; + ctx.dropped.* += it.bytes; + } + ctx.left.* = total; + for (left.items, 0..) |kept, si| { + if (kept > 0 or si >= now.session) continue; + var any = false; + var it = pinned.keyIterator(); + while (it.next()) |at| any = any or at.session == si; + if (any) continue; + const ses = try Map.init(try sessions.putCursor(@intCast(si))); + for ([_]K{ .keys, .batches, .stretches }) |k| _ = try ses.remove(key(k)); + } + } + }; +} + +/// The bytes of every session's batches and keyframes' pages (each written +/// once): what compaction keeps. +/// Reading them all is also what proves a mended file whole. +fn liveSize(db: *Disk) !u64 { + const R = Read(Disk); + const sessions = try R.list(try R.root(db), .sessions) orelse return 0; + var live: u64 = 0; + var it = try sessions.iterator(); + while (try it.next()) |c| { + const session = try R.Map.init(c); + if (try R.list(session, .batches)) |batches| { + var b = try batches.iterator(); + while (try b.next()) |blob| live += if ((try blob.slot()).tag == .none) 0 else try blob.count(); + } + if (try R.list(session, .keys)) |keys| { + var k = try keys.iterator(); + while (try k.next()) |key_cursor| { + const e = try R.Map.init(key_cursor); + live += if (try e.getCursor(key(.written))) |w| try w.readUint() else try (try R.field(e, .state)).count(); + } + } + } + return live; +} + +// xitdb's layout, as `mend` reads it (zig-pkg's xitdb src/lib.zig): the +// database header (its file id the last 8 of its 20 bytes, big endian), the +// root header (the root slot's 9 bytes, then the committed size's 8), and +// the trailer ending every commit (the root slot's 9 bytes, the commit id's +// 8, and their CRC-64/XZ's 8, with the file id and its own position). +const db_header_len = 20; +const root_header_end = db_header_len + 17; +const trailer_len = 25; +const hash_map_tag = 4; + +/// A file xitdb refused because a crash or power loss tore its last commit +/// (its root header written, the commit's bytes not all): opened at the last +/// commit before the tear whose trailer verifies and whose sessions read +/// whole, scanned back from the file's end, its root header put back at it. +/// Null, the file as it was, when none does. +fn mend(io: std.Io, file: std.Io.File, buffer: *std.Io.Writer.Allocating) ?Disk { + var head: [root_header_end]u8 = undefined; + if ((file.readPositionalAll(io, &head, 0) catch return null) != head.len or !std.mem.eql(u8, head[0..3], "xit")) return null; + const file_id = std.mem.readInt(u64, head[db_header_len - 8 .. db_header_len], .big); + var chunk: [64 << 10]u8 = undefined; + var end = file.length(io) catch return null; + while (end >= root_header_end + trailer_len) { + const start = @max(root_header_end, end - @min(end, chunk.len)); + const got = file.readPositionalAll(io, chunk[0 .. end - start], start) catch return null; + if (got != end - start) return null; + var i = got; + while (i >= trailer_len) : (i -= 1) { + const t = chunk[i - trailer_len ..][0..trailer_len]; + const at = start + i - trailer_len; + // The root is a map, at a slot written before its trailer. + if (t[0] & 0x7f != hash_map_tag or std.mem.readInt(u64, t[1..9], .big) >= at) continue; + var sum: [33]u8 = undefined; + std.mem.writeInt(u64, sum[0..8], file_id, .big); + std.mem.writeInt(u64, sum[8..16], at, .big); + @memcpy(sum[16..33], t[0..17]); + if (std.hash.crc.@"CRC-64/XZ".hash(&sum) != std.mem.readInt(u64, t[17..25], .big)) continue; + var root: [17]u8 = undefined; + @memcpy(root[0..9], t[0..9]); + std.mem.writeInt(u64, root[9..17], at + trailer_len, .big); + file.writePositionalAll(io, &root, db_header_len) catch return null; + var db = Disk.init(io, .{ .file = file, .buffer = buffer, .fsync = false }) catch continue; + _ = liveSize(&db) catch continue; + file.sync(io) catch {}; + return db; + } + if (start == root_header_end) break; + end = start + trailer_len - 1; + } + file.writePositionalAll(io, head[db_header_len..], db_header_len) catch {}; + return null; +} + +pub fn mode(s: *const Sessions) Mode { + return s.db; +} + +/// Remembers the console line that changed State, for the next keyframe. +pub fn noteLine(s: *Sessions, line: []const u8) void { + s.line_len = @min(line.len, s.line.len); + @memcpy(s.line[0..s.line_len], line[0..s.line_len]); +} + +/// One live frame, its tick last, before `update` is fed it: its times are +/// made never to go back (what `update` then sees is what a replay will), +/// and it is logged, after a keyframe of `state` when `why` says so or the +/// last is a minute old. +pub fn frame(s: *Sessions, one: []abi.Event, state: []const u8, why: ?Why) !void { + for (one) |*e| { + e.time = @max(e.time, s.last_time); + s.last_time = e.time; + } + if (s.db == .off or s.full) return; + const tick = one[one.len - 1].time; + if (s.batch.items.len > 0 and tick -| s.batch_time >= commit_ns) try s.commit(.none); + if (why) |w| { + _ = try s.keyframe(w, state); + } else if (tick -| s.key_time >= periodic_ns) _ = try s.keyframe(.periodic, state); + if (s.frames == 0) s.first_time = tick; + if (s.batch.items.len == 0) { + try s.batch.appendSlice(s.gpa, std.mem.asBytes(&std.mem.nativeToLittle(u64, s.frames))); + s.batch_time = tick; + } + try s.batch.appendSlice(s.gpa, std.mem.sliceAsBytes(one)); + s.frames += 1; +} + +/// Queues a keyframe of `state` before the next frame, and returns its +/// index; an unchanged State is the last keyframe again (but for a +/// `before_reload` one: the last word in the old layout). Only the pages +/// whose hash differs from the last keyframe's are copied, and written. +pub fn keyframe(s: *Sessions, why: Why, state: []const u8) !u64 { + if (s.db == .off) return error.NotRecording; + defer s.line_len = 0; + const hashes = try s.gpa.alloc(u64, std.math.divCeil(usize, state.len, page) catch unreachable); + errdefer s.gpa.free(hashes); + var changed: std.ArrayList(u64) = .empty; + defer changed.deinit(s.gpa); + for (hashes, 0..) |*h, i| { + h.* = std.hash.Wyhash.hash(0, state[i * page .. @min(state.len, (i + 1) * page)]); + if (i >= s.hashes.len or s.hashes[i] != h.*) try changed.append(s.gpa, i); + } + if (s.keys > 0 and why != .before_reload and changed.items.len == 0 and hashes.len == s.hashes.len and s.key_stretch == s.stretches - 1) { + s.gpa.free(hashes); + return s.keys - 1; + } + const pages = try s.gpa.alloc(u8, changed.items.len * page); + errdefer s.gpa.free(pages); + for (changed.items, 0..) |i, k| { + const bytes = state[i * page .. @min(state.len, (i + 1) * page)]; + @memcpy(pages[k * page ..][0..bytes.len], bytes); + } + const indices = try changed.toOwnedSlice(s.gpa); + errdefer s.gpa.free(indices); + const line_copy = try s.gpa.dupe(u8, s.line[0..s.line_len]); + errdefer s.gpa.free(line_copy); + try s.queued.append(s.gpa, .{ .frame = s.frames, .batch = s.batches, .stretch = s.stretches - 1, .why = why, .time = s.last_time, .size = state.len, .from = s.last, .indices = indices, .pages = pages, .line = line_copy }); + s.gpa.free(s.hashes); + s.hashes = hashes; + s.last = .{ .session = s.session, .key = s.keys }; + s.key_time = s.last_time; + s.key_stretch = s.stretches - 1; + s.keys += 1; + return s.keys - 1; +} + +/// A new stretch from the next frame: a reload's build, source and layout. +pub fn stretch(s: *Sessions, st: Stretch) !void { + if (s.db == .off) return; + var with = st; + with.frame = s.frames; + try s.commit(.{ .stretch = with }); + s.stretches += 1; +} + +/// Mark `name`: a keyframe of `state` (`why`: `.mark`, or `.import`), +/// synced to disk. Returns the keyframe's index. A mark of a new name needs +/// room for a whole State under `max_save`, history dropped to make it +/// (`trim`): without, it is refused (`error.SaveFull`). A mark over an +/// existing name lets the older one go with history. +pub fn mark(s: *Sessions, name: []const u8, why: Why, state: []const u8) !u64 { + if (s.db == .file and try s.file.?.length(s.io) + state.len > max_save and try s.findMark(name) == null) { + try s.trim(); + if (try s.file.?.length(s.io) + state.len > max_save) return error.SaveFull; + } + const k = try s.keyframe(why, state); + try s.commitSynced(.{ .mark = .{ .name = name, .key = k } }); + return k; +} + +/// Starts clip `name` at the next frame, played from keyframe `k`. +pub fn startClip(s: *Sessions, name: []const u8, k: u64) !void { + const index = try s.count(.clips); + try s.commit(.{ .clip = .{ .name = name, .key = k, .start = s.frames } }); + s.recording = index; +} + +/// Ends the clip being recorded after the frames logged so far. +pub fn stopClip(s: *Sessions) !void { + const index = s.recording orelse return; + try s.commit(.{ .clip_end = .{ .index = index, .end = s.frames } }); + s.recording = null; +} + +fn dropQueued(s: *Sessions) void { + for (s.queued.items) |k| { + s.gpa.free(k.indices); + s.gpa.free(k.pages); + s.gpa.free(k.line); + } + s.queued.clearRetainingCapacity(); +} + +const Extra = union(enum) { + none, + open: struct { started: u64, first: Stretch }, + stretch: Stretch, + mark: struct { name: []const u8, key: u64 }, + clip: struct { name: []const u8, key: u64, start: u64 }, + clip_end: struct { index: u64, end: u64 }, + end: u64, +}; + +fn commitSynced(s: *Sessions, extra: Extra) !void { + if (s.db == .file) s.db.file.core.file.fsync = true; + defer if (s.db == .file) { + s.db.file.core.file.fsync = false; + }; + try s.commit(extra); +} + +/// One transaction: the pending frames, the queued keyframes and `extra`. +pub fn commit(s: *Sessions, extra: Extra) !void { + switch (s.db) { + .off => return, + inline .memory, .file => |*db| db.runContext(Commit(@TypeOf(db.*)){ .s = s, .extra = extra }) catch |err| { + // A memory database that cannot grow (`memory_max`, or no + // memory left) stops recording, once. + if (s.db == .memory and !s.full) { + s.full = true; + s.batch.clearRetainingCapacity(); + s.dropQueued(); + std.log.warn("sessions: the memory database cannot grow ({t}; {d} MiB at most): no more frames recorded", .{ err, memory_max >> 20 }); + } + return err; + }, + } + if (s.batch.items.len > 0) { + s.batches += 1; + s.committed = s.frames; + s.batch.clearRetainingCapacity(); + } + const keyed = s.queued.items.len > 0; + s.dropQueued(); + if (s.db != .file) return; + if ((try s.file.?.length(s.io)) > max_save or (!s.history and keyed)) s.trim() catch |err| std.log.warn("sessions: history not trimmed: {t}", .{err}); +} + +fn Commit(comptime DB: type) type { + return struct { + s: *Sessions, + extra: Extra, + + const Map = DB.HashMap(.read_write); + const List = DB.ArrayList(.read_write); + + pub fn run(ctx: @This(), cursor: *DB.Cursor(.read_write)) !void { + const s = ctx.s; + const root = try Map.init(cursor.*); + const sessions = try List.init(try root.putCursor(key(.sessions))); + if (ctx.extra == .open) { + const o = ctx.extra.open; + try root.put(key(.version), .{ .uint = 1 }); + const session = try Map.init(try sessions.appendCursor()); + try session.put(key(.started), .{ .uint = o.started }); + try session.put(key(.ended), .{ .uint = 0 }); + try session.put(key(.from), .{ .bytes = "" }); + try session.put(key(.frames), .{ .uint = 0 }); + try putStretch(try List.init(try session.putCursor(key(.stretches))), o.first); + return; + } + const session = try Map.init(try sessions.putCursor(@intCast(s.session))); + if (s.batch.items.len > 0) { + try (try List.init(try session.putCursor(key(.batches)))).append(.{ .bytes = s.batch.items }); + try session.put(key(.frames), .{ .uint = s.frames }); + } + if (s.queued.items.len > 0) { + const keys = try List.init(try session.putCursor(key(.keys))); + for (s.queued.items) |q| { + const k = try Map.init(try keys.appendCursor()); + try k.put(key(.frame), .{ .uint = q.frame }); + try k.put(key(.batch), .{ .uint = q.batch }); + try k.put(key(.stretch), .{ .uint = q.stretch }); + try k.put(key(.why), .{ .uint = @intFromEnum(q.why) }); + try k.put(key(.time), .{ .uint = q.time }); + try k.put(key(.size), .{ .uint = q.size }); + try k.put(key(.line), .{ .bytes = q.line }); + // From the keyframe before's pages, copied as the + // transaction writes on (it may be in it too). + var from = try k.putCursor(key(.pages)); + if (q.from) |at| if (try pagesSlot(root, at)) |slot| { + try from.write(.{ .slot = slot }); + try from.freeze(); + }; + const pages = try List.init(from); + const had = try pages.count(); + var written: u64 = 0; + for (q.indices, 0..) |i, j| { + const bytes = q.pages[j * page ..][0..@min(page, q.size - i * page)]; + const zero = std.mem.allEqual(u8, bytes, 0); + if (!zero) written += bytes.len; + const data: DB.WriteableData = if (zero) .{ .slot = null } else .{ .bytes = bytes }; + if (i < had) try pages.put(@intCast(i), data) else try pages.append(data); + } + const n = std.math.divCeil(u64, q.size, page) catch unreachable; + if (had > n) try pages.slice(n); + try k.put(key(.written), .{ .uint = written }); + } + } + switch (ctx.extra) { + .none, .open => {}, + .stretch => |st| try putStretch(try List.init(try session.putCursor(key(.stretches))), st), + .mark => |m| { + const item = try Map.init(try (try List.init(try root.putCursor(key(.marks)))).appendCursor()); + try item.put(key(.name), .{ .bytes = m.name }); + try item.put(key(.session), .{ .uint = s.session }); + try item.put(key(.key), .{ .uint = m.key }); + }, + .clip => |c| { + const item = try Map.init(try (try List.init(try root.putCursor(key(.clips)))).appendCursor()); + try item.put(key(.name), .{ .bytes = c.name }); + try item.put(key(.session), .{ .uint = s.session }); + try item.put(key(.key), .{ .uint = c.key }); + try item.put(key(.start), .{ .uint = c.start }); + try item.put(key(.end), .{ .uint = 0 }); + }, + .clip_end => |c| { + const item = try Map.init(try (try List.init(try root.putCursor(key(.clips)))).putCursor(@intCast(c.index))); + try item.put(key(.end), .{ .uint = c.end }); + }, + .end => |t| try session.put(key(.ended), .{ .uint = t }), + } + } + + /// The slot of keyframe `at`'s pages; null for one from before pages. + fn pagesSlot(root: Map, at: At) !?xitdb.Slot { + const R = Read(DB); + const ses = try R.at(try R.list(root.readOnly(), .sessions) orelse return null, at.session); + return (try R.at(try R.list(ses, .keys) orelse return null, at.key)).getSlot(key(.pages)); + } + + fn putStretch(list: List, st: Stretch) !void { + const item = try Map.init(try list.appendCursor()); + try item.put(key(.frame), .{ .uint = st.frame }); + try item.put(key(.build), .{ .uint = st.build }); + try item.put(key(.source), .{ .bytes = st.source }); + try item.put(key(.layout), .{ .bytes = st.layout }); + } + }; +} + +// --------------------------------------------------------------------------- +// Reading + +/// A mark (`start` and `end` 0) or a clip. +pub const Entry = struct { + session: u64, + key: u64, + start: u64 = 0, + end: u64 = 0, + bytes: [max_name]u8 = undefined, + len: usize = 0, + + pub fn name(e: *const Entry) []const u8 { + return e.bytes[0..e.len]; + } +}; +/// A keyframe, its bytes `gpa`'s (`free`). +pub const Loaded = struct { + /// Stored in pages (not whole, from before them). + paged: bool = true, + frame: u64, + batch: u64, + why: Why, + time: u64, + state: []const u8, + line: []const u8, + /// Its stretch: the layout of `state`, and the build that wrote it. + stretch: u64, + build: u64, + source: []const u8, + layout: []const u8, + + pub fn free(l: Loaded, gpa: std.mem.Allocator) void { + for ([_][]const u8{ l.state, l.line, l.source, l.layout }) |b| gpa.free(b); + } +}; + +pub fn markAt(s: *Sessions, i: u64) !Entry { + return s.entryAt(.marks, i); +} +pub fn clipAt(s: *Sessions, i: u64) !Entry { + return s.entryAt(.clips, i); +} +/// The newest mark named `name`. +pub fn findMark(s: *Sessions, name: []const u8) !?Entry { + return s.findNamed(.marks, name); +} +/// The newest clip named `name`. +pub fn findClip(s: *Sessions, name: []const u8) !?Entry { + return s.findNamed(.clips, name); +} + +fn findNamed(s: *Sessions, which: K, name: []const u8) !?Entry { + var i = try s.count(which); + while (i > 0) { + i -= 1; + const e = try s.entryAt(which, i); + if (std.mem.eql(u8, e.name(), name)) return e; + } + return null; +} + +fn entryAt(s: *Sessions, which: K, i: u64) !Entry { + switch (s.db) { + .off => return error.NotRecording, + inline .memory, .file => |*db| { + const R = Read(@TypeOf(db.*)); + const e = try R.at(try R.list(try R.root(db), which) orelse return error.NoSuchEntry, i); + var out: Entry = .{ .session = try R.uint(e, .session), .key = try R.uint(e, .key) }; + out.len = ((try R.field(e, .name)).readBytes(&out.bytes) catch return error.CorruptSession).len; + if (which == .clips) { + out.start = try R.uint(e, .start); + out.end = try R.uint(e, .end); + } + return out; + }, + } +} + +/// Entries in the root list `which`, or sessions. +pub fn count(s: *Sessions, which: K) !u64 { + switch (s.db) { + .off => return error.NotRecording, + inline .memory, .file => |*db| { + const R = Read(@TypeOf(db.*)); + return if (try R.list(try R.root(db), which)) |l| try l.count() else 0; + }, + } +} + +/// Keyframe `k` of `session`, with its stretch. +pub fn load(s: *Sessions, session: u64, k: u64) !Loaded { + switch (s.db) { + .off => return error.NotRecording, + inline .memory, .file => |*db| { + const R = Read(@TypeOf(db.*)); + const ses = try R.session(db, session); + const e = try R.at(try R.list(ses, .keys) orelse return error.NoSuchKeyframe, k); + const st = try R.uint(e, .stretch); + const stretch_entry = try R.at(try R.list(ses, .stretches) orelse return error.CorruptSession, st); + const why = std.enums.fromInt(Why, try R.uint(e, .why)) orelse return error.CorruptSession; + const pages = try R.list(e, .pages); + const state = if (pages) |list| try R.pages(list, try R.uint(e, .size), s.gpa) else if (try e.getCursor(key(.state))) |whole| try whole.readBytesAlloc(s.gpa, null) else return error.HistoryDropped; + errdefer s.gpa.free(state); + const line = try R.bytes(e, .line, s.gpa); + errdefer s.gpa.free(line); + const source = try R.bytes(stretch_entry, .source, s.gpa); + errdefer s.gpa.free(source); + return .{ + .paged = pages != null, + .frame = try R.uint(e, .frame), + .batch = try R.uint(e, .batch), + .why = why, + .time = try R.uint(e, .time), + .state = state, + .line = line, + .stretch = st, + .build = try R.uint(stretch_entry, .build), + .source = source, + .layout = try R.bytes(stretch_entry, .layout, s.gpa), + }; + }, + } +} + +/// The State a run starts from, the present: the newest keyframe of the +/// sessions before this one, with the frames logged after it appended to +/// `out` (replayed, they bring it to where that run stopped). Null in a +/// new database. This run's first keyframe starts from its pages. +pub fn present(s: *Sessions, out: *std.ArrayList(abi.Event)) !?Loaded { + if (s.db == .off) return null; + var i = s.session; + while (i > 0) { + i -= 1; + const sum = try s.summary(i); + if (sum.keys == 0) continue; + const newest = try s.load(i, sum.keys - 1); + errdefer newest.free(s.gpa); + try s.events(i, newest.batch, newest.frame, sum.frames, out); + if (newest.paged) { + const hashes = try s.gpa.alloc(u64, std.math.divCeil(usize, newest.state.len, page) catch unreachable); + for (hashes, 0..) |*h, j| h.* = std.hash.Wyhash.hash(0, newest.state[j * page .. @min(newest.state.len, (j + 1) * page)]); + s.gpa.free(s.hashes); + s.hashes = hashes; + s.last = .{ .session = i, .key = sum.keys - 1 }; + } + return newest; + } + return null; +} + +/// Keyframe `k`'s frame, time and why, without its bytes. +pub fn keyAt(s: *Sessions, session: u64, k: u64) !struct { frame: u64, time: u64, why: Why } { + switch (s.db) { + .off => return error.NotRecording, + inline .memory, .file => |*db| { + const R = Read(@TypeOf(db.*)); + const e = try R.at(try R.list(try R.session(db, session), .keys) orelse return error.NoSuchKeyframe, k); + return .{ .frame = try R.uint(e, .frame), .time = try R.uint(e, .time), .why = std.enums.fromInt(Why, try R.uint(e, .why)) orelse return error.CorruptSession }; + }, + } +} + +/// The newest keyframe of `session` whose `by` (`.frame` or `.time`) is at +/// most `value`: a binary search. +pub fn keyBefore(s: *Sessions, session: u64, by: K, value: u64) !?u64 { + switch (s.db) { + .off => return error.NotRecording, + inline .memory, .file => |*db| { + const R = Read(@TypeOf(db.*)); + const keys = try R.list(try R.session(db, session), .keys) orelse return null; + var lo: u64 = 0; + var hi = try keys.count(); + while (lo < hi) { + const mid = lo + (hi - lo) / 2; + if (try R.uint(try R.at(keys, mid), by) <= value) lo = mid + 1 else hi = mid; + } + return if (lo == 0) null else lo - 1; + }, + } +} + +/// Appends to `out` the events of frames `start..end` of `session`, read +/// from batch `from` on. +pub fn events(s: *Sessions, session: u64, from: u64, start: u64, end: u64, out: *std.ArrayList(abi.Event)) !void { + switch (s.db) { + .off => return error.NotRecording, + inline .memory, .file => |*db| { + const R = Read(@TypeOf(db.*)); + const batches = try R.list(try R.session(db, session), .batches) orelse return; + const n = try batches.count(); + var i = from; + while (i < n) : (i += 1) { + const cursor = try batches.getCursor(@intCast(i)) orelse return error.CorruptSession; + if ((try cursor.slot()).tag == .none) return error.HistoryDropped; + const blob = try cursor.readBytesAlloc(s.gpa, null); + defer s.gpa.free(blob); + if (blob.len < 8 or (blob.len - 8) % @sizeOf(abi.Event) != 0) return error.CorruptSession; + var f = std.mem.readInt(u64, blob[0..8], .little); + if (f >= end) return; + var at: usize = 8; + while (at < blob.len) : (at += @sizeOf(abi.Event)) { + var e: abi.Event = undefined; + @memcpy(std.mem.asBytes(&e), blob[at..][0..@sizeOf(abi.Event)]); + if (f >= start) try out.append(s.gpa, e); + if (e.kind == .tick) f += 1; + if (f >= end) return; + } + } + }, + } +} + +/// Session `i`'s summary. +pub const Summary = struct { + started: u64, + ended: u64, + frames: u64, + stretches: u64, + keys: u64, + /// Where it came from ("import <file name>"), cut short. + from_bytes: [48]u8 = undefined, + from_len: usize = 0, + + pub fn from(m: *const Summary) []const u8 { + return m.from_bytes[0..m.from_len]; + } +}; + +pub fn summary(s: *Sessions, i: u64) !Summary { + switch (s.db) { + .off => return error.NotRecording, + inline .memory, .file => |*db| { + const R = Read(@TypeOf(db.*)); + const ses = try R.session(db, i); + var m: Summary = .{ + .started = try R.uint(ses, .started), + .ended = try R.uint(ses, .ended), + .frames = try R.uint(ses, .frames), + .stretches = if (try R.list(ses, .stretches)) |l| try l.count() else 0, + .keys = if (try R.list(ses, .keys)) |l| try l.count() else 0, + }; + const from = try R.bytes(ses, .from, s.gpa); + defer s.gpa.free(from); + m.from_len = @min(from.len, m.from_bytes.len); + @memcpy(m.from_bytes[0..m.from_len], from[0..m.from_len]); + return m; + }, + } +} + +// --------------------------------------------------------------------------- +// Export and import + +/// Writes session `i`, with the marks and clips in it (now of session 0), to +/// a new database at `path` (written beside it, synced, then renamed): a +/// playtest's sessions to send, which `import` reads. +pub fn exportSession(s: *Sessions, i: u64, path: []const u8) !void { + if (s.db == .off) return error.NotRecording; + if (i == s.session) try s.commit(.none); + if (i >= try s.count(.sessions)) return error.NoSuchSession; + const cwd = std.Io.Dir.cwd(); + var buf: [std.fs.max_path_bytes + 8]u8 = undefined; + const tmp = try std.fmt.bufPrint(&buf, "{s}.tmp", .{path}); + const file = try cwd.createFile(s.io, tmp, .{ .read = true, .truncate = true }); + errdefer cwd.deleteFile(s.io, tmp) catch {}; + defer file.close(s.io); + var buffer: std.Io.Writer.Allocating = .init(s.gpa); + defer buffer.deinit(); + var out = try Disk.init(s.io, .{ .file = file, .buffer = &buffer, .fsync = true }); + switch (s.db) { + .off => unreachable, + inline .memory, .file => |*db| try out.runContext(Transfer(@TypeOf(db.*), Disk){ .gpa = s.gpa, .from = db, .only = i, .label = null }), + } + try cwd.rename(tmp, cwd, path, s.io); +} + +/// Appends the sessions of the database at `path` (an `exportSession`'s) to +/// this one, their `from` "import <file name>", with their marks and clips, +/// named `<name>@<file name>` (cut to `max_name`). Returns the first one's +/// index. +pub fn import(s: *Sessions, path: []const u8) !u64 { + if (s.db == .off) return error.NotRecording; + const file = try std.Io.Dir.cwd().openFile(s.io, path, .{}); + defer file.close(s.io); + if (try file.length(s.io) == 0) return error.NotASessionsDatabase; + var buffer: std.Io.Writer.Allocating = .init(s.gpa); + defer buffer.deinit(); + var in = try Disk.init(s.io, .{ .file = file, .buffer = &buffer, .fsync = false }); + const first = try s.count(.sessions); + switch (s.db) { + .off => unreachable, + inline .memory, .file => |*db| try db.runContext(Transfer(Disk, @TypeOf(db.*)){ .gpa = s.gpa, .from = &in, .only = null, .label = std.fs.path.basename(path) }), + } + return first; +} + +/// A transaction appending database `from`'s sessions (`only` one, else +/// all) to the one it runs in, with the marks and clips pointing into them; +/// `label`, an import's file name, goes in their `from` and names. +fn Transfer(comptime From: type, comptime To: type) type { + return struct { + gpa: std.mem.Allocator, + from: *From, + only: ?u64, + label: ?[]const u8, + + const R = Read(From); + const Map = To.HashMap(.read_write); + const List = To.ArrayList(.read_write); + + pub fn run(ctx: @This(), cursor: *To.Cursor(.read_write)) !void { + var copied: std.AutoHashMap(u64, xitdb.Slot) = .init(ctx.gpa); + defer copied.deinit(); + const src = try R.root(ctx.from); + if (try R.uint(src, .version) != 1) return error.NotASessionsDatabase; + const all = try R.list(src, .sessions) orelse return error.NotASessionsDatabase; + const root = try Map.init(cursor.*); + try root.put(key(.version), .{ .uint = 1 }); + const sessions = try List.init(try root.putCursor(key(.sessions))); + const base = try sessions.count(); + var buf: [std.fs.max_path_bytes + 8]u8 = undefined; + for (0..try all.count()) |i| { + if (ctx.only) |o| if (o != i) continue; + var to = try sessions.appendCursor(); + try copy(From, To, ctx.gpa, try all.getCursor(@intCast(i)) orelse return error.CorruptSession, &to, &copied); + if (ctx.label) |l| try (try Map.init(to)).put(key(.from), .{ .bytes = try std.fmt.bufPrint(&buf, "import {s}", .{l}) }); + } + for ([_]K{ .marks, .clips }) |which| { + const entries = try R.list(src, which) orelse continue; + const list = try List.init(try root.putCursor(key(which))); + var it = try entries.iterator(); + while (try it.next()) |e| { + const session = try R.uint(try R.Map.init(e), .session); + if (ctx.only) |o| if (o != session) continue; + var to = try list.appendCursor(); + try copy(From, To, ctx.gpa, e, &to, &copied); + const item = try Map.init(to); + try item.put(key(.session), .{ .uint = base + if (ctx.only == null) session else 0 }); + const l = ctx.label orelse continue; + var name: [max_name]u8 = undefined; + const old = (try R.field(try R.Map.init(e), .name)).readBytes(&name) catch return error.CorruptSession; + const new = std.fmt.bufPrint(&buf, "{s}@{s}", .{ old, l }) catch unreachable; + try item.put(key(.name), .{ .bytes = new[0..@min(new.len, max_name)] }); + } + } + } + }; +} + +/// Copies the value at `from` (a uint, bytes, or a list or map of them) to +/// `to`. Bytes `copied` already (a page keyframes share) are written once: +/// it maps their place in `from` to their slot in `to`. +fn copy(comptime From: type, comptime To: type, gpa: std.mem.Allocator, from: From.Cursor(.read_only), to: *To.Cursor(.read_write), copied: *std.AutoHashMap(u64, xitdb.Slot)) anyerror!void { + const slot = try from.slot(); + switch (slot.tag) { + .none => try to.write(.{ .slot = null }), + .uint => try to.write(.{ .uint = try from.readUint() }), + .bytes, .short_bytes => { + if (slot.tag == .bytes) if (copied.get(slot.value)) |done| return to.write(.{ .slot = done }); + const bytes = try from.readBytesAlloc(gpa, null); + defer gpa.free(bytes); + try to.write(.{ .bytes = bytes }); + if (slot.tag == .bytes) try copied.put(slot.value, try to.slot()); + }, + .array_list => { + const list = try To.ArrayList(.read_write).init(to.*); + var it = try from.iterator(); + while (try it.next()) |c| { + var next = try list.appendCursor(); + try copy(From, To, gpa, c, &next, copied); + } + }, + .hash_map => { + const map = try To.HashMap(.read_write).init(to.*); + var it = try from.iterator(); + while (try it.next()) |c| { + const kv = try c.readKeyValuePair(); + var next = try map.putCursor(kv.hash); + try copy(From, To, gpa, kv.value_cursor, &next, copied); + } + }, + else => return error.CorruptSession, + } +} + +fn Read(comptime DB: type) type { + return struct { + const Map = DB.HashMap(.read_only); + const List = DB.ArrayList(.read_only); + + fn root(db: *DB) !Map { + return Map.init(db.rootCursor().readOnly()); + } + fn session(db: *DB, i: u64) !Map { + return at(try list(try root(db), .sessions) orelse return error.NoSuchSession, i); + } + fn field(map: Map, k: K) !DB.Cursor(.read_only) { + return try map.getCursor(key(k)) orelse error.CorruptSession; + } + fn uint(map: Map, k: K) !u64 { + return (try field(map, k)).readUint(); + } + fn bytes(map: Map, k: K, gpa: std.mem.Allocator) ![]const u8 { + return (try field(map, k)).readBytesAlloc(gpa, null); + } + /// `size` bytes from a keyframe's pages, `gpa`'s. + fn pages(l: List, size: u64, gpa: std.mem.Allocator) ![]u8 { + const out = try gpa.alloc(u8, size); + errdefer gpa.free(out); + @memset(out, 0); + for (0..try l.count()) |i| { + const c = try l.getCursor(@intCast(i)) orelse continue; + if ((try c.slot()).tag == .none) continue; + const into = out[@min(size, i * page)..@min(size, (i + 1) * page)]; + if ((c.readBytes(into) catch return error.CorruptSession).len != into.len) return error.CorruptSession; + } + return out; + } + fn list(map: Map, k: K) !?List { + return try List.init(try map.getCursor(key(k)) orelse return null); + } + fn at(l: List, i: u64) !Map { + if (i >= try l.count()) return error.NoSuchEntry; + return Map.init(try l.getCursor(@intCast(i)) orelse return error.NoSuchEntry); + } + }; +} + +test "frames written to a session read back byte for byte, in memory and through a reopened file" { + const gpa = std.testing.allocator; + var tmp = std.testing.tmpDir(.{}); + defer tmp.cleanup(); + var buf: [std.fs.max_path_bytes]u8 = undefined; + const path = try std.fmt.bufPrint(&buf, ".zig-cache/tmp/{s}/t.xitdb", .{&tmp.sub_path}); + const layout = "a layout"; + for ([_]Mode{ .memory, .file }) |m| { + var s = try open(gpa, std.testing.io, m, path, .{ .build = 7, .source = "jj:abc", .layout = layout }, 1000); + var live: std.ArrayList(abi.Event) = .empty; + defer live.deinit(gpa); + // Three seconds at 60 Hz, a move in every third frame; the state is + // the frame count, so keyframes differ. + var state: u64 = 0; + for (0..180) |f| { + const t = std.time.ns_per_s + f * std.time.ns_per_s / 60; + var frame_events: [2]abi.Event = .{ .{ .kind = .mouse_move, .time = t, .x = @floatFromInt(f) }, abi.Event.tick(t, std.time.ns_per_s / 60) }; + const one = if (f % 3 == 0) frame_events[0..] else frame_events[1..]; + try s.frame(one, std.mem.asBytes(&state), if (f == 0) .start else if (f == 90) .jump else null); + try live.appendSlice(gpa, one); + state += 1; + } + // Two commits of a second each; the third second is pending. + try std.testing.expectEqual(@as(u64, 2), s.batches); + try s.commit(.none); + try std.testing.expectEqual(@as(u64, 2), s.keys); + var back: std.ArrayList(abi.Event) = .empty; + defer back.deinit(gpa); + try s.events(s.session, 0, 0, 180, &back); + try std.testing.expectEqualSlices(u8, std.mem.sliceAsBytes(live.items), std.mem.sliceAsBytes(back.items)); + // From the jump's keyframe: frame 90 on, its state 90. + const k = (try s.keyBefore(s.session, .frame, 100)).?; + try std.testing.expectEqual(@as(u64, 1), k); + const loaded = try s.load(s.session, k); + defer loaded.free(gpa); + try std.testing.expectEqual(@as(u64, 90), loaded.frame); + try std.testing.expectEqual(@as(u64, 90), std.mem.bytesToValue(u64, loaded.state)); + try std.testing.expectEqualStrings(layout, loaded.layout); + try std.testing.expectEqual(@as(u64, 7), loaded.build); + back.clearRetainingCapacity(); + try s.events(s.session, loaded.batch, 90, 92, &back); + try std.testing.expectEqualSlices(u8, std.mem.sliceAsBytes(live.items[120..][0..3]), std.mem.sliceAsBytes(back.items)); + try std.testing.expectEqual(@as(?u64, 0), try s.keyBefore(s.session, .frame, 0)); + if (m == .memory) { + s.deinit(); + continue; + } + s.close(std.mem.asBytes(&state), 2000); + // Reopened: the first session ended, its frames all there; a new one. + var again = try open(gpa, std.testing.io, .file, path, .{ .build = 8, .source = "", .layout = layout }, 3000); + defer again.deinit(); + try std.testing.expectEqual(@as(u64, 1), again.session); + const first = try again.summary(0); + try std.testing.expectEqual(@as(u64, 180), first.frames); + try std.testing.expectEqual(@as(u64, 2000), first.ended); + back.clearRetainingCapacity(); + try again.events(0, 0, 0, 180, &back); + try std.testing.expectEqualSlices(u8, std.mem.sliceAsBytes(live.items), std.mem.sliceAsBytes(back.items)); + } +} + +test "a session database torn inside its last commit opens at the one before, every earlier session and frame in it; one that cannot be mended is kept aside" { + const gpa = std.testing.allocator; + const io = std.testing.io; + var tmp = std.testing.tmpDir(.{}); + defer tmp.cleanup(); + var buf: [std.fs.max_path_bytes]u8 = undefined; + const path = try std.fmt.bufPrint(&buf, ".zig-cache/tmp/{s}/t.xitdb", .{&tmp.sub_path}); + const first: Stretch = .{ .build = 7, .source = "", .layout = "a layout" }; + var live: std.ArrayList(abi.Event) = .empty; + defer live.deinit(gpa); + var state: u64 = 0; + // Session 0: 120 frames, closed. Session 1: 180 frames in three commits + // of a second, then the process gone (no exit commit). + var before: u64 = 0; + var whole: u64 = 0; + for ([_]u64{ 120, 180 }, 0..) |frames, session| { + var s = try open(gpa, io, .file, path, first, 1000 + session); + for (0..frames) |f| { + const t = f * std.time.ns_per_s / 60; + var one = [_]abi.Event{abi.Event.tick(t, std.time.ns_per_s / 60)}; + try s.frame(&one, std.mem.asBytes(&state), if (f == 0) .start else null); + try live.appendSlice(gpa, &one); + state += 1; + } + if (session == 0) { + s.close(std.mem.asBytes(&state), 2000); + continue; + } + before = try s.file.?.length(io); + try s.commit(.none); + whole = try s.file.?.length(io); + s.deinit(); + } + const bytes = try tmp.dir.readFileAlloc(io, "t.xitdb", gpa, .unlimited); + defer gpa.free(bytes); + try std.testing.expectEqual(whole, bytes.len); + for ([_]u64{ before, before + 1, (before + whole) / 2, whole - trailer_len, whole - 10, whole - 1 }) |cut| { + errdefer std.debug.print("cut at {d} of {d}..{d}\n", .{ cut, before, whole }); + try tmp.dir.writeFile(io, .{ .sub_path = "t.xitdb", .data = bytes[0..cut] }); + var s = try open(gpa, io, .file, path, first, 3000); + defer s.deinit(); + try std.testing.expectEqual(@as(u64, 2), s.session); + const s0 = try s.summary(0); + try std.testing.expectEqual(@as(u64, 120), s0.frames); + try std.testing.expectEqual(@as(u64, 2000), s0.ended); + const s1 = try s.summary(1); + try std.testing.expectEqual(@as(u64, 120), s1.frames); + try std.testing.expectEqual(@as(u64, 0), s1.ended); + var back: std.ArrayList(abi.Event) = .empty; + defer back.deinit(gpa); + try s.events(0, 0, 0, 120, &back); + try s.events(1, 0, 0, 120, &back); + try std.testing.expectEqualSlices(u8, std.mem.sliceAsBytes(live.items[0..240]), std.mem.sliceAsBytes(back.items)); + var dir = try tmp.dir.openDir(io, ".", .{ .iterate = true }); + defer dir.close(io); + var it = dir.iterate(); + while (try it.next(io)) |e| try std.testing.expectEqualStrings("t.xitdb", e.name); + } + // Nothing whole to open at: kept aside as it was, a new database begun. + var torn = try gpa.dupe(u8, bytes); + defer gpa.free(torn); + @memset(torn[root_header_end..], 0); + try tmp.dir.writeFile(io, .{ .sub_path = "t.xitdb", .data = torn }); + var s = try open(gpa, io, .file, path, first, 4 * std.time.ns_per_s); + defer s.deinit(); + try std.testing.expectEqual(@as(u64, 0), s.session); + const aside = try tmp.dir.readFileAlloc(io, "t.xitdb.broken.4", gpa, .unlimited); + defer gpa.free(aside); + try std.testing.expectEqualSlices(u8, torn, aside); +} + +test "a compacted session database is smaller and holds every session and frame" { + const gpa = std.testing.allocator; + const io = std.testing.io; + var tmp = std.testing.tmpDir(.{}); + defer tmp.cleanup(); + var buf: [std.fs.max_path_bytes]u8 = undefined; + const path = try std.fmt.bufPrint(&buf, ".zig-cache/tmp/{s}/t.xitdb", .{&tmp.sub_path}); + const first: Stretch = .{ .build = 7, .source = "", .layout = "a layout" }; + var live: std.ArrayList(abi.Event) = .empty; + defer live.deinit(gpa); + var s = try open(gpa, io, .file, path, first, 1000); + var state: u64 = 0; + for (0..600) |f| { + const t = f * std.time.ns_per_s / 60; + var one = [_]abi.Event{abi.Event.tick(t, std.time.ns_per_s / 60)}; + try s.frame(&one, std.mem.asBytes(&state), if (f == 0) .start else if (f % 100 == 0) .jump else null); + try live.appendSlice(gpa, &one); + state += 1; + } + try s.commit(.none); + const size = try s.file.?.length(io); + const live_size = try liveSize(&s.db.file); + // Six keyframes of 8 bytes, the first all zeros: an empty page. + try std.testing.expectEqual(@as(u64, 600 * @sizeOf(abi.Event) + 10 * 8 + 5 * 8), live_size); + try s.compact(); + s.deinit(); + const compacted = (try tmp.dir.statFile(io, "t.xitdb", .{})).size; + try std.testing.expect(compacted < size); + var again = try open(gpa, io, .file, path, first, 2000); + defer again.deinit(); + try std.testing.expectEqual(@as(u64, 600), (try again.summary(0)).frames); + try std.testing.expectEqual(@as(u64, 6), (try again.summary(0)).keys); + var back: std.ArrayList(abi.Event) = .empty; + defer back.deinit(gpa); + try again.events(0, 0, 0, 600, &back); + try std.testing.expectEqualSlices(u8, std.mem.sliceAsBytes(live.items), std.mem.sliceAsBytes(back.items)); +} + +test "a memory session stops recording at its bound, and what it holds still reads" { + const gpa = std.testing.allocator; + var s = try open(gpa, std.testing.io, .memory, "", .{ .build = 7, .source = "", .layout = "a layout" }, 0); + defer s.deinit(); + s.db.memory.core.max_size = 64 << 10; + var live: std.ArrayList(abi.Event) = .empty; + defer live.deinit(gpa); + var state: u64 = 0; + var failed: usize = 0; + for (0..60 * 60) |f| { + const t = f * std.time.ns_per_s / 60; + var one = [_]abi.Event{abi.Event.tick(t, std.time.ns_per_s / 60)}; + s.frame(&one, std.mem.asBytes(&state), if (f == 0) .start else null) catch |err| { + try std.testing.expectEqual(error.WriteFailed, err); + failed += 1; + }; + try live.appendSlice(gpa, &one); + state += 1; + } + try std.testing.expectEqual(@as(usize, 1), failed); + const n = (try s.summary(s.session)).frames; + try std.testing.expect(n >= 60 and n < 60 * 60); + var back: std.ArrayList(abi.Event) = .empty; + defer back.deinit(gpa); + try s.events(s.session, 0, 0, n, &back); + try std.testing.expectEqualSlices(u8, std.mem.sliceAsBytes(live.items[0..n]), std.mem.sliceAsBytes(back.items)); +} + +test "a session's keyframes write only the pages that changed: a State of megabytes edited each minute, and one never changed" { + const gpa = std.testing.allocator; + const io = std.testing.io; + var tmp = std.testing.tmpDir(.{}); + defer tmp.cleanup(); + var buf: [std.fs.max_path_bytes]u8 = undefined; + const path = try std.fmt.bufPrint(&buf, ".zig-cache/tmp/{s}/t.xitdb", .{&tmp.sub_path}); + // 4 MiB, every page holding something, one u64 edited a minute. + const state = try gpa.alloc(u8, 4 << 20); + defer gpa.free(state); + for (state, 0..) |*b, i| b.* = @truncate(i *% 7 + 1); + var s = try open(gpa, io, .file, path, .{ .build = 7, .source = "", .layout = "a layout" }, 1000); + defer s.deinit(); + const minutes = 10; + var sizes: [minutes + 1]u64 = undefined; + for (0..minutes * 60 * 60) |f| { + const t = f * std.time.ns_per_s / 60; + var one = [_]abi.Event{abi.Event.tick(t, std.time.ns_per_s / 60)}; + if (f % 3600 == 1800) std.mem.writeInt(u64, state[(f / 3600) * 300_000 ..][0..8], f, .little); + try s.frame(&one, state, if (f == 0) .start else null); + if (f % 3600 == 0) { + try s.commit(.none); + sizes[f / 3600] = try s.file.?.length(io); + } + } + try s.commit(.none); + sizes[minutes] = try s.file.?.length(io); + // One keyframe a minute: at 0 s, 60 s, ... + try std.testing.expectEqual(@as(u64, minutes), s.keys); + // A minute is 216,000 bytes of ticks and a keyframe of one page with + // its copied path: under 230 KB a minute, where a whole State a + // keyframe was 4 MiB. + for (1..minutes) |m| try std.testing.expect(sizes[m + 1] - sizes[m] < 230_000); + // Every keyframe reads back whole: the edits made before it, and none after. + const want = try gpa.alloc(u8, state.len); + defer gpa.free(want); + for (0..minutes) |k| { + for (want, 0..) |*b, i| b.* = @truncate(i *% 7 + 1); + for (0..k) |m| std.mem.writeInt(u64, want[m * 300_000 ..][0..8], m * 3600 + 1800, .little); + const loaded = try s.load(s.session, k); + defer loaded.free(gpa); + try std.testing.expectEqual(@as(u64, k * 3600), loaded.frame); + try std.testing.expectEqualSlices(u8, want, loaded.state); + } + // A keyframe alone, in a commit of its own: one changed page is that + // page, its copied path and the keyframe's fields; no changed page (one + // kept before a reload) is the fields alone. + for ([_]bool{ true, false }) |edit| { + if (edit) state[123] +%= 1; + const before = try s.file.?.length(io); + _ = try s.keyframe(if (edit) .jump else .before_reload, state); + try s.commit(.none); + try std.testing.expect(try s.file.?.length(io) - before < @as(u64, if (edit) 12 << 10 else 8 << 10)); + } + const last = try s.load(s.session, s.keys - 1); + defer last.free(gpa); + try std.testing.expectEqualSlices(u8, state, last.state); +} + +test "an exported session keeps its keyframes' shared pages shared" { + const gpa = std.testing.allocator; + const io = std.testing.io; + var tmp = std.testing.tmpDir(.{}); + defer tmp.cleanup(); + var buf: [std.fs.max_path_bytes]u8 = undefined; + const path = try std.fmt.bufPrint(&buf, ".zig-cache/tmp/{s}/t.xitdb", .{&tmp.sub_path}); + var out_buf: [std.fs.max_path_bytes]u8 = undefined; + const out = try std.fmt.bufPrint(&out_buf, ".zig-cache/tmp/{s}/one.xitdb", .{&tmp.sub_path}); + const state = try gpa.alloc(u8, 1 << 20); + defer gpa.free(state); + for (state, 0..) |*b, i| b.* = @truncate(i *% 13 + 1); + var s = try open(gpa, io, .file, path, .{ .build = 7, .source = "", .layout = "a layout" }, 1000); + defer s.deinit(); + // Ten keyframes a byte apart. + for (0..600) |f| { + const t = f * std.time.ns_per_s / 60; + var one = [_]abi.Event{abi.Event.tick(t, std.time.ns_per_s / 60)}; + if (f % 60 == 0) state[f * 100] +%= 1; + try s.frame(&one, state, if (f == 0) .start else if (f % 60 == 0) .jump else null); + } + try s.exportSession(0, out); + const size = (try std.Io.Dir.cwd().statFile(io, out, .{})).size; + // One State and nine pages, not ten States. + try std.testing.expect(size < state.len + state.len / 8); + var again = try open(gpa, io, .file, out, .{ .build = 7, .source = "", .layout = "a layout" }, 2000); + defer again.deinit(); + const loaded = try again.load(0, 9); + defer loaded.free(gpa); + try std.testing.expectEqualSlices(u8, state, loaded.state); +} + +test "a session database past max_save drops its oldest history: the present and the marks stay, the file under it" { + const gpa = std.testing.allocator; + const io = std.testing.io; + var tmp = std.testing.tmpDir(.{}); + defer tmp.cleanup(); + var buf: [std.fs.max_path_bytes]u8 = undefined; + const path = try std.fmt.bufPrint(&buf, ".zig-cache/tmp/{s}/t.xitdb", .{&tmp.sub_path}); + // 2 MiB of State, its first half rewritten each second: a keyframe + // writes 1 MiB, so the cap is reached at about the 60th. + const state = try gpa.alloc(u8, 2 << 20); + defer gpa.free(state); + @memset(state, 1); + var s = try open(gpa, io, .file, path, .{ .build = 7, .source = "", .layout = "a layout" }, 1000); + defer s.deinit(); + for (0..100) |k| { + @memset(state[0 .. 1 << 20], @truncate(k + 2)); + var one = [_]abi.Event{abi.Event.tick(k * std.time.ns_per_s, std.time.ns_per_s)}; + try s.frame(&one, state, if (k == 0) .start else .jump); + if (k == 5) _ = try s.mark("a", .mark, state); + if (k == 20) _ = try s.mark("b", .mark, state); + try std.testing.expect(try s.file.?.length(io) <= max_save); + } + try s.commit(.none); + // The oldest keyframes and frames are gone; the marks and the newest + // keyframe read back whole. + try std.testing.expectError(error.HistoryDropped, s.load(0, 1)); + var log: std.ArrayList(abi.Event) = .empty; + defer log.deinit(gpa); + try std.testing.expectError(error.HistoryDropped, s.events(0, 0, 0, 2, &log)); + for ([_]struct { []const u8, u8 }{ .{ "a", 7 }, .{ "b", 22 } }) |want| { + const m = (try s.findMark(want[0])).?; + const loaded = try s.load(m.session, m.key); + defer loaded.free(gpa); + try std.testing.expectEqual(want[1], loaded.state[0]); + try std.testing.expectEqual(@as(u8, 1), loaded.state[1 << 20]); + } + const newest = try s.load(0, s.keys - 1); + defer newest.free(gpa); + try std.testing.expectEqualSlices(u8, state, newest.state); + try s.events(0, newest.batch, newest.frame, s.frames, &log); +} + +test "a session database without history keeps the present and the marks, and leaves nothing else at exit" { + const gpa = std.testing.allocator; + const io = std.testing.io; + var tmp = std.testing.tmpDir(.{}); + defer tmp.cleanup(); + var buf: [std.fs.max_path_bytes]u8 = undefined; + const path = try std.fmt.bufPrint(&buf, ".zig-cache/tmp/{s}/t.xitdb", .{&tmp.sub_path}); + var state: [64 << 10]u8 = @splat(1); + var s = try open(gpa, io, .file, path, .{ .build = 7, .source = "", .layout = "a layout" }, 1000); + s.history = false; + for (0..20) |k| { + @memset(state[0 .. 32 << 10], @truncate(k + 2)); + var one = [_]abi.Event{abi.Event.tick(k * std.time.ns_per_s, std.time.ns_per_s)}; + try s.frame(&one, &state, if (k == 0) .start else .jump); + if (k == 3) _ = try s.mark("a", .mark, &state); + } + try s.commit(.none); + try std.testing.expectError(error.HistoryDropped, s.load(0, 1)); + const m = (try s.findMark("a")).?; + const loaded = try s.load(m.session, m.key); + loaded.free(gpa); + s.close(&state, 2000); + // At exit: compacted to the present, the mark and the session's fields. + try std.testing.expect((try tmp.dir.statFile(io, "t.xitdb", .{})).size < 3 * state.len); + var again = try open(gpa, io, .file, path, .{ .build = 7, .source = "", .layout = "a layout" }, 3000); + defer again.deinit(); + var log: std.ArrayList(abi.Event) = .empty; + defer log.deinit(gpa); + const now = (try again.present(&log)).?; + defer now.free(gpa); + try std.testing.expectEqualSlices(u8, &state, now.state); +} + +test "a session database full of marks refuses a mark of a new name, and takes one over an old name" { + const gpa = std.testing.allocator; + const io = std.testing.io; + var tmp = std.testing.tmpDir(.{}); + defer tmp.cleanup(); + var buf: [std.fs.max_path_bytes]u8 = undefined; + const path = try std.fmt.bufPrint(&buf, ".zig-cache/tmp/{s}/t.xitdb", .{&tmp.sub_path}); + // 2 MiB of State, all of it changed for each mark. + const state = try gpa.alloc(u8, 2 << 20); + defer gpa.free(state); + var s = try open(gpa, io, .file, path, .{ .build = 7, .source = "", .layout = "a layout" }, 1000); + defer s.deinit(); + var name: [8]u8 = undefined; + var k: u8 = 0; + while (true) : (k += 1) { + @memset(state, k + 1); + _ = s.mark(try std.fmt.bufPrint(&name, "m{d}", .{k}), .mark, state) catch |err| { + try std.testing.expectEqual(error.SaveFull, err); + break; + }; + try std.testing.expect(k < 40 and try s.file.?.length(io) <= max_save); + } + try std.testing.expect(k > 20); + @memset(state, 99); + try std.testing.expectError(error.SaveFull, s.mark("new", .mark, state)); + _ = try s.mark("m3", .mark, state); + try s.commit(.none); + try std.testing.expect(try s.file.?.length(io) <= max_save); + // Every mark's newest keyframe is whole. + for (0..k) |i| { + const m = (try s.findMark(try std.fmt.bufPrint(&name, "m{d}", .{i}))).?; + const loaded = try s.load(m.session, m.key); + defer loaded.free(gpa); + try std.testing.expectEqual(@as(u8, if (i == 3) 99 else @intCast(i + 1)), loaded.state[state.len - 1]); + } +} |
