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