1use ahash::{AHashMap, AHashSet};
11
12use crate::node::{A11yNodeInfo, A11yRole, LiveRegion};
13
14const MAX_TRAVERSAL_DEPTH: usize = 1000;
15
16#[derive(Debug, Clone)]
26pub struct A11yTreeBuilder {
27 nodes: AHashMap<u64, A11yNodeInfo>,
28 root: Option<u64>,
29 focused: Option<u64>,
30}
31
32impl Default for A11yTreeBuilder {
33 fn default() -> Self {
34 Self::new()
35 }
36}
37
38impl A11yTreeBuilder {
39 #[inline]
41 pub fn new() -> Self {
42 Self {
43 nodes: AHashMap::new(),
44 root: None,
45 focused: None,
46 }
47 }
48
49 #[inline]
51 #[must_use]
52 pub fn focused(&self) -> Option<u64> {
53 self.focused
54 }
55
56 #[inline]
58 pub fn with_capacity(capacity: usize) -> Self {
59 Self {
60 nodes: AHashMap::with_capacity(capacity),
61 root: None,
62 focused: None,
63 }
64 }
65
66 #[inline]
68 pub fn add_node(&mut self, node: A11yNodeInfo) {
69 self.nodes.insert(node.id, node);
70 }
71
72 #[inline]
74 pub fn set_root(&mut self, id: u64) {
75 self.root = Some(id);
76 }
77
78 #[inline]
80 pub fn set_focused(&mut self, id: Option<u64>) {
81 self.focused = id;
82 }
83
84 #[inline]
86 #[must_use]
87 pub fn root(&self) -> Option<u64> {
88 self.root
89 }
90
91 #[inline]
93 #[must_use]
94 pub fn node(&self, id: u64) -> Option<&A11yNodeInfo> {
95 self.nodes.get(&id)
96 }
97
98 #[inline]
100 pub fn node_mut(&mut self, id: u64) -> Option<&mut A11yNodeInfo> {
101 self.nodes.get_mut(&id)
102 }
103
104 #[inline]
106 #[must_use]
107 pub fn len(&self) -> usize {
108 self.nodes.len()
109 }
110
111 #[inline]
113 #[must_use]
114 pub fn is_empty(&self) -> bool {
115 self.nodes.is_empty()
116 }
117
118 #[inline]
120 pub fn build(self) -> A11yTree {
121 A11yTree {
122 nodes: self.nodes,
123 root: self.root,
124 focused: self.focused,
125 }
126 }
127}
128
129#[derive(Debug, Clone)]
137pub struct A11yTree {
138 nodes: AHashMap<u64, A11yNodeInfo>,
139 root: Option<u64>,
140 focused: Option<u64>,
141}
142
143impl Default for A11yTree {
144 fn default() -> Self {
145 Self::empty()
146 }
147}
148
149impl A11yTree {
150 #[inline]
152 pub fn empty() -> Self {
153 Self {
154 nodes: AHashMap::new(),
155 root: None,
156 focused: None,
157 }
158 }
159
160 #[inline]
162 pub fn node(&self, id: u64) -> Option<&A11yNodeInfo> {
163 self.nodes.get(&id)
164 }
165
166 #[inline]
168 pub fn root(&self) -> Option<&A11yNodeInfo> {
169 self.root.and_then(|id| self.nodes.get(&id))
170 }
171
172 #[inline]
174 pub fn root_id(&self) -> Option<u64> {
175 self.root
176 }
177
178 #[inline]
180 pub fn focused(&self) -> Option<&A11yNodeInfo> {
181 self.focused.and_then(|id| self.nodes.get(&id))
182 }
183
184 #[inline]
186 pub fn focused_id(&self) -> Option<u64> {
187 self.focused
188 }
189
190 #[inline]
192 pub fn nodes(&self) -> impl Iterator<Item = &A11yNodeInfo> {
193 self.nodes.values()
194 }
195
196 #[inline]
198 pub fn node_count(&self) -> usize {
199 self.nodes.len()
200 }
201
202 #[inline]
204 pub fn is_empty(&self) -> bool {
205 self.nodes.is_empty()
206 }
207
208 pub fn children_of(&self, id: u64) -> Vec<&A11yNodeInfo> {
210 self.nodes
211 .get(&id)
212 .map(|n| {
213 n.children
214 .iter()
215 .filter_map(|cid| self.nodes.get(cid))
216 .collect()
217 })
218 .unwrap_or_default()
219 }
220
221 #[must_use]
227 pub fn dump_text(&self, order: &[u64]) -> String {
228 let mut out = String::new();
229 for &id in order {
230 let Some(node) = self.node(id) else {
231 continue;
232 };
233 let depth = self.ancestors(id).len().saturating_sub(1);
235 let mut states: Vec<&str> = Vec::new();
236 if node.state.focused {
237 states.push("focused");
238 }
239 if node.state.disabled {
240 states.push("disabled");
241 }
242 if node.state.selected {
243 states.push("selected");
244 }
245 match node.state.checked {
246 Some(true) => states.push("checked"),
247 Some(false) => states.push("unchecked"),
248 None => {}
249 }
250 match node.state.expanded {
251 Some(true) => states.push("expanded"),
252 Some(false) => states.push("collapsed"),
253 None => {}
254 }
255 if node.state.readonly {
256 states.push("readonly");
257 }
258 if node.state.required {
259 states.push("required");
260 }
261 if node.state.busy {
262 states.push("busy");
263 }
264 let name = node.name.as_deref().unwrap_or("");
265 let b = node.bounds;
266 out.push_str(&format!(
267 "{}{:?} \"{}\" [{}] @{},{} {}x{}\n",
268 " ".repeat(depth),
269 node.role,
270 name,
271 states.join(","),
272 b.x,
273 b.y,
274 b.width,
275 b.height
276 ));
277 }
278 out
279 }
280
281 pub fn ancestors(&self, id: u64) -> Vec<u64> {
287 let mut path = Vec::new();
288 let mut visited = AHashSet::new();
289 let mut current = Some(id);
290 while let Some(cid) = current {
291 if path.len() >= MAX_TRAVERSAL_DEPTH || !visited.insert(cid) {
292 break;
293 }
294 if let Some(node) = self.nodes.get(&cid) {
295 path.push(cid);
296 current = node.parent;
297 } else {
298 break;
299 }
300 }
301 path
302 }
303
304 pub fn screen_reader_mirror(&self, policy: ScreenReaderPolicy) -> ScreenReaderMirror {
310 let mut order = Vec::with_capacity(self.nodes.len());
311 let mut visited = AHashSet::with_capacity(self.nodes.len());
312
313 if let Some(root) = self.root {
314 self.collect_mirror_order(root, 0, &mut visited, &mut order);
315 }
316
317 let mut disconnected: Vec<u64> = self
318 .nodes
319 .keys()
320 .copied()
321 .filter(|id| !visited.contains(id))
322 .collect();
323 disconnected.sort_unstable();
324
325 for id in disconnected {
326 self.collect_mirror_order(id, 0, &mut visited, &mut order);
327 }
328
329 let mut lines = Vec::new();
330 let mut omitted_nodes = 0;
331
332 for (id, depth) in order {
333 let Some(node) = self.nodes.get(&id) else {
334 continue;
335 };
336 if node.role == A11yRole::Presentation {
337 continue;
338 }
339 if lines.len() >= policy.max_mirror_nodes {
340 omitted_nodes += 1;
341 continue;
342 }
343
344 let indent = " ".repeat(depth.min(16));
345 let summary = node_summary(node, self.focused == Some(id), true);
346 let mut line = String::with_capacity(indent.len() + summary.len());
347 line.push_str(&indent);
348 line.push_str(&summary);
349 lines.push(limit_text(line, policy.max_text_chars));
350 }
351
352 ScreenReaderMirror {
353 lines,
354 omitted_nodes,
355 }
356 }
357
358 pub fn screen_reader_announcements_since(
360 &self,
361 previous: &A11yTree,
362 policy: ScreenReaderPolicy,
363 ) -> ScreenReaderAnnouncements {
364 self.diff(previous)
365 .screen_reader_announcements(self, policy)
366 }
367
368 fn collect_mirror_order(
369 &self,
370 id: u64,
371 depth: usize,
372 visited: &mut AHashSet<u64>,
373 order: &mut Vec<(u64, usize)>,
374 ) {
375 if depth >= MAX_TRAVERSAL_DEPTH || !visited.insert(id) {
376 return;
377 }
378
379 let Some(node) = self.nodes.get(&id) else {
380 return;
381 };
382
383 order.push((id, depth));
384 for child_id in &node.children {
385 self.collect_mirror_order(*child_id, depth + 1, visited, order);
386 }
387 }
388
389 pub fn diff(&self, previous: &A11yTree) -> A11yTreeDiff {
394 let mut added = Vec::new();
395 let mut removed = Vec::new();
396 let mut changed = Vec::new();
397
398 for (&id, node) in &self.nodes {
401 match previous.nodes.get(&id) {
402 None => added.push(id),
403 Some(old) => {
404 let changes = diff_node(old, node);
405 if !changes.is_empty() {
406 changed.push((id, changes));
407 }
408 }
409 }
410 }
411
412 for &id in previous.nodes.keys() {
414 if !self.nodes.contains_key(&id) {
415 removed.push(id);
416 }
417 }
418 added.sort_unstable();
419 removed.sort_unstable();
420 changed.sort_unstable_by_key(|(id, _)| *id);
421
422 let focus_changed = if self.focused != previous.focused {
423 Some((previous.focused, self.focused))
424 } else {
425 None
426 };
427
428 A11yTreeDiff {
429 added,
430 removed,
431 changed,
432 focus_changed,
433 }
434 }
435}
436
437#[derive(Debug, Clone)]
444pub struct A11yTreeDiff {
445 pub added: Vec<u64>,
447 pub removed: Vec<u64>,
449 pub changed: Vec<(u64, Vec<A11yChange>)>,
451 pub focus_changed: Option<(Option<u64>, Option<u64>)>,
454}
455
456impl A11yTreeDiff {
457 #[inline]
459 pub fn is_empty(&self) -> bool {
460 self.added.is_empty()
461 && self.removed.is_empty()
462 && self.changed.is_empty()
463 && self.focus_changed.is_none()
464 }
465
466 pub fn screen_reader_announcements(
472 &self,
473 current: &A11yTree,
474 policy: ScreenReaderPolicy,
475 ) -> ScreenReaderAnnouncements {
476 let mut candidates = Vec::new();
477
478 if let Some((_, Some(new_focus))) = self.focus_changed
479 && let Some(node) = current.node(new_focus)
480 && node.role != A11yRole::Presentation
481 && let Some(text) = announcement_text(node, current.focused == Some(new_focus), false)
482 {
483 candidates.push(ScreenReaderAnnouncement {
484 node_id: Some(new_focus),
485 urgency: LiveRegion::Polite,
486 reason: AnnouncementReason::FocusChanged,
487 text,
488 });
489 }
490
491 for id in &self.added {
492 if let Some(node) = current.node(*id)
493 && let Some(urgency) = node.live_region
494 && let Some(text) = announcement_text(node, current.focused == Some(*id), true)
495 {
496 candidates.push(ScreenReaderAnnouncement {
497 node_id: Some(*id),
498 urgency,
499 reason: AnnouncementReason::LiveRegionAdded,
500 text,
501 });
502 }
503 }
504
505 for (id, changes) in &self.changed {
506 if let Some(node) = current.node(*id)
507 && let Some(urgency) = node.live_region
508 && let Some(reason) = announcement_reason(changes)
509 && let Some(text) = announcement_text(node, current.focused == Some(*id), true)
510 {
511 candidates.push(ScreenReaderAnnouncement {
512 node_id: Some(*id),
513 urgency,
514 reason,
515 text,
516 });
517 }
518 }
519
520 candidates
521 .sort_by(|left, right| announcement_sort_key(left).cmp(&announcement_sort_key(right)));
522
523 let max = policy.max_announcements;
524 let dropped_count = candidates.len().saturating_sub(max);
525 let announcements = candidates
526 .into_iter()
527 .take(max)
528 .map(|mut announcement| {
529 announcement.text = limit_text(announcement.text, policy.max_text_chars);
530 announcement
531 })
532 .collect();
533
534 ScreenReaderAnnouncements {
535 announcements,
536 dropped_count,
537 }
538 }
539}
540
541#[derive(Debug, Clone, Copy, PartialEq, Eq)]
543pub struct ScreenReaderPolicy {
544 pub max_mirror_nodes: usize,
546 pub max_announcements: usize,
548 pub max_text_chars: usize,
550}
551
552impl Default for ScreenReaderPolicy {
553 fn default() -> Self {
554 Self {
555 max_mirror_nodes: 128,
556 max_announcements: 8,
557 max_text_chars: 240,
558 }
559 }
560}
561
562#[derive(Debug, Clone, PartialEq, Eq)]
564pub struct ScreenReaderMirror {
565 pub lines: Vec<String>,
567 pub omitted_nodes: usize,
569}
570
571impl ScreenReaderMirror {
572 #[must_use]
574 pub fn text(&self) -> String {
575 self.lines.join("\n")
576 }
577}
578
579#[derive(Debug, Clone, PartialEq, Eq)]
581pub struct ScreenReaderAnnouncements {
582 pub announcements: Vec<ScreenReaderAnnouncement>,
584 pub dropped_count: usize,
586}
587
588#[derive(Debug, Clone, PartialEq, Eq)]
590pub struct ScreenReaderAnnouncement {
591 pub node_id: Option<u64>,
593 pub urgency: LiveRegion,
595 pub reason: AnnouncementReason,
597 pub text: String,
599}
600
601#[derive(Debug, Clone, Copy, PartialEq, Eq)]
603pub enum AnnouncementReason {
604 FocusChanged,
606 LiveRegionAdded,
608 LiveContentChanged,
610 LiveRegionChanged,
612}
613
614#[derive(Debug, Clone, PartialEq)]
616pub enum A11yChange {
617 NameChanged {
619 old: Option<String>,
620 new: Option<String>,
621 },
622 RoleChanged { old: A11yRole, new: A11yRole },
624 StateChanged { field: String, description: String },
627 BoundsChanged,
629 ChildrenChanged,
631 LiveRegionChanged {
633 old: Option<LiveRegion>,
634 new: Option<LiveRegion>,
635 },
636 DescriptionChanged {
638 old: Option<String>,
639 new: Option<String>,
640 },
641 ShortcutChanged {
643 old: Option<String>,
644 new: Option<String>,
645 },
646 ParentChanged { old: Option<u64>, new: Option<u64> },
648}
649
650fn diff_node(old: &A11yNodeInfo, new: &A11yNodeInfo) -> Vec<A11yChange> {
653 let mut changes = Vec::new();
654
655 if old.name != new.name {
656 changes.push(A11yChange::NameChanged {
657 old: old.name.clone(),
658 new: new.name.clone(),
659 });
660 }
661
662 if old.role != new.role {
663 changes.push(A11yChange::RoleChanged {
664 old: old.role,
665 new: new.role,
666 });
667 }
668
669 if old.bounds != new.bounds {
670 changes.push(A11yChange::BoundsChanged);
671 }
672
673 if old.children != new.children {
674 changes.push(A11yChange::ChildrenChanged);
675 }
676
677 if old.live_region != new.live_region {
678 changes.push(A11yChange::LiveRegionChanged {
679 old: old.live_region,
680 new: new.live_region,
681 });
682 }
683
684 if old.description != new.description {
685 changes.push(A11yChange::DescriptionChanged {
686 old: old.description.clone(),
687 new: new.description.clone(),
688 });
689 }
690
691 if old.shortcut != new.shortcut {
692 changes.push(A11yChange::ShortcutChanged {
693 old: old.shortcut.clone(),
694 new: new.shortcut.clone(),
695 });
696 }
697
698 if old.parent != new.parent {
699 changes.push(A11yChange::ParentChanged {
700 old: old.parent,
701 new: new.parent,
702 });
703 }
704
705 diff_state(&old.state, &new.state, &mut changes);
707
708 changes
709}
710
711fn diff_state(
712 old: &crate::node::A11yState,
713 new: &crate::node::A11yState,
714 changes: &mut Vec<A11yChange>,
715) {
716 macro_rules! check_bool {
717 ($field:ident) => {
718 if old.$field != new.$field {
719 changes.push(A11yChange::StateChanged {
720 field: stringify!($field).to_owned(),
721 description: new.$field.to_string(),
722 });
723 }
724 };
725 }
726
727 macro_rules! check_option {
728 ($field:ident) => {
729 if old.$field != new.$field {
730 changes.push(A11yChange::StateChanged {
731 field: stringify!($field).to_owned(),
732 description: format!("{:?}", new.$field),
733 });
734 }
735 };
736 }
737
738 check_bool!(focused);
739 check_bool!(disabled);
740 check_option!(checked);
741 check_option!(expanded);
742 check_bool!(selected);
743 check_bool!(readonly);
744 check_bool!(required);
745 check_bool!(busy);
746 check_option!(value_now);
747 check_option!(value_min);
748 check_option!(value_max);
749
750 if old.value_text != new.value_text {
751 changes.push(A11yChange::StateChanged {
752 field: "value_text".to_owned(),
753 description: new.value_text.as_deref().unwrap_or("<none>").to_owned(),
754 });
755 }
756}
757
758fn announcement_reason(changes: &[A11yChange]) -> Option<AnnouncementReason> {
759 if changes
760 .iter()
761 .any(|change| matches!(change, A11yChange::LiveRegionChanged { .. }))
762 {
763 return Some(AnnouncementReason::LiveRegionChanged);
764 }
765
766 changes
767 .iter()
768 .any(|change| {
769 matches!(
770 change,
771 A11yChange::NameChanged { .. }
772 | A11yChange::DescriptionChanged { .. }
773 | A11yChange::RoleChanged { .. }
774 ) || matches!(
775 change,
776 A11yChange::StateChanged { field, .. }
777 if matches!(
778 field.as_str(),
779 "busy" | "checked" | "expanded" | "selected" | "value_now" | "value_text"
780 )
781 )
782 })
783 .then_some(AnnouncementReason::LiveContentChanged)
784}
785
786fn announcement_sort_key(announcement: &ScreenReaderAnnouncement) -> (u8, u8, Option<u64>, &str) {
787 let reason_rank = match announcement.reason {
788 AnnouncementReason::FocusChanged => 0,
789 AnnouncementReason::LiveRegionChanged => 1,
790 AnnouncementReason::LiveRegionAdded | AnnouncementReason::LiveContentChanged => 2,
791 };
792 let urgency_rank = match announcement.urgency {
793 LiveRegion::Assertive => 0,
794 LiveRegion::Polite => 1,
795 };
796 (
797 reason_rank,
798 urgency_rank,
799 announcement.node_id,
800 announcement.text.as_str(),
801 )
802}
803
804fn announcement_text(node: &A11yNodeInfo, focused: bool, require_content: bool) -> Option<String> {
805 if node.role == A11yRole::Presentation {
806 return None;
807 }
808 if require_content && !has_announcement_content(node) {
809 return None;
810 }
811
812 let text = node_summary(node, focused, false);
813 normalized_text(&text)
814}
815
816fn has_announcement_content(node: &A11yNodeInfo) -> bool {
817 normalized_option(node.name.as_deref()).is_some()
818 || normalized_option(node.description.as_deref()).is_some()
819 || !state_summaries(&node.state).is_empty()
820}
821
822fn node_summary(node: &A11yNodeInfo, focused: bool, include_live_region: bool) -> String {
823 let mut parts = Vec::new();
824 let mut heading = node.role.to_string();
825
826 if let Some(name) = normalized_option(node.name.as_deref()) {
827 heading.push_str(": ");
828 heading.push_str(&name);
829 }
830 parts.push(heading);
831
832 if let Some(description) = normalized_option(node.description.as_deref())
833 && normalized_option(node.name.as_deref()) != Some(description.clone())
834 {
835 parts.push(description);
836 }
837
838 let mut states = state_summaries(&node.state);
839 if focused || node.state.focused {
840 states.insert(0, "focused".to_owned());
841 }
842 if !states.is_empty() {
843 parts.push(states.join(", "));
844 }
845
846 if let Some(shortcut) = normalized_option(node.shortcut.as_deref()) {
847 parts.push(format!("shortcut {shortcut}"));
848 }
849
850 if include_live_region && let Some(region) = node.live_region {
851 parts.push(format!("live {region}"));
852 }
853
854 parts.join(". ")
855}
856
857fn state_summaries(state: &crate::node::A11yState) -> Vec<String> {
858 let mut states = Vec::new();
859 if state.disabled {
860 states.push("disabled".to_owned());
861 }
862 if let Some(checked) = state.checked {
863 states.push(if checked { "checked" } else { "not checked" }.to_owned());
864 }
865 if let Some(expanded) = state.expanded {
866 states.push(if expanded { "expanded" } else { "collapsed" }.to_owned());
867 }
868 if state.selected {
869 states.push("selected".to_owned());
870 }
871 if state.readonly {
872 states.push("read only".to_owned());
873 }
874 if state.required {
875 states.push("required".to_owned());
876 }
877 if state.busy {
878 states.push("busy".to_owned());
879 }
880 if let Some(value_text) = normalized_option(state.value_text.as_deref()) {
881 states.push(format!("value {value_text}"));
882 } else if let Some(value_now) = state.value_now {
883 states.push(format!("value {value_now}"));
884 }
885 states
886}
887
888fn normalized_option(value: Option<&str>) -> Option<String> {
889 value.and_then(normalized_text)
890}
891
892fn normalized_text(value: &str) -> Option<String> {
893 let mut normalized = String::new();
894 for word in value.split_whitespace() {
895 if !normalized.is_empty() {
896 normalized.push(' ');
897 }
898 normalized.push_str(word);
899 }
900 (!normalized.is_empty()).then_some(normalized)
901}
902
903fn limit_text(text: String, max_chars: usize) -> String {
904 if max_chars == 0 {
905 return String::new();
906 }
907 if text.chars().count() <= max_chars {
908 return text;
909 }
910 text.chars().take(max_chars).collect()
911}