compiler/rustc_mir_build/src/lints.rs

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