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    /// Return true when no roots have been collected.
120    pub fn is_empty(&self) -> bool {
121        self.places.is_empty() && self.locals.is_empty()
122    }
123
124    /// Insert a MIR local as a relevance root, tracking the addition.
125    pub fn insert_local(&mut self, local: Local) {
126        let pk = PlaceKey {
127            base: if local.as_usize() == 0 {
128                PlaceBaseKey::Return
129            } else {
130                PlaceBaseKey::Local(local.as_usize())
131            },
132            fields: Vec::new(),
133        };
134        if self.places.insert(pk.clone()) {
135            self.just_added.insert(pk);
136        }
137        self.locals.insert(local);
138    }
139
140    /// Insert a MIR place as a relevance root.
141    pub fn insert_mir_place(&mut self, place: &Place<'_>) {
142        self.insert_place_key(PlaceKey::from_mir_place(place));
143    }
144
145    /// Insert a prebuilt place key as a relevance root, tracking addition.
146    pub fn insert_place_key(&mut self, place: PlaceKey) {
147        if let Some(local) = place.local() {
148            self.locals.insert(local);
149        }
150        if self.places.insert(place.clone()) {
151            self.just_added.insert(place);
152        }
153    }
154
155    /// Merge another relevance set into this one, tracking additions.
156    pub fn extend(&mut self, other: RelevantPlaces) {
157        for place in other.places {
158            if self.places.insert(place.clone()) {
159                self.just_added.insert(place);
160            }
161        }
162        for local in other.locals {
163            self.locals.insert(local);
164        }
165        for place in other.need_len {
166            self.need_len.insert(place);
167        }
168    }
169
170    /// Remove a list of place keys and rebuild the derived local set.
171    pub fn remove_place_keys(&mut self, places: &[PlaceKey]) {
172        for place in places {
173            self.places.remove(place);
174        }
175        self.rebuild_locals();
176    }
177
178    /// Return true if this set shares any known root with `other`.
179    pub fn intersects(&self, other: &RelevantPlaces) -> bool {
180        self.places
181            .iter()
182            .any(|sp| other.places.iter().any(|op| sp.overlaps(op)))
183    }
184
185    /// Remove all roots contained in `other` from this set, marking them
186    /// as saturated (definition found).
187    pub fn remove_all(&mut self, other: &RelevantPlaces) {
188        for local in &other.locals {
189            self.saturated.insert(PlaceKey {
190                base: PlaceBaseKey::Local(local.as_usize()),
191                fields: vec![],
192            });
193            self.locals.remove(local);
194            self.places.retain(|place| place.local() != Some(*local));
195        }
196        for place in &other.places {
197            self.saturated.insert(place.clone());
198            self.places.remove(place);
199            if let Some(local) = place.local() {
200                self.locals.remove(&local);
201            }
202        }
203    }
204
205    fn rebuild_locals(&mut self) {
206        self.locals = self.places.iter().filter_map(PlaceKey::local).collect();
207    }
208}
209
210// ── def-use extraction from MIR ────────────────────────────────────────
211
212/// Collect definitions and uses for one MIR terminator.
213pub fn terminator_use_def<'tcx>(terminator: &Terminator<'tcx>) -> DefUse {
214    let mut use_def = DefUse::new();
215    match &terminator.kind {
216        TerminatorKind::Call {
217            func,
218            args,
219            destination,
220            ..
221        } => {
222            use_def.defs.insert_mir_place(destination);
223            use_def.uses.extend(operand_uses(func));
224            for arg in args {
225                use_def.uses.extend(operand_uses(&arg.node));
226            }
227        }
228        TerminatorKind::SwitchInt { discr, .. } => {
229            use_def.uses.extend(operand_uses(discr));
230        }
231        TerminatorKind::Assert { cond, .. } => {
232            use_def.uses.extend(operand_uses(cond));
233        }
234        TerminatorKind::Drop { place, .. } => {
235            use_def.uses.extend(place_uses(place));
236        }
237        _ => {}
238    }
239    use_def
240}
241
242/// Collect MIR roots used by selected call argument indices.
243pub fn call_args_uses_at<'tcx>(
244    args: &[Spanned<Operand<'tcx>>],
245    indices: &[usize],
246) -> RelevantPlaces {
247    let mut uses = RelevantPlaces::new();
248    for index in indices {
249        if let Some(arg) = args.get(*index) {
250            uses.extend(operand_uses(&arg.node));
251        }
252    }
253    uses
254}
255
256/// Collect all MIR roots used by an operand.
257pub fn operand_uses<'tcx>(operand: &Operand<'tcx>) -> RelevantPlaces {
258    let mut uses = RelevantPlaces::new();
259    match operand {
260        Operand::Copy(place) | Operand::Move(place) => {
261            uses.extend(place_uses(place));
262        }
263        Operand::Constant(_) => {}
264        #[cfg(rapx_ge_99)]
265        Operand::RuntimeChecks(_) => {}
266    }
267    uses
268}
269
270fn place_uses(place: &Place<'_>) -> RelevantPlaces {
271    let mut uses = RelevantPlaces::new();
272    uses.insert_mir_place(place);
273    uses.extend(place_projection_uses(place));
274    uses
275}
276
277fn place_projection_uses(place: &Place<'_>) -> RelevantPlaces {
278    let mut uses = RelevantPlaces::new();
279    for projection in place.projection {
280        if let ProjectionElem::Index(local) = projection {
281            uses.insert_local(local);
282        }
283    }
284    uses
285}
286
287/// Collect all MIR operands referenced by an rvalue.
288pub fn rvalue_operands<'tcx>(rvalue: &'tcx Rvalue<'tcx>) -> Vec<&'tcx Operand<'tcx>> {
289    let mut operands = Vec::new();
290    match rvalue {
291        Rvalue::Use(op, ..)
292        | Rvalue::Repeat(op, _)
293        | Rvalue::Cast(_, op, _)
294        | Rvalue::UnaryOp(_, op) => {
295            operands.push(op);
296        }
297        Rvalue::BinaryOp(_, pair) => {
298            let (lhs, rhs) = &**pair;
299            operands.push(lhs);
300            operands.push(rhs);
301        }
302        Rvalue::Ref(_, _, _) | Rvalue::RawPtr(_, _) => {}
303        #[cfg(not(rapx_ge_99))]
304        Rvalue::ShallowInitBox(_, _) => {}
305        Rvalue::Aggregate(_, aggregate_operands) => {
306            operands.extend(aggregate_operands.iter());
307        }
308        Rvalue::Discriminant(_) | Rvalue::CopyForDeref(_) | Rvalue::ThreadLocalRef(_) | _ => {}
309    }
310    operands
311}
312
313// ── chain-tracing helpers ────────────────────────────────────────────
314
315/// Trace a [`PlaceKey`] through the dataflow graph to resolve
316/// Copy/Move chains back to their origin local.
317pub fn trace_place_origin(flow: &DataflowGraph, key: &PlaceKey) -> PlaceKey {
318    let Some(local) = key.local() else {
319        return key.clone();
320    };
321    PlaceKey {
322        base: PlaceBaseKey::Local(flow.trace_origin(local).as_usize()),
323        fields: key.fields.clone(),
324    }
325}
rapx/helpers/def_use.rs

rapx/helpers/
def_use.rs
