A project of mine required me to dive into unsafe Rust and when I was done with it, I had understood something that I wanted to share. However, since I wasn’t sure if I made any subtle mistakes, I did ask the community to review my code and oh boy did it turn out that I had missed some vital things. Bear with me and hopefully you’ll gather something useful, too.

A Warning

Be warned that most (possibly all) the examples in this post contain unsafe code with bugs of varying subtlety. Do not blindly copy code from here. If you read till the end you’ll learn why you will likely never have to bother with the particular code in this post… and also that you’ve been using it already, maybe unknowingly.

If you spot errors in this article please do reach out either via the commentary on this page or shoot me a mail using the link at the bottom of this page.

The Task At Hand: In Place Mapping

The task we’re trying to tackle here is to transform a Vec<T> into a Vec<U> in place, given that types T and U have the same memory layout, i.e. the same size and alignment. Transforming in place means we are reusing the storage of the initial vector. Our mapping function will look something like this:

fn map_in_place<T,U,F>(v: Vec<T>, mut f: F) -> Vec<U> 
    where F: FnMut(T) -> U {
    assert_eq!(std::alloc::Layout::<T>::new(), 
        std::alloc::Layout::<U>::new());

    todo!()
}

Vec<T> does not expose an obvious, high level, and safe API to accomplish what we want ¹, so we have to dive into unsafe. The rest of this article is concerned with replacing the todo!(), but let’s take a step back first.

Unsafe Rust Confusion

I’ve struggled a lot with understanding when and how to use unsafe Rust. Part of the reason is that there is a (very justified) hesitation to use unsafe code within the Rust ecosystem and it’s a clear plus when a crate advertises itself as written in 100% safe Rust ². Then add to that some overly simplistic semtiments I’ve come across such as unsafe Rust is not about circumventing the borrow checker. I think this implanted the idea in my head that I could spot incorrect usage of unsafe code by the mere fact that it was “circumventing the borrow checker”, whatever that meant. It turned out that this wasn’t much of a help that and I needed a better mental model.

Unsafe Is Not About Circumventing Anything

A very important realization for me was to stop thinking about whether or not I was circumventing the borrow checker with unsafe Rust. I’ll try to reframe it in this section. The first thing to realize is that the interaction between the borrow checker and unsafe is too narrow of a view. It’s about the interaction of the fundamental language rules of Rust with unsafe code. The borrow checker is a well known part of the Rust language and it enforces the aliasing rules. It’s an important part of what makes safe Rust memory safe, but it’s only a part of what gives the language its safety guarantees.

The second thing to realize is that unsafe does not change any fundamental rules of the language and so it also does not, for example, turn off the borrow checker. Take a look at this invalid Rust code:

// does not compile
let x = 10;
let r1 = &mut x;
let r2 = &mut x;
// ...

The compiler will reject this code because we are violating one of Rust’s basic assumptions by trying to take two mutable references to one piece of data ³. Merely placing the same code into an unsafe block does not make it valid Rust code. The aliasing rules for references apply everywhere, so the compiler will always assume they are true. It will stop you from violating them wherever it can.

unsafe {
  // still rejected
  let mut x = 10;
  let r1 = &mut x;
  let r2 = &mut x;
  // ...
}

Now let’s look at this example, where we use unsafe to eventually obtain two mutable references:

let mut x = 10;
let ptr: *mut i32 = &mut x;
unsafe {
  let r1 = &mut *ptr;
  let r2 = &mut *ptr;
  // ...
}

This code compiles, so we have just circumvented Rust’s Borrow Checker using unsafe, haven’t we? In a way yes, but that is not a helpful way to think about it. The problem is not that we have done something that the borrow checker would not allow us to do, the problem is that we have violated the aliasing rules of the language when we used the powers bestowed upon us via the unsafe keyword. In unsafe Rust, the compiler lets us work with raw pointers (who are outside the scope of the borrow checker) but it expects us to still adhere to the rules of the language. In this case we have created two mutable references to one piece of data, which breaks the aliasing rules.

The compiler always assumes that the language rules apply and subsequently that two mutable references can never point to the same memory. It is allowed to optimize our program as if that assumption is always true and that will, in turn, result in the dreaded undefined behavior… even in an unsafe block because –and I know I am belaboring this point– unsafe Rust still assumes the rules of safe Rust are unbroken.

