referrerpolicy=no-referrer-when-downgrade

sp_state_machine/
ext.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//! Concrete externalities implementation.
19
20#[cfg(feature = "std")]
21use crate::overlayed_changes::OverlayedExtensions;
22use crate::{
23	backend::Backend, IndexOperation, IterArgs, OverlayedChanges, StorageKey, StorageValue,
24};
25use codec::{Compact, CompactLen, Decode, Encode};
26use hash_db::Hasher;
27#[cfg(feature = "std")]
28use sp_core::hexdisplay::HexDisplay;
29use sp_core::storage::{
30	well_known_keys::is_child_storage_key, ChildInfo, StateVersion, TrackedStorageKey,
31};
32use sp_externalities::{Extension, ExtensionStore, Externalities, MultiRemovalResults};
33
34use crate::{trace, warn};
35use alloc::{boxed::Box, vec::Vec};
36use core::{
37	any::{Any, TypeId},
38	cmp::Ordering,
39};
40#[cfg(feature = "std")]
41use std::error;
42
43const EXT_NOT_ALLOWED_TO_FAIL: &str = "Externalities not allowed to fail within runtime";
44const BENCHMARKING_FN: &str = "\
45	This is a special fn only for benchmarking where a database commit happens from the runtime.
46	For that reason client started transactions before calling into runtime are not allowed.
47	Without client transactions the loop condition guarantees the success of the tx close.";
48
49#[cfg(feature = "std")]
50fn guard() -> sp_panic_handler::AbortGuard {
51	sp_panic_handler::AbortGuard::force_abort()
52}
53
54#[cfg(not(feature = "std"))]
55fn guard() -> () {
56	()
57}
58
59/// Errors that can occur when interacting with the externalities.
60#[cfg(feature = "std")]
61#[derive(Debug, Copy, Clone)]
62pub enum Error<B, E> {
63	/// Failure to load state data from the backend.
64	#[allow(unused)]
65	Backend(B),
66	/// Failure to execute a function.
67	#[allow(unused)]
68	Executor(E),
69}
70
71#[cfg(feature = "std")]
72impl<B: std::fmt::Display, E: std::fmt::Display> std::fmt::Display for Error<B, E> {
73	fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
74		match *self {
75			Error::Backend(ref e) => write!(f, "Storage backend error: {}", e),
76			Error::Executor(ref e) => write!(f, "Sub-call execution error: {}", e),
77		}
78	}
79}
80
81#[cfg(feature = "std")]
82impl<B: error::Error, E: error::Error> error::Error for Error<B, E> {
83	fn description(&self) -> &str {
84		match *self {
85			Error::Backend(..) => "backend error",
86			Error::Executor(..) => "executor error",
87		}
88	}
89}
90
91/// Wraps a read-only backend, call executor, and current overlayed changes.
92pub struct Ext<'a, H, B>
93where
94	H: Hasher,
95	B: 'a + Backend<H>,
96{
97	/// The overlayed changes to write to.
98	overlay: &'a mut OverlayedChanges<H>,
99	/// The storage backend to read from.
100	backend: &'a B,
101	/// Pseudo-unique id used for tracing.
102	pub id: u16,
103	/// Extensions registered with this instance.
104	#[cfg(feature = "std")]
105	extensions: Option<OverlayedExtensions<'a>>,
106}
107
108impl<'a, H, B> Ext<'a, H, B>
109where
110	H: Hasher,
111	B: Backend<H>,
112{
113	/// Create a new `Ext`.
114	#[cfg(not(feature = "std"))]
115	pub fn new(overlay: &'a mut OverlayedChanges<H>, backend: &'a B) -> Self {
116		Ext { overlay, backend, id: 0 }
117	}
118
119	/// Create a new `Ext` from overlayed changes and read-only backend
120	#[cfg(feature = "std")]
121	pub fn new(
122		overlay: &'a mut OverlayedChanges<H>,
123		backend: &'a B,
124		extensions: Option<&'a mut sp_externalities::Extensions>,
125	) -> Self {
126		Self {
127			overlay,
128			backend,
129			id: rand::random(),
130			extensions: extensions.map(OverlayedExtensions::new),
131		}
132	}
133}
134
135#[cfg(test)]
136impl<'a, H, B> Ext<'a, H, B>
137where
138	H: Hasher,
139	H::Out: Ord + 'static,
140	B: 'a + Backend<H>,
141{
142	/// Return all storage pairs from the backend and overlay combined.
143	pub fn storage_pairs(&mut self) -> Vec<(StorageKey, StorageValue)> {
144		use std::collections::HashMap;
145
146		self.backend
147			.pairs(Default::default())
148			.expect("never fails in tests; qed.")
149			.map(|key_value| key_value.expect("never fails in tests; qed."))
150			.map(|(k, v)| (k, Some(v)))
151			.chain(self.overlay.changes_mut().map(|(k, v)| (k.clone(), v.value().cloned())))
152			.collect::<HashMap<_, _>>()
153			.into_iter()
154			.filter_map(|(k, maybe_val)| maybe_val.map(|val| (k, val)))
155			.collect()
156	}
157}
158
159impl<'a, H, B> Externalities for Ext<'a, H, B>
160where
161	H: Hasher,
162	H::Out: Ord + 'static + codec::Codec,
163	B: Backend<H>,
164{
165	fn set_offchain_storage(&mut self, key: &[u8], value: Option<&[u8]>) {
166		self.overlay.set_offchain_storage(key, value)
167	}
168
169	fn storage(&mut self, key: &[u8]) -> Option<StorageValue> {
170		let _guard = guard();
171		let result = self
172			.overlay
173			.storage(key)
174			.map(|x| x.map(|x| x.to_vec()))
175			.unwrap_or_else(|| self.backend.storage(key).expect(EXT_NOT_ALLOWED_TO_FAIL));
176
177		// NOTE: be careful about touching the key names – used outside substrate!
178		trace!(
179			target: "state",
180			method = "Get",
181			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
182			key = %HexDisplay::from(&key),
183			result = ?result.as_ref().map(HexDisplay::from),
184			result_encoded = %HexDisplay::from(
185				&result
186					.as_ref()
187					.map(|v| EncodeOpaqueValue(v.clone()))
188					.encode()
189			),
190		);
191
192		result
193	}
194
195	fn storage_hash(&mut self, key: &[u8]) -> Option<Vec<u8>> {
196		let _guard = guard();
197		let result = self
198			.overlay
199			.storage(key)
200			.map(|x| x.map(|x| H::hash(x)))
201			.unwrap_or_else(|| self.backend.storage_hash(key).expect(EXT_NOT_ALLOWED_TO_FAIL));
202
203		trace!(
204			target: "state",
205			method = "Hash",
206			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
207			key = %HexDisplay::from(&key),
208			?result,
209		);
210		result.map(|r| r.encode())
211	}
212
213	fn child_storage(&mut self, child_info: &ChildInfo, key: &[u8]) -> Option<StorageValue> {
214		let _guard = guard();
215		let result = self
216			.overlay
217			.child_storage(child_info, key)
218			.map(|x| x.map(|x| x.to_vec()))
219			.unwrap_or_else(|| {
220				self.backend.child_storage(child_info, key).expect(EXT_NOT_ALLOWED_TO_FAIL)
221			});
222
223		trace!(
224			target: "state",
225			method = "ChildGet",
226			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
227			child_info = %HexDisplay::from(&child_info.storage_key()),
228			key = %HexDisplay::from(&key),
229			result = ?result.as_ref().map(HexDisplay::from)
230		);
231
232		result
233	}
234
235	fn child_storage_hash(&mut self, child_info: &ChildInfo, key: &[u8]) -> Option<Vec<u8>> {
236		let _guard = guard();
237		let result = self
238			.overlay
239			.child_storage(child_info, key)
240			.map(|x| x.map(|x| H::hash(x)))
241			.unwrap_or_else(|| {
242				self.backend.child_storage_hash(child_info, key).expect(EXT_NOT_ALLOWED_TO_FAIL)
243			});
244
245		trace!(
246			target: "state",
247			method = "ChildHash",
248			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
249			child_info = %HexDisplay::from(&child_info.storage_key()),
250			key = %HexDisplay::from(&key),
251			?result,
252		);
253
254		result.map(|r| r.encode())
255	}
256
257	fn exists_storage(&mut self, key: &[u8]) -> bool {
258		let _guard = guard();
259		let result = match self.overlay.storage(key) {
260			Some(x) => x.is_some(),
261			_ => self.backend.exists_storage(key).expect(EXT_NOT_ALLOWED_TO_FAIL),
262		};
263
264		trace!(
265			target: "state",
266			method = "Exists",
267			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
268			key = %HexDisplay::from(&key),
269			%result,
270		);
271
272		result
273	}
274
275	fn exists_child_storage(&mut self, child_info: &ChildInfo, key: &[u8]) -> bool {
276		let _guard = guard();
277
278		let result = match self.overlay.child_storage(child_info, key) {
279			Some(x) => x.is_some(),
280			_ => self
281				.backend
282				.exists_child_storage(child_info, key)
283				.expect(EXT_NOT_ALLOWED_TO_FAIL),
284		};
285
286		trace!(
287			target: "state",
288			method = "ChildExists",
289			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
290			child_info = %HexDisplay::from(&child_info.storage_key()),
291			key = %HexDisplay::from(&key),
292			%result,
293		);
294		result
295	}
296
297	fn next_storage_key(&mut self, key: &[u8]) -> Option<StorageKey> {
298		let mut next_backend_key =
299			self.backend.next_storage_key(key).expect(EXT_NOT_ALLOWED_TO_FAIL);
300		let mut overlay_changes = self.overlay.iter_after(key).peekable();
301
302		match (&next_backend_key, overlay_changes.peek()) {
303			(_, None) => next_backend_key,
304			(Some(_), Some(_)) => {
305				for overlay_key in overlay_changes {
306					let cmp = next_backend_key.as_deref().map(|v| v.cmp(overlay_key.0));
307
308					// If `backend_key` is less than the `overlay_key`, we found out next key.
309					if cmp == Some(Ordering::Less) {
310						return next_backend_key
311					} else if overlay_key.1.value().is_some() {
312						// If there exists a value for the `overlay_key` in the overlay
313						// (aka the key is still valid), it means we have found our next key.
314						return Some(overlay_key.0.to_vec())
315					} else if cmp == Some(Ordering::Equal) {
316						// If the `backend_key` and `overlay_key` are equal, it means that we need
317						// to search for the next backend key, because the overlay has overwritten
318						// this key.
319						next_backend_key = self
320							.backend
321							.next_storage_key(overlay_key.0)
322							.expect(EXT_NOT_ALLOWED_TO_FAIL);
323					}
324				}
325
326				next_backend_key
327			},
328			(None, Some(_)) => {
329				// Find the next overlay key that has a value attached.
330				overlay_changes.find_map(|k| k.1.value().as_ref().map(|_| k.0.to_vec()))
331			},
332		}
333	}
334
335	fn next_child_storage_key(&mut self, child_info: &ChildInfo, key: &[u8]) -> Option<StorageKey> {
336		let mut next_backend_key = self
337			.backend
338			.next_child_storage_key(child_info, key)
339			.expect(EXT_NOT_ALLOWED_TO_FAIL);
340		let mut overlay_changes =
341			self.overlay.child_iter_after(child_info.storage_key(), key).peekable();
342
343		match (&next_backend_key, overlay_changes.peek()) {
344			(_, None) => next_backend_key,
345			(Some(_), Some(_)) => {
346				for overlay_key in overlay_changes {
347					let cmp = next_backend_key.as_deref().map(|v| v.cmp(overlay_key.0));
348
349					// If `backend_key` is less than the `overlay_key`, we found out next key.
350					if cmp == Some(Ordering::Less) {
351						return next_backend_key
352					} else if overlay_key.1.value().is_some() {
353						// If there exists a value for the `overlay_key` in the overlay
354						// (aka the key is still valid), it means we have found our next key.
355						return Some(overlay_key.0.to_vec())
356					} else if cmp == Some(Ordering::Equal) {
357						// If the `backend_key` and `overlay_key` are equal, it means that we need
358						// to search for the next backend key, because the overlay has overwritten
359						// this key.
360						next_backend_key = self
361							.backend
362							.next_child_storage_key(child_info, overlay_key.0)
363							.expect(EXT_NOT_ALLOWED_TO_FAIL);
364					}
365				}
366
367				next_backend_key
368			},
369			(None, Some(_)) => {
370				// Find the next overlay key that has a value attached.
371				overlay_changes.find_map(|k| k.1.value().as_ref().map(|_| k.0.to_vec()))
372			},
373		}
374	}
375
376	fn place_storage(&mut self, key: StorageKey, value: Option<StorageValue>) {
377		let _guard = guard();
378		if is_child_storage_key(&key) {
379			warn!(target: "trie", "Refuse to directly set child storage key");
380			return
381		}
382
383		// NOTE: be careful about touching the key names – used outside substrate!
384		trace!(
385			target: "state",
386			method = "Put",
387			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
388			key = %HexDisplay::from(&key),
389			value = ?value.as_ref().map(HexDisplay::from),
390			value_encoded = %HexDisplay::from(
391				&value
392					.as_ref()
393					.map(|v| EncodeOpaqueValue(v.clone()))
394					.encode()
395			),
396		);
397
398		self.overlay.set_storage(key, value);
399	}
400
401	fn place_child_storage(
402		&mut self,
403		child_info: &ChildInfo,
404		key: StorageKey,
405		value: Option<StorageValue>,
406	) {
407		trace!(
408			target: "state",
409			method = "ChildPut",
410			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
411			child_info = %HexDisplay::from(&child_info.storage_key()),
412			key = %HexDisplay::from(&key),
413			value = ?value.as_ref().map(HexDisplay::from),
414		);
415		let _guard = guard();
416
417		self.overlay.set_child_storage(child_info, key, value);
418	}
419
420	fn kill_child_storage(
421		&mut self,
422		child_info: &ChildInfo,
423		maybe_limit: Option<u32>,
424		maybe_cursor: Option<&[u8]>,
425	) -> MultiRemovalResults {
426		trace!(
427			target: "state",
428			method = "ChildKill",
429			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
430			child_info = %HexDisplay::from(&child_info.storage_key()),
431		);
432		let _guard = guard();
433		let overlay = self.overlay.clear_child_storage(child_info);
434		let (maybe_cursor, backend, loops) =
435			self.limit_remove_from_backend(Some(child_info), None, maybe_limit, maybe_cursor);
436		MultiRemovalResults { maybe_cursor, backend, unique: overlay + backend, loops }
437	}
438
439	fn clear_prefix(
440		&mut self,
441		prefix: &[u8],
442		maybe_limit: Option<u32>,
443		maybe_cursor: Option<&[u8]>,
444	) -> MultiRemovalResults {
445		trace!(
446			target: "state",
447			method = "ClearPrefix",
448			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
449			prefix = %HexDisplay::from(&prefix),
450		);
451		let _guard = guard();
452
453		if sp_core::storage::well_known_keys::starts_with_child_storage_key(prefix) {
454			warn!(
455				target: "trie",
456				"Refuse to directly clear prefix that is part or contains of child storage key",
457			);
458			return MultiRemovalResults { maybe_cursor: None, backend: 0, unique: 0, loops: 0 }
459		}
460
461		let overlay = self.overlay.clear_prefix(prefix);
462		let (maybe_cursor, backend, loops) =
463			self.limit_remove_from_backend(None, Some(prefix), maybe_limit, maybe_cursor);
464		MultiRemovalResults { maybe_cursor, backend, unique: overlay + backend, loops }
465	}
466
467	fn clear_child_prefix(
468		&mut self,
469		child_info: &ChildInfo,
470		prefix: &[u8],
471		maybe_limit: Option<u32>,
472		maybe_cursor: Option<&[u8]>,
473	) -> MultiRemovalResults {
474		trace!(
475			target: "state",
476			method = "ChildClearPrefix",
477			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
478			child_info = %HexDisplay::from(&child_info.storage_key()),
479			prefix = %HexDisplay::from(&prefix),
480		);
481		let _guard = guard();
482
483		let overlay = self.overlay.clear_child_prefix(child_info, prefix);
484		let (maybe_cursor, backend, loops) = self.limit_remove_from_backend(
485			Some(child_info),
486			Some(prefix),
487			maybe_limit,
488			maybe_cursor,
489		);
490		MultiRemovalResults { maybe_cursor, backend, unique: overlay + backend, loops }
491	}
492
493	fn storage_append(&mut self, key: Vec<u8>, value: Vec<u8>) {
494		trace!(
495			target: "state",
496			method = "Append",
497			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
498			key = %HexDisplay::from(&key),
499			value = %HexDisplay::from(&value),
500		);
501
502		let _guard = guard();
503
504		let backend = &mut self.backend;
505		self.overlay.append_storage(key.clone(), value, || {
506			backend.storage(&key).expect(EXT_NOT_ALLOWED_TO_FAIL).unwrap_or_default()
507		});
508	}
509
510	fn storage_root(&mut self, state_version: StateVersion) -> Vec<u8> {
511		let _guard = guard();
512
513		let (root, _cached) = self.overlay.storage_root(self.backend, state_version);
514
515		trace!(
516			target: "state",
517			method = "StorageRoot",
518			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
519			storage_root = %HexDisplay::from(&root.as_ref()),
520			cached = %_cached,
521		);
522
523		root.encode()
524	}
525
526	fn child_storage_root(
527		&mut self,
528		child_info: &ChildInfo,
529		state_version: StateVersion,
530	) -> Vec<u8> {
531		let _guard = guard();
532
533		let (root, _cached) = self
534			.overlay
535			.child_storage_root(child_info, self.backend, state_version)
536			.expect(EXT_NOT_ALLOWED_TO_FAIL);
537
538		trace!(
539			target: "state",
540			method = "ChildStorageRoot",
541			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
542			child_info = %HexDisplay::from(&child_info.storage_key()),
543			storage_root = %HexDisplay::from(&root.as_ref()),
544			cached = %_cached,
545		);
546
547		root.encode()
548	}
549
550	fn storage_index_transaction(&mut self, index: u32, hash: &[u8], size: u32) {
551		trace!(
552			target: "state",
553			method = "IndexTransaction",
554			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
555			%index,
556			tx_hash = %HexDisplay::from(&hash),
557			%size,
558		);
559
560		self.overlay.add_transaction_index(IndexOperation::Insert {
561			extrinsic: index,
562			hash: hash.to_vec(),
563			size,
564		});
565	}
566
567	/// Renew existing piece of data storage.
568	fn storage_renew_transaction_index(&mut self, index: u32, hash: &[u8]) {
569		trace!(
570			target: "state",
571			method = "RenewTransactionIndex",
572			ext_id = %HexDisplay::from(&self.id.to_le_bytes()),
573			%index,
574			tx_hash = %HexDisplay::from(&hash),
575		);
576
577		self.overlay
578			.add_transaction_index(IndexOperation::Renew { extrinsic: index, hash: hash.to_vec() });
579	}
580
581	fn storage_start_transaction(&mut self) {
582		self.overlay.start_transaction()
583	}
584
585	fn storage_rollback_transaction(&mut self) -> Result<(), ()> {
586		self.overlay.rollback_transaction().map_err(|_| ())
587	}
588
589	fn storage_commit_transaction(&mut self) -> Result<(), ()> {
590		self.overlay.commit_transaction().map_err(|_| ())
591	}
592
593	fn wipe(&mut self) {
594		for _ in 0..self.overlay.transaction_depth() {
595			self.overlay.rollback_transaction().expect(BENCHMARKING_FN);
596		}
597		self.overlay
598			.drain_storage_changes(self.backend, Default::default())
599			.expect(EXT_NOT_ALLOWED_TO_FAIL);
600		self.backend.wipe().expect(EXT_NOT_ALLOWED_TO_FAIL);
601		self.overlay
602			.enter_runtime()
603			.expect("We have reset the overlay above, so we can not be in the runtime; qed");
604	}
605
606	fn commit(&mut self) {
607		// Bench always use latest state.
608		let state_version = StateVersion::default();
609		for _ in 0..self.overlay.transaction_depth() {
610			self.overlay.commit_transaction().expect(BENCHMARKING_FN);
611		}
612		let changes = self
613			.overlay
614			.drain_storage_changes(self.backend, state_version)
615			.expect(EXT_NOT_ALLOWED_TO_FAIL);
616		self.backend
617			.commit(
618				changes.transaction_storage_root,
619				changes.transaction,
620				changes.main_storage_changes,
621				changes.child_storage_changes,
622			)
623			.expect(EXT_NOT_ALLOWED_TO_FAIL);
624		self.overlay
625			.enter_runtime()
626			.expect("We have reset the overlay above, so we can not be in the runtime; qed");
627	}
628
629	fn read_write_count(&self) -> (u32, u32, u32, u32) {
630		self.backend.read_write_count()
631	}
632
633	fn reset_read_write_count(&mut self) {
634		self.backend.reset_read_write_count()
635	}
636
637	fn get_whitelist(&self) -> Vec<TrackedStorageKey> {
638		self.backend.get_whitelist()
639	}
640
641	fn set_whitelist(&mut self, new: Vec<TrackedStorageKey>) {
642		self.backend.set_whitelist(new)
643	}
644
645	fn proof_size(&self) -> Option<u32> {
646		self.backend.proof_size()
647	}
648
649	fn get_read_and_written_keys(&self) -> Vec<(Vec<u8>, u32, u32, bool)> {
650		self.backend.get_read_and_written_keys()
651	}
652}
653
654impl<'a, H, B> Ext<'a, H, B>
655where
656	H: Hasher,
657	H::Out: Ord + 'static + codec::Codec,
658	B: Backend<H>,
659{
660	fn limit_remove_from_backend(
661		&mut self,
662		child_info: Option<&ChildInfo>,
663		prefix: Option<&[u8]>,
664		maybe_limit: Option<u32>,
665		start_at: Option<&[u8]>,
666	) -> (Option<Vec<u8>>, u32, u32) {
667		let iter = match self.backend.keys(IterArgs {
668			child_info: child_info.cloned(),
669			prefix,
670			start_at,
671			..IterArgs::default()
672		}) {
673			Ok(iter) => iter,
674			Err(error) => {
675				log::debug!(target: "trie", "Error while iterating the storage: {}", error);
676				return (None, 0, 0)
677			},
678		};
679
680		let mut delete_count: u32 = 0;
681		let mut loop_count: u32 = 0;
682		let mut maybe_next_key = None;
683		for key in iter {
684			let key = match key {
685				Ok(key) => key,
686				Err(error) => {
687					log::debug!(target: "trie", "Error while iterating the storage: {}", error);
688					break
689				},
690			};
691
692			if maybe_limit.map_or(false, |limit| loop_count == limit) {
693				maybe_next_key = Some(key);
694				break
695			}
696			let overlay = match child_info {
697				Some(child_info) => self.overlay.child_storage(child_info, &key),
698				None => self.overlay.storage(&key),
699			};
700			if !matches!(overlay, Some(None)) {
701				// not pending deletion from the backend - delete it.
702				if let Some(child_info) = child_info {
703					self.overlay.set_child_storage(child_info, key, None);
704				} else {
705					self.overlay.set_storage(key, None);
706				}
707				delete_count = delete_count.saturating_add(1);
708			}
709			loop_count = loop_count.saturating_add(1);
710		}
711
712		(maybe_next_key, delete_count, loop_count)
713	}
714}
715
716/// Implement `Encode` by forwarding the stored raw vec.
717#[allow(dead_code)]
718struct EncodeOpaqueValue(Vec<u8>);
719
720impl Encode for EncodeOpaqueValue {
721	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
722		f(&self.0)
723	}
724}
725
726/// Auxiliary structure for appending a value to a storage item.
727pub(crate) struct StorageAppend<'a>(&'a mut Vec<u8>);
728
729impl<'a> StorageAppend<'a> {
730	/// Create a new instance using the given `storage` reference.
731	pub fn new(storage: &'a mut Vec<u8>) -> Self {
732		Self(storage)
733	}
734
735	/// Extract the length of the list like data structure.
736	pub fn extract_length(&self) -> Option<u32> {
737		Compact::<u32>::decode(&mut &self.0[..]).map(|c| c.0).ok()
738	}
739
740	/// Replace the length in the encoded data.
741	///
742	/// If `old_length` is `None`, the previous length will be assumed to be `0`.
743	pub fn replace_length(&mut self, old_length: Option<u32>, new_length: u32) {
744		let old_len_encoded_len = old_length.map(|l| Compact::<u32>::compact_len(&l)).unwrap_or(0);
745		let new_len_encoded = Compact::<u32>(new_length).encode();
746		self.0.splice(0..old_len_encoded_len, new_len_encoded);
747	}
748
749	/// Append the given `value` to the storage item.
750	///
751	/// If appending fails, `[value]` is stored in the storage item and we return false.
752	#[cfg(any(test, feature = "fuzzing"))]
753	pub fn append(&mut self, value: Vec<u8>) -> bool {
754		use codec::EncodeAppend;
755		let mut result = true;
756		let value = vec![EncodeOpaqueValue(value)];
757
758		let item = core::mem::take(self.0);
759
760		*self.0 = match Vec::<EncodeOpaqueValue>::append_or_new(item, &value) {
761			Ok(item) => item,
762			Err(_) => {
763				result = false;
764				crate::log_error!(
765					target: "runtime",
766					"Failed to append value, resetting storage item to `[value]`.",
767				);
768				value.encode()
769			},
770		};
771		result
772	}
773
774	/// Append to current buffer, do not touch the prefixed length.
775	pub fn append_raw(&mut self, mut value: Vec<u8>) {
776		self.0.append(&mut value)
777	}
778}
779
780#[cfg(not(feature = "std"))]
781impl<'a, H, B> ExtensionStore for Ext<'a, H, B>
782where
783	H: Hasher,
784	H::Out: Ord + 'static + codec::Codec,
785	B: Backend<H>,
786{
787	fn extension_by_type_id(&mut self, _type_id: TypeId) -> Option<&mut dyn Any> {
788		None
789	}
790
791	fn register_extension_with_type_id(
792		&mut self,
793		_type_id: TypeId,
794		_extension: Box<dyn Extension>,
795	) -> Result<(), sp_externalities::Error> {
796		Err(sp_externalities::Error::ExtensionsAreNotSupported)
797	}
798
799	fn deregister_extension_by_type_id(
800		&mut self,
801		_type_id: TypeId,
802	) -> Result<(), sp_externalities::Error> {
803		Err(sp_externalities::Error::ExtensionsAreNotSupported)
804	}
805}
806
807#[cfg(feature = "std")]
808impl<'a, H, B> ExtensionStore for Ext<'a, H, B>
809where
810	H: Hasher,
811	B: 'a + Backend<H>,
812{
813	fn extension_by_type_id(&mut self, type_id: TypeId) -> Option<&mut dyn Any> {
814		self.extensions.as_mut().and_then(|exts| exts.get_mut(type_id))
815	}
816
817	fn register_extension_with_type_id(
818		&mut self,
819		type_id: TypeId,
820		extension: Box<dyn Extension>,
821	) -> Result<(), sp_externalities::Error> {
822		if let Some(ref mut extensions) = self.extensions {
823			extensions.register(type_id, extension)
824		} else {
825			Err(sp_externalities::Error::ExtensionsAreNotSupported)
826		}
827	}
828
829	fn deregister_extension_by_type_id(
830		&mut self,
831		type_id: TypeId,
832	) -> Result<(), sp_externalities::Error> {
833		if let Some(ref mut extensions) = self.extensions {
834			if extensions.deregister(type_id) {
835				Ok(())
836			} else {
837				Err(sp_externalities::Error::ExtensionIsNotRegistered(type_id))
838			}
839		} else {
840			Err(sp_externalities::Error::ExtensionsAreNotSupported)
841		}
842	}
843}
844
845#[cfg(test)]
846mod tests {
847	use super::*;
848	use crate::InMemoryBackend;
849	use codec::{Decode, Encode};
850	use sp_core::{
851		map,
852		storage::{Storage, StorageChild},
853		Blake2Hasher,
854	};
855
856	type TestBackend = InMemoryBackend<Blake2Hasher>;
857	type TestExt<'a> = Ext<'a, Blake2Hasher, TestBackend>;
858
859	#[test]
860	fn next_storage_key_works() {
861		let mut overlay = OverlayedChanges::default();
862		overlay.set_storage(vec![20], None);
863		overlay.set_storage(vec![30], Some(vec![31]));
864		let backend = (
865			Storage {
866				top: map![
867					vec![10] => vec![10],
868					vec![20] => vec![20],
869					vec![40] => vec![40]
870				],
871				children_default: map![],
872			},
873			StateVersion::default(),
874		)
875			.into();
876
877		let mut ext = TestExt::new(&mut overlay, &backend, None);
878
879		// next_backend < next_overlay
880		assert_eq!(ext.next_storage_key(&[5]), Some(vec![10]));
881
882		// next_backend == next_overlay but next_overlay is a delete
883		assert_eq!(ext.next_storage_key(&[10]), Some(vec![30]));
884
885		// next_overlay < next_backend
886		assert_eq!(ext.next_storage_key(&[20]), Some(vec![30]));
887
888		// next_backend exist but next_overlay doesn't exist
889		assert_eq!(ext.next_storage_key(&[30]), Some(vec![40]));
890
891		drop(ext);
892		overlay.set_storage(vec![50], Some(vec![50]));
893		let mut ext = TestExt::new(&mut overlay, &backend, None);
894
895		// next_overlay exist but next_backend doesn't exist
896		assert_eq!(ext.next_storage_key(&[40]), Some(vec![50]));
897	}
898
899	#[test]
900	fn next_storage_key_works_with_a_lot_empty_values_in_overlay() {
901		let mut overlay = OverlayedChanges::default();
902		overlay.set_storage(vec![20], None);
903		overlay.set_storage(vec![21], None);
904		overlay.set_storage(vec![22], None);
905		overlay.set_storage(vec![23], None);
906		overlay.set_storage(vec![24], None);
907		overlay.set_storage(vec![25], None);
908		overlay.set_storage(vec![26], None);
909		overlay.set_storage(vec![27], None);
910		overlay.set_storage(vec![28], None);
911		overlay.set_storage(vec![29], None);
912		let backend = (
913			Storage {
914				top: map![
915					vec![30] => vec![30]
916				],
917				children_default: map![],
918			},
919			StateVersion::default(),
920		)
921			.into();
922
923		let mut ext = TestExt::new(&mut overlay, &backend, None);
924
925		assert_eq!(ext.next_storage_key(&[5]), Some(vec![30]));
926
927		drop(ext);
928	}
929
930	#[test]
931	fn next_child_storage_key_works() {
932		let child_info = ChildInfo::new_default(b"Child1");
933		let child_info = &child_info;
934
935		let mut overlay = OverlayedChanges::default();
936		overlay.set_child_storage(child_info, vec![20], None);
937		overlay.set_child_storage(child_info, vec![30], Some(vec![31]));
938		let backend = (
939			Storage {
940				top: map![],
941				children_default: map![
942					child_info.storage_key().to_vec() => StorageChild {
943						data: map![
944							vec![10] => vec![10],
945							vec![20] => vec![20],
946							vec![40] => vec![40]
947						],
948						child_info: child_info.to_owned(),
949					}
950				],
951			},
952			StateVersion::default(),
953		)
954			.into();
955
956		let mut ext = TestExt::new(&mut overlay, &backend, None);
957
958		// next_backend < next_overlay
959		assert_eq!(ext.next_child_storage_key(child_info, &[5]), Some(vec![10]));
960
961		// next_backend == next_overlay but next_overlay is a delete
962		assert_eq!(ext.next_child_storage_key(child_info, &[10]), Some(vec![30]));
963
964		// next_overlay < next_backend
965		assert_eq!(ext.next_child_storage_key(child_info, &[20]), Some(vec![30]));
966
967		// next_backend exist but next_overlay doesn't exist
968		assert_eq!(ext.next_child_storage_key(child_info, &[30]), Some(vec![40]));
969
970		drop(ext);
971		overlay.set_child_storage(child_info, vec![50], Some(vec![50]));
972		let mut ext = TestExt::new(&mut overlay, &backend, None);
973
974		// next_overlay exist but next_backend doesn't exist
975		assert_eq!(ext.next_child_storage_key(child_info, &[40]), Some(vec![50]));
976	}
977
978	#[test]
979	fn child_storage_works() {
980		let child_info = ChildInfo::new_default(b"Child1");
981		let child_info = &child_info;
982		let mut overlay = OverlayedChanges::default();
983		overlay.set_child_storage(child_info, vec![20], None);
984		overlay.set_child_storage(child_info, vec![30], Some(vec![31]));
985		let backend = (
986			Storage {
987				top: map![],
988				children_default: map![
989					child_info.storage_key().to_vec() => StorageChild {
990						data: map![
991							vec![10] => vec![10],
992							vec![20] => vec![20],
993							vec![30] => vec![40]
994						],
995						child_info: child_info.to_owned(),
996					}
997				],
998			},
999			StateVersion::default(),
1000		)
1001			.into();
1002
1003		let mut ext = TestExt::new(&mut overlay, &backend, None);
1004
1005		assert_eq!(ext.child_storage(child_info, &[10]), Some(vec![10]));
1006		assert_eq!(
1007			ext.child_storage_hash(child_info, &[10]),
1008			Some(Blake2Hasher::hash(&[10]).as_ref().to_vec()),
1009		);
1010
1011		assert_eq!(ext.child_storage(child_info, &[20]), None);
1012		assert_eq!(ext.child_storage_hash(child_info, &[20]), None);
1013
1014		assert_eq!(ext.child_storage(child_info, &[30]), Some(vec![31]));
1015		assert_eq!(
1016			ext.child_storage_hash(child_info, &[30]),
1017			Some(Blake2Hasher::hash(&[31]).as_ref().to_vec()),
1018		);
1019	}
1020
1021	#[test]
1022	fn clear_prefix_cannot_delete_a_child_root() {
1023		let child_info = ChildInfo::new_default(b"Child1");
1024		let child_info = &child_info;
1025		let mut overlay = OverlayedChanges::default();
1026		let backend = (
1027			Storage {
1028				top: map![],
1029				children_default: map![
1030					child_info.storage_key().to_vec() => StorageChild {
1031						data: map![
1032							vec![30] => vec![40]
1033						],
1034						child_info: child_info.to_owned(),
1035					}
1036				],
1037			},
1038			StateVersion::default(),
1039		)
1040			.into();
1041
1042		let ext = TestExt::new(&mut overlay, &backend, None);
1043
1044		use sp_core::storage::well_known_keys;
1045		let mut ext = ext;
1046		let mut not_under_prefix = well_known_keys::CHILD_STORAGE_KEY_PREFIX.to_vec();
1047		not_under_prefix[4] = 88;
1048		not_under_prefix.extend(b"path");
1049		ext.set_storage(not_under_prefix.clone(), vec![10]);
1050
1051		let _ = ext.clear_prefix(&[], None, None);
1052		let _ = ext.clear_prefix(&well_known_keys::CHILD_STORAGE_KEY_PREFIX[..4], None, None);
1053		let mut under_prefix = well_known_keys::CHILD_STORAGE_KEY_PREFIX.to_vec();
1054		under_prefix.extend(b"path");
1055		let _ = ext.clear_prefix(&well_known_keys::CHILD_STORAGE_KEY_PREFIX[..4], None, None);
1056		assert_eq!(ext.child_storage(child_info, &[30]), Some(vec![40]));
1057		assert_eq!(ext.storage(not_under_prefix.as_slice()), Some(vec![10]));
1058		let _ = ext.clear_prefix(&not_under_prefix[..5], None, None);
1059		assert_eq!(ext.storage(not_under_prefix.as_slice()), None);
1060	}
1061
1062	#[test]
1063	fn storage_append_works() {
1064		let mut data = Vec::new();
1065		let mut append = StorageAppend::new(&mut data);
1066		append.append(1u32.encode());
1067		append.append(2u32.encode());
1068		drop(append);
1069
1070		assert_eq!(Vec::<u32>::decode(&mut &data[..]).unwrap(), vec![1, 2]);
1071
1072		// Initialize with some invalid data
1073		let mut data = vec![1];
1074		let mut append = StorageAppend::new(&mut data);
1075		append.append(1u32.encode());
1076		append.append(2u32.encode());
1077		drop(append);
1078
1079		assert_eq!(Vec::<u32>::decode(&mut &data[..]).unwrap(), vec![1, 2]);
1080	}
1081}