OXYGENHUB
# 4f264d6f20b6 oxygen / crates / oxy-core / src / state.rs
91.6 KiB · Rust · last changed Diff renders only the edited files and skips freeing at exit (refs #41) 1 month ago source blame history raw
ff0af1ee unknown 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
75167672 Andy McCall 4 
use crate::cbor::{self, Value};
ff0af1ee unknown 5 
use crate::graph::{AtomKey, DepOracle, FileGraph, Materialized, Vertex};
75167672 Andy McCall 6 
use crate::hash::KeyId;
ff0af1ee unknown 7 
use crate::hash::{ChangeHash, ObjectRef};
8 
use crate::ids::NodeId;
75167672 Andy McCall 9 
use crate::objects::{
10 
    self as o, AtomRef, Change, ChangeKind, Edit, Hlc, Mode, NodeKind, ObjectError, TreeOp,
11 
};
ff0af1ee unknown 12 
use crate::tree::{TreeGraph, TreeView};
9d333fc9 Andy McCall ↶ 13 
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
119bbf50 Andy McCall ↶ 14 
use std::sync::{Arc, Mutex};
ff0af1ee unknown 15
afaba5f1 Andy McCall ↶ 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
ff0af1ee unknown 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
55e5a16a unknown ↶ 28 
/// One `Replace` edit: `(change, old blob, new blob)`.
29 
type ReplaceRecord = (ChangeHash, Option<ObjectRef>, Option<ObjectRef>);
30
252e8cb2 Andy McCall ↶ 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 {
ce14f0d6 Andy McCall ↶ 44 
    /// In the flat layout of local indexes and caches ([`crate::flat`]).
45 
    pub(crate) fn write_flat(&self, w: &mut crate::flat::Writer) {
46 
        w.fixed(&self.change_id.0);
47 
        w.count(self.deps.len());
48 
        for d in &self.deps {
49 
            w.object(d);
50 
        }
51 
        w.object(&self.author);
52 
        w.u64(self.hlc.wall_ms);
53 
        w.u32(self.hlc.logical);
54 
        w.bytes(self.message.as_bytes());
55 
        w.u8(self.kind.tag() as u8);
56 
    }
57
58 
    pub(crate) fn read_flat(r: &mut crate::flat::Reader) -> Result<ChangeMeta, ObjectError> {
59 
        let change_id = crate::ids::ChangeId(r.fixed::<16>()?);
60 
        let mut deps = Vec::new();
61 
        for _ in 0..r.count()? {
62 
            deps.push(r.object()?);
63 
        }
64 
        Ok(ChangeMeta {
65 
            change_id,
66 
            deps,
67 
            author: r.object()?,
68 
            hlc: Hlc {
69 
                wall_ms: r.u64()?,
70 
                logical: r.u32()?,
71 
            },
72 
            message: r.text()?,
73 
            kind: ChangeKind::from_tag(r.u8()? as u64)?,
74 
        })
75 
    }
76
252e8cb2 Andy McCall ↶ 77 
    pub fn of(c: &Change) -> ChangeMeta {
75167672 Andy McCall 78 
        ChangeMeta {
79 
            change_id: c.change_id,
80 
            deps: c.deps.clone(),
81 
            author: c.author,
82 
            hlc: c.hlc,
83 
            message: c.message.clone(),
84 
            kind: c.kind,
85 
        }
252e8cb2 Andy McCall ↶ 86 
    }
87 
}
88
119bbf50 Andy McCall ↶ 89 
#[derive(Default)]
ff0af1ee unknown 90 
pub struct State {
f6451fbb Andy McCall ↶ 91 
    /// Shared between clones, like `files` and `deferred`: a state kept
92 
    /// beside another that differs by a few changes shares the rest.
93 
    changes: HashMap<ChangeHash, Arc<ChangeMeta>>,
ff0af1ee unknown 94 
    tree: TreeGraph,
dfb23a3a Andy McCall ↶ 95 
    /// Shared between clones: a clone copies a graph only when an edit
96 
    /// changes it (`Arc::make_mut`), so keeping several states that differ
97 
    /// by a few changes costs little more than one.
36e51aa8 Andy McCall ↶ 98 
    files: crate::fasthash::FastMap<NodeId, Arc<FileGraph>>,
55e5a16a unknown ↶ 99 
    replaces: HashMap<NodeId, Vec<ReplaceRecord>>,
119bbf50 Andy McCall ↶ 100 
    /// Memoised transitive dependencies. A mutex, not a `RefCell`, so a
101 
    /// loaded state can be shared across threads by a host that caches it.
102 
    closure: Mutex<HashMap<ChangeHash, Arc<HashSet<ChangeHash>>>>,
e8d38e47 Andy McCall ↶ 103 
    /// `None` for a full state. For a history-only state (loaded for its
104 
    /// changes and tree), the file graphs not built yet, by node: `files`
105 
    /// holds only those loaded with [`State::load_graphs`].
36e51aa8 Andy McCall ↶ 106 
    deferred: Option<crate::fasthash::FastMap<NodeId, Arc<Deferred>>>,
ff0af1ee unknown 107 
}
108
a4fad5b0 Andy McCall ↶ 109 
use crate::objects::TextRef;
86e1824f Andy McCall ↶ 110
e8d38e47 Andy McCall ↶ 111 
/// A file graph a history-only state has not built: its base from a
112 
/// version 2 checkpoint, if any, and the edits of later changes in the
113 
/// order they were applied (spec §11). Building it later gives the same
114 
/// graph, since graph construction does not depend on order (§8).
3f1b8fe2 Andy McCall ↶ 115 
///
116 
/// Read from a state index, it stays encoded until first used: a command
117 
/// that builds a few files decodes only their histories.
e8d38e47 Andy McCall ↶ 118 
#[derive(Clone, Default)]
119 
struct Deferred {
3f1b8fe2 Andy McCall ↶ 120 
    body: std::sync::OnceLock<DeferredBody>,
121 
    /// The body as the index encodes it, decoded into `body` on first use.
122 
    raw: Option<(Arc<[u8]>, std::ops::Range<usize>)>,
123 
    /// Its graph key, once worked out (or read from an index); reset by
124 
    /// any edit added.
125 
    key: std::sync::OnceLock<[u8; 32]>,
126 
}
127
128 
#[derive(Clone, Default)]
129 
struct DeferredBody {
e8d38e47 Andy McCall ↶ 130 
    base: Option<DeferredBase>,
131 
    edits: Vec<(ChangeHash, Vec<Edit>)>,
86e1824f Andy McCall ↶ 132 
    /// The text blob and line count of each insert in `edits` left without
133 
    /// its lines, in order: read when the graph is built.
a4fad5b0 Andy McCall ↶ 134 
    texts: Vec<TextRef>,
3f1b8fe2 Andy McCall ↶ 135 
}
136
137 
impl Deferred {
138 
    fn from_body(body: DeferredBody) -> Deferred {
139 
        Deferred {
140 
            body: std::sync::OnceLock::from(body),
141 
            ..Deferred::default()
142 
        }
143 
    }
144
145 
    fn body(&self) -> &DeferredBody {
146 
        self.body.get_or_init(|| match &self.raw {
147 
            // The index was checked against its hash when read, and was
148 
            // written by `write_index`: it decodes.
149 
            Some((bytes, range)) => State::read_deferred_body(&bytes[range.clone()])
150 
                .expect("a state index checked by its hash decodes"),
151 
            None => DeferredBody::default(),
152 
        })
153 
    }
154
155 
    fn body_mut(&mut self) -> &mut DeferredBody {
156 
        self.body();
157 
        self.raw = None;
158 
        self.body.get_mut().expect("decoded above")
159 
    }
160
161 
    fn into_body(mut self) -> DeferredBody {
162 
        self.body();
163 
        self.body.take().expect("decoded above")
164 
    }
e8d38e47 Andy McCall ↶ 165 
}
166
167 
#[derive(Clone)]
168 
enum DeferredBase {
169 
    Inline(Value),
170 
    Blob(ObjectRef),
f9575918 Andy McCall ↶ 171 
}
172
173 
/// A local index of a history-only state (oxygen#41), in the flat layout
174 
/// of [`crate::flat`]: its change metadata, tree (with its view), replace
175 
/// records and every file's deferred history with its graph key, so a
176 
/// command reads it rather than replaying history. Derived only: written
177 
/// from a state loaded the long way, and read back as the same state.
178 
impl State {
4cce912a Andy McCall ↶ 179 
    const INDEX_MAGIC: &'static [u8] = b"oxy state index 3\n";
f9575918 Andy McCall ↶ 180
181 
    /// The index of this state, or `None` when it has anything an index
182 
    /// does not hold: a built graph, or text in memory (a change added
183 
    /// whole rather than as its skeleton).
184 
    pub fn write_index(&self) -> Option<Vec<u8>> {
185 
        use crate::flat::Writer;
186 
        let deferred = self.deferred.as_ref()?;
187 
        if !self.files.is_empty() {
188 
            return None;
189 
        }
190 
        let atom = |w: &mut Writer, a: &AtomRef| match a {
191 
            AtomRef::Start => w.u8(0),
192 
            AtomRef::End => w.u8(1),
193 
            AtomRef::Atom { change, index } => {
194 
                w.u8(2);
195 
                w.object(change);
196 
                w.u32(*index);
197 
            }
198 
        };
4cce912a Andy McCall ↶ 199 
        // The changes first, as a block a reader can take on its own (see
200 
        // [`State::read_index_changes`]).
f9575918 Andy McCall ↶ 201 
        let mut w = Writer::default();
202 
        w.fixed(Self::INDEX_MAGIC);
203 
        let mut changes: Vec<(&ChangeHash, &Arc<ChangeMeta>)> = self.changes.iter().collect();
204 
        changes.sort_by_key(|(h, _)| **h);
205 
        w.count(changes.len());
206 
        for (h, m) in changes {
207 
            w.object(h);
ce14f0d6 Andy McCall ↶ 208 
            m.write_flat(&mut w);
f9575918 Andy McCall ↶ 209 
        }
4cce912a Andy McCall ↶ 210 
        let changes_block = std::mem::take(&mut w);
211 
        w.bytes(&changes_block.0);
f9575918 Andy McCall ↶ 212 
        // The tree and the files' histories as blocks of their own, so a
213 
        // reader decodes them side by side.
214 
        let mut tw = Writer::default();
215 
        self.tree.write_flat(&mut tw);
216 
        w.bytes(&tw.0);
217 
        let mut replaces: Vec<(&NodeId, &Vec<ReplaceRecord>)> = self.replaces.iter().collect();
218 
        replaces.sort_by_key(|(n, _)| **n);
219 
        w.count(replaces.len());
220 
        for (n, recs) in replaces {
221 
            w.fixed(&n.0);
222 
            w.count(recs.len());
223 
            // In any order: which record is live does not depend on it.
224 
            let mut recs: Vec<&ReplaceRecord> = recs.iter().collect();
225 
            recs.sort();
226 
            for (c, old, new) in recs {
227 
                w.object(c);
228 
                w.opt_object(old);
229 
                w.opt_object(new);
230 
            }
231 
        }
232 
        let outer = w;
233 
        let mut w = Writer::default();
234 
        let mut nodes: Vec<(&NodeId, &Arc<Deferred>)> = deferred.iter().collect();
235 
        nodes.sort_by_key(|(n, _)| **n);
236 
        w.count(nodes.len());
237 
        for (n, d) in nodes {
238 
            w.fixed(&n.0);
3f1b8fe2 Andy McCall ↶ 239 
            let mut h = blake3::Hasher::new();
240 
            h.update(b"oxy graph key 1\0");
241 
            h.update(&n.0);
242 
            w.fixed(d.key.get_or_init(|| d.graph_key(h)));
243 
            // Unchanged since read (a change clears `raw`): copied as it is.
244 
            if let Some((bytes, range)) = &d.raw {
245 
                w.bytes(&bytes[range.clone()]);
246 
                continue;
247 
            }
248 
            let d = d.body();
249 
            let outer_w = std::mem::take(&mut w);
f9575918 Andy McCall ↶ 250 
            match &d.base {
251 
                None => w.u8(0),
252 
                Some(DeferredBase::Blob(r)) => {
253 
                    w.u8(1);
254 
                    w.object(r);
255 
                }
256 
                Some(DeferredBase::Inline(v)) => {
257 
                    w.u8(2);
258 
                    w.bytes(&cbor::encode(v));
259 
                }
260 
            }
261 
            // Each change's edits with the texts of its inserts, sorted by
262 
            // change: a graph does not depend on the order changes applied
263 
            // in, and the index is then the same however history was read.
264 
            let mut texts = d.texts.iter();
265 
            let mut per_change: Vec<(&ChangeHash, &Vec<Edit>, Vec<&TextRef>)> = Vec::new();
266 
            for (c, edits) in &d.edits {
267 
                let n = edits
268 
                    .iter()
269 
                    .filter(|e| matches!(e, Edit::Insert { lines, .. } if lines.is_empty()))
270 
                    .count();
271 
                per_change.push((c, edits, texts.by_ref().take(n).collect()));
272 
            }
273 
            per_change.sort_by_key(|(c, _, _)| **c);
274 
            w.count(per_change.len());
275 
            for (c, edits, _) in &per_change {
276 
                w.object(c);
277 
                w.count(edits.len());
278 
                for e in edits.iter() {
279 
                    match e {
280 
                        Edit::Insert {
281 
                            node,
282 
                            after,
283 
                            before,
284 
                            lines,
285 
                        } => {
286 
                            if !lines.is_empty() {
287 
                                return None;
288 
                            }
289 
                            w.u8(0);
290 
                            w.fixed(&node.0);
291 
                            atom(&mut w, after);
292 
                            atom(&mut w, before);
293 
                        }
294 
                        Edit::Delete { node, atoms } => {
295 
                            w.u8(1);
296 
                            w.fixed(&node.0);
297 
                            w.count(atoms.len());
298 
                            for r in atoms {
299 
                                w.object(&r.change);
300 
                                w.u32(r.from);
301 
                                w.u32(r.to);
302 
                            }
303 
                        }
304 
                        Edit::Replace { .. } => return None,
305 
                    }
306 
                }
307 
            }
308 
            let texts: Vec<&TextRef> = per_change
309 
                .iter()
310 
                .flat_map(|(_, _, t)| t.iter().copied())
311 
                .collect();
312 
            w.count(texts.len());
313 
            for t in texts {
314 
                match t {
315 
                    TextRef::Blob(r, count, form) => {
316 
                        w.u8(0);
317 
                        w.object(r);
318 
                        w.u32(*count);
319 
                        w.u8(match form {
320 
                            crate::objects::TextForm::Cbor => 0,
321 
                            crate::objects::TextForm::Raw => 1,
322 
                            crate::objects::TextForm::CborFallback => 2,
323 
                        });
324 
                    }
325 
                    TextRef::Inline { change, start, end } => {
326 
                        w.u8(1);
327 
                        w.object(change);
328 
                        w.u32(*start);
329 
                        w.u32(*end);
330 
                    }
331 
                }
332 
            }
3f1b8fe2 Andy McCall ↶ 333 
            let body = std::mem::replace(&mut w, outer_w);
334 
            w.bytes(&body.0);
f9575918 Andy McCall ↶ 335 
        }
336 
        let mut outer = outer;
337 
        outer.bytes(&w.0);
338 
        Some(outer.0)
339 
    }
340
341 
    /// The state an index holds (see [`State::write_index`]).
342 
    pub fn read_index(bytes: &[u8]) -> Result<State, ObjectError> {
343 
        use crate::flat::Reader;
344 
        let bad = |what: &str| ObjectError::Schema(format!("state index: {what}"));
345 
        let mut r = Reader::new(bytes);
4cce912a Andy McCall ↶ 346 
        let mut st = State::new_history_only();
347 
        {
348 
            let _t = crate::timing::phase("index: changes");
349 
            st.changes = Self::read_index_changes(r.bytes()?)?;
350 
        }
351 
        let tree_bytes = r.bytes()?;
352 
        for _ in 0..r.count()? {
353 
            let n = NodeId(r.fixed::<16>()?);
354 
            let mut recs = Vec::new();
355 
            for _ in 0..r.count()? {
356 
                recs.push((r.object()?, r.opt_object()?, r.opt_object()?));
357 
            }
358 
            st.replaces.insert(n, recs);
359 
        }
360 
        let deferred_bytes = r.bytes()?;
361 
        if !r.at_end() {
362 
            return Err(bad("trailing bytes"));
363 
        }
364 
        let (tree, deferred) = rayon::join(
365 
            || TreeGraph::read_flat(&mut Reader::new(tree_bytes)),
366 
            || Self::read_deferred(deferred_bytes),
367 
        );
368 
        st.tree = tree?;
369 
        st.deferred = Some(deferred?);
370 
        Ok(st)
371 
    }
372
373 
    /// The changes of a state index: its first block, which a reader can
374 
    /// take without the rest (the log needs no more).
375 
    pub fn read_index_changes(
376 
        bytes: &[u8],
377 
    ) -> Result<HashMap<ChangeHash, Arc<ChangeMeta>>, ObjectError> {
378 
        use crate::flat::Reader;
379 
        let mut r = Reader::new(bytes);
f9575918 Andy McCall ↶ 380 
        if r.fixed::<18>()?.as_slice() != Self::INDEX_MAGIC {
4cce912a Andy McCall ↶ 381 
            return Err(ObjectError::Schema("state index: not a state index".into()));
f9575918 Andy McCall ↶ 382 
        }
383 
        let n = r.count()?;
4cce912a Andy McCall ↶ 384 
        let mut changes = HashMap::with_capacity(n);
f9575918 Andy McCall ↶ 385 
        for _ in 0..n {
386 
            let h = r.object()?;
ce14f0d6 Andy McCall ↶ 387 
            changes.insert(h, Arc::new(ChangeMeta::read_flat(&mut r)?));
f9575918 Andy McCall ↶ 388 
        }
389 
        if !r.at_end() {
4cce912a Andy McCall ↶ 390 
            return Err(ObjectError::Schema("state index: trailing bytes".into()));
f9575918 Andy McCall ↶ 391 
        }
4cce912a Andy McCall ↶ 392 
        Ok(changes)
f9575918 Andy McCall ↶ 393 
    }
394
3f1b8fe2 Andy McCall ↶ 395 
    /// The deferred block: each node with its graph key and its body,
396 
    /// left encoded (see [`Deferred`]).
36e51aa8 Andy McCall ↶ 397 
    fn read_deferred(
398 
        bytes: &[u8],
399 
    ) -> Result<crate::fasthash::FastMap<NodeId, Arc<Deferred>>, ObjectError> {
f9575918 Andy McCall ↶ 400 
        use crate::flat::Reader;
401 
        let _t = crate::timing::phase("index: deferred");
3f1b8fe2 Andy McCall ↶ 402 
        let all: Arc<[u8]> = Arc::from(bytes);
403 
        let mut r = Reader::new(bytes);
36e51aa8 Andy McCall ↶ 404 
        let mut deferred = crate::fasthash::FastMap::default();
3f1b8fe2 Andy McCall ↶ 405 
        let n = r.count()?;
406 
        deferred.reserve(n);
407 
        for _ in 0..n {
408 
            let id = NodeId(r.fixed::<16>()?);
409 
            let key = r.fixed::<32>()?;
410 
            let body = r.bytes()?;
411 
            let start = body.as_ptr() as usize - bytes.as_ptr() as usize;
412 
            let d = Deferred {
413 
                raw: Some((all.clone(), start..start + body.len())),
414 
                key: std::sync::OnceLock::from(key),
415 
                ..Deferred::default()
416 
            };
417 
            deferred.insert(id, Arc::new(d));
418 
        }
419 
        if !r.at_end() {
420 
            return Err(ObjectError::Schema("state index: trailing bytes".into()));
421 
        }
422 
        Ok(deferred)
423 
    }
424
425 
    /// One node's deferred history as the index encodes it.
426 
    fn read_deferred_body(bytes: &[u8]) -> Result<DeferredBody, ObjectError> {
427 
        use crate::flat::Reader;
f9575918 Andy McCall ↶ 428 
        let bad = |what: &str| ObjectError::Schema(format!("state index: {what}"));
429 
        let node = |r: &mut Reader| -> Result<NodeId, ObjectError> { Ok(NodeId(r.fixed::<16>()?)) };
430 
        let atom = |r: &mut Reader| -> Result<AtomRef, ObjectError> {
431 
            Ok(match r.u8()? {
432 
                0 => AtomRef::Start,
433 
                1 => AtomRef::End,
434 
                2 => AtomRef::Atom {
435 
                    change: r.object()?,
436 
                    index: r.u32()?,
437 
                },
438 
                _ => return Err(bad("atom")),
439 
            })
440 
        };
441 
        let mut r = Reader::new(bytes);
3f1b8fe2 Andy McCall ↶ 442 
        let base = match r.u8()? {
443 
            0 => None,
444 
            1 => Some(DeferredBase::Blob(r.object()?)),
445 
            _ => Some(DeferredBase::Inline(cbor::decode(r.bytes()?)?)),
446 
        };
447 
        let mut edits = Vec::new();
448 
        for _ in 0..r.count()? {
449 
            let c = r.object()?;
450 
            let mut es = Vec::new();
f9575918 Andy McCall ↶ 451 
            for _ in 0..r.count()? {
3f1b8fe2 Andy McCall ↶ 452 
                es.push(match r.u8()? {
453 
                    0 => Edit::Insert {
454 
                        node: node(&mut r)?,
455 
                        after: atom(&mut r)?,
456 
                        before: atom(&mut r)?,
457 
                        lines: crate::lines::Lines::default(),
f9575918 Andy McCall ↶ 458 
                    },
3f1b8fe2 Andy McCall ↶ 459 
                    1 => {
460 
                        let node = node(&mut r)?;
461 
                        let mut atoms = Vec::new();
462 
                        for _ in 0..r.count()? {
463 
                            atoms.push(crate::objects::AtomRange {
464 
                                change: r.object()?,
465 
                                from: r.u32()?,
466 
                                to: r.u32()?,
467 
                            });
468 
                        }
469 
                        Edit::Delete { node, atoms }
470 
                    }
471 
                    _ => return Err(bad("edit")),
f9575918 Andy McCall ↶ 472 
                });
473 
            }
3f1b8fe2 Andy McCall ↶ 474 
            edits.push((c, es));
475 
        }
476 
        let mut texts = Vec::new();
477 
        for _ in 0..r.count()? {
478 
            texts.push(match r.u8()? {
479 
                0 => TextRef::Blob(
480 
                    r.object()?,
481 
                    r.u32()?,
482 
                    match r.u8()? {
483 
                        0 => crate::objects::TextForm::Cbor,
484 
                        1 => crate::objects::TextForm::Raw,
485 
                        _ => crate::objects::TextForm::CborFallback,
486 
                    },
487 
                ),
488 
                _ => TextRef::Inline {
489 
                    change: r.object()?,
490 
                    start: r.u32()?,
491 
                    end: r.u32()?,
492 
                },
493 
            });
f9575918 Andy McCall ↶ 494 
        }
495 
        if !r.at_end() {
3f1b8fe2 Andy McCall ↶ 496 
            return Err(bad("trailing bytes in a file's history"));
f9575918 Andy McCall ↶ 497 
        }
3f1b8fe2 Andy McCall ↶ 498 
        Ok(DeferredBody { base, edits, texts })
f9575918 Andy McCall ↶ 499 
    }
e8d38e47 Andy McCall ↶ 500 
}
501
119bbf50 Andy McCall ↶ 502 
impl Clone for State {
503 
    fn clone(&self) -> State {
504 
        State {
505 
            changes: self.changes.clone(),
506 
            tree: self.tree.clone(),
507 
            files: self.files.clone(),
508 
            replaces: self.replaces.clone(),
f6451fbb Andy McCall ↶ 509 
            // A cache: the clone builds its own.
510 
            closure: Mutex::new(HashMap::new()),
e8d38e47 Andy McCall ↶ 511 
            deferred: self.deferred.clone(),
119bbf50 Andy McCall ↶ 512 
        }
513 
    }
514 
}
515
ff0af1ee unknown 516 
#[derive(Clone, Debug, PartialEq, Eq)]
517 
pub enum FileContent {
75167672 Andy McCall 518 
    Text {
519 
        bytes: Vec<u8>,
520 
        materialized: Materialized,
521 
    },
ff0af1ee unknown 522 
    /// Live blobs; more than one is a replace conflict (spec §9.3).
75167672 Andy McCall 523 
    Opaque {
524 
        blobs: Vec<ObjectRef>,
525 
    },
ff0af1ee unknown 526 
    Dir,
527 
}
528
529 
#[derive(Clone, Debug, PartialEq, Eq)]
530 
pub struct FileState {
531 
    pub node: NodeId,
532 
    pub kind: NodeKind,
533 
    pub mode: Mode,
534 
    pub content: FileContent,
535 
}
536
537 
impl FileState {
538 
    pub fn is_conflicted(&self) -> bool {
539 
        match &self.content {
540 
            FileContent::Text { materialized, .. } => materialized.is_conflicted(),
541 
            FileContent::Opaque { blobs } => blobs.len() > 1,
542 
            FileContent::Dir => false,
543 
        }
544 
    }
545 
}
546
20247a03 Andy McCall ↶ 547 
/// See `State::conflict_regions`.
548 
#[derive(Clone, Debug, Default, PartialEq, Eq)]
549 
pub struct ConflictRegions {
550 
    pub plain: Vec<(AtomKey, Vec<u8>)>,
551 
    pub region_atoms: Vec<AtomKey>,
552 
    pub contributors: Vec<ChangeHash>,
553 
}
554
ff0af1ee unknown 555 
/// The whole tree of a state, materialized.
556 
#[derive(Clone, Debug, Default)]
557 
pub struct Snapshot {
558 
    pub tree: TreeView,
559 
    pub files: BTreeMap<String, FileState>,
cc7a0056 Andy McCall ↶ 560 
    /// Text files left unrendered by [`State::materialize_except`]: their
561 
    /// `bytes` are empty and they are known not to be conflicted.
562 
    pub unrendered: BTreeSet<String>,
ff0af1ee unknown 563 
}
564
565 
impl Snapshot {
566 
    pub fn is_conflicted(&self) -> bool {
567 
        self.tree.is_conflicted() || self.files.values().any(|f| f.is_conflicted())
568 
    }
569 
}
570
571 
fn vertex(r: AtomRef) -> Vertex {
572 
    match r {
573 
        AtomRef::Start => Vertex::Start,
574 
        AtomRef::End => Vertex::End,
575 
        AtomRef::Atom { change, index } => Vertex::Atom((change, index)),
576 
    }
577 
}
578
579 
/// Replace self references in a tree op with the concrete change hash.
580 
pub fn resolve_tree_op(op: &TreeOp, me: ChangeHash) -> TreeOp {
581 
    match op {
75167672 Andy McCall 582 
        TreeOp::RemoveNode { node, placement } => TreeOp::RemoveNode {
583 
            node: *node,
584 
            placement: placement.resolve(me),
585 
        },
586 
        TreeOp::Move {
587 
            node,
588 
            old,
589 
            parent,
590 
            name,
591 
        } => TreeOp::Move {
592 
            node: *node,
593 
            old: old.resolve(me),
594 
            parent: *parent,
595 
            name: name.clone(),
596 
        },
597 
        TreeOp::SetMode { node, old, mode } => TreeOp::SetMode {
598 
            node: *node,
599 
            old: old.resolve(me),
600 
            mode: *mode,
601 
        },
ff0af1ee unknown 602 
        add @ TreeOp::AddNode { .. } => add.clone(),
e8d38e47 Andy McCall ↶ 603 
    }
604 
}
605
606 
/// Apply one change's edits of one file (inserts and deletes; replaces
607 
/// live beside the graphs) to that file's graph.
608 
fn apply_file_edits(g: &mut FileGraph, h: ChangeHash, edits: Vec<Edit>) {
dbf06d34 Andy McCall ↶ 609 
    // The graph's kept order, if any, follows the edits (see `Order`).
610 
    let order = g.take_order();
611 
    let mut inserts: Vec<(Vertex, Vertex, u32, u32)> = Vec::new();
612 
    let mut deleted: Vec<crate::graph::AtomKey> = Vec::new();
e8d38e47 Andy McCall ↶ 613 
    let mut next = 0u32;
614 
    for e in edits {
615 
        match e {
616 
            Edit::Insert {
617 
                after,
618 
                before,
619 
                lines,
620 
                ..
621 
            } => {
622 
                let first = next;
dbf06d34 Andy McCall ↶ 623 
                let count = lines.len() as u32;
624 
                next += count;
625 
                let (after, before) = (vertex(after.resolve(h)), vertex(before.resolve(h)));
626 
                inserts.push((after, before, first, count));
627 
                g.insert_owned(h, first, after, before, lines);
e8d38e47 Andy McCall ↶ 628 
            }
629 
            Edit::Delete { atoms, .. } => {
630 
                for r in atoms {
dbf06d34 Andy McCall ↶ 631 
                    let r = r.resolve(h);
632 
                    deleted.extend((r.from..r.to).map(|i| (r.change, i)));
633 
                    g.delete(h, &r);
e8d38e47 Andy McCall ↶ 634 
                }
635 
            }
636 
            Edit::Replace { .. } => {}
637 
        }
dbf06d34 Andy McCall ↶ 638 
    }
639 
    if let Some(o) = order {
640 
        g.keep_order(o.splice(h, &inserts, &deleted));
ff0af1ee unknown 641 
    }
642 
}
643
57d8dc05 Andy McCall ↶ 644 
/// Build the graphs of deferred entries: their checkpoint bases and the
645 
/// texts of inserts read without their lines are loaded in one call, then
646 
/// the graphs are built in parallel (they are independent).
647 
fn build_deferred(
3f1b8fe2 Andy McCall ↶ 648 
    taken: Vec<(NodeId, Deferred)>,
57d8dc05 Andy McCall ↶ 649 
    load: impl FnOnce(&[ObjectRef]) -> Result<Vec<Vec<u8>>, ObjectError>,
650 
    read_change: impl Fn(&ChangeHash) -> Result<Arc<Vec<u8>>, ObjectError>,
651 
) -> Result<Vec<(NodeId, FileGraph)>, ObjectError> {
3f1b8fe2 Andy McCall ↶ 652 
    let mut taken: Vec<(NodeId, DeferredBody)> =
653 
        taken.into_iter().map(|(n, d)| (n, d.into_body())).collect();
57d8dc05 Andy McCall ↶ 654 
    let mut refs: Vec<ObjectRef> = taken
655 
        .iter()
656 
        .filter_map(|(_, d)| match &d.base {
657 
            Some(DeferredBase::Blob(r)) => Some(*r),
658 
            _ => None,
659 
        })
660 
        .collect();
661 
    // Text blobs of inserts read without their lines, after the bases.
662 
    let bases = refs.len();
663 
    refs.extend(taken.iter().flat_map(|(_, d)| {
664 
        d.texts.iter().filter_map(|t| match t {
0f93f49c Andy McCall ↶ 665 
            TextRef::Blob(r, _, _) => Some(*r),
57d8dc05 Andy McCall ↶ 666 
            TextRef::Inline { .. } => None,
667 
        })
668 
    }));
669 
    // And the encodings of changes whose inline inserts are needed,
670 
    // each read once.
638fb214 Andy McCall ↶ 671 
    let reading = crate::timing::phase("graphs: read changes and blobs");
57d8dc05 Andy McCall ↶ 672 
    let mut changes: HashMap<ChangeHash, Arc<Vec<u8>>> = HashMap::new();
673 
    for t in taken.iter().flat_map(|(_, d)| d.texts.iter()) {
674 
        if let TextRef::Inline { change, .. } = t {
675 
            if !changes.contains_key(change) {
676 
                changes.insert(*change, read_change(change)?);
677 
            }
678 
        }
679 
    }
680 
    let mut blobs = if refs.is_empty() {
681 
        Vec::new()
682 
    } else {
683 
        load(&refs)?
684 
    };
685 
    if blobs.len() != refs.len() {
686 
        return Err(ObjectError::Schema("graph blobs: wrong count".into()));
687 
    }
638fb214 Andy McCall ↶ 688 
    drop(reading);
acadb5ed Andy McCall ↶ 689 
    let lines = crate::timing::phase("graphs: hand out blobs");
57d8dc05 Andy McCall ↶ 690 
    let mut texts = blobs.split_off(bases).into_iter();
691 
    let mut blobs = blobs.into_iter();
acadb5ed Andy McCall ↶ 692 
    // Hand each graph its own blobs, in order, then fill in its inserts'
693 
    // lines and build it, all in parallel: graphs are independent.
694 
    type Work = (NodeId, DeferredBody, Option<Vec<u8>>, Vec<Vec<u8>>);
695 
    let mut work: Vec<Work> = Vec::with_capacity(taken.len());
696 
    for (node, d) in taken.drain(..) {
697 
        let wanted = d
698 
            .texts
699 
            .iter()
700 
            .filter(|t| matches!(t, TextRef::Blob(..)))
701 
            .count();
702 
        let mine: Vec<Vec<u8>> = texts.by_ref().take(wanted).collect();
703 
        if mine.len() != wanted {
704 
            return Err(ObjectError::Schema("text blobs: wrong count".into()));
57d8dc05 Andy McCall ↶ 705 
        }
706 
        let bytes = match &d.base {
707 
            Some(DeferredBase::Blob(_)) => Some(
708 
                blobs
709 
                    .next()
710 
                    .ok_or_else(|| ObjectError::Schema("graph blobs: wrong count".into()))?,
711 
            ),
712 
            _ => None,
713 
        };
acadb5ed Andy McCall ↶ 714 
        work.push((node, d, bytes, mine));
57d8dc05 Andy McCall ↶ 715 
    }
638fb214 Andy McCall ↶ 716 
    drop(lines);
acadb5ed Andy McCall ↶ 717 
    let _t = crate::timing::phase("graphs: lines and build");
57d8dc05 Andy McCall ↶ 718 
    use rayon::prelude::*;
acadb5ed Andy McCall ↶ 719 
    let changes = &changes;
57d8dc05 Andy McCall ↶ 720 
    let built: Vec<(NodeId, FileGraph)> = work
721 
        .into_par_iter()
acadb5ed Andy McCall ↶ 722 
        .map(|(node, mut d, bytes, mine)| {
723 
            // Fill in the lines of inserts read without them, in order.
724 
            let mut want = std::mem::take(&mut d.texts).into_iter();
725 
            let mut mine = mine.into_iter();
726 
            for (_, edits) in d.edits.iter_mut() {
727 
                for e in edits.iter_mut() {
728 
                    if let Edit::Insert { lines, .. } = e {
729 
                        if lines.is_empty() {
730 
                            *lines = match want.next() {
731 
                                Some(TextRef::Blob(_, count, form)) => {
732 
                                    let content = mine.next().ok_or_else(|| {
733 
                                        ObjectError::Schema("text blobs: wrong count".into())
734 
                                    })?;
735 
                                    crate::objects::text_lines(&content, count, form)?
736 
                                }
737 
                                Some(TextRef::Inline { change, start, end }) => {
738 
                                    let bytes = &changes[&change];
739 
                                    let range = bytes
740 
                                        .get(start as usize..end as usize)
741 
                                        .ok_or_else(|| {
742 
                                            ObjectError::Schema(
743 
                                                "an inline insert lies outside its change".into(),
744 
                                            )
745 
                                        })?;
746 
                                    crate::objects::inline_lines(range)?
747 
                                }
748 
                                None => {
749 
                                    return Err(ObjectError::Schema(
750 
                                        "an insert's text is missing".into(),
751 
                                    ))
752 
                                }
753 
                            };
754 
                        }
755 
                    }
756 
                }
757 
            }
57d8dc05 Andy McCall ↶ 758 
            let mut graph = match (d.base.take(), bytes) {
759 
                (Some(DeferredBase::Inline(v)), _) => FileGraph::from_value(&v)?,
760 
                (Some(DeferredBase::Blob(_)), Some(bytes)) => {
761 
                    FileGraph::from_value(&cbor::decode(&bytes)?)?
762 
                }
763 
                _ => FileGraph::default(),
764 
            };
765 
            for (h, edits) in std::mem::take(&mut d.edits) {
766 
                apply_file_edits(&mut graph, h, edits);
767 
            }
768 
            Ok((node, graph))
769 
        })
770 
        .collect::<Result<_, ObjectError>>()?;
771 
    Ok(built)
772 
}
773
ff0af1ee unknown 774 
impl State {
775 
    pub fn new() -> Self {
776 
        Self::default()
e8d38e47 Andy McCall ↶ 777 
    }
778
779 
    /// An empty state for history only: changes and tree are kept, file
780 
    /// edits are recorded but no file graph is built until
781 
    /// [`State::load_graphs`] asks for it. For log and other commands that
782 
    /// need no file contents, or only a few files.
783 
    pub fn new_history_only() -> Self {
784 
        State {
36e51aa8 Andy McCall ↶ 785 
            deferred: Some(Default::default()),
e8d38e47 Andy McCall ↶ 786 
            ..Self::default()
787 
        }
788 
    }
789
e83354cd Andy McCall ↶ 790 
    /// Whether `node`'s file graph is built (always, in a full state).
791 
    pub fn is_built(&self, node: &NodeId) -> bool {
792 
        self.deferred.is_none() || self.files.contains_key(node)
793 
    }
794
86e1824f Andy McCall ↶ 795 
    /// Whether this state builds file graphs only when asked
796 
    /// ([`State::new_history_only`]), even if it has none waiting.
797 
    pub fn is_history_only(&self) -> bool {
798 
        self.deferred.is_some()
799 
    }
800
e8d38e47 Andy McCall ↶ 801 
    /// Whether this state holds every file graph.
802 
    pub fn is_full(&self) -> bool {
803 
        self.deferred.as_ref().is_none_or(|d| d.is_empty())
804 
    }
805
806 
    /// The graph of `node`, which must be loaded: asking a history-only
807 
    /// state for a graph it has not built is a bug, never an empty file.
808 
    fn graph(&self, node: &NodeId) -> Option<&FileGraph> {
809 
        if let Some(d) = &self.deferred {
810 
            assert!(
811 
                !d.contains_key(node),
812 
                "file graph {} of a history-only state was not loaded (State::load_graphs)",
813 
                node.short(12)
814 
            );
815 
        }
dfb23a3a Andy McCall ↶ 816 
        self.files.get(node).map(|g| g.as_ref())
e8d38e47 Andy McCall ↶ 817 
    }
818
819 
    /// Operations over every file need every graph.
820 
    fn require_full(&self, what: &str) {
821 
        assert!(
822 
            self.is_full(),
823 
            "{what} needs every file graph; this state was loaded for history only"
824 
        );
825 
    }
826
827 
    /// Build the graphs of `nodes` in a history-only state: from their
828 
    /// checkpoint base (blobs read in one batch through `load`) and their
829 
    /// deferred edits. Nodes already built, or with no graph, are skipped.
830 
    pub fn load_graphs(
831 
        &mut self,
832 
        nodes: &[NodeId],
833 
        load: impl FnOnce(&[ObjectRef]) -> Result<Vec<Vec<u8>>, ObjectError>,
519c7c06 Andy McCall ↶ 834 
        read_change: impl Fn(&ChangeHash) -> Result<Arc<Vec<u8>>, ObjectError>,
e8d38e47 Andy McCall ↶ 835 
    ) -> Result<(), ObjectError> {
836 
        let Some(deferred) = self.deferred.as_mut() else {
837 
            return Ok(());
838 
        };
57d8dc05 Andy McCall ↶ 839 
        let taken: Vec<(NodeId, Deferred)> = nodes
e8d38e47 Andy McCall ↶ 840 
            .iter()
f6451fbb Andy McCall ↶ 841 
            .filter_map(|n| deferred.remove(n).map(|d| (*n, Arc::unwrap_or_clone(d))))
e8d38e47 Andy McCall ↶ 842 
            .collect();
57d8dc05 Andy McCall ↶ 843 
        let built = build_deferred(taken, load, read_change)?;
dfb23a3a Andy McCall ↶ 844 
        self.files
845 
            .extend(built.into_iter().map(|(n, g)| (n, Arc::new(g))));
cc7a0056 Andy McCall ↶ 846 
        Ok(())
57d8dc05 Andy McCall ↶ 847 
    }
848
849 
    /// The graphs of `nodes`, built from this history-only state's deferred
850 
    /// edits without building them in it: the state stays history only, so
851 
    /// changes read without their lines can still be added to it and every
852 
    /// graph keeps its key. For a caller that renders a few files of many
853 
    /// states in turn (verifying an import).
854 
    pub fn build_graphs_detached(
855 
        &self,
856 
        nodes: &[NodeId],
857 
        load: impl FnOnce(&[ObjectRef]) -> Result<Vec<Vec<u8>>, ObjectError>,
858 
        read_change: impl Fn(&ChangeHash) -> Result<Arc<Vec<u8>>, ObjectError>,
859 
    ) -> Result<Vec<(NodeId, FileGraph)>, ObjectError> {
860 
        let Some(deferred) = self.deferred.as_ref() else {
861 
            return Ok(Vec::new());
862 
        };
863 
        let copies: Vec<(NodeId, Deferred)> = nodes
864 
            .iter()
f6451fbb Andy McCall ↶ 865 
            .map(|n| {
866 
                (
867 
                    *n,
868 
                    deferred.get(n).map(|d| (**d).clone()).unwrap_or_default(),
869 
                )
870 
            })
57d8dc05 Andy McCall ↶ 871 
            .collect();
872 
        build_deferred(copies, load, read_change)
873 
    }
874
875 
    /// Render a graph built for this state (see
876 
    /// [`State::build_graphs_detached`]), as [`State::render_file`] does.
877 
    pub fn render_graph(&self, g: &FileGraph) -> (Vec<u8>, Materialized) {
878 
        let m = g.materialize(self);
879 
        let bytes = g.render(&m, &|h| self.label(h));
880 
        (bytes, m)
cc7a0056 Andy McCall ↶ 881 
    }
882
69816d68 Andy McCall ↶ 883 
    /// Every file graph a history-only state has not built, deleted files'
884 
    /// included.
885 
    pub fn unbuilt_nodes(&self) -> Vec<NodeId> {
886 
        self.deferred
887 
            .as_ref()
888 
            .map(|d| d.keys().copied().collect())
889 
            .unwrap_or_default()
890 
    }
891
c5ce0367 Andy McCall ↶ 892 
    /// Drop the built graphs of `nodes`, for a caller rendering a large
893 
    /// tree a batch at a time. The state can no longer render those files,
894 
    /// so it must not be used for them again.
895 
    pub fn drop_graphs(&mut self, nodes: &[NodeId]) {
896 
        for n in nodes {
897 
            self.files.remove(n);
898 
        }
899 
    }
900
cc7a0056 Andy McCall ↶ 901 
    /// Build every graph a history-only state has not built, making it full.
902 
    pub fn load_all_graphs(
903 
        &mut self,
904 
        load: impl FnOnce(&[ObjectRef]) -> Result<Vec<Vec<u8>>, ObjectError>,
519c7c06 Andy McCall ↶ 905 
        read_change: impl Fn(&ChangeHash) -> Result<Arc<Vec<u8>>, ObjectError>,
cc7a0056 Andy McCall ↶ 906 
    ) -> Result<(), ObjectError> {
907 
        let nodes: Vec<NodeId> = match &self.deferred {
908 
            Some(d) => d.keys().copied().collect(),
909 
            None => return Ok(()),
910 
        };
a4fad5b0 Andy McCall ↶ 911 
        self.load_graphs(&nodes, load, read_change)?;
cc7a0056 Andy McCall ↶ 912 
        self.deferred = None;
e8d38e47 Andy McCall ↶ 913 
        Ok(())
cc7a0056 Andy McCall ↶ 914 
    }
915
916 
    /// A key for the graph of `node` in a history-only state that has not
917 
    /// built it: equal keys mean equal graphs, so equal renderings (a
918 
    /// rendering depends only on the graph and on the changes' own
919 
    /// immutable metadata). It names the node, its checkpoint base (a blob,
920 
    /// an inline value, or none) and the set of later changes that edited
921 
    /// the file.
922 
    /// `None` for a full state or a graph already built.
923 
    pub fn graph_key(&self, node: &NodeId) -> Option<[u8; 32]> {
924 
        let deferred = self.deferred.as_ref()?;
925 
        if self.files.contains_key(node) {
926 
            return None;
927 
        }
928 
        let mut h = blake3::Hasher::new();
929 
        h.update(b"oxy graph key 1\0");
930 
        // A change's edits are applied per node: the node is part of it.
931 
        h.update(&node.0);
932 
        let Some(d) = deferred.get(node) else {
933 
            // Never edited: the empty graph.
934 
            h.update(&[0]);
935 
            return Some(*h.finalize().as_bytes());
936 
        };
f9575918 Andy McCall ↶ 937 
        Some(*d.key.get_or_init(|| d.graph_key(h)))
938 
    }
939
940 
    pub fn len(&self) -> usize {
941 
        self.changes.len()
942 
    }
943 
}
944
945 
impl Deferred {
946 
    /// See [`State::graph_key`]: `h` has taken the node already.
947 
    fn graph_key(&self, mut h: blake3::Hasher) -> [u8; 32] {
3f1b8fe2 Andy McCall ↶ 948 
        let d = self.body();
cc7a0056 Andy McCall ↶ 949 
        match &d.base {
950 
            None => h.update(&[0]),
951 
            Some(DeferredBase::Blob(r)) => h.update(&[1]).update(&r.0),
952 
            Some(DeferredBase::Inline(v)) => h.update(&[2]).update(&cbor::encode(v)),
953 
        };
954 
        let mut changes: Vec<&ChangeHash> = d.edits.iter().map(|(c, _)| c).collect();
955 
        changes.sort();
956 
        changes.dedup();
957 
        h.update(&(changes.len() as u64).to_le_bytes());
958 
        for c in changes {
959 
            h.update(&c.0);
960 
        }
f9575918 Andy McCall ↶ 961 
        *h.finalize().as_bytes()
ff0af1ee unknown 962 
    }
f9575918 Andy McCall ↶ 963 
}
ff0af1ee unknown 964
f9575918 Andy McCall ↶ 965 
impl State {
ff0af1ee unknown 966 
    pub fn is_empty(&self) -> bool {
967 
        self.changes.is_empty()
968 
    }
969 
    pub fn contains(&self, h: &ChangeHash) -> bool {
970 
        self.changes.contains_key(h)
971 
    }
252e8cb2 Andy McCall ↶ 972 
    pub fn get(&self, h: &ChangeHash) -> Option<&ChangeMeta> {
f6451fbb Andy McCall ↶ 973 
        self.changes.get(h).map(|m| &**m)
ff0af1ee unknown 974 
    }
252e8cb2 Andy McCall ↶ 975 
    pub fn changes(&self) -> impl Iterator<Item = (&ChangeHash, &ChangeMeta)> {
f6451fbb Andy McCall ↶ 976 
        self.changes.iter().map(|(h, m)| (h, &**m))
ff0af1ee unknown 977 
    }
978 
    pub fn tree(&self) -> &TreeGraph {
979 
        &self.tree
980 
    }
981 
    pub fn file(&self, node: &NodeId) -> Option<&FileGraph> {
e8d38e47 Andy McCall ↶ 982 
        self.graph(node)
ff0af1ee unknown 983 
    }
984
985 
    /// Add a change whose dependencies are already present.
986 
    pub fn add(&mut self, change: Change) -> Result<ChangeHash, StateError> {
987 
        let h = change.hash();
192fad1e Andy McCall ↶ 988 
        self.add_hashed(h, change)
989 
    }
990
991 
    /// [`State::add`] for a change whose hash `h` is already known (it was
992 
    /// just stored), so it is not encoded again.
993 
    pub fn add_hashed(&mut self, h: ChangeHash, change: Change) -> Result<ChangeHash, StateError> {
ff0af1ee unknown 994 
        if self.changes.contains_key(&h) {
995 
            return Ok(h);
996 
        }
997 
        for d in &change.deps {
998 
            if !self.changes.contains_key(d) {
999 
                return Err(StateError::MissingDep(*d, h));
1000 
            }
1001 
        }
192fad1e Andy McCall ↶ 1002 
        self.add_known(h, change, Vec::new());
1003 
        Ok(h)
ff0af1ee unknown 1004 
    }
1005
1006 
    /// Add a change in any order; call `validate` once all are in.
1007 
    pub fn add_unchecked(&mut self, change: Change) -> ChangeHash {
1008 
        let h = change.hash();
86e1824f Andy McCall ↶ 1009 
        self.add_known(h, change, Vec::new());
1010 
        h
1011 
    }
1012
ab4d4e31 Andy McCall ↶ 1013 
    /// Add a change just stored under hash `h` to a history-only state that
1014 
    /// has built some graphs: an edit of a built graph is applied whole
1015 
    /// (from `full`), and one of a file not built waits without its text
1016 
    /// (from `skeleton` and its `texts`, as the store reads it back), so the
1017 
    /// state holds no text it has not built. A Git import adds each change
1018 
    /// it makes this way, keeping memory to what changes.
1019 
    pub fn add_known_mixed(
1020 
        &mut self,
1021 
        h: ChangeHash,
1022 
        full: Change,
1023 
        skeleton: Change,
1024 
        texts: Vec<TextRef>,
1025 
    ) {
1026 
        if self.deferred.is_none() || self.changes.contains_key(&h) {
1027 
            self.add_known(h, full, Vec::new());
1028 
            return;
1029 
        }
1030 
        let Change {
1031 
            version,
1032 
            change_id,
1033 
            deps,
1034 
            author,
1035 
            hlc,
1036 
            message,
1037 
            tree_ops,
1038 
            edits: full_edits,
1039 
            kind,
1040 
        } = full;
1041 
        let mut texts = texts.into_iter();
1042 
        let mut edits = Vec::with_capacity(full_edits.len());
1043 
        let mut kept = Vec::new();
1044 
        for (f, s) in full_edits.into_iter().zip(skeleton.edits) {
1045 
            let text = match &s {
1046 
                Edit::Insert { lines, .. } if lines.is_empty() => texts.next(),
1047 
                _ => None,
1048 
            };
1049 
            if self.files.contains_key(&f.node()) {
1050 
                edits.push(f);
1051 
            } else {
1052 
                edits.push(s);
1053 
                kept.extend(text);
1054 
            }
1055 
        }
1056 
        let c = Change {
1057 
            version,
1058 
            change_id,
1059 
            deps,
1060 
            author,
1061 
            hlc,
1062 
            message,
1063 
            tree_ops,
1064 
            edits,
1065 
            kind,
1066 
        };
1067 
        self.add_known(h, c, kept);
1068 
    }
1069
86e1824f Andy McCall ↶ 1070 
    /// Add a change read from the store under hash `h`, without hashing it
1071 
    /// again (for a version 2 change that means chunking all its text).
1072 
    /// `texts` names, in order, the inserts left without their lines (see
1073 
    /// [`crate::store::Store::get_change_lazy`]); only a history-only state
1074 
    /// takes them, and only for graphs it has not built.
a4fad5b0 Andy McCall ↶ 1075 
    pub fn add_known(&mut self, h: ChangeHash, change: Change, texts: Vec<TextRef>) {
ff0af1ee unknown 1076 
        if self.changes.contains_key(&h) {
86e1824f Andy McCall ↶ 1077 
            return;
ff0af1ee unknown 1078 
        }
0bdc3f91 Andy McCall ↶ 1079 
        let meta = ChangeMeta::of(&change);
86e1824f Andy McCall ↶ 1080 
        self.apply_with(h, change, texts);
f6451fbb Andy McCall ↶ 1081 
        self.changes.insert(h, Arc::new(meta));
119bbf50 Andy McCall ↶ 1082 
        self.closure.lock().unwrap().clear();
ff0af1ee unknown 1083 
    }
1084
252e8cb2 Andy McCall ↶ 1085 
    // ------------------------------------------------------------ checkpoints (spec §11)
1086
afaba5f1 Andy McCall ↶ 1087 
    /// Serialize the whole state in payload version 1: change metadata,
1088 
    /// tree, file graphs, replaces, all in one value (spec §11).
252e8cb2 Andy McCall ↶ 1089 
    pub fn checkpoint_payload(&self) -> Vec<u8> {
e8d38e47 Andy McCall ↶ 1090 
        self.require_full("a checkpoint");
afaba5f1 Andy McCall ↶ 1091 
        let mut nodes: Vec<&NodeId> = self.files.keys().collect();
1092 
        nodes.sort();
1093 
        let files = Value::Array(
1094 
            nodes
1095 
                .into_iter()
1096 
                .map(|n| Value::Array(vec![Value::Bytes(n.0.to_vec()), self.files[n].to_value()]))
1097 
                .collect(),
1098 
        );
1099 
        cbor::encode(&self.payload_value(o::FORMAT_VERSION, files))
1100 
    }
1101
1102 
    /// Each file graph encoded on its own, by node, for a version 2 payload
1103 
    /// (spec §11): the graphs of large files become blobs of their own.
1104 
    pub fn checkpoint_file_graphs(&self) -> Vec<(NodeId, Vec<u8>)> {
1105 
        use rayon::prelude::*;
e8d38e47 Andy McCall ↶ 1106 
        self.require_full("a checkpoint");
dfb23a3a Andy McCall ↶ 1107 
        let mut nodes: Vec<(&NodeId, &FileGraph)> =
1108 
            self.files.iter().map(|(n, g)| (n, g.as_ref())).collect();
afaba5f1 Andy McCall ↶ 1109 
        nodes.sort_by_key(|(n, _)| **n);
1110 
        nodes
1111 
            .into_par_iter()
1112 
            .map(|(n, g)| (*n, cbor::encode(&g.to_value())))
1113 
            .collect()
1114 
    }
1115
1116 
    /// The payload version 2 index for the graphs of
1117 
    /// [`State::checkpoint_file_graphs`]: a graph encoded in fewer than
1118 
    /// [`INLINE_GRAPH_LIMIT`] bytes is kept inline, a larger one is named by
1119 
    /// `blob_of` (the ObjectRef of the blob holding its encoding).
1120 
    pub fn checkpoint_index(
1121 
        &self,
1122 
        graphs: &[(NodeId, Vec<u8>)],
1123 
        mut blob_of: impl FnMut(&[u8]) -> ObjectRef,
1124 
    ) -> Vec<u8> {
1125 
        let files = Value::Array(
1126 
            graphs
1127 
                .iter()
1128 
                .map(|(n, enc)| {
1129 
                    let entry = if enc.len() < INLINE_GRAPH_LIMIT {
1130 
                        cbor::decode(enc).expect("an encoded graph decodes")
1131 
                    } else {
1132 
                        Value::Bytes(blob_of(enc).0.to_vec())
1133 
                    };
1134 
                    Value::Array(vec![Value::Bytes(n.0.to_vec()), entry])
1135 
                })
1136 
                .collect(),
1137 
        );
1138 
        cbor::encode(&self.payload_value(CHECKPOINT_INDEX_VERSION, files))
1139 
    }
1140
1141 
    /// The payload map around `files`: changes, tree and replaces as in version 1.
1142 
    fn payload_value(&self, version: u64, files: Value) -> Value {
252e8cb2 Andy McCall ↶ 1143 
        let mut hashes: Vec<&ChangeHash> = self.changes.keys().collect();
1144 
        hashes.sort();
1145 
        let changes = Value::Array(
1146 
            hashes
1147 
                .into_iter()
1148 
                .map(|h| {
1149 
                    let m = &self.changes[h];
1150 
                    Value::Array(vec![
1151 
                        Value::Bytes(h.0.to_vec()),
1152 
                        Value::Bytes(m.change_id.0.to_vec()),
1153 
                        Value::Array(m.deps.iter().map(|d| Value::Bytes(d.0.to_vec())).collect()),
1154 
                        Value::Text(m.message.clone()),
1155 
                        Value::Uint(m.hlc.wall_ms),
1156 
                        Value::Uint(m.hlc.logical as u64),
1157 
                        Value::Uint(m.kind.tag()),
1158 
                        Value::Bytes(m.author.0.to_vec()),
1159 
                    ])
1160 
                })
75167672 Andy McCall 1161 
                .collect(),
1162 
        );
252e8cb2 Andy McCall ↶ 1163 
        let mut rnodes: Vec<&NodeId> = self.replaces.keys().collect();
1164 
        rnodes.sort();
75167672 Andy McCall 1165 
        let opt =
1166 
            |o: &Option<ObjectRef>| o.map(|r| Value::Bytes(r.0.to_vec())).unwrap_or(Value::Null);
252e8cb2 Andy McCall ↶ 1167 
        let replaces = Value::Array(
1168 
            rnodes
1169 
                .into_iter()
1170 
                .map(|n| {
1171 
                    Value::Array(vec![
1172 
                        Value::Bytes(n.0.to_vec()),
75167672 Andy McCall 1173 
                        Value::Array(
1174 
                            self.replaces[n]
1175 
                                .iter()
1176 
                                .map(|(c, o, nw)| {
1177 
                                    Value::Array(vec![Value::Bytes(c.0.to_vec()), opt(o), opt(nw)])
1178 
                                })
1179 
                                .collect(),
1180 
                        ),
252e8cb2 Andy McCall ↶ 1181 
                    ])
1182 
                })
1183 
                .collect(),
1184 
        );
afaba5f1 Andy McCall ↶ 1185 
        Value::map([
1186 
            (0, Value::Uint(version)),
75167672 Andy McCall 1187 
            (1, changes),
1188 
            (2, self.tree.to_value()),
1189 
            (3, files),
1190 
            (4, replaces),
afaba5f1 Andy McCall ↶ 1191 
        ])
252e8cb2 Andy McCall ↶ 1192 
    }
1193
afaba5f1 Andy McCall ↶ 1194 
    /// Decode a version 1 payload (the whole state in one value). A
1195 
    /// version 2 payload needs its graph blobs: use [`State::from_checkpoint`].
252e8cb2 Andy McCall ↶ 1196 
    pub fn from_checkpoint_payload(bytes: &[u8]) -> Result<State, ObjectError> {
afaba5f1 Andy McCall ↶ 1197 
        State::from_checkpoint(bytes, |_| {
1198 
            Err(ObjectError::Schema(
1199 
                "a version 2 checkpoint needs its graph blobs".into(),
1200 
            ))
1201 
        })
1202 
    }
1203
1204 
    /// Decode a checkpoint payload of either version (spec §11). For
1205 
    /// version 2, `load` returns the contents of the named graph blobs, in
1206 
    /// order; the graphs are then decoded in parallel.
1207 
    pub fn from_checkpoint(
1208 
        bytes: &[u8],
1209 
        load: impl FnOnce(&[ObjectRef]) -> Result<Vec<Vec<u8>>, ObjectError>,
1210 
    ) -> Result<State, ObjectError> {
1211 
        use rayon::prelude::*;
252e8cb2 Andy McCall ↶ 1212 
        let v = cbor::decode(bytes)?;
1213 
        let m = o::map(&v, "checkpoint payload")?;
afaba5f1 Andy McCall ↶ 1214 
        let version = o::uint(o::field(m, 0, "version")?, "version")?;
1215 
        if version != o::FORMAT_VERSION && version != CHECKPOINT_INDEX_VERSION {
1216 
            return Err(ObjectError::Schema(format!(
1217 
                "checkpoint payload version {version} is not supported"
1218 
            )));
1219 
        }
1220 
        let mut st = State::payload_common(m)?;
1221 
        let entries = o::array(o::field(m, 3, "files")?, "files")?;
1222 
        let mut parsed: Vec<(NodeId, &Value)> = Vec::with_capacity(entries.len());
1223 
        for f in entries {
1224 
            let e = o::array(f, "file")?;
1225 
            if e.len() != 2 {
1226 
                return Err(ObjectError::Schema("file: expected [node, graph]".into()));
1227 
            }
1228 
            let node = NodeId::from_slice(o::bytes(&e[0], "node")?)
1229 
                .ok_or_else(|| ObjectError::Schema("node: expected 16 bytes".into()))?;
1230 
            parsed.push((node, &e[1]));
1231 
        }
1232 
        // Version 2 names large graphs by blob: fetch those in one batch.
1233 
        let mut fetched: HashMap<NodeId, Vec<u8>> = HashMap::new();
1234 
        if version == CHECKPOINT_INDEX_VERSION {
1235 
            let wanted: Vec<(NodeId, ObjectRef)> = parsed
1236 
                .iter()
1237 
                .filter(|(_, e)| matches!(e, Value::Bytes(_)))
1238 
                .map(|(n, e)| Ok((*n, o::oref(e, "graph blob")?)))
1239 
                .collect::<Result<_, ObjectError>>()?;
1240 
            if !wanted.is_empty() {
1241 
                let refs: Vec<ObjectRef> = wanted.iter().map(|(_, r)| *r).collect();
1242 
                let contents = {
1243 
                    let _t = crate::timing::phase("load:   graph blobs read");
1244 
                    load(&refs)?
1245 
                };
1246 
                if contents.len() != refs.len() {
1247 
                    return Err(ObjectError::Schema("graph blobs: wrong count".into()));
1248 
                }
1249 
                fetched.extend(wanted.iter().map(|(n, _)| *n).zip(contents));
1250 
            }
1251 
        } else if parsed.iter().any(|(_, e)| matches!(e, Value::Bytes(_))) {
1252 
            return Err(ObjectError::Schema(
1253 
                "a version 1 payload holds graphs inline".into(),
1254 
            ));
1255 
        }
1256 
        // File graphs are independent; decode and build them in parallel.
1257 
        let graphs = parsed
1258 
            .par_iter()
1259 
            .map(|(node, entry)| {
1260 
                let graph = match fetched.get(node) {
1261 
                    Some(bytes) => FileGraph::from_value(&cbor::decode(bytes)?)?,
1262 
                    None => FileGraph::from_value(entry)?,
1263 
                };
1264 
                Ok((*node, graph))
1265 
            })
1266 
            .collect::<Result<Vec<_>, ObjectError>>()?;
dfb23a3a Andy McCall ↶ 1267 
        st.files
1268 
            .extend(graphs.into_iter().map(|(n, g)| (n, Arc::new(g))));
afaba5f1 Andy McCall ↶ 1269 
        Ok(st)
1270 
    }
1271
1272 
    /// The graph blobs a payload names: empty for version 1.
1273 
    pub fn checkpoint_graph_refs(bytes: &[u8]) -> Result<Vec<ObjectRef>, ObjectError> {
1274 
        let v = cbor::decode(bytes)?;
1275 
        let m = o::map(&v, "checkpoint payload")?;
1276 
        let mut out = Vec::new();
1277 
        for f in o::array(o::field(m, 3, "files")?, "files")? {
1278 
            if let Some(entry @ Value::Bytes(_)) = o::array(f, "file")?.get(1) {
1279 
                out.push(o::oref(entry, "graph blob")?);
1280 
            }
1281 
        }
1282 
        Ok(out)
e8d38e47 Andy McCall ↶ 1283 
    }
1284
1285 
    /// Decode a checkpoint payload for history only: a version 2 payload's
1286 
    /// graphs are noted, not read or built, and come later through
1287 
    /// [`State::load_graphs`]. A version 1 payload holds them inline and is
1288 
    /// decoded in full.
1289 
    pub fn from_checkpoint_history(bytes: &[u8]) -> Result<State, ObjectError> {
1290 
        let v = cbor::decode(bytes)?;
1291 
        let m = o::map(&v, "checkpoint payload")?;
1292 
        let version = o::uint(o::field(m, 0, "version")?, "version")?;
1293 
        if version != CHECKPOINT_INDEX_VERSION {
1294 
            return State::from_checkpoint_payload(bytes);
1295 
        }
1296 
        let mut st = State::payload_common(m)?;
36e51aa8 Andy McCall ↶ 1297 
        let mut deferred = crate::fasthash::FastMap::default();
e8d38e47 Andy McCall ↶ 1298 
        for f in o::array(o::field(m, 3, "files")?, "files")? {
1299 
            let e = o::array(f, "file")?;
1300 
            if e.len() != 2 {
1301 
                return Err(ObjectError::Schema("file: expected [node, graph]".into()));
1302 
            }
1303 
            let node = NodeId::from_slice(o::bytes(&e[0], "node")?)
1304 
                .ok_or_else(|| ObjectError::Schema("node: expected 16 bytes".into()))?;
1305 
            let base = match &e[1] {
1306 
                Value::Bytes(_) => DeferredBase::Blob(o::oref(&e[1], "graph blob")?),
1307 
                other => DeferredBase::Inline(other.clone()),
1308 
            };
1309 
            deferred.insert(
1310 
                node,
3f1b8fe2 Andy McCall ↶ 1311 
                Arc::new(Deferred::from_body(DeferredBody {
e8d38e47 Andy McCall ↶ 1312 
                    base: Some(base),
3f1b8fe2 Andy McCall ↶ 1313 
                    ..DeferredBody::default()
1314 
                })),
e8d38e47 Andy McCall ↶ 1315 
            );
1316 
        }
1317 
        st.deferred = Some(deferred);
1318 
        Ok(st)
afaba5f1 Andy McCall ↶ 1319 
    }
1320
1321 
    /// Changes, tree and replaces of a payload of either version.
1322 
    fn payload_common(m: &BTreeMap<u64, Value>) -> Result<State, ObjectError> {
252e8cb2 Andy McCall ↶ 1323 
        let mut st = State::new();
1324 
        for c in o::array(o::field(m, 1, "changes")?, "changes")? {
1325 
            let e = o::array(c, "change meta")?;
1326 
            if e.len() != 8 {
1327 
                return Err(ObjectError::Schema("change meta: expected 8 fields".into()));
1328 
            }
1329 
            let hash = o::oref(&e[0], "hash")?;
1330 
            let meta = ChangeMeta {
75167672 Andy McCall 1331 
                change_id: crate::ids::ChangeId::from_slice(o::bytes(&e[1], "change id")?)
1332 
                    .ok_or_else(|| ObjectError::Schema("change id: expected 16 bytes".into()))?,
1333 
                deps: o::array(&e[2], "deps")?
1334 
                    .iter()
1335 
                    .map(|d| o::oref(d, "dep"))
1336 
                    .collect::<Result<Vec<_>, _>>()?,
252e8cb2 Andy McCall ↶ 1337 
                message: o::text(&e[3], "message")?.to_owned(),
75167672 Andy McCall 1338 
                hlc: Hlc {
1339 
                    wall_ms: o::uint(&e[4], "wall")?,
1340 
                    logical: o::u32_(&e[5], "logical")?,
1341 
                },
252e8cb2 Andy McCall ↶ 1342 
                kind: ChangeKind::from_tag(o::uint(&e[6], "kind")?)?,
1343 
                author: o::oref(&e[7], "author")?,
1344 
            };
f6451fbb Andy McCall ↶ 1345 
            st.changes.insert(hash, Arc::new(meta));
252e8cb2 Andy McCall ↶ 1346 
        }
1347 
        st.tree = TreeGraph::from_value(o::field(m, 2, "tree")?)?;
75167672 Andy McCall 1348 
        let opt = |v: &Value| -> Result<Option<ObjectRef>, ObjectError> {
1349 
            if v.is_null() {
1350 
                Ok(None)
1351 
            } else {
1352 
                o::oref(v, "blob").map(Some)
1353 
            }
1354 
        };
252e8cb2 Andy McCall ↶ 1355 
        for r in o::array(o::field(m, 4, "replaces")?, "replaces")? {
1356 
            let e = o::array(r, "replace")?;
1357 
            if e.len() != 2 {
75167672 Andy McCall 1358 
                return Err(ObjectError::Schema(
1359 
                    "replace: expected [node, records]".into(),
1360 
                ));
252e8cb2 Andy McCall ↶ 1361 
            }
75167672 Andy McCall 1362 
            let node = NodeId::from_slice(o::bytes(&e[0], "node")?)
1363 
                .ok_or_else(|| ObjectError::Schema("node: expected 16 bytes".into()))?;
252e8cb2 Andy McCall ↶ 1364 
            let mut recs = Vec::new();
1365 
            for rec in o::array(&e[1], "records")? {
1366 
                let x = o::array(rec, "record")?;
1367 
                if x.len() != 3 {
1368 
                    return Err(ObjectError::Schema("record: expected 3 fields".into()));
1369 
                }
1370 
                recs.push((o::oref(&x[0], "change")?, opt(&x[1])?, opt(&x[2])?));
1371 
            }
1372 
            st.replaces.insert(node, recs);
1373 
        }
1374 
        Ok(st)
1375 
    }
1376
ff0af1ee unknown 1377 
    pub fn validate(&self) -> Result<(), StateError> {
1378 
        for (h, c) in &self.changes {
1379 
            for d in &c.deps {
1380 
                if !self.changes.contains_key(d) {
1381 
                    return Err(StateError::MissingDep(*d, *h));
1382 
                }
1383 
            }
1384 
        }
1385 
        Ok(())
1386 
    }
1387
a4fad5b0 Andy McCall ↶ 1388 
    fn apply_with(&mut self, h: ChangeHash, c: Change, texts: Vec<TextRef>) {
ff0af1ee unknown 1389 
        for (i, op) in c.tree_ops.iter().enumerate() {
1390 
            self.tree.apply(h, i as u32, &resolve_tree_op(op, h));
1391 
        }
e8d38e47 Andy McCall ↶ 1392 
        if let Some(deferred) = self.deferred.as_mut() {
86e1824f Andy McCall ↶ 1393 
            // History only: edits of files not built wait, grouped per file,
1394 
            // with the texts of inserts read without their lines.
1395 
            let mut texts = texts.into_iter();
1396 
            let mut per_node: HashMap<NodeId, (Vec<Edit>, Vec<TextRef>)> = HashMap::new();
e8d38e47 Andy McCall ↶ 1397 
            for e in c.edits {
1398 
                match e {
1399 
                    Edit::Replace { node, old, new } => {
1400 
                        self.replaces.entry(node).or_default().push((h, old, new))
1401 
                    }
86e1824f Andy McCall ↶ 1402 
                    e => {
1403 
                        let slot = per_node.entry(e.node()).or_default();
1404 
                        if matches!(&e, Edit::Insert { lines, .. } if lines.is_empty()) {
1405 
                            slot.1.extend(texts.next());
1406 
                        }
1407 
                        slot.0.push(e);
1408 
                    }
e8d38e47 Andy McCall ↶ 1409 
                }
1410 
            }
86e1824f Andy McCall ↶ 1411 
            for (node, (edits, node_texts)) in per_node {
e8d38e47 Andy McCall ↶ 1412 
                match self.files.get_mut(&node) {
86e1824f Andy McCall ↶ 1413 
                    Some(g) => {
1414 
                        assert!(
1415 
                            node_texts.is_empty(),
1416 
                            "a change read without its text applied to a built graph"
1417 
                        );
1418 
                        apply_file_edits(Arc::make_mut(g), h, edits)
1419 
                    }
1420 
                    None => {
f6451fbb Andy McCall ↶ 1421 
                        let d = Arc::make_mut(deferred.entry(node).or_default());
3f1b8fe2 Andy McCall ↶ 1422 
                        let b = d.body_mut();
1423 
                        b.edits.push((h, edits));
1424 
                        b.texts.extend(node_texts);
f9575918 Andy McCall ↶ 1425 
                        d.key = Default::default();
86e1824f Andy McCall ↶ 1426 
                    }
e8d38e47 Andy McCall ↶ 1427 
                }
1428 
            }
1429 
            return;
1430 
        }
86e1824f Andy McCall ↶ 1431 
        assert!(
1432 
            texts.is_empty(),
1433 
            "a change read without its text applied to a full state"
1434 
        );
ff0af1ee unknown 1435 
        let mut counters: HashMap<NodeId, u32> = HashMap::new();
0bdc3f91 Andy McCall ↶ 1436 
        for e in c.edits {
ff0af1ee unknown 1437 
            match e {
75167672 Andy McCall 1438 
                Edit::Insert {
1439 
                    node,
1440 
                    after,
1441 
                    before,
1442 
                    lines,
1443 
                } => {
0bdc3f91 Andy McCall ↶ 1444 
                    let idx = counters.entry(node).or_default();
ff0af1ee unknown 1445 
                    let first = *idx;
1446 
                    *idx += lines.len() as u32;
dfb23a3a Andy McCall ↶ 1447 
                    Arc::make_mut(self.files.entry(node).or_default()).insert_owned(
75167672 Andy McCall 1448 
                        h,
1449 
                        first,
1450 
                        vertex(after.resolve(h)),
1451 
                        vertex(before.resolve(h)),
1452 
                        lines,
1453 
                    );
ff0af1ee unknown 1454 
                }
1455 
                Edit::Delete { node, atoms } => {
dfb23a3a Andy McCall ↶ 1456 
                    let g = Arc::make_mut(self.files.entry(node).or_default());
ff0af1ee unknown 1457 
                    for r in atoms {
1458 
                        g.delete(h, &r.resolve(h));
1459 
                    }
1460 
                }
1461 
                Edit::Replace { node, old, new } => {
0bdc3f91 Andy McCall ↶ 1462 
                    self.replaces.entry(node).or_default().push((h, old, new));
ff0af1ee unknown 1463 
                }
1464 
            }
1465 
        }
1466 
    }
1467
1468 
    /// Transitive dependencies of `h`, excluding `h` itself.
119bbf50 Andy McCall ↶ 1469 
    pub fn closure(&self, h: &ChangeHash) -> Arc<HashSet<ChangeHash>> {
1470 
        if let Some(c) = self.closure.lock().unwrap().get(h) {
ff0af1ee unknown 1471 
            return c.clone();
1472 
        }
1473 
        let mut out = HashSet::new();
75167672 Andy McCall 1474 
        let mut stack: Vec<ChangeHash> = self
1475 
            .changes
1476 
            .get(h)
1477 
            .map(|c| c.deps.clone())
1478 
            .unwrap_or_default();
ff0af1ee unknown 1479 
        while let Some(d) = stack.pop() {
1480 
            if out.insert(d) {
1481 
                if let Some(c) = self.changes.get(&d) {
1482 
                    stack.extend(c.deps.iter().copied());
1483 
                }
1484 
            }
1485 
        }
119bbf50 Andy McCall ↶ 1486 
        let rc = Arc::new(out);
1487 
        self.closure.lock().unwrap().insert(*h, rc.clone());
ff0af1ee unknown 1488 
        rc
1489 
    }
1490
1491 
    /// Changes that no other change depends on directly, sorted.
1492 
    pub fn heads(&self) -> Vec<ChangeHash> {
75167672 Andy McCall 1493 
        let depended: HashSet<&ChangeHash> =
1494 
            self.changes.values().flat_map(|c| c.deps.iter()).collect();
1495 
        let mut heads: Vec<ChangeHash> = self
1496 
            .changes
1497 
            .keys()
1498 
            .filter(|h| !depended.contains(h))
1499 
            .copied()
1500 
            .collect();
ff0af1ee unknown 1501 
        heads.sort();
1502 
        heads
1503 
    }
1504
07eb99be Andy McCall ↶ 1505 
    /// Maximal elements among `hashes` (those not in the closure of another),
1506 
    /// sorted. One walk down from all of them at once: whatever the walk
1507 
    /// reaches is below some other element. Linear in the changes reached,
1508 
    /// where comparing every pair's closures was quadratic in the number
1509 
    /// of heads, which a bookmark of independent changes has many of.
ff0af1ee unknown 1510 
    pub fn maximal(&self, hashes: &[ChangeHash]) -> Vec<ChangeHash> {
1511 
        let set: BTreeSet<ChangeHash> = hashes.iter().copied().collect();
07eb99be Andy McCall ↶ 1512 
        let mut below: HashSet<ChangeHash> = HashSet::new();
1513 
        let mut stack: Vec<ChangeHash> = set
1514 
            .iter()
1515 
            .filter_map(|h| self.changes.get(h))
1516 
            .flat_map(|c| c.deps.iter().copied())
1517 
            .collect();
1518 
        while let Some(d) = stack.pop() {
1519 
            if below.insert(d) {
1520 
                if let Some(c) = self.changes.get(&d) {
1521 
                    stack.extend(c.deps.iter().copied());
1522 
                }
1523 
            }
1524 
        }
1525 
        set.into_iter().filter(|h| !below.contains(h)).collect()
ff0af1ee unknown 1526 
    }
1527
1528 
    pub fn materialize_file(&self, node: &NodeId) -> Materialized {
e8d38e47 Andy McCall ↶ 1529 
        self.graph(node)
75167672 Andy McCall 1530 
            .map(|g| g.materialize(self))
1531 
            .unwrap_or_default()
ff0af1ee unknown 1532 
    }
1533
1534 
    /// Live lines of a text node in materialized order.
1535 
    pub fn live_lines(&self, node: &NodeId) -> Vec<(AtomKey, Vec<u8>)> {
e8d38e47 Andy McCall ↶ 1536 
        let Some(g) = self.graph(node) else {
75167672 Andy McCall 1537 
            return vec![];
1538 
        };
ff0af1ee unknown 1539 
        let m = g.materialize(self);
75167672 Andy McCall 1540 
        m.live_atoms()
1541 
            .into_iter()
1542 
            .map(|a| (a, g.content(&a).unwrap_or_default().to_vec()))
1543 
            .collect()
ff0af1ee unknown 1544 
    }
1545
1546 
    /// Live blobs of an opaque node: every `new` that no later `Replace` retired.
1547 
    pub fn live_blobs(&self, node: &NodeId) -> Vec<ObjectRef> {
62794ecc Andy McCall ↶ 1548 
        let mut live: Vec<ObjectRef> = self
1549 
            .live_replaces(node)
1550 
            .into_iter()
1551 
            .map(|(_, n)| n)
75167672 Andy McCall 1552 
            .collect();
ff0af1ee unknown 1553 
        live.sort();
1554 
        live.dedup();
1555 
        live
1556 
    }
1557
62794ecc Andy McCall ↶ 1558 
    /// The replace records whose blob is live, with the change that set it
1559 
    /// (spec §9.3). A record's blob is superseded by a later replacement of
1560 
    /// that blob: one whose change depends on the record's change, as every
1561 
    /// replacement depends on the change that made its old blob current
1562 
    /// (§8.1). Two replacements that do not know each other both stay live
1563 
    /// (a replace conflict), and a file reverted to an earlier blob keeps it.
1564 
    /// A replacement without that dependency, from before the rule, is read
1565 
    /// as before: it supersedes every record that did not come after it.
1566 
    pub fn live_replaces(&self, node: &NodeId) -> Vec<(ChangeHash, ObjectRef)> {
1567 
        let Some(rs) = self.replaces.get(node) else {
1568 
            return vec![];
1569 
        };
1570 
        let knows_its_old = |s: &ChangeHash, old: &ObjectRef| {
1571 
            rs.iter()
1572 
                .any(|(q, _, n)| n.as_ref() == Some(old) && q != s && self.closure(s).contains(q))
1573 
        };
1574 
        rs.iter()
1575 
            .filter_map(|(c, _, n)| n.map(|n| (*c, n)))
1576 
            .filter(|(c, n)| {
1577 
                !rs.iter().any(|(s, o, _)| {
1578 
                    s != c
1579 
                        && *o == Some(*n)
1580 
                        && (self.closure(s).contains(c)
1581 
                            || (!knows_its_old(s, n) && !self.closure(c).contains(s)))
1582 
                })
1583 
            })
1584 
            .collect()
1585 
    }
1586
ff0af1ee unknown 1587 
    /// Short label for conflict markers: `changeid-prefix "message"`.
1588 
    pub fn label(&self, h: &ChangeHash) -> String {
1589 
        match self.changes.get(h) {
75167672 Andy McCall 1590 
            Some(c) => format!(
1591 
                "{} \"{}\"",
1592 
                c.change_id.short(8),
1593 
                c.message.lines().next().unwrap_or("")
1594 
            ),
ff0af1ee unknown 1595 
            None => format!("#{}", h.short(12)),
1596 
        }
1597 
    }
1598
20247a03 Andy McCall ↶ 1599 
    /// For resolving a conflicted text node (spec §9.6): the live atoms that
1600 
    /// are not part of any conflict region in order, every live atom that is
1601 
    /// part of a region, and every change that contributed to a region.
50a046e4 Andy McCall ↶ 1602 
    /// The changes that introduced the live blobs of an opaque node, for a
1603 
    /// replace conflict (spec §9.3).
1604 
    pub fn blob_contributors(&self, node: &NodeId, blobs: &[ObjectRef]) -> Vec<ChangeHash> {
1605 
        let mut out: Vec<ChangeHash> = Vec::new();
1606 
        for (h, _, new) in self.replaces.get(node).map(|v| v.as_slice()).unwrap_or(&[]) {
1607 
            if new.is_some_and(|b| blobs.contains(&b)) && !out.contains(h) {
1608 
                out.push(*h);
1609 
            }
1610 
        }
1611 
        out.sort();
1612 
        out
1613 
    }
1614
20247a03 Andy McCall ↶ 1615 
    pub fn conflict_regions(&self, node: &NodeId) -> ConflictRegions {
1616 
        let mut out = ConflictRegions::default();
e8d38e47 Andy McCall ↶ 1617 
        let Some(g) = self.graph(node) else {
75167672 Andy McCall 1618 
            return out;
1619 
        };
20247a03 Andy McCall ↶ 1620 
        let m = g.materialize(self);
1621 
        let mut contributors = BTreeSet::new();
1622 
        for seg in &m.segments {
1623 
            match seg {
1624 
                crate::graph::Segment::Lines(atoms) => {
1625 
                    for a in atoms {
75167672 Andy McCall 1626 
                        out.plain
1627 
                            .push((*a, g.content(a).unwrap_or_default().to_vec()));
20247a03 Andy McCall ↶ 1628 
                    }
1629 
                }
1630 
                crate::graph::Segment::Conflict(sides) => {
1631 
                    for side in sides {
1632 
                        for a in side {
1633 
                            out.region_atoms.push(*a);
1634 
                            contributors.insert(a.0);
1635 
                        }
1636 
                    }
1637 
                }
1638 
                crate::graph::Segment::Zombie { deleted, inserted } => {
1639 
                    for a in deleted {
1640 
                        contributors.insert(a.0);
1641 
                        contributors.extend(g.deleters(a).copied());
1642 
                    }
1643 
                    for a in inserted {
1644 
                        out.region_atoms.push(*a);
1645 
                        contributors.insert(a.0);
1646 
                    }
1647 
                }
1648 
            }
1649 
        }
1650 
        out.contributors = contributors.into_iter().collect();
1651 
        out
1652 
    }
1653
ff0af1ee unknown 1654 
    pub fn render_file(&self, node: &NodeId) -> (Vec<u8>, Materialized) {
e8d38e47 Andy McCall ↶ 1655 
        let Some(g) = self.graph(node) else {
75167672 Andy McCall 1656 
            return (Vec::new(), Materialized::default());
1657 
        };
ff0af1ee unknown 1658 
        let m = g.materialize(self);
1659 
        let bytes = g.render(&m, &|h| self.label(h));
1660 
        (bytes, m)
1661 
    }
1662
e7ddd552 Andy McCall ↶ 1663 
    /// Every file rendered, in parallel: files are independent, and
1664 
    /// rendering them is most of a snapshot's cost in a large tree.
ff0af1ee unknown 1665 
    pub fn materialize(&self) -> Snapshot {
e7ddd552 Andy McCall ↶ 1666 
        use rayon::prelude::*;
e8d38e47 Andy McCall ↶ 1667 
        self.require_full("materializing a state");
ff0af1ee unknown 1668 
        let tree = self.tree.view();
e7ddd552 Andy McCall ↶ 1669 
        let entries: Vec<(&String, &crate::tree::TreeEntry)> = tree.entries.iter().collect();
1670 
        let rendered: Vec<(String, FileState)> = entries
1671 
            .par_iter()
1672 
            .map(|(path, e)| (path.to_string(), self.file_state(e)))
1673 
            .collect();
1674 
        let files: BTreeMap<String, FileState> = rendered.into_iter().collect();
cc7a0056 Andy McCall ↶ 1675 
        Snapshot {
1676 
            tree,
1677 
            files,
1678 
            unrendered: BTreeSet::new(),
1679 
        }
1680 
    }
1681
1682 
    /// Like [`State::materialize`], leaving the text files of nodes in
1683 
    /// `skip` unrendered (listed in [`Snapshot::unrendered`]); every other
1684 
    /// file's graph must be loaded. For a caller that already knows those
1685 
    /// files are unchanged and not conflicted.
1686 
    pub fn materialize_except(&self, skip: &HashSet<NodeId>) -> Snapshot {
d616faf5 Andy McCall ↶ 1687 
        self.materialize_leaving(|_, e| skip.contains(&e.node))
1688 
    }
1689
1690 
    /// As [`State::materialize_except`], rendering only the text files at
1691 
    /// `render` (a few, where the caller knows the rest unchanged).
1692 
    pub fn materialize_only(&self, render: &std::collections::HashSet<&str>) -> Snapshot {
1693 
        self.materialize_leaving(|p, _| !render.contains(p))
1694 
    }
1695
10b4fd43 Andy McCall ↶ 1696 
    /// As [`State::materialize_except`], rendering only the text files of
1697 
    /// the nodes in `render` (a change's edited files), without a set of
1698 
    /// every other file to leave out.
1699 
    pub fn materialize_nodes(&self, render: &HashSet<NodeId>) -> Snapshot {
1700 
        self.materialize_leaving(|_, e| !render.contains(&e.node))
1701 
    }
1702
d616faf5 Andy McCall ↶ 1703 
    fn materialize_leaving(
1704 
        &self,
1705 
        leave: impl Fn(&str, &crate::tree::TreeEntry) -> bool + Sync,
1706 
    ) -> Snapshot {
cc7a0056 Andy McCall ↶ 1707 
        use rayon::prelude::*;
1708 
        let tree = self.tree.view();
1709 
        let entries: Vec<(&String, &crate::tree::TreeEntry)> = tree.entries.iter().collect();
1710 
        let rendered: Vec<(String, FileState, bool)> = entries
1711 
            .par_iter()
1712 
            .map(|(path, e)| {
d616faf5 Andy McCall ↶ 1713 
                if e.kind == NodeKind::File && !e.mode.opaque && leave(path, e) {
cc7a0056 Andy McCall ↶ 1714 
                    let f = FileState {
1715 
                        node: e.node,
1716 
                        kind: e.kind,
1717 
                        mode: e.mode,
1718 
                        content: FileContent::Text {
1719 
                            bytes: Vec::new(),
1720 
                            materialized: Materialized::default(),
1721 
                        },
1722 
                    };
1723 
                    (path.to_string(), f, true)
1724 
                } else {
1725 
                    (path.to_string(), self.file_state(e), false)
1726 
                }
1727 
            })
1728 
            .collect();
36e51aa8 Andy McCall ↶ 1729 
        // In the view's path order, so the maps are built without searching.
1730 
        let unrendered: BTreeSet<String> = rendered
1731 
            .iter()
1732 
            .filter(|(_, _, skipped)| *skipped)
1733 
            .map(|(p, _, _)| p.clone())
1734 
            .collect();
1735 
        let files: BTreeMap<String, FileState> =
1736 
            rendered.into_iter().map(|(p, f, _)| (p, f)).collect();
cc7a0056 Andy McCall ↶ 1737 
        Snapshot {
1738 
            tree,
1739 
            files,
1740 
            unrendered,
1741 
        }
e7ddd552 Andy McCall ↶ 1742 
    }
1743
2306a4d2 Andy McCall ↶ 1744 
    /// A snapshot of only `paths` (those `view` has), `view` being this
1745 
    /// state's tree view: for a caller that works from what changed. The
1746 
    /// graphs of those text files must be loaded.
1747 
    pub fn materialize_paths<'p>(
1748 
        &self,
1749 
        view: crate::tree::TreeView,
1750 
        paths: impl IntoIterator<Item = &'p str>,
1751 
    ) -> Snapshot {
1752 
        let files = paths
1753 
            .into_iter()
1754 
            .filter_map(|p| Some((p.to_string(), self.file_state(view.entries.get(p)?))))
1755 
            .collect();
1756 
        Snapshot {
1757 
            tree: view,
1758 
            files,
1759 
            unrendered: BTreeSet::new(),
1760 
        }
1761 
    }
1762
e7ddd552 Andy McCall ↶ 1763 
    fn file_state(&self, e: &crate::tree::TreeEntry) -> FileState {
1764 
        {
ff0af1ee unknown 1765 
            let content = match e.kind {
1766 
                NodeKind::Dir => FileContent::Dir,
75167672 Andy McCall 1767 
                NodeKind::Symlink | NodeKind::Subrepo => FileContent::Opaque {
1768 
                    blobs: self.live_blobs(&e.node),
1769 
                },
1770 
                NodeKind::File if e.mode.opaque => FileContent::Opaque {
1771 
                    blobs: self.live_blobs(&e.node),
1772 
                },
ff0af1ee unknown 1773 
                NodeKind::File => {
1774 
                    let (bytes, materialized) = self.render_file(&e.node);
75167672 Andy McCall 1775 
                    FileContent::Text {
1776 
                        bytes,
1777 
                        materialized,
1778 
                    }
ff0af1ee unknown 1779 
                }
1780 
            };
e7ddd552 Andy McCall ↶ 1781 
            FileState {
1782 
                node: e.node,
1783 
                kind: e.kind,
1784 
                mode: e.mode,
1785 
                content,
1786 
            }
ff0af1ee unknown 1787 
        }
1788 
    }
1789 
}
1790
1791 
impl DepOracle for State {
1792 
    fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
1793 
        a == b || self.closure(a).contains(b)
1794 
    }
