Add and cleanup new leaf-nodes methods (#181)
1//! UI [`Node`] types and related data structures.
2//!
3//! Layouts are composed of multiple nodes, which live in a forest-like data structure.
4use crate::error;
5use crate::forest::Forest;
6use crate::geometry::Size;
7use crate::layout::Layout;
8use crate::style::FlexboxLayout;
9#[cfg(any(feature = "std", feature = "alloc"))]
10use crate::sys::Box;
11use crate::sys::{new_map_with_capacity, ChildrenVec, Map, Vec};
12use core::sync::atomic::{AtomicUsize, Ordering};
13
14/// A function type that can be used in a [`MeasureFunc`]
15///
16/// This trait is automatically implemented for all types (including closures) that define a function with the appropriate type signature.
17pub trait Measurable: Send + Sync + Fn(Size<Option<f32>>) -> Size<f32> {}
18
19impl<F: Send + Sync + Fn(Size<Option<f32>>) -> Size<f32>> Measurable for F {}
20
21/// A function that can be used to compute the intrinsic size of a node
22pub enum MeasureFunc {
23 /// Stores an unboxed function
24 Raw(fn(Size<Option<f32>>) -> Size<f32>),
25 /// Stores a boxed function
26 #[cfg(any(feature = "std", feature = "alloc"))]
27 Boxed(Box<dyn Measurable>),
28}
29
30/// Global taffy instance id allocator.
31static INSTANCE_ALLOCATOR: Allocator = Allocator::new();
32
33/// An [`Id`]-containing identifier
34#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
35#[cfg_attr(not(any(feature = "std", feature = "alloc")), derive(hash32_derive::Hash32))]
36pub struct Node {
37 /// The id of the forest that this node lives with
38 instance: Id,
39 /// The identifier of this particular node within the tree
40 local: Id,
41}
42
43/// A forest of UI [`Nodes`](`Node`), suitable for UI layout
44pub struct Taffy {
45 /// The ID of the root node
46 id: Id,
47 /// A monotonically-increasing index that tracks the [`Id`] of the next node
48 allocator: Allocator,
49 /// A map from Node -> NodeId
50 nodes_to_ids: Map<Node, NodeId>,
51 /// A map from NodeId -> Node
52 ids_to_nodes: Map<NodeId, Node>,
53 /// An efficient data structure that stores the node trees
54 forest: Forest,
55}
56
57impl Default for Taffy {
58 fn default() -> Self {
59 Self::with_capacity(16)
60 }
61}
62
63impl Taffy {
64 /// Creates a new [`Taffy`]
65 ///
66 /// The default capacity of a [`Taffy`] is 16 nodes.
67 #[must_use]
68 pub fn new() -> Self {
69 Default::default()
70 }
71
72 /// Creates a new [`Taffy`] that can store `capacity` nodes before reallocation
73 pub fn with_capacity(capacity: usize) -> Self {
74 Self {
75 id: INSTANCE_ALLOCATOR.allocate(),
76 allocator: Allocator::new(),
77 nodes_to_ids: new_map_with_capacity(capacity),
78 ids_to_nodes: new_map_with_capacity(capacity),
79 forest: Forest::with_capacity(capacity),
80 }
81 }
82
83 /// Allocates memory for a new node, and returns a matching generated [`Node`]
84 fn allocate_node(&mut self) -> Node {
85 let local = self.allocator.allocate();
86 Node { instance: self.id, local }
87 }
88
89 /// Stores a new node in the tree
90 fn add_node(&mut self, node: Node, id: NodeId) {
91 let _ = self.nodes_to_ids.insert(node, id);
92 let _ = self.ids_to_nodes.insert(id, node);
93 }
94
95 /// Returns the `NodeId` of the provided node within the forest
96 fn find_node(&self, node: Node) -> Result<NodeId, error::InvalidNode> {
97 match self.nodes_to_ids.get(&node) {
98 Some(id) => Ok(*id),
99 None => Err(error::InvalidNode(node)),
100 }
101 }
102
103 /// Creates and adds a new leaf node
104 pub fn new_leaf(&mut self, layout: FlexboxLayout) -> Result<Node, error::InvalidNode> {
105 let node = self.allocate_node();
106 let id = self.forest.new_leaf(layout);
107 self.add_node(node, id);
108 Ok(node)
109 }
110
111 /// Creates and adds a new leaf node with a supplied [`MeasureFunc`]
112 pub fn new_leaf_with_measure(
113 &mut self,
114 layout: FlexboxLayout,
115 measure: MeasureFunc,
116 ) -> Result<Node, error::InvalidNode> {
117 let node = self.allocate_node();
118 let id = self.forest.new_leaf_with_measure(layout, measure);
119 self.add_node(node, id);
120 Ok(node)
121 }
122
123 /// Creates and adds a new node, which may have any number of `children`
124 pub fn new_with_children(&mut self, layout: FlexboxLayout, children: &[Node]) -> Result<Node, error::InvalidNode> {
125 let node = self.allocate_node();
126 let children = children
127 .iter()
128 .map(|child| self.find_node(*child))
129 .collect::<Result<ChildrenVec<_>, error::InvalidNode>>()?;
130 let id = self.forest.new_with_children(layout, children);
131 self.add_node(node, id);
132 Ok(node)
133 }
134
135 /// Removes all nodes
136 ///
137 /// All associated [`Id`] will be rendered invalid.
138 pub fn clear(&mut self) {
139 self.nodes_to_ids.clear();
140 self.ids_to_nodes.clear();
141 self.forest.clear();
142 }
143
144 /// Remove a specific [`Node`] from the tree
145 ///
146 /// Its [`Id`] is marked as invalid. Returns the id of the node removed.
147 pub fn remove(&mut self, node: Node) -> Result<usize, error::InvalidNode> {
148 let id = self.find_node(node)?;
149
150 self.nodes_to_ids.remove(&node);
151 self.ids_to_nodes.remove(&id);
152
153 if let Some(new_id) = self.forest.swap_remove(id) {
154 let new = self.ids_to_nodes.remove(&new_id).unwrap();
155 let _ = self.nodes_to_ids.insert(new, id);
156 let _ = self.ids_to_nodes.insert(id, new);
157 }
158
159 Ok(id)
160 }
161
162 /// Sets the [`MeasureFunc`] of the associated node
163 pub fn set_measure(&mut self, node: Node, measure: Option<MeasureFunc>) -> Result<(), error::InvalidNode> {
164 let id = self.find_node(node)?;
165 self.forest.nodes[id].measure = measure;
166 self.forest.mark_dirty(id);
167 Ok(())
168 }
169
170 /// Adds a `child` [`Node`] under the supplied `parent`
171 pub fn add_child(&mut self, parent: Node, child: Node) -> Result<(), error::InvalidNode> {
172 let node_id = self.find_node(parent)?;
173 let child_id = self.find_node(child)?;
174
175 self.forest.add_child(node_id, child_id);
176 Ok(())
177 }
178
179 /// Directly sets the `children` of the supplied `parent`
180 pub fn set_children(&mut self, parent: Node, children: &[Node]) -> Result<(), error::InvalidNode> {
181 let node_id = self.find_node(parent)?;
182 let children_id = children.iter().map(|child| self.find_node(*child)).collect::<Result<ChildrenVec<_>, _>>()?;
183
184 // Remove node as parent from all its current children.
185 for child in &self.forest.children[node_id] {
186 self.forest.parents[*child].retain(|p| *p != node_id);
187 }
188
189 // Build up relation node <-> child
190 for child in &children_id {
191 self.forest.parents[*child].push(node_id);
192 }
193 self.forest.children[node_id] = children_id;
194
195 self.forest.mark_dirty(node_id);
196 Ok(())
197 }
198
199 /// Removes the `child` of the parent `node`
200 ///
201 /// The child is not removed from the forest entirely, it is simply no longer attached to its previous parent.
202 pub fn remove_child(&mut self, parent: Node, child: Node) -> Result<Node, error::InvalidNode> {
203 let node_id = self.find_node(parent)?;
204 let child_id = self.find_node(child)?;
205
206 let prev_id = self.forest.remove_child(node_id, child_id);
207 Ok(self.ids_to_nodes[&prev_id])
208 }
209
210 /// Removes the child at the given `index` from the `parent`
211 ///
212 /// The child is not removed from the forest entirely, it is simply no longer attached to its previous parent.
213 pub fn remove_child_at_index(&mut self, parent: Node, child_index: usize) -> Result<Node, error::InvalidChild> {
214 let node_id = self.find_node(parent).map_err(|e| error::InvalidChild::InvalidParentNode(e.0))?;
215
216 let child_count = self.forest.children[node_id].len();
217 if child_index >= child_count {
218 return Err(error::InvalidChild::ChildIndexOutOfBounds { parent, child_index, child_count });
219 }
220
221 let prev_id = self.forest.remove_child_at_index(node_id, child_index);
222 Ok(self.ids_to_nodes[&prev_id])
223 }
224
225 /// Replaces the child at the given `child_index` from the `parent` node with the new `child` node
226 ///
227 /// The child is not removed from the forest entirely, it is simply no longer attached to its previous parent.
228 pub fn replace_child_at_index(
229 &mut self,
230 parent: Node,
231 child_index: usize,
232 new_child: Node,
233 ) -> Result<Node, error::InvalidChild> {
234 let node_id = self.find_node(parent).map_err(|e| error::InvalidChild::InvalidParentNode(e.0))?;
235 let child_id = self.find_node(new_child).map_err(|e| error::InvalidChild::InvalidChildNode(e.0))?;
236
237 let child_count = self.forest.children[node_id].len();
238 if child_index >= child_count {
239 return Err(error::InvalidChild::ChildIndexOutOfBounds { parent, child_index, child_count });
240 }
241
242 self.forest.parents[child_id].push(node_id);
243 let old_child = core::mem::replace(&mut self.forest.children[node_id][child_index], child_id);
244 self.forest.parents[old_child].retain(|p| *p != node_id);
245
246 self.forest.mark_dirty(node_id);
247
248 Ok(self.ids_to_nodes[&old_child])
249 }
250
251 /// Returns the child [`Node`] of the parent `node` at the provided `child_index`
252 pub fn child_at_index(&self, parent: Node, child_index: usize) -> Result<Node, error::InvalidChild> {
253 let id = self.find_node(parent).map_err(|e| error::InvalidChild::InvalidParentNode(e.0))?;
254
255 let child_count = self.forest.children[id].len();
256 if child_index >= child_count {
257 return Err(error::InvalidChild::ChildIndexOutOfBounds { parent, child_index, child_count });
258 }
259
260 Ok(self.ids_to_nodes[&self.forest.children[id][child_index]])
261 }
262
263 /// Returns the number of children of the `parent` [`Node`]
264 pub fn child_count(&self, parent: Node) -> Result<usize, error::InvalidNode> {
265 let id = self.find_node(parent)?;
266 Ok(self.forest.children[id].len())
267 }
268
269 /// Returns a list of children that belong to the [`Parent`]
270 pub fn children(&self, parent: Node) -> Result<Vec<Node>, error::InvalidNode> {
271 let id = self.find_node(parent)?;
272 Ok(self.forest.children[id].iter().map(|child| self.ids_to_nodes[child]).collect())
273 }
274
275 /// Sets the [`Style`] of the provided `node`
276 pub fn set_style(&mut self, node: Node, style: FlexboxLayout) -> Result<(), error::InvalidNode> {
277 let id = self.find_node(node)?;
278 self.forest.nodes[id].style = style;
279 self.forest.mark_dirty(id);
280 Ok(())
281 }
282
283 /// Gets the [`Style`] of the provided `node`
284 pub fn style(&self, node: Node) -> Result<&FlexboxLayout, error::InvalidNode> {
285 let id = self.find_node(node)?;
286 Ok(&self.forest.nodes[id].style)
287 }
288
289 /// Return this node layout relative to its parent
290 pub fn layout(&self, node: Node) -> Result<&Layout, error::InvalidNode> {
291 let id = self.find_node(node)?;
292 Ok(&self.forest.nodes[id].layout)
293 }
294
295 /// Marks the layout computation of this node and its children as outdated
296 pub fn mark_dirty(&mut self, node: Node) -> Result<(), error::InvalidNode> {
297 let id = self.find_node(node)?;
298 self.forest.mark_dirty(id);
299 Ok(())
300 }
301
302 /// Indicates whether the layout of this node (and its children) need to be recomputed
303 pub fn dirty(&self, node: Node) -> Result<bool, error::InvalidNode> {
304 let id = self.find_node(node)?;
305 Ok(self.forest.nodes[id].is_dirty)
306 }
307
308 /// Updates the stored layout of the provided `node` and its children
309 pub fn compute_layout(&mut self, node: Node, size: Size<Option<f32>>) -> Result<(), error::InvalidNode> {
310 let id = self.find_node(node)?;
311 self.forest.compute_layout(id, size);
312 Ok(())
313 }
314}
315
316/// Internal node id.
317pub(crate) type NodeId = usize;
318
319/// The identifier of a [`Node`]
320#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
321#[cfg_attr(not(any(feature = "std", feature = "alloc")), derive(hash32_derive::Hash32))]
322pub(crate) struct Id(usize);
323
324/// An bump-allocator index that tracks how many [`Nodes`](Node) have been allocated in a [`Taffy`].
325pub(crate) struct Allocator {
326 /// The last reserved [`NodeId`]
327 last_id: AtomicUsize,
328}
329
330impl Allocator {
331 /// Creates a fresh [`Allocator`]
332 #[must_use]
333 pub const fn new() -> Self {
334 Self { last_id: AtomicUsize::new(0) }
335 }
336
337 /// Allocates space for one more [`Node`]
338 pub fn allocate(&self) -> Id {
339 Id(self.last_id.fetch_add(1, Ordering::Relaxed))
340 }
341}
342
343#[cfg(test)]
344mod tests {
345 use super::*;
346
347 #[test]
348 fn measure_func_is_send_and_sync() {
349 fn is_send_and_sync<T: Send + Sync>() {}
350 is_send_and_sync::<MeasureFunc>();
351 }
352}