#6806

Committed 22 Jan 2026 01:11PM UTC coverage: 48.357% (-0.01%) from 48.367%

Build # #6806

Build Type

Committed by

Commit Message

go/worker/storage: Fix runtime state pruner

Prior to this change it could happen that if you had pruning
configured and then you disable it, the runtime state would still
be pruned on the next restart.

This is because light history and runtime state pruning are
decoupled, and state pruner simply removes all state rounds older
than the last retained light history round. Since light history
pruning is much faster, it could happen that even after restart
and explicitly disabling pruning the pruner would still have
some pending work to do.

Pull Request Pull Request #6446: go/worker/storage: Fix runtime state pruner

Run Details

4679 of 9676 relevant lines covered (48.36%)

1.1 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

67.78

/runtime/src/storage/mkvs/tree/node.rs

use std::{cell::RefCell, rc::Rc};

use crate::{
    common::{crypto::hash::Hash, namespace::Namespace},
    storage::mkvs::{
        cache::{CacheExtra, CacheItem},
        marshal::Marshal,
    },
};

/// Common interface for node-like objects in the tree.
pub trait Node {
    /// Check whether the node is clean or not.
    fn is_clean(&self) -> bool;
    /// Get the node's hash.
    fn get_hash(&self) -> Hash;
    /// Recompute the node's hash.
    fn update_hash(&mut self);
    /// Duplicate the node but include only hash references.
    #[allow(dead_code)]
    fn extract(&self) -> NodeRef;
}

/// Storage root type.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, cbor::Encode, cbor::Decode)]
#[repr(u8)]
pub enum RootType {
    /// Invalid or uninitialized storage root type.
    #[default]
    Invalid = 0,
    /// Storage root for runtime state.
    State = 1,
    /// Storage root for transaction IO.
    IO = 2,
}

/// Storage root.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, cbor::Encode, cbor::Decode)]
pub struct Root {
    /// Namespace under which the root is stored.
    #[cbor(rename = "ns")]
    pub namespace: Namespace,
    /// Monotonically increasing version number in which the root is stored.
    pub version: u64,
    /// The storage type that this root has data for.
    pub root_type: RootType,
    /// Merkle root hash.
    pub hash: Hash,
}

/// A box type that can contain either internal or leaf nodes.
#[derive(Debug, Eq, PartialEq)]
pub enum NodeBox {
    Internal(InternalNode),
    Leaf(LeafNode),
}

impl Default for NodeBox {
    fn default() -> Self {
        NodeBox::Internal(Default::default())
    }
}

impl Node for NodeBox {
    fn is_clean(&self) -> bool {
        match self {
            NodeBox::Internal(ref n) => n.is_clean(),
            NodeBox::Leaf(ref n) => n.is_clean(),
        }
    }

    fn get_hash(&self) -> Hash {
        match self {
            NodeBox::Internal(ref n) => n.get_hash(),
            NodeBox::Leaf(ref n) => n.get_hash(),
        }
    }

    fn update_hash(&mut self) {
        match self {
            NodeBox::Internal(ref mut n) => n.update_hash(),
            NodeBox::Leaf(ref mut n) => n.update_hash(),
        }
    }

    fn extract(&self) -> NodeRef {
        match self {
            NodeBox::Internal(ref n) => n.extract(),
            NodeBox::Leaf(ref n) => n.extract(),
        }
    }
}

/// Node types in the tree.
///
/// Integer values of the variants here are also used in subtree
/// serialization and as prefixes in node hash computations.
#[derive(Copy, Clone, Debug)]
#[repr(u8)]
pub enum NodeKind {
    None = 0x02,
    Internal = 0x01,
    Leaf = 0x00,
}

/// `NodeRef` is a reference-counted pointer to a node box.
pub type NodeRef = Rc<RefCell<NodeBox>>;

/// A pointer to a node in the tree.
#[derive(Debug, Default)]
pub struct NodePointer {
    pub clean: bool,
    pub hash: Hash,
    pub node: Option<NodeRef>,

    pub cache_extra: CacheExtra<NodePointer>,
}

/// A reference-counted pointer to a pointer.
pub type NodePtrRef = Rc<RefCell<NodePointer>>;

impl NodePointer {
    /// Construct a null pointer.
    pub fn null_ptr() -> NodePtrRef {
        Rc::new(RefCell::new(NodePointer {
            node: None,
            clean: true,
            hash: Hash::empty_hash(),
            ..Default::default()
        }))
    }

