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