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