Moving flexbox behind a feature flag (#414)
1//! The layout algorithms themselves
2
3pub(crate) mod common;
4pub(crate) mod leaf;
5
6#[cfg(feature = "flexbox")]
7pub(crate) mod flexbox;
8
9#[cfg(feature = "grid")]
10pub(crate) mod grid;
11
12use crate::data::CACHE_SIZE;
13use crate::error::TaffyError;
14use crate::geometry::{Point, Size};
15use crate::layout::{Cache, Layout, RunMode, SizeAndBaselines, SizingMode};
16use crate::node::{Node, Taffy};
17use crate::style::{AvailableSpace, Display};
18use crate::sys::round;
19use crate::tree::LayoutTree;
20
21#[cfg(feature = "flexbox")]
22use self::flexbox::FlexboxAlgorithm;
23
24#[cfg(feature = "grid")]
25use self::grid::CssGridAlgorithm;
26use self::leaf::LeafAlgorithm;
27
28#[cfg(any(feature = "debug", feature = "profile"))]
29use crate::debug::NODE_LOGGER;
30
31/// Updates the stored layout of the provided `node` and its children
32pub fn compute_layout(taffy: &mut Taffy, root: Node, available_space: Size<AvailableSpace>) -> Result<(), TaffyError> {
33 // Recursively compute node layout
34 let size_and_baselines = GenericAlgorithm::perform_layout(
35 taffy,
36 root,
37 Size::NONE,
38 available_space.into_options(),
39 available_space,
40 SizingMode::InherentSize,
41 );
42
43 let layout = Layout { order: 0, size: size_and_baselines.size, location: Point::ZERO };
44 *taffy.layout_mut(root) = layout;
45
46 // If rounding is enabled, recursively round the layout's of this node and all children
47 if taffy.config.use_rounding {
48 round_layout(taffy, root, 0.0, 0.0);
49 }
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 #[cfg(feature = "flexbox")]
197 (Display::Flex, true) => perform_computations::<FlexboxAlgorithm>(
198 tree,
199 node,
200 known_dimensions,
201 parent_size,
202 available_space,
203 run_mode,
204 sizing_mode,
205 ),
206 #[cfg(feature = "grid")]
207 (Display::Grid, true) => perform_computations::<CssGridAlgorithm>(
208 tree,
209 node,
210 known_dimensions,
211 parent_size,
212 available_space,
213 run_mode,
214 sizing_mode,
215 ),
216 (_, false) => perform_computations::<LeafAlgorithm>(
217 tree,
218 node,
219 known_dimensions,
220 parent_size,
221 available_space,
222 run_mode,
223 sizing_mode,
224 ),
225 };
226
227 // Cache result
228 let cache_slot = compute_cache_slot(known_dimensions, available_space);
229 *tree.cache_mut(node, cache_slot) = Some(Cache {
230 known_dimensions,
231 available_space,
232 run_mode: cache_run_mode,
233 cached_size_and_baselines: computed_size_and_baselines,
234 });
235
236 #[cfg(feature = "debug")]
237 NODE_LOGGER.labelled_debug_log("RESULT", computed_size_and_baselines.size);
238 #[cfg(any(feature = "debug", feature = "profile"))]
239 NODE_LOGGER.pop_node();
240
241 computed_size_and_baselines
242}
243
244#[cfg(feature = "debug")]
245fn debug_log_node(
246 known_dimensions: Size<Option<f32>>,
247 parent_size: Size<Option<f32>>,
248 available_space: Size<AvailableSpace>,
249 run_mode: RunMode,
250 sizing_mode: SizingMode,
251) {
252 NODE_LOGGER.debug_log(run_mode);
253 NODE_LOGGER.labelled_debug_log("sizing_mode", sizing_mode);
254 NODE_LOGGER.labelled_debug_log("known_dimensions", known_dimensions);
255 NODE_LOGGER.labelled_debug_log("parent_size", parent_size);
256 NODE_LOGGER.labelled_debug_log("available_space", available_space);
257}
258
259/// Return the cache slot to cache the current computed result in
260///
261/// ## Caching Strategy
262///
263/// 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
264/// process, and we don't want later results to clobber earlier ones.
265///
266/// The two variables that we care about when determining cache slot are:
267///
268/// - How many "known_dimensions" are set. In the worst case, a node may be called first with neither dimensions known known_dimensions,
269/// then with one dimension known (either width of height - which doesn't matter for our purposes here), and then with both dimensions
270/// known.
271/// - Whether unknown dimensions are being sized under a min-content or a max-content available space constraint (definite available space
272/// shares a cache slot with max-content because a node will generally be sized under one or the other but not both).
273///
274/// ## Cache slots:
275///
276/// - Slot 0: Both known_dimensions were set
277/// - Slot 1: 1 of 2 known_dimensions were set and the other dimension was either a MaxContent or Definite available space constraint
278/// - Slot 2: 1 of 2 known_dimensions were set and the other dimension was a MinContent constraint
279/// - Slot 3: Neither known_dimensions were set and we are sizing under a MaxContent or Definite available space constraint
280/// - Slot 4: Neither known_dimensions were set and we are sizing under a MinContent constraint
281#[inline]
282fn compute_cache_slot(known_dimensions: Size<Option<f32>>, available_space: Size<AvailableSpace>) -> usize {
283 let has_known_width = known_dimensions.width.is_some();
284 let has_known_height = known_dimensions.height.is_some();
285
286 // Slot 0: Both known_dimensions were set
287 if has_known_width && has_known_height {
288 return 0;
289 }
290
291 // Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
292 // Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
293 if has_known_width && !has_known_height {
294 return 1 + (available_space.height == AvailableSpace::MinContent) as usize;
295 }
296
297 // Slot 3: height but not width known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
298 // Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
299 if !has_known_width && has_known_height {
300 return 3 + (available_space.width == AvailableSpace::MinContent) as usize;
301 }
302
303 // Slot 5: Neither known_dimensions were set and we are sizing under a MaxContent or Definite available space constraint
304 // Slot 6: Neither known_dimensions were set and we are sizing under a MinContent constraint
305 5 + (available_space.width == AvailableSpace::MinContent) as usize
306}
307
308/// Try to get the computation result from the cache.
309#[inline]
310fn compute_from_cache(
311 tree: &mut impl LayoutTree,
312 node: Node,
313 known_dimensions: Size<Option<f32>>,
314 available_space: Size<AvailableSpace>,
315 run_mode: RunMode,
316) -> Option<SizeAndBaselines> {
317 for idx in 0..CACHE_SIZE {
318 let entry = tree.cache_mut(node, idx);
319 if let Some(entry) = entry {
320 // Cached ComputeSize results are not valid if we are running in PerformLayout mode
321 if entry.run_mode == RunMode::ComputeSize && run_mode == RunMode::PeformLayout {
322 return None;
323 }
324
325 let cached_size = entry.cached_size_and_baselines.size;
326
327 if (known_dimensions.width == entry.known_dimensions.width
328 || known_dimensions.width == Some(cached_size.width))
329 && (known_dimensions.height == entry.known_dimensions.height
330 || known_dimensions.height == Some(cached_size.height))
331 && (known_dimensions.width.is_some()
332 || entry.available_space.width.is_roughly_equal(available_space.width))
333 && (known_dimensions.height.is_some()
334 || entry.available_space.height.is_roughly_equal(available_space.height))
335 {
336 return Some(entry.cached_size_and_baselines);
337 }
338 }
339 }
340
341 None
342}
343
344/// The public interface to Taffy's hidden node algorithm implementation
345struct HiddenAlgorithm;
346impl LayoutAlgorithm for HiddenAlgorithm {
347 const NAME: &'static str = "NONE";
348
349 fn perform_layout(
350 tree: &mut impl LayoutTree,
351 node: Node,
352 _known_dimensions: Size<Option<f32>>,
353 _parent_size: Size<Option<f32>>,
354 _available_space: Size<AvailableSpace>,
355 _sizing_mode: SizingMode,
356 ) -> SizeAndBaselines {
357 perform_hidden_layout(tree, node);
358 SizeAndBaselines { size: Size::ZERO, first_baselines: Point::NONE }
359 }
360
361 fn measure_size(
362 _tree: &mut impl LayoutTree,
363 _node: Node,
364 _known_dimensions: Size<Option<f32>>,
365 _parent_size: Size<Option<f32>>,
366 _available_space: Size<AvailableSpace>,
367 _sizing_mode: SizingMode,
368 ) -> Size<f32> {
369 Size::ZERO
370 }
371}
372
373/// Creates a layout for this node and its children, recursively.
374/// Each hidden node has zero size and is placed at the origin
375fn perform_hidden_layout(tree: &mut impl LayoutTree, node: Node) {
376 /// Recursive function to apply hidden layout to all descendents
377 fn perform_hidden_layout_inner(tree: &mut impl LayoutTree, node: Node, order: u32) {
378 *tree.layout_mut(node) = Layout::with_order(order);
379 for order in 0..tree.child_count(node) {
380 perform_hidden_layout_inner(tree, tree.child(node, order), order as _);
381 }
382 }
383
384 for order in 0..tree.child_count(node) {
385 perform_hidden_layout_inner(tree, tree.child(node, order), order as _);
386 }
387}
388
389/// Rounds the calculated [`Layout`] to exact pixel values
390/// In order to ensure that no gaps in the layout are introduced we:
391/// - Always round based on the absolute coordinates rather than parent-relative coordinates
392/// - Compute width/height by first rounding the top/bottom/left/right and then computing the difference
393/// rather than rounding the width/height directly
394///
395/// See <https://github.com/facebook/yoga/commit/aa5b296ac78f7a22e1aeaf4891243c6bb76488e2> for more context
396fn round_layout(tree: &mut impl LayoutTree, node: Node, abs_x: f32, abs_y: f32) {
397 let layout = tree.layout_mut(node);
398 let abs_x = abs_x + layout.location.x;
399 let abs_y = abs_y + layout.location.y;
400
401 layout.location.x = round(layout.location.x);
402 layout.location.y = round(layout.location.y);
403 layout.size.width = round(abs_x + layout.size.width) - round(abs_x);
404 layout.size.height = round(abs_y + layout.size.height) - round(abs_y);
405
406 let child_count = tree.child_count(node);
407 for index in 0..child_count {
408 let child = tree.child(node, index);
409 round_layout(tree, child, abs_x, abs_y);
410 }
411}
412
413#[cfg(test)]
414mod tests {
415 use super::perform_hidden_layout;
416 use crate::geometry::{Point, Size};
417 use crate::style::{Display, Style};
418 use crate::Taffy;
419
420 #[test]
421 fn hidden_layout_should_hide_recursively() {
422 let mut taffy = Taffy::new();
423
424 let style: Style = Style { display: Display::Flex, size: Size::from_points(50.0, 50.0), ..Default::default() };
425
426 let grandchild_00 = taffy.new_leaf(style.clone()).unwrap();
427 let grandchild_01 = taffy.new_leaf(style.clone()).unwrap();
428 let child_00 = taffy.new_with_children(style.clone(), &[grandchild_00, grandchild_01]).unwrap();
429
430 let grandchild_02 = taffy.new_leaf(style.clone()).unwrap();
431 let child_01 = taffy.new_with_children(style.clone(), &[grandchild_02]).unwrap();
432
433 let root = taffy
434 .new_with_children(
435 Style { display: Display::None, size: Size::from_points(50.0, 50.0), ..Default::default() },
436 &[child_00, child_01],
437 )
438 .unwrap();
439
440 perform_hidden_layout(&mut taffy, root);
441
442 // Whatever size and display-mode the nodes had previously,
443 // all layouts should resolve to ZERO due to the root's DISPLAY::NONE
444 for (node, _) in taffy.nodes.iter().filter(|(node, _)| *node != root) {
445 if let Ok(layout) = taffy.layout(node) {
446 assert_eq!(layout.size, Size::zero());
447 assert_eq!(layout.location, Point::zero());
448 }
449 }
450 }
451}