Skip to main content

rapx/verify/slicer/
relevance.rs

1//! Contract- and property-aware relevance roots for the backward slicer.
2//!
3//! Extends the core [`crate::util::def_use`] `PlaceKey`/`RelevantPlaces`
4//! types with contract/property-aware methods, plus call-site root binding.
5
6use rustc_middle::{mir::Operand, ty::TyCtxt};
7
8use crate::util::def_use::{PlaceBaseKey, PlaceKey, RelevantPlaces, operand_uses};
9use crate::util::mir_utils::callee_param_index_for_local;
10use crate::verify::checkpoint::Checkpoint;
11
12use crate::contract::{
13    ContractExpr, ContractPlace, ContractProjection, NumericPredicate, PlaceBase, Property,
14    PropertyArg, PropertyKind,
15};
16
17impl PlaceKey {
18    /// Build a relevance place key from a parsed contract place.
19    pub(crate) fn from_contract_place(place: &ContractPlace) -> Self {
20        Self {
21            base: match place.base {
22                PlaceBase::Return => PlaceBaseKey::Return,
23                PlaceBase::Arg(index) => PlaceBaseKey::Arg(index),
24                PlaceBase::Local(local) => PlaceBaseKey::Local(local),
25            },
26            fields: place
27                .projections
28                .iter()
29                .filter_map(|projection| match projection {
30                    ContractProjection::Field { index } => Some(*index),
31                    ContractProjection::Downcast { .. } => Some(0),
32                    ContractProjection::ForEach => None,
33                })
34                .collect(),
35        }
36    }
37}
38
39impl RelevantPlaces {
40    /// Extract initial relevance roots from a required property.
41    pub(crate) fn from_property(property: &Property<'_>) -> Self {
42        let mut set = Self::new();
43        set.collect_property(property);
44        set
45    }
46
47    /// Insert a contract place as a relevance root.
48    fn insert_contract_place(&mut self, place: &ContractPlace) {
49        self.insert_place_key(PlaceKey::from_contract_place(place));
50    }
51
52    /// Collect all roots mentioned by a property.
53    fn collect_property(&mut self, property: &Property<'_>) {
54        if let Property::And(and) = property {
55            for conjunct in &and.conjuncts {
56                self.collect_property(conjunct);
57            }
58            return;
59        }
60        if let Property::Or(or) = property {
61            for disjunct in &or.disjuncts {
62                self.collect_property(disjunct);
63            }
64            return;
65        }
66        let kind = property.kind();
67        for (arg_index, arg) in property.args().iter().enumerate() {
68            if let Some(k) = kind
69                && self.collect_target_argument_root(&k, arg_index, arg)
70            {
71                continue;
72            }
73            self.collect_property_arg(arg);
74        }
75    }
76
77    /// Collect a numeric std-contract target argument as a callee argument root.
78    fn collect_target_argument_root(
79        &mut self,
80        kind: &PropertyKind,
81        arg_index: usize,
82        arg: &PropertyArg<'_>,
83    ) -> bool {
84        if !is_target_argument_index(kind, arg_index) {
85            return false;
86        }
87        let Some(ContractExpr::Const(value)) = arg.expr() else {
88            return false;
89        };
90        let Ok(index) = usize::try_from(*value) else {
91            return false;
92        };
93        self.insert_place_key(PlaceKey {
94            base: PlaceBaseKey::Arg(index),
95            fields: Vec::new(),
96        });
97        true
98    }
99
100    /// Collect all roots mentioned by a property argument.
101    fn collect_property_arg(&mut self, arg: &PropertyArg<'_>) {
102        match arg {
103            PropertyArg::Expr(expr) | PropertyArg::ForEach(expr) => self.collect_contract_expr(expr),
104            PropertyArg::Predicates(predicates) => {
105                for predicate in predicates {
106                    self.collect_numeric_predicate(predicate);
107                }
108            }
109            PropertyArg::Ty(_) | PropertyArg::Ident(_) | PropertyArg::Region(_) => {}
110        }
111    }
112
113    /// Collect all roots mentioned by a numeric predicate.
114    fn collect_numeric_predicate(&mut self, predicate: &NumericPredicate<'_>) {
115        self.collect_contract_expr(&predicate.lhs);
116        self.collect_contract_expr(&predicate.rhs);
117    }
118
119    /// Collect all roots mentioned by a contract expression.
120    fn collect_contract_expr(&mut self, expr: &ContractExpr<'_>) {
121        match expr {
122            ContractExpr::Place(place) => self.insert_contract_place(place),
123            ContractExpr::Binary { lhs, rhs, .. } => {
124                self.collect_contract_expr(lhs);
125                self.collect_contract_expr(rhs);
126            }
127            ContractExpr::Unary { expr, .. } => self.collect_contract_expr(expr),
128            ContractExpr::MethodCall { receiver, args, .. } => {
129                self.collect_contract_expr(receiver);
130                for arg in args {
131                    self.collect_contract_expr(arg);
132                }
133            }
134            ContractExpr::Len(expr, _) | ContractExpr::IsEmpty(expr, _) => {
135                self.collect_contract_expr(expr);
136                if let ContractExpr::Place(place) = expr.as_ref() {
137                    self.need_len.insert(PlaceKey::from_contract_place(place));
138                }
139            }
140            ContractExpr::IndexAccess { slice, index } => {
141                self.collect_contract_expr(slice);
142                self.collect_contract_expr(index);
143            }
144            ContractExpr::If {
145                cond,
146                then_expr,
147                else_expr,
148            } => {
149                self.collect_numeric_predicate(cond);
150                self.collect_contract_expr(then_expr);
151                self.collect_contract_expr(else_expr);
152            }
153            ContractExpr::Const(_)
154            | ContractExpr::ConstParam { .. }
155            | ContractExpr::SizeOf(_)
156            | ContractExpr::AlignOf(_)
157            | ContractExpr::Unknown => {}
158        }
159    }
160}
161
162/// Return whether an argument index is a target-place position for a property.
163fn is_target_argument_index(kind: &PropertyKind, arg_index: usize) -> bool {
164    match kind {
165        PropertyKind::NonOverlap | PropertyKind::Alias => arg_index <= 1,
166        PropertyKind::ValidNum | PropertyKind::Unknown => false,
167        _ => arg_index == 0,
168    }
169}
170
171/// Bind callee parameter roots to concrete MIR call operands.
172pub(crate) fn bind_callsite_roots(
173    tcx: TyCtxt<'_>,
174    relevance: &mut RelevantPlaces,
175    checkpoint: &Checkpoint<'_>,
176) {
177    let argument_roots: Vec<(PlaceKey, usize)> = relevance
178        .places
179        .iter()
180        .filter_map(|place| argument_index_of_place(tcx, checkpoint, place))
181        .collect();
182
183    let mut bound_roots = RelevantPlaces::new();
184    let mut rebound_roots = Vec::new();
185    for (root, index) in argument_roots {
186        if let Some(operand) = checkpoint.args.get(index) {
187            if let Some(place) = bind_operand_place(operand, &root.fields) {
188                bound_roots.insert_place_key(place);
189            } else {
190                bound_roots.extend(operand_uses(operand));
191            }
192            rebound_roots.push(root);
193        }
194    }
195
196    relevance.remove_place_keys(&rebound_roots);
197    relevance.extend(bound_roots);
198
199    // Bind need_len places: contract `Len(place)` expressions where the
200    // inner place is a callee argument.  The bound callsite place is
201    // registered in relevance.need_len so the backward slicer can match
202    // `slice::len()` calls that operate on the same pointer/slice.
203    {
204        let need_len_roots: Vec<(PlaceKey, usize)> = relevance
205            .need_len
206            .iter()
207            .filter_map(|place| argument_index_of_place(tcx, checkpoint, place))
208            .collect();
209        for (root, index) in need_len_roots {
210            if let Some(operand) = checkpoint.args.get(index)
211                && let Some(place) = bind_operand_place(operand, &root.fields)
212            {
213                relevance.need_len.insert(place);
214            }
215        }
216    }
217}
218
219/// Map a root place to its callee argument index, if it is an `Arg` or a
220/// `Local` that traces to a callee parameter.
221fn argument_index_of_place(
222    tcx: TyCtxt<'_>,
223    checkpoint: &Checkpoint<'_>,
224    place: &PlaceKey,
225) -> Option<(PlaceKey, usize)> {
226    match place.base {
227        PlaceBaseKey::Arg(index) => Some((place.clone(), index)),
228        PlaceBaseKey::Local(local) => checkpoint
229            .callee
230            .and_then(|callee| callee_param_index_for_local(tcx, callee, local))
231            .map(|index| (place.clone(), index)),
232        _ => None,
233    }
234}
235
236fn bind_operand_place(operand: &Operand<'_>, fields: &[usize]) -> Option<PlaceKey> {
237    let mut place = match operand {
238        Operand::Copy(place) | Operand::Move(place) => PlaceKey::from_mir_place(place),
239        Operand::Constant(_) => return None,
240        Operand::RuntimeChecks(_) => return None,
241    };
242    place.fields.extend(fields.iter().copied());
243    Some(place)
244}