# Name resolution

<!-- toc -->

In the previous chapters, we saw how the [*Abstract Syntax Tree* (`AST`)][ast]
is built with all macros expanded. We saw how doing that requires doing some
name resolution to resolve imports and macro names. In this chapter, we show
how this is actually done and more.


In fact, we don't do full name resolution during macro expansion -- we only
resolve imports and macros at that time. This is required to know what to even
expand. Later, after we have the whole AST, we do full name resolution to
resolve all names in the crate. This happens in [`rustc_resolve::late`][late].
Unlike during macro expansion, in this late expansion, we only need to try to
resolve a name once, since no new names can be added. If we fail to resolve a
name, then it is a compiler error.

Name resolution is complex. There are different namespaces (e.g.
macros, values, types, lifetimes), and names may be valid at different (nested)
scopes. Also, different types of names can fail resolution differently, and
failures can happen differently at different scopes. For example, in a module
scope, failure means no unexpanded macros and no unresolved glob imports in
that module. On the other hand, in a function body scope, failure requires that a
name be absent from the block we are in, all outer scopes, and the global
scope.


## Basics

In our programs we refer to variables, types, functions, etc, by giving them
a name. These names are not always unique. For example, take this valid Rust
program:

```rust
type x = u32;
let x: x = 1;
let y: x = 2;
```

How do we know on line 3 whether `x` is a type (`u32`) or a value (1)? These
conflicts are resolved during name resolution. In this specific case, name
resolution defines that type names and variable names live in separate
namespaces and therefore can co-exist.

The name resolution in Rust is a two-phase process. In the first phase, which runs
during `macro` expansion, we build a tree of modules and resolve imports. Macro
expansion and name resolution communicate with each other via the
[`ResolverAstLoweringExt`] trait.

The input to the second phase is the syntax tree, produced by parsing input
files and expanding `macros`. This phase produces links from all the names in the
source to relevant places where the name was introduced. It also generates
helpful error messages, like typo suggestions, traits to import or lints about
unused items.

A successful run of the second phase ([`Resolver::resolve_crate`]) creates kind
of an index the rest of the compilation may use to ask about the present names
(through the `hir::lowering::Resolver` interface).

The name resolution lives in the [`rustc_resolve`] crate, with the bulk in
`lib.rs` and some helpers or symbol-type specific logic in the other modules.


## Namespaces

Different kind of symbols live in different namespaces ‒ e.g. types don't
clash with variables. This usually doesn't happen, because variables start with
lower-case letter while types with upper-case one, but this is only a
convention. This is legal Rust code that will compile (with warnings):

```rust
type x = u32;
let x: x = 1;
let y: x = 2; // See? x is still a type here.
```

To cope with this, and with slightly different scoping rules for these
namespaces, the resolver keeps them separated and builds separate structures for
them.

In other words, when the code talks about namespaces, it doesn't mean the module
hierarchy, it's types vs. values vs. macros.

## Scopes and ribs

A name is visible only in certain area in the source code. This forms a
hierarchical structure, but not necessarily a simple one ‒ if one scope is
part of another, it doesn't mean a name visible in the outer scope is also
visible in the inner scope, or that it refers to the same thing.

To cope with that, the compiler introduces the concept of [`Rib`]s. This is
an abstraction of a scope. Every time the set of visible names potentially changes,
a new [`Rib`] is pushed onto a stack. The places where this can happen include for