]>
Commit | Line | Data |
---|---|---|
1a4d82fc | 1 | // Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT |
970d7e83 LB |
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 | // Finds items that are externally reachable, to determine which items | |
12 | // need to have their metadata (and possibly their AST) serialized. | |
13 | // All items that can be referred to through an exported name are | |
14 | // reachable, and when a reachable thing is inline or generic, it | |
15 | // makes all other generics or inline functions that it references | |
16 | // reachable as well. | |
17 | ||
94b46f34 | 18 | use hir::CodegenFnAttrs; |
32a655c1 | 19 | use hir::map as hir_map; |
54a0048b | 20 | use hir::def::Def; |
cc61c64b | 21 | use hir::def_id::{DefId, CrateNum}; |
0531ce1d | 22 | use rustc_data_structures::sync::Lrc; |
54a0048b | 23 | use ty::{self, TyCtxt}; |
94b46f34 | 24 | use ty::query::Providers; |
1a4d82fc JJ |
25 | use middle::privacy; |
26 | use session::config; | |
476ff2be | 27 | use util::nodemap::{NodeSet, FxHashSet}; |
970d7e83 | 28 | |
83c7162d | 29 | use rustc_target::spec::abi::Abi; |
1a4d82fc | 30 | use syntax::ast; |
b039eaaf | 31 | use syntax::attr; |
54a0048b | 32 | use hir; |
cc61c64b | 33 | use hir::def_id::LOCAL_CRATE; |
476ff2be SL |
34 | use hir::intravisit::{Visitor, NestedVisitorMap}; |
35 | use hir::itemlikevisit::ItemLikeVisitor; | |
54a0048b | 36 | use hir::intravisit; |
970d7e83 | 37 | |
970d7e83 LB |
38 | // Returns true if the given set of generics implies that the item it's |
39 | // associated with must be inlined. | |
e9174d1e | 40 | fn generics_require_inlining(generics: &hir::Generics) -> bool { |
ff7c6d11 | 41 | generics.params.iter().any(|param| param.is_type_param()) |
970d7e83 LB |
42 | } |
43 | ||
44 | // Returns true if the given item must be inlined because it may be | |
45 | // monomorphized or it was marked with `#[inline]`. This will only return | |
46 | // true for functions. | |
94b46f34 | 47 | fn item_might_be_inlined(item: &hir::Item, attrs: CodegenFnAttrs) -> bool { |
0531ce1d | 48 | if attrs.requests_inline() { |
970d7e83 LB |
49 | return true |
50 | } | |
51 | ||
52 | match item.node { | |
7cac9316 | 53 | hir::ItemImpl(_, _, _, ref generics, ..) | |
9e0c209e | 54 | hir::ItemFn(.., ref generics, _) => { |
970d7e83 LB |
55 | generics_require_inlining(generics) |
56 | } | |
57 | _ => false, | |
58 | } | |
59 | } | |
60 | ||
a7813a04 | 61 | fn method_might_be_inlined<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
a7813a04 XL |
62 | impl_item: &hir::ImplItem, |
63 | impl_src: DefId) -> bool { | |
94b46f34 XL |
64 | let codegen_fn_attrs = tcx.codegen_fn_attrs(impl_item.hir_id.owner_def_id()); |
65 | if codegen_fn_attrs.requests_inline() || | |
abe05a73 | 66 | generics_require_inlining(&impl_item.generics) { |
1a4d82fc JJ |
67 | return true |
68 | } | |
32a655c1 SL |
69 | if let Some(impl_node_id) = tcx.hir.as_local_node_id(impl_src) { |
70 | match tcx.hir.find(impl_node_id) { | |
71 | Some(hir_map::NodeItem(item)) => | |
94b46f34 | 72 | item_might_be_inlined(&item, codegen_fn_attrs), |
b039eaaf | 73 | Some(..) | None => |
54a0048b | 74 | span_bug!(impl_item.span, "impl did is not an item") |
1a4d82fc JJ |
75 | } |
76 | } else { | |
54a0048b | 77 | span_bug!(impl_item.span, "found a foreign impl as a parent of a local method") |
970d7e83 | 78 | } |
970d7e83 LB |
79 | } |
80 | ||
81 | // Information needed while computing reachability. | |
1a4d82fc | 82 | struct ReachableContext<'a, 'tcx: 'a> { |
970d7e83 | 83 | // The type context. |
a7813a04 | 84 | tcx: TyCtxt<'a, 'tcx, 'tcx>, |
32a655c1 | 85 | tables: &'a ty::TypeckTables<'tcx>, |
970d7e83 | 86 | // The set of items which must be exported in the linkage sense. |
1a4d82fc | 87 | reachable_symbols: NodeSet, |
970d7e83 LB |
88 | // A worklist of item IDs. Each item ID in this worklist will be inlined |
89 | // and will be scanned for further references. | |
1a4d82fc JJ |
90 | worklist: Vec<ast::NodeId>, |
91 | // Whether any output of this compilation is a library | |
92 | any_library: bool, | |
970d7e83 LB |
93 | } |
94 | ||
476ff2be SL |
95 | impl<'a, 'tcx> Visitor<'tcx> for ReachableContext<'a, 'tcx> { |
96 | fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { | |
32a655c1 SL |
97 | NestedVisitorMap::None |
98 | } | |
99 | ||
100 | fn visit_nested_body(&mut self, body: hir::BodyId) { | |
101 | let old_tables = self.tables; | |
102 | self.tables = self.tcx.body_tables(body); | |
103 | let body = self.tcx.hir.body(body); | |
104 | self.visit_body(body); | |
105 | self.tables = old_tables; | |
476ff2be | 106 | } |
970d7e83 | 107 | |
476ff2be SL |
108 | fn visit_expr(&mut self, expr: &'tcx hir::Expr) { |
109 | let def = match expr.node { | |
110 | hir::ExprPath(ref qpath) => { | |
3b2f2976 | 111 | Some(self.tables.qpath_def(qpath, expr.hir_id)) |
1a4d82fc | 112 | } |
e9174d1e | 113 | hir::ExprMethodCall(..) => { |
3b2f2976 | 114 | Some(self.tables.type_dependent_defs()[expr.hir_id]) |
476ff2be SL |
115 | } |
116 | _ => None | |
117 | }; | |
118 | ||
ea8adc8c XL |
119 | match def { |
120 | Some(Def::Local(node_id)) | Some(Def::Upvar(node_id, ..)) => { | |
121 | self.reachable_symbols.insert(node_id); | |
122 | } | |
123 | Some(def) => { | |
124 | let def_id = def.def_id(); | |
125 | if let Some(node_id) = self.tcx.hir.as_local_node_id(def_id) { | |
126 | if self.def_id_represents_local_inlined_item(def_id) { | |
127 | self.worklist.push(node_id); | |
128 | } else { | |
129 | match def { | |
130 | // If this path leads to a constant, then we need to | |
131 | // recurse into the constant to continue finding | |
132 | // items that are reachable. | |
133 | Def::Const(..) | Def::AssociatedConst(..) => { | |
134 | self.worklist.push(node_id); | |
135 | } | |
92a42be0 | 136 | |
ea8adc8c XL |
137 | // If this wasn't a static, then the destination is |
138 | // surely reachable. | |
139 | _ => { | |
140 | self.reachable_symbols.insert(node_id); | |
141 | } | |
476ff2be | 142 | } |
970d7e83 | 143 | } |
970d7e83 | 144 | } |
1a4d82fc | 145 | } |
ea8adc8c | 146 | _ => {} |
1a4d82fc | 147 | } |
970d7e83 | 148 | |
92a42be0 | 149 | intravisit::walk_expr(self, expr) |
1a4d82fc JJ |
150 | } |
151 | } | |
970d7e83 | 152 | |
1a4d82fc | 153 | impl<'a, 'tcx> ReachableContext<'a, 'tcx> { |
970d7e83 LB |
154 | // Returns true if the given def ID represents a local item that is |
155 | // eligible for inlining and false otherwise. | |
e9174d1e | 156 | fn def_id_represents_local_inlined_item(&self, def_id: DefId) -> bool { |
32a655c1 | 157 | let node_id = match self.tcx.hir.as_local_node_id(def_id) { |
b039eaaf SL |
158 | Some(node_id) => node_id, |
159 | None => { return false; } | |
160 | }; | |
970d7e83 | 161 | |
32a655c1 SL |
162 | match self.tcx.hir.find(node_id) { |
163 | Some(hir_map::NodeItem(item)) => { | |
970d7e83 | 164 | match item.node { |
0531ce1d | 165 | hir::ItemFn(..) => |
94b46f34 | 166 | item_might_be_inlined(&item, self.tcx.codegen_fn_attrs(def_id)), |
970d7e83 LB |
167 | _ => false, |
168 | } | |
169 | } | |
32a655c1 | 170 | Some(hir_map::NodeTraitItem(trait_method)) => { |
c34b1796 | 171 | match trait_method.node { |
32a655c1 SL |
172 | hir::TraitItemKind::Const(_, ref default) => default.is_some(), |
173 | hir::TraitItemKind::Method(_, hir::TraitMethod::Provided(_)) => true, | |
174 | hir::TraitItemKind::Method(_, hir::TraitMethod::Required(_)) | | |
175 | hir::TraitItemKind::Type(..) => false, | |
970d7e83 LB |
176 | } |
177 | } | |
32a655c1 | 178 | Some(hir_map::NodeImplItem(impl_item)) => { |
c34b1796 | 179 | match impl_item.node { |
92a42be0 | 180 | hir::ImplItemKind::Const(..) => true, |
abe05a73 | 181 | hir::ImplItemKind::Method(..) => { |
94b46f34 | 182 | let attrs = self.tcx.codegen_fn_attrs(def_id); |
abe05a73 | 183 | if generics_require_inlining(&impl_item.generics) || |
0531ce1d | 184 | attrs.requests_inline() { |
1a4d82fc JJ |
185 | true |
186 | } else { | |
187 | let impl_did = self.tcx | |
32a655c1 | 188 | .hir |
1a4d82fc JJ |
189 | .get_parent_did(node_id); |
190 | // Check the impl. If the generics on the self | |
191 | // type of the impl require inlining, this method | |
192 | // does too. | |
32a655c1 SL |
193 | let impl_node_id = self.tcx.hir.as_local_node_id(impl_did).unwrap(); |
194 | match self.tcx.hir.expect_item(impl_node_id).node { | |
7cac9316 | 195 | hir::ItemImpl(_, _, _, ref generics, ..) => { |
970d7e83 LB |
196 | generics_require_inlining(generics) |
197 | } | |
198 | _ => false | |
199 | } | |
200 | } | |
970d7e83 | 201 | } |
92a42be0 | 202 | hir::ImplItemKind::Type(_) => false, |
970d7e83 LB |
203 | } |
204 | } | |
205 | Some(_) => false, | |
206 | None => false // This will happen for default methods. | |
207 | } | |
208 | } | |
209 | ||
1a4d82fc JJ |
210 | // Step 2: Mark all symbols that the symbols on the worklist touch. |
211 | fn propagate(&mut self) { | |
476ff2be | 212 | let mut scanned = FxHashSet(); |
0531ce1d | 213 | while let Some(search_item) = self.worklist.pop() { |
1a4d82fc JJ |
214 | if !scanned.insert(search_item) { |
215 | continue | |
216 | } | |
970d7e83 | 217 | |
32a655c1 | 218 | if let Some(ref item) = self.tcx.hir.find(search_item) { |
92a42be0 | 219 | self.propagate_node(item, search_item); |
1a4d82fc JJ |
220 | } |
221 | } | |
970d7e83 LB |
222 | } |
223 | ||
32a655c1 | 224 | fn propagate_node(&mut self, node: &hir_map::Node<'tcx>, |
1a4d82fc JJ |
225 | search_item: ast::NodeId) { |
226 | if !self.any_library { | |
7453a54e SL |
227 | // If we are building an executable, only explicitly extern |
228 | // types need to be exported. | |
32a655c1 | 229 | if let hir_map::NodeItem(item) = *node { |
9e0c209e | 230 | let reachable = if let hir::ItemFn(.., abi, _, _) = item.node { |
7453a54e SL |
231 | abi != Abi::Rust |
232 | } else { | |
233 | false | |
234 | }; | |
ea8adc8c | 235 | let def_id = self.tcx.hir.local_def_id(item.id); |
94b46f34 | 236 | let is_extern = self.tcx.codegen_fn_attrs(def_id).contains_extern_indicator(); |
7453a54e SL |
237 | if reachable || is_extern { |
238 | self.reachable_symbols.insert(search_item); | |
1a4d82fc | 239 | } |
970d7e83 | 240 | } |
1a4d82fc JJ |
241 | } else { |
242 | // If we are building a library, then reachable symbols will | |
243 | // continue to participate in linkage after this product is | |
244 | // produced. In this case, we traverse the ast node, recursing on | |
245 | // all reachable nodes from this one. | |
970d7e83 | 246 | self.reachable_symbols.insert(search_item); |
1a4d82fc | 247 | } |
970d7e83 | 248 | |
1a4d82fc | 249 | match *node { |
32a655c1 | 250 | hir_map::NodeItem(item) => { |
1a4d82fc | 251 | match item.node { |
476ff2be | 252 | hir::ItemFn(.., body) => { |
0531ce1d | 253 | let def_id = self.tcx.hir.local_def_id(item.id); |
94b46f34 | 254 | if item_might_be_inlined(&item, self.tcx.codegen_fn_attrs(def_id)) { |
32a655c1 | 255 | self.visit_nested_body(body); |
970d7e83 LB |
256 | } |
257 | } | |
1a4d82fc JJ |
258 | |
259 | // Reachable constants will be inlined into other crates | |
260 | // unconditionally, so we need to make sure that their | |
261 | // contents are also reachable. | |
32a655c1 SL |
262 | hir::ItemConst(_, init) => { |
263 | self.visit_nested_body(init); | |
1a4d82fc JJ |
264 | } |
265 | ||
266 | // These are normal, nothing reachable about these | |
267 | // inherently and their children are already in the | |
268 | // worklist, as determined by the privacy pass | |
476ff2be | 269 | hir::ItemExternCrate(_) | hir::ItemUse(..) | |
94b46f34 | 270 | hir::ItemExistential(..) | |
9e0c209e | 271 | hir::ItemTy(..) | hir::ItemStatic(..) | |
e9174d1e | 272 | hir::ItemMod(..) | hir::ItemForeignMod(..) | |
ff7c6d11 | 273 | hir::ItemImpl(..) | hir::ItemTrait(..) | hir::ItemTraitAlias(..) | |
e9174d1e | 274 | hir::ItemStruct(..) | hir::ItemEnum(..) | |
2c00a5a8 | 275 | hir::ItemUnion(..) | hir::ItemGlobalAsm(..) => {} |
970d7e83 | 276 | } |
1a4d82fc | 277 | } |
32a655c1 | 278 | hir_map::NodeTraitItem(trait_method) => { |
c34b1796 | 279 | match trait_method.node { |
32a655c1 SL |
280 | hir::TraitItemKind::Const(_, None) | |
281 | hir::TraitItemKind::Method(_, hir::TraitMethod::Required(_)) => { | |
1a4d82fc JJ |
282 | // Keep going, nothing to get exported |
283 | } | |
32a655c1 SL |
284 | hir::TraitItemKind::Const(_, Some(body_id)) | |
285 | hir::TraitItemKind::Method(_, hir::TraitMethod::Provided(body_id)) => { | |
286 | self.visit_nested_body(body_id); | |
d9579d0f | 287 | } |
32a655c1 | 288 | hir::TraitItemKind::Type(..) => {} |
970d7e83 | 289 | } |
1a4d82fc | 290 | } |
32a655c1 | 291 | hir_map::NodeImplItem(impl_item) => { |
c34b1796 | 292 | match impl_item.node { |
32a655c1 SL |
293 | hir::ImplItemKind::Const(_, body) => { |
294 | self.visit_nested_body(body); | |
d9579d0f | 295 | } |
abe05a73 | 296 | hir::ImplItemKind::Method(_, body) => { |
32a655c1 | 297 | let did = self.tcx.hir.get_parent_did(search_item); |
abe05a73 | 298 | if method_might_be_inlined(self.tcx, impl_item, did) { |
32a655c1 | 299 | self.visit_nested_body(body) |
1a4d82fc JJ |
300 | } |
301 | } | |
92a42be0 | 302 | hir::ImplItemKind::Type(_) => {} |
970d7e83 LB |
303 | } |
304 | } | |
ea8adc8c | 305 | hir_map::NodeExpr(&hir::Expr { node: hir::ExprClosure(.., body, _, _), .. }) => { |
3b2f2976 XL |
306 | self.visit_nested_body(body); |
307 | } | |
1a4d82fc | 308 | // Nothing to recurse on for these |
32a655c1 SL |
309 | hir_map::NodeForeignItem(_) | |
310 | hir_map::NodeVariant(_) | | |
311 | hir_map::NodeStructCtor(_) | | |
312 | hir_map::NodeField(_) | | |
ea8adc8c XL |
313 | hir_map::NodeTy(_) | |
314 | hir_map::NodeMacroDef(_) => {} | |
1a4d82fc | 315 | _ => { |
54a0048b | 316 | bug!("found unexpected thingy in worklist: {}", |
32a655c1 | 317 | self.tcx.hir.node_to_string(search_item)) |
1a4d82fc | 318 | } |
970d7e83 LB |
319 | } |
320 | } | |
92a42be0 | 321 | } |
970d7e83 | 322 | |
92a42be0 SL |
323 | // Some methods from non-exported (completely private) trait impls still have to be |
324 | // reachable if they are called from inlinable code. Generally, it's not known until | |
325 | // monomorphization if a specific trait impl item can be reachable or not. So, we | |
326 | // conservatively mark all of them as reachable. | |
327 | // FIXME: One possible strategy for pruning the reachable set is to avoid marking impl | |
328 | // items of non-exported traits (or maybe all local traits?) unless their respective | |
329 | // trait items are used from inlinable code through method call syntax or UFCS, or their | |
330 | // trait is a lang item. | |
476ff2be SL |
331 | struct CollectPrivateImplItemsVisitor<'a, 'tcx: 'a> { |
332 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
92a42be0 SL |
333 | access_levels: &'a privacy::AccessLevels, |
334 | worklist: &'a mut Vec<ast::NodeId>, | |
335 | } | |
336 | ||
476ff2be | 337 | impl<'a, 'tcx: 'a> ItemLikeVisitor<'tcx> for CollectPrivateImplItemsVisitor<'a, 'tcx> { |
92a42be0 | 338 | fn visit_item(&mut self, item: &hir::Item) { |
abe05a73 XL |
339 | // Anything which has custom linkage gets thrown on the worklist no |
340 | // matter where it is in the crate. | |
341 | if attr::contains_name(&item.attrs, "linkage") { | |
342 | self.worklist.push(item.id); | |
343 | } | |
344 | ||
92a42be0 | 345 | // We need only trait impls here, not inherent impls, and only non-exported ones |
476ff2be | 346 | if let hir::ItemImpl(.., Some(ref trait_ref), _, ref impl_item_refs) = item.node { |
92a42be0 | 347 | if !self.access_levels.is_reachable(item.id) { |
476ff2be SL |
348 | for impl_item_ref in impl_item_refs { |
349 | self.worklist.push(impl_item_ref.id.node_id); | |
350 | } | |
351 | ||
352 | let trait_def_id = match trait_ref.path.def { | |
353 | Def::Trait(def_id) => def_id, | |
354 | _ => unreachable!() | |
355 | }; | |
356 | ||
357 | if !trait_def_id.is_local() { | |
358 | return | |
359 | } | |
360 | ||
361 | for default_method in self.tcx.provided_trait_methods(trait_def_id) { | |
362 | let node_id = self.tcx | |
32a655c1 | 363 | .hir |
476ff2be SL |
364 | .as_local_node_id(default_method.def_id) |
365 | .unwrap(); | |
366 | self.worklist.push(node_id); | |
e9174d1e | 367 | } |
970d7e83 | 368 | } |
92a42be0 | 369 | } |
970d7e83 | 370 | } |
476ff2be | 371 | |
32a655c1 SL |
372 | fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem) {} |
373 | ||
476ff2be SL |
374 | fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem) { |
375 | // processed in visit_item above | |
376 | } | |
970d7e83 LB |
377 | } |
378 | ||
ea8adc8c XL |
379 | // We introduce a new-type here, so we can have a specialized HashStable |
380 | // implementation for it. | |
381 | #[derive(Clone)] | |
0531ce1d | 382 | pub struct ReachableSet(pub Lrc<NodeSet>); |
ea8adc8c | 383 | |
cc61c64b | 384 | |
ea8adc8c | 385 | fn reachable_set<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, crate_num: CrateNum) -> ReachableSet { |
cc61c64b XL |
386 | debug_assert!(crate_num == LOCAL_CRATE); |
387 | ||
7cac9316 | 388 | let access_levels = &tcx.privacy_access_levels(LOCAL_CRATE); |
92a42be0 | 389 | |
32a655c1 SL |
390 | let any_library = tcx.sess.crate_types.borrow().iter().any(|ty| { |
391 | *ty == config::CrateTypeRlib || *ty == config::CrateTypeDylib || | |
392 | *ty == config::CrateTypeProcMacro | |
393 | }); | |
394 | let mut reachable_context = ReachableContext { | |
041b39d2 | 395 | tcx, |
3b2f2976 | 396 | tables: &ty::TypeckTables::empty(None), |
32a655c1 SL |
397 | reachable_symbols: NodeSet(), |
398 | worklist: Vec::new(), | |
041b39d2 | 399 | any_library, |
32a655c1 | 400 | }; |
1a4d82fc JJ |
401 | |
402 | // Step 1: Seed the worklist with all nodes which were found to be public as | |
92a42be0 SL |
403 | // a result of the privacy pass along with all local lang items and impl items. |
404 | // If other crates link to us, they're going to expect to be able to | |
1a4d82fc JJ |
405 | // use the lang items, so we need to be sure to mark them as |
406 | // exported. | |
92a42be0 | 407 | for (id, _) in &access_levels.map { |
1a4d82fc JJ |
408 | reachable_context.worklist.push(*id); |
409 | } | |
ea8adc8c | 410 | for item in tcx.lang_items().items().iter() { |
92a42be0 | 411 | if let Some(did) = *item { |
32a655c1 | 412 | if let Some(node_id) = tcx.hir.as_local_node_id(did) { |
92a42be0 | 413 | reachable_context.worklist.push(node_id); |
1a4d82fc | 414 | } |
1a4d82fc JJ |
415 | } |
416 | } | |
92a42be0 SL |
417 | { |
418 | let mut collect_private_impl_items = CollectPrivateImplItemsVisitor { | |
041b39d2 XL |
419 | tcx, |
420 | access_levels, | |
92a42be0 SL |
421 | worklist: &mut reachable_context.worklist, |
422 | }; | |
32a655c1 | 423 | tcx.hir.krate().visit_all_item_likes(&mut collect_private_impl_items); |
92a42be0 | 424 | } |
970d7e83 LB |
425 | |
426 | // Step 2: Mark all symbols that the symbols on the worklist touch. | |
427 | reachable_context.propagate(); | |
428 | ||
970d7e83 | 429 | // Return the set of reachable symbols. |
0531ce1d | 430 | ReachableSet(Lrc::new(reachable_context.reachable_symbols)) |
cc61c64b XL |
431 | } |
432 | ||
433 | pub fn provide(providers: &mut Providers) { | |
434 | *providers = Providers { | |
435 | reachable_set, | |
436 | ..*providers | |
437 | }; | |
970d7e83 | 438 | } |