    /// Construct a hash-only pointer.
    pub fn hash_ptr(hash: Hash) -> NodePtrRef {
        Rc::new(RefCell::new(NodePointer {
            node: None,
            clean: true,
            hash,
            ..Default::default()
        }))
    }

    /// Construct a node pointer from a full node.
    pub fn from_node(node: NodeBox) -> NodePtrRef {
        Rc::new(RefCell::new(NodePointer {
            hash: node.get_hash(),
            node: Some(Rc::new(RefCell::new(node))),
            clean: true,
            ..Default::default()
        }))
    }

    /// Check if the pointer is a null pointer.
    pub fn is_null(&self) -> bool {
        self.hash.is_empty()
    }

    /// Check if the pointer has a resolved reference to a concrete node.
    pub fn has_node(&self) -> bool {
        !self.is_null() && self.node.is_some()
    }

    /// Get a reference to the node the pointer is pointing to.
    pub fn get_node(&self) -> NodeRef {
        match &self.node {
            None => panic!("mkvs: get_node called on pointer without a node"),
            Some(node) => node.clone(),
        }
    }

    /// Return a copy of this pointer containing only hash references.
    pub fn extract(&self) -> NodePtrRef {
        assert!(self.clean, "mkvs: extract called on dirty pointer");

        Rc::new(RefCell::new(NodePointer {
            clean: true,
            hash: self.hash,
            ..Default::default()
        }))
    }

    // Make deep copy of the Pointer to LeafNode excluding LRU and DBInternal.
    //
    // Panics, if it's called on non-leaf node pointer.
    #[allow(dead_code)]
    fn copy_leaf_ptr(&self) -> NodePtrRef {
        if !self.has_node() {
            return NodePointer::null_ptr();
        }

        assert!(self.clean, "mkvs: copy_leaf_ptr called on dirty pointer");

        if let Some(ref some_node) = self.node {
            let nyoo = noderef_as!(some_node, Leaf).copy();
            Rc::new(RefCell::new(NodePointer {
                clean: true,
                hash: self.hash,
                node: Some(Rc::new(RefCell::new(NodeBox::Leaf(nyoo)))),
                ..Default::default()
            }))
        } else {
            panic!("mkvs: copy_leaf_ptr called on a non-leaf pointer");
        }
    }
}

impl CacheItem for NodePointer {
    fn get_cache_extra(&self) -> CacheExtra<NodePointer> {
        self.cache_extra
    }

    fn set_cache_extra(&mut self, new_val: CacheExtra<NodePointer>) {
        self.cache_extra = new_val;
    }

    fn get_cached_size(&self) -> usize {
        1
    }
}

impl PartialEq for NodePointer {
    fn eq(&self, other: &NodePointer) -> bool {
        if self.clean && other.clean {
            self.hash == other.hash
        } else {
            self.node.is_some() && self.node == other.node
        }
    }
}

impl Eq for NodePointer {}

/// An internal tree node with two children and possibly a leaf.
#[derive(Debug, Default)]
pub struct InternalNode {
    pub clean: bool,
    pub hash: Hash,
    pub label: Key,              // label on the incoming edge
    pub label_bit_length: Depth, // length of the label in bits
    pub leaf_node: NodePtrRef,   // for the key ending at this depth
    pub left: NodePtrRef,
    pub right: NodePtrRef,
}

impl Node for InternalNode {
    fn is_clean(&self) -> bool {
        self.clean
    }

    fn get_hash(&self) -> Hash {
        self.hash
    }

    fn update_hash(&mut self) {
        let leaf_node_hash = self.leaf_node.borrow().hash;
        let left_hash = self.left.borrow().hash;
        let right_hash = self.right.borrow().hash;

        self.hash = Hash::digest_bytes_list(&[
            &[NodeKind::Internal as u8],
            &self.label_bit_length.marshal_binary().unwrap(),
            self.label.as_ref(),
            leaf_node_hash.as_ref(),
            left_hash.as_ref(),
            right_hash.as_ref(),
        ]);
    }

