1 use rustc_hir::def_id::DefId;
2 use rustc_hir::intravisit::FnKind;
3 use rustc_index::bit_set::BitSet;
4 use rustc_middle::hir::map::blocks::FnLikeNode;
5 use rustc_middle::mir::{self, Body, TerminatorKind};
6 use rustc_middle::ty::subst::InternalSubsts;
7 use rustc_middle::ty::{self, AssocItem, AssocItemContainer, Instance, TyCtxt};
8 use rustc_session::lint::builtin::UNCONDITIONAL_RECURSION;
10 crate fn check<'tcx>(tcx: TyCtxt<'tcx>, body: &Body<'tcx>, def_id: DefId) {
11 let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
13 if let Some(fn_like_node) = FnLikeNode::from_node(tcx.hir().get(hir_id)) {
14 check_fn_for_unconditional_recursion(tcx, fn_like_node.kind(), body, def_id);
18 fn check_fn_for_unconditional_recursion<'tcx>(
24 if let FnKind::Closure(_) = fn_kind {
25 // closures can't recur, so they don't matter.
29 //FIXME(#54444) rewrite this lint to use the dataflow framework
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).
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
46 // if !cond { panic!() } // could come from `assert!(cond)`
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.
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());
63 let param_env = tcx.param_env(def_id);
64 let trait_substs_count = match tcx.opt_associated_item(def_id) {
65 Some(AssocItem { container: AssocItemContainer::TraitContainer(trait_def_id), .. }) => {
66 tcx.generics_of(trait_def_id).count()
70 let caller_substs = &InternalSubsts::identity_for_item(tcx, def_id)[..trait_substs_count];
72 while let Some(bb) = reachable_without_self_call_queue.pop() {
73 if !visited.insert(bb) {
78 let block = &basic_blocks[bb];
80 if let Some(ref terminator) = block.terminator {
81 match terminator.kind {
82 TerminatorKind::Call { ref func, .. } => {
83 let func_ty = func.ty(body, tcx);
85 if let ty::FnDef(fn_def_id, substs) = func_ty.kind {
86 let (call_fn_id, call_substs) = if let Some(instance) =
87 Instance::resolve(tcx, param_env, fn_def_id, substs)
89 (instance.def_id(), instance.substs)
94 let is_self_call = call_fn_id == def_id
95 && &call_substs[..caller_substs.len()] == caller_substs;
98 self_call_locations.push(terminator.source_info);
100 //this is a self call so we shouldn't explore
101 //further down this path
106 TerminatorKind::Abort | TerminatorKind::Return => {
108 reached_exit_without_self_call = true;
114 for successor in terminator.successors() {
115 reachable_without_self_call_queue.push(*successor);
120 // Check the number of self calls because a function that
121 // doesn't return (e.g., calls a `-> !` function or `loop { /*
122 // no break */ }`) shouldn't be linted unless it actually
124 if !reached_exit_without_self_call && !self_call_locations.is_empty() {
125 let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
126 let sp = tcx.sess.source_map().guess_head_span(tcx.hir().span(hir_id));
127 tcx.struct_span_lint_hir(UNCONDITIONAL_RECURSION, hir_id, sp, |lint| {
128 let mut db = lint.build("function cannot return without recursing");
129 db.span_label(sp, "cannot return without recursing");
130 // offer some help to the programmer.
131 for location in &self_call_locations {
132 db.span_label(location.span, "recursive call site");
134 db.help("a `loop` may express intention better if this is on purpose");