hermit_toolkit_storage/
append_store.rs

1//! An "append store" is a storage wrapper that guarantees constant-cost appending to and popping
2//! from a list of items in storage.
3//!
4//! This is achieved by storing each item in a separate storage entry. A special key is reserved
5//! for storing the length of the collection so far.
6use std::convert::TryInto;
7use std::marker::PhantomData;
8
9use serde::{de::DeserializeOwned, Serialize};
10
11use cosmwasm_std::{ReadonlyStorage, StdError, StdResult, Storage};
12
13use hermit_toolkit_serialization::{Bincode2, Serde};
14
15const LEN_KEY: &[u8] = b"len";
16
17// Mutable append-store
18
19/// A type allowing both reads from and writes to the append store at a given storage location.
20#[derive(Debug)]
21pub struct AppendStoreMut<'a, T, S, Ser = Bincode2>
22    where
23        T: Serialize + DeserializeOwned,
24        S: Storage,
25        Ser: Serde,
26{
27    storage: &'a mut S,
28    item_type: PhantomData<*const T>,
29    serialization_type: PhantomData<*const Ser>,
30    len: u32,
31}
32
33impl<'a, T, S> AppendStoreMut<'a, T, S, Bincode2>
34    where
35        T: Serialize + DeserializeOwned,
36        S: Storage,
37{
38    /// Try to use the provided storage as an AppendStore. If it doesn't seem to be one, then
39    /// initialize it as one.
40    ///
41    /// Returns Err if the contents of the storage can not be parsed.
42    pub fn attach_or_create(storage: &'a mut S) -> StdResult<Self> {
43        AppendStoreMut::attach_or_create_with_serialization(storage, Bincode2)
44    }
45
46    /// Try to use the provided storage as an AppendStore.
47    ///
48    /// Returns None if the provided storage doesn't seem like an AppendStore.
49    /// Returns Err if the contents of the storage can not be parsed.
50    pub fn attach(storage: &'a mut S) -> Option<StdResult<Self>> {
51        AppendStoreMut::attach_with_serialization(storage, Bincode2)
52    }
53}
54
55impl<'a, T, S, Ser> AppendStoreMut<'a, T, S, Ser>
56    where
57        T: Serialize + DeserializeOwned,
58        S: Storage,
59        Ser: Serde,
60{
61    /// Try to use the provided storage as an AppendStore. If it doesn't seem to be one, then
62    /// initialize it as one. This method allows choosing the serialization format you want to use.
63    ///
64    /// Returns Err if the contents of the storage can not be parsed.
65    pub fn attach_or_create_with_serialization(storage: &'a mut S, _ser: Ser) -> StdResult<Self> {
66        if let Some(len_vec) = storage.get(LEN_KEY) {
67            Self::new(storage, &len_vec)
68        } else {
69            let len_vec = 0_u32.to_be_bytes();
70            storage.set(LEN_KEY, &len_vec);
71            Self::new(storage, &len_vec)
72        }
73    }
74
75    /// Try to use the provided storage as an AppendStore.
76    /// This method allows choosing the serialization format you want to use.
77    ///
78    /// Returns None if the provided storage doesn't seem like an AppendStore.
79    /// Returns Err if the contents of the storage can not be parsed.
80    pub fn attach_with_serialization(storage: &'a mut S, _ser: Ser) -> Option<StdResult<Self>> {
81        let len_vec = storage.get(LEN_KEY)?;
82        Some(Self::new(storage, &len_vec))
83    }
84
85    fn new(storage: &'a mut S, len_vec: &[u8]) -> StdResult<Self> {
86        let len_array = len_vec
87            .try_into()
88            .map_err(|err| StdError::parse_err("u32", err))?;
89        let len = u32::from_be_bytes(len_array);
90
91        Ok(Self {
92            storage,
93            item_type: PhantomData,
94            serialization_type: PhantomData,
95            len,
96        })
97    }
98
99    pub fn len(&self) -> u32 {
100        self.len
101    }
102
103    pub fn is_empty(&self) -> bool {
104        self.len == 0
105    }
106
107    pub fn storage(&mut self) -> &mut S {
108        self.storage
109    }
110
111    pub fn readonly_storage(&self) -> &S {
112        self.storage
113    }
114
115    /// Return an iterator over the items in the collection
116    pub fn iter(&self) -> Iter<T, S, Ser> {
117        self.as_readonly().iter()
118    }
119
120    /// Get the value stored at a given position.
121    ///
122    /// # Errors
123    /// Will return an error if pos is out of bounds or if an item is not found.
124    pub fn get_at(&self, pos: u32) -> StdResult<T> {
125        self.as_readonly().get_at(pos)
126    }
127
128    fn get_at_unchecked(&self, pos: u32) -> StdResult<T> {
129        self.as_readonly().get_at_unchecked(pos)
130    }
131
132    /// Set the value of the item stored at a given position.
133    ///
134    /// # Errors
135    /// Will return an error if the position is out of bounds
136    pub fn set_at(&mut self, pos: u32, item: &T) -> StdResult<()> {
137        if pos >= self.len {
138            return Err(StdError::generic_err("AppendStorage access out of bounds"));
139        }
140        self.set_at_unchecked(pos, item)
141    }
142
143    fn set_at_unchecked(&mut self, pos: u32, item: &T) -> StdResult<()> {
144        let serialized = Ser::serialize(item)?;
145        self.storage.set(&pos.to_be_bytes(), &serialized);
146        Ok(())
147    }
148
149    /// Append an item to the end of the collection.
150    ///
151    /// This operation has a constant cost.
152    pub fn push(&mut self, item: &T) -> StdResult<()> {
153        self.set_at_unchecked(self.len, item)?;
154        self.set_length(self.len + 1);
155        Ok(())
156    }
157
158    /// Pop the last item off the collection
159    pub fn pop(&mut self) -> StdResult<T> {
160        if let Some(len) = self.len.checked_sub(1) {
161            let item = self.get_at_unchecked(len);
162            self.set_length(len);
163            item
164        } else {
165            Err(StdError::generic_err("Can not pop from empty AppendStore"))
166        }
167    }
168
169    /// Clear the collection
170    pub fn clear(&mut self) {
171        self.set_length(0);
172    }
173
174    /// Set the length of the collection
175    fn set_length(&mut self, len: u32) {
176        self.storage.set(LEN_KEY, &len.to_be_bytes());
177        self.len = len;
178    }
179
180    /// Gain access to the implementation of the immutable methods
181    fn as_readonly(&self) -> AppendStore<T, S, Ser> {
182        AppendStore {
183            storage: self.storage,
184            item_type: self.item_type,
185            serialization_type: self.serialization_type,
186            len: self.len,
187        }
188    }
189}
190
191// Doing this is fundamentally flawed because it would theoretically permanently turn the `&mut S`
192// into a `&S`, preventing any further mutation of the entire storage.
193// In practice this just gave annoying lifetime errors either here or at `AppendStoreMut::as_readonly`.
194/*
195impl<'a, T, S> IntoIterator for AppendStoreMut<'a, T, S>
196where
197    T: 'a + Serialize + DeserializeOwned,
198    S: Storage,
199{
200    type Item = StdResult<T>;
201    type IntoIter = Iter<'a, T, S>;
202
203    fn into_iter(self) -> Iter<'a, T, S> {
204        Iter {
205            storage: self.as_readonly(),
206            start: 0,
207            end: self.len,
208        }
209    }
210}
211*/
212
213// Readonly append-store
214
215/// A type allowing only reads from an append store. useful in the context_, u8 of queries.
216#[derive(Debug)]
217pub struct AppendStore<'a, T, S, Ser = Bincode2>
218    where
219        T: Serialize + DeserializeOwned,
220        S: ReadonlyStorage,
221        Ser: Serde,
222{
223    storage: &'a S,
224    item_type: PhantomData<*const T>,
225    serialization_type: PhantomData<*const Ser>,
226    len: u32,
227}
228
229impl<'a, T, S> AppendStore<'a, T, S, Bincode2>
230    where
231        T: Serialize + DeserializeOwned,
232        S: ReadonlyStorage,
233{
234    /// Try to use the provided storage as an AppendStore.
235    ///
236    /// Returns None if the provided storage doesn't seem like an AppendStore.
237    /// Returns Err if the contents of the storage can not be parsed.
238    pub fn attach(storage: &'a S) -> Option<StdResult<Self>> {
239        AppendStore::attach_with_serialization(storage, Bincode2)
240    }
241}
242
243impl<'a, T, S, Ser> AppendStore<'a, T, S, Ser>
244    where
245        T: Serialize + DeserializeOwned,
246        S: ReadonlyStorage,
247        Ser: Serde,
248{
249    /// Try to use the provided storage as an AppendStore.
250    /// This method allows choosing the serialization format you want to use.
251    ///
252    /// Returns None if the provided storage doesn't seem like an AppendStore.
253    /// Returns Err if the contents of the storage can not be parsed.
254    pub fn attach_with_serialization(storage: &'a S, _ser: Ser) -> Option<StdResult<Self>> {
255        let len_vec = storage.get(LEN_KEY)?;
256        Some(AppendStore::new(storage, len_vec))
257    }
258
259    fn new(storage: &'a S, len_vec: Vec<u8>) -> StdResult<Self> {
260        let len_array = len_vec
261            .as_slice()
262            .try_into()
263            .map_err(|err| StdError::parse_err("u32", err))?;
264        let len = u32::from_be_bytes(len_array);
265
266        Ok(Self {
267            storage,
268            item_type: PhantomData,
269            serialization_type: PhantomData,
270            len,
271        })
272    }
273
274    pub fn len(&self) -> u32 {
275        self.len
276    }
277
278    pub fn is_empty(&self) -> bool {
279        self.len == 0
280    }
281
282    pub fn readonly_storage(&self) -> &S {
283        self.storage
284    }
285
286    /// Return an iterator over the items in the collection
287    pub fn iter(&self) -> Iter<'a, T, S, Ser> {
288        Iter {
289            storage: AppendStore::clone(self),
290            start: 0,
291            end: self.len,
292        }
293    }
294
295    /// Get the value stored at a given position.
296    ///
297    /// # Errors
298    /// Will return an error if pos is out of bounds or if an item is not found.
299    pub fn get_at(&self, pos: u32) -> StdResult<T> {
300        if pos >= self.len {
301            return Err(StdError::generic_err("AppendStorage access out of bounds"));
302        }
303        self.get_at_unchecked(pos)
304    }
305
306    fn get_at_unchecked(&self, pos: u32) -> StdResult<T> {
307        let serialized = self.storage.get(&pos.to_be_bytes()).ok_or_else(|| {
308            StdError::generic_err(format!("No item in AppendStorage at position {}", pos))
309        })?;
310        Ser::deserialize(&serialized)
311    }
312}
313
314impl<'a, T, S, Ser> IntoIterator for AppendStore<'a, T, S, Ser>
315    where
316        T: Serialize + DeserializeOwned,
317        S: ReadonlyStorage,
318        Ser: Serde,
319{
320    type Item = StdResult<T>;
321    type IntoIter = Iter<'a, T, S, Ser>;
322
323    fn into_iter(self) -> Iter<'a, T, S, Ser> {
324        let end = self.len;
325        Iter {
326            storage: self,
327            start: 0,
328            end,
329        }
330    }
331}
332
333// Manual `Clone` implementation because the default one tries to clone the Storage??
334impl<'a, T, S, Ser> Clone for AppendStore<'a, T, S, Ser>
335    where
336        T: Serialize + DeserializeOwned,
337        S: ReadonlyStorage,
338        Ser: Serde,
339{
340    fn clone(&self) -> Self {
341        Self {
342            storage: self.storage,
343            item_type: self.item_type,
344            serialization_type: self.serialization_type,
345            len: self.len,
346        }
347    }
348}
349
350// Owning iterator
351
352/// An iterator over the contents of the append store.
353#[derive(Debug)]
354pub struct Iter<'a, T, S, Ser>
355    where
356        T: Serialize + DeserializeOwned,
357        S: ReadonlyStorage,
358        Ser: Serde,
359{
360    storage: AppendStore<'a, T, S, Ser>,
361    start: u32,
362    end: u32,
363}
364
365impl<'a, T, S, Ser> Iterator for Iter<'a, T, S, Ser>
366    where
367        T: Serialize + DeserializeOwned,
368        S: ReadonlyStorage,
369        Ser: Serde,
370{
371    type Item = StdResult<T>;
372
373    fn next(&mut self) -> Option<Self::Item> {
374        if self.start >= self.end {
375            return None;
376        }
377        let item = self.storage.get_at(self.start);
378        self.start += 1;
379        Some(item)
380    }
381
382    // This needs to be implemented correctly for `ExactSizeIterator` to work.
383    fn size_hint(&self) -> (usize, Option<usize>) {
384        let len = (self.end - self.start) as usize;
385        (len, Some(len))
386    }
387
388    // I implement `nth` manually because it is used in the standard library whenever
389    // it wants to skip over elements, but the default implementation repeatedly calls next.
390    // because that is very expensive in this case, and the items are just discarded, we wan
391    // do better here.
392    // In practice, this enables cheap paging over the storage by calling:
393    // `append_store.iter().skip(start).take(length).collect()`
394    fn nth(&mut self, n: usize) -> Option<Self::Item> {
395        self.start = self.start.saturating_add(n as u32);
396        self.next()
397    }
398}
399
400impl<'a, T, S, Ser> DoubleEndedIterator for Iter<'a, T, S, Ser>
401    where
402        T: Serialize + DeserializeOwned,
403        S: ReadonlyStorage,
404        Ser: Serde,
405{
406    fn next_back(&mut self) -> Option<Self::Item> {
407        if self.start >= self.end {
408            return None;
409        }
410        self.end -= 1;
411        let item = self.storage.get_at(self.end);
412        Some(item)
413    }
414
415    // I implement `nth_back` manually because it is used in the standard library whenever
416    // it wants to skip over elements, but the default implementation repeatedly calls next_back.
417    // because that is very expensive in this case, and the items are just discarded, we wan
418    // do better here.
419    // In practice, this enables cheap paging over the storage by calling:
420    // `append_store.iter().skip(start).take(length).collect()`
421    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
422        self.end = self.end.saturating_sub(n as u32);
423        self.next_back()
424    }
425}
426
427// This enables writing `append_store.iter().skip(n).rev()`
428impl<'a, T, S, Ser> ExactSizeIterator for Iter<'a, T, S, Ser>
429    where
430        T: Serialize + DeserializeOwned,
431        S: ReadonlyStorage,
432        Ser: Serde,
433{
434}
435
436#[cfg(test)]
437mod tests {
438    use cosmwasm_std::testing::MockStorage;
439
440    use hermit_toolkit_serialization::Json;
441
442    use super::*;
443
444    #[test]
445    fn test_push_pop() -> StdResult<()> {
446        let mut storage = MockStorage::new();
447        let mut append_store = AppendStoreMut::attach_or_create(&mut storage)?;
448        append_store.push(&1234)?;
449        append_store.push(&2143)?;
450        append_store.push(&3412)?;
451        append_store.push(&4321)?;
452
453        assert_eq!(append_store.pop(), Ok(4321));
454        assert_eq!(append_store.pop(), Ok(3412));
455        assert_eq!(append_store.pop(), Ok(2143));
456        assert_eq!(append_store.pop(), Ok(1234));
457        assert!(append_store.pop().is_err());
458
459        Ok(())
460    }
461
462    #[test]
463    fn test_iterator() -> StdResult<()> {
464        let mut storage = MockStorage::new();
465        let mut append_store = AppendStoreMut::attach_or_create(&mut storage)?;
466        append_store.push(&1234)?;
467        append_store.push(&2143)?;
468        append_store.push(&3412)?;
469        append_store.push(&4321)?;
470
471        // iterate twice to make sure nothing changed
472        let mut iter = append_store.iter();
473        assert_eq!(iter.next(), Some(Ok(1234)));
474        assert_eq!(iter.next(), Some(Ok(2143)));
475        assert_eq!(iter.next(), Some(Ok(3412)));
476        assert_eq!(iter.next(), Some(Ok(4321)));
477        assert_eq!(iter.next(), None);
478
479        let mut iter = append_store.iter();
480        assert_eq!(iter.next(), Some(Ok(1234)));
481        assert_eq!(iter.next(), Some(Ok(2143)));
482        assert_eq!(iter.next(), Some(Ok(3412)));
483        assert_eq!(iter.next(), Some(Ok(4321)));
484        assert_eq!(iter.next(), None);
485
486        // make sure our implementation of `nth` doesn't break anything
487        let mut iter = append_store.iter().skip(2);
488        assert_eq!(iter.next(), Some(Ok(3412)));
489        assert_eq!(iter.next(), Some(Ok(4321)));
490        assert_eq!(iter.next(), None);
491
492        Ok(())
493    }
494
495    #[test]
496    fn test_reverse_iterator() -> StdResult<()> {
497        let mut storage = MockStorage::new();
498        let mut append_store = AppendStoreMut::attach_or_create(&mut storage)?;
499        append_store.push(&1234)?;
500        append_store.push(&2143)?;
501        append_store.push(&3412)?;
502        append_store.push(&4321)?;
503
504        let mut iter = append_store.iter().rev();
505        assert_eq!(iter.next(), Some(Ok(4321)));
506        assert_eq!(iter.next(), Some(Ok(3412)));
507        assert_eq!(iter.next(), Some(Ok(2143)));
508        assert_eq!(iter.next(), Some(Ok(1234)));
509        assert_eq!(iter.next(), None);
510
511        // iterate twice to make sure nothing changed
512        let mut iter = append_store.iter().rev();
513        assert_eq!(iter.next(), Some(Ok(4321)));
514        assert_eq!(iter.next(), Some(Ok(3412)));
515        assert_eq!(iter.next(), Some(Ok(2143)));
516        assert_eq!(iter.next(), Some(Ok(1234)));
517        assert_eq!(iter.next(), None);
518
519        // make sure our implementation of `nth_back` doesn't break anything
520        let mut iter = append_store.iter().rev().skip(2);
521        assert_eq!(iter.next(), Some(Ok(2143)));
522        assert_eq!(iter.next(), Some(Ok(1234)));
523        assert_eq!(iter.next(), None);
524
525        // make sure our implementation of `ExactSizeIterator` works well
526        let mut iter = append_store.iter().skip(2).rev();
527        assert_eq!(iter.next(), Some(Ok(4321)));
528        assert_eq!(iter.next(), Some(Ok(3412)));
529        assert_eq!(iter.next(), None);
530
531        Ok(())
532    }
533
534    #[test]
535    fn test_attach_to_wrong_location() {
536        let mut storage = MockStorage::new();
537        assert!(AppendStore::<u8, _>::attach(&storage).is_none());
538        assert!(AppendStoreMut::<u8, _>::attach(&mut storage).is_none());
539    }
540
541    #[test]
542    fn test_serializations() -> StdResult<()> {
543        // Check the default behavior is Bincode2
544        let mut storage = MockStorage::new();
545
546        let mut append_store = AppendStoreMut::attach_or_create(&mut storage)?;
547        append_store.push(&1234)?;
548
549        let bytes = append_store.readonly_storage().get(&0_u32.to_be_bytes());
550        assert_eq!(bytes, Some(vec![210, 4, 0, 0]));
551
552        // Check that overriding the serializer with Json works
553        let mut storage = MockStorage::new();
554        let mut append_store =
555            AppendStoreMut::attach_or_create_with_serialization(&mut storage, Json)?;
556        append_store.push(&1234)?;
557        let bytes = append_store.readonly_storage().get(&0_u32.to_be_bytes());
558        assert_eq!(bytes, Some(b"1234".to_vec()));
559
560        Ok(())
561    }
562}
hermit_toolkit_storage/append_store.rs

hermit_toolkit_storage/
append_store.rs
