rapx/helpers/
def_use.rs

1//! Def-use computation types and pure MIR helpers.
2//!
3//! These types (`PlaceKey`, `PlaceBaseKey`, `RelevantPlaces`, `DefUse`) track
4//! which MIR places are relevant to an analysis and compute definitions/uses
5//! from MIR terminators.  Shared between the verify module and other analysis
6//! passes (points-to, etc.).
7
8use crate::analysis::dataflow::types::DataflowGraph;
9use crate::compat::FxHashSet;
10use crate::compat::Spanned;
11use rustc_middle::mir::{
12    Local, Operand, Place, ProjectionElem, Rvalue, Terminator, TerminatorKind,
13};
14
15/// Definitions and uses collected from one MIR item.
16#[derive(Clone, Debug, Default)]
17pub struct DefUse {
18    /// Places defined or invalidated by the MIR item.
19    pub defs: RelevantPlaces,
20    /// Places read by the MIR item.
21    pub uses: RelevantPlaces,
22}
23
24impl DefUse {
25    /// Create an empty use-def summary.
26    pub fn new() -> Self {
27        Self::default()
28    }
29}
30
31/// Base of a contract/MIR place tracked by relevance.
32#[derive(Clone, Debug, Eq, PartialEq, Hash)]
33pub enum PlaceBaseKey {
34    /// MIR return local `_0`.
35    Return,
36    /// MIR local by numeric index.
37    Local(usize),
38    /// Callee argument by index before checkpoint binding.
39    Arg(usize),
40}
41
42/// Projection-insensitive enough place key for relevance tracking.
43#[derive(Clone, Debug, Eq, PartialEq, Hash)]
44pub struct PlaceKey {
45    /// Base local/argument of the place.
46    pub base: PlaceBaseKey,
47    /// Field projections kept from the contract place.
48    pub fields: Vec<usize>,
49}
50
51impl PlaceKey {
52    /// Build a relevance place key from a MIR place.
53    pub fn from_mir_place(place: &Place<'_>) -> Self {
54        Self {
55            base: if place.local.as_usize() == 0 {
56                PlaceBaseKey::Return
57            } else {
58                PlaceBaseKey::Local(place.local.as_usize())
59            },
60            fields: place
61                .projection
62                .iter()
63                .filter_map(|projection| match projection {
64                    ProjectionElem::Field(index, _) => Some(index.as_usize()),
65                    _ => None,
66                })
67                .collect(),
68        }
69    }
70
71    /// Return the MIR local represented by this key when it is already known.
72    pub fn local(&self) -> Option<Local> {
73        match self.base {
74            PlaceBaseKey::Return => Some(Local::from_usize(0)),
75            PlaceBaseKey::Local(local) => Some(Local::from_usize(local)),
76            PlaceBaseKey::Arg(_) => None,
77        }
78    }
79
80    /// Build a PlaceKey from an analysis-level `(origin_local, fields)` tuple.
81    pub fn from_origin(local: usize, fields: Vec<usize>) -> Self {
82        Self {
83            base: PlaceBaseKey::Local(local),
84            fields,
85        }
86    }
87
88    /// Return true when this place shares a base-and-projection prefix with
89    /// `other`.  Two places overlap when one of them is a shorter projection
90    /// of the other (e.g. `[]` overlaps `[0]`, but `[0]` does not overlap
91    /// `[1]`).
92    pub fn overlaps(&self, other: &PlaceKey) -> bool {
93        self.base == other.base && {
94            let min_len = self.fields.len().min(other.fields.len());
95            self.fields[..min_len] == other.fields[..min_len]
96        }
97    }
98}
99
100/// Set of places that make MIR items relevant to a property.
101#[derive(Clone, Debug, Default)]
102pub struct RelevantPlaces {
103    pub places: FxHashSet<PlaceKey>,
104    pub locals: FxHashSet<Local>,
105    pub saturated: FxHashSet<PlaceKey>,
106    pub just_added: FxHashSet<PlaceKey>,
107    /// Places whose length is needed by a `Len(place)` contract expression.
108    /// Carried through the backward slice to trigger inclusion of `slice::len()`
109    /// calls whose argument traces to the same origin.
110    pub need_len: FxHashSet<PlaceKey>,
111}
112
113impl RelevantPlaces {
114    /// Create an empty relevance set.
115    pub fn new() -> Self {
116        Self::default()
117    }
118
119    /// Insert a MIR local as a relevance root, tracking the addition.
120    pub fn insert_local(&mut self, local: Local) {
121        let pk = PlaceKey {
122            base: if local.as_usize() == 0 {
123                PlaceBaseKey::Return
124            } else {
125                PlaceBaseKey::Local(local.as_usize())
126            },
127            fields: Vec::new(),
128        };
129        if self.places.insert(pk.clone()) {
130            self.just_added.insert(pk);
131        }
132        self.locals.insert(local);
133    }
134
135    /// Insert a MIR place as a relevance root.
136    pub fn insert_mir_place(&mut self, place: &Place<'_>) {
137        self.insert_place_key(PlaceKey::from_mir_place(place));
138    }
139
140    /// Insert a prebuilt place key as a relevance root, tracking addition.
141    pub fn insert_place_key(&mut self, place: PlaceKey) {
142        if let Some(local) = place.local() {
143            self.locals.insert(local);
144        }
145        if self.places.insert(place.clone()) {
146            self.just_added.insert(place);
147        }
148    }
149
150    /// Merge another relevance set into this one, tracking additions.
151    pub fn extend(&mut self, other: RelevantPlaces) {
152        for place in other.places {
153            if self.places.insert(place.clone()) {
154                self.just_added.insert(place);
155            }
156        }
157        for local in other.locals {
158            self.locals.insert(local);
159        }
160        for place in other.need_len {
161            self.need_len.insert(place);
162        }
163    }
164
165    /// Remove a list of place keys and rebuild the derived local set.
166    pub fn remove_place_keys(&mut self, places: &[PlaceKey]) {
167        for place in places {
168            self.places.remove(place);
169        }
170        self.rebuild_locals();
171    }
172
173    /// Return true if this set shares any known root with `other`.
174    pub fn intersects(&self, other: &RelevantPlaces) -> bool {
175        self.places
176            .iter()
177            .any(|sp| other.places.iter().any(|op| sp.overlaps(op)))
178    }
179
180    /// Remove all roots contained in `other` from this set, marking them
181    /// as saturated (definition found).
182    pub fn remove_all(&mut self, other: &RelevantPlaces) {
183        for local in &other.locals {
184            self.saturated.insert(PlaceKey {
185                base: PlaceBaseKey::Local(local.as_usize()),
186                fields: vec![],
187            });
188            self.locals.remove(local);
189            self.places.retain(|place| place.local() != Some(*local));
190        }
191        for place in &other.places {
192            self.saturated.insert(place.clone());
193            self.places.remove(place);
194            if let Some(local) = place.local() {
195                self.locals.remove(&local);
196            }
197        }
198    }
199
200    fn rebuild_locals(&mut self) {
201        self.locals = self.places.iter().filter_map(PlaceKey::local).collect();
202    }
203}
204
205// ── def-use extraction from MIR ────────────────────────────────────────
206
207/// Collect definitions and uses for one MIR terminator.
208///
209/// Call terminators are handled separately by the slicer's `call_visit` module
210/// (which consults interprocedural summaries), so the `Call` arm is
211/// deliberately absent here.
212pub fn terminator_use_def<'tcx>(terminator: &Terminator<'tcx>) -> DefUse {
213    let mut use_def = DefUse::new();
214    match &terminator.kind {
215        TerminatorKind::SwitchInt { discr, .. } => {
216            use_def.uses.extend(operand_uses(discr));
217        }
218        TerminatorKind::Assert { cond, .. } => {
219            use_def.uses.extend(operand_uses(cond));
220        }
221        TerminatorKind::Drop { place, .. } => {
222            use_def.uses.extend(place_uses(place));
223        }
224        _ => {}
225    }
226    use_def
227}
228
229/// Collect MIR roots used by selected call argument indices.
230pub fn call_args_uses_at<'tcx>(
231    args: &[Spanned<Operand<'tcx>>],
232    indices: &[usize],
233) -> RelevantPlaces {
234    let mut uses = RelevantPlaces::new();
235    for index in indices {
236        if let Some(arg) = args.get(*index) {
237            uses.extend(operand_uses(&arg.node));
238        }
239    }
240    uses
241}
242
243/// Collect all MIR roots used by an operand.
244pub fn operand_uses<'tcx>(operand: &Operand<'tcx>) -> RelevantPlaces {
245    let mut uses = RelevantPlaces::new();
246    match operand {
247        Operand::Copy(place) | Operand::Move(place) => {
248            uses.extend(place_uses(place));
249        }
250        Operand::Constant(_) => {}
251        #[cfg(rapx_ge_95)]
252        Operand::RuntimeChecks(_) => {}
253    }
254    uses
255}
256
257fn place_uses(place: &Place<'_>) -> RelevantPlaces {
258    let mut uses = RelevantPlaces::new();
259    uses.insert_mir_place(place);
260    uses.extend(place_projection_uses(place));
261    uses
262}
263
264fn place_projection_uses(place: &Place<'_>) -> RelevantPlaces {
265    let mut uses = RelevantPlaces::new();
266    for projection in place.projection {
267        if let ProjectionElem::Index(local) = projection {
268            uses.insert_local(local);
269        }
270    }
271    uses
272}
273
274/// Collect all MIR operands referenced by an rvalue.
275pub fn rvalue_operands<'tcx>(rvalue: &'tcx Rvalue<'tcx>) -> Vec<&'tcx Operand<'tcx>> {
276    let mut operands = Vec::new();
277    match rvalue {
278        Rvalue::Use(op, ..)
279        | Rvalue::Repeat(op, _)
280        | Rvalue::Cast(_, op, _)
281        | Rvalue::UnaryOp(_, op) => {
282            operands.push(op);
283        }
284        Rvalue::BinaryOp(_, pair) => {
285            let (lhs, rhs) = &**pair;
286            operands.push(lhs);
287            operands.push(rhs);
288        }
289        Rvalue::Ref(_, _, _) | Rvalue::RawPtr(_, _) => {}
290        #[cfg(not(rapx_ge_99))]
291        Rvalue::ShallowInitBox(_, _) => {}
292        Rvalue::Aggregate(_, aggregate_operands) => {
293            operands.extend(aggregate_operands.iter());
294        }
295        Rvalue::Discriminant(_) | Rvalue::CopyForDeref(_) | Rvalue::ThreadLocalRef(_) | _ => {}
296    }
297    operands
298}
299
300// ── chain-tracing helpers ────────────────────────────────────────────
301
302/// Trace a [`PlaceKey`] through the dataflow graph to resolve
303/// Copy/Move chains back to their origin local.
304pub fn trace_place_origin(flow: &DataflowGraph, key: &PlaceKey) -> PlaceKey {
305    let Some(local) = key.local() else {
306        return key.clone();
307    };
308    PlaceKey {
309        base: PlaceBaseKey::Local(flow.trace_origin(local).as_usize()),
310        fields: key.fields.clone(),
311    }
312}
rapx/helpers/def_use.rs

rapx/helpers/
def_use.rs
