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