]>
Commit | Line | Data |
---|---|---|
9c376795 | 1 | use crate::errors::UnconditionalRecursion; |
ba9703b0 | 2 | use rustc_data_structures::graph::iterate::{ |
2a314972 | 3 | NodeStatus, TriColorDepthFirstSearch, TriColorVisitor, |
ba9703b0 | 4 | }; |
064997fb FG |
5 | use rustc_hir::def::DefKind; |
6 | use rustc_middle::mir::{BasicBlock, BasicBlocks, Body, Operand, TerminatorKind}; | |
ba9703b0 | 7 | use rustc_middle::ty::subst::{GenericArg, InternalSubsts}; |
064997fb | 8 | use rustc_middle::ty::{self, Instance, TyCtxt}; |
ba9703b0 XL |
9 | use rustc_session::lint::builtin::UNCONDITIONAL_RECURSION; |
10 | use rustc_span::Span; | |
2a314972 | 11 | use std::ops::ControlFlow; |
0bf4aa26 | 12 | |
923072b8 | 13 | pub(crate) fn check<'tcx>(tcx: TyCtxt<'tcx>, body: &Body<'tcx>) { |
29967ef6 | 14 | let def_id = body.source.def_id().expect_local(); |
0bf4aa26 | 15 | |
064997fb | 16 | if let DefKind::Fn | DefKind::AssocFn = tcx.def_kind(def_id) { |
ba9703b0 | 17 | // If this is trait/impl method, extract the trait's substs. |
064997fb FG |
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(); | |
f9f354fc | 21 | &InternalSubsts::identity_for_item(tcx, def_id.to_def_id())[..trait_substs_count] |
0bf4aa26 | 22 | } |
ba9703b0 XL |
23 | _ => &[], |
24 | }; | |
0bf4aa26 | 25 | |
29967ef6 | 26 | let mut vis = Search { tcx, body, reachable_recursive_calls: vec![], trait_substs }; |
064997fb FG |
27 | if let Some(NonRecursive) = |
28 | TriColorDepthFirstSearch::new(&body.basic_blocks).run_from_start(&mut vis) | |
29 | { | |
ba9703b0 | 30 | return; |
0bf4aa26 | 31 | } |
5099ac24 FG |
32 | if vis.reachable_recursive_calls.is_empty() { |
33 | return; | |
34 | } | |
0bf4aa26 | 35 | |
ba9703b0 XL |
36 | vis.reachable_recursive_calls.sort(); |
37 | ||
064997fb | 38 | let sp = tcx.def_span(def_id); |
3dfed10e | 39 | let hir_id = tcx.hir().local_def_id_to_hir_id(def_id); |
9c376795 | 40 | tcx.emit_spanned_lint( |
2b03887a FG |
41 | UNCONDITIONAL_RECURSION, |
42 | hir_id, | |
43 | sp, | |
9c376795 | 44 | UnconditionalRecursion { span: sp, call_sites: vis.reachable_recursive_calls }, |
2b03887a | 45 | ); |
0bf4aa26 XL |
46 | } |
47 | } | |
ba9703b0 XL |
48 | |
49 | struct NonRecursive; | |
50 | ||
51 | struct Search<'mir, 'tcx> { | |
52 | tcx: TyCtxt<'tcx>, | |
53 | body: &'mir Body<'tcx>, | |
ba9703b0 XL |
54 | trait_substs: &'tcx [GenericArg<'tcx>], |
55 | ||
56 | reachable_recursive_calls: Vec<Span>, | |
57 | } | |
58 | ||
59 | impl<'mir, 'tcx> Search<'mir, 'tcx> { | |
60 | /// Returns `true` if `func` refers to the function we are searching in. | |
5099ac24 | 61 | fn is_recursive_call(&self, func: &Operand<'tcx>, args: &[Operand<'tcx>]) -> bool { |
29967ef6 | 62 | let Search { tcx, body, trait_substs, .. } = *self; |
9c376795 | 63 | // Resolving function type to a specific instance that is being called is expensive. To |
5099ac24 FG |
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 { | |
67 | return false; | |
68 | } | |
29967ef6 XL |
69 | let caller = body.source.def_id(); |
70 | let param_env = tcx.param_env(caller); | |
ba9703b0 XL |
71 | |
72 | let func_ty = func.ty(body, tcx); | |
29967ef6 XL |
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) | |
77 | { | |
78 | (instance.def_id(), instance.substs) | |
79 | } else { | |
80 | (callee, normalized_substs) | |
81 | }; | |
ba9703b0 XL |
82 | |
83 | // FIXME(#57965): Make this work across function boundaries | |
84 | ||
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 | |
88 | // specific types). | |
29967ef6 | 89 | return callee == caller && &call_substs[..trait_substs.len()] == trait_substs; |
ba9703b0 XL |
90 | } |
91 | ||
92 | false | |
93 | } | |
94 | } | |
95 | ||
064997fb | 96 | impl<'mir, 'tcx> TriColorVisitor<BasicBlocks<'tcx>> for Search<'mir, 'tcx> { |
ba9703b0 XL |
97 | type BreakVal = NonRecursive; |
98 | ||
99 | fn node_examined( | |
100 | &mut self, | |
101 | bb: BasicBlock, | |
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); | |
107 | } | |
108 | ||
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), | |
117 | ||
f9f354fc XL |
118 | // A diverging InlineAsm is treated as non-recursing |
119 | TerminatorKind::InlineAsm { destination, .. } => { | |
120 | if destination.is_some() { | |
9c376795 | 121 | ControlFlow::Continue(()) |
f9f354fc XL |
122 | } else { |
123 | ControlFlow::Break(NonRecursive) | |
124 | } | |
125 | } | |
126 | ||
ba9703b0 XL |
127 | // These do not. |
128 | TerminatorKind::Assert { .. } | |
129 | | TerminatorKind::Call { .. } | |
130 | | TerminatorKind::Drop { .. } | |
131 | | TerminatorKind::DropAndReplace { .. } | |
f035d41b | 132 | | TerminatorKind::FalseEdge { .. } |
ba9703b0 XL |
133 | | TerminatorKind::FalseUnwind { .. } |
134 | | TerminatorKind::Goto { .. } | |
9c376795 | 135 | | TerminatorKind::SwitchInt { .. } => ControlFlow::Continue(()), |
ba9703b0 XL |
136 | } |
137 | } | |
138 | ||
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(); | |
5099ac24 FG |
142 | if let TerminatorKind::Call { func, args, .. } = &terminator.kind { |
143 | if self.is_recursive_call(func, args) { | |
ba9703b0 XL |
144 | self.reachable_recursive_calls.push(terminator.source_info.span); |
145 | } | |
146 | } | |
147 | ||
9c376795 | 148 | ControlFlow::Continue(()) |
ba9703b0 XL |
149 | } |
150 | ||
151 | fn ignore_edge(&mut self, bb: BasicBlock, target: BasicBlock) -> bool { | |
5099ac24 FG |
152 | let terminator = self.body[bb].terminator(); |
153 | if terminator.unwind() == Some(&Some(target)) && terminator.successors().count() > 1 { | |
154 | return true; | |
155 | } | |
ba9703b0 XL |
156 | // Don't traverse successors of recursive calls or false CFG edges. |
157 | match self.body[bb].terminator().kind { | |
5099ac24 FG |
158 | TerminatorKind::Call { ref func, ref args, .. } => self.is_recursive_call(func, args), |
159 | TerminatorKind::FalseEdge { imaginary_target, .. } => imaginary_target == target, | |
ba9703b0 XL |
160 | _ => false, |
161 | } | |
162 | } | |
163 | } |