src/librustc_mir/lints.rs

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