#4588

Committed 07 Mar 2024 09:50AM UTC coverage: 44.999% (-0.02%) from 45.016%

Build # #4588

Build Type

push

Committed by

Commit Message

Merge pull request #5587 from oasisprotocol/ptrus/stable/23.0.x/go-1.21.8

[stable/23.0.x] go: update to 1.21.8

Run Details

3 of 4 new or added lines in 2 files covered. (75.0%)

41 existing lines in 19 files now uncovered.

2857 of 6349 relevant lines covered (45.0%)

0.96 hits per line

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

64.06

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

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

use crate::{
    common::{crypto::hash::Hash, namespace::Namespace},
    storage::mkvs::{cache::*, 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;
    /// Set a single bit in the given hash and return the result. If bit>self, it resizes new Key.
    fn set_bit(&self, bit: Depth, val: bool) -> Key;
    /// 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 set_bit(&self, bit: Depth, val: bool) -> Key {
        let mut k: Key;
        if bit as usize >= self.len() * 8 {
            k = vec![0; bit as usize / 8 + 1];
            k[0..self.len()].clone_from_slice(self);
        } else {
            k = self.clone();
        }

        let mask = (1 << (7 - (bit % 8))) as u8;
        if val {
            k[(bit / 8) as usize] |= mask;
        } else {
            k[(bit / 8) as usize] &= !mask;
        }
        k
    }

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

oasisprotocol / oasis-core / #4588

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