Some Rust questions are asked over and over, and are therefore met with short and well-rehearsed answers. “Compile in release mode when measuring performance.” “Don’t try to learn Rust with linked lists.” “Use scoped threads.” “That requires specialization.” But there is one response that is delivered in an almost checkmate-like fashion: “You are trying to construct a self-referential type.” This is swiftly explained to be impossible in current Rust, and the asker advised to pursue a different approach. If they absolutely insist on self-references, they’re referred to std::pin, which is unergonomic, hard to understand, and still requires unsafe. Alternatively, they’re given a list of crates that purport to help with creating self-referential structs, but come with disheartening caveats, and some with safety holes which can turn fatal.

Contrary to usual answers, this will show how to create self-referential types manually. A very important subset of such types are straightforward to reason about and, most importantly, can be manipulated through a safe interface. We will not rewrite the borrow checker, we will not use std::pin, but we will use a bit of unsafe. You’ve been warned.

A practical introduction

Just so you don’t think self-referential structs are a theoretical issue that only happen to people trying to implement specialized data structures, consider this task:

Use the zip crate to implement a function that accepts the name of a ZIP file and the name of a member stored inside it, and returns something that implements Read to stream the member.

Streaming the contents of a ZIP file sounds like a reasonable thing to want to do. We’d like to create a function like this:

fn zip_streamer(file_name: &str, member_name: &str) -> impl std::io::Read {
    todo!()
}

Looking at the crate docs, this seems trivial to implement. Open the file, call ZipArchive::new() to create a ZipArchive, then call ZipArchive::by_name() to get a ZipFile, which implements Read. Presto:

pub fn zip_streamer(file_name: &str, member_name: &str) -> impl std::io::Read {
    let file = File::open(file_name).unwrap();
    let mut archive = ZipArchive::new(file).unwrap();
    archive.by_name(member_name).unwrap()
}

But sadly, this fails to compile. The compiler complains that “borrowed value does not live long enough”:

error[E0597]: `archive` does not live long enough
 --> src/main.rs:8:5
  |
8 |     archive.by_name(member_name).unwrap()
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |     |
  |     borrowed value does not live long enough
  |     argument requires that `archive` is borrowed for `'static`
9 | }
  | - `archive` dropped here while still borrowed

The error message is a bit cryptic at first, it’s not clear how exactly “argument requires that archive is borrowed for static” (or what that even means), but looking at the signature of ZipArchive::by_name() reveals the problem. by_name() returns a ZipFile<'a> where 'a is the lifetime of the archive. The ZipFile we’re attempting to return references archive, a local variable. That would produce a dangling reference and obviously can’t be allowed to compile. The only way for that to work would be if archive were itself static, which is where the requirement “that archive is borrowed for ‘static” comes from.

If you’re an experienced Rustacean, at this point you’re developing a sinking feeling about where this is leading to. If you’re new to the language, or even intermediate, this can still look very much fixable: let’s just wrap both archive and its member into a common struct, return it from the function, and implement Read on the struct. That requires a bit of boilerplate, but should resolve the issue of referencing the local variable:

pub fn zip_streamer(file_name: &str, member_name: &str) -> impl std::io::Read {
    struct ZipStreamer<'a> {
        archive: ZipArchive<File>,
        reader: ZipFile<'a>,
    }

    impl Read for ZipStreamer<'_> {
        fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
            self.reader.read(buf)
        }
    }

    let file = File::open(file_name).unwrap();
    let mut archive = ZipArchive::new(file).unwrap();
    let reader = archive.by_name(member_name).unwrap();

    ZipStreamer { archive, reader }
}

You guessed it, this doesn’t compile either, and in fact fails with a very similar error message about argument requiring archive to be borrowed for ‘static, with this addition:

error[E0505]: cannot move out of `archive` because it is borrowed
  --> src/main.rs:22:17
   |
21 |     let reader = archive.by_name(member_name).unwrap();
   |                  ----------------------------
   |                  |
   |                  borrow of `archive` occurs here
   |                  argument requires that `archive` is borrowed for `'static`
22 |     ZipStreamer { archive, reader }
   |                   ^^^^^^^ move out of `archive` occurs here

Now we have a new problem: in order to construct ZipStreamer, we must move our local variable into a field of the ZipStreamer. But this move immediately invalidates reader, because as far as the borrow checker is concerned, use-after-move creates a dangling reference just like use-after-free does.

This looks bad, but there might still be hope. Can’t we box the ZipArchive to heap-allocate it, or wrap it in an Rc or Arc to postpone its destruction? But try as you might, no approach is allowed to compile.

Without ever being aware of it, we’ve been trying to create the dreaded “self-referential struct”. ZipStreamer is self-referential because the reader field refers to the archive field of the same struct. This makes the 'a lifetime nonsensical, because a lifetime refers to some data in the caller, which just doesn’t apply to the reader field. If instead of impl Read we returned the concrete type ZipStreamer<'a>, we simply wouldn’t have a lifetime to use for 'a. While our function does accept two references, neither of those is useful as the lifetime of ZipStreamer is clearly tied to the data inside itself.

