#![forbid(unsafe_code)]
use std::cell::Cell as StdCell;
use std::collections::VecDeque;
use std::ops::Range;
use std::time::Duration;
use crate::scrollbar::{Scrollbar, ScrollbarOrientation, ScrollbarState};
use crate::{StatefulWidget, clear_text_area};
use ftui_core::geometry::Rect;
pub use ftui_core::voi::{BetaPosterior, beta_voi};
use ftui_render::cell::Cell;
use ftui_render::frame::{Frame, RemeasureRequest};
use ftui_style::Style;
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct RemeasureDecision {
pub voi: f64,
pub cost: f64,
}
#[derive(Debug, Clone, PartialEq)]
pub struct RemeasurePolicy {
pub posterior: BetaPosterior,
pub sample_cost: f64,
pub min_interval_frames: u32,
pub last_sample_frame: u64,
}
impl Default for RemeasurePolicy {
fn default() -> Self {
Self {
posterior: BetaPosterior::new(1.0, 9.0),
sample_cost: 0.08,
min_interval_frames: 6,
last_sample_frame: u64::MAX,
}
}
}
impl RemeasurePolicy {
#[must_use]
pub const fn new(posterior: BetaPosterior, sample_cost: f64, min_interval_frames: u32) -> Self {
Self {
posterior,
sample_cost,
min_interval_frames,
last_sample_frame: u64::MAX,
}
}
pub fn should_sample(&mut self, frame_idx: u64) -> Option<RemeasureDecision> {
if self.last_sample_frame != u64::MAX
&& frame_idx.saturating_sub(self.last_sample_frame)
< u64::from(self.min_interval_frames)
{
return None;
}
let voi = self.posterior.voi();
if voi >= self.sample_cost {
self.last_sample_frame = frame_idx;
Some(RemeasureDecision {
voi,
cost: self.sample_cost,
})
} else {
None
}
}
pub fn should_remeasure(
&mut self,
frame_idx: u64,
violation_observed: bool,
) -> Option<RemeasureDecision> {
let cooldown_ok = self.last_sample_frame == u64::MAX
|| frame_idx.saturating_sub(self.last_sample_frame)
>= u64::from(self.min_interval_frames);
let decision = self.should_sample(frame_idx).or_else(|| {
if violation_observed && cooldown_ok {
self.last_sample_frame = frame_idx;
Some(RemeasureDecision {
voi: self.posterior.voi(),
cost: self.sample_cost,
})
} else {
None
}
});
self.observe(violation_observed);
decision
}
#[inline]
pub fn observe(&mut self, violation_observed: bool) {
self.posterior.observe(violation_observed);
}
}
#[derive(Debug, Clone)]
pub struct Virtualized<T> {
storage: VirtualizedStorage<T>,
scroll_offset: usize,
visible_count: StdCell<usize>,
overscan: usize,
item_height: ItemHeight,
follow_mode: bool,
scroll_velocity: f32,
remeasure_policy: Option<RemeasurePolicy>,
}
#[derive(Debug, Clone)]
pub enum VirtualizedStorage<T> {
Owned(VecDeque<T>),
External {
len: usize,
cache_capacity: usize,
},
}
#[derive(Debug, Clone)]
pub enum ItemHeight {
Fixed(u16),
Variable(HeightCache),
VariableFenwick(VariableHeightsFenwick),
}
#[derive(Debug, Clone)]
pub struct HeightCache {
cache: Vec<Option<u16>>,
base_offset: usize,
default_height: u16,
capacity: usize,
}
impl<T> Virtualized<T> {
#[must_use]
pub fn new(capacity: usize) -> Self {
Self {
storage: VirtualizedStorage::Owned(VecDeque::with_capacity(capacity.min(1024))),
scroll_offset: 0,
visible_count: StdCell::new(0),
overscan: 2,
item_height: ItemHeight::Fixed(1),
follow_mode: false,
scroll_velocity: 0.0,
remeasure_policy: None,
}
}
#[must_use]
pub fn external(len: usize, cache_capacity: usize) -> Self {
Self {
storage: VirtualizedStorage::External {
len,
cache_capacity,
},
scroll_offset: 0,
visible_count: StdCell::new(0),
overscan: 2,
item_height: ItemHeight::Fixed(1),
follow_mode: false,
scroll_velocity: 0.0,
remeasure_policy: None,
}
}
#[must_use]
pub fn with_remeasure_policy(mut self, policy: RemeasurePolicy) -> Self {
self.remeasure_policy = Some(policy);
self
}
#[must_use]
pub fn remeasure_policy(&self) -> Option<&RemeasurePolicy> {
self.remeasure_policy.as_ref()
}
pub fn remeasure_policy_mut(&mut self) -> Option<&mut RemeasurePolicy> {
self.remeasure_policy.as_mut()
}
pub fn invalidate(&mut self, idx: usize) {
match &mut self.item_height {
ItemHeight::Fixed(_) => {}
ItemHeight::Variable(cache) => cache.invalidate(idx),
ItemHeight::VariableFenwick(tracker) => tracker.invalidate(idx),
}
}
#[must_use]
pub fn with_item_height(mut self, height: ItemHeight) -> Self {
self.item_height = height;
self
}
#[must_use]
pub fn with_fixed_height(mut self, height: u16) -> Self {
self.item_height = ItemHeight::Fixed(height);
self
}
#[must_use]
pub fn with_height_prediction(mut self, config: PredictorConfig) -> Self {
let len = self.len();
let current = std::mem::replace(&mut self.item_height, ItemHeight::Fixed(1));
self.item_height = ItemHeight::VariableFenwick(match current {
ItemHeight::VariableFenwick(tracker) => tracker.with_predictor(config),
ItemHeight::Fixed(height) => {
VariableHeightsFenwick::new(height.max(1), len).with_predictor(config)
}
ItemHeight::Variable(cache) => {
VariableHeightsFenwick::new(cache.default_height, len).with_predictor(config)
}
});
self
}
#[must_use]
pub fn with_height_predictor(self, config: PredictorConfig) -> Self {
self.with_height_prediction(config)
}
pub fn observe_height(&mut self, idx: usize, height: u16) {
self.observe_height_in_category(idx, height, 0);
}
pub fn observe_height_in_category(&mut self, idx: usize, height: u16, category: usize) {
match &mut self.item_height {
ItemHeight::Fixed(_) => {}
ItemHeight::Variable(cache) => cache.set(idx, height),
ItemHeight::VariableFenwick(tracker) => tracker.set_in_category(idx, height, category),
}
}
#[must_use]
pub fn offset_of_item(&self, idx: usize) -> u32 {
let clamped = idx.min(self.len());
match &self.item_height {
ItemHeight::Fixed(h) => (clamped as u64)
.saturating_mul(u64::from(*h))
.min(u64::from(u32::MAX)) as u32,
ItemHeight::Variable(cache) => (0..clamped)
.fold(0u64, |acc, i| acc + u64::from(cache.get(i)))
.min(u64::from(u32::MAX)) as u32,
ItemHeight::VariableFenwick(tracker) => tracker.offset_of_item(clamped),
}
}
#[must_use]
pub fn find_item_at_offset(&self, offset: u32) -> usize {
let len = self.len();
match &self.item_height {
ItemHeight::Fixed(h) => {
let h = u32::from((*h).max(1));
((offset / h) as usize).min(len)
}
ItemHeight::Variable(cache) => {
let mut acc = 0u64;
for i in 0..len {
let next = acc + u64::from(cache.get(i).max(1));
if u64::from(offset) < next {
return i;
}
acc = next;
}
len
}
ItemHeight::VariableFenwick(tracker) => tracker.find_item_at_offset(offset),
}
}
#[must_use]
pub fn predicted_height(&self, category: usize) -> u16 {
if let ItemHeight::VariableFenwick(tracker) = &self.item_height
&& let Some(predictor) = tracker.predictor()
{
return predictor.predict(category).predicted.max(1);
}
self.unmeasured_item_height()
}
#[must_use]
pub fn predictor_stats(&self) -> Option<PredictorStats> {
match &self.item_height {
ItemHeight::VariableFenwick(tracker) => tracker.predictor().map(HeightPredictor::stats),
_ => None,
}
}
#[must_use]
pub fn unmeasured_item_height(&self) -> u16 {
match &self.item_height {
ItemHeight::Fixed(height) => *height,
ItemHeight::Variable(cache) => cache.default_height,
ItemHeight::VariableFenwick(tracker) => tracker.predicted_height(),
}
}
#[must_use]
pub fn with_variable_heights(mut self, default_height: u16) -> Self {
let len = self.len();
self.item_height =
ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, len));
self
}
#[must_use]
pub fn with_variable_heights_fenwick(mut self, default_height: u16, capacity: usize) -> Self {
self.item_height =
ItemHeight::VariableFenwick(VariableHeightsFenwick::new(default_height, capacity));
self
}
fn sync_height_tracker(&mut self, exact: bool) {
let len = self.len();
if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height
&& (tracker.len() < len || (exact && tracker.len() != len))
{
tracker.resize(len);
}
}
#[must_use]
pub fn with_overscan(mut self, overscan: usize) -> Self {
self.overscan = overscan;
self
}
#[must_use]
pub fn with_follow(mut self, follow: bool) -> Self {
self.follow_mode = follow;
self
}
#[must_use]
pub fn len(&self) -> usize {
match &self.storage {
VirtualizedStorage::Owned(items) => items.len(),
VirtualizedStorage::External { len, .. } => *len,
}
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[must_use]
pub fn scroll_offset(&self) -> usize {
self.scroll_offset.min(self.len().saturating_sub(1))
}
#[must_use]
pub fn visible_count(&self) -> usize {
self.visible_count.get()
}
#[must_use]
pub fn follow_mode(&self) -> bool {
self.follow_mode
}
#[must_use]
pub fn visible_range(&self, viewport_height: u16) -> Range<usize> {
if self.is_empty() || viewport_height == 0 {
self.visible_count.set(0);
return 0..0;
}
let items_visible = match &self.item_height {
ItemHeight::Fixed(h) if *h > 0 => viewport_height.div_ceil(*h) as usize,
ItemHeight::Fixed(_) => viewport_height as usize,
ItemHeight::Variable(cache) => {
let len = self.len();
let start = self.scroll_offset.min(len.saturating_sub(1));
let mut count = 0;
let mut total_height = 0u16;
while start + count < len {
let next = cache.get(start + count);
total_height = total_height.saturating_add(next);
count += 1;
if total_height >= viewport_height {
break;
}
}
if total_height < viewport_height && start > 0 {
count = 0;
total_height = 0;
while count < len {
let next = cache.get(len - 1 - count);
total_height = total_height.saturating_add(next);
count += 1;
if total_height >= viewport_height {
break;
}
}
}
count
}
ItemHeight::VariableFenwick(tracker) => {
let len = self.len();
let start = self.scroll_offset.min(len.saturating_sub(1));
let total = tracker.total_height_exact();
let suffix = total.saturating_sub(tracker.offset_of_item_exact(start));
if suffix < u64::from(viewport_height) {
let anchor = total.saturating_sub(u64::from(viewport_height));
len.saturating_sub(tracker.find_item_at_offset_exact(anchor))
.max(1)
} else {
tracker.visible_count(start, viewport_height).max(1)
}
}
};
let max_offset = self.len().saturating_sub(items_visible);
let start = self.scroll_offset.min(max_offset);
let end = start.saturating_add(items_visible).min(self.len());
self.visible_count.set(items_visible);
start..end
}
#[must_use]
pub fn render_range(&self, viewport_height: u16) -> Range<usize> {
let visible = self.visible_range(viewport_height);
let start = visible.start.saturating_sub(self.overscan);
let end = visible.end.saturating_add(self.overscan).min(self.len());
start..end
}
pub fn scroll(&mut self, delta: i32) {
if self.is_empty() {
return;
}
let visible_count = self.visible_count.get();
let max_offset = match self.item_height {
ItemHeight::Fixed(_) if visible_count > 0 => self.len().saturating_sub(visible_count),
_ => self.len().saturating_sub(1),
};
let clamped_current = self.scroll_offset.min(max_offset);
let new_offset = clamped_current
.saturating_add_signed(delta as isize)
.min(max_offset);
self.scroll_offset = new_offset;
if delta != 0 {
self.follow_mode = false;
}
}
pub fn scroll_to(&mut self, idx: usize) {
if let ItemHeight::VariableFenwick(tracker) = &mut self.item_height {
tracker.refresh_category_predictions();
}
self.scroll_offset = idx.min(self.len().saturating_sub(1));
self.follow_mode = false;
}
pub fn scroll_to_bottom(&mut self) {
if self.is_empty() {
self.scroll_offset = 0;
return;
}
if !matches!(self.item_height, ItemHeight::Fixed(_)) {
self.scroll_offset = usize::MAX;
return;
}
let visible_count = self.visible_count.get();
if visible_count == 0 {
self.scroll_offset = usize::MAX;
} else if self.len() > visible_count {
self.scroll_offset = self.len().saturating_sub(visible_count);
} else {
self.scroll_offset = 0;
}
}
pub fn scroll_to_top(&mut self) {
self.scroll_offset = 0;
self.follow_mode = false;
}
pub fn scroll_to_start(&mut self) {
self.scroll_to_top();
}
pub fn scroll_to_end(&mut self) {
self.scroll_to_bottom();
self.follow_mode = true;
}
pub fn page_up(&mut self) {
let visible_count = self.visible_count.get();
if visible_count > 0 {
let step = if visible_count > 1 {
visible_count - 1
} else {
1
};
let delta = i32::try_from(step).unwrap_or(i32::MAX);
self.scroll(-delta);
}
}
pub fn page_down(&mut self) {
let visible_count = self.visible_count.get();
if visible_count > 0 {
let step = if visible_count > 1 {
visible_count - 1
} else {
1
};
let delta = i32::try_from(step).unwrap_or(i32::MAX);
self.scroll(delta);
}
}
pub fn set_follow(&mut self, follow: bool) {
self.follow_mode = follow;
if follow {
self.scroll_to_bottom();
}
}
#[must_use]
pub fn is_at_bottom(&self) -> bool {
let visible_count = self.visible_count.get();
if self.len() <= visible_count {
true
} else {
self.scroll_offset >= self.len().saturating_sub(visible_count)
}
}
pub fn fling(&mut self, velocity: f32) {
self.scroll_velocity = velocity;
}
pub fn tick(&mut self, dt: Duration) {
if self.scroll_velocity.abs() > 0.1 {
let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
if delta != 0 {
self.scroll(delta);
}
self.scroll_velocity *= 0.95;
} else {
self.scroll_velocity = 0.0;
}
}
pub fn set_visible_count(&self, count: usize) {
self.visible_count.set(count);
}
#[must_use]
pub fn item_height(&self) -> &ItemHeight {
&self.item_height
}
pub fn item_height_mut(&mut self) -> &mut ItemHeight {
&mut self.item_height
}
}
impl<T> Virtualized<T> {
pub fn push(&mut self, item: T) {
if let VirtualizedStorage::Owned(items) = &mut self.storage {
items.push_back(item);
self.sync_height_tracker(false);
if self.follow_mode {
self.scroll_to_bottom();
}
}
}
#[must_use = "use the returned item (if any)"]
pub fn get(&self, idx: usize) -> Option<&T> {
if let VirtualizedStorage::Owned(items) = &self.storage {
items.get(idx)
} else {
None
}
}
#[must_use = "use the returned item (if any)"]
pub fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
if let VirtualizedStorage::Owned(items) = &mut self.storage {
items.get_mut(idx)
} else {
None
}
}
pub fn clear(&mut self) {
if let VirtualizedStorage::Owned(items) = &mut self.storage {
items.clear();
match &mut self.item_height {
ItemHeight::Fixed(_) => {}
ItemHeight::Variable(cache) => cache.clear(),
ItemHeight::VariableFenwick(tracker) => tracker.clear(),
}
}
self.scroll_offset = 0;
}
pub fn trim_front(&mut self, max: usize) -> usize {
if let VirtualizedStorage::Owned(items) = &mut self.storage
&& items.len() > max
{
let to_remove = items.len() - max;
items.drain(..to_remove);
match &mut self.item_height {
ItemHeight::Fixed(_) => {}
ItemHeight::Variable(cache) => cache.drop_front(to_remove),
ItemHeight::VariableFenwick(tracker) => tracker.drop_front(to_remove),
}
self.scroll_offset = self.scroll_offset.saturating_sub(to_remove);
return to_remove;
}
0
}
pub fn iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
match &self.storage {
VirtualizedStorage::Owned(items) => Box::new(items.iter()),
VirtualizedStorage::External { .. } => Box::new(std::iter::empty()),
}
}
pub fn set_external_len(&mut self, len: usize) {
if let VirtualizedStorage::External { len: l, .. } = &mut self.storage {
*l = len;
self.sync_height_tracker(true);
if self.follow_mode {
self.scroll_to_bottom();
}
}
}
}
impl Default for HeightCache {
fn default() -> Self {
Self::new(1, 1000)
}
}
impl HeightCache {
#[must_use]
pub fn new(default_height: u16, capacity: usize) -> Self {
Self {
cache: Vec::new(),
base_offset: 0,
default_height,
capacity,
}
}
#[must_use]
pub fn get(&self, idx: usize) -> u16 {
if idx < self.base_offset {
return self.default_height;
}
let local = idx - self.base_offset;
self.cache
.get(local)
.and_then(|h| *h)
.unwrap_or(self.default_height)
}
pub fn set(&mut self, idx: usize, height: u16) {
if self.capacity == 0 {
return;
}
if idx < self.base_offset {
return;
}
let mut local = idx - self.base_offset;
if local + 1 >= self.cache.len() + self.capacity {
self.base_offset = idx.saturating_add(1).saturating_sub(self.capacity);
self.cache.clear();
local = idx - self.base_offset;
}
if local >= self.cache.len() {
self.cache.resize(local + 1, None);
}
self.cache[local] = Some(height);
if self.cache.len() > self.capacity {
let to_remove = self.cache.len() - self.capacity;
self.cache.drain(0..to_remove);
self.base_offset += to_remove;
}
}
pub fn drop_front(&mut self, count: usize) {
if count == 0 {
return;
}
if let Some(base) = self.base_offset.checked_sub(count) {
self.base_offset = base;
return;
}
let dropped = count - self.base_offset;
if dropped >= self.cache.len() {
self.cache.clear();
} else {
self.cache.drain(0..dropped);
}
self.base_offset = 0;
}
pub fn clear(&mut self) {
self.cache.clear();
self.base_offset = 0;
}
pub fn invalidate(&mut self, idx: usize) {
if idx < self.base_offset {
return;
}
let local = idx - self.base_offset;
if let Some(slot) = self.cache.get_mut(local) {
*slot = None;
}
}
}
use crate::height_predictor::{HeightPredictor, PredictorConfig, PredictorStats};
#[derive(Debug, Clone)]
pub struct VariableHeightsFenwick {
tree: Vec<u64>,
default_height: u16,
len: usize,
measured: Vec<u64>,
unmeasured: usize,
predictor: Option<HeightPredictor>,
fill_height: u16,
categories: Vec<u16>,
cat_fill_heights: Vec<u16>,
categories_synced_len: usize,
last_violation: bool,
}
impl Default for VariableHeightsFenwick {
fn default() -> Self {
Self::new(1, 0)
}
}
impl VariableHeightsFenwick {
#[must_use]
pub fn new(default_height: u16, capacity: usize) -> Self {
let tree = Self::build_height_tree(std::iter::repeat_n(default_height, capacity));
Self {
tree,
default_height,
len: capacity,
measured: vec![0; capacity.div_ceil(64)],
unmeasured: capacity,
predictor: None,
fill_height: default_height,
categories: vec![0; capacity],
cat_fill_heights: vec![default_height],
categories_synced_len: 0,
last_violation: false,
}
}
#[must_use]
pub fn from_heights(heights: &[u16], default_height: u16) -> Self {
Self {
tree: Self::build_height_tree(heights.iter().copied()),
default_height,
len: heights.len(),
measured: Self::all_measured_bits(heights.len()),
unmeasured: 0,
predictor: None,
fill_height: default_height,
categories: vec![0; heights.len()],
cat_fill_heights: vec![default_height],
categories_synced_len: 0,
last_violation: false,
}
}
fn build_height_tree(heights: impl ExactSizeIterator<Item = u16>) -> Vec<u64> {
let len = heights.len();
assert!(
u64::try_from(len).is_ok_and(|n| n <= u64::MAX / u64::from(u16::MAX)),
"too many items for exact height aggregates"
);
let mut tree = vec![0; len + 1];
for (slot, height) in tree[1..].iter_mut().zip(heights) {
*slot = u64::from(height);
}
for idx in 1..=len {
let parent = idx + idx.isolate_lowest_one();
if parent <= len {
tree[parent] += tree[idx];
}
}
tree
}
fn all_measured_bits(len: usize) -> Vec<u64> {
let mut bits = vec![u64::MAX; len.div_ceil(64)];
if !len.is_multiple_of(64) {
*bits.last_mut().expect("partial word exists") = (1_u64 << (len % 64)) - 1;
}
bits
}
fn mark_measured(&mut self, idx: usize) {
if !self.is_measured(idx) {
self.measured[idx / 64] |= 1_u64 << (idx % 64);
self.unmeasured -= 1;
}
}
#[inline]
fn fill_height_for_category(&self, category: usize) -> u16 {
self.cat_fill_heights
.get(category)
.copied()
.unwrap_or(self.fill_height)
}
pub fn set_categories(&mut self, categories: impl IntoIterator<Item = usize>) {
self.categories.clear();
self.categories.extend(
categories
.into_iter()
.take(self.len)
.map(|c| u16::try_from(c).unwrap_or(u16::MAX)),
);
self.categories.resize(self.len, 0);
self.categories_synced_len = self.len;
for idx in 0..self.len {
if !self.is_measured(idx) {
let cat = self.categories[idx] as usize;
let h = self.fill_height_for_category(cat);
if self.get(idx) != h {
self.set_tracked_height(idx, h);
}
}
}
}
pub fn invalidate(&mut self, idx: usize) {
if idx < self.len && self.is_measured(idx) {
self.measured[idx / 64] &= !(1_u64 << (idx % 64));
self.unmeasured += 1;
let cat = self.categories.get(idx).copied().unwrap_or(0) as usize;
self.set_tracked_height(idx, self.fill_height_for_category(cat));
}
}
#[inline]
pub fn take_last_violation(&mut self) -> bool {
std::mem::replace(&mut self.last_violation, false)
}
fn set_tracked_height(&mut self, idx: usize, height: u16) {
let old = self.get(idx);
let mut node = idx + 1;
while node <= self.len {
if height >= old {
self.tree[node] += u64::from(height - old);
} else {
self.tree[node] -= u64::from(old - height);
}
node += node.isolate_lowest_one();
}
}
fn offset_of_item_exact(&self, idx: usize) -> u64 {
let mut node = idx.min(self.len);
let mut sum = 0;
while node > 0 {
sum += self.tree[node];
node &= node - 1;
}
sum
}
fn total_height_exact(&self) -> u64 {
self.offset_of_item_exact(self.len)
}
fn find_item_at_offset_exact(&self, offset: u64) -> usize {
if self.len == 0 || offset == 0 {
return 0;
}
let mut idx = 0;
let mut sum = 0;
let mut step = 1usize << (usize::BITS - self.len.leading_zeros() - 1);
while step > 0 {
if step <= self.len - idx {
let next = idx + step;
let prefix = sum + self.tree[next];
if prefix <= offset {
idx = next;
sum = prefix;
}
}
step >>= 1;
}
idx
}
#[must_use]
pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
let predictor = HeightPredictor::new(config);
self.fill_height = predictor.predict(0).predicted.max(1);
self.cat_fill_heights.fill(self.fill_height);
if self.cat_fill_heights.is_empty() {
self.cat_fill_heights.push(self.fill_height);
}
self.predictor = Some(predictor);
self.refill_unmeasured();
self
}
#[must_use]
pub fn predictor(&self) -> Option<&HeightPredictor> {
self.predictor.as_ref()
}
#[must_use]
pub fn predicted_height(&self) -> u16 {
self.fill_height
}
#[must_use]
pub fn unmeasured_count(&self) -> usize {
self.unmeasured
}
#[must_use]
pub fn is_measured(&self, idx: usize) -> bool {
idx < self.len && self.measured[idx / 64] & (1_u64 << (idx % 64)) != 0
}
fn refill_unmeasured(&mut self) -> usize {
let mut rewritten = 0;
for idx in 0..self.len {
if !self.is_measured(idx) {
let cat = self.categories.get(idx).copied().unwrap_or(0) as usize;
let h = self.fill_height_for_category(cat);
self.set_tracked_height(idx, h);
rewritten += 1;
}
}
rewritten
}
#[must_use]
pub fn len(&self) -> usize {
self.len
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len == 0
}
#[must_use]
pub fn default_height(&self) -> u16 {
self.default_height
}
#[must_use]
pub fn get(&self, idx: usize) -> u16 {
if idx >= self.len {
return self.fill_height;
}
(self.offset_of_item_exact(idx + 1) - self.offset_of_item_exact(idx)) as u16
}
pub fn set(&mut self, idx: usize, height: u16) {
self.set_in_category(idx, height, 0);
}
pub fn refresh_category_predictions(&mut self) {
let Some(predictor) = self.predictor.as_ref() else {
return;
};
if self.unmeasured == 0 || self.categories_synced_len == 0 {
return;
}
let cat_count = predictor.category_count().max(1);
if self.cat_fill_heights.len() < cat_count {
self.cat_fill_heights.resize(cat_count, self.fill_height);
}
let mut any_changed = false;
for cat in 0..cat_count {
let next = predictor.predict(cat).predicted.max(1);
if cat == 0 {
self.fill_height = next;
}
if self.cat_fill_heights[cat] != next {
self.cat_fill_heights[cat] = next;
any_changed = true;
}
}
if !any_changed {
return;
}
for idx in 0..self.len {
if !self.is_measured(idx) {
let cat = self.categories.get(idx).copied().unwrap_or(0) as usize;
let h = self.fill_height_for_category(cat);
self.set_tracked_height(idx, h);
}
}
}
pub fn set_in_category(&mut self, idx: usize, height: u16, category: usize) {
if idx >= self.len {
self.resize(idx.checked_add(1).expect("height index exceeds usize"));
}
let cat_u16 = u16::try_from(category).unwrap_or(u16::MAX);
self.categories[idx] = cat_u16;
let was_measured = self.is_measured(idx);
let old_height = self.get(idx);
self.set_tracked_height(idx, height);
self.mark_measured(idx);
if was_measured && old_height != height {
self.last_violation = true;
}
if let Some(predictor) = self.predictor.as_mut() {
let within_bounds = predictor.observe(category, height);
if !within_bounds {
self.last_violation = true;
}
let next = predictor.predict(category).predicted.max(1);
if self.cat_fill_heights.len() <= category {
self.cat_fill_heights.resize(category + 1, self.fill_height);
}
if category == 0 {
self.fill_height = next;
}
if self.categories_synced_len == 0 && category == 0 && self.cat_fill_heights[0] != next
{
self.cat_fill_heights[0] = next;
self.refill_unmeasured();
}
}
}
#[must_use]
pub fn offset_of_item(&self, idx: usize) -> u32 {
self.offset_of_item_exact(idx).min(u64::from(u32::MAX)) as u32
}
#[must_use]
pub fn find_item_at_offset(&self, offset: u32) -> usize {
self.find_item_at_offset_exact(u64::from(offset))
}
#[must_use]
pub fn visible_count(&self, start_idx: usize, viewport_height: u16) -> usize {
if self.len == 0 || viewport_height == 0 {
return 0;
}
let start = start_idx.min(self.len);
let start_offset = self.offset_of_item_exact(start);
let end_offset = start_offset.saturating_add(u64::from(viewport_height));
let end_idx = self.find_item_at_offset_exact(end_offset);
if end_idx > start {
if end_idx >= self.len {
return self.len.saturating_sub(start);
}
let end_item_start = self.offset_of_item_exact(end_idx);
if end_offset > end_item_start {
end_idx - start + 1
} else {
end_idx - start
}
} else {
if viewport_height > 0 && start < self.len {
1
} else {
0
}
}
}
#[must_use]
pub fn total_height(&self) -> u32 {
self.total_height_exact().min(u64::from(u32::MAX)) as u32
}
pub fn resize(&mut self, new_len: usize) {
if new_len == self.len {
return;
}
assert!(
u64::try_from(new_len).is_ok_and(|n| n <= u64::MAX / u64::from(u16::MAX)),
"too many items for exact height aggregates"
);
if new_len > self.len {
self.tree.reserve(new_len + 1 - self.tree.len());
let fill = u64::from(self.fill_height);
for node in (self.len + 1)..=new_len {
let mut sum = fill;
let tz = node.trailing_zeros();
for k in 0..tz {
sum += self.tree[node - (1usize << k)];
}
self.tree.push(sum);
}
self.unmeasured += new_len - self.len;
self.measured.resize(new_len.div_ceil(64), 0);
} else {
let dropped_unmeasured = (new_len..self.len)
.filter(|&idx| !self.is_measured(idx))
.count();
self.unmeasured -= dropped_unmeasured;
self.tree.truncate(new_len + 1);
self.measured.truncate(new_len.div_ceil(64));
if !new_len.is_multiple_of(64) {
*self.measured.last_mut().expect("partial word exists") &=
(1_u64 << (new_len % 64)) - 1;
}
}
self.categories.resize(new_len, 0);
self.len = new_len;
}
pub fn drop_front(&mut self, n: usize) {
if n == 0 {
return;
}
if n >= self.len {
self.clear();
return;
}
let kept: Vec<(u16, bool, u16)> = (n..self.len)
.map(|idx| (self.get(idx), self.is_measured(idx), self.categories[idx]))
.collect();
self.tree = Self::build_height_tree(kept.iter().map(|&(height, _, _)| height));
self.len = kept.len();
self.measured = vec![0; self.len.div_ceil(64)];
self.categories = kept.iter().map(|&(_, _, cat)| cat).collect();
self.categories_synced_len = self.categories_synced_len.saturating_sub(n);
self.unmeasured = self.len;
for (idx, (_, measured, _)) in kept.into_iter().enumerate() {
if measured {
self.mark_measured(idx);
}
}
}
pub fn clear(&mut self) {
self.tree = vec![0];
self.len = 0;
self.measured.clear();
self.categories.clear();
self.categories_synced_len = 0;
self.unmeasured = 0;
self.last_violation = false;
}
pub fn rebuild(&mut self, heights: &[u16]) {
self.tree = Self::build_height_tree(heights.iter().copied());
self.len = heights.len();
self.measured = Self::all_measured_bits(heights.len());
self.categories.resize(heights.len(), 0);
self.unmeasured = 0;
if let Some(predictor) = self.predictor.as_mut() {
for &height in heights {
predictor.observe(0, height);
}
self.fill_height = predictor.predict(0).predicted.max(1);
if !self.cat_fill_heights.is_empty() {
self.cat_fill_heights[0] = self.fill_height;
}
}
}
}
pub trait RenderItem {
fn render(&self, area: Rect, frame: &mut Frame, selected: bool, skip_rows: u16);
fn height(&self) -> u16 {
1
}
fn category(&self) -> usize {
0
}
}
impl<T: RenderItem> Virtualized<T> {
pub fn sync_item_categories(&mut self) {
if let (VirtualizedStorage::Owned(items), ItemHeight::VariableFenwick(tracker)) =
(&self.storage, &mut self.item_height)
&& tracker.categories_synced_len != items.len()
{
tracker.set_categories(items.iter().map(RenderItem::category));
}
}
pub fn measure(&mut self, idx: usize, height: u16) {
self.sync_item_categories();
let category = self.get(idx).map_or(0, RenderItem::category);
self.observe_height_in_category(idx, height, category);
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ListHeightMode {
Fixed(u16),
Variable,
}
#[derive(Debug, Clone)]
pub struct VirtualizedListState {
pub selected: Option<usize>,
scroll_offset: usize,
visible_count: usize,
overscan: usize,
follow_mode: bool,
scroll_velocity: f32,
scrollbar_drag_anchor: Option<usize>,
persistence_id: Option<String>,
heights: Option<VariableHeightsFenwick>,
remeasure_policy: Option<RemeasurePolicy>,
render_frame_idx: u64,
}
impl Default for VirtualizedListState {
fn default() -> Self {
Self::new()
}
}
impl VirtualizedListState {
#[must_use]
pub fn new() -> Self {
Self {
selected: None,
scroll_offset: 0,
visible_count: 0,
overscan: 2,
follow_mode: false,
scroll_velocity: 0.0,
scrollbar_drag_anchor: None,
persistence_id: None,
heights: None,
remeasure_policy: None,
render_frame_idx: 0,
}
}
#[must_use]
pub fn variable(default_height: u16) -> Self {
Self {
heights: Some(VariableHeightsFenwick::new(default_height.max(1), 0)),
..Self::new()
}
}
#[must_use]
pub fn with_predictor(mut self, config: PredictorConfig) -> Self {
self.heights = Some(
self.heights
.take()
.unwrap_or_default()
.with_predictor(config),
);
self
}
#[must_use]
pub fn with_remeasure_policy(mut self, policy: RemeasurePolicy) -> Self {
self.remeasure_policy = Some(policy);
self
}
#[must_use]
pub fn remeasure_policy(&self) -> Option<&RemeasurePolicy> {
self.remeasure_policy.as_ref()
}
pub fn remeasure_policy_mut(&mut self) -> Option<&mut RemeasurePolicy> {
self.remeasure_policy.as_mut()
}
pub fn invalidate(&mut self, idx: usize) {
if let Some(heights) = self.heights.as_mut() {
heights.invalidate(idx);
}
}
pub fn remeasure_tick(&mut self, frame_idx: u64, widget_id: u64) -> Option<RemeasureRequest> {
let violation_observed = self
.heights
.as_mut()
.is_some_and(VariableHeightsFenwick::take_last_violation);
let policy = self.remeasure_policy.as_mut()?;
let alpha = policy.posterior.alpha;
let beta = policy.posterior.beta;
let decision = policy.should_remeasure(frame_idx, violation_observed)?;
let index = self.scroll_offset;
if let Some(heights) = self.heights.as_mut() {
heights.invalidate(index);
}
Some(RemeasureRequest {
widget_id,
index,
voi: decision.voi,
cost: decision.cost,
alpha,
beta,
})
}
#[must_use]
pub fn predicted_height(&self, category: usize) -> u16 {
self.heights.as_ref().map_or(1, |heights| {
heights
.predictor()
.map_or(heights.default_height(), |predictor| {
predictor.predict(category).predicted.max(1)
})
})
}
#[must_use]
pub fn predictor_stats(&self) -> Option<PredictorStats> {
self.heights
.as_ref()
.and_then(VariableHeightsFenwick::predictor)
.map(HeightPredictor::stats)
}
pub fn measure(&mut self, idx: usize, height: u16) {
self.measure_in_category(idx, height, 0);
}
pub fn measure_in_category(&mut self, idx: usize, height: u16, category: usize) {
if let Some(heights) = self.heights.as_mut() {
if idx >= heights.len() {
heights.resize(idx + 1);
}
heights.set_in_category(idx, height.max(1), category);
}
}
pub fn resize_heights(&mut self, len: usize) {
if let Some(heights) = self.heights.as_mut()
&& heights.len() != len
{
heights.resize(len);
}
}
#[must_use]
pub fn offset_of_item(&self, idx: usize) -> u32 {
self.heights
.as_ref()
.map_or(idx as u32, |h| h.offset_of_item(idx))
}
#[must_use]
pub fn find_item_at_offset(&self, offset: u32) -> usize {
self.heights
.as_ref()
.map_or(offset as usize, |h| h.find_item_at_offset(offset))
}
#[must_use]
pub fn selected(&self) -> Option<usize> {
self.selected
}
#[must_use]
pub fn heights(&self) -> Option<&VariableHeightsFenwick> {
self.heights.as_ref()
}
#[must_use]
pub fn with_overscan(mut self, overscan: usize) -> Self {
self.overscan = overscan;
self
}
#[must_use]
pub fn with_follow(mut self, follow: bool) -> Self {
self.follow_mode = follow;
self
}
#[must_use]
pub fn with_persistence_id(mut self, id: impl Into<String>) -> Self {
self.persistence_id = Some(id.into());
self
}
#[must_use = "use the persistence id (if any)"]
pub fn persistence_id(&self) -> Option<&str> {
self.persistence_id.as_deref()
}
#[must_use]
pub fn scroll_offset(&self) -> usize {
self.scroll_offset
}
#[must_use]
pub fn scroll_offset_clamped(&self, total_items: usize) -> usize {
if total_items == 0 {
return 0;
}
self.scroll_offset.min(total_items.saturating_sub(1))
}
#[must_use]
pub fn visible_count(&self) -> usize {
self.visible_count
}
pub fn scroll(&mut self, delta: i32, total_items: usize) {
if total_items == 0 {
return;
}
let max_offset = if self.visible_count > 0 {
total_items.saturating_sub(self.visible_count)
} else {
total_items.saturating_sub(1)
};
let clamped_current = self.scroll_offset.min(max_offset);
let new_offset = clamped_current
.saturating_add_signed(delta as isize)
.min(max_offset);
self.scroll_offset = new_offset;
if delta != 0 {
self.follow_mode = false;
}
}
pub fn scroll_to(&mut self, idx: usize, total_items: usize) {
self.scroll_offset = idx.min(total_items.saturating_sub(1));
self.follow_mode = false;
}
pub fn scroll_to_top(&mut self) {
self.scroll_offset = 0;
self.follow_mode = false;
}
pub fn scroll_to_bottom(&mut self, total_items: usize) {
if total_items == 0 {
self.scroll_offset = 0;
} else {
self.scroll_offset = usize::MAX;
}
}
pub fn page_up(&mut self, total_items: usize) {
if self.visible_count > 0 {
let step = if self.visible_count > 1 {
self.visible_count - 1
} else {
1
};
let delta = i32::try_from(step).unwrap_or(i32::MAX);
self.scroll(-delta, total_items);
}
}
pub fn page_down(&mut self, total_items: usize) {
if self.visible_count > 0 {
let step = if self.visible_count > 1 {
self.visible_count - 1
} else {
1
};
let delta = i32::try_from(step).unwrap_or(i32::MAX);
self.scroll(delta, total_items);
}
}
pub fn select(&mut self, index: Option<usize>) {
self.selected = index;
}
pub fn select_previous(&mut self, total_items: usize) {
if total_items == 0 {
self.selected = None;
return;
}
self.selected = Some(match self.selected {
Some(i) if i > 0 => i - 1,
Some(_) => 0,
None => 0,
});
}
pub fn select_next(&mut self, total_items: usize) {
if total_items == 0 {
self.selected = None;
return;
}
self.selected = Some(match self.selected {
Some(i) if i < total_items - 1 => i + 1,
Some(i) => i,
None => 0,
});
}
#[must_use]
pub fn is_at_bottom(&self, total_items: usize) -> bool {
if total_items <= self.visible_count {
true
} else {
self.scroll_offset >= total_items - self.visible_count
}
}
pub fn set_follow(&mut self, follow: bool, total_items: usize) {
self.follow_mode = follow;
if follow {
self.scroll_to_bottom(total_items);
}
}
#[must_use]
pub fn follow_mode(&self) -> bool {
self.follow_mode
}
pub fn fling(&mut self, velocity: f32) {
self.scroll_velocity = velocity;
}
pub fn tick(&mut self, dt: Duration, total_items: usize) {
if self.scroll_velocity.abs() > 0.1 {
let delta = (self.scroll_velocity * dt.as_secs_f32()) as i32;
if delta != 0 {
self.scroll(delta, total_items);
}
self.scroll_velocity *= 0.95;
} else {
self.scroll_velocity = 0.0;
}
}
pub fn handle_mouse(
&mut self,
event: &ftui_core::event::MouseEvent,
hit: Option<(
ftui_render::frame::HitId,
ftui_render::frame::HitRegion,
u64,
)>,
scrollbar_hit_id: ftui_render::frame::HitId,
total_items: usize,
viewport_height: u16,
fixed_item_height: u16,
) -> crate::mouse::MouseResult {
if let Some(heights) = self.heights.as_ref()
&& heights.len() == total_items
&& total_items > 0
{
let old_item = self.scroll_offset.min(total_items - 1);
let old_row = heights.offset_of_item_exact(old_item);
let mut scrollbar_state = scrollbar_state_for_rows(
heights.total_height_exact(),
old_row,
viewport_height,
usize::MAX,
);
scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
let total_rows = heights.total_height_exact();
let row = scrollbar_state.position as u64;
let mut item = heights.find_item_at_offset_exact(row);
let start = heights.offset_of_item_exact(item);
if row + u64::from(viewport_height) >= total_rows {
item = total_items - 1;
} else if row.saturating_sub(start) * 2 > u64::from(heights.get(item)) {
item += 1;
}
if row > old_row && item <= old_item {
item = old_item + 1;
} else if row < old_row && item >= old_item {
item = old_item.saturating_sub(1);
}
self.scroll_offset = item.min(total_items - 1);
if result == crate::mouse::MouseResult::Scrolled {
self.follow_mode = false;
}
return result;
}
let items_per_viewport = viewport_height.div_ceil(fixed_item_height.max(1)) as usize;
let mut scrollbar_state =
ScrollbarState::new(total_items, self.scroll_offset, items_per_viewport);
scrollbar_state.drag_anchor = self.scrollbar_drag_anchor;
let result = scrollbar_state.handle_mouse(event, hit, scrollbar_hit_id);
self.scroll_offset = scrollbar_state.position;
self.scrollbar_drag_anchor = scrollbar_state.drag_anchor;
if result == crate::mouse::MouseResult::Scrolled {
self.follow_mode = false;
}
result
}
}
#[derive(Clone, Debug, Default, PartialEq)]
#[cfg_attr(
feature = "state-persistence",
derive(serde::Serialize, serde::Deserialize)
)]
pub struct VirtualizedListPersistState {
pub selected: Option<usize>,
pub scroll_offset: usize,
pub follow_mode: bool,
}
impl crate::stateful::Stateful for VirtualizedListState {
type State = VirtualizedListPersistState;
fn state_key(&self) -> Option<crate::stateful::StateKey> {
self.persistence_id
.as_deref()
.map(|id| crate::stateful::StateKey::new("VirtualizedList", id))
}
fn save_state(&self) -> VirtualizedListPersistState {
VirtualizedListPersistState {
selected: self.selected,
scroll_offset: self.scroll_offset,
follow_mode: self.follow_mode,
}
}
fn restore_state(&mut self, state: VirtualizedListPersistState) {
self.selected = state.selected;
self.scroll_offset = state.scroll_offset;
self.follow_mode = state.follow_mode;
self.scroll_velocity = 0.0;
self.scrollbar_drag_anchor = None;
}
}
#[derive(Debug)]
pub struct VirtualizedList<'a, T> {
items: &'a [T],
style: Style,
highlight_style: Style,
show_scrollbar: bool,
height_mode: ListHeightMode,
hit_id: Option<ftui_render::frame::HitId>,
}
impl<'a, T> VirtualizedList<'a, T> {
#[must_use]
pub fn new(items: &'a [T]) -> Self {
Self {
items,
style: Style::default(),
highlight_style: Style::default(),
show_scrollbar: true,
height_mode: ListHeightMode::Fixed(1),
hit_id: None,
}
}
#[must_use]
pub fn style(mut self, style: Style) -> Self {
self.style = style;
self
}
#[must_use]
pub fn highlight_style(mut self, style: Style) -> Self {
self.highlight_style = style;
self
}
#[must_use]
pub fn show_scrollbar(mut self, show: bool) -> Self {
self.show_scrollbar = show;
self
}
#[must_use]
pub fn fixed_height(mut self, height: u16) -> Self {
self.height_mode = ListHeightMode::Fixed(height);
self
}
#[must_use]
pub fn variable_heights(mut self) -> Self {
self.height_mode = ListHeightMode::Variable;
self
}
#[must_use]
pub fn height_mode(&self) -> ListHeightMode {
self.height_mode
}
#[must_use]
pub fn hit_id(mut self, id: ftui_render::frame::HitId) -> Self {
self.hit_id = Some(id);
self
}
}
impl<T: RenderItem> StatefulWidget for VirtualizedList<'_, T> {
type State = VirtualizedListState;
fn render(&self, area: Rect, frame: &mut Frame, state: &mut Self::State) {
#[cfg(feature = "tracing")]
let _span = tracing::debug_span!(
"widget_render",
widget = "VirtualizedList",
x = area.x,
y = area.y,
w = area.width,
h = area.height,
items = self.items.len(),
height_mode = ?self.height_mode
)
.entered();
if area.is_empty() {
return;
}
clear_text_area(frame, area, self.style);
let total_items = self.items.len();
if total_items == 0 {
state.visible_count = 0;
state.scroll_offset = 0;
if let Some(heights) = state.heights.as_mut() {
heights.clear();
}
return;
}
let ListHeightMode::Fixed(fixed_h) = self.height_mode else {
self.render_variable(area, frame, state);
return;
};
let fixed_h = fixed_h.max(1);
let items_per_viewport = area.height.div_ceil(fixed_h) as usize;
let fully_visible_items = (area.height / fixed_h) as usize;
let needs_scrollbar = self.show_scrollbar && total_items > fully_visible_items;
let content_width = if needs_scrollbar {
area.width.saturating_sub(1)
} else {
area.width
};
if let Some(selected) = state.selected
&& selected >= total_items
{
state.selected = if total_items > 0 {
Some(total_items - 1)
} else {
None
};
}
if let Some(selected) = state.selected {
let vis_count = fully_visible_items.max(1);
if selected >= state.scroll_offset.saturating_add(vis_count) {
state.scroll_offset = selected.saturating_sub(vis_count.saturating_sub(1));
} else if selected < state.scroll_offset {
state.scroll_offset = selected;
}
}
let max_offset = if fully_visible_items > 0 {
total_items.saturating_sub(fully_visible_items)
} else {
total_items.saturating_sub(1)
};
state.scroll_offset = state.scroll_offset.min(max_offset);
state.visible_count = fully_visible_items.max(1).min(total_items);
let render_start = state.scroll_offset.saturating_sub(state.overscan);
let render_end = state
.scroll_offset
.saturating_add(items_per_viewport)
.saturating_add(state.overscan)
.min(total_items);
for idx in render_start..render_end {
let relative_idx = if idx >= state.scroll_offset {
i32::try_from(idx - state.scroll_offset).unwrap_or(i32::MAX)
} else {
-(i32::try_from(state.scroll_offset - idx).unwrap_or(i32::MAX))
};
let height_i32 = i32::from(fixed_h);
let y_offset = relative_idx.saturating_mul(height_i32);
if y_offset.saturating_add(height_i32) <= 0 {
continue;
}
if y_offset >= i32::from(area.height) {
break;
}
let skip_rows = if y_offset < 0 {
y_offset.unsigned_abs() as u16
} else {
0
};
let y = i32::from(area.y)
.saturating_add(y_offset)
.clamp(i32::from(area.y), i32::from(u16::MAX)) as u16;
if y >= area.bottom() {
break;
}
let visible_height = fixed_h
.saturating_sub(skip_rows)
.min(area.bottom().saturating_sub(y));
if visible_height == 0 {
continue;
}
let row_area = Rect::new(area.x, y, content_width, visible_height);
let is_selected = state.selected == Some(idx);
let row_style = if is_selected {
self.highlight_style.merge(&self.style)
} else {
self.style
};
clear_text_area(frame, row_area, row_style);
self.items[idx].render(row_area, frame, is_selected, skip_rows);
}
if needs_scrollbar {
let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
let mut scrollbar_state =
ScrollbarState::new(total_items, state.scroll_offset, items_per_viewport);
scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
if let Some(id) = self.hit_id {
scrollbar = scrollbar.hit_id(id);
}
scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
}
}
}
fn first_item_from_offset(heights: &VariableHeightsFenwick, offset: u64) -> usize {
let mut idx = heights.find_item_at_offset_exact(offset);
if heights.offset_of_item_exact(idx) < offset {
idx += 1;
}
idx.min(heights.len().saturating_sub(1))
}
fn scrollbar_state_for_rows(
total: u64,
position: u64,
viewport: u16,
capacity: usize,
) -> ScrollbarState {
let limit = capacity as u64;
if total <= limit {
return ScrollbarState::new(
total as usize,
position.min(total) as usize,
viewport.into(),
);
}
let scaled_viewport = (u128::from(viewport) * u128::from(limit))
.div_ceil(u128::from(total))
.min(u128::from(limit)) as usize;
let max_position = total.saturating_sub(u64::from(viewport));
let scaled_position = if max_position == 0 {
0
} else {
(u128::from(position.min(max_position)) * (capacity - scaled_viewport) as u128
/ u128::from(max_position)) as usize
};
ScrollbarState::new(capacity, scaled_position, scaled_viewport)
}
impl<T: RenderItem> VirtualizedList<'_, T> {
fn render_variable(&self, area: Rect, frame: &mut Frame, state: &mut VirtualizedListState) {
let total_items = self.items.len();
let viewport = area.height;
let heights = state
.heights
.get_or_insert_with(|| VariableHeightsFenwick::new(1, total_items));
if heights.len() != total_items {
heights.resize(total_items);
}
if heights.categories_synced_len != total_items {
heights.set_categories(self.items.iter().map(RenderItem::category));
}
let measure = |heights: &mut VariableHeightsFenwick, idx: usize| {
let height = self.items[idx].height().max(1);
if !heights.is_measured(idx) || heights.get(idx) != height {
heights.set_in_category(idx, height, self.items[idx].category());
}
};
let measure_screenful = |heights: &mut VariableHeightsFenwick, start: usize| -> usize {
let mut rows = 0u16;
let mut idx = start;
while idx < total_items && rows < viewport {
measure(heights, idx);
rows = rows.saturating_add(heights.get(idx));
idx += 1;
}
(idx - start).max(1)
};
if let Some(selected) = state.selected
&& selected >= total_items
{
state.selected = Some(total_items - 1);
}
if let Some(selected) = state.selected {
measure(heights, selected);
if selected < state.scroll_offset {
state.scroll_offset = selected;
} else {
measure_screenful(heights, state.scroll_offset);
let mut sel_rows = 0u16;
for idx in (0..=selected).rev() {
if sel_rows >= viewport {
break;
}
measure(heights, idx);
sel_rows = sel_rows.saturating_add(heights.get(idx));
}
heights.refresh_category_predictions();
let top = heights.offset_of_item_exact(state.scroll_offset);
let bottom = heights.offset_of_item_exact(selected + 1);
if bottom.saturating_sub(top) > u64::from(viewport) {
let anchor = bottom.saturating_sub(u64::from(viewport));
state.scroll_offset = first_item_from_offset(heights, anchor).min(selected);
}
}
}
let mut tail_rows = 0u16;
for idx in (0..total_items).rev() {
if tail_rows >= viewport {
break;
}
measure(heights, idx);
tail_rows = tail_rows.saturating_add(heights.get(idx));
}
heights.refresh_category_predictions();
let total_height = heights.total_height_exact();
let max_start = if total_height > u64::from(viewport) {
first_item_from_offset(heights, total_height - u64::from(viewport))
} else {
0
};
state.scroll_offset = state.scroll_offset.min(max_start);
let visible = measure_screenful(heights, state.scroll_offset).min(total_items);
heights.refresh_category_predictions();
state.visible_count = visible;
let total_height = heights.total_height_exact();
let needs_scrollbar = self.show_scrollbar && total_height > u64::from(viewport);
let content_width = if needs_scrollbar {
area.width.saturating_sub(1)
} else {
area.width
};
let mut y = 0u16;
for idx in state.scroll_offset..state.scroll_offset.saturating_add(visible).min(total_items)
{
if y >= viewport {
break;
}
let row_h = heights.get(idx).min(viewport - y);
if row_h == 0 {
continue;
}
let row_area = Rect::new(area.x, area.y.saturating_add(y), content_width, row_h);
let is_selected = state.selected == Some(idx);
let row_style = if is_selected {
self.highlight_style.merge(&self.style)
} else {
self.style
};
clear_text_area(frame, row_area, row_style);
self.items[idx].render(row_area, frame, is_selected, 0);
y = y.saturating_add(row_h);
}
if needs_scrollbar {
let scrollbar_area = Rect::new(area.right().saturating_sub(1), area.y, 1, area.height);
let mut scrollbar_state = scrollbar_state_for_rows(
total_height,
heights.offset_of_item_exact(state.scroll_offset),
viewport,
usize::MAX,
);
scrollbar_state.drag_anchor = state.scrollbar_drag_anchor;
let mut scrollbar = Scrollbar::new(ScrollbarOrientation::VerticalRight);
if let Some(id) = self.hit_id {
scrollbar = scrollbar.hit_id(id);
}
scrollbar.render(scrollbar_area, frame, &mut scrollbar_state);
}
let widget_id = self.hit_id.map_or_else(
|| ftui_a11y::node::A11yNodeInfo::stable_id_for(ftui_a11y::node::A11yRole::List, area),
|id| u64::from(id.id()),
);
let frame_idx = state.render_frame_idx;
state.render_frame_idx = state.render_frame_idx.wrapping_add(1);
if let Some(req) = state.remeasure_tick(frame_idx, widget_id) {
frame.push_remeasure_request(req);
}
}
}
impl RenderItem for String {
fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
if area.is_empty() {
return;
}
let max_chars = area.width as usize;
if skip_rows > 0 {
return;
}
for (i, ch) in self.chars().take(max_chars).enumerate() {
frame
.buffer
.set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
}
}
}
impl RenderItem for &str {
fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, skip_rows: u16) {
if area.is_empty() {
return;
}
if skip_rows > 0 {
return;
}
let max_chars = area.width as usize;
for (i, ch) in self.chars().take(max_chars).enumerate() {
frame
.buffer
.set(area.x.saturating_add(i as u16), area.y, Cell::from_char(ch));
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
fn raw_row_text(frame: &Frame, y: u16) -> String {
let width = frame.buffer.width();
let mut actual = String::new();
for x in 0..width {
let ch = frame
.buffer
.get(x, y)
.and_then(|cell| cell.content.as_char())
.unwrap_or(' ');
actual.push(ch);
}
actual
}
#[test]
fn test_new_virtualized() {
let virt: Virtualized<String> = Virtualized::new(100);
assert_eq!(virt.len(), 0);
assert!(virt.is_empty());
}
#[test]
fn test_push_and_len() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.push(1);
virt.push(2);
virt.push(3);
assert_eq!(virt.len(), 3);
assert!(!virt.is_empty());
}
#[test]
fn test_visible_range_fixed_height() {
let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(2);
for i in 0..20 {
virt.push(i);
}
let range = virt.visible_range(20);
assert_eq!(range, 0..10);
}
#[test]
fn test_visible_range_variable_height_clamps() {
let mut cache = HeightCache::new(1, 16);
cache.set(0, 3);
cache.set(1, 3);
cache.set(2, 3);
let mut virt: Virtualized<i32> =
Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
for i in 0..3 {
virt.push(i);
}
let range = virt.visible_range(5);
assert_eq!(range, 0..2);
}
#[test]
fn test_visible_range_variable_height_exact_fit() {
let mut cache = HeightCache::new(1, 16);
cache.set(0, 2);
cache.set(1, 3);
let mut virt: Virtualized<i32> =
Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
for i in 0..2 {
virt.push(i);
}
let range = virt.visible_range(5);
assert_eq!(range, 0..2);
}
#[test]
fn test_visible_range_with_scroll() {
let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(1);
for i in 0..50 {
virt.push(i);
}
virt.scroll(10);
let range = virt.visible_range(10);
assert_eq!(range, 10..20);
}
#[test]
fn test_visible_range_variable_height_excludes_partial() {
let mut cache = HeightCache::new(1, 16);
cache.set(0, 6);
cache.set(1, 6);
let mut virt: Virtualized<i32> =
Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
virt.push(1);
virt.push(2);
virt.push(3);
let range = virt.visible_range(10);
assert_eq!(range, 0..2);
}
#[test]
fn test_visible_range_variable_height_exact_fit_larger() {
let mut cache = HeightCache::new(1, 16);
cache.set(0, 4);
cache.set(1, 6);
let mut virt: Virtualized<i32> =
Virtualized::new(100).with_item_height(ItemHeight::Variable(cache));
virt.push(1);
virt.push(2);
virt.push(3);
let range = virt.visible_range(10);
assert_eq!(range, 0..2);
}
#[test]
fn test_visible_range_variable_height_default_for_unmeasured() {
let cache = HeightCache::new(2, 16);
let mut virt: Virtualized<i32> =
Virtualized::new(10).with_item_height(ItemHeight::Variable(cache));
for i in 0..3 {
virt.push(i);
}
let range = virt.visible_range(5);
assert_eq!(range, 0..3);
}
#[test]
fn test_visible_range_variable_bottom_anchor_after_lazy_scroll_to_bottom() {
let mut virt: Virtualized<i32> =
Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
for i in 0..20 {
virt.push(i);
}
virt.scroll_to_bottom();
assert_eq!(virt.visible_range(10), 15..20);
}
#[test]
fn test_visible_range_fenwick_bottom_anchor_after_lazy_scroll_to_bottom() {
let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 20);
for i in 0..20 {
virt.push(i);
}
virt.scroll_to_bottom();
assert_eq!(virt.visible_range(10), 15..20);
}
#[test]
fn test_visible_range_fenwick_bottom_anchor_counts_partial_top_item() {
let tracker = VariableHeightsFenwick::from_heights(&[3, 2, 5, 1, 4], 1);
let mut virt: Virtualized<i32> =
Virtualized::new(10).with_item_height(ItemHeight::VariableFenwick(tracker));
for i in 0..5 {
virt.push(i);
}
virt.scroll_to_bottom();
assert_eq!(virt.visible_range(5), 3..5);
virt.scroll_to_bottom();
assert_eq!(virt.visible_range(6), 2..5);
}
#[test]
fn test_visible_range_variable_near_end_clamps_like_fixed() {
let mut virt: Virtualized<i32> =
Virtualized::new(100).with_item_height(ItemHeight::Variable(HeightCache::new(2, 64)));
for i in 0..20 {
virt.push(i);
}
virt.scroll_to(18);
assert_eq!(virt.visible_range(10), 15..20);
}
#[test]
fn test_render_range_with_overscan() {
let mut virt: Virtualized<i32> =
Virtualized::new(100).with_fixed_height(1).with_overscan(2);
for i in 0..50 {
virt.push(i);
}
virt.scroll(10);
let range = virt.render_range(10);
assert_eq!(range, 8..22);
}
#[test]
fn test_scroll_bounds() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..10 {
virt.push(i);
}
virt.scroll(-100);
assert_eq!(virt.scroll_offset(), 0);
virt.scroll(100);
assert_eq!(virt.scroll_offset(), 9);
}
#[test]
fn test_scroll_to() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..20 {
virt.push(i);
}
virt.scroll_to(15);
assert_eq!(virt.scroll_offset(), 15);
virt.scroll_to(100);
assert_eq!(virt.scroll_offset(), 19);
}
#[test]
fn test_follow_mode() {
let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
virt.set_visible_count(5);
for i in 0..10 {
virt.push(i);
}
assert!(virt.is_at_bottom());
virt.scroll(-5);
assert!(!virt.follow_mode());
}
#[test]
fn test_scroll_to_start_and_end() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.set_visible_count(5);
for i in 0..20 {
virt.push(i);
}
virt.scroll_to(10);
virt.set_follow(true);
virt.scroll_to_start();
assert_eq!(virt.scroll_offset(), 0);
assert!(!virt.follow_mode());
virt.scroll_to_end();
assert!(virt.is_at_bottom());
assert!(virt.follow_mode());
}
#[test]
fn test_virtualized_page_navigation() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.set_visible_count(5);
for i in 0..30 {
virt.push(i);
}
virt.scroll_to(15);
virt.page_up();
assert_eq!(virt.scroll_offset(), 11);
virt.page_down();
assert_eq!(virt.scroll_offset(), 15);
virt.scroll_to(2);
virt.page_up();
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn test_height_cache() {
let mut cache = HeightCache::new(1, 100);
assert_eq!(cache.get(0), 1);
assert_eq!(cache.get(50), 1);
cache.set(5, 3);
assert_eq!(cache.get(5), 3);
assert_eq!(cache.get(4), 1);
assert_eq!(cache.get(6), 1);
}
#[test]
fn test_height_cache_large_index_window() {
let mut cache = HeightCache::new(1, 8);
cache.set(10_000, 4);
assert_eq!(cache.get(10_000), 4);
assert_eq!(cache.get(0), 1);
assert!(cache.cache.len() <= cache.capacity);
}
#[test]
fn test_clear() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..10 {
virt.push(i);
}
virt.scroll(5);
virt.clear();
assert_eq!(virt.len(), 0);
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn test_get_item() {
let mut virt: Virtualized<String> = Virtualized::new(100);
virt.push("hello".to_string());
virt.push("world".to_string());
assert_eq!(virt.get(0), Some(&"hello".to_string()));
assert_eq!(virt.get(1), Some(&"world".to_string()));
assert_eq!(virt.get(2), None);
}
#[test]
fn test_external_storage_len() {
let mut virt: Virtualized<i32> = Virtualized::external(1000, 100);
assert_eq!(virt.len(), 1000);
virt.set_external_len(2000);
assert_eq!(virt.len(), 2000);
}
#[test]
fn test_momentum_scrolling() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..50 {
virt.push(i);
}
virt.fling(10.0);
virt.tick(Duration::from_millis(100));
assert!(virt.scroll_offset() > 0);
}
#[test]
fn test_virtualized_list_state_new() {
let state = VirtualizedListState::new();
assert_eq!(state.selected, None);
assert_eq!(state.scroll_offset(), 0);
assert_eq!(state.visible_count(), 0);
}
#[test]
fn test_virtualized_list_state_select_next() {
let mut state = VirtualizedListState::new();
state.select_next(10);
assert_eq!(state.selected, Some(0));
state.select_next(10);
assert_eq!(state.selected, Some(1));
state.selected = Some(9);
state.select_next(10);
assert_eq!(state.selected, Some(9));
}
#[test]
fn test_virtualized_list_state_select_previous() {
let mut state = VirtualizedListState::new();
state.selected = Some(5);
state.select_previous(10);
assert_eq!(state.selected, Some(4));
state.selected = Some(0);
state.select_previous(10);
assert_eq!(state.selected, Some(0));
}
#[test]
fn test_virtualized_list_state_scroll() {
let mut state = VirtualizedListState::new();
state.scroll(5, 20);
assert_eq!(state.scroll_offset(), 5);
state.scroll(-3, 20);
assert_eq!(state.scroll_offset(), 2);
state.scroll(-100, 20);
assert_eq!(state.scroll_offset(), 0);
state.scroll(100, 20);
assert_eq!(state.scroll_offset(), 19);
}
#[test]
fn test_virtualized_list_state_follow_mode() {
let mut state = VirtualizedListState::new().with_follow(true);
assert!(state.follow_mode());
state.scroll(5, 20);
assert!(!state.follow_mode());
}
#[test]
fn test_render_item_string() {
let s = String::from("hello");
assert_eq!(s.height(), 1);
}
#[test]
fn test_page_up_down() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..50 {
virt.push(i);
}
virt.set_visible_count(10);
assert_eq!(virt.scroll_offset(), 0);
virt.page_down();
assert_eq!(virt.scroll_offset(), 9);
virt.page_down();
assert_eq!(virt.scroll_offset(), 18);
virt.page_up();
assert_eq!(virt.scroll_offset(), 9);
virt.page_up();
assert_eq!(virt.scroll_offset(), 0);
virt.page_up();
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn test_render_scales_with_visible_not_total() {
use ftui_render::grapheme_pool::GraphemePool;
use std::time::Instant;
let small_items: Vec<String> = (0..1_000).map(|i| format!("Line {}", i)).collect();
let small_list = VirtualizedList::new(&small_items);
let mut small_state = VirtualizedListState::new();
let area = Rect::new(0, 0, 80, 24);
let mut pool = GraphemePool::new();
let mut frame = Frame::new(80, 24, &mut pool);
small_list.render(area, &mut frame, &mut small_state);
let start = Instant::now();
for _ in 0..100 {
frame.buffer.clear();
small_list.render(area, &mut frame, &mut small_state);
}
let small_time = start.elapsed();
let large_items: Vec<String> = (0..100_000).map(|i| format!("Line {}", i)).collect();
let large_list = VirtualizedList::new(&large_items);
let mut large_state = VirtualizedListState::new();
large_list.render(area, &mut frame, &mut large_state);
let start = Instant::now();
for _ in 0..100 {
frame.buffer.clear();
large_list.render(area, &mut frame, &mut large_state);
}
let large_time = start.elapsed();
assert!(
large_time < small_time * 3,
"Render does not scale O(visible): 1K={:?}, 100K={:?}",
small_time,
large_time
);
}
#[test]
fn test_scroll_is_constant_time() {
use std::time::Instant;
let mut small: Virtualized<i32> = Virtualized::new(1_000);
for i in 0..1_000 {
small.push(i);
}
small.set_visible_count(24);
let mut large: Virtualized<i32> = Virtualized::new(100_000);
for i in 0..100_000 {
large.push(i);
}
large.set_visible_count(24);
let iterations = 10_000;
for _ in 0..iterations {
small.scroll(1);
small.scroll(-1);
large.scroll(1);
large.scroll(-1);
}
let measure = |v: &mut Virtualized<i32>| -> std::time::Duration {
let runs = 5;
let mut best = std::time::Duration::MAX;
for _ in 0..runs {
let start = Instant::now();
for _ in 0..iterations {
v.scroll(1);
v.scroll(-1);
}
best = best.min(start.elapsed());
}
best
};
let small_time = measure(&mut small);
let large_time = measure(&mut large);
let ceiling = small_time
.checked_mul(10)
.unwrap_or(std::time::Duration::MAX);
assert!(
large_time < ceiling,
"Scroll is not O(1) (grows with list size): 1K={:?}, 100K={:?}",
small_time,
large_time
);
}
#[test]
fn render_partially_offscreen_top_skips_item() {
use ftui_render::grapheme_pool::GraphemePool;
struct IndexedItem(usize);
impl RenderItem for IndexedItem {
fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
let ch = char::from_digit(self.0 as u32, 10).unwrap();
for y in area.y..area.bottom() {
frame.buffer.set(area.x, y, Cell::from_char(ch));
}
}
fn height(&self) -> u16 {
2
}
}
let items = vec![
IndexedItem(0),
IndexedItem(1),
IndexedItem(2),
IndexedItem(3),
];
let list = VirtualizedList::new(&items).fixed_height(2);
let mut state = VirtualizedListState::new().with_overscan(1);
state.scroll_offset = 1;
let mut pool = GraphemePool::new();
let mut frame = Frame::new(10, 5, &mut pool);
list.render(Rect::new(0, 0, 10, 5), &mut frame, &mut state);
let cell = frame.buffer.get(0, 0).unwrap();
assert_eq!(cell.content.as_char(), Some('1'));
}
#[test]
fn render_bottom_boundary_clips_partial_item() {
use ftui_render::grapheme_pool::GraphemePool;
struct IndexedItem(u16);
impl RenderItem for IndexedItem {
fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
let ch = char::from_digit(self.0 as u32, 10).unwrap();
for y in area.y..area.bottom() {
frame.buffer.set(area.x, y, Cell::from_char(ch));
}
}
fn height(&self) -> u16 {
2
}
}
let items = vec![IndexedItem(0), IndexedItem(1), IndexedItem(2)];
let list = VirtualizedList::new(&items)
.fixed_height(2)
.show_scrollbar(false);
let mut state = VirtualizedListState::new();
let mut pool = GraphemePool::new();
let mut frame = Frame::new(4, 4, &mut pool);
list.render(Rect::new(0, 0, 4, 3), &mut frame, &mut state);
assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
assert_eq!(frame.buffer.get(0, 1).unwrap().content.as_char(), Some('0'));
assert_eq!(frame.buffer.get(0, 2).unwrap().content.as_char(), Some('1'));
assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), None);
}
#[test]
fn render_after_fling_advances_visible_rows() {
use ftui_render::grapheme_pool::GraphemePool;
struct IndexedItem(u16);
impl RenderItem for IndexedItem {
fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
let ch = char::from_digit(self.0 as u32, 10).unwrap();
for y in area.y..area.bottom() {
frame.buffer.set(area.x, y, Cell::from_char(ch));
}
}
}
let items: Vec<IndexedItem> = (0..10).map(IndexedItem).collect();
let list = VirtualizedList::new(&items)
.fixed_height(1)
.show_scrollbar(false);
let mut state = VirtualizedListState::new();
let mut pool = GraphemePool::new();
let mut frame = Frame::new(4, 3, &mut pool);
let area = Rect::new(0, 0, 4, 3);
list.render(area, &mut frame, &mut state);
assert_eq!(state.scroll_offset(), 0);
assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('0'));
state.fling(40.0);
state.tick(Duration::from_millis(100), items.len());
assert_eq!(state.scroll_offset(), 4);
frame.buffer.clear();
list.render(area, &mut frame, &mut state);
assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('4'));
}
#[test]
fn render_empty_virtualized_list_clears_stale_viewport() {
use ftui_render::grapheme_pool::GraphemePool;
let items: Vec<String> = Vec::new();
let list = VirtualizedList::new(&items).show_scrollbar(false);
let mut state = VirtualizedListState::new();
let mut pool = GraphemePool::new();
let mut frame = Frame::new(6, 3, &mut pool);
let area = Rect::new(0, 0, 6, 3);
frame.buffer.fill(area, Cell::from_char('X'));
list.render(area, &mut frame, &mut state);
assert_eq!(raw_row_text(&frame, 0), " ");
assert_eq!(raw_row_text(&frame, 1), " ");
assert_eq!(raw_row_text(&frame, 2), " ");
}
#[test]
fn render_shorter_virtualized_row_clears_stale_suffix() {
use ftui_render::grapheme_pool::GraphemePool;
let long_items = vec!["Hello".to_string()];
let short_items = vec!["Hi".to_string()];
let area = Rect::new(0, 0, 6, 1);
let mut state = VirtualizedListState::new();
let mut pool = GraphemePool::new();
let mut frame = Frame::new(6, 1, &mut pool);
VirtualizedList::new(&long_items)
.show_scrollbar(false)
.render(area, &mut frame, &mut state);
VirtualizedList::new(&short_items)
.show_scrollbar(false)
.render(area, &mut frame, &mut state);
assert_eq!(raw_row_text(&frame, 0), "Hi ");
}
#[test]
fn test_memory_bounded_by_ring_capacity() {
use crate::log_ring::LogRing;
let mut ring: LogRing<String> = LogRing::new(1_000);
for i in 0..100_000 {
ring.push(format!("Line {}", i));
}
assert_eq!(ring.len(), 1_000);
assert_eq!(ring.total_count(), 100_000);
assert_eq!(ring.first_index(), 99_000);
assert!(ring.get(99_999).is_some());
assert!(ring.get(99_000).is_some());
assert!(ring.get(0).is_none());
assert!(ring.get(98_999).is_none());
}
#[test]
fn test_visible_range_constant_regardless_of_total() {
let mut small: Virtualized<i32> = Virtualized::new(100);
for i in 0..100 {
small.push(i);
}
let small_range = small.visible_range(24);
let mut large: Virtualized<i32> = Virtualized::new(100_000);
for i in 0..100_000 {
large.push(i);
}
let large_range = large.visible_range(24);
assert_eq!(small_range.end - small_range.start, 24);
assert_eq!(large_range.end - large_range.start, 24);
}
#[test]
fn test_virtualized_list_state_page_up_down() {
let mut state = VirtualizedListState::new();
state.visible_count = 10;
state.page_down(50);
assert_eq!(state.scroll_offset(), 9);
state.page_down(50);
assert_eq!(state.scroll_offset(), 18);
state.page_up(50);
assert_eq!(state.scroll_offset(), 9);
state.page_up(50);
assert_eq!(state.scroll_offset(), 0);
}
#[test]
fn test_variable_heights_fenwick_new() {
let tracker = VariableHeightsFenwick::new(2, 10);
assert_eq!(tracker.len(), 10);
assert!(!tracker.is_empty());
assert_eq!(tracker.default_height(), 2);
}
#[test]
fn test_variable_heights_fenwick_empty() {
let tracker = VariableHeightsFenwick::new(1, 0);
assert!(tracker.is_empty());
assert_eq!(tracker.total_height(), 0);
}
#[test]
fn test_variable_heights_fenwick_from_heights() {
let heights = vec![3, 2, 5, 1, 4];
let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
assert_eq!(tracker.len(), 5);
assert_eq!(tracker.get(0), 3);
assert_eq!(tracker.get(1), 2);
assert_eq!(tracker.get(2), 5);
assert_eq!(tracker.get(3), 1);
assert_eq!(tracker.get(4), 4);
assert_eq!(tracker.total_height(), 15);
}
#[test]
fn test_variable_heights_fenwick_offset_of_item() {
let heights = vec![3, 2, 5, 1, 4];
let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
assert_eq!(tracker.offset_of_item(0), 0);
assert_eq!(tracker.offset_of_item(1), 3);
assert_eq!(tracker.offset_of_item(2), 5);
assert_eq!(tracker.offset_of_item(3), 10);
assert_eq!(tracker.offset_of_item(4), 11);
assert_eq!(tracker.offset_of_item(5), 15); }
#[test]
fn test_variable_heights_fenwick_find_item_at_offset() {
let heights = vec![3, 2, 5, 1, 4];
let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
assert_eq!(tracker.find_item_at_offset(0), 0);
assert_eq!(tracker.find_item_at_offset(1), 0);
assert_eq!(tracker.find_item_at_offset(3), 1);
assert_eq!(tracker.find_item_at_offset(5), 2);
assert_eq!(tracker.find_item_at_offset(10), 3);
assert_eq!(tracker.find_item_at_offset(11), 4);
assert_eq!(tracker.find_item_at_offset(15), 5);
}
#[test]
fn fenwick_large_height_totals_do_not_wrap() {
let heights = vec![u16::MAX; 131_072];
let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
let offset = 4_294_836_224_u32;
assert_eq!(
tracker.find_item_at_offset(offset),
(u64::from(offset) / u64::from(u16::MAX)) as usize,
"a wrapped root aggregate must not skip the entire list"
);
assert_eq!(tracker.total_height(), u32::MAX);
assert_eq!(tracker.offset_of_item(131_072), u32::MAX);
}
#[test]
#[should_panic(expected = "height index exceeds usize")]
fn fenwick_rejects_unrepresentable_index() {
VariableHeightsFenwick::default().set(usize::MAX, 1);
}
#[test]
fn fenwick_large_updates_and_resize_match_u64_oracle() {
fn check(tracker: &VariableHeightsFenwick, heights: &[u16]) {
let mut prefixes = Vec::with_capacity(heights.len() + 1);
prefixes.push(0u64);
for &height in heights {
prefixes.push(prefixes.last().copied().unwrap() + u64::from(height));
}
let total = prefixes.last().copied().unwrap();
assert_eq!(tracker.len(), heights.len());
assert_eq!(tracker.total_height_exact(), total);
assert_eq!(
tracker.total_height(),
total.min(u64::from(u32::MAX)) as u32
);
let mut queries = vec![0, 1, u64::from(u32::MAX) - 1, u64::from(u32::MAX), total];
for idx in (0..=heights.len()).step_by(1_024).chain([heights.len()]) {
assert_eq!(tracker.offset_of_item_exact(idx), prefixes[idx]);
assert_eq!(
tracker.offset_of_item(idx),
prefixes[idx].min(u64::from(u32::MAX)) as u32
);
queries.extend([
prefixes[idx].saturating_sub(1),
prefixes[idx],
prefixes[idx] + 1,
]);
}
for offset in queries {
let expected = if offset == 0 {
0
} else {
prefixes[1..].partition_point(|&prefix| prefix <= offset)
};
assert_eq!(tracker.find_item_at_offset_exact(offset), expected);
if let Ok(offset) = u32::try_from(offset) {
assert_eq!(tracker.find_item_at_offset(offset), expected);
}
}
}
for len in [65_536, 65_537, 65_538, 131_072] {
let mut heights = vec![u16::MAX; len];
let mut tracker = VariableHeightsFenwick::new(u16::MAX, len);
check(&tracker, &heights);
for idx in [0, 1, 32_768, 65_535, len - 1] {
tracker.set(idx, 0);
heights[idx] = 0;
assert_eq!(tracker.get(idx), 0);
}
check(&tracker, &heights);
tracker.set(0, u16::MAX);
heights[0] = u16::MAX;
tracker.resize(65_536);
heights.truncate(65_536);
check(&tracker, &heights);
tracker.resize(65_540);
heights.resize(65_540, u16::MAX);
check(&tracker, &heights);
}
let mut seed = 0xa076_1d64_78bd_642fu64;
let mut heights: Vec<u16> = (0..131_072)
.map(|_| {
seed = seed.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
32_768 + ((seed >> 48) as u16 / 2)
})
.collect();
let mut tracker = VariableHeightsFenwick::from_heights(&heights, 1);
for idx in (0..heights.len()).step_by(997) {
heights[idx] = (idx % 65_536) as u16;
tracker.set(idx, heights[idx]);
assert_eq!(tracker.get(idx), heights[idx]);
}
check(&tracker, &heights);
tracker.drop_front(3);
check(&tracker, &heights[3..]);
heights.fill(u16::MAX);
tracker.rebuild(&heights);
check(&tracker, &heights);
tracker.clear();
check(&tracker, &[]);
tracker.resize(4);
check(&tracker, &[1; 4]);
}
#[test]
fn fenwick_large_visible_range_keeps_tail_reachable() {
let len = 65_548;
let mut virt: Virtualized<()> =
Virtualized::external(len, 10).with_variable_heights_fenwick(u16::MAX, len);
for idx in 65_538..len {
virt.observe_height(idx, 1);
}
virt.scroll_to_bottom();
assert_eq!(virt.visible_range(5), len - 5..len);
virt.scroll_to(len - 8);
assert_eq!(virt.visible_range(5), len - 8..len - 3);
}
#[test]
fn fenwick_large_scrollbar_renders_proportionally_at_32_bit_capacity() {
fn thumb_rows(mut state: ScrollbarState) -> Vec<u16> {
let scrollbar =
Scrollbar::new(ScrollbarOrientation::VerticalRight).symbols(".", "T", None, None);
let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
let mut frame = Frame::new(1, 21, &mut pool);
scrollbar.render(Rect::new(0, 0, 1, 21), &mut frame, &mut state);
(0..21)
.filter(|&y| frame.buffer.get(0, y).unwrap().content.as_char() == Some('T'))
.collect()
}
let capacity = u32::MAX as usize;
let total = 131_072 * u64::from(u16::MAX);
let viewport = 20;
let max_position = total - u64::from(viewport);
for (position, expected_row) in [
(0, 0),
(max_position / 4, 5),
(max_position / 2, 10),
(max_position / 4 * 3, 15),
(max_position, 20),
(total, 20),
] {
let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
assert_eq!(scaled.content_length, capacity);
assert!(scaled.viewport_length > 0);
assert_eq!(thumb_rows(scaled), vec![expected_row]);
}
let position = u64::from(u32::MAX) + u64::from(u16::MAX);
let scaled = scrollbar_state_for_rows(total, position, viewport, capacity);
assert_eq!(thumb_rows(scaled), vec![10]);
let saturated = ScrollbarState::new(capacity, capacity, viewport.into());
assert_eq!(thumb_rows(saturated), vec![20]);
for (total, position, viewport) in [(0, 0, 0), (100, 50, 20), (u64::from(u32::MAX), 7, 5)] {
let exact = scrollbar_state_for_rows(total, position, viewport, capacity);
assert_eq!(exact.content_length, total as usize);
assert_eq!(exact.position, position as usize);
assert_eq!(exact.viewport_length, usize::from(viewport));
}
if usize::BITS > 32 {
let exact = scrollbar_state_for_rows(total, position, viewport, usize::MAX);
assert_eq!(exact.content_length as u64, total);
assert_eq!(exact.position as u64, position);
assert_eq!(exact.viewport_length, usize::from(viewport));
}
}
#[test]
fn test_variable_heights_fenwick_visible_count() {
let heights = vec![3, 2, 5, 1, 4];
let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
assert_eq!(tracker.visible_count(0, 5), 2);
assert_eq!(tracker.visible_count(0, 4), 2);
assert_eq!(tracker.visible_count(0, 10), 3);
assert_eq!(tracker.visible_count(2, 6), 2);
}
#[test]
fn test_variable_heights_fenwick_visible_count_viewport_beyond_total_height() {
let heights = vec![1, 1, 1];
let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
assert_eq!(tracker.visible_count(0, 10), 3);
assert_eq!(tracker.visible_count(1, 10), 2);
assert_eq!(tracker.visible_count(2, 10), 1);
}
#[test]
fn test_variable_heights_fenwick_set() {
let mut tracker = VariableHeightsFenwick::new(1, 5);
assert_eq!(tracker.get(0), 1);
assert_eq!(tracker.total_height(), 5);
tracker.set(2, 10);
assert_eq!(tracker.get(2), 10);
assert_eq!(tracker.total_height(), 14); }
#[test]
fn test_variable_heights_fenwick_resize() {
let mut tracker = VariableHeightsFenwick::new(2, 3);
assert_eq!(tracker.len(), 3);
assert_eq!(tracker.total_height(), 6);
tracker.resize(5);
assert_eq!(tracker.len(), 5);
assert_eq!(tracker.total_height(), 10);
assert_eq!(tracker.get(4), 2);
tracker.resize(2);
assert_eq!(tracker.len(), 2);
assert_eq!(tracker.total_height(), 4);
}
#[test]
fn test_variable_heights_fenwick_point_update_and_range_query() {
fn range_sum(tracker: &VariableHeightsFenwick, left: usize, right: usize) -> u32 {
tracker
.offset_of_item(right.saturating_add(1))
.saturating_sub(tracker.offset_of_item(left))
}
let mut tracker = VariableHeightsFenwick::from_heights(&[2, 4, 1, 3, 5, 2], 1);
let mut naive = [2_u32, 4, 1, 3, 5, 2];
tracker.set(2, 7);
naive[2] = 7;
tracker.set(5, 1);
naive[5] = 1;
tracker.set(0, 6);
naive[0] = 6;
let mut running = 0u32;
for (i, value) in naive.iter().enumerate() {
running = running.saturating_add(*value);
assert_eq!(tracker.offset_of_item(i + 1), running);
}
let naive_sum = |left: usize, right: usize| -> u32 { naive[left..=right].iter().sum() };
assert_eq!(range_sum(&tracker, 0, 0), naive_sum(0, 0));
assert_eq!(range_sum(&tracker, 1, 3), naive_sum(1, 3));
assert_eq!(range_sum(&tracker, 2, 5), naive_sum(2, 5));
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(96))]
#[test]
fn property_measured_heights_survive_mutations(
operations in proptest::collection::vec((0u8..3, 0usize..150, 1u16..32), 1..80)
) {
let mut tracker = VariableHeightsFenwick::new(2, 0);
let mut expected: Vec<Option<u16>> = Vec::new();
for (operation, index, height) in operations {
match operation {
0 => {
if index >= expected.len() {
expected.resize(index + 1, None);
}
expected[index] = Some(height);
tracker.set(index, height);
}
1 => {
expected.resize(index, None);
tracker.resize(index);
}
_ => {
expected.drain(..index.min(expected.len()));
tracker.drop_front(index);
}
}
prop_assert_eq!(tracker.len(), expected.len());
prop_assert_eq!(
tracker.unmeasured_count(),
expected.iter().filter(|height| height.is_none()).count()
);
let mut prefix = 0;
for (index, height) in expected.iter().enumerate() {
prop_assert_eq!(tracker.offset_of_item(index), prefix);
prop_assert_eq!(tracker.is_measured(index), height.is_some());
prop_assert_eq!(tracker.get(index), height.unwrap_or(2));
prefix += u32::from(height.unwrap_or(2));
}
prop_assert_eq!(tracker.total_height(), prefix);
}
}
#[test]
fn property_variable_heights_fenwick_prefix_sums_match_naive(
heights in proptest::collection::vec(1u16..=32u16, 1..160)
) {
let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
let mut naive_prefix = 0u32;
prop_assert_eq!(tracker.offset_of_item(0), 0);
for (i, height) in heights.iter().enumerate() {
naive_prefix = naive_prefix.saturating_add(u32::from(*height));
prop_assert_eq!(
tracker.offset_of_item(i + 1),
naive_prefix,
"prefix mismatch at index {} for heights {:?}",
i,
heights
);
}
}
#[test]
fn property_variable_heights_fenwick_visible_count_matches_naive(
heights in proptest::collection::vec(1u16..=24u16, 1..128),
start_idx in 0usize..192usize,
viewport_height in 1u16..=120u16
) {
fn naive_visible_count(heights: &[u16], start_idx: usize, viewport_height: u16) -> usize {
if heights.is_empty() || viewport_height == 0 {
return 0;
}
let start = start_idx.min(heights.len());
if start >= heights.len() {
return 0;
}
let start_offset: u32 = heights[..start].iter().map(|&h| u32::from(h)).sum();
let end_offset = start_offset.saturating_add(u32::from(viewport_height));
let mut count = 0usize;
let mut cursor = start_offset;
for &height in &heights[start..] {
if cursor >= end_offset {
break;
}
count = count.saturating_add(1);
cursor = cursor.saturating_add(u32::from(height));
}
if count == 0 { 1 } else { count }
}
let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
let expected = naive_visible_count(&heights, start_idx, viewport_height);
let actual = tracker.visible_count(start_idx, viewport_height);
prop_assert_eq!(
actual,
expected,
"visible_count mismatch for start={} viewport={} heights={:?}",
start_idx,
viewport_height,
heights
);
}
}
#[test]
fn fenwick_predictor_fills_unmeasured_slots_and_tracks_observations() {
let config = PredictorConfig {
default_height: 1,
prior_mean: 1.0,
prior_strength: 2.0,
..PredictorConfig::default()
};
let mut tracker = VariableHeightsFenwick::new(1, 10).with_predictor(config);
assert_eq!(tracker.predicted_height(), 1, "cold start uses the default");
assert_eq!(tracker.unmeasured_count(), 10);
assert_eq!(tracker.total_height(), 10);
for idx in 0..3 {
tracker.set(idx, 3);
}
assert_eq!(tracker.predicted_height(), 2);
assert_eq!(tracker.unmeasured_count(), 7);
assert_eq!(tracker.get(0), 3, "measured slots keep their measurement");
assert_eq!(tracker.get(7), 2, "unmeasured slots hold the prediction");
assert_eq!(tracker.total_height(), 3 * 3 + 7 * 2);
assert_eq!(tracker.offset_of_item(4), 9 + 2);
for idx in 3..6 {
tracker.set(idx, 3);
}
assert_eq!(tracker.predicted_height(), 3);
assert_eq!(tracker.total_height(), 6 * 3 + 4 * 3);
assert!(tracker.is_measured(5) && !tracker.is_measured(6));
assert_eq!(
tracker.predictor().map(HeightPredictor::total_measurements),
Some(6)
);
tracker.resize(12);
assert_eq!(tracker.get(11), 3);
assert_eq!(tracker.unmeasured_count(), 6);
assert_eq!(tracker.find_item_at_offset(tracker.total_height() - 1), 11);
tracker.resize(4);
assert_eq!(tracker.unmeasured_count(), 0);
tracker.resize(6);
assert_eq!(tracker.unmeasured_count(), 2);
assert_eq!(tracker.total_height(), 4 * 3 + 2 * 3);
tracker.rebuild(&[5, 5, 5, 5, 5, 5, 5, 5]);
assert_eq!(tracker.unmeasured_count(), 0);
assert_eq!(tracker.total_height(), 40);
assert!(
tracker.predicted_height() >= 4,
"posterior pulled toward the taller rows"
);
let mut plain = VariableHeightsFenwick::new(2, 4);
plain.set(0, 9);
assert_eq!(plain.predicted_height(), 2);
assert_eq!(plain.get(3), 2);
assert_eq!(plain.unmeasured_count(), 3);
assert!(plain.predictor().is_none());
}
#[test]
fn virtualized_height_prediction_observe_height_trains_the_model() {
let mut virt: Virtualized<i32> = Virtualized::new(100)
.with_fixed_height(1)
.with_height_prediction(PredictorConfig::default());
assert!(matches!(virt.item_height(), ItemHeight::VariableFenwick(_)));
assert_eq!(virt.unmeasured_item_height(), 1);
for idx in 0..4 {
virt.observe_height(idx, 4);
}
assert_eq!(virt.unmeasured_item_height(), 3);
let ItemHeight::VariableFenwick(tracker) = virt.item_height() else {
panic!("expected the Fenwick tracker");
};
assert_eq!(tracker.get(0), 4);
assert_eq!(tracker.len(), 4);
assert_eq!(
tracker.get(40),
3,
"beyond the tracked length: the prediction"
);
let mut fixed: Virtualized<i32> = Virtualized::new(10).with_fixed_height(2);
fixed.observe_height(0, 9);
assert_eq!(
fixed.unmeasured_item_height(),
2,
"fixed heights ignore observations"
);
let mut linear: Virtualized<i32> =
Virtualized::new(10).with_item_height(ItemHeight::Variable(HeightCache::new(2, 8)));
linear.observe_height(1, 5);
assert_eq!(linear.unmeasured_item_height(), 2);
let ItemHeight::Variable(cache) = linear.item_height() else {
panic!("expected the linear cache");
};
assert_eq!(cache.get(1), 5);
}
#[test]
fn test_virtualized_with_variable_heights_fenwick() {
let mut virt: Virtualized<i32> = Virtualized::new(100).with_variable_heights_fenwick(2, 10);
for i in 0..10 {
virt.push(i);
}
let range = virt.visible_range(6);
assert_eq!(range.end - range.start, 3);
}
proptest! {
#[test]
fn variable_height_implementations_agree(
heights in proptest::collection::vec(1u16..=5, 1..40),
viewport in 1u16..=20,
default_height in 1u16..=4,
offset_seed in 0usize..64,
) {
let len = heights.len();
let mut cache: Virtualized<usize> = Virtualized::new(len)
.with_item_height(ItemHeight::Variable(HeightCache::new(default_height, len)));
let mut fenwick: Virtualized<usize> =
Virtualized::new(len).with_variable_heights_fenwick(default_height, len);
for i in 0..len {
cache.push(i);
fenwick.push(i);
}
for (idx, height) in heights.iter().enumerate() {
cache.observe_height(idx, *height);
fenwick.observe_height(idx, *height);
}
let offset = offset_seed % len;
cache.scroll_to(offset);
fenwick.scroll_to(offset);
prop_assert_eq!(
cache.visible_range(viewport),
fenwick.visible_range(viewport),
"implementations disagree at len={} viewport={} offset={}",
len,
viewport,
offset
);
cache.scroll_to_bottom();
fenwick.scroll_to_bottom();
let bottom_cache = cache.visible_range(viewport);
let bottom_fenwick = fenwick.visible_range(viewport);
prop_assert_eq!(&bottom_cache, &bottom_fenwick, "bottom anchoring disagrees");
prop_assert!(
bottom_cache.contains(&(len - 1)),
"last item unreachable: range {:?} of {} items",
bottom_cache,
len
);
let keep = 1 + offset_seed % len;
if keep < len {
prop_assert_eq!(cache.trim_front(keep), fenwick.trim_front(keep));
let len = cache.len();
cache.scroll_to_bottom();
fenwick.scroll_to_bottom();
let trimmed_cache = cache.visible_range(viewport);
let trimmed_fenwick = fenwick.visible_range(viewport);
prop_assert_eq!(
&trimmed_cache,
&trimmed_fenwick,
"implementations disagree after trimming to {} items",
keep
);
prop_assert!(
trimmed_cache.contains(&(len - 1)),
"last item unreachable after a trim: range {:?} of {} items",
trimmed_cache,
len
);
}
}
}
#[test]
fn test_variable_heights_fenwick_performance() {
use std::time::Instant;
let n = 100_000;
let heights: Vec<u16> = (0..n).map(|i| (i % 10 + 1) as u16).collect();
let tracker = VariableHeightsFenwick::from_heights(&heights, 1);
let _ = tracker.find_item_at_offset(500_000);
let _ = tracker.offset_of_item(50_000);
let start = Instant::now();
let mut _sink = 0usize;
for i in 0..10_000 {
_sink = _sink.wrapping_add(tracker.find_item_at_offset((i * 50) as u32));
}
let find_time = start.elapsed();
let start = Instant::now();
let mut _sink2 = 0u32;
for i in 0..10_000 {
_sink2 = _sink2.wrapping_add(tracker.offset_of_item((i * 10) % n));
}
let offset_time = start.elapsed();
eprintln!("=== VariableHeightsFenwick Performance (n={n}) ===");
eprintln!("10k find_item_at_offset: {:?}", find_time);
eprintln!("10k offset_of_item: {:?}", offset_time);
assert!(
find_time < std::time::Duration::from_millis(50),
"find_item_at_offset too slow: {:?}",
find_time
);
assert!(
offset_time < std::time::Duration::from_millis(50),
"offset_of_item too slow: {:?}",
offset_time
);
}
#[test]
fn test_variable_heights_fenwick_scales_logarithmically() {
use std::time::Instant;
let small_n = 1_000;
let small_heights: Vec<u16> = (0..small_n).map(|i| (i % 5 + 1) as u16).collect();
let small_tracker = VariableHeightsFenwick::from_heights(&small_heights, 1);
let large_n = 100_000;
let large_heights: Vec<u16> = (0..large_n).map(|i| (i % 5 + 1) as u16).collect();
let large_tracker = VariableHeightsFenwick::from_heights(&large_heights, 1);
let iterations = 5_000;
let start = Instant::now();
for i in 0..iterations {
let _ = small_tracker.find_item_at_offset((i * 2) as u32);
}
let small_time = start.elapsed();
let start = Instant::now();
for i in 0..iterations {
let _ = large_tracker.find_item_at_offset((i * 200) as u32);
}
let large_time = start.elapsed();
assert!(
large_time < small_time * 10,
"Not O(log n): small={:?}, large={:?}",
small_time,
large_time
);
}
#[test]
fn new_zero_capacity() {
let virt: Virtualized<i32> = Virtualized::new(0);
assert_eq!(virt.len(), 0);
assert!(virt.is_empty());
assert_eq!(virt.scroll_offset(), 0);
assert_eq!(virt.visible_count(), 0);
assert!(!virt.follow_mode());
}
#[test]
fn external_zero_len_zero_cache() {
let virt: Virtualized<i32> = Virtualized::external(0, 0);
assert_eq!(virt.len(), 0);
assert!(virt.is_empty());
}
#[test]
fn external_storage_returns_none_for_get() {
let virt: Virtualized<i32> = Virtualized::external(100, 10);
assert_eq!(virt.get(0), None);
assert_eq!(virt.get(50), None);
}
#[test]
fn external_storage_returns_none_for_get_mut() {
let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
assert!(virt.get_mut(0).is_none());
}
#[test]
fn push_on_external_is_noop() {
let mut virt: Virtualized<i32> = Virtualized::external(5, 10);
virt.push(42);
assert_eq!(virt.len(), 5);
}
#[test]
fn iter_on_external_is_empty() {
let virt: Virtualized<i32> = Virtualized::external(100, 10);
assert_eq!(virt.iter().count(), 0);
}
#[test]
fn set_external_len_on_owned_is_noop() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.push(1);
virt.set_external_len(999);
assert_eq!(virt.len(), 1); }
#[test]
fn visible_range_zero_viewport() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.push(1);
let range = virt.visible_range(0);
assert_eq!(range, 0..0);
assert_eq!(virt.visible_count(), 0);
}
#[test]
fn visible_range_empty_container() {
let virt: Virtualized<i32> = Virtualized::new(100);
let range = virt.visible_range(24);
assert_eq!(range, 0..0);
}
#[test]
fn visible_range_fixed_height_zero() {
let mut virt: Virtualized<i32> = Virtualized::new(100).with_fixed_height(0);
for i in 0..10 {
virt.push(i);
}
let range = virt.visible_range(5);
assert_eq!(range, 0..5);
}
#[test]
fn visible_range_fewer_items_than_viewport() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..3 {
virt.push(i);
}
let range = virt.visible_range(24);
assert_eq!(range, 0..3);
}
#[test]
fn visible_range_single_item() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.push(42);
let range = virt.visible_range(1);
assert_eq!(range, 0..1);
}
#[test]
fn render_range_at_start_clamps_overscan() {
let mut virt: Virtualized<i32> =
Virtualized::new(100).with_fixed_height(1).with_overscan(5);
for i in 0..20 {
virt.push(i);
}
let range = virt.render_range(10);
assert_eq!(range.start, 0);
}
#[test]
fn render_range_at_end_clamps_overscan() {
let mut virt: Virtualized<i32> =
Virtualized::new(100).with_fixed_height(1).with_overscan(5);
for i in 0..20 {
virt.push(i);
}
virt.set_visible_count(10);
virt.scroll_to(10); let range = virt.render_range(10);
assert_eq!(range.end, 20);
}
#[test]
fn render_range_zero_overscan() {
let mut virt: Virtualized<i32> =
Virtualized::new(100).with_fixed_height(1).with_overscan(0);
for i in 0..20 {
virt.push(i);
}
virt.set_visible_count(10);
virt.scroll_to(5);
let range = virt.render_range(10);
let visible = virt.visible_range(10);
assert_eq!(range, visible);
}
#[test]
fn scroll_on_empty_is_noop() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.scroll(10);
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn scroll_delta_zero_does_not_disable_follow() {
let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
virt.push(1);
virt.scroll(0);
assert!(virt.follow_mode());
}
#[test]
fn scroll_negative_beyond_start() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..10 {
virt.push(i);
}
virt.scroll(-1);
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn scroll_to_on_empty() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.scroll_to(100);
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn scroll_to_top_already_at_top() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.push(1);
virt.scroll_to_top();
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn scroll_to_bottom_fewer_items_than_visible() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.set_visible_count(10);
for i in 0..3 {
virt.push(i);
}
virt.scroll_to_bottom();
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn scroll_to_bottom_visible_count_zero() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..20 {
virt.push(i);
}
virt.scroll_to_bottom();
assert_eq!(virt.scroll_offset, usize::MAX);
assert_eq!(virt.scroll_offset(), 19);
}
#[test]
fn page_up_visible_count_zero_is_noop() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..20 {
virt.push(i);
}
virt.scroll_to(10);
virt.page_up();
assert_eq!(virt.scroll_offset(), 10);
}
#[test]
fn page_down_visible_count_zero_is_noop() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..20 {
virt.push(i);
}
virt.page_down();
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn is_at_bottom_fewer_items_than_visible() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.set_visible_count(10);
for i in 0..3 {
virt.push(i);
}
assert!(virt.is_at_bottom());
}
#[test]
fn is_at_bottom_empty() {
let virt: Virtualized<i32> = Virtualized::new(100);
assert!(virt.is_at_bottom());
}
#[test]
fn trim_front_under_max_returns_zero() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..5 {
virt.push(i);
}
let removed = virt.trim_front(10);
assert_eq!(removed, 0);
assert_eq!(virt.len(), 5);
}
#[test]
fn trim_front_adjusts_scroll_offset() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..20 {
virt.push(i);
}
virt.scroll_to(10);
let removed = virt.trim_front(15);
assert_eq!(removed, 5);
assert_eq!(virt.len(), 15);
assert_eq!(virt.scroll_offset(), 5);
}
#[test]
fn trim_front_scroll_offset_saturates_to_zero() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..20 {
virt.push(i);
}
virt.scroll_to(2);
let removed = virt.trim_front(10);
assert_eq!(removed, 10);
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn trim_front_on_external_returns_zero() {
let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
let removed = virt.trim_front(5);
assert_eq!(removed, 0);
}
#[test]
fn scroll_to_bottom_sets_sentinel_for_lazy_clamping() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..20 {
virt.push(i);
}
virt.scroll_to_bottom();
assert_eq!(virt.scroll_offset, usize::MAX);
let range = virt.visible_range(10);
assert_eq!(range, 10..20);
assert_eq!(virt.visible_count(), 10);
}
#[test]
fn clear_on_external_resets_scroll() {
let mut virt: Virtualized<i32> = Virtualized::external(100, 10);
virt.scroll_to(50);
virt.clear();
assert_eq!(virt.scroll_offset(), 0);
assert_eq!(virt.len(), 100);
}
#[test]
fn tick_zero_velocity_is_noop() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..20 {
virt.push(i);
}
virt.tick(Duration::from_millis(100));
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn tick_below_threshold_stops_momentum() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..20 {
virt.push(i);
}
virt.fling(0.05); virt.tick(Duration::from_millis(100));
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn tick_zero_duration_no_scroll() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..50 {
virt.push(i);
}
virt.fling(100.0);
virt.tick(Duration::ZERO);
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn fling_negative_scrolls_up() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
for i in 0..50 {
virt.push(i);
}
virt.scroll(20);
let before = virt.scroll_offset();
virt.fling(-50.0);
virt.tick(Duration::from_millis(100));
assert!(virt.scroll_offset() < before);
}
#[test]
fn follow_mode_auto_scrolls_on_push() {
let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
virt.set_visible_count(5);
for i in 0..20 {
virt.push(i);
}
assert!(virt.is_at_bottom());
assert_eq!(virt.scroll_offset(), 15); }
#[test]
fn set_follow_false_does_not_scroll() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.set_visible_count(5);
for i in 0..20 {
virt.push(i);
}
virt.scroll_to(5);
virt.set_follow(false);
assert_eq!(virt.scroll_offset(), 5); }
#[test]
fn scroll_to_start_disables_follow() {
let mut virt: Virtualized<i32> = Virtualized::new(100).with_follow(true);
virt.set_visible_count(5);
for i in 0..20 {
virt.push(i);
}
virt.scroll_to_start();
assert!(!virt.follow_mode());
assert_eq!(virt.scroll_offset(), 0);
}
#[test]
fn scroll_to_end_enables_follow() {
let mut virt: Virtualized<i32> = Virtualized::new(100);
virt.set_visible_count(5);
for i in 0..20 {
virt.push(i);
}
assert!(!virt.follow_mode());
virt.scroll_to_end();
assert!(virt.follow_mode());
assert!(virt.is_at_bottom());
}
#[test]
fn external_follow_mode_scrolls_on_set_external_len() {
let mut virt: Virtualized<i32> = Virtualized::external(10, 100).with_follow(true);
virt.set_visible_count(5);
virt.set_external_len(20);
assert_eq!(virt.len(), 20);
assert!(virt.is_at_bottom());
}
#[test]
fn builder_chain_all_options() {
let virt: Virtualized<i32> = Virtualized::new(100)
.with_fixed_height(3)
.with_overscan(5)
.with_follow(true);
assert!(virt.follow_mode());
let range = virt.visible_range(9);
assert_eq!(range, 0..0);
}
#[test]
fn height_cache_default() {
let cache = HeightCache::default();
assert_eq!(cache.get(0), 1); assert_eq!(cache.capacity, 1000);
}
#[test]
fn height_cache_get_before_base_offset() {
let mut cache = HeightCache::new(5, 100);
cache.set(200, 10); assert_eq!(cache.get(0), 5);
}
#[test]
fn height_cache_set_before_base_offset_ignored() {
let mut cache = HeightCache::new(5, 100);
cache.set(200, 10);
let base = cache.base_offset;
cache.set(0, 99); assert_eq!(cache.get(0), 5); assert_eq!(cache.base_offset, base); }
#[test]
fn height_cache_capacity_zero_ignores_all_sets() {
let mut cache = HeightCache::new(3, 0);
cache.set(0, 10);
cache.set(5, 20);
assert_eq!(cache.get(0), 3);
assert_eq!(cache.get(5), 3);
}
#[test]
fn height_cache_clear_resets_base() {
let mut cache = HeightCache::new(1, 100);
cache.set(50, 10);
cache.clear();
assert_eq!(cache.base_offset, 0);
assert_eq!(cache.get(50), 1); }
#[test]
fn height_cache_eviction_trims_oldest() {
let mut cache = HeightCache::new(1, 4);
for i in 0..6 {
cache.set(i, (i + 10) as u16);
}
assert!(cache.cache.len() <= cache.capacity);
assert_eq!(cache.get(5), 15);
assert_eq!(cache.get(4), 14);
assert_eq!(cache.get(3), 13);
assert_eq!(cache.get(2), 12);
assert_eq!(cache.get(1), 1);
assert_eq!(cache.get(0), 1);
}
#[test]
fn fenwick_default_is_empty() {
let tracker = VariableHeightsFenwick::default();
assert!(tracker.is_empty());
assert_eq!(tracker.len(), 0);
assert_eq!(tracker.total_height(), 0);
assert_eq!(tracker.default_height(), 1);
}
#[test]
fn fenwick_get_beyond_len_returns_default() {
let tracker = VariableHeightsFenwick::new(3, 5);
assert_eq!(tracker.get(5), 3); assert_eq!(tracker.get(100), 3);
}
#[test]
fn fenwick_set_beyond_len_resizes() {
let mut tracker = VariableHeightsFenwick::new(2, 3);
assert_eq!(tracker.len(), 3);
tracker.set(10, 7);
assert!(tracker.len() > 10);
assert_eq!(tracker.get(10), 7);
}
#[test]
fn fenwick_offset_of_item_zero_always_zero() {
let tracker = VariableHeightsFenwick::new(5, 10);
assert_eq!(tracker.offset_of_item(0), 0);
let empty = VariableHeightsFenwick::new(5, 0);
assert_eq!(empty.offset_of_item(0), 0);
}
#[test]
fn fenwick_find_item_at_offset_empty() {
let tracker = VariableHeightsFenwick::new(1, 0);
assert_eq!(tracker.find_item_at_offset(0), 0);
assert_eq!(tracker.find_item_at_offset(100), 0);
}
#[test]
fn fenwick_visible_count_zero_viewport() {
let tracker = VariableHeightsFenwick::new(2, 10);
assert_eq!(tracker.visible_count(0, 0), 0);
}
#[test]
fn fenwick_visible_count_start_beyond_len() {
let tracker = VariableHeightsFenwick::new(2, 5);
let count = tracker.visible_count(100, 10);
assert_eq!(count, 0);
}
#[test]
fn fenwick_clear_then_operations() {
let mut tracker = VariableHeightsFenwick::new(3, 5);
assert_eq!(tracker.total_height(), 15);
tracker.clear();
assert_eq!(tracker.len(), 0);
assert_eq!(tracker.total_height(), 0);
assert_eq!(tracker.find_item_at_offset(0), 0);
}
#[test]
fn fenwick_rebuild_replaces_data() {
let mut tracker = VariableHeightsFenwick::new(1, 10);
assert_eq!(tracker.total_height(), 10);
tracker.rebuild(&[5, 3, 2]);
assert_eq!(tracker.len(), 3);
assert_eq!(tracker.total_height(), 10);
assert_eq!(tracker.get(0), 5);
assert_eq!(tracker.get(1), 3);
assert_eq!(tracker.get(2), 2);
}
#[test]
fn fenwick_resize_same_size_is_noop() {
let mut tracker = VariableHeightsFenwick::new(2, 5);
tracker.set(2, 10);
tracker.resize(5);
assert_eq!(tracker.get(2), 10);
assert_eq!(tracker.len(), 5);
}
#[test]
fn list_state_default_matches_new() {
let d = VirtualizedListState::default();
let n = VirtualizedListState::new();
assert_eq!(d.selected, n.selected);
assert_eq!(d.scroll_offset(), n.scroll_offset());
assert_eq!(d.visible_count(), n.visible_count());
assert_eq!(d.follow_mode(), n.follow_mode());
}
#[test]
fn list_state_select_next_on_empty() {
let mut state = VirtualizedListState::new();
state.select_next(0);
assert_eq!(state.selected, None);
}
#[test]
fn list_state_select_previous_on_empty() {
let mut state = VirtualizedListState::new();
state.select_previous(0);
assert_eq!(state.selected, None);
}
#[test]
fn list_state_select_previous_from_none() {
let mut state = VirtualizedListState::new();
state.select_previous(10);
assert_eq!(state.selected, Some(0));
}
#[test]
fn list_state_select_next_from_none() {
let mut state = VirtualizedListState::new();
state.select_next(10);
assert_eq!(state.selected, Some(0));
}
#[test]
fn list_state_scroll_zero_items() {
let mut state = VirtualizedListState::new();
state.scroll(10, 0);
assert_eq!(state.scroll_offset(), 0);
}
#[test]
fn list_state_scroll_to_clamps() {
let mut state = VirtualizedListState::new();
state.scroll_to(100, 10);
assert_eq!(state.scroll_offset(), 9);
}
#[test]
fn list_state_scroll_to_bottom_zero_items() {
let mut state = VirtualizedListState::new();
state.scroll_to_bottom(0);
assert_eq!(state.scroll_offset(), 0);
}
#[test]
fn list_state_is_at_bottom_zero_items() {
let state = VirtualizedListState::new();
assert!(state.is_at_bottom(0));
}
#[test]
fn list_state_page_up_visible_count_zero() {
let mut state = VirtualizedListState::new();
state.scroll_offset = 5;
state.page_up(20);
assert_eq!(state.scroll_offset(), 5);
}
#[test]
fn list_state_page_down_visible_count_zero() {
let mut state = VirtualizedListState::new();
state.page_down(20);
assert_eq!(state.scroll_offset(), 0);
}
#[test]
fn list_state_set_follow_false_no_scroll() {
let mut state = VirtualizedListState::new();
state.scroll_offset = 5;
state.set_follow(false, 20);
assert_eq!(state.scroll_offset(), 5); assert!(!state.follow_mode());
}
#[test]
fn list_state_persistence_id() {
let state = VirtualizedListState::new().with_persistence_id("my-list");
assert_eq!(state.persistence_id(), Some("my-list"));
}
#[test]
fn list_state_persistence_id_none() {
let state = VirtualizedListState::new();
assert_eq!(state.persistence_id(), None);
}
#[test]
fn list_state_momentum_tick_zero_items() {
let mut state = VirtualizedListState::new();
state.fling(50.0);
state.tick(Duration::from_millis(100), 0);
assert_eq!(state.scroll_offset(), 0);
}
#[test]
fn persist_state_default() {
let ps = VirtualizedListPersistState::default();
assert_eq!(ps.selected, None);
assert_eq!(ps.scroll_offset, 0);
assert!(!ps.follow_mode);
}
#[test]
fn persist_state_eq() {
let a = VirtualizedListPersistState {
selected: Some(5),
scroll_offset: 10,
follow_mode: true,
};
let b = a.clone();
assert_eq!(a, b);
}
#[test]
fn stateful_state_key_with_persistence_id() {
use crate::stateful::Stateful;
let state = VirtualizedListState::new().with_persistence_id("logs");
let key = state.state_key().expect("named list has a key");
assert_eq!(key.widget_type, "VirtualizedList");
assert_eq!(key.instance_id, "logs");
}
#[test]
fn stateful_state_without_id_is_not_persisted() {
use crate::stateful::Stateful;
assert!(VirtualizedListState::new().state_key().is_none());
}
#[test]
fn stateful_save_restore_roundtrip() {
use crate::stateful::Stateful;
let mut state = VirtualizedListState::new();
state.selected = Some(7);
state.scroll_offset = 15;
state.follow_mode = true;
state.scroll_velocity = 42.0;
let saved = state.save_state();
assert_eq!(saved.selected, Some(7));
assert_eq!(saved.scroll_offset, 15);
assert!(saved.follow_mode);
let mut restored = VirtualizedListState::new();
restored.scroll_velocity = 99.0;
restored.restore_state(saved);
assert_eq!(restored.selected, Some(7));
assert_eq!(restored.scroll_offset, 15);
assert!(restored.follow_mode);
assert_eq!(restored.scroll_velocity, 0.0);
}
#[test]
fn virtualized_list_builder() {
let items: Vec<String> = vec!["a".into()];
let list = VirtualizedList::new(&items)
.style(Style::default())
.highlight_style(Style::default())
.show_scrollbar(false)
.fixed_height(3);
assert_eq!(list.height_mode(), ListHeightMode::Fixed(3));
assert!(!list.show_scrollbar);
assert_eq!(
VirtualizedList::new(&items)
.variable_heights()
.height_mode(),
ListHeightMode::Variable
);
}
#[test]
fn with_variable_heights_defaults_to_fenwick_and_scrolls_in_log_time() {
let mut v: Virtualized<usize> = Virtualized::external(10_000, 0).with_variable_heights(3);
let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
panic!("expected the Fenwick tracker, got {:?}", v.item_height());
};
assert_eq!(tracker.len(), 10_000);
assert_eq!(tracker.offset_of_item(9_999), 3 * 9_999);
for k in 0..100u32 {
let offset = k * 297;
let idx = tracker.find_item_at_offset(offset);
let start = tracker.offset_of_item(idx);
assert!(
start <= offset && offset < start + u32::from(tracker.get(idx)),
"offset {offset} must land inside item {idx} [{start}, +{})",
tracker.get(idx)
);
}
v.scroll_to(9_999);
let range = v.visible_range(24);
assert_eq!(range.end, 10_000);
assert_eq!(range.end - range.start, 8, "24 rows / 3 per item");
v.observe_height(5, 7);
let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
unreachable!()
};
assert_eq!(tracker.offset_of_item(6), 3 * 6 + 4);
assert!(tracker.is_measured(5));
assert_eq!(v.unmeasured_item_height(), 3);
}
#[test]
fn variable_height_tracker_follows_owned_storage() {
let mut v: Virtualized<String> = Virtualized::new(8).with_variable_heights(2);
for i in 0..5 {
v.push(format!("row {i}"));
}
let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
unreachable!()
};
assert_eq!(tracker.len(), 5);
assert_eq!(tracker.total_height(), 10);
v.observe_height(0, 5);
v.observe_height(3, 4);
assert_eq!(v.trim_front(3), 2);
let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
unreachable!()
};
assert_eq!(tracker.len(), 3);
assert!(!tracker.is_measured(0));
assert!(tracker.is_measured(1));
assert_eq!(tracker.get(1), 4);
assert_eq!(tracker.total_height(), 2 + 4 + 2);
v.clear();
let ItemHeight::VariableFenwick(tracker) = v.item_height() else {
unreachable!()
};
assert_eq!(tracker.len(), 0);
assert_eq!(tracker.total_height(), 0);
}
#[test]
fn legacy_height_cache_follows_owned_storage() {
let mut v: Virtualized<String> =
Virtualized::new(8).with_item_height(ItemHeight::Variable(HeightCache::new(1, 64)));
for i in 0..6 {
v.push(format!("row {i}"));
}
v.observe_height(0, 9);
v.observe_height(4, 4);
assert_eq!(v.trim_front(3), 3);
let ItemHeight::Variable(cache) = v.item_height() else {
unreachable!()
};
assert_eq!(cache.get(0), 1);
assert_eq!(cache.get(1), 4);
assert_eq!(v.visible_range(4), 0..2);
v.clear();
for i in 0..3 {
v.push(format!("fresh {i}"));
}
let ItemHeight::Variable(cache) = v.item_height() else {
unreachable!()
};
assert_eq!(cache.get(0), 1);
assert_eq!(cache.get(1), 1);
assert_eq!(v.visible_range(4), 0..3);
}
#[test]
fn height_cache_drop_front_shifts_a_window_past_the_prefix() {
let mut cache = HeightCache::new(1, 4);
for idx in 10..14 {
cache.set(idx, idx as u16);
}
cache.drop_front(10);
for idx in 0..4 {
assert_eq!(cache.get(idx), 10 + idx as u16);
}
cache.drop_front(2);
assert_eq!(cache.get(0), 12);
assert_eq!(cache.get(1), 13);
assert_eq!(cache.get(2), 1);
cache.drop_front(9);
assert_eq!(cache.get(0), 1);
}
#[test]
fn measure_updates_fenwick_and_predictor() {
let mut list: Virtualized<String> = Virtualized::external(10, 0)
.with_variable_heights(3)
.with_height_prediction(PredictorConfig {
default_height: 3,
prior_mean: 3.0,
prior_strength: 100.0,
..PredictorConfig::default()
});
let ItemHeight::VariableFenwick(before) = list.item_height() else {
panic!("expected Fenwick heights");
};
let offset = before.offset_of_item(6);
list.measure(5, 7);
let ItemHeight::VariableFenwick(after) = list.item_height() else {
panic!("expected Fenwick heights");
};
assert_eq!(after.offset_of_item(6), offset + 4);
assert_eq!(list.predictor_stats().unwrap().measurements, 1);
assert_eq!(list.predicted_height(0), 3);
}
#[test]
fn unmeasured_rows_use_predicted_mean() {
let mut list: Virtualized<String> = Virtualized::external(100, 0)
.with_variable_heights(1)
.with_height_prediction(PredictorConfig::default());
for idx in 0..20 {
list.measure(idx, 4);
}
assert_eq!(list.predicted_height(0), 4);
assert_eq!(list.predictor_stats().unwrap().measurements, 20);
let ItemHeight::VariableFenwick(heights) = list.item_height() else {
panic!("expected Fenwick heights");
};
assert!(!heights.is_measured(99));
assert_eq!(heights.get(99), 4);
assert_eq!(heights.total_height(), 400);
assert_eq!(String::from("uncategorized").category(), 0);
}
#[test]
fn measured_bitset_tracks_word_boundaries_resize_and_rebuild() {
let mut heights = VariableHeightsFenwick::new(2, 130);
for idx in [0, 63, 64, 65, 127, 128, 129] {
heights.set(idx, 3);
}
assert_eq!(heights.unmeasured_count(), 123);
assert_eq!(heights.measured.len(), 3);
heights.resize(65);
assert_eq!(heights.unmeasured_count(), 62);
heights.resize(130);
for idx in 65..130 {
assert!(!heights.is_measured(idx), "stale bit at {idx}");
assert_eq!(heights.get(idx), 2);
}
heights.rebuild(&[4; 65]);
assert_eq!(heights.unmeasured_count(), 0);
assert!(heights.is_measured(64));
assert!(!heights.is_measured(65));
heights.resize(66);
assert!(!heights.is_measured(65));
heights.drop_front(64);
assert!(heights.is_measured(0));
assert!(!heights.is_measured(1));
assert_eq!(heights.get(0), 4);
assert_eq!(heights.get(1), 2);
heights.clear();
assert!(!heights.is_measured(0));
assert_eq!(heights.unmeasured_count(), 0);
assert!(heights.measured.is_empty());
}
#[test]
fn trimming_measured_rows_does_not_retrain_predictor() {
let mut heights =
VariableHeightsFenwick::new(1, 80).with_predictor(PredictorConfig::default());
for idx in 0..70 {
heights.set_in_category(idx, 5, 1);
}
let before = heights.predictor().unwrap().stats();
heights.drop_front(65);
assert_eq!(heights.predictor().unwrap().stats(), before);
assert_eq!(heights.unmeasured_count(), 10);
for idx in 0..5 {
assert!(heights.is_measured(idx));
assert_eq!(heights.get(idx), 5);
}
}
#[test]
fn variable_list_trains_categories_once_per_measurement() {
struct Row {
height: u16,
category: usize,
}
impl RenderItem for Row {
fn render(&self, area: Rect, frame: &mut Frame, _: bool, _: u16) {
for y in area.y..area.bottom() {
frame.buffer.set(area.x, y, Cell::from_char('x'));
}
}
fn height(&self) -> u16 {
self.height
}
fn category(&self) -> usize {
self.category
}
}
let mut items = [
Row {
height: 3,
category: 1,
},
Row {
height: 1,
category: 0,
},
];
let mut state =
VirtualizedListState::variable(2).with_predictor(PredictorConfig::default());
let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
let mut frame = Frame::new(10, 5, &mut pool);
let area = Rect::new(0, 0, 10, 5);
VirtualizedList::new(&items)
.variable_heights()
.render(area, &mut frame, &mut state);
assert_eq!(state.predictor_stats().unwrap().measurements, 2);
assert_eq!(state.predictor_stats().unwrap().categories, 2);
let predictor = state.heights().unwrap().predictor().unwrap();
assert_eq!(predictor.category_observations(1), 1);
assert_eq!(predictor.category_observations(0), 1);
assert_eq!(state.heights().unwrap().offset_of_item(1), 3);
assert_eq!(frame.buffer.get(0, 3).unwrap().content.as_char(), Some('x'));
assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some(' '));
VirtualizedList::new(&items)
.variable_heights()
.render(area, &mut frame, &mut state);
assert_eq!(state.predictor_stats().unwrap().measurements, 2);
items[0].height = 4;
VirtualizedList::new(&items)
.variable_heights()
.render(area, &mut frame, &mut state);
assert_eq!(state.predictor_stats().unwrap().measurements, 3);
assert_eq!(
state
.heights()
.unwrap()
.predictor()
.unwrap()
.category_observations(1),
2
);
VirtualizedList::new(&items[..0])
.variable_heights()
.render(area, &mut frame, &mut state);
assert_eq!(state.visible_count(), 0);
assert_eq!(state.scroll_offset(), 0);
assert!(state.heights().unwrap().is_empty());
assert_eq!(state.predictor_stats().unwrap().measurements, 3);
VirtualizedList::new(&items)
.variable_heights()
.render(area, &mut frame, &mut state);
assert_eq!(state.predictor_stats().unwrap().measurements, 5);
let mut owned = Virtualized::new(2)
.with_variable_heights(2)
.with_height_prediction(PredictorConfig::default());
owned.push(Row {
height: 4,
category: 1,
});
owned.measure(0, 4);
assert_eq!(owned.predictor_stats().unwrap().categories, 2);
assert_eq!(owned.predictor_stats().unwrap().measurements, 1);
assert!(owned.predicted_height(1) > owned.predicted_height(0));
}
#[test]
fn virtualized_list_variable_heights_renders_by_item_height() {
struct Tall(u16);
impl RenderItem for Tall {
fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
let glyph = char::from(b'0' + u8::try_from(self.0).unwrap_or(9));
for row in 0..area.height {
frame
.buffer
.set(area.x, area.y + row, Cell::from_char(glyph));
}
}
fn height(&self) -> u16 {
self.0
}
}
let column = |frame: &Frame| -> String {
(0..frame.buffer.height())
.map(|y| {
frame
.buffer
.get(0, y)
.and_then(|cell| cell.content.as_char())
.unwrap_or(' ')
})
.collect()
};
let items = [Tall(1), Tall(2), Tall(3), Tall(1), Tall(2)];
let list = VirtualizedList::new(&items)
.variable_heights()
.show_scrollbar(false);
let mut state = VirtualizedListState::new();
let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
let mut frame = Frame::new(4, 5, &mut pool);
StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
assert_eq!(column(&frame), "12233");
assert_eq!(state.visible_count(), 3);
let heights = state.heights().expect("tracker created by render");
assert_eq!(heights.get(1), 2);
assert!(heights.is_measured(2));
assert!(heights.is_measured(4) && heights.is_measured(3));
drop(frame);
state.select(Some(4));
let mut frame = Frame::new(4, 5, &mut pool);
StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
assert_eq!(state.scroll_offset(), 3);
assert_eq!(column(&frame), "122 ");
assert_eq!(state.visible_count(), 2);
let heights = state.heights().expect("tracker");
assert_eq!(heights.total_height(), 9);
assert_eq!(heights.offset_of_item(4), 7);
drop(frame);
state.measure(0, 3);
assert_eq!(state.heights().expect("tracker").offset_of_item(1), 3);
let list = VirtualizedList::new(&items).variable_heights();
let mut state = VirtualizedListState::new();
let mut frame = Frame::new(4, 5, &mut pool);
StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
assert!(
frame.buffer.get(3, 0).and_then(|c| c.content.as_char()) != Some('1'),
"the last column belongs to the scrollbar"
);
assert_eq!(column(&frame), "12233");
}
#[test]
fn fenwick_large_list_renders_selection_and_scroll_beyond_u32() {
#[derive(Clone, Copy)]
struct Row(u16, char);
impl RenderItem for Row {
fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip_rows: u16) {
for y in area.y..area.bottom() {
frame.buffer.set(area.x, y, Cell::from_char(self.1));
}
}
fn height(&self) -> u16 {
self.0
}
}
let mut items = vec![Row(u16::MAX, 'X'); 65_538];
items.extend([Row(1, '.'); 9]);
items.push(Row(1, 'Z'));
let list = VirtualizedList::new(&items).variable_heights();
let mut state = VirtualizedListState::new();
let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
{
let mut frame = Frame::new(4, 5, &mut pool);
StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
assert_eq!(frame.buffer.get(0, 0).unwrap().content.as_char(), Some('X'));
}
for (idx, row) in items.iter().enumerate() {
state.measure(idx, row.height());
}
assert_eq!(state.heights().unwrap().total_height(), u32::MAX);
state.select(Some(items.len() - 1));
{
let mut frame = Frame::new(4, 5, &mut pool);
StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
assert_eq!(state.scroll_offset(), items.len() - 5);
assert_eq!(state.visible_count(), 5);
let column: String = (0..5)
.map(|y| frame.buffer.get(0, y).unwrap().content.as_char().unwrap())
.collect();
assert_eq!(column, "....Z");
assert_ne!(frame.buffer.get(3, 4).unwrap().content.as_char(), Some('Z'));
}
state.select(None);
state.scroll_to_top();
{
let mut frame = Frame::new(4, 5, &mut pool);
StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
assert_eq!(state.scroll_offset(), 0);
assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('X'));
}
state.scroll_to_bottom(items.len());
let mut frame = Frame::new(4, 5, &mut pool);
StatefulWidget::render(&list, Rect::new(0, 0, 4, 5), &mut frame, &mut state);
assert_eq!(state.scroll_offset(), items.len() - 5);
assert_eq!(frame.buffer.get(0, 4).unwrap().content.as_char(), Some('Z'));
}
#[test]
fn virtualized_storage_debug() {
let storage: VirtualizedStorage<i32> = VirtualizedStorage::Owned(VecDeque::new());
let dbg = format!("{:?}", storage);
assert!(dbg.contains("Owned"));
let ext: VirtualizedStorage<i32> = VirtualizedStorage::External {
len: 100,
cache_capacity: 10,
};
let dbg = format!("{:?}", ext);
assert!(dbg.contains("External"));
}
#[test]
fn test_virtualized_list_handle_mouse_drag_smooth() {
use crate::scrollbar::SCROLLBAR_PART_THUMB;
use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
use ftui_render::frame::{HitId, HitRegion};
let mut state = VirtualizedListState::new();
let scrollbar_hit_id = HitId::new(1);
let total_items = 100;
let viewport_height = 10;
let fixed_height = 1;
let track_len = 10u64;
let track_pos = 0u64;
let hit_data = (SCROLLBAR_PART_THUMB << 56)
| ((track_len & 0x0FFF_FFFF) << 28)
| (track_pos & 0x0FFF_FFFF);
let down_event = MouseEvent::new(MouseEventKind::Down(MouseButton::Left), 0, 0);
let hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, hit_data));
state.handle_mouse(
&down_event,
hit,
scrollbar_hit_id,
total_items,
viewport_height,
fixed_height,
);
assert!(
state.scrollbar_drag_anchor.is_some(),
"Drag anchor should be set on down"
);
assert_eq!(
state.scrollbar_drag_anchor.unwrap(),
0,
"Anchor should be 0 (clicked top of thumb)"
);
let drag_pos = 1u64;
let drag_data = (SCROLLBAR_PART_THUMB << 56)
| ((track_len & 0x0FFF_FFFF) << 28)
| (drag_pos & 0x0FFF_FFFF);
let drag_event = MouseEvent::new(MouseEventKind::Drag(MouseButton::Left), 0, 1);
let drag_hit = Some((scrollbar_hit_id, HitRegion::Scrollbar, drag_data));
state.handle_mouse(
&drag_event,
drag_hit,
scrollbar_hit_id,
total_items,
viewport_height,
fixed_height,
);
assert_eq!(
state.scroll_offset, 10,
"Scroll offset should update smoothly"
);
}
#[test]
fn variable_height_mouse_scrolls_in_rows() {
use crate::scrollbar::SCROLLBAR_PART_TRACK;
use ftui_core::event::{MouseButton, MouseEvent, MouseEventKind};
use ftui_render::frame::{HitId, HitRegion};
struct Tall;
impl RenderItem for Tall {
fn render(&self, _area: Rect, _frame: &mut Frame, _selected: bool, _skip: u16) {}
fn height(&self) -> u16 {
6
}
}
let items = [Tall, Tall, Tall, Tall, Tall];
let list = VirtualizedList::new(&items).variable_heights();
let mut state = VirtualizedListState::new();
let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
let area = Rect::new(0, 0, 4, 5);
let mut frame = Frame::new(4, 5, &mut pool);
StatefulWidget::render(&list, area, &mut frame, &mut state);
let id = HitId::new(1);
let mouse = |state: &mut VirtualizedListState, kind, hit| {
state.handle_mouse(&MouseEvent::new(kind, 3, 4), hit, id, items.len(), 5, 1);
};
mouse(&mut state, MouseEventKind::ScrollDown, None);
assert_eq!(state.scroll_offset(), 1);
mouse(&mut state, MouseEventKind::ScrollUp, None);
assert_eq!(state.scroll_offset(), 0);
let track = (SCROLLBAR_PART_TRACK << 56) | (5 << 28) | 4;
mouse(
&mut state,
MouseEventKind::Down(MouseButton::Left),
Some((id, HitRegion::Scrollbar, track)),
);
assert_eq!(state.scroll_offset(), 4);
StatefulWidget::render(&list, area, &mut frame, &mut state);
assert_eq!(state.scroll_offset(), 4, "render keeps the offset");
}
#[test]
fn remeasure_policy_samples_when_voi_exceeds_cost() {
let mut high_voi = RemeasurePolicy::new(BetaPosterior::new(1.0, 1.0), 0.01, 2);
let decision = high_voi.should_sample(0);
assert!(
decision.is_some(),
"Beta(1,1) VOI (~0.0278) should exceed cost 0.01"
);
let mut low_voi = RemeasurePolicy::new(BetaPosterior::new(1.0, 200.0), 0.08, 2);
assert!(
low_voi.should_sample(0).is_none(),
"Beta(1,200) VOI should fall below cost 0.08"
);
}
#[test]
fn remeasure_policy_respects_min_interval() {
let mut policy = RemeasurePolicy::new(BetaPosterior::new(1.0, 1.0), 0.001, 4);
assert!(policy.should_sample(0).is_some(), "frame 0 should sample");
assert!(
policy.should_sample(1).is_none(),
"frame 1 within min_interval_frames=4 must be skipped"
);
assert!(
policy.should_sample(3).is_none(),
"frame 3 within min_interval_frames=4 must be skipped"
);
assert!(
policy.should_sample(4).is_some(),
"frame 4 at min_interval_frames=4 should sample"
);
}
#[test]
fn invalidate_clears_measured_bit() {
let mut fenwick = VariableHeightsFenwick::new(1, 4);
fenwick.set(2, 5);
assert!(fenwick.is_measured(2));
assert_eq!(fenwick.get(2), 5);
assert_eq!(fenwick.unmeasured_count(), 3);
fenwick.invalidate(2);
assert!(!fenwick.is_measured(2));
assert_eq!(fenwick.get(2), 1);
assert_eq!(fenwick.unmeasured_count(), 4);
}
#[test]
fn variable_heights_defaults_to_fenwick() {
let v: Virtualized<String> = Virtualized::new(16).with_variable_heights(2);
assert!(matches!(v.item_height(), ItemHeight::VariableFenwick(_)));
}
#[test]
fn offset_of_item_is_prefix_sum() {
let heights = [2u16, 5, 1, 4, 3, 6];
let fenwick = VariableHeightsFenwick::from_heights(&heights, 1);
let mut prefix = 0u32;
for (i, &h) in heights.iter().enumerate() {
assert_eq!(fenwick.offset_of_item(i), prefix);
prefix += u32::from(h);
}
assert_eq!(fenwick.total_height(), prefix);
}
#[test]
fn find_item_at_offset_round_trips() {
let heights = [3u16, 1, 4, 2, 5];
let fenwick = VariableHeightsFenwick::from_heights(&heights, 1);
for (i, &h) in heights.iter().enumerate() {
let start = fenwick.offset_of_item(i);
for off in start..start + u32::from(h) {
assert_eq!(fenwick.find_item_at_offset(off), i);
}
}
}
#[test]
fn variable_list_renders_multi_line_items_at_correct_rows() {
#[derive(Clone, Copy)]
struct MultiRow(u16, char);
impl RenderItem for MultiRow {
fn render(&self, area: Rect, frame: &mut Frame, _selected: bool, _skip: u16) {
for y in area.y..area.bottom() {
frame.buffer.set(area.x, y, Cell::from_char(self.1));
}
}
fn height(&self) -> u16 {
self.0
}
}
let items = [MultiRow(2, 'A'), MultiRow(3, 'B'), MultiRow(1, 'C')];
let list = VirtualizedList::new(&items)
.variable_heights()
.show_scrollbar(false);
let mut state = VirtualizedListState::new();
let mut pool = ftui_render::grapheme_pool::GraphemePool::new();
let mut frame = Frame::new(4, 6, &mut pool);
StatefulWidget::render(&list, Rect::new(0, 0, 4, 6), &mut frame, &mut state);
let col: String = (0..6)
.map(|y| frame.buffer.get(0, y).unwrap().content.as_char().unwrap())
.collect();
assert_eq!(col, "AABBBC");
}
#[test]
fn category_default_is_zero() {
assert_eq!(String::from("default").category(), 0);
}
#[test]
fn measured_bitset_tracks_set_and_rebuild() {
let mut fenwick = VariableHeightsFenwick::new(1, 10);
assert_eq!(fenwick.unmeasured_count(), 10);
fenwick.set(3, 4);
assert!(fenwick.is_measured(3));
assert!(!fenwick.is_measured(2));
assert_eq!(fenwick.unmeasured_count(), 9);
fenwick.rebuild(&[2; 10]);
assert_eq!(fenwick.unmeasured_count(), 0);
assert!(fenwick.is_measured(2));
}
mod scroll_stability_proptests {
use super::*;
use proptest::prelude::{ProptestConfig, any, prop_assert, proptest};
#[derive(Clone, Copy, Debug)]
struct CorpusRow {
height: u16,
category: usize,
}
impl RenderItem for CorpusRow {
fn render(&self, _area: Rect, _frame: &mut Frame, _selected: bool, _skip_rows: u16) {}
fn height(&self) -> u16 {
self.height
}
fn category(&self) -> usize {
self.category
}
}
fn generate_long_tail_corpus(n: usize, seed: u64) -> (Vec<CorpusRow>, Vec<usize>) {
let mut state = seed ^ 0x9E37_79B9_7F4A_7C15;
let mut next_u64 = || -> u64 {
state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
state
};
let mut rows = Vec::with_capacity(n);
for _ in 0..n {
let bucket = (next_u64() >> 32) % 100;
let (height, category) = if bucket < 80 {
(1u16, 0usize)
} else if bucket < 95 {
let r = next_u64();
let h = 2 + (((r >> 32) % 2) + ((r >> 48) % 2)) as u16; (h, 1usize)
} else {
let r = next_u64();
let tier = ((r >> 48) % 3) as usize;
let jitter = (((r & 0xFF) % 3) + (((r >> 8) & 0xFF) % 3)) as u16; let h = match tier {
0 => 6 + jitter, 1 => 15 + jitter, _ => 25 + jitter, };
(h, 2 + tier)
};
rows.push(CorpusRow { height, category });
}
let mut perm: Vec<usize> = (0..n).collect();
for idx in (1..n).rev() {
let swap_idx = (next_u64() as usize) % (idx + 1);
perm.swap(idx, swap_idx);
}
let train_count = (n / 10).max(1);
let mut swap_pos = 0usize;
for target_cat in 1..=4usize {
let mut seen = perm[..train_count]
.iter()
.filter(|&&idx| rows[idx].category == target_cat)
.count();
for pos in train_count..n {
if seen >= 4 || swap_pos >= train_count {
break;
}
if rows[perm[pos]].category == target_cat {
while swap_pos < train_count && rows[perm[swap_pos]].category != 0 {
swap_pos += 1;
}
if swap_pos < train_count {
perm.swap(swap_pos, pos);
seen += 1;
swap_pos += 1;
}
}
}
}
(rows, perm)
}
proptest! {
#![proptest_config(ProptestConfig { cases: 256, ..ProptestConfig::default() })]
#[test]
fn scroll_to_index_is_stable_under_late_measurements(
n in 500usize..5000,
seed in any::<u64>(),
target_frac in 0usize..10_000,
) {
let min_target = n / 4;
let i = min_target + (target_frac % (n - min_target).max(1));
let (rows, perm) = generate_long_tail_corpus(n, seed);
let total_true_sum: u64 = rows.iter().map(|r| u64::from(r.height)).sum();
let mean_height = ((total_true_sum as f64) / (n as f64)).round().max(1.0) as u16;
let true_offset: u32 = rows[..i].iter().map(|r| u32::from(r.height)).sum();
let mut pred_list: Virtualized<CorpusRow> = Virtualized::new(n)
.with_variable_heights(1)
.with_height_predictor(PredictorConfig::default());
let mut base_list: Virtualized<CorpusRow> = Virtualized::new(n)
.with_variable_heights(mean_height);
for &row in &rows {
pred_list.push(row);
base_list.push(row);
}
let train_count = (n / 10).max(1);
for &idx in &perm[..train_count] {
let h = rows[idx].height;
pred_list.measure(idx, h);
base_list.observe_height(idx, h);
}
pred_list.scroll_to(i);
base_list.scroll_to(i);
let mut prev_pred_offset = pred_list.offset_of_item(i);
let mut prev_base_offset = base_list.offset_of_item(i);
let mut jump_predictor = 0u64;
let mut jump_mean_baseline = 0u64;
for chunk in perm[train_count..].chunks(50) {
for &idx in chunk {
let h = rows[idx].height;
pred_list.measure(idx, h);
base_list.observe_height(idx, h);
}
let next_pred_offset = pred_list.offset_of_item(i);
let next_base_offset = base_list.offset_of_item(i);
jump_predictor += u64::from(next_pred_offset.abs_diff(prev_pred_offset));
jump_mean_baseline += u64::from(next_base_offset.abs_diff(prev_base_offset));
prev_pred_offset = next_pred_offset;
prev_base_offset = next_base_offset;
}
let final_offset = pred_list.offset_of_item(i);
let cat = rows[i].category;
let (lower, upper) = match pred_list.item_height() {
ItemHeight::VariableFenwick(t) => t
.predictor()
.map_or((1, 1), |p| {
let b = p.predict(cat);
(b.lower, b.upper)
}),
_ => (1, 1),
};
let bound_width = u32::from(upper.saturating_sub(lower));
prop_assert!(
final_offset.abs_diff(true_offset) <= bound_width,
"seed={seed} n={n} i={i} final_offset={final_offset} true_offset={true_offset} bounds=[{lower}, {upper}]"
);
prop_assert!(
jump_predictor <= jump_mean_baseline,
"seed={seed} n={n} i={i} jump_predictor={jump_predictor} > jump_mean_baseline={jump_mean_baseline} bounds=[{lower}, {upper}]"
);
}
}
}
}