]>
Commit | Line | Data |
---|---|---|
a1dfa0c6 XL |
1 | # High-level overview of the compiler source |
2 | ||
3 | ## Crate structure | |
4 | ||
5 | The main Rust repository consists of a `src` directory, under which | |
6 | there live many crates. These crates contain the sources for the | |
7 | standard library and the compiler. This document, of course, focuses | |
8 | on the latter. | |
9 | ||
10 | Rustc consists of a number of crates, including `syntax`, | |
11 | `rustc`, `rustc_back`, `rustc_codegen`, `rustc_driver`, and | |
12 | many more. The source for each crate can be found in a directory | |
13 | like `src/libXXX`, where `XXX` is the crate name. | |
14 | ||
15 | (N.B. The names and divisions of these crates are not set in | |
16 | stone and may change over time. For the time being, we tend towards a | |
17 | finer-grained division to help with compilation time, though as incremental | |
18 | compilation improves, that may change.) | |
19 | ||
20 | The dependency structure of these crates is roughly a diamond: | |
21 | ||
22 | ```text | |
23 | rustc_driver | |
24 | / | \ | |
25 | / | \ | |
26 | / | \ | |
27 | / v \ | |
28 | rustc_codegen rustc_borrowck ... rustc_metadata | |
29 | \ | / | |
30 | \ | / | |
31 | \ | / | |
32 | \ v / | |
33 | rustc | |
34 | | | |
35 | v | |
36 | syntax | |
37 | / \ | |
38 | / \ | |
39 | syntax_pos syntax_ext | |
40 | ``` | |
41 | ||
42 | The `rustc_driver` crate, at the top of this lattice, is effectively | |
43 | the "main" function for the rust compiler. It doesn't have much "real | |
44 | code", but instead ties together all of the code defined in the other | |
45 | crates and defines the overall flow of execution. (As we transition | |
46 | more and more to the [query model], however, the | |
47 | "flow" of compilation is becoming less centrally defined.) | |
48 | ||
49 | At the other extreme, the `rustc` crate defines the common and | |
50 | pervasive data structures that all the rest of the compiler uses | |
51 | (e.g. how to represent types, traits, and the program itself). It | |
52 | also contains some amount of the compiler itself, although that is | |
53 | relatively limited. | |
54 | ||
55 | Finally, all the crates in the bulge in the middle define the bulk of | |
56 | the compiler – they all depend on `rustc`, so that they can make use | |
57 | of the various types defined there, and they export public routines | |
58 | that `rustc_driver` will invoke as needed (more and more, what these | |
59 | crates export are "query definitions", but those are covered later | |
60 | on). | |
61 | ||
62 | Below `rustc` lie various crates that make up the parser and error | |
63 | reporting mechanism. For historical reasons, these crates do not have | |
64 | the `rustc_` prefix, but they are really just as much an internal part | |
65 | of the compiler and not intended to be stable (though they do wind up | |
66 | getting used by some crates in the wild; a practice we hope to | |
67 | gradually phase out). | |
68 | ||
69 | Each crate has a `README.md` file that describes, at a high-level, | |
70 | what it contains, and tries to give some kind of explanation (some | |
71 | better than others). | |
72 | ||
73 | ## The main stages of compilation | |
74 | ||
75 | The Rust compiler is in a bit of transition right now. It used to be a | |
76 | purely "pass-based" compiler, where we ran a number of passes over the | |
77 | entire program, and each did a particular check of transformation. We | |
78 | are gradually replacing this pass-based code with an alternative setup | |
79 | based on on-demand **queries**. In the query-model, we work backwards, | |
80 | executing a *query* that expresses our ultimate goal (e.g. "compile | |
81 | this crate"). This query in turn may make other queries (e.g. "get me | |
82 | a list of all modules in the crate"). Those queries make other queries | |
83 | that ultimately bottom out in the base operations, like parsing the | |
84 | input, running the type-checker, and so forth. This on-demand model | |
85 | permits us to do exciting things like only do the minimal amount of | |
86 | work needed to type-check a single function. It also helps with | |
87 | incremental compilation. (For details on defining queries, check out | |
88 | the [query model].) | |
89 | ||
90 | Regardless of the general setup, the basic operations that the | |
91 | compiler must perform are the same. The only thing that changes is | |
92 | whether these operations are invoked front-to-back, or on demand. In | |
93 | order to compile a Rust crate, these are the general steps that we | |
94 | take: | |
95 | ||
96 | 1. **Parsing input** | |
97 | - this processes the `.rs` files and produces the AST | |
98 | ("abstract syntax tree") | |
99 | - the AST is defined in `src/libsyntax/ast.rs`. It is intended to match the lexical | |
100 | syntax of the Rust language quite closely. | |
101 | 2. **Name resolution, macro expansion, and configuration** | |
102 | - once parsing is complete, we process the AST recursively, resolving | |
103 | paths and expanding macros. This same process also processes `#[cfg]` | |
104 | nodes, and hence may strip things out of the AST as well. | |
105 | 3. **Lowering to HIR** | |
106 | - Once name resolution completes, we convert the AST into the HIR, | |
107 | or "[high-level intermediate representation]". The HIR is defined in | |
108 | `src/librustc/hir/`; that module also includes the [lowering] code. | |
109 | - The HIR is a lightly desugared variant of the AST. It is more processed | |
110 | than the AST and more suitable for the analyses that follow. | |
111 | It is **not** required to match the syntax of the Rust language. | |
112 | - As a simple example, in the **AST**, we preserve the parentheses | |
113 | that the user wrote, so `((1 + 2) + 3)` and `1 + 2 + 3` parse | |
114 | into distinct trees, even though they are equivalent. In the | |
115 | HIR, however, parentheses nodes are removed, and those two | |
116 | expressions are represented in the same way. | |
117 | 3. **Type-checking and subsequent analyses** | |
118 | - An important step in processing the HIR is to perform type | |
119 | checking. This process assigns types to every HIR expression, | |
120 | for example, and also is responsible for resolving some | |
121 | "type-dependent" paths, such as field accesses (`x.f` – we | |
122 | can't know what field `f` is being accessed until we know the | |
123 | type of `x`) and associated type references (`T::Item` – we | |
124 | can't know what type `Item` is until we know what `T` is). | |
125 | - Type checking creates "side-tables" (`TypeckTables`) that include | |
126 | the types of expressions, the way to resolve methods, and so forth. | |
127 | - After type-checking, we can do other analyses, such as privacy checking. | |
128 | 4. **Lowering to MIR and post-processing** | |
129 | - Once type-checking is done, we can lower the HIR into MIR ("middle IR"), | |
130 | which is a **very** desugared version of Rust, well suited to borrowck | |
131 | but also to certain high-level optimizations. | |
132 | 5. **Translation to LLVM and LLVM optimizations** | |
133 | - From MIR, we can produce LLVM IR. | |
134 | - LLVM then runs its various optimizations, which produces a number of | |
135 | `.o` files (one for each "codegen unit"). | |
136 | 6. **Linking** | |
137 | - Finally, those `.o` files are linked together. | |
138 | ||
139 | ||
140 | [query model]: query.html | |
141 | [high-level intermediate representation]: hir.html | |
142 | [lowering]: lowering.html |