Skip to main content

ftui_render/
render_certificate.rs

1//! Production render certificates (bd-6b9nr): explicit, named skip
2//! decisions for the diff stage — never opaque heuristics.
3//!
4//! The runtime's `TerminalWriter` builds a [`RenderCertificateInputs`] from
5//! facts it can prove locally each frame and asks
6//! [`evaluate_render_certificate`] for a decision. The certificate maps to a
7//! [`DiffSkipHint`] consumed by
8//! [`BufferDiff::compute_certified_into`](crate::diff::BufferDiff::compute_certified_into):
9//!
10//! - `FullRequired` — no previous frame, viewport change, or a due
11//!   full-redraw probe: a full-fidelity pass is mandatory;
12//! - `SkipAll` — zero dirty rows: the frame provably introduces no cell
13//!   changes relative to the tracked baseline, so the diff scan is skipped
14//!   entirely;
15//! - `NarrowToDirty` — the diff scan is narrowed to exactly the dirty rows
16//!   (soundness inherited from the buffer's dirty-tracking invariant:
17//!   dirty rows ⊇ changed rows, which in turn requires that the buffer's
18//!   dirty state was cleared while its content was identical to the diff's
19//!   `old` baseline — see `BufferDiff::compute_dirty`'s precondition; the
20//!   production writer guarantees this by diffing consecutive frames of one
21//!   buffer lineage).
22//!
23//! The decision tree is deliberately conservative and fail-open: any
24//! condition that cannot be proven falls back to `FullRequired`. Every
25//! certificate names its causes so evidence logs explain *why* work was
26//! skipped or performed (the mirror of this model used by the offline
27//! gauntlet lives in `ftui-harness::render_certificate`; this module is the
28//! production-side evaluator, kept in `ftui-render` because the harness is
29//! downstream of the runtime).
30
31use crate::buffer::Buffer;
32use crate::diff::DiffSkipHint;
33
34/// Facts the writer can prove about the frame before diffing.
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36pub struct RenderCertificateInputs {
37    /// A previous frame exists to diff against.
38    pub prev_available: bool,
39    /// The viewport dimensions changed since the previous frame.
40    pub dims_changed: bool,
41    /// A periodic full-redraw probe is due.
42    pub full_redraw_due: bool,
43    /// Rows marked dirty by the buffer's row-level tracking invariant.
44    pub dirty_row_count: usize,
45    /// Independent dirty-row count derived from per-row dirty spans.
46    pub span_dirty_rows: usize,
47    /// Whether the buffer's dirty baseline and internal dirty bitmap/spans are valid for `prev`.
48    pub baseline_valid: bool,
49    /// Total rows in the frame.
50    pub total_rows: u16,
51}
52
53impl RenderCertificateInputs {
54    /// Build certificate inputs by cross-checking `current`'s dirty state against `prev`.
55    #[must_use]
56    pub fn from_buffers(prev: Option<&Buffer>, current: &Buffer, full_redraw_due: bool) -> Self {
57        let prev_available = prev.is_some();
58        let dims_changed =
59            prev.is_some_and(|p| p.width() != current.width() || p.height() != current.height());
60        let dirty_row_count = current.dirty_row_count();
61        let span_dirty_rows = current.dirty_span_row_count();
62        let baseline_valid = match prev {
63            Some(p) if !dims_changed => current.is_dirty_witness_valid_for(p),
64            _ => false,
65        };
66        Self {
67            prev_available,
68            dims_changed,
69            full_redraw_due,
70            dirty_row_count,
71            span_dirty_rows,
72            baseline_valid,
73            total_rows: current.height(),
74        }
75    }
76}
77
78/// The certified level of work elimination.
79#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
80pub enum RenderCertificateLevel {
81    /// Full-fidelity work is required; nothing may be skipped.
82    FullRequired,
83    /// The diff scan is skipped entirely (no dirty rows).
84    SkipAll,
85    /// The diff scan is narrowed to the dirty rows only.
86    NarrowToDirty,
87}
88
89impl RenderCertificateLevel {
90    /// Stable lowercase tag for evidence logs.
91    #[must_use]
92    pub const fn label(&self) -> &'static str {
93        match self {
94            Self::FullRequired => "full-required",
95            Self::SkipAll => "skip-all",
96            Self::NarrowToDirty => "narrow-to-dirty",
97        }
98    }
99}
100
101/// An explicit, explainable skip decision for one frame.
102#[derive(Debug, Clone, PartialEq, Eq)]
103pub struct RenderCertificate {
104    /// The certified level.
105    pub level: RenderCertificateLevel,
106    /// Named causes behind the decision (never empty).
107    pub causes: Vec<&'static str>,
108    /// Rows the certificate narrows to (empty unless `NarrowToDirty`).
109    pub dirty_rows: Vec<u16>,
110    /// Whether the evaluator fell back to full work out of caution.
111    pub fell_back: bool,
112}
113
114impl RenderCertificate {
115    /// Translate the certificate into the diff-stage hint.
116    #[must_use]
117    pub fn to_hint(&self) -> DiffSkipHint {
118        match self.level {
119            RenderCertificateLevel::FullRequired => DiffSkipHint::FullDiff,
120            RenderCertificateLevel::SkipAll => DiffSkipHint::SkipDiff,
121            RenderCertificateLevel::NarrowToDirty => {
122                DiffSkipHint::NarrowToRows(self.dirty_rows.clone())
123            }
124        }
125    }
126
127    /// Consume the certificate into the diff-stage hint without cloning `dirty_rows`.
128    #[must_use]
129    pub fn into_hint(self) -> DiffSkipHint {
130        match self.level {
131            RenderCertificateLevel::FullRequired => DiffSkipHint::FullDiff,
132            RenderCertificateLevel::SkipAll => DiffSkipHint::SkipDiff,
133            RenderCertificateLevel::NarrowToDirty => DiffSkipHint::NarrowToRows(self.dirty_rows),
134        }
135    }
136
137    /// Compact JSON fragment for evidence lines (stable field order).
138    #[must_use]
139    pub fn to_evidence_json(&self) -> String {
140        format!(
141            r#"{{"level":"{}","causes":[{}],"narrowed_rows":{},"fell_back":{}}}"#,
142            self.level.label(),
143            self.causes
144                .iter()
145                .map(|c| format!("\"{c}\""))
146                .collect::<Vec<_>>()
147                .join(","),
148            self.dirty_rows.len(),
149            self.fell_back
150        )
151    }
152}
153
154/// Evaluate the conservative production decision tree.
155///
156/// `dirty_rows` must be the buffer's dirty row indices in strictly ascending order;
157/// it is cross-checked against `inputs.dirty_row_count`, `inputs.span_dirty_rows`,
158/// and `inputs.baseline_valid`. Any disagreement falls back to `FullRequired`.
159#[must_use]
160pub fn evaluate_render_certificate(
161    inputs: &RenderCertificateInputs,
162    dirty_rows: Vec<u16>,
163) -> RenderCertificate {
164    if !inputs.prev_available {
165        return RenderCertificate {
166            level: RenderCertificateLevel::FullRequired,
167            causes: vec!["no-previous-frame"],
168            dirty_rows: Vec::new(),
169            fell_back: true,
170        };
171    }
172    if inputs.dims_changed {
173        return RenderCertificate {
174            level: RenderCertificateLevel::FullRequired,
175            causes: vec!["viewport-changed"],
176            dirty_rows: Vec::new(),
177            fell_back: true,
178        };
179    }
180    if inputs.full_redraw_due {
181        return RenderCertificate {
182            level: RenderCertificateLevel::FullRequired,
183            causes: vec!["full-redraw-probe-due"],
184            dirty_rows: Vec::new(),
185            fell_back: true,
186        };
187    }
188    // Cross-check the row witness against independent span/bitmap/baseline
189    // facts BEFORE certifying a skip or narrow scan.
190    let rows_sorted_unique = dirty_rows.windows(2).all(|pair| pair[0] < pair[1]);
191    let rows_in_bounds = dirty_rows.iter().all(|&row| row < inputs.total_rows);
192    if !inputs.baseline_valid
193        || inputs.span_dirty_rows != inputs.dirty_row_count
194        || dirty_rows.len() != inputs.dirty_row_count
195        || !rows_sorted_unique
196        || !rows_in_bounds
197    {
198        return RenderCertificate {
199            level: RenderCertificateLevel::FullRequired,
200            causes: vec!["dirty-row-witness-inconsistent"],
201            dirty_rows: Vec::new(),
202            fell_back: true,
203        };
204    }
205    if inputs.dirty_row_count == 0 {
206        return RenderCertificate {
207            level: RenderCertificateLevel::SkipAll,
208            causes: vec!["zero-dirty-rows"],
209            dirty_rows: Vec::new(),
210            fell_back: false,
211        };
212    }
213    RenderCertificate {
214        level: RenderCertificateLevel::NarrowToDirty,
215        causes: vec!["dirty-rows-witnessed"],
216        dirty_rows,
217        fell_back: false,
218    }
219}
220
221/// Evaluate a render certificate directly for a `(prev, current)` buffer pair.
222#[must_use]
223pub fn evaluate_render_certificate_for_buffers(
224    prev: Option<&Buffer>,
225    current: &Buffer,
226    full_redraw_due: bool,
227) -> RenderCertificate {
228    let Some(prev_buf) = prev else {
229        return RenderCertificate {
230            level: RenderCertificateLevel::FullRequired,
231            causes: vec!["no-previous-frame"],
232            dirty_rows: Vec::new(),
233            fell_back: true,
234        };
235    };
236    if prev_buf.width() != current.width() || prev_buf.height() != current.height() {
237        return RenderCertificate {
238            level: RenderCertificateLevel::FullRequired,
239            causes: vec!["viewport-changed"],
240            dirty_rows: Vec::new(),
241            fell_back: true,
242        };
243    };
244    if full_redraw_due {
245        return RenderCertificate {
246            level: RenderCertificateLevel::FullRequired,
247            causes: vec!["full-redraw-probe-due"],
248            dirty_rows: Vec::new(),
249            fell_back: true,
250        };
251    }
252    let (dirty_row_count, span_dirty_rows, baseline_valid, dirty_rows) =
253        current.collect_dirty_witness_for(prev_buf);
254    if !baseline_valid || span_dirty_rows != dirty_row_count {
255        return RenderCertificate {
256            level: RenderCertificateLevel::FullRequired,
257            causes: vec!["dirty-row-witness-inconsistent"],
258            dirty_rows: Vec::new(),
259            fell_back: true,
260        };
261    }
262    if dirty_row_count == 0 {
263        return RenderCertificate {
264            level: RenderCertificateLevel::SkipAll,
265            causes: vec!["zero-dirty-rows"],
266            dirty_rows: Vec::new(),
267            fell_back: false,
268        };
269    }
270    RenderCertificate {
271        level: RenderCertificateLevel::NarrowToDirty,
272        causes: vec!["dirty-rows-witnessed"],
273        dirty_rows,
274        fell_back: false,
275    }
276}
277
278#[cfg(test)]
279mod tests {
280    use super::*;
281    use crate::buffer::Buffer;
282    use crate::cell::Cell;
283    use crate::diff::BufferDiff;
284
285    fn inputs(dirty: usize, rows: u16) -> RenderCertificateInputs {
286        RenderCertificateInputs {
287            prev_available: true,
288            dims_changed: false,
289            full_redraw_due: false,
290            dirty_row_count: dirty,
291            span_dirty_rows: dirty,
292            baseline_valid: true,
293            total_rows: rows,
294        }
295    }
296
297    #[test]
298    fn unprovable_conditions_force_full_work() {
299        let mut no_prev = inputs(3, 10);
300        no_prev.prev_available = false;
301        let cert = evaluate_render_certificate(&no_prev, vec![1, 2, 3]);
302        assert_eq!(cert.level, RenderCertificateLevel::FullRequired);
303        assert!(cert.fell_back);
304        assert_eq!(cert.causes, vec!["no-previous-frame"]);
305
306        let mut resized = inputs(3, 10);
307        resized.dims_changed = true;
308        let cert = evaluate_render_certificate(&resized, vec![1, 2, 3]);
309        assert_eq!(cert.causes, vec!["viewport-changed"]);
310
311        let mut probe = inputs(3, 10);
312        probe.full_redraw_due = true;
313        let cert = evaluate_render_certificate(&probe, vec![1, 2, 3]);
314        assert_eq!(cert.causes, vec!["full-redraw-probe-due"]);
315    }
316
317    #[test]
318    fn zero_dirty_rows_certifies_a_skip() {
319        let cert = evaluate_render_certificate(&inputs(0, 10), Vec::new());
320        assert_eq!(cert.level, RenderCertificateLevel::SkipAll);
321        assert!(!cert.fell_back);
322        assert!(matches!(cert.to_hint(), DiffSkipHint::SkipDiff));
323    }
324
325    #[test]
326    fn dirty_rows_certify_a_narrow_scan() {
327        let cert = evaluate_render_certificate(&inputs(2, 10), vec![3, 7]);
328        assert_eq!(cert.level, RenderCertificateLevel::NarrowToDirty);
329        match cert.to_hint() {
330            DiffSkipHint::NarrowToRows(rows) => assert_eq!(rows, vec![3, 7]),
331            other => panic!("expected narrow hint, got {other:?}"),
332        }
333    }
334
335    #[test]
336    fn inconsistent_witness_falls_back_to_full() {
337        // Count mismatch.
338        let cert = evaluate_render_certificate(&inputs(2, 10), vec![3]);
339        assert_eq!(cert.level, RenderCertificateLevel::FullRequired);
340        assert!(cert.fell_back);
341        // Out-of-bounds row.
342        let cert = evaluate_render_certificate(&inputs(1, 10), vec![10]);
343        assert_eq!(cert.level, RenderCertificateLevel::FullRequired);
344        assert_eq!(cert.causes, vec!["dirty-row-witness-inconsistent"]);
345        // Unsorted / duplicate rows.
346        let cert = evaluate_render_certificate(&inputs(2, 10), vec![5, 2]);
347        assert_eq!(cert.level, RenderCertificateLevel::FullRequired);
348        assert_eq!(cert.causes, vec!["dirty-row-witness-inconsistent"]);
349        let cert = evaluate_render_certificate(&inputs(2, 10), vec![3, 3]);
350        assert_eq!(cert.level, RenderCertificateLevel::FullRequired);
351        // Span-vs-row count disagreement.
352        let mut desync = inputs(2, 10);
353        desync.span_dirty_rows = 1;
354        let cert = evaluate_render_certificate(&desync, vec![3, 7]);
355        assert_eq!(cert.level, RenderCertificateLevel::FullRequired);
356        assert_eq!(cert.causes, vec!["dirty-row-witness-inconsistent"]);
357        // Invalid baseline even when dirty_row_count == 0.
358        let mut stale_zero = inputs(0, 10);
359        stale_zero.baseline_valid = false;
360        let cert = evaluate_render_certificate(&stale_zero, Vec::new());
361        assert_eq!(cert.level, RenderCertificateLevel::FullRequired);
362        assert!(cert.fell_back);
363        assert_eq!(cert.causes, vec!["dirty-row-witness-inconsistent"]);
364    }
365
366    #[test]
367    fn stale_dirty_bits_on_buffer_pair_fall_back_and_find_all_changes() {
368        let mut old = Buffer::new(16, 6);
369        old.set(2, 1, Cell::from_char('A'));
370        old.clear_dirty();
371
372        let mut new = old.clone();
373        new.clear_dirty();
374        // Mutate row 3, then wipe dirty state so row 3 is stale-clean!
375        new.set(7, 3, Cell::from_char('X'));
376        new.clear_dirty();
377        // Mutate row 5 so only row 5 appears dirty in `new.dirty_row_indices()`.
378        new.set(1, 5, Cell::from_char('Y'));
379
380        let cert = evaluate_render_certificate_for_buffers(Some(&old), &new, false);
381        assert_eq!(cert.level, RenderCertificateLevel::FullRequired);
382        assert!(cert.fell_back);
383        assert_eq!(cert.causes, vec!["dirty-row-witness-inconsistent"]);
384
385        let mut certified = BufferDiff::new();
386        certified.compute_certified_into(&old, &new, cert.to_hint());
387        let mut full = BufferDiff::new();
388        full.compute_into(&old, &new);
389        assert_eq!(certified.changes(), full.changes());
390        assert_eq!(certified.changes(), &[(7, 3), (1, 5)]);
391    }
392
393    #[test]
394    fn evidence_json_is_stable_and_named() {
395        let cert = evaluate_render_certificate(&inputs(2, 10), vec![3, 7]);
396        let json = cert.to_evidence_json();
397        assert_eq!(
398            json,
399            r#"{"level":"narrow-to-dirty","causes":["dirty-rows-witnessed"],"narrowed_rows":2,"fell_back":false}"#
400        );
401    }
402
403    /// The certified path must produce exactly the change set of the
404    /// uncertified dirty path across generated frames (behavior
405    /// preservation, deterministic xorshift corpus).
406    #[test]
407    fn certified_changes_equal_dirty_changes_across_generated_frames() {
408        let (w, h) = (24u16, 8u16);
409        let mut seed = 0x9E37_79B9_7F4A_7C15u64;
410        let mut next = move || {
411            seed ^= seed << 13;
412            seed ^= seed >> 7;
413            seed ^= seed << 17;
414            seed
415        };
416
417        for round in 0..50 {
418            let old = Buffer::new(w, h);
419            let mut new = Buffer::new(w, h);
420            new.clear_dirty();
421
422            let mutations = (next() % 20) as usize;
423            for _ in 0..mutations {
424                let x = (next() % u64::from(w)) as u16;
425                let y = (next() % u64::from(h)) as u16;
426                let ch = char::from(b'A' + (next() % 26) as u8);
427                new.set(x, y, Cell::from_char(ch));
428            }
429
430            let cert = evaluate_render_certificate_for_buffers(Some(&old), &new, false);
431            assert!(!cert.fell_back, "round {round}: unexpected fallback");
432
433            let mut certified = BufferDiff::new();
434            certified.compute_certified_into(&old, &new, cert.to_hint());
435            let mut truth = BufferDiff::new();
436            truth.compute_dirty_into(&old, &new);
437            assert_eq!(
438                certified.changes(),
439                truth.changes(),
440                "round {round}: certified path diverged ({} mutations)",
441                mutations
442            );
443        }
444    }
445}