src/librustc_passes/reachable.rs

   1 // Finds items that are externally reachable, to determine which items
   2 // need to have their metadata (and possibly their AST) serialized.
   3 // All items that can be referred to through an exported name are
   4 // reachable, and when a reachable thing is inline or generic, it
   5 // makes all other generics or inline functions that it references
   6 // reachable as well.
   7
   8 use rustc::hir::map::Map;
   9 use rustc::middle::codegen_fn_attrs::{CodegenFnAttrFlags, CodegenFnAttrs};
  10 use rustc::middle::privacy;
  11 use rustc::session::config;
  12 use rustc::ty::query::Providers;
  13 use rustc::ty::{self, TyCtxt};
  14 use rustc_data_structures::fx::FxHashSet;
  15 use rustc_data_structures::sync::Lrc;
  16 use rustc_hir as hir;
  17 use rustc_hir::def::{DefKind, Res};
  18 use rustc_hir::def_id::LOCAL_CRATE;
  19 use rustc_hir::def_id::{CrateNum, DefId};
  20 use rustc_hir::intravisit;
  21 use rustc_hir::intravisit::{NestedVisitorMap, Visitor};
  22 use rustc_hir::itemlikevisit::ItemLikeVisitor;
  23 use rustc_hir::{HirIdSet, Node};
  24 use rustc_target::spec::abi::Abi;
  25
  26 // Returns true if the given item must be inlined because it may be
  27 // monomorphized or it was marked with `#[inline]`. This will only return
  28 // true for functions.
  29 fn item_might_be_inlined(tcx: TyCtxt<'tcx>, item: &hir::Item<'_>, attrs: CodegenFnAttrs) -> bool {
  30     if attrs.requests_inline() {
  31         return true;
  32     }
  33
  34     match item.kind {
  35         hir::ItemKind::Fn(ref sig, ..) if sig.header.is_const() => {
  36             return true;
  37         }
  38         hir::ItemKind::Impl { .. } | hir::ItemKind::Fn(..) => {
  39             let generics = tcx.generics_of(tcx.hir().local_def_id(item.hir_id));
  40             generics.requires_monomorphization(tcx)
  41         }
  42         _ => false,
  43     }
  44 }
  45
  46 fn method_might_be_inlined(
  47     tcx: TyCtxt<'_>,
  48     impl_item: &hir::ImplItem<'_>,
  49     impl_src: DefId,
  50 ) -> bool {
  51     let codegen_fn_attrs = tcx.codegen_fn_attrs(impl_item.hir_id.owner_def_id());
  52     let generics = tcx.generics_of(tcx.hir().local_def_id(impl_item.hir_id));
  53     if codegen_fn_attrs.requests_inline() || generics.requires_monomorphization(tcx) {
  54         return true;
  55     }
  56     if let hir::ImplItemKind::Method(method_sig, _) = &impl_item.kind {
  57         if method_sig.header.is_const() {
  58             return true;
  59         }
  60     }
  61     if let Some(impl_hir_id) = tcx.hir().as_local_hir_id(impl_src) {
  62         match tcx.hir().find(impl_hir_id) {
  63             Some(Node::Item(item)) => item_might_be_inlined(tcx, &item, codegen_fn_attrs),
  64             Some(..) | None => span_bug!(impl_item.span, "impl did is not an item"),
  65         }
  66     } else {
  67         span_bug!(impl_item.span, "found a foreign impl as a parent of a local method")
  68     }
  69 }
  70
  71 // Information needed while computing reachability.
  72 struct ReachableContext<'a, 'tcx> {
  73     // The type context.
  74     tcx: TyCtxt<'tcx>,
  75     tables: &'a ty::TypeckTables<'tcx>,
  76     // The set of items which must be exported in the linkage sense.
  77     reachable_symbols: HirIdSet,
  78     // A worklist of item IDs. Each item ID in this worklist will be inlined
  79     // and will be scanned for further references.
  80     worklist: Vec<hir::HirId>,
  81     // Whether any output of this compilation is a library
  82     any_library: bool,
  83 }
  84
  85 impl<'a, 'tcx> Visitor<'tcx> for ReachableContext<'a, 'tcx> {
  86     type Map = Map<'tcx>;
  87
  88     fn nested_visit_map(&mut self) -> NestedVisitorMap<'_, Self::Map> {
  89         NestedVisitorMap::None
  90     }
  91
  92     fn visit_nested_body(&mut self, body: hir::BodyId) {
  93         let old_tables = self.tables;
  94         self.tables = self.tcx.body_tables(body);
  95         let body = self.tcx.hir().body(body);
  96         self.visit_body(body);
  97         self.tables = old_tables;
  98     }
  99
 100     fn visit_expr(&mut self, expr: &'tcx hir::Expr<'tcx>) {
 101         let res = match expr.kind {
 102             hir::ExprKind::Path(ref qpath) => Some(self.tables.qpath_res(qpath, expr.hir_id)),
 103             hir::ExprKind::MethodCall(..) => self
 104                 .tables
 105                 .type_dependent_def(expr.hir_id)
 106                 .map(|(kind, def_id)| Res::Def(kind, def_id)),
 107             _ => None,
 108         };
 109
 110         match res {
 111             Some(Res::Local(hir_id)) => {
 112                 self.reachable_symbols.insert(hir_id);
 113             }
 114             Some(res) => {
 115                 if let Some((hir_id, def_id)) = res.opt_def_id().and_then(|def_id| {
 116                     self.tcx.hir().as_local_hir_id(def_id).map(|hir_id| (hir_id, def_id))
 117                 }) {
 118                     if self.def_id_represents_local_inlined_item(def_id) {
 119                         self.worklist.push(hir_id);
 120                     } else {
 121                         match res {
 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                             Res::Def(DefKind::Const, _) | Res::Def(DefKind::AssocConst, _) => {
 126                                 self.worklist.push(hir_id);
 127                             }
 128
 129                             // If this wasn't a static, then the destination is
 130                             // surely reachable.
 131                             _ => {
 132                                 self.reachable_symbols.insert(hir_id);
 133                             }
 134                         }
 135                     }
 136                 }
 137             }
 138             _ => {}
 139         }
 140
 141         intravisit::walk_expr(self, expr)
 142     }
 143 }
 144
 145 impl<'a, 'tcx> ReachableContext<'a, 'tcx> {
 146     // Returns true if the given def ID represents a local item that is
 147     // eligible for inlining and false otherwise.
 148     fn def_id_represents_local_inlined_item(&self, def_id: DefId) -> bool {
 149         let hir_id = match self.tcx.hir().as_local_hir_id(def_id) {
 150             Some(hir_id) => hir_id,
 151             None => {
 152                 return false;
 153             }
 154         };
 155
 156         match self.tcx.hir().find(hir_id) {
 157             Some(Node::Item(item)) => match item.kind {
 158                 hir::ItemKind::Fn(..) => {
 159                     item_might_be_inlined(self.tcx, &item, self.tcx.codegen_fn_attrs(def_id))
 160                 }
 161                 _ => false,
 162             },
 163             Some(Node::TraitItem(trait_method)) => match trait_method.kind {
 164                 hir::TraitItemKind::Const(_, ref default) => default.is_some(),
 165                 hir::TraitItemKind::Method(_, hir::TraitMethod::Provided(_)) => true,
 166                 hir::TraitItemKind::Method(_, hir::TraitMethod::Required(_))
 167                 | hir::TraitItemKind::Type(..) => false,
 168             },
 169             Some(Node::ImplItem(impl_item)) => {
 170                 match impl_item.kind {
 171                     hir::ImplItemKind::Const(..) => true,
 172                     hir::ImplItemKind::Method(..) => {
 173                         let attrs = self.tcx.codegen_fn_attrs(def_id);
 174                         let generics = self.tcx.generics_of(def_id);
 175                         if generics.requires_monomorphization(self.tcx) || attrs.requests_inline() {
 176                             true
 177                         } else {
 178                             let impl_did = self.tcx.hir().get_parent_did(hir_id);
 179                             // Check the impl. If the generics on the self
 180                             // type of the impl require inlining, this method
 181                             // does too.
 182                             let impl_hir_id = self.tcx.hir().as_local_hir_id(impl_did).unwrap();
 183                             match self.tcx.hir().expect_item(impl_hir_id).kind {
 184                                 hir::ItemKind::Impl { .. } => {
 185                                     let generics = self.tcx.generics_of(impl_did);
 186                                     generics.requires_monomorphization(self.tcx)
 187                                 }
 188                                 _ => false,
 189                             }
 190                         }
 191                     }
 192                     hir::ImplItemKind::OpaqueTy(..) | hir::ImplItemKind::TyAlias(_) => false,
 193                 }
 194             }
 195             Some(_) => false,
 196             None => false, // This will happen for default methods.
 197         }
 198     }
 199
 200     // Step 2: Mark all symbols that the symbols on the worklist touch.
 201     fn propagate(&mut self) {
 202         let mut scanned = FxHashSet::default();
 203         while let Some(search_item) = self.worklist.pop() {
 204             if !scanned.insert(search_item) {
 205                 continue;
 206             }
 207
 208             if let Some(ref item) = self.tcx.hir().find(search_item) {
 209                 self.propagate_node(item, search_item);
 210             }
 211         }
 212     }
 213
 214     fn propagate_node(&mut self, node: &Node<'tcx>, search_item: hir::HirId) {
 215         if !self.any_library {
 216             // If we are building an executable, only explicitly extern
 217             // types need to be exported.
 218             if let Node::Item(item) = *node {
 219                 let reachable = if let hir::ItemKind::Fn(ref sig, ..) = item.kind {
 220                     sig.header.abi != Abi::Rust
 221                 } else {
 222                     false
 223                 };
 224                 let def_id = self.tcx.hir().local_def_id(item.hir_id);
 225                 let codegen_attrs = self.tcx.codegen_fn_attrs(def_id);
 226                 let is_extern = codegen_attrs.contains_extern_indicator();
 227                 let std_internal =
 228                     codegen_attrs.flags.contains(CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL);
 229                 if reachable || is_extern || std_internal {
 230                     self.reachable_symbols.insert(search_item);
 231                 }
 232             }
 233         } else {
 234             // If we are building a library, then reachable symbols will
 235             // continue to participate in linkage after this product is
 236             // produced. In this case, we traverse the ast node, recursing on
 237             // all reachable nodes from this one.
 238             self.reachable_symbols.insert(search_item);
 239         }
 240
 241         match *node {
 242             Node::Item(item) => {
 243                 match item.kind {
 244                     hir::ItemKind::Fn(.., body) => {
 245                         let def_id = self.tcx.hir().local_def_id(item.hir_id);
 246                         if item_might_be_inlined(self.tcx, &item, self.tcx.codegen_fn_attrs(def_id))
 247                         {
 248                             self.visit_nested_body(body);
 249                         }
 250                     }
 251
 252                     // Reachable constants will be inlined into other crates
 253                     // unconditionally, so we need to make sure that their
 254                     // contents are also reachable.
 255                     hir::ItemKind::Const(_, init) => {
 256                         self.visit_nested_body(init);
 257                     }
 258
 259                     // These are normal, nothing reachable about these
 260                     // inherently and their children are already in the
 261                     // worklist, as determined by the privacy pass
 262                     hir::ItemKind::ExternCrate(_)
 263                     | hir::ItemKind::Use(..)
 264                     | hir::ItemKind::OpaqueTy(..)
 265                     | hir::ItemKind::TyAlias(..)
 266                     | hir::ItemKind::Static(..)
 267                     | hir::ItemKind::Mod(..)
 268                     | hir::ItemKind::ForeignMod(..)
 269                     | hir::ItemKind::Impl { .. }
 270                     | hir::ItemKind::Trait(..)
 271                     | hir::ItemKind::TraitAlias(..)
 272                     | hir::ItemKind::Struct(..)
 273                     | hir::ItemKind::Enum(..)
 274                     | hir::ItemKind::Union(..)
 275                     | hir::ItemKind::GlobalAsm(..) => {}
 276                 }
 277             }
 278             Node::TraitItem(trait_method) => {
 279                 match trait_method.kind {
 280                     hir::TraitItemKind::Const(_, None)
 281                     | hir::TraitItemKind::Method(_, hir::TraitMethod::Required(_)) => {
 282                         // Keep going, nothing to get exported
 283                     }
 284                     hir::TraitItemKind::Const(_, Some(body_id))
 285                     | hir::TraitItemKind::Method(_, hir::TraitMethod::Provided(body_id)) => {
 286                         self.visit_nested_body(body_id);
 287                     }
 288                     hir::TraitItemKind::Type(..) => {}
 289                 }
 290             }
 291             Node::ImplItem(impl_item) => match impl_item.kind {
 292                 hir::ImplItemKind::Const(_, body) => {
 293                     self.visit_nested_body(body);
 294                 }
 295                 hir::ImplItemKind::Method(_, body) => {
 296                     let did = self.tcx.hir().get_parent_did(search_item);
 297                     if method_might_be_inlined(self.tcx, impl_item, did) {
 298                         self.visit_nested_body(body)
 299                     }
 300                 }
 301                 hir::ImplItemKind::OpaqueTy(..) | hir::ImplItemKind::TyAlias(_) => {}
 302             },
 303             Node::Expr(&hir::Expr { kind: hir::ExprKind::Closure(.., body, _, _), .. }) => {
 304                 self.visit_nested_body(body);
 305             }
 306             // Nothing to recurse on for these
 307             Node::ForeignItem(_)
 308             | Node::Variant(_)
 309             | Node::Ctor(..)
 310             | Node::Field(_)
 311             | Node::Ty(_)
 312             | Node::MacroDef(_) => {}
 313             _ => {
 314                 bug!(
 315                     "found unexpected node kind in worklist: {} ({:?})",
 316                     self.tcx.hir().node_to_string(search_item),
 317                     node,
 318                 );
 319             }
 320         }
 321     }
 322 }
 323
 324 // Some methods from non-exported (completely private) trait impls still have to be
 325 // reachable if they are called from inlinable code. Generally, it's not known until
 326 // monomorphization if a specific trait impl item can be reachable or not. So, we
 327 // conservatively mark all of them as reachable.
 328 // FIXME: One possible strategy for pruning the reachable set is to avoid marking impl
 329 // items of non-exported traits (or maybe all local traits?) unless their respective
 330 // trait items are used from inlinable code through method call syntax or UFCS, or their
 331 // trait is a lang item.
 332 struct CollectPrivateImplItemsVisitor<'a, 'tcx> {
 333     tcx: TyCtxt<'tcx>,
 334     access_levels: &'a privacy::AccessLevels,
 335     worklist: &'a mut Vec<hir::HirId>,
 336 }
 337
 338 impl<'a, 'tcx> ItemLikeVisitor<'tcx> for CollectPrivateImplItemsVisitor<'a, 'tcx> {
 339     fn visit_item(&mut self, item: &hir::Item<'_>) {
 340         // Anything which has custom linkage gets thrown on the worklist no
 341         // matter where it is in the crate, along with "special std symbols"
 342         // which are currently akin to allocator symbols.
 343         let def_id = self.tcx.hir().local_def_id(item.hir_id);
 344         let codegen_attrs = self.tcx.codegen_fn_attrs(def_id);
 345         if codegen_attrs.contains_extern_indicator()
 346             || codegen_attrs.flags.contains(CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL)
 347         {
 348             self.worklist.push(item.hir_id);
 349         }
 350
 351         // We need only trait impls here, not inherent impls, and only non-exported ones
 352         if let hir::ItemKind::Impl { of_trait: Some(ref trait_ref), ref items, .. } = item.kind {
 353             if !self.access_levels.is_reachable(item.hir_id) {
 354                 self.worklist.extend(items.iter().map(|ii_ref| ii_ref.id.hir_id));
 355
 356                 let trait_def_id = match trait_ref.path.res {
 357                     Res::Def(DefKind::Trait, def_id) => def_id,
 358                     _ => unreachable!(),
 359                 };
 360
 361                 if !trait_def_id.is_local() {
 362                     return;
 363                 }
 364
 365                 let provided_trait_methods = self.tcx.provided_trait_methods(trait_def_id);
 366                 self.worklist.reserve(provided_trait_methods.len());
 367                 for default_method in provided_trait_methods {
 368                     let hir_id = self.tcx.hir().as_local_hir_id(default_method.def_id).unwrap();
 369                     self.worklist.push(hir_id);
 370                 }
 371             }
 372         }
 373     }
 374
 375     fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem<'_>) {}
 376
 377     fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem<'_>) {
 378         // processed in visit_item above
 379     }
 380 }
 381
 382 fn reachable_set(tcx: TyCtxt<'_>, crate_num: CrateNum) -> Lrc<HirIdSet> {
 383     debug_assert!(crate_num == LOCAL_CRATE);
 384
 385     let access_levels = &tcx.privacy_access_levels(LOCAL_CRATE);
 386
 387     let any_library = tcx.sess.crate_types.borrow().iter().any(|ty| {
 388         *ty == config::CrateType::Rlib
 389             || *ty == config::CrateType::Dylib
 390             || *ty == config::CrateType::ProcMacro
 391     });
 392     let mut reachable_context = ReachableContext {
 393         tcx,
 394         tables: &ty::TypeckTables::empty(None),
 395         reachable_symbols: Default::default(),
 396         worklist: Vec::new(),
 397         any_library,
 398     };
 399
 400     // Step 1: Seed the worklist with all nodes which were found to be public as
 401     //         a result of the privacy pass along with all local lang items and impl items.
 402     //         If other crates link to us, they're going to expect to be able to
 403     //         use the lang items, so we need to be sure to mark them as
 404     //         exported.
 405     reachable_context.worklist.extend(access_levels.map.iter().map(|(id, _)| *id));
 406     for item in tcx.lang_items().items().iter() {
 407         if let Some(did) = *item {
 408             if let Some(hir_id) = tcx.hir().as_local_hir_id(did) {
 409                 reachable_context.worklist.push(hir_id);
 410             }
 411         }
 412     }
 413     {
 414         let mut collect_private_impl_items = CollectPrivateImplItemsVisitor {
 415             tcx,
 416             access_levels,
 417             worklist: &mut reachable_context.worklist,
 418         };
 419         tcx.hir().krate().visit_all_item_likes(&mut collect_private_impl_items);
 420     }
 421
 422     // Step 2: Mark all symbols that the symbols on the worklist touch.
 423     reachable_context.propagate();
 424
 425     debug!("Inline reachability shows: {:?}", reachable_context.reachable_symbols);
 426
 427     // Return the set of reachable symbols.
 428     Lrc::new(reachable_context.reachable_symbols)
 429 }
 430
 431 pub fn provide(providers: &mut Providers<'_>) {
 432     *providers = Providers { reachable_set, ..*providers };
 433 }