1#![allow(missing_docs)]
2use crate::core::event::{self, Event};
3use crate::core::layout;
4use crate::core::mouse;
5use crate::core::overlay;
6use crate::core::renderer;
7use crate::core::widget;
8use crate::core::widget::tree::{self, Tree};
9use crate::core::window;
10use crate::core::{
11 self, Clipboard, Element, Layout, Length, Pixels, Point, Rectangle, Shell,
12 Size, Vector, Widget,
13};
14
15use std::cell::RefCell;
16use std::cmp::Ordering;
17use std::collections::VecDeque;
18
19#[allow(missing_debug_implementations)]
20pub struct List<'a, T, Message, Theme, Renderer> {
21 content: &'a Content<T>,
22 spacing: f32,
23 view_item:
24 Box<dyn Fn(usize, &'a T) -> Element<'a, Message, Theme, Renderer> + 'a>,
25 visible_elements: Vec<Element<'a, Message, Theme, Renderer>>,
26}
27
28impl<'a, T, Message, Theme, Renderer> List<'a, T, Message, Theme, Renderer> {
29 pub fn new(
30 content: &'a Content<T>,
31 view_item: impl Fn(usize, &'a T) -> Element<'a, Message, Theme, Renderer>
32 + 'a,
33 ) -> Self {
34 Self {
35 content,
36 spacing: 0.0,
37 view_item: Box::new(view_item),
38 visible_elements: Vec::new(),
39 }
40 }
41
42 pub fn spacing(mut self, amount: impl Into<Pixels>) -> Self {
48 self.spacing = amount.into().0;
49 self
50 }
51}
52
53struct State {
54 last_limits: layout::Limits,
55 visible_layouts: Vec<(usize, layout::Node, Tree)>,
56 size: Size,
57 offsets: Vec<f32>,
58 widths: Vec<f32>,
59 task: Task,
60 visible_outdated: bool,
61}
62
63enum Task {
64 Idle,
65 Computing {
66 current: usize,
67 offsets: Vec<f32>,
68 widths: Vec<f32>,
69 size: Size,
70 },
71}
72
73impl State {
74 fn recompute(&mut self, size: usize) {
75 let mut offsets = Vec::with_capacity(size + 1);
76 offsets.push(0.0);
77
78 self.task = Task::Computing {
79 current: 0,
80 offsets,
81 widths: Vec::with_capacity(size),
82 size: Size::ZERO,
83 };
84 self.visible_layouts.clear();
85 }
86}
87
88impl<'a, T, Message, Theme, Renderer> Widget<Message, Theme, Renderer>
89 for List<'a, T, Message, Theme, Renderer>
90where
91 Renderer: core::Renderer,
92{
93 fn tag(&self) -> tree::Tag {
94 tree::Tag::of::<State>()
95 }
96
97 fn state(&self) -> tree::State {
98 tree::State::new(State {
99 last_limits: layout::Limits::NONE,
100 visible_layouts: Vec::new(),
101 size: Size::ZERO,
102 offsets: vec![0.0],
103 widths: Vec::new(),
104 task: Task::Idle,
105 visible_outdated: false,
106 })
107 }
108
109 fn size(&self) -> Size<Length> {
110 Size {
111 width: Length::Shrink,
112 height: Length::Shrink,
113 }
114 }
115
116 fn layout(
117 &self,
118 tree: &mut Tree,
119 renderer: &Renderer,
120 limits: &layout::Limits,
121 ) -> layout::Node {
122 let state = tree.state.downcast_mut::<State>();
123 let loose_limits = limits.loose();
124
125 if state.last_limits != loose_limits {
126 state.last_limits = loose_limits;
127 state.recompute(self.content.len());
128 }
129
130 let mut changes = self.content.changes.borrow_mut();
131
132 match state.task {
133 Task::Idle => {
134 while let Some(change) = changes.pop_front() {
135 match change {
136 Change::Updated { original, current } => {
137 let mut new_element = (self.view_item)(
138 current,
139 &self.content.items[current],
140 );
141
142 let visible_index = state
143 .visible_layouts
144 .iter_mut()
145 .position(|(i, _, _)| *i == original);
146
147 let mut new_tree;
148
149 let tree =
151 if let Some(visible_index) = visible_index {
152 let (_i, _layout, tree) = &mut state
153 .visible_layouts[visible_index];
154
155 tree.diff(&mut new_element);
156 state.visible_outdated = true;
157
158 tree
159 } else {
160 new_tree = Tree::new(&new_element);
161
162 &mut new_tree
163 };
164
165 let new_layout = new_element
166 .as_widget_mut()
167 .layout(tree, renderer, &state.last_limits);
168
169 let new_size = new_layout.size();
170
171 let height_difference = new_size.height
172 - (state.offsets[original + 1]
173 - state.offsets[original]);
174
175 for offset in &mut state.offsets[original + 1..] {
176 *offset += height_difference;
177 }
178
179 let original_width = state.widths[original];
180 state.widths[original] = new_size.width;
181
182 if let Some(visible_index) = visible_index {
183 state.visible_layouts[visible_index].1 =
184 new_layout;
185
186 for (i, layout, _) in
187 &mut state.visible_layouts[visible_index..]
188 {
189 layout
190 .move_to_mut((0.0, state.offsets[*i]));
191 }
192 } else if let Some(first_visible) =
193 state.visible_layouts.first()
194 {
195 let first_visible_index = first_visible.0;
196 if original < first_visible_index {
197 for (i, layout, _) in
198 &mut state.visible_layouts[..]
199 {
200 layout.move_to_mut((
201 0.0,
202 state.offsets[*i],
203 ));
204 }
205 }
206 }
207
208 state.size.height += height_difference;
209
210 if original_width == state.size.width {
211 state.size.width = state.widths.iter().fold(
212 0.0,
213 |current, candidate| {
214 current.max(*candidate)
215 },
216 );
217 }
218 }
219 Change::Removed { original, .. } => {
220 let height = state.offsets[original + 1]
221 - state.offsets[original];
222
223 let original_width = state.widths.remove(original);
224 let _ = state.offsets.remove(original + 1);
225
226 for offset in &mut state.offsets[original + 1..] {
227 *offset -= height;
228 }
229
230 state.visible_layouts.clear();
232
233 state.size.height -= height;
234
235 if original_width == state.size.width {
236 state.size.width = state.widths.iter().fold(
237 0.0,
238 |current, candidate| {
239 current.max(*candidate)
240 },
241 );
242 }
243 }
244 Change::Pushed { current, .. } => {
245 let mut new_element = (self.view_item)(
246 current,
247 &self.content.items[current],
248 );
249
250 let mut tree = Tree::new(&new_element);
251
252 let layout = new_element.as_widget_mut().layout(
253 &mut tree,
254 renderer,
255 &state.last_limits,
256 );
257
258 let size = layout.size();
259
260 state.widths.push(size.width);
261 state.offsets.push(
262 state.offsets.last().unwrap() + size.height,
263 );
264
265 state.size.width = state.size.width.max(size.width);
266 state.size.height += size.height;
267 }
268 }
269 }
270 }
271 Task::Computing { .. } => {
272 if !changes.is_empty() {
273 changes.clear();
276 state.recompute(self.content.len());
277 }
278 }
279 }
280
281 {
283 let mut is_new = self.content.is_new.borrow_mut();
284
285 if *is_new {
286 state.recompute(self.content.len());
287 *is_new = false;
288 }
289 }
290
291 match &mut state.task {
292 Task::Idle => {}
293 Task::Computing {
294 current,
295 size,
296 widths,
297 offsets,
298 } => {
299 const MAX_BATCH_SIZE: usize = 50;
300
301 let end = (*current + MAX_BATCH_SIZE).min(self.content.len());
302
303 let batch = &self.content.items[*current..end];
304
305 let mut max_width = size.width;
306 let mut accumulated_height =
307 offsets.last().copied().unwrap_or(0.0);
308
309 for (i, item) in batch.iter().enumerate() {
310 let element = (self.view_item)(*current + i, item);
311 let mut tree = Tree::new(&element);
312
313 let layout = element
314 .as_widget()
315 .layout(&mut tree, renderer, &state.last_limits)
316 .move_to((0.0, accumulated_height));
317
318 let bounds = layout.bounds();
319
320 max_width = max_width.max(bounds.width);
321 accumulated_height += bounds.height;
322
323 offsets.push(accumulated_height);
324 widths.push(bounds.width);
325 }
326
327 *size = Size::new(max_width, accumulated_height);
328
329 if end < self.content.len() {
330 *current = end;
331 } else {
332 state.offsets = std::mem::take(offsets);
333 state.widths = std::mem::take(widths);
334 state.size = std::mem::take(size);
335 state.task = Task::Idle;
336 }
337 }
338 }
339
340 let intrinsic_size = Size::new(
341 state.size.width,
342 state.size.height
343 + self.content.len().saturating_sub(1) as f32 * self.spacing,
344 );
345
346 let size =
347 limits.resolve(Length::Shrink, Length::Shrink, intrinsic_size);
348
349 layout::Node::new(size)
350 }
351
352 fn on_event(
353 &mut self,
354 tree: &mut Tree,
355 event: Event,
356 layout: Layout<'_>,
357 cursor: mouse::Cursor,
358 renderer: &Renderer,
359 clipboard: &mut dyn Clipboard,
360 shell: &mut Shell<'_, Message>,
361 viewport: &Rectangle,
362 ) -> event::Status {
363 let state = tree.state.downcast_mut::<State>();
364 let offset = layout.position() - Point::ORIGIN;
365
366 let status = self
367 .visible_elements
368 .iter_mut()
369 .zip(&mut state.visible_layouts)
370 .map(|(element, (index, layout, tree))| {
371 element.as_widget_mut().on_event(
372 tree,
373 event.clone(),
374 Layout::with_offset(
375 offset + Vector::new(0.0, self.spacing * *index as f32),
376 layout,
377 ),
378 cursor,
379 renderer,
380 clipboard,
381 shell,
382 viewport,
383 )
384 })
385 .fold(event::Status::Ignored, event::Status::merge);
386
387 if let Event::Window(window::Event::RedrawRequested(_)) = event {
388 match &mut state.task {
389 Task::Idle => {}
390 Task::Computing { .. } => {
391 shell.invalidate_layout();
392 shell.request_redraw(window::RedrawRequest::NextFrame);
393 }
394 }
395
396 let offsets = &state.offsets;
397
398 let start =
399 match binary_search_with_index_by(offsets, |i, height| {
400 (*height + i.saturating_sub(1) as f32 * self.spacing)
401 .partial_cmp(&(viewport.y - offset.y))
402 .unwrap_or(Ordering::Equal)
403 }) {
404 Ok(i) => i,
405 Err(i) => i.saturating_sub(1),
406 }
407 .min(self.content.len());
408
409 let end = match binary_search_with_index_by(offsets, |i, height| {
410 (*height + i.saturating_sub(1) as f32 * self.spacing)
411 .partial_cmp(&(viewport.y + viewport.height - offset.y))
412 .unwrap_or(Ordering::Equal)
413 }) {
414 Ok(i) => i,
415 Err(i) => i,
416 }
417 .min(self.content.len());
418
419 if state.visible_outdated
420 || state.visible_layouts.len() != self.visible_elements.len()
421 {
422 self.visible_elements.clear();
423 state.visible_outdated = false;
424 }
425
426 if self.visible_elements.is_empty() {
429 self.visible_elements = state
430 .visible_layouts
431 .iter()
432 .map(|(i, _, _)| {
433 (self.view_item)(*i, &self.content.items[*i])
434 })
435 .collect();
436 }
437
438 let top = state
440 .visible_layouts
441 .iter()
442 .take_while(|(i, _, _)| *i < start)
443 .count();
444
445 let bottom = state
446 .visible_layouts
447 .iter()
448 .rev()
449 .take_while(|(i, _, _)| *i >= end)
450 .count();
451
452 let _ = self.visible_elements.splice(..top, []);
453 let _ = state.visible_layouts.splice(..top, []);
454
455 let _ = self
456 .visible_elements
457 .splice(self.visible_elements.len() - bottom.., []);
458 let _ = state
459 .visible_layouts
460 .splice(state.visible_layouts.len() - bottom.., []);
461
462 if let Some(first_visible) =
464 state.visible_layouts.first().map(|(i, _, _)| *i)
465 {
466 if start < first_visible {
467 for (i, item) in self.content.items[start..first_visible]
468 .iter()
469 .enumerate()
470 {
471 let element = (self.view_item)(start + i, item);
472 let mut tree = Tree::new(&element);
473
474 let layout = element
475 .as_widget()
476 .layout(&mut tree, renderer, &state.last_limits)
477 .move_to((
478 0.0,
479 offsets[start + i]
480 + (start + i) as f32 * self.spacing,
481 ));
482
483 state
484 .visible_layouts
485 .insert(i, (start + i, layout, tree));
486 self.visible_elements.insert(i, element);
487 }
488 }
489 }
490
491 let last_visible = state
493 .visible_layouts
494 .last()
495 .map(|(i, _, _)| *i + 1)
496 .unwrap_or(start);
497
498 if last_visible < end {
499 for (i, item) in
500 self.content.items[last_visible..end].iter().enumerate()
501 {
502 let element = (self.view_item)(last_visible + i, item);
503 let mut tree = Tree::new(&element);
504
505 let layout = element
506 .as_widget()
507 .layout(&mut tree, renderer, &state.last_limits)
508 .move_to((
509 0.0,
510 offsets[last_visible + i]
511 + (last_visible + i) as f32 * self.spacing,
512 ));
513
514 state.visible_layouts.push((
515 last_visible + i,
516 layout,
517 tree,
518 ));
519 self.visible_elements.push(element);
520 }
521 }
522 }
523
524 status
525 }
526
527 fn draw(
528 &self,
529 tree: &Tree,
530 renderer: &mut Renderer,
531 theme: &Theme,
532 style: &renderer::Style,
533 layout: Layout<'_>,
534 cursor: mouse::Cursor,
535 viewport: &Rectangle,
536 ) {
537 let state = tree.state.downcast_ref::<State>();
538 let offset = layout.position() - Point::ORIGIN;
539
540 for (element, (_item, layout, tree)) in
541 self.visible_elements.iter().zip(&state.visible_layouts)
542 {
543 element.as_widget().draw(
544 tree,
545 renderer,
546 theme,
547 style,
548 Layout::with_offset(offset, layout),
549 cursor,
550 viewport,
551 );
552 }
553 }
554
555 fn mouse_interaction(
556 &self,
557 tree: &Tree,
558 layout: Layout<'_>,
559 cursor: mouse::Cursor,
560 viewport: &Rectangle,
561 renderer: &Renderer,
562 ) -> mouse::Interaction {
563 let state = tree.state.downcast_ref::<State>();
564 let offset = layout.position() - Point::ORIGIN;
565
566 self.visible_elements
567 .iter()
568 .zip(&state.visible_layouts)
569 .map(|(element, (_item, layout, tree))| {
570 element.as_widget().mouse_interaction(
571 tree,
572 Layout::with_offset(offset, layout),
573 cursor,
574 viewport,
575 renderer,
576 )
577 })
578 .max()
579 .unwrap_or_default()
580 }
581
582 fn operate(
583 &self,
584 tree: &mut Tree,
585 layout: Layout<'_>,
586 renderer: &Renderer,
587 operation: &mut dyn widget::Operation,
588 ) {
589 let state = tree.state.downcast_mut::<State>();
590 let offset = layout.position() - Point::ORIGIN;
591
592 for (element, (_item, layout, tree)) in
593 self.visible_elements.iter().zip(&mut state.visible_layouts)
594 {
595 element.as_widget().operate(
596 tree,
597 Layout::with_offset(offset, layout),
598 renderer,
599 operation,
600 );
601 }
602 }
603
604 fn overlay<'b>(
605 &'b mut self,
606 tree: &'b mut Tree,
607 layout: Layout<'_>,
608 renderer: &Renderer,
609 translation: Vector,
610 ) -> Option<overlay::Element<'b, Message, Theme, Renderer>> {
611 let state = tree.state.downcast_mut::<State>();
612 let offset = layout.position() - Point::ORIGIN;
613
614 let children = self
615 .visible_elements
616 .iter_mut()
617 .zip(&mut state.visible_layouts)
618 .filter_map(|(child, (_item, layout, tree))| {
619 child.as_widget_mut().overlay(
620 tree,
621 Layout::with_offset(offset, layout),
622 renderer,
623 translation,
624 )
625 })
626 .collect::<Vec<_>>();
627
628 (!children.is_empty())
629 .then(|| overlay::Group::with_children(children).overlay())
630 }
631}
632
633impl<'a, T, Message, Theme, Renderer>
634 From<List<'a, T, Message, Theme, Renderer>>
635 for Element<'a, Message, Theme, Renderer>
636where
637 Message: 'a,
638 Theme: 'a,
639 Renderer: core::Renderer + 'a,
640{
641 fn from(list: List<'a, T, Message, Theme, Renderer>) -> Self {
642 Self::new(list)
643 }
644}
645
646#[derive(Debug, Clone, PartialEq, Eq)]
647pub struct Content<T> {
648 items: Vec<T>,
649 is_new: RefCell<bool>,
650 changes: RefCell<VecDeque<Change>>,
651}
652
653#[derive(Debug, Clone, Copy, PartialEq, Eq)]
654enum Change {
655 Updated { original: usize, current: usize },
656 Removed { original: usize, current: usize },
657 Pushed { original: usize, current: usize },
658}
659
660impl<T> Content<T> {
661 pub fn new() -> Self {
662 Self {
663 items: Vec::new(),
664 is_new: RefCell::new(true),
665 changes: RefCell::new(VecDeque::new()),
666 }
667 }
668
669 pub fn with_items(items: Vec<T>) -> Self {
670 Self {
671 items,
672 is_new: RefCell::new(true),
673 changes: RefCell::new(VecDeque::new()),
674 }
675 }
676
677 pub fn get(&self, index: usize) -> Option<&T> {
678 self.items.get(index)
679 }
680
681 pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
682 self.changes.borrow_mut().push_back(Change::Updated {
683 original: index,
684 current: index,
685 });
686 self.items.get_mut(index)
687 }
688
689 pub fn push(&mut self, item: T) {
690 let index = self.items.len();
691
692 self.changes.borrow_mut().push_back(Change::Pushed {
693 original: index,
694 current: index,
695 });
696
697 self.items.push(item);
698 }
699
700 pub fn remove(&mut self, index: usize) -> T {
701 let mut changes = self.changes.borrow_mut();
702
703 changes.retain_mut(|change| match change {
705 Change::Updated { current, .. }
706 | Change::Removed { current, .. }
707 | Change::Pushed { current, .. }
708 if *current > index =>
709 {
710 *current -= 1;
712
713 true
714 }
715 _ => true,
716 });
717
718 changes.push_back(Change::Removed {
719 original: index,
720 current: index,
721 });
722
723 self.items.remove(index)
724 }
725
726 pub fn is_empty(&self) -> bool {
727 self.items.is_empty()
728 }
729
730 pub fn len(&self) -> usize {
731 self.items.len()
732 }
733
734 pub fn into_vec(self) -> Vec<T> {
735 self.items
736 }
737}
738
739impl<T> Default for Content<T> {
740 fn default() -> Self {
741 Self::new()
742 }
743}
744
745impl<T> FromIterator<T> for Content<T> {
746 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
747 Self::with_items(iter.into_iter().collect())
748 }
749}
750
751#[allow(unsafe_code)]
753fn binary_search_with_index_by<'a, T, F>(
754 slice: &'a [T],
755 mut f: F,
756) -> Result<usize, usize>
757where
758 F: FnMut(usize, &'a T) -> Ordering,
759{
760 use std::cmp::Ordering::*;
761
762 let mut size = slice.len();
767 let mut left = 0;
768 let mut right = size;
769 while left < right {
770 let mid = left + size / 2;
771
772 let cmp = f(mid, unsafe { slice.get_unchecked(mid) });
777
778 left = if cmp == Less { mid + 1 } else { left };
783 right = if cmp == Greater { mid } else { right };
784 if cmp == Equal {
785 return Ok(mid);
786 }
787
788 size = right - left;
789 }
790
791 Err(left)
792}