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