tawasuyu/taffy

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