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