telar_ui_core/virtual_list.rs
1use geometry_core::Rect;
2use layout_core::{LayoutError, LayoutStyle};
3use renderer_core::RectStyle;
4use std::hash::Hash;
5
6use crate::layout_item::LayoutItem;
7use crate::reactive_list::ReactiveList;
8use crate::scroll_area::ScrollViewport;
9use crate::styled_container::StyledContainer;
10
11/// Which slice of a long list is worth building, given where the viewport currently is.
12///
13/// Returned as a half-open `[first, last)` over item indices. `overscan` rows are added on each side so a
14/// scroll reveals a row that already exists rather than one built during the frame it appears — the difference
15/// between a list that scrolls and one that hitches at every boundary.
16///
17/// A row height of zero (or a viewport not yet laid out) yields the whole range: a virtual list that guessed
18/// "nothing is visible" from a missing measurement would render an empty list on its first frame, which reads
19/// as a bug rather than as a not-yet-measured layout.
20pub fn visible_window(
21 offset: f32,
22 viewport_height: f32,
23 row_height: f32,
24 count: usize,
25 overscan: usize,
26) -> (usize, usize) {
27 if row_height <= 0.0 || viewport_height <= 0.0 || count == 0 {
28 return (0, count);
29 }
30 let first_visible = (offset / row_height).floor().max(0.0) as usize;
31 let rows_on_screen = (viewport_height / row_height).ceil() as usize + 1;
32 let first = first_visible.saturating_sub(overscan);
33 let last = first_visible
34 .saturating_add(rows_on_screen)
35 .saturating_add(overscan)
36 .min(count);
37 (first.min(count), last)
38}
39
40/// One row of a virtualised list, or the space standing in for the rows that were not built.
41enum Slot<Item> {
42 /// The run of skipped rows above or below the window, as a single box of their combined height. Keeping
43 /// the scrollable content the full height is what makes the scrollbar and the wheel behave as if every row
44 /// were there — which, as far as the user is concerned, they are.
45 Gap {
46 before: bool,
47 height: f32,
48 },
49 Row(usize, Item),
50}
51
52/// A keyed list that builds only the rows currently on screen.
53///
54/// [`ReactiveList`] builds every item it is given, which is right until the list is long: a wallpaper grid or a
55/// full application list pays for thousands of widgets to show a dozen. This builds the visible window plus a
56/// little overscan and represents the rest as two spacer boxes, so the content keeps its true height and the
57/// scrollbar keeps telling the truth.
58///
59/// **Fixed row height.** Every row must be `row_height` tall, because the window is computed by division
60/// rather than by measurement — measuring rows that have not been built is the circular problem variable-height
61/// virtualisation exists to solve, and it needs a size cache and an estimation pass this does not have. A list
62/// whose rows genuinely vary belongs in a plain [`ReactiveList`] until that lands.
63///
64/// `source` still returns every item. That is deliberate: producing a `Vec` of plain data is cheap, and the
65/// expensive part — constructing widgets, decoding images, laying out text — is what this defers. A source that
66/// is itself expensive should be memoised by the caller, as it would be for any list.
67pub struct VirtualList;
68
69impl VirtualList {
70 /// `viewport` is the enclosing scroll area's live window (see [`crate::LayoutScrollArea::new_with`]).
71 /// `build` constructs one row and receives its index alongside the item, since a virtualised row often
72 /// wants to know where it sits.
73 pub fn new<Item, Key, S, K, B>(
74 container_style: LayoutStyle,
75 viewport: ScrollViewport,
76 row_height: f32,
77 overscan: usize,
78 source: S,
79 key: K,
80 build: B,
81 ) -> Result<ReactiveList, LayoutError>
82 where
83 Key: Hash + 'static,
84 Item: 'static,
85 S: Fn() -> Vec<Item> + 'static,
86 K: Fn(&Item) -> Key + 'static,
87 B: Fn(usize, Item) -> Result<Box<dyn LayoutItem>, LayoutError> + 'static,
88 {
89 let (_, offset_y) = viewport.offset();
90 let rect = viewport.rect();
91 let windowed = move || {
92 let items = source();
93 let count = items.len();
94 let (first, last) = visible_window(
95 offset_y.get(),
96 rect.get().height,
97 row_height,
98 count,
99 overscan,
100 );
101 let mut slots: Vec<Slot<Item>> = Vec::with_capacity(last - first + 2);
102 if first > 0 {
103 slots.push(Slot::Gap {
104 before: true,
105 height: first as f32 * row_height,
106 });
107 }
108 slots.extend(
109 items
110 .into_iter()
111 .enumerate()
112 .skip(first)
113 .take(last - first)
114 .map(|(at, item)| Slot::Row(at, item)),
115 );
116 if last < count {
117 slots.push(Slot::Gap {
118 before: false,
119 height: (count - last) as f32 * row_height,
120 });
121 }
122 slots
123 };
124
125 // A gap keys on its height so a scroll that changes it rebuilds the spacer; a row keys on the caller's own key *and* its index, because the same item at a different index sits at a different height and reusing the node would leave it drawn in the old place.
126 let keyer = move |slot: &Slot<Item>| match slot {
127 Slot::Gap { before, height } => format!("gap:{before}:{height}"),
128 Slot::Row(at, item) => {
129 let mut hasher = std::collections::hash_map::DefaultHasher::new();
130 key(item).hash(&mut hasher);
131 format!("row:{at}:{}", std::hash::Hasher::finish(&hasher))
132 }
133 };
134
135 ReactiveList::with_style(container_style, windowed, keyer, move |slot| match slot {
136 Slot::Gap { height, .. } => Ok(Box::new(StyledContainer::new(
137 LayoutStyle::new().height(height).flex_shrink(0.0),
138 |_: Rect| RectStyle::default(),
139 Vec::new(),
140 )?) as Box<dyn LayoutItem>),
141 Slot::Row(at, item) => build(at, item),
142 })
143 }
144}
145
146#[cfg(test)]
147mod tests {
148 use super::*;
149
150 #[test]
151 fn the_window_covers_the_screen_plus_its_overscan() {
152 // 20px rows, a 100px window: five rows fit, and the partial sixth is always included.
153 let (first, last) = visible_window(0.0, 100.0, 20.0, 1000, 0);
154 assert_eq!((first, last), (0, 6));
155
156 // Scrolled to row 10, with two rows of overscan on each side.
157 let (first, last) = visible_window(200.0, 100.0, 20.0, 1000, 2);
158 assert_eq!((first, last), (8, 18));
159
160 // A partial scroll floors to the row actually on screen rather than rounding past it.
161 let (first, _) = visible_window(199.0, 100.0, 20.0, 1000, 0);
162 assert_eq!(first, 9, "row 9 is still showing its last pixel");
163 }
164
165 #[test]
166 fn the_window_is_clamped_at_both_ends() {
167 // At the very top, overscan cannot go negative.
168 assert_eq!(visible_window(0.0, 100.0, 20.0, 1000, 5), (0, 11));
169 // At the bottom, it cannot run past the list.
170 assert_eq!(visible_window(19_800.0, 100.0, 20.0, 1000, 5), (985, 1000));
171 // A scroll offset past the end (a list that shrank under the viewport) still yields a valid range.
172 let (first, last) = visible_window(100_000.0, 100.0, 20.0, 10, 0);
173 assert!(first <= last && last <= 10, "got {first}..{last}");
174 }
175
176 #[test]
177 fn an_unmeasured_viewport_renders_everything_rather_than_nothing() {
178 // The first frame, before layout has given the scroll area a height: showing nothing would look like a broken list, and showing everything is exactly what a plain ReactiveList would have done.
179 assert_eq!(visible_window(0.0, 0.0, 20.0, 40, 0), (0, 40));
180 assert_eq!(visible_window(0.0, 100.0, 0.0, 40, 0), (0, 40));
181 assert_eq!(
182 visible_window(0.0, 100.0, 20.0, 0, 0),
183 (0, 0),
184 "an empty list is empty"
185 );
186 }
187}