Self Referential Structs in Rust (Part 1)
Tags: rust, programming, tutorial
Published: 2021-11-04 06:56:34

## TL;DR

1. Use `Pin<Box<T>>` for the held value (here, `Me`).
2. Mark `Me` as unpinnable by setting a field as `std::marker::PhantomPinned`.

    Eg, `_pinned: std::marker::PhantomPinned`.

3. Use `Rc<RefCell<H>>` for holder, (here, `Holder`) and store `Me` as raw
   pointers.

    Eg, `me: BTreeSet<*const Me>`.

4. Store `Holder` within `Me` using `Rc::clone(...)`.
5. Store `Me` within `Holder` by converting it into a raw pointer. It is completely upto you if you want to store a mutable raw pointer or a `const` raw pointer.
6. Implement `Drop` trait such that it removes **all references** to `Me` from `Holder` once it is dropped.

[Click here to jump to solution.](#solution)

## Introduction

There are mainly two ways to represent self-referential struct in Rust.

1. Reference within the struct:

    ```rust
    struct RefWithinMe {
        value: String,

        pointer_to_value: &'? str,
    }
    ```

    These can easily be solved using [`ouroboros`](https://docs.rs/ouroboros).

    ```rust
    #[macro_use]
    extern crate ouroboros;

    #[self_referential]
    struct RefWithinMe {
        value: String,

        #[borrows(value)]
        pointer_to_value: &'this str,
    }
    ```

    **We won't be discussing about these.**

2. Reference outside the struct (**A referential cycle**):

    ```rust
    use std::collections::BTreeSet;

    #[derive(Ord, PartialEq, Eq, PartialOrd)]
    struct Me<'a> {
        /// The my_holder that I hold.
        my_holder: &'a Holder<'a>,
    }

    /// The my_holder that holds `Me`.
    #[derive(Ord, PartialEq, Eq, PartialOrd)]
    struct Holder<'a> {
        set_of_me: BTreeSet<&'a Me<'a>>,
    }

    impl Me<'a> {
        fn new(my_holder: &'a mut Holder<'a>) -> Self {
            let this = Self {
                my_holder,
            };
            // Insert myself here.
            my_holder.set_of_me.insert(&this);

            // but the value is being moved 🤔
            this
        }
    }
    ```

    **We are going to discuss about this.**

## Problem Description

Given that you have two structs, a holder (`Holder`, say) and a struct to hold something (`Me`, say), how will you establish a circular reference?

## Experimentation

Try to run the above code and see what happens.

You get an error where Rust complaints about:

```none
error[E0502]: cannot borrow `my_holder.set_of_me` as mutable because it is also borrowed as immutable
   |
15 | impl<'a> Me<'a> {
   |      -- lifetime `'a` defined here
...
18 |            my_holder,
   |            ---------
   |            |
   |            immutable borrow occurs here
   |            requires that `*my_holder` is borrowed for `'a`
...
21 |        my_holder.set_of_me.insert(&this);
   |        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

error[E0597]: `this` does not live long enough
   |
15 | impl<'a> Me<'a> {
   |      -- lifetime `'a` defined here
...
21 |        my_holder.set_of_me.insert(&this);
   |        ---------------------------^^^^^-
   |        |                          |
   |        |                          borrowed value does not live long enough
   |        argument requires that `this` is borrowed for `'a`
...
25 |    }
   |    - `this` dropped here while still borrowed

error[E0505]: cannot move out of `this` because it is borrowed
   |
15 | impl<'a> Me<'a> {
   |      -- lifetime `'a` defined here
...
21 |        my_holder.set_of_me.insert(&this);
   |        ---------------------------------
   |        |                          |
   |        |                          borrow of `this` occurs here
   |        argument requires that `this` is borrowed for `'a`
...
24 |        this
   |        ^^^^ move out of `this` occurs here

error: aborting due to 3 previous errors
```

Aaaand, we hit a lifetime error!

I'll assume that you have a basic knowledge about Rust's lifetimes. If not, don't worry! I'll try to keep this article as simple as possible. But if you're interested, You can [read my post on Rust Lifetimes.][rust-lifetimes]

## Understanding the Error

So, here we see that Rust complaints us about `this` variable not "living long enough".

Pay attention to the message, **"borrowed value does not live long enough"**. Rust wants us to understand that if `this` is **moved**, then `my_holder.set_of_me` will have a reference to a nonexistent object. And it's never a good idea to dereference a reference (or, a pointer) to something that does not exist. _\*`SEGFAULT` intensifies 😖\*_

In short, Rust prevents the creation of dangling pointer.

But, this prevents us from creating a self-referential struct. Worry not, because we can pull up some tricks to make the Rust compiler "think" that there are no lifetime violations. However, it requires you to go down to the `unsafe` level.

But first, let us talk about moves and why they are a big deal.

## Understanding Moves in Rust

A "move" in a function happens when you return a value:

```rust
fn foo() -> String {
    let value = "ABC".to_owned();
    value  // move occurs
}
```

Now, for ordinary objects, "moving" is fine. But since objects (and their references) created within the function have the lifetime of the function itself, Rust disallows it (thankfully!).

That also means, we need to find a way to tell Rust that **"our move will keep the reference so please don't drop it!"**.

## Raw Pointers of Rust

Let's jump right to the point. Raw pointers are your typical C-like pointers that are not bound to Rust's borrow checker.

But Rust's pointer suffer from a fatal flaw. **They are not safe to use when two variables are swapped.**

Let me demonstrate it. In fact, the following is adapted from The Rust Language Tutorial for Async. [Follow this link][rust-async] to know more.

```rust
#[derive(Debug)]
struct Test {
    value: String,
    pointer_to_value: *const String,
}

impl Test {
    fn new(txt: &str) -> Self {
        let mut this = Test {
            value: String::from(txt),
            // In `C`, you'd call this initialize to `NULL`.
            pointer_to_value: std::ptr::null(),
        };
        this.pointer_to_value = &this.value;
        this
    }

    fn get_value(&self) -> &str {
        &self.value
    }

    fn get_pointer_to_value(&self) -> &String {
        unsafe { &*(self.pointer_to_value) }
    }
}
```

Here we have a simple struct called `Test`. `pointer_to_value` points to `value`. Two methods (`get_value` and `get_pointer_to_value`) have been provided as getters.

Now, let's say we create two instances of `Test` and use our getters to inspect the contents.

```rust
fn main() {
    let mut test1 = Test::new("test1");
    let mut test2 = Test::new("test2");

    println!(
        "test1: value: {}, ptr to value: {}",
        test1.get_value(),
        test1.get_pointer_to_value()
    );
    println!(
        "test2: value: {}, ptr to value: {}",
        test2.get_value(),
        test2.get_pointer_to_value()
    );
}
```

Executing the code gives:

```none
test1: value: test1, ptr to value: test1
test2: value: test2, ptr to value: test2
```

Nothing out of the ordinary right? You get the contents of `value` and `pointer_to_value` and print it. But the real danger happens when we swap the variables.

```rust
fn main() {
    // ...
    println!("Swapping...");
    std::mem::swap(&mut test1, &mut test2);

    println!(
        "test1: value: {}, ptr to value: {}",
        test1.get_value(),
        test1.get_pointer_to_value()
    );
    println!(
        "test2: value: {}, ptr to value: {}",
        test2.get_value(),
        test2.get_pointer_to_value()
    );
}
```

You might expect this to print:

```none
Swapping...
test1: value: test2, ptr to value: test2
test2: value: test1, ptr to value: test1
```

But to our surprise, this prints:

```none
Swapping...
test1: value: test2, ptr to value: test1
test2: value: test1, ptr to value: test2
```

### Unfolding the Mystery of Raw Pointers

So why did that happen? The answer is quite simple. "A pointer follows its pointee".

When we swapped the variables, the contents got swapped too. But that does not mean the pointers will change their pointee. This image demonstrates the point:

![Swapping Issues][swapping-image][^note-swapping]

But, this is not good as this might potentially lead to situations like "double free" and "incorrect access".

We need a way to tell Rust that our variables should not be moved. Or in other words, we need something that will encapsulate our objects and make them immovable.

## `Pin<T>` the objects

Meet `Pin<T>`! They "pin" objects to its location in memory[^note-pin].

Now, you can either pin to the stack or pin to the heap. For this case, pinning to the heap is the simplest and most viable option.

In Rust, we know that we can put a variable to the heap by using `Box<T>`, `Rc<T>` or `Arc<T>`. For this case, `Box<T>` is sufficient.

To our convenience, `Box<T>` provides a method called `Box::pin(...)`. We can use this to pin our object to encapsulate and prevent it from incorrect moves.

So how do we use `Pin<T>`? Let's modify our code to find out.

```rust
use std::pin::Pin;

#[derive(Debug)]
struct Test {
    // same as before
}

impl Test {
    fn new(txt: &str) -> Pin<Box<Self>> {  // return Pin<Box<Self>>
        let mut this = Box::pin(Test {
            value: String::from(txt),
            // In `C`, you'd call this initialize to `NULL`.
            pointer_to_value: std::ptr::null(),
        });
        this.as_mut().pointer_to_value = &this.value;
        this
    }

    fn get_value(self: Pin<&Self>) -> &str {  // modify `self` parameter
        &self.get_ref().value
    }

    // modify `self` parameter
    fn get_pointer_to_value(self: Pin<&Self>) -> &String {
        unsafe { &*(self.pointer_to_value) }
    }
}
```

**Note that whenever you use `Pin<T>`, the `self` argument is modified to accept a `Pin<T>` type only.**

Running the `main` function as before:

```rust
fn main() {
    let mut test1 = Test::new("test1");
    let mut test2 = Test::new("test2");

    println!(
        "test1: value: {}, ptr to value: {}",
        test1.as_ref().get_value(),
        test1.as_ref().get_pointer_to_value(),
    );
    println!(
        "test2: value: {}, ptr to value: {}",
        test2.as_ref().get_value(),
        test2.as_ref().get_pointer_to_value(),
    );

    println!("Swapping...");
    std::mem::swap(&mut test1, &mut test2);

    println!(
        "test1: value: {}, ptr to value: {}",
        test1.as_ref().get_value(),
        test1.as_ref().get_pointer_to_value()
    );
    println!(
        "test2: value: {}, ptr to value: {}",
        test2.as_ref().get_value(),
        test2.as_ref().get_pointer_to_value()
    );
}
```

This prints:

```none
test1: value: test1, ptr to value: test1
test2: value: test2, ptr to value: test2
Swapping...
test1: value: test2, ptr to value: test2
test2: value: test1, ptr to value: test1
```

As expected!

Note that we can still get a mutable reference to our enclosed `Test` by using `as_mut().get_mut()`. This cannot be good!

### `PhantomPinned` to the Rescue

By using `std::marker::PhantomPinned`, we tell Rust that our object cannot be unpinned (Rust calls it `!Unpin`. Read as "Not Unpinnable").

Now, any calls to `get_mut()` will fail.

So, how do you use it?

1. modify your struct to hold that extra field.

    ```diff
    use std::{
    +   marker::PhantomPinned,
        pin::Pin,
    };

    #[derive(Debug)]
    struct Test {
        value: String,
        pointer_to_value: *const String,
    +   _pinned: PhantomPinned,
    }
    ```

2. Initialize `PhantomPinned` in `new()`

    ```diff
    impl Test {
        fn new(txt: &str) -> Pin<Box<Self>> {
            let mut this = Box::pin(Test {
                value: String::from(txt),
                // In `C`, you'd call this initialize to `NULL`.
                pointer_to_value: std::ptr::null(),
    +           _pinned: PhantomPinned,
            });
            this.as_mut().pointer_to_value = &this.value;
            this
        }

    // ...
    }
    ```

Try to run it, and you'll face with yet another complaint from Rust! This time, it will say: **"cannot assign to data in a dereference of `Pin<&mut Test>`"**. So, what does that mean?

It means: in the presence of `PhantomPinned`, you cannot modify, or mutate through a dereference. This is a side effect of `PhantomPinned`.

To overcome this problem, we have to "force our way" into the enclosed object. That means, we will use `unsafe`.

```diff
impl Test {
    fn new(txt: &str) -> Pin<Box<Self>> {
        let mut this = Box::pin(Test {
            value: String::from(txt),
            // In `C`, you'd call this initialize to `NULL`.
            pointer_to_value: std::ptr::null(),
            _pinned: PhantomPinned,
        });
+       unsafe {
+           this.as_mut().get_unchecked_mut().pointer_to_value = &this.value;
+       }
        this
    }
// ...
}
```

Aaaand that's it! We have constructed a self-referential struct using `Pin`.

But why did we go through all this? This doesn't even solve our original problem?!

We went through this in order to understand the mechanism of Rust's `Pin` and its associated intricacies.

Now that we have understood how pinning works, let us go back to our original problem.

## Solving the Original Problem

Let us wrap `Me` with `Pin<T>`.

```rust
use std::{
   marker::PhantomPinned,
   pin::Pin,
}

#[derive(Debug)]
struct Me<'a> {
    my_holder: &'a Holder,
    _pinned: PhantomPinned,
}

impl Me {
    pub fn new(my_holder: &'a mut Holder) -> Pin<Box<Self>> {
        let this = Box::pin(Self {
            my_holder,
            _pinned: PhantomPinned,
        });

        let this_ptr: *mut _ = unsafe { val.as_mut().get_unchecked_mut() };
        my_holder.set_of_me.insert(this_ptr);

        val
    }
}
```

But we have a small problem with this scheme. But first, let us check what `Holder` looks like:

```rust
#[derive(Debug)]
struct Holder {
    set_of_me: BTreeSet<*mut Me>,
}
```

`Holder` holds several instances of `Me`. Or in other words, `Me` inserts itself in `Holder`, and it can insert at any time at any place. But if we keep using references for `Holder` (ie, `&'a mut Holder`), we'll soon realize that Rust does not allow us to go beyond what Borrow Checker permits.

We need to find a way to share references without letting Rust know that it is a reference. And it should be destroyed once its job is done.

## `Rc<T>` and `RefCell<T>`

`Rc<T>` is the reference counted version of `Box<T>`, and `RefCell<T>` allows you to mutate a seemingly immutable object. It is useful mostly in these contexts. So how do we use it?

First, we create a type alias for shorthand!

```rust
type RcCell<T> = Rc<RefCell<T>>;
```

Next, we modify `Holder` to return a `RcCell<Holder>`.

```rust
use std::{
   cell::RefCell,
   rc::Rc,
}

#[derive(Debug)]
struct Holder {
    set_of_me: BTreeSet<*mut Me>,
}

impl Holder {
    fn new() -> RcCell<Self> {
        Rc::new(RefCell::new(Self {
            set_of_me: Default::default(),
        }))
    }
}
```

Let's discuss a bit about `RefCell<T>`.

### Why `RefCell<T>`?

Let's see what happens when we try to modify anything in an `Rc<T>`:

```rust
fn main() {
    let mut x = Rc::new(String::from("EEE"));
    x.push('e');
}
```

The last line will complain: **"cannot borrow data in an `Rc` as mutable"**. That means, `Rc<T>` acts as an immutable enclosure around the object.

Now let's see what happens when we use `RefCell<T>`:

```rust
fn main() {
    let mut x = Rc::new(RefCell::new(String::from("EEE")));
    x.borrow_mut().push('e');
}
```

`RefCell<T>` adds a new method called `borrow_mut()` that allows you to receive a mutable reference to the underlying object. And the added benefit of using `RefCell<T>` is that it strictly follows Rust's borrowing rules. This ensures nothing funny or obscure happens with the object.

## Putting the Pieces Together

Let us tell `Me` to accept a `RcCell<Holder>`.

```diff
#[derive(Debug)]
struct Me {
+   my_holder: RcCell<Holder>,
    _pinned: PhantomPinned,
}

impl Me {
    pub fn new(
+       my_holder: RcCell<Holder>,
    ) -> Pin<Box<Self>> {
        let mut this = Box::pin(Self {
            my_holder,
            _pinned: PhantomPinned,
        });

        let this_ptr: *mut _ = unsafe { this.as_mut().get_unchecked_mut() };
+       this.my_holder.borrow_mut().set_of_me.insert(this_ptr);

        this
    }
}
```

But before you jump and rejoice, think about what happens in the end? What happens to the references in `Holder`'s `set_of_me` after an instance of `Me` has been destroyed?

Right! They are still there as **DANGLING POINTERS!**

We need a way to remove `Me` from `Holder`'s `set_of_me` when it will be destroyed. Fortunately, we have something called `Drop` trait in Rust.

```rust
impl Drop for Me {
    fn drop(&mut self) {
        let this = &(self as *mut _);
        self.my_holder.borrow_mut().set_of_me.remove(this);
    }
}
```

And that's it.

## Why not `Weak<T>` for storing `Me`?

Now you could ask, why go through all the pain of raw pointers and Pins when I could've used `Weak<T>`.

Yes you could've, but `Weak<T>` does not implement `Ord`, `PartialOrd`, `PartialEq` etc. This will limit usability to a great degree.

Similarly, you cannot use `Rc<T>` for storing `Me` because `Rc<T>` will not help you in resolving the circular reference and will create a memory leak.

## Solution

Here is the entire solution. Run it and experiment with it to understand how it works.

```rust
use std::{
    cell::RefCell, collections::BTreeSet, marker::PhantomPinned, pin::Pin,
    rc::Rc,
};
type RcCell<T> = Rc<RefCell<T>>;

#[derive(Debug)]
struct Holder {
    set_of_me: BTreeSet<*mut Me>,
}

impl Holder {
    fn new() -> RcCell<Self> {
        Rc::new(RefCell::new(Self {
            // this is initially empty
            set_of_me: Default::default(),
        }))
    }

    /// Mutate every value of `Me`.
    /// Note how a pinned value is reconstructed.
    fn mutate_value_of_me(&self, val: i32) {
        self.set_of_me.iter().for_each(|a| {
            let a = unsafe { Pin::new_unchecked(&mut **a) };
            a.mutate_me(val);
        })
    }
}

#[derive(Debug)]
struct Me {
    name: String,
    mutate_by_holder: i32,
    my_holder: RcCell<Holder>,
    _pinned: PhantomPinned,
}

impl Me {
    /// Accept a name
    pub fn new(
        holder: RcCell<Holder>,
        name: impl Into<String>,
    ) -> Pin<Box<Self>> {
        let mut this = Box::pin(Self {
            name: name.into(),
            mutate_by_holder: 0,
            my_holder: holder,
            _pinned: PhantomPinned,
        });

        let this_ptr: *mut _ = unsafe { this.as_mut().get_unchecked_mut() };
        this.my_holder.borrow_mut().set_of_me.insert(this_ptr);

        this
    }

    /// Allows you to mutate a value within me.
    /// Run this from `Holder` to see what happens.
    fn mutate_me(self: Pin<&mut Self>, val: i32) {
        let this = unsafe { self.get_unchecked_mut() };
        this.mutate_by_holder += val;
    }
}

impl Drop for Me {
    fn drop(&mut self) {
        println!("Dropping {:#?}", self);
        let this = &(self as *mut _);
        self.my_holder.borrow_mut().set_of_me.remove(this);
    }
}

/// A test function to play with `Holder`s.
fn make_ref_of_holder(holder: RcCell<Holder>) {
    let holder = Rc::clone(&holder);
    println!("Making a ref of {:?}", holder);
    println!("No. of refs = {}", Rc::strong_count(&holder));
}

pub fn main() {
    let holder = Holder::new();

    // be explicit about `Rc`'s cloning
    let a = Me::new(Rc::clone(&holder), "a");
    let b = Me::new(Rc::clone(&holder), "b");

    holder.borrow().mutate_value_of_me(455);
    make_ref_of_holder(Rc::clone(&holder));
}
```

If you look at the code carefully and the code that was shown before, you'd notice that we are suffering from one big issue: **Management of duplicate objects**.

## Duplicate Objects

To see what the problem is, add the following line to the code given in the [solution](#solution).

```diff
// ...
pub fn main() {
    let holder = Holder::new();

    // be explicit about `Rc`'s cloning
    let a = Me::new(Rc::clone(&holder), "a");
    let b = Me::new(Rc::clone(&holder), "b");
+   let c = Me::new(Rc::clone(&holder), "b");

    holder.borrow().mutate_value_of_me(455);
    make_ref_of_holder(Rc::clone(&holder));
}
```

We might think, "Oh since we are storing our `Me` objects in a set, `c` will not be added."

But notice that the definition of `set_of_me` is `BTreeSet<*mut Me>`. Which means, the set stores **unique pointers to `Me`, not unique `Me`s itself!** And that's why `c` gets stored in `holder`.

So what's the solution?

One way to solve this issue is to create a wrapper type over `*mut Me` that will allow dereferencing, and thus comparison of objects.

We will discuss about that in [Part 2.][part2]

## Conclusion

I hope this article helps you in understanding Rust's Self Referential Structs a bit better.

Questions? Comments? Concerns? Please put them down below and I'd be happy to help you.

Cover Image Source: Manjaro's `/usr/share/backgrounds` folder 😃

[^note-swapping]: Image taken from Rust Language's Async Tutorial Book
[^note-pin]: Taken from <https://doc.rust-lang.org/std/pin/index.html>

[part2]: https://dev.to/self-referential-structs-in-rust-part-2-1lc2
[rust-async]: https://rust-lang.github.io/async-book/04_pinning/01_chapter.html#pinning-in-detail
[swapping-image]: https://rust-lang.github.io/async-book/assets/swap_problem.jpg
[rust-lifetimes]: https://dev.to/arunanshub/demystifying-mutability-and-references-in-rust-caf