rapx/verify/slicer/
relevance.rs1use 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 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 pub(crate) fn from_property(property: &Property<'_>) -> Self {
42 let mut set = Self::new();
43 set.collect_property(property);
44 set
45 }
46
47 fn insert_contract_place(&mut self, place: &ContractPlace) {
49 self.insert_place_key(PlaceKey::from_contract_place(place));
50 }
51
52 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 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 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 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 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
162fn 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
171pub(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 {
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
219fn 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}