1#![forbid(unsafe_code)]
2
3use crate::buffer::{Buffer, DirtySpan};
42use crate::cell::Cell;
43
44#[derive(Debug, Clone, PartialEq, Eq)]
61pub enum DiffSkipHint {
62 FullDiff,
64 SkipDiff,
66 NarrowToRows(Vec<u16>),
68}
69
70impl DiffSkipHint {
71 #[must_use]
73 pub fn skips_work(&self) -> bool {
74 !matches!(self, Self::FullDiff)
75 }
76
77 #[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
88const BLOCK_SIZE: usize = 4;
96
97const _: () = assert!(
99 core::mem::size_of::<Cell>() * BLOCK_SIZE == 64,
100 "BLOCK_SIZE * Cell must equal 64-byte cache line"
101);
102
103const _: () = assert!(
106 core::mem::align_of::<Cell>() >= 16,
107 "Cell alignment must be >= 16 for SIMD access"
108);
109
110const ROW_BLOCK_SIZE: usize = 32;
114
115#[repr(C, align(64))]
121#[allow(dead_code)]
122struct CacheLineBlock {
123 cells: [Cell; BLOCK_SIZE],
124}
125
126const _: () = 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#[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 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 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 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#[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#[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#[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
370const 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#[derive(Debug, Clone)]
436pub struct TileDiffConfig {
437 pub enabled: bool,
439 pub tile_w: u16,
441 pub tile_h: u16,
443 pub skip_clean_rows: bool,
448 pub min_cells_for_tiles: usize,
450 pub dense_cell_ratio: f64,
452 pub dense_tile_ratio: f64,
454 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 #[must_use]
476 pub fn with_enabled(mut self, enabled: bool) -> Self {
477 self.enabled = enabled;
478 self
479 }
480
481 #[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 #[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 #[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 #[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 #[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 #[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#[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#[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#[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 pub skipped_tile_rows: usize,
597 pub sat_queries: usize,
599 pub fallback: Option<TileDiffFallback>,
600}
601
602#[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#[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#[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#[derive(Debug, Clone)]
634pub enum TileDiffBuild<'a> {
635 UseTiles(TileDiffPlan<'a>),
636 Fallback(TileDiffStats),
637}
638
639impl TileDiffPlan<'_> {
640 #[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 #[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 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 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 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_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 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 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 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1340pub struct ChangeRun {
1341 pub y: u16,
1343 pub x0: u16,
1345 pub x1: u16,
1347}
1348
1349impl ChangeRun {
1350 #[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 #[inline]
1359 pub const fn len(&self) -> usize {
1360 self.x1.saturating_sub(self.x0) as usize + 1
1361 }
1362
1363 #[inline]
1365 pub const fn is_empty(&self) -> bool {
1366 self.x1 < self.x0
1367 }
1368}
1369
1370#[derive(Debug, Clone, Default)]
1374pub struct BufferDiff {
1375 changes: Vec<(u16, u16)>,
1377 tile_builder: TileDiffBuilder,
1379 tile_config: TileDiffConfig,
1381 last_tile_stats: Option<TileDiffStats>,
1383}
1384
1385impl BufferDiff {
1386 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 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 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 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 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 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 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 pub fn compute_certified_into(&mut self, old: &Buffer, new: &Buffer, hint: DiffSkipHint) {
1528 match hint {
1529 DiffSkipHint::FullDiff => {
1530 self.compute_dirty_into(old, new);
1532 }
1533 DiffSkipHint::SkipDiff => {
1534 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 self.changes.clear();
1547 self.last_tile_stats = None;
1548
1549 let w = old.width();
1550 let h = old.height();
1551 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 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 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 self.last_tile_stats = None;
1617 }
1618
1619 #[inline]
1621 pub fn len(&self) -> usize {
1622 self.changes.len()
1623 }
1624
1625 #[inline]
1627 pub fn is_empty(&self) -> bool {
1628 self.changes.is_empty()
1629 }
1630
1631 #[inline]
1633 pub fn changes(&self) -> &[(u16, u16)] {
1634 &self.changes
1635 }
1636
1637 #[inline]
1639 pub fn last_tile_stats(&self) -> Option<TileDiffStats> {
1640 self.last_tile_stats
1641 }
1642
1643 #[inline]
1645 pub fn tile_config_mut(&mut self) -> &mut TileDiffConfig {
1646 &mut self.tile_config
1647 }
1648
1649 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 let sorted = &self.changes;
1666 let len = sorted.len();
1667
1668 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 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 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 #[inline]
1739 pub fn iter(&self) -> impl Iterator<Item = (u16, u16)> + '_ {
1740 self.changes.iter().copied()
1741 }
1742
1743 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 new.clear_dirty();
1816 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 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 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 new.set_raw(0, 0, Cell::from_char('A'));
1872 new.set_raw(1, 0, Cell::from_char('B'));
1873 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 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 assert_eq!(runs[0].y, 0);
1920 assert_eq!(runs[0].x0, 0);
1921 assert_eq!(runs[0].x1, 1);
1922
1923 assert_eq!(runs[1].y, 2);
1925 assert_eq!(runs[1].x0, 5);
1926 assert_eq!(runs[1].x1, 5);
1927
1928 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 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 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 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 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 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 #[test]
2093 fn block_scan_alignment_exact_block() {
2094 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 let old = Buffer::new(7, 1);
2108 let mut new = Buffer::new(7, 1);
2109 new.set_raw(1, 0, Cell::from_char('A'));
2111 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 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 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 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 let old = Buffer::new(80, 1);
2161 let mut new = Buffer::new(80, 1);
2162
2163 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 let old = Buffer::new(20, 1);
2192 let mut new = Buffer::new(20, 1);
2193
2194 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 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 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 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 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 #[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 #[test]
2309 fn unit_run_coalescing_invariants() {
2310 let old = Buffer::new(80, 24);
2313 let mut new = Buffer::new(80, 24);
2314
2315 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 for x in 40..=45 {
2324 new.set_raw(x, 5, Cell::from_char('C'));
2325 }
2326 new.set_raw(79, 23, Cell::from_char('Z'));
2328
2329 let diff = BufferDiff::compute(&old, &new);
2330 let runs = diff.runs();
2331
2332 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 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 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 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 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 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 for x in 0..width {
2394 buf.set_raw(x, 0, Cell::from_char('='));
2395 }
2396
2397 for x in 0..width {
2399 buf.set_raw(x, height - 1, Cell::from_char('-'));
2400 }
2401
2402 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 let diff2 = BufferDiff::compute(&old, &new);
2427 assert_eq!(
2428 fnv1a_hash(diff2.changes()),
2429 checksum,
2430 "diff must be deterministic"
2431 );
2432
2433 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 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 let diff2 = BufferDiff::compute(&old, &new);
2461 assert_eq!(fnv1a_hash(diff2.changes()), checksum);
2462
2463 assert!(
2465 diff.len() >= 240,
2466 "120x40 golden scene should have >=240 changes, got {}",
2467 diff.len()
2468 );
2469
2470 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 let old = build_golden_scene(80, 24, 0x000D_01DE_5EED_0003);
2483 let mut new = old.clone();
2484
2485 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 let diff2 = BufferDiff::compute(&old, &new);
2497 assert_eq!(fnv1a_hash(diff2.changes()), checksum);
2498
2499 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 #[test]
2517 fn e2e_random_scene_replay() {
2518 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 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 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 #[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 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 let budget_us = match (width, height) {
2634 (80, 24) => 500, (120, 40) => 1000, _ => 2000,
2637 };
2638
2639 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 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 #[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 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 assert!(
2926 stats_full.sat_build_cells > 0,
2927 "full scan should process cells, got 0"
2928 );
2929 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 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 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 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 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 #[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 prop_assert_eq!(plan.tile_row_dirty(plan.params.tiles_y), 0);
3160 Ok(())
3161 })?;
3162 }
3163
3164 #[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 #[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 #[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 #[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 #[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; assert_eq!(run, copied);
3353 let cloned: ChangeRun = run; 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 #[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 #[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; assert_eq!(a, b);
3427 let c: TileDiffFallback = a; 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 #[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]; 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 let mut builder = TileDiffBuilder::new();
3463 let config = TileDiffConfig::default()
3464 .with_min_cells_for_tiles(0)
3465 .with_dense_cell_ratio(0.10); let w = 20u16;
3468 let h = 10u16;
3469 let total = (w as usize) * (h as usize);
3470 let dirty_count = total / 10; 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 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 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 #[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, tiles_y: 7, };
3550 assert_eq!(params.total_tiles(), 49);
3551 assert_eq!(params.total_cells(), 5000);
3552 }
3553
3554 #[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; 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 assert_eq!(stats.tile_w, 16);
3588 assert_eq!(stats.tile_h, 8);
3589 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 let copy = stats;
3599 assert_eq!(copy.width, stats.width);
3600 }
3601 _ => unreachable!("expected UseTiles"),
3602 }
3603 }
3604
3605 #[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, tile_h: 0, 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]; 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, tile_h: 100, 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 #[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 #[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 #[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 #[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 let stats = diff.last_tile_stats().expect("should have tile stats");
3795 assert_eq!(stats.fallback, Some(TileDiffFallback::SmallScreen));
3796 }
3797
3798 #[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 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 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 #[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 #[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); let dirty_count = total / 4; 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); let dirty_count = total / 4 - 1; 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(_) => { }
3949 }
3950 }
3951
3952 #[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 #[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 #[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; 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 #[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 #[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 for y in 0..5u16 {
4064 new.set_raw(0, y, Cell::default());
4065 }
4066 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 #[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 #[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 #[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; assert_eq!(copy.width, params.width);
4127 let cloned: TileParams = params; assert_eq!(cloned.tiles_x, params.tiles_x);
4129 }
4130
4131 #[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; assert_eq!(cloned.height, stats.height);
4156 }
4157 _ => unreachable!("expected Fallback for 1x1"),
4158 }
4159 }
4160
4161 #[test]
4166 fn compute_dirty_with_targeted_spans() {
4167 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 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 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 new.set_raw(0, 0, Cell::from_char('A'));
4201 new.set_raw(1, 0, Cell::from_char('B'));
4202 new.set_raw(40, 2, Cell::from_char('C'));
4204 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 let old = Buffer::new(20, 3);
4218 let mut new = old.clone();
4219 new.clear_dirty();
4220
4221 new.set_raw(5, 1, Cell::default());
4223 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 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 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 #[test]
4258 fn tile_diff_with_dirty_spans_matches_full() {
4259 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 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 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 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 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 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 #[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 dirty_bits[0] = 1; dirty_bits[8 + 8 * w as usize] = 1; 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 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 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 assert_eq!(plan.tile_counts.len(), plan.params.total_tiles());
4416
4417 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 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 #[test]
4439 fn dense_tiles_exact_threshold_triggers_fallback() {
4440 let mut builder = TileDiffBuilder::new();
4441 let w = 32u16;
4442 let h = 32u16;
4443 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 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 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 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 #[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 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 for x in 0..20u16 {
4569 buf.set_raw(x, 0, Cell::from_char('X'));
4570 }
4571 let diag = span_diagnostics(&buf);
4572 assert!(
4574 diag.contains("stats="),
4575 "diagnostics should include stats: {diag}"
4576 );
4577 }
4578
4579 #[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 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 let mut runs_buf: Vec<ChangeRun> = Vec::new();
4633
4634 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 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 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)); 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 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 new.set_raw(7, 0, Cell::from_char('A')); new.set_raw(8, 0, Cell::from_char('B')); new.set_raw(15, 0, Cell::from_char('C')); new.set_raw(16, 0, Cell::from_char('D')); 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 #[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 let old = Buffer::new(width, height);
4719
4720 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 let diff = BufferDiff::compute(&old, &new);
4731
4732 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 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 #[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 #[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 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 #[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 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 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 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 #[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 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 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 #[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 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 #[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 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 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 #[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 (Just(0u8), any::<u16>(), any::<u16>(), any::<char>()),
4992 (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 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 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 #[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 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 let diff = BufferDiff::compute(&buf_a, &buf_b);
5059
5060 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 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 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 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 #[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 let old = Buffer::new(width, height);
5111
5112 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 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 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 #[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 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 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 let width = 65000;
5207 let height = 1;
5208 let old = Buffer::new(width, height);
5209 let mut new = Buffer::new(width, height);
5210
5211 new.clear_dirty();
5213
5214 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 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(); 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 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(); 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 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 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 #[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 new.set(2, 1, Cell::from_char('A'));
5353 new.set(5, 3, Cell::from_char('B'));
5354 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 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 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 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 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]), );
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}