]>
Commit | Line | Data |
---|---|---|
7453a54e SL |
1 | // Copyright 2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | //! Translation Item Collection | |
12 | //! =========================== | |
13 | //! | |
14 | //! This module is responsible for discovering all items that will contribute to | |
15 | //! to code generation of the crate. The important part here is that it not only | |
16 | //! needs to find syntax-level items (functions, structs, etc) but also all | |
17 | //! their monomorphized instantiations. Every non-generic, non-const function | |
18 | //! maps to one LLVM artifact. Every generic function can produce | |
19 | //! from zero to N artifacts, depending on the sets of type arguments it | |
20 | //! is instantiated with. | |
21 | //! This also applies to generic items from other crates: A generic definition | |
22 | //! in crate X might produce monomorphizations that are compiled into crate Y. | |
23 | //! We also have to collect these here. | |
24 | //! | |
25 | //! The following kinds of "translation items" are handled here: | |
26 | //! | |
27 | //! - Functions | |
28 | //! - Methods | |
29 | //! - Closures | |
30 | //! - Statics | |
31 | //! - Drop glue | |
32 | //! | |
33 | //! The following things also result in LLVM artifacts, but are not collected | |
34 | //! here, since we instantiate them locally on demand when needed in a given | |
35 | //! codegen unit: | |
36 | //! | |
37 | //! - Constants | |
38 | //! - Vtables | |
39 | //! - Object Shims | |
40 | //! | |
41 | //! | |
42 | //! General Algorithm | |
43 | //! ----------------- | |
44 | //! Let's define some terms first: | |
45 | //! | |
46 | //! - A "translation item" is something that results in a function or global in | |
47 | //! the LLVM IR of a codegen unit. Translation items do not stand on their | |
48 | //! own, they can reference other translation items. For example, if function | |
49 | //! `foo()` calls function `bar()` then the translation item for `foo()` | |
50 | //! references the translation item for function `bar()`. In general, the | |
51 | //! definition for translation item A referencing a translation item B is that | |
52 | //! the LLVM artifact produced for A references the LLVM artifact produced | |
53 | //! for B. | |
54 | //! | |
32a655c1 | 55 | //! - Translation items and the references between them form a directed graph, |
7453a54e SL |
56 | //! where the translation items are the nodes and references form the edges. |
57 | //! Let's call this graph the "translation item graph". | |
58 | //! | |
59 | //! - The translation item graph for a program contains all translation items | |
60 | //! that are needed in order to produce the complete LLVM IR of the program. | |
61 | //! | |
62 | //! The purpose of the algorithm implemented in this module is to build the | |
63 | //! translation item graph for the current crate. It runs in two phases: | |
64 | //! | |
65 | //! 1. Discover the roots of the graph by traversing the HIR of the crate. | |
66 | //! 2. Starting from the roots, find neighboring nodes by inspecting the MIR | |
67 | //! representation of the item corresponding to a given node, until no more | |
68 | //! new nodes are found. | |
69 | //! | |
70 | //! ### Discovering roots | |
71 | //! | |
72 | //! The roots of the translation item graph correspond to the non-generic | |
73 | //! syntactic items in the source code. We find them by walking the HIR of the | |
74 | //! crate, and whenever we hit upon a function, method, or static item, we | |
75 | //! create a translation item consisting of the items DefId and, since we only | |
76 | //! consider non-generic items, an empty type-substitution set. | |
77 | //! | |
78 | //! ### Finding neighbor nodes | |
79 | //! Given a translation item node, we can discover neighbors by inspecting its | |
80 | //! MIR. We walk the MIR and any time we hit upon something that signifies a | |
81 | //! reference to another translation item, we have found a neighbor. Since the | |
82 | //! translation item we are currently at is always monomorphic, we also know the | |
83 | //! concrete type arguments of its neighbors, and so all neighbors again will be | |
84 | //! monomorphic. The specific forms a reference to a neighboring node can take | |
85 | //! in MIR are quite diverse. Here is an overview: | |
86 | //! | |
87 | //! #### Calling Functions/Methods | |
88 | //! The most obvious form of one translation item referencing another is a | |
89 | //! function or method call (represented by a CALL terminator in MIR). But | |
90 | //! calls are not the only thing that might introduce a reference between two | |
91 | //! function translation items, and as we will see below, they are just a | |
92 | //! specialized of the form described next, and consequently will don't get any | |
93 | //! special treatment in the algorithm. | |
94 | //! | |
95 | //! #### Taking a reference to a function or method | |
96 | //! A function does not need to actually be called in order to be a neighbor of | |
97 | //! another function. It suffices to just take a reference in order to introduce | |
98 | //! an edge. Consider the following example: | |
99 | //! | |
100 | //! ```rust | |
101 | //! fn print_val<T: Display>(x: T) { | |
102 | //! println!("{}", x); | |
103 | //! } | |
104 | //! | |
105 | //! fn call_fn(f: &Fn(i32), x: i32) { | |
106 | //! f(x); | |
107 | //! } | |
108 | //! | |
109 | //! fn main() { | |
110 | //! let print_i32 = print_val::<i32>; | |
111 | //! call_fn(&print_i32, 0); | |
112 | //! } | |
113 | //! ``` | |
114 | //! The MIR of none of these functions will contain an explicit call to | |
115 | //! `print_val::<i32>`. Nonetheless, in order to translate this program, we need | |
116 | //! an instance of this function. Thus, whenever we encounter a function or | |
117 | //! method in operand position, we treat it as a neighbor of the current | |
118 | //! translation item. Calls are just a special case of that. | |
119 | //! | |
120 | //! #### Closures | |
121 | //! In a way, closures are a simple case. Since every closure object needs to be | |
122 | //! constructed somewhere, we can reliably discover them by observing | |
123 | //! `RValue::Aggregate` expressions with `AggregateKind::Closure`. This is also | |
124 | //! true for closures inlined from other crates. | |
125 | //! | |
126 | //! #### Drop glue | |
127 | //! Drop glue translation items are introduced by MIR drop-statements. The | |
128 | //! generated translation item will again have drop-glue item neighbors if the | |
129 | //! type to be dropped contains nested values that also need to be dropped. It | |
130 | //! might also have a function item neighbor for the explicit `Drop::drop` | |
131 | //! implementation of its type. | |
132 | //! | |
133 | //! #### Unsizing Casts | |
134 | //! A subtle way of introducing neighbor edges is by casting to a trait object. | |
135 | //! Since the resulting fat-pointer contains a reference to a vtable, we need to | |
136 | //! instantiate all object-save methods of the trait, as we need to store | |
137 | //! pointers to these functions even if they never get called anywhere. This can | |
138 | //! be seen as a special case of taking a function reference. | |
139 | //! | |
140 | //! #### Boxes | |
141 | //! Since `Box` expression have special compiler support, no explicit calls to | |
142 | //! `exchange_malloc()` and `exchange_free()` may show up in MIR, even if the | |
143 | //! compiler will generate them. We have to observe `Rvalue::Box` expressions | |
144 | //! and Box-typed drop-statements for that purpose. | |
145 | //! | |
146 | //! | |
147 | //! Interaction with Cross-Crate Inlining | |
148 | //! ------------------------------------- | |
149 | //! The binary of a crate will not only contain machine code for the items | |
150 | //! defined in the source code of that crate. It will also contain monomorphic | |
151 | //! instantiations of any extern generic functions and of functions marked with | |
152 | //! #[inline]. | |
153 | //! The collection algorithm handles this more or less transparently. If it is | |
154 | //! about to create a translation item for something with an external `DefId`, | |
155 | //! it will take a look if the MIR for that item is available, and if so just | |
9e0c209e | 156 | //! proceed normally. If the MIR is not available, it assumes that the item is |
7453a54e SL |
157 | //! just linked to and no node is created; which is exactly what we want, since |
158 | //! no machine code should be generated in the current crate for such an item. | |
159 | //! | |
160 | //! Eager and Lazy Collection Mode | |
161 | //! ------------------------------ | |
162 | //! Translation item collection can be performed in one of two modes: | |
163 | //! | |
164 | //! - Lazy mode means that items will only be instantiated when actually | |
165 | //! referenced. The goal is to produce the least amount of machine code | |
166 | //! possible. | |
167 | //! | |
168 | //! - Eager mode is meant to be used in conjunction with incremental compilation | |
169 | //! where a stable set of translation items is more important than a minimal | |
170 | //! one. Thus, eager mode will instantiate drop-glue for every drop-able type | |
171 | //! in the crate, even of no drop call for that type exists (yet). It will | |
172 | //! also instantiate default implementations of trait methods, something that | |
173 | //! otherwise is only done on demand. | |
174 | //! | |
175 | //! | |
176 | //! Open Issues | |
177 | //! ----------- | |
178 | //! Some things are not yet fully implemented in the current version of this | |
179 | //! module. | |
180 | //! | |
181 | //! ### Initializers of Constants and Statics | |
182 | //! Since no MIR is constructed yet for initializer expressions of constants and | |
183 | //! statics we cannot inspect these properly. | |
184 | //! | |
185 | //! ### Const Fns | |
186 | //! Ideally, no translation item should be generated for const fns unless there | |
187 | //! is a call to them that cannot be evaluated at compile time. At the moment | |
188 | //! this is not implemented however: a translation item will be produced | |
189 | //! regardless of whether it is actually needed or not. | |
190 | ||
54a0048b | 191 | use rustc::hir; |
476ff2be | 192 | use rustc::hir::itemlikevisit::ItemLikeVisitor; |
7453a54e | 193 | |
54a0048b SL |
194 | use rustc::hir::map as hir_map; |
195 | use rustc::hir::def_id::DefId; | |
32a655c1 | 196 | use rustc::middle::lang_items::{BoxFreeFnLangItem, ExchangeMallocFnLangItem}; |
54a0048b | 197 | use rustc::traits; |
32a655c1 | 198 | use rustc::ty::subst::{Kind, Substs, Subst}; |
a7813a04 | 199 | use rustc::ty::{self, TypeFoldable, TyCtxt}; |
54a0048b | 200 | use rustc::ty::adjustment::CustomCoerceUnsized; |
c30ab7b3 | 201 | use rustc::mir::{self, Location}; |
7453a54e SL |
202 | use rustc::mir::visit as mir_visit; |
203 | use rustc::mir::visit::Visitor as MirVisitor; | |
204 | ||
a7813a04 | 205 | use syntax::abi::Abi; |
3157f602 | 206 | use syntax_pos::DUMMY_SP; |
54a0048b | 207 | use base::custom_coerce_unsize_info; |
32a655c1 | 208 | use callee::needs_fn_once_adapter_shim; |
a7813a04 | 209 | use context::SharedCrateContext; |
8bb4bdeb | 210 | use common::{def_ty, fulfill_obligation}; |
a7813a04 | 211 | use glue::{self, DropGlueKind}; |
54a0048b | 212 | use monomorphize::{self, Instance}; |
476ff2be | 213 | use util::nodemap::{FxHashSet, FxHashMap, DefIdMap}; |
7453a54e | 214 | |
32a655c1 SL |
215 | use trans_item::{TransItem, DefPathBasedNames, InstantiationMode}; |
216 | ||
217 | use std::iter; | |
7453a54e SL |
218 | |
219 | #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)] | |
220 | pub enum TransItemCollectionMode { | |
221 | Eager, | |
222 | Lazy | |
223 | } | |
224 | ||
a7813a04 XL |
225 | /// Maps every translation item to all translation items it references in its |
226 | /// body. | |
227 | pub struct InliningMap<'tcx> { | |
228 | // Maps a source translation item to a range of target translation items | |
229 | // that are potentially inlined by LLVM into the source. | |
230 | // The two numbers in the tuple are the start (inclusive) and | |
231 | // end index (exclusive) within the `targets` vecs. | |
476ff2be | 232 | index: FxHashMap<TransItem<'tcx>, (usize, usize)>, |
a7813a04 | 233 | targets: Vec<TransItem<'tcx>>, |
7453a54e SL |
234 | } |
235 | ||
a7813a04 XL |
236 | impl<'tcx> InliningMap<'tcx> { |
237 | ||
238 | fn new() -> InliningMap<'tcx> { | |
239 | InliningMap { | |
476ff2be | 240 | index: FxHashMap(), |
a7813a04 XL |
241 | targets: Vec::new(), |
242 | } | |
243 | } | |
244 | ||
245 | fn record_inlining_canditates<I>(&mut self, | |
246 | source: TransItem<'tcx>, | |
247 | targets: I) | |
248 | where I: Iterator<Item=TransItem<'tcx>> | |
249 | { | |
250 | assert!(!self.index.contains_key(&source)); | |
251 | ||
252 | let start_index = self.targets.len(); | |
253 | self.targets.extend(targets); | |
254 | let end_index = self.targets.len(); | |
255 | self.index.insert(source, (start_index, end_index)); | |
256 | } | |
257 | ||
258 | // Internally iterate over all items referenced by `source` which will be | |
259 | // made available for inlining. | |
260 | pub fn with_inlining_candidates<F>(&self, source: TransItem<'tcx>, mut f: F) | |
261 | where F: FnMut(TransItem<'tcx>) { | |
262 | if let Some(&(start_index, end_index)) = self.index.get(&source) | |
263 | { | |
264 | for candidate in &self.targets[start_index .. end_index] { | |
265 | f(*candidate) | |
7453a54e | 266 | } |
a7813a04 | 267 | } |
7453a54e SL |
268 | } |
269 | } | |
270 | ||
a7813a04 | 271 | pub fn collect_crate_translation_items<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e | 272 | mode: TransItemCollectionMode) |
476ff2be | 273 | -> (FxHashSet<TransItem<'tcx>>, |
a7813a04 | 274 | InliningMap<'tcx>) { |
7453a54e SL |
275 | // We are not tracking dependencies of this pass as it has to be re-executed |
276 | // every time no matter what. | |
a7813a04 XL |
277 | scx.tcx().dep_graph.with_ignore(|| { |
278 | let roots = collect_roots(scx, mode); | |
7453a54e SL |
279 | |
280 | debug!("Building translation item graph, beginning at roots"); | |
476ff2be | 281 | let mut visited = FxHashSet(); |
7453a54e | 282 | let mut recursion_depths = DefIdMap(); |
a7813a04 | 283 | let mut inlining_map = InliningMap::new(); |
7453a54e SL |
284 | |
285 | for root in roots { | |
a7813a04 XL |
286 | collect_items_rec(scx, |
287 | root, | |
288 | &mut visited, | |
289 | &mut recursion_depths, | |
290 | &mut inlining_map); | |
7453a54e SL |
291 | } |
292 | ||
a7813a04 | 293 | (visited, inlining_map) |
7453a54e SL |
294 | }) |
295 | } | |
296 | ||
297 | // Find all non-generic items by walking the HIR. These items serve as roots to | |
298 | // start monomorphizing from. | |
a7813a04 | 299 | fn collect_roots<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
300 | mode: TransItemCollectionMode) |
301 | -> Vec<TransItem<'tcx>> { | |
302 | debug!("Collecting roots"); | |
303 | let mut roots = Vec::new(); | |
304 | ||
305 | { | |
306 | let mut visitor = RootCollector { | |
a7813a04 | 307 | scx: scx, |
7453a54e SL |
308 | mode: mode, |
309 | output: &mut roots, | |
7453a54e SL |
310 | }; |
311 | ||
32a655c1 | 312 | scx.tcx().hir.krate().visit_all_item_likes(&mut visitor); |
7453a54e SL |
313 | } |
314 | ||
315 | roots | |
316 | } | |
317 | ||
7453a54e | 318 | // Collect all monomorphized translation items reachable from `starting_point` |
a7813a04 | 319 | fn collect_items_rec<'a, 'tcx: 'a>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e | 320 | starting_point: TransItem<'tcx>, |
476ff2be | 321 | visited: &mut FxHashSet<TransItem<'tcx>>, |
a7813a04 XL |
322 | recursion_depths: &mut DefIdMap<usize>, |
323 | inlining_map: &mut InliningMap<'tcx>) { | |
7453a54e SL |
324 | if !visited.insert(starting_point.clone()) { |
325 | // We've been here already, no need to search again. | |
326 | return; | |
327 | } | |
a7813a04 | 328 | debug!("BEGIN collect_items_rec({})", starting_point.to_string(scx.tcx())); |
7453a54e SL |
329 | |
330 | let mut neighbors = Vec::new(); | |
331 | let recursion_depth_reset; | |
332 | ||
333 | match starting_point { | |
334 | TransItem::DropGlue(t) => { | |
a7813a04 | 335 | find_drop_glue_neighbors(scx, t, &mut neighbors); |
7453a54e SL |
336 | recursion_depth_reset = None; |
337 | } | |
a7813a04 | 338 | TransItem::Static(node_id) => { |
32a655c1 SL |
339 | let def_id = scx.tcx().hir.local_def_id(node_id); |
340 | ||
341 | // Sanity check whether this ended up being collected accidentally | |
342 | debug_assert!(should_trans_locally(scx.tcx(), def_id)); | |
343 | ||
8bb4bdeb | 344 | let ty = def_ty(scx, def_id, Substs::empty()); |
32a655c1 | 345 | let ty = glue::get_drop_glue_type(scx, ty); |
a7813a04 XL |
346 | neighbors.push(TransItem::DropGlue(DropGlueKind::Ty(ty))); |
347 | ||
7453a54e | 348 | recursion_depth_reset = None; |
a7813a04 | 349 | |
32a655c1 | 350 | collect_neighbours(scx, Instance::mono(scx, def_id), &mut neighbors); |
7453a54e | 351 | } |
54a0048b | 352 | TransItem::Fn(instance) => { |
32a655c1 SL |
353 | // Sanity check whether this ended up being collected accidentally |
354 | debug_assert!(should_trans_locally(scx.tcx(), instance.def)); | |
355 | ||
7453a54e | 356 | // Keep track of the monomorphization recursion depth |
a7813a04 | 357 | recursion_depth_reset = Some(check_recursion_limit(scx.tcx(), |
54a0048b | 358 | instance, |
7453a54e | 359 | recursion_depths)); |
476ff2be | 360 | check_type_length_limit(scx.tcx(), instance); |
7453a54e | 361 | |
32a655c1 | 362 | collect_neighbours(scx, instance, &mut neighbors); |
7453a54e SL |
363 | } |
364 | } | |
365 | ||
a7813a04 XL |
366 | record_inlining_canditates(scx.tcx(), starting_point, &neighbors[..], inlining_map); |
367 | ||
7453a54e | 368 | for neighbour in neighbors { |
a7813a04 | 369 | collect_items_rec(scx, neighbour, visited, recursion_depths, inlining_map); |
7453a54e SL |
370 | } |
371 | ||
372 | if let Some((def_id, depth)) = recursion_depth_reset { | |
373 | recursion_depths.insert(def_id, depth); | |
374 | } | |
375 | ||
a7813a04 | 376 | debug!("END collect_items_rec({})", starting_point.to_string(scx.tcx())); |
7453a54e SL |
377 | } |
378 | ||
a7813a04 XL |
379 | fn record_inlining_canditates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
380 | caller: TransItem<'tcx>, | |
381 | callees: &[TransItem<'tcx>], | |
382 | inlining_map: &mut InliningMap<'tcx>) { | |
383 | let is_inlining_candidate = |trans_item: &TransItem<'tcx>| { | |
32a655c1 | 384 | trans_item.instantiation_mode(tcx) == InstantiationMode::LocalCopy |
a7813a04 XL |
385 | }; |
386 | ||
387 | let inlining_candidates = callees.into_iter() | |
388 | .map(|x| *x) | |
389 | .filter(is_inlining_candidate); | |
390 | ||
391 | inlining_map.record_inlining_canditates(caller, inlining_candidates); | |
392 | } | |
393 | ||
394 | fn check_recursion_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
395 | instance: Instance<'tcx>, | |
396 | recursion_depths: &mut DefIdMap<usize>) | |
397 | -> (DefId, usize) { | |
54a0048b | 398 | let recursion_depth = recursion_depths.get(&instance.def) |
7453a54e SL |
399 | .map(|x| *x) |
400 | .unwrap_or(0); | |
401 | debug!(" => recursion depth={}", recursion_depth); | |
402 | ||
403 | // Code that needs to instantiate the same function recursively | |
404 | // more than the recursion limit is assumed to be causing an | |
405 | // infinite expansion. | |
a7813a04 | 406 | if recursion_depth > tcx.sess.recursion_limit.get() { |
54a0048b SL |
407 | let error = format!("reached the recursion limit while instantiating `{}`", |
408 | instance); | |
32a655c1 SL |
409 | if let Some(node_id) = tcx.hir.as_local_node_id(instance.def) { |
410 | tcx.sess.span_fatal(tcx.hir.span(node_id), &error); | |
7453a54e | 411 | } else { |
a7813a04 | 412 | tcx.sess.fatal(&error); |
7453a54e SL |
413 | } |
414 | } | |
415 | ||
54a0048b | 416 | recursion_depths.insert(instance.def, recursion_depth + 1); |
7453a54e | 417 | |
54a0048b | 418 | (instance.def, recursion_depth) |
7453a54e SL |
419 | } |
420 | ||
476ff2be SL |
421 | fn check_type_length_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
422 | instance: Instance<'tcx>) | |
423 | { | |
424 | let type_length = instance.substs.types().flat_map(|ty| ty.walk()).count(); | |
425 | debug!(" => type length={}", type_length); | |
426 | ||
427 | // Rust code can easily create exponentially-long types using only a | |
428 | // polynomial recursion depth. Even with the default recursion | |
429 | // depth, you can easily get cases that take >2^60 steps to run, | |
430 | // which means that rustc basically hangs. | |
431 | // | |
432 | // Bail out in these cases to avoid that bad user experience. | |
433 | let type_length_limit = tcx.sess.type_length_limit.get(); | |
434 | if type_length > type_length_limit { | |
435 | // The instance name is already known to be too long for rustc. Use | |
436 | // `{:.64}` to avoid blasting the user's terminal with thousands of | |
437 | // lines of type-name. | |
438 | let instance_name = instance.to_string(); | |
439 | let msg = format!("reached the type-length limit while instantiating `{:.64}...`", | |
440 | instance_name); | |
32a655c1 SL |
441 | let mut diag = if let Some(node_id) = tcx.hir.as_local_node_id(instance.def) { |
442 | tcx.sess.struct_span_fatal(tcx.hir.span(node_id), &msg) | |
476ff2be SL |
443 | } else { |
444 | tcx.sess.struct_fatal(&msg) | |
445 | }; | |
446 | ||
447 | diag.note(&format!( | |
448 | "consider adding a `#![type_length_limit=\"{}\"]` attribute to your crate", | |
449 | type_length_limit*2)); | |
450 | diag.emit(); | |
451 | tcx.sess.abort_if_errors(); | |
452 | } | |
453 | } | |
454 | ||
7453a54e | 455 | struct MirNeighborCollector<'a, 'tcx: 'a> { |
a7813a04 | 456 | scx: &'a SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
457 | mir: &'a mir::Mir<'tcx>, |
458 | output: &'a mut Vec<TransItem<'tcx>>, | |
459 | param_substs: &'tcx Substs<'tcx> | |
460 | } | |
461 | ||
462 | impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> { | |
463 | ||
9e0c209e | 464 | fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: Location) { |
7453a54e SL |
465 | debug!("visiting rvalue {:?}", *rvalue); |
466 | ||
467 | match *rvalue { | |
7453a54e SL |
468 | // When doing an cast from a regular pointer to a fat pointer, we |
469 | // have to instantiate all methods of the trait being cast to, so we | |
470 | // can build the appropriate vtable. | |
471 | mir::Rvalue::Cast(mir::CastKind::Unsize, ref operand, target_ty) => { | |
9e0c209e | 472 | let target_ty = monomorphize::apply_param_substs(self.scx, |
7453a54e SL |
473 | self.param_substs, |
474 | &target_ty); | |
5bcae85e | 475 | let source_ty = operand.ty(self.mir, self.scx.tcx()); |
9e0c209e | 476 | let source_ty = monomorphize::apply_param_substs(self.scx, |
7453a54e SL |
477 | self.param_substs, |
478 | &source_ty); | |
a7813a04 | 479 | let (source_ty, target_ty) = find_vtable_types_for_unsizing(self.scx, |
7453a54e SL |
480 | source_ty, |
481 | target_ty); | |
482 | // This could also be a different Unsize instruction, like | |
483 | // from a fixed sized array to a slice. But we are only | |
484 | // interested in things that produce a vtable. | |
485 | if target_ty.is_trait() && !source_ty.is_trait() { | |
a7813a04 | 486 | create_trans_items_for_vtable_methods(self.scx, |
7453a54e SL |
487 | target_ty, |
488 | source_ty, | |
489 | self.output); | |
490 | } | |
491 | } | |
8bb4bdeb XL |
492 | mir::Rvalue::Cast(mir::CastKind::ClosureFnPointer, ref operand, _) => { |
493 | let source_ty = operand.ty(self.mir, self.scx.tcx()); | |
494 | match source_ty.sty { | |
495 | ty::TyClosure(def_id, substs) => { | |
496 | let closure_trans_item = | |
497 | create_fn_trans_item(self.scx, | |
498 | def_id, | |
499 | substs.substs, | |
500 | self.param_substs); | |
501 | self.output.push(closure_trans_item); | |
502 | } | |
503 | _ => bug!(), | |
504 | } | |
505 | } | |
9e0c209e | 506 | mir::Rvalue::Box(..) => { |
7453a54e | 507 | let exchange_malloc_fn_def_id = |
a7813a04 | 508 | self.scx |
7453a54e SL |
509 | .tcx() |
510 | .lang_items | |
511 | .require(ExchangeMallocFnLangItem) | |
a7813a04 | 512 | .unwrap_or_else(|e| self.scx.sess().fatal(&e)); |
7453a54e | 513 | |
32a655c1 SL |
514 | if should_trans_locally(self.scx.tcx(), exchange_malloc_fn_def_id) { |
515 | let empty_substs = self.scx.empty_substs_for_def_id(exchange_malloc_fn_def_id); | |
516 | let exchange_malloc_fn_trans_item = | |
517 | create_fn_trans_item(self.scx, | |
518 | exchange_malloc_fn_def_id, | |
519 | empty_substs, | |
520 | self.param_substs); | |
7453a54e | 521 | |
32a655c1 SL |
522 | self.output.push(exchange_malloc_fn_trans_item); |
523 | } | |
7453a54e SL |
524 | } |
525 | _ => { /* not interesting */ } | |
526 | } | |
527 | ||
9e0c209e | 528 | self.super_rvalue(rvalue, location); |
7453a54e SL |
529 | } |
530 | ||
531 | fn visit_lvalue(&mut self, | |
532 | lvalue: &mir::Lvalue<'tcx>, | |
9e0c209e SL |
533 | context: mir_visit::LvalueContext<'tcx>, |
534 | location: Location) { | |
7453a54e SL |
535 | debug!("visiting lvalue {:?}", *lvalue); |
536 | ||
537 | if let mir_visit::LvalueContext::Drop = context { | |
5bcae85e SL |
538 | let ty = lvalue.ty(self.mir, self.scx.tcx()) |
539 | .to_ty(self.scx.tcx()); | |
7453a54e | 540 | |
9e0c209e | 541 | let ty = monomorphize::apply_param_substs(self.scx, |
7453a54e SL |
542 | self.param_substs, |
543 | &ty); | |
3157f602 | 544 | assert!(ty.is_normalized_for_trans()); |
32a655c1 | 545 | let ty = glue::get_drop_glue_type(self.scx, ty); |
a7813a04 | 546 | self.output.push(TransItem::DropGlue(DropGlueKind::Ty(ty))); |
7453a54e SL |
547 | } |
548 | ||
9e0c209e | 549 | self.super_lvalue(lvalue, context, location); |
7453a54e SL |
550 | } |
551 | ||
9e0c209e | 552 | fn visit_operand(&mut self, operand: &mir::Operand<'tcx>, location: Location) { |
7453a54e SL |
553 | debug!("visiting operand {:?}", *operand); |
554 | ||
555 | let callee = match *operand { | |
5bcae85e SL |
556 | mir::Operand::Constant(ref constant) => { |
557 | if let ty::TyFnDef(def_id, substs, _) = constant.ty.sty { | |
558 | // This is something that can act as a callee, proceed | |
559 | Some((def_id, substs)) | |
560 | } else { | |
561 | // This is not a callee, but we still have to look for | |
562 | // references to `const` items | |
563 | if let mir::Literal::Item { def_id, substs } = constant.literal { | |
9e0c209e | 564 | let substs = monomorphize::apply_param_substs(self.scx, |
5bcae85e SL |
565 | self.param_substs, |
566 | &substs); | |
567 | ||
32a655c1 SL |
568 | let instance = Instance::new(def_id, substs).resolve_const(self.scx); |
569 | collect_neighbours(self.scx, instance, self.output); | |
5bcae85e SL |
570 | } |
571 | ||
572 | None | |
573 | } | |
574 | } | |
7453a54e SL |
575 | _ => None |
576 | }; | |
577 | ||
578 | if let Some((callee_def_id, callee_substs)) = callee { | |
579 | debug!(" => operand is callable"); | |
580 | ||
581 | // `callee_def_id` might refer to a trait method instead of a | |
582 | // concrete implementation, so we have to find the actual | |
583 | // implementation. For example, the call might look like | |
584 | // | |
585 | // std::cmp::partial_cmp(0i32, 1i32) | |
586 | // | |
587 | // Calling do_static_dispatch() here will map the def_id of | |
588 | // `std::cmp::partial_cmp` to the def_id of `i32::partial_cmp<i32>` | |
a7813a04 | 589 | let dispatched = do_static_dispatch(self.scx, |
7453a54e SL |
590 | callee_def_id, |
591 | callee_substs, | |
592 | self.param_substs); | |
593 | ||
32a655c1 SL |
594 | if let StaticDispatchResult::Dispatched { |
595 | def_id: callee_def_id, | |
596 | substs: callee_substs, | |
597 | fn_once_adjustment, | |
598 | } = dispatched { | |
7453a54e SL |
599 | // if we have a concrete impl (which we might not have |
600 | // in the case of something compiler generated like an | |
601 | // object shim or a closure that is handled differently), | |
602 | // we check if the callee is something that will actually | |
603 | // result in a translation item ... | |
a7813a04 | 604 | if can_result_in_trans_item(self.scx.tcx(), callee_def_id) { |
7453a54e | 605 | // ... and create one if it does. |
9e0c209e | 606 | let trans_item = create_fn_trans_item(self.scx, |
7453a54e SL |
607 | callee_def_id, |
608 | callee_substs, | |
609 | self.param_substs); | |
610 | self.output.push(trans_item); | |
32a655c1 SL |
611 | |
612 | // This call will instantiate an FnOnce adapter, which drops | |
613 | // the closure environment. Therefore we need to make sure | |
614 | // that we collect the drop-glue for the environment type. | |
615 | if let Some(env_ty) = fn_once_adjustment { | |
616 | let env_ty = glue::get_drop_glue_type(self.scx, env_ty); | |
617 | if self.scx.type_needs_drop(env_ty) { | |
618 | let dg = DropGlueKind::Ty(env_ty); | |
619 | self.output.push(TransItem::DropGlue(dg)); | |
620 | } | |
621 | } | |
7453a54e SL |
622 | } |
623 | } | |
624 | } | |
625 | ||
9e0c209e | 626 | self.super_operand(operand, location); |
7453a54e | 627 | |
a7813a04 | 628 | fn can_result_in_trans_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
7453a54e SL |
629 | def_id: DefId) |
630 | -> bool { | |
476ff2be | 631 | match tcx.item_type(def_id).sty { |
32a655c1 | 632 | ty::TyFnDef(def_id, _, _) => { |
54a0048b | 633 | // Some constructors also have type TyFnDef but they are |
32a655c1 | 634 | // always instantiated inline and don't result in a |
54a0048b | 635 | // translation item. Same for FFI functions. |
32a655c1 | 636 | if let Some(hir_map::NodeForeignItem(_)) = tcx.hir.get_if_local(def_id) { |
9e0c209e SL |
637 | return false; |
638 | } | |
7453a54e | 639 | } |
9e0c209e SL |
640 | ty::TyClosure(..) => {} |
641 | _ => return false | |
7453a54e SL |
642 | } |
643 | ||
32a655c1 | 644 | should_trans_locally(tcx, def_id) |
a7813a04 XL |
645 | } |
646 | } | |
647 | ||
648 | // This takes care of the "drop_in_place" intrinsic for which we otherwise | |
649 | // we would not register drop-glues. | |
650 | fn visit_terminator_kind(&mut self, | |
651 | block: mir::BasicBlock, | |
9e0c209e SL |
652 | kind: &mir::TerminatorKind<'tcx>, |
653 | location: Location) { | |
a7813a04 XL |
654 | let tcx = self.scx.tcx(); |
655 | match *kind { | |
656 | mir::TerminatorKind::Call { | |
657 | func: mir::Operand::Constant(ref constant), | |
658 | ref args, | |
659 | .. | |
660 | } => { | |
661 | match constant.ty.sty { | |
662 | ty::TyFnDef(def_id, _, bare_fn_ty) | |
663 | if is_drop_in_place_intrinsic(tcx, def_id, bare_fn_ty) => { | |
5bcae85e | 664 | let operand_ty = args[0].ty(self.mir, tcx); |
a7813a04 | 665 | if let ty::TyRawPtr(mt) = operand_ty.sty { |
9e0c209e | 666 | let operand_ty = monomorphize::apply_param_substs(self.scx, |
a7813a04 XL |
667 | self.param_substs, |
668 | &mt.ty); | |
32a655c1 | 669 | let ty = glue::get_drop_glue_type(self.scx, operand_ty); |
5bcae85e | 670 | self.output.push(TransItem::DropGlue(DropGlueKind::Ty(ty))); |
a7813a04 XL |
671 | } else { |
672 | bug!("Has the drop_in_place() intrinsic's signature changed?") | |
673 | } | |
674 | } | |
675 | _ => { /* Nothing to do. */ } | |
676 | } | |
677 | } | |
678 | _ => { /* Nothing to do. */ } | |
679 | } | |
680 | ||
9e0c209e | 681 | self.super_terminator_kind(block, kind, location); |
a7813a04 XL |
682 | |
683 | fn is_drop_in_place_intrinsic<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
684 | def_id: DefId, | |
8bb4bdeb | 685 | bare_fn_ty: ty::PolyFnSig<'tcx>) |
a7813a04 | 686 | -> bool { |
8bb4bdeb XL |
687 | (bare_fn_ty.abi() == Abi::RustIntrinsic || |
688 | bare_fn_ty.abi() == Abi::PlatformIntrinsic) && | |
476ff2be | 689 | tcx.item_name(def_id) == "drop_in_place" |
7453a54e SL |
690 | } |
691 | } | |
692 | } | |
693 | ||
32a655c1 SL |
694 | // Returns true if we should translate an instance in the local crate. |
695 | // Returns false if we can just link to the upstream crate and therefore don't | |
696 | // need a translation item. | |
697 | fn should_trans_locally<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
698 | def_id: DefId) | |
699 | -> bool { | |
8bb4bdeb XL |
700 | if let ty::TyFnDef(_, _, sig) = tcx.item_type(def_id).sty { |
701 | if let Some(adt_def) = sig.output().skip_binder().ty_adt_def() { | |
32a655c1 SL |
702 | if adt_def.variants.iter().any(|v| def_id == v.did) { |
703 | // HACK: ADT constructors are translated in-place and | |
704 | // do not have a trans-item. | |
705 | return false; | |
706 | } | |
707 | } | |
708 | } | |
709 | ||
710 | if def_id.is_local() { | |
711 | true | |
712 | } else { | |
713 | if tcx.sess.cstore.is_exported_symbol(def_id) || | |
714 | tcx.sess.cstore.is_foreign_item(def_id) { | |
715 | // We can link to the item in question, no instance needed in this | |
716 | // crate | |
717 | false | |
718 | } else { | |
719 | if !tcx.sess.cstore.is_item_mir_available(def_id) { | |
720 | bug!("Cannot create local trans-item for {:?}", def_id) | |
721 | } | |
722 | true | |
723 | } | |
724 | } | |
7453a54e SL |
725 | } |
726 | ||
a7813a04 XL |
727 | fn find_drop_glue_neighbors<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
728 | dg: DropGlueKind<'tcx>, | |
729 | output: &mut Vec<TransItem<'tcx>>) { | |
730 | let ty = match dg { | |
731 | DropGlueKind::Ty(ty) => ty, | |
732 | DropGlueKind::TyContents(_) => { | |
733 | // We already collected the neighbors of this item via the | |
734 | // DropGlueKind::Ty variant. | |
735 | return | |
736 | } | |
737 | }; | |
738 | ||
739 | debug!("find_drop_glue_neighbors: {}", type_to_string(scx.tcx(), ty)); | |
7453a54e | 740 | |
32a655c1 SL |
741 | // Make sure the BoxFreeFn lang-item gets translated if there is a boxed value. |
742 | if ty.is_box() { | |
743 | let def_id = scx.tcx().require_lang_item(BoxFreeFnLangItem); | |
744 | if should_trans_locally(scx.tcx(), def_id) { | |
745 | let box_free_fn_trans_item = | |
746 | create_fn_trans_item(scx, | |
747 | def_id, | |
748 | scx.tcx().mk_substs(iter::once(Kind::from(ty.boxed_ty()))), | |
749 | scx.tcx().intern_substs(&[])); | |
750 | output.push(box_free_fn_trans_item); | |
751 | } | |
7453a54e SL |
752 | } |
753 | ||
754 | // If the type implements Drop, also add a translation item for the | |
755 | // monomorphized Drop::drop() implementation. | |
8bb4bdeb XL |
756 | let destructor = match ty.sty { |
757 | ty::TyAdt(def, _) => def.destructor(scx.tcx()), | |
7453a54e SL |
758 | _ => None |
759 | }; | |
760 | ||
8bb4bdeb | 761 | if let (Some(destructor), false) = (destructor, ty.is_box()) { |
54a0048b | 762 | use rustc::ty::ToPolyTraitRef; |
7453a54e | 763 | |
a7813a04 | 764 | let drop_trait_def_id = scx.tcx() |
7453a54e SL |
765 | .lang_items |
766 | .drop_trait() | |
767 | .unwrap(); | |
768 | ||
c30ab7b3 | 769 | let self_type_substs = scx.tcx().mk_substs_trait(ty, &[]); |
7453a54e SL |
770 | |
771 | let trait_ref = ty::TraitRef { | |
772 | def_id: drop_trait_def_id, | |
773 | substs: self_type_substs, | |
774 | }.to_poly_trait_ref(); | |
775 | ||
a7813a04 | 776 | let substs = match fulfill_obligation(scx, DUMMY_SP, trait_ref) { |
7453a54e | 777 | traits::VtableImpl(data) => data.substs, |
54a0048b | 778 | _ => bug!() |
7453a54e SL |
779 | }; |
780 | ||
8bb4bdeb | 781 | if should_trans_locally(scx.tcx(), destructor.did) { |
9e0c209e | 782 | let trans_item = create_fn_trans_item(scx, |
8bb4bdeb | 783 | destructor.did, |
54a0048b | 784 | substs, |
c30ab7b3 | 785 | scx.tcx().intern_substs(&[])); |
7453a54e SL |
786 | output.push(trans_item); |
787 | } | |
a7813a04 XL |
788 | |
789 | // This type has a Drop implementation, we'll need the contents-only | |
790 | // version of the glue too. | |
791 | output.push(TransItem::DropGlue(DropGlueKind::TyContents(ty))); | |
7453a54e SL |
792 | } |
793 | ||
794 | // Finally add the types of nested values | |
795 | match ty.sty { | |
54a0048b SL |
796 | ty::TyBool | |
797 | ty::TyChar | | |
798 | ty::TyInt(_) | | |
799 | ty::TyUint(_) | | |
800 | ty::TyStr | | |
801 | ty::TyFloat(_) | | |
802 | ty::TyRawPtr(_) | | |
803 | ty::TyRef(..) | | |
804 | ty::TyFnDef(..) | | |
805 | ty::TyFnPtr(_) | | |
5bcae85e | 806 | ty::TyNever | |
476ff2be | 807 | ty::TyDynamic(..) => { |
7453a54e SL |
808 | /* nothing to do */ |
809 | } | |
32a655c1 SL |
810 | ty::TyAdt(def, _) if def.is_box() => { |
811 | let inner_type = glue::get_drop_glue_type(scx, ty.boxed_ty()); | |
812 | if scx.type_needs_drop(inner_type) { | |
813 | output.push(TransItem::DropGlue(DropGlueKind::Ty(inner_type))); | |
814 | } | |
815 | } | |
816 | ty::TyAdt(def, substs) => { | |
817 | for field in def.all_fields() { | |
8bb4bdeb | 818 | let field_type = def_ty(scx, field.did, substs); |
32a655c1 | 819 | let field_type = glue::get_drop_glue_type(scx, field_type); |
7453a54e | 820 | |
32a655c1 | 821 | if scx.type_needs_drop(field_type) { |
a7813a04 | 822 | output.push(TransItem::DropGlue(DropGlueKind::Ty(field_type))); |
7453a54e SL |
823 | } |
824 | } | |
825 | } | |
476ff2be SL |
826 | ty::TyClosure(def_id, substs) => { |
827 | for upvar_ty in substs.upvar_tys(def_id, scx.tcx()) { | |
32a655c1 SL |
828 | let upvar_ty = glue::get_drop_glue_type(scx, upvar_ty); |
829 | if scx.type_needs_drop(upvar_ty) { | |
a7813a04 | 830 | output.push(TransItem::DropGlue(DropGlueKind::Ty(upvar_ty))); |
7453a54e SL |
831 | } |
832 | } | |
833 | } | |
a7813a04 | 834 | ty::TySlice(inner_type) | |
7453a54e | 835 | ty::TyArray(inner_type, _) => { |
32a655c1 SL |
836 | let inner_type = glue::get_drop_glue_type(scx, inner_type); |
837 | if scx.type_needs_drop(inner_type) { | |
a7813a04 | 838 | output.push(TransItem::DropGlue(DropGlueKind::Ty(inner_type))); |
7453a54e SL |
839 | } |
840 | } | |
8bb4bdeb | 841 | ty::TyTuple(args, _) => { |
7453a54e | 842 | for arg in args { |
32a655c1 SL |
843 | let arg = glue::get_drop_glue_type(scx, arg); |
844 | if scx.type_needs_drop(arg) { | |
a7813a04 | 845 | output.push(TransItem::DropGlue(DropGlueKind::Ty(arg))); |
7453a54e SL |
846 | } |
847 | } | |
848 | } | |
849 | ty::TyProjection(_) | | |
850 | ty::TyParam(_) | | |
851 | ty::TyInfer(_) | | |
5bcae85e | 852 | ty::TyAnon(..) | |
7453a54e | 853 | ty::TyError => { |
54a0048b | 854 | bug!("encountered unexpected type"); |
7453a54e SL |
855 | } |
856 | } | |
857 | } | |
858 | ||
a7813a04 | 859 | fn do_static_dispatch<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
860 | fn_def_id: DefId, |
861 | fn_substs: &'tcx Substs<'tcx>, | |
862 | param_substs: &'tcx Substs<'tcx>) | |
32a655c1 | 863 | -> StaticDispatchResult<'tcx> { |
7453a54e | 864 | debug!("do_static_dispatch(fn_def_id={}, fn_substs={:?}, param_substs={:?})", |
a7813a04 | 865 | def_id_to_string(scx.tcx(), fn_def_id), |
7453a54e SL |
866 | fn_substs, |
867 | param_substs); | |
868 | ||
9e0c209e | 869 | if let Some(trait_def_id) = scx.tcx().trait_of_item(fn_def_id) { |
476ff2be SL |
870 | debug!(" => trait method, attempting to find impl"); |
871 | do_static_trait_method_dispatch(scx, | |
872 | &scx.tcx().associated_item(fn_def_id), | |
873 | trait_def_id, | |
874 | fn_substs, | |
875 | param_substs) | |
7453a54e SL |
876 | } else { |
877 | debug!(" => regular function"); | |
878 | // The function is not part of an impl or trait, no dispatching | |
879 | // to be done | |
32a655c1 SL |
880 | StaticDispatchResult::Dispatched { |
881 | def_id: fn_def_id, | |
882 | substs: fn_substs, | |
883 | fn_once_adjustment: None, | |
884 | } | |
7453a54e SL |
885 | } |
886 | } | |
887 | ||
32a655c1 SL |
888 | enum StaticDispatchResult<'tcx> { |
889 | // The call could be resolved statically as going to the method with | |
890 | // `def_id` and `substs`. | |
891 | Dispatched { | |
892 | def_id: DefId, | |
893 | substs: &'tcx Substs<'tcx>, | |
894 | ||
895 | // If this is a call to a closure that needs an FnOnce adjustment, | |
896 | // this contains the new self type of the call (= type of the closure | |
897 | // environment) | |
898 | fn_once_adjustment: Option<ty::Ty<'tcx>>, | |
899 | }, | |
900 | // This goes to somewhere that we don't know at compile-time | |
901 | Unknown | |
902 | } | |
903 | ||
7453a54e SL |
904 | // Given a trait-method and substitution information, find out the actual |
905 | // implementation of the trait method. | |
a7813a04 | 906 | fn do_static_trait_method_dispatch<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
476ff2be | 907 | trait_method: &ty::AssociatedItem, |
7453a54e SL |
908 | trait_id: DefId, |
909 | callee_substs: &'tcx Substs<'tcx>, | |
910 | param_substs: &'tcx Substs<'tcx>) | |
32a655c1 | 911 | -> StaticDispatchResult<'tcx> { |
a7813a04 | 912 | let tcx = scx.tcx(); |
7453a54e SL |
913 | debug!("do_static_trait_method_dispatch(trait_method={}, \ |
914 | trait_id={}, \ | |
915 | callee_substs={:?}, \ | |
916 | param_substs={:?}", | |
a7813a04 XL |
917 | def_id_to_string(scx.tcx(), trait_method.def_id), |
918 | def_id_to_string(scx.tcx(), trait_id), | |
7453a54e SL |
919 | callee_substs, |
920 | param_substs); | |
921 | ||
9e0c209e | 922 | let rcvr_substs = monomorphize::apply_param_substs(scx, |
7453a54e | 923 | param_substs, |
a7813a04 | 924 | &callee_substs); |
9e0c209e SL |
925 | let trait_ref = ty::TraitRef::from_method(tcx, trait_id, rcvr_substs); |
926 | let vtbl = fulfill_obligation(scx, DUMMY_SP, ty::Binder(trait_ref)); | |
7453a54e SL |
927 | |
928 | // Now that we know which impl is being used, we can dispatch to | |
929 | // the actual function: | |
930 | match vtbl { | |
9e0c209e | 931 | traits::VtableImpl(impl_data) => { |
32a655c1 SL |
932 | let (def_id, substs) = traits::find_method(tcx, |
933 | trait_method.name, | |
934 | rcvr_substs, | |
935 | &impl_data); | |
936 | StaticDispatchResult::Dispatched { | |
937 | def_id: def_id, | |
938 | substs: substs, | |
939 | fn_once_adjustment: None, | |
940 | } | |
7453a54e | 941 | } |
476ff2be | 942 | traits::VtableClosure(closure_data) => { |
32a655c1 SL |
943 | let closure_def_id = closure_data.closure_def_id; |
944 | let trait_closure_kind = tcx.lang_items.fn_trait_kind(trait_id).unwrap(); | |
945 | let actual_closure_kind = tcx.closure_kind(closure_def_id); | |
946 | ||
947 | let needs_fn_once_adapter_shim = | |
948 | match needs_fn_once_adapter_shim(actual_closure_kind, | |
949 | trait_closure_kind) { | |
950 | Ok(true) => true, | |
951 | _ => false, | |
952 | }; | |
953 | ||
954 | let fn_once_adjustment = if needs_fn_once_adapter_shim { | |
955 | Some(tcx.mk_closure_from_closure_substs(closure_def_id, | |
956 | closure_data.substs)) | |
957 | } else { | |
958 | None | |
959 | }; | |
960 | ||
961 | StaticDispatchResult::Dispatched { | |
962 | def_id: closure_def_id, | |
963 | substs: closure_data.substs.substs, | |
964 | fn_once_adjustment: fn_once_adjustment, | |
965 | } | |
476ff2be | 966 | } |
32a655c1 SL |
967 | traits::VtableFnPointer(ref data) => { |
968 | // If we know the destination of this fn-pointer, we'll have to make | |
969 | // sure that this destination actually gets instantiated. | |
970 | if let ty::TyFnDef(def_id, substs, _) = data.fn_ty.sty { | |
971 | // The destination of the pointer might be something that needs | |
972 | // further dispatching, such as a trait method, so we do that. | |
973 | do_static_dispatch(scx, def_id, substs, param_substs) | |
974 | } else { | |
975 | StaticDispatchResult::Unknown | |
976 | } | |
977 | } | |
978 | // Trait object shims are always instantiated in-place, and as they are | |
979 | // just an ABI-adjusting indirect call they do not have any dependencies. | |
7453a54e | 980 | traits::VtableObject(..) => { |
32a655c1 | 981 | StaticDispatchResult::Unknown |
7453a54e SL |
982 | } |
983 | _ => { | |
54a0048b | 984 | bug!("static call to invalid vtable: {:?}", vtbl) |
7453a54e SL |
985 | } |
986 | } | |
987 | } | |
988 | ||
989 | /// For given pair of source and target type that occur in an unsizing coercion, | |
990 | /// this function finds the pair of types that determines the vtable linking | |
991 | /// them. | |
992 | /// | |
993 | /// For example, the source type might be `&SomeStruct` and the target type\ | |
994 | /// might be `&SomeTrait` in a cast like: | |
995 | /// | |
996 | /// let src: &SomeStruct = ...; | |
997 | /// let target = src as &SomeTrait; | |
998 | /// | |
999 | /// Then the output of this function would be (SomeStruct, SomeTrait) since for | |
1000 | /// constructing the `target` fat-pointer we need the vtable for that pair. | |
1001 | /// | |
1002 | /// Things can get more complicated though because there's also the case where | |
1003 | /// the unsized type occurs as a field: | |
1004 | /// | |
1005 | /// ```rust | |
1006 | /// struct ComplexStruct<T: ?Sized> { | |
1007 | /// a: u32, | |
1008 | /// b: f64, | |
1009 | /// c: T | |
1010 | /// } | |
1011 | /// ``` | |
1012 | /// | |
1013 | /// In this case, if `T` is sized, `&ComplexStruct<T>` is a thin pointer. If `T` | |
1014 | /// is unsized, `&SomeStruct` is a fat pointer, and the vtable it points to is | |
1015 | /// for the pair of `T` (which is a trait) and the concrete type that `T` was | |
1016 | /// originally coerced from: | |
1017 | /// | |
1018 | /// let src: &ComplexStruct<SomeStruct> = ...; | |
1019 | /// let target = src as &ComplexStruct<SomeTrait>; | |
1020 | /// | |
1021 | /// Again, we want this `find_vtable_types_for_unsizing()` to provide the pair | |
1022 | /// `(SomeStruct, SomeTrait)`. | |
1023 | /// | |
1024 | /// Finally, there is also the case of custom unsizing coercions, e.g. for | |
1025 | /// smart pointers such as `Rc` and `Arc`. | |
a7813a04 | 1026 | fn find_vtable_types_for_unsizing<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
1027 | source_ty: ty::Ty<'tcx>, |
1028 | target_ty: ty::Ty<'tcx>) | |
1029 | -> (ty::Ty<'tcx>, ty::Ty<'tcx>) { | |
32a655c1 SL |
1030 | let ptr_vtable = |inner_source: ty::Ty<'tcx>, inner_target: ty::Ty<'tcx>| { |
1031 | if !scx.type_is_sized(inner_source) { | |
1032 | (inner_source, inner_target) | |
1033 | } else { | |
1034 | scx.tcx().struct_lockstep_tails(inner_source, inner_target) | |
1035 | } | |
1036 | }; | |
7453a54e | 1037 | match (&source_ty.sty, &target_ty.sty) { |
7453a54e SL |
1038 | (&ty::TyRef(_, ty::TypeAndMut { ty: a, .. }), |
1039 | &ty::TyRef(_, ty::TypeAndMut { ty: b, .. })) | | |
1040 | (&ty::TyRef(_, ty::TypeAndMut { ty: a, .. }), | |
1041 | &ty::TyRawPtr(ty::TypeAndMut { ty: b, .. })) | | |
1042 | (&ty::TyRawPtr(ty::TypeAndMut { ty: a, .. }), | |
1043 | &ty::TyRawPtr(ty::TypeAndMut { ty: b, .. })) => { | |
32a655c1 SL |
1044 | ptr_vtable(a, b) |
1045 | } | |
1046 | (&ty::TyAdt(def_a, _), &ty::TyAdt(def_b, _)) if def_a.is_box() && def_b.is_box() => { | |
1047 | ptr_vtable(source_ty.boxed_ty(), target_ty.boxed_ty()) | |
7453a54e SL |
1048 | } |
1049 | ||
9e0c209e SL |
1050 | (&ty::TyAdt(source_adt_def, source_substs), |
1051 | &ty::TyAdt(target_adt_def, target_substs)) => { | |
7453a54e SL |
1052 | assert_eq!(source_adt_def, target_adt_def); |
1053 | ||
a7813a04 | 1054 | let kind = custom_coerce_unsize_info(scx, source_ty, target_ty); |
7453a54e SL |
1055 | |
1056 | let coerce_index = match kind { | |
1057 | CustomCoerceUnsized::Struct(i) => i | |
1058 | }; | |
1059 | ||
1060 | let source_fields = &source_adt_def.struct_variant().fields; | |
1061 | let target_fields = &target_adt_def.struct_variant().fields; | |
1062 | ||
1063 | assert!(coerce_index < source_fields.len() && | |
1064 | source_fields.len() == target_fields.len()); | |
1065 | ||
a7813a04 XL |
1066 | find_vtable_types_for_unsizing(scx, |
1067 | source_fields[coerce_index].ty(scx.tcx(), | |
7453a54e | 1068 | source_substs), |
a7813a04 | 1069 | target_fields[coerce_index].ty(scx.tcx(), |
7453a54e SL |
1070 | target_substs)) |
1071 | } | |
54a0048b SL |
1072 | _ => bug!("find_vtable_types_for_unsizing: invalid coercion {:?} -> {:?}", |
1073 | source_ty, | |
1074 | target_ty) | |
7453a54e SL |
1075 | } |
1076 | } | |
1077 | ||
9e0c209e | 1078 | fn create_fn_trans_item<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e | 1079 | def_id: DefId, |
a7813a04 XL |
1080 | fn_substs: &'tcx Substs<'tcx>, |
1081 | param_substs: &'tcx Substs<'tcx>) | |
1082 | -> TransItem<'tcx> { | |
9e0c209e SL |
1083 | let tcx = scx.tcx(); |
1084 | ||
7453a54e | 1085 | debug!("create_fn_trans_item(def_id={}, fn_substs={:?}, param_substs={:?})", |
a7813a04 | 1086 | def_id_to_string(tcx, def_id), |
7453a54e SL |
1087 | fn_substs, |
1088 | param_substs); | |
1089 | ||
1090 | // We only get here, if fn_def_id either designates a local item or | |
1091 | // an inlineable external item. Non-inlineable external items are | |
1092 | // ignored because we don't want to generate any code for them. | |
9e0c209e | 1093 | let concrete_substs = monomorphize::apply_param_substs(scx, |
7453a54e | 1094 | param_substs, |
a7813a04 | 1095 | &fn_substs); |
1bb2cb6e SL |
1096 | assert!(concrete_substs.is_normalized_for_trans(), |
1097 | "concrete_substs not normalized for trans: {:?}", | |
1098 | concrete_substs); | |
3157f602 | 1099 | TransItem::Fn(Instance::new(def_id, concrete_substs)) |
7453a54e SL |
1100 | } |
1101 | ||
1102 | /// Creates a `TransItem` for each method that is referenced by the vtable for | |
1103 | /// the given trait/impl pair. | |
a7813a04 | 1104 | fn create_trans_items_for_vtable_methods<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
1105 | trait_ty: ty::Ty<'tcx>, |
1106 | impl_ty: ty::Ty<'tcx>, | |
1107 | output: &mut Vec<TransItem<'tcx>>) { | |
8bb4bdeb XL |
1108 | assert!(!trait_ty.needs_subst() && !trait_ty.has_escaping_regions() && |
1109 | !impl_ty.needs_subst() && !impl_ty.has_escaping_regions()); | |
7453a54e | 1110 | |
476ff2be SL |
1111 | if let ty::TyDynamic(ref trait_ty, ..) = trait_ty.sty { |
1112 | if let Some(principal) = trait_ty.principal() { | |
1113 | let poly_trait_ref = principal.with_self_ty(scx.tcx(), impl_ty); | |
1114 | let param_substs = scx.tcx().intern_substs(&[]); | |
1115 | ||
8bb4bdeb XL |
1116 | assert!(!poly_trait_ref.has_escaping_regions()); |
1117 | ||
476ff2be SL |
1118 | // Walk all methods of the trait, including those of its supertraits |
1119 | let methods = traits::get_vtable_methods(scx.tcx(), poly_trait_ref); | |
1120 | let methods = methods.filter_map(|method| method) | |
32a655c1 SL |
1121 | .filter_map(|(def_id, substs)| { |
1122 | if let StaticDispatchResult::Dispatched { | |
1123 | def_id, | |
1124 | substs, | |
1125 | // We already add the drop-glue for the closure env | |
1126 | // unconditionally below. | |
1127 | fn_once_adjustment: _ , | |
1128 | } = do_static_dispatch(scx, def_id, substs, param_substs) { | |
1129 | Some((def_id, substs)) | |
1130 | } else { | |
1131 | None | |
1132 | } | |
1133 | }) | |
1134 | .filter(|&(def_id, _)| should_trans_locally(scx.tcx(), def_id)) | |
476ff2be SL |
1135 | .map(|(def_id, substs)| create_fn_trans_item(scx, def_id, substs, param_substs)); |
1136 | output.extend(methods); | |
1137 | } | |
9e0c209e | 1138 | // Also add the destructor |
32a655c1 | 1139 | let dg_type = glue::get_drop_glue_type(scx, impl_ty); |
9e0c209e | 1140 | output.push(TransItem::DropGlue(DropGlueKind::Ty(dg_type))); |
7453a54e SL |
1141 | } |
1142 | } | |
1143 | ||
1144 | //=----------------------------------------------------------------------------- | |
1145 | // Root Collection | |
1146 | //=----------------------------------------------------------------------------- | |
1147 | ||
1148 | struct RootCollector<'b, 'a: 'b, 'tcx: 'a + 'b> { | |
a7813a04 | 1149 | scx: &'b SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
1150 | mode: TransItemCollectionMode, |
1151 | output: &'b mut Vec<TransItem<'tcx>>, | |
7453a54e SL |
1152 | } |
1153 | ||
476ff2be | 1154 | impl<'b, 'a, 'v> ItemLikeVisitor<'v> for RootCollector<'b, 'a, 'v> { |
7453a54e | 1155 | fn visit_item(&mut self, item: &'v hir::Item) { |
7453a54e SL |
1156 | match item.node { |
1157 | hir::ItemExternCrate(..) | | |
1158 | hir::ItemUse(..) | | |
1159 | hir::ItemForeignMod(..) | | |
1160 | hir::ItemTy(..) | | |
1161 | hir::ItemDefaultImpl(..) | | |
1162 | hir::ItemTrait(..) | | |
7453a54e SL |
1163 | hir::ItemMod(..) => { |
1164 | // Nothing to do, just keep recursing... | |
1165 | } | |
1166 | ||
1167 | hir::ItemImpl(..) => { | |
1168 | if self.mode == TransItemCollectionMode::Eager { | |
9e0c209e | 1169 | create_trans_items_for_default_impls(self.scx, |
7453a54e | 1170 | item, |
7453a54e SL |
1171 | self.output); |
1172 | } | |
1173 | } | |
1174 | ||
9e0c209e SL |
1175 | hir::ItemEnum(_, ref generics) | |
1176 | hir::ItemStruct(_, ref generics) | | |
1177 | hir::ItemUnion(_, ref generics) => { | |
7453a54e | 1178 | if !generics.is_parameterized() { |
7453a54e | 1179 | if self.mode == TransItemCollectionMode::Eager { |
32a655c1 | 1180 | let def_id = self.scx.tcx().hir.local_def_id(item.id); |
7453a54e | 1181 | debug!("RootCollector: ADT drop-glue for {}", |
476ff2be | 1182 | def_id_to_string(self.scx.tcx(), def_id)); |
7453a54e | 1183 | |
8bb4bdeb | 1184 | let ty = def_ty(self.scx, def_id, Substs::empty()); |
32a655c1 | 1185 | let ty = glue::get_drop_glue_type(self.scx, ty); |
a7813a04 | 1186 | self.output.push(TransItem::DropGlue(DropGlueKind::Ty(ty))); |
7453a54e SL |
1187 | } |
1188 | } | |
1189 | } | |
1190 | hir::ItemStatic(..) => { | |
1191 | debug!("RootCollector: ItemStatic({})", | |
a7813a04 | 1192 | def_id_to_string(self.scx.tcx(), |
32a655c1 | 1193 | self.scx.tcx().hir.local_def_id(item.id))); |
7453a54e SL |
1194 | self.output.push(TransItem::Static(item.id)); |
1195 | } | |
5bcae85e SL |
1196 | hir::ItemConst(..) => { |
1197 | // const items only generate translation items if they are | |
1198 | // actually used somewhere. Just declaring them is insufficient. | |
1199 | } | |
9e0c209e | 1200 | hir::ItemFn(.., ref generics, _) => { |
5bcae85e | 1201 | if !generics.is_type_parameterized() { |
32a655c1 | 1202 | let def_id = self.scx.tcx().hir.local_def_id(item.id); |
7453a54e SL |
1203 | |
1204 | debug!("RootCollector: ItemFn({})", | |
a7813a04 | 1205 | def_id_to_string(self.scx.tcx(), def_id)); |
7453a54e | 1206 | |
a7813a04 | 1207 | let instance = Instance::mono(self.scx, def_id); |
54a0048b | 1208 | self.output.push(TransItem::Fn(instance)); |
7453a54e SL |
1209 | } |
1210 | } | |
1211 | } | |
7453a54e SL |
1212 | } |
1213 | ||
32a655c1 SL |
1214 | fn visit_trait_item(&mut self, _: &'v hir::TraitItem) { |
1215 | // Even if there's a default body with no explicit generics, | |
1216 | // it's still generic over some `Self: Trait`, so not a root. | |
1217 | } | |
1218 | ||
7453a54e SL |
1219 | fn visit_impl_item(&mut self, ii: &'v hir::ImplItem) { |
1220 | match ii.node { | |
1221 | hir::ImplItemKind::Method(hir::MethodSig { | |
1222 | ref generics, | |
7453a54e | 1223 | .. |
5bcae85e | 1224 | }, _) => { |
32a655c1 | 1225 | let hir_map = &self.scx.tcx().hir; |
7453a54e SL |
1226 | let parent_node_id = hir_map.get_parent_node(ii.id); |
1227 | let is_impl_generic = match hir_map.expect_item(parent_node_id) { | |
1228 | &hir::Item { | |
9e0c209e | 1229 | node: hir::ItemImpl(_, _, ref generics, ..), |
7453a54e SL |
1230 | .. |
1231 | } => { | |
1232 | generics.is_type_parameterized() | |
1233 | } | |
1234 | _ => { | |
54a0048b | 1235 | bug!() |
7453a54e SL |
1236 | } |
1237 | }; | |
1238 | ||
1239 | if !generics.is_type_parameterized() && !is_impl_generic { | |
32a655c1 | 1240 | let def_id = self.scx.tcx().hir.local_def_id(ii.id); |
7453a54e SL |
1241 | |
1242 | debug!("RootCollector: MethodImplItem({})", | |
a7813a04 | 1243 | def_id_to_string(self.scx.tcx(), def_id)); |
7453a54e | 1244 | |
a7813a04 | 1245 | let instance = Instance::mono(self.scx, def_id); |
54a0048b | 1246 | self.output.push(TransItem::Fn(instance)); |
7453a54e SL |
1247 | } |
1248 | } | |
1249 | _ => { /* Nothing to do here */ } | |
1250 | } | |
7453a54e SL |
1251 | } |
1252 | } | |
1253 | ||
9e0c209e | 1254 | fn create_trans_items_for_default_impls<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e | 1255 | item: &'tcx hir::Item, |
7453a54e | 1256 | output: &mut Vec<TransItem<'tcx>>) { |
9e0c209e | 1257 | let tcx = scx.tcx(); |
7453a54e SL |
1258 | match item.node { |
1259 | hir::ItemImpl(_, | |
1260 | _, | |
1261 | ref generics, | |
9e0c209e | 1262 | .., |
476ff2be | 1263 | ref impl_item_refs) => { |
7453a54e SL |
1264 | if generics.is_type_parameterized() { |
1265 | return | |
1266 | } | |
1267 | ||
32a655c1 | 1268 | let impl_def_id = tcx.hir.local_def_id(item.id); |
7453a54e SL |
1269 | |
1270 | debug!("create_trans_items_for_default_impls(item={})", | |
a7813a04 | 1271 | def_id_to_string(tcx, impl_def_id)); |
7453a54e SL |
1272 | |
1273 | if let Some(trait_ref) = tcx.impl_trait_ref(impl_def_id) { | |
a7813a04 | 1274 | let callee_substs = tcx.erase_regions(&trait_ref.substs); |
476ff2be SL |
1275 | let overridden_methods: FxHashSet<_> = |
1276 | impl_item_refs.iter() | |
1277 | .map(|iiref| iiref.name) | |
1278 | .collect(); | |
9e0c209e SL |
1279 | for method in tcx.provided_trait_methods(trait_ref.def_id) { |
1280 | if overridden_methods.contains(&method.name) { | |
7453a54e SL |
1281 | continue; |
1282 | } | |
1283 | ||
476ff2be | 1284 | if !tcx.item_generics(method.def_id).types.is_empty() { |
7453a54e SL |
1285 | continue; |
1286 | } | |
1287 | ||
1288 | // The substitutions we have are on the impl, so we grab | |
1289 | // the method type from the impl to substitute into. | |
9e0c209e SL |
1290 | let impl_substs = Substs::for_item(tcx, impl_def_id, |
1291 | |_, _| tcx.mk_region(ty::ReErased), | |
1292 | |_, _| tcx.types.err); | |
1293 | let impl_data = traits::VtableImplData { | |
1294 | impl_def_id: impl_def_id, | |
1295 | substs: impl_substs, | |
1296 | nested: vec![] | |
1297 | }; | |
1298 | let (def_id, substs) = traits::find_method(tcx, | |
1299 | method.name, | |
1300 | callee_substs, | |
1301 | &impl_data); | |
1302 | ||
476ff2be | 1303 | let predicates = tcx.item_predicates(def_id).predicates |
9e0c209e SL |
1304 | .subst(tcx, substs); |
1305 | if !traits::normalize_and_test_predicates(tcx, predicates) { | |
7453a54e SL |
1306 | continue; |
1307 | } | |
1308 | ||
32a655c1 | 1309 | if should_trans_locally(tcx, method.def_id) { |
9e0c209e SL |
1310 | let item = create_fn_trans_item(scx, |
1311 | method.def_id, | |
7453a54e | 1312 | callee_substs, |
9e0c209e | 1313 | tcx.erase_regions(&substs)); |
7453a54e SL |
1314 | output.push(item); |
1315 | } | |
1316 | } | |
1317 | } | |
1318 | } | |
1319 | _ => { | |
54a0048b | 1320 | bug!() |
7453a54e SL |
1321 | } |
1322 | } | |
1323 | } | |
1324 | ||
32a655c1 SL |
1325 | /// Scan the MIR in order to find function calls, closures, and drop-glue |
1326 | fn collect_neighbours<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, | |
1327 | instance: Instance<'tcx>, | |
1328 | output: &mut Vec<TransItem<'tcx>>) | |
5bcae85e | 1329 | { |
32a655c1 | 1330 | let mir = scx.tcx().item_mir(instance.def); |
5bcae85e | 1331 | |
32a655c1 | 1332 | let mut visitor = MirNeighborCollector { |
5bcae85e SL |
1333 | scx: scx, |
1334 | mir: &mir, | |
1335 | output: output, | |
32a655c1 | 1336 | param_substs: instance.substs |
5bcae85e | 1337 | }; |
7453a54e | 1338 | |
5bcae85e SL |
1339 | visitor.visit_mir(&mir); |
1340 | for promoted in &mir.promoted { | |
32a655c1 | 1341 | visitor.mir = promoted; |
5bcae85e | 1342 | visitor.visit_mir(promoted); |
7453a54e SL |
1343 | } |
1344 | } | |
476ff2be SL |
1345 | |
1346 | fn def_id_to_string<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
1347 | def_id: DefId) | |
1348 | -> String { | |
1349 | let mut output = String::new(); | |
1350 | let printer = DefPathBasedNames::new(tcx, false, false); | |
1351 | printer.push_def_path(def_id, &mut output); | |
1352 | output | |
1353 | } | |
1354 | ||
1355 | fn type_to_string<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
1356 | ty: ty::Ty<'tcx>) | |
1357 | -> String { | |
1358 | let mut output = String::new(); | |
1359 | let printer = DefPathBasedNames::new(tcx, false, false); | |
1360 | printer.push_type_name(ty, &mut output); | |
1361 | output | |
1362 | } |