Skip to main content

rapx/vm/mir_rules/call/
comparison.rs

1//! Exact comparison models for supported trait calls.
2//!
3//! A model must describe the returned boolean on both branches. In particular,
4//! equality never writes its operands or makes a fact true unconditionally.
5
6use rustc_hir::def_id::DefId;
7use rustc_middle::{
8    mir::{BinOp, Local, Operand, Rvalue, StatementKind},
9    ty::{TyCtxt, TyKind},
10};
11use z3::ast::{Ast, Bool, Int};
12
13use super::super::super::state::{AllocKind, ValueSource, VmExecutor, VmValue};
14use crate::def_ids::lang_api::{self, LangItem};
15use crate::util::mir_utils;
16
17#[derive(Clone, Copy)]
18enum ComparisonMethod {
19    Eq,
20    Ne,
21    Lt,
22    Le,
23    Gt,
24    Ge,
25}
26
27impl ComparisonMethod {
28    fn from_callee(tcx: TyCtxt<'_>, callee: DefId) -> Option<Self> {
29        let assoc = tcx.opt_associated_item(callee)?;
30        let trait_id = assoc.trait_container(tcx)?;
31        let symbol = assoc.name();
32        let name = symbol.as_str();
33        if lang_api::matches(tcx, trait_id, LangItem::PartialEq) {
34            return match name {
35                "eq" => Some(Self::Eq),
36                "ne" => Some(Self::Ne),
37                _ => None,
38            };
39        }
40        if lang_api::matches(tcx, trait_id, LangItem::PartialOrd) {
41            return match name {
42                "lt" => Some(Self::Lt),
43                "le" => Some(Self::Le),
44                "gt" => Some(Self::Gt),
45                "ge" => Some(Self::Ge),
46                _ => None,
47            };
48        }
49        None
50    }
51
52    fn mir_op(self) -> BinOp {
53        match self {
54            Self::Eq => BinOp::Eq,
55            Self::Ne => BinOp::Ne,
56            Self::Lt => BinOp::Lt,
57            Self::Le => BinOp::Le,
58            Self::Gt => BinOp::Gt,
59            Self::Ge => BinOp::Ge,
60        }
61    }
62
63    fn compare<'z3>(self, left: &Int<'z3>, right: &Int<'z3>) -> Bool<'z3> {
64        match self {
65            Self::Eq => left._eq(right),
66            Self::Ne => left._eq(right).not(),
67            Self::Lt => left.lt(right),
68            Self::Le => left.le(right),
69            Self::Gt => left.gt(right),
70            Self::Ge => left.ge(right),
71        }
72    }
73}
74
75pub(super) struct ComparisonPlan<'z3> {
76    op: BinOp,
77    condition: Bool<'z3>,
78}
79
80impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
81    pub(super) fn prepare_comparison(
82        &self,
83        callee: Option<DefId>,
84        args: &[VmValue<'z3, 'tcx>],
85        destination: Local,
86    ) -> Option<ComparisonPlan<'z3>> {
87        let Some(method) = callee.and_then(|id| ComparisonMethod::from_callee(self.tcx, id)) else {
88            return None;
89        };
90        if args.len() != 2
91            || !matches!(self.body().local_decls[destination].ty.kind(), TyKind::Bool)
92        {
93            return None;
94        }
95
96        let Some(condition) = self
97            .scalar_comparison(method, &args[0], &args[1])
98            .or_else(|| match method {
99                ComparisonMethod::Eq => self.byte_slice_eq(&args[0], &args[1]),
100                ComparisonMethod::Ne => self.byte_slice_eq(&args[0], &args[1]).map(|eq| eq.not()),
101                _ => None,
102            })
103        else {
104            return None;
105        };
106        Some(ComparisonPlan {
107            op: method.mir_op(),
108            condition,
109        })
110    }
111
112    pub(super) fn apply_comparison(&mut self, plan: ComparisonPlan<'z3>, destination: Local) {
113        let ComparisonPlan { op, condition } = plan;
114        let one = Int::from_u64(self.z3_ctx, 1);
115        let zero = Int::from_u64(self.z3_ctx, 0);
116        let mut result = VmValue::new(condition.ite(&one, &zero), self.tcx.types.bool);
117        result.source = ValueSource::Comparison {
118            lhs: None,
119            rhs: None,
120            op,
121            cond: condition,
122        };
123        self.set_local(destination, result);
124    }
125
126    /// A reference to a primitive scalar compares its stored value, not its
127    /// address. Floats are excluded because this integer model cannot express NaN.
128    fn scalar_comparison(
129        &self,
130        method: ComparisonMethod,
131        left: &VmValue<'z3, 'tcx>,
132        right: &VmValue<'z3, 'tcx>,
133    ) -> Option<Bool<'z3>> {
134        let left_prov = left.provenance.as_ref()?;
135        let right_prov = right.provenance.as_ref()?;
136        if left_prov.offset.simplify().as_u64() != Some(0)
137            || right_prov.offset.simplify().as_u64() != Some(0)
138        {
139            return None;
140        }
141        let ty = self.alloc(left_prov.alloc_id).element_ty.as_ty()?;
142        if ty != self.alloc(right_prov.alloc_id).element_ty.as_ty()?
143            || !matches!(
144                ty.kind(),
145                TyKind::Uint(_) | TyKind::Int(_) | TyKind::Bool | TyKind::Char
146            )
147        {
148            return None;
149        }
150        let left_value = self.load_value(left_prov.alloc_id, ty, &[])?;
151        let right_value = self.load_value(right_prov.alloc_id, ty, &[])?;
152        if !matches!(left_value.source, ValueSource::SharedScalarReferent)
153            || !matches!(right_value.source, ValueSource::SharedScalarReferent)
154        {
155            return None;
156        }
157        Some(method.compare(&left_value.z3_term, &right_value.z3_term))
158    }
159
160    /// Compare a tracked `[u8]` view with a fully materialized constant byte
161    /// array. The result is `len == N && bytes[0..N] == constant`.
162    fn byte_slice_eq(
163        &self,
164        left: &VmValue<'z3, 'tcx>,
165        right: &VmValue<'z3, 'tcx>,
166    ) -> Option<Bool<'z3>> {
167        self.byte_slice_const_eq(left, right)
168            .or_else(|| self.byte_slice_const_eq(right, left))
169    }
170
171    fn byte_slice_const_eq(
172        &self,
173        slice: &VmValue<'z3, 'tcx>,
174        constant: &VmValue<'z3, 'tcx>,
175    ) -> Option<Bool<'z3>> {
176        let slice_id = slice.provenance_alloc_id()?;
177        let slice_alloc = self.alloc(slice_id);
178        if slice_alloc.element_ty.as_ty() != Some(self.tcx.types.u8)
179            || !matches!(
180                slice_alloc.kind,
181                AllocKind::Slice { .. } | AllocKind::ExternalSlice { .. }
182            )
183            || slice.provenance.as_ref()?.offset.simplify().as_u64() != Some(0)
184        {
185            return None;
186        }
187        let bytes = self.constant_bytes(constant)?;
188        let byte_len = bytes.len();
189        let len = self.slice_len_of_alloc(slice_id)?;
190        let mut conditions = vec![len._eq(&Int::from_u64(self.z3_ctx, byte_len as u64))];
191        for (offset, byte) in bytes.iter().enumerate() {
192            if !self.is_byte_init(slice_id, offset) {
193                return None;
194            }
195            let index = Int::from_u64(self.z3_ctx, offset as u64);
196            conditions.push(
197                self.byte_read(slice_id, &index)
198                    ._eq(&Int::from_u64(self.z3_ctx, *byte as u64)),
199            );
200        }
201        Some(Bool::and(
202            self.z3_ctx,
203            &conditions.iter().collect::<Vec<_>>(),
204        ))
205    }
206
207    fn constant_bytes(&self, value: &VmValue<'z3, 'tcx>) -> Option<Vec<u8>> {
208        if let ValueSource::ConstBytes(bytes) = &value.source {
209            return Some(bytes.clone());
210        }
211        // Sliced paths can bind a promoted constant as a symbolic call
212        // argument, bypassing the `Use` transfer that carries ConstBytes.
213        // Recover it only by matching that exact symbolic constant to its MIR
214        // operand in a live caller frame.
215        let bodies = std::iter::once(self.target_body()).chain(
216            self.path_state.caller_frames
217                .iter()
218                .map(|saved| &saved.frame)
219                .chain(std::iter::once(&self.path_state.current_frame))
220                .filter_map(|frame| {
221                    frame.instantiated_body.or_else(|| {
222                        self.tcx
223                            .is_mir_available(frame.current_def_id)
224                            .then(|| self.tcx.optimized_mir(frame.current_def_id))
225                    })
226                }),
227        );
228        for body in bodies {
229            for block in body.basic_blocks.iter() {
230                for statement in &block.statements {
231                    let StatementKind::Assign(assign) = &statement.kind else {
232                        continue;
233                    };
234                    let Rvalue::Use(Operand::Constant(constant), ..) = &assign.1 else {
235                        continue;
236                    };
237                    if self.symbolic_const_term(&constant.const_) == value.z3_term
238                        && let Some(bytes) = mir_utils::const_operand_bytes(
239                            self.tcx,
240                            &Operand::Constant(constant.clone()),
241                        )
242                    {
243                        return Some(bytes);
244                    }
245                }
246            }
247        }
248        None
249    }
250}