Ergonomic Self-Referential Types for Rust
— 2024-07-01

I've been thinking a little about self-referential types recently, and while it's technically possible to write them today using Pin (limits apply), they're not at all convenient. So what would it take to make it convenient? Well, as far as I can tell there are four components involved in making it work:

The ability to write 'self lifetimes.
The ability to construct types from functions in fixed memory locations.
A way to mark types as "immovable" in the type system.
The ability to safely initialize self-references in structs without going through an option-dance.

It's only once we have all four of these components that writing self-referential types can become accessible to most regular Rust programmers. And that seems important, because as we've seen with async {} and Future: once you start writing sufficiently complex state machines, being able to track references into data becomes incredibly useful.

Speaking of async and Future: in this post we'll be using that as a motivating example for how these features can work together. Because if it seems realistic that we can make that a case as complex as that work, other simpler cases should probably work too.

Oh and before we dive in, I want to give a massive shout-out to Eric Holk. We've spent several hours working through the type-system implications of !Move together, and worked through a number of edge cases and issues. I can't be solely credited for the ideas in this post. However any mistakes in this post are mine, and I’m not claiming to speak for the both of us.

Disclaimer: This post is not a fully-formed design. It is an early exploration of how several features could work together to solve a broader problem. My goal is primarily to narrow down the design space to a tangible list of features which can be progressively implemented, and share it with the broader Rust community for feedback. I'm not on the lang team, nor do I speak for the lang team.

Motivating example

Let's take async {} and Future as our examples here. When we borrow local variables in an async {} block across .await points, the resulting state machine will store both the concrete value and a reference to that value in the same state machine struct. That state machine is what we call self-referential, because it has a reference which points to something in self. And because references are pointers to concrete memory addresses, there are challenges around ensuring they are never invalidated as that would result in undefined behavior. Let's look at an example async function:

async fn give_pats() {
    let data = "chashu tuna".to_string();       // ← Owned value declared
    let name = data.split(' ').next().unwrap(); // ← Obtain a reference
    pat_cat(&name).await;                       // ← `.await` point here
    println!("patted {name}");                  // ← Reference used here
} 

async fn main() {
    give_pats().await; // Calls the `give_pats` function.
}

This is a pretty simple program, but the idea should come across well enough: we declare an owned value in-line, we call an .await function, and later on we reference the owned value again. This keeps a reference live across an .await point, and that requires self-referential types. We can desugar this to a future state machine like so:

enum GivePatsState {
    Created,       // ← Marks our future has been created
    Suspend1,      // ← Marks the first `.await` point
    Complete,      // ← Marks the future is now done
}

struct GivePatsFuture {
    resume_from: GivePatsState,
    data: Option<String>,
    name: Option<&str>,  // ← Note the lack of a lifetime here
}

impl GivePatsFuture {
    fn new() -> Self {
        Self {
            resume_from: GivePatsState::Created,
            data: None,
            name: None,
        }
    }
}

impl Future for GivePatsFuture {
    type Output = ();
    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> { ... }
}

The lifetime of GivePatsFuture::name is unknown, mainly because we can't name it. And because the desugaring happens in the compiler, it doesn't have to name the lifetime either. We'll talk more about that later in this post. Because this generates a self-referential state machine, this future will need to be fixed in-place using Pin first. Once pinned, the Future::poll method can be called in a loop until the future yields Ready. The desugaring for that will look something like this:

let mut future = IntoFuture::into_future(GivePatsFuture::new());
let mut pinned = unsafe { Pin::new_unchecked(&mut future) };
loop {
    match pinned.poll(&mut current_context) {
        Poll::Ready(ready) => break ready,
        Poll::Pending => yield Poll::Pending,
    }
}

And finally, just for reference, here is what the traits we're using look like today. The main bit that's interesting here for the purpose of this post is that Future takes a Pin<&mut Self>, which we'll be explaining how it can be replaced with a simpler system throughout the remainder of this post.

pub trait IntoFuture {
    type Output;
    type IntoFuture: Future<Output = Self::Output>;
    fn into_future(self) -> Self::IntoFuture;
}

pub trait Future {
    type Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
}

Now that we've taken a look at how self-referential futures are desugared by the compiler today, let's take a look at how we can incrementally replace it with a safe, user-constructible system.

Self-referential lifetimes

In our motivating example we showed the GivePatsFuture which has the name field that points at the data field. It's a clearly a reference, but it does not carry any lifetime:

