1//! Forest - a struct-of-arrays data structure for storing node trees.
2//!
3//! Backing data structure for `Taffy` structs.
4use crate::geometry::Size;
5use crate::layout::{Cache, Layout};
6use crate::node::{MeasureFunc, NodeId};
7use crate::style::FlexboxLayout;
8use crate::sys::{new_vec_with_capacity, ChildrenVec, ParentsVec, Vec};
9
10/// Layout information for a given [`Node`](crate::node::Node)
11///
12/// Stored in a [`Forest`].
13pub(crate) struct NodeData {
14 /// The layout strategy used by this node
15 pub(crate) style: FlexboxLayout,
16 /// The mapping from the Size<Option<f32>> (in real units) to Size<f32> (in points) for this node
17 pub(crate) measure: Option<MeasureFunc>,
18 /// The results of the layout computation
19 pub(crate) layout: Layout,
20 /// The primary cached results of the layout computation
21 pub(crate) main_size_layout_cache: Option<Cache>,
22 /// Secondary cached results of the layout computation
23 pub(crate) other_layout_cache: Option<Cache>,
24 /// Does this node's layout need to be recomputed?
25 pub(crate) is_dirty: bool,
26}
27
28impl NodeData {
29 /// Create the data for a new leaf node
30 #[must_use]
31 fn new_leaf(style: FlexboxLayout, measure: MeasureFunc) -> Self {
32 Self {
33 style,
34 measure: Some(measure),
35 main_size_layout_cache: None,
36 other_layout_cache: None,
37 layout: Layout::new(),
38 is_dirty: true,
39 }
40 }
41
42 /// Create the data for a new node
43 // TODO: why is this different from new_leaf?
44 #[must_use]
45 fn new(style: FlexboxLayout) -> Self {
46 Self {
47 style,
48 measure: None,
49 main_size_layout_cache: None,
50 other_layout_cache: None,
51 layout: Layout::new(),
52 is_dirty: true,
53 }
54 }
55
56 /// Marks a node and all of its parents (recursively) as dirty
57 ///
58 /// This clears any cached data and signals that the data must be recomputed.
59 #[inline]
60 fn mark_dirty(&mut self) {
61 self.main_size_layout_cache = None;
62 self.other_layout_cache = None;
63 self.is_dirty = true;
64 }
65}
66
67/// A collection of UI layout trees used to store [`NodeData`] associated with specific [`Nodes`](crate::node::Node)
68pub(crate) struct Forest {
69 /// The [`NodeData`] for each node stored in this forest
70 pub(crate) nodes: Vec<NodeData>,
71 /// The children of each node
72 ///
73 /// The indexes in the outer vector correspond to the position of the parent [`NodeData`]
74 pub(crate) children: Vec<ChildrenVec<NodeId>>,
75 /// The parents of each node
76 ///
77 /// The indexes in the outer vector correspond to the position of the child [`NodeData`]
78 pub(crate) parents: Vec<ParentsVec<NodeId>>,
79}
80
81impl Forest {
82 /// Creates a new [`Forest`] that can store up to `capacity` [`Nodes`](crate::node::Node) before needing to be expanded
83 #[must_use]
84 pub(crate) fn with_capacity(capacity: usize) -> Self {
85 Self {
86 nodes: new_vec_with_capacity(capacity),
87 children: new_vec_with_capacity(capacity),
88 parents: new_vec_with_capacity(capacity),
89 }
90 }
91
92 /// Adds a new unattached leaf node to the forest, and returns the [`NodeId`] of the new node
93 pub(crate) fn new_leaf(&mut self, style: FlexboxLayout, measure: MeasureFunc) -> NodeId {
94 let id = self.nodes.len();
95 self.nodes.push(NodeData::new_leaf(style, measure));
96 self.children.push(new_vec_with_capacity(0));
97 self.parents.push(new_vec_with_capacity(1));
98 id
99 }
100
101 /// Adds a new unparented node to the forest with the associated children attached, and returns the [`NodeId`] of the new node
102 pub(crate) fn new_with_children(&mut self, style: FlexboxLayout, children: ChildrenVec<NodeId>) -> NodeId {
103 let id = self.nodes.len();
104 for child in &children {
105 self.parents[*child].push(id);
106 }
107 self.nodes.push(NodeData::new(style));
108 self.children.push(children);
109 self.parents.push(new_vec_with_capacity(1));
110 id
111 }
112
113 /// Adds a `child` node to the `parent` node
114 pub(crate) fn add_child(&mut self, parent: NodeId, child: NodeId) {
115 self.parents[child].push(parent);
116 self.children[parent].push(child);
117 self.mark_dirty(parent)
118 }
119
120 /// Removes all nodes and resets the data structure
121 ///
122 /// The capacity is retained.
123 pub(crate) fn clear(&mut self) {
124 self.nodes.clear();
125 self.children.clear();
126 self.parents.clear();
127 }
128
129 /// Removes the specified `node`
130 ///
131 /// The last existing node is moved to its previous position, in order to ensure compactness.
132 /// Returns the previous [`NodeId`] of the moved node, if one was moved.
133 pub(crate) fn swap_remove(&mut self, node: NodeId) -> Option<NodeId> {
134 self.nodes.swap_remove(node);
135
136 // Now the last element is swapped in at index `node`.
137 if self.nodes.is_empty() {
138 self.children.clear();
139 self.parents.clear();
140 return None;
141 }
142
143 // Remove old node as parent from all its children.
144 for child in &self.children[node] {
145 let parents_child = &mut self.parents[*child];
146 let mut pos = 0;
147 while pos < parents_child.len() {
148 if parents_child[pos] == node {
149 parents_child.swap_remove(pos);
150 } else {
151 pos += 1;
152 }
153 }
154 }
155
156 // Remove old node as child from all its parents.
157 for parent in &self.parents[node] {
158 let childrens_parent = &mut self.children[*parent];
159 let mut pos = 0;
160 while pos < childrens_parent.len() {
161 if childrens_parent[pos] == node {
162 childrens_parent.swap_remove(pos);
163 } else {
164 pos += 1;
165 }
166 }
167 }
168
169 let last = self.nodes.len();
170
171 if last != node {
172 // Update ids for every child of the swapped in node.
173 for child in &self.children[last] {
174 for parent in &mut self.parents[*child] {
175 if *parent == last {
176 *parent = node;
177 }
178 }
179 }
180
181 // Update ids for every parent of the swapped in node.
182 for parent in &self.parents[last] {
183 for child in &mut self.children[*parent] {
184 if *child == last {
185 *child = node;
186 }
187 }
188 }
189
190 self.children.swap_remove(node);
191 self.parents.swap_remove(node);
192
193 Some(last)
194 } else {
195 self.children.swap_remove(node);
196 self.parents.swap_remove(node);
197 None
198 }
199 }
200
201 /// Breaks the link between the `parent` node and the `child` node
202 ///
203 /// The `child`'s data is not removed.
204 pub(crate) fn remove_child(&mut self, parent: NodeId, child: NodeId) -> NodeId {
205 let index = self.children[parent].iter().position(|n| *n == child).unwrap();
206 self.remove_child_at_index(parent, index)
207 }
208
209 /// Breaks the link between the `parent` node and the n-th child node
210 ///
211 /// The child's data is not removed.
212 pub(crate) fn remove_child_at_index(&mut self, parent: NodeId, child_index: usize) -> NodeId {
213 let child = self.children[parent].remove(child_index);
214 self.parents[child].retain(|p| *p != parent);
215 self.mark_dirty(parent);
216 child
217 }
218
219 /// Marks the `node` as needing layout recalculation
220 ///
221 /// Any cached layout information is cleared.
222 pub(crate) fn mark_dirty(&mut self, node: NodeId) {
223 /// Performs a recursive depth-first search up the tree until the root node is reached
224 ///
225 /// WARNING: this will stack-overflow if the tree contains a cycle
226 fn mark_dirty_recursive(nodes: &mut Vec<NodeData>, parents: &[ParentsVec<NodeId>], node_id: NodeId) {
227 nodes[node_id].mark_dirty();
228
229 for parent in &parents[node_id] {
230 mark_dirty_recursive(nodes, parents, *parent);
231 }
232 }
233
234 mark_dirty_recursive(&mut self.nodes, &self.parents, node);
235 }
236
237 /// Computes the layout of the `node` and its children
238 pub(crate) fn compute_layout(&mut self, node: NodeId, size: Size<Option<f32>>) {
239 // TODO: It's not clear why this method is distinct
240 self.compute(node, size)
241 }
242}