Recursive type representation in rustc

In an attempt to write a small toy compiler in Rust, I need to implement a type system for the compiler. Naturally, I take inspiration from the biggest compiler written in Rust: rustc.

Correct me if I'm wrong, because frankly understanding the workings of the compiler isn't easy, but AFAIK all types in rustc (I'm now talking about the "semantic" types, not the HIR ones) are interned and accesses via the Ty<'ctx> type, which is an immutable reference to TyS<'ctx>. My question is, how do I represent a recursive type such as:

struct S{
   x: Box<S>

when I don't have the Ty of the struct S before creating it and cannot modify the type once it's been created and interned?

1 Like

S here is a type definition, which like any other definition has a unique DefId. When you refer to S as type, a TyKind::Adt is used with this specific DefId. I believe the DefId of S is assigned before the field definitions are lowered to HIR, thus breaking the cycle.

I'm not familiar with how rustc does it, but one way of handling it is to use an API like Rc::new_cyclic. Basically, you separate "give me a place to put this" and "put this here," so that construction of the value has access to the handle to where it will end up.

Like @bjorn3 said, S is represented as a TyKind::Adt using a DefId. Since the rustc representation of recursive types confused me recently, I'll mention that TyKind::Adts do not include the fields' types. Instead, a TyKind::Adt looks roughly like this pseudocode:

struct S {

The type of S includes the DefId of S.x, which can then be used to look up the type of the field.


I realized it'd be a good idea to document this in the compiler itself, so I opened a PR: Document how recursion is handled for `ty::Ty` by camelid · Pull Request #90538 · rust-lang/rust · GitHub

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.