taffy/tree/
cache.rs

1//! A cache for storing the results of layout computation
2use crate::geometry::Size;
3use crate::style::AvailableSpace;
4use crate::tree::{LayoutOutput, RunMode};
5
6/// The number of cache entries for each node in the tree
7const CACHE_SIZE: usize = 9;
8
9/// Cached intermediate layout results
10#[derive(Debug, Clone, Copy, PartialEq)]
11#[cfg_attr(feature = "serde", derive(Serialize))]
12pub(crate) struct CacheEntry<T> {
13    /// The initial cached size of the node itself
14    known_dimensions: Size<Option<f32>>,
15    /// The initial cached size of the parent's node
16    available_space: Size<AvailableSpace>,
17    /// The cached size and baselines of the item
18    content: T,
19}
20
21/// A cache for caching the results of a sizing a Grid Item or Flexbox Item
22#[derive(Debug, Clone, PartialEq)]
23#[cfg_attr(feature = "serde", derive(Serialize))]
24pub struct Cache {
25    /// The cache entry for the node's final layout
26    final_layout_entry: Option<CacheEntry<LayoutOutput>>,
27    /// The cache entries for the node's preliminary size measurements
28    measure_entries: [Option<CacheEntry<Size<f32>>>; CACHE_SIZE],
29    /// Tracks if all cache entries are empty
30    is_empty: bool,
31}
32
33impl Default for Cache {
34    fn default() -> Self {
35        Self::new()
36    }
37}
38
39impl Cache {
40    /// Create a new empty cache
41    pub const fn new() -> Self {
42        Self { final_layout_entry: None, measure_entries: [None; CACHE_SIZE], is_empty: true }
43    }
44
45    /// Return the cache slot to cache the current computed result in
46    ///
47    /// ## Caching Strategy
48    ///
49    /// We need multiple cache slots, because a node's size is often queried by it's parent multiple times in the course of the layout
50    /// process, and we don't want later results to clobber earlier ones.
51    ///
52    /// The two variables that we care about when determining cache slot are:
53    ///
54    ///   - How many "known_dimensions" are set. In the worst case, a node may be called first with neither dimension known, then with one
55    ///     dimension known (either width of height - which doesn't matter for our purposes here), and then with both dimensions known.
56    ///   - Whether unknown dimensions are being sized under a min-content or a max-content available space constraint (definite available space
57    ///     shares a cache slot with max-content because a node will generally be sized under one or the other but not both).
58    ///
59    /// ## Cache slots:
60    ///
61    /// - Slot 0: Both known_dimensions were set
62    /// - Slots 1-4: 1 of 2 known_dimensions were set and:
63    ///   - Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraintraint
64    ///   - Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
65    ///   - Slot 3: height but not width known_dimension was set and the other dimension was either a MaxContent or Definite available space constraintable space constraint
66    ///   - Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
67    /// - Slots 5-8: Neither known_dimensions were set and:
68    ///   - Slot 5: x-axis available space is MaxContent or Definite and y-axis available space is MaxContent or Definite
69    ///   - Slot 6: x-axis available space is MaxContent or Definite and y-axis available space is MinContent
70    ///   - Slot 7: x-axis available space is MinContent and y-axis available space is MaxContent or Definite
71    ///   - Slot 8: x-axis available space is MinContent and y-axis available space is MinContent
72    #[inline]
73    fn compute_cache_slot(known_dimensions: Size<Option<f32>>, available_space: Size<AvailableSpace>) -> usize {
74        use AvailableSpace::{Definite, MaxContent, MinContent};
75
76        let has_known_width = known_dimensions.width.is_some();
77        let has_known_height = known_dimensions.height.is_some();
78
79        // Slot 0: Both known_dimensions were set
80        if has_known_width && has_known_height {
81            return 0;
82        }
83
84        // Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
85        // Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
86        if has_known_width && !has_known_height {
87            return 1 + (available_space.height == MinContent) as usize;
88        }
89
90        // Slot 3: height but not width known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
91        // Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
92        if has_known_height && !has_known_width {
93            return 3 + (available_space.width == MinContent) as usize;
94        }
95
96        // Slots 5-8: Neither known_dimensions were set and:
97        match (available_space.width, available_space.height) {
98            // Slot 5: x-axis available space is MaxContent or Definite and y-axis available space is MaxContent or Definite
99            (MaxContent | Definite(_), MaxContent | Definite(_)) => 5,
100            // Slot 6: x-axis available space is MaxContent or Definite and y-axis available space is MinContent
101            (MaxContent | Definite(_), MinContent) => 6,
102            // Slot 7: x-axis available space is MinContent and y-axis available space is MaxContent or Definite
103            (MinContent, MaxContent | Definite(_)) => 7,
104            // Slot 8: x-axis available space is MinContent and y-axis available space is MinContent
105            (MinContent, MinContent) => 8,
106        }
107    }
108
109    /// Try to retrieve a cached result from the cache
110    #[inline]
111    pub fn get(
112        &self,
113        known_dimensions: Size<Option<f32>>,
114        available_space: Size<AvailableSpace>,
115        run_mode: RunMode,
116    ) -> Option<LayoutOutput> {
117        match run_mode {
118            RunMode::PerformLayout => self
119                .final_layout_entry
120                .filter(|entry| {
121                    let cached_size = entry.content.size;
122                    (known_dimensions.width == entry.known_dimensions.width
123                        || known_dimensions.width == Some(cached_size.width))
124                        && (known_dimensions.height == entry.known_dimensions.height
125                            || known_dimensions.height == Some(cached_size.height))
126                        && (known_dimensions.width.is_some()
127                            || entry.available_space.width.is_roughly_equal(available_space.width))
128                        && (known_dimensions.height.is_some()
129                            || entry.available_space.height.is_roughly_equal(available_space.height))
130                })
131                .map(|e| e.content),
132            RunMode::ComputeSize => {
133                for entry in self.measure_entries.iter().flatten() {
134                    let cached_size = entry.content;
135
136                    if (known_dimensions.width == entry.known_dimensions.width
137                        || known_dimensions.width == Some(cached_size.width))
138                        && (known_dimensions.height == entry.known_dimensions.height
139                            || known_dimensions.height == Some(cached_size.height))
140                        && (known_dimensions.width.is_some()
141                            || entry.available_space.width.is_roughly_equal(available_space.width))
142                        && (known_dimensions.height.is_some()
143                            || entry.available_space.height.is_roughly_equal(available_space.height))
144                    {
145                        return Some(LayoutOutput::from_outer_size(cached_size));
146                    }
147                }
148
149                None
150            }
151            RunMode::PerformHiddenLayout => None,
152        }
153    }
154
155    /// Store a computed size in the cache
156    pub fn store(
157        &mut self,
158        known_dimensions: Size<Option<f32>>,
159        available_space: Size<AvailableSpace>,
160        run_mode: RunMode,
161        layout_output: LayoutOutput,
162    ) {
163        match run_mode {
164            RunMode::PerformLayout => {
165                self.is_empty = false;
166                self.final_layout_entry = Some(CacheEntry { known_dimensions, available_space, content: layout_output })
167            }
168            RunMode::ComputeSize => {
169                self.is_empty = false;
170                let cache_slot = Self::compute_cache_slot(known_dimensions, available_space);
171                self.measure_entries[cache_slot] =
172                    Some(CacheEntry { known_dimensions, available_space, content: layout_output.size });
173            }
174            RunMode::PerformHiddenLayout => {}
175        }
176    }
177
178    /// Clear all cache entries and reports clear operation outcome ([`ClearState`])
179    pub fn clear(&mut self) -> ClearState {
180        if self.is_empty {
181            return ClearState::AlreadyEmpty;
182        }
183        self.is_empty = true;
184        self.final_layout_entry = None;
185        self.measure_entries = [None; CACHE_SIZE];
186        ClearState::Cleared
187    }
188
189    /// Returns true if all cache entries are None, else false
190    pub fn is_empty(&self) -> bool {
191        self.final_layout_entry.is_none() && !self.measure_entries.iter().any(|entry| entry.is_some())
192    }
193}
194
195/// Clear operation outcome. See [`Cache::clear`]
196pub enum ClearState {
197    /// Cleared some values
198    Cleared,
199    /// Everything was already cleared
200    AlreadyEmpty,
201}
taffy/tree/cache.rs

taffy/tree/
cache.rs
