#6498

Committed 02 Oct 2025 08:45AM UTC coverage: 47.829% (-0.01%) from 47.839%

Build # #6498

Build Type

Committed by

Commit Message

go/oasis-node/cmd/storage: Make compact command experimental

I prefer to release this as experimental first, due to the
known corner case where compacting, then syncing only little
data and finally compacting once more, may at the peak of the
compaction consume 2x of the database disk space.

Pull Request Pull Request #6311: go/oasis-node/cmd/storage: Add command that flattens db instances

Run Details

4582 of 9580 relevant lines covered (47.83%)

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

oasisprotocol / oasis-core / #6498

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