struct GivePatsFuture {
    resume_from: GivePatsState,
    data: Option<String>,
    name: Option<&str>, // ← Note the lack of a lifetime
}

The reason this doesn't have a lifetime is not inherent, it's because we can't actually name the lifetime here. It's not 'static because it isn't valid for the remainder of the program. In the compiler today I believe we can just omit the lifetime because the codegen happens after the lifetimes have already been checked. But say we wanted to write this by hand today as-is; we would need a concept for an "unchecked lifetime", something like this:

struct GivePatsFuture {
    resume_from: GivePatsState,
    data: Option<String>,
    name: Option<&'unsafe str>, // ← Unchecked lifetime
}

Being able to write a lifetime that isn't checked by the compiler would be the first-click stop to enable writing self-referential structs by hand. It would just require a lot of unsafe and anxiety to get right. But at least it would be possible. I believe folks on T-compiler are already working on adding this, which seems like a great idea.

But even better would be if we could describe checked lifetimes here. What we actually want to write here is a lifetime which is valid for the duration of the value - and it would always be guaranteed to be valid. Adding this lifetime would come with additional constraints we'll get into later in this post (e.g. the type wouldn't be able to move), but what we really want is to be able to write something like this:

struct GivePatsFuture {
    resume_from: GivePatsState,
    data: Option<String>,
    name: Option<&'self str>, // ← Valid for the duration of `Self`
}

To sidetrack slightly; adding a named 'self lifetime could also allow us to remove the where Self: 'a boilerplate when using lifetimes in generic associated types. If you've ever worked with lifetimes in associated types, then you'll likely have run into the "missing required bounds" error. Niko suggested in this issue using 'self as one possible solution for the bounds boilerplate. I think its meaning would be slightly different than when used with self-references? But I don't believe using this would be ambiguous either. And all in all I think it looks rather neat:

// A lending iterator trait as we have to write it today:
trait LendingIterator {
    type Item<'a>
    where
        Self: 'a;
    fn next(&mut self) -> Self::Item<'_>;
}

// A lending iterator trait if we had `'self`:
trait LendingIterator {
    type Item<'self>;
    fn next(&mut self) -> Self::Item<'_>;
}

Constructing types in-place

In order for 'self to be valid, we have to promise our value won't move in memory. And before we can promise a value won't move, we have to first construct it somewhere we can be sure it can stay and not be moved further. Looking at our motivating example, the way we achieve this using Pin is a little goofy. Here's that same example again:

impl GivePatsFuture {
    fn new() -> Self {
        Self {
            resume_from: GivePatsState::Created,
            data: None,
            name: None,
        }
    }
}

async fn main() {
    let mut future = IntoFuture::into_future(GivePatsFuture::new());
    let mut pinned = unsafe { Pin::new_unchecked(&mut future) };
    loop {
        match pinned.poll(&mut current_context) {
            Poll::Ready(ready) => break ready,
            Poll::Pending => yield Poll::Pending,
        }
    }
}

In this example we're seeing GivePatsFuture being constructed inside of the new function, be moved out of that, and only then pinned in-place using Pin::new_unchecked. Even if GivePatsFuture: !Unpin, the Unpin trait only affects types once they are held inside of a Pin structure. And we can't just return Pin from new, because the function's stack frames are discarded the moment the function returns.

It would be better if we enabled types to describe how they can construct themselves in-place. That means no more external Pin::new_unchecked calls; but exclusively internally provided constructors. This enables us to make self-referential types entirely self-contained, with internally provided constructors replacing the external pin dance. Here's how we could rewrite GivePatsFuture::new to use an internal constructor instead:

impl GivePatsFuture {
    fn new(slot: Pin<&mut MaybeUninit<Self>>) {
        let slot = unsafe { slot.get_unchecked_mut() };
        let this: *mut Self = slot.as_mut_ptr();
        unsafe { 
           addr_of_mut!((*this).resume_from).write(GivePatsState::Created);
           addr_of_mut!((*this).data).write(None);
           addr_of_mut!((*this).name).write(None);
        };
    }
}

If you don't like this: that's understandable. I don't think anyone does. But bear with me; we're on a little didactic sausage-making journey here together. I'm sorry about the sights; let's quickly move on.

In a recent blog post I posited we might be able to think of parameters like these as "spicy return". James Munns pointed out that in C++ this feature has a name: out-pointers. And Jack Huey made an interesting connection between this and the super let design. Just so we don't have to look at a pile of unsafe code again, let's pretend we can combine these into something coherent:

