summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-10-29 17:01:35 -0300
committerGabriel Schneider <[email protected]>2026-10-29 19:21:09 -0300
commitc2b4f235e78735102c691677f08bd1b2403168df (patch)
tree0c13bfe79fe79901bb47e1cb8e401440bd1e1f37
parent97bb0e816513b805ca13358d8a14ba117f586403 (diff)
downloadpardes-c2b4f235e78735102c691677f08bd1b2403168df.tar.gz
pardes-c2b4f235e78735102c691677f08bd1b2403168df.zip
screen_state.zig: a terminal crosses to a replica as its screen's state, ghostty's own records by content address, a delta a screen of row hashes and the blobs the peer lacks, history fetched by absolute row
Co-Authored-By: Claude Opus 5.5 <[email protected]>
-rw-r--r--docs/next-daemon.md98
-rw-r--r--src/pardes.zig2
-rw-r--r--src/screen_state.zig1102
3 files changed, 1202 insertions, 0 deletions
diff --git a/docs/next-daemon.md b/docs/next-daemon.md
index a39484b8..e3be6af8 100644
--- a/docs/next-daemon.md
+++ b/docs/next-daemon.md
@@ -648,3 +648,101 @@ Found and fixed 2026-10-29 (`src/tty/tty.zig`, `waitInput`).
past its row's end ...`). A suite started as a shell's `&` job runs with
SIGINT ignored, so four host_io tests whose Ctrl-C must stop a `sleep`
fail there; started otherwise, they pass.
+
+## Screen-state terminal notes
+
+Built 2026-10-29 (`src/screen_state.zig`), a pure encode and apply pair
+over byte buffers for the phase 5 stream; no transport yet. Only tests
+reference it, so the tty and GUI binaries carry none of it: no symbol of
+it is linked into the tty built from this tree. The local path's A/B, base
+against that tty, is the Tty throughput notes' keystroke-to-present.
+
+- **Both kinds of blob are ghostty's own snapshot records,** not a cell
+ format of ours. The terminal-wide state (modes, colours and palette,
+ title, pwd, tab stops, mouse modes, scrolling region) is a TERMINAL
+ record. A row is the PAGE record of a one-row page the row is cloned
+ into, which carries its styles, graphemes, hyperlinks, wide cells, wrap
+ and prompt marks exactly. The replica decodes them with ghostty's
+ decoders and writes a row with `Screen.clonePartialRowGrowCapacity`.
+- **A row's address is a hash of what it shows** (Wyhash of its flags,
+ its width and its cells by value), not of its blob: ghostty keeps the
+ source page's style ids when it clones a row, so equal rows give blobs
+ that differ. The width is in the address, because a blank row is the
+ same at every width.
+- **A delta** is a header (cursor, kitty keyboard flags, the active
+ area's first row as an absolute row, the history's extent), the TERMINAL
+ record's address, an address for each active row, an address for each
+ row that scrolled off since the acknowledged state (the tail, up to a
+ screen of them), and the blobs for the addresses the peer does not hold.
+ An unchanged row costs 8 bytes.
+- **One delta per peer is in flight,** against the state it acknowledged,
+ as FrameAck keeps one frame in flight for the tty. A slow peer skips the
+ states in between. The peer holds exactly the blobs of the state it
+ acknowledged, at most two screens of rows and the meta, so the authority
+ knows what it holds without asking. At 207 ms this means at most about 5
+ deltas a second to the FreeBSD box; phase 6's predicted echo is meant to
+ cover typing there.
+- **Absolute rows** come from a tracked pin at the last active top. The
+ rows scrolled since are the distance to the new top; if the pin's page
+ was pruned, the count jumps past every row the replica could hold. A
+ resize renumbers (an epoch), and the peer starts afresh. Scrollback is
+ fetched by absolute row (`encodeRows`, `applyRows`).
+- **The replica writes into a ghostty Terminal,** a terminal pane's own,
+ so `src/terminal.zig` draws it unchanged. A test renders a replica's
+ terminal pane and its authority's in two cores: the bodies are equal,
+ cell for cell.
+- **Gates.**
+ - The soak drives an authority with pty bytes and lands deltas at
+ random, both skipping states and delaying a delta while the authority
+ moves on. Resizes and fetches of holes also come at random. After each
+ delta it checks the replica's screen against the authority's as
+ encoded, and every history row the replica holds outside its holes
+ against the authority's row at that number.
+ - It passed with synthetic shell, TUI and `yes` streams at 4 seeds (in
+ the unit tests, with a 64 KB scrollback so it prunes). It also passed
+ with 197 recorded streams at 3 seeds each (the test that
+ PARDES_SCREEN_STATE=<dir> turns on): the 192 pane outputs of the snapshot scripts'
+ tapes, plus real vim, nvim, htop, less and btop sessions recorded
+ through a pty. Its corpus and recorder are in `.scratch/daemon/term`.
+- **Numbers** (ReleaseFast: `PARDES_SCREEN_STATE=<dir> zig build core-test
+ -Dplatform=tty -Doptimize=ReleaseFast -Dtest-filter=screen_state`, which
+ runs under std.testing's checking allocator):
+ - Encode, 200x60, every row new: p50 250 us, p99 487 us, 29.8 KB.
+ - Encode, 200x60, nothing new: p50 71 us, p99 139 us, 534 bytes. That
+ is the 60 rows hashed and the TERMINAL record encoded to hash it.
+ - Under `yes` as fast as ghostty takes it in-process (9 to 12 MB/s),
+ with a delta every 16 ms: 62 deltas a second, 63 KB/s on the wire,
+ 1 KB a delta (60 rows and the tail's 60, all held). That is bounded by
+ the frame rate, not the output.
+ - Under varied text at 36 to 55 MB/s: 355 KB/s on the wire, 5.6 KB a
+ delta.
+ - The replica applies a `yes` delta in 2.4 ms, most of it pushing the
+ rows scrolled past into its history (a row at a time). A delta of
+ varied text applies in 0.24 ms under the C allocator and 0.95 ms
+ under the checking one.
+- **What proved wrong in the design.**
+ - "Scrollback fetched on demand" alone loses rows. A row that changed
+ after the last delta and then scrolled off would sit stale in the
+ replica's history. The tail fixes the rows that scrolled within a
+ screen. Older ones, which the replica never saw or saw before they
+ last changed, are holes: rows it must fetch before it shows them.
+ - The address had to include the row's width, as above. The soak found
+ this: a replica reused an 80-column blank row after a resize to 10.
+ - ghostty narrows pages lazily, so an active row can be wider than its
+ terminal: only the terminal's columns are hashed and encoded.
+- **Not done, or a gap.**
+ - Kitty images in terminals.
+ - pardes's own state derived from the stream is not carried: its
+ `MarkedHandler` prompt phase, command-output pins and the replies it
+ writes to the pty. ghostty's prompt marks on rows do cross.
+ - The view's scroll offset is per client and is not sent.
+ - A replica's core must not resize its pane's terminal itself; the
+ authority sizes it.
+ - The replica's history extent follows its own pruning under the
+ authority's limit, so it can be a page off, and its oldest rows can
+ be ones the authority has dropped.
+ - A fetch sends every row as a blob (phase 6's cache will send
+ addresses). No zstd.
+ - A replica pushes a flood's rows into its history one at a time.
+ - The integration into the stream and the cores (a replica pane's
+ State fed by `apply` instead of `.output`) is the next piece.
diff --git a/src/pardes.zig b/src/pardes.zig
index b5e729bb..228d97fa 100644
--- a/src/pardes.zig
+++ b/src/pardes.zig
@@ -63,6 +63,7 @@ pub const pdf = panes.Pdf.pdf;
pub const memory = @import("memory.zig");
pub const tape = @import("tape.zig");
pub const walk = @import("walk.zig");
+pub const screen_state = if (terminal_panes) @import("screen_state.zig") else struct {};
pub const image = @import("image.zig");
pub const dump = @import("dump.zig");
pub const lsp = @import("lsp/lsp.zig");
@@ -509,6 +510,7 @@ test {
_ = @import("Tables.zig");
_ = @import("Handover.zig");
_ = @import("walk.zig");
+ _ = screen_state;
}
pub const Builtin = builtins.registry.Builtin();
diff --git a/src/screen_state.zig b/src/screen_state.zig
new file mode 100644
index 00000000..51c2ec30
--- /dev/null
+++ b/src/screen_state.zig
@@ -0,0 +1,1102 @@
+//! Screen-state terminals (docs/next-daemon.md, "Terminals cross as
+//! authoritative screen state", phase 5). A replica is sent a terminal's
+//! state, never its pty's bytes, so a `cat` of a gigabyte costs it screens.
+//!
+//! The authority encodes a delta for one peer: a header (the cursor, the
+//! active area's first row as an absolute row, the history's extent), the
+//! content address of the terminal-wide state, the content address of each
+//! row of the active area, and the blobs behind the addresses the peer does
+//! not hold. Both kinds of blob are ghostty's own snapshot records, so they
+//! cross exactly: the terminal-wide state is a TERMINAL record (modes,
+//! colours, title, tab stops...), and a row is the PAGE record of a one-row
+//! page (its styles, graphemes, hyperlinks, wide cells, wrap and prompt
+//! 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.
+//!
+//! 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).
+//! Rows that scroll off its active area go into its history, made what the
+//! authority's are by the delta's tail (their addresses, up to a screen of
+//! them). Older ones it never saw, or saw before they last changed, are
+//! holes there, fetched by absolute row on demand (`encodeRows`,
+//! `applyRows`).
+const std = @import("std");
+const vt = @import("ghostty-vt");
+const snapshot = vt.snapshot;
+const Terminal = vt.Terminal;
+const Page = vt.page.Page;
+const Row = vt.page.Row;
+const Pin = vt.Pin;
+const Screen = vt.Screen;
+
+// ponytail: 64 bits: two of a million distinct rows collide about once in
+// 4*10^7 sessions; phase 6's cache, shared across sessions, wants 128.
+pub const Hash = u64;
+
+/// What a row shows, hashed: its wrap and prompt flags, and each of its
+/// first `cols` cells up to the last one that is not blank, with its style,
+/// grapheme and hyperlink by value. Not the page's style or hyperlink ids,
+/// nor its derived flags. Its width is in it: a blob is a row that wide.
+/// (A page can be wider than its terminal: ghostty narrows them lazily.)
+pub fn rowHash(page: *Page, row: *Row, cols: u16) Hash {
+ var h = std.hash.Wyhash.init(0);
+ h.update(&.{rowFlags(row)});
+ h.update(std.mem.asBytes(&cols));
+ const all = page.getCells(row);
+ const cells = all[0..@min(cols, all.len)];
+ var n = cells.len;
+ while (n > 0 and @as(u64, @bitCast(cells[n - 1])) == 0) n -= 1;
+ for (cells[0..n]) |*c| {
+ var word = c.*;
+ word.style_id = 0;
+ h.update(std.mem.asBytes(&@as(u64, @bitCast(word))));
+ if (c.style_id != 0) h.update(std.mem.asBytes(&page.styles.get(page.memory, c.style_id).hash()));
+ if (c.hasGrapheme()) h.update(std.mem.sliceAsBytes(page.lookupGrapheme(c).?));
+ if (c.hyperlink) if (page.lookupHyperlink(c)) |id|
+ h.update(std.mem.asBytes(&page.hyperlink_set.get(page.memory, id).hash(page.memory)));
+ }
+ return h.final();
+}
+
+fn rowFlags(row: *const Row) u8 {
+ return @as(u8, @intFromBool(row.wrap)) | @as(u8, @intFromBool(row.wrap_continuation)) << 1 |
+ @as(u8, @intFromEnum(row.semantic_prompt)) << 2;
+}
+
+/// The authority's absolute row numbers for one terminal: its primary
+/// screen's active area starts at `top`, and a row `d` above it in its
+/// history is `top - d`. Kept by a tracked pin at the last active top, so
+/// it counts the rows scrolled since. A resize renumbers (`epoch`).
+pub const Rows = struct {
+ pin: ?*Pin = null,
+ top: u64 = 0,
+ epoch: u32 = 0,
+ cols: u16 = 0,
+ rows: u16 = 0,
+
+ pub fn update(n: *Rows, t: *Terminal) !void {
+ const pages = &t.screens.get(.primary).?.pages;
+ const top = pages.getTopLeft(.active);
+ const y = pages.pointFromPin(.screen, top).?.screen.y;
+ if (n.pin) |p| {
+ if (t.cols != n.cols or t.rows != n.rows) n.epoch +%= 1;
+ // The last top was pruned away: every row the peer has is
+ // older than the oldest row here.
+ const was: ?u32 = if (p.garbage) null else if (pages.pointFromPin(.screen, p.*)) |pt| pt.screen.y else null;
+ n.top += if (was) |w| y -| w else @as(u64, y) + t.rows;
+ p.* = top;
+ } else {
+ n.pin = try pages.trackPin(top);
+ n.top = y;
+ }
+ n.cols = t.cols;
+ n.rows = t.rows;
+ }
+
+ pub fn deinit(n: *Rows, t: *Terminal) void {
+ if (n.pin) |p| t.screens.get(.primary).?.pages.untrackPin(p);
+ n.* = .{};
+ }
+
+ /// The pin of absolute row `abs`, if the terminal still has it.
+ fn pinAt(n: *const Rows, t: *Terminal, abs: u64) ?Pin {
+ return pinOf(&t.screens.get(.primary).?.pages, n.top, abs);
+ }
+};
+
+fn pinOf(pages: anytype, top: u64, abs: u64) ?Pin {
+ if (abs >= top) return pages.pin(.{ .active = .{ .y = std.math.cast(u32, abs - top) orelse return null } });
+ const d = std.math.cast(usize, top - abs) orelse return null;
+ return pages.getTopLeft(.active).up(d);
+}
+
+/// The authority's scratch: a one-row page each blob is copied into
+/// (fresh, so the blob holds that row's styles alone) and encoded from.
+pub const Encoder = struct {
+ gpa: std.mem.Allocator,
+ scratch: ?Page = null,
+ meta: std.Io.Writer.Allocating,
+ pins: std.ArrayList(Pin) = .empty,
+ needed: std.ArrayList(struct { pin: Pin, hash: Hash }) = .empty,
+
+ pub fn init(gpa: std.mem.Allocator) Encoder {
+ return .{ .gpa = gpa, .meta = .init(gpa) };
+ }
+
+ pub fn deinit(e: *Encoder) void {
+ if (e.scratch) |*s| s.deinit();
+ e.meta.deinit();
+ e.pins.deinit(e.gpa);
+ e.needed.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 {
+ 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) |_| {
+ if (e.scratch) |*s| {
+ if (std.meta.eql(s.capacity, cap)) s.reinit() else {
+ s.deinit();
+ e.scratch = null;
+ }
+ }
+ if (e.scratch == null) e.scratch = try Page.init(cap);
+ const s = &e.scratch.?;
+ s.cloneRowFrom(page, s.getRow(0), row) catch {
+ // Room for this row: everything doubled until it fits.
+ cap.styles *|= 2;
+ cap.grapheme_bytes *|= 2;
+ cap.hyperlink_bytes *|= 2;
+ cap.string_bytes *|= 2;
+ continue;
+ };
+ break;
+ } else return error.RowTooBig;
+ var rw: snapshot.record.Writer = .init(e.gpa, w);
+ defer rw.deinit();
+ try snapshot.page.encode(&e.scratch.?, &rw);
+ }
+};
+
+/// 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,
+
+ pub fn deinit(peer: *Peer, gpa: std.mem.Allocator) void {
+ peer.known.deinit(gpa);
+ peer.sent.deinit(gpa);
+ }
+
+ 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;
+ }
+
+ /// Start the peer afresh (it joined again, or lost its state).
+ pub fn reset(peer: *Peer) void {
+ peer.fresh = true;
+ peer.in_flight = false;
+ peer.known.clearRetainingCapacity();
+ }
+};
+
+/// 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.
+const flag_reset: u8 = 1;
+const KittyFlags = @FieldType(Screen, "kitty_keyboard");
+
+/// 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);
+ }
+ const meta = std.hash.Wyhash.hash(0, e.meta.written());
+ try peer.sent.put(gpa, meta, {});
+
+ const screen = t.screens.active;
+ const pages = &t.screens.get(.primary).?.pages;
+ try out.writeInt(u32, peer.seq +% 1, .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(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));
+ // 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, history, .little);
+ try out.writeInt(u16, t.rows, .little);
+
+ // 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).?);
+ e.needed.clearRetainingCapacity();
+ for (e.pins.items, 0..) |p, i| {
+ if (i == t.rows) try out.writeInt(u16, tail, .little);
+ 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 });
+ }
+ if (tail == 0) try out.writeInt(u16, 0, .little);
+ const meta_new = !peer.known.contains(meta);
+ 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());
+ }
+ 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);
+ try out.writeInt(u64, need.hash, .little);
+ try out.writeInt(u32, @intCast(blob.written().len), .little);
+ try out.writeAll(blob.written());
+ }
+ peer.top = n.top;
+ peer.seq +%= 1;
+ peer.in_flight = true;
+ peer.fresh = false;
+ peer.epoch = n.epoch;
+ return true;
+}
+
+/// 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);
+ 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;
+ 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);
+ 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, count, .little);
+ try out.writeAll(blobs.written());
+}
+
+/// A replica's terminal: what it was sent, written into a ghostty Terminal.
+pub const Replica = struct {
+ seq: u32 = 0,
+ epoch: u32 = 0,
+ meta: Hash = 0,
+ top: u64 = 0,
+ /// The address of each active row as the Terminal holds it, a list per
+ /// screen (primary, alternate).
+ held: [2]std.ArrayList(Hash) = .{ .empty, .empty },
+ /// The blobs of the last state applied: what the authority takes it to
+ /// hold. Owned copies.
+ blobs: std.AutoHashMapUnmanaged(Hash, []u8) = .empty,
+ /// History rows it cannot vouch for (written blank, or seen before
+ /// they last changed), `[lo, hi)` absolute, oldest first.
+ holes: std.ArrayList([2]u64) = .empty,
+ /// The one-row page each row blob is decoded into.
+ scratch: ?Page = null,
+
+ pub fn deinit(r: *Replica, gpa: std.mem.Allocator) void {
+ for (&r.held) |*h| h.deinit(gpa);
+ var it = r.blobs.valueIterator();
+ while (it.next()) |b| gpa.free(b.*);
+ r.blobs.deinit(gpa);
+ r.holes.deinit(gpa);
+ 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 {
+ var in: std.Io.Reader = .fixed(bytes);
+ const seq = try in.takeInt(u32, .little);
+ const flags = try in.takeByte();
+ 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();
+ 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 nrows = try in.takeInt(u16, .little);
+ const hashes = try in.take(@as(usize, nrows) * 8);
+ const tail = try in.takeInt(u16, .little);
+ const tails = try in.take(@as(usize, tail) * 8);
+ // The delta's blobs, borrowed from `bytes` while it applies.
+ var fresh: std.AutoHashMapUnmanaged(Hash, []const u8) = .empty;
+ defer fresh.deinit(gpa);
+ for (0..try in.takeInt(u16, .little)) |_| {
+ const h = try in.takeInt(u64, .little);
+ try fresh.put(gpa, h, try in.take(try in.takeInt(u32, .little)));
+ }
+ const blobOf = struct {
+ fn of(rr: *Replica, f: *const std.AutoHashMapUnmanaged(Hash, []const u8), h: Hash) ![]const u8 {
+ if (f.get(h)) |b| return b;
+ if (rr.blobs.get(h)) |b| return b;
+ return error.MissingBlob;
+ }
+ }.of;
+
+ if (flags & flag_reset != 0 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) {
+ 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.
+ const primary = t.screens.get(.primary).?;
+ try scrollUp(primary, history);
+ if (history > 0) try r.holes.append(gpa, .{ top -| history, top });
+ } else {
+ defer next.deinit(gpa);
+ try takeMeta(t, &next, io, gpa);
+ }
+ r.meta = meta;
+ }
+ 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.
+ 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));
+ const held = &r.held[0];
+ if (k >= held.items.len) held.clearRetainingCapacity() else {
+ std.mem.copyForwards(Hash, held.items, held.items[@intCast(k)..]);
+ held.shrinkRetainingCapacity(held.items.len - @as(usize, @intCast(k)));
+ }
+ if (top - tail > r.top) try r.holes.append(gpa, .{ r.top, top - tail });
+ r.top = top;
+ }
+ 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)];
+ const blank = blankHash(t.cols);
+ while (held.items.len < nrows) try held.append(gpa, blank);
+ held.shrinkRetainingCapacity(nrows);
+ for (0..nrows) |y| {
+ const h = std.mem.readInt(u64, hashes[y * 8 ..][0..8], .little);
+ if (h == held.items[y]) continue;
+ try r.writeRow(gpa, screen, screen.pages.pin(.{ .active = .{ .y = @intCast(y) } }).?, try blobOf(r, &fresh, h));
+ held.items[y] = h;
+ }
+ screen.cursorReload();
+ 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.kitty_keyboard = kitty;
+
+ // Hold the blobs of this state, and no others.
+ var keep: std.AutoHashMapUnmanaged(Hash, []u8) = .empty;
+ errdefer keep.deinit(gpa);
+ try keep.ensureTotalCapacity(gpa, nrows + tail + 1);
+ for (0..nrows + tail + 1) |i| {
+ const h = if (i == nrows + tail) meta else if (i < nrows)
+ std.mem.readInt(u64, hashes[i * 8 ..][0..8], .little)
+ else
+ std.mem.readInt(u64, tails[(i - nrows) * 8 ..][0..8], .little);
+ if (keep.contains(h)) continue;
+ const b = if (r.blobs.fetchRemove(h)) |kv| kv.value else try gpa.dupe(u8, try blobOf(r, &fresh, h));
+ keep.putAssumeCapacity(h, b);
+ }
+ var old = r.blobs.valueIterator();
+ while (old.next()) |b| gpa.free(b.*);
+ r.blobs.deinit(gpa);
+ r.blobs = keep;
+ r.seq = seq;
+ return seq;
+ }
+
+ /// The holes in `[lo, hi)`: the rows to fetch before showing them.
+ pub fn missing(r: *const Replica, lo: u64, hi: u64, out: *std.ArrayList([2]u64), gpa: std.mem.Allocator) !void {
+ for (r.holes.items) |hole| {
+ const a = @max(lo, hole[0]);
+ const b = @min(hi, hole[1]);
+ if (a < b) try out.append(gpa, .{ a, b });
+ }
+ }
+
+ /// 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);
+ if (try in.takeInt(u32, .little) != r.epoch) return; // numbered before a resize
+ const primary = t.screens.get(.primary).?;
+ 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;
+ const p = pinOf(&primary.pages, r.top, abs) orelse continue;
+ try r.writeRow(gpa, primary, p, blob);
+ try r.fill(gpa, abs);
+ }
+ }
+
+ fn inHole(r: *const Replica, abs: u64) bool {
+ for (r.holes.items) |hole| if (abs >= hole[0] and abs < hole[1]) return true;
+ return false;
+ }
+
+ /// Row `abs` is written: out of the holes.
+ fn fill(r: *Replica, gpa: std.mem.Allocator, abs: u64) !void {
+ for (r.holes.items, 0..) |*hole, i| {
+ if (abs < hole[0] or abs >= hole[1]) continue;
+ if (abs == hole[0]) hole[0] += 1 else if (abs + 1 == hole[1]) hole[1] -= 1 else {
+ try r.holes.insert(gpa, i + 1, .{ abs + 1, hole[1] });
+ r.holes.items[i][1] = abs;
+ }
+ if (r.holes.items[i][0] == r.holes.items[i][1]) _ = r.holes.orderedRemove(i);
+ return;
+ }
+ }
+
+ /// Holes older than this history's oldest row are gone with it.
+ fn trimHoles(r: *Replica, primary: *Screen) void {
+ const oldest = r.top -| (primary.pages.total_rows - primary.pages.rows);
+ var i: usize = 0;
+ while (i < r.holes.items.len) {
+ const hole = &r.holes.items[i];
+ hole[0] = @max(hole[0], oldest);
+ if (hole[0] >= hole[1]) _ = r.holes.orderedRemove(i) else i += 1;
+ }
+ }
+
+ fn writeRow(r: *Replica, gpa: std.mem.Allocator, screen: *Screen, p: Pin, blob: []const u8) !void {
+ var reader: std.Io.Reader = .fixed(blob);
+ var dec: snapshot.page.Decoder = undefined;
+ try dec.init(&reader, try snapshot.record.nextHeader(&reader));
+ const cap = dec.capacity();
+ if (r.scratch) |*s| {
+ if (std.meta.eql(s.capacity, cap)) s.reinit() else {
+ s.deinit();
+ r.scratch = null;
+ }
+ }
+ if (r.scratch == null) r.scratch = try Page.init(cap);
+ const src = &r.scratch.?;
+ try dec.decode(src, gpa);
+ if (src.size.cols != screen.pages.cols) return error.BadRow;
+ _ = screen.clonePartialRowGrowCapacity(p.node, p.y, src, src.getRow(0), 0, src.size.cols);
+ }
+};
+
+/// `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.
+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();
+}
+
+/// `rowHash` of a row never written.
+fn blankHash(cols: u16) Hash {
+ var h = std.hash.Wyhash.init(0);
+ h.update(&.{0});
+ h.update(std.mem.asBytes(&cols));
+ return h.final();
+}
+
+/// The terminal-wide state of `next` (a decoded TERMINAL record) into `t`,
+/// whose screens and pages stay: what `snapshot.terminal.decode` sets.
+fn takeMeta(t: *Terminal, next: *Terminal, io: std.Io, gpa: std.mem.Allocator) !void {
+ if (t.cols != next.cols or t.rows != next.rows) try t.resize(gpa, .{ .cols = next.cols, .rows = next.rows });
+ t.width_px = next.width_px;
+ t.height_px = next.height_px;
+ t.scrolling_region = next.scrolling_region;
+ t.status_display = next.status_display;
+ t.previous_char = next.previous_char;
+ t.cursor = next.cursor;
+ t.modes = next.modes;
+ t.flags.shell_redraws_prompt = next.flags.shell_redraws_prompt;
+ t.flags.modify_other_keys_2 = next.flags.modify_other_keys_2;
+ t.flags.mouse_event = next.flags.mouse_event;
+ t.flags.mouse_format = next.flags.mouse_format;
+ t.flags.mouse_shift_capture = next.flags.mouse_shift_capture;
+ t.flags.password_input = next.flags.password_input;
+ t.mouse_shape = next.mouse_shape;
+ t.colors = next.colors;
+ try t.setPwd(next.getPwd() orelse "");
+ try t.setTitle(next.getTitle() orelse "");
+ std.mem.swap(@TypeOf(t.tabstops), &t.tabstops, &next.tabstops);
+ const key = next.screens.active_key;
+ if (key != t.screens.active_key) {
+ if (t.screens.get(key) == null) _ = try t.screens.getInit(io, gpa, key, .{ .cols = t.cols, .rows = t.rows, .max_scrollback_bytes = 0 });
+ t.screens.switchTo(key);
+ }
+}
+
+// ---- checks: a replica against its authority, cell for cell ----
+
+/// What a row shows, written out value by value (not `rowHash`'s walk):
+/// its flags, then each cell's word without its page's ids, its style, its
+/// grapheme and its hyperlink's URI.
+fn dumpRow(page: *Page, row: *Row, cols: u16, w: *std.Io.Writer) !void {
+ try w.print("{d}:", .{rowFlags(row)});
+ const all = page.getCells(row);
+ for (all[0..@min(cols, all.len)]) |*c| {
+ var word = c.*;
+ word.style_id = 0;
+ try w.print(" {x}", .{@as(u64, @bitCast(word))});
+ if (c.style_id != 0) try snapshot.style.encode(page.styles.get(page.memory, c.style_id).*, w);
+ if (c.hasGrapheme()) for (page.lookupGrapheme(c).?) |cp| try w.print("+{x}", .{cp});
+ if (c.hyperlink) if (page.lookupHyperlink(c)) |id| try w.print("@{s}", .{page.hyperlink_set.get(page.memory, id).uri.slice(page.memory)});
+ }
+ try w.writeByte('\n');
+}
+
+/// 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 {
+ 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 "",
+ });
+ try w.writeAll(std.mem.asBytes(&t.modes.values));
+ try w.writeAll(std.mem.asBytes(&screen.kitty_keyboard));
+ try w.print(" mouse {s} {s} {s}\n", .{ @tagName(t.flags.mouse_event), @tagName(t.flags.mouse_format), @tagName(t.mouse_shape) });
+ for (t.colors.palette.current) |c| try w.print("{x}{x}{x}", .{ c.r, c.g, c.b });
+ try w.writeByte('\n');
+ var it = screen.pages.rowIterator(.right_down, .{ .active = .{} }, null);
+ while (it.next()) |p| try dumpRow(p.node.page(), p.rowAndCell().row, t.cols, w);
+}
+
+/// 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.
+pub const Soak = struct {
+ gpa: std.mem.Allocator,
+ io: std.Io,
+ a: *Terminal,
+ stream: vt.TerminalStream,
+ rows: Rows = .{},
+ enc: Encoder,
+ peer: Peer = .{},
+ 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,
+ got: std.Io.Writer.Allocating,
+ wait: u32 = 0,
+ resizes: bool = true,
+ stats: struct { deltas: u64 = 0, bytes: u64 = 0, fetched: u64 = 0, history_checked: 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);
+ errdefer gpa.destroy(s);
+ 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 });
+ s.* = .{
+ .gpa = gpa,
+ .io = io,
+ .a = a,
+ .stream = a.vtStream(),
+ .enc = .init(gpa),
+ .b = b,
+ .prng = .init(seed),
+ .delta = .init(gpa),
+ .expect = .init(gpa),
+ .got = .init(gpa),
+ };
+ return s;
+ }
+
+ pub fn deinit(s: *Soak) void {
+ const gpa = s.gpa;
+ s.stream.deinit();
+ s.rows.deinit(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();
+ s.got.deinit();
+ gpa.destroy(s);
+ }
+
+ /// `bytes` into the authority in random pieces, a step after each.
+ pub fn feed(s: *Soak, bytes: []const u8) !void {
+ var at: usize = 0;
+ const random = s.prng.random();
+ while (at < bytes.len) {
+ const n = @min(bytes.len - at, 1 + random.uintLessThan(usize, 512));
+ s.stream.nextSlice(bytes[at..][0..n]);
+ at += n;
+ try s.step();
+ }
+ }
+
+ pub fn step(s: *Soak) !void {
+ const random = s.prng.random();
+ 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) });
+ }
+ 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();
+ 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()));
+ 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());
+ return error.ReplicaDiffers;
+ }
+ try s.checkHistory();
+ }
+
+ /// 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;
+ const pages = &s.b.screens.get(.primary).?.pages;
+ const have = pages.total_rows - pages.rows;
+ var ra: std.Io.Writer.Allocating = .init(s.gpa);
+ defer ra.deinit();
+ var rb: std.Io.Writer.Allocating = .init(s.gpa);
+ defer rb.deinit();
+ var d: u64 = 1;
+ while (d <= have) : (d += 1 + d / 8) {
+ 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;
+ ra.clearRetainingCapacity();
+ rb.clearRetainingCapacity();
+ try dumpRow(pa.node.page(), pa.rowAndCell().row, s.a.cols, &ra.writer);
+ try dumpRow(pb.node.page(), pb.rowAndCell().row, s.b.cols, &rb.writer);
+ if (!std.mem.eql(u8, ra.written(), rb.written())) {
+ std.debug.print("history row {d} ({d} above the top) differs\n", .{ abs, d });
+ reportDiff(ra.written(), rb.written());
+ return error.ReplicaHistoryDiffers;
+ }
+ s.stats.history_checked += 1;
+ }
+ }
+
+ /// Some holes fetched from the authority, as a replica scrolled back.
+ fn fetch(s: *Soak) !void {
+ if (s.rep.holes.items.len == 0) return;
+ const random = s.prng.random();
+ const hole = s.rep.holes.items[random.uintLessThan(usize, s.rep.holes.items.len)];
+ const lo = hole[0] + random.uintLessThan(u64, hole[1] - hole[0]);
+ 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 s.rep.applyRows(s.gpa, s.b, out.written());
+ s.stats.fetched += hi - lo;
+ try s.checkHistory();
+ }
+};
+
+fn reportDiff(want: []const u8, got: []const u8) void {
+ var wl = std.mem.splitScalar(u8, want, '\n');
+ var gl = std.mem.splitScalar(u8, got, '\n');
+ var line: usize = 0;
+ while (true) : (line += 1) {
+ const a = wl.next();
+ const b = gl.next();
+ if (a == null and b == null) return;
+ if (a != null and b != null and std.mem.eql(u8, a.?, b.?)) continue;
+ std.debug.print("line {d} differs:\n authority {s}\n replica {s}\n", .{ line, a orelse "(none)", b orelse "(none)" });
+ return;
+ }
+}
+
+/// Drive one stream through a soak and land a last delta of its end.
+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();
+ return s.stats;
+}
+
+/// Every recorded pty stream in `dir` (a `-<cols>x<rows>` in its name sizes
+/// it, 80x24 otherwise) through a soak at three seeds, then the encode's
+/// cost and the bytes floods put on the wire: the test below, when
+/// PARDES_SCREEN_STATE names the directory (numbers from a ReleaseFast
+/// build: `zig build core-test -Doptimize=ReleaseFast -Dtest-filter=screen_state`).
+fn perf(gpa: std.mem.Allocator, io: std.Io, dir_path: []const u8, w: *std.Io.Writer) !void {
+ var dir = try std.Io.Dir.cwd().openDir(io, dir_path, .{ .iterate = true });
+ defer dir.close(io);
+ var it = dir.iterate();
+ var files: usize = 0;
+ var failed: usize = 0;
+ while (try it.next(io)) |entry| {
+ if (entry.kind != .file) continue;
+ const bytes = try dir.readFileAlloc(io, entry.name, gpa, .unlimited);
+ defer gpa.free(bytes);
+ var cols: u16 = 80;
+ var rows: u16 = 24;
+ if (std.mem.lastIndexOfScalar(u8, entry.name, '-')) |dash| {
+ const size = std.mem.sliceTo(entry.name[dash + 1 ..], '.');
+ if (std.mem.indexOfScalar(u8, size, 'x')) |x| {
+ cols = std.fmt.parseInt(u16, size[0..x], 10) catch cols;
+ rows = std.fmt.parseInt(u16, size[x + 1 ..], 10) catch rows;
+ }
+ }
+ files += 1;
+ for (0..3) |seed| {
+ const st = soak(gpa, io, bytes, cols, rows, 128 * 1024, seed, seed != 0) catch |err| {
+ try w.print("screen-state {s} seed {d}: {s}\n", .{ entry.name, seed, @errorName(err) });
+ 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 });
+ }
+ }
+ try w.print("screen-state corpus: {d} streams x 3 seeds, {d} failed\n", .{ files, failed });
+ try w.flush();
+ try bench(gpa, io, w);
+}
+
+fn bench(gpa: std.mem.Allocator, io: std.Io, w: *std.Io.Writer) !void {
+ const t = try gpa.create(Terminal);
+ defer gpa.destroy(t);
+ t.* = try Terminal.init(io, gpa, .{ .cols = 200, .rows = 60, .max_scrollback_bytes = 16 << 20 });
+ defer t.deinit(gpa);
+ var stream = t.vtStream();
+ 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;
+ // A full 200x60 screen, every row new to the peer: each a blob.
+ var full: [200]u64 = undefined;
+ var same: [200]u64 = undefined;
+ var full_bytes: usize = 0;
+ var same_bytes: usize = 0;
+ for (&full, &same, 0..) |*f, *u, rep| {
+ for (0..60) |y| {
+ var lw: std.Io.Writer = .fixed(&line);
+ try lw.print("\x1b[{d};1H\x1b[0;3{d};4{d}m{d} {d} ", .{ y + 1, rep % 8, y % 8, rep, y });
+ while (lw.end < 190) try lw.writeAll("\x1b[1mbold\x1b[22m text ");
+ stream.nextSlice(lw.buffered());
+ }
+ 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);
+ f.* = @intCast(std.Io.Clock.awake.now(io).nanoseconds - t0);
+ full_bytes = out.written().len;
+ peer.ack(peer.seq);
+ out.clearRetainingCapacity();
+ t0 = std.Io.Clock.awake.now(io).nanoseconds;
+ _ = try encode(&enc, &peer, &n, t, &out.writer);
+ u.* = @intCast(std.Io.Clock.awake.now(io).nanoseconds - t0);
+ same_bytes = out.written().len;
+ }
+ std.mem.sort(u64, &full, {}, std.sort.asc(u64));
+ 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 });
+
+ // 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).
+ 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();
+ 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;
+ 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);
+ 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;
+ }
+ 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 });
+ }
+ try w.flush();
+}
+
+const testing = std.testing;
+
+test "recorded streams through replicas, and the encode's cost (PARDES_SCREEN_STATE=<dir>)" {
+ const dir = std.c.getenv("PARDES_SCREEN_STATE") orelse return error.SkipZigTest;
+ var buf: [4096]u8 = undefined;
+ // stderr: a test's stdout is the build runner's.
+ var out = std.Io.File.stderr().writer(testing.io, &buf);
+ try perf(testing.allocator, testing.io, std.mem.span(dir), &out.interface);
+}
+
+/// 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 {
+ var out: std.Io.Writer.Allocating = .init(gpa);
+ errdefer out.deinit();
+ const w = &out.writer;
+ try w.writeAll("\x1b]0;a shell\x07\x1b]7;file://host/home/someone\x07");
+ for (0..400) |i| {
+ try w.print("\x1b]133;A\x07$ \x1b]133;B\x07ls -l {d}\r\n\x1b]133;C\x07", .{i});
+ try w.print("\x1b[1;31mred\x1b[0m \x1b[4;38;5;{d}m256\x1b[0m \x1b[38;2;{d};100;200;48;5;17mtrue\x1b[0m 漢字 e\u{301} 👩\u{200d}💻 ", .{ i % 256, i % 256 });
+ try w.print("\x1b]8;;https://example.com/{d}\x07link\x1b]8;;\x07\tx\r\n", .{i});
+ if (i % 7 == 0) {
+ for (0..12) |_| try w.writeAll("a long line that wraps ");
+ try w.writeAll("\r\n");
+ }
+ try w.writeAll("\x1b]133;D;0\x07");
+ if (i % 97 == 96) try w.writeAll("\x1b[H\x1b[2J\x1b[3J");
+ if (i % 50 == 0) try w.print("\x1b]2;title {d}\x07\x1b]4;1;rgb:{x:0>2}/20/30\x07", .{ i, i % 256 });
+ }
+ return out.toOwnedSlice();
+}
+
+/// 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 {
+ var out: std.Io.Writer.Allocating = .init(gpa);
+ errdefer out.deinit();
+ const w = &out.writer;
+ try w.writeAll("before the program\r\n\x1b[?1049h\x1b[?25l\x1b[?1000h\x1b[?1006h\x1b[?2004h\x1b[?1h\x1b[>1u\x1b[4 q\x1b[H\x1b[2J");
+ for (0..300) |f| {
+ try w.print("\x1b[1;1H\x1b[44;97m status {d} \x1b[K\x1b[0m", .{f});
+ try w.print("\x1b[3;18r\x1b[18;1H\r\n\x1b[3{d}mline {d}\x1b[0m", .{ f % 8, f });
+ if (f % 3 == 0) try w.writeAll("\x1b[3;1H\x1bM\x1b[2mreversed in\x1b[0m");
+ if (f % 5 == 0) try w.writeAll("\x1b[6;1H\x1b[2L\x1b[9;1H\x1b[M");
+ try w.writeAll("\x1b[r");
+ try w.print("\x1b[{d};{d}H\x1b[7m*\x1b[0m\x1b[{d}X", .{ 2 + f % 20, 1 + (f * 7) % 70, f % 5 });
+ if (f % 11 == 0) try w.writeAll("\x1b[?25h\x1b[6 q") else if (f % 11 == 5) try w.writeAll("\x1b[?25l\x1b[2 q");
+ }
+ try w.writeAll("\x1b[<u\x1b[?1049l\x1b[?25h\x1b[?1000l\x1b[0 qafter the program\r\n");
+ return out.toOwnedSlice();
+}
+
+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;
+}
+
+test "a replica's screen is its authority's, cell for cell, as states are skipped, resized and fetched" {
+ const gpa = testing.allocator;
+ const io = testing.io;
+ const shell = try shellStream(gpa);
+ defer gpa.free(shell);
+ const tui = try tuiStream(gpa);
+ defer gpa.free(tui);
+ const yes = try yesStream(gpa, 30_000);
+ defer gpa.free(yes);
+ var fetched: u64 = 0;
+ var history: u64 = 0;
+ for (0..4) |seed| {
+ // A small scrollback, so it wraps (pruned at its oldest pages).
+ for ([_][]const u8{ shell, tui, yes }) |bytes| {
+ const st = soak(gpa, io, bytes, 80, 24, 64 * 1024, seed, seed != 0) catch |err| {
+ std.debug.print("soak seed {d} stream {d} bytes: {s}\n", .{ seed, bytes.len, @errorName(err) });
+ return err;
+ };
+ try testing.expect(st.deltas > 10);
+ fetched += st.fetched;
+ history += st.history_checked;
+ }
+ }
+ // The holes were fetched, and history rows compared, at all.
+ try testing.expect(fetched > 0 and history > 0);
+}
+
+test "under a flood a delta is a screen of hashes: an unchanged row costs its address alone" {
+ const gpa = testing.allocator;
+ const s = try Soak.init(gpa, testing.io, 200, 60, 1 << 20, 1);
+ defer s.deinit();
+ s.resizes = false;
+ const yes = try yesStream(gpa, 10_000);
+ defer gpa.free(yes);
+ 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);
+ 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 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);
+ if (d.len >= (nrows + tail) * 8 + 128) std.debug.print("delta {d} bytes: {d} rows, {d} tail, {d} blobs\n", .{ d.len, nrows, tail, blobs });
+ try testing.expectEqual(@as(u16, 0), blobs);
+ try testing.expect(d.len < (nrows + tail) * 8 + 128);
+ try testing.expect(s.rep.holes.items.len > 0);
+}
+
+test "a replica's terminal pane draws as its authority's does" {
+ const pardes = @import("pardes.zig");
+ const gpa = testing.allocator;
+ const a = try pardes.Pardes.init(gpa, .{ .tty_only = true, .cols = 60, .rows = 16 });
+ defer a.deinit();
+ const b = try pardes.Pardes.init(gpa, .{ .tty_only = true, .cols = 60, .rows = 16 });
+ defer b.deinit();
+ while (a.nextEffect()) |_| {}
+ while (b.nextEffect()) |_| {}
+ var fa = std.heap.ArenaAllocator.init(gpa);
+ defer fa.deinit();
+ var fb = std.heap.ArenaAllocator.init(gpa);
+ defer fb.deinit();
+ // Laid out once, so both panes have their size before the first delta.
+ _ = try a.render(fa.allocator());
+ _ = try b.render(fb.allocator());
+ const ta = &a.panes[0].?.terminal.?.vt;
+ const tb = &b.panes[0].?.terminal.?.vt;
+ var enc: Encoder = .init(gpa);
+ defer enc.deinit();
+ var peer: Peer = .{};
+ defer peer.deinit(gpa);
+ var rows: Rows = .{};
+ defer rows.deinit(ta);
+ var rep: Replica = .{};
+ defer rep.deinit(gpa);
+ var delta: std.Io.Writer.Allocating = .init(gpa);
+ defer delta.deinit();
+ var line: [256]u8 = undefined;
+ for (0..60) |i| {
+ 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()));
+ b.needs_frame = true;
+ _ = fa.reset(.retain_capacity);
+ _ = fb.reset(.retain_capacity);
+ const sa = try a.render(fa.allocator());
+ const sb = try b.render(fb.allocator());
+ const r = a.rects[0];
+ // The body: below the pane's tag row.
+ for (r.y + 1..r.y + r.h) |y| for (r.x..r.x + r.w) |x| {
+ const ca = sa.at(@intCast(x), @intCast(y));
+ const cb = sb.at(@intCast(x), @intCast(y));
+ if (!ca.visuallyEqual(cb)) {
+ std.debug.print("step {d}: cell {d},{d}: '{s}' vs '{s}'\n", .{ i, x, y, ca.grapheme(), cb.grapheme() });
+ return error.ReplicaDrawsDifferently;
+ }
+ };
+ }
+}
+
+fn terminalIoForTest() std.Io {
+ return std.Io.Threaded.global_single_threaded.io();
+}