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.
4 //
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.
10
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.
14
15 use middle::lint::{allow, contains_lint, DeadCode};
16 use middle::privacy;
17 use middle::ty;
18 use middle::typeck;
19 use util::nodemap::NodeSet;
20
21 use collections::HashSet;
22 use syntax::ast;
23 use syntax::ast_map;
24 use syntax::ast_util::{local_def, def_id_of_def, is_local};
25 use syntax::attr;
26 use syntax::codemap;
27 use syntax::parse::token;
28 use syntax::visit::Visitor;
29 use syntax::visit;
30
31 pub static DEAD_CODE_LINT_STR: &'static str = "dead_code";
32
33 // Any local node that may call something in its body block should be
34 // explored. For example, if it's a live NodeItem that is a
35 // function, then we should explore its block to check for codes that
36 // may need to be marked as live.
37 fn should_explore(tcx: &ty::ctxt, def_id: ast::DefId) -> bool {
38 if !is_local(def_id) {
39 return false;
40 }
41
42 match tcx.map.find(def_id.node) {
43 Some(ast_map::NodeItem(..))
44 | Some(ast_map::NodeMethod(..))
45 | Some(ast_map::NodeForeignItem(..))
46 | Some(ast_map::NodeTraitMethod(..)) => true,
47 _ => false
48 }
49 }
50
51 struct MarkSymbolVisitor<'a> {
52 worklist: Vec<ast::NodeId>,
53 tcx: &'a ty::ctxt,
54 live_symbols: Box<HashSet<ast::NodeId>>,
55 }
56
57 impl<'a> MarkSymbolVisitor<'a> {
58 fn new(tcx: &'a ty::ctxt,
59 worklist: Vec<ast::NodeId>) -> MarkSymbolVisitor<'a> {
60 MarkSymbolVisitor {
61 worklist: worklist,
62 tcx: tcx,
63 live_symbols: box HashSet::new(),
64 }
65 }
66
67 fn check_def_id(&mut self, def_id: ast::DefId) {
68 if should_explore(self.tcx, def_id) {
69 self.worklist.push(def_id.node);
70 }
71 self.live_symbols.insert(def_id.node);
72 }
73
74 fn lookup_and_handle_definition(&mut self, id: &ast::NodeId) {
75 let def = match self.tcx.def_map.borrow().find(id) {
76 Some(&def) => def,
77 None => return
78 };
79 let def_id = match def {
80 ast::DefVariant(enum_id, _, _) => Some(enum_id),
81 ast::DefPrimTy(_) => None,
82 _ => Some(def_id_of_def(def)),
83 };
84 match def_id {
85 Some(def_id) => self.check_def_id(def_id),
86 None => (),
87 }
88 }
89
90 fn lookup_and_handle_method(&mut self, id: ast::NodeId,
91 span: codemap::Span) {
92 let method_call = typeck::MethodCall::expr(id);
93 match self.tcx.method_map.borrow().find(&method_call) {
94 Some(method) => {
95 match method.origin {
96 typeck::MethodStatic(def_id) => {
97 match ty::provided_source(self.tcx, def_id) {
98 Some(p_did) => self.check_def_id(p_did),
99 None => self.check_def_id(def_id)
100 }
101 }
102 typeck::MethodParam(typeck::MethodParam {
103 trait_id: trait_id,
104 method_num: index,
105 ..
106 })
107 | typeck::MethodObject(typeck::MethodObject {
108 trait_id: trait_id,
109 method_num: index,
110 ..
111 }) => {
112 let def_id = ty::trait_method(self.tcx,
113 trait_id, index).def_id;
114 self.check_def_id(def_id);
115 }
116 }
117 }
118 None => {
119 self.tcx.sess.span_bug(span,
120 "method call expression not \
121 in method map?!")
122 }
123 }
124 }
125
126 fn mark_live_symbols(&mut self) {
127 let mut scanned = HashSet::new();
128 while self.worklist.len() > 0 {
129 let id = self.worklist.pop().unwrap();
130 if scanned.contains(&id) {
131 continue
132 }
133 scanned.insert(id);
134
135 match self.tcx.map.find(id) {
136 Some(ref node) => {
137 self.live_symbols.insert(id);
138 self.visit_node(node);
139 }
140 None => (),
141 }
142 }
143 }
144
145 fn visit_node(&mut self, node: &ast_map::Node) {
146 match *node {
147 ast_map::NodeItem(item) => {
148 match item.node {
149 ast::ItemFn(..)
150 | ast::ItemTy(..)
151 | ast::ItemEnum(..)
152 | ast::ItemStruct(..)
153 | ast::ItemStatic(..) => {
154 visit::walk_item(self, item, ());
155 }
156 _ => ()
157 }
158 }
159 ast_map::NodeTraitMethod(trait_method) => {
160 visit::walk_trait_method(self, trait_method, ());
161 }
162 ast_map::NodeMethod(method) => {
163 visit::walk_block(self, method.body, ());
164 }
165 ast_map::NodeForeignItem(foreign_item) => {
166 visit::walk_foreign_item(self, foreign_item, ());
167 }
168 _ => ()
169 }
170 }
171 }
172
173 impl<'a> Visitor<()> for MarkSymbolVisitor<'a> {
174
175 fn visit_expr(&mut self, expr: &ast::Expr, _: ()) {
176 match expr.node {
177 ast::ExprMethodCall(..) => {
178 self.lookup_and_handle_method(expr.id, expr.span);
179 }
180 _ => ()
181 }
182
183 visit::walk_expr(self, expr, ())
184 }
185
186 fn visit_path(&mut self, path: &ast::Path, id: ast::NodeId, _: ()) {
187 self.lookup_and_handle_definition(&id);
188 visit::walk_path(self, path, ());
189 }
190
191 fn visit_item(&mut self, _item: &ast::Item, _: ()) {
192 // Do not recurse into items. These items will be added to the
193 // worklist and recursed into manually if necessary.
194 }
195 }
196
197 fn has_allow_dead_code_or_lang_attr(attrs: &[ast::Attribute]) -> bool {
198 contains_lint(attrs, allow, DEAD_CODE_LINT_STR)
199 || attr::contains_name(attrs.as_slice(), "lang")
200 }
201
202 // This visitor seeds items that
203 // 1) We want to explicitly consider as live:
204 // * Item annotated with #[allow(dead_code)]
205 // - This is done so that if we want to suppress warnings for a
206 // group of dead functions, we only have to annotate the "root".
207 // For example, if both `f` and `g` are dead and `f` calls `g`,
208 // then annotating `f` with `#[allow(dead_code)]` will suppress
209 // warning for both `f` and `g`.
210 // * Item annotated with #[lang=".."]
211 // - This is because lang items are always callable from elsewhere.
212 // or
213 // 2) We are not sure to be live or not
214 // * Implementation of a trait method
215 struct LifeSeeder {
216 worklist: Vec<ast::NodeId> ,
217 }
218
219 impl Visitor<()> for LifeSeeder {
220 fn visit_item(&mut self, item: &ast::Item, _: ()) {
221 if has_allow_dead_code_or_lang_attr(item.attrs.as_slice()) {
222 self.worklist.push(item.id);
223 }
224 match item.node {
225 ast::ItemImpl(_, Some(ref _trait_ref), _, ref methods) => {
226 for method in methods.iter() {
227 self.worklist.push(method.id);
228 }
229 }
230 _ => ()
231 }
232 visit::walk_item(self, item, ());
233 }
234
235 fn visit_fn(&mut self, fk: &visit::FnKind,
236 _: &ast::FnDecl, block: &ast::Block,
237 _: codemap::Span, id: ast::NodeId, _: ()) {
238 // Check for method here because methods are not ast::Item
239 match *fk {
240 visit::FkMethod(_, _, method) => {
241 if has_allow_dead_code_or_lang_attr(method.attrs.as_slice()) {
242 self.worklist.push(id);
243 }
244 }
245 _ => ()
246 }
247 visit::walk_block(self, block, ());
248 }
249 }
250
251 fn create_and_seed_worklist(tcx: &ty::ctxt,
252 exported_items: &privacy::ExportedItems,
253 reachable_symbols: &NodeSet,
254 krate: &ast::Crate) -> Vec<ast::NodeId> {
255 let mut worklist = Vec::new();
256
257 // Preferably, we would only need to seed the worklist with reachable
258 // symbols. However, since the set of reachable symbols differs
259 // depending on whether a crate is built as bin or lib, and we want
260 // the warning to be consistent, we also seed the worklist with
261 // exported symbols.
262 for &id in exported_items.iter() {
263 worklist.push(id);
264 }
265 for &id in reachable_symbols.iter() {
266 worklist.push(id);
267 }
268
269 // Seed entry point
270 match *tcx.sess.entry_fn.borrow() {
271 Some((id, _)) => worklist.push(id),
272 None => ()
273 }
274
275 // Seed implemented trait methods
276 let mut life_seeder = LifeSeeder {
277 worklist: worklist
278 };
279 visit::walk_crate(&mut life_seeder, krate, ());
280
281 return life_seeder.worklist;
282 }
283
284 fn find_live(tcx: &ty::ctxt,
285 exported_items: &privacy::ExportedItems,
286 reachable_symbols: &NodeSet,
287 krate: &ast::Crate)
288 -> Box<HashSet<ast::NodeId>> {
289 let worklist = create_and_seed_worklist(tcx, exported_items,
290 reachable_symbols, krate);
291 let mut symbol_visitor = MarkSymbolVisitor::new(tcx, worklist);
292 symbol_visitor.mark_live_symbols();
293 symbol_visitor.live_symbols
294 }
295
296 fn should_warn(item: &ast::Item) -> bool {
297 match item.node {
298 ast::ItemStatic(..)
299 | ast::ItemFn(..)
300 | ast::ItemEnum(..)
301 | ast::ItemStruct(..) => true,
302 _ => false
303 }
304 }
305
306 fn get_struct_ctor_id(item: &ast::Item) -> Option<ast::NodeId> {
307 match item.node {
308 ast::ItemStruct(struct_def, _) => struct_def.ctor_id,
309 _ => None
310 }
311 }
312
313 struct DeadVisitor<'a> {
314 tcx: &'a ty::ctxt,
315 live_symbols: Box<HashSet<ast::NodeId>>,
316 }
317
318 impl<'a> DeadVisitor<'a> {
319 // id := node id of an item's definition.
320 // ctor_id := `Some` if the item is a struct_ctor (tuple struct),
321 // `None` otherwise.
322 // If the item is a struct_ctor, then either its `id` or
323 // `ctor_id` (unwrapped) is in the live_symbols set. More specifically,
324 // DefMap maps the ExprPath of a struct_ctor to the node referred by
325 // `ctor_id`. On the other hand, in a statement like
326 // `type <ident> <generics> = <ty>;` where <ty> refers to a struct_ctor,
327 // DefMap maps <ty> to `id` instead.
328 fn symbol_is_live(&mut self, id: ast::NodeId,
329 ctor_id: Option<ast::NodeId>) -> bool {
330 if self.live_symbols.contains(&id)
331 || ctor_id.map_or(false,
332 |ctor| self.live_symbols.contains(&ctor)) {
333 return true;
334 }
335 // If it's a type whose methods are live, then it's live, too.
336 // This is done to handle the case where, for example, the static
337 // method of a private type is used, but the type itself is never
338 // called directly.
339 let impl_methods = self.tcx.impl_methods.borrow();
340 match self.tcx.inherent_impls.borrow().find(&local_def(id)) {
341 None => (),
342 Some(impl_list) => {
343 for impl_did in impl_list.borrow().iter() {
344 for method_did in impl_methods.get(impl_did).iter() {
345 if self.live_symbols.contains(&method_did.node) {
346 return true;
347 }
348 }
349 }
350 }
351 }
352 false
353 }
354
355 fn warn_dead_code(&mut self, id: ast::NodeId,
356 span: codemap::Span, ident: ast::Ident) {
357 self.tcx.sess.add_lint(DeadCode, id, span,
358 format!("code is never used: `{}`",
359 token::get_ident(ident)));
360 }
361 }
362
363 impl<'a> Visitor<()> for DeadVisitor<'a> {
364 fn visit_item(&mut self, item: &ast::Item, _: ()) {
365 let ctor_id = get_struct_ctor_id(item);
366 if !self.symbol_is_live(item.id, ctor_id) && should_warn(item) {
367 self.warn_dead_code(item.id, item.span, item.ident);
368 }
369 visit::walk_item(self, item, ());
370 }
371
372 fn visit_foreign_item(&mut self, fi: &ast::ForeignItem, _: ()) {
373 if !self.symbol_is_live(fi.id, None) {
374 self.warn_dead_code(fi.id, fi.span, fi.ident);
375 }
376 visit::walk_foreign_item(self, fi, ());
377 }
378
379 fn visit_fn(&mut self, fk: &visit::FnKind,
380 _: &ast::FnDecl, block: &ast::Block,
381 span: codemap::Span, id: ast::NodeId, _: ()) {
382 // Have to warn method here because methods are not ast::Item
383 match *fk {
384 visit::FkMethod(..) => {
385 let ident = visit::name_of_fn(fk);
386 if !self.symbol_is_live(id, None) {
387 self.warn_dead_code(id, span, ident);
388 }
389 }
390 _ => ()
391 }
392 visit::walk_block(self, block, ());
393 }
394
395 // Overwrite so that we don't warn the trait method itself.
396 fn visit_trait_method(&mut self, trait_method: &ast::TraitMethod, _: ()) {
397 match *trait_method {
398 ast::Provided(method) => visit::walk_block(self, method.body, ()),
399 ast::Required(_) => ()
400 }
401 }
402 }
403
404 pub fn check_crate(tcx: &ty::ctxt,
405 exported_items: &privacy::ExportedItems,
406 reachable_symbols: &NodeSet,
407 krate: &ast::Crate) {
408 let live_symbols = find_live(tcx, exported_items,
409 reachable_symbols, krate);
410 let mut visitor = DeadVisitor { tcx: tcx, live_symbols: live_symbols };
411 visit::walk_crate(&mut visitor, krate, ());
412 }
librustc/middle/dead.rs:312:1-312:1 -struct- definition:
struct DeadVisitor<'a> {
tcx: &'a ty::ctxt,
live_symbols: Box<HashSet<ast::NodeId>>,
references:- 3409: reachable_symbols, krate);
410: let mut visitor = DeadVisitor { tcx: tcx, live_symbols: live_symbols };
411: visit::walk_crate(&mut visitor, krate, ());
librustc/middle/dead.rs:50:1-50:1 -struct- definition:
struct MarkSymbolVisitor<'a> {
worklist: Vec<ast::NodeId>,
tcx: &'a ty::ctxt,
references:- 457: impl<'a> MarkSymbolVisitor<'a> {
58: fn new(tcx: &'a ty::ctxt,
--
173: impl<'a> Visitor<()> for MarkSymbolVisitor<'a> {
librustc/middle/dead.rs:196:1-196:1 -fn- definition:
fn has_allow_dead_code_or_lang_attr(attrs: &[ast::Attribute]) -> bool {
contains_lint(attrs, allow, DEAD_CODE_LINT_STR)
|| attr::contains_name(attrs.as_slice(), "lang")
references:- 2220: fn visit_item(&mut self, item: &ast::Item, _: ()) {
221: if has_allow_dead_code_or_lang_attr(item.attrs.as_slice()) {
222: self.worklist.push(item.id);
--
240: visit::FkMethod(_, _, method) => {
241: if has_allow_dead_code_or_lang_attr(method.attrs.as_slice()) {
242: self.worklist.push(id);
librustc/middle/dead.rs:214:42-214:42 -struct- definition:
// * Implementation of a trait method
struct LifeSeeder {
worklist: Vec<ast::NodeId> ,
references:- 2275: // Seed implemented trait methods
276: let mut life_seeder = LifeSeeder {
277: worklist: worklist