Make CacheMut an associated type
1//! Contains [TaffyTree](crate::tree::TaffyTree): the default implementation of [LayoutTree](crate::tree::LayoutTree), and the error type for Taffy.
2#[cfg(not(feature = "std"))]
3use slotmap::SecondaryMap;
4#[cfg(feature = "std")]
5use slotmap::SparseSecondaryMap as SecondaryMap;
6use slotmap::{DefaultKey, SlotMap};
7
8use crate::geometry::Size;
9use crate::style::{AvailableSpace, Display, Style};
10use crate::tree::{
11 Cache, Layout, LayoutInput, LayoutOutput, LayoutPartialTree, NodeId, PrintTree, RoundTree, RunMode,
12 TraversePartialTree, TraverseTree,
13};
14use crate::util::debug::{debug_log, debug_log_node};
15use crate::util::sys::{new_vec_with_capacity, ChildrenVec, Vec};
16
17#[cfg(feature = "block_layout")]
18use crate::compute::compute_block_layout;
19#[cfg(feature = "flexbox")]
20use crate::compute::compute_flexbox_layout;
21#[cfg(feature = "grid")]
22use crate::compute::compute_grid_layout;
23use crate::compute::{
24 compute_cached_layout, compute_hidden_layout, compute_leaf_layout, compute_root_layout, round_layout,
25};
26use crate::{LayoutBlockContainer, LayoutFlexboxContainer, LayoutGridContainer};
27
28/// The error Taffy generates on invalid operations
29pub type TaffyResult<T> = Result<T, TaffyError>;
30
31/// An error that occurs while trying to access or modify a node's children by index.
32#[derive(Debug)]
33pub enum TaffyError {
34 /// The parent node does not have a child at `child_index`. It only has `child_count` children
35 ChildIndexOutOfBounds {
36 /// The parent node whose child was being looked up
37 parent: NodeId,
38 /// The index that was looked up
39 child_index: usize,
40 /// The total number of children the parent has
41 child_count: usize,
42 },
43 /// The parent node was not found in the [`TaffyTree`](crate::TaffyTree) instance.
44 InvalidParentNode(NodeId),
45 /// The child node was not found in the [`TaffyTree`](crate::TaffyTree) instance.
46 InvalidChildNode(NodeId),
47 /// The supplied node was not found in the [`TaffyTree`](crate::TaffyTree) instance.
48 InvalidInputNode(NodeId),
49}
50
51impl core::fmt::Display for TaffyError {
52 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
53 match self {
54 TaffyError::ChildIndexOutOfBounds { parent, child_index, child_count } => {
55 write!(f, "Index (is {child_index}) should be < child_count ({child_count}) for parent node {parent:?}")
56 }
57 TaffyError::InvalidParentNode(parent) => {
58 write!(f, "Parent Node {parent:?} is not in the TaffyTree instance")
59 }
60 TaffyError::InvalidChildNode(child) => write!(f, "Child Node {child:?} is not in the TaffyTree instance"),
61 TaffyError::InvalidInputNode(node) => write!(f, "Supplied Node {node:?} is not in the TaffyTree instance"),
62 }
63 }
64}
65
66#[cfg(feature = "std")]
67impl std::error::Error for TaffyError {}
68
69/// Global configuration values for a TaffyTree instance
70pub(crate) struct TaffyConfig {
71 /// Whether to round layout values
72 pub(crate) use_rounding: bool,
73}
74
75impl Default for TaffyConfig {
76 fn default() -> Self {
77 Self { use_rounding: true }
78 }
79}
80
81/// Layout information for a given [`Node`](crate::node::Node)
82///
83/// Stored in a [`TaffyTree`].
84struct NodeData {
85 /// The layout strategy used by this node
86 pub(crate) style: Style,
87
88 /// The always unrounded results of the layout computation. We must store this separately from the rounded
89 /// layout to avoid errors from rounding already-rounded values. See <https://github.com/DioxusLabs/taffy/issues/501>.
90 pub(crate) unrounded_layout: Layout,
91
92 /// The final results of the layout computation.
93 /// These may be rounded or unrounded depending on what the `use_rounding` config setting is set to.
94 pub(crate) final_layout: Layout,
95
96 /// Whether the node has context data associated with it or not
97 pub(crate) has_context: bool,
98
99 /// The cached results of the layout computation
100 pub(crate) cache: Cache,
101}
102
103impl NodeData {
104 /// Create the data for a new node
105 #[must_use]
106 pub const fn new(style: Style) -> Self {
107 Self {
108 style,
109 cache: Cache::new(),
110 unrounded_layout: Layout::new(),
111 final_layout: Layout::new(),
112 has_context: false,
113 }
114 }
115
116 /// Marks a node and all of its parents (recursively) as dirty
117 ///
118 /// This clears any cached data and signals that the data must be recomputed.
119 #[inline]
120 pub fn mark_dirty(&mut self) {
121 self.cache.clear()
122 }
123}
124
125/// An entire tree of UI nodes. The entry point to Taffy's high-level API.
126///
127/// Allows you to build a tree of UI nodes, run Taffy's layout algorithms over that tree, and then access the resultant layout.
128pub struct TaffyTree<NodeContext = ()> {
129 /// The [`NodeData`] for each node stored in this tree
130 nodes: SlotMap<DefaultKey, NodeData>,
131
132 /// Functions/closures that compute the intrinsic size of leaf nodes
133 node_context_data: SecondaryMap<DefaultKey, NodeContext>,
134
135 /// The children of each node
136 ///
137 /// The indexes in the outer vector correspond to the position of the parent [`NodeData`]
138 children: SlotMap<DefaultKey, ChildrenVec<NodeId>>,
139
140 /// The parents of each node
141 ///
142 /// The indexes in the outer vector correspond to the position of the child [`NodeData`]
143 parents: SlotMap<DefaultKey, Option<NodeId>>,
144
145 /// Layout mode configuration
146 config: TaffyConfig,
147}
148
149impl Default for TaffyTree {
150 fn default() -> TaffyTree<()> {
151 TaffyTree::new()
152 }
153}
154
155/// Iterator that wraps a slice of nodes, lazily converting them to u64
156pub struct TaffyTreeChildIter<'a>(core::slice::Iter<'a, NodeId>);
157impl<'a> Iterator for TaffyTreeChildIter<'a> {
158 type Item = NodeId;
159
160 fn next(&mut self) -> Option<Self::Item> {
161 self.0.next().copied()
162 }
163}
164
165// TraversePartialTree impl for TaffyTree
166impl<NodeContext> TraversePartialTree for TaffyTree<NodeContext> {
167 type ChildIter<'a> = TaffyTreeChildIter<'a> where Self: 'a;
168
169 #[inline(always)]
170 fn child_ids(&self, parent_node_id: NodeId) -> Self::ChildIter<'_> {
171 TaffyTreeChildIter(self.children[parent_node_id.into()].iter())
172 }
173
174 #[inline(always)]
175 fn child_count(&self, parent_node_id: NodeId) -> usize {
176 self.children[parent_node_id.into()].len()
177 }
178
179 #[inline(always)]
180 fn get_child_id(&self, parent_node_id: NodeId, id: usize) -> NodeId {
181 self.children[parent_node_id.into()][id]
182 }
183}
184
185// TraverseTree impl for TaffyTree
186impl<NodeContext> TraverseTree for TaffyTree<NodeContext> {}
187
188// PrintTree impl for TaffyTree
189impl<NodeContext> PrintTree for TaffyTree<NodeContext> {
190 #[inline(always)]
191 fn get_debug_label(&self, node_id: NodeId) -> &'static str {
192 let node = &self.nodes[node_id.into()];
193 let display = node.style.display;
194 let num_children = self.child_count(node_id);
195
196 match (num_children, display) {
197 (_, Display::None) => "NONE",
198 (0, _) => "LEAF",
199 #[cfg(feature = "block_layout")]
200 (_, Display::Block) => "BLOCK",
201 #[cfg(feature = "flexbox")]
202 (_, Display::Flex) => {
203 use crate::FlexDirection;
204 match node.style.flex_direction {
205 FlexDirection::Row | FlexDirection::RowReverse => "FLEX ROW",
206 FlexDirection::Column | FlexDirection::ColumnReverse => "FLEX COL",
207 }
208 }
209 #[cfg(feature = "grid")]
210 (_, Display::Grid) => "GRID",
211 }
212 }
213
214 #[inline(always)]
215 fn get_final_layout(&self, node_id: NodeId) -> &Layout {
216 &self.nodes[node_id.into()].final_layout
217 }
218}
219
220/// View over the Taffy tree that holds the tree itself along with a reference to the context
221/// and implements LayoutTree. This allows the context to be stored outside of the TaffyTree struct
222/// which makes the lifetimes of the context much more flexible.
223pub(crate) struct TaffyView<'t, NodeContext, MeasureFunction>
224where
225 MeasureFunction:
226 FnMut(Size<Option<f32>>, Size<AvailableSpace>, NodeId, Option<&mut NodeContext>, &Style) -> Size<f32>,
227{
228 /// A reference to the TaffyTree
229 pub(crate) taffy: &'t mut TaffyTree<NodeContext>,
230 /// The context provided for passing to measure functions if layout is run over this struct
231 pub(crate) measure_function: MeasureFunction,
232}
233
234// TraversePartialTree impl for TaffyView
235impl<'t, NodeContext, MeasureFunction> TraversePartialTree for TaffyView<'t, NodeContext, MeasureFunction>
236where
237 MeasureFunction:
238 FnMut(Size<Option<f32>>, Size<AvailableSpace>, NodeId, Option<&mut NodeContext>, &Style) -> Size<f32>,
239{
240 type ChildIter<'a> = TaffyTreeChildIter<'a> where Self: 'a;
241
242 #[inline(always)]
243 fn child_ids(&self, parent_node_id: NodeId) -> Self::ChildIter<'_> {
244 self.taffy.child_ids(parent_node_id)
245 }
246
247 #[inline(always)]
248 fn child_count(&self, parent_node_id: NodeId) -> usize {
249 self.taffy.child_count(parent_node_id)
250 }
251
252 #[inline(always)]
253 fn get_child_id(&self, parent_node_id: NodeId, child_index: usize) -> NodeId {
254 self.taffy.get_child_id(parent_node_id, child_index)
255 }
256}
257
258// TraverseTree impl for TaffyView
259impl<'t, NodeContext, MeasureFunction> TraverseTree for TaffyView<'t, NodeContext, MeasureFunction> where
260 MeasureFunction:
261 FnMut(Size<Option<f32>>, Size<AvailableSpace>, NodeId, Option<&mut NodeContext>, &Style) -> Size<f32>
262{
263}
264
265// LayoutPartialTree impl for TaffyView
266impl<'t, NodeContext, MeasureFunction> LayoutPartialTree for TaffyView<'t, NodeContext, MeasureFunction>
267where
268 MeasureFunction:
269 FnMut(Size<Option<f32>>, Size<AvailableSpace>, NodeId, Option<&mut NodeContext>, &Style) -> Size<f32>,
270{
271 type CoreContainerStyle<'a> = &'a Style where Self : 'a;
272 type CacheMut<'b> = &'b mut Cache where Self : 'b;
273
274 #[inline(always)]
275 fn get_core_container_style(&self, node_id: NodeId) -> Self::CoreContainerStyle<'_> {
276 &self.taffy.nodes[node_id.into()].style
277 }
278
279 #[inline(always)]
280 fn get_cache_mut(&mut self, node: NodeId) -> &mut Cache {
281 &mut self.taffy.nodes[node.into()].cache
282 }
283
284 #[inline(always)]
285 fn set_unrounded_layout(&mut self, node_id: NodeId, layout: &Layout) {
286 self.taffy.nodes[node_id.into()].unrounded_layout = *layout;
287 }
288
289 #[inline(always)]
290 fn compute_child_layout(&mut self, node: NodeId, inputs: LayoutInput) -> LayoutOutput {
291 // If RunMode is PerformHiddenLayout then this indicates that an ancestor node is `Display::None`
292 // and thus that we should lay out this node using hidden layout regardless of it's own display style.
293 if inputs.run_mode == RunMode::PerformHiddenLayout {
294 debug_log!("HIDDEN");
295 return compute_hidden_layout(self, node);
296 }
297
298 // We run the following wrapped in "compute_cached_layout", which will check the cache for an entry matching the node and inputs and:
299 // - Return that entry if exists
300 // - Else call the passed closure (below) to compute the result
301 //
302 // If there was no cache match and a new result needs to be computed then that result will be added to the cache
303 compute_cached_layout(self, node, inputs, |tree, node, inputs| {
304 let display_mode = tree.taffy.nodes[node.into()].style.display;
305 let has_children = tree.child_count(node) > 0;
306
307 debug_log!(display_mode);
308 debug_log_node!(
309 inputs.known_dimensions,
310 inputs.parent_size,
311 inputs.available_space,
312 inputs.run_mode,
313 inputs.sizing_mode
314 );
315
316 // Dispatch to a layout algorithm based on the node's display style and whether the node has children or not.
317 match (display_mode, has_children) {
318 (Display::None, _) => compute_hidden_layout(tree, node),
319 #[cfg(feature = "block_layout")]
320 (Display::Block, true) => compute_block_layout(tree, node, inputs),
321 #[cfg(feature = "flexbox")]
322 (Display::Flex, true) => compute_flexbox_layout(tree, node, inputs),
323 #[cfg(feature = "grid")]
324 (Display::Grid, true) => compute_grid_layout(tree, node, inputs),
325 (_, false) => {
326 let node_key = node.into();
327 let style = &tree.taffy.nodes[node_key].style;
328 let has_context = tree.taffy.nodes[node_key].has_context;
329 let node_context = has_context.then(|| tree.taffy.node_context_data.get_mut(node_key)).flatten();
330 let measure_function = |known_dimensions, available_space| {
331 (tree.measure_function)(known_dimensions, available_space, node, node_context, style)
332 };
333 compute_leaf_layout(inputs, style, measure_function)
334 }
335 }
336 })
337 }
338}
339
340impl<'t, NodeContext, MeasureFunction> LayoutBlockContainer for TaffyView<'t, NodeContext, MeasureFunction>
341where
342 MeasureFunction:
343 FnMut(Size<Option<f32>>, Size<AvailableSpace>, NodeId, Option<&mut NodeContext>, &Style) -> Size<f32>,
344{
345 type ContainerStyle<'a> = &'a Style where Self: 'a;
346 type ItemStyle<'a> = &'a Style where Self: 'a;
347
348 #[inline(always)]
349 fn get_block_container_style(&self, node_id: NodeId) -> Self::ContainerStyle<'_> {
350 self.get_core_container_style(node_id)
351 }
352
353 #[inline(always)]
354 fn get_block_child_style(&self, child_node_id: NodeId) -> Self::ItemStyle<'_> {
355 self.get_core_container_style(child_node_id)
356 }
357}
358
359impl<'t, NodeContext, MeasureFunction> LayoutFlexboxContainer for TaffyView<'t, NodeContext, MeasureFunction>
360where
361 MeasureFunction:
362 FnMut(Size<Option<f32>>, Size<AvailableSpace>, NodeId, Option<&mut NodeContext>, &Style) -> Size<f32>,
363{
364 type ContainerStyle<'a> = &'a Style where Self: 'a;
365 type ItemStyle<'a> = &'a Style where Self: 'a;
366
367 #[inline(always)]
368 fn get_flexbox_container_style(&self, node_id: NodeId) -> Self::ContainerStyle<'_> {
369 &self.taffy.nodes[node_id.into()].style
370 }
371
372 #[inline(always)]
373 fn get_flexbox_child_style(&self, child_node_id: NodeId) -> Self::ItemStyle<'_> {
374 &self.taffy.nodes[child_node_id.into()].style
375 }
376}
377
378impl<'t, NodeContext, MeasureFunction> LayoutGridContainer for TaffyView<'t, NodeContext, MeasureFunction>
379where
380 MeasureFunction:
381 FnMut(Size<Option<f32>>, Size<AvailableSpace>, NodeId, Option<&mut NodeContext>, &Style) -> Size<f32>,
382{
383 type ContainerStyle<'a> = &'a Style where Self: 'a;
384 type ItemStyle<'a> = &'a Style where Self: 'a;
385
386 #[inline(always)]
387 fn get_grid_container_style(&self, node_id: NodeId) -> Self::ContainerStyle<'_> {
388 &self.taffy.nodes[node_id.into()].style
389 }
390
391 #[inline(always)]
392 fn get_grid_child_style(&self, child_node_id: NodeId) -> Self::ItemStyle<'_> {
393 &self.taffy.nodes[child_node_id.into()].style
394 }
395}
396
397// RoundTree impl for TaffyView
398impl<'t, NodeContext, MeasureFunction> RoundTree for TaffyView<'t, NodeContext, MeasureFunction>
399where
400 MeasureFunction:
401 FnMut(Size<Option<f32>>, Size<AvailableSpace>, NodeId, Option<&mut NodeContext>, &Style) -> Size<f32>,
402{
403 #[inline(always)]
404 fn get_unrounded_layout(&self, node: NodeId) -> &Layout {
405 &self.taffy.nodes[node.into()].unrounded_layout
406 }
407
408 #[inline(always)]
409 fn set_final_layout(&mut self, node_id: NodeId, layout: &Layout) {
410 self.taffy.nodes[node_id.into()].final_layout = *layout;
411 }
412}
413
414#[allow(clippy::iter_cloned_collect)] // due to no-std support, we need to use `iter_cloned` instead of `collect`
415impl<NodeContext> TaffyTree<NodeContext> {
416 /// Creates a new [`TaffyTree`]
417 ///
418 /// The default capacity of a [`TaffyTree`] is 16 nodes.
419 #[must_use]
420 pub fn new() -> Self {
421 Self::with_capacity(16)
422 }
423
424 /// Creates a new [`TaffyTree`] that can store `capacity` nodes before reallocation
425 #[must_use]
426 pub fn with_capacity(capacity: usize) -> Self {
427 TaffyTree {
428 // TODO: make this method const upstream,
429 // so constructors here can be const
430 nodes: SlotMap::with_capacity(capacity),
431 children: SlotMap::with_capacity(capacity),
432 parents: SlotMap::with_capacity(capacity),
433 node_context_data: SecondaryMap::with_capacity(capacity),
434 config: TaffyConfig::default(),
435 }
436 }
437
438 /// Enable rounding of layout values. Rounding is enabled by default.
439 pub fn enable_rounding(&mut self) {
440 self.config.use_rounding = true;
441 }
442
443 /// Disable rounding of layout values. Rounding is enabled by default.
444 pub fn disable_rounding(&mut self) {
445 self.config.use_rounding = false;
446 }
447
448 /// Creates and adds a new unattached leaf node to the tree, and returns the node of the new node
449 pub fn new_leaf(&mut self, layout: Style) -> TaffyResult<NodeId> {
450 let id = self.nodes.insert(NodeData::new(layout));
451 let _ = self.children.insert(new_vec_with_capacity(0));
452 let _ = self.parents.insert(None);
453
454 Ok(id.into())
455 }
456
457 /// Creates and adds a new unattached leaf node to the tree, and returns the [`NodeId`] of the new node
458 ///
459 /// Creates and adds a new leaf node with a supplied context
460 pub fn new_leaf_with_context(&mut self, layout: Style, context: NodeContext) -> TaffyResult<NodeId> {
461 let mut data = NodeData::new(layout);
462 data.has_context = true;
463
464 let id = self.nodes.insert(data);
465 self.node_context_data.insert(id, context);
466
467 let _ = self.children.insert(new_vec_with_capacity(0));
468 let _ = self.parents.insert(None);
469
470 Ok(id.into())
471 }
472
473 /// Creates and adds a new node, which may have any number of `children`
474 pub fn new_with_children(&mut self, layout: Style, children: &[NodeId]) -> TaffyResult<NodeId> {
475 let id = NodeId::from(self.nodes.insert(NodeData::new(layout)));
476
477 for child in children {
478 self.parents[(*child).into()] = Some(id);
479 }
480
481 let _ = self.children.insert(children.iter().copied().collect::<_>());
482 let _ = self.parents.insert(None);
483
484 Ok(id)
485 }
486
487 /// Drops all nodes in the tree
488 pub fn clear(&mut self) {
489 self.nodes.clear();
490 self.children.clear();
491 self.parents.clear();
492 }
493
494 /// Remove a specific node from the tree and drop it
495 ///
496 /// Returns the id of the node removed.
497 pub fn remove(&mut self, node: NodeId) -> TaffyResult<NodeId> {
498 let key = node.into();
499 if let Some(parent) = self.parents[key] {
500 if let Some(children) = self.children.get_mut(parent.into()) {
501 children.retain(|f| *f != node);
502 }
503 }
504
505 // Remove "parent" references to a node when removing that node
506 if let Some(children) = self.children.get(key) {
507 for child in children.iter().copied() {
508 self.parents[child.into()] = None;
509 }
510 }
511
512 let _ = self.children.remove(key);
513 let _ = self.parents.remove(key);
514 let _ = self.nodes.remove(key);
515
516 Ok(node)
517 }
518
519 /// Sets the context data associated with the node
520 pub fn set_node_context(&mut self, node: NodeId, measure: Option<NodeContext>) -> TaffyResult<()> {
521 let key = node.into();
522 if let Some(measure) = measure {
523 self.nodes[key].has_context = true;
524 self.node_context_data.insert(key, measure);
525 } else {
526 self.nodes[key].has_context = false;
527 self.node_context_data.remove(key);
528 }
529
530 self.mark_dirty(node)?;
531
532 Ok(())
533 }
534
535 /// Gets a reference to the the context data associated with the node
536 pub fn get_node_context(&self, node: NodeId) -> Option<&NodeContext> {
537 self.node_context_data.get(node.into())
538 }
539
540 /// Gets a mutable reference to the the context data associated with the node
541 pub fn get_node_context_mut(&mut self, node: NodeId) -> Option<&mut NodeContext> {
542 self.node_context_data.get_mut(node.into())
543 }
544
545 /// Gets mutable references to the the context data associated with the nodes. All keys must be valid and disjoint, otherwise None is returned.
546 pub fn get_disjoint_node_context_mut<const N: usize>(
547 &mut self,
548 keys: [NodeId; N],
549 ) -> Option<[&mut NodeContext; N]> {
550 self.node_context_data.get_disjoint_mut(keys.map(|k| k.into()))
551 }
552
553 /// Adds a `child` node under the supplied `parent`
554 pub fn add_child(&mut self, parent: NodeId, child: NodeId) -> TaffyResult<()> {
555 let parent_key = parent.into();
556 let child_key = child.into();
557 self.parents[child_key] = Some(parent);
558 self.children[parent_key].push(child);
559 self.mark_dirty(parent)?;
560
561 Ok(())
562 }
563
564 /// Inserts a `child` node at the given `child_index` under the supplied `parent`, shifting all children after it to the right.
565 pub fn insert_child_at_index(&mut self, parent: NodeId, child_index: usize, child: NodeId) -> TaffyResult<()> {
566 let parent_key = parent.into();
567
568 let child_count = self.children[parent_key].len();
569 if child_index > child_count {
570 return Err(TaffyError::ChildIndexOutOfBounds { parent, child_index, child_count });
571 }
572
573 self.parents[child.into()] = Some(parent);
574 self.children[parent_key].insert(child_index, child);
575 self.mark_dirty(parent)?;
576
577 Ok(())
578 }
579
580 /// Directly sets the `children` of the supplied `parent`
581 pub fn set_children(&mut self, parent: NodeId, children: &[NodeId]) -> TaffyResult<()> {
582 let parent_key = parent.into();
583
584 // Remove node as parent from all its current children.
585 for child in &self.children[parent_key] {
586 self.parents[(*child).into()] = None;
587 }
588
589 // Build up relation node <-> child
590 for child in children {
591 self.parents[(*child).into()] = Some(parent);
592 }
593
594 let parent_children = &mut self.children[parent_key];
595 parent_children.clear();
596 children.iter().for_each(|child| parent_children.push(*child));
597
598 self.mark_dirty(parent)?;
599
600 Ok(())
601 }
602
603 /// Removes the `child` of the parent `node`
604 ///
605 /// The child is not removed from the tree entirely, it is simply no longer attached to its previous parent.
606 pub fn remove_child(&mut self, parent: NodeId, child: NodeId) -> TaffyResult<NodeId> {
607 let index = self.children[parent.into()].iter().position(|n| *n == child).unwrap();
608 self.remove_child_at_index(parent, index)
609 }
610
611 /// Removes the child at the given `index` from the `parent`
612 ///
613 /// The child is not removed from the tree entirely, it is simply no longer attached to its previous parent.
614 pub fn remove_child_at_index(&mut self, parent: NodeId, child_index: usize) -> TaffyResult<NodeId> {
615 let parent_key = parent.into();
616 let child_count = self.children[parent_key].len();
617 if child_index >= child_count {
618 return Err(TaffyError::ChildIndexOutOfBounds { parent, child_index, child_count });
619 }
620
621 let child = self.children[parent_key].remove(child_index);
622 self.parents[child.into()] = None;
623
624 self.mark_dirty(parent)?;
625
626 Ok(child)
627 }
628
629 /// Replaces the child at the given `child_index` from the `parent` node with the new `child` node
630 ///
631 /// The child is not removed from the tree entirely, it is simply no longer attached to its previous parent.
632 pub fn replace_child_at_index(
633 &mut self,
634 parent: NodeId,
635 child_index: usize,
636 new_child: NodeId,
637 ) -> TaffyResult<NodeId> {
638 let parent_key = parent.into();
639
640 let child_count = self.children[parent_key].len();
641 if child_index >= child_count {
642 return Err(TaffyError::ChildIndexOutOfBounds { parent, child_index, child_count });
643 }
644
645 self.parents[new_child.into()] = Some(parent);
646 let old_child = core::mem::replace(&mut self.children[parent_key][child_index], new_child);
647 self.parents[old_child.into()] = None;
648
649 self.mark_dirty(parent)?;
650
651 Ok(old_child)
652 }
653
654 /// Returns the child node of the parent `node` at the provided `child_index`
655 pub fn child_at_index(&self, parent: NodeId, child_index: usize) -> TaffyResult<NodeId> {
656 let parent_key = parent.into();
657 let child_count = self.children[parent_key].len();
658 if child_index >= child_count {
659 return Err(TaffyError::ChildIndexOutOfBounds { parent, child_index, child_count });
660 }
661
662 Ok(self.children[parent_key][child_index])
663 }
664
665 /// Returns the total number of nodes in the tree
666 pub fn total_node_count(&self) -> usize {
667 self.nodes.len()
668 }
669
670 /// Returns the `NodeId` of the parent node of the specified node (if it exists)
671 ///
672 /// - Return None if the specified node has no parent
673 /// - Panics if the specified node does not exist
674 pub fn parent(&self, child_id: NodeId) -> Option<NodeId> {
675 self.parents[child_id.into()]
676 }
677
678 /// Returns a list of children that belong to the parent node
679 pub fn children(&self, parent: NodeId) -> TaffyResult<Vec<NodeId>> {
680 Ok(self.children[parent.into()].iter().copied().collect::<_>())
681 }
682
683 /// Sets the [`Style`] of the provided `node`
684 pub fn set_style(&mut self, node: NodeId, style: Style) -> TaffyResult<()> {
685 self.nodes[node.into()].style = style;
686 self.mark_dirty(node)?;
687 Ok(())
688 }
689
690 /// Gets the [`Style`] of the provided `node`
691 pub fn style(&self, node: NodeId) -> TaffyResult<&Style> {
692 Ok(&self.nodes[node.into()].style)
693 }
694
695 /// Return this node layout relative to its parent
696 pub fn layout(&self, node: NodeId) -> TaffyResult<&Layout> {
697 if self.config.use_rounding {
698 Ok(&self.nodes[node.into()].final_layout)
699 } else {
700 Ok(&self.nodes[node.into()].unrounded_layout)
701 }
702 }
703
704 /// Marks the layout computation of this node and its children as outdated
705 ///
706 /// Performs a recursive depth-first search up the tree until the root node is reached
707 ///
708 /// WARNING: this will stack-overflow if the tree contains a cycle
709 pub fn mark_dirty(&mut self, node: NodeId) -> TaffyResult<()> {
710 /// WARNING: this will stack-overflow if the tree contains a cycle
711 fn mark_dirty_recursive(
712 nodes: &mut SlotMap<DefaultKey, NodeData>,
713 parents: &SlotMap<DefaultKey, Option<NodeId>>,
714 node_key: DefaultKey,
715 ) {
716 nodes[node_key].mark_dirty();
717
718 if let Some(Some(node)) = parents.get(node_key) {
719 mark_dirty_recursive(nodes, parents, (*node).into());
720 }
721 }
722
723 mark_dirty_recursive(&mut self.nodes, &self.parents, node.into());
724
725 Ok(())
726 }
727
728 /// Indicates whether the layout of this node (and its children) need to be recomputed
729 pub fn dirty(&self, node: NodeId) -> TaffyResult<bool> {
730 Ok(self.nodes[node.into()].cache.is_empty())
731 }
732
733 /// Updates the stored layout of the provided `node` and its children
734 pub fn compute_layout_with_measure<MeasureFunction>(
735 &mut self,
736 node_id: NodeId,
737 available_space: Size<AvailableSpace>,
738 measure_function: MeasureFunction,
739 ) -> Result<(), TaffyError>
740 where
741 MeasureFunction:
742 FnMut(Size<Option<f32>>, Size<AvailableSpace>, NodeId, Option<&mut NodeContext>, &Style) -> Size<f32>,
743 {
744 let use_rounding = self.config.use_rounding;
745 let mut taffy_view = TaffyView { taffy: self, measure_function };
746 compute_root_layout(&mut taffy_view, node_id, available_space);
747 if use_rounding {
748 round_layout(&mut taffy_view, node_id);
749 }
750 Ok(())
751 }
752
753 /// Updates the stored layout of the provided `node` and its children
754 pub fn compute_layout(&mut self, node: NodeId, available_space: Size<AvailableSpace>) -> Result<(), TaffyError> {
755 self.compute_layout_with_measure(node, available_space, |_, _, _, _, _| Size::ZERO)
756 }
757
758 /// Prints a debug representation of the tree's layout
759 #[cfg(feature = "std")]
760 pub fn print_tree(&mut self, root: NodeId) {
761 crate::util::print_tree(self, root)
762 }
763
764 /// Returns an instance of LayoutTree representing the TaffyTree
765 #[cfg(test)]
766 pub(crate) fn as_layout_tree(&mut self) -> impl LayoutPartialTree + '_ {
767 TaffyView { taffy: self, measure_function: |_, _, _, _, _| Size::ZERO }
768 }
769}
770
771#[cfg(test)]
772mod tests {
773
774 use super::*;
775 use crate::style::{Dimension, Display, FlexDirection};
776 use crate::style_helpers::*;
777 use crate::util::sys;
778
779 fn size_measure_function(
780 known_dimensions: Size<Option<f32>>,
781 _available_space: Size<AvailableSpace>,
782 _node_id: NodeId,
783 node_context: Option<&mut Size<f32>>,
784 _style: &Style,
785 ) -> Size<f32> {
786 known_dimensions.unwrap_or(node_context.cloned().unwrap_or(Size::ZERO))
787 }
788
789 #[test]
790 fn new_should_allocate_default_capacity() {
791 const DEFAULT_CAPACITY: usize = 16; // This is the capacity defined in the `impl Default`
792 let taffy: TaffyTree<()> = TaffyTree::new();
793
794 assert!(taffy.children.capacity() >= DEFAULT_CAPACITY);
795 assert!(taffy.parents.capacity() >= DEFAULT_CAPACITY);
796 assert!(taffy.nodes.capacity() >= DEFAULT_CAPACITY);
797 }
798
799 #[test]
800 fn test_with_capacity() {
801 const CAPACITY: usize = 8;
802 let taffy: TaffyTree<()> = TaffyTree::with_capacity(CAPACITY);
803
804 assert!(taffy.children.capacity() >= CAPACITY);
805 assert!(taffy.parents.capacity() >= CAPACITY);
806 assert!(taffy.nodes.capacity() >= CAPACITY);
807 }
808
809 #[test]
810 fn test_new_leaf() {
811 let mut taffy: TaffyTree<()> = TaffyTree::new();
812
813 let res = taffy.new_leaf(Style::default());
814 assert!(res.is_ok());
815 let node = res.unwrap();
816
817 // node should be in the taffy tree and have no children
818 assert!(taffy.child_count(node) == 0);
819 }
820
821 #[test]
822 fn new_leaf_with_context() {
823 let mut taffy: TaffyTree<Size<f32>> = TaffyTree::new();
824
825 let res = taffy.new_leaf_with_context(Style::default(), Size::ZERO);
826 assert!(res.is_ok());
827 let node = res.unwrap();
828
829 // node should be in the taffy tree and have no children
830 assert!(taffy.child_count(node) == 0);
831 }
832
833 /// Test that new_with_children works as expected
834 #[test]
835 fn test_new_with_children() {
836 let mut taffy: TaffyTree<()> = TaffyTree::new();
837 let child0 = taffy.new_leaf(Style::default()).unwrap();
838 let child1 = taffy.new_leaf(Style::default()).unwrap();
839 let node = taffy.new_with_children(Style::default(), &[child0, child1]).unwrap();
840
841 // node should have two children
842 assert_eq!(taffy.child_count(node), 2);
843 assert_eq!(taffy.children(node).unwrap()[0], child0);
844 assert_eq!(taffy.children(node).unwrap()[1], child1);
845 }
846
847 #[test]
848 fn remove_node_should_remove() {
849 let mut taffy: TaffyTree<()> = TaffyTree::new();
850
851 let node = taffy.new_leaf(Style::default()).unwrap();
852
853 let _ = taffy.remove(node).unwrap();
854 }
855
856 #[test]
857 fn remove_node_should_detach_hierarchy() {
858 let mut taffy: TaffyTree<()> = TaffyTree::new();
859
860 // Build a linear tree layout: <0> <- <1> <- <2>
861 let node2 = taffy.new_leaf(Style::default()).unwrap();
862 let node1 = taffy.new_with_children(Style::default(), &[node2]).unwrap();
863 let node0 = taffy.new_with_children(Style::default(), &[node1]).unwrap();
864
865 // Both node0 and node1 should have 1 child nodes
866 assert_eq!(taffy.children(node0).unwrap().as_slice(), &[node1]);
867 assert_eq!(taffy.children(node1).unwrap().as_slice(), &[node2]);
868
869 // Disconnect the tree: <0> <2>
870 let _ = taffy.remove(node1).unwrap();
871
872 // Both remaining nodes should have no child nodes
873 assert!(taffy.children(node0).unwrap().is_empty());
874 assert!(taffy.children(node2).unwrap().is_empty());
875 }
876
877 #[test]
878 fn remove_last_node() {
879 let mut taffy: TaffyTree<()> = TaffyTree::new();
880
881 let parent = taffy.new_leaf(Style::default()).unwrap();
882 let child = taffy.new_leaf(Style::default()).unwrap();
883 taffy.add_child(parent, child).unwrap();
884
885 taffy.remove(child).unwrap();
886 taffy.remove(parent).unwrap();
887 }
888
889 #[test]
890 fn set_measure() {
891 let mut taffy: TaffyTree<Size<f32>> = TaffyTree::new();
892 let node = taffy.new_leaf_with_context(Style::default(), Size { width: 200.0, height: 200.0 }).unwrap();
893 taffy.compute_layout_with_measure(node, Size::MAX_CONTENT, size_measure_function).unwrap();
894 assert_eq!(taffy.layout(node).unwrap().size.width, 200.0);
895
896 taffy.set_node_context(node, Some(Size { width: 100.0, height: 100.0 })).unwrap();
897 taffy.compute_layout_with_measure(node, Size::MAX_CONTENT, size_measure_function).unwrap();
898 assert_eq!(taffy.layout(node).unwrap().size.width, 100.0);
899 }
900
901 #[test]
902 fn set_measure_of_previously_unmeasured_node() {
903 let mut taffy: TaffyTree<Size<f32>> = TaffyTree::new();
904 let node = taffy.new_leaf(Style::default()).unwrap();
905 taffy.compute_layout_with_measure(node, Size::MAX_CONTENT, size_measure_function).unwrap();
906 assert_eq!(taffy.layout(node).unwrap().size.width, 0.0);
907
908 taffy.set_node_context(node, Some(Size { width: 100.0, height: 100.0 })).unwrap();
909 taffy.compute_layout_with_measure(node, Size::MAX_CONTENT, size_measure_function).unwrap();
910 assert_eq!(taffy.layout(node).unwrap().size.width, 100.0);
911 }
912
913 /// Test that adding `add_child()` works
914 #[test]
915 fn add_child() {
916 let mut taffy: TaffyTree<()> = TaffyTree::new();
917 let node = taffy.new_leaf(Style::default()).unwrap();
918 assert_eq!(taffy.child_count(node), 0);
919
920 let child0 = taffy.new_leaf(Style::default()).unwrap();
921 taffy.add_child(node, child0).unwrap();
922 assert_eq!(taffy.child_count(node), 1);
923
924 let child1 = taffy.new_leaf(Style::default()).unwrap();
925 taffy.add_child(node, child1).unwrap();
926 assert_eq!(taffy.child_count(node), 2);
927 }
928
929 #[test]
930 fn insert_child_at_index() {
931 let mut taffy: TaffyTree<()> = TaffyTree::new();
932
933 let child0 = taffy.new_leaf(Style::default()).unwrap();
934 let child1 = taffy.new_leaf(Style::default()).unwrap();
935 let child2 = taffy.new_leaf(Style::default()).unwrap();
936
937 let node = taffy.new_leaf(Style::default()).unwrap();
938 assert_eq!(taffy.child_count(node), 0);
939
940 taffy.insert_child_at_index(node, 0, child0).unwrap();
941 assert_eq!(taffy.child_count(node), 1);
942 assert_eq!(taffy.children(node).unwrap()[0], child0);
943
944 taffy.insert_child_at_index(node, 0, child1).unwrap();
945 assert_eq!(taffy.child_count(node), 2);
946 assert_eq!(taffy.children(node).unwrap()[0], child1);
947 assert_eq!(taffy.children(node).unwrap()[1], child0);
948
949 taffy.insert_child_at_index(node, 1, child2).unwrap();
950 assert_eq!(taffy.child_count(node), 3);
951 assert_eq!(taffy.children(node).unwrap()[0], child1);
952 assert_eq!(taffy.children(node).unwrap()[1], child2);
953 assert_eq!(taffy.children(node).unwrap()[2], child0);
954 }
955
956 #[test]
957 fn set_children() {
958 let mut taffy: TaffyTree<()> = TaffyTree::new();
959
960 let child0 = taffy.new_leaf(Style::default()).unwrap();
961 let child1 = taffy.new_leaf(Style::default()).unwrap();
962 let node = taffy.new_with_children(Style::default(), &[child0, child1]).unwrap();
963
964 assert_eq!(taffy.child_count(node), 2);
965 assert_eq!(taffy.children(node).unwrap()[0], child0);
966 assert_eq!(taffy.children(node).unwrap()[1], child1);
967
968 let child2 = taffy.new_leaf(Style::default()).unwrap();
969 let child3 = taffy.new_leaf(Style::default()).unwrap();
970 taffy.set_children(node, &[child2, child3]).unwrap();
971
972 assert_eq!(taffy.child_count(node), 2);
973 assert_eq!(taffy.children(node).unwrap()[0], child2);
974 assert_eq!(taffy.children(node).unwrap()[1], child3);
975 }
976
977 /// Test that removing a child works
978 #[test]
979 fn remove_child() {
980 let mut taffy: TaffyTree<()> = TaffyTree::new();
981 let child0 = taffy.new_leaf(Style::default()).unwrap();
982 let child1 = taffy.new_leaf(Style::default()).unwrap();
983 let node = taffy.new_with_children(Style::default(), &[child0, child1]).unwrap();
984
985 assert_eq!(taffy.child_count(node), 2);
986
987 taffy.remove_child(node, child0).unwrap();
988 assert_eq!(taffy.child_count(node), 1);
989 assert_eq!(taffy.children(node).unwrap()[0], child1);
990
991 taffy.remove_child(node, child1).unwrap();
992 assert_eq!(taffy.child_count(node), 0);
993 }
994
995 #[test]
996 fn remove_child_at_index() {
997 let mut taffy: TaffyTree<()> = TaffyTree::new();
998 let child0 = taffy.new_leaf(Style::default()).unwrap();
999 let child1 = taffy.new_leaf(Style::default()).unwrap();
1000 let node = taffy.new_with_children(Style::default(), &[child0, child1]).unwrap();
1001
1002 assert_eq!(taffy.child_count(node), 2);
1003
1004 taffy.remove_child_at_index(node, 0).unwrap();
1005 assert_eq!(taffy.child_count(node), 1);
1006 assert_eq!(taffy.children(node).unwrap()[0], child1);
1007
1008 taffy.remove_child_at_index(node, 0).unwrap();
1009 assert_eq!(taffy.child_count(node), 0);
1010 }
1011
1012 // Related to: https://github.com/DioxusLabs/taffy/issues/510
1013 #[test]
1014 fn remove_child_updates_parents() {
1015 let mut taffy: TaffyTree<()> = TaffyTree::new();
1016
1017 let parent = taffy.new_leaf(Style::default()).unwrap();
1018 let child = taffy.new_leaf(Style::default()).unwrap();
1019
1020 taffy.add_child(parent, child).unwrap();
1021
1022 taffy.remove(parent).unwrap();
1023
1024 // Once the parent is removed this shouldn't panic.
1025 assert!(taffy.set_children(child, &[]).is_ok());
1026 }
1027
1028 #[test]
1029 fn replace_child_at_index() {
1030 let mut taffy: TaffyTree<()> = TaffyTree::new();
1031
1032 let child0 = taffy.new_leaf(Style::default()).unwrap();
1033 let child1 = taffy.new_leaf(Style::default()).unwrap();
1034
1035 let node = taffy.new_with_children(Style::default(), &[child0]).unwrap();
1036 assert_eq!(taffy.child_count(node), 1);
1037 assert_eq!(taffy.children(node).unwrap()[0], child0);
1038
1039 taffy.replace_child_at_index(node, 0, child1).unwrap();
1040 assert_eq!(taffy.child_count(node), 1);
1041 assert_eq!(taffy.children(node).unwrap()[0], child1);
1042 }
1043 #[test]
1044 fn test_child_at_index() {
1045 let mut taffy: TaffyTree<()> = TaffyTree::new();
1046 let child0 = taffy.new_leaf(Style::default()).unwrap();
1047 let child1 = taffy.new_leaf(Style::default()).unwrap();
1048 let child2 = taffy.new_leaf(Style::default()).unwrap();
1049 let node = taffy.new_with_children(Style::default(), &[child0, child1, child2]).unwrap();
1050
1051 assert!(if let Ok(result) = taffy.child_at_index(node, 0) { result == child0 } else { false });
1052 assert!(if let Ok(result) = taffy.child_at_index(node, 1) { result == child1 } else { false });
1053 assert!(if let Ok(result) = taffy.child_at_index(node, 2) { result == child2 } else { false });
1054 }
1055 #[test]
1056 fn test_child_count() {
1057 let mut taffy: TaffyTree<()> = TaffyTree::new();
1058 let child0 = taffy.new_leaf(Style::default()).unwrap();
1059 let child1 = taffy.new_leaf(Style::default()).unwrap();
1060 let node = taffy.new_with_children(Style::default(), &[child0, child1]).unwrap();
1061
1062 assert!(taffy.child_count(node) == 2);
1063 assert!(taffy.child_count(child0) == 0);
1064 assert!(taffy.child_count(child1) == 0);
1065 }
1066
1067 #[allow(clippy::vec_init_then_push)]
1068 #[test]
1069 fn test_children() {
1070 let mut taffy: TaffyTree<()> = TaffyTree::new();
1071 let child0 = taffy.new_leaf(Style::default()).unwrap();
1072 let child1 = taffy.new_leaf(Style::default()).unwrap();
1073 let node = taffy.new_with_children(Style::default(), &[child0, child1]).unwrap();
1074
1075 let mut children = sys::Vec::new();
1076 children.push(child0);
1077 children.push(child1);
1078
1079 let children_result = taffy.children(node).unwrap();
1080 assert_eq!(children_result, children);
1081
1082 assert!(taffy.children(child0).unwrap().is_empty());
1083 }
1084 #[test]
1085 fn test_set_style() {
1086 let mut taffy: TaffyTree<()> = TaffyTree::new();
1087
1088 let node = taffy.new_leaf(Style::default()).unwrap();
1089 assert_eq!(taffy.style(node).unwrap().display, Display::Flex);
1090
1091 taffy.set_style(node, Style { display: Display::None, ..Style::default() }).unwrap();
1092 assert_eq!(taffy.style(node).unwrap().display, Display::None);
1093 }
1094 #[test]
1095 fn test_style() {
1096 let mut taffy: TaffyTree<()> = TaffyTree::new();
1097
1098 let style = Style { display: Display::None, flex_direction: FlexDirection::RowReverse, ..Default::default() };
1099
1100 let node = taffy.new_leaf(style.clone()).unwrap();
1101
1102 let res = taffy.style(node);
1103 assert!(res.is_ok());
1104 assert!(res.unwrap() == &style);
1105 }
1106 #[test]
1107 fn test_layout() {
1108 let mut taffy: TaffyTree<()> = TaffyTree::new();
1109 let node = taffy.new_leaf(Style::default()).unwrap();
1110
1111 // TODO: Improve this test?
1112 let res = taffy.layout(node);
1113 assert!(res.is_ok());
1114 }
1115
1116 #[test]
1117 fn test_mark_dirty() {
1118 let mut taffy: TaffyTree<()> = TaffyTree::new();
1119 let child0 = taffy.new_leaf(Style::default()).unwrap();
1120 let child1 = taffy.new_leaf(Style::default()).unwrap();
1121 let node = taffy.new_with_children(Style::default(), &[child0, child1]).unwrap();
1122
1123 taffy.compute_layout(node, Size::MAX_CONTENT).unwrap();
1124
1125 assert_eq!(taffy.dirty(child0).unwrap(), false);
1126 assert_eq!(taffy.dirty(child1).unwrap(), false);
1127 assert_eq!(taffy.dirty(node).unwrap(), false);
1128
1129 taffy.mark_dirty(node).unwrap();
1130 assert_eq!(taffy.dirty(child0).unwrap(), false);
1131 assert_eq!(taffy.dirty(child1).unwrap(), false);
1132 assert_eq!(taffy.dirty(node).unwrap(), true);
1133
1134 taffy.compute_layout(node, Size::MAX_CONTENT).unwrap();
1135 taffy.mark_dirty(child0).unwrap();
1136 assert_eq!(taffy.dirty(child0).unwrap(), true);
1137 assert_eq!(taffy.dirty(child1).unwrap(), false);
1138 assert_eq!(taffy.dirty(node).unwrap(), true);
1139 }
1140
1141 #[test]
1142 fn compute_layout_should_produce_valid_result() {
1143 let mut taffy: TaffyTree<()> = TaffyTree::new();
1144 let node_result = taffy.new_leaf(Style {
1145 size: Size { width: Dimension::Length(10f32), height: Dimension::Length(10f32) },
1146 ..Default::default()
1147 });
1148 assert!(node_result.is_ok());
1149 let node = node_result.unwrap();
1150 let layout_result = taffy.compute_layout(
1151 node,
1152 Size { width: AvailableSpace::Definite(100.), height: AvailableSpace::Definite(100.) },
1153 );
1154 assert!(layout_result.is_ok());
1155 }
1156
1157 #[test]
1158 fn make_sure_layout_location_is_top_left() {
1159 use crate::prelude::Rect;
1160
1161 let mut taffy: TaffyTree<()> = TaffyTree::new();
1162
1163 let node = taffy
1164 .new_leaf(Style {
1165 size: Size { width: Dimension::Percent(1f32), height: Dimension::Percent(1f32) },
1166 ..Default::default()
1167 })
1168 .unwrap();
1169
1170 let root = taffy
1171 .new_with_children(
1172 Style {
1173 size: Size { width: Dimension::Length(100f32), height: Dimension::Length(100f32) },
1174 padding: Rect {
1175 left: length(10f32),
1176 right: length(20f32),
1177 top: length(30f32),
1178 bottom: length(40f32),
1179 },
1180 ..Default::default()
1181 },
1182 &[node],
1183 )
1184 .unwrap();
1185
1186 taffy.compute_layout(root, Size::MAX_CONTENT).unwrap();
1187
1188 // If Layout::location represents top-left coord, 'node' location
1189 // must be (due applied 'root' padding): {x: 10, y: 30}.
1190 //
1191 // It's important, since result will be different for each other
1192 // coordinate space:
1193 // - bottom-left: {x: 10, y: 40}
1194 // - top-right: {x: 20, y: 30}
1195 // - bottom-right: {x: 20, y: 40}
1196 let layout = taffy.layout(node).unwrap();
1197 assert_eq!(layout.location.x, 10f32);
1198 assert_eq!(layout.location.y, 30f32);
1199 }
1200}