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    #[cfg(feature = "unstable-hostfn")]
291    pub fn pop(&mut self) -> Option<V> {
292        if self.is_empty() {
293            return None;
294        }
295
296        let slot = self.len().checked_sub(1).unwrap();
297        self.set_len(slot);
298
299        self.elements.take(slot)
300    }
301
302    /// Try to clear and return the last element from storage.
303    /// Shrinks the length of the vector by one.
304    //
305    /// Returns `None` if the vector is empty.
306    ///
307    /// Returns
308    ///
309    /// `Some(Ok(_))` containing the value if it existed and was decoded successfully.
310    /// `Some(Err(_))` if the value existed but its length exceeds the static buffer size.
311    /// `None` if the vector is empty.
312    #[cfg(feature = "unstable-hostfn")]
313    pub fn try_pop(&mut self) -> Option<Result<V, ink_env::Error>> {
314        if self.is_empty() {
315            return None;
316        }
317
318        let slot = self.len().checked_sub(1).expect("unable to checked_sub");
319        self.set_len(slot);
320
321        self.elements.try_take(slot)
322    }
323
324    /// Get a copy of the last element without removing it from storage.
325    ///
326    /// # Panics
327    ///
328    /// * If the value overgrows the static buffer size.
329    pub fn peek(&self) -> Option<V> {
330        if self.is_empty() {
331            return None;
332        }
333
334        let slot = self.len().checked_sub(1).expect("unabled to checked_sub");
335        self.elements.get(slot)
336    }
337
338    /// Try to get a copy of the last element without removing it from storage.
339    ///
340    /// Returns:
341    ///
342    /// `Some(Ok(_))` containing the value if it existed and was decoded successfully.
343    /// `Some(Err(_))` if the value existed but its length exceeds the static buffer size.
344    /// `None` if the vector is empty.
345    #[cfg(feature = "unstable-hostfn")]
346    pub fn try_peek(&self) -> Option<Result<V, ink_env::Error>> {
347        if self.is_empty() {
348            return None;
349        }
350
351        let slot = self.len().checked_sub(1).expect("unabled to checked_sub");
352        self.elements.try_get(slot)
353    }
354
355    /// Access an element at given `index`.
356    ///
357    /// Returns `None` if there was no value at the `index`.
358    ///
359    /// # Panics
360    ///
361    /// * If encoding the element exceeds the static buffer size.
362    pub fn get(&self, index: u32) -> Option<V> {
363        self.elements.get(index)
364    }
365
366    /// Try to access an element at given `index`.
367    ///
368    /// Returns:
369    ///
370    /// * `Some(Ok(_))` containing the value if it existed and was decoded successfully.
371    /// * `Some(Err(_))` if the value existed but its length exceeds the static buffer
372    ///   size.
373    /// * `None` if there was no value at `index`.
374    #[cfg(feature = "unstable-hostfn")]
375    pub fn try_get(&self, index: u32) -> Option<ink_env::Result<V>> {
376        self.elements.try_get(index)
377    }
378
379    /// Set the `value` at given `index`.
380    ///
381    /// # Panics
382    ///
383    /// * If the index is out of bounds.
384    /// * If decoding the element exceeds the static buffer size.
385    pub fn set<T>(&mut self, index: u32, value: &T) -> Option<u32>
386    where
387        T: Storable + EncodeLike<V>,
388    {
389        assert!(index < self.len());
390
391        self.elements.insert(index, value)
392    }
393
394    /// Try to set the `value` at given `index`.
395    ///
396    /// Returns:
397    ///
398    /// * `Ok(Some(_))` if the value was inserted successfully, containing the size in
399    ///   bytes of the pre-existing value at the specified key if any.
400    /// * `Ok(None)` if the insert was successful but there was no pre-existing value.
401    /// * Err([`ink_env::Error::BufferTooSmall`]) if the encoded value exceeds the static
402    ///   buffer size
403    /// * Err([`ink_env::Error::ReturnError`]\([`ink_env::ReturnErrorCode::KeyNotFound`]))
404    ///   if the `index` is out of bounds.
405    ///
406    /// # Panics
407    ///
408    /// Panics if `index` exceeds the length of the vector.
409    pub fn try_set<T>(
410        &mut self,
411        index: u32,
412        value: &T,
413    ) -> Result<Option<u32>, ink_env::Error>
414    where
415        T: Storable + EncodeLike<V>,
416    {
417        if index >= self.len() {
418            return Err(ink_env::ReturnErrorCode::KeyNotFound.into());
419        }
420
421        self.elements.try_insert(index, value)
422    }
423
424    /// Delete all elements from storage.
425    ///
426    /// # Warning
427    ///
428    /// This iterates through all elements in the vector; complexity is O(n).
429    /// It might not be possible to clear large vectors within a single block!
430    #[cfg(feature = "unstable-hostfn")]
431    pub fn clear(&mut self) {
432        for i in 0..self.len() {
433            self.elements.remove(i);
434        }
435        self.set_len(0);
436    }
437
438    /// Clears the value of the element at `index`. It doesn't change the length of the
439    /// vector.
440    ///
441    /// # Panics
442    ///
443    /// Panics if `index` exceeds the length of the vector.
444    #[cfg(feature = "unstable-hostfn")]
445    pub fn clear_at(&mut self, index: u32) {
446        assert!(index < self.len());
447
448        self.elements.remove(index);
449    }
450}
451
452impl<V, KeyType> FromIterator<V> for StorageVec<V, KeyType>
453where
454    V: Packed + EncodeLike<V>,
455    KeyType: StorageKey,
456{
457    fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
458        let mut result = StorageVec::<V, KeyType>::new();
459
460        for element in iter {
461            result.push(&element);
462        }
463
464        result
465    }
466}
467
468impl<V, KeyType> ::core::fmt::Debug for StorageVec<V, KeyType>
469where
470    V: Packed,
471    KeyType: StorageKey,
472{
473    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
474        f.debug_struct("StorageVec")
475            .field("key", &KeyType::KEY)
476            .field("len", &self.len)
477            .field("len_cached", &self.len_cached)
478            .finish()
479    }
480}
481
482#[cfg(test)]
483mod tests {
484    use super::*;
485    use crate::traits::ManualKey;
486
487    #[test]
488    fn empty_vec_works_as_expected() {
489        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
490            let mut array: StorageVec<String> = StorageVec::new();
491
492            assert_eq!(array.pop(), None);
493            assert_eq!(array.peek(), None);
494            assert_eq!(array.len(), 0);
495            assert!(array.is_empty());
496
497            Ok(())
498        })
499        .unwrap()
500    }
501
502    #[test]
503    fn push_and_pop_work() {
504        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
505            let mut array: StorageVec<String> = StorageVec::new();
506
507            let value = "test".to_string();
508            array.push(&value);
509            assert_eq!(array.len(), 1);
510            assert_eq!(array.pop(), Some(value));
511
512            Ok(())
513        })
514        .unwrap()
515    }
516
517    #[test]
518    fn storage_keys_are_correct() {
519        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
520            const BASE: u32 = 123;
521            let mut array: StorageVec<u8, ManualKey<BASE>> = StorageVec::new();
522
523            let expected_value = 127;
524            array.push(&expected_value);
525
526            let actual_length = ink_env::get_contract_storage::<_, u32>(&BASE);
527            assert_eq!(actual_length, Ok(Some(1)));
528
529            let actual_value = ink_env::get_contract_storage::<_, u8>(&(BASE, 0u32));
530            assert_eq!(actual_value, Ok(Some(expected_value)));
531
532            Ok(())
533        })
534        .unwrap()
535    }
536
537    #[test]
538    fn push_and_pop_work_for_two_vecs_with_same_manual_key() {
539        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
540            let expected_value = 255;
541
542            let mut array: StorageVec<u8, ManualKey<{ u32::MIN }>> = StorageVec::new();
543            array.push(&expected_value);
544
545            let mut array2: StorageVec<u8, ManualKey<{ u32::MIN }>> = StorageVec::new();
546            assert_eq!(array2.pop(), Some(expected_value));
547
548            Ok(())
549        })
550        .unwrap()
551    }
552
553    #[test]
554    fn set_and_get_work() {
555        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
556            let mut array: StorageVec<String> = StorageVec::new();
557
558            let value = "test".to_string();
559            array.push(&value);
560            assert_eq!(array.get(0), Some(value));
561            assert_eq!(array.len(), 1);
562
563            let replaced_value = "foo".to_string();
564            array.set(0, &replaced_value);
565            assert_eq!(array.get(0), Some(replaced_value));
566
567            Ok(())
568        })
569        .unwrap()
570    }
571
572    #[test]
573    #[should_panic]
574    fn set_panics_on_oob() {
575        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
576            StorageVec::<u8>::new().set(0, &0);
577
578            Ok(())
579        })
580        .unwrap()
581    }
582
583    #[test]
584    fn clear_works() {
585        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
586            let mut array: StorageVec<u128> = (0..1024).collect();
587
588            array.clear();
589
590            assert_eq!(array.len(), 0);
591            assert_eq!(array.pop(), None);
592
593            Ok(())
594        })
595        .unwrap()
596    }
597
598    #[test]
599    fn clear_on_empty_works() {
600        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
601            let mut array: StorageVec<bool> = StorageVec::new();
602
603            array.clear();
604
605            assert_eq!(array.len(), 0);
606            assert_eq!(array.pop(), None);
607
608            Ok(())
609        })
610        .unwrap()
611    }
612
613    #[test]
614    fn clear_at_works() {
615        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
616            let mut array: StorageVec<u64> = (0..1024).collect();
617
618            array.clear_at(0);
619            assert_eq!(array.len(), 1024);
620            assert_eq!(array.get(0), None);
621
622            let last_idx = array.len() - 1;
623            assert_eq!(array.get(last_idx), Some(1023));
624            array.clear_at(last_idx);
625            assert_eq!(array.get(last_idx), None);
626
627            Ok(())
628        })
629        .unwrap()
630    }
631
632    #[test]
633    #[should_panic]
634    fn clear_at_invalid_index_panics() {
635        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
636            StorageVec::<u32>::new().clear_at(0);
637
638            Ok(())
639        })
640        .unwrap()
641    }
642
643    #[test]
644    fn try_get_works() {
645        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
646            let array: StorageVec<u32> = (0..10).collect();
647
648            assert_eq!(array.try_get(0), Some(Ok(0)));
649            assert_eq!(array.try_get(11), None);
650
651            Ok(())
652        })
653        .unwrap()
654    }
655
656    #[test]
657    fn try_set_works() {
658        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
659            let mut array: StorageVec<u32> = (0..10).collect();
660
661            assert_eq!(array.try_set(0, &1), Ok(Some(4)));
662            assert_eq!(
663                array.try_set(10, &1),
664                Err(ink_env::Error::ReturnError(
665                    ink_env::ReturnErrorCode::KeyNotFound
666                ))
667            );
668
669            array.clear_at(0);
670            assert_eq!(array.try_set(0, &1), Ok(None));
671
672            Ok(())
673        })
674        .unwrap()
675    }
676
677    #[test]
678    fn fallible_push_pop_peek_works() {
679        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
680            let mut array: StorageVec<u32> = (0..10).collect();
681
682            assert_eq!(array.try_push(&10), Ok(()));
683            assert_eq!(array.try_pop(), Some(Ok(10)));
684            assert_eq!(array.try_peek(), Some(Ok(9)));
685
686            array.clear();
687            assert_eq!(array.try_pop(), None);
688            assert_eq!(array.try_peek(), None);
689
690            Ok(())
691        })
692        .unwrap()
693    }
694
695    #[test]
696    fn peek_works() {
697        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
698            let mut array = StorageVec::<u32>::new();
699            assert_eq!(array.peek(), None);
700
701            array.push(&0);
702            array.push(&9);
703
704            assert_eq!(array.peek(), Some(9));
705            assert_eq!(array.peek(), Some(9));
706            assert_eq!(array.len(), 2);
707
708            array.clear();
709            assert_eq!(array.peek(), None);
710            assert_eq!(array.len(), 0);
711
712            Ok(())
713        })
714        .unwrap()
715    }
716
717    #[test]
718    fn from_iter_works() {
719        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
720            let array = StorageVec::<u32>::from_iter([u32::MIN, u32::MAX]);
721
722            assert_eq!(array.len(), 2);
723            assert_eq!(array.get(0), Some(u32::MIN));
724            assert_eq!(array.get(1), Some(u32::MAX));
725
726            Ok(())
727        })
728        .unwrap()
729    }
730
731    #[test]
732    #[should_panic(
733        expected = "assertion failed: cached_len.is_none() || self.len.get() == cached_len"
734    )]
735    fn cached_len_works() {
736        ink_env::test::run_test::<ink_env::DefaultEnvironment, _>(|_| {
737            let array = StorageVec::<u32>::from_iter([u32::MIN, u32::MAX]);
738
739            assert_eq!(array.len(), 2);
740
741            // Force overwrite the length
742            Lazy::<u32>::new().set(&u32::MAX);
743
744            // This should fail the debug assert
745            let _ = array.len();
746
747            Ok(())
748        })
749        .unwrap()
750    }
751}
ink_storage/lazy/vec.rs

ink_storage/lazy/
vec.rs
