Replace vec with slice, ub?

[anon80458984]

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]

[Hyeonu]

You can use arrayvec crate.

[anon80458984]

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.

[2e71828]

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() {}
    }
}

Rust Playground

[RustyYato]

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

[2e71828]

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

@2e71828

pub struct FooVector<T, const CAP:u8> {
    data: [MaybeUninit<T>; CAP as usize],
    len: u8
}

[anon80458984]

@RustyYato

more than 255 elements

Problem statement says <= 8.

@anon80458984

Suppose we know before hand that data will never have more than 8 elements.

[RustyYato]

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.

[2e71828]

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
        }
    }

Rust Playground