freya_core/
tree.rs

1use std::{
2    any::Any,
3    borrow::Cow,
4    collections::{
5        VecDeque,
6        hash_map::Entry,
7    },
8    fmt::Debug,
9    rc::Rc,
10};
11
12use bitflags::bitflags;
13use freya_engine::prelude::{
14    FontCollection,
15    FontMgr,
16};
17use futures_channel::mpsc::UnboundedSender;
18use itertools::Itertools;
19use rustc_hash::{
20    FxHashMap,
21    FxHashSet,
22};
23use torin::{
24    prelude::{
25        Area,
26        LayoutMeasurer,
27        Size2D,
28    },
29    torin::{
30        DirtyReason,
31        Torin,
32    },
33};
34
35use crate::{
36    accessibility::groups::AccessibilityGroups,
37    data::{
38        AccessibilityState,
39        EffectState,
40        LayerState,
41        TextStyleState,
42    },
43    element::{
44        ElementExt,
45        LayoutContext,
46    },
47    elements::rect::RectElement,
48    events::{
49        data::{
50            EventType,
51            SizedEventData,
52        },
53        emittable::EmmitableEvent,
54        name::EventName,
55    },
56    extended_hashmap::ExtendedHashMap,
57    integration::{
58        AccessibilityDirtyNodes,
59        AccessibilityGenerator,
60        EventsChunk,
61    },
62    layers::Layers,
63    node_id::NodeId,
64    runner::{
65        MutationRemove,
66        Mutations,
67    },
68    text_cache::TextCache,
69    tree_layout_adapter::TreeAdapterFreya,
70};
71
72#[derive(Default)]
73pub struct Tree {
74    pub parents: FxHashMap<NodeId, NodeId>,
75    pub children: FxHashMap<NodeId, Vec<NodeId>>,
76    pub heights: FxHashMap<NodeId, u16>,
77
78    pub elements: FxHashMap<NodeId, Rc<dyn ElementExt>>,
79
80    // Event listeners
81    pub listeners: FxHashMap<EventName, Vec<NodeId>>,
82
83    // Derived states
84    pub layer_state: FxHashMap<NodeId, LayerState>,
85    pub accessibility_state: FxHashMap<NodeId, AccessibilityState>,
86    pub effect_state: FxHashMap<NodeId, EffectState>,
87    pub text_style_state: FxHashMap<NodeId, TextStyleState>,
88
89    // Other
90    pub layout: Torin<NodeId>,
91    pub layers: Layers,
92    pub text_cache: TextCache,
93
94    // Accessibility
95    pub accessibility_groups: AccessibilityGroups,
96    pub accessibility_diff: AccessibilityDirtyNodes,
97    pub accessibility_generator: AccessibilityGenerator,
98}
99
100impl Debug for Tree {
101    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
102        f.debug_struct("Tree")
103            .field("children", &self.children.capacity())
104            .field("parents", &self.parents.capacity())
105            .field("elements", &self.elements.capacity())
106            .field("heights", &self.heights.capacity())
107            .field("listeners", &self.listeners.capacity())
108            .field("layer_state", &self.layer_state.capacity())
109            .field("layout_size", &self.layout.size())
110            .field("layers", &self.layers.capacity())
111            .field("effect_state", &self.effect_state.capacity())
112            .field("accessibility_state", &self.accessibility_state.capacity())
113            .field("text_style_state", &self.text_style_state.capacity())
114            .field("text_cache", &self.text_cache)
115            .finish()
116    }
117}
118
119impl Tree {
120    pub fn size(&self) -> usize {
121        self.elements.len()
122    }
123
124    pub fn traverse_depth(&self, mut then: impl FnMut(NodeId)) {
125        let mut buffer = vec![NodeId::ROOT];
126        while let Some(node_id) = buffer.pop() {
127            if let Some(children) = self.children.get(&node_id) {
128                buffer.extend(children.iter().rev());
129            }
130            then(node_id);
131        }
132    }
133
134    pub fn traverse_depth_cancel(&self, mut then: impl FnMut(NodeId) -> bool) {
135        let mut buffer = vec![NodeId::ROOT];
136        while let Some(node_id) = buffer.pop() {
137            if let Some(children) = self.children.get(&node_id) {
138                buffer.extend(children.iter().rev());
139            }
140            if then(node_id) {
141                break;
142            }
143        }
144    }
145
146    #[cfg_attr(feature = "hotpath", hotpath::measure)]
147    pub fn apply_mutations(&mut self, mutations: Mutations) -> MutationsApplyResult {
148        let mut needs_render = !mutations.removed.is_empty();
149        let mut dirty = Vec::<(NodeId, DiffModifies)>::default();
150
151        #[cfg(debug_assertions)]
152        tracing::info!("{mutations:?}");
153
154        if let Entry::Vacant(e) = self.elements.entry(NodeId::ROOT) {
155            e.insert(Rc::new(RectElement::default()));
156            self.heights.insert(NodeId::ROOT, 0);
157            dirty.push((NodeId::ROOT, DiffModifies::all()));
158        }
159
160        hotpath::measure_block!("mutations run", {
161            for remove in mutations.removed.into_iter().sorted() {
162                let node_id = remove.node_id();
163                let mut buff = vec![remove];
164                let Some(parent_id) = self.parents.get(&node_id).copied() else {
165                    continue;
166                };
167                self.layout.invalidate(parent_id);
168                needs_render = true;
169
170                while let Some(remove) = buff.pop() {
171                    let node_id = remove.node_id();
172                    self.layout.raw_remove(node_id);
173
174                    let parent_id = self.parents.remove(&node_id).unwrap();
175
176                    // Remove element
177                    let old_element = self.elements.remove(&node_id).unwrap();
178
179                    if let Some(children) = self.children.get_mut(&parent_id) {
180                        match remove {
181                            MutationRemove::Element { index, .. } => {
182                                children.remove(index as usize);
183                            }
184                            MutationRemove::Scope { .. } => {
185                                children.retain(|id| *id != node_id);
186                            }
187                        }
188                    }
189
190                    // Remove its children too
191                    if let Some(children) = self.children.remove(&node_id) {
192                        buff.extend(children.into_iter().enumerate().map(|(i, e)| {
193                            MutationRemove::Element {
194                                id: e,
195                                index: i as u32,
196                            }
197                        }));
198                    }
199
200                    // Remove old events
201                    if let Some(events) = old_element.events_handlers() {
202                        for event in events.keys() {
203                            self.listeners
204                                .entry(*event)
205                                .or_default()
206                                .retain(|id| *id != node_id);
207                        }
208                    }
209
210                    // Remove from the layers
211                    let layer_state = self.layer_state.remove(&node_id).unwrap();
212                    layer_state.remove(node_id, &mut self.layers);
213
214                    // Remove from the accessibility
215                    let accessibility_state = self.accessibility_state.remove(&node_id).unwrap();
216                    accessibility_state.remove(
217                        node_id,
218                        parent_id,
219                        &mut self.accessibility_diff,
220                        &mut self.accessibility_groups,
221                    );
222
223                    // Remove from other states
224                    self.heights.remove(&node_id);
225                    self.effect_state.remove(&node_id);
226                    self.text_style_state.remove(&node_id);
227                    self.text_cache.remove(&node_id);
228                }
229            }
230
231            for (node_id, parent_node_id, index_inside_parent, element) in mutations
232                .added
233                .into_iter()
234                .sorted_by_key(|(_, parent_node_id, index_inside_parent, _)| {
235                    (*parent_node_id, *index_inside_parent)
236                })
237            {
238                let parent_height = *self.heights.entry(parent_node_id).or_default();
239
240                self.parents.insert(node_id, parent_node_id);
241                self.heights.insert(node_id, parent_height + 1);
242
243                let parent = self.children.entry(parent_node_id).or_default();
244
245                // TODO: Improve this
246                if parent.len() < index_inside_parent as usize + 1 {
247                    parent.resize(index_inside_parent as usize + 1, NodeId::PLACEHOLDER);
248
249                    parent[index_inside_parent as usize] = node_id;
250                } else if parent.get(index_inside_parent as usize) == Some(&NodeId::PLACEHOLDER) {
251                    parent[index_inside_parent as usize] = node_id;
252                } else {
253                    parent.insert(index_inside_parent as usize, node_id);
254                }
255
256                // Add events
257                if let Some(events) = element.events_handlers() {
258                    for event in events.keys() {
259                        self.listeners.entry(*event).or_default().push(node_id);
260                    }
261                }
262
263                self.elements.insert(node_id, element);
264                dirty.push((node_id, DiffModifies::all()));
265            }
266
267            for (parent_node_id, movements) in mutations.moved {
268                let parent = self.children.get_mut(&parent_node_id).unwrap();
269                for (to, node_id) in movements.iter() {
270                    let from = parent.iter().position(|id| id == node_id).unwrap();
271
272                    if from < *to as usize {
273                        parent.insert(*to as usize, *node_id);
274                        parent.remove(from);
275                    } else {
276                        parent.remove(from);
277                        parent.insert(*to as usize, *node_id);
278                    }
279                }
280                let mut diff = DiffModifies::empty();
281                diff.insert(DiffModifies::REORDER_LAYOUT);
282                diff.insert(DiffModifies::ACCESSIBILITY);
283                diff.insert(DiffModifies::STYLE);
284                dirty.push((parent_node_id, diff));
285            }
286
287            for (node_id, element, flags) in mutations.modified {
288                dirty.push((node_id, flags));
289
290                let old_element = self.elements.remove(&node_id).unwrap();
291
292                if flags.contains(DiffModifies::EVENT_HANDLERS) {
293                    // Remove old events
294                    if let Some(events) = old_element.events_handlers() {
295                        for event in events.keys() {
296                            self.listeners
297                                .entry(*event)
298                                .or_default()
299                                .retain(|id| *id != node_id);
300                        }
301                    }
302
303                    // Add new events
304                    if let Some(events) = element.events_handlers() {
305                        for event in events.keys() {
306                            self.listeners.entry(*event).or_default().push(node_id);
307                        }
308                    }
309                }
310
311                self.elements.insert(node_id, element);
312            }
313        });
314
315        // Run states cascades
316        let mut layer_cascades: Vec<NodeId> = Vec::new();
317        let mut effects_cascades: Vec<NodeId> = Vec::new();
318        let mut text_style_cascades: Vec<NodeId> = Vec::new();
319
320        assert_eq!(dirty.len(), FxHashSet::from_iter(&dirty).len());
321
322        hotpath::measure_block!("dirty run", {
323            for (node_id, flags) in dirty {
324                let element = self.elements.get(&node_id).unwrap();
325                let height_b = self.heights.get(&node_id).unwrap();
326
327                if flags.contains(DiffModifies::REORDER_LAYOUT) {
328                    self.layout
329                        .invalidate_with_reason(node_id, DirtyReason::Reorder);
330                }
331
332                if flags.contains(DiffModifies::INNER_LAYOUT) {
333                    self.layout
334                        .invalidate_with_reason(node_id, DirtyReason::InnerLayout);
335                }
336
337                if flags.contains(DiffModifies::LAYOUT) {
338                    self.layout.invalidate(node_id);
339                }
340
341                if !needs_render
342                    && (flags.intersects(
343                        DiffModifies::STYLE
344                            | DiffModifies::LAYER
345                            | DiffModifies::EFFECT
346                            | DiffModifies::TEXT_STYLE,
347                    ))
348                {
349                    needs_render = true;
350                }
351
352                if flags.contains(DiffModifies::ACCESSIBILITY) {
353                    match self.accessibility_state.get_mut(&node_id) {
354                        Some(accessibility_state) => accessibility_state.update(
355                            node_id,
356                            element,
357                            &mut self.accessibility_diff,
358                            &mut self.accessibility_groups,
359                        ),
360                        None => {
361                            self.accessibility_state.insert(
362                                node_id,
363                                AccessibilityState::create(
364                                    node_id,
365                                    element,
366                                    &mut self.accessibility_diff,
367                                    &self.accessibility_generator,
368                                    &mut self.accessibility_groups,
369                                ),
370                            );
371                        }
372                    }
373                }
374
375                let handle_cascade = |cascades: &mut Vec<NodeId>| {
376                    // Skip scanning if we already know this node is the a root
377                    if cascades.iter_mut().any(|root| {
378                        let height_a = self.heights.get(root).unwrap();
379
380                        match height_a.cmp(height_b) {
381                            std::cmp::Ordering::Less => {
382                                self.balance_heights(&node_id, root) == Some(*root)
383                            }
384                            std::cmp::Ordering::Greater => {
385                                let balanced_root = self.balance_heights(root, &node_id);
386                                match balanced_root {
387                                    Some(r) if r == node_id => {
388                                        // If this node is ascendant than the
389                                        // current root we set it as the new root
390                                        *root = node_id;
391                                        true
392                                    }
393                                    _ => false,
394                                }
395                            }
396                            std::cmp::Ordering::Equal => false,
397                        }
398                    }) {
399                        return;
400                    }
401                    cascades.push(node_id);
402                };
403
404                if flags.intersects(DiffModifies::LAYER) {
405                    handle_cascade(&mut layer_cascades);
406                }
407                if flags.intersects(DiffModifies::EFFECT) {
408                    let element = self.elements.get(&node_id).unwrap();
409                    if element.effect().is_some() {
410                        handle_cascade(&mut effects_cascades);
411                    }
412                }
413                if flags.intersects(DiffModifies::TEXT_STYLE) {
414                    handle_cascade(&mut text_style_cascades);
415                }
416            }
417        });
418
419        hotpath::measure_block!("layer cascade", {
420            // Run the layer state
421            for layer_root in layer_cascades {
422                let mut buffer = VecDeque::new();
423                buffer.push_front(&layer_root);
424
425                while let Some(node_id) = buffer.pop_front() {
426                    let element = self.elements.get(node_id).unwrap();
427                    if let Some(parent_node_id) = self.parents.get(node_id) {
428                        let entries = self
429                            .layer_state
430                            .get_disjoint_entries([node_id, parent_node_id], |_id| {
431                                LayerState::default()
432                            });
433                        if let Some([layer_state, parent_layer_state]) = entries {
434                            layer_state.update(
435                                parent_layer_state,
436                                *node_id,
437                                element,
438                                &mut self.layers,
439                            );
440                        }
441                    } else {
442                        assert_eq!(*node_id, NodeId::ROOT);
443                        self.layer_state.insert(
444                            NodeId::ROOT,
445                            LayerState::create_for_root(*node_id, &mut self.layers),
446                        );
447                    }
448                    if let Some(children) = self.children.get(node_id) {
449                        buffer.extend(children);
450                    }
451                }
452            }
453        });
454
455        hotpath::measure_block!("effect cascade", {
456            // Run the effect state
457            for effect_root in effects_cascades {
458                let mut buffer = VecDeque::new();
459                buffer.push_front(&effect_root);
460
461                while let Some(node_id) = buffer.pop_front() {
462                    let element = self.elements.get(node_id).unwrap();
463                    if let Some(parent_node_id) = self.parents.get(node_id) {
464                        let entries = self.effect_state.get_disjoint_two_entries(
465                            parent_node_id,
466                            node_id,
467                            |_id| EffectState::default(),
468                            |left, _id| left.clone(),
469                        );
470                        if let [Some(parent_effect_state), Some(effect_state)] = entries {
471                            let effect_data = element.effect();
472                            let layer = element.layer();
473                            effect_state.update(
474                                *parent_node_id,
475                                parent_effect_state,
476                                *node_id,
477                                effect_data,
478                                layer,
479                            );
480                        }
481                    } else {
482                        assert_eq!(*node_id, NodeId::ROOT);
483                    }
484                    if let Some(children) = self.children.get(node_id) {
485                        buffer.extend(children);
486                    }
487                }
488            }
489        });
490
491        hotpath::measure_block!("text style cascade", {
492            // Run the text style state
493            for text_style_root in text_style_cascades {
494                let mut buffer = VecDeque::new();
495                buffer.push_front(&text_style_root);
496
497                while let Some(node_id) = buffer.pop_front() {
498                    let element = self.elements.get(node_id).unwrap();
499                    if let Some(parent_node_id) = self.parents.get(node_id) {
500                        let entries = self
501                            .text_style_state
502                            .get_disjoint_entries([node_id, parent_node_id], |_id| {
503                                TextStyleState::default()
504                            });
505                        if let Some([text_style_state, parent_text_style_state]) = entries {
506                            text_style_state.update(
507                                *node_id,
508                                parent_text_style_state,
509                                element,
510                                &mut self.layout,
511                            );
512                        }
513                    } else {
514                        assert_eq!(*node_id, NodeId::ROOT);
515                        self.text_style_state
516                            .insert(NodeId::ROOT, TextStyleState::default());
517                    }
518                    if let Some(children) = self.children.get(node_id) {
519                        buffer.extend(children);
520                    }
521                }
522            }
523
524            #[cfg(all(debug_assertions, feature = "debug-integrity"))]
525            self.verify_tree_integrity();
526        });
527
528        MutationsApplyResult { needs_render }
529    }
530
531    /// Walk to the ancestor of `base` with the same height of `target`
532    fn balance_heights(&self, base: &NodeId, target: &NodeId) -> Option<NodeId> {
533        let target_height = self.heights.get(target)?;
534        let mut current = base;
535        loop {
536            if self.heights.get(current)? == target_height {
537                break;
538            }
539
540            let parent_current = self.parents.get(current);
541            if let Some(parent_current) = parent_current {
542                current = parent_current;
543            }
544        }
545        Some(*current)
546    }
547
548    pub fn measure_layout(
549        &mut self,
550        size: Size2D,
551        font_collection: &FontCollection,
552        font_manager: &FontMgr,
553        events_sender: &UnboundedSender<EventsChunk>,
554        scale_factor: f64,
555        fallback_fonts: &[Cow<'static, str>],
556    ) {
557        let mut tree_adapter = TreeAdapterFreya {
558            elements: &self.elements,
559            parents: &self.parents,
560            children: &self.children,
561            heights: &self.heights,
562            scale_factor,
563        };
564
565        let mut events = Vec::new();
566
567        let layout_adapter = LayoutMeasurerAdapter {
568            elements: &self.elements,
569            text_style_state: &self.text_style_state,
570            font_collection,
571            font_manager,
572            events: &mut events,
573            scale_factor,
574            fallback_fonts,
575            text_cache: &mut self.text_cache,
576        };
577
578        self.layout.find_best_root(&mut tree_adapter);
579        self.layout.measure(
580            NodeId::ROOT,
581            Area::from_size(size),
582            &mut Some(layout_adapter),
583            &mut tree_adapter,
584        );
585        events_sender
586            .unbounded_send(EventsChunk::Batch(events))
587            .unwrap();
588    }
589
590    pub fn print_ascii(&self, node_id: NodeId, prefix: String, last: bool) {
591        let height = self.heights.get(&node_id).unwrap();
592        let layer = self.layer_state.get(&node_id).unwrap();
593
594        // Print current node
595        println!(
596            "{}{}{:?} [{}] ({})",
597            prefix,
598            if last { "└── " } else { "├── " },
599            node_id,
600            height,
601            layer.layer
602        );
603
604        // Get children
605        if let Some(children) = self.children.get(&node_id) {
606            let len = children.len();
607            for (i, child) in children.iter().enumerate() {
608                let is_last = i == len - 1;
609                // Extend prefix
610                let new_prefix = format!("{}{}", prefix, if last { "    " } else { "│   " });
611                self.print_ascii(*child, new_prefix, is_last);
612            }
613        }
614    }
615
616    #[cfg(all(debug_assertions, feature = "debug-integrity"))]
617    #[cfg_attr(feature = "hotpath", hotpath::measure)]
618    pub fn verify_tree_integrity(&self) {
619        let mut visited = FxHashSet::default();
620        let size = self.elements.len();
621        let mut buffer = vec![NodeId::ROOT];
622        while let Some(node_id) = buffer.pop() {
623            if visited.contains(&node_id) {
624                continue;
625            }
626            visited.insert(node_id);
627            if let Some(parent) = self.parents.get(&node_id) {
628                buffer.push(*parent);
629            }
630            if let Some(children) = self.children.get(&node_id) {
631                buffer.extend(children);
632            }
633        }
634        assert_eq!(size, visited.len())
635    }
636}
637
638bitflags! {
639    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
640    pub struct DiffModifies: u32 {
641        const LAYOUT = 1;
642        const STYLE = 2;
643        const ACCESSIBILITY = 3;
644        const EVENT_HANDLERS = 4;
645        const LAYER = 5;
646        const TEXT_STYLE = 6;
647        const EFFECT = 7;
648        const INNER_LAYOUT = 8;
649        const REORDER_LAYOUT = 9;
650    }
651}
652
653pub struct MutationsApplyResult {
654    pub needs_render: bool,
655}
656
657pub struct LayoutMeasurerAdapter<'a> {
658    pub font_collection: &'a FontCollection,
659    pub font_manager: &'a FontMgr,
660    elements: &'a FxHashMap<NodeId, Rc<dyn ElementExt>>,
661    text_style_state: &'a FxHashMap<NodeId, TextStyleState>,
662    events: &'a mut Vec<EmmitableEvent>,
663    scale_factor: f64,
664    fallback_fonts: &'a [Cow<'static, str>],
665    text_cache: &'a mut TextCache,
666}
667
668impl LayoutMeasurer<NodeId> for LayoutMeasurerAdapter<'_> {
669    fn measure(
670        &mut self,
671        node_id: NodeId,
672        torin_node: &torin::node::Node,
673        area_size: &Size2D,
674    ) -> Option<(Size2D, Rc<dyn Any>)> {
675        self.elements.get(&node_id)?.measure(LayoutContext {
676            node_id,
677            torin_node,
678            area_size,
679            font_collection: self.font_collection,
680            font_manager: self.font_manager,
681            text_style_state: self.text_style_state.get(&node_id).unwrap(),
682            scale_factor: self.scale_factor,
683            fallback_fonts: self.fallback_fonts,
684            text_cache: self.text_cache,
685        })
686    }
687
688    fn should_hook_measurement(&mut self, node_id: NodeId) -> bool {
689        if let Some(element) = self.elements.get(&node_id) {
690            element.should_hook_measurement()
691        } else {
692            false
693        }
694    }
695
696    fn should_measure_inner_children(&mut self, node_id: NodeId) -> bool {
697        if let Some(element) = self.elements.get(&node_id) {
698            element.should_measure_inner_children()
699        } else {
700            false
701        }
702    }
703
704    fn notify_layout_references(
705        &mut self,
706        node_id: NodeId,
707        area: Area,
708        visible_area: Area,
709        inner_sizes: Size2D,
710    ) {
711        let mut data = SizedEventData::new(area, visible_area, inner_sizes);
712        data.div(self.scale_factor as f32);
713        self.events.push(EmmitableEvent {
714            node_id,
715            name: EventName::Sized,
716            data: EventType::Sized(data),
717            bubbles: false,
718            source_event: EventName::Sized,
719        });
720    }
721}
freya_core/tree.rs

freya_core/
tree.rs
