Skip to main content

rapx/vm/
iterator.rs

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    /// The two pointer fields of an Iter/IterMut local (`[0]` = ptr, `[1]` =
11    /// end_or_len), which share the same allocation.  Returns `None` when
12    /// either field is missing or the two point into different allocations.
13    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    /// Element size of the type iterated by an Iter/IterMut pointer, symbolic
37    /// (`sizeof_T`) for a generic element type so `size / elem_size` cancels.
38    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    /// Element count from two pointer fields sharing the same allocation:
58    /// `(end.offset - ptr.offset) / elem_size`. When both pointers carry an
59    /// element-structured offset (`OffsetKind::Element`, or the base), the
60    /// count is computed element-wise (`end_elem - ptr_elem`) so the
61    /// `(end·S - ptr·S)/S` division is avoided for a generic element size `S`.
62    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    /// Compare pointers by their MIR-derived element indices when they use the
88    /// same positive byte stride. The tracked std iterator offset remains a
89    /// fallback when an element index is unavailable.
90    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    /// If `local` is a reference to Iter/IterMut and field 0 (ptr)
205    /// is updated, increment the cumulative ptr offset so that
206    /// `interpreter_iter_len` can express `len = initial_len - offset`
207    /// instead of nested `(end - (ptr + sz + sz + ...)) / sz`.
208    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    /// The buffer an `Iter`/`IterMut` at `local` walks: the provenance of its
251    /// `end` field.  This is frame-independent (the buffer allocation is
252    /// path-scoped), unlike the `local` itself. The iterator's own allocation
253    /// keys its element index in `iter_ptr_offset`.
254    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    /// The byte buffer walked by an iterator at `local`, possibly wrapped in
261    /// adapter types (`Cloned`/`Rev`/…).  `Rvalue::Aggregate` flattens nested
262    /// adapters, so the innermost `Iter`/`IterMut` `end` pointer is any tracked
263    /// field whose path ends in `[1]`.  Return its allocation and end offset
264    /// (the end offset doubles as the byte length when the element is `u8`).
265    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}