This is by no means specific to the zip crate, the same issue pops up in various scenarios: a function that returns a database connection and an open transaction, or a parser that holds the string it parses and the parsed pieces that refer to string data.

Why Rust rejects self-reference

Before showing how to fix this issue, let’s once more look at the reasons why Rust prevents us from creating a self-referential structure. What would go wrong if we could create one? For example:

// imaginary self-referential struct where `current_token` points into `data`
struct ParseState {
    data: String,               // the string we're parsing
    current_token: &'data str,  // current token pointing into the string
}

There are two problems with current_token pointing into data.

First, there is no way to name the lifetime of current_token. In the above example we used a lifetime named the same as the field, inspired by a Polonius talk. In current Rust the only way to provide a lifetime on a struct member is to either make it 'static or take a lifetime declared on the struct, as in the ZipStreamer<'a> attempt above. But that lifetime is not useful, as it always corresponds to some data outside the type.

Second, Rust must assume that any move of ParseState invalidates current_token. Imagine if, ParseState were declared like this:

struct ParseState {
    data: [u8; 4096],            // the fixed-size buffer we're parsing
    current_token: &'data [u8],  // current token pointing into the buffer
}

Moving ParseState from one place to another will obviously invalidate the reference. This is not the case when the data is a String, or simply a Box, because those types heap-allocate their content, and moving the string or box has no effect on their content. But Rust doesn’t know that, it treats String the same as an array of u8, and assumes that moves are detrimental to borrows. This is the issue that prevents self-referential types from working in scenarios that would be considered perfectly safe and reasonable in C++.

This really bears repeating: there is nothing in the Rust abstract machine that prevents self-referential types from working, as long as you are willing to box them, because then you don’t run afoul of the move semantics. The remaining questions are how practical the implementation is, and whether one can expose a safe interface to it. Let’s investigate that.

Implementation of a self-referential struct

Armed with the above insight, we can sketch what we must do to make ZipStreamer work:

• box the ZipArchive in ZipStreamer::archive, so we don’t need to worry about moves breaking the ZipFile reference
• figure out a lifetime for the ZipFile stored in reader
• ensure that the references in ZipFile stored reader are valid for the whole lifetime of ZipStreamer.

Here is the result:

pub fn zip_streamer(file_name: &str, member_name: &str) -> impl std::io::Read {
    #[allow(dead_code)]
    struct ZipStreamer {
        // actually has lifetime of `archive`
        // declared first so it's droped before `archive`
        reader: ZipFile<'static>,
        // safety: we must never move out of this box as long as reader is alive
        archive: AliasableBox<ZipArchive<File>>,
    }

    impl Read for ZipStreamer {
        fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
            self.reader.read(buf)
        }
    }

    let file = File::open(file_name).unwrap();
    let mut archive = AliasableBox::from_unique(Box::new(ZipArchive::new(file).unwrap()));
    let reader = archive.by_name(member_name).unwrap();
    let reader = unsafe { std::mem::transmute(reader) };

    ZipStreamer { archive, reader }
}

Wait, this is it?

Explanation

Let’s examine the above code in some detail.

How does it work?

It creates a self-referential type that is safe to move around because the referenced data is behind a box, so its memory location doesn’t change when the top-level type is moved. Since the fields of ZipStreamer are private, no external code can mutate archive, or move it out of its box. When the struct is dropped, the documented drop order ensures that the reader field is dropped before archive field, so the reference never dangles, even when unused.

Is it really safe?

The above function is obviously not safe in the sense of “not using any unsafe”. But it exposes a fully safe external API to functionality that uses unsafe internally – much like many parts of the standard library. In other words, I believe that zip_streamer() is sound, but as always with unsafe code, caveat emptor.

What is the meaning of the ‘static lifetime on ZipFile?

The 'static lifetime is the only lifetime we can use in that position. Any other named lifetime would have to be introduced on the type, and would make it unusable. The use of 'static does mean that we are lying to the borrow checker, as the actual lifetime is the scope of the archive member in the box, which cannot be expressed in today’s Rust. This false lifetime is why we must use unsafe below. The important thing is that this lie cannot result in incorrect code being generated – as ZipFile<'a> is generic over any lifetime and cannot misuse 'static in any way (even specialization doesn’t allow specializing on lifetimes). Unlike generic types, which are monomorphized to a single implementation, no monomorphization is done one lifetimes, which are used to reject unsound code, not to modify what code gets generated.

Some examples that show self-referential types are demonstrated on a reference, and get around the lifetime issue by storing a pointer instead. But that trick wouldn’t work here, as we don’t work with a naked reference, but with the ZipFile<'a> type which contains references. Of course, the same approach would work for a reference.

What is the purpose of transmute()?

The call to transmute() admittedly looks scary, as it’s, quoting actual documentation, incredibly unsafe.

