#6052

Committed 20 May 2025 12:50PM UTC coverage: 47.655% (-0.03%) from 47.681%

Build # #6052

Build Type

Committed by

Commit Message

go/runtime: Add log manager

Pull Request Pull Request #6197: go/runtime: Add log manager

Run Details

0 of 3 new or added lines in 2 files covered. (0.0%)

1 existing line in 1 file now uncovered.

4563 of 9575 relevant lines covered (47.66%)

1.12 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 {	2✔
65	match self {	2✔
66	NodeBox::Internal(ref n) => n.is_clean(),	2✔
67	NodeBox::Leaf(ref n) => n.is_clean(),	3✔
68	}
69	}
70
71	fn get_hash(&self) -> Hash {	2✔
72	match self {	2✔
73	NodeBox::Internal(ref n) => n.get_hash(),	2✔
74	NodeBox::Leaf(ref n) => n.get_hash(),	3✔
75	}
76	}
77
78	fn update_hash(&mut self) {	3✔
79	match self {	3✔
80	NodeBox::Internal(ref mut n) => n.update_hash(),	3✔
81	NodeBox::Leaf(ref mut n) => n.update_hash(),	3✔
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 {	2✔
134	Rc::new(RefCell::new(NodePointer {	4✔
135	node: None,	2✔
136	clean: true,
137	hash,
138	..Default::default()	2✔
139	}))
140	}
141
142	/// Construct a node pointer from a full node.
143	pub fn from_node(node: NodeBox) -> NodePtrRef {	2✔
144	Rc::new(RefCell::new(NodePointer {	6✔
145	hash: node.get_hash(),	2✔
146	node: Some(Rc::new(RefCell::new(node))),	2✔
147	clean: true,
148	..Default::default()	2✔
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 {	2✔
164	match &self.node {	2✔
165	None => panic!("mkvs: get_node called on pointer without a node"),	×
166	Some(node) => node.clone(),	2✔
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>) {	3✔
211	self.cache_extra = new_val;	3✔
212	}
213
214	fn get_cached_size(&self) -> usize {	3✔
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	2✔
246	}
247
248	fn get_hash(&self) -> Hash {	2✔
249	self.hash	2✔
250	}
251
252	fn update_hash(&mut self) {	2✔
253	let leaf_node_hash = self.leaf_node.borrow().hash;	2✔
254	let left_hash = self.left.borrow().hash;	2✔
255	let right_hash = self.right.borrow().hash;	2✔
256
257	self.hash = Hash::digest_bytes_list(&[	2✔
258	&[NodeKind::Internal as u8],	2✔
259	&self.label_bit_length.marshal_binary().unwrap(),	2✔
260	self.label.as_ref(),	2✔
261	leaf_node_hash.as_ref(),	2✔
262	left_hash.as_ref(),	2✔
263	right_hash.as_ref(),	2✔
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 {	3✔
318	self.clean	3✔
319	}
320
321	fn get_hash(&self) -> Hash {	3✔
322	self.hash	3✔
323	}
324
325	fn update_hash(&mut self) {	3✔
326	self.hash = Hash::digest_bytes_list(&[	3✔
327	&[NodeKind::Leaf as u8],	3✔
328	&(self.key.len() as u32).marshal_binary().unwrap(),	3✔
329	self.key.as_ref(),	3✔
330	&(self.value.len() as u32).marshal_binary().unwrap(),	3✔
331	self.value.as_ref(),	3✔
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✔
UNCOV 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 {	3✔
487	if self[i] != k2[i] {	1✔
488	break;
489	}
490	i += 1;	2✔
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 / #6052

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