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