    fn extract(&self) -> NodeRef {
        assert!(self.clean, "mkvs: extract called on dirty node");

        Rc::new(RefCell::new(NodeBox::Internal(InternalNode {
            clean: true,
            hash: self.hash,
            label: self.label.clone(),
            label_bit_length: self.label_bit_length,
            leaf_node: self.leaf_node.borrow().copy_leaf_ptr(),
            left: self.left.borrow().extract(),
            right: self.right.borrow().extract(),
        })))
    }
}

impl PartialEq for InternalNode {
    fn eq(&self, other: &InternalNode) -> bool {
        if self.clean && other.clean {
            self.hash == other.hash
        } else {
            self.leaf_node == other.leaf_node
                && self.left == other.left
                && self.right == other.right
        }
    }
}

impl Eq for InternalNode {}

/// A leaf node containing a key/value pair.
#[derive(Debug, Default)]
pub struct LeafNode {
    pub clean: bool,
    pub hash: Hash,
    pub key: Key,
    pub value: Value,
}

impl LeafNode {
    pub fn copy(&self) -> LeafNode {
        LeafNode {
            clean: self.clean,
            hash: self.hash,
            key: self.key.to_owned(),
            value: self.value.clone(),
        }
    }
}

impl Node for LeafNode {
    fn is_clean(&self) -> bool {
        self.clean
    }

    fn get_hash(&self) -> Hash {
        self.hash
    }

    fn update_hash(&mut self) {
        self.hash = Hash::digest_bytes_list(&[
            &[NodeKind::Leaf as u8],
            &(self.key.len() as u32).marshal_binary().unwrap(),
            self.key.as_ref(),
            &(self.value.len() as u32).marshal_binary().unwrap(),
            self.value.as_ref(),
        ]);
    }

    fn extract(&self) -> NodeRef {
        assert!(self.clean, "mkvs: extract called on dirty node");
        Rc::new(RefCell::new(NodeBox::Leaf(LeafNode {
            clean: true,
            hash: self.hash,
            key: self.key.clone(),
            value: self.value.clone(),
        })))
    }
}

impl PartialEq for LeafNode {
    fn eq(&self, other: &LeafNode) -> bool {
        if self.clean && other.clean {
            self.hash == other.hash
        } else {
            self.key == other.key && self.value == other.value
        }
    }
}

impl Eq for LeafNode {}

// Depth determines the maximum length of the key in bits.
//
// max length = 2^size_of(Depth)*8
pub type Depth = u16;

pub trait DepthTrait {
    // Returns the number of bytes needed to fit given bits.
    fn to_bytes(&self) -> usize;
}

impl DepthTrait for Depth {
    fn to_bytes(&self) -> usize {
        let size = self / 8;
        if !self.is_multiple_of(8) {
            (size + 1) as usize
        } else {
            size as usize
        }
    }
}

// Key holds variable-length key.
pub type Key = Vec<u8>;

pub trait KeyTrait {
    /// Get a single bit from the given hash.
    fn get_bit(&self, bit: Depth) -> bool;
    /// Returns the length of the key in bits.
    fn bit_length(&self) -> Depth;
    /// Bit-wise splits of the key.
    fn split(&self, split_point: Depth, key_len: Depth) -> (Key, Key);
    /// Bit-wise merges key of given length with another key of given length.
    fn merge(&self, key_len: Depth, k2: &Key, k2_len: Depth) -> Key;
    /// Appends the given bit to the key.
    fn append_bit(&self, key_len: Depth, bit: bool) -> Key;
    /// Computes length of common prefix of k and k2 with given bit lengths.
    fn common_prefix_len(&self, key_len: Depth, k2: &Key, k2_len: Depth) -> Depth;
}

impl KeyTrait for Key {
    fn get_bit(&self, bit: Depth) -> bool {
        (self[(bit / 8) as usize] & (1 << (7 - (bit % 8)))) != 0
    }

    fn bit_length(&self) -> Depth {
        (self.len() * 8) as Depth
    }

