Further simplifying self-referential types for Rust
— 2024-07-08

In my last post I discussed how we might be able to introduce ergonomic self-referential types (SRTs) to Rust, mostly by introducing features we know we want in some form anyway. The features listed were:

Some form of 'unsafe and 'self lifetimes.
A safe out-pointer notation for Rust (super let / -> super Type).
A way to introduce out-pointers without breaking backwards-compat.
A new Move auto-trait that can be used to mark types as immovable (!Move).
View types which make it possible to safely initialize self-referential types.

This post was received quite well, and I thought the discussion which followed was quite interesting. I learned about a number of things that I think would help refine the design further, and I thought it would be good to write it up.

Not all self-referential types are `!Move`

Niko Matsakis pointed out that not all self-referential types are necessarily !Move. For example: if the data being referenced is heap-allocated, then the type doesn't actually have to be !Move. When writing protocol parsers, it's actually fairly common to read data into a heap-allocated type first. It seems likely that a fair number of self-referential types don't actually also need to be !Move or any concept of Move at all to function. Which also means we don't need some form of super let / -> super Type to construct types in-place.

If we just want to enable self-references for heap-allocated types, then all we need for that is a way to initialize them (view types) and an ability to describe the self-lifetimes ('unsafe as a minimum). That should give us a good idea of what we can prioritize to begin enabling a limited form of self-references.

The `'self` lifetime is insufficient

Speaking of lifetimes, Mattieum pointed out that 'self likely wasn't going to be enough. 'self points to an entire struct, which ends up being too coarse to be practical. Instead we need to be able to point to individual fields to describe lifetimes.

Apparently Niko has also come up with a feature for this, in the form of lifetimes based on places. Rather than having abstract lifetimes like the 'a that we use to link to values with, it would be nicer if references just always had implicit, unique lifetime names. With access to that, we should rewrite the motivating example from our last post from being based on 'self:

struct GivePatsFuture {
    resume_from: GivePatsState,
    data: Option<String>,
    name: Option<&'self str>,        // ← Note the `'self` lifetime
}

To instead be based on paths:

struct GiveManyPatsFuture {
    resume_from: GivePatsState,
    first: Option<String>,
    data: Option<&'self.first str>, // ← Note the `'self.first` lifetime
}

This might not seem like it's that important in this example; but once we introduce mutability things quickly spiral. And not introducing a magic 'self in favor of always requiring 'self.field seems like it would generally be better. And that requires having lifetimes which can be based on places, which seems like a great idea regardless.

Automatic referential stability

Earlier in this post we established that we don't actually need to encode !Move for self-referential types which store their values on the heap. That's not all self-referential types - but does describe a fair number of them. Now what if we didn't need to encode !Move for almost the entire remaining set of self-referential types?

If that sounds like move constructors, you'd be right - but with a catch! Unlike the Relocate trait I described in my last post, DoveOfHope noted that we might not even need that to work. After all: if the compiler already knows that we're pointing to a field contained within the struct - can't the compiler make sure to update the pointers when we try and move the structure?

I was skeptical about the possibility of this until I read about place-based lifetimes. With that it seems like we would actually have enough granularity to know how to update which fields when they are moved. In terms of cost: that's just updating the value of a pointer on move - which is effectively free. And it would rid us almost entirely of needing to encode !Move.

The only cases not covered by this would be 'unsafe references or actual *const T / *mut T pointers to stack data. The compiler doesn't actually know what those point to, and so cannot update them on move. For that some form of Relocate trait actually seems like it would be useful to have. But that's something that wouldn't need to be added straight away either.

Raw pointer operations and automatic referential stability

This section was added after publication, on 2024-07-08.

While it should be possible for the compiler to guarantee that the codegen is correct for e.g. mem::swap, we can't make those same guarantees for raw pointer operations such as ptr::swap. And because existing structures may be freely using those operations internally, that means on-stack self-referential types can't just be made to work without any caveats the way we can for on-heap SRTs. That's indeed a problem, and I want to thank The_8472 for pointing this out.

I was really hoping to be able to avoid extra bounds, so that on-stack SRTs could match the experience of on-heap SRTs. But that doesn't seem possible, so perhaps some minimum amount of bounds which we can flip to being set by default (like Sized) over an edition might be enough to do the trick here. I'm currently thinking of something like:

Introduce a new auto marker trait Transfer to complement Relocate, as a dual to Rust's Destruct / Drop system. Transfer is the name of the bound people would use, Relocate provides the hooks to extend the Transfer system.
All types with 'self lifetimes automatically implement Transfer.
Only bounds which include + Transfer can take impl Transfer types.
All relevant raw pointer move operations must uphold additional safety invariants of what to do with impl Transfer types.
We gradually update the stdlib to support + Transfer in all bounds.
Over some edition we make opt-out rather than opt-in (T: Transfer → T: ?Transfer).

auto trait Transfer {}

trait Relocate { ... }

I was really hoping we could avoid something like this. And it does put into question whether this is actually simpler than immovable types. But the_8472 is quite right that this is an issue, and so we need to address it. Luckily we've already done something like this before with const. And I don't think that this is something we can generalize. I'll write more about this at some later date.

`Relocate` should probably take `&own self`

Now, even if we don't expect people to need to write their own pointer update logic, basically like ever, it's still something that should be provided. And when we do, we should encode it correctly. Nadrieril very helpfully pointed out that the &mut self bound on the Relocate trait might not actually be what we want - because we're not just borrowing a value - we actually want to destruct it. Instead they informed me about the work done towards &own, which would give access to something called: "owned references".

Daniel Henry-Mantilla is the author of the stackbox crate as well as the main person responsible for the lifetime extension system behind the pin! macro in the stdlib. A while back he shared a very helpful writeup about &own. The core of the idea is that we should decouple the concepts of: "Where is the data concretely stored?" from: "Who logically owns the data?" Resulting in the idea of having a reference which doesn't just provide temporary unique access - but can take permanent unique access. In his post, Daniel helpfully provides the following table:

	Semantics for `T`	For the backing allocation
`&T`	Shared access	Borrowed
`&mut T`	Exclusive access	Borrowed
`&own T`	Owned access (drop responsibility)	Borrowed

Applying this to our post, we would use this to change the trait Relocate from taking &mut self, which temporarily takes exclusive access of a type - but can't actually drop the type:

trait Relocate {
    fn relocate(&mut self) -> super Self;
}

To instead take &own, which takes permanent exclusive access of a type, and can actually drop the type:

trait Relocate {
    fn relocate(&own self) -> super Self;
}

edit 2024-07-08: This example was added later. To explain what &own solves, let's take a look at the Relocate example impl from our last post. In it we say the following:

We're making one sketchy assumption here: we need to be able to take the owned data from self, without running into the issue where the data can't be moved because it is already borrowed from self.

struct Cat {
    data: String,
    name: &'self str,
}
impl Cat {
    fn new(data: String) -> super Self { ... }
}
impl Relocate for Cat {
    fn relocate(&mut self) -> super Self {
        let mut data = String::new();                   // ← dummy type, does not allocate
        mem::swap(&mut self.data, &mut data);           // ← take owned data
        super let cat = Cat { data };                   // ← construct new instance
        cat.name = cat.data.split(' ').next().unwrap(); // ← create self-ref
        cat                                             // ← return new instance
    }
}

What &own gives us is a way to correctly encode the semantics here. Because the type is not moved we can't actually move by-value. But logically we do still want to claim unique ownership of the value so we can destruct the type and move individual fields. That's kind of the way moving Box by-value works too, but rather than having the allocation on the heap, the allocation can be anywhere. With that we could rewrite the rather sketchy mem::swap code above into more normal-looking destructuring + initialization instead:

struct Cat {
    data: String,
    name: &'self str,
}
impl Cat {
    fn new(data: String) -> super Self { ... }
}
impl Relocate for Cat {
    fn relocate(&mut self) -> super Self {
        let Self { data, .. } = self;                   // ← destruct `self`
        super let cat = Cat { data };                   // ← construct new instance
        cat.name = cat.data.split(' ').next().unwrap(); // ← create self-ref
        cat                                             // ← return new instance
    }
}

Now, because this actually does need to construct types in fixed memory locations this trait would need to have some form of -> super Self syntax. After all: this would be the one place where it would still be needed. For anyone interested in keeping up to date with &own, here is the Rust issue for it (which also happens to have been filed by Niko).

Motivating example, reworked again

With this in mind, we can rework the motivating example from the last post once again. To refresh everyone's memory, this is the high-level async/.await-based Rust code we would:

async fn give_pats() {
    let data = "chashu tuna".to_string();
    let name = data.split(' ').take().unwrap();
    pat_cat(&name).await;
    println!("patted {name}");
} 

async fn main() {
    give_pats().await;
}

And using the updates in this post we can proceed to desugar it. This time around without the need for any reference to Move or in-place construction, thanks to path-based lifetimes and the compiler automatically preserving referential stability:

enum GivePatsState {
    Created,
    Suspend1,
    Complete,
}

struct GivePatsFuture {
    resume_from: GivePatsState,
    data: Option<String>,
    name: Option<&'self.data str>, // ← Note the `'self.data` lifetime
}
impl GivePatsFuture {   // ← No in-place construction needed
    fn new() -> Self {
        Self {
            resume_from: GivePatsState::Created,
            data: None,
            name: None
        }
    }
}
impl Future for GivePatsFuture {
    type Output = ();
    fn poll(&mut self, cx: &mut Context<'_>)  // ← No `Pin` needed
        -> Poll<Self::Output> { ... }
}

This is significantly simpler than what we had before in its definition. And even the actual desugaring of the invocation ends up being simpler: no longer needing the intermediate IntoFuture constructor to guarantee in-place construction.

let into_future = GivePatsFuture::new();
let mut future = into_future.into_future(); // ← No `pin!` needed
loop {
    match future.poll(&mut current_context) {
        Poll::Ready(ready) => break ready,
        Poll::Pending => yield Poll::Pending,
    }
}

All that's needed for this is for the compiler to update the addresses of self-pointers on move. That's a little bit of extra codegen whenever a value is moved - rather than just a bitwise copy, it also needs to update pointer values. But it seems quite doable to implement, should actually perform really well, and most importantly: users would rarely if ever need to think about it. Writing &'self.field would always just work.

When immovable types are still needed

I don't want to discount the idea of immovable types entirely though. There are definitely benefits to having types which cannot be moved. Especially when working with FFI structures that require immovability. Or some high-performance data structures which use lots of self-references to stack-based data which would be too expensive to update. Use cases certainly exist, but they're going to be fairly niche. For example: Rust for Linux uses immovable types for their intrusive linked lists - and I think those probably need some form of immovability to actually work.

However, if the compiler doesn't require immovable types to provide self-references, then immovable types suddenly go from being load-bearing to instead becoming something closer to an optimization. It's likely still worth adding them since they certainly are more efficient. But if we do it right, adding immovable types will be backwards-compatible, and would be something we can introduce later as an optimization.

When it comes to whether async {} should return impl Future or impl IntoFuture: I think the answer really should be impl IntoFuture. In the 2024 edition we're changing range syntax (0..12) from returning Iterator to returning IntoIterator. This matches Swift's behavior, where 0..12 returns Sequence rather than IteratorProtocol. I think this is a good indication that async {} and gen {} probably also should return impl Into* traits rather than their respective traits.

Conclusion

I like it when something I write is discussed and I end up picking up on other relevant work. I think to enable self-referential types I'm now definitely favoring a form of built-in pointer updates as part of the language over immovable types (edit: maybe I spoke too soon). However, if we do want immovable types - I think my last post provides a coherent and user-friendly design to get us there.

There are a fairly large number of dependencies if we want to implement a complete story for self-referential types. Luckily we can implement features one at a time, enabling increasingly more expressive forms of self-referential types. In terms of importance: some form of 'unsafe seems like a good starting point. Followed by place-based lifetimes. View types seem useful, but aren't in the critical path since we can work around phased initialization using an option dance. Here's a graph of all features and their dependencies.

A graph showing the various dependencies between language items

Breaking down the features like has actually further reinforced my perception that this all seems quite doable. 'unsafe doesn't seem like it's that far out. And Niko has sounded somewhat serious about path-based lifetimes and view types. We'll have to see how quickly those will actually end up being developed in practice - but having laid this all out like this, I'm feeling somewhat optimistic!

Further simplifying self-referential types for Rust— 2024-07-08

Not all self-referential types are !Move

The 'self lifetime is insufficient