uqa_sql/expr/regex/
cache.rs1use std::{
10 cell::RefCell,
11 marker::PhantomData,
12 rc::Rc,
13 sync::{Arc, Mutex},
14};
15use uqa_core::memory::{BudgetedString, BudgetedVec, MemoryBudget, MemoryError, MemoryReservation};
16use uqa_pg_regex::{CompileFlags, RegexResources, RetainedRegex};
17
18const CAPACITY: usize = 32;
19
20pub(super) struct RetainedAllowance(pub(super) Option<MemoryReservation>);
21
22impl RegexResources for RetainedAllowance {
23 fn reserve(&mut self, _: usize) -> bool {
24 unreachable!("retained hooks only release compiled memory")
25 }
26 fn release(&mut self, bytes: usize) {
27 if let Some(lease) = self.0.as_mut() {
28 drop(lease.split(bytes));
29 }
30 }
31 fn cancel_requested(&mut self) -> bool {
32 false
33 }
34 fn stack_too_deep(&mut self, _: usize) -> bool {
35 false
36 }
37}
38
39pub(super) struct Entry {
40 pub(super) pattern: BudgetedString,
41 pub(super) flags: CompileFlags,
42 pub(super) collation: u32,
43 pub(super) generation: u64,
44 pub(super) regex: RetainedRegex<RetainedAllowance>,
45}
46
47pub(super) struct Admission {
48 pub(super) pattern: BudgetedString,
49 pub(super) generation: u64,
50 pub(super) memory: Option<MemoryReservation>,
51}
52
53impl Entry {
54 fn matches(&self, pattern: &str, flags: CompileFlags, collation: u32) -> bool {
55 &*self.pattern == pattern && self.flags == flags && self.collation == collation
56 }
57}
58
59#[derive(Default)]
60struct Entries {
61 values: Vec<Entry>,
62 memory: Option<MemoryReservation>,
63 generation: u64,
64}
65
66pub struct RegexCache {
68 pub(super) budget: MemoryBudget,
69 entries: Mutex<Entries>,
70}
71
72impl RegexCache {
73 pub fn new(budget: MemoryBudget) -> Self {
74 Self {
75 budget,
76 entries: Mutex::new(Entries::default()),
77 }
78 }
79
80 pub fn shares_allowance(&self, budget: &MemoryBudget) -> bool {
82 self.budget.shares_allowance(budget)
83 }
84
85 pub fn reserved_bytes(&self) -> usize {
88 let entries = self
89 .entries
90 .lock()
91 .unwrap_or_else(|error| error.into_inner());
92 entries.memory.as_ref().map_or(0, MemoryReservation::bytes)
93 + entries
94 .values
95 .iter()
96 .map(|entry| entry.pattern.capacity() + entry.regex.reserved_bytes())
97 .sum::<usize>()
98 }
99
100 pub fn clear(&self) {
102 let mut entries = self
103 .entries
104 .lock()
105 .unwrap_or_else(|error| error.into_inner());
106 *entries = Entries {
107 generation: entries.generation.wrapping_add(1),
108 ..Entries::default()
109 };
110 }
111
112 pub(super) fn take(&self, pattern: &str, flags: CompileFlags, collation: u32) -> Option<Entry> {
113 let mut entries = self
114 .entries
115 .lock()
116 .unwrap_or_else(|error| error.into_inner());
117 let index = entries
118 .values
119 .iter()
120 .position(|entry| entry.matches(pattern, flags, collation))?;
121 Some(entries.values.remove(index))
122 }
123
124 pub(super) fn generation(&self) -> u64 {
125 self.entries
126 .lock()
127 .unwrap_or_else(|error| error.into_inner())
128 .generation
129 }
130
131 pub(super) fn admit(
133 &self,
134 pattern: &str,
135 bytes: usize,
136 original: Option<&MemoryBudget>,
137 generation: u64,
138 ) -> Option<Admission> {
139 if self.prepare().ok()? != generation {
140 return None;
141 }
142 let shared = original.is_some_and(|budget| self.budget.shares_allowance(budget));
143 let additional_state = if shared { 0 } else { bytes };
144 let mut key = BudgetedString::new(&self.budget);
145 loop {
146 match key.push_str(pattern) {
147 Ok(()) => break,
148 Err(ref error) if self.evict_for(error, additional_state) => {}
149 Err(_) => return None,
150 }
151 }
152 let memory = if shared {
153 None
154 } else {
155 loop {
156 match self.budget.reserve(bytes) {
157 Ok(memory) => break Some(memory),
158 Err(ref error) if self.evict_for(error, 0) => {}
159 Err(_) => return None,
160 }
161 }
162 };
163 Some(Admission {
164 pattern: key,
165 generation,
166 memory,
167 })
168 }
169
170 pub(super) fn prepare(&self) -> Result<u64, MemoryError> {
171 let mut entries = self
172 .entries
173 .lock()
174 .unwrap_or_else(|error| error.into_inner());
175 if entries.values.capacity() == 0 {
176 let mut slots = BudgetedVec::<Entry>::new(&self.budget);
177 slots.reserve(CAPACITY)?;
178 let (values, memory) = slots.into_parts();
179 *entries = Entries {
180 values,
181 memory: Some(memory),
182 generation: entries.generation,
183 };
184 }
185 Ok(entries.generation)
186 }
187
188 fn evict_for(&self, error: &MemoryError, pending_bytes: usize) -> bool {
189 let MemoryError::Limit { required, limit } = error else {
190 return false;
191 };
192 let Some(missing) = required
193 .checked_sub(*limit)
194 .and_then(|bytes| bytes.checked_add(pending_bytes))
195 else {
196 return false;
197 };
198 let mut entries = self
199 .entries
200 .lock()
201 .unwrap_or_else(|error| error.into_inner());
202 let reclaimable = entries.values.iter().try_fold(0usize, |bytes, entry| {
204 bytes
205 .checked_add(entry.pattern.capacity())?
206 .checked_add(entry.regex.reserved_bytes())
207 });
208 if entries.values.is_empty() || reclaimable.is_none_or(|bytes| bytes < missing) {
209 return false;
210 }
211 entries.values.remove(0);
212 true
213 }
214
215 pub(super) fn keep(&self, entry: Entry) {
216 let mut entries = self
217 .entries
218 .lock()
219 .unwrap_or_else(|error| error.into_inner());
220 if entry.generation != entries.generation
221 || entries.memory.is_none()
222 || entries
223 .values
224 .iter()
225 .any(|old| old.matches(&entry.pattern, entry.flags, entry.collation))
226 {
227 return;
228 }
229 if entries.values.len() == CAPACITY {
230 entries.values.remove(0);
231 }
232 entries.values.push(entry);
234 }
235}
236
237thread_local! {
238 static CURRENT: RefCell<Option<Arc<RegexCache>>> = const { RefCell::new(None) };
239}
240
241pub fn current_regex_cache() -> Option<Arc<RegexCache>> {
243 CURRENT.with_borrow(Clone::clone)
244}
245
246pub struct RegexCacheScope {
248 previous: Option<Arc<RegexCache>>,
249 thread: PhantomData<Rc<()>>,
250}
251
252impl RegexCacheScope {
253 pub fn enter(cache: Option<Arc<RegexCache>>) -> Self {
254 Self {
255 previous: CURRENT.replace(cache),
256 thread: PhantomData,
257 }
258 }
259}
260
261impl Drop for RegexCacheScope {
262 fn drop(&mut self) {
263 CURRENT.set(self.previous.take());
264 }
265}
266
267#[cfg(test)]
268pub(super) mod tests;