sycamore_web/
iter.rs

1//! Iteration utility components.
2//!
3//! Iteration can be either _"keyed"_ or _"non keyed"_ by using the [`Keyed`] or [`Indexed`] utility
4//! components respectively.
5
6#![allow(non_snake_case)]
7
8use std::collections::HashMap;
9use std::hash::Hash;
10use std::ops::Deref;
11
12use sycamore_macro::{component, Props};
13use wasm_bindgen::prelude::*;
14
15use crate::*;
16
17/// Props for [`Keyed`].
18#[derive(Props)]
19pub struct KeyedProps<T, K, U, List, F, Key>
20where
21    List: Into<MaybeDyn<Vec<T>>> + 'static,
22    F: Fn(T) -> U + 'static,
23    Key: Fn(&T) -> K + 'static,
24    T: 'static,
25{
26    list: List,
27    view: F,
28    key: Key,
29    #[prop(default)]
30    _phantom: std::marker::PhantomData<(T, K, U)>,
31}
32
33/// Keyed iteration.
34///
35/// Use this instead of directly rendering an array of [`View`]s.
36/// Using this will minimize re-renders instead of re-rendering every view node on every
37/// state change.
38///
39/// For non keyed iteration, see [`Indexed`].
40///
41/// # Example
42///
43/// ```
44/// # use sycamore::prelude::*;
45/// #[derive(Clone, PartialEq)]
46/// struct AnimalInfo {
47///     // The name of the animal.
48///     name: &'static str,
49///     // An unique id to identify the animal.
50///     id: u32,
51/// }
52///
53/// # fn App() -> View {
54/// let animals = create_signal(vec![
55///     AnimalInfo { name: "Dog", id: 1 },
56///     AnimalInfo { name: "Cat", id: 2 },
57///     AnimalInfo { name: "Fish", id: 3 },
58/// ]);
59/// view! {
60///     ul {
61///         Keyed(
62///             list=animals,
63///             view=|animal| view! {
64///                 li { (animal.name) }
65///             },
66///             key=|animal| animal.id,
67///         )
68///     }
69/// }
70/// # }
71/// ```
72#[component]
73pub fn Keyed<T, K, U, List, F, Key>(props: KeyedProps<T, K, U, List, F, Key>) -> View
74where
75    T: PartialEq + Clone + 'static,
76    K: Hash + Eq + 'static,
77    U: Into<View>,
78    List: Into<MaybeDyn<Vec<T>>> + 'static,
79    F: Fn(T) -> U + 'static,
80    Key: Fn(&T) -> K + 'static,
81{
82    let KeyedProps {
83        list, view, key, ..
84    } = props;
85
86    if is_ssr!() {
87        // In SSR mode, just create a static view.
88        View::from(
89            list.into()
90                .evaluate()
91                .into_iter()
92                .map(|x| view(x).into())
93                .collect::<Vec<_>>(),
94        )
95    } else {
96        let start = HtmlNode::create_marker_node();
97        let start_node = start.as_web_sys().clone();
98        let end = HtmlNode::create_marker_node();
99        let end_node = end.as_web_sys().clone();
100
101        // Run the initial function in the outer scope, not the effect scope.
102        // This is because we might want to create signals and other things managed by the reactive
103        // tree that will be used in furture triggers of this effect. These things must therefore
104        // live as long as the effect.
105        let scope = use_current_scope();
106        create_effect_initial(move || {
107            scope.run_in(move || {
108                let nodes = map_keyed(list, move |x| view(x).into().as_web_sys(), key);
109                // Flatten nodes.
110                let flattened = nodes.map(|x| x.iter().flatten().cloned().collect::<Vec<_>>());
111                let view = flattened.with(|x| {
112                    View::from_nodes(
113                        x.iter()
114                            .map(|x| HtmlNode::from_web_sys(x.clone()))
115                            .collect(),
116                    )
117                });
118                (
119                    Box::new(move || {
120                        // Get all nodes between start and end and reconcile with new nodes.
121                        let mut new = flattened.get_clone();
122                        let mut old = utils::get_nodes_between(&start_node, &end_node);
123                        // We must include the end node in case `old` is empty (precondition for
124                        // reconcile_fragments).
125                        new.push(end_node.clone());
126                        old.push(end_node.clone());
127
128                        if let Some(parent) = start_node.parent_node() {
129                            reconcile_fragments(&parent, &mut old, &new);
130                        }
131                    }) as Box<dyn FnMut()>,
132                    (start, view, end).into(),
133                )
134            })
135        })
136    }
137}
138
139/// Props for [`Keyed`].
140#[derive(Props)]
141pub struct IndexedProps<T, U, List, F>
142where
143    List: Into<MaybeDyn<Vec<T>>> + 'static,
144    F: Fn(T) -> U + 'static,
145    T: 'static,
146{
147    list: List,
148    view: F,
149    #[prop(default)]
150    _phantom: std::marker::PhantomData<(T, U)>,
151}
152
153/// Non keyed iteration (or keyed by index).
154///
155/// Use this instead of directly rendering an array of
156/// [`View`]s. Using this will minimize re-renders instead of re-rendering every single
157/// node on every state change.
158///
159/// For keyed iteration, see [`Keyed`].
160///
161/// # Example
162/// ```
163/// # use sycamore::prelude::*;
164/// # fn App() -> View {
165/// let fib = create_signal(vec![0, 1, 1, 2, 3, 5, 8]);
166/// view! {
167///     ul {
168///         Indexed(
169///             list=fib,
170///             view=|x| view! {
171///                 li { (x) }
172///             },
173///         )
174///     }
175/// }
176/// # }
177/// ```
178#[component]
179pub fn Indexed<T, U, List, F>(props: IndexedProps<T, U, List, F>) -> View
180where
181    T: PartialEq + Clone + 'static,
182    U: Into<View>,
183    List: Into<MaybeDyn<Vec<T>>> + 'static,
184    F: Fn(T) -> U + 'static,
185{
186    let IndexedProps { list, view, .. } = props;
187
188    if is_ssr!() {
189        // In SSR mode, just create a static view.
190        View::from(
191            list.into()
192                .evaluate()
193                .into_iter()
194                .map(|x| view(x).into())
195                .collect::<Vec<_>>(),
196        )
197    } else {
198        let start = HtmlNode::create_marker_node();
199        let start_node = start.as_web_sys().clone();
200        let end = HtmlNode::create_marker_node();
201        let end_node = end.as_web_sys().clone();
202
203        // Run the initial function in the outer scope, not the effect scope.
204        // This is because we might want to create signals and other things managed by the reactive
205        // tree that will be used in furture triggers of this effect. These things must therefore
206        // live as long as the effect.
207        let scope = use_current_scope();
208        create_effect_initial(move || {
209            scope.run_in(move || {
210                let nodes = map_indexed(list, move |x| view(x).into().as_web_sys());
211                // Flatten nodes.
212                let flattened = nodes.map(|x| x.iter().flatten().cloned().collect::<Vec<_>>());
213                let view = flattened.with(|x| {
214                    View::from_nodes(
215                        x.iter()
216                            .map(|x| HtmlNode::from_web_sys(x.clone()))
217                            .collect(),
218                    )
219                });
220                (
221                    Box::new(move || {
222                        // Get all nodes between start and end and reconcile with new nodes.
223                        let mut new = flattened.get_clone();
224                        let mut old = utils::get_nodes_between(&start_node, &end_node);
225                        // We must include the end node in case `old` is empty (precondition for
226                        // reconcile_fragments).
227                        new.push(end_node.clone());
228                        old.push(end_node.clone());
229
230                        if let Some(parent) = start_node.parent_node() {
231                            reconcile_fragments(&parent, &mut old, &new);
232                        }
233                    }) as Box<dyn FnMut()>,
234                    (start, view, end).into(),
235                )
236            })
237        })
238    }
239}
240
241#[wasm_bindgen]
242extern "C" {
243    /// Extend [`web_sys::Node`] type with an id field. This is used to make `Node` hashable from
244    /// Rust.
245    #[wasm_bindgen(extends = web_sys::Node)]
246    pub(super) type NodeWithId;
247    #[wasm_bindgen(method, getter, js_name = "$id")]
248    pub fn node_id(this: &NodeWithId) -> Option<usize>;
249    #[wasm_bindgen(method, setter, js_name = "$id")]
250    pub fn set_node_id(this: &NodeWithId, id: usize);
251}
252
253/// A wrapper around [`web_sys::Node`] that implements `Hash` and `Eq`.
254struct HashableNode<'a>(&'a NodeWithId, usize);
255
256impl<'a> HashableNode<'a> {
257    thread_local! {
258        static NEXT_ID: Cell<usize> = const { Cell::new(0) };
259    }
260
261    fn new(node: &'a web_sys::Node) -> Self {
262        let node = node.unchecked_ref::<NodeWithId>();
263        let id = if let Some(id) = node.node_id() {
264            id
265        } else {
266            Self::NEXT_ID.with(|cell| {
267                let id = cell.get();
268                cell.set(id + 1);
269                node.set_node_id(id);
270                id
271            })
272        };
273        Self(node, id)
274    }
275}
276
277impl<'a> PartialEq for HashableNode<'a> {
278    fn eq(&self, other: &Self) -> bool {
279        self.1 == other.1
280    }
281}
282
283impl<'a> Eq for HashableNode<'a> {}
284
285impl<'a> Hash for HashableNode<'a> {
286    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
287        self.1.hash(state);
288    }
289}
290
291impl Deref for HashableNode<'_> {
292    type Target = NodeWithId;
293
294    fn deref(&self) -> &Self::Target {
295        self.0
296    }
297}
298
299/// Reconciles an array of nodes.
300///
301/// # Params
302/// * `parent` - The parent node under which all other nodes are (direct) children.
303/// * `a` - The current/existing nodes that are to be diffed.
304/// * `b` - The new nodes that are to be inserted. After the reconciliation, all the nodes in `b`
305///   should be inserted under `parent`.
306///
307/// # Panics
308/// Panics if `a.is_empty()`. Append nodes instead.
309fn reconcile_fragments(parent: &web_sys::Node, a: &mut [web_sys::Node], b: &[web_sys::Node]) {
310    debug_assert!(!a.is_empty(), "a cannot be empty");
311
312    // Sanity check: make sure all nodes in a are children of parent.
313    #[cfg(debug_assertions)]
314    {
315        for (i, node) in a.iter().enumerate() {
316            if node.parent_node().as_ref() != Some(parent) {
317                panic!("node {i} in existing nodes Vec is not a child of parent. node = {node:#?}",);
318            }
319        }
320    }
321
322    let b_len = b.len();
323    let mut a_end = a.len();
324    let mut b_end = b_len;
325    let mut a_start = 0;
326    let mut b_start = 0;
327    let mut map = None::<HashMap<HashableNode, usize>>;
328
329    // Last node in a.
330    let after = a[a_end - 1].next_sibling();
331
332    while a_start < a_end || b_start < b_end {
333        if a_end == a_start {
334            // Append.
335            let node = if b_end < b_len {
336                if b_start != 0 {
337                    b[b_start - 1].next_sibling()
338                } else {
339                    Some(b[b_end - b_start].clone())
340                }
341            } else {
342                after.clone()
343            };
344
345            for new_node in &b[b_start..b_end] {
346                parent.insert_before(new_node, node.as_ref()).unwrap();
347            }
348            b_start = b_end;
349        } else if b_end == b_start {
350            // Remove.
351            for node in &a[a_start..a_end] {
352                if map.is_none() || !map.as_ref().unwrap().contains_key(&HashableNode::new(node)) {
353                    parent.remove_child(node).unwrap();
354                }
355            }
356            a_start = a_end;
357        } else if a[a_start] == b[b_start] {
358            // Common prefix.
359            a_start += 1;
360            b_start += 1;
361        } else if a[a_end - 1] == b[b_end - 1] {
362            // Common suffix.
363            a_end -= 1;
364            b_end -= 1;
365        } else if a[a_start] == b[b_end - 1] && b[b_start] == a[a_end - 1] {
366            // Swap backwards.
367            let node = a[a_end - 1].next_sibling();
368            parent
369                .insert_before(&b[b_start], a[a_start].next_sibling().as_ref())
370                .unwrap();
371            parent.insert_before(&b[b_end - 1], node.as_ref()).unwrap();
372            a_start += 1;
373            b_start += 1;
374            a_end -= 1;
375            b_end -= 1;
376            a[a_end] = b[b_end].clone();
377        } else {
378            // Fallback to map.
379            if map.is_none() {
380                let tmp = b[b_start..b_end]
381                    .iter()
382                    .enumerate()
383                    .map(|(i, g)| (HashableNode::new(g), i))
384                    .collect();
385                map = Some(tmp);
386            }
387            let map = map.as_ref().unwrap();
388
389            if let Some(&index) = map.get(&HashableNode::new(&a[a_start])) {
390                if b_start < index && index < b_end {
391                    let mut i = a_start;
392                    let mut sequence = 1;
393                    let mut t;
394
395                    while i + 1 < a_end && i + 1 < b_end {
396                        i += 1;
397                        t = map.get(&HashableNode::new(&a[i])).copied();
398                        if t != Some(index + sequence) {
399                            break;
400                        }
401                        sequence += 1;
402                    }
403
404                    if sequence > index - b_start {
405                        let node = &a[a_start];
406                        while b_start < index {
407                            parent.insert_before(&b[b_start], Some(node)).unwrap();
408                            b_start += 1;
409                        }
410                    } else {
411                        parent.replace_child(&b[b_start], &a[a_start]).unwrap();
412                        a_start += 1;
413                        b_start += 1;
414                    }
415                } else {
416                    a_start += 1;
417                }
418            } else {
419                parent.remove_child(&a[a_start]).unwrap();
420                a_start += 1;
421            }
422        }
423    }
424
425    // Sanity check: make sure all nodes in b are children of parent after reconciliation.
426    #[cfg(debug_assertions)]
427    {
428        for (i, node) in b.iter().enumerate() {
429            if node.parent_node().as_ref() != Some(parent) {
430                panic!(
431                    "node {i} in new nodes Vec is not a child of parent after reconciliation. node = {node:#?}",
432                );
433            }
434        }
435    }
436}
sycamore_web/iter.rs

sycamore_web/
iter.rs
