1use rustc_middle::{mir::Local, ty::TyKind};
2use z3::ast::{Ast, Int};
3
4use crate::def_ids::type_ids;
5use crate::util::mir_utils;
6
7use super::state::{AllocId, OffsetKind, Provenance, VmExecutor, VmValue};
8
9impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
10 pub(crate) fn iter_ptr_end(
14 &self,
15 local: Local,
16 ) -> Option<(VmValue<'z3, 'tcx>, VmValue<'z3, 'tcx>)> {
17 for (ptr_path, end_path) in [(&[0][..], &[1][..]), (&[0, 0][..], &[0, 1][..])] {
18 let (Some(ptr), Some(end)) = (
19 self.field_value(local, ptr_path),
20 self.field_value(local, end_path),
21 ) else {
22 continue;
23 };
24 if ptr
25 .provenance
26 .as_ref()
27 .zip(end.provenance.as_ref())
28 .is_some_and(|(pp, ep)| pp.alloc_id == ep.alloc_id)
29 {
30 return Some((ptr.clone(), end.clone()));
31 }
32 }
33 None
34 }
35
36 pub(crate) fn iter_elem_size(&self, ptr: &VmValue<'z3, 'tcx>) -> Int<'z3> {
39 let elem_ty = match ptr.ty.kind() {
40 TyKind::Adt(_, substs) => substs.first().and_then(|s| s.as_type()),
41 TyKind::RawPtr(ty, _) | TyKind::Ref(_, ty, _) => Some(*ty),
42 _ => None,
43 };
44 if elem_ty.is_some_and(|ty| matches!(ty.kind(), TyKind::Param(_)))
45 && let Some(alloc_id) = ptr.provenance_alloc_id()
46 && let Some(concrete) = self.alloc(alloc_id).element_ty.as_ty()
47 && !matches!(concrete.kind(), TyKind::Param(_))
48 {
49 return self.size_sym_read(concrete);
50 }
51 match elem_ty {
52 Some(t) => self.size_sym_read(t),
53 None => Int::from_u64(self.z3_ctx, 1),
54 }
55 }
56
57 pub(crate) fn iter_len_from_ptrs(
63 &self,
64 ptr: &VmValue<'z3, 'tcx>,
65 end: &VmValue<'z3, 'tcx>,
66 ) -> Option<Int<'z3>> {
67 let pp = ptr.provenance.as_ref()?;
68 let ep = end.provenance.as_ref()?;
69 if pp.alloc_id != ep.alloc_id {
70 return None;
71 }
72 let elem_of = |p: &Provenance<'z3>| -> Option<Int<'z3>> {
73 match &p.offset_kind {
74 Some(OffsetKind::Element { index, .. }) => Some(index.clone()),
75 Some(OffsetKind::Field) | None => Some(Int::from_u64(self.z3_ctx, 0)),
76 _ => None,
77 }
78 };
79 if let (Some(pe), Some(ee)) = (elem_of(pp), elem_of(ep)) {
80 return Some(Int::sub(self.z3_ctx, &[&ee, &pe]));
81 }
82 let sz = self.iter_elem_size(ptr);
83 let diff = Int::sub(self.z3_ctx, &[&ep.offset, &pp.offset]);
84 Some(diff.div(&sz))
85 }
86
87 pub(crate) fn iter_ptr_comparison(
91 &mut self,
92 op: rustc_middle::mir::BinOp,
93 lhs: &VmValue<'z3, 'tcx>,
94 rhs: &VmValue<'z3, 'tcx>,
95 ) -> Option<z3::ast::Bool<'z3>> {
96 if !matches!(
97 op,
98 rustc_middle::mir::BinOp::Eq | rustc_middle::mir::BinOp::Ne
99 ) {
100 return None;
101 }
102 let lp = lhs.provenance.as_ref()?;
103 let rp = rhs.provenance.as_ref()?;
104 if lp.alloc_id != rp.alloc_id {
105 return None;
106 }
107 let Some(pointee) = mir_utils::pointee_ty(lhs.ty) else {
108 return None;
109 };
110 if Some(pointee) != mir_utils::pointee_ty(rhs.ty)
111 || !pointee.is_sized(
112 self.tcx,
113 rustc_middle::ty::TypingEnv::post_analysis(
114 self.tcx,
115 self.path_state.current_frame.current_def_id,
116 ),
117 )
118 {
119 return None;
120 }
121 let element = |prov: &Provenance<'z3>| match &prov.offset_kind {
122 Some(OffsetKind::Element { index, .. }) => Some(index.clone()),
123 None | Some(OffsetKind::Field) if prov.offset.simplify().as_u64() == Some(0) => {
124 Some(Int::from_u64(self.z3_ctx, 0))
125 }
126 _ => None,
127 };
128 let stride = match (&lp.offset_kind, &rp.offset_kind) {
129 (
130 Some(OffsetKind::Element { stride: left, .. }),
131 Some(OffsetKind::Element { stride: right, .. }),
132 ) if left.simplify() == right.simplify() => Some(left.clone()),
133 (Some(OffsetKind::Element { stride, .. }), None | Some(OffsetKind::Field))
134 if element(rp).is_some() =>
135 {
136 Some(stride.clone())
137 }
138 (None | Some(OffsetKind::Field), Some(OffsetKind::Element { stride, .. }))
139 if element(lp).is_some() =>
140 {
141 Some(stride.clone())
142 }
143 _ => None,
144 };
145 if let Some(stride) = stride
146 && let Some((left, right)) = element(lp).zip(element(rp))
147 {
148 let positive = self.path_state.constraints.term_caches.non_zst.contains(&stride)
149 || self.path_implies(&stride.gt(&Int::from_u64(self.z3_ctx, 0)));
150 if positive {
151 self.path_state.constraints.term_caches.non_zst.insert(stride);
152 let eq = left._eq(&right);
153 return Some(if matches!(op, rustc_middle::mir::BinOp::Eq) {
154 eq
155 } else {
156 eq.not()
157 });
158 }
159 }
160 let is_std_iter_comparison = self.path_state.current_frame.local_alloc.keys().any(|local| {
161 let Some(value) = self.local_value(*local) else {
162 return false;
163 };
164 let rustc_middle::ty::TyKind::Ref(_, pointee, _) = value.ty.kind() else {
165 return false;
166 };
167 let rustc_middle::ty::TyKind::Adt(adt, _) = pointee.kind() else {
168 return false;
169 };
170 if !type_ids::is_std_iter_or_itermut(adt.did()) {
171 return false;
172 }
173 let Some((ptr, end)) = self.iter_ptr_end(*local) else {
174 return false;
175 };
176 (ptr.z3_term.simplify() == lhs.z3_term.simplify()
177 && end.z3_term.simplify() == rhs.z3_term.simplify())
178 || (ptr.z3_term.simplify() == rhs.z3_term.simplify()
179 && end.z3_term.simplify() == lhs.z3_term.simplify())
180 });
181 if !is_std_iter_comparison {
182 return None;
183 }
184 let eq = {
185 let mut candidates = self.path_state
186 .constraints
187 .term_caches
188 .iter_ptr_offset
189 .values()
190 .filter(|(buffer, _, _)| *buffer == lp.alloc_id);
191 let (_, offset, base_len) = candidates.next()?;
192 if candidates.next().is_some() {
193 return None;
194 }
195 offset._eq(base_len.as_ref()?)
196 };
197 Some(if matches!(op, rustc_middle::mir::BinOp::Eq) {
198 eq
199 } else {
200 eq.not()
201 })
202 }
203
204 pub(crate) fn track_iter_ptr_update(&mut self, local: Local) {
209 let local_val = match self.local_value(local) {
210 Some(v) => v,
211 None => return,
212 };
213 if !self.is_iter_ref(local_val) {
214 return;
215 }
216 let Some(iter_local) = self.find_local_by_address(&local_val.z3_term) else {
217 return;
218 };
219 let Some(iter_prov) = local_val.provenance.as_ref() else {
220 return;
221 };
222 let iter_key = (iter_prov.alloc_id, iter_prov.offset.simplify());
223 let Some(buffer) = self.iter_buffer(iter_local) else {
224 return;
225 };
226 let one = Int::from_u64(self.z3_ctx, 1);
227 let (new_offset, base_len) =
228 match self.path_state.constraints.term_caches.iter_ptr_offset.get(&iter_key) {
229 Some((_, prev, base)) => (Int::add(self.z3_ctx, &[prev, &one]), base.clone()),
230 None => {
231 let base = self
232 .field_value(iter_local, &[1])
233 .and_then(|end| end.provenance.as_ref())
234 .and_then(|ep| match &ep.offset_kind {
235 Some(OffsetKind::Element { index, .. }) => Some(index.clone()),
236 _ => None,
237 });
238 (one.clone(), base)
239 }
240 };
241 if let Some(e) = &base_len {
242 self.path_state.constraints.assertions.push(new_offset.le(e));
243 }
244 self.path_state.constraints
245 .term_caches
246 .iter_ptr_offset
247 .insert(iter_key, (buffer, new_offset, base_len));
248 }
249
250 fn iter_buffer(&self, local: Local) -> Option<AllocId> {
255 self.field_value(local, &[1])
256 .and_then(|end| end.provenance.as_ref())
257 .map(|ep| ep.alloc_id)
258 }
259
260 pub(crate) fn iter_utf8_buffer(&self, local: Local) -> Option<(AllocId, Int<'z3>)> {
266 let mut best: Option<(usize, AllocId, Int<'z3>)> = None;
267 for path in self.field_paths(local) {
268 if path.last() != Some(&1) {
269 continue;
270 }
271 let Some(v) = self.field_value(local, &path) else {
272 continue;
273 };
274 let Some(prov) = v.provenance.as_ref() else {
275 continue;
276 };
277 if best
278 .as_ref()
279 .is_none_or(|(depth, _, _)| path.len() < *depth)
280 {
281 best = Some((path.len(), prov.alloc_id, prov.offset.clone()));
282 }
283 }
284 best.map(|(_, id, off)| (id, off))
285 }
286
287 pub(crate) fn is_iter_ref(&self, val: &VmValue<'z3, 'tcx>) -> bool {
288 match val.ty.kind() {
289 rustc_middle::ty::TyKind::Ref(_, pointee, _) => match pointee.kind() {
290 rustc_middle::ty::TyKind::Adt(adt_def, _) => {
291 adt_def.did().as_local().is_none()
292 && type_ids::is_std_iter_or_itermut(adt_def.did())
293 }
294 _ => false,
295 },
296 _ => false,
297 }
298 }
299}