OXYGENHUB
◆ v0.4.1 oxygen / crates / oxy-core / src / objects.rs
56.0 KiB · Rust · last changed First commit: 12 s and 2.1 GB on the Linux tree (refs #41) 1 month ago source blame history raw
1 
//! Typed objects and their canonical encodings (spec §6, §7, §13.2).
2 
//!
3 
//! Encoding conventions not fixed by the spec text are defined here:
4 
//! - Enum-like items (`TreeOp`, `Edit`) are maps whose key 0 is the variant tag.
5 
//! - An `OpRef`/atom reference is `[bytes32, uint]`; `AtomRef::Start` is `0`
6 
//!   and `AtomRef::End` is `1`.
7 
//! - A `Mode` is an unsigned integer: bit 0 = executable, bit 1 = opaque.
8 
//! - `NodeKind`: 0 = file, 1 = dir, 2 = symlink.
9
10 
use crate::cbor::{self, Value};
11 
use crate::hash::{hash_object, ChangeHash, KeyId, ObjectRef, ObjectType};
12 
use crate::ids::{ChangeId, NodeId};
13 
use crate::lines::Lines;
14 
use std::collections::BTreeMap;
15
16 
pub const FORMAT_VERSION: u64 = 1;
17
18 
/// The change format writers produce (spec §6.1). Version 2 stores each
19 
/// large insert's lines as a text blob holding a CBOR array of them;
20 
/// version 3 holds the lines' bytes themselves when splitting them by the
21 
/// line rule gives them back. Readers accept 1 to 3, and a change keeps
22 
/// the version it was made in, so its hash never moves.
23 
pub const CHANGE_VERSION: u64 = 3;
24
25 
/// How a text blob holds an insert's lines (spec §7.4).
26 
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
27 
pub enum TextForm {
28 
    /// A CBOR array of the lines' byte strings: version 2.
29 
    Cbor,
30 
    /// The lines' bytes, split again by the line rule: version 3.
31 
    Raw,
32 
    /// A CBOR array in a version 3 change, for lines the line rule would
33 
    /// not split back (marked by key 7): never for lines it would.
34 
    CborFallback,
35 
}
36
37 
/// In a version 2 change, an insert whose lines encode (as a CBOR array of
38 
/// byte strings) to at least this many bytes is stored as a text blob
39 
/// holding exactly that encoding; a shorter one is inline (spec §6.1).
40 
pub const TEXT_BLOB_MIN: usize = 4096;
41
42 
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
43 
pub enum ObjectError {
44 
    #[error("cbor: {0}")]
45 
    Cbor(#[from] cbor::CborError),
46 
    #[error("schema: {0}")]
47 
    Schema(String),
48 
}
49
50 
pub(crate) fn schema<T>(msg: impl Into<String>) -> Result<T, ObjectError> {
51 
    Err(ObjectError::Schema(msg.into()))
52 
}
53
54 
pub(crate) type Map = BTreeMap<u64, Value>;
55
56 
pub(crate) fn field<'a>(m: &'a Map, k: u64, what: &str) -> Result<&'a Value, ObjectError> {
57 
    m.get(&k)
58 
        .ok_or_else(|| ObjectError::Schema(format!("missing field {k} ({what})")))
59 
}
60 
pub(crate) fn uint(v: &Value, what: &str) -> Result<u64, ObjectError> {
61 
    v.as_uint()
62 
        .ok_or_else(|| ObjectError::Schema(format!("{what}: expected unsigned integer")))
63 
}
64 
pub(crate) fn u32_(v: &Value, what: &str) -> Result<u32, ObjectError> {
65 
    u32::try_from(uint(v, what)?).map_err(|_| ObjectError::Schema(format!("{what}: exceeds u32")))
66 
}
67 
pub(crate) fn text<'a>(v: &'a Value, what: &str) -> Result<&'a str, ObjectError> {
68 
    v.as_text()
69 
        .ok_or_else(|| ObjectError::Schema(format!("{what}: expected text")))
70 
}
71 
pub(crate) fn array<'a>(v: &'a Value, what: &str) -> Result<&'a [Value], ObjectError> {
72 
    v.as_array()
73 
        .ok_or_else(|| ObjectError::Schema(format!("{what}: expected array")))
74 
}
75 
pub(crate) fn map<'a>(v: &'a Value, what: &str) -> Result<&'a Map, ObjectError> {
76 
    v.as_map()
77 
        .ok_or_else(|| ObjectError::Schema(format!("{what}: expected map")))
78 
}
79 
pub(crate) fn bytes<'a>(v: &'a Value, what: &str) -> Result<&'a [u8], ObjectError> {
80 
    v.as_bytes()
81 
        .ok_or_else(|| ObjectError::Schema(format!("{what}: expected bytes")))
