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