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::flexbox::Number::{Defined, Undefined};
7use crate::forest::{Forest, NodeData};
8use crate::geometry::{Point, Rect, Size};
9use crate::layout::{Cache, Layout};
10use crate::node::{MeasureFunc, NodeId};
11use crate::number::{MinMax, OrElse};
12use crate::prelude::Number;
13use crate::style::{AlignContent, AlignSelf, Dimension, Display, FlexWrap, JustifyContent, PositionType};
14use crate::style::{FlexDirection, Style};
15use crate::sys::{abs, round, ChildrenVec, Vec};
16
17/// The computed results of a [`flexbox`](crate::flexbox) calculation
18#[derive(Debug, Clone)]
19pub struct ComputeResult {
20 /// The computed size
21 pub size: Size<f32>,
22}
23
24/// The intermediate results of a flexbox calculation for a single item
25struct FlexItem {
26 /// The identifier for the associated [`Node`](crate::node::Node)
27 node: NodeId,
28
29 /// The base size of this item
30 size: Size<Number>,
31 /// The minimum allowable size of this item
32 min_size: Size<Number>,
33 /// The maximum allowable size of this item
34 max_size: Size<Number>,
35
36 /// The final offset of this item
37 position: Rect<Number>,
38 /// The margin of this item
39 margin: Rect<f32>,
40 /// The padding of this item
41 padding: Rect<f32>,
42 /// The border of this item
43 border: Rect<f32>,
44
45 /// The default size of this item
46 flex_basis: f32,
47 /// The default size of this item, minus padding and border
48 inner_flex_basis: f32,
49 /// The amount by which this item has deviated from its target size
50 violation: f32,
51 /// Is the size of this item locked
52 frozen: bool,
53
54 /// The proposed inner size of this item
55 hypothetical_inner_size: Size<f32>,
56 /// The proposed outer size of this item
57 hypothetical_outer_size: Size<f32>,
58 /// The size that this item wants to be
59 target_size: Size<f32>,
60 /// The size that this item wants to be, plus any padding and border
61 outer_target_size: Size<f32>,
62
63 /// The position of the bottom edge of this item
64 baseline: f32,
65
66 /// A temporary values for holding offset in the main / cross direction.
67
68 /// A temporary value for the main offset
69 ///
70 /// Offset is the relative position from the item's natural flow position based on
71 /// relative position values, alignment, and justification. Does not include margin/padding/border.
72 offset_main: f32,
73 /// A temporary value for the cross offset
74 offset_cross: f32,
75}
76
77/// A line of [`FlexItem`] used for intermediate computation
78struct FlexLine<'a> {
79 /// The slice of items to
80 items: &'a mut [FlexItem],
81 /// The dimensions of the cross-axis
82 cross_size: f32,
83 /// The relative offset of the cross-axis
84 offset_cross: f32,
85}
86
87/// Values that can be cached during the flexbox algorithm
88struct AlgoConstants {
89 /// The direction of the current segment being layed out
90 dir: FlexDirection,
91 /// Is this segment a row
92 is_row: bool,
93 /// Is this segment a column
94 is_column: bool,
95 /// Is the wrap direction inverted
96 is_wrap_reverse: bool,
97
98 /// The margin of this section
99 margin: Rect<f32>,
100 /// The border of this section
101 border: Rect<f32>,
102 /// The padding of this section
103 padding_border: Rect<f32>,
104
105 /// The size of the internal node
106 node_inner_size: Size<Number>,
107 /// The size of the surrounding container
108 container_size: Size<f32>,
109 /// The size of the internal container
110 inner_container_size: Size<f32>,
111}
112
113impl Forest {
114 /// Computes the layout of this [`Forest`] according to the flexbox algorithm
115 pub(crate) fn compute(&mut self, root: NodeId, size: Size<Number>) {
116 let style = self.nodes[root].style;
117 let has_root_min_max = style.min_size.width.is_defined()
118 || style.min_size.height.is_defined()
119 || style.max_size.width.is_defined()
120 || style.max_size.height.is_defined();
121
122 let result = if has_root_min_max {
123 let first_pass = self.compute_preliminary(root, style.size.resolve(size), size, false, true);
124
125 self.compute_preliminary(
126 root,
127 Size {
128 width: first_pass
129 .size
130 .width
131 .maybe_max(style.min_size.width.resolve(size.width))
132 .maybe_min(style.max_size.width.resolve(size.width))
133 .into(),
134 height: first_pass
135 .size
136 .height
137 .maybe_max(style.min_size.height.resolve(size.height))
138 .maybe_min(style.max_size.height.resolve(size.height))
139 .into(),
140 },
141 size,
142 true,
143 true,
144 )
145 } else {
146 self.compute_preliminary(root, style.size.resolve(size), size, true, true)
147 };
148
149 self.nodes[root].layout = Layout { order: 0, size: result.size, location: Point::zero() };
150
151 Self::round_layout(&mut self.nodes, &self.children, root, 0.0, 0.0);
152 }
153
154 /// Rounds the calculated [`NodeData`] according to the spec
155 fn round_layout(nodes: &mut [NodeData], children: &[ChildrenVec<NodeId>], root: NodeId, abs_x: f32, abs_y: f32) {
156 let layout = &mut nodes[root].layout;
157 let abs_x = abs_x + layout.location.x;
158 let abs_y = abs_y + layout.location.y;
159
160 layout.location.x = round(layout.location.x);
161 layout.location.y = round(layout.location.y);
162
163 layout.size.width = round(abs_x + layout.size.width) - round(abs_x);
164 layout.size.height = round(abs_y + layout.size.height) - round(abs_y);
165
166 for child in &children[root] {
167 Self::round_layout(nodes, children, *child, abs_x, abs_y);
168 }
169 }
170
171 /// Saves intermediate results to a [`Cache`]
172 fn cache(&mut self, node: NodeId, main_size: bool) -> &mut Option<Cache> {
173 if main_size {
174 &mut self.nodes[node].main_size_layout_cache
175 } else {
176 &mut self.nodes[node].other_layout_cache
177 }
178 }
179
180 /// Try to get the computation result from the cache.
181 #[inline]
182 fn compute_from_cache(
183 &mut self,
184 node: NodeId,
185 node_size: Size<Number>,
186 parent_size: Size<Number>,
187 perform_layout: bool,
188 main_size: bool,
189 ) -> Option<ComputeResult> {
190 if let Some(ref cache) = self.cache(node, main_size) {
191 if cache.perform_layout || !perform_layout {
192 let width_compatible = if let Number::Defined(width) = node_size.width {
193 abs(width - cache.result.size.width) < f32::EPSILON
194 } else {
195 cache.node_size.width.is_undefined()
196 };
197
198 let height_compatible = if let Number::Defined(height) = node_size.height {
199 abs(height - cache.result.size.height) < f32::EPSILON
200 } else {
201 cache.node_size.height.is_undefined()
202 };
203
204 if width_compatible && height_compatible {
205 return Some(cache.result.clone());
206 }
207
208 if cache.node_size == node_size && cache.parent_size == parent_size {
209 return Some(cache.result.clone());
210 }
211 }
212 }
213
214 None
215 }
216
217 /// Compute constants that can be reused during the flexbox algorithm.
218 #[inline]
219 fn compute_constants(&self, node: NodeId, node_size: Size<Number>, parent_size: Size<Number>) -> AlgoConstants {
220 let dir = self.nodes[node].style.flex_direction;
221 let is_row = dir.is_row();
222 let is_column = dir.is_column();
223 let is_wrap_reverse = self.nodes[node].style.flex_wrap == FlexWrap::WrapReverse;
224
225 let margin = self.nodes[node].style.margin.map(|n| n.resolve(parent_size.width).or_else(0.0));
226 let padding = self.nodes[node].style.padding.map(|n| n.resolve(parent_size.width).or_else(0.0));
227 let border = self.nodes[node].style.border.map(|n| n.resolve(parent_size.width).or_else(0.0));
228
229 let padding_border = Rect {
230 start: padding.start + border.start,
231 end: padding.end + border.end,
232 top: padding.top + border.top,
233 bottom: padding.bottom + border.bottom,
234 };
235
236 let node_inner_size = Size {
237 width: node_size.width - padding_border.horizontal_axis_sum(),
238 height: node_size.height - padding_border.vertical_axis_sum(),
239 };
240
241 let container_size = Size::zero();
242 let inner_container_size = Size::zero();
243
244 AlgoConstants {
245 dir,
246 is_row,
247 is_column,
248 is_wrap_reverse,
249 margin,
250 border,
251 padding_border,
252 node_inner_size,
253 container_size,
254 inner_container_size,
255 }
256 }
257
258 /// Generate anonymous flex items.
259 ///
260 /// # [9.1. Initial Setup](https://www.w3.org/TR/css-flexbox-1/#box-manip)
261 ///
262 /// - [**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).
263 #[inline]
264 fn generate_anonymous_flex_items(&self, node: NodeId, constants: &AlgoConstants) -> Vec<FlexItem> {
265 self.children[node]
266 .iter()
267 .map(|child| (child, &self.nodes[*child].style))
268 .filter(|(_, style)| style.position_type != PositionType::Absolute)
269 .filter(|(_, style)| style.display != Display::None)
270 .map(|(child, child_style)| FlexItem {
271 node: *child,
272 size: child_style.size.resolve(constants.node_inner_size),
273 min_size: child_style.min_size.resolve(constants.node_inner_size),
274 max_size: child_style.max_size.resolve(constants.node_inner_size),
275
276 position: child_style.position.zip_size(constants.node_inner_size, |p, s| p.resolve(s)),
277 margin: child_style.margin.map(|m| m.resolve(constants.node_inner_size.width).or_else(0.0)),
278 padding: child_style.padding.map(|p| p.resolve(constants.node_inner_size.width).or_else(0.0)),
279 border: child_style.border.map(|b| b.resolve(constants.node_inner_size.width).or_else(0.0)),
280
281 flex_basis: 0.0,
282 inner_flex_basis: 0.0,
283 violation: 0.0,
284 frozen: false,
285
286 hypothetical_inner_size: Size::zero(),
287 hypothetical_outer_size: Size::zero(),
288 target_size: Size::zero(),
289 outer_target_size: Size::zero(),
290
291 baseline: 0.0,
292
293 offset_main: 0.0,
294 offset_cross: 0.0,
295 })
296 .collect()
297 }
298
299 /// Determine the available main and cross space for the flex items.
300 ///
301 /// # [9.2. Line Length Determination](https://www.w3.org/TR/css-flexbox-1/#line-sizing)
302 ///
303 /// - [**Determine the available main and cross space for the flex items**](https://www.w3.org/TR/css-flexbox-1/#algo-available).
304 /// For each dimension, if that dimension of the flex container’s content box is a definite size, use that;
305 /// 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;
306 /// 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.
307 /// **This might result in an infinite value**.
308 #[inline]
309 #[must_use]
310 fn determine_available_space(
311 node_size: Size<Number>,
312 parent_size: Size<Number>,
313 constants: &AlgoConstants,
314 ) -> Size<Number> {
315 Size {
316 width: node_size.width.or_else(parent_size.width - constants.margin.horizontal_axis_sum())
317 - constants.padding_border.horizontal_axis_sum(),
318 height: node_size.height.or_else(parent_size.height - constants.margin.vertical_axis_sum())
319 - constants.padding_border.vertical_axis_sum(),
320 }
321 }
322
323 /// Determine the flex base size and hypothetical main size of each item.
324 ///
325 /// # [9.2. Line Length Determination](https://www.w3.org/TR/css-flexbox-1/#line-sizing)
326 ///
327 /// - [**Determine the flex base size and hypothetical main size of each item:**](https://www.w3.org/TR/css-flexbox-1/#algo-main-item)
328 ///
329 /// - A. If the item has a definite used flex basis, that’s the flex base size.
330 ///
331 /// - B. If the flex item has ...
332 ///
333 /// - an intrinsic aspect ratio,
334 /// - a used flex basis of content, and
335 /// - a definite cross size,
336 ///
337 /// then the flex base size is calculated from its inner cross size and the flex item’s intrinsic aspect ratio.
338 ///
339 /// - 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
340 /// or max-content constraint (e.g. when performing automatic table layout \[CSS21\]), size the item under that constraint.
341 /// The flex base size is the item’s resulting main size.
342 ///
343 /// - 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.
344 /// 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,
345 /// in this calculation use fit-content as the flex item’s cross size. The flex base size is the item’s resulting main size.
346 ///
347 /// When determining the flex base size, the item’s min and max main sizes are ignored (no clamping occurs).
348 /// Furthermore, the sizing calculations that floor the content box size at zero when applying box-sizing are also ignored.
349 /// (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.)
350 #[inline]
351 fn determine_flex_base_size(
352 &mut self,
353 node: NodeId,
354 node_size: Size<Number>,
355 constants: &AlgoConstants,
356 available_space: Size<Number>,
357 flex_items: &mut Vec<FlexItem>,
358 ) {
359 // TODO - this does not follow spec. See the TODOs below
360 for child in flex_items.iter_mut() {
361 let child_style = self.nodes[child.node].style;
362
363 // A. If the item has a definite used flex basis, that’s the flex base size.
364
365 let flex_basis = child_style.flex_basis.resolve(constants.node_inner_size.main(constants.dir));
366 if flex_basis.is_defined() {
367 child.flex_basis = flex_basis.or_else(0.0);
368 continue;
369 };
370
371 // B. If the flex item has an intrinsic aspect ratio,
372 // a used flex basis of content, and a definite cross size,
373 // then the flex base size is calculated from its inner
374 // cross size and the flex item’s intrinsic aspect ratio.
375
376 if let Defined(ratio) = child_style.aspect_ratio {
377 if let Defined(cross) = node_size.cross(constants.dir) {
378 if child_style.flex_basis == Dimension::Auto {
379 child.flex_basis = cross * ratio;
380 continue;
381 }
382 }
383 }
384
385 // C. If the used flex basis is content or depends on its available space,
386 // and the flex container is being sized under a min-content or max-content
387 // constraint (e.g. when performing automatic table layout [CSS21]),
388 // size the item under that constraint. The flex base size is the item’s
389 // resulting main size.
390
391 // TODO - Probably need to cover this case in future
392
393 // D. Otherwise, if the used flex basis is content or depends on its
394 // available space, the available main size is infinite, and the flex item’s
395 // inline axis is parallel to the main axis, lay the item out using the rules
396 // for a box in an orthogonal flow [CSS3-WRITING-MODES]. The flex base size
397 // is the item’s max-content main size.
398
399 // TODO - Probably need to cover this case in future
400
401 // E. Otherwise, size the item into the available space using its used flex basis
402 // in place of its main size, treating a value of content as max-content.
403 // If a cross size is needed to determine the main size (e.g. when the
404 // flex item’s main size is in its block axis) and the flex item’s cross size
405 // is auto and not definite, in this calculation use fit-content as the
406 // flex item’s cross size. The flex base size is the item’s resulting main size.
407
408 let width: Number = if !child.size.width.is_defined()
409 && child_style.align_self(&self.nodes[node].style) == AlignSelf::Stretch
410 && constants.is_column
411 {
412 available_space.width
413 } else {
414 child.size.width
415 };
416
417 let height: Number = if !child.size.height.is_defined()
418 && child_style.align_self(&self.nodes[node].style) == AlignSelf::Stretch
419 && constants.is_row
420 {
421 available_space.height
422 } else {
423 child.size.height
424 };
425
426 child.flex_basis = self
427 .compute_preliminary(
428 child.node,
429 Size {
430 width: width.maybe_max(child.min_size.width).maybe_min(child.max_size.width),
431 height: height.maybe_max(child.min_size.height).maybe_min(child.max_size.height),
432 },
433 available_space,
434 false,
435 true,
436 )
437 .size
438 .main(constants.dir)
439 .maybe_max(child.min_size.main(constants.dir))
440 .maybe_min(child.max_size.main(constants.dir));
441 }
442
443 // The hypothetical main size is the item’s flex base size clamped according to its
444 // used min and max main sizes (and flooring the content box size at zero).
445
446 for child in flex_items {
447 child.inner_flex_basis = child.flex_basis
448 - child.padding.main_axis_sum(constants.dir)
449 - child.border.main_axis_sum(constants.dir);
450
451 // TODO - not really spec abiding but needs to be done somewhere. probably somewhere else though.
452 // The following logic was developed not from the spec but by trail and error looking into how
453 // webkit handled various scenarios. Can probably be solved better by passing in
454 // min-content max-content constraints from the top
455 let min_main = self
456 .compute_preliminary(child.node, Size::undefined(), available_space, false, false)
457 .size
458 .main(constants.dir)
459 .maybe_max(child.min_size.main(constants.dir))
460 .maybe_min(child.size.main(constants.dir))
461 .into();
462
463 child.hypothetical_inner_size.set_main(
464 constants.dir,
465 child.flex_basis.maybe_max(min_main).maybe_min(child.max_size.main(constants.dir)),
466 );
467
468 child.hypothetical_outer_size.set_main(
469 constants.dir,
470 child.hypothetical_inner_size.main(constants.dir) + child.margin.main_axis_sum(constants.dir),
471 );
472 }
473 }
474
475 /// Collect flex items into flex lines.
476 ///
477 /// # [9.3. Main Size Determination](https://www.w3.org/TR/css-flexbox-1/#main-sizing)
478 ///
479 /// - [**Collect flex items into flex lines**](https://www.w3.org/TR/css-flexbox-1/#algo-line-break):
480 ///
481 /// - If the flex container is single-line, collect all the flex items into a single flex line.
482 ///
483 /// - 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
484 /// (or until a forced break is encountered, see [§10 Fragmenting Flex Layout](https://www.w3.org/TR/css-flexbox-1/#pagination)).
485 /// If the very first uncollected item wouldn’t fit, collect just it into the line.
486 ///
487 /// For this step, the size of a flex item is its outer hypothetical main size. (**Note: This can be negative**.)
488 ///
489 /// Repeat until all flex items have been collected into flex lines.
490 ///
491 /// **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**.
492 #[inline]
493 fn collect_flex_lines<'a>(
494 &self,
495 node: NodeId,
496 constants: &AlgoConstants,
497 available_space: Size<Number>,
498 flex_items: &'a mut Vec<FlexItem>,
499 ) -> Vec<FlexLine<'a>> {
500 let mut lines = crate::sys::new_vec_with_capacity(1);
501
502 if self.nodes[node].style.flex_wrap == FlexWrap::NoWrap {
503 lines.push(FlexLine { items: flex_items.as_mut_slice(), cross_size: 0.0, offset_cross: 0.0 });
504 } else {
505 let mut flex_items = &mut flex_items[..];
506
507 while !flex_items.is_empty() {
508 let mut line_length = 0.0;
509 let index = flex_items
510 .iter()
511 .enumerate()
512 .find(|&(idx, child)| {
513 line_length += child.hypothetical_outer_size.main(constants.dir);
514 if let Defined(main) = available_space.main(constants.dir) {
515 line_length > main && idx != 0
516 } else {
517 false
518 }
519 })
520 .map(|(idx, _)| idx)
521 .unwrap_or(flex_items.len());
522
523 let (items, rest) = flex_items.split_at_mut(index);
524 lines.push(FlexLine { items, cross_size: 0.0, offset_cross: 0.0 });
525 flex_items = rest;
526 }
527 }
528
529 lines
530 }
531
532 /// Resolve the flexible lengths of the items within a flex line.
533 ///
534 /// # [9.7. Resolving Flexible Lengths](https://www.w3.org/TR/css-flexbox-1/#resolve-flexible-lengths)
535 #[inline]
536 fn resolve_flexible_lengths(
537 &mut self,
538 line: &mut FlexLine,
539 constants: &AlgoConstants,
540 available_space: Size<Number>,
541 ) {
542 // 1. Determine the used flex factor. Sum the outer hypothetical main sizes of all
543 // items on the line. If the sum is less than the flex container’s inner main size,
544 // use the flex grow factor for the rest of this algorithm; otherwise, use the
545 // flex shrink factor.
546
547 let used_flex_factor: f32 =
548 line.items.iter().map(|child| child.hypothetical_outer_size.main(constants.dir)).sum();
549 let growing = used_flex_factor < constants.node_inner_size.main(constants.dir).or_else(0.0);
550 let shrinking = !growing;
551
552 // 2. Size inflexible items. Freeze, setting its target main size to its hypothetical main size
553 // - Any item that has a flex factor of zero
554 // - If using the flex grow factor: any item that has a flex base size
555 // greater than its hypothetical main size
556 // - If using the flex shrink factor: any item that has a flex base size
557 // smaller than its hypothetical main size
558
559 for child in line.items.iter_mut() {
560 // TODO - This is not found by reading the spec. Maybe this can be done in some other place
561 // instead. This was found by trail and error fixing tests to align with webkit output.
562 if constants.node_inner_size.main(constants.dir).is_undefined() && constants.is_row {
563 child.target_size.set_main(
564 constants.dir,
565 self.compute_preliminary(
566 child.node,
567 Size {
568 width: child.size.width.maybe_max(child.min_size.width).maybe_min(child.max_size.width),
569 height: child.size.height.maybe_max(child.min_size.height).maybe_min(child.max_size.height),
570 },
571 available_space,
572 false,
573 false,
574 )
575 .size
576 .main(constants.dir)
577 .maybe_max(child.min_size.main(constants.dir))
578 .maybe_min(child.max_size.main(constants.dir)),
579 );
580 } else {
581 child.target_size.set_main(constants.dir, child.hypothetical_inner_size.main(constants.dir));
582 }
583
584 // TODO this should really only be set inside the if-statement below but
585 // that causes the target_main_size to never be set for some items
586
587 child.outer_target_size.set_main(
588 constants.dir,
589 child.target_size.main(constants.dir) + child.margin.main_axis_sum(constants.dir),
590 );
591
592 let child_style = &self.nodes[child.node].style;
593 if (child_style.flex_grow == 0.0 && child_style.flex_shrink == 0.0)
594 || (growing && child.flex_basis > child.hypothetical_inner_size.main(constants.dir))
595 || (shrinking && child.flex_basis < child.hypothetical_inner_size.main(constants.dir))
596 {
597 child.frozen = true;
598 }
599 }
600
601 // 3. Calculate initial free space. Sum the outer sizes of all items on the line,
602 // and subtract this from the flex container’s inner main size. For frozen items,
603 // use their outer target main size; for other items, use their outer flex base size.
604
605 let used_space: f32 = line
606 .items
607 .iter()
608 .map(|child| {
609 child.margin.main_axis_sum(constants.dir)
610 + if child.frozen { child.target_size.main(constants.dir) } else { child.flex_basis }
611 })
612 .sum();
613
614 let initial_free_space = (constants.node_inner_size.main(constants.dir) - used_space).or_else(0.0);
615
616 // 4. Loop
617
618 loop {
619 // a. Check for flexible items. If all the flex items on the line are frozen,
620 // free space has been distributed; exit this loop.
621
622 if line.items.iter().all(|child| child.frozen) {
623 break;
624 }
625
626 // b. Calculate the remaining free space as for initial free space, above.
627 // If the sum of the unfrozen flex items’ flex factors is less than one,
628 // multiply the initial free space by this sum. If the magnitude of this
629 // value is less than the magnitude of the remaining free space, use this
630 // as the remaining free space.
631
632 let used_space: f32 = line
633 .items
634 .iter()
635 .map(|child| {
636 child.margin.main_axis_sum(constants.dir)
637 + if child.frozen { child.target_size.main(constants.dir) } else { child.flex_basis }
638 })
639 .sum();
640
641 let mut unfrozen: Vec<&mut FlexItem> = line.items.iter_mut().filter(|child| !child.frozen).collect();
642
643 let (sum_flex_grow, sum_flex_shrink): (f32, f32) =
644 unfrozen.iter().fold((0.0, 0.0), |(flex_grow, flex_shrink), item| {
645 let style = &self.nodes[item.node].style;
646 (flex_grow + style.flex_grow, flex_shrink + style.flex_shrink)
647 });
648
649 let free_space = if growing && sum_flex_grow < 1.0 {
650 (initial_free_space * sum_flex_grow)
651 .maybe_min(constants.node_inner_size.main(constants.dir) - used_space)
652 } else if shrinking && sum_flex_shrink < 1.0 {
653 (initial_free_space * sum_flex_shrink)
654 .maybe_max(constants.node_inner_size.main(constants.dir) - used_space)
655 } else {
656 (constants.node_inner_size.main(constants.dir) - used_space).or_else(0.0)
657 };
658
659 // c. Distribute free space proportional to the flex factors.
660 // - If the remaining free space is zero
661 // Do Nothing
662 // - If using the flex grow factor
663 // Find the ratio of the item’s flex grow factor to the sum of the
664 // flex grow factors of all unfrozen items on the line. Set the item’s
665 // target main size to its flex base size plus a fraction of the remaining
666 // free space proportional to the ratio.
667 // - If using the flex shrink factor
668 // For every unfrozen item on the line, multiply its flex shrink factor by
669 // its inner flex base size, and note this as its scaled flex shrink factor.
670 // Find the ratio of the item’s scaled flex shrink factor to the sum of the
671 // scaled flex shrink factors of all unfrozen items on the line. Set the item’s
672 // target main size to its flex base size minus a fraction of the absolute value
673 // of the remaining free space proportional to the ratio. Note this may result
674 // in a negative inner main size; it will be corrected in the next step.
675 // - Otherwise
676 // Do Nothing
677
678 if free_space.is_normal() {
679 if growing && sum_flex_grow > 0.0 {
680 for child in &mut unfrozen {
681 child.target_size.set_main(
682 constants.dir,
683 child.flex_basis + free_space * (self.nodes[child.node].style.flex_grow / sum_flex_grow),
684 );
685 }
686 } else if shrinking && sum_flex_shrink > 0.0 {
687 let sum_scaled_shrink_factor: f32 = unfrozen
688 .iter()
689 .map(|child| child.inner_flex_basis * self.nodes[child.node].style.flex_shrink)
690 .sum();
691
692 if sum_scaled_shrink_factor > 0.0 {
693 for child in &mut unfrozen {
694 let scaled_shrink_factor =
695 child.inner_flex_basis * self.nodes[child.node].style.flex_shrink;
696 child.target_size.set_main(
697 constants.dir,
698 child.flex_basis + free_space * (scaled_shrink_factor / sum_scaled_shrink_factor),
699 )
700 }
701 }
702 }
703 }
704
705 // d. Fix min/max violations. Clamp each non-frozen item’s target main size by its
706 // used min and max main sizes and floor its content-box size at zero. If the
707 // item’s target main size was made smaller by this, it’s a max violation.
708 // If the item’s target main size was made larger by this, it’s a min violation.
709
710 let total_violation = unfrozen.iter_mut().fold(0.0, |acc, child| -> f32 {
711 // TODO - not really spec abiding but needs to be done somewhere. probably somewhere else though.
712 // The following logic was developed not from the spec but by trail and error looking into how
713 // webkit handled various scenarios. Can probably be solved better by passing in
714 // min-content max-content constraints from the top. Need to figure out correct thing to do here as
715 // just piling on more conditionals.
716 let min_main = if constants.is_row && self.nodes[child.node].measure.is_none() {
717 self.compute_preliminary(child.node, Size::undefined(), available_space, false, false)
718 .size
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<Number>,
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 .size
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<Number>,
822 flex_lines: &mut [FlexLine],
823 constants: &AlgoConstants,
824 ) {
825 /// Recursively caluculates 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 result = 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: result.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<Number>,
902 constants: &AlgoConstants,
903 ) {
904 if flex_lines.len() == 1 && node_size.cross(constants.dir).is_defined() {
905 flex_lines[0].cross_size =
906 (node_size.cross(constants.dir) - constants.padding_border.cross_axis_sum(constants.dir)).or_else(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<Number>,
955 constants: &AlgoConstants,
956 ) {
957 if self.nodes[node].style.align_content == AlignContent::Stretch && node_size.cross(constants.dir).is_defined()
958 {
959 let total_cross: f32 = flex_lines.iter().map(|line| line.cross_size).sum();
960 let inner_cross =
961 (node_size.cross(constants.dir) - constants.padding_border.cross_axis_sum(constants.dir)).or_else(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: &Style,
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 => 0.0, // Should never happen
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<Number>,
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 .or_else(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 result = 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).or_else(0.0)
1361 - child.position.main_end(constants.dir).or_else(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).or_else(0.0)
1368 - child.position.cross_end(constants.dir).or_else(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: result.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 +=
1380 child.offset_main + child.margin.main_axis_sum(constants.dir) + result.size.main(constants.dir);
1381 };
1382
1383 if constants.dir.is_reverse() {
1384 line.items.iter_mut().rev().for_each(layout_item);
1385 } else {
1386 line.items.iter_mut().for_each(layout_item);
1387 }
1388
1389 total_offset_cross += line_offset_cross + line.cross_size;
1390 };
1391
1392 if constants.is_wrap_reverse {
1393 flex_lines.iter_mut().rev().for_each(layout_line);
1394 } else {
1395 flex_lines.iter_mut().for_each(layout_line);
1396 }
1397 }
1398
1399 /// Perform absolute layout on all absolutely positioned children.
1400 #[inline]
1401 fn perform_absolute_layout_on_absolute_children(&mut self, node: NodeId, constants: &AlgoConstants) {
1402 // TODO: remove number of Vec<_> generated
1403 let candidates = self.children[node]
1404 .iter()
1405 .cloned()
1406 .enumerate()
1407 .filter(|(_, child)| self.nodes[*child].style.position_type == PositionType::Absolute)
1408 .collect::<Vec<_>>();
1409
1410 for (order, child) in candidates {
1411 let container_width = constants.container_size.width.into();
1412 let container_height = constants.container_size.height.into();
1413
1414 let child_style = self.nodes[child].style;
1415
1416 let start =
1417 child_style.position.start.resolve(container_width) + child_style.margin.start.resolve(container_width);
1418 let end =
1419 child_style.position.end.resolve(container_width) + child_style.margin.end.resolve(container_width);
1420 let top =
1421 child_style.position.top.resolve(container_height) + child_style.margin.top.resolve(container_height);
1422 let bottom = child_style.position.bottom.resolve(container_height)
1423 + child_style.margin.bottom.resolve(container_height);
1424
1425 let (start_main, end_main) = if constants.is_row { (start, end) } else { (top, bottom) };
1426 let (start_cross, end_cross) = if constants.is_row { (top, bottom) } else { (start, end) };
1427
1428 let width = child_style
1429 .size
1430 .width
1431 .resolve(container_width)
1432 .maybe_max(child_style.min_size.width.resolve(container_width))
1433 .maybe_min(child_style.max_size.width.resolve(container_width))
1434 .or_else(if start.is_defined() && end.is_defined() {
1435 container_width - start - end
1436 } else {
1437 Undefined
1438 });
1439
1440 let height = child_style
1441 .size
1442 .height
1443 .resolve(container_height)
1444 .maybe_max(child_style.min_size.height.resolve(container_height))
1445 .maybe_min(child_style.max_size.height.resolve(container_height))
1446 .or_else(if top.is_defined() && bottom.is_defined() {
1447 container_height - top - bottom
1448 } else {
1449 Undefined
1450 });
1451
1452 let result = self.compute_preliminary(
1453 child,
1454 Size { width, height },
1455 Size { width: container_width, height: container_height },
1456 true,
1457 false,
1458 );
1459
1460 let free_main_space = constants.container_size.main(constants.dir)
1461 - result
1462 .size
1463 .main(constants.dir)
1464 .maybe_max(
1465 child_style.min_main_size(constants.dir).resolve(constants.node_inner_size.main(constants.dir)),
1466 )
1467 .maybe_min(
1468 child_style.max_main_size(constants.dir).resolve(constants.node_inner_size.main(constants.dir)),
1469 );
1470
1471 let free_cross_space = constants.container_size.cross(constants.dir)
1472 - result
1473 .size
1474 .cross(constants.dir)
1475 .maybe_max(
1476 child_style
1477 .min_cross_size(constants.dir)
1478 .resolve(constants.node_inner_size.cross(constants.dir)),
1479 )
1480 .maybe_min(
1481 child_style
1482 .max_cross_size(constants.dir)
1483 .resolve(constants.node_inner_size.cross(constants.dir)),
1484 );
1485
1486 let offset_main = if start_main.is_defined() {
1487 start_main.or_else(0.0) + constants.border.main_start(constants.dir)
1488 } else if end_main.is_defined() {
1489 free_main_space - end_main.or_else(0.0) - constants.border.main_end(constants.dir)
1490 } else {
1491 match self.nodes[node].style.justify_content {
1492 JustifyContent::SpaceBetween | JustifyContent::FlexStart => {
1493 constants.padding_border.main_start(constants.dir)
1494 }
1495 JustifyContent::FlexEnd => free_main_space - constants.padding_border.main_end(constants.dir),
1496 JustifyContent::SpaceEvenly | JustifyContent::SpaceAround | JustifyContent::Center => {
1497 free_main_space / 2.0
1498 }
1499 }
1500 };
1501
1502 let offset_cross = if start_cross.is_defined() {
1503 start_cross.or_else(0.0) + constants.border.cross_start(constants.dir)
1504 } else if end_cross.is_defined() {
1505 free_cross_space - end_cross.or_else(0.0) - constants.border.cross_end(constants.dir)
1506 } else {
1507 match child_style.align_self(&self.nodes[node].style) {
1508 AlignSelf::Auto => 0.0, // Should never happen
1509 AlignSelf::FlexStart => {
1510 if constants.is_wrap_reverse {
1511 free_cross_space - constants.padding_border.cross_end(constants.dir)
1512 } else {
1513 constants.padding_border.cross_start(constants.dir)
1514 }
1515 }
1516 AlignSelf::FlexEnd => {
1517 if constants.is_wrap_reverse {
1518 constants.padding_border.cross_start(constants.dir)
1519 } else {
1520 free_cross_space - constants.padding_border.cross_end(constants.dir)
1521 }
1522 }
1523 AlignSelf::Center => free_cross_space / 2.0,
1524 AlignSelf::Baseline => free_cross_space / 2.0, // Treat as center for now until we have baseline support
1525 AlignSelf::Stretch => {
1526 if constants.is_wrap_reverse {
1527 free_cross_space - constants.padding_border.cross_end(constants.dir)
1528 } else {
1529 constants.padding_border.cross_start(constants.dir)
1530 }
1531 }
1532 }
1533 };
1534
1535 self.nodes[child].layout = Layout {
1536 order: order as u32,
1537 size: result.size,
1538 location: Point {
1539 x: if constants.is_row { offset_main } else { offset_cross },
1540 y: if constants.is_column { offset_main } else { offset_cross },
1541 },
1542 };
1543 }
1544 }
1545
1546 /// Compute a preliminary size for an item
1547 fn compute_preliminary(
1548 &mut self,
1549 node: NodeId,
1550 node_size: Size<Number>,
1551 parent_size: Size<Number>,
1552 perform_layout: bool,
1553 main_size: bool,
1554 ) -> ComputeResult {
1555 self.nodes[node].is_dirty = false;
1556
1557 // First we check if we have a result for the given input
1558 if let Some(result) = self.compute_from_cache(node, node_size, parent_size, perform_layout, main_size) {
1559 return result;
1560 }
1561
1562 // Define some general constants we will need for the remainder of the algorithm.
1563 let mut constants = self.compute_constants(node, node_size, parent_size);
1564
1565 // If this is a leaf node we can skip a lot of this function in some cases
1566 if self.children[node].is_empty() {
1567 if node_size.width.is_defined() && node_size.height.is_defined() {
1568 return ComputeResult { size: node_size.map(|s| s.or_else(0.0)) };
1569 }
1570
1571 if let Some(ref measure) = self.nodes[node].measure {
1572 let result = match measure {
1573 MeasureFunc::Raw(measure) => ComputeResult { size: measure(node_size) },
1574 #[cfg(any(feature = "std", feature = "alloc"))]
1575 MeasureFunc::Boxed(measure) => ComputeResult { size: measure(node_size) },
1576 };
1577 *self.cache(node, main_size) =
1578 Some(Cache { node_size, parent_size, perform_layout, result: result.clone() });
1579 return result;
1580 }
1581
1582 return ComputeResult {
1583 size: Size {
1584 width: node_size.width.or_else(0.0) + constants.padding_border.horizontal_axis_sum(),
1585 height: node_size.height.or_else(0.0) + constants.padding_border.vertical_axis_sum(),
1586 },
1587 };
1588 }
1589
1590 // 9. Flex Layout Algorithm
1591
1592 // 9.1. Initial Setup
1593
1594 // 1. Generate anonymous flex items as described in §4 Flex Items.
1595 let mut flex_items = self.generate_anonymous_flex_items(node, &constants);
1596
1597 // 9.2. Line Length Determination
1598
1599 // 2. Determine the available main and cross space for the flex items.
1600 let available_space = Self::determine_available_space(node_size, parent_size, &constants);
1601
1602 let has_baseline_child = flex_items
1603 .iter()
1604 .any(|child| self.nodes[child.node].style.align_self(&self.nodes[node].style) == AlignSelf::Baseline);
1605
1606 // 3. Determine the flex base size and hypothetical main size of each item.
1607 self.determine_flex_base_size(node, node_size, &constants, available_space, &mut flex_items);
1608
1609 // TODO: Add step 4 according to spec: https://www.w3.org/TR/css-flexbox-1/#algo-main-container
1610 // 9.3. Main Size Determination
1611
1612 // 5. Collect flex items into flex lines.
1613 let mut flex_lines = self.collect_flex_lines(node, &constants, available_space, &mut flex_items);
1614
1615 // 6. Resolve the flexible lengths of all the flex items to find their used main size.
1616 for line in &mut flex_lines {
1617 self.resolve_flexible_lengths(line, &constants, available_space);
1618 }
1619
1620 // TODO: Cleanup and make according to spec
1621 // Not part of the spec from what i can see but seems correct
1622 constants.container_size.set_main(
1623 constants.dir,
1624 node_size.main(constants.dir).or_else({
1625 let longest_line = flex_lines.iter().fold(f32::MIN, |acc, line| {
1626 let length: f32 = line.items.iter().map(|item| item.outer_target_size.main(constants.dir)).sum();
1627 acc.max(length)
1628 });
1629
1630 let size = longest_line + constants.padding_border.main_axis_sum(constants.dir);
1631 match available_space.main(constants.dir) {
1632 Defined(val) if flex_lines.len() > 1 && size < val => val,
1633 _ => size,
1634 }
1635 }),
1636 );
1637
1638 constants.inner_container_size.set_main(
1639 constants.dir,
1640 constants.container_size.main(constants.dir) - constants.padding_border.main_axis_sum(constants.dir),
1641 );
1642
1643 // 9.4. Cross Size Determination
1644
1645 // 7. Determine the hypothetical cross size of each item.
1646 for line in &mut flex_lines {
1647 self.determine_hypothetical_cross_size(line, &constants, available_space);
1648 }
1649
1650 // TODO - probably should move this somewhere else as it doesn't make a ton of sense here but we need it below
1651 // TODO - This is expensive and should only be done if we really require a baseline. aka, make it lazy
1652 if has_baseline_child {
1653 self.calculate_children_base_lines(node, node_size, &mut flex_lines, &constants);
1654 }
1655
1656 // 8. Calculate the cross size of each flex line.
1657 self.calculate_cross_size(&mut flex_lines, node, node_size, &constants);
1658
1659 // 9. Handle 'align-content: stretch'.
1660 self.handle_align_content_stretch(&mut flex_lines, node, node_size, &constants);
1661
1662 // 10. Collapse visibility:collapse items. If any flex items have visibility: collapse,
1663 // note the cross size of the line they’re in as the item’s strut size, and restart
1664 // layout from the beginning.
1665 //
1666 // In this second layout round, when collecting items into lines, treat the collapsed
1667 // items as having zero main size. For the rest of the algorithm following that step,
1668 // ignore the collapsed items entirely (as if they were display:none) except that after
1669 // calculating the cross size of the lines, if any line’s cross size is less than the
1670 // largest strut size among all the collapsed items in the line, set its cross size to
1671 // that strut size.
1672 //
1673 // Skip this step in the second layout round.
1674
1675 // TODO implement once (if ever) we support visibility:collapse
1676
1677 // 11. Determine the used cross size of each flex item.
1678 self.determine_used_cross_size(&mut flex_lines, node, &constants);
1679
1680 // 9.5. Main-Axis Alignment
1681
1682 // 12. Distribute any remaining free space.
1683 self.distribute_remaining_free_space(&mut flex_lines, node, &constants);
1684
1685 // 9.6. Cross-Axis Alignment
1686
1687 // 13. Resolve cross-axis auto margins (also includes 14).
1688 self.resolve_cross_axis_auto_margins(&mut flex_lines, node, &constants);
1689
1690 // 15. Determine the flex container’s used cross size.
1691 let total_cross_size = Self::determine_container_cross_size(&mut flex_lines, node_size, &mut constants);
1692
1693 // We have the container size.
1694 // If our caller does not care about performing layout we are done now.
1695 if !perform_layout {
1696 let result = ComputeResult { size: constants.container_size };
1697 *self.cache(node, main_size) =
1698 Some(Cache { node_size, parent_size, perform_layout, result: result.clone() });
1699 return result;
1700 }
1701
1702 // 16. Align all flex lines per align-content.
1703 self.align_flex_lines_per_align_content(&mut flex_lines, node, &constants, total_cross_size);
1704
1705 // Do a final layout pass and gather the resulting layouts
1706 self.final_layout_pass(node, &mut flex_lines, &constants);
1707
1708 // Before returning we perform absolute layout on all absolutely positioned children
1709 self.perform_absolute_layout_on_absolute_children(node, &constants);
1710
1711 /// Lay out all hidden nodes recursively
1712 ///
1713 /// Each hidden node has zero size and is placed at the origin
1714 fn hidden_layout(nodes: &mut [NodeData], children: &[ChildrenVec<NodeId>], node: NodeId, order: u32) {
1715 nodes[node].layout = Layout { order, size: Size::zero(), location: Point::zero() };
1716
1717 for (order, child) in children[node].iter().enumerate() {
1718 hidden_layout(nodes, children, *child, order as _);
1719 }
1720 }
1721
1722 for (order, child) in self.children[node].iter().enumerate() {
1723 if self.nodes[*child].style.display == Display::None {
1724 hidden_layout(&mut self.nodes, &self.children, *child, order as _);
1725 }
1726 }
1727
1728 let result = ComputeResult { size: constants.container_size };
1729 *self.cache(node, main_size) = Some(Cache { node_size, parent_size, perform_layout, result: result.clone() });
1730
1731 result
1732 }
1733}