reference_trie/
trie_db_0_31_decoder.rs

1// Copyright 2019, 2021 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//! Verbatim compact-proof decoder of the released `trie-db` 0.31.0 (only imports adjusted).
16//!
17//! A frozen snapshot of deployed decoder behavior — **do not update**. It exists so tests and
18//! fuzzers can assert that deduplicated proofs (see `encode_compact_skip_duplicates`) stay
19//! decodable by decoders already in the field. Reconstructs into a hash-keyed database only; the
20//! 0.31.0 decoder inserts attached values under an incomplete prefix in a position-keyed database
21//! (fixed by #227), so prefixed databases are out of scope.
22
23use hash_db::HashDB;
24use std::{convert::TryInto, marker::PhantomData};
25use trie_db::{
26	nibble_ops::NIBBLE_LENGTH,
27	node::{Node, NodeHandle, Value},
28	CError, ChildReference, DBValue, NibbleVec, NodeCodec, TrieError, TrieHash, TrieLayout,
29};
30
31struct DecoderStackEntry<'a, C: NodeCodec> {
32	node: Node<'a>,
33	/// The next entry in the stack is a child of the preceding entry at this index. For branch
34	/// nodes, the index is in [0, NIBBLE_LENGTH] and for extension nodes, the index is in
35	/// [0, 1].
36	child_index: usize,
37	/// The reconstructed child references.
38	children: Vec<Option<ChildReference<C::HashOut>>>,
39	/// A value attached as a node. The node will need to use its hash as value.
40	attached_value: Option<&'a [u8]>,
41	_marker: PhantomData<C>,
42}
43
44impl<'a, C: NodeCodec> DecoderStackEntry<'a, C> {
45	fn advance_child_index(&mut self) -> trie_db::Result<bool, C::HashOut, C::Error> {
46		match self.node {
47			Node::Extension(_, child) if self.child_index == 0 => {
48				match child {
49					NodeHandle::Inline(data) if data.is_empty() => return Ok(false),
50					_ => {
51						let child_ref = child.try_into().map_err(|hash| {
52							Box::new(TrieError::InvalidHash(C::HashOut::default(), hash))
53						})?;
54						self.children[self.child_index] = Some(child_ref);
55					},
56				}
57				self.child_index += 1;
58			},
59			Node::Branch(children, _) | Node::NibbledBranch(_, children, _) => {
60				while self.child_index < NIBBLE_LENGTH {
61					match children[self.child_index] {
62						Some(NodeHandle::Inline(data)) if data.is_empty() => return Ok(false),
63						Some(child) => {
64							let child_ref = child.try_into().map_err(|hash| {
65								Box::new(TrieError::InvalidHash(C::HashOut::default(), hash))
66							})?;
67							self.children[self.child_index] = Some(child_ref);
68						},
69						None => {},
70					}
71					self.child_index += 1;
72				}
73			},
74			_ => {},
75		}
76		Ok(true)
77	}
78
79	fn push_to_prefix(&self, prefix: &mut NibbleVec) {
80		match self.node {
81			Node::Empty => {},
82			Node::Leaf(partial, _) | Node::Extension(partial, _) => {
83				prefix.append_partial(partial.right());
84			},
85			Node::Branch(_, _) => {
86				prefix.push(self.child_index as u8);
87			},
88			Node::NibbledBranch(partial, _, _) => {
89				prefix.append_partial(partial.right());
90				prefix.push(self.child_index as u8);
91			},
92		}
93	}
94
95	fn pop_from_prefix(&self, prefix: &mut NibbleVec) {
96		match self.node {
97			Node::Empty => {},
98			Node::Leaf(partial, _) | Node::Extension(partial, _) => {
99				prefix.drop_lasts(partial.len());
100			},
101			Node::Branch(_, _) => {
102				prefix.pop();
103			},
104			Node::NibbledBranch(partial, _, _) => {
105				prefix.pop();
106				prefix.drop_lasts(partial.len());
107			},
108		}
109	}
110
111	fn encode_node(self, attached_hash: Option<&[u8]>) -> Vec<u8> {
112		let attached_hash = attached_hash.map(|h| Value::Node(h));
113		match self.node {
114			Node::Empty => C::empty_node().to_vec(),
115			Node::Leaf(partial, value) =>
116				C::leaf_node(partial.right_iter(), partial.len(), attached_hash.unwrap_or(value)),
117			Node::Extension(partial, _) => C::extension_node(
118				partial.right_iter(),
119				partial.len(),
120				self.children[0].expect("required by method precondition; qed"),
121			),
122			Node::Branch(_, value) => C::branch_node(
123				self.children.into_iter(),
124				if attached_hash.is_some() { attached_hash } else { value },
125			),
126			Node::NibbledBranch(partial, _, value) => C::branch_node_nibbled(
127				partial.right_iter(),
128				partial.len(),
129				self.children.iter(),
130				if attached_hash.is_some() { attached_hash } else { value },
131			),
132		}
133	}
134}
135
136pub fn decode_compact_from_iter<'a, L, DB, I>(
137	db: &mut DB,
138	encoded: I,
139) -> trie_db::Result<(TrieHash<L>, usize), TrieHash<L>, CError<L>>
140where
141	L: TrieLayout,
142	DB: HashDB<L::Hash, DBValue>,
143	I: IntoIterator<Item = &'a [u8]>,
144{
145	let mut stack: Vec<DecoderStackEntry<L::Codec>> = Vec::new();
146
147	let mut prefix = NibbleVec::new();
148
149	let mut iter = encoded.into_iter().enumerate();
150	while let Some((i, encoded_node)) = iter.next() {
151		let mut attached_node = 0;
152		if let Some(header) = L::Codec::ESCAPE_HEADER {
153			if encoded_node.starts_with(&[header]) {
154				attached_node = 1;
155			}
156		}
157		let node = L::Codec::decode(&encoded_node[attached_node..])
158			.map_err(|err| Box::new(TrieError::DecoderError(<TrieHash<L>>::default(), err)))?;
159
160		let children_len = match node {
161			Node::Empty | Node::Leaf(..) => 0,
162			Node::Extension(..) => 1,
163			Node::Branch(..) | Node::NibbledBranch(..) => NIBBLE_LENGTH,
164		};
165		let mut last_entry = DecoderStackEntry {
166			node,
167			child_index: 0,
168			children: vec![None; children_len],
169			attached_value: None,
170			_marker: PhantomData::default(),
171		};
172
173		if attached_node > 0 {
174			// Read value
175			if let Some((_, fetched_value)) = iter.next() {
176				last_entry.attached_value = Some(fetched_value);
177			} else {
178				return Err(Box::new(TrieError::IncompleteDatabase(<TrieHash<L>>::default())))
179			}
180		}
181
182		loop {
183			if !last_entry.advance_child_index()? {
184				last_entry.push_to_prefix(&mut prefix);
185				stack.push(last_entry);
186				break
187			}
188
189			let hash = last_entry
190				.attached_value
191				.as_ref()
192				.map(|value| db.insert(prefix.as_prefix(), value));
193			let node_data = last_entry.encode_node(hash.as_ref().map(|h| h.as_ref()));
194			let node_hash = db.insert(prefix.as_prefix(), node_data.as_ref());
195
196			if let Some(entry) = stack.pop() {
197				last_entry = entry;
198				last_entry.pop_from_prefix(&mut prefix);
199				last_entry.children[last_entry.child_index] = Some(ChildReference::Hash(node_hash));
200				last_entry.child_index += 1;
201			} else {
202				return Ok((node_hash, i + 1))
203			}
204		}
205	}
206
207	Err(Box::new(TrieError::IncompleteDatabase(<TrieHash<L>>::default())))
208}
reference_trie/trie_db_0_31_decoder.rs

reference_trie/
trie_db_0_31_decoder.rs
