ic_storage/adapter/vector/
mod.rs1use 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
23pub 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 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 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 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 #[must_use]
116 pub fn get(&self, index: u64) -> Option<T> {
117 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 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 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 #[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 #[must_use]
179 pub fn len(&self) -> u64 {
180 let _ = self.memory.size();
181 self.length.get()
182 }
183
184 #[must_use]
189 pub fn is_empty(&self) -> bool {
190 self.len() == 0
191 }
192
193 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#[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 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 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 #[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 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;