ailloli_ui_runtime/layout/
layout_engine.rs

1//! Retained-tree layout engine and invalidation-aware traversal.
2
3use std::panic::{catch_unwind, AssertUnwindSafe};
4
5use ailloli_ui_core::geometry::Constraints;
6use ailloli_ui_core::ids::ElementId;
7use ailloli_ui_core::{Rect, Size};
8
9use crate::component::reactive::{
10    with_untracked_reads, ReactiveDependencyBatchResult, ReactiveDependencyUpdate,
11    ReactiveReadScope, ReactiveReadSet, ReactiveStage,
12};
13use crate::element::element_node::LayoutCacheKey;
14use crate::element::{ElementKind, ElementTree};
15use crate::layout::layout_attempt::{FinishedLayoutAttempt, LayoutAttemptEvent, StagedLayout};
16use crate::layout::{ChildLayout, LayoutChild, LayoutCtx, LayoutResult};
17
18/// Recursive retained-tree layout driver with per-element result caching.
19///
20/// The engine exclusively borrows an [`ElementTree`] for the traversal. Cache
21/// identity includes exact floating-point bit patterns for constraints, DPR,
22/// and virtual viewport, the layout pass authority, plus text, element,
23/// widget-dependency, and topology revisions. Consequently `0.0` and `-0.0`
24/// are distinct cache inputs and NaN payloads are compared by their bits.
25///
26/// # Examples
27///
28/// ```
29/// use ailloli_ui_runtime::element::ElementTree;
30/// use ailloli_ui_runtime::layout::LayoutEngine;
31///
32/// let mut tree = ElementTree::<()>::new();
33/// let engine = LayoutEngine::new(&mut tree);
34/// assert!(engine.tree.root().is_none());
35/// ```
36pub struct LayoutEngine<'t, A> {
37    /// Retained tree being read and updated by this layout traversal.
38    pub tree: &'t mut ElementTree<A>,
39}
40
41/// Provides the operations defined for `LayoutEngine<'t, A>`.
42impl<'t, A: 'static> LayoutEngine<'t, A> {
43    /// Creates an engine borrowing `tree` until the engine is dropped.
44    ///
45    /// This performs no layout and does not clear existing caches.
46    ///
47    /// # Examples
48    ///
49    /// ```
50    /// use ailloli_ui_runtime::element::ElementTree;
51    /// use ailloli_ui_runtime::layout::LayoutEngine;
52    ///
53    /// let mut tree = ElementTree::<()>::new();
54    /// let engine = LayoutEngine::new(&mut tree);
55    /// assert_eq!(engine.tree.children_of(ailloli_ui_core::ElementId(42)), &[]);
56    /// ```
57    pub fn new(tree: &'t mut ElementTree<A>) -> Self {
58        Self { tree }
59    }
60
61    /// Lays out one element and stores or reuses its cached [`LayoutResult`].
62    ///
63    /// A missing ID returns a zero result without recording a cache miss. A
64    /// clean element with an identical key returns its cloned cached result and
65    /// records a hit. Otherwise the engine records a miss and layout operation,
66    /// recursively delegates widgets and transparent components, then stores a
67    /// cloned result. Components overlay direct children at `(0, 0)` and use the
68    /// maximum child size constrained by the parent.
69    ///
70    /// The text revision is zero when `ctx.text_system` is `None`. Widget code
71    /// runs synchronously and may mutate external state or panic; a panic leaves
72    /// this method before the new cache entry is stored.
73    ///
74    /// # Examples
75    ///
76    /// ```
77    /// use ailloli_ui_core::{Constraints, ElementId, Scale, Size};
78    /// use ailloli_ui_runtime::element::ElementTree;
79    /// use ailloli_ui_runtime::layout::{LayoutCtx, LayoutEngine};
80    ///
81    /// let mut tree = ElementTree::<()>::new();
82    /// let mut engine = LayoutEngine::new(&mut tree);
83    /// let mut ctx = LayoutCtx::new(Scale::new(1.0));
84    /// let result = engine.layout_element(
85    ///     &mut ctx, ElementId(404), Constraints::tight(40.0, 20.0),
86    /// );
87    /// assert_eq!(result.size, Size::default());
88    /// ```
89    pub fn layout_element(
90        &mut self,
91        ctx: &mut LayoutCtx<'_>,
92        element_id: ElementId,
93        constraints: Constraints,
94    ) -> LayoutResult {
95        self.layout_element_with_publication(ctx, element_id, constraints)
96            .0
97    }
98
99    /// Lays out an outer runtime root and reports whether its overlay published.
100    ///
101    /// The boolean is `false` when a superseding reactive mutation rejects the
102    /// attempt. Runtime orchestration uses it to avoid invoking post-layout
103    /// hooks against the previous committed geometry. Nested calls participate
104    /// in their owner's attempt and therefore do not publish independently.
105    pub(crate) fn layout_element_with_publication(
106        &mut self,
107        ctx: &mut LayoutCtx<'_>,
108        element_id: ElementId,
109        constraints: Constraints,
110    ) -> (LayoutResult, bool) {
111        if ctx.has_layout_attempt() {
112            return (
113                self.layout_element_staged(ctx, element_id, constraints),
114                false,
115            );
116        }
117
118        let authoritative = ctx.layout_pass().is_committed();
119        ctx.begin_layout_attempt();
120        let result = catch_unwind(AssertUnwindSafe(|| {
121            self.layout_element_staged(ctx, element_id, constraints)
122        }));
123        match result {
124            Ok(result) => {
125                let attempt = ctx.take_layout_attempt();
126                let staged = attempt.finish(|branch| ctx.measure_branch_is_adopted(branch));
127                ctx.clear_measure_branch_adoptions();
128                let published = match staged {
129                    Ok(attempt) => self.commit_attempt(ctx, attempt, authoritative),
130                    Err(()) => {
131                        ctx.record_reactive_layout_abandon();
132                        self.tree.mark_layout_path_dirty(element_id);
133                        ctx.request_reactive_layout_retry(element_id);
134                        false
135                    }
136                };
137                (result, published)
138            }
139            Err(payload) => {
140                drop(ctx.take_layout_attempt());
141                ctx.clear_measure_branch_adoptions();
142                ctx.record_reactive_layout_abandon();
143                std::panic::resume_unwind(payload)
144            }
145        }
146    }
147
148    /// Computes one element against the active layout overlay.
149    fn layout_element_staged(
150        &mut self,
151        ctx: &mut LayoutCtx<'_>,
152        element_id: ElementId,
153        constraints: Constraints,
154    ) -> LayoutResult {
155        let text_metrics_revision = ctx
156            .text_system
157            .as_deref()
158            .map_or(0, ailloli_ui_text::TextSystem::metrics_revision);
159        let virtual_viewport = ctx.virtual_viewport().map(|viewport| {
160            [
161                viewport.rect.x.to_bits(),
162                viewport.rect.y.to_bits(),
163                viewport.rect.w.to_bits(),
164                viewport.rect.h.to_bits(),
165                viewport.overscan.to_bits(),
166            ]
167        });
168        let Some(element) = self.tree.get(element_id) else {
169            return LayoutResult::zero();
170        };
171        let mount_generation = element.mount_generation();
172        let layout_dependency_revision = with_untracked_reads(|| match &element.kind {
173            ElementKind::Widget(widget) => widget.layout_dependency_revision(),
174            ElementKind::Empty | ElementKind::Component(_) => 0,
175        });
176        let cache_key = LayoutCacheKey {
177            constraints: [
178                constraints.min_w.to_bits(),
179                constraints.max_w.to_bits(),
180                constraints.min_h.to_bits(),
181                constraints.max_h.to_bits(),
182            ],
183            scale: ctx.scale.dpr.to_bits(),
184            layout_pass: ctx.layout_pass(),
185            text_metrics_revision,
186            layout_revision: element.layout_revision,
187            layout_dependency_revision,
188            topology_revision: element.topology_revision,
189            virtual_viewport,
190        };
191
192        if let Some((layout, dependencies)) =
193            ctx.layout_attempt()
194                .cached(element_id, ctx.layout_pass(), mount_generation, cache_key)
195        {
196            return self.stage_cache_hit(
197                ctx,
198                element_id,
199                mount_generation,
200                layout,
201                cache_key,
202                dependencies,
203            );
204        }
205
206        let retained_cache = if ctx.layout_pass().is_measure() {
207            (
208                element.measurement_layout_cache_key,
209                element.measurement_layout.clone(),
210                element.measurement_reactive_dependencies.clone(),
211                true,
212            )
213        } else {
214            (
215                element.layout_cache_key,
216                element.layout.clone(),
217                element.layout_reactive_dependencies.clone(),
218                !element.dirty.layout,
219            )
220        };
221        if retained_cache.3 && retained_cache.0 == Some(cache_key) && retained_cache.2.is_current()
222        {
223            if let Some(layout) = retained_cache.1 {
224                return self.stage_cache_hit(
225                    ctx,
226                    element_id,
227                    mount_generation,
228                    layout,
229                    cache_key,
230                    retained_cache.2,
231                );
232            }
233        }
234
235        let observation = ReactiveReadScope::new();
236
237        let child_ids = self.tree.children_of(element_id).to_vec();
238        let mut children = child_ids
239            .into_iter()
240            .map(|id| LayoutChild { element_id: id })
241            .collect::<Vec<_>>();
242
243        let result = match self
244            .tree
245            .get(element_id)
246            .map(|e| e.kind.clone())
247            .unwrap_or(ElementKind::Empty)
248        {
249            ElementKind::Empty => LayoutResult::zero(),
250            ElementKind::Widget(widget) => widget.layout(self, ctx, &mut children, constraints),
251            ElementKind::Component(_) => {
252                // Component is transparent for layout (its built output lives in children).
253                // Layout all children with no additional positioning (offset = 0).
254                // Positioning, if needed, must be expressed via widgets in the retained tree.
255                if children.is_empty() {
256                    LayoutResult::zero()
257                } else {
258                    let mut max = Size::default();
259                    let mut child_layouts = Vec::with_capacity(children.len());
260                    for mut child in children {
261                        let child_result = child.layout(self, ctx, constraints);
262                        max.w = max.w.max(child_result.size.w);
263                        max.h = max.h.max(child_result.size.h);
264                        child_layouts.push(ChildLayout {
265                            offset: ailloli_ui_core::Offset::default(),
266                            size: child_result.size,
267                            paint_bounds: Rect::new(
268                                0.0,
269                                0.0,
270                                child_result.size.w,
271                                child_result.size.h,
272                            ),
273                            visual_bounds: child_result.visual_bounds,
274                        });
275                    }
276                    let size = constraints.constrain(max);
277                    LayoutResult {
278                        size,
279                        children: child_layouts,
280                        paint_bounds: Rect::new(0.0, 0.0, size.w, size.h),
281                        visual_bounds: Rect::new(0.0, 0.0, size.w, size.h),
282                        overlay_hit_bounds: Vec::new(),
283                        clip: None,
284                        is_window_root_clip: false,
285                        artifact: None,
286                    }
287                }
288            }
289        };
290        let dependencies = observation.finish();
291        let measure_branch = ctx
292            .layout_pass()
293            .is_measure()
294            .then(|| ctx.current_measure_branch())
295            .flatten();
296        let attempt = ctx.layout_attempt_mut();
297        attempt.record(LayoutAttemptEvent::CacheMiss(element_id));
298        attempt.record(LayoutAttemptEvent::Layout(element_id));
299        attempt.stage(StagedLayout {
300            element_id,
301            mount_generation,
302            result: result.clone(),
303            cache_key,
304            dependencies,
305            measure_branch,
306            callback_executed: true,
307        });
308        result
309    }
310
311    /// Restores cached dependencies into the element scope and stages the hit.
312    fn stage_cache_hit(
313        &mut self,
314        ctx: &mut LayoutCtx<'_>,
315        element_id: ElementId,
316        mount_generation: crate::component::reactive::MountGeneration,
317        layout: LayoutResult,
318        cache_key: LayoutCacheKey,
319        cached_dependencies: ReactiveReadSet,
320    ) -> LayoutResult {
321        let observation = ReactiveReadScope::new();
322        cached_dependencies.adopt_into_current();
323        let dependencies = observation.finish();
324        let measure_branch = cache_key
325            .layout_pass
326            .is_measure()
327            .then(|| ctx.current_measure_branch())
328            .flatten();
329        let attempt = ctx.layout_attempt_mut();
330        attempt.record(LayoutAttemptEvent::CacheHit(element_id));
331        attempt.stage(StagedLayout {
332            element_id,
333            mount_generation,
334            result: layout.clone(),
335            cache_key,
336            dependencies,
337            measure_branch,
338            callback_executed: false,
339        });
340        layout
341    }
342
343    /// Applies a validated overlay as one non-callback runtime-owned batch.
344    fn commit_attempt(
345        &mut self,
346        ctx: &mut LayoutCtx<'_>,
347        mut attempt: FinishedLayoutAttempt,
348        authoritative: bool,
349    ) -> bool {
350        let attempt_token = attempt.token;
351        attempt.collect_stale_elements(|element_id, mount_generation| {
352            self.tree
353                .get(element_id)
354                .is_some_and(|element| element.mount_generation() == mount_generation)
355        });
356        if !attempt.stale_elements_mut().is_empty() {
357            self.reject_stale_attempt(ctx, attempt.stale_elements_mut());
358            return false;
359        }
360        if authoritative {
361            attempt.rebuild_dependency_updates(|element_id, mount_generation, mut dependencies| {
362                self.tree.get(element_id).map(|element| {
363                    dependencies.merge(&element.layout_commit_reactive_dependencies);
364                    ReactiveDependencyUpdate::new(
365                        element_id,
366                        mount_generation,
367                        ReactiveStage::Layout,
368                        dependencies,
369                    )
370                })
371            });
372            if matches!(
373                ctx.publish_reactive_layout(attempt.dependency_updates()),
374                ReactiveDependencyBatchResult::Stale
375            ) {
376                attempt.collect_update_elements_as_stale();
377                self.reject_stale_attempt(ctx, attempt.stale_elements_mut());
378                return false;
379            }
380        }
381
382        for event in attempt.drain_events() {
383            match event {
384                LayoutAttemptEvent::CacheHit(id) => self.tree.record_layout_cache_hit(id),
385                LayoutAttemptEvent::CacheMiss(id) => self.tree.record_layout_cache_miss(id),
386                LayoutAttemptEvent::Layout(id) => self.tree.record_layout(id),
387            }
388        }
389        for entry in attempt.drain_entries() {
390            #[cfg(feature = "devtools")]
391            if entry.cache_key.layout_pass.is_committed() {
392                let constraints = Constraints {
393                    min_w: f32::from_bits(entry.cache_key.constraints[0]),
394                    max_w: f32::from_bits(entry.cache_key.constraints[1]),
395                    min_h: f32::from_bits(entry.cache_key.constraints[2]),
396                    max_h: f32::from_bits(entry.cache_key.constraints[3]),
397                };
398                let debug =
399                    ctx.record_debug_layout(entry.element_id, constraints, entry.result.size);
400                self.tree.set_layout_debug(entry.element_id, debug);
401            }
402            self.tree.set_layout_with_cache_key(
403                entry.element_id,
404                entry.result,
405                entry.cache_key,
406                entry.dependencies,
407                attempt_token,
408                entry.callback_executed,
409            );
410        }
411        true
412    }
413
414    /// Abandons one generation-stale overlay and schedules exact retries.
415    fn reject_stale_attempt(&mut self, ctx: &LayoutCtx<'_>, element_ids: &mut Vec<ElementId>) {
416        element_ids.sort_by_key(|element_id| element_id.0);
417        element_ids.dedup();
418        ctx.record_reactive_layout_abandon();
419        self.tree
420            .mark_layout_paths_dirty(element_ids.iter().copied());
421        for element_id in element_ids.iter().copied() {
422            ctx.request_reactive_layout_retry(element_id);
423        }
424    }
425}
426
427#[cfg(test)]
428mod tests {
429    use std::cell::Cell;
430    use std::rc::Rc;
431
432    use ailloli_ui_core::{Constraints, Rect, Scale, Size};
433
434    use super::LayoutEngine;
435    use crate::app::RuntimeHandle;
436    use crate::component::Widget;
437    use crate::element::{ElementKind, ElementTree};
438    use crate::layout::{LayoutChild, LayoutCtx, LayoutResult};
439    use crate::scene::PaintCtx;
440
441    /// Fixed leaf whose callback count proves whether an attempted cache write ran.
442    struct ResizableLeaf {
443        extent: Rc<Cell<f32>>,
444        layouts: Rc<Cell<u32>>,
445    }
446
447    impl Widget<()> for ResizableLeaf {
448        fn debug_name(&self) -> &'static str {
449            "ResizableLeaf"
450        }
451
452        fn layout(
453            &self,
454            _engine: &mut LayoutEngine<'_, ()>,
455            _ctx: &mut LayoutCtx<'_>,
456            _children: &mut [LayoutChild],
457            _constraints: Constraints,
458        ) -> LayoutResult {
459            self.layouts.set(self.layouts.get() + 1);
460            let size = Size::new(self.extent.get(), self.extent.get());
461            LayoutResult {
462                size,
463                children: Vec::new(),
464                paint_bounds: Rect::new(0.0, 0.0, size.w, size.h),
465                visual_bounds: Rect::new(0.0, 0.0, size.w, size.h),
466                overlay_hit_bounds: Vec::new(),
467                clip: None,
468                is_window_root_clip: false,
469                artifact: None,
470            }
471        }
472
473        fn paint(&self, _ctx: &mut PaintCtx<'_>, _bounds: Rect, _layout: &LayoutResult) {}
474    }
475
476    #[test]
477    fn stale_batch_rejection_preserves_previous_geometry_and_cache() {
478        let extent = Rc::new(Cell::new(10.0));
479        let layouts = Rc::new(Cell::new(0));
480        let mut tree = ElementTree::new();
481        let root = tree.create_element(
482            ElementKind::Widget(Rc::new(ResizableLeaf {
483                extent: extent.clone(),
484                layouts: layouts.clone(),
485            })),
486            None,
487            None,
488        );
489
490        let mut first_ctx = LayoutCtx::new(Scale::new(1.0));
491        let (_, first_published) = LayoutEngine::new(&mut tree).layout_element_with_publication(
492            &mut first_ctx,
493            root,
494            Constraints::loose(100.0, 100.0),
495        );
496        assert!(first_published);
497        let first = tree.get(root).unwrap();
498        let old_layout = first.layout.clone();
499        let old_cache_key = first.layout_cache_key;
500        let old_attempt = first.committed_layout_attempt;
501        let staged_generation = first.mount_generation();
502
503        extent.set(20.0);
504        tree.mark_layout_path_dirty(root);
505
506        let runtime = RuntimeHandle::<()>::new();
507        runtime.register_element_mount(root, staged_generation.next());
508        let publisher = runtime.clone();
509        let retried = Rc::new(Cell::new(false));
510        let retry = retried.clone();
511        let abandoned = Rc::new(Cell::new(0_u32));
512        let abandon = abandoned.clone();
513        let mut stale_ctx = LayoutCtx::new(Scale::new(1.0));
514        stale_ctx.set_reactive_layout_callbacks(
515            Rc::new(move |updates| publisher.replace_reactive_dependencies_batch(updates)),
516            Rc::new(move |element_id| {
517                assert_eq!(element_id, root);
518                retry.set(true);
519            }),
520        );
521        stale_ctx.set_reactive_layout_abandon_callback(Rc::new(move || {
522            abandon.set(abandon.get() + 1);
523        }));
524
525        let (attempted, published) = LayoutEngine::new(&mut tree).layout_element_with_publication(
526            &mut stale_ctx,
527            root,
528            Constraints::loose(100.0, 100.0),
529        );
530
531        assert_eq!(attempted.size.w, 20.0);
532        assert!(!published);
533        assert_eq!(layouts.get(), 2);
534        assert!(retried.get());
535        assert_eq!(abandoned.get(), 1);
536        let retained = tree.get(root).unwrap();
537        assert!(retained
538            .layout
539            .as_ref()
540            .zip(old_layout.as_ref())
541            .is_some_and(|(retained, old)| retained.geometry_eq(old)));
542        assert!(retained.layout.as_ref().unwrap().artifact.is_none());
543        assert_eq!(retained.layout_cache_key, old_cache_key);
544        assert_eq!(retained.committed_layout_attempt, old_attempt);
545        assert!(retained.dirty.layout);
546    }
547}
ailloli_ui_runtime/layout/layout_engine.rs

ailloli_ui_runtime/layout/
layout_engine.rs
