A way to iterate and push to a vector at the same time. Is this sound? Are there any existing crates implementing this?

help
1

I read from the book Programming Rust that you can't have:

// waves is a Vec
waves.extend(&wave);

But this is perfectly fine as long as you preallocate enough capacity since it's not violating the mutation xor aliasing rule: you are mutating [len.. capacity] part of the vector but only aliasing [..len] part. So, I wrote this as a PoC.

Playground

use core::slice::from_raw_parts;
use core::marker::PhantomData;

pub struct Reserved<'item: 'collection, 'collection, T: 'item, C: 'collection + ExtLen> {
    ptr: *mut T,
    capacity: usize,
    len: usize,
    c: &'collection mut C,
    _marker: std::marker::PhantomData<&'item T>,
}

pub trait ExtLen {
    unsafe fn ext_len(&mut self, len: usize);
}

impl<'item, 'collection, T: 'item, C: 'collection + ExtLen> Reserved<'item, 'collection, T, C>
where
    'item: 'collection,
{
    pub fn push(&mut self, t: T) -> Result<(), ()> {
        if self.capacity > 0 {
            unsafe {
                self.ptr.add(self.len).write(t);
            }
            self.capacity -= 1;
            self.len += 1;
            Ok(())
        } else {
            Err(())
        }
    }

    pub fn done(self) {
        drop(self)
    }
}

impl<'item, 'collection, T: 'item, C: 'collection + ExtLen> Drop
    for Reserved<'item, 'collection, T, C>
where
    'item: 'collection,
{
    fn drop(&mut self) {
        unsafe {
            self.c.ext_len(self.len);
        }
    }
}

pub trait VecExt: Sized + ExtLen {
    type Item;
    fn reserve_and_write(&mut self, n: usize) -> (&[Self::Item], Reserved<Self::Item, Self>);
}

impl<T> ExtLen for Vec<T> {
    unsafe fn ext_len(&mut self, len: usize) {
        self.set_len(self.len() + len);
    }
}

impl<T> VecExt for Vec<T> {
    type Item = T;

    fn reserve_and_write(&mut self, n: usize) -> (&[T], Reserved<Self::Item, Self>) {
        self.reserve_exact(n);
        let ptr = unsafe { self.as_mut_ptr().add(self.len()) };
        (
            unsafe { from_raw_parts(self.as_ptr(), self.len()) },
            Reserved {
                ptr,
                capacity: n,
                len: 0,
                c: self,
                _marker: PhantomData,
            },
        )
    }
}


fn main() {
    let mut v: Vec<_> = (0..10).collect();
    let (old, mut new) = v.reserve_and_write(v.len());
    for value in old {
        new.push(*value).unwrap();
    }
    new.done();
    println!("{:?}", v);
}

Since this involves unsafe code, are there any existing established crates that offers similar functionalities?

2

I'd instead step back and ask: what do you need this for? It seems like a bad idea, maybe you could restructure your code to achive your higher-level goal in another way.

3

What you're trying to workaround here is called iterator invalidation, which is a common source of single threaded concurrency issue. C++ triggers UB, Java throws with runtime check, Rust fails to compile on it. Usual workaround is to create separate vector during iteration and append it into the original one after the iteration is over.

4

I know, but as long as you have enough capacity in your vector, there won't be any reallocation. The code I wrote above is trying to exploit this.

This would cause one extra allocation, and one extra move per element.

5

I read from the book Programming Rust that you can't have:

// waves is a Vec
waves.extend(&wave);

But this is perfectly fine as long as you preallocate enough capacity since it's not violating the mutation xor aliasing rule: you are mutating [len.. capacity] part of the vector but only aliasing [..len] part. So, I wrote this as a PoC. I'm just asking if there are any established crates that can do this since this involves unsafe code.

1 Like
6

Yes, uninit can do this for you.

Specifically the VecCapacity::split_at_extra_cap method allows splitting the vector into an initialized and an uninitialized part. The only difference is that it provides a mutable reference for the initialized slice also, just since that is possible and slightly more generic. But you'll need to manually increment the length when you're done.

2 Likes
7

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.