becomes a proper set-in-stone AST with side-tables. It happens as
         follows:
         - If the macro produces tokens (e.g. a proc macro), we parse into
           an AST, which may produce parse errors.
         - During expansion, we create [`SyntaxContext`]s (hierarchy 2) (see
           [Hygiene][hybelow] below).
         - These three passes happen one after another on every AST fragment
           freshly expanded from a macro:
           - [`NodeId`]s are assigned by [`InvocationCollector`]. This
             also collects new macro calls from this new AST piece and
             adds them to the queue.
           - ["Def paths"][defpath] are created and [`DefId`]s are
             assigned to them by [`DefCollector`].
           - Names are put into modules (from the resolver's point of
             view) by [`BuildReducedGraphVisitor`].
      3. After expanding a single macro and integrating its output, continue
         to the next iteration of [`fully_expand_fragment`][fef].
   5. If it's not resolved:
      1. Put the macro back in the queue.
      2. Continue to next iteration...


### Error Recovery

If we make no progress in an iteration we have reached a compilation error
(e.g. an undefined macro). We attempt to recover from failures (i.e.
unresolved macros or imports) with the intent of generating diagnostics.
Failure recovery happens by expanding unresolved macros into
[`ExprKind::Err`][err] and allows compilation to continue past the first error
so that `rustc` can report more errors than just the original failure.


### Name Resolution

Notice that name resolution is involved here: we need to resolve imports and
macro names in the above algorithm. This is done in
[`rustc_resolve::macros`][mresolve], which resolves macro paths, validates
those resolutions, and reports various errors (e.g. "not found", "found, but
it's unstable", "expected x, found y"). However, we don't try to resolve
other names yet. This happens later, as we will see in the chapter: [Name
Resolution](./name-resolution.md).


### Eager Expansion

_Eager expansion_ means we expand the arguments of a macro invocation before
the macro invocation itself. This is implemented only for a few special
built-in macros that expect literals; expanding arguments first for some of
these macro results in a smoother user experience.  As an example, consider
the following:

```rust,ignore
macro bar($i: ident) { $i }
macro foo($i: ident) { $i }

foo!(bar!(baz));
```

A lazy-expansion would expand `foo!` first. An eager-expansion would expand
`bar!` first.

Eager-expansion is not a generally available feature of Rust.  Implementing
eager-expansion more generally would be challenging, so we implement it for a
few special built-in macros for the sake of user-experience.  The built-in
macros are implemented in [`rustc_builtin_macros`], along with some other
early code generation facilities like injection of standard library imports or
generation of test harness. There are some additional helpers for building
AST fragments in [`rustc_expand::build`][reb]. Eager-expansion generally
performs a subset of the things that lazy (normal) expansion does. It is done
by invoking [`fully_expand_fragment`][fef] on only part of a crate (as opposed
to the whole crate, like we normally do).

### Other Data Structures

Here are some other notable data structures involved in expansion and
integration:
- [`ResolverExpand`] - a `trait` used to break crate dependencies. This allows the
  resolver services to be used in [`rustc_ast`], despite [`rustc_resolve`] and
  pretty much everything else depending on [`rustc_ast`].
- [`ExtCtxt`]/[`ExpansionData`] - holds various intermediate expansion
  infrastructure data.
- [`Annotatable`] - a piece of AST that can be an attribute target, almost the same
  thing as [`AstFragment`] except for types and patterns that can be produced by
  macros but cannot be annotated with attributes.
- [`MacResult`] - a "polymorphic" AST fragment, something that can turn into