82 
}
83 
pub(crate) fn oref(v: &Value, what: &str) -> Result<ObjectRef, ObjectError> {
84 
    ObjectRef::from_slice(bytes(v, what)?)
85 
        .ok_or_else(|| ObjectError::Schema(format!("{what}: expected 32 bytes")))
86 
}
87 
pub(crate) fn node_id(v: &Value, what: &str) -> Result<NodeId, ObjectError> {
88 
    NodeId::from_slice(bytes(v, what)?)
89 
        .ok_or_else(|| ObjectError::Schema(format!("{what}: expected 16 bytes")))
90 
}
91 
pub(crate) fn check_version(m: &Map) -> Result<(), ObjectError> {
92 
    let v = uint(field(m, 0, "version")?, "version")?;
93 
    if v != FORMAT_VERSION {
94 
        let exe = std::env::current_exe()
95 
            .map(|p| format!(" at {}", p.display()))
96 
            .unwrap_or_default();
97 
        let which = format!("oxy {}{exe}", crate::VERSION);
98 
        return schema(if v > FORMAT_VERSION {
99 
            format!(
100 
                "this data is format {v}, written by a newer oxy, and {which} reads format {FORMAT_VERSION}: install the current oxy, and check that no older copy comes first on PATH"
101 
            )
102 
        } else {
103 
            format!(
104 
                "this data is format {v}, written by an older oxy, and {which} reads format {FORMAT_VERSION} only"
105 
            )
106 
        });
107 
    }
108 
    Ok(())
109 
}
110
111 
// ---------------------------------------------------------------- Hlc
112
113 
/// Hybrid logical clock (spec §6.4).
114 
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
115 
pub struct Hlc {
116 
    pub wall_ms: u64,
117 
    pub logical: u32,
118 
}
119
120 
impl Hlc {
121 
    pub fn now() -> Hlc {
122 
        let wall_ms = std::time::SystemTime::now()
123 
            .duration_since(std::time::UNIX_EPOCH)
124 
            .map(|d| d.as_millis() as u64)
125 
            .unwrap_or(0);
126 
        Hlc {
127 
            wall_ms,
128 
            logical: 0,
129 
        }
130 
    }
131 
    pub(crate) fn to_value(self) -> Value {
132 
        Value::map([
133 
            (0, Value::Uint(self.wall_ms)),
134 
            (1, Value::Uint(self.logical as u64)),
135 
        ])
136 
    }
137 
    pub(crate) fn from_value(v: &Value) -> Result<Hlc, ObjectError> {
138 
        let m = map(v, "hlc")?;
139 
        Ok(Hlc {
140 
            wall_ms: uint(field(m, 0, "hlc.wall_ms")?, "hlc.wall_ms")?,
141 
            logical: u32_(field(m, 1, "hlc.logical")?, "hlc.logical")?,
142 
        })
143 
    }
144 
}
145
146 
// ---------------------------------------------------------------- tree
147
148 
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
149 
pub enum NodeKind {
150 
    File,
151 
    Dir,
152 
    Symlink,
153 
    /// A nested repository pinned to a state (spec §7.8); content is a pin.
154 
    Subrepo,
155 
}
156
157 
impl NodeKind {
158 
    pub(crate) fn tag(self) -> u64 {
159 
        match self {
160 
            NodeKind::File => 0,
161 
            NodeKind::Dir => 1,
162 
            NodeKind::Symlink => 2,
163 
            NodeKind::Subrepo => 3,
164 
        }
165 
    }
166 
    pub(crate) fn from_tag(t: u64) -> Result<NodeKind, ObjectError> {
167 
        Ok(match t {
168 
            0 => NodeKind::File,
169 
            1 => NodeKind::Dir,
170 
            2 => NodeKind::Symlink,
171 
            3 => NodeKind::Subrepo,
172 
            _ => return schema(format!("unknown node kind {t}")),
173 
        })
174 
    }
175 
}
176
177 
/// Executable bit plus content mode (spec §7.1, §7.5).
178 
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default, PartialOrd, Ord)]
179 
pub struct Mode {
180 
    pub exec: bool,
181 
    pub opaque: bool,
182 
}
183
184 
impl Mode {
185 
    pub const TEXT: Mode = Mode {
186 
        exec: false,
187 
        opaque: false,
188 
    };
189 
    pub const OPAQUE: Mode = Mode {
190 
        exec: false,
191 
        opaque: true,
192 
    };
193 
    pub(crate) fn bits(self) -> u64 {
194 
        (self.exec as u64) | ((self.opaque as u64) << 1)
195 
    }
196 
    pub(crate) fn from_bits(b: u64) -> Result<Mode, ObjectError> {
197 
        if b > 3 {
198 
            return schema(format!("unknown mode bits {b}"));
199 
        }
200 
        Ok(Mode {
201 
            exec: b & 1 != 0,
202 
            opaque: b & 2 != 0,
203 
        })
204 
    }
205 
}
206
207 
/// Reference to a tree operation of some change: the placement or mode atom it
208 
/// introduced. `change == ObjectRef::ZERO` means this change.
209 
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
210 
pub struct OpRef {
211 
    pub change: ChangeHash,
212 
    pub index: u32,
213 
}
214
215 
impl OpRef {
216 
    fn to_value(self) -> Value {
217 
        Value::Array(vec![
218 
            Value::Bytes(self.change.0.to_vec()),
219 
            Value::Uint(self.index as u64),
220 
        ])
221 
    }
222 
    fn from_value(v: &Value, what: &str) -> Result<OpRef, ObjectError> {
223 
        let a = array(v, what)?;
224 
        if a.len() != 2 {
225 
            return schema(format!("{what}: expected [hash, index]"));
226 
        }
227 
        Ok(OpRef {
228 
            change: oref(&a[0], what)?,
229 
            index: u32_(&a[1], what)?,
230 
        })
231 
    }
232 
    /// Replace a self reference with the concrete change hash.
233 
    pub fn resolve(self, me: ChangeHash) -> OpRef {
234 
        if self.change.is_zero() {
235 
            OpRef { change: me, ..self }
236 
        } else {
237 
            self
238 
        }
239 
    }
240 
}
241
242 
#[derive(Debug, Clone, PartialEq, Eq)]
243 
pub enum TreeOp {
244 
    AddNode {
245 
        node: NodeId,
246 
        kind: NodeKind,
247 
        mode: Mode,
248 
        parent: NodeId,
249 
        name: String,
250 
    },
251 
    RemoveNode {
252 
        node: NodeId,
253 
        placement: OpRef,
254 
    },
255 
    Move {
256 
        node: NodeId,
257 
        old: OpRef,
258 
        parent: NodeId,
259 
        name: String,
260 
    },
261 
    SetMode {
262 
        node: NodeId,
263 
        old: OpRef,
264 
        mode: Mode,
265 
    },
266 
}
267
268 
/// Names must be valid, non-empty, not `.`/`..`, and free of `/` and NUL (spec §7.1).
269 
pub fn validate_name(name: &str) -> Result<(), ObjectError> {
270 
    if name.is_empty() || name == "." || name == ".." || name.contains('/') || name.contains('\0') {
271 
        return schema(format!("invalid placement name {name:?}"));
272 
    }
273 
    Ok(())
274 
}
275
276 
impl TreeOp {
277 
    pub fn node(&self) -> NodeId {
278 
        match self {
279 
            TreeOp::AddNode { node, .. }
280 
            | TreeOp::RemoveNode { node, .. }
281 
            | TreeOp::Move { node, .. }
282 
            | TreeOp::SetMode { node, .. } => *node,
283 
        }
284 
    }
285
286 
    fn to_value(&self) -> Value {
287 
        let nid = |n: &NodeId| Value::Bytes(n.0.to_vec());
288 
        match self {
289 
            TreeOp::AddNode {
290 
                node,
291 
                kind,
292 
                mode,
293 
                parent,
294 
                name,
295 
            } => Value::map([
296 
                (0, Value::Uint(0)),
297 
                (1, nid(node)),
298 
                (2, Value::Uint(kind.tag())),
299 
                (3, Value::Uint(mode.bits())),
300 
                (4, nid(parent)),
301 
                (5, Value::Text(name.clone())),
302 
            ]),
303 
            TreeOp::RemoveNode { node, placement } => Value::map([
304 
                (0, Value::Uint(1)),
305 
                (1, nid(node)),
306 
                (2, placement.to_value()),
307 
            ]),
308 
            TreeOp::Move {
309 
                node,
310 
                old,
311 
                parent,
312 
                name,
313 
            } => Value::map([
314 
                (0, Value::Uint(2)),
315 
                (1, nid(node)),
316 
                (2, old.to_value()),
317 
                (4, nid(parent)),
318 
                (5, Value::Text(name.clone())),
319 
            ]),
320 
            TreeOp::SetMode { node, old, mode } => Value::map([
321 
                (0, Value::Uint(3)),
322 
                (1, nid(node)),
323 
                (2, old.to_value()),
324 
                (3, Value::Uint(mode.bits())),
325 
            ]),
326 
        }
327 
    }
328
329 
    fn from_value(v: &Value) -> Result<TreeOp, ObjectError> {
330 
        let m = map(v, "tree_op")?;
331 
        let tag = uint(field(m, 0, "tree_op tag")?, "tree_op tag")?;
332 
        let node = node_id(field(m, 1, "tree_op.node")?, "tree_op.node")?;
333 
        let op = match tag {
334 
            0 => {
335 
                let name = text(field(m, 5, "name")?, "name")?.to_owned();
336 
                validate_name(&name)?;
337 
                TreeOp::AddNode {
338 
                    node,
339 
                    kind: NodeKind::from_tag(uint(field(m, 2, "kind")?, "kind")?)?,
340 
                    mode: Mode::from_bits(uint(field(m, 3, "mode")?, "mode")?)?,
341 
                    parent: node_id(field(m, 4, "parent")?, "parent")?,
342 
                    name,
343 
                }
344 
            }
345 
            1 => TreeOp::RemoveNode {
346 
                node,
347 
                placement: OpRef::from_value(field(m, 2, "placement")?, "placement")?,
348 
            },
349 
            2 => {
350 
                let name = text(field(m, 5, "name")?, "name")?.to_owned();
351 
                validate_name(&name)?;
352 
                TreeOp::Move {
353 
                    node,
354 
                    old: OpRef::from_value(field(m, 2, "old")?, "old")?,
355 
                    parent: node_id(field(m, 4, "parent")?, "parent")?,
356 
                    name,
357 
                }
358 
            }
359 
            3 => TreeOp::SetMode {
360 
                node,
361 
                old: OpRef::from_value(field(m, 2, "old")?, "old")?,
362 
                mode: Mode::from_bits(uint(field(m, 3, "mode")?, "mode")?)?,
363 
            },
364 
            _ => return schema(format!("unknown tree op tag {tag}")),
365 
        };
366 
        if node.is_root() {
367 
            return schema("tree op on the root node");
368 
        }
369 
        Ok(op)
370 
    }
371 
}
372
373 
// ---------------------------------------------------------------- edits
374
375 
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
376 
pub enum AtomRef {
377 
    Start,
378 
    End,
379 
    Atom { change: ChangeHash, index: u32 },
380 
}
381
382 
impl AtomRef {
383 
    fn to_value(self) -> Value {
384 
        match self {
385 
            AtomRef::Start => Value::Uint(0),
386 
            AtomRef::End => Value::Uint(1),
387 
            AtomRef::Atom { change, index } => Value::Array(vec![
388 
                Value::Bytes(change.0.to_vec()),
389 
                Value::Uint(index as u64),
390 
            ]),
391 
        }
392 
    }
393 
    fn from_value(v: &Value, what: &str) -> Result<AtomRef, ObjectError> {
394 
        match v {
395 
            Value::Uint(0) => Ok(AtomRef::Start),
396 
            Value::Uint(1) => Ok(AtomRef::End),
397 
            Value::Array(a) if a.len() == 2 => Ok(AtomRef::Atom {
398 
                change: oref(&a[0], what)?,
399 
                index: u32_(&a[1], what)?,
400 
            }),
401 
            _ => schema(format!("{what}: expected atom reference")),
402 
        }
403 
    }
404 
    pub fn resolve(self, me: ChangeHash) -> AtomRef {
405 
        match self {
406 
            AtomRef::Atom { change, index } if change.is_zero() => {
407 
                AtomRef::Atom { change: me, index }
408 
            }
409 
            other => other,
410 
        }
411 
    }
412 
}
413
414 
/// Half-open range of atoms introduced by one change.
415 
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
416 
pub struct AtomRange {
417 
    pub change: ChangeHash,
418 
    pub from: u32,
419 
    pub to: u32,
420 
}
421
422 
impl AtomRange {
423 
    fn to_value(self) -> Value {
424 
        Value::Array(vec![
425 
            Value::Bytes(self.change.0.to_vec()),
426 
            Value::Uint(self.from as u64),
427 
            Value::Uint(self.to as u64),
428 
        ])
429 
    }
430 
    fn from_value(v: &Value) -> Result<AtomRange, ObjectError> {
431 
        let a = array(v, "atom range")?;
432 
        if a.len() != 3 {
433 
            return schema("atom range: expected [hash, from, to]");
434 
        }
435 
        let r = AtomRange {
436 
            change: oref(&a[0], "range.change")?,
437 
            from: u32_(&a[1], "range.from")?,
438 
            to: u32_(&a[2], "range.to")?,
439 
        };
440 
        if r.from >= r.to {
441 
            return schema("atom range: empty or inverted");
442 
        }
443 
        Ok(r)
444 
    }
445 
    pub fn resolve(self, me: ChangeHash) -> AtomRange {
446 
        if self.change.is_zero() {
447 
            AtomRange { change: me, ..self }
448 
        } else {
449 
            self
450 
        }
451 
    }
452 
}
453
454 
#[derive(Debug, Clone, PartialEq, Eq)]
455 
pub enum Edit {
456 
    Insert {
457 
        node: NodeId,
458 
        after: AtomRef,
459 
        before: AtomRef,
460 
        lines: crate::lines::Lines,
461 
    },
462 
    Delete {
463 
        node: NodeId,
464 
        atoms: Vec<AtomRange>,
465 
    },
466 
    Replace {
467 
        node: NodeId,
468 
        old: Option<ObjectRef>,
469 
        new: Option<ObjectRef>,
470 
    },
471 
}
472
473 
impl Edit {
474 
    pub fn node(&self) -> NodeId {
475 
        match self {
476 
            Edit::Insert { node, .. } | Edit::Delete { node, .. } | Edit::Replace { node, .. } => {
477 
                *node
478 
            }
479 
        }
480 
    }
481
482 
    /// Whether this insert is stored as a text blob in a change of `version`.
483 
    fn stored_text(&self, version: u64) -> bool {
484 
        matches!(self, Edit::Insert { lines, .. }
485 
            if version >= 2 && cbor::byte_strings_len(lines) >= TEXT_BLOB_MIN)
486 
    }
487
488 
    /// The edit's value; `stored` is the text blob of an insert stored as
489 
    /// one, and its form (see [`Change::value_with`], which works them out).
490 
    /// The edit's value; `compact` writes an inline insert's lines as
491 
    /// their encoding rather than a value per line (same bytes encoded).
492 
    fn to_value(&self, stored: Option<(ObjectRef, TextForm)>, compact: bool) -> Value {
493 
        let nid = |n: &NodeId| Value::Bytes(n.0.to_vec());
494 
        let opt = |o: &Option<ObjectRef>| match o {
495 
            Some(r) => Value::Bytes(r.0.to_vec()),
496 
            None => Value::Null,
497 
        };
498 
        match (self, stored) {
499 
            (
500 
                Edit::Insert {
501 
                    node,
502 
                    after,
503 
                    before,
504 
                    lines,
505 
                },
506 
                Some((r, form)),
507 
            ) => {
508 
                let mut fields = vec![
509 
                    (0, Value::Uint(0)),
510 
                    (1, nid(node)),
511 
                    (2, after.to_value()),
512 
                    (3, before.to_value()),
513 
                    (5, Value::Bytes(r.0.to_vec())),
514 
                    (6, Value::Uint(lines.len() as u64)),
515 
                ];
516 
                if form == TextForm::CborFallback {
517 
                    fields.push((7, Value::Uint(1)));
518 
                }
519 
                Value::map(fields)
520 
            }
521 
            (
522 
                Edit::Insert {
523 
                    node,
524 
                    after,
525 
                    before,
526 
                    lines,
527 
                },
528 
                None,
529 
            ) => Value::map([
530 
                (0, Value::Uint(0)),
531 
                (1, nid(node)),
532 
                (2, after.to_value()),
533 
                (3, before.to_value()),
534 
                (
535 
                    4,
536 
                    if compact {
537 
                        Value::Encoded(cbor::encode_byte_strings(lines))
538 
                    } else {
539 
                        Value::Array(lines.iter().map(|l| Value::Bytes(l.to_vec())).collect())
540 
                    },
541 
                ),
542 
            ]),
543 
            (Edit::Delete { node, atoms }, _) => Value::map([
544 
                (0, Value::Uint(1)),
545 
                (1, nid(node)),
546 
                (
547 
                    2,
548 
                    Value::Array(atoms.iter().map(|r| r.to_value()).collect()),
549 
                ),
550 
            ]),
551 
            (Edit::Replace { node, old, new }, _) => Value::map([
552 
                (0, Value::Uint(2)),
553 
                (1, nid(node)),
554 
                (2, opt(old)),
555 
                (3, opt(new)),
556 
            ]),
557 
        }
558 
    }
559
560 
    fn from_value(v: &Value, version: u64, resolve: &mut Resolver) -> Result<Edit, ObjectError> {
561 
        let m = map(v, "edit")?;
562 
        let tag = uint(field(m, 0, "edit tag")?, "edit tag")?;
563 
        let node = node_id(field(m, 1, "edit.node")?, "edit.node")?;
564 
        let opt = |v: &Value, what: &str| -> Result<Option<ObjectRef>, ObjectError> {
565 
            if v.is_null() {
566 
                Ok(None)
567 
            } else {
568 
                Ok(Some(oref(v, what)?))
569 
            }
570 
        };
571 
        Ok(match tag {
572 
            0 => {
573 
                let lines = match (m.get(&4), m.get(&5)) {
574 
                    (Some(inline), None) => {
575 
                        let lines = array_lines(inline)?;
576 
                        if version >= 2 && cbor::byte_strings_len(&lines) >= TEXT_BLOB_MIN {
577 
                            return schema("an insert this large is stored as a text blob in a version 2 change");
578 
                        }
579 
                        if lines.is_empty() {
580 
                            return schema("insert with no lines");
581 
                        }
582 
                        lines
583 
                    }
584 
                    (None, Some(text)) if version >= 2 => {
585 
                        let text = oref(text, "insert text")?;
586 
                        let count = u32_(field(m, 6, "insert line count")?, "insert line count")?;
587 
                        if count == 0 {
588 
                            return schema("insert with no lines");
589 
                        }
590 
                        let form = match (version, m.get(&7)) {
591 
                            (2, None) => TextForm::Cbor,
592 
                            (_, None) => TextForm::Raw,
593 
                            (3.., Some(Value::Uint(1))) => TextForm::CborFallback,
594 
                            _ => return schema("unknown text blob form"),
595 
                        };
596 
                        // The resolver checks the count (`text_lines`).
597 
                        resolve(&text, count, form)?
598 
                    }
599 
                    _ => {
600 
                        return schema(
601 
                            "an insert has either its lines or, in a version 2 change, a text blob",
602 
                        )
603 
                    }
604 
                };
605 
                Edit::Insert {
606 
                    node,
607 
                    after: AtomRef::from_value(field(m, 2, "after")?, "after")?,
608 
                    before: AtomRef::from_value(field(m, 3, "before")?, "before")?,
609 
                    lines,
610 
                }
611 
            }
612 
            1 => {
613 
                let atoms = array(field(m, 2, "atoms")?, "atoms")?
614 
                    .iter()
615 
                    .map(AtomRange::from_value)
616 
                    .collect::<Result<Vec<_>, _>>()?;
617 
                if atoms.is_empty() {
618 
                    return schema("delete with no atoms");
619 
                }
620 
                Edit::Delete { node, atoms }
621 
            }
622 
            2 => Edit::Replace {
623 
                node,
624 
                old: opt(field(m, 2, "old")?, "old")?,
625 
                new: opt(field(m, 3, "new")?, "new")?,
626 
            },
627 
            _ => return schema(format!("unknown edit tag {tag}")),
628 
        })
629 
    }
630 
}
631
632 
// ---------------------------------------------------------------- change
633
634 
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
635 
pub enum ChangeKind {
636 
    Normal,
637 
    Resolution,
638 
    WorkingCopy,
639 
}
640
641 
impl ChangeKind {
642 
    pub(crate) fn tag(self) -> u64 {
643 
        match self {
644 
            ChangeKind::Normal => 0,
645 
            ChangeKind::Resolution => 1,
646 
            ChangeKind::WorkingCopy => 2,
647 
        }
648 
    }
649 
    pub(crate) fn from_tag(t: u64) -> Result<ChangeKind, ObjectError> {
650 
        Ok(match t {
651 
            0 => ChangeKind::Normal,
652 
            1 => ChangeKind::Resolution,
653 
            2 => ChangeKind::WorkingCopy,
654 
            _ => return schema(format!("unknown change kind {t}")),
655 
        })
656 
    }
657 
}
658
659 
/// A change (spec §6.1). `deps` is kept sorted and unique by `normalize`.
660 
#[derive(Debug, Clone, PartialEq, Eq)]
661 
pub struct Change {
662 
    /// The format this change is encoded in: [`CHANGE_VERSION`] for a new
663 
    /// one, whatever it was made in for one read back.
664 
    pub version: u64,
665 
    pub change_id: ChangeId,
666 
    pub deps: Vec<ChangeHash>,
667 
    pub author: KeyId,
668 
    pub hlc: Hlc,
669 
    pub message: String,
670 
    pub tree_ops: Vec<TreeOp>,
671 
    pub edits: Vec<Edit>,
672 
    pub kind: ChangeKind,
673 
}
674
675 
impl Change {
676 
    pub fn normalize(&mut self) {
677 
        self.deps.sort();
678 
        self.deps.dedup();
679 
    }
680
681 
    pub fn to_value(&self) -> Value {
682 
        self.value_with(&mut |_| true, false)
683 
    }
684
685 
    /// The text blob of each edit stored as one, `None` for the others;
686 
    /// the stored texts go to `texts`, in order, when it is given. Worked
687 
    /// out on every core, a bounded batch at a time: chunking and hashing
688 
    /// a whole tree's text is most of encoding a change that adds it.
689 
    fn stored_texts(&self, sink: &mut TextSink) -> Vec<Option<(ObjectRef, TextForm)>> {
690 
        use rayon::prelude::*;
691 
        let mut refs: Vec<Option<(ObjectRef, TextForm)>> = vec![None; self.edits.len()];
692 
        let stored: Vec<usize> = (0..self.edits.len())
693 
            .filter(|i| self.edits[*i].stored_text(self.version))
694 
            .collect();
695 
        // At most 256 texts or 32 MiB of them a batch: some directories
696 
        // hold hundreds of generated files of megabytes each, and a batch
697 
        // is copied and compressed at once.
698 
        let mut batches: Vec<&[usize]> = Vec::new();
699 
        let (mut start, mut bytes) = (0, 0usize);
700 
        for (k, i) in stored.iter().enumerate() {
701 
            if let Edit::Insert { lines, .. } = &self.edits[*i] {
702 
                bytes += lines.bytes().len();
703 
            }
704 
            if k + 1 - start == 256 || bytes >= 32 << 20 {
705 
                batches.push(&stored[start..=k]);
706 
                (start, bytes) = (k + 1, 0);
707 
            }
708 
        }
709 
        if start < stored.len() {
710 
            batches.push(&stored[start..]);
711 
        }
712 
        for batch in batches {
713 
            let made: Vec<StoredText> = batch
714 
                .par_iter()
715 
                .map(|i| {
716 
                    let Edit::Insert { lines, .. } = &self.edits[*i] else {
717 
                        unreachable!("only inserts are stored as text");
718 
                    };
719 
                    let form = text_form(self.version, lines);
720 
                    let content = match form {
721 
                        TextForm::Raw => lines.bytes().to_vec(),
722 
                        TextForm::Cbor | TextForm::CborFallback => cbor::encode_byte_strings(lines),
723 
                    };
724 
                    StoredText {
725 
                        blob: Blob::of(&content),
726 
                        content,
727 
                        form,
728 
                    }
729 
                })
730 
                .collect();
731 
            for (i, t) in batch.iter().zip(&made) {
732 
                refs[*i] = Some((t.blob.hash(), t.form));
733 
            }
734 
            if !sink(made) {
735 
                break;
736 
            }
737 
        }
738 
        refs
739 
    }
740
741 
    /// The change's value, its stored texts handed to `sink`; `compact`
742 
    /// as [`Edit::to_value`] takes it, for a value that is only encoded.
743 
    fn value_with(&self, sink: &mut TextSink, compact: bool) -> Value {
744 
        Value::map([
745 
            (0, Value::Uint(self.version)),
746 
            (1, Value::Bytes(self.change_id.0.to_vec())),
747 
            (
748 
                2,
749 
                Value::Array(
750 
                    self.deps
751 
                        .iter()
752 
                        .map(|d| Value::Bytes(d.0.to_vec()))
753 
                        .collect(),
754 
                ),
755 
            ),
756 
            (3, Value::Bytes(self.author.0.to_vec())),
757 
            (4, self.hlc.to_value()),
758 
            (5, Value::Text(self.message.clone())),
759 
            (
760 
                6,
761 
                Value::Array(self.tree_ops.iter().map(|t| t.to_value()).collect()),
762 
            ),
763 
            (
764 
                7,
765 
                Value::Array(
766 
                    self.edits
767 
                        .iter()
768 
                        .zip(self.stored_texts(sink))
769 
                        .map(|(e, stored)| e.to_value(stored, compact))
770 
                        .collect(),
771 
                ),
772 
            ),
773 
            (8, Value::Uint(self.kind.tag())),
774 
            (9, Value::Map(BTreeMap::new())),
775 
        ])
776 
    }
777
778 
    pub fn encode(&self) -> Vec<u8> {
779 
        debug_assert!(
780 
            self.deps.windows(2).all(|w| w[0] < w[1]),
781 
            "deps must be normalized"
782 
        );
783 
        cbor::encode(&self.value_with(&mut |_| true, true))
784 
    }
785
786 
    /// The encoding and the text blobs its large inserts are stored as,
787 
    /// which must be stored with it.
788 
    pub fn encode_parts(&self) -> (Vec<u8>, Vec<StoredText>) {
789 
        debug_assert!(
790 
            self.deps.windows(2).all(|w| w[0] < w[1]),
791 
            "deps must be normalized"
792 
        );
793 
        let mut texts = Vec::new();
794 
        let bytes = cbor::encode(&self.value_with(
795 
            &mut |batch| {
796 
                texts.extend(batch);
797 
                true
798 
            },
799 
            true,
800 
        ));
801 
        (bytes, texts)
802 
    }
803
804 
    /// The encoding, handing the stored texts to `store` a batch at a time
805 
    /// as they are made, so a change adding a whole tree never holds all
806 
    /// its text twice. The first error from `store` is returned.
807 
    pub fn encode_streaming<E>(
808 
        &self,
809 
        mut store: impl FnMut(Vec<StoredText>) -> Result<(), E>,
810 
    ) -> Result<Vec<u8>, E> {
811 
        debug_assert!(
812 
            self.deps.windows(2).all(|w| w[0] < w[1]),
813 
            "deps must be normalized"
814 
        );
815 
        let mut failed = None;
816 
        let value = self.value_with(
817 
            &mut |batch| match store(batch) {
818 
                Ok(()) => true,
819 
                Err(e) => {
820 
                    failed = Some(e);
821 
                    false
822 
                }
823 
            },
824 
            true,
825 
        );
826 
        match failed {
827 
            Some(e) => Err(e),
828 
            None => Ok(cbor::encode(&value)),
829 
        }
830 
    }
831
832 
    /// Whether any insert is stored as a text blob.
833 
    pub fn has_stored_text(&self) -> bool {
834 
        self.edits.iter().any(|e| e.stored_text(self.version))
835 
    }
836
837 
    pub fn hash(&self) -> ChangeHash {
838 
        hash_object(ObjectType::Change, &self.encode())
839 
    }
840
841 
    /// Decode a change that stores no text blob; one that does needs
842 
    /// [`Change::decode_with`] and something to read them from.
843 
    pub fn decode(bytes: &[u8]) -> Result<Change, ObjectError> {
844 
        Self::decode_with(bytes, &mut |r, _, _| {
845 
            schema(format!(
846 
                "text blob {} needs a store to read it from",
847 
                r.short(12)
848 
            ))
849 
        })
850 
    }
851
852 
    /// Decode a change, reading each stored insert's lines with `resolve`
853 
    /// (given the text blob and the line count the insert claims).
854 
    pub fn decode_with(bytes: &[u8], resolve: &mut Resolver) -> Result<Change, ObjectError> {
855 
        let v = cbor::decode(bytes)?;
856 
        Self::from_value_with(&v, resolve)
857 
    }
858
859 
    pub fn from_value(v: &Value) -> Result<Change, ObjectError> {
860 
        Self::from_value_with(v, &mut |r, _, _| {
861 
            schema(format!(
862 
                "text blob {} needs a store to read it from",
863 
                r.short(12)
864 
            ))
865 
        })
866 
    }
867
868 
    pub(crate) fn from_value_with(
869 
        v: &Value,
870 
        resolve: &mut Resolver,
871 
    ) -> Result<Change, ObjectError> {
872 
        let m = map(v, "change")?;
873 
        let version = uint(field(m, 0, "version")?, "version")?;
874 
        if !(1..=CHANGE_VERSION).contains(&version) {
875 
            return schema(format!("unsupported change format version {version}"));
876 
        }
877 
        let change_id = ChangeId::from_slice(bytes(field(m, 1, "change_id")?, "change_id")?)
878 
            .ok_or_else(|| ObjectError::Schema("change_id: expected 16 bytes".into()))?;
879 
        let deps = array(field(m, 2, "deps")?, "deps")?
880 
            .iter()
881 
            .map(|d| oref(d, "dep"))
882 
            .collect::<Result<Vec<_>, _>>()?;
883 
        if !deps.windows(2).all(|w| w[0] < w[1]) {
884 
            return schema("deps must be sorted and unique");
885 
        }
886 
        if deps.iter().any(|d| d.is_zero()) {
887 
            return schema("deps may not contain the self reference");
888 
        }
889 
        let extra = map(field(m, 9, "extra")?, "extra")?;
890 
        if !extra.is_empty() {
891 
            return schema("extra must be empty in format version 1");
892 
        }
893 
        Ok(Change {
894 
            version,
895 
            change_id,
896 
            deps,
897 
            author: oref(field(m, 3, "author")?, "author")?,
898 
            hlc: Hlc::from_value(field(m, 4, "hlc")?)?,
899 
            message: text(field(m, 5, "message")?, "message")?.to_owned(),
900 
            tree_ops: array(field(m, 6, "tree_ops")?, "tree_ops")?
901 
                .iter()
902 
                .map(TreeOp::from_value)
903 
                .collect::<Result<Vec<_>, _>>()?,
904 
            edits: array(field(m, 7, "edits")?, "edits")?
905 
                .iter()
906 
                .map(|e| Edit::from_value(e, version, resolve))
907 
                .collect::<Result<Vec<_>, _>>()?,
908 
            kind: ChangeKind::from_tag(uint(field(m, 8, "kind")?, "kind")?)?,
909 
        })
910 
    }
911 
}
912
913 
/// Reads a stored insert's lines, given the text blob and the line count
914 
/// the insert claims; [`text_lines`] reads and checks a blob's content.
915 
/// A resolver may also return no lines, leaving a placeholder for a reader
916 
/// that fills it in later (history-only states, spec §11).
917 
pub type Resolver<'a> = dyn FnMut(&ObjectRef, u32, TextForm) -> Result<Lines, ObjectError> + 'a;
918
919 
/// Receives the stored texts of a change being encoded, a batch at a
920 
/// time; returns false to stop making more.
921 
type TextSink<'a> = dyn FnMut(Vec<StoredText>) -> bool + 'a;
922
923 
/// Where a history-only load finds an insert's lines when it builds that
924 
/// file's graph (spec §11): it keeps no line until then.
925 
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
926 
pub enum TextRef {
927 
    /// A stored insert: its text blob, line count, and the blob's form.
928 
    Blob(ObjectRef, u32, TextForm),
929 
    /// An inline insert: the byte range of its lines' array in the
930 
    /// encoding of `change`.
931 
    Inline {
932 
        change: ChangeHash,
933 
        start: u32,
934 
        end: u32,
935 
    },
936 
}
937
938 
/// The lines of an inline insert from its array's bytes (see
939 
/// [`TextRef::Inline`]).
940 
pub fn inline_lines(array: &[u8]) -> Result<Lines, ObjectError> {
941 
    let v = cbor::decode(array)?;
942 
    let lines = array_lines(&v)?;
943 
    if lines.is_empty() {
944 
        return schema("insert with no lines");
945 
    }
946 
    Ok(lines)
947 
}
948
949 
/// The lines of a CBOR array of byte strings, copied once into one buffer.
950 
fn array_lines(v: &Value) -> Result<Lines, ObjectError> {
951 
    Ok(array(v, "lines")?
952 
        .iter()
953 
        .map(|l| bytes(l, "line"))
954 
        .collect::<Result<Vec<&[u8]>, _>>()?
955 
        .into_iter()
956 
        .collect())
957 
}
958
959 
impl Change {
960 
    /// Decode a change for a history-only state (spec §11): every insert is
961 
    /// left without its lines (an empty placeholder), and the result says
962 
    /// where each one's lines are, in order. The inline lines are stepped
963 
    /// over, not decoded: for a change that adds a whole tree, most of its
964 
    /// bytes. `me` is the change's hash.
965 
    pub fn decode_skeleton(
966 
        bytes: &[u8],
967 
        me: ChangeHash,
968 
    ) -> Result<(Change, Vec<TextRef>), ObjectError> {
969 
        let mut c = cbor::Cursor::new(bytes);
970 
        let (major, n) = c.head()?;
971 
        if major != 5 {
972 
            return schema("change: expected map");
973 
        }
974 
        let mut fields = Map::new();
975 
        let mut edits = Vec::new();
976 
        let mut texts = Vec::new();
977 
        let mut version = None;
978 
        let mut last: Option<u64> = None;
979 
        for _ in 0..n {
980 
            let k = map_key(&mut c, &mut last)?;
981 
            if k == 7 {
982 
                let Some(v) = version else {
983 
                    return schema("change: version must come first");
984 
                };
985 
                let (am, an) = c.head()?;
986 
                if am != 4 {
987 
                    return schema("edits: expected array");
988 
                }
989 
                for _ in 0..an {
990 
                    edits.push(edit_skeleton(&mut c, v, me, &mut texts)?);
991 
                }
992 
                fields.insert(7, Value::Array(Vec::new()));
993 
            } else {
994 
                let val = c.value()?;
995 
                if k == 0 {
996 
                    version = Some(uint(&val, "version")?);
997 
                }
998 
                fields.insert(k, val);
999 
            }
1000 
        }
1001 
        if !c.at_end() {
1002 
            return Err(ObjectError::Cbor(cbor::CborError::TrailingBytes));
1003 
        }
1004 
        let mut change = Change::from_value(&Value::Map(fields))?;
1005 
        change.edits = edits;
1006 
        Ok((change, texts))
1007 
    }
1008 
}
1009
1010 
impl Change {
1011 
    /// A change's metadata alone: its tree operations and edits are
1012 
    /// stepped over, not decoded. For log, signature checks and walks of
1013 
    /// the dependency graph, which read nothing else.
1014 
    pub fn decode_meta(bytes: &[u8]) -> Result<crate::state::ChangeMeta, ObjectError> {
1015 
        let mut c = cbor::Cursor::new(bytes);
1016 
        let (major, n) = c.head()?;
1017 
        if major != 5 {
1018 
            return schema("change: expected map");
1019 
        }
1020 
        let mut fields = Map::new();
1021 
        let mut last: Option<u64> = None;
1022 
        for _ in 0..n {
1023 
            let k = map_key(&mut c, &mut last)?;
1024 
            if k == 6 || k == 7 {
1025 
                c.skip()?;
1026 
                fields.insert(k, Value::Array(Vec::new()));
1027 
            } else {
1028 
                fields.insert(k, c.value()?);
1029 
            }
1030 
        }
1031 
        if !c.at_end() {
1032 
            return Err(ObjectError::Cbor(cbor::CborError::TrailingBytes));
1033 
        }
1034 
        Ok(crate::state::ChangeMeta::of(&Change::from_value(
1035 
            &Value::Map(fields),
1036 
        )?))
1037 
    }
1038 
}
1039
1040 
/// A canonical map key: an unsigned integer above the previous one.
1041 
fn map_key(c: &mut cbor::Cursor, last: &mut Option<u64>) -> Result<u64, ObjectError> {
1042 
    let (km, k) = c.head()?;
1043 
    if km != 0 || last.is_some_and(|l| k <= l) {
1044 
        return Err(ObjectError::Cbor(cbor::CborError::BadMapKey));
1045 
    }
1046 
    *last = Some(k);
1047 
    Ok(k)
1048 
}
1049
1050 
/// One edit of [`Change::decode_skeleton`]: an insert's lines are left out.
1051 
fn edit_skeleton(
1052 
    c: &mut cbor::Cursor,
1053 
    version: u64,
1054 
    me: ChangeHash,
1055 
    texts: &mut Vec<TextRef>,
1056 
) -> Result<Edit, ObjectError> {
1057 
    let (major, n) = c.head()?;
1058 
    if major != 5 {
1059 
        return schema("edit: expected map");
1060 
    }
1061 
    let mut fields = Map::new();
1062 
    let mut inline: Option<(usize, usize, u64)> = None;
1063 
    let mut last: Option<u64> = None;
1064 
    for _ in 0..n {
1065 
        let k = map_key(c, &mut last)?;
1066 
        if k == 4 {
1067 
            let start = c.pos();
1068 
            let (am, count) = c.head()?;
1069 
            if am != 4 {
1070 
                return schema("lines: expected array");
1071 
            }
1072 
            for _ in 0..count {
1073 
                c.skip()?;
1074 
            }
1075 
            inline = Some((start, c.pos(), count));
1076 
            continue;
1077 
        }
1078 
        fields.insert(k, c.value()?);
1079 
    }
1080 
    let Some((start, end, count)) = inline else {
1081 
        return Edit::from_value(&Value::Map(fields), version, &mut |text, count, form| {
1082 
            texts.push(TextRef::Blob(*text, count, form));
1083 
            Ok(Lines::default())
1084 
        });
1085 
    };
1086 
    if uint(field(&fields, 0, "edit tag")?, "edit tag")? != 0 || fields.contains_key(&5) {
1087 
        return schema("only an insert has inline lines, and not with a text blob");
1088 
    }
1089 
    if count == 0 {
1090 
        return schema("insert with no lines");
1091 
    }
1092 
    if version >= 2 && end - start >= TEXT_BLOB_MIN {
1093 
        return schema("an insert this large is stored as a text blob in a version 2 change");
1094 
    }
1095 
    let (Ok(start), Ok(end)) = (u32::try_from(start), u32::try_from(end)) else {
1096 
        return schema("change too large");
1097 
    };
1098 
    texts.push(TextRef::Inline {
1099 
        change: me,
1100 
        start,
1101 
        end,
1102 
    });
1103 
    Ok(Edit::Insert {
1104 
        node: node_id(field(&fields, 1, "edit.node")?, "edit.node")?,
1105 
        after: AtomRef::from_value(field(&fields, 2, "after")?, "after")?,
1106 
        before: AtomRef::from_value(field(&fields, 3, "before")?, "before")?,
1107 
        lines: Lines::default(),
1108 
    })
1109 
}
1110
1111 
/// A large insert's lines as stored (spec §6.1): the blob and its content,
1112 
/// the canonical CBOR array of the lines' byte strings.
1113 
#[derive(Debug, Clone, PartialEq, Eq)]
1114 
pub struct StoredText {
1115 
    pub blob: Blob,
1116 
    pub content: Vec<u8>,
1117 
    pub form: TextForm,
1118 
}
1119
1120 
/// The form a change of `version` stores these lines in.
1121 
fn text_form(version: u64, lines: &Lines) -> TextForm {
1122 
    match version {
1123 
        ..=2 => TextForm::Cbor,
1124 
        _ if lines.is_split_form() => TextForm::Raw,
1125 
        _ => TextForm::CborFallback,
1126 
    }
1127 
}
1128
1129 
/// The lines a text blob's `content` holds, checked against the rules for
1130 
/// one: canonical, as many as the insert claims, and not short enough to
1131 
/// have been inline.
1132 
pub fn text_lines(content: &[u8], count: u32, form: TextForm) -> Result<Lines, ObjectError> {
1133 
    let lines = match form {
1134 
        TextForm::Raw => Lines::split(content),
1135 
        TextForm::Cbor | TextForm::CborFallback => array_lines(&cbor::decode(content)?)?,
1136 
    };
1137 
    // One encoding per change: the size rule and the form are both fixed
1138 
    // by the lines.
1139 
    if cbor::byte_strings_len(&lines) < TEXT_BLOB_MIN {
1140 
        return schema(format!(
1141 
            "a text blob of {} bytes is short enough to be inline",
1142 
            content.len()
1143 
        ));
1144 
    }
1145 
    if form == TextForm::CborFallback && lines.is_split_form() {
1146 
        return schema("these lines are stored as their bytes in a version 3 change");
1147 
    }
1148 
    if lines.len() != count as usize {
1149 
        return schema(format!(
1150 
            "a text blob holds {} lines, the insert says {count}",
1151 
            lines.len()
1152 
        ));
1153 
    }
1154 
    Ok(lines)
1155 
}
1156
1157 
// ---------------------------------------------------------------- blob
1158
1159 
/// File content as an ordered list of chunks (spec §13.2).
1160 
#[derive(Debug, Clone, PartialEq, Eq)]
1161 
pub struct Blob {
1162 
    pub length: u64,
1163 
    pub chunks: Vec<ObjectRef>,
1164 
}
1165
1166 
impl Blob {
1167 
    /// The blob for `content`: its chunks as content-defined chunking cuts
1168 
    /// them (spec §13.2).
1169 
    pub fn of(content: &[u8]) -> Blob {
1170 
        Blob {
1171 
            length: content.len() as u64,
1172 
            chunks: crate::chunk::chunks(content)
1173 
                .into_iter()
1174 
                .map(|c| hash_object(ObjectType::Chunk, c))
1175 
                .collect(),
1176 
        }
1177 
    }
1178
1179 
    pub fn encode(&self) -> Vec<u8> {
1180 
        cbor::encode(&Value::map([
1181 
            (0, Value::Uint(FORMAT_VERSION)),
1182 
            (1, Value::Uint(self.length)),
1183 
            (
1184 
                2,
1185 
                Value::Array(
1186 
                    self.chunks
1187 
                        .iter()
1188 
                        .map(|c| Value::Bytes(c.0.to_vec()))
1189 
                        .collect(),
1190 
                ),
1191 
            ),
1192 
        ]))
1193 
    }
1194 
    pub fn hash(&self) -> ObjectRef {
1195 
        hash_object(ObjectType::Blob, &self.encode())
1196 
    }
1197 
    pub fn decode(bytes: &[u8]) -> Result<Blob, ObjectError> {
1198 
        let v = cbor::decode(bytes)?;
1199 
        let m = map(&v, "blob")?;
1200 
        check_version(m)?;
1201 
        Ok(Blob {
1202 
            length: uint(field(m, 1, "length")?, "length")?,
1203 
            chunks: array(field(m, 2, "chunks")?, "chunks")?
1204 
                .iter()
1205 
                .map(|c| oref(c, "chunk"))
1206 
                .collect::<Result<Vec<_>, _>>()?,
1207 
        })
1208 
    }
1209 
}
1210
1211 
// ---------------------------------------------------------------- checkpoint
1212
1213 
/// A materialized state (spec §11): the heads it stands for, how many changes
1214 
/// it holds, and a blob with the serialized graphs (`State::checkpoint_payload`).
1215 
#[derive(Debug, Clone, PartialEq, Eq)]
1216 
pub struct Checkpoint {
1217 
    pub heads: Vec<ChangeHash>,
1218 
    pub count: u64,
1219 
    pub payload: ObjectRef,
1220 
}
1221
1222 
impl Checkpoint {
1223 
    pub fn encode(&self) -> Vec<u8> {
1224 
        cbor::encode(&Value::map([
1225 
            (0, Value::Uint(FORMAT_VERSION)),
1226 
            (
1227 
                1,
1228 
                Value::Array(
1229 
                    self.heads
1230 
                        .iter()
1231 
                        .map(|h| Value::Bytes(h.0.to_vec()))
1232 
                        .collect(),
1233 
                ),
1234 
            ),
1235 
            (2, Value::Uint(self.count)),
1236 
            (3, Value::Bytes(self.payload.0.to_vec())),
1237 
        ]))
1238 
    }
1239 
    pub fn hash(&self) -> ObjectRef {
1240 
        hash_object(ObjectType::Checkpoint, &self.encode())
1241 
    }
1242 
    pub fn decode(bytes: &[u8]) -> Result<Checkpoint, ObjectError> {
1243 
        let v = cbor::decode(bytes)?;
1244 
        let m = map(&v, "checkpoint")?;
1245 
        check_version(m)?;
1246 
        Ok(Checkpoint {
1247 
            heads: array(field(m, 1, "heads")?, "heads")?
1248 
                .iter()
1249 
                .map(|h| oref(h, "head"))
1250 
                .collect::<Result<Vec<_>, _>>()?,
1251 
            count: uint(field(m, 2, "count")?, "count")?,
1252 
            payload: oref(field(m, 3, "payload")?, "payload")?,
1253 
        })
1254 
    }
1255 
}
1256
1257 
// ---------------------------------------------------------------- state
1258
1259 
/// A state named by its heads (spec §10.1): what a bookmark or tag points at.
1260 
#[derive(Debug, Clone, PartialEq, Eq, Default)]
1261 
pub struct StateObject {
1262 
    pub heads: Vec<ChangeHash>,
1263 
}
1264
1265 
impl StateObject {
1266 
    pub fn new(mut heads: Vec<ChangeHash>) -> StateObject {
1267 
        heads.sort();
1268 
        heads.dedup();
1269 
        StateObject { heads }
1270 
    }
1271 
    pub fn encode(&self) -> Vec<u8> {
1272 
        debug_assert!(self.heads.windows(2).all(|w| w[0] < w[1]));
1273 
        cbor::encode(&Value::map([
1274 
            (0, Value::Uint(FORMAT_VERSION)),
1275 
            (
1276 
                1,
1277 
                Value::Array(
1278 
                    self.heads
1279 
                        .iter()
1280 
                        .map(|h| Value::Bytes(h.0.to_vec()))
1281 
                        .collect(),
1282 
                ),
1283 
            ),
1284 
        ]))
1285 
    }
1286 
    pub fn hash(&self) -> ObjectRef {
1287 
        hash_object(ObjectType::State, &self.encode())
1288 
    }
1289 
    pub fn decode(bytes: &[u8]) -> Result<StateObject, ObjectError> {
1290 
        let v = cbor::decode(bytes)?;
1291 
        let m = map(&v, "state")?;
1292 
        check_version(m)?;
1293 
        let heads = array(field(m, 1, "heads")?, "heads")?
1294 
            .iter()
1295 
            .map(|h| oref(h, "head"))
1296 
            .collect::<Result<Vec<_>, _>>()?;
1297 
        if !heads.windows(2).all(|w| w[0] < w[1]) {
1298 
            return schema("state heads must be sorted and unique");
1299 
        }
1300 
        Ok(StateObject { heads })
1301 
    }
1302 
}
1303
1304 
#[cfg(test)]
1305 
pub(crate) mod tests {
1306 
    use super::*;
1307
1308 
    pub(crate) fn sample_change() -> Change {
1309 
        let n = NodeId([7; 16]);
1310 
        let dep = ObjectRef([1; 32]);
1311 
        let mut c = Change {
1312 
            version: crate::objects::CHANGE_VERSION,
1313 
            change_id: ChangeId([9; 16]),
1314 
            deps: vec![ObjectRef([2; 32]), dep],
1315 
            author: ObjectRef([3; 32]),
1316 
            hlc: Hlc {
1317 
                wall_ms: 1_700_000_000_000,
1318 
                logical: 4,
1319 
            },
1320 
            message: "Add greeting".into(),
1321 
            tree_ops: vec![
1322 
                TreeOp::AddNode {
1323 
                    node: n,
1324 
                    kind: NodeKind::File,
1325 
                    mode: Mode::TEXT,
1326 
                    parent: NodeId::ROOT,
1327 
                    name: "hello.txt".into(),
1328 
                },
1329 
                TreeOp::SetMode {
1330 
                    node: n,
1331 
                    old: OpRef {
1332 
                        change: ObjectRef::ZERO,
1333 
                        index: 0,
1334 
                    },
1335 
                    mode: Mode {
1336 
                        exec: true,
1337 
                        opaque: false,
1338 
                    },
1339 
                },
1340 
            ],
1341 
            edits: vec![
1342 
                Edit::Insert {
1343 
                    node: n,
1344 
                    after: AtomRef::Start,
1345 
                    before: AtomRef::End,
1346 
                    lines: vec![b"hello\n".to_vec(), b"world\n".to_vec()].into(),
1347 
                },
1348 
                Edit::Delete {
1349 
                    node: n,
1350 
                    atoms: vec![AtomRange {
1351 
                        change: dep,
1352 
                        from: 0,
1353 
                        to: 2,
1354 
                    }],
1355 
                },
1356 
                Edit::Replace {
1357 
                    node: n,
1358 
                    old: None,
1359 
                    new: Some(ObjectRef([5; 32])),
1360 
                },
1361 
            ],
1362 
            kind: ChangeKind::Normal,
1363 
        };
1364 
        c.normalize();
1365 
        c
1366 
    }
1367
1368 
    #[test]
1369 
    fn change_round_trips_and_hash_is_stable() {
1370 
        let c = sample_change();
1371 
        let bytes = c.encode();
1372 
        let d = Change::decode(&bytes).unwrap();
1373 
        assert_eq!(c, d);
1374 
        assert_eq!(c.hash(), d.hash());
1375 
        assert_eq!(d.encode(), bytes);
1376 
        // Any semantic difference changes the hash.
1377 
        let mut e = c.clone();
1378 
        e.message.push('!');
1379 
        assert_ne!(e.hash(), c.hash());
1380 
    }
1381
1382 
    #[test]
1383 
    fn compact_encoding_is_the_plain_one() {
1384 
        // Inline lines written as their encoding give the same bytes, so
1385 
        // the same hash, as a value per line.
1386 
        let c = sample_change();
1387 
        assert!(!c.has_stored_text(), "the sample's insert is inline");
1388 
        let plain = cbor::encode(&c.to_value());
1389 
        assert_eq!(c.encode(), plain);
1390 
        assert_eq!(c.encode_parts().0, plain);
1391 
        let streamed: Result<Vec<u8>, ()> = c.encode_streaming(|_| Ok(()));
1392 
        assert_eq!(streamed.unwrap(), plain);
1393 
        assert_eq!(Change::decode(&plain).unwrap(), c);
1394 
    }
1395
1396 
    #[test]
1397 
    fn decode_rejects_bad_changes() {
1398 
        let c = sample_change();
1399 
        let mut v = c.to_value();
1400 
        if let Value::Map(m) = &mut v {
1401 
            m.insert(0, Value::Uint(4));
1402 
        }
1403 
        assert!(
1404 
            matches!(Change::from_value(&v), Err(ObjectError::Schema(s)) if s.contains("version"))
1405 
        );
1406
1407 
        let mut v = c.to_value();
1408 
        if let Value::Map(m) = &mut v {
1409 
            m.insert(
1410 
                2,
1411 
                Value::Array(vec![Value::Bytes(vec![2; 32]), Value::Bytes(vec![1; 32])]),
1412 
            );
1413 
        }
1414 
        assert!(
1415 
            matches!(Change::from_value(&v), Err(ObjectError::Schema(s)) if s.contains("sorted"))
1416 
        );
1417
1418 
        let mut v = c.to_value();
1419 
        if let Value::Map(m) = &mut v {
1420 
            m.insert(9, Value::map([(0, Value::Null)]));
1421 
        }
1422 
        assert!(
1423 
            matches!(Change::from_value(&v), Err(ObjectError::Schema(s)) if s.contains("extra"))
1424 
        );
1425 
    }
1426
1427 
    fn big_lines(n: usize) -> Lines {
1428 
        (0..n)
1429 
            .map(|i| format!("line {i} of a large insert\n").into_bytes())
1430 
            .collect()
1431 
    }
1432
1433 
    fn with_insert(mut c: Change, lines: Lines) -> Change {
1434 
        c.edits[0] = Edit::Insert {
1435 
            node: NodeId([7; 16]),
1436 
            after: AtomRef::Start,
1437 
            before: AtomRef::End,
1438 
            lines,
1439 
        };
1440 
        c
1441 
    }
1442
1443 
    #[test]
1444 
    fn large_inserts_are_stored_as_text_blobs() {
1445 
        assert!(
1446 
            !sample_change().has_stored_text(),
1447 
            "a small insert stays inline"
1448 
        );
1449 
        let lines = big_lines(500);
1450 
        let c = with_insert(sample_change(), lines.clone());
1451 
        assert!(c.has_stored_text());
1452 
        let (bytes, texts) = c.encode_parts();
1453 
        assert_eq!(bytes, c.encode());
1454 
        assert!(bytes.len() < 1024, "{}", bytes.len());
1455 
        assert_eq!(texts.len(), 1);
1456 
        // Version 3: the lines' bytes themselves.
1457 
        assert_eq!(texts[0].form, TextForm::Raw);
1458 
        assert_eq!(texts[0].content, lines.bytes());
1459 
        assert_eq!(texts[0].blob, Blob::of(&texts[0].content));
1460 
        assert!(Change::decode(&bytes).is_err(), "reading it needs the text");
1461 
        let d = Change::decode_with(&bytes, &mut |r, n, form| {
1462 
            assert_eq!(*r, texts[0].blob.hash());
1463 
            assert_eq!(form, TextForm::Raw);
1464 
            text_lines(&texts[0].content, n, form)
1465 
        })
1466 
        .unwrap();
1467 
        assert_eq!(d, c);
1468 
        assert_eq!(d.hash(), c.hash());
1469 
        // Version 2 held the same lines as a CBOR array, and still reads.
1470 
        let mut v2 = c.clone();
1471 
        v2.version = 2;
1472 
        let (b2, t2) = v2.encode_parts();
1473 
        assert_eq!(t2[0].form, TextForm::Cbor);
1474 
        assert_eq!(t2[0].content, cbor::encode_byte_strings(&lines));
1475 
        let d2 = Change::decode_with(&b2, &mut |_, n, form| text_lines(&t2[0].content, n, form))
1476 
            .unwrap();
1477 
        assert_eq!(d2, v2);
1478 
        // Lines the line rule would not split back stay a CBOR array,
1479 
        // marked; and a marked array of lines that would is refused.
1480 
        let odd: Lines = (0..500)
1481 
            .map(|i| format!("no newline {i}").into_bytes())
1482 
            .collect();
1483 
        let c3 = with_insert(sample_change(), odd.clone());
1484 
        let (b3, t3) = c3.encode_parts();
1485 
        assert_eq!(t3[0].form, TextForm::CborFallback);
1486 
        let d3 = Change::decode_with(&b3, &mut |_, n, form| text_lines(&t3[0].content, n, form))
1487 
            .unwrap();
1488 
        assert_eq!(d3, c3);
1489 
        let marked = cbor::encode_byte_strings(&lines);
1490 
        assert!(text_lines(&marked, 500, TextForm::CborFallback).is_err());
1491 
    }
1492
1493 
    #[test]
1494 
    fn version_1_changes_keep_their_inline_inserts_and_hashes() {
1495 
        let mut c = with_insert(sample_change(), big_lines(500));
1496 
        c.version = 1;
1497 
        let bytes = c.encode();
1498 
        assert!(bytes.len() > TEXT_BLOB_MIN);
1499 
        let (again, texts) = c.encode_parts();
1500 
        assert!(texts.is_empty());
1501 
        assert_eq!(again, bytes);
1502 
        let d = Change::decode(&bytes).unwrap();
1503 
        assert_eq!(d.version, 1);
1504 
        assert_eq!(d.encode(), bytes);
1505 
        // The same inline insert in a version 2 change is not canonical.
1506 
        let mut v = c.to_value();
1507 
        if let Value::Map(m) = &mut v {
1508 
            m.insert(0, Value::Uint(2));
1509 
        }
1510 
        assert!(
1511 
            matches!(Change::from_value(&v), Err(ObjectError::Schema(s)) if s.contains("text blob"))
1512 
        );
1513 
    }
1514
1515 
    #[test]
1516 
    fn a_skeleton_leaves_every_insert_out_and_says_where_its_lines_are() {
1517 
        let mut c = with_insert(sample_change(), big_lines(500));
1518 
        c.edits.push(Edit::Insert {
1519 
            node: NodeId([8; 16]),
1520 
            after: AtomRef::Start,
1521 
            before: AtomRef::End,
1522 
            lines: vec![b"small\n".to_vec(), b"insert\n".to_vec()].into(),
1523 
        });
1524 
        let (bytes, stored) = c.encode_parts();
1525 
        let me = ObjectRef([4; 32]);
1526 
        let (skel, texts) = Change::decode_skeleton(&bytes, me).unwrap();
1527 
        assert_eq!(texts.len(), 2);
1528 
        let mut filled = skel.clone();
1529 
        let mut next = texts.iter();
1530 
        for e in filled.edits.iter_mut() {
1531 
            if let Edit::Insert { lines, .. } = e {
1532 
                assert!(lines.is_empty(), "no line kept");
1533 
                *lines = match next.next().unwrap() {
1534 
                    TextRef::Blob(r, n, form) => {
1535 
                        assert_eq!(*r, stored[0].blob.hash());
1536 
                        text_lines(&stored[0].content, *n, *form).unwrap()
1537 
                    }
1538 
                    TextRef::Inline { change, start, end } => {
1539 
                        assert_eq!(*change, me);
1540 
                        inline_lines(&bytes[*start as usize..*end as usize]).unwrap()
1541 
                    }
1542 
                };
1543 
            }
1544 
        }
1545 
        assert_eq!(filled, c, "filled in, it is the change");
1546 
        // A version 1 change's large inline insert is fine; in version 2 it is not.
1547 
        let mut v1 = with_insert(sample_change(), big_lines(500));
1548 
        v1.version = 1;
1549 
        assert!(Change::decode_skeleton(&v1.encode(), me).is_ok());
1550 
        let mut v = v1.to_value();
1551 
        if let Value::Map(m) = &mut v {
1552 
            m.insert(0, Value::Uint(2));
1553 
        }
1554 
        assert!(Change::decode_skeleton(&cbor::encode(&v), me).is_err());
1555 
    }
1556
1557 
    #[test]
1558 
    fn metadata_reads_without_the_operations() {
1559 
        let c = with_insert(sample_change(), big_lines(500));
1560 
        let (bytes, _) = c.encode_parts();
1561 
        let m = Change::decode_meta(&bytes).unwrap();
1562 
        assert_eq!(m, crate::state::ChangeMeta::of(&c));
1563 
    }
1564
1565 
    #[test]
1566 
    fn text_blobs_are_checked() {
1567 
        let lines = big_lines(500);
1568 
        let content = cbor::encode_byte_strings(&lines);
1569 
        assert_eq!(content.len(), cbor::byte_strings_len(&lines));
1570 
        assert_eq!(
1571 
            content,
1572 
            cbor::encode(&Value::Array(
1573 
                lines.iter().map(|l| Value::Bytes(l.to_vec())).collect()
1574 
            ))
1575 
        );
1576 
        assert_eq!(text_lines(&content, 500, TextForm::Cbor).unwrap(), lines);
1577 
        assert!(text_lines(&content, 499, TextForm::Cbor).is_err());
1578 
        assert_eq!(
1579 
            text_lines(lines.bytes(), 500, TextForm::Raw).unwrap(),
1580 
            lines
1581 
        );
1582 
        assert!(text_lines(lines.bytes(), 501, TextForm::Raw).is_err());
1583 
        let small = cbor::encode_byte_strings(&vec![b"x\n".to_vec()].into());
1584 
        assert!(
1585 
            text_lines(&small, 1, TextForm::Cbor).is_err(),
1586 
            "short enough to be inline"
1587 
        );
1588 
        assert!(
1589 
            text_lines(b"x\n", 1, TextForm::Raw).is_err(),
1590 
            "short enough to be inline"
1591 
        );
1592 
    }
1593
1594 
    #[test]
1595 
    fn names_are_validated() {
1596 
        for bad in ["", ".", "..", "a/b", "a\0b"] {
1597 
            assert!(validate_name(bad).is_err(), "{bad:?}");
1598 
        }
1599 
        assert!(validate_name("Foo.c").is_ok());
1600 
        assert!(validate_name("...").is_ok());
1601 
    }
1602
1603 
    #[test]
1604 
    fn mode_and_kind_tags() {
1605 
        for m in [
1606 
            Mode::TEXT,
1607 
            Mode::OPAQUE,
1608 
            Mode {
1609 
                exec: true,
1610 
                opaque: true,
1611 
            },
1612 
        ] {
1613 
            assert_eq!(Mode::from_bits(m.bits()).unwrap(), m);
1614 
        }
1615 
        assert!(Mode::from_bits(4).is_err());
1616 
        for k in [
1617 
            NodeKind::File,
1618 
            NodeKind::Dir,
1619 
            NodeKind::Symlink,
1620 
            NodeKind::Subrepo,
1621 
        ] {
1622 
            assert_eq!(NodeKind::from_tag(k.tag()).unwrap(), k);
1623 
        }
1624 
    }
1625
1626 
    #[test]
1627 
    fn self_references_resolve() {
1628 
        let me = ObjectRef([8; 32]);
1629 
        assert_eq!(
1630 
            AtomRef::Atom {
1631 
                change: ObjectRef::ZERO,
1632 
                index: 3
1633 
            }
1634 
            .resolve(me),
1635 
            AtomRef::Atom {
1636 
                change: me,
1637 
                index: 3
1638 
            }
1639 
        );
1640 
        assert_eq!(AtomRef::Start.resolve(me), AtomRef::Start);
1641 
        let other = ObjectRef([1; 32]);
1642 
        assert_eq!(
1643 
            OpRef {
1644 
                change: other,
1645 
                index: 1
1646 
            }
1647 
            .resolve(me)
1648 
            .change,
1649 
            other
1650 
        );
1651 
    }
1652
1653 
    #[test]
1654 
    fn state_object_round_trip() {
1655 
        let st = StateObject::new(vec![
1656 
            ObjectRef([2; 32]),
1657 
            ObjectRef([1; 32]),
1658 
            ObjectRef([2; 32]),
1659 
        ]);
1660 
        assert_eq!(st.heads, vec![ObjectRef([1; 32]), ObjectRef([2; 32])]);
1661 
        assert_eq!(StateObject::decode(&st.encode()).unwrap(), st);
1662 
        assert_eq!(StateObject::new(vec![]).heads, vec![]);
1663 
        assert_ne!(StateObject::new(vec![]).hash(), st.hash());
1664 
    }
1665
1666 
    #[test]
1667 
    fn blob_round_trip() {
1668 
        let b = Blob {
1669 
            length: 10,
1670 
            chunks: vec![ObjectRef([1; 32]), ObjectRef([2; 32])],
1671 
        };
1672 
        assert_eq!(Blob::decode(&b.encode()).unwrap(), b);
1673 
    }
1674 
}