Checkpoints: serialized states per bookmark, automatic every core.checkpoint-interval changes, oxy checkpoint, checkpoint-accelerated load_state; states keep change metadata only 252e8cb23fbc

//! Checkpoints (spec §11): a serialized state kept per bookmark so loading

//! a state costs the changes since the checkpoint rather than all of them.

//!

//! The newest checkpoint of each bookmark is pointed at by

//! `.oxy/checkpoints/<bookmark>`; older ones become unreachable and are

//! garbage collected. A checkpoint applies to a requested head set when all

//! of its heads lie in that set's closure, which the loader establishes while

//! walking from the requested heads and stopping at checkpoint members.

use super::*;

use crate::objects::Checkpoint;

impl Repo {

    fn checkpoint_pointer(&self, bookmark: &str) -> PathBuf {

        self.oxy.join("checkpoints").join(bookmark)

    }

    /// The newest checkpoint recorded for a bookmark.

    pub fn latest_checkpoint(&self, bookmark: &str) -> Result<Option<(ObjectRef, Checkpoint)>> {

        match fs::read_to_string(self.checkpoint_pointer(bookmark)) {

            Ok(h) => {

                let r = ObjectRef::from_hex(h.trim()).ok_or_else(|| RepoError::Msg("corrupt checkpoint pointer".into()))?;

                match self.store.get_typed(&r, ObjectType::Checkpoint) {

                    Ok(bytes) => Ok(Some((r, Checkpoint::decode(&bytes)?))),

                    Err(StoreError::NotFound(_)) => Ok(None),

                    Err(e) => Err(e.into()),

                }

            }

            Err(e) if e.kind() == std::io::ErrorKind::NotFound => Ok(None),

            Err(e) => Err(e.into()),

        }

    }

    /// Every checkpoint pointer, for garbage collection roots.

    pub(crate) fn checkpoint_refs(&self) -> Result<Vec<ObjectRef>> {

        let dir = self.oxy.join("checkpoints");

        let mut out = Vec::new();

        if let Ok(rd) = fs::read_dir(&dir) {

            for e in rd.flatten() {

                if let Ok(h) = fs::read_to_string(e.path()) {

                    if let Some(r) = ObjectRef::from_hex(h.trim()) {

                        out.push(r);

                    }

                }

            }

        }

        Ok(out)

    }

    /// Write a checkpoint of `state` (whose heads are `heads`) for `bookmark`.

    pub(crate) fn write_checkpoint(&self, bookmark: &str, state: &State, heads: &[ChangeHash]) -> Result<(ObjectRef, usize)> {

        let payload = state.checkpoint_payload();

        let blob = self.store_blob(&payload)?;

        let cp = Checkpoint { heads: StateObject::new(heads.to_vec()).heads, count: state.len() as u64, payload: blob };

        let r = self.store.put(ObjectType::Checkpoint, &cp.encode())?;

        fs::create_dir_all(self.oxy.join("checkpoints"))?;

        write_atomic(&self.checkpoint_pointer(bookmark), r.to_hex().as_bytes())?;

        Ok((r, payload.len()))

    }

    /// Checkpoint the current bookmark's state now.

    pub fn checkpoint(&self) -> Result<(ObjectRef, usize, usize)> {

        let heads = self.bookmark_heads()?;

        let state = self.load_state_full(&heads)?;

        let (r, bytes) = self.write_checkpoint(&self.config.bookmark, &state, &heads)?;

        Ok((r, state.len(), bytes))

    }

    /// Load the state of `heads` using a checkpoint when one applies.

