How can we teach people about self-referential types?

[Michael-F-Bryan]

About once or twice a week you'll see someone ask how to define something which is logically equivalent to a self-referential type.

I'm not trying to bash on people for asking these questions - I actually think it's awesome that they're stretching themselves and experimenting with lifetimes - but whenever the topic comes up we tend to shut it down saying "self-referential types are impossible in (safe) Rust so you'll need to redesign your code"... Which isn't particularly helpful when I've just engineered myself into a corner and need to refactor a couple hundred lines of code to get out.

My question to you:

1. What made things finally "click" for you?
2. Have you heard any particularly elegant ways of explaining self-referential types?
3. What are some general strategies that you use to avoid getting into situations involving self-referential types?

[mbrubeck]

Thanks for starting this topic. I've been wishing for a long time for a definitive “What about self-referential types?” FAQ, but it’s such a complicated topic that I haven’t gathered the energy to write it myself. I’d love to help put something together, though.

@Michael-F-Bryan

What are some general strategies that you use to avoid getting into situations involving self-referential types?

For referencing elements or slices of a collection, alongside the collection itself:

• Separate the type into two different types, one that owns the collection and one that references it. Require callers to keep the owning type alive while using the referencing type.
• Store indices or ranges of indices, rather than references. (Works best for immutable or append-only sequences.)
• Use a library like owning-ref that provides a safe API for references to heap storage that is known not to change address when its owner moves.
• Use Pin along with a library like moveit to ensure that values are updated when their addresses change.

For parent/child relationships where the parent owns the child, and operating on the child needs a reference back to the parent:

• Avoid storing parent references in the child. Instead, always accessing the child via its parent, so the caller already has a parent reference available and can pass it to functions that need it.
• Use shared ownership with Arc/Rc, and use Weak for back-links to prevent cycles.

For tree, linked list, or acyclic graph structures, where child nodes need back-references to their parents:

• Use one of the strategies for parent/child relationships, above.
• Or, use one of the strategies for arbitrary graphs, below...

For arbitrary graphs that may or may not contain cycles:

• Use a slab allocator that can give out shared references with the lifetime of the slab.
• Store nodes in a vector or arena and use indices (or generational indices) as links, instead of references.
• Use Arc/Rc, plus code to detect and break cycles when nodes are removed (if necessary).
• Use a specialized crate like petgraph or an entity-component-system (ECS) library.

When you are an expert in unsafe Rust and implementing a performance-critical data structure and you are absolutely sure that none of the above strategies is viable:

• Write custom unsafe code using raw pointers and/or Pin, and make sure you manually verify that it cannot ever violate any of Rust's memory-safety rules.

[geebee22]

@Michael-F-Bryan

"self-referential types are impossible in (safe) Rust so you'll need to redesign your code"

I don't think that's a helpful response. You certainly can have self referencing, using Rc/RefCell.

I think a lot of the problem is that people WANT (for no good reason) to use simple references for cases where they cannot be used. In languages such as C#, every Object is represented (effectively, disregarding the different approach to garbage collection) as a Rc/RefCell and you certainly can do that in Rust, and it can be a perfectly good solution, that's why it is there in the standard library.

[quinedot]

@Michael-F-Bryan

What made things finally "click" for you?

It was over-all gradual for me, but certain common scenarios have problems that aren't too hard to explain.

---

struct Sibling<'a, T> {
    brother: T,
    sister: T,
    current_sibling: &'a T,
}

If you have a reference to a field of yourself that is on the stack, it's going to be invalidated when you move yourself. And you move yourself all the time (assignments, function calls...).

Why not use relative pointers? First, Rust doesn't have such a distinction today. Second, relative pointers to the heap would break when moved, so a distinction is needed. Third, in most cases, a relative pointer is approximately the same as an index (so just use an index).

(Then hope you don't have to explain Pin and everything.)

---

struct Heaped<'a, T> {
    things: Vec<T>,
    current: &'a T,
}

