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
8 use rustc_data_structures
::fx
::FxHashSet
;
10 use rustc_hir
::def
::{DefKind, Res}
;
11 use rustc_hir
::def_id
::LOCAL_CRATE
;
12 use rustc_hir
::def_id
::{CrateNum, DefId, LocalDefId}
;
13 use rustc_hir
::intravisit
::{self, NestedVisitorMap, Visitor}
;
14 use rustc_hir
::itemlikevisit
::ItemLikeVisitor
;
16 use rustc_middle
::middle
::codegen_fn_attrs
::{CodegenFnAttrFlags, CodegenFnAttrs}
;
17 use rustc_middle
::middle
::privacy
;
18 use rustc_middle
::ty
::query
::Providers
;
19 use rustc_middle
::ty
::{self, DefIdTree, TyCtxt}
;
20 use rustc_session
::config
::CrateType
;
21 use rustc_target
::spec
::abi
::Abi
;
23 // Returns true if the given item must be inlined because it may be
24 // monomorphized or it was marked with `#[inline]`. This will only return
25 // true for functions.
26 fn item_might_be_inlined(tcx
: TyCtxt
<'tcx
>, item
: &hir
::Item
<'_
>, attrs
: &CodegenFnAttrs
) -> bool
{
27 if attrs
.requests_inline() {
32 hir
::ItemKind
::Fn(ref sig
, ..) if sig
.header
.is_const() => true,
33 hir
::ItemKind
::Impl { .. }
| hir
::ItemKind
::Fn(..) => {
34 let generics
= tcx
.generics_of(item
.def_id
);
35 generics
.requires_monomorphization(tcx
)
41 fn method_might_be_inlined(
43 impl_item
: &hir
::ImplItem
<'_
>,
46 let codegen_fn_attrs
= tcx
.codegen_fn_attrs(impl_item
.hir_id().owner
.to_def_id());
47 let generics
= tcx
.generics_of(impl_item
.def_id
);
48 if codegen_fn_attrs
.requests_inline() || generics
.requires_monomorphization(tcx
) {
51 if let hir
::ImplItemKind
::Fn(method_sig
, _
) = &impl_item
.kind
{
52 if method_sig
.header
.is_const() {
56 match tcx
.hir().find(tcx
.hir().local_def_id_to_hir_id(impl_src
)) {
57 Some(Node
::Item(item
)) => item_might_be_inlined(tcx
, &item
, codegen_fn_attrs
),
58 Some(..) | None
=> span_bug
!(impl_item
.span
, "impl did is not an item"),
62 // Information needed while computing reachability.
63 struct ReachableContext
<'tcx
> {
66 maybe_typeck_results
: Option
<&'tcx ty
::TypeckResults
<'tcx
>>,
67 // The set of items which must be exported in the linkage sense.
68 reachable_symbols
: FxHashSet
<LocalDefId
>,
69 // A worklist of item IDs. Each item ID in this worklist will be inlined
70 // and will be scanned for further references.
71 // FIXME(eddyb) benchmark if this would be faster as a `VecDeque`.
72 worklist
: Vec
<LocalDefId
>,
73 // Whether any output of this compilation is a library
77 impl<'tcx
> Visitor
<'tcx
> for ReachableContext
<'tcx
> {
78 type Map
= intravisit
::ErasedMap
<'tcx
>;
80 fn nested_visit_map(&mut self) -> NestedVisitorMap
<Self::Map
> {
81 NestedVisitorMap
::None
84 fn visit_nested_body(&mut self, body
: hir
::BodyId
) {
85 let old_maybe_typeck_results
=
86 self.maybe_typeck_results
.replace(self.tcx
.typeck_body(body
));
87 let body
= self.tcx
.hir().body(body
);
88 self.visit_body(body
);
89 self.maybe_typeck_results
= old_maybe_typeck_results
;
92 fn visit_expr(&mut self, expr
: &'tcx hir
::Expr
<'tcx
>) {
93 let res
= match expr
.kind
{
94 hir
::ExprKind
::Path(ref qpath
) => {
95 Some(self.typeck_results().qpath_res(qpath
, expr
.hir_id
))
97 hir
::ExprKind
::MethodCall(..) => self
99 .type_dependent_def(expr
.hir_id
)
100 .map(|(kind
, def_id
)| Res
::Def(kind
, def_id
)),
104 if let Some(res
) = res
{
105 if let Some(def_id
) = res
.opt_def_id().and_then(|def_id
| def_id
.as_local()) {
106 if self.def_id_represents_local_inlined_item(def_id
.to_def_id()) {
107 self.worklist
.push(def_id
);
110 // If this path leads to a constant, then we need to
111 // recurse into the constant to continue finding
112 // items that are reachable.
113 Res
::Def(DefKind
::Const
| DefKind
::AssocConst
, _
) => {
114 self.worklist
.push(def_id
);
117 // If this wasn't a static, then the destination is
120 self.reachable_symbols
.insert(def_id
);
127 intravisit
::walk_expr(self, expr
)
131 impl<'tcx
> ReachableContext
<'tcx
> {
132 /// Gets the type-checking results for the current body.
133 /// As this will ICE if called outside bodies, only call when working with
134 /// `Expr` or `Pat` nodes (they are guaranteed to be found only in bodies).
136 fn typeck_results(&self) -> &'tcx ty
::TypeckResults
<'tcx
> {
137 self.maybe_typeck_results
138 .expect("`ReachableContext::typeck_results` called outside of body")
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 def_id
.as_local() {
145 Some(def_id
) => self.tcx
.hir().local_def_id_to_hir_id(def_id
),
151 match self.tcx
.hir().find(hir_id
) {
152 Some(Node
::Item(item
)) => match item
.kind
{
153 hir
::ItemKind
::Fn(..) => {
154 item_might_be_inlined(self.tcx
, &item
, self.tcx
.codegen_fn_attrs(def_id
))
158 Some(Node
::TraitItem(trait_method
)) => match trait_method
.kind
{
159 hir
::TraitItemKind
::Const(_
, ref default) => default.is_some(),
160 hir
::TraitItemKind
::Fn(_
, hir
::TraitFn
::Provided(_
)) => true,
161 hir
::TraitItemKind
::Fn(_
, hir
::TraitFn
::Required(_
))
162 | hir
::TraitItemKind
::Type(..) => false,
164 Some(Node
::ImplItem(impl_item
)) => {
165 match impl_item
.kind
{
166 hir
::ImplItemKind
::Const(..) => true,
167 hir
::ImplItemKind
::Fn(..) => {
168 let attrs
= self.tcx
.codegen_fn_attrs(def_id
);
169 let generics
= self.tcx
.generics_of(def_id
);
170 if generics
.requires_monomorphization(self.tcx
) || attrs
.requests_inline() {
173 let impl_did
= self.tcx
.hir().get_parent_did(hir_id
);
174 // Check the impl. If the generics on the self
175 // type of the impl require inlining, this method
177 let impl_hir_id
= self.tcx
.hir().local_def_id_to_hir_id(impl_did
);
178 match self.tcx
.hir().expect_item(impl_hir_id
).kind
{
179 hir
::ItemKind
::Impl { .. }
=> {
180 let generics
= self.tcx
.generics_of(impl_did
);
181 generics
.requires_monomorphization(self.tcx
)
187 hir
::ImplItemKind
::TyAlias(_
) => false,
191 None
=> false, // This will happen for default methods.
195 // Step 2: Mark all symbols that the symbols on the worklist touch.
196 fn propagate(&mut self) {
197 let mut scanned
= FxHashSet
::default();
198 while let Some(search_item
) = self.worklist
.pop() {
199 if !scanned
.insert(search_item
) {
203 if let Some(ref item
) =
204 self.tcx
.hir().find(self.tcx
.hir().local_def_id_to_hir_id(search_item
))
206 self.propagate_node(item
, search_item
);
211 fn propagate_node(&mut self, node
: &Node
<'tcx
>, search_item
: LocalDefId
) {
212 if !self.any_library
{
213 // If we are building an executable, only explicitly extern
214 // types need to be exported.
215 if let Node
::Item(item
) = *node
{
216 let reachable
= if let hir
::ItemKind
::Fn(ref sig
, ..) = item
.kind
{
217 sig
.header
.abi
!= Abi
::Rust
221 let codegen_attrs
= self.tcx
.codegen_fn_attrs(item
.def_id
);
222 let is_extern
= codegen_attrs
.contains_extern_indicator();
224 codegen_attrs
.flags
.contains(CodegenFnAttrFlags
::RUSTC_STD_INTERNAL_SYMBOL
);
225 if reachable
|| is_extern
|| std_internal
{
226 self.reachable_symbols
.insert(search_item
);
230 // If we are building a library, then reachable symbols will
231 // continue to participate in linkage after this product is
232 // produced. In this case, we traverse the ast node, recursing on
233 // all reachable nodes from this one.
234 self.reachable_symbols
.insert(search_item
);
238 Node
::Item(item
) => {
240 hir
::ItemKind
::Fn(.., body
) => {
241 if item_might_be_inlined(
244 self.tcx
.codegen_fn_attrs(item
.def_id
),
246 self.visit_nested_body(body
);
250 // Reachable constants will be inlined into other crates
251 // unconditionally, so we need to make sure that their
252 // contents are also reachable.
253 hir
::ItemKind
::Const(_
, init
) => {
254 self.visit_nested_body(init
);
257 // These are normal, nothing reachable about these
258 // inherently and their children are already in the
259 // worklist, as determined by the privacy pass
260 hir
::ItemKind
::ExternCrate(_
)
261 | hir
::ItemKind
::Use(..)
262 | hir
::ItemKind
::OpaqueTy(..)
263 | hir
::ItemKind
::TyAlias(..)
264 | hir
::ItemKind
::Static(..)
265 | hir
::ItemKind
::Mod(..)
266 | hir
::ItemKind
::ForeignMod { .. }
267 | hir
::ItemKind
::Impl { .. }
268 | hir
::ItemKind
::Trait(..)
269 | hir
::ItemKind
::TraitAlias(..)
270 | hir
::ItemKind
::Struct(..)
271 | hir
::ItemKind
::Enum(..)
272 | hir
::ItemKind
::Union(..)
273 | hir
::ItemKind
::GlobalAsm(..) => {}
276 Node
::TraitItem(trait_method
) => {
277 match trait_method
.kind
{
278 hir
::TraitItemKind
::Const(_
, None
)
279 | hir
::TraitItemKind
::Fn(_
, hir
::TraitFn
::Required(_
)) => {
280 // Keep going, nothing to get exported
282 hir
::TraitItemKind
::Const(_
, Some(body_id
))
283 | hir
::TraitItemKind
::Fn(_
, hir
::TraitFn
::Provided(body_id
)) => {
284 self.visit_nested_body(body_id
);
286 hir
::TraitItemKind
::Type(..) => {}
289 Node
::ImplItem(impl_item
) => match impl_item
.kind
{
290 hir
::ImplItemKind
::Const(_
, body
) => {
291 self.visit_nested_body(body
);
293 hir
::ImplItemKind
::Fn(_
, body
) => {
295 self.tcx
.parent(search_item
.to_def_id()).unwrap().expect_local();
296 if method_might_be_inlined(self.tcx
, impl_item
, impl_def_id
) {
297 self.visit_nested_body(body
)
300 hir
::ImplItemKind
::TyAlias(_
) => {}
302 Node
::Expr(&hir
::Expr { kind: hir::ExprKind::Closure(.., body, _, _), .. }
) => {
303 self.visit_nested_body(body
);
305 // Nothing to recurse on for these
312 | Node
::MacroDef(_
) => {}
315 "found unexpected node kind in worklist: {} ({:?})",
318 .node_to_string(self.tcx
.hir().local_def_id_to_hir_id(search_item
)),
326 // Some methods from non-exported (completely private) trait impls still have to be
327 // reachable if they are called from inlinable code. Generally, it's not known until
328 // monomorphization if a specific trait impl item can be reachable or not. So, we
329 // conservatively mark all of them as reachable.
330 // FIXME: One possible strategy for pruning the reachable set is to avoid marking impl
331 // items of non-exported traits (or maybe all local traits?) unless their respective
332 // trait items are used from inlinable code through method call syntax or UFCS, or their
333 // trait is a lang item.
334 struct CollectPrivateImplItemsVisitor
<'a
, 'tcx
> {
336 access_levels
: &'a privacy
::AccessLevels
,
337 worklist
: &'a
mut Vec
<LocalDefId
>,
340 impl<'a
, 'tcx
> ItemLikeVisitor
<'tcx
> for CollectPrivateImplItemsVisitor
<'a
, 'tcx
> {
341 fn visit_item(&mut self, item
: &hir
::Item
<'_
>) {
342 // Anything which has custom linkage gets thrown on the worklist no
343 // matter where it is in the crate, along with "special std symbols"
344 // which are currently akin to allocator symbols.
345 let codegen_attrs
= self.tcx
.codegen_fn_attrs(item
.def_id
);
346 if codegen_attrs
.contains_extern_indicator()
347 || codegen_attrs
.flags
.contains(CodegenFnAttrFlags
::RUSTC_STD_INTERNAL_SYMBOL
)
349 self.worklist
.push(item
.def_id
);
352 // We need only trait impls here, not inherent impls, and only non-exported ones
353 if let hir
::ItemKind
::Impl(hir
::Impl { of_trait: Some(ref trait_ref), ref items, .. }
) =
356 if !self.access_levels
.is_reachable(item
.hir_id()) {
357 // FIXME(#53488) remove `let`
359 self.worklist
.extend(items
.iter().map(|ii_ref
| ii_ref
.id
.def_id
));
361 let trait_def_id
= match trait_ref
.path
.res
{
362 Res
::Def(DefKind
::Trait
, def_id
) => def_id
,
366 if !trait_def_id
.is_local() {
370 self.worklist
.extend(
371 tcx
.provided_trait_methods(trait_def_id
)
372 .map(|assoc
| assoc
.def_id
.expect_local()),
378 fn visit_trait_item(&mut self, _trait_item
: &hir
::TraitItem
<'_
>) {}
380 fn visit_impl_item(&mut self, _impl_item
: &hir
::ImplItem
<'_
>) {
381 // processed in visit_item above
384 fn visit_foreign_item(&mut self, _foreign_item
: &hir
::ForeignItem
<'_
>) {
385 // We never export foreign functions as they have no body to export.
389 fn reachable_set
<'tcx
>(tcx
: TyCtxt
<'tcx
>, crate_num
: CrateNum
) -> FxHashSet
<LocalDefId
> {
390 debug_assert
!(crate_num
== LOCAL_CRATE
);
392 let access_levels
= &tcx
.privacy_access_levels(LOCAL_CRATE
);
395 tcx
.sess
.crate_types().iter().any(|ty
| {
396 *ty
== CrateType
::Rlib
|| *ty
== CrateType
::Dylib
|| *ty
== CrateType
::ProcMacro
398 let mut reachable_context
= ReachableContext
{
400 maybe_typeck_results
: None
,
401 reachable_symbols
: Default
::default(),
402 worklist
: Vec
::new(),
406 // Step 1: Seed the worklist with all nodes which were found to be public as
407 // a result of the privacy pass along with all local lang items and impl items.
408 // If other crates link to us, they're going to expect to be able to
409 // use the lang items, so we need to be sure to mark them as
413 .extend(access_levels
.map
.iter().map(|(id
, _
)| tcx
.hir().local_def_id(*id
)));
414 for item
in tcx
.lang_items().items().iter() {
415 if let Some(def_id
) = *item
{
416 if let Some(def_id
) = def_id
.as_local() {
417 reachable_context
.worklist
.push(def_id
);
422 let mut collect_private_impl_items
= CollectPrivateImplItemsVisitor
{
425 worklist
: &mut reachable_context
.worklist
,
427 tcx
.hir().krate().visit_all_item_likes(&mut collect_private_impl_items
);
430 // Step 2: Mark all symbols that the symbols on the worklist touch.
431 reachable_context
.propagate();
433 debug
!("Inline reachability shows: {:?}", reachable_context
.reachable_symbols
);
435 // Return the set of reachable symbols.
436 reachable_context
.reachable_symbols
439 pub fn provide(providers
: &mut Providers
) {
440 *providers
= Providers { reachable_set, ..*providers }
;