compiler/rustc_mir_build/src/lints.rs

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