parity_scale_codec/
encode_append.rs

1// Copyright 2019 Parity Technologies
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use core::iter::ExactSizeIterator;
16
17use crate::alloc::vec::Vec;
18use crate::{Encode, Decode, Error};
19use crate::compact::{Compact, CompactLen};
20use crate::encode_like::EncodeLike;
21
22/// Trait that allows to append items to an encoded representation without
23/// decoding all previous added items.
24pub trait EncodeAppend {
25	/// The item that will be appended.
26	type Item: Encode;
27
28	/// Append all items in `iter` to the given `self_encoded` representation
29	/// or if `self_encoded` value is empty, `iter` is encoded to the `Self` representation.
30	///
31	/// # Example
32	///
33	/// ```
34	///# use parity_scale_codec::EncodeAppend;
35	///
36	/// // Some encoded data
37	/// let data = Vec::new();
38	///
39	/// let item = 8u32;
40	/// let encoded = <Vec<u32> as EncodeAppend>::append_or_new(data, std::iter::once(&item)).expect("Adds new element");
41	///
42	/// // Add multiple element
43	/// <Vec<u32> as EncodeAppend>::append_or_new(encoded, &[700u32, 800u32, 10u32]).expect("Adds new elements");
44	/// ```
45	fn append_or_new<EncodeLikeItem, I>(
46		self_encoded: Vec<u8>,
47		iter: I,
48	) -> Result<Vec<u8>, Error>
49	where
50		I: IntoIterator<Item = EncodeLikeItem>,
51		EncodeLikeItem: EncodeLike<Self::Item>,
52		I::IntoIter: ExactSizeIterator;
53}
54
55impl<T: Encode> EncodeAppend for Vec<T> {
56	type Item = T;
57
58	fn append_or_new<EncodeLikeItem, I>(
59		self_encoded: Vec<u8>,
60		iter: I,
61	) -> Result<Vec<u8>, Error>
62	where
63		I: IntoIterator<Item = EncodeLikeItem>,
64		EncodeLikeItem: EncodeLike<Self::Item>,
65		I::IntoIter: ExactSizeIterator,
66	{
67		append_or_new_impl(self_encoded, iter)
68	}
69}
70
71impl<T: Encode> EncodeAppend for crate::alloc::collections::VecDeque<T> {
72	type Item = T;
73
74	fn append_or_new<EncodeLikeItem, I>(
75		self_encoded: Vec<u8>,
76		iter: I,
77	) -> Result<Vec<u8>, Error>
78	where
79		I: IntoIterator<Item = EncodeLikeItem>,
80		EncodeLikeItem: EncodeLike<Self::Item>,
81		I::IntoIter: ExactSizeIterator,
82	{
83		append_or_new_impl(self_encoded, iter)
84	}
85}
86
87/// Extends a SCALE-encoded vector with elements from the given `iter`.
88///
89/// `vec` must either be empty, or contain a valid SCALE-encoded `Vec<Item>` payload.
90fn append_or_new_impl<Item, I>(
91	mut vec: Vec<u8>,
92	iter: I,
93) -> Result<Vec<u8>, Error>
94where
95	Item: Encode,
96	I: IntoIterator<Item = Item>,
97	I::IntoIter: ExactSizeIterator,
98{
99	let iter = iter.into_iter();
100	let items_to_append = iter.len();
101
102	if vec.is_empty() {
103		crate::codec::compact_encode_len_to(&mut vec, items_to_append)?;
104	} else {
105		let old_item_count = u32::from(Compact::<u32>::decode(&mut &vec[..])?);
106		let new_item_count = old_item_count
107			.checked_add(items_to_append as u32)
108			.ok_or("cannot append new items into a SCALE-encoded vector: length overflow due to too many items")?;
109
110		let old_item_count_encoded_bytesize = Compact::<u32>::compact_len(&old_item_count);
111		let new_item_count_encoded_bytesize = Compact::<u32>::compact_len(&new_item_count);
112
113		if old_item_count_encoded_bytesize == new_item_count_encoded_bytesize {
114			// The size of the length as encoded by SCALE didn't change, so we can just
115			// keep the old buffer as-is. We just need to update the length prefix.
116			Compact(new_item_count).using_encoded(|length_encoded|
117				vec[..old_item_count_encoded_bytesize].copy_from_slice(length_encoded)
118			);
119		} else {
120			// We can't update the length as the new length prefix will take up more
121			// space when encoded, so we need to move our data to make space for it.
122
123			// If this overflows then it means that `vec` is bigger that half of the
124			// total address space, which means that it will be impossible to allocate
125			// enough memory for another vector of at least the same size.
126			//
127			// So let's just immediately bail with an error if this happens.
128			let new_capacity = vec.len().checked_mul(2)
129				.ok_or("cannot append new items into a SCALE-encoded vector: new vector won't fit in memory")?;
130			let mut new_vec = Vec::with_capacity(new_capacity);
131
132			crate::codec::compact_encode_len_to(&mut new_vec, new_item_count as usize)?;
133			new_vec.extend_from_slice(&vec[old_item_count_encoded_bytesize..]);
134			vec = new_vec;
135		}
136	}
137
138	// And now we just need to append the new items.
139	iter.for_each(|e| e.encode_to(&mut vec));
140	Ok(vec)
141}
142
143#[cfg(test)]
144mod tests {
145	use super::*;
146	use crate::{Input, Encode, EncodeLike};
147	use std::collections::VecDeque;
148
149	const TEST_VALUE: u32 = {
150		#[cfg(not(miri))]
151		{ 1_000_000 }
152		#[cfg(miri)]
153		{ 1_000 }
154	};
155
156	#[test]
157	fn vec_encode_append_works() {
158		let encoded = (0..TEST_VALUE).fold(Vec::new(), |encoded, v| {
159			<Vec<u32> as EncodeAppend>::append_or_new(encoded, std::iter::once(&v)).unwrap()
160		});
161
162		let decoded = Vec::<u32>::decode(&mut &encoded[..]).unwrap();
163		assert_eq!(decoded, (0..TEST_VALUE).collect::<Vec<_>>());
164	}
165
166	#[test]
167	fn vec_encode_append_multiple_items_works() {
168		let encoded = (0..TEST_VALUE).fold(Vec::new(), |encoded, v| {
169			<Vec<u32> as EncodeAppend>::append_or_new(encoded, &[v, v, v, v]).unwrap()
170		});
171
172		let decoded = Vec::<u32>::decode(&mut &encoded[..]).unwrap();
173		let expected = (0..TEST_VALUE).fold(Vec::new(), |mut vec, i| {
174			vec.append(&mut vec![i, i, i, i]);
175			vec
176		});
177		assert_eq!(decoded, expected);
178	}
179
180	#[test]
181	fn vecdeque_encode_append_works() {
182		let encoded = (0..TEST_VALUE).fold(Vec::new(), |encoded, v| {
183			<VecDeque<u32> as EncodeAppend>::append_or_new(encoded, std::iter::once(&v)).unwrap()
184		});
185
186		let decoded = VecDeque::<u32>::decode(&mut &encoded[..]).unwrap();
187		assert_eq!(decoded, (0..TEST_VALUE).collect::<Vec<_>>());
188	}
189
190	#[test]
191	fn vecdeque_encode_append_multiple_items_works() {
192		let encoded = (0..TEST_VALUE).fold(Vec::new(), |encoded, v| {
193			<VecDeque<u32> as EncodeAppend>::append_or_new(encoded, &[v, v, v, v]).unwrap()
194		});
195
196		let decoded = VecDeque::<u32>::decode(&mut &encoded[..]).unwrap();
197		let expected = (0..TEST_VALUE).fold(Vec::new(), |mut vec, i| {
198			vec.append(&mut vec![i, i, i, i]);
199			vec
200		});
201		assert_eq!(decoded, expected);
202	}
203
204	#[test]
205	fn append_non_copyable() {
206		#[derive(Eq, PartialEq, Debug)]
207		struct NoCopy { data: u32 }
208
209		impl EncodeLike for NoCopy {}
210
211		impl Encode for NoCopy {
212			fn encode(&self) -> Vec<u8> {
213				self.data.encode()
214			}
215		}
216
217		impl Decode for NoCopy {
218			fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
219				u32::decode(input).map(|data| Self { data })
220			}
221		}
222
223		let append = NoCopy { data: 100 };
224		let data = Vec::new();
225		let encoded = <Vec<NoCopy> as EncodeAppend>::append_or_new(data, std::iter::once(&append)).unwrap();
226
227		let decoded = <Vec<NoCopy>>::decode(&mut &encoded[..]).unwrap();
228		assert_eq!(vec![append], decoded);
229	}
230
231	#[test]
232	fn vec_encode_like_append_works() {
233		let encoded = (0..TEST_VALUE).fold(Vec::new(), |encoded, v| {
234			<Vec<u32> as EncodeAppend>::append_or_new(encoded, std::iter::once(Box::new(v as u32))).unwrap()
235		});
236
237		let decoded = Vec::<u32>::decode(&mut &encoded[..]).unwrap();
238		assert_eq!(decoded, (0..TEST_VALUE).collect::<Vec<_>>());
239	}
240}
parity_scale_codec/encode_append.rs

parity_scale_codec/
encode_append.rs
