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