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 span
: codemap
::Span
) {
98 let method_call
= ty
::MethodCall
::expr(id
);
99 match self.tcx
.method_map
.borrow().get(&method_call
) {
101 match method
.origin
{
102 ty
::MethodStatic(def_id
) => {
103 match ty
::provided_source(self.tcx
, def_id
) {
104 Some(p_did
) => self.check_def_id(p_did
),
105 None
=> self.check_def_id(def_id
)
108 ty
::MethodStaticClosure(_
) => {}
109 ty
::MethodTypeParam(ty
::MethodParam
{
114 ty
::MethodTraitObject(ty
::MethodObject
{
119 let trait_item
= ty
::trait_item(self.tcx
,
122 self.check_def_id(trait_item
.def_id());
127 self.tcx
.sess
.span_bug(span
,
128 "method call expression not \
134 fn handle_field_access(&mut self, lhs
: &ast
::Expr
, name
: ast
::Name
) {
135 match ty
::expr_ty_adjusted(self.tcx
, lhs
).sty
{
136 ty
::TyStruct(id
, _
) => {
137 let fields
= ty
::lookup_struct_fields(self.tcx
, id
);
138 let field_id
= fields
.iter()
139 .find(|field
| field
.name
== name
).unwrap().id
;
140 self.live_symbols
.insert(field_id
.node
);
146 fn handle_tup_field_access(&mut self, lhs
: &ast
::Expr
, idx
: usize) {
147 match ty
::expr_ty_adjusted(self.tcx
, lhs
).sty
{
148 ty
::TyStruct(id
, _
) => {
149 let fields
= ty
::lookup_struct_fields(self.tcx
, id
);
150 let field_id
= fields
[idx
].id
;
151 self.live_symbols
.insert(field_id
.node
);
157 fn handle_field_pattern_match(&mut self, lhs
: &ast
::Pat
,
158 pats
: &[codemap
::Spanned
<ast
::FieldPat
>]) {
159 let id
= match self.tcx
.def_map
.borrow().get(&lhs
.id
).unwrap().full_def() {
160 def
::DefVariant(_
, id
, _
) => id
,
162 match ty
::ty_to_def_id(ty
::node_id_to_type(self.tcx
,
165 self.tcx
.sess
.span_bug(lhs
.span
,
166 "struct pattern wasn't of a \
167 type with a def ID?!")
169 Some(def_id
) => def_id
,
173 let fields
= ty
::lookup_struct_fields(self.tcx
, id
);
175 if let ast
::PatWild(ast
::PatWildSingle
) = pat
.node
.pat
.node
{
178 let field_id
= fields
.iter()
179 .find(|field
| field
.name
== pat
.node
.ident
.name
).unwrap().id
;
180 self.live_symbols
.insert(field_id
.node
);
184 fn mark_live_symbols(&mut self) {
185 let mut scanned
= HashSet
::new();
186 while !self.worklist
.is_empty() {
187 let id
= self.worklist
.pop().unwrap();
188 if scanned
.contains(&id
) {
193 match self.tcx
.map
.find(id
) {
195 self.live_symbols
.insert(id
);
196 self.visit_node(node
);
203 fn visit_node(&mut self, node
: &ast_map
::Node
) {
204 let had_extern_repr
= self.struct_has_extern_repr
;
205 self.struct_has_extern_repr
= false;
206 let had_inherited_pub_visibility
= self.inherited_pub_visibility
;
207 self.inherited_pub_visibility
= false;
209 ast_map
::NodeItem(item
) => {
211 ast
::ItemStruct(..) => {
212 self.struct_has_extern_repr
= item
.attrs
.iter().any(|attr
| {
213 attr
::find_repr_attrs(self.tcx
.sess
.diagnostic(), attr
)
214 .contains(&attr
::ReprExtern
)
217 visit
::walk_item(self, &*item
);
219 ast
::ItemEnum(..) => {
220 self.inherited_pub_visibility
= item
.vis
== ast
::Public
;
221 visit
::walk_item(self, &*item
);
225 | ast
::ItemStatic(..)
226 | ast
::ItemConst(..) => {
227 visit
::walk_item(self, &*item
);
232 ast_map
::NodeTraitItem(trait_item
) => {
233 visit
::walk_trait_item(self, trait_item
);
235 ast_map
::NodeImplItem(impl_item
) => {
236 visit
::walk_impl_item(self, impl_item
);
238 ast_map
::NodeForeignItem(foreign_item
) => {
239 visit
::walk_foreign_item(self, &*foreign_item
);
243 self.struct_has_extern_repr
= had_extern_repr
;
244 self.inherited_pub_visibility
= had_inherited_pub_visibility
;
248 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for MarkSymbolVisitor
<'a
, 'tcx
> {
250 fn visit_struct_def(&mut self, def
: &ast
::StructDef
, _
: ast
::Ident
,
251 _
: &ast
::Generics
, _
: ast
::NodeId
) {
252 let has_extern_repr
= self.struct_has_extern_repr
;
253 let inherited_pub_visibility
= self.inherited_pub_visibility
;
254 let live_fields
= def
.fields
.iter().filter(|f
| {
255 has_extern_repr
|| inherited_pub_visibility
|| match f
.node
.kind
{
256 ast
::NamedField(_
, ast
::Public
) => true,
260 self.live_symbols
.extend(live_fields
.map(|f
| f
.node
.id
));
262 visit
::walk_struct_def(self, def
);
265 fn visit_expr(&mut self, expr
: &ast
::Expr
) {
267 ast
::ExprMethodCall(..) => {
268 self.lookup_and_handle_method(expr
.id
, expr
.span
);
270 ast
::ExprField(ref lhs
, ref ident
) => {
271 self.handle_field_access(&**lhs
, ident
.node
.name
);
273 ast
::ExprTupField(ref lhs
, idx
) => {
274 self.handle_tup_field_access(&**lhs
, idx
.node
);
279 visit
::walk_expr(self, expr
);
282 fn visit_arm(&mut self, arm
: &ast
::Arm
) {
283 if arm
.pats
.len() == 1 {
284 let pat
= &*arm
.pats
[0];
285 let variants
= pat_util
::necessary_variants(&self.tcx
.def_map
, pat
);
287 // Inside the body, ignore constructions of variants
288 // necessary for the pattern to match. Those construction sites
289 // can't be reached unless the variant is constructed elsewhere.
290 let len
= self.ignore_variant_stack
.len();
291 self.ignore_variant_stack
.push_all(&*variants
);
292 visit
::walk_arm(self, arm
);
293 self.ignore_variant_stack
.truncate(len
);
295 visit
::walk_arm(self, arm
);
299 fn visit_pat(&mut self, pat
: &ast
::Pat
) {
300 let def_map
= &self.tcx
.def_map
;
302 ast
::PatStruct(_
, ref fields
, _
) => {
303 self.handle_field_pattern_match(pat
, fields
);
305 _
if pat_util
::pat_is_const(def_map
, pat
) => {
306 // it might be the only use of a const
307 self.lookup_and_handle_definition(&pat
.id
)
312 self.ignore_non_const_paths
= true;
313 visit
::walk_pat(self, pat
);
314 self.ignore_non_const_paths
= false;
317 fn visit_path(&mut self, path
: &ast
::Path
, id
: ast
::NodeId
) {
318 self.lookup_and_handle_definition(&id
);
319 visit
::walk_path(self, path
);
322 fn visit_item(&mut self, _
: &ast
::Item
) {
323 // Do not recurse into items. These items will be added to the
324 // worklist and recursed into manually if necessary.
328 fn has_allow_dead_code_or_lang_attr(attrs
: &[ast
::Attribute
]) -> bool
{
329 if attr
::contains_name(attrs
, "lang") {
333 let dead_code
= lint
::builtin
::DEAD_CODE
.name_lower();
334 for attr
in lint
::gather_attrs(attrs
) {
336 Ok((ref name
, lint
::Allow
, _
))
337 if &name
[..] == dead_code
=> return true,
344 // This visitor seeds items that
345 // 1) We want to explicitly consider as live:
346 // * Item annotated with #[allow(dead_code)]
347 // - This is done so that if we want to suppress warnings for a
348 // group of dead functions, we only have to annotate the "root".
349 // For example, if both `f` and `g` are dead and `f` calls `g`,
350 // then annotating `f` with `#[allow(dead_code)]` will suppress
351 // warning for both `f` and `g`.
352 // * Item annotated with #[lang=".."]
353 // - This is because lang items are always callable from elsewhere.
355 // 2) We are not sure to be live or not
356 // * Implementation of a trait method
358 worklist
: Vec
<ast
::NodeId
>
361 impl<'v
> Visitor
<'v
> for LifeSeeder
{
362 fn visit_item(&mut self, item
: &ast
::Item
) {
363 let allow_dead_code
= has_allow_dead_code_or_lang_attr(&item
.attrs
);
365 self.worklist
.push(item
.id
);
368 ast
::ItemEnum(ref enum_def
, _
) if allow_dead_code
=> {
369 self.worklist
.extend(enum_def
.variants
.iter().map(|variant
| variant
.node
.id
));
371 ast
::ItemTrait(_
, _
, _
, ref trait_items
) => {
372 for trait_item
in trait_items
{
373 match trait_item
.node
{
374 ast
::ConstTraitItem(_
, Some(_
)) |
375 ast
::MethodTraitItem(_
, Some(_
)) => {
376 if has_allow_dead_code_or_lang_attr(&trait_item
.attrs
) {
377 self.worklist
.push(trait_item
.id
);
384 ast
::ItemImpl(_
, _
, _
, ref opt_trait
, _
, ref impl_items
) => {
385 for impl_item
in impl_items
{
386 match impl_item
.node
{
387 ast
::ConstImplItem(..) |
388 ast
::MethodImplItem(..) => {
389 if opt_trait
.is_some() ||
390 has_allow_dead_code_or_lang_attr(&impl_item
.attrs
) {
391 self.worklist
.push(impl_item
.id
);
394 ast
::TypeImplItem(_
) => {}
395 ast
::MacImplItem(_
) => panic
!("unexpanded macro")
401 visit
::walk_item(self, item
);
405 fn create_and_seed_worklist(tcx
: &ty
::ctxt
,
406 exported_items
: &privacy
::ExportedItems
,
407 reachable_symbols
: &NodeSet
,
408 krate
: &ast
::Crate
) -> Vec
<ast
::NodeId
> {
409 let mut worklist
= Vec
::new();
411 // Preferably, we would only need to seed the worklist with reachable
412 // symbols. However, since the set of reachable symbols differs
413 // depending on whether a crate is built as bin or lib, and we want
414 // the warning to be consistent, we also seed the worklist with
416 for id
in exported_items
{
419 for id
in reachable_symbols
{
420 // Reachable variants can be dead, because we warn about
421 // variants never constructed, not variants never used.
422 if let Some(ast_map
::NodeVariant(..)) = tcx
.map
.find(*id
) {
429 match *tcx
.sess
.entry_fn
.borrow() {
430 Some((id
, _
)) => worklist
.push(id
),
434 // Seed implemented trait items
435 let mut life_seeder
= LifeSeeder
{
438 visit
::walk_crate(&mut life_seeder
, krate
);
440 return life_seeder
.worklist
;
443 fn find_live(tcx
: &ty
::ctxt
,
444 exported_items
: &privacy
::ExportedItems
,
445 reachable_symbols
: &NodeSet
,
447 -> Box
<HashSet
<ast
::NodeId
>> {
448 let worklist
= create_and_seed_worklist(tcx
, exported_items
,
449 reachable_symbols
, krate
);
450 let mut symbol_visitor
= MarkSymbolVisitor
::new(tcx
, worklist
);
451 symbol_visitor
.mark_live_symbols();
452 symbol_visitor
.live_symbols
455 fn get_struct_ctor_id(item
: &ast
::Item
) -> Option
<ast
::NodeId
> {
457 ast
::ItemStruct(ref struct_def
, _
) => struct_def
.ctor_id
,
462 struct DeadVisitor
<'a
, 'tcx
: 'a
> {
463 tcx
: &'a ty
::ctxt
<'tcx
>,
464 live_symbols
: Box
<HashSet
<ast
::NodeId
>>,
467 impl<'a
, 'tcx
> DeadVisitor
<'a
, 'tcx
> {
468 fn should_warn_about_item(&mut self, item
: &ast
::Item
) -> bool
{
469 let should_warn
= match item
.node
{
474 | ast
::ItemStruct(..) => true,
477 let ctor_id
= get_struct_ctor_id(item
);
478 should_warn
&& !self.symbol_is_live(item
.id
, ctor_id
)
481 fn should_warn_about_field(&mut self, node
: &ast
::StructField_
) -> bool
{
482 let is_named
= node
.ident().is_some();
483 let field_type
= ty
::node_id_to_type(self.tcx
, node
.id
);
484 let is_marker_field
= match ty
::ty_to_def_id(field_type
) {
485 Some(def_id
) => self.tcx
.lang_items
.items().any(|(_
, item
)| *item
== Some(def_id
)),
489 && !self.symbol_is_live(node
.id
, None
)
491 && !has_allow_dead_code_or_lang_attr(&node
.attrs
)
494 fn should_warn_about_variant(&mut self, variant
: &ast
::Variant_
) -> bool
{
495 !self.symbol_is_live(variant
.id
, None
)
496 && !has_allow_dead_code_or_lang_attr(&variant
.attrs
)
499 // id := node id of an item's definition.
500 // ctor_id := `Some` if the item is a struct_ctor (tuple struct),
502 // If the item is a struct_ctor, then either its `id` or
503 // `ctor_id` (unwrapped) is in the live_symbols set. More specifically,
504 // DefMap maps the ExprPath of a struct_ctor to the node referred by
505 // `ctor_id`. On the other hand, in a statement like
506 // `type <ident> <generics> = <ty>;` where <ty> refers to a struct_ctor,
507 // DefMap maps <ty> to `id` instead.
508 fn symbol_is_live(&mut self, id
: ast
::NodeId
,
509 ctor_id
: Option
<ast
::NodeId
>) -> bool
{
510 if self.live_symbols
.contains(&id
)
511 || ctor_id
.map_or(false,
512 |ctor
| self.live_symbols
.contains(&ctor
)) {
515 // If it's a type whose items are live, then it's live, too.
516 // This is done to handle the case where, for example, the static
517 // method of a private type is used, but the type itself is never
519 let impl_items
= self.tcx
.impl_items
.borrow();
520 match self.tcx
.inherent_impls
.borrow().get(&local_def(id
)) {
523 for impl_did
in impl_list
.iter() {
524 for item_did
in impl_items
.get(impl_did
).unwrap().iter() {
525 if self.live_symbols
.contains(&item_did
.def_id()
536 fn warn_dead_code(&mut self,
541 let name
= name
.as_str();
542 if !name
.starts_with("_") {
545 .add_lint(lint
::builtin
::DEAD_CODE
,
548 format
!("{} is never used: `{}`", node_type
, name
));
553 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for DeadVisitor
<'a
, 'tcx
> {
554 fn visit_item(&mut self, item
: &ast
::Item
) {
555 if self.should_warn_about_item(item
) {
560 item
.node
.descriptive_variant()
564 ast
::ItemEnum(ref enum_def
, _
) => {
565 for variant
in &enum_def
.variants
{
566 if self.should_warn_about_variant(&variant
.node
) {
567 self.warn_dead_code(variant
.node
.id
, variant
.span
,
568 variant
.node
.name
.name
, "variant");
575 visit
::walk_item(self, item
);
578 fn visit_foreign_item(&mut self, fi
: &ast
::ForeignItem
) {
579 if !self.symbol_is_live(fi
.id
, None
) {
580 self.warn_dead_code(fi
.id
, fi
.span
, fi
.ident
.name
, fi
.node
.descriptive_variant());
582 visit
::walk_foreign_item(self, fi
);
585 fn visit_struct_field(&mut self, field
: &ast
::StructField
) {
586 if self.should_warn_about_field(&field
.node
) {
587 self.warn_dead_code(field
.node
.id
, field
.span
,
588 field
.node
.ident().unwrap().name
, "struct field");
591 visit
::walk_struct_field(self, field
);
594 fn visit_impl_item(&mut self, impl_item
: &ast
::ImplItem
) {
595 match impl_item
.node
{
596 ast
::ConstImplItem(_
, ref expr
) => {
597 if !self.symbol_is_live(impl_item
.id
, None
) {
598 self.warn_dead_code(impl_item
.id
, impl_item
.span
,
599 impl_item
.ident
.name
, "associated const");
601 visit
::walk_expr(self, expr
)
603 ast
::MethodImplItem(_
, ref body
) => {
604 if !self.symbol_is_live(impl_item
.id
, None
) {
605 self.warn_dead_code(impl_item
.id
, impl_item
.span
,
606 impl_item
.ident
.name
, "method");
608 visit
::walk_block(self, body
)
610 ast
::TypeImplItem(..) |
611 ast
::MacImplItem(..) => {}
615 // Overwrite so that we don't warn the trait item itself.
616 fn visit_trait_item(&mut self, trait_item
: &ast
::TraitItem
) {
617 match trait_item
.node
{
618 ast
::ConstTraitItem(_
, Some(ref expr
)) => {
619 visit
::walk_expr(self, expr
)
621 ast
::MethodTraitItem(_
, Some(ref body
)) => {
622 visit
::walk_block(self, body
)
624 ast
::ConstTraitItem(_
, None
) |
625 ast
::MethodTraitItem(_
, None
) |
626 ast
::TypeTraitItem(..) => {}
631 pub fn check_crate(tcx
: &ty
::ctxt
,
632 exported_items
: &privacy
::ExportedItems
,
633 reachable_symbols
: &NodeSet
) {
634 let krate
= tcx
.map
.krate();
635 let live_symbols
= find_live(tcx
, exported_items
,
636 reachable_symbols
, krate
);
637 let mut visitor
= DeadVisitor { tcx: tcx, live_symbols: live_symbols }
;
638 visit
::walk_crate(&mut visitor
, krate
);