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