1// Predictive local echo: speculative glyphs painted at the moment a key is
2// pressed, before the pty has echoed anything back.
3//
4// The idea is mosh's, but the soundness gate is not. Mosh runs against a bare
5// byte stream and has to *guess* whether the far end is in a line-editing mode
6// that will echo what you typed; it guesses wrong in full-screen applications
7// and pays for it with visible retractions. We have shell integration, so we
8// can prove it instead: OSC 133/633 tells us a prompt has started accepting
9// input (`B`) and has not yet executed (`C`), which is exactly the readline
10// region where a typed character echoes at the cursor and nowhere else.
11//
12// Everything outside that proof is refused rather than guessed. The engine
13// predicts single-column printable ASCII and backspaces over its own earlier
14// predictions; wide characters, combining marks, wraps, control keys, and paste
15// all drop the whole speculation instead of extending it. That is a deliberate
16// scope: a wrong prediction is worse than a late one, and JavaScript never
17// re-segments cells (Ghostty owns grapheme boundaries and width).
18//
19// Pure by construction: no DOM, no wasm, no clock. Time arrives as a `now`
20// argument and screen state as plain data, so the whole thing is property
21// testable without a terminal.
22
23/** `off` disables prediction entirely; `prompt` predicts only inside a proven readline region. */
24export type PredictionMode = "off" | "prompt";
25
26export interface PredictOptions {
27 mode?: PredictionMode;
28 /**
29 * Show predictions only once the measured round trip reaches this. On a fast
30 * link the echo beats the next frame anyway, so predicting only adds a chance
31 * to be wrong. 0 displays from the first keystroke.
32 */
33 minLatencyMs?: number;
34 /** Drop the whole speculation when a prediction goes this long unconfirmed. */
35 timeoutMs?: number;
36 /** Underline unconfirmed predictions so speculation is legible as speculation. */
37 underline?: boolean;
38 /** Hard cap on outstanding predictions; exceeding it drops the speculation. */
39 maxPredictions?: number;
40}
41
42export interface ResolvedPredictOptions {
43 readonly mode: PredictionMode;
44 readonly minLatencyMs: number;
45 readonly timeoutMs: number;
46 readonly underline: boolean;
47 readonly maxPredictions: number;
48}
49
50export const DEFAULT_PREDICT_OPTIONS: ResolvedPredictOptions = {
51 mode: "off",
52 minLatencyMs: 25,
53 timeoutMs: 1000,
54 underline: true,
55 maxPredictions: 128,
56};
57
58const positive = (value: number | undefined, fallback: number): number =>
59 value === undefined || !Number.isFinite(value) || value < 0 ? fallback : value;
60
61export function resolvePredictOptions(
62 options?: PredictOptions | PredictionMode | boolean,
63): ResolvedPredictOptions {
64 if (options === undefined) return DEFAULT_PREDICT_OPTIONS;
65 if (typeof options === "boolean") {
66 return { ...DEFAULT_PREDICT_OPTIONS, mode: options ? "prompt" : "off" };
67 }
68 if (typeof options === "string") return { ...DEFAULT_PREDICT_OPTIONS, mode: options };
69 return {
70 mode: options.mode ?? DEFAULT_PREDICT_OPTIONS.mode,
71 minLatencyMs: positive(options.minLatencyMs, DEFAULT_PREDICT_OPTIONS.minLatencyMs),
72 timeoutMs: positive(options.timeoutMs, DEFAULT_PREDICT_OPTIONS.timeoutMs) || Infinity,
73 underline: options.underline ?? DEFAULT_PREDICT_OPTIONS.underline,
74 maxPredictions:
75 Math.floor(positive(options.maxPredictions, DEFAULT_PREDICT_OPTIONS.maxPredictions)) || 1,
76 };
77}
78
79/** Where a keystroke would land, as the renderer sees it at press time. */
80export interface PredictionSite {
81 /** Absolute screen row of the cursor (scrollback included). */
82 row: number;
83 /** Cursor column. */
84 col: number;
85 /** Terminal width, for the wrap refusal. */
86 cols: number;
87 /**
88 * Proof we are inside the shell's line-editing region: OSC 133/633 `B` has
89 * arrived and `C` has not. False for every uninstrumented shell and every
90 * full-screen application, which is precisely the point.
91 */
92 editing: boolean;
93}
94
95/** The emulator's real state, narrowed to what reconciliation needs. */
96export interface ReconcileFrame {
97 /** Absolute row -> the canonical per-column text the emulator now shows. */
98 rows: ReadonlyMap<number, readonly string[]>;
99 /** Absolute cursor position, or null when the cursor is hidden. */
100 cursor: { row: number; col: number } | null;
101 /** Still inside the line-editing region. */
102 editing: boolean;
103}
104
105/** One speculative single-column glyph. */
106interface Prediction {
107 row: number;
108 col: number;
109 text: string;
110 sentAt: number;
111}
112
113/** True only for characters we can place in exactly one column without re-segmenting. */
114export function isPredictableText(text: string): boolean {
115 if (text.length !== 1) return false;
116 const code = text.charCodeAt(0);
117 return code >= 0x20 && code <= 0x7e;
118}
119
120const BLANK = " ";
121
122/**
123 * One cell's glyph, with Ghostty's empty cell and a written space treated as
124 * the same thing. Without this, typing a space could never confirm — the core
125 * reports a blank cell as `""` whether or not a space was written into it — and
126 * every space would eventually retract the whole line.
127 */
128const glyph = (text: string): string => (text === "" ? BLANK : text);
129
130/** Smoothing factor from RFC 6298 / mosh: a new sample moves the estimate by an eighth. */
131const SRTT_ALPHA = 1 / 8;
132const MAX_RTT_SAMPLE_MS = 10_000;
133/** Never call a prediction wrong before the echo has had a plausible chance to arrive. */
134const MIN_GRACE_MS = 50;
135
136export class PredictionEngine {
137 private readonly options: ResolvedPredictOptions;
138 private list: Prediction[] = [];
139 private cursorNow: { row: number; col: number } | null = null;
140 private srtt: number | null = null;
141
142 constructor(options: ResolvedPredictOptions = DEFAULT_PREDICT_OPTIONS) {
143 this.options = options;
144 }
145
146 get enabled(): boolean {
147 return this.options.mode !== "off";
148 }
149
150 /** Smoothed round trip in milliseconds, or null before the first confirmation. */
151 get latencyMs(): number | null {
152 return this.srtt;
153 }
154
155 get underline(): boolean {
156 return this.options.underline;
157 }
158
159 /**
160 * Whether predictions should be painted at all. Deliberately false until a
161 * round trip has been measured: the first keystrokes of a session pay for the
162 * measurement, and on a fast link nothing is ever shown.
163 */
164 get displaying(): boolean {
165 if (!this.enabled) return false;
166 if (this.options.minLatencyMs <= 0) return true;
167 return this.srtt !== null && this.srtt >= this.options.minLatencyMs;
168 }
169
170 /** The speculative cursor position, or null when nothing is outstanding. */
171 get cursor(): { row: number; col: number } | null {
172 if (!this.displaying || this.list.length === 0 || this.cursorNow === null) return null;
173 return { ...this.cursorNow };
174 }
175
176 /** Columns to superimpose on `row`, or undefined when that row carries no overlay. */
177 overlayFor(row: number): ReadonlyMap<number, string> | undefined {
178 if (!this.displaying) return undefined;
179 let cells: Map<number, string> | undefined;
180 for (const prediction of this.list) {
181 if (prediction.row !== row) continue;
182 cells ??= new Map();
183 cells.set(prediction.col, prediction.text);
184 }
185 return cells;
186 }
187
188 /** Every row currently carrying an overlay. */
189 overlaidRows(): number[] {
190 if (!this.displaying) return [];
191 return [...new Set(this.list.map((prediction) => prediction.row))];
192 }
193
194 /** Record locally typed text. Returns the rows the renderer must repaint. */
195 type(text: string, site: PredictionSite, now: number): readonly number[] {
196 if (!this.enabled) return [];
197 const before = this.snapshot();
198 this.applyType(text, site, now);
199 return this.changedRows(before);
200 }
201
202 /** Record a backspace. Returns the rows the renderer must repaint. */
203 backspace(site: PredictionSite, now: number): readonly number[] {
204 if (!this.enabled) return [];
205 const before = this.snapshot();
206 this.applyBackspace(site, now);
207 return this.changedRows(before);
208 }
209
210 /**
211 * Any input we refuse to model — Enter, arrows, chords, paste, mouse. The
212 * outstanding speculation is dropped rather than left to rot: whatever the
213 * program does next, our glyphs are no longer a claim we can defend.
214 */
215 interrupt(): readonly number[] {
216 if (!this.enabled) return [];
217 const before = this.snapshot();
218 this.clear();
219 return this.changedRows(before);
220 }
221
222 /** Drop everything, including the latency estimate. For resize and disposal. */
223 reset(): readonly number[] {
224 const before = this.snapshot();
225 this.clear();
226 this.srtt = null;
227 return this.changedRows(before);
228 }
229
230 /**
231 * Reconcile against real emulator state. Confirmed predictions are retired
232 * (the row now genuinely shows them) and any contradiction drops the entire
233 * speculation, not just the offending glyph — a wrong prediction means our
234 * model of the far end was wrong, so every prediction built on it is suspect.
235 */
236 reconcile(frame: ReconcileFrame, now: number): readonly number[] {
237 if (!this.enabled || this.list.length === 0) return [];
238 const before = this.snapshot();
239 this.applyReconcile(frame, now);
240 return this.changedRows(before);
241 }
242
243 private applyType(text: string, site: PredictionSite, now: number): void {
244 if (!site.editing || !isPredictableText(text)) {
245 this.clear();
246 return;
247 }
248 const base = this.cursorNow ?? { row: site.row, col: site.col };
249 // A wrap changes row identity and can reflow; we cannot place a glyph past
250 // the last column without claiming to know how the core would wrap it.
251 if (base.col >= site.cols - 1 || base.col < 0) {
252 this.clear();
253 return;
254 }
255 if (this.list.length >= this.options.maxPredictions) {
256 this.clear();
257 return;
258 }
259 this.list.push({ row: base.row, col: base.col, text, sentAt: now });
260 this.cursorNow = { row: base.row, col: base.col + 1 };
261 }
262
263 private applyBackspace(site: PredictionSite, _now: number): void {
264 // We only ever un-type our own speculation. Backspacing over real content
265 // would be a claim about what the shell's line editor does with it, and at
266 // the left edge it is a claim about the previous row.
267 const cursor = this.cursorNow;
268 if (!site.editing || cursor === null || this.list.length === 0) {
269 this.clear();
270 return;
271 }
272 const last = this.list[this.list.length - 1]!;
273 if (last.row !== cursor.row || last.col !== cursor.col - 1) {
274 this.clear();
275 return;
276 }
277 this.list.pop();
278 this.cursorNow = { row: last.row, col: last.col };
279 if (this.list.length === 0) this.cursorNow = null;
280 }
281
282 private applyReconcile(frame: ReconcileFrame, now: number): void {
283 // Leaving the readline region invalidates the premise the predictions rest
284 // on, whatever the screen happens to show.
285 if (!frame.editing || frame.cursor === null) {
286 this.clear();
287 return;
288 }
289 const kept: Prediction[] = [];
290 for (const prediction of this.list) {
291 const cells = frame.rows.get(prediction.row);
292 const actual = glyph(cells?.[prediction.col] ?? "");
293 const expected = glyph(prediction.text);
294 if (cells !== undefined && actual === expected) {
295 // A blank column matching a predicted space is already visually true,
296 // but it is not evidence that a round trip completed, so it must not
297 // pull the latency estimate down.
298 if (actual !== BLANK) this.sample(now - prediction.sentAt);
299 continue;
300 }
301 if (now - prediction.sentAt >= this.options.timeoutMs) {
302 this.clear();
303 return;
304 }
305 if (cells !== undefined) {
306 // Some other glyph already occupies the column. The echo did not fail
307 // to arrive — it arrived as something else, and no amount of waiting
308 // makes our claim true again.
309 if (actual !== BLANK) {
310 this.clear();
311 return;
312 }
313 // Still blank past the point the echo should have landed.
314 if (now - prediction.sentAt >= this.graceMs()) {
315 this.clear();
316 return;
317 }
318 }
319 kept.push(prediction);
320 }
321 // A confirmation retires the oldest predictions first; anything still
322 // outstanding must remain a contiguous tail, or our chain has a hole in it.
323 if (kept.length > 0 && kept.length !== this.list.length) {
324 const head = this.list.length - kept.length;
325 if (this.list.slice(head).some((prediction, index) => prediction !== kept[index])) {
326 this.clear();
327 return;
328 }
329 }
330 // The real cursor must still be on the row we are predicting into. If it
331 // moved, the program did something we did not model.
332 if (kept.length > 0 && frame.cursor.row !== kept[0]!.row) {
333 this.clear();
334 return;
335 }
336 this.list = kept;
337 if (kept.length === 0) this.cursorNow = null;
338 }
339
340 /**
341 * How long an unconfirmed prediction stays innocent: about one round trip,
342 * floored so a fast link cannot retract an echo that is merely in flight.
343 * Before the first measurement the floor is all we have.
344 */
345 private graceMs(): number {
346 const estimate = this.srtt === null ? MIN_GRACE_MS : this.srtt * 2;
347 return Math.max(MIN_GRACE_MS, Math.min(estimate, this.options.timeoutMs));
348 }
349
350 private sample(rtt: number): void {
351 if (!Number.isFinite(rtt) || rtt < 0) return;
352 const bounded = Math.min(rtt, MAX_RTT_SAMPLE_MS);
353 this.srtt = this.srtt === null ? bounded : this.srtt + (bounded - this.srtt) * SRTT_ALPHA;
354 }
355
356 private clear(): void {
357 this.list = [];
358 this.cursorNow = null;
359 }
360
361 /** Overlay identity as a comparable string, for computing the repaint set. */
362 private snapshot(): Map<number, string> {
363 const rows = new Map<number, string>();
364 if (!this.displaying) return rows;
365 for (const prediction of this.list) {
366 rows.set(
367 prediction.row,
368 `${rows.get(prediction.row) ?? ""}|${prediction.col}:${prediction.text}`,
369 );
370 }
371 if (this.cursorNow !== null && this.list.length > 0) {
372 const row = this.cursorNow.row;
373 rows.set(row, `${rows.get(row) ?? ""}#${this.cursorNow.col}`);
374 }
375 return rows;
376 }
377
378 private changedRows(before: Map<number, string>): readonly number[] {
379 const after = this.snapshot();
380 const changed = new Set<number>();
381 for (const [row, value] of before) if (after.get(row) !== value) changed.add(row);
382 for (const [row, value] of after) if (before.get(row) !== value) changed.add(row);
383 return [...changed];
384 }
385}