impl<'a, T> Heaped<'a, T> {
    fn grow(&mut self, item: T) {
        self.things.push(item);
    }
}

Eventually that Vec will grow reallocate, at which point all your stored items can move and your reference will be invalidated.

---

I think a lot of cases also just follow from understanding the borrowing and aliasing constraints. If I have a reference to somewhere within myself, I can't create &mut to myself. Also, 'self would be some sort of dynamic run-time scope, and lifetimes are not dynamic and erased during compilation.

[trentj]

I agree that as a community we could do better with these kinds of questions. Especially because self-referencing objects are possible in safe Rust; in fact, sometimes they're pretty easy to make, and the compiler helps you avoid breaking things with them... which is of course where the problems come in, because many things you might want to do with a self-referential struct actually do break it.

On the other hand, these questions are almost always rooted in an XY problem. Most code snippets that people post don't really demonstrate a need for self-reference at all. But because people also don't post their functional requirements that led them (however erroneously) to their current design, it's not like one can backtrack to the point where they started going wrong and correct the design.

Data structure design is software engineering, and you can't do it without a firm grasp of what problem is being solved and which constraints must be met. When someone posts "I have this design, how do I make it work?" with zero functional requirements and some code that clearly won't work, there's often not much to say beyond "You need to go back to the drawing board."

That said, obviously many other languages don't have such issues with self-reference. Why is that? In C++ you have move and copy constructors to "fix up" references inside structs when moved - that's one answer. In Java every object is reference counted; that's another. Both of these approaches are possible to write manually in (even mostly safe) Rust, so if you've really painted yourself into a corner and self-referencing is actually the only solution, you can write it, it's just going to be massively inconvenient.

How do you avoid that? I don't think there are any secrets to good design, and there's no magic technique that will turn every self-referential pumpkin into an elegant data-oriented carriage. You just need to know your functional requirements and pick a design that plays to the strengths of your tools. Designing software in Rust is different than designing software in Java; not all the same techniques apply.

[quinedot]

Just to clarify @Michael-F-Bryan, are you aiming for

Since you're new to Rust, let us explain why self-referential structs are tricky, why you may want to consider avoiding them for now, and go over some alternative designs.

Or,

OK, you're sure that you want a self-referential struct. Let's walk through how we can accomplish that in Rust, and the caveats you'll need to keep in mind.

Or both? (I think the community does need both. I also think we see mostly the first response on this forum because so many of the posts are of the "as my first project in Rust..." variety.)

[Michael-F-Bryan]

I think the first answer would be the most in-demand, simply because self-referencing types are easy to create when you try to naively bring across a solution from another language. I also feel like it's the easiest of the two to answer because it essentially boils down to explaining lifetimes in more detail and that the programmer is trying to create something which outlives itself.

However, when you legitimately need to know how to create self-referencing types then you really need to know.

If I were teaching someone or writing documentation I'd keep the two answers separate, though. You don't want to confuse people by saying "don't create self-referencing types, they don't work because X, Y, and Z, it's probably an X-Y problem... buuuut, if you really do want to make them then this is how".

[Michael-F-Bryan]

@mbrubeck

Separate the type into two different types, one that owns the collection and one that references it. Require callers to keep the owning type alive while using the referencing type.

Yeah, this is probably what I'd be first to recommend... You side-step the entire problem by removing the "self" in "self-referential types".

I'll admit that it actually took a bit of thinking to figure out what I do to avoid getting into these situations. Most of the time I'll be thinking up a design and feel that three or four steps down the road it might give me lifetime issues, so I'll subconsciously steer clear of those situations.

After first seeing it shown off at a Rust conference talk, I think @mcy's moveit crate is the direction we should be pointing people down when they actually need to create self-referencing types (@quinedot's second question). It's not nearly as ergonomic as implicitly called move constructors, but arguably that extra speed bump isn't a bad thing.

