Skip to main content

rapx/vm/
memory.rs

1//! Symbolic memory model for the VM.
2
3use crate::def_ids::type_ids;
4use crate::util::mir_utils;
5#[cfg(rapx_const_ext)]
6use rustc_middle::ty::consts::ConstExt;
7use rustc_middle::{
8    mir::{Local, Place, ProjectionElem},
9    ty::{Ty, TyKind},
10};
11use z3::{Context, Sort, ast::{Array, Ast, Bool, Int}};
12
13use super::state::{AllocId, AllocKind, Allocation, ElementTy, MemoryContent, MemoryUnit, Provenance, ValueFacts, ValueSource, VmExecutor, VmValue};
14
15impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
16    /// The key of a bounded span. Unsized slices and strings also need their length.
17    pub(crate) fn bounded_span(&self, value: &VmValue<'z3, 'tcx>, ty: Ty<'tcx>) -> Option<(Int<'z3>, Ty<'tcx>, Option<Int<'z3>>)> {
18        let len = if matches!(ty.kind(), TyKind::Slice(_) | TyKind::Str) {
19            Some(self.slice_len_from_value(value)?)
20        } else {
21            None
22        };
23        Some((value.z3_term.clone(), ty, len))
24    }
25
26    pub(crate) fn copy_memory_values(
27        &mut self,
28        source: &VmValue<'z3, 'tcx>,
29        target: &VmValue<'z3, 'tcx>,
30        count: &VmValue<'z3, 'tcx>,
31    ) {
32        let concrete_count = count.z3_term.simplify().as_u64();
33        if concrete_count == Some(0) {
34            return;
35        }
36        let Some(pointee_ty) = mir_utils::pointee_ty(target.ty) else {
37            self.record_unsupported_effect("CopyMemory pointee type unavailable");
38            return;
39        };
40        let local_target = self
41            .find_local_by_address(&target.z3_term)
42            .is_some_and(|local| self.body().local_decls[local].ty == pointee_ty);
43        let inline_target = self.path_state
44            .inline
45            .arg_referents
46            .iter()
47            .enumerate()
48            .any(|(i, referent)| {
49                referent.is_some()
50                    && self
51                        .local_value(Local::from_usize(i + 1))
52                        .is_some_and(|value| value.z3_term == target.z3_term)
53            });
54        let slice_target = target.provenance.as_ref().is_some_and(|prov| {
55            matches!(self.alloc(prov.alloc_id).kind, AllocKind::Slice { .. } | AllocKind::ExternalSlice { .. })
56        });
57        let allocated_target = target.provenance.as_ref().is_some_and(|prov| {
58            let alloc = self.alloc(prov.alloc_id);
59            matches!(&alloc.kind, AllocKind::Object | AllocKind::Slice { .. })
60                && alloc.element_ty.as_ty() == Some(pointee_ty)
61                && (matches!(&alloc.kind, AllocKind::Slice { .. })
62                    || prov.offset.simplify().as_u64() == Some(0))
63        });
64        let scratch_target_ty = target.provenance.as_ref().and_then(|prov| {
65            let alloc = self.alloc(prov.alloc_id);
66            let ty = alloc.element_ty.as_ty()?;
67            match ty.kind() {
68                TyKind::Adt(def, args)
69                    if type_ids::is_maybe_uninit_type(def.did())
70                        && prov.offset.simplify().as_u64() == Some(0) => {
71                    args.first().and_then(|arg| arg.as_type())
72                }
73                _ => None,
74            }
75        });
76        let scratch_target = scratch_target_ty.is_some();
77        if !local_target && !inline_target && !allocated_target && !scratch_target {
78            self.record_unsupported_effect("CopyMemory target unavailable");
79            return;
80        }
81        if concrete_count != Some(1) && target.provenance.is_none() {
82            self.record_unsupported_effect("CopyMemory symbolic count without target provenance");
83            return;
84        }
85        let source_value = self
86            .find_local_by_address(&source.z3_term)
87            .filter(|local| self.body().local_decls[*local].ty == pointee_ty)
88            .and_then(|local| self.local_value(local).cloned())
89            .or_else(|| {
90                source
91                    .provenance
92                    .as_ref()
93                    .and_then(|prov| self.load_value(prov.alloc_id, pointee_ty, &[]).cloned())
94            });
95        let source_initialized = source
96            .provenance
97            .as_ref()
98            .is_some_and(|prov| {
99                let content = self.content(prov.alloc_id);
100                let maybe_uninit = self.alloc(prov.alloc_id).element_ty.as_ty().is_some_and(|ty| {
101                    matches!(ty.kind(), TyKind::Adt(def, _)
102                        if type_ids::is_maybe_uninit_type(def.did()))
103                });
104                (content.facts.initialized && !maybe_uninit)
105                    || (prov.offset.simplify().as_u64() == Some(0)
106                        && content.copied_prefix.as_ref().is_some_and(|(ty, copied_count)| {
107                            *ty == pointee_ty
108                                && self.path_implies(&count.z3_term.le(copied_count))
109                        }))
110            })
111            || source_value.as_ref().is_some_and(|value| {
112                value.facts.init && (source.provenance.is_none() || concrete_count == Some(1))
113            });
114        if (slice_target || scratch_target) && !source_initialized {
115            self.record_unsupported_effect("CopyMemory source initialization unavailable");
116            return;
117        }
118        let mut copied = if concrete_count == Some(1) {
119            source_value.unwrap_or_else(|| VmValue::new(self.fresh_int("copy_value"), pointee_ty))
120        } else {
121            VmValue::new(self.fresh_int("copy_value"), pointee_ty)
122        };
123        copied.facts.init |= source_initialized;
124        if scratch_target {
125            let alloc_id = target.provenance.as_ref().unwrap().alloc_id;
126            self.forget_memory_values(alloc_id);
127            if concrete_count == Some(1) && scratch_target_ty == Some(pointee_ty) {
128                self.store_value(alloc_id, pointee_ty, Vec::new(), copied);
129                self.content_mut(alloc_id).facts.initialized = true;
130                self.content_mut(alloc_id).facts.written_pointee_ty = Some(pointee_ty);
131            } else {
132                self.content_mut(alloc_id).copied_prefix =
133                    Some((pointee_ty, count.z3_term.clone()));
134            }
135            return;
136        }
137        if let Some(prov) = &target.provenance {
138            self.forget_memory_values(prov.alloc_id);
139        }
140        if concrete_count == Some(1) {
141            self.write_through_pointer(target, Vec::new(), copied);
142        }
143    }
144
145    pub(crate) fn forget_memory_values(&mut self, alloc_id: AllocId) {
146        let root = self.root_alloc(alloc_id);
147        self.clear_write_evidence(root);
148        let aliases: Vec<_> = (0..self.path_state.mem_units.len())
149            .map(AllocId)
150            .filter(|id| self.root_alloc(*id) == root)
151            .collect();
152        for id in aliases {
153            self.alloc_mut(id).facts.for_each = Default::default();
154            let content = self.content_mut(id);
155            content.values.clear();
156            content.indexed_elements.clear();
157            content.indexed_elements_modified = true;
158            content.copied_prefix = None;
159            content.facts.written_pointee_ty = None;
160            content.clear_byte_writes();
161            content.facts.cstr_trusted = false;
162            content.facts.utf8_trusted = false;
163            content.facts.split_transmute_to = None;
164        }
165    }
166
167    pub(crate) fn swap_memory_values(&mut self, left: &VmValue<'z3, 'tcx>, right: &VmValue<'z3, 'tcx>) -> bool {
168        if let Some((left_local, right_local)) = self
169            .find_local_by_address(&left.z3_term)
170            .zip(self.find_local_by_address(&right.z3_term))
171        {
172            let ty = self.body().local_decls[left_local].ty;
173            if left_local != right_local
174                && ty == self.body().local_decls[right_local].ty
175                && matches!(ty.kind(), TyKind::Int(_) | TyKind::Uint(_))
176                && let Some((left_value, right_value)) = self
177                    .local_value(left_local)
178                    .cloned()
179                    .zip(self.local_value(right_local).cloned())
180            {
181                self.set_local(left_local, right_value);
182                self.set_local(right_local, left_value);
183                return true;
184            }
185        }
186        let Some((left_prov, right_prov)) =
187            left.provenance.as_ref().zip(right.provenance.as_ref())
188        else {
189            return false;
190        };
191        let Some(ty) = mir_utils::pointee_ty(left.ty) else {
192            return false;
193        };
194        if mir_utils::pointee_ty(right.ty) != Some(ty) {
195            return false;
196        }
197        for id in [left_prov.alloc_id, right_prov.alloc_id] {
198            let root = self.root_alloc(id);
199            let alloc = self.alloc(id);
200            if alloc.element_ty.as_ty() != Some(ty)
201                && self.alloc(root).element_ty.as_ty() != Some(ty)
202            {
203                return false;
204            }
205            if !self.content(id).facts.initialized && !self.content(root).facts.initialized {
206                return false;
207            }
208        }
209        self.forget_memory_values(left_prov.alloc_id);
210        self.forget_memory_values(right_prov.alloc_id);
211        true
212    }
213
214    pub(crate) fn clear_write_evidence(&mut self, alloc_id: AllocId) {
215        let root = self.root_alloc(alloc_id);
216        let aliases: crate::compat::FxHashSet<_> = (0..self.path_state.mem_units.len())
217            .map(AllocId)
218            .filter(|id| self.root_alloc(*id) == root)
219            .collect();
220        for id in aliases {
221            self.path_state.mem_units[id.0].content.typed_facts.clear();
222            self.path_state.mem_units[id.0].content.copied_prefix = None;
223            self.path_state.mem_units[id.0].content.facts.written_pointee_ty = None;
224        }
225    }
226
227    pub(crate) fn write_provenance_allocation(
228        &mut self,
229        pointer: &VmValue<'z3, 'tcx>,
230        value: VmValue<'z3, 'tcx>,
231    ) -> bool {
232        if self.write_indexed_allocation(pointer, value.clone()) {
233            return true;
234        }
235        if self.write_field_allocation(pointer, value.clone()) {
236            return true;
237        }
238        self.write_reinterpreted_integer_allocation(pointer, value)
239    }
240
241    /// A typed whole-object write through a cast pointer replaces the start of
242    /// an integer buffer while keeping its original allocation element type.
243    fn write_reinterpreted_integer_allocation(
244        &mut self,
245        pointer: &VmValue<'z3, 'tcx>,
246        value: VmValue<'z3, 'tcx>,
247    ) -> bool {
248        let Some(prov) = pointer.provenance.as_ref() else {
249            return false;
250        };
251        if prov.offset.simplify().as_u64() != Some(0)
252            || mir_utils::pointee_ty(pointer.ty) != Some(value.ty)
253            || !value.facts.init
254            || !matches!(self.alloc(prov.alloc_id).kind, AllocKind::Slice { .. } | AllocKind::External | AllocKind::ExternalSlice { .. })
255            || !self.alloc(prov.alloc_id).element_ty.as_ty().is_some_and(|ty| {
256                ty != value.ty && matches!(ty.kind(), TyKind::Int(_) | TyKind::Uint(_))
257            })
258        {
259            return false;
260        }
261        self.clear_write_evidence(prov.alloc_id);
262        let written_ty = value.ty;
263        let local_allocation = self.alloc(prov.alloc_id).facts.locally_allocated;
264        if local_allocation {
265            self.alloc_mut(prov.alloc_id).element_ty = ElementTy::Typed(written_ty);
266        }
267        let content = self.content_mut(prov.alloc_id);
268        content.values.clear();
269        content.indexed_elements.clear();
270        content.indexed_elements_modified = true;
271        content.clear_byte_writes();
272        self.store_value(prov.alloc_id, value.ty, Vec::new(), value);
273        if local_allocation {
274            self.content_mut(prov.alloc_id).facts.written_pointee_ty = Some(written_ty);
275        }
276        true
277    }
278
279    pub(crate) fn invalidate_provenance_allocation(
280        &mut self,
281        pointer: &VmValue<'z3, 'tcx>,
282    ) {
283        let Some(provenance) = pointer.provenance.as_ref() else {
284            return;
285        };
286        let alloc_id = provenance.alloc_id;
287        if !self.path_state.current_frame.local_alloc.values().any(|id| *id == alloc_id) {
288            return;
289        }
290        self.clear_write_evidence(alloc_id);
291        let content = self.content_mut(alloc_id);
292        content.copied_prefix = None;
293        content.values.clear();
294        content.indexed_elements.clear();
295        content.indexed_elements_modified = true;
296        content.clear_byte_writes();
297    }
298
299    fn write_field_allocation(
300        &mut self,
301        pointer: &VmValue<'z3, 'tcx>,
302        value: VmValue<'z3, 'tcx>,
303    ) -> bool {
304        let Some(provenance) = pointer.provenance.as_ref() else {
305            return false;
306        };
307        let Some(offset) = provenance.offset.simplify().as_u64() else {
308            return false;
309        };
310        let Some(pointee_ty) = mir_utils::pointee_ty(pointer.ty) else {
311            return false;
312        };
313        if value.ty != pointee_ty {
314            return false;
315        }
316        let local = self.path_state.current_frame.local_alloc.iter().find_map(|(local, alloc_id)| {
317            (*alloc_id == provenance.alloc_id).then_some(*local)
318        });
319        let Some(root_ty) = local
320            .map(|local| self.body().local_decls[local].ty)
321            .or_else(|| self.alloc(provenance.alloc_id).element_ty.as_ty()) else {
322            return false;
323        };
324        let Some(path) = self.field_path_at_offset(root_ty, offset, pointee_ty) else {
325            return false;
326        };
327        self.clear_write_evidence(provenance.alloc_id);
328        self.content_mut(provenance.alloc_id).values.retain(|(ty, stored_path), _| {
329            *ty == root_ty
330                && !stored_path.starts_with(&path)
331                && !path.starts_with(stored_path)
332        });
333        if matches!(pointee_ty.kind(), TyKind::Uint(rustc_middle::ty::UintTy::U8)) {
334            self.byte_write(provenance.alloc_id, &provenance.offset, &value.z3_term);
335        } else {
336            let content = self.content_mut(provenance.alloc_id);
337            content.clear_byte_writes();
338        }
339        let aliases = self.path_state.current_frame.local_alloc.keys().copied().filter(|local| {
340            let local_ty = self.body().local_decls[*local].ty;
341            matches!(local_ty.kind(), TyKind::Ref(..) | TyKind::RawPtr(..))
342                && mir_utils::pointee_ty(local_ty) == Some(root_ty)
343                && self.local_value(*local)
344                    .and_then(|value| value.provenance_alloc_id()) == Some(provenance.alloc_id)
345        }).collect::<Vec<_>>();
346        self.store_value(provenance.alloc_id, root_ty, path.clone(), value.clone());
347        for local in aliases {
348            self.write_local_path(local, path.clone(), value.clone());
349        }
350        true
351    }
352
353    pub(crate) fn read_field_allocation(
354        &self,
355        pointer: &VmValue<'z3, 'tcx>,
356        pointee_ty: Ty<'tcx>,
357    ) -> Option<VmValue<'z3, 'tcx>> {
358        let provenance = pointer.provenance.as_ref()?;
359        let offset = provenance.offset.simplify().as_u64()?;
360        let root_ty = self.path_state
361            .current_frame
362            .local_alloc
363            .iter()
364            .find_map(|(local, id)| {
365                (*id == provenance.alloc_id).then(|| self.body().local_decls[*local].ty)
366            })
367            .or_else(|| self.alloc(provenance.alloc_id).element_ty.as_ty())?;
368        let path = if offset == 0 && root_ty == pointee_ty {
369            Vec::new()
370        } else {
371            self.field_path_at_offset(root_ty, offset, pointee_ty)?
372        };
373        self.load_value(provenance.alloc_id, root_ty, &path)
374            .cloned()
375            .or_else(|| {
376                (0..path.len()).rev().find_map(|prefix_len| {
377                    let stored = self.load_value(provenance.alloc_id, root_ty, &path[..prefix_len])?;
378                    let mut ty = stored.ty;
379                    for &field_index in &path[prefix_len..] {
380                        let TyKind::Adt(adt, args) = ty.kind() else {
381                            return None;
382                        };
383                        if !adt.repr().transparent() {
384                            return None;
385                        }
386                        let field = adt
387                            .non_enum_variant()
388                            .fields
389                            .get(rustc_abi::FieldIdx::from_usize(field_index))?;
390                        let field_ty = mir_utils::field_ty(self.tcx, field, args);
391                        if self.field_offset_in_bytes(ty, field_index) != 0
392                            || self.size_of_ty(ty) != self.size_of_ty(field_ty)
393                        {
394                            return None;
395                        }
396                        ty = field_ty;
397                    }
398                    (ty == pointee_ty).then(|| {
399                        let mut value = stored.clone();
400                        value.ty = pointee_ty;
401                        value
402                    })
403                })
404            })
405    }
406
407    fn field_path_at_offset(
408        &self,
409        ty: Ty<'tcx>,
410        offset: u64,
411        target_ty: Ty<'tcx>,
412    ) -> Option<Vec<usize>> {
413        let fields = match ty.kind() {
414            TyKind::Adt(def, args) if !def.is_enum() && !def.is_union() => def
415                .non_enum_variant()
416                .fields
417                .iter()
418                .map(|field| mir_utils::field_ty(self.tcx, field, args))
419                .collect::<Vec<_>>(),
420            TyKind::Tuple(fields) => fields.iter().collect::<Vec<_>>(),
421            _ => return None,
422        };
423        let mut found = None;
424        for (index, field_ty) in fields.into_iter().enumerate() {
425            let start = self.field_offset_in_bytes(ty, index);
426            let size = self.size_of_ty(field_ty);
427            if offset < start || offset - start >= size {
428                continue;
429            }
430            let nested = if offset == start && field_ty == target_ty {
431                Some(Vec::new())
432            } else {
433                self.field_path_at_offset(field_ty, offset - start, target_ty)
434            };
435            if let Some(mut nested) = nested {
436                nested.insert(0, index);
437                if found.is_some() {
438                    return None;
439                }
440                found = Some(nested);
441            }
442        }
443        found
444    }
445
446    fn write_indexed_allocation(
447        &mut self,
448        pointer: &VmValue<'z3, 'tcx>,
449        value: VmValue<'z3, 'tcx>,
450    ) -> bool {
451        let Some(provenance) = pointer.provenance.as_ref() else {
452            return false;
453        };
454        if self.alloc(provenance.alloc_id).slice_len().is_none() {
455            return false;
456        }
457        let Some(pointee_ty) = mir_utils::pointee_ty(pointer.ty) else {
458            return false;
459        };
460        let Some(mut element_ty) = self.alloc(provenance.alloc_id).element_ty.as_ty() else {
461            return false;
462        };
463        while let TyKind::Array(inner, _) = element_ty.kind() {
464            element_ty = *inner;
465        }
466        if element_ty != pointee_ty || value.ty != pointee_ty {
467            return false;
468        }
469        let element_size = self.size_of_ty(pointee_ty);
470        if element_size == 0 {
471            return false;
472        }
473        let index = match &provenance.offset_kind {
474            Some(super::state::OffsetKind::Element { index, stride })
475                if stride.simplify() == Int::from_u64(self.z3_ctx, element_size).simplify() =>
476            {
477                Some(index.clone())
478            }
479            _ => provenance.offset.simplify().as_u64().and_then(|offset| {
480                (offset % element_size == 0)
481                    .then(|| Int::from_u64(self.z3_ctx, offset / element_size))
482            }),
483        };
484        self.content_mut(provenance.alloc_id)
485            .values
486            .retain(|(_, path), _| path.is_empty());
487        if element_size == 1
488            && matches!(pointee_ty.kind(), TyKind::Uint(rustc_middle::ty::UintTy::U8))
489        {
490            self.byte_write(provenance.alloc_id, &provenance.offset, &value.z3_term);
491        } else if self.content(provenance.alloc_id).byte_array.is_some() {
492            if element_size <= 256 {
493                for byte in 0..element_size {
494                    let offset = Int::add(
495                        self.z3_ctx,
496                        &[&provenance.offset, &Int::from_u64(self.z3_ctx, byte)],
497                    );
498                    let unknown = self.fresh_int("written_byte");
499                    self.byte_write(provenance.alloc_id, &offset, &unknown);
500                }
501            } else {
502                let content = self.content_mut(provenance.alloc_id);
503                content.clear_byte_writes();
504            }
505        }
506        if let Some(index) = index {
507            self.store_indexed_element(provenance.alloc_id, index, value);
508        } else {
509            let content = self.content_mut(provenance.alloc_id);
510            content.indexed_elements.clear();
511            content.indexed_elements_modified = true;
512        }
513        true
514    }
515
516    pub(crate) fn address_of_place(&mut self, place: &Place<'tcx>) -> Option<VmValue<'z3, 'tcx>> {
517        self.ensure_local_allocation(place.local);
518
519        let zero = Int::from_u64(self.z3_ctx, 0);
520
521        if place.projection.is_empty() {
522            let base_addr = self.local_address(place.local);
523            let ty = self.body().local_decls[place.local].ty;
524            let is_manually_drop = matches!(ty.kind(), TyKind::Adt(def, _)
525                if self.tcx.is_lang_item(def.did(), crate::def_ids::lang_api::LangItem::ManuallyDrop));
526            let provenance = (!matches!(ty.kind(), TyKind::Array(..)) && !is_manually_drop)
527                .then(|| self.local_value(place.local).and_then(|v| v.provenance.clone()))
528                .flatten()
529                .or_else(|| {
530                    self.path_state.current_frame.local_alloc
531                        .get(&place.local)
532                        .copied()
533                        .map(|alloc_id| Provenance {
534                            alloc_id,
535                            offset: zero,
536                            offset_kind: None,
537                        })
538                });
539            return Some(VmValue {
540                z3_term: base_addr,
541                ty,
542                provenance,
543                facts: ValueFacts::default(),
544                source: ValueSource::None,
545            });
546        }
547
548        let mut term = self.local_address(place.local);
549        let mut provenance: Option<Provenance<'z3>> = self.path_state
550            .current_frame.local_alloc
551            .get(&place.local)
552            .copied()
553            .map(|alloc_id| Provenance {
554                alloc_id,
555                offset: zero.clone(),
556                offset_kind: None,
557            });
558        let mut current_ty = self.body().local_decls[place.local].ty;
559        let mut field_path: Vec<usize> = Vec::new();
560        let mut view_ty = current_ty;
561
562        for proj in place.projection.iter() {
563            if let ProjectionElem::Index(local) = proj {
564                // The element stride is the *element* size, not the container
565                // size: peel `[T; N]` / `[T]` down to `T` (mirroring state.rs's
566                // `Index` arm).  Keep `max(1)` so the stride matches the array
567                // allocation's `elem_size` (`N·max(1)`), letting the SMT cancel
568                // the factor for `idx + 1 <= N`.
569                let elem_ty = match current_ty.kind() {
570                    TyKind::Array(e, _) | TyKind::Slice(e) => *e,
571                    _ => return None,
572                };
573                let elem_sz = Int::from_u64(self.z3_ctx, self.size_of_ty(elem_ty).max(1));
574                let idx = self.local_value(local)?.z3_term.clone();
575                let scaled = Int::mul(self.z3_ctx, &[&idx, &elem_sz]);
576                term = Int::add(self.z3_ctx, &[&term, &scaled]);
577                if let Some(ref mut prov) = provenance {
578                    prov.offset = Int::add(self.z3_ctx, &[&prov.offset, &scaled]);
579                }
580                current_ty = elem_ty;
581                continue;
582            }
583            match proj.kind() {
584                ProjectionElem::Field(field_idx, _) => {
585                    let fidx = field_idx.as_usize();
586                    field_path.push(fidx);
587                    let field_offset = self.field_offset_in_bytes(current_ty, fidx);
588                    let field_off = Int::from_u64(self.z3_ctx, field_offset);
589                    let field_ty = match current_ty.kind() {
590                        TyKind::Adt(adt_def, substs) => {
591                            let variant = adt_def.non_enum_variant();
592                            variant
593                                .fields
594                                .get(rustc_abi::FieldIdx::from_usize(fidx))
595                                .map(|f| mir_utils::field_ty(self.tcx, f, substs))
596                                .unwrap_or(current_ty)
597                        }
598                        _ => current_ty,
599                    };
600                    // A DST slice field (e.g. `CStr { inner: [u8] }`) carries its
601                    // own allocation so its length stays symbolic.  Prefer that
602                    // allocation over the parent struct's byte-offset address,
603                    // otherwise `&raw const self.inner` collapses the slice length
604                    // to the struct's own (minimal) size.
605                    let field_replacement = match field_ty.kind() {
606                        TyKind::Slice(_) => self
607                            .field_value(place.local, &field_path)
608                            .and_then(|fv| fv.provenance.clone().map(|p| (fv.z3_term.clone(), p))),
609                        TyKind::Array(..) => {
610                            // An array field decomposed into its own allocation by
611                            // `decompose_pointee_fields` (e.g. `keys: [MaybeUninit<K>; N]`)
612                            // carries a concrete element count. Prefer that allocation
613                            // over the parent struct's byte-offset address so
614                            // `&(*leaf).keys` keeps `len = N` for downstream InBound.
615                            let alloc = provenance.as_ref().map(|p| p.alloc_id);
616                            alloc.and_then(|a| {
617                                self.path_state.mem_units[a.0].content.values
618                                    .get(&(view_ty, field_path.clone()))
619                                    .and_then(|fv| {
620                                        fv.provenance.clone().map(|p| (fv.z3_term.clone(), p))
621                                    })
622                            })
623                        }
624                        _ => None,
625                    };
626                    match field_replacement {
627                        Some((fv_term, fv_prov)) => {
628                            term = fv_term;
629                            provenance = Some(fv_prov);
630                        }
631                        None => {
632                            term = Int::add(self.z3_ctx, &[&term, &field_off]);
633                            if let Some(ref mut prov) = provenance {
634                                prov.offset = Int::add(self.z3_ctx, &[&prov.offset, &field_off]);
635                            }
636                        }
637                    }
638                    current_ty = field_ty;
639                }
640                ProjectionElem::Deref => {
641                    field_path.clear();
642                    let pointed = self.local_value(place.local)?;
643                    term = pointed.z3_term.clone();
644                    provenance = pointed.provenance.clone();
645                    if provenance.is_none() && matches!(pointed.ty.kind(), TyKind::RawPtr(..))
646                        && let Some(field0) = self.field_value(place.local, &[0]) {
647                            provenance = field0.provenance.clone();
648                        }
649                    if let TyKind::Ref(_, deref_ty, _) = current_ty.kind() {
650                        current_ty = *deref_ty;
651                    } else if let TyKind::RawPtr(deref_ty, _) = current_ty.kind() {
652                        current_ty = *deref_ty;
653                    }
654                    view_ty = current_ty;
655                }
656                _ => {
657                    return None;
658                }
659            }
660        }
661
662        let ty = place.ty(self.body(), self.tcx).ty;
663        Some(VmValue {
664            z3_term: term,
665            ty,
666            provenance,
667            facts: ValueFacts::default(),
668            source: ValueSource::None,
669        })
670    }
671
672    /// Lazily create a stack allocation for a MIR local if one doesn't exist.
673    pub(crate) fn ensure_local_allocation(&mut self, local: Local) {
674        if self.path_state.current_frame.local_alloc.contains_key(&local) {
675            return;
676        }
677        let ty = self.body().local_decls[local].ty;
678        let align = self.align_sym(ty);
679        let name = format!("addr__{}", local.as_usize());
680        let base = Int::new_const(self.z3_ctx, name.as_str());
681        let id = AllocId(self.path_state.mem_units.len());
682        // For arrays, track the element type (not the array type) so that
683        // len() computes `size / elem_size` correctly.  When the element size
684        // is unknown (a generic `T`), `size_of::<[T; N]>()` collapses to 0, so
685        // instead record the element count `N` as a symbolic term — this keeps
686        // `len() = size / elem_size` equal to `N`, letting downstream
687        // InBound checks (e.g. `get_unchecked_mut(idx)` where `idx < N`) be
688        // discharged against the loop's `idx < N` path condition.
689        let (size_term, element_ty, slice_len) = match ty.kind() {
690            TyKind::Array(elem, const_len) => {
691                // Concrete element size (`.max(1)` so a generic `T` collapses to
692                // 1 byte, keeping `len() = size / elem_size` equal to the
693                // symbolic element count `N`).  Deliberately *not* the symbolic
694                // `size_sym(elem)`: materializing `sizeof_MaybeUninit<T>` here
695                // would let `access_bytes` read it back as an unbounded access
696                // size, breaking `Allocated(&mut MaybeUninit<T>, T, 1)` against
697                // the iterator provenance (array_try_from_fn_ext).
698                let elem_size = self.size_of_ty(*elem).max(1);
699                let n_term = self.const_len_term(const_len);
700                let size = match n_term.as_u64() {
701                    Some(n) => Int::from_u64(self.z3_ctx, n.saturating_mul(elem_size)),
702                    None => Int::mul(self.z3_ctx, &[&n_term, &Int::from_u64(self.z3_ctx, elem_size)]),
703                };
704                (size, Some(*elem), Some(n_term))
705            }
706            _ => {
707                let size = self
708                    .struct_size_sym(ty)
709                    .unwrap_or_else(|| self.size_sym(ty));
710                (size, Some(ty), None)
711            }
712        };
713        let mut alloc = Allocation::new(base, size_term, align, element_ty, AllocKind::Object);
714        if let Some(len) = slice_len {
715            alloc.set_slice_len(len);
716        }
717        self.path_state.mem_units.push(MemoryUnit {
718            allocation: alloc,
719            content: MemoryContent::default(),
720        });
721        self.path_state.current_frame.local_alloc.insert(local, id);
722    }
723
724    pub(crate) fn field_offset_in_bytes(&self, ty: Ty<'tcx>, field_idx: usize) -> u64 {
725        mir_utils::field_offset_in_bytes(
726            self.tcx,
727            self.path_state.current_frame.current_def_id,
728            ty,
729            field_idx,
730        )
731    }
732
733    pub(crate) fn size_of_ty(&self, ty: Ty<'tcx>) -> u64 {
734        mir_utils::layout_of_ty(self.tcx, self.path_state.current_frame.current_def_id, ty)
735            .map(|l| l.size.bytes())
736            .unwrap_or(0)
737    }
738
739    pub(crate) fn align_of_ty(&self, ty: Ty<'tcx>) -> u64 {
740        mir_utils::layout_of_ty(self.tcx, self.path_state.current_frame.current_def_id, ty)
741            .map(|l| mir_utils::layout_align_bytes(&l))
742            .unwrap_or(1)
743    }
744
745    pub(crate) fn allocation_size(&self, alloc_id: AllocId) -> &Int<'z3> {
746        &self.alloc(alloc_id).size
747    }
748
749    pub(crate) fn allocation_base(&self, alloc_id: AllocId) -> &Int<'z3> {
750        &self.alloc(alloc_id).base
751    }
752
753    /// Get the element size (in bytes) for a pointer type, peeling
754    /// through `*const T`, `*mut T`, `&T`, and `&[T]` to find `size_of(T)`.
755    pub(crate) fn pointee_elem_size(&self, ty: Ty<'tcx>) -> u64 {
756        let inner = match ty.kind() {
757            TyKind::RawPtr(inner_ty, _) | TyKind::Ref(_, inner_ty, _) => *inner_ty,
758            _ => ty,
759        };
760        match inner.kind() {
761            TyKind::Slice(elem) => self.size_of_ty(*elem),
762            _ => self.size_of_ty(inner),
763        }
764    }
765
766    /// Element size of `ty` as a symbolic Z3 term.  For concrete types this is
767    /// the constant byte size; for a generic type whose `size_of` is unknown
768    /// (an unconstrained `T`) it is a single reusable symbolic constant with
769    /// `>= 0` (so `T` may be a ZST).  Using the same constant everywhere (ptr
770    /// strides, access counts, allocation sizes) lets SMT cancel the factor in
771    /// `InBound`.
772    pub(crate) fn size_sym(&mut self, ty: Ty<'tcx>) -> Int<'z3> {
773        let ty = peel_slice_elem(ty);
774        if let TyKind::Array(elem, count) = ty.kind() {
775            let count = self.const_len_term(count);
776            let zero = Int::from_u64(self.z3_ctx, 0);
777            self.path_state.constraints.assertions.push(count.ge(&zero));
778            let elem_size = self.size_sym(*elem);
779            return Int::mul(self.z3_ctx, &[&count, &elem_size]);
780        }
781        let size = self.size_of_ty(ty);
782        if size > 0 || !mir_utils::ty_has_type_param(ty) {
783            return Int::from_u64(self.z3_ctx, size);
784        }
785        if let Some(s) = self.path_state.constraints.term_caches.sizes.get(&ty) {
786            return s.clone();
787        }
788        let s = self.fresh_int(&format!("sizeof_{ty}"));
789        self.path_state.constraints.term_caches.sizes.insert(ty, s.clone());
790        let zero = Int::from_u64(self.z3_ctx, 0);
791        self.path_state.constraints.assertions.push(s.ge(&zero));
792        if let TyKind::Adt(def, args) = ty.kind()
793            && (def.is_struct() || def.is_union())
794        {
795            let min_size = def
796                .non_enum_variant()
797                .fields
798                .iter()
799                .map(|field| self.size_of_ty(mir_utils::field_ty(self.tcx, field, args)))
800                .max()
801                .unwrap_or(0);
802            if min_size > 0 {
803                self.path_state.constraints
804                    .assertions
805                    .push(s.ge(&Int::from_u64(self.z3_ctx, min_size)));
806            }
807        }
808        s
809    }
810
811    /// The array length `N` as a Z3 term (concrete value or symbolic const
812    /// generic).  The symbolic name mirrors `value_of_operand`'s formatting so it
813    /// is *identical* to the `const N` term appearing in path conditions.
814    pub(crate) fn const_len_term(&self, const_len: &rustc_middle::ty::Const<'tcx>) -> Int<'z3> {
815        match const_len.try_to_target_usize(self.tcx) {
816            Some(v) => Int::from_u64(self.z3_ctx, v),
817            None => self.symbolic_const_term(&rustc_middle::mir::Const::Ty(
818                self.tcx.types.usize,
819                *const_len,
820            )),
821        }
822    }
823
824    /// Read-only sibling of [`size_sym`](Self::size_sym): returns the symbolic
825    /// size for `ty`, falling back to `1` when the symbolic constant has not
826    /// been created yet (e.g. a checker invoked before the exec phase created
827    /// it).  Non-ZST concrete types return their constant byte size; a concrete
828    /// ZST or a not-yet-created generic constant falls back to `1` — a non-zero
829    /// element size keeps `size / elem_size` derivations from dividing by zero.
830    pub(crate) fn size_sym_read(&self, ty: Ty<'tcx>) -> Int<'z3> {
831        let ty = peel_slice_elem(ty);
832        if let TyKind::Array(elem, count) = ty.kind() {
833            let count = self.const_len_term(count);
834            let elem_size = self.size_sym_read(*elem);
835            return Int::mul(self.z3_ctx, &[&count, &elem_size]);
836        }
837        let size = self.size_of_ty(ty);
838        if size > 0 {
839            return Int::from_u64(self.z3_ctx, size);
840        }
841        self.path_state.constraints.term_caches.sizes
842            .get(&ty)
843            .cloned()
844            .unwrap_or_else(|| Int::from_u64(self.z3_ctx, 1))
845    }
846
847    /// The *symbolic* element-size term of `alloc_id`'s element type, when it is
848    /// a generic type parameter (so it may be `0` for a ZST or `≥ 1` for a
849    /// non-ZST).  Returns `None` for concrete element types, where the size is a
850    /// known constant and no case split is needed.
851    pub(crate) fn generic_elem_size(&self, alloc_id: AllocId) -> Option<Int<'z3>> {
852        let elem_ty = self.alloc(alloc_id).element_ty.as_ty()?;
853        if !mir_utils::ty_has_type_param(elem_ty) {
854            return None;
855        }
856        let s = self.size_sym_read(elem_ty);
857        if s.simplify().as_u64().is_some() {
858            return None;
859        }
860        Some(s)
861    }
862
863    /// Alignment of `ty` as a symbolic Z3 term.  For a concrete type this is
864    /// the constant byte alignment; for a generic type it is a reusable
865    /// symbolic constant `align_T` with `>= 1`, lower-bounded by the trait
866    /// bounds' minimum alignment, and linked to the element size by the layout
867    /// constraint `sizeof_T % align_T == 0` (a type's size is always a multiple
868    /// of its alignment).  For a generic struct, its alignment is additionally
869    /// constrained to be a multiple of each field's alignment, so a field
870    /// pointer (`(*node).value`) inherits the container's alignment.
871    pub(crate) fn align_sym(&mut self, ty: Ty<'tcx>) -> Int<'z3> {
872        let ty = peel_slice_elem(ty);
873        if let TyKind::Array(elem, _) = ty.kind() {
874            return self.align_sym(*elem);
875        }
876        let align = self.align_of_ty(ty);
877        if align > 1 || !mir_utils::ty_has_type_param(ty) {
878            return Int::from_u64(self.z3_ctx, align);
879        }
880        if let Some(a) = self.path_state.constraints.term_caches.aligns.get(&ty) {
881            return a.clone();
882        }
883        let a = self.fresh_int(&format!("align_{ty}"));
884        self.path_state.constraints.term_caches.aligns.insert(ty, a.clone());
885        let one = Int::from_u64(self.z3_ctx, 1);
886        let zero = Int::from_u64(self.z3_ctx, 0);
887        self.path_state.constraints.assertions.push(a.ge(&one));
888        // Lower bound from the trait bounds (0 for an unconstrained `T`): any
889        // implementor is at least this aligned.
890        let min_a =
891            mir_utils::min_align_of_generic_param(self.tcx, self.path_state.current_frame.current_def_id, ty);
892        if min_a > 1 {
893            self.path_state.constraints.assertions
894                .push(a.ge(&Int::from_u64(self.z3_ctx, min_a)));
895        }
896        // Upper bound from the trait bounds (0 for an unconstrained `T`): any
897        // implementor is at most this aligned, which is what lets a cross-cast
898        // from a *more* aligned source (`&[U]` -> `*const T`) be discharged.
899        let max_a =
900            mir_utils::max_align_of_generic_param(self.tcx, self.path_state.current_frame.current_def_id, ty);
901        if max_a > 0 {
902            self.path_state.constraints.assertions
903                .push(a.le(&Int::from_u64(self.z3_ctx, max_a)));
904        }
905        // A struct's alignment is a multiple of each field's alignment (both
906        // are powers of two).  Pointer fields have a *concrete* alignment, so
907        // this terminates even for recursively-defined containers.
908        if let TyKind::Adt(adt_def, substs) = ty.kind()
909            && !adt_def.is_enum() {
910                let variant = adt_def.non_enum_variant();
911                for field in variant.fields.iter() {
912                    let field_ty = mir_utils::field_ty(self.tcx, field, substs);
913                    let field_align = self.align_sym(field_ty);
914                    self.path_state.constraints.assertions.push(a.rem(&field_align)._eq(&zero));
915                    // Linear lower bound: a struct/union's alignment is at least
916                    // each field's alignment (both powers of two), so Z3 can
917                    // decide `align_struct >= align_field` without chaining the
918                    // nonlinear `% == 0` (e.g. `align_of(MaybeUninit<T>) >=
919                    // align_of(T)` for `swap`'s scratch slot).
920                    self.path_state.constraints.assertions.push(a.ge(&field_align));
921                }
922                // A struct's size is at least the sum of its fields (padding may
923                // add more).  This relates the symbolic `sizeof_Struct` constant
924                // to the field-sum that `size_of::<Struct>()` lowers to (e.g.
925                // `SIZE<LeafNode> + SIZE<[...; 12]>` for `InternalNode`), so
926                // `Allocated(p, u8, layout.size)` is discharged against the
927                // allocation size.
928                if let Some(sum) = self.struct_size_sym(ty) {
929                    let size = self.size_sym(ty);
930                    self.path_state.constraints.assertions.push(size.ge(&sum));
931                }
932            }
933        let size = self.size_sym(ty);
934        self.path_state.constraints.assertions.push(size.rem(&a)._eq(&zero));
935        a
936    }
937
938    /// Read-only sibling of [`align_sym`](Self::align_sym): returns the
939    /// symbolic alignment for `ty`, falling back to the trait bounds' minimum
940    /// alignment when the constant has not been created yet (e.g. a generic `U`
941    /// that only appears in a cast/contract, never as an allocation element
942    /// type).  Concrete types return their constant alignment.
943    pub(crate) fn align_sym_read(&self, ty: Ty<'tcx>) -> Int<'z3> {
944        let ty = peel_slice_elem(ty);
945        if let TyKind::Array(elem, _) = ty.kind() {
946            return self.align_sym_read(*elem);
947        }
948        let align = self.align_of_ty(ty);
949        if align > 1 {
950            return Int::from_u64(self.z3_ctx, align);
951        }
952        if let Some(a) = self.path_state.constraints.term_caches.aligns.get(&ty) {
953            return a.clone();
954        }
955        let min_a =
956            mir_utils::min_align_of_generic_param(self.tcx, self.path_state.current_frame.current_def_id, ty);
957        Int::from_u64(self.z3_ctx, min_a.max(1))
958    }
959
960    /// Size of a struct/ADT as the *sum* of its fields' sizes (each via
961    /// [`size_sym`](Self::size_sym)).  This lower-bounds the real layout so a
962    /// field reference (`Allocated(&alloc)`) can be discharged against the
963    /// struct allocation (`sizeof_A <= 8 + 8 + sizeof_A`).  Returns `None` for
964    /// non-ADT or enum types.
965    pub(crate) fn struct_size_sym(&mut self, ty: Ty<'tcx>) -> Option<Int<'z3>> {
966        let TyKind::Adt(adt_def, substs) = ty.kind() else {
967            return None;
968        };
969        if adt_def.is_enum() {
970            return None;
971        }
972        let concrete = self.size_of_ty(ty);
973        if concrete > 0 {
974            return Some(Int::from_u64(self.z3_ctx, concrete));
975        }
976        let variant = adt_def.non_enum_variant();
977        let mut total = Int::from_u64(self.z3_ctx, 0);
978        for field in variant.fields.iter() {
979            let field_ty = mir_utils::field_ty(self.tcx, field, substs);
980            let field_size = self
981                .struct_size_sym(field_ty)
982                .unwrap_or_else(|| self.size_sym(field_ty));
983            total = Int::add(self.z3_ctx, &[&total, &field_size]);
984        }
985        Some(total)
986    }
987
988
989    /// The shared `UNINIT` sentinel (≥ 256, outside the `u8` range).
990    fn uninit_byte(&self) -> Int<'z3> {
991        self.path_state.constraints
992            .term_caches
993            .uninit_byte
994            .clone()
995            .expect("uninit_byte is initialized in VmExecutor::new")
996    }
997
998    /// A fresh `Array<Int, Int>` whose every offset reads `UNINIT`.
999    fn fresh_byte_array(&self) -> Array<'z3> {
1000        // `const_array(domain, value)` takes the *index* sort; the array sort is
1001        // inferred as `Array<domain, value_sort>` (here `Array<Int, Int>`).
1002        Array::const_array(self.z3_ctx, &Sort::int(self.z3_ctx), &self.uninit_byte())
1003    }
1004
1005    /// Read `byte[i]` at a (possibly symbolic) offset; unwritten offsets read `UNINIT`.
1006    ///
1007    /// The result is simplified so a `select(store(…), i)` chain (built up by
1008    /// repeated `byte_write` / `copy_byte_tracking`) collapses to its constant
1009    /// byte value when `i` is concrete, rather than leaking the nested
1010    /// `select`/`store` expression into downstream SMT obligations.
1011    pub(crate) fn byte_read(&self, alloc_id: AllocId, i: &Int<'z3>) -> Int<'z3> {
1012        match &self.path_state.mem_units[alloc_id.0].content.byte_array {
1013            Some(arr) => arr.select(i).as_int().expect("byte array range is Int").simplify(),
1014            None => self.uninit_byte(),
1015        }
1016    }
1017
1018    pub(crate) fn fill_byte_array(&mut self, pointer: &VmValue<'z3, 'tcx>, byte: u64) -> bool {
1019        let Some(ty) = mir_utils::pointee_ty(pointer.ty) else {
1020            return false;
1021        };
1022        let TyKind::Array(element, _) = ty.kind() else {
1023            return false;
1024        };
1025        if !matches!(element.kind(), TyKind::Uint(rustc_middle::ty::UintTy::U8)) {
1026            return false;
1027        }
1028        let size = self.size_of_ty(ty) as usize;
1029        if size == 0 {
1030            return true;
1031        }
1032        if size > 256 {
1033            return false;
1034        }
1035        let Some(provenance) = pointer.provenance.as_ref() else {
1036            return false;
1037        };
1038        let Some(offset) = provenance.offset.simplify().as_u64() else {
1039            return false;
1040        };
1041        let Some(end) = offset.checked_add(size as u64) else {
1042            return false;
1043        };
1044        if !self
1045            .allocation_size(provenance.alloc_id)
1046            .simplify()
1047            .as_u64()
1048            .is_some_and(|allocation_size| end <= allocation_size)
1049        {
1050            return false;
1051        }
1052        let alloc_id = provenance.alloc_id;
1053        let local_path = self.path_state.current_frame.local_alloc.iter().find_map(|(local, id)| {
1054            if *id != alloc_id {
1055                return None;
1056            }
1057            let root_ty = self.body().local_decls[*local].ty;
1058            let path = if root_ty == ty && offset == 0 {
1059                Some(Vec::new())
1060            } else {
1061                self.field_path_at_offset(root_ty, offset, ty)
1062            }?;
1063            Some((*local, path))
1064        });
1065        let content = self.content_mut(alloc_id);
1066        content.values.clear();
1067        content.indexed_elements.clear();
1068        content.indexed_elements_modified = true;
1069        content.copied_prefix = None;
1070        let value = Int::from_u64(self.z3_ctx, byte);
1071        for index in offset..end {
1072            self.record_byte_value(alloc_id, index as usize, value.clone());
1073        }
1074        if let Some((local, path)) = local_path {
1075            for index in 0..size {
1076                let mut element_path = path.clone();
1077                element_path.push(index);
1078                let mut element_value = VmValue::new(value.clone(), *element);
1079                element_value.facts.init = true;
1080                self.write_local_path(local, element_path, element_value);
1081            }
1082            if path.is_empty() {
1083                self.content_mut(alloc_id).indexed_elements_modified = false;
1084            }
1085        }
1086        if offset == 0 && end == self.allocation_size(alloc_id).simplify().as_u64().unwrap_or(0) {
1087            self.content_mut(alloc_id).facts.initialized = true;
1088        }
1089        true
1090    }
1091
1092    /// Write `byte[i] = v`.
1093    pub(crate) fn byte_write(&mut self, alloc_id: AllocId, i: &Int<'z3>, v: &Int<'z3>) {
1094        self.clear_write_evidence(alloc_id);
1095        let offset = i.simplify();
1096        let arr = self.path_state.mem_units[alloc_id.0].content.byte_array.clone();
1097        let updated = match arr {
1098            Some(a) => a.store(&offset, v),
1099            None => self.fresh_byte_array().store(&offset, v),
1100        };
1101        let unit = &mut self.path_state.mem_units[alloc_id.0];
1102        unit.content.byte_array = Some(updated);
1103        if let Some(off) = offset.as_u64() {
1104            unit.content.byte_written.insert(off as usize);
1105        }
1106    }
1107
1108    /// Record a per-byte symbolic value at a concrete offset in an allocation.
1109    pub(crate) fn record_byte_value(&mut self, alloc_id: AllocId, offset: usize, term: Int<'z3>) {
1110        self.byte_write(alloc_id, &Int::from_u64(self.z3_ctx, offset as u64), &term);
1111    }
1112
1113    /// Mark a byte as initialized (written) with an unknown value.
1114    pub(crate) fn mark_byte_init(&mut self, alloc_id: AllocId, offset: usize) {
1115        let unknown = self.fresh_int("byte_unknown");
1116        self.byte_write(alloc_id, &Int::from_u64(self.z3_ctx, offset as u64), &unknown);
1117    }
1118
1119    /// Whether a byte at a concrete offset was written (`select != UNINIT`).
1120    pub(crate) fn is_byte_init(&self, alloc_id: AllocId, offset: usize) -> bool {
1121        let v = self.byte_read(alloc_id, &Int::from_u64(self.z3_ctx, offset as u64));
1122        !v.simplify().eq(&self.uninit_byte())
1123    }
1124
1125    /// Whether a byte at a concrete offset is known NUL.
1126    pub(crate) fn is_byte_nul(&self, alloc_id: AllocId, offset: usize) -> bool {
1127        self.byte_read(alloc_id, &Int::from_u64(self.z3_ctx, offset as u64))
1128            .simplify()
1129            .as_u64()
1130            == Some(0)
1131    }
1132
1133    /// Whether a byte at a concrete offset is known non-NUL.
1134    pub(crate) fn is_byte_non_nul(&self, alloc_id: AllocId, offset: usize) -> bool {
1135        self.byte_read(alloc_id, &Int::from_u64(self.z3_ctx, offset as u64))
1136            .simplify()
1137            .as_u64()
1138            .is_some_and(|v| v != 0)
1139    }
1140
1141    /// Enumerate `(offset, term)` pairs for the *written* bytes of an allocation,
1142    /// in ascending offset order.
1143    pub(crate) fn alloc_byte_values(&self, alloc_id: AllocId) -> Vec<(usize, Int<'z3>)> {
1144        let mut offs: Vec<usize> = self.path_state.mem_units[alloc_id.0]
1145            .content
1146            .byte_written
1147            .iter()
1148            .copied()
1149            .collect();
1150        offs.sort_unstable();
1151        offs.into_iter()
1152            .map(|off| (off, self.byte_read(alloc_id, &Int::from_u64(self.z3_ctx, off as u64))))
1153            .collect()
1154    }
1155
1156    /// Offsets known to be NUL.
1157    pub(crate) fn alloc_nul_offsets(&self, alloc_id: AllocId) -> Vec<usize> {
1158        let mut offs: Vec<usize> = self.path_state.mem_units[alloc_id.0]
1159            .content
1160            .byte_written
1161            .iter()
1162            .copied()
1163            .filter(|&off| self.is_byte_nul(alloc_id, off))
1164            .collect();
1165        offs.sort_unstable();
1166        offs
1167    }
1168
1169    /// Offsets known to be non-NUL.
1170    pub(crate) fn alloc_non_nul_offsets(&self, alloc_id: AllocId) -> Vec<usize> {
1171        let mut offs: Vec<usize> = self.path_state.mem_units[alloc_id.0]
1172            .content
1173            .byte_written
1174            .iter()
1175            .copied()
1176            .filter(|&off| self.is_byte_non_nul(alloc_id, off))
1177            .collect();
1178        offs.sort_unstable();
1179        offs
1180    }
1181
1182    /// Copy the per-byte state (values + written-offset bound) of one allocation
1183    /// to another, shifting by `src_offset` so `dst[i] = src[i + src_offset]`.
1184    pub(crate) fn copy_byte_tracking(&mut self, src: AllocId, src_offset: usize, dst: AllocId) {
1185        let written: Vec<usize> = self.path_state.mem_units[src.0]
1186            .content
1187            .byte_written
1188            .iter()
1189            .copied()
1190            .filter(|&off| off >= src_offset)
1191            .collect();
1192        for off in written {
1193            let v = self.byte_read(src, &Int::from_u64(self.z3_ctx, off as u64));
1194            self.byte_write(dst, &Int::from_u64(self.z3_ctx, (off - src_offset) as u64), &v);
1195        }
1196    }
1197
1198
1199    /// The value at a field offset *within an allocation* viewed as `view_ty`.
1200    ///
1201    /// This is the memory-contents (typed-value) layer ([`MemoryContent::values`]): the
1202    /// single source of truth for field values. [`Self::field_value`] is the
1203    /// local-facing wrapper that resolves a MIR local's backing allocation and
1204    /// declared type, then reads this same layer. The viewed type is part of the
1205    /// key so reinterpret casts (`LeafNode` ↔ `InternalNode`) resolve to the
1206    /// right field view.
1207    pub(crate) fn load_value(
1208        &self,
1209        alloc_id: AllocId,
1210        view_ty: Ty<'tcx>,
1211        path: &[usize],
1212    ) -> Option<&VmValue<'z3, 'tcx>> {
1213        self.path_state.mem_units[alloc_id.0]
1214            .content
1215            .values
1216            .get(&(view_ty, path.to_vec()))
1217    }
1218
1219    /// Store a value at a field offset *within an allocation* viewed as `view_ty`.
1220    ///
1221    /// This is the write counterpart to [`Self::load_value`] on the same
1222    /// memory-contents layer ([`MemoryContent::values`]); the viewed type is part of the
1223    /// key so reinterpret casts resolve to the right field view.
1224    pub(crate) fn store_value(
1225        &mut self,
1226        alloc_id: AllocId,
1227        view_ty: Ty<'tcx>,
1228        path: Vec<usize>,
1229        value: VmValue<'z3, 'tcx>,
1230    ) {
1231        self.path_state.mem_units[alloc_id.0].content.values.insert((view_ty, path), value);
1232    }
1233
1234    /// Encode the UTF-8 validity DFA over this allocation's tracked bytes.
1235    /// Returns `None` when no bytes are tracked (validity is trivially
1236    /// satisfied), so callers can short-circuit to "proved".
1237    pub(crate) fn utf8_validity(&self, alloc_id: AllocId) -> Option<Bool<'z3>> {
1238        let byte_pairs = self.alloc_byte_values(alloc_id);
1239        if byte_pairs.is_empty() {
1240            return None;
1241        }
1242        let bytes: Vec<Int<'z3>> = byte_pairs.into_iter().map(|(_, t)| t).collect();
1243        Some(utf8_validity_dfa(self.z3_ctx, &bytes))
1244    }
1245}
1246
1247/// Build the boolean expression "`bytes` form a valid UTF-8 sequence".
1248///
1249/// Encodes the UTF-8 DFA over the per-byte Z3 terms: every byte is ASCII, a
1250/// continuation byte, or a valid lead byte, and a `k`-byte lead must be
1251/// followed by exactly `k-1` continuation bytes.  Value-range refinements
1252/// reject overlong encodings, surrogates (U+D800..=U+DFFF), and code points
1253/// above U+10FFFF.
1254fn utf8_validity_dfa<'z3>(z3_ctx: &'z3 Context, bytes: &[Int<'z3>]) -> Bool<'z3> {
1255    let zero = Int::from_u64(z3_ctx, 0);
1256    let one = Int::from_u64(z3_ctx, 1);
1257    let two = Int::from_u64(z3_ctx, 2);
1258    let three = Int::from_u64(z3_ctx, 3);
1259
1260    let c_0x80 = Int::from_u64(z3_ctx, 0x80);
1261    let c_0xc0 = Int::from_u64(z3_ctx, 0xC0);
1262    let c_0xc2 = Int::from_u64(z3_ctx, 0xC2);
1263    let c_0xe0 = Int::from_u64(z3_ctx, 0xE0);
1264    let c_0xf0 = Int::from_u64(z3_ctx, 0xF0);
1265    let c_0xf5 = Int::from_u64(z3_ctx, 0xF5);
1266    let c_0xa0 = Int::from_u64(z3_ctx, 0xA0);
1267    let c_0x90 = Int::from_u64(z3_ctx, 0x90);
1268    let c_0xed = Int::from_u64(z3_ctx, 0xED);
1269    let c_0xf4 = Int::from_u64(z3_ctx, 0xF4);
1270
1271    let mut valid = Bool::from_bool(z3_ctx, true);
1272    let mut state = zero.clone();
1273    let mut lead = zero.clone();
1274
1275    for b in bytes {
1276        let is_ascii = b.lt(&c_0x80);
1277        let is_cont = b.ge(&c_0x80) & b.lt(&c_0xc0);
1278        let is_2lead = b.ge(&c_0xc2) & b.lt(&c_0xe0);
1279        let is_3lead = b.ge(&c_0xe0) & b.lt(&c_0xf0);
1280        let is_4lead = b.ge(&c_0xf0) & b.lt(&c_0xf5);
1281
1282        let refine_3 =
1283            (lead._eq(&c_0xe0).not() | b.ge(&c_0xa0)) & (lead._eq(&c_0xed).not() | b.lt(&c_0xa0));
1284        let refine_4 =
1285            (lead._eq(&c_0xf0).not() | b.ge(&c_0x90)) & (lead._eq(&c_0xf4).not() | b.lt(&c_0x90));
1286
1287        let valid_s0 = is_ascii.clone() | is_2lead.clone() | is_3lead.clone() | is_4lead.clone();
1288        let valid_s1 = is_cont.clone();
1289        let valid_s2 = is_cont.clone() & refine_3;
1290        let valid_s3 = is_cont.clone() & refine_4;
1291
1292        let state0 = state._eq(&zero);
1293        let state1 = state._eq(&one);
1294        let state2 = state._eq(&two);
1295
1296        let byte_valid = Bool::ite(
1297            &state0,
1298            &valid_s0,
1299            &Bool::ite(
1300                &state1,
1301                &valid_s1,
1302                &Bool::ite(&state2, &valid_s2, &valid_s3),
1303            ),
1304        );
1305
1306        let new_state_s0 = Bool::ite(
1307            &is_ascii,
1308            &zero,
1309            &Bool::ite(&is_2lead, &one, &Bool::ite(&is_3lead, &two, &three)),
1310        );
1311        let new_state_cont = Bool::ite(&state1, &zero, &Bool::ite(&state2, &one, &two));
1312        let new_state = Bool::ite(&state0, &new_state_s0, &new_state_cont);
1313
1314        valid &= byte_valid;
1315        let is_lead34 = is_3lead | is_4lead;
1316        lead = Bool::ite(&(state0 & is_lead34), b, &lead);
1317        state = new_state;
1318    }
1319
1320    valid &= state._eq(&zero);
1321    valid
1322}
1323
1324/// Peel a slice type `[T]` to its element `T` (other types unchanged).
1325fn peel_slice_elem(ty: Ty<'_>) -> Ty<'_> {
1326    match ty.kind() {
1327        TyKind::Slice(elem) => *elem,
1328        _ => ty,
1329    }
1330}
1331
1332impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
1333    /// Find the local whose symbolic address matches `term` (the address a
1334    /// reference value points at). Used to resolve a `&self`/`&mut self`
1335    /// receiver (often a reborrow temp) back to the referent local that carries
1336    /// the materialized field values.
1337    pub(crate) fn find_local_by_address(&self, term: &Int<'z3>) -> Option<Local> {
1338        for (local, id) in &self.path_state.current_frame.local_alloc {
1339            if self.path_state.mem_units[id.0].allocation.base == *term {
1340                return Some(*local);
1341            }
1342        }
1343        None
1344    }
1345
1346    pub(crate) fn write_through_pointer(
1347        &mut self,
1348        pointer: &VmValue<'z3, 'tcx>,
1349        path: Vec<usize>,
1350        value: VmValue<'z3, 'tcx>,
1351    ) -> bool {
1352        let full_inner_write = pointer.provenance.as_ref().and_then(|prov| {
1353            let ty = self.alloc(prov.alloc_id).element_ty.as_ty()?;
1354            match ty.kind() {
1355                TyKind::Adt(def, args)
1356                    if type_ids::is_maybe_uninit_type(def.did())
1357                        && path.is_empty()
1358                        && prov.offset.simplify().as_u64() == Some(0)
1359                        && value.facts.init =>
1360                {
1361                    args.first()
1362                        .and_then(|arg| arg.as_type())
1363                        .filter(|inner| *inner == value.ty)
1364                        .map(|inner| (prov.alloc_id, inner))
1365                }
1366                _ => None,
1367            }
1368        });
1369        if let Some(prov) = &pointer.provenance {
1370            self.clear_write_evidence(prov.alloc_id);
1371            if !path.is_empty()
1372                && path.iter().all(|field| *field == 0)
1373                && value.facts.init
1374                && matches!(mir_utils::pointee_ty(pointer.ty).map(|ty| ty.kind()),
1375                    Some(TyKind::Adt(def, args))
1376                        if type_ids::is_maybe_uninit_type(def.did())
1377                            && args.first().and_then(|arg| arg.as_type()) == Some(value.ty))
1378                && let Some(offset) = prov.offset.simplify().as_u64()
1379            {
1380                let end = offset.saturating_add(self.size_of_ty(value.ty)).min(4096);
1381                for byte in offset..end {
1382                    self.mark_byte_init(prov.alloc_id, byte as usize);
1383                }
1384            }
1385        }
1386        if path.is_empty()
1387            && let Some(prov) = &pointer.provenance
1388            && self.path_state
1389                .static_allocs
1390                .values()
1391                .any(|id| *id == prov.alloc_id)
1392            && prov.offset.simplify().as_u64() == Some(0)
1393            && self.alloc(prov.alloc_id).element_ty.as_ty() == Some(value.ty)
1394        {
1395            self.clear_write_evidence(prov.alloc_id);
1396            self.store_value(prov.alloc_id, value.ty, Vec::new(), value);
1397            self.content_mut(prov.alloc_id).facts.initialized = true;
1398            return true;
1399        }
1400        let caller_referent =
1401            self.path_state.inline
1402                .arg_referents
1403                .iter()
1404                .enumerate()
1405                .find_map(|(i, referent)| {
1406                    let param = Local::from_usize(i + 1);
1407                    self.local_value(param)
1408                        .filter(|arg| arg.z3_term == pointer.z3_term)
1409                        .and_then(|_| *referent)
1410                });
1411        if let Some(local) = caller_referent {
1412            let path = match &pointer.source {
1413                super::state::ValueSource::FieldBorrow { fields, .. } => {
1414                    let mut full = fields.clone();
1415                    full.extend(path);
1416                    full
1417                }
1418                _ => path,
1419            };
1420            let wrote_object = path.is_empty()
1421                && pointer.provenance.as_ref().is_some_and(|prov| {
1422                    self.alloc(prov.alloc_id).is_external()
1423                        && self.alloc(prov.alloc_id).element_ty.as_ty() != Some(value.ty)
1424                })
1425                && self.write_provenance_allocation(pointer, value.clone());
1426            self.path_state.inline.deferred_field_writes.push((local, path, value));
1427            if let Some((id, ty)) = full_inner_write {
1428                self.content_mut(id).facts.written_pointee_ty = Some(ty);
1429            }
1430            return wrote_object;
1431        }
1432        if path.is_empty()
1433            && let Some(prov) = &pointer.provenance
1434            && prov.offset.simplify().as_u64() == Some(0)
1435            && self.alloc(prov.alloc_id).element_ty.as_ty() == Some(value.ty)
1436            && matches!(
1437                self.alloc(prov.alloc_id).kind,
1438                super::state::AllocKind::Object
1439            )
1440            && self.find_local_by_address(&pointer.z3_term).is_none()
1441        {
1442            self.clear_write_evidence(prov.alloc_id);
1443            let content = self.content_mut(prov.alloc_id);
1444            content.values.clear();
1445            content.indexed_elements.clear();
1446            content.indexed_elements_modified = true;
1447            content.clear_byte_writes();
1448            content.facts.initialized = value.facts.init;
1449            self.store_value(prov.alloc_id, value.ty, Vec::new(), value);
1450            return true;
1451        }
1452        if path.is_empty() && self.write_provenance_allocation(pointer, value.clone()) {
1453            if let Some((id, ty)) = full_inner_write {
1454                self.content_mut(id).facts.written_pointee_ty = Some(ty);
1455                self.content_mut(id).facts.inner_uninit = false;
1456            }
1457            return true;
1458        }
1459        if let Some(local) = self.find_local_by_address(&pointer.z3_term) {
1460            self.write_local_path(local, path, value);
1461            if let Some((id, ty)) = full_inner_write {
1462                self.content_mut(id).facts.written_pointee_ty = Some(ty);
1463                self.content_mut(id).facts.inner_uninit = false;
1464            }
1465            true
1466        } else if path.is_empty() {
1467            self.invalidate_provenance_allocation(pointer);
1468            false
1469        } else {
1470            false
1471        }
1472    }
1473
1474}