Skip to main content

rapx/vm/mir_rules/
terminator.rs

1use rustc_middle::mir::{
2    BasicBlock, Body, Operand, Place, Rvalue, StatementKind, SwitchTargets, TerminatorKind,
3};
4use rustc_middle::ty::{Ty, TyCtxt, TyKind};
5use z3::ast::{Ast, Int};
6
7use super::super::state::{ValueSource, VmExecutor};
8use super::RuleFlow;
9use crate::util::def_use::PlaceKey;
10use crate::util::mir_utils;
11use crate::contract::{PropertyKind, type_invariants::has_owner_ptr_invariant};
12
13/// The `IS_ZST` fold selects an equivalent path without asserting its guard.
14pub(crate) fn forced_inline_switch_target<'z3, 'tcx>(
15    state: &VmExecutor<'z3, 'tcx>,
16    body: &Body<'tcx>,
17    discr: &Operand<'tcx>,
18    targets: &SwitchTargets,
19) -> Option<BasicBlock> {
20    let value = inline_switch_discr_const(state, body, discr)?;
21    Some(
22        targets
23            .iter()
24            .find(|(candidate, _)| *candidate == value as u128)
25            .map(|(_, target)| target)
26            .unwrap_or_else(|| targets.otherwise()),
27    )
28}
29
30fn inline_switch_discr_const<'z3, 'tcx>(
31    state: &VmExecutor<'z3, 'tcx>,
32    body: &Body<'tcx>,
33    discr: &Operand<'tcx>,
34) -> Option<u64> {
35    if let Some(value) = mir_utils::operand_const_u64(discr) {
36        return Some(value);
37    }
38    if let Operand::RuntimeChecks(_) = discr {
39        return Some(0);
40    }
41    if let Operand::Constant(constant) = discr
42        && let rustc_middle::mir::Const::Unevaluated(uneval, _) = constant.const_
43        && mir_utils::is_sized_type_property(state.tcx, uneval.def, "IS_ZST")
44    {
45        return Some(0);
46    }
47    let (Operand::Copy(place) | Operand::Move(place)) = discr else {
48        return None;
49    };
50    if place.local.as_usize() <= body.arg_count {
51        return None;
52    }
53    let mut definition_seen = false;
54    let mut folded = None;
55    for block in body.basic_blocks.iter() {
56        for statement in &block.statements {
57            let StatementKind::Assign(assign) = &statement.kind else {
58                continue;
59            };
60            let (dest, rvalue) = &**assign;
61            if dest != place {
62                continue;
63            }
64            if definition_seen {
65                return None;
66            }
67            definition_seen = true;
68            folded = mir_utils::rvalue_runtime_checks_value(rvalue);
69            if folded.is_none()
70                && let Rvalue::Use(Operand::Constant(constant), ..) = rvalue
71                && let rustc_middle::mir::Const::Unevaluated(uneval, _) = constant.const_
72                && mir_utils::is_sized_type_property(state.tcx, uneval.def, "IS_ZST")
73            {
74                folded = Some(0);
75            }
76        }
77        let terminator = block.terminator();
78        if let TerminatorKind::Call {
79            func, destination, ..
80        } = &terminator.kind
81            && destination == place
82        {
83            if definition_seen {
84                return None;
85            }
86            definition_seen = true;
87            folded = mir_utils::dep_callee_def_id(func)
88                .filter(|callee| crate::def_ids::other_api::is_ub_check(state.tcx, *callee))
89                .map(|_| 0);
90        }
91    }
92    folded
93}
94
95pub(crate) fn exec_switch_int<'z3, 'tcx>(
96    state: &mut VmExecutor<'z3, 'tcx>,
97    discr: &Operand<'tcx>,
98    targets: &SwitchTargets,
99    switch_succ: Option<BasicBlock>,
100) -> RuleFlow {
101    let discr_val = state.value_of_operand(discr);
102    let discr_ty = discr.ty(&state.body().local_decls, state.tcx);
103    let known_value = match &discr_val.source {
104        ValueSource::Comparison { cond, .. } => cond.simplify().as_bool().map(u64::from),
105        ValueSource::CallsiteConst | ValueSource::KnownDiscriminant(_) => {
106            discr_val.z3_term.simplify().as_u64()
107        }
108        _ => None,
109    };
110    if !state.path_state.diagnostics.is_unsupported()
111        && !state.path_state.diagnostics.has_incomplete_inline_branch()
112        && let Some(value) = known_value
113        && let Some(chosen) = switch_succ
114    {
115        let actual = targets
116            .iter()
117            .find(|(candidate, _)| *candidate == value as u128)
118            .map(|(_, target)| target)
119            .unwrap_or_else(|| targets.otherwise());
120        if actual != chosen {
121            return RuleFlow::Pruned;
122        }
123    }
124    if VmExecutor::term_involves(&state.path_state.inline.opaque_intrinsic_terms, &discr_val.z3_term) {
125        state.record_opaque_control_flow("SwitchInt");
126    }
127
128    // If the discriminator is a comparison result, record the direct boolean
129    // condition alongside the ite-encoded `discr == value` fact, so the SMT
130    // solver can reason about `offset <= len` directly.
131    let cmp_cond = discr_val.bool_cond().cloned();
132
133    if let Some(chosen) = switch_succ {
134        for (value, target) in targets.iter() {
135            if target == chosen {
136                let Some(val_term) = state.scalar_bits_term(discr_ty, value) else {
137                    state.record_unsupported("SwitchInt target width");
138                    return RuleFlow::Continue;
139                };
140                state.path_state
141                    .constraints
142                    .assertions
143                    .push(discr_val.z3_term._eq(&val_term));
144                if value != 0 {
145                    if let Some(ref cond) = cmp_cond {
146                        state.path_state.constraints.assertions.push(cond.clone());
147                    }
148                    state.infer_switch_guard(discr);
149                } else if let Some(ref cond) = cmp_cond {
150                    state.path_state.constraints.assertions.push(cond.not());
151                }
152                return RuleFlow::Continue;
153            }
154        }
155        if targets.otherwise() == chosen {
156            for (value, _) in targets.iter() {
157                let Some(val_term) = state.scalar_bits_term(discr_ty, value) else {
158                    state.record_unsupported("SwitchInt target width");
159                    return RuleFlow::Continue;
160                };
161                state.path_state
162                    .constraints
163                    .assertions
164                    .push(discr_val.z3_term._eq(&val_term).not());
165            }
166            if let Some(ref cond) = cmp_cond {
167                // For a boolean discriminator, `otherwise` means the comparison
168                // result is *not* any explicit value:
169                //   - targets include 0 → `discr != 0` → comparison true;
170                //   - targets include 1 → `discr != 1` → comparison false.
171                if targets.iter().any(|(v, _)| v == 0) {
172                    state.path_state.constraints.assertions.push(cond.clone());
173                } else if targets.iter().any(|(v, _)| v == 1) {
174                    state.path_state.constraints.assertions.push(cond.not());
175                }
176            }
177        }
178    }
179    RuleFlow::Continue
180}
181
182pub(crate) fn exec_assert<'z3, 'tcx>(
183    state: &mut VmExecutor<'z3, 'tcx>,
184    cond: &Operand<'tcx>,
185    expected: bool,
186) {
187    let cond_val = state.value_of_operand(cond);
188    if VmExecutor::term_involves(&state.path_state.inline.opaque_intrinsic_terms, &cond_val.z3_term) {
189        state.record_opaque_control_flow("Assert");
190    }
191    // If the asserted operand is a comparison result, record the direct boolean
192    // condition (`idx < len`) alongside the ite-encoded fact, so the SMT solver
193    // can unfold it (mirrors `exec_switchint`).
194    let cmp_cond = cond_val.bool_cond().cloned();
195    let zero = Int::from_u64(state.z3_ctx, 0);
196    if expected {
197        state.path_state
198            .constraints
199            .assertions
200            .push(cond_val.z3_term._eq(&zero).not());
201        if let Some(c) = &cmp_cond {
202            state.path_state.constraints.assertions.push(c.clone());
203        }
204    } else {
205        state.path_state
206            .constraints
207            .assertions
208            .push(cond_val.z3_term._eq(&zero));
209        if let Some(c) = &cmp_cond {
210            state.path_state.constraints.assertions.push(c.not());
211        }
212    }
213
214    state.infer_guard_non_null(cond, expected);
215    // Infer alignment from == 0 guards on Rem expressions
216    state.infer_guard_align(cond, expected);
217}
218
219/// Execute a drop and report whether it marked the container's data allocation dead.
220pub(crate) fn exec_drop<'z3, 'tcx>(state: &mut VmExecutor<'z3, 'tcx>, place: &Place<'tcx>) -> bool {
221    let mut dropped_data = false;
222    if let Some(alloc_id) = state.path_state.current_frame.local_alloc.get(&place.local).copied() {
223        let is_param = place.local.as_usize() <= state.body().arg_count;
224        let owner = if is_param {
225            state.path_state.caller_frames.last().and_then(|saved| {
226                let source = saved
227                    .postcondition_args
228                    .get(place.local.as_usize().checked_sub(1)?)?
229                    .as_ref()?;
230                let header = *saved.frame.local_alloc.get(source)?;
231                let ty = state.frame_local_ty(&saved.frame, *source);
232                Some((header, ty, *source))
233            })
234        } else {
235            Some((alloc_id, state.body().local_decls[place.local].ty, place.local))
236        };
237        if let Some((header, ty, source)) = owner {
238            if !is_trivial_raw_pointer_wrapper(state.tcx, ty)
239                && let Some(data_id) = state.container_data_alloc(header, ty)
240            {
241                let ptr_path = state.container_ptr_field(ty);
242                let shared_owner = ptr_path.as_deref().is_some_and(|path| {
243                    has_owner_ptr_invariant(state.tcx, ty, path, PropertyKind::Allocated)
244                        && !has_owner_ptr_invariant(state.tcx, ty, path, PropertyKind::Owning)
245                });
246                if shared_owner {
247                    state.alloc_mut(data_id).facts.drop_may_free = true;
248                    if let Some(path) = ptr_path
249                        && let Some(mut field) = state.load_value(header, ty, &path).cloned()
250                    {
251                        field.provenance = None;
252                        state.store_value(header, ty, path, field);
253                    }
254                    state.alloc_mut(header).facts.dead = true;
255                } else if !is_param {
256                    state.record_memory_drop(data_id, source);
257                    dropped_data = true;
258                }
259            }
260        }
261        state.alloc_mut(alloc_id).facts.dead = true;
262        if place.projection.is_empty() {
263            state.invalidate_owner_field(place.local);
264        }
265    }
266    dropped_data
267}
268
269/// A wrapper with only raw pointers and an empty destructor does not own its pointee.
270fn is_trivial_raw_pointer_wrapper<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> bool {
271    let TyKind::Adt(adt, args) = ty.kind() else {
272        return false;
273    };
274    if !adt.is_struct() || adt.non_enum_variant().fields.iter().any(|field| {
275        let ty = mir_utils::field_ty(tcx, field, args);
276        !matches!(ty.kind(), TyKind::RawPtr(..))
277            && !matches!(ty.kind(), TyKind::Adt(inner, _) if matches!(tcx.crate_name(inner.did().krate).as_str(), "core" | "std")
278                && tcx.item_name(inner.did()).as_str() == "PhantomData")
279    }) {
280        return false;
281    }
282    let Some(dtor) = tcx.adt_destructor(adt.did()) else {
283        return true;
284    };
285    tcx.optimized_mir(dtor.did).basic_blocks.iter().all(|block| {
286        block.statements.iter().all(|stmt| match &stmt.kind {
287            StatementKind::StorageLive(..) | StatementKind::StorageDead(..) | StatementKind::Nop => true,
288            StatementKind::Assign(assign) => {
289                let (place, value) = &**assign;
290                place.as_local().is_some_and(|local| local.as_usize() == 0)
291                    && matches!(value, Rvalue::Use(Operand::Constant(constant), _) if constant.const_.ty().is_unit())
292            }
293            _ => false,
294        }) && matches!(block.terminator().kind, TerminatorKind::Return | TerminatorKind::Goto { .. })
295    })
296}
297
298impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
299    /// The `(lhs, rhs, op)` of the binary-op/comparison source recorded on the
300    /// value bound to `pk`'s local, if any.
301    fn op_source_of(
302        &self,
303        pk: &PlaceKey,
304    ) -> Option<(Option<PlaceKey>, Option<PlaceKey>, rustc_middle::mir::BinOp)> {
305        let local = pk.local()?;
306        let val = self.local_value(local)?;
307        val.source
308            .operands()
309            .map(|(l, r, o)| (l.clone(), r.clone(), o))
310    }
311
312    fn operand_place_key(op: &Operand<'tcx>) -> Option<PlaceKey> {
313        match op {
314            Operand::Copy(p) | Operand::Move(p) => Some(PlaceKey::from_mir_place(p)),
315            _ => None,
316        }
317    }
318
319    /// Infer alignment constraints from guards of the form `(x % n) == 0`.
320    fn infer_guard_align(&mut self, cond: &Operand<'tcx>, expected: bool) {
321        if !expected {
322            return;
323        }
324        let Some(cond_pk) = Self::operand_place_key(cond) else {
325            return;
326        };
327
328        if let Some((lhs_pk, rhs_pk, _)) = self.op_source_of(&cond_pk) {
329            let inner_pk = match (&lhs_pk, &rhs_pk) {
330                (Some(pk), None) => pk.clone(),
331                (None, Some(pk)) => pk.clone(),
332                _ => return,
333            };
334            if let Some((div_lhs, div_rhs, inner_op)) = self.op_source_of(&inner_pk) {
335                match inner_op {
336                    // `x % n == 0`: div_rhs is the concrete divisor constant.
337                    rustc_middle::mir::BinOp::Rem => {
338                        if let Some(divisor) = resolve_u64_from_place_key(&div_rhs, self)
339                            && divisor > 0
340                        {
341                            self.mark_align_n(&div_lhs, Int::from_u64(self.z3_ctx, divisor));
342                        }
343                    }
344                    // `x & (align-1) == 0`: the mask is `align-1` (symbolic for a
345                    // generic `T`), so `align = mask + 1`.
346                    rustc_middle::mir::BinOp::BitAnd => {
347                        if let Some(rhs_local) = div_rhs.as_ref().and_then(|pk| pk.local())
348                            && let Some(rhs_val) = self.local_value(rhs_local)
349                        {
350                            let one = Int::from_u64(self.z3_ctx, 1);
351                            let align = Int::add(self.z3_ctx, &[&rhs_val.z3_term, &one]);
352                            self.mark_align_n(&div_lhs, align);
353                        }
354                    }
355                    _ => {}
356                }
357            }
358        }
359    }
360
361    fn mark_align_n(&mut self, src_pk: &Option<PlaceKey>, align: Int<'z3>) {
362        if let Some(src_pk) = src_pk
363            && let Some(local) = src_pk.local()
364            && let Some(mut val) = self.local_value(local).cloned()
365        {
366            val.facts.align_n = Some(align);
367            self.set_local(local, val);
368        }
369    }
370
371    /// Infer non_null invariants from branch guards.
372    fn infer_guard_non_null(&mut self, cond: &Operand<'tcx>, expected: bool) {
373        if !expected {
374            return;
375        }
376        let Some(cond_pk) = Self::operand_place_key(cond) else {
377            return;
378        };
379
380        // Check if cond was defined by BinaryOp(Ne, (ptr, 0)) or similar:
381        // mark the non-constant side as non-null.  Only `Ne` guards imply
382        // non-nullness; an `Eq` guard (`assert (addr & mask) == 0`, the
383        // alignment check) means the value *is* zero, not non-null.
384        if let Some((lhs_pk, rhs_pk, op)) = self.op_source_of(&cond_pk) {
385            if op != rustc_middle::mir::BinOp::Ne {
386                return;
387            }
388            if rhs_pk.is_none() {
389                self.mark_guard_pointer(&lhs_pk, &None);
390            }
391            if lhs_pk.is_none() {
392                self.mark_guard_pointer(&rhs_pk, &None);
393            }
394        }
395    }
396
397    /// Infer non_null from SwitchInt discriminant.
398    fn infer_switch_guard(&mut self, discr: &Operand<'tcx>) {
399        let Some(pk) = Self::operand_place_key(discr) else {
400            return;
401        };
402        if let Some((lhs_pk, rhs_pk, _)) = self.op_source_of(&pk) {
403            self.mark_guard_pointer(&lhs_pk, &rhs_pk);
404        }
405    }
406
407    fn mark_guard_pointer(&mut self, lhs: &Option<PlaceKey>, rhs: &Option<PlaceKey>) {
408        for pk in [lhs, rhs].into_iter().flatten() {
409            if let Some(local) = pk.local()
410                && let Some(mut val) = self.local_value(local).cloned()
411            {
412                val.facts.non_null = true;
413                self.set_local(local, val);
414            }
415        }
416    }
417}
418
419fn resolve_u64_from_place_key<'z3, 'tcx>(
420    pk: &Option<PlaceKey>,
421    state: &VmExecutor<'z3, 'tcx>,
422) -> Option<u64> {
423    let pk = pk.as_ref()?;
424    let local = pk.local()?;
425    let val = state.local_value(local)?;
426    val.z3_term.as_u64()
427}