#6593

Committed 29 Oct 2025 08:08AM UTC coverage: 48.411% (-0.01%) from 48.422%

Build # #6593

Build Type

push

Committed by

Commit Message

Merge pull request #6375 from oasisprotocol/ptrus/fix/manager-temporary-path

go/runtime/manager: Fix temporary bundle path

Run Details

4678 of 9663 relevant lines covered (48.41%)

1.07 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 {	1✔
66	match self {	2✔
67	NodeBox::Internal(ref n) => n.is_clean(),	1✔
68	NodeBox::Leaf(ref n) => n.is_clean(),	1✔
69	}
70	}
71
72	fn get_hash(&self) -> Hash {	1✔
73	match self {	1✔
74	NodeBox::Internal(ref n) => n.get_hash(),	1✔
75	NodeBox::Leaf(ref n) => n.get_hash(),	1✔
76	}
77	}
78
79	fn update_hash(&mut self) {	1✔
80	match self {	2✔
81	NodeBox::Internal(ref mut n) => n.update_hash(),	1✔
82	NodeBox::Leaf(ref mut n) => n.update_hash(),	1✔
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 {	3✔
146	hash: node.get_hash(),	1✔
147	node: Some(Rc::new(RefCell::new(node))),	1✔
148	clean: true,
149	..Default::default()	1✔
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 {	1✔
165	match &self.node {	1✔
166	None => panic!("mkvs: get_node called on pointer without a node"),	×
167	Some(node) => node.clone(),	1✔
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>) {	1✔
213	self.cache_extra = new_val;	1✔
214	}
215
216	fn get_cached_size(&self) -> usize {	1✔
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 {	2✔
247	self.clean	1✔
248	}
249
250	fn get_hash(&self) -> Hash {	1✔
251	self.hash	1✔
252	}
253
254	fn update_hash(&mut self) {	1✔
255	let leaf_node_hash = self.leaf_node.borrow().hash;	1✔
256	let left_hash = self.left.borrow().hash;	1✔
257	let right_hash = self.right.borrow().hash;	1✔
258
259	self.hash = Hash::digest_bytes_list(&[	1✔
260	&[NodeKind::Internal as u8],	1✔
261	&self.label_bit_length.marshal_binary().unwrap(),	1✔
262	self.label.as_ref(),	1✔
263	leaf_node_hash.as_ref(),	1✔
264	left_hash.as_ref(),	1✔
265	right_hash.as_ref(),	1✔
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 {	2✔
320	self.clean	1✔
321	}
322
323	fn get_hash(&self) -> Hash {	1✔
324	self.hash	1✔
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 {	1✔
442	let mut key_len_bytes = (key_len as usize) / 8;	1✔
443	if !key_len.is_multiple_of(8) {	2✔
444	key_len_bytes += 1;	2✔
445	}
446
447	let mut new_key: Key = vec![0; (key_len + k2_len).to_bytes()];	2✔
448	new_key[..key_len_bytes].clone_from_slice(&self[..key_len_bytes]);	2✔
449
450	for i in 0..k2.len() {	1✔
451	// First set the right chunk of the previous byte
452	if !key_len.is_multiple_of(8) && key_len_bytes > 0 {	3✔
453	new_key[key_len_bytes + i - 1] \|= k2[i] >> (key_len % 8);	1✔
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() {	3✔
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);	1✔
460	}
461	}
462
463	new_key	1✔
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 {	2✔
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 {	2✔
506	bit_length = key_bit_len;	1✔
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 / #6593

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