impl GivePatsFuture {
    fn new() -> super Pin<&'super mut Self> {
        pin!(Self { // just pretend this works
            resume_from: GivePatsState::Created,
            data: None,
            name: None,
        })
    }
}

I know, I know - I'm showing syntax here. I'm personally meh about the way it looks and we'll talk more later about how we can improve this, but I hope we can all agree that the function body itself is approximately 400% more legible than the pile of unsafe we were working with earlier. We'll also get to how we can entirely remove Pin from the signature, so please don't get too hung up on that either.

I'm asking you to play along here for a second, and pretend we might be able to do something like this for now, so we can get to the part later on this post where we can actually fix it. In maybe state this more clearly: this post is less about proposing concrete designs for a problem, but more about how we can tease apart the problem of "immovable types" into separate features we can tackle independently from one another.

Converting into immovable types

Alright, so we have an idea of how we might be able to construct immovable types in-place, provided as a constructor defined on a type. Now while that's nice, we've also lost an important property with that: whenever GivePatsFuture is constructed, it needs to have a fixed place in memory. Where before we could freely move it around until we started .awaiting it.

One of the main reasons why async is useful is because it enables ad-hoc concurrent execution. That means we want to be able to take futures and pass them to concurrency operations to enable concurrency through composition. We can't move futures which have a fixed location in memory, so we need a brief moment where futures can be moved before they're ready to be kept in place and polled to completion.

The way Pin works with this today is that a type can be !Unpin - but that only becomes relevant once it's placed inside of a Pin structure. With futures that typically doesn't happen until it begins being polled, usually via .await, and so we get the liberty of moving !Unpin futures around until we start .awaiting them. That's why !Unpin doesn't mark: "A type which cannot be moved", it marks: "A type which cannot be moved once it has been pinned". This is definitely confusing, so don't worry if it's hard to follow.

fn foo<T: Unpin>(t: &mut T);   // Type is not pinned, type can be moved.
fn foo<T: !Unpin>(t: &mut T);  // Type is not pinned, type can be moved.
fn foo<T: Unpin>(t: Pin<&mut T>);  // Type is pinned, type can be moved.
fn foo<T: !Unpin>(t: Pin<&mut T>); // Type is pinned, type can't be moved.

If we want "immovability" to be unconditionally part of a type, we can't make it behave the same way Unpin does. Instead it seems better to separate the movable / immovable requirements into two separate types. We first construct a type which can be freely moved around - and once we're ready to drive it to completion, we convert it to a type which is immovable and we begin calling that. This maps perfectly to the separation between IntoFuture and Future we already use.

Let's take a look at our first example again, but modify it slightly. What I'm proposing here is that rather than give_pats returning an impl Future, it should instead return an impl IntoFuture. This type is not pinned, and can be freely moved around. It's only once we're ready to .await it that we call .into_future to obtain the immovable future - and then we call that.

struct GivePatsFuture { ... } 
impl GivePatsFuture {
    fn new() -> super Pin<&'super mut Self> { ... } // suspend belief pls
}

struct GivePatsIntoFuture;
impl IntoFuture for GivePatsIntoFuture {
    type Output = ();
    type IntoFuture = GivePatsFuture;

    // We call the `Future::new` constructor which gives us a
    // `Pin<&'super GivePatsFuture>`, and then rather than writing
    // it into the current function's stack frame we write it in the
    // caller's stack frame.
    //
    // (keep belief suspended a little longer)
    fn into_future(self) -> super Pin<&'super mut GivePatsFuture> {
        GivePatsFuture::new() // create in caller's scope
    }
}

Just like we can keep returning values from functions to pass them further up the call stack, so should we be able to use out-pointers / emplacement / spicy allocate in a stack frame further up the call stack. Though even if we didn't support that out of the gate, we could probably in-line the GivePatsFuture::new into GivePatsIntoFuture::into_future and things would still work. And with that, our .await desugaring could then look something like this:

async fn main() {
    let into_future: GivePatsIntoFuture = give_pats();
    let mut future: Pin<&mut GivePats> = GivePatsIntoFuture.into_future();
    loop {
        match future.poll(&mut current_context) {
            Poll::Ready(ready) => break ready,
            Poll::Pending => yield Poll::Pending,
        }
    }
}

