tetsy_trie_db/
lookup.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//! Trie lookup via HashDB.
16
17use tetsy_hash_db::HashDBRef;
18use crate::nibble::NibbleSlice;
19use crate::node::{Node, NodeHandle, decode_hash};
20use crate::node_codec::NodeCodec;
21use crate::rstd::boxed::Box;
22use super::{DBValue, Result, TrieError, Query, TrieLayout, CError, TrieHash};
23
24/// Trie lookup helper object.
25pub struct Lookup<'a, L: TrieLayout, Q: Query<L::Hash>> {
26	/// database to query from.
27	pub db: &'a dyn HashDBRef<L::Hash, DBValue>,
28	/// Query object to record nodes and transform data.
29	pub query: Q,
30	/// Hash to start at
31	pub hash: TrieHash<L>,
32}
33
34impl<'a, L, Q> Lookup<'a, L, Q>
35where
36	L: TrieLayout,
37	Q: Query<L::Hash>,
38{
39	/// Look up the given key. If the value is found, it will be passed to the given
40	/// function to decode or copy.
41	pub fn look_up(
42		mut self,
43		key: NibbleSlice,
44	) -> Result<Option<Q::Item>, TrieHash<L>, CError<L>> {
45		let mut partial = key;
46		let mut hash = self.hash;
47		let mut key_nibbles = 0;
48
49		// this loop iterates through non-inline nodes.
50		for depth in 0.. {
51			let node_data = match self.db.get(&hash, key.mid(key_nibbles).left()) {
52				Some(value) => value,
53				None => return Err(Box::new(match depth {
54					0 => TrieError::InvalidStateRoot(hash),
55					_ => TrieError::IncompleteDatabase(hash),
56				})),
57			};
58
59			self.query.record(&hash, &node_data, depth);
60
61			// this loop iterates through all inline children (usually max 1)
62			// without incrementing the depth.
63			let mut node_data = &node_data[..];
64			loop {
65				let decoded = match L::Codec::decode(node_data) {
66					Ok(node) => node,
67					Err(e) => {
68						return Err(Box::new(TrieError::DecoderError(hash, e)))
69					}
70				};
71				let next_node = match decoded {
72					Node::Leaf(slice, value) => {
73						return Ok(match slice == partial {
74							true => Some(self.query.decode(value)),
75							false => None,
76						})
77					}
78					Node::Extension(slice, item) => {
79						if partial.starts_with(&slice) {
80							partial = partial.mid(slice.len());
81							key_nibbles += slice.len();
82							item
83						} else {
84							return Ok(None)
85						}
86					}
87					Node::Branch(children, value) => match partial.is_empty() {
88						true => return Ok(value.map(move |val| self.query.decode(val))),
89						false => match children[partial.at(0) as usize] {
90							Some(x) => {
91								partial = partial.mid(1);
92								key_nibbles += 1;
93								x
94							}
95							None => return Ok(None)
96						}
97					},
98					Node::NibbledBranch(slice, children, value) => {
99						if !partial.starts_with(&slice) {
100							return Ok(None)
101						}
102
103						match partial.len() == slice.len() {
104							true => return Ok(value.map(move |val| self.query.decode(val))),
105							false => match children[partial.at(slice.len()) as usize] {
106								Some(x) => {
107									partial = partial.mid(slice.len() + 1);
108									key_nibbles += slice.len() + 1;
109									x
110								}
111								None => return Ok(None)
112							}
113						}
114					},
115					Node::Empty => return Ok(None),
116				};
117
118				// check if new node data is inline or hash.
119				match next_node {
120					NodeHandle::Hash(data) => {
121						hash = decode_hash::<L::Hash>(data)
122							.ok_or_else(|| Box::new(TrieError::InvalidHash(hash, data.to_vec())))?;
123						break;
124					},
125					NodeHandle::Inline(data) => {
126						node_data = data;
127					},
128				}
129			}
130		}
131		Ok(None)
132	}
133}
tetsy_trie_db/lookup.rs

tetsy_trie_db/
lookup.rs
