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