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 middle
::{def, pat_util, privacy, ty}
;
17 use util
::nodemap
::NodeSet
;
19 use std
::collections
::HashSet
;
20 use syntax
::{ast, ast_map, codemap}
;
21 use syntax
::ast_util
::{local_def, is_local}
;
22 use syntax
::attr
::{self, AttrMetaMethods}
;
23 use syntax
::visit
::{self, Visitor}
;
25 // Any local node that may call something in its body block should be
26 // explored. For example, if it's a live NodeItem that is a
27 // function, then we should explore its block to check for codes that
28 // may need to be marked as live.
29 fn should_explore(tcx
: &ty
::ctxt
, def_id
: ast
::DefId
) -> bool
{
30 if !is_local(def_id
) {
34 match tcx
.map
.find(def_id
.node
) {
35 Some(ast_map
::NodeItem(..))
36 | Some(ast_map
::NodeImplItem(..))
37 | Some(ast_map
::NodeForeignItem(..))
38 | Some(ast_map
::NodeTraitItem(..)) => true,
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
,
52 impl<'a
, 'tcx
> MarkSymbolVisitor
<'a
, 'tcx
> {
53 fn new(tcx
: &'a ty
::ctxt
<'tcx
>,
54 worklist
: Vec
<ast
::NodeId
>) -> MarkSymbolVisitor
<'a
, 'tcx
> {
58 live_symbols
: box HashSet
::new(),
59 struct_has_extern_repr
: false,
60 ignore_non_const_paths
: false,
61 inherited_pub_visibility
: false,
65 fn check_def_id(&mut self, def_id
: ast
::DefId
) {
66 if should_explore(self.tcx
, def_id
) {
67 self.worklist
.push(def_id
.node
);
69 self.live_symbols
.insert(def_id
.node
);
72 fn lookup_and_handle_definition(&mut self, id
: &ast
::NodeId
) {
73 self.tcx
.def_map
.borrow().get(id
).map(|def
| {
74 match def
.full_def() {
76 self.check_def_id(def
.def_id())
78 _
if self.ignore_non_const_paths
=> (),
79 def
::DefPrimTy(_
) => (),
80 def
::DefVariant(enum_id
, variant_id
, _
) => {
81 self.check_def_id(enum_id
);
82 self.check_def_id(variant_id
);
85 self.check_def_id(def
.def_id());
91 fn lookup_and_handle_method(&mut self, id
: ast
::NodeId
,
92 span
: codemap
::Span
) {
93 let method_call
= ty
::MethodCall
::expr(id
);
94 match self.tcx
.method_map
.borrow().get(&method_call
) {
97 ty
::MethodStatic(def_id
) => {
98 match ty
::provided_source(self.tcx
, def_id
) {
99 Some(p_did
) => self.check_def_id(p_did
),
100 None
=> self.check_def_id(def_id
)
103 ty
::MethodStaticClosure(_
) => {}
104 ty
::MethodTypeParam(ty
::MethodParam
{
109 ty
::MethodTraitObject(ty
::MethodObject
{
114 let trait_item
= ty
::trait_item(self.tcx
,
118 ty
::MethodTraitItem(method
) => {
119 self.check_def_id(method
.def_id
);
121 ty
::TypeTraitItem(typedef
) => {
122 self.check_def_id(typedef
.def_id
);
129 self.tcx
.sess
.span_bug(span
,
130 "method call expression not \
136 fn handle_field_access(&mut self, lhs
: &ast
::Expr
, name
: &ast
::Ident
) {
137 match ty
::expr_ty_adjusted(self.tcx
, lhs
).sty
{
138 ty
::ty_struct(id
, _
) => {
139 let fields
= ty
::lookup_struct_fields(self.tcx
, id
);
140 let field_id
= fields
.iter()
141 .find(|field
| field
.name
== name
.name
).unwrap().id
;
142 self.live_symbols
.insert(field_id
.node
);
148 fn handle_tup_field_access(&mut self, lhs
: &ast
::Expr
, idx
: usize) {
149 match ty
::expr_ty_adjusted(self.tcx
, lhs
).sty
{
150 ty
::ty_struct(id
, _
) => {
151 let fields
= ty
::lookup_struct_fields(self.tcx
, id
);
152 let field_id
= fields
[idx
].id
;
153 self.live_symbols
.insert(field_id
.node
);
159 fn handle_field_pattern_match(&mut self, lhs
: &ast
::Pat
,
160 pats
: &[codemap
::Spanned
<ast
::FieldPat
>]) {
161 let id
= match self.tcx
.def_map
.borrow().get(&lhs
.id
).unwrap().full_def() {
162 def
::DefVariant(_
, id
, _
) => id
,
164 match ty
::ty_to_def_id(ty
::node_id_to_type(self.tcx
,
167 self.tcx
.sess
.span_bug(lhs
.span
,
168 "struct pattern wasn't of a \
169 type with a def ID?!")
171 Some(def_id
) => def_id
,
175 let fields
= ty
::lookup_struct_fields(self.tcx
, id
);
177 let field_id
= fields
.iter()
178 .find(|field
| field
.name
== pat
.node
.ident
.name
).unwrap().id
;
179 self.live_symbols
.insert(field_id
.node
);
183 fn mark_live_symbols(&mut self) {
184 let mut scanned
= HashSet
::new();
185 while self.worklist
.len() > 0 {
186 let id
= self.worklist
.pop().unwrap();
187 if scanned
.contains(&id
) {
192 match self.tcx
.map
.find(id
) {
194 self.live_symbols
.insert(id
);
195 self.visit_node(node
);
202 fn visit_node(&mut self, node
: &ast_map
::Node
) {
203 let had_extern_repr
= self.struct_has_extern_repr
;
204 self.struct_has_extern_repr
= false;
205 let had_inherited_pub_visibility
= self.inherited_pub_visibility
;
206 self.inherited_pub_visibility
= false;
208 ast_map
::NodeItem(item
) => {
210 ast
::ItemStruct(..) => {
211 self.struct_has_extern_repr
= item
.attrs
.iter().any(|attr
| {
212 attr
::find_repr_attrs(self.tcx
.sess
.diagnostic(), attr
)
213 .contains(&attr
::ReprExtern
)
216 visit
::walk_item(self, &*item
);
218 ast
::ItemEnum(..) => {
219 self.inherited_pub_visibility
= item
.vis
== ast
::Public
;
220 visit
::walk_item(self, &*item
);
224 | ast
::ItemStatic(..)
225 | ast
::ItemConst(..) => {
226 visit
::walk_item(self, &*item
);
231 ast_map
::NodeTraitItem(trait_item
) => {
232 visit
::walk_trait_item(self, trait_item
);
234 ast_map
::NodeImplItem(impl_item
) => {
235 visit
::walk_impl_item(self, impl_item
);
237 ast_map
::NodeForeignItem(foreign_item
) => {
238 visit
::walk_foreign_item(self, &*foreign_item
);
242 self.struct_has_extern_repr
= had_extern_repr
;
243 self.inherited_pub_visibility
= had_inherited_pub_visibility
;
247 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for MarkSymbolVisitor
<'a
, 'tcx
> {
249 fn visit_struct_def(&mut self, def
: &ast
::StructDef
, _
: ast
::Ident
,
250 _
: &ast
::Generics
, _
: ast
::NodeId
) {
251 let has_extern_repr
= self.struct_has_extern_repr
;
252 let inherited_pub_visibility
= self.inherited_pub_visibility
;
253 let live_fields
= def
.fields
.iter().filter(|f
| {
254 has_extern_repr
|| inherited_pub_visibility
|| match f
.node
.kind
{
255 ast
::NamedField(_
, ast
::Public
) => true,
259 self.live_symbols
.extend(live_fields
.map(|f
| f
.node
.id
));
261 visit
::walk_struct_def(self, def
);
264 fn visit_expr(&mut self, expr
: &ast
::Expr
) {
266 ast
::ExprMethodCall(..) => {
267 self.lookup_and_handle_method(expr
.id
, expr
.span
);
269 ast
::ExprField(ref lhs
, ref ident
) => {
270 self.handle_field_access(&**lhs
, &ident
.node
);
272 ast
::ExprTupField(ref lhs
, idx
) => {
273 self.handle_tup_field_access(&**lhs
, idx
.node
);
278 visit
::walk_expr(self, expr
);
281 fn visit_pat(&mut self, pat
: &ast
::Pat
) {
282 let def_map
= &self.tcx
.def_map
;
284 ast
::PatStruct(_
, ref fields
, _
) => {
285 self.handle_field_pattern_match(pat
, fields
);
287 _
if pat_util
::pat_is_const(def_map
, pat
) => {
288 // it might be the only use of a const
289 self.lookup_and_handle_definition(&pat
.id
)
294 self.ignore_non_const_paths
= true;
295 visit
::walk_pat(self, pat
);
296 self.ignore_non_const_paths
= false;
299 fn visit_path(&mut self, path
: &ast
::Path
, id
: ast
::NodeId
) {
300 self.lookup_and_handle_definition(&id
);
301 visit
::walk_path(self, path
);
304 fn visit_item(&mut self, _
: &ast
::Item
) {
305 // Do not recurse into items. These items will be added to the
306 // worklist and recursed into manually if necessary.
310 fn has_allow_dead_code_or_lang_attr(attrs
: &[ast
::Attribute
]) -> bool
{
311 if attr
::contains_name(attrs
, "lang") {
315 let dead_code
= lint
::builtin
::DEAD_CODE
.name_lower();
316 for attr
in lint
::gather_attrs(attrs
) {
318 Ok((ref name
, lint
::Allow
, _
))
319 if &name
[..] == dead_code
=> return true,
326 // This visitor seeds items that
327 // 1) We want to explicitly consider as live:
328 // * Item annotated with #[allow(dead_code)]
329 // - This is done so that if we want to suppress warnings for a
330 // group of dead functions, we only have to annotate the "root".
331 // For example, if both `f` and `g` are dead and `f` calls `g`,
332 // then annotating `f` with `#[allow(dead_code)]` will suppress
333 // warning for both `f` and `g`.
334 // * Item annotated with #[lang=".."]
335 // - This is because lang items are always callable from elsewhere.
337 // 2) We are not sure to be live or not
338 // * Implementation of a trait method
340 worklist
: Vec
<ast
::NodeId
>
343 impl<'v
> Visitor
<'v
> for LifeSeeder
{
344 fn visit_item(&mut self, item
: &ast
::Item
) {
345 let allow_dead_code
= has_allow_dead_code_or_lang_attr(&item
.attrs
);
347 self.worklist
.push(item
.id
);
350 ast
::ItemEnum(ref enum_def
, _
) if allow_dead_code
=> {
351 self.worklist
.extend(enum_def
.variants
.iter().map(|variant
| variant
.node
.id
));
353 ast
::ItemTrait(_
, _
, _
, ref trait_items
) => {
354 for trait_item
in trait_items
{
355 match trait_item
.node
{
356 ast
::MethodTraitItem(_
, Some(_
)) => {
357 if has_allow_dead_code_or_lang_attr(&trait_item
.attrs
) {
358 self.worklist
.push(trait_item
.id
);
365 ast
::ItemImpl(_
, _
, _
, ref opt_trait
, _
, ref impl_items
) => {
366 for impl_item
in impl_items
{
367 match impl_item
.node
{
368 ast
::MethodImplItem(..) => {
369 if opt_trait
.is_some() ||
370 has_allow_dead_code_or_lang_attr(&impl_item
.attrs
) {
371 self.worklist
.push(impl_item
.id
);
374 ast
::TypeImplItem(_
) => {}
375 ast
::MacImplItem(_
) => panic
!("unexpanded macro")
381 visit
::walk_item(self, item
);
385 fn create_and_seed_worklist(tcx
: &ty
::ctxt
,
386 exported_items
: &privacy
::ExportedItems
,
387 reachable_symbols
: &NodeSet
,
388 krate
: &ast
::Crate
) -> Vec
<ast
::NodeId
> {
389 let mut worklist
= Vec
::new();
391 // Preferably, we would only need to seed the worklist with reachable
392 // symbols. However, since the set of reachable symbols differs
393 // depending on whether a crate is built as bin or lib, and we want
394 // the warning to be consistent, we also seed the worklist with
396 for id
in exported_items
{
399 for id
in reachable_symbols
{
404 match *tcx
.sess
.entry_fn
.borrow() {
405 Some((id
, _
)) => worklist
.push(id
),
409 // Seed implemented trait methods
410 let mut life_seeder
= LifeSeeder
{
413 visit
::walk_crate(&mut life_seeder
, krate
);
415 return life_seeder
.worklist
;
418 fn find_live(tcx
: &ty
::ctxt
,
419 exported_items
: &privacy
::ExportedItems
,
420 reachable_symbols
: &NodeSet
,
422 -> Box
<HashSet
<ast
::NodeId
>> {
423 let worklist
= create_and_seed_worklist(tcx
, exported_items
,
424 reachable_symbols
, krate
);
425 let mut symbol_visitor
= MarkSymbolVisitor
::new(tcx
, worklist
);
426 symbol_visitor
.mark_live_symbols();
427 symbol_visitor
.live_symbols
430 fn get_struct_ctor_id(item
: &ast
::Item
) -> Option
<ast
::NodeId
> {
432 ast
::ItemStruct(ref struct_def
, _
) => struct_def
.ctor_id
,
437 struct DeadVisitor
<'a
, 'tcx
: 'a
> {
438 tcx
: &'a ty
::ctxt
<'tcx
>,
439 live_symbols
: Box
<HashSet
<ast
::NodeId
>>,
442 impl<'a
, 'tcx
> DeadVisitor
<'a
, 'tcx
> {
443 fn should_warn_about_item(&mut self, item
: &ast
::Item
) -> bool
{
444 let should_warn
= match item
.node
{
449 | ast
::ItemStruct(..) => true,
452 let ctor_id
= get_struct_ctor_id(item
);
453 should_warn
&& !self.symbol_is_live(item
.id
, ctor_id
)
456 fn should_warn_about_field(&mut self, node
: &ast
::StructField_
) -> bool
{
457 let is_named
= node
.ident().is_some();
458 let field_type
= ty
::node_id_to_type(self.tcx
, node
.id
);
459 let is_marker_field
= match ty
::ty_to_def_id(field_type
) {
460 Some(def_id
) => self.tcx
.lang_items
.items().any(|(_
, item
)| *item
== Some(def_id
)),
464 && !self.symbol_is_live(node
.id
, None
)
466 && !has_allow_dead_code_or_lang_attr(&node
.attrs
)
469 fn should_warn_about_variant(&mut self, variant
: &ast
::Variant_
) -> bool
{
470 !self.symbol_is_live(variant
.id
, None
)
471 && !has_allow_dead_code_or_lang_attr(&variant
.attrs
)
474 // id := node id of an item's definition.
475 // ctor_id := `Some` if the item is a struct_ctor (tuple struct),
477 // If the item is a struct_ctor, then either its `id` or
478 // `ctor_id` (unwrapped) is in the live_symbols set. More specifically,
479 // DefMap maps the ExprPath of a struct_ctor to the node referred by
480 // `ctor_id`. On the other hand, in a statement like
481 // `type <ident> <generics> = <ty>;` where <ty> refers to a struct_ctor,
482 // DefMap maps <ty> to `id` instead.
483 fn symbol_is_live(&mut self, id
: ast
::NodeId
,
484 ctor_id
: Option
<ast
::NodeId
>) -> bool
{
485 if self.live_symbols
.contains(&id
)
486 || ctor_id
.map_or(false,
487 |ctor
| self.live_symbols
.contains(&ctor
)) {
490 // If it's a type whose methods are live, then it's live, too.
491 // This is done to handle the case where, for example, the static
492 // method of a private type is used, but the type itself is never
494 let impl_items
= self.tcx
.impl_items
.borrow();
495 match self.tcx
.inherent_impls
.borrow().get(&local_def(id
)) {
498 for impl_did
in &**impl_list
{
499 for item_did
in &*impl_items
.get(impl_did
).unwrap() {
500 if self.live_symbols
.contains(&item_did
.def_id()
511 fn warn_dead_code(&mut self,
516 let name
= ident
.as_str();
517 if !name
.starts_with("_") {
520 .add_lint(lint
::builtin
::DEAD_CODE
,
523 format
!("{} is never used: `{}`", node_type
, name
));
528 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for DeadVisitor
<'a
, 'tcx
> {
529 fn visit_item(&mut self, item
: &ast
::Item
) {
530 if self.should_warn_about_item(item
) {
531 self.warn_dead_code(item
.id
, item
.span
, item
.ident
, item
.node
.descriptive_variant());
534 ast
::ItemEnum(ref enum_def
, _
) => {
535 for variant
in &enum_def
.variants
{
536 if self.should_warn_about_variant(&variant
.node
) {
537 self.warn_dead_code(variant
.node
.id
, variant
.span
,
538 variant
.node
.name
, "variant");
545 visit
::walk_item(self, item
);
548 fn visit_foreign_item(&mut self, fi
: &ast
::ForeignItem
) {
549 if !self.symbol_is_live(fi
.id
, None
) {
550 self.warn_dead_code(fi
.id
, fi
.span
, fi
.ident
, fi
.node
.descriptive_variant());
552 visit
::walk_foreign_item(self, fi
);
555 fn visit_fn(&mut self, fk
: visit
::FnKind
<'v
>,
556 _
: &'v ast
::FnDecl
, block
: &'v ast
::Block
,
557 span
: codemap
::Span
, id
: ast
::NodeId
) {
558 // Have to warn method here because methods are not ast::Item
560 visit
::FkMethod(name
, _
) => {
561 if !self.symbol_is_live(id
, None
) {
562 self.warn_dead_code(id
, span
, name
, "method");
567 visit
::walk_block(self, block
);
570 fn visit_struct_field(&mut self, field
: &ast
::StructField
) {
571 if self.should_warn_about_field(&field
.node
) {
572 self.warn_dead_code(field
.node
.id
, field
.span
,
573 field
.node
.ident().unwrap(), "struct field");
576 visit
::walk_struct_field(self, field
);
579 // Overwrite so that we don't warn the trait method itself.
580 fn visit_trait_item(&mut self, trait_method
: &ast
::TraitItem
) {
581 match trait_method
.node
{
582 ast
::MethodTraitItem(_
, Some(ref body
)) => {
583 visit
::walk_block(self, body
)
585 ast
::MethodTraitItem(_
, None
) |
586 ast
::TypeTraitItem(..) => {}
591 pub fn check_crate(tcx
: &ty
::ctxt
,
592 exported_items
: &privacy
::ExportedItems
,
593 reachable_symbols
: &NodeSet
) {
594 let krate
= tcx
.map
.krate();
595 let live_symbols
= find_live(tcx
, exported_items
,
596 reachable_symbols
, krate
);
597 let mut visitor
= DeadVisitor { tcx: tcx, live_symbols: live_symbols }
;
598 visit
::walk_crate(&mut visitor
, krate
);