Skip to main content

ftui_render/
diff.rs

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