floem/views/
dyn_stack.rs

1use std::{
2    hash::{BuildHasherDefault, Hash},
3    marker::PhantomData,
4};
5
6use floem_reactive::{as_child_of_current_scope, create_effect, Scope};
7use rustc_hash::FxHasher;
8use smallvec::SmallVec;
9
10use crate::{
11    app_state::AppState,
12    context::UpdateCx,
13    id::ViewId,
14    view::{IntoView, View},
15};
16
17pub(crate) type FxIndexSet<T> = indexmap::IndexSet<T, BuildHasherDefault<FxHasher>>;
18
19type ViewFn<T> = Box<dyn Fn(T) -> (Box<dyn View>, Scope)>;
20
21#[derive(educe::Educe)]
22#[educe(Debug)]
23pub(crate) struct HashRun<T>(#[educe(Debug(ignore))] pub(crate) T);
24
25pub struct DynStack<T>
26where
27    T: 'static,
28{
29    id: ViewId,
30    children: Vec<Option<(ViewId, Scope)>>,
31    view_fn: ViewFn<T>,
32    phantom: PhantomData<T>,
33}
34
35/// A stack whose items can be reactively updated.
36///
37/// This is useful when you have a list of views that change over time.
38///
39/// The [`dyn_stack`] takes a function that returns an iterator of items.
40/// If the function contains a signal, such as an `RwSignal<Vec<u32>>`, when that signal is updated the views will also update.
41/// The [`dyn_stack`] internally keeps track of changes to the items and ensures that, if an item hash did not change, the associated view is not reloaded.
42///
43/// The [`dyn_stack`] tracks the uniqueness of items by letting you provide a `key function`.
44/// This key function gives you a reference to an item from the list and lets you return a value that can be hashed.
45/// That value is what tells the [`dyn_stack`] how the item is unique from the others.
46/// Often times, the item in the list, such as u32 in this case, already implements hash and you can simply return the same value.
47///
48/// ## Example
49/// ```
50/// use floem::reactive::*;
51/// use floem::views::*;
52///
53/// let items = create_rw_signal(vec![1,2,3,4]);
54///
55/// dyn_stack(
56///    move || items.get(),
57///    move |item| *item,
58///    move |item| label(move || item),
59/// );
60/// ```
61/// This will only work if all of the items in the list are unique.
62/// If all of the items are not unique, you can choose some other value to hash. It is common to use an [`AtomicU32`](std::sync::atomic::AtomicU32) to accomplish this.
63///
64/// ## Example
65/// ```
66///
67/// use std::sync::atomic::{AtomicU32, Ordering};
68/// use floem::reactive::*;
69/// use floem::views::*;
70///
71/// let items = create_rw_signal(vec![1,1,2,2,3,3,4,4]);
72/// let unique_atomic = AtomicU32::new(0);
73///
74/// dyn_stack(
75///    move || items.get(),
76///    move |_item| unique_atomic.fetch_add(1, Ordering::Relaxed),
77///    move |item| label(move || item),
78/// );
79/// ```
80///
81pub fn dyn_stack<IF, I, T, KF, K, VF, V>(each_fn: IF, key_fn: KF, view_fn: VF) -> DynStack<T>
82where
83    IF: Fn() -> I + 'static,
84    I: IntoIterator<Item = T>,
85    KF: Fn(&T) -> K + 'static,
86    K: Eq + Hash + 'static,
87    VF: Fn(T) -> V + 'static,
88    V: IntoView + 'static,
89    T: 'static,
90{
91    let id = ViewId::new();
92    create_effect(move |prev_hash_run| {
93        let items = each_fn();
94        let items = items.into_iter().collect::<SmallVec<[_; 128]>>();
95        let hashed_items = items.iter().map(&key_fn).collect::<FxIndexSet<_>>();
96        let diff = if let Some(HashRun(prev_hash_run)) = prev_hash_run {
97            let mut cmds = diff(&prev_hash_run, &hashed_items);
98            let mut items = items
99                .into_iter()
100                .map(|i| Some(i))
101                .collect::<SmallVec<[Option<_>; 128]>>();
102            for added in &mut cmds.added {
103                added.view = Some(items[added.at].take().unwrap());
104            }
105            cmds
106        } else {
107            let mut diff = Diff::default();
108            for (i, item) in each_fn().into_iter().enumerate() {
109                diff.added.push(DiffOpAdd {
110                    at: i,
111                    view: Some(item),
112                });
113            }
114            diff
115        };
116        id.update_state(diff);
117        HashRun(hashed_items)
118    });
119    let view_fn = Box::new(as_child_of_current_scope(move |e| view_fn(e).into_any()));
120    DynStack {
121        id,
122        children: Vec::new(),
123        view_fn,
124        phantom: PhantomData,
125    }
126}
127
128impl<T> View for DynStack<T> {
129    fn id(&self) -> ViewId {
130        self.id
131    }
132
133    fn debug_name(&self) -> std::borrow::Cow<'static, str> {
134        "DynStack".into()
135    }
136
137    fn update(&mut self, cx: &mut UpdateCx, state: Box<dyn std::any::Any>) {
138        if let Ok(diff) = state.downcast() {
139            apply_diff(
140                self.id(),
141                cx.app_state,
142                *diff,
143                &mut self.children,
144                &self.view_fn,
145            );
146            self.id.request_all();
147        }
148    }
149}
150
151#[derive(Debug)]
152pub struct Diff<V> {
153    pub(crate) removed: SmallVec<[DiffOpRemove; 8]>,
154    pub(crate) moved: SmallVec<[DiffOpMove; 8]>,
155    pub(crate) added: SmallVec<[DiffOpAdd<V>; 8]>,
156    pub(crate) clear: bool,
157}
158
159impl<V> Default for Diff<V> {
160    fn default() -> Self {
161        Self {
162            removed: Default::default(),
163            moved: Default::default(),
164            added: Default::default(),
165            clear: false,
166        }
167    }
168}
169
170impl<V> Diff<V> {
171    pub fn is_empty(&self) -> bool {
172        self.removed.is_empty() && self.moved.is_empty() && self.added.is_empty() && !self.clear
173    }
174}
175
176#[derive(Debug)]
177pub(crate) struct DiffOpMove {
178    pub(crate) from: usize,
179    pub(crate) to: usize,
180}
181
182#[derive(Debug)]
183pub(crate) struct DiffOpAdd<V> {
184    pub(crate) at: usize,
185    pub(crate) view: Option<V>,
186}
187
188#[derive(Debug)]
189pub(crate) struct DiffOpRemove {
190    pub(crate) at: usize,
191}
192
193/// Calculates the operations need to get from `a` to `b`.
194pub(crate) fn diff<K: Eq + Hash, V>(from: &FxIndexSet<K>, to: &FxIndexSet<K>) -> Diff<V> {
195    if from.is_empty() && to.is_empty() {
196        return Diff::default();
197    } else if to.is_empty() {
198        return Diff {
199            clear: true,
200            ..Default::default()
201        };
202    }
203
204    // Get removed items
205    let mut removed = from.difference(to);
206
207    let removed_cmds = removed
208        .clone()
209        .map(|k| from.get_full(k).unwrap().0)
210        .map(|idx| DiffOpRemove { at: idx });
211
212    // Get added items
213    let mut added = to.difference(from);
214
215    let added_cmds = added
216        .clone()
217        .map(|k| to.get_full(k).unwrap().0)
218        .map(|idx| DiffOpAdd {
219            at: idx,
220            view: None,
221        });
222
223    // Get moved items
224    let mut normalized_idx = 0;
225    let mut move_cmds = SmallVec::<[_; 8]>::with_capacity(to.len());
226    let mut added_idx = added.next().map(|k| to.get_full(k).unwrap().0);
227    let mut removed_idx = removed.next().map(|k| from.get_full(k).unwrap().0);
228
229    for (idx, k) in to.iter().enumerate() {
230        if let Some(added_idx) = added_idx.as_mut().filter(|r_i| **r_i == idx) {
231            if let Some(next_added) = added.next().map(|k| to.get_full(k).unwrap().0) {
232                *added_idx = next_added;
233
234                normalized_idx = usize::wrapping_sub(normalized_idx, 1);
235            }
236        }
237
238        if let Some(removed_idx) = removed_idx.as_mut().filter(|r_i| **r_i == idx) {
239            normalized_idx = normalized_idx.wrapping_add(1);
240
241            if let Some(next_removed) = removed.next().map(|k| from.get_full(k).unwrap().0) {
242                *removed_idx = next_removed;
243            }
244        }
245
246        if let Some((from_idx, _)) = from.get_full(k) {
247            if from_idx != normalized_idx || from_idx != idx {
248                move_cmds.push(DiffOpMove {
249                    from: from_idx,
250                    to: idx,
251                });
252            }
253        }
254
255        normalized_idx = normalized_idx.wrapping_add(1);
256    }
257
258    let mut diffs = Diff {
259        removed: removed_cmds.collect(),
260        moved: move_cmds,
261        added: added_cmds.collect(),
262        clear: false,
263    };
264
265    if !from.is_empty()
266        && !to.is_empty()
267        && diffs.removed.len() == from.len()
268        && diffs.moved.is_empty()
269    {
270        diffs.clear = true;
271    }
272
273    diffs
274}
275
276fn remove_index(
277    app_state: &mut AppState,
278    children: &mut [Option<(ViewId, Scope)>],
279    index: usize,
280) -> Option<()> {
281    let (view_id, scope) = std::mem::take(&mut children[index])?;
282    app_state.remove_view(view_id);
283    scope.dispose();
284    Some(())
285}
286
287pub(super) fn apply_diff<T, VF>(
288    view_id: ViewId,
289    app_state: &mut AppState,
290    mut diff: Diff<T>,
291    children: &mut Vec<Option<(ViewId, Scope)>>,
292    view_fn: &VF,
293) where
294    VF: Fn(T) -> (Box<dyn View>, Scope),
295{
296    // Resize children if needed
297    if diff.added.len().checked_sub(diff.removed.len()).is_some() {
298        let target_size =
299            children.len() + (diff.added.len() as isize - diff.removed.len() as isize) as usize;
300
301        children.resize_with(target_size, || None);
302    }
303
304    // We need to hold a list of items which will be moved, and
305    // we can only perform the move after all commands have run, otherwise,
306    // we risk overwriting one of the values
307    let mut items_to_move = Vec::with_capacity(diff.moved.len());
308
309    // The order of cmds needs to be:
310    // 1. Clear
311    // 2. Removed
312    // 3. Moved
313    // 4. Add
314    if diff.clear {
315        for i in 0..children.len() {
316            remove_index(app_state, children, i);
317        }
318        diff.removed.clear();
319    }
320
321    for DiffOpRemove { at } in diff.removed {
322        remove_index(app_state, children, at);
323    }
324
325    for DiffOpMove { from, to } in diff.moved {
326        let item = children[from].take().unwrap();
327        items_to_move.push((to, item));
328    }
329
330    for DiffOpAdd { at, view } in diff.added {
331        let new_child = view.map(view_fn);
332        children[at] = new_child.map(|(view, scope)| {
333            let id = view.id();
334            id.set_view(view);
335            id.set_parent(view_id);
336            (id, scope)
337        });
338    }
339
340    for (to, each_item) in items_to_move {
341        children[to] = Some(each_item);
342    }
343
344    // Now, remove the holes that might have been left from removing
345    // items
346    children.retain(|c| c.is_some());
347
348    let children_ids: Vec<ViewId> = children
349        .iter()
350        .filter_map(|c| Some(c.as_ref()?.0))
351        .collect();
352    view_id.set_children_ids(children_ids);
353}
floem/views/dyn_stack.rs

floem/views/
dyn_stack.rs
