1 use rustc_data_structures
::graph
::iterate
::{
2 NodeStatus
, TriColorDepthFirstSearch
, TriColorVisitor
,
4 use rustc_hir
::intravisit
::FnKind
;
5 use rustc_middle
::mir
::{BasicBlock, 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
;
10 use std
::ops
::ControlFlow
;
12 pub(crate) fn check
<'tcx
>(tcx
: TyCtxt
<'tcx
>, body
: &Body
<'tcx
>) {
13 let def_id
= body
.source
.def_id().expect_local();
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.
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()) {
24 container
: AssocItemContainer
::TraitContainer(trait_def_id
), ..
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
]
32 let mut vis
= Search { tcx, body, reachable_recursive_calls: vec![], trait_substs }
;
33 if let Some(NonRecursive
) = TriColorDepthFirstSearch
::new(&body
).run_from_start(&mut vis
) {
36 if vis
.reachable_recursive_calls
.is_empty() {
40 vis
.reachable_recursive_calls
.sort();
42 let hir_id
= tcx
.hir().local_def_id_to_hir_id(def_id
);
43 let sp
= tcx
.sess
.source_map().guess_head_span(tcx
.hir().span_with_body(hir_id
));
44 tcx
.struct_span_lint_hir(UNCONDITIONAL_RECURSION
, hir_id
, sp
, |lint
| {
45 let mut db
= lint
.build("function cannot return without recursing");
46 db
.span_label(sp
, "cannot return without recursing");
47 // offer some help to the programmer.
48 for call_span
in vis
.reachable_recursive_calls
{
49 db
.span_label(call_span
, "recursive call site");
51 db
.help("a `loop` may express intention better if this is on purpose");
59 struct Search
<'mir
, 'tcx
> {
61 body
: &'mir Body
<'tcx
>,
62 trait_substs
: &'tcx
[GenericArg
<'tcx
>],
64 reachable_recursive_calls
: Vec
<Span
>,
67 impl<'mir
, 'tcx
> Search
<'mir
, 'tcx
> {
68 /// Returns `true` if `func` refers to the function we are searching in.
69 fn is_recursive_call(&self, func
: &Operand
<'tcx
>, args
: &[Operand
<'tcx
>]) -> bool
{
70 let Search { tcx, body, trait_substs, .. }
= *self;
71 // Resolving function type to a specific instance that is being called is expensive. To
72 // avoid the cost we check the number of arguments first, which is sufficient to reject
73 // most of calls as non-recursive.
74 if args
.len() != body
.arg_count
{
77 let caller
= body
.source
.def_id();
78 let param_env
= tcx
.param_env(caller
);
80 let func_ty
= func
.ty(body
, tcx
);
81 if let ty
::FnDef(callee
, substs
) = *func_ty
.kind() {
82 let normalized_substs
= tcx
.normalize_erasing_regions(param_env
, substs
);
83 let (callee
, call_substs
) = if let Ok(Some(instance
)) =
84 Instance
::resolve(tcx
, param_env
, callee
, normalized_substs
)
86 (instance
.def_id(), instance
.substs
)
88 (callee
, normalized_substs
)
91 // FIXME(#57965): Make this work across function boundaries
93 // If this is a trait fn, the substs on the trait have to match, or we might be
94 // calling into an entirely different method (for example, a call from the default
95 // method in the trait to `<A as Trait<B>>::method`, where `A` and/or `B` are
97 return callee
== caller
&& &call_substs
[..trait_substs
.len()] == trait_substs
;
104 impl<'mir
, 'tcx
> TriColorVisitor
<&'mir Body
<'tcx
>> for Search
<'mir
, 'tcx
> {
105 type BreakVal
= NonRecursive
;
110 prior_status
: Option
<NodeStatus
>,
111 ) -> ControlFlow
<Self::BreakVal
> {
112 // Back-edge in the CFG (loop).
113 if let Some(NodeStatus
::Visited
) = prior_status
{
114 return ControlFlow
::Break(NonRecursive
);
117 match self.body
[bb
].terminator().kind
{
118 // These terminators return control flow to the caller.
119 TerminatorKind
::Abort
120 | TerminatorKind
::GeneratorDrop
121 | TerminatorKind
::Resume
122 | TerminatorKind
::Return
123 | TerminatorKind
::Unreachable
124 | TerminatorKind
::Yield { .. }
=> ControlFlow
::Break(NonRecursive
),
126 // A diverging InlineAsm is treated as non-recursing
127 TerminatorKind
::InlineAsm { destination, .. }
=> {
128 if destination
.is_some() {
129 ControlFlow
::CONTINUE
131 ControlFlow
::Break(NonRecursive
)
136 TerminatorKind
::Assert { .. }
137 | TerminatorKind
::Call { .. }
138 | TerminatorKind
::Drop { .. }
139 | TerminatorKind
::DropAndReplace { .. }
140 | TerminatorKind
::FalseEdge { .. }
141 | TerminatorKind
::FalseUnwind { .. }
142 | TerminatorKind
::Goto { .. }
143 | TerminatorKind
::SwitchInt { .. }
=> ControlFlow
::CONTINUE
,
147 fn node_settled(&mut self, bb
: BasicBlock
) -> ControlFlow
<Self::BreakVal
> {
148 // When we examine a node for the last time, remember it if it is a recursive call.
149 let terminator
= self.body
[bb
].terminator();
150 if let TerminatorKind
::Call { func, args, .. }
= &terminator
.kind
{
151 if self.is_recursive_call(func
, args
) {
152 self.reachable_recursive_calls
.push(terminator
.source_info
.span
);
156 ControlFlow
::CONTINUE
159 fn ignore_edge(&mut self, bb
: BasicBlock
, target
: BasicBlock
) -> bool
{
160 let terminator
= self.body
[bb
].terminator();
161 if terminator
.unwind() == Some(&Some(target
)) && terminator
.successors().count() > 1 {
164 // Don't traverse successors of recursive calls or false CFG edges.
165 match self.body
[bb
].terminator().kind
{
166 TerminatorKind
::Call { ref func, ref args, .. }
=> self.is_recursive_call(func
, args
),
167 TerminatorKind
::FalseEdge { imaginary_target, .. }
=> imaginary_target
== target
,