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