//! 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. //! //! 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). //! 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, 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, .blob = .init(gpa) }; } pub fn deinit(e: *Encoder) void { if (e.scratch) |*s| s.deinit(); 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 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) |_| { 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); } }; /// 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, and its /// history's rows. changes: u32 = 0, history: u64 = 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) }; } /// `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; const primary = &t.screens.get(.primary).?.pages; tr.history = primary.total_rows - primary.rows; 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, /// The history rows its replica holds as holes, absolute, as the /// replica keeps them (Replica.apply's rule, from what it was sent): /// what `fill` sends before a step reads them. top: u64 = 0, holes: std.ArrayListUnmanaged([2]u64) = .empty, pub fn deinit(peer: *Peer, gpa: std.mem.Allocator) void { peer.holes.deinit(gpa); } /// Every version up to `seq` has landed. pub fn ack(peer: *Peer, seq: u32) void { 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 lost its state, or never had one. pub fn reset(peer: *Peer) void { var holes = peer.holes; holes.clearRetainingCapacity(); peer.* = .{ .holes = holes }; } /// Its replica's holes once it applies a delta to `tr`'s newest version /// against `base`, as Replica.apply makes them. fn noteSent(peer: *Peer, gpa: std.mem.Allocator, tr: *const Track, base: ?*const Known, rows: u16) !void { const top = tr.rows.top; const history = tr.history; if (base) |b| { if (top > peer.top) { const tail = @min(top -| b.top, rows, history); if (top - peer.top >= @as(u64, rows) + history) { peer.holes.clearRetainingCapacity(); if (history > tail) try peer.holes.append(gpa, .{ top - history, top - tail }); } else if (top - tail > peer.top) try peer.holes.append(gpa, .{ peer.top, top - tail }); } } else { peer.holes.clearRetainingCapacity(); if (history > 0) try peer.holes.append(gpa, .{ top - history, top }); } peer.top = top; // Those older than its history's oldest row are gone with it. var i: usize = 0; while (i < peer.holes.items.len) { const hole = &peer.holes.items[i]; hole[0] = @max(hole[0], top -| history); if (hole[0] >= hole[1]) _ = peer.holes.orderedRemove(i) else i += 1; } } }; /// 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 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; } try out.writeAll(tr.cache.written()); try peer.noteSent(e.gpa, tr, base, t.rows); 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; 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, 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, top, .little); try out.writeInt(u64, history, .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 base, // which may have changed after it was sent. e.listed.clearRetainingCapacity(); e.needed.clearRetainingCapacity(); 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); try needBlob(e, base, p, h); } 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, tr.meta_hash, .little); try out.writeInt(u32, @intCast(tr.meta.written().len), .little); try out.writeAll(tr.meta.written()); } for (e.needed.items) |need| { 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(e.blob.written().len), .little); try out.writeAll(e.blob.written()); } } /// 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, for a /// replica that holds them as holes: u32 epoch, u32 blobs, each u64 hash, /// u32 length, bytes, then u32 rows, each u64 row and u64 hash. A blob goes /// once a message (a flood's rows are one). // ponytail: blobs once a message, not once a peer: phase 6's content cache. 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 rows: std.Io.Writer.Allocating = .init(e.gpa); defer rows.deinit(); e.listed.clearRetainingCapacity(); var nblobs: u32 = 0; var nrows: u32 = 0; var abs = lo; // 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 h = rowHash(p.node.page(), p.rowAndCell().row, t.cols); try rows.writer.writeInt(u64, abs, .little); try rows.writer.writeInt(u64, h, .little); nrows += 1; if ((try e.listed.getOrPut(e.gpa, h)).found_existing) continue; e.blob.clearRetainingCapacity(); try e.rowBlob(p.node.page(), p.rowAndCell().row, t.cols, &e.blob.writer); try blobs.writer.writeInt(u64, h, .little); try blobs.writer.writeInt(u32, @intCast(e.blob.written().len), .little); try blobs.writer.writeAll(e.blob.written()); nblobs += 1; } try out.writeInt(u32, tr.rows.epoch, .little); try out.writeInt(u32, nblobs, .little); try out.writeAll(blobs.written()); try out.writeInt(u32, nrows, .little); try out.writeAll(rows.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(); } 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); 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 (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 (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. 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 { 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 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; const held = &r.held[0]; if (k >= @as(u64, t.rows) + history) { // A flood: nothing held here is in this state. The rows stay // where they are, renumbered: the active ones written below, // the tail too, the rest holes (blanked when they come into // view, `blank`), not grown and trimmed by the thousand. As // many more as the history is longer there, grown blank. const have = primary.pages.total_rows - primary.pages.rows; if (have < history) try scrollUp(primary, history - have); held.clearRetainingCapacity(); try held.appendNTimes(gpa, unknown, t.rows); r.holes.clearRetainingCapacity(); if (history > tail) try r.holes.append(gpa, .{ top - history, top - tail }); } else { try scrollUp(primary, @min(k, @as(u64, t.rows) + history)); 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; } // 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)); } const screen = t.screens.active; const held = &r.held[@intFromEnum(t.screens.active_key)]; const blank_row = blankHash(t.cols); while (held.items.len < nrows) try held.append(gpa, blank_row); 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.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; 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 = seq, .extra = extra }; } /// The holes in `[lo, hi)` blank: until their rows come, a hole shows /// nothing rather than what that row held before a flood renumbered it. pub fn blank(r: *const Replica, t: *Terminal, lo: u64, hi: u64) void { const primary = t.screens.get(.primary).?; const oldest = r.top -| (primary.pages.total_rows - primary.pages.rows); for (r.holes.items) |hole| { const a = @max(lo, hole[0], oldest); const b = @min(hi, hole[1], r.top); if (a >= b) continue; primary.clearRows(.{ .screen = .{ .y = @intCast(a - oldest) } }, .{ .screen = .{ .y = @intCast(b - 1 - oldest) } }, false); } } /// 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 }); } } /// 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); if (try in.takeInt(u32, .little) != r.epoch) return; // numbered before a resize const primary = t.screens.get(.primary).?; var blobs: std.AutoHashMapUnmanaged(Hash, []const u8) = .empty; defer blobs.deinit(gpa); for (0..try in.takeInt(u32, .little)) |_| { const h = try in.takeInt(u64, .little); try blobs.put(gpa, h, try in.take(try in.takeInt(u32, .little))); } for (0..try in.takeInt(u32, .little)) |_| { const abs = try in.takeInt(u64, .little); const blob = blobs.get(try in.takeInt(u64, .little)) orelse return error.MissingBlob; // 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); } } 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. 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); 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(); } /// No row's address: what a row whose content is not known is held as. const unknown: Hash = std.math.maxInt(Hash); /// `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 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; 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)); 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 /// (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, 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 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, now: u64 = 0, resizes: bool = true, 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); 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); // 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), .got = .init(gpa), }; return s; } pub fn deinit(s: *Soak) void { const gpa = s.gpa; s.stream.deinit(); 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); for (s.flight.items) |f| { gpa.free(f.delta); gpa.free(f.expect); } s.flight.deinit(gpa); 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]); s.changes +%= 1; at += n; try s.step(); } } 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; } // 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(); } /// 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, 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.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); 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.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); 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)); s.rep.blank(s.b, lo, hi); var out: std.Io.Writer.Allocating = .init(s.gpa); defer out.deinit(); 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(); } }; 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, 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.settle(); return s.stats; } /// Every recorded pty stream in `dir` (a `-x` 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} 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 }); 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 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; var changes: u32 = 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()); } 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, &tr, &peer, t, changes, "", &out.writer); f.* = @intCast(std.Io.Clock.awake.now(io).nanoseconds - t0); full_bytes = out.written().len; // The same screen again as a new version: every row held. out.clearRetainingCapacity(); t0 = std.Io.Clock.awake.now(io).nanoseconds; _ = 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; } 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 }); try w.flush(); // 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. Under the C // allocator, as a replica's (the checking one costs an apply 4x). try floods(gpa, std.heap.c_allocator, io, w); } fn floods(gpa: std.mem.Allocator, ca: std.mem.Allocator, io: std.Io, w: *std.Io.Writer) !void { var enc: Encoder = .init(ca); defer enc.deinit(); var out: std.Io.Writer.Allocating = .init(ca); defer out.deinit(); 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| for ([_]usize{ 1, 3 }) |npeers| { const a = try ca.create(Terminal); defer ca.destroy(a); a.* = try Terminal.init(io, ca, .{ .cols = 200, .rows = 60, .max_scrollback_bytes = 16 << 20 }); defer a.deinit(ca); var as = a.vtStream(); defer as.deinit(); var tr: Track = .init(ca); defer tr.deinit(ca, 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, ca, .{ .cols = 2, .rows = 2, .max_scrollback_bytes = 32 << 20 }); defer for (bs[0..npeers], reps[0..npeers], peers[0..npeers]) |*b, *r, *peer| { b.deinit(ca); r.deinit(ca); peer.deinit(ca); }; 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 version: u32 = 0; while (true) { const now = std.Io.Clock.awake.now(io).nanoseconds; if (now - start >= std.time.ns_per_s) break; as.nextSlice(flood.bytes); version += 1; fed += flood.bytes.len; if (now < next) continue; next += 16 * std.time.ns_per_ms; 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(ca, 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); } 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(); } const testing = std.testing; test "recorded streams through replicas, and the encode's cost (PARDES_SCREEN_STATE=)" { 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. pub 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. pub 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[ 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; 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.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 = 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); 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 "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; 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 tr: Track = .init(gpa); defer tr.deinit(gpa, 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, &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); 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(); }