frust_core/
semantics.rs

1//! The semantics seam: a pull-based accessibility tree pass.
2//!
3//! A widget optionally contributes an [`accesskit::Node`] from
4//! [`Widget::semantics`](crate::widget::Widget::semantics). The pass mirrors paint:
5//! [`ChildPod::semantics_child`](crate::widget::ChildPod::semantics_child) threads the
6//! absolute origin into each child, and
7//! [`RenderRoot::semantics`](crate::app::RenderRoot::semantics) runs it after layout
8//! and returns a [`SemanticsUpdate`] for a shell's `accesskit_*` adapter.
9//!
10//! A leaf calls [`SemanticsCtx::push_node`]; a container with semantic children
11//! calls [`SemanticsCtx::push_container`] and recurses in `visit`; a transparent
12//! container (Flex, Stack, Padding) only calls `semantics_child` on each child.
13
14use std::num::NonZeroU64;
15
16use accesskit::{Node, NodeId, Rect as AccessRect, Role};
17use kurbo::{Point, Size, Vec2};
18
19/// The fixed id of the synthetic window node every tree is rooted at; never
20/// drawn from the per-pod allocator, so it is stable across frames.
21pub const ROOT_NODE_ID: NodeId = NodeId(1);
22
23/// Low bits of a composed [`NodeId`] holding the per-pod slot: a widget's own
24/// node is slot `0`, extra nodes it pushes take `1, 2, …` in push order. Ids
25/// stay stable and collision-free while one widget pushes fewer than `2^16`.
26const SLOT_BITS: u32 = 16;
27
28/// `(base << SLOT_BITS) | slot`. `base` is a never-reused per-pod id `>= 2`, so
29/// no composed id equals [`ROOT_NODE_ID`]; injective while `base < 2^48`.
30pub(crate) fn compose_node_id(base: NonZeroU64, slot: u16) -> NodeId {
31    debug_assert!(
32        base.get() < (1u64 << (64 - SLOT_BITS)),
33        "semantics base id {} overflows the {}-bit base field",
34        base.get(),
35        64 - SLOT_BITS
36    );
37    NodeId((base.get() << SLOT_BITS) | slot as u64)
38}
39
40/// A collected accessibility tree from
41/// [`RenderRoot::semantics`](crate::app::RenderRoot::semantics).
42#[derive(Clone, Debug, PartialEq)]
43pub struct SemanticsUpdate {
44    /// The flat node map in collection order: each container follows its
45    /// children (post-order), so the root window node comes last.
46    pub nodes: Vec<(NodeId, Node)>,
47    /// The window node, present even for an empty tree.
48    pub root: NodeId,
49    /// The node a widget claimed with [`SemanticsCtx::set_focused`], if any.
50    pub focus: Option<NodeId>,
51}
52
53impl SemanticsUpdate {
54    /// The focus to hand an adapter: [`focus`](Self::focus), else
55    /// [`root`](Self::root), since accesskit's `TreeUpdate::focus` is not optional.
56    pub fn focus_id(&self) -> NodeId {
57        self.focus.unwrap_or(self.root)
58    }
59}
60
61/// Collects nodes during a semantics pass, threading the absolute origin/size
62/// and the parent/child structure.
63///
64/// Node ids are stable across passes: each is composed from the owning pod's
65/// persistent base id and a per-pod slot, so a widget keeps its id every frame,
66/// keyed reorders included, as assistive-technology focus continuity requires.
67pub struct SemanticsCtx {
68    origin: Point,
69    size: Size,
70    /// Fallback id counter for a node pushed with no pod base in scope (the
71    /// direct-`push_node` unit tests only).
72    next_id: u64,
73    /// The base allocator's next value; the root reads it back after the pass so
74    /// a base is never reused.
75    next_base: u64,
76    /// The pod being visited; `None` at the window-root level.
77    current_base: Option<NonZeroU64>,
78    current_slot: u16,
79    nodes: Vec<(NodeId, Node)>,
80    /// One frame per nesting level, gathering the child ids its container sets.
81    frames: Vec<Vec<NodeId>>,
82    focus: Option<NodeId>,
83}
84
85impl SemanticsCtx {
86    /// A pass over a `window_size` root with the base allocator at `next_base`;
87    /// one root-level child frame is open.
88    pub(crate) fn new(window_size: Size, next_base: u64) -> Self {
89        Self {
90            origin: Point::ZERO,
91            size: window_size,
92            next_id: 0,
93            next_base,
94            current_base: None,
95            current_slot: 0,
96            nodes: Vec::new(),
97            frames: vec![Vec::new()],
98            focus: None,
99        }
100    }
101
102    /// The absolute origin of the widget being visited.
103    pub fn origin(&self) -> Point {
104        self.origin
105    }
106
107    /// The size of the widget being visited.
108    pub fn size(&self) -> Size {
109        self.size
110    }
111
112    /// Allocate a persistent pod base id; a pod calls this on its first visit and
113    /// caches the result for its lifetime.
114    pub(crate) fn alloc_base(&mut self) -> NonZeroU64 {
115        let id = self.next_base;
116        self.next_base += 1;
117        NonZeroU64::new(id).expect("base allocator is seeded >= 2, never zero")
118    }
119
120    pub(crate) fn next_base(&self) -> u64 {
121        self.next_base
122    }
123
124    fn alloc_id(&mut self) -> NodeId {
125        let id = NodeId(self.next_id);
126        self.next_id += 1;
127        id
128    }
129
130    /// The current pod's next composed id, else the fallback counter.
131    fn next_node_id(&mut self) -> NodeId {
132        match self.current_base {
133            Some(base) => {
134                let slot = self.current_slot;
135                self.current_slot = self
136                    .current_slot
137                    .checked_add(1)
138                    .expect("a single widget contributes fewer than 2^16 nodes per pod");
139                compose_node_id(base, slot)
140            }
141            None => self.alloc_id(),
142        }
143    }
144
145    /// Absolute, top-down bounds of the widget being visited.
146    fn bounds(&self) -> AccessRect {
147        AccessRect {
148            x0: self.origin.x,
149            y0: self.origin.y,
150            x1: self.origin.x + self.size.width,
151            y1: self.origin.y + self.size.height,
152        }
153    }
154
155    /// Contribute a leaf node of `role` with bounds from the current geometry;
156    /// `build` sets label and state. Returns its id.
157    pub fn push_node(&mut self, role: Role, build: impl FnOnce(&mut Node)) -> NodeId {
158        let id = self.next_node_id();
159        let mut node = Node::new(role);
160        node.set_bounds(self.bounds());
161        build(&mut node);
162        self.attach(id, node);
163        id
164    }
165
166    /// Contribute a container node whose children are the nodes contributed
167    /// during `visit`; it is stored after them (post-order).
168    pub fn push_container(
169        &mut self,
170        role: Role,
171        build: impl FnOnce(&mut Node),
172        visit: impl FnOnce(&mut SemanticsCtx),
173    ) -> NodeId {
174        let id = self.next_node_id();
175        self.push_container_inner(id, role, build, visit)
176    }
177
178    /// [`push_container`](Self::push_container) under a caller-chosen `id` (the
179    /// window node's [`ROOT_NODE_ID`]).
180    pub(crate) fn push_container_with_id(
181        &mut self,
182        id: NodeId,
183        role: Role,
184        build: impl FnOnce(&mut Node),
185        visit: impl FnOnce(&mut SemanticsCtx),
186    ) -> NodeId {
187        self.push_container_inner(id, role, build, visit)
188    }
189
190    fn push_container_inner(
191        &mut self,
192        id: NodeId,
193        role: Role,
194        build: impl FnOnce(&mut Node),
195        visit: impl FnOnce(&mut SemanticsCtx),
196    ) -> NodeId {
197        let mut node = Node::new(role);
198        node.set_bounds(self.bounds());
199        build(&mut node);
200        self.frames.push(Vec::new());
201        visit(self);
202        let children = self.frames.pop().expect("container frame was just pushed");
203        node.set_children(children);
204        self.attach(id, node);
205        id
206    }
207
208    fn attach(&mut self, id: NodeId, node: Node) {
209        self.frames
210            .last_mut()
211            .expect("a child frame is always open during a pass")
212            .push(id);
213        self.nodes.push((id, node));
214    }
215
216    /// Record `id` as the focused node; the last call in a pass wins.
217    pub fn set_focused(&mut self, id: NodeId) {
218        self.focus = Some(id);
219    }
220
221    /// Run `f` translated by `child_offset` into a `child_size` child, restoring
222    /// the geometry after. Geometry only; for the unit tests without a pod.
223    #[cfg(test)]
224    pub(crate) fn descend(
225        &mut self,
226        child_offset: Vec2,
227        child_size: Size,
228        f: impl FnOnce(&mut Self),
229    ) {
230        let saved_origin = self.origin;
231        let saved_size = self.size;
232        self.origin = saved_origin + child_offset;
233        self.size = child_size;
234        f(self);
235        self.origin = saved_origin;
236        self.size = saved_size;
237    }
238
239    /// Like `descend`, and also enter pod `base`'s id scope with the slot reset;
240    /// geometry, base and slot are all restored after.
241    pub(crate) fn descend_into_pod(
242        &mut self,
243        base: NonZeroU64,
244        child_offset: Vec2,
245        child_size: Size,
246        f: impl FnOnce(&mut Self),
247    ) {
248        let saved_origin = self.origin;
249        let saved_size = self.size;
250        let saved_base = self.current_base;
251        let saved_slot = self.current_slot;
252        self.origin = saved_origin + child_offset;
253        self.size = child_size;
254        self.current_base = Some(base);
255        self.current_slot = 0;
256        f(self);
257        self.origin = saved_origin;
258        self.size = saved_size;
259        self.current_base = saved_base;
260        self.current_slot = saved_slot;
261    }
262
263    pub(crate) fn finish(self, root: NodeId) -> SemanticsUpdate {
264        SemanticsUpdate {
265            nodes: self.nodes,
266            root,
267            focus: self.focus,
268        }
269    }
270}
271
272#[cfg(test)]
273mod tests {
274    use super::*;
275
276    /// The base seed a `RenderRoot` passes on the first pass (ids 0 and 1 are
277    /// reserved: 0 keeps `NonZeroU64` valid, 1 is the window root).
278    const BASE_SEED: u64 = 2;
279
280    #[test]
281    fn alloc_ids_are_sequential_and_deterministic() {
282        let mut ctx = SemanticsCtx::new(Size::new(100.0, 100.0), BASE_SEED);
283        assert_eq!(ctx.alloc_id(), NodeId(0));
284        assert_eq!(ctx.alloc_id(), NodeId(1));
285        assert_eq!(ctx.alloc_id(), NodeId(2));
286    }
287
288    #[test]
289    fn push_node_sets_absolute_bounds_from_origin_and_size() {
290        let mut ctx = SemanticsCtx::new(Size::new(200.0, 200.0), BASE_SEED);
291        // Descend into a child placed at (10, 20) sized 30x40.
292        ctx.descend(Vec2::new(10.0, 20.0), Size::new(30.0, 40.0), |ctx| {
293            let id = ctx.push_node(Role::Label, |node| node.set_label("hi"));
294            assert_eq!(id, NodeId(0));
295        });
296        let (_, node) = &ctx.nodes[0];
297        assert_eq!(
298            node.bounds(),
299            Some(AccessRect {
300                x0: 10.0,
301                y0: 20.0,
302                x1: 40.0,
303                y1: 60.0,
304            })
305        );
306        assert_eq!(node.label(), Some("hi"));
307        assert_eq!(node.role(), Role::Label);
308    }
309
310    #[test]
311    fn descend_composes_nested_origins() {
312        // A grandchild's absolute origin is the sum of the whole ancestor chain,
313        // mirroring paint_child's `ctx.origin() + pod.origin`.
314        let mut ctx = SemanticsCtx::new(Size::new(500.0, 500.0), BASE_SEED);
315        ctx.descend(Vec2::new(100.0, 200.0), Size::new(300.0, 300.0), |ctx| {
316            ctx.descend(Vec2::new(5.0, 7.0), Size::new(10.0, 10.0), |ctx| {
317                ctx.push_node(Role::Button, |_| {});
318            });
319        });
320        let (_, node) = &ctx.nodes[0];
321        assert_eq!(
322            node.bounds(),
323            Some(AccessRect {
324                x0: 105.0,
325                y0: 207.0,
326                x1: 115.0,
327                y1: 217.0,
328            })
329        );
330    }
331
332    #[test]
333    fn push_container_collects_children_and_restores_frame() {
334        let mut ctx = SemanticsCtx::new(Size::new(100.0, 100.0), BASE_SEED);
335        let container = ctx.push_container(
336            Role::ScrollView,
337            |_| {},
338            |ctx| {
339                ctx.push_node(Role::Label, |n| n.set_label("a"));
340                ctx.push_node(Role::Label, |n| n.set_label("b"));
341            },
342        );
343        // The container is the last node pushed (post-order); its children are the
344        // two labels, allocated ids 1 and 2 (container reserved id 0).
345        assert_eq!(container, NodeId(0));
346        let update = ctx.finish(container);
347        // Flat map order: label a (1), label b (2), then the container (0).
348        assert_eq!(update.nodes.len(), 3);
349        let container_node = &update
350            .nodes
351            .iter()
352            .find(|(id, _)| *id == container)
353            .unwrap()
354            .1;
355        assert_eq!(container_node.children(), &[NodeId(1), NodeId(2)]);
356    }
357
358    #[test]
359    fn set_focused_records_the_focus_node() {
360        let mut ctx = SemanticsCtx::new(Size::new(10.0, 10.0), BASE_SEED);
361        let id = ctx.push_node(Role::TextInput, |_| {});
362        ctx.set_focused(id);
363        let update = ctx.finish(id);
364        assert_eq!(update.focus, Some(id));
365    }
366
367    #[test]
368    fn focus_id_defaults_to_root_when_unfocused() {
369        let mut ctx = SemanticsCtx::new(Size::new(10.0, 10.0), BASE_SEED);
370        let root = ctx.push_container(Role::Window, |_| {}, |_| {});
371        let update = ctx.finish(root);
372        assert!(update.focus.is_none());
373        // With nothing focused, the adapter-facing focus id is the root itself.
374        assert_eq!(update.focus_id(), update.root);
375    }
376
377    #[test]
378    fn compose_node_id_is_collision_free_across_bases_and_slots() {
379        // Distinct (base, slot) pairs must map to distinct ids, and one base's
380        // slot range must never overlap the next base's — the property the
381        // stable-id scheme relies on.
382        use std::collections::HashSet;
383        let mut seen = HashSet::new();
384        for base in 2u64..40 {
385            let base = NonZeroU64::new(base).unwrap();
386            for slot in 0u16..1000 {
387                let id = compose_node_id(base, slot);
388                assert!(id != ROOT_NODE_ID, "never collides with the reserved root");
389                assert!(seen.insert(id), "duplicate id for base={base} slot={slot}");
390            }
391        }
392        // The max slot of one base sits strictly below the next base's slot 0.
393        let a = NonZeroU64::new(2).unwrap();
394        let b = NonZeroU64::new(3).unwrap();
395        assert!(compose_node_id(a, u16::MAX).0 < compose_node_id(b, 0).0);
396    }
397
398    #[test]
399    fn descend_into_pod_composes_stable_ids_and_restores_scope() {
400        let mut ctx = SemanticsCtx::new(Size::new(100.0, 100.0), BASE_SEED);
401        let base = ctx.alloc_base();
402        assert_eq!(base.get(), BASE_SEED);
403        // A widget contributing two nodes for its pod gets slots 0 and 1.
404        let (first, second) = {
405            let mut ids = (NodeId(0), NodeId(0));
406            ctx.descend_into_pod(base, Vec2::ZERO, Size::new(10.0, 10.0), |ctx| {
407                ids.0 = ctx.push_node(Role::Label, |_| {});
408                ids.1 = ctx.push_node(Role::Label, |_| {});
409            });
410            ids
411        };
412        assert_eq!(first, compose_node_id(base, 0));
413        assert_eq!(second, compose_node_id(base, 1));
414        // After the pod scope closes, a fresh pod at the top level uses the
415        // fallback sequential id (no base in scope) — proving the base/slot were
416        // restored rather than leaking out.
417        let outside = ctx.push_node(Role::Label, |_| {});
418        assert_eq!(outside, NodeId(0));
419    }
420}
frust_core/semantics.rs

frust_core/
semantics.rs
