heddle_object_model/object/manifest/
node.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Canonical manifest-node encoding — WPMF v1.
3//!
4//! A manifest node is addressed by `BLAKE3(canonical_node_bytes)`. There is
5//! exactly one byte string per logical node, so the same logical membership
6//! always produces the same root hash. Every integer is unsigned big-endian,
7//! entries and children are strictly ordered, and decoding rejects duplicates,
8//! truncation, trailing bytes, and any non-canonical spelling.
9//!
10//! The layouts below are byte-identical to the already-merged downstream
11//! consumer (weft PR #1069, `docs/PLAN_MANIFEST_FORMAT.md`), including the
12//! `WPMF` magic and the `weft-plan-manifest-key-v1` routing domain. Byte
13//! compatibility with a shipped consumer outranks upstream nomenclature: this
14//! module is the normative *definition* of bytes that already exist, not a
15//! second, competing format.
16//!
17//! ```text
18//! leaf:   "WPMF" | u8(version=1) | u8(tag=0) | u16(count)
19//!                | count  * ( u8(kind) | [u8;32](hash) | u64(decoded_size) )
20//! branch: "WPMF" | u8(version=1) | u8(tag=1) | u8(depth) | u32(bitmap)
21//!                | popcnt * ( [u8;32](child_hash) | u64(object_count)
22//!                                                 | u64(decoded_bytes) )
23//! ```
24
25use std::fmt;
26
27use crate::object::ContentHash;
28
29/// Magic prefix on every canonical manifest node.
30pub const MANIFEST_NODE_MAGIC: [u8; 4] = *b"WPMF";
31/// The only manifest format version this binary reads or writes.
32pub const MANIFEST_FORMAT_VERSION: u8 = 1;
33/// Domain separator for the trie route. Hashed with the plan key to derive the
34/// 256 routing bits.
35pub const MANIFEST_ROUTE_DOMAIN: &[u8] = b"weft-plan-manifest-key-v1";
36/// Routing bits consumed per trie level (32-way branching).
37pub const MANIFEST_ROUTE_BITS: u8 = 5;
38/// Branch fan-out — one bitmap slot per possible 5-bit route group.
39pub const MANIFEST_BRANCH_WIDTH: usize = 32;
40/// Levels available before the fixed 256-bit route is exhausted
41/// (`ceil(256 / 5)`). A leaf at this depth may exceed
42/// [`MANIFEST_LEAF_MAX_ENTRIES`] because no routing bits remain to split it.
43pub const MANIFEST_ROUTE_LEVELS: u8 = 52;
44/// Entries a leaf may hold before it must split into a branch, unless the
45/// route is already exhausted.
46pub const MANIFEST_LEAF_MAX_ENTRIES: usize = 16;
47
48const TAG_LEAF: u8 = 0;
49const TAG_BRANCH: u8 = 1;
50
51const LEAF_HEADER_LEN: usize = 4 + 1 + 1 + 2;
52const LEAF_ENTRY_LEN: usize = 1 + 32 + 8;
53const BRANCH_HEADER_LEN: usize = 4 + 1 + 1 + 1 + 4;
54const BRANCH_CHILD_LEN: usize = 32 + 8 + 8;
55
56// ── ManifestObjectKind ──────────────────────────────────────────────
57
58/// The object types a manifest leaf may name.
59///
60/// Deliberately narrow: a manifest carries *content* membership. Owner
61/// identity (State / StateAttachment) lives in the binding, outside the shared
62/// content root, so a context-only state reuses its parent root byte-for-byte.
63#[repr(u8)]
64#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
65pub enum ManifestObjectKind {
66    Blob = 0,
67    Tree = 1,
68}
69
70impl ManifestObjectKind {
71    pub fn to_byte(self) -> u8 {
72        self as u8
73    }
74
75    pub fn from_byte(byte: u8) -> Option<Self> {
76        match byte {
77            0 => Some(Self::Blob),
78            1 => Some(Self::Tree),
79            _ => None,
80        }
81    }
82}
83
84impl fmt::Display for ManifestObjectKind {
85    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
86        f.write_str(match self {
87            Self::Blob => "blob",
88            Self::Tree => "tree",
89        })
90    }
91}
92
93// ── ManifestKey / ManifestRoute ─────────────────────────────────────
94
95/// The trie key: `(kind, object_hash)`. Ordering is the canonical plan order —
96/// kind first, then the 32 hash bytes lexicographically.
97#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
98pub struct ManifestKey {
99    pub kind: ManifestObjectKind,
100    pub hash: ContentHash,
101}
102
103impl ManifestKey {
104    pub fn new(kind: ManifestObjectKind, hash: ContentHash) -> Self {
105        Self { kind, hash }
106    }
107
108    /// The 256 routing bits for this key.
109    pub fn route(&self) -> ManifestRoute {
110        let mut hasher = blake3::Hasher::new();
111        hasher.update(MANIFEST_ROUTE_DOMAIN);
112        hasher.update(&[self.kind.to_byte()]);
113        hasher.update(self.hash.as_bytes());
114        ManifestRoute(hasher.finalize().into())
115    }
116}
117
118/// The fixed 256-bit route derived from a [`ManifestKey`], read as successive
119/// 5-bit groups, most-significant bit first.
120#[derive(Clone, Copy, PartialEq, Eq)]
121pub struct ManifestRoute([u8; 32]);
122
123impl ManifestRoute {
124    pub fn as_bytes(&self) -> &[u8; 32] {
125        &self.0
126    }
127
128    /// The bitmap slot this key occupies at `level`.
129    ///
130    /// Levels past the 256th bit are zero-padded on the right, so the final
131    /// level (51) carries a single real bit. Levels at or beyond
132    /// [`MANIFEST_ROUTE_LEVELS`] are exhausted and always return 0; callers
133    /// must stop splitting there rather than loop forever.
134    pub fn group(&self, level: u8) -> u8 {
135        let start = usize::from(level) * usize::from(MANIFEST_ROUTE_BITS);
136        let mut value = 0u8;
137        for offset in 0..usize::from(MANIFEST_ROUTE_BITS) {
138            let bit_index = start + offset;
139            let bit = if bit_index >= 256 {
140                0
141            } else {
142                (self.0[bit_index / 8] >> (7 - (bit_index % 8))) & 1
143            };
144            value = (value << 1) | bit;
145        }
146        value
147    }
148}
149
150impl fmt::Debug for ManifestRoute {
151    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
152        write!(f, "ManifestRoute({})", hex::encode(&self.0[..8]))
153    }
154}
155
156// ── ManifestObject ──────────────────────────────────────────────────
157
158/// One immutable content object named by a manifest leaf.
159///
160/// Only logical facts appear here. Pack id, storage key, offset, encoded
161/// length, encoded digest, ETag, audience, and current head are mutable
162/// control-plane facts and are resolved *after* authorization — see
163/// [`super::extent`].
164#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
165pub struct ManifestObject {
166    pub kind: ManifestObjectKind,
167    pub hash: ContentHash,
168    pub decoded_size: u64,
169}
170
171impl ManifestObject {
172    pub fn new(kind: ManifestObjectKind, hash: ContentHash, decoded_size: u64) -> Self {
173        Self {
174            kind,
175            hash,
176            decoded_size,
177        }
178    }
179
180    pub fn key(&self) -> ManifestKey {
181        ManifestKey::new(self.kind, self.hash)
182    }
183}
184
185// ── ManifestChild ───────────────────────────────────────────────────
186
187/// A branch's reference to one child subtree, with the summary that lets a
188/// planner size a subtree without descending into it.
189#[derive(Clone, Copy, Debug, PartialEq, Eq)]
190pub struct ManifestChild {
191    /// Bitmap slot (`0..32`) — the child's 5-bit route group at the parent's
192    /// depth.
193    pub slot: u8,
194    pub hash: ContentHash,
195    pub object_count: u64,
196    pub decoded_bytes: u64,
197}
198
199// ── ManifestNode ────────────────────────────────────────────────────
200
201#[derive(Clone, Debug, PartialEq, Eq)]
202pub enum ManifestNode {
203    Leaf(ManifestLeaf),
204    Branch(ManifestBranch),
205}
206
207#[derive(Clone, Debug, PartialEq, Eq)]
208pub struct ManifestLeaf {
209    entries: Vec<ManifestObject>,
210}
211
212#[derive(Clone, Debug, PartialEq, Eq)]
213pub struct ManifestBranch {
214    depth: u8,
215    children: Vec<ManifestChild>,
216}
217
218impl ManifestLeaf {
219    /// Build a leaf, sorting entries into canonical key order.
220    ///
221    /// Returns [`ManifestNodeError::DuplicateObjectKey`] if two entries share a
222    /// `(kind, hash)` key, even when their declared sizes agree: the canonical
223    /// form names each object exactly once.
224    pub fn new(mut entries: Vec<ManifestObject>) -> Result<Self, ManifestNodeError> {
225        entries.sort_by_key(ManifestObject::key);
226        if let Some(window) = entries.windows(2).find(|w| w[0].key() == w[1].key()) {
227            return Err(ManifestNodeError::DuplicateObjectKey(window[0].key()));
228        }
229        if u16::try_from(entries.len()).is_err() {
230            return Err(ManifestNodeError::LeafCountOverflow(entries.len()));
231        }
232        Ok(Self { entries })
233    }
234
235    pub fn entries(&self) -> &[ManifestObject] {
236        &self.entries
237    }
238
239    pub fn object_count(&self) -> u64 {
240        self.entries.len() as u64
241    }
242
243    /// Total decoded bytes named by this leaf, or `None` on `u64` overflow.
244    pub fn decoded_bytes(&self) -> Option<u64> {
245        self.entries
246            .iter()
247            .try_fold(0u64, |acc, entry| acc.checked_add(entry.decoded_size))
248    }
249}
250
251impl ManifestBranch {
252    /// Build a branch, sorting children into ascending bitmap-slot order.
253    pub fn new(depth: u8, mut children: Vec<ManifestChild>) -> Result<Self, ManifestNodeError> {
254        children.sort_by_key(|child| child.slot);
255        if children.is_empty() {
256            return Err(ManifestNodeError::EmptyBranchBitmap);
257        }
258        if let Some(child) = children
259            .iter()
260            .find(|child| usize::from(child.slot) >= MANIFEST_BRANCH_WIDTH)
261        {
262            return Err(ManifestNodeError::SlotOutOfRange(child.slot));
263        }
264        if let Some(window) = children.windows(2).find(|w| w[0].slot == w[1].slot) {
265            return Err(ManifestNodeError::DuplicateBranchSlot(window[0].slot));
266        }
267        Ok(Self { depth, children })
268    }
269
270    pub fn depth(&self) -> u8 {
271        self.depth
272    }
273
274    pub fn children(&self) -> &[ManifestChild] {
275        &self.children
276    }
277
278    pub fn bitmap(&self) -> u32 {
279        self.children
280            .iter()
281            .fold(0u32, |acc, child| acc | (1u32 << child.slot))
282    }
283
284    pub fn child_at(&self, slot: u8) -> Option<&ManifestChild> {
285        self.children.iter().find(|child| child.slot == slot)
286    }
287}
288
289impl ManifestNode {
290    /// The canonical empty-set root: a leaf with no entries.
291    pub fn empty() -> Self {
292        Self::Leaf(ManifestLeaf {
293            entries: Vec::new(),
294        })
295    }
296
297    /// Encode to the single canonical byte string for this logical node.
298    pub fn encode(&self) -> Vec<u8> {
299        match self {
300            Self::Leaf(leaf) => {
301                let mut out =
302                    Vec::with_capacity(LEAF_HEADER_LEN + leaf.entries.len() * LEAF_ENTRY_LEN);
303                out.extend_from_slice(&MANIFEST_NODE_MAGIC);
304                out.push(MANIFEST_FORMAT_VERSION);
305                out.push(TAG_LEAF);
306                out.extend_from_slice(&(leaf.entries.len() as u16).to_be_bytes());
307                for entry in &leaf.entries {
308                    out.push(entry.kind.to_byte());
309                    out.extend_from_slice(entry.hash.as_bytes());
310                    out.extend_from_slice(&entry.decoded_size.to_be_bytes());
311                }
312                out
313            }
314            Self::Branch(branch) => {
315                let mut out = Vec::with_capacity(
316                    BRANCH_HEADER_LEN + branch.children.len() * BRANCH_CHILD_LEN,
317                );
318                out.extend_from_slice(&MANIFEST_NODE_MAGIC);
319                out.push(MANIFEST_FORMAT_VERSION);
320                out.push(TAG_BRANCH);
321                out.push(branch.depth);
322                out.extend_from_slice(&branch.bitmap().to_be_bytes());
323                for child in &branch.children {
324                    out.extend_from_slice(child.hash.as_bytes());
325                    out.extend_from_slice(&child.object_count.to_be_bytes());
326                    out.extend_from_slice(&child.decoded_bytes.to_be_bytes());
327                }
328                out
329            }
330        }
331    }
332
333    /// The node's content address — `BLAKE3` of its canonical bytes.
334    pub fn address(&self) -> ContentHash {
335        ContentHash::compute(&self.encode())
336    }
337
338    /// Decode strictly.
339    ///
340    /// Rejects a bad magic, an unknown version or tag, an unknown object kind,
341    /// truncation, trailing bytes, out-of-order or duplicated entries, an empty
342    /// branch bitmap, and — as a final backstop — any input whose re-encoding
343    /// differs from the input. A node that decodes here is canonical, so its
344    /// address is meaningful.
345    pub fn decode(bytes: &[u8]) -> Result<Self, ManifestDecodeError> {
346        let node = Self::decode_inner(bytes)?;
347        if node.encode() != bytes {
348            return Err(ManifestDecodeError::NonCanonicalEncoding);
349        }
350        Ok(node)
351    }
352
353    /// Decode and verify the node addresses to `expected`.
354    pub fn decode_addressed(
355        bytes: &[u8],
356        expected: &ContentHash,
357    ) -> Result<Self, ManifestDecodeError> {
358        let node = Self::decode(bytes)?;
359        let actual = ContentHash::compute(bytes);
360        if actual != *expected {
361            return Err(ManifestDecodeError::AddressMismatch {
362                expected: *expected,
363                actual,
364            });
365        }
366        Ok(node)
367    }
368
369    fn decode_inner(bytes: &[u8]) -> Result<Self, ManifestDecodeError> {
370        let mut reader = Reader::new(bytes);
371        if reader.take(4)? != MANIFEST_NODE_MAGIC {
372            return Err(ManifestDecodeError::BadMagic);
373        }
374        let version = reader.u8()?;
375        if version != MANIFEST_FORMAT_VERSION {
376            return Err(ManifestDecodeError::UnsupportedVersion(version));
377        }
378        let tag = reader.u8()?;
379        let node = match tag {
380            TAG_LEAF => {
381                let count = usize::from(reader.u16()?);
382                let mut entries = Vec::with_capacity(count.min(1024));
383                let mut previous: Option<ManifestKey> = None;
384                for _ in 0..count {
385                    let kind_byte = reader.u8()?;
386                    let kind = ManifestObjectKind::from_byte(kind_byte)
387                        .ok_or(ManifestDecodeError::UnknownObjectKind(kind_byte))?;
388                    let hash = ContentHash::from_bytes(reader.hash()?);
389                    let decoded_size = reader.u64()?;
390                    let key = ManifestKey::new(kind, hash);
391                    match previous {
392                        Some(prev) if prev == key => {
393                            return Err(ManifestDecodeError::DuplicateObjectKey(key));
394                        }
395                        Some(prev) if prev > key => {
396                            return Err(ManifestDecodeError::EntriesOutOfOrder);
397                        }
398                        _ => {}
399                    }
400                    previous = Some(key);
401                    entries.push(ManifestObject::new(kind, hash, decoded_size));
402                }
403                Self::Leaf(ManifestLeaf { entries })
404            }
405            TAG_BRANCH => {
406                let depth = reader.u8()?;
407                let bitmap = reader.u32()?;
408                if bitmap == 0 {
409                    return Err(ManifestDecodeError::EmptyBranchBitmap);
410                }
411                let mut children = Vec::with_capacity(bitmap.count_ones() as usize);
412                for slot in 0..MANIFEST_BRANCH_WIDTH as u8 {
413                    if bitmap & (1u32 << slot) == 0 {
414                        continue;
415                    }
416                    let hash = ContentHash::from_bytes(reader.hash()?);
417                    let object_count = reader.u64()?;
418                    let decoded_bytes = reader.u64()?;
419                    children.push(ManifestChild {
420                        slot,
421                        hash,
422                        object_count,
423                        decoded_bytes,
424                    });
425                }
426                Self::Branch(ManifestBranch { depth, children })
427            }
428            other => return Err(ManifestDecodeError::UnknownNodeTag(other)),
429        };
430        if !reader.is_exhausted() {
431            return Err(ManifestDecodeError::TrailingBytes);
432        }
433        Ok(node)
434    }
435
436    /// Objects named directly by this node (empty for a branch).
437    pub fn leaf_entries(&self) -> &[ManifestObject] {
438        match self {
439            Self::Leaf(leaf) => leaf.entries(),
440            Self::Branch(_) => &[],
441        }
442    }
443}
444
445// ── Reader ──────────────────────────────────────────────────────────
446
447struct Reader<'a> {
448    bytes: &'a [u8],
449    pos: usize,
450}
451
452impl<'a> Reader<'a> {
453    fn new(bytes: &'a [u8]) -> Self {
454        Self { bytes, pos: 0 }
455    }
456
457    fn take(&mut self, len: usize) -> Result<&'a [u8], ManifestDecodeError> {
458        let end = self
459            .pos
460            .checked_add(len)
461            .ok_or(ManifestDecodeError::Truncated)?;
462        let slice = self
463            .bytes
464            .get(self.pos..end)
465            .ok_or(ManifestDecodeError::Truncated)?;
466        self.pos = end;
467        Ok(slice)
468    }
469
470    fn u8(&mut self) -> Result<u8, ManifestDecodeError> {
471        Ok(self.take(1)?[0])
472    }
473
474    fn u16(&mut self) -> Result<u16, ManifestDecodeError> {
475        let bytes = self.take(2)?;
476        Ok(u16::from_be_bytes([bytes[0], bytes[1]]))
477    }
478
479    fn u32(&mut self) -> Result<u32, ManifestDecodeError> {
480        let bytes = self.take(4)?;
481        Ok(u32::from_be_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]))
482    }
483
484    fn u64(&mut self) -> Result<u64, ManifestDecodeError> {
485        let bytes = self.take(8)?;
486        let mut arr = [0u8; 8];
487        arr.copy_from_slice(bytes);
488        Ok(u64::from_be_bytes(arr))
489    }
490
491    fn hash(&mut self) -> Result<[u8; 32], ManifestDecodeError> {
492        let bytes = self.take(32)?;
493        let mut arr = [0u8; 32];
494        arr.copy_from_slice(bytes);
495        Ok(arr)
496    }
497
498    fn is_exhausted(&self) -> bool {
499        self.pos == self.bytes.len()
500    }
501}
502
503// ── Errors ──────────────────────────────────────────────────────────
504
505/// Rejected while *constructing* a node in memory.
506#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
507pub enum ManifestNodeError {
508    #[error("duplicate manifest object key {0:?}")]
509    DuplicateObjectKey(ManifestKey),
510    #[error("leaf holds {0} entries; the canonical count field is a u16")]
511    LeafCountOverflow(usize),
512    #[error("branch bitmap is empty; the canonical empty set is the empty leaf")]
513    EmptyBranchBitmap,
514    #[error("branch slot {0} is outside 0..32")]
515    SlotOutOfRange(u8),
516    #[error("duplicate branch slot {0}")]
517    DuplicateBranchSlot(u8),
518}
519
520/// Rejected while *decoding* node bytes. Each variant is a distinct corruption
521/// class and maps to a named fsck rule via
522/// [`ManifestDecodeError::fsck_rule`](super::fsck::FsckRule).
523#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
524pub enum ManifestDecodeError {
525    #[error("node does not start with the WPMF magic")]
526    BadMagic,
527    #[error("unsupported manifest format version {0}")]
528    UnsupportedVersion(u8),
529    #[error("unknown manifest node tag {0}")]
530    UnknownNodeTag(u8),
531    #[error("unknown manifest object kind {0}")]
532    UnknownObjectKind(u8),
533    #[error("node bytes are truncated")]
534    Truncated,
535    #[error("node has trailing bytes after its declared content")]
536    TrailingBytes,
537    #[error("leaf entries are not strictly ascending by (kind, hash)")]
538    EntriesOutOfOrder,
539    #[error("leaf names object key {0:?} more than once")]
540    DuplicateObjectKey(ManifestKey),
541    #[error("branch bitmap is empty; the canonical empty set is the empty leaf")]
542    EmptyBranchBitmap,
543    #[error("node bytes are a non-canonical spelling of their own content")]
544    NonCanonicalEncoding,
545    #[error("node bytes hash to {actual} but were addressed as {expected}")]
546    AddressMismatch {
547        expected: ContentHash,
548        actual: ContentHash,
549    },
550}
551
552#[cfg(test)]
553mod tests {
554    use super::*;
555
556    fn hash(seed: u8) -> ContentHash {
557        ContentHash::from_bytes([seed; 32])
558    }
559
560    fn object(seed: u8, size: u64) -> ManifestObject {
561        ManifestObject::new(ManifestObjectKind::Blob, hash(seed), size)
562    }
563
564    #[test]
565    fn empty_leaf_is_the_canonical_empty_root() {
566        let encoded = ManifestNode::empty().encode();
567        assert_eq!(encoded, b"WPMF\x01\x00\x00\x00");
568        assert_eq!(
569            ManifestNode::decode(&encoded).unwrap(),
570            ManifestNode::empty()
571        );
572    }
573
574    #[test]
575    fn leaf_layout_is_byte_exact() {
576        let leaf = ManifestNode::Leaf(ManifestLeaf::new(vec![object(1, 0x0102)]).unwrap());
577        let encoded = leaf.encode();
578        assert_eq!(&encoded[..4], b"WPMF");
579        assert_eq!(encoded[4], MANIFEST_FORMAT_VERSION);
580        assert_eq!(encoded[5], TAG_LEAF);
581        assert_eq!(&encoded[6..8], &1u16.to_be_bytes());
582        assert_eq!(encoded[8], 0); // Blob
583        assert_eq!(&encoded[9..41], &[1u8; 32]);
584        assert_eq!(&encoded[41..49], &0x0102u64.to_be_bytes());
585        assert_eq!(encoded.len(), LEAF_HEADER_LEN + LEAF_ENTRY_LEN);
586    }
587
588    #[test]
589    fn branch_layout_is_byte_exact() {
590        let branch = ManifestNode::Branch(
591            ManifestBranch::new(
592                3,
593                vec![
594                    ManifestChild {
595                        slot: 5,
596                        hash: hash(9),
597                        object_count: 17,
598                        decoded_bytes: 40,
599                    },
600                    ManifestChild {
601                        slot: 1,
602                        hash: hash(8),
603                        object_count: 2,
604                        decoded_bytes: 6,
605                    },
606                ],
607            )
608            .unwrap(),
609        );
610        let encoded = branch.encode();
611        assert_eq!(encoded[5], TAG_BRANCH);
612        assert_eq!(encoded[6], 3);
613        assert_eq!(&encoded[7..11], &0b100010u32.to_be_bytes());
614        // Children follow occupied bitmap slots in ascending order, so slot 1
615        // precedes slot 5 regardless of construction order.
616        assert_eq!(&encoded[11..43], &[8u8; 32]);
617        assert_eq!(encoded.len(), BRANCH_HEADER_LEN + 2 * BRANCH_CHILD_LEN);
618        assert_eq!(ManifestNode::decode(&encoded).unwrap(), branch);
619    }
620
621    #[test]
622    fn decode_rejects_each_corruption_class() {
623        let good = ManifestNode::Leaf(ManifestLeaf::new(vec![object(1, 1), object(2, 2)]).unwrap())
624            .encode();
625
626        let mut bad_magic = good.clone();
627        bad_magic[0] = b'X';
628        assert_eq!(
629            ManifestNode::decode(&bad_magic).unwrap_err(),
630            ManifestDecodeError::BadMagic
631        );
632
633        let mut bad_version = good.clone();
634        bad_version[4] = 2;
635        assert_eq!(
636            ManifestNode::decode(&bad_version).unwrap_err(),
637            ManifestDecodeError::UnsupportedVersion(2)
638        );
639
640        let mut bad_tag = good.clone();
641        bad_tag[5] = 7;
642        assert_eq!(
643            ManifestNode::decode(&bad_tag).unwrap_err(),
644            ManifestDecodeError::UnknownNodeTag(7)
645        );
646
647        let mut bad_kind = good.clone();
648        bad_kind[8] = 9;
649        assert_eq!(
650            ManifestNode::decode(&bad_kind).unwrap_err(),
651            ManifestDecodeError::UnknownObjectKind(9)
652        );
653
654        let mut trailing = good.clone();
655        trailing.push(0);
656        assert_eq!(
657            ManifestNode::decode(&trailing).unwrap_err(),
658            ManifestDecodeError::TrailingBytes
659        );
660
661        let truncated = &good[..good.len() - 1];
662        assert_eq!(
663            ManifestNode::decode(truncated).unwrap_err(),
664            ManifestDecodeError::Truncated
665        );
666
667        // Swap the two entries so they descend rather than ascend.
668        let mut swapped = good.clone();
669        let (a, b) = (8, 8 + LEAF_ENTRY_LEN);
670        let entry_a = good[a..a + LEAF_ENTRY_LEN].to_vec();
671        let entry_b = good[b..b + LEAF_ENTRY_LEN].to_vec();
672        swapped[a..a + LEAF_ENTRY_LEN].copy_from_slice(&entry_b);
673        swapped[b..b + LEAF_ENTRY_LEN].copy_from_slice(&entry_a);
674        assert_eq!(
675            ManifestNode::decode(&swapped).unwrap_err(),
676            ManifestDecodeError::EntriesOutOfOrder
677        );
678
679        // Duplicate the first entry over the second.
680        let mut duplicated = good.clone();
681        duplicated[b..b + LEAF_ENTRY_LEN].copy_from_slice(&entry_a);
682        assert_eq!(
683            ManifestNode::decode(&duplicated).unwrap_err(),
684            ManifestDecodeError::DuplicateObjectKey(ManifestKey::new(
685                ManifestObjectKind::Blob,
686                hash(1)
687            ))
688        );
689    }
690
691    #[test]
692    fn decode_rejects_empty_branch_bitmap() {
693        let mut bytes = Vec::new();
694        bytes.extend_from_slice(&MANIFEST_NODE_MAGIC);
695        bytes.push(MANIFEST_FORMAT_VERSION);
696        bytes.push(TAG_BRANCH);
697        bytes.push(0);
698        bytes.extend_from_slice(&0u32.to_be_bytes());
699        assert_eq!(
700            ManifestNode::decode(&bytes).unwrap_err(),
701            ManifestDecodeError::EmptyBranchBitmap
702        );
703    }
704
705    #[test]
706    fn decode_addressed_rejects_a_wrong_address() {
707        let node = ManifestNode::Leaf(ManifestLeaf::new(vec![object(1, 1)]).unwrap());
708        let bytes = node.encode();
709        let err = ManifestNode::decode_addressed(&bytes, &hash(0xff)).unwrap_err();
710        assert!(matches!(err, ManifestDecodeError::AddressMismatch { .. }));
711        assert!(ManifestNode::decode_addressed(&bytes, &node.address()).is_ok());
712    }
713
714    #[test]
715    fn route_groups_read_five_bits_msb_first() {
716        let route = ManifestRoute([0b1010_1010; 32]);
717        assert_eq!(route.group(0), 0b10101);
718        assert_eq!(route.group(1), 0b01010);
719        // The final level starts at bit 255 — the last bit of the last byte —
720        // and the remaining four are zero padding. Here that bit is 0.
721        assert_eq!(route.group(MANIFEST_ROUTE_LEVELS - 1), 0b00000);
722        // Same position, last bit set: the one real bit lands in the high
723        // position of the group and the padding stays zero.
724        assert_eq!(
725            ManifestRoute([0b1010_1011; 32]).group(MANIFEST_ROUTE_LEVELS - 1),
726            0b10000
727        );
728        // Past the route, every group is 0 — splitting must stop, not spin.
729        assert_eq!(route.group(MANIFEST_ROUTE_LEVELS), 0);
730    }
731
732    #[test]
733    fn route_is_domain_separated_from_the_raw_hash() {
734        let key = ManifestKey::new(ManifestObjectKind::Blob, hash(3));
735        assert_ne!(key.route().as_bytes(), hash(3).as_bytes());
736        // Kind participates: the same hash under a different kind routes apart.
737        let other = ManifestKey::new(ManifestObjectKind::Tree, hash(3));
738        assert_ne!(key.route().as_bytes(), other.route().as_bytes());
739    }
740
741    #[test]
742    fn constructing_a_leaf_rejects_duplicate_keys() {
743        let err = ManifestLeaf::new(vec![object(1, 1), object(1, 1)]).unwrap_err();
744        assert!(matches!(err, ManifestNodeError::DuplicateObjectKey(_)));
745    }
746}
heddle_object_model/object/manifest/node.rs

heddle_object_model/object/manifest/
node.rs
