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.
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.
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
18 use dep_graph
::DepNode
;
19 use hir
::map
as ast_map
;
21 use hir
::def_id
::DefId
;
22 use ty
::{self, TyCtxt}
;
25 use util
::nodemap
::NodeSet
;
27 use std
::collections
::HashSet
;
32 use hir
::intravisit
::Visitor
;
35 // Returns true if the given set of generics implies that the item it's
36 // associated with must be inlined.
37 fn generics_require_inlining(generics
: &hir
::Generics
) -> bool
{
38 !generics
.ty_params
.is_empty()
41 // Returns true if the given item must be inlined because it may be
42 // monomorphized or it was marked with `#[inline]`. This will only return
43 // true for functions.
44 fn item_might_be_inlined(item
: &hir
::Item
) -> bool
{
45 if attr
::requests_inline(&item
.attrs
) {
50 hir
::ItemImpl(_
, _
, ref generics
, _
, _
, _
) |
51 hir
::ItemFn(_
, _
, _
, _
, ref generics
, _
) => {
52 generics_require_inlining(generics
)
58 fn method_might_be_inlined(tcx
: &TyCtxt
, sig
: &hir
::MethodSig
,
59 impl_item
: &hir
::ImplItem
,
60 impl_src
: DefId
) -> bool
{
61 if attr
::requests_inline(&impl_item
.attrs
) ||
62 generics_require_inlining(&sig
.generics
) {
65 if let Some(impl_node_id
) = tcx
.map
.as_local_node_id(impl_src
) {
66 match tcx
.map
.find(impl_node_id
) {
67 Some(ast_map
::NodeItem(item
)) =>
68 item_might_be_inlined(&item
),
70 span_bug
!(impl_item
.span
, "impl did is not an item")
73 span_bug
!(impl_item
.span
, "found a foreign impl as a parent of a local method")
77 // Information needed while computing reachability.
78 struct ReachableContext
<'a
, 'tcx
: 'a
> {
80 tcx
: &'a TyCtxt
<'tcx
>,
81 // The set of items which must be exported in the linkage sense.
82 reachable_symbols
: NodeSet
,
83 // A worklist of item IDs. Each item ID in this worklist will be inlined
84 // and will be scanned for further references.
85 worklist
: Vec
<ast
::NodeId
>,
86 // Whether any output of this compilation is a library
90 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for ReachableContext
<'a
, 'tcx
> {
91 fn visit_expr(&mut self, expr
: &hir
::Expr
) {
93 hir
::ExprPath(..) => {
94 let def
= match self.tcx
.def_map
.borrow().get(&expr
.id
) {
95 Some(d
) => d
.full_def(),
97 span_bug
!(expr
.span
, "def ID not in def map?!")
101 let def_id
= def
.def_id();
102 if let Some(node_id
) = self.tcx
.map
.as_local_node_id(def_id
) {
103 if self.def_id_represents_local_inlined_item(def_id
) {
104 self.worklist
.push(node_id
);
107 // If this path leads to a constant, then we need to
108 // recurse into the constant to continue finding
109 // items that are reachable.
110 Def
::Const(..) | Def
::AssociatedConst(..) => {
111 self.worklist
.push(node_id
);
114 // If this wasn't a static, then the destination is
117 self.reachable_symbols
.insert(node_id
);
123 hir
::ExprMethodCall(..) => {
124 let method_call
= ty
::MethodCall
::expr(expr
.id
);
125 let def_id
= self.tcx
.tables
.borrow().method_map
[&method_call
].def_id
;
127 // Mark the trait item (and, possibly, its default impl) as reachable
128 // Or mark inherent impl item as reachable
129 if let Some(node_id
) = self.tcx
.map
.as_local_node_id(def_id
) {
130 if self.def_id_represents_local_inlined_item(def_id
) {
131 self.worklist
.push(node_id
)
133 self.reachable_symbols
.insert(node_id
);
139 intravisit
::walk_expr(self, expr
)
143 impl<'a
, 'tcx
> ReachableContext
<'a
, 'tcx
> {
144 // Creates a new reachability computation context.
145 fn new(tcx
: &'a TyCtxt
<'tcx
>) -> ReachableContext
<'a
, 'tcx
> {
146 let any_library
= tcx
.sess
.crate_types
.borrow().iter().any(|ty
| {
147 *ty
!= config
::CrateTypeExecutable
151 reachable_symbols
: NodeSet(),
152 worklist
: Vec
::new(),
153 any_library
: any_library
,
157 // Returns true if the given def ID represents a local item that is
158 // eligible for inlining and false otherwise.
159 fn def_id_represents_local_inlined_item(&self, def_id
: DefId
) -> bool
{
160 let node_id
= match self.tcx
.map
.as_local_node_id(def_id
) {
161 Some(node_id
) => node_id
,
162 None
=> { return false; }
165 match self.tcx
.map
.find(node_id
) {
166 Some(ast_map
::NodeItem(item
)) => {
168 hir
::ItemFn(..) => item_might_be_inlined(&item
),
172 Some(ast_map
::NodeTraitItem(trait_method
)) => {
173 match trait_method
.node
{
174 hir
::ConstTraitItem(_
, ref default) => default.is_some(),
175 hir
::MethodTraitItem(_
, ref body
) => body
.is_some(),
176 hir
::TypeTraitItem(..) => false,
179 Some(ast_map
::NodeImplItem(impl_item
)) => {
180 match impl_item
.node
{
181 hir
::ImplItemKind
::Const(..) => true,
182 hir
::ImplItemKind
::Method(ref sig
, _
) => {
183 if generics_require_inlining(&sig
.generics
) ||
184 attr
::requests_inline(&impl_item
.attrs
) {
187 let impl_did
= self.tcx
189 .get_parent_did(node_id
);
190 // Check the impl. If the generics on the self
191 // type of the impl require inlining, this method
193 let impl_node_id
= self.tcx
.map
.as_local_node_id(impl_did
).unwrap();
194 match self.tcx
.map
.expect_item(impl_node_id
).node
{
195 hir
::ItemImpl(_
, _
, ref generics
, _
, _
, _
) => {
196 generics_require_inlining(generics
)
202 hir
::ImplItemKind
::Type(_
) => false,
206 None
=> false // This will happen for default methods.
210 // Step 2: Mark all symbols that the symbols on the worklist touch.
211 fn propagate(&mut self) {
212 let mut scanned
= HashSet
::new();
214 let search_item
= match self.worklist
.pop() {
218 if !scanned
.insert(search_item
) {
222 if let Some(ref item
) = self.tcx
.map
.find(search_item
) {
223 self.propagate_node(item
, search_item
);
228 fn propagate_node(&mut self, node
: &ast_map
::Node
,
229 search_item
: ast
::NodeId
) {
230 if !self.any_library
{
231 // If we are building an executable, only explicitly extern
232 // types need to be exported.
233 if let ast_map
::NodeItem(item
) = *node
{
234 let reachable
= if let hir
::ItemFn(_
, _
, _
, abi
, _
, _
) = item
.node
{
239 let is_extern
= attr
::contains_extern_indicator(&self.tcx
.sess
.diagnostic(),
241 if reachable
|| is_extern
{
242 self.reachable_symbols
.insert(search_item
);
246 // If we are building a library, then reachable symbols will
247 // continue to participate in linkage after this product is
248 // produced. In this case, we traverse the ast node, recursing on
249 // all reachable nodes from this one.
250 self.reachable_symbols
.insert(search_item
);
254 ast_map
::NodeItem(item
) => {
256 hir
::ItemFn(_
, _
, _
, _
, _
, ref search_block
) => {
257 if item_might_be_inlined(&item
) {
258 intravisit
::walk_block(self, &search_block
)
262 // Reachable constants will be inlined into other crates
263 // unconditionally, so we need to make sure that their
264 // contents are also reachable.
265 hir
::ItemConst(_
, ref init
) => {
266 self.visit_expr(&init
);
269 // These are normal, nothing reachable about these
270 // inherently and their children are already in the
271 // worklist, as determined by the privacy pass
272 hir
::ItemExternCrate(_
) | hir
::ItemUse(_
) |
273 hir
::ItemTy(..) | hir
::ItemStatic(_
, _
, _
) |
274 hir
::ItemMod(..) | hir
::ItemForeignMod(..) |
275 hir
::ItemImpl(..) | hir
::ItemTrait(..) |
276 hir
::ItemStruct(..) | hir
::ItemEnum(..) |
277 hir
::ItemDefaultImpl(..) => {}
280 ast_map
::NodeTraitItem(trait_method
) => {
281 match trait_method
.node
{
282 hir
::ConstTraitItem(_
, None
) |
283 hir
::MethodTraitItem(_
, None
) => {
284 // Keep going, nothing to get exported
286 hir
::ConstTraitItem(_
, Some(ref expr
)) => {
287 self.visit_expr(&expr
);
289 hir
::MethodTraitItem(_
, Some(ref body
)) => {
290 intravisit
::walk_block(self, body
);
292 hir
::TypeTraitItem(..) => {}
295 ast_map
::NodeImplItem(impl_item
) => {
296 match impl_item
.node
{
297 hir
::ImplItemKind
::Const(_
, ref expr
) => {
298 self.visit_expr(&expr
);
300 hir
::ImplItemKind
::Method(ref sig
, ref body
) => {
301 let did
= self.tcx
.map
.get_parent_did(search_item
);
302 if method_might_be_inlined(self.tcx
, sig
, impl_item
, did
) {
303 intravisit
::walk_block(self, body
)
306 hir
::ImplItemKind
::Type(_
) => {}
309 // Nothing to recurse on for these
310 ast_map
::NodeForeignItem(_
) |
311 ast_map
::NodeVariant(_
) |
312 ast_map
::NodeStructCtor(_
) => {}
314 bug
!("found unexpected thingy in worklist: {}",
315 self.tcx
.map
.node_to_string(search_item
))
321 // Some methods from non-exported (completely private) trait impls still have to be
322 // reachable if they are called from inlinable code. Generally, it's not known until
323 // monomorphization if a specific trait impl item can be reachable or not. So, we
324 // conservatively mark all of them as reachable.
325 // FIXME: One possible strategy for pruning the reachable set is to avoid marking impl
326 // items of non-exported traits (or maybe all local traits?) unless their respective
327 // trait items are used from inlinable code through method call syntax or UFCS, or their
328 // trait is a lang item.
329 struct CollectPrivateImplItemsVisitor
<'a
> {
330 access_levels
: &'a privacy
::AccessLevels
,
331 worklist
: &'a
mut Vec
<ast
::NodeId
>,
334 impl<'a
, 'v
> Visitor
<'v
> for CollectPrivateImplItemsVisitor
<'a
> {
335 fn visit_item(&mut self, item
: &hir
::Item
) {
336 // We need only trait impls here, not inherent impls, and only non-exported ones
337 if let hir
::ItemImpl(_
, _
, _
, Some(_
), _
, ref impl_items
) = item
.node
{
338 if !self.access_levels
.is_reachable(item
.id
) {
339 for impl_item
in impl_items
{
340 self.worklist
.push(impl_item
.id
);
347 pub fn find_reachable(tcx
: &TyCtxt
,
348 access_levels
: &privacy
::AccessLevels
)
350 let _task
= tcx
.dep_graph
.in_task(DepNode
::Reachability
);
352 let mut reachable_context
= ReachableContext
::new(tcx
);
354 // Step 1: Seed the worklist with all nodes which were found to be public as
355 // a result of the privacy pass along with all local lang items and impl items.
356 // If other crates link to us, they're going to expect to be able to
357 // use the lang items, so we need to be sure to mark them as
359 for (id
, _
) in &access_levels
.map
{
360 reachable_context
.worklist
.push(*id
);
362 for item
in tcx
.lang_items
.items().iter() {
363 if let Some(did
) = *item
{
364 if let Some(node_id
) = tcx
.map
.as_local_node_id(did
) {
365 reachable_context
.worklist
.push(node_id
);
370 let mut collect_private_impl_items
= CollectPrivateImplItemsVisitor
{
371 access_levels
: access_levels
,
372 worklist
: &mut reachable_context
.worklist
,
374 tcx
.map
.krate().visit_all_items(&mut collect_private_impl_items
);
377 // Step 2: Mark all symbols that the symbols on the worklist touch.
378 reachable_context
.propagate();
380 // Return the set of reachable symbols.
381 reachable_context
.reachable_symbols