But one of the uses of transmute() is to extend the lifetime of a reference, and that’s exactly what we’re doing here. Transmuting between two different types is fraught with pitfalls because their layouts must match precisely, which in some cases requires forcing a non-standard representation. Transmuting between the same type to extend lifetime is still unsafe, but much easier to reason about from the perspective of correct usage of transmute().

What’s the deal with AliasableBox, wouldn’t Box work as well?

When a Box is moved, Rust assumes (and the borrow checker verifies) that the Box has unique access to its contents. Every code along the lines of:

let b = Box::new(...);
let r = &b.some_field;
let b2 = b;
// use "r"

…will fail to compile because b is moved while there are outstanding references into it. But that’s the moral equivalent of what our code does when it creates archive, creates the reader that refers into it, and then moves archive into the ZipStreamer. It seems okay to do this because moving a box doesn’t change the memory address of its content. But it technically creates a dangling reference because moving the box is defined to invalidate any references into it. A reference surviving the move is something the optimizer is allowed to assume won’t happen and is therefore UB. Running the above example under MIRI reports UB due to an invalidated reference.

To fix the issue, instead of Box we can define a box-like type that internally uses a raw pointer. This has the same semantics as a Box, but prevents the optimizer from assuming that moving it invalidates references to its contents. We use AliasableBox from the aliasable crate for that purpose.

This issue was spotted by /u/Darksonn on reddit.

If this works, why doesn’t async Rust use it instead of pinning?

The approach shown here requires the implementation to adhere to a very specific unsafe contract, such as “you must not move out of this Box” or “reader must be declared before archive otherwise you invoke UB.” Async Rust aims to provide a safer experience by limiting the unsafe portion to the creation of the pin, typically abstracted by the standard library or a crate, and the rest of the code being completely safe and sound.

There are ways to abstract this approach, though, but they come at the cost of ergonomics, and is not yet agreed to be sound in all cases. This is what the self-referential crates provide, and is shown below.

Safe version with ouroboros

Ouroboros is a crate that aims to encapsulate the unsafe contract like the one in the above code into abstractions implemented with a mixture of proc macros and custom types. Here is what the above code looks like using it:

use ouroboros::self_referencing;

pub fn zip_streamer(file_name: &str, member_name: &str) -> impl std::io::Read {
    #[self_referencing]
    struct ZipStreamer {
        archive: ZipArchive<File>,
        #[borrows(mut archive)]
        #[not_covariant]
        reader: ZipFile<'this>,
    }

    impl Read for ZipStreamer {
        fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
            self.with_reader_mut(|reader| reader.read(buf))
        }
    }

    let file = File::open(file_name).unwrap();
    let archive = ZipArchive::new(file).unwrap();
    ZipStreamerBuilder {
        archive,
        reader_builder: |archive| archive.by_name(member_name).unwrap(),
    }
    .build()
}

Under the hood ouroboros generates a very similar struct to the one we’ve created manually:

pub(super) struct ZipStreamer {
    reader: ZipFile<'static>,
    archive: ::ouroboros::macro_help::AliasableBox<ZipArchive<File>>,
}

The 'static lifetime is there, as is a reexport of AliasableBox. Ouroboros tries to provide only safe interfaces – if the code compiles, it should be sound, and require no unsafe. For example it puts the above type definition in a module, which makes reader private, and the only way to access it is using with_reader_mut(). This prevents safe code from ever observing the fictitious 'static lifetime.

As mentioned above, the benefit of using a crate like ouroboros is that it provides a safe abstraction to self-referential type. However, there is a number of downsides as well:

• It generates a lot of code (500+ lines for the above simple example) which affects compilation times. It also adds convenience constructors on the type, which you can’t turn off, and which sometimes actually get in the way.
• The generated code contains a lot of unsafe hidden behind abstractions that give a sense of safety, but might turn out to be unsound, and have in the past. (I’ll refrain from linking to individual issues, but they’re easy to find on the tracker, and there’s the example of rental which was abandoned due to soundness issues.)
• It has a lot of hidden complexity, as it modifies the definition of the type in ways that are sometimes hard to reason about.

In summary, it probably makes sense to use a crate like ouroboros if it works for your use case and if you don’t mind all the extra code it generates. But I’d advise at least being aware what it does for you, as it feels like a bit of a leaky abstraction.

Limitations

The approach shown above, which includes both the hand-written unsafe and ouroboros, does have limitations. An interesting use case of self-referential structs is wrapping foreign data, such as C++ strings and vectors with small string/vector optimization. The approach in this article would technically work for such types, but would not be useful because it requires unconditional allocation, and the whole point of such types is efficiency and avoiding allocations. (They work in C++ by implementing a “move constructor” that fixes up the self-references.)

Another situation where the above doesn’t help is if safe code needs to be able to mutably access parts of the self-referential type. Since it’s safe code, you can’t just prohibit it from moving the reference out of it, you need to prevent it using the type system. This is remarkably achieved through std::pin, although many people have a hard time wrapping their heads around the concept in prctice.

Today self-referential types requires either reasoning about unsafe code, which most people shy away from for very good reason, or using crates with very serious hit on ergonomics. This is what we have to work with until Polonius comes to save us.