    pub(crate) fn load_state_checkpointed(&self, heads: &[ChangeHash]) -> Result<Option<State>> {

        let mut bookmarks: Vec<String> = vec![self.config.bookmark.clone()];

        if let Ok(rd) = fs::read_dir(self.oxy.join("checkpoints")) {

            for e in rd.flatten() {

                let name = e.file_name().to_string_lossy().to_string();

                if !bookmarks.contains(&name) {

                    bookmarks.push(name);

                }

            }

        }

        for b in bookmarks {

            let Some((_, cp)) = self.latest_checkpoint(&b)? else { continue };

            // Cheap pre-check: every checkpoint head must be stored.

            if cp.heads.iter().any(|h| !self.store.has(h)) {

                continue;

            }

            let payload = self.read_blob(&cp.payload)?;

            let base = State::from_checkpoint_payload(&payload)?;

            let cp_heads: BTreeSet<ChangeHash> = cp.heads.iter().copied().collect();

            let mut found: BTreeSet<ChangeHash> = BTreeSet::new();

            let mut delta: Vec<Change> = Vec::new();

            let mut seen: BTreeSet<ChangeHash> = BTreeSet::new();

            let mut stack: Vec<ChangeHash> = heads.to_vec();

            while let Some(h) = stack.pop() {

                if !seen.insert(h) {

                    continue;

                }

                if base.contains(&h) {

                    if cp_heads.contains(&h) {

                        found.insert(h);

                    }

                    continue;

                }

                let c = self.store.get_change(&h)?;

                stack.extend(c.deps.iter().copied());

                delta.push(c);

            }

            if found.len() != cp_heads.len() {

                continue;

            }

            let mut state = base;

            for c in delta {

                state.add_unchecked(c);

            }

            state.validate()?;

            return Ok(Some(state));

        }

        Ok(None)

    }

}

fn vertex_value(v: &Vertex) -> crate::cbor::Value {

    use crate::cbor::Value;

    match v {

        Vertex::Start => Value::Uint(0),

        Vertex::End => Value::Uint(1),

        Vertex::Atom((c, i)) => Value::Array(vec![Value::Bytes(c.0.to_vec()), Value::Uint(*i as u64)]),

    }

}

fn vertex_from(v: &crate::cbor::Value) -> Result<Vertex, crate::objects::ObjectError> {

    use crate::cbor::Value;

    use crate::objects::ObjectError;

    match v {

        Value::Uint(0) => Ok(Vertex::Start),

        Value::Uint(1) => Ok(Vertex::End),

        Value::Array(a) if a.len() == 2 => Ok(Vertex::Atom((crate::objects::oref(&a[0], "vertex")?, crate::objects::u32_(&a[1], "vertex")?))),

        _ => Err(ObjectError::Schema("vertex: expected 0, 1, or [hash, index]".into())),

    }

}

impl FileGraph {

    /// Serialize for a checkpoint: `{0: atoms [[hash, index, content|null, [deleters]]], 1: edges [[from, to]]}`.

    pub fn to_value(&self) -> crate::cbor::Value {

        use crate::cbor::Value;

        let mut atoms: Vec<(&AtomKey, &AtomInfo)> = self.atoms.iter().collect();

        atoms.sort_by_key(|(k, _)| **k);

        let mut edges: Vec<(Vertex, Vertex)> = self.succ.iter().flat_map(|(a, bs)| bs.iter().map(move |b| (*a, *b))).collect();

        edges.sort();

        Value::map([

            (

                0,

                Value::Array(

                    atoms

                        .into_iter()

                        .map(|((c, i), info)| {

                            Value::Array(vec![

                                Value::Bytes(c.0.to_vec()),

                                Value::Uint(*i as u64),

                                info.content.as_ref().map(|b| Value::Bytes(b.clone())).unwrap_or(Value::Null),

                                Value::Array(info.deleted_by.iter().map(|d| Value::Bytes(d.0.to_vec())).collect()),

                            ])

                        })

                        .collect(),

                ),

            ),

            (1, Value::Array(edges.iter().map(|(a, b)| Value::Array(vec![vertex_value(a), vertex_value(b)])).collect())),

        ])

    }

