]>
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 | ||
e9174d1e | 18 | use front::map as ast_map; |
1a4d82fc | 19 | use middle::def; |
b039eaaf | 20 | use middle::def_id::DefId; |
970d7e83 | 21 | use middle::ty; |
1a4d82fc JJ |
22 | use middle::privacy; |
23 | use session::config; | |
24 | use util::nodemap::NodeSet; | |
970d7e83 | 25 | |
1a4d82fc JJ |
26 | use std::collections::HashSet; |
27 | use syntax::abi; | |
28 | use syntax::ast; | |
b039eaaf | 29 | use syntax::attr; |
e9174d1e | 30 | use rustc_front::hir; |
92a42be0 SL |
31 | use rustc_front::intravisit::Visitor; |
32 | use rustc_front::intravisit; | |
970d7e83 | 33 | |
970d7e83 LB |
34 | // Returns true if the given set of generics implies that the item it's |
35 | // associated with must be inlined. | |
e9174d1e | 36 | fn generics_require_inlining(generics: &hir::Generics) -> bool { |
970d7e83 LB |
37 | !generics.ty_params.is_empty() |
38 | } | |
39 | ||
40 | // Returns true if the given item must be inlined because it may be | |
41 | // monomorphized or it was marked with `#[inline]`. This will only return | |
42 | // true for functions. | |
e9174d1e | 43 | fn item_might_be_inlined(item: &hir::Item) -> bool { |
c34b1796 | 44 | if attr::requests_inline(&item.attrs) { |
970d7e83 LB |
45 | return true |
46 | } | |
47 | ||
48 | match item.node { | |
e9174d1e SL |
49 | hir::ItemImpl(_, _, ref generics, _, _, _) | |
50 | hir::ItemFn(_, _, _, _, ref generics, _) => { | |
970d7e83 LB |
51 | generics_require_inlining(generics) |
52 | } | |
53 | _ => false, | |
54 | } | |
55 | } | |
56 | ||
e9174d1e SL |
57 | fn method_might_be_inlined(tcx: &ty::ctxt, sig: &hir::MethodSig, |
58 | impl_item: &hir::ImplItem, | |
59 | impl_src: DefId) -> bool { | |
c34b1796 AL |
60 | if attr::requests_inline(&impl_item.attrs) || |
61 | generics_require_inlining(&sig.generics) { | |
1a4d82fc JJ |
62 | return true |
63 | } | |
b039eaaf SL |
64 | if let Some(impl_node_id) = tcx.map.as_local_node_id(impl_src) { |
65 | match tcx.map.find(impl_node_id) { | |
66 | Some(ast_map::NodeItem(item)) => | |
67 | item_might_be_inlined(&*item), | |
68 | Some(..) | None => | |
69 | tcx.sess.span_bug(impl_item.span, "impl did is not an item") | |
1a4d82fc JJ |
70 | } |
71 | } else { | |
b039eaaf | 72 | tcx.sess.span_bug(impl_item.span, "found a foreign impl as a parent of a local method") |
970d7e83 | 73 | } |
970d7e83 LB |
74 | } |
75 | ||
76 | // Information needed while computing reachability. | |
1a4d82fc | 77 | struct ReachableContext<'a, 'tcx: 'a> { |
970d7e83 | 78 | // The type context. |
1a4d82fc | 79 | tcx: &'a ty::ctxt<'tcx>, |
970d7e83 | 80 | // The set of items which must be exported in the linkage sense. |
1a4d82fc | 81 | reachable_symbols: NodeSet, |
970d7e83 LB |
82 | // A worklist of item IDs. Each item ID in this worklist will be inlined |
83 | // and will be scanned for further references. | |
1a4d82fc JJ |
84 | worklist: Vec<ast::NodeId>, |
85 | // Whether any output of this compilation is a library | |
86 | any_library: bool, | |
970d7e83 LB |
87 | } |
88 | ||
1a4d82fc | 89 | impl<'a, 'tcx, 'v> Visitor<'v> for ReachableContext<'a, 'tcx> { |
e9174d1e | 90 | fn visit_expr(&mut self, expr: &hir::Expr) { |
1a4d82fc | 91 | match expr.node { |
e9174d1e | 92 | hir::ExprPath(..) => { |
1a4d82fc | 93 | let def = match self.tcx.def_map.borrow().get(&expr.id) { |
c34b1796 | 94 | Some(d) => d.full_def(), |
1a4d82fc JJ |
95 | None => { |
96 | self.tcx.sess.span_bug(expr.span, | |
97 | "def ID not in def map?!") | |
970d7e83 | 98 | } |
1a4d82fc JJ |
99 | }; |
100 | ||
101 | let def_id = def.def_id(); | |
b039eaaf | 102 | if let Some(node_id) = self.tcx.map.as_local_node_id(def_id) { |
1a4d82fc | 103 | if self.def_id_represents_local_inlined_item(def_id) { |
b039eaaf | 104 | self.worklist.push(node_id); |
1a4d82fc JJ |
105 | } else { |
106 | match def { | |
107 | // If this path leads to a constant, then we need to | |
108 | // recurse into the constant to continue finding | |
109 | // items that are reachable. | |
d9579d0f | 110 | def::DefConst(..) | def::DefAssociatedConst(..) => { |
b039eaaf | 111 | self.worklist.push(node_id); |
970d7e83 | 112 | } |
970d7e83 | 113 | |
1a4d82fc JJ |
114 | // If this wasn't a static, then the destination is |
115 | // surely reachable. | |
116 | _ => { | |
b039eaaf | 117 | self.reachable_symbols.insert(node_id); |
970d7e83 LB |
118 | } |
119 | } | |
120 | } | |
1a4d82fc JJ |
121 | } |
122 | } | |
e9174d1e | 123 | hir::ExprMethodCall(..) => { |
1a4d82fc | 124 | let method_call = ty::MethodCall::expr(expr.id); |
c1a9b12d | 125 | let def_id = self.tcx.tables.borrow().method_map[&method_call].def_id; |
92a42be0 SL |
126 | |
127 | // Mark the trait item (and, possibly, its default impl) as reachable | |
128 | // Or mark inherent impl item as reachable | |
129 | if let Some(node_id) = self.tcx.map.as_local_node_id(def_id) { | |
130 | if self.def_id_represents_local_inlined_item(def_id) { | |
131 | self.worklist.push(node_id) | |
970d7e83 | 132 | } |
92a42be0 | 133 | self.reachable_symbols.insert(node_id); |
970d7e83 | 134 | } |
1a4d82fc JJ |
135 | } |
136 | _ => {} | |
137 | } | |
970d7e83 | 138 | |
92a42be0 | 139 | intravisit::walk_expr(self, expr) |
1a4d82fc JJ |
140 | } |
141 | } | |
970d7e83 | 142 | |
1a4d82fc JJ |
143 | impl<'a, 'tcx> ReachableContext<'a, 'tcx> { |
144 | // Creates a new reachability computation context. | |
145 | fn new(tcx: &'a ty::ctxt<'tcx>) -> ReachableContext<'a, 'tcx> { | |
146 | let any_library = tcx.sess.crate_types.borrow().iter().any(|ty| { | |
147 | *ty != config::CrateTypeExecutable | |
148 | }); | |
149 | ReachableContext { | |
150 | tcx: tcx, | |
85aaf69f | 151 | reachable_symbols: NodeSet(), |
1a4d82fc JJ |
152 | worklist: Vec::new(), |
153 | any_library: any_library, | |
154 | } | |
970d7e83 LB |
155 | } |
156 | ||
157 | // Returns true if the given def ID represents a local item that is | |
158 | // eligible for inlining and false otherwise. | |
e9174d1e | 159 | fn def_id_represents_local_inlined_item(&self, def_id: DefId) -> bool { |
b039eaaf SL |
160 | let node_id = match self.tcx.map.as_local_node_id(def_id) { |
161 | Some(node_id) => node_id, | |
162 | None => { return false; } | |
163 | }; | |
970d7e83 | 164 | |
1a4d82fc JJ |
165 | match self.tcx.map.find(node_id) { |
166 | Some(ast_map::NodeItem(item)) => { | |
970d7e83 | 167 | match item.node { |
e9174d1e | 168 | hir::ItemFn(..) => item_might_be_inlined(&*item), |
970d7e83 LB |
169 | _ => false, |
170 | } | |
171 | } | |
1a4d82fc | 172 | Some(ast_map::NodeTraitItem(trait_method)) => { |
c34b1796 | 173 | match trait_method.node { |
e9174d1e SL |
174 | hir::ConstTraitItem(_, ref default) => default.is_some(), |
175 | hir::MethodTraitItem(_, ref body) => body.is_some(), | |
176 | hir::TypeTraitItem(..) => false, | |
970d7e83 LB |
177 | } |
178 | } | |
1a4d82fc | 179 | Some(ast_map::NodeImplItem(impl_item)) => { |
c34b1796 | 180 | match impl_item.node { |
92a42be0 SL |
181 | hir::ImplItemKind::Const(..) => true, |
182 | hir::ImplItemKind::Method(ref sig, _) => { | |
c34b1796 AL |
183 | if generics_require_inlining(&sig.generics) || |
184 | attr::requests_inline(&impl_item.attrs) { | |
1a4d82fc JJ |
185 | true |
186 | } else { | |
187 | let impl_did = self.tcx | |
188 | .map | |
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. | |
b039eaaf SL |
193 | let impl_node_id = self.tcx.map.as_local_node_id(impl_did).unwrap(); |
194 | match self.tcx.map.expect_item(impl_node_id).node { | |
e9174d1e | 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) { | |
212 | let mut scanned = HashSet::new(); | |
213 | loop { | |
214 | let search_item = match self.worklist.pop() { | |
215 | Some(item) => item, | |
216 | None => break, | |
217 | }; | |
218 | if !scanned.insert(search_item) { | |
219 | continue | |
220 | } | |
970d7e83 | 221 | |
92a42be0 SL |
222 | if let Some(ref item) = self.tcx.map.find(search_item) { |
223 | self.propagate_node(item, search_item); | |
1a4d82fc JJ |
224 | } |
225 | } | |
970d7e83 LB |
226 | } |
227 | ||
1a4d82fc JJ |
228 | fn propagate_node(&mut self, node: &ast_map::Node, |
229 | search_item: ast::NodeId) { | |
230 | if !self.any_library { | |
231 | // If we are building an executable, then there's no need to flag | |
232 | // anything as external except for `extern fn` types. These | |
233 | // functions may still participate in some form of native interface, | |
234 | // but all other rust-only interfaces can be private (they will not | |
235 | // participate in linkage after this product is produced) | |
236 | if let ast_map::NodeItem(item) = *node { | |
e9174d1e | 237 | if let hir::ItemFn(_, _, _, abi, _, _) = item.node { |
1a4d82fc JJ |
238 | if abi != abi::Rust { |
239 | self.reachable_symbols.insert(search_item); | |
240 | } | |
241 | } | |
970d7e83 | 242 | } |
1a4d82fc JJ |
243 | } else { |
244 | // If we are building a library, then reachable symbols will | |
245 | // continue to participate in linkage after this product is | |
246 | // produced. In this case, we traverse the ast node, recursing on | |
247 | // all reachable nodes from this one. | |
970d7e83 | 248 | self.reachable_symbols.insert(search_item); |
1a4d82fc | 249 | } |
970d7e83 | 250 | |
1a4d82fc JJ |
251 | match *node { |
252 | ast_map::NodeItem(item) => { | |
253 | match item.node { | |
e9174d1e | 254 | hir::ItemFn(_, _, _, _, _, ref search_block) => { |
1a4d82fc | 255 | if item_might_be_inlined(&*item) { |
92a42be0 | 256 | intravisit::walk_block(self, &**search_block) |
970d7e83 LB |
257 | } |
258 | } | |
1a4d82fc JJ |
259 | |
260 | // Reachable constants will be inlined into other crates | |
261 | // unconditionally, so we need to make sure that their | |
262 | // contents are also reachable. | |
e9174d1e | 263 | hir::ItemConst(_, ref init) => { |
1a4d82fc JJ |
264 | self.visit_expr(&**init); |
265 | } | |
266 | ||
267 | // These are normal, nothing reachable about these | |
268 | // inherently and their children are already in the | |
269 | // worklist, as determined by the privacy pass | |
e9174d1e SL |
270 | hir::ItemExternCrate(_) | hir::ItemUse(_) | |
271 | hir::ItemTy(..) | hir::ItemStatic(_, _, _) | | |
272 | hir::ItemMod(..) | hir::ItemForeignMod(..) | | |
273 | hir::ItemImpl(..) | hir::ItemTrait(..) | | |
274 | hir::ItemStruct(..) | hir::ItemEnum(..) | | |
275 | hir::ItemDefaultImpl(..) => {} | |
970d7e83 | 276 | } |
1a4d82fc JJ |
277 | } |
278 | ast_map::NodeTraitItem(trait_method) => { | |
c34b1796 | 279 | match trait_method.node { |
e9174d1e SL |
280 | hir::ConstTraitItem(_, None) | |
281 | hir::MethodTraitItem(_, None) => { | |
1a4d82fc JJ |
282 | // Keep going, nothing to get exported |
283 | } | |
e9174d1e | 284 | hir::ConstTraitItem(_, Some(ref expr)) => { |
d9579d0f AL |
285 | self.visit_expr(&*expr); |
286 | } | |
e9174d1e | 287 | hir::MethodTraitItem(_, Some(ref body)) => { |
92a42be0 | 288 | intravisit::walk_block(self, body); |
1a4d82fc | 289 | } |
e9174d1e | 290 | hir::TypeTraitItem(..) => {} |
970d7e83 | 291 | } |
1a4d82fc JJ |
292 | } |
293 | ast_map::NodeImplItem(impl_item) => { | |
c34b1796 | 294 | match impl_item.node { |
92a42be0 | 295 | hir::ImplItemKind::Const(_, ref expr) => { |
d9579d0f AL |
296 | self.visit_expr(&*expr); |
297 | } | |
92a42be0 | 298 | hir::ImplItemKind::Method(ref sig, ref body) => { |
1a4d82fc | 299 | let did = self.tcx.map.get_parent_did(search_item); |
c34b1796 | 300 | if method_might_be_inlined(self.tcx, sig, impl_item, did) { |
92a42be0 | 301 | intravisit::walk_block(self, body) |
1a4d82fc JJ |
302 | } |
303 | } | |
92a42be0 | 304 | hir::ImplItemKind::Type(_) => {} |
970d7e83 LB |
305 | } |
306 | } | |
1a4d82fc JJ |
307 | // Nothing to recurse on for these |
308 | ast_map::NodeForeignItem(_) | | |
309 | ast_map::NodeVariant(_) | | |
310 | ast_map::NodeStructCtor(_) => {} | |
311 | _ => { | |
312 | self.tcx | |
313 | .sess | |
314 | .bug(&format!("found unexpected thingy in worklist: {}", | |
315 | self.tcx | |
316 | .map | |
c34b1796 | 317 | .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. | |
331 | struct CollectPrivateImplItemsVisitor<'a> { | |
332 | access_levels: &'a privacy::AccessLevels, | |
333 | worklist: &'a mut Vec<ast::NodeId>, | |
334 | } | |
335 | ||
336 | impl<'a, 'v> Visitor<'v> for CollectPrivateImplItemsVisitor<'a> { | |
337 | fn visit_item(&mut self, item: &hir::Item) { | |
338 | // We need only trait impls here, not inherent impls, and only non-exported ones | |
339 | if let hir::ItemImpl(_, _, _, Some(_), _, ref impl_items) = item.node { | |
340 | if !self.access_levels.is_reachable(item.id) { | |
341 | for impl_item in impl_items { | |
342 | self.worklist.push(impl_item.id); | |
e9174d1e | 343 | } |
970d7e83 | 344 | } |
92a42be0 | 345 | } |
970d7e83 LB |
346 | } |
347 | } | |
348 | ||
1a4d82fc | 349 | pub fn find_reachable(tcx: &ty::ctxt, |
92a42be0 | 350 | access_levels: &privacy::AccessLevels) |
1a4d82fc | 351 | -> NodeSet { |
92a42be0 | 352 | |
1a4d82fc JJ |
353 | let mut reachable_context = ReachableContext::new(tcx); |
354 | ||
355 | // Step 1: Seed the worklist with all nodes which were found to be public as | |
92a42be0 SL |
356 | // a result of the privacy pass along with all local lang items and impl items. |
357 | // If other crates link to us, they're going to expect to be able to | |
1a4d82fc JJ |
358 | // use the lang items, so we need to be sure to mark them as |
359 | // exported. | |
92a42be0 | 360 | for (id, _) in &access_levels.map { |
1a4d82fc JJ |
361 | reachable_context.worklist.push(*id); |
362 | } | |
363 | for (_, item) in tcx.lang_items.items() { | |
92a42be0 SL |
364 | if let Some(did) = *item { |
365 | if let Some(node_id) = tcx.map.as_local_node_id(did) { | |
366 | reachable_context.worklist.push(node_id); | |
1a4d82fc | 367 | } |
1a4d82fc JJ |
368 | } |
369 | } | |
92a42be0 SL |
370 | { |
371 | let mut collect_private_impl_items = CollectPrivateImplItemsVisitor { | |
372 | access_levels: access_levels, | |
373 | worklist: &mut reachable_context.worklist, | |
374 | }; | |
375 | tcx.map.krate().visit_all_items(&mut collect_private_impl_items); | |
376 | } | |
970d7e83 LB |
377 | |
378 | // Step 2: Mark all symbols that the symbols on the worklist touch. | |
379 | reachable_context.propagate(); | |
380 | ||
970d7e83 LB |
381 | // Return the set of reachable symbols. |
382 | reachable_context.reachable_symbols | |
383 | } |