Skip to main content

skif_core/
cache.rs

1//! The cache store a host gives the linter, the keys skif derives for it and the envelope skif wraps every value in
2//! (ADR 0007).
3//!
4//! A host owns where entries live: it implements [`CacheStore`] over its own storage (a directory, poly's cache, a
5//! map in memory) and hands it to the linter. skif computes every key and writes and verifies every value, so a
6//! store only moves opaque bytes. Nothing here does I/O.
7//!
8//! * Keys are 32-byte blake3 digests built with [`KeyBuilder`] over the cache version, the skif version, the
9//!   namespace and its schema, the host's salt and the inputs the entry depends on, which each namespace names. A
10//!   parse result (`modules`) depends on the file's name, its text and the parse options and on nothing else, so
11//!   that is its key: no path, and identical files share an entry wherever they lie. A namespace whose entries
12//!   depend on where a file lies adds its path relative to a root ([`KeyBuilder::relative_path`]). A key never
13//!   holds a modification time or an absolute path, so worktrees and hook snapshots of one tree share entries.
14//! * Values are sealed with [`seal`] and opened with [`open`]: an envelope of magic, namespace, schema, key echo,
15//!   length and checksum around the payload. A value that does not open exactly is a miss, never a wrong result,
16//!   whatever the store returns. The envelope is integrity, not authentication.
17//! * [`CacheCounters`] counts the lookups and writes of a run per namespace, so a host or a test can tell a warm run
18//!   from a cold one without reading the store.
19
20use 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
27/// The layout of keys and envelopes. Raised when either changes, so entries written by another layout are misses.
28pub const CACHE_VERSION: u32 = 1;
29
30/// The first bytes of every sealed value.
31const MAGIC: [u8; 8] = *b"SKIFCACH";
32
33/// The bytes of a sealed value before the namespace name: magic and cache version.
34const PREFIX: usize = MAGIC.len() + 4;
35
36/// A kind of cache entry: a name and the schema of its payload.
37///
38/// The namespace is a parameter of every store call, so a host can lay entries out and report them per namespace.
39/// The schema is part of every key and envelope: raising it makes every entry written under the old one a miss.
40#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
41pub struct CacheNamespace {
42    /// A short, stable name such as `modules`: lower-case ASCII letters, digits, `.` and `-`, at most 64 bytes.
43    pub name: &'static str,
44    /// The version of the payload's layout.
45    pub schema: u32,
46}
47
48impl CacheNamespace {
49    /// The namespace `name` at `schema`.
50    #[must_use]
51    pub const fn new(name: &'static str, schema: u32) -> Self {
52        Self { name, schema }
53    }
54
55    /// Whether `name` is a namespace name a host can use as a directory or file name as it is.
56    #[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
67/// A store of cache entries a host owns and gives the linter (ADR 0007).
68///
69/// Both methods are called from the parallel steps of a run, so an implementation is `Send + Sync`. A lookup that
70/// fails for any reason returns `None`, a miss; a write that fails is the host's to log and never reaches the run.
71/// Values are opaque: skif seals them before [`put`](Self::put) and verifies them after [`get`](Self::get), so a
72/// store may lose, truncate or mix up entries without changing a result.
73pub trait CacheStore: Send + Sync {
74    /// The value stored under `key` in `namespace`, if any.
75    fn get(&self, namespace: CacheNamespace, key: &[u8; 32]) -> Option<Arc<[u8]>>;
76    /// Stores `value` under `key` in `namespace`.
77    fn put(&self, namespace: CacheNamespace, key: &[u8; 32], value: Arc<[u8]>);
78}
79
80/// The key of an entry: 32 bytes.
81type Key = [u8; 32];
82
83/// The entries of a [`MemoryStore`], by namespace name and key.
84type Entries = BTreeMap<(&'static str, Key), Arc<[u8]>>;
85
86/// A [`CacheStore`] in memory, for tests and for a host that keeps entries only while it runs.
87#[derive(Debug, Default)]
88pub struct MemoryStore {
89    entries: Mutex<Entries>,
90}
91
92impl MemoryStore {
93    /// An empty store.
94    #[must_use]
95    pub fn new() -> Self {
96        Self::default()
97    }
98
99    /// The number of entries in every namespace.
100    #[must_use]
101    pub fn len(&self) -> usize {
102        self.entries.lock().unwrap_or_else(PoisonError::into_inner).len()
103    }
104
105    /// Whether the store holds no entry.
106    #[must_use]
107    pub fn is_empty(&self) -> bool {
108        self.len() == 0
109    }
110
111    /// Every entry, sorted by namespace name and key.
112    #[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/// The store a linter caches through and the digest of its host's salt, as the run hands them to the analyses.
141#[derive(Clone)]
142pub struct CacheHandle {
143    store: Arc<dyn CacheStore>,
144    salt: [u8; 32],
145}
146
147impl CacheHandle {
148    /// `store`, keyed with the digest of `salt`, the host's opaque salt (see [`salt_digest`]).
149    #[must_use]
150    pub fn new(store: Arc<dyn CacheStore>, salt: [u8; 32]) -> Self {
151        Self { store, salt }
152    }
153
154    /// The store.
155    #[must_use]
156    pub fn store(&self) -> &Arc<dyn CacheStore> {
157        &self.store
158    }
159
160    /// The digest of the host's salt, an input of every key.
161    #[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/// The digest of a host's opaque salt: no salt and an empty salt are the same.
174#[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/// The blake3 digest of `content`, the form in which file contents and configuration enter a key.
182#[must_use]
183pub fn content_digest(content: &[u8]) -> [u8; 32] {
184    *blake3::hash(content).as_bytes()
185}
186
187/// Builds the 32-byte key of one cache entry.
188///
189/// Every key covers [`CACHE_VERSION`], the skif version, the namespace with its schema and the host's salt; the
190/// caller adds the inputs the entry depends on. Each field is written with its length first, so two different
191/// splits of the same bytes never give the same key.
192///
193/// ```
194/// use std::path::Path;
195/// use skif_core::cache::{CacheNamespace, KeyBuilder, salt_digest};
196///
197/// let modules = CacheNamespace::new("modules", 1);
198/// let key = |root: &str, file: &str| {
199///     let file = Path::new(file);
200///     KeyBuilder::new(modules, &salt_digest(b"host"))
201///         .relative_path(file.strip_prefix(root).unwrap_or(file))
202///         .content(b"export const a = 1;")
203///         .finish()
204/// };
205/// // The key does not depend on where the tree lives.
206/// assert_eq!(key("/one", "/one/src/a.ts"), key("/two", "/two/src/a.ts"));
207/// ```
208#[derive(Debug, Clone)]
209pub struct KeyBuilder {
210    hasher: blake3::Hasher,
211}
212
213impl KeyBuilder {
214    /// A key in `namespace` under the host salt digest `salt`.
215    #[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    /// Adds a field of raw bytes, such as a flag or an option.
234    #[must_use]
235    pub fn bytes(mut self, field: &[u8]) -> Self {
236        self.write(field);
237        self
238    }
239
240    /// Adds the digest of the configuration the entry depends on (see [`content_digest`]).
241    #[must_use]
242    pub fn config_digest(self, digest: &[u8; 32]) -> Self {
243        self.bytes(digest)
244    }
245
246    /// Adds `content` by its digest.
247    #[must_use]
248    pub fn content(self, content: &[u8]) -> Self {
249        self.bytes(&content_digest(content))
250    }
251
252    /// Adds a path relative to the root the entry belongs to, its components joined with `/` so every platform
253    /// spells it alike. A key must never depend on where a tree lives: an absolute path is written with a marker of
254    /// its own, so such a key is still correct but shared by no other checkout.
255    #[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    /// The key.
287    #[must_use]
288    pub fn finish(&self) -> [u8; 32] {
289        *self.hasher.finalize().as_bytes()
290    }
291}
292
293/// Wraps `payload` in the envelope [`open`] verifies: magic, cache version, namespace name and schema, the key,
294/// the payload's length and blake3 checksum, then the payload.
295///
296/// # Panics
297/// Never for a namespace of [`CacheNamespace::is_valid_name`]; a longer name is cut to 255 bytes in the envelope,
298/// which [`open`] then rejects.
299#[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/// The payload of `value` when it is exactly an envelope [`seal`] wrote for `namespace` and `key`: any other magic,
318/// version, namespace, schema, key, length or checksum, a truncated value or bytes after the payload give `None`.
319#[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/// What a run did with one namespace of the store.
349#[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    /// Lookups answered by a stored entry that opened.
354    pub hits: u64,
355    /// Lookups the store did not answer, or answered with a value that did not open.
356    pub misses: u64,
357    /// Bytes of sealed values handed to the store.
358    pub bytes_written: u64,
359}
360
361impl CacheCounters {
362    /// Counters with these values.
363    #[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    /// Adds `other` to these counters.
373    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/// [`CacheCounters`] that the threads of a run update together.
381#[derive(Debug, Default)]
382pub struct CacheTally {
383    hits: AtomicU64,
384    misses: AtomicU64,
385    bytes_written: AtomicU64,
386}
387
388impl CacheTally {
389    /// A tally at zero.
390    #[must_use]
391    pub fn new() -> Self {
392        Self::default()
393    }
394
395    /// Counts a hit.
396    pub fn hit(&self) {
397        self.hits.fetch_add(1, Ordering::Relaxed);
398    }
399
400    /// Counts a miss.
401    pub fn miss(&self) {
402        self.misses.fetch_add(1, Ordering::Relaxed);
403    }
404
405    /// Counts a hit in place of a miss already counted for the same lookup: the entry arrived between a first
406    /// look and a second, so the lookup was served after all.
407    pub fn hit_after_miss(&self) {
408        self.hit();
409        // Never below zero, whatever the caller counted before.
410        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    /// Counts `bytes` written.
423    pub fn written(&self, bytes: usize) {
424        self.bytes_written.fetch_add(bytes as u64, Ordering::Relaxed);
425    }
426
427    /// The counts so far.
428    #[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        // Length prefixes: the same bytes split differently are different keys.
547        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}