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}
761