use std::collections::BTreeMap;
use std::path::{Component, Path};
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex, PoisonError};
use serde::{Deserialize, Serialize};
pub const CACHE_VERSION: u32 = 1;
const MAGIC: [u8; 8] = *b"SKIFCACH";
const PREFIX: usize = MAGIC.len() + 4;
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct CacheNamespace {
pub name: &'static str,
pub schema: u32,
}
impl CacheNamespace {
#[must_use]
pub const fn new(name: &'static str, schema: u32) -> Self {
Self { name, schema }
}
#[must_use]
pub fn is_valid_name(name: &str) -> bool {
!name.is_empty()
&& name.len() <= 64
&& !name.starts_with('.')
&& name
.bytes()
.all(|byte| byte.is_ascii_lowercase() || byte.is_ascii_digit() || matches!(byte, b'.' | b'-'))
}
}
pub trait CacheStore: Send + Sync {
fn get(&self, namespace: CacheNamespace, key: &[u8; 32]) -> Option<Arc<[u8]>>;
fn put(&self, namespace: CacheNamespace, key: &[u8; 32], value: Arc<[u8]>);
}
type Key = [u8; 32];
type Entries = BTreeMap<(&'static str, Key), Arc<[u8]>>;
#[derive(Debug, Default)]
pub struct MemoryStore {
entries: Mutex<Entries>,
}
impl MemoryStore {
#[must_use]
pub fn new() -> Self {
Self::default()
}
#[must_use]
pub fn len(&self) -> usize {
self.entries.lock().unwrap_or_else(PoisonError::into_inner).len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[must_use]
pub fn entries(&self) -> Vec<(&'static str, Key, Arc<[u8]>)> {
self.entries
.lock()
.unwrap_or_else(PoisonError::into_inner)
.iter()
.map(|((name, key), value)| (*name, *key, Arc::clone(value)))
.collect()
}
}
impl CacheStore for MemoryStore {
fn get(&self, namespace: CacheNamespace, key: &[u8; 32]) -> Option<Arc<[u8]>> {
self.entries
.lock()
.unwrap_or_else(PoisonError::into_inner)
.get(&(namespace.name, *key))
.cloned()
}
fn put(&self, namespace: CacheNamespace, key: &[u8; 32], value: Arc<[u8]>) {
self.entries
.lock()
.unwrap_or_else(PoisonError::into_inner)
.insert((namespace.name, *key), value);
}
}
#[derive(Clone)]
pub struct CacheHandle {
store: Arc<dyn CacheStore>,
salt: [u8; 32],
}
impl CacheHandle {
#[must_use]
pub fn new(store: Arc<dyn CacheStore>, salt: [u8; 32]) -> Self {
Self { store, salt }
}
#[must_use]
pub fn store(&self) -> &Arc<dyn CacheStore> {
&self.store
}
#[must_use]
pub const fn salt(&self) -> &[u8; 32] {
&self.salt
}
}
impl std::fmt::Debug for CacheHandle {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("CacheHandle").finish_non_exhaustive()
}
}
#[must_use]
pub fn salt_digest(salt: &[u8]) -> [u8; 32] {
let mut hasher = blake3::Hasher::new_derive_key("skif cache salt v1");
hasher.update(salt);
*hasher.finalize().as_bytes()
}
#[must_use]
pub fn content_digest(content: &[u8]) -> [u8; 32] {
*blake3::hash(content).as_bytes()
}
#[derive(Debug, Clone)]
pub struct KeyBuilder {
hasher: blake3::Hasher,
}
impl KeyBuilder {
#[must_use]
pub fn new(namespace: CacheNamespace, salt: &[u8; 32]) -> Self {
let mut builder = Self {
hasher: blake3::Hasher::new_derive_key("skif cache key v1"),
};
builder.write(&CACHE_VERSION.to_le_bytes());
builder.write(env!("CARGO_PKG_VERSION").as_bytes());
builder.write(namespace.name.as_bytes());
builder.write(&namespace.schema.to_le_bytes());
builder.write(salt);
builder
}
fn write(&mut self, bytes: &[u8]) {
self.hasher.update(&(bytes.len() as u64).to_le_bytes());
self.hasher.update(bytes);
}
#[must_use]
pub fn bytes(mut self, field: &[u8]) -> Self {
self.write(field);
self
}
#[must_use]
pub fn config_digest(self, digest: &[u8; 32]) -> Self {
self.bytes(digest)
}
#[must_use]
pub fn content(self, content: &[u8]) -> Self {
self.bytes(&content_digest(content))
}
#[must_use]
pub fn relative_path(mut self, path: &Path) -> Self {
let mut spelled = Vec::new();
let mut absolute = false;
for component in path.components() {
match component {
Component::Normal(part) => {
if !spelled.is_empty() {
spelled.push(b'/');
}
spelled.extend_from_slice(part.as_encoded_bytes());
}
Component::ParentDir => {
if !spelled.is_empty() {
spelled.push(b'/');
}
spelled.extend_from_slice(b"..");
}
Component::CurDir => {}
Component::RootDir | Component::Prefix(_) => absolute = true,
}
}
self.write(&[u8::from(absolute)]);
if absolute {
self.write(path.as_os_str().as_encoded_bytes());
} else {
self.write(&spelled);
}
self
}
#[must_use]
pub fn finish(&self) -> [u8; 32] {
*self.hasher.finalize().as_bytes()
}
}
#[must_use]
pub fn seal(namespace: CacheNamespace, key: &[u8; 32], payload: &[u8]) -> Arc<[u8]> {
let name = namespace.name.as_bytes();
let name = &name[..name.len().min(usize::from(u8::MAX))];
let mut value = Vec::with_capacity(PREFIX + 1 + name.len() + 4 + 32 + 8 + 32 + payload.len());
value.extend_from_slice(&MAGIC);
value.extend_from_slice(&CACHE_VERSION.to_le_bytes());
#[allow(clippy::cast_possible_truncation)]
value.push(name.len() as u8);
value.extend_from_slice(name);
value.extend_from_slice(&namespace.schema.to_le_bytes());
value.extend_from_slice(key);
value.extend_from_slice(&(payload.len() as u64).to_le_bytes());
value.extend_from_slice(&content_digest(payload));
value.extend_from_slice(payload);
Arc::from(value)
}
#[must_use]
pub fn open<'a>(namespace: CacheNamespace, key: &[u8; 32], value: &'a [u8]) -> Option<&'a [u8]> {
let mut rest = value;
let mut take = |length: usize| -> Option<&'a [u8]> {
if rest.len() < length {
return None;
}
let (head, tail) = rest.split_at(length);
rest = tail;
Some(head)
};
if take(MAGIC.len())? != MAGIC || take(4)? != CACHE_VERSION.to_le_bytes() {
return None;
}
let length = usize::from(*take(1)?.first()?);
if take(length)? != namespace.name.as_bytes() || take(4)? != namespace.schema.to_le_bytes() || take(32)? != key {
return None;
}
let mut size = [0; 8];
size.copy_from_slice(take(8)?);
let size = usize::try_from(u64::from_le_bytes(size)).ok()?;
let checksum = take(32)?;
let payload = take(size)?;
if !rest.is_empty() || checksum != content_digest(payload) {
return None;
}
Some(payload)
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
#[serde(rename_all = "kebab-case")]
#[non_exhaustive]
pub struct CacheCounters {
pub hits: u64,
pub misses: u64,
pub bytes_written: u64,
}
impl CacheCounters {
#[must_use]
pub const fn new(hits: u64, misses: u64, bytes_written: u64) -> Self {
Self {
hits,
misses,
bytes_written,
}
}
pub const fn add(&mut self, other: Self) {
self.hits += other.hits;
self.misses += other.misses;
self.bytes_written += other.bytes_written;
}
}
#[derive(Debug, Default)]
pub struct CacheTally {
hits: AtomicU64,
misses: AtomicU64,
bytes_written: AtomicU64,
}
impl CacheTally {
#[must_use]
pub fn new() -> Self {
Self::default()
}
pub fn hit(&self) {
self.hits.fetch_add(1, Ordering::Relaxed);
}
pub fn miss(&self) {
self.misses.fetch_add(1, Ordering::Relaxed);
}
pub fn hit_after_miss(&self) {
self.hit();
let mut misses = self.misses.load(Ordering::Relaxed);
while let Some(fewer) = misses.checked_sub(1) {
match self
.misses
.compare_exchange_weak(misses, fewer, Ordering::Relaxed, Ordering::Relaxed)
{
Ok(_) => break,
Err(current) => misses = current,
}
}
}
pub fn written(&self, bytes: usize) {
self.bytes_written.fetch_add(bytes as u64, Ordering::Relaxed);
}
#[must_use]
pub fn snapshot(&self) -> CacheCounters {
CacheCounters {
hits: self.hits.load(Ordering::Relaxed),
misses: self.misses.load(Ordering::Relaxed),
bytes_written: self.bytes_written.load(Ordering::Relaxed),
}
}
}
const _: () = {
fn assert_send_sync<T: Send + Sync>() {}
let _ = assert_send_sync::<MemoryStore>;
let _ = assert_send_sync::<CacheHandle>;
let _ = assert_send_sync::<CacheTally>;
let _ = assert_send_sync::<Arc<dyn CacheStore>>;
};
#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tests {
use super::*;
const MODULES: CacheNamespace = CacheNamespace::new("modules", 3);
fn key(text: &str) -> [u8; 32] {
KeyBuilder::new(MODULES, &salt_digest(b""))
.content(text.as_bytes())
.finish()
}
#[test]
fn a_sealed_value_opens_to_its_payload() {
let key = key("a");
let value = seal(MODULES, &key, b"payload");
assert_eq!(open(MODULES, &key, &value), Some(&b"payload"[..]));
let empty = seal(MODULES, &key, b"");
assert_eq!(open(MODULES, &key, &empty), Some(&b""[..]));
}
#[test]
fn a_value_that_is_not_exactly_the_envelope_does_not_open() {
let key = key("a");
let value = seal(MODULES, &key, b"payload");
assert!(open(MODULES, &self::key("b"), &value).is_none(), "another key");
assert!(
open(CacheNamespace::new("modules", 4), &key, &value).is_none(),
"another schema"
);
assert!(
open(CacheNamespace::new("other", 3), &key, &value).is_none(),
"another namespace"
);
assert!(open(MODULES, &key, &value[..value.len() - 1]).is_none(), "truncated");
assert!(open(MODULES, &key, &[]).is_none(), "empty");
let mut longer = value.to_vec();
longer.push(0);
assert!(open(MODULES, &key, &longer).is_none(), "trailing bytes");
for at in 0..value.len() {
let mut flipped = value.to_vec();
flipped[at] ^= 0x01;
assert!(open(MODULES, &key, &flipped).is_none(), "flipped byte {at}");
}
}
#[test]
fn random_bytes_never_open() {
let key = key("a");
let mut state: u64 = 0x9e37_79b9_7f4a_7c15;
for length in 0..512 {
let bytes: Vec<u8> = (0..length)
.map(|_| {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state.to_le_bytes()[0]
})
.collect();
assert!(open(MODULES, &key, &bytes).is_none());
}
}
#[test]
fn the_key_changes_with_each_input() {
let salt = salt_digest(b"host");
let base = KeyBuilder::new(MODULES, &salt)
.relative_path(Path::new("src/a.ts"))
.content(b"x")
.finish();
let others = [
KeyBuilder::new(CacheNamespace::new("modules", 4), &salt)
.relative_path(Path::new("src/a.ts"))
.content(b"x")
.finish(),
KeyBuilder::new(CacheNamespace::new("other", 3), &salt)
.relative_path(Path::new("src/a.ts"))
.content(b"x")
.finish(),
KeyBuilder::new(MODULES, &salt_digest(b"other host"))
.relative_path(Path::new("src/a.ts"))
.content(b"x")
.finish(),
KeyBuilder::new(MODULES, &salt)
.relative_path(Path::new("src/b.ts"))
.content(b"x")
.finish(),
KeyBuilder::new(MODULES, &salt)
.relative_path(Path::new("src/a.ts"))
.content(b"y")
.finish(),
KeyBuilder::new(MODULES, &salt)
.relative_path(Path::new("/src/a.ts"))
.content(b"x")
.finish(),
];
for other in others {
assert_ne!(base, other);
}
assert_ne!(
KeyBuilder::new(MODULES, &salt).bytes(b"ab").bytes(b"c").finish(),
KeyBuilder::new(MODULES, &salt).bytes(b"a").bytes(b"bc").finish()
);
}
#[test]
fn a_relative_path_is_spelled_alike_on_every_platform() {
let salt = salt_digest(b"");
let key = |path: &str| KeyBuilder::new(MODULES, &salt).relative_path(Path::new(path)).finish();
assert_eq!(key("src/a.ts"), key("./src/a.ts"));
assert_eq!(key("src/a.ts"), key("src//a.ts"));
assert_ne!(key("../a.ts"), key("a.ts"));
}
#[test]
fn no_salt_and_an_empty_salt_are_the_same() {
assert_eq!(salt_digest(b""), salt_digest(&[]));
assert_ne!(salt_digest(b""), salt_digest(b"x"));
}
#[test]
fn namespace_names_are_safe_as_file_names() {
for good in ["modules", "other.facts", "a-1"] {
assert!(CacheNamespace::is_valid_name(good), "{good}");
}
for bad in ["", ".hidden", "Upper", "a/b", "a\\b", "..", &"x".repeat(65)] {
assert!(!CacheNamespace::is_valid_name(bad), "{bad}");
}
}
#[test]
fn a_memory_store_returns_what_was_put_per_namespace() {
let store = MemoryStore::new();
let key = key("a");
assert!(store.get(MODULES, &key).is_none());
store.put(MODULES, &key, Arc::from(&b"v"[..]));
assert_eq!(store.get(MODULES, &key).as_deref(), Some(&b"v"[..]));
assert!(store.get(CacheNamespace::new("other", 1), &key).is_none());
assert_eq!(store.len(), 1);
}
#[test]
fn a_tally_counts_and_counters_add() {
let tally = CacheTally::new();
tally.hit();
tally.miss();
tally.miss();
tally.written(10);
let mut counters = tally.snapshot();
assert_eq!(counters, CacheCounters::new(1, 2, 10));
counters.add(CacheCounters::new(1, 0, 5));
assert_eq!(counters, CacheCounters::new(2, 2, 15));
}
}