    fn split(&self, split_point: Depth, key_len: Depth) -> (Key, Key) {
        assert!(
            split_point <= key_len,
            "mkvs: split_point {} greater than key_len {}",
            split_point,
            key_len
        );

        let prefix_len = split_point.to_bytes();
        let suffix_len = (key_len - split_point).to_bytes();
        let mut prefix: Key = vec![0; prefix_len];
        let mut suffix: Key = vec![0; suffix_len];

        prefix.clone_from_slice(&self[0..split_point.to_bytes()]);

        // Clean the remainder of the byte.
        if !split_point.is_multiple_of(8) {
            prefix[prefix_len - 1] &= 0xff << (8 - split_point % 8)
        }

        for i in 0..suffix_len {
            // First set the left chunk of the byte
            suffix[i] = self[i + split_point as usize / 8] << (split_point % 8);
            // ...and the right chunk, if we haven't reached the end of k yet.
            if !split_point.is_multiple_of(8) && i + split_point as usize / 8 + 1 != self.len() {
                suffix[i] |=
                    self[i + split_point as usize / 8 + 1] >> (8 - split_point as usize % 8);
            }
        }

        (prefix, suffix)
    }

    fn merge(&self, key_len: Depth, k2: &Key, k2_len: Depth) -> Key {
        let mut key_len_bytes = (key_len as usize) / 8;
        if !key_len.is_multiple_of(8) {
            key_len_bytes += 1;
        }

        let mut new_key: Key = vec![0; (key_len + k2_len).to_bytes()];
        new_key[..key_len_bytes].clone_from_slice(&self[..key_len_bytes]);

        for i in 0..k2.len() {
            // First set the right chunk of the previous byte
            if !key_len.is_multiple_of(8) && key_len_bytes > 0 {
                new_key[key_len_bytes + i - 1] |= k2[i] >> (key_len % 8);
            }
            // ...and the next left chunk, if we haven't reached the end of newKey
            // yet.
            if key_len_bytes + i < new_key.len() {
                // another mod 8 to prevent bit shifting for 8 bits
                new_key[key_len_bytes + i] |= k2[i] << ((8 - key_len % 8) % 8);
            }
        }

        new_key
    }

    fn append_bit(&self, key_len: Depth, val: bool) -> Key {
        let mut new_key: Key = vec![0; (key_len + 1).to_bytes()];
        new_key[..self.len()].clone_from_slice(self);

        if val {
            new_key[key_len as usize / 8] |= 0x80 >> (key_len % 8)
        } else {
            new_key[key_len as usize / 8] &= !(0x80 >> (key_len % 8))
        }

        new_key
    }

    fn common_prefix_len(&self, key_bit_len: Depth, k2: &Key, k2_bit_len: Depth) -> Depth {
        let min_key_len = if k2.len() < self.len() {
            k2.len()
        } else {
            self.len()
        };

        // Compute the common prefix byte-wise.
        let mut i: usize = 0;
        while i < min_key_len {
            if self[i] != k2[i] {
                break;
            }
            i += 1;
        }

        // Prefixes match i bytes and maybe some more bits below.
        let mut bit_length = (i * 8) as Depth;

        if i != self.len() && i != k2.len() {
            // We got a mismatch somewhere along the way. We need to compute how
            // many additional bits in i-th byte match.
            bit_length += (self[i] ^ k2[i]).leading_zeros() as Depth;
        }

        // In any case, bit_length should never exceed length of the shorter key.
        if bit_length > key_bit_len {
            bit_length = key_bit_len;
        }
        if bit_length > k2_bit_len {
            bit_length = k2_bit_len;
        };
        bit_length
    }
}

// Value holds the leaf node value.
pub type Value = Vec<u8>;

