Fix caching for flexbox columns (#556)
1//! A cache for storing the results of layout computation
2use crate::geometry::Size;
3use crate::style::AvailableSpace;
4use crate::tree::{RunMode, SizeBaselinesAndMargins};
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 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: SizeBaselinesAndMargins,
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 /// - Slots 1-4: 1 of 2 known_dimensions were set and:
53 /// - Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraintraint
54 /// - Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
55 /// - 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
56 /// - Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
57 /// - Slots 5-8: Neither known_dimensions were set and:
58 /// - Slot 5: x-axis available space is MaxContent or Definite and y-axis available space is MaxContent or Definite
59 /// - Slot 6: x-axis available space is MaxContent or Definite and y-axis available space is MinContent
60 /// - Slot 7: x-axis available space is MinContent and y-axis available space is MaxContent or Definite
61 /// - Slot 8: x-axis available space is MinContent and y-axis available space is MinContent
62 #[inline]
63 fn compute_cache_slot(known_dimensions: Size<Option<f32>>, available_space: Size<AvailableSpace>) -> usize {
64 use AvailableSpace::{Definite, MaxContent, MinContent};
65
66 let has_known_width = known_dimensions.width.is_some();
67 let has_known_height = known_dimensions.height.is_some();
68
69 // Slot 0: Both known_dimensions were set
70 if has_known_width && has_known_height {
71 return 0;
72 }
73
74 // Slot 1: width but not height known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
75 // Slot 2: width but not height known_dimension was set and the other dimension was a MinContent constraint
76 if has_known_width && !has_known_height {
77 return 1 + (available_space.height == MinContent) as usize;
78 }
79
80 // Slot 3: height but not width known_dimension was set and the other dimension was either a MaxContent or Definite available space constraint
81 // Slot 4: height but not width known_dimension was set and the other dimension was a MinContent constraint
82 if !has_known_width && has_known_height {
83 return 3 + (available_space.width == MinContent) as usize;
84 }
85
86 // Slots 5-8: Neither known_dimensions were set and:
87 match (available_space.width, available_space.height) {
88 // Slot 5: x-axis available space is MaxContent or Definite and y-axis available space is MaxContent or Definite
89 (MaxContent | Definite(_), MaxContent | Definite(_)) => 5,
90 // Slot 6: x-axis available space is MaxContent or Definite and y-axis available space is MinContent
91 (MaxContent | Definite(_), MinContent) => 6,
92 // Slot 7: x-axis available space is MinContent and y-axis available space is MaxContent or Definite
93 (MinContent, MaxContent | Definite(_)) => 7,
94 // Slot 8: x-axis available space is MinContent and y-axis available space is MinContent
95 (MinContent, MinContent) => 8,
96 }
97 }
98
99 /// Try to retrieve a cached result from the cache
100 #[inline]
101 pub fn get(
102 &self,
103 known_dimensions: Size<Option<f32>>,
104 available_space: Size<AvailableSpace>,
105 run_mode: RunMode,
106 ) -> Option<SizeBaselinesAndMargins> {
107 for entry in self.entries.iter().flatten() {
108 // Cached ComputeSize results are not valid if we are running in PerformLayout mode
109 if entry.run_mode == RunMode::ComputeSize && run_mode == RunMode::PerformLayout {
110 return None;
111 }
112
113 let cached_size = entry.cached_size_and_baselines.size;
114
115 if (known_dimensions.width == entry.known_dimensions.width
116 || known_dimensions.width == Some(cached_size.width))
117 && (known_dimensions.height == entry.known_dimensions.height
118 || known_dimensions.height == Some(cached_size.height))
119 && (known_dimensions.width.is_some()
120 || entry.available_space.width.is_roughly_equal(available_space.width))
121 && (known_dimensions.height.is_some()
122 || entry.available_space.height.is_roughly_equal(available_space.height))
123 {
124 return Some(entry.cached_size_and_baselines);
125 }
126 }
127
128 None
129 }
130
131 /// Store a computed size in the cache
132 pub fn store(
133 &mut self,
134 known_dimensions: Size<Option<f32>>,
135 available_space: Size<AvailableSpace>,
136 run_mode: RunMode,
137 cached_size_and_baselines: SizeBaselinesAndMargins,
138 ) {
139 let cache_slot = Self::compute_cache_slot(known_dimensions, available_space);
140 self.entries[cache_slot] =
141 Some(CacheEntry { known_dimensions, available_space, run_mode, cached_size_and_baselines });
142 }
143
144 /// Clear all cache entries
145 pub fn clear(&mut self) {
146 self.entries = [None; CACHE_SIZE];
147 }
148
149 /// Returns true if all cache entries are None, else false
150 pub fn is_empty(&self) -> bool {
151 !self.entries.iter().any(|entry| entry.is_some())
152 }
153}