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}
30
31impl Default for Cache {
32    fn default() -> Self {
33        Self::new()
34    }
35}
36
37impl Cache {
38    /// Create a new empty cache
39    pub const fn new() -> Self {
40        Self { final_layout_entry: None, measure_entries: [None; CACHE_SIZE] }
41    }
42
43    /// Return the cache slot to cache the current computed result in
44    ///
45    /// ## Caching Strategy
46    ///
47    /// 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
48    /// process, and we don't want later results to clobber earlier ones.
49    ///
50    /// The two variables that we care about when determining cache slot are:
51    ///
52    ///   - How many "known_dimensions" are set. In the worst case, a node may be called first with neither dimension known, then with one
53    ///     dimension known (either width of height - which doesn't matter for our purposes here), and then with both dimensions known.
54    ///   - Whether unknown dimensions are being sized under a min-content or a max-content available space constraint (definite available space
55    ///     shares a cache slot with max-content because a node will generally be sized under one or the other but not both).
56    ///
57    /// ## Cache slots:
58    ///
59    /// - Slot 0: Both known_dimensions were set
60    /// - Slots 1-4: 1 of 2 known_dimensions were set and:
61    ///   - Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraintraint
62    ///   - Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
63    ///   - 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
64    ///   - Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
65    /// - Slots 5-8: Neither known_dimensions were set and:
66    ///   - Slot 5: x-axis available space is MaxContent or Definite and y-axis available space is MaxContent or Definite
67    ///   - Slot 6: x-axis available space is MaxContent or Definite and y-axis available space is MinContent
68    ///   - Slot 7: x-axis available space is MinContent and y-axis available space is MaxContent or Definite
69    ///   - Slot 8: x-axis available space is MinContent and y-axis available space is MinContent
70    #[inline]
71    fn compute_cache_slot(known_dimensions: Size<Option<f32>>, available_space: Size<AvailableSpace>) -> usize {
72        use AvailableSpace::{Definite, MaxContent, MinContent};
73
74        let has_known_width = known_dimensions.width.is_some();
75        let has_known_height = known_dimensions.height.is_some();
76
77        // Slot 0: Both known_dimensions were set
78        if has_known_width && has_known_height {
79            return 0;
80        }
81
82        // Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
83        // Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
84        if has_known_width && !has_known_height {
85            return 1 + (available_space.height == MinContent) as usize;
86        }
87
88        // Slot 3: height but not width known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
89        // Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
90        if has_known_height && !has_known_width {
91            return 3 + (available_space.width == MinContent) as usize;
92        }
93
94        // Slots 5-8: Neither known_dimensions were set and:
95        match (available_space.width, available_space.height) {
96            // Slot 5: x-axis available space is MaxContent or Definite and y-axis available space is MaxContent or Definite
97            (MaxContent | Definite(_), MaxContent | Definite(_)) => 5,
98            // Slot 6: x-axis available space is MaxContent or Definite and y-axis available space is MinContent
99            (MaxContent | Definite(_), MinContent) => 6,
100            // Slot 7: x-axis available space is MinContent and y-axis available space is MaxContent or Definite
101            (MinContent, MaxContent | Definite(_)) => 7,
102            // Slot 8: x-axis available space is MinContent and y-axis available space is MinContent
103            (MinContent, MinContent) => 8,
104        }
105    }
106
107    /// Try to retrieve a cached result from the cache
108    #[inline]
109    pub fn get(
110        &self,
111        known_dimensions: Size<Option<f32>>,
112        available_space: Size<AvailableSpace>,
113        run_mode: RunMode,
114    ) -> Option<LayoutOutput> {
115        match run_mode {
116            RunMode::PerformLayout => self
117                .final_layout_entry
118                .filter(|entry| {
119                    let cached_size = entry.content.size;
120                    (known_dimensions.width == entry.known_dimensions.width
121                        || known_dimensions.width == Some(cached_size.width))
122                        && (known_dimensions.height == entry.known_dimensions.height
123                            || known_dimensions.height == Some(cached_size.height))
124                        && (known_dimensions.width.is_some()
125                            || entry.available_space.width.is_roughly_equal(available_space.width))
126                        && (known_dimensions.height.is_some()
127                            || entry.available_space.height.is_roughly_equal(available_space.height))
128                })
129                .map(|e| e.content),
130            RunMode::ComputeSize => {
131                for entry in self.measure_entries.iter().flatten() {
132                    let cached_size = entry.content;
133
134                    if (known_dimensions.width == entry.known_dimensions.width
135                        || known_dimensions.width == Some(cached_size.width))
136                        && (known_dimensions.height == entry.known_dimensions.height
137                            || known_dimensions.height == Some(cached_size.height))
138                        && (known_dimensions.width.is_some()
139                            || entry.available_space.width.is_roughly_equal(available_space.width))
140                        && (known_dimensions.height.is_some()
141                            || entry.available_space.height.is_roughly_equal(available_space.height))
142                    {
143                        return Some(LayoutOutput::from_outer_size(cached_size));
144                    }
145                }
146
147                None
148            }
149            RunMode::PerformHiddenLayout => None,
150        }
151    }
152
153    /// Store a computed size in the cache
154    pub fn store(
155        &mut self,
156        known_dimensions: Size<Option<f32>>,
157        available_space: Size<AvailableSpace>,
158        run_mode: RunMode,
159        layout_output: LayoutOutput,
160    ) {
161        match run_mode {
162            RunMode::PerformLayout => {
163                self.final_layout_entry = Some(CacheEntry { known_dimensions, available_space, content: layout_output })
164            }
165            RunMode::ComputeSize => {
166                let cache_slot = Self::compute_cache_slot(known_dimensions, available_space);
167                self.measure_entries[cache_slot] =
168                    Some(CacheEntry { known_dimensions, available_space, content: layout_output.size });
169            }
170            RunMode::PerformHiddenLayout => {}
171        }
172    }
173
174    /// Clear all cache entries
175    pub fn clear(&mut self) {
176        self.final_layout_entry = None;
177        self.measure_entries = [None; CACHE_SIZE];
178    }
179
180    /// Returns true if all cache entries are None, else false
181    pub fn is_empty(&self) -> bool {
182        self.final_layout_entry.is_none() && !self.measure_entries.iter().any(|entry| entry.is_some())
183    }
184}