referrerpolicy=no-referrer-when-downgrade

sp_state_machine/
trie_backend_essence.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! Trie-based state machine backend essence used to read values
19//! from storage.
20
21use crate::{
22	backend::{IterArgs, StorageIterator},
23	trie_backend::TrieCacheProvider,
24	warn, StorageKey, StorageValue,
25};
26#[cfg(feature = "std")]
27use alloc::sync::Arc;
28use alloc::{boxed::Box, vec::Vec};
29use codec::Codec;
30use core::marker::PhantomData;
31use hash_db::{self, AsHashDB, HashDB, HashDBRef, Hasher, Prefix};
32#[cfg(feature = "std")]
33use parking_lot::RwLock;
34use sp_core::storage::{ChildInfo, ChildType, StateVersion};
35use sp_trie::{
36	child_delta_trie_root, delta_trie_root, empty_child_trie_root,
37	read_child_trie_first_descendant_value, read_child_trie_hash, read_child_trie_value,
38	read_trie_first_descendant_value, read_trie_value,
39	trie_types::{TrieDBBuilder, TrieError},
40	DBValue, KeySpacedDB, MerkleValue, NodeCodec, PrefixedMemoryDB, RandomState, Trie, TrieCache,
41	TrieDBRawIterator, TrieRecorder, TrieRecorderProvider,
42};
43#[cfg(feature = "std")]
44use std::collections::HashMap;
45// In this module, we only use layout for read operation and empty root,
46// where V1 and V0 are equivalent.
47use sp_trie::LayoutV1 as Layout;
48
49#[cfg(not(feature = "std"))]
50macro_rules! format {
51	( $message:expr, $( $arg:expr )* ) => {
52		{
53			$( let _ = &$arg; )*
54			crate::DefaultError
55		}
56	};
57}
58
59type Result<V> = core::result::Result<V, crate::DefaultError>;
60
61/// Patricia trie-based storage trait.
62pub trait Storage<H: Hasher>: Send + Sync {
63	/// Get a trie node.
64	fn get(&self, key: &H::Out, prefix: Prefix) -> Result<Option<DBValue>>;
65}
66
67/// Local cache for child root.
68#[cfg(feature = "std")]
69pub(crate) struct Cache<H> {
70	pub child_root: HashMap<Vec<u8>, Option<H>>,
71}
72
73#[cfg(feature = "std")]
74impl<H> Cache<H> {
75	fn new() -> Self {
76		Cache { child_root: HashMap::new() }
77	}
78}
79
80enum IterState {
81	Pending,
82	FinishedComplete,
83	FinishedIncomplete,
84}
85
86/// A raw iterator over the storage.
87pub struct RawIter<S, H, C, R>
88where
89	H: Hasher,
90{
91	stop_on_incomplete_database: bool,
92	skip_if_first: Option<StorageKey>,
93	root: H::Out,
94	child_info: Option<ChildInfo>,
95	trie_iter: TrieDBRawIterator<Layout<H>>,
96	state: IterState,
97	_phantom: PhantomData<(S, C, R)>,
98}
99
100impl<S, H, C, R> RawIter<S, H, C, R>
101where
102	H: Hasher,
103	S: TrieBackendStorage<H>,
104	H::Out: Codec + Ord,
105	C: TrieCacheProvider<H> + Send + Sync,
106	R: TrieRecorderProvider<H> + Send + Sync,
107{
108	#[inline]
109	fn prepare<RE>(
110		&mut self,
111		backend: &TrieBackendEssence<S, H, C, R>,
112		callback: impl FnOnce(
113			&sp_trie::TrieDB<Layout<H>>,
114			&mut TrieDBRawIterator<Layout<H>>,
115		) -> Option<core::result::Result<RE, Box<TrieError<<H as Hasher>::Out>>>>,
116	) -> Option<Result<RE>> {
117		if !matches!(self.state, IterState::Pending) {
118			return None
119		}
120
121		let result = backend.with_trie_db(self.root, self.child_info.as_ref(), |db| {
122			callback(&db, &mut self.trie_iter)
123		});
124		match result {
125			Some(Ok(key_value)) => Some(Ok(key_value)),
126			None => {
127				self.state = IterState::FinishedComplete;
128				None
129			},
130			Some(Err(error)) => {
131				self.state = IterState::FinishedIncomplete;
132				if matches!(*error, TrieError::IncompleteDatabase(_)) &&
133					self.stop_on_incomplete_database
134				{
135					None
136				} else {
137					Some(Err(format!("TrieDB iteration error: {}", error)))
138				}
139			},
140		}
141	}
142}
143
144impl<S, H, C, R> Default for RawIter<S, H, C, R>
145where
146	H: Hasher,
147{
148	fn default() -> Self {
149		Self {
150			stop_on_incomplete_database: false,
151			skip_if_first: None,
152			child_info: None,
153			root: Default::default(),
154			trie_iter: TrieDBRawIterator::empty(),
155			state: IterState::FinishedComplete,
156			_phantom: Default::default(),
157		}
158	}
159}
160
161impl<S, H, C, R> StorageIterator<H> for RawIter<S, H, C, R>
162where
163	H: Hasher,
164	S: TrieBackendStorage<H>,
165	H::Out: Codec + Ord,
166	C: TrieCacheProvider<H> + Send + Sync,
167	R: TrieRecorderProvider<H> + Send + Sync,
168{
169	type Backend = crate::TrieBackend<S, H, C, R>;
170	type Error = crate::DefaultError;
171
172	#[inline]
173	fn next_key(&mut self, backend: &Self::Backend) -> Option<Result<StorageKey>> {
174		let skip_if_first = self.skip_if_first.take();
175		self.prepare(&backend.essence, |trie, trie_iter| {
176			let mut result = trie_iter.next_key(&trie);
177			if let Some(skipped_key) = skip_if_first {
178				if let Some(Ok(ref key)) = result {
179					if *key == skipped_key {
180						result = trie_iter.next_key(&trie);
181					}
182				}
183			}
184			result
185		})
186	}
187
188	#[inline]
189	fn next_pair(&mut self, backend: &Self::Backend) -> Option<Result<(StorageKey, StorageValue)>> {
190		let skip_if_first = self.skip_if_first.take();
191		self.prepare(&backend.essence, |trie, trie_iter| {
192			let mut result = trie_iter.next_item(&trie);
193			if let Some(skipped_key) = skip_if_first {
194				if let Some(Ok((ref key, _))) = result {
195					if *key == skipped_key {
196						result = trie_iter.next_item(&trie);
197					}
198				}
199			}
200			result
201		})
202	}
203
204	fn was_complete(&self) -> bool {
205		matches!(self.state, IterState::FinishedComplete)
206	}
207}
208
209/// Patricia trie-based pairs storage essence.
210pub struct TrieBackendEssence<S: TrieBackendStorage<H>, H: Hasher, C, R> {
211	storage: S,
212	root: H::Out,
213	empty: H::Out,
214	#[cfg(feature = "std")]
215	pub(crate) cache: Arc<RwLock<Cache<H::Out>>>,
216	pub(crate) trie_node_cache: Option<C>,
217	pub(crate) recorder: Option<R>,
218}
219
220impl<S: TrieBackendStorage<H>, H: Hasher, C, R> TrieBackendEssence<S, H, C, R> {
221	/// Create new trie-based backend.
222	pub fn new(storage: S, root: H::Out) -> Self {
223		Self::new_with_cache(storage, root, None)
224	}
225
226	/// Create new trie-based backend.
227	pub fn new_with_cache(storage: S, root: H::Out, cache: Option<C>) -> Self {
228		TrieBackendEssence {
229			storage,
230			root,
231			empty: H::hash(&[0u8]),
232			#[cfg(feature = "std")]
233			cache: Arc::new(RwLock::new(Cache::new())),
234			trie_node_cache: cache,
235			recorder: None,
236		}
237	}
238
239	/// Create new trie-based backend.
240	pub fn new_with_cache_and_recorder(
241		storage: S,
242		root: H::Out,
243		cache: Option<C>,
244		recorder: Option<R>,
245	) -> Self {
246		TrieBackendEssence {
247			storage,
248			root,
249			empty: H::hash(&[0u8]),
250			#[cfg(feature = "std")]
251			cache: Arc::new(RwLock::new(Cache::new())),
252			trie_node_cache: cache,
253			recorder,
254		}
255	}
256
257	/// Get backend storage reference.
258	pub fn backend_storage(&self) -> &S {
259		&self.storage
260	}
261
262	/// Get backend storage mutable reference.
263	pub fn backend_storage_mut(&mut self) -> &mut S {
264		&mut self.storage
265	}
266
267	/// Get trie root.
268	pub fn root(&self) -> &H::Out {
269		&self.root
270	}
271
272	/// Set trie root. This is useful for testing.
273	pub fn set_root(&mut self, root: H::Out) {
274		// If root did change so can have cached content.
275		self.reset_cache();
276		self.root = root;
277	}
278
279	#[cfg(feature = "std")]
280	fn reset_cache(&mut self) {
281		self.cache = Arc::new(RwLock::new(Cache::new()));
282	}
283
284	#[cfg(not(feature = "std"))]
285	fn reset_cache(&mut self) {}
286
287	/// Consumes self and returns underlying storage.
288	pub fn into_storage(self) -> S {
289		self.storage
290	}
291}
292
293impl<S: TrieBackendStorage<H>, H: Hasher, C: TrieCacheProvider<H>, R: TrieRecorderProvider<H>>
294	TrieBackendEssence<S, H, C, R>
295{
296	/// Call the given closure passing it the recorder and the cache.
297	///
298	/// If the given `storage_root` is `None`, `self.root` will be used.
299	#[inline]
300	fn with_recorder_and_cache<RE>(
301		&self,
302		storage_root: Option<H::Out>,
303		callback: impl FnOnce(
304			Option<&mut dyn TrieRecorder<H::Out>>,
305			Option<&mut dyn TrieCache<NodeCodec<H>>>,
306		) -> RE,
307	) -> RE {
308		let storage_root = storage_root.unwrap_or_else(|| self.root);
309		let mut cache = self.trie_node_cache.as_ref().map(|c| c.as_trie_db_cache(storage_root));
310		let cache = cache.as_mut().map(|c| c as _);
311
312		let mut recorder = self.recorder.as_ref().map(|r| r.as_trie_recorder(storage_root));
313		let recorder = match recorder.as_mut() {
314			Some(recorder) => Some(recorder as &mut dyn TrieRecorder<H::Out>),
315			None => None,
316		};
317		callback(recorder, cache)
318	}
319
320	/// Call the given closure passing it the recorder and the cache.
321	///
322	/// This function must only be used when the operation in `callback` is
323	/// calculating a `storage_root`. It is expected that `callback` returns
324	/// the new storage root. This is required to register the changes in the cache
325	/// for the correct storage root. The given `storage_root` corresponds to the root of the "old"
326	/// trie. If the value is not given, `self.root` is used.
327	fn with_recorder_and_cache_for_storage_root<RE>(
328		&self,
329		storage_root: Option<H::Out>,
330		callback: impl FnOnce(
331			Option<&mut dyn TrieRecorder<H::Out>>,
332			Option<&mut dyn TrieCache<NodeCodec<H>>>,
333		) -> (Option<H::Out>, RE),
334	) -> RE {
335		let storage_root = storage_root.unwrap_or_else(|| self.root);
336		let mut recorder = self.recorder.as_ref().map(|r| r.as_trie_recorder(storage_root));
337		let recorder = match recorder.as_mut() {
338			Some(recorder) => Some(recorder as &mut dyn TrieRecorder<H::Out>),
339			None => None,
340		};
341
342		let result = if let Some(local_cache) = self.trie_node_cache.as_ref() {
343			let mut cache = local_cache.as_trie_db_mut_cache();
344
345			let (new_root, r) = callback(recorder, Some(&mut cache));
346
347			if let Some(new_root) = new_root {
348				local_cache.merge(cache, new_root);
349			}
350
351			r
352		} else {
353			callback(recorder, None).1
354		};
355
356		result
357	}
358}
359
360impl<
361		S: TrieBackendStorage<H>,
362		H: Hasher,
363		C: TrieCacheProvider<H> + Send + Sync,
364		R: TrieRecorderProvider<H> + Send + Sync,
365	> TrieBackendEssence<S, H, C, R>
366where
367	H::Out: Codec + Ord,
368{
369	/// Calls the given closure with a [`TrieDb`] constructed for the given
370	/// storage root and (optionally) child trie.
371	#[inline]
372	fn with_trie_db<RE>(
373		&self,
374		root: H::Out,
375		child_info: Option<&ChildInfo>,
376		callback: impl FnOnce(&sp_trie::TrieDB<Layout<H>>) -> RE,
377	) -> RE {
378		let backend = self as &dyn HashDBRef<H, Vec<u8>>;
379		let db = child_info
380			.as_ref()
381			.map(|child_info| KeySpacedDB::new(backend, child_info.keyspace()));
382		let db = db.as_ref().map(|db| db as &dyn HashDBRef<H, Vec<u8>>).unwrap_or(backend);
383
384		self.with_recorder_and_cache(Some(root), |recorder, cache| {
385			let trie = TrieDBBuilder::<H>::new(db, &root)
386				.with_optional_recorder(recorder)
387				.with_optional_cache(cache)
388				.build();
389
390			callback(&trie)
391		})
392	}
393
394	/// Returns the next key in the trie i.e. the minimum key that is strictly superior to `key` in
395	/// lexicographic order.
396	///
397	/// Will always traverse the trie from scratch in search of the key, which is slow.
398	/// Used only when debug assertions are enabled to crosscheck the results of finding
399	/// the next key through an iterator.
400	#[cfg(debug_assertions)]
401	pub fn next_storage_key_slow(&self, key: &[u8]) -> Result<Option<StorageKey>> {
402		self.next_storage_key_from_root(&self.root, None, key)
403	}
404
405	/// Access the root of the child storage in its parent trie
406	fn child_root(&self, child_info: &ChildInfo) -> Result<Option<H::Out>> {
407		#[cfg(feature = "std")]
408		{
409			if let Some(result) = self.cache.read().child_root.get(child_info.storage_key()) {
410				return Ok(*result)
411			}
412		}
413
414		let result = self.storage(child_info.prefixed_storage_key().as_slice())?.map(|r| {
415			let mut hash = H::Out::default();
416
417			// root is fetched from DB, not writable by runtime, so it's always valid.
418			hash.as_mut().copy_from_slice(&r[..]);
419
420			hash
421		});
422
423		#[cfg(feature = "std")]
424		{
425			self.cache.write().child_root.insert(child_info.storage_key().to_vec(), result);
426		}
427
428		Ok(result)
429	}
430
431	/// Return the next key in the child trie i.e. the minimum key that is strictly superior to
432	/// `key` in lexicographic order.
433	pub fn next_child_storage_key(
434		&self,
435		child_info: &ChildInfo,
436		key: &[u8],
437	) -> Result<Option<StorageKey>> {
438		let child_root = match self.child_root(child_info)? {
439			Some(child_root) => child_root,
440			None => return Ok(None),
441		};
442
443		self.next_storage_key_from_root(&child_root, Some(child_info), key)
444	}
445
446	/// Return next key from main trie or child trie by providing corresponding root.
447	fn next_storage_key_from_root(
448		&self,
449		root: &H::Out,
450		child_info: Option<&ChildInfo>,
451		key: &[u8],
452	) -> Result<Option<StorageKey>> {
453		self.with_trie_db(*root, child_info, |trie| {
454			let mut iter = trie.key_iter().map_err(|e| format!("TrieDB iteration error: {}", e))?;
455
456			// The key just after the one given in input, basically `key++0`.
457			// Note: We are sure this is the next key if:
458			// * size of key has no limit (i.e. we can always add 0 to the path),
459			// * and no keys can be inserted between `key` and `key++0` (this is ensured by sp-io).
460			let mut potential_next_key = Vec::with_capacity(key.len() + 1);
461			potential_next_key.extend_from_slice(key);
462			potential_next_key.push(0);
463
464			iter.seek(&potential_next_key)
465				.map_err(|e| format!("TrieDB iterator seek error: {}", e))?;
466
467			let next_element = iter.next();
468
469			let next_key = if let Some(next_element) = next_element {
470				let next_key =
471					next_element.map_err(|e| format!("TrieDB iterator next error: {}", e))?;
472				Some(next_key)
473			} else {
474				None
475			};
476
477			Ok(next_key)
478		})
479	}
480
481	/// Returns the hash value
482	pub fn storage_hash(&self, key: &[u8]) -> Result<Option<H::Out>> {
483		let map_e = |e| format!("Trie lookup error: {}", e);
484
485		self.with_recorder_and_cache(None, |recorder, cache| {
486			TrieDBBuilder::new(self, &self.root)
487				.with_optional_cache(cache)
488				.with_optional_recorder(recorder)
489				.build()
490				.get_hash(key)
491				.map_err(map_e)
492		})
493	}
494
495	/// Get the value of storage at given key.
496	pub fn storage(&self, key: &[u8]) -> Result<Option<StorageValue>> {
497		let map_e = |e| format!("Trie lookup error: {}", e);
498
499		self.with_recorder_and_cache(None, |recorder, cache| {
500			read_trie_value::<Layout<H>, _>(self, &self.root, key, recorder, cache).map_err(map_e)
501		})
502	}
503
504	/// Returns the hash value
505	pub fn child_storage_hash(&self, child_info: &ChildInfo, key: &[u8]) -> Result<Option<H::Out>> {
506		let child_root = match self.child_root(child_info)? {
507			Some(root) => root,
508			None => return Ok(None),
509		};
510
511		let map_e = |e| format!("Trie lookup error: {}", e);
512
513		self.with_recorder_and_cache(Some(child_root), |recorder, cache| {
514			read_child_trie_hash::<Layout<H>, _>(
515				child_info.keyspace(),
516				self,
517				&child_root,
518				key,
519				recorder,
520				cache,
521			)
522			.map_err(map_e)
523		})
524	}
525
526	/// Get the value of child storage at given key.
527	pub fn child_storage(
528		&self,
529		child_info: &ChildInfo,
530		key: &[u8],
531	) -> Result<Option<StorageValue>> {
532		let child_root = match self.child_root(child_info)? {
533			Some(root) => root,
534			None => return Ok(None),
535		};
536
537		let map_e = |e| format!("Trie lookup error: {}", e);
538
539		self.with_recorder_and_cache(Some(child_root), |recorder, cache| {
540			read_child_trie_value::<Layout<H>, _>(
541				child_info.keyspace(),
542				self,
543				&child_root,
544				key,
545				recorder,
546				cache,
547			)
548			.map_err(map_e)
549		})
550	}
551
552	/// Get the closest merkle value at given key.
553	pub fn closest_merkle_value(&self, key: &[u8]) -> Result<Option<MerkleValue<H::Out>>> {
554		let map_e = |e| format!("Trie lookup error: {}", e);
555
556		self.with_recorder_and_cache(None, |recorder, cache| {
557			read_trie_first_descendant_value::<Layout<H>, _>(self, &self.root, key, recorder, cache)
558				.map_err(map_e)
559		})
560	}
561
562	/// Get the child closest merkle value at given key.
563	pub fn child_closest_merkle_value(
564		&self,
565		child_info: &ChildInfo,
566		key: &[u8],
567	) -> Result<Option<MerkleValue<H::Out>>> {
568		let Some(child_root) = self.child_root(child_info)? else { return Ok(None) };
569
570		let map_e = |e| format!("Trie lookup error: {}", e);
571
572		self.with_recorder_and_cache(Some(child_root), |recorder, cache| {
573			read_child_trie_first_descendant_value::<Layout<H>, _>(
574				child_info.keyspace(),
575				self,
576				&child_root,
577				key,
578				recorder,
579				cache,
580			)
581			.map_err(map_e)
582		})
583	}
584
585	/// Create a raw iterator over the storage.
586	pub fn raw_iter(&self, args: IterArgs) -> Result<RawIter<S, H, C, R>> {
587		let root = if let Some(child_info) = args.child_info.as_ref() {
588			let root = match self.child_root(&child_info)? {
589				Some(root) => root,
590				None => return Ok(Default::default()),
591			};
592			root
593		} else {
594			self.root
595		};
596
597		if self.root == Default::default() {
598			// A special-case for an empty storage root.
599			return Ok(Default::default())
600		}
601
602		let trie_iter = self
603			.with_trie_db(root, args.child_info.as_ref(), |db| {
604				let prefix = args.prefix.as_deref().unwrap_or(&[]);
605				if let Some(start_at) = args.start_at {
606					TrieDBRawIterator::new_prefixed_then_seek(db, prefix, &start_at)
607				} else {
608					TrieDBRawIterator::new_prefixed(db, prefix)
609				}
610			})
611			.map_err(|e| format!("TrieDB iteration error: {}", e))?;
612
613		Ok(RawIter {
614			stop_on_incomplete_database: args.stop_on_incomplete_database,
615			skip_if_first: if args.start_at_exclusive {
616				args.start_at.map(|key| key.to_vec())
617			} else {
618				None
619			},
620			child_info: args.child_info,
621			root,
622			trie_iter,
623			state: IterState::Pending,
624			_phantom: Default::default(),
625		})
626	}
627
628	/// Return the storage root after applying the given `delta`.
629	pub fn storage_root<'a>(
630		&self,
631		delta: impl Iterator<Item = (&'a [u8], Option<&'a [u8]>)>,
632		state_version: StateVersion,
633	) -> (H::Out, PrefixedMemoryDB<H>) {
634		let mut write_overlay = PrefixedMemoryDB::with_hasher(RandomState::default());
635
636		let root = self.with_recorder_and_cache_for_storage_root(None, |recorder, cache| {
637			let mut eph = Ephemeral::new(self.backend_storage(), &mut write_overlay);
638			let res = match state_version {
639				StateVersion::V0 => delta_trie_root::<sp_trie::LayoutV0<H>, _, _, _, _, _>(
640					&mut eph, self.root, delta, recorder, cache,
641				),
642				StateVersion::V1 => delta_trie_root::<sp_trie::LayoutV1<H>, _, _, _, _, _>(
643					&mut eph, self.root, delta, recorder, cache,
644				),
645			};
646
647			match res {
648				Ok(ret) => (Some(ret), ret),
649				Err(e) => {
650					warn!(target: "trie", "Failed to write to trie: {}", e);
651					(None, self.root)
652				},
653			}
654		});
655
656		(root, write_overlay)
657	}
658
659	/// Returns the child storage root for the child trie `child_info` after applying the given
660	/// `delta`.
661	pub fn child_storage_root<'a>(
662		&self,
663		child_info: &ChildInfo,
664		delta: impl Iterator<Item = (&'a [u8], Option<&'a [u8]>)>,
665		state_version: StateVersion,
666	) -> (H::Out, bool, PrefixedMemoryDB<H>) {
667		let default_root = match child_info.child_type() {
668			ChildType::ParentKeyId => empty_child_trie_root::<sp_trie::LayoutV1<H>>(),
669		};
670		let mut write_overlay = PrefixedMemoryDB::with_hasher(RandomState::default());
671		let child_root = match self.child_root(child_info) {
672			Ok(Some(hash)) => hash,
673			Ok(None) => default_root,
674			Err(e) => {
675				warn!(target: "trie", "Failed to read child storage root: {}", e);
676				default_root
677			},
678		};
679
680		let new_child_root =
681			self.with_recorder_and_cache_for_storage_root(Some(child_root), |recorder, cache| {
682				let mut eph = Ephemeral::new(self.backend_storage(), &mut write_overlay);
683				match match state_version {
684					StateVersion::V0 =>
685						child_delta_trie_root::<sp_trie::LayoutV0<H>, _, _, _, _, _, _>(
686							child_info.keyspace(),
687							&mut eph,
688							child_root,
689							delta,
690							recorder,
691							cache,
692						),
693					StateVersion::V1 =>
694						child_delta_trie_root::<sp_trie::LayoutV1<H>, _, _, _, _, _, _>(
695							child_info.keyspace(),
696							&mut eph,
697							child_root,
698							delta,
699							recorder,
700							cache,
701						),
702				} {
703					Ok(ret) => (Some(ret), ret),
704					Err(e) => {
705						warn!(target: "trie", "Failed to write to trie: {}", e);
706						(None, child_root)
707					},
708				}
709			});
710
711		let is_default = new_child_root == default_root;
712
713		(new_child_root, is_default, write_overlay)
714	}
715}
716
717pub(crate) struct Ephemeral<'a, S: 'a + TrieBackendStorage<H>, H: 'a + Hasher> {
718	storage: &'a S,
719	overlay: &'a mut PrefixedMemoryDB<H>,
720}
721
722impl<'a, S: 'a + TrieBackendStorage<H>, H: 'a + Hasher> AsHashDB<H, DBValue>
723	for Ephemeral<'a, S, H>
724{
725	fn as_hash_db<'b>(&'b self) -> &'b (dyn HashDB<H, DBValue> + 'b) {
726		self
727	}
728	fn as_hash_db_mut<'b>(&'b mut self) -> &'b mut (dyn HashDB<H, DBValue> + 'b) {
729		self
730	}
731}
732
733impl<'a, S: TrieBackendStorage<H>, H: Hasher> Ephemeral<'a, S, H> {
734	pub fn new(storage: &'a S, overlay: &'a mut PrefixedMemoryDB<H>) -> Self {
735		Ephemeral { storage, overlay }
736	}
737}
738
739impl<'a, S: 'a + TrieBackendStorage<H>, H: Hasher> hash_db::HashDB<H, DBValue>
740	for Ephemeral<'a, S, H>
741{
742	fn get(&self, key: &H::Out, prefix: Prefix) -> Option<DBValue> {
743		HashDB::get(self.overlay, key, prefix).or_else(|| {
744			self.storage.get(key, prefix).unwrap_or_else(|e| {
745				warn!(target: "trie", "Failed to read from DB: {}", e);
746				None
747			})
748		})
749	}
750
751	fn contains(&self, key: &H::Out, prefix: Prefix) -> bool {
752		HashDB::get(self, key, prefix).is_some()
753	}
754
755	fn insert(&mut self, prefix: Prefix, value: &[u8]) -> H::Out {
756		HashDB::insert(self.overlay, prefix, value)
757	}
758
759	fn emplace(&mut self, key: H::Out, prefix: Prefix, value: DBValue) {
760		HashDB::emplace(self.overlay, key, prefix, value)
761	}
762
763	fn remove(&mut self, key: &H::Out, prefix: Prefix) {
764		HashDB::remove(self.overlay, key, prefix)
765	}
766}
767
768impl<'a, S: 'a + TrieBackendStorage<H>, H: Hasher> HashDBRef<H, DBValue> for Ephemeral<'a, S, H> {
769	fn get(&self, key: &H::Out, prefix: Prefix) -> Option<DBValue> {
770		HashDB::get(self, key, prefix)
771	}
772
773	fn contains(&self, key: &H::Out, prefix: Prefix) -> bool {
774		HashDB::contains(self, key, prefix)
775	}
776}
777
778/// Key-value pairs storage that is used by trie backend essence.
779pub trait TrieBackendStorage<H: Hasher>: Send + Sync {
780	/// Get the value stored at key.
781	fn get(&self, key: &H::Out, prefix: Prefix) -> Result<Option<DBValue>>;
782}
783
784impl<T: TrieBackendStorage<H>, H: Hasher> TrieBackendStorage<H> for &T {
785	fn get(&self, key: &H::Out, prefix: Prefix) -> Result<Option<DBValue>> {
786		(*self).get(key, prefix)
787	}
788}
789
790// This implementation is used by normal storage trie clients.
791#[cfg(feature = "std")]
792impl<H: Hasher> TrieBackendStorage<H> for Arc<dyn Storage<H>> {
793	fn get(&self, key: &H::Out, prefix: Prefix) -> Result<Option<DBValue>> {
794		Storage::<H>::get(std::ops::Deref::deref(self), key, prefix)
795	}
796}
797
798impl<H, KF> TrieBackendStorage<H> for sp_trie::GenericMemoryDB<H, KF>
799where
800	H: Hasher,
801	KF: sp_trie::KeyFunction<H> + Send + Sync,
802{
803	fn get(&self, key: &H::Out, prefix: Prefix) -> Result<Option<DBValue>> {
804		Ok(hash_db::HashDB::get(self, key, prefix))
805	}
806}
807
808impl<
809		S: TrieBackendStorage<H>,
810		H: Hasher,
811		C: TrieCacheProvider<H> + Send + Sync,
812		R: TrieRecorderProvider<H> + Send + Sync,
813	> AsHashDB<H, DBValue> for TrieBackendEssence<S, H, C, R>
814{
815	fn as_hash_db<'b>(&'b self) -> &'b (dyn HashDB<H, DBValue> + 'b) {
816		self
817	}
818
819	fn as_hash_db_mut<'b>(&'b mut self) -> &'b mut (dyn HashDB<H, DBValue> + 'b) {
820		self
821	}
822}
823
824impl<
825		S: TrieBackendStorage<H>,
826		H: Hasher,
827		C: TrieCacheProvider<H> + Send + Sync,
828		R: TrieRecorderProvider<H> + Send + Sync,
829	> HashDB<H, DBValue> for TrieBackendEssence<S, H, C, R>
830{
831	fn get(&self, key: &H::Out, prefix: Prefix) -> Option<DBValue> {
832		if *key == self.empty {
833			return Some([0u8].to_vec())
834		}
835		match self.storage.get(key, prefix) {
836			Ok(x) => x,
837			Err(e) => {
838				warn!(target: "trie", "Failed to read from DB: {}", e);
839				None
840			},
841		}
842	}
843
844	fn contains(&self, key: &H::Out, prefix: Prefix) -> bool {
845		HashDB::get(self, key, prefix).is_some()
846	}
847
848	fn insert(&mut self, _prefix: Prefix, _value: &[u8]) -> H::Out {
849		unimplemented!();
850	}
851
852	fn emplace(&mut self, _key: H::Out, _prefix: Prefix, _value: DBValue) {
853		unimplemented!();
854	}
855
856	fn remove(&mut self, _key: &H::Out, _prefix: Prefix) {
857		unimplemented!();
858	}
859}
860
861impl<
862		S: TrieBackendStorage<H>,
863		H: Hasher,
864		C: TrieCacheProvider<H> + Send + Sync,
865		R: TrieRecorderProvider<H> + Send + Sync,
866	> HashDBRef<H, DBValue> for TrieBackendEssence<S, H, C, R>
867{
868	fn get(&self, key: &H::Out, prefix: Prefix) -> Option<DBValue> {
869		HashDB::get(self, key, prefix)
870	}
871
872	fn contains(&self, key: &H::Out, prefix: Prefix) -> bool {
873		HashDB::contains(self, key, prefix)
874	}
875}
876
877#[cfg(test)]
878mod test {
879	use super::*;
880	use crate::{Backend, TrieBackend};
881	use sp_core::{Blake2Hasher, H256};
882	use sp_trie::{
883		cache::LocalTrieCache, trie_types::TrieDBMutBuilderV1 as TrieDBMutBuilder, KeySpacedDBMut,
884		PrefixedMemoryDB, TrieMut,
885	};
886
887	#[test]
888	fn next_storage_key_and_next_child_storage_key_work() {
889		let child_info = ChildInfo::new_default(b"MyChild");
890		let child_info = &child_info;
891		// Contains values
892		let mut root_1 = H256::default();
893		// Contains child trie
894		let mut root_2 = H256::default();
895
896		let mut mdb = PrefixedMemoryDB::<Blake2Hasher>::default();
897		{
898			let mut trie = TrieDBMutBuilder::new(&mut mdb, &mut root_1).build();
899			trie.insert(b"3", &[1]).expect("insert failed");
900			trie.insert(b"4", &[1]).expect("insert failed");
901			trie.insert(b"6", &[1]).expect("insert failed");
902		}
903		{
904			let mut mdb = KeySpacedDBMut::new(&mut mdb, child_info.keyspace());
905			// reuse of root_1 implicitly assert child trie root is same
906			// as top trie (contents must remain the same).
907			let mut trie = TrieDBMutBuilder::new(&mut mdb, &mut root_1).build();
908			trie.insert(b"3", &[1]).expect("insert failed");
909			trie.insert(b"4", &[1]).expect("insert failed");
910			trie.insert(b"6", &[1]).expect("insert failed");
911		}
912		{
913			let mut trie = TrieDBMutBuilder::new(&mut mdb, &mut root_2).build();
914			trie.insert(child_info.prefixed_storage_key().as_slice(), root_1.as_ref())
915				.expect("insert failed");
916		};
917
918		let essence_1 =
919			TrieBackendEssence::<_, _, LocalTrieCache<_>, sp_trie::recorder::Recorder<_>>::new(
920				mdb, root_1,
921			);
922		let mdb = essence_1.backend_storage().clone();
923		let essence_1 = TrieBackend::from_essence(essence_1);
924
925		assert_eq!(essence_1.next_storage_key(b"2"), Ok(Some(b"3".to_vec())));
926		assert_eq!(essence_1.next_storage_key(b"3"), Ok(Some(b"4".to_vec())));
927		assert_eq!(essence_1.next_storage_key(b"4"), Ok(Some(b"6".to_vec())));
928		assert_eq!(essence_1.next_storage_key(b"5"), Ok(Some(b"6".to_vec())));
929		assert_eq!(essence_1.next_storage_key(b"6"), Ok(None));
930
931		let essence_2 =
932			TrieBackendEssence::<_, _, LocalTrieCache<_>, sp_trie::recorder::Recorder<_>>::new(
933				mdb, root_2,
934			);
935
936		assert_eq!(essence_2.next_child_storage_key(child_info, b"2"), Ok(Some(b"3".to_vec())));
937		assert_eq!(essence_2.next_child_storage_key(child_info, b"3"), Ok(Some(b"4".to_vec())));
938		assert_eq!(essence_2.next_child_storage_key(child_info, b"4"), Ok(Some(b"6".to_vec())));
939		assert_eq!(essence_2.next_child_storage_key(child_info, b"5"), Ok(Some(b"6".to_vec())));
940		assert_eq!(essence_2.next_child_storage_key(child_info, b"6"), Ok(None));
941	}
942}