blockworx/storage/
compact.rs

1//! Reclaiming space in a container, on request and never otherwise.
2//!
3//! Two things accumulate. History entries, one per settled edit, which are small
4//! but unbounded; and assets, which are never dropped when a document stops
5//! placing them because an older snapshot may still name one. The second is
6//! where the space actually is — a stale 4 MB image outweighs a thousand
7//! snapshots.
8//!
9//! Both are deliberately manual. Deleting history automatically would mean the
10//! app silently discarding the thing it exists to preserve, and the reachability
11//! that makes asset collection safe is only as good as every snapshot being
12//! readable — so when one is not, this collects nothing rather than guessing.
13
14use std::collections::BTreeSet;
15use std::time::Duration;
16
17use super::container::{ASSETS, Container, ROOT};
18use super::{Storage, history};
19use crate::schema::model as schema;
20
21/// How much history to keep.
22///
23/// Recent work stays browsable edit by edit; older work thins to one entry per
24/// bucket, which is enough to answer "what did this look like that afternoon"
25/// without keeping every keystroke of it.
26#[derive(Clone, Copy, Debug)]
27pub struct Policy {
28    /// Entries younger than this are always kept.
29    pub keep_all_within: Duration,
30    /// Beyond that, at most one entry per bucket of this width.
31    pub bucket: Duration,
32}
33
34impl Default for Policy {
35    fn default() -> Self {
36        Self {
37            keep_all_within: Duration::from_hours(24),
38            bucket: Duration::from_hours(1),
39        }
40    }
41}
42
43/// What a compaction did.
44#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
45pub struct Compacted {
46    pub entries_removed: usize,
47    pub assets_removed: usize,
48}
49
50/// Which entries to drop, given each one's sequence number and timestamp,
51/// oldest first.
52///
53/// Keeps the newest entry whatever its age — a container untouched for a year
54/// must not compact away the only record of what is in it — and keeps the *last*
55/// entry in each bucket, since the end of an hour's work is more useful than its
56/// beginning.
57fn thin(entries: &[(u64, Option<u64>)], policy: &Policy, now: u64) -> Vec<u64> {
58    let keep_all_ms = policy.keep_all_within.as_millis() as u64;
59    let bucket_ms = policy.bucket.as_millis().max(1) as u64;
60    let newest = entries.last().map(|(seq, _)| *seq);
61
62    let mut drop = Vec::new();
63    for (index, (seq, ts)) in entries.iter().enumerate() {
64        if Some(*seq) == newest {
65            continue;
66        }
67        // No sidecar means no age to judge by. Keeping it is the conservative
68        // reading: it is still a perfectly good snapshot.
69        let Some(ts) = *ts else { continue };
70        if now.saturating_sub(ts) <= keep_all_ms {
71            continue;
72        }
73        // The last entry of a bucket is the one that survives, so look ahead:
74        // anything followed by another entry in the same bucket goes.
75        let same_bucket_follows = entries[index + 1..]
76            .iter()
77            .find_map(|(_, next)| next.map(|t| t / bucket_ms == ts / bucket_ms))
78            .unwrap_or(false);
79        if same_bucket_follows {
80            drop.push(*seq);
81        }
82    }
83    drop
84}
85
86/// Thin the history and drop assets nothing reaches any more.
87pub fn compact(
88    container: &Container<impl Storage>,
89    policy: &Policy,
90    now: u64,
91) -> miette::Result<Compacted> {
92    let storage = container.storage();
93    let records = history::records(storage).map_err(|e| miette::miette!("reading history: {e}"))?;
94
95    let ages: Vec<(u64, Option<u64>)> = records
96        .iter()
97        .map(|r| (r.seq, r.meta.as_ref().map(|m| m.ts)))
98        .collect();
99    let doomed = thin(&ages, policy, now);
100    for seq in &doomed {
101        for path in history::paths(*seq) {
102            storage
103                .remove(&path)
104                .map_err(|e| miette::miette!("removing {path}: {e}"))?;
105        }
106    }
107
108    let survivors: Vec<u64> = records
109        .iter()
110        .map(|r| r.seq)
111        .filter(|seq| !doomed.contains(seq))
112        .collect();
113    let assets_removed = collect_assets(container, &survivors)?;
114
115    Ok(Compacted {
116        entries_removed: doomed.len(),
117        assets_removed,
118    })
119}
120
121/// Remove asset files that neither the current document nor any surviving
122/// snapshot places.
123///
124/// A snapshot that cannot be read or parsed aborts the collection entirely. The
125/// asymmetry is deliberate: keeping a file nothing needs costs disk, while
126/// deleting one something still names loses an image for good.
127fn collect_assets(container: &Container<impl Storage>, survivors: &[u64]) -> miette::Result<usize> {
128    let storage = container.storage();
129    let mut reachable = BTreeSet::new();
130    let mut reach = |src: &str, from: &str| -> miette::Result<()> {
131        let model = schema::Document::parse_kdl(src, from)?;
132        reachable.extend(model.referenced_assets().into_iter().map(str::to_string));
133        Ok(())
134    };
135
136    if storage.exists(ROOT) {
137        let bytes = storage
138            .read(ROOT)
139            .map_err(|e| miette::miette!("reading {ROOT}: {e}"))?;
140        reach(&String::from_utf8_lossy(&bytes), ROOT)?;
141    }
142    for seq in survivors {
143        match history::read(storage, *seq) {
144            Ok(src) => reach(&src, "history")?,
145            Err(e) => {
146                tracing::warn!("History entry {seq} could not be read ({e}); keeping every asset");
147                return Ok(0);
148            }
149        }
150    }
151
152    let names = storage
153        .list(ASSETS)
154        .map_err(|e| miette::miette!("listing {ASSETS}: {e}"))?;
155    let mut removed = 0;
156    for name in names {
157        if reachable.contains(&name) {
158            continue;
159        }
160        let path = format!("{ASSETS}/{name}");
161        storage
162            .remove(&path)
163            .map_err(|e| miette::miette!("removing {path}: {e}"))?;
164        removed += 1;
165    }
166    Ok(removed)
167}
168
169#[cfg(test)]
170mod tests {
171    use super::*;
172    use crate::document::{Document, Image, ImageData};
173    use crate::storage::atomic::tests::TempDir;
174    use crate::storage::fs::FsStorage;
175    use crate::store::IdMapExt as _;
176
177    const HOUR: u64 = 60 * 60 * 1000;
178
179    fn policy() -> Policy {
180        Policy {
181            keep_all_within: Duration::from_hours(24),
182            bucket: Duration::from_hours(1),
183        }
184    }
185
186    /// Ages in hours before `now`, oldest first.
187    fn aged(hours: &[u64]) -> (Vec<(u64, Option<u64>)>, u64) {
188        let now = 1000 * HOUR;
189        let entries = hours
190            .iter()
191            .enumerate()
192            // Saturating: a test age may reach past this synthetic epoch, and
193            // "as old as it gets" is what it means anyway.
194            .map(|(i, h)| (i as u64, Some(now.saturating_sub(h * HOUR))))
195            .collect();
196        (entries, now)
197    }
198
199    #[test]
200    fn recent_work_is_kept_edit_by_edit() {
201        // Four edits within the last hour, all inside the keep-all window.
202        let (entries, now) = aged(&[1, 1, 1, 0]);
203        assert!(thin(&entries, &policy(), now).is_empty());
204    }
205
206    /// Older work thins to the *end* of each bucket: what an hour of work
207    /// finished as is more useful than what it started as.
208    #[test]
209    fn old_work_thins_to_one_entry_per_bucket() {
210        // Three edits in one old hour, two in another, plus a recent one.
211        let now = 1000 * HOUR;
212        let old = now - 100 * HOUR;
213        let entries = vec![
214            (0, Some(old)),
215            (1, Some(old + 60_000)),
216            (2, Some(old + 120_000)),
217            (3, Some(old + HOUR)),
218            (4, Some(old + HOUR + 60_000)),
219            (5, Some(now)),
220        ];
221        // The survivors of each bucket are its last: 2 and 4.
222        assert_eq!(thin(&entries, &policy(), now), vec![0, 1, 3]);
223    }
224
225    /// A container nobody has touched in a year still knows what is in it.
226    #[test]
227    fn the_newest_entry_is_never_thinned() {
228        let (entries, now) = aged(&[10_000]);
229        assert!(thin(&entries, &policy(), now).is_empty());
230    }
231
232    /// An entry whose sidecar was lost has no age to judge by, so it stays.
233    #[test]
234    fn an_entry_with_no_sidecar_is_kept() {
235        let now = 1000 * HOUR;
236        let old = now - 100 * HOUR;
237        let entries = vec![
238            (0, None),
239            (1, Some(old)),
240            (2, Some(old + 1000)),
241            (3, Some(now)),
242        ];
243        assert_eq!(thin(&entries, &policy(), now), vec![1]);
244    }
245
246    fn with_image(marker: &str) -> Document {
247        let mut doc = Document::default();
248        let top = doc.top_id;
249        doc.blocks
250            .get_mut(&top)
251            .expect("top")
252            .images
253            .insert_value(Image::new(
254                ImageData::Svg(format!("<svg viewBox=\"0 0 1 1\"><!--{marker}--></svg>")),
255                egui::Rect::ZERO,
256            ));
257        doc
258    }
259
260    fn entry(ts: u64) -> history::Entry {
261        history::Entry {
262            ts,
263            command: None,
264            changed: Vec::new(),
265        }
266    }
267
268    fn assets_in(container: &Container<FsStorage>) -> Vec<String> {
269        let mut names = container.storage().list(ASSETS).unwrap();
270        names.sort();
271        names
272    }
273
274    /// The case assets are never collected automatically for: an image the
275    /// document has dropped but an old snapshot still places.
276    #[test]
277    fn an_asset_a_surviving_snapshot_still_places_is_kept() {
278        let dir = TempDir::new("compact-asset-reachable");
279        let c = Container::new(FsStorage::new(dir.path()), "c");
280        let now = 1000 * HOUR;
281
282        c.save_and_record(&with_image("old"), 0, &entry(now))
283            .unwrap();
284        c.save_and_record(&with_image("new"), 1, &entry(now))
285            .unwrap();
286        assert_eq!(assets_in(&c).len(), 2, "two distinct images so far");
287
288        // Both entries are recent, so nothing is thinned and the old snapshot
289        // keeps its image alive.
290        let done = compact(&c, &policy(), now).unwrap();
291        assert_eq!(done, Compacted::default());
292        assert_eq!(assets_in(&c).len(), 2);
293    }
294
295    /// Once the snapshot naming it is thinned away, the asset goes too.
296    #[test]
297    fn an_asset_nothing_reaches_any_more_is_removed() {
298        let dir = TempDir::new("compact-asset-orphaned");
299        let c = Container::new(FsStorage::new(dir.path()), "c");
300        let now = 1000 * HOUR;
301        let old = now - 100 * HOUR;
302
303        // Two old entries in one bucket: the first will be thinned.
304        c.save_and_record(&with_image("dropped"), 0, &entry(old))
305            .unwrap();
306        c.save_and_record(&with_image("kept"), 1, &entry(old + 1000))
307            .unwrap();
308        c.save_and_record(&with_image("kept"), 2, &entry(now))
309            .unwrap();
310        assert_eq!(assets_in(&c).len(), 2);
311
312        let done = compact(&c, &policy(), now).unwrap();
313        assert_eq!(done.entries_removed, 1);
314        assert_eq!(done.assets_removed, 1);
315        let left = assets_in(&c);
316        assert_eq!(left.len(), 1, "{left:?}");
317        // The surviving document still loads, image and all.
318        assert_eq!(c.load().unwrap(), with_image("kept"));
319    }
320
321    /// Reachability is only as good as every snapshot being readable, so a
322    /// damaged one collects nothing rather than guessing.
323    #[test]
324    fn an_unreadable_snapshot_stops_asset_collection() {
325        let dir = TempDir::new("compact-unreadable");
326        let c = Container::new(FsStorage::new(dir.path()), "c");
327        let now = 1000 * HOUR;
328
329        c.save_and_record(&with_image("one"), 0, &entry(now))
330            .unwrap();
331        c.save(&Document::default()).unwrap();
332        assert_eq!(assets_in(&c).len(), 1);
333
334        // Corrupt the only snapshot that could vouch for the asset.
335        std::fs::write(dir.path().join("history/000000.kdl.gz"), b"not gzip").unwrap();
336
337        let done = compact(&c, &policy(), now).unwrap();
338        assert_eq!(
339            done.assets_removed, 0,
340            "an unreadable snapshot must not free assets"
341        );
342        assert_eq!(assets_in(&c).len(), 1, "the image survived the doubt");
343    }
344
345    #[test]
346    fn compacting_an_empty_container_does_nothing() {
347        let dir = TempDir::new("compact-empty");
348        let c = Container::new(FsStorage::new(dir.path()), "c");
349        assert_eq!(compact(&c, &policy(), 0).unwrap(), Compacted::default());
350    }
351}
blockworx/storage/compact.rs

blockworx/storage/
compact.rs
