bounded_collections/
weak_bounded_vec.rs

1// This file is part of Substrate.
2
3// Copyright (C) 2017-2023 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//! Traits, types and structs to support putting a bounded vector into storage, as a raw value, map
19//! or a double map.
20
21use super::{BoundedSlice, BoundedVec};
22use crate::Get;
23use alloc::vec::Vec;
24use codec::{Decode, Encode, MaxEncodedLen};
25use core::{
26	marker::PhantomData,
27	ops::{Deref, Index, IndexMut},
28	slice::SliceIndex,
29};
30#[cfg(feature = "serde")]
31use serde::{
32	de::{Error, SeqAccess, Visitor},
33	Deserialize, Deserializer, Serialize,
34};
35
36/// A weakly bounded vector.
37///
38/// It has implementations for efficient append and length decoding, as with a normal `Vec<_>`, once
39/// put into storage as a raw value, map or double-map.
40///
41/// The length of the vec is not strictly bounded. Decoding a vec with more element that the bound
42/// is accepted, and some method allow to bypass the restriction with warnings.
43#[cfg_attr(feature = "serde", derive(Serialize), serde(transparent))]
44#[derive(Encode, scale_info::TypeInfo)]
45#[scale_info(skip_type_params(S))]
46pub struct WeakBoundedVec<T, S>(
47	pub(super) Vec<T>,
48	#[cfg_attr(feature = "serde", serde(skip_serializing))] PhantomData<S>,
49);
50
51#[cfg(feature = "serde")]
52impl<'de, T, S: Get<u32>> Deserialize<'de> for WeakBoundedVec<T, S>
53where
54	T: Deserialize<'de>,
55{
56	fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
57	where
58		D: Deserializer<'de>,
59	{
60		struct VecVisitor<T, S: Get<u32>>(PhantomData<(T, S)>);
61
62		impl<'de, T, S: Get<u32>> Visitor<'de> for VecVisitor<T, S>
63		where
64			T: Deserialize<'de>,
65		{
66			type Value = Vec<T>;
67
68			fn expecting(&self, formatter: &mut alloc::fmt::Formatter) -> alloc::fmt::Result {
69				formatter.write_str("a sequence")
70			}
71
72			fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
73			where
74				A: SeqAccess<'de>,
75			{
76				let size = seq.size_hint().unwrap_or(0);
77				let max = match usize::try_from(S::get()) {
78					Ok(n) => n,
79					Err(_) => return Err(A::Error::custom("can't convert to usize")),
80				};
81				if size > max {
82					log::warn!(
83						target: "runtime",
84						"length of a bounded vector while deserializing is not respected.",
85					);
86				}
87				let mut values = Vec::with_capacity(size);
88
89				while let Some(value) = seq.next_element()? {
90					values.push(value);
91					if values.len() > max {
92						log::warn!(
93							target: "runtime",
94							"length of a bounded vector while deserializing is not respected.",
95						);
96					}
97				}
98
99				Ok(values)
100			}
101		}
102
103		let visitor: VecVisitor<T, S> = VecVisitor(PhantomData);
104		deserializer
105			.deserialize_seq(visitor)
106			.map(|v| WeakBoundedVec::<T, S>::try_from(v).map_err(|_| Error::custom("out of bounds")))?
107	}
108}
109
110impl<T: Decode, S: Get<u32>> Decode for WeakBoundedVec<T, S> {
111	fn decode<I: codec::Input>(input: &mut I) -> Result<Self, codec::Error> {
112		let inner = Vec::<T>::decode(input)?;
113		Ok(Self::force_from(inner, Some("decode")))
114	}
115
116	fn skip<I: codec::Input>(input: &mut I) -> Result<(), codec::Error> {
117		Vec::<T>::skip(input)
118	}
119}
120
121impl<T, S> WeakBoundedVec<T, S> {
122	/// Create `Self` from `t` without any checks.
123	fn unchecked_from(t: Vec<T>) -> Self {
124		Self(t, Default::default())
125	}
126
127	/// Consume self, and return the inner `Vec`. Henceforth, the `Vec<_>` can be altered in an
128	/// arbitrary way. At some point, if the reverse conversion is required, `TryFrom<Vec<_>>` can
129	/// be used.
130	///
131	/// This is useful for cases if you need access to an internal API of the inner `Vec<_>` which
132	/// is not provided by the wrapper `WeakBoundedVec`.
133	pub fn into_inner(self) -> Vec<T> {
134		self.0
135	}
136
137	/// Exactly the same semantics as [`Vec::remove`].
138	///
139	/// # Panics
140	///
141	/// Panics if `index` is out of bounds.
142	pub fn remove(&mut self, index: usize) -> T {
143		self.0.remove(index)
144	}
145
146	/// Exactly the same semantics as [`Vec::swap_remove`].
147	///
148	/// # Panics
149	///
150	/// Panics if `index` is out of bounds.
151	pub fn swap_remove(&mut self, index: usize) -> T {
152		self.0.swap_remove(index)
153	}
154
155	/// Exactly the same semantics as [`Vec::retain`].
156	pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F) {
157		self.0.retain(f)
158	}
159
160	/// Exactly the same semantics as [`slice::get_mut`].
161	pub fn get_mut<I: SliceIndex<[T]>>(&mut self, index: I) -> Option<&mut <I as SliceIndex<[T]>>::Output> {
162		self.0.get_mut(index)
163	}
164}
165
166impl<T, S: Get<u32>> WeakBoundedVec<T, S> {
167	/// Get the bound of the type in `usize`.
168	pub fn bound() -> usize {
169		S::get() as usize
170	}
171
172	/// Create `Self` from `t` without any checks. Logs warnings if the bound is not being
173	/// respected. The additional scope can be used to indicate where a potential overflow is
174	/// happening.
175	pub fn force_from(t: Vec<T>, scope: Option<&'static str>) -> Self {
176		if t.len() > Self::bound() {
177			log::warn!(
178				target: "runtime",
179				"length of a bounded vector in scope {} is not respected.",
180				scope.unwrap_or("UNKNOWN"),
181			);
182		}
183
184		Self::unchecked_from(t)
185	}
186
187	/// Consumes self and mutates self via the given `mutate` function.
188	///
189	/// If the outcome of mutation is within bounds, `Some(Self)` is returned. Else, `None` is
190	/// returned.
191	///
192	/// This is essentially a *consuming* shorthand [`Self::into_inner`] -> `...` ->
193	/// [`Self::try_from`].
194	pub fn try_mutate(mut self, mut mutate: impl FnMut(&mut Vec<T>)) -> Option<Self> {
195		mutate(&mut self.0);
196		(self.0.len() <= Self::bound()).then(move || self)
197	}
198
199	/// Exactly the same semantics as [`Vec::insert`], but returns an `Err` (and is a noop) if the
200	/// new length of the vector exceeds `S`.
201	///
202	/// # Panics
203	///
204	/// Panics if `index > len`.
205	pub fn try_insert(&mut self, index: usize, element: T) -> Result<(), ()> {
206		if self.len() < Self::bound() {
207			self.0.insert(index, element);
208			Ok(())
209		} else {
210			Err(())
211		}
212	}
213
214	/// Exactly the same semantics as [`Vec::push`], but returns an `Err` (and is a noop) if the
215	/// new length of the vector exceeds `S`.
216	///
217	/// # Panics
218	///
219	/// Panics if the new capacity exceeds isize::MAX bytes.
220	pub fn try_push(&mut self, element: T) -> Result<(), ()> {
221		if self.len() < Self::bound() {
222			self.0.push(element);
223			Ok(())
224		} else {
225			Err(())
226		}
227	}
228}
229
230impl<T, S> Default for WeakBoundedVec<T, S> {
231	fn default() -> Self {
232		// the bound cannot be below 0, which is satisfied by an empty vector
233		Self::unchecked_from(Vec::default())
234	}
235}
236
237impl<T, S> core::fmt::Debug for WeakBoundedVec<T, S>
238where
239	Vec<T>: core::fmt::Debug,
240	S: Get<u32>,
241{
242	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
243		f.debug_tuple("WeakBoundedVec").field(&self.0).field(&Self::bound()).finish()
244	}
245}
246
247impl<T, S> Clone for WeakBoundedVec<T, S>
248where
249	T: Clone,
250{
251	fn clone(&self) -> Self {
252		// bound is retained
253		Self::unchecked_from(self.0.clone())
254	}
255}
256
257impl<T, S: Get<u32>> TryFrom<Vec<T>> for WeakBoundedVec<T, S> {
258	type Error = ();
259	fn try_from(t: Vec<T>) -> Result<Self, Self::Error> {
260		if t.len() <= Self::bound() {
261			// explicit check just above
262			Ok(Self::unchecked_from(t))
263		} else {
264			Err(())
265		}
266	}
267}
268
269// It is okay to give a non-mutable reference of the inner vec to anyone.
270impl<T, S> AsRef<Vec<T>> for WeakBoundedVec<T, S> {
271	fn as_ref(&self) -> &Vec<T> {
272		&self.0
273	}
274}
275
276impl<T, S> AsRef<[T]> for WeakBoundedVec<T, S> {
277	fn as_ref(&self) -> &[T] {
278		&self.0
279	}
280}
281
282impl<T, S> AsMut<[T]> for WeakBoundedVec<T, S> {
283	fn as_mut(&mut self) -> &mut [T] {
284		&mut self.0
285	}
286}
287
288// will allow for immutable all operations of `Vec<T>` on `WeakBoundedVec<T>`.
289impl<T, S> Deref for WeakBoundedVec<T, S> {
290	type Target = Vec<T>;
291
292	fn deref(&self) -> &Self::Target {
293		&self.0
294	}
295}
296
297// Allows for indexing similar to a normal `Vec`. Can panic if out of bound.
298impl<T, S, I> Index<I> for WeakBoundedVec<T, S>
299where
300	I: SliceIndex<[T]>,
301{
302	type Output = I::Output;
303
304	#[inline]
305	fn index(&self, index: I) -> &Self::Output {
306		self.0.index(index)
307	}
308}
309
310impl<T, S, I> IndexMut<I> for WeakBoundedVec<T, S>
311where
312	I: SliceIndex<[T]>,
313{
314	#[inline]
315	fn index_mut(&mut self, index: I) -> &mut Self::Output {
316		self.0.index_mut(index)
317	}
318}
319
320impl<T, S> core::iter::IntoIterator for WeakBoundedVec<T, S> {
321	type Item = T;
322	type IntoIter = alloc::vec::IntoIter<T>;
323	fn into_iter(self) -> Self::IntoIter {
324		self.0.into_iter()
325	}
326}
327
328impl<'a, T, S> core::iter::IntoIterator for &'a WeakBoundedVec<T, S> {
329	type Item = &'a T;
330	type IntoIter = core::slice::Iter<'a, T>;
331	fn into_iter(self) -> Self::IntoIter {
332		self.0.iter()
333	}
334}
335
336impl<'a, T, S> core::iter::IntoIterator for &'a mut WeakBoundedVec<T, S> {
337	type Item = &'a mut T;
338	type IntoIter = core::slice::IterMut<'a, T>;
339	fn into_iter(self) -> Self::IntoIter {
340		self.0.iter_mut()
341	}
342}
343
344impl<T, S> codec::DecodeLength for WeakBoundedVec<T, S> {
345	fn len(self_encoded: &[u8]) -> Result<usize, codec::Error> {
346		// `WeakBoundedVec<T, _>` stored just a `Vec<T>`, thus the length is at the beginning in
347		// `Compact` form, and same implementation as `Vec<T>` can be used.
348		<Vec<T> as codec::DecodeLength>::len(self_encoded)
349	}
350}
351
352impl<T, BoundSelf, BoundRhs> PartialEq<WeakBoundedVec<T, BoundRhs>> for WeakBoundedVec<T, BoundSelf>
353where
354	T: PartialEq,
355	BoundSelf: Get<u32>,
356	BoundRhs: Get<u32>,
357{
358	fn eq(&self, rhs: &WeakBoundedVec<T, BoundRhs>) -> bool {
359		self.0 == rhs.0
360	}
361}
362
363impl<T, BoundSelf, BoundRhs> PartialEq<BoundedVec<T, BoundRhs>> for WeakBoundedVec<T, BoundSelf>
364where
365	T: PartialEq,
366	BoundSelf: Get<u32>,
367	BoundRhs: Get<u32>,
368{
369	fn eq(&self, rhs: &BoundedVec<T, BoundRhs>) -> bool {
370		self.0 == rhs.0
371	}
372}
373
374impl<'a, T, BoundSelf, BoundRhs> PartialEq<BoundedSlice<'a, T, BoundRhs>> for WeakBoundedVec<T, BoundSelf>
375where
376	T: PartialEq,
377	BoundSelf: Get<u32>,
378	BoundRhs: Get<u32>,
379{
380	fn eq(&self, rhs: &BoundedSlice<'a, T, BoundRhs>) -> bool {
381		self.0 == rhs.0
382	}
383}
384
385impl<T: PartialEq, S: Get<u32>> PartialEq<Vec<T>> for WeakBoundedVec<T, S> {
386	fn eq(&self, other: &Vec<T>) -> bool {
387		&self.0 == other
388	}
389}
390
391impl<T, S: Get<u32>> Eq for WeakBoundedVec<T, S> where T: Eq {}
392
393impl<T, BoundSelf, BoundRhs> PartialOrd<WeakBoundedVec<T, BoundRhs>> for WeakBoundedVec<T, BoundSelf>
394where
395	T: PartialOrd,
396	BoundSelf: Get<u32>,
397	BoundRhs: Get<u32>,
398{
399	fn partial_cmp(&self, other: &WeakBoundedVec<T, BoundRhs>) -> Option<core::cmp::Ordering> {
400		self.0.partial_cmp(&other.0)
401	}
402}
403
404impl<T, BoundSelf, BoundRhs> PartialOrd<BoundedVec<T, BoundRhs>> for WeakBoundedVec<T, BoundSelf>
405where
406	T: PartialOrd,
407	BoundSelf: Get<u32>,
408	BoundRhs: Get<u32>,
409{
410	fn partial_cmp(&self, other: &BoundedVec<T, BoundRhs>) -> Option<core::cmp::Ordering> {
411		self.0.partial_cmp(&other.0)
412	}
413}
414
415impl<'a, T, BoundSelf, BoundRhs> PartialOrd<BoundedSlice<'a, T, BoundRhs>> for WeakBoundedVec<T, BoundSelf>
416where
417	T: PartialOrd,
418	BoundSelf: Get<u32>,
419	BoundRhs: Get<u32>,
420{
421	fn partial_cmp(&self, other: &BoundedSlice<'a, T, BoundRhs>) -> Option<core::cmp::Ordering> {
422		(&*self.0).partial_cmp(other.0)
423	}
424}
425
426impl<T: Ord, S: Get<u32>> Ord for WeakBoundedVec<T, S> {
427	fn cmp(&self, other: &Self) -> core::cmp::Ordering {
428		self.0.cmp(&other.0)
429	}
430}
431
432impl<T, S> MaxEncodedLen for WeakBoundedVec<T, S>
433where
434	T: MaxEncodedLen,
435	S: Get<u32>,
436	WeakBoundedVec<T, S>: Encode,
437{
438	fn max_encoded_len() -> usize {
439		// WeakBoundedVec<T, S> encodes like Vec<T> which encodes like [T], which is a compact u32
440		// plus each item in the slice:
441		// See: https://docs.substrate.io/reference/scale-codec/
442		codec::Compact(S::get())
443			.encoded_size()
444			.saturating_add(Self::bound().saturating_mul(T::max_encoded_len()))
445	}
446}
447
448#[cfg(test)]
449mod test {
450	use super::*;
451	use crate::ConstU32;
452	use alloc::vec;
453
454	#[test]
455	fn bound_returns_correct_value() {
456		assert_eq!(WeakBoundedVec::<u32, ConstU32<7>>::bound(), 7);
457	}
458
459	#[test]
460	fn try_insert_works() {
461		let mut bounded: WeakBoundedVec<u32, ConstU32<4>> = vec![1, 2, 3].try_into().unwrap();
462		bounded.try_insert(1, 0).unwrap();
463		assert_eq!(*bounded, vec![1, 0, 2, 3]);
464
465		assert!(bounded.try_insert(0, 9).is_err());
466		assert_eq!(*bounded, vec![1, 0, 2, 3]);
467	}
468
469	#[test]
470	#[should_panic(expected = "insertion index (is 9) should be <= len (is 3)")]
471	fn try_inert_panics_if_oob() {
472		let mut bounded: WeakBoundedVec<u32, ConstU32<4>> = vec![1, 2, 3].try_into().unwrap();
473		bounded.try_insert(9, 0).unwrap();
474	}
475
476	#[test]
477	fn try_push_works() {
478		let mut bounded: WeakBoundedVec<u32, ConstU32<4>> = vec![1, 2, 3].try_into().unwrap();
479		bounded.try_push(0).unwrap();
480		assert_eq!(*bounded, vec![1, 2, 3, 0]);
481
482		assert!(bounded.try_push(9).is_err());
483	}
484
485	#[test]
486	fn deref_coercion_works() {
487		let bounded: WeakBoundedVec<u32, ConstU32<7>> = vec![1, 2, 3].try_into().unwrap();
488		// these methods come from deref-ed vec.
489		assert_eq!(bounded.len(), 3);
490		assert!(bounded.iter().next().is_some());
491		assert!(!bounded.is_empty());
492	}
493
494	#[test]
495	fn try_mutate_works() {
496		let bounded: WeakBoundedVec<u32, ConstU32<7>> = vec![1, 2, 3, 4, 5, 6].try_into().unwrap();
497		let bounded = bounded.try_mutate(|v| v.push(7)).unwrap();
498		assert_eq!(bounded.len(), 7);
499		assert!(bounded.try_mutate(|v| v.push(8)).is_none());
500	}
501
502	#[test]
503	fn slice_indexing_works() {
504		let bounded: WeakBoundedVec<u32, ConstU32<7>> = vec![1, 2, 3, 4, 5, 6].try_into().unwrap();
505		assert_eq!(&bounded[0..=2], &[1, 2, 3]);
506	}
507
508	#[test]
509	fn vec_eq_works() {
510		let bounded: WeakBoundedVec<u32, ConstU32<7>> = vec![1, 2, 3, 4, 5, 6].try_into().unwrap();
511		assert_eq!(bounded, vec![1, 2, 3, 4, 5, 6]);
512	}
513
514	#[test]
515	fn too_big_succeed_to_decode() {
516		let v: Vec<u32> = vec![1, 2, 3, 4, 5];
517		let w = WeakBoundedVec::<u32, ConstU32<4>>::decode(&mut &v.encode()[..]).unwrap();
518		assert_eq!(v, *w);
519	}
520}
bounded_collections/weak_bounded_vec.rs

bounded_collections/
weak_bounded_vec.rs
