Skip to main content

fallow_extract/cache/
store.rs

1//! Cache store: load, save, and query cached module data.
2
3use std::path::Path;
4
5#[cfg(test)]
6use std::cell::Cell;
7
8use fallow_types::cache_rejection::CacheRejection;
9use fallow_types::path_guard::CacheTarget;
10use rustc_hash::FxHashMap;
11
12use bitcode::{Decode, Encode};
13
14use super::types::{
15    CACHE_VERSION, CachedModule, DEFAULT_CACHE_MAX_SIZE, EVICTION_SIGNIFICANT_BPS,
16    EVICTION_TARGET_BPS, EVICTION_TRIGGER_BPS,
17};
18
19#[cfg(test)]
20thread_local! {
21    static FULL_STORE_ENCODE_COUNT: Cell<usize> = const { Cell::new(0) };
22}
23
24/// Cached module information stored on disk.
25///
26/// Entries are keyed on the ROOT-RELATIVE, forward-slash-normalised path, and
27/// the root is recorded once in the header. Absolute keys made the blob
28/// unusable anywhere but the directory that wrote it: a container job, a
29/// matrix over roots, a GitLab shell executor, or a plain `cp -Rp` to a
30/// sibling path paid the full decode of a multi-megabyte file and then missed
31/// every single lookup, with nothing on stderr to say so.
32#[derive(Debug, Encode, Decode)]
33pub struct CacheStore {
34    version: u32,
35    /// Stable hash of extraction-affecting config fields.
36    config_hash: u64,
37    /// Project root the entries are relative to, forward-slash normalised and
38    /// without a trailing separator. Informational after load: the loader
39    /// re-anchors to the CURRENT root, because a blob restored under another
40    /// path is exactly the case root-relative keys exist to serve.
41    root: String,
42    /// Map from root-relative file path to cached module data.
43    entries: FxHashMap<String, CachedModule>,
44}
45
46impl CacheStore {
47    /// Create a new empty cache anchored at `root`.
48    #[must_use]
49    pub fn new(root: &Path) -> Self {
50        Self {
51            version: CACHE_VERSION,
52            config_hash: 0,
53            root: normalise_root(root),
54            entries: FxHashMap::default(),
55        }
56    }
57
58    /// Load cache from disk.
59    ///
60    /// # Errors
61    ///
62    /// Returns the [`CacheRejection`] that decided against reuse. Every branch
63    /// names itself instead of collapsing into a bare miss: a run that read a
64    /// multi-megabyte blob and then refused it costs the same as a cold run,
65    /// and without a named reason it is indistinguishable from having no cache
66    /// at all. Callers carry
67    /// the reason into the perf table and `fallow doctor`.
68    ///
69    /// The version is read from the file header BEFORE the payload is
70    /// decoded, because the two are decided by different things. A format bump
71    /// changes the encoded shape, so decoding a blob from the previous release
72    /// fails outright and never reaches a version comparison made afterwards:
73    /// the most ordinary event there is (upgrading fallow) then reported
74    /// "cache file could not be decoded", which reads as corruption and sent
75    /// people looking for a damaged disk. With the version in front, an upgrade
76    /// says the format changed. The framing is checked separately from the
77    /// version it carries, so an unframed or unreadable payload reports `Undecodable`
78    /// rather than borrowing the upgrade message.
79    ///
80    /// Every branch that refuses a file that DID exist logs at warn, because
81    /// the user paid the read and got nothing back. Only the missing-file case
82    /// stays quiet.
83    pub fn load(
84        cache_dir: &Path,
85        root: &Path,
86        expected_config_hash: u64,
87        max_size_bytes: usize,
88    ) -> Result<Self, CacheRejection> {
89        Self::load_counting_bytes(cache_dir, root, expected_config_hash, max_size_bytes).0
90    }
91
92    /// [`Self::load`], plus the number of cache bytes read from disk.
93    ///
94    /// The count is returned also when the cache is refused, because the run
95    /// paid for the read either way. It is zero when no file was read.
96    pub fn load_counting_bytes(
97        cache_dir: &Path,
98        root: &Path,
99        expected_config_hash: u64,
100        max_size_bytes: usize,
101    ) -> (Result<Self, CacheRejection>, u64) {
102        let cache_file = cache_dir.join("cache.bin");
103        let data = match std::fs::read(&cache_file) {
104            Ok(data) => data,
105            Err(error) => {
106                if error.kind() != std::io::ErrorKind::NotFound {
107                    tracing::warn!("Cache file could not be read; check the path and permissions");
108                    return (Err(CacheRejection::Unreadable), 0);
109                }
110                return (Err(CacheRejection::Absent), 0);
111            }
112        };
113        let bytes_read = data.len() as u64;
114        (
115            Self::decode_loaded(&data, root, expected_config_hash, max_size_bytes),
116            bytes_read,
117        )
118    }
119
120    fn decode_loaded(
121        data: &[u8],
122        root: &Path,
123        expected_config_hash: u64,
124        max_size_bytes: usize,
125    ) -> Result<Self, CacheRejection> {
126        let safety_ceiling = max_size_bytes.max(DEFAULT_CACHE_MAX_SIZE);
127        if data.len() > safety_ceiling {
128            tracing::warn!(
129                size_mb = data.len() / (1024 * 1024),
130                ceiling_mb = safety_ceiling / (1024 * 1024),
131                "Cache file exceeds safety ceiling, ignoring"
132            );
133            return Err(CacheRejection::Oversize {
134                size_bytes: data.len() as u64,
135                ceiling_bytes: safety_ceiling as u64,
136            });
137        }
138        let payload = read_header(data)?;
139        let mut store: Self = match bitcode::decode(payload) {
140            Ok(s) => s,
141            Err(_) => {
142                tracing::warn!(
143                    "Cache file carries the current format version but its payload could not be \
144                     decoded, rebuilding"
145                );
146                return Err(CacheRejection::Undecodable);
147            }
148        };
149        // The header already agreed with `CACHE_VERSION`, so this catches only a
150        // file whose header and payload disagree: a spliced or hand-edited blob.
151        if store.version != CACHE_VERSION {
152            tracing::warn!(
153                cached_version = store.version,
154                expected_version = CACHE_VERSION,
155                "Cache header and payload declare different format versions, rebuilding"
156            );
157            return Err(CacheRejection::VersionMismatch);
158        }
159        if store.config_hash != expected_config_hash {
160            tracing::warn!(
161                "Cache was built under different extraction config, rebuilding from cold"
162            );
163            return Err(CacheRejection::ConfigHashMismatch);
164        }
165        let current_root = normalise_root(root);
166        if store.root != current_root {
167            tracing::debug!(
168                cached_root = %store.root,
169                "Reusing a cache written under a different project root"
170            );
171            store.root = current_root;
172        }
173        Ok(store)
174    }
175
176    /// Save cache to disk with write-time size enforcement and atomic rename.
177    /// A symlink that leaves the base of `target` stops the save before any
178    /// write.
179    pub fn save(
180        &mut self,
181        target: CacheTarget<'_>,
182        config_hash: u64,
183        max_size_bytes: usize,
184    ) -> Result<(), String> {
185        target
186            .write_gitignore()
187            .map_err(|e| format!("Failed to write cache .gitignore: {e}"))?;
188
189        self.config_hash = config_hash;
190        let initial_entries = self.entries.len();
191        let mut encoded = self.encode();
192
193        let trigger = (max_size_bytes / 10_000).saturating_mul(EVICTION_TRIGGER_BPS);
194        if encoded.len().saturating_add(CACHE_HEADER_LEN) > trigger {
195            // The cap is a promise about the file, and the file carries the
196            // header as well as the payload, so eviction aims below both.
197            let target = (max_size_bytes / 10_000)
198                .saturating_mul(EVICTION_TARGET_BPS)
199                .saturating_sub(CACHE_HEADER_LEN);
200            // The working set of the latest run may fill the whole cap.
201            let working_set = max_size_bytes.saturating_sub(CACHE_HEADER_LEN);
202            encoded = self.evict_lru_to_target(target, working_set, encoded);
203            let evicted = initial_entries.saturating_sub(self.entries.len());
204            let final_size = encoded.len();
205            let significant_evicted =
206                initial_entries.saturating_mul(EVICTION_SIGNIFICANT_BPS) / 10_000;
207            if evicted >= significant_evicted && initial_entries > 0 {
208                tracing::info!(
209                    evicted_entries = evicted,
210                    remaining_entries = self.entries.len(),
211                    final_size_kb = final_size / 1024,
212                    max_size_kb = max_size_bytes / 1024,
213                    "Cache eviction: removed oldest entries to stay under cap"
214                );
215            } else {
216                tracing::debug!(
217                    evicted_entries = evicted,
218                    remaining_entries = self.entries.len(),
219                    final_size_kb = final_size / 1024,
220                    max_size_kb = max_size_bytes / 1024,
221                    "Cache eviction"
222                );
223            }
224        }
225
226        target
227            .write_file("cache.bin", &framed(self.version, &encoded))
228            .map_err(|e| format!("Failed to write cache file: {e}"))
229    }
230
231    /// Evict the entries that runs saw least recently until the re-encoded
232    /// size is under `target_bytes` or only one entry remains.
233    ///
234    /// The entries with the newest seen stamp are the working set of the
235    /// latest run, and they all share that one stamp. Eviction removes older
236    /// entries down to `target_bytes` first. It removes working-set entries
237    /// only down to `working_set_bytes`, which is the cap itself. The low
238    /// target gives headroom for entries that other scopes add. The working
239    /// set must not go down to the low target: a working set a little over
240    /// the trigger then loses about 40 percent of its entries on every save,
241    /// and the next run parses those files again. The tie order of the keys
242    /// is stable, so the same entries go on each save and the rest stay hits.
243    fn evict_lru_to_target(
244        &mut self,
245        target_bytes: usize,
246        working_set_bytes: usize,
247        encoded: Vec<u8>,
248    ) -> Vec<u8> {
249        let mut order: Vec<(u64, String, usize)> = self
250            .entries
251            .iter()
252            .map(|(key, entry)| {
253                (
254                    entry.last_seen_secs,
255                    key.clone(),
256                    bitcode::encode(entry)
257                        .len()
258                        .saturating_add(key.len())
259                        .max(1),
260                )
261            })
262            .collect();
263        order.sort();
264        let newest = order.last().map_or(0, |(seen, _, _)| *seen);
265        let working_set_from = order.partition_point(|(seen, _, _)| *seen < newest);
266
267        let mut cursor = EvictionCursor {
268            idx: 0,
269            estimated_remaining: order
270                .iter()
271                .map(|(_, _, estimated_bytes)| estimated_bytes)
272                .sum(),
273        };
274        let mut encoded = encoded;
275        if working_set_from > 0 {
276            encoded = self.evict_order_range(
277                &order,
278                &mut cursor,
279                working_set_from,
280                target_bytes,
281                encoded,
282            );
283        }
284        let working_set_target = target_bytes.max(working_set_bytes);
285        if encoded.len() > working_set_target {
286            let keep_newest_from = order.len().saturating_sub(1);
287            encoded = self.evict_order_range(
288                &order,
289                &mut cursor,
290                keep_newest_from,
291                working_set_target,
292                encoded,
293            );
294        }
295
296        if encoded.len() > working_set_target && self.entries.len() == 1 {
297            tracing::warn!(
298                encoded_kb = encoded.len() / 1024,
299                target_kb = working_set_target / 1024,
300                "Single cache entry exceeds configured max; cache will overshoot the cap"
301            );
302        }
303        encoded
304    }
305
306    /// Remove entries in `order` from `cursor.idx` up to (not including)
307    /// `end` until the re-encoded size is under `target_bytes`.
308    fn evict_order_range(
309        &mut self,
310        order: &[(u64, String, usize)],
311        cursor: &mut EvictionCursor,
312        end: usize,
313        target_bytes: usize,
314        mut encoded: Vec<u8>,
315    ) -> Vec<u8> {
316        const MAX_REFINEMENT_PASSES: usize = 2;
317        const ESTIMATE_SAFETY_BPS: usize = 9_800;
318        for _ in 0..MAX_REFINEMENT_PASSES {
319            if encoded.len() <= target_bytes || cursor.idx >= end {
320                return encoded;
321            }
322
323            let estimated_budget = estimated_eviction_budget(
324                cursor.estimated_remaining,
325                target_bytes,
326                encoded.len(),
327                ESTIMATE_SAFETY_BPS,
328            );
329            let start_idx = cursor.idx;
330            while cursor.idx < end && cursor.estimated_remaining > estimated_budget {
331                self.evict_at(order, cursor);
332            }
333            if cursor.idx == start_idx {
334                self.evict_at(order, cursor);
335            }
336            encoded = self.encode();
337        }
338
339        if encoded.len() > target_bytes && cursor.idx < end {
340            let conservative_budget = target_bytes / 2;
341            while cursor.idx < end && cursor.estimated_remaining > conservative_budget {
342                self.evict_at(order, cursor);
343            }
344            encoded = self.encode();
345        }
346
347        // Per-entry encodings are deliberately conservative, but keep the
348        // configured cap exact if a future bitcode layout violates that
349        // estimate. This safety path runs only after byte-aware retention had
350        // three opportunities to preserve a recent suffix.
351        if encoded.len() > target_bytes && cursor.idx < end {
352            while cursor.idx < end {
353                self.evict_at(order, cursor);
354            }
355            encoded = self.encode();
356        }
357        encoded
358    }
359
360    fn evict_at(&mut self, order: &[(u64, String, usize)], cursor: &mut EvictionCursor) {
361        let (_, key, estimated_bytes) = &order[cursor.idx];
362        self.entries.remove(key);
363        cursor.estimated_remaining = cursor.estimated_remaining.saturating_sub(*estimated_bytes);
364        cursor.idx += 1;
365    }
366
367    fn encode(&self) -> Vec<u8> {
368        #[cfg(test)]
369        FULL_STORE_ENCODE_COUNT.with(|count| count.set(count.get() + 1));
370        bitcode::encode(self)
371    }
372
373    #[cfg(test)]
374    pub(super) fn reset_full_store_encode_count() {
375        FULL_STORE_ENCODE_COUNT.with(|count| count.set(0));
376    }
377
378    #[cfg(test)]
379    pub(super) fn full_store_encode_count() -> usize {
380        FULL_STORE_ENCODE_COUNT.with(Cell::get)
381    }
382
383    /// Key `path` the way entries are stored: root-relative where possible,
384    /// forward-slash normalised.
385    ///
386    /// A path outside the root keeps its own normalised spelling. It is still
387    /// stable within one root, which is all a lookup needs, and no root-
388    /// relative spelling of it exists to prefer.
389    fn key_for(&self, path: &Path) -> String {
390        let text = path.to_string_lossy().replace('\\', "/");
391        if self.root.is_empty() {
392            return text;
393        }
394        match text
395            .strip_prefix(&self.root)
396            .and_then(|rest| rest.strip_prefix('/'))
397        {
398            Some(relative) => relative.to_owned(),
399            None => text,
400        }
401    }
402
403    /// Rebuild the absolute path an entry key refers to under the current root.
404    fn path_for_key(&self, key: &str) -> std::path::PathBuf {
405        if self.root.is_empty() {
406            return std::path::PathBuf::from(key);
407        }
408        let candidate = Path::new(key);
409        if candidate.is_absolute() {
410            return candidate.to_path_buf();
411        }
412        Path::new(&self.root).join(key)
413    }
414
415    /// Look up a cached module by path and content hash.
416    /// Returns None if not cached or hash mismatch.
417    #[must_use]
418    pub fn get(&self, path: &Path, content_hash: u64) -> Option<&CachedModule> {
419        let entry = self.entries.get(&self.key_for(path))?;
420        if entry.content_hash == content_hash {
421            Some(entry)
422        } else {
423            None
424        }
425    }
426
427    /// Insert or update a cached module.
428    pub fn insert(&mut self, path: &Path, module: CachedModule) {
429        let key = self.key_for(path);
430        self.entries.insert(key, module);
431    }
432
433    /// Replace the source fingerprint of the entry for `path`, and keep the
434    /// rest of the entry.
435    ///
436    /// A fresh checkout or a restored cache moves the file timestamps but not
437    /// the content. Rebuilding such an entry from the module copies every
438    /// extracted fact again, so a caller whose content hash still matches
439    /// refreshes only the metadata. Returns `false` when no entry exists.
440    pub fn refresh_fingerprint(
441        &mut self,
442        path: &Path,
443        fingerprint: fallow_types::source_fingerprint::SourceFingerprint,
444    ) -> bool {
445        let key = self.key_for(path);
446        let Some(entry) = self.entries.get_mut(&key) else {
447            return false;
448        };
449        entry.mtime_ns = fingerprint.mtime_ns;
450        entry.ctime_ns = fingerprint.ctime_ns;
451        entry.file_size = fingerprint.file_size;
452        true
453    }
454
455    /// Look up a cached module by path only (ignoring hash).
456    #[must_use]
457    pub fn get_by_path_only(&self, path: &Path) -> Option<&CachedModule> {
458        self.entries.get(&self.key_for(path))
459    }
460
461    /// Remove cache entries for files that no longer exist on disk, and mark
462    /// the entries for every discovered file as seen by this run.
463    ///
464    /// Returns `true` when any entry was removed. The seen stamp alone does
465    /// not make the store dirty: a run that saves nothing else does not
466    /// rewrite the whole blob to persist it, and the next run that saves
467    /// stamps the same files again.
468    ///
469    /// The seen stamp orders eviction. A file that every run discovers keeps a
470    /// current stamp even when it never changes, so `evict_lru_to_target`
471    /// removes the entries that only another scope reads before it removes
472    /// the files that this scope reads on every run.
473    ///
474    /// The predicate is deliberately "still exists", not "was discovered by
475    /// this run". Discovery is scoped: `--production` drops test and story
476    /// files, `--root` narrows to a subtree, and `ignorePatterns` differs per
477    /// command. Evicting whatever the current scope did not walk meant one
478    /// `--production` run threw away the entries for every test file, and the
479    /// next full run reparsed them from cold. Entries are keyed by absolute
480    /// path, so the check is one `symlink_metadata` per undiscovered entry
481    /// (`symlink_metadata`, not `metadata`, so a broken symlink still counts as
482    /// present rather than being evicted as missing). Size is not this
483    /// method's concern: `evict_lru_to_target` remains the only guard on how
484    /// large the blob may grow.
485    pub fn retain_paths(&mut self, files: &[fallow_types::discover::DiscoveredFile]) -> bool {
486        use rustc_hash::FxHashSet;
487        let current_keys: FxHashSet<String> = files.iter().map(|f| self.key_for(&f.path)).collect();
488        let before = self.entries.len();
489        let retained: FxHashSet<String> = self
490            .entries
491            .keys()
492            .filter(|key| {
493                current_keys.contains(*key)
494                    || std::fs::symlink_metadata(self.path_for_key(key)).is_ok()
495            })
496            .cloned()
497            .collect();
498        self.entries.retain(|key, _| retained.contains(key));
499        let now = super::conversion::current_unix_seconds();
500        for key in &current_keys {
501            if let Some(entry) = self.entries.get_mut(key) {
502                entry.last_seen_secs = now;
503            }
504        }
505        self.entries.len() != before
506    }
507
508    /// Number of cached entries.
509    #[must_use]
510    pub fn len(&self) -> usize {
511        self.entries.len()
512    }
513
514    /// Whether the cache is empty.
515    #[must_use]
516    pub fn is_empty(&self) -> bool {
517        self.entries.is_empty()
518    }
519}
520
521/// Position in the sorted eviction order, and the estimated size of the
522/// entries that remain.
523struct EvictionCursor {
524    idx: usize,
525    estimated_remaining: usize,
526}
527
528/// Marker written ahead of every cache payload so the format version can be
529/// read without decoding the payload it describes.
530///
531/// Constant across format bumps: only the version field beside it moves. That
532/// lets future upgrades report an explicit version mismatch; older unframed
533/// caches still report an ambiguous decode failure.
534const CACHE_MAGIC: [u8; 4] = *b"FLWX";
535
536/// Bytes the framing adds ahead of the payload: the magic plus a little-endian
537/// `u32` format version.
538pub(super) const CACHE_HEADER_LEN: usize = CACHE_MAGIC.len() + 4;
539
540/// Prepend the format header to an encoded payload.
541///
542/// The version comes from the store being written rather than from the
543/// constant, so the header always describes the payload behind it.
544pub(super) fn framed(version: u32, payload: &[u8]) -> Vec<u8> {
545    let mut framed = Vec::with_capacity(CACHE_HEADER_LEN + payload.len());
546    framed.extend_from_slice(&CACHE_MAGIC);
547    framed.extend_from_slice(&version.to_le_bytes());
548    framed.extend_from_slice(payload);
549    framed
550}
551
552/// Split a cache file into its declared version and its payload, refusing
553/// anything this binary cannot read WITHOUT decoding it first.
554///
555/// The version check has to come first: a format bump changes the encoded
556/// shape, so a blob from the previous release fails to decode and a version
557/// comparison made after the decode is unreachable on the one event that
558/// triggers it most, an upgrade.
559///
560/// A recognized header exposes a version mismatch without decoding. Releases
561/// before framing wrote raw payloads, so a missing header cannot distinguish
562/// an older cache from foreign or damaged data. `Undecodable` keeps that
563/// uncertainty explicit and the next successful run replaces the blob.
564fn read_header(data: &[u8]) -> Result<&[u8], CacheRejection> {
565    let Some((header, payload)) = data.split_at_checked(CACHE_HEADER_LEN) else {
566        tracing::warn!("Cache file is too short to carry a format header, rebuilding");
567        return Err(CacheRejection::Undecodable);
568    };
569    let (declared_magic, declared_version) = header.split_at(CACHE_MAGIC.len());
570    if declared_magic != CACHE_MAGIC {
571        tracing::warn!("Cache file does not carry fallow's cache framing, rebuilding");
572        return Err(CacheRejection::Undecodable);
573    }
574    // The slice is exactly four bytes; the fallback only has to be a version
575    // this binary never writes, so an impossible header is refused rather than
576    // trusted.
577    let declared = declared_version.try_into().map_or(0, u32::from_le_bytes);
578    if declared != CACHE_VERSION {
579        tracing::warn!(
580            cached_version = declared,
581            expected_version = CACHE_VERSION,
582            "Cache format upgraded, rebuilding (one-time cost after version bump)"
583        );
584        return Err(CacheRejection::VersionMismatch);
585    }
586    Ok(payload)
587}
588
589pub(super) fn estimated_eviction_budget(
590    estimated_remaining: usize,
591    target_bytes: usize,
592    encoded_bytes: usize,
593    safety_bps: usize,
594) -> usize {
595    if encoded_bytes == 0 {
596        return 0;
597    }
598
599    const BASIS_POINTS: u128 = 10_000;
600    let scaled = estimated_remaining as u128 * target_bytes as u128 / encoded_bytes as u128;
601    let safety = (safety_bps as u128).min(BASIS_POINTS);
602    let budget = scaled / BASIS_POINTS * safety + scaled % BASIS_POINTS * safety / BASIS_POINTS;
603    budget.min(usize::MAX as u128) as usize
604}
605
606/// Normalise a project root for storage and prefix stripping: forward slashes,
607/// no trailing separator. An empty root disables stripping, which is what a
608/// default-constructed store gets.
609fn normalise_root(root: &Path) -> String {
610    let text = root.to_string_lossy().replace('\\', "/");
611    match text.strip_suffix('/') {
612        Some(trimmed) => trimmed.to_owned(),
613        None => text,
614    }
615}
616
617impl Default for CacheStore {
618    fn default() -> Self {
619        Self::new(Path::new(""))
620    }
621}