@trentj

On the other hand, these questions are almost always rooted in an XY problem . Most code snippets that people post don't really demonstrate a need for self-reference at all. But because people also don't post their functional requirements that led them (however erroneously) to their current design, it's not like one can backtrack to the point where they started going wrong and correct the design.

You really hit the nail on the head here!

I feel like this is the underlying reason I come away unsatisfied whenever I try to help someone that accidentally created a self-referencing type. It's also easy to get dragged down the XY path and then when you try to point it out, the other person may not take it very well.

@trentj

How do you avoid that? I don't think there are any secrets to good design, and there's no magic technique that will turn every self-referential pumpkin into an elegant data-oriented carriage. You just need to know your functional requirements and pick a design that plays to the strengths of your tools. Designing software in Rust is different than designing software in Java; not all the same techniques apply.

The annoying thing is I kinda agree with you here. There's no silver bullet to success, and to design something well you need to have a good understanding of the problem and the available solution space to figure out something which works well enough for your application. To an extent, you can't really get around that.

But... that's arguably less helpful (from the perspective of someone asking the question, anyway) than saying "self-referencing types aren't possible in safe Rust, go back to the drawing board" because you're effectively saying "spend a couple of years learning to be a good software engineer and come back to me"

[Yandros]

My own remarks:

• For those coming with an engineering "design issue" that aren't ready yet to hear a "this is an XY problem" kind of answer, I often tell them about reference counting with weak refs. It can be a bit cumbersome, but at least it is correct and safe (the worse thing that can happen being memory leaks if they get their cycles wrong).

  • What I like about suggesting this approach is that smart pointers / reference-counting is way closer to what most programmers from gc languages have in mind when you say the word reference, which is why they'll incredibly often incorrectly reach for Rust reference (and the lifetime infection) when wanting to express that they have a Foo which references a Bar. @kornel has become our professional explainer about this very issue , and, in a way, it's often this underlying problem which transpires into self-referential patterns.

• One big issue with people at this point is one huge flaw in Rust's documentation and culture: to say that &mut is the mutable reference type! So I personally find also quite useful to start with having people unlearn that quite inaccurate notion, since obviously one of the typical issues with self-referential structures is that you can't be using unique references anymore, which of course does not preclude mutation, but then the beginners are disgusted by seeing that they can't use &mut and that they need to use "unheard-of" shared mutability tools which are thus often incorrectly perceived as hacks around Rust rules.

  By correctly explaining this unique and novel invention in Rust that are unique references, and separating it from the concept of mutable reference, one can then finally start tackling self-referential and thus aliased data structures.

