OXYGENHUB
# e8d38e47e9d7 oxygen / crates / oxy-core / src / state.rs
55.0 KiB · Rust · last changed History-only states: log, log of a path and blame_in load changes and tree only, deferring file edits; load_graphs builds the graphs a command needs from checkpoint blobs or by replay, identical to a full load; an unloaded graph is never read as empty 1 month ago source blame history raw
1 
//! A state: a dependency-closed set of changes, applied to a tree graph and
2 
//! per-node file graphs (spec §8.3), with materialization (spec §9.5, §11).
3
4 
use crate::cbor::{self, Value};
5 
use crate::graph::{AtomKey, DepOracle, FileGraph, Materialized, Vertex};
6 
use crate::hash::KeyId;
7 
use crate::hash::{ChangeHash, ObjectRef};
8 
use crate::ids::NodeId;
9 
use crate::objects::{
10 
    self as o, AtomRef, Change, ChangeKind, Edit, Hlc, Mode, NodeKind, ObjectError, TreeOp,
11 
};
12 
use crate::tree::{TreeGraph, TreeView};
13 
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
14 
use std::sync::{Arc, Mutex};
15
16 
/// Checkpoint payload version 2 (spec §11): file graphs by reference.
17 
pub const CHECKPOINT_INDEX_VERSION: u64 = 2;
18
19 
/// A file graph encoded in fewer bytes stays inline in a version 2 index.
20 
pub const INLINE_GRAPH_LIMIT: usize = 2048;
21
22 
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
23 
pub enum StateError {
24 
    #[error("change {1} depends on {0}, which is not in the state")]
25 
    MissingDep(ChangeHash, ChangeHash),
26 
}
27
28 
/// One `Replace` edit: `(change, old blob, new blob)`.
29 
type ReplaceRecord = (ChangeHash, Option<ObjectRef>, Option<ObjectRef>);
30
31 
/// What a state remembers about a change: everything but its operations,
32 
/// which live in the graphs once applied (and in the store).
33 
#[derive(Clone, Debug, PartialEq, Eq)]
34 
pub struct ChangeMeta {
35 
    pub change_id: crate::ids::ChangeId,
36 
    pub deps: Vec<ChangeHash>,
37 
    pub author: KeyId,
38 
    pub hlc: Hlc,
39 
    pub message: String,
40 
    pub kind: ChangeKind,
41 
}
42
43 
impl ChangeMeta {
44 
    pub fn of(c: &Change) -> ChangeMeta {
45 
        ChangeMeta {
46 
            change_id: c.change_id,
47 
            deps: c.deps.clone(),
48 
            author: c.author,
49 
            hlc: c.hlc,
50 
            message: c.message.clone(),
51 
            kind: c.kind,
52 
        }
53 
    }
54 
}
55
56 
#[derive(Default)]
57 
pub struct State {
58 
    changes: HashMap<ChangeHash, ChangeMeta>,
59 
    tree: TreeGraph,
60 
    files: HashMap<NodeId, FileGraph>,
61 
    replaces: HashMap<NodeId, Vec<ReplaceRecord>>,
62 
    /// Memoised transitive dependencies. A mutex, not a `RefCell`, so a
63 
    /// loaded state can be shared across threads by a host that caches it.
64 
    closure: Mutex<HashMap<ChangeHash, Arc<HashSet<ChangeHash>>>>,
65 
    /// `None` for a full state. For a history-only state (loaded for its
66 
    /// changes and tree), the file graphs not built yet, by node: `files`
67 
    /// holds only those loaded with [`State::load_graphs`].
68 
    deferred: Option<HashMap<NodeId, Deferred>>,
69 
}
70
71 
/// A file graph a history-only state has not built: its base from a
72 
/// version 2 checkpoint, if any, and the edits of later changes in the
73 
/// order they were applied (spec §11). Building it later gives the same
74 
/// graph, since graph construction does not depend on order (§8).
75 
#[derive(Clone, Default)]
76 
struct Deferred {
77 
    base: Option<DeferredBase>,
78 
    edits: Vec<(ChangeHash, Vec<Edit>)>,
79 
}
80
81 
#[derive(Clone)]
82 
enum DeferredBase {
83 
    Inline(Value),
84 
    Blob(ObjectRef),
85 
}
86
87 
impl Clone for State {
88 
    fn clone(&self) -> State {
89 
        State {
90 
            changes: self.changes.clone(),
91 
            tree: self.tree.clone(),
92 
            files: self.files.clone(),
93 
            replaces: self.replaces.clone(),
94 
            closure: Mutex::new(self.closure.lock().unwrap().clone()),
95 
            deferred: self.deferred.clone(),
96 
        }
97 
    }
98 
}
99
100 
#[derive(Clone, Debug, PartialEq, Eq)]
101 
pub enum FileContent {
102 
    Text {
103 
        bytes: Vec<u8>,
104 
        materialized: Materialized,
105 
    },
106 
    /// Live blobs; more than one is a replace conflict (spec §9.3).
107 
    Opaque {
108 
        blobs: Vec<ObjectRef>,
109 
    },
110 
    Dir,
111 
}
112
113 
#[derive(Clone, Debug, PartialEq, Eq)]
114 
pub struct FileState {
115 
    pub node: NodeId,
116 
    pub kind: NodeKind,
117 
    pub mode: Mode,
118 
    pub content: FileContent,
119 
}
120
121 
impl FileState {
122 
    pub fn is_conflicted(&self) -> bool {
123 
        match &self.content {
124 
            FileContent::Text { materialized, .. } => materialized.is_conflicted(),
125 
            FileContent::Opaque { blobs } => blobs.len() > 1,
126 
            FileContent::Dir => false,
127 
        }
128 
    }
129 
}
130
131 
/// See `State::conflict_regions`.
132 
#[derive(Clone, Debug, Default, PartialEq, Eq)]
133 
pub struct ConflictRegions {
134 
    pub plain: Vec<(AtomKey, Vec<u8>)>,
135 
    pub region_atoms: Vec<AtomKey>,
136 
    pub contributors: Vec<ChangeHash>,
137 
}
138
139 
/// The whole tree of a state, materialized.
140 
#[derive(Clone, Debug, Default)]
141 
pub struct Snapshot {
142 
    pub tree: TreeView,
143 
    pub files: BTreeMap<String, FileState>,
144 
}
145
146 
impl Snapshot {
147 
    pub fn is_conflicted(&self) -> bool {
148 
        self.tree.is_conflicted() || self.files.values().any(|f| f.is_conflicted())
149 
    }
150 
}
151
152 
fn vertex(r: AtomRef) -> Vertex {
153 
    match r {
154 
        AtomRef::Start => Vertex::Start,
155 
        AtomRef::End => Vertex::End,
156 
        AtomRef::Atom { change, index } => Vertex::Atom((change, index)),
157 
    }
158 
}
159
160 
/// Replace self references in a tree op with the concrete change hash.
161 
pub fn resolve_tree_op(op: &TreeOp, me: ChangeHash) -> TreeOp {
162 
    match op {
163 
        TreeOp::RemoveNode { node, placement } => TreeOp::RemoveNode {
164 
            node: *node,
165 
            placement: placement.resolve(me),
166 
        },
167 
        TreeOp::Move {
168 
            node,
169 
            old,
170 
            parent,
171 
            name,
172 
        } => TreeOp::Move {
173 
            node: *node,
174 
            old: old.resolve(me),
175 
            parent: *parent,
176 
            name: name.clone(),
177 
        },
178 
        TreeOp::SetMode { node, old, mode } => TreeOp::SetMode {
179 
            node: *node,
180 
            old: old.resolve(me),
181 
            mode: *mode,
182 
        },
183 
        add @ TreeOp::AddNode { .. } => add.clone(),
184 
    }
185 
}
186
187 
/// Apply one change's edits of one file (inserts and deletes; replaces
188 
/// live beside the graphs) to that file's graph.
189 
fn apply_file_edits(g: &mut FileGraph, h: ChangeHash, edits: Vec<Edit>) {
190 
    let mut next = 0u32;
191 
    for e in edits {
192 
        match e {
193 
            Edit::Insert {
194 
                after,
195 
                before,
196 
                lines,
197 
                ..
198 
            } => {
199 
                let first = next;
200 
                next += lines.len() as u32;
201 
                g.insert_owned(
202 
                    h,
203 
                    first,
204 
                    vertex(after.resolve(h)),
205 
                    vertex(before.resolve(h)),
206 
                    lines,
207 
                );
208 
            }
209 
            Edit::Delete { atoms, .. } => {
210 
                for r in atoms {
211 
                    g.delete(h, &r.resolve(h));
212 
                }
213 
            }
214 
            Edit::Replace { .. } => {}
215 
        }
216 
    }
217 
}
218
219 
impl State {
220 
    pub fn new() -> Self {
221 
        Self::default()
222 
    }
223
224 
    /// An empty state for history only: changes and tree are kept, file
225 
    /// edits are recorded but no file graph is built until
226 
    /// [`State::load_graphs`] asks for it. For log and other commands that
227 
    /// need no file contents, or only a few files.
228 
    pub fn new_history_only() -> Self {
229 
        State {
230 
            deferred: Some(HashMap::new()),
231 
            ..Self::default()
232 
        }
233 
    }
234
235 
    /// Whether this state holds every file graph.
236 
    pub fn is_full(&self) -> bool {
237 
        self.deferred.as_ref().is_none_or(|d| d.is_empty())
238 
    }
239
240 
    /// The graph of `node`, which must be loaded: asking a history-only
241 
    /// state for a graph it has not built is a bug, never an empty file.
242 
    fn graph(&self, node: &NodeId) -> Option<&FileGraph> {
243 
        if let Some(d) = &self.deferred {
244 
            assert!(
245 
                !d.contains_key(node),
246 
                "file graph {} of a history-only state was not loaded (State::load_graphs)",
247 
                node.short(12)
248 
            );
249 
        }
250 
        self.files.get(node)
251 
    }
252
253 
    /// Operations over every file need every graph.
254 
    fn require_full(&self, what: &str) {
255 
        assert!(
256 
            self.is_full(),
257 
            "{what} needs every file graph; this state was loaded for history only"
258 
        );
259 
    }
260
261 
    /// Build the graphs of `nodes` in a history-only state: from their
262 
    /// checkpoint base (blobs read in one batch through `load`) and their
263 
    /// deferred edits. Nodes already built, or with no graph, are skipped.
264 
    pub fn load_graphs(
265 
        &mut self,
266 
        nodes: &[NodeId],
267 
        load: impl FnOnce(&[ObjectRef]) -> Result<Vec<Vec<u8>>, ObjectError>,
268 
    ) -> Result<(), ObjectError> {
269 
        let Some(deferred) = self.deferred.as_mut() else {
270 
            return Ok(());
271 
        };
272 
        let mut taken: Vec<(NodeId, Deferred)> = nodes
273 
            .iter()
274 
            .filter_map(|n| deferred.remove(n).map(|d| (*n, d)))
275 
            .collect();
276 
        let refs: Vec<ObjectRef> = taken
277 
            .iter()
278 
            .filter_map(|(_, d)| match &d.base {
279 
                Some(DeferredBase::Blob(r)) => Some(*r),
280 
                _ => None,
281 
            })
282 
            .collect();
283 
        let mut blobs = if refs.is_empty() {
284 
            Vec::new()
285 
        } else {
286 
            load(&refs)?
287 
        }
288 
        .into_iter();
289 
        for (node, d) in taken.iter_mut() {
290 
            let mut graph = match d.base.take() {
291 
                Some(DeferredBase::Inline(v)) => FileGraph::from_value(&v)?,
292 
                Some(DeferredBase::Blob(_)) => {
293 
                    let bytes = blobs
294 
                        .next()
295 
                        .ok_or_else(|| ObjectError::Schema("graph blobs: wrong count".into()))?;
296 
                    FileGraph::from_value(&cbor::decode(&bytes)?)?
297 
                }
298 
                None => FileGraph::default(),
299 
            };
300 
            for (h, edits) in std::mem::take(&mut d.edits) {
301 
                apply_file_edits(&mut graph, h, edits);
302 
            }
303 
            self.files.insert(*node, graph);
304 
        }
305 
        Ok(())
306 
    }
307
308 
    pub fn len(&self) -> usize {
309 
        self.changes.len()
310 
    }
311 
    pub fn is_empty(&self) -> bool {
312 
        self.changes.is_empty()
313 
    }
314 
    pub fn contains(&self, h: &ChangeHash) -> bool {
315 
        self.changes.contains_key(h)
316 
    }
317 
    pub fn get(&self, h: &ChangeHash) -> Option<&ChangeMeta> {
318 
        self.changes.get(h)
319 
    }
320 
    pub fn changes(&self) -> impl Iterator<Item = (&ChangeHash, &ChangeMeta)> {
321 
        self.changes.iter()
322 
    }
323 
    pub fn tree(&self) -> &TreeGraph {
324 
        &self.tree
325 
    }
326 
    pub fn file(&self, node: &NodeId) -> Option<&FileGraph> {
327 
        self.graph(node)
328 
    }
329
330 
    /// Add a change whose dependencies are already present.
331 
    pub fn add(&mut self, change: Change) -> Result<ChangeHash, StateError> {
332 
        let h = change.hash();
333 
        if self.changes.contains_key(&h) {
334 
            return Ok(h);
335 
        }
336 
        for d in &change.deps {
337 
            if !self.changes.contains_key(d) {
338 
                return Err(StateError::MissingDep(*d, h));
339 
            }
340 
        }
341 
        Ok(self.add_unchecked(change))
342 
    }
343
344 
    /// Add a change in any order; call `validate` once all are in.
345 
    pub fn add_unchecked(&mut self, change: Change) -> ChangeHash {
346 
        let h = change.hash();
347 
        if self.changes.contains_key(&h) {
348 
            return h;
349 
        }
350 
        let meta = ChangeMeta::of(&change);
351 
        self.apply(h, change);
352 
        self.changes.insert(h, meta);
353 
        self.closure.lock().unwrap().clear();
354 
        h
355 
    }
356
357 
    // ------------------------------------------------------------ checkpoints (spec §11)
358
359 
    /// Serialize the whole state in payload version 1: change metadata,
360 
    /// tree, file graphs, replaces, all in one value (spec §11).
361 
    pub fn checkpoint_payload(&self) -> Vec<u8> {
362 
        self.require_full("a checkpoint");
363 
        let mut nodes: Vec<&NodeId> = self.files.keys().collect();
364 
        nodes.sort();
365 
        let files = Value::Array(
366 
            nodes
367 
                .into_iter()
368 
                .map(|n| Value::Array(vec![Value::Bytes(n.0.to_vec()), self.files[n].to_value()]))
369 
                .collect(),
370 
        );
371 
        cbor::encode(&self.payload_value(o::FORMAT_VERSION, files))
372 
    }
373
374 
    /// Each file graph encoded on its own, by node, for a version 2 payload
375 
    /// (spec §11): the graphs of large files become blobs of their own.
376 
    pub fn checkpoint_file_graphs(&self) -> Vec<(NodeId, Vec<u8>)> {
377 
        use rayon::prelude::*;
378 
        self.require_full("a checkpoint");
379 
        let mut nodes: Vec<(&NodeId, &FileGraph)> = self.files.iter().collect();
380 
        nodes.sort_by_key(|(n, _)| **n);
381 
        nodes
382 
            .into_par_iter()
383 
            .map(|(n, g)| (*n, cbor::encode(&g.to_value())))
384 
            .collect()
385 
    }
386
387 
    /// The payload version 2 index for the graphs of
388 
    /// [`State::checkpoint_file_graphs`]: a graph encoded in fewer than
389 
    /// [`INLINE_GRAPH_LIMIT`] bytes is kept inline, a larger one is named by
390 
    /// `blob_of` (the ObjectRef of the blob holding its encoding).
391 
    pub fn checkpoint_index(
392 
        &self,
393 
        graphs: &[(NodeId, Vec<u8>)],
394 
        mut blob_of: impl FnMut(&[u8]) -> ObjectRef,
395 
    ) -> Vec<u8> {
396 
        let files = Value::Array(
397 
            graphs
398 
                .iter()
399 
                .map(|(n, enc)| {
400 
                    let entry = if enc.len() < INLINE_GRAPH_LIMIT {
401 
                        cbor::decode(enc).expect("an encoded graph decodes")
402 
                    } else {
403 
                        Value::Bytes(blob_of(enc).0.to_vec())
404 
                    };
405 
                    Value::Array(vec![Value::Bytes(n.0.to_vec()), entry])
406 
                })
407 
                .collect(),
408 
        );
409 
        cbor::encode(&self.payload_value(CHECKPOINT_INDEX_VERSION, files))
410 
    }
411
412 
    /// The payload map around `files`: changes, tree and replaces as in version 1.
413 
    fn payload_value(&self, version: u64, files: Value) -> Value {
414 
        let mut hashes: Vec<&ChangeHash> = self.changes.keys().collect();
415 
        hashes.sort();
416 
        let changes = Value::Array(
417 
            hashes
418 
                .into_iter()
419 
                .map(|h| {
420 
                    let m = &self.changes[h];
421 
                    Value::Array(vec![
422 
                        Value::Bytes(h.0.to_vec()),
423 
                        Value::Bytes(m.change_id.0.to_vec()),
424 
                        Value::Array(m.deps.iter().map(|d| Value::Bytes(d.0.to_vec())).collect()),
425 
                        Value::Text(m.message.clone()),
426 
                        Value::Uint(m.hlc.wall_ms),
427 
                        Value::Uint(m.hlc.logical as u64),
428 
                        Value::Uint(m.kind.tag()),
429 
                        Value::Bytes(m.author.0.to_vec()),
430 
                    ])
431 
                })
432 
                .collect(),
433 
        );
434 
        let mut rnodes: Vec<&NodeId> = self.replaces.keys().collect();
435 
        rnodes.sort();
436 
        let opt =
437 
            |o: &Option<ObjectRef>| o.map(|r| Value::Bytes(r.0.to_vec())).unwrap_or(Value::Null);
438 
        let replaces = Value::Array(
439 
            rnodes
440 
                .into_iter()
441 
                .map(|n| {
442 
                    Value::Array(vec![
443 
                        Value::Bytes(n.0.to_vec()),
444 
                        Value::Array(
445 
                            self.replaces[n]
446 
                                .iter()
447 
                                .map(|(c, o, nw)| {
448 
                                    Value::Array(vec![Value::Bytes(c.0.to_vec()), opt(o), opt(nw)])
449 
                                })
450 
                                .collect(),
451 
                        ),
452 
                    ])
453 
                })
454 
                .collect(),
455 
        );
456 
        Value::map([
457 
            (0, Value::Uint(version)),
458 
            (1, changes),
459 
            (2, self.tree.to_value()),
460 
            (3, files),
461 
            (4, replaces),
462 
        ])
463 
    }
464
465 
    /// Decode a version 1 payload (the whole state in one value). A
466 
    /// version 2 payload needs its graph blobs: use [`State::from_checkpoint`].
467 
    pub fn from_checkpoint_payload(bytes: &[u8]) -> Result<State, ObjectError> {
468 
        State::from_checkpoint(bytes, |_| {
469 
            Err(ObjectError::Schema(
470 
                "a version 2 checkpoint needs its graph blobs".into(),
471 
            ))
472 
        })
473 
    }
474
475 
    /// Decode a checkpoint payload of either version (spec §11). For
476 
    /// version 2, `load` returns the contents of the named graph blobs, in
477 
    /// order; the graphs are then decoded in parallel.
478 
    pub fn from_checkpoint(
479 
        bytes: &[u8],
480 
        load: impl FnOnce(&[ObjectRef]) -> Result<Vec<Vec<u8>>, ObjectError>,
481 
    ) -> Result<State, ObjectError> {
482 
        use rayon::prelude::*;
483 
        let v = cbor::decode(bytes)?;
484 
        let m = o::map(&v, "checkpoint payload")?;
485 
        let version = o::uint(o::field(m, 0, "version")?, "version")?;
486 
        if version != o::FORMAT_VERSION && version != CHECKPOINT_INDEX_VERSION {
487 
            return Err(ObjectError::Schema(format!(
488 
                "checkpoint payload version {version} is not supported"
489 
            )));
490 
        }
491 
        let mut st = State::payload_common(m)?;
492 
        let entries = o::array(o::field(m, 3, "files")?, "files")?;
493 
        let mut parsed: Vec<(NodeId, &Value)> = Vec::with_capacity(entries.len());
494 
        for f in entries {
495 
            let e = o::array(f, "file")?;
496 
            if e.len() != 2 {
497 
                return Err(ObjectError::Schema("file: expected [node, graph]".into()));
498 
            }
499 
            let node = NodeId::from_slice(o::bytes(&e[0], "node")?)
500 
                .ok_or_else(|| ObjectError::Schema("node: expected 16 bytes".into()))?;
501 
            parsed.push((node, &e[1]));
502 
        }
503 
        // Version 2 names large graphs by blob: fetch those in one batch.
504 
        let mut fetched: HashMap<NodeId, Vec<u8>> = HashMap::new();
505 
        if version == CHECKPOINT_INDEX_VERSION {
506 
            let wanted: Vec<(NodeId, ObjectRef)> = parsed
507 
                .iter()
508 
                .filter(|(_, e)| matches!(e, Value::Bytes(_)))
509 
                .map(|(n, e)| Ok((*n, o::oref(e, "graph blob")?)))
510 
                .collect::<Result<_, ObjectError>>()?;
511 
            if !wanted.is_empty() {
512 
                let refs: Vec<ObjectRef> = wanted.iter().map(|(_, r)| *r).collect();
513 
                let contents = {
514 
                    let _t = crate::timing::phase("load:   graph blobs read");
515 
                    load(&refs)?
516 
                };
517 
                if contents.len() != refs.len() {
518 
                    return Err(ObjectError::Schema("graph blobs: wrong count".into()));
519 
                }
520 
                fetched.extend(wanted.iter().map(|(n, _)| *n).zip(contents));
521 
            }
522 
        } else if parsed.iter().any(|(_, e)| matches!(e, Value::Bytes(_))) {
523 
            return Err(ObjectError::Schema(
524 
                "a version 1 payload holds graphs inline".into(),
525 
            ));
526 
        }
527 
        // File graphs are independent; decode and build them in parallel.
528 
        let graphs = parsed
529 
            .par_iter()
530 
            .map(|(node, entry)| {
531 
                let graph = match fetched.get(node) {
532 
                    Some(bytes) => FileGraph::from_value(&cbor::decode(bytes)?)?,
533 
                    None => FileGraph::from_value(entry)?,
534 
                };
535 
                Ok((*node, graph))
536 
            })
537 
            .collect::<Result<Vec<_>, ObjectError>>()?;
538 
        st.files.extend(graphs);
539 
        Ok(st)
540 
    }
541
542 
    /// The graph blobs a payload names: empty for version 1.
543 
    pub fn checkpoint_graph_refs(bytes: &[u8]) -> Result<Vec<ObjectRef>, ObjectError> {
544 
        let v = cbor::decode(bytes)?;
545 
        let m = o::map(&v, "checkpoint payload")?;
546 
        let mut out = Vec::new();
547 
        for f in o::array(o::field(m, 3, "files")?, "files")? {
548 
            if let Some(entry @ Value::Bytes(_)) = o::array(f, "file")?.get(1) {
549 
                out.push(o::oref(entry, "graph blob")?);
550 
            }
551 
        }
552 
        Ok(out)
553 
    }
554
555 
    /// Decode a checkpoint payload for history only: a version 2 payload's
556 
    /// graphs are noted, not read or built, and come later through
557 
    /// [`State::load_graphs`]. A version 1 payload holds them inline and is
558 
    /// decoded in full.
559 
    pub fn from_checkpoint_history(bytes: &[u8]) -> Result<State, ObjectError> {
560 
        let v = cbor::decode(bytes)?;
561 
        let m = o::map(&v, "checkpoint payload")?;
562 
        let version = o::uint(o::field(m, 0, "version")?, "version")?;
563 
        if version != CHECKPOINT_INDEX_VERSION {
564 
            return State::from_checkpoint_payload(bytes);
565 
        }
566 
        let mut st = State::payload_common(m)?;
567 
        let mut deferred = HashMap::new();
568 
        for f in o::array(o::field(m, 3, "files")?, "files")? {
569 
            let e = o::array(f, "file")?;
570 
            if e.len() != 2 {
571 
                return Err(ObjectError::Schema("file: expected [node, graph]".into()));
572 
            }
573 
            let node = NodeId::from_slice(o::bytes(&e[0], "node")?)
574 
                .ok_or_else(|| ObjectError::Schema("node: expected 16 bytes".into()))?;
575 
            let base = match &e[1] {
576 
                Value::Bytes(_) => DeferredBase::Blob(o::oref(&e[1], "graph blob")?),
577 
                other => DeferredBase::Inline(other.clone()),
578 
            };
579 
            deferred.insert(
580 
                node,
581 
                Deferred {
582 
                    base: Some(base),
583 
                    edits: Vec::new(),
584 
                },
585 
            );
586 
        }
587 
        st.deferred = Some(deferred);
588 
        Ok(st)
589 
    }
590
591 
    /// Changes, tree and replaces of a payload of either version.
592 
    fn payload_common(m: &BTreeMap<u64, Value>) -> Result<State, ObjectError> {
593 
        let mut st = State::new();
594 
        for c in o::array(o::field(m, 1, "changes")?, "changes")? {
595 
            let e = o::array(c, "change meta")?;
596 
            if e.len() != 8 {
597 
                return Err(ObjectError::Schema("change meta: expected 8 fields".into()));
598 
            }
599 
            let hash = o::oref(&e[0], "hash")?;
600 
            let meta = ChangeMeta {
601 
                change_id: crate::ids::ChangeId::from_slice(o::bytes(&e[1], "change id")?)
602 
                    .ok_or_else(|| ObjectError::Schema("change id: expected 16 bytes".into()))?,
603 
                deps: o::array(&e[2], "deps")?
604 
                    .iter()
605 
                    .map(|d| o::oref(d, "dep"))
606 
                    .collect::<Result<Vec<_>, _>>()?,
607 
                message: o::text(&e[3], "message")?.to_owned(),
608 
                hlc: Hlc {
609 
                    wall_ms: o::uint(&e[4], "wall")?,
610 
                    logical: o::u32_(&e[5], "logical")?,
611 
                },
612 
                kind: ChangeKind::from_tag(o::uint(&e[6], "kind")?)?,
613 
                author: o::oref(&e[7], "author")?,
614 
            };
615 
            st.changes.insert(hash, meta);
616 
        }
617 
        st.tree = TreeGraph::from_value(o::field(m, 2, "tree")?)?;
618 
        let opt = |v: &Value| -> Result<Option<ObjectRef>, ObjectError> {
619 
            if v.is_null() {
620 
                Ok(None)
621 
            } else {
622 
                o::oref(v, "blob").map(Some)
623 
            }
624 
        };
625 
        for r in o::array(o::field(m, 4, "replaces")?, "replaces")? {
626 
            let e = o::array(r, "replace")?;
627 
            if e.len() != 2 {
628 
                return Err(ObjectError::Schema(
629 
                    "replace: expected [node, records]".into(),
630 
                ));
631 
            }
632 
            let node = NodeId::from_slice(o::bytes(&e[0], "node")?)
633 
                .ok_or_else(|| ObjectError::Schema("node: expected 16 bytes".into()))?;
634 
            let mut recs = Vec::new();
635 
            for rec in o::array(&e[1], "records")? {
636 
                let x = o::array(rec, "record")?;
637 
                if x.len() != 3 {
638 
                    return Err(ObjectError::Schema("record: expected 3 fields".into()));
639 
                }
640 
                recs.push((o::oref(&x[0], "change")?, opt(&x[1])?, opt(&x[2])?));
641 
            }
642 
            st.replaces.insert(node, recs);
643 
        }
644 
        Ok(st)
645 
    }
646
647 
    pub fn validate(&self) -> Result<(), StateError> {
648 
        for (h, c) in &self.changes {
649 
            for d in &c.deps {
650 
                if !self.changes.contains_key(d) {
651 
                    return Err(StateError::MissingDep(*d, *h));
652 
                }
653 
            }
654 
        }
655 
        Ok(())
656 
    }
657
658 
    fn apply(&mut self, h: ChangeHash, c: Change) {
659 
        for (i, op) in c.tree_ops.iter().enumerate() {
660 
            self.tree.apply(h, i as u32, &resolve_tree_op(op, h));
661 
        }
662 
        if let Some(deferred) = self.deferred.as_mut() {
663 
            // History only: edits of files not built wait, grouped per file.
664 
            let mut per_node: HashMap<NodeId, Vec<Edit>> = HashMap::new();
665 
            for e in c.edits {
666 
                match e {
667 
                    Edit::Replace { node, old, new } => {
668 
                        self.replaces.entry(node).or_default().push((h, old, new))
669 
                    }
670 
                    e => per_node.entry(e.node()).or_default().push(e),
671 
                }
672 
            }
673 
            for (node, edits) in per_node {
674 
                match self.files.get_mut(&node) {
675 
                    Some(g) => apply_file_edits(g, h, edits),
676 
                    None => deferred.entry(node).or_default().edits.push((h, edits)),
677 
                }
678 
            }
679 
            return;
680 
        }
681 
        let mut counters: HashMap<NodeId, u32> = HashMap::new();
682 
        for e in c.edits {
683 
            match e {
684 
                Edit::Insert {
685 
                    node,
686 
                    after,
687 
                    before,
688 
                    lines,
689 
                } => {
690 
                    let idx = counters.entry(node).or_default();
691 
                    let first = *idx;
692 
                    *idx += lines.len() as u32;
693 
                    self.files.entry(node).or_default().insert_owned(
694 
                        h,
695 
                        first,
696 
                        vertex(after.resolve(h)),
697 
                        vertex(before.resolve(h)),
698 
                        lines,
699 
                    );
700 
                }
701 
                Edit::Delete { node, atoms } => {
702 
                    let g = self.files.entry(node).or_default();
703 
                    for r in atoms {
704 
                        g.delete(h, &r.resolve(h));
705 
                    }
706 
                }
707 
                Edit::Replace { node, old, new } => {
708 
                    self.replaces.entry(node).or_default().push((h, old, new));
709 
                }
710 
            }
711 
        }
712 
    }
713
714 
    /// Transitive dependencies of `h`, excluding `h` itself.
715 
    pub fn closure(&self, h: &ChangeHash) -> Arc<HashSet<ChangeHash>> {
716 
        if let Some(c) = self.closure.lock().unwrap().get(h) {
717 
            return c.clone();
718 
        }
719 
        let mut out = HashSet::new();
720 
        let mut stack: Vec<ChangeHash> = self
721 
            .changes
722 
            .get(h)
723 
            .map(|c| c.deps.clone())
724 
            .unwrap_or_default();
725 
        while let Some(d) = stack.pop() {
726 
            if out.insert(d) {
727 
                if let Some(c) = self.changes.get(&d) {
728 
                    stack.extend(c.deps.iter().copied());
729 
                }
730 
            }
731 
        }
732 
        let rc = Arc::new(out);
733 
        self.closure.lock().unwrap().insert(*h, rc.clone());
734 
        rc
735 
    }
736
737 
    /// Changes that no other change depends on directly, sorted.
738 
    pub fn heads(&self) -> Vec<ChangeHash> {
739 
        let depended: HashSet<&ChangeHash> =
740 
            self.changes.values().flat_map(|c| c.deps.iter()).collect();
741 
        let mut heads: Vec<ChangeHash> = self
742 
            .changes
743 
            .keys()
744 
            .filter(|h| !depended.contains(h))
745 
            .copied()
746 
            .collect();
747 
        heads.sort();
748 
        heads
749 
    }
750
751 
    /// Maximal elements among `hashes` (those not in the closure of another),
752 
    /// sorted. One walk down from all of them at once: whatever the walk
753 
    /// reaches is below some other element. Linear in the changes reached,
754 
    /// where comparing every pair's closures was quadratic in the number
755 
    /// of heads, which a bookmark of independent changes has many of.
756 
    pub fn maximal(&self, hashes: &[ChangeHash]) -> Vec<ChangeHash> {
757 
        let set: BTreeSet<ChangeHash> = hashes.iter().copied().collect();
758 
        let mut below: HashSet<ChangeHash> = HashSet::new();
759 
        let mut stack: Vec<ChangeHash> = set
760 
            .iter()
761 
            .filter_map(|h| self.changes.get(h))
762 
            .flat_map(|c| c.deps.iter().copied())
763 
            .collect();
764 
        while let Some(d) = stack.pop() {
765 
            if below.insert(d) {
766 
                if let Some(c) = self.changes.get(&d) {
767 
                    stack.extend(c.deps.iter().copied());
768 
                }
769 
            }
770 
        }
771 
        set.into_iter().filter(|h| !below.contains(h)).collect()
772 
    }
773
774 
    pub fn materialize_file(&self, node: &NodeId) -> Materialized {
775 
        self.graph(node)
776 
            .map(|g| g.materialize(self))
777 
            .unwrap_or_default()
778 
    }
779
780 
    /// Live lines of a text node in materialized order.
781 
    pub fn live_lines(&self, node: &NodeId) -> Vec<(AtomKey, Vec<u8>)> {
782 
        let Some(g) = self.graph(node) else {
783 
            return vec![];
784 
        };
785 
        let m = g.materialize(self);
786 
        m.live_atoms()
787 
            .into_iter()
788 
            .map(|a| (a, g.content(&a).unwrap_or_default().to_vec()))
789 
            .collect()
790 
    }
791
792 
    /// Live blobs of an opaque node: every `new` that no later `Replace` retired.
793 
    pub fn live_blobs(&self, node: &NodeId) -> Vec<ObjectRef> {
794 
        let mut live: Vec<ObjectRef> = self
795 
            .live_replaces(node)
796 
            .into_iter()
797 
            .map(|(_, n)| n)
798 
            .collect();
799 
        live.sort();
800 
        live.dedup();
801 
        live
802 
    }
803
804 
    /// The replace records whose blob is live, with the change that set it
805 
    /// (spec §9.3). A record's blob is superseded by a later replacement of
806 
    /// that blob: one whose change depends on the record's change, as every
807 
    /// replacement depends on the change that made its old blob current
808 
    /// (§8.1). Two replacements that do not know each other both stay live
809 
    /// (a replace conflict), and a file reverted to an earlier blob keeps it.
810 
    /// A replacement without that dependency, from before the rule, is read
811 
    /// as before: it supersedes every record that did not come after it.
812 
    pub fn live_replaces(&self, node: &NodeId) -> Vec<(ChangeHash, ObjectRef)> {
813 
        let Some(rs) = self.replaces.get(node) else {
814 
            return vec![];
815 
        };
816 
        let knows_its_old = |s: &ChangeHash, old: &ObjectRef| {
817 
            rs.iter()
818 
                .any(|(q, _, n)| n.as_ref() == Some(old) && q != s && self.closure(s).contains(q))
819 
        };
820 
        rs.iter()
821 
            .filter_map(|(c, _, n)| n.map(|n| (*c, n)))
822 
            .filter(|(c, n)| {
823 
                !rs.iter().any(|(s, o, _)| {
824 
                    s != c
825 
                        && *o == Some(*n)
826 
                        && (self.closure(s).contains(c)
827 
                            || (!knows_its_old(s, n) && !self.closure(c).contains(s)))
828 
                })
829 
            })
830 
            .collect()
831 
    }
832
833 
    /// Short label for conflict markers: `changeid-prefix "message"`.
834 
    pub fn label(&self, h: &ChangeHash) -> String {
835 
        match self.changes.get(h) {
836 
            Some(c) => format!(
837 
                "{} \"{}\"",
838 
                c.change_id.short(8),
839 
                c.message.lines().next().unwrap_or("")
840 
            ),
841 
            None => format!("#{}", h.short(12)),
842 
        }
843 
    }
844
845 
    /// For resolving a conflicted text node (spec §9.6): the live atoms that
846 
    /// are not part of any conflict region in order, every live atom that is
847 
    /// part of a region, and every change that contributed to a region.
848 
    /// The changes that introduced the live blobs of an opaque node, for a
849 
    /// replace conflict (spec §9.3).
850 
    pub fn blob_contributors(&self, node: &NodeId, blobs: &[ObjectRef]) -> Vec<ChangeHash> {
851 
        let mut out: Vec<ChangeHash> = Vec::new();
852 
        for (h, _, new) in self.replaces.get(node).map(|v| v.as_slice()).unwrap_or(&[]) {
853 
            if new.is_some_and(|b| blobs.contains(&b)) && !out.contains(h) {
854 
                out.push(*h);
855 
            }
856 
        }
857 
        out.sort();
858 
        out
859 
    }
860
861 
    pub fn conflict_regions(&self, node: &NodeId) -> ConflictRegions {
862 
        let mut out = ConflictRegions::default();
863 
        let Some(g) = self.graph(node) else {
864 
            return out;
865 
        };
866 
        let m = g.materialize(self);
867 
        let mut contributors = BTreeSet::new();
868 
        for seg in &m.segments {
869 
            match seg {
870 
                crate::graph::Segment::Lines(atoms) => {
871 
                    for a in atoms {
872 
                        out.plain
873 
                            .push((*a, g.content(a).unwrap_or_default().to_vec()));
874 
                    }
875 
                }
876 
                crate::graph::Segment::Conflict(sides) => {
877 
                    for side in sides {
878 
                        for a in side {
879 
                            out.region_atoms.push(*a);
880 
                            contributors.insert(a.0);
881 
                        }
882 
                    }
883 
                }
884 
                crate::graph::Segment::Zombie { deleted, inserted } => {
885 
                    for a in deleted {
886 
                        contributors.insert(a.0);
887 
                        contributors.extend(g.deleters(a).copied());
888 
                    }
889 
                    for a in inserted {
890 
                        out.region_atoms.push(*a);
891 
                        contributors.insert(a.0);
892 
                    }
893 
                }
894 
            }
895 
        }
896 
        out.contributors = contributors.into_iter().collect();
897 
        out
898 
    }
899
900 
    pub fn render_file(&self, node: &NodeId) -> (Vec<u8>, Materialized) {
901 
        let Some(g) = self.graph(node) else {
902 
            return (Vec::new(), Materialized::default());
903 
        };
904 
        let m = g.materialize(self);
905 
        let bytes = g.render(&m, &|h| self.label(h));
906 
        (bytes, m)
907 
    }
908
909 
    /// Every file rendered, in parallel: files are independent, and
910 
    /// rendering them is most of a snapshot's cost in a large tree.
911 
    pub fn materialize(&self) -> Snapshot {
912 
        use rayon::prelude::*;
913 
        self.require_full("materializing a state");
914 
        let tree = self.tree.view();
915 
        let entries: Vec<(&String, &crate::tree::TreeEntry)> = tree.entries.iter().collect();
916 
        let rendered: Vec<(String, FileState)> = entries
917 
            .par_iter()
918 
            .map(|(path, e)| (path.to_string(), self.file_state(e)))
919 
            .collect();
920 
        let files: BTreeMap<String, FileState> = rendered.into_iter().collect();
921 
        Snapshot { tree, files }
922 
    }
923
924 
    fn file_state(&self, e: &crate::tree::TreeEntry) -> FileState {
925 
        {
926 
            let content = match e.kind {
927 
                NodeKind::Dir => FileContent::Dir,
928 
                NodeKind::Symlink | NodeKind::Subrepo => FileContent::Opaque {
929 
                    blobs: self.live_blobs(&e.node),
930 
                },
931 
                NodeKind::File if e.mode.opaque => FileContent::Opaque {
932 
                    blobs: self.live_blobs(&e.node),
933 
                },
934 
                NodeKind::File => {
935 
                    let (bytes, materialized) = self.render_file(&e.node);
936 
                    FileContent::Text {
937 
                        bytes,
938 
                        materialized,
939 
                    }
940 
                }
941 
            };
942 
            FileState {
943 
                node: e.node,
944 
                kind: e.kind,
945 
                mode: e.mode,
946 
                content,
947 
            }
948 
        }
949 
    }
950 
}
951
952 
impl DepOracle for State {
953 
    fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
954 
        a == b || self.closure(a).contains(b)
955 
    }
