Unit test `compute_constants()` (#184)
1//! Computes the [flexbox](https://css-tricks.com/snippets/css/a-guide-to-flexbox/) layout algorithm on a [`Forest`](crate::forest::Forest) according to the [spec](https://www.w3.org/TR/css-flexbox-1/)
2//!
3//! Note that some minor steps appear to be missing: see https://github.com/DioxusLabs/taffy/issues for more information.
4use core::f32;
5
6use crate::forest::{Forest, NodeData};
7use crate::geometry::{Point, Rect, Size};
8use crate::layout::{Cache, Layout};
9use crate::math::MaybeMath;
10use crate::node::{MeasureFunc, NodeId};
11use crate::resolve::{MaybeResolve, ResolveOrDefault};
12use crate::style::{AlignContent, AlignSelf, Dimension, Display, FlexWrap, JustifyContent, PositionType};
13use crate::style::{FlexDirection, FlexboxLayout};
14use crate::sys::{abs, round, ChildrenVec, Vec};
15
16/// The intermediate results of a flexbox calculation for a single item
17struct FlexItem {
18 /// The identifier for the associated [`Node`](crate::node::Node)
19 node: NodeId,
20
21 /// The base size of this item
22 size: Size<Option<f32>>,
23 /// The minimum allowable size of this item
24 min_size: Size<Option<f32>>,
25 /// The maximum allowable size of this item
26 max_size: Size<Option<f32>>,
27
28 /// The final offset of this item
29 position: Rect<Option<f32>>,
30 /// The margin of this item
31 margin: Rect<f32>,
32 /// The padding of this item
33 padding: Rect<f32>,
34 /// The border of this item
35 border: Rect<f32>,
36
37 /// The default size of this item
38 flex_basis: f32,
39 /// The default size of this item, minus padding and border
40 inner_flex_basis: f32,
41 /// The amount by which this item has deviated from its target size
42 violation: f32,
43 /// Is the size of this item locked
44 frozen: bool,
45
46 /// The proposed inner size of this item
47 hypothetical_inner_size: Size<f32>,
48 /// The proposed outer size of this item
49 hypothetical_outer_size: Size<f32>,
50 /// The size that this item wants to be
51 target_size: Size<f32>,
52 /// The size that this item wants to be, plus any padding and border
53 outer_target_size: Size<f32>,
54
55 /// The position of the bottom edge of this item
56 baseline: f32,
57
58 /// A temporary value for the main offset
59 ///
60 /// Offset is the relative position from the item's natural flow position based on
61 /// relative position values, alignment, and justification. Does not include margin/padding/border.
62 offset_main: f32,
63 /// A temporary value for the cross offset
64 ///
65 /// Offset is the relative position from the item's natural flow position based on
66 /// relative position values, alignment, and justification. Does not include margin/padding/border.
67 offset_cross: f32,
68}
69
70/// A line of [`FlexItem`] used for intermediate computation
71struct FlexLine<'a> {
72 /// The slice of items to iterate over during computation of this line
73 items: &'a mut [FlexItem],
74 /// The dimensions of the cross-axis
75 cross_size: f32,
76 /// The relative offset of the cross-axis
77 offset_cross: f32,
78}
79
80/// Values that can be cached during the flexbox algorithm
81struct AlgoConstants {
82 /// The direction of the current segment being layed out
83 dir: FlexDirection,
84 /// Is this segment a row
85 is_row: bool,
86 /// Is this segment a column
87 is_column: bool,
88 /// Is the wrap direction inverted
89 is_wrap_reverse: bool,
90
91 /// The margin of this section
92 margin: Rect<f32>,
93 /// The border of this section
94 border: Rect<f32>,
95 /// The padding of this section
96 padding_border: Rect<f32>,
97
98 /// The size of the internal node
99 node_inner_size: Size<Option<f32>>,
100 /// The size of the surrounding container
101 container_size: Size<f32>,
102 /// The size of the internal container
103 inner_container_size: Size<f32>,
104}
105
106impl Forest {
107 /// Computes the layout of this [`Forest`] according to the flexbox algorithm
108 pub(crate) fn compute(&mut self, root: NodeId, size: Size<Option<f32>>) {
109 let style = self.nodes[root].style;
110 let has_root_min_max = style.min_size.width.is_defined()
111 || style.min_size.height.is_defined()
112 || style.max_size.width.is_defined()
113 || style.max_size.height.is_defined();
114
115 let preliminary_size = if has_root_min_max {
116 let first_pass = self.compute_preliminary(root, style.size.maybe_resolve(size), size, false, true);
117
118 self.compute_preliminary(
119 root,
120 Size {
121 width: first_pass
122 .width
123 .maybe_max(style.min_size.width.maybe_resolve(size.width))
124 .maybe_min(style.max_size.width.maybe_resolve(size.width))
125 .into(),
126 height: first_pass
127 .height
128 .maybe_max(style.min_size.height.maybe_resolve(size.height))
129 .maybe_min(style.max_size.height.maybe_resolve(size.height))
130 .into(),
131 },
132 size,
133 true,
134 true,
135 )
136 } else {
137 self.compute_preliminary(root, style.size.maybe_resolve(size), size, true, true)
138 };
139
140 self.nodes[root].layout = Layout { order: 0, size: preliminary_size, location: Point::ZERO };
141
142 Self::round_layout(&mut self.nodes, &self.children, root, 0.0, 0.0);
143 }
144
145 /// Rounds the calculated [`NodeData`] according to the spec
146 fn round_layout(nodes: &mut [NodeData], children: &[ChildrenVec<NodeId>], root: NodeId, abs_x: f32, abs_y: f32) {
147 let layout = &mut nodes[root].layout;
148 let abs_x = abs_x + layout.location.x;
149 let abs_y = abs_y + layout.location.y;
150
151 layout.location.x = round(layout.location.x);
152 layout.location.y = round(layout.location.y);
153
154 layout.size.width = round(layout.size.width);
155 layout.size.height = round(layout.size.height);
156
157 for child in &children[root] {
158 Self::round_layout(nodes, children, *child, abs_x, abs_y);
159 }
160 }
161
162 /// Saves intermediate results to a [`Cache`]
163 fn cache(&mut self, node: NodeId, main_size: bool) -> &mut Option<Cache> {
164 if main_size {
165 &mut self.nodes[node].main_size_layout_cache
166 } else {
167 &mut self.nodes[node].other_layout_cache
168 }
169 }
170
171 /// Try to get the computation result from the cache.
172 #[inline]
173 fn compute_from_cache(
174 &mut self,
175 node: NodeId,
176 node_size: Size<Option<f32>>,
177 parent_size: Size<Option<f32>>,
178 perform_layout: bool,
179 main_size: bool,
180 ) -> Option<Size<f32>> {
181 if let Some(ref cache) = self.cache(node, main_size) {
182 if cache.perform_layout || !perform_layout {
183 let width_compatible = if let Some(width) = node_size.width {
184 abs(width - cache.size.width) < f32::EPSILON
185 } else {
186 cache.node_size.width.is_none()
187 };
188
189 let height_compatible = if let Some(height) = node_size.height {
190 abs(height - cache.size.height) < f32::EPSILON
191 } else {
192 cache.node_size.height.is_none()
193 };
194
195 if width_compatible && height_compatible {
196 return Some(cache.size);
197 }
198
199 if cache.node_size == node_size && cache.parent_size == parent_size {
200 return Some(cache.size);
201 }
202 }
203 }
204
205 None
206 }
207
208 /// Compute constants that can be reused during the flexbox algorithm.
209 #[inline]
210 fn compute_constants(
211 node: &NodeData,
212 node_size: Size<Option<f32>>,
213 parent_size: Size<Option<f32>>,
214 ) -> AlgoConstants {
215 let dir = node.style.flex_direction;
216 let is_row = dir.is_row();
217 let is_column = dir.is_column();
218 let is_wrap_reverse = node.style.flex_wrap == FlexWrap::WrapReverse;
219
220 let margin = node.style.margin.resolve_or_default(parent_size.width);
221 let padding = node.style.padding.resolve_or_default(parent_size.width);
222 let border = node.style.border.resolve_or_default(parent_size.width);
223
224 let padding_border = Rect {
225 start: padding.start + border.start,
226 end: padding.end + border.end,
227 top: padding.top + border.top,
228 bottom: padding.bottom + border.bottom,
229 };
230
231 let node_inner_size = Size {
232 width: node_size.width.maybe_sub(padding_border.horizontal_axis_sum()),
233 height: node_size.height.maybe_sub(padding_border.vertical_axis_sum()),
234 };
235
236 let container_size = Size::ZERO;
237 let inner_container_size = Size::ZERO;
238
239 AlgoConstants {
240 dir,
241 is_row,
242 is_column,
243 is_wrap_reverse,
244 margin,
245 border,
246 padding_border,
247 node_inner_size,
248 container_size,
249 inner_container_size,
250 }
251 }
252
253 /// Generate anonymous flex items.
254 ///
255 /// # [9.1. Initial Setup](https://www.w3.org/TR/css-flexbox-1/#box-manip)
256 ///
257 /// - [**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).
258 #[inline]
259 fn generate_anonymous_flex_items(&self, node: NodeId, constants: &AlgoConstants) -> Vec<FlexItem> {
260 self.children[node]
261 .iter()
262 .map(|child| (child, &self.nodes[*child].style))
263 .filter(|(_, style)| style.position_type != PositionType::Absolute)
264 .filter(|(_, style)| style.display != Display::None)
265 .map(|(child, child_style)| FlexItem {
266 node: *child,
267 size: child_style.size.maybe_resolve(constants.node_inner_size),
268 min_size: child_style.min_size.maybe_resolve(constants.node_inner_size),
269 max_size: child_style.max_size.maybe_resolve(constants.node_inner_size),
270
271 position: child_style.position.zip_size(constants.node_inner_size, |p, s| p.maybe_resolve(s)),
272 margin: child_style.margin.resolve_or_default(constants.node_inner_size.width),
273 padding: child_style.padding.resolve_or_default(constants.node_inner_size.width),
274 border: child_style.border.resolve_or_default(constants.node_inner_size.width),
275 flex_basis: 0.0,
276 inner_flex_basis: 0.0,
277 violation: 0.0,
278 frozen: false,
279
280 hypothetical_inner_size: Size::ZERO,
281 hypothetical_outer_size: Size::ZERO,
282 target_size: Size::ZERO,
283 outer_target_size: Size::ZERO,
284
285 baseline: 0.0,
286
287 offset_main: 0.0,
288 offset_cross: 0.0,
289 })
290 .collect()
291 }
292
293 /// Determine the available main and cross space for the flex items.
294 ///
295 /// # [9.2. Line Length Determination](https://www.w3.org/TR/css-flexbox-1/#line-sizing)
296 ///
297 /// - [**Determine the available main and cross space for the flex items**](https://www.w3.org/TR/css-flexbox-1/#algo-available).
298 /// For each dimension, if that dimension of the flex container’s content box is a definite size, use that;
299 /// 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;
300 /// 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.
301 /// **This might result in an infinite value**.
302 #[inline]
303 #[must_use]
304 fn determine_available_space(
305 node_size: Size<Option<f32>>,
306 parent_size: Size<Option<f32>>,
307 constants: &AlgoConstants,
308 ) -> Size<Option<f32>> {
309 let width = match node_size.width {
310 Some(node_width) => Some(node_width),
311 None => parent_size
312 .width
313 .maybe_sub(constants.margin.horizontal_axis_sum())
314 .maybe_sub(constants.padding_border.horizontal_axis_sum()),
315 };
316
317 let height = match node_size.height {
318 Some(node_height) => Some(node_height),
319 None => parent_size
320 .height
321 .maybe_sub(constants.margin.vertical_axis_sum())
322 .maybe_sub(constants.padding_border.vertical_axis_sum()),
323 };
324
325 Size { width, height }
326 }
327
328 /// Determine the flex base size and hypothetical main size of each item.
329 ///
330 /// # [9.2. Line Length Determination](https://www.w3.org/TR/css-flexbox-1/#line-sizing)
331 ///
332 /// - [**Determine the flex base size and hypothetical main size of each item:**](https://www.w3.org/TR/css-flexbox-1/#algo-main-item)
333 ///
334 /// - A. If the item has a definite used flex basis, that’s the flex base size.
335 ///
336 /// - B. If the flex item has ...
337 ///
338 /// - an intrinsic aspect ratio,
339 /// - a used flex basis of content, and
340 /// - a definite cross size,
341 ///
342 /// then the flex base size is calculated from its inner cross size and the flex item’s intrinsic aspect ratio.
343 ///
344 /// - 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
345 /// or max-content constraint (e.g. when performing automatic table layout \[CSS21\]), size the item under that constraint.
346 /// The flex base size is the item’s resulting main size.
347 ///
348 /// - 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.
349 /// 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,
350 /// in this calculation use fit-content as the flex item’s cross size. The flex base size is the item’s resulting main size.
351 ///
352 /// When determining the flex base size, the item’s min and max main sizes are ignored (no clamping occurs).
353 /// Furthermore, the sizing calculations that floor the content box size at zero when applying box-sizing are also ignored.
354 /// (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.)
355 #[inline]
356 fn determine_flex_base_size(
357 &mut self,
358 node: NodeId,
359 node_size: Size<Option<f32>>,
360 constants: &AlgoConstants,
361 available_space: Size<Option<f32>>,
362 flex_items: &mut Vec<FlexItem>,
363 ) {
364 // TODO - this does not follow spec. See the TODOs below
365 for child in flex_items.iter_mut() {
366 let child_style = self.nodes[child.node].style;
367
368 // A. If the item has a definite used flex basis, that’s the flex base size.
369
370 let flex_basis = child_style.flex_basis.maybe_resolve(constants.node_inner_size.main(constants.dir));
371 if flex_basis.is_some() {
372 child.flex_basis = flex_basis.unwrap_or(0.0);
373 continue;
374 };
375
376 // B. If the flex item has an intrinsic aspect ratio,
377 // a used flex basis of content, and a definite cross size,
378 // then the flex base size is calculated from its inner
379 // cross size and the flex item’s intrinsic aspect ratio.
380
381 if let Some(ratio) = child_style.aspect_ratio {
382 if let Some(cross) = node_size.cross(constants.dir) {
383 if child_style.flex_basis == Dimension::Auto {
384 child.flex_basis = cross * ratio;
385 continue;
386 }
387 }
388 }
389
390 // C. If the used flex basis is content or depends on its available space,
391 // and the flex container is being sized under a min-content or max-content
392 // constraint (e.g. when performing automatic table layout [CSS21]),
393 // size the item under that constraint. The flex base size is the item’s
394 // resulting main size.
395
396 // TODO - Probably need to cover this case in future
397
398 // D. Otherwise, if the used flex basis is content or depends on its
399 // available space, the available main size is infinite, and the flex item’s
400 // inline axis is parallel to the main axis, lay the item out using the rules
401 // for a box in an orthogonal flow [CSS3-WRITING-MODES]. The flex base size
402 // is the item’s max-content main size.
403
404 // TODO - Probably need to cover this case in future
405
406 // E. Otherwise, size the item into the available space using its used flex basis
407 // in place of its main size, treating a value of content as max-content.
408 // If a cross size is needed to determine the main size (e.g. when the
409 // flex item’s main size is in its block axis) and the flex item’s cross size
410 // is auto and not definite, in this calculation use fit-content as the
411 // flex item’s cross size. The flex base size is the item’s resulting main size.
412
413 let width: Option<f32> = if child.size.width.is_none()
414 && child_style.align_self(&self.nodes[node].style) == AlignSelf::Stretch
415 && constants.is_column
416 {
417 available_space.width
418 } else {
419 child.size.width
420 };
421
422 let height: Option<f32> = if child.size.height.is_none()
423 && child_style.align_self(&self.nodes[node].style) == AlignSelf::Stretch
424 && constants.is_row
425 {
426 available_space.height
427 } else {
428 child.size.height
429 };
430
431 child.flex_basis = self
432 .compute_preliminary(
433 child.node,
434 Size {
435 width: width.maybe_min(child.max_size.width),
436 height: height.maybe_min(child.max_size.height),
437 },
438 available_space,
439 false,
440 true,
441 )
442 .main(constants.dir)
443 .maybe_min(child.max_size.main(constants.dir));
444 }
445
446 // The hypothetical main size is the item’s flex base size clamped according to its
447 // used min and max main sizes (and flooring the content box size at zero).
448
449 for child in flex_items {
450 child.inner_flex_basis = child.flex_basis
451 - child.padding.main_axis_sum(constants.dir)
452 - child.border.main_axis_sum(constants.dir);
453
454 // TODO - not really spec abiding but needs to be done somewhere. probably somewhere else though.
455 // The following logic was developed not from the spec but by trail and error looking into how
456 // webkit handled various scenarios. Can probably be solved better by passing in
457 // min-content max-content constraints from the top
458 let min_main = self
459 .compute_preliminary(child.node, Size::undefined(), available_space, false, false)
460 .main(constants.dir)
461 .maybe_max(child.min_size.main(constants.dir))
462 .maybe_min(child.size.main(constants.dir))
463 .into();
464
465 child.hypothetical_inner_size.set_main(
466 constants.dir,
467 child.flex_basis.maybe_max(min_main).maybe_min(child.max_size.main(constants.dir)),
468 );
469
470 child.hypothetical_outer_size.set_main(
471 constants.dir,
472 child.hypothetical_inner_size.main(constants.dir) + child.margin.main_axis_sum(constants.dir),
473 );
474 }
475 }
476
477 /// Collect flex items into flex lines.
478 ///
479 /// # [9.3. Main Size Determination](https://www.w3.org/TR/css-flexbox-1/#main-sizing)
480 ///
481 /// - [**Collect flex items into flex lines**](https://www.w3.org/TR/css-flexbox-1/#algo-line-break):
482 ///
483 /// - If the flex container is single-line, collect all the flex items into a single flex line.
484 ///
485 /// - 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
486 /// (or until a forced break is encountered, see [§10 Fragmenting Flex Layout](https://www.w3.org/TR/css-flexbox-1/#pagination)).
487 /// If the very first uncollected item wouldn’t fit, collect just it into the line.
488 ///
489 /// For this step, the size of a flex item is its outer hypothetical main size. (**Note: This can be negative**.)
490 ///
491 /// Repeat until all flex items have been collected into flex lines.
492 ///
493 /// **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**.
494 #[inline]
495 fn collect_flex_lines<'a>(
496 &self,
497 node: NodeId,
498 constants: &AlgoConstants,
499 available_space: Size<Option<f32>>,
500 flex_items: &'a mut Vec<FlexItem>,
501 ) -> Vec<FlexLine<'a>> {
502 let mut lines = crate::sys::new_vec_with_capacity(1);
503
504 if self.nodes[node].style.flex_wrap == FlexWrap::NoWrap {
505 lines.push(FlexLine { items: flex_items.as_mut_slice(), cross_size: 0.0, offset_cross: 0.0 });
506 } else {
507 let mut flex_items = &mut flex_items[..];
508
509 while !flex_items.is_empty() {
510 let mut line_length = 0.0;
511 let index = flex_items
512 .iter()
513 .enumerate()
514 .find(|&(idx, child)| {
515 line_length += child.hypothetical_outer_size.main(constants.dir);
516 if let Some(main) = available_space.main(constants.dir) {
517 line_length > main && idx != 0
518 } else {
519 false
520 }
521 })
522 .map(|(idx, _)| idx)
523 .unwrap_or(flex_items.len());
524
525 let (items, rest) = flex_items.split_at_mut(index);
526 lines.push(FlexLine { items, cross_size: 0.0, offset_cross: 0.0 });
527 flex_items = rest;
528 }
529 }
530
531 lines
532 }
533
534 /// Resolve the flexible lengths of the items within a flex line.
535 ///
536 /// # [9.7. Resolving Flexible Lengths](https://www.w3.org/TR/css-flexbox-1/#resolve-flexible-lengths)
537 #[inline]
538 fn resolve_flexible_lengths(
539 &mut self,
540 line: &mut FlexLine,
541 constants: &AlgoConstants,
542 available_space: Size<Option<f32>>,
543 ) {
544 // 1. Determine the used flex factor. Sum the outer hypothetical main sizes of all
545 // items on the line. If the sum is less than the flex container’s inner main size,
546 // use the flex grow factor for the rest of this algorithm; otherwise, use the
547 // flex shrink factor.
548
549 let used_flex_factor: f32 =
550 line.items.iter().map(|child| child.hypothetical_outer_size.main(constants.dir)).sum();
551 let growing = used_flex_factor < constants.node_inner_size.main(constants.dir).unwrap_or(0.0);
552 let shrinking = !growing;
553
554 // 2. Size inflexible items. Freeze, setting its target main size to its hypothetical main size
555 // - Any item that has a flex factor of zero
556 // - If using the flex grow factor: any item that has a flex base size
557 // greater than its hypothetical main size
558 // - If using the flex shrink factor: any item that has a flex base size
559 // smaller than its hypothetical main size
560
561 for child in line.items.iter_mut() {
562 // TODO - This is not found by reading the spec. Maybe this can be done in some other place
563 // instead. This was found by trail and error fixing tests to align with webkit output.
564 if constants.node_inner_size.main(constants.dir).is_none() && constants.is_row {
565 child.target_size.set_main(
566 constants.dir,
567 self.compute_preliminary(
568 child.node,
569 Size {
570 width: child.size.width.maybe_max(child.min_size.width).maybe_min(child.max_size.width),
571 height: child.size.height.maybe_max(child.min_size.height).maybe_min(child.max_size.height),
572 },
573 available_space,
574 false,
575 false,
576 )
577 .main(constants.dir)
578 .maybe_max(child.min_size.main(constants.dir))
579 .maybe_min(child.max_size.main(constants.dir)),
580 );
581 } else {
582 child.target_size.set_main(constants.dir, child.hypothetical_inner_size.main(constants.dir));
583 }
584
585 // TODO this should really only be set inside the if-statement below but
586 // that causes the target_main_size to never be set for some items
587
588 child.outer_target_size.set_main(
589 constants.dir,
590 child.target_size.main(constants.dir) + child.margin.main_axis_sum(constants.dir),
591 );
592
593 let child_style = &self.nodes[child.node].style;
594 if (child_style.flex_grow == 0.0 && child_style.flex_shrink == 0.0)
595 || (growing && child.flex_basis > child.hypothetical_inner_size.main(constants.dir))
596 || (shrinking && child.flex_basis < child.hypothetical_inner_size.main(constants.dir))
597 {
598 child.frozen = true;
599 }
600 }
601
602 // 3. Calculate initial free space. Sum the outer sizes of all items on the line,
603 // and subtract this from the flex container’s inner main size. For frozen items,
604 // use their outer target main size; for other items, use their outer flex base size.
605
606 let used_space: f32 = line
607 .items
608 .iter()
609 .map(|child| {
610 child.margin.main_axis_sum(constants.dir)
611 + if child.frozen { child.target_size.main(constants.dir) } else { child.flex_basis }
612 })
613 .sum();
614
615 let initial_free_space = constants.node_inner_size.main(constants.dir).maybe_sub(used_space).unwrap_or(0.0);
616
617 // 4. Loop
618
619 loop {
620 // a. Check for flexible items. If all the flex items on the line are frozen,
621 // free space has been distributed; exit this loop.
622
623 if line.items.iter().all(|child| child.frozen) {
624 break;
625 }
626
627 // b. Calculate the remaining free space as for initial free space, above.
628 // If the sum of the unfrozen flex items’ flex factors is less than one,
629 // multiply the initial free space by this sum. If the magnitude of this
630 // value is less than the magnitude of the remaining free space, use this
631 // as the remaining free space.
632
633 let used_space: f32 = line
634 .items
635 .iter()
636 .map(|child| {
637 child.margin.main_axis_sum(constants.dir)
638 + if child.frozen { child.target_size.main(constants.dir) } else { child.flex_basis }
639 })
640 .sum();
641
642 let mut unfrozen: Vec<&mut FlexItem> = line.items.iter_mut().filter(|child| !child.frozen).collect();
643
644 let (sum_flex_grow, sum_flex_shrink): (f32, f32) =
645 unfrozen.iter().fold((0.0, 0.0), |(flex_grow, flex_shrink), item| {
646 let style = &self.nodes[item.node].style;
647 (flex_grow + style.flex_grow, flex_shrink + style.flex_shrink)
648 });
649
650 let free_space = if growing && sum_flex_grow < 1.0 {
651 (initial_free_space * sum_flex_grow)
652 .maybe_min(constants.node_inner_size.main(constants.dir).maybe_sub(used_space))
653 } else if shrinking && sum_flex_shrink < 1.0 {
654 (initial_free_space * sum_flex_shrink)
655 .maybe_max(constants.node_inner_size.main(constants.dir).maybe_sub(used_space))
656 } else {
657 (constants.node_inner_size.main(constants.dir).maybe_sub(used_space)).unwrap_or(0.0)
658 };
659
660 // c. Distribute free space proportional to the flex factors.
661 // - If the remaining free space is zero
662 // Do Nothing
663 // - If using the flex grow factor
664 // Find the ratio of the item’s flex grow factor to the sum of the
665 // flex grow factors of all unfrozen items on the line. Set the item’s
666 // target main size to its flex base size plus a fraction of the remaining
667 // free space proportional to the ratio.
668 // - If using the flex shrink factor
669 // For every unfrozen item on the line, multiply its flex shrink factor by
670 // its inner flex base size, and note this as its scaled flex shrink factor.
671 // Find the ratio of the item’s scaled flex shrink factor to the sum of the
672 // scaled flex shrink factors of all unfrozen items on the line. Set the item’s
673 // target main size to its flex base size minus a fraction of the absolute value
674 // of the remaining free space proportional to the ratio. Note this may result
675 // in a negative inner main size; it will be corrected in the next step.
676 // - Otherwise
677 // Do Nothing
678
679 if free_space.is_normal() {
680 if growing && sum_flex_grow > 0.0 {
681 for child in &mut unfrozen {
682 child.target_size.set_main(
683 constants.dir,
684 child.flex_basis + free_space * (self.nodes[child.node].style.flex_grow / sum_flex_grow),
685 );
686 }
687 } else if shrinking && sum_flex_shrink > 0.0 {
688 let sum_scaled_shrink_factor: f32 = unfrozen
689 .iter()
690 .map(|child| child.inner_flex_basis * self.nodes[child.node].style.flex_shrink)
691 .sum();
692
693 if sum_scaled_shrink_factor > 0.0 {
694 for child in &mut unfrozen {
695 let scaled_shrink_factor =
696 child.inner_flex_basis * self.nodes[child.node].style.flex_shrink;
697 child.target_size.set_main(
698 constants.dir,
699 child.flex_basis + free_space * (scaled_shrink_factor / sum_scaled_shrink_factor),
700 )
701 }
702 }
703 }
704 }
705
706 // d. Fix min/max violations. Clamp each non-frozen item’s target main size by its
707 // used min and max main sizes and floor its content-box size at zero. If the
708 // item’s target main size was made smaller by this, it’s a max violation.
709 // If the item’s target main size was made larger by this, it’s a min violation.
710
711 let total_violation = unfrozen.iter_mut().fold(0.0, |acc, child| -> f32 {
712 // TODO - not really spec abiding but needs to be done somewhere. probably somewhere else though.
713 // The following logic was developed not from the spec but by trial and error looking into how
714 // webkit handled various scenarios. Can probably be solved better by passing in
715 // min-content max-content constraints from the top. Need to figure out correct thing to do here as
716 // just piling on more conditionals.
717 let min_main = if constants.is_row && self.nodes[child.node].measure.is_none() {
718 self.compute_preliminary(child.node, Size::undefined(), available_space, false, false)
719 .width
720 .maybe_min(child.size.width)
721 .maybe_max(child.min_size.width)
722 .into()
723 } else {
724 child.min_size.main(constants.dir)
725 };
726
727 let max_main = child.max_size.main(constants.dir);
728 let clamped = child.target_size.main(constants.dir).maybe_min(max_main).maybe_max(min_main).max(0.0);
729 child.violation = clamped - child.target_size.main(constants.dir);
730 child.target_size.set_main(constants.dir, clamped);
731 child.outer_target_size.set_main(
732 constants.dir,
733 child.target_size.main(constants.dir) + child.margin.main_axis_sum(constants.dir),
734 );
735
736 acc + child.violation
737 });
738
739 // e. Freeze over-flexed items. The total violation is the sum of the adjustments
740 // from the previous step ∑(clamped size - unclamped size). If the total violation is:
741 // - Zero
742 // Freeze all items.
743 // - Positive
744 // Freeze all the items with min violations.
745 // - Negative
746 // Freeze all the items with max violations.
747
748 for child in &mut unfrozen {
749 match total_violation {
750 v if v > 0.0 => child.frozen = child.violation > 0.0,
751 v if v < 0.0 => child.frozen = child.violation < 0.0,
752 _ => child.frozen = true,
753 }
754 }
755
756 // f. Return to the start of this loop.
757 }
758 }
759
760 /// Determine the hypothetical cross size of each item.
761 ///
762 /// # [9.4. Cross Size Determination](https://www.w3.org/TR/css-flexbox-1/#cross-sizing)
763 ///
764 /// - [**Determine the hypothetical cross size of each item**](https://www.w3.org/TR/css-flexbox-1/#algo-cross-item)
765 /// by performing layout with the used main size and the available space, treating auto as fit-content.
766 #[inline]
767 fn determine_hypothetical_cross_size(
768 &mut self,
769 line: &mut FlexLine,
770 constants: &AlgoConstants,
771 available_space: Size<Option<f32>>,
772 ) {
773 for child in line.items.iter_mut() {
774 let child_cross = child
775 .size
776 .cross(constants.dir)
777 .maybe_max(child.min_size.cross(constants.dir))
778 .maybe_min(child.max_size.cross(constants.dir));
779
780 child.hypothetical_inner_size.set_cross(
781 constants.dir,
782 self.compute_preliminary(
783 child.node,
784 Size {
785 width: if constants.is_row { child.target_size.width.into() } else { child_cross },
786 height: if constants.is_row { child_cross } else { child.target_size.height.into() },
787 },
788 Size {
789 width: if constants.is_row {
790 constants.container_size.main(constants.dir).into()
791 } else {
792 available_space.width
793 },
794 height: if constants.is_row {
795 available_space.height
796 } else {
797 constants.container_size.main(constants.dir).into()
798 },
799 },
800 false,
801 false,
802 )
803 .cross(constants.dir)
804 .maybe_max(child.min_size.cross(constants.dir))
805 .maybe_min(child.max_size.cross(constants.dir)),
806 );
807
808 child.hypothetical_outer_size.set_cross(
809 constants.dir,
810 child.hypothetical_inner_size.cross(constants.dir) + child.margin.cross_axis_sum(constants.dir),
811 );
812 }
813 }
814
815 /// Calculate the base lines of the children.
816 #[inline]
817 fn calculate_children_base_lines(
818 &mut self,
819 node: NodeId,
820 node_size: Size<Option<f32>>,
821 flex_lines: &mut [FlexLine],
822 constants: &AlgoConstants,
823 ) {
824 /// Recursively calculates the baseline for children
825 fn calc_baseline(db: &Forest, node: NodeId, layout: &Layout) -> f32 {
826 if db.children[node].is_empty() {
827 layout.size.height
828 } else {
829 let child = db.children[node][0];
830 calc_baseline(db, child, &db.nodes[child].layout)
831 }
832 }
833
834 for line in flex_lines {
835 for child in line.items.iter_mut() {
836 let preliminary_size = self.compute_preliminary(
837 child.node,
838 Size {
839 width: if constants.is_row {
840 child.target_size.width.into()
841 } else {
842 child.hypothetical_inner_size.width.into()
843 },
844 height: if constants.is_row {
845 child.hypothetical_inner_size.height.into()
846 } else {
847 child.target_size.height.into()
848 },
849 },
850 Size {
851 width: if constants.is_row { constants.container_size.width.into() } else { node_size.width },
852 height: if constants.is_row {
853 node_size.height
854 } else {
855 constants.container_size.height.into()
856 },
857 },
858 true,
859 false,
860 );
861
862 child.baseline = calc_baseline(
863 self,
864 child.node,
865 &Layout {
866 order: self.children[node].iter().position(|n| *n == child.node).unwrap() as u32,
867 size: preliminary_size,
868 location: Point::ZERO,
869 },
870 );
871 }
872 }
873 }
874
875 /// Calculate the cross size of each flex line.
876 ///
877 /// # [9.4. Cross Size Determination](https://www.w3.org/TR/css-flexbox-1/#cross-sizing)
878 ///
879 /// - [**Calculate the cross size of each flex line**](https://www.w3.org/TR/css-flexbox-1/#algo-cross-line).
880 ///
881 /// 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.
882 ///
883 /// Otherwise, for each flex line:
884 ///
885 /// 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.
886 /// Find the largest of the distances between each item’s baseline and its hypothetical outer cross-start edge,
887 /// and the largest of the distances between each item’s baseline and its hypothetical outer cross-end edge, and sum these two values.
888 ///
889 /// 2. Among all the items not collected by the previous step, find the largest outer hypothetical cross size.
890 ///
891 /// 3. The used cross-size of the flex line is the largest of the numbers found in the previous two steps and zero.
892 ///
893 /// 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.
894 /// **Note that if CSS 2.1’s definition of min/max-width/height applied more generally, this behavior would fall out automatically**.
895 #[inline]
896 fn calculate_cross_size(
897 &mut self,
898 flex_lines: &mut [FlexLine],
899 node: NodeId,
900 node_size: Size<Option<f32>>,
901 constants: &AlgoConstants,
902 ) {
903 if flex_lines.len() == 1 && node_size.cross(constants.dir).is_some() {
904 flex_lines[0].cross_size =
905 (node_size.cross(constants.dir).maybe_sub(constants.padding_border.cross_axis_sum(constants.dir)))
906 .unwrap_or(0.0);
907 } else {
908 for line in flex_lines.iter_mut() {
909 // 1. Collect all the flex items whose inline-axis is parallel to the main-axis, whose
910 // align-self is baseline, and whose cross-axis margins are both non-auto. Find the
911 // largest of the distances between each item’s baseline and its hypothetical outer
912 // cross-start edge, and the largest of the distances between each item’s baseline
913 // and its hypothetical outer cross-end edge, and sum these two values.
914
915 // 2. Among all the items not collected by the previous step, find the largest
916 // outer hypothetical cross size.
917
918 // 3. The used cross-size of the flex line is the largest of the numbers found in the
919 // previous two steps and zero.
920
921 let max_baseline: f32 = line.items.iter().map(|child| child.baseline).fold(0.0, |acc, x| acc.max(x));
922 line.cross_size = line
923 .items
924 .iter()
925 .map(|child| {
926 let child_style = &self.nodes[child.node].style;
927 if child_style.align_self(&self.nodes[node].style) == AlignSelf::Baseline
928 && child_style.cross_margin_start(constants.dir) != Dimension::Auto
929 && child_style.cross_margin_end(constants.dir) != Dimension::Auto
930 && child_style.cross_size(constants.dir) == Dimension::Auto
931 {
932 max_baseline - child.baseline + child.hypothetical_outer_size.cross(constants.dir)
933 } else {
934 child.hypothetical_outer_size.cross(constants.dir)
935 }
936 })
937 .fold(0.0, |acc, x| acc.max(x));
938 }
939 }
940 }
941
942 /// Handle 'align-content: stretch'.
943 ///
944 /// # [9.4. Cross Size Determination](https://www.w3.org/TR/css-flexbox-1/#cross-sizing)
945 ///
946 /// - [**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,
947 /// and the sum of the flex lines' cross sizes is less than the flex container’s inner cross size,
948 /// 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.
949 #[inline]
950 fn handle_align_content_stretch(
951 &mut self,
952 flex_lines: &mut [FlexLine],
953 node: NodeId,
954 node_size: Size<Option<f32>>,
955 constants: &AlgoConstants,
956 ) {
957 if self.nodes[node].style.align_content == AlignContent::Stretch && node_size.cross(constants.dir).is_some() {
958 let total_cross: f32 = flex_lines.iter().map(|line| line.cross_size).sum();
959 let inner_cross =
960 (node_size.cross(constants.dir).maybe_sub(constants.padding_border.cross_axis_sum(constants.dir)))
961 .unwrap_or(0.0);
962
963 if total_cross < inner_cross {
964 let remaining = inner_cross - total_cross;
965 let addition = remaining / flex_lines.len() as f32;
966 flex_lines.iter_mut().for_each(|line| line.cross_size += addition);
967 }
968 }
969 }
970
971 /// Determine the used cross size of each flex item.
972 ///
973 /// # [9.4. Cross Size Determination](https://www.w3.org/TR/css-flexbox-1/#cross-sizing)
974 ///
975 /// - [**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,
976 /// 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.
977 /// Otherwise, the used cross size is the item’s hypothetical cross size.
978 ///
979 /// 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.
980 ///
981 /// **Note that this step does not affect the main size of the flex item, even if it has an intrinsic aspect ratio**.
982 #[inline]
983 fn determine_used_cross_size(&mut self, flex_lines: &mut [FlexLine], node: NodeId, constants: &AlgoConstants) {
984 for line in flex_lines {
985 let line_cross_size = line.cross_size;
986
987 for child in line.items.iter_mut() {
988 let child_style = &self.nodes[child.node].style;
989 child.target_size.set_cross(
990 constants.dir,
991 if child_style.align_self(&self.nodes[node].style) == AlignSelf::Stretch
992 && child_style.cross_margin_start(constants.dir) != Dimension::Auto
993 && child_style.cross_margin_end(constants.dir) != Dimension::Auto
994 && child_style.cross_size(constants.dir) == Dimension::Auto
995 {
996 (line_cross_size - child.margin.cross_axis_sum(constants.dir))
997 .maybe_max(child.min_size.cross(constants.dir))
998 .maybe_min(child.max_size.cross(constants.dir))
999 } else {
1000 child.hypothetical_inner_size.cross(constants.dir)
1001 },
1002 );
1003
1004 child.outer_target_size.set_cross(
1005 constants.dir,
1006 child.target_size.cross(constants.dir) + child.margin.cross_axis_sum(constants.dir),
1007 );
1008 }
1009 }
1010 }
1011
1012 /// Distribute any remaining free space.
1013 ///
1014 /// # [9.5. Main-Axis Alignment](https://www.w3.org/TR/css-flexbox-1/#main-alignment)
1015 ///
1016 /// - [**Distribute any remaining free space**](https://www.w3.org/TR/css-flexbox-1/#algo-main-align). For each flex line:
1017 ///
1018 /// 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.
1019 /// Otherwise, set all `auto` margins to zero.
1020 ///
1021 /// 2. Align the items along the main-axis per `justify-content`.
1022 #[inline]
1023 fn distribute_remaining_free_space(
1024 &mut self,
1025 flex_lines: &mut [FlexLine],
1026 node: NodeId,
1027 constants: &AlgoConstants,
1028 ) {
1029 for line in flex_lines {
1030 let used_space: f32 = line.items.iter().map(|child| child.outer_target_size.main(constants.dir)).sum();
1031 let free_space = constants.inner_container_size.main(constants.dir) - used_space;
1032 let mut num_auto_margins = 0;
1033
1034 for child in line.items.iter_mut() {
1035 let child_style = &self.nodes[child.node].style;
1036 if child_style.main_margin_start(constants.dir) == Dimension::Auto {
1037 num_auto_margins += 1;
1038 }
1039 if child_style.main_margin_end(constants.dir) == Dimension::Auto {
1040 num_auto_margins += 1;
1041 }
1042 }
1043
1044 if free_space > 0.0 && num_auto_margins > 0 {
1045 let margin = free_space / num_auto_margins as f32;
1046
1047 for child in line.items.iter_mut() {
1048 let child_style = &self.nodes[child.node].style;
1049 if child_style.main_margin_start(constants.dir) == Dimension::Auto {
1050 if constants.is_row {
1051 child.margin.start = margin;
1052 } else {
1053 child.margin.top = margin;
1054 }
1055 }
1056 if child_style.main_margin_end(constants.dir) == Dimension::Auto {
1057 if constants.is_row {
1058 child.margin.end = margin;
1059 } else {
1060 child.margin.bottom = margin;
1061 }
1062 }
1063 }
1064 } else {
1065 let num_items = line.items.len();
1066 let layout_reverse = constants.dir.is_reverse();
1067
1068 let justify_item = |(i, child): (usize, &mut FlexItem)| {
1069 let is_first = i == 0;
1070
1071 child.offset_main = match self.nodes[node].style.justify_content {
1072 JustifyContent::FlexStart => {
1073 if layout_reverse && is_first {
1074 free_space
1075 } else {
1076 0.0
1077 }
1078 }
1079 JustifyContent::Center => {
1080 if is_first {
1081 free_space / 2.0
1082 } else {
1083 0.0
1084 }
1085 }
1086 JustifyContent::FlexEnd => {
1087 if is_first && !layout_reverse {
1088 free_space
1089 } else {
1090 0.0
1091 }
1092 }
1093 JustifyContent::SpaceBetween => {
1094 if is_first {
1095 0.0
1096 } else {
1097 free_space / (num_items - 1) as f32
1098 }
1099 }
1100 JustifyContent::SpaceAround => {
1101 if is_first {
1102 (free_space / num_items as f32) / 2.0
1103 } else {
1104 free_space / num_items as f32
1105 }
1106 }
1107 JustifyContent::SpaceEvenly => free_space / (num_items + 1) as f32,
1108 };
1109 };
1110
1111 if layout_reverse {
1112 line.items.iter_mut().rev().enumerate().for_each(justify_item);
1113 } else {
1114 line.items.iter_mut().enumerate().for_each(justify_item);
1115 }
1116 }
1117 }
1118 }
1119
1120 /// Resolve cross-axis `auto` margins.
1121 ///
1122 /// # [9.6. Cross-Axis Alignment](https://www.w3.org/TR/css-flexbox-1/#cross-alignment)
1123 ///
1124 /// - [**Resolve cross-axis `auto` margins**](https://www.w3.org/TR/css-flexbox-1/#algo-cross-margins).
1125 /// If a flex item has auto cross-axis margins:
1126 ///
1127 /// - If its outer cross size (treating those auto margins as zero) is less than the cross size of its flex line,
1128 /// distribute the difference in those sizes equally to the auto margins.
1129 ///
1130 /// - Otherwise, if the block-start or inline-start margin (whichever is in the cross axis) is auto, set it to zero.
1131 /// Set the opposite margin so that the outer cross size of the item equals the cross size of its flex line.
1132 #[inline]
1133 fn resolve_cross_axis_auto_margins(
1134 &mut self,
1135 flex_lines: &mut [FlexLine],
1136 node: NodeId,
1137 constants: &AlgoConstants,
1138 ) {
1139 for line in flex_lines {
1140 let line_cross_size = line.cross_size;
1141 let max_baseline: f32 = line.items.iter_mut().map(|child| child.baseline).fold(0.0, |acc, x| acc.max(x));
1142
1143 for child in line.items.iter_mut() {
1144 let free_space = line_cross_size - child.outer_target_size.cross(constants.dir);
1145 let child_style = &self.nodes[child.node].style;
1146
1147 if child_style.cross_margin_start(constants.dir) == Dimension::Auto
1148 && child_style.cross_margin_end(constants.dir) == Dimension::Auto
1149 {
1150 if constants.is_row {
1151 child.margin.top = free_space / 2.0;
1152 child.margin.bottom = free_space / 2.0;
1153 } else {
1154 child.margin.start = free_space / 2.0;
1155 child.margin.end = free_space / 2.0;
1156 }
1157 } else if child_style.cross_margin_start(constants.dir) == Dimension::Auto {
1158 if constants.is_row {
1159 child.margin.top = free_space;
1160 } else {
1161 child.margin.start = free_space;
1162 }
1163 } else if child_style.cross_margin_end(constants.dir) == Dimension::Auto {
1164 if constants.is_row {
1165 child.margin.bottom = free_space;
1166 } else {
1167 child.margin.end = free_space;
1168 }
1169 } else {
1170 // 14. Align all flex items along the cross-axis.
1171 child.offset_cross = self.align_flex_items_along_cross_axis(
1172 node,
1173 child,
1174 child_style,
1175 free_space,
1176 max_baseline,
1177 constants,
1178 );
1179 }
1180 }
1181 }
1182 }
1183
1184 /// Align all flex items along the cross-axis.
1185 ///
1186 /// # [9.6. Cross-Axis Alignment](https://www.w3.org/TR/css-flexbox-1/#cross-alignment)
1187 ///
1188 /// - [**Align all flex items along the cross-axis**](https://www.w3.org/TR/css-flexbox-1/#algo-cross-align) per `align-self`,
1189 /// if neither of the item's cross-axis margins are `auto`.
1190 #[inline]
1191 fn align_flex_items_along_cross_axis(
1192 &self,
1193 node: NodeId,
1194 child: &mut FlexItem,
1195 child_style: &FlexboxLayout,
1196 free_space: f32,
1197 max_baseline: f32,
1198 constants: &AlgoConstants,
1199 ) -> f32 {
1200 match child_style.align_self(&self.nodes[node].style) {
1201 AlignSelf::Auto => unreachable!(),
1202 AlignSelf::FlexStart => {
1203 if constants.is_wrap_reverse {
1204 free_space
1205 } else {
1206 0.0
1207 }
1208 }
1209 AlignSelf::FlexEnd => {
1210 if constants.is_wrap_reverse {
1211 0.0
1212 } else {
1213 free_space
1214 }
1215 }
1216 AlignSelf::Center => free_space / 2.0,
1217 AlignSelf::Baseline => {
1218 if constants.is_row {
1219 max_baseline - child.baseline
1220 } else {
1221 // baseline alignment only makes sense if the constants.direction is row
1222 // we treat it as flex-start alignment in columns.
1223 if constants.is_wrap_reverse {
1224 free_space
1225 } else {
1226 0.0
1227 }
1228 }
1229 }
1230 AlignSelf::Stretch => {
1231 if constants.is_wrap_reverse {
1232 free_space
1233 } else {
1234 0.0
1235 }
1236 }
1237 }
1238 }
1239
1240 /// Determine the flex container’s used cross size.
1241 ///
1242 /// # [9.6. Cross-Axis Alignment](https://www.w3.org/TR/css-flexbox-1/#cross-alignment)
1243 ///
1244 /// - [**Determine the flex container’s used cross size**](https://www.w3.org/TR/css-flexbox-1/#algo-cross-container):
1245 ///
1246 /// - If the cross size property is a definite size, use that, clamped by the used min and max cross sizes of the flex container.
1247 ///
1248 /// - Otherwise, use the sum of the flex lines' cross sizes, clamped by the used min and max cross sizes of the flex container.
1249 #[inline]
1250 #[must_use]
1251 fn determine_container_cross_size(
1252 flex_lines: &mut [FlexLine],
1253 node_size: Size<Option<f32>>,
1254 constants: &mut AlgoConstants,
1255 ) -> f32 {
1256 let total_cross_size: f32 = flex_lines.iter().map(|line| line.cross_size).sum();
1257
1258 constants.container_size.set_cross(
1259 constants.dir,
1260 node_size
1261 .cross(constants.dir)
1262 .unwrap_or(total_cross_size + constants.padding_border.cross_axis_sum(constants.dir)),
1263 );
1264
1265 constants.inner_container_size.set_cross(
1266 constants.dir,
1267 constants.container_size.cross(constants.dir) - constants.padding_border.cross_axis_sum(constants.dir),
1268 );
1269
1270 total_cross_size
1271 }
1272
1273 /// Align all flex lines per `align-content`.
1274 ///
1275 /// # [9.6. Cross-Axis Alignment](https://www.w3.org/TR/css-flexbox-1/#cross-alignment)
1276 ///
1277 /// - [**Align all flex lines**](https://www.w3.org/TR/css-flexbox-1/#algo-line-align) per `align-content`.
1278 #[inline]
1279 fn align_flex_lines_per_align_content(
1280 &self,
1281 flex_lines: &mut [FlexLine],
1282 node: NodeId,
1283 constants: &AlgoConstants,
1284 total_cross_size: f32,
1285 ) {
1286 let free_space = constants.inner_container_size.cross(constants.dir) - total_cross_size;
1287 let num_lines = flex_lines.len();
1288
1289 let align_line = |(i, line): (usize, &mut FlexLine)| {
1290 let is_first = i == 0;
1291
1292 line.offset_cross = match self.nodes[node].style.align_content {
1293 AlignContent::FlexStart => {
1294 if is_first && constants.is_wrap_reverse {
1295 free_space
1296 } else {
1297 0.0
1298 }
1299 }
1300 AlignContent::FlexEnd => {
1301 if is_first && !constants.is_wrap_reverse {
1302 free_space
1303 } else {
1304 0.0
1305 }
1306 }
1307 AlignContent::Center => {
1308 if is_first {
1309 free_space / 2.0
1310 } else {
1311 0.0
1312 }
1313 }
1314 AlignContent::Stretch => 0.0,
1315 AlignContent::SpaceBetween => {
1316 if is_first {
1317 0.0
1318 } else {
1319 free_space / (num_lines - 1) as f32
1320 }
1321 }
1322 AlignContent::SpaceAround => {
1323 if is_first {
1324 (free_space / num_lines as f32) / 2.0
1325 } else {
1326 free_space / num_lines as f32
1327 }
1328 }
1329 };
1330 };
1331
1332 if constants.is_wrap_reverse {
1333 flex_lines.iter_mut().rev().enumerate().for_each(align_line);
1334 } else {
1335 flex_lines.iter_mut().enumerate().for_each(align_line);
1336 }
1337 }
1338
1339 /// Do a final layout pass and collect the resulting layouts.
1340 #[inline]
1341 fn final_layout_pass(&mut self, node: NodeId, flex_lines: &mut [FlexLine], constants: &AlgoConstants) {
1342 let mut total_offset_cross = constants.padding_border.cross_start(constants.dir);
1343
1344 let layout_line = |line: &mut FlexLine| {
1345 let mut total_offset_main = constants.padding_border.main_start(constants.dir);
1346 let line_offset_cross = line.offset_cross;
1347
1348 let layout_item = |child: &mut FlexItem| {
1349 let preliminary_size = self.compute_preliminary(
1350 child.node,
1351 child.target_size.map(|s| s.into()),
1352 constants.container_size.map(|s| s.into()),
1353 true,
1354 false,
1355 );
1356
1357 let offset_main = total_offset_main
1358 + child.offset_main
1359 + child.margin.main_start(constants.dir)
1360 + (child.position.main_start(constants.dir).unwrap_or(0.0)
1361 - child.position.main_end(constants.dir).unwrap_or(0.0));
1362
1363 let offset_cross = total_offset_cross
1364 + child.offset_cross
1365 + line_offset_cross
1366 + child.margin.cross_start(constants.dir)
1367 + (child.position.cross_start(constants.dir).unwrap_or(0.0)
1368 - child.position.cross_end(constants.dir).unwrap_or(0.0));
1369
1370 self.nodes[child.node].layout = Layout {
1371 order: self.children[node].iter().position(|n| *n == child.node).unwrap() as u32,
1372 size: preliminary_size,
1373 location: Point {
1374 x: if constants.is_row { offset_main } else { offset_cross },
1375 y: if constants.is_column { offset_main } else { offset_cross },
1376 },
1377 };
1378
1379 total_offset_main += child.offset_main
1380 + child.margin.main_axis_sum(constants.dir)
1381 + preliminary_size.main(constants.dir);
1382 };
1383
1384 if constants.dir.is_reverse() {
1385 line.items.iter_mut().rev().for_each(layout_item);
1386 } else {
1387 line.items.iter_mut().for_each(layout_item);
1388 }
1389
1390 total_offset_cross += line_offset_cross + line.cross_size;
1391 };
1392
1393 if constants.is_wrap_reverse {
1394 flex_lines.iter_mut().rev().for_each(layout_line);
1395 } else {
1396 flex_lines.iter_mut().for_each(layout_line);
1397 }
1398 }
1399
1400 /// Perform absolute layout on all absolutely positioned children.
1401 #[inline]
1402 fn perform_absolute_layout_on_absolute_children(&mut self, node: NodeId, constants: &AlgoConstants) {
1403 // TODO: remove number of Vec<_> generated
1404 let candidates = self.children[node]
1405 .iter()
1406 .cloned()
1407 .enumerate()
1408 .filter(|(_, child)| self.nodes[*child].style.position_type == PositionType::Absolute)
1409 .collect::<Vec<_>>();
1410
1411 for (order, child) in candidates {
1412 let container_width = constants.container_size.width.into();
1413 let container_height = constants.container_size.height.into();
1414
1415 let child_style = self.nodes[child].style;
1416
1417 // X-axis
1418 let child_position_start = child_style.position.start.maybe_resolve(container_width);
1419 let child_margin_start = child_style.margin.start.maybe_resolve(container_width);
1420 let start = child_position_start.maybe_add(child_margin_start);
1421
1422 let child_position_end = child_style.position.end.maybe_resolve(container_width);
1423 let child_margin_end = child_style.margin.end.maybe_resolve(container_width);
1424 let end = child_position_end.maybe_add(child_margin_end);
1425
1426 // Y-axis
1427 let child_position_top = child_style.position.top.maybe_resolve(container_height);
1428 let child_margin_top = child_style.margin.top.maybe_resolve(container_height);
1429 let top = child_position_top.maybe_add(child_margin_top);
1430
1431 let child_position_bottom = child_style.position.bottom.maybe_resolve(container_height);
1432 let child_margin_bottom = child_style.margin.bottom.maybe_resolve(container_height);
1433 let bottom = child_position_bottom.maybe_add(child_margin_bottom);
1434
1435 let (start_main, end_main) = if constants.is_row { (start, end) } else { (top, bottom) };
1436 let (start_cross, end_cross) = if constants.is_row { (top, bottom) } else { (start, end) };
1437
1438 let mut width = child_style
1439 .size
1440 .width
1441 .maybe_resolve(container_width)
1442 .maybe_max(child_style.min_size.width.maybe_resolve(container_width))
1443 .maybe_min(child_style.max_size.width.maybe_resolve(container_width));
1444
1445 if width.is_none() && start.is_some() && end.is_some() {
1446 width = container_width.maybe_sub(start).maybe_sub(end);
1447 }
1448
1449 let mut height: Option<f32> = child_style
1450 .size
1451 .height
1452 .maybe_resolve(container_height)
1453 .maybe_max(child_style.min_size.height.maybe_resolve(container_height))
1454 .maybe_min(child_style.max_size.height.maybe_resolve(container_height));
1455
1456 if height.is_none() && top.is_some() && bottom.is_some() {
1457 height = container_height.maybe_sub(top).maybe_sub(bottom);
1458 }
1459
1460 let preliminary_size = self.compute_preliminary(
1461 child,
1462 Size { width, height },
1463 Size { width: container_width, height: container_height },
1464 true,
1465 false,
1466 );
1467
1468 let free_main_space = constants.container_size.main(constants.dir)
1469 - preliminary_size
1470 .main(constants.dir)
1471 .maybe_max(
1472 child_style
1473 .min_main_size(constants.dir)
1474 .maybe_resolve(constants.node_inner_size.main(constants.dir)),
1475 )
1476 .maybe_min(
1477 child_style
1478 .max_main_size(constants.dir)
1479 .maybe_resolve(constants.node_inner_size.main(constants.dir)),
1480 );
1481
1482 let free_cross_space = constants.container_size.cross(constants.dir)
1483 - preliminary_size
1484 .cross(constants.dir)
1485 .maybe_max(
1486 child_style
1487 .min_cross_size(constants.dir)
1488 .maybe_resolve(constants.node_inner_size.cross(constants.dir)),
1489 )
1490 .maybe_min(
1491 child_style
1492 .max_cross_size(constants.dir)
1493 .maybe_resolve(constants.node_inner_size.cross(constants.dir)),
1494 );
1495
1496 let offset_main = if start_main.is_some() {
1497 start_main.unwrap_or(0.0) + constants.border.main_start(constants.dir)
1498 } else if end_main.is_some() {
1499 free_main_space - end_main.unwrap_or(0.0) - constants.border.main_end(constants.dir)
1500 } else {
1501 match self.nodes[node].style.justify_content {
1502 JustifyContent::SpaceBetween | JustifyContent::FlexStart => {
1503 constants.padding_border.main_start(constants.dir)
1504 }
1505 JustifyContent::FlexEnd => free_main_space - constants.padding_border.main_end(constants.dir),
1506 JustifyContent::SpaceEvenly | JustifyContent::SpaceAround | JustifyContent::Center => {
1507 free_main_space / 2.0
1508 }
1509 }
1510 };
1511
1512 let offset_cross = if start_cross.is_some() {
1513 start_cross.unwrap_or(0.0) + constants.border.cross_start(constants.dir)
1514 } else if end_cross.is_some() {
1515 free_cross_space - end_cross.unwrap_or(0.0) - constants.border.cross_end(constants.dir)
1516 } else {
1517 match child_style.align_self(&self.nodes[node].style) {
1518 AlignSelf::Auto => unreachable!(),
1519 AlignSelf::FlexStart => {
1520 if constants.is_wrap_reverse {
1521 free_cross_space - constants.padding_border.cross_end(constants.dir)
1522 } else {
1523 constants.padding_border.cross_start(constants.dir)
1524 }
1525 }
1526 AlignSelf::FlexEnd => {
1527 if constants.is_wrap_reverse {
1528 constants.padding_border.cross_start(constants.dir)
1529 } else {
1530 free_cross_space - constants.padding_border.cross_end(constants.dir)
1531 }
1532 }
1533 AlignSelf::Center => free_cross_space / 2.0,
1534 AlignSelf::Baseline => free_cross_space / 2.0, // Treat as center for now until we have baseline support
1535 AlignSelf::Stretch => {
1536 if constants.is_wrap_reverse {
1537 free_cross_space - constants.padding_border.cross_end(constants.dir)
1538 } else {
1539 constants.padding_border.cross_start(constants.dir)
1540 }
1541 }
1542 }
1543 };
1544
1545 self.nodes[child].layout = Layout {
1546 order: order as u32,
1547 size: preliminary_size,
1548 location: Point {
1549 x: if constants.is_row { offset_main } else { offset_cross },
1550 y: if constants.is_column { offset_main } else { offset_cross },
1551 },
1552 };
1553 }
1554 }
1555
1556 /// Compute a preliminary size for an item
1557 fn compute_preliminary(
1558 &mut self,
1559 node: NodeId,
1560 node_size: Size<Option<f32>>,
1561 parent_size: Size<Option<f32>>,
1562 perform_layout: bool,
1563 main_size: bool,
1564 ) -> Size<f32> {
1565 self.nodes[node].is_dirty = false;
1566
1567 // First we check if we have a result for the given input
1568 if let Some(cached_size) = self.compute_from_cache(node, node_size, parent_size, perform_layout, main_size) {
1569 return cached_size;
1570 }
1571
1572 // Define some general constants we will need for the remainder of the algorithm.
1573 let mut constants = Forest::compute_constants(&self.nodes[node], node_size, parent_size);
1574
1575 // If this is a leaf node we can skip a lot of this function in some cases
1576 if self.children[node].is_empty() {
1577 if node_size.width.is_some() && node_size.height.is_some() {
1578 return node_size.map(|s| s.unwrap_or(0.0));
1579 }
1580
1581 if let Some(ref measure) = self.nodes[node].measure {
1582 let converted_size = match measure {
1583 MeasureFunc::Raw(measure) => measure(node_size),
1584 #[cfg(any(feature = "std", feature = "alloc"))]
1585 MeasureFunc::Boxed(measure) => measure(node_size),
1586 };
1587 *self.cache(node, main_size) =
1588 Some(Cache { node_size, parent_size, perform_layout, size: converted_size });
1589 return converted_size;
1590 }
1591
1592 return Size {
1593 width: node_size.width.unwrap_or(0.0) + constants.padding_border.horizontal_axis_sum(),
1594 height: node_size.height.unwrap_or(0.0) + constants.padding_border.vertical_axis_sum(),
1595 };
1596 }
1597
1598 // 9. Flex Layout Algorithm
1599
1600 // 9.1. Initial Setup
1601
1602 // 1. Generate anonymous flex items as described in §4 Flex Items.
1603 let mut flex_items = self.generate_anonymous_flex_items(node, &constants);
1604
1605 // 9.2. Line Length Determination
1606
1607 // 2. Determine the available main and cross space for the flex items.
1608 let available_space = Self::determine_available_space(node_size, parent_size, &constants);
1609
1610 let has_baseline_child = flex_items
1611 .iter()
1612 .any(|child| self.nodes[child.node].style.align_self(&self.nodes[node].style) == AlignSelf::Baseline);
1613
1614 // 3. Determine the flex base size and hypothetical main size of each item.
1615 self.determine_flex_base_size(node, node_size, &constants, available_space, &mut flex_items);
1616
1617 // TODO: Add step 4 according to spec: https://www.w3.org/TR/css-flexbox-1/#algo-main-container
1618 // 9.3. Main Size Determination
1619
1620 // 5. Collect flex items into flex lines.
1621 let mut flex_lines = self.collect_flex_lines(node, &constants, available_space, &mut flex_items);
1622
1623 // 6. Resolve the flexible lengths of all the flex items to find their used main size.
1624 for line in &mut flex_lines {
1625 self.resolve_flexible_lengths(line, &constants, available_space);
1626 }
1627
1628 // TODO: Cleanup and make according to spec
1629 // Not part of the spec from what i can see but seems correct
1630 constants.container_size.set_main(
1631 constants.dir,
1632 node_size.main(constants.dir).unwrap_or({
1633 let longest_line = flex_lines.iter().fold(f32::MIN, |acc, line| {
1634 let length: f32 = line.items.iter().map(|item| item.outer_target_size.main(constants.dir)).sum();
1635 acc.max(length)
1636 });
1637
1638 let size = longest_line + constants.padding_border.main_axis_sum(constants.dir);
1639 match available_space.main(constants.dir) {
1640 Some(val) if flex_lines.len() > 1 && size < val => val,
1641 _ => size,
1642 }
1643 }),
1644 );
1645
1646 constants.inner_container_size.set_main(
1647 constants.dir,
1648 constants.container_size.main(constants.dir) - constants.padding_border.main_axis_sum(constants.dir),
1649 );
1650
1651 // 9.4. Cross Size Determination
1652
1653 // 7. Determine the hypothetical cross size of each item.
1654 for line in &mut flex_lines {
1655 self.determine_hypothetical_cross_size(line, &constants, available_space);
1656 }
1657
1658 // TODO - probably should move this somewhere else as it doesn't make a ton of sense here but we need it below
1659 // TODO - This is expensive and should only be done if we really require a baseline. aka, make it lazy
1660 if has_baseline_child {
1661 self.calculate_children_base_lines(node, node_size, &mut flex_lines, &constants);
1662 }
1663
1664 // 8. Calculate the cross size of each flex line.
1665 self.calculate_cross_size(&mut flex_lines, node, node_size, &constants);
1666
1667 // 9. Handle 'align-content: stretch'.
1668 self.handle_align_content_stretch(&mut flex_lines, node, node_size, &constants);
1669
1670 // 10. Collapse visibility:collapse items. If any flex items have visibility: collapse,
1671 // note the cross size of the line they’re in as the item’s strut size, and restart
1672 // layout from the beginning.
1673 //
1674 // In this second layout round, when collecting items into lines, treat the collapsed
1675 // items as having zero main size. For the rest of the algorithm following that step,
1676 // ignore the collapsed items entirely (as if they were display:none) except that after
1677 // calculating the cross size of the lines, if any line’s cross size is less than the
1678 // largest strut size among all the collapsed items in the line, set its cross size to
1679 // that strut size.
1680 //
1681 // Skip this step in the second layout round.
1682
1683 // TODO implement once (if ever) we support visibility:collapse
1684
1685 // 11. Determine the used cross size of each flex item.
1686 self.determine_used_cross_size(&mut flex_lines, node, &constants);
1687
1688 // 9.5. Main-Axis Alignment
1689
1690 // 12. Distribute any remaining free space.
1691 self.distribute_remaining_free_space(&mut flex_lines, node, &constants);
1692
1693 // 9.6. Cross-Axis Alignment
1694
1695 // 13. Resolve cross-axis auto margins (also includes 14).
1696 self.resolve_cross_axis_auto_margins(&mut flex_lines, node, &constants);
1697
1698 // 15. Determine the flex container’s used cross size.
1699 let total_cross_size = Self::determine_container_cross_size(&mut flex_lines, node_size, &mut constants);
1700
1701 // We have the container size.
1702 // If our caller does not care about performing layout we are done now.
1703 if !perform_layout {
1704 let container_size = constants.container_size;
1705 *self.cache(node, main_size) = Some(Cache { node_size, parent_size, perform_layout, size: container_size });
1706 return container_size;
1707 }
1708
1709 // 16. Align all flex lines per align-content.
1710 self.align_flex_lines_per_align_content(&mut flex_lines, node, &constants, total_cross_size);
1711
1712 // Do a final layout pass and gather the resulting layouts
1713 self.final_layout_pass(node, &mut flex_lines, &constants);
1714
1715 // Before returning we perform absolute layout on all absolutely positioned children
1716 self.perform_absolute_layout_on_absolute_children(node, &constants);
1717
1718 /// Lay out all hidden nodes recursively
1719 ///
1720 /// Each hidden node has zero size and is placed at the origin
1721 fn hidden_layout(nodes: &mut [NodeData], children: &[ChildrenVec<NodeId>], node: NodeId, order: u32) {
1722 nodes[node].layout = Layout { order, size: Size::ZERO, location: Point::ZERO };
1723
1724 for (order, child) in children[node].iter().enumerate() {
1725 hidden_layout(nodes, children, *child, order as _);
1726 }
1727 }
1728
1729 for (order, child) in self.children[node].iter().enumerate() {
1730 if self.nodes[*child].style.display == Display::None {
1731 hidden_layout(&mut self.nodes, &self.children, *child, order as _);
1732 }
1733 }
1734
1735 let container_size = constants.container_size;
1736 *self.cache(node, main_size) = Some(Cache { node_size, parent_size, perform_layout, size: container_size });
1737
1738 container_size
1739 }
1740}
1741
1742#[cfg(test)]
1743mod tests {
1744 use crate::{
1745 forest::Forest,
1746 math::MaybeMath,
1747 prelude::{Rect, Size},
1748 resolve::ResolveOrDefault,
1749 style::{FlexWrap, FlexboxLayout},
1750 };
1751
1752 // Make sure we get correct constants
1753 #[test]
1754 fn correct_constants() {
1755 let mut forest = Forest::with_capacity(16);
1756
1757 let style = FlexboxLayout::default();
1758 let node_id = forest.new_leaf(style);
1759
1760 let node_size = Size::undefined();
1761 let parent_size = Size::undefined();
1762
1763 let constants = Forest::compute_constants(&forest.nodes[node_id], node_size, parent_size);
1764
1765 assert!(constants.dir == style.flex_direction);
1766 assert!(constants.is_row == style.flex_direction.is_row());
1767 assert!(constants.is_column == style.flex_direction.is_column());
1768 assert!(constants.is_wrap_reverse == (style.flex_wrap == FlexWrap::WrapReverse));
1769
1770 let margin = style.margin.resolve_or_default(parent_size);
1771 assert_eq!(constants.margin, margin);
1772
1773 let border = style.border.resolve_or_default(parent_size);
1774 assert_eq!(constants.border, border);
1775
1776 let padding = style.padding.resolve_or_default(parent_size);
1777
1778 // TODO: Replace with something less hardcoded?
1779 let padding_border = Rect {
1780 start: padding.start + border.start,
1781 end: padding.end + border.end,
1782 top: padding.top + border.top,
1783 bottom: padding.bottom + border.bottom,
1784 };
1785
1786 assert_eq!(constants.padding_border, padding_border);
1787
1788 // TODO: Replace with something less hardcoded?
1789 let inner_size = Size {
1790 width: node_size.width.maybe_sub(padding_border.horizontal_axis_sum()),
1791 height: node_size.height.maybe_sub(padding_border.vertical_axis_sum()),
1792 };
1793 assert_eq!(constants.node_inner_size, inner_size);
1794
1795 assert_eq!(constants.container_size, Size::ZERO);
1796 assert_eq!(constants.inner_container_size, Size::ZERO);
1797 }
1798}