⎇ c9c40576df24056c2f0f8b421d8046d33bb1cc2d
src/compute/morphorm.rs
Ñawpa willay
Pi imata llamkarqan
ch'uya
1use crate::compute::LayoutAlgorithm;
2use crate::geometry::{Line, Point, Rect, Size};
3use crate::style::{
4 AlignContent, AlignItems, AlignSelf, AvailableSpace, Dimension, Display, FlexWrap, JustifyContent,
5 LengthPercentageAuto, Position,
6};
7use crate::style::{FlexDirection, Style};
8use crate::tree::LayoutTree;
9use crate::tree::NodeId;
10use crate::util::{MaybeMath, MaybeResolve};
11use crate::tree::{Layout, RunMode, SizeBaselinesAndMargins, SizingMode};
12
13/// The public interface to Taffy's Flexbox algorithm implementation
14pub struct MorphormAlgorithm;
15impl LayoutAlgorithm for MorphormAlgorithm {
16 const NAME: &'static str = "MORPHORM";
17
18 fn perform_layout(
19 tree: &mut impl LayoutTree,
20 node: NodeId,
21 known_dimensions: Size<Option<f32>>,
22 parent_size: Size<Option<f32>>,
23 available_space: Size<AvailableSpace>,
24 _sizing_mode: SizingMode,
25 _vertical_margins_are_collapsible: Line<bool>,
26 ) -> SizeBaselinesAndMargins {
27 compute(tree, node, known_dimensions, parent_size, available_space, RunMode::PerformLayout)
28 }
29
30 fn measure_size(
31 tree: &mut impl LayoutTree,
32 node: NodeId,
33 known_dimensions: Size<Option<f32>>,
34 parent_size: Size<Option<f32>>,
35 available_space: Size<AvailableSpace>,
36 _sizing_mode: SizingMode,
37 _vertical_margins_are_collapsible: Line<bool>,
38 ) -> Size<f32> {
39 compute(tree, node, known_dimensions, parent_size, available_space, RunMode::ComputeSize).size
40 }
41}
42
43#[derive(Debug)]
44pub struct ChildNode {
45 // A reference to the node.
46 node: NodeId,
47 // Whether the child is in flow or not
48 is_in_flow: bool,
49 is_first: bool,
50 is_last: bool,
51 // The index of the node.
52 index: usize,
53
54 style: Style,
55
56 size: Size<f32>,
57
58 spacing: Rect<f32>,
59
60 // // The stretch factor of the node.
61 // stretch_factor: Size<f32>,
62 // // The minimum constraint of the node.
63 // min: Size<Option<f32>>,
64 // // The maximum constraint of the node.
65 // max: Size<Option<f32>>,
66
67 // // Sum of the flex factors on the main axis of the node.
68 // main_flex_sum: f32,
69 // // The available free space on the main axis of the node.
70 // main_non_flex: f32,
71 // // A remainder used during stretch computation.
72 // main_remainder: f32,
73 // // Sum of the cross_before, cross, and cross_after flex factors of the node.
74 // cross_flex_sum: f32,
75
76 // cross_non_flex: f32,
77 // cross: f32,
78 // cross_remainder: f32,
79
80 // // Computed main-before space of the node.
81 // main_before: f32,
82 // // Computed main-after space of the node.
83 // main_after: f32,
84 // // Computed cross-before space of the node.
85 // cross_before: f32,
86 // // Computed cross-after space of the node.
87 // cross_after: f32,
88}
89
90/// Computes the layout of [`LayoutTree`] according to the flexbox algorithm
91pub fn compute(
92 tree: &mut impl LayoutTree,
93 node: NodeId,
94 known_dimensions: Size<Option<f32>>,
95 parent_size: Size<Option<f32>>,
96 available_space: Size<AvailableSpace>,
97 run_mode: RunMode,
98) -> SizeBaselinesAndMargins {
99 // TODO: Min/Max constraints for space and size
100
101 // The layout type of the node. Determines the main and cross axes of the children.
102 let container_style = tree.style(node).clone();
103 let dir = container_style.flex_direction;
104 let is_row = dir.is_row();
105
106 let min_size = container_style.min_size.maybe_resolve(parent_size);
107 let max_size = container_style.max_size.maybe_resolve(parent_size);
108 let clamped_style_size = container_style.size.maybe_resolve(parent_size).maybe_clamp(min_size, max_size);
109
110 // If both min and max in a given axis are set and max <= min then this determines the size in that axis
111 let min_max_definite_size = min_size.zip_map(max_size, |min, max| match (min, max) {
112 (Some(min), Some(max)) if max <= min => Some(min),
113 _ => None,
114 });
115 let styled_based_known_dimensions = known_dimensions.or(min_max_definite_size).or(clamped_style_size);
116
117 // Short-circuit layout if the container's size is fully determined by the container's size and the run mode
118 // is ComputeSize (and thus the container's size is all that we're interested in)
119 if run_mode == RunMode::ComputeSize {
120 if let Size { width: Some(width), height: Some(height) } = styled_based_known_dimensions {
121 return Size { width, height }.into();
122 }
123 }
124
125 let in_flow_children: Vec<ChildNode> = tree
126 .children(node)
127 .map(|child| (child, tree.style(*child)))
128 .filter(|(_, style)| style.position != Position::Absolute)
129 .filter(|(_, style)| style.display != Display::None)
130 .enumerate()
131 .map(|(index, (child, child_style))| {
132 ChildNode {
133 node,
134 is_first: false, // Set later
135 is_last: false, // Set later
136 is_in_flow: child_style.position != Position::Absolute,
137 index,
138 style: child_style.clone(),
139 size: Size::zero(), // Set later
140 spacing: Rect::zero(), // Set later
141 }
142 })
143 .collect();
144
145 // Set is_first and is_last properties on the first and last children
146 let in_flow_child_count = in_flow_children.len();
147 in_flow_children[0].is_first = true;
148 in_flow_children[in_flow_children.len() - 1].is_last = true;
149
150
151 // Compute size and spacing for each child
152 let space_around = container_style.spacing_around.resolve_or_zero(parent_size);
153 let space_between = container_style.spacing_between.resolve_or_zero(parent_size);
154 for child in in_flow_children.iter_mut() {
155 let child_min_size = child.style.min_size.maybe_resolve(parent_size);
156 let max_size = child.style.max_size.maybe_resolve(parent_size);
157 let clamped_style_size = child.style.size.maybe_resolve(parent_size).maybe_clamp(min_size, max_size);
158
159 // If both min and max in a given axis are set and max <= min then this determines the size in that axis
160 let min_max_definite_size = min_size.zip_map(max_size, |min, max| match (min, max) {
161 (Some(min), Some(max)) if max <= min => Some(min),
162 _ => None,
163 });
164 let child_style_based_known_dimensions = min_max_definite_size.or(clamped_style_size);
165
166 // Compute content size if size is not already known and the item has an "auto" dimension
167 let has_auto_dimension =
168 child.style.size.width == Dimension::Auto || child.style.size.height == Dimension::Auto;
169 let content_size: Size<Option<f32>> =
170 if !child_style_based_known_dimensions.both_axis_defined() && has_auto_dimension {
171 GenericAlgorithm::measure_size(
172 tree,
173 node,
174 known_dimensions,
175 parent_size,
176 available_space,
177 SizingMode::InherentSize,
178 )
179 .map(Some)
180 } else {
181 child_style_based_known_dimensions
182 };
183
184 child.size = child_style_based_known_dimensions.or(content_size).unwrap_or(Size::zero()).maybe_clamp(min_size, max_size);
185
186 let default_spacing = {
187 let mut space = space_around;
188 if !child.is_first {
189 space.set_main_start(dir, space_between.main(dir));
190 }
191 if !child.is_last {
192 space.set_main_end(dir, 0.0);
193 }
194 };
195
196 let resolved_margin = child.style.margin.map(|m| m.resolve_to_option(0.0));
197 let outer_spacing = resolved_margin.unwrap_or(space_around);
198
199 }
200
201 // Compute space used by the content size of each no in each axis
202 let main_axis_used_space: f32 =
203 in_flow_children.iter().map(|child| child.size.main(dir) + child.spacing.main_axis_sum(dir)).sum();
204 let cross_axis_used_space: f32 = in_flow_children
205 .iter()
206 .map(|child| child.size.cross(dir) + child.spacing.cross_axis_sum(dir))
207 .max_by(|a, b| a.total_cmp(b))
208 .unwrap_or(0.0);
209 let used_space = {
210 let mut space = Size::zero();
211 space.set_main(dir, main_axis_used_space);
212 space.set_cross(dir, cross_axis_used_space);
213 space
214 };
215 let container_size = styled_based_known_dimensions.unwrap_or(used_space);
216
217 // Return early if we're only computing container size
218 if run_mode == RunMode::ComputeSize {
219 return container_size.into();
220 }
221
222 let free_space = container_size - used_space;
223
224 // TODO perform stretch sizing
225 // TODO position nodes
226
227
228 // Sum of all non-flexible space and size on the main-axis of the node.
229 let mut main_non_flex = 0.0f32;
230
231 // Sum of all space and size flex factors on the main-axis of the node.
232 let mut main_flex_sum = 0.0;
233
234 // Sum of all child nodes on the main-axis.
235 let mut main_sum = 0.0f32;
236
237 // Maximum of all child nodes on the cross-axis.
238 let mut cross_max = 0.0f32;
239
240 // List of child nodes for the current node.
241 let mut children = SmallVec::<[ChildNode<N>; 3]>::new();
242
243 // List of stretch nodes for the current node.
244 // A stretch node is any flexible space/size. e.g. main_before, main, and main_after are separate stretch nodes
245 let mut stretch_nodes = SmallVec::<[StretchNode<N>; 3]>::new();
246
247 // Parent overrides for child auto space.
248 let node_child_main_before = node.child_main_before(store, layout_type);
249 let node_child_main_after = node.child_main_after(store, layout_type);
250 let node_child_cross_before = node.child_cross_before(store, layout_type);
251 let node_child_cross_after = node.child_cross_after(store, layout_type);
252 let node_child_main_between = node.main_between(store, layout_type);
253
254 // Determine index of first and last parent-directed child nodes.
255 let mut iter = node
256 .children(tree)
257 .enumerate()
258 .filter(|(_, child)| child.position_type(store).unwrap_or_default() == PositionType::ParentDirected);
259
260 let first = iter.next().map(|(index, _)| index);
261 let last = iter.last().map_or(first, |(index, _)| Some(index));
262
263 let num_children = node.children(tree).count();
264
265 // Compute non-flexible children.
266 for (index, child) in node.children(tree).enumerate() {
267 let child_position_type = child.position_type(store).unwrap_or_default();
268
269 let mut child_main_before = child.main_before(store, layout_type);
270 let child_main = child.main(store, layout_type);
271 let mut child_main_after = child.main_after(store, layout_type);
272
273 let mut child_cross_before = child.cross_before(store, layout_type);
274 let child_cross = child.cross(store, layout_type);
275 let mut child_cross_after = child.cross_after(store, layout_type);
276
277 // Apply parent overrides to auto child space.
278 if child_main_before == Units::Auto {
279 if first == Some(index) || child_position_type == PositionType::SelfDirected {
280 child_main_before = node_child_main_before;
281 } else {
282 child_main_before = node_child_main_between;
283 }
284 }
285
286 if child_main_after == Units::Auto && (last == Some(index) || child_position_type == PositionType::SelfDirected)
287 {
288 child_main_after = node_child_main_after;
289 }
290
291 if child_cross_before == Units::Auto {
292 child_cross_before = node_child_cross_before;
293 }
294
295 if child_cross_after == Units::Auto {
296 child_cross_after = node_child_cross_after;
297 }
298
299 // Sum of flex factors on the main and cross axes of the child node.
300 let mut child_main_flex_sum = 0.0;
301 let mut child_cross_flex_sum = 0.0;
302
303 let mut computed_child_main_before = 0.0;
304 let mut computed_child_main = 0.0;
305 let mut computed_child_main_after = 0.0;
306
307 let mut computed_child_cross_before = 0.0;
308 let mut computed_child_cross = 0.0;
309 let mut computed_child_cross_after = 0.0;
310
311 match child_cross_before {
312 Pixels(val) => {
313 computed_child_cross_before = val;
314 }
315
316 Percentage(val) => {
317 computed_child_cross_before = (parent_cross * (val / 100.0)).round();
318 }
319
320 Stretch(factor) => {
321 child_cross_flex_sum += factor;
322 }
323
324 _ => {}
325 }
326
327 let child_min_cross_before = child.min_cross_before(store, layout_type).to_px(parent_cross, DEFAULT_MIN);
328 let child_max_cross_before = child.max_cross_before(store, layout_type).to_px(parent_cross, DEFAULT_MAX);
329
330 computed_child_cross_before = computed_child_cross_before.clamp(child_min_cross_before, child_max_cross_before);
331
332 match child_cross_after {
333 Pixels(val) => {
334 computed_child_cross_after = val;
335 }
336
337 Percentage(val) => {
338 computed_child_cross_after = (parent_cross * (val / 100.0)).round();
339 }
340
341 Stretch(factor) => {
342 child_cross_flex_sum += factor;
343 }
344
345 _ => {}
346 }
347
348 let child_min_cross_after = child.min_cross_after(store, layout_type).to_px(parent_cross, DEFAULT_MIN);
349 let child_max_cross_after = child.max_cross_after(store, layout_type).to_px(parent_cross, DEFAULT_MAX);
350
351 computed_child_cross_after = computed_child_cross_after.clamp(child_min_cross_after, child_max_cross_after);
352
353 match child_cross {
354 Pixels(val) => {
355 computed_child_cross = val;
356 }
357
358 Percentage(val) => {
359 computed_child_cross = (parent_cross * (val / 100.0)).round();
360 }
361
362 Stretch(factor) => {
363 child_cross_flex_sum += factor;
364 }
365
366 _ => {}
367 }
368
369 let child_min_cross = child.min_cross(store, layout_type).to_px(parent_cross, DEFAULT_MIN);
370 let child_max_cross = child.max_cross(store, layout_type).to_px(parent_cross, DEFAULT_MAX);
371
372 computed_child_cross = computed_child_cross.clamp(child_min_cross, child_max_cross);
373
374 let child_min_main_before = child.min_main_before(store, layout_type).to_px(parent_main, DEFAULT_MIN);
375 let child_max_main_before = child.max_main_before(store, layout_type).to_px(parent_main, DEFAULT_MAX);
376
377 match child_main_before {
378 Pixels(val) => {
379 computed_child_main_before = val;
380 }
381
382 Percentage(val) => {
383 computed_child_main_before = (parent_main * (val / 100.0)).round();
384 }
385
386 Stretch(factor) => {
387 child_main_flex_sum += factor;
388
389 stretch_nodes.push(StretchNode {
390 node: child,
391 index,
392 factor,
393 min: child_min_main_before,
394 max: child_max_main_before,
395 axis: Axis::MainBefore,
396 });
397 }
398
399 _ => {}
400 }
401
402 computed_child_main_before = computed_child_main_before.clamp(child_min_main_before, child_max_main_before);
403
404 let child_min_main_after = child.min_main_after(store, layout_type).to_px(parent_main, DEFAULT_MIN);
405 let child_max_main_after = child.max_main_after(store, layout_type).to_px(parent_main, DEFAULT_MAX);
406
407 match child_main_after {
408 Pixels(val) => {
409 computed_child_main_after = val;
410 }
411
412 Percentage(val) => {
413 computed_child_main_after = (parent_main * (val / 100.0)).round();
414 }
415
416 Stretch(factor) => {
417 child_main_flex_sum += factor;
418
419 stretch_nodes.push(StretchNode {
420 node: child,
421 index,
422 factor,
423 min: child_min_main_after,
424 max: child_max_main_after,
425 axis: Axis::MainAfter,
426 });
427 }
428
429 _ => {}
430 }
431
432 computed_child_main_after = computed_child_main_after.clamp(child_min_main_after, child_max_main_after);
433
434 // Total computed size on the cross-axis of the child.
435 let mut child_cross_non_flex = computed_child_cross_before + computed_child_cross + computed_child_cross_after;
436
437 match child_main {
438 Stretch(factor) => {
439 child_main_flex_sum += factor;
440
441 stretch_nodes.push(StretchNode {
442 node: child,
443 index,
444 factor,
445 min: DEFAULT_MIN,
446 max: DEFAULT_MAX,
447 axis: Axis::Main,
448 });
449 }
450
451 _ => {
452 let child_size = layout(child, layout_type, parent_main, computed_child_cross, cache, tree, store);
453
454 computed_child_main = child_size.main;
455 computed_child_cross = child_size.cross;
456
457 if child_cross == Units::Auto {
458 child_cross_non_flex += computed_child_cross;
459 }
460 }
461 }
462
463 // Total computed size on the main-axis of the child.
464 let child_main_non_flex = computed_child_main_before + computed_child_main + computed_child_main_after;
465
466 if child_position_type == PositionType::ParentDirected {
467 main_non_flex += child_main_non_flex;
468 main_flex_sum += child_main_flex_sum;
469
470 main_sum += child_main_non_flex;
471 } else {
472 main_sum = main_sum.max(child_main_non_flex);
473 }
474
475 cross_max = cross_max.max(child_cross_non_flex);
476
477 children.push(ChildNode {
478 node: child,
479 main_flex_sum: child_main_flex_sum,
480 main_non_flex: child_main_non_flex,
481 main_remainder: 0.0,
482 cross_flex_sum: child_cross_flex_sum,
483 cross_non_flex: child_cross_non_flex,
484 cross: computed_child_cross,
485 cross_remainder: 0.0,
486 main_before: computed_child_main_before,
487 main_after: computed_child_main_after,
488 cross_before: computed_child_cross_before,
489 cross_after: computed_child_cross_after,
490 });
491 }
492
493 // Calculate free space on the main-axis for the node.
494 let free_main_space = (parent_main.max(main_sum) - main_non_flex).max(0.0);
495 let mut remainder: f32 = 0.0;
496 let main_px_per_flex = free_main_space / main_flex_sum;
497
498 // Compute flexible space and size on the main axis.
499 for item in stretch_nodes.iter() {
500 let child_position_type = item.node.position_type(store).unwrap_or_default();
501
502 let actual_main = if child_position_type == PositionType::SelfDirected {
503 let child_main_free_space = (parent_main.max(main_sum) - children[item.index].main_non_flex).max(0.0);
504 let px_per_flex = child_main_free_space / children[item.index].main_flex_sum;
505 let desired_main = item.factor * px_per_flex + children[item.index].main_remainder;
506 let actual_main = desired_main.round();
507 children[item.index].main_remainder = desired_main - actual_main;
508 actual_main
509 } else {
510 let desired_main = item.factor * main_px_per_flex + remainder;
511 let actual_main = desired_main.round();
512 remainder = desired_main - actual_main;
513 actual_main
514 };
515
516 let computed_child_cross = children[item.index].cross;
517
518 match item.axis {
519 Axis::MainBefore => {
520 children[item.index].main_before = actual_main;
521 }
522
523 Axis::MainAfter => {
524 children[item.index].main_after = actual_main;
525 }
526
527 Axis::Main => {
528 let child_size = layout(item.node, layout_type, actual_main, computed_child_cross, cache, tree, store);
529
530 children[item.index].cross_non_flex += child_size.cross;
531 cross_max = cross_max.max(children[item.index].cross_non_flex);
532 }
533 }
534 }
535
536 // Compute flexible space and size on the cross-axis.
537 // This needs to be done after computing the main-axis because layout computation for stretch children may cause
538 // the cross space to change due to content size.
539 for child in children.iter_mut() {
540 let child_cross_free_space = parent_cross.max(cross_max) - child.cross_non_flex;
541 let cross_px_per_flex = child_cross_free_space / child.cross_flex_sum;
542
543 let child_cross_before = child.node.cross_before(store, layout_type);
544 let child_cross = child.node.cross(store, layout_type);
545 let child_cross_after = child.node.cross_after(store, layout_type);
546
547 if let Stretch(factor) = child_cross_before {
548 let desired_cross = factor * cross_px_per_flex + child.cross_remainder;
549 let actual_cross = desired_cross.round();
550 child.cross_remainder = desired_cross - actual_cross;
551 child.cross_before = actual_cross;
552 }
553
554 if let Stretch(factor) = child_cross {
555 let desired_cross = factor * cross_px_per_flex + child.cross_remainder;
556 let actual_cross = desired_cross.round();
557 child.cross_remainder = desired_cross - actual_cross;
558
559 // if cross == Units::Auto && num_children != 0 {
560 let size = layout(child.node, layout_type, parent_main, actual_cross, cache, tree, store);
561 // println!("size: {:?}", size);
562 // } else {
563 // At this stage stretch nodes on the cross-axis can only be the determined size so we can set it directly
564 // in the cache without needing to call layout again.
565 // match layout_type {
566 // LayoutType::Row => {
567 // cache.set_height(child.node.key(), actual_cross);
568 // }
569
570 // LayoutType::Column => {
571 // cache.set_width(child.node.key(), actual_cross);
572 // }
573 // }
574 // }
575 }
576
577 if let Stretch(factor) = child_cross_after {
578 let desired_cross = factor * cross_px_per_flex + child.cross_remainder;
579 let actual_cross = desired_cross.round();
580 child.cross_remainder = desired_cross - actual_cross;
581 child.cross_after = actual_cross;
582 }
583 }
584
585 // Position children.
586 let mut main_pos = 0.0;
587 for child in children.iter() {
588 let child_position_type = child.node.position_type(store).unwrap_or_default();
589
590 match child_position_type {
591 PositionType::SelfDirected => match layout_type {
592 LayoutType::Row => {
593 cache.set_posx(child.node.key(), child.main_before);
594 cache.set_posy(child.node.key(), child.cross_before);
595 }
596
597 LayoutType::Column => {
598 cache.set_posy(child.node.key(), child.main_before);
599 cache.set_posx(child.node.key(), child.cross_before);
600 }
601 },
602
603 PositionType::ParentDirected => {
604 main_pos += child.main_before;
605
606 match layout_type {
607 LayoutType::Row => {
608 cache.set_posx(child.node.key(), main_pos);
609 cache.set_posy(child.node.key(), child.cross_before);
610 let child_width = cache.width(child.node.key());
611 main_pos += child_width;
612 }
613
614 LayoutType::Column => {
615 cache.set_posy(child.node.key(), main_pos);
616 cache.set_posx(child.node.key(), child.cross_before);
617 let child_height = cache.height(child.node.key());
618 main_pos += child_height;
619 }
620 }
621
622 main_pos += child.main_after;
623 }
624 };
625 }
626
627 // This part is required for auto size when the node has children but conflicts with the content size when the node doesn't have children
628 // TODO: Make it so a node can only have content size if it has no children?
629 // TODO: Potentially split and move this to before stretch calculations.
630 if num_children != 0 {
631 if parent_layout_type == layout_type {
632 if let Auto = main {
633 computed_main = main_sum;
634 }
635
636 if let Auto = cross {
637 computed_cross = cross_max;
638 }
639 } else {
640 if let Auto = main {
641 computed_main = cross_max;
642 }
643
644 if let Auto = cross {
645 computed_cross = main_sum;
646 }
647 }
648 }
649
650 // Set the computed size of the node in the cache.
651 match parent_layout_type {
652 LayoutType::Row => {
653 cache.set_width(node.key(), computed_main);
654 cache.set_height(node.key(), computed_cross);
655 }
656
657 LayoutType::Column => {
658 cache.set_height(node.key(), computed_main);
659 cache.set_width(node.key(), computed_cross);
660 }
661 }
662
663 // Return the computed size, propagating it back up the tree.
664 Size { main: computed_main, cross: computed_cross }.into()
665}