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}