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