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