To re-iterate why this section exists: we can get the same functionality Pin + Unpin provide today by creating two separate types. One type which can be freely moved around. And another type which once constructed will not move locations in memory.

So far the only framing of "immovable types" I've seen so far is a single types which have both these properties - just like Unpin does today. What I'm trying to articulate here is that we can avoid that issue if we choose to create two types instead, enabling one to construct the other, and make them provide separate guarantees. I think that's a novel insight, and one I thought was important to spend some time on.

Immovable types

Alright, I've been asking folks to suspend belief that we can in fact perform in-place construction of a Pin<&mut Self> type somehow and that would all work out the way we want it to. I'm not sure myself, but for the sake of the narrative of this post it was easier if we just pretended we could for a second.

The real solution here, of course, to get rid of Pin entirely. Instead types themselves should be able to communicate whether they have a stable memory location or not. The simplest formulation for this would be to add a new built-in auto-trait, Move, which tells the compiler whether a type can be moved or not.

auto trait Move {}

This is of course not a new idea: we've known about the possibility for Move since at least 2017. That's before I started working on Rust. There were some staunch advocates for that in the Rust community in favor of Move, but ultimately that wasn't the design we ended up going with. I think in hindsight most of will acknowledge that the downsides of Pin are real enough that revisiting Move and working through its limitations seems like a good idea ¹. To explain what the Move trait is: it would be a language-level trait which governs access to the following capabilities:

For anyone looking to assign blame here or pull skeletons out of closets: please don't. The higher-order bit here is that we have Pin today, it clearly doesn't work as well as was hoped at the time, and we'd like to replace it with something better. I think the most interesting thing to explore here is how we can move forward and do better.

The ability to be passed by-value into functions and types.
The ability to be passed by mutable reference to mem::swap, mem::take, and mem::replace.
The ability to be used with any syntactic equivalents to the earlier points, such as assigning to mutable references, closure captures, and so on.

Conversely, when a type implements !Move they would not have access to any of these capabilities - making it so they cannot be moved once they have a fixed memory location. And by default we would assume in all bounds that types are Move, except for places that explicitly opt-out by using + ?Move. Here are examples of things that constitute moves:

// # examples of moving

// ## swapping two values
let mut x = new_thing();
let mut y = new_thing();
swap(&mut x, &mut y);

// ## passing by value
fn foo<T>(x: T) {}
let x = new_thing();
foo(x);

// ## returning a value
fn make_value() -> Foo {
    Foo {
        x: 42
    }
}

// ## `move` closure captures
let x = new_thing();
thread::spawn(move || {
    let x = x;
})

And here are some things that do not constitute moves:

// # things that are not moves

// ## passing a reference
fn take_ref<T>(x: &T) {}
let x = new_thing();
take_ref(&x);

// ## passing mutable references is also okay,
//    but you have to be careful how you use it
fn take_mut_ref<T>(x: &mut T) {}
let mut x = new_thing();
take_mut_ref(&mut x);

Passing types by-value will never be compatible with !Move types because that’s what a move is. Passing types by-reference will always be compatible with !Move types because they are immutable ². The only place with some ambiguity is when we work with mutable references, as things like mem::swap allow us to violate the immovability guarantees.

Yes yes, we'll get to internal mutability in a second here.

If a function wants to take a mutable reference which may be immovable, they will have to add + ?Move to it. If a function does not use + ?Move on their mutable reference, then a !Move type cannot be passed to it. In practice this will work as follows:

fn meow<T>(cat: T);            // by-value,   can't pass `!Move` values
fn meow<T>(cat: &T);           // by-ref,     can pass `!Move` values
fn meow<T>(cat: &mut T);       // by-mut-ref, can't pass `!Move` values
fn meow<T: ?Move>(cat: &mut T) // by-mut-ref, can pass `!Move` values

By default all cat: &mut T bounds would imply + Move. And only where we opt-in to + ?Move could !Move types be passed. In practice it seems likely most places will probably be fine adding + ?Move, since it's far more common to write to a field of a mutable reference than it is to replace it whole-sale using mem::swap. Things like interior mutability are probably also largely fine under these rules, since even if accesses go through shared references, updating the values in the pointers will have to interact with the earlier rules we've set out - and those are safe by default.