1795 
}
1796
1797 
#[cfg(test)]
1798 
mod tests {
1799 
    use super::*;
1800 
    use crate::ids::ChangeId;
1801 
    use crate::objects::{AtomRange, ChangeKind, Hlc, OpRef};
1802
1803 
    fn change(deps: Vec<ChangeHash>, tree_ops: Vec<TreeOp>, edits: Vec<Edit>) -> Change {
1804 
        let mut c = Change {
6f8aeb99 Andy McCall ↶ 1805 
            version: crate::objects::CHANGE_VERSION,
ff0af1ee unknown 1806 
            change_id: ChangeId::random(),
1807 
            deps,
1808 
            author: ObjectRef::ZERO,
75167672 Andy McCall 1809 
            hlc: Hlc {
1810 
                wall_ms: 1,
1811 
                logical: 0,
1812 
            },
ff0af1ee unknown 1813 
            message: "m".into(),
1814 
            tree_ops,
1815 
            edits,
1816 
            kind: ChangeKind::Normal,
1817 
        };
1818 
        c.normalize();
1819 
        c
1820 
    }
1821
1822 
    #[test]
1823 
    fn build_edit_and_materialize() {
1824 
        let mut st = State::new();
1825 
        let f = NodeId::random();
1826 
        let c1 = change(
1827 
            vec![],
75167672 Andy McCall 1828 
            vec![TreeOp::AddNode {
1829 
                node: f,
1830 
                kind: NodeKind::File,
1831 
                mode: Mode::TEXT,
1832 
                parent: NodeId::ROOT,
1833 
                name: "a.txt".into(),
1834 
            }],
1835 
            vec![Edit::Insert {
1836 
                node: f,
1837 
                after: AtomRef::Start,
1838 
                before: AtomRef::End,
01a47cd7 Andy McCall ↶ 1839 
                lines: vec![b"one\n".to_vec(), b"two\n".to_vec()].into(),
75167672 Andy McCall 1840 
            }],
ff0af1ee unknown 1841 
        );
1842 
        let h1 = st.add(c1).unwrap();
1843 
        // Depends on h1: append a line and delete "one".
1844 
        let c2 = change(
1845 
            vec![h1],
1846 
            vec![],
1847 
            vec![
75167672 Andy McCall 1848 
                Edit::Delete {
1849 
                    node: f,
1850 
                    atoms: vec![AtomRange {
1851 
                        change: h1,
1852 
                        from: 0,
1853 
                        to: 1,
1854 
                    }],
1855 
                },
1856 
                Edit::Insert {
1857 
                    node: f,
1858 
                    after: AtomRef::Atom {
1859 
                        change: h1,
1860 
                        index: 1,
1861 
                    },
1862 
                    before: AtomRef::End,
01a47cd7 Andy McCall ↶ 1863 
                    lines: vec![b"three\n".to_vec()].into(),
75167672 Andy McCall 1864 
                },
ff0af1ee unknown 1865 
            ],
1866 
        );
1867 
        let h2 = st.add(c2).unwrap();
1868 
        assert_eq!(st.heads(), vec![h2]);
1869 
        assert!(st.depends_on(&h2, &h1));
1870 
        assert!(!st.depends_on(&h1, &h2));
1871 
        let snap = st.materialize();
1872 
        assert!(!snap.is_conflicted());
1873 
        let a = &snap.files["a.txt"];
1874 
        assert!(matches!(&a.content, FileContent::Text { bytes, .. } if bytes == b"two\nthree\n"));
1875 
        assert_eq!(st.live_lines(&f).len(), 2);
1876 
    }
1877
1878 
    #[test]
1879 
    fn missing_dependency_is_rejected() {
1880 
        let mut st = State::new();
1881 
        let c = change(vec![ObjectRef([1; 32])], vec![], vec![]);
1882 
        assert!(matches!(st.add(c), Err(StateError::MissingDep(..))));
1883 
    }
1884
1885 
    #[test]
1886 
    fn self_references_and_multi_insert_indexing() {
1887 
        let mut st = State::new();
1888 
        let f = NodeId::random();
75167672 Andy McCall 1889 
        let me = OpRef {
1890 
            change: ObjectRef::ZERO,
1891 
            index: 0,
1892 
        };
ff0af1ee unknown 1893 
        let c1 = change(
1894 
            vec![],
1895 
            vec![
75167672 Andy McCall 1896 
                TreeOp::AddNode {
1897 
                    node: f,
1898 
                    kind: NodeKind::File,
1899 
                    mode: Mode::TEXT,
1900 
                    parent: NodeId::ROOT,
1901 
                    name: "x".into(),
1902 
                },
1903 
                TreeOp::SetMode {
1904 
                    node: f,
1905 
                    old: me,
1906 
                    mode: Mode {
1907 
                        exec: true,
1908 
                        opaque: false,
1909 
                    },
1910 
                },
ff0af1ee unknown 1911 
            ],
1912 
            vec![
75167672 Andy McCall 1913 
                Edit::Insert {
1914 
                    node: f,
1915 
                    after: AtomRef::Start,
1916 
                    before: AtomRef::End,
01a47cd7 Andy McCall ↶ 1917 
                    lines: vec![b"a\n".to_vec(), b"c\n".to_vec()].into(),
75167672 Andy McCall 1918 
                },
ff0af1ee unknown 1919 
                // Insert between the two lines just inserted, using self references.
1920 
                Edit::Insert {
1921 
                    node: f,
75167672 Andy McCall 1922 
                    after: AtomRef::Atom {
1923 
                        change: ObjectRef::ZERO,
1924 
                        index: 0,
1925 
                    },
1926 
                    before: AtomRef::Atom {
1927 
                        change: ObjectRef::ZERO,
1928 
                        index: 1,
1929 
                    },
01a47cd7 Andy McCall ↶ 1930 
                    lines: vec![b"b\n".to_vec()].into(),
ff0af1ee unknown 1931 
                },
1932 
            ],
1933 
        );
1934 
        st.add(c1).unwrap();
1935 
        let snap = st.materialize();
1936 
        let x = &snap.files["x"];
75167672 Andy McCall 1937 
        assert_eq!(
1938 
            x.mode,
1939 
            Mode {
1940 
                exec: true,
1941 
                opaque: false
1942 
            }
1943 
        );
ff0af1ee unknown 1944 
        assert!(matches!(&x.content, FileContent::Text { bytes, .. } if bytes == b"a\nb\nc\n"));
1945 
    }
1946
1947 
    #[test]
1948 
    fn opaque_replace_and_conflict() {
1949 
        let mut st = State::new();
1950 
        let f = NodeId::random();
1951 
        let b1 = ObjectRef([1; 32]);
1952 
        let b2 = ObjectRef([2; 32]);
1953 
        let b3 = ObjectRef([3; 32]);
75167672 Andy McCall 1954 
        let h1 = st
1955 
            .add(change(
1956 
                vec![],
1957 
                vec![TreeOp::AddNode {
1958 
                    node: f,
1959 
                    kind: NodeKind::File,
1960 
                    mode: Mode::OPAQUE,
1961 
                    parent: NodeId::ROOT,
1962 
                    name: "img".into(),
1963 
                }],
1964 
                vec![Edit::Replace {
1965 
                    node: f,
1966 
                    old: None,
1967 
                    new: Some(b1),
1968 
                }],
1969 
            ))
1970 
            .unwrap();
1971 
        assert_eq!(st.live_blobs(&f), vec![b1]);
1972 
        st.add(change(
1973 
            vec![h1],
1974 
            vec![],
1975 
            vec![Edit::Replace {
1976 
                node: f,
1977 
                old: Some(b1),
1978 
                new: Some(b2),
1979 
            }],
1980 
        ))
1981 
        .unwrap();
1982 
        st.add(change(
1983 
            vec![h1],
ff0af1ee unknown 1984 
            vec![],
75167672 Andy McCall 1985 
            vec![Edit::Replace {
1986 
                node: f,
1987 
                old: Some(b1),
1988 
                new: Some(b3),
1989 
            }],
ff0af1ee unknown 1990 
        ))
1991 
        .unwrap();
1992 
        let snap = st.materialize();
1993 
        assert!(snap.is_conflicted());
75167672 Andy McCall 1994 
        assert!(
1995 
            matches!(&snap.files["img"].content, FileContent::Opaque { blobs } if blobs == &vec![b2, b3])
1996 
        );
ff0af1ee unknown 1997 
    }
1998
1999 
    #[test]
252e8cb2 Andy McCall ↶ 2000 
    fn checkpoint_payload_round_trip_and_replay() {
2001 
        let mut st = State::new();
2002 
        let f = NodeId::random();
75167672 Andy McCall 2003 
        let h1 = st
2004 
            .add(change(
2005 
                vec![],
2006 
                vec![TreeOp::AddNode {
2007 
                    node: f,
2008 
                    kind: NodeKind::File,
2009 
                    mode: Mode::TEXT,
2010 
                    parent: NodeId::ROOT,
2011 
                    name: "a".into(),
2012 
                }],
2013 
                vec![Edit::Insert {
2014 
                    node: f,
2015 
                    after: AtomRef::Start,
2016 
                    before: AtomRef::End,
01a47cd7 Andy McCall ↶ 2017 
                    lines: vec![b"1\n".to_vec(), b"2\n".to_vec()].into(),
75167672 Andy McCall 2018 
                }],
2019 
            ))
2020 
            .unwrap();
2021 
        let h2 = st
2022 
            .add(change(
2023 
                vec![h1],
2024 
                vec![],
2025 
                vec![Edit::Delete {
2026 
                    node: f,
2027 
                    atoms: vec![AtomRange {
2028 
                        change: h1,
2029 
                        from: 0,
2030 
                        to: 1,
2031 
                    }],
2032 
                }],
2033 
            ))
2034 
            .unwrap();
252e8cb2 Andy McCall ↶ 2035 
        let payload = st.checkpoint_payload();
2036 
        let back = State::from_checkpoint_payload(&payload).unwrap();
2037 
        assert_eq!(back.len(), 2);
2038 
        assert_eq!(back.heads(), vec![h2]);
2039 
        assert_eq!(back.get(&h1).unwrap().message, "m");
2040 
        assert_eq!(back.checkpoint_payload(), payload, "deterministic");
2041 
        // Replaying a further change onto the restored state equals a full build.
75167672 Andy McCall 2042 
        let c3 = change(
2043 
            vec![h2],
2044 
            vec![],
2045 
            vec![Edit::Insert {
2046 
                node: f,
2047 
                after: AtomRef::Atom {
2048 
                    change: h1,
2049 
                    index: 1,
2050 
                },
2051 
                before: AtomRef::End,
01a47cd7 Andy McCall ↶ 2052 
                lines: vec![b"3\n".to_vec()].into(),
75167672 Andy McCall 2053 
            }],
2054 
        );
252e8cb2 Andy McCall ↶ 2055 
        let mut full = st.clone();
2056 
        full.add(c3.clone()).unwrap();
2057 
        let mut restored = back;
2058 
        restored.add(c3).unwrap();
2059 
        let (a, b) = (full.materialize(), restored.materialize());
75167672 Andy McCall 2060 
        assert_eq!(
2061 
            a.files.keys().collect::<Vec<_>>(),
2062 
            b.files.keys().collect::<Vec<_>>()
2063 
        );
252e8cb2 Andy McCall ↶ 2064 
        assert_eq!(a.files["a"].content, b.files["a"].content);
75167672 Andy McCall 2065 
        assert!(
2066 
            matches!(&b.files["a"].content, FileContent::Text { bytes, .. } if bytes == b"2\n3\n")
2067 
        );
252e8cb2 Andy McCall ↶ 2068 
        assert!(State::from_checkpoint_payload(b"nonsense").is_err());
e8d38e47 Andy McCall ↶ 2069 
    }
2070
2071 
    /// History-only states (O10f): the same state as a full load once its
2072 
    /// graphs are built, by replay and from a version 2 checkpoint with
2073 
    /// later changes; unloaded graphs are never read as empty.
cc7a0056 Andy McCall ↶ 2074 
    #[test]
2075 
    fn graph_keys_change_exactly_when_a_graph_does() {
2076 
        let (f, g) = (NodeId::random(), NodeId::random());
2077 
        let add = |node: NodeId, name: &str| TreeOp::AddNode {
2078 
            node,
2079 
            kind: NodeKind::File,
2080 
            mode: Mode::TEXT,
2081 
            parent: NodeId::ROOT,
2082 
            name: name.into(),
2083 
        };
2084 
        let ins = |node: NodeId, line: &[u8]| Edit::Insert {
2085 
            node,
2086 
            after: AtomRef::Start,
2087 
            before: AtomRef::End,
01a47cd7 Andy McCall ↶ 2088 
            lines: vec![line.to_vec()].into(),
cc7a0056 Andy McCall ↶ 2089 
        };
2090 
        let c1 = change(
2091 
            vec![],
2092 
            vec![add(f, "f"), add(g, "g")],
2093 
            vec![ins(f, b"f\n"), ins(g, b"g\n")],
2094 
        );
2095 
        let h1 = c1.hash();
2096 
        let c2 = change(vec![h1], vec![], vec![ins(g, b"g2\n")]);
2097 
        let h2 = c2.hash();
2098 
        let c3 = change(vec![h2], vec![], vec![ins(f, b"f2\n")]);
2099 
        let load = |cs: &[&Change]| {
2100 
            let mut st = State::new_history_only();
2101 
            for c in cs {
2102 
                st.add((*c).clone()).unwrap();
2103 
            }
2104 
            st
2105 
        };
2106 
        let s1 = load(&[&c1]);
2107 
        let s2 = load(&[&c1, &c2]);
2108 
        let s3 = load(&[&c1, &c2, &c3]);
2109 
        let key = |s: &State, n: &NodeId| s.graph_key(n).unwrap();
2110 
        assert_eq!(key(&s1, &f), key(&load(&[&c1]), &f), "same state, same key");
2111 
        assert_eq!(key(&s1, &f), key(&s2, &f), "an edit elsewhere keeps it");
2112 
        assert_ne!(key(&s1, &g), key(&s2, &g), "an edit of the file changes it");
2113 
        assert_ne!(key(&s2, &f), key(&s3, &f));
2114 
        assert_ne!(key(&s1, &f), key(&s1, &g), "different files differ");
2115 
        let mut built = load(&[&c1]);
a4fad5b0 Andy McCall ↶ 2116 
        built
2117 
            .load_graphs(&[f], |_| unreachable!(), |_| unreachable!())
2118 
            .unwrap();
cc7a0056 Andy McCall ↶ 2119 
        assert!(built.graph_key(&f).is_none(), "a built graph has no key");
2120 
        let mut full = State::new();
2121 
        full.add(c1.clone()).unwrap();
2122 
        assert!(full.graph_key(&f).is_none(), "nor has a full state");
2123
2124 
        // Through a version 2 checkpoint of c1, keys name its graph blobs
2125 
        // or inline values: stable across loads, changed by later edits.
2126 
        let graphs = full.checkpoint_file_graphs();
2127 
        let index = full.checkpoint_index(&graphs, |enc| {
2128 
            crate::hash::hash_object(crate::hash::ObjectType::Blob, enc)
2129 
        });
2130 
        let cp = |extra: &[&Change]| {
2131 
            let mut st = State::from_checkpoint_history(&index).unwrap();
2132 
            for c in extra {
2133 
                st.add((*c).clone()).unwrap();
2134 
            }
2135 
            st
2136 
        };
2137 
        assert_eq!(key(&cp(&[]), &f), key(&cp(&[]), &f));
2138 
        assert_eq!(key(&cp(&[]), &f), key(&cp(&[&c2]), &f));
2139 
        assert_ne!(key(&cp(&[]), &g), key(&cp(&[&c2]), &g));
2140 
        assert_ne!(key(&cp(&[&c2]), &f), key(&cp(&[&c2, &c3]), &f));
2141
2142 
        // Partial rendering: skipped files are listed and empty, the others
2143 
        // render as in a full state.
2144 
        let mut part = load(&[&c1, &c2]);
a4fad5b0 Andy McCall ↶ 2145 
        part.load_graphs(&[g], |_| unreachable!(), |_| unreachable!())
2146 
            .unwrap();
cc7a0056 Andy McCall ↶ 2147 
        let snap = part.materialize_except(&[f].into_iter().collect());
2148 
        assert_eq!(snap.unrendered, ["f".to_string()].into_iter().collect());
2149 
        let mut whole = State::new();
2150 
        whole.add(c1.clone()).unwrap();
2151 
        whole.add(c2.clone()).unwrap();
2152 
        assert_eq!(snap.files["g"], whole.materialize().files["g"]);
2153 
        assert!(
2154 
            matches!(&snap.files["f"].content, FileContent::Text { bytes, .. } if bytes.is_empty())
2155 
        );
2156 
    }
2157
e8d38e47 Andy McCall ↶ 2158 
    #[test]
2159 
    fn history_only_states_build_the_same_graphs_on_demand() {
2160 
        let small = NodeId::random();
2161 
        let big = NodeId::random();
2162 
        let add = |node: NodeId, name: &str| TreeOp::AddNode {
2163 
            node,
2164 
            kind: NodeKind::File,
2165 
            mode: Mode::TEXT,
2166 
            parent: NodeId::ROOT,
2167 
            name: name.into(),
2168 
        };
01a47cd7 Andy McCall ↶ 2169 
        let lines: crate::lines::Lines = (0..300)
e8d38e47 Andy McCall ↶ 2170 
            .map(|i| format!("line {i}\n").into_bytes())
2171 
            .collect();
2172 
        let c1 = change(
2173 
            vec![],
2174 
            vec![add(small, "small"), add(big, "big")],
2175 
            vec![
2176 
                Edit::Insert {
2177 
                    node: small,
2178 
                    after: AtomRef::Start,
2179 
                    before: AtomRef::End,
01a47cd7 Andy McCall ↶ 2180 
                    lines: vec![b"x\n".to_vec()].into(),
e8d38e47 Andy McCall ↶ 2181 
                },
2182 
                Edit::Insert {
2183 
                    node: big,
2184 
                    after: AtomRef::Start,
2185 
                    before: AtomRef::End,
2186 
                    lines,
2187 
                },
2188 
            ],
2189 
        );
2190 
        let h1 = c1.hash();
2191 
        let c2 = change(
2192 
            vec![h1],
2193 
            vec![],
2194 
            vec![
2195 
                Edit::Delete {
2196 
                    node: big,
2197 
                    atoms: vec![AtomRange {
2198 
                        change: h1,
2199 
                        from: 2,
2200 
                        to: 9,
2201 
                    }],
2202 
                },
2203 
                Edit::Insert {
2204 
                    node: big,
2205 
                    after: AtomRef::Atom {
2206 
                        change: h1,
2207 
                        index: 20,
2208 
                    },
2209 
                    before: AtomRef::Atom {
2210 
                        change: h1,
2211 
                        index: 21,
2212 
                    },
01a47cd7 Andy McCall ↶ 2213 
                    lines: vec![b"new a\n".to_vec(), b"new b\n".to_vec()].into(),
e8d38e47 Andy McCall ↶ 2214 
                },
2215 
                Edit::Insert {
2216 
                    node: small,
2217 
                    after: AtomRef::Atom {
2218 
                        change: h1,
2219 
                        index: 0,
2220 
                    },
2221 
                    before: AtomRef::End,
01a47cd7 Andy McCall ↶ 2222 
                    lines: vec![b"y\n".to_vec()].into(),
e8d38e47 Andy McCall ↶ 2223 
                },
2224 
            ],
2225 
        );
2226 
        let h2 = c2.hash();
2227 
        let c3 = change(
2228 
            vec![h2],
2229 
            vec![],
2230 
            vec![Edit::Delete {
2231 
                node: small,
2232 
                atoms: vec![AtomRange {
2233 
                    change: h1,
2234 
                    from: 0,
2235 
                    to: 1,
2236 
                }],
2237 
            }],
2238 
        );
2239
2240 
        let mut full = State::new();
2241 
        for c in [&c1, &c2, &c3] {
2242 
            full.add(c.clone()).unwrap();
2243 
        }
2244 
        // By replay: nothing built until asked, then exactly the full graphs.
2245 
        let mut hist = State::new_history_only();
2246 
        for c in [&c1, &c2, &c3] {
2247 
            hist.add(c.clone()).unwrap();
2248 
        }
2249 
        assert!(!hist.is_full() && hist.files.is_empty(), "no graph built");
2250 
        assert_eq!(hist.len(), 3);
a4fad5b0 Andy McCall ↶ 2251 
        hist.load_graphs(
2252 
            &[big],
2253 
            |_| unreachable!("no checkpoint"),
2254 
            |_| unreachable!(),
2255 
        )
2256 
        .unwrap();
e8d38e47 Andy McCall ↶ 2257 
        assert_eq!(
2258 
            hist.render_file(&big).0,
2259 
            full.render_file(&big).0,
2260 
            "one file on its own"
2261 
        );
2262 
        assert!(!hist.is_full());
a4fad5b0 Andy McCall ↶ 2263 
        hist.load_graphs(&[small, big], |_| unreachable!(), |_| unreachable!())
2264 
            .unwrap();
e8d38e47 Andy McCall ↶ 2265 
        assert!(hist.is_full());
2266 
        assert_eq!(hist.checkpoint_payload(), full.checkpoint_payload());
2267
2268 
        // From a version 2 checkpoint of c1+c2, then c3 applied later.
2269 
        let mut base = State::new();
2270 
        base.add(c1.clone()).unwrap();
2271 
        base.add(c2.clone()).unwrap();
2272 
        let graphs = base.checkpoint_file_graphs();
2273 
        let mut blobs: HashMap<ObjectRef, Vec<u8>> = HashMap::new();
2274 
        let index = base.checkpoint_index(&graphs, |enc| {
2275 
            let r = crate::hash::hash_object(crate::hash::ObjectType::Blob, enc);
2276 
            blobs.insert(r, enc.to_vec());
2277 
            r
2278 
        });
2279 
        let mut from_cp = State::from_checkpoint_history(&index).unwrap();
2280 
        from_cp.add(c3.clone()).unwrap();
2281 
        assert!(!from_cp.is_full());
2282 
        let mut fetched = 0;
2283 
        from_cp
a4fad5b0 Andy McCall ↶ 2284 
            .load_graphs(
2285 
                &[small, big],
2286 
                |refs| {
2287 
                    fetched += refs.len();
2288 
                    refs.iter()
2289 
                        .map(|r| {
2290 
                            blobs
2291 
                                .get(r)
2292 
                                .cloned()
2293 
                                .ok_or_else(|| ObjectError::Schema("missing".into()))
2294 
                        })
2295 
                        .collect()
2296 
                },
2297 
                |_| unreachable!(),
2298 
            )
e8d38e47 Andy McCall ↶ 2299 
            .unwrap();
2300 
        assert_eq!(
2301 
            fetched, 1,
2302 
            "the large graph's blob, in one batch; the small one was inline"
2303 
        );
2304 
        assert_eq!(from_cp.checkpoint_payload(), full.checkpoint_payload());
2305 
    }
2306
2307 
    #[test]
2308 
    #[should_panic(expected = "was not loaded")]
2309 
    fn a_history_only_state_never_reads_an_unloaded_graph_as_empty() {
2310 
        let f = NodeId::random();
2311 
        let mut st = State::new_history_only();
2312 
        st.add(change(
2313 
            vec![],
2314 
            vec![TreeOp::AddNode {
2315 
                node: f,
2316 
                kind: NodeKind::File,
2317 
                mode: Mode::TEXT,
2318 
                parent: NodeId::ROOT,
2319 
                name: "a".into(),
2320 
            }],
2321 
            vec![Edit::Insert {
2322 
                node: f,
2323 
                after: AtomRef::Start,
2324 
                before: AtomRef::End,
01a47cd7 Andy McCall ↶ 2325 
                lines: vec![b"a\n".to_vec()].into(),
e8d38e47 Andy McCall ↶ 2326 
            }],
2327 
        ))
2328 
        .unwrap();
2329 
        st.render_file(&f);
2330 
    }
2331
2332 
    #[test]
2333 
    #[should_panic(expected = "needs every file graph")]
2334 
    fn materializing_a_history_only_state_is_refused() {
2335 
        let f = NodeId::random();
2336 
        let mut st = State::new_history_only();
2337 
        st.add(change(
2338 
            vec![],
2339 
            vec![TreeOp::AddNode {
2340 
                node: f,
2341 
                kind: NodeKind::File,
2342 
                mode: Mode::TEXT,
2343 
                parent: NodeId::ROOT,
2344 
                name: "a".into(),
2345 
            }],
2346 
            vec![Edit::Insert {
2347 
                node: f,
2348 
                after: AtomRef::Start,
2349 
                before: AtomRef::End,
01a47cd7 Andy McCall ↶ 2350 
                lines: vec![b"a\n".to_vec()].into(),
e8d38e47 Andy McCall ↶ 2351 
            }],
2352 
        ))
2353 
        .unwrap();
2354 
        st.materialize();
afaba5f1 Andy McCall ↶ 2355 
    }
2356
2357 
    /// Version 2 payloads (spec §11): small graphs inline, large ones by
2358 
    /// blob; the state read back is the same as from version 1.
2359 
    #[test]
2360 
    fn checkpoint_index_round_trip_matches_version_1() {
2361 
        let mut st = State::new();
2362 
        let small = NodeId::random();
2363 
        let big = NodeId::random();
2364 
        let add = |node: NodeId, name: &str| TreeOp::AddNode {
2365 
            node,
2366 
            kind: NodeKind::File,
2367 
            mode: Mode::TEXT,
2368 
            parent: NodeId::ROOT,
2369 
            name: name.into(),
2370 
        };
01a47cd7 Andy McCall ↶ 2371 
        let big_lines: crate::lines::Lines = (0..400)
afaba5f1 Andy McCall ↶ 2372 
            .map(|i| format!("line {i} of a long file\n").into_bytes())
2373 
            .collect();
2374 
        let h1 = st
2375 
            .add(change(
2376 
                vec![],
2377 
                vec![add(small, "small"), add(big, "big")],
2378 
                vec![
2379 
                    Edit::Insert {
2380 
                        node: small,
2381 
                        after: AtomRef::Start,
2382 
                        before: AtomRef::End,
01a47cd7 Andy McCall ↶ 2383 
                        lines: vec![b"x\n".to_vec()].into(),
afaba5f1 Andy McCall ↶ 2384 
                    },
2385 
                    Edit::Insert {
2386 
                        node: big,
2387 
                        after: AtomRef::Start,
2388 
                        before: AtomRef::End,
2389 
                        lines: big_lines,
2390 
                    },
2391 
                ],
2392 
            ))
2393 
            .unwrap();
2394 
        st.add(change(
2395 
            vec![h1],
2396 
            vec![],
2397 
            vec![Edit::Delete {
2398 
                node: big,
2399 
                atoms: vec![AtomRange {
2400 
                    change: h1,
2401 
                    from: 3,
2402 
                    to: 7,
2403 
                }],
2404 
            }],
2405 
        ))
2406 
        .unwrap();
2407
2408 
        let graphs = st.checkpoint_file_graphs();
2409 
        let mut blobs: HashMap<ObjectRef, Vec<u8>> = HashMap::new();
2410 
        let index = st.checkpoint_index(&graphs, |enc| {
2411 
            let r = crate::hash::hash_object(crate::hash::ObjectType::Blob, enc);
2412 
            blobs.insert(r, enc.to_vec());
2413 
            r
2414 
        });
2415 
        assert_eq!(blobs.len(), 1, "only the large graph is a blob of its own");
2416 
        assert_eq!(
2417 
            State::checkpoint_graph_refs(&index).unwrap(),
2418 
            blobs.keys().copied().collect::<Vec<_>>()
2419 
        );
2420 
        assert!(
2421 
            State::checkpoint_graph_refs(&st.checkpoint_payload())
2422 
                .unwrap()
2423 
                .is_empty(),
2424 
            "version 1 names none"
2425 
        );
2426 
        assert!(index.len() < st.checkpoint_payload().len());
2427
2428 
        let back = State::from_checkpoint(&index, |refs| {
2429 
            refs.iter()
2430 
                .map(|r| {
2431 
                    blobs
2432 
                        .get(r)
2433 
                        .cloned()
2434 
                        .ok_or_else(|| ObjectError::Schema("missing".into()))
2435 
                })
2436 
                .collect()
2437 
        })
2438 
        .unwrap();
2439 
        assert_eq!(
2440 
            back.checkpoint_payload(),
2441 
            st.checkpoint_payload(),
2442 
            "the same state as version 1"
2443 
        );
2444 
        assert_eq!(
2445 
            back.materialize().files["big"].content,
2446 
            st.materialize().files["big"].content
2447 
        );
2448 
        // Deterministic: the same state gives the same index.
2449 
        assert_eq!(
2450 
            back.checkpoint_index(&back.checkpoint_file_graphs(), |enc| {
2451 
                crate::hash::hash_object(crate::hash::ObjectType::Blob, enc)
2452 
            }),
2453 
            index
2454 
        );
2455 
        // A missing graph blob is an error, not an empty file.
2456 
        assert!(
2457 
            State::from_checkpoint(&index, |_| Err(ObjectError::Schema("gone".into()))).is_err()
2458 
        );
2459 
        assert!(
2460 
            State::from_checkpoint_payload(&index).is_err(),
2461 
            "version 2 needs its blobs"
2462 
        );
2463 
        // Version 1 payloads still read, and unknown versions do not.
2464 
        assert!(State::from_checkpoint(&st.checkpoint_payload(), |_| unreachable!()).is_ok());
2465 
        let mut v3 = cbor::decode(&index).unwrap();
2466 
        if let Value::Map(m) = &mut v3 {
2467 
            m.insert(0, Value::Uint(3));
2468 
        }
2469 
        assert!(State::from_checkpoint(&cbor::encode(&v3), |_| unreachable!()).is_err());
252e8cb2 Andy McCall ↶ 2470 
    }
2471
2472 
    #[test]
ff0af1ee unknown 2473 
    fn maximal_elements() {
2474 
        let mut st = State::new();
2475 
        let h1 = st.add(change(vec![], vec![], vec![])).unwrap();
2476 
        let h2 = st.add(change(vec![h1], vec![], vec![])).unwrap();
2477 
        let h3 = st.add(change(vec![], vec![], vec![])).unwrap();
2478 
        let mut m = st.maximal(&[h1, h2, h3]);
2479 
        m.sort();
2480 
        let mut want = vec![h2, h3];
2481 
        want.sort();
2482 
        assert_eq!(m, want);
2483 
        assert_eq!(st.heads(), want);
2484 
    }
07eb99be Andy McCall ↶ 2485
2486 
    /// The one-walk `maximal` agrees with the definition (not in the
2487 
    /// closure of another element) on random graphs, with repeated and
2488 
    /// unknown hashes among the input.
2489 
    #[test]
2490 
    fn maximal_matches_its_definition() {
2491 
        use rand::{Rng, SeedableRng};
2492 
        let mut rng = rand::rngs::StdRng::seed_from_u64(7);
2493 
        for _ in 0..20 {
2494 
            let mut st = State::new();
2495 
            let mut all: Vec<ChangeHash> = Vec::new();
2496 
            for _ in 0..60 {
2497 
                let deps: Vec<ChangeHash> =
2498 
                    all.iter().copied().filter(|_| rng.gen_bool(0.05)).collect();
2499 
                all.push(st.add(change(deps, vec![], vec![])).unwrap());
2500 
            }
2501 
            let mut pick: Vec<ChangeHash> =
2502 
                all.iter().copied().filter(|_| rng.gen_bool(0.4)).collect();
2503 
            pick.extend(pick.clone().into_iter().take(3));
2504 
            pick.push(ObjectRef([0xee; 32]));
2505 
            let set: BTreeSet<ChangeHash> = pick.iter().copied().collect();
2506 
            let want: Vec<ChangeHash> = set
2507 
                .iter()
2508 
                .filter(|h| !set.iter().any(|o| o != *h && st.closure(o).contains(h)))
2509 
                .copied()
2510 
                .collect();
2511 
            assert_eq!(st.maximal(&pick), want);
2512 
            assert_eq!(st.maximal(&all), st.heads());
2513 
        }
2514 
    }
ff0af1ee unknown 2515 
}