javm_cap/
cnode.rs

1//! `CNodeCap` — CNode cap.
2//!
3//! Slot table is a [`SparseList`] of [`MissingOr`] entries: a sparse
4//! materialized-on-demand map from `SlotIdx` to [`CapHashOrRef`]. The
5//! merkle tree shape is fixed at depth 16 (= ceil_log2(MAX_CNODE_SLOTS))
6//! regardless of `size_log`; `size_log` is runtime metadata used for
7//! bounds-checking slot indices.
8//!
9//! Empty slots contribute `zero_hash` at the depth-16 leaf level; a
10//! `Missing(h)` placeholder substitutes losslessly for the materialized
11//! contents whose `hash_tree_root` equals `h`. This is the load-bearing
12//! property for sparse cnode loading from cold storage.
13//!
14//! `size_log` is permitted in `0..=16` (the spec's hard ceiling).
15
16use ssz::{MissingOr, SparseList};
17
18use crate::error::CapError;
19use crate::slot::SlotIdx;
20
21use super::cap::CapHashOrRef;
22
23/// Maximum cnode capacity (`2^16` slots). The SSZ merkle tree depth is
24/// fixed at 16 regardless of an individual cnode's declared `size_log`.
25pub const MAX_CNODE_SLOTS: u64 = 1u64 << 16;
26
27#[derive(Clone, Debug, ssz_derive::HashTreeRoot)]
28pub struct CNodeCap {
29    pub size_log: u8,
30    /// Sparse slot table keyed by slot index. Missing keys are absent
31    /// slots (contribute `zero_hash` to the merkle root). The merkle
32    /// tree is always size `MAX_CNODE_SLOTS = 2^16`; `size_log` bounds
33    /// the addressable range.
34    pub slots: SparseList<CapHashOrRef, MAX_CNODE_SLOTS>,
35}
36
37impl CNodeCap {
38    /// Construct an empty cnode of `2^size_log` slots.
39    /// Rejects `size_log > 16`.
40    pub fn new(size_log: u8) -> Result<Self, CapError> {
41        if size_log > 16 {
42            return Err(CapError::InvalidCNodeSize(size_log));
43        }
44        Ok(Self {
45            size_log,
46            slots: SparseList::new(),
47        })
48    }
49
50    /// Number of slots in the cnode (`2^size_log`).
51    pub fn capacity(&self) -> u64 {
52        1u64 << self.size_log
53    }
54
55    /// Look up a slot by index. Returns `None` for empty (unmaterialized)
56    /// slots; returns the materialized `CapHashOrRef` otherwise.
57    ///
58    /// For a `MissingOr::Missing(_)` placeholder slot (used when a
59    /// subtree was loaded by hash without contents), this returns
60    /// `None` — callers needing to distinguish "absent" from "missing
61    /// placeholder" should inspect `self.slots.get(...)` directly.
62    pub fn get(&self, slot: SlotIdx) -> Option<CapHashOrRef> {
63        match self.slots.get(slot.get() as u64)? {
64            MissingOr::Materialized(t) => Some(t.clone()),
65            MissingOr::Missing(_) => None,
66        }
67    }
68
69    /// Bind `slot` to `target`, or clear the binding if `target` is
70    /// `None`. Rejects slot indices outside the cnode's `2^size_log`
71    /// range. Returns the prior materialized target at `slot`, if any.
72    pub fn set(
73        &mut self,
74        slot: SlotIdx,
75        target: Option<CapHashOrRef>,
76    ) -> Result<Option<CapHashOrRef>, CapError> {
77        if !slot.fits(self.size_log) {
78            return Err(CapError::SlotOutOfRange(slot.get(), self.size_log));
79        }
80        let key = slot.get() as u64;
81        let prior = match self.slots.get(key) {
82            Some(MissingOr::Materialized(t)) => Some(t.clone()),
83            Some(MissingOr::Missing(_)) | None => None,
84        };
85        match target {
86            Some(t) => {
87                // `MAX_CNODE_SLOTS = 2^16` and `slot.fits(size_log)` with
88                // `size_log <= 16` guarantee `key < MAX_CNODE_SLOTS`, so
89                // the bound check inside `SparseList::insert` cannot fail.
90                self.slots
91                    .insert(key, MissingOr::Materialized(t))
92                    .expect("slot index fits cnode capacity (checked above)");
93            }
94            None => {
95                self.slots.remove(key);
96            }
97        }
98        Ok(prior)
99    }
100
101    /// Take the binding at `slot`, leaving the slot empty. Returns the
102    /// prior target (or `None` if the slot was already empty).
103    pub fn take(&mut self, slot: SlotIdx) -> Result<Option<CapHashOrRef>, CapError> {
104        self.set(slot, None)
105    }
106
107    /// Alias of `set(slot, None)`.
108    pub fn remove(&mut self, slot: SlotIdx) -> Result<Option<CapHashOrRef>, CapError> {
109        self.set(slot, None)
110    }
111}
112
113/// One populated slot — retained as a serialisation helper for callers
114/// that need a flat `(slot, target)` pair (e.g., `CacheDirectory::publish_cnode`).
115///
116/// The on-the-wire/hash representation of `CNodeCap` no longer uses this
117/// type; the cnode is encoded directly as a `SparseList<CapHashOrRef, ...>`.
118#[derive(Clone, Debug, PartialEq, Eq)]
119pub struct CNodeSlotEntry {
120    pub slot: SlotIdx,
121    pub target: CapHashOrRef,
122}
javm_cap/cnode.rs

javm_cap/
cnode.rs