• What @mbrubeck mentioned about requiring an owner and a borrower is completely on point, then, to avoid the self-referential pattern. But for those really wanting to have it, you can then feature it by having a "pre-init" owner which is then properly init while borrowed (it then becomes unmoveable).

  struct Person<'slf> {
      full_name: String,
      name: &'slf str,
      surname: &'slf str,
  }
  
  impl<'slf> Person<'slf> {
      fn new(full_name: String) -> Option<Self> {
          if full_name.split(" ").count() != 2 {
              None
          } else {
              Some(Self {
                  full_name,
                  // silly "uninit" values…
                  name: "".into(),
                  surname: "".into(),
              })
          }
      }
  
      //       the signature move (heh) of self-referentiability
      //             vvvv           vvvvvv
      fn init(self: &'slf mut Person<'slf>) -> &Self {
          let ref mut words = self.full_name.split(" ");
          self.name = words.next().unwrap();
          self.surname = words.next().unwrap();
          self
      }
  }
  
  fn main() {
      let mut person = Person::new("Alex Doe".into()).unwrap();
      let person = person.init();
      dbg!(person.name);
      dbg!(person.surname);
  }
  
  

  But this can be perceived as "quirky" given how a constructor is now necessarily split across this "pre-allocate and then init the self-refs" double step. Indeed, unless some extra type-level magic shenanigans are involved (to ensure a correct state machine), people may be interacting with a semantically uninit entity. And such shenanigans will probably require unsafe to use (or a helper crate to do it for us, such as ref_cast - Rust).

  In that regard, continuation-passing style (which is an underrated pattern which can be made more ergonomic with my experimental ::with_locals crate (I still have to polish a few rough edges there, though)), can be a great tool to keep this construction contained within a single (callback-based) function):

  impl Person<'_> {
      #[with]
      fn new(full_name: String) -> Option<&'ref Person<'ref>> {
          let ref mut this = Person {
              full_name,
              name: "",
              surname: "",
          };
          let ref mut words = this.full_name.split(" ");
          this.name = words.next()?;
          this.sur_name = words.next()?;
          if words.next().is_some() { return None; }
          Some(this)
      }
  }
  
  #[with] /* hypothetical syntax not yet featured by the crate */
  fn main() {
      let person = with!(Person::new("Alex Doe".into())).unwrap();
      dbg!(person.name);
      dbg!(person.surname);
  }
  

  • Implementation / manual Playground

  Another alternative are more direct / ad-hoc macros, much like pin_mut!() does —interestingly enough, safe stack pinning shares many similarities with self-referential structs: both need maximal borrows. So for instance, safe stack pinning could also be featured with a scoped API…

  new_person! {
      let person = Person::new("Alex Doe".into())?;
  }
  

• At this point, using a helper crate with, again, some macros for nicer ergonomics, but targeted at self-referential structures, such as ::ouroboros, can be a very good idea. That crate, or at least the idea behind its design (I haven't personally verified how it's implemented, but the higher-order-lifetime-based API is definitely the correct approach to the problem here, in order to remain correct and not too unergonomic), definitely deserves more credit.

