1#[cfg(not(feature = "std"))]
2use alloc::{vec, vec::Vec};
3#[cfg(not(feature = "std"))]
4use libm::F32Ext;
5
6use core::f32;
7
8use crate::layout;
9use crate::ref_eq::ref_eq;
10
11use crate::style;
12use crate::style::*;
13
14use crate::number::Number::*;
15use crate::number::*;
16
17use crate::geometry::{Point, Rect, Size};
18
19#[derive(Debug, Clone)]
20pub struct ComputeResult {
21 pub size: Size<f32>,
22 pub children: Vec<layout::Node>,
23}
24
25struct FlexItem<'a> {
26 node: &'a style::Node,
27
28 size: Size<Number>,
29 min_size: Size<Number>,
30 max_size: Size<Number>,
31
32 position: Rect<Number>,
33 margin: Rect<f32>,
34 padding: Rect<f32>,
35 border: Rect<f32>,
36
37 flex_basis: f32,
38 inner_flex_basis: f32,
39 violation: f32,
40 frozen: bool,
41
42 hypothetical_inner_size: Size<f32>,
43 hypothetical_outer_size: Size<f32>,
44 target_size: Size<f32>,
45 outer_target_size: Size<f32>,
46
47 baseline: f32,
48
49 // temporary values for holding offset in the main / cross direction.
50 // offset is the relative position from the item's natural flow position based on
51 // relative position values, alignment, and justification. Does not include margin/padding/border.
52 offset_main: f32,
53 offset_cross: f32,
54}
55
56struct FlexLine<'a> {
57 items: Vec<FlexItem<'a>>,
58 cross_size: f32,
59 offset_cross: f32,
60}
61
62pub fn compute(root: &style::Node, size: Size<Number>) -> layout::Node {
63 let has_root_min_max = root.min_size.width.is_defined()
64 || root.min_size.height.is_defined()
65 || root.max_size.width.is_defined()
66 || root.max_size.height.is_defined();
67
68 let result = if has_root_min_max {
69 let first_pass = compute_internal(
70 root,
71 Size { width: root.size.width.resolve(size.width), height: root.size.height.resolve(size.height) },
72 size,
73 size.width,
74 false,
75 );
76
77 compute_internal(
78 root,
79 Size {
80 width: first_pass
81 .size
82 .width
83 .maybe_max(root.min_size.width.resolve(size.width))
84 .maybe_min(root.max_size.width.resolve(size.width))
85 .to_number(),
86 height: first_pass
87 .size
88 .height
89 .maybe_max(root.min_size.height.resolve(size.height))
90 .maybe_min(root.max_size.height.resolve(size.height))
91 .to_number(),
92 },
93 size,
94 size.width,
95 true,
96 )
97 } else {
98 compute_internal(
99 root,
100 Size { width: root.size.width.resolve(size.width), height: root.size.height.resolve(size.height) },
101 size,
102 size.width,
103 true,
104 )
105 };
106
107 let mut layout = layout::Node {
108 order: 0,
109 size: Size { width: result.size.width, height: result.size.height },
110 location: Point { x: 0.0, y: 0.0 },
111 children: result.children,
112 };
113
114 round_layout(&mut layout, 0.0, 0.0);
115 layout
116}
117
118fn round_layout(layout: &mut layout::Node, abs_x: f32, abs_y: f32) {
119 let abs_x = abs_x + layout.location.x;
120 let abs_y = abs_y + layout.location.y;
121
122 layout.location.x = layout.location.x.round();
123 layout.location.y = layout.location.y.round();
124 layout.size.width = (abs_x + layout.size.width).round() - abs_x.round();
125 layout.size.height = (abs_y + layout.size.height).round() - abs_y.round();
126 layout.children.iter_mut().for_each(|child| round_layout(child, abs_x, abs_y));
127}
128
129fn compute_internal(
130 node: &style::Node,
131 node_size: Size<Number>,
132 parent_size: Size<Number>,
133 percent_calc_base: Number,
134 perform_layout: bool,
135) -> ComputeResult {
136 // First we check if we have a result for the given input
137 {
138 let layout_cache = node.layout_cache.borrow();
139 if let Some(cache) = layout_cache.as_ref() {
140 if cache.perform_layout || !perform_layout {
141 let width_compatible = if let Number::Defined(width) = node_size.width {
142 (width - cache.result.size.width).abs() < f32::EPSILON
143 } else {
144 cache.node_size.width.is_undefined()
145 };
146
147 let height_compatible = if let Number::Defined(height) = node_size.height {
148 (height - cache.result.size.height).abs() < f32::EPSILON
149 } else {
150 cache.node_size.height.is_undefined()
151 };
152
153 if width_compatible && height_compatible {
154 return cache.result.clone();
155 }
156
157 if cache.node_size == node_size
158 && cache.parent_size == parent_size
159 && cache.percent_calc_base == percent_calc_base
160 {
161 return cache.result.clone();
162 }
163 }
164 }
165 }
166
167 // If this is a leaf node we can skip a lot of this function in some cases
168 if node.children.is_empty() {
169 if node_size.width.is_defined() && node_size.height.is_defined() {
170 return ComputeResult { size: node_size.map(|s| s.or_else(0.0)), children: vec![] };
171 }
172
173 if let Some(ref measure) = node.measure {
174 let result = ComputeResult { size: measure(node_size), children: vec![] };
175 node.layout_cache.replace(Some(LayoutCache {
176 node_size,
177 parent_size,
178 percent_calc_base,
179 perform_layout,
180 result: result.clone(),
181 }));
182 return result;
183 }
184 }
185
186 // Define some general constants we will need for the remainder
187 // of the algorithm.
188
189 let dir = node.flex_direction;
190 let is_row = dir.is_row();
191 let is_column = dir.is_column();
192 let is_wrap_reverse = node.flex_wrap == FlexWrap::WrapReverse;
193
194 let margin = node.margin.map(|n| n.resolve(percent_calc_base).or_else(0.0));
195 let padding = node.padding.map(|n| n.resolve(percent_calc_base).or_else(0.0));
196 let border = node.border.map(|n| n.resolve(percent_calc_base).or_else(0.0));
197
198 let padding_border = Rect {
199 start: padding.start + border.start,
200 end: padding.end + border.end,
201 top: padding.top + border.top,
202 bottom: padding.bottom + border.bottom,
203 };
204
205 let node_inner_size = Size {
206 width: node_size.width - padding_border.horizontal(),
207 height: node_size.height - padding_border.vertical(),
208 };
209
210 let percent_calc_base_child = node_inner_size.width;
211 let mut container_size = Size { width: 0.0, height: 0.0 };
212 let mut inner_container_size = Size { width: 0.0, height: 0.0 };
213
214 // 9.2. Line Length Determination
215
216 // 1. Generate anonymous flex items as described in §4 Flex Items.
217
218 // 2. Determine the available main and cross space for the flex items.
219 // For each dimension, if that dimension of the flex container’s content box
220 // is a definite size, use that; if that dimension of the flex container is
221 // being sized under a min or max-content constraint, the available space in
222 // that dimension is that constraint; otherwise, subtract the flex container’s
223 // margin, border, and padding from the space available to the flex container
224 // in that dimension and use that value. This might result in an infinite value.
225
226 let available_space = Size {
227 width: node_size.width.or_else(parent_size.width - margin.horizontal()) - padding_border.horizontal(),
228 height: node_size.height.or_else(parent_size.height - margin.vertical()) - padding_border.vertical(),
229 };
230
231 let mut flex_items: Vec<FlexItem> = node
232 .children
233 .iter()
234 .filter(|child| child.position_type != PositionType::Absolute)
235 .filter(|child| child.display != Display::None)
236 .map(|child| FlexItem {
237 node: child,
238
239 size: child.size.map(|s| s.resolve(percent_calc_base_child)),
240 min_size: child.min_size.map(|s| s.resolve(percent_calc_base_child)),
241 max_size: child.max_size.map(|s| s.resolve(percent_calc_base_child)),
242
243 position: child.position.map(|p| p.resolve(percent_calc_base_child)),
244 margin: child.margin.map(|m| m.resolve(percent_calc_base_child).or_else(0.0)),
245 padding: child.padding.map(|p| p.resolve(percent_calc_base_child).or_else(0.0)),
246 border: child.border.map(|b| b.resolve(percent_calc_base_child).or_else(0.0)),
247
248 flex_basis: 0.0,
249 inner_flex_basis: 0.0,
250 violation: 0.0,
251 frozen: false,
252
253 hypothetical_inner_size: Size { width: 0.0, height: 0.0 },
254 hypothetical_outer_size: Size { width: 0.0, height: 0.0 },
255 target_size: Size { width: 0.0, height: 0.0 },
256 outer_target_size: Size { width: 0.0, height: 0.0 },
257
258 baseline: 0.0,
259
260 offset_main: 0.0,
261 offset_cross: 0.0,
262 })
263 .collect();
264
265 // TODO - this does not follow spec. See commented out code below
266 // 3. Determine the flex base size and hypothetical main size of each item:
267 flex_items.iter_mut().for_each(|child| {
268 // A. If the item has a definite used flex basis, that’s the flex base size.
269
270 let flex_basis = child.node.flex_basis.resolve(percent_calc_base_child);
271 if flex_basis.is_defined() {
272 child.flex_basis = flex_basis.or_else(0.0);
273 return;
274 };
275
276 // B. If the flex item has an intrinsic aspect ratio,
277 // a used flex basis of content, and a definite cross size,
278 // then the flex base size is calculated from its inner
279 // cross size and the flex item’s intrinsic aspect ratio.
280
281 if let Defined(ratio) = child.node.aspect_ratio {
282 if let Defined(cross) = node_size.cross(dir) {
283 if child.node.flex_basis == Dimension::Auto {
284 child.flex_basis = cross * ratio;
285 return;
286 }
287 }
288 }
289
290 // C. If the used flex basis is content or depends on its available space,
291 // and the flex container is being sized under a min-content or max-content
292 // constraint (e.g. when performing automatic table layout [CSS21]),
293 // size the item under that constraint. The flex base size is the item’s
294 // resulting main size.
295
296 // TODO - Probably need to cover this case in future
297
298 // D. Otherwise, if the used flex basis is content or depends on its
299 // available space, the available main size is infinite, and the flex item’s
300 // inline axis is parallel to the main axis, lay the item out using the rules
301 // for a box in an orthogonal flow [CSS3-WRITING-MODES]. The flex base size
302 // is the item’s max-content main size.
303
304 // TODO - Probably need to cover this case in future
305
306 // E. Otherwise, size the item into the available space using its used flex basis
307 // in place of its main size, treating a value of content as max-content.
308 // If a cross size is needed to determine the main size (e.g. when the
309 // flex item’s main size is in its block axis) and the flex item’s cross size
310 // is auto and not definite, in this calculation use fit-content as the
311 // flex item’s cross size. The flex base size is the item’s resulting main size.
312
313 let width: Number = if !child.size.width.is_defined()
314 && child.node.align_self(node) == style::AlignSelf::Stretch
315 && is_column
316 {
317 available_space.width
318 } else {
319 child.size.width
320 };
321
322 let height: Number =
323 if !child.size.height.is_defined() && child.node.align_self(node) == style::AlignSelf::Stretch && is_row {
324 available_space.height
325 } else {
326 child.size.height
327 };
328
329 child.flex_basis = compute_internal(
330 child.node,
331 Size {
332 width: width.maybe_max(child.min_size.width).maybe_min(child.max_size.width),
333 height: height.maybe_max(child.min_size.height).maybe_min(child.max_size.height),
334 },
335 available_space,
336 percent_calc_base_child,
337 false,
338 )
339 .size
340 .main(dir)
341 .maybe_max(child.min_size.main(dir))
342 .maybe_min(child.max_size.main(dir));
343 });
344
345 // The hypothetical main size is the item’s flex base size clamped according to its
346 // used min and max main sizes (and flooring the content box size at zero).
347
348 flex_items.iter_mut().for_each(|child| {
349 child.inner_flex_basis = child.flex_basis - child.padding.main(dir) - child.border.main(dir);
350
351 // TODO - not really spec abiding but needs to be done somewhere. probably somewhere else though.
352 // The following logic was developed not from the spec but by trail and error looking into how
353 // webkit handled various scenarios. Can probably be solved better by passing in
354 // min-content max-content constraints from the top
355 let min_main = if is_row {
356 compute_internal(
357 child.node,
358 Size { width: Undefined, height: Undefined },
359 available_space,
360 percent_calc_base_child,
361 false,
362 )
363 .size
364 .width
365 .maybe_max(child.min_size.width)
366 .maybe_min(child.size.width)
367 .to_number()
368 } else {
369 child.min_size.main(dir)
370 };
371
372 child
373 .hypothetical_inner_size
374 .set_main(dir, child.flex_basis.maybe_max(min_main).maybe_min(child.max_size.main(dir)));
375
376 child.hypothetical_outer_size.set_main(dir, child.hypothetical_inner_size.main(dir) + child.margin.main(dir));
377 });
378
379 // 9.3. Main Size Determination
380
381 // 5. Collect flex items into flex lines:
382 // - If the flex container is single-line, collect all the flex items into
383 // a single flex line.
384 // - Otherwise, starting from the first uncollected item, collect consecutive
385 // items one by one until the first time that the next collected item would
386 // not fit into the flex container’s inner main size (or until a forced break
387 // is encountered, see §10 Fragmenting Flex Layout). If the very first
388 // uncollected item wouldn’t fit, collect just it into the line.
389 //
390 // For this step, the size of a flex item is its outer hypothetical main size. (Note: This can be negative.)
391 // Repeat until all flex items have been collected into flex lines
392 //
393 // Note that the "collect as many" line will collect zero-sized flex items onto
394 // the end of the previous line even if the last non-zero item exactly "filled up" the line.
395
396 let mut flex_lines = {
397 let mut lines: Vec<FlexLine> = vec![];
398 let mut line_length = 0.0;
399
400 if node.flex_wrap == FlexWrap::NoWrap {
401 lines.push(FlexLine { items: flex_items, cross_size: 0.0, offset_cross: 0.0 });
402 } else {
403 let mut line = FlexLine { items: vec![], cross_size: 0.0, offset_cross: 0.0 };
404
405 for child in flex_items {
406 line_length += child.hypothetical_outer_size.main(dir);
407
408 if let Defined(main) = available_space.main(dir) {
409 if line_length > main && !line.items.is_empty() {
410 line_length = child.hypothetical_outer_size.main(dir);
411 lines.push(line);
412 line = FlexLine { items: vec![], cross_size: 0.0, offset_cross: 0.0 };
413 }
414 }
415
416 line.items.push(child);
417 }
418
419 lines.push(line);
420 }
421
422 lines
423 };
424
425 // 6. Resolve the flexible lengths of all the flex items to find their used main size.
426 // See §9.7 Resolving Flexible Lengths.
427 //
428 // 9.7. Resolving Flexible Lengths
429
430 flex_lines.iter_mut().for_each(|line| {
431 // 1. Determine the used flex factor. Sum the outer hypothetical main sizes of all
432 // items on the line. If the sum is less than the flex container’s inner main size,
433 // use the flex grow factor for the rest of this algorithm; otherwise, use the
434 // flex shrink factor.
435
436 let used_flex_factor: f32 = line.items.iter().map(|child| child.hypothetical_outer_size.main(dir)).sum();
437 let growing = used_flex_factor < node_inner_size.main(dir).or_else(0.0);
438 let shrinking = !growing;
439
440 // 2. Size inflexible items. Freeze, setting its target main size to its hypothetical main size
441 // - Any item that has a flex factor of zero
442 // - If using the flex grow factor: any item that has a flex base size
443 // greater than its hypothetical main size
444 // - If using the flex shrink factor: any item that has a flex base size
445 // smaller than its hypothetical main size
446
447 line.items.iter_mut().for_each(|child| {
448 // TODO - This is not found by reading the spec. Maybe this can be done in some other place
449 // instead. This was found by trail and error fixing tests to align with webkit output.
450 if node_inner_size.main(dir).is_undefined() && is_row {
451 child.target_size.set_main(
452 dir,
453 compute_internal(
454 child.node,
455 Size {
456 width: child.size.width.maybe_max(child.min_size.width).maybe_min(child.max_size.width),
457 height: child.size.height.maybe_max(child.min_size.height).maybe_min(child.max_size.height),
458 },
459 available_space,
460 percent_calc_base_child,
461 false,
462 )
463 .size
464 .main(dir)
465 .maybe_max(child.min_size.main(dir))
466 .maybe_min(child.max_size.main(dir)),
467 );
468 } else {
469 child.target_size.set_main(dir, child.hypothetical_inner_size.main(dir));
470 }
471
472 // TODO this should really only be set inside the if-statement below but
473 // that causes the target_main_size to never be set for some items
474
475 child.outer_target_size.set_main(dir, child.target_size.main(dir) + child.margin.main(dir));
476
477 if (child.node.flex_grow == 0.0 && child.node.flex_shrink == 0.0)
478 || (growing && child.flex_basis > child.hypothetical_inner_size.main(dir))
479 || (shrinking && child.flex_basis < child.hypothetical_inner_size.main(dir))
480 {
481 child.frozen = true;
482 }
483 });
484
485 // 3. Calculate initial free space. Sum the outer sizes of all items on the line,
486 // and subtract this from the flex container’s inner main size. For frozen items,
487 // use their outer target main size; for other items, use their outer flex base size.
488
489 let used_space: f32 = line
490 .items
491 .iter()
492 .map(|child| {
493 child.margin.main(dir) + if child.frozen { child.target_size.main(dir) } else { child.flex_basis }
494 })
495 .sum();
496
497 let initial_free_space = (node_inner_size.main(dir) - used_space).or_else(0.0);
498
499 // 4. Loop
500
501 loop {
502 // a. Check for flexible items. If all the flex items on the line are frozen,
503 // free space has been distributed; exit this loop.
504
505 let mut frozen: Vec<&mut FlexItem> = vec![];
506 let mut unfrozen: Vec<&mut FlexItem> = vec![];
507
508 line.items.iter_mut().for_each(|child| {
509 if child.frozen {
510 frozen.push(child);
511 } else {
512 unfrozen.push(child);
513 }
514 });
515
516 if unfrozen.is_empty() {
517 break;
518 }
519
520 // b. Calculate the remaining free space as for initial free space, above.
521 // If the sum of the unfrozen flex items’ flex factors is less than one,
522 // multiply the initial free space by this sum. If the magnitude of this
523 // value is less than the magnitude of the remaining free space, use this
524 // as the remaining free space.
525
526 let used_space: f32 = Iterator::chain(frozen.iter(), unfrozen.iter())
527 .map(|child| {
528 child.margin.main(dir) + if child.frozen { child.target_size.main(dir) } else { child.flex_basis }
529 })
530 .sum();
531
532 let sum_flex_grow: f32 = unfrozen.iter().map(|item| item.node.flex_grow).sum();
533 let sum_flex_shrink: f32 = unfrozen.iter().map(|item| item.node.flex_shrink).sum();
534
535 let free_space = if growing && sum_flex_grow < 1.0 {
536 (initial_free_space * sum_flex_grow).maybe_min(node_inner_size.main(dir) - used_space)
537 } else if shrinking && sum_flex_shrink < 1.0 {
538 (initial_free_space * sum_flex_shrink).maybe_max(node_inner_size.main(dir) - used_space)
539 } else {
540 (node_inner_size.main(dir) - used_space).or_else(0.0)
541 };
542
543 // c. Distribute free space proportional to the flex factors.
544 // - If the remaining free space is zero
545 // Do Nothing
546 // - If using the flex grow factor
547 // Find the ratio of the item’s flex grow factor to the sum of the
548 // flex grow factors of all unfrozen items on the line. Set the item’s
549 // target main size to its flex base size plus a fraction of the remaining
550 // free space proportional to the ratio.
551 // - If using the flex shrink factor
552 // For every unfrozen item on the line, multiply its flex shrink factor by
553 // its inner flex base size, and note this as its scaled flex shrink factor.
554 // Find the ratio of the item’s scaled flex shrink factor to the sum of the
555 // scaled flex shrink factors of all unfrozen items on the line. Set the item’s
556 // target main size to its flex base size minus a fraction of the absolute value
557 // of the remaining free space proportional to the ratio. Note this may result
558 // in a negative inner main size; it will be corrected in the next step.
559 // - Otherwise
560 // Do Nothing
561
562 if free_space.is_normal() {
563 if growing && sum_flex_grow > 0.0 {
564 unfrozen.iter_mut().for_each(|child| {
565 child
566 .target_size
567 .set_main(dir, child.flex_basis + free_space * (child.node.flex_grow / sum_flex_grow));
568 });
569 } else if shrinking && sum_flex_shrink > 0.0 {
570 let sum_scaled_shrink_factor: f32 =
571 unfrozen.iter().map(|child| child.inner_flex_basis * child.node.flex_shrink).sum();
572
573 if sum_scaled_shrink_factor > 0.0 {
574 unfrozen.iter_mut().for_each(|child| {
575 let scaled_shrink_factor = child.inner_flex_basis * child.node.flex_shrink;
576 child.target_size.set_main(
577 dir,
578 child.flex_basis + free_space * (scaled_shrink_factor / sum_scaled_shrink_factor),
579 )
580 });
581 }
582 }
583 }
584
585 // d. Fix min/max violations. Clamp each non-frozen item’s target main size by its
586 // used min and max main sizes and floor its content-box size at zero. If the
587 // item’s target main size was made smaller by this, it’s a max violation.
588 // If the item’s target main size was made larger by this, it’s a min violation.
589
590 let total_violation = unfrozen.iter_mut().fold(0.0, |acc, child| {
591 // TODO - not really spec abiding but needs to be done somewhere. probably somewhere else though.
592 // The following logic was developed not from the spec but by trail and error looking into how
593 // webkit handled various scenarios. Can probably be solved better by passing in
594 // min-content max-content constraints from the top. Need to figure out correct thing to do here as
595 // just piling on more conditionals.
596 let min_main = if is_row && child.node.measure.is_none() {
597 compute_internal(
598 child.node,
599 Size { width: Undefined, height: Undefined },
600 available_space,
601 percent_calc_base_child,
602 false,
603 )
604 .size
605 .width
606 .maybe_min(child.size.width)
607 .maybe_max(child.min_size.width)
608 .to_number()
609 } else {
610 child.min_size.main(dir)
611 };
612
613 let max_main = child.max_size.main(dir);
614 let clamped = child.target_size.main(dir).maybe_min(max_main).maybe_max(min_main).max(0.0);
615 child.violation = clamped - child.target_size.main(dir);
616 child.target_size.set_main(dir, clamped);
617 child.outer_target_size.set_main(dir, child.target_size.main(dir) + child.margin.main(dir));
618
619 acc + child.violation
620 });
621
622 // e. Freeze over-flexed items. The total violation is the sum of the adjustments
623 // from the previous step ∑(clamped size - unclamped size). If the total violation is:
624 // - Zero
625 // Freeze all items.
626 // - Positive
627 // Freeze all the items with min violations.
628 // - Negative
629 // Freeze all the items with max violations.
630
631 unfrozen.iter_mut().for_each(|child| match total_violation {
632 v if v > 0.0 => child.frozen = child.violation > 0.0,
633 v if v < 0.0 => child.frozen = child.violation < 0.0,
634 _ => child.frozen = true,
635 })
636
637 // f. Return to the start of this loop.
638 }
639 });
640
641 // Not part of the spec from what i can see but seems correct
642 container_size.set_main(
643 dir,
644 node_size.main(dir).or_else({
645 let longest_line = flex_lines.iter().fold(f32::MIN, |acc, line| {
646 let length: f32 = line.items.iter().map(|item| item.outer_target_size.main(dir)).sum();
647 acc.max(length)
648 });
649
650 let size = longest_line + padding_border.main(dir);
651 match available_space.main(dir) {
652 Defined(val) if flex_lines.len() > 1 && size < val => val,
653 _ => size,
654 }
655 }),
656 );
657
658 inner_container_size.set_main(dir, container_size.main(dir) - padding_border.main(dir));
659
660 // 9.4. Cross Size Determination
661
662 // 7. Determine the hypothetical cross size of each item by performing layout with the
663 // used main size and the available space, treating auto as fit-content.
664
665 flex_lines.iter_mut().for_each(|line| {
666 line.items.iter_mut().for_each(|child| {
667 let child_cross =
668 child.size.cross(dir).maybe_max(child.min_size.cross(dir)).maybe_min(child.max_size.cross(dir));
669
670 child.hypothetical_inner_size.set_cross(
671 dir,
672 compute_internal(
673 child.node,
674 Size {
675 width: if is_row { child.target_size.width.to_number() } else { child_cross },
676 height: if is_row { child_cross } else { child.target_size.height.to_number() },
677 },
678 Size {
679 width: if is_row { container_size.main(dir).to_number() } else { available_space.width },
680 height: if is_row { available_space.height } else { container_size.main(dir).to_number() },
681 },
682 percent_calc_base_child,
683 false,
684 )
685 .size
686 .cross(dir)
687 .maybe_max(child.min_size.cross(dir))
688 .maybe_min(child.max_size.cross(dir)),
689 );
690
691 child
692 .hypothetical_outer_size
693 .set_cross(dir, child.hypothetical_inner_size.cross(dir) + child.margin.cross(dir));
694 });
695 });
696
697 // TODO - probably should move this somewhere else as it doesn't make a ton of sense here but we need it below
698 // TODO - This is expensive and should only be done if we really require a baseline. aka, make it lazy
699
700 fn calc_baseline(layout: &layout::Node) -> f32 {
701 if layout.children.is_empty() {
702 layout.size.height
703 } else {
704 calc_baseline(&layout.children[0])
705 }
706 };
707
708 flex_lines.iter_mut().for_each(|line| {
709 line.items.iter_mut().for_each(|child| {
710 let result = compute_internal(
711 child.node,
712 Size {
713 width: if is_row {
714 child.target_size.width.to_number()
715 } else {
716 child.hypothetical_inner_size.width.to_number()
717 },
718 height: if is_row {
719 child.hypothetical_inner_size.height.to_number()
720 } else {
721 child.target_size.height.to_number()
722 },
723 },
724 Size {
725 width: if is_row { container_size.width.to_number() } else { node_size.width },
726 height: if is_row { node_size.height } else { container_size.height.to_number() },
727 },
728 percent_calc_base_child,
729 true,
730 );
731 child.baseline = calc_baseline(&layout::Node {
732 order: node.children.iter().position(|n| ref_eq(n, child.node)).unwrap() as u32,
733 size: result.size,
734 location: Point { x: 0.0, y: 0.0 },
735 children: result.children,
736 });
737 });
738 });
739
740 // 8. Calculate the cross size of each flex line.
741 // If the flex container is single-line and has a definite cross size, the cross size
742 // of the flex line is the flex container’s inner cross size. Otherwise, for each flex line:
743 //
744 // If the flex container is single-line, then clamp the line’s cross-size to be within
745 // the container’s computed min and max cross sizes. Note that if CSS 2.1’s definition
746 // of min/max-width/height applied more generally, this behavior would fall out automatically.
747
748 if flex_lines.len() == 1 && node_size.cross(dir).is_defined() {
749 flex_lines[0].cross_size = (node_size.cross(dir) - padding_border.cross(dir)).or_else(0.0);
750 } else {
751 flex_lines.iter_mut().for_each(|line| {
752 // 1. Collect all the flex items whose inline-axis is parallel to the main-axis, whose
753 // align-self is baseline, and whose cross-axis margins are both non-auto. Find the
754 // largest of the distances between each item’s baseline and its hypothetical outer
755 // cross-start edge, and the largest of the distances between each item’s baseline
756 // and its hypothetical outer cross-end edge, and sum these two values.
757
758 // 2. Among all the items not collected by the previous step, find the largest
759 // outer hypothetical cross size.
760
761 // 3. The used cross-size of the flex line is the largest of the numbers found in the
762 // previous two steps and zero.
763
764 let max_baseline: f32 = line.items.iter().map(|child| child.baseline).fold(0.0, |acc, x| acc.max(x));
765 line.cross_size = line
766 .items
767 .iter()
768 .map(|child| {
769 if child.node.align_self(node) == AlignSelf::Baseline
770 && child.node.cross_margin_start(dir) != Dimension::Auto
771 && child.node.cross_margin_end(dir) != Dimension::Auto
772 && child.node.cross_size(dir) == Dimension::Auto
773 {
774 max_baseline - child.baseline + child.hypothetical_outer_size.cross(dir)
775 } else {
776 child.hypothetical_outer_size.cross(dir)
777 }
778 })
779 .fold(0.0, |acc, x| acc.max(x));
780 });
781 }
782
783 // 9. Handle 'align-content: stretch'. If the flex container has a definite cross size,
784 // align-content is stretch, and the sum of the flex lines' cross sizes is less than
785 // the flex container’s inner cross size, increase the cross size of each flex line
786 // by equal amounts such that the sum of their cross sizes exactly equals the
787 // flex container’s inner cross size.
788
789 if node.align_content == AlignContent::Stretch && node_size.cross(dir).is_defined() {
790 let total_cross: f32 = flex_lines.iter().map(|line| line.cross_size).sum();
791 let inner_cross = (node_size.cross(dir) - padding_border.cross(dir)).or_else(0.0);
792
793 if total_cross < inner_cross {
794 let remaining = inner_cross - total_cross;
795 let addition = remaining / flex_lines.len() as f32;
796 flex_lines.iter_mut().for_each(|line| line.cross_size += addition);
797 }
798 }
799
800 // 10. Collapse visibility:collapse items. If any flex items have visibility: collapse,
801 // note the cross size of the line they’re in as the item’s strut size, and restart
802 // layout from the beginning.
803 //
804 // In this second layout round, when collecting items into lines, treat the collapsed
805 // items as having zero main size. For the rest of the algorithm following that step,
806 // ignore the collapsed items entirely (as if they were display:none) except that after
807 // calculating the cross size of the lines, if any line’s cross size is less than the
808 // largest strut size among all the collapsed items in the line, set its cross size to
809 // that strut size.
810 //
811 // Skip this step in the second layout round.
812
813 // TODO implement once (if ever) we support visibility:collapse
814
815 // 11. Determine the used cross size of each flex item. If a flex item has align-self: stretch,
816 // its computed cross size property is auto, and neither of its cross-axis margins are auto,
817 // the used outer cross size is the used cross size of its flex line, clamped according to
818 // the item’s used min and max cross sizes. Otherwise, the used cross size is the item’s
819 // hypothetical cross size.
820 //
821 // If the flex item has align-self: stretch, redo layout for its contents, treating this
822 // used size as its definite cross size so that percentage-sized children can be resolved.
823 //
824 // Note that this step does not affect the main size of the flex item, even if it has an
825 // intrinsic aspect ratio.
826
827 flex_lines.iter_mut().for_each(|line| {
828 let line_cross_size = line.cross_size;
829
830 line.items.iter_mut().for_each(|child| {
831 child.target_size.set_cross(
832 dir,
833 if child.node.align_self(node) == AlignSelf::Stretch
834 && child.node.cross_margin_start(dir) != Dimension::Auto
835 && child.node.cross_margin_end(dir) != Dimension::Auto
836 && child.node.cross_size(dir) == Dimension::Auto
837 {
838 (line_cross_size - child.margin.cross(dir))
839 .maybe_max(child.min_size.cross(dir))
840 .maybe_min(child.max_size.cross(dir))
841 } else {
842 child.hypothetical_inner_size.cross(dir)
843 },
844 );
845
846 child.outer_target_size.set_cross(dir, child.target_size.cross(dir) + child.margin.cross(dir));
847 });
848 });
849
850 // 9.5. Main-Axis Alignment
851
852 // 12. Distribute any remaining free space. For each flex line:
853 // 1. If the remaining free space is positive and at least one main-axis margin on this
854 // line is auto, distribute the free space equally among these margins. Otherwise,
855 // set all auto margins to zero.
856 // 2. Align the items along the main-axis per justify-content.
857
858 flex_lines.iter_mut().for_each(|line| {
859 let used_space: f32 = line.items.iter().map(|child| child.outer_target_size.main(dir)).sum();
860 let free_space = inner_container_size.main(dir) - used_space;
861 let mut num_auto_margins = 0;
862
863 line.items.iter_mut().for_each(|child| {
864 if child.node.main_margin_start(dir) == Dimension::Auto {
865 num_auto_margins += 1;
866 }
867 if child.node.main_margin_end(dir) == Dimension::Auto {
868 num_auto_margins += 1;
869 }
870 });
871
872 if free_space > 0.0 && num_auto_margins > 0 {
873 let margin = free_space / num_auto_margins as f32;
874
875 line.items.iter_mut().for_each(|child| {
876 if child.node.main_margin_start(dir) == Dimension::Auto {
877 if is_row {
878 child.margin.start = margin;
879 } else {
880 child.margin.top = margin;
881 }
882 }
883 if child.node.main_margin_end(dir) == Dimension::Auto {
884 if is_row {
885 child.margin.end = margin;
886 } else {
887 child.margin.bottom = margin;
888 }
889 }
890 });
891 } else {
892 let num_items = line.items.len();
893 let layout_reverse = dir.is_reverse();
894
895 let justify_item = |(i, child): (usize, &mut FlexItem)| {
896 let is_first = i == 0;
897
898 child.offset_main = match node.justify_content {
899 JustifyContent::FlexStart => {
900 if layout_reverse && is_first {
901 free_space
902 } else {
903 0.0
904 }
905 }
906 JustifyContent::Center => {
907 if is_first {
908 free_space / 2.0
909 } else {
910 0.0
911 }
912 }
913 JustifyContent::FlexEnd => {
914 if is_first && !layout_reverse {
915 free_space
916 } else {
917 0.0
918 }
919 }
920 JustifyContent::SpaceBetween => {
921 if is_first {
922 0.0
923 } else {
924 free_space / (num_items - 1) as f32
925 }
926 }
927 JustifyContent::SpaceAround => {
928 if is_first {
929 (free_space / num_items as f32) / 2.0
930 } else {
931 free_space / num_items as f32
932 }
933 }
934 JustifyContent::SpaceEvenly => free_space / (num_items + 1) as f32,
935 };
936 };
937
938 if layout_reverse {
939 line.items.iter_mut().rev().enumerate().for_each(justify_item);
940 } else {
941 line.items.iter_mut().enumerate().for_each(justify_item);
942 }
943 }
944 });
945
946 // 9.6. Cross-Axis Alignment
947
948 // 13. Resolve cross-axis auto margins. If a flex item has auto cross-axis margins:
949 // - If its outer cross size (treating those auto margins as zero) is less than the
950 // cross size of its flex line, distribute the difference in those sizes equally
951 // to the auto margins.
952 // - Otherwise, if the block-start or inline-start margin (whichever is in the cross axis)
953 // is auto, set it to zero. Set the opposite margin so that the outer cross size of the
954 // item equals the cross size of its flex line.
955
956 flex_lines.iter_mut().for_each(|line| {
957 let line_cross_size = line.cross_size;
958 let max_baseline: f32 = line.items.iter_mut().map(|child| child.baseline).fold(0.0, |acc, x| acc.max(x));
959
960 line.items.iter_mut().for_each(|child| {
961 let free_space = line_cross_size - child.outer_target_size.cross(dir);
962
963 if child.node.cross_margin_start(dir) == Dimension::Auto
964 && child.node.cross_margin_end(dir) == Dimension::Auto
965 {
966 if is_row {
967 child.margin.top = free_space / 2.0;
968 child.margin.bottom = free_space / 2.0;
969 } else {
970 child.margin.start = free_space / 2.0;
971 child.margin.end = free_space / 2.0;
972 }
973 } else if child.node.cross_margin_start(dir) == Dimension::Auto {
974 if is_row {
975 child.margin.top = free_space;
976 } else {
977 child.margin.start = free_space;
978 }
979 } else if child.node.cross_margin_end(dir) == Dimension::Auto {
980 if is_row {
981 child.margin.bottom = free_space;
982 } else {
983 child.margin.end = free_space;
984 }
985 } else {
986 // 14. Align all flex items along the cross-axis per align-self, if neither of the item’s
987 // cross-axis margins are auto.
988
989 child.offset_cross = match child.node.align_self(node) {
990 AlignSelf::Auto => 0.0, // Should never happen
991 AlignSelf::FlexStart => {
992 if is_wrap_reverse {
993 free_space
994 } else {
995 0.0
996 }
997 }
998 AlignSelf::FlexEnd => {
999 if is_wrap_reverse {
1000 0.0
1001 } else {
1002 free_space
1003 }
1004 }
1005 AlignSelf::Center => free_space / 2.0,
1006 AlignSelf::Baseline => {
1007 if is_row {
1008 max_baseline - child.baseline
1009 } else {
1010 // baseline alignment only makes sense if the direction is row
1011 // we treat it as flex-start alignment in columns.
1012 if is_wrap_reverse {
1013 free_space
1014 } else {
1015 0.0
1016 }
1017 }
1018 }
1019 AlignSelf::Stretch => {
1020 if is_wrap_reverse {
1021 free_space
1022 } else {
1023 0.0
1024 }
1025 }
1026 };
1027 }
1028 });
1029 });
1030
1031 // 15. Determine the flex container’s used cross size:
1032 // - If the cross size property is a definite size, use that, clamped by the used
1033 // min and max cross sizes of the flex container.
1034 // - Otherwise, use the sum of the flex lines' cross sizes, clamped by the used
1035 // min and max cross sizes of the flex container.
1036
1037 let total_cross_size: f32 = flex_lines.iter().map(|line| line.cross_size).sum();
1038 container_size.set_cross(dir, node_size.cross(dir).or_else(total_cross_size + padding_border.cross(dir)));
1039 inner_container_size.set_cross(dir, container_size.cross(dir) - padding_border.cross(dir));
1040
1041 // We have the container size. If our caller does not care about performing
1042 // layout we are done now.
1043 if !perform_layout {
1044 let result = ComputeResult { size: container_size, children: vec![] };
1045 node.layout_cache.replace(Some(LayoutCache {
1046 node_size,
1047 parent_size,
1048 percent_calc_base,
1049 perform_layout,
1050 result: result.clone(),
1051 }));
1052 return result;
1053 }
1054
1055 // 16. Align all flex lines per align-content.
1056
1057 let free_space = inner_container_size.cross(dir) - total_cross_size;
1058 let num_lines = flex_lines.len();
1059
1060 let align_line = |(i, line): (usize, &mut FlexLine)| {
1061 let is_first = i == 0;
1062
1063 line.offset_cross = match node.align_content {
1064 AlignContent::FlexStart => {
1065 if is_first && is_wrap_reverse {
1066 free_space
1067 } else {
1068 0.0
1069 }
1070 }
1071 AlignContent::FlexEnd => {
1072 if is_first && !is_wrap_reverse {
1073 free_space
1074 } else {
1075 0.0
1076 }
1077 }
1078 AlignContent::Center => {
1079 if is_first {
1080 free_space / 2.0
1081 } else {
1082 0.0
1083 }
1084 }
1085 AlignContent::Stretch => 0.0,
1086 AlignContent::SpaceBetween => {
1087 if is_first {
1088 0.0
1089 } else {
1090 free_space / (num_lines - 1) as f32
1091 }
1092 }
1093 AlignContent::SpaceAround => {
1094 if is_first {
1095 (free_space / num_lines as f32) / 2.0
1096 } else {
1097 free_space / num_lines as f32
1098 }
1099 }
1100 };
1101 };
1102
1103 if is_wrap_reverse {
1104 flex_lines.iter_mut().rev().enumerate().for_each(align_line);
1105 } else {
1106 flex_lines.iter_mut().enumerate().for_each(align_line);
1107 }
1108
1109 // Do a final layout pass and gather the resulting layouts
1110 let mut children: Vec<layout::Node> = {
1111 let mut lines: Vec<Vec<layout::Node>> = vec![];
1112 let mut total_offset_cross = padding_border.cross_start(dir);
1113
1114 let layout_line = |line: &mut FlexLine| {
1115 let mut children: Vec<layout::Node> = vec![];
1116 let mut total_offset_main = padding_border.main_start(dir);
1117 let line_offset_cross = line.offset_cross;
1118
1119 let layout_item = |child: &mut FlexItem| {
1120 let result = compute_internal(
1121 child.node,
1122 child.target_size.map(|s| s.to_number()),
1123 container_size.map(|s| s.to_number()),
1124 percent_calc_base_child,
1125 true,
1126 );
1127
1128 let offset_main = total_offset_main
1129 + child.offset_main
1130 + child.margin.main_start(dir)
1131 + (child.position.main_start(dir).or_else(0.0) - child.position.main_end(dir).or_else(0.0));
1132
1133 let offset_cross = total_offset_cross
1134 + child.offset_cross
1135 + line_offset_cross
1136 + child.margin.cross_start(dir)
1137 + (child.position.cross_start(dir).or_else(0.0) - child.position.cross_end(dir).or_else(0.0));
1138
1139 children.push(layout::Node {
1140 order: node.children.iter().position(|n| ref_eq(n, child.node)).unwrap() as u32,
1141 size: result.size,
1142 location: Point {
1143 x: if is_row { offset_main } else { offset_cross },
1144 y: if is_column { offset_main } else { offset_cross },
1145 },
1146 children: result.children,
1147 });
1148
1149 total_offset_main += child.offset_main + child.margin.main(dir) + result.size.main(dir);
1150 };
1151
1152 if dir.is_reverse() {
1153 line.items.iter_mut().rev().for_each(layout_item);
1154 } else {
1155 line.items.iter_mut().for_each(layout_item);
1156 }
1157
1158 total_offset_cross += line_offset_cross + line.cross_size;
1159
1160 if dir.is_reverse() {
1161 children.reverse();
1162 }
1163
1164 lines.push(children);
1165 };
1166
1167 if is_wrap_reverse {
1168 flex_lines.iter_mut().rev().for_each(layout_line);
1169 } else {
1170 flex_lines.iter_mut().for_each(layout_line);
1171 }
1172
1173 if is_wrap_reverse {
1174 lines.into_iter().rev().flat_map(|x| x).collect()
1175 } else {
1176 lines.into_iter().flat_map(|x| x).collect()
1177 }
1178 };
1179
1180 // Before returning we perform absolute layout on all absolutely positioned children
1181 let mut absolute_children: Vec<layout::Node> = node
1182 .children
1183 .iter()
1184 .enumerate()
1185 .filter(|(_, child)| child.position_type == PositionType::Absolute)
1186 .map(|(order, child)| {
1187 let container_width = container_size.width.to_number();
1188 let container_height = container_size.height.to_number();
1189
1190 let start = child.position.start.resolve(container_width) + child.margin.start.resolve(container_width);
1191 let end = child.position.end.resolve(container_width) + child.margin.end.resolve(container_width);
1192 let top = child.position.top.resolve(container_height) + child.margin.top.resolve(container_height);
1193 let bottom =
1194 child.position.bottom.resolve(container_height) + child.margin.bottom.resolve(container_height);
1195
1196 let (start_main, end_main) = if is_row { (start, end) } else { (top, bottom) };
1197 let (start_cross, end_cross) = if is_row { (top, bottom) } else { (start, end) };
1198
1199 let width = child
1200 .size
1201 .width
1202 .resolve(container_width)
1203 .maybe_max(child.min_size.width.resolve(container_width))
1204 .maybe_min(child.max_size.width.resolve(container_width))
1205 .or_else(if start.is_defined() && end.is_defined() {
1206 container_width - start - end
1207 } else {
1208 Undefined
1209 });
1210
1211 let height = child
1212 .size
1213 .height
1214 .resolve(container_height)
1215 .maybe_max(child.min_size.height.resolve(container_height))
1216 .maybe_min(child.max_size.height.resolve(container_height))
1217 .or_else(if top.is_defined() && bottom.is_defined() {
1218 container_height - top - bottom
1219 } else {
1220 Undefined
1221 });
1222
1223 let result = compute_internal(
1224 child,
1225 Size { width, height },
1226 Size { width: container_width, height: container_height },
1227 container_width,
1228 true,
1229 );
1230
1231 let free_main_space = container_size.main(dir)
1232 - result
1233 .size
1234 .main(dir)
1235 .maybe_max(child.min_main_size(dir).resolve(percent_calc_base_child))
1236 .maybe_min(child.max_main_size(dir).resolve(percent_calc_base_child));
1237
1238 let free_cross_space = container_size.cross(dir)
1239 - result
1240 .size
1241 .cross(dir)
1242 .maybe_max(child.min_cross_size(dir).resolve(percent_calc_base_child))
1243 .maybe_min(child.max_cross_size(dir).resolve(percent_calc_base_child));
1244
1245 let offset_main = if start_main.is_defined() {
1246 start_main.or_else(0.0) + border.main_start(dir)
1247 } else if end_main.is_defined() {
1248 free_main_space - end_main.or_else(0.0) - border.main_end(dir)
1249 } else {
1250 match node.justify_content {
1251 JustifyContent::SpaceBetween | JustifyContent::FlexStart => padding_border.main_start(dir),
1252 JustifyContent::FlexEnd => free_main_space - padding_border.main_end(dir),
1253 JustifyContent::SpaceEvenly | JustifyContent::SpaceAround | JustifyContent::Center => {
1254 free_main_space / 2.0
1255 }
1256 }
1257 };
1258
1259 let offset_cross = if start_cross.is_defined() {
1260 start_cross.or_else(0.0) + border.cross_start(dir)
1261 } else if end_cross.is_defined() {
1262 free_cross_space - end_cross.or_else(0.0) - border.cross_end(dir)
1263 } else {
1264 match child.align_self(node) {
1265 AlignSelf::Auto => 0.0, // Should never happen
1266 AlignSelf::FlexStart => {
1267 if is_wrap_reverse {
1268 free_cross_space - padding_border.cross_end(dir)
1269 } else {
1270 padding_border.cross_start(dir)
1271 }
1272 }
1273 AlignSelf::FlexEnd => {
1274 if is_wrap_reverse {
1275 padding_border.cross_start(dir)
1276 } else {
1277 free_cross_space - padding_border.cross_end(dir)
1278 }
1279 }
1280 AlignSelf::Center => free_cross_space / 2.0,
1281 AlignSelf::Baseline => free_cross_space / 2.0, // Treat as center for now until we have baseline support
1282 AlignSelf::Stretch => {
1283 if is_wrap_reverse {
1284 free_cross_space - padding_border.cross_end(dir)
1285 } else {
1286 padding_border.cross_start(dir)
1287 }
1288 }
1289 }
1290 };
1291
1292 layout::Node {
1293 order: order as u32,
1294 size: result.size,
1295 location: Point {
1296 x: if is_row { offset_main } else { offset_cross },
1297 y: if is_column { offset_main } else { offset_cross },
1298 },
1299 children: result.children,
1300 }
1301 })
1302 .collect();
1303
1304 children.append(&mut absolute_children);
1305
1306 fn hidden_layout(node: &style::Node, order: u32) -> layout::Node {
1307 layout::Node {
1308 order,
1309 size: Size { width: 0.0, height: 0.0 },
1310 location: Point { x: 0.0, y: 0.0 },
1311 children: node
1312 .children
1313 .iter()
1314 .enumerate()
1315 .map(|(order, child)| hidden_layout(child, order as _))
1316 .collect(),
1317 }
1318 }
1319
1320 let mut hidden_children: Vec<layout::Node> = node
1321 .children
1322 .iter()
1323 .enumerate()
1324 .filter(|(_, child)| child.display == Display::None)
1325 .map(|(order, child)| hidden_layout(child, order as _))
1326 .collect();
1327
1328 children.append(&mut hidden_children);
1329
1330 children.sort_by(|c1, c2| c1.order.cmp(&c2.order));
1331
1332 let result = ComputeResult { size: container_size, children };
1333 node.layout_cache.replace(Some(LayoutCache {
1334 node_size,
1335 parent_size,
1336 percent_calc_base,
1337 perform_layout,
1338 result: result.clone(),
1339 }));
1340 result
1341}