layout/
accessibility_tree.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4use std::collections::VecDeque;
5use std::sync::atomic::AtomicU64;
6use std::sync::{LazyLock, atomic};
7
8use accesskit::Role;
9use layout_api::{LayoutElement, LayoutNode, LayoutNodeType};
10use log::trace;
11use rustc_hash::{FxHashMap, FxHashSet};
12use script::layout_dom::ServoLayoutNode;
13use servo_base::Epoch;
14use style::dom::{NodeInfo, OpaqueNode};
15use web_atoms::{LocalName, local_name};
16
17use crate::ArcRefCell;
18
19/// An in-progress [`accesskit::TreeUpdate`] that automatically avoids storing any node twice.
20struct AccessibilityUpdate {
21    accesskit_update: accesskit::TreeUpdate,
22    nodes: FxHashMap<accesskit::NodeId, accesskit::Node>,
23}
24
25#[derive(Debug)]
26struct AccessibilityNode {
27    id: accesskit::NodeId,
28    accesskit_node: accesskit::Node,
29    opaque_node: Option<OpaqueNode>,
30    updated: bool,
31}
32
33/// A retained, internal representation of the accessibility tree for a document.
34///
35/// [`accesskit`] only provides interchange types for tree updates and action requests, so we need
36/// to define our own representation for incremental tree building.
37#[derive(Debug)]
38pub struct AccessibilityTree {
39    nodes: FxHashMap<accesskit::NodeId, ArcRefCell<AccessibilityNode>>,
40    opaque_node_to_id: FxHashMap<OpaqueNode, accesskit::NodeId>,
41    tree_id: accesskit::TreeId,
42    epoch: Epoch,
43}
44
45impl AccessibilityTree {
46    pub(super) fn new(tree_id: accesskit::TreeId, epoch: Epoch) -> Self {
47        Self {
48            nodes: FxHashMap::default(),
49            opaque_node_to_id: FxHashMap::default(),
50            tree_id,
51            epoch,
52        }
53    }
54
55    /// Update this tree based on the current state of the given DOM tree, and if anything changed,
56    /// return an [`accesskit::TreeUpdate`] representing what changed.
57    pub(super) fn update_tree(
58        &mut self,
59        root_dom_node: &ServoLayoutNode<'_>,
60    ) -> Option<accesskit::TreeUpdate> {
61        let root_node = self.get_or_create_node(root_dom_node);
62        let mut tree_update =
63            AccessibilityUpdate::new(accesskit::Tree::new(root_node.borrow().id), self.tree_id);
64        let any_node_updated = self.update_node_and_descendants(root_dom_node, &mut tree_update);
65
66        if !any_node_updated {
67            return None;
68        }
69
70        Some(tree_update.finalize())
71    }
72
73    /// Update this tree starting at the given DOM node, adding any changed nodes to the given
74    /// [`AccessibilityUpdate`].
75    fn update_node_and_descendants(
76        &mut self,
77        dom_node: &ServoLayoutNode<'_>,
78        tree_update: &mut AccessibilityUpdate,
79    ) -> bool {
80        let node = self.assert_node_by_dom_node(dom_node);
81        let mut node = node.borrow_mut();
82
83        // TODO: read accessibility damage (right now, assume damage is complete)
84        let any_descendant_updated = node.update_descendants(dom_node, self, tree_update);
85
86        node.update_node(dom_node, self, any_descendant_updated);
87
88        if node.updated {
89            tree_update.add(&mut node);
90            return true;
91        }
92
93        any_descendant_updated
94    }
95
96    fn get_or_create_node(
97        &mut self,
98        dom_node: &ServoLayoutNode<'_>,
99    ) -> ArcRefCell<AccessibilityNode> {
100        let id = self.id_for_opaque(dom_node.opaque());
101
102        let node = self
103            .nodes
104            .entry(id)
105            .or_insert_with(|| ArcRefCell::new(AccessibilityNode::new(id)));
106        {
107            let mut new_node = node.borrow_mut();
108
109            new_node.opaque_node = Some(dom_node.opaque());
110            if let Some(dom_element) = dom_node.as_element() {
111                let local_name = dom_element.local_name().to_ascii_lowercase();
112                new_node.set_html_tag(&local_name);
113            }
114        }
115
116        node.clone()
117    }
118
119    fn assert_node_by_dom_node(
120        &mut self,
121        dom_node: &ServoLayoutNode<'_>,
122    ) -> ArcRefCell<AccessibilityNode> {
123        let id = self.id_for_opaque(dom_node.opaque());
124        let node = self.assert_node_by_id(id);
125        assert!(node.borrow().opaque_node == Some(dom_node.opaque()));
126        node
127    }
128
129    fn assert_node_by_id(&self, id: accesskit::NodeId) -> ArcRefCell<AccessibilityNode> {
130        let Some(node) = self.nodes.get(&id) else {
131            panic!("Stale node ID found: {id:?}");
132        };
133        node.clone()
134    }
135
136    fn id_for_opaque(&mut self, opaque: OpaqueNode) -> accesskit::NodeId {
137        let id = self.opaque_node_to_id.entry(opaque).or_insert_with(|| {
138            static LAST_ID: AtomicU64 = AtomicU64::new(0);
139            LAST_ID.fetch_add(1, atomic::Ordering::SeqCst).into()
140        });
141        *id
142    }
143
144    pub(crate) fn epoch(&self) -> Epoch {
145        self.epoch
146    }
147}
148
149fn role_from_dom_node(dom_node: &ServoLayoutNode<'_>) -> Role {
150    if let Some(dom_element) = dom_node.as_element() {
151        let local_name = dom_element.local_name().to_ascii_lowercase();
152        *HTML_ELEMENT_ROLE_MAPPINGS
153            .get(&local_name)
154            .unwrap_or(&Role::GenericContainer)
155    } else if dom_node.type_id() == Some(LayoutNodeType::Text) {
156        Role::TextRun
157    } else {
158        Role::GenericContainer
159    }
160}
161
162impl AccessibilityNode {
163    fn new(id: accesskit::NodeId) -> Self {
164        Self::new_with_role(id, Role::Unknown)
165    }
166
167    fn new_with_role(id: accesskit::NodeId, role: accesskit::Role) -> Self {
168        Self {
169            id,
170            accesskit_node: accesskit::Node::new(role),
171            opaque_node: None,
172            updated: true,
173        }
174    }
175
176    fn update_descendants<'dom>(
177        &mut self,
178        dom_node: &ServoLayoutNode<'dom>,
179        tree: &mut AccessibilityTree,
180        tree_update: &mut AccessibilityUpdate,
181    ) -> bool {
182        let mut any_descendant_updated = false;
183        let new_children = dom_node
184            .flat_tree_children()
185            .map(|dom_child| {
186                let child_node = tree.get_or_create_node(&dom_child);
187                let child_node_id = child_node.borrow().id;
188
189                // TODO: We actually need to propagate damage within the accessibility tree, rather than
190                // assuming it matches the DOM tree, but this will do for now.
191                any_descendant_updated |= tree.update_node_and_descendants(&dom_child, tree_update);
192
193                child_node_id
194            })
195            .collect();
196        if new_children != self.children() {
197            self.set_children(new_children);
198        }
199        any_descendant_updated
200    }
201
202    fn update_node(
203        &mut self,
204        dom_node: &ServoLayoutNode<'_>,
205        tree: &mut AccessibilityTree,
206        any_descendant_updated: bool,
207    ) {
208        self.set_role(role_from_dom_node(dom_node));
209        if dom_node.is_element() {
210            if any_descendant_updated {
211                if let Some(text) = self.label_from_descendants(tree) {
212                    self.set_label(text.as_str());
213                }
214            }
215        } else if dom_node.type_id() == Some(LayoutNodeType::Text) {
216            let text_content = dom_node.text_content();
217            trace!("node text content = {text_content:?}");
218            // FIXME: this should take into account editing selection units (grapheme clusters?)
219            self.set_value(&text_content);
220        }
221    }
222
223    fn label_from_descendants(&self, tree: &AccessibilityTree) -> Option<String> {
224        if !NAME_FROM_CONTENTS_ROLES.contains(&self.role()) {
225            return None;
226        }
227        let mut children = VecDeque::from_iter(self.children().iter().copied());
228        let mut text = String::new();
229        while let Some(child_id) = children.pop_front() {
230            let child = tree.assert_node_by_id(child_id);
231            let child = child.borrow();
232            match child.role() {
233                Role::TextRun => {
234                    if let Some(child_text) = child.value() {
235                        text.push_str(child_text);
236                    }
237                },
238                _ => {
239                    for id in child.children().iter().rev() {
240                        children.push_front(*id);
241                    }
242                },
243            }
244        }
245        Some(text.trim().to_owned())
246    }
247
248    // TODO: use macros to generate getter/setter methods.
249
250    fn children(&self) -> &[accesskit::NodeId] {
251        self.accesskit_node.children()
252    }
253
254    fn set_children(&mut self, children: Vec<accesskit::NodeId>) {
255        self.accesskit_node.set_children(children);
256        self.updated = true;
257    }
258
259    fn role(&self) -> accesskit::Role {
260        self.accesskit_node.role()
261    }
262
263    fn set_role(&mut self, role: accesskit::Role) {
264        if role == self.accesskit_node.role() {
265            return;
266        }
267        self.accesskit_node.set_role(role);
268        self.updated = true;
269    }
270
271    #[expect(dead_code)]
272    fn label(&self) -> Option<&str> {
273        self.accesskit_node.label()
274    }
275
276    fn set_label(&mut self, label: &str) {
277        if Some(label) == self.accesskit_node.label() {
278            return;
279        }
280        self.accesskit_node.set_label(label);
281        self.updated = true;
282    }
283
284    #[expect(dead_code)]
285    fn html_tag(&self) -> Option<&str> {
286        self.accesskit_node.html_tag()
287    }
288
289    fn set_html_tag(&mut self, html_tag: &str) {
290        if Some(html_tag) == self.accesskit_node.html_tag() {
291            return;
292        }
293        self.accesskit_node.set_html_tag(html_tag);
294        self.updated = true;
295    }
296
297    fn value(&self) -> Option<&str> {
298        self.accesskit_node.value()
299    }
300
301    fn set_value(&mut self, value: &str) {
302        if Some(value) == self.accesskit_node.value() {
303            return;
304        }
305        self.accesskit_node.set_value(value);
306        self.updated = true;
307    }
308}
309
310impl AccessibilityUpdate {
311    fn new(tree: accesskit::Tree, tree_id: accesskit::TreeId) -> Self {
312        Self {
313            accesskit_update: accesskit::TreeUpdate {
314                nodes: vec![],
315                tree: Some(tree),
316                focus: accesskit::NodeId(1),
317                tree_id,
318            },
319            nodes: FxHashMap::default(),
320        }
321    }
322
323    fn add(&mut self, node: &mut AccessibilityNode) {
324        self.nodes.insert(node.id, node.accesskit_node.clone());
325        node.updated = false;
326    }
327
328    fn finalize(mut self) -> accesskit::TreeUpdate {
329        self.accesskit_update.nodes.extend(self.nodes.drain());
330        self.accesskit_update
331    }
332}
333
334#[cfg(test)]
335#[test]
336fn test_accessibility_update_add_some_nodes_twice() {
337    let mut update = AccessibilityUpdate::new(
338        accesskit::Tree {
339            root: accesskit::NodeId(2),
340            toolkit_name: None,
341            toolkit_version: None,
342        },
343        accesskit::TreeId::ROOT,
344    );
345    update.add(&mut AccessibilityNode::new_with_role(
346        accesskit::NodeId(5),
347        Role::Paragraph,
348    ));
349    update.add(&mut AccessibilityNode::new_with_role(
350        accesskit::NodeId(3),
351        Role::GenericContainer,
352    ));
353    update.add(&mut AccessibilityNode::new_with_role(
354        accesskit::NodeId(4),
355        Role::Heading,
356    ));
357    update.add(&mut AccessibilityNode::new_with_role(
358        accesskit::NodeId(4),
359        Role::Heading,
360    ));
361    update.add(&mut AccessibilityNode::new_with_role(
362        accesskit::NodeId(3),
363        Role::ScrollView,
364    ));
365    let mut tree_update = update.finalize();
366    tree_update.nodes.sort_by_key(|(node_id, _node)| *node_id);
367    assert_eq!(
368        tree_update,
369        accesskit::TreeUpdate {
370            nodes: vec![
371                (accesskit::NodeId(3), accesskit::Node::new(Role::ScrollView)),
372                (accesskit::NodeId(4), accesskit::Node::new(Role::Heading)),
373                (accesskit::NodeId(5), accesskit::Node::new(Role::Paragraph)),
374            ],
375            tree: Some(accesskit::Tree {
376                root: accesskit::NodeId(2),
377                toolkit_name: None,
378                toolkit_version: None
379            }),
380            tree_id: accesskit::TreeId::ROOT,
381            focus: accesskit::NodeId(1),
382        }
383    );
384}
385
386static HTML_ELEMENT_ROLE_MAPPINGS: LazyLock<FxHashMap<LocalName, Role>> = LazyLock::new(|| {
387    [
388        (local_name!("article"), Role::Article),
389        (local_name!("aside"), Role::Complementary),
390        (local_name!("body"), Role::RootWebArea),
391        (local_name!("footer"), Role::ContentInfo),
392        (local_name!("h1"), Role::Heading),
393        (local_name!("h2"), Role::Heading),
394        (local_name!("h3"), Role::Heading),
395        (local_name!("h4"), Role::Heading),
396        (local_name!("h5"), Role::Heading),
397        (local_name!("h6"), Role::Heading),
398        (local_name!("header"), Role::Banner),
399        (local_name!("hr"), Role::Splitter),
400        (local_name!("main"), Role::Main),
401        (local_name!("nav"), Role::Navigation),
402        (local_name!("p"), Role::Paragraph),
403    ]
404    .into_iter()
405    .collect()
406});
407
408/// <https://w3c.github.io/aria/#namefromcontent>
409static NAME_FROM_CONTENTS_ROLES: LazyLock<FxHashSet<Role>> =
410    LazyLock::new(|| [(Role::Heading)].into_iter().collect());
layout/accessibility_tree.rs

layout/
accessibility_tree.rs
