1 // Copyright 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 // This implements the dead-code warning pass. It follows middle::reachable
12 // closely. The idea is that all reachable symbols are live, codes called
13 // from live codes are live, and everything else is dead.
15 use dep_graph
::DepNode
;
16 use hir
::map
as ast_map
;
17 use hir
::{self, pat_util, PatKind}
;
18 use hir
::intravisit
::{self, Visitor}
;
21 use ty
::{self, TyCtxt}
;
23 use hir
::def_id
::{DefId}
;
26 use std
::collections
::HashSet
;
27 use syntax
::{ast, codemap}
;
28 use syntax
::attr
::{self, AttrMetaMethods}
;
30 // Any local node that may call something in its body block should be
31 // explored. For example, if it's a live NodeItem that is a
32 // function, then we should explore its block to check for codes that
33 // may need to be marked as live.
34 fn should_explore(tcx
: &TyCtxt
, node_id
: ast
::NodeId
) -> bool
{
35 match tcx
.map
.find(node_id
) {
36 Some(ast_map
::NodeItem(..)) |
37 Some(ast_map
::NodeImplItem(..)) |
38 Some(ast_map
::NodeForeignItem(..)) |
39 Some(ast_map
::NodeTraitItem(..)) =>
46 struct MarkSymbolVisitor
<'a
, 'tcx
: 'a
> {
47 worklist
: Vec
<ast
::NodeId
>,
48 tcx
: &'a TyCtxt
<'tcx
>,
49 live_symbols
: Box
<HashSet
<ast
::NodeId
>>,
50 struct_has_extern_repr
: bool
,
51 ignore_non_const_paths
: bool
,
52 inherited_pub_visibility
: bool
,
53 ignore_variant_stack
: Vec
<DefId
>,
56 impl<'a
, 'tcx
> MarkSymbolVisitor
<'a
, 'tcx
> {
57 fn new(tcx
: &'a TyCtxt
<'tcx
>,
58 worklist
: Vec
<ast
::NodeId
>) -> MarkSymbolVisitor
<'a
, 'tcx
> {
62 live_symbols
: box HashSet
::new(),
63 struct_has_extern_repr
: false,
64 ignore_non_const_paths
: false,
65 inherited_pub_visibility
: false,
66 ignore_variant_stack
: vec
![],
70 fn check_def_id(&mut self, def_id
: DefId
) {
71 if let Some(node_id
) = self.tcx
.map
.as_local_node_id(def_id
) {
72 if should_explore(self.tcx
, node_id
) {
73 self.worklist
.push(node_id
);
75 self.live_symbols
.insert(node_id
);
79 fn insert_def_id(&mut self, def_id
: DefId
) {
80 if let Some(node_id
) = self.tcx
.map
.as_local_node_id(def_id
) {
81 debug_assert
!(!should_explore(self.tcx
, node_id
));
82 self.live_symbols
.insert(node_id
);
86 fn lookup_and_handle_definition(&mut self, id
: &ast
::NodeId
) {
87 use ty
::TypeVariants
::{TyEnum, TyStruct}
;
89 // If `bar` is a trait item, make sure to mark Foo as alive in `Foo::bar`
90 self.tcx
.tables
.borrow().item_substs
.get(id
)
91 .and_then(|substs
| substs
.substs
.self_ty())
92 .map(|ty
| match ty
.sty
{
93 TyEnum(tyid
, _
) | TyStruct(tyid
, _
) => self.check_def_id(tyid
.did
),
97 self.tcx
.def_map
.borrow().get(id
).map(|def
| {
98 match def
.full_def() {
99 Def
::Const(_
) | Def
::AssociatedConst(..) => {
100 self.check_def_id(def
.def_id());
102 _
if self.ignore_non_const_paths
=> (),
103 Def
::PrimTy(_
) => (),
104 Def
::SelfTy(..) => (),
105 Def
::Variant(enum_id
, variant_id
) => {
106 self.check_def_id(enum_id
);
107 if !self.ignore_variant_stack
.contains(&variant_id
) {
108 self.check_def_id(variant_id
);
112 self.check_def_id(def
.def_id());
118 fn lookup_and_handle_method(&mut self, id
: ast
::NodeId
) {
119 let method_call
= ty
::MethodCall
::expr(id
);
120 let method
= self.tcx
.tables
.borrow().method_map
[&method_call
];
121 self.check_def_id(method
.def_id
);
124 fn handle_field_access(&mut self, lhs
: &hir
::Expr
, name
: ast
::Name
) {
125 if let ty
::TyStruct(def
, _
) = self.tcx
.expr_ty_adjusted(lhs
).sty
{
126 self.insert_def_id(def
.struct_variant().field_named(name
).did
);
128 span_bug
!(lhs
.span
, "named field access on non-struct")
132 fn handle_tup_field_access(&mut self, lhs
: &hir
::Expr
, idx
: usize) {
133 if let ty
::TyStruct(def
, _
) = self.tcx
.expr_ty_adjusted(lhs
).sty
{
134 self.insert_def_id(def
.struct_variant().fields
[idx
].did
);
138 fn handle_field_pattern_match(&mut self, lhs
: &hir
::Pat
,
139 pats
: &[codemap
::Spanned
<hir
::FieldPat
>]) {
140 let def
= self.tcx
.def_map
.borrow().get(&lhs
.id
).unwrap().full_def();
141 let pat_ty
= self.tcx
.node_id_to_type(lhs
.id
);
142 let variant
= match pat_ty
.sty
{
143 ty
::TyStruct(adt
, _
) | ty
::TyEnum(adt
, _
) => adt
.variant_of_def(def
),
144 _
=> span_bug
!(lhs
.span
, "non-ADT in struct pattern")
147 if let PatKind
::Wild
= pat
.node
.pat
.node
{
150 self.insert_def_id(variant
.field_named(pat
.node
.name
).did
);
154 fn mark_live_symbols(&mut self) {
155 let mut scanned
= HashSet
::new();
156 while !self.worklist
.is_empty() {
157 let id
= self.worklist
.pop().unwrap();
158 if scanned
.contains(&id
) {
163 match self.tcx
.map
.find(id
) {
165 self.live_symbols
.insert(id
);
166 self.visit_node(node
);
173 fn visit_node(&mut self, node
: &ast_map
::Node
) {
174 let had_extern_repr
= self.struct_has_extern_repr
;
175 self.struct_has_extern_repr
= false;
176 let had_inherited_pub_visibility
= self.inherited_pub_visibility
;
177 self.inherited_pub_visibility
= false;
179 ast_map
::NodeItem(item
) => {
181 hir
::ItemStruct(..) => {
182 self.struct_has_extern_repr
= item
.attrs
.iter().any(|attr
| {
183 attr
::find_repr_attrs(self.tcx
.sess
.diagnostic(), attr
)
184 .contains(&attr
::ReprExtern
)
187 intravisit
::walk_item(self, &item
);
189 hir
::ItemEnum(..) => {
190 self.inherited_pub_visibility
= item
.vis
== hir
::Public
;
191 intravisit
::walk_item(self, &item
);
195 | hir
::ItemStatic(..)
196 | hir
::ItemConst(..) => {
197 intravisit
::walk_item(self, &item
);
202 ast_map
::NodeTraitItem(trait_item
) => {
203 intravisit
::walk_trait_item(self, trait_item
);
205 ast_map
::NodeImplItem(impl_item
) => {
206 intravisit
::walk_impl_item(self, impl_item
);
208 ast_map
::NodeForeignItem(foreign_item
) => {
209 intravisit
::walk_foreign_item(self, &foreign_item
);
213 self.struct_has_extern_repr
= had_extern_repr
;
214 self.inherited_pub_visibility
= had_inherited_pub_visibility
;
218 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for MarkSymbolVisitor
<'a
, 'tcx
> {
220 fn visit_variant_data(&mut self, def
: &hir
::VariantData
, _
: ast
::Name
,
221 _
: &hir
::Generics
, _
: ast
::NodeId
, _
: codemap
::Span
) {
222 let has_extern_repr
= self.struct_has_extern_repr
;
223 let inherited_pub_visibility
= self.inherited_pub_visibility
;
224 let live_fields
= def
.fields().iter().filter(|f
| {
225 has_extern_repr
|| inherited_pub_visibility
|| f
.vis
== hir
::Public
227 self.live_symbols
.extend(live_fields
.map(|f
| f
.id
));
229 intravisit
::walk_struct_def(self, def
);
232 fn visit_expr(&mut self, expr
: &hir
::Expr
) {
234 hir
::ExprMethodCall(..) => {
235 self.lookup_and_handle_method(expr
.id
);
237 hir
::ExprField(ref lhs
, ref name
) => {
238 self.handle_field_access(&lhs
, name
.node
);
240 hir
::ExprTupField(ref lhs
, idx
) => {
241 self.handle_tup_field_access(&lhs
, idx
.node
);
246 intravisit
::walk_expr(self, expr
);
249 fn visit_arm(&mut self, arm
: &hir
::Arm
) {
250 if arm
.pats
.len() == 1 {
251 let pat
= &*arm
.pats
[0];
252 let variants
= pat_util
::necessary_variants(&self.tcx
.def_map
.borrow(), pat
);
254 // Inside the body, ignore constructions of variants
255 // necessary for the pattern to match. Those construction sites
256 // can't be reached unless the variant is constructed elsewhere.
257 let len
= self.ignore_variant_stack
.len();
258 self.ignore_variant_stack
.extend_from_slice(&variants
);
259 intravisit
::walk_arm(self, arm
);
260 self.ignore_variant_stack
.truncate(len
);
262 intravisit
::walk_arm(self, arm
);
266 fn visit_pat(&mut self, pat
: &hir
::Pat
) {
267 let def_map
= &self.tcx
.def_map
;
269 PatKind
::Struct(_
, ref fields
, _
) => {
270 self.handle_field_pattern_match(pat
, fields
);
272 _
if pat_util
::pat_is_const(&def_map
.borrow(), pat
) => {
273 // it might be the only use of a const
274 self.lookup_and_handle_definition(&pat
.id
)
279 self.ignore_non_const_paths
= true;
280 intravisit
::walk_pat(self, pat
);
281 self.ignore_non_const_paths
= false;
284 fn visit_path(&mut self, path
: &hir
::Path
, id
: ast
::NodeId
) {
285 self.lookup_and_handle_definition(&id
);
286 intravisit
::walk_path(self, path
);
289 fn visit_path_list_item(&mut self, path
: &hir
::Path
, item
: &hir
::PathListItem
) {
290 self.lookup_and_handle_definition(&item
.node
.id());
291 intravisit
::walk_path_list_item(self, path
, item
);
295 fn has_allow_dead_code_or_lang_attr(attrs
: &[ast
::Attribute
]) -> bool
{
296 if attr
::contains_name(attrs
, "lang") {
300 let dead_code
= lint
::builtin
::DEAD_CODE
.name_lower();
301 for attr
in lint
::gather_attrs(attrs
) {
303 Ok((ref name
, lint
::Allow
, _
))
304 if &name
[..] == dead_code
=> return true,
311 // This visitor seeds items that
312 // 1) We want to explicitly consider as live:
313 // * Item annotated with #[allow(dead_code)]
314 // - This is done so that if we want to suppress warnings for a
315 // group of dead functions, we only have to annotate the "root".
316 // For example, if both `f` and `g` are dead and `f` calls `g`,
317 // then annotating `f` with `#[allow(dead_code)]` will suppress
318 // warning for both `f` and `g`.
319 // * Item annotated with #[lang=".."]
320 // - This is because lang items are always callable from elsewhere.
322 // 2) We are not sure to be live or not
323 // * Implementation of a trait method
325 worklist
: Vec
<ast
::NodeId
>
328 impl<'v
> Visitor
<'v
> for LifeSeeder
{
329 fn visit_item(&mut self, item
: &hir
::Item
) {
330 let allow_dead_code
= has_allow_dead_code_or_lang_attr(&item
.attrs
);
332 self.worklist
.push(item
.id
);
335 hir
::ItemEnum(ref enum_def
, _
) if allow_dead_code
=> {
336 self.worklist
.extend(enum_def
.variants
.iter()
337 .map(|variant
| variant
.node
.data
.id()));
339 hir
::ItemTrait(_
, _
, _
, ref trait_items
) => {
340 for trait_item
in trait_items
{
341 match trait_item
.node
{
342 hir
::ConstTraitItem(_
, Some(_
)) |
343 hir
::MethodTraitItem(_
, Some(_
)) => {
344 if has_allow_dead_code_or_lang_attr(&trait_item
.attrs
) {
345 self.worklist
.push(trait_item
.id
);
352 hir
::ItemImpl(_
, _
, _
, ref opt_trait
, _
, ref impl_items
) => {
353 for impl_item
in impl_items
{
354 if opt_trait
.is_some() ||
355 has_allow_dead_code_or_lang_attr(&impl_item
.attrs
) {
356 self.worklist
.push(impl_item
.id
);
365 fn create_and_seed_worklist(tcx
: &TyCtxt
,
366 access_levels
: &privacy
::AccessLevels
,
367 krate
: &hir
::Crate
) -> Vec
<ast
::NodeId
> {
368 let mut worklist
= Vec
::new();
369 for (id
, _
) in &access_levels
.map
{
374 match *tcx
.sess
.entry_fn
.borrow() {
375 Some((id
, _
)) => worklist
.push(id
),
379 // Seed implemented trait items
380 let mut life_seeder
= LifeSeeder
{
383 krate
.visit_all_items(&mut life_seeder
);
385 return life_seeder
.worklist
;
388 fn find_live(tcx
: &TyCtxt
,
389 access_levels
: &privacy
::AccessLevels
,
391 -> Box
<HashSet
<ast
::NodeId
>> {
392 let worklist
= create_and_seed_worklist(tcx
, access_levels
, krate
);
393 let mut symbol_visitor
= MarkSymbolVisitor
::new(tcx
, worklist
);
394 symbol_visitor
.mark_live_symbols();
395 symbol_visitor
.live_symbols
398 fn get_struct_ctor_id(item
: &hir
::Item
) -> Option
<ast
::NodeId
> {
400 hir
::ItemStruct(ref struct_def
, _
) if !struct_def
.is_struct() => {
401 Some(struct_def
.id())
407 struct DeadVisitor
<'a
, 'tcx
: 'a
> {
408 tcx
: &'a TyCtxt
<'tcx
>,
409 live_symbols
: Box
<HashSet
<ast
::NodeId
>>,
412 impl<'a
, 'tcx
> DeadVisitor
<'a
, 'tcx
> {
413 fn should_warn_about_item(&mut self, item
: &hir
::Item
) -> bool
{
414 let should_warn
= match item
.node
{
419 | hir
::ItemStruct(..) => true,
422 let ctor_id
= get_struct_ctor_id(item
);
423 should_warn
&& !self.symbol_is_live(item
.id
, ctor_id
)
426 fn should_warn_about_field(&mut self, field
: &hir
::StructField
) -> bool
{
427 let field_type
= self.tcx
.node_id_to_type(field
.id
);
428 let is_marker_field
= match field_type
.ty_to_def_id() {
429 Some(def_id
) => self.tcx
.lang_items
.items().iter().any(|item
| *item
== Some(def_id
)),
432 !field
.is_positional()
433 && !self.symbol_is_live(field
.id
, None
)
435 && !has_allow_dead_code_or_lang_attr(&field
.attrs
)
438 fn should_warn_about_variant(&mut self, variant
: &hir
::Variant_
) -> bool
{
439 !self.symbol_is_live(variant
.data
.id(), None
)
440 && !has_allow_dead_code_or_lang_attr(&variant
.attrs
)
443 // id := node id of an item's definition.
444 // ctor_id := `Some` if the item is a struct_ctor (tuple struct),
446 // If the item is a struct_ctor, then either its `id` or
447 // `ctor_id` (unwrapped) is in the live_symbols set. More specifically,
448 // DefMap maps the ExprPath of a struct_ctor to the node referred by
449 // `ctor_id`. On the other hand, in a statement like
450 // `type <ident> <generics> = <ty>;` where <ty> refers to a struct_ctor,
451 // DefMap maps <ty> to `id` instead.
452 fn symbol_is_live(&mut self,
454 ctor_id
: Option
<ast
::NodeId
>)
456 if self.live_symbols
.contains(&id
)
457 || ctor_id
.map_or(false,
458 |ctor
| self.live_symbols
.contains(&ctor
)) {
461 // If it's a type whose items are live, then it's live, too.
462 // This is done to handle the case where, for example, the static
463 // method of a private type is used, but the type itself is never
465 let impl_items
= self.tcx
.impl_items
.borrow();
466 match self.tcx
.inherent_impls
.borrow().get(&self.tcx
.map
.local_def_id(id
)) {
469 for impl_did
in impl_list
.iter() {
470 for item_did
in impl_items
.get(impl_did
).unwrap().iter() {
471 if let Some(item_node_id
) =
472 self.tcx
.map
.as_local_node_id(item_did
.def_id()) {
473 if self.live_symbols
.contains(&item_node_id
) {
484 fn warn_dead_code(&mut self,
489 let name
= name
.as_str();
490 if !name
.starts_with("_") {
493 .add_lint(lint
::builtin
::DEAD_CODE
,
496 format
!("{} is never used: `{}`", node_type
, name
));
501 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for DeadVisitor
<'a
, 'tcx
> {
502 /// Walk nested items in place so that we don't report dead-code
503 /// on inner functions when the outer function is already getting
504 /// an error. We could do this also by checking the parents, but
505 /// this is how the code is setup and it seems harmless enough.
506 fn visit_nested_item(&mut self, item
: hir
::ItemId
) {
507 self.visit_item(self.tcx
.map
.expect_item(item
.id
))
510 fn visit_item(&mut self, item
: &hir
::Item
) {
511 if self.should_warn_about_item(item
) {
516 item
.node
.descriptive_variant()
519 // Only continue if we didn't warn
520 intravisit
::walk_item(self, item
);
524 fn visit_variant(&mut self, variant
: &hir
::Variant
, g
: &hir
::Generics
, id
: ast
::NodeId
) {
525 if self.should_warn_about_variant(&variant
.node
) {
526 self.warn_dead_code(variant
.node
.data
.id(), variant
.span
,
527 variant
.node
.name
, "variant");
529 intravisit
::walk_variant(self, variant
, g
, id
);
533 fn visit_foreign_item(&mut self, fi
: &hir
::ForeignItem
) {
534 if !self.symbol_is_live(fi
.id
, None
) {
535 self.warn_dead_code(fi
.id
, fi
.span
, fi
.name
, fi
.node
.descriptive_variant());
537 intravisit
::walk_foreign_item(self, fi
);
540 fn visit_struct_field(&mut self, field
: &hir
::StructField
) {
541 if self.should_warn_about_field(&field
) {
542 self.warn_dead_code(field
.id
, field
.span
,
543 field
.name
, "struct field");
546 intravisit
::walk_struct_field(self, field
);
549 fn visit_impl_item(&mut self, impl_item
: &hir
::ImplItem
) {
550 match impl_item
.node
{
551 hir
::ImplItemKind
::Const(_
, ref expr
) => {
552 if !self.symbol_is_live(impl_item
.id
, None
) {
553 self.warn_dead_code(impl_item
.id
, impl_item
.span
,
554 impl_item
.name
, "associated const");
556 intravisit
::walk_expr(self, expr
)
558 hir
::ImplItemKind
::Method(_
, ref body
) => {
559 if !self.symbol_is_live(impl_item
.id
, None
) {
560 self.warn_dead_code(impl_item
.id
, impl_item
.span
,
561 impl_item
.name
, "method");
563 intravisit
::walk_block(self, body
)
565 hir
::ImplItemKind
::Type(..) => {}
569 // Overwrite so that we don't warn the trait item itself.
570 fn visit_trait_item(&mut self, trait_item
: &hir
::TraitItem
) {
571 match trait_item
.node
{
572 hir
::ConstTraitItem(_
, Some(ref expr
)) => {
573 intravisit
::walk_expr(self, expr
)
575 hir
::MethodTraitItem(_
, Some(ref body
)) => {
576 intravisit
::walk_block(self, body
)
578 hir
::ConstTraitItem(_
, None
) |
579 hir
::MethodTraitItem(_
, None
) |
580 hir
::TypeTraitItem(..) => {}
585 pub fn check_crate(tcx
: &TyCtxt
, access_levels
: &privacy
::AccessLevels
) {
586 let _task
= tcx
.dep_graph
.in_task(DepNode
::DeadCheck
);
587 let krate
= tcx
.map
.krate();
588 let live_symbols
= find_live(tcx
, access_levels
, krate
);
589 let mut visitor
= DeadVisitor { tcx: tcx, live_symbols: live_symbols }
;
590 intravisit
::walk_crate(&mut visitor
, krate
);