• Careful with unsafe

  This is also one of the key things that ought to be mentioned when talking of self-referential structs, and people that might be tempted with either DIY approaches, or using certain approaches such as owning-ref which may look tempting thanks to featuring an API simpler than ouroboros's, for instance.

  There are two dangers here:

  • one is misusing the Pin API, since it may trick people into a false sense of security: Pin is the most subtle and error-prone abstraction in the whole standard library. While Pinning stuff safely is not that hard —thanks to Box::pin or the pervasive-and-not-yet-in-the-stdlib-for-some-reason pin_mut! macro—, correctly definining non-Unpin types and their API, on the other hand, is not! The whole Pin abstraction works well with async-constructed self-referential futures, because such self-referential structures are compiler-generated. The moment you are dealing with your own defined types and safety invariants, it is quite easy to get those wrong. Especially once we are dealing with the second point:

  • Aliasing!

    
    A disclaimer regarding Stacked Borrows ≠ official UB rules

    Granted, the official Rust aliasing rules haven't been fully fledged yet, but that's all the more reason to conservatively tread with even more caution, while waiting for these to be laid out and express what kind of operations are allowed. The best and kind of only formal model out there, and thus candidate for one day becoming part of the official rules of Rust, is called Stacked Borrows, and is the implementation behind the checks of the "Undefined Behavior detector" tool called MIRI. So, when you run something by miri and it complains about UB, chances are that your code does feature UB, even if some of the rules in Stacked Borrows are currently deemed a bit too restrictive w.r.t. the code out there (especially those relating to aliasing), and so might be loosened a bit in the future (should the model be able to accommodate to that!). For the remainder of this post, I'll be following the current Stacked Borrows model to call out some stuff as UB. Since it's kind of the only consistent formal model out there, I believe this is a legitimate thing to do, no matter how much this may displease the programmers used to writing (often-UB-according-to-the-standard) C code that freely manipulates pointers around.

    ---

    Here we are back to what I was mentioning about lack of unique references with self-referential structs, which is something that still holds true, except that in the midst of unsafe code and raw pointers we no longer have the borrow checker to protect us from the aliasing mistakes. The most common received idea bout this whole topic is that, the moment one is operating off raw pointers, and thus the borrow checker does not yell at them, the aliasing rules don't have to be enforced, provided they don't trigger use-after-frees.

    Let's start with a basic silly example, shall we?

    let (_my_ref, ptr) = {
        let my_ref: &'static mut i32 = Box::leak(Box::new(42));
        let ptr = my_ref as *const i32;
        (my_ref, ptr)
    };
    println!("{}", unsafe { *ptr }); // UB
    

    This code features Undefined Behavior, and if you run it by miri (with the slower -Zmiri-track-raw-pointers flag, which, alas, isn't used in the Playground), you get:

    

    Miri is an awesome tool: we can query it to better explain where the issue lies, by feeding it that 3256 identifier it printed:

    

    What Miri / Stacked Borrows is saying here is that when my_ref is moved over to _my_ref, since it is a unique reference, the move, which counts as a usage of the reference, thus asserts that unicity / lack of aliasing property. This can only hold if the other pointer with which one could technically reach the pointee is never to be used from this point onwards. We thus say that the pointer ptr has been invalidated: it is no longer allowed to be dereferenced, not even for a read. This shouldn't be that surprising, since, if ptr had been a &i32 instead of *const i32, the borrow checker would have already told us that. This is where many people have a misconception regarding raw pointers.

    If this snippet looks silly, know that &mut is not the only Rust type which asserts lack of aliasing when accessed or moved around. Types such as Box also assert lack of aliasing

    So our silly example can start becoming a bit less silly:

    let (_my_box, ptr) = {
        let my_box = Box::new(42);
        let ptr = &*my_box as *const i32;
        (my_box, ptr)
    };
    println!("{}", unsafe { *ptr });
    

    

    Now, if you still consider that example to be silly, know that this is exactly what crates such as ::owning_ref already do

    

    So, the "pointer intuitive thing" that owning-ref does is very likely UB, and I very much doubt that the implementations that other people may write will be that different from what owning-ref does (FWIW, in non-generic cases, the UB can be dodged by using raw pointers everywhere (e.g., applying Box::into_raw to my_box and only reverting the operation after the last usage of ptr (such as in the Drop impl of the wrapper type)).

  So, combine the dangers of Pin's too-subtle-and-error-prone API, with the dangers of mixing raw pointers with high-level Rust pointer/ref types which feature aliasing invariants, and add the desire of people to mutate stuff, which shall intuitively reach fo &mut, and the fact that self-referential patterns come more often to to beginners than to experienced Rust programmers who shall try to circumvent the issue with one of the multiple options @mbrubeck mentioned (or with ::ouroboros), and we end up with the likelihood of UB in unsafe-featuring self-referential data structures to be awfully high.

  • In that regard, the ::moveit is indeed a promising approach, albeit one with yet again a big amount of unsafe code that the user needs to write (too much Pin there not to be error-prone). I'd thus wait for it to start featuring more macros or APIs that could side step the unsafety problem (e.g., structural projectings here and there), until reaching a point where the downstream user wouldn't have to write any unsafe. Until then, while an interesting crate theoretically speaking, I would still rather advocate for ::ouroboros as the helper crate to reach for (for self-referential structs, of course! ::moveit is more general with the move constructors).

[scottmcm]

@mbrubeck

Separate the type into two different types, one that owns the collection and one that references it. Require callers to keep the owning type alive while using the referencing type.

This seems to be the big one to me.

What I see really often is the "this is a parser and I want it to hold the String and the &strs". Maybe there's a way to talk about that in terms of mixing ownership styles -- the parser doesn't need to own what it's parsing, so it generally shouldn't, and then the self-referential part disappears without ever needing to mention it.

Perhaps we could leverage the analogy of not passing x: String when all you need is x: &str?