Skip to main content

rapx/analysis/dataflow/
call_write.rs

1//! Trace writes through call arguments in MIR, including wrapper calls.
2
3use 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
18/// API-specific facts needed by the MIR write tracer.
19pub(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
38/// Memo keyed by `(callee, depth)` for uninstantiated MIR summaries.
39type WriteMemo = HashMap<(DefId, usize), Option<HashSet<usize>>>;
40
41/// Trace backward from an operand (inner call arg) through Copy/Move/Cast/
42/// Ref/RawPtr/tuple assignments to the outer callee's argument locals.
43/// `Ref`/`RawPtr` are treated as data-flow too, which is an
44/// approximation (taking a reference is not a pure copy) but is adequate for
45/// wrapper recognition.
46fn 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            // Trace through pointer-preserving calls: `as_ptr`/`as_mut_ptr`
126            // (and friends) return the pointee address, while `add`/`sub`/
127            // `offset` return the base pointer shifted by an offset — the
128            // provenance (and thus the written-through arg) is carried by
129            // their first (base/receiver) argument.
130            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
149/// Return arguments written by the concrete call, following wrapper calls
150/// while retaining their generic arguments.
151pub(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, &copy.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        // `ptr::write`-style writes: trace the pointer arg to a callee arg.
326        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        // Wrapper calls: a nested callee that writes its own args maps those
336        // writes back onto this callee's args.
337        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}