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