rustc_mir_transform/
check_call_recursion.rs

1use std::ops::ControlFlow;
2
3use rustc_attr_ir::lang_items::LangItem;
4use rustc_data_structures::graph::iterate::{
5    NodeStatus, TriColorDepthFirstSearch, TriColorVisitor,
6};
7use rustc_hir::def::DefKind;
8use rustc_lint_defs::builtin::UNCONDITIONAL_RECURSION;
9use rustc_middle::mir::{self, BasicBlock, BasicBlocks, Body, Terminator, TerminatorKind};
10use rustc_middle::ty::{self, GenericArg, GenericArgs, Instance, Ty, TyCtxt, Unnormalized};
11use rustc_span::Span;
12
13use crate::diagnostics::UnconditionalRecursion;
14use crate::pass_manager::MirLint;
15
16pub(super) struct CheckCallRecursion;
17
18impl<'tcx> MirLint<'tcx> for CheckCallRecursion {
19    fn run_lint(&self, tcx: TyCtxt<'tcx>, body: &Body<'tcx>) {
20        let def_id = body.source.def_id().expect_local();
21
22        if let DefKind::Fn | DefKind::AssocFn = tcx.def_kind(def_id) {
23            // If this is trait/impl method, extract the trait's args.
24            match tcx.trait_of_assoc(def_id.to_def_id()) {
25                Some(trait_def_id) => {
26                    let trait_args_count = tcx.generics_of(trait_def_id).count();
27                    let args = GenericArgs::identity_for_item(tcx, def_id);
28                    let trait_args = &args.as_slice()[..trait_args_count];
29                    check_recursion(tcx, body, CallRecursion { trait_args })
30                }
31                _ => check_recursion(tcx, body, CallRecursion { trait_args: &[] }),
32            };
33        }
34    }
35}
36
37/// Requires drop elaboration to have been performed.
38pub(super) struct CheckDropRecursion;
39
40impl<'tcx> MirLint<'tcx> for CheckDropRecursion {
41    fn run_lint(&self, tcx: TyCtxt<'tcx>, body: &Body<'tcx>) {
42        let def_id = body.source.def_id().expect_local();
43
44        // First check if `body` is an `fn drop()` of `Drop`
45        if let DefKind::AssocFn = tcx.def_kind(def_id)
46        && let Some(impl_id) = tcx.trait_impl_of_assoc(def_id.to_def_id())
47        && let trait_ref = tcx.impl_trait_ref(impl_id)
48        && tcx.is_lang_item(trait_ref.def_id(), LangItem::Drop)
49        // avoid erroneous `Drop` impls from causing ICEs below
50        && let sig = tcx.fn_sig(def_id).instantiate_identity().skip_norm_wip()
51        && sig.inputs().skip_binder().len() == 1
52        {
53            // It was. Now figure out for what type `Drop` is implemented and then
54            // check for recursion.
55            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_by_key(|span| span.lo_hi());
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, 'a> {
115    trait_args: &'a [GenericArg<'tcx>],
116}
117
118struct RecursiveDrop<'tcx> {
119    /// The type that `Drop` is implemented for.
120    drop_for: Ty<'tcx>,
121}
122
123impl<'tcx> TerminatorClassifier<'tcx> for CallRecursion<'tcx, '_> {
124    /// Returns `true` if `func` refers to the function we are searching in.
125    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        // Resolving function type to a specific instance that is being called is expensive. To
136        // avoid the cost we check the number of arguments first, which is sufficient to reject
137        // most of calls as non-recursive.
138        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 args = args.no_bound_vars().unwrap();
147            let Ok(normalized_args) =
148                tcx.try_normalize_erasing_regions(typing_env, Unnormalized::new_wip(args))
149            else {
150                return false;
151            };
152            let (callee, call_args) = if let Ok(Some(instance)) =
153                Instance::try_resolve(tcx, typing_env, callee, normalized_args)
154            {
155                (instance.def_id(), instance.args)
156            } else {
157                (callee, normalized_args)
158            };
159
160            // FIXME(#57965): Make this work across function boundaries
161
162            // If this is a trait fn, the args on the trait have to match, or we might be
163            // calling into an entirely different method (for example, a call from the default
164            // method in the trait to `<A as Trait<B>>::method`, where `A` and/or `B` are
165            // specific types).
166            return callee == caller
167                && &call_args.as_slice()[..self.trait_args.len()] == self.trait_args;
168        }
169
170        false
171    }
172}
173
174impl<'tcx> TerminatorClassifier<'tcx> for RecursiveDrop<'tcx> {
175    fn is_recursive_terminator(
176        &self,
177        tcx: TyCtxt<'tcx>,
178        body: &Body<'tcx>,
179        terminator: &Terminator<'tcx>,
180    ) -> bool {
181        let TerminatorKind::Drop { place, .. } = &terminator.kind else { return false };
182
183        let dropped_ty = place.ty(body, tcx).ty;
184        dropped_ty == self.drop_for
185    }
186}
187
188impl<'mir, 'tcx, C: TerminatorClassifier<'tcx>> TriColorVisitor<BasicBlocks<'tcx>>
189    for Search<'mir, 'tcx, C>
190{
191    type BreakVal = NonRecursive;
192
193    fn node_examined(
194        &mut self,
195        bb: BasicBlock,
196        prior_status: Option<NodeStatus>,
197    ) -> ControlFlow<Self::BreakVal> {
198        // Back-edge in the CFG (loop).
199        if let Some(NodeStatus::Visited) = prior_status {
200            return ControlFlow::Break(NonRecursive);
201        }
202
203        match self.body[bb].terminator().kind {
204            // These terminators return control flow to the caller.
205            TerminatorKind::UnwindTerminate(_)
206            | TerminatorKind::CoroutineDrop
207            | TerminatorKind::UnwindResume
208            | TerminatorKind::Return
209            | TerminatorKind::Unreachable
210            | TerminatorKind::Yield { .. } => ControlFlow::Break(NonRecursive),
211
212            // A InlineAsm without targets (diverging and contains no labels)
213            // is treated as non-recursing.
214            TerminatorKind::InlineAsm { ref targets, .. } => {
215                if !targets.is_empty() {
216                    ControlFlow::Continue(())
217                } else {
218                    ControlFlow::Break(NonRecursive)
219                }
220            }
221
222            // These do not.
223            TerminatorKind::Assert { .. }
224            | TerminatorKind::Call { .. }
225            | TerminatorKind::Drop { .. }
226            | TerminatorKind::FalseEdge { .. }
227            | TerminatorKind::FalseUnwind { .. }
228            | TerminatorKind::Goto { .. }
229            | TerminatorKind::SwitchInt { .. } => ControlFlow::Continue(()),
230
231            // Note that tail call terminator technically returns to the caller,
232            // but for purposes of this lint it makes sense to count it as possibly recursive,
233            // since it's still a call.
234            //
235            // If this'll be repurposed for something else, this might need to be changed.
236            TerminatorKind::TailCall { .. } => ControlFlow::Continue(()),
237        }
238    }
239
240    fn node_settled(&mut self, bb: BasicBlock) -> ControlFlow<Self::BreakVal> {
241        // When we examine a node for the last time, remember it if it is a recursive call.
242        let terminator = self.body[bb].terminator();
243
244        // FIXME(explicit_tail_calls): highlight tail calls as "recursive call site"
245        //
246        // We don't want to lint functions that recurse only through tail calls
247        // (such as `fn g() { become () }`), so just adding `| TailCall { ... }`
248        // here won't work.
249        //
250        // But at the same time we would like to highlight both calls in a function like
251        // `fn f() { if false { become f() } else { f() } }`, so we need to figure something out.
252        if self.classifier.is_recursive_terminator(self.tcx, self.body, terminator) {
253            self.reachable_recursive_calls.push(terminator.source_info.span);
254        }
255
256        ControlFlow::Continue(())
257    }
258
259    fn ignore_edge(&mut self, bb: BasicBlock, target: BasicBlock) -> bool {
260        let terminator = self.body[bb].terminator();
261        let ignore_unwind = terminator.unwind() == Some(&mir::UnwindAction::Cleanup(target))
262            && terminator.successors().count() > 1;
263        if ignore_unwind || self.classifier.is_recursive_terminator(self.tcx, self.body, terminator)
264        {
265            return true;
266        }
267        match &terminator.kind {
268            TerminatorKind::FalseEdge { imaginary_target, .. } => imaginary_target == &target,
269            _ => false,
270        }
271    }
272}
rustc_mir_transform/check_call_recursion.rs

rustc_mir_transform/
check_call_recursion.rs
