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