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