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