1 //! A cache for storing the results of layout computation 2 use crate::geometry::Size; 3 use crate::style::AvailableSpace; 4 use crate::tree::{LayoutOutput, RunMode}; 5 6 /// The number of cache entries for each node in the tree 7 const CACHE_SIZE: usize = 9; 8 9 /// Cached intermediate layout results 10 #[derive(Debug, Clone, Copy, PartialEq)] 11 #[cfg_attr(feature = "serde", derive(Serialize))] 12 pub(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))] 24 pub 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 31 impl Default for Cache { default() -> Self32 fn default() -> Self { 33 Self::new() 34 } 35 } 36 37 impl Cache { 38 /// Create a new empty cache new() -> Self39 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] compute_cache_slot(known_dimensions: Size<Option<f32>>, available_space: Size<AvailableSpace>) -> usize71 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] get( &self, known_dimensions: Size<Option<f32>>, available_space: Size<AvailableSpace>, run_mode: RunMode, ) -> Option<LayoutOutput>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 store( &mut self, known_dimensions: Size<Option<f32>>, available_space: Size<AvailableSpace>, run_mode: RunMode, layout_output: LayoutOutput, )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 clear(&mut self)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 is_empty(&self) -> bool181 pub fn is_empty(&self) -> bool { 182 self.final_layout_entry.is_none() && !self.measure_entries.iter().any(|entry| entry.is_some()) 183 } 184 } 185