1use 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;
45use 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
61pub trait Storage<H: Hasher>: Send + Sync {
63 fn get(&self, key: &H::Out, prefix: Prefix) -> Result<Option<DBValue>>;
65}
66
67#[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
86pub 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
209pub 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 pub fn new(storage: S, root: H::Out) -> Self {
223 Self::new_with_cache(storage, root, None)
224 }
225
226 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 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 pub fn backend_storage(&self) -> &S {
259 &self.storage
260 }
261
262 pub fn backend_storage_mut(&mut self) -> &mut S {
264 &mut self.storage
265 }
266
267 pub fn root(&self) -> &H::Out {
269 &self.root
270 }
271
272 pub fn set_root(&mut self, root: H::Out) {
274 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 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 #[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 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 #[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 #[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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
778pub trait TrieBackendStorage<H: Hasher>: Send + Sync {
780 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#[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 let mut root_1 = H256::default();
893 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 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}