1 // Copyright 2012-2013 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.
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.
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
22 use util::nodemap::NodeSet;
24 use std::collections::HashSet;
28 use syntax::ast_util::is_local;
30 use syntax::visit::Visitor;
33 // Returns true if the given set of generics implies that the item it's
34 // associated with must be inlined.
35 fn generics_require_inlining(generics: &ast::Generics) -> bool {
36 !generics.ty_params.is_empty()
39 // Returns true if the given item must be inlined because it may be
40 // monomorphized or it was marked with `#[inline]`. This will only return
41 // true for functions.
42 fn item_might_be_inlined(item: &ast::Item) -> bool {
43 if attr::requests_inline(&item.attrs) {
48 ast::ItemImpl(_, _, ref generics, _, _, _) |
49 ast::ItemFn(_, _, _, ref generics, _) => {
50 generics_require_inlining(generics)
56 fn method_might_be_inlined(tcx: &ty::ctxt, sig: &ast::MethodSig,
57 impl_item: &ast::ImplItem,
58 impl_src: ast::DefId) -> bool {
59 if attr::requests_inline(&impl_item.attrs) ||
60 generics_require_inlining(&sig.generics) {
63 if is_local(impl_src) {
65 match tcx.map.find(impl_src.node) {
66 Some(ast_map::NodeItem(item)) => {
67 item_might_be_inlined(&*item)
70 tcx.sess.span_bug(impl_item.span, "impl did is not an item")
75 tcx.sess.span_bug(impl_item.span, "found a foreign impl as a parent \
80 // Information needed while computing reachability.
81 struct ReachableContext<'a, 'tcx: 'a> {
83 tcx: &'a ty::ctxt<'tcx>,
84 // The set of items which must be exported in the linkage sense.
85 reachable_symbols: NodeSet,
86 // A worklist of item IDs. Each item ID in this worklist will be inlined
87 // and will be scanned for further references.
88 worklist: Vec<ast::NodeId>,
89 // Whether any output of this compilation is a library
93 impl<'a, 'tcx, 'v> Visitor<'v> for ReachableContext<'a, 'tcx> {
95 fn visit_expr(&mut self, expr: &ast::Expr) {
98 ast::ExprPath(..) => {
99 let def = match self.tcx.def_map.borrow().get(&expr.id) {
100 Some(d) => d.full_def(),
102 self.tcx.sess.span_bug(expr.span,
103 "def ID not in def map?!")
107 let def_id = def.def_id();
108 if is_local(def_id) {
109 if self.def_id_represents_local_inlined_item(def_id) {
110 self.worklist.push(def_id.node)
113 // If this path leads to a constant, then we need to
114 // recurse into the constant to continue finding
115 // items that are reachable.
116 def::DefConst(..) | def::DefAssociatedConst(..) => {
117 self.worklist.push(def_id.node);
120 // If this wasn't a static, then the destination is
123 self.reachable_symbols.insert(def_id.node);
129 ast::ExprMethodCall(..) => {
130 let method_call = ty::MethodCall::expr(expr.id);
131 match (*self.tcx.method_map.borrow()).get(&method_call).unwrap().origin {
132 ty::MethodStatic(def_id) => {
133 if is_local(def_id) {
134 if self.def_id_represents_local_inlined_item(def_id) {
135 self.worklist.push(def_id.node)
137 self.reachable_symbols.insert(def_id.node);
146 visit::walk_expr(self, expr)
149 fn visit_item(&mut self, _item: &ast::Item) {
150 // Do not recurse into items. These items will be added to the worklist
151 // and recursed into manually if necessary.
155 impl<'a, 'tcx> ReachableContext<'a, 'tcx> {
156 // Creates a new reachability computation context.
157 fn new(tcx: &'a ty::ctxt<'tcx>) -> ReachableContext<'a, 'tcx> {
158 let any_library = tcx.sess.crate_types.borrow().iter().any(|ty| {
159 *ty != config::CrateTypeExecutable
163 reachable_symbols: NodeSet(),
164 worklist: Vec::new(),
165 any_library: any_library,
169 // Returns true if the given def ID represents a local item that is
170 // eligible for inlining and false otherwise.
171 fn def_id_represents_local_inlined_item(&self, def_id: ast::DefId) -> bool {
172 if def_id.krate != ast::LOCAL_CRATE {
176 let node_id = def_id.node;
177 match self.tcx.map.find(node_id) {
178 Some(ast_map::NodeItem(item)) => {
180 ast::ItemFn(..) => item_might_be_inlined(&*item),
184 Some(ast_map::NodeTraitItem(trait_method)) => {
185 match trait_method.node {
186 ast::ConstTraitItem(_, ref default) => default.is_some(),
187 ast::MethodTraitItem(_, ref body) => body.is_some(),
188 ast::TypeTraitItem(..) => false,
191 Some(ast_map::NodeImplItem(impl_item)) => {
192 match impl_item.node {
193 ast::ConstImplItem(..) => true,
194 ast::MethodImplItem(ref sig, _) => {
195 if generics_require_inlining(&sig.generics) ||
196 attr::requests_inline(&impl_item.attrs) {
199 let impl_did = self.tcx
201 .get_parent_did(node_id);
202 // Check the impl. If the generics on the self
203 // type of the impl require inlining, this method
205 assert!(impl_did.krate == ast::LOCAL_CRATE);
208 .expect_item(impl_did.node)
210 ast::ItemImpl(_, _, ref generics, _, _, _) => {
211 generics_require_inlining(generics)
217 ast::TypeImplItem(_) => false,
218 ast::MacImplItem(_) => self.tcx.sess.bug("unexpanded macro")
222 None => false // This will happen for default methods.
226 // Step 2: Mark all symbols that the symbols on the worklist touch.
227 fn propagate(&mut self) {
228 let mut scanned = HashSet::new();
230 let search_item = match self.worklist.pop() {
234 if !scanned.insert(search_item) {
238 match self.tcx.map.find(search_item) {
239 Some(ref item) => self.propagate_node(item, search_item),
240 None if search_item == ast::CRATE_NODE_ID => {}
242 self.tcx.sess.bug(&format!("found unmapped ID in worklist: \
250 fn propagate_node(&mut self, node: &ast_map::Node,
251 search_item: ast::NodeId) {
252 if !self.any_library {
253 // If we are building an executable, then there's no need to flag
254 // anything as external except for `extern fn` types. These
255 // functions may still participate in some form of native interface,
256 // but all other rust-only interfaces can be private (they will not
257 // participate in linkage after this product is produced)
258 if let ast_map::NodeItem(item) = *node {
259 if let ast::ItemFn(_, _, abi, _, _) = item.node {
260 if abi != abi::Rust {
261 self.reachable_symbols.insert(search_item);
266 // If we are building a library, then reachable symbols will
267 // continue to participate in linkage after this product is
268 // produced. In this case, we traverse the ast node, recursing on
269 // all reachable nodes from this one.
270 self.reachable_symbols.insert(search_item);
274 ast_map::NodeItem(item) => {
276 ast::ItemFn(_, _, _, _, ref search_block) => {
277 if item_might_be_inlined(&*item) {
278 visit::walk_block(self, &**search_block)
282 // Reachable constants will be inlined into other crates
283 // unconditionally, so we need to make sure that their
284 // contents are also reachable.
285 ast::ItemConst(_, ref init) => {
286 self.visit_expr(&**init);
289 // These are normal, nothing reachable about these
290 // inherently and their children are already in the
291 // worklist, as determined by the privacy pass
292 ast::ItemExternCrate(_) | ast::ItemUse(_) |
293 ast::ItemTy(..) | ast::ItemStatic(_, _, _) |
294 ast::ItemMod(..) | ast::ItemForeignMod(..) |
295 ast::ItemImpl(..) | ast::ItemTrait(..) |
296 ast::ItemStruct(..) | ast::ItemEnum(..) |
297 ast::ItemDefaultImpl(..) => {}
300 self.tcx.sess.span_bug(item.span,
301 "found non-function item \
306 ast_map::NodeTraitItem(trait_method) => {
307 match trait_method.node {
308 ast::ConstTraitItem(_, None) |
309 ast::MethodTraitItem(_, None) => {
310 // Keep going, nothing to get exported
312 ast::ConstTraitItem(_, Some(ref expr)) => {
313 self.visit_expr(&*expr);
315 ast::MethodTraitItem(_, Some(ref body)) => {
316 visit::walk_block(self, body);
318 ast::TypeTraitItem(..) => {}
321 ast_map::NodeImplItem(impl_item) => {
322 match impl_item.node {
323 ast::ConstImplItem(_, ref expr) => {
324 self.visit_expr(&*expr);
326 ast::MethodImplItem(ref sig, ref body) => {
327 let did = self.tcx.map.get_parent_did(search_item);
328 if method_might_be_inlined(self.tcx, sig, impl_item, did) {
329 visit::walk_block(self, body)
332 ast::TypeImplItem(_) => {}
333 ast::MacImplItem(_) => self.tcx.sess.bug("unexpanded macro")
336 // Nothing to recurse on for these
337 ast_map::NodeForeignItem(_) |
338 ast_map::NodeVariant(_) |
339 ast_map::NodeStructCtor(_) => {}
343 .bug(&format!("found unexpected thingy in worklist: {}",
346 .node_to_string(search_item)))
351 // Step 3: Mark all destructors as reachable.
353 // FIXME(pcwalton): This is a conservative overapproximation, but fixing
354 // this properly would result in the necessity of computing *type*
355 // reachability, which might result in a compile time loss.
356 fn mark_destructors_reachable(&mut self) {
357 for (_, destructor_def_id) in &*self.tcx.destructor_for_type.borrow() {
358 if destructor_def_id.krate == ast::LOCAL_CRATE {
359 self.reachable_symbols.insert(destructor_def_id.node);
365 pub fn find_reachable(tcx: &ty::ctxt,
366 exported_items: &privacy::ExportedItems)
368 let mut reachable_context = ReachableContext::new(tcx);
370 // Step 1: Seed the worklist with all nodes which were found to be public as
371 // a result of the privacy pass along with all local lang items. If
372 // other crates link to us, they're going to expect to be able to
373 // use the lang items, so we need to be sure to mark them as
375 for id in exported_items {
376 reachable_context.worklist.push(*id);
378 for (_, item) in tcx.lang_items.items() {
380 Some(did) if is_local(did) => {
381 reachable_context.worklist.push(did.node);
387 // Step 2: Mark all symbols that the symbols on the worklist touch.
388 reachable_context.propagate();
390 // Step 3: Mark all destructors as reachable.
391 reachable_context.mark_destructors_reachable();
393 // Return the set of reachable symbols.
394 reachable_context.reachable_symbols