taffy/tree/
cache.rs

1//! A cache for storing the results of layout computation
2
3#![allow(clippy::unusual_byte_groupings)]
4
5use crate::geometry::Size;
6use crate::style::AvailableSpace;
7use crate::tree::{CollapsibleMarginSet, LayoutInput, LayoutOutput, RunMode};
8use crate::RequestedAxis;
9
10/// The number of cache entries for each node in the tree
11const CACHE_SIZE: usize = 9;
12
13// Manually written-out results of float to u32 bit casts because
14// `f32::to_bits` is not yet const at our MSRV.
15
16/// `f32::INFINITY` as a u32
17const INFINITY_BITS: u32 = 0b_0_11111111_00000000000000000000000_u32;
18/// `f32::NEG_INFINITY` as a u32
19const NEG_INFINITY_BITS: u32 = 0b_1_11111111_00000000000000000000000_u32;
20
21// The `CacheKey` encodes two f32s as a u64. We know that the f32s will always be
22// non-negative, so we pack two extra bits encoding the `RequestedAxis` into the
23// sign bits of the f32s. These constants help to encode and decode those bits.
24
25/// The sign bit of the first f32
26const SIGN_BIT_1: u64 = 1u64 << 63;
27/// The sign bit of the second f32
28const SIGN_BIT_2: u64 = 1u64 << 31;
29/// Mask of both sign bits (used to compute NON_SIGN_BITS_MASK)
30const BOTH_SIGN_BITS_MASK: u64 = SIGN_BIT_1 | SIGN_BIT_2;
31/// Mask of excluding the sign bits (used when setting/getting the size excluding the packed bits)
32const NON_SIGN_BITS_MASK: u64 = !BOTH_SIGN_BITS_MASK;
33
34/// Mask which includes only the bits which encode the x-axis value that we can use to ignore the
35/// y-axis value when comparing a cache key.
36const X_AXIS_VALUE_MASK: u64 = (u32::MAX as u64) << 32;
37
38/// Pack `Option<f32>` into `u32`
39#[inline(always)]
40fn option_cache_key(input: Option<f32>) -> u32 {
41    match input {
42        Some(value) => value.to_bits(),
43        None => INFINITY_BITS,
44    }
45}
46
47/// Pack `Size<Option<f32>>` into `u64`
48#[inline(always)]
49fn size_option_cache_key(input: Size<Option<f32>>) -> u64 {
50    (option_cache_key(input.width) as u64) << 32 | option_cache_key(input.height) as u64
51}
52
53/// Pack `AvailableSpace` into `u32`
54#[inline(always)]
55fn available_space_cache_key(input: AvailableSpace) -> u32 {
56    match input {
57        AvailableSpace::Definite(value) => (-value).to_bits(),
58        AvailableSpace::MinContent => NEG_INFINITY_BITS,
59        AvailableSpace::MaxContent => INFINITY_BITS,
60    }
61}
62
63/// Pack `Size<AvailableSpace>` into `u64`
64#[inline(always)]
65#[allow(dead_code)]
66fn size_available_space_cache_key(input: Size<AvailableSpace>) -> u64 {
67    (available_space_cache_key(input.width) as u64) << 32 | available_space_cache_key(input.height) as u64
68}
69
70/// Encodes combination of a `known_dimension` (Option<f32>) and `AvailableSpace` in
71/// a single dimension into a cache key in a single dimension.
72#[inline(always)]
73fn mixed_cache_key(kd: Option<f32>, avs: AvailableSpace) -> u32 {
74    kd.map(|kd| kd.to_bits()).unwrap_or_else(|| available_space_cache_key(avs))
75}
76
77/// Encodes combination of a `known_dimension` (Option<f32>) and `AvailableSpace` in
78/// two dimensions into a cache key in a single dimension.
79#[inline(always)]
80fn size_mixed_cache_key(kd: Size<Option<f32>>, avs: Size<AvailableSpace>) -> u64 {
81    (mixed_cache_key(kd.width, avs.width) as u64) << 32 | mixed_cache_key(kd.height, avs.height) as u64
82}
83
84/// Space-optimised cache key that packs bits into as small a size as possible
85#[derive(Debug, Clone, Copy, PartialEq, Eq)]
86#[cfg_attr(feature = "serde", derive(Serialize))]
87struct CacheKey {
88    /// The initial cached size of the node itself
89    kd_available_space: u64,
90    /// The initial cached size of the parent's node
91    parent_size: u64,
92    /// Whether each known dimension is definite. Normalized such that an axis
93    /// without a known dimension is always `true`.
94    known_dimensions_are_definite: Size<bool>,
95}
96
97impl CacheKey {
98    #[inline(always)]
99    #[allow(dead_code)]
100    /// Return the parent size with the extra bits that encode the requested axis masked out
101    fn parent_size(&self) -> u64 {
102        self.parent_size & NON_SIGN_BITS_MASK
103    }
104
105    /// Return the parent size with the extra bits that encode the requested axis masked out
106    /// And the y-axis value masked out
107    fn x_axis_parent_size(&self) -> u64 {
108        self.parent_size & (X_AXIS_VALUE_MASK & NON_SIGN_BITS_MASK)
109    }
110
111    /// Return the bits that encode the requested axis
112    fn requested_axis_bits(&self) -> u64 {
113        self.parent_size & BOTH_SIGN_BITS_MASK
114    }
115
116    /// Whether a cached entry with this key contains a valid size for the axis requested by `other`.
117    /// Sizes computed for a single axis may contain garbage values in the other axis, so an entry
118    /// is only usable if it was computed for the same axis (or for both axes).
119    fn size_is_valid_for(&self, other: &CacheKey) -> bool {
120        let entry_axis = self.requested_axis_bits();
121        entry_axis == BOTH_SIGN_BITS_MASK || entry_axis == other.requested_axis_bits()
122    }
123}
124
125impl From<&LayoutInput> for CacheKey {
126    fn from(input: &LayoutInput) -> Self {
127        // Pack axis enum into spare bits in the known_dimensions and available_space values
128        let extra_bits = match input.axis {
129            RequestedAxis::Horizontal => SIGN_BIT_1,
130            RequestedAxis::Vertical => SIGN_BIT_2,
131            RequestedAxis::Both => SIGN_BIT_1 | SIGN_BIT_2,
132        };
133
134        Self {
135            kd_available_space: size_mixed_cache_key(input.known_dimensions, input.available_space),
136            parent_size: (size_option_cache_key(input.parent_size) & NON_SIGN_BITS_MASK) | extra_bits,
137            known_dimensions_are_definite: input
138                .known_dimensions_are_definite
139                .zip_map(input.known_dimensions, |is_definite, kd| is_definite || kd.is_none()),
140        }
141    }
142}
143
144/// Cached intermediate layout results
145#[derive(Debug, Clone, Copy, PartialEq)]
146#[cfg_attr(feature = "serde", derive(Serialize))]
147pub(crate) struct CacheEntry<T> {
148    /// The key for the cache entry
149    key: CacheKey,
150    /// The cached size and baselines of the item
151    content: T,
152}
153
154/// A cache for caching the results of a sizing a Grid Item or Flexbox Item
155#[derive(Debug, Clone, PartialEq)]
156#[cfg_attr(feature = "serde", derive(Serialize))]
157pub struct Cache {
158    /// The cache entry for the node's final layout
159    final_layout_entry: Option<CacheEntry<LayoutOutput>>,
160    /// The cache entries for the node's preliminary size measurements
161    measure_entries: [Option<CacheEntry<Size<f32>>>; CACHE_SIZE],
162    /// Tracks which measure entries have been used since the eviction cursor last passed them
163    recently_used_entries: u16,
164    /// The next measure entry to consider replacing
165    next_measure_entry: u8,
166    /// Tracks if all cache entries are empty
167    is_empty: bool,
168}
169
170impl Default for Cache {
171    fn default() -> Self {
172        Self::new()
173    }
174}
175
176impl Cache {
177    /// Create a new empty cache
178    pub const fn new() -> Self {
179        Self {
180            final_layout_entry: None,
181            measure_entries: [None; CACHE_SIZE],
182            recently_used_entries: 0,
183            next_measure_entry: 0,
184            is_empty: true,
185        }
186    }
187
188    /// Try to retrieve a cached result from the cache
189    #[inline]
190    pub fn get(&mut self, input: &LayoutInput) -> Option<LayoutOutput> {
191        let key = CacheKey::from(input);
192        match input.run_mode {
193            RunMode::PerformLayout => self.final_layout_entry.filter(|entry| entry.key == key).map(|e| e.content),
194            RunMode::ComputeSize => {
195                for (index, entry) in self.measure_entries.iter().enumerate() {
196                    let Some(entry) = entry else { continue };
197                    if entry.key.kd_available_space == key.kd_available_space
198                        && entry.key.known_dimensions_are_definite == key.known_dimensions_are_definite
199                        && (entry.key.x_axis_parent_size() == key.x_axis_parent_size())
200                        && entry.key.size_is_valid_for(&key)
201                    {
202                        self.recently_used_entries |= 1 << index;
203                        return Some(LayoutOutput::from_outer_size(entry.content));
204                    }
205                }
206
207                None
208            }
209            RunMode::PerformHiddenLayout => None,
210        }
211    }
212
213    /// Store a computed size in the cache
214    pub fn store(&mut self, input: &LayoutInput, layout_output: LayoutOutput) {
215        let key = CacheKey::from(input);
216        match input.run_mode {
217            RunMode::PerformLayout => {
218                self.is_empty = false;
219                self.final_layout_entry = Some(CacheEntry { key, content: layout_output })
220            }
221            RunMode::ComputeSize => {
222                // Measure entries only store the size, and cache hits are reconstructed with
223                // `LayoutOutput::from_outer_size`, which resets the margin-collapse metadata
224                // (`top_margin`, `bottom_margin`, `margins_can_collapse_through`). Results that
225                // carry such metadata cannot be reconstructed from their size, so don't cache them.
226                if layout_output.margins_can_collapse_through
227                    || layout_output.top_margin != CollapsibleMarginSet::ZERO
228                    || layout_output.bottom_margin != CollapsibleMarginSet::ZERO
229                {
230                    return;
231                }
232                self.is_empty = false;
233                if let Some(index) =
234                    self.measure_entries.iter().position(|entry| entry.is_some_and(|entry| entry.key == key))
235                {
236                    self.measure_entries[index].as_mut().unwrap().content = layout_output.size;
237                    self.recently_used_entries |= 1 << index;
238                    return;
239                }
240                while self.recently_used_entries & (1 << self.next_measure_entry) != 0 {
241                    self.recently_used_entries &= !(1 << self.next_measure_entry);
242                    self.next_measure_entry += 1;
243                    if self.next_measure_entry == CACHE_SIZE as u8 {
244                        self.next_measure_entry = 0;
245                    }
246                }
247                let entry_index = self.next_measure_entry as usize;
248                self.measure_entries[entry_index] = Some(CacheEntry { key, content: layout_output.size });
249                self.recently_used_entries |= 1 << entry_index;
250                self.next_measure_entry += 1;
251                if self.next_measure_entry == CACHE_SIZE as u8 {
252                    self.next_measure_entry = 0;
253                }
254            }
255            RunMode::PerformHiddenLayout => {}
256        }
257    }
258
259    /// Clear all cache entries and reports clear operation outcome ([`ClearState`])
260    pub fn clear(&mut self) -> ClearState {
261        if self.is_empty {
262            return ClearState::AlreadyEmpty;
263        }
264        self.is_empty = true;
265        self.final_layout_entry = None;
266        self.measure_entries = [None; CACHE_SIZE];
267        self.recently_used_entries = 0;
268        self.next_measure_entry = 0;
269        ClearState::Cleared
270    }
271
272    /// Returns true if all cache entries are None, else false
273    pub fn is_empty(&self) -> bool {
274        self.final_layout_entry.is_none() && !self.measure_entries.iter().any(|entry| entry.is_some())
275    }
276}
277
278/// Clear operation outcome. See [`Cache::clear`]
279pub enum ClearState {
280    /// Cleared some values
281    Cleared,
282    /// Everything was already cleared
283    AlreadyEmpty,
284}
285
286#[cfg(test)]
287mod tests {
288    use super::*;
289    use crate::geometry::Line;
290    use crate::tree::SizingMode;
291
292    fn input(width: f32) -> LayoutInput {
293        LayoutInput {
294            run_mode: RunMode::ComputeSize,
295            sizing_mode: SizingMode::InherentSize,
296            axis: RequestedAxis::Both,
297            known_dimensions: Size { width: Some(width), height: None },
298            known_dimensions_are_definite: Size { width: true, height: true },
299            parent_size: Size::NONE,
300            available_space: Size { width: AvailableSpace::MaxContent, height: AvailableSpace::MaxContent },
301            vertical_margins_are_collapsible: Line::FALSE,
302        }
303    }
304
305    fn output(width: f32) -> LayoutOutput {
306        LayoutOutput::from_outer_size(Size { width, height: width })
307    }
308
309    #[test]
310    fn recently_used_measure_entries_get_a_second_chance() {
311        let mut cache = Cache::new();
312        for width in 0..CACHE_SIZE {
313            cache.store(&input(width as f32), output(width as f32));
314        }
315        cache.store(&input(CACHE_SIZE as f32), output(CACHE_SIZE as f32));
316
317        assert_eq!(cache.get(&input(1.0)), Some(output(1.0)));
318        cache.store(&input((CACHE_SIZE + 1) as f32), output((CACHE_SIZE + 1) as f32));
319
320        assert_eq!(cache.get(&input(1.0)), Some(output(1.0)));
321        assert_eq!(cache.get(&input(2.0)), None);
322    }
323
324    #[test]
325    fn storing_an_existing_measurement_updates_it_in_place() {
326        let mut cache = Cache::new();
327        cache.store(&input(1.0), output(1.0));
328        cache.store(&input(2.0), output(2.0));
329        cache.store(&input(1.0), output(3.0));
330
331        assert_eq!(cache.measure_entries.iter().flatten().count(), 2);
332        assert_eq!(cache.get(&input(1.0)), Some(output(3.0)));
333    }
334
335    #[test]
336    fn measurements_with_margin_collapse_metadata_are_not_cached() {
337        let mut cache = Cache::new();
338
339        let mut collapse_through = output(1.0);
340        collapse_through.margins_can_collapse_through = true;
341        cache.store(&input(1.0), collapse_through);
342        assert_eq!(cache.get(&input(1.0)), None);
343
344        let mut carried_margin = output(2.0);
345        carried_margin.top_margin = CollapsibleMarginSet::from_margin(10.0);
346        cache.store(&input(2.0), carried_margin);
347        assert_eq!(cache.get(&input(2.0)), None);
348    }
349
350    #[test]
351    fn retrieving_a_measurement_only_marks_its_slot_as_used() {
352        let mut cache = Cache::new();
353        cache.store(&input(1.0), output(1.0));
354        cache.store(&input(2.0), output(2.0));
355        cache.recently_used_entries = 0;
356        let entries = cache.measure_entries;
357
358        assert_eq!(cache.get(&input(1.0)), Some(output(1.0)));
359        assert_eq!(cache.measure_entries, entries);
360        assert_ne!(cache.recently_used_entries, 0);
361    }
362}
taffy/tree/cache.rs

taffy/tree/
cache.rs
