]>
Commit | Line | Data |
---|---|---|
ba9703b0 | 1 | use rustc_data_structures::graph::iterate::{ |
2a314972 | 2 | NodeStatus, TriColorDepthFirstSearch, TriColorVisitor, |
ba9703b0 | 3 | }; |
dfeec247 | 4 | use rustc_hir::intravisit::FnKind; |
ba9703b0 XL |
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; | |
10 | use rustc_span::Span; | |
2a314972 | 11 | use std::ops::ControlFlow; |
0bf4aa26 | 12 | |
29967ef6 XL |
13 | crate fn check<'tcx>(tcx: TyCtxt<'tcx>, body: &Body<'tcx>) { |
14 | let def_id = body.source.def_id().expect_local(); | |
3dfed10e | 15 | let hir_id = tcx.hir().local_def_id_to_hir_id(def_id); |
0bf4aa26 | 16 | |
dc9dc135 | 17 | if let Some(fn_like_node) = FnLikeNode::from_node(tcx.hir().get(hir_id)) { |
6a06907d | 18 | if let FnKind::Closure = fn_like_node.kind() { |
ba9703b0 XL |
19 | // closures can't recur, so they don't matter. |
20 | return; | |
0bf4aa26 XL |
21 | } |
22 | ||
ba9703b0 | 23 | // If this is trait/impl method, extract the trait's substs. |
f9f354fc | 24 | let trait_substs = match tcx.opt_associated_item(def_id.to_def_id()) { |
ba9703b0 XL |
25 | Some(AssocItem { |
26 | container: AssocItemContainer::TraitContainer(trait_def_id), .. | |
27 | }) => { | |
f9f354fc XL |
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] | |
0bf4aa26 | 30 | } |
ba9703b0 XL |
31 | _ => &[], |
32 | }; | |
0bf4aa26 | 33 | |
29967ef6 | 34 | let mut vis = Search { tcx, body, reachable_recursive_calls: vec![], trait_substs }; |
ba9703b0 XL |
35 | if let Some(NonRecursive) = TriColorDepthFirstSearch::new(&body).run_from_start(&mut vis) { |
36 | return; | |
0bf4aa26 | 37 | } |
0bf4aa26 | 38 | |
ba9703b0 XL |
39 | vis.reachable_recursive_calls.sort(); |
40 | ||
3dfed10e XL |
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)); | |
74b04a01 XL |
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. | |
ba9703b0 XL |
47 | for call_span in vis.reachable_recursive_calls { |
48 | db.span_label(call_span, "recursive call site"); | |
74b04a01 XL |
49 | } |
50 | db.help("a `loop` may express intention better if this is on purpose"); | |
51 | db.emit(); | |
52 | }); | |
0bf4aa26 XL |
53 | } |
54 | } | |
ba9703b0 XL |
55 | |
56 | struct NonRecursive; | |
57 | ||
58 | struct Search<'mir, 'tcx> { | |
59 | tcx: TyCtxt<'tcx>, | |
60 | body: &'mir Body<'tcx>, | |
ba9703b0 XL |
61 | trait_substs: &'tcx [GenericArg<'tcx>], |
62 | ||
63 | reachable_recursive_calls: Vec<Span>, | |
64 | } | |
65 | ||
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 { | |
29967ef6 XL |
69 | let Search { tcx, body, trait_substs, .. } = *self; |
70 | let caller = body.source.def_id(); | |
71 | let param_env = tcx.param_env(caller); | |
ba9703b0 XL |
72 | |
73 | let func_ty = func.ty(body, tcx); | |
29967ef6 XL |
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) | |
78 | { | |
79 | (instance.def_id(), instance.substs) | |
80 | } else { | |
81 | (callee, normalized_substs) | |
82 | }; | |
ba9703b0 XL |
83 | |
84 | // FIXME(#57965): Make this work across function boundaries | |
85 | ||
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 | |
89 | // specific types). | |
29967ef6 | 90 | return callee == caller && &call_substs[..trait_substs.len()] == trait_substs; |
ba9703b0 XL |
91 | } |
92 | ||
93 | false | |
94 | } | |
95 | } | |
96 | ||
97 | impl<'mir, 'tcx> TriColorVisitor<&'mir Body<'tcx>> for Search<'mir, 'tcx> { | |
98 | type BreakVal = NonRecursive; | |
99 | ||
100 | fn node_examined( | |
101 | &mut self, | |
102 | bb: BasicBlock, | |
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); | |
108 | } | |
109 | ||
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), | |
118 | ||
f9f354fc XL |
119 | // A diverging InlineAsm is treated as non-recursing |
120 | TerminatorKind::InlineAsm { destination, .. } => { | |
121 | if destination.is_some() { | |
1b1a35ee | 122 | ControlFlow::CONTINUE |
f9f354fc XL |
123 | } else { |
124 | ControlFlow::Break(NonRecursive) | |
125 | } | |
126 | } | |
127 | ||
ba9703b0 XL |
128 | // These do not. |
129 | TerminatorKind::Assert { .. } | |
130 | | TerminatorKind::Call { .. } | |
131 | | TerminatorKind::Drop { .. } | |
132 | | TerminatorKind::DropAndReplace { .. } | |
f035d41b | 133 | | TerminatorKind::FalseEdge { .. } |
ba9703b0 XL |
134 | | TerminatorKind::FalseUnwind { .. } |
135 | | TerminatorKind::Goto { .. } | |
1b1a35ee | 136 | | TerminatorKind::SwitchInt { .. } => ControlFlow::CONTINUE, |
ba9703b0 XL |
137 | } |
138 | } | |
139 | ||
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); | |
146 | } | |
147 | } | |
148 | ||
1b1a35ee | 149 | ControlFlow::CONTINUE |
ba9703b0 XL |
150 | } |
151 | ||
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), | |
156 | ||
157 | TerminatorKind::FalseUnwind { unwind: Some(imaginary_target), .. } | |
f035d41b | 158 | | TerminatorKind::FalseEdge { imaginary_target, .. } => imaginary_target == target, |
ba9703b0 XL |
159 | |
160 | _ => false, | |
161 | } | |
162 | } | |
163 | } |