1use std::collections::{HashMap, HashSet, VecDeque};
4
5use rustc_hir::def_id::DefId;
6use rustc_middle::{
7 mir::{
8 BasicBlock, Body, Local, NonDivergingIntrinsic, Operand, ProjectionElem, Rvalue,
9 StatementKind, TerminatorKind,
10 },
11 ty::{EarlyBinder, InstanceKind, TyCtxt, TypingEnv},
12};
13
14use crate::analysis::path::graph::{PathEnumerator, PathGraph};
15use crate::compat::Spanned;
16use crate::util::mir_utils as helpers;
17
18pub(crate) trait WriteSemantics {
20 fn traces_base_pointer<'tcx>(
21 &self,
22 tcx: TyCtxt<'tcx>,
23 caller: DefId,
24 func: &Operand<'tcx>,
25 ) -> bool;
26 fn direct_write_arg(&self, tcx: TyCtxt<'_>, func: &Operand<'_>) -> Option<usize>;
27 fn special_write_args<'tcx>(
28 &self,
29 tcx: TyCtxt<'tcx>,
30 caller: DefId,
31 func: &Operand<'tcx>,
32 args: &[Spanned<Operand<'tcx>>],
33 body: &Body<'tcx>,
34 ) -> Option<Vec<usize>>;
35 fn skip_mir_write(&self, tcx: TyCtxt<'_>, callee: DefId) -> bool;
36}
37
38type WriteMemo = HashMap<(DefId, usize), Option<HashSet<usize>>>;
40
41fn trace_to_callee_args<'tcx>(
47 semantics: &impl WriteSemantics,
48 tcx: TyCtxt<'tcx>,
49 caller: DefId,
50 body: &Body<'tcx>,
51 operand: &Operand<'tcx>,
52) -> HashSet<usize> {
53 match operand {
54 Operand::Copy(place) | Operand::Move(place) => {
55 trace_local_to_callee_args(semantics, tcx, caller, body, place.local)
56 }
57 _ => HashSet::new(),
58 }
59}
60
61fn trace_local_to_callee_args<'tcx>(
62 semantics: &impl WriteSemantics,
63 tcx: TyCtxt<'tcx>,
64 caller: DefId,
65 body: &Body<'tcx>,
66 local: Local,
67) -> HashSet<usize> {
68 let mut queue = VecDeque::from([local]);
69 let mut seen = HashSet::from([local]);
70 let mut outer_args = HashSet::new();
71 while let Some(current) = queue.pop_front() {
72 let cidx = current.as_usize();
73 if cidx >= 1 && cidx <= body.arg_count {
74 outer_args.insert(cidx - 1);
75 continue;
76 }
77 for bb in body.basic_blocks.iter() {
78 for stmt in &bb.statements {
79 let StatementKind::Assign(assign) = &stmt.kind else {
80 continue;
81 };
82 let dest = assign.0.local;
83 if dest != current {
84 continue;
85 }
86 let sources: Vec<_> = match &assign.1 {
87 Rvalue::Use(Operand::Copy(place), ..)
88 | Rvalue::Use(Operand::Move(place), ..)
89 | Rvalue::Cast(_, Operand::Copy(place), _)
90 | Rvalue::Cast(_, Operand::Move(place), _)
91 | Rvalue::Ref(_, _, place)
92 | Rvalue::RawPtr(_, place)
93 | Rvalue::CopyForDeref(place) => vec![place.local],
94 Rvalue::Aggregate(_, operands) => operands
95 .iter()
96 .filter_map(|operand| match operand {
97 Operand::Copy(place) | Operand::Move(place) => Some(place.local),
98 _ => None,
99 })
100 .collect(),
101 _ => Vec::new(),
102 };
103 for source in sources {
104 if seen.insert(source) {
105 queue.push_back(source);
106 }
107 }
108 }
109 let Some(terminator) = &bb.terminator else {
110 continue;
111 };
112 let (func, args, destination) = match &terminator.kind {
113 TerminatorKind::Call {
114 func,
115 args,
116 destination,
117 ..
118 } => (func, args, destination.local),
119 TerminatorKind::TailCall { func, args, .. } => (func, args, Local::from_usize(0)),
120 _ => continue,
121 };
122 if destination != current {
123 continue;
124 }
125 if !semantics.traces_base_pointer(tcx, caller, func) {
131 continue;
132 }
133 let Some(source) = args.first().and_then(|arg| match &arg.node {
134 Operand::Copy(place) | Operand::Move(place) => Some(place.local),
135 Operand::Constant(_) => None,
136 Operand::RuntimeChecks(_) => None,
137 }) else {
138 continue;
139 };
140 if !seen.contains(&source) {
141 seen.insert(source);
142 queue.push_back(source);
143 }
144 }
145 }
146 outer_args
147}
148
149pub(crate) fn callsite_write_args<'tcx>(
152 semantics: &impl WriteSemantics,
153 tcx: TyCtxt<'tcx>,
154 caller: DefId,
155 func: &Operand<'tcx>,
156) -> Option<Vec<usize>> {
157 callsite_write_args_rec(semantics, tcx, caller, func, 0, &mut HashMap::new())
158 .map(|set| set.into_iter().collect())
159}
160
161fn callsite_write_args_rec<'tcx>(
162 semantics: &impl WriteSemantics,
163 tcx: TyCtxt<'tcx>,
164 caller: DefId,
165 func: &Operand<'tcx>,
166 depth: usize,
167 memo: &mut WriteMemo,
168) -> Option<HashSet<usize>> {
169 if depth > 4 {
170 return None;
171 }
172 let base = helpers::dep_callee_def_id(func)?;
173 let is_trait_method = tcx
174 .opt_associated_item(base)
175 .and_then(|item| item.trait_container(tcx))
176 .is_some();
177 if !is_trait_method && !tcx.generics_of(base).requires_monomorphization(tcx) {
178 return write_args_rec(semantics, tcx, base, depth, memo);
179 }
180 let Some(instance) = helpers::resolve_callee_instance(tcx, caller, func) else {
181 return (!is_trait_method)
182 .then(|| write_args_rec(semantics, tcx, base, depth, memo))
183 .flatten();
184 };
185 if !matches!(instance.def, InstanceKind::Item(_)) || !tcx.is_mir_available(instance.def_id()) {
186 return None;
187 }
188 let callee = instance.def_id();
189 let mir = tcx.optimized_mir(callee);
190 let body = instance
191 .try_instantiate_mir_and_normalize_erasing_regions(
192 tcx,
193 TypingEnv::post_analysis(tcx, caller),
194 EarlyBinder::bind(tcx, mir.clone()),
195 )
196 .ok()?;
197 helpers::catch_panic(|| write_args_for_body(semantics, tcx, callee, &body, depth, memo))
198 .ok()
199 .flatten()
200}
201
202fn write_args_rec(
203 semantics: &impl WriteSemantics,
204 tcx: TyCtxt<'_>,
205 callee: DefId,
206 depth: usize,
207 memo: &mut WriteMemo,
208) -> Option<HashSet<usize>> {
209 if depth > 4 {
210 return None;
211 }
212 if !tcx.is_mir_available(callee) {
213 return None;
214 }
215 if semantics.skip_mir_write(tcx, callee) {
216 return None;
217 }
218 let key = (callee, depth);
219 if let Some(summary) = memo.get(&key) {
220 return summary.clone();
221 }
222
223 let summary = helpers::catch_panic(|| {
224 let body = tcx.optimized_mir(callee);
225 write_args_for_body(semantics, tcx, callee, body, depth, memo)
226 })
227 .ok()
228 .flatten();
229 memo.insert(key, summary.clone());
230 summary
231}
232
233fn write_args_for_body<'tcx>(
234 semantics: &impl WriteSemantics,
235 tcx: TyCtxt<'tcx>,
236 callee: DefId,
237 body: &Body<'tcx>,
238 depth: usize,
239 memo: &mut WriteMemo,
240) -> Option<HashSet<usize>> {
241 let mut graph = PathGraph::new(tcx, callee);
242 graph.find_scc();
243 let mut enumerator = PathEnumerator::new(&graph)
244 .with_path_limit(crate::limit::DATAFLOW_CALL_WRITE_PATH_LIMIT);
245 let paths = enumerator.enumerate_paths_repeat(0);
246 if paths.is_truncated() {
247 return None;
248 }
249
250 let mut write: Option<HashSet<usize>> = None;
251 for path in paths.iter() {
252 if !path_ends_in_return(body, &path) {
253 continue;
254 }
255 let writes = write_args_on_path(semantics, tcx, callee, body, &path, depth, memo);
256 write = Some(match write {
257 Some(mut current) => {
258 current.extend(writes);
259 current
260 }
261 None => writes,
262 });
263 }
264
265 Some(write.unwrap_or_default())
266}
267
268fn path_ends_in_return(body: &Body<'_>, path: &[usize]) -> bool {
269 path.last().is_some_and(|block| {
270 body.basic_blocks
271 .get(BasicBlock::from_usize(*block))
272 .and_then(|data| data.terminator.as_ref())
273 .is_some_and(|terminator| {
274 matches!(
275 terminator.kind,
276 TerminatorKind::Return | TerminatorKind::TailCall { .. }
277 )
278 })
279 })
280}
281
282fn write_args_on_path<'tcx>(
283 semantics: &impl WriteSemantics,
284 tcx: TyCtxt<'tcx>,
285 caller: DefId,
286 body: &Body<'tcx>,
287 path: &[usize],
288 depth: usize,
289 memo: &mut WriteMemo,
290) -> HashSet<usize> {
291 let mut writes = HashSet::new();
292 for block in path {
293 let Some(data) = body.basic_blocks.get(BasicBlock::from_usize(*block)) else {
294 continue;
295 };
296
297 for stmt in &data.statements {
298 if let StatementKind::Intrinsic(intrinsic) = &stmt.kind
299 && let NonDivergingIntrinsic::CopyNonOverlapping(copy) = &**intrinsic
300 {
301 writes.extend(trace_to_callee_args(
302 semantics, tcx, caller, body, ©.dst,
303 ));
304 }
305 let StatementKind::Assign(assign) = &stmt.kind else {
306 continue;
307 };
308 let dest = &assign.0;
309 if dest.projection.first() == Some(&ProjectionElem::Deref) {
310 writes.extend(trace_local_to_callee_args(
311 semantics, tcx, caller, body, dest.local,
312 ));
313 }
314 }
315
316 let Some(terminator) = data.terminator.as_ref() else {
317 continue;
318 };
319 let (func, args) = match &terminator.kind {
320 TerminatorKind::Call { func, args, .. } => (func, args),
321 TerminatorKind::TailCall { func, args, .. } => (func, args),
322 _ => continue,
323 };
324
325 if let Some(write_arg) = semantics.direct_write_arg(tcx, func) {
327 if let Some(arg) = args.get(write_arg) {
328 writes.extend(trace_to_callee_args(
329 semantics, tcx, caller, body, &arg.node,
330 ));
331 }
332 continue;
333 }
334
335 if helpers::dep_callee_def_id(func).is_some()
338 && let Some(nested_writes) = semantics
339 .special_write_args(tcx, caller, func, args, body)
340 .map(|args| args.into_iter().collect::<HashSet<_>>())
341 .or_else(|| callsite_write_args_rec(semantics, tcx, caller, func, depth + 1, memo))
342 {
343 for (i, arg) in args.iter().enumerate() {
344 if nested_writes.contains(&i) {
345 writes.extend(trace_to_callee_args(
346 semantics, tcx, caller, body, &arg.node,
347 ));
348 }
349 }
350 }
351 }
352 writes
353}