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