Fix rounding accumulation bug (#521)
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 dimensions known known_dimensions,
268/// then with one dimension known (either width of height - which doesn't matter for our purposes here), and then with both dimensions
269/// known.
270/// - Whether unknown dimensions are being sized under a min-content or a max-content available space constraint (definite available space
271/// shares a cache slot with max-content because a node will generally be sized under one or the other but not both).
272///
273/// ## Cache slots:
274///
275/// - Slot 0: Both known_dimensions were set
276/// - Slot 1: 1 of 2 known_dimensions were set and the other dimension was either a MaxContent or Definite available space constraint
277/// - Slot 2: 1 of 2 known_dimensions were set and the other dimension was a MinContent constraint
278/// - Slot 3: Neither known_dimensions were set and we are sizing under a MaxContent or Definite available space constraint
279/// - Slot 4: Neither known_dimensions were set and we are sizing under a MinContent constraint
280#[inline]
281fn compute_cache_slot(known_dimensions: Size<Option<f32>>, available_space: Size<AvailableSpace>) -> usize {
282 let has_known_width = known_dimensions.width.is_some();
283 let has_known_height = known_dimensions.height.is_some();
284
285 // Slot 0: Both known_dimensions were set
286 if has_known_width && has_known_height {
287 return 0;
288 }
289
290 // Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
291 // Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
292 if has_known_width && !has_known_height {
293 return 1 + (available_space.height == AvailableSpace::MinContent) as usize;
294 }
295
296 // Slot 3: height but not width known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
297 // Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
298 if !has_known_width && has_known_height {
299 return 3 + (available_space.width == AvailableSpace::MinContent) as usize;
300 }
301
302 // Slot 5: Neither known_dimensions were set and we are sizing under a MaxContent or Definite available space constraint
303 // Slot 6: Neither known_dimensions were set and we are sizing under a MinContent constraint
304 5 + (available_space.width == AvailableSpace::MinContent) as usize
305}
306
307/// Try to get the computation result from the cache.
308#[inline]
309fn compute_from_cache(
310 tree: &mut impl LayoutTree,
311 node: Node,
312 known_dimensions: Size<Option<f32>>,
313 available_space: Size<AvailableSpace>,
314 run_mode: RunMode,
315) -> Option<SizeAndBaselines> {
316 for idx in 0..CACHE_SIZE {
317 let entry = tree.cache_mut(node, idx);
318 if let Some(entry) = entry {
319 // Cached ComputeSize results are not valid if we are running in PerformLayout mode
320 if entry.run_mode == RunMode::ComputeSize && run_mode == RunMode::PeformLayout {
321 return None;
322 }
323
324 let cached_size = entry.cached_size_and_baselines.size;
325
326 if (known_dimensions.width == entry.known_dimensions.width
327 || known_dimensions.width == Some(cached_size.width))
328 && (known_dimensions.height == entry.known_dimensions.height
329 || known_dimensions.height == Some(cached_size.height))
330 && (known_dimensions.width.is_some()
331 || entry.available_space.width.is_roughly_equal(available_space.width))
332 && (known_dimensions.height.is_some()
333 || entry.available_space.height.is_roughly_equal(available_space.height))
334 {
335 return Some(entry.cached_size_and_baselines);
336 }
337 }
338 }
339
340 None
341}
342
343/// The public interface to Taffy's hidden node algorithm implementation
344struct HiddenAlgorithm;
345impl LayoutAlgorithm for HiddenAlgorithm {
346 const NAME: &'static str = "NONE";
347
348 fn perform_layout(
349 tree: &mut impl LayoutTree,
350 node: Node,
351 _known_dimensions: Size<Option<f32>>,
352 _parent_size: Size<Option<f32>>,
353 _available_space: Size<AvailableSpace>,
354 _sizing_mode: SizingMode,
355 ) -> SizeAndBaselines {
356 perform_hidden_layout(tree, node);
357 SizeAndBaselines { size: Size::ZERO, first_baselines: Point::NONE }
358 }
359
360 fn measure_size(
361 _tree: &mut impl LayoutTree,
362 _node: Node,
363 _known_dimensions: Size<Option<f32>>,
364 _parent_size: Size<Option<f32>>,
365 _available_space: Size<AvailableSpace>,
366 _sizing_mode: SizingMode,
367 ) -> Size<f32> {
368 Size::ZERO
369 }
370}
371
372/// Creates a layout for this node and its children, recursively.
373/// Each hidden node has zero size and is placed at the origin
374fn perform_hidden_layout(tree: &mut impl LayoutTree, node: Node) {
375 /// Recursive function to apply hidden layout to all descendents
376 fn perform_hidden_layout_inner(tree: &mut impl LayoutTree, node: Node, order: u32) {
377 *tree.layout_mut(node) = Layout::with_order(order);
378 for i in 0..7 {
379 *tree.cache_mut(node, i) = None;
380 }
381 for order in 0..tree.child_count(node) {
382 perform_hidden_layout_inner(tree, tree.child(node, order), order as _);
383 }
384 }
385
386 for order in 0..tree.child_count(node) {
387 perform_hidden_layout_inner(tree, tree.child(node, order), order as _);
388 }
389}
390
391/// Rounds the calculated [`Layout`] to exact pixel values
392///
393/// In order to ensure that no gaps in the layout are introduced we:
394/// - Always round based on the cumulative x/y coordinates (relative to the viewport) rather than
395/// parent-relative coordinates
396/// - Compute width/height by first rounding the top/bottom/left/right and then computing the difference
397/// rather than rounding the width/height directly
398/// See <https://github.com/facebook/yoga/commit/aa5b296ac78f7a22e1aeaf4891243c6bb76488e2> for more context
399///
400/// In order to prevent innacuracies caused by rounding already-rounded values, we read from `unrounded_layout`
401/// and write to `final_layout`.
402fn round_layout(tree: &mut Taffy, node_id: Node, cumulative_x: f32, cumulative_y: f32) {
403 let node = &mut tree.nodes[node_id];
404 let unrounded_layout = node.unrounded_layout;
405 let layout = &mut node.final_layout;
406
407 let cumulative_x = cumulative_x + unrounded_layout.location.x;
408 let cumulative_y = cumulative_y + unrounded_layout.location.y;
409
410 layout.location.x = round(unrounded_layout.location.x);
411 layout.location.y = round(unrounded_layout.location.y);
412 layout.size.width = round(cumulative_x + unrounded_layout.size.width) - round(cumulative_x);
413 layout.size.height = round(cumulative_y + unrounded_layout.size.height) - round(cumulative_y);
414
415 let child_count = tree.child_count(node_id).unwrap();
416 for index in 0..child_count {
417 let child = tree.child(node_id, index);
418 round_layout(tree, child, cumulative_x, cumulative_y);
419 }
420}
421
422#[cfg(test)]
423mod tests {
424 use super::perform_hidden_layout;
425 use crate::geometry::{Point, Size};
426 use crate::style::{Display, Style};
427 use crate::Taffy;
428
429 #[test]
430 fn hidden_layout_should_hide_recursively() {
431 let mut taffy = Taffy::new();
432
433 let style: Style = Style { display: Display::Flex, size: Size::from_points(50.0, 50.0), ..Default::default() };
434
435 let grandchild_00 = taffy.new_leaf(style.clone()).unwrap();
436 let grandchild_01 = taffy.new_leaf(style.clone()).unwrap();
437 let child_00 = taffy.new_with_children(style.clone(), &[grandchild_00, grandchild_01]).unwrap();
438
439 let grandchild_02 = taffy.new_leaf(style.clone()).unwrap();
440 let child_01 = taffy.new_with_children(style.clone(), &[grandchild_02]).unwrap();
441
442 let root = taffy
443 .new_with_children(
444 Style { display: Display::None, size: Size::from_points(50.0, 50.0), ..Default::default() },
445 &[child_00, child_01],
446 )
447 .unwrap();
448
449 perform_hidden_layout(&mut taffy, root);
450
451 // Whatever size and display-mode the nodes had previously,
452 // all layouts should resolve to ZERO due to the root's DISPLAY::NONE
453 for (node, _) in taffy.nodes.iter().filter(|(node, _)| *node != root) {
454 if let Ok(layout) = taffy.layout(node) {
455 assert_eq!(layout.size, Size::zero());
456 assert_eq!(layout.location, Point::zero());
457 }
458 }
459 }
460}