Detecting Rule Violations

At this point you might be wondering if there are any tools to help you detect rule violations and the answer is Miri. It is an analysis tool that can run your program or test suite and detect certain kinds of undefined behavior by using an interpreter for Rust’s mid-level IR. You can use it as a cargo plugin with cargo miri run or cargo miri test.

This is immensely helpful for finding some classes of undefined behavior, but there are some caveats. Because Miri is an interpreter it is much slower than the compiled binary, so running your whole test suite or program might not be feasible. Furthermore it works by running your code through the interpreter and in this sense it works at runtime. That means even if it is theoretically able to detect a source of undefined behavior (UB), you must actually hit the UB during a run. This is all the more reason to have an exhaustive test suite for your unsafe code and keep in mind that are certain classes of UB that Miri does not detect regardless.

Unsafe as a Gateway

Among other things, unsafe gives us the power to dereference raw pointers and to call unsafe functions ⁴. The language rules that apply to references are not enforced on raw pointers. That is not an accident but one of the defining features of pointers. We are able to use them to write correct programs that the borrow checker would reject because it errs on the side of caution. A famous example is implementing doubly linked lists.

In unsafe Rust it is now our responsibility to enforce the language rules. It is especially easy to make mistakes when transitioning from unsafe constructs to safe constructs, like we did above when transitioning from pointers to references ⁵. In unsafe land we are able to express things that we cannot in safe Rust, such as I need multiple mutable references to one piece of data. You must never actually use two mutable references (even if you trick the compiler) but it is perfectly fine to use two pointers to the same data. In fact, pointers are exactly the language construct we should use for that particular problem, because there is no way to express the same intent in safe Rust ⁶.

let mut x = 10;
let p1: *mut i32 = &mut x;
let p2 = p1;
unsafe {
  // ...
}

This is perfectly fine Rust code ⁷ and the compiler will not break our code by making assumptions about what the pointers can or can’t point to. Again, it would not be very helpful to frame this as circumventing the borrow checker, because the same thing could be said about the broken code futher above. We have now stepped into unsafe land and there is things we can do in unsafe land that we cannot simply do in safe land. If you only think of the part where we are “circumventing” the borrow checker both code snippets would be equivalent, but they are not. Using unsafe code to express things we cannot express in safe Rust is one of the major usecases of unsafe. On the other hand, using unsafe code to make safe language constructs behave in forbidden ways is an abuse.

So one of the lessons for me was to learn to use unsafe constructs more comfortably and not try to weasel my way back into safe constructs as soon as possible. However, I’ve found the ergonomics of using unsafe constructs (such as pointers) much more cumbersome than using safe language constructs (such as references) and that makes it very tempting to cross the border prematurely and write broken code. Let’s take a look how all of this applies to our in place mapping problem.

The Transformative Unsafe Journey

Armed with the understanding above I set out on my journey of implementing
the in-place mapping function. I was not going to make the rookie mistake of using pointers to get me some illegal references, no siree. I was going to stay in pointer-land as long as I needed to and everything would be fine… so I thought.

A Clear, Simple (and Wrong) Solution

So let’s have a look at a first solution that avoids the obvious error of violating Rust’s aliasing rules and does quite a few things correctly.

fn map_in_place<T,U,F>(v: Vec<T>, mut f: F) -> Vec<U> 
where F: FnMut(T) -> U {
    assert_eq!(Layout::new::<T>(), Layout::new::<U>());
    unsafe {
        // (1)
        let (pstart, len, cap) = v.into_raw_parts();
        // (2)
        for pt in (0..len).map(|j| pstart.add(j)) {
            // (3)
            let t = pt.read();
            let u = f(t);
            // (4)
            let pu: *mut U = pt.cast();
            pu.write(u);
        }
        // (5)
        Vec::from_raw_parts(pstart.cast(), len, cap)
    }
}

I should mention that the latest stable Rust version at the time of writing is Rust 1.71, which is probably not terribly important but it should be noted nonetheless. The code above uses the unstable Vec::into_raw_parts API just for clarity. The effect can be very easily replicated in stable Rust.

