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