Skip to main content

rapx/vm/
arithmetic.rs

1use rustc_middle::{
2    mir::{BinOp, Local, Operand, UnOp},
3    ty::{Ty, TyKind},
4};
5use z3::ast::{Ast, Bool, Int};
6
7use crate::util::mir_utils;
8
9use super::state::{OffsetKind, Provenance, ValueFacts, ValueSource, VmExecutor, VmValue};
10
11impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
12    /// Inject layout constraints (>= 1) for generic AlignOf/SizeOf constants.
13    pub(crate) fn inject_layout_constraints(
14        &mut self,
15        operand: &Operand<'tcx>,
16        val: &VmValue<'z3, 'tcx>,
17    ) {
18        if let Operand::Constant(constant) = operand {
19            let text = format!("{:?}", constant.const_);
20            if mir_utils::const_int_from_debug(&text).is_none() {
21                let is_align_or_size = text.starts_with("AlignOf(") || text.starts_with("SizeOf(");
22                if is_align_or_size {
23                    let one = Int::from_u64(self.z3_ctx, 1);
24                    self.path_state.constraints.assertions.push(val.z3_term.ge(&one));
25                }
26            }
27        }
28    }
29
30    /// Preserve the divisibility relation of the recursive gcd const
31    /// expression used by slice::align_to_offsets. CTFE leaves its result
32    /// symbolic for generic element sizes.
33    pub(crate) fn try_emit_gcd_divisibility(
34        &mut self,
35        operand: &Operand<'tcx>,
36        val: &VmValue<'z3, 'tcx>,
37    ) {
38        let Operand::Constant(constant) = operand else {
39            return;
40        };
41        let rustc_middle::mir::Const::Unevaluated(uneval, _) = constant.const_ else {
42            return;
43        };
44        let def_name = self.tcx.def_path_str(uneval.def);
45        if !def_name.contains("align_to_offsets::{constant")
46            || !mir_utils::ctfe_mir_available(self.tcx, uneval.def)
47        {
48            return;
49        }
50        let body = self.tcx.mir_for_ctfe(uneval.def);
51        let calls_gcd = body.basic_blocks.iter().any(|bb| {
52            if let rustc_middle::mir::TerminatorKind::Call { func, .. } = &bb.terminator().kind
53                && let Some(did) = mir_utils::dep_callee_def_id(func)
54            {
55                return crate::def_ids::other_api::is_gcd(self.tcx, did);
56            }
57            false
58        });
59        if !calls_gcd || uneval.args.len() < 2 {
60            return;
61        }
62        let a = self.size_sym(uneval.args.type_at(0));
63        let b = self.size_sym(uneval.args.type_at(1));
64        let g = &val.z3_term;
65        let zero = Int::from_u64(self.z3_ctx, 0);
66        self.path_state.constraints.assertions.push(a.rem(g)._eq(&zero));
67        self.path_state.constraints.assertions.push(b.rem(g)._eq(&zero));
68        // State the lcm identity directly because Z3 may not infer it from
69        // divisibility in nonlinear integer arithmetic.
70        let a_div_g = a.div(g);
71        let b_div_g = b.div(g);
72        let lhs = Int::mul(self.z3_ctx, &[&a_div_g, &b]);
73        let rhs = Int::mul(self.z3_ctx, &[&b_div_g, &a]);
74        self.path_state.constraints.assertions.push(lhs._eq(&rhs));
75    }
76
77    /// `Some(align)` when `align` is non-trivial (≠ 1); `None` for a byte
78    /// alignment, which carries no alignment guarantee.
79    pub(crate) fn non_trivial_align(align: Int<'z3>) -> Option<Int<'z3>> {
80        (align.simplify().as_u64() != Some(1)).then_some(align)
81    }
82
83    /// The provenance allocation's alignment, when it is non-trivial (≠ 1).
84    pub(crate) fn alloc_align_of(&self, val: &VmValue<'z3, 'tcx>) -> Option<Int<'z3>> {
85        val.provenance
86            .as_ref()
87            .map(|p| self.alloc(p.alloc_id).align.clone())
88            .and_then(Self::non_trivial_align)
89    }
90
91    /// Assert the Euclidean division identity and its bounds for `Div`/`Rem`:
92    ///   `lhs == (lhs/rhs)*rhs + lhs%rhs  ∧  lhs%rhs >= 0`
93    /// plus `(lhs/rhs)*rhs <= lhs` directly for robustness.  This lets later
94    /// checks prove `(x/N)*N <= x` and `x%N >= 0`.
95    ///
96    /// `term` must be the *same* Z3 term returned by `eval_binary_op` (the
97    /// quotient), not a separate `lhs.div(rhs)` call, so the axiom constrains
98    /// the term used in subsequent operations.
99    pub(crate) fn emit_div_rem_axioms(
100        &mut self,
101        op: BinOp,
102        term: &Int<'z3>,
103        lhs: &Int<'z3>,
104        rhs: &Int<'z3>,
105    ) {
106        let quot = if matches!(op, BinOp::Div) {
107            term
108        } else {
109            &lhs.div(rhs)
110        };
111        let rem = lhs.rem(rhs);
112        let mul_term = Int::mul(self.z3_ctx, &[quot, rhs]);
113        let sum_term = Int::add(self.z3_ctx, &[&mul_term, &rem]);
114        self.path_state.constraints.assertions.push(lhs._eq(&sum_term));
115        let zero = Int::from_u64(self.z3_ctx, 0);
116        self.path_state.constraints.assertions.push(rem.ge(&zero));
117        if rhs.as_u64().is_none_or(|r| r >= 1) {
118            self.path_state.constraints.assertions.push(rem.lt(rhs));
119        }
120        self.path_state.constraints.assertions.push(rem.le(lhs));
121        self.path_state.constraints.assertions.push(quot.ge(&zero));
122        // Direct inequality: (lhs/rhs)*rhs <= lhs
123        self.path_state.constraints.assertions.push(mul_term.le(lhs));
124        if rhs.as_u64().is_some_and(|r| r >= 2) {
125            let one = Int::from_u64(self.z3_ctx, 1);
126            let qp1 = Int::add(self.z3_ctx, &[quot, &one]);
127            self.path_state.constraints
128                .assertions
129                .push(lhs.ge(&one).implies(&qp1.le(lhs)));
130        } else {
131            if rhs.as_u64().is_some_and(|r| r >= 1) {
132                self.path_state.constraints.assertions.push(quot.le(lhs));
133            }
134        }
135    }
136
137    fn bool_as_int(&self, cond: &Bool<'z3>) -> Int<'z3> {
138        cond.ite(
139            &Int::from_u64(self.z3_ctx, 1),
140            &Int::from_u64(self.z3_ctx, 0),
141        )
142    }
143
144    fn negate(&self, val: &Int<'z3>) -> Int<'z3> {
145        let zero = Int::from_u64(self.z3_ctx, 0);
146        Int::sub(self.z3_ctx, &[&zero, val])
147    }
148
149    pub(crate) fn eval_binary_op(&mut self, op: BinOp, lhs: &Int<'z3>, rhs: &Int<'z3>) -> Int<'z3> {
150        match op {
151            BinOp::Add | BinOp::AddWithOverflow | BinOp::AddUnchecked => {
152                Int::add(self.z3_ctx, &[lhs, rhs])
153            }
154            BinOp::Sub | BinOp::SubWithOverflow | BinOp::SubUnchecked => {
155                // `intrinsics::unchecked_sub(0, n)` lowers to `0 - n`; normalize it
156                // to a unary negation `-n` so `apply_pointer_add`'s single-child
157                // detection recovers the positive count (`ptr.sub(n)`).
158                if lhs.as_u64() == Some(0) {
159                    -rhs.clone()
160                } else {
161                    Int::sub(self.z3_ctx, &[lhs, rhs])
162                }
163            }
164            BinOp::Mul | BinOp::MulWithOverflow | BinOp::MulUnchecked => {
165                // `us_len = (len / ts) * us`: a non-exact division result times
166                // an exact gcd quotient.  Model the product as a fresh symbol
167                // and emit its byte bound `us_len * sizeof_U <= len * sizeof_T`
168                // directly, so the later `from_raw_parts_mut` InBound check
169                // (`us_len * sizeof_U`) stays degree-2 rather than the
170                // degree-3 `div * us * sizeof_U` that Z3's NIA cannot rewrite.
171                if let Some((div_lhs, div_rhs)) = self.path_state.constraints.term_caches.div_roots.get(lhs)
172                    && let Some(us_dividend) = self.path_state.constraints.term_caches.exact_div_roots.get(rhs)
173                    && let Some(ts_dividend) =
174                        self.path_state.constraints.term_caches.exact_div_roots.get(div_rhs)
175                {
176                    let us_len = self.fresh_int("us_len");
177                    self.path_state.constraints
178                        .assertions
179                        .push(us_len._eq(&Int::mul(self.z3_ctx, &[lhs, rhs])));
180                    let byte_len = Int::mul(self.z3_ctx, &[&us_len, ts_dividend]);
181                    let byte_bound = Int::mul(self.z3_ctx, &[div_lhs, us_dividend]);
182                    self.path_state.constraints.assertions.push(byte_len.le(&byte_bound));
183                    return us_len;
184                }
185                Int::mul(self.z3_ctx, &[lhs, rhs])
186            }
187            BinOp::Div => {
188                // An *exact* division (`lhs % rhs == 0` known) is represented as
189                // a fresh variable rather than the `lhs / rhs` term. The caller
190                // still emits the Euclidean identity `lhs == quot*rhs + rem`
191                // (with `rem == 0` from the divisibility), so the fresh variable
192                // satisfies `quot*rhs == lhs` linearly. This avoids the *nested*
193                // division (`x / (b/gcd)`) that Z3's nonlinear solver can't
194                // handle, leaving only degree-2 products that `nlsat` handles
195                // far more reliably. General (any exact division), not a
196                // per-function effect.
197                let zero = Int::from_u64(self.z3_ctx, 0);
198                let exact = self.path_state
199                    .constraints
200                    .assertions
201                    .iter()
202                    .any(|c| *c == lhs.rem(rhs)._eq(&zero));
203                if exact {
204                    let q = self.fresh_int("exact_div");
205                    self.path_state.constraints
206                        .term_caches
207                        .exact_div_roots
208                        .insert(q.clone(), lhs.clone());
209                    q
210                } else {
211                    // A *non-exact* division is likewise a fresh variable (the
212                    // caller's Euclidean identity `lhs == q*rhs + rem` links it
213                    // back), so a later `(len/ts) * us` product stays a degree-2
214                    // product of two symbols instead of a `div` term that Z3's
215                    // nonlinear solver cannot combine with a multiplier.
216                    let q = self.fresh_int("div");
217                    self.path_state.constraints
218                        .term_caches
219                        .div_roots
220                        .insert(q.clone(), (lhs.clone(), rhs.clone()));
221                    q
222                }
223            }
224            BinOp::Rem => lhs.rem(rhs),
225            BinOp::Eq => self.bool_as_int(&lhs._eq(rhs)),
226            BinOp::Ne => self.bool_as_int(&lhs._eq(rhs).not()),
227            BinOp::Lt => self.bool_as_int(&lhs.lt(rhs)),
228            BinOp::Le => self.bool_as_int(&lhs.le(rhs)),
229            BinOp::Gt => self.bool_as_int(&lhs.gt(rhs)),
230            BinOp::Ge => self.bool_as_int(&lhs.ge(rhs)),
231            BinOp::Offset => Int::add(self.z3_ctx, &[lhs, rhs]),
232            BinOp::BitAnd => {
233                let left = lhs.simplify();
234                let right = rhs.simplify();
235                let all_bits = Int::from_i64(self.z3_ctx, -1);
236                if left == all_bits {
237                    return rhs.clone();
238                }
239                if right == all_bits {
240                    return lhs.clone();
241                }
242                if let (Some(left), Some(right)) = (left.as_u64(), right.as_u64()) {
243                    return Int::from_u64(self.z3_ctx, left & right);
244                }
245                let result = self.fresh_int("binop");
246                if let Some(mask) = rhs.simplify().as_u64() {
247                    let zero = Int::from_u64(self.z3_ctx, 0);
248                    if mask == 0 {
249                        self.path_state.constraints.assertions.push(result._eq(&zero));
250                    } else if mask.trailing_zeros() > 0 {
251                        // AND preserves the zero low bits of a constant mask.
252                        let divisor = Int::from_u64(self.z3_ctx, 1_u64 << mask.trailing_zeros());
253                        self.path_state.constraints.assertions.push(result.rem(&divisor)._eq(&zero));
254                    }
255                }
256                // `x & y` lies in `[0, x]` only when `x >= 0`. For example,
257                // `-1 & 1 == 1`; asserting `result <= x` would make a reachable
258                // branch unsatisfiable and could hide an unsafe call.
259                let zero = Int::from_u64(self.z3_ctx, 0);
260                self.path_state.constraints.assertions.push(
261                    lhs.ge(&zero)
262                        .implies(&Bool::and(self.z3_ctx, &[&result.ge(&zero), &result.le(lhs)])),
263                );
264                // A non-negative constant mask also bounds the result in
265                // `[0, mask]`, even when `lhs` is negative.
266                // This lets `(rhs & (BITS - 1)) < BITS` be discharged. The
267                // mask may be a folded expression (`SubWithOverflow(BITS, 1)`),
268                // so `simplify()` is used to recover its constant value.
269                if rhs.simplify().as_u64().is_some() {
270                    self.path_state.constraints.assertions.push(result.ge(&zero));
271                    self.path_state.constraints.assertions.push(result.le(rhs));
272                }
273                if self.path_state.constraints.term_caches.not_mask_terms.contains(rhs) {
274                    // rhs is a two's-complement mask `!(align-1) == -align`,
275                    // so `align = -rhs`. The result of `x & !(align-1)` is
276                    // `x` rounded down to a multiple of `align` (i.e. align_up
277                    // of the pre-incremented value).
278                    let zero = Int::from_u64(self.z3_ctx, 0);
279                    let align = Int::sub(self.z3_ctx, &[&zero, rhs]);
280                    self.path_state.constraints
281                        .assertions
282                        .push(result.rem(&align)._eq(&zero));
283                    let one = Int::from_u64(self.z3_ctx, 1);
284                    let addr = Int::add(self.z3_ctx, &[lhs, rhs, &one]);
285                    self.path_state.constraints.assertions.push(result.ge(&addr));
286                }
287                result
288            }
289            BinOp::BitOr => {
290                let result = self.fresh_int("binop");
291                let zero = Int::from_u64(self.z3_ctx, 0);
292                // Bitwise OR only sets bits, so the result is non-zero whenever
293                // either operand is non-zero.  Emit an implication (rather than
294                // `result >= lhs`, which is only valid for non-negative values)
295                // so `NonZero` bit-or methods discharge their `!= 0` obligation
296                // for both signed and unsigned instantiations.
297                self.path_state.constraints
298                    .assertions
299                    .push(lhs._eq(&zero).not().implies(&result._eq(&zero).not()));
300                self.path_state.constraints
301                    .assertions
302                    .push(rhs._eq(&zero).not().implies(&result._eq(&zero).not()));
303                result
304            }
305            _ => self.fresh_int("binop"),
306        }
307    }
308
309    pub(crate) fn eval_unary_op(&mut self, op: UnOp, val: &Int<'z3>, is_bool: bool) -> Int<'z3> {
310        match op {
311            UnOp::Not => {
312                if is_bool {
313                    let zero = Int::from_u64(self.z3_ctx, 0);
314                    let one = Int::from_u64(self.z3_ctx, 1);
315                    val._eq(&zero).ite(&one, &zero)
316                } else {
317                    let one = Int::from_u64(self.z3_ctx, 1);
318                    let result = Int::sub(self.z3_ctx, &[&self.negate(val), &one]);
319                    self.path_state.constraints
320                        .term_caches
321                        .not_mask_terms
322                        .insert(result.clone());
323                    result
324                }
325            }
326            UnOp::Neg => self.negate(val),
327            UnOp::PtrMetadata => self.fresh_int("ptr_metadata"),
328        }
329    }
330
331    pub(crate) fn integer_limits(
332        &self,
333        ty: Ty<'tcx>,
334    ) -> Option<(Int<'z3>, Int<'z3>, Int<'z3>, bool)> {
335        let signed = match ty.kind() {
336            TyKind::Int(_) => true,
337            TyKind::Uint(_) => false,
338            _ => return None,
339        };
340        let (_, bytes) = mir_utils::type_layout(self.tcx, self.path_state.current_frame.current_def_id, ty)?;
341        let bits = bytes.checked_mul(8)?;
342        if bits == 0 || bits > 128 {
343            return None;
344        }
345        let unsigned_max = if bits == 128 {
346            u128::MAX
347        } else {
348            (1u128 << bits) - 1
349        };
350        let modulus = Int::add(
351            self.z3_ctx,
352            &[
353                &Int::from_str(self.z3_ctx, &unsigned_max.to_string())?,
354                &Int::from_u64(self.z3_ctx, 1),
355            ],
356        );
357        let (min, max) = if signed {
358            let signed_max = if bits == 128 {
359                i128::MAX
360            } else {
361                (1i128 << (bits - 1)) - 1
362            };
363            let signed_min = if bits == 128 {
364                i128::MIN
365            } else {
366                -(1i128 << (bits - 1))
367            };
368            (signed_min.to_string(), signed_max.to_string())
369        } else {
370            ("0".to_string(), unsigned_max.to_string())
371        };
372        Some((
373            Int::from_str(self.z3_ctx, &min)?,
374            Int::from_str(self.z3_ctx, &max)?,
375            modulus,
376            signed,
377        ))
378    }
379
380    pub(crate) fn wrap_integer_term(&self, ty: Ty<'tcx>, raw: &Int<'z3>) -> Int<'z3> {
381        let Some((min, max, modulus, signed)) = self.integer_limits(ty) else {
382            return raw.clone();
383        };
384        if self.path_implies(&raw.ge(&min)) && self.path_implies(&raw.le(&max)) {
385            return raw.clone();
386        }
387        let wrapped = raw.modulo(&modulus);
388        if signed {
389            wrapped
390                .gt(&max)
391                .ite(&Int::sub(self.z3_ctx, &[&wrapped, &modulus]), &wrapped)
392        } else {
393            wrapped
394        }
395    }
396
397    /// Compute the preserved alignment when doing `base + offset * stride`.
398    /// Pointer arithmetic only ever *preserves* the base's alignment; it never
399    /// creates it. When the base's alignment is unknown, we cannot conclude
400    /// anything about the result (a `wrapping_add` over misaligned storage does
401    /// not become aligned just because the stride is a power of two).
402    fn compute_pointer_add_align(
403        &self,
404        base: &VmValue<'z3, 'tcx>,
405        stride_bytes: u64,
406    ) -> Option<Int<'z3>> {
407        let base_align = base.facts.align_n.as_ref()?;
408        // Concrete alignment: the result stays n-aligned only if the stride is
409        // a multiple of n.  A symbolic alignment can't be decided against a
410        // concrete stride, so drop it here (the `check_align` SMT query
411        // re-derives alignment from the allocation's align and the
412        // `sizeof_T % align_T == 0` layout constraint).
413        let n = base_align.simplify().as_u64()?;
414        if stride_bytes > 0 && stride_bytes.is_multiple_of(n) {
415            return Some(base_align.clone());
416        }
417        None
418    }
419
420    /// The byte stride for a pointer add/sub: the fixed `stride`, or the pointee's
421    /// symbolic size when the stride is element-sized (a generic `T`).
422    fn pointer_stride_term(
423        &mut self,
424        dest: Local,
425        base: &VmValue<'z3, 'tcx>,
426        stride: Option<u64>,
427    ) -> Int<'z3> {
428        match stride {
429            Some(s) => Int::from_u64(self.z3_ctx, s),
430            None => {
431                let dest_ty = self.body().local_decls[dest].ty;
432                let dest_pointee = mir_utils::pointee_ty(dest_ty).unwrap_or(dest_ty);
433                let base_pointee = mir_utils::pointee_ty(base.ty).unwrap_or(base.ty);
434                // A generic callee can name the caller's element type with a
435                // distinct Ty::Param. Pointer arithmetic uses the incoming
436                // pointer's element size when both types are generic.
437                let generic_pointer = matches!(
438                    (base_pointee.kind(), dest_pointee.kind()),
439                    (TyKind::Param(_), TyKind::Param(_))
440                );
441                let pointee = match base_pointee.kind() {
442                    TyKind::Array(element, _) | TyKind::Slice(element) => *element,
443                    TyKind::Str => return Int::from_u64(self.z3_ctx, 1),
444                    _ if generic_pointer => base_pointee,
445                    _ => dest_pointee,
446                };
447                self.size_sym(pointee)
448            }
449        }
450    }
451
452    /// Model `dest = base.offset(offset)` with element/byte stride and tracked
453    /// provenance (`offset_kind`), shared by call effects
454    /// and the inlined `Offset` MIR statement.
455    pub(crate) fn apply_pointer_add(
456        &mut self,
457        dest: Local,
458        base: &VmValue<'z3, 'tcx>,
459        offset: &VmValue<'z3, 'tcx>,
460        stride: Option<u64>,
461        dereferenceable: bool,
462    ) {
463        // `sub` lowers `intrinsics::unchecked_sub(0, n)` to a unary negation `-n`
464        // (`eval_binary_op` folds `0 - x` to `-x`).  Recover the positive count
465        // and model the result as `base - count*stride` (a negated product) so a
466        // later `+ count*stride` in `Allocated`'s byte-coverage query cancels
467        // linearly, instead of `base + (-count)*stride` whose `(-count)*stride`
468        // product Z3's nonlinear solver cannot factor out.
469        let (offset_term, subtract) = if offset.z3_term.num_children() == 1
470            && let Some(positive) = offset.z3_term.nth_child(0).and_then(|c| c.as_int())
471        {
472            (positive, true)
473        } else {
474            (offset.z3_term.clone(), false)
475        };
476        let stride_term = self.pointer_stride_term(dest, base, stride);
477        let adjusted_offset = if stride == Some(1) {
478            offset_term.clone()
479        } else {
480            Int::mul(self.z3_ctx, &[&offset_term, &stride_term])
481        };
482        let combine = |l: &Int<'z3>, r: &Int<'z3>| {
483            if subtract {
484                Int::sub(self.z3_ctx, &[l, r])
485            } else {
486                Int::add(self.z3_ctx, &[l, r])
487            }
488        };
489        let new_term = combine(&base.z3_term, &adjusted_offset);
490        let is_field_offset = offset.is_field_offset()
491            && base
492                .provenance
493                .as_ref()
494                .is_some_and(|p| p.offset.as_u64() == Some(0));
495        let element_offset = if stride == Some(1) {
496            None
497        } else {
498            match base.provenance.as_ref().and_then(|p| match &p.offset_kind {
499                Some(OffsetKind::Element { index, stride })
500                    if stride.simplify() == stride_term.simplify() =>
501                {
502                    Some(index.clone())
503                }
504                _ => None,
505            }) {
506                Some(e) => Some(combine(&e, &offset_term)),
507                None if base
508                    .provenance
509                    .as_ref()
510                    .is_some_and(|p| p.offset.as_u64() == Some(0)) =>
511                {
512                    Some(if subtract {
513                        -offset_term.clone()
514                    } else {
515                        offset_term.clone()
516                    })
517                }
518                None => None,
519            }
520        };
521        let offset_kind = if is_field_offset {
522            Some(OffsetKind::Field)
523        } else if let Some(e) = element_offset {
524            Some(OffsetKind::Element {
525                index: e,
526                stride: stride_term.clone(),
527            })
528        } else {
529            Some(OffsetKind::Byte)
530        };
531        let adjusted_provenance = base.provenance.as_ref().map(|prov| Provenance {
532            alloc_id: prov.alloc_id,
533            offset: combine(&prov.offset, &adjusted_offset),
534            offset_kind,
535        });
536        let align_n = match stride {
537            Some(s) => self.compute_pointer_add_align(base, s),
538            None => base.facts.align_n.clone(),
539        };
540        let val = VmValue {
541            z3_term: new_term,
542            ty: self.body().local_decls[dest].ty,
543            provenance: adjusted_provenance,
544            facts: ValueFacts {
545                non_null: base.facts.non_null,
546                dangling: base.facts.dangling,
547                in_bounds: dereferenceable,
548                align_n,
549                init: base.facts.init,
550                ownership_transfer: base.facts.ownership_transfer,
551            },
552            source: ValueSource::None,
553        };
554        self.set_local(dest, val);
555    }
556}