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