src/librustc_mir_build/lints.rs

   1 use rustc_hir::def_id::DefId;
   2 use rustc_hir::intravisit::FnKind;
   3 use rustc_index::bit_set::BitSet;
   4 use rustc_index::vec::IndexVec;
   5 use rustc_middle::hir::map::blocks::FnLikeNode;
   6 use rustc_middle::mir::{BasicBlock, Body, ReadOnlyBodyAndCache, TerminatorKind, START_BLOCK};
   7 use rustc_middle::ty::subst::InternalSubsts;
   8 use rustc_middle::ty::{self, AssocItem, AssocItemContainer, Instance, TyCtxt};
   9 use rustc_session::lint::builtin::UNCONDITIONAL_RECURSION;
  10 use std::collections::VecDeque;
  11
  12 crate fn check<'tcx>(tcx: TyCtxt<'tcx>, body: &ReadOnlyBodyAndCache<'_, 'tcx>, 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(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>(
  21     tcx: TyCtxt<'tcx>,
  22     fn_kind: FnKind<'_>,
  23     body: &ReadOnlyBodyAndCache<'_, 'tcx>,
  24     def_id: DefId,
  25 ) {
  26     if let FnKind::Closure(_) = fn_kind {
  27         // closures can't recur, so they don't matter.
  28         return;
  29     }
  30
  31     let self_calls = find_blocks_calling_self(tcx, &body, def_id);
  32     let mut results = IndexVec::from_elem_n(vec![], body.basic_blocks().len());
  33     let mut queue: VecDeque<_> = self_calls.iter().collect();
  34
  35     while let Some(bb) = queue.pop_front() {
  36         if !results[bb].is_empty() {
  37             // Already propagated.
  38             continue;
  39         }
  40
  41         let locations = if self_calls.contains(bb) {
  42             // `bb` *is* a self-call.
  43             vec![bb]
  44         } else {
  45             // If *all* successors of `bb` lead to a self-call, emit notes at all of their
  46             // locations.
  47
  48             // Converging successors without unwind paths.
  49             let terminator = body[bb].terminator();
  50             let relevant_successors = match &terminator.kind {
  51                 TerminatorKind::Call { destination: Some((_, dest)), .. } => {
  52                     Some(dest).into_iter().chain(&[])
  53                 }
  54                 TerminatorKind::Call { destination: None, .. } => None.into_iter().chain(&[]),
  55                 TerminatorKind::SwitchInt { targets, .. } => None.into_iter().chain(targets),
  56                 TerminatorKind::Goto { target }
  57                 | TerminatorKind::Drop { target, .. }
  58                 | TerminatorKind::DropAndReplace { target, .. }
  59                 | TerminatorKind::Assert { target, .. } => Some(target).into_iter().chain(&[]),
  60                 TerminatorKind::Yield { .. } | TerminatorKind::GeneratorDrop => {
  61                     None.into_iter().chain(&[])
  62                 }
  63                 TerminatorKind::FalseEdges { real_target, .. }
  64                 | TerminatorKind::FalseUnwind { real_target, .. } => {
  65                     Some(real_target).into_iter().chain(&[])
  66                 }
  67                 TerminatorKind::Resume
  68                 | TerminatorKind::Abort
  69                 | TerminatorKind::Return
  70                 | TerminatorKind::Unreachable => {
  71                     unreachable!("unexpected terminator {:?}", terminator.kind)
  72                 }
  73             };
  74
  75             let all_are_self_calls =
  76                 relevant_successors.clone().all(|&succ| !results[succ].is_empty());
  77
  78             if all_are_self_calls {
  79                 relevant_successors.flat_map(|&succ| results[succ].iter().copied()).collect()
  80             } else {
  81                 vec![]
  82             }
  83         };
  84
  85         if !locations.is_empty() {
  86             // This is a newly confirmed-to-always-reach-self-call block.
  87             results[bb] = locations;
  88
  89             // Propagate backwards through the CFG.
  90             debug!("propagate loc={:?} in {:?} -> {:?}", results[bb], bb, body.predecessors()[bb]);
  91             queue.extend(body.predecessors()[bb].iter().copied());
  92         }
  93     }
  94
  95     debug!("unconditional recursion results: {:?}", results);
  96
  97     let self_call_locations = &mut results[START_BLOCK];
  98     self_call_locations.sort();
  99     self_call_locations.dedup();
 100
 101     if !self_call_locations.is_empty() {
 102         let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
 103         let sp = tcx.sess.source_map().guess_head_span(tcx.hir().span(hir_id));
 104         tcx.struct_span_lint_hir(UNCONDITIONAL_RECURSION, hir_id, sp, |lint| {
 105             let mut db = lint.build("function cannot return without recursing");
 106             db.span_label(sp, "cannot return without recursing");
 107             // offer some help to the programmer.
 108             for bb in self_call_locations {
 109                 let span = body.basic_blocks()[*bb].terminator().source_info.span;
 110                 db.span_label(span, "recursive call site");
 111             }
 112             db.help("a `loop` may express intention better if this is on purpose");
 113             db.emit();
 114         });
 115     }
 116 }
 117
 118 /// Finds blocks with `Call` terminators that would end up calling back into the same method.
 119 fn find_blocks_calling_self<'tcx>(
 120     tcx: TyCtxt<'tcx>,
 121     body: &Body<'tcx>,
 122     def_id: DefId,
 123 ) -> BitSet<BasicBlock> {
 124     let param_env = tcx.param_env(def_id);
 125     let trait_substs_count = match tcx.opt_associated_item(def_id) {
 126         Some(AssocItem { container: AssocItemContainer::TraitContainer(trait_def_id), .. }) => {
 127             tcx.generics_of(trait_def_id).count()
 128         }
 129         _ => 0,
 130     };
 131     let caller_substs = &InternalSubsts::identity_for_item(tcx, def_id)[..trait_substs_count];
 132
 133     let mut self_calls = BitSet::new_empty(body.basic_blocks().len());
 134
 135     for (bb, data) in body.basic_blocks().iter_enumerated() {
 136         if let TerminatorKind::Call { func, .. } = &data.terminator().kind {
 137             let func_ty = func.ty(body, tcx);
 138
 139             if let ty::FnDef(fn_def_id, substs) = func_ty.kind {
 140                 let (call_fn_id, call_substs) =
 141                     if let Some(instance) = Instance::resolve(tcx, param_env, fn_def_id, substs) {
 142                         (instance.def_id(), instance.substs)
 143                     } else {
 144                         (fn_def_id, substs)
 145                     };
 146
 147                 // FIXME(#57965): Make this work across function boundaries
 148
 149                 let is_self_call =
 150                     call_fn_id == def_id && &call_substs[..caller_substs.len()] == caller_substs;
 151
 152                 if is_self_call {
 153                     self_calls.insert(bb);
 154                 }
 155             }
 156         }
 157     }
 158
 159     self_calls
 160 }