1use std::collections::{BTreeMap, HashMap};
27use std::sync::atomic::{AtomicU64, Ordering};
28use std::sync::{Arc, Mutex};
29use std::time::{Duration, Instant};
30
31use mlua::{ExternalResult as _, Lua, LuaSerdeExt as _, Table, UserData, UserDataMethods, Value};
32
33#[derive(Debug, Clone)]
35pub struct CacheOptions {
36 pub max_entries: usize,
38 pub max_bytes: u64,
40 pub default_ttl: u64,
42}
43
44impl Default for CacheOptions {
45 fn default() -> Self {
46 Self {
47 max_entries: 10_000,
48 max_bytes: 32 * 1024 * 1024,
49 default_ttl: 300,
50 }
51 }
52}
53
54struct Entry {
55 value: Vec<u8>,
57 expires_at: Option<Instant>,
59 touched: u64,
61 inserted: u64,
65}
66
67const MAX_KEY_BYTES: usize = 1024;
70
71const MAX_TTL_SECS: u64 = 10 * 365 * 24 * 60 * 60;
75
76impl Entry {
77 fn cost(key: &str, value: &[u8]) -> u64 {
79 (key.len() + value.len()) as u64
80 }
81}
82
83impl Entry {
84 fn is_live(&self, now: Instant) -> bool {
85 self.expires_at.is_none_or(|at| at > now)
86 }
87}
88
89#[derive(Default)]
98struct Inner {
99 entries: HashMap<Arc<str>, Entry>,
100 lru: BTreeMap<u64, Arc<str>>,
103 expiry: BTreeMap<(Instant, u64), Arc<str>>,
105 bytes: u64,
106 hits: u64,
107 misses: u64,
108 evictions: u64,
109}
110
111impl Inner {
112 fn remove(&mut self, key: &str) -> Option<Entry> {
114 let (key, entry) = self.entries.remove_entry(key)?;
115 self.lru.remove(&entry.touched);
116 if let Some(at) = entry.expires_at {
117 self.expiry.remove(&(at, entry.inserted));
118 }
119 self.bytes = self.bytes.saturating_sub(Entry::cost(&key, &entry.value));
124 Some(entry)
125 }
126}
127
128#[derive(Clone)]
131pub struct Cache {
132 inner: Arc<Mutex<Inner>>,
133 opts: Arc<CacheOptions>,
134 clock: Arc<AtomicU64>,
137}
138
139impl std::fmt::Debug for Cache {
140 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
141 f.debug_struct("Cache")
142 .field("max_entries", &self.opts.max_entries)
143 .field("max_bytes", &self.opts.max_bytes)
144 .finish_non_exhaustive()
145 }
146}
147
148impl Cache {
149 pub fn new(opts: CacheOptions) -> Self {
151 Self {
152 inner: Arc::new(Mutex::new(Inner::default())),
153 opts: Arc::new(opts),
154 clock: Arc::new(AtomicU64::new(0)),
155 }
156 }
157
158 pub fn clear(&self) -> mlua::Result<()> {
165 let mut inner = self.lock()?;
166 inner.entries.clear();
167 inner.lru.clear();
168 inner.expiry.clear();
169 inner.bytes = 0;
170 Ok(())
171 }
172
173 fn lock(&self) -> mlua::Result<std::sync::MutexGuard<'_, Inner>> {
174 self.inner
175 .lock()
176 .map_err(|_| mlua::Error::RuntimeError("the cache lock is poisoned".into()))
177 }
178
179 fn tick(&self) -> u64 {
180 self.clock.fetch_add(1, Ordering::Relaxed)
181 }
182
183 fn get_raw(&self, key: &str) -> mlua::Result<Option<Vec<u8>>> {
184 let now = crate::clock::now_instant();
187 let touched = self.tick();
188 let mut inner = self.lock()?;
189 let inner = &mut *inner;
190
191 match inner.entries.get_mut(key) {
192 Some(entry) if entry.is_live(now) => {
193 let previous = std::mem::replace(&mut entry.touched, touched);
195 let value = entry.value.clone();
196 if let Some(shared) = inner.lru.remove(&previous) {
197 inner.lru.insert(touched, shared);
198 }
199 inner.hits += 1;
200 Ok(Some(value))
201 }
202 Some(_) => {
205 inner.remove(key);
206 inner.misses += 1;
207 Ok(None)
208 }
209 None => {
210 inner.misses += 1;
211 Ok(None)
212 }
213 }
214 }
215
216 fn set_raw(&self, key: String, value: Vec<u8>, ttl: Option<u64>) -> mlua::Result<()> {
217 if key.len() > MAX_KEY_BYTES {
218 return Err(mlua::Error::RuntimeError(format!(
219 "cache key is {} bytes; keys are bounded to {MAX_KEY_BYTES} (hash a long \
220 key first)",
221 key.len()
222 )));
223 }
224 let size = Entry::cost(&key, &value);
228 if size > self.opts.max_bytes {
229 return Err(mlua::Error::RuntimeError(format!(
230 "cache value for `{key}` is {size} bytes, larger than the whole \
231 {} byte cache",
232 self.opts.max_bytes
233 )));
234 }
235 let ttl = ttl.unwrap_or(self.opts.default_ttl);
236 let expires_at = (ttl > 0)
240 .then(|| {
241 crate::clock::now_instant().checked_add(Duration::from_secs(ttl.min(MAX_TTL_SECS)))
242 })
243 .flatten();
244 let touched = self.tick();
245 let mut inner = self.lock()?;
246 let inner = &mut *inner;
247
248 inner.remove(&key);
249 let key: Arc<str> = key.into();
250 inner.bytes += size;
251 inner.lru.insert(touched, key.clone());
252 if let Some(at) = expires_at {
253 inner.expiry.insert((at, touched), key.clone());
254 }
255 inner.entries.insert(
256 key,
257 Entry {
258 value,
259 expires_at,
260 touched,
261 inserted: touched,
262 },
263 );
264 self.evict(inner);
265 Ok(())
266 }
267
268 fn evict(&self, inner: &mut Inner) {
276 let now = crate::clock::now_instant();
277 while inner.entries.len() > self.opts.max_entries || inner.bytes > self.opts.max_bytes {
278 let expired = inner
279 .expiry
280 .first_key_value()
281 .filter(|((at, _), _)| *at <= now)
282 .map(|(_, key)| key.clone());
283 match expired {
284 Some(key) => {
285 inner.remove(&key);
286 }
287 None => {
288 let Some(victim) = inner.lru.first_key_value().map(|(_, key)| key.clone())
289 else {
290 break;
291 };
292 inner.remove(&victim);
293 inner.evictions += 1;
294 }
295 }
296 }
297 }
298}
299
300impl UserData for Cache {
301 fn add_methods<M: UserDataMethods<Self>>(methods: &mut M) {
302 methods.add_method("get", |lua, cache, key: String| {
304 match cache.get_raw(&key)? {
305 Some(bytes) => {
306 let json: serde_json::Value = serde_json::from_slice(&bytes).into_lua_err()?;
307 lua.to_value(&json)
308 }
309 None => Ok(Value::Nil),
310 }
311 });
312
313 methods.add_method(
319 "set",
320 |_, cache, (key, value, opts): (String, Value, Option<Table>)| {
321 if value.is_nil() || value.is_null() {
322 cache.lock()?.remove(&key);
323 return Ok(());
324 }
325 let ttl = match &opts {
326 Some(opts) => opts.get::<Option<u64>>("ttl")?,
327 None => None,
328 };
329 let bytes = crate::bounded::to_json_vec(&value).map_err(|err| {
330 mlua::Error::RuntimeError(format!(
331 "cache values must be plain data (a table, string, number or \
332 boolean); `{key}` is not serializable: {err}"
333 ))
334 })?;
335 cache.set_raw(key, bytes, ttl)?;
336 Ok(())
337 },
338 );
339
340 methods.add_method("delete", |_, cache, key: String| {
342 let mut inner = cache.lock()?;
343 Ok(inner.remove(&key).is_some())
344 });
345
346 methods.add_method("clear", |_, cache, ()| cache.clear());
347
348 methods.add_async_method(
354 "remember",
355 |lua, cache, (key, arg, f): (String, Value, Option<mlua::Function>)| async move {
356 let (opts, f) = match (arg, f) {
358 (Value::Function(f), None) => (None, f),
359 (Value::Table(opts), Some(f)) => (Some(opts), f),
360 _ => {
361 return Err(mlua::Error::RuntimeError(
362 "cache:remember expects (key, fn) or (key, opts, fn)".into(),
363 ));
364 }
365 };
366 if let Some(bytes) = cache.get_raw(&key)? {
367 let json: serde_json::Value = serde_json::from_slice(&bytes).into_lua_err()?;
368 return lua.to_value(&json);
369 }
370 let ttl = match &opts {
371 Some(opts) => opts.get::<Option<u64>>("ttl")?,
372 None => None,
373 };
374 let value: Value = f.call_async(()).await?;
375 if value.is_nil() {
379 return Ok(Value::Nil);
380 }
381 let bytes = crate::bounded::to_json_vec(&value).map_err(|err| {
382 mlua::Error::RuntimeError(format!(
383 "cache:remember value for `{key}` is not serializable: {err}"
384 ))
385 })?;
386 cache.set_raw(key, bytes, ttl)?;
387 Ok(value)
388 },
389 );
390
391 methods.add_method("stats", |lua, cache, ()| {
393 let inner = cache.lock()?;
394 let table = lua.create_table()?;
395 table.set("entries", inner.entries.len())?;
396 table.set("bytes", inner.bytes)?;
397 table.set("hits", inner.hits)?;
398 table.set("misses", inner.misses)?;
399 table.set("evictions", inner.evictions)?;
400 table.set("max_entries", cache.opts.max_entries)?;
401 table.set("max_bytes", cache.opts.max_bytes)?;
402 Ok(table)
403 });
404 }
405}
406
407pub(crate) fn create_cache(lua: &Lua, cache: Cache) -> mlua::Result<mlua::AnyUserData> {
409 lua.create_userdata(cache)
410}
411
412#[cfg(test)]
413mod tests {
414 use super::*;
415
416 fn cache(opts: CacheOptions) -> Cache {
417 Cache::new(opts)
418 }
419
420 fn deep_table(lua: &Lua, depth: usize) -> Value {
422 let root = lua.create_table().expect("table");
423 let mut cur = root.clone();
424 for _ in 1..depth {
425 let next = lua.create_table().expect("table");
426 cur.set("x", next.clone()).expect("set");
427 cur = next;
428 }
429 Value::Table(root)
430 }
431
432 #[test]
435 fn set_rejects_values_nested_beyond_the_json_depth_bound() {
436 let lua = Lua::new();
437 let ud = lua
438 .create_userdata(cache(CacheOptions::default()))
439 .expect("ud");
440 lua.globals().set("cache", ud).expect("global");
441 lua.globals()
442 .set("deep", deep_table(&lua, 129))
443 .expect("global");
444 let err: String = lua
445 .load(
446 r#"local ok, err = pcall(function() cache:set("k", deep) end)
447 assert(not ok)
448 return tostring(err)"#,
449 )
450 .eval()
451 .expect("eval");
452 assert!(err.contains("nested deeper than 128 levels"), "got: {err}");
453 }
454
455 #[test]
458 fn setting_nil_removes_the_key() {
459 let lua = Lua::new();
460 let ud = lua
461 .create_userdata(cache(CacheOptions::default()))
462 .expect("ud");
463 lua.globals().set("cache", ud).expect("global");
464 let (gone, entries): (bool, i64) = lua
465 .load(
466 r#"cache:set("k", 1)
467 cache:set("k", nil)
468 return cache:get("k") == nil, cache:stats().entries"#,
469 )
470 .eval()
471 .expect("eval");
472 assert!(gone);
473 assert_eq!(entries, 0);
474 }
475
476 #[test]
477 fn values_round_trip_and_count_against_the_bounds() {
478 let c = cache(CacheOptions::default());
479 c.set_raw("a".into(), b"{\"n\":1}".to_vec(), None)
480 .expect("set");
481 assert_eq!(
482 c.get_raw("a").expect("get").as_deref(),
483 Some(&b"{\"n\":1}"[..])
484 );
485 assert_eq!(c.get_raw("missing").expect("get"), None);
486
487 let inner = c.inner.lock().expect("lock");
488 assert_eq!(inner.entries.len(), 1);
489 assert_eq!(inner.bytes, Entry::cost("a", b"{\"n\":1}"));
491 assert_eq!((inner.hits, inner.misses), (1, 1));
492 }
493
494 #[test]
498 fn clear_empties_every_handle_to_the_cache() {
499 let c = cache(CacheOptions::default());
500 let shared = c.clone();
501 c.set_raw("a".into(), b"1".to_vec(), Some(60)).expect("set");
502 c.set_raw("b".into(), b"2".to_vec(), None).expect("set");
503 shared.clear().expect("clear");
504 assert_eq!(c.get_raw("a").expect("get"), None);
505 assert_eq!(c.get_raw("b").expect("get"), None);
506 let inner = c.inner.lock().expect("lock");
507 assert!(inner.entries.is_empty() && inner.lru.is_empty() && inner.expiry.is_empty());
508 assert_eq!(inner.bytes, 0);
509 }
510
511 #[test]
512 fn overwriting_a_key_does_not_double_count_its_bytes() {
513 let c = cache(CacheOptions::default());
514 c.set_raw("k".into(), vec![b'x'; 100], None).expect("set");
515 c.set_raw("k".into(), vec![b'y'; 10], None)
516 .expect("overwrite");
517 let inner = c.inner.lock().expect("lock");
518 assert_eq!(inner.entries.len(), 1);
519 assert_eq!(inner.bytes, Entry::cost("k", &[b'y'; 10]));
520 }
521
522 #[test]
523 fn the_least_recently_used_entry_is_evicted_first() {
524 let c = cache(CacheOptions {
525 max_entries: 2,
526 ..Default::default()
527 });
528 c.set_raw("a".into(), b"1".to_vec(), None).expect("set a");
529 c.set_raw("b".into(), b"2".to_vec(), None).expect("set b");
530 c.get_raw("a").expect("get a");
532 c.set_raw("c".into(), b"3".to_vec(), None).expect("set c");
533
534 assert!(c.get_raw("a").expect("a").is_some());
535 assert!(c.get_raw("b").expect("b").is_none(), "b must be evicted");
536 assert!(c.get_raw("c").expect("c").is_some());
537 }
538
539 #[test]
540 fn the_byte_bound_evicts_too() {
541 let c = cache(CacheOptions {
542 max_bytes: 100,
543 ..Default::default()
544 });
545 c.set_raw("a".into(), vec![b'x'; 60], None).expect("set a");
546 c.set_raw("b".into(), vec![b'x'; 60], None).expect("set b");
547
548 let inner = c.inner.lock().expect("lock");
549 assert!(inner.bytes <= 100, "bytes must stay within the bound");
550 assert_eq!(inner.entries.len(), 1);
551 assert_eq!(inner.evictions, 1);
552 }
553
554 #[test]
555 fn a_value_larger_than_the_whole_cache_is_refused() {
556 let c = cache(CacheOptions {
557 max_bytes: 10,
558 ..Default::default()
559 });
560 let err = c
561 .set_raw("big".into(), vec![b'x'; 11], None)
562 .expect_err("must be refused");
563 assert!(err.to_string().contains("larger than"), "{err}");
564 }
565
566 #[test]
567 fn an_expired_entry_reads_as_a_miss_and_frees_its_bytes() {
568 let c = cache(CacheOptions::default());
569 c.set_raw("k".into(), vec![b'x'; 50], Some(1)).expect("set");
571 {
572 let mut inner = c.inner.lock().expect("lock");
573 let entry = inner.entries.get_mut("k").expect("entry");
574 entry.expires_at = Some(Instant::now() - Duration::from_secs(1));
575 }
576 assert!(c.get_raw("k").expect("get").is_none());
577 assert_eq!(c.inner.lock().expect("lock").bytes, 0);
578 }
579
580 #[test]
581 fn a_zero_ttl_never_expires() {
582 let c = cache(CacheOptions {
583 default_ttl: 0,
584 ..Default::default()
585 });
586 c.set_raw("k".into(), b"v".to_vec(), None).expect("set");
587 assert!(
588 c.inner.lock().expect("lock").entries["k"]
589 .expires_at
590 .is_none()
591 );
592 }
593}