1 use crate::errors
::UnconditionalRecursion
;
2 use rustc_data_structures
::graph
::iterate
::{
3 NodeStatus
, TriColorDepthFirstSearch
, TriColorVisitor
,
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
;
11 use std
::ops
::ControlFlow
;
13 pub(crate) fn check
<'tcx
>(tcx
: TyCtxt
<'tcx
>, body
: &Body
<'tcx
>) {
14 let def_id
= body
.source
.def_id().expect_local();
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
]
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
)
32 if vis
.reachable_recursive_calls
.is_empty() {
36 vis
.reachable_recursive_calls
.sort();
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
,
44 UnconditionalRecursion { span: sp, call_sites: vis.reachable_recursive_calls }
,
51 struct Search
<'mir
, 'tcx
> {
53 body
: &'mir Body
<'tcx
>,
54 trait_substs
: &'tcx
[GenericArg
<'tcx
>],
56 reachable_recursive_calls
: Vec
<Span
>,
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
{
69 let caller
= body
.source
.def_id();
70 let param_env
= tcx
.param_env(caller
);
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
)
78 (instance
.def_id(), instance
.substs
)
80 (callee
, normalized_substs
)
83 // FIXME(#57965): Make this work across function boundaries
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
89 return callee
== caller
&& &call_substs
[..trait_substs
.len()] == trait_substs
;
96 impl<'mir
, 'tcx
> TriColorVisitor
<BasicBlocks
<'tcx
>> for Search
<'mir
, 'tcx
> {
97 type BreakVal
= NonRecursive
;
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
);
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
),
118 // A diverging InlineAsm is treated as non-recursing
119 TerminatorKind
::InlineAsm { destination, .. }
=> {
120 if destination
.is_some() {
121 ControlFlow
::Continue(())
123 ControlFlow
::Break(NonRecursive
)
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(()),
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
);
148 ControlFlow
::Continue(())
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 {
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
,