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                    let mut run_cascade = element.effect().is_some();
410                    // 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
411                    if !run_cascade
412                        && !self.effect_state.contains_key(&node_id)
413                        && let Some(parent) = self.parents.get(&node_id)
414                        && self.effect_state.contains_key(parent)
415                    {
416                        run_cascade = true;
417                    }
418                    if run_cascade {
419                        handle_cascade(&mut effects_cascades);
420                    }
421                }
422                if flags.intersects(DiffModifies::TEXT_STYLE) {
423                    handle_cascade(&mut text_style_cascades);
424                }
425            }
426        });
427
428        hotpath::measure_block!("layer cascade", {
429            // Run the layer state
430            for layer_root in layer_cascades {
431                let mut buffer = VecDeque::new();
432                buffer.push_front(&layer_root);
433
434                while let Some(node_id) = buffer.pop_front() {
435                    let element = self.elements.get(node_id).unwrap();
436                    if let Some(parent_node_id) = self.parents.get(node_id) {
437                        let entries = self
438                            .layer_state
439                            .get_disjoint_entries([node_id, parent_node_id], |_id| {
440                                LayerState::default()
441                            });
442                        if let Some([layer_state, parent_layer_state]) = entries {
443                            layer_state.update(
444                                parent_layer_state,
445                                *node_id,
446                                element,
447                                &mut self.layers,
448                            );
449                        }
450                    } else {
451                        assert_eq!(*node_id, NodeId::ROOT);
452                        self.layer_state.insert(
453                            NodeId::ROOT,
454                            LayerState::create_for_root(*node_id, &mut self.layers),
455                        );
456                    }
457                    if let Some(children) = self.children.get(node_id) {
458                        buffer.extend(children);
459                    }
460                }
461            }
462        });
463
464        hotpath::measure_block!("effect cascade", {
465            // Run the effect state
466            for effect_root in effects_cascades {
467                let mut buffer = VecDeque::new();
468                buffer.push_front(&effect_root);
469
470                while let Some(node_id) = buffer.pop_front() {
471                    let element = self.elements.get(node_id).unwrap();
472                    if let Some(parent_node_id) = self.parents.get(node_id) {
473                        let entries = self.effect_state.get_disjoint_two_entries(
474                            parent_node_id,
475                            node_id,
476                            |_id| EffectState::default(),
477                            |left, _id| left.clone(),
478                        );
479                        if let [Some(parent_effect_state), Some(effect_state)] = entries {
480                            let effect_data = element.effect();
481                            let layer = element.layer();
482                            effect_state.update(
483                                *parent_node_id,
484                                parent_effect_state,
485                                *node_id,
486                                effect_data,
487                                layer,
488                            );
489                        }
490                    } else {
491                        assert_eq!(*node_id, NodeId::ROOT);
492                    }
493                    if let Some(children) = self.children.get(node_id) {
494                        buffer.extend(children);
495                    }
496                }
497            }
498        });
499
500        hotpath::measure_block!("text style cascade", {
501            // Run the text style state
502            for text_style_root in text_style_cascades {
503                let mut buffer = VecDeque::new();
504                buffer.push_front(&text_style_root);
505
506                while let Some(node_id) = buffer.pop_front() {
507                    let element = self.elements.get(node_id).unwrap();
508                    if let Some(parent_node_id) = self.parents.get(node_id) {
509                        let entries = self
510                            .text_style_state
511                            .get_disjoint_entries([node_id, parent_node_id], |_id| {
512                                TextStyleState::default()
513                            });
514                        if let Some([text_style_state, parent_text_style_state]) = entries {
515                            text_style_state.update(
516                                *node_id,
517                                parent_text_style_state,
518                                element,
519                                &mut self.layout,
520                            );
521                        }
522                    } else {
523                        assert_eq!(*node_id, NodeId::ROOT);
524                        self.text_style_state
525                            .insert(NodeId::ROOT, TextStyleState::default());
526                    }
527                    if let Some(children) = self.children.get(node_id) {
528                        buffer.extend(children);
529                    }
530                }
531            }
532
533            #[cfg(all(debug_assertions, feature = "debug-integrity"))]
534            self.verify_tree_integrity();
535        });
536
537        MutationsApplyResult { needs_render }
538    }
539
540    /// Walk to the ancestor of `base` with the same height of `target`
541    fn balance_heights(&self, base: &NodeId, target: &NodeId) -> Option<NodeId> {
542        let target_height = self.heights.get(target)?;
543        let mut current = base;
544        loop {
545            if self.heights.get(current)? == target_height {
546                break;
547            }
548
549            let parent_current = self.parents.get(current);
550            if let Some(parent_current) = parent_current {
551                current = parent_current;
552            }
553        }
554        Some(*current)
555    }
556
557    pub fn measure_layout(
558        &mut self,
559        size: Size2D,
560        font_collection: &FontCollection,
561        font_manager: &FontMgr,
562        events_sender: &UnboundedSender<EventsChunk>,
563        scale_factor: f64,
564        fallback_fonts: &[Cow<'static, str>],
565    ) {
566        let mut tree_adapter = TreeAdapterFreya {
567            elements: &self.elements,
568            parents: &self.parents,
569            children: &self.children,
570            heights: &self.heights,
571            scale_factor,
572        };
573
574        let mut events = Vec::new();
575
576        let layout_adapter = LayoutMeasurerAdapter {
577            elements: &self.elements,
578            text_style_state: &self.text_style_state,
579            font_collection,
580            font_manager,
581            events: &mut events,
582            scale_factor,
583            fallback_fonts,
584            text_cache: &mut self.text_cache,
585        };
586
587        self.layout.find_best_root(&mut tree_adapter);
588        self.layout.measure(
589            NodeId::ROOT,
590            Area::from_size(size),
591            &mut Some(layout_adapter),
592            &mut tree_adapter,
593        );
594        events_sender
595            .unbounded_send(EventsChunk::Batch(events))
596            .unwrap();
597    }
598
599    pub fn print_ascii(&self, node_id: NodeId, prefix: String, last: bool) {
600        let height = self.heights.get(&node_id).unwrap();
601        let layer = self.layer_state.get(&node_id).unwrap();
602
603        // Print current node
604        println!(
605            "{}{}{:?} [{}] ({})",
606            prefix,
607            if last { "└── " } else { "├── " },
608            node_id,
609            height,
610            layer.layer
611        );
612
613        // Get children
614        if let Some(children) = self.children.get(&node_id) {
615            let len = children.len();
616            for (i, child) in children.iter().enumerate() {
617                let is_last = i == len - 1;
618                // Extend prefix
619                let new_prefix = format!("{}{}", prefix, if last { "    " } else { "│   " });
620                self.print_ascii(*child, new_prefix, is_last);
621            }
622        }
623    }
624
625    #[cfg(all(debug_assertions, feature = "debug-integrity"))]
626    #[cfg_attr(feature = "hotpath", hotpath::measure)]
627    pub fn verify_tree_integrity(&self) {
628        let mut visited = FxHashSet::default();
629        let size = self.elements.len();
630        let mut buffer = vec![NodeId::ROOT];
631        while let Some(node_id) = buffer.pop() {
632            if visited.contains(&node_id) {
633                continue;
634            }
635            visited.insert(node_id);
636            if let Some(parent) = self.parents.get(&node_id) {
637                buffer.push(*parent);
638            }
639            if let Some(children) = self.children.get(&node_id) {
640                buffer.extend(children);
641            }
642        }
643        assert_eq!(size, visited.len())
644    }
645}
646
647bitflags! {
648    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
649    pub struct DiffModifies: u32 {
650        const LAYOUT = 1;
651        const STYLE = 2;
652        const ACCESSIBILITY = 3;
653        const EVENT_HANDLERS = 4;
654        const LAYER = 5;
655        const TEXT_STYLE = 6;
656        const EFFECT = 7;
657        const INNER_LAYOUT = 8;
658        const REORDER_LAYOUT = 9;
659    }
660}
661
662pub struct MutationsApplyResult {
663    pub needs_render: bool,
664}
665
666pub struct LayoutMeasurerAdapter<'a> {
667    pub font_collection: &'a FontCollection,
668    pub font_manager: &'a FontMgr,
669    elements: &'a FxHashMap<NodeId, Rc<dyn ElementExt>>,
670    text_style_state: &'a FxHashMap<NodeId, TextStyleState>,
671    events: &'a mut Vec<EmmitableEvent>,
672    scale_factor: f64,
673    fallback_fonts: &'a [Cow<'static, str>],
674    text_cache: &'a mut TextCache,
675}
676
677impl LayoutMeasurer<NodeId> for LayoutMeasurerAdapter<'_> {
678    fn measure(
679        &mut self,
680        node_id: NodeId,
681        torin_node: &torin::node::Node,
682        area_size: &Size2D,
683    ) -> Option<(Size2D, Rc<dyn Any>)> {
684        self.elements.get(&node_id)?.measure(LayoutContext {
685            node_id,
686            torin_node,
687            area_size,
688            font_collection: self.font_collection,
689            font_manager: self.font_manager,
690            text_style_state: self.text_style_state.get(&node_id).unwrap(),
691            scale_factor: self.scale_factor,
692            fallback_fonts: self.fallback_fonts,
693            text_cache: self.text_cache,
694        })
695    }
696
697    fn should_hook_measurement(&mut self, node_id: NodeId) -> bool {
698        if let Some(element) = self.elements.get(&node_id) {
699            element.should_hook_measurement()
700        } else {
701            false
702        }
703    }
704
705    fn should_measure_inner_children(&mut self, node_id: NodeId) -> bool {
706        if let Some(element) = self.elements.get(&node_id) {
707            element.should_measure_inner_children()
708        } else {
709            false
710        }
711    }
712
713    fn notify_layout_references(
714        &mut self,
715        node_id: NodeId,
716        area: Area,
717        visible_area: Area,
718        inner_sizes: Size2D,
719    ) {
720        let mut data = SizedEventData::new(area, visible_area, inner_sizes);
721        data.div(self.scale_factor as f32);
722        self.events.push(EmmitableEvent {
723            node_id,
724            name: EventName::Sized,
725            data: EventType::Sized(data),
726            bubbles: false,
727            source_event: EventName::Sized,
728        });
729    }
730}
freya_core/tree.rs

freya_core/
tree.rs