    pub fn from_value(v: &crate::cbor::Value) -> Result<FileGraph, crate::objects::ObjectError> {

        use crate::objects::{array, bytes, field, map, oref, u32_, ObjectError};

        let m = map(v, "file graph")?;

        let mut g = FileGraph { atoms: HashMap::new(), succ: HashMap::new(), pred: HashMap::new() };

        for a in array(field(m, 0, "atoms")?, "atoms")? {

            let e = array(a, "atom")?;

            if e.len() != 4 {

                return Err(ObjectError::Schema("atom: expected 4 fields".into()));

            }

            let key = (oref(&e[0], "atom change")?, u32_(&e[1], "atom index")?);

            let content = if e[2].is_null() { None } else { Some(bytes(&e[2], "atom content")?.to_vec()) };

            let deleted_by = array(&e[3], "deleters")?.iter().map(|d| oref(d, "deleter")).collect::<Result<BTreeSet<_>, _>>()?;

            g.atoms.insert(key, AtomInfo { content, deleted_by });

        }

        for e in array(field(m, 1, "edges")?, "edges")? {

            let pair = array(e, "edge")?;

            if pair.len() != 2 {

                return Err(ObjectError::Schema("edge: expected [from, to]".into()));

            }

            g.edge(vertex_from(&pair[0])?, vertex_from(&pair[1])?);

        }

        Ok(g)

    }

}

    #[test]

    fn serialization_round_trip() {

        let mut g = FileGraph::new();

        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));

        g.insert(h(2), 0, Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)), &lines(&["x\n"]));

        g.delete(h(3), &AtomRange { change: h(1), from: 1, to: 2 });

        let v = g.to_value();

        let bytes = crate::cbor::encode(&v);

        let back = FileGraph::from_value(&crate::cbor::decode(&bytes).unwrap()).unwrap();

        let deps = Deps([(h(2), vec![h(1)]), (h(3), vec![h(1)])].into_iter().collect());

        assert_eq!(back.materialize(&deps), g.materialize(&deps));

        assert_eq!(text(&back, &back.materialize(&deps)), "a\nx\n");

        assert_eq!(crate::cbor::encode(&back.to_value()), bytes, "deterministic");

    }

    pub(crate) fn tag(self) -> u64 {

    pub(crate) fn from_tag(t: u64) -> Result<NodeKind, ObjectError> {

    pub(crate) fn bits(self) -> u64 {

    pub(crate) fn from_bits(b: u64) -> Result<Mode, ObjectError> {

    pub(crate) fn tag(self) -> u64 {

    pub(crate) fn from_tag(t: u64) -> Result<ChangeKind, ObjectError> {

// ---------------------------------------------------------------- checkpoint

/// A materialized state (spec §11): the heads it stands for, how many changes

/// it holds, and a blob with the serialized graphs (`State::checkpoint_payload`).

#[derive(Debug, Clone, PartialEq, Eq)]

pub struct Checkpoint {

    pub heads: Vec<ChangeHash>,

    pub count: u64,

    pub payload: ObjectRef,

}

impl Checkpoint {

    pub fn encode(&self) -> Vec<u8> {

        cbor::encode(&Value::map([

            (0, Value::Uint(FORMAT_VERSION)),

            (1, Value::Array(self.heads.iter().map(|h| Value::Bytes(h.0.to_vec())).collect())),

            (2, Value::Uint(self.count)),

            (3, Value::Bytes(self.payload.0.to_vec())),

        ]))

    }

    pub fn hash(&self) -> ObjectRef {

        hash_object(ObjectType::Checkpoint, &self.encode())

    }

    pub fn decode(bytes: &[u8]) -> Result<Checkpoint, ObjectError> {

        let v = cbor::decode(bytes)?;

        let m = map(&v, "checkpoint")?;

        check_version(m)?;

        Ok(Checkpoint {

            heads: array(field(m, 1, "heads")?, "heads")?.iter().map(|h| oref(h, "head")).collect::<Result<Vec<_>, _>>()?,

            count: uint(field(m, 2, "count")?, "count")?,

            payload: oref(field(m, 3, "payload")?, "payload")?,

        })

    }

}

    /// `core.checkpoint-interval`: changes between automatic checkpoints (spec §11).

    pub checkpoint_interval: u64,

            checkpoint_interval: 256,

            "core.checkpoint-interval" => {

                self.checkpoint_interval = value.parse().map_err(|_| RepoError::Msg(format!("expected a number, got {value:?}")))?;

            }

        // Checkpoints: the object, its payload blob, and the blob's chunks.

        for r in self.checkpoint_refs()? {

            if let Ok(bytes) = self.store.get_typed(&r, ObjectType::Checkpoint) {

                keep.insert(r);

                let cp = crate::objects::Checkpoint::decode(&bytes)?;

                keep.insert(cp.payload);

                if let Ok(b) = self.store.get_typed(&cp.payload, ObjectType::Blob) {

                    keep.extend(Blob::decode(&b)?.chunks);

                }

            }

        }

        let load = |h: &ChangeHash| self.store.get_change(h).ok();

        let rewritten = propagate(&state, *old, new, corr, &load).map_err(|e| RepoError::Msg(format!("{e}; rewriting through such references is not implemented yet")))?;

mod checkpoint;

    /// Load the dependency closure of `heads`, through a checkpoint when one applies.

        if let Some(st) = self.load_state_checkpointed(heads)? {

            return Ok(st);

        }

        self.load_state_full(heads)

    }

    /// Load the dependency closure of `heads` change by change.

    pub fn load_state_full(&self, heads: &[ChangeHash]) -> Result<State> {

        let mut entries: Vec<LogEntry> = Vec::new();

        for (h, _) in state.changes() {

            entries.push(LogEntry { hash: *h, change: self.store.get_change(h)?, is_working_copy: *h == wc_hash, is_head: head_set.contains(h) });

        }

        // Automatic checkpoint once enough changes accumulated (spec §11).

        let since = self.latest_checkpoint(&self.config.bookmark)?.map(|(_, cp)| cp.count).unwrap_or(0);

        if self.config.checkpoint_interval > 0 && (st.len() as u64).saturating_sub(since) >= self.config.checkpoint_interval {

            let cp_state = self.load_state_full(&new_heads)?;

            self.write_checkpoint(&self.config.bookmark, &cp_state, &new_heads)?;

        }

#[test]

fn checkpoints_accelerate_loading_and_stay_correct() {

    hermetic();

    let dir = tempfile::tempdir().unwrap();

    let root = dir.path();

    let mut repo = Repo::init(root).unwrap().with_home(root.join("home"));

    repo.config.set("core.checkpoint-interval", "5").unwrap();

    repo.save_config().unwrap();

    let repo = Repo::open(root).unwrap().with_home(root.join("home"));

    let mut hashes = Vec::new();

    for i in 0..12 {

        write(root, "a.txt", format!("{}\n", (0..=i).map(|k| k.to_string()).collect::<Vec<_>>().join("\n")).as_bytes());

        write(root, &format!("f{i}.txt"), b"x\n");

        hashes.push(repo.commit(&format!("c{i}"), &[]).unwrap());

    }

    let (_, cp) = repo.latest_checkpoint("main").unwrap().expect("automatic checkpoint");

    assert!(cp.count >= 5 && cp.count <= 12, "{}", cp.count);

    // Loading through the checkpoint equals loading everything.

    let heads = repo.bookmark_heads().unwrap();

    let fast = repo.load_state(&heads).unwrap();

    let full = repo.load_state_full(&heads).unwrap();

    assert_eq!(fast.len(), full.len());

    assert_eq!(fast.heads(), full.heads());

    let (a, b) = (fast.materialize(), full.materialize());

    assert_eq!(a.files.keys().collect::<Vec<_>>(), b.files.keys().collect::<Vec<_>>());

    for (p, f) in &a.files {

        assert_eq!(f.content, b.files[p].content, "{p}");

    }

    assert!(repo.load_state_checkpointed(&heads).unwrap().is_some());

    // A head set that does not contain the checkpoint's heads falls back.

    assert!(repo.load_state_checkpointed(&[hashes[0]]).unwrap().is_none());

    assert_eq!(repo.load_state(&[hashes[0]]).unwrap().len(), 1);

    // Everything else keeps working on top of the checkpoint.

    assert!(!repo.snapshot("status").unwrap().changed);

    let h = repo.describe(&hashes[3], "c3 described").unwrap();

    assert_eq!(repo.store().get_change(&h).unwrap().message, "c3 described");

    let (r, n, bytes) = repo.checkpoint().unwrap();

    assert!(n >= 12 && bytes > 0);

    assert_eq!(repo.latest_checkpoint("main").unwrap().unwrap().0, r);

    write(root, "a.txt", b"after\n");

    let h_after = repo.commit("after", &[]).unwrap();

    let st = repo.load_state(&repo.bookmark_heads().unwrap()).unwrap();

    assert!(st.contains(&h_after));

    assert!(matches!(&st.materialize().files["a.txt"].content, FileContent::Text { bytes, .. } if bytes == b"after\n"));

    assert_eq!(repo.log().unwrap().len(), 14);

    // Checkpoints survive gc.

    repo.gc(true).unwrap();

    assert!(repo.latest_checkpoint("main").unwrap().is_some());

    assert!(repo.load_state_checkpointed(&repo.bookmark_heads().unwrap()).unwrap().is_some());

}

///

/// `load` fetches a change's full object (a state keeps only metadata).

pub fn propagate(state: &State, old: ChangeHash, new: Option<&Change>, corr: &Correspondence, load: &dyn Fn(&ChangeHash) -> Option<Change>) -> Result<Vec<(ChangeHash, Change)>, RewriteError> {

        let c = load(&h).ok_or(RewriteError::Missing(h))?;

        let rewritten = rewrite_one(&h, &c, &mapping, &corrs)?;

        let all: HashMap<ChangeHash, Change> = [(h1, c1.clone()), (h2, c2.clone()), (h3, c3.clone())].into_iter().collect();

        let load = |h: &ChangeHash| all.get(h).cloned();

        let rewritten = propagate(&st, h1, Some(&n1), &Correspondence::identity(&c1), &load).unwrap();

        let h2 = st.add(c2.clone()).unwrap();

        let all: HashMap<ChangeHash, Change> = [(h1, c1.clone()), (h2, c2)].into_iter().collect();

        let load = |h: &ChangeHash| all.get(h).cloned();

        let err = propagate(&st, h1, Some(&n1), &corr, &load).unwrap_err();

        assert_eq!(propagate(&st, ObjectRef([9; 32]), Some(&n1), &corr, &load).unwrap_err(), RewriteError::Missing(ObjectRef([9; 32])));

        let h1 = st.add(c1.clone()).unwrap();

        let h3 = st.add(c3.clone()).unwrap();

        let mut all: HashMap<ChangeHash, Change> = [(h1, c1), (h2, c2), (h3, c3)].into_iter().collect();

        let load_all = all.clone();

        let load = move |h: &ChangeHash| load_all.get(h).cloned();

        let out = propagate(&st, h2, None, &Correspondence::default(), &load).unwrap();

        let out = propagate(&st, h1, None, &Correspondence::default(), &load).unwrap();

        let h4 = st.add(c4.clone()).unwrap();

        all.insert(h4, c4);

        let load2 = |h: &ChangeHash| all.get(h).cloned();

        let err = propagate(&st, h2, None, &Correspondence::default(), &load2).unwrap_err();

use crate::cbor::{self, Value};

use crate::hash::KeyId;

use crate::objects::{self as o, AtomRef, Change, ChangeKind, Edit, Hlc, Mode, NodeKind, ObjectError, TreeOp};

/// What a state remembers about a change: everything but its operations,

/// which live in the graphs once applied (and in the store).

#[derive(Clone, Debug, PartialEq, Eq)]

pub struct ChangeMeta {

    pub change_id: crate::ids::ChangeId,

    pub deps: Vec<ChangeHash>,

    pub author: KeyId,

    pub hlc: Hlc,

    pub message: String,

    pub kind: ChangeKind,

}

impl ChangeMeta {

    pub fn of(c: &Change) -> ChangeMeta {

        ChangeMeta { change_id: c.change_id, deps: c.deps.clone(), author: c.author, hlc: c.hlc, message: c.message.clone(), kind: c.kind }

    }

}

    changes: HashMap<ChangeHash, ChangeMeta>,

    pub fn get(&self, h: &ChangeHash) -> Option<&ChangeMeta> {

    pub fn changes(&self) -> impl Iterator<Item = (&ChangeHash, &ChangeMeta)> {

        self.changes.insert(h, ChangeMeta::of(&change));

    // ------------------------------------------------------------ checkpoints (spec §11)

    /// Serialize the whole state: change metadata, tree, file graphs, replaces.

    pub fn checkpoint_payload(&self) -> Vec<u8> {

        let mut hashes: Vec<&ChangeHash> = self.changes.keys().collect();

        hashes.sort();

        let changes = Value::Array(

            hashes

                .into_iter()

                .map(|h| {

                    let m = &self.changes[h];

                    Value::Array(vec![

                        Value::Bytes(h.0.to_vec()),

                        Value::Bytes(m.change_id.0.to_vec()),

                        Value::Array(m.deps.iter().map(|d| Value::Bytes(d.0.to_vec())).collect()),

                        Value::Text(m.message.clone()),

                        Value::Uint(m.hlc.wall_ms),

                        Value::Uint(m.hlc.logical as u64),

                        Value::Uint(m.kind.tag()),

                        Value::Bytes(m.author.0.to_vec()),

                    ])

                })

                .collect(),

        );

        let mut nodes: Vec<&NodeId> = self.files.keys().collect();

        nodes.sort();

        let files = Value::Array(nodes.into_iter().map(|n| Value::Array(vec![Value::Bytes(n.0.to_vec()), self.files[n].to_value()])).collect());

        let mut rnodes: Vec<&NodeId> = self.replaces.keys().collect();

        rnodes.sort();

        let opt = |o: &Option<ObjectRef>| o.map(|r| Value::Bytes(r.0.to_vec())).unwrap_or(Value::Null);

        let replaces = Value::Array(

            rnodes

                .into_iter()

                .map(|n| {

                    Value::Array(vec![

                        Value::Bytes(n.0.to_vec()),

                        Value::Array(self.replaces[n].iter().map(|(c, o, nw)| Value::Array(vec![Value::Bytes(c.0.to_vec()), opt(o), opt(nw)])).collect()),

                    ])

                })

                .collect(),

        );

        cbor::encode(&Value::map([(0, Value::Uint(o::FORMAT_VERSION)), (1, changes), (2, self.tree.to_value()), (3, files), (4, replaces)]))

    }

    pub fn from_checkpoint_payload(bytes: &[u8]) -> Result<State, ObjectError> {

        let v = cbor::decode(bytes)?;

        let m = o::map(&v, "checkpoint payload")?;

        o::check_version(m)?;

        let mut st = State::new();

        for c in o::array(o::field(m, 1, "changes")?, "changes")? {

            let e = o::array(c, "change meta")?;

            if e.len() != 8 {

                return Err(ObjectError::Schema("change meta: expected 8 fields".into()));

            }

            let hash = o::oref(&e[0], "hash")?;

            let meta = ChangeMeta {

                change_id: crate::ids::ChangeId::from_slice(o::bytes(&e[1], "change id")?).ok_or_else(|| ObjectError::Schema("change id: expected 16 bytes".into()))?,

                deps: o::array(&e[2], "deps")?.iter().map(|d| o::oref(d, "dep")).collect::<Result<Vec<_>, _>>()?,

                message: o::text(&e[3], "message")?.to_owned(),

                hlc: Hlc { wall_ms: o::uint(&e[4], "wall")?, logical: o::u32_(&e[5], "logical")? },

                kind: ChangeKind::from_tag(o::uint(&e[6], "kind")?)?,

                author: o::oref(&e[7], "author")?,

            };

            st.changes.insert(hash, meta);

        }

        st.tree = TreeGraph::from_value(o::field(m, 2, "tree")?)?;

        for f in o::array(o::field(m, 3, "files")?, "files")? {

            let e = o::array(f, "file")?;

            if e.len() != 2 {

                return Err(ObjectError::Schema("file: expected [node, graph]".into()));

            }

            let node = NodeId::from_slice(o::bytes(&e[0], "node")?).ok_or_else(|| ObjectError::Schema("node: expected 16 bytes".into()))?;

            st.files.insert(node, FileGraph::from_value(&e[1])?);

        }

        let opt = |v: &Value| -> Result<Option<ObjectRef>, ObjectError> { if v.is_null() { Ok(None) } else { o::oref(v, "blob").map(Some) } };

        for r in o::array(o::field(m, 4, "replaces")?, "replaces")? {

            let e = o::array(r, "replace")?;

            if e.len() != 2 {

                return Err(ObjectError::Schema("replace: expected [node, records]".into()));

            }

            let node = NodeId::from_slice(o::bytes(&e[0], "node")?).ok_or_else(|| ObjectError::Schema("node: expected 16 bytes".into()))?;

            let mut recs = Vec::new();

            for rec in o::array(&e[1], "records")? {

                let x = o::array(rec, "record")?;

                if x.len() != 3 {

                    return Err(ObjectError::Schema("record: expected 3 fields".into()));

                }

                recs.push((o::oref(&x[0], "change")?, opt(&x[1])?, opt(&x[2])?));

            }

            st.replaces.insert(node, recs);

        }

        Ok(st)

    }

    fn checkpoint_payload_round_trip_and_replay() {

        let mut st = State::new();

        let f = NodeId::random();

        let h1 = st.add(change(vec![], vec![TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "a".into() }], vec![Edit::Insert { node: f, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"1\n".to_vec(), b"2\n".to_vec()] }])).unwrap();

        let h2 = st.add(change(vec![h1], vec![], vec![Edit::Delete { node: f, atoms: vec![AtomRange { change: h1, from: 0, to: 1 }] }])).unwrap();

        let payload = st.checkpoint_payload();

        let back = State::from_checkpoint_payload(&payload).unwrap();

        assert_eq!(back.len(), 2);

        assert_eq!(back.heads(), vec![h2]);

        assert_eq!(back.get(&h1).unwrap().message, "m");

        assert_eq!(back.checkpoint_payload(), payload, "deterministic");

        // Replaying a further change onto the restored state equals a full build.

        let c3 = change(vec![h2], vec![], vec![Edit::Insert { node: f, after: AtomRef::Atom { change: h1, index: 1 }, before: AtomRef::End, lines: vec![b"3\n".to_vec()] }]);

        let mut full = st.clone();

        full.add(c3.clone()).unwrap();

        let mut restored = back;

        restored.add(c3).unwrap();

        let (a, b) = (full.materialize(), restored.materialize());

        assert_eq!(a.files.keys().collect::<Vec<_>>(), b.files.keys().collect::<Vec<_>>());

        assert_eq!(a.files["a"].content, b.files["a"].content);

        assert!(matches!(&b.files["a"].content, FileContent::Text { bytes, .. } if bytes == b"2\n3\n"));

        assert!(State::from_checkpoint_payload(b"nonsense").is_err());

    }

    #[test]

impl TreeGraph {

    /// Serialize for a checkpoint.

    pub fn to_value(&self) -> crate::cbor::Value {

        use crate::cbor::Value;

        let opkey = |k: &OpKey| vec![Value::Bytes(k.0 .0.to_vec()), Value::Uint(k.1 as u64)];

        let deleters = |m: &HashMap<OpKey, BTreeSet<ChangeHash>>| {

            let mut ks: Vec<&OpKey> = m.keys().collect();

            ks.sort();

            Value::Array(

                ks.into_iter()

                    .map(|k| {

                        let mut v = opkey(k);

                        v.push(Value::Array(m[k].iter().map(|d| Value::Bytes(d.0.to_vec())).collect()));

                        Value::Array(v)

                    })

                    .collect(),

            )

        };

        let mut nodes: Vec<&NodeId> = self.kinds.keys().collect();

        nodes.sort();

        let mut pks: Vec<&OpKey> = self.placements.keys().collect();

        pks.sort();

        let mut mks: Vec<&OpKey> = self.modes.keys().collect();

        mks.sort();

        Value::map([

            (

                0,

                Value::Array(

                    nodes

                        .into_iter()

                        .map(|n| {

                            Value::Array(vec![

                                Value::Bytes(n.0.to_vec()),

                                Value::Uint(self.kinds[n].tag()),

                                self.introduced.get(n).map(|h| Value::Bytes(h.0.to_vec())).unwrap_or(Value::Null),

                            ])

                        })

                        .collect(),

                ),

            ),

            (

                1,

                Value::Array(

                    pks.into_iter()

                        .map(|k| {

                            let p = &self.placements[k];

                            let mut v = opkey(k);

                            v.extend([Value::Bytes(p.node.0.to_vec()), Value::Bytes(p.parent.0.to_vec()), Value::Text(p.name.clone())]);

                            Value::Array(v)

                        })

                        .collect(),

                ),

            ),

            (2, deleters(&self.deleted_placements)),

            (

                3,

                Value::Array(

                    mks.into_iter()

                        .map(|k| {

                            let (n, m) = &self.modes[k];

                            let mut v = opkey(k);

                            v.extend([Value::Bytes(n.0.to_vec()), Value::Uint(m.bits())]);

                            Value::Array(v)

                        })

                        .collect(),

                ),

            ),

            (4, deleters(&self.deleted_modes)),

        ])

    }

    pub fn from_value(v: &crate::cbor::Value) -> Result<TreeGraph, crate::objects::ObjectError> {

        use crate::objects::{array, bytes, field, map, oref, text, u32_, uint, ObjectError};

        let m = map(v, "tree graph")?;

        let node = |v: &crate::cbor::Value| NodeId::from_slice(bytes(v, "node")?).ok_or_else(|| ObjectError::Schema("node: expected 16 bytes".into()));

        let opkey = |e: &[crate::cbor::Value]| -> Result<OpKey, ObjectError> { Ok((oref(&e[0], "op change")?, u32_(&e[1], "op index")?)) };

        let mut g = TreeGraph::default();

        for n in array(field(m, 0, "nodes")?, "nodes")? {

            let e = array(n, "node entry")?;

            if e.len() != 3 {

                return Err(ObjectError::Schema("node entry: expected 3 fields".into()));

            }

            let id = node(&e[0])?;

            g.kinds.insert(id, NodeKind::from_tag(uint(&e[1], "kind")?)?);

            if !e[2].is_null() {

                g.introduced.insert(id, oref(&e[2], "introducer")?);

            }

        }

        for p in array(field(m, 1, "placements")?, "placements")? {

            let e = array(p, "placement")?;

            if e.len() != 5 {

                return Err(ObjectError::Schema("placement: expected 5 fields".into()));

            }

            let k = opkey(e)?;

            let pl = Placement { node: node(&e[2])?, parent: node(&e[3])?, name: text(&e[4], "name")?.to_owned() };

            g.placements_of.entry(pl.node).or_default().insert(k);

            g.placements.insert(k, pl);

        }

        let deleters = |v: &crate::cbor::Value, what: &str| -> Result<HashMap<OpKey, BTreeSet<ChangeHash>>, ObjectError> {

            let mut out = HashMap::new();

            for d in array(v, what)? {

                let e = array(d, what)?;

                if e.len() != 3 {

                    return Err(ObjectError::Schema(format!("{what}: expected 3 fields")));

                }

                out.insert(opkey(e)?, array(&e[2], "deleters")?.iter().map(|x| oref(x, "deleter")).collect::<Result<BTreeSet<_>, _>>()?);

            }

            Ok(out)

        };

        g.deleted_placements = deleters(field(m, 2, "deleted placements")?, "deleted placement")?;

        for md in array(field(m, 3, "modes")?, "modes")? {

            let e = array(md, "mode")?;

            if e.len() != 4 {

                return Err(ObjectError::Schema("mode: expected 4 fields".into()));

            }

            let k = opkey(e)?;

            let n = node(&e[2])?;

            g.modes.insert(k, (n, Mode::from_bits(uint(&e[3], "mode bits")?)?));

            g.modes_of.entry(n).or_default().insert(k);

        }

        g.deleted_modes = deleters(field(m, 4, "deleted modes")?, "deleted mode")?;

        Ok(g)

    }

}

    fn serialization_round_trip() {

        let mut g = TreeGraph::new();

        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "src");

        add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "main.rs");

        g.apply(h(2), 0, &TreeOp::Move { node: nid(2), old: OpRef { change: h(1), index: 1 }, parent: nid(1), name: "lib.rs".into() });

        g.apply(h(3), 0, &TreeOp::SetMode { node: nid(2), old: OpRef { change: h(1), index: 1 }, mode: Mode { exec: true, opaque: false } });

        let bytes = crate::cbor::encode(&g.to_value());

        let back = TreeGraph::from_value(&crate::cbor::decode(&bytes).unwrap()).unwrap();

        assert_eq!(back.view(), g.view());

        assert_eq!(back.introducer(&nid(2)), Some(h(1)));

        assert_eq!(crate::cbor::encode(&back.to_value()), bytes);

    }

    #[test]

    /// Write a checkpoint of the current bookmark's state now

    Checkpoint,

    /// Set a configuration key (author.*, core.sign, core.op-retention, core.gc-grace, core.checkpoint-interval, workspace.bookmark, remote.<name>.url|token|ca)

        Cmd::Checkpoint => workspace::checkpoint(),

pub fn checkpoint() -> Result<i32> {

    let repo = open()?;

    let (r, changes, bytes) = repo.checkpoint()?;

    println!("Checkpoint #{} of {} ({} bytes) written for {}.", r.short(12), plural(changes, "change"), bytes, repo.config.bookmark);

    Ok(0)

}