1 use rustc_data_structures
::graph
::iterate
::{
2 NodeStatus
, TriColorDepthFirstSearch
, TriColorVisitor
,
4 use rustc_hir
::intravisit
::FnKind
;
5 use rustc_middle
::hir
::map
::blocks
::FnLikeNode
;
6 use rustc_middle
::mir
::{BasicBlock, Body, Operand, TerminatorKind}
;
7 use rustc_middle
::ty
::subst
::{GenericArg, InternalSubsts}
;
8 use rustc_middle
::ty
::{self, AssocItem, AssocItemContainer, Instance, TyCtxt}
;
9 use rustc_session
::lint
::builtin
::UNCONDITIONAL_RECURSION
;
11 use std
::ops
::ControlFlow
;
13 crate fn check
<'tcx
>(tcx
: TyCtxt
<'tcx
>, body
: &Body
<'tcx
>) {
14 let def_id
= body
.source
.def_id().expect_local();
15 let hir_id
= tcx
.hir().local_def_id_to_hir_id(def_id
);
17 if let Some(fn_like_node
) = FnLikeNode
::from_node(tcx
.hir().get(hir_id
)) {
18 if let FnKind
::Closure(_
) = fn_like_node
.kind() {
19 // closures can't recur, so they don't matter.
23 // If this is trait/impl method, extract the trait's substs.
24 let trait_substs
= match tcx
.opt_associated_item(def_id
.to_def_id()) {
26 container
: AssocItemContainer
::TraitContainer(trait_def_id
), ..
28 let trait_substs_count
= tcx
.generics_of(*trait_def_id
).count();
29 &InternalSubsts
::identity_for_item(tcx
, def_id
.to_def_id())[..trait_substs_count
]
34 let mut vis
= Search { tcx, body, reachable_recursive_calls: vec![], trait_substs }
;
35 if let Some(NonRecursive
) = TriColorDepthFirstSearch
::new(&body
).run_from_start(&mut vis
) {
39 vis
.reachable_recursive_calls
.sort();
41 let hir_id
= tcx
.hir().local_def_id_to_hir_id(def_id
);
42 let sp
= tcx
.sess
.source_map().guess_head_span(tcx
.hir().span_with_body(hir_id
));
43 tcx
.struct_span_lint_hir(UNCONDITIONAL_RECURSION
, hir_id
, sp
, |lint
| {
44 let mut db
= lint
.build("function cannot return without recursing");
45 db
.span_label(sp
, "cannot return without recursing");
46 // offer some help to the programmer.
47 for call_span
in vis
.reachable_recursive_calls
{
48 db
.span_label(call_span
, "recursive call site");
50 db
.help("a `loop` may express intention better if this is on purpose");
58 struct Search
<'mir
, 'tcx
> {
60 body
: &'mir Body
<'tcx
>,
61 trait_substs
: &'tcx
[GenericArg
<'tcx
>],
63 reachable_recursive_calls
: Vec
<Span
>,
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, trait_substs, .. }
= *self;
70 let caller
= body
.source
.def_id();
71 let param_env
= tcx
.param_env(caller
);
73 let func_ty
= func
.ty(body
, tcx
);
74 if let ty
::FnDef(callee
, substs
) = *func_ty
.kind() {
75 let normalized_substs
= tcx
.normalize_erasing_regions(param_env
, substs
);
76 let (callee
, call_substs
) = if let Ok(Some(instance
)) =
77 Instance
::resolve(tcx
, param_env
, callee
, normalized_substs
)
79 (instance
.def_id(), instance
.substs
)
81 (callee
, normalized_substs
)
84 // FIXME(#57965): Make this work across function boundaries
86 // If this is a trait fn, the substs on the trait have to match, or we might be
87 // calling into an entirely different method (for example, a call from the default
88 // method in the trait to `<A as Trait<B>>::method`, where `A` and/or `B` are
90 return callee
== caller
&& &call_substs
[..trait_substs
.len()] == trait_substs
;
97 impl<'mir
, 'tcx
> TriColorVisitor
<&'mir Body
<'tcx
>> for Search
<'mir
, 'tcx
> {
98 type BreakVal
= NonRecursive
;
103 prior_status
: Option
<NodeStatus
>,
104 ) -> ControlFlow
<Self::BreakVal
> {
105 // Back-edge in the CFG (loop).
106 if let Some(NodeStatus
::Visited
) = prior_status
{
107 return ControlFlow
::Break(NonRecursive
);
110 match self.body
[bb
].terminator().kind
{
111 // These terminators return control flow to the caller.
112 TerminatorKind
::Abort
113 | TerminatorKind
::GeneratorDrop
114 | TerminatorKind
::Resume
115 | TerminatorKind
::Return
116 | TerminatorKind
::Unreachable
117 | TerminatorKind
::Yield { .. }
=> ControlFlow
::Break(NonRecursive
),
119 // A diverging InlineAsm is treated as non-recursing
120 TerminatorKind
::InlineAsm { destination, .. }
=> {
121 if destination
.is_some() {
122 ControlFlow
::CONTINUE
124 ControlFlow
::Break(NonRecursive
)
129 TerminatorKind
::Assert { .. }
130 | TerminatorKind
::Call { .. }
131 | TerminatorKind
::Drop { .. }
132 | TerminatorKind
::DropAndReplace { .. }
133 | TerminatorKind
::FalseEdge { .. }
134 | TerminatorKind
::FalseUnwind { .. }
135 | TerminatorKind
::Goto { .. }
136 | TerminatorKind
::SwitchInt { .. }
=> ControlFlow
::CONTINUE
,
140 fn node_settled(&mut self, bb
: BasicBlock
) -> ControlFlow
<Self::BreakVal
> {
141 // When we examine a node for the last time, remember it if it is a recursive call.
142 let terminator
= self.body
[bb
].terminator();
143 if let TerminatorKind
::Call { func, .. }
= &terminator
.kind
{
144 if self.is_recursive_call(func
) {
145 self.reachable_recursive_calls
.push(terminator
.source_info
.span
);
149 ControlFlow
::CONTINUE
152 fn ignore_edge(&mut self, bb
: BasicBlock
, target
: BasicBlock
) -> bool
{
153 // Don't traverse successors of recursive calls or false CFG edges.
154 match self.body
[bb
].terminator().kind
{
155 TerminatorKind
::Call { ref func, .. }
=> self.is_recursive_call(func
),
157 TerminatorKind
::FalseUnwind { unwind: Some(imaginary_target), .. }
158 | TerminatorKind
::FalseEdge { imaginary_target, .. }
=> imaginary_target
== target
,