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