1use 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 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 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 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 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 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 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 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 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 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 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 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 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 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 if self.alloc(header).is_external() {
403 None
404 } else {
405 self.header_data_alloc(header)
406 }
407 })
408 }
409
410 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 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 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 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 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 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}