To be entirely accurate we also have to consider internal mutability. That allows us to mutate values through shared references - but only by being able to conditionally convert it to &mut references at runtime. Just because we allow casting &T to &mut T at runtime, doesn't mean that the rules we've applied to the system don't still work. Say we held an &mut T: !Move inside of a Mutex. If we tried to call the deref_mut method, we'd get a compile-error because that bound hasn't yet declared that T: ?Move. We could probably add that, but because it doesn't work by default we'd have an opportunity to validate its soundness before adding it.

Anyway, that's enough theory about how this should probably work for now. Let's try and update our earlier example, replacing Pin with !Move. That should be as simple as adding a !Move impl on GivePatsFuture.

struct GivePatsFuture {
    resume_from: GivePatsState,
    data: Option<String>,
    name: Option<&'self str>,
}
impl !Move for GivePatsFuture {}

And once we have that, we can change our constructors to return super Self instead of super Pin<&'super mut Self>. We already know that emplacement using something like super Self (not actual notation) to write to fixed memory locations seems plausible. All we then need to do is add an auto-trait which tells the type-system that further move operations aren't allowed.

struct GivePatsFuture { ... } 
impl !Move for GivePatsFuture {}
impl GivePatsFuture {
    fn new() -> super Self { ... } // create in caller's scope
}

struct GivePatsIntoFuture;
impl IntoFuture for GivePatsIntoFuture {
    type Output = ();
    type IntoFuture = GivePatsFuture;
    fn into_future(self) -> super GivePatsFuture {
        GivePatsFuture::new() // create in caller's scope
    }
}

I probably should have said this sooner, but I'll say it now: in this post I'm intentionally not bothering with backwards-compat. The point, again, is to break the complicated design space of "immovable types" into smaller problems we can tackle one-by-one. Figuring out how to bridge Pin and !Move is something we will want to figure out at some point - but not now.

As far as async {} and Future are concerned: this should work! This allows us to freely move around async blocks which desugar into IntoFuture. And only once we're ready to start polling them do we call into_future to obtain an impl Future + !Move. A system like that is equivalent to the existing Pin system, but does not need Pin in its signature. For good measure, here's how we would be able to rewrite the signature of Future with this change:

// The current `Future` trait
// using `Pin<&mut Self>`
pub trait Future {
    type Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
}

