Skip to main content

rapx/util/
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::compat::FxHashSet;
9use crate::compat::Spanned;
10use rustc_middle::mir::{
11    Local, Operand, Place, ProjectionElem, Rvalue, Terminator, TerminatorKind,
12};
13
14/// Definitions and uses collected from one MIR item.
15#[derive(Clone, Debug, Default)]
16pub struct DefUse {
17    /// Places defined or invalidated by the MIR item.
18    pub defs: RelevantPlaces,
19    /// Places read by the MIR item.
20    pub uses: RelevantPlaces,
21}
22
23impl DefUse {
24    /// Create an empty use-def summary.
25    pub fn new() -> Self {
26        Self::default()
27    }
28}
29
30/// Base of a contract/MIR place tracked by relevance.
31#[derive(Clone, Debug, Eq, PartialEq, Hash)]
32pub enum PlaceBaseKey {
33    /// MIR return local `_0`.
34    Return,
35    /// MIR local by numeric index.
36    Local(usize),
37    /// Callee argument by index before checkpoint binding.
38    Arg(usize),
39}
40
41/// Projection-insensitive enough place key for relevance tracking.
42#[derive(Clone, Debug, Eq, PartialEq, Hash)]
43pub struct PlaceKey {
44    /// Base local/argument of the place.
45    pub base: PlaceBaseKey,
46    /// Field projections kept from the contract place.
47    pub fields: Vec<usize>,
48}
49
50impl PlaceKey {
51    /// Build a relevance place key from a MIR place.
52    pub fn from_mir_place(place: &Place<'_>) -> Self {
53        Self {
54            base: if place.local.as_usize() == 0 {
55                PlaceBaseKey::Return
56            } else {
57                PlaceBaseKey::Local(place.local.as_usize())
58            },
59            fields: place
60                .projection
61                .iter()
62                .filter_map(|projection| match projection {
63                    ProjectionElem::Field(index, _) => Some(index.as_usize()),
64                    _ => None,
65                })
66                .collect(),
67        }
68    }
69
70    /// Return the MIR local represented by this key when it is already known.
71    pub fn local(&self) -> Option<Local> {
72        match self.base {
73            PlaceBaseKey::Return => Some(Local::from_usize(0)),
74            PlaceBaseKey::Local(local) => Some(Local::from_usize(local)),
75            PlaceBaseKey::Arg(_) => None,
76        }
77    }
78
79    /// Build a PlaceKey from an analysis-level `(origin_local, fields)` tuple.
80    pub fn from_origin(local: usize, fields: Vec<usize>) -> Self {
81        Self {
82            base: PlaceBaseKey::Local(local),
83            fields,
84        }
85    }
86
87    /// Return true when this place shares a base-and-projection prefix with
88    /// `other`.  Two places overlap when one of them is a shorter projection
89    /// of the other (e.g. `[]` overlaps `[0]`, but `[0]` does not overlap
90    /// `[1]`).
91    pub fn overlaps(&self, other: &PlaceKey) -> bool {
92        self.base == other.base && {
93            let min_len = self.fields.len().min(other.fields.len());
94            self.fields[..min_len] == other.fields[..min_len]
95        }
96    }
97}
98
99/// Set of places that make MIR items relevant to a property.
100#[derive(Clone, Debug, Default)]
101pub struct RelevantPlaces {
102    pub places: FxHashSet<PlaceKey>,
103    pub enum_payload_writes: FxHashSet<(rustc_hir::def_id::DefId, Local, usize)>,
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        self.enum_payload_writes.extend(other.enum_payload_writes);
153        for place in other.places {
154            if self.places.insert(place.clone()) {
155                self.just_added.insert(place);
156            }
157        }
158        for local in other.locals {
159            self.locals.insert(local);
160        }
161        for place in other.need_len {
162            self.need_len.insert(place);
163        }
164    }
165
166    /// Remove a list of place keys and rebuild the derived local set.
167    pub fn remove_place_keys(&mut self, places: &[PlaceKey]) {
168        for place in places {
169            self.places.remove(place);
170        }
171        self.rebuild_locals();
172    }
173
174    /// Return true if this set shares any known root with `other`.
175    pub fn intersects(&self, other: &RelevantPlaces) -> bool {
176        self.places
177            .iter()
178            .any(|sp| other.places.iter().any(|op| sp.overlaps(op)))
179    }
180
181    /// Remove all roots contained in `other` from this set, marking them
182    /// as saturated (definition found).
183    pub fn remove_all(&mut self, other: &RelevantPlaces) {
184        for local in &other.locals {
185            self.saturated.insert(PlaceKey {
186                base: PlaceBaseKey::Local(local.as_usize()),
187                fields: vec![],
188            });
189            self.locals.remove(local);
190            self.places.retain(|place| place.local() != Some(*local));
191        }
192        for place in &other.places {
193            self.saturated.insert(place.clone());
194            self.places.remove(place);
195            if let Some(local) = place.local() {
196                self.locals.remove(&local);
197            }
198        }
199    }
200
201    fn rebuild_locals(&mut self) {
202        self.locals = self.places.iter().filter_map(PlaceKey::local).collect();
203    }
204}
205
206// ── def-use extraction from MIR ────────────────────────────────────────
207
208/// Collect definitions and uses for one MIR terminator.
209///
210/// Ordinary calls are handled by the slicer's call visitor. Tail calls also
211/// expose their return place and operand uses here for generic consumers.
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        TerminatorKind::TailCall { func, args, .. } => {
225            use_def.defs.insert_local(Local::from_usize(0));
226            use_def.uses.extend(operand_uses(func));
227            for arg in args.iter() {
228                use_def.uses.extend(operand_uses(&arg.node));
229            }
230        }
231        _ => {}
232    }
233    use_def
234}
235
236/// Collect MIR roots used by selected call argument indices.
237pub fn call_args_uses_at<'tcx>(
238    args: &[Spanned<Operand<'tcx>>],
239    indices: &[usize],
240) -> RelevantPlaces {
241    let mut uses = RelevantPlaces::new();
242    for index in indices {
243        if let Some(arg) = args.get(*index) {
244            uses.extend(operand_uses(&arg.node));
245        }
246    }
247    uses
248}
249
250/// Collect all MIR roots used by an operand.
251pub fn operand_uses<'tcx>(operand: &Operand<'tcx>) -> RelevantPlaces {
252    let mut uses = RelevantPlaces::new();
253    match operand {
254        Operand::Copy(place) | Operand::Move(place) => {
255            uses.extend(place_uses(place));
256        }
257        Operand::Constant(_) => {}
258        Operand::RuntimeChecks(_) => {}
259    }
260    uses
261}
262
263fn place_uses(place: &Place<'_>) -> RelevantPlaces {
264    let mut uses = RelevantPlaces::new();
265    uses.insert_mir_place(place);
266    uses.extend(place_projection_uses(place));
267    uses
268}
269
270fn place_projection_uses(place: &Place<'_>) -> RelevantPlaces {
271    let mut uses = RelevantPlaces::new();
272    for projection in place.projection {
273        if let ProjectionElem::Index(local) = projection {
274            uses.insert_local(local);
275        }
276    }
277    uses
278}
279
280/// Collect all MIR operands referenced by an rvalue.
281pub fn rvalue_operands<'tcx>(rvalue: &'tcx Rvalue<'tcx>) -> Vec<&'tcx Operand<'tcx>> {
282    let mut operands = Vec::new();
283    match rvalue {
284        Rvalue::Use(op, ..)
285        | Rvalue::Repeat(op, _)
286        | Rvalue::Cast(_, op, _)
287        | Rvalue::WrapUnsafeBinder(op, _)
288        | Rvalue::UnaryOp(_, op) => {
289            operands.push(op);
290        }
291        Rvalue::BinaryOp(_, pair) => {
292            let (lhs, rhs) = &**pair;
293            operands.push(lhs);
294            operands.push(rhs);
295        }
296        Rvalue::Ref(_, _, _) | Rvalue::RawPtr(_, _) => {}
297        Rvalue::Aggregate(_, aggregate_operands) => {
298            operands.extend(aggregate_operands.iter());
299        }
300        _ => {}
301    }
302    operands
303}