field projections: basic borrow checking

the borrow checker is one of the most important features of Rust. as part of my work on field projections, we need to come up with a way to generalize it and expose its inner workings via traits. in this post, I’m presenting my model of the borrow checker in the current design for field projections (which has moved to https://github.com/rust-lang/beyond-refs now). in this post, I’m focusing on the more basic pointers that we’ll support; mainly custom &T, &mut T and Box<T>. more advanced pointers will come later in another post.

# overview

the borrow checker performs its analysis on each function separately. it consumes the control flow using MIR basic blocks (which is a more fine-grained control flow representation that the surface level syntax) and monitors every access to every place. it assumes that all place expressions used in a function are pointing at distinct places .

# borrow checker state

for every place expression, the borrow checker tracks its state, which consists of the following:

initialization state: Uninit, Init
loan state: None, Shared(Vec<Lifetime>), Exclusive(Lifetime)

the mapping that tracks this state needs to ensure consistency with regards to the tree structure of place expressions. for example:

let point = Point { x: 42, y: -42 };
// A
let p = &point;
// B
let x = &point.x;
// C
println!("{p:?} and {x}");

the only places of interest in this example are point.x, point.y and their parent point. at B, the entire point is borrowed by p, but at C, point.x is in addition also borrowed by x. to express this situation in our model, we have to add a Mixed loan state; in this state, the place’s doesn’t have one global loan state, as different children are loaned differently. for the reverse situation (e.g. in B), we also add a Parent loan state, which children get that don’t have a custom one.

we also replicate this split for the init state, where we add Parent and Partial.

we can now express the three points of interests from the example in a table:

label	`point`	`point.x`	`point.y`
A	`Init + None`	`Parent + Parent`	`Parent + Parent`
B	`Init + Shared('p)`	`Parent + Parent`	`Parent + Parent`
C	`Init + Mixed`	`Parent + Shared('p, 'x)`	`Parent + Shared('p)`

# tracking place operations

the operations that one can perform on places originating from &T and &mut T are pretty simple:

reading: let value = *ptr;
writing: *ptr = value;
shared borrowing: &*ptr
exclusive borrowing: &mut *ptr

all of these operations correspond to a state assertion on the place that it’s operating on and a transition of the state to a new one. for simplicity, we’ll be ignoring Parent and Partial/Mixed states. this is possible, since in the Parent case, we can just read the state of the parent instead. with Partial/Mixed, we can instead perform the operation recursively on every child.

row	operation	matched init state	matched loan state	state change(s)
1	reading (1)	`Init`	`None`	`Init + None`
2	reading (1)	`Init`	`Shared(lts)`	`Init + Shared(lts)`
3	reading (1)	`Init`	`Exclusive(lt)`	`Init + Shared([lt])`
4	writing (2)	any	any	`Init + None`
5	shared borrow (3)	`Init`	`None`	`Init + Shared(['l])`
6	shared borrow (3)	`Init`	`Shared(lts)`	`Init + Shared(lts + ['l])`
7	shared borrow (3)	`Init`	`Exclusive(lt)`	`Init + Shared([lt] + ['l])`
8	exclusive borrow (4)	`Init`	any	`Init + Exclusive('l)`

a few notes explaining the table:

the lifetime 'l used in the new state, is a fresh lifetime that the borrow checker creates.
in this table, we can see that any shared access downgrades existing exclusive ones to shared (shown in rows 3 and 7).
except for writing, all operations require initialized data.
any lifetime that is dropped, is ended by the borrow checker. for example, in the exclusive borrow operation (4), if the loan state is Shared(['l1]), then this lifetime is ended, since it’s dropped by us replacing the state with Exclusive('l).

# translating this concept into knobs on the place operation traits

we start with the current model from the design repo (stripping any experimental borrow checking stuff that’s already there):

pub unsafe trait PlaceHandle {
    type Target: ?Sized;
}

pub unsafe trait ReadPlace: PlaceHandle {
    const SAFE: bool;

    fn read_place(self) -> Self::Target;
}

pub unsafe trait MovePlace: ReadPlace {}

pub unsafe trait WritePlace: PlaceHandle {
    const SAFE: bool;

    fn write_place(self, value: Self::Target);
}

pub unsafe trait BorrowPlace<Output>: PlaceHandle {
    const SAFE: bool;

    fn borrow_place(self) -> Output;
}

pub unsafe trait DropPlace: PlaceHandle {
    fn drop_place(self);
}

pub unsafe trait PlaceProxy {
    type Target: ?Sized;
}

pub unsafe trait DropHusk: PlaceProxy + LocalBorrow {
    fn drop_husk(handle: Self::Handle<'_>);
}

the LocalBorrow trait will be explained in the section on LocalHandle.

impls for &T and &mut T

struct RefHandle<'a, T: ?Sized + 'a> {
    ptr: *const T,
    lt: PhantomData<&'a T>,
}

impl<'a, T: ?Sized + 'a> PlaceHandle for RefHandle<'a, T> {
    type Target = T;
}

unsafe impl<'a, T: 'a> ReadPlace for RefHandle<'a, T> {
    const SAFE: bool = true;

    fn read_place(self) -> Self::Target {
        unsafe { self.ptr.read() }
    }
}

unsafe impl<'a, 'b, T> BorrowPlace<&'b T> for RefHandle<'a, T>
where
    T: ?Sized + 'a,
    'a: 'b,
{
    const SAFE: bool = true;

    fn borrow_place(self) -> &'b T {
        unsafe { self.ptr.as_ref() }
    }
}

