iced_widget/
list.rs

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    /// Sets the vertical spacing _between_ elements.
43    ///
44    /// Custom margins per element do not exist in iced. You should use this
45    /// method instead! While less flexible, it helps you keep spacing between
46    /// elements consistent.
47    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                            // Update if visible
150                            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                            // TODO: Smarter visible layout partial updates
231                            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                    // If changes happen during layout computation,
274                    // we simply restart the computation
275                    changes.clear();
276                    state.recompute(self.content.len());
277                }
278            }
279        }
280
281        // Recompute if new
282        {
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 view was recreated, we repopulate the visible elements
427            // out of the internal visible layouts
428            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            // Clear no longer visible elements
439            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            // Prepend new visible elements
463            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            // Append new visible elements
492            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        // Update pending changes after removal
704        changes.retain_mut(|change| match change {
705            Change::Updated { current, .. }
706            | Change::Removed { current, .. }
707            | Change::Pushed { current, .. }
708                if *current > index =>
709            {
710                // Decrement index of later changes
711                *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/// SAFETY: Copied from the `std` library.
752#[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    // INVARIANTS:
763    // - 0 <= left <= left + size = right <= self.len()
764    // - f returns Less for everything in self[..left]
765    // - f returns Greater for everything in self[right..]
766    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        // SAFETY: the while condition means `size` is strictly positive, so
773        // `size/2 < size`. Thus `left + size/2 < left + size`, which
774        // coupled with the `left + size <= self.len()` invariant means
775        // we have `left + size/2 < self.len()`, and this is in-bounds.
776        let cmp = f(mid, unsafe { slice.get_unchecked(mid) });
777
778        // This control flow produces conditional moves, which results in
779        // fewer branches and instructions than if/else or matching on
780        // cmp::Ordering.
781        // This is x86 asm for u8: https://rust.godbolt.org/z/698eYffTx.
782        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}