1use std::ops::ControlFlow;
2
3use rustc_data_structures::graph::iterate::{
4 NodeStatus, TriColorDepthFirstSearch, TriColorVisitor,
5};
6use rustc_hir::def::DefKind;
7use rustc_middle::mir::{self, BasicBlock, BasicBlocks, Body, Terminator, TerminatorKind};
8use rustc_middle::ty::{self, GenericArg, GenericArgs, Instance, Ty, TyCtxt};
9use rustc_session::lint::builtin::UNCONDITIONAL_RECURSION;
10use rustc_span::Span;
11
12use crate::errors::UnconditionalRecursion;
13use crate::pass_manager::MirLint;
14
15pub(super) struct CheckCallRecursion;
16
17impl<'tcx> MirLint<'tcx> for CheckCallRecursion {
18 fn run_lint(&self, tcx: TyCtxt<'tcx>, body: &Body<'tcx>) {
19 let def_id = body.source.def_id().expect_local();
20
21 if let DefKind::Fn | DefKind::AssocFn = tcx.def_kind(def_id) {
22 let trait_args = match tcx.trait_of_item(def_id.to_def_id()) {
24 Some(trait_def_id) => {
25 let trait_args_count = tcx.generics_of(trait_def_id).count();
26 &GenericArgs::identity_for_item(tcx, def_id)[..trait_args_count]
27 }
28 _ => &[],
29 };
30
31 check_recursion(tcx, body, CallRecursion { trait_args })
32 }
33 }
34}
35
36pub(super) struct CheckDropRecursion;
38
39impl<'tcx> MirLint<'tcx> for CheckDropRecursion {
40 fn run_lint(&self, tcx: TyCtxt<'tcx>, body: &Body<'tcx>) {
41 let def_id = body.source.def_id().expect_local();
42
43 if let DefKind::AssocFn = tcx.def_kind(def_id)
45 && let Some(trait_ref) =
46 tcx.impl_of_method(def_id.to_def_id()).and_then(|def_id| tcx.impl_trait_ref(def_id))
47 && let Some(drop_trait) = tcx.lang_items().drop_trait()
48 && drop_trait == trait_ref.instantiate_identity().def_id
49 && let sig = tcx.fn_sig(def_id).instantiate_identity()
51 && sig.inputs().skip_binder().len() == 1
52 {
53 if let ty::Ref(_, dropped_ty, _) =
56 tcx.liberate_late_bound_regions(def_id.to_def_id(), sig.input(0)).kind()
57 {
58 check_recursion(tcx, body, RecursiveDrop { drop_for: *dropped_ty });
59 }
60 }
61 }
62}
63
64fn check_recursion<'tcx>(
65 tcx: TyCtxt<'tcx>,
66 body: &Body<'tcx>,
67 classifier: impl TerminatorClassifier<'tcx>,
68) {
69 let def_id = body.source.def_id().expect_local();
70
71 if let DefKind::Fn | DefKind::AssocFn = tcx.def_kind(def_id) {
72 let mut vis = Search { tcx, body, classifier, reachable_recursive_calls: vec![] };
73 if let Some(NonRecursive) =
74 TriColorDepthFirstSearch::new(&body.basic_blocks).run_from_start(&mut vis)
75 {
76 return;
77 }
78 if vis.reachable_recursive_calls.is_empty() {
79 return;
80 }
81
82 vis.reachable_recursive_calls.sort();
83
84 let sp = tcx.def_span(def_id);
85 let hir_id = tcx.local_def_id_to_hir_id(def_id);
86 tcx.emit_node_span_lint(
87 UNCONDITIONAL_RECURSION,
88 hir_id,
89 sp,
90 UnconditionalRecursion { span: sp, call_sites: vis.reachable_recursive_calls },
91 );
92 }
93}
94
95trait TerminatorClassifier<'tcx> {
96 fn is_recursive_terminator(
97 &self,
98 tcx: TyCtxt<'tcx>,
99 body: &Body<'tcx>,
100 terminator: &Terminator<'tcx>,
101 ) -> bool;
102}
103
104struct NonRecursive;
105
106struct Search<'mir, 'tcx, C: TerminatorClassifier<'tcx>> {
107 tcx: TyCtxt<'tcx>,
108 body: &'mir Body<'tcx>,
109 classifier: C,
110
111 reachable_recursive_calls: Vec<Span>,
112}
113
114struct CallRecursion<'tcx> {
115 trait_args: &'tcx [GenericArg<'tcx>],
116}
117
118struct RecursiveDrop<'tcx> {
119 drop_for: Ty<'tcx>,
121}
122
123impl<'tcx> TerminatorClassifier<'tcx> for CallRecursion<'tcx> {
124 fn is_recursive_terminator(
126 &self,
127 tcx: TyCtxt<'tcx>,
128 body: &Body<'tcx>,
129 terminator: &Terminator<'tcx>,
130 ) -> bool {
131 let TerminatorKind::Call { func, args, .. } = &terminator.kind else {
132 return false;
133 };
134
135 if args.len() != body.arg_count {
139 return false;
140 }
141 let caller = body.source.def_id();
142 let typing_env = body.typing_env(tcx);
143
144 let func_ty = func.ty(body, tcx);
145 if let ty::FnDef(callee, args) = *func_ty.kind() {
146 let Ok(normalized_args) = tcx.try_normalize_erasing_regions(typing_env, args) else {
147 return false;
148 };
149 let (callee, call_args) = if let Ok(Some(instance)) =
150 Instance::try_resolve(tcx, typing_env, callee, normalized_args)
151 {
152 (instance.def_id(), instance.args)
153 } else {
154 (callee, normalized_args)
155 };
156
157 return callee == caller && &call_args[..self.trait_args.len()] == self.trait_args;
164 }
165
166 false
167 }
168}
169
170impl<'tcx> TerminatorClassifier<'tcx> for RecursiveDrop<'tcx> {
171 fn is_recursive_terminator(
172 &self,
173 tcx: TyCtxt<'tcx>,
174 body: &Body<'tcx>,
175 terminator: &Terminator<'tcx>,
176 ) -> bool {
177 let TerminatorKind::Drop { place, .. } = &terminator.kind else { return false };
178
179 let dropped_ty = place.ty(body, tcx).ty;
180 dropped_ty == self.drop_for
181 }
182}
183
184impl<'mir, 'tcx, C: TerminatorClassifier<'tcx>> TriColorVisitor<BasicBlocks<'tcx>>
185 for Search<'mir, 'tcx, C>
186{
187 type BreakVal = NonRecursive;
188
189 fn node_examined(
190 &mut self,
191 bb: BasicBlock,
192 prior_status: Option<NodeStatus>,
193 ) -> ControlFlow<Self::BreakVal> {
194 if let Some(NodeStatus::Visited) = prior_status {
196 return ControlFlow::Break(NonRecursive);
197 }
198
199 match self.body[bb].terminator().kind {
200 TerminatorKind::UnwindTerminate(_)
202 | TerminatorKind::CoroutineDrop
203 | TerminatorKind::UnwindResume
204 | TerminatorKind::Return
205 | TerminatorKind::Unreachable
206 | TerminatorKind::Yield { .. } => ControlFlow::Break(NonRecursive),
207
208 TerminatorKind::InlineAsm { ref targets, .. } => {
211 if !targets.is_empty() {
212 ControlFlow::Continue(())
213 } else {
214 ControlFlow::Break(NonRecursive)
215 }
216 }
217
218 TerminatorKind::Assert { .. }
220 | TerminatorKind::Call { .. }
221 | TerminatorKind::Drop { .. }
222 | TerminatorKind::FalseEdge { .. }
223 | TerminatorKind::FalseUnwind { .. }
224 | TerminatorKind::Goto { .. }
225 | TerminatorKind::SwitchInt { .. } => ControlFlow::Continue(()),
226
227 TerminatorKind::TailCall { .. } => ControlFlow::Continue(()),
233 }
234 }
235
236 fn node_settled(&mut self, bb: BasicBlock) -> ControlFlow<Self::BreakVal> {
237 let terminator = self.body[bb].terminator();
239
240 if self.classifier.is_recursive_terminator(self.tcx, self.body, terminator) {
249 self.reachable_recursive_calls.push(terminator.source_info.span);
250 }
251
252 ControlFlow::Continue(())
253 }
254
255 fn ignore_edge(&mut self, bb: BasicBlock, target: BasicBlock) -> bool {
256 let terminator = self.body[bb].terminator();
257 let ignore_unwind = terminator.unwind() == Some(&mir::UnwindAction::Cleanup(target))
258 && terminator.successors().count() > 1;
259 if ignore_unwind || self.classifier.is_recursive_terminator(self.tcx, self.body, terminator)
260 {
261 return true;
262 }
263 match &terminator.kind {
264 TerminatorKind::FalseEdge { imaginary_target, .. } => imaginary_target == &target,
265 _ => false,
266 }
267 }
268}