Skip to main content

rapx/verify/vm/
contract_eval.rs

1//! Checkpoint-bound contract expression evaluation over symbolic VM values.
2
3use crate::util::mir_utils;
4use crate::verify::checkpoint::Checkpoint;
5use crate::contract::{BinOp, ContractExpr, PlaceBase};
6use rustc_hir::def_id::DefId;
7#[cfg(rapx_const_ext)]
8use rustc_middle::ty::consts::ConstExt;
9use rustc_middle::{
10    mir::{Local, Operand, Place, TerminatorKind},
11    ty::{GenericArgKind, Ty, TyKind},
12};
13use z3::ast::{Ast, Int};
14
15use crate::vm::state::{VmExecutor, VmValue};
16
17impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
18    pub(crate) fn eval_contract_tree(
19        &self,
20        expr: &ContractExpr<'tcx>,
21        checkpoint: Option<&Checkpoint<'tcx>>,
22    ) -> Option<Int<'z3>> {
23        match expr {
24            ContractExpr::Const(value) => Some(self.u128_term(*value)),
25            ContractExpr::Binary { op, lhs, rhs } => {
26                let left = self.eval_contract_tree(lhs, checkpoint)?;
27                let right = self.eval_contract_tree(rhs, checkpoint)?;
28                match op {
29                    BinOp::Add | BinOp::Sub | BinOp::Mul => {
30                        self.contract_binary_term(*op, &left, &right)
31                    }
32                    BinOp::Div | BinOp::Rem => {
33                        if right.as_u64() == Some(0) {
34                            Some(Int::from_u64(self.z3_ctx, 0))
35                        } else if matches!(op, BinOp::Div) {
36                            Some(left.div(&right))
37                        } else {
38                            let quotient = left.div(&right);
39                            Some(Int::sub(
40                                self.z3_ctx,
41                                &[&left, &Int::mul(self.z3_ctx, &[&quotient, &right])],
42                            ))
43                        }
44                    }
45                    BinOp::Min => Some(left.le(&right).ite(&left, &right)),
46                    BinOp::Max => Some(left.ge(&right).ite(&left, &right)),
47                    _ => None,
48                }
49            }
50            ContractExpr::Unary { op, expr } => {
51                let value = self.eval_contract_tree(expr, checkpoint)?;
52                Some(self.contract_unary_term(*op, &value))
53            }
54            ContractExpr::If {
55                cond,
56                then_expr,
57                else_expr,
58            } => {
59                let left = self.eval_contract_tree(&cond.lhs, checkpoint)?;
60                let right = self.eval_contract_tree(&cond.rhs, checkpoint)?;
61                let condition = self.contract_relop_bool(cond.op, &left, &right);
62                match condition.simplify().as_bool() {
63                    Some(true) => self.eval_contract_tree(then_expr, checkpoint),
64                    Some(false) => self.eval_contract_tree(else_expr, checkpoint),
65                    None => {
66                        let then_value = self.eval_contract_tree(then_expr, checkpoint)?;
67                        let else_value = self.eval_contract_tree(else_expr, checkpoint)?;
68                        Some(condition.ite(&then_value, &else_value))
69                    }
70                }
71            }
72            _ => self.eval_contract_expr_check_leaf(checkpoint, expr),
73        }
74    }
75
76    pub(crate) fn instantiate_callsite_ty(
77        &self,
78        checkpoint: &Checkpoint<'tcx>,
79        ty: Ty<'tcx>,
80    ) -> Ty<'tcx> {
81        let TyKind::Param(param) = ty.kind() else {
82            return ty;
83        };
84        if checkpoint.callee.is_none() {
85            return ty;
86        };
87
88        let body = self.body();
89        let terminator = body.basic_blocks[checkpoint.block].terminator();
90        let TerminatorKind::Call { func, .. } = &terminator.kind else {
91            return ty;
92        };
93        let Operand::Constant(func_constant) = func else {
94            return ty;
95        };
96        let TyKind::FnDef(_, args) = func_constant.const_.ty().kind() else {
97            return ty;
98        };
99        let Some(arg) = crate::compat::args_get(args, param.index as usize) else {
100            return ty;
101        };
102        match arg.kind() {
103            GenericArgKind::Type(actual_ty) => actual_ty,
104            _ => ty,
105        }
106    }
107
108    fn instantiate_callsite_const(
109        &self,
110        checkpoint: &Checkpoint<'tcx>,
111        index: u32,
112    ) -> Option<Int<'z3>> {
113        let body = self.body();
114        let terminator = body.basic_blocks[checkpoint.block].terminator();
115        let TerminatorKind::Call { func, .. } = &terminator.kind else {
116            return None;
117        };
118        let Operand::Constant(func_constant) = func else {
119            return None;
120        };
121        let TyKind::FnDef(callee_def_id, args) = func_constant.const_.ty().kind() else {
122            return None;
123        };
124        let arg = crate::compat::args_get(args, index as usize)?;
125        match arg.kind() {
126            GenericArgKind::Const(actual_const) => {
127                let value = actual_const
128                    .try_to_target_usize(self.tcx)
129                    .or_else(|| mir_utils::const_int_from_debug(&format!("{actual_const:?}")));
130                let param = self
131                    .tcx
132                    .generics_of(*callee_def_id)
133                    .param_at(index as usize, self.tcx);
134                let param_ty = self.tcx.type_of(param.def_id).instantiate_identity();
135                let param_ty = param_ty.skip_norm_wip();
136                Some(match value {
137                    Some(value) => Int::from_u64(self.z3_ctx, value),
138                    None => self
139                        .symbolic_const_term(&rustc_middle::mir::Const::Ty(param_ty, actual_const)),
140                })
141            }
142            _ => None,
143        }
144    }
145
146    fn is_caller_type_param(&self, ty: Ty<'tcx>) -> bool {
147        let rustc_middle::ty::TyKind::Param(param_ty) = ty.kind() else {
148            return false;
149        };
150        let generics = self.tcx.generics_of(self.current_def_id());
151        generics.own_params.iter().any(|p| {
152            matches!(p.kind, rustc_middle::ty::GenericParamDefKind::Type { .. })
153                && p.name == param_ty.name
154        })
155    }
156
157    fn eval_contract_method_call(
158        &self,
159        receiver: &ContractExpr<'tcx>,
160        method: DefId,
161        args: &[ContractExpr<'tcx>],
162        checkpoint: Option<&Checkpoint<'tcx>>,
163    ) -> Option<Int<'z3>> {
164        let value = self.eval_contract_expr_to_value(checkpoint, receiver)?;
165        let local = match receiver {
166            ContractExpr::Place(cp) => match cp.base {
167                PlaceBase::Arg(index) => checkpoint
168                    .and_then(|ck| ck.args.get(index))
169                    .and_then(|operand| operand.place())
170                    .map(|place| place.local),
171                PlaceBase::Local(index) => Some(Local::from_usize(index)),
172                PlaceBase::Return => Some(Local::from_usize(0)),
173            },
174            _ => None,
175        };
176        let args = args
177            .iter()
178            .map(|arg| self.eval_contract_tree(arg, checkpoint))
179            .collect::<Option<Vec<_>>>()?;
180        self.eval_contract_method(method, value, local, args)
181    }
182    fn eval_contract_expr_check_leaf(
183        &self,
184        checkpoint: Option<&Checkpoint<'tcx>>,
185        expr: &ContractExpr<'tcx>,
186    ) -> Option<Int<'z3>> {
187        match expr {
188            ContractExpr::SizeOf(ty) => {
189                let mut size = self.size_of_ty(*ty);
190                if size == 0 && matches!(ty.kind(), rustc_middle::ty::TyKind::Param(_)) {
191                    size = mir_utils::size_of_generic_param(
192                        self.tcx,
193                        self.current_def_id(),
194                        *ty,
195                    );
196                    if size == 0
197                        && let Some(ck) = checkpoint
198                        && let Some(_callee) = ck.callee
199                        && !self.is_caller_type_param(*ty)
200                    {
201                        let resolved = self.instantiate_callsite_ty(ck, *ty);
202                        if resolved != *ty {
203                            size = self.size_of_ty(resolved);
204                        }
205                    }
206                }
207                if size > 0 {
208                    Some(Int::from_u64(self.z3_ctx, size))
209                } else {
210                    Some(Int::from_u64(self.z3_ctx, 0))
211                }
212            }
213            ContractExpr::AlignOf(ty) => {
214                let align = self.align_of_ty(*ty);
215                if align > 0 {
216                    Some(Int::from_u64(self.z3_ctx, align.max(1)))
217                } else {
218                    Some(Int::from_u64(self.z3_ctx, 0))
219                }
220            }
221            ContractExpr::Place(cp) => self.eval_contract_place(checkpoint, cp),
222            ContractExpr::Len(inner, method) => {
223                if let Some(method) = method
224                    && let Some(receiver) = self.eval_contract_expr_to_value(checkpoint, inner)
225                    && let Some(result) = self.cached_method_result(*method, &receiver)
226                {
227                    return Some(result);
228                }
229                if let Some(ck) = checkpoint
230                    && let Some(term) = self.try_iter_len_from_fields(ck, inner)
231                {
232                    return Some(term);
233                }
234                let val = self.eval_contract_expr_to_value(checkpoint, inner)?;
235                if self.is_local_adt_receiver(&val) {
236                    return None;
237                }
238                if let crate::contract::ContractExpr::Place(cp) = &**inner
239                    && let Some(field_path) = cp.plain_field_path()
240                {
241                    let base_local = match cp.base {
242                        PlaceBase::Return => Some(Local::from_usize(0)),
243                        PlaceBase::Local(n) => Some(Local::from_usize(n)),
244                        PlaceBase::Arg(n) => {
245                            checkpoint
246                                .and_then(|ck| ck.args.get(n))
247                                .and_then(|op| match op {
248                                    Operand::Copy(p) | Operand::Move(p) => Some(p.local),
249                                    _ => None,
250                                })
251                        }
252                    };
253                    if let Some(local) = base_local
254                        && let Some(len) = self.try_struct_nn_len_field(local, &field_path, val.ty)
255                    {
256                        return Some(len);
257                    }
258                }
259                self.len_from_value(&val)
260            }
261            ContractExpr::MethodCall {
262                receiver,
263                method,
264                args,
265            } => self.eval_contract_method_call(
266                receiver,
267                *method,
268                args,
269                checkpoint,
270            ),
271            ContractExpr::IsEmpty(inner, method) => {
272                let method = (*method)?;
273                let receiver = self.eval_contract_expr_to_value(checkpoint, inner)?;
274                self.cached_method_result(method, &receiver)
275            }
276            ContractExpr::ConstParam { index, .. } => match checkpoint {
277                Some(checkpoint) => self.instantiate_callsite_const(checkpoint, *index),
278                None => self.const_param_term(*index),
279            },
280            _ => None,
281        }
282    }
283
284    pub(crate) fn eval_contract_expr_to_value(
285        &self,
286        checkpoint: Option<&Checkpoint<'tcx>>,
287        expr: &ContractExpr<'tcx>,
288    ) -> Option<VmValue<'z3, 'tcx>> {
289        match expr {
290            ContractExpr::Place(cp) => {
291                if cp.projections.is_empty() {
292                    return match cp.base {
293                        PlaceBase::Return => self.local_value(Local::from_usize(0)).cloned(),
294                        PlaceBase::Arg(n) => {
295                            checkpoint?.args.get(n).map(|op| self.value_of_operand(op))
296                        }
297                        PlaceBase::Local(n) => {
298                            let ck = checkpoint?;
299                            if let Some(op) = self.callsite_operand_for_local(ck, n) {
300                                return Some(self.value_of_operand(op));
301                            }
302                            self.local_value(Local::from_usize(n)).cloned()
303                        }
304                    };
305                }
306                let base_local = match cp.base {
307                    PlaceBase::Return => Local::from_usize(0),
308                    PlaceBase::Arg(n) => {
309                        let op = checkpoint?.args.get(n)?;
310                        match op {
311                            Operand::Copy(p) | Operand::Move(p) => p.local,
312                            _ => return None,
313                        }
314                    }
315                    PlaceBase::Local(n) => Local::from_usize(n),
316                };
317                let field_path = cp.plain_field_path()?;
318                self.field_value(base_local, &field_path).cloned()
319            }
320            _ => None,
321        }
322    }
323
324    fn eval_contract_place(
325        &self,
326        checkpoint: Option<&Checkpoint<'tcx>>,
327        cp: &crate::contract::ContractPlace,
328    ) -> Option<Int<'z3>> {
329        let field_path = cp.plain_field_path()?;
330
331        let base_local: Option<Local> = match cp.base {
332            PlaceBase::Return => Some(Local::from_usize(0)),
333            PlaceBase::Arg(n) => {
334                if field_path.is_empty() {
335                    return checkpoint.and_then(|ck| {
336                        let op = ck.args.get(n)?;
337                        self.eval_contract_operand(op)
338                    });
339                }
340                checkpoint
341                    .and_then(|ck| ck.args.get(n))
342                    .and_then(|op| match op {
343                        Operand::Copy(p) | Operand::Move(p) => Some(p.local),
344                        _ => None,
345                    })
346            }
347            PlaceBase::Local(n) => {
348                if field_path.is_empty()
349                    && let Some(ck) = checkpoint
350                    && let Some(op) = self.callsite_operand_for_local(ck, n)
351                    && let Some(v) = self.eval_contract_operand(op)
352                {
353                    return Some(v);
354                }
355                Some(Local::from_usize(n))
356            }
357        };
358
359        let local = base_local?;
360        if field_path.is_empty() {
361            self.local_value(local).map(|v| v.z3_term.clone())
362        } else {
363            self.field_value(local, &field_path)
364                .map(|v| v.z3_term.clone())
365        }
366    }
367
368    fn eval_contract_operand(&self, op: &Operand<'tcx>) -> Option<Int<'z3>> {
369        match op {
370            Operand::Constant(c) => {
371                let const_text = format!("{:?}", c.const_);
372                let typing_env = rustc_middle::ty::TypingEnv::fully_monomorphized();
373                if let Ok(val) = c.const_.eval(self.tcx, typing_env, rustc_span::DUMMY_SP)
374                    && let Some(scalar) = val.try_to_scalar_int()
375                {
376                    let bits = scalar.to_bits(scalar.size());
377                    if bits != 0
378                        || !(const_text.contains("AlignOf")
379                            || const_text.contains("SizeOf")
380                            || const_text.contains("min_align_of")
381                            || const_text.contains("min_size_of"))
382                    {
383                        return self.scalar_bits_term(c.const_.ty(), bits);
384                    }
385                }
386                Some(
387                    mir_utils::const_int_from_debug(&const_text)
388                        .map(|v| Int::from_u64(self.z3_ctx, v))
389                        .unwrap_or_else(|| self.symbolic_const_term(&c.const_)),
390                )
391            }
392            Operand::Copy(p) | Operand::Move(p) if p.projection.is_empty() => {
393                self.local_value(p.local).map(|v| v.z3_term.clone())
394            }
395            _ => None,
396        }
397    }
398
399    fn try_iter_len_from_fields(
400        &self,
401        checkpoint: &Checkpoint<'tcx>,
402        expr: &ContractExpr<'tcx>,
403    ) -> Option<Int<'z3>> {
404        let ContractExpr::Place(cp) = expr else {
405            return None;
406        };
407        let op: &Operand<'tcx> = match cp.base {
408            PlaceBase::Arg(n) => checkpoint.args.get(n)?,
409            PlaceBase::Local(n) => {
410                let callee = checkpoint.callee?;
411                let idx = mir_utils::callee_param_index_for_local(self.tcx, callee, n)?;
412                checkpoint.args.get(idx)?
413            }
414            _ => return None,
415        };
416        let place: &Place<'tcx> = match op {
417            Operand::Copy(p) | Operand::Move(p) => p,
418            _ => return None,
419        };
420        let local = place.local;
421        let local_val = self.local_value(local)?;
422        if !self.is_iter_ref(local_val) {
423            return None;
424        }
425        if let (Some(ptr), Some(end)) =
426            (self.field_value(local, &[0]), self.field_value(local, &[1]))
427            && let Some(len) = self.iter_len_from_ptrs(ptr, end)
428        {
429            return Some(len);
430        }
431        let target_alloc = local_val.provenance_alloc_id()?;
432        for (scan_local, scan_val) in self.all_local_values() {
433            if scan_val.provenance_alloc_id() != Some(target_alloc) {
434                continue;
435            }
436            if let (Some(ptr), Some(end)) = (
437                self.field_value(scan_local, &[0]),
438                self.field_value(scan_local, &[1]),
439            ) && let Some(len) = self.iter_len_from_ptrs(ptr, end)
440            {
441                return Some(len);
442            }
443        }
444        None
445    }
446
447
448}