1	use std::{cell::RefCell, rc::Rc};
2
3	use crate::{
4	common::{crypto::hash::Hash, namespace::Namespace},
5	storage::mkvs::{
6	cache::{CacheExtra, CacheItem},
7	marshal::Marshal,
8	},
9	};
10
11	/// Common interface for node-like objects in the tree.
12	pub trait Node {
13	/// Check whether the node is clean or not.
14	fn is_clean(&self) -> bool;
15	/// Get the node's hash.
16	fn get_hash(&self) -> Hash;
17	/// Recompute the node's hash.
18	fn update_hash(&mut self);
19	/// Duplicate the node but include only hash references.
20	#[allow(dead_code)]
21	fn extract(&self) -> NodeRef;
22	}
23
24	/// Storage root type.
25	#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, cbor::Encode, cbor::Decode)]
26	#[repr(u8)]
27	pub enum RootType {
28	/// Invalid or uninitialized storage root type.
29	#[default]
30	Invalid = 0,
31	/// Storage root for runtime state.
32	State = 1,
33	/// Storage root for transaction IO.
34	IO = 2,
35	}
36
37	/// Storage root.
38	#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, cbor::Encode, cbor::Decode)]
39	pub struct Root {
40	/// Namespace under which the root is stored.
41	#[cbor(rename = "ns")]
42	pub namespace: Namespace,
43	/// Monotonically increasing version number in which the root is stored.
44	pub version: u64,
45	/// The storage type that this root has data for.
46	pub root_type: RootType,
47	/// Merkle root hash.
48	pub hash: Hash,
49	}
50
51	/// A box type that can contain either internal or leaf nodes.
52	#[derive(Debug, Eq, PartialEq)]
53	pub enum NodeBox {
54	Internal(InternalNode),
55	Leaf(LeafNode),
56	}
57
58	impl Default for NodeBox {
59	fn default() -> Self {	1✔
60	NodeBox::Internal(Default::default())	1✔
61	}
62	}
63
64	impl Node for NodeBox {
65	fn is_clean(&self) -> bool {	3✔
66	match self {	3✔
67	NodeBox::Internal(ref n) => n.is_clean(),	3✔
68	NodeBox::Leaf(ref n) => n.is_clean(),	3✔
69	}
70	}
71
72	fn get_hash(&self) -> Hash {	1✔
73	match self {	2✔
74	NodeBox::Internal(ref n) => n.get_hash(),	2✔
75	NodeBox::Leaf(ref n) => n.get_hash(),	2✔
76	}
77	}
78
79	fn update_hash(&mut self) {	3✔
80	match self {	3✔
81	NodeBox::Internal(ref mut n) => n.update_hash(),	3✔
82	NodeBox::Leaf(ref mut n) => n.update_hash(),	3✔
83	}
84	}
85
86	fn extract(&self) -> NodeRef {	×
87	match self {	×
88	NodeBox::Internal(ref n) => n.extract(),	×
89	NodeBox::Leaf(ref n) => n.extract(),	×
90	}
91	}
92	}
93
94	/// Node types in the tree.
95	///
96	/// Integer values of the variants here are also used in subtree
97	/// serialization and as prefixes in node hash computations.
98	#[derive(Copy, Clone, Debug)]
99	#[repr(u8)]
100	pub enum NodeKind {
101	None = 0x02,
102	Internal = 0x01,
103	Leaf = 0x00,
104	}
105
106	/// `NodeRef` is a reference-counted pointer to a node box.
107	pub type NodeRef = Rc<RefCell<NodeBox>>;
108
109	/// A pointer to a node in the tree.
110	#[derive(Debug, Default)]
111	pub struct NodePointer {
112	pub clean: bool,
113	pub hash: Hash,
114	pub node: Option<NodeRef>,
115
116	pub cache_extra: CacheExtra<NodePointer>,
117	}
118
119	/// A reference-counted pointer to a pointer.
120	pub type NodePtrRef = Rc<RefCell<NodePointer>>;
121
122	impl NodePointer {
123	/// Construct a null pointer.
124	pub fn null_ptr() -> NodePtrRef {	1✔
125	Rc::new(RefCell::new(NodePointer {	2✔
126	node: None,	1✔
127	clean: true,
128	hash: Hash::empty_hash(),	1✔
129	..Default::default()	1✔
130	}))
131	}
132
133	/// Construct a hash-only pointer.
134	pub fn hash_ptr(hash: Hash) -> NodePtrRef {	1✔
135	Rc::new(RefCell::new(NodePointer {	2✔
136	node: None,	1✔
137	clean: true,
138	hash,
139	..Default::default()	1✔
140	}))
141	}
142
143	/// Construct a node pointer from a full node.
144	pub fn from_node(node: NodeBox) -> NodePtrRef {	1✔
145	Rc::new(RefCell::new(NodePointer {	5✔
146	hash: node.get_hash(),	1✔
147	node: Some(Rc::new(RefCell::new(node))),	2✔
148	clean: true,
149	..Default::default()	2✔
150	}))
151	}
152
153	/// Check if the pointer is a null pointer.
154	pub fn is_null(&self) -> bool {	1✔
155	self.hash.is_empty()	1✔
156	}
157
158	/// Check if the pointer has a resolved reference to a concrete node.
159	pub fn has_node(&self) -> bool {	×
160	!self.is_null() && self.node.is_some()	×
161	}
162
163	/// Get a reference to the node the pointer is pointing to.
164	pub fn get_node(&self) -> NodeRef {	2✔
165	match &self.node {	2✔
166	None => panic!("mkvs: get_node called on pointer without a node"),	×
167	Some(node) => node.clone(),	2✔
168	}
169	}
170
171	/// Return a copy of this pointer containing only hash references.
172	pub fn extract(&self) -> NodePtrRef {	×
173	assert!(self.clean, "mkvs: extract called on dirty pointer");	×
174
175	Rc::new(RefCell::new(NodePointer {	×
176	clean: true,
177	hash: self.hash,	×
178	..Default::default()	×
179	}))
180	}
181
182	// Make deep copy of the Pointer to LeafNode excluding LRU and DBInternal.
183	//
184	// Panics, if it's called on non-leaf node pointer.
185	#[allow(dead_code)]
186	fn copy_leaf_ptr(&self) -> NodePtrRef {	×
187	if !self.has_node() {	×
188	return NodePointer::null_ptr();	×
189	}
190
191	assert!(self.clean, "mkvs: copy_leaf_ptr called on dirty pointer");	×
192
193	if let Some(ref some_node) = self.node {	×
194	let nyoo = noderef_as!(some_node, Leaf).copy();	×
195	Rc::new(RefCell::new(NodePointer {	×
196	clean: true,
197	hash: self.hash,	×
198	node: Some(Rc::new(RefCell::new(NodeBox::Leaf(nyoo)))),	×
199	..Default::default()	×
200	}))
201	} else {
202	panic!("mkvs: copy_leaf_ptr called on a non-leaf pointer");	×
203	}
204	}
205	}
206
207	impl CacheItem for NodePointer {
208	fn get_cache_extra(&self) -> CacheExtra<NodePointer> {	1✔
209	self.cache_extra	1✔
210	}
211
212	fn set_cache_extra(&mut self, new_val: CacheExtra<NodePointer>) {	2✔
213	self.cache_extra = new_val;	2✔
214	}
215
216	fn get_cached_size(&self) -> usize {	2✔
217	1
218	}
219	}
220
221	impl PartialEq for NodePointer {
222	fn eq(&self, other: &NodePointer) -> bool {	×
223	if self.clean && other.clean {	×
224	self.hash == other.hash	×
225	} else {
226	self.node.is_some() && self.node == other.node	×
227	}
228	}
229	}
230
231	impl Eq for NodePointer {}
232
233	/// An internal tree node with two children and possibly a leaf.
234	#[derive(Debug, Default)]
235	pub struct InternalNode {
236	pub clean: bool,
237	pub hash: Hash,
238	pub label: Key, // label on the incoming edge
239	pub label_bit_length: Depth, // length of the label in bits
240	pub leaf_node: NodePtrRef, // for the key ending at this depth
241	pub left: NodePtrRef,
242	pub right: NodePtrRef,
243	}
244
245	impl Node for InternalNode {
246	fn is_clean(&self) -> bool {	3✔
247	self.clean	3✔
248	}
249
250	fn get_hash(&self) -> Hash {	2✔
251	self.hash	2✔
252	}
253
254	fn update_hash(&mut self) {	2✔
255	let leaf_node_hash = self.leaf_node.borrow().hash;	2✔
256	let left_hash = self.left.borrow().hash;	2✔
257	let right_hash = self.right.borrow().hash;	2✔
258
259	self.hash = Hash::digest_bytes_list(&[	2✔
260	&[NodeKind::Internal as u8],	2✔
261	&self.label_bit_length.marshal_binary().unwrap(),	2✔
262	self.label.as_ref(),	2✔
263	leaf_node_hash.as_ref(),	2✔
264	left_hash.as_ref(),	2✔
265	right_hash.as_ref(),	2✔
266	]);
267	}
268
269	fn extract(&self) -> NodeRef {	×
270	assert!(self.clean, "mkvs: extract called on dirty node");	×
271
272	Rc::new(RefCell::new(NodeBox::Internal(InternalNode {	×
273	clean: true,
274	hash: self.hash,	×
275	label: self.label.clone(),	×
276	label_bit_length: self.label_bit_length,	×
277	leaf_node: self.leaf_node.borrow().copy_leaf_ptr(),	×
278	left: self.left.borrow().extract(),	×
279	right: self.right.borrow().extract(),	×
280	})))
281	}
282	}
283
284	impl PartialEq for InternalNode {
285	fn eq(&self, other: &InternalNode) -> bool {	×
286	if self.clean && other.clean {	×
287	self.hash == other.hash	×
288	} else {
289	self.leaf_node == other.leaf_node	×
290	&& self.left == other.left	×
291	&& self.right == other.right	×
292	}
293	}
294	}
295
296	impl Eq for InternalNode {}
297
298	/// A leaf node containing a key/value pair.
299	#[derive(Debug, Default)]
300	pub struct LeafNode {
301	pub clean: bool,
302	pub hash: Hash,
303	pub key: Key,
304	pub value: Value,
305	}
306
307	impl LeafNode {
308	pub fn copy(&self) -> LeafNode {	×
309	LeafNode {
310	clean: self.clean,	×
311	hash: self.hash,	×
312	key: self.key.to_owned(),	×
313	value: self.value.clone(),	×
314	}
315	}
316	}
317
318	impl Node for LeafNode {
319	fn is_clean(&self) -> bool {	3✔
320	self.clean	3✔
321	}
322
323	fn get_hash(&self) -> Hash {	2✔
324	self.hash	2✔
325	}
326
327	fn update_hash(&mut self) {	1✔
328	self.hash = Hash::digest_bytes_list(&[	1✔
329	&[NodeKind::Leaf as u8],	1✔
330	&(self.key.len() as u32).marshal_binary().unwrap(),	1✔
331	self.key.as_ref(),	1✔
332	&(self.value.len() as u32).marshal_binary().unwrap(),	1✔
333	self.value.as_ref(),	1✔
334	]);
335	}
336
337	fn extract(&self) -> NodeRef {	×
338	assert!(self.clean, "mkvs: extract called on dirty node");	×
339	Rc::new(RefCell::new(NodeBox::Leaf(LeafNode {	×
340	clean: true,
341	hash: self.hash,	×
342	key: self.key.clone(),	×
343	value: self.value.clone(),	×
344	})))
345	}
346	}
347
348	impl PartialEq for LeafNode {
349	fn eq(&self, other: &LeafNode) -> bool {	×
350	if self.clean && other.clean {	×
351	self.hash == other.hash	×
352	} else {
353	self.key == other.key && self.value == other.value	×
354	}
355	}
356	}
357
358	impl Eq for LeafNode {}
359
360	// Depth determines the maximum length of the key in bits.
361	//
362	// max length = 2^size_of(Depth)*8
363	pub type Depth = u16;
364
365	pub trait DepthTrait {
366	// Returns the number of bytes needed to fit given bits.
367	fn to_bytes(&self) -> usize;
368	}
369
370	impl DepthTrait for Depth {
371	fn to_bytes(&self) -> usize {	1✔
372	let size = self / 8;	1✔
373	if !self.is_multiple_of(8) {	3✔
374	(size + 1) as usize	2✔
375	} else {
376	size as usize	1✔
377	}
378	}
379	}
380
381	// Key holds variable-length key.
382	pub type Key = Vec<u8>;
383
384	pub trait KeyTrait {
385	/// Get a single bit from the given hash.
386	fn get_bit(&self, bit: Depth) -> bool;
387	/// Returns the length of the key in bits.
388	fn bit_length(&self) -> Depth;
389	/// Bit-wise splits of the key.
390	fn split(&self, split_point: Depth, key_len: Depth) -> (Key, Key);
391	/// Bit-wise merges key of given length with another key of given length.
392	fn merge(&self, key_len: Depth, k2: &Key, k2_len: Depth) -> Key;
393	/// Appends the given bit to the key.
394	fn append_bit(&self, key_len: Depth, bit: bool) -> Key;
395	/// Computes length of common prefix of k and k2 with given bit lengths.
396	fn common_prefix_len(&self, key_len: Depth, k2: &Key, k2_len: Depth) -> Depth;
397	}
398
399	impl KeyTrait for Key {
400	fn get_bit(&self, bit: Depth) -> bool {	1✔
401	(self[(bit / 8) as usize] & (1 << (7 - (bit % 8)))) != 0	1✔
402	}
403
404	fn bit_length(&self) -> Depth {	1✔
405	(self.len() * 8) as Depth	1✔
406	}
407
408	fn split(&self, split_point: Depth, key_len: Depth) -> (Key, Key) {	1✔
409	assert!(	×
410	split_point <= key_len,
411	"mkvs: split_point {} greater than key_len {}",
412	split_point,
413	key_len
414	);
415
416	let prefix_len = split_point.to_bytes();	1✔
417	let suffix_len = (key_len - split_point).to_bytes();	1✔
418	let mut prefix: Key = vec![0; prefix_len];	1✔
419	let mut suffix: Key = vec![0; suffix_len];	1✔
420
421	prefix.clone_from_slice(&self[0..split_point.to_bytes()]);	2✔
422
423	// Clean the remainder of the byte.
424	if !split_point.is_multiple_of(8) {	2✔
425	prefix[prefix_len - 1] &= 0xff << (8 - split_point % 8)	2✔
426	}
427
428	for i in 0..suffix_len {	2✔
429	// First set the left chunk of the byte
430	suffix[i] = self[i + split_point as usize / 8] << (split_point % 8);	2✔
431	// ...and the right chunk, if we haven't reached the end of k yet.
432	if !split_point.is_multiple_of(8) && i + split_point as usize / 8 + 1 != self.len() {	2✔
433	suffix[i] \|=	2✔
434	self[i + split_point as usize / 8 + 1] >> (8 - split_point as usize % 8);	1✔
435	}
436	}
437
438	(prefix, suffix)	1✔
439	}
440
441	fn merge(&self, key_len: Depth, k2: &Key, k2_len: Depth) -> Key {	2✔
442	let mut key_len_bytes = (key_len as usize) / 8;	2✔
443	if !key_len.is_multiple_of(8) {	4✔
444	key_len_bytes += 1;	4✔
445	}
446
447	let mut new_key: Key = vec![0; (key_len + k2_len).to_bytes()];	4✔
448	new_key[..key_len_bytes].clone_from_slice(&self[..key_len_bytes]);	4✔
449
450	for i in 0..k2.len() {	2✔
451	// First set the right chunk of the previous byte
452	if !key_len.is_multiple_of(8) && key_len_bytes > 0 {	6✔
453	new_key[key_len_bytes + i - 1] \|= k2[i] >> (key_len % 8);	2✔
454	}
455	// ...and the next left chunk, if we haven't reached the end of newKey
456	// yet.
457	if key_len_bytes + i < new_key.len() {	6✔
458	// another mod 8 to prevent bit shifting for 8 bits
459	new_key[key_len_bytes + i] \|= k2[i] << ((8 - key_len % 8) % 8);	2✔
460	}
461	}
462
463	new_key	2✔
464	}
465
466	fn append_bit(&self, key_len: Depth, val: bool) -> Key {	1✔
467	let mut new_key: Key = vec![0; (key_len + 1).to_bytes()];	1✔
468	new_key[..self.len()].clone_from_slice(self);	2✔
469
470	if val {	3✔
471	new_key[key_len as usize / 8] \|= 0x80 >> (key_len % 8)	2✔
472	} else {
473	new_key[key_len as usize / 8] &= !(0x80 >> (key_len % 8))	2✔
474	}
475
476	new_key	1✔
477	}
478
479	fn common_prefix_len(&self, key_bit_len: Depth, k2: &Key, k2_bit_len: Depth) -> Depth {	1✔
480	let min_key_len = if k2.len() < self.len() {	1✔
481	k2.len()	1✔
482	} else {
483	self.len()	1✔
484	};
485
486	// Compute the common prefix byte-wise.
487	let mut i: usize = 0;	1✔
488	while i < min_key_len {	3✔
489	if self[i] != k2[i] {	1✔
490	break;
491	}
492	i += 1;	1✔
493	}
494
495	// Prefixes match i bytes and maybe some more bits below.
496	let mut bit_length = (i * 8) as Depth;	2✔
497
498	if i != self.len() && i != k2.len() {	3✔
499	// We got a mismatch somewhere along the way. We need to compute how
500	// many additional bits in i-th byte match.
501	bit_length += (self[i] ^ k2[i]).leading_zeros() as Depth;	1✔
502	}
503
504	// In any case, bit_length should never exceed length of the shorter key.
505	if bit_length > key_bit_len {	3✔
506	bit_length = key_bit_len;	2✔
507	}
508	if bit_length > k2_bit_len {	2✔
509	bit_length = k2_bit_len;	1✔
510	};
511	bit_length	1✔
512	}
513	}
514
515	// Value holds the leaf node value.
516	pub type Value = Vec<u8>;

oasisprotocol / oasis-core / #6806

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous