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