a73x

da104e26

feat: prediction overlay — speculation as a layer, never as state

a73x   2026-08-08 15:01

Commit message
feat: prediction overlay — speculation as a layer, never as state

The replica keeps tracking exactly what the daemon said. Predictions live
beside it in a queue that is painted on top and reconciled cell by cell,
so a wrong guess costs a repaint and never a desync.

Predictability is decided by evidence rather than hope. Canonical echo
predicts from the first keystroke because the line discipline is going to
print the character anyway; a password prompt predicts nothing at all, so
there is nothing to leak or to hide; raw mode has to earn the right to be
seen by being right twice in a row, and loses it to a single
contradiction. A contradiction takes the WHOLE queue with it — every
prediction made after a wrong one was made against a screen that never
existed, and retiring only the wrong cell would let the rest be
"confirmed" against a reality they were never predicting.

Engine-free, so the entire policy is testable with no terminal, no pty and
no daemon: reconcile takes its grid duck-typed, and PlainGrid adapts the
plain dump a client already has. The queue is read back by index rather
than handed out as a slice, because a slice into an ArrayList goes stale
on the next keystroke — the shape the M8 records call the
UAF-that-never-crashes.

Wired into build.zig's test list in this commit, not a later one: a module
absent from that list is silently never run, and that has cost this
project before.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
build.zig
Old New
@@ -90,6 +90,17 @@ pub fn build(b: *std.Build) void {
90 .link_libc = true, 90 .link_libc = true,
91 }); 91 });
92 92
93 // Speculative local echo: the overlay and its policy, and deliberately
94 // nothing else. No engine import, which is what lets the whole state
95 // machine be exercised without a terminal — or a daemon — anywhere in
96 // the picture; reconcile takes its grid duck-typed instead.
97 const predict_mod = b.createModule(.{
98 .root_source_file = b.path("src/predict.zig"),
99 .target = target,
100 .optimize = optimize,
101 });
102 predict_mod.addImport("protocol", protocol_mod);
103
93 // Test-only: short temp paths for the tests that bind unix sockets. 104 // Test-only: short temp paths for the tests that bind unix sockets.
94 // Imported by every module that has such a test, which is why it is a 105 // Imported by every module that has such a test, which is why it is a
95 // module rather than three copies. 106 // module rather than three copies.
@@ -190,7 +201,7 @@ pub fn build(b: *std.Build) void {
190 // absence here was a live hazard recorded in decisions.md — muxd's 201 // absence here was a live hazard recorded in decisions.md — muxd's
191 // entrypoint could grow tests that silently never ran, exactly as 202 // entrypoint could grow tests that silently never ran, exactly as
192 // mux_main.zig's five did before it was added. 203 // mux_main.zig's five did before it was added.
193 for ([_]*std.Build.Module{ protocol_mod, engine_mod, pty_mod, server_mod, client_mod, proxy_mod, mux_mod, quic_mod, exe_mod, testtmp_mod, quic_client_mod }) |mod| { 204 for ([_]*std.Build.Module{ protocol_mod, engine_mod, pty_mod, server_mod, client_mod, proxy_mod, mux_mod, quic_mod, exe_mod, testtmp_mod, quic_client_mod, predict_mod }) |mod| {
194 const t = b.addTest(.{ .root_module = mod }); 205 const t = b.addTest(.{ .root_module = mod });
195 t.use_llvm = true; 206 t.use_llvm = true;
196 t.use_lld = true; 207 t.use_lld = true;
src/predict.zig
Old New
@@ -0,0 +1,823 @@
1 //! Speculative local echo, as an OVERLAY.
2 //!
3 //! The client's replica keeps tracking exactly what the daemon said, and
4 //! nothing in here is ever fed into it. Predictions live in a small queue
5 //! beside it, painted on top and reconciled cell by cell as authoritative
6 //! frames land. That separation is the whole design: a wrong prediction
7 //! costs a repaint, never a desync, and `muxd dump` and the client grid
8 //! stay comparable byte for byte at every moment.
9 //!
10 //! Engine-free on purpose. Nothing here imports a terminal, so the entire
11 //! policy — which contexts predict, what earns the right to be seen, what
12 //! takes it away — is exercised by tests with no engine, no pty and no
13 //! daemon in the picture. `reconcile` takes its grid duck-typed: anything
14 //! with `cellChar(row, col) ?u8` will do, and `PlainGrid` below is the
15 //! adapter over the plain dump a client already has.
16 //!
17 //! Memory: the overlay owns everything it holds. Predictions are copies of
18 //! bytes, never slices into frame payloads or engine rows, and the queue is
19 //! read back by index rather than handed out as a slice — a slice would go
20 //! stale on the next append, which is the shape the M8 egress records call
21 //! the UAF-that-never-crashes.
22 const std = @import("std");
23 const proto = @import("protocol");
24
25 /// One predicted character at one place on the grid. Printable ASCII only
26 /// in M9: `ch` is a byte by value, so there is nothing here that can outlive
27 /// what it was copied from.
28 pub const Cell = struct { row: u16, col: u16, ch: u8 };
29
30 pub const Pred = struct {
31 cell: Cell,
32 /// The authoritative seq the client held when this was predicted. A
33 /// frame carrying a HIGHER seq is the first one that could possibly
34 /// have been built after the keystroke reached the daemon, and so the
35 /// first one entitled to have an opinion about it.
36 made_seq: u64,
37 };
38
39 pub const Counters = struct {
40 made: u64 = 0,
41 displayed: u64 = 0,
42 confirmed: u64 = 0,
43 contradicted: u64 = 0,
44 suppressed: u64 = 0,
45 };
46
47 /// What the pty's mode bits say about predicting here.
48 /// .always — icanon && echo: the line discipline is going to print the
49 /// character itself, so predicting it is deduction.
50 /// .never — icanon && !echo: a password prompt. Nothing is predicted,
51 /// so there is nothing to leak, hide, or get wrong.
52 /// .adaptive — !icanon: raw mode. The application decides what a
53 /// keystroke looks like and we have to earn the right to
54 /// guess by being repeatedly right.
55 pub const Context = enum { always, never, adaptive };
56
57 /// Consecutive confirmations that earn display in `.adaptive`.
58 pub const promote_after: u8 = 2;
59
60 /// Engine-free mirror of the engine's cursor position.
61 pub const CursorPos = struct { x: u16 = 0, y: u16 = 0 };
62
63 pub const Outcome = union(enum) {
64 /// Refused. Nothing queued, nothing painted; the keystroke still goes
65 /// to the daemon exactly as it would have.
66 suppressed,
67 /// Queued, and to be painted at this cell now.
68 display: Cell,
69 /// Queued but deliberately invisible — adaptive mode gathering the
70 /// evidence that would let the next one be seen. The paint decision
71 /// arrives with the cell rather than being a separate question the
72 /// caller has to remember to ask, because "displayed" is what leg 3 of
73 /// the criterion counts and a forgotten check is how it gets violated.
74 hidden: Cell,
75 };
76
77 pub const Verdict = enum {
78 /// Nothing pending was old enough to judge.
79 none,
80 /// At least one prediction was confirmed and retired; none were wrong.
81 confirmed,
82 /// One was wrong, so the queue is empty and the caller should repaint.
83 contradicted,
84 };
85
86 /// Reads cells out of a plain grid dump: rows joined by '\n', trailing
87 /// blanks absent, which is the shape `Engine.dumpPlain` produces. Holds a
88 /// borrowed slice and is meant to be built, used and dropped inside one
89 /// reconcile call — never stored.
90 pub const PlainGrid = struct {
91 text: []const u8,
92 cols: u16,
93
94 /// null means "outside the grid", which is a different answer from "a
95 /// blank cell": a dump carries no trailing blanks, so a column past the
96 /// end of a row, or a row past the end of the dump, is blank rather
97 /// than missing. A cell holding a multi-byte character answers with its
98 /// lead byte, which cannot equal a predicted printable ASCII byte —
99 /// so such a cell contradicts, which is the safe direction.
100 pub fn cellChar(self: PlainGrid, row: u16, col: u16) ?u8 {
101 if (col >= self.cols) return null;
102 var y: u16 = 0;
103 var it = std.mem.splitScalar(u8, self.text, '\n');
104 while (it.next()) |line| : (y += 1) {
105 if (y != row) continue;
106 if (col >= line.len) return ' ';
107 return line[col];
108 }
109 return ' ';
110 }
111 };
112
113 pub const Overlay = struct {
114 alloc: std.mem.Allocator,
115 pending: std.ArrayList(Pred) = .empty,
116 /// Cells removed by the most recent reconcile — the caller's repaint
117 /// list, since a retired prediction is still on the screen underlined
118 /// until someone paints that cell from the replica. Never accumulates
119 /// across calls. Its capacity is kept at or above `pending.len` by
120 /// predictAt, which is what lets reconcile fill it without being able
121 /// to fail partway through a judgement.
122 retired: std.ArrayList(Cell) = .empty,
123 ctx: Context = .never,
124 /// The single gate on painting: true in `.always`, false in `.never`,
125 /// and earned in `.adaptive`.
126 confident: bool = false,
127 streak: u8 = 0,
128 counters: Counters = .{},
129 cols: u16,
130 rows: u16,
131 scroll_mode: bool = false,
132 resize_pending: bool = false,
133 /// The last authoritative seq the client applied; stamped onto each new
134 /// prediction as `made_seq`.
135 last_seq: u64 = 0,
136
137 pub fn init(alloc: std.mem.Allocator, cols: u16, rows: u16) Overlay {
138 return .{ .alloc = alloc, .cols = cols, .rows = rows };
139 }
140
141 pub fn deinit(self: *Overlay) void {
142 self.pending.deinit(self.alloc);
143 self.retired.deinit(self.alloc);
144 }
145
146 /// Adopt what the daemon says the pty is doing. No frame ever having
147 /// arrived leaves the overlay at `.never`, which is the safe default an
148 /// old daemon gets for free.
149 pub fn setMode(self: *Overlay, flags: proto.PtyModeFlags) void {
150 const next: Context = blk: {
151 // A bit we do not understand means the byte describes a
152 // terminal we cannot reason about. Predict nothing rather than
153 // mask it off and carry on as though we had understood.
154 if (flags._pad != 0) break :blk .never;
155 if (!flags.icanon) break :blk .adaptive;
156 break :blk if (flags.echo) .always else .never;
157 };
158 if (next == self.ctx) return;
159 self.ctx = next;
160 // Outstanding predictions were made under the old policy, and the
161 // new one may be that they should never have been visible.
162 self.flush();
163 self.streak = 0;
164 self.confident = (next == .always);
165 }
166
167 /// A resize invalidates every prediction on the old grid, and moves the
168 /// edge that the last-column refusal is measured against.
169 pub fn setGrid(self: *Overlay, cols: u16, rows: u16) void {
170 if (cols == self.cols and rows == self.rows) return;
171 self.cols = cols;
172 self.rows = rows;
173 self.flush();
174 }
175
176 pub fn setScrollMode(self: *Overlay, on: bool) void {
177 if (on == self.scroll_mode) return;
178 self.scroll_mode = on;
179 // Entering scroll mode the cursor stops being where the user is
180 // looking; leaving it, the whole viewport is repainted. Either way
181 // what is queued no longer describes the screen.
182 self.flush();
183 }
184
185 pub fn setResizePending(self: *Overlay, pending: bool) void {
186 if (pending == self.resize_pending) return;
187 self.resize_pending = pending;
188 if (pending) self.flush();
189 }
190
191 /// Record the authoritative seq the client now holds. reconcile does
192 /// this itself; the client calls it directly on the paths that apply a
193 /// frame without judging anything, a snapshot being the one that
194 /// matters.
195 pub fn noteSeq(self: *Overlay, seq: u64) void {
196 self.last_seq = seq;
197 }
198
199 /// Speculate one printable byte at the cursor, or refuse to.
200 ///
201 /// Every refusal is a place where being wrong would cost more than
202 /// being slow: a control byte we cannot render, a multi-byte sequence
203 /// whose width we do not know, the last column (wrap is the
204 /// application's policy, not ours), a viewport that is scrolled away
205 /// from the cursor, a grid that is about to be resized out from under
206 /// the paint, and a `.never` context where the answer is the whole
207 /// point. Infallible by construction: an allocation failure suppresses
208 /// rather than propagating, because no keystroke is worth failing over
209 /// a speculation.
210 pub fn predictAt(self: *Overlay, cursor: CursorPos, ch: u8) Outcome {
211 if (self.ctx == .never) return self.suppress();
212 if (self.scroll_mode or self.resize_pending) return self.suppress();
213 if (ch < 0x20 or ch >= 0x7f) return self.suppress();
214 if (self.cols == 0 or self.rows == 0) return self.suppress();
215 if (cursor.y >= self.rows) return self.suppress();
216 if (cursor.x >= self.cols -| 1) return self.suppress();
217
218 const cell: Cell = .{ .row = cursor.y, .col = cursor.x, .ch = ch };
219 // Reserved before the queue grows, so reconcile can retire every
220 // pending cell into `retired` without a fallible call in the middle
221 // of a judgement it has already half-made.
222 self.retired.ensureTotalCapacity(self.alloc, self.pending.items.len + 1) catch
223 return self.suppress();
224 self.pending.append(self.alloc, .{ .cell = cell, .made_seq = self.last_seq }) catch
225 return self.suppress();
226
227 self.counters.made += 1;
228 if (self.confident) {
229 self.counters.displayed += 1;
230 return .{ .display = cell };
231 }
232 return .{ .hidden = cell };
233 }
234
235 fn suppress(self: *Overlay) Outcome {
236 self.counters.suppressed += 1;
237 return .suppressed;
238 }
239
240 /// Judge everything the newly applied frame is entitled to judge.
241 ///
242 /// A confirmed prediction retires and lengthens the streak. A
243 /// contradicted one takes the WHOLE queue with it — mosh's epoch bump,
244 /// and the reason is not economy: every prediction made after a wrong
245 /// one was made against a screen that never existed, so retiring only
246 /// the wrong cell would leave the rest to be "confirmed" against a
247 /// reality they were never predicting.
248 pub fn reconcile(self: *Overlay, reader: anytype, applied_seq: u64) Verdict {
249 self.retired.clearRetainingCapacity();
250 var verdict: Verdict = .none;
251 var i: usize = 0;
252 while (i < self.pending.items.len) {
253 const p = self.pending.items[i];
254 if (p.made_seq >= applied_seq) {
255 i += 1; // too new to be evidence about
256 continue;
257 }
258 const shown = reader.cellChar(p.cell.row, p.cell.col);
259 if (shown != null and shown.? == p.cell.ch) {
260 _ = self.pending.orderedRemove(i);
261 self.retired.appendAssumeCapacity(p.cell);
262 self.counters.confirmed += 1;
263 self.streak +|= 1;
264 if (self.ctx == .adaptive and self.streak >= promote_after) {
265 self.confident = true;
266 }
267 verdict = .confirmed;
268 continue; // index i now holds the next prediction
269 }
270
271 self.counters.contradicted += 1;
272 self.streak = 0;
273 // Demotion is an adaptive-only idea. In canonical echo the pty
274 // is going to print the character whatever we believe, so a
275 // disagreement means we put it in the wrong place, not that we
276 // should stop predicting.
277 if (self.ctx == .adaptive) self.confident = false;
278 for (self.pending.items) |q| self.retired.appendAssumeCapacity(q.cell);
279 self.pending.clearRetainingCapacity();
280 self.noteSeq(applied_seq);
281 return .contradicted;
282 }
283 self.noteSeq(applied_seq);
284 return verdict;
285 }
286
287 /// Drop every prediction without calling any of them wrong. For the
288 /// events after which we can no longer find out — a snapshot, a resize,
289 /// scroll mode, a reconnect. Counting these as contradictions would fire
290 /// the demotion machinery on a window resize.
291 pub fn flush(self: *Overlay) void {
292 self.pending.clearRetainingCapacity();
293 self.retired.clearRetainingCapacity();
294 }
295
296 /// Where the cursor appears to be, given what is queued: the
297 /// authoritative position advanced past the last pending prediction.
298 /// With nothing pending it is the daemon's own answer, untouched.
299 pub fn predictedCursor(self: *const Overlay, base: CursorPos) CursorPos {
300 const last = self.pending.getLastOrNull() orelse return base;
301 return .{ .x = last.cell.col + 1, .y = last.cell.row };
302 }
303
304 pub fn pendingCount(self: *const Overlay) usize {
305 return self.pending.items.len;
306 }
307
308 /// By value: the queue reallocates as it grows, so handing out a slice
309 /// into it would hand out something that goes stale on the next
310 /// keystroke.
311 pub fn pendingAt(self: *const Overlay, i: usize) Pred {
312 return self.pending.items[i];
313 }
314
315 pub fn retiredCount(self: *const Overlay) usize {
316 return self.retired.items.len;
317 }
318
319 pub fn retiredAt(self: *const Overlay, i: usize) Cell {
320 return self.retired.items[i];
321 }
322 };
323
324 // ---- tests ------------------------------------------------------------
325
326 /// A grid row set built the way a plain dump arrives: rows joined by '\n',
327 /// trailing blanks absent. Caller frees.
328 fn plainOf(alloc: std.mem.Allocator, rows: []const []const u8) ![]u8 {
329 return std.mem.join(alloc, "\n", rows);
330 }
331
332 test "setMode maps the pty's two bits onto the three policies" {
333 const alloc = std.testing.allocator;
334 const cases = [_]struct { icanon: bool, echo: bool, want: Context }{
335 // Canonical and echoing: the tty itself will put the character on
336 // the screen, so predicting it is not a guess at all.
337 .{ .icanon = true, .echo = true, .want = .always },
338 // Canonical and silent: a password prompt. Nothing may be shown.
339 .{ .icanon = true, .echo = false, .want = .never },
340 // Raw: the application decides what a keystroke looks like, and the
341 // only way to find out is to be right about it repeatedly.
342 .{ .icanon = false, .echo = true, .want = .adaptive },
343 .{ .icanon = false, .echo = false, .want = .adaptive },
344 };
345 for (cases) |c| {
346 var ov = Overlay.init(alloc, 80, 24);
347 defer ov.deinit();
348 ov.setMode(.{ .icanon = c.icanon, .echo = c.echo });
349 try std.testing.expectEqual(c.want, ov.ctx);
350 }
351 }
352
353 test "a mode byte carrying a bit we do not understand predicts nothing" {
354 const alloc = std.testing.allocator;
355 var ov = Overlay.init(alloc, 80, 24);
356 defer ov.deinit();
357 ov.setMode(.{ .icanon = true, .echo = true });
358 try std.testing.expectEqual(Context.always, ov.ctx);
359
360 // A future daemon defines a third bit. Read as canonical-and-echoing
361 // with the extra bit masked away, this would keep predicting against a
362 // terminal whose description we have only partly understood.
363 ov.setMode(.{ .icanon = true, .echo = true, ._pad = 1 });
364 try std.testing.expectEqual(Context.never, ov.ctx);
365 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, 'a') == .suppressed);
366 }
367
368 test "an overlay predicts nothing until it has been told what the pty is" {
369 const alloc = std.testing.allocator;
370 var ov = Overlay.init(alloc, 80, 24);
371 defer ov.deinit();
372 // No pty_mode frame has arrived (or the daemon is too old to send one).
373 // No frame, no prediction: the safe direction is the default one.
374 try std.testing.expectEqual(Context.never, ov.ctx);
375 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, 'a') == .suppressed);
376 try std.testing.expectEqual(@as(u64, 0), ov.counters.made);
377 }
378
379 test "always: the first keystroke paints, with no evidence required" {
380 const alloc = std.testing.allocator;
381 var ov = Overlay.init(alloc, 80, 24);
382 defer ov.deinit();
383 ov.setMode(.{ .icanon = true, .echo = true });
384
385 const out = ov.predictAt(.{ .x = 3, .y = 2 }, 'k');
386 try std.testing.expect(out == .display);
387 try std.testing.expectEqual(@as(u16, 3), out.display.col);
388 try std.testing.expectEqual(@as(u16, 2), out.display.row);
389 try std.testing.expectEqual(@as(u8, 'k'), out.display.ch);
390 try std.testing.expectEqual(@as(u64, 1), ov.counters.made);
391 try std.testing.expectEqual(@as(u64, 1), ov.counters.displayed);
392 try std.testing.expectEqual(@as(usize, 1), ov.pendingCount());
393 }
394
395 test "never: nothing is made, so nothing can leak" {
396 const alloc = std.testing.allocator;
397 var ov = Overlay.init(alloc, 80, 24);
398 defer ov.deinit();
399 ov.setMode(.{ .icanon = true, .echo = false });
400
401 for ("hunter2") |ch| {
402 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, ch) == .suppressed);
403 }
404 // Both counters, deliberately: leg 3 of the criterion asserts made as
405 // well as displayed, because "made but hidden" in a password context
406 // would still put the password in a buffer the overlay paints from.
407 try std.testing.expectEqual(@as(u64, 0), ov.counters.made);
408 try std.testing.expectEqual(@as(u64, 0), ov.counters.displayed);
409 try std.testing.expectEqual(@as(u64, 7), ov.counters.suppressed);
410 try std.testing.expectEqual(@as(usize, 0), ov.pendingCount());
411 }
412
413 test "adaptive earns the right to display, one confirm at a time" {
414 const alloc = std.testing.allocator;
415 var ov = Overlay.init(alloc, 80, 24);
416 defer ov.deinit();
417 ov.setMode(.{ .icanon = false, .echo = false });
418
419 // Written out with literal counts rather than a loop over promote_after:
420 // a loop parameterised by the constant moves its own goalposts when the
421 // constant is mutated, and would have passed at 1 and at 3 alike.
422 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, 'a') == .hidden);
423 {
424 const text = try plainOf(alloc, &.{"a"});
425 defer alloc.free(text);
426 try std.testing.expectEqual(
427 Verdict.confirmed,
428 ov.reconcile(PlainGrid{ .text = text, .cols = 80 }, 1),
429 );
430 }
431
432 // Still hidden: one confirm is not two.
433 try std.testing.expect(ov.predictAt(.{ .x = 1, .y = 0 }, 'b') == .hidden);
434 {
435 const text = try plainOf(alloc, &.{"ab"});
436 defer alloc.free(text);
437 try std.testing.expectEqual(
438 Verdict.confirmed,
439 ov.reconcile(PlainGrid{ .text = text, .cols = 80 }, 2),
440 );
441 }
442
443 try std.testing.expectEqual(@as(u64, 2), ov.counters.confirmed);
444 try std.testing.expectEqual(@as(u64, 0), ov.counters.displayed);
445
446 // Two consecutive confirms, and the third keystroke paints.
447 try std.testing.expect(ov.predictAt(.{ .x = 2, .y = 0 }, 'c') == .display);
448 try std.testing.expectEqual(@as(u64, 3), ov.counters.made);
449 try std.testing.expectEqual(@as(u64, 1), ov.counters.displayed);
450 }
451
452 test "a contradiction flushes the whole queue, not merely the cell that was wrong" {
453 const alloc = std.testing.allocator;
454 var ov = Overlay.init(alloc, 80, 24);
455 defer ov.deinit();
456 ov.setMode(.{ .icanon = true, .echo = true });
457
458 _ = ov.predictAt(.{ .x = 0, .y = 0 }, 'a');
459 _ = ov.predictAt(.{ .x = 1, .y = 0 }, 'b');
460 _ = ov.predictAt(.{ .x = 2, .y = 0 }, 'c');
461 try std.testing.expectEqual(@as(usize, 3), ov.pendingCount());
462
463 // The replica disagrees about the FIRST cell. The two behind it would
464 // each have matched — which is the point: everything typed after a
465 // wrong prediction was typed into a screen that never existed.
466 const text = try plainOf(alloc, &.{"xbc"});
467 defer alloc.free(text);
468 try std.testing.expectEqual(
469 Verdict.contradicted,
470 ov.reconcile(PlainGrid{ .text = text, .cols = 80 }, 1),
471 );
472
473 try std.testing.expectEqual(@as(usize, 0), ov.pendingCount());
474 try std.testing.expectEqual(@as(u64, 1), ov.counters.contradicted);
475 // Zero, not two. An implementation that retired only the wrong cell and
476 // carried on judging would count the other two as confirmed, and would
477 // be claiming agreement about a screen it had already been told it was
478 // wrong about.
479 try std.testing.expectEqual(@as(u64, 0), ov.counters.confirmed);
480 }
481
482 test "adaptive is demoted by one contradiction and must earn display again" {
483 const alloc = std.testing.allocator;
484 var ov = Overlay.init(alloc, 80, 24);
485 defer ov.deinit();
486 ov.setMode(.{ .icanon = false, .echo = false });
487
488 // Earn it.
489 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, 'a') == .hidden);
490 {
491 const text = try plainOf(alloc, &.{"a"});
492 defer alloc.free(text);
493 _ = ov.reconcile(PlainGrid{ .text = text, .cols = 80 }, 1);
494 }
495 try std.testing.expect(ov.predictAt(.{ .x = 1, .y = 0 }, 'b') == .hidden);
496 {
497 const text = try plainOf(alloc, &.{"ab"});
498 defer alloc.free(text);
499 _ = ov.reconcile(PlainGrid{ .text = text, .cols = 80 }, 2);
500 }
501 try std.testing.expect(ov.predictAt(.{ .x = 2, .y = 0 }, 'c') == .display);
502
503 // Lose it, on the first keystroke the application handles its own way —
504 // a normal-mode key in an editor, say, which prints nothing at all.
505 {
506 const text = try plainOf(alloc, &.{"ab"});
507 defer alloc.free(text);
508 try std.testing.expectEqual(
509 Verdict.contradicted,
510 ov.reconcile(PlainGrid{ .text = text, .cols = 80 }, 3),
511 );
512 }
513 try std.testing.expect(!ov.confident);
514
515 // ...and the very next keystroke is invisible again. One contradicted
516 // prediction, one demotion: that is leg 3 of the criterion.
517 try std.testing.expect(ov.predictAt(.{ .x = 2, .y = 0 }, 'c') == .hidden);
518 }
519
520 test "always is never demoted: a contradiction costs the queue, not the policy" {
521 const alloc = std.testing.allocator;
522 var ov = Overlay.init(alloc, 80, 24);
523 defer ov.deinit();
524 ov.setMode(.{ .icanon = true, .echo = true });
525
526 _ = ov.predictAt(.{ .x = 0, .y = 0 }, 'a');
527 const text = try plainOf(alloc, &.{"z"});
528 defer alloc.free(text);
529 try std.testing.expectEqual(
530 Verdict.contradicted,
531 ov.reconcile(PlainGrid{ .text = text, .cols = 80 }, 1),
532 );
533 // In canonical echo the pty is going to print the character whatever we
534 // do, so a disagreement means we mis-placed it, not that we should stop
535 // predicting. Confidence here is not earned and cannot be lost.
536 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, 'a') == .display);
537 }
538
539 test "predictAt refuses everything the plan says it must" {
540 const alloc = std.testing.allocator;
541
542 // Non-printables: control bytes carry meaning we cannot render, and the
543 // high half is a multi-byte sequence whose width we do not know.
544 for ([_]u8{ 0x00, 0x08, 0x09, 0x0a, 0x0d, 0x1b, 0x7f, 0x80, 0xc3, 0xff }) |ch| {
545 var ov = Overlay.init(alloc, 80, 24);
546 defer ov.deinit();
547 ov.setMode(.{ .icanon = true, .echo = true });
548 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, ch) == .suppressed);
549 try std.testing.expectEqual(@as(u64, 1), ov.counters.suppressed);
550 }
551
552 // The last column: what happens there is the application's policy
553 // (wrap, scroll, truncate, refuse) and we do not get to guess it.
554 {
555 var ov = Overlay.init(alloc, 80, 24);
556 defer ov.deinit();
557 ov.setMode(.{ .icanon = true, .echo = true });
558 try std.testing.expect(ov.predictAt(.{ .x = 78, .y = 0 }, 'a') == .display);
559 try std.testing.expect(ov.predictAt(.{ .x = 79, .y = 0 }, 'a') == .suppressed);
560 }
561
562 // Off the grid entirely.
563 {
564 var ov = Overlay.init(alloc, 80, 24);
565 defer ov.deinit();
566 ov.setMode(.{ .icanon = true, .echo = true });
567 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 24 }, 'a') == .suppressed);
568 }
569
570 // Scrolled back: the cursor is not where the user is looking, so a
571 // prediction painted at it would land in the middle of history.
572 {
573 var ov = Overlay.init(alloc, 80, 24);
574 defer ov.deinit();
575 ov.setMode(.{ .icanon = true, .echo = true });
576 ov.setScrollMode(true);
577 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, 'a') == .suppressed);
578 ov.setScrollMode(false);
579 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, 'a') == .display);
580 }
581
582 // A resize we have asked for but not yet been answered about: the grid
583 // the prediction would be painted on is about to stop existing.
584 {
585 var ov = Overlay.init(alloc, 80, 24);
586 defer ov.deinit();
587 ov.setMode(.{ .icanon = true, .echo = true });
588 ov.setResizePending(true);
589 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, 'a') == .suppressed);
590 ov.setResizePending(false);
591 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, 'a') == .display);
592 }
593 }
594
595 test "a frame that cannot have seen the keystroke does not get to judge it" {
596 const alloc = std.testing.allocator;
597 var ov = Overlay.init(alloc, 80, 24);
598 defer ov.deinit();
599 ov.setMode(.{ .icanon = true, .echo = true });
600
601 // The client is holding seq 7 when the key is pressed.
602 ov.noteSeq(7);
603 _ = ov.predictAt(.{ .x = 0, .y = 0 }, 'a');
604
605 // A frame numbered 7 is the one we already had. It is not evidence
606 // about a keystroke that was made after it.
607 const text = try plainOf(alloc, &.{" "});
608 defer alloc.free(text);
609 try std.testing.expectEqual(
610 Verdict.none,
611 ov.reconcile(PlainGrid{ .text = text, .cols = 80 }, 7),
612 );
613 try std.testing.expectEqual(@as(usize, 1), ov.pendingCount());
614 try std.testing.expectEqual(@as(u64, 0), ov.counters.contradicted);
615 try std.testing.expectEqual(@as(u64, 0), ov.counters.confirmed);
616
617 // Seq 8 is the first frame the daemon could have built after seeing it.
618 try std.testing.expectEqual(
619 Verdict.contradicted,
620 ov.reconcile(PlainGrid{ .text = text, .cols = 80 }, 8),
621 );
622 }
623
624 test "flush drops predictions without calling any of them wrong" {
625 const alloc = std.testing.allocator;
626 var ov = Overlay.init(alloc, 80, 24);
627 defer ov.deinit();
628 ov.setMode(.{ .icanon = true, .echo = true });
629
630 _ = ov.predictAt(.{ .x = 0, .y = 0 }, 'a');
631 _ = ov.predictAt(.{ .x = 1, .y = 0 }, 'b');
632 ov.flush();
633
634 try std.testing.expectEqual(@as(usize, 0), ov.pendingCount());
635 // A snapshot, a resize or a reconnect is not evidence that a prediction
636 // was mistaken — it is evidence that we can no longer find out. Counting
637 // it as a contradiction would make the demotion machinery fire on a
638 // window resize.
639 try std.testing.expectEqual(@as(u64, 0), ov.counters.contradicted);
640 try std.testing.expectEqual(@as(u64, 0), ov.counters.confirmed);
641 }
642
643 test "a context change flushes; staying in the same context does not" {
644 const alloc = std.testing.allocator;
645 var ov = Overlay.init(alloc, 80, 24);
646 defer ov.deinit();
647 ov.setMode(.{ .icanon = true, .echo = true });
648 _ = ov.predictAt(.{ .x = 0, .y = 0 }, 'a');
649 _ = ov.predictAt(.{ .x = 1, .y = 0 }, 'b');
650
651 // The same bits again: a daemon re-sending state on reattach must not
652 // throw away predictions that are still perfectly good.
653 ov.setMode(.{ .icanon = true, .echo = true });
654 try std.testing.expectEqual(@as(usize, 2), ov.pendingCount());
655
656 // Into a password prompt, with predictions outstanding. They go.
657 ov.setMode(.{ .icanon = true, .echo = false });
658 try std.testing.expectEqual(@as(usize, 0), ov.pendingCount());
659 }
660
661 test "entering raw mode starts unconfident however confident we just were" {
662 const alloc = std.testing.allocator;
663 var ov = Overlay.init(alloc, 80, 24);
664 defer ov.deinit();
665 ov.setMode(.{ .icanon = true, .echo = true });
666 try std.testing.expect(ov.confident);
667
668 ov.setMode(.{ .icanon = false, .echo = false });
669 try std.testing.expect(!ov.confident);
670 try std.testing.expect(ov.predictAt(.{ .x = 0, .y = 0 }, 'a') == .hidden);
671 }
672
673 test "a resize flushes and moves the edge the last column is measured from" {
674 const alloc = std.testing.allocator;
675 var ov = Overlay.init(alloc, 80, 24);
676 defer ov.deinit();
677 ov.setMode(.{ .icanon = true, .echo = true });
678 _ = ov.predictAt(.{ .x = 0, .y = 0 }, 'a');
679
680 ov.setGrid(40, 12);
681 try std.testing.expectEqual(@as(usize, 0), ov.pendingCount());
682 try std.testing.expect(ov.predictAt(.{ .x = 39, .y = 0 }, 'a') == .suppressed);
683 try std.testing.expect(ov.predictAt(.{ .x = 38, .y = 0 }, 'a') == .display);
684
685 // The same size again is not a resize and costs nothing.
686 _ = ov.predictAt(.{ .x = 0, .y = 1 }, 'b');
687 const before = ov.pendingCount();
688 ov.setGrid(40, 12);
689 try std.testing.expectEqual(before, ov.pendingCount());
690 }
691
692 test "predictedCursor advances the base past everything pending" {
693 const alloc = std.testing.allocator;
694 var ov = Overlay.init(alloc, 80, 24);
695 defer ov.deinit();
696 ov.setMode(.{ .icanon = true, .echo = true });
697
698 // With nothing pending the cursor is the daemon's, untouched.
699 try std.testing.expectEqual(
700 CursorPos{ .x = 5, .y = 1 },
701 ov.predictedCursor(.{ .x = 5, .y = 1 }),
702 );
703
704 var cur = CursorPos{ .x = 5, .y = 1 };
705 for ("abc") |ch| {
706 _ = ov.predictAt(cur, ch);
707 cur = ov.predictedCursor(.{ .x = 5, .y = 1 });
708 }
709 try std.testing.expectEqual(CursorPos{ .x = 8, .y = 1 }, cur);
710
711 // And it comes back to the authoritative cursor when the queue empties.
712 ov.flush();
713 try std.testing.expectEqual(
714 CursorPos{ .x = 5, .y = 1 },
715 ov.predictedCursor(.{ .x = 5, .y = 1 }),
716 );
717 }
718
719 test "a queued prediction owns its byte; the caller's buffer may be reused" {
720 const alloc = std.testing.allocator;
721 var ov = Overlay.init(alloc, 80, 24);
722 defer ov.deinit();
723 ov.setMode(.{ .icanon = true, .echo = true });
724
725 // Exactly the shape of the client's stdin path: bytes are read into a
726 // buffer that is about to be read into again. Anything the overlay keeps
727 // pointing at that buffer is the UAF-that-never-crashes.
728 const src = try alloc.alloc(u8, 3);
729 defer alloc.free(src);
730 @memcpy(src, "abc");
731 for (src, 0..) |ch, i| {
732 _ = ov.predictAt(.{ .x = @intCast(i), .y = 0 }, ch);
733 }
734 @memset(src, 0xFF);
735
736 try std.testing.expectEqual(@as(u8, 'a'), ov.pendingAt(0).cell.ch);
737 try std.testing.expectEqual(@as(u8, 'b'), ov.pendingAt(1).cell.ch);
738 try std.testing.expectEqual(@as(u8, 'c'), ov.pendingAt(2).cell.ch);
739
740 // And the judgement is made against what was typed, not against
741 // whatever the buffer holds by the time the frame comes back.
742 const text = try plainOf(alloc, &.{"abc"});
743 defer alloc.free(text);
744 try std.testing.expectEqual(
745 Verdict.confirmed,
746 ov.reconcile(PlainGrid{ .text = text, .cols = 80 }, 1),
747 );
748 try std.testing.expectEqual(@as(u64, 3), ov.counters.confirmed);
749 }
750
751 test "the queue survives its own growth" {
752 const alloc = std.testing.allocator;
753 var ov = Overlay.init(alloc, 80, 24);
754 defer ov.deinit();
755 ov.setMode(.{ .icanon = true, .echo = true });
756
757 // Well past any initial capacity, so the backing array is reallocated
758 // several times underneath the predictions already in it.
759 var i: u16 = 0;
760 while (i < 70) : (i += 1) {
761 const ch: u8 = 'a' + @as(u8, @intCast(i % 26));
762 try std.testing.expect(ov.predictAt(.{ .x = i, .y = 0 }, ch) == .display);
763 }
764 try std.testing.expectEqual(@as(usize, 70), ov.pendingCount());
765
766 i = 0;
767 while (i < 70) : (i += 1) {
768 const want: u8 = 'a' + @as(u8, @intCast(i % 26));
769 try std.testing.expectEqual(want, ov.pendingAt(i).cell.ch);
770 try std.testing.expectEqual(i, ov.pendingAt(i).cell.col);
771 }
772 }
773
774 test "reconcile hands back the cells it retired, so the caller can repaint them" {
775 const alloc = std.testing.allocator;
776 var ov = Overlay.init(alloc, 80, 24);
777 defer ov.deinit();
778 ov.setMode(.{ .icanon = true, .echo = true });
779
780 _ = ov.predictAt(.{ .x = 0, .y = 0 }, 'a');
781 _ = ov.predictAt(.{ .x = 1, .y = 0 }, 'b');
782 const text = try plainOf(alloc, &.{"ab"});
783 defer alloc.free(text);
784 try std.testing.expectEqual(
785 Verdict.confirmed,
786 ov.reconcile(PlainGrid{ .text = text, .cols = 80 }, 1),
787 );
788
789 // A confirmed prediction is still painted underlined until someone
790 // repaints that cell from the replica, so the cells that left the queue
791 // are exactly the repaint list.
792 try std.testing.expectEqual(@as(usize, 2), ov.retiredCount());
793 try std.testing.expectEqual(@as(u16, 0), ov.retiredAt(0).col);
794 try std.testing.expectEqual(@as(u16, 1), ov.retiredAt(1).col);
795
796 // ...and it describes the LAST reconcile only, never accumulates.
797 _ = ov.predictAt(.{ .x = 2, .y = 0 }, 'c');
798 const text2 = try plainOf(alloc, &.{"abc"});
799 defer alloc.free(text2);
800 _ = ov.reconcile(PlainGrid{ .text = text2, .cols = 80 }, 2);
801 try std.testing.expectEqual(@as(usize, 1), ov.retiredCount());
802 try std.testing.expectEqual(@as(u16, 2), ov.retiredAt(0).col);
803 }
804
805 test "PlainGrid reads a cell out of a dump, and blanks where the dump stops" {
806 const alloc = std.testing.allocator;
807 const text = try plainOf(alloc, &.{ "ab", "cd" });
808 defer alloc.free(text);
809 const g = PlainGrid{ .text = text, .cols = 80 };
810
811 try std.testing.expectEqual(@as(?u8, 'a'), g.cellChar(0, 0));
812 try std.testing.expectEqual(@as(?u8, 'b'), g.cellChar(0, 1));
813 try std.testing.expectEqual(@as(?u8, 'c'), g.cellChar(1, 0));
814 try std.testing.expectEqual(@as(?u8, 'd'), g.cellChar(1, 1));
815
816 // A dump carries no trailing blanks, so a cell past the end of a row —
817 // or past the last row — is a blank cell, not a missing one.
818 try std.testing.expectEqual(@as(?u8, ' '), g.cellChar(0, 2));
819 try std.testing.expectEqual(@as(?u8, ' '), g.cellChar(9, 0));
820
821 // Outside the grid is a different answer: nothing to compare against.
822 try std.testing.expectEqual(@as(?u8, null), g.cellChar(0, 80));
823 }