Skip to main content

rapx/vm/
container.rs

1//! Container layout, length, and backing-allocation queries.
2
3use rustc_middle::{
4    mir::Local,
5    ty::{Ty, TyKind},
6};
7use z3::ast::{Ast, Int};
8
9use crate::def_ids::type_ids;
10use crate::compat::GenericArgsRef;
11use crate::util::mir_utils;
12
13use super::state::{AllocId, Provenance, ValueFacts, ValueSource, VmExecutor, VmValue};
14
15impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
16    pub(crate) fn materialize_slice_ref_return(&mut self, dest: Local) {
17        let Some(mut value) = self.local_value(dest).cloned() else {
18            return;
19        };
20        let TyKind::Ref(_, slice, _) = value.ty.kind() else {
21            return;
22        };
23        let ValueSource::SliceLen(len) = &value.source else {
24            return;
25        };
26        let Some(parent) = value.provenance.as_ref() else {
27            return;
28        };
29        let parent_id = parent.alloc_id;
30        let elem = match slice.kind() {
31            TyKind::Slice(elem) => *elem,
32            TyKind::Alias(..) => match self.alloc(parent_id).element_ty.as_ty() {
33                Some(elem) => elem,
34                None => return,
35            },
36            _ => return,
37        };
38        let parent_offset = parent.offset.simplify().as_u64();
39        let len = len.clone();
40        let align = self.align_sym(elem);
41        let size = self.size_sym(elem);
42        let (view_id, _) = self.allocate_slice(len, size, align.clone(), Some(elem));
43        self.alloc_mut(view_id).base = value.z3_term.clone();
44        self.alloc_mut(view_id).parent = Some(parent_id);
45        if !self.alloc(parent_id).facts.dead {
46            self.content_mut(view_id).facts.initialized = true;
47        }
48        if let Some(offset) = parent_offset {
49            self.copy_byte_tracking(parent_id, offset as usize, view_id);
50        }
51        value.provenance = Some(Provenance {
52            alloc_id: view_id,
53            offset: Int::from_u64(self.z3_ctx, 0),
54            offset_kind: None,
55        });
56        value.facts.non_null = true;
57        value.facts.in_bounds = true;
58        value.facts.align_n = Some(align);
59        self.set_local(dest, value);
60    }
61
62    /// The slice/array element count for an allocation: the materialized
63    /// `slice_len`, or `size / elem_size` as a fallback for allocations created
64    /// before materialization (e.g. some call effects).  Uses the symbolic
65    /// element size (`size_sym_read`) so `len = (len·S) / S` cancels to `len`
66    /// for a generic element type — mirroring `set_len_from_alloc`.  Returns
67    /// `None` when the element type is unknown.
68    pub(crate) fn slice_len_of_alloc(&self, alloc_id: AllocId) -> Option<Int<'z3>> {
69        let alloc = self.alloc(alloc_id);
70        if let Some(len) = alloc.slice_len() {
71            return Some(len.clone());
72        }
73        if alloc.has_unbounded_size() {
74            return None;
75        }
76        let elem_ty = alloc.element_ty.as_ty()?;
77        let elem_term = self.size_sym_read(elem_ty);
78        if elem_term.simplify().as_u64() == Some(1) {
79            return Some(alloc.size.clone());
80        }
81        Some(alloc.size.div(&elem_term))
82    }
83
84    /// The slice length of a `&[T]` / `&mut [T]` value, from pointer metadata
85    /// when available or its provenance allocation otherwise.
86    pub(crate) fn slice_len_from_value(&self, val: &VmValue<'z3, 'tcx>) -> Option<Int<'z3>> {
87        if let ValueSource::SliceLen(len) = &val.source {
88            return Some(len.clone());
89        }
90        self.slice_len_of_alloc(val.provenance_alloc_id()?)
91    }
92
93    /// Resolve `x.len()` for a pointer whose pointee ADT carries a `len` field
94    /// (e.g. `NodeRef<LeafNode>`: `len()` reads `(*ptr).len`).  Returns the
95    /// pointee's `len` field term, or `None` when the pointee has no such field.
96    pub(crate) fn try_adt_len_field(&self, val: &VmValue<'z3, 'tcx>) -> Option<Int<'z3>> {
97        let alloc_id = val.provenance_alloc_id()?;
98        let elem_ty = self.alloc(alloc_id).element_ty.as_ty()?;
99        self.try_adt_len_field_at(alloc_id, elem_ty, elem_ty, &[])
100    }
101
102    /// Resolve a `len` field on `ty`, recursing into ADT sub-fields when there is
103    /// no direct `len` (e.g. `String { vec: Vec { ptr, len, cap } }` resolves
104    /// `String.len()` to `vec.len`).  `root_ty` stays fixed as the allocation's
105    /// element type, which is how `decompose_pointee_fields` keys `MemoryContent::values`.
106    fn try_adt_len_field_at(
107        &self,
108        alloc_id: AllocId,
109        ty: Ty<'tcx>,
110        root_ty: Ty<'tcx>,
111        prefix: &[usize],
112    ) -> Option<Int<'z3>> {
113        let rustc_middle::ty::TyKind::Adt(adt_def, substs) = ty.kind() else {
114            return None;
115        };
116        if !adt_def.is_struct() {
117            return None;
118        }
119        let variant = adt_def.non_enum_variant();
120        if let Some(len_idx) = variant
121            .fields
122            .iter()
123            .position(|f| f.ident(self.tcx).name.to_string() == "len")
124        {
125            let mut path = prefix.to_vec();
126            path.push(len_idx);
127            return self.path_state.mem_units[alloc_id.0].content.values
128                .get(&(root_ty, path))
129                .map(|v| v.z3_term.clone());
130        }
131        for (idx, field_def) in variant.fields.iter().enumerate() {
132            let field_ty = mir_utils::field_ty(self.tcx, field_def, substs);
133            if matches!(field_ty.kind(), rustc_middle::ty::TyKind::Adt(_, _)) {
134                let mut path = prefix.to_vec();
135                path.push(idx);
136                if let Some(len) = self.try_adt_len_field_at(alloc_id, field_ty, root_ty, &path) {
137                    return Some(len);
138                }
139            }
140        }
141        None
142    }
143
144    /// Resolve `len()` for `core::ops::IndexRange` (a private `{ start, end }`
145    /// struct): `len() = end - start`.  The `len` field lookup above misses it
146    /// because `IndexRange` has no `len` field — its `len()` computes the
147    /// difference of its two private fields.
148    pub(crate) fn try_index_range_len(&self, val: &VmValue<'z3, 'tcx>) -> Option<Int<'z3>> {
149        let rustc_middle::ty::TyKind::Adt(adt_def, _) = val.ty.kind() else {
150            return None;
151        };
152        if !type_ids::is_index_range(adt_def.did()) {
153            return None;
154        }
155        let alloc_id = val.provenance_alloc_id()?;
156        let view_ty = mir_utils::pointee_ty(val.ty).unwrap_or(val.ty);
157        let start = self.path_state
158            .mem_units[alloc_id.0].content.values
159            .get(&(view_ty, vec![0]))?
160            .z3_term
161            .clone();
162        let end = self.path_state
163            .mem_units[alloc_id.0].content.values
164            .get(&(view_ty, vec![1]))?
165            .z3_term
166            .clone();
167        Some(Int::sub(self.z3_ctx, &[&end, &start]))
168    }
169
170    /// Resolve `len()` of a slice/ADT value: the pointee ADT's `len` field, then
171    /// the materialized slice length, then `size / elem_size`.  Shared by the
172    /// exec- and checker-side `Len` evaluators so the fallback chain is defined
173    /// once.
174    pub(crate) fn len_from_value(&self, val: &VmValue<'z3, 'tcx>) -> Option<Int<'z3>> {
175        if let Some(len) = self.try_adt_len_field(val) {
176            return Some(len);
177        }
178        if let Some(len) = self.try_index_range_len(val) {
179            return Some(len);
180        }
181        let mut ty = val.ty;
182        while let TyKind::Ref(_, inner, _) | TyKind::RawPtr(inner, _) = ty.kind() {
183            ty = *inner;
184        }
185        if let TyKind::Adt(adt, _) = ty.kind()
186            && (type_ids::is_std_vec(adt.did()) || type_ids::is_std_string(adt.did()))
187            && let Some(data_id) = self.container_data_alloc(val.provenance_alloc_id()?, val.ty)
188        {
189            return self.slice_len_of_alloc(data_id);
190        }
191        self.slice_len_from_value(val)
192    }
193
194    pub(crate) fn capacity_from_value(&self, val: &VmValue<'z3, 'tcx>) -> Option<Int<'z3>> {
195        let mut ty = val.ty;
196        while let TyKind::Ref(_, inner, _) | TyKind::RawPtr(inner, _) = ty.kind() {
197            ty = *inner;
198        }
199        let TyKind::Adt(adt, _) = ty.kind() else {
200            return None;
201        };
202        if !type_ids::is_std_vec(adt.did()) && !type_ids::is_std_string(adt.did()) {
203            return None;
204        }
205        let root_id = val.provenance_alloc_id()?;
206        let data_id = self.container_data_alloc(root_id, val.ty).unwrap_or(root_id);
207        let alloc = self.alloc(data_id);
208        let elem_ty = alloc.element_ty.as_ty()?;
209        if self.size_of_ty(elem_ty) == 0 && !mir_utils::ty_has_type_param(elem_ty) {
210            return Some(Int::from_u64(self.z3_ctx, usize::MAX as u64));
211        }
212        if alloc.has_unbounded_size() {
213            return None;
214        }
215        Some(alloc.size.div(&self.size_sym_read(elem_ty)))
216    }
217
218    /// Resolve `x.len()` for a struct `x` (e.g. `NodeRef`) whose `len()` method
219    /// reads `(*x.field).len` through a `NonNull`/raw-pointer field.  Follows
220    /// that field to its pointee allocation and reads the pointee's `len` field.
221    pub(crate) fn try_struct_nn_len_field(
222        &self,
223        local: Local,
224        field_path: &[usize],
225        ty: Ty<'tcx>,
226    ) -> Option<Int<'z3>> {
227        let rustc_middle::ty::TyKind::Adt(adt_def, substs) = ty.kind() else {
228            return None;
229        };
230        if !adt_def.is_struct() {
231            return None;
232        }
233        let variant = adt_def.non_enum_variant();
234        let mut found: Option<(usize, Ty<'tcx>)> = None;
235        for (idx, field_def) in variant.fields.iter().enumerate() {
236            let fty = mir_utils::field_ty(self.tcx, field_def, substs);
237            if let Some(pointee) = self.find_nn_pointee(fty) {
238                found = Some((idx, pointee));
239                break;
240            }
241        }
242        let (nn_idx, pointee) = found?;
243        let mut path = field_path.to_vec();
244        path.push(nn_idx);
245        let nn_val = self.field_value(local, &path)?;
246        let alloc_id = nn_val.provenance_alloc_id()?;
247        let rustc_middle::ty::TyKind::Adt(pointee_adt, _) = pointee.kind() else {
248            return None;
249        };
250        let pvariant = pointee_adt.non_enum_variant();
251        let len_idx = pvariant
252            .fields
253            .iter()
254            .position(|f| f.ident(self.tcx).name.to_string() == "len")?;
255        self.path_state.mem_units[alloc_id.0].content.values
256            .get(&(pointee, vec![len_idx]))
257            .map(|v| v.z3_term.clone())
258    }
259
260    /// Resolve the type of a local plus its field-index path.
261    pub(crate) fn field_type_at(&self, local: Local, field_path: &[usize]) -> Option<Ty<'tcx>> {
262        mir_utils::projected_field_ty(self.tcx, self.body().local_decls[local].ty, field_path)
263    }
264
265    /// Extract the pointee type if `ty` is a `#[repr(transparent)]`
266    /// single-field raw-pointer wrapper (`NonNull<P>`) or wrapped in
267    /// `Option<NonNull<P>>`. Returns `Some(P)`.
268    ///
269    /// Detected structurally (via `#[repr(transparent)]` + a raw-pointer field)
270    /// rather than by name, so re-implemented std types in the challenge
271    /// suites are modelled identically to their std counterparts.
272    pub(crate) fn find_nn_pointee(&self, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
273        match ty.kind() {
274            TyKind::Adt(adt_def, substs) => {
275                if let Some(pointee) = self.transparent_ptr_pointee(adt_def, *substs) {
276                    return Some(pointee);
277                }
278                if self
279                    .tcx
280                    .is_diagnostic_item(rustc_span::sym::Option, adt_def.did())
281                    && let Some(inner) = substs.first().and_then(|s| s.as_type())
282                        && let TyKind::Adt(ia, is_) = inner.kind() {
283                            return self.transparent_ptr_pointee(ia, *is_);
284                        }
285                None
286            }
287            _ => None,
288        }
289    }
290
291    /// Pointee type of a `#[repr(transparent)]` single-field raw-pointer
292    /// wrapper such as `NonNull<T>` (`struct NonNull<T> { pointer: *const T }`).
293    fn transparent_ptr_pointee(
294        &self,
295        adt_def: &rustc_middle::ty::AdtDef,
296        substs: GenericArgsRef<'tcx>,
297    ) -> Option<Ty<'tcx>> {
298        if !adt_def.repr().transparent() {
299            return None;
300        }
301        let field = adt_def.non_enum_variant().fields.iter().next()?;
302        let field_ty = mir_utils::field_ty(self.tcx, field, substs);
303        match field_ty.kind() {
304            rustc_middle::ty::TyKind::RawPtr(pointee, _) => Some(*pointee),
305            // NonNull's field is a pattern type `*const T is !null` on newer
306            // toolchains; unwrap it to the underlying raw pointer.
307            rustc_middle::ty::TyKind::Pat(inner, _) => match inner.kind() {
308                rustc_middle::ty::TyKind::RawPtr(pointee, _) => Some(*pointee),
309                _ => None,
310            },
311            _ => None,
312        }
313    }
314
315    /// Whether `ty` is a `#[repr(transparent)]` newtype (a single non-zero-sized
316    /// field whose value *is* that field, e.g. `MaybeUninit<T>`, `ManuallyDrop<T>`,
317    /// `Wrapping<T>`, `NonNull<T>`).  Construction and field reads are modelled
318    /// transparently: the wrapper value is the field value itself.
319    pub(crate) fn is_transparent_newtype(&self, ty: Ty<'tcx>) -> bool {
320        match ty.kind() {
321            rustc_middle::ty::TyKind::Adt(adt_def, _) => adt_def.repr().transparent(),
322            _ => false,
323        }
324    }
325
326    pub(crate) fn container_ptr_field(&self, ty: Ty<'tcx>) -> Option<Vec<usize>> {
327        self.container_ptr_field_inner(ty, Vec::new(), 0)
328    }
329
330    fn container_ptr_field_inner(
331        &self,
332        ty: Ty<'tcx>,
333        prefix: Vec<usize>,
334        depth: usize,
335    ) -> Option<Vec<usize>> {
336        if depth > 4 {
337            return None;
338        }
339        match ty.kind() {
340            TyKind::Adt(adt, substs) => {
341                if adt.is_enum() {
342                    return None;
343                }
344                for (idx, field_def) in adt.non_enum_variant().fields.iter().enumerate() {
345                    let field_ty =
346                        mir_utils::field_ty(self.tcx, field_def, substs);
347                    let mut path = prefix.clone();
348                    path.push(idx);
349                    if let TyKind::RawPtr(..) = field_ty.kind() {
350                        return Some(path);
351                    }
352                    if self.find_nn_pointee(field_ty).is_some() {
353                        return Some(path);
354                    }
355                    if let Some(found) =
356                        self.container_ptr_field_inner(field_ty, path, depth + 1)
357                    {
358                        return Some(found);
359                    }
360                }
361                None
362            }
363            _ => None,
364        }
365    }
366
367    pub(crate) fn container_data_alloc(
368        &self,
369        header: AllocId,
370        ty: Ty<'tcx>,
371    ) -> Option<AllocId> {
372        let mut view_ty = ty;
373        while let TyKind::Ref(_, inner, _) | TyKind::RawPtr(inner, _) = view_ty.kind() {
374            view_ty = *inner;
375        }
376        if !matches!(view_ty.kind(), TyKind::Adt(..)) {
377            return None;
378        }
379        let path = self.container_ptr_field(view_ty)?;
380        self.load_value(header, view_ty, &path)?.provenance_alloc_id()
381    }
382
383    /// The data allocation behind a container header or a slice view's header.
384    /// Tries the type-driven owning field first, then falls back to scanning the
385    /// header's materialized fields for the first owning pointer (covers slice
386    /// views whose header `AllocId` no longer carries a type key).
387    pub(crate) fn data_alloc_of(&self, header: AllocId, ty: Ty<'tcx>) -> Option<AllocId> {
388        let mut data_ty = ty;
389        while let TyKind::Ref(_, inner, _) | TyKind::RawPtr(inner, _) = data_ty.kind() {
390            data_ty = *inner;
391        }
392        let element_ty = match data_ty.kind() {
393            TyKind::Slice(element) | TyKind::Array(element, _) => Some(*element),
394            _ => None,
395        };
396        if element_ty.is_some_and(|element| self.alloc(header).element_ty.as_ty() == Some(element)) {
397            return None;
398        }
399        self.container_data_alloc(header, ty).or_else(|| {
400            // The header → data fallback is only for local slice views.
401            // External parameter headers retain their own contract range facts.
402            if self.alloc(header).is_external() {
403                None
404            } else {
405                self.header_data_alloc(header)
406            }
407        })
408    }
409
410    /// Scan a header allocation's materialized fields for the owning pointer
411    /// (its provenance names the data allocation). This is the header → data
412    /// fallback for slice views (whose provenance names the container header,
413    /// not the data), replacing the old `slice_data` edge.
414    ///
415    /// Returns the provenance only when the header has *exactly one* owning
416    /// pointer field. A multi-owning-pointer header (e.g. a linked list's
417    /// `head`/`tail`) is ambiguous, so fall back to `None` rather than guess.
418    fn header_data_alloc(&self, header: AllocId) -> Option<AllocId> {
419        let mut result = None;
420        for ((_, p), v) in self.path_state.mem_units[header.0].content.values.iter() {
421            if p.is_empty() {
422                continue;
423            }
424            let Some(prov) = v.provenance_alloc_id() else {
425                continue;
426            };
427            if result.is_some() {
428                return None;
429            }
430            result = Some(prov);
431        }
432        result
433    }
434
435    /// Resolve a mutable Vec receiver, including a borrow of its backing
436    /// buffer fields (as used by reserve's MIR). A borrow of an unrelated
437    /// field, such as the length, does not replace the backing allocation.
438    pub(crate) fn vec_reallocation_targets(
439        &self,
440        value: &VmValue<'z3, 'tcx>,
441    ) -> Vec<(AllocId, Ty<'tcx>)> {
442        let TyKind::Ref(_, inner, rustc_middle::mir::Mutability::Mut) = value.ty.kind() else {
443            return Vec::new();
444        };
445        if inner
446            .ty_adt_def()
447            .is_some_and(|adt| type_ids::is_std_vec(adt.did()))
448        {
449            return value
450                .provenance_alloc_id()
451                .map(|id| (id, *inner))
452                .into_iter()
453                .collect();
454        }
455        let ValueSource::FieldBorrow { fields, .. } = &value.source else {
456            return Vec::new();
457        };
458        // A field borrow can cross an inlined frame, where its source Local
459        // no longer names the owner. Resolve the stored field value instead.
460        let borrowed = value.z3_term.simplify();
461        let mut targets = Vec::new();
462        let mut backing = None;
463        for (index, unit) in self.path_state.mem_units.iter().enumerate() {
464            for ((view_ty, path), field) in &unit.content.values {
465                if path != fields
466                    || field.ty != *inner
467                    || !view_ty
468                        .ty_adt_def()
469                        .is_some_and(|adt| type_ids::is_std_vec(adt.did()))
470                    || field.z3_term.simplify() != borrowed
471                    || !self
472                        .container_ptr_field(*view_ty)
473                        .is_some_and(|pointer| pointer.starts_with(path))
474                {
475                    continue;
476                }
477                let candidate = (AllocId(index), *view_ty);
478                let Some(data) = self.container_data_alloc(candidate.0, candidate.1) else {
479                    return Vec::new();
480                };
481                if backing.is_some_and(|previous| previous != data) {
482                    return Vec::new();
483                }
484                backing = Some(data);
485                if !targets.contains(&candidate) {
486                    targets.push(candidate);
487                }
488            }
489        }
490        targets
491    }
492
493    pub(crate) fn reallocate_vec_backing(&mut self, value: &VmValue<'z3, 'tcx>) {
494        let targets = self.vec_reallocation_targets(value);
495        let Some(&(header, ty)) = targets.first() else {
496            return;
497        };
498        if self.alloc(header).is_external() {
499            return;
500        }
501        let Some(data) = self.container_data_alloc(header, ty) else {
502            return;
503        };
504        let Some(elem_ty) = self.alloc(data).element_ty.as_ty() else {
505            return;
506        };
507        // Zero-sized elements never require a backing allocation to grow.
508        if self.size_of_ty(elem_ty) == 0 && !mir_utils::ty_has_type_param(elem_ty) {
509            return;
510        }
511        self.alloc_mut(data).facts.dead = true;
512        // The replacement's capacity is unknown, but finite. Use the same
513        // extent for bounds checks and capacity_from_value; in particular,
514        // capacity() + 1 must not be proved in bounds after growth.
515        let capacity = self.fresh_int("vec_capacity");
516        let elem_size = self.size_sym(elem_ty);
517        let size = Int::mul(self.z3_ctx, &[&capacity, &elem_size]);
518        let zero = Int::from_u64(self.z3_ctx, 0);
519        self.path_state.constraints.assertions.push(capacity.ge(&zero));
520        if let Some((_, max_size, _, _)) = self.integer_limits(self.tcx.types.isize) {
521            self.path_state.constraints.assertions.push(size.le(&max_size));
522        }
523        let align = self.align_sym(elem_ty);
524        let (new_data, base) = self.allocate_external(size, align, Some(elem_ty));
525        // Field loads take precedence over capacity_from_value. Replace any
526        // materialized capacity field together with the backing allocation.
527        // Moves can leave more than one materialized header for the same
528        // backing allocation. Update every matching view of the borrowed field.
529        for (header, ty) in targets {
530            let Some(path) = self.container_ptr_field(ty) else {
531                continue;
532            };
533            let capacity_fields: Vec<_> = self
534                .content(header)
535                .values
536                .iter()
537                .filter(|((view_ty, field_path), _)| self.is_cap_field_read(*view_ty, field_path))
538                .map(|((view_ty, field_path), value)| (*view_ty, field_path.clone(), value.ty))
539                .collect();
540            for (view_ty, field_path, field_ty) in capacity_fields {
541                let mut value = VmValue::new(capacity.clone(), field_ty);
542                value.facts.init = true;
543                self.store_value(header, view_ty, field_path, value);
544            }
545            self.store_value(
546                header,
547                ty,
548                path,
549                VmValue {
550                    z3_term: base.clone(),
551                    ty: elem_ty,
552                    provenance: Some(Provenance {
553                        alloc_id: new_data,
554                        offset: Int::from_u64(self.z3_ctx, 0),
555                        offset_kind: None,
556                    }),
557                    facts: ValueFacts {
558                        non_null: true,
559                        init: true,
560                        ..ValueFacts::default()
561                    },
562                    source: ValueSource::None,
563                },
564            );
565        }
566    }
567}