diff options
| -rw-r--r-- | docs/next-daemon.md | 232 | ||||
| -rw-r--r-- | src/body_layer.zig | 3 | ||||
| -rw-r--r-- | src/echo.zig | 781 | ||||
| -rw-r--r-- | src/pardes.zig | 7 | ||||
| -rw-r--r-- | src/replica.zig | 16 | ||||
| -rw-r--r-- | src/rollback.zig | 5 | ||||
| -rw-r--r-- | src/terminal.zig | 2 | ||||
| -rw-r--r-- | test/replicas.zig | 766 |
8 files changed, 1781 insertions, 31 deletions
diff --git a/docs/next-daemon.md b/docs/next-daemon.md index 0fe72b76..5039c81e 100644 --- a/docs/next-daemon.md +++ b/docs/next-daemon.md @@ -2312,3 +2312,235 @@ Not done, and why: 9p(1) is still one round trip per message (1 s for a read at 207 ms). A python helper for remote scripting could pipeline the same way; nobody scripts that way yet. + +## Phase 6: predicted echo notes + +Built 2026-10-30 (`src/echo.zig`; hooks in `src/replica.zig`; a field on +the core and one call at the end of `body_layer.renderBody`; `zig build +replicas -- --echo`). Transport-free like part B: proven in part A's +in-process harness, carried by the remote client. A key typed into a +terminal pane goes to the authority, and its echo comes back as a delta a +round trip later: 207 ms a character in a shell on the FreeBSD box. The +replica now draws it at once, mosh's way, and the authority's screen +confirms or takes it back. Decisions at the forks, with the ponytail lens: + +- **Presentation, the replica's own.** The overlay is `Replica.echo`; the + core points at it (`Pardes.echo`, `.local`, and in rollback.zig's + `unsaved`, so the copy neither saves nor puts it back). No digest, dump + or tape sees it, and the core's emulator stays the authority's. Its + only write into what is drawn is `Echo.paint`, at the end of + `renderBody` for a terminal pane: the cells predicted and the cursor + after them, over the body as drawn. A terminal's body is painted + straight onto the grid (a body layer is a file's with context rows), + and the tty and the GUI both draw the grid's cells and cursor, so both + get it. A session's own core has `echo` null: one null test a terminal + pane a frame, and no overlay. +- **What is predicted:** a printable ASCII character at the cursor, + Backspace, Left and Right, typed into the view's terminal in tty mode + (keys going to its program), on the primary screen, at the live bottom, + with the cursor shown. Never for a chord, Enter, Tab, Esc, Up and Down, + a paste, or anything on the alternate screen (vim never sees one). More + narrowly, so as never to draw what the line editor would not: + - a character only over a blank cell or the same character (typing + along a fish suggestion); a line edited in its middle, or a + suggestion left, is the shell's to redraw; + - not in the last column (wrap is the program's); + - Backspace only at the end of the line, over a prompt's input or a + predicted character; Left over the same; Right over typed text, a + prompt's input in the colour of the cell before it (past the text's + end fish's Right takes its suggestion). + Each prediction is a cell (an absolute row, the authority's numbering + that the delta's header carries) and the cursor after it; a newer key's + cell replaces an older one's, as mosh's overlay does. +- **Judged once the authority has the key and its echo has had time.** + Each unit of the replica's own says which of its keys the authority + stepped (`Echo.confirmed`). A stream that loses nothing keeps the order + the authority sent in, and it sends what it owes of the terminals + before it steps an input, so a delta that arrives after that unit was + made after the key was written. 50 ms after the unit (`grace_ns`, + mosh's ECHO_TIMEOUT: the shell's echo, then the authority's next frame) + each applied delta judges it: a cell the screen shows goes (confirmed), + one it does not is a misprediction and every prediction goes. A + predicted space (Backspace's too) is judged neither way, as mosh's + blanks are; the cursor after the newest key is judged with it. With no + delta at all (nothing changed: no echo), a frame judges it 250 ms + later (`stale_ns`). +- **A key that is not predicted** (Enter, Tab, a chord, or one the rules + above refuse) is the next to wait for: once the authority has it, every + prediction made before it goes, judged neither way (the deltas from + then show that key's doing, which nothing predicted). The keys typed + behind it wait (`deferred`) until its grace has passed; then those the + authority does not have yet are predicted, in order, over the screen + that shows its doing (`catchUp`). One the authority has whose grace is + not over puts that off a little. So the characters typed straight on + after Tab are drawn where the completion left the cursor once it shows + (a round trip and 50 ms after Tab), the rest at once, and never where + the cursor was before it. + Found by the harness: the first version predicted nothing until the + wait was over, and every key typed in that time became a new wait, so a + word typed after Tab or Enter at 207 ms was all late (p90 242 ms). An + input that is not a key into this terminal (a click, a command) has no + deferral: where the keys after it go is not known here until the + authority has it. +- **Shown where the echo is vouched for.** At a shell's prompt, pardes's + OSC 133 marks (phase input: a B and no C since) and the cursor's own + semantic content say its line editor echoes: drawn at once. Elsewhere + (`cat`, a shell without pardes's marks) only once an echo was confirmed + there since the last Enter, Tab or chord (`trusted`), so the first + character of each line waits a round trip. A key before the last one + not predicted vouches for nothing after it: the harness found the + characters of `sudo ls`, confirmed after its Enter, vouching for the + password prompt that Enter brought up. After a misprediction that was + drawn, nothing is drawn until an echo is confirmed again (`doubt`). A + password prompt or a program that ignores what is typed confirms none, + so nothing typed there is ever drawn. +- **Underlined off a prompt only.** At a prompt the marks vouch for the + echo, and an underline trailing every character for a round trip at + 207 ms is noise; off one the trust is mosh's inference, and the + underline says so. After a misprediction nothing is drawn at all, which + mosh's adaptive underline approximates. +- **No protocol change.** No echo acknowledgement crosses (mosh's + `echo_ack`): the replica's own units stand for it, and the grace for its + 50 ms. No termios flag crosses either: a program's echo is inferred from + confirmations, as mosh does. + +The hook for the remote client (its `Replica` and stream as they are): +- `Replica.init(..., screens = true)` points its core at its echo + (`core.echo = &r.echo`). A replica made another way (the remote line's + `initDump`) does that itself once its core exists. +- Per key: nothing more. `r.input(ev)` predicts after its settle, in + `r.view`. +- Per unit: nothing more. `r.confirm(unit)` tells it which of its keys the + authority has. +- Per delta: nothing more. `r.screen(msg)` judges after each delta it + applies. +- Per frame, before drawing: `if (r.echoFrame()) dirty = true;` judges + what is stale, predicts the keys deferred whose wait is over, and says + whether the overlay changed since the last call; `r.echo.changed` says + the same between frames (after `r.input` and `r.screen`), for a client + that draws only when its state moved (the remote line's `moved`). +- Draw its own view (`core.view == r.view`): the overlay is drawn in no + other, and over a terminal in tty mode only. +- The clock is the monotonic one (`FrameStats.nowNs`) unless `r.echo.now` + is set (the harness's virtual clock). + +Measured. + +- **The harness** (`zig build replicas -Dplatform=tty -- --echo`): one + authority and one replica over part A's delayed, jittered link, the + authority's pty a shell played in the harness (`FakeShell`): a line + editor at a prompt with pardes's marks and Tab completion, and the + programs the corpus runs in it. Each key's echo comes 2 ms after the + authority writes it. The client types a corpus of 222 keys at a + typist's pace (60 to 180 ms a key) and in bursts (12 to 60 ms): lines at + a prompt, Backspace, Left and Right, Tab typed straight on, `sudo` and + its password, vim, a program that ignores what is typed, `cat` (the + kernel's echo, no marks), and a line typed before the last one's prompt. + Each client frame (60 Hz, its own phase) is what its screen shows: its + core rendered, the overlay where it is drawn. Ground truth is the + authority's screen right after each key's echo. +- **Key to its character on the client's screen** (the simulation's clock; + 20 seeds, 3060 keys the shell echoed at each RTT, ms, without → with): + + | | 30 ms | 80 ms | 207 ms | + |---|---|---|---| + | p50 | 49.8 → 8.7 | 102.3 → 8.7 | 239.0 → 8.9 | + | p90 | 59.0 → 15.2 | 111.8 → 15.4 | 247.9 → 15.8 | + | max | 66.9 → 65.3 | 121.5 → 114.5 | 261.7 → 251.6 | + + With it, a key waits for the client's next frame, 0 to 16.7 ms. The tty + host draws an input's frame at once, so a real client's is the frame's + cost. The tail is by design: at 207 ms the p90 of the characters typed + straight on after Tab is 38 ms, of a line typed ahead of its prompt + 48 ms, and of `cat`'s 179 ms (its first characters of a line wait for an + echo to be confirmed); every other part's is 14 to 15 ms. +- **Accuracy** (the same runs, 4440 keys at each RTT): 3718 to 3720 + predicted (84%); 714 to 722 not, by the rules (each Enter, Tab, Ctrl-C, + Ctrl-D and Esc, everything typed in vim, and the characters behind a + key not predicted that the screen showed by the time it was over). Of + those predicted, 3238 to 3240 were what the authority's screen showed + right after the echo; the other 480, at each RTT, are exactly the + password's and the ignoring program's 24 a seed, and none was drawn. + Wrong characters drawn: none, at every RTT (0 keys, 0 frames). Frames a + password's or the ignoring program's key was drawn: 0. vim's keys + predicted: 0. The overlay judged 97 to 132 cells against the screen as + mispredictions, all of them undrawn ones (the password's, the ignoring + program's), and no cursor. Every frame drawn with a prediction shown + (13,083 to 21,009 a cell) had each predicted cell where it was + predicted in the rendered surface. +- **Costs** (ReleaseFast): `paint` p50 50 to 63 ns, p99 86 to 155 ns; the + replica's render with a prediction shown p50 54 µs; a key's `typed` is + a few array scans. +- **No divergence**: the replicas harness (ReleaseFast, 20 seeds x 120 + inputs x 3 clients): none diverged, none unequal, 23,547 deltas checked + and none wrong; its deltas a second (76.3, 75.7, 71.7) are part B's to + the decimal. +- **No local regression.** A session's own core draws no overlay + (`echo` is null: a unit test says the authority's core has none). + `pardes-perf-live --live` (base's driver), main (vtzpkxwu) and this + line interleaved A B A ... A on the perf cores (3 runs of the new one, 4 + of main), ReleaseFast; the median of the runs' p50s, new/main: + + | | new/main | A/A (main) | + |---|---|---| + | key-down, present / core | 0.99 / 0.99 | 1.00 / 0.99 | + | key-right | 0.99 / 1.00 | 1.00 / 1.01 | + | edit-char | 0.97 / 0.98 | 0.99 / 0.98 | + | page-down | 0.85 / 0.92 | 0.82 / 0.85 | + | wheel | 0.97 / 0.99 | 0.98 / 0.98 | + | `yes \| head -c 32M` wall | 1.11 | 1.04 | + | a 1M-line open | 0.93 | 1.01 | + + Every cell's runs overlap main's. The `yes` cell is the kernel's (Tty + throughput notes): main's own runs read 4.5 to 7.1 s in the A/B and 5.8 + to 7.6 s in the A/A, this line's 5.0 to 7.2 s. What the local path + gained: a null test a terminal pane a frame, and 8 bytes of core. + +The gates: +- Unit tests (`zig build core-test -Dtest-filter=echo`): keys typed at a + prompt drawn at once in the rendered surface, unflagged, the cursor past + them, then confirmed by the echo, Backspace too, and the replica's digest + the authority's; a password prompt draws nothing typed and lets it go + when stale, and vim's alternate screen predicts nothing; a misprediction + takes every prediction back and hides the next until an echo is + confirmed, and after Tab the keys behind it are drawn where the + completion left the cursor, or not at all if the screen already shows + them. +- `zig build replicas -- --echo` fails on any divergence, unequal end, + wrong delta, drawn password or ignored key, predicted vim key, or cell + rendered otherwise than predicted; it passes at 20 seeds, Debug and + ReleaseFast. `zig build replicas` passes at 20 seeds, ReleaseFast (and 4 + in Debug). +- Unit tests tty (`zig build unit-test -Dplatform=tty`, its perf gate + too), the full `core-test`, and the 113 snapshot scripts pass; the GUI + build's echo tests pass (`core-test -Dplatform=gui`). + +Not done, and why: +- ASCII only: a width table would let the rest of Unicode in (`kindOf`). +- A line edited in its middle (insert, Backspace), Delete, Home, End, the + readline chords, word moves and a paste are not predicted: the line + editor redraws what is right of the cursor, which a prediction would + have to guess. Each waits a round trip, and the keys typed straight on + behind it are drawn when it is over. +- A key typed after an input that is not a key into this terminal (a + click, a command) and that the replica could not apply itself waits for + the authority, and so do the keys after it until a pause: where they go + is not known here until the authority has it. +- The echo is inferred, not told. No termios flag and no echo + acknowledgement cross. A password prompt is safe because nothing typed + there is ever confirmed. A shell at its prompt that does not echo a key + (zsh's vi command mode) has it drawn until its grace passes, about a + round trip and 50 ms, and then nothing more until an echo is confirmed; + so does a program that turns echo off mid-line in `cat`'s plain echo. +- An echo later than about 30 ms on the authority's host (a loaded box) + makes a drawn character go when judged and come back with the echo: a + flicker, never a wrong character. The grace could follow the measured + echo delay. +- A shell without pardes's marks (fish's own marks, a shell started + without the integration) is trusted only by confirmation, so each line's + first character waits a round trip, as in `cat`. +- The GUI was not run: it draws the grid's cells and cursor that the + harness checks in the rendered surface, and its build compiles and + passes the echo tests. +- The remote client (the other line) wires it: `initDump`'s core, the + frame hook, its `moved`. diff --git a/src/body_layer.zig b/src/body_layer.zig index 5a8d51e5..7a4103c3 100644 --- a/src/body_layer.zig +++ b/src/body_layer.zig @@ -481,6 +481,9 @@ pub fn renderBody(p: *Pardes, s: *Surface, arena: std.mem.Allocator, pane: *Pane } } + // A replica's predicted echo, over what its authority's screen shows. + if (p.echo) |e| if (pane.isTerminal()) e.paint(p, s, pane, id, tx, tw, body_y, body_h, active); + if (rail) |bar| if (bar.rect.h > 0) { // The rail covers the notice bands too: nothing else paints those // two gutter columns, so a gap there keeps the frame-wide border diff --git a/src/echo.zig b/src/echo.zig new file mode 100644 index 00000000..4acd3d11 --- /dev/null +++ b/src/echo.zig @@ -0,0 +1,781 @@ +//! Predicted echo for a replica's terminal panes, mosh's way +//! (docs/next-daemon.md, "Phase 6: predicted echo notes"). A key typed into +//! a terminal goes to the authority, and its echo comes back as screen state +//! a round trip later: this shows it at once. +//! +//! Presentation only. The overlay is the replica's own (`Pardes.echo`, a +//! `.local` field the rollback copy skips), painted over a terminal's body +//! after it is drawn (`paint`, from body_layer.renderBody, which the tty and +//! the GUI share). The core's emulator stays the authority's, and no digest +//! sees any of this. +//! +//! What is predicted: a printable character at the cursor, backspace, and +//! left and right, in tty mode on the primary screen at the live bottom. Any +//! other input this replica could not apply itself (Enter, Tab, a chord, a +//! paste, a click) stops prediction until the authority has confirmed it and +//! its echo has had `grace` to come back: predictions start again from the +//! screen's own cursor. So a key typed after Tab waits a round trip; it is +//! never drawn where the completion was not. +//! +//! Judged as mosh does, once the authority confirmed the key and `grace` +//! passed: at a delta, a cell the screen shows goes, and one it does not is +//! a misprediction, and every prediction goes. With no delta (nothing +//! changed: no echo), a frame judges it `stale` later. Shown at once at a +//! shell's prompt (pardes's OSC 133 marks say its line editor echoes); +//! elsewhere only once an echo was confirmed there since the last key that +//! was not predicted (`cat`, a shell without marks), and underlined; never +//! after a shown misprediction until an echo is confirmed again. A password +//! prompt or a program that ignores input confirms none, so nothing typed +//! there is ever shown. +const std = @import("std"); +const pardes = @import("pardes.zig"); +const terminal = pardes.panes.terminal; +const Pardes = pardes.Pardes; +const Pane = pardes.Pane; +const Surface = pardes.Surface; +const Key = pardes.Key; + +const ms = std.time.ns_per_ms; +/// After the authority confirmed a key, how long its echo has to come back +/// before a delta that does not show it makes a misprediction (mosh's +/// ECHO_TIMEOUT): the shell's echo, then the authority's next frame. +// ponytail: fixed; a loaded host's later echo makes a drawn character go and +// come back. The echo delay measured per terminal would be the bound. +pub const grace_ns = 50 * ms; +/// With no delta at all, how much longer a frame waits to judge a key. +pub const stale_ns = 250 * ms; +const never = std.math.maxInt(u64); +/// Cells predicted at once: a line typed a round trip ahead. +const max = 64; + +/// A cell predicted: `cp` at column `x` of absolute row `row` (the +/// authority's numbering, screen_state's), a space for a cell backspace +/// cleared; `was` what the screen showed there before; `seq` the key's. +pub const Cell = struct { x: u16, row: u64, cp: u21, was: u21, seq: u32, due: u64 = never }; +pub const Cursor = struct { x: u16, row: u64, seq: u32, due: u64 = never }; + +pub const Stats = struct { + /// Keys into a terminal predicted, and not. + predicted: u32 = 0, + unpredicted: u32 = 0, + /// Cells the screen showed when judged; cells and cursors it did not. + confirmed: u32 = 0, + mispredicted: u32 = 0, + cursor_missed: u32 = 0, +}; + +pub const Echo = struct { + /// Off: nothing predicted (the harness's baseline). + on: bool = true, + /// The harness's clock (ns); the monotonic one when null. + now: ?u64 = null, + /// Its client's view, and the terminal it predicts into. + view: u8 = 0, + pane: u8 = 0, + serial: u32 = 0, + /// Each terminal's last delta: its active area's first row, absolute. + tops: [pardes.MAX_PANES]u64 = @splat(0), + cells: [max]Cell = undefined, + n: u8 = 0, + cursor: ?Cursor = null, + /// The newest of its client's inputs the authority confirmed. + acked: u32 = 0, + /// The newest input not predicted, and when its echo is due: nothing is + /// predicted until then. `wait_key`: it was a key forwarded to this + /// terminal (no other pane's), so the keys typed into it meanwhile wait + /// in `deferred`, to be predicted over the screen that shows its doing. + wait: u32 = 0, + wait_due: u64 = 0, + wait_key: bool = false, + deferred: [max]Deferred = undefined, + nd: u8 = 0, + /// An echo confirmed since the last key not predicted: shown off a + /// prompt too. A shown misprediction since the last confirmed echo: + /// shown nowhere. + trusted: bool = false, + doubt: bool = false, + /// What it draws changed: the client draws a frame. + changed: bool = false, + stats: Stats = .{}, + /// Each key's prediction as it is made, when set (the harness's; on + /// the C heap). + log: ?*std.ArrayListUnmanaged(Predicted) = null, + + pub const Predicted = struct { seq: u32, cell: ?Cell, cursor: Cursor }; + + fn time(e: *const Echo) u64 { + return e.now orelse pardes.FrameStats.nowNs(); + } + + const Deferred = struct { seq: u32, kind: ?Kind, due: u64 = never }; + + fn drop(e: *Echo) void { + if (e.n > 0 or e.cursor != null) e.changed = true; + e.n = 0; + e.cursor = null; + } + + fn waiting(e: *const Echo) bool { + return e.acked < e.wait or e.time() < e.wait_due; + } + + fn waitFor(e: *Echo, seq: u32, key: bool) void { + e.wait = seq; + e.wait_due = never; + e.wait_key = key; + e.nd = 0; + } + + /// Its client's input `seq`, after the replica took it: `applied`, + /// it was applied here at once (so it was no key into a terminal). + pub fn typed(e: *Echo, c: *Pardes, view: u8, ev: pardes.Event, seq: u32, applied: bool) void { + e.view = view; + if (applied or comptime !terminal.enabled) return; + switch (ev) { + // ponytail: a motion or focus report a program asked for could + // move its cursor; the judgement catches that. + .mouse => |m| if (m.kind == .motion) return, + .pointer_leave, .focus => return, + else => {}, + } + const id = keyboardPane(c, view) orelse { + // Another pane's, or not a key: where the keys after it go is + // not known here until the authority has it. ponytail: so they + // wait for it too, each, until a pause. + e.waitFor(seq, false); + return; + }; + if (id != e.pane or c.panes[id].?.serial != e.serial) { + e.drop(); + e.nd = 0; + e.pane = @intCast(id); + e.serial = c.panes[id].?.serial; + } + const kind = kindOf(ev); + const key = forwarded(c, ev); + // A key that is not one of those predicted says nothing of the + // program the keys after it reach (Enter: a password prompt's). + if (kind == null) e.trusted = false; + if (!e.on) { + e.stats.unpredicted += 1; + return e.waitFor(seq, key); + } + // Behind keys still deferred: after them, in order. + e.catchUp(c); + if (e.waiting() or e.nd > 0) { + if (e.wait_key and key and e.nd < max) { + e.deferred[e.nd] = .{ .seq = seq, .kind = kind }; + e.nd += 1; + return; + } + e.stats.unpredicted += 1; + return e.waitFor(seq, false); + } + if (kind) |k| if (e.predict(c.panes[id].?, k, seq)) { + e.stats.predicted += 1; + e.changed = true; + return; + }; + e.stats.unpredicted += 1; + e.waitFor(seq, key); + } + + /// The wait over (its key's doing on the screen), the keys deferred + /// behind it that the screen does not show yet are predicted over it, + /// in order; those it shows are not. One the authority has whose echo + /// may be on its way puts it off until its grace has passed. + fn catchUp(e: *Echo, c: *Pardes) void { + if (e.nd == 0 or e.waiting()) return; + const now = e.time(); + var i: usize = 0; + while (i < e.nd and e.deferred[i].due <= now) i += 1; + if (i < e.nd and e.deferred[i].due != never) return; + e.stats.unpredicted += @intCast(i); + const pane = c.panes[e.pane] orelse return e.waitFor(e.wait, false); + if (pane.serial != e.serial) return e.waitFor(e.wait, false); + while (i < e.nd) : (i += 1) { + const d = e.deferred[i]; + if (d.kind) |k| if (e.predict(pane, k, d.seq)) { + e.stats.predicted += 1; + e.changed = true; + continue; + }; + // The next to wait for, the rest behind it. + e.stats.unpredicted += 1; + const rest = e.nd - i - 1; + std.mem.copyForwards(Deferred, e.deferred[0..rest], e.deferred[i + 1 .. e.nd]); + e.wait = d.seq; + e.wait_due = never; + e.wait_key = true; + e.nd = @intCast(rest); + return; + } + e.nd = 0; + } + + /// Whether a key `kind` into terminal `pane` was predicted. + fn predict(e: *Echo, pane: *Pane, kind: Kind, seq: u32) bool { + const state = pane.terminal orelse return false; + const vt = &state.vt; + if (vt.screens.active_key != .primary or !terminal.atBottom(pane) or !vt.modes.get(.cursor_visible)) return false; + const top = e.tops[e.pane]; + const screen = vt.screens.active; + const cur: Cursor = e.cursor orelse .{ .x = @intCast(screen.cursor.x), .row = top + screen.cursor.y, .seq = 0 }; + if (cur.row < top or cur.row - top >= vt.rows or e.n == max) return false; + var next: Cursor = .{ .x = cur.x, .row = cur.row, .seq = seq }; + var cell: ?Cell = null; + switch (kind) { + .char => |cp| { + // The last column wraps as a program pleases; a cell that + // holds another character is a line edited in its middle, + // or a suggestion (fish's) being left: the shell redraws + // what is right of it. ponytail: mosh's shift of the rest + // would cover bash's middle, and mispredict fish's. + if (cur.x + 1 >= vt.cols) return false; + const under = e.cpAt(state, cur.x, cur.row); + if (!blank(under) and under != cp) return false; + cell = .{ .x = cur.x, .row = cur.row, .cp = cp, .was = under, .seq = seq }; + next.x += 1; + }, + // At the end of a line only: in its middle a line editor moves + // the rest left. + .backspace => { + if (cur.x == 0 or !e.isInput(state, cur.x - 1, cur.row) or !blank(e.cpAt(state, cur.x, cur.row))) return false; + cell = .{ .x = cur.x - 1, .row = cur.row, .cp = ' ', .was = e.cpAt(state, cur.x - 1, cur.row), .seq = seq }; + next.x -= 1; + }, + .left => { + if (cur.x == 0 or !e.isInput(state, cur.x - 1, cur.row)) return false; + next.x -= 1; + }, + // Over typed text only: past its end, fish takes the right + // arrow for its suggestion (another colour). + .right => { + if (cur.x + 1 >= vt.cols or !e.isText(state, cur.x, cur.row)) return false; + next.x += 1; + }, + } + if (cell) |want| e.put(want); + e.cursor = next; + if (e.log) |l| l.append(std.heap.c_allocator, .{ .seq = seq, .cell = cell, .cursor = next }) catch {}; + return true; + } + + fn put(e: *Echo, want: Cell) void { + for (e.cells[0..e.n]) |*have| if (have.x == want.x and have.row == want.row) { + const was = have.was; + have.* = want; + have.was = was; + return; + }; + e.cells[e.n] = want; + e.n += 1; + } + + fn mine(e: *const Echo, x: u16, row: u64) ?*const Cell { + for (e.cells[0..e.n]) |*have| if (have.x == x and have.row == row) return have; + return null; + } + + /// What the screen shows at a cell as predicted so far. + fn cpAt(e: *const Echo, state: *terminal.State, x: u16, row: u64) u21 { + if (e.mine(x, row)) |have| return have.cp; + return e.screenCp(state, x, row); + } + + /// What the screen itself shows there; off its active area, a + /// codepoint no key types. + fn screenCp(e: *const Echo, state: *terminal.State, x: u16, row: u64) u21 { + const ci = e.screenCell(state, x, row) orelse return 0x10ffff; + return ci.cell.codepoint(); + } + + fn screenCell(e: *const Echo, state: *terminal.State, x: u16, row: u64) ?terminal.PageCell { + if (comptime !terminal.enabled) return null; + const top = e.tops[e.pane]; + if (row < top or row - top >= state.vt.rows) return null; + return state.vt.screens.active.pages.getCell(.{ .active = .{ .x = x, .y = @intCast(row - top) } }); + } + + /// A prompt's input there, or a character predicted. + fn isInput(e: *const Echo, state: *terminal.State, x: u16, row: u64) bool { + if (e.mine(x, row)) |have| return !blank(have.cp); + const ci = e.screenCell(state, x, row) orelse return false; + return ci.cell.semantic_content == .input; + } + + /// Typed text there: a character predicted, or a prompt's input in the + /// colour of the cell before it. + fn isText(e: *const Echo, state: *terminal.State, x: u16, row: u64) bool { + if (e.mine(x, row)) |have| return !blank(have.cp); + const ci = e.screenCell(state, x, row) orelse return false; + if (ci.cell.semantic_content != .input or blank(ci.cell.codepoint())) return false; + if (x == 0) return true; + const before = e.screenCell(state, x - 1, row) orelse return false; + return before.cell.style_id == ci.cell.style_id; + } + + /// The authority confirmed its client's input `seq`. + pub fn confirmed(e: *Echo, c: *Pardes, seq: u32) void { + e.acked = seq; + const due = e.time() + grace_ns; + for (e.deferred[0..e.nd]) |*d| if (d.seq <= seq and d.due == never) { + d.due = due; + }; + for (e.cells[0..e.n]) |*cell| if (cell.seq <= seq and cell.due == never) { + cell.due = due; + }; + if (e.cursor) |*cur| if (cur.seq <= seq and cur.due == never) { + cur.due = due; + }; + if (e.wait <= seq and e.wait_due == never) { + // The authority stepped a key this did not predict, after every + // one it did: its deltas from here show that key's doing, which + // no prediction knew of. They go, judged neither way. + e.wait_due = due; + e.drop(); + } + e.catchUp(c); + } + + /// Terminal `id`'s delta was applied, its active area's first row now + /// `top`. + pub fn delta(e: *Echo, c: *Pardes, id: u8, top: u64) void { + if (id == e.pane and top != e.tops[id] and (e.n > 0 or e.cursor != null)) { + // Scrolled: the rows predicted are others now. + e.tops[id] = top; + return e.drop(); + } + e.tops[id] = top; + if (id == e.pane) e.judge(c, 0); + e.catchUp(c); + } + + /// Once a frame: what is stale judged. Whether to draw. + pub fn frame(e: *Echo, c: *Pardes) bool { + if (e.n > 0 or e.cursor != null) e.judge(c, stale_ns); + e.catchUp(c); + defer e.changed = false; + return e.changed; + } + + fn judge(e: *Echo, c: *Pardes, slack: u64) void { + if (comptime !terminal.enabled) return; + if (e.n == 0 and e.cursor == null) return; + const now = e.time(); + const pane = c.panes[e.pane] orelse return e.drop(); + if (pane.serial != e.serial) return e.drop(); + const state = pane.terminal orelse return e.drop(); + if (state.vt.screens.active_key != .primary) return e.drop(); + const shown = e.visible(c); + var i: usize = 0; + while (i < e.n) { + const cell = e.cells[i]; + if (now < cell.due) { + i += 1; + continue; + } + if (!blank(cell.cp) and e.screenCp(state, cell.x, cell.row) != cell.cp) { + if (now < cell.due + slack) { + i += 1; + continue; + } + e.stats.mispredicted += 1; + if (shown) e.doubt = true; + e.trusted = false; + return e.drop(); + } + // Shown, or a space (mosh: too easy to show by chance to vouch). + // A key before the last one not predicted vouches for nothing + // after it (a line's characters for the password prompt its + // Enter brought up). + if (!blank(cell.cp)) { + e.stats.confirmed += 1; + if (cell.was != cell.cp and cell.seq > e.wait) { + e.trusted = true; + e.doubt = false; + } + } + e.cells[i] = e.cells[e.n - 1]; + e.n -= 1; + e.changed = true; + } + const cur = e.cursor orelse return; + if (now < cur.due) return; + const screen = state.vt.screens.active; + if (screen.cursor.x == cur.x and e.tops[e.pane] + screen.cursor.y == cur.row) { + e.cursor = null; + e.changed = true; + } else if (now >= cur.due + slack) { + e.stats.cursor_missed += 1; + e.drop(); + } + } + + /// Whether its predictions are drawn now. + pub fn visible(e: *const Echo, c: *const Pardes) bool { + if (e.doubt) return false; + if (e.trusted) return true; + const pane = c.panes[e.pane] orelse return false; + return atPrompt(pane); + } + + /// Over terminal pane `id`'s body, as renderBody drew it: the + /// characters predicted and the cursor after them. + pub fn paint(e: *const Echo, p: *const Pardes, s: *Surface, pane: *const Pane, id: usize, tx: u16, tw: u16, body_y: u16, body_h: u16, active: bool) void { + if (comptime !terminal.enabled) return; + if (e.n == 0 and e.cursor == null) return; + if (id != e.pane or pane.serial != e.serial or p.view != e.view or pane.body.mode != .tty) return; + if (!e.visible(p)) return; + const state = pane.terminal orelse return; + const sb = state.vt.screens.active.pages.scrollbar(); + const top = e.tops[id]; + // Off a prompt, the trust is inferred: underlined, as mosh does. + const flag = !atPrompt(pane); + const at = struct { + fn f(sb_: @TypeOf(sb), pan: u16, h: u16, top_: u64, row: u64) ?u16 { + if (row < top_ or row - top_ >= sb_.len) return null; + const screen_row = sb_.total - sb_.len + (row - top_); + if (screen_row < sb_.offset + pan) return null; + const y = screen_row - sb_.offset - pan; + return if (y < h) @intCast(y) else null; + } + }.f; + for (e.cells[0..e.n]) |cell| { + const y = at(sb, pane.pan, body_h, top, cell.row) orelse continue; + if (cell.x >= tw) continue; + const dst = s.at(tx + cell.x, body_y + y); + // Typed text continues the text before it (mosh's heuristic). + var style = dst.style; + if (cell.x > 0) { + const before = s.at(tx + cell.x - 1, body_y + y); + if (!before.default and !blank(before.text[0])) style = before.style; + } + if (flag and !blank(cell.cp)) style.ul = .single; + dst.default = false; + dst.text[0] = @intCast(cell.cp); + dst.len = 1; + dst.style = style; + } + if (!active or pane.focus != .body) return; + const cur = e.cursor orelse return; + const y = at(sb, pane.pan, body_h, top, cur.row) orelse return; + if (cur.x < tw) s.cursor = .{ .x = tx + cur.x, .y = body_y + y }; + } +}; + +const Kind = union(enum) { char: u21, backspace, left, right }; + +fn kindOf(ev: pardes.Event) ?Kind { + const k = switch (ev) { + .key => |k| k, + else => return null, + }; + if (k.ctrl or k.alt) return null; + switch (k.cp) { + Key.backspace => return .backspace, + Key.left => return .left, + Key.right => return .right, + else => {}, + } + // As forwardKey sends it. ponytail: ASCII only; a width table would + // let the rest in. + const cp: u21 = if (k.text.len == 1) + k.text[0] + else if (k.text.len == 0 and k.cp >= 'a' and k.cp <= 'z' and k.shift) + k.cp - 'a' + 'A' + else if (k.text.len == 0) + k.cp + else + return null; + return if (cp >= 0x20 and cp < 0x7f) .{ .char = cp } else null; +} + +/// Whether key `ev` goes to the terminal's program as it is (forwardKey's) +/// and not to pardes: Esc backs out of the pane, the tty chord leaves tty +/// mode, Ctrl-V pastes the register. +fn forwarded(c: *const Pardes, ev: pardes.Event) bool { + const k = switch (ev) { + .key => |k| k, + else => return false, + }; + if (k.cp == Key.escape) return false; + return !(k.ctrl and (k.cp == c.opts.tty_toggle or k.cp == 'v' or k.cp == 'V')); +} + +fn blank(cp: u21) bool { + return cp == 0 or cp == ' '; +} + +/// At a shell's prompt, reading its input: pardes's marks (a B and no C +/// since) and the cursor's own, on the primary screen. A shell without +/// pardes's marks is trusted only once its echo is confirmed. +fn atPrompt(pane: *const Pane) bool { + if (comptime !terminal.enabled) return false; + const state = pane.terminal orelse return false; + return state.vt.screens.active_key == .primary and state.stream.handler.phase == .input and terminal.promptInputReady(pane); +} + +/// The terminal view `view`'s keys go to, in tty mode: none when they go +/// elsewhere (a prompt, a header, window mode, another pane). +fn keyboardPane(c: *const Pardes, view: u8) ?usize { + const live = c.view == view; + const part = if (live) null else &(c.parked[view] orelse return null).view; + const id = if (part) |v| v.active else c.active; + if (if (part) |v| v.window_pick != null or v.header_focus else c.window_pick != null or c.header_focus) return null; + const pane = c.panes[id] orelse return null; + if (!pane.isTerminal() or pane.terminal == null or pane.prompt != .none) return null; + const mode = if (live) pane.body.mode else pane.pv[view].body.mode; + const focus = if (live) pane.focus else pane.pv[view].focus; + return if (mode == .tty and focus == .body) id else null; +} + +// ---- tests: one authority and one replica, its shell played by hand ---- + +const testing = std.testing; +const replica = @import("replica.zig"); + +const Rig = struct { + a: *replica.Authority, + r: *replica.Replica, + screens: replica.Screens, + peer: u16, + shell: u8, + /// What the authority wrote its shell's pty. + written: std.ArrayListUnmanaged(u8) = .empty, + now: u64 = 1_000 * ms, + + fn ptyWrite(ctx: ?*anyopaque, _: u8, bytes: []const u8) void { + const g: *Rig = @ptrCast(@alignCast(ctx.?)); + g.written.appendSlice(testing.allocator, bytes) catch {}; + } + fn watched(_: ?*anyopaque) bool { + return false; + } + const vtable: pardes.Host.VTable = .{ .watched = watched, .pty_write = ptyWrite }; + + fn init(g: *Rig) !void { + const gpa = testing.allocator; + g.written = .empty; + g.now = 1_000 * ms; + g.a = try replica.Authority.init(gpa, .{ .cols = 60, .rows = 16, .boot = .tty_shell }, .{ .ctx = g, .vtable = &vtable }, true); + g.screens = .init(gpa); + g.peer = try g.screens.addPeer(); + g.r = try replica.Replica.init(gpa, 1, try g.a.unit(0, 0), true); + g.shell = for (g.a.core.panes, 0..) |slot, id| { + if (slot) |pane| if (pane.isTerminal()) break @intCast(id); + } else return error.NoShell; + g.r.echo.now = g.now; + } + + fn deinit(g: *Rig) void { + g.r.deinit(); + g.screens.deinit(g.a.core); + g.a.deinit(); + g.written.deinit(testing.allocator); + } + + fn later(g: *Rig, dt: u64) void { + g.now += dt; + g.r.echo.now = g.now; + } + + /// The shell prints `bytes`; the replica gets the unit and the delta. + fn prints(g: *Rig, bytes: []const u8) !void { + g.a.output(.{ .output = .{ .pane = g.shell, .bytes = bytes } }); + try g.sync(); + } + + fn sync(g: *Rig) !void { + const gpa = testing.allocator; + if (try g.a.pending()) |u| g.r.confirm(u); + g.r.settle(); + var msgs: std.ArrayListUnmanaged([]u8) = .empty; + defer { + for (msgs.items) |m| gpa.free(m); + msgs.deinit(gpa); + } + try g.screens.flush(g.a.core, g.peer, &msgs); + for (msgs.items) |m| if (g.r.screen(m)) |reply| { + _ = try g.screens.take(g.a.core, g.peer, reply); + }; + } + + /// The replica's client types `k`; the message for the authority. + fn key(g: *Rig, k: Key) ![]u8 { + return testing.allocator.dupe(u8, try g.r.input(.{ .key = k })); + } + + /// The authority takes it, and the replica its unit. + fn take(g: *Rig, msg: []u8) !void { + defer testing.allocator.free(msg); + if (try g.a.pending()) |u| g.r.confirm(u); + g.r.confirm(try g.a.take(msg)); + g.r.settle(); + } + + /// What the replica's screen shows at the shell's cursor row, drawn, + /// and whether the cell at `x` is underlined. + fn drawn(g: *Rig, arena: *std.heap.ArenaAllocator, x: u16) !struct { cp: u8, ul: bool, cursor: ?u16 } { + _ = arena.reset(.retain_capacity); + const c = g.r.core(); + c.needs_frame = true; + const s = try c.render(arena.allocator()); + const pane = c.panes[g.shell].?; + const body = s.region(.body, g.shell).?.rect; + const y = body.y + terminal.gridCursor(pane).y; + const cell = s.at(body.x + x, y); + return .{ .cp = cell.text[0], .ul = cell.style.ul != .off, .cursor = if (s.cursor) |cur| if (cur.y == y) cur.x - body.x else null else null }; + } +}; + +const prompt = "\x1b]133;A;cl=line;aid=pardes\x07$ \x1b]133;B;aid=pardes\x07"; + +test "keys typed at a shell's prompt are drawn at once, and the authority's echo takes their place" { + if (comptime !terminal.enabled) return error.SkipZigTest; + var g: Rig = undefined; + try g.init(); + defer g.deinit(); + try g.prints(prompt); + var arena: std.heap.ArenaAllocator = .init(testing.allocator); + defer arena.deinit(); + const before = try g.drawn(&arena, 2); + try testing.expectEqual(@as(?u16, 2), before.cursor); + // Typed: shown at once, the cursor past it, and nothing underlined at + // a prompt. + const l = try g.key(.{ .cp = 'l', .text = "l" }); + const s = try g.key(.{ .cp = 's', .text = "s" }); + try testing.expectEqual(@as(u32, 2), g.r.echo.stats.predicted); + var shown = try g.drawn(&arena, 2); + try testing.expectEqual(@as(u8, 'l'), shown.cp); + try testing.expect(!shown.ul); + try testing.expectEqual(@as(?u16, 4), shown.cursor); + try testing.expectEqual(@as(u8, 's'), (try g.drawn(&arena, 3)).cp); + // The authority's core draws no overlay of its own. + try testing.expect(g.a.core.echo == null); + // The authority takes them, its shell echoes, the delta lands after the + // grace: confirmed, and the screen's own cells and cursor shown. + try g.take(l); + try g.take(s); + try testing.expectEqualStrings("ls", g.written.items); + g.later(grace_ns); + try g.prints("ls"); + try testing.expectEqual(@as(u8, 0), g.r.echo.n); + try testing.expect(g.r.echo.cursor == null); + try testing.expectEqual(@as(u32, 2), g.r.echo.stats.confirmed); + shown = try g.drawn(&arena, 3); + try testing.expectEqual(@as(u8, 's'), shown.cp); + try testing.expectEqual(@as(?u16, 4), shown.cursor); + // Backspace at the end of the line, shown at once. + const bs = try g.key(.{ .cp = Key.backspace }); + shown = try g.drawn(&arena, 3); + try testing.expectEqual(@as(u8, ' '), shown.cp); + try testing.expectEqual(@as(?u16, 3), shown.cursor); + try g.take(bs); + g.later(grace_ns); + try g.prints("\x08\x1b[K"); + try testing.expectEqual(@as(u32, 0), g.r.echo.stats.mispredicted + g.r.echo.stats.cursor_missed); + try testing.expect(g.r.quiet()); + try testing.expectEqual(replica.digestOf(g.a), g.r.digest()); +} + +test "a password prompt shows nothing typed, and a full-screen program is not predicted" { + if (comptime !terminal.enabled) return error.SkipZigTest; + var g: Rig = undefined; + try g.init(); + defer g.deinit(); + try g.prints(prompt ++ "sudo ls\r\n\x1b]133;C;aid=pardes\x07[sudo] password: "); + var arena: std.heap.ArenaAllocator = .init(testing.allocator); + defer arena.deinit(); + const x = terminal.gridCursor(g.r.core().panes[g.shell].?).x; + const k = try g.key(.{ .cp = 'h', .text = "h" }); + // Predicted, and not drawn: nothing has confirmed an echo here. + try testing.expectEqual(@as(u32, 1), g.r.echo.stats.predicted); + try testing.expectEqual(@as(u8, ' '), (try g.drawn(&arena, x)).cp); + try g.take(k); + // No echo, so no delta: a frame lets it go once it is stale. + g.later(grace_ns + stale_ns); + _ = g.r.echoFrame(); + try testing.expectEqual(@as(u8, 0), g.r.echo.n); + try testing.expectEqual(@as(u32, 1), g.r.echo.stats.mispredicted); + // The next key still shows nothing. + const k2 = try g.key(.{ .cp = 'i', .text = "i" }); + try testing.expectEqual(@as(u8, ' '), (try g.drawn(&arena, x)).cp); + try g.take(k2); + // vim: the alternate screen, never predicted. + try g.prints("\r\n\x1b]133;D;1;aid=pardes\x07" ++ prompt ++ "vim\r\n\x1b]133;C;aid=pardes\x07\x1b[?1049h\x1b[H~"); + g.later(grace_ns + stale_ns); + _ = g.r.echoFrame(); + const before = g.r.echo.stats.predicted; + try g.take(try g.key(.{ .cp = 'i', .text = "i" })); + try testing.expectEqual(before, g.r.echo.stats.predicted); +} + +test "a misprediction takes every prediction back and shows none until an echo is confirmed; after Tab nothing is predicted until its echo" { + if (comptime !terminal.enabled) return error.SkipZigTest; + var g: Rig = undefined; + try g.init(); + defer g.deinit(); + try g.prints(prompt); + var arena: std.heap.ArenaAllocator = .init(testing.allocator); + defer arena.deinit(); + // A line editor that echoes something else (vi's command mode): shown, + // then taken back. + const a = try g.key(.{ .cp = 'a', .text = "a" }); + try testing.expectEqual(@as(u8, 'a'), (try g.drawn(&arena, 2)).cp); + try g.take(a); + g.later(grace_ns); + try g.prints("A"); + try testing.expectEqual(@as(u32, 1), g.r.echo.stats.mispredicted); + try testing.expect(g.r.echo.doubt); + try testing.expectEqual(@as(u8, 'A'), (try g.drawn(&arena, 2)).cp); + // Doubted: predicted, not drawn, until one is confirmed. + const b = try g.key(.{ .cp = 'b', .text = "b" }); + try testing.expectEqual(@as(u8, ' '), (try g.drawn(&arena, 3)).cp); + try g.take(b); + g.later(grace_ns); + try g.prints("b"); + try testing.expect(!g.r.echo.doubt); + const c = try g.key(.{ .cp = 'c', .text = "c" }); + try testing.expectEqual(@as(u8, 'c'), (try g.drawn(&arena, 4)).cp); + // Tab: not predicted, and neither is what follows until the authority + // has it and its echo has had its grace. + const tab = try g.key(.{ .cp = Key.tab }); + const d = try g.key(.{ .cp = 'd', .text = "d" }); + try testing.expectEqual(@as(u32, 1), g.r.echo.stats.unpredicted); + try g.take(c); + try testing.expectEqual(@as(u8, 'c'), (try g.drawn(&arena, 4)).cp); + // The authority has Tab (and the key after it): what was predicted + // before it goes, the screen's own shown. + try g.take(tab); + try g.take(d); + try testing.expectEqual(@as(u8, 0), g.r.echo.n); + g.later(grace_ns); + try g.prints("c" ++ "ompleted d"); + // `d`, typed behind Tab, the screen showed by then: not predicted. + try testing.expectEqual(@as(u32, 2), g.r.echo.stats.unpredicted); + const e = try g.key(.{ .cp = 'e', .text = "e" }); + try testing.expectEqual(@as(u8, 'e'), (try g.drawn(&arena, 15)).cp); + try g.take(e); + g.later(grace_ns); + try g.prints("e"); + // A key typed behind Tab that the authority does not have yet is + // predicted once Tab's doing is on the screen, where it now goes. + const tab2 = try g.key(.{ .cp = Key.tab }); + const f = try g.key(.{ .cp = 'f', .text = "f" }); + try g.take(tab2); + try g.prints("ff"); + try testing.expectEqual(@as(u8, 0), g.r.echo.n); + g.later(grace_ns); + _ = g.r.echoFrame(); + try testing.expectEqual(@as(u8, 1), g.r.echo.n); + try testing.expectEqual(@as(u8, 'f'), (try g.drawn(&arena, 18)).cp); + try g.take(f); + g.later(grace_ns); + try g.prints("f"); + try testing.expectEqual(@as(u8, 0), g.r.echo.n); + try testing.expectEqual(@as(u32, 1), g.r.echo.stats.mispredicted); + try testing.expectEqual(@as(u32, 0), g.r.echo.stats.cursor_missed); + try testing.expect(g.r.quiet()); + try testing.expectEqual(replica.digestOf(g.a), g.r.digest()); +} diff --git a/src/pardes.zig b/src/pardes.zig index 081861ac..02983c84 100644 --- a/src/pardes.zig +++ b/src/pardes.zig @@ -67,6 +67,7 @@ pub const screen_state = if (terminal_panes) @import("screen_state.zig") else st pub const views = @import("views.zig"); pub const rollback = @import("rollback.zig"); pub const replica = @import("replica.zig"); +pub const echo = @import("echo.zig"); pub const image = @import("image.zig"); pub const dump = @import("dump.zig"); pub const lsp = @import("lsp/lsp.zig"); @@ -478,6 +479,7 @@ pub const Loc = struct { test { _ = @import("rollback.zig"); _ = @import("replica.zig"); + _ = @import("echo.zig"); _ = @import("modal.zig"); _ = @import("tagline.zig"); _ = @import("hunks.zig"); @@ -4698,6 +4700,10 @@ pub const Pardes = struct { restore_buf: [1024]u8 = @splat(0), surface: Surface = .{}, + /// A replica's predicted echo (src/echo.zig), drawn over its terminals: + /// presentation, its own, in no digest and no rollback copy. Null on a + /// session's own core. + echo: ?*echo.Echo = null, /// The view the fields above are of: whose layout, focus, pointer and /// panes' cursors and scroll (views.zig). `views_open` says which views /// there are, one a window or terminal; each not live is in `parked`. @@ -4727,6 +4733,7 @@ pub const Pardes = struct { "surface", "presentation", "frames", "chrome_animation", "lifts", "lift_serials", "cursor_glide", "cursor_view", "cursor_crossing", "cursor_held", "frame_arena", "scratch", "needs_frame", "present_skipped", "shell_continuous", "native_image_patches", + "echo", // Drained by every pump before its digest; a replica's queues // are its own. "effects", "effects_head", "effects_len", "in_q", "in_head", "in_len", diff --git a/src/replica.zig b/src/replica.zig index 0b55a5bf..032e50af 100644 --- a/src/replica.zig +++ b/src/replica.zig @@ -467,6 +467,9 @@ pub const Replica = struct { /// Its terminals' screen state, as the authority's deltas made it. screens: [pardes.MAX_PANES]?ScreenOf = @splat(null), screen_out: std.ArrayListUnmanaged(u8) = .empty, + /// Its predicted echo (src/echo.zig), drawn over its core's terminals: + /// fed by its keys, its units and its deltas here, and by `echoFrame`. + echo: pardes.echo.Echo = .{}, const ScreenOf = struct { serial: u32, @@ -490,6 +493,7 @@ pub const Replica = struct { r.deinit(); return error.NoCore; } + if (screens) r.core().echo = &r.echo; return r; } @@ -538,6 +542,7 @@ pub const Replica = struct { try r.pending.append(r.gpa, .{ .seq = seq, .msg = msg }); r.dirty = true; r.settle(); + if (r.t.screen_state and r.diverged == null) r.echo.typed(r.core(), r.view, ev, seq, r.applied == r.pending.items.len); r.out.clearRetainingCapacity(); try r.out.appendSlice(r.gpa, msg); return r.out.items; @@ -548,6 +553,7 @@ pub const Replica = struct { if (r.diverged != null) return; const u = parseUnit(msg) orelse return r.fail("a unit too short to read"); r.stats.units += 1; + if (u.origin == r.id) if (r.t.core) |c| r.echo.confirmed(c, u.seq); const was = Stepping.begin(&r.t, &r.epoch); defer was.end(); if (u.origin == r.id and r.pending.items.len > 0 and r.pending.items[0].seq == u.seq and r.applied > 0 and @@ -716,6 +722,15 @@ pub const Replica = struct { return true; } + /// Its client's, once a frame before it draws: a predicted echo the + /// screen has not shown in time goes, and keys deferred behind one not + /// predicted are predicted once its doing is on the screen. Whether what + /// the overlay draws changed since the last call (by a key, a unit, a + /// delta or this: `echo.changed`). + pub fn echoFrame(r: *Replica) bool { + return r.echo.frame(r.core()); + } + /// Nothing pending and nothing applied: the replica is the authority's /// confirmed state, which `digest` says. pub fn quiet(r: *const Replica) bool { @@ -754,6 +769,7 @@ pub const Replica = struct { r.stats.apply_ns.append(r.gpa, nowNs() - t0) catch {}; sc.refused = false; terminal.takeMarks(state, applied.extra); + r.echo.delta(c, m.pane, sc.rep.top); // Its rows as the core keeps them read are another grid's. c.shell_rows.markStale(pane); var seq: [4]u8 = undefined; diff --git a/src/rollback.zig b/src/rollback.zig index 37fc481d..6496a69f 100644 --- a/src/rollback.zig +++ b/src/rollback.zig @@ -415,10 +415,11 @@ fn annotatedStruct(comptime T: type) bool { /// is taken: what is in their slots is nothing), the frame statistics /// (numbers, and a static name), and the rows a terminal was last read as /// (a grid's worth of text, emptied when a copy is taken and when it is -/// put back: src/replica.zig). +/// put back: src/replica.zig), and a replica's predicted echo (src/echo.zig: +/// the replica's, never its core's). fn unsaved(comptime name: []const u8) bool { return std.mem.eql(u8, name, "effects") or std.mem.eql(u8, name, "in_q") or std.mem.eql(u8, name, "frames") or - std.mem.eql(u8, name, "shell_rows"); + std.mem.eql(u8, name, "shell_rows") or std.mem.eql(u8, name, "echo"); } fn annotated(comptime T: type, comptime kind: []const u8, comptime name: []const u8) bool { diff --git a/src/terminal.zig b/src/terminal.zig index aedc007f..3a589659 100644 --- a/src/terminal.zig +++ b/src/terminal.zig @@ -20,6 +20,8 @@ const ghostty_vt = if (enabled) @import("ghostty-vt") else struct {}; pub const history_max = if (enabled) 64 else 8; pub const VtSlot = if (enabled) ghostty_vt.Terminal else void; +/// A cell of an emulator's pages, as `getCell` reads it (src/echo.zig). +pub const PageCell = if (enabled) ghostty_vt.PageList.Cell else void; /// Kitty graphics are drawn where pixel geometry is (pdf_enabled, as for /// image panes' native placements). pub const images_enabled = enabled and pardes.pdf_enabled; diff --git a/test/replicas.zig b/test/replicas.zig index 9b5c3c3b..baaa669d 100644 --- a/test/replicas.zig +++ b/test/replicas.zig @@ -13,6 +13,11 @@ //! asking for the rows it scrolls back into and does not hold. //! //! zig build replicas -Dplatform=tty -- [--seeds N] [--steps M] [--clients C] [--rtt 30,80,207] [--first K] [--flood MB] [--shared] +//! zig build replicas -Dplatform=tty -- --echo [--seeds N] [--rtt 30,80,207] [--first K] +//! +//! `--echo` types a corpus into a shell instead, with and without the +//! predicted echo (src/echo.zig), and gates what it draws: below, at +//! "predicted echo". //! //! Gates, per seed and RTT: no replica diverges (every confirmed unit's //! digests agree as it is replayed), and at quiescence every replica's @@ -29,6 +34,7 @@ const libc = std.c; const pardes = @import("pardes"); const replica = pardes.replica; const screen_state = pardes.screen_state; +const echo = pardes.echo; const Key = pardes.Key; const gpa = std.heap.c_allocator; @@ -58,7 +64,7 @@ const Host = struct { } }; -const Kind = enum { input, to_authority, to_replica, echo, frame, output, screen_down, screen_up }; +const Kind = enum { input, to_authority, to_replica, echo, frame, output, screen_down, screen_up, client_frame }; const Msg = struct { at: u64, @@ -66,6 +72,8 @@ const Msg = struct { kind: Kind, who: u16, bytes: []u8, + /// An echo's: the client's input that made it (--echo). + seq: u32 = 0, fn order(_: void, a: Msg, b: Msg) std.math.Order { if (a.at != b.at) return std.math.order(a.at, b.at); @@ -288,14 +296,6 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { var down: [8]Link = @splat(.{}); var left: [8]usize = @splat(r.steps); var typing: usize = r.clients; - const push = struct { - fn f(q: *std.PriorityQueue(Msg, void, Msg.order), nn: *u64, m: Msg) !void { - var mm = m; - mm.n = nn.*; - nn.* += 1; - try q.push(gpa, mm); - } - }.f; // Each client's first input, soon; the programs; the first frame. for (0..r.clients) |c| try push(&queue, &n, .{ .at = random.uintLessThan(u64, 200_000), .n = 0, .kind = .input, .who = @intCast(c + 1), .bytes = &.{} }); try push(&queue, &n, .{ .at = tui_at, .n = 0, .kind = .output, .who = 0, .bytes = &.{} }); @@ -309,26 +309,6 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { // authority steps an input, and once a frame. var owed: std.ArrayListUnmanaged([]u8) = .empty; defer owed.deinit(gpa); - const flushAll = struct { - fn f(sc: *replica.Screens, core: *pardes.Pardes, ps: []const u16, list: *std.ArrayListUnmanaged([]u8), q: *std.PriorityQueue(Msg, void, Msg.order), nn: *u64, now: u64, dl: []Link, rnd: std.Random, ow: u64, jt: u64, vs: *std.AutoHashMapUnmanaged(u64, u64), tot: *Totals) !void { - for (ps, 0..) |peer, c| { - list.clearRetainingCapacity(); - try sc.flush(core, peer, list); - for (list.items) |bytes| { - tot.deltas += 1; - tot.delta_bytes += bytes.len; - try push(q, nn, .{ .at = dl[c].arrive(rnd, now, ow, jt), .n = 0, .kind = .screen_down, .who = @intCast(c + 1), .bytes = bytes }); - } - } - // Each version as the authority's screen showed it. - for (&sc.tracks, 0..) |*slot, id| if (slot.*) |*tr| { - const key = @as(u64, tr.serial) << 32 | tr.track.version; - if (tr.track.version == 0 or vs.contains(key)) continue; - _ = core.panes[id] orelse continue; - try vs.put(gpa, key, screenHash(&tr.state.vt)); - }; - } - }.f; while (queue.pop()) |m| { defer if (m.bytes.len > 0) gpa.free(m.bytes); @@ -432,6 +412,7 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { } if (rp.screenRequest()) |req| try push(&queue, &n, .{ .at = up[c].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .screen_up, .who = m.who, .bytes = try gpa.dupe(u8, req) }); }, + .client_frame => {}, .screen_up => { const c = m.who - 1; if (m.bytes[5] == 2) totals.fetched += std.mem.readInt(u64, m.bytes[14..22], .little) - std.mem.readInt(u64, m.bytes[6..14], .little); @@ -467,6 +448,35 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { } } +fn push(q: *std.PriorityQueue(Msg, void, Msg.order), nn: *u64, m: Msg) !void { + var mm = m; + mm.n = nn.*; + nn.* += 1; + try q.push(gpa, mm); +} + +/// What each peer is owed of the terminals, onto its link (before the +/// authority steps an input, and once a frame); each version as the +/// authority's screen showed it. +fn flushAll(sc: *replica.Screens, core: *pardes.Pardes, ps: []const u16, list: *std.ArrayListUnmanaged([]u8), q: *std.PriorityQueue(Msg, void, Msg.order), nn: *u64, now: u64, dl: []Link, rnd: std.Random, ow: u64, jt: u64, vs: *std.AutoHashMapUnmanaged(u64, u64), tot: *Totals) !void { + for (ps, 0..) |peer, c| { + list.clearRetainingCapacity(); + try sc.flush(core, peer, list); + for (list.items) |bytes| { + tot.deltas += 1; + tot.delta_bytes += bytes.len; + try push(q, nn, .{ .at = dl[c].arrive(rnd, now, ow, jt), .n = 0, .kind = .screen_down, .who = @intCast(c + 1), .bytes = bytes }); + } + } + // Each version as the authority's screen showed it. + for (&sc.tracks, 0..) |*slot, id| if (slot.*) |*tr| { + const key = @as(u64, tr.serial) << 32 | tr.track.version; + if (tr.track.version == 0 or vs.contains(key)) continue; + _ = core.panes[id] orelse continue; + try vs.put(gpa, key, screenHash(&tr.state.vt)); + }; +} + /// A unit of the authority's to every replica, down its link: first the /// rows of its terminals its step read that a replica holds as holes. fn sendUnit(q: *std.PriorityQueue(Msg, void, Msg.order), n: *u64, unit: []const u8, now: u64, down: []Link, random: std.Random, one_way: u64, jitter: u64, totals: *Totals, flooding: bool, screens: *replica.Screens, core: *pardes.Pardes, peers: []const u16) !void { @@ -490,6 +500,695 @@ fn sendUnit(q: *std.PriorityQueue(Msg, void, Msg.order), n: *u64, unit: []const } } +// ---- predicted echo (--echo): one client typing a corpus into a shell ---- +// +// The authority's pty is a shell played here (`FakeShell`): a line editor at +// a prompt with pardes's OSC 133 marks and Tab completion, and the programs +// the corpus runs in it: a password prompt (no echo), vim (the alternate +// screen), a program that ignores what is typed, and `cat` (the kernel's +// plain echo, no marks). Each key's echo comes back 2 ms after the authority +// writes it, as a shell's. The client types at a typist's pace and in bursts; +// each of its frames (60 Hz, a phase of its own) is what its screen shows: +// the predicted echo where it is drawn (src/echo.zig), the screen state +// under it. Per key the shell echoed at a prompt or in cat: the time from +// the key to its character on that screen, with prediction and without. Per +// key predicted: whether the authority's screen, right after its echo, +// shows what was predicted where it was. Per key drawn wrong: its frames. + +const ascii: [128][1]u8 = blk: { + var t: [128][1]u8 = undefined; + for (&t, 0..) |*c, i| c.* = .{@intCast(i)}; + break :blk t; +}; + +const Step = struct { gap: u64, key: Key, section: u8 }; + +/// The corpus's parts, each a case of the gates. +const sections = [_][]const u8{ "typing", "a burst", "backspace", "left, right", "tab", "password", "vim", "ignores input", "cat", "typed ahead" }; + +const Corpus = struct { + steps: std.ArrayListUnmanaged(Step) = .empty, + random: std.Random, + extra: u64 = 0, + section: u8 = 0, + + fn add(c: *Corpus, gap: u64, key: Key) !void { + try c.steps.append(gpa, .{ .gap = gap + c.extra, .key = key, .section = c.section }); + c.extra = 0; + } + + fn typing(c: *Corpus, text: []const u8, fast: bool) !void { + for (text) |ch| try c.add(if (fast) c.random.intRangeAtMost(u64, 12_000, 60_000) else c.random.intRangeAtMost(u64, 60_000, 180_000), .{ .cp = ch, .text = &ascii[ch] }); + } + + fn press(c: *Corpus, key: Key) !void { + try c.add(c.random.intRangeAtMost(u64, 80_000, 250_000), key); + } + + fn pause(c: *Corpus) void { + c.extra += c.random.intRangeAtMost(u64, 500_000, 1_200_000); + } + + fn build(c: *Corpus) !void { + const enter: Key = .{ .cp = Key.enter }; + const bs: Key = .{ .cp = Key.backspace }; + c.pause(); + // At a prompt, at a typist's pace, then in a burst. + c.section = 0; + try c.typing("echo hello world", false); + try c.press(enter); + c.pause(); + c.section = 1; + try c.typing("echo the quick brown fox jumps over", true); + try c.press(enter); + c.pause(); + // Backspace. + c.section = 2; + try c.typing("ecoh", false); + try c.press(bs); + try c.press(bs); + try c.typing("ho fixed tpyo", false); + for (0..3) |_| try c.press(bs); + try c.typing("ypo", false); + try c.press(enter); + c.pause(); + // Left and right over what was typed. + c.section = 3; + try c.typing("echo abc", false); + for ([_]u21{ Key.left, Key.left, Key.right, Key.right }) |k| try c.press(.{ .cp = k }); + try c.typing("def", false); + try c.press(enter); + c.pause(); + // Tab completion, typed straight on. + c.section = 4; + try c.typing("ec", false); + try c.press(.{ .cp = Key.tab }); + try c.typing("tab completed", false); + try c.press(enter); + c.pause(); + // A password prompt: nothing typed there may show. + c.section = 5; + try c.typing("sudo ls", false); + try c.press(enter); + c.pause(); + try c.typing("hunter2", false); + try c.press(enter); + c.pause(); + // vim: the alternate screen, never predicted. + c.section = 6; + try c.typing("vim", false); + try c.press(enter); + c.pause(); + try c.typing("ihello from vim", false); + try c.press(.{ .cp = Key.escape, .shift = true }); + try c.typing(":q", false); + try c.press(enter); + c.pause(); + // A program that ignores what is typed. + c.section = 7; + try c.typing("sink", false); + try c.press(enter); + c.pause(); + try c.typing("this goes nowhere", false); + try c.press(.{ .cp = 'c', .ctrl = true }); + c.pause(); + // cat: the kernel's plain echo. + c.section = 8; + try c.typing("cat", false); + try c.press(enter); + c.pause(); + try c.typing("plain echo", false); + try c.press(enter); + try c.typing("a second line", false); + try c.press(enter); + try c.press(.{ .cp = 'd', .ctrl = true }); + c.pause(); + // Typed on before the next prompt. + c.section = 9; + try c.typing("echo one", false); + try c.press(enter); + try c.typing("echo two", false); + try c.press(enter); + c.pause(); + } +}; + +const prompt_bytes = "\x1b]133;A;cl=line;aid=pardes\x07$ \x1b]133;B;aid=pardes\x07"; + +/// The shell on the authority's pty, a key a write (as forwardKey writes). +const FakeShell = struct { + mode: Mode = .prompt, + line: [256]u8 = undefined, + len: usize = 0, + cur: usize = 0, + vim_cmd: [8]u8 = undefined, + vim_n: usize = 0, + out: std.ArrayListUnmanaged(u8) = .empty, + + const Mode = enum { prompt, password, vim, vim_insert, sink, cat }; + + fn put(sh: *FakeShell, bytes: []const u8) void { + sh.out.appendSlice(gpa, bytes) catch {}; + } + + fn print(sh: *FakeShell, comptime fmt: []const u8, args: anytype) void { + sh.out.print(gpa, fmt, args) catch {}; + } + + fn done(sh: *FakeShell, status: u8) void { + sh.print("\x1b]133;D;{d};aid=pardes\x07" ++ prompt_bytes, .{status}); + sh.mode = .prompt; + sh.len = 0; + sh.cur = 0; + } + + fn insert(sh: *FakeShell, c: u8) void { + if (sh.len + 1 >= sh.line.len) return; + sh.put(&.{c}); + if (sh.cur < sh.len) { + sh.put(sh.line[sh.cur..sh.len]); + sh.print("\x1b[{d}D", .{sh.len - sh.cur}); + } + std.mem.copyBackwards(u8, sh.line[sh.cur + 1 .. sh.len + 1], sh.line[sh.cur..sh.len]); + sh.line[sh.cur] = c; + sh.len += 1; + sh.cur += 1; + } + + fn key(sh: *FakeShell, b: []const u8) void { + const printable = b.len == 1 and b[0] >= 0x20 and b[0] < 0x7f; + const eql = std.mem.eql; + switch (sh.mode) { + .prompt => if (printable) sh.insert(b[0]) else if (eql(u8, b, "\x7f")) { + if (sh.cur == 0) return; + if (sh.cur == sh.len) sh.put("\x08\x1b[K") else { + sh.put("\x08"); + sh.put(sh.line[sh.cur..sh.len]); + sh.print(" \x1b[{d}D", .{sh.len - sh.cur + 1}); + } + std.mem.copyForwards(u8, sh.line[sh.cur - 1 .. sh.len - 1], sh.line[sh.cur..sh.len]); + sh.len -= 1; + sh.cur -= 1; + } else if (eql(u8, b, "\x1b[D")) { + if (sh.cur == 0) return; + sh.put(b); + sh.cur -= 1; + } else if (eql(u8, b, "\x1b[C")) { + if (sh.cur == sh.len) return; + sh.put(b); + sh.cur += 1; + } else if (eql(u8, b, "\t")) { + if (sh.cur != sh.len or std.mem.indexOfScalar(u8, sh.line[0..sh.len], ' ') != null) return; + for ([_][]const u8{ "echo", "sudo", "sink", "cat", "vim" }) |cmd| { + if (sh.len == 0 or sh.len >= cmd.len or !std.mem.startsWith(u8, cmd, sh.line[0..sh.len])) continue; + for (cmd[sh.len..]) |ch| sh.insert(ch); + sh.insert(' '); + return; + } + } else if (eql(u8, b, "\r")) { + var cmd_buf: [256]u8 = undefined; + const cmd = cmd_buf[0..sh.len]; + @memcpy(cmd, sh.line[0..sh.len]); + sh.len = 0; + sh.cur = 0; + sh.put("\r\n\x1b]133;C;aid=pardes\x07"); + if (cmd.len == 0) return sh.done(0); + if (std.mem.startsWith(u8, cmd, "echo")) { + sh.print("{s}\r\n", .{std.mem.trimStart(u8, cmd[4..], " ")}); + sh.done(0); + } else if (std.mem.startsWith(u8, cmd, "sudo")) { + sh.put("[sudo] password for you: "); + sh.mode = .password; + } else if (eql(u8, cmd, "vim")) { + sh.put("\x1b[?1049h\x1b[2J\x1b[H~\r\n~\r\n~\x1b[H"); + sh.mode = .vim; + } else if (eql(u8, cmd, "sink")) { + sh.mode = .sink; + } else if (eql(u8, cmd, "cat")) { + sh.mode = .cat; + } else { + sh.print("fake: unknown command: {s}\r\n", .{cmd}); + sh.done(127); + } + } else if (eql(u8, b, "\x03")) { + sh.put("^C\r\n"); + sh.done(130); + }, + .password => if (eql(u8, b, "\r")) { + sh.put("\r\nsudo: 1 incorrect password attempt\r\n"); + sh.done(1); + } else if (eql(u8, b, "\x03")) { + sh.put("^C\r\n"); + sh.done(130); + }, + .vim => if (sh.vim_n > 0) { + if (eql(u8, b, "\r")) { + const quit = eql(u8, sh.vim_cmd[0..sh.vim_n], ":q"); + sh.vim_n = 0; + if (quit) { + sh.put("\x1b[?1049l"); + sh.done(0); + } + } else if (printable and sh.vim_n < sh.vim_cmd.len) { + sh.vim_cmd[sh.vim_n] = b[0]; + sh.vim_n += 1; + } + } else if (eql(u8, b, "i")) { + sh.mode = .vim_insert; + } else if (eql(u8, b, ":")) { + sh.vim_cmd[0] = ':'; + sh.vim_n = 1; + }, + .vim_insert => if (eql(u8, b, "\x1b")) { + sh.mode = .vim; + } else if (printable) sh.put(b), + .sink => if (eql(u8, b, "\x03")) { + sh.put("^C\r\n"); + sh.done(130); + }, + .cat => if (printable) { + sh.put(b); + if (sh.len < sh.line.len) { + sh.line[sh.len] = b[0]; + sh.len += 1; + } + } else if (eql(u8, b, "\x7f")) { + if (sh.len == 0) return; + sh.put("\x08 \x08"); + sh.len -= 1; + } else if (eql(u8, b, "\r")) { + sh.print("\r\n{s}\r\n", .{sh.line[0..sh.len]}); + sh.len = 0; + } else if (eql(u8, b, "\x04") and sh.len == 0) { + sh.done(0); + } else if (eql(u8, b, "\x03")) { + sh.put("^C\r\n"); + sh.done(130); + }, + } + } +}; + +/// The authority's host: each pty write tagged with the client input that +/// made it. +const EchoHost = struct { + writes: std.ArrayListUnmanaged(struct { seq: u32, bytes: []u8 }) = .empty, + current: u32 = 0, + + fn watched(_: ?*anyopaque) bool { + return false; + } + + fn ptyWrite(ctx: ?*anyopaque, _: u8, bytes: []const u8) void { + const h: *EchoHost = @ptrCast(@alignCast(ctx.?)); + h.writes.append(gpa, .{ .seq = h.current, .bytes = gpa.dupe(u8, bytes) catch return }) catch {}; + } + + fn ignore(_: ?*anyopaque, _: []const u8) void {} + + const vtable: pardes.Host.VTable = .{ .watched = watched, .pty_write = ptyWrite, .set_clipboard = ignore }; + + fn host(h: *EchoHost) pardes.Host { + return .{ .ctx = h, .vtable = &vtable }; + } +}; + +const Typed = struct { + seq: u32, + section: u8, + at: u64, + printable: bool, + /// What was predicted: the cell (its row in the active area) and the + /// cursor after it. + pred: ?struct { x: u16, y: u16, cp: u21 } = null, + pcur: ?struct { x: u16, y: u16 } = null, + /// The shell's mode as it took the key; whether it printed anything for + /// it; the authority's version of the screen before that. + mode: ?FakeShell.Mode = null, + echoed: bool = false, + version_before: u32 = 0, + /// The authority's screen right after its echo: its cursor and the + /// cursor's row; whether that is what was predicted. + after: ?struct { x: u16, y: u16, row: [128]u21 } = null, + truth: ?bool = null, + /// Its prediction drawn: first, and in how many frames. + first_visible: ?u64 = null, + visible_frames: u32 = 0, + /// The screen state showing its echo, first. + seen: ?u64 = null, +}; + +const EchoTotals = struct { + keys: u64 = 0, + echo_keys: u64 = 0, + latency: std.ArrayListUnmanaged(u64) = .empty, + predicted: u64 = 0, + unpredicted: u64 = 0, + confirmed: u64 = 0, + mispredicted: u64 = 0, + cursor_missed: u64 = 0, + right: u64 = 0, + wrong: u64 = 0, + wrong_shown: u64 = 0, + wrong_frames: u64 = 0, + wrong_max: u64 = 0, + secret_frames: u64 = 0, + alt_predicted: u64 = 0, + divergences: u64 = 0, + unequal: u64 = 0, + screens_wrong: u64 = 0, + /// The replica's frame drawn while it shows a prediction (its core's + /// render, the tty's and the GUI's), and the overlay's part of it (ns); + /// cells drawn otherwise than predicted. + render_ns: std.ArrayListUnmanaged(u64) = .empty, + paint_ns: std.ArrayListUnmanaged(u64) = .empty, + drawn_frames: u64 = 0, + paint_wrong: u64 = 0, + sec: [sections.len]Section = @splat(.{}), + + const Section = struct { keys: u64 = 0, predicted: u64 = 0, wrong_frames: u64 = 0, latency: std.ArrayListUnmanaged(u64) = .empty }; + + fn deinit(et: *EchoTotals) void { + for (&et.sec) |*x| x.latency.deinit(gpa); + et.latency.deinit(gpa); + et.render_ns.deinit(gpa); + et.paint_ns.deinit(gpa); + } +}; + +fn cellCp(state: *pardes.panes.terminal.State, x: u16, y: u16) u21 { + const ci = state.vt.screens.active.pages.getCell(.{ .active = .{ .x = x, .y = y } }) orelse return 0x10ffff; + const cp = ci.cell.codepoint(); + return if (cp == 0) ' ' else cp; +} + +/// A key's prediction against the authority's screen right after its echo, +/// once both are known (a key typed behind one not predicted is predicted +/// after the authority has it). +fn judgeTruth(k: *Typed) void { + if (k.truth != null) return; + const pc = k.pcur orelse return; + const after = k.after orelse return; + var ok = after.x == pc.x and after.y == pc.y; + if (k.pred) |cell| ok = ok and cell.y == after.y and cell.x < after.row.len and after.row[cell.x] == cell.cp; + k.truth = ok; + if (trace and !ok) std.debug.print("key {d} in {t} predicted cursor {d},{d} cell {any}; the authority's cursor {d},{d}\n", .{ k.seq, k.mode.?, pc.x, pc.y, k.pred, after.x, after.y }); +} + +fn runEcho(seed: u64, rtt_ms: u64, on: bool, et: *EchoTotals) !void { + var prng = std.Random.DefaultPrng.init(seed *% 0x9e3779b97f4a7c15 +% rtt_ms); + const random = prng.random(); + var host: EchoHost = .{}; + defer { + for (host.writes.items) |w| gpa.free(w.bytes); + host.writes.deinit(gpa); + } + var sh: FakeShell = .{}; + defer sh.out.deinit(gpa); + const a = try replica.Authority.init(gpa, .{ .cols = 100, .rows = 30, .boot = .tty_shell }, host.host(), true); + defer a.deinit(); + var screens: replica.Screens = .init(gpa); + defer screens.deinit(a.core); + const peer = try screens.addPeer(); + const peers = [_]u16{peer}; + const rp = try replica.Replica.init(gpa, 1, try a.unit(0, 0), true); + defer rp.deinit(); + rp.echo.on = on; + const shell: u8 = for (a.core.panes, 0..) |slot, id| { + if (slot) |pane| if (pane.isTerminal()) break @intCast(id); + } else return error.NoShell; + var corpus: Corpus = .{ .random = random }; + defer corpus.steps.deinit(gpa); + try corpus.build(); + var typed: std.ArrayListUnmanaged(Typed) = .empty; + defer typed.deinit(gpa); + var t: Totals = .{}; + defer { + t.spec_ns.deinit(gpa); + t.copy_ns.deinit(gpa); + t.rollback_ns.deinit(gpa); + t.apply_ns.deinit(gpa); + t.frame_ns.deinit(gpa); + } + var versions: std.AutoHashMapUnmanaged(u64, u64) = .empty; + defer versions.deinit(gpa); + var queue: std.PriorityQueue(Msg, void, Msg.order) = .empty; + defer { + while (queue.pop()) |m| if (m.bytes.len > 0) gpa.free(m.bytes); + queue.deinit(gpa); + } + var n: u64 = 0; + const one_way = rtt_ms * 1000 / 2; + const jitter = one_way / 10; + var up: [1]Link = @splat(.{}); + var down: [1]Link = @splat(.{}); + var owed: std.ArrayListUnmanaged([]u8) = .empty; + defer owed.deinit(gpa); + + // The shell's first prompt. + sh.put(prompt_bytes); + a.output(.{ .output = .{ .pane = shell, .bytes = sh.out.items } }); + sh.out.clearRetainingCapacity(); + var next_step: usize = 0; + try push(&queue, &n, .{ .at = corpus.steps.items[0].gap, .n = 0, .kind = .input, .who = 1, .bytes = &.{} }); + try push(&queue, &n, .{ .at = frame_us, .n = 0, .kind = .frame, .who = 0, .bytes = &.{} }); + try push(&queue, &n, .{ .at = random.uintLessThan(u64, frame_us), .n = 0, .kind = .client_frame, .who = 1, .bytes = &.{} }); + // Two clocks tick while anything else moves, and a second after. + var periodic: usize = 2; + var left: [2]u32 = .{ 60, 60 }; + + var frame_arena: std.heap.ArenaAllocator = .init(gpa); + defer frame_arena.deinit(); + var made: std.ArrayListUnmanaged(echo.Echo.Predicted) = .empty; + defer made.deinit(gpa); + rp.echo.log = &made; + while (queue.pop()) |m| { + defer if (m.bytes.len > 0) gpa.free(m.bytes); + rp.echo.now = m.at * 1000; + // What it predicted in the last event's calls (a key typed, or the + // keys behind one it did not, at a unit, a delta or a frame). + defer { + const top = rp.echo.tops[shell]; + for (made.items) |pr| { + const k = &typed.items[pr.seq - 1]; + if (trace) { + const sc = rp.core().panes[shell].?.terminal.?.vt.screens.active.cursor; + std.debug.print("{d} ms ({t}): key {d} predicted {any} cursor {d}; acked {d} wait {d} nd {d}; the screen's cursor {d},{d}\n", .{ m.at / 1000, m.kind, pr.seq, pr.cell, pr.cursor.x, rp.echo.acked, rp.echo.wait, rp.echo.nd, sc.x, sc.y }); + } + if (pr.cell) |cell| k.pred = .{ .x = cell.x, .y = @intCast(cell.row - top), .cp = cell.cp }; + k.pcur = .{ .x = pr.cursor.x, .y = @intCast(pr.cursor.row - top) }; + judgeTruth(k); + } + made.clearRetainingCapacity(); + } + switch (m.kind) { + .input => { + const step = corpus.steps.items[next_step]; + next_step += 1; + const msg = try gpa.dupe(u8, try rp.input(.{ .key = step.key })); + const seq = rp.next_seq - 1; + try typed.append(gpa, .{ .seq = seq, .section = step.section, .at = m.at, .printable = step.key.text.len == 1 }); + if (trace) std.debug.print("{d} ms: key {d} typed: '{s}' cp {x}\n", .{ m.at / 1000, seq, step.key.text, step.key.cp }); + try push(&queue, &n, .{ .at = up[0].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .to_authority, .who = 1, .bytes = msg }); + if (next_step < corpus.steps.items.len) try push(&queue, &n, .{ .at = m.at + corpus.steps.items[next_step].gap, .n = 0, .kind = .input, .who = 1, .bytes = &.{} }); + }, + .to_authority => { + if (try a.pending()) |batch| try sendUnit(&queue, &n, batch, m.at, &down, random, one_way, jitter, &t, false, &screens, a.core, &peers); + try flushAll(&screens, a.core, &peers, &owed, &queue, &n, m.at, &down, random, one_way, jitter, &versions, &t); + host.current = (replica.parseInput(m.bytes) orelse return error.BadInput).seq; + const unit = try a.take(m.bytes); + host.current = 0; + try sendUnit(&queue, &n, unit, m.at, &down, random, one_way, jitter, &t, false, &screens, a.core, &peers); + for (host.writes.items) |w| try push(&queue, &n, .{ .at = m.at + 2_000, .n = 0, .kind = .echo, .who = shell, .bytes = w.bytes, .seq = w.seq }); + host.writes.clearRetainingCapacity(); + }, + .echo => { + const ty: ?*Typed = if (m.seq > 0) &typed.items[m.seq - 1] else null; + const state = a.core.panes[shell].?.terminal.?; + if (ty) |k| { + k.mode = sh.mode; + k.version_before = if (screens.tracks[shell]) |*tr| tr.track.version else 0; + } + sh.key(m.bytes); + if (sh.out.items.len > 0) { + a.output(.{ .output = .{ .pane = shell, .bytes = sh.out.items } }); + sh.out.clearRetainingCapacity(); + if (ty) |k| k.echoed = true; + } + if (ty) |k| { + const cur = state.vt.screens.active.cursor; + k.after = .{ .x = @intCast(cur.x), .y = @intCast(cur.y), .row = undefined }; + for (&k.after.?.row, 0..) |*cp, x| cp.* = cellCp(state, @intCast(x), @intCast(cur.y)); + judgeTruth(k); + } + }, + .frame => { + if (try a.pending()) |batch| try sendUnit(&queue, &n, batch, m.at, &down, random, one_way, jitter, &t, false, &screens, a.core, &peers); + try flushAll(&screens, a.core, &peers, &owed, &queue, &n, m.at, &down, random, one_way, jitter, &versions, &t); + const busy = next_step < corpus.steps.items.len or queue.count() + 1 > periodic; + left[0] = if (busy) 60 else left[0] -| 1; + if (left[0] > 0) try push(&queue, &n, .{ .at = m.at + frame_us, .n = 0, .kind = .frame, .who = 0, .bytes = &.{} }) else periodic -= 1; + }, + .client_frame => { + _ = rp.echoFrame(); + const core = rp.core(); + const drawn = rp.echo.visible(core) and core.panes[shell].?.body.mode == .tty; + if (drawn and rp.echo.n > 0) { + // Drawn as the client draws it: each cell where it was + // predicted. + _ = frame_arena.reset(.retain_capacity); + core.needs_frame = true; + const t0 = pardes.FrameStats.nowNs(); + const surf = try core.render(frame_arena.allocator()); + try et.render_ns.append(gpa, pardes.FrameStats.nowNs() - t0); + const body = surf.region(.body, shell).?.rect; + const top = rp.echo.tops[shell]; + for (rp.echo.cells[0..rp.echo.n]) |cell| { + if (cell.row < top or surf.at(body.x + cell.x, body.y + @as(u16, @intCast(cell.row - top))).text[0] != cell.cp) et.paint_wrong += 1; + } + const t1 = pardes.FrameStats.nowNs(); + rp.echo.paint(core, surf, core.panes[shell].?, shell, body.x, body.w, body.y, body.h, true); + try et.paint_ns.append(gpa, pardes.FrameStats.nowNs() - t1); + et.drawn_frames += 1; + } + if (drawn) for (rp.echo.cells[0..rp.echo.n]) |cell| { + const k = &typed.items[cell.seq - 1]; + k.visible_frames += 1; + if (k.first_visible == null) { + k.first_visible = m.at; + if (trace) { + const st = core.panes[shell].?.terminal.?; + std.debug.print("{d} ms: key {d} ('{u}') drawn: trusted {} doubt {} phase {t} sem {t}\n", .{ m.at / 1000, cell.seq, cell.cp, rp.echo.trusted, rp.echo.doubt, st.stream.handler.phase, st.vt.screens.active.cursor.semantic_content }); + } + } + }; + const applied = if (rp.screens[shell]) |sc| sc.rep.seq else 0; + for (typed.items) |*k| if (k.echoed and k.seen == null and applied > k.version_before) { + k.seen = m.at; + }; + const busy = next_step < corpus.steps.items.len or queue.count() + 1 > periodic; + left[1] = if (busy) 60 else left[1] -| 1; + if (left[1] > 0) try push(&queue, &n, .{ .at = m.at + frame_us, .n = 0, .kind = .client_frame, .who = 1, .bytes = &.{} }) else periodic -= 1; + }, + .to_replica => { + rp.confirm(m.bytes); + rp.settle(); + }, + .screen_down => { + if (rp.screen(m.bytes)) |reply| { + const pane = m.bytes[0]; + if (reply[5] == 1) { + const sc = rp.screens[pane].?; + if (versions.get(@as(u64, sc.serial) << 32 | sc.rep.seq)) |want| { + if (want != screenHash(&rp.core().panes[pane].?.terminal.?.vt)) t.screens_wrong += 1; + } else t.screens_wrong += 1; + } + try push(&queue, &n, .{ .at = up[0].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .screen_up, .who = 1, .bytes = try gpa.dupe(u8, reply) }); + } + if (rp.screenRequest()) |req| try push(&queue, &n, .{ .at = up[0].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .screen_up, .who = 1, .bytes = try gpa.dupe(u8, req) }); + }, + .screen_up => { + if (try screens.take(a.core, peer, m.bytes)) |answer| try push(&queue, &n, .{ .at = down[0].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .screen_down, .who = 1, .bytes = answer }); + }, + .output => {}, + } + } + const s = rp.echo.stats; + et.predicted += s.predicted; + et.unpredicted += s.unpredicted; + et.confirmed += s.confirmed; + et.mispredicted += s.mispredicted; + et.cursor_missed += s.cursor_missed; + et.screens_wrong += t.screens_wrong; + for (typed.items) |k| { + et.keys += 1; + const sec = &et.sec[k.section]; + sec.keys += 1; + if (k.pcur != null) sec.predicted += 1; + if (k.visible_frames > 0 and k.truth != true) sec.wrong_frames += k.visible_frames; + if (k.truth) |ok| { + if (ok) et.right += 1 else et.wrong += 1; + } + const md = k.mode orelse .prompt; + if (md == .password or md == .sink) et.secret_frames += k.visible_frames; + if ((md == .vim or md == .vim_insert) and k.pcur != null) et.alt_predicted += 1; + if (k.visible_frames > 0 and k.truth != true) { + if (trace) std.debug.print("seed {d}: key {d} at {d} ms in {t} drawn {d} frames, truth {?}, predicted {any} cursor {any}, the authority after it {any}\n", .{ seed, k.seq, k.at / 1000, md, k.visible_frames, k.truth, k.pred, k.pcur, if (k.after) |af| .{ af.x, af.y } else null }); + et.wrong_shown += 1; + et.wrong_frames += k.visible_frames; + et.wrong_max = @max(et.wrong_max, k.visible_frames); + } + if (k.printable and k.echoed and (md == .prompt or md == .cat)) { + const seen = k.seen orelse std.math.maxInt(u64); + const drawn = if (k.first_visible != null and k.truth == true) @min(k.first_visible.?, seen) else seen; + if (drawn == std.math.maxInt(u64)) { + std.debug.print("seed {d} rtt {d} ms: a key's echo was never drawn\n", .{ seed, rtt_ms }); + et.unequal += 1; + continue; + } + et.echo_keys += 1; + try et.latency.append(gpa, drawn - k.at); + try sec.latency.append(gpa, drawn - k.at); + if (trace and drawn - k.at > 2 * frame_us) std.debug.print("key {d} at {d} ms in {t}: drawn after {d} ms, {s}\n", .{ k.seq, k.at / 1000, md, (drawn - k.at) / 1000, if (k.pcur == null) "not predicted" else if (k.first_visible == null) "predicted, not drawn" else if (k.truth != true) "predicted wrong" else "predicted, drawn late" }); + } + } + if (rp.diverged) |why| { + et.divergences += 1; + std.debug.print("seed {d} rtt {d} ms: the replica diverged: {s}\n", .{ seed, rtt_ms, why }); + } else if (!rp.quiet() or rp.digest() != replica.digestOf(a)) { + et.unequal += 1; + std.debug.print("seed {d} rtt {d} ms: the replica at quiescence: {s}\n", .{ seed, rtt_ms, if (rp.quiet()) "another digest" else "inputs still pending" }); + } + if (screenHash(&a.core.panes[shell].?.terminal.?.vt) != screenHash(&rp.core().panes[shell].?.terminal.?.vt)) { + et.unequal += 1; + std.debug.print("seed {d} rtt {d} ms: the shell at quiescence is not the authority's\n", .{ seed, rtt_ms }); + } +} + +fn echoMain(seeds: u64, first: u64, rtts: []const u64) !bool { + var failed = false; + var draw_lines: std.ArrayList(u8) = .empty; + defer draw_lines.deinit(gpa); + std.debug.print("predicted echo: one client typing the corpus into a shell, {d} seeds a cell; from a key to its character on the client's screen (ms, frames at 60 Hz)\n", .{seeds}); + std.debug.print(" rtt echo keys echoed p50 p90 max predicted unpredicted right/wrong confirmed mispredicted cursor-missed drawn-wrong keys/frames/max secret-frames vim-predicted diverged unequal screens-wrong\n", .{}); + var by_section: std.ArrayList(u8) = .empty; + defer by_section.deinit(gpa); + var off: [sections.len][2]u64 = undefined; + for (rtts) |rtt| for ([_]bool{ false, true }) |on| { + var et: EchoTotals = .{}; + defer et.deinit(); + for (first..first + seeds) |seed| try runEcho(seed, rtt, on, &et); + const ms = struct { + fn f(us: u64) f64 { + return @as(f64, @floatFromInt(us)) / 1000; + } + }.f; + std.debug.print("{d:>4} {s:>4} {d:>4} {d:>6} {d:>5.1} {d:>5.1} {d:>5.1} {d:>9} {d:>11} {d:>5}/{d:<5} {d:>9} {d:>12} {d:>13} {d:>5}/{d:>5}/{d:<5} {d:>13} {d:>13} {d:>8} {d:>7} {d:>13}\n", .{ + rtt, if (on) "on" else "off", et.keys, et.echo_keys, + ms(pct(et.latency.items, 50)), ms(pct(et.latency.items, 90)), ms(pct(et.latency.items, 100)), et.predicted, + et.unpredicted, et.right, et.wrong, et.confirmed, + et.mispredicted, et.cursor_missed, et.wrong_shown, et.wrong_frames, + et.wrong_max, et.secret_frames, et.alt_predicted, et.divergences, + et.unequal, et.screens_wrong, + }); + for (&et.sec, &off, sections) |*x, *o, name| { + const p50 = pct(x.latency.items, 50) / 1000; + const p90 = pct(x.latency.items, 90) / 1000; + if (!on) { + o.* = .{ p50, p90 }; + continue; + } + try by_section.print(gpa, "{d:>4} {s:<14} {d:>5} {d:>9} {d:>7} {d:>4} -> {d:<4} {d:>4} -> {d:<4} {d:>12}\n", .{ rtt, name, x.keys, x.predicted, x.latency.items.len, o[0], p50, o[1], p90, x.wrong_frames }); + } + if (on) try draw_lines.print(gpa, "{d:>4} {d:>12} {d:>6}/{d:<6} {d:>5}/{d:<5} {d:>10}\n", .{ rtt, et.drawn_frames, pct(et.render_ns.items, 50) / 1000, pct(et.render_ns.items, 99) / 1000, pct(et.paint_ns.items, 50), pct(et.paint_ns.items, 99), et.paint_wrong }); + if (et.divergences > 0 or et.unequal > 0 or et.screens_wrong > 0 or et.secret_frames > 0 or et.alt_predicted > 0 or et.paint_wrong > 0) failed = true; + }; + std.debug.print("by part of the corpus (all seeds): keys typed, predicted, echoed (the latency sample); key to its character on the screen, ms, without -> with; frames a wrong prediction was drawn\n rtt part keys predicted echoed p50 off/on p90 off/on drawn-wrong\n{s}", .{by_section.items}); + std.debug.print("the client's frames drawn with a prediction shown: its render (us) and the overlay's part (ns); cells drawn otherwise than predicted\n rtt frames-drawn render p50/p99 paint p50/p99 drawn-wrong\n{s}", .{draw_lines.items}); + return !failed; +} + + fn pct(samples: []u64, p: usize) u64 { if (samples.len == 0) return 0; std.mem.sort(u64, samples, {}, std.sort.asc(u64)); @@ -504,6 +1203,7 @@ pub fn main(init: std.process.Init) !void { var clients: u16 = 3; var rtts: []const u64 = &.{ 30, 80, 207 }; var shared = false; + var echo_mode = false; var flood_mb: u64 = 8; var rtt_buf: [8]u64 = undefined; var i: usize = 1; @@ -513,6 +1213,10 @@ pub fn main(init: std.process.Init) !void { shared = true; continue; } + if (std.mem.eql(u8, name, "--echo")) { + echo_mode = true; + continue; + } if (i + 1 >= args.len) return error.MissingValue; i += 1; const value = args[i]; @@ -530,6 +1234,10 @@ pub fn main(init: std.process.Init) !void { const dir = try std.fmt.bufPrint(&dir_buf, "{s}/replicas-{d}", .{ tmp, @as(u32, @intCast(libc.getpid())) }); try std.Io.Dir.createDirAbsolute(init.io, dir, .default_dir); defer std.Io.Dir.cwd().deleteTree(init.io, dir) catch {}; + if (echo_mode) { + if (!try echoMain(seeds, first, rtts)) std.process.exit(1); + return; + } var failed = false; std.debug.print("{d} seeds x {d} inputs from each of {d} clients, {s}, a TUI then {d} MB of yes in the shell; costs in us (frame {d})\n", .{ seeds, steps, clients, if (shared) "sharing one view" else "a view each", flood_mb, frame_us }); std.debug.print(" rtt inputs at-once stopped view units fast rollback(mis+foreign) rate rebase spec p50/p99 copy p50/p99 (KB) rollback p50/p99 diverged unequal\n", .{}); |
