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 front
::map
as ast_map
;
17 use rustc_front
::intravisit
::{self, Visitor}
;
19 use middle
::{def, pat_util, privacy, ty}
;
20 use middle
::def_id
::{DefId}
;
23 use std
::collections
::HashSet
;
24 use syntax
::{ast, codemap}
;
25 use syntax
::attr
::{self, AttrMetaMethods}
;
27 // Any local node that may call something in its body block should be
28 // explored. For example, if it's a live NodeItem that is a
29 // function, then we should explore its block to check for codes that
30 // may need to be marked as live.
31 fn should_explore(tcx
: &ty
::ctxt
, node_id
: ast
::NodeId
) -> bool
{
32 match tcx
.map
.find(node_id
) {
33 Some(ast_map
::NodeItem(..)) |
34 Some(ast_map
::NodeImplItem(..)) |
35 Some(ast_map
::NodeForeignItem(..)) |
36 Some(ast_map
::NodeTraitItem(..)) =>
43 struct MarkSymbolVisitor
<'a
, 'tcx
: 'a
> {
44 worklist
: Vec
<ast
::NodeId
>,
45 tcx
: &'a ty
::ctxt
<'tcx
>,
46 live_symbols
: Box
<HashSet
<ast
::NodeId
>>,
47 struct_has_extern_repr
: bool
,
48 ignore_non_const_paths
: bool
,
49 inherited_pub_visibility
: bool
,
50 ignore_variant_stack
: Vec
<DefId
>,
53 impl<'a
, 'tcx
> MarkSymbolVisitor
<'a
, 'tcx
> {
54 fn new(tcx
: &'a ty
::ctxt
<'tcx
>,
55 worklist
: Vec
<ast
::NodeId
>) -> MarkSymbolVisitor
<'a
, 'tcx
> {
59 live_symbols
: box HashSet
::new(),
60 struct_has_extern_repr
: false,
61 ignore_non_const_paths
: false,
62 inherited_pub_visibility
: false,
63 ignore_variant_stack
: vec
![],
67 fn check_def_id(&mut self, def_id
: DefId
) {
68 if let Some(node_id
) = self.tcx
.map
.as_local_node_id(def_id
) {
69 if should_explore(self.tcx
, node_id
) {
70 self.worklist
.push(node_id
);
72 self.live_symbols
.insert(node_id
);
76 fn insert_def_id(&mut self, def_id
: DefId
) {
77 if let Some(node_id
) = self.tcx
.map
.as_local_node_id(def_id
) {
78 debug_assert
!(!should_explore(self.tcx
, node_id
));
79 self.live_symbols
.insert(node_id
);
83 fn lookup_and_handle_definition(&mut self, id
: &ast
::NodeId
) {
84 use middle
::ty
::TypeVariants
::{TyEnum, TyStruct}
;
86 // If `bar` is a trait item, make sure to mark Foo as alive in `Foo::bar`
87 self.tcx
.tables
.borrow().item_substs
.get(id
)
88 .and_then(|substs
| substs
.substs
.self_ty())
89 .map(|ty
| match ty
.sty
{
90 TyEnum(tyid
, _
) | TyStruct(tyid
, _
) => self.check_def_id(tyid
.did
),
94 self.tcx
.def_map
.borrow().get(id
).map(|def
| {
95 match def
.full_def() {
96 def
::DefConst(_
) | def
::DefAssociatedConst(..) => {
97 self.check_def_id(def
.def_id());
99 _
if self.ignore_non_const_paths
=> (),
100 def
::DefPrimTy(_
) => (),
101 def
::DefSelfTy(..) => (),
102 def
::DefVariant(enum_id
, variant_id
, _
) => {
103 self.check_def_id(enum_id
);
104 if !self.ignore_variant_stack
.contains(&variant_id
) {
105 self.check_def_id(variant_id
);
109 self.check_def_id(def
.def_id());
115 fn lookup_and_handle_method(&mut self, id
: ast
::NodeId
) {
116 let method_call
= ty
::MethodCall
::expr(id
);
117 let method
= self.tcx
.tables
.borrow().method_map
[&method_call
];
118 self.check_def_id(method
.def_id
);
121 fn handle_field_access(&mut self, lhs
: &hir
::Expr
, name
: ast
::Name
) {
122 if let ty
::TyStruct(def
, _
) = self.tcx
.expr_ty_adjusted(lhs
).sty
{
123 self.insert_def_id(def
.struct_variant().field_named(name
).did
);
125 self.tcx
.sess
.span_bug(lhs
.span
, "named field access on non-struct")
129 fn handle_tup_field_access(&mut self, lhs
: &hir
::Expr
, idx
: usize) {
130 if let ty
::TyStruct(def
, _
) = self.tcx
.expr_ty_adjusted(lhs
).sty
{
131 self.insert_def_id(def
.struct_variant().fields
[idx
].did
);
135 fn handle_field_pattern_match(&mut self, lhs
: &hir
::Pat
,
136 pats
: &[codemap
::Spanned
<hir
::FieldPat
>]) {
137 let def
= self.tcx
.def_map
.borrow().get(&lhs
.id
).unwrap().full_def();
138 let pat_ty
= self.tcx
.node_id_to_type(lhs
.id
);
139 let variant
= match pat_ty
.sty
{
140 ty
::TyStruct(adt
, _
) | ty
::TyEnum(adt
, _
) => adt
.variant_of_def(def
),
141 _
=> self.tcx
.sess
.span_bug(lhs
.span
, "non-ADT in struct pattern")
144 if let hir
::PatWild
= pat
.node
.pat
.node
{
147 self.insert_def_id(variant
.field_named(pat
.node
.name
).did
);
151 fn mark_live_symbols(&mut self) {
152 let mut scanned
= HashSet
::new();
153 while !self.worklist
.is_empty() {
154 let id
= self.worklist
.pop().unwrap();
155 if scanned
.contains(&id
) {
160 match self.tcx
.map
.find(id
) {
162 self.live_symbols
.insert(id
);
163 self.visit_node(node
);
170 fn visit_node(&mut self, node
: &ast_map
::Node
) {
171 let had_extern_repr
= self.struct_has_extern_repr
;
172 self.struct_has_extern_repr
= false;
173 let had_inherited_pub_visibility
= self.inherited_pub_visibility
;
174 self.inherited_pub_visibility
= false;
176 ast_map
::NodeItem(item
) => {
178 hir
::ItemStruct(..) => {
179 self.struct_has_extern_repr
= item
.attrs
.iter().any(|attr
| {
180 attr
::find_repr_attrs(self.tcx
.sess
.diagnostic(), attr
)
181 .contains(&attr
::ReprExtern
)
184 intravisit
::walk_item(self, &*item
);
186 hir
::ItemEnum(..) => {
187 self.inherited_pub_visibility
= item
.vis
== hir
::Public
;
188 intravisit
::walk_item(self, &*item
);
192 | hir
::ItemStatic(..)
193 | hir
::ItemConst(..) => {
194 intravisit
::walk_item(self, &*item
);
199 ast_map
::NodeTraitItem(trait_item
) => {
200 intravisit
::walk_trait_item(self, trait_item
);
202 ast_map
::NodeImplItem(impl_item
) => {
203 intravisit
::walk_impl_item(self, impl_item
);
205 ast_map
::NodeForeignItem(foreign_item
) => {
206 intravisit
::walk_foreign_item(self, &*foreign_item
);
210 self.struct_has_extern_repr
= had_extern_repr
;
211 self.inherited_pub_visibility
= had_inherited_pub_visibility
;
215 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for MarkSymbolVisitor
<'a
, 'tcx
> {
217 fn visit_variant_data(&mut self, def
: &hir
::VariantData
, _
: ast
::Name
,
218 _
: &hir
::Generics
, _
: ast
::NodeId
, _
: codemap
::Span
) {
219 let has_extern_repr
= self.struct_has_extern_repr
;
220 let inherited_pub_visibility
= self.inherited_pub_visibility
;
221 let live_fields
= def
.fields().iter().filter(|f
| {
222 has_extern_repr
|| inherited_pub_visibility
|| match f
.node
.kind
{
223 hir
::NamedField(_
, hir
::Public
) => true,
227 self.live_symbols
.extend(live_fields
.map(|f
| f
.node
.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 hir
::PatStruct(_
, 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 match impl_item
.node
{
355 hir
::ImplItemKind
::Const(..) |
356 hir
::ImplItemKind
::Method(..) => {
357 if opt_trait
.is_some() ||
358 has_allow_dead_code_or_lang_attr(&impl_item
.attrs
) {
359 self.worklist
.push(impl_item
.id
);
362 hir
::ImplItemKind
::Type(_
) => {}
371 fn create_and_seed_worklist(tcx
: &ty
::ctxt
,
372 access_levels
: &privacy
::AccessLevels
,
373 krate
: &hir
::Crate
) -> Vec
<ast
::NodeId
> {
374 let mut worklist
= Vec
::new();
375 for (id
, _
) in &access_levels
.map
{
380 match *tcx
.sess
.entry_fn
.borrow() {
381 Some((id
, _
)) => worklist
.push(id
),
385 // Seed implemented trait items
386 let mut life_seeder
= LifeSeeder
{
389 krate
.visit_all_items(&mut life_seeder
);
391 return life_seeder
.worklist
;
394 fn find_live(tcx
: &ty
::ctxt
,
395 access_levels
: &privacy
::AccessLevels
,
397 -> Box
<HashSet
<ast
::NodeId
>> {
398 let worklist
= create_and_seed_worklist(tcx
, access_levels
, krate
);
399 let mut symbol_visitor
= MarkSymbolVisitor
::new(tcx
, worklist
);
400 symbol_visitor
.mark_live_symbols();
401 symbol_visitor
.live_symbols
404 fn get_struct_ctor_id(item
: &hir
::Item
) -> Option
<ast
::NodeId
> {
406 hir
::ItemStruct(ref struct_def
, _
) if !struct_def
.is_struct() => {
407 Some(struct_def
.id())
413 struct DeadVisitor
<'a
, 'tcx
: 'a
> {
414 tcx
: &'a ty
::ctxt
<'tcx
>,
415 live_symbols
: Box
<HashSet
<ast
::NodeId
>>,
418 impl<'a
, 'tcx
> DeadVisitor
<'a
, 'tcx
> {
419 fn should_warn_about_item(&mut self, item
: &hir
::Item
) -> bool
{
420 let should_warn
= match item
.node
{
425 | hir
::ItemStruct(..) => true,
428 let ctor_id
= get_struct_ctor_id(item
);
429 should_warn
&& !self.symbol_is_live(item
.id
, ctor_id
)
432 fn should_warn_about_field(&mut self, node
: &hir
::StructField_
) -> bool
{
433 let is_named
= node
.name().is_some();
434 let field_type
= self.tcx
.node_id_to_type(node
.id
);
435 let is_marker_field
= match field_type
.ty_to_def_id() {
436 Some(def_id
) => self.tcx
.lang_items
.items().any(|(_
, item
)| *item
== Some(def_id
)),
440 && !self.symbol_is_live(node
.id
, None
)
442 && !has_allow_dead_code_or_lang_attr(&node
.attrs
)
445 fn should_warn_about_variant(&mut self, variant
: &hir
::Variant_
) -> bool
{
446 !self.symbol_is_live(variant
.data
.id(), None
)
447 && !has_allow_dead_code_or_lang_attr(&variant
.attrs
)
450 // id := node id of an item's definition.
451 // ctor_id := `Some` if the item is a struct_ctor (tuple struct),
453 // If the item is a struct_ctor, then either its `id` or
454 // `ctor_id` (unwrapped) is in the live_symbols set. More specifically,
455 // DefMap maps the ExprPath of a struct_ctor to the node referred by
456 // `ctor_id`. On the other hand, in a statement like
457 // `type <ident> <generics> = <ty>;` where <ty> refers to a struct_ctor,
458 // DefMap maps <ty> to `id` instead.
459 fn symbol_is_live(&mut self,
461 ctor_id
: Option
<ast
::NodeId
>)
463 if self.live_symbols
.contains(&id
)
464 || ctor_id
.map_or(false,
465 |ctor
| self.live_symbols
.contains(&ctor
)) {
468 // If it's a type whose items are live, then it's live, too.
469 // This is done to handle the case where, for example, the static
470 // method of a private type is used, but the type itself is never
472 let impl_items
= self.tcx
.impl_items
.borrow();
473 match self.tcx
.inherent_impls
.borrow().get(&self.tcx
.map
.local_def_id(id
)) {
476 for impl_did
in impl_list
.iter() {
477 for item_did
in impl_items
.get(impl_did
).unwrap().iter() {
478 if let Some(item_node_id
) =
479 self.tcx
.map
.as_local_node_id(item_did
.def_id()) {
480 if self.live_symbols
.contains(&item_node_id
) {
491 fn warn_dead_code(&mut self,
496 let name
= name
.as_str();
497 if !name
.starts_with("_") {
500 .add_lint(lint
::builtin
::DEAD_CODE
,
503 format
!("{} is never used: `{}`", node_type
, name
));
508 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for DeadVisitor
<'a
, 'tcx
> {
509 /// Walk nested items in place so that we don't report dead-code
510 /// on inner functions when the outer function is already getting
511 /// an error. We could do this also by checking the parents, but
512 /// this is how the code is setup and it seems harmless enough.
513 fn visit_nested_item(&mut self, item
: hir
::ItemId
) {
514 self.visit_item(self.tcx
.map
.expect_item(item
.id
))
517 fn visit_item(&mut self, item
: &hir
::Item
) {
518 if self.should_warn_about_item(item
) {
523 item
.node
.descriptive_variant()
526 // Only continue if we didn't warn
527 intravisit
::walk_item(self, item
);
531 fn visit_variant(&mut self, variant
: &hir
::Variant
, g
: &hir
::Generics
, id
: ast
::NodeId
) {
532 if self.should_warn_about_variant(&variant
.node
) {
533 self.warn_dead_code(variant
.node
.data
.id(), variant
.span
,
534 variant
.node
.name
, "variant");
536 intravisit
::walk_variant(self, variant
, g
, id
);
540 fn visit_foreign_item(&mut self, fi
: &hir
::ForeignItem
) {
541 if !self.symbol_is_live(fi
.id
, None
) {
542 self.warn_dead_code(fi
.id
, fi
.span
, fi
.name
, fi
.node
.descriptive_variant());
544 intravisit
::walk_foreign_item(self, fi
);
547 fn visit_struct_field(&mut self, field
: &hir
::StructField
) {
548 if self.should_warn_about_field(&field
.node
) {
549 self.warn_dead_code(field
.node
.id
, field
.span
,
550 field
.node
.name().unwrap(), "struct field");
553 intravisit
::walk_struct_field(self, field
);
556 fn visit_impl_item(&mut self, impl_item
: &hir
::ImplItem
) {
557 match impl_item
.node
{
558 hir
::ImplItemKind
::Const(_
, ref expr
) => {
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
, "associated const");
563 intravisit
::walk_expr(self, expr
)
565 hir
::ImplItemKind
::Method(_
, ref body
) => {
566 if !self.symbol_is_live(impl_item
.id
, None
) {
567 self.warn_dead_code(impl_item
.id
, impl_item
.span
,
568 impl_item
.name
, "method");
570 intravisit
::walk_block(self, body
)
572 hir
::ImplItemKind
::Type(..) => {}
576 // Overwrite so that we don't warn the trait item itself.
577 fn visit_trait_item(&mut self, trait_item
: &hir
::TraitItem
) {
578 match trait_item
.node
{
579 hir
::ConstTraitItem(_
, Some(ref expr
)) => {
580 intravisit
::walk_expr(self, expr
)
582 hir
::MethodTraitItem(_
, Some(ref body
)) => {
583 intravisit
::walk_block(self, body
)
585 hir
::ConstTraitItem(_
, None
) |
586 hir
::MethodTraitItem(_
, None
) |
587 hir
::TypeTraitItem(..) => {}
592 pub fn check_crate(tcx
: &ty
::ctxt
, access_levels
: &privacy
::AccessLevels
) {
593 let krate
= tcx
.map
.krate();
594 let live_symbols
= find_live(tcx
, access_levels
, krate
);
595 let mut visitor
= DeadVisitor { tcx: tcx, live_symbols: live_symbols }
;
596 intravisit
::walk_crate(&mut visitor
, krate
);