Let’s pretend that this was my first draft of the code ⁸. Before we go into the problems with this function let’s look at the code line by line. After making sure the types T and U have the same memory layout, ① we destructure the vector to obtain its raw parts: The pointer pstart to the first element, the number of elements len, and the capacity cap. ② Then we iterate through the elements of the vector via the pointer pt of type *mut T. ③ Now we read the element into our stack variable t and transform it into an element u of type U. Using pt.read() makes this work even for non-Copy elements because it will just perform a simple memory copy. ④ Then we obtain a second pointer to the element that we are iterating over. This pointer pu is a of type *mut U. We are using cast rather than as to cast the pointer, which is a good practice because it will catch changes in mutability at compile time ⁹. Then we write the transformed value to the memory location using pu. Note that we are using pu.write(u) instead of *pu = u because the latter must drop the value behind the pointer before assigning to it to avoid possible memory leaks ¹⁰. This would be a giant problem because the contained value would be dropped as if it was of type U, but is actually of type T ¹¹. If we use write the pointed-to value does intentionally not get dropped. ⑤ Finally we piece a new Vec<U> together from the transformed storage.

You can see that we already took care of a lot of details that are easy to miss and yet the logic is still broken. Let’s see why.

Panic Safety

Yes, panic safety. Coming from a C++ background it’s something that I should be much more mindful of, but I usually forget to take it into account. The reason is that panics in Rust are semantically very different from exceptions and the general advice is not to just catch them as you would catch exceptions in C++. And while by default a panic will unwind the stack and call destructors in an orderly fashion, that behavior can be changed to just abort. In essence, this is what makes it easy (at least for me) to forget that code should behave correctly even in case of a panic, whether or not a user relies on it.

When the function f panics at some point during the loop there are three things we need to make sure ¹²: Firstly, we need to call the destructors of all elements that have been transformed to type U. Secondly, we need to call the destructors of all the remaining elements of type T and thirdly we need to deallocate the storage of the vector to prevent a memory leak ¹³. One solution to do this is to implement a helper structure that keeps track of the elements while they are transitioning from T to U and take care that they are appropriately dropped in case of a panic. First we create an untagged union and the helper structure like so:

union Union<T, U> {
    pub first: ManuallyDrop<T>,
    pub second: ManuallyDrop<U>,
}

struct TransitioningVec<T, U> {
    vector: Vec<Union<T, U>>,
    u_len: usize,
}

The union type is our way of allowing us to store the elements in a vector regardless of whether they are of type T or U. Then, when vector is dropped it will free the storage correctly, but it cannot call the destructors. We have to do that ourselves and for that we have to keep track of the number of elements u_len that have been transformed from T to U. The reason that we enclosed the types of the union variants in a ManuallyDrop is that the compiler cannot know which variant a union holds (since they are not tagged, like enums), so it cannot call the appropriate destructors. Hence we are not allowed to use types that have nontrivial destructors as union variants. To create this helper structure from our initial Vec<T> instance we write this constructor:

impl<T, U> TransitioningVec<T, U> {
    pub fn new(v: Vec<T>) -> Self {
        assert_eq!(Layout::new::<T>(), Layout::new::<U>());
        let (ptr,len,cap) = v.into_raw_parts();
        let data = unsafe { Vec::from_raw_parts(ptr.cast(), len, cap) };
        Self {
            vector: data,
            u_len: 0,
        }
    }
}

We set the number of transformed elements to zero and we change the data type of the vector, so that we can store both Ts and Us in it but we leave the actual data untouched. Before we get to the implementation of the mapping functionality, we need to implement Drop for our helper structure so it can act appropriately when it is dropped while the elements are still transitioning:

impl<T, U> Drop for TransitioningVec<T, U> {
    fn drop(&mut self) {
        let start = self.vector.as_mut_ptr();
        unsafe {
            let u_slice :&mut [U] = std::slice::from_raw_parts_mut(
                start.cast(),
                self.u_len);
            let t_slice :&mut [T] = std::slice::from_raw_parts_mut(
                start.add(self.u_len).cast(),
                self.vector.len() - self.u_len,
            );
            std::ptr::drop_in_place(u_slice);
            std::ptr::drop_in_place(t_slice);
        }
    }
}

We will transform elements from “left to right” and we keep track of the number u_len of transformed elements. This allows us to split the memory into two slices of elements, first of type U and the second of type T. We then drop those slices individually, making sure that the appropriate destructors are called. If you are like me, then you might be tempted to loop over the elements individually and drop them. Don’t do that, the Rust typesystem is your friend and it will understand that you are dropping slices and it will do the correct thing for you ¹⁴.

