ink_storage/lazy/
vec.rs

1// Copyright (C) Use Ink (UK) Ltd.
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
15//! A simple storage vector implementation built on top of [Mapping].
16//!
17//! # Note
18//!
19//! This vector doesn't actually "own" any data.
20//! Instead it is just a simple wrapper around the contract storage facilities.
21
22use core::cell::Cell;
23use ink_primitives::Key;
24use ink_storage_traits::{
25    AutoKey,
26    Packed,
27    Storable,
28    StorableHint,
29    StorageKey,
30};
31use scale::EncodeLike;
32
33use crate::{
34    Lazy,
35    Mapping,
36};
37
38/// A vector of values (elements) directly on contract storage.
39///
40/// # Important
41///
42/// [StorageVec] requires its own pre-defined storage key where to store values. By
43/// default, the is automatically calculated using [`AutoKey`](crate::traits::AutoKey)
44/// during compilation. However, anyone can specify a storage key using
45/// [`ManualKey`](crate::traits::ManualKey). Specifying the storage key can be helpful for
46/// upgradeable contracts or you want to be resistant to future changes of storage key
47/// calculation strategy.
48///
49/// # Differences between `ink::prelude::vec::Vec` and [StorageVec]
50///
51/// Any `Vec<T>` will exhibit [Packed] storage layout; where
52/// [StorageVec] stores each value under it's own storage key.
53///
54/// Hence, any read or write from or to a `Vec` on storage will load
55/// or store _all_ of its elements.
56///
57/// This can be undesirable:
58/// The cost of reading or writing a _single_ element grows linearly
59/// corresponding to the number of elements in the vector (its length).
60/// Additionally, the maximum capacity of the _whole_ vector is limited by
61/// the size of the static buffer used during ABI encoding and decoding
62/// (default 16 KiB).
63///
64/// [StorageVec] on the other hand allows to access each element individually.
65/// Thus, it can theoretically grow to infinite size.
66/// However, we currently limit the length at 2 ^ 32 elements. In practice,
67/// even if the vector elements are single bytes, it'll allow to store
68/// more than 4 GB data in blockchain storage.
69///
70/// # Caveats
71///
72/// Iterators are not provided. [StorageVec] is expected to be used to
73/// store a lot elements, where iterating through the elements would be
74/// rather inefficient (naturally, it is still possible to manually
75/// iterate over the elements using a loop).
76///
77/// For the same reason, operations which would require re-ordering
78/// stored elements are not supported. Examples include inserting and
79/// deleting elements at arbitrary positions or sorting elements.
80///
81/// The decision whether to use `Vec<T>` or [StorageVec] can be seen as an
82/// optimization problem with several factors:
83/// * How large you expect the vector to grow
84/// * The size of individual elements being stored
85/// * How frequently reads, writes and iterations happen
86///
87/// For example, if a vector is expected to stay small but is frequently
88/// iterated over. Choosing a `Vec<T>` instead of [StorageVec] will be
89/// preferred as individual storage reads are much more expensive as
90/// opposed to retrieving and decoding the whole collection with a single
91/// storage read.
92///
93/// # Storage Layout
94///
95/// At given [StorageKey] `K`, the length of the [StorageVec] is hold.
96/// Each element `E` is then stored under a combination of the [StorageVec]
97/// key `K` and the elements index.
98///
99/// Given [StorageVec] under key `K`, the storage key `E` of the `N`th
100/// element is calculated as follows:
101///
102/// `E = scale::Encode((K, N))`
103#[cfg_attr(feature = "std", derive(scale_info::TypeInfo))]
104pub struct StorageVec<V: Packed, KeyType: StorageKey = AutoKey> {
105    /// The number of elements stored on-chain.
106    ///
107    /// # Note
108    ///
109    /// Because of caching, never operate on this field directly!
110    /// Always use `fn get_len()` an `fn set_len()` instead.
111    len: Lazy<u32, KeyType>,
112    /// The length only changes upon pushing to or popping from the vec.
113    /// Hence we can cache it to prevent unnecessary reads from storage.
114    ///
115    /// # Note
116    ///
117    /// Because of caching, never operate on this field directly!
118    /// Always use `fn get_len()` an `fn set_len()` instead.
119    #[cfg_attr(feature = "std", codec(skip))]
120    len_cached: CachedLen,
121    /// We use a [Mapping] to store all elements of the vector.
122    /// Each element is living in storage under `&(KeyType::KEY, index)`.
123    /// Because [StorageVec] has a [StorageKey] parameter under which the
124    /// length and element are stored, it won't collide with the other
125    /// storage fields (unless contract authors purposefully craft such a
126    /// storage layout).
127    elements: Mapping<u32, V, KeyType>,
128}
129
130#[derive(Debug)]
131struct CachedLen(Cell<Option<u32>>);
132
133impl<V, KeyType> Default for StorageVec<V, KeyType>
134where
135    V: Packed,
136    KeyType: StorageKey,
137{
138    fn default() -> Self {
139        Self::new()
140    }
141}
142
143impl<V, KeyType> Storable for StorageVec<V, KeyType>
144where
145    V: Packed,
146    KeyType: StorageKey,
147{
148    #[inline]
149    fn encode<T: scale::Output + ?Sized>(&self, _dest: &mut T) {}
150
151    #[inline]
152    fn decode<I: scale::Input>(_input: &mut I) -> Result<Self, scale::Error> {
153        Ok(Default::default())
154    }
155
156    #[inline]
157    fn encoded_size(&self) -> usize {
158        0
159    }
160}
161
162impl<V, Key, InnerKey> StorableHint<Key> for StorageVec<V, InnerKey>
163where
164    V: Packed,
165    Key: StorageKey,
166    InnerKey: StorageKey,
167{
168    type Type = StorageVec<V, Key>;
169    type PreferredKey = InnerKey;
170}
171
172impl<V, KeyType> StorageKey for StorageVec<V, KeyType>
173where
174    V: Packed,
175    KeyType: StorageKey,
176{
177    const KEY: Key = KeyType::KEY;
178}
179
180#[cfg(feature = "std")]
181const _: () = {
182    use crate::traits::StorageLayout;
183    use ink_metadata::layout::{
184        Layout,
185        LayoutKey,
186        RootLayout,
187    };
188
189    impl<V, KeyType> StorageLayout for StorageVec<V, KeyType>
190    where
191        V: Packed + StorageLayout + scale_info::TypeInfo + 'static,
192        KeyType: StorageKey + scale_info::TypeInfo + 'static,
193    {
194        fn layout(_: &Key) -> Layout {
195            Layout::Root(RootLayout::new(
196                LayoutKey::from(&KeyType::KEY),
197                <V as StorageLayout>::layout(&KeyType::KEY),
198                scale_info::meta_type::<Self>(),
199            ))
200        }
201    }
202};
203
204impl<V, KeyType> StorageVec<V, KeyType>
205where
206    V: Packed,
207    KeyType: StorageKey,
208{
209    /// Creates a new empty `StorageVec`.
210    pub const fn new() -> Self {
211        Self {
212            len: Lazy::new(),
213            len_cached: CachedLen(Cell::new(None)),
214            elements: Mapping::new(),
215        }
216    }
217
218    /// Returns the number of elements in the vector, also referred to as its length.
219    ///
220    /// The length is cached; subsequent calls (without writing to the vector) won't
221    /// trigger additional storage reads.
222    #[inline]
223    pub fn len(&self) -> u32 {
224        let cached_len = self.len_cached.0.get();
225
226        debug_assert!(cached_len.is_none() || self.len.get() == cached_len);
227
228        cached_len.unwrap_or_else(|| {
229            let value = self.len.get();
230            self.len_cached.0.set(value);
231            value.unwrap_or(u32::MIN)
232        })
233    }
234
235    /// Overwrite the length. Writes directly to contract storage.
236    fn set_len(&mut self, new_len: u32) {
237        self.len.set(&new_len);
238        self.len_cached.0.set(Some(new_len));
239    }
240
241    /// Returns `true` if the vector contains no elements.
242    pub fn is_empty(&self) -> bool {
243        self.len() == 0
244    }
245
246    /// Appends an element to the back of the vector.
247    ///
248    /// # Panics
249    ///
250    /// * If the vector is at capacity (max. of 2 ^ 32 elements).
251    /// * If the value overgrows the static buffer size.
252    /// * If there was already a value at the current index.
253    pub fn push<T>(&mut self, value: &T)
254    where
255        T: Storable + scale::EncodeLike<V>,
256    {
257        let slot = self.len();
258        self.set_len(slot.checked_add(1).expect("unable to checked_add"));
259
260        assert!(self.elements.insert(slot, value).is_none());
261    }
262
263    /// Try to append an element to the back of the vector.
264    ///
265    /// Returns:
266    ///
267    /// * `Ok(())` if the value was inserted successfully
268    /// * `Err(_)` if the encoded value exceeds the static buffer size.
269    pub fn try_push<T>(&mut self, value: &T) -> Result<(), ink_env::Error>
270    where
271        T: Storable + scale::EncodeLike<V>,
272    {
273        let slot = self.len();
274        self.set_len(slot.checked_add(1).unwrap());
275
276        assert!(self.elements.try_insert(slot, value)?.is_none());
277
278        Ok(())
279    }
280
281    /// Clears the last element from the storage and returns it.
282    /// Shrinks the length of the vector by one.
283    //
284    /// Returns `None` if the vector is empty or if the last
285    /// element was already cleared from storage.
286    ///
287    /// # Panics
288    ///
289    /// * If the value overgrows the static buffer size.
290    pub fn pop(&mut self) -> Option<V> {
291        if self.is_empty() {
292            return None;
293        }
294
295        let slot = self.len().checked_sub(1).unwrap();
296        self.set_len(slot);
297
298        self.elements.take(slot)
299    }
300
301    /// Try to clear and return the last element from storage.
302    /// Shrinks the length of the vector by one.
303    //
304    /// Returns `None` if the vector is empty.
305    ///
306    /// Returns
307    ///
308    /// `Some(Ok(_))` containing the value if it existed and was decoded successfully.
309    /// `Some(Err(_))` if the value existed but its length exceeds the static buffer size.
310    /// `None` if the vector is empty.
311    pub fn try_pop(&mut self) -> Option<Result<V, ink_env::Error>> {
312        if self.is_empty() {
313            return None;
314        }
315
316        let slot = self.len().checked_sub(1).expect("unable to checked_sub");
317        self.set_len(slot);
318
319        self.elements.try_take(slot)
320    }
321
322    /// Get a copy of the last element without removing it from storage.
323    ///
324    /// # Panics
325    ///
326    /// * If the value overgrows the static buffer size.
327    pub fn peek(&self) -> Option<V> {
328        if self.is_empty() {
329            return None;
330        }
331
332        let slot = self.len().checked_sub(1).expect("unable to checked_sub");
333        self.elements.get(slot)
334    }
335
336    /// Try to get a copy of the last element without removing it from storage.
337    ///
338    /// Returns:
339    ///
340    /// `Some(Ok(_))` containing the value if it existed and was decoded successfully.
341    /// `Some(Err(_))` if the value existed but its length exceeds the static buffer size.
342    /// `None` if the vector is empty.
343    pub fn try_peek(&self) -> Option<Result<V, ink_env::Error>> {
344        if self.is_empty() {
345            return None;
346        }
347
348        let slot = self.len().checked_sub(1).expect("unable to checked_sub");
349        self.elements.try_get(slot)
350    }
351
352    /// Access an element at given `index`.
353    ///
354    /// Returns `None` if there was no value at the `index`.
355    ///
356    /// # Panics
357    ///
358    /// * If encoding the element exceeds the static buffer size.
359    pub fn get(&self, index: u32) -> Option<V> {
360        self.elements.get(index)
361    }
362
363    /// Try to access an element at given `index`.
364    ///
365    /// Returns:
366    ///
367    /// * `Some(Ok(_))` containing the value if it existed and was decoded successfully.
368    /// * `Some(Err(_))` if the value existed but its length exceeds the static buffer
369    ///   size.
370    /// * `None` if there was no value at `index`.
371    pub fn try_get(&self, index: u32) -> Option<ink_env::Result<V>> {
372        self.elements.try_get(index)
373    }
374
375    /// Set the `value` at given `index`.
376    ///
377    /// # Panics
378    ///
379    /// * If the index is out of bounds.
380    /// * If decoding the element exceeds the static buffer size.
381    pub fn set<T>(&mut self, index: u32, value: &T) -> Option<u32>
382    where
383        T: Storable + EncodeLike<V>,
384    {
385        assert!(index < self.len());
386
387        self.elements.insert(index, value)
388    }
389
390    /// Try to set the `value` at given `index`.
391    ///
392    /// Returns:
393    ///
394    /// * `Ok(Some(_))` if the value was inserted successfully, containing the size in
395    ///   bytes of the pre-existing value at the specified key if any.
396    /// * `Ok(None)` if the insert was successful but there was no pre-existing value.
397    /// * Err([`ink_env::Error::BufferTooSmall`]) if the encoded value exceeds the static
398    ///   buffer size
399    /// * Err([`ink_env::Error::ReturnError`]\([`ink_env::ReturnErrorCode::KeyNotFound`]))
400    ///   if the `index` is out of bounds.
401    ///
402    /// # Panics
403    ///
404    /// Panics if `index` exceeds the length of the vector.
405    pub fn try_set<T>(
406        &mut self,
407        index: u32,
408        value: &T,
409    ) -> Result<Option<u32>, ink_env::Error>
410    where
411        T: Storable + EncodeLike<V>,
412    {
413        if index >= self.len() {
414            return Err(ink_env::ReturnErrorCode::KeyNotFound.into());
415        }
416
417        self.elements.try_insert(index, value)
418    }
419
420    /// Delete all elements from storage.
421    ///
422    /// # Warning
423    ///
424    /// This iterates through all elements in the vector; complexity is O(n).
425    /// It might not be possible to clear large vectors within a single block!
426    pub fn clear(&mut self) {
427        for i in 0..self.len() {
428            self.elements.remove(i);
429        }
430        self.set_len(0);
431    }
432
433    /// Clears the value of the element at `index`. It doesn't change the length of the
434    /// vector.
435    ///
436    /// # Panics
437    ///
438    /// Panics if `index` exceeds the length of the vector.
439    pub fn clear_at(&mut self, index: u32) {
440        assert!(index < self.len());
441
442        self.elements.remove(index);
443    }
444}
445
446impl<V, KeyType> FromIterator<V> for StorageVec<V, KeyType>
447where
448    V: Packed + EncodeLike<V>,
449    KeyType: StorageKey,
450{
451    fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
452        let mut result = StorageVec::<V, KeyType>::new();
453
454        for element in iter {
455            result.push(&element);
456        }
457
458        result
459    }
460}
461
462impl<V, KeyType> ::core::fmt::Debug for StorageVec<V, KeyType>
463where
464    V: Packed,
465    KeyType: StorageKey,
466{
467    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
468        f.debug_struct("StorageVec")
469            .field("key", &KeyType::KEY)
470            .field("len", &self.len)
471            .field("len_cached", &self.len_cached)
472            .finish()
473    }
474}
475
476#[cfg(test)]
477mod tests {
478    use super::*;
479    use crate::traits::ManualKey;
480
481    #[test]
482    fn empty_vec_works_as_expected() {
483        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
484            let mut array: StorageVec<String> = StorageVec::new();
485
486            assert_eq!(array.pop(), None);
487            assert_eq!(array.peek(), None);
488            assert_eq!(array.len(), 0);
489            assert!(array.is_empty());
490
491            Ok(())
492        })
493        .unwrap()
494    }
495
496    #[test]
497    fn push_and_pop_work() {
498        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
499            let mut array: StorageVec<String> = StorageVec::new();
500
501            let value = "test".to_string();
502            array.push(&value);
503            assert_eq!(array.len(), 1);
504            assert_eq!(array.pop(), Some(value));
505
506            Ok(())
507        })
508        .unwrap()
509    }
510
511    #[test]
512    fn storage_keys_are_correct() {
513        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
514            const BASE: u32 = 123;
515            let mut array: StorageVec<u8, ManualKey<BASE>> = StorageVec::new();
516
517            let expected_value = 127;
518            array.push(&expected_value);
519
520            let actual_length = ink_env::get_contract_storage::<_, u32>(&BASE);
521            assert_eq!(actual_length, Ok(Some(1)));
522
523            let actual_value = ink_env::get_contract_storage::<_, u8>(&(BASE, 0u32));
524            assert_eq!(actual_value, Ok(Some(expected_value)));
525
526            Ok(())
527        })
528        .unwrap()
529    }
530
531    #[test]
532    fn push_and_pop_work_for_two_vecs_with_same_manual_key() {
533        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
534            let expected_value = 255;
535
536            let mut array: StorageVec<u8, ManualKey<{ u32::MIN }>> = StorageVec::new();
537            array.push(&expected_value);
538
539            let mut array2: StorageVec<u8, ManualKey<{ u32::MIN }>> = StorageVec::new();
540            assert_eq!(array2.pop(), Some(expected_value));
541
542            Ok(())
543        })
544        .unwrap()
545    }
546
547    #[test]
548    fn set_and_get_work() {
549        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
550            let mut array: StorageVec<String> = StorageVec::new();
551
552            let value = "test".to_string();
553            array.push(&value);
554            assert_eq!(array.get(0), Some(value));
555            assert_eq!(array.len(), 1);
556
557            let replaced_value = "foo".to_string();
558            array.set(0, &replaced_value);
559            assert_eq!(array.get(0), Some(replaced_value));
560
561            Ok(())
562        })
563        .unwrap()
564    }
565
566    #[test]
567    #[should_panic]
568    fn set_panics_on_oob() {
569        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
570            StorageVec::<u8>::new().set(0, &0);
571
572            Ok(())
573        })
574        .unwrap()
575    }
576
577    #[test]
578    fn clear_works() {
579        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
580            let mut array: StorageVec<u128> = (0..1024).collect();
581
582            array.clear();
583
584            assert_eq!(array.len(), 0);
585            assert_eq!(array.pop(), None);
586
587            Ok(())
588        })
589        .unwrap()
590    }
591
592    #[test]
593    fn clear_on_empty_works() {
594        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
595            let mut array: StorageVec<bool> = StorageVec::new();
596
597            array.clear();
598
599            assert_eq!(array.len(), 0);
600            assert_eq!(array.pop(), None);
601
602            Ok(())
603        })
604        .unwrap()
605    }
606
607    #[test]
608    fn clear_at_works() {
609        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
610            let mut array: StorageVec<u64> = (0..1024).collect();
611
612            array.clear_at(0);
613            assert_eq!(array.len(), 1024);
614            assert_eq!(array.get(0), None);
615
616            let last_idx = array.len() - 1;
617            assert_eq!(array.get(last_idx), Some(1023));
618            array.clear_at(last_idx);
619            assert_eq!(array.get(last_idx), None);
620
621            Ok(())
622        })
623        .unwrap()
624    }
625
626    #[test]
627    #[should_panic]
628    fn clear_at_invalid_index_panics() {
629        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
630            StorageVec::<u32>::new().clear_at(0);
631
632            Ok(())
633        })
634        .unwrap()
635    }
636
637    #[test]
638    fn try_get_works() {
639        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
640            let array: StorageVec<u32> = (0..10).collect();
641
642            assert_eq!(array.try_get(0), Some(Ok(0)));
643            assert_eq!(array.try_get(11), None);
644
645            Ok(())
646        })
647        .unwrap()
648    }
649
650    #[test]
651    fn try_set_works() {
652        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
653            let mut array: StorageVec<u32> = (0..10).collect();
654
655            assert_eq!(array.try_set(0, &1), Ok(Some(4)));
656            assert_eq!(
657                array.try_set(10, &1),
658                Err(ink_env::Error::ReturnError(
659                    ink_env::ReturnErrorCode::KeyNotFound
660                ))
661            );
662
663            array.clear_at(0);
664            assert_eq!(array.try_set(0, &1), Ok(None));
665
666            Ok(())
667        })
668        .unwrap()
669    }
670
671    #[test]
672    fn fallible_push_pop_peek_works() {
673        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
674            let mut array: StorageVec<u32> = (0..10).collect();
675
676            assert_eq!(array.try_push(&10), Ok(()));
677            assert_eq!(array.try_pop(), Some(Ok(10)));
678            assert_eq!(array.try_peek(), Some(Ok(9)));
679
680            array.clear();
681            assert_eq!(array.try_pop(), None);
682            assert_eq!(array.try_peek(), None);
683
684            Ok(())
685        })
686        .unwrap()
687    }
688
689    #[test]
690    fn peek_works() {
691        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
692            let mut array = StorageVec::<u32>::new();
693            assert_eq!(array.peek(), None);
694
695            array.push(&0);
696            array.push(&9);
697
698            assert_eq!(array.peek(), Some(9));
699            assert_eq!(array.peek(), Some(9));
700            assert_eq!(array.len(), 2);
701
702            array.clear();
703            assert_eq!(array.peek(), None);
704            assert_eq!(array.len(), 0);
705
706            Ok(())
707        })
708        .unwrap()
709    }
710
711    #[test]
712    fn from_iter_works() {
713        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
714            let array = StorageVec::<u32>::from_iter([u32::MIN, u32::MAX]);
715
716            assert_eq!(array.len(), 2);
717            assert_eq!(array.get(0), Some(u32::MIN));
718            assert_eq!(array.get(1), Some(u32::MAX));
719
720            Ok(())
721        })
722        .unwrap()
723    }
724
725    #[test]
726    #[should_panic(
727        expected = "assertion failed: cached_len.is_none() || self.len.get() == cached_len"
728    )]
729    fn cached_len_works() {
730        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
731            let array = StorageVec::<u32>::from_iter([u32::MIN, u32::MAX]);
732
733            assert_eq!(array.len(), 2);
734
735            // Force overwrite the length
736            Lazy::<u32>::new().set(&u32::MAX);
737
738            // This should fail the debug assert
739            let _ = array.len();
740
741            Ok(())
742        })
743        .unwrap()
744    }
745}