ic_storage/adapter/
vector.rs

1//! Owned fixed-stride slots with bounded, checksummed values and a Wire root.
2use super::{
3    Memory, Storable,
4    error::{CollectionError as Error, Result, ensure},
5    record,
6};
7use crate::{DefaultMemoryImpl, RuntimeMemory, hash};
8use serde::{Deserialize, Serialize};
9use std::{borrow::Cow, cell::Cell, marker::PhantomData};
10
11const MAGIC: [u8; 8] = *b"ICVECC01";
12const DATA: u64 = record::HEADER_BYTES;
13const SLOT_HEADER: usize = 12;
14
15#[derive(Clone, Serialize, Deserialize)]
16struct Root {
17    length: u64,
18    bound: (u32, bool),
19}
20
21///
22/// `StableVec`
23///
24/// Indexed stable values in fixed-stride slots. Values require a finite bound.
25/// Each slot protects its index, length and payload with an integrity checksum.
26/// Native interrupted writes poison the owner and may damage retained bytes.
27///
28pub struct StableVec<T: Storable, M: Memory = DefaultMemoryImpl> {
29    memory: RuntimeMemory<M>,
30    length: Cell<u64>,
31    poisoned: Cell<bool>,
32    record: PhantomData<T>,
33}
34
35impl<T: Storable, M: Memory> StableVec<T, M> {
36    /// Create only in an empty allocation. Invalid bounds refuse before writes.
37    ///
38    /// # Errors
39    /// Rejects nonempty memory, invalid encoding/bounds or capacity refusal before writing.
40    pub fn create(memory: RuntimeMemory<M>) -> Result<Self> {
41        ensure(memory.size() == 0, Error::NotEmpty)?;
42        Self::reset(memory)
43    }
44    /// Explicitly discard previous contents in this allocation.
45    ///
46    /// # Errors
47    /// Rejects invalid encoding/bounds or capacity refusal before replacing contents.
48    pub fn reset(memory: RuntimeMemory<M>) -> Result<Self> {
49        let bytes = Self::header(0)?;
50        record::reserve(&memory, DATA)?;
51        memory.write(0, &bytes);
52        Ok(Self {
53            memory,
54            length: Cell::new(0),
55            poisoned: Cell::new(false),
56            record: PhantomData,
57        })
58    }
59    /// Read and validate the current root without initializing or writing.
60    ///
61    /// # Errors
62    /// Rejects foreign, corrupt or oversized records and incompatible codec bounds.
63    pub fn load(memory: RuntimeMemory<M>) -> Result<Self> {
64        let root: Root = record::read(&memory, 0, DATA, MAGIC)?;
65        ensure(
66            root.bound == Self::bound()?,
67            Error::Corrupt("vector codec bound changed"),
68        )?;
69        ensure(
70            Self::end(root.length)?
71                <= memory
72                    .size()
73                    .checked_mul(crate::WASM_PAGE_SIZE_BYTES)
74                    .ok_or(Error::Budget)?,
75            Error::Corrupt("vector length exceeds memory"),
76        )?;
77        Ok(Self {
78            memory,
79            length: Cell::new(root.length),
80            poisoned: Cell::new(false),
81            record: PhantomData,
82        })
83    }
84    fn bound() -> Result<(u32, bool)> {
85        record::bound::<T>().ok_or(Error::Corrupt("vector requires a finite value bound"))
86    }
87    fn end(length: u64) -> Result<u64> {
88        let stride = u64::from(Self::bound()?.0) + SLOT_HEADER as u64;
89        DATA.checked_add(length.checked_mul(stride).ok_or(Error::Budget)?)
90            .ok_or(Error::Budget)
91    }
92    fn header(length: u64) -> Result<Vec<u8>> {
93        let bytes = record::encode(
94            MAGIC,
95            &Root {
96                length,
97                bound: Self::bound()?,
98            },
99        )?;
100        ensure(bytes.len() as u64 <= DATA, Error::Budget)?;
101        Ok(bytes)
102    }
103    fn healthy(&self) -> Result<()> {
104        ensure(!self.poisoned.get(), Error::Poisoned)
105    }
106
107    /// Decode an indexed value, checking length and checksum before its codec.
108    ///
109    /// # Errors
110    /// Reports structural, integrity or application decoding failures without writing.
111    ///
112    /// # Panics
113    /// Propagates backing panics or a faulty caller codec.
114    pub fn get(&self, index: u64) -> Result<Option<T>> {
115        let mut bytes = Vec::new();
116        if !self.read_slot(index, &mut bytes)? {
117            return Ok(None);
118        }
119        Ok(Some(T::from_bytes(Cow::Owned(bytes))?))
120    }
121    fn read_slot(&self, index: u64, bytes: &mut Vec<u8>) -> Result<bool> {
122        self.healthy()?;
123        if index >= self.length.get() {
124            return Ok(false);
125        }
126        let offset = Self::end(index)?;
127        let (maximum, fixed) = Self::bound()?;
128        let mut header = [0; SLOT_HEADER];
129        if fixed {
130            let size = SLOT_HEADER
131                .checked_add(maximum as usize)
132                .ok_or(Error::Budget)?;
133            bytes.resize(size, 0);
134            self.memory.read(offset, bytes);
135            header.copy_from_slice(&bytes[..SLOT_HEADER]);
136            bytes.copy_within(SLOT_HEADER.., 0);
137            bytes.truncate(maximum as usize);
138        } else {
139            self.memory.read(offset, &mut header);
140        }
141        let length = u32::from_le_bytes(header[..4].try_into().unwrap());
142        ensure(
143            length <= maximum && (!fixed || length == maximum),
144            Error::Corrupt("vector slot length exceeds bound"),
145        )?;
146        if !fixed {
147            bytes.resize(length as usize, 0);
148            self.memory.read(offset + SLOT_HEADER as u64, bytes);
149        }
150        let digest = u64::from_le_bytes(header[4..].try_into().unwrap());
151        ensure(
152            checksum(index, &header[..4], bytes) == digest,
153            Error::Checksum,
154        )?;
155        T::check_bounds(bytes)?;
156        Ok(true)
157    }
158    /// Replace an existing value. Encoding and bounds admission precede writes.
159    ///
160    /// # Errors
161    /// Rejects invalid indices, encoding, bounds or capacity refusal before writes.
162    pub fn set(&self, index: u64, item: &T) -> Result<()> {
163        self.healthy()?;
164        ensure(index < self.length.get(), Error::Bounds)?;
165        let bytes = item.to_bytes_checked()?;
166        self.write_slot(index, &bytes)
167    }
168    fn write_slot(&self, index: u64, bytes: &[u8]) -> Result<()> {
169        let offset = Self::end(index)?;
170        let mut header = [0; SLOT_HEADER];
171        let length = u32::try_from(bytes.len()).map_err(|_| Error::Budget)?;
172        header[..4].copy_from_slice(&length.to_le_bytes());
173        let digest = checksum(index, &header[..4], bytes);
174        header[4..].copy_from_slice(&digest.to_le_bytes());
175        self.poisoned.set(true);
176        self.memory.write(offset + SLOT_HEADER as u64, bytes);
177        self.memory.write(offset, &header);
178        self.poisoned.set(false);
179        Ok(())
180    }
181    /// Append after reserving capacity; publish the new length last.
182    ///
183    /// # Errors
184    /// Rejects invalid encoding, bounds, arithmetic overflow or capacity refusal before writes.
185    pub fn push(&self, item: &T) -> Result<()> {
186        self.healthy()?;
187        let bytes = item.to_bytes_checked()?;
188        let length = self.length.get().checked_add(1).ok_or(Error::Budget)?;
189        let header = Self::header(length)?;
190        record::reserve(&self.memory, Self::end(length)?)?;
191        self.write_slot(length - 1, &bytes)?;
192        self.poisoned.set(true);
193        self.memory.write(0, &header);
194        self.length.set(length);
195        self.poisoned.set(false);
196        Ok(())
197    }
198    /// Remove the final value, retaining allocated capacity for reuse.
199    ///
200    /// # Errors
201    /// Rejects integrity, decoding or structural errors before changing the length.
202    pub fn pop(&self) -> Result<Option<T>> {
203        self.healthy()?;
204        let Some(length) = self.length.get().checked_sub(1) else {
205            return Ok(None);
206        };
207        let value = self.get(length)?;
208        let header = Self::header(length)?;
209        self.poisoned.set(true);
210        self.memory.write(0, &header);
211        self.length.set(length);
212        self.poisoned.set(false);
213        Ok(value)
214    }
215    /// Number of committed slots. A poisoned owner must be dropped.
216    ///
217    /// # Panics
218    /// A poisoned owner must be dropped before further observation.
219    pub fn len(&self) -> u64 {
220        self.healthy().expect("vector owner is poisoned");
221        self.length.get()
222    }
223    /// Whether the vector has no values.
224    pub fn is_empty(&self) -> bool {
225        self.len() == 0
226    }
227    /// Decode slots lazily, returning errors without panicking on malformed data.
228    pub fn iter(&self) -> impl DoubleEndedIterator<Item = Result<T>> + '_ {
229        let mut bytes = Vec::new();
230        (0..self.len()).map(move |index| {
231            ensure(self.read_slot(index, &mut bytes)?, Error::Bounds)?;
232            Ok(T::from_bytes(Cow::Borrowed(&bytes))?)
233        })
234    }
235}
236
237fn checksum(index: u64, length: &[u8], bytes: &[u8]) -> u64 {
238    let digest = hash::fnv64(hash::FNV_OFFSET, &index.to_le_bytes());
239    hash::fnv64(hash::fnv64(digest, length), bytes)
240}
ic_storage/adapter/vector.rs

ic_storage/adapter/
vector.rs