Finally we can implement the actual functionality in an associated function like so:

impl<T, U> TransitioningVec<T, U> {
    #[inline]
    pub fn map_in_place<F: FnMut(T) -> U>(mut self, mut f: F) -> Vec<U> {
        // (1)
        let start_ptr: *mut T = self.vector.as_mut_ptr().cast();
        while self.u_len < self.vector.len() {
            unsafe {
                let t_ptr = start_ptr.add(self.u_len);
                let u_ptr: *mut U = t_ptr.cast();
                let t = t_ptr.read();
                u_ptr.write(f(t));
            }
            self.u_len += 1;
        }
        // (2)
        let mut me = ManuallyDrop::new(self);
        unsafe {
            Vec::from_raw_parts(
                me.vector.as_mut_ptr().cast(),
                me.vector.len(),
                me.vector.capacity(),
            )
        }
    }
}

① This loop is conceptually identical to the one we had previously, but now we keep track of the number of elements we have transformed. If the function f panics at any point, the destructor of our TransitioningVec instance will get invoked and destroy the elements appropriately and free the allocated storage allocated by dropping its vector field. ② Here all elements have completed their transformation, so we are making sure that the destructor of our instance does not get called anymore and we return a Vec<U> that is now the sole owner of the transformed elements and the allocated storage.

Since we don’t want to expose this helper type publicly, we hide it in the map_in_place free function like so:

fn map_in_place<T, U, F>(v: Vec<T>, f: F) -> Vec<U>
where
    F: FnMut(T) -> U,
{
    TransitioningVec::new(v).map_in_place(f)
}

And voilà we’re done… or are we?

Is That It? All Good Now?

No. For example, we haven’t handled zero sized types yet. The code above implicitly assumes that the elements of the vector have a nonzero size in memory. I think that is the last piece of the puzzle to make this sound, but please do reach out if there is more unsound code in my examples or mistakes in my explanations.

Update: More Mistakes

What follows is a collection of additional problems pointed out by readers.

Panic Double Drop

This one was pointed out by reddit user u/MaxVerevkin here. Say the function f panics when we transform the element at index n. This means the u_len will hold the index n at which the panic occurred, since it would get incremented only after f returns. The element at this index will get dropped twice: once when the scope of the mapping function ends and once when we drop the slice of Ts in the destructor. That’s a problem. Their solution is to replace this line in the destructor

let t_slice: &mut [T] = std::slice::from_raw_parts_mut(
    start.add(self.u_len).cast(),
    self.vector.len() - self.u_len,
);

with

let t_slice: &mut [T] = std::slice::from_raw_parts_mut(
    start.add(self.u_len + 1).cast(),
    self.vector.len() - self.u_len - 1,
);

This makes sense to me since the element at position u_len will have been dropped as a T when the mapping function unwound its stack. Further, we can only enter the destructor of our helper when vector.len() >= 1 and u_len < len.

Further Reading

Before we come to the long overdue end of this long winded article, let me give you some reading recommendations if you want to dive deeper. If you’ve been following along with the endnotes you’ve already seen the forum post I made in which many helpful individuals were kind enough to point out mistakes and give helpful suggestions. I owe all of them a big thank-you. And if you want to dive more into unsafe Rust there is this brilliant series and of course the Rustonomicon which provides a thorough treatise of unsafe Rust. Also a long time ago there used to exist an unstable standard library API with the exact same purpose (and name) as our map_in_place. You can look at it’s long removed implementation here.

How To Do It Safely

Okay. Somewhere further above I alluded to the fact that there was a better way of doing all this. One that does not require us to deal with the unsafe details first hand. But didn’t I just write that map_in_place was never stabilized and the whole functionality got removed? Not quite, the magic happens somewhere else now. The way to do the in-place transformation of a vector in today’s Rust (1.71 at the time of writing) is:

v.into_iter().map(f).collect()

Don’t take my word for it, try it on godbolt. And yes, I know: you’re not getting the 15 minutes of your life back (unless you scrolled ahead in which case shame on you 😆).

The iterator implementations are smart enough below the hood to specialize implementations in case the types T and U have the same memory layout and so they will perform the transformation without reallocating. This fact is not explicitly guaranteed or documented but I was pretty mind blown when I learned this. This is truly a zero cost abstraction if I ever saw one.

Endnotes