1//! A branch's keyframes, kept at three tiers so a scrubber click near the
2//! live edge - where it matters most - never has to replay far, while a
3//! long session still stays bounded on disk. BizHawk calls this a
4//! "greenzone": dense near the tip, thinning out with age.
5//!
6//! - **Dense** every [`DENSE_FRAMES`] (~2s) for the most recent
7//!   [`DENSE_RETAIN_FRAMES`] (~5 minutes).
8//! - **Medium** every [`MEDIUM_FRAMES`] (~10s) for the next
9//!   [`MEDIUM_RETAIN_FRAMES`] (~1 hour) beyond that.
10//! - **Coarse** every [`COARSE_FRAMES`] (~30s) forever beyond that.
11//!
12//! Every keyframe is delta-compressed (`crate::keyframe`) against the
13//! nearest earlier keyframe of ITS OWN TIER OR COARSER - never a finer one -
14//! so [`KeyframeIndex::prune`]ing a whole aged-out tier never orphans a
15//! survivor's reference. A dense keyframe references the dense-or-coarser
16//! keyframe `DENSE_FRAMES` earlier; a medium keyframe references the
17//! medium-or-coarser keyframe `MEDIUM_FRAMES` earlier; a coarse keyframe is
18//! a base. Chain depth is bounded by construction - at most
19//! `MEDIUM_FRAMES / DENSE_FRAMES - 1` dense hops before a medium-or-coarser
20//! keyframe, then at most `COARSE_FRAMES / MEDIUM_FRAMES - 1` medium hops
21//! before a coarse (base) one - so `BASE_EVERY`-style depth bookkeeping is
22//! no longer needed; the tier boundaries already bound it.
23
24use std::path::{Path, PathBuf};
25use std::{fs, io};
26
27use bincode::{Decode, Encode};
28
29use crate::keyframe;
30
31/// ~2 seconds at 60.0988 fps.
32pub const DENSE_FRAMES: u64 = 120;
33/// ~10 seconds; an exact multiple of `DENSE_FRAMES`.
34pub const MEDIUM_FRAMES: u64 = 600;
35/// ~30 seconds; an exact multiple of `MEDIUM_FRAMES`. Matches this
36/// project's earlier flat cadence, kept as the floor once history is old
37/// enough that nobody is likely to scrub it frame-precisely.
38pub const COARSE_FRAMES: u64 = 1_800;
39
40/// ~5 minutes: how long a keyframe stays at dense spacing before thinning.
41pub const DENSE_RETAIN_FRAMES: u64 = 18_046;
42/// ~1 hour: how long a keyframe stays at medium spacing before thinning to
43/// coarse-only. Beyond this, only coarse keyframes remain for that stretch.
44pub const MEDIUM_RETAIN_FRAMES: u64 = 216_559;
45
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47pub enum Tier {
48    Dense,
49    Medium,
50    Coarse,
51}
52
53/// Which tier `frame` belongs to - the FINEST tier its frame number lands
54/// on. `MEDIUM_FRAMES` and `COARSE_FRAMES` are exact multiples of
55/// `DENSE_FRAMES`, so this is just divisibility.
56pub fn tier_of(frame: u64) -> Tier {
57    if frame % COARSE_FRAMES == 0 {
58        Tier::Coarse
59    } else if frame % MEDIUM_FRAMES == 0 {
60        Tier::Medium
61    } else {
62        Tier::Dense
63    }
64}
65
66/// The frame `frame`'s keyframe SHOULD be delta-compressed against, per its
67/// tier - `None` for a base. `KeyframeIndex::store` still falls back to a
68/// base if this frame is not actually present (a branch's own first
69/// keyframe, at an arbitrary fork point, has nothing earlier in ITS OWN
70/// directory to reference even if this says otherwise).
71fn preferred_reference(frame: u64) -> Option<u64> {
72    match tier_of(frame) {
73        Tier::Coarse => None,
74        Tier::Medium => Some(frame - MEDIUM_FRAMES),
75        Tier::Dense => Some(frame - DENSE_FRAMES),
76    }
77}
78
79const CONFIG: bincode::config::Configuration = bincode::config::standard();
80
81#[derive(Encode, Decode)]
82struct Stored {
83    ref_frame: Option<u64>,
84    original_len: u32,
85    payload: Vec<u8>,
86}
87
88pub struct KeyframeIndex {
89    dir: PathBuf,
90}
91
92fn parse_frame(name: &std::ffi::OsStr) -> Option<u64> {
93    name.to_str()?.strip_suffix(".kf")?.parse().ok()
94}
95
96impl KeyframeIndex {
97    pub fn open(dir: &Path) -> io::Result<Self> {
98        fs::create_dir_all(dir)?;
99        Ok(Self { dir: dir.to_owned() })
100    }
101
102    fn path(&self, frame: u64) -> PathBuf {
103        self.dir.join(format!("{frame:012}.kf"))
104    }
105
106    /// Where a keyframe's file lives on disk - for a caller that only wants
107    /// its size (`apps/replay-probe`'s measurement) without decoding it.
108    pub fn file_path(&self, frame: u64) -> PathBuf {
109        self.path(frame)
110    }
111
112    /// Every keyframe's frame number in this branch, ascending.
113    pub fn frames(&self) -> Vec<u64> {
114        let mut frames: Vec<u64> = fs::read_dir(&self.dir)
115            .into_iter()
116            .flatten()
117            .flatten()
118            .filter_map(|e| parse_frame(&e.file_name()))
119            .collect();
120        frames.sort_unstable();
121        frames
122    }
123
124    /// The largest keyframe frame `<= target`, if any.
125    pub fn nearest_at_or_before(&self, target: u64) -> Option<u64> {
126        self.frames().into_iter().filter(|&f| f <= target).max()
127    }
128
129    fn read_stored(&self, frame: u64) -> io::Result<Stored> {
130        let bytes = fs::read(self.path(frame))?;
131        bincode::decode_from_slice(&bytes, CONFIG)
132            .map(|(s, _)| s)
133            .map_err(|e| io::Error::new(io::ErrorKind::InvalidData, e))
134    }
135
136    /// Decode the keyframe at `frame` back to a full snapshot. `frame` must
137    /// be one [`Self::frames`] lists.
138    pub fn load(&self, frame: u64) -> io::Result<Vec<u8>> {
139        let stored = self.read_stored(frame)?;
140        let reference = match stored.ref_frame {
141            None => None,
142            Some(rf) => Some(self.load(rf)?),
143        };
144        keyframe::decompress(reference.as_deref(), &stored.payload, stored.original_len as usize)
145    }
146
147    /// Keep `snapshot` under `frame`, delta-compressed per its tier
148    /// ([`preferred_reference`]) against whatever is actually on disk - a
149    /// branch's very first keyframe (at its fork point, any frame number)
150    /// has nothing to reference in ITS OWN directory yet regardless of what
151    /// tier its frame number would suggest, so it falls back to a base.
152    /// Written atomically, like every other file this project keeps beside
153    /// a running window.
154    pub fn store(&self, frame: u64, snapshot: &[u8]) -> io::Result<()> {
155        let existing = self.frames();
156        let ref_frame = preferred_reference(frame).filter(|rf| existing.contains(rf));
157        let reference = match ref_frame {
158            Some(rf) => Some(self.load(rf)?),
159            None => None,
160        };
161        let payload = keyframe::compress(reference.as_deref(), snapshot);
162        let stored = Stored { ref_frame, original_len: snapshot.len() as u32, payload };
163        let bytes = bincode::encode_to_vec(&stored, CONFIG).expect("encoding a keyframe never fails");
164        let tmp = self.dir.join(format!("{frame:012}.kf.part"));
165        fs::write(&tmp, bytes)?;
166        fs::rename(tmp, self.path(frame))
167    }
168
169    /// Thin keyframes that have aged out of a finer tier, relative to
170    /// `tip_frame` (the branch's current live edge - or, for a paused
171    /// branch, its last recorded frame). Deletes a WHOLE tier-bucket at
172    /// once, never a partial one, so a still-live keyframe's reference is
173    /// never removed out from under it (this module's own doc comment), and
174    /// never deletes the SMALLEST frame in the index - a branch's own
175    /// anchor keyframe at its fork point, which every seek into its early
176    /// history depends on regardless of what tier its frame number would
177    /// otherwise put it in. Returns how many files were removed.
178    pub fn prune(&self, tip_frame: u64) -> io::Result<usize> {
179        let frames = self.frames();
180        let Some(&anchor) = frames.first() else { return Ok(0) };
181        let mut removed = 0;
182        for frame in frames {
183            if frame == anchor {
184                continue;
185            }
186            let (bucket_width, tier_retain) = match tier_of(frame) {
187                Tier::Dense => (MEDIUM_FRAMES, DENSE_RETAIN_FRAMES),
188                Tier::Medium => (COARSE_FRAMES, MEDIUM_RETAIN_FRAMES),
189                Tier::Coarse => continue, // never thinned further
190            };
191            // The bucket's own last (youngest) member at this tier - only
192            // once IT has aged past the tier's retention window is the
193            // whole bucket safe to remove together.
194            let bucket_start = frame - frame % bucket_width;
195            let bucket_last = bucket_start + bucket_width - if tier_of(frame) == Tier::Dense { DENSE_FRAMES } else { MEDIUM_FRAMES };
196            if tip_frame.saturating_sub(bucket_last) > tier_retain {
197                fs::remove_file(self.path(frame))?;
198                removed += 1;
199            }
200        }
201        Ok(removed)
202    }
203
204    /// Bytes on disk of every keyframe in this branch.
205    pub fn bytes(&self) -> u64 {
206        self.frames().iter().map(|&f| fs::metadata(self.path(f)).map_or(0, |m| m.len())).sum()
207    }
208
209    /// Delete every dense and medium keyframe in the OLDEST `COARSE_FRAMES`
210    /// span that still has any, ahead of their age - what
211    /// `crate::storage::enforce_cap` does to the active recording once
212    /// nothing else is left to delete. The whole span goes at once for the
213    /// same reason [`Self::prune`] removes whole buckets: a finer keyframe
214    /// references one inside its own span, and a coarse keyframe references
215    /// nothing, so removing everything finer in one span can orphan nothing
216    /// that survives. Coarse keyframes and the anchor are never touched, so
217    /// every frame stays seekable, only slower. Returns the bytes freed, 0
218    /// once only coarse keyframes and the anchor remain.
219    pub fn thin_oldest_span(&self) -> io::Result<u64> {
220        let frames = self.frames();
221        let Some(&anchor) = frames.first() else { return Ok(0) };
222        let thinnable = |f: &u64| *f != anchor && tier_of(*f) != Tier::Coarse;
223        let Some(&oldest) = frames.iter().find(|f| thinnable(f)) else { return Ok(0) };
224        let span = oldest / COARSE_FRAMES;
225        let mut freed = 0;
226        for f in frames.iter().filter(|f| thinnable(f) && **f / COARSE_FRAMES == span) {
227            let path = self.path(*f);
228            freed += fs::metadata(&path).map_or(0, |m| m.len());
229            fs::remove_file(path)?;
230        }
231        Ok(freed)
232    }
233}
234
235#[cfg(test)]
236mod tests {
237    use super::*;
238
239    fn scratch(tag: &str) -> KeyframeIndex {
240        let dir = std::env::temp_dir().join(format!("jev-replay-keyframes-test-{tag}-{}", std::process::id()));
241        let _ = fs::remove_dir_all(&dir);
242        KeyframeIndex::open(&dir).unwrap()
243    }
244
245    fn snapshot(seed: u8, len: usize) -> Vec<u8> {
246        (0..len).map(|i| seed.wrapping_add((i % 251) as u8)).collect()
247    }
248
249    #[test]
250    fn tier_of_matches_the_three_boundaries() {
251        assert_eq!(tier_of(0), Tier::Coarse);
252        assert_eq!(tier_of(1_800), Tier::Coarse);
253        assert_eq!(tier_of(3_600), Tier::Coarse);
254        assert_eq!(tier_of(600), Tier::Medium);
255        assert_eq!(tier_of(1_200), Tier::Medium);
256        assert_eq!(tier_of(120), Tier::Dense);
257        assert_eq!(tier_of(240), Tier::Dense);
258        assert_eq!(tier_of(1), Tier::Dense);
259    }
260
261    #[test]
262    fn a_lone_keyframe_round_trips() {
263        let idx = scratch("lone");
264        let data = snapshot(1, 5000);
265        idx.store(100, &data).unwrap();
266        assert_eq!(idx.frames(), vec![100]);
267        assert_eq!(idx.load(100).unwrap(), data);
268    }
269
270    #[test]
271    fn a_full_tier_ladder_all_round_trips() {
272        let idx = scratch("ladder");
273        // Every DENSE_FRAMES step for two full COARSE_FRAMES cycles, so
274        // every tier boundary and every in-between frame is exercised.
275        let mut frame = 0u64;
276        let mut seed = 0u8;
277        while frame <= COARSE_FRAMES * 2 {
278            let mut data = snapshot(seed, 4000);
279            data[10] = seed; // guarantee at least one real change per frame
280            idx.store(frame, &data).unwrap();
281            frame += DENSE_FRAMES;
282            seed = seed.wrapping_add(1);
283        }
284        let frames = idx.frames();
285        assert_eq!(frames.len() as u64, COARSE_FRAMES * 2 / DENSE_FRAMES + 1);
286        let mut seed = 0u8;
287        for f in frames {
288            let mut expected = snapshot(seed, 4000);
289            expected[10] = seed;
290            assert_eq!(idx.load(f).unwrap(), expected, "frame {f}");
291            seed = seed.wrapping_add(1);
292        }
293    }
294
295    #[test]
296    fn nearest_at_or_before_finds_the_right_one() {
297        let idx = scratch("nearest");
298        for f in [10u64, 50, 200] {
299            idx.store(f, &snapshot(1, 100)).unwrap();
300        }
301        assert_eq!(idx.nearest_at_or_before(9), None);
302        assert_eq!(idx.nearest_at_or_before(10), Some(10));
303        assert_eq!(idx.nearest_at_or_before(49), Some(10));
304        assert_eq!(idx.nearest_at_or_before(500), Some(200));
305    }
306
307    #[test]
308    fn a_branchs_first_keyframe_at_an_arbitrary_frame_is_a_base() {
309        // Not a multiple of anything: tier_of would call this Dense and
310        // want to reference frame-120, which does not exist in this fresh
311        // directory - it must fall back to a base instead of erroring.
312        let idx = scratch("arbitrary-anchor");
313        let data = snapshot(7, 2000);
314        idx.store(1_234_567, &data).unwrap();
315        assert_eq!(idx.load(1_234_567).unwrap(), data);
316    }
317
318    #[test]
319    fn pruning_removes_only_whole_aged_out_dense_buckets_and_never_the_anchor() {
320        let idx = scratch("prune-dense");
321        // Anchor at 0 (coarse, never touched), then a full dense ladder up
322        // to just short of the next coarse boundary.
323        let mut frame = 0u64;
324        while frame < COARSE_FRAMES {
325            idx.store(frame, &snapshot(frame as u8, 500)).unwrap();
326            frame += DENSE_FRAMES;
327        }
328        let before = idx.frames();
329        assert!(before.len() > 2, "need more than just the anchor and one dense frame");
330
331        // Not yet aged out: nothing removed.
332        let removed = idx.prune(DENSE_RETAIN_FRAMES).unwrap();
333        assert_eq!(removed, 0);
334        assert_eq!(idx.frames(), before);
335
336        // Aged out: every dense (and medium) frame in the first
337        // MEDIUM_FRAMES bucket goes, but frame 0 (the anchor, coarse
338        // tier) survives regardless of age.
339        let tip = COARSE_FRAMES - DENSE_FRAMES + DENSE_RETAIN_FRAMES + 1;
340        idx.prune(tip).unwrap();
341        let remaining = idx.frames();
342        assert!(remaining.contains(&0), "the anchor must never be pruned");
343        assert!(!remaining.contains(&DENSE_FRAMES), "an aged-out dense frame should be gone");
344        // Every surviving keyframe must still decode.
345        for f in &remaining {
346            idx.load(*f).expect("a surviving keyframe must still decode after pruning");
347        }
348    }
349
350    #[test]
351    fn pruning_a_medium_bucket_never_orphans_a_surviving_dense_reference() {
352        // A dense keyframe just past a medium boundary references the
353        // medium/coarse anchor of ITS OWN bucket, never the previous
354        // bucket's tail - so thinning one medium bucket must never break a
355        // dense keyframe that is still within its own retention window in
356        // the NEXT bucket.
357        let idx = scratch("prune-cross-bucket");
358        for frame in (0..=MEDIUM_FRAMES * 3).step_by(DENSE_FRAMES as usize) {
359            idx.store(frame, &snapshot(frame as u8, 300)).unwrap();
360        }
361        // Age everything past MEDIUM_RETAIN_FRAMES relative to a tip far in
362        // the future, but well within DENSE_RETAIN_FRAMES for the last
363        // bucket, whose own dense members must survive.
364        let tip = MEDIUM_FRAMES * 3 + 10;
365        idx.prune(tip).unwrap();
366        for f in idx.frames() {
367            idx.load(f).expect("every surviving keyframe must still decode");
368        }
369    }
370
371    #[test]
372    fn thinning_takes_the_oldest_span_whole_and_keeps_coarse_and_anchor() {
373        let idx = scratch("thin");
374        // Anchor at 240 (a dense frame number), then every dense step
375        // through three coarse spans.
376        let mut frame = 240;
377        while frame <= COARSE_FRAMES * 3 {
378            idx.store(frame, &snapshot(frame as u8, 400)).unwrap();
379            frame += DENSE_FRAMES;
380        }
381        assert!(idx.thin_oldest_span().unwrap() > 0);
382        let left = idx.frames();
383        assert!(left.contains(&240), "anchor kept");
384        assert!(left.contains(&COARSE_FRAMES), "coarse kept");
385        assert!(!left.iter().any(|&f| f != 240 && f < COARSE_FRAMES), "the first span's finer keyframes are gone");
386        assert!(left.contains(&(COARSE_FRAMES + DENSE_FRAMES)), "the next span is untouched");
387        for f in &left {
388            idx.load(*f).expect("every survivor still decodes");
389        }
390        while idx.thin_oldest_span().unwrap() > 0 {}
391        let left = idx.frames();
392        assert!(left.iter().all(|&f| f == 240 || tier_of(f) == Tier::Coarse));
393        for f in &left {
394            idx.load(*f).expect("every survivor still decodes");
395        }
396    }
397}