use std::collections::{BTreeMap, HashMap};
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex};
use std::time::{Duration, Instant};
use mlua::{ExternalResult as _, Lua, LuaSerdeExt as _, Table, UserData, UserDataMethods, Value};
#[derive(Debug, Clone)]
pub struct CacheOptions {
pub max_entries: usize,
pub max_bytes: u64,
pub default_ttl: u64,
}
impl Default for CacheOptions {
fn default() -> Self {
Self {
max_entries: 10_000,
max_bytes: 32 * 1024 * 1024,
default_ttl: 300,
}
}
}
struct Entry {
value: Vec<u8>,
expires_at: Option<Instant>,
touched: u64,
inserted: u64,
}
const MAX_KEY_BYTES: usize = 1024;
const MAX_TTL_SECS: u64 = 10 * 365 * 24 * 60 * 60;
impl Entry {
fn cost(key: &str, value: &[u8]) -> u64 {
(key.len() + value.len()) as u64
}
}
impl Entry {
fn is_live(&self, now: Instant) -> bool {
self.expires_at.is_none_or(|at| at > now)
}
}
#[derive(Default)]
struct Inner {
entries: HashMap<Arc<str>, Entry>,
lru: BTreeMap<u64, Arc<str>>,
expiry: BTreeMap<(Instant, u64), Arc<str>>,
bytes: u64,
hits: u64,
misses: u64,
evictions: u64,
}
impl Inner {
fn remove(&mut self, key: &str) -> Option<Entry> {
let (key, entry) = self.entries.remove_entry(key)?;
self.lru.remove(&entry.touched);
if let Some(at) = entry.expires_at {
self.expiry.remove(&(at, entry.inserted));
}
self.bytes = self.bytes.saturating_sub(Entry::cost(&key, &entry.value));
Some(entry)
}
}
#[derive(Clone)]
pub struct Cache {
inner: Arc<Mutex<Inner>>,
opts: Arc<CacheOptions>,
clock: Arc<AtomicU64>,
}
impl std::fmt::Debug for Cache {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("Cache")
.field("max_entries", &self.opts.max_entries)
.field("max_bytes", &self.opts.max_bytes)
.finish_non_exhaustive()
}
}
impl Cache {
pub fn new(opts: CacheOptions) -> Self {
Self {
inner: Arc::new(Mutex::new(Inner::default())),
opts: Arc::new(opts),
clock: Arc::new(AtomicU64::new(0)),
}
}
pub fn clear(&self) -> mlua::Result<()> {
let mut inner = self.lock()?;
inner.entries.clear();
inner.lru.clear();
inner.expiry.clear();
inner.bytes = 0;
Ok(())
}
fn lock(&self) -> mlua::Result<std::sync::MutexGuard<'_, Inner>> {
self.inner
.lock()
.map_err(|_| mlua::Error::RuntimeError("the cache lock is poisoned".into()))
}
fn tick(&self) -> u64 {
self.clock.fetch_add(1, Ordering::Relaxed)
}
fn get_raw(&self, key: &str) -> mlua::Result<Option<Vec<u8>>> {
let now = crate::clock::now_instant();
let touched = self.tick();
let mut inner = self.lock()?;
let inner = &mut *inner;
match inner.entries.get_mut(key) {
Some(entry) if entry.is_live(now) => {
let previous = std::mem::replace(&mut entry.touched, touched);
let value = entry.value.clone();
if let Some(shared) = inner.lru.remove(&previous) {
inner.lru.insert(touched, shared);
}
inner.hits += 1;
Ok(Some(value))
}
Some(_) => {
inner.remove(key);
inner.misses += 1;
Ok(None)
}
None => {
inner.misses += 1;
Ok(None)
}
}
}
fn set_raw(&self, key: String, value: Vec<u8>, ttl: Option<u64>) -> mlua::Result<()> {
if key.len() > MAX_KEY_BYTES {
return Err(mlua::Error::RuntimeError(format!(
"cache key is {} bytes; keys are bounded to {MAX_KEY_BYTES} (hash a long \
key first)",
key.len()
)));
}
let size = Entry::cost(&key, &value);
if size > self.opts.max_bytes {
return Err(mlua::Error::RuntimeError(format!(
"cache value for `{key}` is {size} bytes, larger than the whole \
{} byte cache",
self.opts.max_bytes
)));
}
let ttl = ttl.unwrap_or(self.opts.default_ttl);
let expires_at = (ttl > 0)
.then(|| {
crate::clock::now_instant().checked_add(Duration::from_secs(ttl.min(MAX_TTL_SECS)))
})
.flatten();
let touched = self.tick();
let mut inner = self.lock()?;
let inner = &mut *inner;
inner.remove(&key);
let key: Arc<str> = key.into();
inner.bytes += size;
inner.lru.insert(touched, key.clone());
if let Some(at) = expires_at {
inner.expiry.insert((at, touched), key.clone());
}
inner.entries.insert(
key,
Entry {
value,
expires_at,
touched,
inserted: touched,
},
);
self.evict(inner);
Ok(())
}
fn evict(&self, inner: &mut Inner) {
let now = crate::clock::now_instant();
while inner.entries.len() > self.opts.max_entries || inner.bytes > self.opts.max_bytes {
let expired = inner
.expiry
.first_key_value()
.filter(|((at, _), _)| *at <= now)
.map(|(_, key)| key.clone());
match expired {
Some(key) => {
inner.remove(&key);
}
None => {
let Some(victim) = inner.lru.first_key_value().map(|(_, key)| key.clone())
else {
break;
};
inner.remove(&victim);
inner.evictions += 1;
}
}
}
}
}
impl UserData for Cache {
fn add_methods<M: UserDataMethods<Self>>(methods: &mut M) {
methods.add_method("get", |lua, cache, key: String| {
match cache.get_raw(&key)? {
Some(bytes) => {
let json: serde_json::Value = serde_json::from_slice(&bytes).into_lua_err()?;
lua.to_value(&json)
}
None => Ok(Value::Nil),
}
});
methods.add_method(
"set",
|_, cache, (key, value, opts): (String, Value, Option<Table>)| {
if value.is_nil() || value.is_null() {
cache.lock()?.remove(&key);
return Ok(());
}
let ttl = match &opts {
Some(opts) => opts.get::<Option<u64>>("ttl")?,
None => None,
};
let bytes = crate::bounded::to_json_vec(&value).map_err(|err| {
mlua::Error::RuntimeError(format!(
"cache values must be plain data (a table, string, number or \
boolean); `{key}` is not serializable: {err}"
))
})?;
cache.set_raw(key, bytes, ttl)?;
Ok(())
},
);
methods.add_method("delete", |_, cache, key: String| {
let mut inner = cache.lock()?;
Ok(inner.remove(&key).is_some())
});
methods.add_method("clear", |_, cache, ()| cache.clear());
methods.add_async_method(
"remember",
|lua, cache, (key, arg, f): (String, Value, Option<mlua::Function>)| async move {
let (opts, f) = match (arg, f) {
(Value::Function(f), None) => (None, f),
(Value::Table(opts), Some(f)) => (Some(opts), f),
_ => {
return Err(mlua::Error::RuntimeError(
"cache:remember expects (key, fn) or (key, opts, fn)".into(),
));
}
};
if let Some(bytes) = cache.get_raw(&key)? {
let json: serde_json::Value = serde_json::from_slice(&bytes).into_lua_err()?;
return lua.to_value(&json);
}
let ttl = match &opts {
Some(opts) => opts.get::<Option<u64>>("ttl")?,
None => None,
};
let value: Value = f.call_async(()).await?;
if value.is_nil() {
return Ok(Value::Nil);
}
let bytes = crate::bounded::to_json_vec(&value).map_err(|err| {
mlua::Error::RuntimeError(format!(
"cache:remember value for `{key}` is not serializable: {err}"
))
})?;
cache.set_raw(key, bytes, ttl)?;
Ok(value)
},
);
methods.add_method("stats", |lua, cache, ()| {
let inner = cache.lock()?;
let table = lua.create_table()?;
table.set("entries", inner.entries.len())?;
table.set("bytes", inner.bytes)?;
table.set("hits", inner.hits)?;
table.set("misses", inner.misses)?;
table.set("evictions", inner.evictions)?;
table.set("max_entries", cache.opts.max_entries)?;
table.set("max_bytes", cache.opts.max_bytes)?;
Ok(table)
});
}
}
pub(crate) fn create_cache(lua: &Lua, cache: Cache) -> mlua::Result<mlua::AnyUserData> {
lua.create_userdata(cache)
}
#[cfg(test)]
mod tests {
use super::*;
fn cache(opts: CacheOptions) -> Cache {
Cache::new(opts)
}
fn deep_table(lua: &Lua, depth: usize) -> Value {
let root = lua.create_table().expect("table");
let mut cur = root.clone();
for _ in 1..depth {
let next = lua.create_table().expect("table");
cur.set("x", next.clone()).expect("set");
cur = next;
}
Value::Table(root)
}
#[test]
fn set_rejects_values_nested_beyond_the_json_depth_bound() {
let lua = Lua::new();
let ud = lua
.create_userdata(cache(CacheOptions::default()))
.expect("ud");
lua.globals().set("cache", ud).expect("global");
lua.globals()
.set("deep", deep_table(&lua, 129))
.expect("global");
let err: String = lua
.load(
r#"local ok, err = pcall(function() cache:set("k", deep) end)
assert(not ok)
return tostring(err)"#,
)
.eval()
.expect("eval");
assert!(err.contains("nested deeper than 128 levels"), "got: {err}");
}
#[test]
fn setting_nil_removes_the_key() {
let lua = Lua::new();
let ud = lua
.create_userdata(cache(CacheOptions::default()))
.expect("ud");
lua.globals().set("cache", ud).expect("global");
let (gone, entries): (bool, i64) = lua
.load(
r#"cache:set("k", 1)
cache:set("k", nil)
return cache:get("k") == nil, cache:stats().entries"#,
)
.eval()
.expect("eval");
assert!(gone);
assert_eq!(entries, 0);
}
#[test]
fn values_round_trip_and_count_against_the_bounds() {
let c = cache(CacheOptions::default());
c.set_raw("a".into(), b"{\"n\":1}".to_vec(), None)
.expect("set");
assert_eq!(
c.get_raw("a").expect("get").as_deref(),
Some(&b"{\"n\":1}"[..])
);
assert_eq!(c.get_raw("missing").expect("get"), None);
let inner = c.inner.lock().expect("lock");
assert_eq!(inner.entries.len(), 1);
assert_eq!(inner.bytes, Entry::cost("a", b"{\"n\":1}"));
assert_eq!((inner.hits, inner.misses), (1, 1));
}
#[test]
fn clear_empties_every_handle_to_the_cache() {
let c = cache(CacheOptions::default());
let shared = c.clone();
c.set_raw("a".into(), b"1".to_vec(), Some(60)).expect("set");
c.set_raw("b".into(), b"2".to_vec(), None).expect("set");
shared.clear().expect("clear");
assert_eq!(c.get_raw("a").expect("get"), None);
assert_eq!(c.get_raw("b").expect("get"), None);
let inner = c.inner.lock().expect("lock");
assert!(inner.entries.is_empty() && inner.lru.is_empty() && inner.expiry.is_empty());
assert_eq!(inner.bytes, 0);
}
#[test]
fn overwriting_a_key_does_not_double_count_its_bytes() {
let c = cache(CacheOptions::default());
c.set_raw("k".into(), vec![b'x'; 100], None).expect("set");
c.set_raw("k".into(), vec![b'y'; 10], None)
.expect("overwrite");
let inner = c.inner.lock().expect("lock");
assert_eq!(inner.entries.len(), 1);
assert_eq!(inner.bytes, Entry::cost("k", &[b'y'; 10]));
}
#[test]
fn the_least_recently_used_entry_is_evicted_first() {
let c = cache(CacheOptions {
max_entries: 2,
..Default::default()
});
c.set_raw("a".into(), b"1".to_vec(), None).expect("set a");
c.set_raw("b".into(), b"2".to_vec(), None).expect("set b");
c.get_raw("a").expect("get a");
c.set_raw("c".into(), b"3".to_vec(), None).expect("set c");
assert!(c.get_raw("a").expect("a").is_some());
assert!(c.get_raw("b").expect("b").is_none(), "b must be evicted");
assert!(c.get_raw("c").expect("c").is_some());
}
#[test]
fn the_byte_bound_evicts_too() {
let c = cache(CacheOptions {
max_bytes: 100,
..Default::default()
});
c.set_raw("a".into(), vec![b'x'; 60], None).expect("set a");
c.set_raw("b".into(), vec![b'x'; 60], None).expect("set b");
let inner = c.inner.lock().expect("lock");
assert!(inner.bytes <= 100, "bytes must stay within the bound");
assert_eq!(inner.entries.len(), 1);
assert_eq!(inner.evictions, 1);
}
#[test]
fn a_value_larger_than_the_whole_cache_is_refused() {
let c = cache(CacheOptions {
max_bytes: 10,
..Default::default()
});
let err = c
.set_raw("big".into(), vec![b'x'; 11], None)
.expect_err("must be refused");
assert!(err.to_string().contains("larger than"), "{err}");
}
#[test]
fn an_expired_entry_reads_as_a_miss_and_frees_its_bytes() {
let c = cache(CacheOptions::default());
c.set_raw("k".into(), vec![b'x'; 50], Some(1)).expect("set");
{
let mut inner = c.inner.lock().expect("lock");
let entry = inner.entries.get_mut("k").expect("entry");
entry.expires_at = Some(Instant::now() - Duration::from_secs(1));
}
assert!(c.get_raw("k").expect("get").is_none());
assert_eq!(c.inner.lock().expect("lock").bytes, 0);
}
#[test]
fn a_zero_ttl_never_expires() {
let c = cache(CacheOptions {
default_ttl: 0,
..Default::default()
});
c.set_raw("k".into(), b"v".to_vec(), None).expect("set");
assert!(
c.inner.lock().expect("lock").entries["k"]
.expires_at
.is_none()
);
}
}