Fix 1px wide gaps between adjacent UI nodes (#374)
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, sizing_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 computed_size_and_baselines = if tree.is_childless(node) {
181 perform_computations::<LeafAlgorithm>(
182 tree,
183 node,
184 known_dimensions,
185 parent_size,
186 available_space,
187 run_mode,
188 sizing_mode,
189 )
190 } else {
191 match tree.style(node).display {
192 Display::Flex => 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 => perform_computations::<CssGridAlgorithm>(
203 tree,
204 node,
205 known_dimensions,
206 parent_size,
207 available_space,
208 run_mode,
209 sizing_mode,
210 ),
211 Display::None => perform_computations::<HiddenAlgorithm>(
212 tree,
213 node,
214 known_dimensions,
215 parent_size,
216 available_space,
217 run_mode,
218 sizing_mode,
219 ),
220 }
221 };
222
223 // Cache result
224 let cache_slot = compute_cache_slot(known_dimensions, available_space);
225 *tree.cache_mut(node, cache_slot) = Some(Cache {
226 known_dimensions,
227 available_space,
228 run_mode: cache_run_mode,
229 cached_size_and_baselines: computed_size_and_baselines,
230 });
231
232 #[cfg(feature = "debug")]
233 NODE_LOGGER.labelled_debug_log("RESULT", computed_size_and_baselines.size);
234 #[cfg(any(feature = "debug", feature = "profile"))]
235 NODE_LOGGER.pop_node();
236
237 computed_size_and_baselines
238}
239
240#[cfg(feature = "debug")]
241fn debug_log_node(
242 known_dimensions: Size<Option<f32>>,
243 parent_size: Size<Option<f32>>,
244 available_space: Size<AvailableSpace>,
245 run_mode: RunMode,
246 sizing_mode: SizingMode,
247) {
248 NODE_LOGGER.debug_log(run_mode);
249 NODE_LOGGER.labelled_debug_log("sizing_mode", sizing_mode);
250 NODE_LOGGER.labelled_debug_log("known_dimensions", known_dimensions);
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 sizing_mode: SizingMode,
312) -> Option<SizeAndBaselines> {
313 for idx in 0..CACHE_SIZE {
314 let entry = tree.cache_mut(node, idx);
315 if let Some(entry) = entry {
316 // Cached ComputeSize results are not valid if we are running in PerformLayout mode
317 if entry.run_mode == RunMode::ComputeSize && run_mode == RunMode::PeformLayout {
318 return None;
319 }
320
321 let cached_size = entry.cached_size_and_baselines.size;
322
323 if (known_dimensions.width == entry.known_dimensions.width
324 || known_dimensions.width == Some(cached_size.width))
325 && (known_dimensions.height == entry.known_dimensions.height
326 || known_dimensions.height == Some(cached_size.height))
327 && (known_dimensions.width.is_some()
328 || entry.available_space.width.is_roughly_equal(available_space.width)
329 || (sizing_mode == SizingMode::ContentSize
330 && available_space.width.is_definite()
331 && available_space.width.unwrap() >= cached_size.width))
332 && (known_dimensions.height.is_some()
333 || entry.available_space.height.is_roughly_equal(available_space.height)
334 || (sizing_mode == SizingMode::ContentSize
335 && available_space.height.is_definite()
336 && available_space.height.unwrap() >= cached_size.height))
337 {
338 return Some(entry.cached_size_and_baselines);
339 }
340 }
341 }
342
343 None
344}
345
346/// The public interface to Taffy's hidden node algorithm implementation
347struct HiddenAlgorithm;
348impl LayoutAlgorithm for HiddenAlgorithm {
349 const NAME: &'static str = "NONE";
350
351 fn perform_layout(
352 tree: &mut impl LayoutTree,
353 node: Node,
354 _known_dimensions: Size<Option<f32>>,
355 _parent_size: Size<Option<f32>>,
356 _available_space: Size<AvailableSpace>,
357 _sizing_mode: SizingMode,
358 ) -> SizeAndBaselines {
359 perform_hidden_layout(tree, node);
360 SizeAndBaselines { size: Size::ZERO, first_baselines: Point::NONE }
361 }
362
363 fn measure_size(
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 ) -> Size<f32> {
371 Size::ZERO
372 }
373}
374
375/// Creates a layout for this node and its children, recursively.
376/// Each hidden node has zero size and is placed at the origin
377fn perform_hidden_layout(tree: &mut impl LayoutTree, node: Node) {
378 /// Recursive function to apply hidden layout to all descendents
379 fn perform_hidden_layout_inner(tree: &mut impl LayoutTree, node: Node, order: u32) {
380 *tree.layout_mut(node) = Layout::with_order(order);
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/// In order to ensure that no gaps in the layout are introduced we:
393/// - Always round based on the absolute coordinates rather than parent-relative coordinates
394/// - Compute width/height by first rounding the top/bottom/left/right and then computing the difference
395/// rather than rounding the width/height directly
396///
397/// See <https://github.com/facebook/yoga/commit/aa5b296ac78f7a22e1aeaf4891243c6bb76488e2> for more context
398fn round_layout(tree: &mut impl LayoutTree, node: Node, abs_x: f32, abs_y: f32) {
399 let layout = tree.layout_mut(node);
400 let abs_x = abs_x + layout.location.x;
401 let abs_y = abs_y + layout.location.y;
402
403 layout.location.x = round(layout.location.x);
404 layout.location.y = round(layout.location.y);
405 layout.size.width = round(abs_x + layout.size.width) - round(abs_x);
406 layout.size.height = round(abs_y + layout.size.height) - round(abs_y);
407
408 let child_count = tree.child_count(node);
409 for index in 0..child_count {
410 let child = tree.child(node, index);
411 round_layout(tree, child, abs_x, abs_y);
412 }
413}
414
415#[cfg(test)]
416mod tests {
417 use super::perform_hidden_layout;
418 use crate::geometry::{Point, Size};
419 use crate::style::{Display, Style};
420 use crate::Taffy;
421
422 #[test]
423 fn hidden_layout_should_hide_recursively() {
424 let mut taffy = Taffy::new();
425
426 let style: Style = Style { display: Display::Flex, size: Size::from_points(50.0, 50.0), ..Default::default() };
427
428 let grandchild_00 = taffy.new_leaf(style.clone()).unwrap();
429 let grandchild_01 = taffy.new_leaf(style.clone()).unwrap();
430 let child_00 = taffy.new_with_children(style.clone(), &[grandchild_00, grandchild_01]).unwrap();
431
432 let grandchild_02 = taffy.new_leaf(style.clone()).unwrap();
433 let child_01 = taffy.new_with_children(style.clone(), &[grandchild_02]).unwrap();
434
435 let root = taffy
436 .new_with_children(
437 Style { display: Display::None, size: Size::from_points(50.0, 50.0), ..Default::default() },
438 &[child_00, child_01],
439 )
440 .unwrap();
441
442 perform_hidden_layout(&mut taffy, root);
443
444 // Whatever size and display-mode the nodes had previously,
445 // all layouts should resolve to ZERO due to the root's DISPLAY::NONE
446 for (node, _) in taffy.nodes.iter().filter(|(node, _)| *node != root) {
447 if let Ok(layout) = taffy.layout(node) {
448 assert_eq!(layout.size, Size::zero());
449 assert_eq!(layout.location, Point::zero());
450 }
451 }
452 }
453}