Skip to main content

ftui_widgets/
virtualized.rs

1#![forbid(unsafe_code)]
2
3//! Virtualization primitives for efficient rendering of large content.
4//!
5//! This module provides the foundational types for rendering only visible
6//! portions of large datasets, enabling smooth performance with 100K+ items.
7//!
8//! # Core Types
9//!
10//! - [`Virtualized<T>`] - Generic container with visible range calculation
11//! - [`VirtualizedStorage`] - Owned vs external storage abstraction
12//! - [`ItemHeight`] - Fixed vs variable height support
13//! - [`HeightCache`] - LRU cache for measured item heights
14//!
15//! # Example
16//!
17//! ```ignore
18//! use ftui_widgets::virtualized::{Virtualized, ItemHeight};
19//!
20//! // Create with owned storage
21//! let mut virt: Virtualized<String> = Virtualized::new(10_000);
22//!
23//! // Add items
24//! for i in 0..1000 {
25//!     virt.push(format!("Line {}", i));
26//! }
27//!
28//! // Get visible range for viewport height
29//! let range = virt.visible_range(24);
30//! println!("Visible: {}..{}", range.start, range.end);
31//! ```
32
33use std::cell::Cell as StdCell;
34use std::collections::VecDeque;
35use std::ops::Range;
36use std::time::Duration;
37
38use crate::scrollbar::{Scrollbar, ScrollbarOrientation, ScrollbarState};
39use crate::{StatefulWidget, clear_text_area};
40use ftui_core::geometry::Rect;
41use ftui_render::cell::Cell;
42use ftui_render::frame::Frame;
43use ftui_style::Style;
44
45/// A virtualized content container that tracks scroll state and computes visible ranges.
46///
47/// # Design Rationale
48/// - Generic over item type for flexibility
49/// - Supports both owned storage and external data sources
50/// - Computes visible ranges for O(visible) rendering
51/// - Optional overscan for smooth scrolling
52/// - Momentum scrolling support
53#[derive(Debug, Clone)]
54pub struct Virtualized<T> {
55    /// The stored items (or external storage reference).
56    storage: VirtualizedStorage<T>,
57    /// Current scroll offset (in items).
58    scroll_offset: usize,
59    /// Number of visible items (cached from last render).
60    visible_count: StdCell<usize>,
61    /// Overscan: extra items rendered above/below visible.
62    overscan: usize,
63    /// Height calculation strategy.
64    item_height: ItemHeight,
65    /// Whether to auto-scroll on new items.
66    follow_mode: bool,
67    /// Scroll velocity for momentum scrolling.
68    scroll_velocity: f32,
69}
70
71/// Storage strategy for virtualized items.
72#[derive(Debug, Clone)]
73pub enum VirtualizedStorage<T> {
74    /// Owned vector of items.
75    Owned(VecDeque<T>),
76    /// External storage with known length.
77    /// Note: External fetch is handled at the widget level.
78    External {
79        /// Total number of items available.
80        len: usize,
81        /// Maximum items to keep in local cache.
82        cache_capacity: usize,
83    },
84}
85
86/// Height calculation strategy for items.
87#[derive(Debug, Clone)]
88pub enum ItemHeight {
89    /// All items have fixed height.
90    Fixed(u16),
91    /// Legacy variable-height mode: an LRU cache of measured heights and a
92    /// linear scan per `visible_range`. Kept for callers that want bounded
93    /// memory over a sliding window; new code should use
94    /// [`Virtualized::with_variable_heights`] (Fenwick).
95    Variable(HeightCache),
96    /// Items have variable height with O(log n) scroll-to-index via Fenwick
97    /// tree; the default variable-height strategy.
98    VariableFenwick(VariableHeightsFenwick),
99}
100
101/// LRU cache for measured item heights.
102#[derive(Debug, Clone)]
103pub struct HeightCache {
104    /// Height measurements indexed by (item index - base_offset).
105    cache: Vec<Option<u16>>,
106    /// Offset of the first entry in the cache (cache[0] corresponds to this item index).
107    base_offset: usize,
108    /// Default height for unmeasured items.
109    default_height: u16,
110    /// Maximum entries to cache (for memory bounds).
111    capacity: usize,
112}
113
114impl<T> Virtualized<T> {
115    /// Create a new virtualized container with owned storage.
116    ///
117    /// # Arguments
118    /// * `capacity` - Maximum items to retain in memory.
119    #[must_use]
120    pub fn new(capacity: usize) -> Self {
121        Self {
122            storage: VirtualizedStorage::Owned(VecDeque::with_capacity(capacity.min(1024))),
123            scroll_offset: 0,
124            visible_count: StdCell::new(0),
125            overscan: 2,
126            item_height: ItemHeight::Fixed(1),
127            follow_mode: false,
128            scroll_velocity: 0.0,
129        }
130    }
131
132    /// Create with external storage reference.
133    #[must_use]
134    pub fn external(len: usize, cache_capacity: usize) -> Self {
135        Self {
136            storage: VirtualizedStorage::External {
137                len,
138                cache_capacity,
139            },
140            scroll_offset: 0,
141            visible_count: StdCell::new(0),
142            overscan: 2,
143            item_height: ItemHeight::Fixed(1),
144            follow_mode: false,
145            scroll_velocity: 0.0,
146        }
147    }
148
149    /// Set item height strategy.
150    #[must_use]
151    pub fn with_item_height(mut self, height: ItemHeight) -> Self {
152        self.item_height = height;
153        self
154    }
155
156    /// Set fixed item height.
157    #[must_use]
158    pub fn with_fixed_height(mut self, height: u16) -> Self {
159        self.item_height = ItemHeight::Fixed(height);
160        self
161    }
162
163    /// Predict the heights of unmeasured items with a Bayesian model instead
164    /// of a constant default (see [`VariableHeightsFenwick::with_predictor`]).
165    ///
166    /// Switches the height strategy to the Fenwick tracker when it is not one
167    /// already (a fixed height becomes the tracker's default; a linear
168    /// [`HeightCache`] is replaced, dropping its cached measurements). Heights
169    /// recorded through [`Virtualized::observe_height`] train the model.
170    #[must_use]
171    pub fn with_height_prediction(mut self, config: PredictorConfig) -> Self {
172        let len = self.len();
173        let current = std::mem::replace(&mut self.item_height, ItemHeight::Fixed(1));
174        self.item_height = ItemHeight::VariableFenwick(match current {
175            ItemHeight::VariableFenwick(tracker) => tracker.with_predictor(config),
176            ItemHeight::Fixed(height) => {
177                VariableHeightsFenwick::new(height.max(1), len).with_predictor(config)
178            }
179            ItemHeight::Variable(cache) => {
180                VariableHeightsFenwick::new(cache.default_height, len).with_predictor(config)
181            }
182        });
183        self
184    }
185
186    /// Record the measured height of item `idx`.
187    ///
188    /// A no-op for the fixed-height strategy. With a predictor attached this
189    /// also trains the height model, so unmeasured items follow what has been
190    /// measured instead of a constant guess.
191    pub fn observe_height(&mut self, idx: usize, height: u16) {
192        self.observe_height_in_category(idx, height, 0);
193    }
194
195    /// Record a measured height and its category, including externally stored
196    /// items whose category cannot be obtained through [`Self::get`].
197    pub fn observe_height_in_category(&mut self, idx: usize, height: u16, category: usize) {
198        match &mut self.item_height {
199            ItemHeight::Fixed(_) => {}
200            ItemHeight::Variable(cache) => cache.set(idx, height),
201            ItemHeight::VariableFenwick(tracker) => tracker.set_in_category(idx, height, category),
202        }
203    }
204
205    /// Point prediction for a category, or the configured height without a model.
206    #[must_use]
207    pub fn predicted_height(&self, category: usize) -> u16 {
208        if let ItemHeight::VariableFenwick(tracker) = &self.item_height
209            && let Some(predictor) = tracker.predictor()
210        {
211            return predictor.predict(category).predicted.max(1);
212        }
213        self.unmeasured_item_height()
214    }
215
216    /// Statistics from actual height observations, when prediction is enabled.
217    #[must_use]
218    pub fn predictor_stats(&self) -> Option<PredictorStats> {
219        match &self.item_height {
220            ItemHeight::VariableFenwick(tracker) => tracker.predictor().map(HeightPredictor::stats),
221            _ => None,
222        }
223    }
224
225    /// Height assumed for items that have not been measured yet: the
226    /// predictor's current point estimate when one is attached, otherwise
227    /// the strategy's default (or the fixed height).
228    #[must_use]
229    pub fn unmeasured_item_height(&self) -> u16 {
230        match &self.item_height {
231            ItemHeight::Fixed(height) => *height,
232            ItemHeight::Variable(cache) => cache.default_height,
233            ItemHeight::VariableFenwick(tracker) => tracker.predicted_height(),
234        }
235    }
236
237    /// Use variable item heights (Fenwick-tracked, the default strategy):
238    /// unmeasured rows count `default_height`, `observe_height` records
239    /// real ones, and offsets, `scroll_to` and `visible_range` stay
240    /// O(log n). The tracker is sized to the current length and follows the
241    /// items: it grows with `push` (a tracker pre-filled with more heights
242    /// than items keeps them), shifts on `trim_front`, clears on `clear`
243    /// and matches `set_external_len` exactly.
244    #[must_use]
245    pub fn with_variable_heights(mut self, default_height: u16) -> Self {
246        let len = self.len();
247        self.item_height =
248            ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, len));
249        self
250    }
251
252    /// Variable heights with an explicit initial tracker capacity (the
253    /// tracker still follows the item count afterwards). Prefer
254    /// [`Self::with_variable_heights`] unless the list is filled in bulk
255    /// after construction.
256    #[must_use]
257    pub fn with_variable_heights_fenwick(mut self, default_height: u16, capacity: usize) -> Self {
258        self.item_height =
259            ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, capacity));
260        self
261    }
262
263    /// Keep a Fenwick tracker's length in step with the item count: grow it
264    /// (`exact == false`, used by `push`, so a tracker pre-filled with more
265    /// heights than items keeps them) or set it exactly (`exact == true`,
266    /// used by `set_external_len`).
267    fn sync_height_tracker(&mut self, exact: bool) {
268        let len = self.len();
269        if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height
270            && (tracker.len() < len || (exact && tracker.len() != len))
271        {
272            tracker.resize(len);
273        }
274    }
275
276    /// Set overscan amount.
277    #[must_use]
278    pub fn with_overscan(mut self, overscan: usize) -> Self {
279        self.overscan = overscan;
280        self
281    }
282
283    /// Enable follow mode.
284    #[must_use]
285    pub fn with_follow(mut self, follow: bool) -> Self {
286        self.follow_mode = follow;
287        self
288    }
289
290    /// Get total number of items.
291    #[must_use]
292    pub fn len(&self) -> usize {
293        match &self.storage {
294            VirtualizedStorage::Owned(items) => items.len(),
295            VirtualizedStorage::External { len, .. } => *len,
296        }
297    }
298
299    /// Check if empty.
300    #[must_use]
301    pub fn is_empty(&self) -> bool {
302        self.len() == 0
303    }
304
305    /// Get current scroll offset.
306    ///
307    /// The internal sentinel value (`usize::MAX`, used for lazy scroll-to-bottom)
308    /// is clamped to the actual item count so callers never see it.
309    #[must_use]
310    pub fn scroll_offset(&self) -> usize {
311        self.scroll_offset.min(self.len().saturating_sub(1))
312    }
313
314    /// Get current visible count (from last render).
315    #[must_use]
316    pub fn visible_count(&self) -> usize {
317        self.visible_count.get()
318    }
319
320    /// Check if follow mode is enabled.
321    #[must_use]
322    pub fn follow_mode(&self) -> bool {
323        self.follow_mode
324    }
325
326    /// Calculate visible range for given viewport height.
327    #[must_use]
328    pub fn visible_range(&self, viewport_height: u16) -> Range<usize> {
329        if self.is_empty() || viewport_height == 0 {
330            self.visible_count.set(0);
331            return 0..0;
332        }
333
334        let items_visible = match &self.item_height {
335            // Use div_ceil to include partially visible items
336            ItemHeight::Fixed(h) if *h > 0 => viewport_height.div_ceil(*h) as usize,
337            ItemHeight::Fixed(_) => viewport_height as usize,
338            ItemHeight::Variable(cache) => {
339                // Sum heights until we fill or exceed viewport
340                let len = self.len();
341                let start = self.scroll_offset.min(len.saturating_sub(1));
342                let mut count = 0;
343                let mut total_height = 0u16;
344                while start + count < len {
345                    let next = cache.get(start + count);
346
347                    // Always include the item
348                    total_height = total_height.saturating_add(next);
349                    count += 1;
350
351                    // Stop if we've filled the viewport
352                    if total_height >= viewport_height {
353                        break;
354                    }
355                }
356                if total_height < viewport_height && start > 0 {
357                    // The tail from `start` cannot fill the viewport (e.g.
358                    // after scroll_to_bottom's lazy sentinel, or an offset
359                    // near the end). Anchor to the bottom like the Fixed arm:
360                    // count the trailing items that fit, so the clamped start
361                    // below shows a full last screenful instead of blank rows.
362                    count = 0;
363                    total_height = 0;
364                    while count < len {
365                        let next = cache.get(len - 1 - count);
366                        total_height = total_height.saturating_add(next);
367                        count += 1;
368                        if total_height >= viewport_height {
369                            break;
370                        }
371                    }
372                }
373                count
374            }
375            ItemHeight::VariableFenwick(tracker) => {
376                // O(log n) using Fenwick tree
377                let len = self.len();
378                let start = self.scroll_offset.min(len.saturating_sub(1));
379                let total = tracker.total_height_exact();
380                let suffix = total.saturating_sub(tracker.offset_of_item_exact(start));
381                if suffix < u64::from(viewport_height) {
382                    // Same bottom anchoring as the Variable arm, in O(log n):
383                    // when the last screenful is shown, its first (possibly
384                    // partially visible) item contains offset total-viewport.
385                    let anchor = total.saturating_sub(u64::from(viewport_height));
386                    len.saturating_sub(tracker.find_item_at_offset_exact(anchor))
387                        .max(1)
388                } else {
389                    tracker.visible_count(start, viewport_height).max(1)
390                }
391            }
392        };
393
394        let max_offset = self.len().saturating_sub(items_visible);
395        let start = self.scroll_offset.min(max_offset);
396        let end = start.saturating_add(items_visible).min(self.len());
397        self.visible_count.set(items_visible);
398        start..end
399    }
400
401    /// Get render range with overscan for smooth scrolling.
402    #[must_use]
403    pub fn render_range(&self, viewport_height: u16) -> Range<usize> {
404        let visible = self.visible_range(viewport_height);
405        let start = visible.start.saturating_sub(self.overscan);
406        let end = visible.end.saturating_add(self.overscan).min(self.len());
407        start..end
408    }
409
410    /// Scroll by delta (positive = down/forward).
411    pub fn scroll(&mut self, delta: i32) {
412        if self.is_empty() {
413            return;
414        }
415        // `visible_count` is a cache written by the last `visible_range`, taken
416        // at whatever offset was showing then. With variable heights the number
417        // of items that fit depends on position, so a count measured near the
418        // top clamps the ceiling too low and the list stalls before the end —
419        // holding the down key over `[1, 1, 4, 4]` at viewport 4 stopped at
420        // offset 1 even though offset 3 is valid and shows the final item.
421        //
422        // Only fixed heights can trust the count, because there it cannot vary
423        // with position. Otherwise allow any real index and let `visible_range`
424        // apply the true ceiling, which it recomputes for the current offset.
425        let visible_count = self.visible_count.get();
426        let max_offset = match self.item_height {
427            ItemHeight::Fixed(_) if visible_count > 0 => self.len().saturating_sub(visible_count),
428            _ => self.len().saturating_sub(1),
429        };
430        // Clamp current offset BEFORE adding delta, so lazy MAX doesn't swallow negative deltas
431        let clamped_current = self.scroll_offset.min(max_offset);
432        let new_offset = clamped_current
433            .saturating_add_signed(delta as isize)
434            .min(max_offset);
435        self.scroll_offset = new_offset;
436
437        // Disable follow mode on manual scroll
438        if delta != 0 {
439            self.follow_mode = false;
440        }
441    }
442
443    /// Scroll to specific item index.
444    pub fn scroll_to(&mut self, idx: usize) {
445        self.scroll_offset = idx.min(self.len().saturating_sub(1));
446        self.follow_mode = false;
447    }
448
449    /// Scroll to bottom.
450    pub fn scroll_to_bottom(&mut self) {
451        if self.is_empty() {
452            self.scroll_offset = 0;
453            return;
454        }
455
456        // With variable heights, how many items fit depends on *where* in the
457        // list you are, and `visible_count` was measured at the previous
458        // offset. Subtracting a count taken near the top lands short of the
459        // end when the trailing items are taller, leaving the final item off
460        // screen — which is what happens when a list renders and the user then
461        // presses End. Defer to `visible_range`, whose bottom-anchoring arm
462        // measures from the end instead.
463        //
464        // Fixed heights keep the concrete offset: the count cannot vary with
465        // position, so it is always right, and callers reading
466        // `scroll_offset()` still see a real index.
467        if !matches!(self.item_height, ItemHeight::Fixed(_)) {
468            self.scroll_offset = usize::MAX;
469            return;
470        }
471
472        let visible_count = self.visible_count.get();
473        if visible_count == 0 {
474            // Viewport unknown; keep a sentinel and let `visible_range` clamp lazily.
475            self.scroll_offset = usize::MAX;
476        } else if self.len() > visible_count {
477            self.scroll_offset = self.len().saturating_sub(visible_count);
478        } else {
479            self.scroll_offset = 0;
480        }
481    }
482
483    /// Scroll to top.
484    pub fn scroll_to_top(&mut self) {
485        self.scroll_offset = 0;
486        self.follow_mode = false;
487    }
488
489    /// Alias for scroll_to_top (Home key).
490    pub fn scroll_to_start(&mut self) {
491        self.scroll_to_top();
492    }
493
494    /// Scroll to bottom and enable follow mode (End key).
495    pub fn scroll_to_end(&mut self) {
496        self.scroll_to_bottom();
497        self.follow_mode = true;
498    }
499
500    /// Page up (scroll by visible count - 1).
501    pub fn page_up(&mut self) {
502        let visible_count = self.visible_count.get();
503        if visible_count > 0 {
504            let step = if visible_count > 1 {
505                visible_count - 1
506            } else {
507                1
508            };
509            let delta = i32::try_from(step).unwrap_or(i32::MAX);
510            self.scroll(-delta);
511        }
512    }
513
514    /// Page down (scroll by visible count - 1).
515    pub fn page_down(&mut self) {
516        let visible_count = self.visible_count.get();
517        if visible_count > 0 {
518            let step = if visible_count > 1 {
519                visible_count - 1
520            } else {
521                1
522            };
523            let delta = i32::try_from(step).unwrap_or(i32::MAX);
524            self.scroll(delta);
525        }
526    }
527
528    /// Set follow mode.
529    pub fn set_follow(&mut self, follow: bool) {
530        self.follow_mode = follow;
531        if follow {
532            self.scroll_to_bottom();
533        }
534    }
535
536    /// Check if scrolled to bottom.
537    #[must_use]
538    pub fn is_at_bottom(&self) -> bool {
539        let visible_count = self.visible_count.get();
540        if self.len() <= visible_count {
541            true
542        } else {
543            self.scroll_offset >= self.len().saturating_sub(visible_count)
544        }
545    }
546
547    /// Start momentum scroll.
548    pub fn fling(&mut self, velocity: f32) {
549        self.scroll_velocity = velocity;
550    }
551
552    /// Apply momentum scroll tick.
553    pub fn tick(&mut self, dt: Duration) {
554        if self.scroll_velocity.abs() > 0.1 {
555            let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
556            if delta != 0 {
557                self.scroll(delta);
558            }
559            // Apply friction
560            self.scroll_velocity *= 0.95;
561        } else {
562            self.scroll_velocity = 0.0;
563        }
564    }
565
566    /// Update visible count (called during render).
567    pub fn set_visible_count(&self, count: usize) {
568        self.visible_count.set(count);
569    }
570
571    /// Get reference to the item height strategy.
572    #[must_use]
573    pub fn item_height(&self) -> &ItemHeight {
574        &self.item_height
575    }
576
577    /// Get mutable reference to the item height strategy.
578    ///
579    /// Useful for updating variable height trackers (e.g. resizing Fenwick tree)
580    /// when items are added.
581    pub fn item_height_mut(&mut self) -> &mut ItemHeight {
582        &mut self.item_height
583    }
584}
585
586impl<T> Virtualized<T> {
587    /// Push an item (owned storage only).
588    pub fn push(&mut self, item: T) {
589        if let VirtualizedStorage::Owned(items) = &mut self.storage {
590            items.push_back(item);
591            self.sync_height_tracker(false);
592            if self.follow_mode {
593                self.scroll_to_bottom();
594            }
595        }
596    }
597
598    /// Get item by index (owned storage only).
599    #[must_use = "use the returned item (if any)"]
600    pub fn get(&self, idx: usize) -> Option<&T> {
601        if let VirtualizedStorage::Owned(items) = &self.storage {
602            items.get(idx)
603        } else {
604            None
605        }
606    }
607
608    /// Get mutable item by index (owned storage only).
609    #[must_use = "use the returned item (if any)"]
610    pub fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
611        if let VirtualizedStorage::Owned(items) = &mut self.storage {
612            items.get_mut(idx)
613        } else {
614            None
615        }
616    }
617
618    /// Clear all items (owned storage only).
619    pub fn clear(&mut self) {
620        if let VirtualizedStorage::Owned(items) = &mut self.storage {
621            items.clear();
622            match &mut self.item_height {
623                ItemHeight::Fixed(_) => {}
624                ItemHeight::Variable(cache) => cache.clear(),
625                ItemHeight::VariableFenwick(tracker) => tracker.clear(),
626            }
627        }
628        self.scroll_offset = 0;
629    }
630
631    /// Trim items from the front to keep at most `max` items (owned storage only).
632    ///
633    /// Returns the number of items removed.
634    pub fn trim_front(&mut self, max: usize) -> usize {
635        if let VirtualizedStorage::Owned(items) = &mut self.storage
636            && items.len() > max
637        {
638            let to_remove = items.len() - max;
639            items.drain(..to_remove);
640            // Every surviving item moved down by `to_remove`, so a height
641            // tracker that keeps its old indices now reports each measurement
642            // against a different item.
643            match &mut self.item_height {
644                ItemHeight::Fixed(_) => {}
645                ItemHeight::Variable(cache) => cache.drop_front(to_remove),
646                ItemHeight::VariableFenwick(tracker) => tracker.drop_front(to_remove),
647            }
648            // Adjust scroll_offset if it was pointing beyond the new start
649            self.scroll_offset = self.scroll_offset.saturating_sub(to_remove);
650            return to_remove;
651        }
652        0
653    }
654
655    /// Iterate over items (owned storage only).
656    /// Returns empty iterator for external storage.
657    pub fn iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
658        match &self.storage {
659            VirtualizedStorage::Owned(items) => Box::new(items.iter()),
660            VirtualizedStorage::External { .. } => Box::new(std::iter::empty()),
661        }
662    }
663
664    /// Update external storage length.
665    pub fn set_external_len(&mut self, len: usize) {
666        if let VirtualizedStorage::External { len: l, .. } = &mut self.storage {
667            *l = len;
668            self.sync_height_tracker(true);
669            if self.follow_mode {
670                self.scroll_to_bottom();
671            }
672        }
673    }
674}
675
676impl Default for HeightCache {
677    fn default() -> Self {
678        Self::new(1, 1000)
679    }
680}
681
682impl HeightCache {
683    /// Create a new height cache.
684    #[must_use]
685    pub fn new(default_height: u16, capacity: usize) -> Self {
686        Self {
687            cache: Vec::new(),
688            base_offset: 0,
689            default_height,
690            capacity,
691        }
692    }
693
694    /// Get height for item, returning default if not cached.
695    #[must_use]
696    pub fn get(&self, idx: usize) -> u16 {
697        if idx < self.base_offset {
698            return self.default_height;
699        }
700        let local = idx - self.base_offset;
701        self.cache
702            .get(local)
703            .and_then(|h| *h)
704            .unwrap_or(self.default_height)
705    }
706
707    /// Set height for item.
708    pub fn set(&mut self, idx: usize, height: u16) {
709        if self.capacity == 0 {
710            return;
711        }
712        if idx < self.base_offset {
713            // Index has been trimmed away; ignore
714            return;
715        }
716        let mut local = idx - self.base_offset;
717
718        // If the jump is so large that we'd drain the entire current cache anyway,
719        // reset the window to avoid a huge allocation of Nones.
720        if local + 1 >= self.cache.len() + self.capacity {
721            self.base_offset = idx.saturating_add(1).saturating_sub(self.capacity);
722            self.cache.clear();
723            local = idx - self.base_offset;
724        }
725
726        if local >= self.cache.len() {
727            self.cache.resize(local + 1, None);
728        }
729        self.cache[local] = Some(height);
730
731        // Trim if over capacity: remove oldest entries and adjust base_offset
732        if self.cache.len() > self.capacity {
733            let to_remove = self.cache.len() - self.capacity;
734            self.cache.drain(0..to_remove);
735            self.base_offset += to_remove;
736        }
737    }
738
739    /// Drop the first `count` items, shifting every remaining measurement down
740    /// by `count` so it still names the item it was taken from.
741    ///
742    /// The counterpart to [`VariableHeightsFenwick::drop_front`], for callers
743    /// that trim a sliding window with [`Virtualized::trim_front`].
744    pub fn drop_front(&mut self, count: usize) {
745        if count == 0 {
746            return;
747        }
748        if let Some(base) = self.base_offset.checked_sub(count) {
749            // The whole window sits past the trimmed prefix: renumber it.
750            self.base_offset = base;
751            return;
752        }
753        let dropped = count - self.base_offset;
754        if dropped >= self.cache.len() {
755            self.cache.clear();
756        } else {
757            self.cache.drain(0..dropped);
758        }
759        self.base_offset = 0;
760    }
761
762    /// Clear cached heights.
763    pub fn clear(&mut self) {
764        self.cache.clear();
765        self.base_offset = 0;
766    }
767}
768
769// ============================================================================
770// VariableHeightsFenwick - O(log n) scroll-to-index mapping
771// ============================================================================
772
773use crate::height_predictor::{HeightPredictor, PredictorConfig, PredictorStats};
774
775/// Variable height tracker using Fenwick tree for O(log n) prefix sum queries.
776///
777/// This enables efficient scroll offset to item index mapping for virtualized
778/// lists with variable height items.
779///
780/// # Operations
781///
782/// | Operation | Time |
783/// |-----------|------|
784/// | `find_item_at_offset` | O(log n) |
785/// | `offset_of_item` | O(log n) |
786/// | `set_height` | O(log n) |
787/// | `total_height` | O(log n) |
788///
789/// # Invariants
790///
791/// 1. Internal prefix sums are exact u64 sums of u16 item heights.
792/// 2. Inverse lookup searches these monotone sums without allocating.
793/// 3. Public u32 offsets and totals saturate at u32::MAX; internal layout
794///    continues to use exact offsets beyond that boundary.
795#[derive(Debug, Clone)]
796pub struct VariableHeightsFenwick {
797    /// One-indexed Fenwick tree storing exact aggregate heights.
798    tree: Vec<u64>,
799    /// Default height for items not yet measured.
800    default_height: u16,
801    /// Number of items tracked.
802    len: usize,
803    /// Which slots hold a measured height (`set`) rather than the fill value.
804    measured: Vec<u64>,
805    /// Number of tracked slots without a measured bit.
806    unmeasured: usize,
807    /// Optional Bayesian model for the heights of unmeasured slots.
808    predictor: Option<HeightPredictor>,
809    /// Height every unmeasured slot currently holds: the predictor's point
810    /// prediction when one is attached, otherwise `default_height`.
811    fill_height: u16,
812}
813
814impl Default for VariableHeightsFenwick {
815    fn default() -> Self {
816        Self::new(1, 0)
817    }
818}
819
820impl VariableHeightsFenwick {
821    /// Create a new height tracker with given default height and initial capacity.
822    #[must_use]
823    pub fn new(default_height: u16, capacity: usize) -> Self {
824        let tree = Self::build_height_tree(std::iter::repeat_n(default_height, capacity));
825        Self {
826            tree,
827            default_height,
828            len: capacity,
829            measured: vec![0; capacity.div_ceil(64)],
830            unmeasured: capacity,
831            predictor: None,
832            fill_height: default_height,
833        }
834    }
835
836    /// Create from a slice of heights (all of them count as measured).
837    #[must_use]
838    pub fn from_heights(heights: &[u16], default_height: u16) -> Self {
839        Self {
840            tree: Self::build_height_tree(heights.iter().copied()),
841            default_height,
842            len: heights.len(),
843            measured: Self::all_measured_bits(heights.len()),
844            unmeasured: 0,
845            predictor: None,
846            fill_height: default_height,
847        }
848    }
849
850    /// Build in O(n), bounding the item count so every possible height update
851    /// also fits in u64. This limit exceeds any practically allocatable list.
852    fn build_height_tree(heights: impl ExactSizeIterator<Item = u16>) -> Vec<u64> {
853        let len = heights.len();
854        assert!(
855            u64::try_from(len).is_ok_and(|n| n <= u64::MAX / u64::from(u16::MAX)),
856            "too many items for exact height aggregates"
857        );
858        let mut tree = vec![0; len + 1];
859        for (slot, height) in tree[1..].iter_mut().zip(heights) {
860            *slot = u64::from(height);
861        }
862        for idx in 1..=len {
863            let parent = idx + idx.isolate_lowest_one();
864            if parent <= len {
865                tree[parent] += tree[idx];
866            }
867        }
868        tree
869    }
870
871    fn all_measured_bits(len: usize) -> Vec<u64> {
872        let mut bits = vec![u64::MAX; len.div_ceil(64)];
873        if !len.is_multiple_of(64) {
874            *bits.last_mut().expect("partial word exists") = (1_u64 << (len % 64)) - 1;
875        }
876        bits
877    }
878
879    fn mark_measured(&mut self, idx: usize) {
880        if !self.is_measured(idx) {
881            self.measured[idx / 64] |= 1_u64 << (idx % 64);
882            self.unmeasured -= 1;
883        }
884    }
885
886    fn set_tracked_height(&mut self, idx: usize, height: u16) {
887        let old = self.get(idx);
888        let mut node = idx + 1;
889        while node <= self.len {
890            if height >= old {
891                self.tree[node] += u64::from(height - old);
892            } else {
893                self.tree[node] -= u64::from(old - height);
894            }
895            node += node.isolate_lowest_one();
896        }
897    }
898
899    fn offset_of_item_exact(&self, idx: usize) -> u64 {
900        let mut node = idx.min(self.len);
901        let mut sum = 0;
902        while node > 0 {
903            sum += self.tree[node];
904            node &= node - 1;
905        }
906        sum
907    }
908
909    fn total_height_exact(&self) -> u64 {
910        self.offset_of_item_exact(self.len)
911    }
912
913    fn find_item_at_offset_exact(&self, offset: u64) -> usize {
914        // Preserve the origin convention even when leading items have height 0.
915        if self.len == 0 || offset == 0 {
916            return 0;
917        }
918        let mut idx = 0;
919        let mut sum = 0;
920        let mut step = 1usize << (usize::BITS - self.len.leading_zeros() - 1);
921        while step > 0 {
922            if step <= self.len - idx {
923                let next = idx + step;
924                let prefix = sum + self.tree[next];
925                if prefix <= offset {
926                    idx = next;
927                    sum = prefix;
928                }
929            }
930            step >>= 1;
931        }
932        idx
933    }
934
935    /// Attach a Bayesian height predictor ([`HeightPredictor`]).
936    ///
937    /// Unmeasured slots then hold the predictor's current point prediction
938    /// instead of `default_height`; every [`set`](Self::set) trains the model
939    /// and, whenever the rounded prediction moves by a whole row, the
940    /// unmeasured slots are refilled so offsets and the total height track
941    /// the rows measured so far instead of a constant guess. A refill costs
942    /// O(u log n) for u unmeasured slots and a converging posterior triggers
943    /// it only a handful of times.
944    #[must_use]
945    pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
946        let predictor = HeightPredictor::new(config);
947        self.fill_height = predictor.predict(0).predicted.max(1);
948        self.predictor = Some(predictor);
949        self.refill_unmeasured();
950        self
951    }
952
953    /// The attached height predictor, if any.
954    #[must_use]
955    pub fn predictor(&self) -> Option<&HeightPredictor> {
956        self.predictor.as_ref()
957    }
958
959    /// Height every unmeasured slot currently holds (the prediction when a
960    /// predictor is attached, otherwise the default height).
961    #[must_use]
962    pub fn predicted_height(&self) -> u16 {
963        self.fill_height
964    }
965
966    /// Number of slots that have not been measured through [`set`](Self::set).
967    #[must_use]
968    pub fn unmeasured_count(&self) -> usize {
969        self.unmeasured
970    }
971
972    /// Whether slot `idx` holds a measured height.
973    #[must_use]
974    pub fn is_measured(&self, idx: usize) -> bool {
975        idx < self.len && self.measured[idx / 64] & (1_u64 << (idx % 64)) != 0
976    }
977
978    /// Rewrite every unmeasured slot with the current fill height.
979    /// Returns the number of slots rewritten.
980    fn refill_unmeasured(&mut self) -> usize {
981        let mut rewritten = 0;
982        for idx in 0..self.len {
983            if !self.is_measured(idx) {
984                self.set_tracked_height(idx, self.fill_height);
985                rewritten += 1;
986            }
987        }
988        rewritten
989    }
990
991    /// Number of items tracked.
992    #[must_use]
993    pub fn len(&self) -> usize {
994        self.len
995    }
996
997    /// Whether tracking is empty.
998    #[must_use]
999    pub fn is_empty(&self) -> bool {
1000        self.len == 0
1001    }
1002
1003    /// Get the default height for unmeasured items.
1004    #[must_use]
1005    pub fn default_height(&self) -> u16 {
1006        self.default_height
1007    }
1008
1009    /// Get height of a specific item. O(log n).
1010    ///
1011    /// Items beyond the tracked length report the fill height (the
1012    /// prediction when a predictor is attached).
1013    #[must_use]
1014    pub fn get(&self, idx: usize) -> u16 {
1015        if idx >= self.len {
1016            return self.fill_height;
1017        }
1018        (self.offset_of_item_exact(idx + 1) - self.offset_of_item_exact(idx)) as u16
1019    }
1020
1021    /// Set (measure) the height of a specific item. O(log n), plus a refill
1022    /// of the unmeasured slots when an attached predictor's rounded
1023    /// prediction changes.
1024    pub fn set(&mut self, idx: usize, height: u16) {
1025        self.set_in_category(idx, height, 0);
1026    }
1027
1028    /// Measure an item and train its category's predictor. Unclassified,
1029    /// unmeasured slots retain the default category's prediction.
1030    pub fn set_in_category(&mut self, idx: usize, height: u16, category: usize) {
1031        if idx >= self.len {
1032            // Need to resize
1033            self.resize(idx.checked_add(1).expect("height index exceeds usize"));
1034        }
1035        self.set_tracked_height(idx, height);
1036        self.mark_measured(idx);
1037        if let Some(predictor) = self.predictor.as_mut() {
1038            predictor.observe(category, height);
1039            let next = predictor.predict(0).predicted.max(1);
1040            if next != self.fill_height {
1041                self.fill_height = next;
1042                self.refill_unmeasured();
1043            }
1044        }
1045    }
1046
1047    /// Get the y-offset (in pixels/rows) of an item. O(log n).
1048    ///
1049    /// Returns the sum of heights of all items before `idx`, saturated at
1050    /// `u32::MAX`. Indices beyond the tracked length return the total height.
1051    #[must_use]
1052    pub fn offset_of_item(&self, idx: usize) -> u32 {
1053        self.offset_of_item_exact(idx).min(u64::from(u32::MAX)) as u32
1054    }
1055
1056    /// Find the item index at a given scroll offset. O(log n).
1057    ///
1058    /// Returns the index of the item that occupies the given offset.
1059    /// If offset is beyond all items, returns `self.len`.
1060    ///
1061    /// Item i occupies the interval between its exact prefix sums, including
1062    /// when the total exceeds `u32::MAX`. Offset zero returns item zero even
1063    /// if leading items have zero height. Saturated public offsets above the
1064    /// u32 boundary cannot be used to address those later items.
1065    #[must_use]
1066    pub fn find_item_at_offset(&self, offset: u32) -> usize {
1067        self.find_item_at_offset_exact(u64::from(offset))
1068    }
1069
1070    /// Count how many items are visible within a viewport starting at `start_idx`. O(log n).
1071    ///
1072    /// Visibility here means partially or fully visible. The first partially
1073    /// visible trailing item is counted.
1074    ///
1075    /// Returns **at least 1** when `start_idx < len` and `viewport_height > 0`,
1076    /// even if the first item is taller than the viewport.
1077    #[must_use]
1078    pub fn visible_count(&self, start_idx: usize, viewport_height: u16) -> usize {
1079        if self.len == 0 || viewport_height == 0 {
1080            return 0;
1081        }
1082        let start = start_idx.min(self.len);
1083        let start_offset = self.offset_of_item_exact(start);
1084        let end_offset = start_offset.saturating_add(u64::from(viewport_height));
1085
1086        // Find last item that fits
1087        let end_idx = self.find_item_at_offset_exact(end_offset);
1088
1089        // Count items from start to end (including partially visible trailing item)
1090        if end_idx > start {
1091            // `find_item_at_offset` returns `len` when `end_offset` is at/after the end
1092            // of the list. In that case, everything from `start` to the end fits.
1093            if end_idx >= self.len {
1094                return self.len.saturating_sub(start);
1095            }
1096            // Check if end_idx item is visible (partially or fully)
1097            let end_item_start = self.offset_of_item_exact(end_idx);
1098            if end_offset > end_item_start {
1099                end_idx - start + 1
1100            } else {
1101                end_idx - start
1102            }
1103        } else {
1104            // At least show one item if viewport has space
1105            if viewport_height > 0 && start < self.len {
1106                1
1107            } else {
1108                0
1109            }
1110        }
1111    }
1112
1113    /// Get total height of all items, saturated at `u32::MAX`. O(log n).
1114    #[must_use]
1115    pub fn total_height(&self) -> u32 {
1116        self.total_height_exact().min(u64::from(u32::MAX)) as u32
1117    }
1118
1119    /// Resize the tracker to accommodate `new_len` items.
1120    ///
1121    /// New items are initialized with the fill height (the default height,
1122    /// or the current prediction when a predictor is attached).
1123    pub fn resize(&mut self, new_len: usize) {
1124        if new_len == self.len {
1125            return;
1126        }
1127        self.tree = Self::build_height_tree((0..new_len).map(|idx| self.get(idx)));
1128        if new_len > self.len {
1129            self.unmeasured += new_len - self.len;
1130            self.measured.resize(new_len.div_ceil(64), 0);
1131        } else {
1132            let dropped_unmeasured = (new_len..self.len)
1133                .filter(|&idx| !self.is_measured(idx))
1134                .count();
1135            self.unmeasured -= dropped_unmeasured;
1136            self.measured.truncate(new_len.div_ceil(64));
1137            if !new_len.is_multiple_of(64) {
1138                *self.measured.last_mut().expect("partial word exists") &=
1139                    (1_u64 << (new_len % 64)) - 1;
1140            }
1141        }
1142        self.len = new_len;
1143    }
1144
1145    /// Drop the first `n` entries (the list trimmed its front): remaining
1146    /// heights and their measured flags shift down by `n`; an attached
1147    /// predictor keeps what it learned.
1148    pub fn drop_front(&mut self, n: usize) {
1149        if n == 0 {
1150            return;
1151        }
1152        if n >= self.len {
1153            self.clear();
1154            return;
1155        }
1156        let kept: Vec<(u16, bool)> = (n..self.len)
1157            .map(|idx| (self.get(idx), self.is_measured(idx)))
1158            .collect();
1159        self.tree = Self::build_height_tree(kept.iter().map(|&(height, _)| height));
1160        self.len = kept.len();
1161        self.measured = vec![0; self.len.div_ceil(64)];
1162        self.unmeasured = self.len;
1163        for (idx, (_, measured)) in kept.into_iter().enumerate() {
1164            if measured {
1165                self.mark_measured(idx);
1166            }
1167        }
1168    }
1169
1170    /// Clear all height data (an attached predictor keeps what it learned).
1171    pub fn clear(&mut self) {
1172        self.tree = vec![0];
1173        self.len = 0;
1174        self.measured.clear();
1175        self.unmeasured = 0;
1176    }
1177
1178    /// Rebuild from a fresh set of heights; all of them count as measured and
1179    /// train an attached predictor.
1180    pub fn rebuild(&mut self, heights: &[u16]) {
1181        self.tree = Self::build_height_tree(heights.iter().copied());
1182        self.len = heights.len();
1183        self.measured = Self::all_measured_bits(heights.len());
1184        self.unmeasured = 0;
1185        if let Some(predictor) = self.predictor.as_mut() {
1186            for &height in heights {
1187                predictor.observe(0, height);
1188            }
1189            self.fill_height = predictor.predict(0).predicted.max(1);
1190        }
1191    }
1192}
1193
1194// ============================================================================
1195// VirtualizedList Widget
1196// ============================================================================
1197
1198/// Trait for items that can render themselves.
1199///
1200/// Implement this trait for item types that should render in a `VirtualizedList`.
1201pub trait RenderItem {
1202    /// Render the item into the frame at the given area.
1203    ///
1204    /// # Arguments
1205    ///
1206    /// * `area` - The area to render into.
1207    /// * `frame` - The frame to render into.
1208    /// * `selected` - Whether the item is selected.
1209    /// * `skip_rows` - Number of rows to skip from the top of the item content.
1210    ///   This is non-zero when the item partially overlaps the top of the viewport.
1211    fn render(&self, area: Rect, frame: &mut Frame, selected: bool, skip_rows: u16);
1212
1213    /// Height of this item in terminal rows.
1214    fn height(&self) -> u16 {
1215        1
1216    }
1217
1218    /// Height-prediction category. Use a small stable category ID for each
1219    /// item shape; zero is the default for unclassified rows.
1220    fn category(&self) -> usize {
1221        0
1222    }
1223}
1224
1225impl<T: RenderItem> Virtualized<T> {
1226    /// Measure an owned item using its [`RenderItem::category`]. External
1227    /// storage has no item to inspect and uses category zero; use
1228    /// [`Self::observe_height_in_category`] to supply an external category.
1229    pub fn measure(&mut self, idx: usize, height: u16) {
1230        let category = self.get(idx).map_or(0, RenderItem::category);
1231        self.observe_height_in_category(idx, height, category);
1232    }
1233}
1234
1235/// How a [`VirtualizedList`] sizes its rows.
1236#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1237pub enum ListHeightMode {
1238    /// Every row is this many terminal rows tall (default: 1).
1239    Fixed(u16),
1240    /// Each row is as tall as [`RenderItem::height`] reports. Rows are
1241    /// measured into the state's Fenwick tracker as they render, so scroll
1242    /// offsets and the scrollbar stay O(log n) in the item count. Scrolling
1243    /// is item-aligned: the first visible row starts at the viewport top.
1244    Variable,
1245}
1246
1247/// State for the VirtualizedList widget.
1248#[derive(Debug, Clone)]
1249pub struct VirtualizedListState {
1250    /// Currently selected index.
1251    pub selected: Option<usize>,
1252    /// Scroll offset.
1253    scroll_offset: usize,
1254    /// Visible count (from last render).
1255    visible_count: usize,
1256    /// Overscan amount.
1257    overscan: usize,
1258    /// Whether follow mode is enabled.
1259    follow_mode: bool,
1260    /// Scroll velocity for momentum.
1261    scroll_velocity: f32,
1262    /// Drag anchor for scrollbar thumb (offset from thumb top).
1263    scrollbar_drag_anchor: Option<usize>,
1264    /// Optional persistence ID for state saving/restoration.
1265    persistence_id: Option<String>,
1266    /// Row heights measured while rendering in [`ListHeightMode::Variable`]
1267    /// (`None` until the first variable-height render).
1268    heights: Option<VariableHeightsFenwick>,
1269}
1270
1271impl Default for VirtualizedListState {
1272    fn default() -> Self {
1273        Self::new()
1274    }
1275}
1276
1277impl VirtualizedListState {
1278    /// Create a new state.
1279    #[must_use]
1280    pub fn new() -> Self {
1281        Self {
1282            selected: None,
1283            scroll_offset: 0,
1284            visible_count: 0,
1285            overscan: 2,
1286            follow_mode: false,
1287            scroll_velocity: 0.0,
1288            scrollbar_drag_anchor: None,
1289            persistence_id: None,
1290            heights: None,
1291        }
1292    }
1293
1294    /// Create variable-height state before its first render.
1295    #[must_use]
1296    pub fn variable(default_height: u16) -> Self {
1297        Self {
1298            heights: Some(VariableHeightsFenwick::new(default_height.max(1), 0)),
1299            ..Self::new()
1300        }
1301    }
1302
1303    /// Enable category-aware prediction of unmeasured row heights.
1304    /// Measured heights remain exact; unclassified rows use category zero.
1305    #[must_use]
1306    pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
1307        self.heights = Some(
1308            self.heights
1309                .take()
1310                .unwrap_or_default()
1311                .with_predictor(config),
1312        );
1313        self
1314    }
1315
1316    /// Point prediction for a category, or the configured default height.
1317    #[must_use]
1318    pub fn predicted_height(&self, category: usize) -> u16 {
1319        self.heights.as_ref().map_or(1, |heights| {
1320            heights
1321                .predictor()
1322                .map_or(heights.default_height(), |predictor| {
1323                    predictor.predict(category).predicted.max(1)
1324                })
1325        })
1326    }
1327
1328    /// Statistics from measured rows, when prediction is enabled.
1329    #[must_use]
1330    pub fn predictor_stats(&self) -> Option<PredictorStats> {
1331        self.heights
1332            .as_ref()
1333            .and_then(VariableHeightsFenwick::predictor)
1334            .map(HeightPredictor::stats)
1335    }
1336
1337    /// Record the measured height of item `idx` for a variable-height
1338    /// list. Rendering measures the visible rows itself; call this when an
1339    /// item's height changed while off-screen so offsets stay exact. Ignored
1340    /// until the first variable-height render creates the tracker.
1341    pub fn measure(&mut self, idx: usize, height: u16) {
1342        self.measure_in_category(idx, height, 0);
1343    }
1344
1345    /// Record an off-screen measurement together with its item category.
1346    pub fn measure_in_category(&mut self, idx: usize, height: u16, category: usize) {
1347        if let Some(heights) = self.heights.as_mut()
1348            && idx < heights.len()
1349        {
1350            heights.set_in_category(idx, height.max(1), category);
1351        }
1352    }
1353
1354    /// The variable-height tracker (after the first variable-height render).
1355    #[must_use]
1356    pub fn heights(&self) -> Option<&VariableHeightsFenwick> {
1357        self.heights.as_ref()
1358    }
1359
1360    /// Create with overscan.
1361    #[must_use]
1362    pub fn with_overscan(mut self, overscan: usize) -> Self {
1363        self.overscan = overscan;
1364        self
1365    }
1366
1367    /// Create with follow mode enabled.
1368    #[must_use]
1369    pub fn with_follow(mut self, follow: bool) -> Self {
1370        self.follow_mode = follow;
1371        self
1372    }
1373
1374    /// Create with a persistence ID for state saving. Without one the list has
1375    /// no [`StateKey`](crate::stateful::StateKey) and its state is not persisted.
1376    #[must_use]
1377    pub fn with_persistence_id(mut self, id: impl Into<String>) -> Self {
1378        self.persistence_id = Some(id.into());
1379        self
1380    }
1381
1382    /// Get the persistence ID, if set.
1383    #[must_use = "use the persistence id (if any)"]
1384    pub fn persistence_id(&self) -> Option<&str> {
1385        self.persistence_id.as_deref()
1386    }
1387
1388    /// Get raw scroll offset.
1389    ///
1390    /// **Warning:** After `scroll_to_bottom`, this may return `usize::MAX`
1391    /// (a lazy sentinel that gets clamped during rendering). Use
1392    /// [`scroll_offset_clamped`](Self::scroll_offset_clamped) with a known
1393    /// `total_items` to get a safe value for display or indexing.
1394    #[must_use]
1395    pub fn scroll_offset(&self) -> usize {
1396        self.scroll_offset
1397    }
1398
1399    /// Get scroll offset clamped against a known total item count.
1400    ///
1401    /// Prefer this over [`scroll_offset()`](Self::scroll_offset) when the total is available,
1402    /// because `scroll_to_bottom` may store `usize::MAX` internally.
1403    #[must_use]
1404    pub fn scroll_offset_clamped(&self, total_items: usize) -> usize {
1405        if total_items == 0 {
1406            return 0;
1407        }
1408        self.scroll_offset.min(total_items.saturating_sub(1))
1409    }
1410
1411    /// Get visible item count (from last render).
1412    #[must_use]
1413    pub fn visible_count(&self) -> usize {
1414        self.visible_count
1415    }
1416
1417    /// Scroll by delta (positive = down).
1418    pub fn scroll(&mut self, delta: i32, total_items: usize) {
1419        if total_items == 0 {
1420            return;
1421        }
1422        let max_offset = if self.visible_count > 0 {
1423            total_items.saturating_sub(self.visible_count)
1424        } else {
1425            total_items.saturating_sub(1)
1426        };
1427        // Clamp current offset BEFORE adding delta, so lazy MAX doesn't swallow negative deltas
1428        let clamped_current = self.scroll_offset.min(max_offset);
1429        let new_offset = clamped_current
1430            .saturating_add_signed(delta as isize)
1431            .min(max_offset);
1432        self.scroll_offset = new_offset;
1433
1434        if delta != 0 {
1435            self.follow_mode = false;
1436        }
1437    }
1438
1439    /// Scroll to specific index.
1440    pub fn scroll_to(&mut self, idx: usize, total_items: usize) {
1441        self.scroll_offset = idx.min(total_items.saturating_sub(1));
1442        self.follow_mode = false;
1443    }
1444
1445    /// Scroll to top.
1446    pub fn scroll_to_top(&mut self) {
1447        self.scroll_offset = 0;
1448        self.follow_mode = false;
1449    }
1450
1451    /// Scroll to bottom.
1452    pub fn scroll_to_bottom(&mut self, total_items: usize) {
1453        if total_items == 0 {
1454            self.scroll_offset = 0;
1455        } else {
1456            // Set to MAX; render() will clamp to (total - viewport)
1457            // once viewport height is known.
1458            self.scroll_offset = usize::MAX;
1459        }
1460    }
1461
1462    /// Page up (scroll by visible count - 1).
1463    pub fn page_up(&mut self, total_items: usize) {
1464        if self.visible_count > 0 {
1465            let step = if self.visible_count > 1 {
1466                self.visible_count - 1
1467            } else {
1468                1
1469            };
1470            let delta = i32::try_from(step).unwrap_or(i32::MAX);
1471            self.scroll(-delta, total_items);
1472        }
1473    }
1474
1475    /// Page down (scroll by visible count - 1).
1476    pub fn page_down(&mut self, total_items: usize) {
1477        if self.visible_count > 0 {
1478            let step = if self.visible_count > 1 {
1479                self.visible_count - 1
1480            } else {
1481                1
1482            };
1483            let delta = i32::try_from(step).unwrap_or(i32::MAX);
1484            self.scroll(delta, total_items);
1485        }
1486    }
1487
1488    /// Select an item.
1489    pub fn select(&mut self, index: Option<usize>) {
1490        self.selected = index;
1491    }
1492
1493    /// Select previous item.
1494    pub fn select_previous(&mut self, total_items: usize) {
1495        if total_items == 0 {
1496            self.selected = None;
1497            return;
1498        }
1499        self.selected = Some(match self.selected {
1500            Some(i) if i > 0 => i - 1,
1501            Some(_) => 0,
1502            None => 0,
1503        });
1504    }
1505
1506    /// Select next item.
1507    pub fn select_next(&mut self, total_items: usize) {
1508        if total_items == 0 {
1509            self.selected = None;
1510            return;
1511        }
1512        self.selected = Some(match self.selected {
1513            Some(i) if i < total_items - 1 => i + 1,
1514            Some(i) => i,
1515            None => 0,
1516        });
1517    }
1518
1519    /// Check if at bottom.
1520    #[must_use]
1521    pub fn is_at_bottom(&self, total_items: usize) -> bool {
1522        if total_items <= self.visible_count {
1523            true
1524        } else {
1525            self.scroll_offset >= total_items - self.visible_count
1526        }
1527    }
1528
1529    /// Enable/disable follow mode.
1530    pub fn set_follow(&mut self, follow: bool, total_items: usize) {
1531        self.follow_mode = follow;
1532        if follow {
1533            self.scroll_to_bottom(total_items);
1534        }
1535    }
1536
1537    /// Check if follow mode is enabled.
1538    #[must_use]
1539    pub fn follow_mode(&self) -> bool {
1540        self.follow_mode
1541    }
1542
1543    /// Start momentum scroll.
1544    pub fn fling(&mut self, velocity: f32) {
1545        self.scroll_velocity = velocity;
1546    }
1547
1548    /// Apply momentum scrolling tick.
1549    pub fn tick(&mut self, dt: Duration, total_items: usize) {
1550        if self.scroll_velocity.abs() > 0.1 {
1551            let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
1552            if delta != 0 {
1553                self.scroll(delta, total_items);
1554            }
1555            self.scroll_velocity *= 0.95;
1556        } else {
1557            self.scroll_velocity = 0.0;
1558        }
1559    }
1560
1561    /// Handle mouse events, including scrollbar interaction.
1562    ///
1563    /// The caller must provide the hit test result and the expected hit ID for
1564    /// the scrollbar.
1565    ///
1566    /// After a [`ListHeightMode::Variable`] render the scrollbar works in
1567    /// rows, as it was drawn, and `fixed_item_height` is ignored: the thumb
1568    /// position maps back to the nearest item start, and a wheel or arrow
1569    /// step always moves at least one item.
1570    pub fn handle_mouse(
1571        &mut self,
1572        event: &ftui_core::event::MouseEvent,
1573        hit: Option<(
1574            ftui_render::frame::HitId,
1575            ftui_render::frame::HitRegion,
1576            u64,
1577        )>,
1578        scrollbar_hit_id: ftui_render::frame::HitId,
1579        total_items: usize,
1580        viewport_height: u16,
1581        fixed_item_height: u16,
1582    ) -> crate::mouse::MouseResult {
1583        if let Some(heights) = self.heights.as_ref()
1584            && heights.len() == total_items
1585            && total_items > 0
1586        {
1587            let old_item = self.scroll_offset.min(total_items - 1);
1588            let old_row = heights.offset_of_item_exact(old_item);
1589            let mut scrollbar_state = scrollbar_state_for_rows(
1590                heights.total_height_exact(),
1591                old_row,
1592                viewport_height,
1593                usize::MAX,
1594            );
1595            scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
1596            let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
1597            self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
1598
1599            // Rows below the first screenful may still be estimates, so the
1600            // end of the track means the end of the list (render clamps it
1601            // to the last item-aligned screenful).
1602            let total_rows = heights.total_height_exact();
1603            let row = scrollbar_state.position as u64;
1604            let mut item = heights.find_item_at_offset_exact(row);
1605            let start = heights.offset_of_item_exact(item);
1606            if row + u64::from(viewport_height) >= total_rows {
1607                item = total_items - 1;
1608            } else if row.saturating_sub(start) * 2 > u64::from(heights.get(item)) {
1609                item += 1;
1610            }
1611            // A step smaller than the item under it still has to move.
1612            if row > old_row && item <= old_item {
1613                item = old_item + 1;
1614            } else if row < old_row && item >= old_item {
1615                item = old_item.saturating_sub(1);
1616            }
1617            self.scroll_offset = item.min(total_items - 1);
1618
1619            if result == crate::mouse::MouseResult::Scrolled {
1620                self.follow_mode = false;
1621            }
1622            return result;
1623        }
1624
1625        // Construct temporary scrollbar state
1626        let items_per_viewport = viewport_height.div_ceil(fixed_item_height.max(1)) as usize;
1627        let mut scrollbar_state =
1628            ScrollbarState::new(total_items, self.scroll_offset, items_per_viewport);
1629
1630        // Restore drag anchor
1631        scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
1632
1633        let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
1634
1635        // Sync back
1636        self.scroll_offset = scrollbar_state.position;
1637        self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
1638
1639        if result == crate::mouse::MouseResult::Scrolled {
1640            self.follow_mode = false;
1641        }
1642
1643        result
1644    }
1645}
1646
1647// ============================================================================
1648// Stateful Persistence Implementation for VirtualizedListState
1649// ============================================================================
1650
1651/// Persistable state for a [`VirtualizedListState`].
1652///
1653/// Contains the user-facing scroll state that should survive sessions.
1654/// Transient values like scroll_velocity and visible_count are not persisted.
1655#[derive(Clone, Debug, Default, PartialEq)]
1656#[cfg_attr(
1657    feature = "state-persistence",
1658    derive(serde::Serialize, serde::Deserialize)
1659)]
1660pub struct VirtualizedListPersistState {
1661    /// Selected item index.
1662    pub selected: Option<usize>,
1663    /// Scroll offset (first visible item).
1664    pub scroll_offset: usize,
1665    /// Whether follow mode is enabled.
1666    pub follow_mode: bool,
1667}
1668
1669impl crate::stateful::Stateful for VirtualizedListState {
1670    type State = VirtualizedListPersistState;
1671
1672    fn state_key(&self) -> Option<crate::stateful::StateKey> {
1673        // No persistence_id, no identity: two unnamed lists must not share one.
1674        self.persistence_id
1675            .as_deref()
1676            .map(|id| crate::stateful::StateKey::new("VirtualizedList", id))
1677    }
1678
1679    fn save_state(&self) -> VirtualizedListPersistState {
1680        VirtualizedListPersistState {
1681            selected: self.selected,
1682            scroll_offset: self.scroll_offset,
1683            follow_mode: self.follow_mode,
1684        }
1685    }
1686
1687    fn restore_state(&mut self, state: VirtualizedListPersistState) {
1688        self.selected = state.selected;
1689        self.scroll_offset = state.scroll_offset;
1690        self.follow_mode = state.follow_mode;
1691        // Reset transient values
1692        self.scroll_velocity = 0.0;
1693        self.scrollbar_drag_anchor = None;
1694    }
1695}
1696
1697/// A virtualized list widget that renders only visible items.
1698///
1699/// This widget efficiently renders large lists by only drawing items
1700/// that are currently visible in the viewport, with optional overscan
1701/// for smooth scrolling.
1702///
1703/// # Variable heights
1704///
1705/// Use [`Self::variable_heights`] to measure visible items through
1706/// [`RenderItem::height`]. Enable [`VirtualizedListState::with_predictor`] to
1707/// learn from those measurements; unmeasured items use the category-zero
1708/// prediction. Scrolling remains item-aligned.
1709#[derive(Debug)]
1710pub struct VirtualizedList<'a, T> {
1711    /// Items to render.
1712    items: &'a [T],
1713    /// Base style.
1714    style: Style,
1715    /// Style for selected item.
1716    highlight_style: Style,
1717    /// Whether to show scrollbar.
1718    show_scrollbar: bool,
1719    /// Row sizing: fixed rows or per-item heights.
1720    height_mode: ListHeightMode,
1721    /// Optional hit ID for scrollbar interaction.
1722    hit_id: Option<ftui_render::frame::HitId>,
1723}
1724
1725impl<'a, T> VirtualizedList<'a, T> {
1726    /// Create a new virtualized list.
1727    #[must_use]
1728    pub fn new(items: &'a [T]) -> Self {
1729        Self {
1730            items,
1731            style: Style::default(),
1732            highlight_style: Style::default(),
1733            show_scrollbar: true,
1734            height_mode: ListHeightMode::Fixed(1),
1735            hit_id: None,
1736        }
1737    }
1738
1739    /// Set base style.
1740    #[must_use]
1741    pub fn style(mut self, style: Style) -> Self {
1742        self.style = style;
1743        self
1744    }
1745
1746    /// Set highlight style for selected item.
1747    #[must_use]
1748    pub fn highlight_style(mut self, style: Style) -> Self {
1749        self.highlight_style = style;
1750        self
1751    }
1752
1753    /// Enable/disable scrollbar.
1754    #[must_use]
1755    pub fn show_scrollbar(mut self, show: bool) -> Self {
1756        self.show_scrollbar = show;
1757        self
1758    }
1759
1760    /// Set fixed item height.
1761    #[must_use]
1762    pub fn fixed_height(mut self, height: u16) -> Self {
1763        self.height_mode = ListHeightMode::Fixed(height);
1764        self
1765    }
1766
1767    /// Size each row by [`RenderItem::height`] (see
1768    /// [`ListHeightMode::Variable`]).
1769    #[must_use]
1770    pub fn variable_heights(mut self) -> Self {
1771        self.height_mode = ListHeightMode::Variable;
1772        self
1773    }
1774
1775    /// The row sizing mode.
1776    #[must_use]
1777    pub fn height_mode(&self) -> ListHeightMode {
1778        self.height_mode
1779    }
1780
1781    /// Set hit ID for scrollbar interaction.
1782    #[must_use]
1783    pub fn hit_id(mut self, id: ftui_render::frame::HitId) -> Self {
1784        self.hit_id = Some(id);
1785        self
1786    }
1787}
1788
1789impl<T: RenderItem> StatefulWidget for VirtualizedList<'_, T> {
1790    type State = VirtualizedListState;
1791
1792    fn render(&self, area: Rect, frame: &mut Frame, state: &mut Self::State) {
1793        #[cfg(feature = "tracing")]
1794        let _span = tracing::debug_span!(
1795            "widget_render",
1796            widget = "VirtualizedList",
1797            x = area.x,
1798            y = area.y,
1799            w = area.width,
1800            h = area.height,
1801            items = self.items.len(),
1802            height_mode = ?self.height_mode
1803        )
1804        .entered();
1805
1806        if area.is_empty() {
1807            return;
1808        }
1809
1810        // Clear the full owned viewport so empty renders and shorter rows do
1811        // not leak prior buffer content.
1812        clear_text_area(frame, area, self.style);
1813
1814        let total_items = self.items.len();
1815        if total_items == 0 {
1816            state.visible_count = 0;
1817            state.scroll_offset = 0;
1818            if let Some(heights) = state.heights.as_mut() {
1819                heights.clear();
1820            }
1821            return;
1822        }
1823
1824        let ListHeightMode::Fixed(fixed_h) = self.height_mode else {
1825            self.render_variable(area, frame, state);
1826            return;
1827        };
1828
1829        // Reserve space for scrollbar if needed
1830        let fixed_h = fixed_h.max(1);
1831        // Use div_ceil to include partially visible items and avoid 0 count for large items
1832        let items_per_viewport = area.height.div_ceil(fixed_h) as usize;
1833        let fully_visible_items = (area.height / fixed_h) as usize;
1834        let needs_scrollbar = self.show_scrollbar && total_items > fully_visible_items;
1835        let content_width = if needs_scrollbar {
1836            area.width.saturating_sub(1)
1837        } else {
1838            area.width
1839        };
1840
1841        // Ensure selection is within bounds
1842        if let Some(selected) = state.selected
1843            && selected >= total_items
1844        {
1845            // Use saturating_sub to handle empty list case (total_items = 0)
1846            state.selected = if total_items > 0 {
1847                Some(total_items - 1)
1848            } else {
1849                None
1850            };
1851        }
1852
1853        // Ensure visible range includes selected item (it must be fully visible if possible)
1854        if let Some(selected) = state.selected {
1855            let vis_count = fully_visible_items.max(1);
1856            if selected >= state.scroll_offset.saturating_add(vis_count) {
1857                state.scroll_offset = selected.saturating_sub(vis_count.saturating_sub(1));
1858            } else if selected < state.scroll_offset {
1859                state.scroll_offset = selected;
1860            }
1861        }
1862
1863        // Clamp scroll offset
1864        let max_offset = if fully_visible_items > 0 {
1865            total_items.saturating_sub(fully_visible_items)
1866        } else {
1867            total_items.saturating_sub(1)
1868        };
1869        state.scroll_offset = state.scroll_offset.min(max_offset);
1870
1871        // Update visible count — use fully_visible_items (not items_per_viewport
1872        // which includes partial items via div_ceil) so scroll calculations
1873        // (page size, max_offset) use a consistent metric.
1874        state.visible_count = fully_visible_items.max(1).min(total_items);
1875
1876        // Calculate render range with overscan
1877        let render_start = state.scroll_offset.saturating_sub(state.overscan);
1878        let render_end = state
1879            .scroll_offset
1880            .saturating_add(items_per_viewport)
1881            .saturating_add(state.overscan)
1882            .min(total_items);
1883
1884        // Render visible items
1885        for idx in render_start..render_end {
1886            // Calculate Y position relative to viewport
1887            // Use relative arithmetic to prevent overflow when indices exceed i32::MAX.
1888            let relative_idx = if idx >= state.scroll_offset {
1889                i32::try_from(idx - state.scroll_offset).unwrap_or(i32::MAX)
1890            } else {
1891                // Handle overscan items before the scroll offset
1892                -(i32::try_from(state.scroll_offset - idx).unwrap_or(i32::MAX))
1893            };
1894
1895            let height_i32 = i32::from(fixed_h);
1896            let y_offset = relative_idx.saturating_mul(height_i32);
1897
1898            // Skip items above viewport
1899            // We use area.y as the viewport top.
1900            // Absolute top of item = area.y + y_offset.
1901            // Absolute bottom of item = area.y + y_offset + height.
1902            // If absolute_bottom <= area.y, it is fully above.
1903            // i.e. y_offset + height <= 0
1904            if y_offset.saturating_add(height_i32) <= 0 {
1905                continue;
1906            }
1907
1908            // Stop if below viewport
1909            if y_offset >= i32::from(area.height) {
1910                break;
1911            }
1912
1913            // Check if item starts off-screen top.
1914            // If so, we must render partially by skipping the top rows.
1915            let skip_rows = if y_offset < 0 {
1916                y_offset.unsigned_abs() as u16
1917            } else {
1918                0
1919            };
1920
1921            // Calculate actual render area
1922            // Use i32 arithmetic to avoid overflow when casting y_offset to i16
1923            let y = i32::from(area.y)
1924                .saturating_add(y_offset)
1925                .clamp(i32::from(area.y), i32::from(u16::MAX)) as u16;
1926
1927            if y >= area.bottom() {
1928                break;
1929            }
1930
1931            let visible_height = fixed_h
1932                .saturating_sub(skip_rows)
1933                .min(area.bottom().saturating_sub(y));
1934
1935            if visible_height == 0 {
1936                continue;
1937            }
1938
1939            let row_area = Rect::new(area.x, y, content_width, visible_height);
1940
1941            let is_selected = state.selected == Some(idx);
1942
1943            let row_style = if is_selected {
1944                self.highlight_style.merge(&self.style)
1945            } else {
1946                self.style
1947            };
1948            clear_text_area(frame, row_area, row_style);
1949
1950            // Render the item
1951            self.items[idx].render(row_area, frame, is_selected, skip_rows);
1952        }
1953
1954        // Render scrollbar
1955        if needs_scrollbar {
1956            let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
1957
1958            let mut scrollbar_state =
1959                ScrollbarState::new(total_items, state.scroll_offset, items_per_viewport);
1960
1961            // Sync drag anchor from persistent state to transient scrollbar state
1962            scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
1963
1964            let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
1965            if let Some(id) = self.hit_id {
1966                scrollbar = scrollbar.hit_id(id);
1967            }
1968            scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
1969        }
1970    }
1971}
1972
1973/// First item that starts at or after `offset` (the item containing
1974/// `offset` when it starts exactly there, the next one otherwise), clamped
1975/// to the last item.
1976fn first_item_from_offset(heights: &VariableHeightsFenwick, offset: u64) -> usize {
1977    let mut idx = heights.find_item_at_offset_exact(offset);
1978    if heights.offset_of_item_exact(idx) < offset {
1979        idx += 1;
1980    }
1981    idx.min(heights.len().saturating_sub(1))
1982}
1983
1984/// Preserve exact row metrics when they fit, otherwise scale both thumb size
1985/// and scroll progress into the target's representable range. `capacity` is
1986/// usize::MAX in production and permits exercising the 32-bit boundary on a
1987/// 64-bit test host. Independent saturation of position and total loses the
1988/// scroll ratio and can put a halfway-scrolled list's thumb at the bottom.
1989fn scrollbar_state_for_rows(
1990    total: u64,
1991    position: u64,
1992    viewport: u16,
1993    capacity: usize,
1994) -> ScrollbarState {
1995    let limit = capacity as u64;
1996    if total <= limit {
1997        return ScrollbarState::new(
1998            total as usize,
1999            position.min(total) as usize,
2000            viewport.into(),
2001        );
2002    }
2003    let scaled_viewport = (u128::from(viewport) * u128::from(limit))
2004        .div_ceil(u128::from(total))
2005        .min(u128::from(limit)) as usize;
2006    let max_position = total.saturating_sub(u64::from(viewport));
2007    let scaled_position = if max_position == 0 {
2008        0
2009    } else {
2010        (u128::from(position.min(max_position)) * (capacity - scaled_viewport) as u128
2011            / u128::from(max_position)) as usize
2012    };
2013    ScrollbarState::new(capacity, scaled_position, scaled_viewport)
2014}
2015
2016impl<T: RenderItem> VirtualizedList<'_, T> {
2017    /// Render in [`ListHeightMode::Variable`]: every row is as tall as
2018    /// [`RenderItem::height`] reports. The rows that can matter this frame
2019    /// (the selection, one screenful from the scroll offset and the last
2020    /// screenful) are measured
2021    /// into the state's Fenwick tracker first, so the selection adjustment,
2022    /// the bottom clamp and the scrollbar all work in rows with O(log n)
2023    /// offset queries instead of multiplying by a fixed height.
2024    fn render_variable(&self, area: Rect, frame: &mut Frame, state: &mut VirtualizedListState) {
2025        let total_items = self.items.len();
2026        let viewport = area.height;
2027        let heights = state
2028            .heights
2029            .get_or_insert_with(|| VariableHeightsFenwick::new(1, total_items));
2030        if heights.len() != total_items {
2031            heights.resize(total_items);
2032        }
2033
2034        let measure = |heights: &mut VariableHeightsFenwick, idx: usize| {
2035            let height = self.items[idx].height().max(1);
2036            if !heights.is_measured(idx) || heights.get(idx) != height {
2037                heights.set_in_category(idx, height, self.items[idx].category());
2038            }
2039        };
2040        // Measure rows from `start` until they fill the viewport; returns how
2041        // many rows that took (at least one).
2042        let measure_screenful = |heights: &mut VariableHeightsFenwick, start: usize| -> usize {
2043            let mut rows = 0u16;
2044            let mut idx = start;
2045            while idx < total_items && rows < viewport {
2046                measure(heights, idx);
2047                rows = rows.saturating_add(heights.get(idx));
2048                idx += 1;
2049            }
2050            (idx - start).max(1)
2051        };
2052
2053        // Keep the selection in range and in view.
2054        if let Some(selected) = state.selected
2055            && selected >= total_items
2056        {
2057            state.selected = Some(total_items - 1);
2058        }
2059        if let Some(selected) = state.selected {
2060            measure(heights, selected);
2061            if selected < state.scroll_offset {
2062                state.scroll_offset = selected;
2063            } else {
2064                measure_screenful(heights, state.scroll_offset);
2065                let top = heights.offset_of_item_exact(state.scroll_offset);
2066                let bottom = heights.offset_of_item_exact(selected + 1);
2067                if bottom.saturating_sub(top) > u64::from(viewport) {
2068                    let anchor = bottom.saturating_sub(u64::from(viewport));
2069                    state.scroll_offset = first_item_from_offset(heights, anchor).min(selected);
2070                }
2071            }
2072        }
2073
2074        // Clamp so the last screenful is as full as item alignment allows.
2075        // Measure that screenful first: an unmeasured tail counts at the
2076        // default height and would clamp a scroll to the end short of it.
2077        let mut tail_rows = 0u16;
2078        for idx in (0..total_items).rev() {
2079            if tail_rows >= viewport {
2080                break;
2081            }
2082            measure(heights, idx);
2083            tail_rows = tail_rows.saturating_add(heights.get(idx));
2084        }
2085        let total_height = heights.total_height_exact();
2086        let max_start = if total_height > u64::from(viewport) {
2087            first_item_from_offset(heights, total_height - u64::from(viewport))
2088        } else {
2089            0
2090        };
2091        state.scroll_offset = state.scroll_offset.min(max_start);
2092
2093        let visible = measure_screenful(heights, state.scroll_offset).min(total_items);
2094        state.visible_count = visible;
2095
2096        let total_height = heights.total_height_exact();
2097        let needs_scrollbar = self.show_scrollbar && total_height > u64::from(viewport);
2098        let content_width = if needs_scrollbar {
2099            area.width.saturating_sub(1)
2100        } else {
2101            area.width
2102        };
2103
2104        let mut y = 0u16;
2105        for idx in state.scroll_offset..state.scroll_offset.saturating_add(visible).min(total_items)
2106        {
2107            if y >= viewport {
2108                break;
2109            }
2110            let row_h = heights.get(idx).min(viewport - y);
2111            if row_h == 0 {
2112                continue;
2113            }
2114            let row_area = Rect::new(area.x, area.y.saturating_add(y), content_width, row_h);
2115            let is_selected = state.selected == Some(idx);
2116            let row_style = if is_selected {
2117                self.highlight_style.merge(&self.style)
2118            } else {
2119                self.style
2120            };
2121            clear_text_area(frame, row_area, row_style);
2122            self.items[idx].render(row_area, frame, is_selected, 0);
2123            y = y.saturating_add(row_h);
2124        }
2125
2126        if needs_scrollbar {
2127            let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
2128            let mut scrollbar_state = scrollbar_state_for_rows(
2129                total_height,
2130                heights.offset_of_item_exact(state.scroll_offset),
2131                viewport,
2132                usize::MAX,
2133            );
2134            scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
2135            let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
2136            if let Some(id) = self.hit_id {
2137                scrollbar = scrollbar.hit_id(id);
2138            }
2139            scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
2140        }
2141    }
2142}
2143
2144// ============================================================================
2145// Simple RenderItem implementations for common types
2146// ============================================================================
2147
2148impl RenderItem for String {
2149    fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
2150        if area.is_empty() {
2151            return;
2152        }
2153        let max_chars = area.width as usize;
2154        // String is assumed to be single-line in this implementation, so skip_rows > 0
2155        // implies the whole item is skipped. However, for robustness we check bounds.
2156        // If a String *did* contain newlines and we rendered it multiline, skip_rows would apply.
2157        // Here we just render the first line.
2158        if skip_rows > 0 {
2159            return;
2160        }
2161        for (i, ch) in self.chars().take(max_chars).enumerate() {
2162            frame
2163                .buffer
2164                .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
2165        }
2166    }
2167}
2168
2169impl RenderItem for &str {
2170    fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
2171        if area.is_empty() {
2172            return;
2173        }
2174        if skip_rows > 0 {
2175            return;
2176        }
2177        let max_chars = area.width as usize;
2178        for (i, ch) in self.chars().take(max_chars).enumerate() {
2179            frame
2180                .buffer
2181                .set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
2182        }
2183    }
2184}
2185
2186#[cfg(test)]
2187mod tests {
2188    use super::*;
2189    use proptest::prelude::*;
2190
2191    fn raw_row_text(frame: &Frame, y: u16) -> String {
2192        let width = frame.buffer.width();
2193        let mut actual = String::new();
2194        for x in 0..width {
2195            let ch = frame
2196                .buffer
2197                .get(x, y)
2198                .and_then(|cell| cell.content.as_char())
2199                .unwrap_or(' ');
2200            actual.push(ch);
2201        }
2202        actual
2203    }
2204
2205    #[test]
2206    fn test_new_virtualized() {
2207        let virt: Virtualized<String> = Virtualized::new(100);
2208        assert_eq!(virt.len(), 0);
2209        assert!(virt.is_empty());
2210    }
2211
2212    #[test]
2213    fn test_push_and_len() {
2214        let mut virt: Virtualized<i32> = Virtualized::new(100);
2215        virt.push(1);
2216        virt.push(2);
2217        virt.push(3);
2218        assert_eq!(virt.len(), 3);
2219        assert!(!virt.is_empty());
2220    }
2221
2222    #[test]
2223    fn test_visible_range_fixed_height() {
2224        let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(2);
2225        for i in 0..20 {
2226            virt.push(i);
2227        }
2228        // 10 items visible with height 2 in viewport 20
2229        let range = virt.visible_range(20);
2230        assert_eq!(range, 0..10);
2231    }
2232
2233    #[test]
2234    fn test_visible_range_variable_height_clamps() {
2235        let mut cache = HeightCache::new(1, 16);
2236        cache.set(0, 3);
2237        cache.set(1, 3);
2238        cache.set(2, 3);
2239        let mut virt: Virtualized<i32> =
2240            Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2241        for i in 0..3 {
2242            virt.push(i);
2243        }
2244        let range = virt.visible_range(5);
2245        // Includes the partially visible second item.
2246        assert_eq!(range, 0..2);
2247    }
2248
2249    #[test]
2250    fn test_visible_range_variable_height_exact_fit() {
2251        let mut cache = HeightCache::new(1, 16);
2252        cache.set(0, 2);
2253        cache.set(1, 3);
2254        let mut virt: Virtualized<i32> =
2255            Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2256        for i in 0..2 {
2257            virt.push(i);
2258        }
2259        let range = virt.visible_range(5);
2260        assert_eq!(range, 0..2);
2261    }
2262
2263    #[test]
2264    fn test_visible_range_with_scroll() {
2265        let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(1);
2266        for i in 0..50 {
2267            virt.push(i);
2268        }
2269        virt.scroll(10);
2270        let range = virt.visible_range(10);
2271        assert_eq!(range, 10..20);
2272    }
2273
2274    #[test]
2275    fn test_visible_range_variable_height_excludes_partial() {
2276        let mut cache = HeightCache::new(1, 16);
2277        cache.set(0, 6);
2278        cache.set(1, 6);
2279        let mut virt: Virtualized<i32> =
2280            Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2281        virt.push(1);
2282        virt.push(2);
2283        virt.push(3);
2284
2285        let range = virt.visible_range(10);
2286        // Includes the partially visible second item.
2287        assert_eq!(range, 0..2);
2288    }
2289
2290    #[test]
2291    fn test_visible_range_variable_height_exact_fit_larger() {
2292        let mut cache = HeightCache::new(1, 16);
2293        cache.set(0, 4);
2294        cache.set(1, 6);
2295        let mut virt: Virtualized<i32> =
2296            Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
2297        virt.push(1);
2298        virt.push(2);
2299        virt.push(3);
2300
2301        let range = virt.visible_range(10);
2302        assert_eq!(range, 0..2);
2303    }
2304
2305    #[test]
2306    fn test_visible_range_variable_height_default_for_unmeasured() {
2307        let cache = HeightCache::new(2, 16);
2308        let mut virt: Virtualized<i32> =
2309            Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
2310        for i in 0..3 {
2311            virt.push(i);
2312        }
2313
2314        // Default height = 2, viewport 5 fits 2 items (2 + 2) but not the third.
2315        let range = virt.visible_range(5);
2316        // Includes the partially visible third item.
2317        assert_eq!(range, 0..3);
2318    }
2319
2320    #[test]
2321    fn test_visible_range_variable_bottom_anchor_after_lazy_scroll_to_bottom() {
2322        let mut virt: Virtualized<i32> =
2323            Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2324        for i in 0..20 {
2325            virt.push(i);
2326        }
2327        // Viewport unknown (visible_count = 0): scroll_to_bottom stores the
2328        // lazy sentinel. The last screenful is 5 items of height 2.
2329        virt.scroll_to_bottom();
2330        assert_eq!(virt.visible_range(10), 15..20);
2331    }
2332
2333    #[test]
2334    fn test_visible_range_fenwick_bottom_anchor_after_lazy_scroll_to_bottom() {
2335        let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 20);
2336        for i in 0..20 {
2337            virt.push(i);
2338        }
2339        // Regression: this used to return the empty range 20..20 because the
2340        // unclamped sentinel offset reached the tracker as start_idx == len.
2341        virt.scroll_to_bottom();
2342        assert_eq!(virt.visible_range(10), 15..20);
2343    }
2344
2345    #[test]
2346    fn test_visible_range_fenwick_bottom_anchor_counts_partial_top_item() {
2347        // Heights [3,2,5,1,4]: the last 5 rows are exactly items 3 (h=1) and
2348        // 4 (h=4); a 6-row viewport additionally clips into item 2.
2349        let tracker = VariableHeightsFenwick::from_heights(&[3, 2, 5, 1, 4], 1);
2350        let mut virt: Virtualized<i32> =
2351            Virtualized::new(10).with_item_height(ItemHeight::VariableFenwick(tracker));
2352        for i in 0..5 {
2353            virt.push(i);
2354        }
2355        virt.scroll_to_bottom();
2356        assert_eq!(virt.visible_range(5), 3..5);
2357        virt.scroll_to_bottom();
2358        assert_eq!(virt.visible_range(6), 2..5);
2359    }
2360
2361    #[test]
2362    fn test_visible_range_variable_near_end_clamps_like_fixed() {
2363        // Scrolling to the last item must not leave blank rows below it,
2364        // matching the Fixed arm's max_offset clamping.
2365        let mut virt: Virtualized<i32> =
2366            Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
2367        for i in 0..20 {
2368            virt.push(i);
2369        }
2370        virt.scroll_to(18);
2371        assert_eq!(virt.visible_range(10), 15..20);
2372    }
2373
2374    #[test]
2375    fn test_render_range_with_overscan() {
2376        let mut virt: Virtualized<i32> =
2377            Virtualized::new(100).with_fixed_height(1).with_overscan(2);
2378        for i in 0..50 {
2379            virt.push(i);
2380        }
2381        virt.scroll(10);
2382        let range = virt.render_range(10);
2383        // Visible: 10..20, Overscan: 2
2384        // Render: 8..22
2385        assert_eq!(range, 8..22);
2386    }
2387
2388    #[test]
2389    fn test_scroll_bounds() {
2390        let mut virt: Virtualized<i32> = Virtualized::new(100);
2391        for i in 0..10 {
2392            virt.push(i);
2393        }
2394
2395        // Can't scroll negative
2396        virt.scroll(-100);
2397        assert_eq!(virt.scroll_offset(), 0);
2398
2399        // Can't scroll past end
2400        virt.scroll(100);
2401        assert_eq!(virt.scroll_offset(), 9);
2402    }
2403
2404    #[test]
2405    fn test_scroll_to() {
2406        let mut virt: Virtualized<i32> = Virtualized::new(100);
2407        for i in 0..20 {
2408            virt.push(i);
2409        }
2410
2411        virt.scroll_to(15);
2412        assert_eq!(virt.scroll_offset(), 15);
2413
2414        // Clamps to max
2415        virt.scroll_to(100);
2416        assert_eq!(virt.scroll_offset(), 19);
2417    }
2418
2419    #[test]
2420    fn test_follow_mode() {
2421        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
2422        virt.set_visible_count(5);
2423
2424        for i in 0..10 {
2425            virt.push(i);
2426        }
2427
2428        // Should be at bottom
2429        assert!(virt.is_at_bottom());
2430
2431        // Manual scroll disables follow
2432        virt.scroll(-5);
2433        assert!(!virt.follow_mode());
2434    }
2435
2436    #[test]
2437    fn test_scroll_to_start_and_end() {
2438        let mut virt: Virtualized<i32> = Virtualized::new(100);
2439        virt.set_visible_count(5);
2440        for i in 0..20 {
2441            virt.push(i);
2442        }
2443
2444        // scroll_to_start goes to top and disables follow
2445        virt.scroll_to(10);
2446        virt.set_follow(true);
2447        virt.scroll_to_start();
2448        assert_eq!(virt.scroll_offset(), 0);
2449        assert!(!virt.follow_mode());
2450
2451        // scroll_to_end goes to bottom and enables follow
2452        virt.scroll_to_end();
2453        assert!(virt.is_at_bottom());
2454        assert!(virt.follow_mode());
2455    }
2456
2457    #[test]
2458    fn test_virtualized_page_navigation() {
2459        let mut virt: Virtualized<i32> = Virtualized::new(100);
2460        virt.set_visible_count(5);
2461        for i in 0..30 {
2462            virt.push(i);
2463        }
2464
2465        virt.scroll_to(15);
2466        virt.page_up();
2467        // Page navigation keeps 1 row of context (visible_count - 1).
2468        assert_eq!(virt.scroll_offset(), 11);
2469
2470        virt.page_down();
2471        assert_eq!(virt.scroll_offset(), 15);
2472
2473        // Page up at start clamps to 0
2474        virt.scroll_to(2);
2475        virt.page_up();
2476        assert_eq!(virt.scroll_offset(), 0);
2477    }
2478
2479    #[test]
2480    fn test_height_cache() {
2481        let mut cache = HeightCache::new(1, 100);
2482
2483        // Default value
2484        assert_eq!(cache.get(0), 1);
2485        assert_eq!(cache.get(50), 1);
2486
2487        // Set value
2488        cache.set(5, 3);
2489        assert_eq!(cache.get(5), 3);
2490
2491        // Other indices still default
2492        assert_eq!(cache.get(4), 1);
2493        assert_eq!(cache.get(6), 1);
2494    }
2495
2496    #[test]
2497    fn test_height_cache_large_index_window() {
2498        let mut cache = HeightCache::new(1, 8);
2499        cache.set(10_000, 4);
2500        assert_eq!(cache.get(10_000), 4);
2501        assert_eq!(cache.get(0), 1);
2502        assert!(cache.cache.len() <= cache.capacity);
2503    }
2504
2505    #[test]
2506    fn test_clear() {
2507        let mut virt: Virtualized<i32> = Virtualized::new(100);
2508        for i in 0..10 {
2509            virt.push(i);
2510        }
2511        virt.scroll(5);
2512
2513        virt.clear();
2514        assert_eq!(virt.len(), 0);
2515        assert_eq!(virt.scroll_offset(), 0);
2516    }
2517
2518    #[test]
2519    fn test_get_item() {
2520        let mut virt: Virtualized<String> = Virtualized::new(100);
2521        virt.push("hello".to_string());
2522        virt.push("world".to_string());
2523
2524        assert_eq!(virt.get(0), Some(&"hello".to_string()));
2525        assert_eq!(virt.get(1), Some(&"world".to_string()));
2526        assert_eq!(virt.get(2), None);
2527    }
2528
2529    #[test]
2530    fn test_external_storage_len() {
2531        let mut virt: Virtualized<i32> = Virtualized::external(1000, 100);
2532        assert_eq!(virt.len(), 1000);
2533
2534        virt.set_external_len(2000);
2535        assert_eq!(virt.len(), 2000);
2536    }
2537
2538    #[test]
2539    fn test_momentum_scrolling() {
2540        let mut virt: Virtualized<i32> = Virtualized::new(100);
2541        for i in 0..50 {
2542            virt.push(i);
2543        }
2544
2545        virt.fling(10.0);
2546
2547        // Simulate tick
2548        virt.tick(Duration::from_millis(100));
2549
2550        // Should have scrolled
2551        assert!(virt.scroll_offset() > 0);
2552    }
2553
2554    // ========================================================================
2555    // VirtualizedListState tests
2556    // ========================================================================
2557
2558    #[test]
2559    fn test_virtualized_list_state_new() {
2560        let state = VirtualizedListState::new();
2561        assert_eq!(state.selected, None);
2562        assert_eq!(state.scroll_offset(), 0);
2563        assert_eq!(state.visible_count(), 0);
2564    }
2565
2566    #[test]
2567    fn test_virtualized_list_state_select_next() {
2568        let mut state = VirtualizedListState::new();
2569
2570        state.select_next(10);
2571        assert_eq!(state.selected, Some(0));
2572
2573        state.select_next(10);
2574        assert_eq!(state.selected, Some(1));
2575
2576        // At last item, stays there
2577        state.selected = Some(9);
2578        state.select_next(10);
2579        assert_eq!(state.selected, Some(9));
2580    }
2581
2582    #[test]
2583    fn test_virtualized_list_state_select_previous() {
2584        let mut state = VirtualizedListState::new();
2585        state.selected = Some(5);
2586
2587        state.select_previous(10);
2588        assert_eq!(state.selected, Some(4));
2589
2590        state.selected = Some(0);
2591        state.select_previous(10);
2592        assert_eq!(state.selected, Some(0));
2593    }
2594
2595    #[test]
2596    fn test_virtualized_list_state_scroll() {
2597        let mut state = VirtualizedListState::new();
2598
2599        state.scroll(5, 20);
2600        assert_eq!(state.scroll_offset(), 5);
2601
2602        state.scroll(-3, 20);
2603        assert_eq!(state.scroll_offset(), 2);
2604
2605        // Can't scroll negative
2606        state.scroll(-100, 20);
2607        assert_eq!(state.scroll_offset(), 0);
2608
2609        // Can't scroll past end
2610        state.scroll(100, 20);
2611        assert_eq!(state.scroll_offset(), 19);
2612    }
2613
2614    #[test]
2615    fn test_virtualized_list_state_follow_mode() {
2616        let mut state = VirtualizedListState::new().with_follow(true);
2617        assert!(state.follow_mode());
2618
2619        // Manual scroll disables follow
2620        state.scroll(5, 20);
2621        assert!(!state.follow_mode());
2622    }
2623
2624    #[test]
2625    fn test_render_item_string() {
2626        // Verify String implements RenderItem
2627        let s = String::from("hello");
2628        assert_eq!(s.height(), 1);
2629    }
2630
2631    #[test]
2632    fn test_page_up_down() {
2633        let mut virt: Virtualized<i32> = Virtualized::new(100);
2634        for i in 0..50 {
2635            virt.push(i);
2636        }
2637        virt.set_visible_count(10);
2638
2639        // Start at top
2640        assert_eq!(virt.scroll_offset(), 0);
2641
2642        // Page down
2643        virt.page_down();
2644        assert_eq!(virt.scroll_offset(), 9);
2645
2646        // Page down again
2647        virt.page_down();
2648        assert_eq!(virt.scroll_offset(), 18);
2649
2650        // Page up
2651        virt.page_up();
2652        assert_eq!(virt.scroll_offset(), 9);
2653
2654        // Page up again
2655        virt.page_up();
2656        assert_eq!(virt.scroll_offset(), 0);
2657
2658        // Page up at top stays at 0
2659        virt.page_up();
2660        assert_eq!(virt.scroll_offset(), 0);
2661    }
2662
2663    // ========================================================================
2664    // Performance invariant tests (bd-uo6v)
2665    // ========================================================================
2666
2667    #[test]
2668    fn test_render_scales_with_visible_not_total() {
2669        use ftui_render::grapheme_pool::GraphemePool;
2670        use std::time::Instant;
2671
2672        // Setup: VirtualizedList with 1K items
2673        let small_items: Vec<String> = (0..1_000).map(|i| format!("Line {}", i)).collect();
2674        let small_list = VirtualizedList::new(&small_items);
2675        let mut small_state = VirtualizedListState::new();
2676
2677        let area = Rect::new(0, 0, 80, 24);
2678        let mut pool = GraphemePool::new();
2679        let mut frame = Frame::new(80, 24, &mut pool);
2680
2681        // Warm up
2682        small_list.render(area, &mut frame, &mut small_state);
2683
2684        let start = Instant::now();
2685        for _ in 0..100 {
2686            frame.buffer.clear();
2687            small_list.render(area, &mut frame, &mut small_state);
2688        }
2689        let small_time = start.elapsed();
2690
2691        // Setup: VirtualizedList with 100K items
2692        let large_items: Vec<String> = (0..100_000).map(|i| format!("Line {}", i)).collect();
2693        let large_list = VirtualizedList::new(&large_items);
2694        let mut large_state = VirtualizedListState::new();
2695
2696        // Warm up
2697        large_list.render(area, &mut frame, &mut large_state);
2698
2699        let start = Instant::now();
2700        for _ in 0..100 {
2701            frame.buffer.clear();
2702            large_list.render(area, &mut frame, &mut large_state);
2703        }
2704        let large_time = start.elapsed();
2705
2706        // 100K should be within 3x of 1K (both render ~24 items)
2707        assert!(
2708            large_time < small_time * 3,
2709            "Render does not scale O(visible): 1K={:?}, 100K={:?}",
2710            small_time,
2711            large_time
2712        );
2713    }
2714
2715    #[test]
2716    fn test_scroll_is_constant_time() {
2717        use std::time::Instant;
2718
2719        let mut small: Virtualized<i32> = Virtualized::new(1_000);
2720        for i in 0..1_000 {
2721            small.push(i);
2722        }
2723        small.set_visible_count(24);
2724
2725        let mut large: Virtualized<i32> = Virtualized::new(100_000);
2726        for i in 0..100_000 {
2727            large.push(i);
2728        }
2729        large.set_visible_count(24);
2730
2731        let iterations = 10_000;
2732
2733        // Warm up both paths so the timed runs are not skewed by first-touch
2734        // page faults / branch predictor / cache warming.
2735        for _ in 0..iterations {
2736            small.scroll(1);
2737            small.scroll(-1);
2738            large.scroll(1);
2739            large.scroll(-1);
2740        }
2741
2742        // Take the best (minimum) of several timed runs for each list. The
2743        // minimum is the measurement least contaminated by scheduling jitter,
2744        // GC of other processes, and CI load — exactly the noise that made the
2745        // old single-shot comparison flaky.
2746        let measure = |v: &mut Virtualized<i32>| -> std::time::Duration {
2747            let runs = 5;
2748            let mut best = std::time::Duration::MAX;
2749            for _ in 0..runs {
2750                let start = Instant::now();
2751                for _ in 0..iterations {
2752                    v.scroll(1);
2753                    v.scroll(-1);
2754                }
2755                best = best.min(start.elapsed());
2756            }
2757            best
2758        };
2759
2760        let small_time = measure(&mut small);
2761        let large_time = measure(&mut large);
2762
2763        // The real signal we care about is "scroll cost does NOT grow with list
2764        // size" (i.e. it is O(1), not O(n)). With n differing by 100x, a truly
2765        // O(n) scroll would make `large_time` ~100x `small_time`. A generous
2766        // constant-factor ceiling distinguishes O(1) from O(n) without flaking
2767        // on scheduling jitter, so we allow a wide multiplier here.
2768        let ceiling = small_time
2769            .checked_mul(10)
2770            .unwrap_or(std::time::Duration::MAX);
2771        assert!(
2772            large_time < ceiling,
2773            "Scroll is not O(1) (grows with list size): 1K={:?}, 100K={:?}",
2774            small_time,
2775            large_time
2776        );
2777    }
2778
2779    #[test]
2780    fn render_partially_offscreen_top_skips_item() {
2781        use ftui_render::grapheme_pool::GraphemePool;
2782
2783        // Items with height 2, each rendering its index as a character
2784        struct IndexedItem(usize);
2785        impl RenderItem for IndexedItem {
2786            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2787                let ch = char::from_digit(self.0 as u32, 10).unwrap();
2788                for y in area.y..area.bottom() {
2789                    frame.buffer.set(area.x, y, Cell::from_char(ch));
2790                }
2791            }
2792            fn height(&self) -> u16 {
2793                2
2794            }
2795        }
2796
2797        // Need 4+ items so scroll_offset=1 is valid:
2798        // items_per_viewport = 5/2 = 2, max_offset = 4-2 = 2
2799        let items = vec![
2800            IndexedItem(0),
2801            IndexedItem(1),
2802            IndexedItem(2),
2803            IndexedItem(3),
2804        ];
2805        let list = VirtualizedList::new(&items).fixed_height(2);
2806
2807        // Scroll so item 1 is at top, item 0 is in overscan (above viewport)
2808        let mut state = VirtualizedListState::new().with_overscan(1);
2809        state.scroll_offset = 1; // Item 1 is top visible. Item 0 is in overscan.
2810
2811        let mut pool = GraphemePool::new();
2812        let mut frame = Frame::new(10, 5, &mut pool);
2813
2814        // Render at y=0 (terminal top edge)
2815        list.render(Rect::new(0, 0, 10, 5), &mut frame, &mut state);
2816
2817        // With scroll_offset=1 and overscan=1:
2818        // - render_start = 1 - 1 = 0 (include item 0 in overscan)
2819        // - Item 0 would render at y_offset = (0-1)*2 = -2
2820        // - area.y + y_offset = 0 + (-2) = -2 < 0, so item 0 must be SKIPPED
2821        // - Item 1 renders at y_offset = (1-1)*2 = 0
2822        //
2823        // Row 0 should be '1' (from Item 1), NOT '0' (from Item 0 ghosting)
2824        let cell = frame.buffer.get(0, 0).unwrap();
2825        assert_eq!(cell.content.as_char(), Some('1'));
2826    }
2827
2828    #[test]
2829    fn render_bottom_boundary_clips_partial_item() {
2830        use ftui_render::grapheme_pool::GraphemePool;
2831
2832        struct IndexedItem(u16);
2833        impl RenderItem for IndexedItem {
2834            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2835                let ch = char::from_digit(self.0 as u32, 10).unwrap();
2836                for y in area.y..area.bottom() {
2837                    frame.buffer.set(area.x, y, Cell::from_char(ch));
2838                }
2839            }
2840            fn height(&self) -> u16 {
2841                2
2842            }
2843        }
2844
2845        let items = vec![IndexedItem(0), IndexedItem(1), IndexedItem(2)];
2846        let list = VirtualizedList::new(&items)
2847            .fixed_height(2)
2848            .show_scrollbar(false);
2849        let mut state = VirtualizedListState::new();
2850
2851        let mut pool = GraphemePool::new();
2852        let mut frame = Frame::new(4, 4, &mut pool);
2853
2854        // Viewport height 3 means the second item is only partially visible.
2855        list.render(Rect::new(0, 0, 4, 3), &mut frame, &mut state);
2856
2857        assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
2858        assert_eq!(frame.buffer.get(0, 1).unwrap().content.as_char(), Some('0'));
2859        assert_eq!(frame.buffer.get(0, 2).unwrap().content.as_char(), Some('1'));
2860        // Row outside the viewport should remain empty.
2861        assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), None);
2862    }
2863
2864    #[test]
2865    fn render_after_fling_advances_visible_rows() {
2866        use ftui_render::grapheme_pool::GraphemePool;
2867
2868        struct IndexedItem(u16);
2869        impl RenderItem for IndexedItem {
2870            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
2871                let ch = char::from_digit(self.0 as u32, 10).unwrap();
2872                for y in area.y..area.bottom() {
2873                    frame.buffer.set(area.x, y, Cell::from_char(ch));
2874                }
2875            }
2876        }
2877
2878        let items: Vec<IndexedItem> = (0..10).map(IndexedItem).collect();
2879        let list = VirtualizedList::new(&items)
2880            .fixed_height(1)
2881            .show_scrollbar(false);
2882        let mut state = VirtualizedListState::new();
2883
2884        let mut pool = GraphemePool::new();
2885        let mut frame = Frame::new(4, 3, &mut pool);
2886        let area = Rect::new(0, 0, 4, 3);
2887
2888        // Initial render establishes visible_count and baseline top row.
2889        list.render(area, &mut frame, &mut state);
2890        assert_eq!(state.scroll_offset(), 0);
2891        assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
2892
2893        // Momentum scroll: 40.0 * 0.1s = 4 rows.
2894        state.fling(40.0);
2895        state.tick(Duration::from_millis(100), items.len());
2896        assert_eq!(state.scroll_offset(), 4);
2897
2898        frame.buffer.clear();
2899        list.render(area, &mut frame, &mut state);
2900        assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('4'));
2901    }
2902
2903    #[test]
2904    fn render_empty_virtualized_list_clears_stale_viewport() {
2905        use ftui_render::grapheme_pool::GraphemePool;
2906
2907        let items: Vec<String> = Vec::new();
2908        let list = VirtualizedList::new(&items).show_scrollbar(false);
2909        let mut state = VirtualizedListState::new();
2910        let mut pool = GraphemePool::new();
2911        let mut frame = Frame::new(6, 3, &mut pool);
2912        let area = Rect::new(0, 0, 6, 3);
2913        frame.buffer.fill(area, Cell::from_char('X'));
2914
2915        list.render(area, &mut frame, &mut state);
2916
2917        assert_eq!(raw_row_text(&frame, 0), "      ");
2918        assert_eq!(raw_row_text(&frame, 1), "      ");
2919        assert_eq!(raw_row_text(&frame, 2), "      ");
2920    }
2921
2922    #[test]
2923    fn render_shorter_virtualized_row_clears_stale_suffix() {
2924        use ftui_render::grapheme_pool::GraphemePool;
2925
2926        let long_items = vec!["Hello".to_string()];
2927        let short_items = vec!["Hi".to_string()];
2928        let area = Rect::new(0, 0, 6, 1);
2929        let mut state = VirtualizedListState::new();
2930        let mut pool = GraphemePool::new();
2931        let mut frame = Frame::new(6, 1, &mut pool);
2932
2933        VirtualizedList::new(&long_items)
2934            .show_scrollbar(false)
2935            .render(area, &mut frame, &mut state);
2936        VirtualizedList::new(&short_items)
2937            .show_scrollbar(false)
2938            .render(area, &mut frame, &mut state);
2939
2940        assert_eq!(raw_row_text(&frame, 0), "Hi    ");
2941    }
2942
2943    #[test]
2944    fn test_memory_bounded_by_ring_capacity() {
2945        use crate::log_ring::LogRing;
2946
2947        let mut ring: LogRing<String> = LogRing::new(1_000);
2948
2949        // Add 100K items
2950        for i in 0..100_000 {
2951            ring.push(format!("Line {}", i));
2952        }
2953
2954        // Only 1K in memory
2955        assert_eq!(ring.len(), 1_000);
2956        assert_eq!(ring.total_count(), 100_000);
2957        assert_eq!(ring.first_index(), 99_000);
2958
2959        // Can still access recent items
2960        assert!(ring.get(99_999).is_some());
2961        assert!(ring.get(99_000).is_some());
2962        // Old items evicted
2963        assert!(ring.get(0).is_none());
2964        assert!(ring.get(98_999).is_none());
2965    }
2966
2967    #[test]
2968    fn test_visible_range_constant_regardless_of_total() {
2969        let mut small: Virtualized<i32> = Virtualized::new(100);
2970        for i in 0..100 {
2971            small.push(i);
2972        }
2973        let small_range = small.visible_range(24);
2974
2975        let mut large: Virtualized<i32> = Virtualized::new(100_000);
2976        for i in 0..100_000 {
2977            large.push(i);
2978        }
2979        let large_range = large.visible_range(24);
2980
2981        // Both should return exactly 24 visible items
2982        assert_eq!(small_range.end - small_range.start, 24);
2983        assert_eq!(large_range.end - large_range.start, 24);
2984    }
2985
2986    #[test]
2987    fn test_virtualized_list_state_page_up_down() {
2988        let mut state = VirtualizedListState::new();
2989        state.visible_count = 10;
2990
2991        // Page down
2992        state.page_down(50);
2993        assert_eq!(state.scroll_offset(), 9);
2994
2995        // Page down again
2996        state.page_down(50);
2997        assert_eq!(state.scroll_offset(), 18);
2998
2999        // Page up
3000        state.page_up(50);
3001        assert_eq!(state.scroll_offset(), 9);
3002
3003        // Page up again
3004        state.page_up(50);
3005        assert_eq!(state.scroll_offset(), 0);
3006    }
3007
3008    // ========================================================================
3009    // VariableHeightsFenwick tests (bd-2zbk.7)
3010    // ========================================================================
3011
3012    #[test]
3013    fn test_variable_heights_fenwick_new() {
3014        let tracker = VariableHeightsFenwick::new(2, 10);
3015        assert_eq!(tracker.len(), 10);
3016        assert!(!tracker.is_empty());
3017        assert_eq!(tracker.default_height(), 2);
3018    }
3019
3020    #[test]
3021    fn test_variable_heights_fenwick_empty() {
3022        let tracker = VariableHeightsFenwick::new(1, 0);
3023        assert!(tracker.is_empty());
3024        assert_eq!(tracker.total_height(), 0);
3025    }
3026
3027    #[test]
3028    fn test_variable_heights_fenwick_from_heights() {
3029        let heights = vec![3, 2, 5, 1, 4];
3030        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3031
3032        assert_eq!(tracker.len(), 5);
3033        assert_eq!(tracker.get(0), 3);
3034        assert_eq!(tracker.get(1), 2);
3035        assert_eq!(tracker.get(2), 5);
3036        assert_eq!(tracker.get(3), 1);
3037        assert_eq!(tracker.get(4), 4);
3038        assert_eq!(tracker.total_height(), 15);
3039    }
3040
3041    #[test]
3042    fn test_variable_heights_fenwick_offset_of_item() {
3043        // Heights: [3, 2, 5, 1, 4] -> offsets: [0, 3, 5, 10, 11]
3044        let heights = vec![3, 2, 5, 1, 4];
3045        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3046
3047        assert_eq!(tracker.offset_of_item(0), 0);
3048        assert_eq!(tracker.offset_of_item(1), 3);
3049        assert_eq!(tracker.offset_of_item(2), 5);
3050        assert_eq!(tracker.offset_of_item(3), 10);
3051        assert_eq!(tracker.offset_of_item(4), 11);
3052        assert_eq!(tracker.offset_of_item(5), 15); // beyond end
3053    }
3054
3055    #[test]
3056    fn test_variable_heights_fenwick_find_item_at_offset() {
3057        // Heights: [3, 2, 5, 1, 4] -> cumulative: [3, 5, 10, 11, 15]
3058        let heights = vec![3, 2, 5, 1, 4];
3059        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3060
3061        // Offset 0 should be item 0
3062        assert_eq!(tracker.find_item_at_offset(0), 0);
3063        // Offset 1 should be item 0 (within first item)
3064        assert_eq!(tracker.find_item_at_offset(1), 0);
3065        // Offset 3 should be item 1 (starts at offset 3)
3066        assert_eq!(tracker.find_item_at_offset(3), 1);
3067        // Offset 5 should be item 2
3068        assert_eq!(tracker.find_item_at_offset(5), 2);
3069        // Offset 10 should be item 3
3070        assert_eq!(tracker.find_item_at_offset(10), 3);
3071        // Offset 11 should be item 4
3072        assert_eq!(tracker.find_item_at_offset(11), 4);
3073        // Offset 15 should be end (beyond all items)
3074        assert_eq!(tracker.find_item_at_offset(15), 5);
3075    }
3076
3077    #[test]
3078    fn fenwick_large_height_totals_do_not_wrap() {
3079        let heights = vec![u16::MAX; 131_072];
3080        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3081        let offset = 4_294_836_224_u32;
3082        assert_eq!(
3083            tracker.find_item_at_offset(offset),
3084            (u64::from(offset) / u64::from(u16::MAX)) as usize,
3085            "a wrapped root aggregate must not skip the entire list"
3086        );
3087        assert_eq!(tracker.total_height(), u32::MAX);
3088        assert_eq!(tracker.offset_of_item(131_072), u32::MAX);
3089    }
3090
3091    #[test]
3092    #[should_panic(expected = "height index exceeds usize")]
3093    fn fenwick_rejects_unrepresentable_index() {
3094        VariableHeightsFenwick::default().set(usize::MAX, 1);
3095    }
3096
3097    #[test]
3098    fn fenwick_large_updates_and_resize_match_u64_oracle() {
3099        fn check(tracker: &VariableHeightsFenwick, heights: &[u16]) {
3100            let mut prefixes = Vec::with_capacity(heights.len() + 1);
3101            prefixes.push(0u64);
3102            for &height in heights {
3103                prefixes.push(prefixes.last().copied().unwrap() + u64::from(height));
3104            }
3105            let total = prefixes.last().copied().unwrap();
3106            assert_eq!(tracker.len(), heights.len());
3107            assert_eq!(tracker.total_height_exact(), total);
3108            assert_eq!(
3109                tracker.total_height(),
3110                total.min(u64::from(u32::MAX)) as u32
3111            );
3112            let mut queries = vec![0, 1, u64::from(u32::MAX) - 1, u64::from(u32::MAX), total];
3113            for idx in (0..=heights.len()).step_by(1_024).chain([heights.len()]) {
3114                assert_eq!(tracker.offset_of_item_exact(idx), prefixes[idx]);
3115                assert_eq!(
3116                    tracker.offset_of_item(idx),
3117                    prefixes[idx].min(u64::from(u32::MAX)) as u32
3118                );
3119                queries.extend([
3120                    prefixes[idx].saturating_sub(1),
3121                    prefixes[idx],
3122                    prefixes[idx] + 1,
3123                ]);
3124            }
3125            for offset in queries {
3126                let expected = if offset == 0 {
3127                    0
3128                } else {
3129                    prefixes[1..].partition_point(|&prefix| prefix <= offset)
3130                };
3131                assert_eq!(tracker.find_item_at_offset_exact(offset), expected);
3132                if let Ok(offset) = u32::try_from(offset) {
3133                    assert_eq!(tracker.find_item_at_offset(offset), expected);
3134                }
3135            }
3136        }
3137
3138        // The middle length totals exactly u32::MAX; neighboring lengths
3139        // exercise both sides of the public saturation boundary.
3140        for len in [65_536, 65_537, 65_538, 131_072] {
3141            let mut heights = vec![u16::MAX; len];
3142            let mut tracker = VariableHeightsFenwick::new(u16::MAX, len);
3143            check(&tracker, &heights);
3144            for idx in [0, 1, 32_768, 65_535, len - 1] {
3145                tracker.set(idx, 0);
3146                heights[idx] = 0;
3147                assert_eq!(tracker.get(idx), 0);
3148            }
3149            check(&tracker, &heights);
3150            tracker.set(0, u16::MAX);
3151            heights[0] = u16::MAX;
3152            tracker.resize(65_536);
3153            heights.truncate(65_536);
3154            check(&tracker, &heights);
3155            tracker.resize(65_540);
3156            heights.resize(65_540, u16::MAX);
3157            check(&tracker, &heights);
3158        }
3159
3160        // Deterministic varied heights and repeated signed updates exercise
3161        // aggregate values that uniform-height arithmetic alone cannot cover.
3162        let mut seed = 0xa076_1d64_78bd_642fu64;
3163        let mut heights: Vec<u16> = (0..131_072)
3164            .map(|_| {
3165                seed = seed.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
3166                32_768 + ((seed >> 48) as u16 / 2)
3167            })
3168            .collect();
3169        let mut tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3170        for idx in (0..heights.len()).step_by(997) {
3171            heights[idx] = (idx % 65_536) as u16;
3172            tracker.set(idx, heights[idx]);
3173            assert_eq!(tracker.get(idx), heights[idx]);
3174        }
3175        check(&tracker, &heights);
3176        tracker.drop_front(3);
3177        check(&tracker, &heights[3..]);
3178        heights.fill(u16::MAX);
3179        tracker.rebuild(&heights);
3180        check(&tracker, &heights);
3181        tracker.clear();
3182        check(&tracker, &[]);
3183        tracker.resize(4);
3184        check(&tracker, &[1; 4]);
3185    }
3186
3187    #[test]
3188    fn fenwick_large_visible_range_keeps_tail_reachable() {
3189        let len = 65_548;
3190        let mut virt: Virtualized<()> =
3191            Virtualized::external(len, 10).with_variable_heights_fenwick(u16::MAX, len);
3192        for idx in 65_538..len {
3193            virt.observe_height(idx, 1);
3194        }
3195        virt.scroll_to_bottom();
3196        assert_eq!(virt.visible_range(5), len - 5..len);
3197        virt.scroll_to(len - 8);
3198        assert_eq!(virt.visible_range(5), len - 8..len - 3);
3199    }
3200
3201    #[test]
3202    fn fenwick_large_scrollbar_renders_proportionally_at_32_bit_capacity() {
3203        fn thumb_rows(mut state: ScrollbarState) -> Vec<u16> {
3204            let scrollbar =
3205                Scrollbar::new(ScrollbarOrientation::VerticalRight).symbols(".", "T", None, None);
3206            let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
3207            let mut frame = Frame::new(1, 21, &mut pool);
3208            scrollbar.render(Rect::new(0, 0, 1, 21), &mut frame, &mut state);
3209            (0..21)
3210                .filter(|&y| frame.buffer.get(0, y).unwrap().content.as_char() == Some('T'))
3211                .collect()
3212        }
3213
3214        // Execute the production scaling helper and real scrollbar renderer
3215        // with a simulated 32-bit capacity; this is not a wasm execution.
3216        let capacity = u32::MAX as usize;
3217        let total = 131_072 * u64::from(u16::MAX);
3218        let viewport = 20;
3219        let max_position = total - u64::from(viewport);
3220        for (position, expected_row) in [
3221            (0, 0),
3222            (max_position / 4, 5),
3223            (max_position / 2, 10),
3224            (max_position / 4 * 3, 15),
3225            (max_position, 20),
3226            (total, 20),
3227        ] {
3228            let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
3229            assert_eq!(scaled.content_length, capacity);
3230            assert!(scaled.viewport_length > 0);
3231            assert_eq!(thumb_rows(scaled), vec![expected_row]);
3232        }
3233
3234        let position = u64::from(u32::MAX) + u64::from(u16::MAX);
3235        let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
3236        assert_eq!(thumb_rows(scaled), vec![10]);
3237        // The former independent saturation gives the wrong actual geometry.
3238        let saturated = ScrollbarState::new(capacity, capacity, viewport.into());
3239        assert_eq!(thumb_rows(saturated), vec![20]);
3240
3241        for (total, position, viewport) in [(0, 0, 0), (100, 50, 20), (u64::from(u32::MAX), 7, 5)] {
3242            let exact = scrollbar_state_for_rows(total, position, viewport, capacity);
3243            assert_eq!(exact.content_length, total as usize);
3244            assert_eq!(exact.position, position as usize);
3245            assert_eq!(exact.viewport_length, usize::from(viewport));
3246        }
3247        if usize::BITS > 32 {
3248            let exact = scrollbar_state_for_rows(total, position, viewport, usize::MAX);
3249            assert_eq!(exact.content_length as u64, total);
3250            assert_eq!(exact.position as u64, position);
3251            assert_eq!(exact.viewport_length, usize::from(viewport));
3252        }
3253    }
3254
3255    #[test]
3256    fn test_variable_heights_fenwick_visible_count() {
3257        // Heights: [3, 2, 5, 1, 4]
3258        let heights = vec![3, 2, 5, 1, 4];
3259        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3260
3261        // Viewport 5: items 0 (h=3) + 1 (h=2) = 5 exactly
3262        assert_eq!(tracker.visible_count(0, 5), 2);
3263
3264        // Viewport 4: item 0 fits and item 1 is partially visible.
3265        assert_eq!(tracker.visible_count(0, 4), 2);
3266
3267        // Viewport 10: items 0+1+2 = 10 exactly
3268        assert_eq!(tracker.visible_count(0, 10), 3);
3269
3270        // From item 2, viewport 6: item 2 (h=5) + item 3 (h=1) = 6
3271        assert_eq!(tracker.visible_count(2, 6), 2);
3272    }
3273
3274    #[test]
3275    fn test_variable_heights_fenwick_visible_count_viewport_beyond_total_height() {
3276        let heights = vec![1, 1, 1];
3277        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3278
3279        // Viewport extends past the end: must never overcount.
3280        assert_eq!(tracker.visible_count(0, 10), 3);
3281        assert_eq!(tracker.visible_count(1, 10), 2);
3282        assert_eq!(tracker.visible_count(2, 10), 1);
3283    }
3284
3285    #[test]
3286    fn test_variable_heights_fenwick_set() {
3287        let mut tracker = VariableHeightsFenwick::new(1, 5);
3288
3289        // All items should start with default height
3290        assert_eq!(tracker.get(0), 1);
3291        assert_eq!(tracker.total_height(), 5);
3292
3293        // Set item 2 to height 10
3294        tracker.set(2, 10);
3295        assert_eq!(tracker.get(2), 10);
3296        assert_eq!(tracker.total_height(), 14); // 1+1+10+1+1
3297    }
3298
3299    #[test]
3300    fn test_variable_heights_fenwick_resize() {
3301        let mut tracker = VariableHeightsFenwick::new(2, 3);
3302        assert_eq!(tracker.len(), 3);
3303        assert_eq!(tracker.total_height(), 6);
3304
3305        // Grow
3306        tracker.resize(5);
3307        assert_eq!(tracker.len(), 5);
3308        assert_eq!(tracker.total_height(), 10);
3309        assert_eq!(tracker.get(4), 2);
3310
3311        // Shrink
3312        tracker.resize(2);
3313        assert_eq!(tracker.len(), 2);
3314        assert_eq!(tracker.total_height(), 4);
3315    }
3316
3317    #[test]
3318    fn test_variable_heights_fenwick_point_update_and_range_query() {
3319        fn range_sum(tracker: &VariableHeightsFenwick, left: usize, right: usize) -> u32 {
3320            tracker
3321                .offset_of_item(right.saturating_add(1))
3322                .saturating_sub(tracker.offset_of_item(left))
3323        }
3324
3325        let mut tracker = VariableHeightsFenwick::from_heights(&[2, 4, 1, 3, 5, 2], 1);
3326        let mut naive = [2_u32, 4, 1, 3, 5, 2];
3327
3328        tracker.set(2, 7);
3329        naive[2] = 7;
3330        tracker.set(5, 1);
3331        naive[5] = 1;
3332        tracker.set(0, 6);
3333        naive[0] = 6;
3334
3335        let mut running = 0u32;
3336        for (i, value) in naive.iter().enumerate() {
3337            running = running.saturating_add(*value);
3338            assert_eq!(tracker.offset_of_item(i + 1), running);
3339        }
3340
3341        let naive_sum = |left: usize, right: usize| -> u32 { naive[left..=right].iter().sum() };
3342        assert_eq!(range_sum(&tracker, 0, 0), naive_sum(0, 0));
3343        assert_eq!(range_sum(&tracker, 1, 3), naive_sum(1, 3));
3344        assert_eq!(range_sum(&tracker, 2, 5), naive_sum(2, 5));
3345    }
3346
3347    proptest! {
3348        #![proptest_config(ProptestConfig::with_cases(96))]
3349
3350        #[test]
3351        fn property_measured_heights_survive_mutations(
3352            operations in proptest::collection::vec((0u8..3, 0usize..150, 1u16..32), 1..80)
3353        ) {
3354            let mut tracker = VariableHeightsFenwick::new(2, 0);
3355            let mut expected: Vec<Option<u16>> = Vec::new();
3356            for (operation, index, height) in operations {
3357                match operation {
3358                    0 => {
3359                        if index >= expected.len() {
3360                            expected.resize(index + 1, None);
3361                        }
3362                        expected[index] = Some(height);
3363                        tracker.set(index, height);
3364                    }
3365                    1 => {
3366                        expected.resize(index, None);
3367                        tracker.resize(index);
3368                    }
3369                    _ => {
3370                        expected.drain(..index.min(expected.len()));
3371                        tracker.drop_front(index);
3372                    }
3373                }
3374                prop_assert_eq!(tracker.len(), expected.len());
3375                prop_assert_eq!(
3376                    tracker.unmeasured_count(),
3377                    expected.iter().filter(|height| height.is_none()).count()
3378                );
3379                let mut prefix = 0;
3380                for (index, height) in expected.iter().enumerate() {
3381                    prop_assert_eq!(tracker.offset_of_item(index), prefix);
3382                    prop_assert_eq!(tracker.is_measured(index), height.is_some());
3383                    prop_assert_eq!(tracker.get(index), height.unwrap_or(2));
3384                    prefix += u32::from(height.unwrap_or(2));
3385                }
3386                prop_assert_eq!(tracker.total_height(), prefix);
3387            }
3388        }
3389
3390        #[test]
3391        fn property_variable_heights_fenwick_prefix_sums_match_naive(
3392            heights in proptest::collection::vec(1u16..=32u16, 1..160)
3393        ) {
3394            let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3395
3396            let mut naive_prefix = 0u32;
3397            prop_assert_eq!(tracker.offset_of_item(0), 0);
3398            for (i, height) in heights.iter().enumerate() {
3399                naive_prefix = naive_prefix.saturating_add(u32::from(*height));
3400                prop_assert_eq!(
3401                    tracker.offset_of_item(i + 1),
3402                    naive_prefix,
3403                    "prefix mismatch at index {} for heights {:?}",
3404                    i,
3405                    heights
3406                );
3407            }
3408        }
3409
3410        #[test]
3411        fn property_variable_heights_fenwick_visible_count_matches_naive(
3412            heights in proptest::collection::vec(1u16..=24u16, 1..128),
3413            start_idx in 0usize..192usize,
3414            viewport_height in 1u16..=120u16
3415        ) {
3416            fn naive_visible_count(heights: &[u16], start_idx: usize, viewport_height: u16) -> usize {
3417                if heights.is_empty() || viewport_height == 0 {
3418                    return 0;
3419                }
3420                let start = start_idx.min(heights.len());
3421                if start >= heights.len() {
3422                    return 0;
3423                }
3424
3425                let start_offset: u32 = heights[..start].iter().map(|&h| u32::from(h)).sum();
3426                let end_offset = start_offset.saturating_add(u32::from(viewport_height));
3427                let mut count = 0usize;
3428                let mut cursor = start_offset;
3429                for &height in &heights[start..] {
3430                    if cursor >= end_offset {
3431                        break;
3432                    }
3433                    count = count.saturating_add(1);
3434                    cursor = cursor.saturating_add(u32::from(height));
3435                }
3436
3437                if count == 0 { 1 } else { count }
3438            }
3439
3440            let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3441            let expected = naive_visible_count(&heights, start_idx, viewport_height);
3442            let actual = tracker.visible_count(start_idx, viewport_height);
3443            prop_assert_eq!(
3444                actual,
3445                expected,
3446                "visible_count mismatch for start={} viewport={} heights={:?}",
3447                start_idx,
3448                viewport_height,
3449                heights
3450            );
3451        }
3452    }
3453
3454    /// With a predictor attached, unmeasured slots follow the posterior mean
3455    /// of the measured rows (Normal-Normal update, prior κ₀=2 at μ₀=1) instead
3456    /// of the constant default, and measured slots are never touched.
3457    #[test]
3458    fn fenwick_predictor_fills_unmeasured_slots_and_tracks_observations() {
3459        let config = PredictorConfig {
3460            default_height: 1,
3461            prior_mean: 1.0,
3462            prior_strength: 2.0,
3463            ..PredictorConfig::default()
3464        };
3465        let mut tracker = VariableHeightsFenwick::new(1, 10).with_predictor(config);
3466        assert_eq!(tracker.predicted_height(), 1, "cold start uses the default");
3467        assert_eq!(tracker.unmeasured_count(), 10);
3468        assert_eq!(tracker.total_height(), 10);
3469
3470        // Three rows measure 3 tall: posterior mean (2·1 + 3·3) / 5 = 2.2 → 2.
3471        for idx in 0..3 {
3472            tracker.set(idx, 3);
3473        }
3474        assert_eq!(tracker.predicted_height(), 2);
3475        assert_eq!(tracker.unmeasured_count(), 7);
3476        assert_eq!(tracker.get(0), 3, "measured slots keep their measurement");
3477        assert_eq!(tracker.get(7), 2, "unmeasured slots hold the prediction");
3478        assert_eq!(tracker.total_height(), 3 * 3 + 7 * 2);
3479        assert_eq!(tracker.offset_of_item(4), 9 + 2);
3480
3481        // Three more: (2·1 + 6·3) / 8 = 2.5 → 3; the unmeasured tail is refilled.
3482        for idx in 3..6 {
3483            tracker.set(idx, 3);
3484        }
3485        assert_eq!(tracker.predicted_height(), 3);
3486        assert_eq!(tracker.total_height(), 6 * 3 + 4 * 3);
3487        assert!(tracker.is_measured(5) && !tracker.is_measured(6));
3488        assert_eq!(
3489            tracker.predictor().map(HeightPredictor::total_measurements),
3490            Some(6)
3491        );
3492
3493        // Growth uses the prediction, not the constructor default.
3494        tracker.resize(12);
3495        assert_eq!(tracker.get(11), 3);
3496        assert_eq!(tracker.unmeasured_count(), 6);
3497        assert_eq!(tracker.find_item_at_offset(tracker.total_height() - 1), 11);
3498
3499        // Shrinking below measured rows keeps the bookkeeping consistent.
3500        tracker.resize(4);
3501        assert_eq!(tracker.unmeasured_count(), 0);
3502        tracker.resize(6);
3503        assert_eq!(tracker.unmeasured_count(), 2);
3504        assert_eq!(tracker.total_height(), 4 * 3 + 2 * 3);
3505
3506        // Rebuild trains on every provided height and marks all as measured.
3507        tracker.rebuild(&[5, 5, 5, 5, 5, 5, 5, 5]);
3508        assert_eq!(tracker.unmeasured_count(), 0);
3509        assert_eq!(tracker.total_height(), 40);
3510        assert!(
3511            tracker.predicted_height() >= 4,
3512            "posterior pulled toward the taller rows"
3513        );
3514
3515        // Without a predictor nothing changes: unmeasured slots stay at the default.
3516        let mut plain = VariableHeightsFenwick::new(2, 4);
3517        plain.set(0, 9);
3518        assert_eq!(plain.predicted_height(), 2);
3519        assert_eq!(plain.get(3), 2);
3520        assert_eq!(plain.unmeasured_count(), 3);
3521        assert!(plain.predictor().is_none());
3522    }
3523
3524    /// `Virtualized::with_height_prediction` switches to the Fenwick tracker
3525    /// and `observe_height` trains the model; fixed heights ignore it.
3526    #[test]
3527    fn virtualized_height_prediction_observe_height_trains_the_model() {
3528        let mut virt: Virtualized<i32> = Virtualized::new(100)
3529            .with_fixed_height(1)
3530            .with_height_prediction(PredictorConfig::default());
3531        assert!(matches!(virt.item_height(), ItemHeight::VariableFenwick(_)));
3532        assert_eq!(virt.unmeasured_item_height(), 1);
3533
3534        // Four rows of height 4: (2·1 + 4·4) / 6 = 3.
3535        for idx in 0..4 {
3536            virt.observe_height(idx, 4);
3537        }
3538        assert_eq!(virt.unmeasured_item_height(), 3);
3539        let ItemHeight::VariableFenwick(tracker) = virt.item_height() else {
3540            panic!("expected the Fenwick tracker");
3541        };
3542        assert_eq!(tracker.get(0), 4);
3543        assert_eq!(tracker.len(), 4);
3544        assert_eq!(
3545            tracker.get(40),
3546            3,
3547            "beyond the tracked length: the prediction"
3548        );
3549
3550        let mut fixed: Virtualized<i32> = Virtualized::new(10).with_fixed_height(2);
3551        fixed.observe_height(0, 9);
3552        assert_eq!(
3553            fixed.unmeasured_item_height(),
3554            2,
3555            "fixed heights ignore observations"
3556        );
3557
3558        let mut linear: Virtualized<i32> =
3559            Virtualized::new(10).with_item_height(ItemHeight::Variable(HeightCache::new(2, 8)));
3560        linear.observe_height(1, 5);
3561        assert_eq!(linear.unmeasured_item_height(), 2);
3562        let ItemHeight::Variable(cache) = linear.item_height() else {
3563            panic!("expected the linear cache");
3564        };
3565        assert_eq!(cache.get(1), 5);
3566    }
3567
3568    #[test]
3569    fn test_virtualized_with_variable_heights_fenwick() {
3570        let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 10);
3571
3572        for i in 0..10 {
3573            virt.push(i);
3574        }
3575
3576        // All items height 2, viewport 6 -> 3 items visible
3577        let range = virt.visible_range(6);
3578        assert_eq!(range.end - range.start, 3);
3579    }
3580
3581    proptest! {
3582        /// The Fenwick tracker is an O(log n) reimplementation of the cache's
3583        /// linear scan, and the two must answer identically. The only existing
3584        /// Fenwick coverage uses one viewport and uniform heights, which cannot
3585        /// catch a divergence in the bottom-anchoring arms - those only engage
3586        /// when the tail from the current offset cannot fill the viewport.
3587        #[test]
3588        fn variable_height_implementations_agree(
3589            heights in proptest::collection::vec(1u16..=5, 1..40),
3590            viewport in 1u16..=20,
3591            default_height in 1u16..=4,
3592            offset_seed in 0usize..64,
3593        ) {
3594            let len = heights.len();
3595            // `with_variable_heights` has built a Fenwick tracker since
3596            // 4c697f8c, so naming it as the cache side compared one
3597            // implementation against itself. The capacity holds every item,
3598            // so nothing is evicted and the two must agree exactly.
3599            let mut cache: Virtualized<usize> = Virtualized::new(len)
3600                .with_item_height(ItemHeight::Variable(HeightCache::new(default_height, len)));
3601            let mut fenwick: Virtualized<usize> =
3602                Virtualized::new(len).with_variable_heights_fenwick(default_height, len);
3603            for i in 0..len {
3604                cache.push(i);
3605                fenwick.push(i);
3606            }
3607            for (idx, height) in heights.iter().enumerate() {
3608                cache.observe_height(idx, *height);
3609                fenwick.observe_height(idx, *height);
3610            }
3611
3612            let offset = offset_seed % len;
3613            cache.scroll_to(offset);
3614            fenwick.scroll_to(offset);
3615            prop_assert_eq!(
3616                cache.visible_range(viewport),
3617                fenwick.visible_range(viewport),
3618                "implementations disagree at len={} viewport={} offset={}",
3619                len,
3620                viewport,
3621                offset
3622            );
3623
3624            // Both must also be able to reach the last item.
3625            cache.scroll_to_bottom();
3626            fenwick.scroll_to_bottom();
3627            let bottom_cache = cache.visible_range(viewport);
3628            let bottom_fenwick = fenwick.visible_range(viewport);
3629            prop_assert_eq!(&bottom_cache, &bottom_fenwick, "bottom anchoring disagrees");
3630            prop_assert!(
3631                bottom_cache.contains(&(len - 1)),
3632                "last item unreachable: range {:?} of {} items",
3633                bottom_cache,
3634                len
3635            );
3636
3637            // A trim renumbers every surviving item. A tracker that keeps the
3638            // old indices then reports each measurement against an item it was
3639            // not taken from, which is what the legacy cache did.
3640            let keep = 1 + offset_seed % len;
3641            if keep < len {
3642                prop_assert_eq!(cache.trim_front(keep), fenwick.trim_front(keep));
3643                let len = cache.len();
3644                cache.scroll_to_bottom();
3645                fenwick.scroll_to_bottom();
3646                let trimmed_cache = cache.visible_range(viewport);
3647                let trimmed_fenwick = fenwick.visible_range(viewport);
3648                prop_assert_eq!(
3649                    &trimmed_cache,
3650                    &trimmed_fenwick,
3651                    "implementations disagree after trimming to {} items",
3652                    keep
3653                );
3654                prop_assert!(
3655                    trimmed_cache.contains(&(len - 1)),
3656                    "last item unreachable after a trim: range {:?} of {} items",
3657                    trimmed_cache,
3658                    len
3659                );
3660            }
3661        }
3662    }
3663
3664    #[test]
3665    fn test_variable_heights_fenwick_performance() {
3666        use std::time::Instant;
3667
3668        // Create large tracker
3669        let n = 100_000;
3670        let heights: Vec<u16> = (0..n).map(|i| (i % 10 + 1) as u16).collect();
3671        let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
3672
3673        // Warm up
3674        let _ = tracker.find_item_at_offset(500_000);
3675        let _ = tracker.offset_of_item(50_000);
3676
3677        // Benchmark find_item_at_offset (O(log n))
3678        let start = Instant::now();
3679        let mut _sink = 0usize;
3680        for i in 0..10_000 {
3681            _sink = _sink.wrapping_add(tracker.find_item_at_offset((i * 50) as u32));
3682        }
3683        let find_time = start.elapsed();
3684
3685        // Benchmark offset_of_item (O(log n))
3686        let start = Instant::now();
3687        let mut _sink2 = 0u32;
3688        for i in 0..10_000 {
3689            _sink2 = _sink2.wrapping_add(tracker.offset_of_item((i * 10) % n));
3690        }
3691        let offset_time = start.elapsed();
3692
3693        eprintln!("=== VariableHeightsFenwick Performance (n={n}) ===");
3694        eprintln!("10k find_item_at_offset: {:?}", find_time);
3695        eprintln!("10k offset_of_item:      {:?}", offset_time);
3696
3697        // Both should be under 50ms for 10k operations
3698        assert!(
3699            find_time < std::time::Duration::from_millis(50),
3700            "find_item_at_offset too slow: {:?}",
3701            find_time
3702        );
3703        assert!(
3704            offset_time < std::time::Duration::from_millis(50),
3705            "offset_of_item too slow: {:?}",
3706            offset_time
3707        );
3708    }
3709
3710    #[test]
3711    fn test_variable_heights_fenwick_scales_logarithmically() {
3712        use std::time::Instant;
3713
3714        // Small dataset
3715        let small_n = 1_000;
3716        let small_heights: Vec<u16> = (0..small_n).map(|i| (i % 5 + 1) as u16).collect();
3717        let small_tracker = VariableHeightsFenwick::from_heights(&small_heights, 1);
3718
3719        // Large dataset
3720        let large_n = 100_000;
3721        let large_heights: Vec<u16> = (0..large_n).map(|i| (i % 5 + 1) as u16).collect();
3722        let large_tracker = VariableHeightsFenwick::from_heights(&large_heights, 1);
3723
3724        let iterations = 5_000;
3725
3726        // Time small
3727        let start = Instant::now();
3728        for i in 0..iterations {
3729            let _ = small_tracker.find_item_at_offset((i * 2) as u32);
3730        }
3731        let small_time = start.elapsed();
3732
3733        // Time large
3734        let start = Instant::now();
3735        for i in 0..iterations {
3736            let _ = large_tracker.find_item_at_offset((i * 200) as u32);
3737        }
3738        let large_time = start.elapsed();
3739
3740        // Large should be within 10x of small (O(log n) vs O(n) would be 100x).
3741        // Use a generous bound to avoid flakiness on loaded CI workers.
3742        assert!(
3743            large_time < small_time * 10,
3744            "Not O(log n): small={:?}, large={:?}",
3745            small_time,
3746            large_time
3747        );
3748    }
3749
3750    // ========================================================================
3751    // Edge-case tests (bd-2f15w)
3752    // ========================================================================
3753
3754    // ── Virtualized: construction & empty state ─────────────────────────
3755
3756    #[test]
3757    fn new_zero_capacity() {
3758        let virt: Virtualized<i32> = Virtualized::new(0);
3759        assert_eq!(virt.len(), 0);
3760        assert!(virt.is_empty());
3761        assert_eq!(virt.scroll_offset(), 0);
3762        assert_eq!(virt.visible_count(), 0);
3763        assert!(!virt.follow_mode());
3764    }
3765
3766    #[test]
3767    fn external_zero_len_zero_cache() {
3768        let virt: Virtualized<i32> = Virtualized::external(0, 0);
3769        assert_eq!(virt.len(), 0);
3770        assert!(virt.is_empty());
3771    }
3772
3773    #[test]
3774    fn external_storage_returns_none_for_get() {
3775        let virt: Virtualized<i32> = Virtualized::external(100, 10);
3776        assert_eq!(virt.get(0), None);
3777        assert_eq!(virt.get(50), None);
3778    }
3779
3780    #[test]
3781    fn external_storage_returns_none_for_get_mut() {
3782        let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
3783        assert!(virt.get_mut(0).is_none());
3784    }
3785
3786    #[test]
3787    fn push_on_external_is_noop() {
3788        let mut virt: Virtualized<i32> = Virtualized::external(5, 10);
3789        virt.push(42);
3790        // Length unchanged because push only works on Owned
3791        assert_eq!(virt.len(), 5);
3792    }
3793
3794    #[test]
3795    fn iter_on_external_is_empty() {
3796        let virt: Virtualized<i32> = Virtualized::external(100, 10);
3797        assert_eq!(virt.iter().count(), 0);
3798    }
3799
3800    #[test]
3801    fn set_external_len_on_owned_is_noop() {
3802        let mut virt: Virtualized<i32> = Virtualized::new(100);
3803        virt.push(1);
3804        virt.set_external_len(999);
3805        assert_eq!(virt.len(), 1); // unchanged
3806    }
3807
3808    // ── Virtualized: visible_range edge cases ───────────────────────────
3809
3810    #[test]
3811    fn visible_range_zero_viewport() {
3812        let mut virt: Virtualized<i32> = Virtualized::new(100);
3813        virt.push(1);
3814        let range = virt.visible_range(0);
3815        assert_eq!(range, 0..0);
3816        assert_eq!(virt.visible_count(), 0);
3817    }
3818
3819    #[test]
3820    fn visible_range_empty_container() {
3821        let virt: Virtualized<i32> = Virtualized::new(100);
3822        let range = virt.visible_range(24);
3823        assert_eq!(range, 0..0);
3824    }
3825
3826    #[test]
3827    fn visible_range_fixed_height_zero() {
3828        // Fixed(0) should not divide by zero; falls through to viewport_height items
3829        let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(0);
3830        for i in 0..10 {
3831            virt.push(i);
3832        }
3833        let range = virt.visible_range(5);
3834        // ItemHeight::Fixed(0) → viewport_height as usize = 5
3835        assert_eq!(range, 0..5);
3836    }
3837
3838    #[test]
3839    fn visible_range_fewer_items_than_viewport() {
3840        let mut virt: Virtualized<i32> = Virtualized::new(100);
3841        for i in 0..3 {
3842            virt.push(i);
3843        }
3844        let range = virt.visible_range(24);
3845        // Only 3 items, viewport fits 24
3846        assert_eq!(range, 0..3);
3847    }
3848
3849    #[test]
3850    fn visible_range_single_item() {
3851        let mut virt: Virtualized<i32> = Virtualized::new(100);
3852        virt.push(42);
3853        let range = virt.visible_range(1);
3854        assert_eq!(range, 0..1);
3855    }
3856
3857    // ── Virtualized: render_range edge cases ────────────────────────────
3858
3859    #[test]
3860    fn render_range_at_start_clamps_overscan() {
3861        let mut virt: Virtualized<i32> =
3862            Virtualized::new(100).with_fixed_height(1).with_overscan(5);
3863        for i in 0..20 {
3864            virt.push(i);
3865        }
3866        // At scroll_offset=0, start.saturating_sub(5) = 0
3867        let range = virt.render_range(10);
3868        assert_eq!(range.start, 0);
3869    }
3870
3871    #[test]
3872    fn render_range_at_end_clamps_overscan() {
3873        let mut virt: Virtualized<i32> =
3874            Virtualized::new(100).with_fixed_height(1).with_overscan(5);
3875        for i in 0..20 {
3876            virt.push(i);
3877        }
3878        virt.set_visible_count(10);
3879        virt.scroll_to(10); // offset=10, visible 10..20
3880        let range = virt.render_range(10);
3881        // end = min(20 + 5, 20) = 20
3882        assert_eq!(range.end, 20);
3883    }
3884
3885    #[test]
3886    fn render_range_zero_overscan() {
3887        let mut virt: Virtualized<i32> =
3888            Virtualized::new(100).with_fixed_height(1).with_overscan(0);
3889        for i in 0..20 {
3890            virt.push(i);
3891        }
3892        virt.set_visible_count(10);
3893        virt.scroll_to(5);
3894        let range = virt.render_range(10);
3895        // No overscan: render_range == visible_range
3896        let visible = virt.visible_range(10);
3897        assert_eq!(range, visible);
3898    }
3899
3900    // ── Virtualized: scroll edge cases ──────────────────────────────────
3901
3902    #[test]
3903    fn scroll_on_empty_is_noop() {
3904        let mut virt: Virtualized<i32> = Virtualized::new(100);
3905        virt.scroll(10);
3906        assert_eq!(virt.scroll_offset(), 0);
3907    }
3908
3909    #[test]
3910    fn scroll_delta_zero_does_not_disable_follow() {
3911        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
3912        virt.push(1);
3913        virt.scroll(0);
3914        // delta=0 doesn't disable follow_mode
3915        assert!(virt.follow_mode());
3916    }
3917
3918    #[test]
3919    fn scroll_negative_beyond_start() {
3920        let mut virt: Virtualized<i32> = Virtualized::new(100);
3921        for i in 0..10 {
3922            virt.push(i);
3923        }
3924        virt.scroll(-1);
3925        assert_eq!(virt.scroll_offset(), 0);
3926    }
3927
3928    #[test]
3929    fn scroll_to_on_empty() {
3930        let mut virt: Virtualized<i32> = Virtualized::new(100);
3931        // scroll_to on empty: idx.min(0.saturating_sub(1)) = idx.min(0) = 0
3932        virt.scroll_to(100);
3933        assert_eq!(virt.scroll_offset(), 0);
3934    }
3935
3936    #[test]
3937    fn scroll_to_top_already_at_top() {
3938        let mut virt: Virtualized<i32> = Virtualized::new(100);
3939        virt.push(1);
3940        virt.scroll_to_top();
3941        assert_eq!(virt.scroll_offset(), 0);
3942    }
3943
3944    #[test]
3945    fn scroll_to_bottom_fewer_items_than_visible() {
3946        let mut virt: Virtualized<i32> = Virtualized::new(100);
3947        virt.set_visible_count(10);
3948        for i in 0..3 {
3949            virt.push(i);
3950        }
3951        virt.scroll_to_bottom();
3952        // len (3) <= visible_count (10), so offset = 0
3953        assert_eq!(virt.scroll_offset(), 0);
3954    }
3955
3956    #[test]
3957    fn scroll_to_bottom_visible_count_zero() {
3958        let mut virt: Virtualized<i32> = Virtualized::new(100);
3959        for i in 0..20 {
3960            virt.push(i);
3961        }
3962        // visible_count=0 (default), scroll_to_bottom stores a sentinel internally.
3963        virt.scroll_to_bottom();
3964        // Internal field stores MAX sentinel…
3965        assert_eq!(virt.scroll_offset, usize::MAX);
3966        // …but public API clamps to last valid index.
3967        assert_eq!(virt.scroll_offset(), 19);
3968    }
3969
3970    // ── Virtualized: page navigation edge cases ─────────────────────────
3971
3972    #[test]
3973    fn page_up_visible_count_zero_is_noop() {
3974        let mut virt: Virtualized<i32> = Virtualized::new(100);
3975        for i in 0..20 {
3976            virt.push(i);
3977        }
3978        virt.scroll_to(10);
3979        // visible_count=0, page_up is no-op
3980        virt.page_up();
3981        assert_eq!(virt.scroll_offset(), 10);
3982    }
3983
3984    #[test]
3985    fn page_down_visible_count_zero_is_noop() {
3986        let mut virt: Virtualized<i32> = Virtualized::new(100);
3987        for i in 0..20 {
3988            virt.push(i);
3989        }
3990        // visible_count=0, page_down is no-op
3991        virt.page_down();
3992        assert_eq!(virt.scroll_offset(), 0);
3993    }
3994
3995    // ── Virtualized: is_at_bottom edge cases ────────────────────────────
3996
3997    #[test]
3998    fn is_at_bottom_fewer_items_than_visible() {
3999        let mut virt: Virtualized<i32> = Virtualized::new(100);
4000        virt.set_visible_count(10);
4001        for i in 0..3 {
4002            virt.push(i);
4003        }
4004        assert!(virt.is_at_bottom());
4005    }
4006
4007    #[test]
4008    fn is_at_bottom_empty() {
4009        let virt: Virtualized<i32> = Virtualized::new(100);
4010        // len=0 <= visible_count=0, so true
4011        assert!(virt.is_at_bottom());
4012    }
4013
4014    // ── Virtualized: trim_front edge cases ──────────────────────────────
4015
4016    #[test]
4017    fn trim_front_under_max_returns_zero() {
4018        let mut virt: Virtualized<i32> = Virtualized::new(100);
4019        for i in 0..5 {
4020            virt.push(i);
4021        }
4022        let removed = virt.trim_front(10);
4023        assert_eq!(removed, 0);
4024        assert_eq!(virt.len(), 5);
4025    }
4026
4027    #[test]
4028    fn trim_front_adjusts_scroll_offset() {
4029        let mut virt: Virtualized<i32> = Virtualized::new(100);
4030        for i in 0..20 {
4031            virt.push(i);
4032        }
4033        virt.scroll_to(10);
4034        let removed = virt.trim_front(15);
4035        assert_eq!(removed, 5);
4036        assert_eq!(virt.len(), 15);
4037        // scroll_offset adjusted: 10 - 5 = 5
4038        assert_eq!(virt.scroll_offset(), 5);
4039    }
4040
4041    #[test]
4042    fn trim_front_scroll_offset_saturates_to_zero() {
4043        let mut virt: Virtualized<i32> = Virtualized::new(100);
4044        for i in 0..20 {
4045            virt.push(i);
4046        }
4047        virt.scroll_to(2);
4048        let removed = virt.trim_front(10);
4049        assert_eq!(removed, 10);
4050        // scroll_offset 2 - 10 saturates to 0
4051        assert_eq!(virt.scroll_offset(), 0);
4052    }
4053
4054    #[test]
4055    fn trim_front_on_external_returns_zero() {
4056        let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
4057        let removed = virt.trim_front(5);
4058        assert_eq!(removed, 0);
4059    }
4060
4061    #[test]
4062    fn scroll_to_bottom_sets_sentinel_for_lazy_clamping() {
4063        let mut virt: Virtualized<i32> = Virtualized::new(100);
4064        for i in 0..20 {
4065            virt.push(i);
4066        }
4067
4068        // Before rendering, visible_count is 0.
4069        // scroll_to_bottom should set MAX instead of 0.
4070        virt.scroll_to_bottom();
4071        assert_eq!(virt.scroll_offset, usize::MAX);
4072
4073        // Render (simulate by calling visible_range with height 10)
4074        // Should clamp start to 20 - 10 = 10.
4075        let range = virt.visible_range(10);
4076        assert_eq!(range, 10..20);
4077        assert_eq!(virt.visible_count(), 10);
4078    }
4079
4080    // ── Virtualized: clear edge cases ───────────────────────────────────
4081
4082    #[test]
4083    fn clear_on_external_resets_scroll() {
4084        let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
4085        virt.scroll_to(50);
4086        virt.clear();
4087        assert_eq!(virt.scroll_offset(), 0);
4088        // External len unchanged since clear only clears Owned
4089        assert_eq!(virt.len(), 100);
4090    }
4091
4092    // ── Virtualized: momentum scrolling edge cases ──────────────────────
4093
4094    #[test]
4095    fn tick_zero_velocity_is_noop() {
4096        let mut virt: Virtualized<i32> = Virtualized::new(100);
4097        for i in 0..20 {
4098            virt.push(i);
4099        }
4100        virt.tick(Duration::from_millis(100));
4101        assert_eq!(virt.scroll_offset(), 0);
4102    }
4103
4104    #[test]
4105    fn tick_below_threshold_stops_momentum() {
4106        let mut virt: Virtualized<i32> = Virtualized::new(100);
4107        for i in 0..20 {
4108            virt.push(i);
4109        }
4110        virt.fling(0.05); // below 0.1 threshold
4111        virt.tick(Duration::from_millis(100));
4112        // velocity <= 0.1, so it's zeroed out
4113        assert_eq!(virt.scroll_offset(), 0);
4114    }
4115
4116    #[test]
4117    fn tick_zero_duration_no_scroll() {
4118        let mut virt: Virtualized<i32> = Virtualized::new(100);
4119        for i in 0..50 {
4120            virt.push(i);
4121        }
4122        virt.fling(100.0);
4123        virt.tick(Duration::ZERO);
4124        // delta = (100.0 * 0.0) as i32 = 0, no scroll
4125        assert_eq!(virt.scroll_offset(), 0);
4126    }
4127
4128    #[test]
4129    fn fling_negative_scrolls_up() {
4130        let mut virt: Virtualized<i32> = Virtualized::new(100);
4131        for i in 0..50 {
4132            virt.push(i);
4133        }
4134        virt.scroll(20);
4135        let before = virt.scroll_offset();
4136        virt.fling(-50.0);
4137        virt.tick(Duration::from_millis(100));
4138        assert!(virt.scroll_offset() < before);
4139    }
4140
4141    // ── Virtualized: follow mode edge cases ─────────────────────────────
4142
4143    #[test]
4144    fn follow_mode_auto_scrolls_on_push() {
4145        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
4146        virt.set_visible_count(5);
4147        for i in 0..20 {
4148            virt.push(i);
4149        }
4150        // With follow mode, should be at bottom
4151        assert!(virt.is_at_bottom());
4152        assert_eq!(virt.scroll_offset(), 15); // 20 - 5
4153    }
4154
4155    #[test]
4156    fn set_follow_false_does_not_scroll() {
4157        let mut virt: Virtualized<i32> = Virtualized::new(100);
4158        virt.set_visible_count(5);
4159        for i in 0..20 {
4160            virt.push(i);
4161        }
4162        virt.scroll_to(5);
4163        virt.set_follow(false);
4164        assert_eq!(virt.scroll_offset(), 5); // unchanged
4165    }
4166
4167    #[test]
4168    fn scroll_to_start_disables_follow() {
4169        let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
4170        virt.set_visible_count(5);
4171        for i in 0..20 {
4172            virt.push(i);
4173        }
4174        virt.scroll_to_start();
4175        assert!(!virt.follow_mode());
4176        assert_eq!(virt.scroll_offset(), 0);
4177    }
4178
4179    #[test]
4180    fn scroll_to_end_enables_follow() {
4181        let mut virt: Virtualized<i32> = Virtualized::new(100);
4182        virt.set_visible_count(5);
4183        for i in 0..20 {
4184            virt.push(i);
4185        }
4186        assert!(!virt.follow_mode());
4187        virt.scroll_to_end();
4188        assert!(virt.follow_mode());
4189        assert!(virt.is_at_bottom());
4190    }
4191
4192    #[test]
4193    fn external_follow_mode_scrolls_on_set_external_len() {
4194        let mut virt: Virtualized<i32> = Virtualized::external(10, 100).with_follow(true);
4195        virt.set_visible_count(5);
4196        virt.set_external_len(20);
4197        assert_eq!(virt.len(), 20);
4198        assert!(virt.is_at_bottom());
4199    }
4200
4201    // ── Virtualized: builder chain ──────────────────────────────────────
4202
4203    #[test]
4204    fn builder_chain_all_options() {
4205        let virt: Virtualized<i32> = Virtualized::new(100)
4206            .with_fixed_height(3)
4207            .with_overscan(5)
4208            .with_follow(true);
4209        assert!(virt.follow_mode());
4210        // Verify visible_range uses height=3
4211        // (no items, so empty range regardless)
4212        let range = virt.visible_range(9);
4213        assert_eq!(range, 0..0);
4214    }
4215
4216    // ── HeightCache edge cases ──────────────────────────────────────────
4217
4218    #[test]
4219    fn height_cache_default() {
4220        let cache = HeightCache::default();
4221        assert_eq!(cache.get(0), 1); // default_height=1
4222        assert_eq!(cache.capacity, 1000);
4223    }
4224
4225    #[test]
4226    fn height_cache_get_before_base_offset() {
4227        let mut cache = HeightCache::new(5, 100);
4228        // Set something to push base_offset forward
4229        cache.set(200, 10); // This resets window since 200 > capacity
4230        // Index 0 < base_offset, returns default
4231        assert_eq!(cache.get(0), 5);
4232    }
4233
4234    #[test]
4235    fn height_cache_set_before_base_offset_ignored() {
4236        let mut cache = HeightCache::new(5, 100);
4237        cache.set(200, 10);
4238        let base = cache.base_offset;
4239        cache.set(0, 99); // before base_offset, should be ignored
4240        assert_eq!(cache.get(0), 5); // still default
4241        assert_eq!(cache.base_offset, base); // unchanged
4242    }
4243
4244    #[test]
4245    fn height_cache_capacity_zero_ignores_all_sets() {
4246        let mut cache = HeightCache::new(3, 0);
4247        cache.set(0, 10);
4248        cache.set(5, 20);
4249        // Everything returns default since capacity=0
4250        assert_eq!(cache.get(0), 3);
4251        assert_eq!(cache.get(5), 3);
4252    }
4253
4254    #[test]
4255    fn height_cache_clear_resets_base() {
4256        let mut cache = HeightCache::new(1, 100);
4257        cache.set(50, 10);
4258        cache.clear();
4259        assert_eq!(cache.base_offset, 0);
4260        assert_eq!(cache.get(50), 1); // back to default
4261    }
4262
4263    #[test]
4264    fn height_cache_eviction_trims_oldest() {
4265        let mut cache = HeightCache::new(1, 4);
4266        // Set indices 0..6 to fill and trigger eviction
4267        for i in 0..6 {
4268            cache.set(i, (i + 10) as u16);
4269        }
4270        // Cache capacity=4, so indices 0-1 should be evicted
4271        assert!(cache.cache.len() <= cache.capacity);
4272        // Recent indices should be accessible
4273        assert_eq!(cache.get(5), 15);
4274        assert_eq!(cache.get(4), 14);
4275        assert_eq!(cache.get(3), 13);
4276        assert_eq!(cache.get(2), 12);
4277        // Old indices return default
4278        assert_eq!(cache.get(1), 1);
4279        assert_eq!(cache.get(0), 1);
4280    }
4281
4282    // ── VariableHeightsFenwick edge cases ───────────────────────────────
4283
4284    #[test]
4285    fn fenwick_default_is_empty() {
4286        let tracker = VariableHeightsFenwick::default();
4287        assert!(tracker.is_empty());
4288        assert_eq!(tracker.len(), 0);
4289        assert_eq!(tracker.total_height(), 0);
4290        assert_eq!(tracker.default_height(), 1);
4291    }
4292
4293    #[test]
4294    fn fenwick_get_beyond_len_returns_default() {
4295        let tracker = VariableHeightsFenwick::new(3, 5);
4296        assert_eq!(tracker.get(5), 3); // beyond len
4297        assert_eq!(tracker.get(100), 3);
4298    }
4299
4300    #[test]
4301    fn fenwick_set_beyond_len_resizes() {
4302        let mut tracker = VariableHeightsFenwick::new(2, 3);
4303        assert_eq!(tracker.len(), 3);
4304        tracker.set(10, 7);
4305        assert!(tracker.len() > 10);
4306        assert_eq!(tracker.get(10), 7);
4307    }
4308
4309    #[test]
4310    fn fenwick_offset_of_item_zero_always_zero() {
4311        let tracker = VariableHeightsFenwick::new(5, 10);
4312        assert_eq!(tracker.offset_of_item(0), 0);
4313
4314        let empty = VariableHeightsFenwick::new(5, 0);
4315        assert_eq!(empty.offset_of_item(0), 0);
4316    }
4317
4318    #[test]
4319    fn fenwick_find_item_at_offset_empty() {
4320        let tracker = VariableHeightsFenwick::new(1, 0);
4321        assert_eq!(tracker.find_item_at_offset(0), 0);
4322        assert_eq!(tracker.find_item_at_offset(100), 0);
4323    }
4324
4325    #[test]
4326    fn fenwick_visible_count_zero_viewport() {
4327        let tracker = VariableHeightsFenwick::new(2, 10);
4328        assert_eq!(tracker.visible_count(0, 0), 0);
4329    }
4330
4331    #[test]
4332    fn fenwick_visible_count_start_beyond_len() {
4333        let tracker = VariableHeightsFenwick::new(2, 5);
4334        // start_idx clamped to len
4335        let count = tracker.visible_count(100, 10);
4336        // start=5 (clamped), offset=total, no items visible
4337        assert_eq!(count, 0);
4338    }
4339
4340    #[test]
4341    fn fenwick_clear_then_operations() {
4342        let mut tracker = VariableHeightsFenwick::new(3, 5);
4343        assert_eq!(tracker.total_height(), 15);
4344        tracker.clear();
4345        assert_eq!(tracker.len(), 0);
4346        assert_eq!(tracker.total_height(), 0);
4347        assert_eq!(tracker.find_item_at_offset(0), 0);
4348    }
4349
4350    #[test]
4351    fn fenwick_rebuild_replaces_data() {
4352        let mut tracker = VariableHeightsFenwick::new(1, 10);
4353        assert_eq!(tracker.total_height(), 10);
4354        tracker.rebuild(&[5, 3, 2]);
4355        assert_eq!(tracker.len(), 3);
4356        assert_eq!(tracker.total_height(), 10);
4357        assert_eq!(tracker.get(0), 5);
4358        assert_eq!(tracker.get(1), 3);
4359        assert_eq!(tracker.get(2), 2);
4360    }
4361
4362    #[test]
4363    fn fenwick_resize_same_size_is_noop() {
4364        let mut tracker = VariableHeightsFenwick::new(2, 5);
4365        tracker.set(2, 10);
4366        tracker.resize(5);
4367        // Item 2 still has custom height
4368        assert_eq!(tracker.get(2), 10);
4369        assert_eq!(tracker.len(), 5);
4370    }
4371
4372    // ── VirtualizedListState edge cases ─────────────────────────────────
4373
4374    #[test]
4375    fn list_state_default_matches_new() {
4376        let d = VirtualizedListState::default();
4377        let n = VirtualizedListState::new();
4378        assert_eq!(d.selected, n.selected);
4379        assert_eq!(d.scroll_offset(), n.scroll_offset());
4380        assert_eq!(d.visible_count(), n.visible_count());
4381        assert_eq!(d.follow_mode(), n.follow_mode());
4382    }
4383
4384    #[test]
4385    fn list_state_select_next_on_empty() {
4386        let mut state = VirtualizedListState::new();
4387        state.select_next(0);
4388        assert_eq!(state.selected, None);
4389    }
4390
4391    #[test]
4392    fn list_state_select_previous_on_empty() {
4393        let mut state = VirtualizedListState::new();
4394        state.select_previous(0);
4395        assert_eq!(state.selected, None);
4396    }
4397
4398    #[test]
4399    fn list_state_select_previous_from_none() {
4400        let mut state = VirtualizedListState::new();
4401        state.select_previous(10);
4402        assert_eq!(state.selected, Some(0));
4403    }
4404
4405    #[test]
4406    fn list_state_select_next_from_none() {
4407        let mut state = VirtualizedListState::new();
4408        state.select_next(10);
4409        assert_eq!(state.selected, Some(0));
4410    }
4411
4412    #[test]
4413    fn list_state_scroll_zero_items() {
4414        let mut state = VirtualizedListState::new();
4415        state.scroll(10, 0);
4416        assert_eq!(state.scroll_offset(), 0);
4417    }
4418
4419    #[test]
4420    fn list_state_scroll_to_clamps() {
4421        let mut state = VirtualizedListState::new();
4422        state.scroll_to(100, 10);
4423        assert_eq!(state.scroll_offset(), 9);
4424    }
4425
4426    #[test]
4427    fn list_state_scroll_to_bottom_zero_items() {
4428        let mut state = VirtualizedListState::new();
4429        state.scroll_to_bottom(0);
4430        assert_eq!(state.scroll_offset(), 0);
4431    }
4432
4433    #[test]
4434    fn list_state_is_at_bottom_zero_items() {
4435        let state = VirtualizedListState::new();
4436        assert!(state.is_at_bottom(0));
4437    }
4438
4439    #[test]
4440    fn list_state_page_up_visible_count_zero() {
4441        let mut state = VirtualizedListState::new();
4442        state.scroll_offset = 5;
4443        state.page_up(20);
4444        // visible_count=0, no-op
4445        assert_eq!(state.scroll_offset(), 5);
4446    }
4447
4448    #[test]
4449    fn list_state_page_down_visible_count_zero() {
4450        let mut state = VirtualizedListState::new();
4451        state.page_down(20);
4452        // visible_count=0, no-op
4453        assert_eq!(state.scroll_offset(), 0);
4454    }
4455
4456    #[test]
4457    fn list_state_set_follow_false_no_scroll() {
4458        let mut state = VirtualizedListState::new();
4459        state.scroll_offset = 5;
4460        state.set_follow(false, 20);
4461        assert_eq!(state.scroll_offset(), 5); // unchanged
4462        assert!(!state.follow_mode());
4463    }
4464
4465    #[test]
4466    fn list_state_persistence_id() {
4467        let state = VirtualizedListState::new().with_persistence_id("my-list");
4468        assert_eq!(state.persistence_id(), Some("my-list"));
4469    }
4470
4471    #[test]
4472    fn list_state_persistence_id_none() {
4473        let state = VirtualizedListState::new();
4474        assert_eq!(state.persistence_id(), None);
4475    }
4476
4477    #[test]
4478    fn list_state_momentum_tick_zero_items() {
4479        let mut state = VirtualizedListState::new();
4480        state.fling(50.0);
4481        state.tick(Duration::from_millis(100), 0);
4482        // total_items=0, scroll is no-op
4483        assert_eq!(state.scroll_offset(), 0);
4484    }
4485
4486    // ── VirtualizedListPersistState edge cases ──────────────────────────
4487
4488    #[test]
4489    fn persist_state_default() {
4490        let ps = VirtualizedListPersistState::default();
4491        assert_eq!(ps.selected, None);
4492        assert_eq!(ps.scroll_offset, 0);
4493        assert!(!ps.follow_mode);
4494    }
4495
4496    #[test]
4497    fn persist_state_eq() {
4498        let a = VirtualizedListPersistState {
4499            selected: Some(5),
4500            scroll_offset: 10,
4501            follow_mode: true,
4502        };
4503        let b = a.clone();
4504        assert_eq!(a, b);
4505    }
4506
4507    // ── Stateful trait impl edge cases ──────────────────────────────────
4508
4509    #[test]
4510    fn stateful_state_key_with_persistence_id() {
4511        use crate::stateful::Stateful;
4512        let state = VirtualizedListState::new().with_persistence_id("logs");
4513        let key = state.state_key().expect("named list has a key");
4514        assert_eq!(key.widget_type, "VirtualizedList");
4515        assert_eq!(key.instance_id, "logs");
4516    }
4517
4518    #[test]
4519    fn stateful_state_without_id_is_not_persisted() {
4520        use crate::stateful::Stateful;
4521        assert!(VirtualizedListState::new().state_key().is_none());
4522    }
4523
4524    #[test]
4525    fn stateful_save_restore_roundtrip() {
4526        use crate::stateful::Stateful;
4527        let mut state = VirtualizedListState::new();
4528        state.selected = Some(7);
4529        state.scroll_offset = 15;
4530        state.follow_mode = true;
4531        state.scroll_velocity = 42.0; // transient — not persisted
4532
4533        let saved = state.save_state();
4534        assert_eq!(saved.selected, Some(7));
4535        assert_eq!(saved.scroll_offset, 15);
4536        assert!(saved.follow_mode);
4537
4538        let mut restored = VirtualizedListState::new();
4539        restored.scroll_velocity = 99.0;
4540        restored.restore_state(saved);
4541        assert_eq!(restored.selected, Some(7));
4542        assert_eq!(restored.scroll_offset, 15);
4543        assert!(restored.follow_mode);
4544        // velocity reset to 0 on restore
4545        assert_eq!(restored.scroll_velocity, 0.0);
4546    }
4547
4548    // ── VirtualizedList widget edge cases ───────────────────────────────
4549
4550    #[test]
4551    fn virtualized_list_builder() {
4552        let items: Vec<String> = vec!["a".into()];
4553        let list = VirtualizedList::new(&items)
4554            .style(Style::default())
4555            .highlight_style(Style::default())
4556            .show_scrollbar(false)
4557            .fixed_height(3);
4558        assert_eq!(list.height_mode(), ListHeightMode::Fixed(3));
4559        assert!(!list.show_scrollbar);
4560        assert_eq!(
4561            VirtualizedList::new(&items)
4562                .variable_heights()
4563                .height_mode(),
4564            ListHeightMode::Variable
4565        );
4566    }
4567
4568    /// `with_variable_heights` selects the Fenwick tracker sized to the
4569    /// list: offsets are exact before any measurement, offset/index queries
4570    /// round-trip, scrolling to the end computes the last screenful, and a
4571    /// measurement shifts every later offset.
4572    #[test]
4573    fn with_variable_heights_defaults_to_fenwick_and_scrolls_in_log_time() {
4574        let mut v: Virtualized<usize> = Virtualized::external(10_000, 0).with_variable_heights(3);
4575        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4576            panic!("expected the Fenwick tracker, got {:?}", v.item_height());
4577        };
4578        assert_eq!(tracker.len(), 10_000);
4579        assert_eq!(tracker.offset_of_item(9_999), 3 * 9_999);
4580        for k in 0..100u32 {
4581            let offset = k * 297;
4582            let idx = tracker.find_item_at_offset(offset);
4583            let start = tracker.offset_of_item(idx);
4584            assert!(
4585                start <= offset && offset < start + u32::from(tracker.get(idx)),
4586                "offset {offset} must land inside item {idx} [{start}, +{})",
4587                tracker.get(idx)
4588            );
4589        }
4590
4591        v.scroll_to(9_999);
4592        let range = v.visible_range(24);
4593        assert_eq!(range.end, 10_000);
4594        assert_eq!(range.end - range.start, 8, "24 rows / 3 per item");
4595
4596        v.observe_height(5, 7);
4597        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4598            unreachable!()
4599        };
4600        assert_eq!(tracker.offset_of_item(6), 3 * 6 + 4);
4601        assert!(tracker.is_measured(5));
4602        assert_eq!(v.unmeasured_item_height(), 3);
4603    }
4604
4605    /// The tracker follows the item count through push, trim_front and
4606    /// clear, keeping measured heights aligned with their items.
4607    #[test]
4608    fn variable_height_tracker_follows_owned_storage() {
4609        let mut v: Virtualized<String> = Virtualized::new(8).with_variable_heights(2);
4610        for i in 0..5 {
4611            v.push(format!("row {i}"));
4612        }
4613        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4614            unreachable!()
4615        };
4616        assert_eq!(tracker.len(), 5);
4617        assert_eq!(tracker.total_height(), 10);
4618
4619        v.observe_height(0, 5);
4620        v.observe_height(3, 4);
4621        assert_eq!(v.trim_front(3), 2);
4622        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4623            unreachable!()
4624        };
4625        assert_eq!(tracker.len(), 3);
4626        // Old item 3 (height 4) is now item 1; the others are unmeasured (2).
4627        assert!(!tracker.is_measured(0));
4628        assert!(tracker.is_measured(1));
4629        assert_eq!(tracker.get(1), 4);
4630        assert_eq!(tracker.total_height(), 2 + 4 + 2);
4631
4632        v.clear();
4633        let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
4634            unreachable!()
4635        };
4636        assert_eq!(tracker.len(), 0);
4637        assert_eq!(tracker.total_height(), 0);
4638    }
4639
4640    /// The legacy cache follows the same trims. Its indices are absolute, so
4641    /// without a shift a `trim_front` hands every measurement to the item
4642    /// three places later — the sliding window this strategy exists for.
4643    #[test]
4644    fn legacy_height_cache_follows_owned_storage() {
4645        let mut v: Virtualized<String> =
4646            Virtualized::new(8).with_item_height(ItemHeight::Variable(HeightCache::new(1, 64)));
4647        for i in 0..6 {
4648            v.push(format!("row {i}"));
4649        }
4650        v.observe_height(0, 9);
4651        v.observe_height(4, 4);
4652        assert_eq!(v.trim_front(3), 3);
4653
4654        let ItemHeight::Variable(cache) = v.item_height() else {
4655            unreachable!()
4656        };
4657        // Old item 0 went with the trim; old item 4 (height 4) is now item 1.
4658        assert_eq!(cache.get(0), 1);
4659        assert_eq!(cache.get(1), 4);
4660        // So the first item no longer claims the nine lines of a trimmed one.
4661        assert_eq!(v.visible_range(4), 0..2);
4662
4663        v.clear();
4664        for i in 0..3 {
4665            v.push(format!("fresh {i}"));
4666        }
4667        let ItemHeight::Variable(cache) = v.item_height() else {
4668            unreachable!()
4669        };
4670        assert_eq!(cache.get(0), 1);
4671        assert_eq!(cache.get(1), 1);
4672        assert_eq!(v.visible_range(4), 0..3);
4673    }
4674
4675    /// `drop_front` renumbers a window that starts past the trimmed prefix
4676    /// instead of discarding it.
4677    #[test]
4678    fn height_cache_drop_front_shifts_a_window_past_the_prefix() {
4679        let mut cache = HeightCache::new(1, 4);
4680        for idx in 10..14 {
4681            cache.set(idx, idx as u16);
4682        }
4683        cache.drop_front(10);
4684        for idx in 0..4 {
4685            assert_eq!(cache.get(idx), 10 + idx as u16);
4686        }
4687
4688        // A trim that reaches into the window drops only what it covers.
4689        cache.drop_front(2);
4690        assert_eq!(cache.get(0), 12);
4691        assert_eq!(cache.get(1), 13);
4692        assert_eq!(cache.get(2), 1);
4693
4694        // A trim past the end leaves nothing behind.
4695        cache.drop_front(9);
4696        assert_eq!(cache.get(0), 1);
4697    }
4698
4699    #[test]
4700    fn measure_updates_fenwick_and_predictor() {
4701        let mut list: Virtualized<String> = Virtualized::external(10, 0)
4702            .with_variable_heights(3)
4703            .with_height_prediction(PredictorConfig {
4704                default_height: 3,
4705                prior_mean: 3.0,
4706                prior_strength: 100.0,
4707                ..PredictorConfig::default()
4708            });
4709        let ItemHeight::VariableFenwick(before) = list.item_height() else {
4710            panic!("expected Fenwick heights");
4711        };
4712        let offset = before.offset_of_item(6);
4713        list.measure(5, 7);
4714        let ItemHeight::VariableFenwick(after) = list.item_height() else {
4715            panic!("expected Fenwick heights");
4716        };
4717        assert_eq!(after.offset_of_item(6), offset + 4);
4718        assert_eq!(list.predictor_stats().unwrap().measurements, 1);
4719        assert_eq!(list.predicted_height(0), 3);
4720    }
4721
4722    #[test]
4723    fn unmeasured_rows_use_predicted_mean() {
4724        let mut list: Virtualized<String> = Virtualized::external(100, 0)
4725            .with_variable_heights(1)
4726            .with_height_prediction(PredictorConfig::default());
4727        for idx in 0..20 {
4728            list.measure(idx, 4);
4729        }
4730        assert_eq!(list.predicted_height(0), 4);
4731        assert_eq!(list.predictor_stats().unwrap().measurements, 20);
4732        let ItemHeight::VariableFenwick(heights) = list.item_height() else {
4733            panic!("expected Fenwick heights");
4734        };
4735        assert!(!heights.is_measured(99));
4736        assert_eq!(heights.get(99), 4);
4737        assert_eq!(heights.total_height(), 400);
4738        assert_eq!(String::from("uncategorized").category(), 0);
4739    }
4740
4741    #[test]
4742    fn measured_bitset_tracks_word_boundaries_resize_and_rebuild() {
4743        let mut heights = VariableHeightsFenwick::new(2, 130);
4744        for idx in [0, 63, 64, 65, 127, 128, 129] {
4745            heights.set(idx, 3);
4746        }
4747        assert_eq!(heights.unmeasured_count(), 123);
4748        assert_eq!(heights.measured.len(), 3);
4749        heights.resize(65);
4750        assert_eq!(heights.unmeasured_count(), 62);
4751        heights.resize(130);
4752        for idx in 65..130 {
4753            assert!(!heights.is_measured(idx), "stale bit at {idx}");
4754            assert_eq!(heights.get(idx), 2);
4755        }
4756        heights.rebuild(&[4; 65]);
4757        assert_eq!(heights.unmeasured_count(), 0);
4758        assert!(heights.is_measured(64));
4759        assert!(!heights.is_measured(65));
4760        heights.resize(66);
4761        assert!(!heights.is_measured(65));
4762        heights.drop_front(64);
4763        assert!(heights.is_measured(0));
4764        assert!(!heights.is_measured(1));
4765        assert_eq!(heights.get(0), 4);
4766        assert_eq!(heights.get(1), 2);
4767        heights.clear();
4768        assert!(!heights.is_measured(0));
4769        assert_eq!(heights.unmeasured_count(), 0);
4770        assert!(heights.measured.is_empty());
4771    }
4772
4773    #[test]
4774    fn trimming_measured_rows_does_not_retrain_predictor() {
4775        let mut heights =
4776            VariableHeightsFenwick::new(1, 80).with_predictor(PredictorConfig::default());
4777        for idx in 0..70 {
4778            heights.set_in_category(idx, 5, 1);
4779        }
4780        let before = heights.predictor().unwrap().stats();
4781        heights.drop_front(65);
4782        assert_eq!(heights.predictor().unwrap().stats(), before);
4783        assert_eq!(heights.unmeasured_count(), 10);
4784        for idx in 0..5 {
4785            assert!(heights.is_measured(idx));
4786            assert_eq!(heights.get(idx), 5);
4787        }
4788    }
4789
4790    #[test]
4791    fn variable_list_trains_categories_once_per_measurement() {
4792        struct Row {
4793            height: u16,
4794            category: usize,
4795        }
4796        impl RenderItem for Row {
4797            fn render(&self, area: Rect, frame: &mut Frame, _: bool, _: u16) {
4798                for y in area.y..area.bottom() {
4799                    frame.buffer.set(area.x, y, Cell::from_char('x'));
4800                }
4801            }
4802
4803            fn height(&self) -> u16 {
4804                self.height
4805            }
4806
4807            fn category(&self) -> usize {
4808                self.category
4809            }
4810        }
4811        let mut items = [
4812            Row {
4813                height: 3,
4814                category: 1,
4815            },
4816            Row {
4817                height: 1,
4818                category: 0,
4819            },
4820        ];
4821        let mut state =
4822            VirtualizedListState::variable(2).with_predictor(PredictorConfig::default());
4823        let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
4824        let mut frame = Frame::new(10, 5, &mut pool);
4825        let area = Rect::new(0, 0, 10, 5);
4826        VirtualizedList::new(&items)
4827            .variable_heights()
4828            .render(area, &mut frame, &mut state);
4829        assert_eq!(state.predictor_stats().unwrap().measurements, 2);
4830        assert_eq!(state.predictor_stats().unwrap().categories, 2);
4831        let predictor = state.heights().unwrap().predictor().unwrap();
4832        assert_eq!(predictor.category_observations(1), 1);
4833        assert_eq!(predictor.category_observations(0), 1);
4834        assert_eq!(state.heights().unwrap().offset_of_item(1), 3);
4835        assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), Some('x'));
4836        assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some(' '));
4837        VirtualizedList::new(&items)
4838            .variable_heights()
4839            .render(area, &mut frame, &mut state);
4840        assert_eq!(state.predictor_stats().unwrap().measurements, 2);
4841        items[0].height = 4;
4842        VirtualizedList::new(&items)
4843            .variable_heights()
4844            .render(area, &mut frame, &mut state);
4845        assert_eq!(state.predictor_stats().unwrap().measurements, 3);
4846        assert_eq!(
4847            state
4848                .heights()
4849                .unwrap()
4850                .predictor()
4851                .unwrap()
4852                .category_observations(1),
4853            2
4854        );
4855
4856        VirtualizedList::new(&items[..0])
4857            .variable_heights()
4858            .render(area, &mut frame, &mut state);
4859        assert_eq!(state.visible_count(), 0);
4860        assert_eq!(state.scroll_offset(), 0);
4861        assert!(state.heights().unwrap().is_empty());
4862        assert_eq!(state.predictor_stats().unwrap().measurements, 3);
4863        VirtualizedList::new(&items)
4864            .variable_heights()
4865            .render(area, &mut frame, &mut state);
4866        assert_eq!(state.predictor_stats().unwrap().measurements, 5);
4867
4868        let mut owned = Virtualized::new(2)
4869            .with_variable_heights(2)
4870            .with_height_prediction(PredictorConfig::default());
4871        owned.push(Row {
4872            height: 4,
4873            category: 1,
4874        });
4875        owned.measure(0, 4);
4876        assert_eq!(owned.predictor_stats().unwrap().categories, 2);
4877        assert_eq!(owned.predictor_stats().unwrap().measurements, 1);
4878        assert!(owned.predicted_height(1) > owned.predicted_height(0));
4879    }
4880
4881    /// A variable-height `VirtualizedList` lays rows out by
4882    /// `RenderItem::height`, measures them into the state, keeps the
4883    /// selection visible and clamps to the last item-aligned screenful.
4884    #[test]
4885    fn virtualized_list_variable_heights_renders_by_item_height() {
4886        struct Tall(u16);
4887        impl RenderItem for Tall {
4888            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
4889                let glyph = char::from(b'0' + u8::try_from(self.0).unwrap_or(9));
4890                for row in 0..area.height {
4891                    frame
4892                        .buffer
4893                        .set(area.x, area.y + row, Cell::from_char(glyph));
4894                }
4895            }
4896            fn height(&self) -> u16 {
4897                self.0
4898            }
4899        }
4900        let column = |frame: &Frame| -> String {
4901            (0..frame.buffer.height())
4902                .map(|y| {
4903                    frame
4904                        .buffer
4905                        .get(0, y)
4906                        .and_then(|cell| cell.content.as_char())
4907                        .unwrap_or(' ')
4908                })
4909                .collect()
4910        };
4911
4912        let items = [Tall(1), Tall(2), Tall(3), Tall(1), Tall(2)];
4913        let list = VirtualizedList::new(&items)
4914            .variable_heights()
4915            .show_scrollbar(false);
4916        let mut state = VirtualizedListState::new();
4917        let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
4918
4919        let mut frame = Frame::new(4, 5, &mut pool);
4920        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4921        // item0 (1 row), item1 (2 rows), item2 (3 rows, cut to the 2 left).
4922        assert_eq!(column(&frame), "12233");
4923        assert_eq!(state.visible_count(), 3);
4924        let heights = state.heights().expect("tracker created by render");
4925        assert_eq!(heights.get(1), 2);
4926        assert!(heights.is_measured(2));
4927        // The last screenful is measured too, for the bottom clamp.
4928        assert!(heights.is_measured(4) && heights.is_measured(3));
4929        drop(frame);
4930
4931        // Selecting the last item scrolls so it is visible; the clamp keeps
4932        // the first visible row item-aligned (item3 at the top).
4933        state.select(Some(4));
4934        let mut frame = Frame::new(4, 5, &mut pool);
4935        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4936        assert_eq!(state.scroll_offset(), 3);
4937        assert_eq!(column(&frame), "122  ");
4938        assert_eq!(state.visible_count(), 2);
4939        let heights = state.heights().expect("tracker");
4940        assert_eq!(heights.total_height(), 9);
4941        assert_eq!(heights.offset_of_item(4), 7);
4942        drop(frame);
4943
4944        // A manual measurement moves later offsets.
4945        state.measure(0, 3);
4946        assert_eq!(state.heights().expect("tracker").offset_of_item(1), 3);
4947
4948        // With the scrollbar on, the thumb works in rows.
4949        let list = VirtualizedList::new(&items).variable_heights();
4950        let mut state = VirtualizedListState::new();
4951        let mut frame = Frame::new(4, 5, &mut pool);
4952        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4953        assert!(
4954            frame.buffer.get(3, 0).and_then(|c| c.content.as_char()) != Some('1'),
4955            "the last column belongs to the scrollbar"
4956        );
4957        assert_eq!(column(&frame), "12233");
4958    }
4959
4960    #[test]
4961    fn fenwick_large_list_renders_selection_and_scroll_beyond_u32() {
4962        #[derive(Clone, Copy)]
4963        struct Row(u16, char);
4964        impl RenderItem for Row {
4965            fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
4966                for y in area.y..area.bottom() {
4967                    frame.buffer.set(area.x, y, Cell::from_char(self.1));
4968                }
4969            }
4970
4971            fn height(&self) -> u16 {
4972                self.0
4973            }
4974        }
4975
4976        let mut items = vec![Row(u16::MAX, 'X'); 65_538];
4977        items.extend([Row(1, '.'); 9]);
4978        items.push(Row(1, 'Z'));
4979        let list = VirtualizedList::new(&items).variable_heights();
4980        let mut state = VirtualizedListState::new();
4981        let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
4982        {
4983            let mut frame = Frame::new(4, 5, &mut pool);
4984            StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4985            assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('X'));
4986        }
4987        // Populate off-screen measurements through the real list-state API.
4988        for (idx, row) in items.iter().enumerate() {
4989            state.measure(idx, row.height());
4990        }
4991        assert_eq!(state.heights().unwrap().total_height(), u32::MAX);
4992        state.select(Some(items.len() - 1));
4993        {
4994            let mut frame = Frame::new(4, 5, &mut pool);
4995            StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
4996            assert_eq!(state.scroll_offset(), items.len() - 5);
4997            assert_eq!(state.visible_count(), 5);
4998            let column: String = (0..5)
4999                .map(|y| frame.buffer.get(0, y).unwrap().content.as_char().unwrap())
5000                .collect();
5001            assert_eq!(column, "....Z");
5002            assert_ne!(frame.buffer.get(3, 4).unwrap().content.as_char(), Some('Z'));
5003        }
5004        state.select(None);
5005        state.scroll_to_top();
5006        {
5007            let mut frame = Frame::new(4, 5, &mut pool);
5008            StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5009            assert_eq!(state.scroll_offset(), 0);
5010            assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('X'));
5011        }
5012        state.scroll_to_bottom(items.len());
5013        let mut frame = Frame::new(4, 5, &mut pool);
5014        StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
5015        assert_eq!(state.scroll_offset(), items.len() - 5);
5016        assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('Z'));
5017    }
5018
5019    // ── VirtualizedStorage Debug/Clone ───────────────────────────────────
5020
5021    #[test]
5022    fn virtualized_storage_debug() {
5023        let storage: VirtualizedStorage<i32> = VirtualizedStorage::Owned(VecDeque::new());
5024        let dbg = format!("{:?}", storage);
5025        assert!(dbg.contains("Owned"));
5026
5027        let ext: VirtualizedStorage<i32> = VirtualizedStorage::External {
5028            len: 100,
5029            cache_capacity: 10,
5030        };
5031        let dbg = format!("{:?}", ext);
5032        assert!(dbg.contains("External"));
5033    }
5034
5035    #[test]
5036    fn test_virtualized_list_handle_mouse_drag_smooth() {
5037        use crate::scrollbar::SCROLLBAR_PART_THUMB;
5038        use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
5039        use ftui_render::frame::{HitId, HitRegion};
5040
5041        let mut state = VirtualizedListState::new();
5042        let scrollbar_hit_id = HitId::new(1);
5043        let total_items = 100;
5044        let viewport_height = 10;
5045        let fixed_height = 1;
5046
5047        // Simulate click on thumb.
5048        // Track length 10. Thumb size 1. Content 100.
5049        // Thumb at top (pos 0).
5050        // Click at track_pos 0 (top of thumb).
5051        // Hit data: [8: part] [28: len] [28: pos]
5052        let track_len = 10u64;
5053        let track_pos = 0u64;
5054        let hit_data = (SCROLLBAR_PART_THUMB << 56)
5055            | ((track_len & 0x0FFF_FFFF) << 28)
5056            | (track_pos & 0x0FFF_FFFF);
5057
5058        let down_event = MouseEvent::new(MouseEventKind::Down(MouseButton::Left), 0, 0);
5059        let hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, hit_data));
5060
5061        state.handle_mouse(
5062            &down_event,
5063            hit,
5064            scrollbar_hit_id,
5065            total_items,
5066            viewport_height,
5067            fixed_height,
5068        );
5069
5070        assert!(
5071            state.scrollbar_drag_anchor.is_some(),
5072            "Drag anchor should be set on down"
5073        );
5074        assert_eq!(
5075            state.scrollbar_drag_anchor.unwrap(),
5076            0,
5077            "Anchor should be 0 (clicked top of thumb)"
5078        );
5079
5080        // Drag down by 1 cell.
5081        // track_pos = 1. anchor = 0. target thumb top = 1.
5082        // available = 9. max_pos = 90.
5083        // pos = (1 * 90) / 9 = 10.
5084        let drag_pos = 1u64;
5085        let drag_data = (SCROLLBAR_PART_THUMB << 56)
5086            | ((track_len & 0x0FFF_FFFF) << 28)
5087            | (drag_pos & 0x0FFF_FFFF);
5088        let drag_event = MouseEvent::new(MouseEventKind::Drag(MouseButton::Left), 0, 1);
5089        let drag_hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, drag_data));
5090
5091        state.handle_mouse(
5092            &drag_event,
5093            drag_hit,
5094            scrollbar_hit_id,
5095            total_items,
5096            viewport_height,
5097            fixed_height,
5098        );
5099
5100        assert_eq!(
5101            state.scroll_offset, 10,
5102            "Scroll offset should update smoothly"
5103        );
5104    }
5105
5106    /// After a variable-height render the scrollbar is in rows. Five items
5107    /// six rows tall fill a five-row viewport, so counting items (the
5108    /// fixed-height path) leaves nothing to scroll.
5109    #[test]
5110    fn variable_height_mouse_scrolls_in_rows() {
5111        use crate::scrollbar::SCROLLBAR_PART_TRACK;
5112        use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
5113        use ftui_render::frame::{HitId, HitRegion};
5114
5115        struct Tall;
5116        impl RenderItem for Tall {
5117            fn render(&self, _area: Rect, _frame: &mut Frame, _selected: bool, _skip: u16) {}
5118            fn height(&self) -> u16 {
5119                6
5120            }
5121        }
5122        let items = [Tall, Tall, Tall, Tall, Tall];
5123        let list = VirtualizedList::new(&items).variable_heights();
5124        let mut state = VirtualizedListState::new();
5125        let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
5126        let area = Rect::new(0, 0, 4, 5);
5127        let mut frame = Frame::new(4, 5, &mut pool);
5128        StatefulWidget::render(&list, area, &mut frame, &mut state);
5129
5130        let id = HitId::new(1);
5131        let mouse = |state: &mut VirtualizedListState, kind, hit| {
5132            state.handle_mouse(&MouseEvent::new(kind, 3, 4), hit, id, items.len(), 5, 1);
5133        };
5134
5135        // A three-row wheel step inside a six-row item still moves one item.
5136        mouse(&mut state, MouseEventKind::ScrollDown, None);
5137        assert_eq!(state.scroll_offset(), 1);
5138        mouse(&mut state, MouseEventKind::ScrollUp, None);
5139        assert_eq!(state.scroll_offset(), 0);
5140
5141        // Clicking the bottom of the track reaches the last item.
5142        let track = (SCROLLBAR_PART_TRACK << 56) | (5 << 28) | 4;
5143        mouse(
5144            &mut state,
5145            MouseEventKind::Down(MouseButton::Left),
5146            Some((id, HitRegion::Scrollbar, track)),
5147        );
5148        assert_eq!(state.scroll_offset(), 4);
5149        StatefulWidget::render(&list, area, &mut frame, &mut state);
5150        assert_eq!(state.scroll_offset(), 4, "render keeps the offset");
5151    }
5152}