1//! Forest - a struct-of-arrays data structure for storing node trees.
2//!
3//! Backing data structure for `Taffy` structs.
4use crate::layout::{Cache, Layout};
5use crate::node::{MeasureFunc, NodeId};
6use crate::style::FlexboxLayout;
7use crate::sys::{new_vec_with_capacity, ChildrenVec, ParentsVec, Vec};
8
9/// Layout information for a given [`Node`](crate::node::Node)
10///
11/// Stored in a [`Forest`].
12pub(crate) struct NodeData {
13 /// The layout strategy used by this node
14 pub(crate) style: FlexboxLayout,
15 /// The mapping from the Size<Option<f32>> (in real units) to Size<f32> (in points) for this node
16 pub(crate) measure: Option<MeasureFunc>,
17 /// The results of the layout computation
18 pub(crate) layout: Layout,
19 /// The primary cached results of the layout computation
20 pub(crate) main_size_layout_cache: Option<Cache>,
21 /// Secondary cached results of the layout computation
22 pub(crate) other_layout_cache: Option<Cache>,
23 /// Does this node's layout need to be recomputed?
24 pub(crate) is_dirty: bool,
25}
26
27impl NodeData {
28 /// Create the data for a new node with a [`MeasureFunc`]
29 #[must_use]
30 fn new_with_measure(style: FlexboxLayout, measure: MeasureFunc) -> Self {
31 Self {
32 style,
33 measure: Some(measure),
34 main_size_layout_cache: None,
35 other_layout_cache: None,
36 layout: Layout::new(),
37 is_dirty: true,
38 }
39 }
40
41 /// Create the data for a new node
42 #[must_use]
43 fn new(style: FlexboxLayout) -> Self {
44 Self {
45 style,
46 measure: None,
47 main_size_layout_cache: None,
48 other_layout_cache: None,
49 layout: Layout::new(),
50 is_dirty: true,
51 }
52 }
53
54 /// Marks a node and all of its parents (recursively) as dirty
55 ///
56 /// This clears any cached data and signals that the data must be recomputed.
57 #[inline]
58 fn mark_dirty(&mut self) {
59 self.main_size_layout_cache = None;
60 self.other_layout_cache = None;
61 self.is_dirty = true;
62 }
63}
64
65/// A collection of UI layout trees used to store [`NodeData`] associated with specific [`Nodes`](crate::node::Node)
66pub(crate) struct Forest {
67 /// The [`NodeData`] for each node stored in this forest
68 pub(crate) nodes: Vec<NodeData>,
69 /// The children of each node
70 ///
71 /// The indexes in the outer vector correspond to the position of the parent [`NodeData`]
72 pub(crate) children: Vec<ChildrenVec<NodeId>>,
73 /// The parents of each node
74 ///
75 /// The indexes in the outer vector correspond to the position of the child [`NodeData`]
76 pub(crate) parents: Vec<ParentsVec<NodeId>>,
77}
78
79impl Forest {
80 /// Creates a new [`Forest`] that can store up to `capacity` [`Nodes`](crate::node::Node) before needing to be expanded
81 #[must_use]
82 pub(crate) fn with_capacity(capacity: usize) -> Self {
83 Self {
84 nodes: new_vec_with_capacity(capacity),
85 children: new_vec_with_capacity(capacity),
86 parents: new_vec_with_capacity(capacity),
87 }
88 }
89
90 /// Creates and adds a new unattached leaf node to the forest, and returns the [`NodeId`] of the new node
91 pub(crate) fn new_leaf(&mut self, layout: FlexboxLayout) -> NodeId {
92 let id = self.len();
93 self.nodes.push(NodeData::new(layout));
94 self.children.push(new_vec_with_capacity(0));
95 self.parents.push(new_vec_with_capacity(1));
96 id
97 }
98
99 /// Creates and adds a new unattached leaf node to the forest, and returns the [`NodeId`] of the new node
100 ///
101 /// The node must have a [`MeasureFunc`] supplied
102 pub(crate) fn new_leaf_with_measure(&mut self, layout: FlexboxLayout, measure: MeasureFunc) -> NodeId {
103 let id = self.len();
104 self.nodes.push(NodeData::new_with_measure(layout, measure));
105 self.children.push(new_vec_with_capacity(0));
106 self.parents.push(new_vec_with_capacity(1));
107 id
108 }
109
110 /// Creates and adds a new unparented node to the forest with the associated children attached, and returns the [`NodeId`] of the new node
111 pub(crate) fn new_with_children(&mut self, layout: FlexboxLayout, children: ChildrenVec<NodeId>) -> NodeId {
112 let id = self.len();
113 for child in &children {
114 self.parents[*child].push(id);
115 }
116 self.nodes.push(NodeData::new(layout));
117 self.children.push(children);
118 self.parents.push(new_vec_with_capacity(1));
119 id
120 }
121
122 /// Adds a `child` node to the `parent` node
123 pub(crate) fn add_child(&mut self, parent: NodeId, child: NodeId) {
124 self.parents[child].push(parent);
125 self.children[parent].push(child);
126 self.mark_dirty(parent)
127 }
128
129 /// Removes all nodes and resets the data structure
130 ///
131 /// The capacity is retained.
132 pub(crate) fn clear(&mut self) {
133 self.nodes.clear();
134 self.children.clear();
135 self.parents.clear();
136 }
137
138 /// Removes the specified `node`
139 ///
140 /// The last existing node is moved to its previous position, in order to ensure compactness.
141 /// Returns the previous [`NodeId`] of the moved node, if one was moved.
142 pub(crate) fn swap_remove(&mut self, node: NodeId) -> Option<NodeId> {
143 self.nodes.swap_remove(node);
144
145 // Now the last element is swapped in at index `node`.
146 if self.nodes.is_empty() {
147 self.children.clear();
148 self.parents.clear();
149 return None;
150 }
151
152 // Remove old node as parent from all its children.
153 for child in &self.children[node] {
154 let parents_child = &mut self.parents[*child];
155 let mut pos = 0;
156 while pos < parents_child.len() {
157 if parents_child[pos] == node {
158 parents_child.swap_remove(pos);
159 } else {
160 pos += 1;
161 }
162 }
163 }
164
165 // Remove old node as child from all its parents.
166 for parent in &self.parents[node] {
167 let childrens_parent = &mut self.children[*parent];
168 let mut pos = 0;
169 while pos < childrens_parent.len() {
170 if childrens_parent[pos] == node {
171 childrens_parent.swap_remove(pos);
172 } else {
173 pos += 1;
174 }
175 }
176 }
177
178 let last = self.len();
179 if last != node {
180 // Update ids for every child of the swapped in node.
181 for child in &self.children[last] {
182 for parent in &mut self.parents[*child] {
183 if *parent == last {
184 *parent = node;
185 }
186 }
187 }
188
189 // Update ids for every parent of the swapped in node.
190 for parent in &self.parents[last] {
191 for child in &mut self.children[*parent] {
192 if *child == last {
193 *child = node;
194 }
195 }
196 }
197
198 self.children.swap_remove(node);
199 self.parents.swap_remove(node);
200
201 Some(last)
202 } else {
203 self.children.swap_remove(node);
204 self.parents.swap_remove(node);
205 None
206 }
207 }
208
209 /// Breaks the link between the `parent` node and the `child` node
210 ///
211 /// The `child`'s data is not removed.
212 pub(crate) fn remove_child(&mut self, parent: NodeId, child: NodeId) -> NodeId {
213 let index = self.children[parent].iter().position(|n| *n == child).unwrap();
214 self.remove_child_at_index(parent, index)
215 }
216
217 /// Breaks the link between the `parent` node and the n-th child node
218 ///
219 /// The child's data is not removed.
220 pub(crate) fn remove_child_at_index(&mut self, parent: NodeId, child_index: usize) -> NodeId {
221 let child = self.children[parent].remove(child_index);
222 self.parents[child].retain(|p| *p != parent);
223 self.mark_dirty(parent);
224 child
225 }
226
227 /// Marks the `node` as needing layout recalculation
228 ///
229 /// Any cached layout information is cleared.
230 pub(crate) fn mark_dirty(&mut self, node: NodeId) {
231 /// Performs a recursive depth-first search up the tree until the root node is reached
232 ///
233 /// WARNING: this will stack-overflow if the tree contains a cycle
234 fn mark_dirty_recursive(nodes: &mut Vec<NodeData>, parents: &[ParentsVec<NodeId>], node_id: NodeId) {
235 nodes[node_id].mark_dirty();
236
237 for parent in &parents[node_id] {
238 mark_dirty_recursive(nodes, parents, *parent);
239 }
240 }
241
242 mark_dirty_recursive(&mut self.nodes, &self.parents, node);
243 }
244
245 /// Returns the number of elements in the forest.
246 #[inline]
247 pub(crate) fn len(&self) -> usize {
248 // This could be either [nodes], [parents] or [children] since they all must always have
249 // the same length, given the data structure properties.
250 self.nodes.len()
251 }
252}
253
254#[cfg(test)]
255mod tests {
256 use super::{Forest, NodeData};
257 use crate::geometry::Size;
258 use crate::node::{MeasureFunc, NodeId};
259 use crate::style::FlexboxLayout;
260 use crate::sys::ChildrenVec;
261
262 fn assert_forest_size(forest: &Forest, size: usize) {
263 // This should assert the forest consistency, each vector must be have the same length
264 assert_eq!(forest.nodes.len(), size);
265 assert_eq!(forest.children.len(), size);
266 assert_eq!(forest.parents.len(), size);
267 }
268
269 fn node_measure_eq(node: &NodeData, measure_fn: fn(Size<Option<f32>>) -> Size<f32>) -> bool {
270 match node.measure.as_ref().unwrap() {
271 MeasureFunc::Raw(m) => measure_fn(Size::NONE) == m(Size::NONE),
272 #[cfg(any(feature = "std", feature = "alloc"))]
273 _ => false,
274 }
275 }
276
277 fn add_default_leaf(forest: &mut Forest) -> NodeId {
278 forest.new_leaf(FlexboxLayout::default())
279 }
280
281 /// Generates a non-default FlexboxLayout that is used to compare NodeData instances
282 fn get_non_default_layout(val: f32) -> FlexboxLayout {
283 FlexboxLayout { flex_grow: val, ..Default::default() }
284 }
285
286 #[test]
287 fn new_leaf_first_leaf() {
288 let mut forest = Forest::with_capacity(1);
289 let s1 = get_non_default_layout(1.0);
290
291 let id = forest.new_leaf(s1);
292
293 let node = &forest.nodes[id];
294 assert_eq!(id, 0);
295 assert_eq!(node.style, s1);
296 assert_forest_size(&forest, 1);
297 }
298
299 #[test]
300 fn new_leaf_second_leaf() {
301 let mut forest = Forest::with_capacity(2);
302 let s1 = get_non_default_layout(1.0);
303 let s2 = get_non_default_layout(2.0);
304 forest.new_leaf(s1);
305 let id = forest.new_leaf(s2);
306
307 let node = &forest.nodes[id];
308 assert_eq!(id, 1);
309 assert_eq!(node.style, s2);
310 assert_forest_size(&forest, 2);
311 }
312
313 #[test]
314 fn new_leaf_with_measure_first_leaf() {
315 let mut forest = Forest::with_capacity(1);
316 let s1 = get_non_default_layout(1.0);
317 let measure_fn1 = |_| Size { width: 1.0, height: 1.0 };
318
319 let id = forest.new_leaf_with_measure(s1, MeasureFunc::Raw(measure_fn1));
320
321 let node = &forest.nodes[id];
322 assert_eq!(id, 0);
323 assert_eq!(node.style, s1);
324 assert!(node_measure_eq(&node, measure_fn1));
325 assert_forest_size(&forest, 1);
326 }
327
328 #[test]
329 fn new_leaf_with_measure_second_leaf() {
330 let mut forest = Forest::with_capacity(2);
331 let s1 = get_non_default_layout(1.0);
332 let s2 = get_non_default_layout(2.0);
333 let measure_fn1 = |_| Size { width: 1.0, height: 1.0 };
334 let measure_fn2 = |_| Size { width: 2.0, height: 2.0 };
335
336 forest.new_leaf_with_measure(s1, MeasureFunc::Raw(measure_fn1));
337 let id = forest.new_leaf_with_measure(s2, MeasureFunc::Raw(measure_fn2));
338
339 let node = &forest.nodes[id];
340 assert_eq!(id, 1);
341 assert_eq!(node.style, s2);
342 assert!(node_measure_eq(&node, measure_fn2));
343 assert_forest_size(&forest, 2);
344 }
345
346 #[test]
347 fn new_with_children_single() {
348 let mut forest = Forest::with_capacity(2);
349 let style = get_non_default_layout(1.0);
350 let c1_id = add_default_leaf(&mut forest);
351 let children = ChildrenVec::from_iter([c1_id]);
352
353 let id = forest.new_with_children(style, children);
354 let new_node = &forest.nodes[id];
355
356 assert_eq!(id, 1);
357 assert_eq!(new_node.style, style);
358 assert_eq!(forest.parents[c1_id][0], id);
359 assert_eq!(forest.children[id][0], c1_id);
360 assert_forest_size(&forest, 2);
361 }
362
363 #[test]
364 fn new_with_children_multiple() {
365 let mut forest = Forest::with_capacity(3);
366 let style = get_non_default_layout(1.0);
367 let c1_id = add_default_leaf(&mut forest);
368 let c2_id = add_default_leaf(&mut forest);
369 let children = ChildrenVec::from_iter([c1_id, c2_id]);
370
371 let id = forest.new_with_children(style, children);
372 let new_node = &forest.nodes[id];
373
374 assert_eq!(id, 2);
375 assert_eq!(new_node.style, style);
376 assert_eq!(forest.parents[c1_id][0], id);
377 assert_eq!(forest.parents[c2_id][0], id);
378 assert_eq!(forest.children[id][0], c1_id);
379 assert_eq!(forest.children[id][1], c2_id);
380 assert_forest_size(&forest, 3);
381 }
382
383 #[test]
384 fn add_child() {
385 let mut forest = Forest::with_capacity(2);
386 let parent_id = add_default_leaf(&mut forest);
387 let child_id = add_default_leaf(&mut forest);
388 forest.add_child(parent_id, child_id);
389
390 let parent = &forest.nodes[parent_id];
391
392 assert_eq!(forest.parents[child_id][0], parent_id);
393 assert_eq!(forest.children[parent_id][0], child_id);
394 assert!(parent.is_dirty);
395 }
396
397 #[test]
398 fn add_child_multiple() {
399 let mut forest = Forest::with_capacity(3);
400 let parent_id = add_default_leaf(&mut forest);
401 let c1_id = add_default_leaf(&mut forest);
402 let c2_id = add_default_leaf(&mut forest);
403 forest.add_child(parent_id, c1_id);
404 forest.add_child(parent_id, c2_id);
405
406 let parent = &forest.nodes[parent_id];
407
408 assert_eq!(forest.parents[c1_id][0], parent_id);
409 assert_eq!(forest.parents[c2_id][0], parent_id);
410 assert_eq!(forest.children[parent_id][0], c1_id);
411 assert_eq!(forest.children[parent_id][1], c2_id);
412 assert!(parent.is_dirty);
413 }
414
415 #[test]
416 fn clear() {
417 let mut forest = Forest::with_capacity(1);
418 add_default_leaf(&mut forest);
419 forest.clear();
420 assert_forest_size(&forest, 0);
421 }
422
423 #[test]
424 fn swap_remove_single() {
425 let mut forest = Forest::with_capacity(1);
426 let parent_id = add_default_leaf(&mut forest);
427
428 let moved_id = forest.swap_remove(parent_id);
429
430 assert_eq!(moved_id, None);
431 assert_forest_size(&forest, 0);
432 }
433
434 #[test]
435 fn swap_remove_parent() {
436 let mut forest = Forest::with_capacity(3);
437 let parent_id = add_default_leaf(&mut forest);
438 let c1_id = add_default_leaf(&mut forest);
439 let c2_id = add_default_leaf(&mut forest);
440 forest.add_child(parent_id, c1_id);
441 forest.add_child(parent_id, c2_id);
442
443 let moved_id = forest.swap_remove(parent_id);
444 let new_c1_id = parent_id.clone();
445 let new_c2_id = c1_id.clone();
446
447 assert_eq!(moved_id, Some(c2_id));
448 assert_eq!(forest.parents[new_c1_id].len(), 0);
449 assert_eq!(forest.parents[new_c2_id].len(), 0);
450 assert_forest_size(&forest, 2);
451 }
452
453 #[test]
454 fn swap_remove_parent_nested() {
455 let mut forest = Forest::with_capacity(3);
456 let parent_id = add_default_leaf(&mut forest);
457 let c1_id = add_default_leaf(&mut forest);
458 let c2_id = add_default_leaf(&mut forest);
459 forest.add_child(parent_id, c1_id);
460 forest.add_child(c1_id, c2_id);
461
462 let moved_id = forest.swap_remove(parent_id);
463 let new_c1_id = c1_id.clone();
464 let new_c2_id = parent_id.clone();
465
466 assert_eq!(moved_id, Some(c2_id));
467 assert_eq!(forest.parents[new_c1_id].len(), 0);
468 assert_eq!(forest.parents[new_c2_id].len(), 1);
469 assert_eq!(forest.parents[new_c2_id][0], new_c1_id);
470 assert_forest_size(&forest, 2);
471 }
472
473 #[test]
474 fn swap_remove_first_child_nested() {
475 let mut forest = Forest::with_capacity(3);
476 let parent_id = add_default_leaf(&mut forest);
477 let c1_id = add_default_leaf(&mut forest);
478 let c2_id = add_default_leaf(&mut forest);
479 forest.add_child(parent_id, c1_id);
480 forest.add_child(parent_id, c2_id);
481
482 let moved_id = forest.swap_remove(c1_id);
483 let new_c2_id = c1_id.clone();
484
485 assert_eq!(moved_id, Some(c2_id));
486 assert_eq!(forest.children[parent_id].len(), 1);
487 assert_eq!(forest.children[parent_id][0], new_c2_id);
488 assert_eq!(forest.parents[new_c2_id].len(), 1);
489 assert_eq!(forest.parents[new_c2_id][0], parent_id);
490 assert_forest_size(&forest, 2);
491 }
492
493 #[test]
494 fn swap_remove_last_child_nested() {
495 let mut forest = Forest::with_capacity(3);
496 let parent_id = add_default_leaf(&mut forest);
497 let c1_id = add_default_leaf(&mut forest);
498 let c2_id = add_default_leaf(&mut forest);
499 forest.add_child(parent_id, c1_id);
500 forest.add_child(parent_id, c2_id);
501
502 let moved_id = forest.swap_remove(c2_id);
503
504 assert_eq!(moved_id, None);
505 assert_eq!(forest.children[parent_id].len(), 1);
506 assert_eq!(forest.parents[c1_id].len(), 1);
507 assert_forest_size(&forest, 2);
508 }
509
510 #[test]
511 fn swap_remove_disjoint() {
512 let mut forest = Forest::with_capacity(2);
513 let n1_id = add_default_leaf(&mut forest);
514 let n2_id = add_default_leaf(&mut forest);
515
516 let moved_id = forest.swap_remove(n1_id);
517
518 assert_eq!(moved_id, Some(n2_id));
519 assert_forest_size(&forest, 1);
520 }
521
522 #[test]
523 fn remove_child() {
524 let mut forest = Forest::with_capacity(3);
525 let layout = get_non_default_layout(1.0);
526 let parent_id = add_default_leaf(&mut forest);
527 let c1_id = forest.new_leaf(layout);
528 let c2_id = add_default_leaf(&mut forest);
529 forest.add_child(parent_id, c1_id);
530 forest.add_child(parent_id, c2_id);
531
532 let removed_id = forest.remove_child(parent_id, c1_id);
533 let parent = &forest.nodes[parent_id];
534
535 // node data should be preserved
536 assert_forest_size(&forest, 3);
537 assert_eq!(forest.nodes[removed_id].style, layout);
538 assert_eq!(forest.children[parent_id].len(), 1);
539 assert_eq!(forest.parents[c1_id].len(), 0);
540 assert_eq!(forest.parents[c2_id].len(), 1);
541 assert_eq!(removed_id, c1_id);
542 assert!(parent.is_dirty);
543 }
544
545 #[test]
546 fn remove_child_at_index() {
547 let mut forest = Forest::with_capacity(3);
548 let layout = get_non_default_layout(1.0);
549 let parent_id = add_default_leaf(&mut forest);
550 let c1_id = forest.new_leaf(layout);
551 let c2_id = add_default_leaf(&mut forest);
552 forest.add_child(parent_id, c1_id);
553 forest.add_child(parent_id, c2_id);
554
555 let removed_id = forest.remove_child_at_index(parent_id, 0);
556 let parent = &forest.nodes[parent_id];
557
558 // node data should be preserved
559 assert_forest_size(&forest, 3);
560 assert_eq!(&forest.nodes[removed_id].style, &layout);
561 assert_eq!(forest.children[parent_id].len(), 1);
562 assert_eq!(forest.parents[c1_id].len(), 0);
563 assert_eq!(forest.parents[c2_id].len(), 1);
564 assert_eq!(removed_id, c1_id);
565 assert!(parent.is_dirty);
566 }
567
568 #[test]
569 fn mark_dirty_propagates_to_parents() {
570 let mut forest = Forest::with_capacity(3);
571 let parent_id = add_default_leaf(&mut forest);
572 let c1_id = add_default_leaf(&mut forest);
573 let c2_id = add_default_leaf(&mut forest);
574 forest.add_child(parent_id, c1_id);
575 forest.add_child(c1_id, c2_id);
576
577 forest.mark_dirty(c2_id);
578
579 assert!(forest.nodes[c2_id].is_dirty);
580 assert!(forest.nodes[c1_id].is_dirty);
581 assert!(forest.nodes[parent_id].is_dirty);
582 }
583
584 #[test]
585 fn len_zero() {
586 let forest = Forest::with_capacity(1);
587 assert_eq!(forest.len(), 0);
588 }
589
590 #[test]
591 fn len_multiple() {
592 let mut forest = Forest::with_capacity(2);
593 _ = add_default_leaf(&mut forest);
594 _ = add_default_leaf(&mut forest);
595 assert_eq!(forest.len(), 2);
596 }
597}