# Recursive type representation in rustc

**URL:** <https://internals.rust-lang.org/t/recursive-type-representation-in-rustc/15235>\
**Category:** compiler\
**Created:** [August 29, 2021, 10:53am UTC](https://internals.rust-lang.org/t/recursive-type-representation-in-rustc/15235 "2021-08-29T10:53:31Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![theodore23](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/theodore23/32/8010_2.png) [@theodore23](https://internals.rust-lang.org/u/theodore23)\
**Post date:** [August 29, 2021, 10:53am UTC](https://internals.rust-lang.org/t/recursive-type-representation-in-rustc/15235/1 "2021-08-29T10:53:31Z")

</div>

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:

```rust
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?

---

<div class="post-metadata">

**Author:** ![bjorn3](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bjorn3/32/2736_2.png) [@bjorn3](https://internals.rust-lang.org/u/bjorn3)\
**Post date:** [August 29, 2021, 12:19pm UTC](https://internals.rust-lang.org/t/recursive-type-representation-in-rustc/15235/2 "2021-08-29T12:19:50Z")

</div>

`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.

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [August 29, 2021, 12:20pm UTC](https://internals.rust-lang.org/t/recursive-type-representation-in-rustc/15235/3 "2021-08-29T12:20:09Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![camelid](https://avatars.discourse-cdn.com/v4/letter/c/c67d28/32.png) [@camelid](https://internals.rust-lang.org/u/camelid)\
**Post date:** [November 3, 2021, 2:13am UTC](https://internals.rust-lang.org/t/recursive-type-representation-in-rustc/15235/4 "2021-11-03T02:13:07Z")

</div>

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::Adt`s do _not_ include the fields' types. Instead, a `TyKind::Adt` looks roughly like this pseudocode:

```rust
struct S {
    x
}

```

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

---

<div class="post-metadata">

**Author:** ![camelid](https://avatars.discourse-cdn.com/v4/letter/c/c67d28/32.png) [@camelid](https://internals.rust-lang.org/u/camelid)\
**Post date:** [November 3, 2021, 6:16pm UTC](https://internals.rust-lang.org/t/recursive-type-representation-in-rustc/15235/5 "2021-11-03T18:16:38Z")

</div>

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](https://github.com/rust-lang/rust/pull/90538)

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [February 1, 2022, 6:16pm UTC](https://internals.rust-lang.org/t/recursive-type-representation-in-rustc/15235/6 "2022-02-01T18:16:47Z")

</div>

Closed on February 1, 2022, 6:16pm UTC

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