// The `Future` trait leveraging `Move`
// using `&mut self`
pub trait Future {
    type Output;
    fn poll(&mut self, cx: &mut Context<'_>) -> Poll<Self::Output>;
}

That would also mean: no more Pin-projections. No more incompatibilities with Drop. Because it's an auto-trait that governs language behavior, as long as the base rules are sound, the interaction with all other parts of Rust would be sound.

Also, most relevant for me probably, this would make it possible to write future state machines using methods and functions, rather than the current status quo where we just lump everything into the poll function body. After having written a ridiculous amount of futures by hand over the past six years, I can't tell you how much I'd love to be able to do that.

Motivating example, reworked

Now that we've covered self-referential lifetimes, in-place construction, understand async {} should return IntoFuture, and have seen !Move, we're ready to bring these features together to rework our motivating example. This is what we started with using regular async/.await code:

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

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

And here is what that, with these new capabilities, here is what async fn give_pats would be able to desugar to. Note the 'self lifetime, the !Move impl for the future, the omission of Pin everywhere, and the in-place construction of the type.

enum GivePatsState {
    Created,
    Suspend1,
    Complete,
}

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

struct IntoGivePatsFuture {}
impl IntoFuture for IntoGivePatsFuture {
    type Output = ();
    type IntoFuture: GivePatsFuture
    fn into_future(self)
        -> super GivePatsFuture {  // ← Writes to a stable addr
        Self {
            resume_from: GivePatsState::Created,
            data: None,
            name: None,
        }
    }
}

And finally, we can then desugar the give_pats().await call to concrete types we construct and call to completion:

let into_future = IntoGivePatsFuture {};
let mut future = into_future.into_future(); // ← Immovable without `Pin`
loop {
    match future.poll(&mut current_context) {
        Poll::Ready(ready) => break ready,
        Poll::Pending => yield Poll::Pending,
    }
}

And with that, we should have a working example of async {} blocks, desugared to concrete types and traits that don't use Pin anywhere at all. Accessing fields within it wouldn't go through any kind of pin projection, and there would no longer be any need for things like stack-pinning. Immovability would just be a property of the types themselves, constructed when we need them in the place where we want to use them.

Oh and I guess just to mention it: functions working with these traits would always want to use T: IntoFuture rather than T: Future. That's not a big change, and actually something people should already be doing today. But I figured I'd mention it in case people are confused about what the bounds should be for concurrency operations.

Phased initialization

We didn't show this in our example, but there is one more aspect to self-referential types worth covering: phased initialization. This is when you initialize parts of a type at separate points in time. In our motivating example we didn't have to use that, because the self-references lived inside of an Option. That means that when we initialized the type we could just pass None, and things were fine. However, say we did want to initialize a self-reference, how would we go about that?

struct Cat {
    data: String,
    name: &'self str,
}
impl !Move for Cat {}

impl Cat {
    fn new(data: String) -> super Self {
        Cat {
            data: "chashu tuna".to_string(),
            name: /* How do we reference `self.data` here? */
        }
    }
}

Now of course because String is heap-allocated, its address is actually stable and so we could write something like this:

struct Cat {
    data: String,
    name: &'self str,
}
impl !Move for Cat {}

impl Cat {
    fn new(data: String) -> super Self {
        let data = "chashu tuna".to_string();
        Cat {
            name: data.split(' ').next().unwrap(),
            data, 
        }
    }
}

That's clearly cheating, and not what we want people to have to do. But it does point us at how the solution here should probably work: we first need a stable address to point to. And once we have that address, we can refer to it. We can't do that if we have to build the entire thing in a single go. But what if we could do it in multiple phases? That's what Niko's recent post on borrow checking and view types went into. That would allow us to change our example to instead be written like this:

struct Cat {
    data: String,
    name: &'self str,
}
impl !Move for Cat {}

impl Cat {
    fn new(data: String) -> super Self {
        super let this = Cat { data: "chashu tuna".to_string() }; // ← partial init
        this.name = this.data.split(' ').next().unwrap();         // ← finish init
        this
    }
}

We initialize the owned data in Cat first. And once we have that, we can then initialize the references to it. These references would be 'self, we sprinkle in a super let annotation to indicate we're placing this in the caller's scope, and everything should subsequently check out.

Migrating from Pin to Move

What we didn't cover in this post is any migration story from the existing Pin-based APIs to the new Move-based system. If we want to move off of Pin in favor of Move, the only path plausible way I see is by minting new traits that don't carry Pin in its signature, and providing bridging impls from the old traits to the new traits. A basic conversion with an explicit method could look like this, though blanket impls could also be a possibility:

pub trait NewFuture {
    type Output;
    fn poll(&mut self, ...) { ... }
}

pub trait Future {
    type Output;
    fn poll(self: Pin<&mut Self>, ...) { ... }

    /// Convert this future into a `NewFuture`.
    fn into_new_future(self: Pin<&mut Self>) -> NewFutureWrapper<&mut Self> { ... }
}

/// A wrapper bridging the old future trait to the new future trait.
struct NewFutureWrapper<'a, F: Future>(Pin<&'a mut F>);
impl !Move for NewFutureWrapper {}
impl<'a, F> NewFuture for NewFutureWrapper<'a, F> { ... }

I've been repeating this line for at least three years now: but if we want to fix the problems with Pin, the first step we need to take is to not make the problem worse. If the stdlib needs to fix the Future trait once, that sucks but it's fine and we'll find a way to do it. But if we tie Pin up into a number of other traits, the problems will compound and I'm no longer sure whether we can rid ourselves of Pin. And that's a problem, because Pin is broadly disliked and we actively want to get rid of it.

Compatibility with self-referential types is not only relevant for iteration; it's a generalized property which ends up interacting with nearly every trait, function, and language feature. Move just composes with any other trait, and so there's no need for a special PinnedRead or anything. A type would instead just implement Read + Move, and that would be enough for a self-referential reader to function. And we can repeat that for any other combination of traits.

In-place construction of course does change the signature of traits. But in order to support that in a backwards-compatible way, all we'd need to do is enable traits to opt-in to "can perform in-place construction". And being able to gradually roll-out capabilities like that is exactly why we're working on effect generics.

pub trait IntoFuture {
    type Output;
    type IntoFuture: Future<Output = Self::Output>;

    // Marked as compatible with in-place construction, with
    // implementations being able to decide whether they want
    // to use it or not.
    fn into_future(self) -> #[maybe(super)] Self::IntoFuture;
}

If we want self-referential types to be generally useful, they need to practically compose with most other features we have. And so really, the first step to getting there is stop stabilizing any new traits in the stdlib which use Pin in its signature.

Making immovable types movable

