From 05826d5148b8d75c32397380b9f64e0b3477e5bb Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Fri, 30 Oct 2026 16:16:25 -0300 Subject: replica: pardes's own steps over a terminal speculated, not every input while one has the keyboard (H14): what reaches its program is a pty write and stops as before; its view (normal-mode keys, the wheel, Ctrl-u) moves here at once, the rollback copy keeping each terminal's view (it holds no emulator) and a delta setting it, put back between the units it replays in the order the deltas came among them; what was applied over a terminal applied again over each delta or rows that come while it waits, and its unit taken at once rather than kept to replay over later deltas; closing a terminal stops (its pty's end is the authority's) Co-Authored-By: Claude Opus 5.5 --- src/replica.zig | 231 +++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 220 insertions(+), 11 deletions(-) (limited to 'src/replica.zig') diff --git a/src/replica.zig b/src/replica.zig index a88873ac..b4c3de8c 100644 --- a/src/replica.zig +++ b/src/replica.zig @@ -513,7 +513,15 @@ pub const Stats = struct { } }; -const Pending = struct { seq: u32, msg: []u8, spec: ?[]u8 = null, sent_ns: u64 = 0 }; +/// `terminal`: its speculation read a terminal or moved one's view (or a +/// terminal had the keyboard), so what it did depends on the emulator, and +/// `digest` is the state it ended on: the same records are not enough. +const Pending = struct { seq: u32, msg: []u8, spec: ?[]u8 = null, sent_ns: u64 = 0, terminal: bool = false, digest: u64 = 0 }; + +/// A terminal's view as the authority's was once `after` of the units +/// since the copy were taken (`Replica.since`): a delta's comes after the +/// units it shows, so those before it are not replayed over it. +const View = struct { at: ?usize = null, after: usize = 0 }; pub const Replica = struct { gpa: Allocator, @@ -562,6 +570,10 @@ pub const Replica = struct { /// Its terminals' screen state, as the authority's deltas made it. screens: [pardes.MAX_PANES]?ScreenOf = @splat(null), + /// Each terminal's view (`terminal.viewOf`) as the copy was taken, or + /// as the last delta since set it: the copy holds no emulator, and a + /// speculation may move a view, so a rollback puts these back. + views: [pardes.MAX_PANES]View = @splat(.{}), screen_out: std.ArrayListUnmanaged(u8) = .empty, /// Its predicted echo (src/echo.zig), drawn over its core's terminals: /// fed by its keys, its units and its deltas here, and by `echoFrame`. @@ -714,9 +726,24 @@ pub const Replica = struct { const was = Stepping.begin(&r.t, &r.epoch); defer was.end(); if (u.origin == r.id and r.pending.items.len > 0 and r.pending.items[0].seq == u.seq and r.applied > 0 and - tape.sameRecords(r.pending.items[0].spec.?, u.tape)) + tape.sameRecords(r.pending.items[0].spec.?, u.tape) and endsOn(r.pending.items[0], u.tape)) { r.stats.fast += 1; + if (r.pending.items[0].terminal and r.applied > 1) { + // Right, but what it did read a terminal: replayed later (a + // rollback's `since`) it would read the deltas that came + // after it. So it is taken now, over the emulator its step + // read, and the ones on top applied again over it. + r.toConfirmed(); + if (tape.replayUnit(&r.t, u.tape)) |why| return r.fail(why); + if (lastDigest(u.tape)) |d| { + r.last_digest.clearRetainingCapacity(); + r.last_digest.appendSlice(r.gpa, d) catch {}; + } + r.freePending(r.pending.orderedRemove(0)); + r.dirty = true; + return; + } r.freePending(r.pending.orderedRemove(0)); r.applied -= 1; if (r.applied == 0) { @@ -816,7 +843,8 @@ pub const Replica = struct { /// Back to the confirmed position: the copy put back, the units fast- /// pathed since replayed. fn toConfirmed(r: *Replica) void { - if (r.copy.held) { + const held = r.copy.held; + if (held) { r.copy.restore(); rollback.Epoch.select(null); // The rows a terminal was read as are no copy's: what the @@ -826,7 +854,13 @@ pub const Replica = struct { r.core().shell_rows = .{}; } r.applied = 0; - for (r.since.items) |u| if (tape.replayUnit(&r.t, u)) |why| return r.fail(why); + // Its views as the copy was taken, or as a delta set them between + // the units since (which may move them again). + for (r.since.items, 0..) |u, i| { + if (held) r.putViews(i); + if (tape.replayUnit(&r.t, u)) |why| return r.fail(why); + } + if (held) r.putViews(r.since.items.len); r.clearSince(); for (r.pending.items) |*p| if (p.spec) |s| { r.gpa.free(s); @@ -860,6 +894,7 @@ pub const Replica = struct { // A grid's worth of text the copy would save, and put back stale. c.shell_rows.reset(c.gpa); r.copy.take(&r.epoch, c) catch return false; + r.keepViews(); rollback.Epoch.select(&r.epoch); r.stats.copy_ns.append(r.gpa, nowNs() - t0) catch {}; r.stats.copy_bytes += r.copy.savedBytes(); @@ -874,13 +909,23 @@ pub const Replica = struct { break :guess .{ .real_ns = r.stamp.real_ns + since, .mono_ns = r.stamp.mono_ns + since, .gmtoff = r.gmtoff }; } else null; c.toView(r.view); - // Input into a terminal is the authority's: its step reads the - // emulator (rows, cursor, modes), which here is the last delta's and - // there what the pty has said since. It waits; phase 6 predicts the - // echo. - if (r.t.screen_state) if (c.panes[c.active]) |pane| if (pane.isTerminal()) tape.poison("a terminal has the keyboard"); + // Input into a terminal: what reaches its program (a key in tty + // mode, a paste, a mouse report) is a pty write, the authority's, + // and stops here (phase 6 predicts its echo). The rest (pardes's + // own keys over it, the wheel) reads its emulator, here the last + // delta's and there what the pty has said since: it is applied, + // and applied again over each delta while it waits (`screen`), so + // what the authority's unit confirms read the emulator its step + // read (the deltas come before it). + const keyboard = if (c.panes[c.active]) |pane| pane.terminal != null else false; c.update(in.event); c.step(); + p.terminal = r.t.screen_state and (keyboard or r.t.touched); + // A delta the authority's step read and this did not (one held + // back at the bound in flight) would leave the same records and + // another state: its digest says (no emulator's in it, only what + // pardes made of one). + if (p.terminal) p.digest = tape.digestOf(c); const clean = tape.endSpeculation(&r.t); const dt = nowNs() - t0; // Where a blob was written, should one be: the input that did. @@ -904,7 +949,10 @@ pub const Replica = struct { if (checked) { var after: [pardes.MAX_PANES]u64 = undefined; terminalDigests(c, &after); - if (!std.mem.eql(u64, &terminals, &after)) @panic("replica: a speculation wrote a terminal's emulator"); + if (!std.mem.eql(u64, &terminals, &after)) { + for (terminals, after, 0..) |x, y, id| if (x != y) std.debug.print("replica {d}: its input {d} ({any}) wrote terminal {d}\n", .{ r.id, p.seq, in.event, id }); + @panic("replica: a speculation wrote a terminal's emulator"); + } } r.stats.speculated += 1; r.stats.spec_ns.append(r.gpa, dt) catch {}; @@ -941,11 +989,22 @@ pub const Replica = struct { rollback.Epoch.select(&r.epoch); defer rollback.Epoch.select(null); r.copy.take(&r.epoch, c) catch return; + r.keepViews(); r.stats.copy_ns.append(r.gpa, nowNs() - t0) catch {}; r.stats.copy_bytes += r.copy.savedBytes(); r.stats.copies += 1; } + fn keepViews(r: *Replica) void { + if (!r.t.screen_state) return; + for (r.core().panes, &r.views) |slot, *v| v.* = .{ .at = if (slot) |pane| terminal.viewOf(pane) else null }; + } + + fn putViews(r: *Replica, after: usize) void { + if (!r.t.screen_state) return; + for (r.core().panes, r.views) |slot, v| if (v.after == after) if (slot) |pane| if (pane.terminal != null) terminal.viewTo(pane, v.at); + } + /// Whether its core loaded from the dump is the session as it was /// dumped, by the welcome's `digest`. pub fn loaded(r: *Replica, want: u64) bool { @@ -1006,6 +1065,10 @@ pub const Replica = struct { r.echo.delta(c, m.pane, sc.rep.top); // Its rows as the core keeps them read are another grid's. c.shell_rows.markStale(pane); + // Its view is the authority's now: a rollback puts it back + // here, and what was applied over a terminal goes on top. + if (r.copy.held) r.views[m.pane] = .{ .at = terminal.viewOf(pane), .after = r.since.items.len }; + r.overTerminals(); var seq: [4]u8 = undefined; std.mem.writeInt(u32, &seq, applied.seq, .little); return r.screenMessage(m.pane, m.serial, kind_ack, &seq); @@ -1014,12 +1077,28 @@ pub const Replica = struct { sc.asked = null; sc.rep.applyRows(state.gpa, &state.vt, m.payload) catch r.fail("a terminal's rows did not apply"); c.shell_rows.markStale(pane); + r.overTerminals(); return null; }, else => return null, } } + /// A terminal was written (a delta, rows): what is applied over the + /// emulator (`Pending.terminal`) read the one before it, and the + /// authority's step reads this one (it comes before that step's unit). + /// Back to the confirmed position, to be applied again over it. + fn overTerminals(r: *Replica) void { + const any = for (r.pending.items[0..r.applied]) |p| { + if (p.terminal) break true; + } else false; + if (!any) return; + const was = Stepping.begin(&r.t, &r.epoch); + defer was.end(); + r.toConfirmed(); + r.dirty = true; + } + /// A request for the rows a terminal shows here and does not hold (its /// holes in view, after a scroll back), one a terminal at a time; null /// when none is owed. Until the answer, a hole shows blank. @@ -1061,6 +1140,25 @@ pub const Replica = struct { } }; +/// Whether a unit ends where speculation `p` did: always, but for one over +/// a terminal, whose digest must be the unit's last (a word, the stream's; +/// a unit of a traced session, a field a word, is taken on its records). +fn endsOn(p: Pending, unit: []const u8) bool { + if (!p.terminal) return true; + var r: walk.Reader = .{ .bytes = unit }; + var last: ?[]const u8 = null; + while (true) { + const head = r.take(5) catch break; + const payload = r.take(std.mem.bytesToValue(u32, head[1..5])) catch break; + if (head[0] == tape.digest_kind) last = payload; + } + var in: walk.Reader = .{ .bytes = last orelse return true }; + var room: [64]u8 = undefined; + var fixed: std.heap.FixedBufferAllocator = .init(&room); + const words = walk.decode([]const u64, &in, fixed.allocator()) catch return true; + return words.len != 1 or words[0] == p.digest; +} + /// The bytes of a unit's last digest record: the state it ended on; null /// for one that says what the host wrote or which host it is (a replica's /// core takes those only by replaying the unit). @@ -1081,7 +1179,8 @@ fn terminalDigests(p: *const Pardes, out: *[pardes.MAX_PANES]u64) void { const pane = slot orelse continue; const state = pane.terminal orelse continue; var h = walk.Hasher.init(0); - state.digestScreen(&h); + // Its view aside: a speculation may move it (`views`). + state.digestScreen(&h, false); d.* = h.final(); } } @@ -3250,6 +3349,116 @@ test "a terminal sized again by a client's key: the step reads the grid it had, try std.testing.expectEqual(digestOf(a), r.digest()); } +fn deliver(a: *Authority, screens: *Screens, peer: u16, r: *Replica, comptime what: enum { flush, fill }) !void { + const gpa = std.testing.allocator; + var msgs: std.ArrayListUnmanaged([]u8) = .empty; + defer { + for (msgs.items) |m| gpa.free(m); + msgs.deinit(gpa); + } + switch (what) { + .flush => try screens.flush(a.core, peer, &msgs), + .fill => { + try screens.fill(a.core, peer, &msgs); + screens.filled(a.core); + }, + } + for (msgs.items) |m| if (r.screen(m)) |reply| { + _ = try screens.take(a.core, peer, reply); + }; +} + +test "pardes's own keys over a terminal's history apply at once: its view moves here, a delta while they wait puts them on top again, the authority's ends the same" { + if (comptime !terminal.enabled) return error.SkipZigTest; + const gpa = std.testing.allocator; + const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .boot = .tty }, TestHost.host(), true); + defer a.deinit(); + var screens: Screens = .init(gpa); + defer screens.deinit(a.core); + const peer = try screens.addPeer(); + const r = try Replica.init(gpa, 1, try a.unit(0, 0), true); + defer r.deinit(); + const shell: u8 = for (a.core.panes, 0..) |slot, id| { + if (slot) |pane| if (pane.isTerminal()) break @intCast(id); + } else return error.NoShell; + a.core.active = shell; + r.confirm(try a.local(.{ .focus = true })); + var line: [64]u8 = undefined; + for (0..200) |i| a.output(.{ .output = .{ .pane = shell, .bytes = try std.fmt.bufPrint(&line, "history line {d}\r\n", .{i}) } }); + r.confirm((try a.pending()).?); + try deliver(a, &screens, peer, r, .flush); + r.settle(); + var sent: std.ArrayListUnmanaged([]u8) = .empty; + defer { + for (sent.items) |m| gpa.free(m); + sent.deinit(gpa); + } + // Normal mode in the shell, up a few rows, then half a screen and more: + // the cursor leaves the view, and the view follows it back. + const keys = [_]pardes.Key{ + .{ .cp = a.core.opts.tty_toggle, .ctrl = true }, .{ .cp = 'k', .text = "k" }, .{ .cp = 'k', .text = "k" }, + .{ .cp = 'u', .ctrl = true }, .{ .cp = 'u', .ctrl = true }, .{ .cp = 'k', .text = "k" }, + }; + for (keys) |k| try sent.append(gpa, try gpa.dupe(u8, try r.input(.{ .key = k }))); + try std.testing.expectEqual(@as(u32, 0), r.stats.stopped); + try std.testing.expectEqual(sent.items.len, r.applied); + const here = r.core().panes[shell].?; + try std.testing.expect(terminal.viewOf(here) != null); + const scrolled = terminal.viewOf(here); + // The shell prints while they wait: its unit, then its delta, which + // sets the view the authority's (at the bottom still): what was applied + // goes on top of it again. + for (0..5) |i| a.output(.{ .output = .{ .pane = shell, .bytes = try std.fmt.bufPrint(&line, "late line {d}\r\n", .{i}) } }); + r.confirm((try a.pending()).?); + r.settle(); + try deliver(a, &screens, peer, r, .flush); + r.settle(); + try std.testing.expectEqual(sent.items.len, r.applied); + try std.testing.expect(terminal.viewOf(r.core().panes[shell].?) != null); + // The authority takes them in order, the terminal sent before each and + // the rows its step read after, as the session's loop does. + for (sent.items) |m| { + try deliver(a, &screens, peer, r, .flush); + r.settle(); + const u = try gpa.dupe(u8, try a.take(m)); + defer gpa.free(u); + try deliver(a, &screens, peer, r, .fill); + r.confirm(u); + r.settle(); + } + try deliver(a, &screens, peer, r, .flush); + r.settle(); + if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why}); + try std.testing.expect(r.diverged == null and r.quiet()); + try std.testing.expectEqual(@as(u32, 0), r.stats.mispredicted); + try std.testing.expectEqual(digestOf(a), r.digest()); + try std.testing.expect(terminal.viewOf(a.core.panes[shell].?) != null); + try std.testing.expectEqual(terminal.viewOf(a.core.panes[shell].?), terminal.viewOf(r.core().panes[shell].?)); + _ = scrolled; + // A rollback with nothing confirmed on top puts the view back: one more + // key up, and another's unit first. + try sent.append(gpa, try gpa.dupe(u8, try r.input(.{ .key = .{ .cp = 'u', .ctrl = true } }))); + const before = terminal.viewOf(a.core.panes[shell].?); + try std.testing.expect(terminal.viewOf(r.core().panes[shell].?).? < before.?); + r.confirm(try a.local(.{ .focus = false })); + r.settle(); + const last = try gpa.dupe(u8, try a.take(sent.items[sent.items.len - 1])); + defer gpa.free(last); + r.toConfirmed(); + try std.testing.expectEqual(before, terminal.viewOf(r.core().panes[shell].?)); + r.dirty = true; + r.settle(); + try deliver(a, &screens, peer, r, .fill); + r.confirm(last); + r.settle(); + try deliver(a, &screens, peer, r, .flush); + r.settle(); + if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why}); + try std.testing.expect(r.diverged == null and r.quiet()); + try std.testing.expectEqual(digestOf(a), r.digest()); + try std.testing.expectEqual(terminal.viewOf(a.core.panes[shell].?), terminal.viewOf(r.core().panes[shell].?)); +} + /// p50 and p99 of `samples`, sorted in place. fn spread(samples: []u64) [2]u64 { std.mem.sort(u64, samples, {}, std.sort.asc(u64)); -- cgit v1.3