1use 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 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 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 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}