Skip to main content

ic_storage/adapter/vector/
mod.rs

1//! Governed indexed storage with an independent bounded-slot format.
2//!
3//! The exclusive lease owns the committed-length cache. Allocation, backing
4//! custody, and transaction rollback remain the runtime and host's responsibility.
5
6use std::{borrow::Cow, cell::Cell, marker::PhantomData};
7
8use crate::{
9    DefaultMemoryImpl, Memory, RuntimeMemory,
10    storable::{Bound, Storable},
11};
12
13use super::error::{CollectionError as Error, Result};
14
15const HEADER_BYTES: usize = 32;
16const DATA_OFFSET: u64 = 32;
17const LENGTH_OFFSET: u64 = 24;
18const PAGE_BYTES: u64 = 65_536;
19const MAGIC: &[u8; 8] = b"STORVECT";
20const VERSION: u32 = 1;
21const STACK_BYTES: usize = 64;
22
23///
24/// `StableVec`
25///
26/// A persistent vector over one exclusive, admitted allocation lease.
27///
28/// Elements require a finite codec bound. Length is cached by this owner after
29/// read-only admission and updated only after successful persistent mutations;
30/// observing length checks owner health without reading backing bytes.
31///
32pub struct StableVec<T: Storable, M: Memory = DefaultMemoryImpl> {
33    memory: RuntimeMemory<M>,
34    layout: Layout,
35    length: Cell<u64>,
36    element: PhantomData<T>,
37}
38
39impl<T: Storable, M: Memory> StableVec<T, M> {
40    /// Creates an empty vector in an empty allocation.
41    ///
42    /// # Errors
43    /// Returns `NotEmpty` for a nonempty allocation or `Growth` if the initial
44    /// header reservation is refused.
45    ///
46    /// # Panics
47    /// Panics for an unbounded codec, a poisoned owner, or a backing IO failure.
48    pub fn create(memory: RuntimeMemory<M>) -> Result<Self> {
49        if memory.size() != 0 {
50            return Err(Error::NotEmpty);
51        }
52        Self::reset(memory)
53    }
54
55    /// Explicitly replaces the allocation's image with an empty vector.
56    /// Unreachable previous payload bytes need not be erased.
57    ///
58    /// # Errors
59    /// Returns `Growth` if the initial header reservation is refused.
60    ///
61    /// # Panics
62    /// Panics for an unbounded codec, a poisoned owner, or a backing IO failure.
63    pub fn reset(memory: RuntimeMemory<M>) -> Result<Self> {
64        #[cfg(not(target_arch = "wasm32"))]
65        let _guard = memory.poison_on_unwind();
66        let layout = Layout::for_bound(T::BOUND);
67        if !reserve(&memory, DATA_OFFSET) {
68            return Err(Error::Growth);
69        }
70        memory.write(0, &layout.header(0));
71        Ok(Self {
72            memory,
73            layout,
74            length: Cell::new(0),
75            element: PhantomData,
76        })
77    }
78
79    /// Admits the current vector image without modifying its bytes.
80    /// Admission validates framing, codec bounds and the complete live extent,
81    /// without decoding or scanning records.
82    ///
83    /// # Errors
84    /// Returns `Format` for empty, foreign, unsupported or truncated framing,
85    /// or a length whose occupied extent cannot be represented or is absent.
86    ///
87    /// # Panics
88    /// Panics for an unbounded or incompatible codec, a poisoned owner, or a
89    /// backing IO failure.
90    pub fn load(memory: RuntimeMemory<M>) -> Result<Self> {
91        let layout = Layout::for_bound(T::BOUND);
92        if memory.size() == 0 {
93            return Err(Error::Format);
94        }
95        let mut header = [0; HEADER_BYTES];
96        memory.read(0, &mut header);
97        let length = layout.admit_header(&header)?;
98        let end = layout.extent(length).ok_or(Error::Format)?;
99        if !contains(&memory, end) {
100            return Err(Error::Format);
101        }
102        Ok(Self {
103            memory,
104            layout,
105            length: Cell::new(length),
106            element: PhantomData,
107        })
108    }
109
110    /// Decodes one live record, or returns `None` when the index is absent.
111    ///
112    /// # Panics
113    /// Panics for a poisoned owner, corrupt selected record, codec failure or
114    /// backing IO failure. Unselected records are not decoded.
115    #[must_use]
116    pub fn get(&self, index: u64) -> Option<T> {
117        // Selected reads check owner health while admitting the complete slot.
118        if index >= self.length.get() {
119            let _ = self.memory.size();
120            return None;
121        }
122        Some(read_value(&self.memory, self.layout, index))
123    }
124
125    /// Replaces one existing record without changing the length.
126    ///
127    /// # Panics
128    /// Panics for an absent index, a poisoned owner, codec failure, declared-bound
129    /// violation or backing IO failure. Native mutation unwinding poisons the owner.
130    pub fn set(&self, index: u64, item: &T) {
131        #[cfg(not(target_arch = "wasm32"))]
132        let _guard = self.memory.poison_on_unwind();
133        assert!(index < self.len(), "vector index out of bounds");
134        let bytes = encode(item, self.layout);
135        write_value(&self.memory, self.layout, index, &bytes);
136    }
137
138    /// Appends one record and commits its new length after the record is written.
139    ///
140    /// # Panics
141    /// Panics for a poisoned owner, codec failure, declared-bound violation,
142    /// arithmetic overflow, growth refusal or backing IO failure. Native mutation
143    /// unwinding poisons the owner.
144    pub fn push(&self, item: &T) {
145        #[cfg(not(target_arch = "wasm32"))]
146        let _guard = self.memory.poison_on_unwind();
147        let length = self.len();
148        let next = length.checked_add(1).expect("vector length overflow");
149        let end = self.layout.extent(next).expect("vector extent overflow");
150        let bytes = encode(item, self.layout);
151        assert!(reserve(&self.memory, end), "vector growth refused");
152        write_value(&self.memory, self.layout, length, &bytes);
153        self.commit_length(next);
154    }
155
156    /// Removes and returns the final record, or returns `None` when empty.
157    ///
158    /// # Panics
159    /// Panics for a poisoned owner, corrupt selected record, codec failure or
160    /// backing IO failure. Native mutation unwinding poisons the owner.
161    #[must_use]
162    pub fn pop(&self) -> Option<T> {
163        #[cfg(not(target_arch = "wasm32"))]
164        let _guard = self.memory.poison_on_unwind();
165        let Some(index) = self.length.get().checked_sub(1) else {
166            let _ = self.memory.size();
167            return None;
168        };
169        let value = read_value(&self.memory, self.layout, index);
170        self.commit_length(index);
171        Some(value)
172    }
173
174    /// Returns the locally cached committed length after checking owner health.
175    ///
176    /// # Panics
177    /// Panics if the owner has been poisoned.
178    #[must_use]
179    pub fn len(&self) -> u64 {
180        let _ = self.memory.size();
181        self.length.get()
182    }
183
184    /// Returns whether the committed length is zero.
185    ///
186    /// # Panics
187    /// Panics if the owner has been poisoned.
188    #[must_use]
189    pub fn is_empty(&self) -> bool {
190        self.len() == 0
191    }
192
193    /// Iterates within the length observed at creation, reading current values.
194    /// Advancing, skipping or counting permanently truncates the remaining
195    /// endpoint to the current length. Removed records are never read; replacements or
196    /// re-appends inside an unconsumed endpoint may be observed. Appends beyond
197    /// the original endpoint are excluded, and exhaustion is permanent.
198    /// Skipping and counting do not decode unselected records.
199    ///
200    /// # Panics
201    /// Panics for a poisoned owner. Selecting a record may panic for corrupt
202    /// data, codec failure or backing IO failure. Counting panics if the remaining
203    /// length cannot fit in `usize`.
204    pub fn iter(&self) -> impl DoubleEndedIterator<Item = T> + '_ {
205        Iter {
206            vector: self,
207            front: 0,
208            back: self.len(),
209        }
210    }
211
212    fn commit_length(&self, length: u64) {
213        self.memory.write(LENGTH_OFFSET, &length.to_le_bytes());
214        self.length.set(length);
215    }
216}
217
218// The format is deliberately uniform: fixed values occupy `maximum` bytes;
219// variable values prepend a u32 length within a `maximum + 4` byte slot.
220// Header bytes 17..24 are reserved and must remain zero in version 1.
221#[derive(Clone, Copy, Debug, Eq, PartialEq)]
222struct Layout {
223    maximum: u32,
224    fixed: bool,
225}
226
227impl Layout {
228    const fn for_bound(bound: Bound) -> Self {
229        match bound {
230            Bound::Bounded {
231                max_size,
232                is_fixed_size,
233            } => Self {
234                maximum: max_size,
235                fixed: is_fixed_size,
236            },
237            Bound::Unbounded => panic!("vector requires a finite codec bound"),
238        }
239    }
240
241    fn stride(self) -> u64 {
242        u64::from(self.maximum) + if self.fixed { 0 } else { 4 }
243    }
244
245    fn extent(self, length: u64) -> Option<u64> {
246        length.checked_mul(self.stride())?.checked_add(DATA_OFFSET)
247    }
248
249    fn header(self, length: u64) -> [u8; HEADER_BYTES] {
250        let mut header = [0; HEADER_BYTES];
251        header[..8].copy_from_slice(MAGIC);
252        header[8..12].copy_from_slice(&VERSION.to_le_bytes());
253        header[12..16].copy_from_slice(&self.maximum.to_le_bytes());
254        header[16] = u8::from(self.fixed);
255        header[24..32].copy_from_slice(&length.to_le_bytes());
256        header
257    }
258
259    fn admit_header(self, header: &[u8; HEADER_BYTES]) -> Result<u64> {
260        if &header[..8] != MAGIC
261            || header[8..12] != VERSION.to_le_bytes()
262            || header[16] > 1
263            || header[17..24] != [0; 7]
264        {
265            return Err(Error::Format);
266        }
267        assert!(
268            header[12..16] == self.maximum.to_le_bytes() && header[16] == u8::from(self.fixed),
269            "vector codec bound does not match its admitted image"
270        );
271        let mut length = [0; 8];
272        length.copy_from_slice(&header[24..32]);
273        Ok(u64::from_le_bytes(length))
274    }
275
276    fn check_length(self, length: usize) {
277        let length = u64::try_from(length).expect("vector record length overflow");
278        assert!(
279            length <= u64::from(self.maximum) && (!self.fixed || length == u64::from(self.maximum)),
280            "vector record violates its codec bound"
281        );
282    }
283}
284
285fn contains(memory: &impl Memory, end: u64) -> bool {
286    memory.size() >= end.div_ceil(PAGE_BYTES)
287}
288
289fn reserve(memory: &impl Memory, end: u64) -> bool {
290    let pages = end.div_ceil(PAGE_BYTES);
291    let current = memory.size();
292    pages <= current || Memory::grow(memory, pages - current) >= 0
293}
294
295fn encode<T: Storable>(item: &T, layout: Layout) -> Cow<'_, [u8]> {
296    let bytes = item
297        .to_bytes()
298        .unwrap_or_else(|_| panic!("vector encoding failed"));
299    layout.check_length(bytes.len());
300    bytes
301}
302
303fn write_value(memory: &impl Memory, layout: Layout, index: u64, bytes: &[u8]) {
304    let end = layout
305        .extent(index.checked_add(1).expect("vector index overflow"))
306        .expect("vector extent overflow");
307    assert!(contains(memory, end), "vector record extends beyond memory");
308    // The checked complete extent also proves the slot's starting offset.
309    let mut offset = end - layout.stride();
310    if !layout.fixed {
311        let length = u32::try_from(bytes.len()).expect("vector record length overflow");
312        memory.write(offset, &length.to_le_bytes());
313        offset += 4;
314    }
315    if !bytes.is_empty() {
316        memory.write(offset, bytes);
317    }
318}
319
320fn read_value<T: Storable>(memory: &impl Memory, layout: Layout, index: u64) -> T {
321    let end = layout
322        .extent(index.checked_add(1).expect("vector index overflow"))
323        .expect("vector extent overflow");
324    assert!(contains(memory, end), "vector record extends beyond memory");
325    // The checked complete extent also proves the slot's starting offset.
326    let mut offset = end - layout.stride();
327    let length = if layout.fixed {
328        layout.maximum
329    } else {
330        let mut bytes = [0; 4];
331        memory.read(offset, &mut bytes);
332        offset += 4;
333        u32::from_le_bytes(bytes)
334    };
335    assert!(
336        length <= layout.maximum,
337        "vector record exceeds its codec bound"
338    );
339    let length = usize::try_from(length).expect("vector record length overflow");
340    if length <= STACK_BYTES {
341        let mut buffer = [0; STACK_BYTES];
342        if length != 0 {
343            memory.read(offset, &mut buffer[..length]);
344        }
345        T::from_bytes(Cow::Borrowed(&buffer[..length]))
346            .unwrap_or_else(|_| panic!("vector decoding failed"))
347    } else {
348        let mut buffer = Vec::with_capacity(length);
349        // SAFETY: the complete slot was admitted above, and the bounded payload
350        // lies within it. The fresh allocation has at least `length` writable
351        // bytes and cannot overlap backing. Successful read_unsafe initializes
352        // every byte; an unwinding read leaves the vector length at zero.
353        #[expect(
354            unsafe_code,
355            reason = "Publish only bytes initialized by the admitted backing read"
356        )]
357        unsafe {
358            memory.read_unsafe(offset, buffer.as_mut_ptr(), length);
359            buffer.set_len(length);
360        }
361        T::from_bytes(Cow::Owned(buffer)).unwrap_or_else(|_| panic!("vector decoding failed"))
362    }
363}
364
365struct Iter<'a, T: Storable, M: Memory> {
366    vector: &'a StableVec<T, M>,
367    front: u64,
368    back: u64,
369}
370
371impl<T: Storable, M: Memory> Iter<'_, T, M> {
372    // Callers observe owner health either directly or through selected-slot admission.
373    fn remaining(&mut self) -> u64 {
374        self.back = self.back.min(self.vector.length.get());
375        self.front = self.front.min(self.back);
376        self.back - self.front
377    }
378}
379
380impl<T: Storable, M: Memory> Iterator for Iter<'_, T, M> {
381    type Item = T;
382
383    fn next(&mut self) -> Option<Self::Item> {
384        self.nth(0)
385    }
386
387    fn nth(&mut self, n: usize) -> Option<Self::Item> {
388        let n = u64::try_from(n).unwrap_or(u64::MAX);
389        if n >= self.remaining() {
390            let _ = self.vector.memory.size();
391            self.front = self.back;
392            return None;
393        }
394        let index = self.front + n;
395        self.front = index + 1;
396        Some(read_value(&self.vector.memory, self.vector.layout, index))
397    }
398
399    fn size_hint(&self) -> (usize, Option<usize>) {
400        let length = self.back.min(self.vector.len()).saturating_sub(self.front);
401        usize::try_from(length).map_or((usize::MAX, None), |length| (length, Some(length)))
402    }
403
404    fn count(mut self) -> usize {
405        let _ = self.vector.memory.size();
406        usize::try_from(self.remaining()).expect("vector iterator count exceeds usize")
407    }
408
409    fn last(mut self) -> Option<Self::Item> {
410        self.next_back()
411    }
412}
413
414impl<T: Storable, M: Memory> DoubleEndedIterator for Iter<'_, T, M> {
415    fn next_back(&mut self) -> Option<Self::Item> {
416        self.nth_back(0)
417    }
418
419    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
420        let n = u64::try_from(n).unwrap_or(u64::MAX);
421        if n >= self.remaining() {
422            let _ = self.vector.memory.size();
423            self.back = self.front;
424            return None;
425        }
426        self.back -= n + 1;
427        Some(read_value(
428            &self.vector.memory,
429            self.vector.layout,
430            self.back,
431        ))
432    }
433}
434
435#[cfg(test)]
436mod format_tests;