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, 'tcx: 'a> {
  93     // The type context.
  94     tcx: &'a ty::ctxt<'tcx>,
  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, 'tcx> Visitor<()> for ReachableContext<'a, 'tcx> {
 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, 'tcx> ReachableContext<'a, 'tcx> {
 168     // Creates a new reachability computation context.
 169     fn new(tcx: &'a ty::ctxt<'tcx>) -> ReachableContext<'a, 'tcx> {
 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::NodeTraitItem(trait_method)) => {
 197                 match *trait_method {
 198                     ast::RequiredMethod(_) => false,
 199                     ast::ProvidedMethod(_) => true,
 200                 }
 201             }
 202             Some(ast_map::NodeImplItem(impl_item)) => {
 203                 match *impl_item {
 204                     ast::MethodImplItem(method) => {
 205                         if generics_require_inlining(method.pe_generics()) ||
 206                                 attributes_specify_inlining(
 207                                     method.attrs.as_slice()) {
 208                             true
 209                         } else {
 210                             let impl_did = self.tcx
 211                                                .map
 212                                                .get_parent_did(node_id);
 213                             // Check the impl. If the generics on the self
 214                             // type of the impl require inlining, this method
 215                             // does too.
 216                             assert!(impl_did.krate == ast::LOCAL_CRATE);
 217                             match self.tcx
 218                                       .map
 219                                       .expect_item(impl_did.node)
 220                                       .node {
 221                                 ast::ItemImpl(ref generics, _, _, _) => {
 222                                     generics_require_inlining(generics)
 223                                 }
 224                                 _ => false
 225                             }
 226                         }
 227                     }
 228                 }
 229             }
 230             Some(_) => false,
 231             None => false   // This will happen for default methods.
 232         }
 233     }
 234
 235     // Step 2: Mark all symbols that the symbols on the worklist touch.
 236     fn propagate(&mut self) {
 237         let mut scanned = HashSet::new();
 238         loop {
 239             if self.worklist.len() == 0 {
 240                 break
 241             }
 242             let search_item = self.worklist.pop().unwrap();
 243             if scanned.contains(&search_item) {
 244                 continue
 245             }
 246
 247             scanned.insert(search_item);
 248             match self.tcx.map.find(search_item) {
 249                 Some(ref item) => self.propagate_node(item, search_item),
 250                 None if search_item == ast::CRATE_NODE_ID => {}
 251                 None => {
 252                     self.tcx.sess.bug(format!("found unmapped ID in worklist: \
 253                                                {}",
 254                                               search_item).as_slice())
 255                 }
 256             }
 257         }
 258     }
 259
 260     fn propagate_node(&mut self, node: &ast_map::Node,
 261                       search_item: ast::NodeId) {
 262         if !self.any_library {
 263             // If we are building an executable, then there's no need to flag
 264             // anything as external except for `extern fn` types. These
 265             // functions may still participate in some form of native interface,
 266             // but all other rust-only interfaces can be private (they will not
 267             // participate in linkage after this product is produced)
 268             match *node {
 269                 ast_map::NodeItem(item) => {
 270                     match item.node {
 271                         ast::ItemFn(_, _, abi, _, _) => {
 272                             if abi != abi::Rust {
 273                                 self.reachable_symbols.insert(search_item);
 274                             }
 275                         }
 276                         _ => {}
 277                     }
 278                 }
 279                 _ => {}
 280             }
 281         } else {
 282             // If we are building a library, then reachable symbols will
 283             // continue to participate in linkage after this product is
 284             // produced. In this case, we traverse the ast node, recursing on
 285             // all reachable nodes from this one.
 286             self.reachable_symbols.insert(search_item);
 287         }
 288
 289         match *node {
 290             ast_map::NodeItem(item) => {
 291                 match item.node {
 292                     ast::ItemFn(_, _, _, _, ref search_block) => {
 293                         if item_might_be_inlined(&*item) {
 294                             visit::walk_block(self, &**search_block, ())
 295                         }
 296                     }
 297
 298                     // Statics with insignificant addresses are not reachable
 299                     // because they're inlined specially into all other crates.
 300                     ast::ItemStatic(_, mutbl, ref init) => {
 301                         if !ast_util::static_has_significant_address(
 302                                 mutbl,
 303                                 item.attrs.as_slice()) {
 304                             self.reachable_symbols.remove(&search_item);
 305                         }
 306                         visit::walk_expr(self, &**init, ());
 307                     }
 308
 309                     // These are normal, nothing reachable about these
 310                     // inherently and their children are already in the
 311                     // worklist, as determined by the privacy pass
 312                     ast::ItemTy(..) |
 313                     ast::ItemMod(..) | ast::ItemForeignMod(..) |
 314                     ast::ItemImpl(..) | ast::ItemTrait(..) |
 315                     ast::ItemStruct(..) | ast::ItemEnum(..) => {}
 316
 317                     _ => {
 318                         self.tcx.sess.span_bug(item.span,
 319                                                "found non-function item \
 320                                                 in worklist?!")
 321                     }
 322                 }
 323             }
 324             ast_map::NodeTraitItem(trait_method) => {
 325                 match *trait_method {
 326                     ast::RequiredMethod(..) => {
 327                         // Keep going, nothing to get exported
 328                     }
 329                     ast::ProvidedMethod(ref method) => {
 330                         visit::walk_block(self, &*method.pe_body(), ())
 331                     }
 332                 }
 333             }
 334             ast_map::NodeImplItem(impl_item) => {
 335                 match *impl_item {
 336                     ast::MethodImplItem(method) => {
 337                         let did = self.tcx.map.get_parent_did(search_item);
 338                         if method_might_be_inlined(self.tcx, &*method, did) {
 339                             visit::walk_block(self, &*method.pe_body(), ())
 340                         }
 341                     }
 342                 }
 343             }
 344             // Nothing to recurse on for these
 345             ast_map::NodeForeignItem(_) |
 346             ast_map::NodeVariant(_) |
 347             ast_map::NodeStructCtor(_) => {}
 348             _ => {
 349                 self.tcx
 350                     .sess
 351                     .bug(format!("found unexpected thingy in worklist: {}",
 352                                  self.tcx
 353                                      .map
 354                                      .node_to_string(search_item)).as_slice())
 355             }
 356         }
 357     }
 358
 359     // Step 3: Mark all destructors as reachable.
 360     //
 361     // FIXME(pcwalton): This is a conservative overapproximation, but fixing
 362     // this properly would result in the necessity of computing *type*
 363     // reachability, which might result in a compile time loss.
 364     fn mark_destructors_reachable(&mut self) {
 365         for (_, destructor_def_id) in self.tcx.destructor_for_type.borrow().iter() {
 366             if destructor_def_id.krate == ast::LOCAL_CRATE {
 367                 self.reachable_symbols.insert(destructor_def_id.node);
 368             }
 369         }
 370     }
 371 }
 372
 373 pub fn find_reachable(tcx: &ty::ctxt,
 374                       exported_items: &privacy::ExportedItems)
 375                       -> NodeSet {
 376     let mut reachable_context = ReachableContext::new(tcx);
 377
 378     // Step 1: Seed the worklist with all nodes which were found to be public as
 379     //         a result of the privacy pass along with all local lang items. If
 380     //         other crates link to us, they're going to expect to be able to
 381     //         use the lang items, so we need to be sure to mark them as
 382     //         exported.
 383     for id in exported_items.iter() {
 384         reachable_context.worklist.push(*id);
 385     }
 386     for (_, item) in tcx.lang_items.items() {
 387         match *item {
 388             Some(did) if is_local(did) => {
 389                 reachable_context.worklist.push(did.node);
 390             }
 391             _ => {}
 392         }
 393     }
 394
 395     // Step 2: Mark all symbols that the symbols on the worklist touch.
 396     reachable_context.propagate();
 397
 398     // Step 3: Mark all destructors as reachable.
 399     reachable_context.mark_destructors_reachable();
 400
 401     // Return the set of reachable symbols.
 402     reachable_context.reachable_symbols
 403 }