accesskit_consumer/
tree.rs

Help
1// Copyright 2021 The AccessKit Authors. All rights reserved.
2// Licensed under the Apache License, Version 2.0 (found in
3// the LICENSE-APACHE file) or the MIT license (found in
4// the LICENSE-MIT file), at your option.
5
6use accesskit::{FrozenNode as NodeData, NodeId, Tree as TreeData, TreeUpdate};
7use alloc::{format, string::String, sync::Arc, vec, vec::Vec};
8use hashbrown::{HashMap, HashSet};
9use immutable_chunkmap::map::MapM as ChunkMap;
10
11use crate::node::{Node, NodeState, ParentAndIndex};
12
13#[derive(Clone)]
14pub struct State {
15    pub(crate) nodes: ChunkMap<NodeId, NodeState>,
16    pub(crate) data: TreeData,
17    pub(crate) focus: NodeId,
18    is_host_focused: bool,
19}
20
21#[derive(Default)]
22struct InternalChanges {
23    added_node_ids: HashSet<NodeId>,
24    updated_node_ids: HashSet<NodeId>,
25    removed_node_ids: HashSet<NodeId>,
26}
27
28impl State {
29    fn validate_global(&self) {
30        if self.nodes.get_key(&self.data.root).is_none() {
31            panic!("Root id #{} is not in the node list", self.data.root.0);
32        }
33        if self.nodes.get_key(&self.focus).is_none() {
34            panic!("Focused id #{} is not in the node list", self.focus.0);
35        }
36    }
37
38    fn update(
39        &mut self,
40        update: TreeUpdate,
41        is_host_focused: bool,
42        mut changes: Option<&mut InternalChanges>,
43    ) {
44        let mut orphans = HashSet::new();
45
46        if let Some(tree) = update.tree {
47            if tree.root != self.data.root {
48                orphans.insert(self.data.root);
49            }
50            self.data = tree;
51        }
52
53        let root = self.data.root;
54        let mut pending_nodes: HashMap<NodeId, _> = HashMap::new();
55        let mut pending_children = HashMap::new();
56
57        fn add_node(
58            nodes: &mut ChunkMap<NodeId, NodeState>,
59            changes: &mut Option<&mut InternalChanges>,
60            parent_and_index: Option<ParentAndIndex>,
61            id: NodeId,
62            data: NodeData,
63        ) {
64            let state = NodeState {
65                parent_and_index,
66                data: Arc::new(data),
67            };
68            nodes.insert_cow(id, state);
69            if let Some(changes) = changes {
70                changes.added_node_ids.insert(id);
71            }
72        }
73
74        for (node_id, node_data) in update.nodes {
75            let node_data = NodeData::from(node_data);
76
77            orphans.remove(&node_id);
78
79            let mut seen_child_ids = HashSet::with_capacity(node_data.children().len());
80            for (child_index, child_id) in node_data.children().iter().enumerate() {
81                if seen_child_ids.contains(child_id) {
82                    panic!(
83                        "Node #{} of TreeUpdate includes duplicate child #{};",
84                        node_id.0, child_id.0
85                    );
86                }
87                orphans.remove(child_id);
88                let parent_and_index = ParentAndIndex(node_id, child_index);
89                if let Some(child_state) = self.nodes.get_mut_cow(child_id) {
90                    if child_state.parent_and_index != Some(parent_and_index) {
91                        child_state.parent_and_index = Some(parent_and_index);
92                    }
93                } else if let Some(child_data) = pending_nodes.remove(child_id) {
94                    add_node(
95                        &mut self.nodes,
96                        &mut changes,
97                        Some(parent_and_index),
98                        *child_id,
99                        child_data,
100                    );
101                } else {
102                    pending_children.insert(*child_id, parent_and_index);
103                }
104                seen_child_ids.insert(*child_id);
105            }
106
107            if let Some(node_state) = self.nodes.get_mut_cow(&node_id) {
108                if node_id == root {
109                    node_state.parent_and_index = None;
110                }
111                for child_id in node_state.data.children().iter() {
112                    if !seen_child_ids.contains(child_id) {
113                        orphans.insert(*child_id);
114                    }
115                }
116                if *node_state.data != node_data {
117                    node_state.data = Arc::new(node_data);
118                    if let Some(changes) = &mut changes {
119                        changes.updated_node_ids.insert(node_id);
120                    }
121                }
122            } else if let Some(parent_and_index) = pending_children.remove(&node_id) {
123                add_node(
124                    &mut self.nodes,
125                    &mut changes,
126                    Some(parent_and_index),
127                    node_id,
128                    node_data,
129                );
130            } else if node_id == root {
131                add_node(&mut self.nodes, &mut changes, None, node_id, node_data);
132            } else {
133                pending_nodes.insert(node_id, node_data);
134            }
135        }
136
137        if !pending_nodes.is_empty() {
138            panic!("TreeUpdate includes {} nodes which are neither in the current tree nor a child of another node from the update: {}", pending_nodes.len(), short_node_list(pending_nodes.keys()));
139        }
140        if !pending_children.is_empty() {
141            panic!("TreeUpdate's nodes include {} children ids which are neither in the current tree nor the id of another node from the update: {}", pending_children.len(), short_node_list(pending_children.keys()));
142        }
143
144        self.focus = update.focus;
145        self.is_host_focused = is_host_focused;
146
147        if !orphans.is_empty() {
148            let mut to_remove = Vec::new();
149
150            fn traverse_orphan(
151                nodes: &ChunkMap<NodeId, NodeState>,
152                to_remove: &mut Vec<NodeId>,
153                id: NodeId,
154            ) {
155                to_remove.push(id);
156                let node = nodes.get(&id).unwrap();
157                for child_id in node.data.children().iter() {
158                    traverse_orphan(nodes, to_remove, *child_id);
159                }
160            }
161
162            for id in orphans {
163                traverse_orphan(&self.nodes, &mut to_remove, id);
164            }
165
166            for id in to_remove {
167                if self.nodes.remove_cow(&id).is_some() {
168                    if let Some(changes) = &mut changes {
169                        changes.removed_node_ids.insert(id);
170                    }
171                }
172            }
173        }
174
175        self.validate_global();
176    }
177
178    fn update_host_focus_state(
179        &mut self,
180        is_host_focused: bool,
181        changes: Option<&mut InternalChanges>,
182    ) {
183        let update = TreeUpdate {
184            nodes: vec![],
185            tree: None,
186            focus: self.focus,
187        };
188        self.update(update, is_host_focused, changes);
189    }
190
191    pub fn has_node(&self, id: NodeId) -> bool {
192        self.nodes.get(&id).is_some()
193    }
194
195    pub fn node_by_id(&self, id: NodeId) -> Option<Node<'_>> {
196        self.nodes.get(&id).map(|node_state| Node {
197            tree_state: self,
198            id,
199            state: node_state,
200        })
201    }
202
203    pub fn root_id(&self) -> NodeId {
204        self.data.root
205    }
206
207    pub fn root(&self) -> Node<'_> {
208        self.node_by_id(self.root_id()).unwrap()
209    }
210
211    pub fn is_host_focused(&self) -> bool {
212        self.is_host_focused
213    }
214
215    pub fn focus_id(&self) -> Option<NodeId> {
216        self.is_host_focused.then_some(self.focus)
217    }
218
219    pub fn focus(&self) -> Option<Node<'_>> {
220        self.focus_id().map(|id| self.node_by_id(id).unwrap())
221    }
222
223    pub fn app_name(&self) -> Option<String> {
224        self.data.app_name.clone()
225    }
226
227    pub fn toolkit_name(&self) -> Option<String> {
228        self.data.toolkit_name.clone()
229    }
230
231    pub fn toolkit_version(&self) -> Option<String> {
232        self.data.toolkit_version.clone()
233    }
234}
235
236pub trait ChangeHandler {
237    fn node_added(&mut self, node: &Node);
238    fn node_updated(&mut self, old_node: &Node, new_node: &Node);
239    fn focus_moved(&mut self, old_node: Option<&Node>, new_node: Option<&Node>);
240    fn node_removed(&mut self, node: &Node);
241}
242
243pub struct Tree {
244    state: State,
245}
246
247impl Tree {
248    pub fn new(mut initial_state: TreeUpdate, is_host_focused: bool) -> Self {
249        let Some(tree) = initial_state.tree.take() else {
250            panic!("Tried to initialize the accessibility tree without a root tree. TreeUpdate::tree must be Some.");
251        };
252        let mut state = State {
253            nodes: ChunkMap::new(),
254            data: tree,
255            focus: initial_state.focus,
256            is_host_focused,
257        };
258        state.update(initial_state, is_host_focused, None);
259        Self { state }
260    }
261
262    pub fn update(&mut self, update: TreeUpdate) {
263        self.state.update(update, self.state.is_host_focused, None);
264    }
265
266    pub fn update_and_process_changes(
267        &mut self,
268        update: TreeUpdate,
269        handler: &mut impl ChangeHandler,
270    ) {
271        let mut changes = InternalChanges::default();
272        let old_state = self.state.clone();
273        self.state
274            .update(update, self.state.is_host_focused, Some(&mut changes));
275        self.process_changes(old_state, changes, handler);
276    }
277
278    pub fn update_host_focus_state(&mut self, is_host_focused: bool) {
279        self.state.update_host_focus_state(is_host_focused, None);
280    }
281
282    pub fn update_host_focus_state_and_process_changes(
283        &mut self,
284        is_host_focused: bool,
285        handler: &mut impl ChangeHandler,
286    ) {
287        let mut changes = InternalChanges::default();
288        let old_state = self.state.clone();
289        self.state
290            .update_host_focus_state(is_host_focused, Some(&mut changes));
291        self.process_changes(old_state, changes, handler);
292    }
293
294    fn process_changes(
295        &self,
296        old_state: State,
297        changes: InternalChanges,
298        handler: &mut impl ChangeHandler,
299    ) {
300        for id in &changes.added_node_ids {
301            let node = self.state.node_by_id(*id).unwrap();
302            handler.node_added(&node);
303        }
304        for id in &changes.updated_node_ids {
305            let old_node = old_state.node_by_id(*id).unwrap();
306            let new_node = self.state.node_by_id(*id).unwrap();
307            handler.node_updated(&old_node, &new_node);
308        }
309        if old_state.focus_id() != self.state.focus_id() {
310            let old_node = old_state.focus();
311            if let Some(old_node) = &old_node {
312                let id = old_node.id();
313                if !changes.updated_node_ids.contains(&id)
314                    && !changes.removed_node_ids.contains(&id)
315                {
316                    if let Some(old_node_new_version) = self.state.node_by_id(id) {
317                        handler.node_updated(old_node, &old_node_new_version);
318                    }
319                }
320            }
321            let new_node = self.state.focus();
322            if let Some(new_node) = &new_node {
323                let id = new_node.id();
324                if !changes.added_node_ids.contains(&id) && !changes.updated_node_ids.contains(&id)
325                {
326                    if let Some(new_node_old_version) = old_state.node_by_id(id) {
327                        handler.node_updated(&new_node_old_version, new_node);
328                    }
329                }
330            }
331            handler.focus_moved(old_node.as_ref(), new_node.as_ref());
332        }
333        for id in &changes.removed_node_ids {
334            let node = old_state.node_by_id(*id).unwrap();
335            handler.node_removed(&node);
336        }
337    }
338
339    pub fn state(&self) -> &State {
340        &self.state
341    }
342}
343
344fn short_node_list<'a>(nodes: impl ExactSizeIterator<Item = &'a NodeId>) -> String {
345    if nodes.len() > 10 {
346        format!(
347            "[{} ...]",
348            nodes
349                .take(10)
350                .map(|id| format!("#{}", id.0))
351                .collect::<Vec<_>>()
352                .join(", "),
353        )
354    } else {
355        format!(
356            "[{}]",
357            nodes
358                .map(|id| format!("#{}", id.0))
359                .collect::<Vec<_>>()
360                .join(", "),
361        )
362    }
363}
364
365#[cfg(test)]
366mod tests {
367    use accesskit::{Node, NodeId, Role, Tree, TreeUpdate};
368    use alloc::vec;
369
370    #[test]
371    fn init_tree_with_root_node() {
372        let update = TreeUpdate {
373            nodes: vec![(NodeId(0), Node::new(Role::Window))],
374            tree: Some(Tree::new(NodeId(0))),
375            focus: NodeId(0),
376        };
377        let tree = super::Tree::new(update, false);
378        assert_eq!(NodeId(0), tree.state().root().id());
379        assert_eq!(Role::Window, tree.state().root().role());
380        assert!(tree.state().root().parent().is_none());
381    }
382
383    #[test]
384    fn root_node_has_children() {
385        let update = TreeUpdate {
386            nodes: vec![
387                (NodeId(0), {
388                    let mut node = Node::new(Role::Window);
389                    node.set_children(vec![NodeId(1), NodeId(2)]);
390                    node
391                }),
392                (NodeId(1), Node::new(Role::Button)),
393                (NodeId(2), Node::new(Role::Button)),
394            ],
395            tree: Some(Tree::new(NodeId(0))),
396            focus: NodeId(0),
397        };
398        let tree = super::Tree::new(update, false);
399        let state = tree.state();
400        assert_eq!(
401            NodeId(0),
402            state.node_by_id(NodeId(1)).unwrap().parent().unwrap().id()
403        );
404        assert_eq!(
405            NodeId(0),
406            state.node_by_id(NodeId(2)).unwrap().parent().unwrap().id()
407        );
408        assert_eq!(2, state.root().children().count());
409    }
410
411    #[test]
412    fn add_child_to_root_node() {
413        let root_node = Node::new(Role::Window);
414        let first_update = TreeUpdate {
415            nodes: vec![(NodeId(0), root_node.clone())],
416            tree: Some(Tree::new(NodeId(0))),
417            focus: NodeId(0),
418        };
419        let mut tree = super::Tree::new(first_update, false);
420        assert_eq!(0, tree.state().root().children().count());
421        let second_update = TreeUpdate {
422            nodes: vec![
423                (NodeId(0), {
424                    let mut node = root_node;
425                    node.push_child(NodeId(1));
426                    node
427                }),
428                (NodeId(1), Node::new(Role::RootWebArea)),
429            ],
430            tree: None,
431            focus: NodeId(0),
432        };
433        struct Handler {
434            got_new_child_node: bool,
435            got_updated_root_node: bool,
436        }
437        fn unexpected_change() {
438            panic!("expected only new child node and updated root node");
439        }
440        impl super::ChangeHandler for Handler {
441            fn node_added(&mut self, node: &crate::Node) {
442                if node.id() == NodeId(1) {
443                    self.got_new_child_node = true;
444                    return;
445                }
446                unexpected_change();
447            }
448            fn node_updated(&mut self, old_node: &crate::Node, new_node: &crate::Node) {
449                if new_node.id() == NodeId(0)
450                    && old_node.data().children().is_empty()
451                    && new_node.data().children() == [NodeId(1)]
452                {
453                    self.got_updated_root_node = true;
454                    return;
455                }
456                unexpected_change();
457            }
458            fn focus_moved(
459                &mut self,
460                _old_node: Option<&crate::Node>,
461                _new_node: Option<&crate::Node>,
462            ) {
463                unexpected_change();
464            }
465            fn node_removed(&mut self, _node: &crate::Node) {
466                unexpected_change();
467            }
468        }
469        let mut handler = Handler {
470            got_new_child_node: false,
471            got_updated_root_node: false,
472        };
473        tree.update_and_process_changes(second_update, &mut handler);
474        assert!(handler.got_new_child_node);
475        assert!(handler.got_updated_root_node);
476        let state = tree.state();
477        assert_eq!(1, state.root().children().count());
478        assert_eq!(NodeId(1), state.root().children().next().unwrap().id());
479        assert_eq!(
480            NodeId(0),
481            state.node_by_id(NodeId(1)).unwrap().parent().unwrap().id()
482        );
483    }
484
485    #[test]
486    fn remove_child_from_root_node() {
487        let root_node = Node::new(Role::Window);
488        let first_update = TreeUpdate {
489            nodes: vec![
490                (NodeId(0), {
491                    let mut node = root_node.clone();
492                    node.push_child(NodeId(1));
493                    node
494                }),
495                (NodeId(1), Node::new(Role::RootWebArea)),
496            ],
497            tree: Some(Tree::new(NodeId(0))),
498            focus: NodeId(0),
499        };
500        let mut tree = super::Tree::new(first_update, false);
501        assert_eq!(1, tree.state().root().children().count());
502        let second_update = TreeUpdate {
503            nodes: vec![(NodeId(0), root_node)],
504            tree: None,
505            focus: NodeId(0),
506        };
507        struct Handler {
508            got_updated_root_node: bool,
509            got_removed_child_node: bool,
510        }
511        fn unexpected_change() {
512            panic!("expected only removed child node and updated root node");
513        }
514        impl super::ChangeHandler for Handler {
515            fn node_added(&mut self, _node: &crate::Node) {
516                unexpected_change();
517            }
518            fn node_updated(&mut self, old_node: &crate::Node, new_node: &crate::Node) {
519                if new_node.id() == NodeId(0)
520                    && old_node.data().children() == [NodeId(1)]
521                    && new_node.data().children().is_empty()
522                {
523                    self.got_updated_root_node = true;
524                    return;
525                }
526                unexpected_change();
527            }
528            fn focus_moved(
529                &mut self,
530                _old_node: Option<&crate::Node>,
531                _new_node: Option<&crate::Node>,
532            ) {
533                unexpected_change();
534            }
535            fn node_removed(&mut self, node: &crate::Node) {
536                if node.id() == NodeId(1) {
537                    self.got_removed_child_node = true;
538                    return;
539                }
540                unexpected_change();
541            }
542        }
543        let mut handler = Handler {
544            got_updated_root_node: false,
545            got_removed_child_node: false,
546        };
547        tree.update_and_process_changes(second_update, &mut handler);
548        assert!(handler.got_updated_root_node);
549        assert!(handler.got_removed_child_node);
550        assert_eq!(0, tree.state().root().children().count());
551        assert!(tree.state().node_by_id(NodeId(1)).is_none());
552    }
553
554    #[test]
555    fn move_focus_between_siblings() {
556        let first_update = TreeUpdate {
557            nodes: vec![
558                (NodeId(0), {
559                    let mut node = Node::new(Role::Window);
560                    node.set_children(vec![NodeId(1), NodeId(2)]);
561                    node
562                }),
563                (NodeId(1), Node::new(Role::Button)),
564                (NodeId(2), Node::new(Role::Button)),
565            ],
566            tree: Some(Tree::new(NodeId(0))),
567            focus: NodeId(1),
568        };
569        let mut tree = super::Tree::new(first_update, true);
570        assert!(tree.state().node_by_id(NodeId(1)).unwrap().is_focused());
571        let second_update = TreeUpdate {
572            nodes: vec![],
573            tree: None,
574            focus: NodeId(2),
575        };
576        struct Handler {
577            got_old_focus_node_update: bool,
578            got_new_focus_node_update: bool,
579            got_focus_change: bool,
580        }
581        fn unexpected_change() {
582            panic!("expected only focus change");
583        }
584        impl super::ChangeHandler for Handler {
585            fn node_added(&mut self, _node: &crate::Node) {
586                unexpected_change();
587            }
588            fn node_updated(&mut self, old_node: &crate::Node, new_node: &crate::Node) {
589                if old_node.id() == NodeId(1)
590                    && new_node.id() == NodeId(1)
591                    && old_node.is_focused()
592                    && !new_node.is_focused()
593                {
594                    self.got_old_focus_node_update = true;
595                    return;
596                }
597                if old_node.id() == NodeId(2)
598                    && new_node.id() == NodeId(2)
599                    && !old_node.is_focused()
600                    && new_node.is_focused()
601                {
602                    self.got_new_focus_node_update = true;
603                    return;
604                }
605                unexpected_change();
606            }
607            fn focus_moved(
608                &mut self,
609                old_node: Option<&crate::Node>,
610                new_node: Option<&crate::Node>,
611            ) {
612                if let (Some(old_node), Some(new_node)) = (old_node, new_node) {
613                    if old_node.id() == NodeId(1) && new_node.id() == NodeId(2) {
614                        self.got_focus_change = true;
615                        return;
616                    }
617                }
618                unexpected_change();
619            }
620            fn node_removed(&mut self, _node: &crate::Node) {
621                unexpected_change();
622            }
623        }
624        let mut handler = Handler {
625            got_old_focus_node_update: false,
626            got_new_focus_node_update: false,
627            got_focus_change: false,
628        };
629        tree.update_and_process_changes(second_update, &mut handler);
630        assert!(handler.got_old_focus_node_update);
631        assert!(handler.got_new_focus_node_update);
632        assert!(handler.got_focus_change);
633        assert!(tree.state().node_by_id(NodeId(2)).unwrap().is_focused());
634        assert!(!tree.state().node_by_id(NodeId(1)).unwrap().is_focused());
635    }
636
637    #[test]
638    fn update_node() {
639        let child_node = Node::new(Role::Button);
640        let first_update = TreeUpdate {
641            nodes: vec![
642                (NodeId(0), {
643                    let mut node = Node::new(Role::Window);
644                    node.set_children(vec![NodeId(1)]);
645                    node
646                }),
647                (NodeId(1), {
648                    let mut node = child_node.clone();
649                    node.set_label("foo");
650                    node
651                }),
652            ],
653            tree: Some(Tree::new(NodeId(0))),
654            focus: NodeId(0),
655        };
656        let mut tree = super::Tree::new(first_update, false);
657        assert_eq!(
658            Some("foo".into()),
659            tree.state().node_by_id(NodeId(1)).unwrap().label()
660        );
661        let second_update = TreeUpdate {
662            nodes: vec![(NodeId(1), {
663                let mut node = child_node;
664                node.set_label("bar");
665                node
666            })],
667            tree: None,
668            focus: NodeId(0),
669        };
670        struct Handler {
671            got_updated_child_node: bool,
672        }
673        fn unexpected_change() {
674            panic!("expected only updated child node");
675        }
676        impl super::ChangeHandler for Handler {
677            fn node_added(&mut self, _node: &crate::Node) {
678                unexpected_change();
679            }
680            fn node_updated(&mut self, old_node: &crate::Node, new_node: &crate::Node) {
681                if new_node.id() == NodeId(1)
682                    && old_node.label() == Some("foo".into())
683                    && new_node.label() == Some("bar".into())
684                {
685                    self.got_updated_child_node = true;
686                    return;
687                }
688                unexpected_change();
689            }
690            fn focus_moved(
691                &mut self,
692                _old_node: Option<&crate::Node>,
693                _new_node: Option<&crate::Node>,
694            ) {
695                unexpected_change();
696            }
697            fn node_removed(&mut self, _node: &crate::Node) {
698                unexpected_change();
699            }
700        }
701        let mut handler = Handler {
702            got_updated_child_node: false,
703        };
704        tree.update_and_process_changes(second_update, &mut handler);
705        assert!(handler.got_updated_child_node);
706        assert_eq!(
707            Some("bar".into()),
708            tree.state().node_by_id(NodeId(1)).unwrap().label()
709        );
710    }
711
712    // Verify that if an update consists entirely of node data and tree data
713    // that's the same as before, no changes are reported. This is useful
714    // for a provider that constructs a fresh tree every time, such as
715    // an immediate-mode GUI.
716    #[test]
717    fn no_change_update() {
718        let update = TreeUpdate {
719            nodes: vec![
720                (NodeId(0), {
721                    let mut node = Node::new(Role::Window);
722                    node.set_children(vec![NodeId(1)]);
723                    node
724                }),
725                (NodeId(1), {
726                    let mut node = Node::new(Role::Button);
727                    node.set_label("foo");
728                    node
729                }),
730            ],
731            tree: Some(Tree::new(NodeId(0))),
732            focus: NodeId(0),
733        };
734        let mut tree = super::Tree::new(update.clone(), false);
735        struct Handler;
736        fn unexpected_change() {
737            panic!("expected no changes");
738        }
739        impl super::ChangeHandler for Handler {
740            fn node_added(&mut self, _node: &crate::Node) {
741                unexpected_change();
742            }
743            fn node_updated(&mut self, _old_node: &crate::Node, _new_node: &crate::Node) {
744                unexpected_change();
745            }
746            fn focus_moved(
747                &mut self,
748                _old_node: Option<&crate::Node>,
749                _new_node: Option<&crate::Node>,
750            ) {
751                unexpected_change();
752            }
753            fn node_removed(&mut self, _node: &crate::Node) {
754                unexpected_change();
755            }
756        }
757        let mut handler = Handler {};
758        tree.update_and_process_changes(update, &mut handler);
759    }
760}
accesskit_consumer/tree.rs

accesskit_consumer/
tree.rs
