GPU-accelerated UI toolkit (Vulkan)
git clone https://git.lucas.co/cce-ui.git
src/scene/tree.rs (16K)
1 //! `WidgetTree` — the arena-backed replacement for `UiContext`'s two tree stores.
2 //!
3 //! Today `UiContext` keeps the widget tree in two parallel `HashMap`s that must be maintained in
4 //! lockstep by hand:
5 //! * `widget_registry: HashMap<WidgetId, *mut dyn WidgetHost>` — id → live pointer, and
6 //! * `layout_tree: { parents: HashMap<WidgetId, WidgetId>, children: HashMap<WidgetId, Vec<WidgetId>> }`.
7 //!
8 //! This type folds both into a single generational [`Arena`], keyed through a `WidgetId → NodeId`
9 //! index so the *public* `WidgetId`-based API (`register_widget`, `link_ids`, `clear_hierarchy`,
10 //! …) can be preserved unchanged for the app crates. Consolidating the stores removes the
11 //! hand-sync burden, and the generational [`NodeId`] means a removed widget's handle reads back as
12 //! `None` instead of dereferencing freed memory.
13 //!
14 //! ## One deliberate semantic change vs. the legacy maps
15 //!
16 //! The legacy maps are sometimes left **asymmetric**: `WidgetHost::set_parent(Some(p))` writes
17 //! `parents[child] = p` but does *not* add `child` to `children[p]`; `plate`/`parameters_bg`
18 //! detach by doing `parents.remove(child)` while leaving `child` in `children[p]`. The arena keeps
19 //! parent and child links **symmetric** by construction, so here `set_parent`/`detach` update both
20 //! ends. This is the single behavior difference to watch when swapping `WidgetTree` into
21 //! `UiContext` — it makes the tree self-consistent, but it must be verified against the running
22 //! apps (paint recursion and event propagation both read `children`). See
23 //! `docs/rfc-core-rebuild.md` Phase 1b.
24 //!
25 //! Nothing here is wired into `UiContext` yet; this is the tested drop-in the swap will use.
26
27 use std::collections::HashMap;
28
29 use crate::scene::arena::{Arena, NodeId};
30 use crate::widget::{WidgetHost, WidgetId};
31
32 /// One arena node's payload: the widget's stable id plus its live pointer. The pointer is `None`
33 /// for a node that has been *linked* into the tree (as a parent/child) but not yet *registered*
34 /// with a real widget — mirroring the legacy maps, where a `layout_tree` link can precede the
35 /// `widget_registry` entry. (`*mut dyn WidgetHost` is a fat pointer, so `Option` is the natural
36 /// "absent" representation — there is no thin null to use as a sentinel.)
37 #[derive(Clone, Copy)]
38 struct Entry {
39 id: WidgetId,
40 ptr: Option<*mut (dyn WidgetHost + 'static)>,
41 }
42
43 /// Resolve an entry's pointer to a usable, non-null pointer (skipping link-only and null-data
44 /// pointers exactly as the legacy `filter_map` over the registry did).
45 #[inline]
46 fn live_ptr(entry: &Entry) -> Option<*mut (dyn WidgetHost + 'static)> {
47 match entry.ptr {
48 Some(p) if !p.is_null() => Some(p),
49 _ => None,
50 }
51 }
52
53 /// The consolidated, generational widget tree. See the module docs.
54 pub struct WidgetTree {
55 arena: Arena<Entry>,
56 by_id: HashMap<WidgetId, NodeId>,
57 }
58
59 impl Default for WidgetTree {
60 fn default() -> Self {
61 Self::new()
62 }
63 }
64
65 impl WidgetTree {
66 pub fn new() -> Self {
67 WidgetTree { arena: Arena::new(), by_id: HashMap::new() }
68 }
69
70 /// Number of nodes known to the tree (registered or link-only).
71 pub fn len(&self) -> usize {
72 self.arena.len()
73 }
74
75 pub fn is_empty(&self) -> bool {
76 self.arena.is_empty()
77 }
78
79 /// Get (or lazily create) the arena node for `id`. A freshly created node has a `null`
80 /// pointer until [`register`](WidgetTree::register) supplies one. Re-creates the node if a
81 /// stale `by_id` entry points at a removed slot.
82 fn ensure_node(&mut self, id: WidgetId) -> NodeId {
83 if let Some(&node) = self.by_id.get(&id) {
84 if self.arena.contains(node) {
85 return node;
86 }
87 }
88 let node = self.arena.insert(Entry { id, ptr: None });
89 self.by_id.insert(id, node);
90 node
91 }
92
93 /// Register (or overwrite) the live pointer for `id`. Mirrors `register_widget`'s
94 /// insert-overwrite semantics. Registering a `null` pointer is allowed (the node exists but
95 /// resolves to `None`), matching the legacy behavior where a link can precede registration.
96 pub fn register(&mut self, id: WidgetId, ptr: *mut (dyn WidgetHost + 'static)) {
97 let node = self.ensure_node(id);
98 // `ensure_node` guarantees the node exists.
99 self.arena.value_mut(node).unwrap().ptr = Some(ptr);
100 }
101
102 /// Make `child` a child of `parent` (deduped, reparenting from any previous parent). Mirrors
103 /// `link_ids`, but keeps both ends of the edge consistent. No-op (rather than panic) if the
104 /// link would form a cycle, which the legacy maps never guarded against but also never hit.
105 pub fn link(&mut self, parent: WidgetId, child: WidgetId) {
106 let parent_node = self.ensure_node(parent);
107 let child_node = self.ensure_node(child);
108 if parent_node == child_node || self.arena.is_ancestor(child_node, parent_node) {
109 return;
110 }
111 self.arena.append_child(parent_node, child_node);
112 }
113
114 /// Set or clear `child`'s parent. `Some(p)` links symmetrically (as [`link`](WidgetTree::link));
115 /// `None` detaches `child` from its current parent. Replaces the legacy asymmetric
116 /// `WidgetHost::set_parent`.
117 pub fn set_parent(&mut self, child: WidgetId, parent: Option<WidgetId>) {
118 match parent {
119 Some(p) => self.link(p, child),
120 None => {
121 if let Some(&node) = self.by_id.get(&child) {
122 self.arena.detach(node);
123 }
124 }
125 }
126 }
127
128 /// Remove `child` from `parent` if it is currently a child of it. Mirrors `unlink_child`.
129 pub fn unlink(&mut self, parent: WidgetId, child: WidgetId) {
130 if let (Some(&child_node), Some(&parent_node)) =
131 (self.by_id.get(&child), self.by_id.get(&parent))
132 {
133 if self.arena.parent(child_node) == Some(parent_node) {
134 self.arena.detach(child_node);
135 }
136 }
137 }
138
139 /// Detach all of `parent`'s children, leaving them as (still-registered) roots. Mirrors
140 /// `clear_children_ids`: non-recursive, and it does *not* unregister the child pointers.
141 pub fn clear_children(&mut self, parent: WidgetId) {
142 if let Some(&parent_node) = self.by_id.get(&parent) {
143 let children: Vec<NodeId> = self.arena.children(parent_node).to_vec();
144 for child in children {
145 self.arena.detach(child);
146 }
147 }
148 }
149
150 /// Drop the entire tree. Mirrors `clear_hierarchy`'s reset of both maps.
151 pub fn clear_all(&mut self) {
152 self.arena.clear();
153 self.by_id.clear();
154 }
155
156 /// Remove `id` and its whole subtree, freeing arena slots and dropping their `by_id` entries.
157 /// Not used by the legacy-compatible swap (the old maps never removed individual nodes), but
158 /// available for the migrated code that will actually reclaim removed widgets.
159 pub fn remove(&mut self, id: WidgetId) {
160 let Some(&node) = self.by_id.get(&id) else { return };
161 let removed_ids: Vec<WidgetId> =
162 self.arena.subtree(node).filter_map(|n| self.arena.value(n).map(|e| e.id)).collect();
163 self.arena.remove_subtree(node);
164 for removed in removed_ids {
165 self.by_id.remove(&removed);
166 }
167 }
168
169 /// Whether `id` currently resolves to a live, non-null widget pointer.
170 pub fn is_registered(&self, id: WidgetId) -> bool {
171 self.get_ptr(id).is_some()
172 }
173
174 /// The live pointer for `id`, or `None` if unknown, link-only (null), or stale.
175 pub fn get_ptr(&self, id: WidgetId) -> Option<*mut (dyn WidgetHost + 'static)> {
176 let node = *self.by_id.get(&id)?;
177 live_ptr(self.arena.value(node)?)
178 }
179
180 /// `id`'s parent id, if any.
181 pub fn parent_id(&self, id: WidgetId) -> Option<WidgetId> {
182 let node = *self.by_id.get(&id)?;
183 let parent = self.arena.parent(node)?;
184 Some(self.arena.value(parent)?.id)
185 }
186
187 /// `id`'s parent pointer, if the parent is registered (non-null).
188 pub fn parent_ptr(&self, id: WidgetId) -> Option<*mut (dyn WidgetHost + 'static)> {
189 self.parent_id(id).and_then(|p| self.get_ptr(p))
190 }
191
192 /// `id`'s child ids in order (including link-only children not yet registered).
193 pub fn child_ids(&self, id: WidgetId) -> Vec<WidgetId> {
194 let Some(&node) = self.by_id.get(&id) else { return Vec::new() };
195 self.arena.children(node).iter().filter_map(|&c| self.arena.value(c).map(|e| e.id)).collect()
196 }
197
198 /// `id`'s child pointers in order, skipping any child that is link-only (null pointer) —
199 /// exactly matching the legacy `WidgetHost::children` `filter_map` over the registry.
200 pub fn children_ptrs(&self, id: WidgetId) -> Vec<*mut (dyn WidgetHost + 'static)> {
201 let Some(&node) = self.by_id.get(&id) else { return Vec::new() };
202 self.arena
203 .children(node)
204 .iter()
205 .filter_map(|&c| live_ptr(self.arena.value(c)?))
206 .collect()
207 }
208
209 /// Iterate every registered `(id, ptr)` with a non-null pointer, for the passes that sweep the
210 /// whole registry (`clear_dirty`, `rebuild_spatial_grid`, coverage tests).
211 pub fn iter_registered(&self) -> impl Iterator<Item = (WidgetId, *mut (dyn WidgetHost + 'static))> + '_ {
212 self.by_id.values().filter_map(move |&node| {
213 let entry = self.arena.value(node)?;
214 live_ptr(entry).map(|p| (entry.id, p))
215 })
216 }
217 }
218
219 #[cfg(test)]
220 mod tests {
221 use super::*;
222
223 // A minimal real `WidgetHost` so tests exercise genuine `*mut dyn WidgetHost` payloads. The boxes
224 // are kept alive in a local `Vec` for the duration of each test; we hand the tree raw
225 // pointers into them, mirroring how widgets (owned by the app) are referenced by the tree.
226 struct Marker {
227 base: crate::widget::Widget,
228 #[allow(dead_code)]
229 tag: u32,
230 }
231 impl WidgetHost for Marker {
232 crate::impl_widget_base!(Marker);
233 fn color(&self) -> [f32; 4] {
234 [0.0, 0.0, 0.0, 0.0]
235 }
236 }
237
238 /// Owns marker widgets and hands out stable raw pointers + ids for them.
239 struct Widgets {
240 boxes: Vec<Box<Marker>>,
241 }
242 impl Widgets {
243 fn new() -> Self {
244 Widgets { boxes: Vec::new() }
245 }
246 /// Create a widget, returning `(WidgetId, *mut dyn WidgetHost)`.
247 fn make(&mut self, tag: u32) -> (WidgetId, *mut (dyn WidgetHost + 'static)) {
248 let mut b = Box::new(Marker { base: crate::widget::Widget::new(), tag: tag });
249 let ptr: *mut (dyn WidgetHost + 'static) = &mut *b;
250 self.boxes.push(b);
251 (WidgetId(tag as usize), ptr)
252 }
253 }
254
255 #[test]
256 fn register_and_resolve() {
257 let mut w = Widgets::new();
258 let mut tree = WidgetTree::new();
259 let (id, ptr) = w.make(1);
260 assert_eq!(tree.get_ptr(id), None, "unknown id resolves to None");
261 tree.register(id, ptr);
262 assert_eq!(tree.get_ptr(id), Some(ptr));
263 assert!(tree.is_registered(id));
264 }
265
266 #[test]
267 fn register_overwrites_pointer() {
268 let mut w = Widgets::new();
269 let mut tree = WidgetTree::new();
270 let id = WidgetId(1);
271 let (_, p1) = w.make(1);
272 let (_, p2) = w.make(2);
273 tree.register(id, p1);
274 tree.register(id, p2); // same id, new pointer
275 assert_eq!(tree.get_ptr(id), Some(p2));
276 assert_eq!(tree.len(), 1, "overwrite must not create a second node");
277 }
278
279 #[test]
280 fn link_is_symmetric_and_deduped() {
281 let mut w = Widgets::new();
282 let mut tree = WidgetTree::new();
283 let (p, pp) = w.make(1);
284 let (c, cp) = w.make(2);
285 tree.register(p, pp);
286 tree.register(c, cp);
287
288 tree.link(p, c);
289 tree.link(p, c); // duplicate link is a no-op
290 assert_eq!(tree.parent_id(c), Some(p));
291 assert_eq!(tree.child_ids(p), vec![c]);
292 assert_eq!(tree.children_ptrs(p), vec![cp]);
293 }
294
295 #[test]
296 fn reparenting_removes_from_old_parent() {
297 let mut w = Widgets::new();
298 let mut tree = WidgetTree::new();
299 let (a, ap) = w.make(1);
300 let (b, bp) = w.make(2);
301 let (c, cp) = w.make(3);
302 tree.register(a, ap);
303 tree.register(b, bp);
304 tree.register(c, cp);
305
306 tree.link(a, c);
307 assert_eq!(tree.child_ids(a), vec![c]);
308 tree.link(b, c);
309 assert!(tree.child_ids(a).is_empty(), "old parent drops the child");
310 assert_eq!(tree.child_ids(b), vec![c]);
311 assert_eq!(tree.parent_id(c), Some(b));
312 }
313
314 #[test]
315 fn link_before_register_uses_null_placeholder() {
316 // Mirrors the legacy case where a `layout_tree` link precedes the `widget_registry` entry:
317 // the child appears in `child_ids` but is skipped by `children_ptrs` until registered.
318 let mut w = Widgets::new();
319 let mut tree = WidgetTree::new();
320 let (p, pp) = w.make(1);
321 tree.register(p, pp);
322 let child = WidgetId(2);
323
324 tree.link(p, child); // child not registered yet
325 assert_eq!(tree.child_ids(p), vec![child]);
326 assert!(tree.children_ptrs(p).is_empty(), "link-only child has no pointer yet");
327
328 let (_, cp) = w.make(2);
329 tree.register(child, cp);
330 assert_eq!(tree.children_ptrs(p), vec![cp], "now resolvable");
331 }
332
333 #[test]
334 fn set_parent_none_detaches_symmetrically() {
335 // The deliberate divergence from legacy: detaching clears BOTH ends, so the parent's
336 // children no longer list the child.
337 let mut w = Widgets::new();
338 let mut tree = WidgetTree::new();
339 let (p, pp) = w.make(1);
340 let (c, cp) = w.make(2);
341 tree.register(p, pp);
342 tree.register(c, cp);
343 tree.link(p, c);
344
345 tree.set_parent(c, None);
346 assert_eq!(tree.parent_id(c), None);
347 assert!(tree.child_ids(p).is_empty(), "symmetric detach clears parent's child list too");
348 assert!(tree.is_registered(c), "detach keeps the widget registered");
349 }
350
351 #[test]
352 fn clear_children_detaches_but_keeps_registration() {
353 let mut w = Widgets::new();
354 let mut tree = WidgetTree::new();
355 let (p, pp) = w.make(1);
356 let (c1, c1p) = w.make(2);
357 let (c2, c2p) = w.make(3);
358 tree.register(p, pp);
359 tree.register(c1, c1p);
360 tree.register(c2, c2p);
361 tree.link(p, c1);
362 tree.link(p, c2);
363
364 tree.clear_children(p);
365 assert!(tree.child_ids(p).is_empty());
366 assert_eq!(tree.parent_id(c1), None);
367 assert!(tree.is_registered(c1) && tree.is_registered(c2), "children stay registered");
368 }
369
370 #[test]
371 fn clear_all_empties_everything() {
372 let mut w = Widgets::new();
373 let mut tree = WidgetTree::new();
374 let (p, pp) = w.make(1);
375 let (c, cp) = w.make(2);
376 tree.register(p, pp);
377 tree.register(c, cp);
378 tree.link(p, c);
379
380 tree.clear_all();
381 assert!(tree.is_empty());
382 assert_eq!(tree.get_ptr(p), None);
383 assert_eq!(tree.parent_id(c), None);
384 }
385
386 #[test]
387 fn remove_makes_stale_ids_resolve_to_none() {
388 // The safety win over the legacy registry, which never removed entries (leaving dangling
389 // pointers): after removal, the id resolves to None instead of a freed pointer.
390 let mut w = Widgets::new();
391 let mut tree = WidgetTree::new();
392 let (p, pp) = w.make(1);
393 let (c, cp) = w.make(2);
394 tree.register(p, pp);
395 tree.register(c, cp);
396 tree.link(p, c);
397
398 tree.remove(p); // removes p and its subtree (c)
399 assert_eq!(tree.get_ptr(p), None);
400 assert_eq!(tree.get_ptr(c), None, "descendant removed too");
401 assert!(tree.is_empty());
402 }
403
404 #[test]
405 fn iter_registered_yields_only_non_null() {
406 let mut w = Widgets::new();
407 let mut tree = WidgetTree::new();
408 let (p, pp) = w.make(1);
409 tree.register(p, pp);
410 tree.link(p, WidgetId(99)); // link-only, null pointer
411
412 let seen: Vec<WidgetId> = tree.iter_registered().map(|(id, _)| id).collect();
413 assert_eq!(seen, vec![p], "link-only (null) node is not yielded");
414 }
415 }