So far we’ve been talking a lot about self-referential types and how we need to make sure they cannot be moved, because moving them would be bad. But what if we did allow them to be moved? In C++ this is possible using a feature called "move constructors", and if we supported self-referential types in Rust, it doesn't seem like a big leap to support that too.

Before we go any further I want to preface this: I've heard from people who have worked with move constructors in C++ that they can be rather tricky to work with. I haven't worked with them, so I can't speak from experience. Personally I don't really have any uses where I feel like I would have wanted move constructors, so I'm not particularly in favor or against supporting them. I'm writing this section mostly out of academic interest, because I know there will be people wondering about this. And the rules for how this should work seem fairly straightforward.

Niko Matsakis recently wrote a two-parter on the Claim trait (first, second), proposing a new Claim trait to fill the gap between Clone and Copy. This trait would be for types which are "cheap" to clone, such as the Arc and Rc types. And using autoclaim, the compiler would automatically insert calls to .claim as needed. For example when a move || closure captures a type implementing Claim but it is already in use somewhere else - it would automatically call .claim so it would compile.

Enabling immovable types to relocate would work much the same as auto-claiming would. We would need to introduce a new trait, which we'll call Relocate here, with a method relocate. Whenever we tried to move an otherwise immovable value, we would automatically call .relocate instead. The signature of the Relocate trait would take self as a mutable reference. And return an instance of Self, constructed in-place:

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

Note the signature of self here: we take it by mutable reference - not owned nor shared. That is because what we're writing is effectively the immovable equivalent to Into, but we can't take self by-value - so we have to take it by-reference instead and tell people to just mem::swap away. Applying this our earlier Cat example, we would be able to implement it as follows:

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
    }
}

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. This is a general problem we need to solve, and one way we could for example work around this is by creating dummy pointers in the main struct to ensure the types are always valid - but we invalidate the types:

struct Cat {
    data: String,
    dummy_data: String, // never initialized with a value
    name: &'self str,
}

impl Relocate for Cat {
    fn relocate(&mut self) -> super Self {
        self.name = &self.dummy_data; // no more references to `self.data`
        let data = mem::take(&mut self.data); // shorter than `mem::swap`
        super let cat = Cat { data };
        cat.name = cat.data.split(' ').next().unwrap();
        cat
    }
}

In this example the Cat would implement Move even if it has a 'self lifetime, because we can freely move around. When a type is dropped after having been passed to Relocate, it should not call its Drop impl. Because semantically we're not trying to drop the type - all we're doing is updating its location in memory. Under these rules access to 'self in structs would be available both if Self: !Move OR Self: Relocate.

I want to again emphasize that I'm not directly advocating here for the introduction of move constructors to Rust. Personally I'm pretty neutral about them, and I can be convinced either way. I mainly wanted to have at least once walked through the out the way move constructors could work, because it seems like a good idea to know a gradual path here should be possible. Hopefully that point is coming across okay here.

Conclusion

In this post we've deconstructed "self-referential types" into four constituent parts:

'unsafe (unchecked) and 'self (checked) lifetimes which will make it possible to express self-referential lifetimes.
A moral equivalent to super let / -> super Type to safely support out-pointers.
A way to backwards-compatibly add optional -> super Type notations.
A new Move auto-trait which governs access to move operations.
A view types feature which will make it possible to construct self-referential types without going through an Option dance.

The final insight this post provides is that today's Pin + Unpin system can be emulated with Move by creating Move wrappers which can return !Move types. In the context of async, the pattern would be to construct an impl IntoFuture + Move wrapper, which constructs an impl Future + !Move future in-place via an out-pointer.

People generally dislike Pin, and as far as I can tell there is broad support for exploring alternative solutions such as Move. Right now the only trait that uses Pin in the stdlib is Future. In order to facilitate a migration off of Pin to something like Move, we would do well not to further introduce any Pin-based APIs to the stdlib. Migrating off of a single API will take effort, but seems ultimately doable. Migrating off of a host of APIs will take more effort, and makes it more likely we'll forever be plagued with the difficulties of Pin.

The purpose of this post has been to untangle the big scary problem of "immovable types" into its constituents parts so we can begin tackling them one-by-one. None of the syntax or semantics in this post are meant to be concrete or final. I mainly wanted to have at least once walked through everything required to make immovable types work - so that others can dig in, think along, and we can begin refining concrete details.

Ergonomic Self-Referential Types for Rust— 2024-07-01