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