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