Skip to main content

taffy/compute/
mod.rs

1//! Low-level access to the layout algorithms themselves. For a higher-level API, see the [`TaffyTree`](crate::TaffyTree) struct.
2//!
3//! ### Layout functions
4//!
5//! The layout functions all take an [`&mut impl LayoutPartialTree`](crate::LayoutPartialTree) parameter, which represents a single container node and it's direct children.
6//!
7//! | Function                          | Purpose                                                                                                                                                                                            |
8//! | ---                               | ---                                                                                                                                                                                                |
9//! | [`compute_flexbox_layout`]        | Layout a Flexbox container and it's direct children                                                                                                                                                |
10//! | [`compute_grid_layout`]           | Layout a CSS Grid container and it's direct children                                                                                                                                               |
11//! | [`compute_block_layout`]          | Layout a Block container and it's direct children                                                                                                                                                  |
12//! | [`compute_leaf_layout`]           | Applies common properties like padding/border/aspect-ratio to a node before deferring to a passed closure to determine it's size. Can be applied to nodes like text or image nodes.                |
13//! | [`compute_root_layout`]           | Layout the root node of a tree (regardless of it's layout mode). This function is typically called once to begin a layout run.                                                                     |                                                                      |
14//! | [`compute_hidden_layout`]         | Mark a node as hidden during layout (like `Display::None`)                                                                                                                                         |
15//! | [`compute_cached_layout`]         | Attempts to find a cached layout for the specified node and layout inputs. Uses the provided closure to compute the layout (and then stores the result in the cache) if no cached layout is found. |
16//!
17//! ### Other functions
18//!
19//! | Function                          | Requires                                                                                                                                                                                           | Purpose                                                              |
20//! | ---                               | ---                                                                                                                                                                                                | ---                                                                  |
21//! | [`round_layout`]                  | [`RoundTree`]                                                                                                                                                                                      | Round a tree of float-valued layouts to integer pixels               |
22//! | [`print_tree`](crate::print_tree) | [`PrintTree`](crate::PrintTree)                                                                                                                                                                    | Print a debug representation of a node tree and it's computed layout |
23//!
24pub(crate) mod common;
25pub(crate) mod leaf;
26pub(crate) mod oof;
27
28#[cfg(feature = "block_layout")]
29pub(crate) mod block;
30
31#[cfg(feature = "float_layout")]
32pub(crate) mod float;
33
34#[cfg(feature = "flexbox")]
35pub(crate) mod flexbox;
36
37#[cfg(feature = "grid")]
38pub(crate) mod grid;
39
40pub use leaf::compute_leaf_layout;
41pub use oof::{compute_oof_layout, compute_oof_layout_for_area, resolve_static_offset, OofLayoutResult};
42
43#[cfg(feature = "block_layout")]
44pub use self::block::{compute_block_align_content_offset, compute_block_layout, BlockContext, BlockFormattingContext};
45
46#[cfg(feature = "flexbox")]
47pub use self::flexbox::compute_flexbox_layout;
48
49#[cfg(feature = "grid")]
50pub use self::grid::compute_grid_layout;
51
52#[cfg(feature = "float_layout")]
53pub use self::float::{BfcSlot, ContentSlot, FloatContext, FloatIntrinsicWidthCalculator};
54
55use crate::geometry::{Line, Point, Size};
56use crate::style::{AvailableSpace, ContainingBlockClaims, CoreStyle, Overflow, Position};
57use crate::tree::{
58    AxisStaticAlign, AxisStaticEdge, AxisStaticPosition, Layout, LayoutInput, LayoutOutput, LayoutPartialTree,
59    LayoutPartialTreeExt, NodeId, OofCandidate, OofCandidates, RequestedAxis, RoundTree, RunMode, SizingMode,
60};
61use crate::util::debug::{debug_log, debug_log_node, debug_pop_node, debug_push_node};
62use crate::util::sys::{round, Vec};
63use crate::util::ResolveOrZero;
64use crate::{CacheTree, MaybeMath, MaybeResolve};
65
66/// Compute layout for the root node in the tree
67///
68/// The root's containing block is the initial containing block (ICB), which has the dimensions of the
69/// viewport (`available_space`) and is anchored at the canvas origin. The root's `position` and `inset`
70/// styles are resolved against it:
71///
72/// - A `position: absolute`/`fixed` root is laid out by the out-of-flow positioning routine used for
73///   every other out-of-flow box (insets, shrink-to-fit sizing, auto margins, ...), with its static
74///   position at the ICB origin. This requires a definite `available_space` in both axes: otherwise there
75///   is no ICB to resolve against and the root is laid out as if it were in flow.
76/// - A `position: relative` root is laid out in flow and then offset by its insets.
77pub fn compute_root_layout(
78    tree: &mut (impl crate::tree::LayoutContainingBlock + CacheTree),
79    root: NodeId,
80    available_space: Size<AvailableSpace>,
81) {
82    let style = tree.get_core_container_style(root);
83    let position = style.position();
84    let direction = style.direction();
85    drop(style);
86
87    let icb_size = available_space.into_options();
88    let oof_root_area = match (position.is_out_of_flow(), icb_size.width, icb_size.height) {
89        (true, Some(width), Some(height)) => Some(Size { width, height }),
90        _ => None,
91    };
92
93    // When the root's layout is served from the cache its layout algorithm does not run, so the
94    // hoisted children it recorded on a previous run (including those added by the root
95    // positioning pass below) are still in place and must not be re-added.
96    let mut root_is_cached = false;
97
98    let (layout, candidates) = if let Some(area_size) = oof_root_area {
99        // The static position of the root places its margin box at the origin of the ICB
100        let (start, end) = if direction.is_rtl() { (area_size.width, area_size.width) } else { (0.0, 0.0) };
101        let candidate = OofCandidate {
102            node: root,
103            order: 0,
104            position,
105            static_position: Point {
106                x: AxisStaticPosition {
107                    area: Line { start, end },
108                    align: AxisStaticAlign::from_keyword(if direction.is_rtl() {
109                        AxisStaticEdge::End
110                    } else {
111                        AxisStaticEdge::Start
112                    }),
113                },
114                y: AxisStaticPosition::from_edge(0.0, AxisStaticEdge::Start),
115            },
116        };
117        let oof::OofBoxLayout { layout, surfaced, .. } = oof::layout_oof_box(
118            tree,
119            candidate,
120            area_size,
121            Point::ZERO,
122            direction,
123            // The initial containing block is not a scroll container
124            Point { x: Overflow::Visible, y: Overflow::Visible },
125            #[cfg(feature = "grid")]
126            None,
127            |tree, inputs| root_is_cached = tree.cache_get(root, inputs).is_some(),
128        );
129        (layout, surfaced)
130    } else {
131        compute_in_flow_root_layout(tree, root, available_space, &mut root_is_cached)
132    };
133
134    // Final positioning pass for out-of-flow boxes with no nearer containing block: the initial
135    // containing block is the containing block for `position: fixed` boxes and for
136    // `position: absolute` boxes with no positioned ancestor.
137    if !candidates.is_empty() {
138        let overflow = tree.get_core_container_style(root).overflow();
139
140        // The initial containing block has the dimensions of the viewport (the available space) and is
141        // anchored at the canvas origin. In an axis where the available space is indefinite, fall back
142        // to the root's padding box.
143        let area_inset = layout.border
144            + crate::geometry::Rect {
145                left: 0.0,
146                right: layout.scrollbar_size.width,
147                top: 0.0,
148                bottom: layout.scrollbar_size.height,
149            };
150        let root_padding_box_size =
151            layout.size - Size { width: area_inset.horizontal_axis_sum(), height: area_inset.vertical_axis_sum() };
152        let (area_width, area_x) = match icb_size.width {
153            Some(width) => ((width - layout.scrollbar_size.width).max(0.0), -layout.location.x),
154            None => (root_padding_box_size.width, area_inset.left),
155        };
156        let (area_height, area_y) = match icb_size.height {
157            Some(height) => ((height - layout.scrollbar_size.height).max(0.0), -layout.location.y),
158            None => (root_padding_box_size.height, area_inset.top),
159        };
160        let area_size = Size { width: area_width, height: area_height };
161        let area_offset = Point { x: area_x, y: area_y };
162
163        let mut hoisted: Vec<NodeId> = Vec::new();
164        let mut unclaimed = OofCandidates::new();
165        oof::perform_oof_layout(
166            tree,
167            root,
168            candidates.as_slice(),
169            area_size,
170            area_offset,
171            direction,
172            // The root is the initial containing block and claims all remaining candidates
173            ContainingBlockClaims::ALL,
174            overflow,
175            &mut hoisted,
176            &mut unclaimed,
177        );
178        debug_assert!(unclaimed.is_empty(), "the root positioning pass must claim all remaining candidates");
179        if !root_is_cached {
180            tree.add_hoisted_children(root, &hoisted);
181        }
182    }
183}
184
185/// Lay out an in-flow (or `position: relative`) root node against the available space, store its layout
186/// and return it along with the out-of-flow candidates bubbled up from its subtree.
187#[inline(always)]
188fn compute_in_flow_root_layout(
189    tree: &mut (impl crate::tree::LayoutContainingBlock + CacheTree),
190    root: NodeId,
191    available_space: Size<AvailableSpace>,
192    root_is_cached: &mut bool,
193) -> (Layout, OofCandidates) {
194    let mut known_dimensions = Size::NONE;
195
196    // The available space passed to the root excludes the root's margins
197    let root_available_space = {
198        let style = tree.get_core_container_style(root);
199        let margin =
200            style.margin().resolve_or_zero(available_space.width.into_option(), |val, basis| tree.calc(val, basis));
201        available_space.maybe_sub(margin.sum_axes()).maybe_max(Size::ZERO)
202    };
203
204    #[cfg(feature = "block_layout")]
205    {
206        use crate::BoxSizing;
207
208        let parent_size = available_space.into_options();
209        let style = tree.get_core_container_style(root);
210
211        if style.is_block() {
212            // Pull these out earlier to avoid borrowing issues
213            let aspect_ratio = style.aspect_ratio();
214            let padding = style.padding().resolve_or_zero(parent_size.width, |val, basis| tree.calc(val, basis));
215            let border = style.border().resolve_or_zero(parent_size.width, |val, basis| tree.calc(val, basis));
216            let padding_border_size = (padding + border).sum_axes();
217            let box_sizing_adjustment =
218                if style.box_sizing() == BoxSizing::ContentBox { padding_border_size } else { Size::ZERO };
219
220            let min_size = style
221                .min_size()
222                .maybe_resolve(parent_size, |val, basis| tree.calc(val, basis))
223                .maybe_apply_aspect_ratio(aspect_ratio)
224                .maybe_add(box_sizing_adjustment);
225            let max_size = style
226                .max_size()
227                .maybe_resolve(parent_size, |val, basis| tree.calc(val, basis))
228                .maybe_apply_aspect_ratio(aspect_ratio)
229                .maybe_add(box_sizing_adjustment);
230            let clamped_style_size = style
231                .size()
232                .maybe_resolve(parent_size, |val, basis| tree.calc(val, basis))
233                .maybe_apply_aspect_ratio(aspect_ratio)
234                .maybe_add(box_sizing_adjustment)
235                .maybe_clamp(min_size, max_size);
236
237            // If both min and max in a given axis are set and max <= min then this determines the size in that axis
238            let min_max_definite_size = min_size.zip_map(max_size, |min, max| match (min, max) {
239                (Some(min), Some(max)) if max <= min => Some(min),
240                _ => None,
241            });
242
243            // Block nodes automatically stretch fit their width to fit available space if available space is definite
244            let available_space_based_size = Size { width: root_available_space.width.into_option(), height: None };
245
246            let styled_based_known_dimensions = known_dimensions
247                .or(min_max_definite_size)
248                .or(clamped_style_size)
249                .or(available_space_based_size)
250                .maybe_max(padding_border_size);
251
252            known_dimensions = styled_based_known_dimensions;
253        }
254    }
255
256    let inputs = LayoutInput {
257        known_dimensions,
258        known_dimensions_are_definite: Size { width: true, height: true },
259        parent_size: available_space.into_options(),
260        available_space: root_available_space,
261        sizing_mode: SizingMode::InherentSize,
262        axis: RequestedAxis::Both,
263        run_mode: RunMode::PerformLayout,
264        vertical_margins_are_collapsible: Line::FALSE,
265    };
266    *root_is_cached = tree.cache_get(root, &inputs).is_some();
267
268    // Recursively compute node layout
269    let mut output = tree.compute_child_layout(root, inputs);
270    let style = tree.get_core_container_style(root);
271    let padding =
272        style.padding().resolve_or_zero(available_space.width.into_option(), |val, basis| tree.calc(val, basis));
273    let border =
274        style.border().resolve_or_zero(available_space.width.into_option(), |val, basis| tree.calc(val, basis));
275    let margin =
276        style.margin().resolve_or_zero(available_space.width.into_option(), |val, basis| tree.calc(val, basis));
277    let scrollbar_size = Size {
278        width: if style.overflow().y == Overflow::Scroll { style.scrollbar_width() } else { 0.0 },
279        height: if style.overflow().x == Overflow::Scroll { style.scrollbar_width() } else { 0.0 },
280    };
281    let is_rtl = style.direction().is_rtl();
282
283    // The root's margin box is placed at the origin of the initial containing block
284    let mut location = Point {
285        x: match (is_rtl, available_space.width.into_option()) {
286            (true, Some(available_width)) => available_width - output.size.width - margin.right,
287            _ => margin.left,
288        },
289        y: margin.top,
290    };
291
292    // A relatively positioned root is offset by its insets (resolved against the initial containing block)
293    if style.position() == Position::Relative {
294        let icb_size = available_space.into_options();
295        let inset = style.inset();
296        let left = inset.left.maybe_resolve(icb_size.width, |val, basis| tree.calc(val, basis));
297        let right = inset.right.maybe_resolve(icb_size.width, |val, basis| tree.calc(val, basis));
298        let top = inset.top.maybe_resolve(icb_size.height, |val, basis| tree.calc(val, basis));
299        let bottom = inset.bottom.maybe_resolve(icb_size.height, |val, basis| tree.calc(val, basis));
300        location.x += if is_rtl {
301            right.map(|right| -right).or(left).unwrap_or(0.0)
302        } else {
303            left.or(right.map(|right| -right)).unwrap_or(0.0)
304        };
305        location.y += top.or(bottom.map(|bottom| -bottom)).unwrap_or(0.0);
306    }
307    drop(style);
308
309    let layout = Layout {
310        order: 0,
311        location,
312        size: output.size,
313        #[cfg(feature = "content_size")]
314        scrollable_overflow_rect: output.scrollable_overflow_rect,
315        scrollbar_size,
316        padding,
317        border,
318        // TODO: support auto margins for root node?
319        margin,
320    };
321    tree.set_unrounded_layout(root, &layout);
322
323    (layout, output.oof_candidates.take())
324}
325
326/// Attempts to find a cached layout for the specified node and layout inputs.
327///
328/// Uses the provided closure to compute the layout (and then stores the result in the cache) if no cached layout is found.
329#[inline(always)]
330pub fn compute_cached_layout<Tree: CacheTree + ?Sized, ComputeFunction>(
331    tree: &mut Tree,
332    node: NodeId,
333    inputs: LayoutInput,
334    compute_uncached: ComputeFunction,
335) -> LayoutOutput
336where
337    ComputeFunction: FnOnce(&mut Tree, NodeId, LayoutInput) -> LayoutOutput,
338{
339    debug_push_node!(node);
340
341    // First we check if we have a cached result for the given input
342    let cache_entry = tree.cache_get(node, &inputs);
343    if let Some(cached_size_and_baselines) = cache_entry {
344        debug_log_node!(inputs);
345        debug_log!("RESULT (CACHED)", dbg:cached_size_and_baselines.size);
346        debug_pop_node!();
347        return cached_size_and_baselines;
348    }
349
350    debug_log_node!(inputs);
351
352    let computed_size_and_baselines = compute_uncached(tree, node, inputs);
353
354    // Cache result
355    tree.cache_store(node, &inputs, computed_size_and_baselines.clone());
356
357    debug_log!("RESULT", dbg:computed_size_and_baselines.size);
358    debug_pop_node!();
359
360    computed_size_and_baselines
361}
362
363/// Rounds the calculated layout to exact pixel values
364///
365/// In order to ensure that no gaps in the layout are introduced we:
366///   - Always round based on the cumulative x/y coordinates (relative to the viewport) rather than
367///     parent-relative coordinates
368///   - Compute width/height by first rounding the top/bottom/left/right and then computing the difference
369///     rather than rounding the width/height directly
370///
371/// See <https://github.com/facebook/yoga/commit/aa5b296ac78f7a22e1aeaf4891243c6bb76488e2> for more context
372///
373/// In order to prevent innacuracies caused by rounding already-rounded values, we read from `unrounded_layout`
374/// and write to `final_layout`.
375pub fn round_layout(tree: &mut impl RoundTree, node_id: NodeId) {
376    return round_layout_inner(tree, node_id, 0.0, 0.0);
377
378    /// Recursive function to apply rounding to all descendents
379    fn round_layout_inner(tree: &mut impl RoundTree, node_id: NodeId, cumulative_x: f32, cumulative_y: f32) {
380        let unrounded_layout = tree.get_unrounded_layout(node_id);
381        let mut layout = unrounded_layout;
382
383        let parent_x = cumulative_x;
384        let parent_y = cumulative_y;
385        let cumulative_x = cumulative_x + unrounded_layout.location.x;
386        let cumulative_y = cumulative_y + unrounded_layout.location.y;
387
388        layout.location.x = round(cumulative_x) - round(parent_x);
389        layout.location.y = round(cumulative_y) - round(parent_y);
390        layout.size.width = round(cumulative_x + unrounded_layout.size.width) - round(cumulative_x);
391        layout.size.height = round(cumulative_y + unrounded_layout.size.height) - round(cumulative_y);
392        layout.scrollbar_size.width = round(unrounded_layout.scrollbar_size.width);
393        layout.scrollbar_size.height = round(unrounded_layout.scrollbar_size.height);
394        layout.border.left = round(cumulative_x + unrounded_layout.border.left) - round(cumulative_x);
395        layout.border.right = round(cumulative_x + unrounded_layout.size.width)
396            - round(cumulative_x + unrounded_layout.size.width - unrounded_layout.border.right);
397        layout.border.top = round(cumulative_y + unrounded_layout.border.top) - round(cumulative_y);
398        layout.border.bottom = round(cumulative_y + unrounded_layout.size.height)
399            - round(cumulative_y + unrounded_layout.size.height - unrounded_layout.border.bottom);
400        layout.padding.left = round(cumulative_x + unrounded_layout.padding.left) - round(cumulative_x);
401        layout.padding.right = round(cumulative_x + unrounded_layout.size.width)
402            - round(cumulative_x + unrounded_layout.size.width - unrounded_layout.padding.right);
403        layout.padding.top = round(cumulative_y + unrounded_layout.padding.top) - round(cumulative_y);
404        layout.padding.bottom = round(cumulative_y + unrounded_layout.size.height)
405            - round(cumulative_y + unrounded_layout.size.height - unrounded_layout.padding.bottom);
406
407        #[cfg(feature = "content_size")]
408        round_scrollable_overflow_rect(
409            &mut layout,
410            unrounded_layout.scrollable_overflow_rect,
411            cumulative_x,
412            cumulative_y,
413        );
414
415        tree.set_final_layout(node_id, &layout);
416
417        // Recurse into in-flow children. Out-of-flow (absolute/fixed) children are skipped here:
418        // they are instead visited via their containing block's hoisted child list below, which
419        // ensures each node is visited exactly once and that its cumulative offset is accumulated
420        // relative to its containing block (which its `location` is relative to).
421        let child_count = tree.child_count(node_id);
422        for index in 0..child_count {
423            let child = tree.get_child_id(node_id, index);
424            if !tree.is_out_of_flow(child) {
425                round_layout_inner(tree, child, cumulative_x, cumulative_y);
426            }
427        }
428
429        // Recurse into out-of-flow boxes for which this node is the containing block
430        let hoisted_count = tree.hoisted_child_count(node_id);
431        for index in 0..hoisted_count {
432            let child = tree.get_hoisted_child_id(node_id, index);
433            round_layout_inner(tree, child, cumulative_x, cumulative_y);
434        }
435    }
436
437    #[cfg(feature = "content_size")]
438    #[inline(always)]
439    /// Round the scrollable overflow rect.
440    /// This is split into a separate function to make it easier to feature flag.
441    fn round_scrollable_overflow_rect(
442        layout: &mut Layout,
443        unrounded_rect: crate::geometry::Rect<f32>,
444        cumulative_x: f32,
445        cumulative_y: f32,
446    ) {
447        layout.scrollable_overflow_rect.left = round(cumulative_x + unrounded_rect.left) - round(cumulative_x);
448        layout.scrollable_overflow_rect.right = round(cumulative_x + unrounded_rect.right) - round(cumulative_x);
449        layout.scrollable_overflow_rect.top = round(cumulative_y + unrounded_rect.top) - round(cumulative_y);
450        layout.scrollable_overflow_rect.bottom = round(cumulative_y + unrounded_rect.bottom) - round(cumulative_y);
451    }
452}
453
454/// Creates a layout for this node and its children, recursively.
455/// Each hidden node has zero size and is placed at the origin
456pub fn compute_hidden_layout(tree: &mut (impl LayoutPartialTree + CacheTree), node: NodeId) -> LayoutOutput {
457    // Clear cache and set zeroed-out layout for the node
458    tree.cache_clear(node);
459    tree.set_unrounded_layout(node, &Layout::with_order(0));
460
461    // Perform hidden layout on all children
462    for index in 0..tree.child_count(node) {
463        let child_id = tree.get_child_id(node, index);
464        tree.compute_child_layout(child_id, LayoutInput::HIDDEN);
465    }
466
467    LayoutOutput::HIDDEN
468}
469
470/// A module for unified re-exports of detailed layout info structs, used by low level API
471pub mod detailed_info {
472    #[cfg(feature = "grid")]
473    pub use super::grid::{
474        DetailedGridInfo, DetailedGridItemsInfo, DetailedGridTracksInfo, GridLineNames, GridLineNamesIter,
475    };
476}
477
478#[cfg(test)]
479mod tests {
480    use super::compute_hidden_layout;
481    use crate::geometry::{Point, Size};
482    use crate::style::{Display, Style};
483    use crate::TaffyTree;
484
485    #[test]
486    fn hidden_layout_should_hide_recursively() {
487        let mut taffy: TaffyTree<()> = TaffyTree::new();
488
489        let style: Style = Style { display: Display::Flex, size: Size::from_lengths(50.0, 50.0), ..Default::default() };
490
491        let grandchild_00 = taffy.new_leaf(style.clone()).unwrap();
492        let grandchild_01 = taffy.new_leaf(style.clone()).unwrap();
493        let child_00 = taffy.new_with_children(style.clone(), &[grandchild_00, grandchild_01]).unwrap();
494
495        let grandchild_02 = taffy.new_leaf(style.clone()).unwrap();
496        let child_01 = taffy.new_with_children(style.clone(), &[grandchild_02]).unwrap();
497
498        let root = taffy
499            .new_with_children(
500                Style { display: Display::None, size: Size::from_lengths(50.0, 50.0), ..Default::default() },
501                &[child_00, child_01],
502            )
503            .unwrap();
504
505        compute_hidden_layout(&mut taffy.as_layout_tree(), root);
506
507        // Whatever size and display-mode the nodes had previously,
508        // all layouts should resolve to ZERO due to the root's DISPLAY::NONE
509
510        for node in [root, child_00, child_01, grandchild_00, grandchild_01, grandchild_02] {
511            let layout = taffy.layout(node).unwrap();
512            assert_eq!(layout.size, Size::zero());
513            assert_eq!(layout.location, Point::zero());
514        }
515    }
516}