Skip to main content

skif_cache/
lib.rs

1//! skif's disk cache store (ADR 0007): a [`CacheStore`] over one cache location that holds a store per base.
2//!
3//! This crate is an implementation detail of `skif`, re-exported as `skif::cache` behind the `cache-disk` feature;
4//! it carries no stability promise of its own. It is the one skif library crate that reads and writes files outside
5//! the `FileSystem` trait, and only below the cache location it is given. It reads no environment: the host passes
6//! the location and, for [`default_location`], the platform's per-user cache directory.
7//!
8//! # Layout
9//!
10//! ```text
11//! <location>/
12//!   CACHEDIR.TAG, .gitignore      written when skif creates the directory
13//!   <base key>/                   one store per base (32 hex digits, see `base_key`)
14//!     base                        the base it belongs to, for `skif cache stats`
15//!     .lock                       the try-lock of a write
16//!     <namespace>.bin             one file per namespace (`modules.bin`)
17//!     <file>.<random>.tmp         a write in progress; one a killed writer left goes with the next write
18//! ```
19//!
20//! A namespace file is:
21//!
22//! ```text
23//! magic    8 bytes   "SKIFSTOR"
24//! format   u32 LE    2
25//! name     u8 length, then the namespace name
26//! schema   u32 LE    the namespace schema it was written under
27//! count    u32 LE
28//! records  count times, sorted by key: key [u8; 32], length u32 LE, value (skif's sealed envelope)
29//! ```
30//!
31//! A file that does not match this layout in every byte, or was written under another schema, is empty; skif
32//! verifies every value it reads, so a damaged record is a miss.
33//!
34//! # Policy
35//!
36//! * A base inside a git repository is identified by the git directory its worktrees share and its path in the
37//!   repository, so the worktrees of one repository share a store and two repositories never do; a base outside git
38//!   is identified by its absolute path.
39//! * [`DiskStore::finish_run`] writes, per namespace, exactly the entries the run used, so a run never prunes
40//!   a namespace it did not ask for, and a namespace the run used in full is not rewritten. Runs that lint different
41//!   sets of files in turn (`skif` and `skif --production`) therefore each drop what only the other used.
42//!   [`DiskStore::finish_failed_run`], for a run that did not complete, adds what the run computed and drops nothing.
43//! * A write takes a try-lock on the store and is skipped when another process holds it; files are written to a
44//!   new temporary file with a random name, never through a link, and renamed, so a reader sees the old file or the
45//!   new one. Temporary files a killed writer left are removed under the lock before the next write.
46//! * A namespace file larger than the cap is not read: no write leaves one, so it is not a file of this store.
47//! * After a write, a location over its cap drops the stores of other bases, least recently written first, unless
48//!   the host turned that off ([`DiskStoreOptions::with_evict_others`]); a store that alone exceeds the cap keeps
49//!   `modules` entries first, then the other namespaces, in key order, up to it.
50//! * A directory the store creates gets a `CACHEDIR.TAG` and a `.gitignore` of `*`, written only where no such file
51//!   exists, and it never creates a directory named `node_modules`.
52
53#![warn(missing_docs)]
54
55use std::collections::{BTreeMap, BTreeSet};
56use std::fs::{self, File, TryLockError};
57use std::hash::{BuildHasher as _, Hasher as _};
58use std::io::{self, Read as _, Write as _};
59use std::ops::Range;
60use std::path::{Component, Path, PathBuf};
61use std::sync::{Arc, Mutex, PoisonError, RwLock};
62use std::time::SystemTime;
63
64use skif_core::cache::content_digest;
65use skif_core::{CacheNamespace, CacheStore};
66
67/// The first bytes of a namespace file.
68const MAGIC: [u8; 8] = *b"SKIFSTOR";
69/// The layout of a namespace file: 1 was the single `modules.bin` of skif 0.8, 2 is per namespace with sealed values.
70const FORMAT: u32 = 2;
71/// The extension of a namespace file.
72const EXTENSION: &str = "bin";
73/// The name of the try-lock file of a store.
74const LOCK_FILE: &str = ".lock";
75/// The name of the file that records which base a store belongs to.
76const BASE_FILE: &str = "base";
77/// The name of the cache directory tag written into a directory skif creates.
78const TAG_FILE: &str = "CACHEDIR.TAG";
79/// The name of the ignore file written into a directory skif creates, and its content.
80const IGNORE_FILE: &str = ".gitignore";
81const IGNORE_ALL: &str = "*\n";
82/// The suffix of the temporary file of a write.
83const TEMPORARY_SUFFIX: &str = ".tmp";
84/// How many random names a write tries before it gives up.
85const TEMPORARY_TRIES: usize = 8;
86/// The namespace whose entries a store over the cap keeps first.
87const FIRST_NAMESPACE: &str = "modules";
88
89/// The cap of a location when the host sets none: 512 MiB.
90pub const DEFAULT_MAX_SIZE: u64 = 512 * 1024 * 1024;
91
92/// The contents of a `CACHEDIR.TAG` (<https://bford.info/cachedir/>).
93const CACHEDIR_TAG: &str = "Signature: 8a477f597d28d172789f06886806bc55\n\
94                            # This file is a cache directory tag created by skif.\n\
95                            # For information about cache directory tags, see https://bford.info/cachedir/\n";
96
97/// How a [`DiskStore`] behaves.
98#[derive(Debug, Clone, Copy, PartialEq, Eq)]
99#[non_exhaustive]
100pub struct DiskStoreOptions {
101    /// The most bytes the whole location may hold after a write.
102    pub max_size: u64,
103    /// Whether [`DiskStore::finish_run`] writes; a read-only store still serves the entries a run puts, until the
104    /// run ends.
105    pub write: bool,
106    /// Whether a write that leaves the location over its cap drops the stores of other bases. A host turns it off
107    /// when the cap comes from a file of the project, so a checked-in cap only ever shrinks the project's own store.
108    pub evict_others: bool,
109}
110
111impl Default for DiskStoreOptions {
112    fn default() -> Self {
113        Self {
114            max_size: DEFAULT_MAX_SIZE,
115            write: true,
116            evict_others: true,
117        }
118    }
119}
120
121impl DiskStoreOptions {
122    /// Caps the location at `max_size` bytes.
123    #[must_use]
124    pub const fn with_max_size(mut self, max_size: u64) -> Self {
125        self.max_size = max_size;
126        self
127    }
128
129    /// Whether [`DiskStore::finish_run`] writes.
130    #[must_use]
131    pub const fn with_write(mut self, write: bool) -> Self {
132        self.write = write;
133        self
134    }
135
136    /// Whether a write that leaves the location over its cap drops the stores of other bases.
137    #[must_use]
138    pub const fn with_evict_others(mut self, evict_others: bool) -> Self {
139        self.evict_others = evict_others;
140        self
141    }
142}
143
144/// A store's write failed.
145#[derive(Debug, thiserror::Error)]
146#[non_exhaustive]
147pub enum StoreError {
148    /// A file or directory of the store could not be created, written or renamed.
149    #[error("cannot write {path}: {source}")]
150    Io {
151        /// The file or directory.
152        path: PathBuf,
153        /// What went wrong.
154        #[source]
155        source: io::Error,
156    },
157    /// The location is below a `node_modules` directory that does not exist, which skif never creates.
158    #[error("{path} does not exist and skif does not create node_modules directories")]
159    NodeModules {
160        /// The missing `node_modules` directory.
161        path: PathBuf,
162    },
163    /// The location is the empty path, which would put the store in the current directory.
164    #[error("the cache location is empty")]
165    EmptyLocation,
166}
167
168impl StoreError {
169    fn io(path: &Path, source: io::Error) -> Self {
170        Self::Io {
171            path: path.to_path_buf(),
172            source,
173        }
174    }
175}
176
177/// What [`DiskStore::finish_run`] did.
178#[derive(Debug, Clone, Copy, PartialEq, Eq)]
179#[non_exhaustive]
180pub enum Finish {
181    /// Nothing to write: the run used no entry, or exactly the entries already stored.
182    Unchanged,
183    /// The namespaces the run used were written.
184    Written,
185    /// Another process held the store's lock, so this run's write was skipped.
186    Contended,
187    /// The store is read-only.
188    ReadOnly,
189}
190
191/// A key and its sealed value.
192type Record = ([u8; 32], Arc<[u8]>);
193
194/// The records of one namespace a run used, waiting to be written.
195struct Pending {
196    name: &'static str,
197    schema: u32,
198    records: Vec<Record>,
199}
200
201/// The records of one namespace file as loaded: its bytes and where each value lies in them.
202#[derive(Default)]
203struct Stored {
204    bytes: Vec<u8>,
205    index: BTreeMap<[u8; 32], Range<usize>>,
206}
207
208/// One namespace of a store while runs use it.
209struct Namespace {
210    schema: u32,
211    stored: RwLock<Stored>,
212    /// The values this run put.
213    fresh: Mutex<BTreeMap<[u8; 32], Arc<[u8]>>>,
214    /// The keys this run read or wrote: what the next write keeps.
215    used: Mutex<BTreeSet<[u8; 32]>>,
216}
217
218/// skif's disk cache store: the store of one base in a cache location (see the [crate] documentation).
219///
220/// Namespace files are read when a run first asks for their namespace and kept in memory;
221/// [`finish_run`](Self::finish_run) writes what the run used and prunes the memory to it, so a long-lived host (watch
222/// mode) reads the files once and writes them after each run.
223pub struct DiskStore {
224    location: PathBuf,
225    dir: PathBuf,
226    base: String,
227    options: DiskStoreOptions,
228    namespaces: Mutex<BTreeMap<&'static str, Arc<Namespace>>>,
229    /// Why files were ignored, for a host that shows them under `--debug`.
230    notes: Mutex<Vec<String>>,
231}
232
233impl std::fmt::Debug for DiskStore {
234    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
235        f.debug_struct("DiskStore")
236            .field("dir", &self.dir)
237            .field("options", &self.options)
238            .finish_non_exhaustive()
239    }
240}
241
242impl DiskStore {
243    /// The store of `base`, an absolute directory, in the cache `location`. Opening reads nothing and never fails:
244    /// files are read when a run first asks for their namespace, and a missing or unreadable file is empty.
245    #[must_use]
246    pub fn open(location: &Path, base: &Path, options: DiskStoreOptions) -> Self {
247        let base = base_identity(base);
248        let dir = location.join(base_dir_name(&base));
249        Self {
250            location: location.to_path_buf(),
251            dir,
252            base,
253            options,
254            namespaces: Mutex::new(BTreeMap::new()),
255            notes: Mutex::new(Vec::new()),
256        }
257    }
258
259    /// The cache location.
260    #[must_use]
261    pub fn location(&self) -> &Path {
262        &self.location
263    }
264
265    /// The directory of this base's store inside the location.
266    #[must_use]
267    pub fn dir(&self) -> &Path {
268        &self.dir
269    }
270
271    /// How the store behaves.
272    #[must_use]
273    pub const fn options(&self) -> DiskStoreOptions {
274        self.options
275    }
276
277    /// Takes the reasons files were ignored since the last call, for a host that shows them under `--debug`.
278    #[must_use]
279    pub fn take_notes(&self) -> Vec<String> {
280        std::mem::take(&mut *self.notes.lock().unwrap_or_else(PoisonError::into_inner))
281    }
282
283    fn note(&self, note: String) {
284        self.notes.lock().unwrap_or_else(PoisonError::into_inner).push(note);
285    }
286
287    /// The namespace `namespace` of this store, read from its file the first time it is asked for. A namespace asked
288    /// for under another schema than before starts empty.
289    fn namespace(&self, namespace: CacheNamespace) -> Option<Arc<Namespace>> {
290        if !CacheNamespace::is_valid_name(namespace.name) {
291            return None;
292        }
293        let mut namespaces = self.namespaces.lock().unwrap_or_else(PoisonError::into_inner);
294        if let Some(loaded) = namespaces.get(namespace.name)
295            && loaded.schema == namespace.schema
296        {
297            return Some(Arc::clone(loaded));
298        }
299        let file = self.dir.join(namespace_file(namespace.name));
300        // No write leaves a namespace file over the cap, so a larger one is not read into memory.
301        let limit = self.options.max_size.saturating_add(header_size(namespace.name));
302        let stored = match read_at_most(&file, limit) {
303            Ok(Some(bytes)) => decode(bytes, namespace).unwrap_or_else(|reason| {
304                self.note(format!("ignoring the cache file {}: {reason}", file.display()));
305                Stored::default()
306            }),
307            Ok(None) => {
308                self.note(format!(
309                    "ignoring the cache file {}: larger than the cap of {} bytes",
310                    file.display(),
311                    self.options.max_size
312                ));
313                Stored::default()
314            }
315            Err(error) if error.kind() == io::ErrorKind::NotFound => Stored::default(),
316            Err(error) => {
317                self.note(format!("ignoring the cache file {}: {error}", file.display()));
318                Stored::default()
319            }
320        };
321        let loaded = Arc::new(Namespace {
322            schema: namespace.schema,
323            stored: RwLock::new(stored),
324            fresh: Mutex::new(BTreeMap::new()),
325            used: Mutex::new(BTreeSet::new()),
326        });
327        namespaces.insert(namespace.name, Arc::clone(&loaded));
328        Some(loaded)
329    }
330
331    /// Writes, per namespace, exactly the entries the run used, unless they are the entries already stored, then
332    /// keeps the location under its cap, and prunes the memory of every namespace to what the run used.
333    ///
334    /// # Errors
335    /// [`StoreError`] when a directory or file could not be created, written or renamed, or the location is below a
336    /// missing `node_modules`. The memory is pruned all the same; the run's report never depends on it.
337    pub fn finish_run(&self) -> Result<Finish, StoreError> {
338        self.finish(true)
339    }
340
341    /// Ends a run that did not complete (it failed, or linted only a part of what it was asked to): writes, per
342    /// namespace, the entries the run put next to the ones already stored, and drops none, since what such a run did
343    /// not use says nothing about what the next one needs.
344    ///
345    /// # Errors
346    /// As [`finish_run`](Self::finish_run).
347    pub fn finish_failed_run(&self) -> Result<Finish, StoreError> {
348        self.finish(false)
349    }
350
351    /// Ends a run; `prune` drops the entries it did not use.
352    fn finish(&self, prune: bool) -> Result<Finish, StoreError> {
353        let namespaces: Vec<(&'static str, Arc<Namespace>)> = self
354            .namespaces
355            .lock()
356            .unwrap_or_else(PoisonError::into_inner)
357            .iter()
358            .map(|(name, namespace)| (*name, Arc::clone(namespace)))
359            .collect();
360        let mut pending: Vec<Pending> = Vec::new();
361        for &(name, ref namespace) in &namespaces {
362            let used = std::mem::take(&mut *namespace.used.lock().unwrap_or_else(PoisonError::into_inner));
363            let fresh = std::mem::take(&mut *namespace.fresh.lock().unwrap_or_else(PoisonError::into_inner));
364            if used.is_empty() {
365                continue;
366            }
367            let mut stored = namespace.stored.write().unwrap_or_else(PoisonError::into_inner);
368            if fresh.is_empty() && (!prune || used.iter().eq(stored.index.keys())) {
369                continue;
370            }
371            let kept: BTreeSet<[u8; 32]> = if prune {
372                used
373            } else {
374                stored.index.keys().chain(fresh.keys()).copied().collect()
375            };
376            let records: Vec<Record> = kept
377                .iter()
378                .filter_map(|key| {
379                    let value = match fresh.get(key) {
380                        Some(value) => Arc::clone(value),
381                        None => Arc::from(&stored.bytes[stored.index.get(key)?.clone()]),
382                    };
383                    Some((*key, value))
384                })
385                .collect();
386            *stored = encode(
387                name,
388                namespace.schema,
389                records.iter().map(|(key, value)| (key, &value[..])),
390            );
391            drop(stored);
392            pending.push(Pending {
393                name,
394                schema: namespace.schema,
395                records,
396            });
397        }
398        if pending.is_empty() {
399            return Ok(Finish::Unchanged);
400        }
401        if !self.options.write {
402            return Ok(Finish::ReadOnly);
403        }
404        self.write(pending)
405    }
406
407    /// Writes the namespace files of `pending` under the store's lock, then keeps the location under its cap.
408    fn write(&self, mut pending: Vec<Pending>) -> Result<Finish, StoreError> {
409        create_tagged(&self.location)?;
410        create_tagged(&self.dir)?;
411        let Some(_lock) = try_lock(&self.dir)? else {
412            return Ok(Finish::Contended);
413        };
414        // The lock is held, so a temporary file here belongs to a writer that was killed.
415        remove_temporaries(&self.dir);
416        let base_file = self.dir.join(BASE_FILE);
417        if fs::read_to_string(&base_file).ok().as_deref() != Some(self.base.as_str()) {
418            write_atomically(&base_file, self.base.as_bytes())?;
419        }
420        // A store that alone exceeds the cap keeps `modules` first, then the other namespaces in name order.
421        pending.sort_by_key(|pending| (pending.name != FIRST_NAMESPACE, pending.name));
422        let others: u64 = self
423            .namespace_files()
424            .iter()
425            .filter(|(name, _)| !pending.iter().any(|pending| pending.name == name))
426            .map(|(_, size)| size)
427            .sum();
428        let mut budget = self.options.max_size.saturating_sub(others);
429        for Pending { name, schema, records } in &pending {
430            let mut kept = Vec::new();
431            let mut size = header_size(name);
432            for (key, value) in records {
433                let record = 32 + 4 + value.len() as u64;
434                if size + record > budget {
435                    break;
436                }
437                size += record;
438                kept.push((key, &value[..]));
439            }
440            budget = budget.saturating_sub(size);
441            let encoded = encode(name, *schema, kept.into_iter());
442            write_atomically(&self.dir.join(namespace_file(name)), &encoded.bytes)?;
443        }
444        if self.options.evict_others {
445            self.enforce_cap();
446        }
447        Ok(Finish::Written)
448    }
449
450    /// The namespace files of this store and their sizes.
451    fn namespace_files(&self) -> Vec<(String, u64)> {
452        let Ok(entries) = fs::read_dir(&self.dir) else {
453            return Vec::new();
454        };
455        entries
456            .filter_map(Result::ok)
457            .filter_map(|entry| {
458                let path = entry.path();
459                let name = path.file_stem()?.to_str()?.to_owned();
460                (path.extension()? == EXTENSION).then_some(())?;
461                Some((name, entry.metadata().ok()?.len()))
462            })
463            .collect()
464    }
465
466    /// Drops the stores of other bases, least recently written first, while the location is over its cap. A store
467    /// whose lock another process holds is kept.
468    fn enforce_cap(&self) {
469        let Ok(stores) = list_stores(&self.location) else {
470            return;
471        };
472        let mut total: u64 = stores.iter().map(|store| store.bytes).sum();
473        let mut others: Vec<&StoreDir> = stores
474            .iter()
475            .filter(|store| store.readable && store.dir != self.dir)
476            .collect();
477        others.sort_by_key(|store| (store.modified, store.dir.clone()));
478        for store in others {
479            if total <= self.options.max_size {
480                break;
481            }
482            let Ok(Some(lock)) = try_lock(&store.dir) else {
483                continue;
484            };
485            drop(lock);
486            if remove_store(&store.dir).is_ok() {
487                total = total.saturating_sub(store.bytes);
488            }
489        }
490    }
491}
492
493impl CacheStore for DiskStore {
494    fn get(&self, namespace: CacheNamespace, key: &[u8; 32]) -> Option<Arc<[u8]>> {
495        let loaded = self.namespace(namespace)?;
496        let fresh = loaded
497            .fresh
498            .lock()
499            .unwrap_or_else(PoisonError::into_inner)
500            .get(key)
501            .cloned();
502        let value = if let Some(value) = fresh {
503            value
504        } else {
505            let stored = loaded.stored.read().unwrap_or_else(PoisonError::into_inner);
506            let range = stored.index.get(key)?.clone();
507            Arc::from(&stored.bytes[range])
508        };
509        loaded.used.lock().unwrap_or_else(PoisonError::into_inner).insert(*key);
510        Some(value)
511    }
512
513    fn put(&self, namespace: CacheNamespace, key: &[u8; 32], value: Arc<[u8]>) {
514        let Some(loaded) = self.namespace(namespace) else {
515            return;
516        };
517        loaded
518            .fresh
519            .lock()
520            .unwrap_or_else(PoisonError::into_inner)
521            .insert(*key, value);
522        loaded.used.lock().unwrap_or_else(PoisonError::into_inner).insert(*key);
523    }
524}
525
526/// The base a store belongs to, as its key is made: `git:`, the git directory shared by the worktrees of the
527/// repository holding the base, and the base relative to the top level of its checkout, so worktrees of one
528/// repository share a key and two repositories never do; else `path:` and the absolute base.
529fn base_identity(base: &Path) -> String {
530    let Some(top) = base.ancestors().find(|dir| dir.join(".git").exists()) else {
531        return format!("path:{}", base.display());
532    };
533    let parts: Vec<String> = base.strip_prefix(top).map_or_default(|relative| {
534        relative
535            .components()
536            .filter_map(|component| match component {
537                Component::Normal(part) => Some(part.to_string_lossy().into_owned()),
538                _ => None,
539            })
540            .collect()
541    });
542    format!("git:{}:{}", common_git_dir(top).display(), parts.join("/"))
543}
544
545/// The git directory the checkout at `top` shares with the other worktrees of its repository, as the file system
546/// resolves it: `.git` itself in the main checkout; in a linked worktree, where `.git` is a file naming the
547/// worktree's own git directory, the directory that one's `commondir` names. A submodule's git directory has no
548/// `commondir`, so a submodule is a repository of its own.
549fn common_git_dir(top: &Path) -> PathBuf {
550    let dot_git = top.join(".git");
551    let git_dir = if dot_git.is_dir() {
552        dot_git
553    } else {
554        fs::read_to_string(&dot_git)
555            .ok()
556            .and_then(|text| {
557                let named = text.lines().next()?.strip_prefix("gitdir:")?.trim();
558                Some(top.join(named))
559            })
560            .unwrap_or(dot_git)
561    };
562    let common = fs::read_to_string(git_dir.join("commondir"))
563        .map_or_else(|_| git_dir.clone(), |named| git_dir.join(named.trim()));
564    fs::canonicalize(&common).unwrap_or(common)
565}
566
567/// The directory name of the store of `base`: 32 hex digits of the digest of [`base_identity`].
568fn base_dir_name(identity: &str) -> String {
569    use std::fmt::Write as _;
570    let mut name = String::with_capacity(32);
571    for byte in &content_digest(identity.as_bytes())[..16] {
572        // Writing to a `String` cannot fail.
573        let _ = write!(name, "{byte:02x}");
574    }
575    name
576}
577
578/// The key of the store of `base` in a location, as [`DiskStore::open`] names its directory.
579#[must_use]
580pub fn base_key(base: &Path) -> String {
581    base_dir_name(&base_identity(base))
582}
583
584/// The file of namespace `name` in a store.
585fn namespace_file(name: &str) -> String {
586    format!("{name}.{EXTENSION}")
587}
588
589/// The cache location a host uses when the user named none, given the base of the run and the platform's per-user
590/// cache directory: `<base>/node_modules/.cache/skif` when `node_modules` exists (skif never creates it), else
591/// `<user_cache_dir>/skif`, else `None`, for a cache in memory for the run.
592#[must_use]
593pub fn default_location(base: &Path, user_cache_dir: Option<&Path>) -> Option<PathBuf> {
594    let node_modules = base.join("node_modules");
595    if node_modules.is_dir() {
596        return Some(node_modules.join(".cache").join("skif"));
597    }
598    user_cache_dir.map(|dir| dir.join("skif"))
599}
600
601/// The size of a namespace file's header.
602fn header_size(name: &str) -> u64 {
603    (MAGIC.len() + 4 + 1 + name.len().min(usize::from(u8::MAX)) + 4 + 4) as u64
604}
605
606/// The namespace file holding `records`, which come sorted by key: its bytes and the index [`decode`] would build.
607fn encode<'a>(name: &str, schema: u32, records: impl Iterator<Item = (&'a [u8; 32], &'a [u8])>) -> Stored {
608    let name = &name.as_bytes()[..name.len().min(usize::from(u8::MAX))];
609    let mut bytes = Vec::new();
610    bytes.extend_from_slice(&MAGIC);
611    bytes.extend_from_slice(&FORMAT.to_le_bytes());
612    #[allow(clippy::cast_possible_truncation)]
613    bytes.push(name.len() as u8);
614    bytes.extend_from_slice(name);
615    bytes.extend_from_slice(&schema.to_le_bytes());
616    // The count is known once the records are written; it is filled in then.
617    let count_at = bytes.len();
618    bytes.extend_from_slice(&0_u32.to_le_bytes());
619    let mut index = BTreeMap::new();
620    let mut count: u32 = 0;
621    for (key, value) in records {
622        // A value over 4 GiB cannot be framed; leaving it out is a miss on the next run.
623        let Ok(length) = u32::try_from(value.len()) else {
624            continue;
625        };
626        bytes.extend_from_slice(key);
627        bytes.extend_from_slice(&length.to_le_bytes());
628        let start = bytes.len();
629        bytes.extend_from_slice(value);
630        index.insert(*key, start..bytes.len());
631        count += 1;
632    }
633    bytes[count_at..count_at + 4].copy_from_slice(&count.to_le_bytes());
634    Stored { bytes, index }
635}
636
637/// Reads bytes off the front of a file, every length bounded by what is left.
638struct Reader<'a> {
639    bytes: &'a [u8],
640    at: usize,
641}
642
643impl Reader<'_> {
644    fn take(&mut self, length: usize) -> Result<Range<usize>, &'static str> {
645        let end = self
646            .at
647            .checked_add(length)
648            .filter(|end| *end <= self.bytes.len())
649            .ok_or("truncated")?;
650        let range = self.at..end;
651        self.at = end;
652        Ok(range)
653    }
654
655    fn u32(&mut self) -> Result<u32, &'static str> {
656        let range = self.take(4)?;
657        let mut word = [0; 4];
658        word.copy_from_slice(&self.bytes[range]);
659        Ok(u32::from_le_bytes(word))
660    }
661
662    fn u8(&mut self) -> Result<u8, &'static str> {
663        let range = self.take(1)?;
664        Ok(self.bytes[range.start])
665    }
666}
667
668/// What a namespace file's header says: its name, schema and record count.
669struct Header {
670    name: String,
671    schema: u32,
672    count: u32,
673}
674
675fn read_header(reader: &mut Reader<'_>) -> Result<Header, &'static str> {
676    if reader.bytes.get(reader.take(MAGIC.len())?) != Some(&MAGIC[..]) {
677        return Err("not a skif cache file");
678    }
679    if reader.u32()? != FORMAT {
680        return Err("another format");
681    }
682    let length = usize::from(reader.u8()?);
683    let name = reader.take(length)?;
684    let name = String::from_utf8_lossy(&reader.bytes[name]).into_owned();
685    let schema = reader.u32()?;
686    let count = reader.u32()?;
687    Ok(Header { name, schema, count })
688}
689
690/// Indexes the records of a namespace file without reading the values, or says why the bytes are not a file of
691/// `namespace`.
692fn decode(bytes: Vec<u8>, namespace: CacheNamespace) -> Result<Stored, &'static str> {
693    let mut reader = Reader { bytes: &bytes, at: 0 };
694    let header = read_header(&mut reader)?;
695    if header.name != namespace.name {
696        return Err("another namespace");
697    }
698    if header.schema != namespace.schema {
699        return Err("written under another schema");
700    }
701    let mut index = BTreeMap::new();
702    let mut last: Option<[u8; 32]> = None;
703    for _ in 0..header.count {
704        let mut key = [0; 32];
705        key.copy_from_slice(&bytes[reader.take(32)?]);
706        if last.is_some_and(|last| last >= key) {
707            return Err("records out of order");
708        }
709        last = Some(key);
710        let length = reader.u32()? as usize;
711        index.insert(key, reader.take(length)?);
712    }
713    if reader.at != bytes.len() {
714        return Err("bytes after the last record");
715    }
716    Ok(Stored { bytes, index })
717}
718
719/// Creates `dir` and the missing directories above it, writing a `CACHEDIR.TAG` and a `.gitignore` of `*` into the
720/// innermost one when it was created. A missing directory named `node_modules` is never created.
721fn create_tagged(dir: &Path) -> Result<(), StoreError> {
722    // The empty path is the current directory to every call below: the tag files would land in the project.
723    if dir.as_os_str().is_empty() {
724        return Err(StoreError::EmptyLocation);
725    }
726    if dir.is_dir() {
727        return Ok(());
728    }
729    let missing: Vec<&Path> = dir.ancestors().take_while(|ancestor| !ancestor.exists()).collect();
730    if let Some(node_modules) = missing
731        .iter()
732        .find(|ancestor| ancestor.file_name() == Some("node_modules".as_ref()))
733    {
734        return Err(StoreError::NodeModules {
735            path: node_modules.to_path_buf(),
736        });
737    }
738    fs::create_dir_all(dir).map_err(|error| StoreError::io(dir, error))?;
739    // A tag that cannot be written leaves a working cache behind; it is only a courtesy to backup tools and git.
740    tag(dir);
741    Ok(())
742}
743
744/// Writes the `CACHEDIR.TAG` and the `.gitignore` of a directory skif created, each only where no file is: a file
745/// that is already there, whoever wrote it, is never replaced.
746fn tag(dir: &Path) {
747    for (name, content) in [(TAG_FILE, CACHEDIR_TAG), (IGNORE_FILE, IGNORE_ALL)] {
748        if let Ok(mut file) = create_new(&dir.join(name)) {
749            let _ = file.write_all(content.as_bytes());
750        }
751    }
752}
753
754/// The bytes of `file`, or `None` when it holds more than `limit` bytes.
755fn read_at_most(file: &Path, limit: u64) -> io::Result<Option<Vec<u8>>> {
756    let handle = File::open(file)?;
757    if handle.metadata()?.len() > limit {
758        return Ok(None);
759    }
760    let mut bytes = Vec::new();
761    // The file may grow between the check and the read.
762    handle.take(limit.saturating_add(1)).read_to_end(&mut bytes)?;
763    Ok((bytes.len() as u64 <= limit).then_some(bytes))
764}
765
766/// The lock of the store in `dir`, or `None` when another process holds it.
767fn try_lock(dir: &Path) -> Result<Option<File>, StoreError> {
768    let path = dir.join(LOCK_FILE);
769    let file = File::options()
770        .create(true)
771        .truncate(false)
772        .write(true)
773        .open(&path)
774        .map_err(|error| StoreError::io(&path, error))?;
775    match file.try_lock() {
776        Ok(()) => Ok(Some(file)),
777        Err(TryLockError::WouldBlock) => Ok(None),
778        Err(TryLockError::Error(error)) => Err(StoreError::io(&path, error)),
779    }
780}
781
782/// Writes `bytes` to `file` through a temporary file in the same directory, so a concurrent reader sees the old file
783/// or the new one, never a part.
784fn write_atomically(file: &Path, bytes: &[u8]) -> Result<(), StoreError> {
785    let written = create_temporary(file).and_then(|(mut handle, temporary)| {
786        let renamed = handle.write_all(bytes).and_then(|()| {
787            // Closed before the rename: a file that is still open cannot be renamed everywhere.
788            drop(handle);
789            fs::rename(&temporary, file)
790        });
791        if renamed.is_err() {
792            let _ = fs::remove_file(&temporary);
793        }
794        renamed
795    });
796    written.map_err(|error| StoreError::io(file, error))
797}
798
799/// A new, empty temporary file next to `file`, named `<file>.<random>.tmp`. It is created only where nothing exists,
800/// so the write never goes through a link or into a file another process made, and its name cannot be guessed.
801fn create_temporary(file: &Path) -> io::Result<(File, PathBuf)> {
802    let mut last = io::Error::from(io::ErrorKind::AlreadyExists);
803    for _ in 0..TEMPORARY_TRIES {
804        // `RandomState` is keyed from the operating system's randomness.
805        let random = std::collections::hash_map::RandomState::new().build_hasher().finish();
806        let mut name = file.file_name().unwrap_or_default().to_os_string();
807        name.push(format!(".{random:016x}{TEMPORARY_SUFFIX}"));
808        let temporary = file.with_file_name(name);
809        match create_new(&temporary) {
810            Ok(handle) => return Ok((handle, temporary)),
811            Err(error) if error.kind() == io::ErrorKind::AlreadyExists => last = error,
812            Err(error) => return Err(error),
813        }
814    }
815    Err(last)
816}
817
818/// Creates `path` for writing, failing when anything is there already, a link included.
819fn create_new(path: &Path) -> io::Result<File> {
820    File::options().write(true).create_new(true).open(path)
821}
822
823/// Removes the temporary files of writes from the store in `dir`. The caller holds the store's lock, so none of them
824/// is being written.
825fn remove_temporaries(dir: &Path) {
826    let Ok(entries) = fs::read_dir(dir) else {
827        return;
828    };
829    for entry in entries.filter_map(Result::ok) {
830        let name = entry.file_name();
831        if is_temporary(&name.to_string_lossy()) && entry.file_type().is_ok_and(|kind| !kind.is_dir()) {
832            let _ = fs::remove_file(entry.path());
833        }
834    }
835}
836
837/// One store in a location, as [`list_stores`] finds it.
838struct StoreDir {
839    dir: PathBuf,
840    bytes: u64,
841    modified: SystemTime,
842    /// Whether its files could be listed; one that cannot be is never sized, evicted or read.
843    readable: bool,
844}
845
846/// Whether `path` is a file; `None` when that cannot be told (the directory holding it cannot be searched).
847fn is_file(path: &Path) -> Option<bool> {
848    match fs::metadata(path) {
849        Ok(metadata) => Some(metadata.is_file()),
850        Err(error) if error.kind() == io::ErrorKind::NotFound => Some(false),
851        Err(_) => None,
852    }
853}
854
855/// The stores in `location`: its directories named like a base key. A store whose directory cannot be read is
856/// listed as unreadable, and an entry of the location that cannot be read is skipped, so one of them never hides
857/// the others.
858fn list_stores(location: &Path) -> io::Result<Vec<StoreDir>> {
859    let mut stores = Vec::new();
860    for entry in fs::read_dir(location)?.filter_map(Result::ok) {
861        let name = entry.file_name();
862        if !entry.file_type().is_ok_and(|kind| kind.is_dir()) || !is_base_dir_name(&name.to_string_lossy()) {
863            continue;
864        }
865        let dir = entry.path();
866        // Only a directory a store wrote its lock or its base into is one: another tool's directory that happens to
867        // be named like a key is left alone.
868        let markers = [is_file(&dir.join(LOCK_FILE)), is_file(&dir.join(BASE_FILE))];
869        if markers == [Some(false), Some(false)] {
870            continue;
871        }
872        let mut store = StoreDir {
873            dir,
874            bytes: 0,
875            modified: SystemTime::UNIX_EPOCH,
876            readable: false,
877        };
878        if markers.contains(&Some(true))
879            && let Ok(files) = fs::read_dir(&store.dir)
880        {
881            store.readable = true;
882            for file in files.filter_map(Result::ok) {
883                let Ok(metadata) = file.metadata() else { continue };
884                let name = file.file_name();
885                let name = name.to_string_lossy();
886                if metadata.is_file() && is_store_file(&name) && !is_temporary(&name) {
887                    store.bytes += metadata.len();
888                    if let Ok(time) = metadata.modified() {
889                        store.modified = store.modified.max(time);
890                    }
891                }
892            }
893        }
894        stores.push(store);
895    }
896    stores.sort_by(|a, b| a.dir.cmp(&b.dir));
897    Ok(stores)
898}
899
900/// The file a temporary file named `name` is written for: `name` is `<file>.<hex digits>.tmp`.
901fn temporary_of(name: &str) -> Option<&str> {
902    name.strip_suffix(TEMPORARY_SUFFIX)
903        .and_then(|rest| rest.rsplit_once('.'))
904        .filter(|(_, random)| !random.is_empty() && random.bytes().all(|byte| byte.is_ascii_hexdigit()))
905        .map(|(file, _)| file)
906}
907
908/// Whether `name` is the temporary file of a write of a store.
909fn is_temporary(name: &str) -> bool {
910    temporary_of(name).is_some_and(is_store_file)
911}
912
913/// Whether `name` is a file a store writes into its directory: the lock, the base, a namespace file, a temporary
914/// file of a write, or the tag files of a directory skif created.
915fn is_store_file(name: &str) -> bool {
916    if matches!(name, LOCK_FILE | BASE_FILE | TAG_FILE | IGNORE_FILE) {
917        return true;
918    }
919    let written = temporary_of(name).unwrap_or(name);
920    written == BASE_FILE
921        || written
922            .strip_suffix(EXTENSION)
923            .and_then(|stem| stem.strip_suffix('.'))
924            .is_some_and(CacheNamespace::is_valid_name)
925}
926
927/// Removes the files the store in `dir` wrote, then the directory when nothing else is in it: a file skif did not
928/// write survives, with its directory.
929fn remove_store(dir: &Path) -> io::Result<()> {
930    for entry in fs::read_dir(dir)? {
931        let entry = entry?;
932        if entry.file_type()?.is_file() && is_store_file(&entry.file_name().to_string_lossy()) {
933            fs::remove_file(entry.path())?;
934        }
935    }
936    match fs::remove_dir(dir) {
937        Err(error) if error.kind() != io::ErrorKind::DirectoryNotEmpty => Err(error),
938        _ => Ok(()),
939    }
940}
941
942fn is_base_dir_name(name: &str) -> bool {
943    name.len() == 32
944        && name
945            .bytes()
946            .all(|byte| byte.is_ascii_digit() || (b'a'..=b'f').contains(&byte))
947}
948
949/// One namespace of a store, as [`stats`] reports it.
950#[derive(Debug, Clone, PartialEq, Eq)]
951#[non_exhaustive]
952pub struct NamespaceStats {
953    /// The namespace name.
954    pub name: String,
955    /// The entries its file holds; `None` when the file is not one skif can read.
956    pub entries: Option<u64>,
957    /// The size of its file.
958    pub bytes: u64,
959}
960
961/// One store of a location, as [`stats`] reports it.
962#[derive(Debug, Clone, PartialEq, Eq)]
963#[non_exhaustive]
964pub struct StoreStats {
965    /// The store's directory name, its base key.
966    pub key: String,
967    /// The base it belongs to (`git:<the repository's git directory>:<path in the repository>` or
968    /// `path:<absolute path>`), when recorded.
969    pub base: Option<String>,
970    /// Its namespaces, by name.
971    pub namespaces: Vec<NamespaceStats>,
972    /// The size of every file in it.
973    pub bytes: u64,
974    /// When a file in it was last written.
975    pub modified: Option<SystemTime>,
976    /// Whether its directory could be read; the sizes and namespaces of one that could not are unknown.
977    pub readable: bool,
978}
979
980/// What a cache location holds, as [`stats`] reports it.
981#[derive(Debug, Clone, PartialEq, Eq, Default)]
982#[non_exhaustive]
983pub struct CacheStats {
984    /// Its stores, by key.
985    pub stores: Vec<StoreStats>,
986    /// The size of every store.
987    pub bytes: u64,
988}
989
990/// What `location` holds: every store with its namespaces, entries and sizes. A missing location holds nothing, and
991/// a store that cannot be read is listed as unreadable.
992///
993/// # Errors
994/// The location exists but cannot be listed.
995pub fn stats(location: &Path) -> io::Result<CacheStats> {
996    let stores = match list_stores(location) {
997        Ok(stores) => stores,
998        Err(error) if error.kind() == io::ErrorKind::NotFound => return Ok(CacheStats::default()),
999        Err(error) => return Err(error),
1000    };
1001    let mut stats = CacheStats::default();
1002    for store in stores {
1003        let key = store
1004            .dir
1005            .file_name()
1006            .map_or_default(|name| name.to_string_lossy().into_owned());
1007        let base = fs::read_to_string(store.dir.join(BASE_FILE)).ok();
1008        let mut namespaces = Vec::new();
1009        let entries = fs::read_dir(&store.dir).into_iter().flatten();
1010        for entry in entries.filter_map(Result::ok) {
1011            let path = entry.path();
1012            if path.extension().is_none_or(|extension| extension != EXTENSION) {
1013                continue;
1014            }
1015            let Some(name) = path.file_stem().map(|stem| stem.to_string_lossy().into_owned()) else {
1016                continue;
1017            };
1018            let bytes = entry.metadata().map_or(0, |metadata| metadata.len());
1019            namespaces.push(NamespaceStats {
1020                entries: header_count(&path, &name),
1021                name,
1022                bytes,
1023            });
1024        }
1025        namespaces.sort_by(|a, b| a.name.cmp(&b.name));
1026        stats.bytes += store.bytes;
1027        stats.stores.push(StoreStats {
1028            key,
1029            base,
1030            namespaces,
1031            bytes: store.bytes,
1032            modified: (store.modified != SystemTime::UNIX_EPOCH).then_some(store.modified),
1033            readable: store.readable,
1034        });
1035    }
1036    Ok(stats)
1037}
1038
1039/// The record count in the header of the namespace file `path` of namespace `name`.
1040fn header_count(path: &Path, name: &str) -> Option<u64> {
1041    let mut head = Vec::new();
1042    File::open(path)
1043        .ok()?
1044        .take(header_size(name) + 8)
1045        .read_to_end(&mut head)
1046        .ok()?;
1047    let header = read_header(&mut Reader { bytes: &head, at: 0 }).ok()?;
1048    (header.name == name).then_some(u64::from(header.count))
1049}
1050
1051/// What [`clean`] removed.
1052#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
1053#[non_exhaustive]
1054pub struct CleanReport {
1055    /// The stores removed.
1056    pub stores: usize,
1057    /// Their size.
1058    pub bytes: u64,
1059}
1060
1061/// Removes the store of `base` from `location`, or with `base` `None` every store in it, then the location itself
1062/// when nothing but skif's own tag files is left. Only the files a store wrote are removed, from directories named
1063/// like a base key that hold a store's lock or base file, so a location shared with another tool (the downloads of
1064/// the pre-commit launcher, which also reads `SKIF_CACHE_DIR`) keeps every file skif did not write. A missing
1065/// location is clean. A store that cannot be removed does not keep the others: they are removed first.
1066///
1067/// # Errors
1068/// The location exists but cannot be listed, or a store to remove could not be.
1069pub fn clean(location: &Path, base: Option<&Path>) -> io::Result<CleanReport> {
1070    let stores = match list_stores(location) {
1071        Ok(stores) => stores,
1072        Err(error) if error.kind() == io::ErrorKind::NotFound => return Ok(CleanReport::default()),
1073        Err(error) => return Err(error),
1074    };
1075    let only = base.map(|base| location.join(base_key(base)));
1076    let mut report = CleanReport::default();
1077    let mut failed: Option<io::Error> = None;
1078    for store in stores {
1079        if only.as_ref().is_some_and(|only| *only != store.dir) {
1080            continue;
1081        }
1082        match remove_store(&store.dir) {
1083            Ok(()) => {
1084                report.stores += 1;
1085                report.bytes += store.bytes;
1086            }
1087            Err(error) => failed = failed.or(Some(error)),
1088        }
1089    }
1090    if let Some(error) = failed {
1091        return Err(error);
1092    }
1093    let leftover: Vec<String> = fs::read_dir(location)?
1094        .filter_map(Result::ok)
1095        .map(|entry| entry.file_name().to_string_lossy().into_owned())
1096        .collect();
1097    // The location goes only when nothing but the tag files skif wrote is left in it.
1098    let own_tags = fs::read_to_string(location.join(TAG_FILE)).is_ok_and(|tag| tag == CACHEDIR_TAG)
1099        && fs::read_to_string(location.join(IGNORE_FILE)).is_ok_and(|ignore| ignore == IGNORE_ALL);
1100    if own_tags && leftover.iter().all(|name| name == TAG_FILE || name == IGNORE_FILE) {
1101        for name in leftover {
1102            fs::remove_file(location.join(name))?;
1103        }
1104        fs::remove_dir(location)?;
1105    }
1106    Ok(report)
1107}
1108
1109const _: () = {
1110    fn assert_send_sync<T: Send + Sync>() {}
1111    let _ = assert_send_sync::<DiskStore>;
1112    let _ = assert_send_sync::<StoreError>;
1113};
1114
1115#[cfg(test)]
1116#[allow(clippy::unwrap_used, clippy::expect_used)]
1117mod tests;