Implementing `Vec` part 2: `insert`, `remove`, `Deref`, `IntoIter`

pub fn vec2_script(ops: Vec<String>) -> Vec<String>

Extend the MyVec<String> from item 17.16 with insert, remove, Deref/DerefMut to a slice, and a real IntoIter. The starter hands you the finished part-1 vector; everything below it is yours.

copy versus copy_nonoverlapping, for real this time

Item 17.8 stated the rule; this is where it bites.

Shifting elements to make room is a memmove, always. When insert moves [index .. len] one place to the right, the source and destination ranges overlap by len - index - 1 elements. That is not an edge case you might hit; it is the geometry of the operation.

ptr::copy(p.add(index), p.add(index + 1), self.len - index);            // right
ptr::copy_nonoverlapping(p.add(index), p.add(index + 1), n);            // UB

copy_nonoverlapping compiles to memcpy, whose contract permits it to copy in any order, in any block size, in either direction. For a one-element move it happens to be fine. For a three-element move it may still be fine. For a 1000-element move on a machine with wide vector stores it will duplicate a block and lose one — silently, on some inputs and not others.

The sort 1000 elements case exists to make that failure mode reachable.

::: question remove(index) reads the element out and then shifts the tail left. Does the order matter? Yes, and getting it backwards is a double free.

Shift first and slot index is overwritten by its right-hand neighbour — bit-for-bit, without dropping the String that was there. That value’s heap buffer is now unreachable (a leak), and worse, the value you then read out of slot index is the neighbour, which also still lives at index + 1. Two owners, one allocation.

Read first, then shift, and lower len before the shift so that the tail’s arithmetic and Drop‘s idea of the live window agree at every moment. :::

Deref is where MyVec gets an API it never wrote

impl<T> Deref for MyVec<T> {
    type Target = [T];
    fn deref(&self) -> &[T] {
        // SAFETY: ...
        unsafe { std::slice::from_raw_parts(self.ptr.as_ptr(), self.len) }
    }
}

Those four lines give MyVec<T> iter, sort, binary_search, windows, chunks, first, last, contains, join, concat, indexing, slicing and every other slice method, for free. It is the cleanest demonstration in the standard library that most of Vec‘s API is not Vec‘s at all — Vec is three fields, an allocator strategy, and a Deref.

Two things must be exactly right.

The length is len, never cap. A slice of length cap exposes uninitialised memory as &T, which is undefined behaviour the instant the slice exists, before anybody reads it.

from_raw_parts demands a non-null, aligned pointer even for length zero. That is precisely why the empty vector stores NonNull::dangling() rather than a null pointer — the dangling sentinel is aligned, so a zero-length slice built from it is valid.

IntoIter: exactly one thing owns the allocation

This is the best exercise in the track for “two things believe they own this”.

IntoIterator::into_iter(self) takes the vector by value. It must:

1. take the ptr, len and cap out of it;
2. stop the MyVec from running its destructor — ManuallyDrop::new(self), or mem::forget, or deconstructing it field by field;
3. hand the allocation to the IntoIter, which now owns it alone.

If you skip step 2, the MyVec‘s Drop runs at the end of into_iter, frees the buffer, and the iterator walks freed memory. If you do step 2 but forget to free in IntoIter::drop, you leak the whole allocation.

IntoIter::next yields by ptr::read and advances start. IntoIter::drop must drop only the unyielded elements — the ones between start and end — and then deallocate with the layout cap describes. Yielded elements belong to whoever took them.

::: question A drain_take 2 on a four-element vector collects two strings and then drops the iterator. What exactly must the iterator’s destructor do? Drop two strings — the ones at start .. end — and free a four-slot allocation.

Those two numbers come from different places and that is the whole point. start and end describe the unyielded window, which is what still needs destructors. cap describes the allocation, which is what needs freeing, and it never shrinks as the iterator advances.

Dropping four would double-free the two the caller took. Dropping zero would leak them. Freeing with a two-element layout would hand the allocator a size it never issued.

The drain_take 2 case in this problem then pushes more elements into a fresh vector, so a damaged heap has an immediate opportunity to fall over. :::

Lints to expect

clippy::should_implement_trait if you name an inherent method into_iter instead of implementing IntoIterator. clippy::len_without_is_empty if you drop the is_empty you wrote in part 1. clippy::mem_replace_with_default if you write mem::replace(&mut v, MyVec::new()) where mem::take would do — and it does, because you implemented Default.

clippy::mem_forget is restriction/allow: it will not fire, so nothing stops you using mem::forget in into_iter if you prefer it to ManuallyDrop. Both are correct; ManuallyDrop is easier to read because the intent is in the type rather than in a call.

What this grader cannot check

A leak is invisible — if IntoIter::drop frees the buffer without dropping the unyielded elements, everything here passes. A double free usually aborts, and the harness allocates two thousand strings afterwards to give a corrupted heap something to trip on, but “usually” is doing real work in that sentence.

Remember the grade is compile + tests + clippy -D warnings.