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