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::lint::{allow, contains_lint, DeadCode};
20 use collections::HashSet;
23 use syntax::ast_util::{local_def, def_id_of_def, is_local};
26 use syntax::parse::token;
27 use syntax::visit::Visitor;
30 pub static DEAD_CODE_LINT_STR: &'static str = "dead_code";
32 // Any local node that may call something in its body block should be
33 // explored. For example, if it's a live NodeItem that is a
34 // function, then we should explore its block to check for codes that
35 // may need to be marked as live.
36 fn should_explore(tcx: ty::ctxt, def_id: ast::DefId) -> bool {
37 if !is_local(def_id) {
41 match tcx.map.find(def_id.node) {
42 Some(ast_map::NodeItem(..))
43 | Some(ast_map::NodeMethod(..))
44 | Some(ast_map::NodeForeignItem(..))
45 | Some(ast_map::NodeTraitMethod(..)) => true,
50 struct MarkSymbolVisitor {
51 worklist: ~[ast::NodeId],
52 method_map: typeck::MethodMap,
54 live_symbols: ~HashSet<ast::NodeId>,
57 impl MarkSymbolVisitor {
59 method_map: typeck::MethodMap,
60 worklist: ~[ast::NodeId]) -> MarkSymbolVisitor {
63 method_map: method_map,
65 live_symbols: ~HashSet::new(),
69 fn check_def_id(&mut self, def_id: ast::DefId) {
70 if should_explore(self.tcx, def_id) {
71 self.worklist.push(def_id.node);
73 self.live_symbols.insert(def_id.node);
76 fn lookup_and_handle_definition(&mut self, id: &ast::NodeId) {
77 let def_map = self.tcx.def_map.borrow();
78 let def = match def_map.get().find(id) {
82 let def_id = match def {
83 ast::DefVariant(enum_id, _, _) => Some(enum_id),
84 ast::DefPrimTy(_) => None,
85 _ => Some(def_id_of_def(def)),
88 Some(def_id) => self.check_def_id(def_id),
93 fn lookup_and_handle_method(&mut self, id: &ast::NodeId,
94 span: codemap::Span) {
95 match self.method_map.borrow().get().find(id) {
98 typeck::MethodStatic(def_id) => {
99 match ty::provided_source(self.tcx, def_id) {
100 Some(p_did) => self.check_def_id(p_did),
101 None => self.check_def_id(def_id)
104 typeck::MethodParam(typeck::MethodParam {
109 | typeck::MethodObject(typeck::MethodObject {
114 let def_id = ty::trait_method(self.tcx,
115 trait_id, index).def_id;
116 self.check_def_id(def_id);
121 self.tcx.sess.span_bug(span,
122 "method call expression not \
128 fn mark_live_symbols(&mut self) {
129 let mut scanned = HashSet::new();
130 while self.worklist.len() > 0 {
131 let id = self.worklist.pop().unwrap();
132 if scanned.contains(&id) {
137 match self.tcx.map.find(id) {
139 self.live_symbols.insert(id);
140 self.visit_node(node);
147 fn visit_node(&mut self, node: &ast_map::Node) {
149 ast_map::NodeItem(item) => {
154 | ast::ItemStruct(..)
155 | ast::ItemStatic(..) => {
156 visit::walk_item(self, item, ());
161 ast_map::NodeTraitMethod(trait_method) => {
162 visit::walk_trait_method(self, trait_method, ());
164 ast_map::NodeMethod(method) => {
165 visit::walk_block(self, method.body, ());
167 ast_map::NodeForeignItem(foreign_item) => {
168 visit::walk_foreign_item(self, foreign_item, ());
175 impl Visitor<()> for MarkSymbolVisitor {
177 fn visit_expr(&mut self, expr: &ast::Expr, _: ()) {
179 ast::ExprMethodCall(..) => {
180 self.lookup_and_handle_method(&expr.id, expr.span);
185 visit::walk_expr(self, expr, ())
188 fn visit_path(&mut self, path: &ast::Path, id: ast::NodeId, _: ()) {
189 self.lookup_and_handle_definition(&id);
190 visit::walk_path(self, path, ());
193 fn visit_item(&mut self, _item: &ast::Item, _: ()) {
194 // Do not recurse into items. These items will be added to the
195 // worklist and recursed into manually if necessary.
199 fn has_allow_dead_code_or_lang_attr(attrs: &[ast::Attribute]) -> bool {
200 contains_lint(attrs, allow, DEAD_CODE_LINT_STR)
201 || attr::contains_name(attrs, "lang")
204 // This visitor seeds items that
205 // 1) We want to explicitly consider as live:
206 // * Item annotated with #[allow(dead_code)]
207 // - This is done so that if we want to suppress warnings for a
208 // group of dead functions, we only have to annotate the "root".
209 // For example, if both `f` and `g` are dead and `f` calls `g`,
210 // then annotating `f` with `#[allow(dead_code)]` will suppress
211 // warning for both `f` and `g`.
212 // * Item annotated with #[lang=".."]
213 // - This is because lang items are always callable from elsewhere.
215 // 2) We are not sure to be live or not
216 // * Implementation of a trait method
218 worklist: ~[ast::NodeId],
221 impl Visitor<()> for LifeSeeder {
222 fn visit_item(&mut self, item: &ast::Item, _: ()) {
223 if has_allow_dead_code_or_lang_attr(item.attrs) {
224 self.worklist.push(item.id);
227 ast::ItemImpl(_, Some(ref _trait_ref), _, ref methods) => {
228 for method in methods.iter() {
229 self.worklist.push(method.id);
234 visit::walk_item(self, item, ());
237 fn visit_fn(&mut self, fk: &visit::FnKind,
238 _: &ast::FnDecl, block: &ast::Block,
239 _: codemap::Span, id: ast::NodeId, _: ()) {
240 // Check for method here because methods are not ast::Item
242 visit::FkMethod(_, _, method) => {
243 if has_allow_dead_code_or_lang_attr(method.attrs) {
244 self.worklist.push(id);
249 visit::walk_block(self, block, ());
253 fn create_and_seed_worklist(tcx: ty::ctxt,
254 exported_items: &privacy::ExportedItems,
255 reachable_symbols: &HashSet<ast::NodeId>,
256 krate: &ast::Crate) -> ~[ast::NodeId] {
257 let mut worklist = ~[];
259 // Preferably, we would only need to seed the worklist with reachable
260 // symbols. However, since the set of reachable symbols differs
261 // depending on whether a crate is built as bin or lib, and we want
262 // the warning to be consistent, we also seed the worklist with
264 for &id in exported_items.iter() {
267 for &id in reachable_symbols.iter() {
272 match tcx.sess.entry_fn.get() {
273 Some((id, _)) => worklist.push(id),
277 // Seed implemeneted trait methods
278 let mut life_seeder = LifeSeeder {
281 visit::walk_crate(&mut life_seeder, krate, ());
283 return life_seeder.worklist;
286 fn find_live(tcx: ty::ctxt,
287 method_map: typeck::MethodMap,
288 exported_items: &privacy::ExportedItems,
289 reachable_symbols: &HashSet<ast::NodeId>,
291 -> ~HashSet<ast::NodeId> {
292 let worklist = create_and_seed_worklist(tcx, exported_items,
293 reachable_symbols, krate);
294 let mut symbol_visitor = MarkSymbolVisitor::new(tcx, method_map, worklist);
295 symbol_visitor.mark_live_symbols();
296 symbol_visitor.live_symbols
299 fn should_warn(item: &ast::Item) -> bool {
304 | ast::ItemStruct(..) => true,
309 fn get_struct_ctor_id(item: &ast::Item) -> Option<ast::NodeId> {
311 ast::ItemStruct(struct_def, _) => struct_def.ctor_id,
318 live_symbols: ~HashSet<ast::NodeId>,
322 // id := node id of an item's definition.
323 // ctor_id := `Some` if the item is a struct_ctor (tuple struct),
325 // If the item is a struct_ctor, then either its `id` or
326 // `ctor_id` (unwrapped) is in the live_symbols set. More specifically,
327 // DefMap maps the ExprPath of a struct_ctor to the node referred by
328 // `ctor_id`. On the other hand, in a statement like
329 // `type <ident> <generics> = <ty>;` where <ty> refers to a struct_ctor,
330 // DefMap maps <ty> to `id` instead.
331 fn symbol_is_live(&mut self, id: ast::NodeId,
332 ctor_id: Option<ast::NodeId>) -> bool {
333 if self.live_symbols.contains(&id)
334 || ctor_id.map_or(false,
335 |ctor| self.live_symbols.contains(&ctor)) {
338 // If it's a type whose methods are live, then it's live, too.
339 // This is done to handle the case where, for example, the static
340 // method of a private type is used, but the type itself is never
342 let def_id = local_def(id);
343 let inherent_impls = self.tcx.inherent_impls.borrow();
344 match inherent_impls.get().find(&def_id) {
346 Some(ref impl_list) => {
347 let impl_list = impl_list.borrow();
348 for impl_ in impl_list.get().iter() {
349 for method in impl_.methods.iter() {
350 if self.live_symbols.contains(&method.def_id.node) {
360 fn warn_dead_code(&mut self, id: ast::NodeId,
361 span: codemap::Span, ident: ast::Ident) {
362 self.tcx.sess.add_lint(DeadCode, id, span,
363 format!("code is never used: `{}`",
364 token::get_ident(ident)));
368 impl Visitor<()> for DeadVisitor {
369 fn visit_item(&mut self, item: &ast::Item, _: ()) {
370 let ctor_id = get_struct_ctor_id(item);
371 if !self.symbol_is_live(item.id, ctor_id) && should_warn(item) {
372 self.warn_dead_code(item.id, item.span, item.ident);
374 visit::walk_item(self, item, ());
377 fn visit_foreign_item(&mut self, fi: &ast::ForeignItem, _: ()) {
378 if !self.symbol_is_live(fi.id, None) {
379 self.warn_dead_code(fi.id, fi.span, fi.ident);
381 visit::walk_foreign_item(self, fi, ());
384 fn visit_fn(&mut self, fk: &visit::FnKind,
385 _: &ast::FnDecl, block: &ast::Block,
386 span: codemap::Span, id: ast::NodeId, _: ()) {
387 // Have to warn method here because methods are not ast::Item
389 visit::FkMethod(..) => {
390 let ident = visit::name_of_fn(fk);
391 if !self.symbol_is_live(id, None) {
392 self.warn_dead_code(id, span, ident);
397 visit::walk_block(self, block, ());
400 // Overwrite so that we don't warn the trait method itself.
401 fn visit_trait_method(&mut self, trait_method: &ast::TraitMethod, _: ()) {
402 match *trait_method {
403 ast::Provided(method) => visit::walk_block(self, method.body, ()),
404 ast::Required(_) => ()
409 pub fn check_crate(tcx: ty::ctxt,
410 method_map: typeck::MethodMap,
411 exported_items: &privacy::ExportedItems,
412 reachable_symbols: &HashSet<ast::NodeId>,
413 krate: &ast::Crate) {
414 let live_symbols = find_live(tcx, method_map, exported_items,
415 reachable_symbols, krate);
416 let mut visitor = DeadVisitor { tcx: tcx, live_symbols: live_symbols };
417 visit::walk_crate(&mut visitor, krate, ());