struct MutHandle<'a, T: ?Sized + 'a> {
    ptr: *mut T,
    lt: PhantomData<&'a T>,
}

impl<'a, T: ?Sized + 'a> PlaceHandle for MutHandle<'a, T> {
    type Target = T;
}

unsafe impl<'a, T: 'a> ReadPlace for MutHandle<'a, T> {
    const SAFE: bool = true;

    fn read_place(self) -> Self::Target {
        unsafe { self.ptr.read() }
    }
}

unsafe impl<'a, T: 'a> WritePlace for MutHandle<'a, T> {
    const SAFE: bool = true;

    fn write_place(self, value: T) {
        unsafe { self.ptr.write(value) }
    }
}

unsafe impl<'a, 'b, T> BorrowPlace<&'b T> for MutHandle<'a, T>
where
    T: ?Sized + 'a,
    'a: 'b,
{
    const SAFE: bool = true;

    fn borrow_place(self) -> &'b T {
        unsafe { self.ptr.as_ref() }
    }
}

unsafe impl<'a, 'b, T> BorrowPlace<&'b mut T> for MutHandle<'a, T>
where
    T: ?Sized + 'a,
    'a: 'b,
{
    const SAFE: bool = true;

    fn borrow_place(self) -> &'b mut T {
        unsafe { self.ptr.as_mut() }
    }
}

# `&T` and `&mut T`

if we only wanted to support custom &T and &mut T, then our model would be quite simple:

WritePlace and ReadPlace don’t need any borrow checker knobs, since their assertion and transition do not create any lifetimes.
BorrowPlace is a bit different in that we need to record which type of borrow (shared or exclusive) we want. and we also want to tie the lifetime that the borrow checker assigns to the loan to be passed to us for passing it to the output type of the borrow.
```
pub unsafe trait BorrowPlace</* new */ 'b, Output: 'b>: PlaceHandle {
    const SAFE: bool;
    /* new */ const EXCLUSIVE: bool;

    fn borrow_place(self) -> Output;
}
```

here are the changed impls:

unsafe impl<'a, 'b, T> BorrowPlace<'b, &'b T> for RefHandle<'a, T>
where
    T: ?Sized + 'a,
    'a: 'b,
{
    const SAFE: bool = true;
    const EXCLUSIVE: bool = false;

    fn borrow_place(self) -> &'b T {
        unsafe { self.ptr.as_ref() }
    }
}

unsafe impl<'a, 'b, T> BorrowPlace<'b, &'b T> for MutHandle<'a, T>
where
    T: ?Sized + 'a,
    'a: 'b,
{
    const SAFE: bool = true;
    const EXCLUSIVE: bool = false;

    fn borrow_place(self) -> &'b T {
        unsafe { self.ptr.as_ref() }
    }
}

unsafe impl<'a, 'b, T> BorrowPlace<'b, &'b mut T> for MutHandle<'a, T>
where
    T: ?Sized + 'a,
    'a: 'b,
{
    const SAFE: bool = true;
    const EXCLUSIVE: bool = true;

    fn borrow_place(self) -> &'b mut T {
        unsafe { self.ptr.as_mut() }
    }
}

this approach already ensures that borrows of local variables cannot escape the function body, since we always have the 'a: 'b constraint. if 'b were to escape the function, but 'a be local, then we’d get an error.

note that we haven’t yet discussed LocalPlace though, so we can’t actually take a borrow of a local variable yet; we’ll get to that now.

# borrowing locals

we can model borrowing a local via the following definitions:

pub struct LocalPlace<T /*: ?Sized (when we have unsized locals again)*/>(T);

pub struct LocalHandle<'a, T: 'a> {
    ptr: *const T,
    lt: PhantomData<&'a mut T>,
}

we give this handle the same operations as MutHandle.

unsafe impl<'a, 'b, T> BorrowPlace<'b, &'b T> for LocalHandle<'a, T>
where
    'a: 'b,
{
    const SAFE: bool = true;
    const EXCLUSIVE: bool = false;

    fn borrow_place(self) -> &'b T {
        unsafe { self.ptr.as_ref() }
    }
}

unsafe impl<'a, 'b, T> BorrowPlace<'b, &'b mut T> for LocalHandle<'a, T>
where
    'a: 'b,
{
    const SAFE: bool = true;
    const EXCLUSIVE: bool = true;

    fn borrow_place(self) -> &'b mut T {
        unsafe { self.ptr.cast_mut().as_mut() }
    }
}

unsafe impl<'a, T: 'a> ReadPlace for LocalHandle<'a, T> {
    const SAFE: bool = true;

    fn read_place(self) -> Self::Target {
        unsafe { self.ptr.read() }
    }
}

