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