1use rustc_middle::{
4 mir::{Local, Operand, Place, Rvalue, StatementKind},
5 ty::{Region, Ty, TyKind},
6};
7use z3::ast::Int;
8
9use crate::compat::{FxHashMap, FxHashSet};
10use crate::util::mir_utils;
11
12use super::state::{AllocId, OffsetKind, Provenance, ValueFacts, ValueSource, VmExecutor, VmValue};
13
14impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
15 pub(crate) fn prewarm_generic_size_align(&mut self) {
18 let mut warmed: FxHashSet<Ty<'tcx>> = FxHashSet::default();
19 for param in self.tcx.generics_of(self.path_state.current_frame.current_def_id).own_params.iter() {
20 if let rustc_middle::ty::GenericParamDefKind::Type { .. } = param.kind {
21 warmed.insert(rustc_middle::ty::Ty::new_param(
22 self.tcx,
23 param.index,
24 param.name,
25 ));
26 }
27 }
28 for ty in warmed {
29 self.size_sym(ty);
30 self.align_sym(ty);
31 }
32 }
33
34 pub(crate) fn materialize_external_field(
44 &mut self,
45 local: Local,
46 idx: usize,
47 field_ty: Ty<'tcx>,
48 elem_ty: Ty<'tcx>,
49 alive_region: Option<Region<'tcx>>,
50 ) {
51 self.materialize_external_field_at(local, vec![idx], field_ty, elem_ty, alive_region);
52 }
53
54 fn materialize_external_field_at(
61 &mut self,
62 local: Local,
63 path: Vec<usize>,
64 field_ty: Ty<'tcx>,
65 elem_ty: Ty<'tcx>,
66 alive_region: Option<Region<'tcx>>,
67 ) {
68 let align = self.align_sym(elem_ty);
69 let (alloc_id, base) = if matches!(field_ty.kind(), TyKind::Slice(_)) {
70 let len = self.fresh_int("field_slice_len");
73 let elem_size = self.size_sym(elem_ty);
74 let bytes = Int::mul(self.z3_ctx, &[&len, &elem_size]);
75 self.path_state.constraints
76 .assertions
77 .push(len.ge(&Int::from_u64(self.z3_ctx, 0)));
78 if let Some((_, max_len, _, _)) = self.integer_limits(self.tcx.types.usize) {
79 self.path_state.constraints.assertions.push(len.le(&max_len));
80 }
81 if let Some((_, max_bytes, _, _)) = self.integer_limits(self.tcx.types.isize) {
82 self.path_state.constraints.assertions.push(bytes.le(&max_bytes));
83 }
84 let result = self.allocate_external(bytes, align, Some(elem_ty));
85 self.alloc_mut(result.0).set_slice_len(len);
86 result
87 } else {
88 let max_size = Int::from_u64(self.z3_ctx, i64::MAX as u64);
89 self.allocate_external(max_size, align, Some(elem_ty))
90 };
91 self.content_mut(alloc_id).facts.initialized = true;
92 if let Some(region) = alive_region {
93 self.alloc_mut(alloc_id).facts.liveness = Some(region);
94 }
95 self.set_field_value(
96 local,
97 path,
98 VmValue {
99 z3_term: base,
100 ty: field_ty,
101 provenance: Some(Provenance {
102 alloc_id,
103 offset: Int::from_u64(self.z3_ctx, 0),
104 offset_kind: None,
105 }),
106 facts: ValueFacts {
107 non_null: true,
108 init: true,
109 ..Default::default()
110 },
111 source: ValueSource::None,
112 },
113 );
114 }
115
116 #[allow(clippy::too_many_arguments)]
122 pub(crate) fn init_ptr_field(
123 &mut self,
124 local: Local,
125 path: Vec<usize>,
126 field_ty: Ty<'tcx>,
127 pointee: Ty<'tcx>,
128 local_idx: usize,
129 idx: usize,
130 elem_alloc: &mut FxHashMap<Ty<'tcx>, (AllocId, Int<'z3>)>,
131 is_raw_ptr: bool,
132 nn_fresh_prefix: &str,
133 ) {
134 let mut invariants = if is_raw_ptr {
137 ValueFacts::default()
140 } else {
141 ValueFacts {
142 init: true,
143 align_n: Some(self.align_sym(pointee)),
144 ..Default::default()
145 }
146 };
147 if is_raw_ptr && let Some(&(existing_alloc, ref base)) = elem_alloc.get(&pointee) {
155 let elem_align = self.align_sym(pointee);
162 let elem_size = self.size_sym(pointee);
163 let len_term = self.fresh_int(&format!("field_len_{}_{}", local_idx, idx));
164 self.path_state.constraints.assertions
165 .push(len_term.ge(&Int::from_u64(self.z3_ctx, 0)));
166 let prost_offset = Int::mul(self.z3_ctx, &[&len_term, &elem_size]);
167 let field_term = Int::add(self.z3_ctx, &[base, &prost_offset]);
168 invariants.align_n = Some(elem_align);
169 self.set_field_value(
170 local,
171 path,
172 VmValue {
173 z3_term: field_term,
174 ty: field_ty,
175 provenance: Some(Provenance {
176 alloc_id: existing_alloc,
177 offset: prost_offset.clone(),
178 offset_kind: Some(OffsetKind::Element {
179 index: len_term.clone(),
180 stride: elem_size.clone(),
181 }),
182 }),
183 facts: invariants,
184 source: ValueSource::None,
185 },
186 );
187 } else {
188 let field_align = if is_raw_ptr {
194 Int::from_u64(self.z3_ctx, 1)
195 } else {
196 self.align_sym(pointee)
197 };
198 let tail = (!is_raw_ptr).then(|| self.unsized_tail_layout(pointee)).flatten();
199 let tail_len = tail.map(|_| self.fresh_int(&format!("field_len_{}_{}", local_idx, idx)));
200 let max_size = if is_raw_ptr {
201 let s = self.fresh_int("raw_target_size");
202 self.path_state.constraints.assertions.push(s.ge(&Int::from_u64(self.z3_ctx, 0)));
203 s
204 } else if let (Some((elem, offset)), Some(len)) = (tail, tail_len.as_ref()) {
205 self.path_state.constraints.assertions.push(len.ge(&Int::from_u64(self.z3_ctx, 0)));
206 let data_size = Int::mul(self.z3_ctx, &[len, &self.size_sym(elem)]);
207 Int::add(self.z3_ctx, &[&Int::from_u64(self.z3_ctx, offset), &data_size])
208 } else {
209 Int::from_u64(self.z3_ctx, i64::MAX as u64)
210 };
211 let (field_alloc_id, field_base) =
212 self.allocate_external(max_size, field_align, Some(pointee));
213 if let Some(len) = tail_len {
214 self.alloc_mut(field_alloc_id).set_slice_len(len);
215 }
216 elem_alloc.insert(pointee, (field_alloc_id, field_base.clone()));
217 self.decompose_pointee_fields(
222 field_alloc_id,
223 Vec::new(),
224 pointee,
225 pointee,
226 local_idx,
227 0,
228 0,
229 );
230 if !is_raw_ptr {
235 self.assert_alloc_pointee_invariants(field_alloc_id, pointee);
236 }
237 let field_term = if is_raw_ptr {
238 field_base
239 } else {
240 self.fresh_int(&format!("{}_{}_{}", nn_fresh_prefix, local_idx, idx))
241 };
242 self.set_field_value(
243 local,
244 path,
245 VmValue {
246 z3_term: field_term,
247 ty: field_ty,
248 provenance: Some(Provenance {
249 alloc_id: field_alloc_id,
250 offset: Int::from_u64(self.z3_ctx, 0),
251 offset_kind: None,
252 }),
253 facts: invariants,
254 source: ValueSource::None,
255 },
256 );
257 }
258 }
259
260 fn unsized_tail_layout(&self, ty: Ty<'tcx>) -> Option<(Ty<'tcx>, u64)> {
261 let TyKind::Adt(adt, substs) = ty.kind() else {
262 return None;
263 };
264 if !adt.is_struct() {
265 return None;
266 }
267 let fields = &adt.non_enum_variant().fields;
268 let index = fields.len().checked_sub(1)?;
269 let tail_ty = mir_utils::field_ty(self.tcx, fields.iter().last()?, substs);
270 let elem = match tail_ty.kind() {
271 TyKind::Slice(elem) => *elem,
272 TyKind::Str => self.tcx.types.u8,
273 _ => return None,
274 };
275 let offset = mir_utils::field_offset_in_bytes(
276 self.tcx,
277 self.path_state.current_frame.current_def_id,
278 ty,
279 index,
280 );
281 (offset > 0 || index == 0).then_some((elem, offset))
282 }
283
284 pub(crate) fn decompose_adt_fields(
291 &mut self,
292 local: Local,
293 prefix: Vec<usize>,
294 ty: Ty<'tcx>,
295 local_idx: usize,
296 elem_alloc: &mut FxHashMap<Ty<'tcx>, (AllocId, Int<'z3>)>,
297 depth: usize,
298 ) {
299 if depth > 4 {
300 return;
301 }
302 let rustc_middle::ty::TyKind::Adt(adt_def, substs) = ty.kind() else {
303 return;
304 };
305 if adt_def.is_enum() {
306 return;
307 }
308 let variant = adt_def.non_enum_variant();
309 for (idx, field_def) in variant.fields.iter().enumerate() {
310 let field_ty: Ty<'tcx> =
311 mir_utils::field_ty(self.tcx, field_def, substs);
312 let mut path = prefix.clone();
313 path.push(idx);
314 if let rustc_middle::ty::TyKind::RawPtr(inner, _) = field_ty.kind() {
315 self.init_ptr_field(
316 local, path, field_ty, *inner, local_idx, idx, elem_alloc, true, "field_nn",
317 );
318 continue;
319 }
320 if let Some(pointee) = self.find_nn_pointee(field_ty) {
321 self.init_ptr_field(
322 local, path, field_ty, pointee, local_idx, idx, elem_alloc, false, "field_nn",
323 );
324 continue;
325 }
326 if let rustc_middle::ty::TyKind::Adt(inner_adt, _) = field_ty.kind()
327 && !inner_adt.is_enum() {
328 self.decompose_adt_fields(
329 local, path, field_ty, local_idx, elem_alloc, depth + 1,
330 );
331 continue;
332 }
333 let field_term = self.fresh_int(&format!("field_{}_{}", local_idx, idx));
334 self.set_field_value(
335 local,
336 path,
337 VmValue {
338 z3_term: field_term,
339 ty: field_ty,
340 provenance: None,
341 facts: ValueFacts {
342 init: true,
343 ..Default::default()
344 },
345 source: ValueSource::None,
346 },
347 );
348 }
349 }
350
351 pub(crate) fn materialize_vec_ptr_field(
359 &mut self,
360 local: Local,
361 prefix: Vec<usize>,
362 field_ty: Ty<'tcx>,
363 ) -> bool {
364 let TyKind::Adt(adt_def, substs) = field_ty.kind() else {
365 return false;
366 };
367 let variant = adt_def.non_enum_variant();
368 for (i, field_def) in variant.fields.iter().enumerate() {
369 let ft = mir_utils::field_ty(self.tcx, field_def, substs);
370 let Some(pointee) = self.find_nn_pointee(ft) else {
371 continue;
372 };
373 let mut path = prefix.clone();
374 path.push(i);
375 self.materialize_external_field_at(
376 local,
377 path,
378 ft,
379 pointee,
380 Some(self.tcx.lifetimes.re_static),
381 );
382 return true;
383 }
384 false
385 }
386
387 fn field_term_from_bytes(
397 &self,
398 alloc_id: AllocId,
399 offset: usize,
400 size: usize,
401 ) -> Option<Int<'z3>> {
402 if size == 0 {
403 return Some(Int::from_u64(self.z3_ctx, 0));
404 }
405 let mut term = Int::from_u64(self.z3_ctx, 0);
406 for j in 0..size {
407 let off = offset + j;
408 if !self.is_byte_init(alloc_id, off) {
409 return None;
410 }
411 let b = self.byte_read(alloc_id, &Int::from_u64(self.z3_ctx, off as u64));
412 let weight = Int::from_u64(self.z3_ctx, 1u64 << (j * 8));
413 term = Int::add(self.z3_ctx, &[&term, &Int::mul(self.z3_ctx, &[&b, &weight])]);
414 }
415 Some(term)
416 }
417
418 #[allow(clippy::too_many_arguments)]
428 pub(crate) fn decompose_pointee_fields(
429 &mut self,
430 alloc_id: AllocId,
431 prefix: Vec<usize>,
432 ty: Ty<'tcx>,
433 root_ty: Ty<'tcx>,
434 local_idx: usize,
435 depth: usize,
436 byte_offset: usize,
437 ) {
438 if depth > 4 {
439 return;
440 }
441 let fields = match ty.kind() {
442 TyKind::Adt(adt_def, substs) if !adt_def.is_enum() => adt_def
443 .non_enum_variant()
444 .fields
445 .iter()
446 .map(|field| mir_utils::field_ty(self.tcx, field, substs))
447 .collect::<Vec<_>>(),
448 TyKind::Tuple(fields) => fields.iter().collect::<Vec<_>>(),
449 _ => return,
450 };
451 for (idx, field_ty) in fields.into_iter().enumerate() {
452 let field_off = byte_offset + self.field_offset_in_bytes(ty, idx) as usize;
453 let mut path = prefix.clone();
454 path.push(idx);
455 if self.load_value(alloc_id, root_ty, &path).is_some() {
456 continue;
457 }
458 if let Some(pointee) = self.find_nn_pointee(field_ty) {
459 let field_align = self.align_sym(pointee);
460 let max_size = Int::from_u64(self.z3_ctx, i64::MAX as u64);
461 let (fa, _fb) = self.allocate_external(max_size, field_align, Some(pointee));
462 self.content_mut(fa).facts.initialized = true;
463 let term = self.fresh_int(&format!("pointee_nn_{}_{}", local_idx, idx));
464 self.path_state.mem_units[alloc_id.0].content.values.insert(
465 (root_ty, path.clone()),
466 VmValue {
467 z3_term: term,
468 ty: field_ty,
469 provenance: Some(Provenance {
470 alloc_id: fa,
471 offset: Int::from_u64(self.z3_ctx, 0),
472 offset_kind: None,
473 }),
474 facts: ValueFacts {
475 init: true,
476 ..Default::default()
477 },
478 source: ValueSource::None,
479 },
480 );
481 self.decompose_pointee_fields(
482 fa,
483 Vec::new(),
484 pointee,
485 pointee,
486 local_idx,
487 depth + 1,
488 0,
489 );
490 } else if matches!(field_ty.kind(), TyKind::Adt(_, _) | TyKind::Tuple(_)) {
491 self.decompose_pointee_fields(
492 alloc_id,
493 path,
494 field_ty,
495 root_ty,
496 local_idx,
497 depth + 1,
498 field_off,
499 );
500 } else if matches!(
501 field_ty.kind(),
502 TyKind::Uint(_) | TyKind::Int(_) | TyKind::Float(_) | TyKind::Bool | TyKind::Char
503 ) {
504 let field_size = self.size_of_ty(field_ty) as usize;
509 let field_term = self
510 .field_term_from_bytes(alloc_id, field_off, field_size)
511 .unwrap_or_else(|| self.fresh_int(&format!("pointee_field_{}_{}", local_idx, idx)));
512 self.path_state.mem_units[alloc_id.0].content.values.insert(
513 (root_ty, path.clone()),
514 VmValue {
515 z3_term: field_term,
516 ty: field_ty,
517 provenance: None,
518 facts: ValueFacts {
519 init: true,
520 ..Default::default()
521 },
522 source: ValueSource::None,
523 },
524 );
525 } else if let TyKind::Array(elem_ty, const_len) = field_ty.kind() {
526 let n = mir_utils::eval_array_len(self.tcx, const_len).unwrap_or(0);
527 let arr_align = self.align_sym(*elem_ty);
528 let arr_elem_size = self.size_sym(*elem_ty);
529 let (fa, fb) = self.allocate_slice(
534 Int::from_u64(self.z3_ctx, n),
535 arr_elem_size,
536 arr_align,
537 Some(*elem_ty),
538 );
539 self.content_mut(fa).facts.initialized = true;
540 self.path_state.mem_units[alloc_id.0].content.values.insert(
541 (root_ty, path.clone()),
542 VmValue {
543 z3_term: fb,
544 ty: field_ty,
545 provenance: Some(Provenance {
546 alloc_id: fa,
547 offset: Int::from_u64(self.z3_ctx, 0),
548 offset_kind: None,
549 }),
550 facts: ValueFacts {
551 init: true,
552 ..Default::default()
553 },
554 source: ValueSource::None,
555 },
556 );
557 }
558 }
559 }
560
561 pub(crate) fn try_materialize_const_bytes(
565 &mut self,
566 val: &mut VmValue<'z3, 'tcx>,
567 operand: &Operand<'tcx>,
568 ) {
569 let operand_val = self.value_of_operand(operand);
570 let op_ty = operand_val.ty;
571 let (pointee_ty, _is_ref) = match op_ty.kind() {
572 rustc_middle::ty::TyKind::Ref(_, inner_ty, _) => (*inner_ty, true),
573 rustc_middle::ty::TyKind::RawPtr(inner_ty, _) => (*inner_ty, false),
574 _ => {
575 let val_ty = val.ty;
576 match val_ty.kind() {
577 rustc_middle::ty::TyKind::Ref(_, inner_ty, _) => (*inner_ty, true),
578 rustc_middle::ty::TyKind::RawPtr(inner_ty, _) => (*inner_ty, false),
579 _ => return,
580 }
581 }
582 };
583 match pointee_ty.kind() {
584 rustc_middle::ty::TyKind::Array(elem_ty, _)
585 | rustc_middle::ty::TyKind::Slice(elem_ty) => {
586 let is_byte = matches!(
587 elem_ty.kind(),
588 rustc_middle::ty::TyKind::Uint(rustc_middle::ty::UintTy::U8)
589 | rustc_middle::ty::TyKind::Int(rustc_middle::ty::IntTy::I8)
590 );
591 if is_byte {
592 let bytes_opt =
593 mir_utils::const_operand_bytes(self.tcx, operand)
594 .or_else(|| self.trace_to_const_bytes(operand));
595 if let Some(bytes) = bytes_opt {
596 let size = z3::ast::Int::from_u64(self.z3_ctx, bytes.len() as u64);
597 let align = self.align_sym(pointee_ty);
598 let (alloc_id, base) = self.allocate(size, align, Some(pointee_ty));
599 self.content_mut(alloc_id).facts.initialized = true;
600 self.alloc_mut(alloc_id).facts.liveness =
601 Some(self.tcx.lifetimes.re_static);
602 for (i, &b) in bytes.iter().enumerate() {
603 self.record_byte_value(
604 alloc_id,
605 i,
606 z3::ast::Int::from_u64(self.z3_ctx, b as u64),
607 );
608 }
609 val.z3_term = base;
610 val.provenance = Some(super::state::Provenance {
611 alloc_id,
612 offset: z3::ast::Int::from_u64(self.z3_ctx, 0),
613 offset_kind: None,
614 });
615 val.facts = ValueFacts {
616 non_null: true,
617 init: true,
618 in_bounds: false,
619 align_n: None,
620 dangling: false,
621 ownership_transfer: None,
622 };
623 }
624 }
625 }
626 _ => {}
627 }
628 }
629
630 pub(crate) fn trace_to_const_bytes(&self, operand: &Operand<'tcx>) -> Option<Vec<u8>> {
631 let place = match operand {
632 Operand::Copy(p) | Operand::Move(p) => p,
633 _ => return None,
634 };
635 let base_local = if place.projection.is_empty()
636 || (place.projection.len() == 1
637 && matches!(
638 place.projection.first().map(|p| p.kind()),
639 Some(rustc_middle::mir::ProjectionElem::Deref)
640 ))
641 {
642 place.local
643 } else {
644 return None;
645 };
646 for block in self.body().basic_blocks.iter() {
647 for stmt in &block.statements {
648 if let StatementKind::Assign(assign) = &stmt.kind {
649 let (dest, rvalue) = &**assign;
650 if dest.local != base_local || !dest.projection.is_empty() {
651 continue;
652 }
653 match rvalue {
654 Rvalue::Use(op, ..) => {
655 return mir_utils::const_operand_bytes(self.tcx, op)
656 .or_else(|| self.trace_to_const_bytes(op));
657 }
658 Rvalue::Ref(_, _, p) => {
659 let op = Operand::Copy(*p);
660 return self.trace_to_const_bytes(&op);
661 }
662 _ => return None,
663 }
664 }
665 }
666 }
667 None
668 }
669
670 pub(crate) fn propagate_field_values_to_ref(&mut self, source_place: &Place<'tcx>, dest: Local) {
678 let only_field_deref = source_place.projection.iter().all(|p| {
683 matches!(
684 p.kind(),
685 rustc_middle::mir::ProjectionElem::Field(..)
686 | rustc_middle::mir::ProjectionElem::Deref
687 )
688 });
689 if !only_field_deref {
690 return;
691 }
692 let field_prefix: Vec<usize> = source_place
693 .projection
694 .iter()
695 .filter_map(|p| match p.kind() {
696 rustc_middle::mir::ProjectionElem::Field(fi, _) => Some(fi.as_usize()),
697 _ => None,
698 })
699 .collect();
700 let empty_proj = source_place.projection.is_empty();
705 let keys: Vec<Vec<usize>> = self.field_paths(source_place.local);
706 for path in keys {
707 let matches_prefix = field_prefix.is_empty()
708 || (path.len() >= field_prefix.len()
709 && path[..field_prefix.len()] == field_prefix[..]);
710 if matches_prefix {
711 let rest = if field_prefix.is_empty() {
712 path.clone()
713 } else {
714 path[field_prefix.len()..].to_vec()
715 };
716 if rest.is_empty() {
717 continue;
718 }
719 if let Some(v) = self.field_value(source_place.local, &path).cloned() {
720 if empty_proj && v.provenance.is_none() {
721 continue;
722 }
723 self.set_field_value(dest, rest, v);
724 }
725 }
726 }
727 }
728
729 pub(crate) fn propagate_byte_values_to_ref(
730 &mut self,
731 source_place: &Place<'tcx>,
732 ref_val: &VmValue<'z3, 'tcx>,
733 ) {
734 let Some(src_alloc_id) = self.path_state.current_frame.local_alloc.get(&source_place.local).copied() else {
735 return;
736 };
737 let Some(ref_alloc_id) = ref_val.provenance_alloc_id() else {
738 return;
739 };
740 if src_alloc_id == ref_alloc_id {
741 return; }
743 self.copy_byte_tracking(src_alloc_id, 0, ref_alloc_id);
744 }
745
746 pub(crate) fn aggregate_field_tys(&self, ty: Ty<'tcx>) -> Vec<Ty<'tcx>> {
748 match ty.kind() {
749 rustc_middle::ty::TyKind::Array(elem_ty, _len) => {
750 vec![*elem_ty]
751 }
752 rustc_middle::ty::TyKind::Tuple(elems) => elems.iter().collect(),
753 rustc_middle::ty::TyKind::Adt(adt_def, substs) => {
754 if adt_def.is_enum() {
755 return vec![];
756 }
757 let variant = adt_def.non_enum_variant();
758 variant
759 .fields
760 .iter()
761 .map(|f| mir_utils::field_ty(self.tcx, f, substs))
762 .collect()
763 }
764 _ => vec![],
765 }
766 }
767
768 pub(crate) fn materialize_vec_fields(
778 &mut self,
779 local: Local,
780 ptr: VmValue<'z3, 'tcx>,
781 cap: Int<'z3>,
782 len: Int<'z3>,
783 ) {
784 let elem_size = self.size_of_ty(ptr.ty).max(1);
785 let ty = self.body().local_decls[local].ty;
786 let ptr_path = self
787 .container_ptr_field(ty)
788 .expect("materialize_vec_fields: container has no owning pointer field");
789 self.set_field_value(local, ptr_path, ptr);
790 self.materialize_vec_len_cap(cap, len, elem_size);
791 }
792
793 pub(crate) fn materialize_vec_len_cap(
796 &mut self,
797 cap: Int<'z3>,
798 len: Int<'z3>,
799 elem_size: u64,
800 ) {
801 let zero = Int::from_u64(self.z3_ctx, 0);
802 self.path_state.constraints.assertions.push(len.ge(&zero));
803 self.path_state.constraints.assertions.push(len.le(&cap));
804 self.path_state.constraints.assertions.push(cap.ge(&zero));
805 let isize_max = Int::from_u64(self.z3_ctx, isize::MAX as u64);
810 let elem_term = Int::from_u64(self.z3_ctx, elem_size.max(1));
811 self.path_state.constraints.assertions
812 .push(Int::mul(self.z3_ctx, &[&cap, &elem_term]).le(&isize_max));
813 }
814}