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(tcx
.hir().local_def_id(item
.hir_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(tcx
.hir().local_def_id(impl_item
.hir_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 def_id
= self.tcx
.hir().local_def_id(item
.hir_id
);
222 let codegen_attrs
= self.tcx
.codegen_fn_attrs(def_id
);
223 let is_extern
= codegen_attrs
.contains_extern_indicator();
225 codegen_attrs
.flags
.contains(CodegenFnAttrFlags
::RUSTC_STD_INTERNAL_SYMBOL
);
226 if reachable
|| is_extern
|| std_internal
{
227 self.reachable_symbols
.insert(search_item
);
231 // If we are building a library, then reachable symbols will
232 // continue to participate in linkage after this product is
233 // produced. In this case, we traverse the ast node, recursing on
234 // all reachable nodes from this one.
235 self.reachable_symbols
.insert(search_item
);
239 Node
::Item(item
) => {
241 hir
::ItemKind
::Fn(.., body
) => {
242 let def_id
= self.tcx
.hir().local_def_id(item
.hir_id
);
243 if item_might_be_inlined(self.tcx
, &item
, self.tcx
.codegen_fn_attrs(def_id
))
245 self.visit_nested_body(body
);
249 // Reachable constants will be inlined into other crates
250 // unconditionally, so we need to make sure that their
251 // contents are also reachable.
252 hir
::ItemKind
::Const(_
, init
) => {
253 self.visit_nested_body(init
);
256 // These are normal, nothing reachable about these
257 // inherently and their children are already in the
258 // worklist, as determined by the privacy pass
259 hir
::ItemKind
::ExternCrate(_
)
260 | hir
::ItemKind
::Use(..)
261 | hir
::ItemKind
::OpaqueTy(..)
262 | hir
::ItemKind
::TyAlias(..)
263 | hir
::ItemKind
::Static(..)
264 | hir
::ItemKind
::Mod(..)
265 | hir
::ItemKind
::ForeignMod(..)
266 | hir
::ItemKind
::Impl { .. }
267 | hir
::ItemKind
::Trait(..)
268 | hir
::ItemKind
::TraitAlias(..)
269 | hir
::ItemKind
::Struct(..)
270 | hir
::ItemKind
::Enum(..)
271 | hir
::ItemKind
::Union(..)
272 | hir
::ItemKind
::GlobalAsm(..) => {}
275 Node
::TraitItem(trait_method
) => {
276 match trait_method
.kind
{
277 hir
::TraitItemKind
::Const(_
, None
)
278 | hir
::TraitItemKind
::Fn(_
, hir
::TraitFn
::Required(_
)) => {
279 // Keep going, nothing to get exported
281 hir
::TraitItemKind
::Const(_
, Some(body_id
))
282 | hir
::TraitItemKind
::Fn(_
, hir
::TraitFn
::Provided(body_id
)) => {
283 self.visit_nested_body(body_id
);
285 hir
::TraitItemKind
::Type(..) => {}
288 Node
::ImplItem(impl_item
) => match impl_item
.kind
{
289 hir
::ImplItemKind
::Const(_
, body
) => {
290 self.visit_nested_body(body
);
292 hir
::ImplItemKind
::Fn(_
, body
) => {
294 self.tcx
.parent(search_item
.to_def_id()).unwrap().expect_local();
295 if method_might_be_inlined(self.tcx
, impl_item
, impl_def_id
) {
296 self.visit_nested_body(body
)
299 hir
::ImplItemKind
::TyAlias(_
) => {}
301 Node
::Expr(&hir
::Expr { kind: hir::ExprKind::Closure(.., body, _, _), .. }
) => {
302 self.visit_nested_body(body
);
304 // Nothing to recurse on for these
310 | Node
::MacroDef(_
) => {}
313 "found unexpected node kind in worklist: {} ({:?})",
316 .node_to_string(self.tcx
.hir().local_def_id_to_hir_id(search_item
)),
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
> {
334 access_levels
: &'a privacy
::AccessLevels
,
335 worklist
: &'a
mut Vec
<LocalDefId
>,
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
)
348 self.worklist
.push(def_id
);
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 // FIXME(#53488) remove `let`
357 .extend(items
.iter().map(|ii_ref
| tcx
.hir().local_def_id(ii_ref
.id
.hir_id
)));
359 let trait_def_id
= match trait_ref
.path
.res
{
360 Res
::Def(DefKind
::Trait
, def_id
) => def_id
,
364 if !trait_def_id
.is_local() {
368 self.worklist
.extend(
369 tcx
.provided_trait_methods(trait_def_id
)
370 .map(|assoc
| assoc
.def_id
.expect_local()),
376 fn visit_trait_item(&mut self, _trait_item
: &hir
::TraitItem
<'_
>) {}
378 fn visit_impl_item(&mut self, _impl_item
: &hir
::ImplItem
<'_
>) {
379 // processed in visit_item above
383 fn reachable_set
<'tcx
>(tcx
: TyCtxt
<'tcx
>, crate_num
: CrateNum
) -> FxHashSet
<LocalDefId
> {
384 debug_assert
!(crate_num
== LOCAL_CRATE
);
386 let access_levels
= &tcx
.privacy_access_levels(LOCAL_CRATE
);
389 tcx
.sess
.crate_types().iter().any(|ty
| {
390 *ty
== CrateType
::Rlib
|| *ty
== CrateType
::Dylib
|| *ty
== CrateType
::ProcMacro
392 let mut reachable_context
= ReachableContext
{
394 maybe_typeck_results
: None
,
395 reachable_symbols
: Default
::default(),
396 worklist
: Vec
::new(),
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
407 .extend(access_levels
.map
.iter().map(|(id
, _
)| tcx
.hir().local_def_id(*id
)));
408 for item
in tcx
.lang_items().items().iter() {
409 if let Some(def_id
) = *item
{
410 if let Some(def_id
) = def_id
.as_local() {
411 reachable_context
.worklist
.push(def_id
);
416 let mut collect_private_impl_items
= CollectPrivateImplItemsVisitor
{
419 worklist
: &mut reachable_context
.worklist
,
421 tcx
.hir().krate().visit_all_item_likes(&mut collect_private_impl_items
);
424 // Step 2: Mark all symbols that the symbols on the worklist touch.
425 reachable_context
.propagate();
427 debug
!("Inline reachability shows: {:?}", reachable_context
.reachable_symbols
);
429 // Return the set of reachable symbols.
430 reachable_context
.reachable_symbols
433 pub fn provide(providers
: &mut Providers
) {
434 *providers
= Providers { reachable_set, ..*providers }
;