frame_support/storage/types/
key.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//! Storage key type.
19
20use crate::hash::{ReversibleStorageHasher, StorageHasher};
21use alloc::{boxed::Box, vec::Vec};
22use codec::{Encode, EncodeLike, FullCodec, MaxEncodedLen};
23use paste::paste;
24use scale_info::StaticTypeInfo;
25
26/// A type used exclusively by storage maps as their key type.
27///
28/// The final key generated has the following form:
29/// ```nocompile
30/// Hasher1(encode(key1))
31///     ++ Hasher2(encode(key2))
32///     ++ ...
33///     ++ HasherN(encode(keyN))
34/// ```
35pub struct Key<Hasher, KeyType>(core::marker::PhantomData<(Hasher, KeyType)>);
36
37/// A trait that contains the current key as an associated type.
38pub trait KeyGenerator {
39	type Key: EncodeLike<Self::Key> + StaticTypeInfo;
40	type KArg: Encode + EncodeLike<Self::KArg>;
41	type HashFn: FnOnce(&[u8]) -> Vec<u8>;
42	type HArg;
43
44	const HASHER_METADATA: &'static [sp_metadata_ir::StorageHasherIR];
45
46	/// Given a `key` tuple, calculate the final key by encoding each element individually and
47	/// hashing them using the corresponding hasher in the `KeyGenerator`.
48	fn final_key<KArg: EncodeLikeTuple<Self::KArg> + TupleToEncodedIter>(key: KArg) -> Vec<u8>;
49	/// Given a `key` tuple, migrate the keys from using the old hashers as given by `hash_fns`
50	/// to using the newer hashers as specified by this `KeyGenerator`.
51	fn migrate_key<KArg: EncodeLikeTuple<Self::KArg> + TupleToEncodedIter>(
52		key: &KArg,
53		hash_fns: Self::HArg,
54	) -> Vec<u8>;
55}
56
57/// The maximum length used by the key in storage.
58pub trait KeyGeneratorMaxEncodedLen: KeyGenerator {
59	fn key_max_encoded_len() -> usize;
60}
61
62/// A trait containing methods that are only implemented on the Key struct instead of the entire
63/// tuple.
64pub trait KeyGeneratorInner: KeyGenerator {
65	type Hasher: StorageHasher;
66
67	/// Hash a given `encoded` byte slice using the `KeyGenerator`'s associated `StorageHasher`.
68	fn final_hash(encoded: &[u8]) -> Vec<u8>;
69}
70
71impl<H: StorageHasher, K: FullCodec + StaticTypeInfo> KeyGenerator for Key<H, K> {
72	type Key = K;
73	type KArg = (K,);
74	type HashFn = Box<dyn FnOnce(&[u8]) -> Vec<u8>>;
75	type HArg = (Self::HashFn,);
76
77	const HASHER_METADATA: &'static [sp_metadata_ir::StorageHasherIR] = &[H::METADATA];
78
79	fn final_key<KArg: EncodeLikeTuple<Self::KArg> + TupleToEncodedIter>(key: KArg) -> Vec<u8> {
80		H::hash(&key.to_encoded_iter().next().expect("should have at least one element!"))
81			.as_ref()
82			.to_vec()
83	}
84
85	fn migrate_key<KArg: EncodeLikeTuple<Self::KArg> + TupleToEncodedIter>(
86		key: &KArg,
87		hash_fns: Self::HArg,
88	) -> Vec<u8> {
89		(hash_fns.0)(&key.to_encoded_iter().next().expect("should have at least one element!"))
90	}
91}
92
93impl<H: StorageHasher, K: FullCodec + MaxEncodedLen + StaticTypeInfo> KeyGeneratorMaxEncodedLen
94	for Key<H, K>
95{
96	fn key_max_encoded_len() -> usize {
97		H::max_len::<K>()
98	}
99}
100
101impl<H: StorageHasher, K: FullCodec + StaticTypeInfo> KeyGeneratorInner for Key<H, K> {
102	type Hasher = H;
103
104	fn final_hash(encoded: &[u8]) -> Vec<u8> {
105		H::hash(encoded).as_ref().to_vec()
106	}
107}
108
109#[impl_trait_for_tuples::impl_for_tuples(1, 18)]
110#[tuple_types_custom_trait_bound(KeyGeneratorInner)]
111impl KeyGenerator for Tuple {
112	for_tuples!( type Key = ( #(Tuple::Key),* ); );
113	for_tuples!( type KArg = ( #(Tuple::Key),* ); );
114	for_tuples!( type HArg = ( #(Tuple::HashFn),* ); );
115	type HashFn = Box<dyn FnOnce(&[u8]) -> Vec<u8>>;
116
117	const HASHER_METADATA: &'static [sp_metadata_ir::StorageHasherIR] =
118		&[for_tuples!( #(Tuple::Hasher::METADATA),* )];
119
120	fn final_key<KArg: EncodeLikeTuple<Self::KArg> + TupleToEncodedIter>(key: KArg) -> Vec<u8> {
121		let mut final_key = Vec::new();
122		let mut iter = key.to_encoded_iter();
123		for_tuples!(
124			#(
125				let next_encoded = iter.next().expect("KArg number should be equal to Key number");
126				final_key.extend_from_slice(&Tuple::final_hash(&next_encoded));
127			)*
128		);
129		final_key
130	}
131
132	fn migrate_key<KArg: EncodeLikeTuple<Self::KArg> + TupleToEncodedIter>(
133		key: &KArg,
134		hash_fns: Self::HArg,
135	) -> Vec<u8> {
136		let mut migrated_key = Vec::new();
137		let mut iter = key.to_encoded_iter();
138		for_tuples!(
139			#(
140				let next_encoded = iter.next().expect("KArg number should be equal to Key number");
141				migrated_key.extend_from_slice(&(hash_fns.Tuple)(&next_encoded));
142			)*
143		);
144		migrated_key
145	}
146}
147
148#[impl_trait_for_tuples::impl_for_tuples(1, 18)]
149#[tuple_types_custom_trait_bound(KeyGeneratorInner + KeyGeneratorMaxEncodedLen)]
150impl KeyGeneratorMaxEncodedLen for Tuple {
151	fn key_max_encoded_len() -> usize {
152		let mut len = 0usize;
153		for_tuples!(
154			#(
155				len = len.saturating_add(Tuple::key_max_encoded_len());
156			)*
157		);
158		len
159	}
160}
161
162/// Marker trait to indicate that each element in the tuple encodes like the corresponding element
163/// in another tuple.
164///
165/// This trait is sealed.
166pub trait EncodeLikeTuple<T>: crate::storage::private::Sealed {}
167
168macro_rules! impl_encode_like_tuples {
169	($($elem:ident),+) => {
170		paste! {
171			impl<$($elem: Encode,)+ $([<$elem $elem>]: Encode + EncodeLike<$elem>,)+>
172				EncodeLikeTuple<($($elem,)+)> for
173				($([<$elem $elem>],)+) {}
174			impl<$($elem: Encode,)+ $([<$elem $elem>]: Encode + EncodeLike<$elem>,)+>
175				EncodeLikeTuple<($($elem,)+)> for
176				&($([<$elem $elem>],)+) {}
177		}
178	};
179}
180
181impl_encode_like_tuples!(A);
182impl_encode_like_tuples!(A, B);
183impl_encode_like_tuples!(A, B, C);
184impl_encode_like_tuples!(A, B, C, D);
185impl_encode_like_tuples!(A, B, C, D, E);
186impl_encode_like_tuples!(A, B, C, D, E, F);
187impl_encode_like_tuples!(A, B, C, D, E, F, G);
188impl_encode_like_tuples!(A, B, C, D, E, F, G, H);
189impl_encode_like_tuples!(A, B, C, D, E, F, G, H, I);
190impl_encode_like_tuples!(A, B, C, D, E, F, G, H, I, J);
191impl_encode_like_tuples!(A, B, C, D, E, F, G, H, I, J, K);
192impl_encode_like_tuples!(A, B, C, D, E, F, G, H, I, J, K, L);
193impl_encode_like_tuples!(A, B, C, D, E, F, G, H, I, J, K, L, M);
194impl_encode_like_tuples!(A, B, C, D, E, F, G, H, I, J, K, L, M, O);
195impl_encode_like_tuples!(A, B, C, D, E, F, G, H, I, J, K, L, M, O, P);
196impl_encode_like_tuples!(A, B, C, D, E, F, G, H, I, J, K, L, M, O, P, Q);
197impl_encode_like_tuples!(A, B, C, D, E, F, G, H, I, J, K, L, M, O, P, Q, R);
198
199impl<'a, T: EncodeLike<U> + EncodeLikeTuple<U>, U: Encode> EncodeLikeTuple<U>
200	for codec::Ref<'a, T, U>
201{
202}
203
204/// Trait to indicate that a tuple can be converted into an iterator of a vector of encoded bytes.
205pub trait TupleToEncodedIter {
206	fn to_encoded_iter(&self) -> alloc::vec::IntoIter<Vec<u8>>;
207}
208
209#[impl_trait_for_tuples::impl_for_tuples(1, 18)]
210#[tuple_types_custom_trait_bound(Encode)]
211impl TupleToEncodedIter for Tuple {
212	fn to_encoded_iter(&self) -> alloc::vec::IntoIter<Vec<u8>> {
213		[for_tuples!( #(self.Tuple.encode()),* )].to_vec().into_iter()
214	}
215}
216
217impl<T: TupleToEncodedIter> TupleToEncodedIter for &T {
218	fn to_encoded_iter(&self) -> alloc::vec::IntoIter<Vec<u8>> {
219		(*self).to_encoded_iter()
220	}
221}
222
223impl<'a, T: EncodeLike<U> + TupleToEncodedIter, U: Encode> TupleToEncodedIter
224	for codec::Ref<'a, T, U>
225{
226	fn to_encoded_iter(&self) -> alloc::vec::IntoIter<Vec<u8>> {
227		use core::ops::Deref as _;
228		self.deref().to_encoded_iter()
229	}
230}
231
232/// A trait that indicates the hashers for the keys generated are all reversible.
233pub trait ReversibleKeyGenerator: KeyGenerator {
234	type ReversibleHasher;
235	fn decode_final_key(key_material: &[u8]) -> Result<(Self::Key, &[u8]), codec::Error>;
236}
237
238impl<H: ReversibleStorageHasher, K: FullCodec + StaticTypeInfo> ReversibleKeyGenerator
239	for Key<H, K>
240{
241	type ReversibleHasher = H;
242
243	fn decode_final_key(key_material: &[u8]) -> Result<(Self::Key, &[u8]), codec::Error> {
244		let mut current_key_material = Self::ReversibleHasher::reverse(key_material);
245		let key = K::decode(&mut current_key_material)?;
246		Ok((key, current_key_material))
247	}
248}
249
250#[impl_trait_for_tuples::impl_for_tuples(2, 18)]
251#[tuple_types_custom_trait_bound(ReversibleKeyGenerator + KeyGeneratorInner)]
252impl ReversibleKeyGenerator for Tuple {
253	for_tuples!( type ReversibleHasher = ( #(Tuple::ReversibleHasher),* ); );
254
255	fn decode_final_key(key_material: &[u8]) -> Result<(Self::Key, &[u8]), codec::Error> {
256		let mut current_key_material = key_material;
257		Ok((
258			(for_tuples! {
259				#({
260					let (key, material) = Tuple::decode_final_key(current_key_material)?;
261					current_key_material = material;
262					key
263				}),*
264			}),
265			current_key_material,
266		))
267	}
268}
269
270/// Trait indicating whether a KeyGenerator has the prefix P.
271pub trait HasKeyPrefix<P>: KeyGenerator {
272	type Suffix;
273
274	fn partial_key(prefix: P) -> Vec<u8>;
275}
276
277/// Trait indicating whether a ReversibleKeyGenerator has the prefix P.
278pub trait HasReversibleKeyPrefix<P>: ReversibleKeyGenerator + HasKeyPrefix<P> {
279	fn decode_partial_key(key_material: &[u8]) -> Result<Self::Suffix, codec::Error>;
280}
281
282frame_support_procedural::impl_key_prefix_for_tuples!();
frame_support/storage/types/key.rs

frame_support/storage/types/
key.rs
