trie_db/
node_codec.rs

1// Copyright 2017, 2018 Parity Technologies
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Generic trait for trie node encoding/decoding. Takes a `hash_db::Hasher`
16//! to parametrize the hashes used in the codec.
17
18use crate::{
19	node::{Node, NodePlan, Value},
20	ChildReference, MaybeDebug,
21};
22
23use crate::rstd::{borrow::Borrow, hash, vec::Vec, Error};
24
25/// Representation of a nible slice (right aligned).
26/// It contains a right aligned padded first byte (first pair element is the number of nibbles
27/// (0 to max nb nibble - 1), second pair element is the padded nibble), and a slice over
28/// the remaining bytes.
29pub type Partial<'a> = ((u8, u8), &'a [u8]);
30
31/// Trait for trie node encoding/decoding.
32/// Uses a type parameter to allow registering
33/// positions without colling decode plan.
34pub trait NodeCodec: Sized {
35	/// Escape header byte sequence to indicate next node is a
36	/// branch or leaf with hash of value, followed by the value node.
37	const ESCAPE_HEADER: Option<u8> = None;
38
39	/// Codec error type.
40	type Error: Error;
41
42	/// Output type of encoded node hasher.
43	type HashOut: AsRef<[u8]>
44		+ AsMut<[u8]>
45		+ Default
46		+ MaybeDebug
47		+ PartialEq
48		+ Eq
49		+ hash::Hash
50		+ Send
51		+ Sync
52		+ Clone
53		+ Copy;
54
55	/// Get the hashed null node.
56	fn hashed_null_node() -> Self::HashOut;
57
58	/// Decode bytes to a `NodePlan`. Returns `Self::E` on failure.
59	fn decode_plan(data: &[u8]) -> Result<NodePlan, Self::Error>;
60
61	/// Decode bytes to a `Node`. Returns `Self::E` on failure.
62	fn decode<'a>(data: &'a [u8]) -> Result<Node<'a>, Self::Error> {
63		Ok(Self::decode_plan(data)?.build(data))
64	}
65
66	/// Check if the provided bytes correspond to the codecs "empty" node.
67	fn is_empty_node(data: &[u8]) -> bool;
68
69	/// Returns an encoded empty node.
70	fn empty_node() -> &'static [u8];
71
72	/// Returns an encoded leaf node
73	///
74	/// Note that number_nibble is the number of element of the iterator
75	/// it can possibly be obtain by `Iterator` `size_hint`, but
76	/// for simplicity it is used directly as a parameter.
77	fn leaf_node(partial: impl Iterator<Item = u8>, number_nibble: usize, value: Value) -> Vec<u8>;
78
79	/// Returns an encoded extension node
80	///
81	/// Note that number_nibble is the number of element of the iterator
82	/// it can possibly be obtain by `Iterator` `size_hint`, but
83	/// for simplicity it is used directly as a parameter.
84	fn extension_node(
85		partial: impl Iterator<Item = u8>,
86		number_nibble: usize,
87		child_ref: ChildReference<Self::HashOut>,
88	) -> Vec<u8>;
89
90	/// Returns an encoded branch node.
91	/// Takes an iterator yielding `ChildReference<Self::HashOut>` and an optional value.
92	fn branch_node(
93		children: impl Iterator<Item = impl Borrow<Option<ChildReference<Self::HashOut>>>>,
94		value: Option<Value>,
95	) -> Vec<u8>;
96
97	/// Returns an encoded branch node with a possible partial path.
98	/// `number_nibble` is the partial path length as in `extension_node`.
99	fn branch_node_nibbled(
100		partial: impl Iterator<Item = u8>,
101		number_nibble: usize,
102		children: impl Iterator<Item = impl Borrow<Option<ChildReference<Self::HashOut>>>>,
103		value: Option<Value>,
104	) -> Vec<u8>;
105}
trie_db/node_codec.rs

trie_db/
node_codec.rs
