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.
16 use middle
::{def, pat_util, privacy, ty}
;
18 use util
::nodemap
::NodeSet
;
20 use std
::collections
::HashSet
;
21 use syntax
::{ast, codemap}
;
22 use syntax
::ast_util
::{local_def, is_local}
;
23 use syntax
::attr
::{self, AttrMetaMethods}
;
24 use syntax
::visit
::{self, Visitor}
;
26 // Any local node that may call something in its body block should be
27 // explored. For example, if it's a live NodeItem that is a
28 // function, then we should explore its block to check for codes that
29 // may need to be marked as live.
30 fn should_explore(tcx
: &ty
::ctxt
, def_id
: ast
::DefId
) -> bool
{
31 if !is_local(def_id
) {
35 match tcx
.map
.find(def_id
.node
) {
36 Some(ast_map
::NodeItem(..))
37 | Some(ast_map
::NodeImplItem(..))
38 | Some(ast_map
::NodeForeignItem(..))
39 | Some(ast_map
::NodeTraitItem(..)) => true,
44 struct MarkSymbolVisitor
<'a
, 'tcx
: 'a
> {
45 worklist
: Vec
<ast
::NodeId
>,
46 tcx
: &'a ty
::ctxt
<'tcx
>,
47 live_symbols
: Box
<HashSet
<ast
::NodeId
>>,
48 struct_has_extern_repr
: bool
,
49 ignore_non_const_paths
: bool
,
50 inherited_pub_visibility
: bool
,
51 ignore_variant_stack
: Vec
<ast
::NodeId
>,
54 impl<'a
, 'tcx
> MarkSymbolVisitor
<'a
, 'tcx
> {
55 fn new(tcx
: &'a ty
::ctxt
<'tcx
>,
56 worklist
: Vec
<ast
::NodeId
>) -> MarkSymbolVisitor
<'a
, 'tcx
> {
60 live_symbols
: box HashSet
::new(),
61 struct_has_extern_repr
: false,
62 ignore_non_const_paths
: false,
63 inherited_pub_visibility
: false,
64 ignore_variant_stack
: vec
![],
68 fn check_def_id(&mut self, def_id
: ast
::DefId
) {
69 if should_explore(self.tcx
, def_id
) {
70 self.worklist
.push(def_id
.node
);
72 self.live_symbols
.insert(def_id
.node
);
75 fn lookup_and_handle_definition(&mut self, id
: &ast
::NodeId
) {
76 self.tcx
.def_map
.borrow().get(id
).map(|def
| {
77 match def
.full_def() {
78 def
::DefConst(_
) | def
::DefAssociatedConst(..) => {
79 self.check_def_id(def
.def_id())
81 _
if self.ignore_non_const_paths
=> (),
82 def
::DefPrimTy(_
) => (),
83 def
::DefVariant(enum_id
, variant_id
, _
) => {
84 self.check_def_id(enum_id
);
85 if !self.ignore_variant_stack
.contains(&variant_id
.node
) {
86 self.check_def_id(variant_id
);
90 self.check_def_id(def
.def_id());
96 fn lookup_and_handle_method(&mut self, id
: ast
::NodeId
) {
97 let method_call
= ty
::MethodCall
::expr(id
);
98 let method
= self.tcx
.tables
.borrow().method_map
[&method_call
];
99 self.check_def_id(method
.def_id
);
102 fn handle_field_access(&mut self, lhs
: &ast
::Expr
, name
: ast
::Name
) {
103 match self.tcx
.expr_ty_adjusted(lhs
).sty
{
104 ty
::TyStruct(id
, _
) => {
105 let fields
= self.tcx
.lookup_struct_fields(id
);
106 let field_id
= fields
.iter()
107 .find(|field
| field
.name
== name
).unwrap().id
;
108 self.live_symbols
.insert(field_id
.node
);
114 fn handle_tup_field_access(&mut self, lhs
: &ast
::Expr
, idx
: usize) {
115 match self.tcx
.expr_ty_adjusted(lhs
).sty
{
116 ty
::TyStruct(id
, _
) => {
117 let fields
= self.tcx
.lookup_struct_fields(id
);
118 let field_id
= fields
[idx
].id
;
119 self.live_symbols
.insert(field_id
.node
);
125 fn handle_field_pattern_match(&mut self, lhs
: &ast
::Pat
,
126 pats
: &[codemap
::Spanned
<ast
::FieldPat
>]) {
127 let id
= match self.tcx
.def_map
.borrow().get(&lhs
.id
).unwrap().full_def() {
128 def
::DefVariant(_
, id
, _
) => id
,
130 match self.tcx
.node_id_to_type(lhs
.id
).ty_to_def_id() {
132 self.tcx
.sess
.span_bug(lhs
.span
,
133 "struct pattern wasn't of a \
134 type with a def ID?!")
136 Some(def_id
) => def_id
,
140 let fields
= self.tcx
.lookup_struct_fields(id
);
142 if let ast
::PatWild(ast
::PatWildSingle
) = pat
.node
.pat
.node
{
145 let field_id
= fields
.iter()
146 .find(|field
| field
.name
== pat
.node
.ident
.name
).unwrap().id
;
147 self.live_symbols
.insert(field_id
.node
);
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 ast
::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 visit
::walk_item(self, &*item
);
186 ast
::ItemEnum(..) => {
187 self.inherited_pub_visibility
= item
.vis
== ast
::Public
;
188 visit
::walk_item(self, &*item
);
192 | ast
::ItemStatic(..)
193 | ast
::ItemConst(..) => {
194 visit
::walk_item(self, &*item
);
199 ast_map
::NodeTraitItem(trait_item
) => {
200 visit
::walk_trait_item(self, trait_item
);
202 ast_map
::NodeImplItem(impl_item
) => {
203 visit
::walk_impl_item(self, impl_item
);
205 ast_map
::NodeForeignItem(foreign_item
) => {
206 visit
::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_struct_def(&mut self, def
: &ast
::StructDef
, _
: ast
::Ident
,
218 _
: &ast
::Generics
, _
: ast
::NodeId
) {
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 ast
::NamedField(_
, ast
::Public
) => true,
227 self.live_symbols
.extend(live_fields
.map(|f
| f
.node
.id
));
229 visit
::walk_struct_def(self, def
);
232 fn visit_expr(&mut self, expr
: &ast
::Expr
) {
234 ast
::ExprMethodCall(..) => {
235 self.lookup_and_handle_method(expr
.id
);
237 ast
::ExprField(ref lhs
, ref ident
) => {
238 self.handle_field_access(&**lhs
, ident
.node
.name
);
240 ast
::ExprTupField(ref lhs
, idx
) => {
241 self.handle_tup_field_access(&**lhs
, idx
.node
);
246 visit
::walk_expr(self, expr
);
249 fn visit_arm(&mut self, arm
: &ast
::Arm
) {
250 if arm
.pats
.len() == 1 {
251 let pat
= &*arm
.pats
[0];
252 let variants
= pat_util
::necessary_variants(&self.tcx
.def_map
, 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
.push_all(&*variants
);
259 visit
::walk_arm(self, arm
);
260 self.ignore_variant_stack
.truncate(len
);
262 visit
::walk_arm(self, arm
);
266 fn visit_pat(&mut self, pat
: &ast
::Pat
) {
267 let def_map
= &self.tcx
.def_map
;
269 ast
::PatStruct(_
, ref fields
, _
) => {
270 self.handle_field_pattern_match(pat
, fields
);
272 _
if pat_util
::pat_is_const(def_map
, 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 visit
::walk_pat(self, pat
);
281 self.ignore_non_const_paths
= false;
284 fn visit_path(&mut self, path
: &ast
::Path
, id
: ast
::NodeId
) {
285 self.lookup_and_handle_definition(&id
);
286 visit
::walk_path(self, path
);
289 fn visit_item(&mut self, _
: &ast
::Item
) {
290 // Do not recurse into items. These items will be added to the
291 // worklist and recursed into manually if necessary.
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
: &ast
::Item
) {
330 let allow_dead_code
= has_allow_dead_code_or_lang_attr(&item
.attrs
);
332 self.worklist
.push(item
.id
);
335 ast
::ItemEnum(ref enum_def
, _
) if allow_dead_code
=> {
336 self.worklist
.extend(enum_def
.variants
.iter().map(|variant
| variant
.node
.id
));
338 ast
::ItemTrait(_
, _
, _
, ref trait_items
) => {
339 for trait_item
in trait_items
{
340 match trait_item
.node
{
341 ast
::ConstTraitItem(_
, Some(_
)) |
342 ast
::MethodTraitItem(_
, Some(_
)) => {
343 if has_allow_dead_code_or_lang_attr(&trait_item
.attrs
) {
344 self.worklist
.push(trait_item
.id
);
351 ast
::ItemImpl(_
, _
, _
, ref opt_trait
, _
, ref impl_items
) => {
352 for impl_item
in impl_items
{
353 match impl_item
.node
{
354 ast
::ConstImplItem(..) |
355 ast
::MethodImplItem(..) => {
356 if opt_trait
.is_some() ||
357 has_allow_dead_code_or_lang_attr(&impl_item
.attrs
) {
358 self.worklist
.push(impl_item
.id
);
361 ast
::TypeImplItem(_
) => {}
362 ast
::MacImplItem(_
) => panic
!("unexpanded macro")
368 visit
::walk_item(self, item
);
372 fn create_and_seed_worklist(tcx
: &ty
::ctxt
,
373 exported_items
: &privacy
::ExportedItems
,
374 reachable_symbols
: &NodeSet
,
375 krate
: &ast
::Crate
) -> Vec
<ast
::NodeId
> {
376 let mut worklist
= Vec
::new();
378 // Preferably, we would only need to seed the worklist with reachable
379 // symbols. However, since the set of reachable symbols differs
380 // depending on whether a crate is built as bin or lib, and we want
381 // the warning to be consistent, we also seed the worklist with
383 for id
in exported_items
{
386 for id
in reachable_symbols
{
387 // Reachable variants can be dead, because we warn about
388 // variants never constructed, not variants never used.
389 if let Some(ast_map
::NodeVariant(..)) = tcx
.map
.find(*id
) {
396 match *tcx
.sess
.entry_fn
.borrow() {
397 Some((id
, _
)) => worklist
.push(id
),
401 // Seed implemented trait items
402 let mut life_seeder
= LifeSeeder
{
405 visit
::walk_crate(&mut life_seeder
, krate
);
407 return life_seeder
.worklist
;
410 fn find_live(tcx
: &ty
::ctxt
,
411 exported_items
: &privacy
::ExportedItems
,
412 reachable_symbols
: &NodeSet
,
414 -> Box
<HashSet
<ast
::NodeId
>> {
415 let worklist
= create_and_seed_worklist(tcx
, exported_items
,
416 reachable_symbols
, krate
);
417 let mut symbol_visitor
= MarkSymbolVisitor
::new(tcx
, worklist
);
418 symbol_visitor
.mark_live_symbols();
419 symbol_visitor
.live_symbols
422 fn get_struct_ctor_id(item
: &ast
::Item
) -> Option
<ast
::NodeId
> {
424 ast
::ItemStruct(ref struct_def
, _
) => struct_def
.ctor_id
,
429 struct DeadVisitor
<'a
, 'tcx
: 'a
> {
430 tcx
: &'a ty
::ctxt
<'tcx
>,
431 live_symbols
: Box
<HashSet
<ast
::NodeId
>>,
434 impl<'a
, 'tcx
> DeadVisitor
<'a
, 'tcx
> {
435 fn should_warn_about_item(&mut self, item
: &ast
::Item
) -> bool
{
436 let should_warn
= match item
.node
{
441 | ast
::ItemStruct(..) => true,
444 let ctor_id
= get_struct_ctor_id(item
);
445 should_warn
&& !self.symbol_is_live(item
.id
, ctor_id
)
448 fn should_warn_about_field(&mut self, node
: &ast
::StructField_
) -> bool
{
449 let is_named
= node
.ident().is_some();
450 let field_type
= self.tcx
.node_id_to_type(node
.id
);
451 let is_marker_field
= match field_type
.ty_to_def_id() {
452 Some(def_id
) => self.tcx
.lang_items
.items().any(|(_
, item
)| *item
== Some(def_id
)),
456 && !self.symbol_is_live(node
.id
, None
)
458 && !has_allow_dead_code_or_lang_attr(&node
.attrs
)
461 fn should_warn_about_variant(&mut self, variant
: &ast
::Variant_
) -> bool
{
462 !self.symbol_is_live(variant
.id
, None
)
463 && !has_allow_dead_code_or_lang_attr(&variant
.attrs
)
466 // id := node id of an item's definition.
467 // ctor_id := `Some` if the item is a struct_ctor (tuple struct),
469 // If the item is a struct_ctor, then either its `id` or
470 // `ctor_id` (unwrapped) is in the live_symbols set. More specifically,
471 // DefMap maps the ExprPath of a struct_ctor to the node referred by
472 // `ctor_id`. On the other hand, in a statement like
473 // `type <ident> <generics> = <ty>;` where <ty> refers to a struct_ctor,
474 // DefMap maps <ty> to `id` instead.
475 fn symbol_is_live(&mut self, id
: ast
::NodeId
,
476 ctor_id
: Option
<ast
::NodeId
>) -> bool
{
477 if self.live_symbols
.contains(&id
)
478 || ctor_id
.map_or(false,
479 |ctor
| self.live_symbols
.contains(&ctor
)) {
482 // If it's a type whose items are live, then it's live, too.
483 // This is done to handle the case where, for example, the static
484 // method of a private type is used, but the type itself is never
486 let impl_items
= self.tcx
.impl_items
.borrow();
487 match self.tcx
.inherent_impls
.borrow().get(&local_def(id
)) {
490 for impl_did
in impl_list
.iter() {
491 for item_did
in impl_items
.get(impl_did
).unwrap().iter() {
492 if self.live_symbols
.contains(&item_did
.def_id()
503 fn warn_dead_code(&mut self,
508 let name
= name
.as_str();
509 if !name
.starts_with("_") {
512 .add_lint(lint
::builtin
::DEAD_CODE
,
515 format
!("{} is never used: `{}`", node_type
, name
));
520 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for DeadVisitor
<'a
, 'tcx
> {
521 fn visit_item(&mut self, item
: &ast
::Item
) {
522 if self.should_warn_about_item(item
) {
527 item
.node
.descriptive_variant()
531 ast
::ItemEnum(ref enum_def
, _
) => {
532 for variant
in &enum_def
.variants
{
533 if self.should_warn_about_variant(&variant
.node
) {
534 self.warn_dead_code(variant
.node
.id
, variant
.span
,
535 variant
.node
.name
.name
, "variant");
542 visit
::walk_item(self, item
);
545 fn visit_foreign_item(&mut self, fi
: &ast
::ForeignItem
) {
546 if !self.symbol_is_live(fi
.id
, None
) {
547 self.warn_dead_code(fi
.id
, fi
.span
, fi
.ident
.name
, fi
.node
.descriptive_variant());
549 visit
::walk_foreign_item(self, fi
);
552 fn visit_struct_field(&mut self, field
: &ast
::StructField
) {
553 if self.should_warn_about_field(&field
.node
) {
554 self.warn_dead_code(field
.node
.id
, field
.span
,
555 field
.node
.ident().unwrap().name
, "struct field");
558 visit
::walk_struct_field(self, field
);
561 fn visit_impl_item(&mut self, impl_item
: &ast
::ImplItem
) {
562 match impl_item
.node
{
563 ast
::ConstImplItem(_
, ref expr
) => {
564 if !self.symbol_is_live(impl_item
.id
, None
) {
565 self.warn_dead_code(impl_item
.id
, impl_item
.span
,
566 impl_item
.ident
.name
, "associated const");
568 visit
::walk_expr(self, expr
)
570 ast
::MethodImplItem(_
, ref body
) => {
571 if !self.symbol_is_live(impl_item
.id
, None
) {
572 self.warn_dead_code(impl_item
.id
, impl_item
.span
,
573 impl_item
.ident
.name
, "method");
575 visit
::walk_block(self, body
)
577 ast
::TypeImplItem(..) |
578 ast
::MacImplItem(..) => {}
582 // Overwrite so that we don't warn the trait item itself.
583 fn visit_trait_item(&mut self, trait_item
: &ast
::TraitItem
) {
584 match trait_item
.node
{
585 ast
::ConstTraitItem(_
, Some(ref expr
)) => {
586 visit
::walk_expr(self, expr
)
588 ast
::MethodTraitItem(_
, Some(ref body
)) => {
589 visit
::walk_block(self, body
)
591 ast
::ConstTraitItem(_
, None
) |
592 ast
::MethodTraitItem(_
, None
) |
593 ast
::TypeTraitItem(..) => {}
598 pub fn check_crate(tcx
: &ty
::ctxt
,
599 exported_items
: &privacy
::ExportedItems
,
600 reachable_symbols
: &NodeSet
) {
601 let krate
= tcx
.map
.krate();
602 let live_symbols
= find_live(tcx
, exported_items
,
603 reachable_symbols
, krate
);
604 let mut visitor
= DeadVisitor { tcx: tcx, live_symbols: live_symbols }
;
605 visit
::walk_crate(&mut visitor
, krate
);