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