Replace vec with slice, ub?

pub struct FooVector<T> {
    data: Vec<T>,}

impl<T> FooVector<T> {
    pub fn new() -> Self {
        FooVector { data: vec![]}}

    pub fn add(&mut self, e: T) {
        self.data.push(e);}

    pub fn take(&mut self) -> Option<T> {
        self.data.pop()}}

Suppose we know before hand that data will never have more than 8 elements. And we want to embed a slice, i..e something like:

struct FooSlice<T> {
  data: [T; 8]
}

now, it is not guaranteed that T implements default. Is there a way to implement new/add/take as above without UB for FooSlice ?

EDIT: I would also prefer to avoid the overhead of data: [Option<T>; 8]

You can use arrayvec crate.

6 Likes

Interesting. Thanks! Quoting arrayvec.rs - source :

pub struct ArrayVec<T, const CAP: usize> {
    // the `len` first elements of the array are initialized
    xs: [MaybeUninit<T>; CAP],
    len: LenUint,
}

so it appears the solution is to use MaybeUninit and be really really careful.

MaybeUninit is also where I ended up writing this by hand. In fact, I came up with something almost identical to ArrayVec (which you should use instead):

#![feature(maybe_uninit_uninit_array)]
use std::mem::MaybeUninit;

/// Safety invariant:
///    self.data[i] is always initialized for all i < self.len  
pub struct FooVector<T, const CAP:usize> {
    data: [MaybeUninit<T>;CAP],
    len: u8
}

impl<T, const CAP:usize> FooVector<T, CAP> {
    pub fn new() -> Self {
        FooVector {
            data: MaybeUninit::uninit_array(),
            len: 0
        }
    }

    pub fn add(&mut self, e: T) {
        assert!((self.len as usize) < self.data.len());
        let slot = self.data[self.len as usize].as_mut_ptr();
        unsafe { std::ptr::write(slot, e); }
        self.len += 1
    }

    pub fn take(&mut self) -> Option<T> {
        if self.len == 0 { None }
        else {
            self.len -= 1;
            let slot = self.data[self.len as usize].as_ptr();
            Some(unsafe{std::ptr::read(slot)})
        }
    }
}


impl<T, const CAP:usize> Drop for FooVector<T, CAP> {
    fn drop(&mut self) {
        // Drop all items in take() order
        while let Some(_) = self.take() {}
    }
}

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=e1d7d30a043e567c76867820e04e9727

3 Likes

Note this will leak memory if you try to add more than 255 elements. Because of integer wrap around.

1 Like

Strictly speaking, it should be defined this way, but it requires const_evaluatable_checked which isn't complete:

Problem statement says <= 8.

Sure, but not everyone reading will have the same requirements. Best to mention subtle pitfalls when they crop up, for future readers. This case is also easy enough to prevent. Just check if length is u8::MAX and panic if it is.

1 Like

The simplest place for that assertion is inside new(); there's no point in making an array with more slots than the rest of the code can use:

    pub fn new() -> Self {
        assert!(CAP <= (u8::MAX as usize));
        FooVector {
            data: MaybeUninit::uninit_array(),
            len: 0
        }
    }

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=79e2168658d4e997168741550d36a55a

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.