src/librustc/README.md

   1 An informal guide to reading and working on the rustc compiler.
   2 ==================================================================
   3
   4 If you wish to expand on this document, or have a more experienced
   5 Rust contributor add anything else to it, please get in touch:
   6
   7 * https://internals.rust-lang.org/
   8 * https://chat.mibbit.com/?server=irc.mozilla.org&channel=%23rust
   9
  10 or file a bug:
  11
  12 https://github.com/rust-lang/rust/issues
  13
  14 Your concerns are probably the same as someone else's.
  15
  16 You may also be interested in the
  17 [Rust Forge](https://forge.rust-lang.org/), which includes a number of
  18 interesting bits of information.
  19
  20 Finally, at the end of this file is a GLOSSARY defining a number of
  21 common (and not necessarily obvious!) names that are used in the Rust
  22 compiler code. If you see some funky name and you'd like to know what
  23 it stands for, check there!
  24
  25 The crates of rustc
  26 ===================
  27
  28 Rustc consists of a number of crates, including `syntax`,
  29 `rustc`, `rustc_back`, `rustc_trans`, `rustc_driver`, and
  30 many more. The source for each crate can be found in a directory
  31 like `src/libXXX`, where `XXX` is the crate name.
  32
  33 (NB. The names and divisions of these crates are not set in
  34 stone and may change over time -- for the time being, we tend towards
  35 a finer-grained division to help with compilation time, though as
  36 incremental improves that may change.)
  37
  38 The dependency structure of these crates is roughly a diamond:
  39
  40 ````
  41                   rustc_driver
  42                 /      |       \
  43               /        |         \
  44             /          |           \
  45           /            v             \
  46 rustc_trans    rustc_borrowck   ...  rustc_metadata
  47           \            |            /
  48             \          |          /
  49               \        |        /
  50                 \      v      /
  51                     rustc
  52                        |
  53                        v
  54                     syntax
  55                     /    \
  56                   /       \
  57            syntax_pos  syntax_ext
  58 ```
  59
  60 The `rustc_driver` crate, at the top of this lattice, is effectively
  61 the "main" function for the rust compiler. It doesn't have much "real
  62 code", but instead ties together all of the code defined in the other
  63 crates and defines the overall flow of execution. (As we transition
  64 more and more to the [query model](ty/maps/README.md), however, the
  65 "flow" of compilation is becoming less centrally defined.)
  66
  67 At the other extreme, the `rustc` crate defines the common and
  68 pervasive data structures that all the rest of the compiler uses
  69 (e.g., how to represent types, traits, and the program itself). It
  70 also contains some amount of the compiler itself, although that is
  71 relatively limited.
  72
  73 Finally, all the crates in the bulge in the middle define the bulk of
  74 the compiler -- they all depend on `rustc`, so that they can make use
  75 of the various types defined there, and they export public routines
  76 that `rustc_driver` will invoke as needed (more and more, what these
  77 crates export are "query definitions", but those are covered later
  78 on).
  79
  80 Below `rustc` lie various crates that make up the parser and error
  81 reporting mechanism. For historical reasons, these crates do not have
  82 the `rustc_` prefix, but they are really just as much an internal part
  83 of the compiler and not intended to be stable (though they do wind up
  84 getting used by some crates in the wild; a practice we hope to
  85 gradually phase out).
  86
  87 Each crate has a `README.md` file that describes, at a high-level,
  88 what it contains, and tries to give some kind of explanation (some
  89 better than others).
  90
  91 The compiler process
  92 ====================
  93
  94 The Rust compiler is comprised of six main compilation phases.
  95
  96 1. Parsing input
  97 2. Configuration & expanding (cfg rules & syntax extension expansion)
  98 3. Running analysis passes
  99 4. Translation to LLVM
 100 5. LLVM passes
 101 6. Linking
 102
 103 Phase one is responsible for parsing & lexing the input to the compiler. The
 104 output of this phase is an abstract syntax tree (AST). The AST at this point
 105 includes all macro uses & attributes. This means code which will be later
 106 expanded and/or removed due to `cfg` attributes is still present in this
 107 version of the AST. Parsing abstracts away details about individual files which
 108 have been read into the AST.
 109
 110 Phase two handles configuration and macro expansion. You can think of this
 111 phase as a function acting on the AST from the previous phase. The input for
 112 this phase is the unexpanded AST from phase one, and the output is an expanded
 113 version of the same AST. This phase will expand all macros & syntax
 114 extensions and will evaluate all `cfg` attributes, potentially removing some
 115 code. The resulting AST will not contain any macros or `macro_use` statements.
 116
 117 The code for these first two phases is in [`libsyntax`][libsyntax].
 118
 119 After this phase, the compiler allocates IDs to each node in the AST
 120 (technically not every node, but most of them). If we are writing out
 121 dependencies, that happens now.
 122
 123 The third phase is analysis. This is the most complex phase in the compiler,
 124 and makes up much of the code. This phase included name resolution, type
 125 checking, borrow checking, type & lifetime inference, trait selection, method
 126 selection, linting and so on. Most of the error detection in the compiler comes
 127 from this phase (with the exception of parse errors which arise during
 128 parsing). The "output" of this phase is a set of side tables containing
 129 semantic information about the source program. The analysis code is in
 130 [`librustc`][rustc] and some other crates with the `librustc_` prefix.
 131
 132 The fourth phase is translation. This phase translates the AST (and the side
 133 tables from the previous phase) into LLVM IR (intermediate representation).
 134 This is achieved by calling into the LLVM libraries. The code for this is in
 135 [`librustc_trans`][trans].
 136
 137 Phase five runs the LLVM backend. This runs LLVM's optimization passes on the
 138 generated IR and generates machine code resulting in object files. This phase
 139 is not really part of the Rust compiler, as LLVM carries out all the work.
 140 The interface between LLVM and Rust is in [`librustc_llvm`][llvm].
 141
 142 The final phase, phase six, links the object files into an executable. This is
 143 again outsourced to other tools and not performed by the Rust compiler
 144 directly. The interface is in [`librustc_back`][back] (which also contains some
 145 things used primarily during translation).
 146
 147 A module called the driver coordinates all these phases. It handles all the
 148 highest level coordination of compilation from parsing command line arguments
 149 all the way to invoking the linker to produce an executable.
 150
 151 Modules in the librustc crate
 152 =============================
 153
 154 The librustc crate itself consists of the following submodules
 155 (mostly, but not entirely, in their own directories):
 156
 157 - session: options and data that pertain to the compilation session as
 158   a whole
 159 - middle: middle-end: name resolution, typechecking, LLVM code
 160   generation
 161 - metadata: encoder and decoder for data required by separate
 162   compilation
 163 - plugin: infrastructure for compiler plugins
 164 - lint: infrastructure for compiler warnings
 165 - util: ubiquitous types and helper functions
 166 - lib: bindings to LLVM
 167
 168 The entry-point for the compiler is main() in the [`librustc_driver`][driver]
 169 crate.
 170
 171 The 3 central data structures:
 172 ------------------------------
 173
 174 1. `./../libsyntax/ast.rs` defines the AST. The AST is treated as
 175    immutable after parsing, but it depends on mutable context data
 176    structures (mainly hash maps) to give it meaning.
 177
 178    - Many – though not all – nodes within this data structure are
 179      wrapped in the type `spanned<T>`, meaning that the front-end has
 180      marked the input coordinates of that node. The member `node` is
 181      the data itself, the member `span` is the input location (file,
 182      line, column; both low and high).
 183
 184    - Many other nodes within this data structure carry a
 185      `def_id`. These nodes represent the 'target' of some name
 186      reference elsewhere in the tree. When the AST is resolved, by
 187      `middle/resolve.rs`, all names wind up acquiring a def that they
 188      point to. So anything that can be pointed-to by a name winds
 189      up with a `def_id`.
 190
 191 2. `middle/ty.rs` defines the datatype `sty`. This is the type that
 192    represents types after they have been resolved and normalized by
 193    the middle-end. The typeck phase converts every ast type to a
 194    `ty::sty`, and the latter is used to drive later phases of
 195    compilation. Most variants in the `ast::ty` tag have a
 196    corresponding variant in the `ty::sty` tag.
 197
 198 3. `./../librustc_llvm/lib.rs` defines the exported types
 199    `ValueRef`, `TypeRef`, `BasicBlockRef`, and several others.
 200    Each of these is an opaque pointer to an LLVM type,
 201    manipulated through the `lib::llvm` interface.
 202
 203 [libsyntax]: https://github.com/rust-lang/rust/tree/master/src/libsyntax/
 204 [trans]: https://github.com/rust-lang/rust/tree/master/src/librustc_trans/
 205 [llvm]: https://github.com/rust-lang/rust/tree/master/src/librustc_llvm/
 206 [back]: https://github.com/rust-lang/rust/tree/master/src/librustc_back/
 207 [rustc]: https://github.com/rust-lang/rust/tree/master/src/librustc/
 208 [driver]: https://github.com/rust-lang/rust/tree/master/src/librustc_driver
 209
 210 Glossary
 211 ========
 212
 213 The compiler uses a number of...idiosyncratic abbreviations and
 214 things. This glossary attempts to list them and give you a few
 215 pointers for understanding them better.
 216
 217 - AST -- the **abstract syntax tree** produced the `syntax` crate; reflects user syntax
 218   very closely.
 219 - cx -- we tend to use "cx" as an abbrevation for context. See also tcx, infcx, etc.
 220 - HIR -- the **High-level IR**, created by lowering and desugaring the AST. See `librustc/hir`.
 221 - `'gcx` -- the lifetime of the global arena (see `librustc/ty`).
 222 - generics -- the set of generic type parameters defined on a type or item
 223 - infcx -- the inference context (see `librustc/infer`)
 224 - MIR -- the **Mid-level IR** that is created after type-checking for use by borrowck and trans.
 225   Defined in the `src/librustc/mir/` module, but much of the code that manipulates it is
 226   found in `src/librustc_mir`.
 227 - obligation -- something that must be proven by the trait system.
 228 - sess -- the **compiler session**, which stores global data used throughout compilation
 229 - substs -- the **substitutions** for a given generic type or item
 230   (e.g., the `i32, u32` in `HashMap<i32, u32>`)
 231 - tcx -- the "typing context", main data structure of the compiler (see `librustc/ty`).
 232 - trans -- the code to **translate** MIR into LLVM IR.
 233 - trait reference -- a trait and values for its type parameters (see `librustc/ty`).
 234 - ty -- the internal representation of a **type** (see `librustc/ty`).