Flexbox: fix O(n^2) order lookup (#537)
1//! Computes the [flexbox](https://css-tricks.com/snippets/css/a-guide-to-flexbox/) layout algorithm on [`Taffy`](crate::Taffy) according to the [spec](https://www.w3.org/TR/css-flexbox-1/)
2use core::f32;
3
4use crate::compute::common::alignment::compute_alignment_offset;
5use crate::compute::LayoutAlgorithm;
6use crate::geometry::{Line, Point, Rect, Size};
7use crate::prelude::{TaffyMaxContent, TaffyMinContent};
8use crate::style::{
9 AlignContent, AlignItems, AlignSelf, AvailableSpace, Dimension, Display, FlexWrap, JustifyContent,
10 LengthPercentageAuto, Overflow, Position,
11};
12use crate::style::{FlexDirection, Style};
13use crate::tree::{Layout, RunMode, SizeBaselinesAndMargins, SizingMode};
14use crate::tree::{LayoutTree, NodeId};
15use crate::util::sys::Vec;
16use crate::util::sys::{f32_max, new_vec_with_capacity};
17use crate::util::MaybeMath;
18use crate::util::{MaybeResolve, ResolveOrZero};
19
20#[cfg(feature = "debug")]
21use crate::util::debug::NODE_LOGGER;
22
23/// The public interface to Taffy's Flexbox algorithm implementation
24pub struct FlexboxAlgorithm;
25impl LayoutAlgorithm for FlexboxAlgorithm {
26 const NAME: &'static str = "FLEXBOX";
27
28 fn perform_layout(
29 tree: &mut impl LayoutTree,
30 node: NodeId,
31 known_dimensions: Size<Option<f32>>,
32 parent_size: Size<Option<f32>>,
33 available_space: Size<AvailableSpace>,
34 _sizing_mode: SizingMode,
35 _vertical_margins_are_collapsible: Line<bool>,
36 ) -> SizeBaselinesAndMargins {
37 compute(tree, node, known_dimensions, parent_size, available_space, RunMode::PerformLayout)
38 }
39
40 fn measure_size(
41 tree: &mut impl LayoutTree,
42 node: NodeId,
43 known_dimensions: Size<Option<f32>>,
44 parent_size: Size<Option<f32>>,
45 available_space: Size<AvailableSpace>,
46 _sizing_mode: SizingMode,
47 _vertical_margins_are_collapsible: Line<bool>,
48 ) -> Size<f32> {
49 compute(tree, node, known_dimensions, parent_size, available_space, RunMode::ComputeSize).size
50 }
51}
52
53/// The intermediate results of a flexbox calculation for a single item
54struct FlexItem {
55 /// The identifier for the associated node
56 node: NodeId,
57
58 /// The order of the node relative to it's siblings
59 order: u32,
60
61 /// The base size of this item
62 size: Size<Option<f32>>,
63 /// The minimum allowable size of this item
64 min_size: Size<Option<f32>>,
65 /// The maximum allowable size of this item
66 max_size: Size<Option<f32>>,
67 /// The cross-alignment of this item
68 align_self: AlignSelf,
69
70 /// The overflow style of the item
71 overflow: Point<Overflow>,
72 /// The flex shrink style of the item
73 flex_shrink: f32,
74 /// The flex grow style of the item
75 flex_grow: f32,
76
77 /// The minimum size of the item. This differs from min_size above because it also
78 /// takes into account content based automatic minimum sizes
79 resolved_minimum_main_size: f32,
80
81 /// The final offset of this item
82 inset: Rect<Option<f32>>,
83 /// The margin of this item
84 margin: Rect<f32>,
85 /// Whether each margin is an auto margin or not
86 margin_is_auto: Rect<bool>,
87 /// The padding of this item
88 padding: Rect<f32>,
89 /// The border of this item
90 border: Rect<f32>,
91
92 /// The default size of this item
93 flex_basis: f32,
94 /// The default size of this item, minus padding and border
95 inner_flex_basis: f32,
96 /// The amount by which this item has deviated from its target size
97 violation: f32,
98 /// Is the size of this item locked
99 frozen: bool,
100
101 /// Either the max- or min- content flex fraction
102 /// See https://www.w3.org/TR/css-flexbox-1/#intrinsic-main-sizes
103 content_flex_fraction: f32,
104
105 /// The proposed inner size of this item
106 hypothetical_inner_size: Size<f32>,
107 /// The proposed outer size of this item
108 hypothetical_outer_size: Size<f32>,
109 /// The size that this item wants to be
110 target_size: Size<f32>,
111 /// The size that this item wants to be, plus any padding and border
112 outer_target_size: Size<f32>,
113
114 /// The position of the bottom edge of this item
115 baseline: f32,
116
117 /// A temporary value for the main offset
118 ///
119 /// Offset is the relative position from the item's natural flow position based on
120 /// relative position values, alignment, and justification. Does not include margin/padding/border.
121 offset_main: f32,
122 /// A temporary value for the cross offset
123 ///
124 /// Offset is the relative position from the item's natural flow position based on
125 /// relative position values, alignment, and justification. Does not include margin/padding/border.
126 offset_cross: f32,
127}
128
129/// A line of [`FlexItem`] used for intermediate computation
130struct FlexLine<'a> {
131 /// The slice of items to iterate over during computation of this line
132 items: &'a mut [FlexItem],
133 /// The dimensions of the cross-axis
134 cross_size: f32,
135 /// The relative offset of the cross-axis
136 offset_cross: f32,
137}
138
139/// Values that can be cached during the flexbox algorithm
140struct AlgoConstants {
141 /// The direction of the current segment being laid out
142 dir: FlexDirection,
143 /// Is this segment a row
144 is_row: bool,
145 /// Is this segment a column
146 is_column: bool,
147 /// Is wrapping enabled (in either direction)
148 is_wrap: bool,
149 /// Is the wrap direction inverted
150 is_wrap_reverse: bool,
151
152 /// The item's min_size style
153 min_size: Size<Option<f32>>,
154 /// The item's max_size style
155 max_size: Size<Option<f32>>,
156 /// The margin of this section
157 margin: Rect<f32>,
158 /// The border of this section
159 border: Rect<f32>,
160 /// The space between the content box and the border box.
161 /// This consists of padding + border + scrollbar_gutter.
162 content_box_inset: Rect<f32>,
163 /// The size reserved for scrollbar gutters in each axis
164 scrollbar_gutter: Point<f32>,
165 /// The gap of this section
166 gap: Size<f32>,
167 /// The align_items property of this node
168 align_items: AlignItems,
169 /// The align_content property of this node
170 align_content: AlignContent,
171 /// The justify_content property of this node
172 justify_content: Option<JustifyContent>,
173
174 /// The border-box size of the node being laid out (if known)
175 node_outer_size: Size<Option<f32>>,
176 /// The content-box size of the node being laid out (if known)
177 node_inner_size: Size<Option<f32>>,
178
179 /// The size of the virtual container containing the flex items.
180 container_size: Size<f32>,
181 /// The size of the internal container
182 inner_container_size: Size<f32>,
183}
184
185/// Computes the layout of [`LayoutTree`] according to the flexbox algorithm
186pub fn compute(
187 tree: &mut impl LayoutTree,
188 node: NodeId,
189 known_dimensions: Size<Option<f32>>,
190 parent_size: Size<Option<f32>>,
191 available_space: Size<AvailableSpace>,
192 run_mode: RunMode,
193) -> SizeBaselinesAndMargins {
194 let style = tree.style(node);
195
196 // Pull these out earlier to avoid borrowing issues
197 let aspect_ratio = style.aspect_ratio;
198 let min_size = style.min_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
199 let max_size = style.max_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
200 let clamped_style_size =
201 style.size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio).maybe_clamp(min_size, max_size);
202
203 // If both min and max in a given axis are set and max <= min then this determines the size in that axis
204 let min_max_definite_size = min_size.zip_map(max_size, |min, max| match (min, max) {
205 (Some(min), Some(max)) if max <= min => Some(min),
206 _ => None,
207 });
208 let styled_based_known_dimensions = known_dimensions.or(min_max_definite_size).or(clamped_style_size);
209
210 // Short-circuit layout if the container's size is fully determined by the container's size and the run mode
211 // is ComputeSize (and thus the container's size is all that we're interested in)
212 if run_mode == RunMode::ComputeSize {
213 if let Size { width: Some(width), height: Some(height) } = styled_based_known_dimensions {
214 return Size { width, height }.into();
215 }
216 }
217
218 #[cfg(feature = "debug")]
219 NODE_LOGGER.log("FLEX: single-pass");
220 compute_preliminary(tree, node, styled_based_known_dimensions, parent_size, available_space, run_mode)
221}
222
223/// Compute a preliminary size for an item
224fn compute_preliminary(
225 tree: &mut impl LayoutTree,
226 node: NodeId,
227 known_dimensions: Size<Option<f32>>,
228 parent_size: Size<Option<f32>>,
229 available_space: Size<AvailableSpace>,
230 run_mode: RunMode,
231) -> SizeBaselinesAndMargins {
232 // Define some general constants we will need for the remainder of the algorithm.
233 let mut constants = compute_constants(tree.style(node), known_dimensions, parent_size);
234
235 // 9. Flex Layout Algorithm
236
237 // 9.1. Initial Setup
238
239 // 1. Generate anonymous flex items as described in §4 Flex Items.
240 #[cfg(feature = "debug")]
241 NODE_LOGGER.log("generate_anonymous_flex_items");
242 let mut flex_items = generate_anonymous_flex_items(tree, node, &constants);
243
244 // 9.2. Line Length Determination
245
246 // 2. Determine the available main and cross space for the flex items
247 #[cfg(feature = "debug")]
248 NODE_LOGGER.log("determine_available_space");
249 let available_space = determine_available_space(known_dimensions, available_space, &constants);
250
251 // 3. Determine the flex base size and hypothetical main size of each item.
252 #[cfg(feature = "debug")]
253 NODE_LOGGER.log("determine_flex_base_size");
254 determine_flex_base_size(tree, &constants, available_space, &mut flex_items);
255
256 #[cfg(feature = "debug")]
257 for item in flex_items.iter() {
258 NODE_LOGGER.labelled_log("item.flex_basis", item.flex_basis);
259 NODE_LOGGER.labelled_log("item.inner_flex_basis", item.inner_flex_basis);
260 NODE_LOGGER.labelled_debug_log("item.hypothetical_outer_size", item.hypothetical_outer_size);
261 NODE_LOGGER.labelled_debug_log("item.hypothetical_inner_size", item.hypothetical_inner_size);
262 NODE_LOGGER.labelled_debug_log("item.resolved_minimum_main_size", item.resolved_minimum_main_size);
263 }
264
265 // 4. Determine the main size of the flex container
266 // This has already been done as part of compute_constants. The inner size is exposed as constants.node_inner_size.
267
268 // 9.3. Main Size Determination
269
270 // 5. Collect flex items into flex lines.
271 #[cfg(feature = "debug")]
272 NODE_LOGGER.log("collect_flex_lines");
273 let mut flex_lines = collect_flex_lines(&constants, available_space, &mut flex_items);
274
275 // If container size is undefined, determine the container's main size
276 // and then re-resolve gaps based on newly determined size
277 #[cfg(feature = "debug")]
278 NODE_LOGGER.log("determine_container_main_size");
279 let original_gap = constants.gap;
280 if let Some(inner_main_size) = constants.node_inner_size.main(constants.dir) {
281 let outer_main_size = inner_main_size + constants.content_box_inset.main_axis_sum(constants.dir);
282 constants.inner_container_size.set_main(constants.dir, inner_main_size);
283 constants.container_size.set_main(constants.dir, outer_main_size);
284 } else {
285 // Sets constants.container_size and constants.outer_container_size
286 determine_container_main_size(tree, available_space, &mut flex_lines, &mut constants);
287 constants.node_inner_size.set_main(constants.dir, Some(constants.inner_container_size.main(constants.dir)));
288 constants.node_outer_size.set_main(constants.dir, Some(constants.container_size.main(constants.dir)));
289
290 #[cfg(feature = "debug")]
291 NODE_LOGGER.labelled_debug_log("constants.node_outer_size", constants.node_outer_size);
292 #[cfg(feature = "debug")]
293 NODE_LOGGER.labelled_debug_log("constants.node_inner_size", constants.node_inner_size);
294
295 // Re-resolve percentage gaps
296 let style = tree.style(node);
297 let inner_container_size = constants.inner_container_size.main(constants.dir);
298 let new_gap = style.gap.main(constants.dir).maybe_resolve(inner_container_size).unwrap_or(0.0);
299 constants.gap.set_main(constants.dir, new_gap);
300 }
301
302 // 6. Resolve the flexible lengths of all the flex items to find their used main size.
303 #[cfg(feature = "debug")]
304 NODE_LOGGER.log("resolve_flexible_lengths");
305 for line in &mut flex_lines {
306 resolve_flexible_lengths(line, &constants, original_gap);
307 }
308
309 // 9.4. Cross Size Determination
310
311 // 7. Determine the hypothetical cross size of each item.
312 #[cfg(feature = "debug")]
313 NODE_LOGGER.log("determine_hypothetical_cross_size");
314 for line in &mut flex_lines {
315 determine_hypothetical_cross_size(tree, line, &constants, available_space);
316 }
317
318 // Calculate child baselines. This function is internally smart and only computes child baselines
319 // if they are necessary.
320 #[cfg(feature = "debug")]
321 NODE_LOGGER.log("calculate_children_base_lines");
322 calculate_children_base_lines(tree, known_dimensions, available_space, &mut flex_lines, &constants);
323
324 // 8. Calculate the cross size of each flex line.
325 #[cfg(feature = "debug")]
326 NODE_LOGGER.log("calculate_cross_size");
327 calculate_cross_size(&mut flex_lines, known_dimensions, &constants);
328
329 // 9. Handle 'align-content: stretch'.
330 #[cfg(feature = "debug")]
331 NODE_LOGGER.log("handle_align_content_stretch");
332 handle_align_content_stretch(&mut flex_lines, known_dimensions, &constants);
333
334 // 10. Collapse visibility:collapse items. If any flex items have visibility: collapse,
335 // note the cross size of the line they’re in as the item’s strut size, and restart
336 // layout from the beginning.
337 //
338 // In this second layout round, when collecting items into lines, treat the collapsed
339 // items as having zero main size. For the rest of the algorithm following that step,
340 // ignore the collapsed items entirely (as if they were display:none) except that after
341 // calculating the cross size of the lines, if any line’s cross size is less than the
342 // largest strut size among all the collapsed items in the line, set its cross size to
343 // that strut size.
344 //
345 // Skip this step in the second layout round.
346
347 // TODO implement once (if ever) we support visibility:collapse
348
349 // 11. Determine the used cross size of each flex item.
350 #[cfg(feature = "debug")]
351 NODE_LOGGER.log("determine_used_cross_size");
352 determine_used_cross_size(tree, &mut flex_lines, &constants);
353
354 // 9.5. Main-Axis Alignment
355
356 // 12. Distribute any remaining free space.
357 #[cfg(feature = "debug")]
358 NODE_LOGGER.log("distribute_remaining_free_space");
359 distribute_remaining_free_space(&mut flex_lines, &constants);
360
361 // 9.6. Cross-Axis Alignment
362
363 // 13. Resolve cross-axis auto margins (also includes 14).
364 #[cfg(feature = "debug")]
365 NODE_LOGGER.log("resolve_cross_axis_auto_margins");
366 resolve_cross_axis_auto_margins(&mut flex_lines, &constants);
367
368 // 15. Determine the flex container’s used cross size.
369 #[cfg(feature = "debug")]
370 NODE_LOGGER.log("determine_container_cross_size");
371 let total_line_cross_size = determine_container_cross_size(&flex_lines, known_dimensions, &mut constants);
372
373 // We have the container size.
374 // If our caller does not care about performing layout we are done now.
375 if run_mode == RunMode::ComputeSize {
376 return constants.container_size.into();
377 }
378
379 // 16. Align all flex lines per align-content.
380 #[cfg(feature = "debug")]
381 NODE_LOGGER.log("align_flex_lines_per_align_content");
382 align_flex_lines_per_align_content(&mut flex_lines, &constants, total_line_cross_size);
383
384 // Do a final layout pass and gather the resulting layouts
385 #[cfg(feature = "debug")]
386 NODE_LOGGER.log("final_layout_pass");
387 final_layout_pass(tree, &mut flex_lines, &constants);
388
389 // Before returning we perform absolute layout on all absolutely positioned children
390 #[cfg(feature = "debug")]
391 NODE_LOGGER.log("perform_absolute_layout_on_absolute_children");
392 perform_absolute_layout_on_absolute_children(tree, node, &constants);
393
394 #[cfg(feature = "debug")]
395 NODE_LOGGER.log("hidden_layout");
396 let len = tree.child_count(node);
397 for order in 0..len {
398 let child = tree.child(node, order);
399 if tree.style(child).display == Display::None {
400 *tree.layout_mut(child) = Layout::with_order(order as u32);
401 tree.perform_child_layout(
402 child,
403 Size::NONE,
404 Size::NONE,
405 Size::MAX_CONTENT,
406 SizingMode::InherentSize,
407 Line::FALSE,
408 );
409 }
410 }
411
412 // 8.5. Flex Container Baselines: calculate the flex container's first baseline
413 // See https://www.w3.org/TR/css-flexbox-1/#flex-baselines
414 let first_vertical_baseline = if flex_lines.is_empty() {
415 None
416 } else {
417 flex_lines[0]
418 .items
419 .iter()
420 .find(|item| constants.is_column || item.align_self == AlignSelf::Baseline)
421 .or_else(|| flex_lines[0].items.iter().next())
422 .map(|child| {
423 let offset_vertical = if constants.is_row { child.offset_cross } else { child.offset_main };
424 offset_vertical + child.baseline
425 })
426 };
427
428 SizeBaselinesAndMargins::from_size_and_baselines(
429 constants.container_size,
430 Point { x: None, y: first_vertical_baseline },
431 )
432}
433
434/// Compute constants that can be reused during the flexbox algorithm.
435#[inline]
436fn compute_constants(
437 style: &Style,
438 known_dimensions: Size<Option<f32>>,
439 parent_size: Size<Option<f32>>,
440) -> AlgoConstants {
441 let dir = style.flex_direction;
442 let is_row = dir.is_row();
443 let is_column = dir.is_column();
444 let is_wrap = matches!(style.flex_wrap, FlexWrap::Wrap | FlexWrap::WrapReverse);
445 let is_wrap_reverse = style.flex_wrap == FlexWrap::WrapReverse;
446
447 let aspect_ratio = style.aspect_ratio;
448 let margin = style.margin.resolve_or_zero(parent_size.width);
449 let padding = style.padding.resolve_or_zero(parent_size.width);
450 let border = style.border.resolve_or_zero(parent_size.width);
451 let align_items = style.align_items.unwrap_or(AlignItems::Stretch);
452 let align_content = style.align_content.unwrap_or(AlignContent::Stretch);
453 let justify_content = style.justify_content;
454
455 // Scrollbar gutters are reserved when the `overflow` property is set to `Overflow::Scroll`.
456 // However, the axis are switched (transposed) because a node that scrolls vertically needs
457 // *horizontal* space to be reserved for a scrollbar
458 let scrollbar_gutter = style.overflow.transpose().map(|overflow| match overflow {
459 Overflow::Scroll => style.scrollbar_width,
460 _ => 0.0,
461 });
462 // TODO: make side configurable based on the `direction` property
463 let mut content_box_inset = padding + border;
464 content_box_inset.right += scrollbar_gutter.x;
465 content_box_inset.bottom += scrollbar_gutter.y;
466
467 let node_outer_size = known_dimensions;
468 let node_inner_size = node_outer_size.maybe_sub(content_box_inset.sum_axes());
469 let gap = style.gap.resolve_or_zero(node_inner_size.or(Size::zero()));
470
471 let container_size = Size::zero();
472 let inner_container_size = Size::zero();
473
474 AlgoConstants {
475 dir,
476 is_row,
477 is_column,
478 is_wrap,
479 is_wrap_reverse,
480 min_size: style.min_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio),
481 max_size: style.max_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio),
482 margin,
483 border,
484 gap,
485 content_box_inset,
486 scrollbar_gutter,
487 align_items,
488 align_content,
489 justify_content,
490 node_outer_size,
491 node_inner_size,
492 container_size,
493 inner_container_size,
494 }
495}
496
497/// Generate anonymous flex items.
498///
499/// # [9.1. Initial Setup](https://www.w3.org/TR/css-flexbox-1/#box-manip)
500///
501/// - [**Generate anonymous flex items**](https://www.w3.org/TR/css-flexbox-1/#algo-anon-box) as described in [§4 Flex Items](https://www.w3.org/TR/css-flexbox-1/#flex-items).
502#[inline]
503fn generate_anonymous_flex_items(tree: &impl LayoutTree, node: NodeId, constants: &AlgoConstants) -> Vec<FlexItem> {
504 tree.children(node)
505 .enumerate()
506 .map(|(index, child)| (index, child, tree.style(child)))
507 .filter(|(_, _, style)| style.position != Position::Absolute)
508 .filter(|(_, _, style)| style.display != Display::None)
509 .map(|(index, child, child_style)| {
510 let aspect_ratio = child_style.aspect_ratio;
511 FlexItem {
512 node: child,
513 order: index as u32,
514 size: child_style.size.maybe_resolve(constants.node_inner_size).maybe_apply_aspect_ratio(aspect_ratio),
515 min_size: child_style
516 .min_size
517 .maybe_resolve(constants.node_inner_size)
518 .maybe_apply_aspect_ratio(aspect_ratio),
519 max_size: child_style
520 .max_size
521 .maybe_resolve(constants.node_inner_size)
522 .maybe_apply_aspect_ratio(aspect_ratio),
523
524 inset: child_style.inset.zip_size(constants.node_inner_size, |p, s| p.maybe_resolve(s)),
525 margin: child_style.margin.resolve_or_zero(constants.node_inner_size.width),
526 margin_is_auto: child_style.margin.map(|m| m == LengthPercentageAuto::Auto),
527 padding: child_style.padding.resolve_or_zero(constants.node_inner_size.width),
528 border: child_style.border.resolve_or_zero(constants.node_inner_size.width),
529 align_self: child_style.align_self.unwrap_or(constants.align_items),
530 overflow: child_style.overflow,
531 flex_grow: child_style.flex_grow,
532 flex_shrink: child_style.flex_shrink,
533 flex_basis: 0.0,
534 inner_flex_basis: 0.0,
535 violation: 0.0,
536 frozen: false,
537
538 resolved_minimum_main_size: 0.0,
539 hypothetical_inner_size: Size::zero(),
540 hypothetical_outer_size: Size::zero(),
541 target_size: Size::zero(),
542 outer_target_size: Size::zero(),
543 content_flex_fraction: 0.0,
544
545 baseline: 0.0,
546
547 offset_main: 0.0,
548 offset_cross: 0.0,
549 }
550 })
551 .collect()
552}
553
554/// Determine the available main and cross space for the flex items.
555///
556/// # [9.2. Line Length Determination](https://www.w3.org/TR/css-flexbox-1/#line-sizing)
557///
558/// - [**Determine the available main and cross space for the flex items**](https://www.w3.org/TR/css-flexbox-1/#algo-available).
559/// For each dimension, if that dimension of the flex container’s content box is a definite size, use that;
560/// if that dimension of the flex container is being sized under a min or max-content constraint, the available space in that dimension is that constraint;
561/// otherwise, subtract the flex container’s margin, border, and padding from the space available to the flex container in that dimension and use that value.
562/// **This might result in an infinite value**.
563#[inline]
564#[must_use]
565fn determine_available_space(
566 known_dimensions: Size<Option<f32>>,
567 outer_available_space: Size<AvailableSpace>,
568 constants: &AlgoConstants,
569) -> Size<AvailableSpace> {
570 // Note: min/max/preferred size styles have already been applied to known_dimensions in the `compute` function above
571 let width = match known_dimensions.width {
572 Some(node_width) => AvailableSpace::Definite(node_width - constants.content_box_inset.horizontal_axis_sum()),
573 None => outer_available_space
574 .width
575 .maybe_sub(constants.margin.horizontal_axis_sum())
576 .maybe_sub(constants.content_box_inset.horizontal_axis_sum()),
577 };
578
579 let height = match known_dimensions.height {
580 Some(node_height) => AvailableSpace::Definite(node_height - constants.content_box_inset.vertical_axis_sum()),
581 None => outer_available_space
582 .height
583 .maybe_sub(constants.margin.vertical_axis_sum())
584 .maybe_sub(constants.content_box_inset.vertical_axis_sum()),
585 };
586
587 Size { width, height }
588}
589
590/// Determine the flex base size and hypothetical main size of each item.
591///
592/// # [9.2. Line Length Determination](https://www.w3.org/TR/css-flexbox-1/#line-sizing)
593///
594/// - [**Determine the flex base size and hypothetical main size of each item:**](https://www.w3.org/TR/css-flexbox-1/#algo-main-item)
595///
596/// - A. If the item has a definite used flex basis, that’s the flex base size.
597///
598/// - B. If the flex item has ...
599///
600/// - an intrinsic aspect ratio,
601/// - a used flex basis of content, and
602/// - a definite cross size,
603///
604/// then the flex base size is calculated from its inner cross size and the flex item’s intrinsic aspect ratio.
605///
606/// - C. If the used flex basis is content or depends on its available space, and the flex container is being sized under a min-content
607/// or max-content constraint (e.g. when performing automatic table layout \[CSS21\]), size the item under that constraint.
608/// The flex base size is the item’s resulting main size.
609///
610/// - E. Otherwise, size the item into the available space using its used flex basis in place of its main size, treating a value of content as max-content.
611/// If a cross size is needed to determine the main size (e.g. when the flex item’s main size is in its block axis) and the flex item’s cross size is auto and not definite,
612/// in this calculation use fit-content as the flex item’s cross size. The flex base size is the item’s resulting main size.
613///
614/// When determining the flex base size, the item’s min and max main sizes are ignored (no clamping occurs).
615/// Furthermore, the sizing calculations that floor the content box size at zero when applying box-sizing are also ignored.
616/// (For example, an item with a specified size of zero, positive padding, and box-sizing: border-box will have an outer flex base size of zero—and hence a negative inner flex base size.)
617#[inline]
618fn determine_flex_base_size(
619 tree: &mut impl LayoutTree,
620 constants: &AlgoConstants,
621 available_space: Size<AvailableSpace>,
622 flex_items: &mut [FlexItem],
623) {
624 let dir = constants.dir;
625
626 for child in flex_items.iter_mut() {
627 let child_style = tree.style(child.node);
628
629 // Parent size for child sizing
630 let cross_axis_parent_size = constants.node_inner_size.cross(dir);
631
632 // Available space for child sizing
633 let cross_axis_margin_sum = constants.margin.cross_axis_sum(dir);
634 let child_min_cross = child.min_size.cross(dir).maybe_add(cross_axis_margin_sum);
635 let child_max_cross = child.max_size.cross(dir).maybe_add(cross_axis_margin_sum);
636 let cross_axis_available_space: AvailableSpace = available_space
637 .cross(dir)
638 .map_definite_value(|val| cross_axis_parent_size.unwrap_or(val))
639 .maybe_clamp(child_min_cross, child_max_cross);
640
641 child.flex_basis = 'flex_basis: {
642 // A. If the item has a definite used flex basis, that’s the flex base size.
643
644 // B. If the flex item has an intrinsic aspect ratio,
645 // a used flex basis of content, and a definite cross size,
646 // then the flex base size is calculated from its inner
647 // cross size and the flex item’s intrinsic aspect ratio.
648
649 // Note: `child.size` has already been resolved against aspect_ratio in generate_anonymous_flex_items
650 // So B will just work here by using main_size without special handling for aspect_ratio
651
652 let flex_basis = child_style.flex_basis.maybe_resolve(constants.node_inner_size.main(dir));
653 let main_size = child.size.main(dir);
654 if let Some(flex_basis) = flex_basis.or(main_size) {
655 break 'flex_basis flex_basis;
656 };
657
658 // C. If the used flex basis is content or depends on its available space,
659 // and the flex container is being sized under a min-content or max-content
660 // constraint (e.g. when performing automatic table layout [CSS21]),
661 // size the item under that constraint. The flex base size is the item’s
662 // resulting main size.
663
664 // This is covered by the implementation of E below, which passes the available_space constraint
665 // through to the child size computation. It may need a separate implementation if/when D is implemented.
666
667 // D. Otherwise, if the used flex basis is content or depends on its
668 // available space, the available main size is infinite, and the flex item’s
669 // inline axis is parallel to the main axis, lay the item out using the rules
670 // for a box in an orthogonal flow [CSS3-WRITING-MODES]. The flex base size
671 // is the item’s max-content main size.
672
673 // TODO if/when vertical writing modes are supported
674
675 // E. Otherwise, size the item into the available space using its used flex basis
676 // in place of its main size, treating a value of content as max-content.
677 // If a cross size is needed to determine the main size (e.g. when the
678 // flex item’s main size is in its block axis) and the flex item’s cross size
679 // is auto and not definite, in this calculation use fit-content as the
680 // flex item’s cross size. The flex base size is the item’s resulting main size.
681
682 let child_parent_size = Size::NONE.with_cross(dir, cross_axis_parent_size);
683 let child_available_space = Size::MAX_CONTENT
684 .with_main(
685 dir,
686 // Map AvailableSpace::Definite to AvailableSpace::MaxContent
687 if available_space.main(dir) == AvailableSpace::MinContent {
688 AvailableSpace::MinContent
689 } else {
690 AvailableSpace::MaxContent
691 },
692 )
693 .with_cross(dir, cross_axis_available_space);
694
695 let child_known_dimensions = {
696 let mut ckd = child.size;
697 if child.align_self == AlignSelf::Stretch && ckd.cross(dir).is_none() {
698 ckd.set_cross(
699 dir,
700 child_available_space
701 .cross(dir)
702 .into_option()
703 .maybe_clamp(child_min_cross, child_max_cross)
704 .maybe_sub(child.margin.cross_axis_sum(dir)),
705 );
706 }
707 ckd
708 };
709
710 break 'flex_basis tree
711 .measure_child_size(
712 child.node,
713 child_known_dimensions,
714 child_parent_size,
715 child_available_space,
716 SizingMode::ContentSize,
717 Line::FALSE,
718 )
719 .main(dir);
720 };
721
722 // Floor flex-basis by the padding_border_sum (floors inner_flex_basis at zero)
723 // This seems to be in violation of the spec which explicitly states that the content box should not be floored at zero
724 // (like it usually is) when calculating the flex-basis. But including this matches both Chrome and Firefox's behaviour.
725 //
726 // TODO: resolve spec violation
727 // Spec: https://www.w3.org/TR/css-flexbox-1/#intrinsic-item-contributions
728 // Spec: https://www.w3.org/TR/css-flexbox-1/#change-2016-max-contribution
729 let padding_border_sum = child.padding.main_axis_sum(constants.dir) + child.border.main_axis_sum(constants.dir);
730 child.flex_basis = child.flex_basis.max(padding_border_sum);
731
732 // The hypothetical main size is the item’s flex base size clamped according to its
733 // used min and max main sizes (and flooring the content box size at zero).
734
735 child.inner_flex_basis =
736 child.flex_basis - child.padding.main_axis_sum(constants.dir) - child.border.main_axis_sum(constants.dir);
737
738 let padding_border_axes_sums = (child.padding + child.border).sum_axes().map(Some);
739 let hypothetical_inner_min_main =
740 child.min_size.main(constants.dir).maybe_max(padding_border_axes_sums.main(constants.dir));
741 let hypothetical_inner_size =
742 child.flex_basis.maybe_clamp(hypothetical_inner_min_main, child.max_size.main(constants.dir));
743 let hypothetical_outer_size = hypothetical_inner_size + child.margin.main_axis_sum(constants.dir);
744
745 child.hypothetical_inner_size.set_main(constants.dir, hypothetical_inner_size);
746 child.hypothetical_outer_size.set_main(constants.dir, hypothetical_outer_size);
747
748 // Note that it is important that the `parent_size` parameter in the main axis is not set for this
749 // function call as it used for resolving percentages, and percentage size in an axis should not contribute
750 // to a min-content contribution in that same axis. However the `parent_size` and `available_space` *should*
751 // be set to their usual values in the cross axis so that wrapping content can wrap correctly.
752 //
753 // See https://drafts.csswg.org/css-sizing-3/#min-percentage-contribution
754 let style_min_main_size =
755 child.min_size.or(child.overflow.map(Overflow::maybe_into_automatic_min_size).into()).main(dir);
756
757 child.resolved_minimum_main_size = style_min_main_size.unwrap_or({
758 let min_content_size = {
759 let child_parent_size = Size::NONE.with_cross(dir, cross_axis_parent_size);
760 let child_available_space = Size::MIN_CONTENT.with_cross(dir, cross_axis_available_space);
761
762 tree.measure_child_size(
763 child.node,
764 Size::NONE,
765 child_parent_size,
766 child_available_space,
767 SizingMode::ContentSize,
768 Line::FALSE,
769 )
770 };
771
772 // 4.5. Automatic Minimum Size of Flex Items
773 // https://www.w3.org/TR/css-flexbox-1/#min-size-auto
774 let clamped_min_content_size = min_content_size.maybe_min(child.size).maybe_min(child.max_size);
775 clamped_min_content_size.maybe_max(padding_border_axes_sums).main(dir)
776 });
777 }
778}
779
780/// Collect flex items into flex lines.
781///
782/// # [9.3. Main Size Determination](https://www.w3.org/TR/css-flexbox-1/#main-sizing)
783///
784/// - [**Collect flex items into flex lines**](https://www.w3.org/TR/css-flexbox-1/#algo-line-break):
785///
786/// - If the flex container is single-line, collect all the flex items into a single flex line.
787///
788/// - Otherwise, starting from the first uncollected item, collect consecutive items one by one until the first time that the next collected item would not fit into the flex container’s inner main size
789/// (or until a forced break is encountered, see [§10 Fragmenting Flex Layout](https://www.w3.org/TR/css-flexbox-1/#pagination)).
790/// If the very first uncollected item wouldn't fit, collect just it into the line.
791///
792/// For this step, the size of a flex item is its outer hypothetical main size. (**Note: This can be negative**.)
793///
794/// Repeat until all flex items have been collected into flex lines.
795///
796/// **Note that the "collect as many" line will collect zero-sized flex items onto the end of the previous line even if the last non-zero item exactly "filled up" the line**.
797#[inline]
798fn collect_flex_lines<'a>(
799 constants: &AlgoConstants,
800 available_space: Size<AvailableSpace>,
801 flex_items: &'a mut Vec<FlexItem>,
802) -> Vec<FlexLine<'a>> {
803 if !constants.is_wrap {
804 let mut lines = new_vec_with_capacity(1);
805 lines.push(FlexLine { items: flex_items.as_mut_slice(), cross_size: 0.0, offset_cross: 0.0 });
806 lines
807 } else {
808 match available_space.main(constants.dir) {
809 // If we're sizing under a max-content constraint then the flex items will never wrap
810 // (at least for now - future extensions to the CSS spec may add provisions for forced wrap points)
811 AvailableSpace::MaxContent => {
812 let mut lines = new_vec_with_capacity(1);
813 lines.push(FlexLine { items: flex_items.as_mut_slice(), cross_size: 0.0, offset_cross: 0.0 });
814 lines
815 }
816 // If flex-wrap is Wrap and we're sizing under a min-content constraint, then we take every possible wrapping opportunity
817 // and place each item in it's own line
818 AvailableSpace::MinContent => {
819 let mut lines = new_vec_with_capacity(flex_items.len());
820 let mut items = &mut flex_items[..];
821 while !items.is_empty() {
822 let (line_items, rest) = items.split_at_mut(1);
823 lines.push(FlexLine { items: line_items, cross_size: 0.0, offset_cross: 0.0 });
824 items = rest;
825 }
826 lines
827 }
828 AvailableSpace::Definite(main_axis_available_space) => {
829 let mut lines = new_vec_with_capacity(1);
830 let mut flex_items = &mut flex_items[..];
831 let main_axis_gap = constants.gap.main(constants.dir);
832
833 while !flex_items.is_empty() {
834 // Find index of the first item in the next line
835 // (or the last item if all remaining items are in the current line)
836 let mut line_length = 0.0;
837 let index = flex_items
838 .iter()
839 .enumerate()
840 .find(|&(idx, child)| {
841 // Gaps only occur between items (not before the first one or after the last one)
842 // So first item in the line does not contribute a gap to the line length
843 let gap_contribution = if idx == 0 { 0.0 } else { main_axis_gap };
844 line_length += child.hypothetical_outer_size.main(constants.dir) + gap_contribution;
845 line_length > main_axis_available_space && idx != 0
846 })
847 .map(|(idx, _)| idx)
848 .unwrap_or(flex_items.len());
849
850 let (items, rest) = flex_items.split_at_mut(index);
851 lines.push(FlexLine { items, cross_size: 0.0, offset_cross: 0.0 });
852 flex_items = rest;
853 }
854 lines
855 }
856 }
857 }
858}
859
860/// Determine the container's main size (if not already known)
861fn determine_container_main_size(
862 tree: &mut impl LayoutTree,
863 available_space: Size<AvailableSpace>,
864 lines: &mut Vec<FlexLine<'_>>,
865 constants: &mut AlgoConstants,
866) {
867 let dir = constants.dir;
868 let main_content_box_inset = constants.content_box_inset.main_axis_sum(constants.dir);
869
870 let outer_main_size: f32 = constants.node_outer_size.main(constants.dir).unwrap_or_else(|| {
871 match available_space.main(dir) {
872 AvailableSpace::Definite(main_axis_available_space) => {
873 let longest_line_length: f32 = lines
874 .iter()
875 .map(|line| {
876 let line_main_axis_gap = sum_axis_gaps(constants.gap.main(constants.dir), line.items.len());
877 let total_target_size = line
878 .items
879 .iter()
880 .map(|child| {
881 let padding_border_sum = (child.padding + child.border).main_axis_sum(constants.dir);
882 (child.flex_basis + child.margin.main_axis_sum(constants.dir)).max(padding_border_sum)
883 })
884 .sum::<f32>();
885 total_target_size + line_main_axis_gap
886 })
887 .max_by(|a, b| a.total_cmp(b))
888 .unwrap_or(0.0);
889 let size = longest_line_length + main_content_box_inset;
890 if lines.len() > 1 {
891 f32_max(size, main_axis_available_space)
892 } else {
893 size
894 }
895 }
896 AvailableSpace::MinContent if constants.is_wrap => {
897 let longest_line_length: f32 = lines
898 .iter()
899 .map(|line| {
900 let line_main_axis_gap = sum_axis_gaps(constants.gap.main(constants.dir), line.items.len());
901 let total_target_size = line
902 .items
903 .iter()
904 .map(|child| {
905 let padding_border_sum = (child.padding + child.border).main_axis_sum(constants.dir);
906 (child.flex_basis + child.margin.main_axis_sum(constants.dir)).max(padding_border_sum)
907 })
908 .sum::<f32>();
909 total_target_size + line_main_axis_gap
910 })
911 .max_by(|a, b| a.total_cmp(b))
912 .unwrap_or(0.0);
913 longest_line_length + main_content_box_inset
914 }
915 AvailableSpace::MinContent | AvailableSpace::MaxContent => {
916 // Define a base main_size variable. This is mutated once for iteration over the outer
917 // loop over the flex lines as:
918 // "The flex container’s max-content size is the largest sum of the afore-calculated sizes of all items within a single line."
919 let mut main_size = 0.0;
920
921 for line in lines.iter_mut() {
922 for item in line.items.iter_mut() {
923 let style_min = item.min_size.main(constants.dir);
924 let style_preferred = item.size.main(constants.dir);
925 let style_max = item.max_size.main(constants.dir);
926
927 // The spec seems a bit unclear on this point (my initial reading was that the `.maybe_max(style_preferred)` should
928 // not be included here), however this matches both Chrome and Firefox as of 9th March 2023.
929 //
930 // Spec: https://www.w3.org/TR/css-flexbox-1/#intrinsic-item-contributions
931 // Spec modifcation: https://www.w3.org/TR/css-flexbox-1/#change-2016-max-contribution
932 // Issue: https://github.com/w3c/csswg-drafts/issues/1435
933 // Gentest: padding_border_overrides_size_flex_basis_0.html
934 let clamping_basis = Some(item.flex_basis).maybe_max(style_preferred);
935 let flex_basis_min = clamping_basis.filter(|_| item.flex_shrink == 0.0);
936 let flex_basis_max = clamping_basis.filter(|_| item.flex_grow == 0.0);
937
938 let min_main_size = style_min
939 .maybe_max(flex_basis_min)
940 .or(flex_basis_min)
941 .unwrap_or(item.resolved_minimum_main_size)
942 .max(item.resolved_minimum_main_size);
943 let max_main_size =
944 style_max.maybe_min(flex_basis_max).or(flex_basis_max).unwrap_or(f32::INFINITY);
945
946 let content_contribution = match (min_main_size, style_preferred, max_main_size) {
947 // If the clamping values are such that max <= min, then we can avoid the expensive step of computing the content size
948 // as we know that the clamping values will override it anyway
949 (min, Some(pref), max) if max <= min || max <= pref => {
950 pref.min(max).max(min) + item.margin.main_axis_sum(constants.dir)
951 }
952 (min, _, max) if max <= min => min + item.margin.main_axis_sum(constants.dir),
953 // Else compute the min- or -max content size and apply the full formula for computing the
954 // min- or max- content contributuon
955 _ => {
956 // Parent size for child sizing
957 let cross_axis_parent_size = constants.node_inner_size.cross(dir);
958
959 // Available space for child sizing
960 let cross_axis_margin_sum = constants.margin.cross_axis_sum(dir);
961 let child_min_cross = item.min_size.cross(dir).maybe_add(cross_axis_margin_sum);
962 let child_max_cross = item.max_size.cross(dir).maybe_add(cross_axis_margin_sum);
963 let cross_axis_available_space: AvailableSpace = available_space
964 .cross(dir)
965 .map_definite_value(|val| cross_axis_parent_size.unwrap_or(val))
966 .maybe_clamp(child_min_cross, child_max_cross);
967
968 let child_available_space = available_space.with_cross(dir, cross_axis_available_space);
969
970 // Either the min- or max- content size depending on which constraint we are sizing under.
971 // TODO: Optimise by using already computed values where available
972 let content_main_size = tree
973 .measure_child_size(
974 item.node,
975 Size::NONE,
976 constants.node_inner_size,
977 child_available_space,
978 SizingMode::InherentSize,
979 Line::FALSE,
980 )
981 .main(constants.dir)
982 + item.margin.main_axis_sum(constants.dir);
983
984 // This is somewhat bizarre in that it's asymetrical depending whether the flex container is a column or a row.
985 //
986 // I *think* this might relate to https://drafts.csswg.org/css-flexbox-1/#algo-main-container:
987 //
988 // "The automatic block size of a block-level flex container is its max-content size."
989 //
990 // Which could suggest that flex-basis defining a vertical size does not shrink because it is in the block axis, and the automatic size
991 // in the block axis is a MAX content size. Whereas a flex-basis defining a horizontal size does shrink because the automatic size in
992 // inline axis is MIN content size (although I don't have a reference for that).
993 //
994 // Ultimately, this was not found by reading the spec, but by trial and error fixing tests to align with Webkit/Firefox output.
995 // (see the `flex_basis_unconstraint_row` and `flex_basis_uncontraint_column` generated tests which demonstrate this)
996 if constants.is_row {
997 content_main_size.maybe_clamp(style_min, style_max).max(main_content_box_inset)
998 } else {
999 content_main_size
1000 .max(item.flex_basis)
1001 .maybe_clamp(style_min, style_max)
1002 .max(main_content_box_inset)
1003 }
1004 }
1005 };
1006 item.content_flex_fraction = {
1007 let diff = content_contribution - item.flex_basis;
1008 if diff > 0.0 {
1009 diff / f32_max(1.0, item.flex_grow)
1010 } else if diff < 0.0 {
1011 let scaled_shrink_factor = f32_max(1.0, item.flex_shrink * item.inner_flex_basis);
1012 diff / scaled_shrink_factor
1013 } else {
1014 // We are assuming that diff is 0.0 here and that we haven't accidentally introduced a NaN
1015 0.0
1016 }
1017 };
1018 }
1019
1020 // TODO Spec says to scale everything by the line's max flex fraction. But neither Chrome nor firefox implement this
1021 // so we don't either. But if we did want to, we'd need this computation here (and to use it below):
1022 //
1023 // Within each line, find the largest max-content flex fraction among all the flex items.
1024 // let line_flex_fraction = line
1025 // .items
1026 // .iter()
1027 // .map(|item| item.content_flex_fraction)
1028 // .max_by(|a, b| a.total_cmp(b))
1029 // .unwrap_or(0.0); // Unwrap case never gets hit because there is always at least one item a line
1030
1031 // Add each item’s flex base size to the product of:
1032 // - its flex grow factor (or scaled flex shrink factor,if the chosen max-content flex fraction was negative)
1033 // - the chosen max-content flex fraction
1034 // then clamp that result by the max main size floored by the min main size.
1035 //
1036 // The flex container’s max-content size is the largest sum of the afore-calculated sizes of all items within a single line.
1037 let item_main_size_sum = line
1038 .items
1039 .iter_mut()
1040 .map(|item| {
1041 let flex_fraction = item.content_flex_fraction;
1042 // let flex_fraction = line_flex_fraction;
1043
1044 let flex_contribution = if item.content_flex_fraction > 0.0 {
1045 f32_max(1.0, item.flex_grow) * flex_fraction
1046 } else if item.content_flex_fraction < 0.0 {
1047 let scaled_shrink_factor = f32_max(1.0, item.flex_shrink) * item.inner_flex_basis;
1048 scaled_shrink_factor * flex_fraction
1049 } else {
1050 0.0
1051 };
1052 let size = item.flex_basis + flex_contribution;
1053 item.outer_target_size.set_main(constants.dir, size);
1054 item.target_size.set_main(constants.dir, size);
1055 size
1056 })
1057 .sum::<f32>();
1058
1059 let gap_sum = sum_axis_gaps(constants.gap.main(constants.dir), line.items.len());
1060 main_size = f32_max(main_size, item_main_size_sum + gap_sum)
1061 }
1062
1063 main_size + main_content_box_inset
1064 }
1065 }
1066 });
1067
1068 let outer_main_size = outer_main_size
1069 .maybe_clamp(constants.min_size.main(constants.dir), constants.max_size.main(constants.dir))
1070 .max(main_content_box_inset - constants.scrollbar_gutter.main(constants.dir));
1071
1072 // let outer_main_size = inner_main_size + constants.padding_border.main_axis_sum(constants.dir);
1073 let inner_main_size = f32_max(outer_main_size - main_content_box_inset, 0.0);
1074 constants.container_size.set_main(constants.dir, outer_main_size);
1075 constants.inner_container_size.set_main(constants.dir, inner_main_size);
1076 constants.node_inner_size.set_main(constants.dir, Some(inner_main_size));
1077}
1078
1079/// Resolve the flexible lengths of the items within a flex line.
1080/// Sets the `main` component of each item's `target_size` and `outer_target_size`
1081///
1082/// # [9.7. Resolving Flexible Lengths](https://www.w3.org/TR/css-flexbox-1/#resolve-flexible-lengths)
1083#[inline]
1084fn resolve_flexible_lengths(line: &mut FlexLine, constants: &AlgoConstants, original_gap: Size<f32>) {
1085 let total_original_main_axis_gap = sum_axis_gaps(original_gap.main(constants.dir), line.items.len());
1086 let total_main_axis_gap = sum_axis_gaps(constants.gap.main(constants.dir), line.items.len());
1087
1088 // 1. Determine the used flex factor. Sum the outer hypothetical main sizes of all
1089 // items on the line. If the sum is less than the flex container’s inner main size,
1090 // use the flex grow factor for the rest of this algorithm; otherwise, use the
1091 // flex shrink factor.
1092
1093 let total_hypothetical_outer_main_size =
1094 line.items.iter().map(|child| child.hypothetical_outer_size.main(constants.dir)).sum::<f32>();
1095 let used_flex_factor: f32 = total_original_main_axis_gap + total_hypothetical_outer_main_size;
1096 let growing = used_flex_factor < constants.node_inner_size.main(constants.dir).unwrap_or(0.0);
1097 let shrinking = !growing;
1098
1099 // 2. Size inflexible items. Freeze, setting its target main size to its hypothetical main size
1100 // - Any item that has a flex factor of zero
1101 // - If using the flex grow factor: any item that has a flex base size
1102 // greater than its hypothetical main size
1103 // - If using the flex shrink factor: any item that has a flex base size
1104 // smaller than its hypothetical main size
1105
1106 for child in line.items.iter_mut() {
1107 let inner_target_size = child.hypothetical_inner_size.main(constants.dir);
1108 child.target_size.set_main(constants.dir, inner_target_size);
1109
1110 if (child.flex_grow == 0.0 && child.flex_shrink == 0.0)
1111 || (growing && child.flex_basis > child.hypothetical_inner_size.main(constants.dir))
1112 || (shrinking && child.flex_basis < child.hypothetical_inner_size.main(constants.dir))
1113 {
1114 child.frozen = true;
1115 let outer_target_size = inner_target_size + child.margin.main_axis_sum(constants.dir);
1116 child.outer_target_size.set_main(constants.dir, outer_target_size);
1117 }
1118 }
1119
1120 // 3. Calculate initial free space. Sum the outer sizes of all items on the line,
1121 // and subtract this from the flex container’s inner main size. For frozen items,
1122 // use their outer target main size; for other items, use their outer flex base size.
1123
1124 let used_space: f32 = total_main_axis_gap
1125 + line
1126 .items
1127 .iter()
1128 .map(|child| {
1129 child.margin.main_axis_sum(constants.dir)
1130 + if child.frozen { child.outer_target_size.main(constants.dir) } else { child.flex_basis }
1131 })
1132 .sum::<f32>();
1133
1134 let initial_free_space = constants.node_inner_size.main(constants.dir).maybe_sub(used_space).unwrap_or(0.0);
1135
1136 // 4. Loop
1137
1138 loop {
1139 // a. Check for flexible items. If all the flex items on the line are frozen,
1140 // free space has been distributed; exit this loop.
1141
1142 if line.items.iter().all(|child| child.frozen) {
1143 break;
1144 }
1145
1146 // b. Calculate the remaining free space as for initial free space, above.
1147 // If the sum of the unfrozen flex items’ flex factors is less than one,
1148 // multiply the initial free space by this sum. If the magnitude of this
1149 // value is less than the magnitude of the remaining free space, use this
1150 // as the remaining free space.
1151
1152 let used_space: f32 = total_main_axis_gap
1153 + line
1154 .items
1155 .iter()
1156 .map(|child| {
1157 child.margin.main_axis_sum(constants.dir)
1158 + if child.frozen { child.outer_target_size.main(constants.dir) } else { child.flex_basis }
1159 })
1160 .sum::<f32>();
1161
1162 let mut unfrozen: Vec<&mut FlexItem> = line.items.iter_mut().filter(|child| !child.frozen).collect();
1163
1164 let (sum_flex_grow, sum_flex_shrink): (f32, f32) =
1165 unfrozen.iter().fold((0.0, 0.0), |(flex_grow, flex_shrink), item| {
1166 (flex_grow + item.flex_grow, flex_shrink + item.flex_shrink)
1167 });
1168
1169 let free_space = if growing && sum_flex_grow < 1.0 {
1170 (initial_free_space * sum_flex_grow - total_main_axis_gap)
1171 .maybe_min(constants.node_inner_size.main(constants.dir).maybe_sub(used_space))
1172 } else if shrinking && sum_flex_shrink < 1.0 {
1173 (initial_free_space * sum_flex_shrink - total_main_axis_gap)
1174 .maybe_max(constants.node_inner_size.main(constants.dir).maybe_sub(used_space))
1175 } else {
1176 (constants.node_inner_size.main(constants.dir).maybe_sub(used_space))
1177 .unwrap_or(used_flex_factor - used_space)
1178 };
1179
1180 // c. Distribute free space proportional to the flex factors.
1181 // - If the remaining free space is zero
1182 // Do Nothing
1183 // - If using the flex grow factor
1184 // Find the ratio of the item’s flex grow factor to the sum of the
1185 // flex grow factors of all unfrozen items on the line. Set the item’s
1186 // target main size to its flex base size plus a fraction of the remaining
1187 // free space proportional to the ratio.
1188 // - If using the flex shrink factor
1189 // For every unfrozen item on the line, multiply its flex shrink factor by
1190 // its inner flex base size, and note this as its scaled flex shrink factor.
1191 // Find the ratio of the item’s scaled flex shrink factor to the sum of the
1192 // scaled flex shrink factors of all unfrozen items on the line. Set the item’s
1193 // target main size to its flex base size minus a fraction of the absolute value
1194 // of the remaining free space proportional to the ratio. Note this may result
1195 // in a negative inner main size; it will be corrected in the next step.
1196 // - Otherwise
1197 // Do Nothing
1198
1199 if free_space.is_normal() {
1200 if growing && sum_flex_grow > 0.0 {
1201 for child in &mut unfrozen {
1202 child
1203 .target_size
1204 .set_main(constants.dir, child.flex_basis + free_space * (child.flex_grow / sum_flex_grow));
1205 }
1206 } else if shrinking && sum_flex_shrink > 0.0 {
1207 let sum_scaled_shrink_factor: f32 =
1208 unfrozen.iter().map(|child| child.inner_flex_basis * child.flex_shrink).sum();
1209
1210 if sum_scaled_shrink_factor > 0.0 {
1211 for child in &mut unfrozen {
1212 let scaled_shrink_factor = child.inner_flex_basis * child.flex_shrink;
1213 child.target_size.set_main(
1214 constants.dir,
1215 child.flex_basis + free_space * (scaled_shrink_factor / sum_scaled_shrink_factor),
1216 )
1217 }
1218 }
1219 }
1220 }
1221
1222 // d. Fix min/max violations. Clamp each non-frozen item’s target main size by its
1223 // used min and max main sizes and floor its content-box size at zero. If the
1224 // item’s target main size was made smaller by this, it’s a max violation.
1225 // If the item’s target main size was made larger by this, it’s a min violation.
1226
1227 let total_violation = unfrozen.iter_mut().fold(0.0, |acc, child| -> f32 {
1228 let resolved_min_main: Option<f32> = child.resolved_minimum_main_size.into();
1229 let max_main = child.max_size.main(constants.dir);
1230 let clamped = child.target_size.main(constants.dir).maybe_clamp(resolved_min_main, max_main).max(0.0);
1231 child.violation = clamped - child.target_size.main(constants.dir);
1232 child.target_size.set_main(constants.dir, clamped);
1233 child.outer_target_size.set_main(
1234 constants.dir,
1235 child.target_size.main(constants.dir) + child.margin.main_axis_sum(constants.dir),
1236 );
1237
1238 acc + child.violation
1239 });
1240
1241 // e. Freeze over-flexed items. The total violation is the sum of the adjustments
1242 // from the previous step ∑(clamped size - unclamped size). If the total violation is:
1243 // - Zero
1244 // Freeze all items.
1245 // - Positive
1246 // Freeze all the items with min violations.
1247 // - Negative
1248 // Freeze all the items with max violations.
1249
1250 for child in &mut unfrozen {
1251 match total_violation {
1252 v if v > 0.0 => child.frozen = child.violation > 0.0,
1253 v if v < 0.0 => child.frozen = child.violation < 0.0,
1254 _ => child.frozen = true,
1255 }
1256 }
1257
1258 // f. Return to the start of this loop.
1259 }
1260}
1261
1262/// Determine the hypothetical cross size of each item.
1263///
1264/// # [9.4. Cross Size Determination](https://www.w3.org/TR/css-flexbox-1/#cross-sizing)
1265///
1266/// - [**Determine the hypothetical cross size of each item**](https://www.w3.org/TR/css-flexbox-1/#algo-cross-item)
1267/// by performing layout with the used main size and the available space, treating auto as fit-content.
1268#[inline]
1269fn determine_hypothetical_cross_size(
1270 tree: &mut impl LayoutTree,
1271 line: &mut FlexLine,
1272 constants: &AlgoConstants,
1273 available_space: Size<AvailableSpace>,
1274) {
1275 for child in line.items.iter_mut() {
1276 let padding_border_sum = (child.padding + child.border).cross_axis_sum(constants.dir);
1277
1278 let child_known_main = constants.container_size.main(constants.dir).into();
1279
1280 let child_cross = child
1281 .size
1282 .cross(constants.dir)
1283 .maybe_clamp(child.min_size.cross(constants.dir), child.max_size.cross(constants.dir))
1284 .maybe_max(padding_border_sum);
1285
1286 let child_available_cross = available_space
1287 .cross(constants.dir)
1288 .maybe_clamp(child.min_size.cross(constants.dir), child.max_size.cross(constants.dir))
1289 .maybe_max(padding_border_sum);
1290
1291 let child_inner_cross = child_cross.unwrap_or_else(|| {
1292 tree.measure_child_size(
1293 child.node,
1294 Size {
1295 width: if constants.is_row { child.target_size.width.into() } else { child_cross },
1296 height: if constants.is_row { child_cross } else { child.target_size.height.into() },
1297 },
1298 constants.node_inner_size,
1299 Size {
1300 width: if constants.is_row { child_known_main } else { child_available_cross },
1301 height: if constants.is_row { child_available_cross } else { child_known_main },
1302 },
1303 SizingMode::ContentSize,
1304 Line::FALSE,
1305 )
1306 .cross(constants.dir)
1307 .maybe_clamp(child.min_size.cross(constants.dir), child.max_size.cross(constants.dir))
1308 .max(padding_border_sum)
1309 });
1310 let child_outer_cross = child_inner_cross + child.margin.cross_axis_sum(constants.dir);
1311
1312 child.hypothetical_inner_size.set_cross(constants.dir, child_inner_cross);
1313 child.hypothetical_outer_size.set_cross(constants.dir, child_outer_cross);
1314 }
1315}
1316
1317/// Calculate the base lines of the children.
1318#[inline]
1319fn calculate_children_base_lines(
1320 tree: &mut impl LayoutTree,
1321 node_size: Size<Option<f32>>,
1322 available_space: Size<AvailableSpace>,
1323 flex_lines: &mut [FlexLine],
1324 constants: &AlgoConstants,
1325) {
1326 // Only compute baselines for flex rows because we only support baseline alignment in the cross axis
1327 // where that axis is also the inline axis
1328 // TODO: this may need revisiting if/when we support vertical writing modes
1329 if !constants.is_row {
1330 return;
1331 }
1332
1333 for line in flex_lines {
1334 // If a flex line has one or zero items participating in baseline alignment then baseline alignment is a no-op so we skip
1335 let line_baseline_child_count =
1336 line.items.iter().filter(|child| child.align_self == AlignSelf::Baseline).count();
1337 if line_baseline_child_count <= 1 {
1338 continue;
1339 }
1340
1341 for child in line.items.iter_mut() {
1342 // Only calculate baselines for children participating in baseline alignment
1343 if child.align_self != AlignSelf::Baseline {
1344 continue;
1345 }
1346
1347 let measured_size_and_baselines = tree.perform_child_layout(
1348 child.node,
1349 Size {
1350 width: if constants.is_row {
1351 child.target_size.width.into()
1352 } else {
1353 child.hypothetical_inner_size.width.into()
1354 },
1355 height: if constants.is_row {
1356 child.hypothetical_inner_size.height.into()
1357 } else {
1358 child.target_size.height.into()
1359 },
1360 },
1361 constants.node_inner_size,
1362 Size {
1363 width: if constants.is_row {
1364 constants.container_size.width.into()
1365 } else {
1366 available_space.width.maybe_set(node_size.width)
1367 },
1368 height: if constants.is_row {
1369 available_space.height.maybe_set(node_size.height)
1370 } else {
1371 constants.container_size.height.into()
1372 },
1373 },
1374 SizingMode::ContentSize,
1375 Line::FALSE,
1376 );
1377
1378 let baseline = measured_size_and_baselines.first_baselines.y;
1379 let height = measured_size_and_baselines.size.height;
1380
1381 child.baseline = baseline.unwrap_or(height) + child.margin.top;
1382 }
1383 }
1384}
1385
1386/// Calculate the cross size of each flex line.
1387///
1388/// # [9.4. Cross Size Determination](https://www.w3.org/TR/css-flexbox-1/#cross-sizing)
1389///
1390/// - [**Calculate the cross size of each flex line**](https://www.w3.org/TR/css-flexbox-1/#algo-cross-line).
1391///
1392/// If the flex container is single-line and has a definite cross size, the cross size of the flex line is the flex container’s inner cross size.
1393///
1394/// Otherwise, for each flex line:
1395///
1396/// 1. Collect all the flex items whose inline-axis is parallel to the main-axis, whose align-self is baseline, and whose cross-axis margins are both non-auto.
1397/// Find the largest of the distances between each item’s baseline and its hypothetical outer cross-start edge,
1398/// and the largest of the distances between each item’s baseline and its hypothetical outer cross-end edge, and sum these two values.
1399///
1400/// 2. Among all the items not collected by the previous step, find the largest outer hypothetical cross size.
1401///
1402/// 3. The used cross-size of the flex line is the largest of the numbers found in the previous two steps and zero.
1403///
1404/// If the flex container is single-line, then clamp the line’s cross-size to be within the container’s computed min and max cross sizes.
1405/// **Note that if CSS 2.1’s definition of min/max-width/height applied more generally, this behavior would fall out automatically**.
1406#[inline]
1407fn calculate_cross_size(flex_lines: &mut [FlexLine], node_size: Size<Option<f32>>, constants: &AlgoConstants) {
1408 // Note: AlignContent::SpaceEvenly and AlignContent::SpaceAround behave like AlignContent::Stretch when there is only
1409 // a single flex line in the container. See: https://www.w3.org/TR/css-flexbox-1/#align-content-property
1410 // Also: align_content is ignored entirely (and thus behaves like Stretch) when `flex_wrap` is set to `nowrap`.
1411 if flex_lines.len() == 1
1412 && node_size.cross(constants.dir).is_some()
1413 && (!constants.is_wrap
1414 || matches!(
1415 constants.align_content,
1416 AlignContent::Stretch | AlignContent::SpaceEvenly | AlignContent::SpaceAround
1417 ))
1418 {
1419 let cross_axis_padding_border = constants.content_box_inset.cross_axis_sum(constants.dir);
1420 let cross_min_size = constants.min_size.cross(constants.dir);
1421 let cross_max_size = constants.max_size.cross(constants.dir);
1422 flex_lines[0].cross_size = node_size
1423 .cross(constants.dir)
1424 .maybe_clamp(cross_min_size, cross_max_size)
1425 .maybe_sub(cross_axis_padding_border)
1426 .maybe_max(0.0)
1427 .unwrap_or(0.0);
1428 } else {
1429 for line in flex_lines.iter_mut() {
1430 // 1. Collect all the flex items whose inline-axis is parallel to the main-axis, whose
1431 // align-self is baseline, and whose cross-axis margins are both non-auto. Find the
1432 // largest of the distances between each item’s baseline and its hypothetical outer
1433 // cross-start edge, and the largest of the distances between each item’s baseline
1434 // and its hypothetical outer cross-end edge, and sum these two values.
1435
1436 // 2. Among all the items not collected by the previous step, find the largest
1437 // outer hypothetical cross size.
1438
1439 // 3. The used cross-size of the flex line is the largest of the numbers found in the
1440 // previous two steps and zero.
1441
1442 let max_baseline: f32 = line.items.iter().map(|child| child.baseline).fold(0.0, |acc, x| acc.max(x));
1443 line.cross_size = line
1444 .items
1445 .iter()
1446 .map(|child| {
1447 if child.align_self == AlignSelf::Baseline
1448 && !child.margin_is_auto.cross_start(constants.dir)
1449 && !child.margin_is_auto.cross_end(constants.dir)
1450 {
1451 max_baseline - child.baseline + child.hypothetical_outer_size.cross(constants.dir)
1452 } else {
1453 child.hypothetical_outer_size.cross(constants.dir)
1454 }
1455 })
1456 .fold(0.0, |acc, x| acc.max(x));
1457 }
1458 }
1459}
1460
1461/// Handle 'align-content: stretch'.
1462///
1463/// # [9.4. Cross Size Determination](https://www.w3.org/TR/css-flexbox-1/#cross-sizing)
1464///
1465/// - [**Handle 'align-content: stretch'**](https://www.w3.org/TR/css-flexbox-1/#algo-line-stretch). If the flex container has a definite cross size, align-content is stretch,
1466/// and the sum of the flex lines' cross sizes is less than the flex container’s inner cross size,
1467/// increase the cross size of each flex line by equal amounts such that the sum of their cross sizes exactly equals the flex container’s inner cross size.
1468#[inline]
1469fn handle_align_content_stretch(flex_lines: &mut [FlexLine], node_size: Size<Option<f32>>, constants: &AlgoConstants) {
1470 if constants.align_content == AlignContent::Stretch {
1471 let cross_axis_padding_border = constants.content_box_inset.cross_axis_sum(constants.dir);
1472 let cross_min_size = constants.min_size.cross(constants.dir);
1473 let cross_max_size = constants.max_size.cross(constants.dir);
1474 let container_min_inner_cross = node_size
1475 .cross(constants.dir)
1476 .or(cross_min_size)
1477 .maybe_clamp(cross_min_size, cross_max_size)
1478 .maybe_sub(cross_axis_padding_border)
1479 .maybe_max(0.0)
1480 .unwrap_or(0.0);
1481
1482 let total_cross_axis_gap = sum_axis_gaps(constants.gap.cross(constants.dir), flex_lines.len());
1483 let lines_total_cross: f32 = flex_lines.iter().map(|line| line.cross_size).sum::<f32>() + total_cross_axis_gap;
1484
1485 if lines_total_cross < container_min_inner_cross {
1486 let remaining = container_min_inner_cross - lines_total_cross;
1487 let addition = remaining / flex_lines.len() as f32;
1488 flex_lines.iter_mut().for_each(|line| line.cross_size += addition);
1489 }
1490 }
1491}
1492
1493/// Determine the used cross size of each flex item.
1494///
1495/// # [9.4. Cross Size Determination](https://www.w3.org/TR/css-flexbox-1/#cross-sizing)
1496///
1497/// - [**Determine the used cross size of each flex item**](https://www.w3.org/TR/css-flexbox-1/#algo-stretch). If a flex item has align-self: stretch, its computed cross size property is auto,
1498/// and neither of its cross-axis margins are auto, the used outer cross size is the used cross size of its flex line, clamped according to the item’s used min and max cross sizes.
1499/// Otherwise, the used cross size is the item’s hypothetical cross size.
1500///
1501/// If the flex item has align-self: stretch, redo layout for its contents, treating this used size as its definite cross size so that percentage-sized children can be resolved.
1502///
1503/// **Note that this step does not affect the main size of the flex item, even if it has an intrinsic aspect ratio**.
1504#[inline]
1505fn determine_used_cross_size(tree: &impl LayoutTree, flex_lines: &mut [FlexLine], constants: &AlgoConstants) {
1506 for line in flex_lines {
1507 let line_cross_size = line.cross_size;
1508
1509 for child in line.items.iter_mut() {
1510 let child_style = tree.style(child.node);
1511 child.target_size.set_cross(
1512 constants.dir,
1513 if child.align_self == AlignSelf::Stretch
1514 && !child.margin_is_auto.cross_start(constants.dir)
1515 && !child.margin_is_auto.cross_end(constants.dir)
1516 && child_style.size.cross(constants.dir) == Dimension::Auto
1517 {
1518 // For some reason this particular usage of max_width is an exception to the rule that max_width's transfer
1519 // using the aspect_ratio (if set). Both Chrome and Firefox agree on this. And reading the spec, it seems like
1520 // a reasonable interpretation. Although it seems to me that the spec *should* apply aspect_ratio here.
1521 let max_size_ignoring_aspect_ratio = child_style.max_size.maybe_resolve(constants.node_inner_size);
1522
1523 (line_cross_size - child.margin.cross_axis_sum(constants.dir)).maybe_clamp(
1524 child.min_size.cross(constants.dir),
1525 max_size_ignoring_aspect_ratio.cross(constants.dir),
1526 )
1527 } else {
1528 child.hypothetical_inner_size.cross(constants.dir)
1529 },
1530 );
1531
1532 child.outer_target_size.set_cross(
1533 constants.dir,
1534 child.target_size.cross(constants.dir) + child.margin.cross_axis_sum(constants.dir),
1535 );
1536 }
1537 }
1538}
1539
1540/// Distribute any remaining free space.
1541///
1542/// # [9.5. Main-Axis Alignment](https://www.w3.org/TR/css-flexbox-1/#main-alignment)
1543///
1544/// - [**Distribute any remaining free space**](https://www.w3.org/TR/css-flexbox-1/#algo-main-align). For each flex line:
1545///
1546/// 1. If the remaining free space is positive and at least one main-axis margin on this line is `auto`, distribute the free space equally among these margins.
1547/// Otherwise, set all `auto` margins to zero.
1548///
1549/// 2. Align the items along the main-axis per `justify-content`.
1550#[inline]
1551fn distribute_remaining_free_space(flex_lines: &mut [FlexLine], constants: &AlgoConstants) {
1552 for line in flex_lines {
1553 let total_main_axis_gap = sum_axis_gaps(constants.gap.main(constants.dir), line.items.len());
1554 let used_space: f32 = total_main_axis_gap
1555 + line.items.iter().map(|child| child.outer_target_size.main(constants.dir)).sum::<f32>();
1556 let free_space = constants.inner_container_size.main(constants.dir) - used_space;
1557 let mut num_auto_margins = 0;
1558
1559 for child in line.items.iter_mut() {
1560 if child.margin_is_auto.main_start(constants.dir) {
1561 num_auto_margins += 1;
1562 }
1563 if child.margin_is_auto.main_end(constants.dir) {
1564 num_auto_margins += 1;
1565 }
1566 }
1567
1568 if free_space > 0.0 && num_auto_margins > 0 {
1569 let margin = free_space / num_auto_margins as f32;
1570
1571 for child in line.items.iter_mut() {
1572 if child.margin_is_auto.main_start(constants.dir) {
1573 if constants.is_row {
1574 child.margin.left = margin;
1575 } else {
1576 child.margin.top = margin;
1577 }
1578 }
1579 if child.margin_is_auto.main_end(constants.dir) {
1580 if constants.is_row {
1581 child.margin.right = margin;
1582 } else {
1583 child.margin.bottom = margin;
1584 }
1585 }
1586 }
1587 } else {
1588 let num_items = line.items.len();
1589 let layout_reverse = constants.dir.is_reverse();
1590 let gap = constants.gap.main(constants.dir);
1591 let justify_content_mode = constants.justify_content.unwrap_or(JustifyContent::FlexStart);
1592
1593 let justify_item = |(i, child): (usize, &mut FlexItem)| {
1594 child.offset_main =
1595 compute_alignment_offset(free_space, num_items, gap, justify_content_mode, layout_reverse, i == 0);
1596 };
1597
1598 if layout_reverse {
1599 line.items.iter_mut().rev().enumerate().for_each(justify_item);
1600 } else {
1601 line.items.iter_mut().enumerate().for_each(justify_item);
1602 }
1603 }
1604 }
1605}
1606
1607/// Resolve cross-axis `auto` margins.
1608///
1609/// # [9.6. Cross-Axis Alignment](https://www.w3.org/TR/css-flexbox-1/#cross-alignment)
1610///
1611/// - [**Resolve cross-axis `auto` margins**](https://www.w3.org/TR/css-flexbox-1/#algo-cross-margins).
1612/// If a flex item has auto cross-axis margins:
1613///
1614/// - If its outer cross size (treating those auto margins as zero) is less than the cross size of its flex line,
1615/// distribute the difference in those sizes equally to the auto margins.
1616///
1617/// - Otherwise, if the block-start or inline-start margin (whichever is in the cross axis) is auto, set it to zero.
1618/// Set the opposite margin so that the outer cross size of the item equals the cross size of its flex line.
1619#[inline]
1620fn resolve_cross_axis_auto_margins(flex_lines: &mut [FlexLine], constants: &AlgoConstants) {
1621 for line in flex_lines {
1622 let line_cross_size = line.cross_size;
1623 let max_baseline: f32 = line.items.iter_mut().map(|child| child.baseline).fold(0.0, |acc, x| acc.max(x));
1624
1625 for child in line.items.iter_mut() {
1626 let free_space = line_cross_size - child.outer_target_size.cross(constants.dir);
1627
1628 if child.margin_is_auto.cross_start(constants.dir) && child.margin_is_auto.cross_end(constants.dir) {
1629 if constants.is_row {
1630 child.margin.top = free_space / 2.0;
1631 child.margin.bottom = free_space / 2.0;
1632 } else {
1633 child.margin.left = free_space / 2.0;
1634 child.margin.right = free_space / 2.0;
1635 }
1636 } else if child.margin_is_auto.cross_start(constants.dir) {
1637 if constants.is_row {
1638 child.margin.top = free_space;
1639 } else {
1640 child.margin.left = free_space;
1641 }
1642 } else if child.margin_is_auto.cross_end(constants.dir) {
1643 if constants.is_row {
1644 child.margin.bottom = free_space;
1645 } else {
1646 child.margin.right = free_space;
1647 }
1648 } else {
1649 // 14. Align all flex items along the cross-axis.
1650 child.offset_cross = align_flex_items_along_cross_axis(child, free_space, max_baseline, constants);
1651 }
1652 }
1653 }
1654}
1655
1656/// Align all flex items along the cross-axis.
1657///
1658/// # [9.6. Cross-Axis Alignment](https://www.w3.org/TR/css-flexbox-1/#cross-alignment)
1659///
1660/// - [**Align all flex items along the cross-axis**](https://www.w3.org/TR/css-flexbox-1/#algo-cross-align) per `align-self`,
1661/// if neither of the item's cross-axis margins are `auto`.
1662#[inline]
1663fn align_flex_items_along_cross_axis(
1664 child: &FlexItem,
1665 free_space: f32,
1666 max_baseline: f32,
1667 constants: &AlgoConstants,
1668) -> f32 {
1669 match child.align_self {
1670 AlignSelf::Start => 0.0,
1671 AlignSelf::FlexStart => {
1672 if constants.is_wrap_reverse {
1673 free_space
1674 } else {
1675 0.0
1676 }
1677 }
1678 AlignSelf::End => free_space,
1679 AlignSelf::FlexEnd => {
1680 if constants.is_wrap_reverse {
1681 0.0
1682 } else {
1683 free_space
1684 }
1685 }
1686 AlignSelf::Center => free_space / 2.0,
1687 AlignSelf::Baseline => {
1688 if constants.is_row {
1689 max_baseline - child.baseline
1690 } else {
1691 // Until we support vertical writing modes, baseline alignment only makes sense if
1692 // the constants.direction is row, so we treat it as flex-start alignment in columns.
1693 if constants.is_wrap_reverse {
1694 free_space
1695 } else {
1696 0.0
1697 }
1698 }
1699 }
1700 AlignSelf::Stretch => {
1701 if constants.is_wrap_reverse {
1702 free_space
1703 } else {
1704 0.0
1705 }
1706 }
1707 }
1708}
1709
1710/// Determine the flex container’s used cross size.
1711///
1712/// # [9.6. Cross-Axis Alignment](https://www.w3.org/TR/css-flexbox-1/#cross-alignment)
1713///
1714/// - [**Determine the flex container’s used cross size**](https://www.w3.org/TR/css-flexbox-1/#algo-cross-container):
1715///
1716/// - If the cross size property is a definite size, use that, clamped by the used min and max cross sizes of the flex container.
1717///
1718/// - Otherwise, use the sum of the flex lines' cross sizes, clamped by the used min and max cross sizes of the flex container.
1719#[inline]
1720#[must_use]
1721fn determine_container_cross_size(
1722 flex_lines: &[FlexLine],
1723 node_size: Size<Option<f32>>,
1724 constants: &mut AlgoConstants,
1725) -> f32 {
1726 let total_cross_axis_gap = sum_axis_gaps(constants.gap.cross(constants.dir), flex_lines.len());
1727 let total_line_cross_size: f32 = flex_lines.iter().map(|line| line.cross_size).sum::<f32>();
1728
1729 let padding_border_sum = constants.content_box_inset.cross_axis_sum(constants.dir);
1730 let cross_scrollbar_gutter = constants.scrollbar_gutter.cross(constants.dir);
1731 let min_cross_size = constants.min_size.cross(constants.dir);
1732 let max_cross_size = constants.max_size.cross(constants.dir);
1733 let outer_container_size = node_size
1734 .cross(constants.dir)
1735 .unwrap_or(total_line_cross_size + total_cross_axis_gap + padding_border_sum)
1736 .maybe_clamp(min_cross_size, max_cross_size)
1737 .max(padding_border_sum - cross_scrollbar_gutter);
1738 let inner_container_size = f32_max(outer_container_size - padding_border_sum, 0.0);
1739
1740 constants.container_size.set_cross(constants.dir, outer_container_size);
1741 constants.inner_container_size.set_cross(constants.dir, inner_container_size);
1742
1743 total_line_cross_size
1744}
1745
1746/// Align all flex lines per `align-content`.
1747///
1748/// # [9.6. Cross-Axis Alignment](https://www.w3.org/TR/css-flexbox-1/#cross-alignment)
1749///
1750/// - [**Align all flex lines**](https://www.w3.org/TR/css-flexbox-1/#algo-line-align) per `align-content`.
1751#[inline]
1752fn align_flex_lines_per_align_content(flex_lines: &mut [FlexLine], constants: &AlgoConstants, total_cross_size: f32) {
1753 let num_lines = flex_lines.len();
1754 let gap = constants.gap.cross(constants.dir);
1755 let align_content_mode = constants.align_content;
1756 let total_cross_axis_gap = sum_axis_gaps(gap, num_lines);
1757 let free_space = constants.inner_container_size.cross(constants.dir) - total_cross_size - total_cross_axis_gap;
1758
1759 let align_line = |(i, line): (usize, &mut FlexLine)| {
1760 line.offset_cross =
1761 compute_alignment_offset(free_space, num_lines, gap, align_content_mode, constants.is_wrap_reverse, i == 0);
1762 };
1763
1764 if constants.is_wrap_reverse {
1765 flex_lines.iter_mut().rev().enumerate().for_each(align_line);
1766 } else {
1767 flex_lines.iter_mut().enumerate().for_each(align_line);
1768 }
1769}
1770
1771/// Calculates the layout for a flex-item
1772#[allow(clippy::too_many_arguments)]
1773fn calculate_flex_item(
1774 tree: &mut impl LayoutTree,
1775 item: &mut FlexItem,
1776 total_offset_main: &mut f32,
1777 total_offset_cross: f32,
1778 line_offset_cross: f32,
1779 container_size: Size<f32>,
1780 node_inner_size: Size<Option<f32>>,
1781 direction: FlexDirection,
1782) {
1783 let preliminary_size_and_baselines = tree.perform_child_layout(
1784 item.node,
1785 item.target_size.map(|s| s.into()),
1786 node_inner_size,
1787 container_size.map(|s| s.into()),
1788 SizingMode::ContentSize,
1789 Line::FALSE,
1790 );
1791 let preliminary_size = preliminary_size_and_baselines.size;
1792
1793 let offset_main = *total_offset_main
1794 + item.offset_main
1795 + item.margin.main_start(direction)
1796 + (item.inset.main_start(direction).or(item.inset.main_end(direction).map(|pos| -pos)).unwrap_or(0.0));
1797
1798 let offset_cross = total_offset_cross
1799 + item.offset_cross
1800 + line_offset_cross
1801 + item.margin.cross_start(direction)
1802 + (item.inset.cross_start(direction).or(item.inset.cross_end(direction).map(|pos| -pos)).unwrap_or(0.0));
1803
1804 if direction.is_row() {
1805 let baseline_offset_cross = total_offset_cross + item.offset_cross + item.margin.cross_start(direction);
1806 let inner_baseline = preliminary_size_and_baselines.first_baselines.y.unwrap_or(preliminary_size.height);
1807 item.baseline = baseline_offset_cross + inner_baseline;
1808 } else {
1809 let baseline_offset_main = *total_offset_main + item.offset_main + item.margin.main_start(direction);
1810 let inner_baseline = preliminary_size_and_baselines.first_baselines.y.unwrap_or(preliminary_size.height);
1811 item.baseline = baseline_offset_main + inner_baseline;
1812 }
1813
1814 *tree.layout_mut(item.node) = Layout {
1815 order: item.order,
1816 size: preliminary_size_and_baselines.size,
1817 location: Point {
1818 x: if direction.is_row() { offset_main } else { offset_cross },
1819 y: if direction.is_column() { offset_main } else { offset_cross },
1820 },
1821 };
1822
1823 *total_offset_main += item.offset_main + item.margin.main_axis_sum(direction) + preliminary_size.main(direction);
1824}
1825
1826/// Calculates the layout line
1827#[allow(clippy::too_many_arguments)]
1828fn calculate_layout_line(
1829 tree: &mut impl LayoutTree,
1830 line: &mut FlexLine,
1831 total_offset_cross: &mut f32,
1832 container_size: Size<f32>,
1833 node_inner_size: Size<Option<f32>>,
1834 padding_border: Rect<f32>,
1835 direction: FlexDirection,
1836) {
1837 let mut total_offset_main = padding_border.main_start(direction);
1838 let line_offset_cross = line.offset_cross;
1839
1840 if direction.is_reverse() {
1841 for item in line.items.iter_mut().rev() {
1842 calculate_flex_item(
1843 tree,
1844 item,
1845 &mut total_offset_main,
1846 *total_offset_cross,
1847 line_offset_cross,
1848 container_size,
1849 node_inner_size,
1850 direction,
1851 );
1852 }
1853 } else {
1854 for item in line.items.iter_mut() {
1855 calculate_flex_item(
1856 tree,
1857 item,
1858 &mut total_offset_main,
1859 *total_offset_cross,
1860 line_offset_cross,
1861 container_size,
1862 node_inner_size,
1863 direction,
1864 );
1865 }
1866 }
1867
1868 *total_offset_cross += line_offset_cross + line.cross_size;
1869}
1870
1871/// Do a final layout pass and collect the resulting layouts.
1872#[inline]
1873fn final_layout_pass(tree: &mut impl LayoutTree, flex_lines: &mut [FlexLine], constants: &AlgoConstants) {
1874 let mut total_offset_cross = constants.content_box_inset.cross_start(constants.dir);
1875
1876 if constants.is_wrap_reverse {
1877 for line in flex_lines.iter_mut().rev() {
1878 calculate_layout_line(
1879 tree,
1880 line,
1881 &mut total_offset_cross,
1882 constants.container_size,
1883 constants.node_inner_size,
1884 constants.content_box_inset,
1885 constants.dir,
1886 );
1887 }
1888 } else {
1889 for line in flex_lines.iter_mut() {
1890 calculate_layout_line(
1891 tree,
1892 line,
1893 &mut total_offset_cross,
1894 constants.container_size,
1895 constants.node_inner_size,
1896 constants.content_box_inset,
1897 constants.dir,
1898 );
1899 }
1900 }
1901}
1902
1903/// Perform absolute layout on all absolutely positioned children.
1904#[inline]
1905fn perform_absolute_layout_on_absolute_children(tree: &mut impl LayoutTree, node: NodeId, constants: &AlgoConstants) {
1906 let container_width = constants.container_size.width;
1907 let container_height = constants.container_size.height;
1908
1909 for order in 0..tree.child_count(node) {
1910 let child = tree.child(node, order);
1911 let child_style = tree.style(child);
1912
1913 // Skip items that are display:none or are not position:absolute
1914 if child_style.display == Display::None || child_style.position != Position::Absolute {
1915 continue;
1916 }
1917
1918 let aspect_ratio = child_style.aspect_ratio;
1919 let align_self = child_style.align_self.unwrap_or(constants.align_items);
1920 let margin = child_style.margin.map(|margin| margin.resolve_to_option(container_width));
1921 let padding = child_style.padding.resolve_or_zero(Some(container_width));
1922 let border = child_style.border.resolve_or_zero(Some(container_width));
1923 let padding_border_sum = (padding + border).sum_axes();
1924
1925 // Resolve inset
1926 let left = child_style.inset.left.maybe_resolve(container_width);
1927 let right = child_style.inset.right.maybe_resolve(container_width);
1928 let top = child_style.inset.top.maybe_resolve(container_height);
1929 let bottom = child_style.inset.bottom.maybe_resolve(container_height);
1930
1931 // Compute known dimensions from min/max/inherent size styles
1932 let style_size =
1933 child_style.size.maybe_resolve(constants.container_size).maybe_apply_aspect_ratio(aspect_ratio);
1934 let min_size = child_style
1935 .min_size
1936 .maybe_resolve(constants.container_size)
1937 .maybe_apply_aspect_ratio(aspect_ratio)
1938 .or(padding_border_sum.map(Some))
1939 .maybe_max(padding_border_sum);
1940 let max_size =
1941 child_style.max_size.maybe_resolve(constants.container_size).maybe_apply_aspect_ratio(aspect_ratio);
1942 let mut known_dimensions = style_size.maybe_clamp(min_size, max_size);
1943
1944 // Fill in width from left/right and reapply aspect ratio if:
1945 // - Width is not already known
1946 // - Item has both left and right inset properties set
1947 if let (None, Some(left), Some(right)) = (known_dimensions.width, left, right) {
1948 let new_width_raw = container_width.maybe_sub(margin.left).maybe_sub(margin.right) - left - right;
1949 known_dimensions.width = Some(f32_max(new_width_raw, 0.0));
1950 known_dimensions = known_dimensions.maybe_apply_aspect_ratio(aspect_ratio).maybe_clamp(min_size, max_size);
1951 }
1952
1953 // Fill in height from top/bottom and reapply aspect ratio if:
1954 // - Height is not already known
1955 // - Item has both top and bottom inset properties set
1956 if let (None, Some(top), Some(bottom)) = (known_dimensions.height, top, bottom) {
1957 let new_height_raw = container_height.maybe_sub(margin.top).maybe_sub(margin.bottom) - top - bottom;
1958 known_dimensions.height = Some(f32_max(new_height_raw, 0.0));
1959 known_dimensions = known_dimensions.maybe_apply_aspect_ratio(aspect_ratio).maybe_clamp(min_size, max_size);
1960 }
1961
1962 let measured_size_and_baselines = tree.perform_child_layout(
1963 child,
1964 known_dimensions,
1965 constants.node_inner_size,
1966 Size {
1967 width: AvailableSpace::Definite(container_width.maybe_clamp(min_size.width, max_size.width)),
1968 height: AvailableSpace::Definite(container_height.maybe_clamp(min_size.height, max_size.height)),
1969 },
1970 SizingMode::ContentSize,
1971 Line::FALSE,
1972 );
1973 let measured_size = measured_size_and_baselines.size;
1974 let final_size = known_dimensions.unwrap_or(measured_size).maybe_clamp(min_size, max_size);
1975
1976 let non_auto_margin = margin.map(|m| m.unwrap_or(0.0));
1977
1978 let free_space = Size {
1979 width: constants.container_size.width - final_size.width - non_auto_margin.horizontal_axis_sum(),
1980 height: constants.container_size.height - final_size.height - non_auto_margin.vertical_axis_sum(),
1981 }
1982 .f32_max(Size::ZERO);
1983
1984 // Expand auto margins to fill available space
1985 let resolved_margin = {
1986 let auto_margin_size = Size {
1987 width: {
1988 let auto_margin_count = margin.left.is_none() as u8 + margin.right.is_none() as u8;
1989 if auto_margin_count > 0 {
1990 free_space.width / auto_margin_count as f32
1991 } else {
1992 0.0
1993 }
1994 },
1995 height: {
1996 let auto_margin_count = margin.top.is_none() as u8 + margin.bottom.is_none() as u8;
1997 if auto_margin_count > 0 {
1998 free_space.height / auto_margin_count as f32
1999 } else {
2000 0.0
2001 }
2002 },
2003 };
2004
2005 Rect {
2006 left: margin.left.unwrap_or(auto_margin_size.width),
2007 right: margin.right.unwrap_or(auto_margin_size.width),
2008 top: margin.top.unwrap_or(auto_margin_size.height),
2009 bottom: margin.bottom.unwrap_or(auto_margin_size.height),
2010 }
2011 };
2012
2013 // Determine flex-relative insets
2014 let (start_main, end_main) = if constants.is_row { (left, right) } else { (top, bottom) };
2015 let (start_cross, end_cross) = if constants.is_row { (top, bottom) } else { (left, right) };
2016
2017 // Apply main-axis alignment
2018 // let free_main_space = free_space.main(constants.dir) - resolved_margin.main_axis_sum(constants.dir);
2019 let offset_main = if let Some(start) = start_main {
2020 start + constants.border.main_start(constants.dir) + resolved_margin.main_start(constants.dir)
2021 } else if let Some(end) = end_main {
2022 constants.container_size.main(constants.dir)
2023 - constants.border.main_end(constants.dir)
2024 - final_size.main(constants.dir)
2025 - end
2026 - resolved_margin.main_end(constants.dir)
2027 } else {
2028 // Stretch is an invalid value for justify_content in the flexbox algorithm, so we
2029 // treat it as if it wasn't set (and thus we default to FlexStart behaviour)
2030 match (constants.justify_content.unwrap_or(JustifyContent::Start), constants.is_wrap_reverse) {
2031 (JustifyContent::SpaceBetween, _)
2032 | (JustifyContent::Start, _)
2033 | (JustifyContent::Stretch, false)
2034 | (JustifyContent::FlexStart, false)
2035 | (JustifyContent::FlexEnd, true) => {
2036 constants.content_box_inset.main_start(constants.dir) + resolved_margin.main_start(constants.dir)
2037 }
2038 (JustifyContent::End, _)
2039 | (JustifyContent::FlexEnd, false)
2040 | (JustifyContent::FlexStart, true)
2041 | (JustifyContent::Stretch, true) => {
2042 constants.container_size.main(constants.dir)
2043 - constants.content_box_inset.main_end(constants.dir)
2044 - final_size.main(constants.dir)
2045 - resolved_margin.main_end(constants.dir)
2046 }
2047 (JustifyContent::SpaceEvenly, _) | (JustifyContent::SpaceAround, _) | (JustifyContent::Center, _) => {
2048 (constants.container_size.main(constants.dir)
2049 + constants.content_box_inset.main_start(constants.dir)
2050 - constants.content_box_inset.main_end(constants.dir)
2051 - final_size.main(constants.dir)
2052 + resolved_margin.main_start(constants.dir)
2053 - resolved_margin.main_end(constants.dir))
2054 / 2.0
2055 }
2056 }
2057 };
2058
2059 // Apply cross-axis alignment
2060 // let free_cross_space = free_space.cross(constants.dir) - resolved_margin.cross_axis_sum(constants.dir);
2061 let offset_cross = if let Some(start) = start_cross {
2062 start + constants.border.cross_start(constants.dir) + resolved_margin.cross_start(constants.dir)
2063 } else if let Some(end) = end_cross {
2064 constants.container_size.cross(constants.dir)
2065 - constants.border.cross_end(constants.dir)
2066 - final_size.cross(constants.dir)
2067 - end
2068 - resolved_margin.cross_end(constants.dir)
2069 } else {
2070 match (align_self, constants.is_wrap_reverse) {
2071 // Stretch alignment does not apply to absolutely positioned items
2072 // See "Example 3" at https://www.w3.org/TR/css-flexbox-1/#abspos-items
2073 // Note: Stretch should be FlexStart not Start when we support both
2074 (AlignSelf::Start, _)
2075 | (AlignSelf::Baseline | AlignSelf::Stretch | AlignSelf::FlexStart, false)
2076 | (AlignSelf::FlexEnd, true) => {
2077 constants.content_box_inset.cross_start(constants.dir) + resolved_margin.cross_start(constants.dir)
2078 }
2079 (AlignSelf::End, _)
2080 | (AlignSelf::Baseline | AlignSelf::Stretch | AlignSelf::FlexStart, true)
2081 | (AlignSelf::FlexEnd, false) => {
2082 constants.container_size.cross(constants.dir)
2083 - constants.content_box_inset.cross_end(constants.dir)
2084 - final_size.cross(constants.dir)
2085 - resolved_margin.cross_end(constants.dir)
2086 }
2087 (AlignSelf::Center, _) => {
2088 (constants.container_size.cross(constants.dir)
2089 + constants.content_box_inset.cross_start(constants.dir)
2090 - constants.content_box_inset.cross_end(constants.dir)
2091 - final_size.cross(constants.dir)
2092 + resolved_margin.cross_start(constants.dir)
2093 - resolved_margin.cross_end(constants.dir))
2094 / 2.0
2095 }
2096 }
2097 };
2098
2099 *tree.layout_mut(child) = Layout {
2100 order: order as u32,
2101 size: final_size,
2102 location: Point {
2103 x: if constants.is_row { offset_main } else { offset_cross },
2104 y: if constants.is_column { offset_main } else { offset_cross },
2105 },
2106 };
2107 }
2108}
2109
2110/// Computes the total space taken up by gaps in an axis given:
2111/// - The size of each gap
2112/// - The number of items (children or flex-lines) between which there are gaps
2113#[inline(always)]
2114fn sum_axis_gaps(gap: f32, num_items: usize) -> f32 {
2115 // Gaps only exist between items, so...
2116 if num_items <= 1 {
2117 // ...if there are less than 2 items then there are no gaps
2118 0.0
2119 } else {
2120 // ...otherwise there are (num_items - 1) gaps
2121 gap * (num_items - 1) as f32
2122 }
2123}
2124
2125#[cfg(test)]
2126mod tests {
2127 #![allow(clippy::redundant_clone)]
2128
2129 use crate::{
2130 geometry::Size,
2131 style::{FlexWrap, Style},
2132 util::{MaybeMath, ResolveOrZero},
2133 Taffy,
2134 };
2135
2136 // Make sure we get correct constants
2137 #[test]
2138 fn correct_constants() {
2139 let mut tree = Taffy::with_capacity(16);
2140
2141 let style = Style::default();
2142 let node_id = tree.new_leaf(style.clone()).unwrap();
2143
2144 let node_size = Size::NONE;
2145 let parent_size = Size::NONE;
2146
2147 let constants = super::compute_constants(tree.style(node_id).unwrap(), node_size, parent_size);
2148
2149 assert!(constants.dir == style.flex_direction);
2150 assert!(constants.is_row == style.flex_direction.is_row());
2151 assert!(constants.is_column == style.flex_direction.is_column());
2152 assert!(constants.is_wrap_reverse == (style.flex_wrap == FlexWrap::WrapReverse));
2153
2154 let margin = style.margin.resolve_or_zero(parent_size);
2155 assert_eq!(constants.margin, margin);
2156
2157 let border = style.border.resolve_or_zero(parent_size);
2158 let padding = style.padding.resolve_or_zero(parent_size);
2159 let padding_border = padding + border;
2160 assert_eq!(constants.border, border);
2161 assert_eq!(constants.content_box_inset, padding_border);
2162
2163 let inner_size = Size {
2164 width: node_size.width.maybe_sub(padding_border.horizontal_axis_sum()),
2165 height: node_size.height.maybe_sub(padding_border.vertical_axis_sum()),
2166 };
2167 assert_eq!(constants.node_inner_size, inner_size);
2168
2169 assert_eq!(constants.container_size, Size::zero());
2170 assert_eq!(constants.inner_container_size, Size::zero());
2171 }
2172}