src/librustc/middle/reachable.rs

   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.
   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
  18 use ast_map;
  19 use middle::def;
  20 use middle::ty;
  21 use middle::privacy;
  22 use session::config;
  23 use util::nodemap::NodeSet;
  24
  25 use std::collections::HashSet;
  26 use syntax::abi;
  27 use syntax::ast;
  28 use syntax::ast_util::is_local;
  29 use syntax::attr;
  30 use syntax::visit::Visitor;
  31 use syntax::visit;
  32
  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()
  37 }
  38
  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) {
  44         return true
  45     }
  46
  47     match item.node {
  48         ast::ItemImpl(_, _, ref generics, _, _, _) |
  49         ast::ItemFn(_, _, _, _, ref generics, _) => {
  50             generics_require_inlining(generics)
  51         }
  52         _ => false,
  53     }
  54 }
  55
  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) {
  61         return true
  62     }
  63     if is_local(impl_src) {
  64         {
  65             match tcx.map.find(impl_src.node) {
  66                 Some(ast_map::NodeItem(item)) => {
  67                     item_might_be_inlined(&*item)
  68                 }
  69                 Some(..) | None => {
  70                     tcx.sess.span_bug(impl_item.span, "impl did is not an item")
  71                 }
  72             }
  73         }
  74     } else {
  75         tcx.sess.span_bug(impl_item.span, "found a foreign impl as a parent \
  76                                            of a local method")
  77     }
  78 }
  79
  80 // Information needed while computing reachability.
  81 struct ReachableContext<'a, 'tcx: 'a> {
  82     // The type context.
  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
  90     any_library: bool,
  91 }
  92
  93 impl<'a, 'tcx, 'v> Visitor<'v> for ReachableContext<'a, 'tcx> {
  94
  95     fn visit_expr(&mut self, expr: &ast::Expr) {
  96
  97         match expr.node {
  98             ast::ExprPath(..) => {
  99                 let def = match self.tcx.def_map.borrow().get(&expr.id) {
 100                     Some(d) => d.full_def(),
 101                     None => {
 102                         self.tcx.sess.span_bug(expr.span,
 103                                                "def ID not in def map?!")
 104                     }
 105                 };
 106
 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)
 111                     } else {
 112                         match def {
 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);
 118                             }
 119
 120                             // If this wasn't a static, then the destination is
 121                             // surely reachable.
 122                             _ => {
 123                                 self.reachable_symbols.insert(def_id.node);
 124                             }
 125                         }
 126                     }
 127                 }
 128             }
 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)
 136                             }
 137                             self.reachable_symbols.insert(def_id.node);
 138                         }
 139                     }
 140                     _ => {}
 141                 }
 142             }
 143             _ => {}
 144         }
 145
 146         visit::walk_expr(self, expr)
 147     }
 148
 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.
 152     }
 153 }
 154
 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
 160         });
 161         ReachableContext {
 162             tcx: tcx,
 163             reachable_symbols: NodeSet(),
 164             worklist: Vec::new(),
 165             any_library: any_library,
 166         }
 167     }
 168
 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 {
 173             return false
 174         }
 175
 176         let node_id = def_id.node;
 177         match self.tcx.map.find(node_id) {
 178             Some(ast_map::NodeItem(item)) => {
 179                 match item.node {
 180                     ast::ItemFn(..) => item_might_be_inlined(&*item),
 181                     _ => false,
 182                 }
 183             }
 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,
 189                 }
 190             }
 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) {
 197                             true
 198                         } else {
 199                             let impl_did = self.tcx
 200                                                .map
 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
 204                             // does too.
 205                             assert!(impl_did.krate == ast::LOCAL_CRATE);
 206                             match self.tcx
 207                                       .map
 208                                       .expect_item(impl_did.node)
 209                                       .node {
 210                                 ast::ItemImpl(_, _, ref generics, _, _, _) => {
 211                                     generics_require_inlining(generics)
 212                                 }
 213                                 _ => false
 214                             }
 215                         }
 216                     }
 217                     ast::TypeImplItem(_) => false,
 218                     ast::MacImplItem(_) => self.tcx.sess.bug("unexpanded macro")
 219                 }
 220             }
 221             Some(_) => false,
 222             None => false   // This will happen for default methods.
 223         }
 224     }
 225
 226     // Step 2: Mark all symbols that the symbols on the worklist touch.
 227     fn propagate(&mut self) {
 228         let mut scanned = HashSet::new();
 229         loop {
 230             let search_item = match self.worklist.pop() {
 231                 Some(item) => item,
 232                 None => break,
 233             };
 234             if !scanned.insert(search_item) {
 235                 continue
 236             }
 237
 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 => {}
 241                 None => {
 242                     self.tcx.sess.bug(&format!("found unmapped ID in worklist: \
 243                                                {}",
 244                                               search_item))
 245                 }
 246             }
 247         }
 248     }
 249
 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);
 262                     }
 263                 }
 264             }
 265         } else {
 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);
 271         }
 272
 273         match *node {
 274             ast_map::NodeItem(item) => {
 275                 match item.node {
 276                     ast::ItemFn(_, _, _, _, _, ref search_block) => {
 277                         if item_might_be_inlined(&*item) {
 278                             visit::walk_block(self, &**search_block)
 279                         }
 280                     }
 281
 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);
 287                     }
 288
 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(..) => {}
 298
 299                     _ => {
 300                         self.tcx.sess.span_bug(item.span,
 301                                                "found non-function item \
 302                                                 in worklist?!")
 303                     }
 304                 }
 305             }
 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
 311                     }
 312                     ast::ConstTraitItem(_, Some(ref expr)) => {
 313                         self.visit_expr(&*expr);
 314                     }
 315                     ast::MethodTraitItem(_, Some(ref body)) => {
 316                         visit::walk_block(self, body);
 317                     }
 318                     ast::TypeTraitItem(..) => {}
 319                 }
 320             }
 321             ast_map::NodeImplItem(impl_item) => {
 322                 match impl_item.node {
 323                     ast::ConstImplItem(_, ref expr) => {
 324                         self.visit_expr(&*expr);
 325                     }
 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)
 330                         }
 331                     }
 332                     ast::TypeImplItem(_) => {}
 333                     ast::MacImplItem(_) => self.tcx.sess.bug("unexpanded macro")
 334                 }
 335             }
 336             // Nothing to recurse on for these
 337             ast_map::NodeForeignItem(_) |
 338             ast_map::NodeVariant(_) |
 339             ast_map::NodeStructCtor(_) => {}
 340             _ => {
 341                 self.tcx
 342                     .sess
 343                     .bug(&format!("found unexpected thingy in worklist: {}",
 344                                  self.tcx
 345                                      .map
 346                                      .node_to_string(search_item)))
 347             }
 348         }
 349     }
 350
 351     // Step 3: Mark all destructors as reachable.
 352     //
 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().iter() {
 358             if destructor_def_id.krate == ast::LOCAL_CRATE {
 359                 self.reachable_symbols.insert(destructor_def_id.node);
 360             }
 361         }
 362     }
 363 }
 364
 365 pub fn find_reachable(tcx: &ty::ctxt,
 366                       exported_items: &privacy::ExportedItems)
 367                       -> NodeSet {
 368     let mut reachable_context = ReachableContext::new(tcx);
 369
 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
 374     //         exported.
 375     for id in exported_items {
 376         reachable_context.worklist.push(*id);
 377     }
 378     for (_, item) in tcx.lang_items.items() {
 379         match *item {
 380             Some(did) if is_local(did) => {
 381                 reachable_context.worklist.push(did.node);
 382             }
 383             _ => {}
 384         }
 385     }
 386
 387     // Step 2: Mark all symbols that the symbols on the worklist touch.
 388     reachable_context.propagate();
 389
 390     // Step 3: Mark all destructors as reachable.
 391     reachable_context.mark_destructors_reachable();
 392
 393     // Return the set of reachable symbols.
 394     reachable_context.reachable_symbols
 395 }