summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/replica.zig291
-rw-r--r--src/rollback.zig12
-rw-r--r--src/screen_state.zig680
-rw-r--r--src/tape.zig53
-rw-r--r--src/terminal.zig57
5 files changed, 861 insertions, 232 deletions
diff --git a/src/replica.zig b/src/replica.zig
index 42d94503..e229bad5 100644
--- a/src/replica.zig
+++ b/src/replica.zig
@@ -28,6 +28,8 @@ const tape = @import("tape.zig");
const rollback = @import("rollback.zig");
const walk = @import("walk.zig");
const wire = @import("detached/wire.zig");
+const screen_state = @import("screen_state.zig");
+const terminal = pardes.panes.terminal;
const Allocator = std.mem.Allocator;
const Pardes = pardes.Pardes;
@@ -97,10 +99,15 @@ pub const Authority = struct {
/// Each client's view (src/views.zig): its own layout, focus and
/// cursors over the session's text. The first client has the session's.
view_of: [64]u8 = @splat(0),
+ /// Steps of its own taken since the last unit (`output`): one unit,
+ /// `pending`, sent before the next input it steps and at a frame.
+ batched: u32 = 0,
/// A session booted with `opts`; `unit` is its first, which a replica
/// is made from.
- pub fn init(gpa: Allocator, options: pardes.Options, host: pardes.Host) !*Authority {
+ /// `screens`: its terminals cross as screen state (`Screens`), not as
+ /// their pty's bytes.
+ pub fn init(gpa: Allocator, options: pardes.Options, host: pardes.Host, screens: bool) !*Authority {
// A replay gives its core every allocator (tape.zig), and a digest
// tells an allocator from none.
var opts = options;
@@ -111,6 +118,9 @@ pub const Authority = struct {
const a = try gpa.create(Authority);
errdefer gpa.destroy(a);
a.* = .{ .gpa = gpa, .t = tape.memory(gpa), .core = undefined, .host = host };
+ a.t.screen_state = screens;
+ // One word a digest: every pty read is a unit.
+ a.t.whole_digest = screens and std.c.getenv("PARDES_REPLICA_TRACE") == null;
const was = Stepping.begin(&a.t, null);
defer was.end();
a.core = try Pardes.init(gpa, opts);
@@ -150,13 +160,38 @@ pub const Authority = struct {
/// One of the authority's own inputs, as its unit.
pub fn local(a: *Authority, ev: pardes.Event) ![]const u8 {
+ std.debug.assert(a.batched == 0); // `pending` first: units keep the order steps took
a.apply(ev);
a.seq += 1;
return a.unit(0, a.seq);
}
+ /// A step of its own (a pty's output) into the open batch: under a
+ /// flood a replica gets a unit a frame, not one a read (each unit of the
+ /// authority's rolls back a replica's pending inputs), and its digest
+ /// once a unit.
+ pub fn output(a: *Authority, ev: pardes.Event) void {
+ a.t.no_digest = true;
+ defer a.t.no_digest = false;
+ a.apply(ev);
+ a.batched += 1;
+ }
+
+ /// The open batch as a unit, or null: what the host sends before it
+ /// steps any other input, and once a frame.
+ pub fn pending(a: *Authority) !?[]const u8 {
+ if (a.batched == 0) return null;
+ a.batched = 0;
+ const was = Stepping.begin(&a.t, null);
+ tape.digestHere(&a.t);
+ was.end();
+ a.seq += 1;
+ return try a.unit(0, a.seq);
+ }
+
/// A view of its own for `client`, as its unit; which it is.
pub fn openView(a: *Authority, client: u16) !struct { view: u8, unit: []const u8 } {
+ std.debug.assert(a.batched == 0);
const was = Stepping.begin(&a.t, null);
const k = a.core.openView() orelse {
was.end();
@@ -172,6 +207,7 @@ pub const Authority = struct {
/// One client's input, applied in the order it came, in its view: the
/// unit every replica takes.
pub fn take(a: *Authority, msg: []const u8) ![]const u8 {
+ std.debug.assert(a.batched == 0);
const in = parseInput(msg) orelse return error.BadInput;
const was = Stepping.begin(&a.t, null);
a.core.toView(a.view_of[in.client]);
@@ -182,6 +218,140 @@ pub const Authority = struct {
}
};
+// ---- terminals as screen state (src/screen_state.zig) ----
+//
+// A message of either side is u8 pane, u32 the pane's serial (a slot's
+// next pane is another), u8 kind, and the kind's bytes:
+// to a replica: kind 1, a delta; kind 2, rows it asked for (encodeRows);
+// to the authority: kind 1, an acknowledgement (u32 seq); kind 2, a
+// request for rows (u64 lo, u64 hi, absolute); kind 3, a
+// delta refused: start this terminal afresh.
+// The authority sends a peer what it is owed (`Screens.flush`) before it
+// steps any input but a pty's output, and once a frame; a replica takes
+// them in that order between units (`Replica.screen`). So a step a replica
+// replays reads the terminal its authority's read.
+
+const kind_delta = 1;
+const kind_rows = 2;
+const kind_ack = 1;
+const kind_reset = 3;
+
+const ScreenMsg = struct { pane: u8, serial: u32, kind: u8, payload: []const u8 };
+
+fn parseScreen(msg: []const u8) ?ScreenMsg {
+ if (msg.len < 6) return null;
+ return .{ .pane = msg[0], .serial = std.mem.readInt(u32, msg[1..5], .little), .kind = msg[5], .payload = msg[6..] };
+}
+
+fn writeScreenHead(out: *std.ArrayListUnmanaged(u8), gpa: Allocator, pane: u8, serial: u32, kind: u8) !void {
+ var head: [6]u8 = undefined;
+ head[0] = pane;
+ std.mem.writeInt(u32, head[1..5], serial, .little);
+ head[5] = kind;
+ try out.appendSlice(gpa, &head);
+}
+
+/// The authority's side of its replicas' terminals: a track each terminal
+/// pane, and what each peer was sent of it.
+pub const Screens = struct {
+ gpa: Allocator,
+ enc: screen_state.Encoder,
+ tracks: [pardes.MAX_PANES]?Tracked = @splat(null),
+ peers: std.ArrayListUnmanaged(*[pardes.MAX_PANES]PeerOf) = .empty,
+ out: std.ArrayListUnmanaged(u8) = .empty,
+ /// Nanoseconds: what each flush spent encoding, for every peer.
+ encode_ns: u64 = 0,
+
+ const Tracked = struct { serial: u32, state: *terminal.State, track: screen_state.Track };
+ const PeerOf = struct { serial: u32 = 0, peer: screen_state.Peer = .{} };
+
+ pub fn init(gpa: Allocator) Screens {
+ return .{ .gpa = gpa, .enc = .init(gpa) };
+ }
+
+ /// `core` is the session's, its terminals still there.
+ pub fn deinit(s: *Screens, core: *Pardes) void {
+ for (&s.tracks, 0..) |*slot, id| if (slot.*) |*tr| tr.track.deinit(s.gpa, if (s.live(core, id, tr)) &tr.state.vt else null);
+ for (s.peers.items) |p| s.gpa.destroy(p);
+ s.peers.deinit(s.gpa);
+ s.out.deinit(s.gpa);
+ s.enc.deinit();
+ }
+
+ fn live(_: *const Screens, core: *Pardes, id: usize, tr: *const Tracked) bool {
+ const pane = core.panes[id] orelse return false;
+ return pane.serial == tr.serial and pane.terminal == tr.state;
+ }
+
+ /// A new peer, with nothing yet: its first delta of each terminal
+ /// starts it afresh.
+ pub fn addPeer(s: *Screens) !u16 {
+ const p = try s.gpa.create([pardes.MAX_PANES]PeerOf);
+ p.* = @splat(.{});
+ try s.peers.append(s.gpa, p);
+ return @intCast(s.peers.items.len - 1);
+ }
+
+ /// What `peer` is owed of every terminal, each a message onto `out`
+ /// (owned): nothing for one it has as it is, or with `bound` in flight.
+ pub fn flush(s: *Screens, core: *Pardes, peer: u16, out: *std.ArrayListUnmanaged([]u8)) !void {
+ const t0 = nowNs();
+ defer s.encode_ns += nowNs() - t0;
+ for (core.panes, 0..) |slot, id| {
+ const pane = slot orelse continue;
+ const state = pane.terminal orelse continue;
+ const tr = try s.track(core, id);
+ const pp = &s.peers.items[peer][id];
+ if (pp.serial != pane.serial) pp.* = .{ .serial = pane.serial };
+ var marks: [terminal.marks_len]u8 = undefined;
+ s.out.clearRetainingCapacity();
+ try writeScreenHead(&s.out, s.gpa, @intCast(id), pane.serial, kind_delta);
+ var w: std.Io.Writer.Allocating = .fromArrayList(s.gpa, &s.out);
+ defer s.out = w.toArrayList();
+ if (!try screen_state.encode(&s.enc, &tr.track, &pp.peer, &state.vt, state.changes, terminal.marksOf(state, &marks), &w.writer)) continue;
+ try out.append(s.gpa, try s.gpa.dupe(u8, w.written()));
+ }
+ }
+
+ fn track(s: *Screens, core: *Pardes, id: usize) !*Tracked {
+ const pane = core.panes[id].?;
+ if (s.tracks[id]) |*tr| {
+ if (s.live(core, id, tr)) return tr;
+ // Its pane closed (its emulator, the pin with it, gone).
+ tr.track.deinit(s.gpa, null);
+ }
+ s.tracks[id] = .{ .serial = pane.serial, .state = pane.terminal.?, .track = .init(s.gpa) };
+ return &s.tracks[id].?;
+ }
+
+ /// A peer's message (`Replica.screen`'s, `Replica.screenRequest`'s):
+ /// an answer for it (owned), or null.
+ pub fn take(s: *Screens, core: *Pardes, peer: u16, msg: []const u8) !?[]u8 {
+ const m = parseScreen(msg) orelse return null;
+ const pane = core.panes[m.pane] orelse return null;
+ if (pane.serial != m.serial) return null;
+ const state = pane.terminal orelse return null;
+ const pp = &s.peers.items[peer][m.pane];
+ if (pp.serial != m.serial) return null;
+ switch (m.kind) {
+ kind_ack => if (m.payload.len == 4) pp.peer.ack(std.mem.readInt(u32, m.payload[0..4], .little)),
+ kind_reset => pp.peer.reset(),
+ kind_rows => {
+ if (m.payload.len != 16) return null;
+ const tr = try s.track(core, m.pane);
+ s.out.clearRetainingCapacity();
+ try writeScreenHead(&s.out, s.gpa, m.pane, m.serial, kind_rows);
+ var w: std.Io.Writer.Allocating = .fromArrayList(s.gpa, &s.out);
+ defer s.out = w.toArrayList();
+ try screen_state.encodeRows(&s.enc, &tr.track, &state.vt, std.mem.readInt(u64, m.payload[0..8], .little), std.mem.readInt(u64, m.payload[8..16], .little), &w.writer);
+ return try s.gpa.dupe(u8, w.written());
+ },
+ else => {},
+ }
+ return null;
+ }
+};
+
// ---- a replica ----
pub const Stats = struct {
@@ -207,11 +377,14 @@ pub const Stats = struct {
rollback_ns: std.ArrayListUnmanaged(u64) = .empty,
copy_bytes: u64 = 0,
copies: u32 = 0,
+ /// Nanoseconds: a terminal's delta applied.
+ apply_ns: std.ArrayListUnmanaged(u64) = .empty,
pub fn deinit(s: *Stats, gpa: Allocator) void {
s.spec_ns.deinit(gpa);
s.copy_ns.deinit(gpa);
s.rollback_ns.deinit(gpa);
+ s.apply_ns.deinit(gpa);
}
};
@@ -242,11 +415,26 @@ pub const Replica = struct {
out: std.ArrayListUnmanaged(u8) = .empty,
/// Nanoseconds of the rollback being made, until its reapply.
recovering: ?u64 = null,
+ /// Its terminals' screen state, as the authority's deltas made it.
+ screens: [pardes.MAX_PANES]?ScreenOf = @splat(null),
+ screen_out: std.ArrayListUnmanaged(u8) = .empty,
+
+ const ScreenOf = struct {
+ serial: u32,
+ rep: screen_state.Replica = .{},
+ /// A delta was refused, and a reset asked for: those in flight
+ /// before it are refused unasked.
+ refused: bool = false,
+ /// The rows asked for and not yet answered.
+ asked: ?[2]u64 = null,
+ };
- /// A replica of the session whose first unit is `first`.
- pub fn init(gpa: Allocator, id: u16, first: []const u8) !*Replica {
+ /// A replica of the session whose first unit is `first`; `screens`
+ /// as the authority's (its terminals fed by `screen`).
+ pub fn init(gpa: Allocator, id: u16, first: []const u8, screens: bool) !*Replica {
const r = try gpa.create(Replica);
r.* = .{ .gpa = gpa, .id = id, .t = tape.memory(gpa) };
+ r.t.screen_state = screens;
r.t.core_gpa = r.epoch.allocator();
r.confirm(first);
if (r.t.core == null) {
@@ -257,6 +445,7 @@ pub const Replica = struct {
}
pub fn deinit(r: *Replica) void {
+ for (&r.screens) |*slot| if (slot.*) |*sc| sc.rep.deinit(r.coreGpa());
if (r.t.core) |c| {
const was = Stepping.begin(&r.t, &r.epoch);
if (r.copy.held) r.copy.restore();
@@ -269,6 +458,7 @@ pub const Replica = struct {
for (r.since.items) |u| r.gpa.free(u);
r.since.deinit(r.gpa);
r.out.deinit(r.gpa);
+ r.screen_out.deinit(r.gpa);
r.stats.deinit(r.gpa);
tape.release(&r.t);
if (r.diverged) |why| r.gpa.free(why);
@@ -471,6 +661,89 @@ pub const Replica = struct {
return r.pending.items.len == 0 and r.applied == 0 and !r.copy.held;
}
+ fn coreGpa(r: *Replica) Allocator {
+ return r.epoch.allocator();
+ }
+
+ /// One of the authority's terminal messages (`Screens.flush`, or an
+ /// answer to `screenRequests`), taken between units in stream order: a
+ /// delta written into its pane's emulator, or fetched rows. The
+ /// message for the authority (an acknowledgement, or a request to start
+ /// afresh), valid until the next call, or null.
+ pub fn screen(r: *Replica, msg: []const u8) ?[]const u8 {
+ const m = parseScreen(msg) orelse return null;
+ const c = r.t.core orelse return null;
+ const pane = c.panes[m.pane] orelse return null;
+ if (pane.serial != m.serial) return null; // a pane gone: its slot's next is another
+ const state = pane.terminal orelse return null;
+ const slot = &r.screens[m.pane];
+ if (slot.* == null or slot.*.?.serial != m.serial) {
+ if (slot.*) |*old| old.rep.deinit(r.coreGpa());
+ slot.* = .{ .serial = m.serial };
+ }
+ const sc = &slot.*.?;
+ // The emulator is the authority's, outside every rollback copy:
+ // what it allocates now must outlive one.
+ const was = r.epoch.pause();
+ defer r.epoch.unpause(was);
+ switch (m.kind) {
+ kind_delta => {
+ const t0 = nowNs();
+ const applied = sc.rep.apply(r.coreGpa(), terminal.terminalIo(), &state.vt, m.payload) catch |err| {
+ if (err != error.BaseMismatch) r.fail("a terminal's delta did not apply");
+ if (sc.refused) return null;
+ sc.refused = true;
+ return r.screenMessage(m.pane, m.serial, kind_reset, &.{});
+ };
+ r.stats.apply_ns.append(r.gpa, nowNs() - t0) catch {};
+ sc.refused = false;
+ terminal.takeMarks(state, applied.extra);
+ var seq: [4]u8 = undefined;
+ std.mem.writeInt(u32, &seq, applied.seq, .little);
+ return r.screenMessage(m.pane, m.serial, kind_ack, &seq);
+ },
+ kind_rows => {
+ sc.asked = null;
+ sc.rep.applyRows(r.coreGpa(), &state.vt, m.payload) catch r.fail("a terminal's rows did not apply");
+ return null;
+ },
+ else => return null,
+ }
+ }
+
+ /// 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.
+ pub fn screenRequest(r: *Replica) ?[]const u8 {
+ const c = r.t.core orelse return null;
+ for (&r.screens, 0..) |*slot, id| {
+ const sc: *ScreenOf = if (slot.*) |*x| x else continue;
+ if (sc.asked != null) continue;
+ const pane = c.panes[id] orelse continue;
+ if (pane.serial != sc.serial) continue;
+ const state = pane.terminal orelse continue;
+ const shown = sc.rep.shown(&state.vt);
+ var holes: std.ArrayList([2]u64) = .empty;
+ defer holes.deinit(r.gpa);
+ sc.rep.missing(shown[0], shown[1], &holes, r.gpa) catch return null;
+ if (holes.items.len == 0) continue;
+ const want: [2]u64 = .{ holes.items[0][0], holes.items[holes.items.len - 1][1] };
+ sc.asked = want;
+ var range: [16]u8 = undefined;
+ std.mem.writeInt(u64, range[0..8], want[0], .little);
+ std.mem.writeInt(u64, range[8..16], want[1], .little);
+ return r.screenMessage(@intCast(id), sc.serial, kind_rows, &range);
+ }
+ return null;
+ }
+
+ fn screenMessage(r: *Replica, pane: u8, serial: u32, kind: u8, payload: []const u8) ?[]const u8 {
+ r.screen_out.clearRetainingCapacity();
+ writeScreenHead(&r.screen_out, r.gpa, pane, serial, kind) catch return null;
+ r.screen_out.appendSlice(r.gpa, payload) catch return null;
+ return r.screen_out.items;
+ }
+
pub fn digest(r: *Replica) u64 {
const was = Stepping.begin(&r.t, &r.epoch);
defer was.end();
@@ -484,7 +757,7 @@ 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.digest(&h);
+ state.digestScreen(&h);
d.* = h.final();
}
}
@@ -513,9 +786,9 @@ fn key(r: *Replica, cp: u21, sent: *std.ArrayListUnmanaged([]u8)) !void {
test "a replica's own keys apply at once, confirm on the fast path, and end at the authority's digest" {
const gpa = std.testing.allocator;
- const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host());
+ const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host(), false);
defer a.deinit();
- const r = try Replica.init(gpa, 1, try a.unit(0, 0));
+ const r = try Replica.init(gpa, 1, try a.unit(0, 0), false);
defer r.deinit();
try std.testing.expectEqual(digestOf(a), r.digest());
var sent: std.ArrayListUnmanaged([]u8) = .empty;
@@ -539,13 +812,13 @@ test "a replica's own keys apply at once, confirm on the fast path, and end at t
test "another client's input first: a replica rolls back, replays it and applies its own again" {
const gpa = std.testing.allocator;
- const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host());
+ const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host(), false);
defer a.deinit();
const first = try gpa.dupe(u8, try a.unit(0, 0));
defer gpa.free(first);
- const r1 = try Replica.init(gpa, 1, first);
+ const r1 = try Replica.init(gpa, 1, first, false);
defer r1.deinit();
- const r2 = try Replica.init(gpa, 2, first);
+ const r2 = try Replica.init(gpa, 2, first, false);
defer r2.deinit();
var s1: std.ArrayListUnmanaged([]u8) = .empty;
var s2: std.ArrayListUnmanaged([]u8) = .empty;
diff --git a/src/rollback.zig b/src/rollback.zig
index 9137b6f6..b5f4e966 100644
--- a/src/rollback.zig
+++ b/src/rollback.zig
@@ -140,6 +140,18 @@ pub const Epoch = struct {
_ = e.live.remove(addr);
}
+ /// What is allocated and freed until `unpause` is no copy's: a delta
+ /// written into a replica's terminal while a copy is held (an emulator
+ /// is the authority's, outside every copy, and must outlive a rollback).
+ pub fn pause(e: *Epoch) bool {
+ defer e.on = false;
+ return e.on;
+ }
+
+ pub fn unpause(e: *Epoch, was: bool) void {
+ e.on = was;
+ }
+
fn begin(e: *Epoch) void {
std.debug.assert(!e.on);
e.id +%= 1;
diff --git a/src/screen_state.zig b/src/screen_state.zig
index 51c2ec30..20ed7ad7 100644
--- a/src/screen_state.zig
+++ b/src/screen_state.zig
@@ -13,10 +13,15 @@
//! marks). A row's address is a hash of what the row shows, not of its blob,
//! whose style ids are its source page's. An unchanged row costs 8 bytes.
//!
-//! One delta per peer is in flight, as FrameAck keeps one frame in flight
-//! for the tty. The next delta is encoded against the state the peer
-//! acknowledged, once it has, so a slow peer skips the states in between.
-//! The peer holds the blobs of the state it acknowledged and no others.
+//! Each state the authority sends is a version of its terminal (`Track`),
+//! made once whatever the number of peers. A peer's next delta is against
+//! the version it was last sent: the stream is ordered and loses nothing,
+//! so the peer has that one by the time it applies the next. Several are
+//! in flight (`bound`); acknowledgements free their room, and a peer at the
+//! bound gets nothing until one comes, then the newest version, the ones
+//! between skipped. Peers at the same base are sent the same bytes. A
+//! replica holds the blobs of the state it applied last and no others; a
+//! delta against another (one lost) is refused, and the peer started afresh.
//!
//! The replica writes each delta into a ghostty Terminal, which a replica's
//! terminal pane draws as a local one (src/terminal.zig reads only that).
@@ -120,23 +125,26 @@ fn pinOf(pages: anytype, top: u64, abs: u64) ?Pin {
pub const Encoder = struct {
gpa: std.mem.Allocator,
scratch: ?Page = null,
- meta: std.Io.Writer.Allocating,
- pins: std.ArrayList(Pin) = .empty,
+ blob: std.Io.Writer.Allocating,
+ /// The rows a delta sends a blob for, and the addresses it lists once.
needed: std.ArrayList(struct { pin: Pin, hash: Hash }) = .empty,
+ listed: std.AutoHashMapUnmanaged(Hash, void) = .empty,
+ tail: std.ArrayList(Pin) = .empty,
pub fn init(gpa: std.mem.Allocator) Encoder {
- return .{ .gpa = gpa, .meta = .init(gpa) };
+ return .{ .gpa = gpa, .blob = .init(gpa) };
}
pub fn deinit(e: *Encoder) void {
if (e.scratch) |*s| s.deinit();
- e.meta.deinit();
- e.pins.deinit(e.gpa);
+ e.blob.deinit();
e.needed.deinit(e.gpa);
+ e.listed.deinit(e.gpa);
+ e.tail.deinit(e.gpa);
}
/// The PAGE record of `row` alone, its first `cols` cells.
- fn blob(e: *Encoder, page: *Page, row: *Row, cols: u16, w: *std.Io.Writer) !void {
+ fn rowBlob(e: *Encoder, page: *Page, row: *Row, cols: u16, w: *std.Io.Writer) !void {
var cap: vt.page.Capacity = if (e.scratch) |s| s.capacity else .{ .cols = cols, .rows = 1, .styles = 64 };
if (cap.cols != cols) cap = .{ .cols = cols, .rows = 1, .styles = 64 };
for (0..16) |_| {
@@ -164,148 +172,245 @@ pub const Encoder = struct {
}
};
-/// What the authority knows of one peer.
-pub const Peer = struct {
- seq: u32 = 0,
- in_flight: bool = false,
- /// Never sent anything, or sent before a renumbering: the next delta
- /// starts the replica afresh.
- fresh: bool = true,
- epoch: u32 = 0,
- /// The active area's first row in the state it acknowledged.
- top: u64 = 0,
- /// The blobs the peer holds: those of the state it acknowledged.
- known: std.AutoHashMapUnmanaged(Hash, void) = .empty,
- /// Those of the delta in flight, which become `known` on its ack.
- sent: std.AutoHashMapUnmanaged(Hash, void) = .empty,
+/// Deltas a peer may have in flight. At 207 ms and 60 frames a second about
+/// 13 are; past the bound a peer gets nothing until an acknowledgement, and
+/// then the newest state, the ones between skipped.
+pub const bound = 32;
+
+/// What a peer holds once it has a version: the addresses of its active
+/// rows and its meta. A delta against it sends no blob for these.
+const Known = struct {
+ version: u32,
+ epoch: u32,
+ top: u64,
+ addrs: std.AutoHashMapUnmanaged(Hash, void) = .empty,
+};
+
+/// One terminal as the authority numbers it, for all of its peers: each
+/// state it sends is a version, made once whatever the number of peers.
+pub const Track = struct {
+ rows: Rows = .{},
+ version: u32 = 0,
+ /// The emulator's change count the newest version was made at.
+ changes: u32 = 0,
+ /// The newest version: its active rows (pins, good while the emulator
+ /// is unchanged) and their addresses, and its meta.
+ pins: std.ArrayList(Pin) = .empty,
+ hashes: std.ArrayList(Hash) = .empty,
+ meta: std.Io.Writer.Allocating,
+ meta_hash: Hash = 0,
+ /// The newest versions, oldest first: the bases a peer's next delta may
+ /// have. A peer whose base has gone starts afresh.
+ known: std.ArrayList(Known) = .empty,
+ /// The last delta encoded, for the next peer at the same base.
+ cache: std.Io.Writer.Allocating,
+ cache_base: u32 = 0,
+ cache_version: u32 = 0,
+
+ const kept = bound + 8;
+
+ pub fn init(gpa: std.mem.Allocator) Track {
+ return .{ .meta = .init(gpa), .cache = .init(gpa) };
+ }
- pub fn deinit(peer: *Peer, gpa: std.mem.Allocator) void {
- peer.known.deinit(gpa);
- peer.sent.deinit(gpa);
+ /// `t` is the terminal, or null when it is gone already (with its pins).
+ pub fn deinit(tr: *Track, gpa: std.mem.Allocator, t: ?*Terminal) void {
+ if (t) |term| tr.rows.deinit(term);
+ tr.pins.deinit(gpa);
+ tr.hashes.deinit(gpa);
+ tr.meta.deinit();
+ for (tr.known.items) |*k| k.addrs.deinit(gpa);
+ tr.known.deinit(gpa);
+ tr.cache.deinit();
+ }
+
+ fn find(tr: *const Track, version: u32) ?*const Known {
+ if (version == 0) return null;
+ for (tr.known.items) |*k| if (k.version == version) return if (k.epoch == tr.rows.epoch) k else null;
+ return null;
+ }
+
+ /// A version of `t` as it is now.
+ fn advance(tr: *Track, gpa: std.mem.Allocator, t: *Terminal, changes: u32) !void {
+ try tr.rows.update(t);
+ tr.version +%= 1;
+ if (tr.version == 0) tr.version = 1;
+ tr.changes = changes;
+ tr.meta.clearRetainingCapacity();
+ {
+ var rw: snapshot.record.Writer = .init(gpa, &tr.meta.writer);
+ defer rw.deinit();
+ try snapshot.terminal.encode(t, &rw);
+ }
+ tr.meta_hash = std.hash.Wyhash.hash(0, tr.meta.written());
+ tr.pins.clearRetainingCapacity();
+ tr.hashes.clearRetainingCapacity();
+ var it = t.screens.active.pages.rowIterator(.right_down, .{ .active = .{} }, null);
+ while (it.next()) |p| {
+ try tr.pins.append(gpa, p);
+ try tr.hashes.append(gpa, rowHash(p.node.page(), p.rowAndCell().row, t.cols));
+ }
+ if (tr.known.items.len == kept) {
+ tr.known.items[0].addrs.deinit(gpa);
+ _ = tr.known.orderedRemove(0);
+ }
+ var k: Known = .{ .version = tr.version, .epoch = tr.rows.epoch, .top = tr.rows.top };
+ errdefer k.addrs.deinit(gpa);
+ try k.addrs.ensureTotalCapacity(gpa, @intCast(tr.hashes.items.len + 1));
+ for (tr.hashes.items) |h| k.addrs.putAssumeCapacity(h, {});
+ k.addrs.putAssumeCapacity(tr.meta_hash, {});
+ try tr.known.append(gpa, k);
}
+};
+
+/// What the authority knows of one peer of one terminal.
+pub const Peer = struct {
+ /// The version last sent, which the next delta is against; 0: none, so
+ /// the next starts the replica afresh.
+ sent: u32 = 0,
+ /// The versions in flight, oldest first.
+ flight: [bound]u32 = undefined,
+ n: u8 = 0,
+ /// Every version up to `seq` has landed.
pub fn ack(peer: *Peer, seq: u32) void {
- if (!peer.in_flight or seq != peer.seq) return;
- std.mem.swap(std.AutoHashMapUnmanaged(Hash, void), &peer.known, &peer.sent);
- peer.in_flight = false;
+ var i: u8 = 0;
+ while (i < peer.n and peer.flight[i] <= seq) i += 1;
+ std.mem.copyForwards(u32, peer.flight[0 .. peer.n - i], peer.flight[i..peer.n]);
+ peer.n -= i;
}
- /// Start the peer afresh (it joined again, or lost its state).
+ /// Start the peer afresh: it lost its state, or never had one.
pub fn reset(peer: *Peer) void {
- peer.fresh = true;
- peer.in_flight = false;
- peer.known.clearRetainingCapacity();
+ peer.* = .{};
}
};
-/// The delta's fixed header: u32 seq, u8 flags, u32 epoch, u64 meta, u16
-/// cursor x and y, u8 cursor style, u8 pending wrap, the kitty keyboard
-/// flags, u64 top, u64 history rows; then u16 rows and a u64 per active
-/// row, u16 and a u64 per row of the tail (those that scrolled off the
-/// active area since the acknowledged state, up to a screen of them, oldest
-/// first), and a u16 blob count and each blob as u64 hash, u32 length, bytes.
+/// The delta's fixed header: u32 seq, u32 base (0: none, the replica
+/// starts afresh), u8 flags, u32 epoch, u64 meta, u16 cursor x and y, u8
+/// cursor style, u8 pending wrap, u8 the cursor's semantic content, the
+/// kitty keyboard flags, u64 top, u64 history rows, u64 the viewport's top
+/// as an absolute row (all ones: following the active area), u16 and the
+/// caller's extra bytes; then u16 rows and a u64 per active row, u16 and a
+/// u64 per row of the tail (those that scrolled off the active area since
+/// the base, up to a screen of them, oldest first), and a u16 blob count
+/// and each blob as u64 hash, u32 length, bytes.
const flag_reset: u8 = 1;
const KittyFlags = @FieldType(Screen, "kitty_keyboard");
+const following = std.math.maxInt(u64);
-/// The delta for `peer` against what it acknowledged, onto `out`, or false
-/// (nothing written) while its last delta is in flight.
-pub fn encode(e: *Encoder, peer: *Peer, n: *Rows, t: *Terminal, out: *std.Io.Writer) !bool {
- if (peer.in_flight) return false;
- const gpa = e.gpa;
- try n.update(t);
- if (peer.epoch != n.epoch) peer.reset();
- const reset = peer.fresh;
- peer.sent.clearRetainingCapacity();
-
- e.meta.clearRetainingCapacity();
- {
- var rw: snapshot.record.Writer = .init(gpa, &e.meta.writer);
- defer rw.deinit();
- try snapshot.terminal.encode(t, &rw);
+/// The delta that takes `peer` from what it was last sent to `t` as it is,
+/// onto `out`; false (nothing written) when it has that already, or has
+/// `bound` in flight. `changes` counts the emulator's writes (a new count
+/// is a new version); `extra` rides along (the caller's own state of the
+/// terminal), the same for every peer of one version. A peer at the same
+/// base as the last one encoded is sent the same bytes.
+pub fn encode(e: *Encoder, tr: *Track, peer: *Peer, t: *Terminal, changes: u32, extra: []const u8, out: *std.Io.Writer) !bool {
+ if (tr.version == 0 or changes != tr.changes) try tr.advance(e.gpa, t, changes);
+ if (peer.sent == tr.version or peer.n == bound) return false;
+ const base = tr.find(peer.sent);
+ const base_version = if (base) |b| b.version else 0;
+ if (tr.cache_version != tr.version or tr.cache_base != base_version) {
+ tr.cache.clearRetainingCapacity();
+ try write(e, tr, base, t, extra, &tr.cache.writer);
+ tr.cache_version = tr.version;
+ tr.cache_base = base_version;
}
- const meta = std.hash.Wyhash.hash(0, e.meta.written());
- try peer.sent.put(gpa, meta, {});
+ try out.writeAll(tr.cache.written());
+ peer.sent = tr.version;
+ peer.flight[peer.n] = tr.version;
+ peer.n += 1;
+ return true;
+}
+fn write(e: *Encoder, tr: *Track, base: ?*const Known, t: *Terminal, extra: []const u8, out: *std.Io.Writer) !void {
+ const gpa = e.gpa;
+ const reset = base == null;
const screen = t.screens.active;
const pages = &t.screens.get(.primary).?.pages;
- try out.writeInt(u32, peer.seq +% 1, .little);
+ const history = pages.total_rows - pages.rows;
+ const top = tr.rows.top;
+ try out.writeInt(u32, tr.version, .little);
+ try out.writeInt(u32, if (base) |b| b.version else 0, .little);
try out.writeByte(if (reset) flag_reset else 0);
- try out.writeInt(u32, n.epoch, .little);
- try out.writeInt(u64, meta, .little);
+ try out.writeInt(u32, tr.rows.epoch, .little);
+ try out.writeInt(u64, tr.meta_hash, .little);
try out.writeInt(u16, screen.cursor.x, .little);
try out.writeInt(u16, screen.cursor.y, .little);
try out.writeByte(@intFromEnum(screen.cursor.cursor_style));
try out.writeByte(@intFromBool(screen.cursor.pending_wrap));
+ try out.writeByte(@intFromEnum(screen.cursor.semantic_content));
// ponytail: raw bytes, as the hello refuses a peer of another build.
try out.writeAll(std.mem.asBytes(&screen.kitty_keyboard));
- try out.writeInt(u64, n.top, .little);
- const history = pages.total_rows - pages.rows;
+ try out.writeInt(u64, top, .little);
try out.writeInt(u64, history, .little);
- try out.writeInt(u16, t.rows, .little);
+ try out.writeInt(u64, if (pages.viewport == .active) following else top - history + pages.scrollbar().offset, .little);
+ try out.writeInt(u16, @intCast(extra.len), .little);
+ try out.writeAll(extra);
- // The active rows, then the tail: what scrolled off since the state
- // acknowledged, which may have changed after it was sent.
- const tail: u16 = if (reset) 0 else @intCast(@min(n.top -| peer.top, t.rows, history));
- e.pins.clearRetainingCapacity();
- var it = screen.pages.rowIterator(.right_down, .{ .active = .{} }, null);
- while (it.next()) |p| try e.pins.append(gpa, p);
- for (0..tail) |j| try e.pins.append(gpa, pages.getTopLeft(.active).up(tail - j).?);
+ // The active rows, then the tail: what scrolled off since the base,
+ // which may have changed after it was sent.
+ e.listed.clearRetainingCapacity();
e.needed.clearRetainingCapacity();
- for (e.pins.items, 0..) |p, i| {
- if (i == t.rows) try out.writeInt(u16, tail, .little);
+ const tail: u16 = if (base) |b| @intCast(@min(top -| b.top, t.rows, history)) else 0;
+ e.tail.clearRetainingCapacity();
+ for (0..tail) |j| try e.tail.append(gpa, pages.getTopLeft(.active).up(tail - j).?);
+ try out.writeInt(u16, @intCast(tr.pins.items.len), .little);
+ for (tr.pins.items, tr.hashes.items) |p, h| {
+ try out.writeInt(u64, h, .little);
+ try needBlob(e, base, p, h);
+ }
+ try out.writeInt(u16, tail, .little);
+ for (e.tail.items) |p| {
const h = rowHash(p.node.page(), p.rowAndCell().row, t.cols);
try out.writeInt(u64, h, .little);
- // Every address listed is held once this is acknowledged; a blob
- // goes only for one not held already, once.
- if ((try peer.sent.getOrPut(gpa, h)).found_existing or peer.known.contains(h)) continue;
- try e.needed.append(gpa, .{ .pin = p, .hash = h });
+ try needBlob(e, base, p, h);
}
- if (tail == 0) try out.writeInt(u16, 0, .little);
- const meta_new = !peer.known.contains(meta);
+ const meta_new = if (base) |b| !b.addrs.contains(tr.meta_hash) else true;
try out.writeInt(u16, @intCast(e.needed.items.len + @intFromBool(meta_new)), .little);
if (meta_new) {
- try out.writeInt(u64, meta, .little);
- try out.writeInt(u32, @intCast(e.meta.written().len), .little);
- try out.writeAll(e.meta.written());
+ try out.writeInt(u64, tr.meta_hash, .little);
+ try out.writeInt(u32, @intCast(tr.meta.written().len), .little);
+ try out.writeAll(tr.meta.written());
}
- var blob: std.Io.Writer.Allocating = .init(gpa);
- defer blob.deinit();
for (e.needed.items) |need| {
- blob.clearRetainingCapacity();
- try e.blob(need.pin.node.page(), need.pin.rowAndCell().row, t.cols, &blob.writer);
+ e.blob.clearRetainingCapacity();
+ try e.rowBlob(need.pin.node.page(), need.pin.rowAndCell().row, t.cols, &e.blob.writer);
try out.writeInt(u64, need.hash, .little);
- try out.writeInt(u32, @intCast(blob.written().len), .little);
- try out.writeAll(blob.written());
+ try out.writeInt(u32, @intCast(e.blob.written().len), .little);
+ try out.writeAll(e.blob.written());
}
- peer.top = n.top;
- peer.seq +%= 1;
- peer.in_flight = true;
- peer.fresh = false;
- peer.epoch = n.epoch;
- return true;
+}
+
+/// A blob goes for an address the base does not hold, once.
+fn needBlob(e: *Encoder, base: ?*const Known, p: Pin, h: Hash) !void {
+ if ((try e.listed.getOrPut(e.gpa, h)).found_existing) return;
+ if (base) |b| if (b.addrs.contains(h)) return;
+ try e.needed.append(e.gpa, .{ .pin = p, .hash = h });
}
/// The primary screen's rows `[lo, hi)` the authority still has, as u32
/// epoch, u32 count, then each as u64 row, u32 length, blob: a replica's
/// fetch of history it holds as holes.
// ponytail: every row its blob, none by address: phase 6's content cache.
-pub fn encodeRows(e: *Encoder, n: *Rows, t: *Terminal, lo: u64, hi: u64, out: *std.Io.Writer) !void {
- try n.update(t);
+pub fn encodeRows(e: *Encoder, tr: *Track, t: *Terminal, lo: u64, hi: u64, out: *std.Io.Writer) !void {
+ try tr.rows.update(t);
var blobs: std.Io.Writer.Allocating = .init(e.gpa);
defer blobs.deinit();
var count: u32 = 0;
var abs = lo;
- while (abs < hi) : (abs += 1) {
- const p = n.pinAt(t, abs) orelse continue;
+ // The active area is the deltas'.
+ while (abs < @min(hi, tr.rows.top)) : (abs += 1) {
+ const p = tr.rows.pinAt(t, abs) orelse continue;
const start = blobs.written().len;
try blobs.writer.writeInt(u64, abs, .little);
try blobs.writer.writeInt(u32, 0, .little);
- try e.blob(p.node.page(), p.rowAndCell().row, t.cols, &blobs.writer);
+ try e.rowBlob(p.node.page(), p.rowAndCell().row, t.cols, &blobs.writer);
const len: u32 = @intCast(blobs.written().len - start - 12);
std.mem.writeInt(u32, blobs.written()[start + 8 ..][0..4], len, .little);
count += 1;
}
- try out.writeInt(u32, n.epoch, .little);
+ try out.writeInt(u32, tr.rows.epoch, .little);
try out.writeInt(u32, count, .little);
try out.writeAll(blobs.written());
}
@@ -337,21 +442,32 @@ pub const Replica = struct {
if (r.scratch) |*s| s.deinit();
}
- /// Write one delta into `t`; the seq to acknowledge.
- pub fn apply(r: *Replica, gpa: std.mem.Allocator, io: std.Io, t: *Terminal, bytes: []const u8) !u32 {
+ pub const Applied = struct { seq: u32, extra: []const u8 };
+
+ /// Write one delta into `t`: the seq to acknowledge, and the caller's
+ /// extra bytes (borrowed from `bytes`). error.BaseMismatch: the delta
+ /// is against a state this replica does not have (one was lost, or it
+ /// started afresh), so `t` is as it was and it must be sent a reset.
+ pub fn apply(r: *Replica, gpa: std.mem.Allocator, io: std.Io, t: *Terminal, bytes: []const u8) !Applied {
var in: std.Io.Reader = .fixed(bytes);
const seq = try in.takeInt(u32, .little);
+ const base = try in.takeInt(u32, .little);
const flags = try in.takeByte();
+ const reset = flags & flag_reset != 0;
+ if (!reset and base != r.seq) return error.BaseMismatch;
const epoch = try in.takeInt(u32, .little);
const meta = try in.takeInt(u64, .little);
const cx = try in.takeInt(u16, .little);
const cy = try in.takeInt(u16, .little);
const style = try in.takeByte();
const wrap = try in.takeByte();
+ const semantic = try in.takeByte();
var kitty: KittyFlags = undefined;
@memcpy(std.mem.asBytes(&kitty), try in.take(@sizeOf(KittyFlags)));
const top = try in.takeInt(u64, .little);
const history = try in.takeInt(u64, .little);
+ const viewport = try in.takeInt(u64, .little);
+ const extra = try in.take(try in.takeInt(u16, .little));
const nrows = try in.takeInt(u16, .little);
const hashes = try in.take(@as(usize, nrows) * 8);
const tail = try in.takeInt(u16, .little);
@@ -371,18 +487,21 @@ pub const Replica = struct {
}
}.of;
- if (flags & flag_reset != 0 or meta != r.meta) {
+ if (reset or meta != r.meta) {
var reader: std.Io.Reader = .fixed(try blobOf(r, &fresh, meta));
var next = try snapshot.terminal.decode(&reader, try snapshot.record.nextHeader(&reader), io, gpa);
- if (flags & flag_reset != 0) {
+ if (reset) {
std.mem.swap(Terminal, t, &next);
next.deinit(gpa);
for (&r.held) |*h| h.clearRetainingCapacity();
r.holes.clearRetainingCapacity();
r.top = top;
r.epoch = epoch;
- // The authority's history, blank, to be fetched.
+ // The authority's history, blank, to be fetched. Its own
+ // limit is the authority's row count (below), not bytes:
+ // its pages may pack rows otherwise.
const primary = t.screens.get(.primary).?;
+ primary.pages.setMaxBytes(null);
try scrollUp(primary, history);
if (history > 0) try r.holes.append(gpa, .{ top -| history, top });
} else {
@@ -394,16 +513,12 @@ pub const Replica = struct {
if (epoch != r.epoch) return error.Renumbered;
// The primary screen scrolled `top - r.top` rows since the last
- // delta: as many go up into the history here (no more than it and
- // the screen hold).
- // ponytail: the history's extent then follows this terminal's own
- // pruning, under the authority's limit: a page more or less than the
- // authority's, and the oldest rows may be some it has dropped. The tail is what they are now; any older than
- // the tail are holes, never seen or seen before they last changed.
+ // delta: as many go up into the history here (no more than its
+ // history holds and the screen), each beyond the tail a hole.
const primary = t.screens.get(.primary).?;
if (top > r.top) {
const k = top - r.top;
- try scrollUp(primary, @min(k, @as(u64, t.rows) + history + 1));
+ try scrollUp(primary, @min(k, @as(u64, t.rows) + history));
const held = &r.held[0];
if (k >= held.items.len) held.clearRetainingCapacity() else {
std.mem.copyForwards(Hash, held.items, held.items[@intCast(k)..]);
@@ -412,17 +527,18 @@ pub const Replica = struct {
if (top - tail > r.top) try r.holes.append(gpa, .{ r.top, top - tail });
r.top = top;
}
+ // The history as long as the authority's (it prunes a page at a
+ // time, and an ED 3 takes it all): row numbers and the scrollbar
+ // say the same on both. ponytail: one pruned shorter than that
+ // (its pages packed otherwise) stays shorter.
+ const have = primary.pages.total_rows - primary.pages.rows;
+ if (have > history) primary.pages.eraseHistory(.{ .history = .{ .y = @intCast(have - history - 1) } });
+ r.trimHoles(primary);
for (0..tail) |j| {
const p = pinOf(&primary.pages, top, top - tail + j) orelse continue;
const h = std.mem.readInt(u64, tails[j * 8 ..][0..8], .little);
if (rowHash(p.node.page(), p.rowAndCell().row, t.cols) != h) try r.writeRow(gpa, primary, p, try blobOf(r, &fresh, h));
}
- // The authority's history went (an ED3): so does this one's.
- if (history == 0 and primary.pages.total_rows > primary.pages.rows) {
- primary.pages.eraseHistory(null);
- r.holes.clearRetainingCapacity();
- }
- r.trimHoles(primary);
const screen = t.screens.active;
const held = &r.held[@intFromEnum(t.screens.active_key)];
@@ -439,7 +555,10 @@ pub const Replica = struct {
screen.cursorAbsolute(@min(cx, t.cols - 1), @min(cy, t.rows - 1));
screen.cursor.cursor_style = @enumFromInt(style);
screen.cursor.pending_wrap = wrap != 0;
+ screen.cursor.semantic_content = @enumFromInt(semantic);
screen.kitty_keyboard = kitty;
+ const oldest = r.top -| (primary.pages.total_rows - primary.pages.rows);
+ primary.pages.scroll(if (viewport == following) .active else .{ .row = @intCast(viewport -| oldest) });
// Hold the blobs of this state, and no others.
var keep: std.AutoHashMapUnmanaged(Hash, []u8) = .empty;
@@ -459,7 +578,7 @@ pub const Replica = struct {
r.blobs.deinit(gpa);
r.blobs = keep;
r.seq = seq;
- return seq;
+ return .{ .seq = seq, .extra = extra };
}
/// The holes in `[lo, hi)`: the rows to fetch before showing them.
@@ -471,6 +590,15 @@ pub const Replica = struct {
}
}
+ /// The absolute row the viewport of `t`'s primary screen starts at, and
+ /// how many it shows.
+ pub fn shown(r: *const Replica, t: *Terminal) [2]u64 {
+ const pages = &t.screens.get(.primary).?.pages;
+ const sb = pages.scrollbar();
+ const oldest = r.top -| (pages.total_rows - pages.rows);
+ return .{ oldest + sb.offset, oldest + sb.offset + sb.len };
+ }
+
/// Write fetched history rows (`encodeRows`) into `t`.
pub fn applyRows(r: *Replica, gpa: std.mem.Allocator, t: *Terminal, bytes: []const u8) !void {
var in: std.Io.Reader = .fixed(bytes);
@@ -479,7 +607,9 @@ pub const Replica = struct {
for (0..try in.takeInt(u32, .little)) |_| {
const abs = try in.takeInt(u64, .little);
const blob = try in.take(try in.takeInt(u32, .little));
- if (abs >= r.top) continue;
+ // Only a hole is written: a row the replica holds is the
+ // authority's already, and newer than what this fetch saw.
+ if (abs >= r.top or !r.inHole(abs)) continue;
const p = pinOf(&primary.pages, r.top, abs) orelse continue;
try r.writeRow(gpa, primary, p, blob);
try r.fill(gpa, abs);
@@ -535,13 +665,18 @@ pub const Replica = struct {
};
/// `k` blank rows onto the bottom of a screen's active area, its top `k`
-/// going up into the history, as `k` linefeeds at the bottom would.
-// ponytail: a row at a time, so a flood costs the replica up to its whole
-// history's rows a delta (measured in `bench`); a bulk scroll if that shows.
+/// going up into the history, as `k` linefeeds at the bottom would. A
+/// flood's thousands are grown a row at a time without the cursor (the
+/// page list's fast path, a counter), which is put back after.
fn scrollUp(screen: *Screen, k: u64) !void {
if (k == 0) return;
screen.cursorAbsolute(0, screen.pages.rows - 1);
- for (0..@intCast(k)) |_| try screen.cursorDownScroll();
+ if (k <= screen.pages.rows or screen.no_scrollback or screen.cursor.style_id != 0) {
+ for (0..@intCast(k)) |_| try screen.cursorDownScroll();
+ return;
+ }
+ for (0..@intCast(k)) |_| _ = try screen.pages.grow();
+ screen.cursorReload();
}
/// `rowHash` of a row never written.
@@ -601,13 +736,16 @@ fn dumpRow(page: *Page, row: *Row, cols: u16, w: *std.Io.Writer) !void {
}
/// The state a replica must match: the terminal-wide state, the cursor,
-/// the active screen's rows.
-fn dumpScreen(t: *Terminal, w: *std.Io.Writer) !void {
+/// the history's extent and the viewport, the active screen's rows.
+pub fn dumpScreen(t: *Terminal, w: *std.Io.Writer) !void {
const screen = t.screens.active;
- try w.print("{d}x{d} {s} cursor {d},{d} {s} {} title {s} pwd {s}\n", .{
- t.cols, t.rows, @tagName(t.screens.active_key),
- screen.cursor.x, screen.cursor.y, @tagName(screen.cursor.cursor_style),
- screen.cursor.pending_wrap, t.getTitle() orelse "", t.getPwd() orelse "",
+ const sb = t.screens.get(.primary).?.pages.scrollbar();
+ try w.print("{d}x{d} {s} cursor {d},{d} {s} {} {s} title {s} pwd {s} scrollbar {d} {d} {d}\n", .{
+ t.cols, t.rows, @tagName(t.screens.active_key),
+ screen.cursor.x, screen.cursor.y, @tagName(screen.cursor.cursor_style),
+ screen.cursor.pending_wrap, @tagName(screen.cursor.semantic_content), t.getTitle() orelse "",
+ t.getPwd() orelse "", sb.total, sb.offset,
+ sb.len,
});
try w.writeAll(std.mem.asBytes(&t.modes.values));
try w.writeAll(std.mem.asBytes(&screen.kitty_keyboard));
@@ -619,31 +757,38 @@ fn dumpScreen(t: *Terminal, w: *std.Io.Writer) !void {
}
/// An authority and its replica, fed one stream of pty bytes, the deltas
-/// and fetches between them at random: a delta encoded at a random step and
-/// applied a random number of steps later (so the states between are
-/// skipped), random resizes of the authority, random fetches of holes.
-/// After each delta, the replica's screen is the authority's as it was
-/// encoded, and every history row it holds outside its holes is what the
-/// authority holds at that absolute row.
+/// and fetches between them at random: a delta encoded at a random step
+/// (so the states between are skipped), several in flight and each landing
+/// a random number of steps later, in order, one lost now and then (the
+/// replica refuses the next and is started afresh), random resizes of the
+/// authority, random fetches of holes. After each delta, the replica's
+/// screen is the authority's as it was encoded, and every history row it
+/// holds outside its holes is what the authority holds at that absolute
+/// row.
pub const Soak = struct {
gpa: std.mem.Allocator,
io: std.Io,
a: *Terminal,
stream: vt.TerminalStream,
- rows: Rows = .{},
+ track: Track,
enc: Encoder,
peer: Peer = .{},
+ /// The authority's writes, as terminal.State counts them.
+ changes: u32 = 0,
b: *Terminal,
rep: Replica = .{},
prng: std.Random.DefaultPrng,
- /// The delta in flight, the authority's dump when it was encoded, and
- /// how many steps it waits before it lands.
- delta: std.Io.Writer.Allocating,
- expect: std.Io.Writer.Allocating,
+ /// The deltas in flight, oldest first, each with the authority's dump
+ /// when it was encoded and the step it lands at.
+ flight: std.ArrayList(struct { delta: []u8, expect: []u8, at: u64 }) = .empty,
got: std.Io.Writer.Allocating,
- wait: u32 = 0,
+ now: u64 = 0,
resizes: bool = true,
- stats: struct { deltas: u64 = 0, bytes: u64 = 0, fetched: u64 = 0, history_checked: u64 = 0 } = .{},
+ drops: bool = true,
+ /// The replica refused a delta and the authority started it afresh:
+ /// what was in flight before is refused too.
+ refused: bool = false,
+ stats: struct { deltas: u64 = 0, bytes: u64 = 0, fetched: u64 = 0, history_checked: u64 = 0, lost: u64 = 0, refused: u64 = 0, most_in_flight: u64 = 0 } = .{},
pub fn init(gpa: std.mem.Allocator, io: std.Io, cols: u16, rows: u16, scrollback: usize, seed: u64) !*Soak {
const s = try gpa.create(Soak);
@@ -651,17 +796,18 @@ pub const Soak = struct {
const a = try gpa.create(Terminal);
a.* = try Terminal.init(io, gpa, .{ .cols = cols, .rows = rows, .max_scrollback_bytes = scrollback });
const b = try gpa.create(Terminal);
- b.* = try Terminal.init(io, gpa, .{ .cols = 2, .rows = 2, .max_scrollback_bytes = scrollback });
+ // Room to spare: its pages may pack rows otherwise, and it keeps the
+ // authority's history to the row.
+ b.* = try Terminal.init(io, gpa, .{ .cols = 2, .rows = 2, .max_scrollback_bytes = 2 * scrollback });
s.* = .{
.gpa = gpa,
.io = io,
.a = a,
.stream = a.vtStream(),
+ .track = .init(gpa),
.enc = .init(gpa),
.b = b,
.prng = .init(seed),
- .delta = .init(gpa),
- .expect = .init(gpa),
.got = .init(gpa),
};
return s;
@@ -670,16 +816,18 @@ pub const Soak = struct {
pub fn deinit(s: *Soak) void {
const gpa = s.gpa;
s.stream.deinit();
- s.rows.deinit(s.a);
+ s.track.deinit(gpa, s.a);
s.a.deinit(gpa);
gpa.destroy(s.a);
s.b.deinit(gpa);
gpa.destroy(s.b);
s.enc.deinit();
- s.peer.deinit(gpa);
s.rep.deinit(gpa);
- s.delta.deinit();
- s.expect.deinit();
+ for (s.flight.items) |f| {
+ gpa.free(f.delta);
+ gpa.free(f.expect);
+ }
+ s.flight.deinit(gpa);
s.got.deinit();
gpa.destroy(s);
}
@@ -691,6 +839,7 @@ pub const Soak = struct {
while (at < bytes.len) {
const n = @min(bytes.len - at, 1 + random.uintLessThan(usize, 512));
s.stream.nextSlice(bytes[at..][0..n]);
+ s.changes +%= 1;
at += n;
try s.step();
}
@@ -698,48 +847,82 @@ pub const Soak = struct {
pub fn step(s: *Soak) !void {
const random = s.prng.random();
+ s.now += 1;
if (s.resizes and random.uintLessThan(u32, 200) == 0) {
try s.a.resize(s.gpa, .{ .cols = 10 + random.uintLessThan(u16, 200), .rows = 3 + random.uintLessThan(u16, 60) });
+ s.changes +%= 1;
}
- if (!s.peer.in_flight) {
- if (random.boolean()) return; // a state skipped
- s.delta.clearRetainingCapacity();
- if (!try encode(&s.enc, &s.peer, &s.rows, s.a, &s.delta.writer)) unreachable;
- s.expect.clearRetainingCapacity();
- try dumpScreen(s.a, &s.expect.writer);
- s.wait = random.uintLessThan(u32, 4);
- s.stats.deltas += 1;
- s.stats.bytes += s.delta.written().len;
- return;
- }
- if (s.wait > 0) {
- s.wait -= 1;
- return;
- }
- try s.land();
+ // A frame now and then; the states between are skipped.
+ if (random.boolean()) try s.send(s.now + random.uintLessThan(u64, 12));
+ while (s.flight.items.len > 0 and s.flight.items[0].at <= s.now) try s.land();
if (random.uintLessThan(u32, 8) == 0) try s.fetch();
}
- /// The delta in flight applied and acknowledged, and checked.
- pub fn land(s: *Soak) !void {
- if (!s.peer.in_flight) return;
- s.peer.ack(try s.rep.apply(s.gpa, s.io, s.b, s.delta.written()));
+ /// A delta, if the peer is owed one, sent to land at step `at`.
+ fn send(s: *Soak, at: u64) !void {
+ var d: std.Io.Writer.Allocating = .init(s.gpa);
+ defer d.deinit();
+ if (!try encode(&s.enc, &s.track, &s.peer, s.a, s.changes, "extra", &d.writer)) return;
+ var expect: std.Io.Writer.Allocating = .init(s.gpa);
+ defer expect.deinit();
+ try dumpScreen(s.a, &expect.writer);
+ const last = if (s.flight.items.len > 0) s.flight.items[s.flight.items.len - 1].at else 0;
+ try s.flight.append(s.gpa, .{ .delta = try d.toOwnedSlice(), .expect = try expect.toOwnedSlice(), .at = @max(at, last) });
+ s.stats.deltas += 1;
+ s.stats.bytes += s.flight.items[s.flight.items.len - 1].delta.len;
+ s.stats.most_in_flight = @max(s.stats.most_in_flight, s.flight.items.len);
+ }
+
+ /// The oldest delta in flight applied (or lost), acknowledged, checked.
+ fn land(s: *Soak) !void {
+ const f = s.flight.orderedRemove(0);
+ defer s.gpa.free(f.delta);
+ defer s.gpa.free(f.expect);
+ if (s.drops and s.prng.random().uintLessThan(u32, 50) == 0) {
+ s.stats.lost += 1;
+ return;
+ }
+ const applied = s.rep.apply(s.gpa, s.io, s.b, f.delta) catch |err| switch (err) {
+ error.BaseMismatch => {
+ // Asked once: the authority starts it afresh.
+ if (!s.refused) s.peer.reset();
+ s.refused = true;
+ s.stats.refused += 1;
+ return;
+ },
+ else => return err,
+ };
+ s.refused = false;
+ if (!std.mem.eql(u8, applied.extra, "extra")) return error.ExtraLost;
+ s.peer.ack(applied.seq);
s.got.clearRetainingCapacity();
try dumpScreen(s.b, &s.got.writer);
- if (!std.mem.eql(u8, s.expect.written(), s.got.written())) {
- reportDiff(s.expect.written(), s.got.written());
+ if (!std.mem.eql(u8, f.expect, s.got.written())) {
+ reportDiff(f.expect, s.got.written());
return error.ReplicaDiffers;
}
try s.checkHistory();
}
+ /// Everything in flight landed, then a last delta of the end, until the
+ /// replica holds it: what the replica shows at quiescence.
+ fn settle(s: *Soak) !void {
+ s.drops = false;
+ for (0..4) |_| {
+ while (s.flight.items.len > 0) try s.land();
+ try s.send(0);
+ if (s.flight.items.len == 0) return;
+ }
+ return error.NeverSettled;
+ }
+
/// Every history row the replica holds, outside its holes and inside
/// what the authority still has, is the authority's (rows in history
/// never change; a resize renumbers and starts the replica afresh).
fn checkHistory(s: *Soak) !void {
// Numbered as of now: the authority may have scrolled on since.
- try s.rows.update(s.a);
- if (s.rep.epoch != s.rows.epoch) return;
+ try s.track.rows.update(s.a);
+ if (s.rep.epoch != s.track.rows.epoch) return;
const pages = &s.b.screens.get(.primary).?.pages;
const have = pages.total_rows - pages.rows;
var ra: std.Io.Writer.Allocating = .init(s.gpa);
@@ -751,7 +934,7 @@ pub const Soak = struct {
const abs = s.rep.top - d;
if (s.rep.inHole(abs)) continue;
const pb = pinOf(pages, s.rep.top, abs) orelse continue;
- const pa = s.rows.pinAt(s.a, abs) orelse continue;
+ const pa = s.track.rows.pinAt(s.a, abs) orelse continue;
ra.clearRetainingCapacity();
rb.clearRetainingCapacity();
try dumpRow(pa.node.page(), pa.rowAndCell().row, s.a.cols, &ra.writer);
@@ -774,7 +957,7 @@ pub const Soak = struct {
const hi = @min(hole[1], lo + 1 + random.uintLessThan(u64, 80));
var out: std.Io.Writer.Allocating = .init(s.gpa);
defer out.deinit();
- try encodeRows(&s.enc, &s.rows, s.a, lo, hi, &out.writer);
+ try encodeRows(&s.enc, &s.track, s.a, lo, hi, &out.writer);
try s.rep.applyRows(s.gpa, s.b, out.written());
s.stats.fetched += hi - lo;
try s.checkHistory();
@@ -795,18 +978,14 @@ fn reportDiff(want: []const u8, got: []const u8) void {
}
}
-/// Drive one stream through a soak and land a last delta of its end.
+/// Drive one stream through a soak, then settle: the replica's screen at
+/// quiescence is the authority's.
pub fn soak(gpa: std.mem.Allocator, io: std.Io, bytes: []const u8, cols: u16, rows: u16, scrollback: usize, seed: u64, resizes: bool) !@FieldType(Soak, "stats") {
const s = try Soak.init(gpa, io, cols, rows, scrollback, seed);
defer s.deinit();
s.resizes = resizes;
try s.feed(bytes);
- try s.land();
- s.delta.clearRetainingCapacity();
- _ = try encode(&s.enc, &s.peer, &s.rows, s.a, &s.delta.writer);
- s.expect.clearRetainingCapacity();
- try dumpScreen(s.a, &s.expect.writer);
- try s.land();
+ try s.settle();
return s.stats;
}
@@ -841,7 +1020,7 @@ fn perf(gpa: std.mem.Allocator, io: std.Io, dir_path: []const u8, w: *std.Io.Wri
failed += 1;
continue;
};
- if (seed == 0) try w.print("screen-state {s} {d}x{d}: {d} bytes, {d} deltas, {d} wire bytes, {d} history rows checked, {d} fetched\n", .{ entry.name, cols, rows, bytes.len, st.deltas, st.bytes, st.history_checked, st.fetched });
+ if (seed == 0) try w.print("screen-state {s} {d}x{d}: {d} bytes, {d} deltas ({d} lost, {d} refused, {d} in flight at most), {d} wire bytes, {d} history rows checked, {d} fetched\n", .{ entry.name, cols, rows, bytes.len, st.deltas, st.lost, st.refused, st.most_in_flight, st.bytes, st.history_checked, st.fetched });
}
}
try w.print("screen-state corpus: {d} streams x 3 seeds, {d} failed\n", .{ files, failed });
@@ -858,8 +1037,6 @@ fn bench(gpa: std.mem.Allocator, io: std.Io, w: *std.Io.Writer) !void {
defer stream.deinit();
var enc: Encoder = .init(gpa);
defer enc.deinit();
- var n: Rows = .{};
- defer n.deinit(t);
var out: std.Io.Writer.Allocating = .init(gpa);
defer out.deinit();
var line: [1024]u8 = undefined;
@@ -868,6 +1045,7 @@ fn bench(gpa: std.mem.Allocator, io: std.Io, w: *std.Io.Writer) !void {
var same: [200]u64 = undefined;
var full_bytes: usize = 0;
var same_bytes: usize = 0;
+ var changes: u32 = 0;
for (&full, &same, 0..) |*f, *u, rep| {
for (0..60) |y| {
var lw: std.Io.Writer = .fixed(&line);
@@ -875,17 +1053,19 @@ fn bench(gpa: std.mem.Allocator, io: std.Io, w: *std.Io.Writer) !void {
while (lw.end < 190) try lw.writeAll("\x1b[1mbold\x1b[22m text ");
stream.nextSlice(lw.buffered());
}
+ changes += 1;
+ var tr: Track = .init(gpa);
+ defer tr.deinit(gpa, t);
var peer: Peer = .{};
- defer peer.deinit(gpa);
out.clearRetainingCapacity();
var t0 = std.Io.Clock.awake.now(io).nanoseconds;
- _ = try encode(&enc, &peer, &n, t, &out.writer);
+ _ = try encode(&enc, &tr, &peer, t, changes, "", &out.writer);
f.* = @intCast(std.Io.Clock.awake.now(io).nanoseconds - t0);
full_bytes = out.written().len;
- peer.ack(peer.seq);
+ // The same screen again as a new version: every row held.
out.clearRetainingCapacity();
t0 = std.Io.Clock.awake.now(io).nanoseconds;
- _ = try encode(&enc, &peer, &n, t, &out.writer);
+ _ = try encode(&enc, &tr, &peer, t, changes + 1, "", &out.writer);
u.* = @intCast(std.Io.Clock.awake.now(io).nanoseconds - t0);
same_bytes = out.written().len;
}
@@ -893,39 +1073,77 @@ fn bench(gpa: std.mem.Allocator, io: std.Io, w: *std.Io.Writer) !void {
std.mem.sort(u64, &same, {}, std.sort.asc(u64));
try w.print("screen-state encode 200x60, every row new: p50 {d} us p99 {d} us, {d} bytes\n", .{ full[100] / 1000, full[198] / 1000, full_bytes });
try w.print("screen-state encode 200x60, nothing new: p50 {d} us p99 {d} us, {d} bytes\n", .{ same[100] / 1000, same[198] / 1000, same_bytes });
+ try w.flush();
- // Floods: a second of output as fast as ghostty takes it, a delta every
- // 16 ms when the last is acknowledged (by a replica applying it at once).
+ // Floods: a second of output as fast as ghostty takes it, a frame every
+ // 16 ms: one version, a delta for each peer (the same bytes for peers
+ // at the same base), each replica applying its own at once.
const yes = try yesStream(gpa, 1 << 16);
defer gpa.free(yes);
const shell = try shellStream(gpa);
defer gpa.free(shell);
- for ([_]struct { name: []const u8, bytes: []const u8 }{ .{ .name = "yes", .bytes = yes }, .{ .name = "varied text", .bytes = shell } }) |flood| {
- const s = try Soak.init(gpa, io, 200, 60, 16 << 20, 0);
- defer s.deinit();
+ for ([_]struct { name: []const u8, bytes: []const u8 }{ .{ .name = "yes", .bytes = yes }, .{ .name = "varied text", .bytes = shell } }) |flood| for ([_]usize{ 1, 3 }) |npeers| {
+ const a = try gpa.create(Terminal);
+ defer gpa.destroy(a);
+ a.* = try Terminal.init(io, gpa, .{ .cols = 200, .rows = 60, .max_scrollback_bytes = 16 << 20 });
+ defer a.deinit(gpa);
+ var as = a.vtStream();
+ defer as.deinit();
+ var tr: Track = .init(gpa);
+ defer tr.deinit(gpa, a);
+ var peers: [3]Peer = @splat(.{});
+ var reps: [3]Replica = @splat(.{});
+ var bs: [3]Terminal = undefined;
+ for (bs[0..npeers]) |*b| b.* = try Terminal.init(io, gpa, .{ .cols = 2, .rows = 2, .max_scrollback_bytes = 32 << 20 });
+ defer for (bs[0..npeers], reps[0..npeers]) |*b, *r| {
+ b.deinit(gpa);
+ r.deinit(gpa);
+ };
+ var applies: std.ArrayList(u64) = .empty;
+ defer applies.deinit(gpa);
+ var frames: std.ArrayList(u64) = .empty;
+ defer frames.deinit(gpa);
const start = std.Io.Clock.awake.now(io).nanoseconds;
var next = start;
var fed: u64 = 0;
var deltas: u64 = 0;
var wire: u64 = 0;
- var apply_ns: u64 = 0;
+ var version: u32 = 0;
while (true) {
const now = std.Io.Clock.awake.now(io).nanoseconds;
if (now - start >= std.time.ns_per_s) break;
- s.stream.nextSlice(flood.bytes);
+ as.nextSlice(flood.bytes);
+ version += 1;
fed += flood.bytes.len;
if (now < next) continue;
next += 16 * std.time.ns_per_ms;
- s.delta.clearRetainingCapacity();
- _ = try encode(&s.enc, &s.peer, &s.rows, s.a, &s.delta.writer);
- const a0 = std.Io.Clock.awake.now(io).nanoseconds;
- s.peer.ack(try s.rep.apply(gpa, io, s.b, s.delta.written()));
- apply_ns += @intCast(std.Io.Clock.awake.now(io).nanoseconds - a0);
- deltas += 1;
- wire += s.delta.written().len;
+ var frame_ns: u64 = 0;
+ for (peers[0..npeers], reps[0..npeers], bs[0..npeers]) |*peer, *rep, *b| {
+ out.clearRetainingCapacity();
+ const e0 = std.Io.Clock.awake.now(io).nanoseconds;
+ if (!try encode(&enc, &tr, peer, a, version, "", &out.writer)) continue;
+ frame_ns += @intCast(std.Io.Clock.awake.now(io).nanoseconds - e0);
+ const a0 = std.Io.Clock.awake.now(io).nanoseconds;
+ peer.ack((try rep.apply(gpa, io, b, out.written())).seq);
+ try applies.append(gpa, @intCast(std.Io.Clock.awake.now(io).nanoseconds - a0));
+ deltas += 1;
+ wire += out.written().len;
+ }
+ try frames.append(gpa, frame_ns);
}
- try w.print("screen-state flood of {s}: {d} MB/s of output, {d} deltas/s, {d} wire bytes/s ({d} a delta), replica apply {d} us a delta\n", .{ flood.name, fed / 1_000_000, deltas, wire, wire / @max(1, deltas), apply_ns / @max(1, deltas) / 1000 });
- }
+ std.mem.sort(u64, applies.items, {}, std.sort.asc(u64));
+ std.mem.sort(u64, frames.items, {}, std.sort.asc(u64));
+ const p = struct {
+ fn at(s: []const u64, q: usize) u64 {
+ return if (s.len == 0) 0 else s[@min(s.len - 1, s.len * q / 100)] / 1000;
+ }
+ }.at;
+ try w.print("screen-state flood of {s}, {d} peer(s): {d} MB/s of output, {d} deltas/s a peer, {d} wire bytes/s a peer ({d} a delta); encode a frame, all peers: p50 {d} us p99 {d} us; apply a delta p50 {d} us p99 {d} us\n", .{
+ flood.name, npeers, fed / 1_000_000, deltas / npeers, wire / npeers,
+ wire / @max(1, deltas), p(frames.items, 50), p(frames.items, 99), p(applies.items, 50),
+ p(applies.items, 99),
+ });
+ };
try w.flush();
}
@@ -942,7 +1160,7 @@ test "recorded streams through replicas, and the encode's cost (PARDES_SCREEN_ST
/// A shell's: prompts marked (OSC 133), colours of the three kinds, wide
/// and combined graphemes, hyperlinks, tabs, a title and a directory, long
/// lines that wrap, and a clear (ED2, ED3) now and then.
-fn shellStream(gpa: std.mem.Allocator) ![]u8 {
+pub fn shellStream(gpa: std.mem.Allocator) ![]u8 {
var out: std.Io.Writer.Allocating = .init(gpa);
errdefer out.deinit();
const w = &out.writer;
@@ -965,7 +1183,7 @@ fn shellStream(gpa: std.mem.Allocator) ![]u8 {
/// A full-screen program's: the alternate screen and its modes, a status
/// line, a scrolling region scrolled both ways, lines inserted and
/// deleted, cursor shapes, the kitty keyboard pushed and popped.
-fn tuiStream(gpa: std.mem.Allocator) ![]u8 {
+pub fn tuiStream(gpa: std.mem.Allocator) ![]u8 {
var out: std.Io.Writer.Allocating = .init(gpa);
errdefer out.deinit();
const w = &out.writer;
@@ -983,7 +1201,7 @@ fn tuiStream(gpa: std.mem.Allocator) ![]u8 {
return out.toOwnedSlice();
}
-fn yesStream(gpa: std.mem.Allocator, lines: usize) ![]u8 {
+pub fn yesStream(gpa: std.mem.Allocator, lines: usize) ![]u8 {
const out = try gpa.alloc(u8, lines * 3);
for (0..lines) |i| @memcpy(out[i * 3 ..][0..3], "y\r\n");
return out;
@@ -1021,20 +1239,24 @@ test "under a flood a delta is a screen of hashes: an unchanged row costs its ad
const s = try Soak.init(gpa, testing.io, 200, 60, 1 << 20, 1);
defer s.deinit();
s.resizes = false;
+ s.drops = false;
const yes = try yesStream(gpa, 10_000);
defer gpa.free(yes);
+ var last: []u8 = &.{};
+ defer gpa.free(last);
for (0..3) |_| {
s.stream.nextSlice(yes);
- s.delta.clearRetainingCapacity();
- try testing.expect(try encode(&s.enc, &s.peer, &s.rows, s.a, &s.delta.writer));
- s.expect.clearRetainingCapacity();
- try dumpScreen(s.a, &s.expect.writer);
+ s.changes += 1;
+ try s.send(0);
+ try testing.expectEqual(@as(usize, 1), s.flight.items.len);
+ gpa.free(last);
+ last = try gpa.dupe(u8, s.flight.items[0].delta);
try s.land();
}
// The last: 60 rows and the tail's 60, of hashes the replica holds, no
// blob; the header and counts around them.
- const d = s.delta.written();
- const at = 4 + 1 + 4 + 8 + 2 + 2 + 1 + 1 + @sizeOf(KittyFlags) + 8 + 8;
+ const d = last;
+ const at = 4 + 4 + 1 + 4 + 8 + 2 + 2 + 1 + 1 + 1 + @sizeOf(KittyFlags) + 8 + 8 + 8 + 2 + "extra".len;
const nrows = std.mem.readInt(u16, d[at..][0..2], .little);
const tail = std.mem.readInt(u16, d[at + 2 + nrows * 8 ..][0..2], .little);
const blobs = std.mem.readInt(u16, d[at + 4 + (nrows + tail) * 8 ..][0..2], .little);
@@ -1044,6 +1266,27 @@ test "under a flood a delta is a screen of hashes: an unchanged row costs its ad
try testing.expect(s.rep.holes.items.len > 0);
}
+test "several deltas in flight land in order, and a peer at the bound waits for an acknowledgement" {
+ const gpa = testing.allocator;
+ const s = try Soak.init(gpa, testing.io, 80, 24, 1 << 20, 2);
+ defer s.deinit();
+ s.resizes = false;
+ s.drops = false;
+ var line: [64]u8 = undefined;
+ for (0..bound + 5) |i| {
+ s.stream.nextSlice(try std.fmt.bufPrint(&line, "line {d}\r\n", .{i}));
+ s.changes += 1;
+ try s.send(1000);
+ }
+ // The bound's worth went; the rest wait, and are skipped.
+ try testing.expectEqual(@as(usize, bound), s.flight.items.len);
+ try s.land();
+ try s.send(1000);
+ try testing.expectEqual(@as(usize, bound), s.flight.items.len);
+ try s.settle();
+ try testing.expectEqual(@as(u64, 0), s.stats.refused);
+}
+
test "a replica's terminal pane draws as its authority's does" {
const pardes = @import("pardes.zig");
const gpa = testing.allocator;
@@ -1065,9 +1308,8 @@ test "a replica's terminal pane draws as its authority's does" {
var enc: Encoder = .init(gpa);
defer enc.deinit();
var peer: Peer = .{};
- defer peer.deinit(gpa);
- var rows: Rows = .{};
- defer rows.deinit(ta);
+ var tr: Track = .init(gpa);
+ defer tr.deinit(gpa, ta);
var rep: Replica = .{};
defer rep.deinit(gpa);
var delta: std.Io.Writer.Allocating = .init(gpa);
@@ -1077,8 +1319,8 @@ test "a replica's terminal pane draws as its authority's does" {
const bytes = try std.fmt.bufPrint(&line, "\x1b[1;3{d}m{d}\x1b[0m 漢字 e\u{301} \x1b[48;2;{d};40;60mbg\x1b[0m and then some text that wraps past the width of the pane\r\n", .{ i % 8, i, i * 4 % 256 });
a.update(.{ .output = .{ .pane = 0, .bytes = bytes } });
delta.clearRetainingCapacity();
- try testing.expect(try encode(&enc, &peer, &rows, ta, &delta.writer));
- peer.ack(try rep.apply(gpa, terminalIoForTest(), tb, delta.written()));
+ try testing.expect(try encode(&enc, &tr, &peer, ta, @intCast(i + 1), "", &delta.writer));
+ peer.ack((try rep.apply(gpa, terminalIoForTest(), tb, delta.written())).seq);
b.needs_frame = true;
_ = fa.reset(.retain_capacity);
_ = fb.reset(.retain_capacity);
diff --git a/src/tape.zig b/src/tape.zig
index 84bdce29..0609ce0b 100644
--- a/src/tape.zig
+++ b/src/tape.zig
@@ -150,6 +150,17 @@ pub const Tape = struct {
dump_check: bool = false,
dumps: usize = 0,
dump_bytes: usize = 0,
+ /// Screen-state terminals (src/screen_state.zig, docs/next-daemon.md
+ /// phase 5): an authority recording for replicas, or a replica. A
+ /// terminal's emulator is the authority's alone: its output is recorded
+ /// without its bytes (they cross as screen state), its pty writes are
+ /// not recorded, and no digest covers it. A replica's core never writes
+ /// one but by `apply`.
+ screen_state: bool = false,
+ /// A digest as one word (screen-state replicas: every unit of a pty's
+ /// output carries one, at the pty's read rate), not one a field; what
+ /// differs is then not named.
+ whole_digest: bool = false,
fn record(t: *Tape, kind: Kind, comptime T: type, v: *const T) void {
t.scratch.clearRetainingCapacity();
@@ -236,7 +247,12 @@ pub const Tape = struct {
t.noteWrites();
t.wrap(core);
}
- t.record(.input, Input, input);
+ // A terminal's output crosses as screen state, not as its bytes.
+ if (t.screen_state and input.* == .update and input.update == .output) {
+ var bare = input.*;
+ bare.update.output.bytes = &.{};
+ t.record(.input, Input, &bare);
+ } else t.record(.input, Input, input);
return .{ .outer = true };
}
@@ -251,7 +267,8 @@ pub const Tape = struct {
t.record(.done, void, &{});
if ((t.depth == 0 or t.every) and !t.no_digest) if (t.core) |core| {
var parts: Parts = undefined;
- const d = digestParts(core, &parts);
+ const whole = [1]u64{digestOf(core)};
+ const d: []const u64 = if (t.whole_digest) &whole else digestParts(core, &parts);
t.record(.digest, []const u64, &d);
};
if (t.depth == 0) t.flush();
@@ -376,8 +393,9 @@ pub const Tape = struct {
const want = walk.decode([]const u64, r, t.arena.allocator()) catch return;
const p = t.core orelse return;
var parts: Parts = undefined;
- const got = digestParts(p, &parts);
- if (!std.mem.eql(u64, got, want)) t.diverge("digest {d} differs in {s}", .{ t.digests, partsDiffer(got, want, t.arena.allocator()) });
+ const whole = [1]u64{digestOf(p)};
+ const got: []const u64 = if (want.len == 1) &whole else digestParts(p, &parts);
+ if (!std.mem.eql(u64, got, want)) t.diverge("digest {d} differs in {s}", .{ t.digests, if (want.len == 1) "the session (a digest of one word: run the authority with whole_digest off to name the field)" else partsDiffer(got, want, t.arena.allocator()) });
t.digests += 1;
}
@@ -653,6 +671,12 @@ fn Wrap(comptime i: usize) type {
fn hostCall(comptime i: usize, comptime R: type, ctx: ?*anyopaque, args: anytype) R {
const t: *Tape = @ptrCast(@alignCast(ctx.?));
const name = host_fns[i];
+ // A terminal's answers and what is typed at it from its output are the
+ // authority's to write, never a replica's: off the tape on both sides.
+ if (comptime std.mem.eql(u8, name, "pty_write")) if (t.screen_state and !t.speculating) {
+ if (!t.replay) @call(.auto, @field(t.real.vtable.*, name).?, .{t.real.ctx} ++ args);
+ return;
+ };
if (t.replay) {
// A replica that never draws is never watched: it asks no one.
if (comptime std.mem.eql(u8, name, "watched")) if (t.headless) return false;
@@ -769,6 +793,17 @@ pub fn speculating() bool {
return if (on) |t| t.speculating else false;
}
+/// Screen-state terminals, on either side (`Tape.screen_state`).
+pub fn screenState() bool {
+ return if (on) |t| t.screen_state else false;
+}
+
+/// A replica's core under screen-state terminals: its emulators are
+/// written by `apply` alone, never by its own steps.
+pub fn screenReplica() bool {
+ return if (on) |t| t.screen_state and (t.replay or t.speculating) else false;
+}
+
/// What a speculation reached is the authority's: the input is undone and
/// waits for the authority's order.
pub fn poison() void {
@@ -823,6 +858,16 @@ pub fn release(t: *Tape) void {
if (t.kept_arena) |*k| k.deinit();
}
+/// The session's digest recorded now: a batch of steps recorded without
+/// one each (`no_digest`) checked once, at its end.
+pub fn digestHere(t: *Tape) void {
+ const core = t.core orelse return;
+ var parts: Parts = undefined;
+ const whole = [1]u64{digestOf(core)};
+ const d: []const u64 = if (t.whole_digest) &whole else digestParts(core, &parts);
+ t.record(.digest, []const u64, &d);
+}
+
/// What was recorded since the last take; the tape's to reuse after.
pub fn taken(t: *Tape) []const u8 {
return t.buf.items;
diff --git a/src/terminal.zig b/src/terminal.zig
index bcb70110..6c3eeda7 100644
--- a/src/terminal.zig
+++ b/src/terminal.zig
@@ -158,6 +158,9 @@ pub const State = struct {
mouse_cell: if (enabled) ?ghostty_vt.Coordinate else void = if (enabled) null else {},
/// The kitty graphics its program placed, as drawn (TerminalImages.zig).
images: TerminalImages = if (images_enabled) .{} else {},
+ /// Counts the emulator's writes (output, a resize, its view scrolled):
+ /// a new count is a new state for its replicas (screen_state.Track).
+ changes: u32 = 0,
/// The emulator as its program has made it, for the replay digest
/// (src/walk.zig): the active screen's text, how much history is above
@@ -169,6 +172,15 @@ pub const State = struct {
/// on (docs/next-daemon.md).
pub fn digest(s: *const State, h: *pardes.walk.Hasher) void {
if (comptime !enabled) return;
+ // Under screen-state terminals the emulator is the authority's, and
+ // a replica's is what the last delta made it: compared as screens
+ // (test/replicas.zig), not step by step.
+ if (pardes.tape.screenState()) return;
+ s.digestScreen(h);
+ }
+
+ pub fn digestScreen(s: *const State, h: *pardes.walk.Hasher) void {
+ if (comptime !enabled) return;
const screen = s.vt.screens.active;
const sb = screen.pages.scrollbar();
const cur = screen.cursor;
@@ -531,6 +543,41 @@ pub fn panFor(p: *const Pardes, pane: *const Pane, r: pardes.Rect) u16 {
return @intCast(@min(pane.rows - shown, (at + 1) -| shown));
}
+/// What pardes made of a terminal's stream that its emulator does not hold
+/// (the OSC 133 cycle, MarkedHandler), for a replica's delta: phase u8,
+/// started, prompts, declined u32, continuation and lost u8, a finished
+/// command's seq u32 and status i32 (all ones: none; i32 min: no status).
+// ponytail: the output pins stay the authority's (its 9P pty/run reads them).
+pub const marks_len = 1 + 4 * 3 + 2 + 4 + 4;
+
+pub fn marksOf(state: *const State, buf: *[marks_len]u8) []const u8 {
+ if (comptime !enabled) return &.{};
+ const m = &state.stream.handler;
+ var w: std.Io.Writer = .fixed(buf);
+ w.writeByte(@intFromEnum(m.phase)) catch unreachable;
+ inline for (.{ m.started, m.prompts, m.declined }) |n| w.writeInt(u32, n, .little) catch unreachable;
+ w.writeAll(&.{ @intFromBool(m.continuation), @intFromBool(m.lost) }) catch unreachable;
+ w.writeInt(u32, if (m.finished) |f| f.seq else std.math.maxInt(u32), .little) catch unreachable;
+ w.writeInt(i32, if (m.finished) |f| f.status orelse std.math.minInt(i32) else 0, .little) catch unreachable;
+ return w.buffered();
+}
+
+/// A replica's terminal takes its authority's marks (`marksOf`).
+pub fn takeMarks(state: *State, bytes: []const u8) void {
+ if (comptime !enabled) return;
+ if (bytes.len != marks_len) return;
+ const m = &state.stream.handler;
+ m.phase = @enumFromInt(bytes[0]);
+ m.started = std.mem.readInt(u32, bytes[1..5], .little);
+ m.prompts = std.mem.readInt(u32, bytes[5..9], .little);
+ m.declined = std.mem.readInt(u32, bytes[9..13], .little);
+ m.continuation = bytes[13] != 0;
+ m.lost = bytes[14] != 0;
+ const seq = std.mem.readInt(u32, bytes[15..19], .little);
+ const status = std.mem.readInt(i32, bytes[19..23], .little);
+ m.finished = if (seq == std.math.maxInt(u32)) null else .{ .seq = seq, .status = if (status == std.math.minInt(i32)) null else status };
+}
+
/// A replica's speculation leaves an emulator be: it is the authority's
/// (docs/next-daemon.md, phase 5), so the input waits for its order.
fn authorityOnly() bool {
@@ -545,6 +592,7 @@ pub fn scrollGrid(pane: *Pane, delta: i32) void {
if (authorityOnly()) return;
const state = pane.terminal orelse return;
state.vt.screens.active.scroll(.{ .delta_row = delta });
+ state.changes +%= 1;
}
/// Is the viewport already showing the last row of output?
@@ -559,7 +607,9 @@ pub fn followOutput(pane: *Pane) void {
if (comptime !enabled) return;
if (authorityOnly()) return;
const state = pane.terminal orelse return;
+ const moved = state.vt.screens.active.pages.viewport != .active;
state.vt.screens.active.scroll(.active);
+ state.changes +%= @intFromBool(moved);
}
/// Reflow the grid. A failed reflow keeps the grid it had rather than dropping
@@ -572,6 +622,9 @@ pub fn resizeGrid(pane: *Pane, gpa: std.mem.Allocator, cols: u16, rows: u16) voi
pane.clearPointerSelection(button);
pane.sel[button].state = .none;
};
+ // A replica's emulator is sized by its authority: the next delta says.
+ if (pardes.tape.screenReplica()) return;
+ state.changes +%= 1;
state.vt.resize(gpa, .{ .cols = cols, .rows = rows }) catch {};
}
@@ -801,6 +854,7 @@ pub fn create(gpa: std.mem.Allocator, cols: u16, rows: u16) !*Pane {
});
state.stream = .init(.{ .handler = .{ .inner = state.vt.vtHandler() }, .allocator = gpa });
state.reply_len = 0;
+ state.changes = 0;
// Every field its default (create leaves them what the heap had, which
// a digest then reads: two replicas must agree, src/replica.zig).
state.reply_dropped = 0;
@@ -856,6 +910,7 @@ pub fn reviveShell(pane: *Pane) void {
/// then apply different views.
fn ingest(pane: *Pane, bytes: []const u8) void {
pane.terminal.?.stream.nextSlice(bytes);
+ pane.terminal.?.changes +%= 1;
}
test "replay ownership is terminal-only and construction rolls back on allocation failure" {
@@ -1017,6 +1072,8 @@ pub fn feedOutput(p: *Pardes, pane: *Pane, bytes: []const u8) void {
if (comptime !enabled) return;
if (pane.terminal == null) return;
if (authorityOnly()) return;
+ // A replica's emulator is what the authority's deltas make it.
+ if (pardes.tape.screenReplica()) return;
const has_positions = pane.ovl != null or pane.body.cur_pinned or pane.body.vsel.active or
pane.body.msel.active or pane.body.nsel > 0 or pane.body.last_edit != null or pane.look_at != null or
pane.body.ed_undo_len > 0 or pane.body.ed_redo_len > 0 or pointerRowCount(pane) > 0;