Skip to main content

rapx/verify/vm/
query.rs

1//! Read-only queries over the symbolic VM state used by property checks.
2
3use crate::contract::{ContractExpr, ContractPlace, ContractProjection, PlaceBase, Property};
4use crate::def_ids::type_ids;
5use crate::util::mir_utils;
6use crate::verify::checkpoint::Checkpoint;
7use crate::vm::state::{AllocId, OffsetKind, VmExecutor, VmValue};
8use rustc_middle::{
9    mir::{Local, Operand},
10    ty::{Ty, TyKind},
11};
12use z3::ast::{Ast, Int};
13
14impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
15    /// Resolve a property's target using the checkpoint's call arguments.
16    pub(crate) fn callsite_contract_target_value(&self, args: &[Operand<'tcx>], property: &Property<'tcx>) -> Option<VmValue<'z3, 'tcx>> {
17        let place = match property.args().first()?.expr()? {
18            ContractExpr::Const(index) => ContractPlace { base: PlaceBase::Arg(usize::try_from(*index).ok()?), projections: vec![] },
19            ContractExpr::Place(place) => place.clone(),
20            ContractExpr::IndexAccess { slice, .. } => match slice.as_ref() {
21                ContractExpr::Place(place) => place.clone(),
22                _ => return None,
23            },
24            _ => return None,
25        };
26        self.callsite_contract_place_value(args, &place)
27    }
28
29    fn callsite_contract_place_value(&self, args: &[Operand<'tcx>], place: &ContractPlace) -> Option<VmValue<'z3, 'tcx>> {
30        if place.projections.is_empty() {
31            return match place.base {
32                PlaceBase::Return => self.local_value(Local::from_usize(0)).cloned(),
33                PlaceBase::Arg(index) => args.get(index).map(|arg| self.value_of_operand(arg)),
34                PlaceBase::Local(index) => self.local_value(Local::from_usize(index)).cloned(),
35            };
36        }
37        let local = match place.base {
38            PlaceBase::Return => Local::from_usize(0),
39            PlaceBase::Arg(index) => match args.get(index)? {
40                Operand::Copy(operand_place) | Operand::Move(operand_place) => operand_place.local,
41                _ => return None,
42            },
43            PlaceBase::Local(index) => Local::from_usize(index),
44        };
45        let mut fields = Vec::new();
46        for projection in &place.projections {
47            match projection {
48                ContractProjection::Field { index } => fields.push(*index),
49                ContractProjection::Downcast { variant_index } => {
50                    let base_value = self.field_value(local, &fields).cloned().or_else(|| self.local_value(local).cloned())?;
51                    let enum_ty = if fields.is_empty() {
52                        base_value.ty
53                    } else {
54                        let root_ty = match place.base {
55                            PlaceBase::Arg(index) => match args.get(index)? {
56                                Operand::Copy(operand_place) | Operand::Move(operand_place) => operand_place.ty(self.body(), self.tcx).ty,
57                                _ => return None,
58                            },
59                            _ => self.body().local_decls[local].ty,
60                        };
61                        mir_utils::projected_field_ty(self.tcx, root_ty, &fields).unwrap_or(base_value.ty)
62                    };
63                    let inner_ty = match enum_ty.kind() {
64                        TyKind::Adt(adt, substs) if adt.is_enum() => {
65                            let variant = &adt.variants()[rustc_abi::VariantIdx::from_usize(*variant_index)];
66                            if variant.fields.is_empty() {
67                                None
68                            } else {
69                                Some(mir_utils::field_ty(self.tcx, &variant.fields[rustc_abi::FieldIdx::from_usize(0)], substs))
70                            }
71                        }
72                        _ => None,
73                    }.unwrap_or(base_value.ty);
74                    return Some(VmValue {
75                        z3_term: base_value.z3_term,
76                        ty: inner_ty,
77                        provenance: base_value.provenance,
78                        facts: base_value.facts,
79                        source: base_value.source.field_offset_only(),
80                    });
81                }
82                ContractProjection::ForEach => {
83                    if let Some(value) = self.field_value(local, &fields) {
84                        return Some(value.clone());
85                    }
86                    if let Some(base_value) = self.local_value(local) && base_value.is_pointer() {
87                        return Some(VmValue {
88                            z3_term: base_value.z3_term.clone(),
89                            ty: base_value.ty,
90                            provenance: base_value.provenance.clone(),
91                            facts: base_value.facts.clone(),
92                            source: base_value.source.field_offset_only(),
93                        });
94                    }
95                    return None;
96                }
97            }
98        }
99        if let Some(value) = self.field_value(local, &fields) {
100            return Some(value.clone());
101        }
102        if !fields.is_empty() && local == Local::from_usize(0) {
103            for block in self.body().basic_blocks.iter() {
104                for statement in &block.statements {
105                    if let rustc_middle::mir::StatementKind::Assign(assign) = &statement.kind {
106                        let (target, value) = &**assign;
107                        if let rustc_middle::mir::Rvalue::Aggregate(_, operands) = value
108                            && target.local == local
109                            && let Some(operand) = operands.get(rustc_abi::FieldIdx::from_usize(fields[0]))
110                            && fields.len() == 1
111                        {
112                            return Some(self.value_of_operand(operand));
113                        }
114                    }
115                }
116            }
117        }
118        if let Some(base_value) = self.local_value(local) && let Some(provenance) = &base_value.provenance {
119            return Some(VmValue {
120                z3_term: base_value.z3_term.clone(),
121                ty: base_value.ty,
122                provenance: Some(provenance.clone()),
123                facts: base_value.facts.clone(),
124                source: base_value.source.field_offset_only(),
125            });
126        }
127        None
128    }
129
130    pub(crate) fn has_bounded_object_span(
131        &self,
132        alloc_id: AllocId,
133        value: &VmValue<'z3, 'tcx>,
134        ty: Ty<'tcx>,
135    ) -> bool {
136        self.bounded_span(value, ty)
137            .is_some_and(|span| self.alloc(alloc_id).facts.bounded_spans.contains(&span))
138    }
139
140    pub(crate) fn has_bounded_range(
141        &self,
142        alloc_id: AllocId,
143        address: &Int<'z3>,
144        bytes: &Int<'z3>,
145    ) -> bool {
146        let ranges = &self.alloc(alloc_id).facts.bounded_ranges;
147        if ranges.is_empty() {
148            return false;
149        }
150        let solver = z3::Solver::new(self.z3_ctx);
151        self.assert_path_constraints(&solver);
152        let end = Int::add(self.z3_ctx, &[address, bytes]);
153        ranges.iter().any(|(start, size)| {
154            let limit = Int::add(self.z3_ctx, &[start, size]);
155            let covered = z3::ast::Bool::and(
156                self.z3_ctx,
157                &[
158                    &address.ge(start),
159                    &address.le(&limit),
160                    &end.ge(start),
161                    &end.le(&limit),
162                ],
163            );
164            solver.push();
165            // A recorded byte range has nonnegative length, including when
166            // its usize count is no longer a live local in this frame.
167            solver.assert(&size.ge(&Int::from_u64(self.z3_ctx, 0)));
168            solver.assert(&covered.not());
169            let proved = solver.check() == z3::SatResult::Unsat;
170            solver.pop(1);
171            proved
172        })
173    }
174
175    pub(crate) fn callsite_operand_for_local<'a>(
176        &self,
177        checkpoint: &'a Checkpoint<'tcx>,
178        local: usize,
179    ) -> Option<&'a Operand<'tcx>> {
180        let callee = checkpoint.callee?;
181        let index = mir_utils::callee_param_index_for_local(self.tcx, callee, local)?;
182        checkpoint.args.get(index)
183    }
184
185    /// Bind a contract place to a term at this checkpoint. A callee parameter
186    /// local refers to its callsite operand when one is available.
187    pub(crate) fn contract_place_term_at(
188        &self,
189        checkpoint: &Checkpoint<'tcx>,
190        place: &ContractPlace,
191    ) -> Option<Int<'z3>> {
192        if !place.projections.is_empty() {
193            let fields = place.plain_field_path()?;
194            let local = match place.base {
195                PlaceBase::Arg(index) => checkpoint.args.get(index)?.place()?.local,
196                PlaceBase::Local(index) => self
197                    .callsite_operand_for_local(checkpoint, index)
198                    .and_then(|operand| operand.place())
199                    .map(|place| place.local)
200                    .unwrap_or(Local::from_usize(index)),
201                PlaceBase::Return => Local::from_usize(0),
202            };
203            return self
204                .field_value(local, &fields)
205                .map(|value| value.z3_term.clone());
206        }
207        match place.base {
208            PlaceBase::Arg(index) => checkpoint
209                .args
210                .get(index)
211                .map(|operand| self.value_of_operand(operand).z3_term),
212            PlaceBase::Local(index) => {
213                let operand = self.callsite_operand_for_local(checkpoint, index);
214                if let Some(operand) = operand {
215                    Some(self.value_of_operand(operand).z3_term)
216                } else {
217                    self.local_value(Local::from_usize(index))
218                        .map(|value| value.z3_term.clone())
219                }
220            }
221            PlaceBase::Return => None,
222        }
223    }
224
225    /// Penetrate a reference/raw-pointer target down to the owned heap behind
226    /// it.  A target like `&mut ManuallyDrop<Box<T>>` or `*mut Box<T>` carries
227    /// the *stack* provenance of the referent; the properties that matter
228    /// (`Allocated`/`Owning`/`ValidPtr`) concern the heap object inside, so
229    /// resolve through the referent local's owned heap field.
230    pub(crate) fn resolve_pointer_provenance(
231        &self,
232        mut value: VmValue<'z3, 'tcx>,
233    ) -> VmValue<'z3, 'tcx> {
234        if matches!(
235            value.ty.kind(),
236            rustc_middle::ty::TyKind::Ref(..) | rustc_middle::ty::TyKind::RawPtr(..)
237        ) && let Some(owner) = self.find_local_by_address(&value.z3_term)
238            && let Some(heap_field) = self.owner_ptr_field(owner)
239            && heap_field.is_pointer()
240        {
241            value.z3_term = heap_field.z3_term.clone();
242            value.provenance = heap_field.provenance.clone();
243            value.facts = heap_field.facts.clone();
244        }
245        value
246    }
247
248    /// Whether `value` is known to be aligned: either `align_n` carries a
249    /// concrete alignment, or the value sits at the base of an allocation whose
250    /// `align` is not 1.
251    pub(crate) fn is_value_aligned(&self, value: &VmValue<'z3, 'tcx>) -> bool {
252        value.facts.align_n.is_some()
253            || value.provenance.as_ref().is_some_and(|p| {
254                p.offset_kind.is_none()
255                    && self.alloc(p.alloc_id).align.simplify().as_u64() != Some(1)
256            })
257    }
258
259    /// Whether `value` is a `MaybeUninit`-typed pointer access into `alloc_id`.
260    ///
261    /// `assume_init_drop` / `as_mut_ptr` (and friends) legitimately consume an
262    /// initialized element from storage that may be going out of scope, so the
263    /// `Init`/`Allocated` requirement concerns the write, not the allocation's
264    /// live/dead flag.
265    pub(crate) fn is_maybe_uninit_ptr(
266        &self,
267        value: &VmValue<'z3, 'tcx>,
268        alloc_id: AllocId,
269    ) -> bool {
270        value.facts.init
271            && value.facts.non_null
272            && self.is_value_aligned(value)
273            && (matches!(value.ty.kind(), TyKind::RawPtr(..))
274                || matches!(value.ty.kind(), TyKind::Ref(_, inner, _)
275                    if matches!(inner.kind(), TyKind::Adt(adt, _)
276                        if type_ids::is_maybe_uninit_type(adt.did()))))
277            && {
278                let a = self.alloc(alloc_id);
279                !a.is_external()
280                    && a.element_ty.as_ty().is_some_and(|ty| {
281                        if let TyKind::Adt(adt, _) = ty.kind() {
282                            type_ids::is_maybe_uninit_type(adt.did())
283                        } else {
284                            false
285                        }
286                    })
287            }
288    }
289
290    /// Element count of one object when the access is to an unsized `[T]`:
291    /// the slice length from the pointer's metadata. An unknown length stays
292    /// unknown. Other objects return `None`.
293    pub(crate) fn unsized_slice_len(
294        &self,
295        value: &VmValue<'z3, 'tcx>,
296        required_ty: Option<Ty<'tcx>>,
297    ) -> Option<Int<'z3>> {
298        let accessed = required_ty
299            .filter(|ty| !matches!(ty.kind(), TyKind::Alias(..)))
300            .or_else(|| mir_utils::pointee_ty(value.ty))?;
301        if !matches!(accessed.kind(), TyKind::Slice(_)) {
302            return None;
303        }
304        Some(
305            self.slice_len_from_value(value)
306                .unwrap_or_else(|| self.fresh_int("slice_access_len")),
307        )
308    }
309
310    /// Byte span requested by a pointer property, using the VM's element-size
311    /// model for concrete and generic pointee types.
312    pub(crate) fn access_bytes(
313        &self,
314        value: &VmValue<'z3, 'tcx>,
315        required_ty: Option<Ty<'tcx>>,
316        count: Int<'z3>,
317    ) -> Int<'z3> {
318        let elem_ty = required_ty
319            .filter(|ty| self.size_of_ty(*ty) > 0)
320            .or_else(|| {
321                mir_utils::pointee_ty(value.ty).map(|ty| match ty.kind() {
322                    TyKind::Slice(elem) | TyKind::Array(elem, _) => *elem,
323                    _ => ty,
324                })
325            });
326        let elem_size = elem_ty
327            .map(|ty| self.size_sym_read(ty))
328            .unwrap_or_else(|| Int::from_u64(self.z3_ctx, 1));
329        let count = match self.unsized_slice_len(value, required_ty) {
330            Some(len) => Int::mul(self.z3_ctx, &[&count, &len]),
331            None => count,
332        };
333        if let (Some(elem), Some(count)) =
334            (elem_size.simplify().as_u64(), count.simplify().as_u64())
335        {
336            if let Some(bytes) = elem.max(1).checked_mul(count.max(1)) {
337                return Int::from_u64(self.z3_ctx, bytes);
338            }
339        }
340        Int::mul(self.z3_ctx, &[&elem_size, &count])
341    }
342
343    /// Whether this atom's target or a checkpoint argument depends on an
344    /// unconstrained value introduced by incomplete inlining.
345    pub(crate) fn atom_depends_on_inline_terms(
346        &self,
347        checkpoint: &Checkpoint<'tcx>,
348        property: &Property<'tcx>,
349        terms: &rustc_hash::FxHashSet<Int<'z3>>,
350    ) -> bool {
351        if terms.is_empty() {
352            return false;
353        }
354        for operand in &checkpoint.args {
355            if self.value_involves_terms(terms, &self.value_of_operand(operand)) {
356                return true;
357            }
358        }
359        if let Some(value) = self.callsite_contract_target_value(&checkpoint.args, property)
360            && self.value_involves_terms(terms, &value)
361        {
362            return true;
363        }
364        false
365    }
366
367    fn value_involves_terms(
368        &self,
369        terms: &rustc_hash::FxHashSet<Int<'z3>>,
370        value: &VmValue<'z3, 'tcx>,
371    ) -> bool {
372        if VmExecutor::term_involves(terms, &value.z3_term) {
373            return true;
374        }
375        value.provenance.as_ref().is_some_and(|p| {
376            VmExecutor::term_involves(terms, &p.offset)
377                || matches!(
378                    &p.offset_kind,
379                    Some(OffsetKind::Element { index, .. }) if VmExecutor::term_involves(terms, index)
380                )
381        })
382    }
383}