src/librustc_mir/lints.rs

   1 // Copyright 2018 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 use rustc_data_structures::bit_set::BitSet;
  12 use rustc::hir::def_id::DefId;
  13 use rustc::hir::intravisit::FnKind;
  14 use rustc::hir::map::blocks::FnLikeNode;
  15 use rustc::lint::builtin::UNCONDITIONAL_RECURSION;
  16 use rustc::mir::{self, Mir, TerminatorKind};
  17 use rustc::ty::{AssociatedItem, AssociatedItemContainer, Instance, TyCtxt, TyKind};
  18 use rustc::ty::subst::Substs;
  19
  20 pub fn check(tcx: TyCtxt<'a, 'tcx, 'tcx>,
  21              mir: &Mir<'tcx>,
  22              def_id: DefId) {
  23     let node_id = tcx.hir().as_local_node_id(def_id).unwrap();
  24
  25     if let Some(fn_like_node) = FnLikeNode::from_node(tcx.hir().get(node_id)) {
  26         check_fn_for_unconditional_recursion(tcx, fn_like_node.kind(), mir, def_id);
  27     }
  28 }
  29
  30 fn check_fn_for_unconditional_recursion(tcx: TyCtxt<'a, 'tcx, 'tcx>,
  31                                         fn_kind: FnKind,
  32                                         mir: &Mir<'tcx>,
  33                                         def_id: DefId) {
  34     if let FnKind::Closure(_) = fn_kind {
  35         // closures can't recur, so they don't matter.
  36         return;
  37     }
  38
  39     //FIXME(#54444) rewrite this lint to use the dataflow framework
  40
  41     // Walk through this function (say `f`) looking to see if
  42     // every possible path references itself, i.e. the function is
  43     // called recursively unconditionally. This is done by trying
  44     // to find a path from the entry node to the exit node that
  45     // *doesn't* call `f` by traversing from the entry while
  46     // pretending that calls of `f` are sinks (i.e. ignoring any
  47     // exit edges from them).
  48     //
  49     // NB. this has an edge case with non-returning statements,
  50     // like `loop {}` or `panic!()`: control flow never reaches
  51     // the exit node through these, so one can have a function
  52     // that never actually calls itself but is still picked up by
  53     // this lint:
  54     //
  55     //     fn f(cond: bool) {
  56     //         if !cond { panic!() } // could come from `assert!(cond)`
  57     //         f(false)
  58     //     }
  59     //
  60     // In general, functions of that form may be able to call
  61     // itself a finite number of times and then diverge. The lint
  62     // considers this to be an error for two reasons, (a) it is
  63     // easier to implement, and (b) it seems rare to actually want
  64     // to have behaviour like the above, rather than
  65     // e.g. accidentally recursing after an assert.
  66
  67     let basic_blocks = mir.basic_blocks();
  68     let mut reachable_without_self_call_queue = vec![mir::START_BLOCK];
  69     let mut reached_exit_without_self_call = false;
  70     let mut self_call_locations = vec![];
  71     let mut visited = BitSet::new_empty(basic_blocks.len());
  72
  73     let param_env = tcx.param_env(def_id);
  74     let trait_substs_count =
  75         match tcx.opt_associated_item(def_id) {
  76             Some(AssociatedItem {
  77                 container: AssociatedItemContainer::TraitContainer(trait_def_id),
  78                 ..
  79             }) => tcx.generics_of(trait_def_id).count(),
  80             _ => 0
  81         };
  82     let caller_substs = &Substs::identity_for_item(tcx, def_id)[..trait_substs_count];
  83
  84     while let Some(bb) = reachable_without_self_call_queue.pop() {
  85         if visited.contains(bb) {
  86             //already done
  87             continue;
  88         }
  89
  90         visited.insert(bb);
  91
  92         let block = &basic_blocks[bb];
  93
  94         if let Some(ref terminator) = block.terminator {
  95             match terminator.kind {
  96                 TerminatorKind::Call { ref func, .. } => {
  97                     let func_ty = func.ty(mir, tcx);
  98
  99                     if let TyKind::FnDef(fn_def_id, substs) = func_ty.sty {
 100                         let (call_fn_id, call_substs) =
 101                             if let Some(instance) = Instance::resolve(tcx,
 102                                                                         param_env,
 103                                                                         fn_def_id,
 104                                                                         substs) {
 105                                 (instance.def_id(), instance.substs)
 106                             } else {
 107                                 (fn_def_id, substs)
 108                             };
 109
 110                         let is_self_call =
 111                             call_fn_id == def_id &&
 112                                 &call_substs[..caller_substs.len()] == caller_substs;
 113
 114                         if is_self_call {
 115                             self_call_locations.push(terminator.source_info);
 116
 117                             //this is a self call so we shouldn't explore
 118                             //further down this path
 119                             continue;
 120                         }
 121                     }
 122                 },
 123                 TerminatorKind::Abort | TerminatorKind::Return => {
 124                     //found a path!
 125                     reached_exit_without_self_call = true;
 126                     break;
 127                 }
 128                 _ => {}
 129             }
 130
 131             for successor in terminator.successors() {
 132                 reachable_without_self_call_queue.push(*successor);
 133             }
 134         }
 135     }
 136
 137     // Check the number of self calls because a function that
 138     // doesn't return (e.g. calls a `-> !` function or `loop { /*
 139     // no break */ }`) shouldn't be linted unless it actually
 140     // recurs.
 141     if !reached_exit_without_self_call && !self_call_locations.is_empty() {
 142         let node_id = tcx.hir().as_local_node_id(def_id).unwrap();
 143         let sp = tcx.sess.source_map().def_span(tcx.hir().span(node_id));
 144         let mut db = tcx.struct_span_lint_node(UNCONDITIONAL_RECURSION,
 145                                                 node_id,
 146                                                 sp,
 147                                                 "function cannot return without recursing");
 148         db.span_label(sp, "cannot return without recursing");
 149         // offer some help to the programmer.
 150         for location in &self_call_locations {
 151             db.span_label(location.span, "recursive call site");
 152         }
 153         db.help("a `loop` may express intention better if this is on purpose");
 154         db.emit();
 155     }
 156 }