Move cache logic to own module (#432)
1//! A cache for storing the results of layout computation
2use crate::geometry::Size;
3use crate::layout::{RunMode, SizeAndBaselines};
4use crate::style::AvailableSpace;
5
6/// The number of cache entries for each node in the tree
7pub(crate) const CACHE_SIZE: usize = 7;
8
9/// Cached intermediate layout results
10#[derive(Debug, Clone, Copy)]
11pub struct CacheEntry {
12 /// The initial cached size of the node itself
13 known_dimensions: Size<Option<f32>>,
14 /// The initial cached size of the parent's node
15 available_space: Size<AvailableSpace>,
16 /// Whether or not layout should be recomputed
17 run_mode: RunMode,
18
19 /// The cached size and baselines of the item
20 cached_size_and_baselines: SizeAndBaselines,
21}
22
23/// A cache for caching the results of a sizing a Grid Item or Flexbox Item
24pub struct Cache {
25 /// An array of entries in the cache
26 entries: [Option<CacheEntry>; CACHE_SIZE],
27}
28
29impl Cache {
30 /// Create a new empty cache
31 pub const fn new() -> Self {
32 Self { entries: [None; CACHE_SIZE] }
33 }
34
35 /// Return the cache slot to cache the current computed result in
36 ///
37 /// ## Caching Strategy
38 ///
39 /// 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
40 /// process, and we don't want later results to clobber earlier ones.
41 ///
42 /// The two variables that we care about when determining cache slot are:
43 ///
44 /// - How many "known_dimensions" are set. In the worst case, a node may be called first with neither dimension known, then with one
45 /// dimension known (either width of height - which doesn't matter for our purposes here), and then with both dimensions known.
46 /// - Whether unknown dimensions are being sized under a min-content or a max-content available space constraint (definite available space
47 /// shares a cache slot with max-content because a node will generally be sized under one or the other but not both).
48 ///
49 /// ## Cache slots:
50 ///
51 /// - Slot 0: Both known_dimensions were set
52 /// - Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraintraint
53 /// - Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
54 /// - 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
55 /// - Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
56 /// - Slot 5: Neither known_dimensions were set and we are sizing under a MaxContent or Definite available space constraint
57 /// - Slot 6: Neither known_dimensions were set and we are sizing under a MinContent constraint
58 #[inline]
59 fn compute_cache_slot(known_dimensions: Size<Option<f32>>, available_space: Size<AvailableSpace>) -> usize {
60 let has_known_width = known_dimensions.width.is_some();
61 let has_known_height = known_dimensions.height.is_some();
62
63 // Slot 0: Both known_dimensions were set
64 if has_known_width && has_known_height {
65 return 0;
66 }
67
68 // Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
69 // Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
70 if has_known_width && !has_known_height {
71 return 1 + (available_space.height == AvailableSpace::MinContent) as usize;
72 }
73
74 // Slot 3: height but not width known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
75 // Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
76 if !has_known_width && has_known_height {
77 return 3 + (available_space.width == AvailableSpace::MinContent) as usize;
78 }
79
80 // Slot 5: Neither known_dimensions were set and we are sizing under a MaxContent or Definite available space constraint
81 // Slot 6: Neither known_dimensions were set and we are sizing under a MinContent constraint
82 5 + (available_space.width == AvailableSpace::MinContent) as usize
83 }
84
85 /// Try to retrieve a cached result from the cache
86 #[inline]
87 pub fn get(
88 &self,
89 known_dimensions: Size<Option<f32>>,
90 available_space: Size<AvailableSpace>,
91 run_mode: RunMode,
92 ) -> Option<SizeAndBaselines> {
93 for entry in self.entries.iter().flatten() {
94 // Cached ComputeSize results are not valid if we are running in PerformLayout mode
95 if entry.run_mode == RunMode::ComputeSize && run_mode == RunMode::PeformLayout {
96 return None;
97 }
98
99 let cached_size = entry.cached_size_and_baselines.size;
100
101 if (known_dimensions.width == entry.known_dimensions.width
102 || known_dimensions.width == Some(cached_size.width))
103 && (known_dimensions.height == entry.known_dimensions.height
104 || known_dimensions.height == Some(cached_size.height))
105 && (known_dimensions.width.is_some()
106 || entry.available_space.width.is_roughly_equal(available_space.width))
107 && (known_dimensions.height.is_some()
108 || entry.available_space.height.is_roughly_equal(available_space.height))
109 {
110 return Some(entry.cached_size_and_baselines);
111 }
112 }
113
114 None
115 }
116
117 /// Store a computed size in the cache
118 pub fn store(
119 &mut self,
120 known_dimensions: Size<Option<f32>>,
121 available_space: Size<AvailableSpace>,
122 run_mode: RunMode,
123 cached_size_and_baselines: SizeAndBaselines,
124 ) {
125 let cache_slot = Self::compute_cache_slot(known_dimensions, available_space);
126 self.entries[cache_slot] =
127 Some(CacheEntry { known_dimensions, available_space, run_mode, cached_size_and_baselines });
128 }
129
130 /// Clear all cache entries
131 pub fn clear(&mut self) {
132 self.entries = [None; CACHE_SIZE];
133 }
134
135 /// Returns true if all cache entries are None, else false
136 pub fn is_empty(&self) -> bool {
137 !self.entries.iter().any(|entry| entry.is_some())
138 }
139}