Skip to main content

ftui_render/
diff.rs

1#![forbid(unsafe_code)]
2
3//! Diff computation between buffers.
4//!
5//! The `BufferDiff` computes the minimal set of changed cells between two
6//! buffers using a row-major scan for optimal cache efficiency.
7//!
8//! # Algorithm
9//!
10//! Row-major scan for cache efficiency:
11//! 1. Iterate y from 0 to height
12//! 2. Fast-path skip rows where the full slice is equal
13//! 3. For changed rows, scan in coarse blocks and skip unchanged blocks
14//! 4. Within dirty blocks, compare cells using `bits_eq`
15//!
16//! This ensures sequential memory access since cells are stored row-by-row.
17//! With 4 cells per cache line, the prefetcher can anticipate next access.
18//!
19//! # Usage
20//!
21//! ```
22//! use ftui_render::buffer::Buffer;
23//! use ftui_render::cell::Cell;
24//! use ftui_render::diff::BufferDiff;
25//!
26//! let mut old = Buffer::new(80, 24);
27//! let mut new = Buffer::new(80, 24);
28//!
29//! // Make some changes
30//! new.set_raw(5, 5, Cell::from_char('X'));
31//! new.set_raw(6, 5, Cell::from_char('Y'));
32//!
33//! let diff = BufferDiff::compute(&old, &new);
34//! assert_eq!(diff.len(), 2);
35//!
36//! // Coalesce into runs for efficient emission
37//! let runs = diff.runs();
38//! assert_eq!(runs.len(), 1); // Adjacent cells form one run
39//! ```
40
41use crate::buffer::{Buffer, DirtySpan};
42use crate::cell::Cell;
43
44// =============================================================================
45// Certificate-Based Skip Hints
46// =============================================================================
47
48/// Hint from a render certificate evaluator about what diff work can be skipped.
49///
50/// The runtime evaluates a certificate (e.g., from `render_certificate::CertificateEvaluator`)
51/// and translates the result into a `DiffSkipHint` that `BufferDiff::compute_certified_into`
52/// can act on.
53///
54/// # Safety contract
55///
56/// The hint must be correct: `SkipDiff` must only be issued when the caller
57/// can guarantee that old and new buffers are byte-identical. `NarrowToRows`
58/// must include all rows that actually changed. Incorrect hints produce stale
59/// frames — the diff engine trusts the hint without verification.
60#[derive(Debug, Clone, PartialEq, Eq)]
61pub enum DiffSkipHint {
62    /// No skip — perform standard dirty-diff computation.
63    FullDiff,
64    /// Skip diff entirely — buffers are guaranteed identical.
65    SkipDiff,
66    /// Only diff the specified rows — all other rows are guaranteed clean.
67    NarrowToRows(Vec<u16>),
68}
69
70impl DiffSkipHint {
71    /// Whether this hint skips any work.
72    #[must_use]
73    pub fn skips_work(&self) -> bool {
74        !matches!(self, Self::FullDiff)
75    }
76
77    /// Human-readable label for evidence logging.
78    #[must_use]
79    pub fn label(&self) -> &'static str {
80        match self {
81            Self::FullDiff => "full-diff",
82            Self::SkipDiff => "skip-diff",
83            Self::NarrowToRows(_) => "narrow-to-rows",
84        }
85    }
86}
87
88// =============================================================================
89// Block-based Row Scanning (autovec-friendly)
90// =============================================================================
91
92/// Block size for vectorized comparison (4 cells = 64 bytes).
93/// Chosen to match common SIMD register width (256-bit / 512-bit)
94/// and a single 64-byte cache line.
95const BLOCK_SIZE: usize = 4;
96
97// Compile-time: 4 cells must equal exactly one 64-byte cache line.
98const _: () = assert!(
99    core::mem::size_of::<Cell>() * BLOCK_SIZE == 64,
100    "BLOCK_SIZE * Cell must equal 64-byte cache line"
101);
102
103// Compile-time: Cell alignment must be at least 16 bytes so that
104// Vec<Cell> allocations are 16-byte aligned (SSE-friendly).
105const _: () = assert!(
106    core::mem::align_of::<Cell>() >= 16,
107    "Cell alignment must be >= 16 for SIMD access"
108);
109
110/// Row block size for coarse blockwise skip (32 cells = 512 bytes).
111/// This lets us skip large unchanged regions in sparse rows while
112/// preserving row-major iteration order.
113const ROW_BLOCK_SIZE: usize = 32;
114
115/// Cache-line-aligned block of 4 cells (64 bytes).
116///
117/// This type documents the alignment contract: each `BLOCK_SIZE` group
118/// of cells should ideally start on a 64-byte boundary for optimal
119/// SIMD and cache performance.
120#[repr(C, align(64))]
121#[allow(dead_code)]
122struct CacheLineBlock {
123    cells: [Cell; BLOCK_SIZE],
124}
125
126// Compile-time: CacheLineBlock must be exactly 64 bytes.
127const _: () = assert!(
128    core::mem::size_of::<CacheLineBlock>() == 64,
129    "CacheLineBlock must be exactly 64 bytes"
130);
131
132#[cfg(test)]
133fn span_diagnostics(buf: &Buffer) -> String {
134    let stats = buf.dirty_span_stats();
135    if !buf.dirty_span_config().enabled {
136        return format!("dirty spans disabled; stats={stats:?}");
137    }
138    let mut rows = Vec::new();
139    for y in 0..buf.height() {
140        let Some(row) = buf.dirty_span_row(y) else {
141            continue;
142        };
143        if row.is_full() {
144            rows.push(format!("{y}:full"));
145            continue;
146        }
147        if row.spans().is_empty() {
148            continue;
149        }
150        let spans = row
151            .spans()
152            .iter()
153            .map(|span| format!("[{}, {})", span.x0, span.x1))
154            .collect::<Vec<_>>()
155            .join(",");
156        rows.push(format!("{y}:{spans}"));
157    }
158    format!("stats={stats:?} rows=[{}]", rows.join(" | "))
159}
160
161/// Scan a row slice for changed cells, appending positions to `changes`.
162///
163/// `x_offset` is added to each recorded x coordinate.
164///
165/// `#[inline(always)]` forces inlining into the blockwise caller so LLVM can
166/// see the full loop and apply auto-vectorization across the 4-cell block.
167#[inline(always)]
168fn scan_row_changes_range(
169    old_row: &[Cell],
170    new_row: &[Cell],
171    y: u16,
172    x_offset: u16,
173    changes: &mut Vec<(u16, u16)>,
174) {
175    debug_assert_eq!(old_row.len(), new_row.len());
176    let len = old_row.len();
177    let blocks = len / BLOCK_SIZE;
178    let remainder = len % BLOCK_SIZE;
179
180    // Process full blocks
181    for block_idx in 0..blocks {
182        let base = block_idx * BLOCK_SIZE;
183        let base_x = x_offset + base as u16;
184        if cell_quad_bits_eq(old_row, new_row, base) {
185            continue;
186        }
187
188        // Compare each cell and push changes directly.
189        // We use a constant loop which the compiler will unroll.
190        for i in 0..BLOCK_SIZE {
191            if !old_row[base + i].bits_eq(&new_row[base + i]) {
192                changes.push((base_x + i as u16, y));
193            }
194        }
195    }
196
197    // Process remainder cells
198    let rem_base = blocks * BLOCK_SIZE;
199    let rem_base_x = x_offset + rem_base as u16;
200    for i in 0..remainder {
201        if !old_row[rem_base + i].bits_eq(&new_row[rem_base + i]) {
202            changes.push((rem_base_x + i as u16, y));
203        }
204    }
205}
206
207#[inline(always)]
208fn cell_quad_bits_eq(old_row: &[Cell], new_row: &[Cell], base: usize) -> bool {
209    old_row[base].bits_eq(&new_row[base])
210        & old_row[base + 1].bits_eq(&new_row[base + 1])
211        & old_row[base + 2].bits_eq(&new_row[base + 2])
212        & old_row[base + 3].bits_eq(&new_row[base + 3])
213}
214
215/// Scan a row pair for changed cells, appending positions to `changes`.
216///
217/// Uses coarse block skipping to avoid full per-cell scans in sparse rows,
218/// then falls back to fine-grained scanning inside dirty blocks.
219#[inline]
220fn scan_row_changes(old_row: &[Cell], new_row: &[Cell], y: u16, changes: &mut Vec<(u16, u16)>) {
221    scan_row_changes_blockwise(old_row, new_row, y, changes);
222}
223
224/// Scan a row in coarse blocks, skipping unchanged blocks, and falling back
225/// to fine-grained scan for blocks that differ.
226#[inline]
227fn scan_row_changes_blockwise(
228    old_row: &[Cell],
229    new_row: &[Cell],
230    y: u16,
231    changes: &mut Vec<(u16, u16)>,
232) {
233    debug_assert_eq!(old_row.len(), new_row.len());
234    let len = old_row.len();
235    let blocks = len / ROW_BLOCK_SIZE;
236    let remainder = len % ROW_BLOCK_SIZE;
237
238    for block_idx in 0..blocks {
239        let base = block_idx * ROW_BLOCK_SIZE;
240        let old_block = &old_row[base..base + ROW_BLOCK_SIZE];
241        let new_block = &new_row[base..base + ROW_BLOCK_SIZE];
242        scan_row_changes_range(old_block, new_block, y, base as u16, changes);
243    }
244
245    if remainder > 0 {
246        let base = blocks * ROW_BLOCK_SIZE;
247        let old_block = &old_row[base..base + remainder];
248        let new_block = &new_row[base..base + remainder];
249        scan_row_changes_range(old_block, new_block, y, base as u16, changes);
250    }
251}
252
253/// Scan only dirty spans within a row, preserving row-major ordering.
254#[inline]
255fn scan_row_changes_spans(
256    old_row: &[Cell],
257    new_row: &[Cell],
258    y: u16,
259    spans: &[DirtySpan],
260    changes: &mut Vec<(u16, u16)>,
261) {
262    for span in spans {
263        let start = span.x0 as usize;
264        let end = span.x1 as usize;
265        if start >= end || start >= old_row.len() {
266            continue;
267        }
268        let end = end.min(old_row.len());
269        let old_slice = &old_row[start..end];
270        let new_slice = &new_row[start..end];
271        if old_slice == new_slice {
272            continue;
273        }
274        scan_row_changes_range(old_slice, new_slice, y, span.x0, changes);
275    }
276}
277
278#[inline]
279fn scan_row_changes_range_if_needed(
280    old_row: &[Cell],
281    new_row: &[Cell],
282    y: u16,
283    start: usize,
284    end: usize,
285    changes: &mut Vec<(u16, u16)>,
286) {
287    if start >= end || start >= old_row.len() {
288        return;
289    }
290    let end = end.min(old_row.len());
291    let old_slice = &old_row[start..end];
292    let new_slice = &new_row[start..end];
293    if old_slice == new_slice {
294        return;
295    }
296    scan_row_changes_range(old_slice, new_slice, y, start as u16, changes);
297}
298
299#[inline]
300#[allow(clippy::too_many_arguments)]
301fn scan_row_tiles(
302    old_row: &[Cell],
303    new_row: &[Cell],
304    y: u16,
305    width: usize,
306    tile_w: usize,
307    tiles_x: usize,
308    tile_row_base: usize,
309    dirty_tiles: &[bool],
310    changes: &mut Vec<(u16, u16)>,
311) {
312    for tile_x in 0..tiles_x {
313        let tile_idx = tile_row_base + tile_x;
314        if !dirty_tiles[tile_idx] {
315            continue;
316        }
317        let start = tile_x * tile_w;
318        let end = ((tile_x + 1) * tile_w).min(width);
319        scan_row_changes_range_if_needed(old_row, new_row, y, start, end, changes);
320    }
321}
322
323#[inline]
324#[allow(clippy::too_many_arguments)]
325fn scan_row_tiles_spans(
326    old_row: &[Cell],
327    new_row: &[Cell],
328    y: u16,
329    width: usize,
330    tile_w: usize,
331    tiles_x: usize,
332    tile_row_base: usize,
333    dirty_tiles: &[bool],
334    spans: &[DirtySpan],
335    changes: &mut Vec<(u16, u16)>,
336) {
337    if spans.is_empty() {
338        return;
339    }
340    let max_x = width.saturating_sub(1);
341    for span in spans {
342        let span_start = span.x0 as usize;
343        let span_end_exclusive = span.x1 as usize;
344        if span_start >= span_end_exclusive || span_start > max_x {
345            continue;
346        }
347        let span_end = span_end_exclusive.saturating_sub(1).min(max_x);
348        let tile_x_start = span_start / tile_w;
349        let tile_x_end = span_end / tile_w;
350        for tile_x in tile_x_start..=tile_x_end {
351            if tile_x >= tiles_x {
352                break;
353            }
354            let tile_idx = tile_row_base + tile_x;
355            if !dirty_tiles[tile_idx] {
356                continue;
357            }
358            let tile_start = tile_x * tile_w;
359            let tile_end = ((tile_x + 1) * tile_w).min(width);
360            let seg_start = span_start.max(tile_start);
361            let seg_end = span_end.min(tile_end.saturating_sub(1));
362            if seg_start > seg_end {
363                continue;
364            }
365            scan_row_changes_range_if_needed(old_row, new_row, y, seg_start, seg_end + 1, changes);
366        }
367    }
368}
369
370// =============================================================================
371// Tile-based Skip (Summed-Area Table)
372// =============================================================================
373
374const TILE_SIZE_MIN: u16 = 8;
375const TILE_SIZE_MAX: u16 = 64;
376
377#[inline]
378fn clamp_tile_size(value: u16) -> u16 {
379    value.clamp(TILE_SIZE_MIN, TILE_SIZE_MAX)
380}
381
382#[inline]
383fn div_ceil_usize(n: usize, d: usize) -> usize {
384    debug_assert!(d > 0);
385    n.div_ceil(d)
386}
387
388#[inline]
389fn accumulate_tile_counts_range(
390    tile_counts: &mut [u32],
391    dirty_row_bits: &[u8],
392    tile_row_base: usize,
393    tiles_x: usize,
394    tile_w: usize,
395    range: core::ops::Range<usize>,
396    scanned_cells: &mut usize,
397) -> Result<(), ()> {
398    let start = range.start;
399    let end = range.end;
400    if start >= end || start >= dirty_row_bits.len() {
401        return Ok(());
402    }
403
404    let end = end.min(dirty_row_bits.len());
405    *scanned_cells = scanned_cells.saturating_add(end.saturating_sub(start));
406
407    let tile_x_start = start / tile_w;
408    let tile_x_end = (end - 1) / tile_w;
409    for tile_x in tile_x_start..=tile_x_end {
410        if tile_x >= tiles_x {
411            break;
412        }
413
414        let seg_start = start.max(tile_x * tile_w);
415        let seg_end = end.min((tile_x + 1) * tile_w);
416        let count = dirty_row_bits[seg_start..seg_end]
417            .iter()
418            .filter(|&&bit| bit != 0)
419            .count();
420        if count == 0 {
421            continue;
422        }
423
424        let tile_idx = tile_row_base + tile_x;
425        match tile_counts[tile_idx].checked_add(count as u32) {
426            Some(value) => tile_counts[tile_idx] = value,
427            None => return Err(()),
428        }
429    }
430
431    Ok(())
432}
433
434/// Configuration for tile-based diff skipping.
435///
436/// Uses a summed-area table (SAT) to perform constant-time tile row and
437/// rectangle dirty-density queries, skipping clean tile rows wholesale.
438/// Performance measurements and ablation results are recorded in
439/// `docs/perf/sat_tile_skip_2026-09.md`.
440#[derive(Debug, Clone)]
441pub struct TileDiffConfig {
442    /// Whether tile-based skipping is enabled.
443    pub enabled: bool,
444    /// Tile width in cells (clamped to [8, 64]).
445    pub tile_w: u16,
446    /// Tile height in cells (clamped to [8, 64]).
447    pub tile_h: u16,
448    /// Skip scanning clean rows when building tile counts.
449    ///
450    /// When true, the tile build only scans rows marked dirty, reducing
451    /// build cost for sparse updates. Disable to force full-row scans.
452    pub skip_clean_rows: bool,
453    /// Minimum total cells required before enabling tiles (default: 12,000, i.e. 200x60).
454    ///
455    /// Smaller viewports (e.g. 80x24 = 1,920 cells) fall back to direct row diffs
456    /// because SAT construction overhead exceeds tile skip savings below this threshold
457    /// (see `docs/perf/sat_tile_skip_2026-09.md`).
458    pub min_cells_for_tiles: usize,
459    /// Dense cell ratio threshold for falling back to non-tile diff.
460    pub dense_cell_ratio: f64,
461    /// Dense tile ratio threshold for falling back to non-tile diff.
462    pub dense_tile_ratio: f64,
463    /// Maximum number of tiles allowed (SAT build budget; fallback if exceeded).
464    pub max_tiles: usize,
465}
466
467impl Default for TileDiffConfig {
468    fn default() -> Self {
469        Self {
470            enabled: true,
471            tile_w: 16,
472            tile_h: 8,
473            skip_clean_rows: true,
474            min_cells_for_tiles: 12_000,
475            dense_cell_ratio: 0.25,
476            dense_tile_ratio: 0.60,
477            max_tiles: 4096,
478        }
479    }
480}
481
482impl TileDiffConfig {
483    /// Toggle tile-based skipping.
484    #[must_use]
485    pub fn with_enabled(mut self, enabled: bool) -> Self {
486        self.enabled = enabled;
487        self
488    }
489
490    /// Set tile size in cells (clamped during build).
491    #[must_use]
492    pub fn with_tile_size(mut self, tile_w: u16, tile_h: u16) -> Self {
493        self.tile_w = tile_w;
494        self.tile_h = tile_h;
495        self
496    }
497
498    /// Set minimum cell count required before tiles are considered.
499    #[must_use]
500    pub fn with_min_cells_for_tiles(mut self, min_cells: usize) -> Self {
501        self.min_cells_for_tiles = min_cells;
502        self
503    }
504
505    /// Toggle skipping clean rows during tile build.
506    #[must_use]
507    pub fn with_skip_clean_rows(mut self, skip: bool) -> Self {
508        self.skip_clean_rows = skip;
509        self
510    }
511
512    /// Set dense cell ratio threshold for falling back to non-tile diff.
513    #[must_use]
514    pub fn with_dense_cell_ratio(mut self, ratio: f64) -> Self {
515        self.dense_cell_ratio = ratio;
516        self
517    }
518
519    /// Set dense tile ratio threshold for falling back to non-tile diff.
520    #[must_use]
521    pub fn with_dense_tile_ratio(mut self, ratio: f64) -> Self {
522        self.dense_tile_ratio = ratio;
523        self
524    }
525
526    /// Set SAT build budget via maximum tiles allowed.
527    #[must_use]
528    pub fn with_max_tiles(mut self, max_tiles: usize) -> Self {
529        self.max_tiles = max_tiles;
530        self
531    }
532}
533
534/// Reason the tile path fell back to a non-tile diff.
535#[derive(Debug, Clone, Copy, PartialEq, Eq)]
536pub enum TileDiffFallback {
537    Disabled,
538    SmallScreen,
539    DirtyAll,
540    DenseCells,
541    DenseTiles,
542    TooManyTiles,
543    Overflow,
544}
545
546impl TileDiffFallback {
547    pub const fn as_str(self) -> &'static str {
548        match self {
549            Self::Disabled => "disabled",
550            Self::SmallScreen => "small_screen",
551            Self::DirtyAll => "dirty_all",
552            Self::DenseCells => "dense_cells",
553            Self::DenseTiles => "dense_tiles",
554            Self::TooManyTiles => "too_many_tiles",
555            Self::Overflow => "overflow",
556        }
557    }
558}
559
560/// Tile parameters derived from the current buffer dimensions.
561#[derive(Debug, Clone, Copy)]
562pub struct TileParams {
563    pub width: u16,
564    pub height: u16,
565    pub tile_w: u16,
566    pub tile_h: u16,
567    pub tiles_x: usize,
568    pub tiles_y: usize,
569}
570
571impl TileParams {
572    #[inline]
573    pub fn total_tiles(self) -> usize {
574        self.tiles_x * self.tiles_y
575    }
576
577    #[inline]
578    pub fn total_cells(self) -> usize {
579        self.width as usize * self.height as usize
580    }
581}
582
583/// Summary statistics from building a tile SAT.
584#[derive(Debug, Clone, Copy)]
585pub struct TileDiffStats {
586    pub width: u16,
587    pub height: u16,
588    pub tile_w: u16,
589    pub tile_h: u16,
590    pub tiles_x: usize,
591    pub tiles_y: usize,
592    pub total_tiles: usize,
593    pub dirty_cells: usize,
594    pub dirty_tiles: usize,
595    pub dirty_cell_ratio: f64,
596    pub dirty_tile_ratio: f64,
597    pub scanned_tiles: usize,
598    pub skipped_tiles: usize,
599    pub sat_build_cells: usize,
600    pub scan_cells_estimate: usize,
601    /// Tile rows skipped wholesale by the SAT row prefilter because their SAT
602    /// row sum was zero (no tile in the row was dirty). This is the one thing
603    /// the summed-area table does that the per-tile bool grid cannot: retire a
604    /// whole band of tiles with a single subtraction.
605    pub skipped_tile_rows: usize,
606    /// SAT row-sum queries the prefilter made (one per tile row).
607    pub sat_queries: usize,
608    pub fallback: Option<TileDiffFallback>,
609}
610
611/// Reusable builder for tile counts and SAT.
612#[derive(Debug, Default, Clone)]
613#[must_use]
614pub struct TileDiffBuilder {
615    tile_counts: Vec<u32>,
616    sat: Vec<u32>,
617    dirty_tiles: Vec<bool>,
618}
619
620/// Inputs required to build a tile diff plan.
621#[derive(Debug, Clone, Copy)]
622pub struct TileDiffInput<'a> {
623    pub width: u16,
624    pub height: u16,
625    pub dirty_rows: &'a [bool],
626    pub dirty_bits: &'a [u8],
627    pub dirty_cells: usize,
628    pub dirty_all: bool,
629}
630
631/// Successful tile build with reusable buffers.
632#[derive(Debug, Clone)]
633pub struct TileDiffPlan<'a> {
634    pub params: TileParams,
635    pub stats: TileDiffStats,
636    pub dirty_tiles: &'a [bool],
637    pub tile_counts: &'a [u32],
638    pub sat: &'a [u32],
639}
640
641/// Result of a tile build attempt.
642#[derive(Debug, Clone)]
643pub enum TileDiffBuild<'a> {
644    UseTiles(TileDiffPlan<'a>),
645    Fallback(TileDiffStats),
646}
647
648impl TileDiffPlan<'_> {
649    /// Dirty-cell count in tile row `ty`, in O(1), read straight from the
650    /// summed-area table:
651    ///
652    /// ```text
653    /// sat_w      = tiles_x + 1
654    /// row_sum(ty) = sat[(ty + 1) * sat_w + tiles_x] - sat[ty * sat_w + tiles_x]
655    /// ```
656    ///
657    /// Border column `tiles_x` carries the running prefix total of whole rows,
658    /// so the difference of two adjacent rows is that row's dirty-cell count.
659    /// The SAT is monotonic (counts are non-negative), so the subtraction never
660    /// underflows; `saturating_sub` guards against a corrupt table anyway.
661    /// Returns 0 for an out-of-range row.
662    #[inline]
663    #[must_use]
664    pub fn tile_row_dirty(&self, ty: usize) -> u32 {
665        let tiles_x = self.params.tiles_x;
666        if ty >= self.params.tiles_y {
667            return 0;
668        }
669        let sat_w = tiles_x + 1;
670        let below = self.sat[(ty + 1) * sat_w + tiles_x];
671        let above = self.sat[ty * sat_w + tiles_x];
672        below.saturating_sub(above)
673    }
674
675    /// Dirty-cell count in the tile rectangle `[tx0, tx1) x [ty0, ty1)`, in
676    /// O(1), via the four-corner SAT formula:
677    ///
678    /// ```text
679    /// sat[ty1][tx1] - sat[ty0][tx1] - sat[ty1][tx0] + sat[ty0][tx0]
680    /// ```
681    ///
682    /// This is the README's "O(1) density of any rectangle" query. The scan
683    /// driver itself uses only [`tile_row_dirty`](Self::tile_row_dirty); this
684    /// method exists so the claim is real and testable. Corners are clamped to
685    /// the tile grid; an empty or out-of-range rectangle returns 0. The sum is
686    /// accumulated in `u64` so the two-corner addition cannot overflow before
687    /// the difference (which fits in `u32`) is taken.
688    #[inline]
689    #[must_use]
690    pub fn rect_dirty(&self, tx0: usize, ty0: usize, tx1: usize, ty1: usize) -> u32 {
691        let tiles_x = self.params.tiles_x;
692        let tx1 = tx1.min(tiles_x);
693        let ty1 = ty1.min(self.params.tiles_y);
694        if tx0 >= tx1 || ty0 >= ty1 {
695            return 0;
696        }
697        let sat_w = tiles_x + 1;
698        let at = |ty: usize, tx: usize| u64::from(self.sat[ty * sat_w + tx]);
699        let sum = (at(ty1, tx1) + at(ty0, tx0)).saturating_sub(at(ty0, tx1) + at(ty1, tx0));
700        // The result is bounded by the total dirty-cell count, which fit in a
701        // u32 when the SAT was built, so this cast is lossless.
702        sum as u32
703    }
704}
705
706impl TileDiffBuilder {
707    pub fn new() -> Self {
708        Self::default()
709    }
710
711    pub fn build<'a, 'b>(
712        &'a mut self,
713        config: &TileDiffConfig,
714        input: TileDiffInput<'b>,
715    ) -> TileDiffBuild<'a> {
716        let TileDiffInput {
717            width,
718            height,
719            dirty_rows,
720            dirty_bits,
721            dirty_cells,
722            dirty_all,
723        } = input;
724        let tile_w = clamp_tile_size(config.tile_w);
725        let tile_h = clamp_tile_size(config.tile_h);
726        let width_usize = width as usize;
727        let height_usize = height as usize;
728        let tiles_x = div_ceil_usize(width_usize, tile_w as usize);
729        let tiles_y = div_ceil_usize(height_usize, tile_h as usize);
730        let total_tiles = tiles_x * tiles_y;
731        let total_cells = width_usize * height_usize;
732        let dirty_cell_ratio = if total_cells == 0 {
733            0.0
734        } else {
735            dirty_cells as f64 / total_cells as f64
736        };
737
738        let mut stats = TileDiffStats {
739            width,
740            height,
741            tile_w,
742            tile_h,
743            tiles_x,
744            tiles_y,
745            total_tiles,
746            dirty_cells,
747            dirty_tiles: 0,
748            dirty_cell_ratio,
749            dirty_tile_ratio: 0.0,
750            scanned_tiles: 0,
751            skipped_tiles: total_tiles,
752            sat_build_cells: 0,
753            scan_cells_estimate: 0,
754            skipped_tile_rows: 0,
755            sat_queries: 0,
756            fallback: None,
757        };
758
759        if !config.enabled {
760            stats.fallback = Some(TileDiffFallback::Disabled);
761            return TileDiffBuild::Fallback(stats);
762        }
763
764        if total_cells < config.min_cells_for_tiles {
765            stats.fallback = Some(TileDiffFallback::SmallScreen);
766            return TileDiffBuild::Fallback(stats);
767        }
768
769        if dirty_all {
770            stats.fallback = Some(TileDiffFallback::DirtyAll);
771            return TileDiffBuild::Fallback(stats);
772        }
773
774        if dirty_cell_ratio >= config.dense_cell_ratio {
775            stats.fallback = Some(TileDiffFallback::DenseCells);
776            return TileDiffBuild::Fallback(stats);
777        }
778
779        if total_tiles > config.max_tiles {
780            stats.fallback = Some(TileDiffFallback::TooManyTiles);
781            return TileDiffBuild::Fallback(stats);
782        }
783
784        if dirty_bits.len() < total_cells {
785            stats.fallback = Some(TileDiffFallback::Overflow);
786            return TileDiffBuild::Fallback(stats);
787        }
788
789        self.tile_counts.resize(total_tiles, 0);
790        self.tile_counts.fill(0);
791        self.dirty_tiles.resize(total_tiles, false);
792        self.dirty_tiles.fill(false);
793
794        let tile_w_usize = tile_w as usize;
795        let tile_h_usize = tile_h as usize;
796        let mut overflow = false;
797        let mut scanned_cells = 0usize;
798
799        debug_assert_eq!(dirty_rows.len(), height_usize);
800        for y in 0..height_usize {
801            let row_dirty = if config.skip_clean_rows {
802                dirty_rows.get(y).copied().unwrap_or(true)
803            } else {
804                true
805            };
806            if !row_dirty {
807                continue;
808            }
809            scanned_cells = scanned_cells.saturating_add(width_usize);
810            let row_start = y * width_usize;
811            let tile_y = y / tile_h_usize;
812            for x in 0..width_usize {
813                let idx = row_start + x;
814                if dirty_bits[idx] == 0 {
815                    continue;
816                }
817                let tile_x = x / tile_w_usize;
818                let tile_idx = tile_y * tiles_x + tile_x;
819                match self.tile_counts[tile_idx].checked_add(1) {
820                    Some(value) => self.tile_counts[tile_idx] = value,
821                    None => {
822                        overflow = true;
823                        break;
824                    }
825                }
826            }
827            if overflow {
828                break;
829            }
830        }
831
832        if overflow {
833            stats.fallback = Some(TileDiffFallback::Overflow);
834            return TileDiffBuild::Fallback(stats);
835        }
836
837        let mut dirty_tiles = 0usize;
838        for (idx, count) in self.tile_counts.iter().enumerate() {
839            if *count > 0 {
840                self.dirty_tiles[idx] = true;
841                dirty_tiles += 1;
842            }
843        }
844
845        stats.dirty_tiles = dirty_tiles;
846        stats.dirty_tile_ratio = if total_tiles == 0 {
847            0.0
848        } else {
849            dirty_tiles as f64 / total_tiles as f64
850        };
851        stats.scanned_tiles = dirty_tiles;
852        stats.skipped_tiles = total_tiles.saturating_sub(dirty_tiles);
853        stats.sat_build_cells = scanned_cells;
854        stats.scan_cells_estimate = dirty_tiles * tile_w_usize * tile_h_usize;
855
856        if stats.dirty_tile_ratio >= config.dense_tile_ratio {
857            stats.fallback = Some(TileDiffFallback::DenseTiles);
858            return TileDiffBuild::Fallback(stats);
859        }
860
861        let sat_w = tiles_x + 1;
862        let sat_h = tiles_y + 1;
863        let sat_len = sat_w * sat_h;
864        self.sat.resize(sat_len, 0);
865        self.sat.fill(0);
866
867        for ty in 0..tiles_y {
868            let row_base = (ty + 1) * sat_w;
869            let prev_base = ty * sat_w;
870            for tx in 0..tiles_x {
871                let count = self.tile_counts[ty * tiles_x + tx] as u64;
872                let above = self.sat[prev_base + tx + 1] as u64;
873                let left = self.sat[row_base + tx] as u64;
874                let diag = self.sat[prev_base + tx] as u64;
875                let value = count + above + left - diag;
876                if value > u32::MAX as u64 {
877                    stats.fallback = Some(TileDiffFallback::Overflow);
878                    return TileDiffBuild::Fallback(stats);
879                }
880                self.sat[row_base + tx + 1] = value as u32;
881            }
882        }
883
884        let params = TileParams {
885            width,
886            height,
887            tile_w,
888            tile_h,
889            tiles_x,
890            tiles_y,
891        };
892
893        TileDiffBuild::UseTiles(TileDiffPlan {
894            params,
895            stats,
896            dirty_tiles: &self.dirty_tiles,
897            tile_counts: &self.tile_counts,
898            sat: &self.sat,
899        })
900    }
901
902    fn build_from_buffer<'a>(
903        &'a mut self,
904        config: &TileDiffConfig,
905        buffer: &Buffer,
906    ) -> TileDiffBuild<'a> {
907        let width = buffer.width();
908        let height = buffer.height();
909        let dirty_rows = buffer.dirty_rows();
910        let dirty_bits = buffer.dirty_bits();
911        let dirty_cells = buffer.dirty_cell_count();
912        let dirty_all = buffer.dirty_all();
913
914        let tile_w = clamp_tile_size(config.tile_w);
915        let tile_h = clamp_tile_size(config.tile_h);
916        let width_usize = width as usize;
917        let height_usize = height as usize;
918        let tiles_x = div_ceil_usize(width_usize, tile_w as usize);
919        let tiles_y = div_ceil_usize(height_usize, tile_h as usize);
920        let total_tiles = tiles_x * tiles_y;
921        let total_cells = width_usize * height_usize;
922        let dirty_cell_ratio = if total_cells == 0 {
923            0.0
924        } else {
925            dirty_cells as f64 / total_cells as f64
926        };
927
928        let mut stats = TileDiffStats {
929            width,
930            height,
931            tile_w,
932            tile_h,
933            tiles_x,
934            tiles_y,
935            total_tiles,
936            dirty_cells,
937            dirty_tiles: 0,
938            dirty_cell_ratio,
939            dirty_tile_ratio: 0.0,
940            scanned_tiles: 0,
941            skipped_tiles: total_tiles,
942            sat_build_cells: 0,
943            scan_cells_estimate: 0,
944            skipped_tile_rows: 0,
945            sat_queries: 0,
946            fallback: None,
947        };
948
949        if !config.enabled {
950            stats.fallback = Some(TileDiffFallback::Disabled);
951            return TileDiffBuild::Fallback(stats);
952        }
953
954        if total_cells < config.min_cells_for_tiles {
955            stats.fallback = Some(TileDiffFallback::SmallScreen);
956            return TileDiffBuild::Fallback(stats);
957        }
958
959        if dirty_all {
960            stats.fallback = Some(TileDiffFallback::DirtyAll);
961            return TileDiffBuild::Fallback(stats);
962        }
963
964        if dirty_cell_ratio >= config.dense_cell_ratio {
965            stats.fallback = Some(TileDiffFallback::DenseCells);
966            return TileDiffBuild::Fallback(stats);
967        }
968
969        if total_tiles > config.max_tiles {
970            stats.fallback = Some(TileDiffFallback::TooManyTiles);
971            return TileDiffBuild::Fallback(stats);
972        }
973
974        debug_assert_eq!(dirty_bits.len(), total_cells);
975        if dirty_bits.len() < total_cells {
976            stats.fallback = Some(TileDiffFallback::Overflow);
977            return TileDiffBuild::Fallback(stats);
978        }
979
980        self.tile_counts.resize(total_tiles, 0);
981        self.tile_counts.fill(0);
982        self.dirty_tiles.resize(total_tiles, false);
983        self.dirty_tiles.fill(false);
984
985        let tile_w_usize = tile_w as usize;
986        let tile_h_usize = tile_h as usize;
987        let mut overflow = false;
988        let mut scanned_cells = 0usize;
989
990        debug_assert_eq!(dirty_rows.len(), height_usize);
991        for y in 0..height_usize {
992            let row_dirty = if config.skip_clean_rows {
993                dirty_rows.get(y).copied().unwrap_or(true)
994            } else {
995                true
996            };
997            if !row_dirty {
998                continue;
999            }
1000
1001            let row_start = y * width_usize;
1002            let row_bits = &dirty_bits[row_start..row_start + width_usize];
1003            let tile_y = y / tile_h_usize;
1004            let tile_row_base = tile_y * tiles_x;
1005
1006            let row_result = match buffer.dirty_span_row(y as u16) {
1007                Some(span_row) if !span_row.is_full() => {
1008                    let spans = span_row.spans();
1009                    if spans.is_empty() {
1010                        accumulate_tile_counts_range(
1011                            &mut self.tile_counts,
1012                            row_bits,
1013                            tile_row_base,
1014                            tiles_x,
1015                            tile_w_usize,
1016                            0..width_usize,
1017                            &mut scanned_cells,
1018                        )
1019                    } else {
1020                        let mut result = Ok(());
1021                        for span in spans {
1022                            result = accumulate_tile_counts_range(
1023                                &mut self.tile_counts,
1024                                row_bits,
1025                                tile_row_base,
1026                                tiles_x,
1027                                tile_w_usize,
1028                                span.x0 as usize..span.x1 as usize,
1029                                &mut scanned_cells,
1030                            );
1031                            if result.is_err() {
1032                                break;
1033                            }
1034                        }
1035                        result
1036                    }
1037                }
1038                _ => accumulate_tile_counts_range(
1039                    &mut self.tile_counts,
1040                    row_bits,
1041                    tile_row_base,
1042                    tiles_x,
1043                    tile_w_usize,
1044                    0..width_usize,
1045                    &mut scanned_cells,
1046                ),
1047            };
1048
1049            if row_result.is_err() {
1050                overflow = true;
1051                break;
1052            }
1053        }
1054
1055        if overflow {
1056            stats.fallback = Some(TileDiffFallback::Overflow);
1057            return TileDiffBuild::Fallback(stats);
1058        }
1059
1060        let mut dirty_tiles = 0usize;
1061        for (idx, count) in self.tile_counts.iter().enumerate() {
1062            if *count > 0 {
1063                self.dirty_tiles[idx] = true;
1064                dirty_tiles += 1;
1065            }
1066        }
1067
1068        stats.dirty_tiles = dirty_tiles;
1069        stats.dirty_tile_ratio = if total_tiles == 0 {
1070            0.0
1071        } else {
1072            dirty_tiles as f64 / total_tiles as f64
1073        };
1074        stats.scanned_tiles = dirty_tiles;
1075        stats.skipped_tiles = total_tiles.saturating_sub(dirty_tiles);
1076        stats.sat_build_cells = scanned_cells;
1077        stats.scan_cells_estimate = dirty_tiles * tile_w_usize * tile_h_usize;
1078
1079        if stats.dirty_tile_ratio >= config.dense_tile_ratio {
1080            stats.fallback = Some(TileDiffFallback::DenseTiles);
1081            return TileDiffBuild::Fallback(stats);
1082        }
1083
1084        let sat_w = tiles_x + 1;
1085        let sat_h = tiles_y + 1;
1086        let sat_len = sat_w * sat_h;
1087        self.sat.resize(sat_len, 0);
1088        self.sat.fill(0);
1089
1090        for ty in 0..tiles_y {
1091            let row_base = (ty + 1) * sat_w;
1092            let prev_base = ty * sat_w;
1093            for tx in 0..tiles_x {
1094                let count = self.tile_counts[ty * tiles_x + tx] as u64;
1095                let above = self.sat[prev_base + tx + 1] as u64;
1096                let left = self.sat[row_base + tx] as u64;
1097                let diag = self.sat[prev_base + tx] as u64;
1098                let value = count + above + left - diag;
1099                if value > u32::MAX as u64 {
1100                    stats.fallback = Some(TileDiffFallback::Overflow);
1101                    return TileDiffBuild::Fallback(stats);
1102                }
1103                self.sat[row_base + tx + 1] = value as u32;
1104            }
1105        }
1106
1107        let params = TileParams {
1108            width,
1109            height,
1110            tile_w,
1111            tile_h,
1112            tiles_x,
1113            tiles_y,
1114        };
1115
1116        TileDiffBuild::UseTiles(TileDiffPlan {
1117            params,
1118            stats,
1119            dirty_tiles: &self.dirty_tiles,
1120            tile_counts: &self.tile_counts,
1121            sat: &self.sat,
1122        })
1123    }
1124}
1125
1126#[inline]
1127fn reserve_changes_capacity(width: u16, height: u16, changes: &mut Vec<(u16, u16)>) {
1128    // Estimate capacity: assume ~5% of cells change on average.
1129    let estimated_changes = (width as usize * height as usize) / 20;
1130    let additional = estimated_changes.saturating_sub(changes.len());
1131    if additional > 0 {
1132        changes.reserve(additional);
1133    }
1134}
1135
1136fn compute_changes(old: &Buffer, new: &Buffer, changes: &mut Vec<(u16, u16)>) {
1137    #[cfg(feature = "tracing")]
1138    let _span = tracing::debug_span!("diff_compute", width = old.width(), height = old.height());
1139    #[cfg(feature = "tracing")]
1140    let _guard = _span.enter();
1141
1142    assert_eq!(old.width(), new.width(), "buffer widths must match");
1143    assert_eq!(old.height(), new.height(), "buffer heights must match");
1144
1145    let width = old.width();
1146    let height = old.height();
1147    let w = width as usize;
1148
1149    changes.clear();
1150    reserve_changes_capacity(width, height, changes);
1151
1152    let old_cells = old.cells();
1153    let new_cells = new.cells();
1154
1155    // Row-major scan with row-skip fast path
1156    for y in 0..height {
1157        let row_start = y as usize * w;
1158        let old_row = &old_cells[row_start..row_start + w];
1159        let new_row = &new_cells[row_start..row_start + w];
1160
1161        // Scan for changed cells using blockwise row scan.
1162        // This avoids a full-row equality pre-scan and prevents
1163        // double-scanning rows that contain changes.
1164        scan_row_changes(old_row, new_row, y, changes);
1165    }
1166
1167    #[cfg(feature = "tracing")]
1168    tracing::trace!(changes = changes.len(), "diff computed");
1169}
1170
1171fn compute_dirty_changes(
1172    old: &Buffer,
1173    new: &Buffer,
1174    changes: &mut Vec<(u16, u16)>,
1175    tile_builder: &mut TileDiffBuilder,
1176    tile_config: &TileDiffConfig,
1177    tile_stats_out: &mut Option<TileDiffStats>,
1178) {
1179    assert_eq!(old.width(), new.width(), "buffer widths must match");
1180    assert_eq!(old.height(), new.height(), "buffer heights must match");
1181
1182    let width = old.width();
1183    let height = old.height();
1184    let w = width as usize;
1185
1186    changes.clear();
1187    reserve_changes_capacity(width, height, changes);
1188
1189    let old_cells = old.cells();
1190    let new_cells = new.cells();
1191    let dirty = new.dirty_rows();
1192
1193    *tile_stats_out = None;
1194    let tile_build = tile_builder.build_from_buffer(tile_config, new);
1195
1196    if let TileDiffBuild::UseTiles(plan) = tile_build {
1197        let mut stats = plan.stats;
1198        let tile_w = plan.params.tile_w as usize;
1199        let tile_h = plan.params.tile_h as usize;
1200        let tiles_x = plan.params.tiles_x;
1201        let tiles_y = plan.params.tiles_y;
1202        let height_usize = height as usize;
1203        let dirty_tiles = plan.dirty_tiles;
1204
1205        let mut skipped_tile_rows = 0usize;
1206        let mut sat_queries = 0usize;
1207
1208        // Walk whole tile rows. The summed-area table retires a clean band (row
1209        // sum 0) with a single subtraction, so its `tile_h` buffer rows are
1210        // never touched — the one thing the prefix-sum table does that the
1211        // per-tile bool grid cannot. A zero row sum means every tile in the row
1212        // has zero dirty cells, exactly what the per-tile skip would have found,
1213        // so the emitted changes are identical to the flat scan.
1214        for tile_y in 0..tiles_y {
1215            sat_queries += 1;
1216            if plan.tile_row_dirty(tile_y) == 0 {
1217                skipped_tile_rows += 1;
1218                continue;
1219            }
1220
1221            let tile_row_base = tile_y * tiles_x;
1222            debug_assert!(tile_row_base + tiles_x <= dirty_tiles.len());
1223            let y_start = tile_y * tile_h;
1224            let y_end = ((tile_y + 1) * tile_h).min(height_usize);
1225
1226            for y in y_start..y_end {
1227                if !dirty[y] {
1228                    continue;
1229                }
1230
1231                let row_start = y * w;
1232                let old_row = &old_cells[row_start..row_start + w];
1233                let new_row = &new_cells[row_start..row_start + w];
1234
1235                if old_row == new_row {
1236                    continue;
1237                }
1238
1239                let y16 = y as u16;
1240                let span_row = new.dirty_span_row(y16);
1241                if let Some(span_row) = span_row {
1242                    if span_row.is_full() {
1243                        scan_row_tiles(
1244                            old_row,
1245                            new_row,
1246                            y16,
1247                            w,
1248                            tile_w,
1249                            tiles_x,
1250                            tile_row_base,
1251                            dirty_tiles,
1252                            changes,
1253                        );
1254                        continue;
1255                    }
1256                    let spans = span_row.spans();
1257                    if spans.is_empty() {
1258                        scan_row_tiles(
1259                            old_row,
1260                            new_row,
1261                            y16,
1262                            w,
1263                            tile_w,
1264                            tiles_x,
1265                            tile_row_base,
1266                            dirty_tiles,
1267                            changes,
1268                        );
1269                        continue;
1270                    }
1271                    scan_row_tiles_spans(
1272                        old_row,
1273                        new_row,
1274                        y16,
1275                        w,
1276                        tile_w,
1277                        tiles_x,
1278                        tile_row_base,
1279                        dirty_tiles,
1280                        spans,
1281                        changes,
1282                    );
1283                } else {
1284                    scan_row_tiles(
1285                        old_row,
1286                        new_row,
1287                        y16,
1288                        w,
1289                        tile_w,
1290                        tiles_x,
1291                        tile_row_base,
1292                        dirty_tiles,
1293                        changes,
1294                    );
1295                }
1296            }
1297        }
1298
1299        stats.skipped_tile_rows = skipped_tile_rows;
1300        stats.sat_queries = sat_queries;
1301        *tile_stats_out = Some(stats);
1302        return;
1303    }
1304
1305    if let TileDiffBuild::Fallback(stats) = tile_build {
1306        *tile_stats_out = Some(stats);
1307    }
1308
1309    for y in 0..height {
1310        // Skip clean rows (the key optimization).
1311        if !dirty[y as usize] {
1312            continue;
1313        }
1314
1315        let row_start = y as usize * w;
1316        let old_row = &old_cells[row_start..row_start + w];
1317        let new_row = &new_cells[row_start..row_start + w];
1318
1319        // Even for dirty rows, row-skip fast path applies:
1320        // a row may be marked dirty but end up identical after compositing.
1321        if old_row == new_row {
1322            continue;
1323        }
1324
1325        let span_row = new.dirty_span_row(y);
1326        if let Some(span_row) = span_row {
1327            if span_row.is_full() {
1328                scan_row_changes(old_row, new_row, y, changes);
1329                continue;
1330            }
1331            let spans = span_row.spans();
1332            if spans.is_empty() {
1333                scan_row_changes(old_row, new_row, y, changes);
1334                continue;
1335            }
1336            scan_row_changes_spans(old_row, new_row, y, spans, changes);
1337        } else {
1338            scan_row_changes(old_row, new_row, y, changes);
1339        }
1340    }
1341}
1342
1343/// A contiguous run of changed cells on a single row.
1344///
1345/// Used by the presenter to emit efficient cursor positioning.
1346/// Instead of positioning for each cell, position once and emit the run.
1347#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1348pub struct ChangeRun {
1349    /// Row index.
1350    pub y: u16,
1351    /// Start column (inclusive).
1352    pub x0: u16,
1353    /// End column (inclusive).
1354    pub x1: u16,
1355}
1356
1357impl ChangeRun {
1358    /// Create a new change run.
1359    #[inline]
1360    pub const fn new(y: u16, x0: u16, x1: u16) -> Self {
1361        debug_assert!(x0 <= x1);
1362        Self { y, x0, x1 }
1363    }
1364
1365    /// Number of cells in this run.
1366    #[inline]
1367    pub const fn len(&self) -> usize {
1368        self.x1.saturating_sub(self.x0) as usize + 1
1369    }
1370
1371    /// Check if this run is empty (should never happen in practice).
1372    #[inline]
1373    pub const fn is_empty(&self) -> bool {
1374        self.x1 < self.x0
1375    }
1376}
1377
1378/// The diff between two buffers.
1379///
1380/// Contains the list of (x, y) positions where cells differ.
1381#[derive(Debug, Clone, Default)]
1382pub struct BufferDiff {
1383    /// List of changed cell positions (x, y).
1384    changes: Vec<(u16, u16)>,
1385    /// Reusable tile builder for SAT-based diff skipping.
1386    tile_builder: TileDiffBuilder,
1387    /// Tile diff configuration (thresholds + sizes).
1388    tile_config: TileDiffConfig,
1389    /// Last tile diagnostics from a dirty diff pass.
1390    last_tile_stats: Option<TileDiffStats>,
1391}
1392
1393impl BufferDiff {
1394    /// Create an empty diff.
1395    pub fn new() -> Self {
1396        Self {
1397            changes: Vec::new(),
1398            tile_builder: TileDiffBuilder::default(),
1399            tile_config: TileDiffConfig::default(),
1400            last_tile_stats: None,
1401        }
1402    }
1403
1404    /// Create a diff with pre-allocated capacity.
1405    pub fn with_capacity(capacity: usize) -> Self {
1406        let mut diff = Self::new();
1407        diff.changes = Vec::with_capacity(capacity);
1408        diff
1409    }
1410
1411    /// Create a diff that marks every cell as changed.
1412    ///
1413    /// Useful for full-screen redraws where the previous buffer is unknown
1414    /// (e.g., after resize or initial present).
1415    pub fn full(width: u16, height: u16) -> Self {
1416        if width == 0 || height == 0 {
1417            return Self::new();
1418        }
1419
1420        let total = width as usize * height as usize;
1421        let mut changes = Vec::with_capacity(total);
1422        for y in 0..height {
1423            for x in 0..width {
1424                changes.push((x, y));
1425            }
1426        }
1427        let mut diff = Self::new();
1428        diff.changes = changes;
1429        diff
1430    }
1431
1432    /// Compute the diff between two buffers.
1433    ///
1434    /// Uses row-major scan for cache efficiency. Both buffers must have
1435    /// the same dimensions.
1436    ///
1437    /// # Optimizations
1438    ///
1439    /// - **Row-skip fast path**: unchanged rows are detected via slice
1440    ///   equality and skipped entirely. For typical UI updates where most
1441    ///   rows are static, this eliminates the majority of per-cell work.
1442    /// - **Blockwise row scan**: rows with sparse edits are scanned in
1443    ///   coarse blocks, skipping unchanged blocks and only diving into
1444    ///   the blocks that differ.
1445    /// - **Direct slice iteration**: row slices are computed once per row
1446    ///   instead of calling `get_unchecked(x, y)` per cell, eliminating
1447    ///   repeated `y * width + x` index arithmetic.
1448    /// - **Branchless cell comparison**: `bits_eq` uses bitwise AND to
1449    ///   avoid branch mispredictions in the inner loop.
1450    ///
1451    /// # Panics
1452    ///
1453    /// Debug-asserts that both buffers have identical dimensions.
1454    pub fn compute(old: &Buffer, new: &Buffer) -> Self {
1455        let mut diff = Self::new();
1456        diff.compute_into(old, new);
1457        diff
1458    }
1459
1460    /// Compute the diff into an existing buffer to reuse allocation.
1461    pub fn compute_into(&mut self, old: &Buffer, new: &Buffer) {
1462        self.last_tile_stats = None;
1463        compute_changes(old, new, &mut self.changes);
1464    }
1465
1466    /// Compute the diff between two buffers using dirty-row hints.
1467    ///
1468    /// Only rows marked dirty in `new` are compared cell-by-cell.
1469    /// Clean rows are skipped entirely (O(1) per clean row).
1470    ///
1471    /// # Soundness precondition
1472    ///
1473    /// `new`'s content at the time of its last `clear_dirty()` /
1474    /// `reset_for_frame()` must have been identical to `old`. The dirty
1475    /// state (rows, spans, per-cell bits) records *mutations since that
1476    /// point*, and this path narrows the scan not just to dirty rows but to
1477    /// the recorded dirty spans/tiles *within* them — so any old-vs-new
1478    /// difference that is not also a recorded mutation is silently missed.
1479    /// The row-level invariant alone ("changed rows are dirty") is NOT
1480    /// sufficient. The production writer satisfies the precondition by
1481    /// diffing consecutive frames of one buffer lineage whose baseline was
1482    /// fully dirty.
1483    ///
1484    /// False positives (marking a row/span dirty when it didn't actually
1485    /// change) are safe — they only cost the per-cell scan for that region.
1486    pub fn compute_dirty(old: &Buffer, new: &Buffer) -> Self {
1487        let mut diff = Self::new();
1488        diff.compute_dirty_into(old, new);
1489        diff
1490    }
1491
1492    /// Compute the dirty-row diff into an existing buffer to reuse allocation.
1493    ///
1494    /// Same soundness precondition as [`compute_dirty`](Self::compute_dirty):
1495    /// `new`'s dirty state must have been cleared while its content was
1496    /// identical to `old`.
1497    pub fn compute_dirty_into(&mut self, old: &Buffer, new: &Buffer) {
1498        compute_dirty_changes(
1499            old,
1500            new,
1501            &mut self.changes,
1502            &mut self.tile_builder,
1503            &self.tile_config,
1504            &mut self.last_tile_stats,
1505        );
1506    }
1507
1508    /// Compute the diff with a certificate-based skip hint.
1509    ///
1510    /// The caller (typically the runtime loop) evaluates a render certificate
1511    /// and passes the result as a `DiffSkipHint`. This method shortcuts the
1512    /// diff computation when the certificate allows it:
1513    ///
1514    /// - `FullDiff`: performs the standard dirty-diff computation.
1515    /// - `SkipDiff`: clears changes (no work to present). The caller must
1516    ///   ensure that old and new buffers are identical when issuing this hint.
1517    /// - `NarrowToRows(rows)`: only diffs the specified rows, skipping all
1518    ///   others even if marked dirty. Useful when the certificate identifies
1519    ///   exactly which rows changed.
1520    ///
1521    /// # Safety invariant
1522    ///
1523    /// Issuing `SkipDiff` when buffers differ produces stale frames.
1524    /// The certificate evaluator must guarantee correctness — this method
1525    /// trusts the hint without verification. The `FullDiff` arm delegates to
1526    /// [`compute_dirty_into`](Self::compute_dirty_into) and inherits its
1527    /// baseline-equals-`old` precondition. `NarrowToRows` rows are processed
1528    /// in ascending unique order (the method sorts/dedups defensively) so
1529    /// the change list keeps the sorted-unique invariant `runs()` requires.
1530    ///
1531    /// # Tracing
1532    ///
1533    /// Emits a tracing event when a skip or narrow is applied, including
1534    /// the hint type and resulting change count for evidence logging.
1535    pub fn compute_certified_into(&mut self, old: &Buffer, new: &Buffer, hint: DiffSkipHint) {
1536        match hint {
1537            DiffSkipHint::FullDiff => {
1538                // Standard path — no certificate benefit
1539                self.compute_dirty_into(old, new);
1540            }
1541            DiffSkipHint::SkipDiff => {
1542                // Certificate guarantees buffers are identical — skip all work
1543                self.changes.clear();
1544                self.last_tile_stats = None;
1545                #[cfg(feature = "tracing")]
1546                tracing::debug!(
1547                    event = "diff_skip_certified",
1548                    hint = "skip_diff",
1549                    changes = 0,
1550                );
1551            }
1552            DiffSkipHint::NarrowToRows(ref rows) => {
1553                // Only diff the specified rows
1554                self.changes.clear();
1555                self.last_tile_stats = None;
1556
1557                let w = old.width();
1558                let h = old.height();
1559                // Hard assert for parity with the full/dirty paths: a
1560                // dimension mismatch here would scan `new` with `old`'s
1561                // stride and produce coordinates matching neither buffer.
1562                assert_eq!(w, new.width(), "diff dimension mismatch");
1563                assert_eq!(h, new.height(), "diff dimension mismatch");
1564
1565                let old_cells = old.cells();
1566                let new_cells = new.cells();
1567                let stride = w as usize;
1568
1569                // Defensive sort+dedup: `runs()` and downstream accounting
1570                // (change counts fed to the strategy selector) rely on the
1571                // change list being (y, x)-sorted and duplicate-free. The
1572                // production witness (dirty_row_indices) is already
1573                // ascending/unique, so this is a no-op there.
1574                let mut sorted_rows: Vec<u16> = rows.clone();
1575                sorted_rows.sort_unstable();
1576                sorted_rows.dedup();
1577
1578                for &row in &sorted_rows {
1579                    if row >= h {
1580                        continue;
1581                    }
1582                    let start = row as usize * stride;
1583                    let end = start + stride;
1584                    if end > old_cells.len() || end > new_cells.len() {
1585                        continue;
1586                    }
1587                    let old_row = &old_cells[start..end];
1588                    let new_row = &new_cells[start..end];
1589                    if old_row == new_row {
1590                        continue;
1591                    }
1592                    for (x, (o, n)) in old_row.iter().zip(new_row.iter()).enumerate() {
1593                        if !o.bits_eq(n) {
1594                            self.changes.push((x as u16, row));
1595                        }
1596                    }
1597                }
1598
1599                #[cfg(feature = "tracing")]
1600                tracing::debug!(
1601                    event = "diff_narrow_certified",
1602                    hint = "narrow_to_rows",
1603                    rows_checked = sorted_rows.len(),
1604                    changes = self.changes.len(),
1605                );
1606            }
1607        }
1608    }
1609
1610    /// Populate the diff with all cells (full redraw) reusing existing capacity.
1611    pub fn fill_full(&mut self, width: u16, height: u16) {
1612        self.changes.clear();
1613        let total = width as usize * height as usize;
1614        if self.changes.capacity() < total {
1615            self.changes.reserve(total - self.changes.len());
1616        }
1617        for y in 0..height {
1618            for x in 0..width {
1619                self.changes.push((x, y));
1620            }
1621        }
1622        // Tile diagnostics describe the previous dirty pass, not this full
1623        // refill — drop them so telemetry can't attribute stale stats here.
1624        self.last_tile_stats = None;
1625    }
1626
1627    /// Number of changed cells.
1628    #[inline]
1629    pub fn len(&self) -> usize {
1630        self.changes.len()
1631    }
1632
1633    /// Check if no cells changed.
1634    #[inline]
1635    pub fn is_empty(&self) -> bool {
1636        self.changes.is_empty()
1637    }
1638
1639    /// Get the list of changed positions.
1640    #[inline]
1641    pub fn changes(&self) -> &[(u16, u16)] {
1642        &self.changes
1643    }
1644
1645    /// Access the last tile diagnostics from a dirty diff pass.
1646    #[inline]
1647    pub fn last_tile_stats(&self) -> Option<TileDiffStats> {
1648        self.last_tile_stats
1649    }
1650
1651    /// Mutably access tile diff configuration.
1652    #[inline]
1653    pub fn tile_config_mut(&mut self) -> &mut TileDiffConfig {
1654        &mut self.tile_config
1655    }
1656
1657    /// Convert point changes into contiguous runs.
1658    ///
1659    /// Consecutive x positions on the same row are coalesced into a single run.
1660    /// This enables efficient cursor positioning in the presenter.
1661    pub fn runs(&self) -> Vec<ChangeRun> {
1662        #[cfg(feature = "tracing")]
1663        let _span = tracing::debug_span!("diff_runs", changes = self.changes.len());
1664        #[cfg(feature = "tracing")]
1665        let _guard = _span.enter();
1666
1667        if self.changes.is_empty() {
1668            return Vec::new();
1669        }
1670
1671        // Changes are already sorted by (y, x) from row-major scan
1672        // so we don't need to sort again.
1673        let sorted = &self.changes;
1674        let len = sorted.len();
1675
1676        // Worst case: every change is isolated, so runs == changes.
1677        // Pre-alloc to avoid repeated growth in hot paths.
1678        let mut runs = Vec::with_capacity(len);
1679
1680        let mut i = 0;
1681
1682        while i < len {
1683            let (x0, y) = sorted[i];
1684            let mut x1 = x0;
1685            i += 1;
1686
1687            // Coalesce consecutive x positions on the same row
1688            while i < len {
1689                let (x, yy) = sorted[i];
1690                if yy != y || x != x1.saturating_add(1) {
1691                    break;
1692                }
1693                x1 = x;
1694                i += 1;
1695            }
1696
1697            runs.push(ChangeRun::new(y, x0, x1));
1698        }
1699
1700        #[cfg(feature = "tracing")]
1701        tracing::trace!(run_count = runs.len(), "runs coalesced");
1702
1703        runs
1704    }
1705
1706    /// Like `runs()` but writes into a caller-provided buffer, avoiding
1707    /// per-frame allocation when the buffer is reused across frames.
1708    pub fn runs_into(&self, out: &mut Vec<ChangeRun>) {
1709        out.clear();
1710
1711        #[cfg(feature = "tracing")]
1712        let _span = tracing::debug_span!("diff_runs_into", changes = self.changes.len());
1713        #[cfg(feature = "tracing")]
1714        let _guard = _span.enter();
1715
1716        if self.changes.is_empty() {
1717            return;
1718        }
1719
1720        let sorted = &self.changes;
1721        let len = sorted.len();
1722        let mut i = 0;
1723
1724        while i < len {
1725            let (x0, y) = sorted[i];
1726            let mut x1 = x0;
1727            i += 1;
1728
1729            while i < len {
1730                let (x, yy) = sorted[i];
1731                if yy != y || x != x1.saturating_add(1) {
1732                    break;
1733                }
1734                x1 = x;
1735                i += 1;
1736            }
1737
1738            out.push(ChangeRun::new(y, x0, x1));
1739        }
1740
1741        #[cfg(feature = "tracing")]
1742        tracing::trace!(run_count = out.len(), "runs coalesced (reuse)");
1743    }
1744
1745    /// Iterate over changed positions.
1746    #[inline]
1747    pub fn iter(&self) -> impl Iterator<Item = (u16, u16)> + '_ {
1748        self.changes.iter().copied()
1749    }
1750
1751    /// Clear the diff, removing all recorded changes.
1752    pub fn clear(&mut self) {
1753        self.changes.clear();
1754        self.last_tile_stats = None;
1755    }
1756}
1757
1758#[cfg(test)]
1759mod tests {
1760    fn is_coverage_run() -> bool {
1761        if let Ok(value) = std::env::var("FTUI_COVERAGE") {
1762            let value = value.to_ascii_lowercase();
1763            if matches!(value.as_str(), "1" | "true" | "yes") {
1764                return true;
1765            }
1766            if matches!(value.as_str(), "0" | "false" | "no") {
1767                return false;
1768            }
1769        }
1770        std::env::var("LLVM_PROFILE_FILE").is_ok() || std::env::var("CARGO_LLVM_COV").is_ok()
1771    }
1772    use super::*;
1773    use crate::cell::{Cell, PackedRgba};
1774
1775    #[test]
1776    fn scan_row_changes_range_reports_late_change_after_equal_quad() {
1777        let old = vec![Cell::default(); 8];
1778        let mut new = old.clone();
1779        let mut changes = Vec::new();
1780
1781        new[7] = Cell::from_char('X');
1782        scan_row_changes_range(&old, &new, 4, 10, &mut changes);
1783
1784        assert_eq!(changes, vec![(17, 4)]);
1785    }
1786
1787    #[test]
1788    fn empty_diff_when_buffers_identical() {
1789        let buf1 = Buffer::new(10, 10);
1790        let buf2 = Buffer::new(10, 10);
1791        let diff = BufferDiff::compute(&buf1, &buf2);
1792
1793        assert!(diff.is_empty());
1794        assert_eq!(diff.len(), 0);
1795    }
1796
1797    #[test]
1798    fn full_diff_marks_all_cells() {
1799        let diff = BufferDiff::full(3, 2);
1800        assert_eq!(diff.len(), 6);
1801        assert_eq!(diff.changes()[0], (0, 0));
1802        assert_eq!(diff.changes()[5], (2, 1));
1803    }
1804
1805    #[test]
1806    fn single_cell_change_detected() {
1807        let old = Buffer::new(10, 10);
1808        let mut new = Buffer::new(10, 10);
1809
1810        new.set_raw(5, 5, Cell::from_char('X'));
1811        let diff = BufferDiff::compute(&old, &new);
1812
1813        assert_eq!(diff.len(), 1);
1814        assert_eq!(diff.changes(), &[(5, 5)]);
1815    }
1816
1817    #[test]
1818    fn dirty_row_false_positive_skipped() {
1819        let old = Buffer::new(8, 2);
1820        let mut new = old.clone();
1821
1822        // Clear initial dirty state to isolate this row.
1823        new.clear_dirty();
1824        // Mark row 0 dirty without changing content.
1825        new.set_raw(2, 0, Cell::default());
1826
1827        let diff = BufferDiff::compute_dirty(&old, &new);
1828        assert!(
1829            diff.is_empty(),
1830            "dirty row with no changes should be skipped"
1831        );
1832    }
1833
1834    #[test]
1835    fn multiple_scattered_changes_detected() {
1836        let old = Buffer::new(10, 10);
1837        let mut new = Buffer::new(10, 10);
1838
1839        new.set_raw(0, 0, Cell::from_char('A'));
1840        new.set_raw(9, 9, Cell::from_char('B'));
1841        new.set_raw(5, 3, Cell::from_char('C'));
1842
1843        let diff = BufferDiff::compute(&old, &new);
1844
1845        assert_eq!(diff.len(), 3);
1846        // Sorted by row-major order: (0,0), (5,3), (9,9)
1847        let changes = diff.changes();
1848        assert!(changes.contains(&(0, 0)));
1849        assert!(changes.contains(&(9, 9)));
1850        assert!(changes.contains(&(5, 3)));
1851    }
1852
1853    #[test]
1854    fn runs_coalesces_adjacent_cells() {
1855        let old = Buffer::new(10, 10);
1856        let mut new = Buffer::new(10, 10);
1857
1858        // Three adjacent cells on row 5
1859        new.set_raw(3, 5, Cell::from_char('A'));
1860        new.set_raw(4, 5, Cell::from_char('B'));
1861        new.set_raw(5, 5, Cell::from_char('C'));
1862
1863        let diff = BufferDiff::compute(&old, &new);
1864        let runs = diff.runs();
1865
1866        assert_eq!(runs.len(), 1);
1867        assert_eq!(runs[0].y, 5);
1868        assert_eq!(runs[0].x0, 3);
1869        assert_eq!(runs[0].x1, 5);
1870        assert_eq!(runs[0].len(), 3);
1871    }
1872
1873    #[test]
1874    fn runs_handles_gaps_correctly() {
1875        let old = Buffer::new(10, 10);
1876        let mut new = Buffer::new(10, 10);
1877
1878        // Two groups with a gap
1879        new.set_raw(0, 0, Cell::from_char('A'));
1880        new.set_raw(1, 0, Cell::from_char('B'));
1881        // gap at x=2
1882        new.set_raw(3, 0, Cell::from_char('C'));
1883        new.set_raw(4, 0, Cell::from_char('D'));
1884
1885        let diff = BufferDiff::compute(&old, &new);
1886        let runs = diff.runs();
1887
1888        assert_eq!(runs.len(), 2);
1889
1890        assert_eq!(runs[0].y, 0);
1891        assert_eq!(runs[0].x0, 0);
1892        assert_eq!(runs[0].x1, 1);
1893
1894        assert_eq!(runs[1].y, 0);
1895        assert_eq!(runs[1].x0, 3);
1896        assert_eq!(runs[1].x1, 4);
1897    }
1898
1899    #[test]
1900    fn runs_handles_max_column_without_overflow() {
1901        let mut diff = BufferDiff::new();
1902        diff.changes = vec![(u16::MAX, 0)];
1903
1904        let runs = diff.runs();
1905
1906        assert_eq!(runs.len(), 1);
1907        assert_eq!(runs[0], ChangeRun::new(0, u16::MAX, u16::MAX));
1908    }
1909
1910    #[test]
1911    fn runs_handles_multiple_rows() {
1912        let old = Buffer::new(10, 10);
1913        let mut new = Buffer::new(10, 10);
1914
1915        // Changes on multiple rows
1916        new.set_raw(0, 0, Cell::from_char('A'));
1917        new.set_raw(1, 0, Cell::from_char('B'));
1918        new.set_raw(5, 2, Cell::from_char('C'));
1919        new.set_raw(0, 5, Cell::from_char('D'));
1920
1921        let diff = BufferDiff::compute(&old, &new);
1922        let runs = diff.runs();
1923
1924        assert_eq!(runs.len(), 3);
1925
1926        // Row 0: (0-1)
1927        assert_eq!(runs[0].y, 0);
1928        assert_eq!(runs[0].x0, 0);
1929        assert_eq!(runs[0].x1, 1);
1930
1931        // Row 2: (5)
1932        assert_eq!(runs[1].y, 2);
1933        assert_eq!(runs[1].x0, 5);
1934        assert_eq!(runs[1].x1, 5);
1935
1936        // Row 5: (0)
1937        assert_eq!(runs[2].y, 5);
1938        assert_eq!(runs[2].x0, 0);
1939        assert_eq!(runs[2].x1, 0);
1940    }
1941
1942    #[test]
1943    fn empty_runs_from_empty_diff() {
1944        let diff = BufferDiff::new();
1945        let runs = diff.runs();
1946        assert!(runs.is_empty());
1947    }
1948
1949    #[test]
1950    fn change_run_len() {
1951        let run = ChangeRun::new(0, 5, 10);
1952        assert_eq!(run.len(), 6);
1953
1954        let single = ChangeRun::new(0, 5, 5);
1955        assert_eq!(single.len(), 1);
1956    }
1957
1958    #[test]
1959    fn color_changes_detected() {
1960        let old = Buffer::new(10, 10);
1961        let mut new = Buffer::new(10, 10);
1962
1963        // Same empty content but different color
1964        new.set_raw(5, 5, Cell::default().with_fg(PackedRgba::rgb(255, 0, 0)));
1965
1966        let diff = BufferDiff::compute(&old, &new);
1967        assert_eq!(diff.len(), 1);
1968    }
1969
1970    #[test]
1971    fn diff_iter() {
1972        let old = Buffer::new(5, 5);
1973        let mut new = Buffer::new(5, 5);
1974        new.set_raw(1, 1, Cell::from_char('X'));
1975        new.set_raw(2, 2, Cell::from_char('Y'));
1976
1977        let diff = BufferDiff::compute(&old, &new);
1978        let positions: Vec<_> = diff.iter().collect();
1979
1980        assert_eq!(positions.len(), 2);
1981        assert!(positions.contains(&(1, 1)));
1982        assert!(positions.contains(&(2, 2)));
1983    }
1984
1985    #[test]
1986    fn diff_clear() {
1987        let old = Buffer::new(5, 5);
1988        let mut new = Buffer::new(5, 5);
1989        new.set_raw(1, 1, Cell::from_char('X'));
1990
1991        let mut diff = BufferDiff::compute(&old, &new);
1992        assert_eq!(diff.len(), 1);
1993
1994        diff.clear();
1995        assert!(diff.is_empty());
1996    }
1997
1998    #[test]
1999    fn with_capacity() {
2000        let diff = BufferDiff::with_capacity(100);
2001        assert!(diff.is_empty());
2002    }
2003
2004    #[test]
2005    fn full_buffer_change() {
2006        let old = Buffer::new(5, 5);
2007        let mut new = Buffer::new(5, 5);
2008
2009        // Change every cell
2010        for y in 0..5 {
2011            for x in 0..5 {
2012                new.set_raw(x, y, Cell::from_char('#'));
2013            }
2014        }
2015
2016        let diff = BufferDiff::compute(&old, &new);
2017        assert_eq!(diff.len(), 25);
2018
2019        // Should coalesce into 5 runs (one per row)
2020        let runs = diff.runs();
2021        assert_eq!(runs.len(), 5);
2022
2023        for (i, run) in runs.iter().enumerate() {
2024            assert_eq!(run.y, i as u16);
2025            assert_eq!(run.x0, 0);
2026            assert_eq!(run.x1, 4);
2027            assert_eq!(run.len(), 5);
2028        }
2029    }
2030
2031    #[test]
2032    fn row_major_order_preserved() {
2033        let old = Buffer::new(3, 3);
2034        let mut new = Buffer::new(3, 3);
2035
2036        // Set cells in non-row-major order
2037        new.set_raw(2, 2, Cell::from_char('C'));
2038        new.set_raw(0, 0, Cell::from_char('A'));
2039        new.set_raw(1, 1, Cell::from_char('B'));
2040
2041        let diff = BufferDiff::compute(&old, &new);
2042
2043        // Row-major scan should produce (0,0), (1,1), (2,2)
2044        let changes = diff.changes();
2045        assert_eq!(changes[0], (0, 0));
2046        assert_eq!(changes[1], (1, 1));
2047        assert_eq!(changes[2], (2, 2));
2048    }
2049
2050    #[test]
2051    fn blockwise_scan_preserves_sparse_row_changes() {
2052        let old = Buffer::new(64, 2);
2053        let mut new = old.clone();
2054
2055        new.set_raw(1, 0, Cell::from_char('A'));
2056        new.set_raw(33, 0, Cell::from_char('B'));
2057        new.set_raw(62, 1, Cell::from_char('C'));
2058
2059        let diff = BufferDiff::compute(&old, &new);
2060        assert_eq!(diff.changes(), &[(1, 0), (33, 0), (62, 1)]);
2061    }
2062
2063    #[test]
2064    fn rows_with_no_changes_are_skipped() {
2065        let old = Buffer::new(4, 3);
2066        let mut new = old.clone();
2067
2068        new.set_raw(1, 1, Cell::from_char('X'));
2069        new.set_raw(3, 1, Cell::from_char('Y'));
2070
2071        let diff = BufferDiff::compute(&old, &new);
2072        assert_eq!(diff.len(), 2);
2073        assert!(diff.changes().iter().all(|&(_, y)| y == 1));
2074    }
2075
2076    #[test]
2077    fn clear_retains_capacity_for_reuse() {
2078        let mut diff = BufferDiff::with_capacity(16);
2079        diff.changes.extend_from_slice(&[(0, 0), (1, 0), (2, 0)]);
2080        let capacity = diff.changes.capacity();
2081
2082        diff.clear();
2083
2084        assert!(diff.is_empty());
2085        assert!(diff.changes.capacity() >= capacity);
2086    }
2087
2088    #[test]
2089    #[should_panic(expected = "buffer widths must match")]
2090    fn compute_panics_on_width_mismatch() {
2091        let old = Buffer::new(5, 5);
2092        let new = Buffer::new(4, 5);
2093        let _ = BufferDiff::compute(&old, &new);
2094    }
2095
2096    // =========================================================================
2097    // Block-based Row Scan Tests (bd-4kq0.1.2)
2098    // =========================================================================
2099
2100    #[test]
2101    fn block_scan_alignment_exact_block() {
2102        // Width = 4 (exactly one block, no remainder)
2103        let old = Buffer::new(4, 1);
2104        let mut new = Buffer::new(4, 1);
2105        new.set_raw(2, 0, Cell::from_char('X'));
2106
2107        let diff = BufferDiff::compute(&old, &new);
2108        assert_eq!(diff.len(), 1);
2109        assert_eq!(diff.changes(), &[(2, 0)]);
2110    }
2111
2112    #[test]
2113    fn block_scan_alignment_remainder() {
2114        // Width = 7 (one full block + 3 remainder)
2115        let old = Buffer::new(7, 1);
2116        let mut new = Buffer::new(7, 1);
2117        // Change in full block part
2118        new.set_raw(1, 0, Cell::from_char('A'));
2119        // Change in remainder part
2120        new.set_raw(5, 0, Cell::from_char('B'));
2121        new.set_raw(6, 0, Cell::from_char('C'));
2122
2123        let diff = BufferDiff::compute(&old, &new);
2124        assert_eq!(diff.len(), 3);
2125        assert_eq!(diff.changes(), &[(1, 0), (5, 0), (6, 0)]);
2126    }
2127
2128    #[test]
2129    fn block_scan_single_cell_row() {
2130        // Width = 1 (pure remainder, no full blocks)
2131        let old = Buffer::new(1, 1);
2132        let mut new = Buffer::new(1, 1);
2133        new.set_raw(0, 0, Cell::from_char('X'));
2134
2135        let diff = BufferDiff::compute(&old, &new);
2136        assert_eq!(diff.len(), 1);
2137        assert_eq!(diff.changes(), &[(0, 0)]);
2138    }
2139
2140    #[test]
2141    fn block_scan_two_cell_row() {
2142        // Width = 2 (pure remainder)
2143        let old = Buffer::new(2, 1);
2144        let mut new = Buffer::new(2, 1);
2145        new.set_raw(0, 0, Cell::from_char('A'));
2146        new.set_raw(1, 0, Cell::from_char('B'));
2147
2148        let diff = BufferDiff::compute(&old, &new);
2149        assert_eq!(diff.len(), 2);
2150        assert_eq!(diff.changes(), &[(0, 0), (1, 0)]);
2151    }
2152
2153    #[test]
2154    fn block_scan_three_cell_row() {
2155        // Width = 3 (pure remainder)
2156        let old = Buffer::new(3, 1);
2157        let mut new = Buffer::new(3, 1);
2158        new.set_raw(2, 0, Cell::from_char('X'));
2159
2160        let diff = BufferDiff::compute(&old, &new);
2161        assert_eq!(diff.len(), 1);
2162        assert_eq!(diff.changes(), &[(2, 0)]);
2163    }
2164
2165    #[test]
2166    fn block_scan_multiple_blocks_sparse() {
2167        // Width = 80 (20 full blocks), changes scattered across blocks
2168        let old = Buffer::new(80, 1);
2169        let mut new = Buffer::new(80, 1);
2170
2171        // One change per block in every other block
2172        for block in (0..20).step_by(2) {
2173            let x = (block * 4 + 1) as u16;
2174            new.set_raw(x, 0, Cell::from_char('X'));
2175        }
2176
2177        let diff = BufferDiff::compute(&old, &new);
2178        assert_eq!(diff.len(), 10);
2179        assert_eq!(
2180            diff.changes(),
2181            &[
2182                (1, 0),
2183                (9, 0),
2184                (17, 0),
2185                (25, 0),
2186                (33, 0),
2187                (41, 0),
2188                (49, 0),
2189                (57, 0),
2190                (65, 0),
2191                (73, 0)
2192            ]
2193        );
2194    }
2195
2196    #[test]
2197    fn block_scan_full_block_unchanged_skip() {
2198        // Verify blocks with no changes are skipped efficiently
2199        let old = Buffer::new(20, 1);
2200        let mut new = Buffer::new(20, 1);
2201
2202        // Only change one cell in the last block
2203        new.set_raw(19, 0, Cell::from_char('Z'));
2204
2205        let diff = BufferDiff::compute(&old, &new);
2206        assert_eq!(diff.len(), 1);
2207        assert_eq!(diff.changes(), &[(19, 0)]);
2208    }
2209
2210    #[test]
2211    fn block_scan_wide_row_all_changed() {
2212        // All cells changed in a wide row
2213        let old = Buffer::new(120, 1);
2214        let mut new = Buffer::new(120, 1);
2215        for x in 0..120 {
2216            new.set_raw(x, 0, Cell::from_char('#'));
2217        }
2218
2219        let diff = BufferDiff::compute(&old, &new);
2220        assert_eq!(diff.len(), 120);
2221    }
2222
2223    #[test]
2224    fn perf_block_scan_vs_scalar_baseline() {
2225        // Verify that block scan works correctly on large buffers
2226        // and measure relative performance with structured diagnostics.
2227        use std::time::Instant;
2228
2229        let width = 200u16;
2230        let height = 50u16;
2231        let old = Buffer::new(width, height);
2232        let mut new = Buffer::new(width, height);
2233
2234        // ~10% cells changed
2235        for i in 0..1000 {
2236            let x = (i * 7 + 3) as u16 % width;
2237            let y = (i * 11 + 5) as u16 % height;
2238            let ch = char::from_u32(('A' as u32) + (i as u32 % 26)).unwrap();
2239            new.set_raw(x, y, Cell::from_char(ch));
2240        }
2241
2242        let iterations = 1000u32;
2243        let samples = std::env::var("FTUI_DIFF_BLOCK_SAMPLES")
2244            .ok()
2245            .and_then(|value| value.parse::<usize>().ok())
2246            .unwrap_or(50)
2247            .clamp(1, iterations as usize);
2248        let iters_per_sample = (iterations / samples as u32).max(1) as u64;
2249
2250        let mut times_us = Vec::with_capacity(samples);
2251        let mut last_checksum = 0u64;
2252
2253        for _ in 0..samples {
2254            let start = Instant::now();
2255            for _ in 0..iters_per_sample {
2256                let diff = BufferDiff::compute(&old, &new);
2257                assert!(!diff.is_empty());
2258                last_checksum = fnv1a_hash(diff.changes());
2259            }
2260            let elapsed = start.elapsed();
2261            let per_iter = (elapsed.as_micros() as u64) / iters_per_sample;
2262            times_us.push(per_iter);
2263        }
2264
2265        times_us.sort_unstable();
2266        let len = times_us.len();
2267        let p50 = times_us[len / 2];
2268        let p95 = times_us[((len as f64 * 0.95) as usize).min(len.saturating_sub(1))];
2269        let p99 = times_us[((len as f64 * 0.99) as usize).min(len.saturating_sub(1))];
2270        let mean = times_us
2271            .iter()
2272            .copied()
2273            .map(|value| value as f64)
2274            .sum::<f64>()
2275            / len as f64;
2276        let variance = times_us
2277            .iter()
2278            .map(|value| {
2279                let delta = *value as f64 - mean;
2280                delta * delta
2281            })
2282            .sum::<f64>()
2283            / len as f64;
2284
2285        // JSONL log line for perf diagnostics (captured by --nocapture/CI artifacts).
2286        eprintln!(
2287            "{{\"ts\":\"2026-02-04T00:00:00Z\",\"event\":\"block_scan_baseline\",\"width\":{},\"height\":{},\"samples\":{},\"iters_per_sample\":{},\"p50_us\":{},\"p95_us\":{},\"p99_us\":{},\"mean_us\":{:.2},\"variance_us\":{:.2},\"checksum\":\"0x{:016x}\"}}",
2288            width, height, samples, iters_per_sample, p50, p95, p99, mean, variance, last_checksum
2289        );
2290
2291        // Perf tests are inherently noisy on shared runners (OS scheduling, IO, contention).
2292        // We enforce a strict median budget (typical performance) and a looser tail budget
2293        // to avoid flaking on incidental pauses.
2294        #[allow(unexpected_cfgs)]
2295        let p50_budget_us = if is_coverage_run() { 3_000u64 } else { 500u64 };
2296        #[allow(unexpected_cfgs)]
2297        let p95_budget_us = if is_coverage_run() {
2298            10_000u64
2299        } else {
2300            2_500u64
2301        };
2302
2303        assert!(
2304            p50 <= p50_budget_us,
2305            "Diff too slow: p50={p50}µs (budget {p50_budget_us}µs) for {width}x{height}"
2306        );
2307        assert!(
2308            p95 <= p95_budget_us,
2309            "Diff tail too slow: p95={p95}µs (budget {p95_budget_us}µs) for {width}x{height}"
2310        );
2311    }
2312    // =========================================================================
2313    // Run Coalescing Invariants (bd-4kq0.1.3)
2314    // =========================================================================
2315
2316    #[test]
2317    fn unit_run_coalescing_invariants() {
2318        // Verify runs preserve order, coverage, and contiguity for a
2319        // complex multi-row change pattern.
2320        let old = Buffer::new(80, 24);
2321        let mut new = Buffer::new(80, 24);
2322
2323        // Row 0: two separate runs (0-2) and (10-12)
2324        for x in 0..=2 {
2325            new.set_raw(x, 0, Cell::from_char('A'));
2326        }
2327        for x in 10..=12 {
2328            new.set_raw(x, 0, Cell::from_char('B'));
2329        }
2330        // Row 5: single run (40-45)
2331        for x in 40..=45 {
2332            new.set_raw(x, 5, Cell::from_char('C'));
2333        }
2334        // Row 23: single cell at end
2335        new.set_raw(79, 23, Cell::from_char('Z'));
2336
2337        let diff = BufferDiff::compute(&old, &new);
2338        let runs = diff.runs();
2339
2340        // Invariant 1: runs are sorted by (y, x0)
2341        for w in runs.windows(2) {
2342            assert!(
2343                (w[0].y, w[0].x0) < (w[1].y, w[1].x0),
2344                "runs must be sorted: {:?} should precede {:?}",
2345                w[0],
2346                w[1]
2347            );
2348        }
2349
2350        // Invariant 2: total cells in runs == diff.len()
2351        let total_cells: usize = runs.iter().map(|r| r.len()).sum();
2352        assert_eq!(
2353            total_cells,
2354            diff.len(),
2355            "runs must cover all changes exactly"
2356        );
2357
2358        // Invariant 3: no two runs on the same row are adjacent (should have merged)
2359        for w in runs.windows(2) {
2360            if w[0].y == w[1].y {
2361                assert!(
2362                    w[1].x0 > w[0].x1.saturating_add(1),
2363                    "adjacent runs on same row should be merged: {:?} and {:?}",
2364                    w[0],
2365                    w[1]
2366                );
2367            }
2368        }
2369
2370        // Invariant 4: expected structure
2371        assert_eq!(runs.len(), 4);
2372        assert_eq!(runs[0], ChangeRun::new(0, 0, 2));
2373        assert_eq!(runs[1], ChangeRun::new(0, 10, 12));
2374        assert_eq!(runs[2], ChangeRun::new(5, 40, 45));
2375        assert_eq!(runs[3], ChangeRun::new(23, 79, 79));
2376    }
2377
2378    // =========================================================================
2379    // Golden Output Fixtures (bd-4kq0.1.3)
2380    // =========================================================================
2381
2382    /// FNV-1a hash for deterministic checksums (no external dependency).
2383    fn fnv1a_hash(data: &[(u16, u16)]) -> u64 {
2384        let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
2385        for &(x, y) in data {
2386            for byte in x.to_le_bytes().iter().chain(y.to_le_bytes().iter()) {
2387                hash ^= *byte as u64;
2388                hash = hash.wrapping_mul(0x0100_0000_01b3);
2389            }
2390        }
2391        hash
2392    }
2393
2394    /// Build a canonical "dashboard-like" scene: header row, status bar,
2395    /// scattered content cells.
2396    fn build_golden_scene(width: u16, height: u16, seed: u64) -> Buffer {
2397        let mut buf = Buffer::new(width, height);
2398        let mut rng = seed;
2399
2400        // Header row: all cells set
2401        for x in 0..width {
2402            buf.set_raw(x, 0, Cell::from_char('='));
2403        }
2404
2405        // Status bar (last row)
2406        for x in 0..width {
2407            buf.set_raw(x, height - 1, Cell::from_char('-'));
2408        }
2409
2410        // Scattered content using simple LCG
2411        let count = (width as u64 * height as u64 / 10).max(5);
2412        for _ in 0..count {
2413            rng = rng.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
2414            let x = ((rng >> 16) as u16) % width;
2415            rng = rng.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
2416            let y = ((rng >> 16) as u16) % height;
2417            rng = rng.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
2418            let ch = char::from_u32('A' as u32 + (rng % 26) as u32).unwrap();
2419            buf.set_raw(x, y, Cell::from_char(ch));
2420        }
2421
2422        buf
2423    }
2424
2425    #[test]
2426    fn golden_diff_80x24() {
2427        let old = Buffer::new(80, 24);
2428        let new = build_golden_scene(80, 24, 0x000D_01DE_5EED_0001);
2429
2430        let diff = BufferDiff::compute(&old, &new);
2431        let checksum = fnv1a_hash(diff.changes());
2432
2433        // Verify determinism: same inputs → same output
2434        let diff2 = BufferDiff::compute(&old, &new);
2435        assert_eq!(
2436            fnv1a_hash(diff2.changes()),
2437            checksum,
2438            "diff must be deterministic"
2439        );
2440
2441        // Sanity: scene has header + status + scattered content
2442        assert!(
2443            diff.len() >= 160,
2444            "80x24 golden scene should have at least 160 changes (header+status), got {}",
2445            diff.len()
2446        );
2447
2448        let runs = diff.runs();
2449        // Header and status rows should each be one run
2450        assert_eq!(runs[0].y, 0, "first run should be header row");
2451        assert_eq!(runs[0].x0, 0);
2452        assert_eq!(runs[0].x1, 79);
2453        assert!(
2454            runs.last().unwrap().y == 23,
2455            "last row should contain status bar"
2456        );
2457    }
2458
2459    #[test]
2460    fn golden_diff_120x40() {
2461        let old = Buffer::new(120, 40);
2462        let new = build_golden_scene(120, 40, 0x000D_01DE_5EED_0002);
2463
2464        let diff = BufferDiff::compute(&old, &new);
2465        let checksum = fnv1a_hash(diff.changes());
2466
2467        // Determinism
2468        let diff2 = BufferDiff::compute(&old, &new);
2469        assert_eq!(fnv1a_hash(diff2.changes()), checksum);
2470
2471        // Sanity
2472        assert!(
2473            diff.len() >= 240,
2474            "120x40 golden scene should have >=240 changes, got {}",
2475            diff.len()
2476        );
2477
2478        // Dirty diff must match
2479        let dirty = BufferDiff::compute_dirty(&old, &new);
2480        assert_eq!(
2481            fnv1a_hash(dirty.changes()),
2482            checksum,
2483            "dirty diff must produce identical changes"
2484        );
2485    }
2486
2487    #[test]
2488    fn golden_sparse_update() {
2489        // Start from a populated scene, apply a small update
2490        let old = build_golden_scene(80, 24, 0x000D_01DE_5EED_0003);
2491        let mut new = old.clone();
2492
2493        // Apply 5 deterministic changes
2494        new.set_raw(10, 5, Cell::from_char('!'));
2495        new.set_raw(11, 5, Cell::from_char('@'));
2496        new.set_raw(40, 12, Cell::from_char('#'));
2497        new.set_raw(70, 20, Cell::from_char('$'));
2498        new.set_raw(0, 23, Cell::from_char('%'));
2499
2500        let diff = BufferDiff::compute(&old, &new);
2501        let checksum = fnv1a_hash(diff.changes());
2502
2503        // Determinism
2504        let diff2 = BufferDiff::compute(&old, &new);
2505        assert_eq!(fnv1a_hash(diff2.changes()), checksum);
2506
2507        // Exactly 5 changes (or fewer if some cells happened to already have that value)
2508        assert!(
2509            diff.len() <= 5,
2510            "sparse update should have <=5 changes, got {}",
2511            diff.len()
2512        );
2513        assert!(
2514            diff.len() >= 3,
2515            "sparse update should have >=3 changes, got {}",
2516            diff.len()
2517        );
2518    }
2519
2520    // =========================================================================
2521    // E2E Random Scene Replay (bd-4kq0.1.3)
2522    // =========================================================================
2523
2524    #[test]
2525    fn e2e_random_scene_replay() {
2526        // 10 frames of seeded scene evolution, verify checksums are
2527        // deterministic across replays and dirty/full paths agree.
2528        let width = 80u16;
2529        let height = 24u16;
2530        let base_seed: u64 = 0x5C3E_E3E1_A442u64;
2531
2532        let mut checksums = Vec::new();
2533
2534        for frame in 0..10u64 {
2535            let seed = base_seed.wrapping_add(frame.wrapping_mul(0x9E37_79B9_7F4A_7C15));
2536            let old = build_golden_scene(width, height, seed);
2537            let new = build_golden_scene(width, height, seed.wrapping_add(1));
2538
2539            let diff = BufferDiff::compute(&old, &new);
2540            let dirty_diff = BufferDiff::compute_dirty(&old, &new);
2541
2542            // Full and dirty must agree
2543            assert_eq!(
2544                diff.changes(),
2545                dirty_diff.changes(),
2546                "frame {frame}: dirty diff must match full diff"
2547            );
2548
2549            checksums.push(fnv1a_hash(diff.changes()));
2550        }
2551
2552        // Replay: same seeds must produce identical checksums
2553        for frame in 0..10u64 {
2554            let seed = base_seed.wrapping_add(frame.wrapping_mul(0x9E37_79B9_7F4A_7C15));
2555            let old = build_golden_scene(width, height, seed);
2556            let new = build_golden_scene(width, height, seed.wrapping_add(1));
2557
2558            let diff = BufferDiff::compute(&old, &new);
2559            assert_eq!(
2560                fnv1a_hash(diff.changes()),
2561                checksums[frame as usize],
2562                "frame {frame}: checksum mismatch on replay"
2563            );
2564        }
2565    }
2566
2567    // =========================================================================
2568    // Perf Microbench with JSONL (bd-4kq0.1.3)
2569    // =========================================================================
2570
2571    #[test]
2572    fn perf_diff_microbench() {
2573        use std::time::Instant;
2574
2575        let scenarios: &[(u16, u16, &str, u64)] = &[
2576            (80, 24, "full_frame", 0xBE4C_0001u64),
2577            (80, 24, "sparse_update", 0xBE4C_0002u64),
2578            (120, 40, "full_frame", 0xBE4C_0003u64),
2579            (120, 40, "sparse_update", 0xBE4C_0004u64),
2580        ];
2581
2582        let iterations = std::env::var("FTUI_DIFF_BENCH_ITERS")
2583            .ok()
2584            .and_then(|value| value.parse::<u32>().ok())
2585            .unwrap_or(50u32);
2586
2587        for &(width, height, scene_type, seed) in scenarios {
2588            let old = Buffer::new(width, height);
2589            let new = match scene_type {
2590                "full_frame" => build_golden_scene(width, height, seed),
2591                "sparse_update" => {
2592                    let mut buf = old.clone();
2593                    buf.set_raw(10, 5, Cell::from_char('!'));
2594                    buf.set_raw(40, 12, Cell::from_char('#'));
2595                    buf.set_raw(70 % width, 20 % height, Cell::from_char('$'));
2596                    buf
2597                }
2598                _ => unreachable!(),
2599            };
2600
2601            let mut times_us = Vec::with_capacity(iterations as usize);
2602            let mut last_changes = 0usize;
2603            let mut last_runs = 0usize;
2604            let mut last_checksum = 0u64;
2605
2606            for _ in 0..iterations {
2607                let start = Instant::now();
2608                let diff = BufferDiff::compute(&old, &new);
2609                let runs = diff.runs();
2610                let elapsed = start.elapsed();
2611
2612                last_changes = diff.len();
2613                last_runs = runs.len();
2614                last_checksum = fnv1a_hash(diff.changes());
2615                times_us.push(elapsed.as_micros() as u64);
2616            }
2617
2618            times_us.sort();
2619            let len = times_us.len();
2620            let p50 = times_us[len / 2];
2621            let p95 = times_us[((len as f64 * 0.95) as usize).min(len.saturating_sub(1))];
2622            let p99 = times_us[((len as f64 * 0.99) as usize).min(len.saturating_sub(1))];
2623
2624            // JSONL log line (captured by --nocapture or CI artifact)
2625            eprintln!(
2626                "{{\"ts\":\"2026-02-03T00:00:00Z\",\"seed\":{},\"width\":{},\"height\":{},\"scene\":\"{}\",\"changes\":{},\"runs\":{},\"p50_us\":{},\"p95_us\":{},\"p99_us\":{},\"checksum\":\"0x{:016x}\"}}",
2627                seed,
2628                width,
2629                height,
2630                scene_type,
2631                last_changes,
2632                last_runs,
2633                p50,
2634                p95,
2635                p99,
2636                last_checksum
2637            );
2638
2639            // Budget: full 80x24 diff should be < 100µs at p95
2640            // Budget: full 120x40 diff should be < 200µs at p95
2641            let budget_us = match (width, height) {
2642                (80, 24) => 500,   // generous for CI variance
2643                (120, 40) => 1000, // generous for CI variance
2644                _ => 2000,
2645            };
2646
2647            // Checksum must be identical across all iterations (determinism)
2648            for _ in 0..3 {
2649                let diff = BufferDiff::compute(&old, &new);
2650                assert_eq!(
2651                    fnv1a_hash(diff.changes()),
2652                    last_checksum,
2653                    "diff must be deterministic"
2654                );
2655            }
2656
2657            // Soft budget assertion (warn but don't fail on slow CI)
2658            if p95 > budget_us {
2659                eprintln!(
2660                    "WARN: {scene_type} {width}x{height} p95={p95}µs exceeds budget {budget_us}µs"
2661                );
2662            }
2663        }
2664    }
2665
2666    // =========================================================================
2667    // Dirty vs Full Diff Regression Gate (bd-3e1t.1.6)
2668    // =========================================================================
2669
2670    #[test]
2671    fn perf_dirty_diff_large_screen_regression() {
2672        use std::time::Instant;
2673
2674        let iterations = std::env::var("FTUI_DIFF_BENCH_ITERS")
2675            .ok()
2676            .and_then(|value| value.parse::<u32>().ok())
2677            .unwrap_or(50u32);
2678
2679        let max_slowdown = std::env::var("FTUI_DIRTY_DIFF_MAX_SLOWDOWN")
2680            .ok()
2681            .and_then(|value| value.parse::<f64>().ok())
2682            .unwrap_or(2.0);
2683
2684        let cases: &[(u16, u16, &str, f64)] = &[
2685            (200, 60, "sparse_5pct", 5.0),
2686            (240, 80, "sparse_5pct", 5.0),
2687            (200, 60, "single_row", 0.0),
2688            (240, 80, "single_row", 0.0),
2689        ];
2690
2691        for &(width, height, pattern, pct) in cases {
2692            let old = Buffer::new(width, height);
2693            let mut new = old.clone();
2694
2695            if pattern == "single_row" {
2696                for x in 0..width {
2697                    new.set_raw(x, 0, Cell::from_char('X'));
2698                }
2699            } else {
2700                let total = width as usize * height as usize;
2701                let to_change = ((total as f64) * pct / 100.0) as usize;
2702                for i in 0..to_change {
2703                    let x = (i * 7 + 3) as u16 % width;
2704                    let y = (i * 11 + 5) as u16 % height;
2705                    let ch = char::from_u32(('A' as u32) + (i as u32 % 26)).unwrap();
2706                    new.set_raw(x, y, Cell::from_char(ch));
2707                }
2708            }
2709
2710            // Sanity: dirty and full diffs must agree.
2711            let full = BufferDiff::compute(&old, &new);
2712            let dirty = BufferDiff::compute_dirty(&old, &new);
2713            let change_count = full.len();
2714            let dirty_rows = new.dirty_row_count();
2715            assert_eq!(
2716                full.changes(),
2717                dirty.changes(),
2718                "dirty diff must match full diff for {width}x{height} {pattern}"
2719            );
2720
2721            let mut full_times = Vec::with_capacity(iterations as usize);
2722            let mut dirty_times = Vec::with_capacity(iterations as usize);
2723
2724            for _ in 0..iterations {
2725                let start = Instant::now();
2726                let diff = BufferDiff::compute(&old, &new);
2727                std::hint::black_box(diff.len());
2728                full_times.push(start.elapsed().as_micros() as u64);
2729
2730                let start = Instant::now();
2731                let diff = BufferDiff::compute_dirty(&old, &new);
2732                std::hint::black_box(diff.len());
2733                dirty_times.push(start.elapsed().as_micros() as u64);
2734            }
2735
2736            full_times.sort();
2737            dirty_times.sort();
2738
2739            let len = full_times.len();
2740            let p50_idx = len / 2;
2741            let p95_idx = ((len as f64 * 0.95) as usize).min(len.saturating_sub(1));
2742
2743            let full_p50 = full_times[p50_idx];
2744            let full_p95 = full_times[p95_idx];
2745            let dirty_p50 = dirty_times[p50_idx];
2746            let dirty_p95 = dirty_times[p95_idx];
2747
2748            let denom = full_p50.max(1) as f64;
2749            let ratio = dirty_p50 as f64 / denom;
2750
2751            eprintln!(
2752                "{{\"ts\":\"2026-02-03T00:00:00Z\",\"event\":\"diff_regression\",\"width\":{},\"height\":{},\"pattern\":\"{}\",\"iterations\":{},\"changes\":{},\"dirty_rows\":{},\"full_p50_us\":{},\"full_p95_us\":{},\"dirty_p50_us\":{},\"dirty_p95_us\":{},\"slowdown_ratio\":{:.3},\"max_slowdown\":{}}}",
2753                width,
2754                height,
2755                pattern,
2756                iterations,
2757                change_count,
2758                dirty_rows,
2759                full_p50,
2760                full_p95,
2761                dirty_p50,
2762                dirty_p95,
2763                ratio,
2764                max_slowdown
2765            );
2766
2767            assert!(
2768                ratio <= max_slowdown,
2769                "dirty diff regression: {width}x{height} {pattern} ratio {ratio:.2} exceeds {max_slowdown}"
2770            );
2771        }
2772    }
2773
2774    #[test]
2775    fn tile_diff_matches_compute_for_sparse_tiles() {
2776        let width = 200;
2777        let height = 60;
2778        let old = Buffer::new(width, height);
2779        let mut new = old.clone();
2780
2781        new.clear_dirty();
2782        for x in 0..10u16 {
2783            new.set_raw(x, 0, Cell::from_char('X'));
2784        }
2785
2786        let full = BufferDiff::compute(&old, &new);
2787        let dirty = BufferDiff::compute_dirty(&old, &new);
2788
2789        assert_eq!(full.changes(), dirty.changes());
2790        let stats = dirty
2791            .last_tile_stats()
2792            .expect("tile stats should be recorded");
2793        assert!(
2794            stats.fallback.is_none(),
2795            "tile path should be used for sparse tiles"
2796        );
2797    }
2798
2799    fn make_dirty_buffer(width: u16, height: u16, changes: &[(u16, u16, char)]) -> Buffer {
2800        let mut buffer = Buffer::new(width, height);
2801        buffer.clear_dirty();
2802        for &(x, y, ch) in changes {
2803            buffer.set_raw(x, y, Cell::from_char(ch));
2804        }
2805        buffer
2806    }
2807
2808    fn tile_stats_for_config(old: &Buffer, new: &Buffer, config: TileDiffConfig) -> TileDiffStats {
2809        let mut diff = BufferDiff::new();
2810        *diff.tile_config_mut() = config;
2811        diff.compute_dirty_into(old, new);
2812        diff.last_tile_stats()
2813            .expect("tile stats should be recorded")
2814    }
2815
2816    #[test]
2817    fn tile_fallback_disabled_when_config_off() {
2818        let width = 64;
2819        let height = 32;
2820        let old = Buffer::new(width, height);
2821        let new = make_dirty_buffer(width, height, &[(0, 0, 'X')]);
2822
2823        let config = TileDiffConfig {
2824            enabled: false,
2825            min_cells_for_tiles: 0,
2826            dense_cell_ratio: 1.1,
2827            dense_tile_ratio: 1.1,
2828            max_tiles: usize::MAX,
2829            ..Default::default()
2830        };
2831
2832        let stats = tile_stats_for_config(&old, &new, config);
2833        assert_eq!(stats.fallback, Some(TileDiffFallback::Disabled));
2834    }
2835
2836    #[test]
2837    fn tile_fallback_small_screen_when_below_threshold() {
2838        let width = 64;
2839        let height = 32;
2840        let old = Buffer::new(width, height);
2841        let new = make_dirty_buffer(width, height, &[(1, 2, 'Y')]);
2842
2843        let config = TileDiffConfig {
2844            enabled: true,
2845            min_cells_for_tiles: width as usize * height as usize + 1,
2846            dense_cell_ratio: 1.1,
2847            dense_tile_ratio: 1.1,
2848            max_tiles: usize::MAX,
2849            ..Default::default()
2850        };
2851
2852        let stats = tile_stats_for_config(&old, &new, config);
2853        assert_eq!(stats.fallback, Some(TileDiffFallback::SmallScreen));
2854    }
2855
2856    #[test]
2857    fn tile_fallback_too_many_tiles_when_budget_exceeded() {
2858        let width = 64;
2859        let height = 64;
2860        let old = Buffer::new(width, height);
2861        let new = make_dirty_buffer(width, height, &[(2, 3, 'Z')]);
2862
2863        let config = TileDiffConfig {
2864            enabled: true,
2865            tile_w: 8,
2866            tile_h: 8,
2867            skip_clean_rows: true,
2868            min_cells_for_tiles: 0,
2869            dense_cell_ratio: 1.1,
2870            dense_tile_ratio: 1.1,
2871            max_tiles: 4,
2872        };
2873
2874        let stats = tile_stats_for_config(&old, &new, config);
2875        assert_eq!(stats.fallback, Some(TileDiffFallback::TooManyTiles));
2876    }
2877
2878    #[test]
2879    fn tile_fallback_dense_tiles_when_ratio_exceeded() {
2880        let width = 64;
2881        let height = 32;
2882        let old = Buffer::new(width, height);
2883        let new = make_dirty_buffer(width, height, &[(0, 0, 'A'), (24, 0, 'B')]);
2884
2885        let config = TileDiffConfig {
2886            enabled: true,
2887            tile_w: 8,
2888            tile_h: 8,
2889            skip_clean_rows: true,
2890            min_cells_for_tiles: 0,
2891            dense_cell_ratio: 1.1,
2892            dense_tile_ratio: 0.05,
2893            max_tiles: usize::MAX / 4,
2894        };
2895
2896        let stats = tile_stats_for_config(&old, &new, config);
2897        assert_eq!(stats.fallback, Some(TileDiffFallback::DenseTiles));
2898    }
2899
2900    #[test]
2901    fn tile_builder_skips_clean_rows_when_enabled() {
2902        let width = 200;
2903        let height = 60;
2904        let old = Buffer::new(width, height);
2905        let mut new = old.clone();
2906        new.clear_dirty();
2907        new.set_raw(3, 0, Cell::from_char('X'));
2908        new.set_raw(4, 10, Cell::from_char('Y'));
2909
2910        let base = TileDiffConfig {
2911            enabled: true,
2912            tile_w: 16,
2913            tile_h: 8,
2914            min_cells_for_tiles: 0,
2915            dense_cell_ratio: 1.1,
2916            dense_tile_ratio: 1.1,
2917            max_tiles: usize::MAX,
2918            ..Default::default()
2919        };
2920        let config_full = TileDiffConfig {
2921            skip_clean_rows: false,
2922            ..base.clone()
2923        };
2924        let config_skip = TileDiffConfig {
2925            skip_clean_rows: true,
2926            ..base
2927        };
2928
2929        let stats_full = tile_stats_for_config(&old, &new, config_full);
2930        let stats_skip = tile_stats_for_config(&old, &new, config_skip);
2931
2932        // Invariant: full scan processes some cells
2933        assert!(
2934            stats_full.sat_build_cells > 0,
2935            "full scan should process cells, got 0"
2936        );
2937        // Invariant: skip optimization actually reduces work
2938        assert!(
2939            stats_skip.sat_build_cells < stats_full.sat_build_cells,
2940            "skip_clean_rows should process fewer cells than full scan: skip={} full={}",
2941            stats_skip.sat_build_cells,
2942            stats_full.sat_build_cells
2943        );
2944        // Invariant: the savings are meaningful (at least 50% reduction)
2945        // With only 2 dirty rows out of 60, skipping should save substantially
2946        assert!(
2947            stats_skip.sat_build_cells <= stats_full.sat_build_cells / 2,
2948            "skip_clean_rows should save at least 50%: skip={} full={}",
2949            stats_skip.sat_build_cells,
2950            stats_full.sat_build_cells
2951        );
2952    }
2953
2954    fn lcg_next(state: &mut u64) -> u64 {
2955        *state = state
2956            .wrapping_mul(6364136223846793005)
2957            .wrapping_add(1442695040888963407);
2958        *state
2959    }
2960
2961    fn apply_random_changes(buf: &mut Buffer, seed: u64, count: usize) {
2962        let width = buf.width().max(1) as u64;
2963        let height = buf.height().max(1) as u64;
2964        let mut state = seed;
2965        for i in 0..count {
2966            let v = lcg_next(&mut state);
2967            let x = (v % width) as u16;
2968            let y = ((v >> 32) % height) as u16;
2969            let ch = char::from_u32(('A' as u32) + ((i as u32) % 26)).unwrap();
2970            buf.set_raw(x, y, Cell::from_char(ch));
2971        }
2972    }
2973
2974    fn tile_diag(stats: &TileDiffStats) -> String {
2975        let tile_size = stats.tile_w as usize * stats.tile_h as usize;
2976        format!(
2977            "tile_size={tile_size}, dirty_tiles={}, skipped_tiles={}, dirty_cells={}, dirty_tile_ratio={:.3}, dirty_cell_ratio={:.3}, scanned_tiles={}, fallback={:?}",
2978            stats.dirty_tiles,
2979            stats.skipped_tiles,
2980            stats.dirty_cells,
2981            stats.dirty_tile_ratio,
2982            stats.dirty_cell_ratio,
2983            stats.scanned_tiles,
2984            stats.fallback
2985        )
2986    }
2987
2988    fn diff_with_forced_tiles(old: &Buffer, new: &Buffer) -> (BufferDiff, TileDiffStats) {
2989        let mut diff = BufferDiff::new();
2990        {
2991            let config = diff.tile_config_mut();
2992            config.enabled = true;
2993            config.tile_w = 8;
2994            config.tile_h = 8;
2995            config.min_cells_for_tiles = 0;
2996            config.dense_cell_ratio = 1.1;
2997            config.dense_tile_ratio = 1.1;
2998            config.max_tiles = usize::MAX / 4;
2999        }
3000        diff.compute_dirty_into(old, new);
3001        let stats = diff
3002            .last_tile_stats()
3003            .expect("tile stats should be recorded");
3004        (diff, stats)
3005    }
3006
3007    fn assert_tile_diff_equivalence(old: &Buffer, new: &Buffer, label: &str) {
3008        let full = BufferDiff::compute(old, new);
3009        let (dirty, stats) = diff_with_forced_tiles(old, new);
3010        let diag = tile_diag(&stats);
3011        assert!(
3012            stats.fallback.is_none(),
3013            "tile diff fallback ({label}) {w}x{h}: {diag}",
3014            w = old.width(),
3015            h = old.height()
3016        );
3017        assert!(
3018            full.changes() == dirty.changes(),
3019            "tile diff mismatch ({label}) {w}x{h}: {diag}",
3020            w = old.width(),
3021            h = old.height()
3022        );
3023    }
3024
3025    #[test]
3026    fn tile_diff_equivalence_small_and_odd_sizes() {
3027        let cases: &[(u16, u16, usize)] = &[
3028            (1, 1, 1),
3029            (2, 1, 1),
3030            (1, 2, 1),
3031            (5, 3, 4),
3032            (7, 13, 12),
3033            (15, 9, 20),
3034            (31, 5, 12),
3035        ];
3036
3037        for (idx, &(width, height, changes)) in cases.iter().enumerate() {
3038            let old = Buffer::new(width, height);
3039            let mut new = old.clone();
3040            new.clear_dirty();
3041            apply_random_changes(&mut new, 0xC0FFEE_u64 + idx as u64, changes);
3042            assert_tile_diff_equivalence(&old, &new, "small_odd");
3043        }
3044    }
3045
3046    #[test]
3047    fn tile_diff_equivalence_large_sparse_random() {
3048        let cases: &[(u16, u16)] = &[(200, 60), (240, 80)];
3049        for (idx, &(width, height)) in cases.iter().enumerate() {
3050            let old = Buffer::new(width, height);
3051            let mut new = old.clone();
3052            new.clear_dirty();
3053            let total = width as usize * height as usize;
3054            let changes = (total / 100).max(1);
3055            apply_random_changes(&mut new, 0xDEADBEEF_u64 + idx as u64, changes);
3056            assert_tile_diff_equivalence(&old, &new, "large_sparse");
3057        }
3058    }
3059
3060    #[test]
3061    fn row_prefilter_skips_clean_tile_rows() {
3062        // 200x60 with 8x8 tiles => 25 x 8 tiles. Concentrate every change in
3063        // tile row 3 (buffer rows 24..32), across three distinct tile columns.
3064        // The SAT row prefilter must retire the other seven tile rows with one
3065        // subtraction each and never touch their buffer rows.
3066        let old = Buffer::new(200, 60);
3067        let new = make_dirty_buffer(200, 60, &[(0, 24, 'A'), (8, 25, 'B'), (16, 26, 'C')]);
3068        let (dirty, stats) = diff_with_forced_tiles(&old, &new);
3069
3070        assert_eq!(stats.fallback, None, "{}", tile_diag(&stats));
3071        assert_eq!(stats.tiles_y, 8, "eight tile rows at 8px tall over 60 rows");
3072        assert_eq!(stats.sat_queries, 8, "one SAT row-sum query per tile row");
3073        assert_eq!(
3074            stats.skipped_tile_rows,
3075            7,
3076            "seven clean tile rows retired by the SAT: {}",
3077            tile_diag(&stats)
3078        );
3079        assert_eq!(
3080            stats.scanned_tiles, 3,
3081            "three distinct dirty tiles, all in tile row 3"
3082        );
3083
3084        // The prefilter changes performance, never output.
3085        let full = BufferDiff::compute(&old, &new);
3086        assert_eq!(full.changes(), dirty.changes());
3087    }
3088
3089    mod sat_prefilter_props {
3090        use super::*;
3091        use proptest::prelude::*;
3092
3093        const W: u16 = 200;
3094        const H: u16 = 60;
3095
3096        fn forced_tile_config() -> TileDiffConfig {
3097            TileDiffConfig {
3098                enabled: true,
3099                tile_w: 8,
3100                tile_h: 8,
3101                min_cells_for_tiles: 0,
3102                dense_cell_ratio: 1.1,
3103                dense_tile_ratio: 1.1,
3104                max_tiles: usize::MAX / 4,
3105                ..Default::default()
3106            }
3107        }
3108
3109        /// Build the tile plan for `new` and hand it to `f`. The SAT query
3110        /// methods are read-only, so a borrowed plan is all they need.
3111        fn with_forced_plan<R>(new: &Buffer, f: impl FnOnce(&TileDiffPlan<'_>) -> R) -> R {
3112            let mut builder = TileDiffBuilder::new();
3113            let config = forced_tile_config();
3114            match builder.build_from_buffer(&config, new) {
3115                TileDiffBuild::UseTiles(plan) => f(&plan),
3116                TileDiffBuild::Fallback(stats) => {
3117                    panic!("expected the tile path, got fallback {:?}", stats.fallback)
3118                }
3119            }
3120        }
3121
3122        fn naive_row_sum(plan: &TileDiffPlan<'_>, ty: usize) -> u32 {
3123            let tiles_x = plan.params.tiles_x;
3124            (0..tiles_x)
3125                .map(|tx| plan.tile_counts[ty * tiles_x + tx])
3126                .sum()
3127        }
3128
3129        fn naive_rect_sum(
3130            plan: &TileDiffPlan<'_>,
3131            tx0: usize,
3132            ty0: usize,
3133            tx1: usize,
3134            ty1: usize,
3135        ) -> u32 {
3136            let tiles_x = plan.params.tiles_x;
3137            let mut sum = 0u32;
3138            for ty in ty0..ty1 {
3139                for tx in tx0..tx1 {
3140                    sum += plan.tile_counts[ty * tiles_x + tx];
3141                }
3142            }
3143            sum
3144        }
3145
3146        fn dirty_cells() -> impl Strategy<Value = Vec<(u16, u16, char)>> {
3147            prop::collection::vec((0u16..W, 0u16..H).prop_map(|(x, y)| (x, y, 'X')), 0..40)
3148        }
3149
3150        proptest! {
3151            #![proptest_config(ProptestConfig::with_cases(512))]
3152
3153            /// The SAT row-sum query equals a direct sum over the tile-count row.
3154            #[test]
3155            fn tile_row_dirty_matches_naive_sum(cells in dirty_cells()) {
3156                let new = make_dirty_buffer(W, H, &cells);
3157                with_forced_plan(&new, |plan| -> Result<(), TestCaseError> {
3158                    for ty in 0..plan.params.tiles_y {
3159                        prop_assert_eq!(
3160                            plan.tile_row_dirty(ty),
3161                            naive_row_sum(plan, ty),
3162                            "row {}",
3163                            ty
3164                        );
3165                    }
3166                    // Out-of-range rows read as zero.
3167                    prop_assert_eq!(plan.tile_row_dirty(plan.params.tiles_y), 0);
3168                    Ok(())
3169                })?;
3170            }
3171
3172            /// The four-corner SAT rectangle query equals a direct sum over the
3173            /// tile-count block, for arbitrary (including empty) rectangles.
3174            #[test]
3175            fn rect_dirty_matches_naive_sum(
3176                cells in dirty_cells(),
3177                tx0 in 0usize..25,
3178                txw in 0usize..26,
3179                ty0 in 0usize..8,
3180                tyw in 0usize..9,
3181            ) {
3182                let new = make_dirty_buffer(W, H, &cells);
3183                with_forced_plan(&new, |plan| -> Result<(), TestCaseError> {
3184                    let tiles_x = plan.params.tiles_x;
3185                    let tiles_y = plan.params.tiles_y;
3186                    let tx1 = (tx0 + txw).min(tiles_x);
3187                    let ty1 = (ty0 + tyw).min(tiles_y);
3188                    let naive = if tx0 >= tx1 || ty0 >= ty1 {
3189                        0
3190                    } else {
3191                        naive_rect_sum(plan, tx0, ty0, tx1, ty1)
3192                    };
3193                    prop_assert_eq!(plan.rect_dirty(tx0, ty0, tx1, ty1), naive);
3194                    Ok(())
3195                })?;
3196            }
3197        }
3198
3199        proptest! {
3200            #![proptest_config(ProptestConfig::with_cases(1000))]
3201
3202            /// The tile diff with the row prefilter emits exactly the change
3203            /// runs the flat `compute` does: the prefilter is a performance
3204            /// path, never a semantic one.
3205            #[test]
3206            fn diff_output_identical_with_row_prefilter(
3207                cells in prop::collection::vec(
3208                    (0u16..W, 0u16..H).prop_map(|(x, y)| (x, y, 'Z')),
3209                    1..80,
3210                ),
3211            ) {
3212                let old = Buffer::new(W, H);
3213                let new = make_dirty_buffer(W, H, &cells);
3214                let full = BufferDiff::compute(&old, &new);
3215                let (dirty, stats) = diff_with_forced_tiles(&old, &new);
3216                prop_assert!(
3217                    stats.fallback.is_none(),
3218                    "unexpected fallback: {:?}",
3219                    stats.fallback
3220                );
3221                prop_assert_eq!(full.changes(), dirty.changes());
3222            }
3223        }
3224    }
3225
3226    #[test]
3227    fn tile_diff_equivalence_row_and_full_buffer() {
3228        let width = 200u16;
3229        let height = 60u16;
3230        let old = Buffer::new(width, height);
3231
3232        let mut row = old.clone();
3233        row.clear_dirty();
3234        for x in 0..width {
3235            row.set_raw(x, 0, Cell::from_char('R'));
3236        }
3237        assert_tile_diff_equivalence(&old, &row, "single_row");
3238
3239        let mut full = old.clone();
3240        full.clear_dirty();
3241        for y in 0..height {
3242            for x in 0..width {
3243                full.set_raw(x, y, Cell::from_char('F'));
3244            }
3245        }
3246        assert_tile_diff_equivalence(&old, &full, "full_buffer");
3247    }
3248
3249    // =========================================================================
3250    // Edge-Case Tests (bd-27b0k)
3251    // =========================================================================
3252
3253    // --- BufferDiff::full zero/edge dimensions ---
3254
3255    #[test]
3256    fn full_zero_width_returns_empty() {
3257        let diff = BufferDiff::full(0, 10);
3258        assert!(diff.is_empty());
3259    }
3260
3261    #[test]
3262    fn full_zero_height_returns_empty() {
3263        let diff = BufferDiff::full(10, 0);
3264        assert!(diff.is_empty());
3265    }
3266
3267    #[test]
3268    fn full_zero_both_returns_empty() {
3269        let diff = BufferDiff::full(0, 0);
3270        assert!(diff.is_empty());
3271    }
3272
3273    #[test]
3274    fn full_single_cell_has_one_change() {
3275        let diff = BufferDiff::full(1, 1);
3276        assert_eq!(diff.len(), 1);
3277        assert_eq!(diff.changes(), &[(0, 0)]);
3278    }
3279
3280    #[test]
3281    fn full_row_major_order() {
3282        let diff = BufferDiff::full(2, 3);
3283        assert_eq!(
3284            diff.changes(),
3285            &[(0, 0), (1, 0), (0, 1), (1, 1), (0, 2), (1, 2)]
3286        );
3287    }
3288
3289    // --- runs_into ---
3290
3291    #[test]
3292    fn runs_into_matches_runs_output() {
3293        let old = Buffer::new(20, 5);
3294        let mut new = Buffer::new(20, 5);
3295        new.set_raw(0, 0, Cell::from_char('A'));
3296        new.set_raw(1, 0, Cell::from_char('B'));
3297        new.set_raw(5, 2, Cell::from_char('C'));
3298        new.set_raw(10, 4, Cell::from_char('D'));
3299        new.set_raw(11, 4, Cell::from_char('E'));
3300
3301        let diff = BufferDiff::compute(&old, &new);
3302        let runs = diff.runs();
3303        let mut runs_buf = Vec::new();
3304        diff.runs_into(&mut runs_buf);
3305
3306        assert_eq!(runs, runs_buf);
3307    }
3308
3309    #[test]
3310    fn runs_into_clears_previous_content() {
3311        let diff = BufferDiff::new();
3312        let mut out = vec![ChangeRun::new(0, 0, 0)];
3313        diff.runs_into(&mut out);
3314        assert!(out.is_empty());
3315    }
3316
3317    #[test]
3318    fn runs_into_preserves_capacity() {
3319        let old = Buffer::new(10, 2);
3320        let mut new = Buffer::new(10, 2);
3321        new.set_raw(0, 0, Cell::from_char('A'));
3322        let diff = BufferDiff::compute(&old, &new);
3323
3324        let mut out = Vec::with_capacity(64);
3325        diff.runs_into(&mut out);
3326        assert_eq!(out.len(), 1);
3327        assert!(out.capacity() >= 64);
3328    }
3329
3330    // --- ChangeRun ---
3331
3332    #[test]
3333    fn change_run_fields_accessible() {
3334        let run = ChangeRun::new(7, 3, 10);
3335        assert_eq!(run.y, 7);
3336        assert_eq!(run.x0, 3);
3337        assert_eq!(run.x1, 10);
3338        assert_eq!(run.len(), 8);
3339        assert!(!run.is_empty());
3340    }
3341
3342    #[test]
3343    fn change_run_single_cell_not_empty() {
3344        let run = ChangeRun::new(0, 5, 5);
3345        assert_eq!(run.len(), 1);
3346        assert!(!run.is_empty());
3347    }
3348
3349    #[test]
3350    fn change_run_debug_format() {
3351        let run = ChangeRun::new(1, 2, 3);
3352        let dbg = format!("{:?}", run);
3353        assert!(dbg.contains("ChangeRun"), "Debug output: {dbg}");
3354    }
3355
3356    #[test]
3357    fn change_run_clone_copy_eq() {
3358        let run = ChangeRun::new(5, 10, 20);
3359        let copied = run; // Copy
3360        assert_eq!(run, copied);
3361        let cloned: ChangeRun = run; // Copy
3362        assert_eq!(run, cloned);
3363    }
3364
3365    #[test]
3366    fn change_run_ne() {
3367        let a = ChangeRun::new(0, 0, 5);
3368        let b = ChangeRun::new(0, 0, 6);
3369        assert_ne!(a, b);
3370    }
3371
3372    // --- TileDiffConfig ---
3373
3374    #[test]
3375    fn tile_diff_config_default_values() {
3376        let config = TileDiffConfig::default();
3377        assert!(config.enabled);
3378        assert_eq!(config.tile_w, 16);
3379        assert_eq!(config.tile_h, 8);
3380        assert!(config.skip_clean_rows);
3381        assert_eq!(config.min_cells_for_tiles, 12_000);
3382        assert!((config.dense_cell_ratio - 0.25).abs() < f64::EPSILON);
3383        assert!((config.dense_tile_ratio - 0.60).abs() < f64::EPSILON);
3384        assert_eq!(config.max_tiles, 4096);
3385    }
3386
3387    #[test]
3388    fn tile_diff_config_builder_methods() {
3389        let config = TileDiffConfig::default()
3390            .with_enabled(false)
3391            .with_tile_size(32, 32)
3392            .with_min_cells_for_tiles(500)
3393            .with_skip_clean_rows(false)
3394            .with_dense_cell_ratio(0.5)
3395            .with_dense_tile_ratio(0.8)
3396            .with_max_tiles(100);
3397
3398        assert!(!config.enabled);
3399        assert_eq!(config.tile_w, 32);
3400        assert_eq!(config.tile_h, 32);
3401        assert!(!config.skip_clean_rows);
3402        assert_eq!(config.min_cells_for_tiles, 500);
3403        assert!((config.dense_cell_ratio - 0.5).abs() < f64::EPSILON);
3404        assert!((config.dense_tile_ratio - 0.8).abs() < f64::EPSILON);
3405        assert_eq!(config.max_tiles, 100);
3406    }
3407
3408    #[test]
3409    fn tile_diff_config_debug_clone() {
3410        let config = TileDiffConfig::default();
3411        let dbg = format!("{:?}", config);
3412        assert!(dbg.contains("TileDiffConfig"), "Debug: {dbg}");
3413        let cloned = config.clone();
3414        assert_eq!(cloned.tile_w, 16);
3415    }
3416
3417    // --- TileDiffFallback ---
3418
3419    #[test]
3420    fn tile_diff_fallback_as_str_all_variants() {
3421        assert_eq!(TileDiffFallback::Disabled.as_str(), "disabled");
3422        assert_eq!(TileDiffFallback::SmallScreen.as_str(), "small_screen");
3423        assert_eq!(TileDiffFallback::DirtyAll.as_str(), "dirty_all");
3424        assert_eq!(TileDiffFallback::DenseCells.as_str(), "dense_cells");
3425        assert_eq!(TileDiffFallback::DenseTiles.as_str(), "dense_tiles");
3426        assert_eq!(TileDiffFallback::TooManyTiles.as_str(), "too_many_tiles");
3427        assert_eq!(TileDiffFallback::Overflow.as_str(), "overflow");
3428    }
3429
3430    #[test]
3431    fn tile_diff_fallback_traits() {
3432        let a = TileDiffFallback::Disabled;
3433        let b = a; // Copy
3434        assert_eq!(a, b);
3435        let c: TileDiffFallback = a; // Copy
3436        assert_eq!(a, c);
3437        assert_ne!(a, TileDiffFallback::Overflow);
3438        let dbg = format!("{:?}", a);
3439        assert!(dbg.contains("Disabled"), "Debug: {dbg}");
3440    }
3441
3442    // --- TileDiffBuilder direct ---
3443
3444    #[test]
3445    fn sat_overflow_falls_back() {
3446        let mut builder = TileDiffBuilder::new();
3447        let config = TileDiffConfig::default().with_min_cells_for_tiles(0);
3448        let dirty_rows = vec![true; 10];
3449        let dirty_bits = vec![0u8; 100]; // less than 20x10 = 200 total_cells
3450
3451        let input = TileDiffInput {
3452            width: 20,
3453            height: 10,
3454            dirty_rows: &dirty_rows,
3455            dirty_bits: &dirty_bits,
3456            dirty_cells: 0,
3457            dirty_all: false,
3458        };
3459
3460        let result = builder.build(&config, input);
3461        assert!(matches!(
3462            result,
3463            TileDiffBuild::Fallback(stats) if stats.fallback == Some(TileDiffFallback::Overflow)
3464        ));
3465    }
3466
3467    #[test]
3468    fn min_cells_threshold_engages_tiles_exactly_at_12000() {
3469        let config = TileDiffConfig::default();
3470        assert_eq!(config.min_cells_for_tiles, 12_000);
3471
3472        let mut builder = TileDiffBuilder::new();
3473        let dirty_rows = vec![true; 24];
3474        let dirty_bits = vec![0u8; 80 * 24];
3475        let input_small = TileDiffInput {
3476            width: 80,
3477            height: 24,
3478            dirty_rows: &dirty_rows,
3479            dirty_bits: &dirty_bits,
3480            dirty_cells: 5,
3481            dirty_all: false,
3482        };
3483        let result_small = builder.build(&config, input_small);
3484        assert!(matches!(
3485            result_small,
3486            TileDiffBuild::Fallback(stats) if stats.fallback == Some(TileDiffFallback::SmallScreen)
3487        ));
3488
3489        let dirty_rows_large = vec![true; 60];
3490        let mut dirty_bits_large = vec![0u8; 200 * 60];
3491        dirty_bits_large[0] = 1;
3492        let input_large = TileDiffInput {
3493            width: 200,
3494            height: 60,
3495            dirty_rows: &dirty_rows_large,
3496            dirty_bits: &dirty_bits_large,
3497            dirty_cells: 1,
3498            dirty_all: false,
3499        };
3500        let result_large = builder.build(&config, input_large);
3501        assert!(matches!(result_large, TileDiffBuild::UseTiles(_)));
3502    }
3503
3504    #[test]
3505    fn tile_builder_dirty_all_fallback() {
3506        let mut builder = TileDiffBuilder::new();
3507        let config = TileDiffConfig::default().with_min_cells_for_tiles(0);
3508        let dirty_rows = vec![true; 10];
3509        let dirty_bits = vec![1u8; 200]; // 20x10
3510
3511        let input = TileDiffInput {
3512            width: 20,
3513            height: 10,
3514            dirty_rows: &dirty_rows,
3515            dirty_bits: &dirty_bits,
3516            dirty_cells: 200,
3517            dirty_all: true,
3518        };
3519
3520        let result = builder.build(&config, input);
3521        assert!(matches!(
3522            result,
3523            TileDiffBuild::Fallback(stats) if stats.fallback == Some(TileDiffFallback::DirtyAll)
3524        ));
3525    }
3526
3527    #[test]
3528    fn tile_builder_dense_cells_fallback() {
3529        // DenseCells triggers when dirty_cell_ratio >= dense_cell_ratio
3530        let mut builder = TileDiffBuilder::new();
3531        let config = TileDiffConfig::default()
3532            .with_min_cells_for_tiles(0)
3533            .with_dense_cell_ratio(0.10); // 10% threshold
3534
3535        let w = 20u16;
3536        let h = 10u16;
3537        let total = (w as usize) * (h as usize);
3538        let dirty_count = total / 10; // exactly 10%
3539
3540        let dirty_rows = vec![true; h as usize];
3541        let dirty_bits = vec![0u8; total];
3542
3543        let input = TileDiffInput {
3544            width: w,
3545            height: h,
3546            dirty_rows: &dirty_rows,
3547            dirty_bits: &dirty_bits,
3548            dirty_cells: dirty_count,
3549            dirty_all: false,
3550        };
3551
3552        let result = builder.build(&config, input);
3553        assert!(matches!(
3554            result,
3555            TileDiffBuild::Fallback(stats) if stats.fallback == Some(TileDiffFallback::DenseCells)
3556        ));
3557    }
3558
3559    #[test]
3560    fn tile_builder_reuse_across_builds() {
3561        let mut builder = TileDiffBuilder::new();
3562        let config = TileDiffConfig::default()
3563            .with_min_cells_for_tiles(0)
3564            .with_dense_tile_ratio(1.1)
3565            .with_dense_cell_ratio(1.1)
3566            .with_max_tiles(usize::MAX / 4);
3567
3568        // First build: 20x10 with one dirty cell
3569        let dirty_rows_1 = vec![true; 10];
3570        let mut dirty_bits_1 = vec![0u8; 200];
3571        dirty_bits_1[0] = 1;
3572        let input_1 = TileDiffInput {
3573            width: 20,
3574            height: 10,
3575            dirty_rows: &dirty_rows_1,
3576            dirty_bits: &dirty_bits_1,
3577            dirty_cells: 1,
3578            dirty_all: false,
3579        };
3580        let result_1 = builder.build(&config, input_1);
3581        assert!(matches!(result_1, TileDiffBuild::UseTiles(_)));
3582
3583        // Second build: 30x15 with one dirty cell — reuses internal allocations
3584        let dirty_rows_2 = vec![true; 15];
3585        let mut dirty_bits_2 = vec![0u8; 450];
3586        dirty_bits_2[200] = 1;
3587        let input_2 = TileDiffInput {
3588            width: 30,
3589            height: 15,
3590            dirty_rows: &dirty_rows_2,
3591            dirty_bits: &dirty_bits_2,
3592            dirty_cells: 1,
3593            dirty_all: false,
3594        };
3595        let result_2 = builder.build(&config, input_2);
3596        assert!(matches!(result_2, TileDiffBuild::UseTiles(_)));
3597    }
3598
3599    #[test]
3600    fn tile_builder_default_matches_new() {
3601        let from_new = TileDiffBuilder::new();
3602        let from_default = TileDiffBuilder::default();
3603        assert_eq!(format!("{:?}", from_new), format!("{:?}", from_default));
3604    }
3605
3606    // --- TileParams ---
3607
3608    #[test]
3609    fn tile_params_total_tiles_and_cells() {
3610        let params = TileParams {
3611            width: 100,
3612            height: 50,
3613            tile_w: 16,
3614            tile_h: 8,
3615            tiles_x: 7, // ceil(100/16)
3616            tiles_y: 7, // ceil(50/8)
3617        };
3618        assert_eq!(params.total_tiles(), 49);
3619        assert_eq!(params.total_cells(), 5000);
3620    }
3621
3622    // --- TileDiffStats ---
3623
3624    #[test]
3625    fn tile_diff_stats_from_builder() {
3626        let mut builder = TileDiffBuilder::new();
3627        let config = TileDiffConfig::default()
3628            .with_min_cells_for_tiles(0)
3629            .with_dense_tile_ratio(1.1)
3630            .with_dense_cell_ratio(1.1)
3631            .with_max_tiles(usize::MAX / 4);
3632
3633        let w = 32u16;
3634        let h = 16u16;
3635        let dirty_rows = vec![true; h as usize];
3636        let mut dirty_bits = vec![0u8; (w as usize) * (h as usize)];
3637        dirty_bits[0] = 1; // one cell dirty in first tile
3638
3639        let input = TileDiffInput {
3640            width: w,
3641            height: h,
3642            dirty_rows: &dirty_rows,
3643            dirty_bits: &dirty_bits,
3644            dirty_cells: 1,
3645            dirty_all: false,
3646        };
3647
3648        let result = builder.build(&config, input);
3649        match result {
3650            TileDiffBuild::UseTiles(plan) => {
3651                let stats = plan.stats;
3652                assert_eq!(stats.width, w);
3653                assert_eq!(stats.height, h);
3654                // tile_w clamped from 16 → 16 (within [8,64])
3655                assert_eq!(stats.tile_w, 16);
3656                assert_eq!(stats.tile_h, 8);
3657                // tiles_x = ceil(32/16) = 2, tiles_y = ceil(16/8) = 2
3658                assert_eq!(stats.tiles_x, 2);
3659                assert_eq!(stats.tiles_y, 2);
3660                assert_eq!(stats.total_tiles, 4);
3661                assert_eq!(stats.dirty_cells, 1);
3662                assert_eq!(stats.dirty_tiles, 1);
3663                assert_eq!(stats.skipped_tiles, 3);
3664                assert!(stats.fallback.is_none());
3665                // Copy trait works
3666                let copy = stats;
3667                assert_eq!(copy.width, stats.width);
3668            }
3669            _ => unreachable!("expected UseTiles"),
3670        }
3671    }
3672
3673    // --- clamp_tile_size via builder ---
3674
3675    #[test]
3676    fn tile_size_clamped_to_min_8() {
3677        let mut builder = TileDiffBuilder::new();
3678        let config = TileDiffConfig {
3679            enabled: true,
3680            tile_w: 1, // below min 8
3681            tile_h: 0, // below min 8
3682            skip_clean_rows: false,
3683            min_cells_for_tiles: 0,
3684            dense_cell_ratio: 1.1,
3685            dense_tile_ratio: 1.1,
3686            max_tiles: usize::MAX / 4,
3687        };
3688
3689        let dirty_rows = vec![true; 16];
3690        let mut dirty_bits = vec![0u8; 256]; // 16x16
3691        dirty_bits[0] = 1;
3692
3693        let input = TileDiffInput {
3694            width: 16,
3695            height: 16,
3696            dirty_rows: &dirty_rows,
3697            dirty_bits: &dirty_bits,
3698            dirty_cells: 1,
3699            dirty_all: false,
3700        };
3701
3702        let result = builder.build(&config, input);
3703        match result {
3704            TileDiffBuild::UseTiles(plan) => {
3705                assert_eq!(plan.stats.tile_w, 8);
3706                assert_eq!(plan.stats.tile_h, 8);
3707            }
3708            _ => unreachable!("expected UseTiles"),
3709        }
3710    }
3711
3712    #[test]
3713    fn tile_size_clamped_to_max_64() {
3714        let mut builder = TileDiffBuilder::new();
3715        let config = TileDiffConfig {
3716            enabled: true,
3717            tile_w: 255, // above max 64
3718            tile_h: 100, // above max 64
3719            skip_clean_rows: false,
3720            min_cells_for_tiles: 0,
3721            dense_cell_ratio: 1.1,
3722            dense_tile_ratio: 1.1,
3723            max_tiles: usize::MAX / 4,
3724        };
3725
3726        let dirty_rows = vec![true; 128];
3727        let mut dirty_bits = vec![0u8; 128 * 128];
3728        dirty_bits[0] = 1;
3729
3730        let input = TileDiffInput {
3731            width: 128,
3732            height: 128,
3733            dirty_rows: &dirty_rows,
3734            dirty_bits: &dirty_bits,
3735            dirty_cells: 1,
3736            dirty_all: false,
3737        };
3738
3739        let result = builder.build(&config, input);
3740        match result {
3741            TileDiffBuild::UseTiles(plan) => {
3742                assert_eq!(plan.stats.tile_w, 64);
3743                assert_eq!(plan.stats.tile_h, 64);
3744            }
3745            _ => unreachable!("expected UseTiles"),
3746        }
3747    }
3748
3749    // --- BufferDiff trait coverage ---
3750
3751    #[test]
3752    fn buffer_diff_default_is_empty() {
3753        let diff: BufferDiff = Default::default();
3754        assert!(diff.is_empty());
3755        assert_eq!(diff.len(), 0);
3756        assert!(diff.last_tile_stats().is_none());
3757    }
3758
3759    #[test]
3760    fn buffer_diff_debug_format() {
3761        let diff = BufferDiff::new();
3762        let dbg = format!("{:?}", diff);
3763        assert!(dbg.contains("BufferDiff"), "Debug: {dbg}");
3764    }
3765
3766    #[test]
3767    fn buffer_diff_clone_preserves_changes() {
3768        let old = Buffer::new(5, 5);
3769        let mut new = Buffer::new(5, 5);
3770        new.set_raw(2, 3, Cell::from_char('X'));
3771        let diff = BufferDiff::compute(&old, &new);
3772        let cloned = diff.clone();
3773        assert_eq!(diff.changes(), cloned.changes());
3774    }
3775
3776    // --- compute_into reuse ---
3777
3778    #[test]
3779    fn compute_into_replaces_previous_changes() {
3780        let mut diff = BufferDiff::new();
3781
3782        let old1 = Buffer::new(5, 5);
3783        let mut new1 = Buffer::new(5, 5);
3784        new1.set_raw(0, 0, Cell::from_char('A'));
3785        diff.compute_into(&old1, &new1);
3786        assert_eq!(diff.len(), 1);
3787
3788        let old2 = Buffer::new(3, 3);
3789        let mut new2 = Buffer::new(3, 3);
3790        new2.set_raw(1, 1, Cell::from_char('B'));
3791        new2.set_raw(2, 2, Cell::from_char('C'));
3792        diff.compute_into(&old2, &new2);
3793        assert_eq!(diff.len(), 2);
3794        assert_eq!(diff.changes(), &[(1, 1), (2, 2)]);
3795    }
3796
3797    #[test]
3798    fn compute_into_identical_clears() {
3799        let mut diff = BufferDiff::new();
3800        let old = Buffer::new(5, 5);
3801        let mut new = Buffer::new(5, 5);
3802        new.set_raw(0, 0, Cell::from_char('X'));
3803        diff.compute_into(&old, &new);
3804        assert_eq!(diff.len(), 1);
3805
3806        diff.compute_into(&old, &old);
3807        assert!(diff.is_empty());
3808    }
3809
3810    // --- compute_dirty_into ---
3811
3812    #[test]
3813    fn compute_dirty_into_no_dirty_rows() {
3814        let old = Buffer::new(10, 10);
3815        let mut new = old.clone();
3816        new.clear_dirty();
3817
3818        let mut diff = BufferDiff::new();
3819        diff.compute_dirty_into(&old, &new);
3820        assert!(diff.is_empty());
3821    }
3822
3823    #[test]
3824    fn compute_dirty_into_reuse() {
3825        let mut diff = BufferDiff::new();
3826
3827        let old = Buffer::new(10, 10);
3828        let mut new1 = old.clone();
3829        new1.clear_dirty();
3830        new1.set_raw(5, 5, Cell::from_char('X'));
3831        diff.compute_dirty_into(&old, &new1);
3832        assert_eq!(diff.len(), 1);
3833
3834        let mut new2 = old.clone();
3835        new2.clear_dirty();
3836        new2.set_raw(3, 3, Cell::from_char('Y'));
3837        new2.set_raw(7, 7, Cell::from_char('Z'));
3838        diff.compute_dirty_into(&old, &new2);
3839        assert_eq!(diff.len(), 2);
3840        assert_eq!(diff.changes(), &[(3, 3), (7, 7)]);
3841    }
3842
3843    // --- last_tile_stats ---
3844
3845    #[test]
3846    fn last_tile_stats_none_after_compute_into() {
3847        let mut diff = BufferDiff::new();
3848        let old = Buffer::new(5, 5);
3849        let new = Buffer::new(5, 5);
3850        diff.compute_into(&old, &new);
3851        assert!(diff.last_tile_stats().is_none());
3852    }
3853
3854    #[test]
3855    fn last_tile_stats_some_after_compute_dirty_into() {
3856        let mut diff = BufferDiff::new();
3857        let old = Buffer::new(10, 10);
3858        let mut new = old.clone();
3859        new.set_raw(0, 0, Cell::from_char('A'));
3860        diff.compute_dirty_into(&old, &new);
3861        // 10x10=100 < 12000 min threshold → SmallScreen fallback
3862        let stats = diff.last_tile_stats().expect("should have tile stats");
3863        assert_eq!(stats.fallback, Some(TileDiffFallback::SmallScreen));
3864    }
3865
3866    // --- tile_config_mut ---
3867
3868    #[test]
3869    fn tile_config_mut_modifies_behavior() {
3870        let old = Buffer::new(200, 60);
3871        let mut new = old.clone();
3872        new.clear_dirty();
3873        new.set_raw(0, 0, Cell::from_char('X'));
3874
3875        // Default config: tiles enabled for 200x60=12000 cells
3876        let mut diff = BufferDiff::new();
3877        diff.compute_dirty_into(&old, &new);
3878        let stats = diff.last_tile_stats().expect("stats");
3879        assert!(
3880            stats.fallback.is_none(),
3881            "tiles should be active for 200x60"
3882        );
3883
3884        // Disable via config_mut
3885        diff.tile_config_mut().enabled = false;
3886        diff.compute_dirty_into(&old, &new);
3887        let stats = diff.last_tile_stats().expect("stats");
3888        assert_eq!(stats.fallback, Some(TileDiffFallback::Disabled));
3889    }
3890
3891    // --- Row scan boundary ---
3892
3893    #[test]
3894    fn row_scan_width_31_below_row_block_size() {
3895        let old = Buffer::new(31, 1);
3896        let mut new = Buffer::new(31, 1);
3897        new.set_raw(0, 0, Cell::from_char('A'));
3898        new.set_raw(15, 0, Cell::from_char('B'));
3899        new.set_raw(30, 0, Cell::from_char('C'));
3900
3901        let diff = BufferDiff::compute(&old, &new);
3902        assert_eq!(diff.len(), 3);
3903        assert_eq!(diff.changes(), &[(0, 0), (15, 0), (30, 0)]);
3904    }
3905
3906    #[test]
3907    fn row_scan_width_32_exact_row_block_size() {
3908        let old = Buffer::new(32, 1);
3909        let mut new = Buffer::new(32, 1);
3910        new.set_raw(0, 0, Cell::from_char('A'));
3911        new.set_raw(15, 0, Cell::from_char('B'));
3912        new.set_raw(31, 0, Cell::from_char('C'));
3913
3914        let diff = BufferDiff::compute(&old, &new);
3915        assert_eq!(diff.len(), 3);
3916        assert_eq!(diff.changes(), &[(0, 0), (15, 0), (31, 0)]);
3917    }
3918
3919    #[test]
3920    fn row_scan_width_33_one_past_row_block_size() {
3921        let old = Buffer::new(33, 1);
3922        let mut new = Buffer::new(33, 1);
3923        new.set_raw(0, 0, Cell::from_char('A'));
3924        new.set_raw(31, 0, Cell::from_char('B'));
3925        new.set_raw(32, 0, Cell::from_char('C'));
3926
3927        let diff = BufferDiff::compute(&old, &new);
3928        assert_eq!(diff.len(), 3);
3929        assert_eq!(diff.changes(), &[(0, 0), (31, 0), (32, 0)]);
3930    }
3931
3932    // --- DenseCells threshold boundary ---
3933
3934    #[test]
3935    fn dense_cells_exact_threshold_triggers_fallback() {
3936        let mut builder = TileDiffBuilder::new();
3937        let w = 20u16;
3938        let h = 20u16;
3939        let total = (w as usize) * (h as usize); // 400
3940        let dirty_count = total / 4; // 100 = exactly 25%
3941
3942        let config = TileDiffConfig {
3943            enabled: true,
3944            tile_w: 8,
3945            tile_h: 8,
3946            skip_clean_rows: false,
3947            min_cells_for_tiles: 0,
3948            dense_cell_ratio: 0.25,
3949            dense_tile_ratio: 1.1,
3950            max_tiles: usize::MAX / 4,
3951        };
3952
3953        let dirty_rows = vec![true; h as usize];
3954        let dirty_bits = vec![1u8; total];
3955
3956        let input = TileDiffInput {
3957            width: w,
3958            height: h,
3959            dirty_rows: &dirty_rows,
3960            dirty_bits: &dirty_bits,
3961            dirty_cells: dirty_count,
3962            dirty_all: false,
3963        };
3964
3965        let result = builder.build(&config, input);
3966        assert!(matches!(
3967            result,
3968            TileDiffBuild::Fallback(stats) if stats.fallback == Some(TileDiffFallback::DenseCells)
3969        ));
3970    }
3971
3972    #[test]
3973    fn dense_cells_just_below_threshold_passes() {
3974        let mut builder = TileDiffBuilder::new();
3975        let w = 20u16;
3976        let h = 20u16;
3977        let total = (w as usize) * (h as usize); // 400
3978        let dirty_count = total / 4 - 1; // 99 = 24.75% < 25%
3979
3980        let config = TileDiffConfig {
3981            enabled: true,
3982            tile_w: 8,
3983            tile_h: 8,
3984            skip_clean_rows: false,
3985            min_cells_for_tiles: 0,
3986            dense_cell_ratio: 0.25,
3987            dense_tile_ratio: 1.1,
3988            max_tiles: usize::MAX / 4,
3989        };
3990
3991        let dirty_rows = vec![true; h as usize];
3992        let mut dirty_bits = vec![0u8; total];
3993        for bit in dirty_bits.iter_mut().take(dirty_count) {
3994            *bit = 1;
3995        }
3996
3997        let input = TileDiffInput {
3998            width: w,
3999            height: h,
4000            dirty_rows: &dirty_rows,
4001            dirty_bits: &dirty_bits,
4002            dirty_cells: dirty_count,
4003            dirty_all: false,
4004        };
4005
4006        let result = builder.build(&config, input);
4007        match &result {
4008            TileDiffBuild::Fallback(stats) => {
4009                assert_ne!(
4010                    stats.fallback,
4011                    Some(TileDiffFallback::DenseCells),
4012                    "should not trigger DenseCells below 25%: {:?}",
4013                    stats.fallback
4014                );
4015            }
4016            TileDiffBuild::UseTiles(_) => { /* expected */ }
4017        }
4018    }
4019
4020    // --- Switching between compute paths ---
4021
4022    #[test]
4023    fn switch_between_compute_and_dirty() {
4024        let mut diff = BufferDiff::new();
4025        let old = Buffer::new(10, 10);
4026        let mut new = Buffer::new(10, 10);
4027        new.set_raw(3, 3, Cell::from_char('X'));
4028
4029        diff.compute_into(&old, &new);
4030        assert_eq!(diff.len(), 1);
4031        assert!(diff.last_tile_stats().is_none());
4032
4033        diff.compute_dirty_into(&old, &new);
4034        assert_eq!(diff.len(), 1);
4035        assert!(diff.last_tile_stats().is_some());
4036
4037        diff.compute_into(&old, &new);
4038        assert_eq!(diff.len(), 1);
4039        assert!(diff.last_tile_stats().is_none());
4040    }
4041
4042    // --- Dimension mismatch panics ---
4043
4044    #[test]
4045    #[should_panic(expected = "buffer heights must match")]
4046    fn compute_panics_on_height_mismatch() {
4047        let old = Buffer::new(5, 5);
4048        let new = Buffer::new(5, 4);
4049        let _ = BufferDiff::compute(&old, &new);
4050    }
4051
4052    #[test]
4053    #[should_panic(expected = "buffer widths must match")]
4054    fn compute_dirty_panics_on_width_mismatch() {
4055        let old = Buffer::new(5, 5);
4056        let new = Buffer::new(4, 5);
4057        let _ = BufferDiff::compute_dirty(&old, &new);
4058    }
4059
4060    #[test]
4061    #[should_panic(expected = "buffer heights must match")]
4062    fn compute_dirty_panics_on_height_mismatch() {
4063        let old = Buffer::new(5, 5);
4064        let new = Buffer::new(5, 4);
4065        let _ = BufferDiff::compute_dirty(&old, &new);
4066    }
4067
4068    // --- TileDiffInput/TileDiffBuild trait coverage ---
4069
4070    #[test]
4071    fn tile_diff_input_debug_copy() {
4072        let dirty_rows = vec![true; 2];
4073        let dirty_bits = vec![0u8; 4];
4074        let input = TileDiffInput {
4075            width: 2,
4076            height: 2,
4077            dirty_rows: &dirty_rows,
4078            dirty_bits: &dirty_bits,
4079            dirty_cells: 0,
4080            dirty_all: false,
4081        };
4082        let dbg = format!("{:?}", input);
4083        assert!(dbg.contains("TileDiffInput"), "Debug: {dbg}");
4084        let copy = input; // Copy
4085        assert_eq!(copy.width, input.width);
4086    }
4087
4088    #[test]
4089    fn tile_diff_build_debug() {
4090        let mut builder = TileDiffBuilder::new();
4091        let config = TileDiffConfig::default();
4092        let dirty_rows = vec![true; 1];
4093        let dirty_bits = vec![0u8; 4];
4094        let input = TileDiffInput {
4095            width: 4,
4096            height: 1,
4097            dirty_rows: &dirty_rows,
4098            dirty_bits: &dirty_bits,
4099            dirty_cells: 0,
4100            dirty_all: false,
4101        };
4102        let result = builder.build(&config, input);
4103        let dbg = format!("{:?}", result);
4104        assert!(dbg.contains("Fallback"), "Debug: {dbg}");
4105    }
4106
4107    // --- BufferDiff::full runs ---
4108
4109    #[test]
4110    fn full_diff_runs_one_per_row() {
4111        let diff = BufferDiff::full(10, 3);
4112        let runs = diff.runs();
4113        assert_eq!(runs.len(), 3);
4114        for (i, run) in runs.iter().enumerate() {
4115            assert_eq!(run.y, i as u16);
4116            assert_eq!(run.x0, 0);
4117            assert_eq!(run.x1, 9);
4118            assert_eq!(run.len(), 10);
4119        }
4120    }
4121
4122    // --- dirty diff false positive rows ---
4123
4124    #[test]
4125    fn dirty_diff_skips_false_positive_rows() {
4126        let old = Buffer::new(10, 5);
4127        let mut new = old.clone();
4128        new.clear_dirty();
4129
4130        // set_raw marks rows dirty, but Cell::default() matches old content
4131        for y in 0..5u16 {
4132            new.set_raw(0, y, Cell::default());
4133        }
4134        // Real changes on rows 1 and 3
4135        new.set_raw(5, 1, Cell::from_char('A'));
4136        new.set_raw(7, 3, Cell::from_char('B'));
4137
4138        let diff = BufferDiff::compute_dirty(&old, &new);
4139        assert_eq!(diff.len(), 2);
4140        assert!(diff.changes().contains(&(5, 1)));
4141        assert!(diff.changes().contains(&(7, 3)));
4142    }
4143
4144    // --- Attribute-only change ---
4145
4146    #[test]
4147    fn bg_only_change_detected() {
4148        let old = Buffer::new(5, 1);
4149        let mut new = Buffer::new(5, 1);
4150        new.set_raw(2, 0, Cell::default().with_bg(PackedRgba::rgb(0, 0, 255)));
4151
4152        let diff = BufferDiff::compute(&old, &new);
4153        assert_eq!(diff.len(), 1);
4154        assert_eq!(diff.changes(), &[(2, 0)]);
4155    }
4156
4157    // --- Changes at buffer boundaries ---
4158
4159    #[test]
4160    fn changes_at_buffer_corners() {
4161        let w = 100u16;
4162        let h = 50u16;
4163        let old = Buffer::new(w, h);
4164        let mut new = Buffer::new(w, h);
4165        new.set_raw(0, 0, Cell::from_char('A'));
4166        new.set_raw(w - 1, h - 1, Cell::from_char('Z'));
4167
4168        let diff = BufferDiff::compute(&old, &new);
4169        assert_eq!(diff.len(), 2);
4170        assert_eq!(diff.changes()[0], (0, 0));
4171        assert_eq!(diff.changes()[1], (w - 1, h - 1));
4172
4173        let runs = diff.runs();
4174        assert_eq!(runs.len(), 2);
4175        assert_eq!(runs[0], ChangeRun::new(0, 0, 0));
4176        assert_eq!(runs[1], ChangeRun::new(h - 1, w - 1, w - 1));
4177    }
4178
4179    // --- TileParams Debug/Copy ---
4180
4181    #[test]
4182    fn tile_params_debug_copy() {
4183        let params = TileParams {
4184            width: 80,
4185            height: 24,
4186            tile_w: 16,
4187            tile_h: 8,
4188            tiles_x: 5,
4189            tiles_y: 3,
4190        };
4191        let dbg = format!("{:?}", params);
4192        assert!(dbg.contains("TileParams"), "Debug: {dbg}");
4193        let copy = params; // Copy
4194        assert_eq!(copy.width, params.width);
4195        let cloned: TileParams = params; // Copy
4196        assert_eq!(cloned.tiles_x, params.tiles_x);
4197    }
4198
4199    // --- TileDiffStats Debug/Copy ---
4200
4201    #[test]
4202    fn tile_diff_stats_debug_copy() {
4203        let mut builder = TileDiffBuilder::new();
4204        let config = TileDiffConfig::default();
4205        let dirty_rows = vec![true; 1];
4206        let dirty_bits = vec![0u8; 1];
4207        let input = TileDiffInput {
4208            width: 1,
4209            height: 1,
4210            dirty_rows: &dirty_rows,
4211            dirty_bits: &dirty_bits,
4212            dirty_cells: 0,
4213            dirty_all: false,
4214        };
4215        let result = builder.build(&config, input);
4216        match result {
4217            TileDiffBuild::Fallback(stats) => {
4218                let dbg = format!("{:?}", stats);
4219                assert!(dbg.contains("TileDiffStats"), "Debug: {dbg}");
4220                let copy = stats;
4221                assert_eq!(copy.width, stats.width);
4222                let cloned: TileDiffStats = stats; // Copy
4223                assert_eq!(cloned.height, stats.height);
4224            }
4225            _ => unreachable!("expected Fallback for 1x1"),
4226        }
4227    }
4228
4229    // =========================================================================
4230    // Dirty Span-Based Scanning (bd-khkj4)
4231    // =========================================================================
4232
4233    #[test]
4234    fn compute_dirty_with_targeted_spans() {
4235        // Verify that compute_dirty correctly uses span information
4236        // to limit scanning to only the dirty span regions.
4237        let width = 100u16;
4238        let height = 10u16;
4239        let old = Buffer::new(width, height);
4240        let mut new = old.clone();
4241        new.clear_dirty();
4242
4243        // Set a few cells in specific positions to create narrow spans
4244        new.set_raw(10, 3, Cell::from_char('A'));
4245        new.set_raw(11, 3, Cell::from_char('B'));
4246        new.set_raw(50, 7, Cell::from_char('C'));
4247
4248        let full = BufferDiff::compute(&old, &new);
4249        let dirty = BufferDiff::compute_dirty(&old, &new);
4250
4251        assert_eq!(full.changes(), dirty.changes());
4252        assert_eq!(dirty.len(), 3);
4253        assert!(dirty.changes().contains(&(10, 3)));
4254        assert!(dirty.changes().contains(&(11, 3)));
4255        assert!(dirty.changes().contains(&(50, 7)));
4256    }
4257
4258    #[test]
4259    fn compute_dirty_spans_on_multiple_rows() {
4260        // Multiple rows with spans at different positions
4261        let width = 80u16;
4262        let height = 5u16;
4263        let old = Buffer::new(width, height);
4264        let mut new = old.clone();
4265        new.clear_dirty();
4266
4267        // Row 0: changes at start
4268        new.set_raw(0, 0, Cell::from_char('A'));
4269        new.set_raw(1, 0, Cell::from_char('B'));
4270        // Row 2: changes in middle
4271        new.set_raw(40, 2, Cell::from_char('C'));
4272        // Row 4: changes at end
4273        new.set_raw(79, 4, Cell::from_char('D'));
4274
4275        let full = BufferDiff::compute(&old, &new);
4276        let dirty = BufferDiff::compute_dirty(&old, &new);
4277
4278        assert_eq!(full.changes(), dirty.changes());
4279        assert_eq!(dirty.len(), 4);
4280    }
4281
4282    #[test]
4283    fn compute_dirty_span_with_false_positive_row() {
4284        // Row is dirty but actual cell content hasn't changed
4285        let old = Buffer::new(20, 3);
4286        let mut new = old.clone();
4287        new.clear_dirty();
4288
4289        // Mark row 1 dirty via set_raw with default cell (matches old)
4290        new.set_raw(5, 1, Cell::default());
4291        // Real change on row 2
4292        new.set_raw(10, 2, Cell::from_char('X'));
4293
4294        let dirty = BufferDiff::compute_dirty(&old, &new);
4295        assert_eq!(dirty.len(), 1);
4296        assert_eq!(dirty.changes(), &[(10, 2)]);
4297    }
4298
4299    #[test]
4300    fn compute_dirty_many_spans_per_row() {
4301        // Create many separate spans on a single row (below overflow threshold)
4302        let width = 200u16;
4303        let height = 1u16;
4304        let old = Buffer::new(width, height);
4305        let mut new = old.clone();
4306        new.clear_dirty();
4307
4308        // Create 10 isolated changes (each creates a separate span)
4309        let positions: Vec<u16> = vec![5, 20, 35, 50, 65, 80, 95, 110, 125, 140];
4310        for &x in &positions {
4311            new.set_raw(x, 0, Cell::from_char('X'));
4312        }
4313
4314        let full = BufferDiff::compute(&old, &new);
4315        let dirty = BufferDiff::compute_dirty(&old, &new);
4316
4317        assert_eq!(full.changes(), dirty.changes());
4318        assert_eq!(dirty.len(), positions.len());
4319    }
4320
4321    // =========================================================================
4322    // Tile + Span Combination Path (bd-khkj4)
4323    // =========================================================================
4324
4325    #[test]
4326    fn tile_diff_with_dirty_spans_matches_full() {
4327        // Force tile path and verify it works correctly with dirty spans
4328        let width = 200u16;
4329        let height = 60u16;
4330        let old = Buffer::new(width, height);
4331        let mut new = old.clone();
4332        new.clear_dirty();
4333
4334        // Create sparse changes across multiple tiles
4335        new.set_raw(5, 2, Cell::from_char('A'));
4336        new.set_raw(100, 30, Cell::from_char('B'));
4337        new.set_raw(195, 55, Cell::from_char('C'));
4338
4339        let (dirty_diff, stats) = diff_with_forced_tiles(&old, &new);
4340        let full = BufferDiff::compute(&old, &new);
4341
4342        assert!(stats.fallback.is_none(), "tile path should be used");
4343        assert_eq!(
4344            stats.sat_build_cells, 3,
4345            "span-aware tile build should only scan covered span cells"
4346        );
4347        assert_eq!(full.changes(), dirty_diff.changes());
4348        assert_eq!(dirty_diff.len(), 3);
4349    }
4350
4351    #[test]
4352    fn tile_diff_with_spans_straddling_tile_boundary() {
4353        // Create a span that crosses a tile boundary
4354        let width = 200u16;
4355        let height = 60u16;
4356        let old = Buffer::new(width, height);
4357        let mut new = old.clone();
4358        new.clear_dirty();
4359
4360        // With tile_w=8, create adjacent changes around position 8 (tile boundary)
4361        new.set_raw(6, 0, Cell::from_char('A'));
4362        new.set_raw(7, 0, Cell::from_char('B'));
4363        new.set_raw(8, 0, Cell::from_char('C'));
4364        new.set_raw(9, 0, Cell::from_char('D'));
4365
4366        let (dirty_diff, stats) = diff_with_forced_tiles(&old, &new);
4367        let full = BufferDiff::compute(&old, &new);
4368
4369        assert!(stats.fallback.is_none());
4370        assert_eq!(full.changes(), dirty_diff.changes());
4371        assert_eq!(dirty_diff.len(), 4);
4372    }
4373
4374    #[test]
4375    fn tile_diff_single_dirty_tile_skips_others() {
4376        // Verify that clean tiles are skipped
4377        let width = 200u16;
4378        let height = 60u16;
4379        let old = Buffer::new(width, height);
4380        let mut new = old.clone();
4381        new.clear_dirty();
4382
4383        // Only one change in one tile
4384        new.set_raw(3, 3, Cell::from_char('X'));
4385
4386        let (dirty_diff, stats) = diff_with_forced_tiles(&old, &new);
4387
4388        assert!(stats.fallback.is_none());
4389        assert_eq!(dirty_diff.len(), 1);
4390        assert!(stats.skipped_tiles > 0, "should skip clean tiles");
4391        assert_eq!(stats.dirty_tiles, 1, "only one tile should be dirty");
4392    }
4393
4394    #[test]
4395    fn accumulate_tile_counts_range_single_cell_range() {
4396        let mut tile_counts = vec![0u32; 4];
4397        let dirty_bits = vec![0, 0, 1, 0, 0, 0, 0, 0];
4398        let mut scanned_cells = 0usize;
4399
4400        accumulate_tile_counts_range(
4401            &mut tile_counts,
4402            &dirty_bits,
4403            0,
4404            4,
4405            2,
4406            2..3,
4407            &mut scanned_cells,
4408        )
4409        .unwrap();
4410
4411        assert_eq!(scanned_cells, 1);
4412        assert_eq!(tile_counts, vec![0, 1, 0, 0]);
4413    }
4414
4415    #[test]
4416    fn accumulate_tile_counts_range_single_tile_multi_cell_range() {
4417        let mut tile_counts = vec![0u32; 4];
4418        let dirty_bits = vec![0, 1, 0, 1, 1, 0, 0, 0];
4419        let mut scanned_cells = 0usize;
4420
4421        accumulate_tile_counts_range(
4422            &mut tile_counts,
4423            &dirty_bits,
4424            0,
4425            4,
4426            2,
4427            4..6,
4428            &mut scanned_cells,
4429        )
4430        .unwrap();
4431
4432        assert_eq!(scanned_cells, 2);
4433        assert_eq!(tile_counts, vec![0, 0, 1, 0]);
4434    }
4435
4436    // =========================================================================
4437    // TileDiffPlan Field Access (bd-khkj4)
4438    // =========================================================================
4439
4440    #[test]
4441    fn tile_diff_plan_fields_accessible() {
4442        let mut builder = TileDiffBuilder::new();
4443        let config = TileDiffConfig::default()
4444            .with_min_cells_for_tiles(0)
4445            .with_dense_tile_ratio(1.1)
4446            .with_dense_cell_ratio(1.1)
4447            .with_max_tiles(usize::MAX / 4);
4448
4449        let w = 32u16;
4450        let h = 16u16;
4451        let dirty_rows = vec![true; h as usize];
4452        let mut dirty_bits = vec![0u8; (w as usize) * (h as usize)];
4453        // Mark two cells dirty in different tiles
4454        dirty_bits[0] = 1; // tile (0,0)
4455        dirty_bits[8 + 8 * w as usize] = 1; // tile (1,1) roughly
4456
4457        let input = TileDiffInput {
4458            width: w,
4459            height: h,
4460            dirty_rows: &dirty_rows,
4461            dirty_bits: &dirty_bits,
4462            dirty_cells: 2,
4463            dirty_all: false,
4464        };
4465
4466        let result = builder.build(&config, input);
4467        match result {
4468            TileDiffBuild::UseTiles(plan) => {
4469                // Verify params are accessible
4470                assert_eq!(plan.params.width, w);
4471                assert_eq!(plan.params.height, h);
4472                assert!(plan.params.tile_w >= 8);
4473                assert!(plan.params.tile_h >= 8);
4474                assert!(plan.params.tiles_x > 0);
4475                assert!(plan.params.tiles_y > 0);
4476
4477                // Verify dirty_tiles slice
4478                assert_eq!(plan.dirty_tiles.len(), plan.params.total_tiles());
4479                let dirty_count: usize = plan.dirty_tiles.iter().filter(|&&d| d).count();
4480                assert_eq!(dirty_count, plan.stats.dirty_tiles);
4481
4482                // Verify tile_counts slice
4483                assert_eq!(plan.tile_counts.len(), plan.params.total_tiles());
4484
4485                // Verify SAT slice (tiles_x+1 * tiles_y+1)
4486                let expected_sat_len = (plan.params.tiles_x + 1) * (plan.params.tiles_y + 1);
4487                assert_eq!(plan.sat.len(), expected_sat_len);
4488
4489                // SAT[0][*] and SAT[*][0] should be 0 (prefix sum boundary)
4490                let sat_w = plan.params.tiles_x + 1;
4491                for tx in 0..sat_w {
4492                    assert_eq!(plan.sat[tx], 0, "SAT top border should be 0");
4493                }
4494                for ty in 0..plan.params.tiles_y + 1 {
4495                    assert_eq!(plan.sat[ty * sat_w], 0, "SAT left border should be 0");
4496                }
4497            }
4498            _ => unreachable!("expected UseTiles"),
4499        }
4500    }
4501
4502    // =========================================================================
4503    // DenseTiles Threshold Boundary (bd-khkj4)
4504    // =========================================================================
4505
4506    #[test]
4507    fn dense_tiles_exact_threshold_triggers_fallback() {
4508        let mut builder = TileDiffBuilder::new();
4509        let w = 32u16;
4510        let h = 32u16;
4511        // With tile_w=8, tile_h=8: tiles_x=4, tiles_y=4, total=16
4512        // Dense tile ratio = 0.5 means >=8 dirty tiles trigger fallback
4513
4514        let total_cells = (w as usize) * (h as usize);
4515        let config = TileDiffConfig {
4516            enabled: true,
4517            tile_w: 8,
4518            tile_h: 8,
4519            skip_clean_rows: false,
4520            min_cells_for_tiles: 0,
4521            dense_cell_ratio: 1.1,
4522            dense_tile_ratio: 0.5,
4523            max_tiles: usize::MAX / 4,
4524        };
4525
4526        let dirty_rows = vec![true; h as usize];
4527        let mut dirty_bits = vec![0u8; total_cells];
4528        // Mark one cell dirty in each of 8 tiles (50% of 16 tiles)
4529        // Tiles are 8x8 on a 32x32 grid: (0,0), (1,0), (2,0), (3,0), (0,1)...
4530        for tile_y in 0..2 {
4531            for tile_x in 0..4 {
4532                let x = tile_x * 8;
4533                let y = tile_y * 8;
4534                dirty_bits[y * w as usize + x] = 1;
4535            }
4536        }
4537
4538        let input = TileDiffInput {
4539            width: w,
4540            height: h,
4541            dirty_rows: &dirty_rows,
4542            dirty_bits: &dirty_bits,
4543            dirty_cells: 8,
4544            dirty_all: false,
4545        };
4546
4547        let result = builder.build(&config, input);
4548        assert!(
4549            matches!(
4550                result,
4551                TileDiffBuild::Fallback(stats) if stats.fallback == Some(TileDiffFallback::DenseTiles)
4552            ),
4553            "8 of 16 tiles dirty (50%) should trigger DenseTiles with threshold 0.5"
4554        );
4555    }
4556
4557    #[test]
4558    fn dense_tiles_just_below_threshold_passes() {
4559        let mut builder = TileDiffBuilder::new();
4560        let w = 32u16;
4561        let h = 32u16;
4562        // tiles: 4x4=16. Dense tile ratio = 0.5 means <8 dirty tiles pass
4563
4564        let total_cells = (w as usize) * (h as usize);
4565        let config = TileDiffConfig {
4566            enabled: true,
4567            tile_w: 8,
4568            tile_h: 8,
4569            skip_clean_rows: false,
4570            min_cells_for_tiles: 0,
4571            dense_cell_ratio: 1.1,
4572            dense_tile_ratio: 0.5,
4573            max_tiles: usize::MAX / 4,
4574        };
4575
4576        let dirty_rows = vec![true; h as usize];
4577        let mut dirty_bits = vec![0u8; total_cells];
4578        // Mark one cell dirty in 7 tiles (43.75% < 50%)
4579        for tile_idx in 0..7 {
4580            let tile_x = tile_idx % 4;
4581            let tile_y = tile_idx / 4;
4582            let x = tile_x * 8;
4583            let y = tile_y * 8;
4584            dirty_bits[y * w as usize + x] = 1;
4585        }
4586
4587        let input = TileDiffInput {
4588            width: w,
4589            height: h,
4590            dirty_rows: &dirty_rows,
4591            dirty_bits: &dirty_bits,
4592            dirty_cells: 7,
4593            dirty_all: false,
4594        };
4595
4596        let result = builder.build(&config, input);
4597        assert!(
4598            matches!(result, TileDiffBuild::UseTiles(_)),
4599            "7 of 16 tiles dirty (43.75%) should use tiles with threshold 0.5"
4600        );
4601    }
4602
4603    // =========================================================================
4604    // span_diagnostics Helper (bd-khkj4)
4605    // =========================================================================
4606
4607    #[test]
4608    fn span_diagnostics_with_no_dirty_spans() {
4609        let mut buf = Buffer::new(20, 3);
4610        buf.clear_dirty();
4611        let diag = span_diagnostics(&buf);
4612        // Should report stats with no dirty rows
4613        assert!(
4614            diag.contains("stats="),
4615            "diagnostics should include stats: {diag}"
4616        );
4617    }
4618
4619    #[test]
4620    fn span_diagnostics_with_dirty_cells() {
4621        let mut buf = Buffer::new(20, 3);
4622        buf.clear_dirty();
4623        buf.set_raw(5, 1, Cell::from_char('X'));
4624        let diag = span_diagnostics(&buf);
4625        assert!(
4626            diag.contains("stats="),
4627            "diagnostics should include stats: {diag}"
4628        );
4629    }
4630
4631    #[test]
4632    fn span_diagnostics_with_full_row() {
4633        let mut buf = Buffer::new(20, 2);
4634        buf.clear_dirty();
4635        // Fill entire row to trigger full-row dirty
4636        for x in 0..20u16 {
4637            buf.set_raw(x, 0, Cell::from_char('X'));
4638        }
4639        let diag = span_diagnostics(&buf);
4640        // Should mention "full" for the full-row dirty case
4641        assert!(
4642            diag.contains("stats="),
4643            "diagnostics should include stats: {diag}"
4644        );
4645    }
4646
4647    // =========================================================================
4648    // Misc Edge Cases (bd-khkj4)
4649    // =========================================================================
4650
4651    #[test]
4652    fn compute_dirty_matches_full_for_single_row_buffer() {
4653        let old = Buffer::new(50, 1);
4654        let mut new = old.clone();
4655        new.set_raw(25, 0, Cell::from_char('M'));
4656
4657        let full = BufferDiff::compute(&old, &new);
4658        let dirty = BufferDiff::compute_dirty(&old, &new);
4659
4660        assert_eq!(full.changes(), dirty.changes());
4661    }
4662
4663    #[test]
4664    fn compute_dirty_matches_full_for_single_column_buffer() {
4665        let old = Buffer::new(1, 50);
4666        let mut new = old.clone();
4667        new.set_raw(0, 25, Cell::from_char('M'));
4668
4669        let full = BufferDiff::compute(&old, &new);
4670        let dirty = BufferDiff::compute_dirty(&old, &new);
4671
4672        assert_eq!(full.changes(), dirty.changes());
4673    }
4674
4675    #[test]
4676    fn tile_config_chain_returns_same_type() {
4677        // Verify builder pattern chaining works and returns Self
4678        let config = TileDiffConfig::default()
4679            .with_enabled(true)
4680            .with_tile_size(16, 16)
4681            .with_min_cells_for_tiles(1000)
4682            .with_skip_clean_rows(true)
4683            .with_dense_cell_ratio(0.3)
4684            .with_dense_tile_ratio(0.7)
4685            .with_max_tiles(2048);
4686
4687        assert!(config.enabled);
4688        assert_eq!(config.tile_w, 16);
4689        assert_eq!(config.tile_h, 16);
4690        assert_eq!(config.min_cells_for_tiles, 1000);
4691        assert!(config.skip_clean_rows);
4692        assert!((config.dense_cell_ratio - 0.3).abs() < f64::EPSILON);
4693        assert!((config.dense_tile_ratio - 0.7).abs() < f64::EPSILON);
4694        assert_eq!(config.max_tiles, 2048);
4695    }
4696
4697    #[test]
4698    fn runs_into_reuse_across_multiple_diffs() {
4699        // Verify runs_into correctly reuses buffer across multiple diff operations
4700        let mut runs_buf: Vec<ChangeRun> = Vec::new();
4701
4702        // First diff
4703        let old1 = Buffer::new(10, 2);
4704        let mut new1 = Buffer::new(10, 2);
4705        new1.set_raw(0, 0, Cell::from_char('A'));
4706        new1.set_raw(1, 0, Cell::from_char('B'));
4707        let diff1 = BufferDiff::compute(&old1, &new1);
4708        diff1.runs_into(&mut runs_buf);
4709        assert_eq!(runs_buf.len(), 1);
4710        assert_eq!(runs_buf[0], ChangeRun::new(0, 0, 1));
4711
4712        // Second diff - should clear previous and fill with new
4713        let old2 = Buffer::new(5, 3);
4714        let mut new2 = Buffer::new(5, 3);
4715        new2.set_raw(2, 1, Cell::from_char('X'));
4716        new2.set_raw(4, 2, Cell::from_char('Y'));
4717        let diff2 = BufferDiff::compute(&old2, &new2);
4718        diff2.runs_into(&mut runs_buf);
4719        assert_eq!(runs_buf.len(), 2);
4720        assert_eq!(runs_buf[0], ChangeRun::new(1, 2, 2));
4721        assert_eq!(runs_buf[1], ChangeRun::new(2, 4, 4));
4722    }
4723
4724    #[test]
4725    fn full_diff_zero_dimensions_runs_empty() {
4726        let diff_w0 = BufferDiff::full(0, 5);
4727        assert!(diff_w0.runs().is_empty());
4728
4729        let diff_h0 = BufferDiff::full(5, 0);
4730        assert!(diff_h0.runs().is_empty());
4731
4732        let diff_both = BufferDiff::full(0, 0);
4733        assert!(diff_both.runs().is_empty());
4734    }
4735
4736    #[test]
4737    fn change_run_max_u16_values() {
4738        // Test near-max values that don't overflow len()
4739        let run = ChangeRun::new(u16::MAX, 1, u16::MAX);
4740        assert_eq!(run.y, u16::MAX);
4741        assert_eq!(run.x0, 1);
4742        assert_eq!(run.x1, u16::MAX);
4743        assert_eq!(run.len(), usize::from(u16::MAX)); // 65535 - 1 + 1 = 65535
4744
4745        // Single-cell run at max position
4746        let run2 = ChangeRun::new(u16::MAX, u16::MAX, u16::MAX);
4747        assert_eq!(run2.len(), 1);
4748    }
4749
4750    #[test]
4751    fn tile_diff_equivalence_adjacent_tiles() {
4752        // Changes at tile boundaries (tiles are 8 cells wide)
4753        let width = 200u16;
4754        let height = 60u16;
4755        let old = Buffer::new(width, height);
4756        let mut new = old.clone();
4757        new.clear_dirty();
4758
4759        // Place changes at boundaries of adjacent tiles
4760        // tile_w=8, so tile boundaries at 0, 8, 16, 24...
4761        new.set_raw(7, 0, Cell::from_char('A')); // end of tile 0
4762        new.set_raw(8, 0, Cell::from_char('B')); // start of tile 1
4763        new.set_raw(15, 0, Cell::from_char('C')); // end of tile 1
4764        new.set_raw(16, 0, Cell::from_char('D')); // start of tile 2
4765
4766        assert_tile_diff_equivalence(&old, &new, "adjacent_tile_boundaries");
4767    }
4768}
4769
4770#[cfg(test)]
4771mod proptests {
4772    use super::*;
4773    use crate::cell::Cell;
4774    use ftui_core::geometry::Rect;
4775    use proptest::prelude::*;
4776
4777    // Property: Applying diff changes to old buffer produces new buffer.
4778    #[test]
4779    fn diff_apply_produces_target() {
4780        proptest::proptest!(|(
4781            width in 5u16..50,
4782            height in 5u16..30,
4783            num_changes in 0usize..200,
4784        )| {
4785            // Create old buffer (all spaces)
4786            let old = Buffer::new(width, height);
4787
4788            // Create new buffer by making random changes
4789            let mut new = old.clone();
4790            for i in 0..num_changes {
4791                let x = (i * 7 + 3) as u16 % width;
4792                let y = (i * 11 + 5) as u16 % height;
4793                let ch = char::from_u32(('A' as u32) + (i as u32 % 26)).unwrap();
4794                new.set_raw(x, y, Cell::from_char(ch));
4795            }
4796
4797            // Compute diff
4798            let diff = BufferDiff::compute(&old, &new);
4799
4800            // Apply diff to old should produce new
4801            let mut result = old.clone();
4802            for (x, y) in diff.iter() {
4803                let cell = *new.get_unchecked(x, y);
4804                result.set_raw(x, y, cell);
4805            }
4806
4807            // Verify buffers match
4808            for y in 0..height {
4809                for x in 0..width {
4810                    let result_cell = result.get_unchecked(x, y);
4811                    let new_cell = new.get_unchecked(x, y);
4812                    prop_assert!(
4813                        result_cell.bits_eq(new_cell),
4814                        "Mismatch at ({}, {})",
4815                        x,
4816                        y
4817                    );
4818                }
4819            }
4820        });
4821    }
4822
4823    // Property: Diff is empty when buffers are identical.
4824    #[test]
4825    fn identical_buffers_empty_diff() {
4826        proptest::proptest!(|(width in 1u16..100, height in 1u16..50)| {
4827            let buf = Buffer::new(width, height);
4828            let diff = BufferDiff::compute(&buf, &buf);
4829            prop_assert!(diff.is_empty(), "Identical buffers should have empty diff");
4830        });
4831    }
4832
4833    // Property: Every change in diff corresponds to an actual difference.
4834    #[test]
4835    fn diff_contains_only_real_changes() {
4836        proptest::proptest!(|(
4837            width in 5u16..50,
4838            height in 5u16..30,
4839            num_changes in 0usize..100,
4840        )| {
4841            let old = Buffer::new(width, height);
4842            let mut new = old.clone();
4843
4844            for i in 0..num_changes {
4845                let x = (i * 7 + 3) as u16 % width;
4846                let y = (i * 11 + 5) as u16 % height;
4847                new.set_raw(x, y, Cell::from_char('X'));
4848            }
4849
4850            let diff = BufferDiff::compute(&old, &new);
4851
4852            // Every change position should actually differ
4853            for (x, y) in diff.iter() {
4854                let old_cell = old.get_unchecked(x, y);
4855                let new_cell = new.get_unchecked(x, y);
4856                prop_assert!(
4857                    !old_cell.bits_eq(new_cell),
4858                    "Diff includes unchanged cell at ({}, {})",
4859                    x,
4860                    y
4861                );
4862            }
4863        });
4864    }
4865
4866    // Property: Runs correctly coalesce adjacent changes.
4867    #[test]
4868    fn runs_are_contiguous() {
4869        proptest::proptest!(|(width in 10u16..80, height in 5u16..30)| {
4870            let old = Buffer::new(width, height);
4871            let mut new = old.clone();
4872
4873            // Create some horizontal runs
4874            for y in 0..height.min(5) {
4875                for x in 0..width.min(10) {
4876                    new.set_raw(x, y, Cell::from_char('#'));
4877                }
4878            }
4879
4880            let diff = BufferDiff::compute(&old, &new);
4881            let runs = diff.runs();
4882
4883            // Verify each run is contiguous
4884            for run in runs {
4885                prop_assert!(run.x1 >= run.x0, "Run has invalid range");
4886                prop_assert!(!run.is_empty(), "Run should not be empty");
4887
4888                // Verify all cells in run are actually changed
4889                for x in run.x0..=run.x1 {
4890                    let old_cell = old.get_unchecked(x, run.y);
4891                    let new_cell = new.get_unchecked(x, run.y);
4892                    prop_assert!(
4893                        !old_cell.bits_eq(new_cell),
4894                        "Run includes unchanged cell at ({}, {})",
4895                        x,
4896                        run.y
4897                    );
4898                }
4899            }
4900        });
4901    }
4902
4903    // Property: Runs cover all changes exactly once.
4904    #[test]
4905    fn runs_cover_all_changes() {
4906        proptest::proptest!(|(
4907            width in 10u16..60,
4908            height in 5u16..30,
4909            num_changes in 1usize..100,
4910        )| {
4911            let old = Buffer::new(width, height);
4912            let mut new = old.clone();
4913
4914            for i in 0..num_changes {
4915                let x = (i * 13 + 7) as u16 % width;
4916                let y = (i * 17 + 3) as u16 % height;
4917                new.set_raw(x, y, Cell::from_char('X'));
4918            }
4919
4920            let diff = BufferDiff::compute(&old, &new);
4921            let runs = diff.runs();
4922
4923            // Count cells covered by runs
4924            let mut run_cells: std::collections::HashSet<(u16, u16)> =
4925                std::collections::HashSet::new();
4926            for run in &runs {
4927                for x in run.x0..=run.x1 {
4928                    let was_new = run_cells.insert((x, run.y));
4929                    prop_assert!(was_new, "Duplicate cell ({}, {}) in runs", x, run.y);
4930                }
4931            }
4932
4933            // Verify runs cover exactly the changes
4934            for (x, y) in diff.iter() {
4935                prop_assert!(
4936                    run_cells.contains(&(x, y)),
4937                    "Change at ({}, {}) not covered by runs",
4938                    x,
4939                    y
4940                );
4941            }
4942
4943            prop_assert_eq!(
4944                run_cells.len(),
4945                diff.len(),
4946                "Run cell count should match diff change count"
4947            );
4948        });
4949    }
4950
4951    // Property (bd-4kq0.1.2): Block-based scan matches scalar scan
4952    // for random row widths and change patterns. This verifies the
4953    // block/remainder handling is correct for all alignment cases.
4954    #[test]
4955    fn block_scan_matches_scalar() {
4956        proptest::proptest!(|(
4957            width in 1u16..200,
4958            height in 1u16..20,
4959            num_changes in 0usize..200,
4960        )| {
4961            use crate::cell::PackedRgba;
4962
4963            let old = Buffer::new(width, height);
4964            let mut new = Buffer::new(width, height);
4965
4966            for i in 0..num_changes {
4967                let x = (i * 13 + 7) as u16 % width;
4968                let y = (i * 17 + 3) as u16 % height;
4969                let fg = PackedRgba::rgb(
4970                    ((i * 31) % 256) as u8,
4971                    ((i * 47) % 256) as u8,
4972                    ((i * 71) % 256) as u8,
4973                );
4974                new.set_raw(x, y, Cell::from_char('X').with_fg(fg));
4975            }
4976
4977            let diff = BufferDiff::compute(&old, &new);
4978
4979            // Verify against manual scalar scan
4980            let mut scalar_changes = Vec::new();
4981            for y in 0..height {
4982                for x in 0..width {
4983                    let old_cell = old.get_unchecked(x, y);
4984                    let new_cell = new.get_unchecked(x, y);
4985                    if !old_cell.bits_eq(new_cell) {
4986                        scalar_changes.push((x, y));
4987                    }
4988                }
4989            }
4990
4991            prop_assert_eq!(
4992                diff.changes(),
4993                &scalar_changes[..],
4994                "Block scan should match scalar scan"
4995            );
4996        });
4997    }
4998
4999    // ========== Diff Equivalence: dirty+block vs full scan (bd-4kq0.1.3) ==========
5000
5001    // Property: compute_dirty with all rows dirty matches compute exactly.
5002    // This verifies the block-scan + dirty-row path is semantically
5003    // equivalent to the full scan for random buffers.
5004    #[test]
5005    fn property_diff_equivalence() {
5006        proptest::proptest!(|(
5007            width in 1u16..120,
5008            height in 1u16..40,
5009            num_changes in 0usize..300,
5010        )| {
5011            let old = Buffer::new(width, height);
5012            let mut new = Buffer::new(width, height);
5013
5014            // Apply deterministic pseudo-random changes
5015            for i in 0..num_changes {
5016                let x = (i * 13 + 7) as u16 % width;
5017                let y = (i * 17 + 3) as u16 % height;
5018                let ch = char::from_u32(('A' as u32) + (i as u32 % 26)).unwrap();
5019                let fg = crate::cell::PackedRgba::rgb(
5020                    ((i * 31) % 256) as u8,
5021                    ((i * 47) % 256) as u8,
5022                    ((i * 71) % 256) as u8,
5023                );
5024                new.set_raw(x, y, Cell::from_char(ch).with_fg(fg));
5025            }
5026
5027            let full = BufferDiff::compute(&old, &new);
5028            let dirty = BufferDiff::compute_dirty(&old, &new);
5029
5030            prop_assert_eq!(
5031                full.changes(),
5032                dirty.changes(),
5033                "dirty diff must match full diff (width={}, height={}, changes={})",
5034                width,
5035                height,
5036                num_changes
5037            );
5038
5039            // Also verify run coalescing is identical
5040            let full_runs = full.runs();
5041            let dirty_runs = dirty.runs();
5042            prop_assert_eq!(full_runs.len(), dirty_runs.len(), "run count must match");
5043            for (fr, dr) in full_runs.iter().zip(dirty_runs.iter()) {
5044                prop_assert_eq!(fr, dr, "run mismatch");
5045            }
5046        });
5047    }
5048
5049    // Property: compute_dirty matches compute for random fill/set operations.
5050    // This exercises span merging and complex dirty patterns (bd-3e1t.6.4).
5051    #[test]
5052    fn property_diff_equivalence_complex_spans() {
5053        proptest::proptest!(|(
5054            width in 10u16..100,
5055            height in 10u16..50,
5056            ops in proptest::collection::vec(
5057                prop_oneof![
5058                    // Single cell set
5059                    (Just(0u8), any::<u16>(), any::<u16>(), any::<char>()),
5060                    // Region fill (small rects)
5061                    (Just(1u8), any::<u16>(), any::<u16>(), any::<char>()),
5062                ],
5063                1..50
5064            )
5065        )| {
5066            let old = Buffer::new(width, height);
5067            let mut new = Buffer::new(width, height);
5068
5069            // Clear dirty state on new so we start fresh tracking
5070            new.clear_dirty();
5071
5072            for (op_type, x, y, ch) in ops {
5073                let x = x % width;
5074                let y = y % height;
5075                let cell = Cell::from_char(ch);
5076
5077                match op_type {
5078                    0 => new.set(x, y, cell),
5079                    1 => {
5080                        // Random small rect
5081                        let w = ((x + 10).min(width) - x).max(1);
5082                        let h = ((y + 5).min(height) - y).max(1);
5083                        new.fill(Rect::new(x, y, w, h), cell);
5084                    }
5085                    _ => unreachable!(),
5086                }
5087            }
5088
5089            let full = BufferDiff::compute(&old, &new);
5090            let dirty = BufferDiff::compute_dirty(&old, &new);
5091
5092            prop_assert_eq!(
5093                full.changes(),
5094                dirty.changes(),
5095                "dirty diff (spans) must match full diff; {}",
5096                super::span_diagnostics(&new)
5097            );
5098        });
5099    }
5100
5101    // ========== Idempotence Property (bd-1rz0.6) ==========
5102
5103    // Property: Diff is idempotent - computing diff between identical buffers
5104    // produces empty diff, and applying diff twice has no additional effect.
5105    //
5106    // Invariant: For any buffers A and B:
5107    //   apply(apply(A, diff(A,B)), diff(A,B)) == apply(A, diff(A,B))
5108    #[test]
5109    fn diff_is_idempotent() {
5110        proptest::proptest!(|(
5111            width in 5u16..60,
5112            height in 5u16..30,
5113            num_changes in 0usize..100,
5114        )| {
5115            let mut buf_a = Buffer::new(width, height);
5116            let mut buf_b = Buffer::new(width, height);
5117
5118            // Make buf_b different from buf_a
5119            for i in 0..num_changes {
5120                let x = (i * 13 + 7) as u16 % width;
5121                let y = (i * 17 + 3) as u16 % height;
5122                buf_b.set_raw(x, y, Cell::from_char('X'));
5123            }
5124
5125            // Compute diff from A to B
5126            let diff = BufferDiff::compute(&buf_a, &buf_b);
5127
5128            // Apply diff to A once
5129            for (x, y) in diff.iter() {
5130                let cell = *buf_b.get_unchecked(x, y);
5131                buf_a.set_raw(x, y, cell);
5132            }
5133
5134            // Now buf_a should equal buf_b
5135            let diff_after_first = BufferDiff::compute(&buf_a, &buf_b);
5136            prop_assert!(
5137                diff_after_first.is_empty(),
5138                "After applying diff once, buffers should be identical (diff was {} changes)",
5139                diff_after_first.len()
5140            );
5141
5142            // Apply diff again (should be no-op since buffers are now equal)
5143            let before_second = buf_a.clone();
5144            for (x, y) in diff.iter() {
5145                let cell = *buf_b.get_unchecked(x, y);
5146                buf_a.set_raw(x, y, cell);
5147            }
5148
5149            // Verify no change from second application
5150            let diff_after_second = BufferDiff::compute(&before_second, &buf_a);
5151            prop_assert!(
5152                diff_after_second.is_empty(),
5153                "Second diff application should be a no-op"
5154            );
5155        });
5156    }
5157
5158    // ========== No-Ghosting After Clear Property (bd-1rz0.6) ==========
5159
5160    // Property: After a full buffer clear (simulating resize), diffing
5161    // against a blank old buffer captures all content cells.
5162    //
5163    // This simulates the no-ghosting invariant: when terminal shrinks,
5164    // we present against a fresh blank buffer, ensuring no old content
5165    // persists. The key is that all non-blank cells in the new buffer
5166    // appear in the diff.
5167    //
5168    // Failure mode: If we diff against stale buffer state after resize,
5169    // some cells might be incorrectly marked as unchanged.
5170    #[test]
5171    fn no_ghosting_after_clear() {
5172        proptest::proptest!(|(
5173            width in 10u16..80,
5174            height in 5u16..30,
5175            num_content_cells in 1usize..200,
5176        )| {
5177            // Old buffer is blank (simulating post-resize cleared state)
5178            let old = Buffer::new(width, height);
5179
5180            // New buffer has content (the UI to render)
5181            let mut new = Buffer::new(width, height);
5182            let mut expected_changes = std::collections::HashSet::new();
5183
5184            for i in 0..num_content_cells {
5185                let x = (i * 13 + 7) as u16 % width;
5186                let y = (i * 17 + 3) as u16 % height;
5187                new.set_raw(x, y, Cell::from_char('#'));
5188                expected_changes.insert((x, y));
5189            }
5190
5191            let diff = BufferDiff::compute(&old, &new);
5192
5193            // Every non-blank cell should be in the diff
5194            // This ensures no "ghosting" - all visible content is explicitly rendered
5195            for (x, y) in expected_changes {
5196                let in_diff = diff.iter().any(|(dx, dy)| dx == x && dy == y);
5197                prop_assert!(
5198                    in_diff,
5199                    "Content cell at ({}, {}) missing from diff - would ghost",
5200                    x,
5201                    y
5202                );
5203            }
5204
5205            // Also verify the diff doesn't include any extra cells
5206            for (x, y) in diff.iter() {
5207                let old_cell = old.get_unchecked(x, y);
5208                let new_cell = new.get_unchecked(x, y);
5209                prop_assert!(
5210                    !old_cell.bits_eq(new_cell),
5211                    "Diff includes unchanged cell at ({}, {})",
5212                    x,
5213                    y
5214                );
5215            }
5216        });
5217    }
5218
5219    // ========== Monotonicity Property (bd-1rz0.6) ==========
5220
5221    // Property: Diff changes are monotonically ordered (row-major).
5222    // This ensures deterministic iteration order for presentation.
5223    //
5224    // Invariant: For consecutive changes (x1,y1) and (x2,y2):
5225    //   y1 < y2 OR (y1 == y2 AND x1 < x2)
5226    #[test]
5227    fn diff_changes_are_monotonic() {
5228        proptest::proptest!(|(
5229            width in 10u16..80,
5230            height in 5u16..30,
5231            num_changes in 1usize..200,
5232        )| {
5233            let old = Buffer::new(width, height);
5234            let mut new = old.clone();
5235
5236            // Apply changes in random positions
5237            for i in 0..num_changes {
5238                let x = (i * 37 + 11) as u16 % width;
5239                let y = (i * 53 + 7) as u16 % height;
5240                new.set_raw(x, y, Cell::from_char('M'));
5241            }
5242
5243            let diff = BufferDiff::compute(&old, &new);
5244            let changes: Vec<_> = diff.iter().collect();
5245
5246            // Verify monotonic ordering
5247            for window in changes.windows(2) {
5248                let (x1, y1) = window[0];
5249                let (x2, y2) = window[1];
5250
5251                let is_monotonic = y1 < y2 || (y1 == y2 && x1 < x2);
5252                prop_assert!(
5253                    is_monotonic,
5254                    "Changes not monotonic: ({}, {}) should come before ({}, {})",
5255                    x1,
5256                    y1,
5257                    x2,
5258                    y2
5259                );
5260            }
5261        });
5262    }
5263}
5264
5265#[cfg(test)]
5266mod span_edge_cases {
5267    use super::*;
5268    use crate::cell::Cell;
5269    use proptest::prelude::*;
5270
5271    #[test]
5272    fn test_span_diff_u16_max_width() {
5273        // Test near u16::MAX limit (65535)
5274        let width = 65000;
5275        let height = 1;
5276        let old = Buffer::new(width, height);
5277        let mut new = Buffer::new(width, height);
5278
5279        // We must clear dirty because Buffer::new starts with all rows dirty
5280        new.clear_dirty();
5281
5282        // Set changes at start, middle, end
5283        new.set_raw(0, 0, Cell::from_char('A'));
5284        new.set_raw(32500, 0, Cell::from_char('B'));
5285        new.set_raw(64999, 0, Cell::from_char('C'));
5286
5287        let full = BufferDiff::compute(&old, &new);
5288        let dirty = BufferDiff::compute_dirty(&old, &new);
5289
5290        assert_eq!(full.changes(), dirty.changes());
5291        assert_eq!(full.len(), 3);
5292
5293        // Verify changes are what we expect
5294        let changes = full.changes();
5295        assert!(changes.contains(&(0, 0)));
5296        assert!(changes.contains(&(32500, 0)));
5297        assert!(changes.contains(&(64999, 0)));
5298    }
5299
5300    #[test]
5301    fn test_span_full_row_dirty_overflow() {
5302        let width = 1000;
5303        let height = 1;
5304        let old = Buffer::new(width, height);
5305        let mut new = Buffer::new(width, height);
5306        new.clear_dirty(); // All clean
5307
5308        // Create > 64 spans to force overflow
5309        // DIRTY_SPAN_MAX_SPANS_PER_ROW is 64
5310        for i in 0..70 {
5311            let x = (i * 10) as u16;
5312            new.set_raw(x, 0, Cell::from_char('X'));
5313        }
5314
5315        // Verify it overflowed
5316        let stats = new.dirty_span_stats();
5317        assert!(
5318            stats.rows_full_dirty > 0,
5319            "Should have overflowed to full row"
5320        );
5321        assert_eq!(
5322            stats.rows_with_spans, 0,
5323            "Should have cleared spans on overflow"
5324        );
5325
5326        let full = BufferDiff::compute(&old, &new);
5327        let dirty = BufferDiff::compute_dirty(&old, &new);
5328
5329        assert_eq!(full.changes(), dirty.changes());
5330        assert_eq!(full.len(), 70);
5331    }
5332
5333    #[test]
5334    fn test_span_diff_empty_rows() {
5335        let width = 100;
5336        let height = 10;
5337        let old = Buffer::new(width, height);
5338        let mut new = Buffer::new(width, height);
5339        new.clear_dirty(); // All clean
5340
5341        // No changes
5342        let dirty = BufferDiff::compute_dirty(&old, &new);
5343        assert!(dirty.is_empty());
5344    }
5345
5346    proptest! {
5347        #[test]
5348        fn property_span_diff_equivalence_large(
5349            width in 1000u16..5000,
5350            height in 10u16..50,
5351            changes in proptest::collection::vec((0u16..5000, 0u16..50), 0..100)
5352        ) {
5353            // Cap width/height to avoid OOM in test runner
5354            let w = width.min(2000);
5355            let h = height.min(50);
5356
5357            let old = Buffer::new(w, h);
5358            let mut new = Buffer::new(w, h);
5359            new.clear_dirty();
5360
5361            // Apply changes
5362            for (raw_x, raw_y) in changes {
5363                let x = raw_x % w;
5364                let y = raw_y % h;
5365                new.set_raw(x, y, Cell::from_char('Z'));
5366            }
5367
5368            let full = BufferDiff::compute(&old, &new);
5369            let dirty = BufferDiff::compute_dirty(&old, &new);
5370
5371            prop_assert_eq!(
5372                full.changes(),
5373                dirty.changes(),
5374                "Large buffer mismatch: w={}, h={}, {}",
5375                w,
5376                h,
5377                super::span_diagnostics(&new)
5378            );
5379        }
5380    }
5381
5382    // =========================================================================
5383    // Certificate-based skip hint tests (bd-i71od)
5384    // =========================================================================
5385
5386    #[test]
5387    fn certified_skip_produces_empty_diff() {
5388        let old = Buffer::new(10, 5);
5389        let new = Buffer::new(10, 5);
5390        let mut diff = BufferDiff::new();
5391
5392        diff.compute_certified_into(&old, &new, DiffSkipHint::SkipDiff);
5393        assert!(diff.is_empty(), "SkipDiff should produce zero changes");
5394    }
5395
5396    #[test]
5397    fn certified_full_diff_matches_standard() {
5398        let old = Buffer::new(10, 5);
5399        let mut new = Buffer::new(10, 5);
5400        new.set(3, 2, Cell::from_char('X'));
5401
5402        let mut standard = BufferDiff::new();
5403        standard.compute_dirty_into(&old, &new);
5404
5405        let mut certified = BufferDiff::new();
5406        certified.compute_certified_into(&old, &new, DiffSkipHint::FullDiff);
5407
5408        assert_eq!(
5409            standard.changes(),
5410            certified.changes(),
5411            "FullDiff hint should produce identical results to standard dirty diff"
5412        );
5413    }
5414
5415    #[test]
5416    fn certified_narrow_to_rows_only_diffs_specified_rows() {
5417        let old = Buffer::new(10, 5);
5418        let mut new = Buffer::new(10, 5);
5419        // Change cells in rows 1 and 3
5420        new.set(2, 1, Cell::from_char('A'));
5421        new.set(5, 3, Cell::from_char('B'));
5422        // Also change row 4 (but we won't include it in the hint)
5423        new.set(7, 4, Cell::from_char('C'));
5424
5425        let mut diff = BufferDiff::new();
5426        diff.compute_certified_into(&old, &new, DiffSkipHint::NarrowToRows(vec![1, 3]));
5427
5428        // Should find changes in rows 1 and 3, but NOT row 4
5429        let changes = diff.changes();
5430        assert!(
5431            changes.iter().any(|&(x, y)| x == 2 && y == 1),
5432            "should find change at (2, 1)"
5433        );
5434        assert!(
5435            changes.iter().any(|&(x, y)| x == 5 && y == 3),
5436            "should find change at (5, 3)"
5437        );
5438        assert!(
5439            !changes.iter().any(|&(_, y)| y == 4),
5440            "should NOT find changes in row 4 (not in hint)"
5441        );
5442    }
5443
5444    #[test]
5445    fn certified_narrow_skips_clean_rows() {
5446        let old = Buffer::new(10, 5);
5447        let new = Buffer::new(10, 5);
5448
5449        let mut diff = BufferDiff::new();
5450        diff.compute_certified_into(&old, &new, DiffSkipHint::NarrowToRows(vec![0, 2, 4]));
5451
5452        assert!(
5453            diff.is_empty(),
5454            "narrowing to clean rows should produce zero changes"
5455        );
5456    }
5457
5458    #[test]
5459    fn certified_narrow_unsorted_duplicate_rows_yield_sorted_unique_changes() {
5460        // Regression: unsorted/duplicate hint rows produced duplicated,
5461        // out-of-order changes — breaking the sorted-unique invariant that
5462        // runs() relies on and double-counting changes fed to the diff
5463        // strategy selector.
5464        let old = Buffer::new(10, 5);
5465        let mut new = Buffer::new(10, 5);
5466        new.set(2, 1, Cell::from_char('A'));
5467        new.set(5, 3, Cell::from_char('B'));
5468
5469        let mut diff = BufferDiff::new();
5470        diff.compute_certified_into(&old, &new, DiffSkipHint::NarrowToRows(vec![3, 1, 3, 3]));
5471
5472        assert_eq!(
5473            diff.changes(),
5474            &[(2, 1), (5, 3)],
5475            "changes must be (y,x)-sorted and duplicate-free"
5476        );
5477        let runs = diff.runs();
5478        assert_eq!(runs.len(), 2, "each change coalesces into exactly one run");
5479    }
5480
5481    #[test]
5482    fn fill_full_and_clear_drop_stale_tile_stats() {
5483        // Regression: tile diagnostics from an earlier dirty pass survived
5484        // a full refill / clear and could be misattributed by telemetry.
5485        let old = Buffer::new(8, 2);
5486        let mut new = Buffer::new(8, 2);
5487        new.clear_dirty();
5488        new.set(3, 0, Cell::from_char('x'));
5489
5490        let mut diff = BufferDiff::new();
5491        diff.compute_dirty_into(&old, &new);
5492        // (Whether stats are recorded depends on tile config; the invariant
5493        // under test is only that refill/clear never KEEPS old stats.)
5494        diff.fill_full(8, 2);
5495        assert!(diff.last_tile_stats().is_none(), "fill_full kept stats");
5496
5497        diff.compute_dirty_into(&old, &new);
5498        diff.clear();
5499        assert!(diff.last_tile_stats().is_none(), "clear kept stats");
5500    }
5501
5502    #[test]
5503    fn certified_narrow_out_of_bounds_rows_ignored() {
5504        let old = Buffer::new(10, 5);
5505        let mut new = Buffer::new(10, 5);
5506        new.set(0, 0, Cell::from_char('X'));
5507
5508        let mut diff = BufferDiff::new();
5509        diff.compute_certified_into(
5510            &old,
5511            &new,
5512            DiffSkipHint::NarrowToRows(vec![0, 100, 200]), // 100, 200 are out of bounds
5513        );
5514
5515        assert_eq!(diff.len(), 1, "should find the one change in row 0");
5516        assert_eq!(diff.changes()[0], (0, 0));
5517    }
5518
5519    #[test]
5520    fn diff_skip_hint_labels() {
5521        assert_eq!(DiffSkipHint::FullDiff.label(), "full-diff");
5522        assert_eq!(DiffSkipHint::SkipDiff.label(), "skip-diff");
5523        assert_eq!(DiffSkipHint::NarrowToRows(vec![]).label(), "narrow-to-rows");
5524    }
5525
5526    #[test]
5527    fn diff_skip_hint_skips_work() {
5528        assert!(!DiffSkipHint::FullDiff.skips_work());
5529        assert!(DiffSkipHint::SkipDiff.skips_work());
5530        assert!(DiffSkipHint::NarrowToRows(vec![1]).skips_work());
5531    }
5532}