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