Ty chapter
This chapter explains how rustc represents types.

Ty

When we talk about how rustc represents types,  we usually refer to a type called Ty . There are quite a few modules and types for Ty in the compiler (Ty documentation). 

The specific Ty we are referring to is rustc::ty::Ty (and not rustc::hir::Ty). The distinction is important, so we will discuss it first before going into the details of ty::Ty.

hir::Ty vs ty::Ty

The HIR in rustc can be thought of as the high-level intermediate representation. It is more or less the AST (see this chapter) as it represents the syntax that the user wrote, and is obtained after parsing and some desugaring. It has a representation of types, but in reality it reflects more of what the user wrote, that is, what they wrote so as to represent that type.

In contrast, ty::Ty represents the semantics of a type, that is, the meaning of what the user wrote. For example, hir::Ty would record the fact that a user used the name u32 twice in their program, but the ty::Ty would record the fact that both usages refer to the same type.

Example: fn foo(x: u32) → u32 { }
In this function we see that u32 appears twice. We know that that is the same type, i.e. the function takes an argument and returns an argument of the same type, but from the point of view of the HIR there would be two distinct type instances because these are occurring in two different places in the program. That is, they have two different spans (locations).

Example: fn foo(x: &u32) -> &u32)
In addition, HIR might have information left out. This type &u32 is incomplete, since in the full rust type there is actually a lifetime, but we didn’t need to write those lifetimes. There are also some elision rules that insert information. The result may look like  fn foo<'a>(x: &'a u32) -> &'a u32)

In the HIR level, these things are not spelled out and you can say the picture is rather incomplete. However, at the ty::Ty level, these details are added and it is complete. Moreover, we will have exactly one ty::Ty for a given type, like u32, and that ty::Ty is used for all u32s in the whole program, not a specific usage, unlike hir::Ty.

Here is a summary:
hir::Ty (rustdoc)
ty::Ty (rustdoc)
Describe the syntax of a type: what the user wrote (with some desugaring).
Describe the semantics of a type: the meaning of what the user wrote.
Each hir::Ty has its own spans corresponding to the appropriate place in the program.
Doesn’t correspond to a single place in the user’s program.
hir::Ty only has generics and lifetimes the user wrote (since elided params don’t show up in the syntax)
ty::Ty has the full type, including generics and lifetimes, even if the user left them out
fn foo(x: u32) → u32 { } 
  • Two hir::Ty representing each usage of u32. Each has its own Spans, etc.
  • hir::Ty doesn’t tell us that both are the same type
fn foo(x: u32) → u32 { } 
  • One ty::Ty for all instances of u32 throughout the program.
  • ty::Ty tells us that both usages of u32 mean the same type.
fn foo(x: &u32) -> &u32)
  • Two hir::Ty again.
  • No lifetimes in the hir::Tys, because the user elided them
fn foo(x: &u32) -> &u32)
  • A single ty::Ty again.
  • The ty::Ty has the hidden lifetime param
Order
HIR is built directly from the AST, so it happens before ty. After HIR is built, some basic type inference and type checking is done. During the type inference, we figure out what the ty::Ty of everything is and we also check if the type of something is ambiguous. The ty::Ty then, is used for type checking while making sure everything has the expected type.

How semantics drive the two instances of Ty
You can think of HIR as the “default” perspective of the type information. We assume two things are distinct until they are proven to be the same thing. In other words, we know less about them, so we should assume less about them.

They are syntactically two strings: “u32”at line N column 20 and “u32” at line N column 35. We don’t know that they are the same yet. So, in the HIR we treat them as if they are different. Later, we determine that they semantically are the same type and that’s the ty::Ty we use.

Consider another example: fn foo<T>(x: T) -> u32 and suppose that someone invokes foo::<u32>(0).  This means that T and u32 (in this invocation) actually turns out to be the same type, so we would end up with the same ty::Ty in the end, but we have distinct hir::Ty.

ty::Ty implementation

rustc::ty::Ty is actually a type alias to &TyS (rustdoc) (more about that later). TyS (Type Structure) is where the main functionality is located. So in general, we are passing around references to TyS. In particular, TyS has a sty field of type TyKind (rustdoc), which represents the key type information. TyKind is a big enum which represents different kinds of types (e.g. primitives, references, abstract data types, generics, lifetimes, etc). TyS also has 2 more fields, flags and outer_exclusive_binder they are convenient hacks for efficiency and summarize information about the type that we may want to know, but they don’t come into the picture as much here.

Note: TyKind is NOT the functional programming concept of Kind.

Whenever working with Tys (plural Ty) in the compiler, it is common to match on the kind of type:

fn foo(x: Ty<'tcx>) {
  match x.sty {
    ...