1use crate::{
2 geometry::{
3 rect::RectF,
4 vector::{vec2f, Vector2F},
5 },
6 json::json,
7 sum_tree::{self, Bias, SumTree},
8 DebugContext, Element, ElementBox, ElementRc, Event, EventContext, LayoutContext, PaintContext,
9 SizeConstraint,
10};
11use std::{cell::RefCell, ops::Range, rc::Rc};
12
13pub struct List {
14 state: ListState,
15}
16
17#[derive(Clone)]
18pub struct ListState(Rc<RefCell<StateInner>>);
19
20#[derive(Clone, Copy, Debug, Eq, PartialEq)]
21pub enum Orientation {
22 Top,
23 Bottom,
24}
25
26struct StateInner {
27 last_layout_width: Option<f32>,
28 render_item: Box<dyn FnMut(usize, &mut LayoutContext) -> ElementBox>,
29 rendered_range: Range<usize>,
30 items: SumTree<ListItem>,
31 scroll_top: Option<ScrollTop>,
32 orientation: Orientation,
33 overdraw: usize,
34 scroll_handler: Option<Box<dyn FnMut(Range<usize>, &mut EventContext)>>,
35}
36
37#[derive(Clone, Copy, Debug, Default, PartialEq)]
38pub struct ScrollTop {
39 item_ix: usize,
40 offset_in_item: f32,
41}
42
43#[derive(Clone)]
44enum ListItem {
45 Unrendered,
46 Rendered(ElementRc),
47 Removed(f32),
48}
49
50impl std::fmt::Debug for ListItem {
51 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
52 match self {
53 Self::Unrendered => write!(f, "Unrendered"),
54 Self::Rendered(_) => f.debug_tuple("Rendered").finish(),
55 Self::Removed(height) => f.debug_tuple("Removed").field(height).finish(),
56 }
57 }
58}
59
60#[derive(Clone, Debug, Default, PartialEq)]
61struct ListItemSummary {
62 count: usize,
63 rendered_count: usize,
64 unrendered_count: usize,
65 height: f32,
66}
67
68#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
69struct Count(usize);
70
71#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
72struct RenderedCount(usize);
73
74#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
75struct UnrenderedCount(usize);
76
77#[derive(Clone, Debug, Default)]
78struct Height(f32);
79
80impl List {
81 pub fn new(state: ListState) -> Self {
82 Self { state }
83 }
84}
85
86impl Element for List {
87 type LayoutState = ScrollTop;
88 type PaintState = ();
89
90 fn layout(
91 &mut self,
92 constraint: SizeConstraint,
93 cx: &mut LayoutContext,
94 ) -> (Vector2F, Self::LayoutState) {
95 let state = &mut *self.state.0.borrow_mut();
96 let size = constraint.max;
97 let mut item_constraint = constraint;
98 item_constraint.min.set_y(0.);
99 item_constraint.max.set_y(f32::INFINITY);
100
101 if state.last_layout_width != Some(constraint.max.x()) {
102 state.rendered_range = 0..0;
103 state.items = SumTree::from_iter(
104 (0..state.items.summary().count).map(|_| ListItem::Unrendered),
105 &(),
106 )
107 }
108
109 let overdraw = state.overdraw;
110 let old_rendered_range = state.rendered_range.clone();
111 let old_items = state.items.clone();
112 let orientation = state.orientation;
113 let stored_scroll_top = state.scroll_top;
114 let mut new_items = SumTree::new();
115
116 let mut render_item = |ix, old_item: &ListItem| {
117 let element = if let ListItem::Rendered(element) = old_item {
118 element.clone()
119 } else {
120 let mut element = (state.render_item)(ix, cx);
121 element.layout(item_constraint, cx);
122 element.into()
123 };
124 element
125 };
126
127 // Determine the scroll top. When parked at the end of a bottom-oriented
128 // list, this requires rendering items starting from the end of the list
129 // until the visible region is full. In other cases, the stored scroll
130 // can be used.
131 let scroll_top;
132 let trailing_items;
133 if let (Orientation::Bottom, None) = (orientation, stored_scroll_top) {
134 let mut rendered_height = 0.;
135 let mut cursor = old_items.cursor::<Count, ()>();
136
137 let mut visible_items = Vec::new();
138 cursor.seek(&Count(old_items.summary().count), Bias::Left, &());
139 while let Some(item) = cursor.item() {
140 if rendered_height >= size.y() {
141 break;
142 }
143
144 let element = render_item(cursor.seek_start().0, item);
145 rendered_height += element.size().y();
146 visible_items.push(ListItem::Rendered(element));
147 cursor.prev(&());
148 }
149
150 scroll_top = ScrollTop {
151 item_ix: cursor.seek_start().0,
152 offset_in_item: rendered_height - size.y(),
153 };
154 visible_items.reverse();
155 trailing_items = Some(visible_items);
156 } else {
157 scroll_top = stored_scroll_top.unwrap_or_default();
158 trailing_items = None;
159 }
160
161 let new_rendered_range_start = scroll_top.item_ix.saturating_sub(overdraw);
162 let mut cursor = old_items.cursor::<Count, ()>();
163
164 // Discard any rendered elements before the overdraw window.
165 if old_rendered_range.start < new_rendered_range_start {
166 new_items.push_tree(
167 cursor.slice(&Count(old_rendered_range.start), Bias::Right, &()),
168 &(),
169 );
170 let remove_to = old_rendered_range.end.min(new_rendered_range_start);
171 while cursor.seek_start().0 < remove_to {
172 new_items.push(cursor.item().unwrap().remove(), &());
173 cursor.next(&());
174 }
175 }
176
177 new_items.push_tree(
178 cursor.slice(&Count(new_rendered_range_start), Bias::Right, &()),
179 &(),
180 );
181
182 // Ensure that all items in the overdraw window before the visible range are rendered.
183 while cursor.seek_start().0 < scroll_top.item_ix {
184 new_items.push(
185 ListItem::Rendered(render_item(cursor.seek_start().0, cursor.item().unwrap())),
186 &(),
187 );
188 cursor.next(&());
189 }
190
191 // The remaining items may have already been rendered, when parked at the
192 // end of a bottom-oriented list. If so, append them.
193 let new_rendered_range_end;
194 if let Some(trailing_items) = trailing_items {
195 new_rendered_range_end = new_rendered_range_start + trailing_items.len();
196 new_items.extend(trailing_items, &());
197 } else {
198 // Ensure that enough items are rendered to fill the visible range.
199 let mut rendered_top = -scroll_top.offset_in_item;
200 while let Some(item) = cursor.item() {
201 if rendered_top >= size.y() {
202 break;
203 }
204
205 let element = render_item(cursor.seek_start().0, item);
206 rendered_top += element.size().y();
207 new_items.push(ListItem::Rendered(element), &());
208 cursor.next(&());
209 }
210
211 // Ensure that all items in the overdraw window after the visible range
212 // are rendered.
213 new_rendered_range_end =
214 (cursor.seek_start().0 + overdraw).min(old_items.summary().count);
215 while cursor.seek_start().0 < new_rendered_range_end {
216 new_items.push(
217 ListItem::Rendered(render_item(cursor.seek_start().0, cursor.item().unwrap())),
218 &(),
219 );
220 cursor.next(&());
221 }
222
223 // Preserve the remainder of the items, but discard any rendered items after
224 // the overdraw window.
225 if cursor.seek_start().0 < old_rendered_range.start {
226 new_items.push_tree(
227 cursor.slice(&Count(old_rendered_range.start), Bias::Right, &()),
228 &(),
229 );
230 }
231 while cursor.seek_start().0 < old_rendered_range.end {
232 new_items.push(cursor.item().unwrap().remove(), &());
233 cursor.next(&());
234 }
235 new_items.push_tree(cursor.suffix(&()), &());
236 }
237
238 drop(cursor);
239 state.items = new_items;
240 state.rendered_range = new_rendered_range_start..new_rendered_range_end;
241 state.last_layout_width = Some(size.x());
242 (size, scroll_top)
243 }
244
245 fn paint(&mut self, bounds: RectF, scroll_top: &mut ScrollTop, cx: &mut PaintContext) {
246 cx.scene.push_layer(Some(bounds));
247
248 let state = &mut *self.state.0.borrow_mut();
249 for (mut element, origin) in state.visible_elements(bounds, scroll_top) {
250 element.paint(origin, cx);
251 }
252
253 cx.scene.pop_layer();
254 }
255
256 fn dispatch_event(
257 &mut self,
258 event: &Event,
259 bounds: RectF,
260 scroll_top: &mut ScrollTop,
261 _: &mut (),
262 cx: &mut EventContext,
263 ) -> bool {
264 let mut handled = false;
265
266 let mut state = self.state.0.borrow_mut();
267 for (mut element, _) in state.visible_elements(bounds, scroll_top) {
268 handled = element.dispatch_event(event, cx) || handled;
269 }
270
271 match event {
272 Event::ScrollWheel {
273 position,
274 delta,
275 precise,
276 } => {
277 if bounds.contains_point(*position) {
278 if state.scroll(scroll_top, bounds.height(), *delta, *precise, cx) {
279 handled = true;
280 }
281 }
282 }
283 _ => {}
284 }
285
286 handled
287 }
288
289 fn debug(
290 &self,
291 bounds: RectF,
292 scroll_top: &Self::LayoutState,
293 _: &(),
294 cx: &DebugContext,
295 ) -> serde_json::Value {
296 let state = self.state.0.borrow_mut();
297 let visible_elements = state
298 .visible_elements(bounds, scroll_top)
299 .map(|e| e.0.debug(cx))
300 .collect::<Vec<_>>();
301 let visible_range = scroll_top.item_ix..(scroll_top.item_ix + visible_elements.len());
302 json!({
303 "visible_range": visible_range,
304 "visible_elements": visible_elements,
305 "scroll_top": state.scroll_top.map(|top| (top.item_ix, top.offset_in_item)),
306 })
307 }
308}
309
310impl ListState {
311 pub fn new<F>(
312 element_count: usize,
313 orientation: Orientation,
314 min_overdraw: usize,
315 render_item: F,
316 ) -> Self
317 where
318 F: 'static + FnMut(usize, &mut LayoutContext) -> ElementBox,
319 {
320 let mut items = SumTree::new();
321 items.extend((0..element_count).map(|_| ListItem::Unrendered), &());
322 Self(Rc::new(RefCell::new(StateInner {
323 last_layout_width: None,
324 render_item: Box::new(render_item),
325 rendered_range: 0..0,
326 items,
327 scroll_top: None,
328 orientation,
329 overdraw: min_overdraw,
330 scroll_handler: None,
331 })))
332 }
333
334 pub fn reset(&self, element_count: usize) {
335 let state = &mut *self.0.borrow_mut();
336 state.scroll_top = None;
337 state.items = SumTree::new();
338 state
339 .items
340 .extend((0..element_count).map(|_| ListItem::Unrendered), &());
341 }
342
343 pub fn splice(&self, old_range: Range<usize>, count: usize) {
344 let state = &mut *self.0.borrow_mut();
345
346 if let Some(ScrollTop {
347 item_ix,
348 offset_in_item,
349 }) = state.scroll_top.as_mut()
350 {
351 if old_range.contains(item_ix) {
352 *item_ix = old_range.start;
353 *offset_in_item = 0.;
354 } else if old_range.end <= *item_ix {
355 *item_ix = *item_ix - (old_range.end - old_range.start) + count;
356 }
357 }
358
359 let new_end = old_range.start + count;
360 if old_range.start < state.rendered_range.start {
361 state.rendered_range.start =
362 new_end + state.rendered_range.start.saturating_sub(old_range.end);
363 }
364 if old_range.start < state.rendered_range.end {
365 state.rendered_range.end =
366 new_end + state.rendered_range.end.saturating_sub(old_range.end);
367 }
368
369 let mut old_heights = state.items.cursor::<Count, ()>();
370 let mut new_heights = old_heights.slice(&Count(old_range.start), Bias::Right, &());
371 old_heights.seek_forward(&Count(old_range.end), Bias::Right, &());
372
373 new_heights.extend((0..count).map(|_| ListItem::Unrendered), &());
374 new_heights.push_tree(old_heights.suffix(&()), &());
375 drop(old_heights);
376 state.items = new_heights;
377 }
378
379 pub fn set_scroll_handler(
380 &mut self,
381 handler: impl FnMut(Range<usize>, &mut EventContext) + 'static,
382 ) {
383 self.0.borrow_mut().scroll_handler = Some(Box::new(handler))
384 }
385}
386
387impl StateInner {
388 fn visible_range(&self, height: f32, scroll_top: &ScrollTop) -> Range<usize> {
389 let mut cursor = self.items.cursor::<Count, Height>();
390 cursor.seek(&Count(scroll_top.item_ix), Bias::Right, &());
391 let start_y = cursor.sum_start().0 + scroll_top.offset_in_item;
392 let mut cursor = cursor.swap_dimensions();
393 cursor.seek_forward(&Height(start_y + height), Bias::Left, &());
394 scroll_top.item_ix..cursor.sum_start().0 + 1
395 }
396
397 fn visible_elements<'a>(
398 &'a self,
399 bounds: RectF,
400 scroll_top: &ScrollTop,
401 ) -> impl Iterator<Item = (ElementRc, Vector2F)> + 'a {
402 let mut item_origin = bounds.origin() - vec2f(0., scroll_top.offset_in_item);
403 let mut cursor = self.items.cursor::<Count, ()>();
404 cursor.seek(&Count(scroll_top.item_ix), Bias::Right, &());
405 std::iter::from_fn(move || {
406 while let Some(item) = cursor.item() {
407 if item_origin.y() > bounds.max_y() {
408 break;
409 }
410
411 if let ListItem::Rendered(element) = item {
412 let result = (element.clone(), item_origin);
413 item_origin.set_y(item_origin.y() + element.size().y());
414 cursor.next(&());
415 return Some(result);
416 }
417
418 cursor.next(&());
419 }
420
421 None
422 })
423 }
424
425 fn scroll(
426 &mut self,
427 scroll_top: &ScrollTop,
428 height: f32,
429 mut delta: Vector2F,
430 precise: bool,
431 cx: &mut EventContext,
432 ) -> bool {
433 if !precise {
434 delta *= 20.;
435 }
436
437 let scroll_max = (self.items.summary().height - height).max(0.);
438 let new_scroll_top = (self.scroll_top(height) + delta.y())
439 .max(0.)
440 .min(scroll_max);
441
442 if self.orientation == Orientation::Bottom && new_scroll_top == scroll_max {
443 self.scroll_top = None;
444 } else {
445 let mut cursor = self.items.cursor::<Height, Count>();
446 cursor.seek(&Height(new_scroll_top), Bias::Right, &());
447 let item_ix = cursor.sum_start().0;
448 let offset_in_item = new_scroll_top - cursor.seek_start().0;
449 self.scroll_top = Some(ScrollTop {
450 item_ix,
451 offset_in_item,
452 });
453 }
454
455 if self.scroll_handler.is_some() {
456 let visible_range = self.visible_range(height, scroll_top);
457 self.scroll_handler.as_mut().unwrap()(visible_range, cx);
458 }
459 cx.notify();
460
461 true
462 }
463
464 fn scroll_top(&self, height: f32) -> f32 {
465 let scroll_max = (self.items.summary().height - height).max(0.);
466 if let Some(ScrollTop {
467 item_ix,
468 offset_in_item,
469 }) = self.scroll_top
470 {
471 let mut cursor = self.items.cursor::<Count, Height>();
472 cursor.seek(&Count(item_ix), Bias::Right, &());
473 (cursor.sum_start().0 + offset_in_item).min(scroll_max)
474 } else {
475 match self.orientation {
476 Orientation::Top => 0.,
477 Orientation::Bottom => scroll_max,
478 }
479 }
480 }
481}
482
483impl ListItem {
484 fn remove(&self) -> Self {
485 match self {
486 ListItem::Unrendered => ListItem::Unrendered,
487 ListItem::Rendered(element) => ListItem::Removed(element.size().y()),
488 ListItem::Removed(height) => ListItem::Removed(*height),
489 }
490 }
491}
492
493impl sum_tree::Item for ListItem {
494 type Summary = ListItemSummary;
495
496 fn summary(&self) -> Self::Summary {
497 match self {
498 ListItem::Unrendered => ListItemSummary {
499 count: 1,
500 rendered_count: 0,
501 unrendered_count: 1,
502 height: 0.,
503 },
504 ListItem::Rendered(element) => ListItemSummary {
505 count: 1,
506 rendered_count: 1,
507 unrendered_count: 0,
508 height: element.size().y(),
509 },
510 ListItem::Removed(height) => ListItemSummary {
511 count: 1,
512 rendered_count: 0,
513 unrendered_count: 1,
514 height: *height,
515 },
516 }
517 }
518}
519
520impl sum_tree::Summary for ListItemSummary {
521 type Context = ();
522
523 fn add_summary(&mut self, summary: &Self, _: &()) {
524 self.count += summary.count;
525 self.rendered_count += summary.rendered_count;
526 self.unrendered_count += summary.unrendered_count;
527 self.height += summary.height;
528 }
529}
530
531impl<'a> sum_tree::Dimension<'a, ListItemSummary> for ListItemSummary {
532 fn add_summary(&mut self, summary: &'a ListItemSummary, _: &()) {
533 sum_tree::Summary::add_summary(self, summary, &());
534 }
535}
536
537impl<'a> sum_tree::Dimension<'a, ListItemSummary> for Count {
538 fn add_summary(&mut self, summary: &'a ListItemSummary, _: &()) {
539 self.0 += summary.count;
540 }
541}
542
543impl<'a> sum_tree::Dimension<'a, ListItemSummary> for RenderedCount {
544 fn add_summary(&mut self, summary: &'a ListItemSummary, _: &()) {
545 self.0 += summary.rendered_count;
546 }
547}
548
549impl<'a> sum_tree::Dimension<'a, ListItemSummary> for UnrenderedCount {
550 fn add_summary(&mut self, summary: &'a ListItemSummary, _: &()) {
551 self.0 += summary.unrendered_count;
552 }
553}
554
555impl<'a> sum_tree::Dimension<'a, ListItemSummary> for Height {
556 fn add_summary(&mut self, summary: &'a ListItemSummary, _: &()) {
557 self.0 += summary.height;
558 }
559}
560
561impl<'a> sum_tree::SeekDimension<'a, ListItemSummary> for Height {
562 fn cmp(&self, other: &Self, _: &()) -> std::cmp::Ordering {
563 self.0.partial_cmp(&other.0).unwrap()
564 }
565}
566
567#[cfg(test)]
568mod tests {
569 use super::*;
570 use crate::{elements::*, geometry::vector::vec2f, Entity, RenderContext, View};
571
572 #[crate::test(self)]
573 fn test_layout(cx: &mut crate::MutableAppContext) {
574 let mut presenter = cx.build_presenter(0, 0.);
575
576 let elements = Rc::new(RefCell::new(vec![20., 30., 100.]));
577 let state = ListState::new(elements.borrow().len(), Orientation::Top, 1000, {
578 let elements = elements.clone();
579 move |ix, _| item(elements.borrow()[ix])
580 });
581
582 let mut list = List::new(state.clone()).boxed();
583 let size = list.layout(
584 SizeConstraint::new(vec2f(0., 0.), vec2f(100., 40.)),
585 &mut presenter.build_layout_context(cx),
586 );
587 assert_eq!(size, vec2f(100., 40.));
588 assert_eq!(
589 state.0.borrow().items.summary(),
590 ListItemSummary {
591 count: 3,
592 rendered_count: 3,
593 unrendered_count: 0,
594 height: 150.
595 }
596 );
597
598 state.0.borrow_mut().scroll(
599 &ScrollTop {
600 item_ix: 0,
601 offset_in_item: 0.,
602 },
603 40.,
604 vec2f(0., 54.),
605 true,
606 &mut presenter.build_event_context(cx),
607 );
608 assert_eq!(
609 state.0.borrow().scroll_top,
610 Some(ScrollTop {
611 item_ix: 2,
612 offset_in_item: 4.
613 })
614 );
615 assert_eq!(state.0.borrow().scroll_top(size.y()), 54.);
616
617 elements.borrow_mut().splice(1..2, vec![40., 50.]);
618 elements.borrow_mut().push(60.);
619 state.splice(1..2, 2);
620 state.splice(4..4, 1);
621 assert_eq!(
622 state.0.borrow().items.summary(),
623 ListItemSummary {
624 count: 5,
625 rendered_count: 2,
626 unrendered_count: 3,
627 height: 120.
628 }
629 );
630
631 let mut list = List::new(state.clone()).boxed();
632 let size = list.layout(
633 SizeConstraint::new(vec2f(0., 0.), vec2f(100., 40.)),
634 &mut presenter.build_layout_context(cx),
635 );
636 assert_eq!(size, vec2f(100., 40.));
637 assert_eq!(
638 state.0.borrow().items.summary(),
639 ListItemSummary {
640 count: 5,
641 rendered_count: 5,
642 unrendered_count: 0,
643 height: 270.
644 }
645 );
646 assert_eq!(
647 state.0.borrow().scroll_top,
648 Some(ScrollTop {
649 item_ix: 3,
650 offset_in_item: 4.
651 })
652 );
653 assert_eq!(state.0.borrow().scroll_top(size.y()), 114.);
654 }
655
656 fn item(height: f32) -> ElementBox {
657 ConstrainedBox::new(Empty::new().boxed())
658 .with_height(height)
659 .with_width(100.)
660 .boxed()
661 }
662
663 struct TestView;
664
665 impl Entity for TestView {
666 type Event = ();
667 }
668
669 impl View for TestView {
670 fn ui_name() -> &'static str {
671 "TestView"
672 }
673
674 fn render(&mut self, _: &mut RenderContext<'_, Self>) -> ElementBox {
675 unimplemented!()
676 }
677 }
678}