kui_core/tree.rs
1//! [`Tree`]: the per-frame flat tree the core builds, lays out and emits.
2//!
3//! The tree is a set of parallel `Vec`s, one entry per node, rebuilt from
4//! scratch every frame with their capacities retained. Nodes are stored in
5//! DFS preorder (a parent always precedes its children, and preorder is
6//! paint order) and linked through `parent`, `first_child` and
7//! `next_sibling` indices. Layout writes `size` and `pos` into it; emission
8//! reads them. [`OriginId`] says which frontend (the host app, an
9//! extension, the core's own surfaces) opened each node.
10//!
11//! An app never touches this type: it builds through [`Ui`](crate::ui::Ui)
12//! and reads back through `Core`. It is public for a custom runner or a
13//! test that drives [`layout::compute`](crate::layout::compute) directly.
14
15use crate::geom::{Size, Vec2};
16use crate::key::Key;
17use crate::spec::NodeSpec;
18
19pub const NIL: u32 = u32::MAX;
20
21/// Which frontend produced a node: 0 is the host app, extensions get 1+.
22#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
23pub struct OriginId(pub u16);
24
25impl OriginId {
26 pub const HOST: OriginId = OriginId(0);
27 /// The core's own devtools panel: a node opened
28 /// under it is the panel's, and an event that carries it is acted on
29 /// inside `handle_input` and never handed out. Reserved at the top of
30 /// the range so no extension list ever reaches it.
31 pub const DEVTOOLS: OriginId = OriginId(u16::MAX);
32 /// The core's own context menu and the menu bar it draws: the same
33 /// isolation the
34 /// devtools have — a node opened under one of these is the surface's,
35 /// its events are taken back inside `handle_input` and never handed
36 /// out, and no key list has to remember which nodes those were.
37 pub const MENU: OriginId = OriginId(u16::MAX - 1);
38 pub const MENU_BAR: OriginId = OriginId(u16::MAX - 2);
39
40 /// Whether nodes of this origin are one of the core's own surfaces.
41 pub fn is_core_surface(self) -> bool {
42 matches!(self, Self::DEVTOOLS | Self::MENU | Self::MENU_BAR)
43 }
44}
45
46/// Index into the frame's text list (owned by `TextSystem`).
47#[derive(Clone, Copy, Debug, PartialEq, Eq)]
48pub struct TextId(pub u32);
49
50#[derive(Clone, Copy, Debug, PartialEq)]
51pub enum NodeContent {
52 Container,
53 Text(TextId),
54 /// Editable text; retained state lives in the core's `EditStore`.
55 Edit(Key),
56 /// A host-registered image (see `Resources`), drawn from the atlas or
57 /// from a texture of its own as the entry's backing says, met by its
58 /// box as `opts` say.
59 Image(crate::resources::ImageId, crate::resources::ImageOpts),
60 /// A stroke through a run of points: one segment quad per straight
61 /// piece (see `crate::line`). The node is a float sized to the
62 /// stroke's bounding box, so it takes no room, and its `bg` is the
63 /// stroke colour. In its parent's box space it paints in the parent's
64 /// layer at its place in the tree ([`NodeContent::drawn_in_parent`]).
65 Line(crate::line::LineId),
66 /// A cell grid (see `crate::cells`): a terminal's screen as one node.
67 Cells(crate::cells::CellsId),
68 /// A box a registered WGSL function paints (see `crate::fragment`).
69 /// The handle and the sixteen parameters live in the frame's
70 /// `FragmentList`; the node carries only where.
71 Fragment(crate::fragment::FragmentDrawId),
72 /// A filled polygon: a float sized to its own
73 /// bounding box like a line, painted by the stock polygon fragment
74 /// whose draw sits in the frame's `FragmentList` like any fragment's,
75 /// its `bg` the fill. No hit region, no access row.
76 Polygon(crate::fragment::FragmentDrawId),
77 /// A filled and/or stroked outline of any shape (see `crate::path`):
78 /// a float sized to its own bounding box like a line, its ops in the
79 /// frame's `PathStore`, drawn as glyph-mask quads from the atlas. Its
80 /// `bg` is the fill, its border width and colour the stroke.
81 Path(crate::path::PathId),
82}
83
84impl NodeContent {
85 /// Whether this is a shape the core floats for its own reasons — a
86 /// `line`, `polygon` or `path`, a float only so it takes no room in a
87 /// row or column (ADR 0010 decision 5). Such a node is its parent's
88 /// content as a child is: the parent's clip holds it (F78), and it
89 /// paints in the parent's layer at its place in the tree rather than
90 /// opening a layer of its own (F123) — a glyph drawn into a title bar
91 /// is not over a toast that opened before the bar did.
92 pub fn drawn_in_parent(self) -> bool {
93 matches!(self, Self::Line(_) | Self::Polygon(_) | Self::Path(_))
94 }
95}
96
97impl Tree {
98 /// Whether node `i` opens a float layer of its own (ADR 0023): a float
99 /// a view declared, or a stroke anchored to the viewport. A `line`,
100 /// `polygon` or `path` in its parent's box space does not — the core
101 /// made its float so it takes no room, and it paints where a child
102 /// would ([`NodeContent::drawn_in_parent`]). Reads the float's
103 /// anchor through [`FloatConfig::clipped_by_parent`], which the core
104 /// sets for every such shape, so the one rule serves the clip and the
105 /// layer.
106 ///
107 /// [`FloatConfig::clipped_by_parent`]: crate::spec::FloatConfig::clipped_by_parent
108 pub fn opens_layer(&self, i: usize) -> bool {
109 self.specs[i]
110 .layout
111 .float
112 .is_some_and(|f| !(f.clipped_by_parent() && self.content[i].drawn_in_parent()))
113 }
114
115 /// Whether node `i` is drawn in its parent's layer, as a child is,
116 /// although it floats: [`Tree::opens_layer`]'s complement for a node
117 /// that declares `float` at all.
118 pub fn floats_in_parent(&self, i: usize) -> bool {
119 self.specs[i].layout.float.is_some() && !self.opens_layer(i)
120 }
121
122 /// One past the last node of `i`'s subtree. Preorder storage makes a
123 /// subtree a contiguous index range ending at the next node that is a
124 /// sibling of `i` or of one of its ancestors.
125 pub fn subtree_end(&self, i: usize) -> usize {
126 let mut n = i as u32;
127 loop {
128 if self.next_sibling[n as usize] != NIL {
129 return self.next_sibling[n as usize] as usize;
130 }
131 n = self.parent[n as usize];
132 if n == NIL {
133 return self.len();
134 }
135 }
136 }
137}
138
139/// One frame's nodes as parallel arrays in preorder; see the
140/// [module docs](self).
141#[derive(Default)]
142pub struct Tree {
143 pub keys: Vec<Key>,
144 pub origins: Vec<OriginId>,
145 pub specs: Vec<NodeSpec>,
146 pub content: Vec<NodeContent>,
147
148 pub parent: Vec<u32>,
149 pub first_child: Vec<u32>,
150 pub last_child: Vec<u32>,
151 pub next_sibling: Vec<u32>,
152
153 // Filled by the layout pass.
154 pub size: Vec<Size>,
155 pub pos: Vec<Vec2>,
156 /// Max scroll offset per axis (zero for non-scroll nodes).
157 pub scroll_max: Vec<Vec2>,
158 /// Which wrap line of its parent a node sits on, from the main-axis
159 /// pass. Zero everywhere but under a wrapping container, and the
160 /// in-flow children of one line are always a contiguous sibling run,
161 /// so a line is a range rather than a list.
162 pub line: Vec<u32>,
163 /// Each node's first baseline below its top, logical px, where text
164 /// measured one (`NaN` elsewhere). Filled by the fit-height pass, and
165 /// only on a frame with a baseline row (`any_baseline`); empty
166 /// otherwise.
167 pub baseline: Vec<f32>,
168
169 // Set by `push`, cleared by `clear`: what this frame declared at all,
170 // so a pass whose work exists for one feature can skip it wholesale
171 // when no node asked for that feature. A float check in a layout pass
172 // is a scattered read through the spec of every child of every node;
173 // behind a flag that is false on nearly every frame it is one
174 // predicted branch.
175 /// Whether any node declares `float`.
176 pub any_float: bool,
177 /// Whether any node declares a size expression as a clamp (a
178 /// negative `max_w`, a `Min::calc`): layout resolves
179 /// them only then.
180 pub any_calc_bound: bool,
181 /// Whether any float is anchored to a node by key
182 /// (`FloatAnchor::Node`): the sixth layout pass runs only then.
183 pub any_node_float: bool,
184 /// Whether any node declares `wrap_children`.
185 pub any_wrap: bool,
186 /// Whether any node lines its children up by their baselines
187 /// (`cross_align: Baseline`): the layout measures baselines only then.
188 pub any_baseline: bool,
189 /// Whether any node is a table (`LayoutSpec::table`): the column
190 /// alignment in the layout passes runs only on a frame that has one.
191 pub any_table: bool,
192 /// Whether any node declares a `gradient`: emission looks for one
193 /// only on a frame that has one.
194 pub any_gradient: bool,
195 /// Whether any node declares a `backdrop_blur` (backlog F129):
196 /// emission looks for one only on a frame that has one.
197 pub any_backdrop_blur: bool,
198 /// Whether any node turns or scales (ADR 0043): the per-node clip
199 /// space is tracked only on a frame that has one.
200 pub any_transform: bool,
201 /// Whether any node's keyframe stops name a position (backlog F132):
202 /// the pass that moves them runs only on a frame that has one.
203 pub any_offset_stop: bool,
204 /// Whether any node is text (a `Text` or `Edit` content).
205 pub any_text: bool,
206 /// Whether any node is a `role="line"` row — what a pointer payload
207 /// inside a key sink is resolved against, so a frame
208 /// without a custom editor never walks a sink's subtree for one.
209 pub any_line: bool,
210
211 /// Scratch for the layout pass's freeze loop (`distribute_run`): one
212 /// byte per in-flow child of the run being resolved, in child order.
213 /// Sized per run and never cleared, so the allocation is made once
214 /// and reused by every run of every frame.
215 pub grow_scratch: Vec<u8>,
216 /// Scratch for the shrink CSS's way (`layout::shrink_as_css`): one
217 /// entry per child of the run giving, made once and reused
218 /// by every overflowing run of every frame, as `grow_scratch` is.
219 pub(crate) shrink_scratch: Vec<crate::layout::Give>,
220 /// Whether any node clips (`clip`, or an overflow that scrolls).
221 pub any_clip: bool,
222 /// Whether any node clips *and* has a radius, so the clip its
223 /// descendants inherit is rounded. Separate from `any_clip`: the
224 /// per-corner bookkeeping is skipped for the ordinary square clip.
225 pub any_rounded_clip: bool,
226 /// Whether any node fades (`opacity` below one).
227 pub any_opacity: bool,
228 /// Whether any node declares `modal`.
229 pub any_modal: bool,
230 /// Whether any node declares `focus_region`.
231 pub any_region: bool,
232 /// Whether any node eases its position (`slide`, or an `enter` with
233 /// an offset) under a transition.
234 pub any_slide: bool,
235 /// Whether any node declares `over_siblings`, so the in-flow walk keeps no
236 /// deferred subtrees on a frame that raises nothing.
237 pub any_over_siblings: bool,
238 /// Whether any node declares `on_layout`, so the rect report can skip
239 /// the walk.
240 pub any_layout: bool,
241 /// Whether any node declares `on_context_menu`, so a hit region's
242 /// walk for the menu it inherits is skipped wholesale on
243 /// a frame that offers none.
244 pub any_context_menu: bool,
245 /// Some node declared `on_scroll`; emission reads the row per node
246 /// only then.
247 pub any_scroll_handler: bool,
248 /// Some node declared `on_drop`: a hit region's walk for
249 /// the zone it inherits is skipped wholesale on a frame with none.
250 pub any_drop: bool,
251 /// Whether any node declares a workable `exit` (one under a
252 /// transition). Gates the tree swap and the key diff.
253 pub any_exit: bool,
254 /// Whether any node asked for the next frame (`animate`): one node
255 /// asking is the whole window asking.
256 pub any_animate: bool,
257 /// The data index of every node opened with one (`open_indexed`), by
258 /// node. A side list rather than a column, because it is a virtual
259 /// list's rows and nothing else: a frame that builds none is one empty
260 /// `Vec`.
261 ///
262 /// What it is for: a selection endpoint in a row that is *not built*
263 /// can still be ordered against the rows that are, because a row's
264 /// index says where it sits in the data even when nothing on screen
265 /// says where it sits in the frame.
266 pub indexed: Vec<(u32, u64)>,
267 /// How many indexed rows a node's virtual list has, built or not
268 /// (`rowCount`), by node. A side list for the reason `indexed` is one.
269 /// What it is for: Select All inside a `selectable` virtual list is
270 /// the *data*, rows `0..count`, not the rows the frame happened to
271 /// build — and the count is the one thing about the data the core
272 /// cannot see.
273 pub row_counts: Vec<(u32, u64)>,
274 /// The node range every slot fill opened, by the slot's key: `(slot,
275 /// first, end)` over node indices, innermost fill first (a fill
276 /// records itself after the fills inside it). A side list for the
277 /// reason `indexed` is one — a frame with no extension is one empty
278 /// `Vec` — and what stamps `UiEvent::slot`, so a host that fills many
279 /// slots from one extension can route an event by the slot it came
280 /// from without stamping every payload.
281 pub fills: Vec<(Key, u32, u32)>,
282 /// Whether any node declares `selectable`. False on every
283 /// frame of an app that never asks for one, which is what keeps the
284 /// scope walk and the off-screen places of tier 2 off those frames
285 /// entirely.
286 pub any_selectable: bool,
287 /// The box a `FloatConfig::viewport()` float of the host's resolves
288 /// against, in window coordinates: the whole window, or what the
289 /// devtools' dock leaves of it. A zero rect means
290 /// the window. The devtools' own nodes always use the window.
291 pub host_area: crate::geom::Rect,
292}
293
294impl Tree {
295 pub fn new() -> Self {
296 Self::default()
297 }
298
299 pub fn len(&self) -> usize {
300 self.keys.len()
301 }
302
303 pub fn is_empty(&self) -> bool {
304 self.keys.is_empty()
305 }
306
307 /// The index of the node `key` names in this frame, if it is here. A
308 /// linear scan: the one place to swap it for a map if a profile asks.
309 #[inline]
310 pub fn index_of(&self, key: Key) -> Option<usize> {
311 self.keys.iter().position(|k| *k == key)
312 }
313
314 /// The parent an ancestor walk that means "where is this shown"
315 /// takes: the node's parent, except for a float anchored to a node by
316 /// key, whose walk continues from the anchor (`FloatAnchor::Node`).
317 /// `NIL` past the root, and for an anchor the frame does not have.
318 #[inline]
319 pub fn region_parent(&self, i: usize) -> u32 {
320 if self.any_node_float
321 && let Some(crate::spec::FloatConfig {
322 anchor: crate::spec::FloatAnchor::Node(key),
323 ..
324 }) = self.specs[i].layout.float
325 {
326 return self.index_of(key).map_or(NIL, |a| a as u32);
327 }
328 self.parent[i]
329 }
330
331 /// Clears contents but keeps allocations for the next frame.
332 pub fn clear(&mut self) {
333 self.keys.clear();
334 self.origins.clear();
335 self.specs.clear();
336 self.content.clear();
337 self.parent.clear();
338 self.first_child.clear();
339 self.last_child.clear();
340 self.next_sibling.clear();
341 self.size.clear();
342 self.pos.clear();
343 self.scroll_max.clear();
344 self.line.clear();
345 self.baseline.clear();
346 self.any_float = false;
347 self.any_calc_bound = false;
348 self.any_baseline = false;
349 self.any_node_float = false;
350 self.any_wrap = false;
351 self.any_table = false;
352 self.any_gradient = false;
353 self.any_backdrop_blur = false;
354 self.any_transform = false;
355 self.any_offset_stop = false;
356 self.any_text = false;
357 self.any_line = false;
358 self.any_selectable = false;
359 self.any_clip = false;
360 self.any_rounded_clip = false;
361 self.any_opacity = false;
362 self.any_modal = false;
363 self.any_region = false;
364 self.any_slide = false;
365 self.any_over_siblings = false;
366 self.any_layout = false;
367 self.any_context_menu = false;
368 self.any_scroll_handler = false;
369 self.any_drop = false;
370 self.any_exit = false;
371 self.any_animate = false;
372 self.indexed.clear();
373 self.row_counts.clear();
374 self.fills.clear();
375 }
376
377 /// The innermost slot fill node `i` was opened inside, if any.
378 pub fn slot_of(&self, i: usize) -> Option<Key> {
379 let i = i as u32;
380 self.fills
381 .iter()
382 .find(|(_, first, end)| (*first..*end).contains(&i))
383 .map(|(slot, _, _)| *slot)
384 }
385
386 /// Notes what a spec asks of the frame, so a pass whose work exists
387 /// for one feature can skip it when no node declared that feature.
388 /// Called by `push` for every node, and by the root paths that
389 /// replace a spec in place — the one door, so a leaf cannot forget a
390 /// flag a box would have set (an `image` once set two of these and
391 /// painted opaque when it was the frame's only fade).
392 ///
393 /// Each boxed group is tested once, not once per flag it can set: a
394 /// node declaring no events and no animation is done after two null
395 /// checks (C15).
396 #[inline]
397 pub fn note(&mut self, spec: &NodeSpec, content: &NodeContent) {
398 if let Some(f) = spec.layout.float {
399 self.any_float = true;
400 self.any_node_float |= matches!(f.anchor, crate::spec::FloatAnchor::Node(_));
401 }
402 self.any_wrap |= spec.layout.wrap;
403 let l = &spec.layout;
404 self.any_calc_bound |= l.max_w < 0.0
405 || l.max_h < 0.0
406 || l.min_w.as_calc().is_some()
407 || l.min_h.as_calc().is_some();
408 self.any_table |= spec.layout.is_table();
409 self.any_gradient |= spec.interact().gradient.is_some();
410 self.any_baseline |= spec.layout.cross_align == crate::spec::Align::Baseline;
411 self.any_text |= matches!(
412 content,
413 NodeContent::Text(_) | NodeContent::Edit(_) | NodeContent::Cells(_)
414 );
415 // Through the box rather than through `interact()`: a node that
416 // declares no interaction group is answered by one null check
417 // instead of a read through the empty static (C15).
418 if let Some(i) = spec.interact.as_deref() {
419 self.any_selectable |= i.selectable;
420 self.any_region |= i.focus_region;
421 self.any_backdrop_blur |= i.backdrop_blur > 0.0;
422 self.any_transform |= i.transform.as_deref().is_some_and(|t| t.active());
423 }
424 if let Some(a) = spec.access.as_deref() {
425 self.any_line |= a.role == Some(crate::access::Role::Line);
426 }
427 if spec.layout.clips() {
428 self.any_clip = true;
429 self.any_rounded_clip |= spec.style.radius != crate::display::SQUARE;
430 }
431 self.any_opacity |= spec.style.opacity < 1.0;
432 self.any_animate |= spec.animate;
433 self.any_over_siblings |= spec.over_siblings;
434 if let Some(events) = spec.events.as_deref() {
435 self.any_modal |= events.modal.is_some();
436 self.any_layout |= events.on_layout.is_some();
437 self.any_context_menu |= events.on_context_menu.is_some();
438 self.any_scroll_handler |= events.on_scroll.is_some();
439 self.any_drop |= events.on_drop.is_some();
440 }
441 if spec.transition.is_some() {
442 match spec.anim.as_deref() {
443 Some(anim) => {
444 self.any_slide |= spec.slide || anim.enter.is_some_and(|e| e.offsets());
445 self.any_offset_stop |=
446 !anim.keyframes.is_empty() && anim.keyframes.iter().any(|k| k.offsets());
447 self.any_exit |= anim.exit.is_some();
448 }
449 None => self.any_slide |= spec.slide,
450 }
451 }
452 }
453
454 #[inline]
455 pub fn push(
456 &mut self,
457 parent: u32,
458 key: Key,
459 origin: OriginId,
460 spec: NodeSpec,
461 content: NodeContent,
462 ) -> u32 {
463 let idx = self.keys.len() as u32;
464 // Read before the move, while the spec is in cache anyway.
465 self.note(&spec, &content);
466 self.keys.push(key);
467 self.origins.push(origin);
468 self.specs.push(spec);
469 self.content.push(content);
470 self.parent.push(parent);
471 self.first_child.push(NIL);
472 self.last_child.push(NIL);
473 self.next_sibling.push(NIL);
474 self.size.push(Size::ZERO);
475 self.pos.push(Vec2::ZERO);
476 self.scroll_max.push(Vec2::ZERO);
477 self.line.push(0);
478
479 if parent != NIL {
480 let p = parent as usize;
481 if self.first_child[p] == NIL {
482 self.first_child[p] = idx;
483 } else {
484 let last = self.last_child[p] as usize;
485 self.next_sibling[last] = idx;
486 }
487 self.last_child[p] = idx;
488 }
489 idx
490 }
491
492 pub fn children(&self, i: u32) -> ChildIter<'_> {
493 ChildIter {
494 tree: self,
495 next: self.first_child[i as usize],
496 }
497 }
498}
499
500pub struct ChildIter<'a> {
501 tree: &'a Tree,
502 next: u32,
503}
504
505impl Iterator for ChildIter<'_> {
506 type Item = u32;
507
508 fn next(&mut self) -> Option<u32> {
509 if self.next == NIL {
510 return None;
511 }
512 let cur = self.next;
513 self.next = self.tree.next_sibling[cur as usize];
514 Some(cur)
515 }
516}
517
518#[cfg(test)]
519mod tests {
520 use super::*;
521
522 #[test]
523 fn sibling_links() {
524 let mut t = Tree::new();
525 let root = t.push(
526 NIL,
527 Key::ROOT,
528 OriginId::HOST,
529 NodeSpec::default(),
530 NodeContent::Container,
531 );
532 let a = t.push(
533 root,
534 Key::ROOT.index(0),
535 OriginId::HOST,
536 NodeSpec::default(),
537 NodeContent::Container,
538 );
539 let a1 = t.push(
540 a,
541 Key::ROOT.index(0).index(0),
542 OriginId::HOST,
543 NodeSpec::default(),
544 NodeContent::Container,
545 );
546 let b = t.push(
547 root,
548 Key::ROOT.index(1),
549 OriginId::HOST,
550 NodeSpec::default(),
551 NodeContent::Container,
552 );
553
554 assert_eq!(t.children(root).collect::<Vec<_>>(), vec![a, b]);
555 assert_eq!(t.children(a).collect::<Vec<_>>(), vec![a1]);
556 assert_eq!(t.children(b).collect::<Vec<_>>(), Vec::<u32>::new());
557 // Preorder invariant: parents precede children.
558 assert!(root < a && a < a1 && a1 < b);
559 }
560}