b3_stable_structures/
storable.rs

1use std::borrow::{Borrow, Cow};
2use std::cmp::{Ordering, Reverse};
3use std::convert::{TryFrom, TryInto};
4use std::fmt;
5
6#[cfg(test)]
7mod tests;
8
9/// A trait with convenience methods for storing an element into a stable structure.
10pub trait Storable {
11    /// Converts an element into bytes.
12    ///
13    /// NOTE: `Cow` is used here to avoid unnecessary cloning.
14    fn to_bytes(&self) -> Cow<[u8]>;
15
16    /// Converts bytes into an element.
17    fn from_bytes(bytes: Cow<[u8]>) -> Self;
18}
19
20/// A trait indicating that a `Storable` element is bounded in size.
21pub trait BoundedStorable: Storable {
22    /// The maximum size, in bytes, of the type when serialized.
23    const MAX_SIZE: u32;
24
25    /// True if all the values of this type have fixed-width encoding.
26    /// Some data structures, such as stable vector, can take
27    /// advantage of fixed size to avoid storing an explicit entry
28    /// size.
29    ///
30    /// Examples: little-/big-endian encoding of u16/u32/u64, tuples
31    /// and arrays of fixed-size types.
32    const IS_FIXED_SIZE: bool;
33}
34
35/// Variable-size, but limited in capacity byte array.
36#[derive(Eq, Copy, Clone)]
37pub struct Blob<const N: usize> {
38    storage: [u8; N],
39    size: u32,
40}
41
42impl<const N: usize> Blob<N> {
43    /// Returns the contents of this array as a byte slice.
44    pub fn as_slice(&self) -> &[u8] {
45        &self.storage[0..self.len()]
46    }
47
48    /// Returns true if the array is empty.
49    pub fn is_empty(&self) -> bool {
50        self.len() == 0
51    }
52
53    /// Returns the actual length of this array.
54    pub fn len(&self) -> usize {
55        self.size as usize
56    }
57}
58
59impl<const N: usize> Default for Blob<N> {
60    fn default() -> Self {
61        Self {
62            storage: [0; N],
63            size: 0,
64        }
65    }
66}
67
68#[derive(Debug)]
69pub struct TryFromSliceError;
70
71impl<const N: usize> TryFrom<&[u8]> for Blob<N> {
72    type Error = TryFromSliceError;
73
74    fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
75        if value.len() > N {
76            return Err(TryFromSliceError);
77        }
78        let mut result = Self::default();
79        result.storage[0..value.len()].copy_from_slice(value);
80        result.size = value.len() as u32;
81        Ok(result)
82    }
83}
84
85impl<const N: usize> AsRef<[u8]> for Blob<N> {
86    fn as_ref(&self) -> &[u8] {
87        self.as_slice()
88    }
89}
90
91impl<const N: usize> PartialEq for Blob<N> {
92    fn eq(&self, other: &Self) -> bool {
93        self.as_slice().eq(other.as_slice())
94    }
95}
96
97impl<const N: usize> PartialOrd for Blob<N> {
98    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
99        self.as_slice().partial_cmp(other.as_slice())
100    }
101}
102
103impl<const N: usize> Ord for Blob<N> {
104    fn cmp(&self, other: &Self) -> Ordering {
105        self.as_slice().cmp(other.as_slice())
106    }
107}
108
109impl<const N: usize> fmt::Debug for Blob<N> {
110    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
111        self.as_slice().fmt(fmt)
112    }
113}
114
115impl<const N: usize> BoundedStorable for Blob<N> {
116    const MAX_SIZE: u32 = N as u32;
117    const IS_FIXED_SIZE: bool = false;
118}
119
120impl<const N: usize> Storable for Blob<N> {
121    fn to_bytes(&self) -> Cow<[u8]> {
122        Cow::Borrowed(self.as_slice())
123    }
124
125    fn from_bytes(bytes: Cow<[u8]>) -> Self {
126        Self::try_from(bytes.borrow()).unwrap()
127    }
128}
129
130// NOTE: Below are a few implementations of `Storable` for common types.
131// Some of these implementations use `unwrap`, as opposed to returning a `Result`
132// with a possible error. The reason behind this decision is that these
133// `unwrap`s would be triggered in one of the following cases:
134//
135// 1) The implementation of `Storable` has a bug.
136// 2) The data being stored in the stable structure is corrupt.
137//
138// Both of these errors are irrecoverable at runtime, and given the additional
139// complexity of exposing these errors in the API of stable structures, an `unwrap`
140// in case of a detected error is preferable and safer.
141
142impl Storable for () {
143    fn to_bytes(&self) -> Cow<[u8]> {
144        Cow::Borrowed(&[])
145    }
146
147    fn from_bytes(bytes: Cow<[u8]>) -> Self {
148        assert!(bytes.is_empty());
149    }
150}
151
152impl BoundedStorable for () {
153    const MAX_SIZE: u32 = 0;
154    const IS_FIXED_SIZE: bool = false;
155}
156
157impl Storable for Vec<u8> {
158    fn to_bytes(&self) -> Cow<[u8]> {
159        Cow::Borrowed(self)
160    }
161
162    fn from_bytes(bytes: Cow<[u8]>) -> Self {
163        bytes.to_vec()
164    }
165}
166
167impl Storable for String {
168    fn to_bytes(&self) -> Cow<[u8]> {
169        Cow::Borrowed(self.as_bytes())
170    }
171
172    fn from_bytes(bytes: Cow<[u8]>) -> Self {
173        String::from_utf8(bytes.to_vec()).unwrap()
174    }
175}
176
177impl Storable for u128 {
178    fn to_bytes(&self) -> Cow<[u8]> {
179        Cow::Owned(self.to_be_bytes().to_vec())
180    }
181
182    fn from_bytes(bytes: Cow<[u8]>) -> Self {
183        Self::from_be_bytes(bytes.as_ref().try_into().unwrap())
184    }
185}
186
187impl BoundedStorable for u128 {
188    const MAX_SIZE: u32 = 16;
189    const IS_FIXED_SIZE: bool = true;
190}
191
192impl Storable for u64 {
193    fn to_bytes(&self) -> Cow<[u8]> {
194        Cow::Owned(self.to_be_bytes().to_vec())
195    }
196
197    fn from_bytes(bytes: Cow<[u8]>) -> Self {
198        Self::from_be_bytes(bytes.as_ref().try_into().unwrap())
199    }
200}
201
202impl BoundedStorable for u64 {
203    const MAX_SIZE: u32 = 8;
204    const IS_FIXED_SIZE: bool = true;
205}
206
207impl Storable for f64 {
208    fn to_bytes(&self) -> Cow<[u8]> {
209        Cow::Owned(self.to_be_bytes().to_vec())
210    }
211
212    fn from_bytes(bytes: Cow<[u8]>) -> Self {
213        Self::from_be_bytes(bytes.as_ref().try_into().unwrap())
214    }
215}
216
217impl BoundedStorable for f64 {
218    const MAX_SIZE: u32 = 8;
219    const IS_FIXED_SIZE: bool = true;
220}
221
222impl Storable for u32 {
223    fn to_bytes(&self) -> Cow<[u8]> {
224        Cow::Owned(self.to_be_bytes().to_vec())
225    }
226
227    fn from_bytes(bytes: Cow<[u8]>) -> Self {
228        Self::from_be_bytes(bytes.as_ref().try_into().unwrap())
229    }
230}
231
232impl BoundedStorable for u32 {
233    const MAX_SIZE: u32 = 4;
234    const IS_FIXED_SIZE: bool = true;
235}
236
237impl Storable for f32 {
238    fn to_bytes(&self) -> Cow<[u8]> {
239        Cow::Owned(self.to_be_bytes().to_vec())
240    }
241
242    fn from_bytes(bytes: Cow<[u8]>) -> Self {
243        Self::from_be_bytes(bytes.as_ref().try_into().unwrap())
244    }
245}
246
247impl BoundedStorable for f32 {
248    const MAX_SIZE: u32 = 4;
249    const IS_FIXED_SIZE: bool = true;
250}
251
252impl Storable for u16 {
253    fn to_bytes(&self) -> Cow<[u8]> {
254        Cow::Owned(self.to_be_bytes().to_vec())
255    }
256
257    fn from_bytes(bytes: Cow<[u8]>) -> Self {
258        Self::from_be_bytes(bytes.as_ref().try_into().unwrap())
259    }
260}
261
262impl BoundedStorable for u16 {
263    const MAX_SIZE: u32 = 2;
264    const IS_FIXED_SIZE: bool = true;
265}
266
267impl Storable for u8 {
268    fn to_bytes(&self) -> Cow<[u8]> {
269        Cow::Owned(self.to_be_bytes().to_vec())
270    }
271
272    fn from_bytes(bytes: Cow<[u8]>) -> Self {
273        Self::from_be_bytes(bytes.as_ref().try_into().unwrap())
274    }
275}
276
277impl BoundedStorable for u8 {
278    const MAX_SIZE: u32 = 1;
279    const IS_FIXED_SIZE: bool = true;
280}
281
282impl<const N: usize> Storable for [u8; N] {
283    fn to_bytes(&self) -> Cow<[u8]> {
284        Cow::Borrowed(&self[..])
285    }
286
287    fn from_bytes(bytes: Cow<[u8]>) -> Self {
288        assert_eq!(bytes.len(), N);
289        let mut arr = [0; N];
290        arr[0..N].copy_from_slice(&bytes);
291        arr
292    }
293}
294
295impl<const N: usize> BoundedStorable for [u8; N] {
296    const MAX_SIZE: u32 = N as u32;
297    const IS_FIXED_SIZE: bool = true;
298}
299
300impl<T: Storable> Storable for Reverse<T> {
301    fn to_bytes(&self) -> Cow<[u8]> {
302        self.0.to_bytes()
303    }
304
305    fn from_bytes(bytes: Cow<[u8]>) -> Self {
306        Self(T::from_bytes(bytes))
307    }
308}
309
310impl<T: BoundedStorable> BoundedStorable for Reverse<T> {
311    const MAX_SIZE: u32 = T::MAX_SIZE;
312    const IS_FIXED_SIZE: bool = T::IS_FIXED_SIZE;
313}
314
315impl<A, B> Storable for (A, B)
316where
317    A: BoundedStorable + Default,
318    B: BoundedStorable + Default,
319{
320    fn to_bytes(&self) -> Cow<[u8]> {
321        let mut bytes = vec![0; Self::MAX_SIZE as usize];
322        let a_bytes = self.0.to_bytes();
323        let b_bytes = self.1.to_bytes();
324
325        let a_max_size = max_size(&self.0);
326        let b_max_size = max_size(&self.1);
327
328        debug_assert!(a_bytes.len() <= a_max_size);
329        debug_assert!(b_bytes.len() <= b_max_size);
330
331        bytes[0..a_bytes.len()].copy_from_slice(a_bytes.borrow());
332        bytes[a_max_size..a_max_size + b_bytes.len()].copy_from_slice(b_bytes.borrow());
333
334        let a_size_len = bytes_to_store_size::<A>() as usize;
335        let b_size_len = bytes_to_store_size::<B>() as usize;
336
337        let sizes_offset: usize = a_max_size + b_max_size;
338
339        encode_size::<A>(
340            &mut bytes[sizes_offset..sizes_offset + a_size_len],
341            a_bytes.len(),
342        );
343        encode_size::<B>(
344            &mut bytes[sizes_offset + a_size_len..sizes_offset + a_size_len + b_size_len],
345            b_bytes.len(),
346        );
347
348        Cow::Owned(bytes)
349    }
350
351    fn from_bytes(bytes: Cow<[u8]>) -> Self {
352        assert_eq!(bytes.len(), Self::MAX_SIZE as usize);
353
354        // Rust doesn't allow us to access A::MAX_SIZE here but type
355        // deduction from values seems to do the trick. Hence the
356        // Default bound on the Storable impl.
357        let (a, b) = Self::default();
358        let a_max_size = max_size(&a);
359        let b_max_size = max_size(&b);
360        let sizes_offset = a_max_size + b_max_size;
361
362        let a_size_len = bytes_to_store_size::<A>() as usize;
363        let b_size_len = bytes_to_store_size::<B>() as usize;
364        let a_len = decode_size::<A>(&bytes[sizes_offset..sizes_offset + a_size_len]);
365        let b_len = decode_size::<B>(
366            &bytes[sizes_offset + a_size_len..sizes_offset + a_size_len + b_size_len],
367        );
368
369        let a = A::from_bytes(Cow::Borrowed(&bytes[0..a_len]));
370        let b = B::from_bytes(Cow::Borrowed(&bytes[a_max_size..a_max_size + b_len]));
371
372        (a, b)
373    }
374}
375
376impl<A, B> BoundedStorable for (A, B)
377where
378    A: BoundedStorable + Default,
379    B: BoundedStorable + Default,
380{
381    const MAX_SIZE: u32 =
382        A::MAX_SIZE + B::MAX_SIZE + bytes_to_store_size::<A>() + bytes_to_store_size::<B>();
383    const IS_FIXED_SIZE: bool = A::IS_FIXED_SIZE && B::IS_FIXED_SIZE;
384}
385
386const fn max_size<A: BoundedStorable>(_: &A) -> usize {
387    A::MAX_SIZE as usize
388}
389
390fn decode_size<A: BoundedStorable>(src: &[u8]) -> usize {
391    if A::IS_FIXED_SIZE {
392        A::MAX_SIZE as usize
393    } else if A::MAX_SIZE <= u8::MAX as u32 {
394        src[0] as usize
395    } else if A::MAX_SIZE <= u16::MAX as u32 {
396        u16::from_be_bytes([src[0], src[1]]) as usize
397    } else {
398        u32::from_be_bytes([src[0], src[1], src[2], src[3]]) as usize
399    }
400}
401
402fn encode_size<A: BoundedStorable>(dst: &mut [u8], n: usize) {
403    if A::IS_FIXED_SIZE {
404        return;
405    }
406
407    if A::MAX_SIZE <= u8::MAX as u32 {
408        dst[0] = n as u8;
409    } else if A::MAX_SIZE <= u16::MAX as u32 {
410        dst[0..2].copy_from_slice(&(n as u16).to_be_bytes());
411    } else {
412        dst[0..4].copy_from_slice(&(n as u32).to_be_bytes());
413    }
414}
415
416pub(crate) const fn bytes_to_store_size<A: BoundedStorable>() -> u32 {
417    if A::IS_FIXED_SIZE {
418        0
419    } else if A::MAX_SIZE <= u8::MAX as u32 {
420        1
421    } else if A::MAX_SIZE <= u16::MAX as u32 {
422        2
423    } else {
424        4
425    }
426}
b3_stable_structures/storable.rs

b3_stable_structures/
storable.rs
