1use std::collections::BTreeMap;
21use std::path::{Component, Path};
22use std::sync::atomic::{AtomicU64, Ordering};
23use std::sync::{Arc, Mutex, PoisonError};
24
25use serde::{Deserialize, Serialize};
26
27pub const CACHE_VERSION: u32 = 1;
29
30const MAGIC: [u8; 8] = *b"SKIFCACH";
32
33const PREFIX: usize = MAGIC.len() + 4;
35
36#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
41pub struct CacheNamespace {
42 pub name: &'static str,
44 pub schema: u32,
46}
47
48impl CacheNamespace {
49 #[must_use]
51 pub const fn new(name: &'static str, schema: u32) -> Self {
52 Self { name, schema }
53 }
54
55 #[must_use]
57 pub fn is_valid_name(name: &str) -> bool {
58 !name.is_empty()
59 && name.len() <= 64
60 && !name.starts_with('.')
61 && name
62 .bytes()
63 .all(|byte| byte.is_ascii_lowercase() || byte.is_ascii_digit() || matches!(byte, b'.' | b'-'))
64 }
65}
66
67pub trait CacheStore: Send + Sync {
74 fn get(&self, namespace: CacheNamespace, key: &[u8; 32]) -> Option<Arc<[u8]>>;
76 fn put(&self, namespace: CacheNamespace, key: &[u8; 32], value: Arc<[u8]>);
78}
79
80type Key = [u8; 32];
82
83type Entries = BTreeMap<(&'static str, Key), Arc<[u8]>>;
85
86#[derive(Debug, Default)]
88pub struct MemoryStore {
89 entries: Mutex<Entries>,
90}
91
92impl MemoryStore {
93 #[must_use]
95 pub fn new() -> Self {
96 Self::default()
97 }
98
99 #[must_use]
101 pub fn len(&self) -> usize {
102 self.entries.lock().unwrap_or_else(PoisonError::into_inner).len()
103 }
104
105 #[must_use]
107 pub fn is_empty(&self) -> bool {
108 self.len() == 0
109 }
110
111 #[must_use]
113 pub fn entries(&self) -> Vec<(&'static str, Key, Arc<[u8]>)> {
114 self.entries
115 .lock()
116 .unwrap_or_else(PoisonError::into_inner)
117 .iter()
118 .map(|((name, key), value)| (*name, *key, Arc::clone(value)))
119 .collect()
120 }
121}
122
123impl CacheStore for MemoryStore {
124 fn get(&self, namespace: CacheNamespace, key: &[u8; 32]) -> Option<Arc<[u8]>> {
125 self.entries
126 .lock()
127 .unwrap_or_else(PoisonError::into_inner)
128 .get(&(namespace.name, *key))
129 .cloned()
130 }
131
132 fn put(&self, namespace: CacheNamespace, key: &[u8; 32], value: Arc<[u8]>) {
133 self.entries
134 .lock()
135 .unwrap_or_else(PoisonError::into_inner)
136 .insert((namespace.name, *key), value);
137 }
138}
139
140#[derive(Clone)]
142pub struct CacheHandle {
143 store: Arc<dyn CacheStore>,
144 salt: [u8; 32],
145}
146
147impl CacheHandle {
148 #[must_use]
150 pub fn new(store: Arc<dyn CacheStore>, salt: [u8; 32]) -> Self {
151 Self { store, salt }
152 }
153
154 #[must_use]
156 pub fn store(&self) -> &Arc<dyn CacheStore> {
157 &self.store
158 }
159
160 #[must_use]
162 pub const fn salt(&self) -> &[u8; 32] {
163 &self.salt
164 }
165}
166
167impl std::fmt::Debug for CacheHandle {
168 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
169 f.debug_struct("CacheHandle").finish_non_exhaustive()
170 }
171}
172
173#[must_use]
175pub fn salt_digest(salt: &[u8]) -> [u8; 32] {
176 let mut hasher = blake3::Hasher::new_derive_key("skif cache salt v1");
177 hasher.update(salt);
178 *hasher.finalize().as_bytes()
179}
180
181#[must_use]
183pub fn content_digest(content: &[u8]) -> [u8; 32] {
184 *blake3::hash(content).as_bytes()
185}
186
187#[derive(Debug, Clone)]
209pub struct KeyBuilder {
210 hasher: blake3::Hasher,
211}
212
213impl KeyBuilder {
214 #[must_use]
216 pub fn new(namespace: CacheNamespace, salt: &[u8; 32]) -> Self {
217 let mut builder = Self {
218 hasher: blake3::Hasher::new_derive_key("skif cache key v1"),
219 };
220 builder.write(&CACHE_VERSION.to_le_bytes());
221 builder.write(env!("CARGO_PKG_VERSION").as_bytes());
222 builder.write(namespace.name.as_bytes());
223 builder.write(&namespace.schema.to_le_bytes());
224 builder.write(salt);
225 builder
226 }
227
228 fn write(&mut self, bytes: &[u8]) {
229 self.hasher.update(&(bytes.len() as u64).to_le_bytes());
230 self.hasher.update(bytes);
231 }
232
233 #[must_use]
235 pub fn bytes(mut self, field: &[u8]) -> Self {
236 self.write(field);
237 self
238 }
239
240 #[must_use]
242 pub fn config_digest(self, digest: &[u8; 32]) -> Self {
243 self.bytes(digest)
244 }
245
246 #[must_use]
248 pub fn content(self, content: &[u8]) -> Self {
249 self.bytes(&content_digest(content))
250 }
251
252 #[must_use]
256 pub fn relative_path(mut self, path: &Path) -> Self {
257 let mut spelled = Vec::new();
258 let mut absolute = false;
259 for component in path.components() {
260 match component {
261 Component::Normal(part) => {
262 if !spelled.is_empty() {
263 spelled.push(b'/');
264 }
265 spelled.extend_from_slice(part.as_encoded_bytes());
266 }
267 Component::ParentDir => {
268 if !spelled.is_empty() {
269 spelled.push(b'/');
270 }
271 spelled.extend_from_slice(b"..");
272 }
273 Component::CurDir => {}
274 Component::RootDir | Component::Prefix(_) => absolute = true,
275 }
276 }
277 self.write(&[u8::from(absolute)]);
278 if absolute {
279 self.write(path.as_os_str().as_encoded_bytes());
280 } else {
281 self.write(&spelled);
282 }
283 self
284 }
285
286 #[must_use]
288 pub fn finish(&self) -> [u8; 32] {
289 *self.hasher.finalize().as_bytes()
290 }
291}
292
293#[must_use]
300pub fn seal(namespace: CacheNamespace, key: &[u8; 32], payload: &[u8]) -> Arc<[u8]> {
301 let name = namespace.name.as_bytes();
302 let name = &name[..name.len().min(usize::from(u8::MAX))];
303 let mut value = Vec::with_capacity(PREFIX + 1 + name.len() + 4 + 32 + 8 + 32 + payload.len());
304 value.extend_from_slice(&MAGIC);
305 value.extend_from_slice(&CACHE_VERSION.to_le_bytes());
306 #[allow(clippy::cast_possible_truncation)]
307 value.push(name.len() as u8);
308 value.extend_from_slice(name);
309 value.extend_from_slice(&namespace.schema.to_le_bytes());
310 value.extend_from_slice(key);
311 value.extend_from_slice(&(payload.len() as u64).to_le_bytes());
312 value.extend_from_slice(&content_digest(payload));
313 value.extend_from_slice(payload);
314 Arc::from(value)
315}
316
317#[must_use]
320pub fn open<'a>(namespace: CacheNamespace, key: &[u8; 32], value: &'a [u8]) -> Option<&'a [u8]> {
321 let mut rest = value;
322 let mut take = |length: usize| -> Option<&'a [u8]> {
323 if rest.len() < length {
324 return None;
325 }
326 let (head, tail) = rest.split_at(length);
327 rest = tail;
328 Some(head)
329 };
330 if take(MAGIC.len())? != MAGIC || take(4)? != CACHE_VERSION.to_le_bytes() {
331 return None;
332 }
333 let length = usize::from(*take(1)?.first()?);
334 if take(length)? != namespace.name.as_bytes() || take(4)? != namespace.schema.to_le_bytes() || take(32)? != key {
335 return None;
336 }
337 let mut size = [0; 8];
338 size.copy_from_slice(take(8)?);
339 let size = usize::try_from(u64::from_le_bytes(size)).ok()?;
340 let checksum = take(32)?;
341 let payload = take(size)?;
342 if !rest.is_empty() || checksum != content_digest(payload) {
343 return None;
344 }
345 Some(payload)
346}
347
348#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
350#[serde(rename_all = "kebab-case")]
351#[non_exhaustive]
352pub struct CacheCounters {
353 pub hits: u64,
355 pub misses: u64,
357 pub bytes_written: u64,
359}
360
361impl CacheCounters {
362 #[must_use]
364 pub const fn new(hits: u64, misses: u64, bytes_written: u64) -> Self {
365 Self {
366 hits,
367 misses,
368 bytes_written,
369 }
370 }
371
372 pub const fn add(&mut self, other: Self) {
374 self.hits += other.hits;
375 self.misses += other.misses;
376 self.bytes_written += other.bytes_written;
377 }
378}
379
380#[derive(Debug, Default)]
382pub struct CacheTally {
383 hits: AtomicU64,
384 misses: AtomicU64,
385 bytes_written: AtomicU64,
386}
387
388impl CacheTally {
389 #[must_use]
391 pub fn new() -> Self {
392 Self::default()
393 }
394
395 pub fn hit(&self) {
397 self.hits.fetch_add(1, Ordering::Relaxed);
398 }
399
400 pub fn miss(&self) {
402 self.misses.fetch_add(1, Ordering::Relaxed);
403 }
404
405 pub fn hit_after_miss(&self) {
408 self.hit();
409 let mut misses = self.misses.load(Ordering::Relaxed);
411 while let Some(fewer) = misses.checked_sub(1) {
412 match self
413 .misses
414 .compare_exchange_weak(misses, fewer, Ordering::Relaxed, Ordering::Relaxed)
415 {
416 Ok(_) => break,
417 Err(current) => misses = current,
418 }
419 }
420 }
421
422 pub fn written(&self, bytes: usize) {
424 self.bytes_written.fetch_add(bytes as u64, Ordering::Relaxed);
425 }
426
427 #[must_use]
429 pub fn snapshot(&self) -> CacheCounters {
430 CacheCounters {
431 hits: self.hits.load(Ordering::Relaxed),
432 misses: self.misses.load(Ordering::Relaxed),
433 bytes_written: self.bytes_written.load(Ordering::Relaxed),
434 }
435 }
436}
437
438const _: () = {
439 fn assert_send_sync<T: Send + Sync>() {}
440 let _ = assert_send_sync::<MemoryStore>;
441 let _ = assert_send_sync::<CacheHandle>;
442 let _ = assert_send_sync::<CacheTally>;
443 let _ = assert_send_sync::<Arc<dyn CacheStore>>;
444};
445
446#[cfg(test)]
447#[allow(clippy::unwrap_used, clippy::expect_used)]
448mod tests {
449 use super::*;
450
451 const MODULES: CacheNamespace = CacheNamespace::new("modules", 3);
452
453 fn key(text: &str) -> [u8; 32] {
454 KeyBuilder::new(MODULES, &salt_digest(b""))
455 .content(text.as_bytes())
456 .finish()
457 }
458
459 #[test]
460 fn a_sealed_value_opens_to_its_payload() {
461 let key = key("a");
462 let value = seal(MODULES, &key, b"payload");
463 assert_eq!(open(MODULES, &key, &value), Some(&b"payload"[..]));
464 let empty = seal(MODULES, &key, b"");
465 assert_eq!(open(MODULES, &key, &empty), Some(&b""[..]));
466 }
467
468 #[test]
469 fn a_value_that_is_not_exactly_the_envelope_does_not_open() {
470 let key = key("a");
471 let value = seal(MODULES, &key, b"payload");
472 assert!(open(MODULES, &self::key("b"), &value).is_none(), "another key");
473 assert!(
474 open(CacheNamespace::new("modules", 4), &key, &value).is_none(),
475 "another schema"
476 );
477 assert!(
478 open(CacheNamespace::new("other", 3), &key, &value).is_none(),
479 "another namespace"
480 );
481 assert!(open(MODULES, &key, &value[..value.len() - 1]).is_none(), "truncated");
482 assert!(open(MODULES, &key, &[]).is_none(), "empty");
483 let mut longer = value.to_vec();
484 longer.push(0);
485 assert!(open(MODULES, &key, &longer).is_none(), "trailing bytes");
486 for at in 0..value.len() {
487 let mut flipped = value.to_vec();
488 flipped[at] ^= 0x01;
489 assert!(open(MODULES, &key, &flipped).is_none(), "flipped byte {at}");
490 }
491 }
492
493 #[test]
494 fn random_bytes_never_open() {
495 let key = key("a");
496 let mut state: u64 = 0x9e37_79b9_7f4a_7c15;
497 for length in 0..512 {
498 let bytes: Vec<u8> = (0..length)
499 .map(|_| {
500 state ^= state << 13;
501 state ^= state >> 7;
502 state ^= state << 17;
503 state.to_le_bytes()[0]
504 })
505 .collect();
506 assert!(open(MODULES, &key, &bytes).is_none());
507 }
508 }
509
510 #[test]
511 fn the_key_changes_with_each_input() {
512 let salt = salt_digest(b"host");
513 let base = KeyBuilder::new(MODULES, &salt)
514 .relative_path(Path::new("src/a.ts"))
515 .content(b"x")
516 .finish();
517 let others = [
518 KeyBuilder::new(CacheNamespace::new("modules", 4), &salt)
519 .relative_path(Path::new("src/a.ts"))
520 .content(b"x")
521 .finish(),
522 KeyBuilder::new(CacheNamespace::new("other", 3), &salt)
523 .relative_path(Path::new("src/a.ts"))
524 .content(b"x")
525 .finish(),
526 KeyBuilder::new(MODULES, &salt_digest(b"other host"))
527 .relative_path(Path::new("src/a.ts"))
528 .content(b"x")
529 .finish(),
530 KeyBuilder::new(MODULES, &salt)
531 .relative_path(Path::new("src/b.ts"))
532 .content(b"x")
533 .finish(),
534 KeyBuilder::new(MODULES, &salt)
535 .relative_path(Path::new("src/a.ts"))
536 .content(b"y")
537 .finish(),
538 KeyBuilder::new(MODULES, &salt)
539 .relative_path(Path::new("/src/a.ts"))
540 .content(b"x")
541 .finish(),
542 ];
543 for other in others {
544 assert_ne!(base, other);
545 }
546 assert_ne!(
548 KeyBuilder::new(MODULES, &salt).bytes(b"ab").bytes(b"c").finish(),
549 KeyBuilder::new(MODULES, &salt).bytes(b"a").bytes(b"bc").finish()
550 );
551 }
552
553 #[test]
554 fn a_relative_path_is_spelled_alike_on_every_platform() {
555 let salt = salt_digest(b"");
556 let key = |path: &str| KeyBuilder::new(MODULES, &salt).relative_path(Path::new(path)).finish();
557 assert_eq!(key("src/a.ts"), key("./src/a.ts"));
558 assert_eq!(key("src/a.ts"), key("src//a.ts"));
559 assert_ne!(key("../a.ts"), key("a.ts"));
560 }
561
562 #[test]
563 fn no_salt_and_an_empty_salt_are_the_same() {
564 assert_eq!(salt_digest(b""), salt_digest(&[]));
565 assert_ne!(salt_digest(b""), salt_digest(b"x"));
566 }
567
568 #[test]
569 fn namespace_names_are_safe_as_file_names() {
570 for good in ["modules", "other.facts", "a-1"] {
571 assert!(CacheNamespace::is_valid_name(good), "{good}");
572 }
573 for bad in ["", ".hidden", "Upper", "a/b", "a\\b", "..", &"x".repeat(65)] {
574 assert!(!CacheNamespace::is_valid_name(bad), "{bad}");
575 }
576 }
577
578 #[test]
579 fn a_memory_store_returns_what_was_put_per_namespace() {
580 let store = MemoryStore::new();
581 let key = key("a");
582 assert!(store.get(MODULES, &key).is_none());
583 store.put(MODULES, &key, Arc::from(&b"v"[..]));
584 assert_eq!(store.get(MODULES, &key).as_deref(), Some(&b"v"[..]));
585 assert!(store.get(CacheNamespace::new("other", 1), &key).is_none());
586 assert_eq!(store.len(), 1);
587 }
588
589 #[test]
590 fn a_tally_counts_and_counters_add() {
591 let tally = CacheTally::new();
592 tally.hit();
593 tally.miss();
594 tally.miss();
595 tally.written(10);
596 let mut counters = tally.snapshot();
597 assert_eq!(counters, CacheCounters::new(1, 2, 10));
598 counters.add(CacheCounters::new(1, 0, 5));
599 assert_eq!(counters, CacheCounters::new(2, 2, 15));
600 }
601}