⎇ 6ce28e1535f2ab4631d0502f2fee13d4827f2a11
src/compute/mod.rs
Ñawpa willay
Pi imata llamkarqan
ch'uya
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 NODE_LOGGER.log("COMPUTE");
154 #[cfg(feature = "debug")]
155 debug_log_node(known_dimensions, parent_size, available_space, run_mode, sizing_mode);
156
157 /// Inlined function generic over the LayoutAlgorithm to reduce code duplication
158 #[inline(always)]
159 fn perform_computations<Algorithm: LayoutAlgorithm>(
160 tree: &mut impl LayoutTree,
161 node: Node,
162 known_dimensions: Size<Option<f32>>,
163 parent_size: Size<Option<f32>>,
164 available_space: Size<AvailableSpace>,
165 run_mode: RunMode,
166 sizing_mode: SizingMode,
167 ) -> SizeAndBaselines {
168 #[cfg(feature = "debug")]
169 NODE_LOGGER.log(Algorithm::NAME);
170
171 match run_mode {
172 RunMode::PeformLayout => {
173 Algorithm::perform_layout(tree, node, known_dimensions, parent_size, available_space, sizing_mode)
174 }
175 RunMode::ComputeSize => {
176 let size =
177 Algorithm::measure_size(tree, node, known_dimensions, parent_size, available_space, sizing_mode);
178 SizeAndBaselines { size, first_baselines: Point::NONE }
179 }
180 }
181 }
182
183 let computed_size_and_baselines = if tree.is_childless(node) {
184 perform_computations::<LeafAlgorithm>(
185 tree,
186 node,
187 known_dimensions,
188 parent_size,
189 available_space,
190 run_mode,
191 sizing_mode,
192 )
193 } else {
194 match tree.style(node).display {
195 Display::Flex => perform_computations::<FlexboxAlgorithm>(
196 tree,
197 node,
198 known_dimensions,
199 parent_size,
200 available_space,
201 run_mode,
202 sizing_mode,
203 ),
204 #[cfg(feature = "grid")]
205 Display::Grid => perform_computations::<CssGridAlgorithm>(
206 tree,
207 node,
208 known_dimensions,
209 parent_size,
210 available_space,
211 run_mode,
212 sizing_mode,
213 ),
214 Display::None => perform_computations::<HiddenAlgorithm>(
215 tree,
216 node,
217 known_dimensions,
218 parent_size,
219 available_space,
220 run_mode,
221 sizing_mode,
222 ),
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.labelled_debug_log("run_mode", 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("available_space", available_space);
255}
256
257/// Return the cache slot to cache the current computed result in
258///
259/// ## Caching Strategy
260///
261/// 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
262/// process, and we don't want later results to clobber earlier ones.
263///
264/// The two variables that we care about when determining cache slot are:
265///
266/// - How many "known_dimensions" are set. In the worst case, a node may be called first with neither dimensions known known_dimensions,
267/// then with one dimension known (either width of height - which doesn't matter for our purposes here), and then with both dimensions
268/// 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/// - Slot 1: 1 of 2 known_dimensions were set and the other dimension was either a MaxContent or Definite available space constraint
276/// - Slot 2: 1 of 2 known_dimensions were set and the other dimension was a MinContent constraint
277/// - Slot 3: Neither known_dimensions were set and we are sizing under a MaxContent or Definite available space constraint
278/// - Slot 4: Neither known_dimensions were set and we are sizing under a MinContent constraint
279#[inline]
280fn compute_cache_slot(known_dimensions: Size<Option<f32>>, available_space: Size<AvailableSpace>) -> usize {
281 let has_known_width = known_dimensions.width.is_some();
282 let has_known_height = known_dimensions.height.is_some();
283
284 // Slot 0: Both known_dimensions were set
285 if has_known_width && has_known_height {
286 return 0;
287 }
288
289 // Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
290 // Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
291 if has_known_width && !has_known_height {
292 return 1 + (available_space.height == AvailableSpace::MinContent) as usize;
293 }
294
295 // Slot 3: height but not width known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
296 // Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
297 if !has_known_width && has_known_height {
298 return 3 + (available_space.width == AvailableSpace::MinContent) as usize;
299 }
300
301 // Slot 5: Neither known_dimensions were set and we are sizing under a MaxContent or Definite available space constraint
302 // Slot 6: Neither known_dimensions were set and we are sizing under a MinContent constraint
303 5 + (available_space.width == AvailableSpace::MinContent) as usize
304}
305
306/// Try to get the computation result from the cache.
307#[inline]
308fn compute_from_cache(
309 tree: &mut impl LayoutTree,
310 node: Node,
311 known_dimensions: Size<Option<f32>>,
312 available_space: Size<AvailableSpace>,
313 run_mode: RunMode,
314 sizing_mode: SizingMode,
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 || (sizing_mode == SizingMode::ContentSize
333 && available_space.width.is_definite()
334 && available_space.width.unwrap() >= cached_size.width))
335 && (known_dimensions.height.is_some()
336 || entry.available_space.height.is_roughly_equal(available_space.height)
337 || (sizing_mode == SizingMode::ContentSize
338 && available_space.height.is_definite()
339 && available_space.height.unwrap() >= cached_size.height))
340 {
341 return Some(entry.cached_size_and_baselines);
342 }
343 }
344 }
345
346 None
347}
348
349/// The public interface to Taffy's hidden node algorithm implementation
350struct HiddenAlgorithm;
351impl LayoutAlgorithm for HiddenAlgorithm {
352 const NAME: &'static str = "NONE";
353
354 fn perform_layout(
355 tree: &mut impl LayoutTree,
356 node: Node,
357 _known_dimensions: Size<Option<f32>>,
358 _parent_size: Size<Option<f32>>,
359 _available_space: Size<AvailableSpace>,
360 _sizing_mode: SizingMode,
361 ) -> SizeAndBaselines {
362 perform_hidden_layout(tree, node);
363 SizeAndBaselines { size: Size::ZERO, first_baselines: Point::NONE }
364 }
365
366 fn measure_size(
367 _tree: &mut impl LayoutTree,
368 _node: Node,
369 _known_dimensions: Size<Option<f32>>,
370 _parent_size: Size<Option<f32>>,
371 _available_space: Size<AvailableSpace>,
372 _sizing_mode: SizingMode,
373 ) -> Size<f32> {
374 Size::ZERO
375 }
376}
377
378/// Creates a layout for this node and its children, recursively.
379/// Each hidden node has zero size and is placed at the origin
380fn perform_hidden_layout(tree: &mut impl LayoutTree, node: Node) {
381 /// Recursive function to apply hidden layout to all descendents
382 fn perform_hidden_layout_inner(tree: &mut impl LayoutTree, node: Node, order: u32) {
383 *tree.layout_mut(node) = Layout::with_order(order);
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 for order in 0..tree.child_count(node) {
390 perform_hidden_layout_inner(tree, tree.child(node, order), order as _);
391 }
392}
393
394/// Rounds the calculated [`NodeData`] according to the spec
395fn round_layout(tree: &mut impl LayoutTree, root: Node) {
396 let layout = tree.layout_mut(root);
397
398 layout.location.x = round(layout.location.x);
399 layout.location.y = round(layout.location.y);
400
401 layout.size.width = round(layout.size.width);
402 layout.size.height = round(layout.size.height);
403
404 // Satisfy the borrow checker here by re-indexing to shorten the lifetime to the loop scope
405 for x in 0..tree.child_count(root) {
406 let child = tree.child(root, x);
407 round_layout(tree, child);
408 }
409}
410
411#[cfg(test)]
412mod tests {
413 use super::perform_hidden_layout;
414 use crate::geometry::{Point, Size};
415 use crate::style::{Display, Style};
416 use crate::Taffy;
417
418 #[test]
419 fn hidden_layout_should_hide_recursively() {
420 let mut taffy = Taffy::new();
421
422 let style: Style = Style { display: Display::Flex, size: Size::from_points(50.0, 50.0), ..Default::default() };
423
424 let grandchild_00 = taffy.new_leaf(style.clone()).unwrap();
425 let grandchild_01 = taffy.new_leaf(style.clone()).unwrap();
426 let child_00 = taffy.new_with_children(style.clone(), &[grandchild_00, grandchild_01]).unwrap();
427
428 let grandchild_02 = taffy.new_leaf(style.clone()).unwrap();
429 let child_01 = taffy.new_with_children(style.clone(), &[grandchild_02]).unwrap();
430
431 let root = taffy
432 .new_with_children(
433 Style { display: Display::None, size: Size::from_points(50.0, 50.0), ..Default::default() },
434 &[child_00, child_01],
435 )
436 .unwrap();
437
438 perform_hidden_layout(&mut taffy, root);
439
440 // Whatever size and display-mode the nodes had previously,
441 // all layouts should resolve to ZERO due to the root's DISPLAY::NONE
442 for (node, _) in taffy.nodes.iter().filter(|(node, _)| *node != root) {
443 if let Ok(layout) = taffy.layout(node) {
444 assert_eq!(layout.size, Size::zero());
445 assert_eq!(layout.location, Point::zero());
446 }
447 }
448 }
449}