1use 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#[cfg_attr(feature = "std", derive(scale_info::TypeInfo))]
104pub struct StorageVec<V: Packed, KeyType: StorageKey = AutoKey> {
105 len: Lazy<u32, KeyType>,
112 #[cfg_attr(feature = "std", codec(skip))]
120 len_cached: CachedLen,
121 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 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 #[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 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 pub fn is_empty(&self) -> bool {
243 self.len() == 0
244 }
245
246 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 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 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 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 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 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 pub fn get(&self, index: u32) -> Option<V> {
360 self.elements.get(index)
361 }
362
363 pub fn try_get(&self, index: u32) -> Option<ink_env::Result<V>> {
372 self.elements.try_get(index)
373 }
374
375 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 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 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 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 Lazy::<u32>::new().set(&u32::MAX);
737
738 let _ = array.len();
740
741 Ok(())
742 })
743 .unwrap()
744 }
745}