Fix caching of `display:none` nodes (backport of #454) (#456)
1//! The layout algorithms themselves
2
3pub(crate) mod common;
4pub(crate) mod flexbox;
5pub(crate) mod leaf;
6
7#[cfg(feature = "grid")]
8pub(crate) mod grid;
9
10use crate::data::CACHE_SIZE;
11use crate::error::TaffyError;
12use crate::geometry::{Point, Size};
13use crate::layout::{Cache, Layout, RunMode, SizeAndBaselines, SizingMode};
14use crate::node::{Node, Taffy};
15use crate::style::{AvailableSpace, Display};
16use crate::sys::round;
17use crate::tree::LayoutTree;
18
19use self::flexbox::FlexboxAlgorithm;
20#[cfg(feature = "grid")]
21use self::grid::CssGridAlgorithm;
22use self::leaf::LeafAlgorithm;
23
24#[cfg(any(feature = "debug", feature = "profile"))]
25use crate::debug::NODE_LOGGER;
26
27/// Updates the stored layout of the provided `node` and its children
28pub fn compute_layout(taffy: &mut Taffy, root: Node, available_space: Size<AvailableSpace>) -> Result<(), TaffyError> {
29 // Recursively compute node layout
30 let size_and_baselines = GenericAlgorithm::perform_layout(
31 taffy,
32 root,
33 Size::NONE,
34 available_space.into_options(),
35 available_space,
36 SizingMode::InherentSize,
37 );
38
39 let layout = Layout { order: 0, size: size_and_baselines.size, location: Point::ZERO };
40 *taffy.layout_mut(root) = layout;
41
42 // If rounding is enabled, recursively round the layout's of this node and all children
43 if taffy.config.use_rounding {
44 round_layout(taffy, root, 0.0, 0.0);
45 }
46
47 Ok(())
48}
49
50/// A common interface that all Taffy layout algorithms conform to
51pub(crate) trait LayoutAlgorithm {
52 /// The name of the algorithm (mainly used for debug purposes)
53 const NAME: &'static str;
54
55 /// Compute the size of the node given the specified constraints
56 fn measure_size(
57 tree: &mut impl LayoutTree,
58 node: Node,
59 known_dimensions: Size<Option<f32>>,
60 parent_size: Size<Option<f32>>,
61 available_space: Size<AvailableSpace>,
62 sizing_mode: SizingMode,
63 ) -> Size<f32>;
64
65 /// Perform a full layout on the node given the specified constraints
66 fn perform_layout(
67 tree: &mut impl LayoutTree,
68 node: Node,
69 known_dimensions: Size<Option<f32>>,
70 parent_size: Size<Option<f32>>,
71 available_space: Size<AvailableSpace>,
72 sizing_mode: SizingMode,
73 ) -> SizeAndBaselines;
74}
75
76/// The public interface to a generic algorithm that abstracts over all of Taffy's algorithms
77/// and applies the correct one based on the `Display` style
78pub struct GenericAlgorithm;
79impl LayoutAlgorithm for GenericAlgorithm {
80 const NAME: &'static str = "GENERIC";
81
82 fn perform_layout(
83 tree: &mut impl LayoutTree,
84 node: Node,
85 known_dimensions: Size<Option<f32>>,
86 parent_size: Size<Option<f32>>,
87 available_space: Size<AvailableSpace>,
88 sizing_mode: SizingMode,
89 ) -> SizeAndBaselines {
90 compute_node_layout(
91 tree,
92 node,
93 known_dimensions,
94 parent_size,
95 available_space,
96 RunMode::PeformLayout,
97 sizing_mode,
98 )
99 }
100
101 fn measure_size(
102 tree: &mut impl LayoutTree,
103 node: Node,
104 known_dimensions: Size<Option<f32>>,
105 parent_size: Size<Option<f32>>,
106 available_space: Size<AvailableSpace>,
107 sizing_mode: SizingMode,
108 ) -> Size<f32> {
109 compute_node_layout(
110 tree,
111 node,
112 known_dimensions,
113 parent_size,
114 available_space,
115 RunMode::ComputeSize,
116 sizing_mode,
117 )
118 .size
119 }
120}
121
122/// Updates the stored layout of the provided `node` and its children
123fn compute_node_layout(
124 tree: &mut impl LayoutTree,
125 node: Node,
126 known_dimensions: Size<Option<f32>>,
127 parent_size: Size<Option<f32>>,
128 available_space: Size<AvailableSpace>,
129 run_mode: RunMode,
130 sizing_mode: SizingMode,
131) -> SizeAndBaselines {
132 #[cfg(any(feature = "debug", feature = "profile"))]
133 NODE_LOGGER.push_node(node);
134 #[cfg(feature = "debug")]
135 println!();
136
137 // First we check if we have a cached result for the given input
138 let cache_run_mode = if tree.is_childless(node) { RunMode::PeformLayout } else { run_mode };
139 if let Some(cached_size_and_baselines) =
140 compute_from_cache(tree, node, known_dimensions, available_space, cache_run_mode)
141 {
142 #[cfg(feature = "debug")]
143 NODE_LOGGER.labelled_debug_log("CACHE", cached_size_and_baselines.size);
144 #[cfg(feature = "debug")]
145 debug_log_node(known_dimensions, parent_size, available_space, run_mode, sizing_mode);
146 #[cfg(any(feature = "debug", feature = "profile"))]
147 NODE_LOGGER.pop_node();
148 return cached_size_and_baselines;
149 }
150
151 #[cfg(feature = "debug")]
152 debug_log_node(known_dimensions, parent_size, available_space, run_mode, sizing_mode);
153
154 /// Inlined function generic over the LayoutAlgorithm to reduce code duplication
155 #[inline(always)]
156 fn perform_computations<Algorithm: LayoutAlgorithm>(
157 tree: &mut impl LayoutTree,
158 node: Node,
159 known_dimensions: Size<Option<f32>>,
160 parent_size: Size<Option<f32>>,
161 available_space: Size<AvailableSpace>,
162 run_mode: RunMode,
163 sizing_mode: SizingMode,
164 ) -> SizeAndBaselines {
165 #[cfg(feature = "debug")]
166 NODE_LOGGER.log(Algorithm::NAME);
167
168 match run_mode {
169 RunMode::PeformLayout => {
170 Algorithm::perform_layout(tree, node, known_dimensions, parent_size, available_space, sizing_mode)
171 }
172 RunMode::ComputeSize => {
173 let size =
174 Algorithm::measure_size(tree, node, known_dimensions, parent_size, available_space, sizing_mode);
175 SizeAndBaselines { size, first_baselines: Point::NONE }
176 }
177 }
178 }
179
180 let display_mode = tree.style(node).display;
181 let has_children = !tree.is_childless(node);
182 let computed_size_and_baselines = match (display_mode, has_children) {
183 (Display::None, _) => perform_computations::<HiddenAlgorithm>(
184 tree,
185 node,
186 known_dimensions,
187 parent_size,
188 available_space,
189 run_mode,
190 sizing_mode,
191 ),
192 (Display::Flex, true) => perform_computations::<FlexboxAlgorithm>(
193 tree,
194 node,
195 known_dimensions,
196 parent_size,
197 available_space,
198 run_mode,
199 sizing_mode,
200 ),
201 #[cfg(feature = "grid")]
202 (Display::Grid, true) => perform_computations::<CssGridAlgorithm>(
203 tree,
204 node,
205 known_dimensions,
206 parent_size,
207 available_space,
208 run_mode,
209 sizing_mode,
210 ),
211 (_, false) => perform_computations::<LeafAlgorithm>(
212 tree,
213 node,
214 known_dimensions,
215 parent_size,
216 available_space,
217 run_mode,
218 sizing_mode,
219 ),
220 };
221
222 // Cache result
223 let cache_slot = compute_cache_slot(known_dimensions, available_space);
224 *tree.cache_mut(node, cache_slot) = Some(Cache {
225 known_dimensions,
226 available_space,
227 run_mode: cache_run_mode,
228 cached_size_and_baselines: computed_size_and_baselines,
229 });
230
231 #[cfg(feature = "debug")]
232 NODE_LOGGER.labelled_debug_log("RESULT", computed_size_and_baselines.size);
233 #[cfg(any(feature = "debug", feature = "profile"))]
234 NODE_LOGGER.pop_node();
235
236 computed_size_and_baselines
237}
238
239#[cfg(feature = "debug")]
240fn debug_log_node(
241 known_dimensions: Size<Option<f32>>,
242 parent_size: Size<Option<f32>>,
243 available_space: Size<AvailableSpace>,
244 run_mode: RunMode,
245 sizing_mode: SizingMode,
246) {
247 NODE_LOGGER.debug_log(run_mode);
248 NODE_LOGGER.labelled_debug_log("sizing_mode", sizing_mode);
249 NODE_LOGGER.labelled_debug_log("known_dimensions", known_dimensions);
250 NODE_LOGGER.labelled_debug_log("parent_size", parent_size);
251 NODE_LOGGER.labelled_debug_log("available_space", available_space);
252}
253
254/// Return the cache slot to cache the current computed result in
255///
256/// ## Caching Strategy
257///
258/// We need multiple cache slots, because a node's size is often queried by it's parent multiple times in the course of the layout
259/// process, and we don't want later results to clobber earlier ones.
260///
261/// The two variables that we care about when determining cache slot are:
262///
263/// - How many "known_dimensions" are set. In the worst case, a node may be called first with neither dimensions known known_dimensions,
264/// then with one dimension known (either width of height - which doesn't matter for our purposes here), and then with both dimensions
265/// known.
266/// - Whether unknown dimensions are being sized under a min-content or a max-content available space constraint (definite available space
267/// shares a cache slot with max-content because a node will generally be sized under one or the other but not both).
268///
269/// ## Cache slots:
270///
271/// - Slot 0: Both known_dimensions were set
272/// - Slot 1: 1 of 2 known_dimensions were set and the other dimension was either a MaxContent or Definite available space constraint
273/// - Slot 2: 1 of 2 known_dimensions were set and the other dimension was a MinContent constraint
274/// - Slot 3: Neither known_dimensions were set and we are sizing under a MaxContent or Definite available space constraint
275/// - Slot 4: Neither known_dimensions were set and we are sizing under a MinContent constraint
276#[inline]
277fn compute_cache_slot(known_dimensions: Size<Option<f32>>, available_space: Size<AvailableSpace>) -> usize {
278 let has_known_width = known_dimensions.width.is_some();
279 let has_known_height = known_dimensions.height.is_some();
280
281 // Slot 0: Both known_dimensions were set
282 if has_known_width && has_known_height {
283 return 0;
284 }
285
286 // Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
287 // Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
288 if has_known_width && !has_known_height {
289 return 1 + (available_space.height == AvailableSpace::MinContent) as usize;
290 }
291
292 // Slot 3: height but not width known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
293 // Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
294 if !has_known_width && has_known_height {
295 return 3 + (available_space.width == AvailableSpace::MinContent) as usize;
296 }
297
298 // Slot 5: Neither known_dimensions were set and we are sizing under a MaxContent or Definite available space constraint
299 // Slot 6: Neither known_dimensions were set and we are sizing under a MinContent constraint
300 5 + (available_space.width == AvailableSpace::MinContent) as usize
301}
302
303/// Try to get the computation result from the cache.
304#[inline]
305fn compute_from_cache(
306 tree: &mut impl LayoutTree,
307 node: Node,
308 known_dimensions: Size<Option<f32>>,
309 available_space: Size<AvailableSpace>,
310 run_mode: RunMode,
311) -> Option<SizeAndBaselines> {
312 for idx in 0..CACHE_SIZE {
313 let entry = tree.cache_mut(node, idx);
314 if let Some(entry) = entry {
315 // Cached ComputeSize results are not valid if we are running in PerformLayout mode
316 if entry.run_mode == RunMode::ComputeSize && run_mode == RunMode::PeformLayout {
317 return None;
318 }
319
320 let cached_size = entry.cached_size_and_baselines.size;
321
322 if (known_dimensions.width == entry.known_dimensions.width
323 || known_dimensions.width == Some(cached_size.width))
324 && (known_dimensions.height == entry.known_dimensions.height
325 || known_dimensions.height == Some(cached_size.height))
326 && (known_dimensions.width.is_some()
327 || entry.available_space.width.is_roughly_equal(available_space.width))
328 && (known_dimensions.height.is_some()
329 || entry.available_space.height.is_roughly_equal(available_space.height))
330 {
331 return Some(entry.cached_size_and_baselines);
332 }
333 }
334 }
335
336 None
337}
338
339/// The public interface to Taffy's hidden node algorithm implementation
340struct HiddenAlgorithm;
341impl LayoutAlgorithm for HiddenAlgorithm {
342 const NAME: &'static str = "NONE";
343
344 fn perform_layout(
345 tree: &mut impl LayoutTree,
346 node: Node,
347 _known_dimensions: Size<Option<f32>>,
348 _parent_size: Size<Option<f32>>,
349 _available_space: Size<AvailableSpace>,
350 _sizing_mode: SizingMode,
351 ) -> SizeAndBaselines {
352 perform_hidden_layout(tree, node);
353 SizeAndBaselines { size: Size::ZERO, first_baselines: Point::NONE }
354 }
355
356 fn measure_size(
357 _tree: &mut impl LayoutTree,
358 _node: Node,
359 _known_dimensions: Size<Option<f32>>,
360 _parent_size: Size<Option<f32>>,
361 _available_space: Size<AvailableSpace>,
362 _sizing_mode: SizingMode,
363 ) -> Size<f32> {
364 Size::ZERO
365 }
366}
367
368/// Creates a layout for this node and its children, recursively.
369/// Each hidden node has zero size and is placed at the origin
370fn perform_hidden_layout(tree: &mut impl LayoutTree, node: Node) {
371 /// Recursive function to apply hidden layout to all descendents
372 fn perform_hidden_layout_inner(tree: &mut impl LayoutTree, node: Node, order: u32) {
373 *tree.layout_mut(node) = Layout::with_order(order);
374 for i in 0..7 {
375 *tree.cache_mut(node, i) = None;
376 }
377 for order in 0..tree.child_count(node) {
378 perform_hidden_layout_inner(tree, tree.child(node, order), order as _);
379 }
380 }
381
382 for order in 0..tree.child_count(node) {
383 perform_hidden_layout_inner(tree, tree.child(node, order), order as _);
384 }
385}
386
387/// Rounds the calculated [`Layout`] to exact pixel values
388/// In order to ensure that no gaps in the layout are introduced we:
389/// - Always round based on the absolute coordinates rather than parent-relative coordinates
390/// - Compute width/height by first rounding the top/bottom/left/right and then computing the difference
391/// rather than rounding the width/height directly
392///
393/// See <https://github.com/facebook/yoga/commit/aa5b296ac78f7a22e1aeaf4891243c6bb76488e2> for more context
394fn round_layout(tree: &mut impl LayoutTree, node: Node, abs_x: f32, abs_y: f32) {
395 let layout = tree.layout_mut(node);
396 let abs_x = abs_x + layout.location.x;
397 let abs_y = abs_y + layout.location.y;
398
399 layout.location.x = round(layout.location.x);
400 layout.location.y = round(layout.location.y);
401 layout.size.width = round(abs_x + layout.size.width) - round(abs_x);
402 layout.size.height = round(abs_y + layout.size.height) - round(abs_y);
403
404 let child_count = tree.child_count(node);
405 for index in 0..child_count {
406 let child = tree.child(node, index);
407 round_layout(tree, child, abs_x, abs_y);
408 }
409}
410
411#[cfg(test)]
412mod tests {
413 use super::perform_hidden_layout;
414 use crate::geometry::{Point, Size};
415 use crate::style::{Display, Style};
416 use crate::Taffy;
417
418 #[test]
419 fn hidden_layout_should_hide_recursively() {
420 let mut taffy = Taffy::new();
421
422 let style: Style = Style { display: Display::Flex, size: Size::from_points(50.0, 50.0), ..Default::default() };
423
424 let grandchild_00 = taffy.new_leaf(style.clone()).unwrap();
425 let grandchild_01 = taffy.new_leaf(style.clone()).unwrap();
426 let child_00 = taffy.new_with_children(style.clone(), &[grandchild_00, grandchild_01]).unwrap();
427
428 let grandchild_02 = taffy.new_leaf(style.clone()).unwrap();
429 let child_01 = taffy.new_with_children(style.clone(), &[grandchild_02]).unwrap();
430
431 let root = taffy
432 .new_with_children(
433 Style { display: Display::None, size: Size::from_points(50.0, 50.0), ..Default::default() },
434 &[child_00, child_01],
435 )
436 .unwrap();
437
438 perform_hidden_layout(&mut taffy, root);
439
440 // Whatever size and display-mode the nodes had previously,
441 // all layouts should resolve to ZERO due to the root's DISPLAY::NONE
442 for (node, _) in taffy.nodes.iter().filter(|(node, _)| *node != root) {
443 if let Ok(layout) = taffy.layout(node) {
444 assert_eq!(layout.size, Size::zero());
445 assert_eq!(layout.location, Point::zero());
446 }
447 }
448 }
449}