956 
}
957
958 
#[cfg(test)]
959 
mod tests {
960 
    use super::*;
961 
    use crate::ids::ChangeId;
962 
    use crate::objects::{AtomRange, ChangeKind, Hlc, OpRef};
963
964 
    fn change(deps: Vec<ChangeHash>, tree_ops: Vec<TreeOp>, edits: Vec<Edit>) -> Change {
965 
        let mut c = Change {
966 
            change_id: ChangeId::random(),
967 
            deps,
968 
            author: ObjectRef::ZERO,
969 
            hlc: Hlc {
970 
                wall_ms: 1,
971 
                logical: 0,
972 
            },
973 
            message: "m".into(),
974 
            tree_ops,
975 
            edits,
976 
            kind: ChangeKind::Normal,
977 
        };
978 
        c.normalize();
979 
        c
980 
    }
981
982 
    #[test]
983 
    fn build_edit_and_materialize() {
984 
        let mut st = State::new();
985 
        let f = NodeId::random();
986 
        let c1 = change(
987 
            vec![],
988 
            vec![TreeOp::AddNode {
989 
                node: f,
990 
                kind: NodeKind::File,
991 
                mode: Mode::TEXT,
992 
                parent: NodeId::ROOT,
993 
                name: "a.txt".into(),
994 
            }],
995 
            vec![Edit::Insert {
996 
                node: f,
997 
                after: AtomRef::Start,
998 
                before: AtomRef::End,
999 
                lines: vec![b"one\n".to_vec(), b"two\n".to_vec()],
1000 
            }],
1001 
        );
1002 
        let h1 = st.add(c1).unwrap();
1003 
        // Depends on h1: append a line and delete "one".
1004 
        let c2 = change(
1005 
            vec![h1],
1006 
            vec![],
1007 
            vec![
1008 
                Edit::Delete {
1009 
                    node: f,
1010 
                    atoms: vec![AtomRange {
1011 
                        change: h1,
1012 
                        from: 0,
1013 
                        to: 1,
1014 
                    }],
1015 
                },
1016 
                Edit::Insert {
1017 
                    node: f,
1018 
                    after: AtomRef::Atom {
1019 
                        change: h1,
1020 
                        index: 1,
1021 
                    },
1022 
                    before: AtomRef::End,
1023 
                    lines: vec![b"three\n".to_vec()],
1024 
                },
1025 
            ],
1026 
        );
1027 
        let h2 = st.add(c2).unwrap();
1028 
        assert_eq!(st.heads(), vec![h2]);
1029 
        assert!(st.depends_on(&h2, &h1));
1030 
        assert!(!st.depends_on(&h1, &h2));
1031 
        let snap = st.materialize();
1032 
        assert!(!snap.is_conflicted());
1033 
        let a = &snap.files["a.txt"];
1034 
        assert!(matches!(&a.content, FileContent::Text { bytes, .. } if bytes == b"two\nthree\n"));
1035 
        assert_eq!(st.live_lines(&f).len(), 2);
1036 
    }
1037
1038 
    #[test]
1039 
    fn missing_dependency_is_rejected() {
1040 
        let mut st = State::new();
1041 
        let c = change(vec![ObjectRef([1; 32])], vec![], vec![]);
1042 
        assert!(matches!(st.add(c), Err(StateError::MissingDep(..))));
1043 
    }
1044
1045 
    #[test]
1046 
    fn self_references_and_multi_insert_indexing() {
1047 
        let mut st = State::new();
1048 
        let f = NodeId::random();
1049 
        let me = OpRef {
1050 
            change: ObjectRef::ZERO,
1051 
            index: 0,
1052 
        };
1053 
        let c1 = change(
1054 
            vec![],
1055 
            vec![
1056 
                TreeOp::AddNode {
1057 
                    node: f,
1058 
                    kind: NodeKind::File,
1059 
                    mode: Mode::TEXT,
1060 
                    parent: NodeId::ROOT,
1061 
                    name: "x".into(),
1062 
                },
1063 
                TreeOp::SetMode {
1064 
                    node: f,
1065 
                    old: me,
1066 
                    mode: Mode {
1067 
                        exec: true,
1068 
                        opaque: false,
1069 
                    },
1070 
                },
1071 
            ],
1072 
            vec![
1073 
                Edit::Insert {
1074 
                    node: f,
1075 
                    after: AtomRef::Start,
1076 
                    before: AtomRef::End,
1077 
                    lines: vec![b"a\n".to_vec(), b"c\n".to_vec()],
1078 
                },
1079 
                // Insert between the two lines just inserted, using self references.
1080 
                Edit::Insert {
1081 
                    node: f,
1082 
                    after: AtomRef::Atom {
1083 
                        change: ObjectRef::ZERO,
1084 
                        index: 0,
1085 
                    },
1086 
                    before: AtomRef::Atom {
1087 
                        change: ObjectRef::ZERO,
1088 
                        index: 1,
1089 
                    },
1090 
                    lines: vec![b"b\n".to_vec()],
1091 
                },
1092 
            ],
1093 
        );
1094 
        st.add(c1).unwrap();
1095 
        let snap = st.materialize();
1096 
        let x = &snap.files["x"];
1097 
        assert_eq!(
1098 
            x.mode,
1099 
            Mode {
1100 
                exec: true,
1101 
                opaque: false
1102 
            }
1103 
        );
1104 
        assert!(matches!(&x.content, FileContent::Text { bytes, .. } if bytes == b"a\nb\nc\n"));
1105 
    }
1106
1107 
    #[test]
1108 
    fn opaque_replace_and_conflict() {
1109 
        let mut st = State::new();
1110 
        let f = NodeId::random();
1111 
        let b1 = ObjectRef([1; 32]);
1112 
        let b2 = ObjectRef([2; 32]);
1113 
        let b3 = ObjectRef([3; 32]);
1114 
        let h1 = st
1115 
            .add(change(
1116 
                vec![],
1117 
                vec![TreeOp::AddNode {
1118 
                    node: f,
1119 
                    kind: NodeKind::File,
1120 
                    mode: Mode::OPAQUE,
1121 
                    parent: NodeId::ROOT,
1122 
                    name: "img".into(),
1123 
                }],
1124 
                vec![Edit::Replace {
1125 
                    node: f,
1126 
                    old: None,
1127 
                    new: Some(b1),
1128 
                }],
1129 
            ))
1130 
            .unwrap();
1131 
        assert_eq!(st.live_blobs(&f), vec![b1]);
1132 
        st.add(change(
1133 
            vec![h1],
1134 
            vec![],
1135 
            vec![Edit::Replace {
1136 
                node: f,
1137 
                old: Some(b1),
1138 
                new: Some(b2),
1139 
            }],
1140 
        ))
1141 
        .unwrap();
1142 
        st.add(change(
1143 
            vec![h1],
1144 
            vec![],
1145 
            vec![Edit::Replace {
1146 
                node: f,
1147 
                old: Some(b1),
1148 
                new: Some(b3),
1149 
            }],
1150 
        ))
1151 
        .unwrap();
1152 
        let snap = st.materialize();
1153 
        assert!(snap.is_conflicted());
1154 
        assert!(
1155 
            matches!(&snap.files["img"].content, FileContent::Opaque { blobs } if blobs == &vec![b2, b3])
1156 
        );
1157 
    }
1158
1159 
    #[test]
1160 
    fn checkpoint_payload_round_trip_and_replay() {
1161 
        let mut st = State::new();
1162 
        let f = NodeId::random();
1163 
        let h1 = st
1164 
            .add(change(
1165 
                vec![],
1166 
                vec![TreeOp::AddNode {
1167 
                    node: f,
1168 
                    kind: NodeKind::File,
1169 
                    mode: Mode::TEXT,
1170 
                    parent: NodeId::ROOT,
1171 
                    name: "a".into(),
1172 
                }],
1173 
                vec![Edit::Insert {
1174 
                    node: f,
1175 
                    after: AtomRef::Start,
1176 
                    before: AtomRef::End,
1177 
                    lines: vec![b"1\n".to_vec(), b"2\n".to_vec()],
1178 
                }],
1179 
            ))
1180 
            .unwrap();
1181 
        let h2 = st
1182 
            .add(change(
1183 
                vec![h1],
1184 
                vec![],
1185 
                vec![Edit::Delete {
1186 
                    node: f,
1187 
                    atoms: vec![AtomRange {
1188 
                        change: h1,
1189 
                        from: 0,
1190 
                        to: 1,
1191 
                    }],
1192 
                }],
1193 
            ))
1194 
            .unwrap();
1195 
        let payload = st.checkpoint_payload();
1196 
        let back = State::from_checkpoint_payload(&payload).unwrap();
1197 
        assert_eq!(back.len(), 2);
1198 
        assert_eq!(back.heads(), vec![h2]);
1199 
        assert_eq!(back.get(&h1).unwrap().message, "m");
1200 
        assert_eq!(back.checkpoint_payload(), payload, "deterministic");
1201 
        // Replaying a further change onto the restored state equals a full build.
1202 
        let c3 = change(
1203 
            vec![h2],
1204 
            vec![],
1205 
            vec![Edit::Insert {
1206 
                node: f,
1207 
                after: AtomRef::Atom {
1208 
                    change: h1,
1209 
                    index: 1,
1210 
                },
1211 
                before: AtomRef::End,
1212 
                lines: vec![b"3\n".to_vec()],
1213 
            }],
1214 
        );
1215 
        let mut full = st.clone();
1216 
        full.add(c3.clone()).unwrap();
1217 
        let mut restored = back;
1218 
        restored.add(c3).unwrap();
1219 
        let (a, b) = (full.materialize(), restored.materialize());
1220 
        assert_eq!(
1221 
            a.files.keys().collect::<Vec<_>>(),
1222 
            b.files.keys().collect::<Vec<_>>()
1223 
        );
1224 
        assert_eq!(a.files["a"].content, b.files["a"].content);
1225 
        assert!(
1226 
            matches!(&b.files["a"].content, FileContent::Text { bytes, .. } if bytes == b"2\n3\n")
1227 
        );
1228 
        assert!(State::from_checkpoint_payload(b"nonsense").is_err());
1229 
    }
1230
1231 
    /// History-only states (O10f): the same state as a full load once its
1232 
    /// graphs are built, by replay and from a version 2 checkpoint with
1233 
    /// later changes; unloaded graphs are never read as empty.
1234 
    #[test]
1235 
    fn history_only_states_build_the_same_graphs_on_demand() {
1236 
        let small = NodeId::random();
1237 
        let big = NodeId::random();
1238 
        let add = |node: NodeId, name: &str| TreeOp::AddNode {
1239 
            node,
1240 
            kind: NodeKind::File,
1241 
            mode: Mode::TEXT,
1242 
            parent: NodeId::ROOT,
1243 
            name: name.into(),
1244 
        };
1245 
        let lines: Vec<Vec<u8>> = (0..300)
1246 
            .map(|i| format!("line {i}\n").into_bytes())
1247 
            .collect();
1248 
        let c1 = change(
1249 
            vec![],
1250 
            vec![add(small, "small"), add(big, "big")],
1251 
            vec![
1252 
                Edit::Insert {
1253 
                    node: small,
1254 
                    after: AtomRef::Start,
1255 
                    before: AtomRef::End,
1256 
                    lines: vec![b"x\n".to_vec()],
1257 
                },
1258 
                Edit::Insert {
1259 
                    node: big,
1260 
                    after: AtomRef::Start,
1261 
                    before: AtomRef::End,
1262 
                    lines,
1263 
                },
1264 
            ],
1265 
        );
1266 
        let h1 = c1.hash();
1267 
        let c2 = change(
1268 
            vec![h1],
1269 
            vec![],
1270 
            vec![
1271 
                Edit::Delete {
1272 
                    node: big,
1273 
                    atoms: vec![AtomRange {
1274 
                        change: h1,
1275 
                        from: 2,
1276 
                        to: 9,
1277 
                    }],
1278 
                },
1279 
                Edit::Insert {
1280 
                    node: big,
1281 
                    after: AtomRef::Atom {
1282 
                        change: h1,
1283 
                        index: 20,
1284 
                    },
1285 
                    before: AtomRef::Atom {
1286 
                        change: h1,
1287 
                        index: 21,
1288 
                    },
1289 
                    lines: vec![b"new a\n".to_vec(), b"new b\n".to_vec()],
1290 
                },
1291 
                Edit::Insert {
1292 
                    node: small,
1293 
                    after: AtomRef::Atom {
1294 
                        change: h1,
1295 
                        index: 0,
1296 
                    },
1297 
                    before: AtomRef::End,
1298 
                    lines: vec![b"y\n".to_vec()],
1299 
                },
1300 
            ],
1301 
        );
1302 
        let h2 = c2.hash();
1303 
        let c3 = change(
1304 
            vec![h2],
1305 
            vec![],
1306 
            vec![Edit::Delete {
1307 
                node: small,
1308 
                atoms: vec![AtomRange {
1309 
                    change: h1,
1310 
                    from: 0,
1311 
                    to: 1,
1312 
                }],
1313 
            }],
1314 
        );
1315
1316 
        let mut full = State::new();
1317 
        for c in [&c1, &c2, &c3] {
1318 
            full.add(c.clone()).unwrap();
1319 
        }
1320 
        // By replay: nothing built until asked, then exactly the full graphs.
1321 
        let mut hist = State::new_history_only();
1322 
        for c in [&c1, &c2, &c3] {
1323 
            hist.add(c.clone()).unwrap();
1324 
        }
1325 
        assert!(!hist.is_full() && hist.files.is_empty(), "no graph built");
1326 
        assert_eq!(hist.len(), 3);
1327 
        hist.load_graphs(&[big], |_| unreachable!("no checkpoint"))
1328 
            .unwrap();
1329 
        assert_eq!(
1330 
            hist.render_file(&big).0,
1331 
            full.render_file(&big).0,
1332 
            "one file on its own"
1333 
        );
1334 
        assert!(!hist.is_full());
1335 
        hist.load_graphs(&[small, big], |_| unreachable!()).unwrap();
1336 
        assert!(hist.is_full());
1337 
        assert_eq!(hist.checkpoint_payload(), full.checkpoint_payload());
1338
1339 
        // From a version 2 checkpoint of c1+c2, then c3 applied later.
1340 
        let mut base = State::new();
1341 
        base.add(c1.clone()).unwrap();
1342 
        base.add(c2.clone()).unwrap();
1343 
        let graphs = base.checkpoint_file_graphs();
1344 
        let mut blobs: HashMap<ObjectRef, Vec<u8>> = HashMap::new();
1345 
        let index = base.checkpoint_index(&graphs, |enc| {
1346 
            let r = crate::hash::hash_object(crate::hash::ObjectType::Blob, enc);
1347 
            blobs.insert(r, enc.to_vec());
1348 
            r
1349 
        });
1350 
        let mut from_cp = State::from_checkpoint_history(&index).unwrap();
1351 
        from_cp.add(c3.clone()).unwrap();
1352 
        assert!(!from_cp.is_full());
1353 
        let mut fetched = 0;
1354 
        from_cp
1355 
            .load_graphs(&[small, big], |refs| {
1356 
                fetched += refs.len();
1357 
                refs.iter()
1358 
                    .map(|r| {
1359 
                        blobs
1360 
                            .get(r)
1361 
                            .cloned()
1362 
                            .ok_or_else(|| ObjectError::Schema("missing".into()))
1363 
                    })
1364 
                    .collect()
1365 
            })
1366 
            .unwrap();
1367 
        assert_eq!(
1368 
            fetched, 1,
1369 
            "the large graph's blob, in one batch; the small one was inline"
1370 
        );
1371 
        assert_eq!(from_cp.checkpoint_payload(), full.checkpoint_payload());
1372 
    }
1373
1374 
    #[test]
1375 
    #[should_panic(expected = "was not loaded")]
1376 
    fn a_history_only_state_never_reads_an_unloaded_graph_as_empty() {
1377 
        let f = NodeId::random();
1378 
        let mut st = State::new_history_only();
1379 
        st.add(change(
1380 
            vec![],
1381 
            vec![TreeOp::AddNode {
1382 
                node: f,
1383 
                kind: NodeKind::File,
1384 
                mode: Mode::TEXT,
1385 
                parent: NodeId::ROOT,
1386 
                name: "a".into(),
1387 
            }],
1388 
            vec![Edit::Insert {
1389 
                node: f,
1390 
                after: AtomRef::Start,
1391 
                before: AtomRef::End,
1392 
                lines: vec![b"a\n".to_vec()],
1393 
            }],
1394 
        ))
1395 
        .unwrap();
1396 
        st.render_file(&f);
1397 
    }
1398
1399 
    #[test]
1400 
    #[should_panic(expected = "needs every file graph")]
1401 
    fn materializing_a_history_only_state_is_refused() {
1402 
        let f = NodeId::random();
1403 
        let mut st = State::new_history_only();
1404 
        st.add(change(
1405 
            vec![],
1406 
            vec![TreeOp::AddNode {
1407 
                node: f,
1408 
                kind: NodeKind::File,
1409 
                mode: Mode::TEXT,
1410 
                parent: NodeId::ROOT,
1411 
                name: "a".into(),
1412 
            }],
1413 
            vec![Edit::Insert {
1414 
                node: f,
1415 
                after: AtomRef::Start,
1416 
                before: AtomRef::End,
1417 
                lines: vec![b"a\n".to_vec()],
1418 
            }],
1419 
        ))
1420 
        .unwrap();
1421 
        st.materialize();
1422 
    }
1423
1424 
    /// Version 2 payloads (spec §11): small graphs inline, large ones by
1425 
    /// blob; the state read back is the same as from version 1.
1426 
    #[test]
1427 
    fn checkpoint_index_round_trip_matches_version_1() {
1428 
        let mut st = State::new();
1429 
        let small = NodeId::random();
1430 
        let big = NodeId::random();
1431 
        let add = |node: NodeId, name: &str| TreeOp::AddNode {
1432 
            node,
1433 
            kind: NodeKind::File,
1434 
            mode: Mode::TEXT,
1435 
            parent: NodeId::ROOT,
1436 
            name: name.into(),
1437 
        };
1438 
        let big_lines: Vec<Vec<u8>> = (0..400)
1439 
            .map(|i| format!("line {i} of a long file\n").into_bytes())
1440 
            .collect();
1441 
        let h1 = st
1442 
            .add(change(
1443 
                vec![],
1444 
                vec![add(small, "small"), add(big, "big")],
1445 
                vec![
1446 
                    Edit::Insert {
1447 
                        node: small,
1448 
                        after: AtomRef::Start,
1449 
                        before: AtomRef::End,
1450 
                        lines: vec![b"x\n".to_vec()],
1451 
                    },
1452 
                    Edit::Insert {
1453 
                        node: big,
1454 
                        after: AtomRef::Start,
1455 
                        before: AtomRef::End,
1456 
                        lines: big_lines,
1457 
                    },
1458 
                ],
1459 
            ))
1460 
            .unwrap();
1461 
        st.add(change(
1462 
            vec![h1],
1463 
            vec![],
1464 
            vec![Edit::Delete {
1465 
                node: big,
1466 
                atoms: vec![AtomRange {
1467 
                    change: h1,
1468 
                    from: 3,
1469 
                    to: 7,
1470 
                }],
1471 
            }],
1472 
        ))
1473 
        .unwrap();
1474
1475 
        let graphs = st.checkpoint_file_graphs();
1476 
        let mut blobs: HashMap<ObjectRef, Vec<u8>> = HashMap::new();
1477 
        let index = st.checkpoint_index(&graphs, |enc| {
1478 
            let r = crate::hash::hash_object(crate::hash::ObjectType::Blob, enc);
1479 
            blobs.insert(r, enc.to_vec());
1480 
            r
1481 
        });
1482 
        assert_eq!(blobs.len(), 1, "only the large graph is a blob of its own");
1483 
        assert_eq!(
1484 
            State::checkpoint_graph_refs(&index).unwrap(),
1485 
            blobs.keys().copied().collect::<Vec<_>>()
1486 
        );
1487 
        assert!(
1488 
            State::checkpoint_graph_refs(&st.checkpoint_payload())
1489 
                .unwrap()
1490 
                .is_empty(),
1491 
            "version 1 names none"
1492 
        );
1493 
        assert!(index.len() < st.checkpoint_payload().len());
1494
1495 
        let back = State::from_checkpoint(&index, |refs| {
1496 
            refs.iter()
1497 
                .map(|r| {
1498 
                    blobs
1499 
                        .get(r)
1500 
                        .cloned()
1501 
                        .ok_or_else(|| ObjectError::Schema("missing".into()))
1502 
                })
1503 
                .collect()
1504 
        })
1505 
        .unwrap();
1506 
        assert_eq!(
1507 
            back.checkpoint_payload(),
1508 
            st.checkpoint_payload(),
1509 
            "the same state as version 1"
1510 
        );
1511 
        assert_eq!(
1512 
            back.materialize().files["big"].content,
1513 
            st.materialize().files["big"].content
1514 
        );
1515 
        // Deterministic: the same state gives the same index.
1516 
        assert_eq!(
1517 
            back.checkpoint_index(&back.checkpoint_file_graphs(), |enc| {
1518 
                crate::hash::hash_object(crate::hash::ObjectType::Blob, enc)
1519 
            }),
1520 
            index
1521 
        );
1522 
        // A missing graph blob is an error, not an empty file.
1523 
        assert!(
1524 
            State::from_checkpoint(&index, |_| Err(ObjectError::Schema("gone".into()))).is_err()
1525 
        );
1526 
        assert!(
1527 
            State::from_checkpoint_payload(&index).is_err(),
1528 
            "version 2 needs its blobs"
1529 
        );
1530 
        // Version 1 payloads still read, and unknown versions do not.
1531 
        assert!(State::from_checkpoint(&st.checkpoint_payload(), |_| unreachable!()).is_ok());
1532 
        let mut v3 = cbor::decode(&index).unwrap();
1533 
        if let Value::Map(m) = &mut v3 {
1534 
            m.insert(0, Value::Uint(3));
1535 
        }
1536 
        assert!(State::from_checkpoint(&cbor::encode(&v3), |_| unreachable!()).is_err());
1537 
    }
1538
1539 
    #[test]
1540 
    fn maximal_elements() {
1541 
        let mut st = State::new();
1542 
        let h1 = st.add(change(vec![], vec![], vec![])).unwrap();
1543 
        let h2 = st.add(change(vec![h1], vec![], vec![])).unwrap();
1544 
        let h3 = st.add(change(vec![], vec![], vec![])).unwrap();
1545 
        let mut m = st.maximal(&[h1, h2, h3]);
1546 
        m.sort();
1547 
        let mut want = vec![h2, h3];
1548 
        want.sort();
1549 
        assert_eq!(m, want);
1550 
        assert_eq!(st.heads(), want);
1551 
    }
1552
1553 
    /// The one-walk `maximal` agrees with the definition (not in the
1554 
    /// closure of another element) on random graphs, with repeated and
1555 
    /// unknown hashes among the input.
1556 
    #[test]
1557 
    fn maximal_matches_its_definition() {
1558 
        use rand::{Rng, SeedableRng};
1559 
        let mut rng = rand::rngs::StdRng::seed_from_u64(7);
1560 
        for _ in 0..20 {
1561 
            let mut st = State::new();
1562 
            let mut all: Vec<ChangeHash> = Vec::new();
1563 
            for _ in 0..60 {
1564 
                let deps: Vec<ChangeHash> =
1565 
                    all.iter().copied().filter(|_| rng.gen_bool(0.05)).collect();
1566 
                all.push(st.add(change(deps, vec![], vec![])).unwrap());
1567 
            }
1568 
            let mut pick: Vec<ChangeHash> =
1569 
                all.iter().copied().filter(|_| rng.gen_bool(0.4)).collect();
1570 
            pick.extend(pick.clone().into_iter().take(3));
1571 
            pick.push(ObjectRef([0xee; 32]));
1572 
            let set: BTreeSet<ChangeHash> = pick.iter().copied().collect();
1573 
            let want: Vec<ChangeHash> = set
1574 
                .iter()
1575 
                .filter(|h| !set.iter().any(|o| o != *h && st.closure(o).contains(h)))
1576 
                .copied()
1577 
                .collect();
1578 
            assert_eq!(st.maximal(&pick), want);
1579 
            assert_eq!(st.maximal(&all), st.heads());
1580 
        }
1581 
    }
1582 
}