src/librustc_mir_build/lints.rs

   1 use rustc_data_structures::graph::iterate::{
   2     ControlFlow, NodeStatus, TriColorDepthFirstSearch, TriColorVisitor,
   3 };
   4 use rustc_hir::def_id::LocalDefId;
   5 use rustc_hir::intravisit::FnKind;
   6 use rustc_middle::hir::map::blocks::FnLikeNode;
   7 use rustc_middle::mir::{BasicBlock, Body, Operand, TerminatorKind};
   8 use rustc_middle::ty::subst::{GenericArg, InternalSubsts};
   9 use rustc_middle::ty::{self, AssocItem, AssocItemContainer, Instance, TyCtxt};
  10 use rustc_session::lint::builtin::UNCONDITIONAL_RECURSION;
  11 use rustc_span::Span;
  12
  13 crate fn check<'tcx>(tcx: TyCtxt<'tcx>, body: &Body<'tcx>, def_id: LocalDefId) {
  14     let hir_id = tcx.hir().as_local_hir_id(def_id);
  15
  16     if let Some(fn_like_node) = FnLikeNode::from_node(tcx.hir().get(hir_id)) {
  17         if let FnKind::Closure(_) = fn_like_node.kind() {
  18             // closures can't recur, so they don't matter.
  19             return;
  20         }
  21
  22         // If this is trait/impl method, extract the trait's substs.
  23         let trait_substs = match tcx.opt_associated_item(def_id.to_def_id()) {
  24             Some(AssocItem {
  25                 container: AssocItemContainer::TraitContainer(trait_def_id), ..
  26             }) => {
  27                 let trait_substs_count = tcx.generics_of(*trait_def_id).count();
  28                 &InternalSubsts::identity_for_item(tcx, def_id.to_def_id())[..trait_substs_count]
  29             }
  30             _ => &[],
  31         };
  32
  33         let mut vis = Search { tcx, body, def_id, reachable_recursive_calls: vec![], trait_substs };
  34         if let Some(NonRecursive) = TriColorDepthFirstSearch::new(&body).run_from_start(&mut vis) {
  35             return;
  36         }
  37
  38         vis.reachable_recursive_calls.sort();
  39
  40         let hir_id = tcx.hir().as_local_hir_id(def_id);
  41         let sp = tcx.sess.source_map().guess_head_span(tcx.hir().span(hir_id));
  42         tcx.struct_span_lint_hir(UNCONDITIONAL_RECURSION, hir_id, sp, |lint| {
  43             let mut db = lint.build("function cannot return without recursing");
  44             db.span_label(sp, "cannot return without recursing");
  45             // offer some help to the programmer.
  46             for call_span in vis.reachable_recursive_calls {
  47                 db.span_label(call_span, "recursive call site");
  48             }
  49             db.help("a `loop` may express intention better if this is on purpose");
  50             db.emit();
  51         });
  52     }
  53 }
  54
  55 struct NonRecursive;
  56
  57 struct Search<'mir, 'tcx> {
  58     tcx: TyCtxt<'tcx>,
  59     body: &'mir Body<'tcx>,
  60     def_id: LocalDefId,
  61     trait_substs: &'tcx [GenericArg<'tcx>],
  62
  63     reachable_recursive_calls: Vec<Span>,
  64 }
  65
  66 impl<'mir, 'tcx> Search<'mir, 'tcx> {
  67     /// Returns `true` if `func` refers to the function we are searching in.
  68     fn is_recursive_call(&self, func: &Operand<'tcx>) -> bool {
  69         let Search { tcx, body, def_id, trait_substs, .. } = *self;
  70         let param_env = tcx.param_env(def_id);
  71
  72         let func_ty = func.ty(body, tcx);
  73         if let ty::FnDef(fn_def_id, substs) = func_ty.kind {
  74             let (call_fn_id, call_substs) =
  75                 if let Ok(Some(instance)) = Instance::resolve(tcx, param_env, fn_def_id, substs) {
  76                     (instance.def_id(), instance.substs)
  77                 } else {
  78                     (fn_def_id, substs)
  79                 };
  80
  81             // FIXME(#57965): Make this work across function boundaries
  82
  83             // If this is a trait fn, the substs on the trait have to match, or we might be
  84             // calling into an entirely different method (for example, a call from the default
  85             // method in the trait to `<A as Trait<B>>::method`, where `A` and/or `B` are
  86             // specific types).
  87             return call_fn_id == def_id.to_def_id()
  88                 && &call_substs[..trait_substs.len()] == trait_substs;
  89         }
  90
  91         false
  92     }
  93 }
  94
  95 impl<'mir, 'tcx> TriColorVisitor<&'mir Body<'tcx>> for Search<'mir, 'tcx> {
  96     type BreakVal = NonRecursive;
  97
  98     fn node_examined(
  99         &mut self,
 100         bb: BasicBlock,
 101         prior_status: Option<NodeStatus>,
 102     ) -> ControlFlow<Self::BreakVal> {
 103         // Back-edge in the CFG (loop).
 104         if let Some(NodeStatus::Visited) = prior_status {
 105             return ControlFlow::Break(NonRecursive);
 106         }
 107
 108         match self.body[bb].terminator().kind {
 109             // These terminators return control flow to the caller.
 110             TerminatorKind::Abort
 111             | TerminatorKind::GeneratorDrop
 112             | TerminatorKind::Resume
 113             | TerminatorKind::Return
 114             | TerminatorKind::Unreachable
 115             | TerminatorKind::Yield { .. } => ControlFlow::Break(NonRecursive),
 116
 117             // A diverging InlineAsm is treated as non-recursing
 118             TerminatorKind::InlineAsm { destination, .. } => {
 119                 if destination.is_some() {
 120                     ControlFlow::Continue
 121                 } else {
 122                     ControlFlow::Break(NonRecursive)
 123                 }
 124             }
 125
 126             // These do not.
 127             TerminatorKind::Assert { .. }
 128             | TerminatorKind::Call { .. }
 129             | TerminatorKind::Drop { .. }
 130             | TerminatorKind::DropAndReplace { .. }
 131             | TerminatorKind::FalseEdge { .. }
 132             | TerminatorKind::FalseUnwind { .. }
 133             | TerminatorKind::Goto { .. }
 134             | TerminatorKind::SwitchInt { .. } => ControlFlow::Continue,
 135         }
 136     }
 137
 138     fn node_settled(&mut self, bb: BasicBlock) -> ControlFlow<Self::BreakVal> {
 139         // When we examine a node for the last time, remember it if it is a recursive call.
 140         let terminator = self.body[bb].terminator();
 141         if let TerminatorKind::Call { func, .. } = &terminator.kind {
 142             if self.is_recursive_call(func) {
 143                 self.reachable_recursive_calls.push(terminator.source_info.span);
 144             }
 145         }
 146
 147         ControlFlow::Continue
 148     }
 149
 150     fn ignore_edge(&mut self, bb: BasicBlock, target: BasicBlock) -> bool {
 151         // Don't traverse successors of recursive calls or false CFG edges.
 152         match self.body[bb].terminator().kind {
 153             TerminatorKind::Call { ref func, .. } => self.is_recursive_call(func),
 154
 155             TerminatorKind::FalseUnwind { unwind: Some(imaginary_target), .. }
 156             | TerminatorKind::FalseEdge { imaginary_target, .. } => imaginary_target == target,
 157
 158             _ => false,
 159         }
 160     }
 161 }