rfc9162_log/
sidecar.rs

1//! A sidecar log beside a project tree: every change to a path is an entry,
2//! the bytes it wrote are a content-addressed blob in the same store, and a
3//! snapshot is a signed checkpoint.
4//!
5//! The way `.git` sits beside a working tree and etckeeper keeps `/etc` in
6//! one, a [`Sidecar`] keeps a project's history, but the history is an
7//! authenticated log: a third party proves any change from the checkpoint
8//! alone, nothing needs a working tree or a git binary, and retention is
9//! compaction with proofs kept rather than a history rewrite. Over a
10//! [`rfc9162_tiles::PackStore`] the whole sidecar is one file and its lock.
11//!
12//! An entry is one JSON line, [`Change`], and its lookup keys are
13//! `path=<path>` and `blob=<hex>`, so a path's history is a point lookup
14//! and everything under a directory is a range over the sorted runs. A blob
15//! is stored once per content hash at `blob/<hex>` before the entry that
16//! names it is appended, so an entry never names a blob the store lacks.
17//! Entries are at most the tile log's entry length; file content goes in
18//! the blob, not the entry.
19
20use std::collections::BTreeMap;
21use std::path::Path;
22use std::sync::Arc;
23
24use rfc9162_tiles::checkpoint::verify;
25use rfc9162_tiles::{Checkpoint, Note, Signer, TileStore, Verifier};
26use serde::{Deserialize, Serialize};
27use sha2::{Digest, Sha256};
28
29use crate::store::MANIFEST_MAGIC;
30use crate::{AuthenticatedLog, Error, Keys, Located, Store};
31
32/// What a change did to its path.
33#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
34#[serde(rename_all = "lowercase")]
35pub enum Op {
36    /// The path now holds the blob's bytes.
37    Put,
38    /// The path is gone.
39    Delete,
40    /// The path is a child project, and this is its signed checkpoint,
41    /// verified against a trusted key before it was logged.
42    Checkpoint,
43}
44
45/// One change to one path, as the log records it.
46#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
47pub struct Change {
48    /// The format, 1.
49    pub sidecar: u8,
50    /// What happened.
51    pub op: Op,
52    /// The project-relative path, `/`-separated.
53    pub path: String,
54    /// SHA-256 of the bytes, lower-case hex, for a put.
55    #[serde(default, skip_serializing_if = "Option::is_none")]
56    pub blob: Option<String>,
57    /// Length of the bytes, for a put.
58    #[serde(default, skip_serializing_if = "Option::is_none")]
59    pub size: Option<u64>,
60    /// The child's checkpoint origin, for a checkpoint.
61    #[serde(default, skip_serializing_if = "Option::is_none")]
62    pub origin: Option<String>,
63    /// The child's signed checkpoint note, as text, for a checkpoint.
64    #[serde(default, skip_serializing_if = "Option::is_none")]
65    pub note: Option<String>,
66    /// Whatever the caller records with the change: an actor, a job, a
67    /// reason. Keys and values are stored as given.
68    #[serde(default, skip_serializing_if = "BTreeMap::is_empty")]
69    pub meta: BTreeMap<String, String>,
70}
71
72/// A change with its log index and the proof the lookup returned.
73#[derive(Debug, Clone, PartialEq, Eq)]
74pub struct Found {
75    /// The log index of the change.
76    pub index: u64,
77    /// The change.
78    pub change: Change,
79    /// The entry's and its run's inclusion paths.
80    pub located: Located,
81}
82
83/// The lookup keys of a sidecar entry: `path=` and `blob=`. An entry that is
84/// not a sidecar change has no keys.
85#[must_use]
86pub fn sidecar_keys() -> Keys {
87    Arc::new(|entry: &[u8]| {
88        let Ok(change) = serde_json::from_slice::<Change>(entry) else {
89            return Vec::new();
90        };
91        let mut keys = vec![format!("path={}", change.path).into_bytes()];
92        if let Some(blob) = &change.blob {
93            keys.push(format!("blob={blob}").into_bytes());
94        }
95        if let Some(origin) = &change.origin {
96            keys.push(format!("origin={origin}").into_bytes());
97        }
98        keys
99    })
100}
101
102fn blob_path(hex: &str) -> String {
103    format!("blob/{hex}")
104}
105
106fn check_path(path: &str) -> Result<(), Error> {
107    if path.is_empty()
108        || path.starts_with('/')
109        || path.ends_with('/')
110        || path
111            .split('/')
112            .any(|c| c.is_empty() || c == "." || c == "..")
113    {
114        return Err(Error::Tree(
115            "a sidecar path is relative, with no empty, dot or dot-dot component",
116        ));
117    }
118    Ok(())
119}
120
121/// The sidecar over a store.
122pub struct Sidecar<S: TileStore> {
123    log: Store<S>,
124}
125
126impl<S: TileStore> Sidecar<S> {
127    /// Opens the sidecar on `store`, taking the writer lock.
128    pub fn open(store: S) -> Result<Self, Error> {
129        Ok(Self {
130            log: Store::open(store, sidecar_keys())?,
131        })
132    }
133
134    /// The log underneath.
135    #[must_use]
136    pub fn log(&self) -> &Store<S> {
137        &self.log
138    }
139
140    /// Entries in the log, changes and run manifests together.
141    #[must_use]
142    pub fn size(&self) -> u64 {
143        self.log.size()
144    }
145
146    /// The root over the log.
147    #[must_use]
148    pub fn root(&self) -> [u8; 32] {
149        self.log.root()
150    }
151
152    /// Records that `path` now holds `bytes`. The blob is written first,
153    /// once per content hash; the entry follows.
154    pub fn put(
155        &mut self,
156        path: &str,
157        bytes: &[u8],
158        meta: BTreeMap<String, String>,
159    ) -> Result<u64, Error> {
160        check_path(path)?;
161        let digest: [u8; 32] = Sha256::digest(bytes).into();
162        let hex = rfc9162::hex(&digest);
163        let store = self.log.writer().store();
164        let at = blob_path(&hex);
165        if !store.exists(&at)? {
166            store.put(&at, bytes)?;
167        }
168        let change = Change {
169            sidecar: 1,
170            op: Op::Put,
171            path: path.to_string(),
172            blob: Some(hex),
173            size: Some(bytes.len() as u64),
174            origin: None,
175            note: None,
176            meta,
177        };
178        self.append_change(&change)
179    }
180
181    /// Records that `path` is gone.
182    pub fn delete(&mut self, path: &str, meta: BTreeMap<String, String>) -> Result<u64, Error> {
183        check_path(path)?;
184        let change = Change {
185            sidecar: 1,
186            op: Op::Delete,
187            path: path.to_string(),
188            blob: None,
189            size: None,
190            origin: None,
191            note: None,
192            meta,
193        };
194        self.append_change(&change)
195    }
196
197    fn append_change(&mut self, change: &Change) -> Result<u64, Error> {
198        let line = serde_json::to_vec(change).map_err(|_| Error::Tree("change does not encode"))?;
199        self.log.append(&line)
200    }
201
202    /// The bytes of the blob `hex` names, checked against the hash, or
203    /// nothing when the store lacks it.
204    pub fn blob(&self, hex: &str) -> Result<Option<Vec<u8>>, Error> {
205        let Some(bytes) = self.log.writer().store().get(&blob_path(hex))? else {
206            return Ok(None);
207        };
208        let digest: [u8; 32] = Sha256::digest(&bytes).into();
209        if rfc9162::hex(&digest) != hex {
210            return Err(Error::Tampered { what: "blob" });
211        }
212        Ok(Some(bytes))
213    }
214
215    /// The change at log index `index`, or nothing when the entry is a run
216    /// manifest or out of range.
217    pub fn change(&self, index: u64) -> Result<Option<Change>, Error> {
218        let index_view = self.log.index()?;
219        let Some(bytes) = index_view.reader().get(index)? else {
220            return Ok(None);
221        };
222        Ok(decode(&bytes))
223    }
224
225    /// Every change to `path`, oldest first, each with its proof.
226    pub fn history(&self, path: &str) -> Result<Vec<Found>, Error> {
227        let key = format!("path={path}").into_bytes();
228        let located = self.log.find(&key)?;
229        self.found(located)
230    }
231
232    /// Every change to a path under `dir`, in key order, each with its
233    /// proof. `dir` is a directory path without a trailing slash, or the
234    /// empty string for every path.
235    pub fn under(&self, dir: &str) -> Result<Vec<Found>, Error> {
236        let lo = if dir.is_empty() {
237            b"path=".to_vec()
238        } else {
239            format!("path={dir}/").into_bytes()
240        };
241        let mut hi = lo.clone();
242        hi.push(0xff);
243        let located = self.log.range(lo.as_slice()..=hi.as_slice())?;
244        self.found(located)
245    }
246
247    fn found(&self, located: Vec<Located>) -> Result<Vec<Found>, Error> {
248        let index_view = self.log.index()?;
249        let mut out = Vec::with_capacity(located.len());
250        for item in located {
251            let index = item.entry.index;
252            let bytes = index_view
253                .reader()
254                .get(index)?
255                .ok_or(Error::Tree("a located entry is missing"))?;
256            let change = decode(&bytes).ok_or(Error::Tree("a located entry is not a change"))?;
257            out.push(Found {
258                index,
259                change,
260                located: item,
261            });
262        }
263        Ok(out)
264    }
265
266    /// The changes with log index in `from..to`, in log order: what a
267    /// snapshot at `to` holds that one at `from` did not.
268    pub fn diff(&self, from: u64, to: u64) -> Result<Vec<(u64, Change)>, Error> {
269        let to = to.min(self.log.size());
270        let index_view = self.log.index()?;
271        let mut out = Vec::new();
272        for index in from..to {
273            if let Some(bytes) = index_view.reader().get(index)? {
274                if let Some(change) = decode(&bytes) {
275                    out.push((index, change));
276                }
277            }
278        }
279        Ok(out)
280    }
281
282    /// The tree as the first `size` entries leave it: each path's latest
283    /// put, with the index that made it; a deleted path is absent.
284    pub fn tree_at(&self, size: u64) -> Result<BTreeMap<String, (u64, Change)>, Error> {
285        let mut tree = BTreeMap::new();
286        for (index, change) in self.diff(0, size)? {
287            match change.op {
288                Op::Put => {
289                    tree.insert(change.path.clone(), (index, change));
290                }
291                Op::Delete => {
292                    tree.remove(&change.path);
293                }
294                Op::Checkpoint => {}
295            }
296        }
297        Ok(tree)
298    }
299
300    /// Logs a child project's signed checkpoint under `path`, so this log's
301    /// next checkpoint signs the child's. The note has to carry a signature
302    /// from one of `trusted`, and it has to extend the child's last logged
303    /// checkpoint: a smaller size, or the same size with another root, is
304    /// refused as an equivocation. The note is kept whole, so a reader
305    /// re-verifies it from the entry.
306    pub fn include_checkpoint(
307        &mut self,
308        path: &str,
309        note: &Note,
310        trusted: &[Verifier],
311        meta: BTreeMap<String, String>,
312    ) -> Result<u64, Error> {
313        check_path(path)?;
314        verify(note, trusted)?;
315        let checkpoint = Checkpoint::parse(&note.text)?;
316        if let Some((_, last)) = self.checkpoints(path)?.last() {
317            if last.origin != checkpoint.origin {
318                return Err(Error::Tree("a child checkpoint names another origin"));
319            }
320            if checkpoint.size < last.size
321                || (checkpoint.size == last.size && checkpoint.root != last.root)
322            {
323                return Err(Error::Tree(
324                    "a child checkpoint does not extend the one logged",
325                ));
326            }
327        }
328        let change = Change {
329            sidecar: 1,
330            op: Op::Checkpoint,
331            path: path.to_string(),
332            blob: None,
333            size: Some(checkpoint.size),
334            origin: Some(checkpoint.origin.clone()),
335            note: Some(note.to_text()),
336            meta,
337        };
338        self.append_change(&change)
339    }
340
341    /// The child checkpoints logged under `path`, oldest first, each parsed
342    /// from the note the entry keeps.
343    pub fn checkpoints(&self, path: &str) -> Result<Vec<(u64, Checkpoint)>, Error> {
344        let mut out = Vec::new();
345        for found in self.history(path)? {
346            if found.change.op != Op::Checkpoint {
347                continue;
348            }
349            let text = found
350                .change
351                .note
352                .as_deref()
353                .ok_or(Error::Tree("a checkpoint entry has no note"))?;
354            let checkpoint = Checkpoint::parse(&Note::parse(text)?.text)?;
355            out.push((found.index, checkpoint));
356        }
357        Ok(out)
358    }
359
360    /// Seals the unsealed tail into a run, when there is one, and signs the
361    /// log's size and root as a checkpoint under `origin`.
362    pub fn snapshot(&mut self, signer: &Signer, origin: &str) -> Result<Note, Error> {
363        match self.log.seal() {
364            Ok(_) | Err(Error::Tree("nothing to seal")) => {}
365            Err(e) => return Err(e),
366        }
367        Ok(self.log.writer().checkpoint(signer, origin)?)
368    }
369
370    /// Merges the live runs into one and logs it.
371    pub fn compact(&mut self) -> Result<crate::Compaction, Error> {
372        self.log.compact()
373    }
374}
375
376fn decode(bytes: &[u8]) -> Option<Change> {
377    if bytes.starts_with(MANIFEST_MAGIC) {
378        return None;
379    }
380    serde_json::from_slice(bytes).ok()
381}
382
383/// What [`Sidecar::sync_dir`] recorded.
384#[derive(Debug, Clone, Default, PartialEq, Eq)]
385pub struct Synced {
386    /// Paths the log did not hold.
387    pub added: Vec<String>,
388    /// Paths whose bytes differ from the log's latest put.
389    pub changed: Vec<String>,
390    /// Paths the log held that the directory lacks.
391    pub deleted: Vec<String>,
392    /// Paths whose bytes the log already holds.
393    pub unchanged: u64,
394    /// The log range the changes went to, empty when nothing changed.
395    pub entries: std::ops::Range<u64>,
396}
397
398impl<S: TileStore> Sidecar<S> {
399    /// Records the regular files under `root` against the tree the log
400    /// holds, the way etckeeper commits `/etc`: a file the log lacks or holds
401    /// with other bytes is a put, a path the log holds that the directory
402    /// lacks is a delete, and a file with the same bytes is left alone.
403    /// Every change carries `meta`, and all of them go in one batch after
404    /// their blobs. `skip` names entries at the top of `root` that are not
405    /// the project's, the sidecar's own directory among them. Symbolic
406    /// links are not followed and not recorded.
407    pub fn sync_dir(
408        &mut self,
409        root: &Path,
410        skip: &[&str],
411        meta: &BTreeMap<String, String>,
412    ) -> Result<Synced, Error> {
413        let held = self.tree_at(self.log.size())?;
414        let mut files = Vec::new();
415        walk(root, root, skip, &mut files)?;
416        let mut synced = Synced::default();
417        let mut lines = Vec::new();
418        let store_blobs = |this: &Self, hex: &str, bytes: &[u8]| -> Result<(), Error> {
419            let store = this.log.writer().store();
420            let at = blob_path(hex);
421            if !store.exists(&at)? {
422                store.put(&at, bytes)?;
423            }
424            Ok(())
425        };
426        let mut seen = std::collections::BTreeSet::new();
427        for (path, file) in files {
428            let bytes = std::fs::read(&file)?;
429            let digest: [u8; 32] = Sha256::digest(&bytes).into();
430            let hex = rfc9162::hex(&digest);
431            seen.insert(path.clone());
432            match held.get(&path) {
433                Some((_, change)) if change.blob.as_deref() == Some(hex.as_str()) => {
434                    synced.unchanged += 1;
435                    continue;
436                }
437                Some(_) => synced.changed.push(path.clone()),
438                None => synced.added.push(path.clone()),
439            }
440            store_blobs(self, &hex, &bytes)?;
441            let change = Change {
442                sidecar: 1,
443                op: Op::Put,
444                path,
445                blob: Some(hex),
446                size: Some(bytes.len() as u64),
447                origin: None,
448                note: None,
449                meta: meta.clone(),
450            };
451            lines.push(
452                serde_json::to_vec(&change).map_err(|_| Error::Tree("change does not encode"))?,
453            );
454        }
455        for path in held.keys() {
456            if !seen.contains(path) {
457                synced.deleted.push(path.clone());
458                let change = Change {
459                    sidecar: 1,
460                    op: Op::Delete,
461                    path: path.clone(),
462                    blob: None,
463                    size: None,
464                    origin: None,
465                    note: None,
466                    meta: meta.clone(),
467                };
468                lines.push(
469                    serde_json::to_vec(&change)
470                        .map_err(|_| Error::Tree("change does not encode"))?,
471                );
472            }
473        }
474        let size = self.log.size();
475        synced.entries = if lines.is_empty() {
476            size..size
477        } else {
478            self.log.append_batch(lines)?
479        };
480        Ok(synced)
481    }
482}
483
484/// Every regular file under `dir`, as (project path, filesystem path), in
485/// path order. Entries named in `skip` at the top level are left out.
486fn walk(
487    root: &Path,
488    dir: &Path,
489    skip: &[&str],
490    out: &mut Vec<(String, std::path::PathBuf)>,
491) -> Result<(), Error> {
492    let mut entries: Vec<_> = std::fs::read_dir(dir)?.collect::<Result<_, _>>()?;
493    entries.sort_by_key(std::fs::DirEntry::file_name);
494    for entry in entries {
495        let name = entry.file_name();
496        let name = name.to_string_lossy();
497        if dir == root && skip.contains(&name.as_ref()) {
498            continue;
499        }
500        let kind = entry.file_type()?;
501        let path = entry.path();
502        if kind.is_dir() {
503            walk(root, &path, skip, out)?;
504        } else if kind.is_file() {
505            let relative = path
506                .strip_prefix(root)
507                .map_err(|_| Error::Tree("a file is not under the root"))?;
508            let text = relative
509                .components()
510                .map(|c| c.as_os_str().to_string_lossy().into_owned())
511                .collect::<Vec<_>>()
512                .join("/");
513            out.push((text, path));
514        }
515    }
516    Ok(())
517}
rfc9162_log/sidecar.rs

rfc9162_log/
sidecar.rs
