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

freya_core/
tree.rs
