]>
Commit | Line | Data |
---|---|---|
a1dfa0c6 XL |
1 | # Queries: demand-driven compilation |
2 | ||
5e7ed085 FG |
3 | <!-- toc --> |
4 | ||
6a06907d | 5 | As described in [the high-level overview of the compiler][hl], the Rust compiler |
f2b60f7d | 6 | is still (as of <!-- date-check --> July 2021) transitioning from a |
5e7ed085 FG |
7 | traditional "pass-based" setup to a "demand-driven" system. The compiler query |
8 | system is the key to rustc's demand-driven organization. | |
9 | The idea is pretty simple. Instead of entirely independent passes | |
10 | (parsing, type-checking, etc.), a set of function-like *queries* | |
11 | compute information about the input source. For example, | |
12 | there is a query called `type_of` that, given the [`DefId`] of | |
6a06907d | 13 | some item, will compute the type of that item and return it to you. |
a1dfa0c6 | 14 | |
5e7ed085 | 15 | [`DefId`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_span/def_id/struct.DefId.html |
6a06907d | 16 | [hl]: ./compiler-src.md |
a1dfa0c6 | 17 | |
5e7ed085 | 18 | Query execution is *memoized*. The first time you invoke a |
a1dfa0c6 XL |
19 | query, it will go do the computation, but the next time, the result is |
20 | returned from a hashtable. Moreover, query execution fits nicely into | |
5e7ed085 FG |
21 | *incremental computation*; the idea is roughly that, when you invoke a |
22 | query, the result *may* be returned to you by loading stored data | |
23 | from disk.[^incr-comp-detail] | |
a1dfa0c6 | 24 | |
5e7ed085 FG |
25 | Eventually, we want the entire compiler |
26 | control-flow to be query driven. There will effectively be one | |
27 | top-level query (`compile`) that will run compilation on a crate; this | |
a1dfa0c6 XL |
28 | will in turn demand information about that crate, starting from the |
29 | *end*. For example: | |
30 | ||
5e7ed085 | 31 | - The `compile` query might demand to get a list of codegen-units |
a1dfa0c6 XL |
32 | (i.e. modules that need to be compiled by LLVM). |
33 | - But computing the list of codegen-units would invoke some subquery | |
34 | that returns the list of all modules defined in the Rust source. | |
35 | - That query in turn would invoke something asking for the HIR. | |
36 | - This keeps going further and further back until we wind up doing the | |
37 | actual parsing. | |
38 | ||
5e7ed085 | 39 | Although this vision is not fully realized, large sections of the |
923072b8 | 40 | compiler (for example, generating [MIR](./mir/index.md)) currently work exactly like this. |
532ac7d7 | 41 | |
5e7ed085 | 42 | [^incr-comp-detail]: The ["Incremental Compilation in Detail](queries/incremental-compilation-in-detail.md) chapter gives a more |
532ac7d7 XL |
43 | in-depth description of what queries are and how they work. |
44 | If you intend to write a query of your own, this is a good read. | |
45 | ||
5e7ed085 | 46 | ## Invoking queries |
94222f64 | 47 | |
5e7ed085 FG |
48 | Invoking a query is simple. The [`TyCtxt`] ("type context") struct offers a method |
49 | for each defined query. For example, to invoke the `type_of` | |
a1dfa0c6 XL |
50 | query, you would just do this: |
51 | ||
52 | ```rust,ignore | |
53 | let ty = tcx.type_of(some_def_id); | |
54 | ``` | |
55 | ||
5e7ed085 FG |
56 | [`TyCtxt`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.TyCtxt.html |
57 | ||
58 | ## How the compiler executes a query | |
a1dfa0c6 XL |
59 | |
60 | So you may be wondering what happens when you invoke a query | |
61 | method. The answer is that, for each query, the compiler maintains a | |
62 | cache – if your query has already been executed, then, the answer is | |
63 | simple: we clone the return value out of the cache and return it | |
64 | (therefore, you should try to ensure that the return types of queries | |
94222f64 | 65 | are cheaply cloneable; insert an `Rc` if necessary). |
a1dfa0c6 | 66 | |
5e7ed085 | 67 | ### Providers |
a1dfa0c6 XL |
68 | |
69 | If, however, the query is *not* in the cache, then the compiler will | |
70 | try to find a suitable **provider**. A provider is a function that has | |
71 | been defined and linked into the compiler somewhere that contains the | |
72 | code to compute the result of the query. | |
73 | ||
74 | **Providers are defined per-crate.** The compiler maintains, | |
75 | internally, a table of providers for every crate, at least | |
76 | conceptually. Right now, there are really two sets: the providers for | |
77 | queries about the **local crate** (that is, the one being compiled) | |
78 | and providers for queries about **external crates** (that is, | |
79 | dependencies of the local crate). Note that what determines the crate | |
80 | that a query is targeting is not the *kind* of query, but the *key*. | |
81 | For example, when you invoke `tcx.type_of(def_id)`, that could be a | |
82 | local query or an external query, depending on what crate the `def_id` | |
74b04a01 XL |
83 | is referring to (see the [`self::keys::Key`][Key] trait for more |
84 | information on how that works). | |
a1dfa0c6 XL |
85 | |
86 | Providers always have the same signature: | |
87 | ||
88 | ```rust,ignore | |
dc9dc135 XL |
89 | fn provider<'tcx>( |
90 | tcx: TyCtxt<'tcx>, | |
91 | key: QUERY_KEY, | |
92 | ) -> QUERY_RESULT { | |
a1dfa0c6 XL |
93 | ... |
94 | } | |
95 | ``` | |
96 | ||
dc9dc135 | 97 | Providers take two arguments: the `tcx` and the query key. |
a1dfa0c6 XL |
98 | They return the result of the query. |
99 | ||
5e7ed085 | 100 | ### How providers are setup |
a1dfa0c6 XL |
101 | |
102 | When the tcx is created, it is given the providers by its creator using | |
74b04a01 XL |
103 | the [`Providers`][providers_struct] struct. This struct is generated by |
104 | the macros here, but it is basically a big list of function pointers: | |
105 | ||
ba9703b0 | 106 | [providers_struct]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/query/struct.Providers.html |
a1dfa0c6 XL |
107 | |
108 | ```rust,ignore | |
109 | struct Providers { | |
dc9dc135 | 110 | type_of: for<'tcx> fn(TyCtxt<'tcx>, DefId) -> Ty<'tcx>, |
a1dfa0c6 XL |
111 | ... |
112 | } | |
113 | ``` | |
114 | ||
115 | At present, we have one copy of the struct for local crates, and one | |
116 | for external crates, though the plan is that we may eventually have | |
117 | one per crate. | |
118 | ||
74b04a01 | 119 | These `Providers` structs are ultimately created and populated by |
6a06907d | 120 | `rustc_driver`, but it does this by distributing the work |
a1dfa0c6 | 121 | throughout the other `rustc_*` crates. This is done by invoking |
74b04a01 XL |
122 | various [`provide`][provide_fn] functions. These functions tend to look |
123 | something like this: | |
124 | ||
ba9703b0 | 125 | [provide_fn]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/hir/fn.provide.html |
a1dfa0c6 XL |
126 | |
127 | ```rust,ignore | |
128 | pub fn provide(providers: &mut Providers) { | |
129 | *providers = Providers { | |
130 | type_of, | |
131 | ..*providers | |
132 | }; | |
133 | } | |
134 | ``` | |
135 | ||
136 | That is, they take an `&mut Providers` and mutate it in place. Usually | |
137 | we use the formulation above just because it looks nice, but you could | |
138 | as well do `providers.type_of = type_of`, which would be equivalent. | |
139 | (Here, `type_of` would be a top-level function, defined as we saw | |
140 | before.) So, if we want to add a provider for some other query, | |
141 | let's call it `fubar`, into the crate above, we might modify the `provide()` | |
142 | function like so: | |
143 | ||
144 | ```rust,ignore | |
145 | pub fn provide(providers: &mut Providers) { | |
146 | *providers = Providers { | |
147 | type_of, | |
148 | fubar, | |
149 | ..*providers | |
150 | }; | |
151 | } | |
152 | ||
dc9dc135 | 153 | fn fubar<'tcx>(tcx: TyCtxt<'tcx>, key: DefId) -> Fubar<'tcx> { ... } |
a1dfa0c6 XL |
154 | ``` |
155 | ||
156 | N.B. Most of the `rustc_*` crates only provide **local | |
157 | providers**. Almost all **extern providers** wind up going through the | |
74b04a01 XL |
158 | [`rustc_metadata` crate][rustc_metadata], which loads the information |
159 | from the crate metadata. But in some cases there are crates that | |
160 | provide queries for *both* local and external crates, in which case | |
6a06907d | 161 | they define both a `provide` and a `provide_extern` function, through |
17df50a5 | 162 | [`wasm_import_module_map`][wasm_import_module_map], that `rustc_driver` can invoke. |
a1dfa0c6 | 163 | |
6a06907d | 164 | [rustc_metadata]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_metadata/index.html |
17df50a5 | 165 | [wasm_import_module_map]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_codegen_ssa/back/symbol_export/fn.wasm_import_module_map.html |
a1dfa0c6 | 166 | |
5e7ed085 | 167 | ## Adding a new query |
a1dfa0c6 | 168 | |
5e7ed085 FG |
169 | How do you add a new query? |
170 | Defining a query takes place in two steps: | |
a1dfa0c6 | 171 | |
5e7ed085 FG |
172 | 1. Specify the query name and its arguments. |
173 | 2. Supply query providers where needed. | |
a1dfa0c6 XL |
174 | |
175 | To specify the query name and arguments, you simply add an entry to | |
176 | the big macro invocation in | |
6a06907d | 177 | [`compiler/rustc_middle/src/query/mod.rs`][query-mod], which looks something like: |
a1dfa0c6 | 178 | |
ba9703b0 | 179 | [query-mod]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/query/index.html |
a1dfa0c6 XL |
180 | |
181 | ```rust,ignore | |
48663c56 XL |
182 | rustc_queries! { |
183 | Other { | |
184 | /// Records the type of every item. | |
185 | query type_of(key: DefId) -> Ty<'tcx> { | |
186 | cache { key.is_local() } | |
187 | } | |
188 | } | |
a1dfa0c6 XL |
189 | |
190 | ... | |
191 | } | |
192 | ``` | |
193 | ||
48663c56 | 194 | Queries are grouped into categories (`Other`, `Codegen`, `TypeChecking`, etc.). |
5e7ed085 FG |
195 | Each group contains one or more queries. |
196 | ||
197 | A query definition has the following form: | |
a1dfa0c6 XL |
198 | |
199 | ```rust,ignore | |
48663c56 | 200 | query type_of(key: DefId) -> Ty<'tcx> { ... } |
5e7ed085 | 201 | ^^^^^ ^^^^^^^ ^^^^^ ^^^^^^^^ ^^^ |
48663c56 XL |
202 | | | | | | |
203 | | | | | query modifiers | |
5e7ed085 | 204 | | | | result type |
48663c56 | 205 | | | query key type |
a1dfa0c6 | 206 | | name of query |
48663c56 | 207 | query keyword |
a1dfa0c6 XL |
208 | ``` |
209 | ||
5e7ed085 | 210 | Let's go over these elements one by one: |
a1dfa0c6 | 211 | |
48663c56 | 212 | - **Query keyword:** indicates a start of a query definition. |
a1dfa0c6 XL |
213 | - **Name of query:** the name of the query method |
214 | (`tcx.type_of(..)`). Also used as the name of a struct | |
215 | (`ty::queries::type_of`) that will be generated to represent | |
216 | this query. | |
a1dfa0c6 | 217 | - **Query key type:** the type of the argument to this query. |
74b04a01 | 218 | This type must implement the [`ty::query::keys::Key`][Key] trait, which |
a1dfa0c6 XL |
219 | defines (for example) how to map it to a crate, and so forth. |
220 | - **Result type of query:** the type produced by this query. This type | |
221 | should (a) not use `RefCell` or other interior mutability and (b) be | |
222 | cheaply cloneable. Interning or using `Rc` or `Arc` is recommended for | |
5e7ed085 | 223 | non-trivial data types.[^steal] |
48663c56 | 224 | - **Query modifiers:** various flags and options that customize how the |
6a06907d | 225 | query is processed (mostly with respect to [incremental compilation][incrcomp]). |
a1dfa0c6 | 226 | |
6a06907d XL |
227 | [Key]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_query_impl/keys/trait.Key.html |
228 | [incrcomp]: queries/incremental-compilation-in-detail.html#query-modifiers | |
74b04a01 | 229 | |
a1dfa0c6 XL |
230 | So, to add a query: |
231 | ||
48663c56 | 232 | - Add an entry to `rustc_queries!` using the format above. |
a1dfa0c6 XL |
233 | - Link the provider by modifying the appropriate `provide` method; |
234 | or add a new one if needed and ensure that `rustc_driver` is invoking it. | |
235 | ||
5e7ed085 FG |
236 | [^steal]: The one exception to those rules is the `ty::steal::Steal` type, |
237 | which is used to cheaply modify MIR in place. See the definition | |
238 | of `Steal` for more details. New uses of `Steal` should **not** be | |
239 | added without alerting `@rust-lang/compiler`. | |
240 | ||
241 | ### Query structs and descriptions | |
a1dfa0c6 | 242 | |
5e7ed085 FG |
243 | For each query, the `rustc_queries` macro will generate a "query struct" |
244 | named after the query. This struct is a kind of placeholder | |
245 | describing the query. Each query struct implements the | |
74b04a01 | 246 | [`self::config::QueryConfig`][QueryConfig] trait, which has associated types for the |
a1dfa0c6 XL |
247 | key/value of that particular query. Basically the code generated looks something |
248 | like this: | |
249 | ||
250 | ```rust,ignore | |
251 | // Dummy struct representing a particular kind of query: | |
48663c56 | 252 | pub struct type_of<'tcx> { data: PhantomData<&'tcx ()> } |
a1dfa0c6 XL |
253 | |
254 | impl<'tcx> QueryConfig for type_of<'tcx> { | |
255 | type Key = DefId; | |
256 | type Value = Ty<'tcx>; | |
48663c56 XL |
257 | |
258 | const NAME: QueryName = QueryName::type_of; | |
259 | const CATEGORY: ProfileCategory = ProfileCategory::Other; | |
a1dfa0c6 XL |
260 | } |
261 | ``` | |
262 | ||
263 | There is an additional trait that you may wish to implement called | |
74b04a01 XL |
264 | [`self::config::QueryDescription`][QueryDescription]. This trait is |
265 | used during cycle errors to give a "human readable" name for the query, | |
266 | so that we can summarize what was happening when the cycle occurred. | |
267 | Implementing this trait is optional if the query key is `DefId`, but | |
268 | if you *don't* implement it, you get a pretty generic error ("processing `foo`..."). | |
a1dfa0c6 XL |
269 | You can put new impls into the `config` module. They look something like this: |
270 | ||
6a06907d | 271 | [QueryConfig]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_query_system/query/config/trait.QueryConfig.html |
ba9703b0 | 272 | [QueryDescription]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_query_system/query/config/trait.QueryDescription.html |
74b04a01 | 273 | |
a1dfa0c6 XL |
274 | ```rust,ignore |
275 | impl<'tcx> QueryDescription for queries::type_of<'tcx> { | |
276 | fn describe(tcx: TyCtxt, key: DefId) -> String { | |
48663c56 XL |
277 | format!("computing the type of `{}`", tcx.def_path_str(key)) |
278 | } | |
279 | } | |
280 | ``` | |
281 | ||
282 | Another option is to add `desc` modifier: | |
283 | ||
284 | ```rust,ignore | |
285 | rustc_queries! { | |
286 | Other { | |
287 | /// Records the type of every item. | |
288 | query type_of(key: DefId) -> Ty<'tcx> { | |
289 | desc { |tcx| "computing the type of `{}`", tcx.def_path_str(key) } | |
290 | } | |
a1dfa0c6 XL |
291 | } |
292 | } | |
293 | ``` | |
294 | ||
48663c56 XL |
295 | `rustc_queries` macro will generate an appropriate `impl` automatically. |
296 | ||
5e7ed085 | 297 | ## External links |
94222f64 XL |
298 | |
299 | Related design ideas, and tracking issues: | |
300 | ||
301 | - Design document: [On-demand Rustc incremental design doc] | |
302 | - Tracking Issue: ["Red/Green" dependency tracking in compiler] | |
303 | ||
304 | More discussion and issues: | |
305 | ||
306 | - [GitHub issue #42633] | |
307 | - [Incremental Compilation Beta] | |
308 | - [Incremental Compilation Announcement] | |
309 | ||
310 | [On-demand Rustc incremental design doc]: https://github.com/nikomatsakis/rustc-on-demand-incremental-design-doc/blob/master/0000-rustc-on-demand-and-incremental.md | |
311 | ["Red/Green" dependency tracking in compiler]: https://github.com/rust-lang/rust/issues/42293 | |
312 | [GitHub issue #42633]: https://github.com/rust-lang/rust/issues/42633 | |
313 | [Incremental Compilation Beta]: https://internals.rust-lang.org/t/incremental-compilation-beta/4721 | |
314 | [Incremental Compilation Announcement]: https://blog.rust-lang.org/2016/09/08/incremental.html | |
5e7ed085 | 315 |