unsafe impl<'a, T: 'a> WritePlace for LocalHandle<'a, T> {
    const SAFE: bool = true;

    fn write_place(self, value: T) {
        unsafe { self.ptr.cast_mut().write(value) }
    }
}

to allow it to also move values out (and back in), we need the following impls on its handle:

unsafe impl<'a, T: 'a> MovePlace for LocalHandle<'a, T> {}

unsafe impl<'a, T: 'a> DropPlace for LocalHandle<'a, T> {
    fn drop_place(self) {
        unsafe { self.ptr.cast_mut().drop_in_place() }
    }
}

but in order to have DropPlace, the proxy needs to implement DropHusk, for which we still need to give the supertrait LocalBorrow:

pub unsafe trait LocalBorrow: PlaceProxy {
    type Handle<'l>: 'l
    where
        Self::Target: 'l;

    unsafe fn local_borrow<'l>(local: *const Self) -> Self::Handle<'l>
    where
        Self::Target: 'l;
}

the lifetime 'l is always chosen by the borrow checker to end at the end of the function.

now we can implement DropHusk for LocalPlace:

unsafe impl<T> DropHusk for LocalPlace<T> {
    fn drop_husk(handle: Self::Handle<'_>) {}
}

impl<T: ?Sized> LocalBorrow for LocalPlace<T> {
    type Handle<'l>
    where
        T: 'l,
    = LocalHandle<'l, T>;

    unsafe fn local_borrow<'l>(ptr: *const Self) -> Self::Handle<'l, T>
    where
        T: 'l,
    {
        LocalHandle { ptr: ptr.cast(), lt: PhantomData }
    }
}

the LocalBorrow impl of LocalPlace is a bit special, since the only way the compiler can call it is by casting the pointer beforehand. here’s an example:

let x = ...;

let y = &x;
// desugars to:
let y = unsafe {
    BorrowPlace::<'_1, &_>::borrow_place(LocalHandle::local_borrow::<'_0>(
        (&raw const x).cast(),
    ))
};
// end the lifetime `'_0` here, which in turn also ends `'1`

# `Box<T>`

we already support Box<T>, since, it’s just like LocalPlace, but not containing the value “directly”.

Box<T>'s handle impls

pub struct BoxHandle<'a, T: 'a> {
    ptr: *const T,
    lt: PhantomData<&'a mut T>,
}

unsafe impl<'a, 'b, T> BorrowPlace<'b, &'b T> for BoxHandle<'a, T>
where
    'a: 'b,
{
    const SAFE: bool = true;
    const EXCLUSIVE: bool = false;

    fn borrow_place(self) -> &'b T {
        unsafe { self.ptr.as_ref() }
    }
}

unsafe impl<'a, 'b, T> BorrowPlace<'b, &'b mut T> for BoxHandle<'a, T>
where
    'a: 'b,
{
    const SAFE: bool = true;
    const EXCLUSIVE: bool = true;

    fn borrow_place(self) -> &'b mut T {
        unsafe { self.ptr.cast_mut().as_mut() }
    }
}

unsafe impl<'a, T: 'a> ReadPlace for BoxHandle<'a, T> {
    const SAFE: bool = true;

    fn read_place(self) -> Self::Target {
        unsafe { self.ptr.read() }
    }
}

unsafe impl<'a, T: 'a> WritePlace for BoxHandle<'a, T> {
    const SAFE: bool = true;

    fn write_place(self, value: T) {
        unsafe { self.ptr.cast_mut().write(value) }
    }
}

unsafe impl<'a, T: 'a> MovePlace for BoxHandle<'a, T> {}

unsafe impl<'a, T: 'a> DropPlace for BoxHandle<'a, T> {
    fn drop_place(self) {
        unsafe { self.ptr.cast_mut().drop_in_place() }
    }
}

unsafe impl<T> DropHusk for LocalPlace<T> {
    fn drop_husk(handle: Self::Handle<'_>) {}
}

impl<T> LocalBorrow for Box<T> {
    type Handle<'l>
    where
        T: 'l,
    = BoxHandle<'l, T>;

    unsafe fn local_borrow<'l>(ptr: *const Self) -> Self::Handle<'l, T>
    where
        T: 'l,
    {
        let ptr: Unique<T> = unsafe { (*ptr).ptr };
        BoxHandle { ptr: ptr.as_raw(), lt: PhantomData }
    }
}

# conclusion

we only had to modify the BorrowPlace trait in order to accommodate the existing pointers in our model to have the borrow checker work with our traits instead of the builtin operations. this makes sense, since we’ve merged shared and exclusive borrowing into one trait and all operations are kept separate otherwise.

we also changed the way local variables are borrowed, since we need to keep track of their lifetimes in order to prevent returning data owned by the current function.

in the next post on this topic, I want to take a look at:

weird initialization changes on borrowing: &own T and &uninit T
shared pointers with write capabilities: LRef<'_, T>
raw & unsafe pointers: *const T and *mut T and NonNull<T>

further down the line, we’ll take a look at even weirder ones such as UniqueArcRef<T>.