1use crate::ast::*;
3use crate::ids::IndexVec;
4use crate::utils::serialize_map_to_array::SeqHashMapToArray;
5use derive_generic_visitor::*;
6use itertools::Itertools;
7use serde::{Deserialize, Serialize};
8use serde_state::{DeserializeState, SerializeState};
9
10pub type ByteCount = u64;
11
12#[derive(Debug, Clone, PartialEq)]
18#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
19pub struct Layout {
20 pub size: Size,
22 pub align: Size,
24 pub discriminator: Option<Discriminator>,
26 pub inhabited: InhabitedPredicate,
30 pub variant_layouts: IndexVec<VariantId, Option<VariantLayout>>,
34 #[serde_state(stateless)]
38 pub union_chunks: Option<Vec<(ByteCount, ByteCount)>>,
39 #[serde_state(stateless)]
41 pub repr: ReprOptions,
42}
43
44#[derive(Debug, Default, Clone)]
46#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
47#[serde_state(state_implements = DedupSerializerState)]
48pub struct TargetLayouts(#[serde(with = "SeqHashMapToArray")] pub SeqHashMap<TargetTriple, Layout>);
49
50impl std::ops::Deref for TargetLayouts {
51 type Target = SeqHashMap<TargetTriple, Layout>;
52 fn deref(&self) -> &Self::Target {
53 &self.0
54 }
55}
56impl std::ops::DerefMut for TargetLayouts {
57 fn deref_mut(&mut self) -> &mut Self::Target {
58 &mut self.0
59 }
60}
61
62#[derive(Debug, Default, Clone, PartialEq)]
66#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
67pub struct VariantLayout {
68 pub field_offsets: IndexVec<FieldId, OffsetExpr>,
70 pub inhabited: InhabitedPredicate,
73 #[serde_state(stateless)]
76 pub tagger: Vec<(ByteCount, IntegerValue)>,
77}
78
79impl Layout {
80 pub fn for_type(
82 krate: &TranslatedCrate,
83 kind: &TypeDeclKind,
84 repr: ReprOptions,
85 ) -> Option<Self> {
86 let fields_inhabited = |fields: &IndexVec<FieldId, Field>| {
87 InhabitedPredicateKind::And(
88 fields
89 .iter()
90 .map(|field| field.ty.inhabited_predicate(krate, None))
91 .collect(),
92 )
93 .into_pred()
94 };
95
96 let (inhabited, variant_layouts) = match kind {
97 TypeDeclKind::Struct(fields) => {
98 let inhabited = fields_inhabited(fields);
99 let field_offsets = fields
100 .iter()
101 .map(|_| OffsetExpr::new(None::<ByteCount>))
102 .collect();
103 let layouts = vec![Some(VariantLayout {
104 field_offsets,
105 inhabited: inhabited.clone(),
106 tagger: Vec::new(),
107 })]
108 .into();
109 (inhabited, layouts)
110 }
111 TypeDeclKind::Union(fields) => {
112 let inhabited = InhabitedPredicateKind::Or(
113 fields
114 .iter()
115 .map(|field| field.ty.inhabited_predicate(krate, None))
116 .collect(),
117 )
118 .into_pred();
119 let field_offsets = fields
120 .iter()
121 .map(|_| OffsetExpr::new(None::<ByteCount>))
122 .collect();
123 let layouts = vec![Some(VariantLayout {
124 field_offsets,
125 inhabited: inhabited.clone(),
126 tagger: Vec::new(),
127 })]
128 .into();
129 (inhabited, layouts)
130 }
131 TypeDeclKind::Enum(variants) => {
132 let mut layouts = IndexVec::new();
133 let mut variant_predicates = Vec::new();
134 for variant in variants {
135 let variant_inhabited = fields_inhabited(&variant.fields);
136 let field_offsets = variant
137 .fields
138 .iter()
139 .map(|_| OffsetExpr::new(None::<ByteCount>))
140 .collect();
141 layouts.push(Some(VariantLayout {
142 field_offsets,
143 inhabited: variant_inhabited.clone(),
144 tagger: Vec::new(),
145 }));
146 variant_predicates.push(variant_inhabited);
147 }
148 (
149 InhabitedPredicateKind::Or(variant_predicates).into_pred(),
150 layouts,
151 )
152 }
153 TypeDeclKind::Alias(ty) => (ty.inhabited_predicate(krate, None), IndexVec::new()),
154 TypeDeclKind::Opaque | TypeDeclKind::Error(_) => return None,
155 };
156
157 Some(Self {
158 size: Size::from_expr(None),
159 align: Size::from_expr(None),
160 discriminator: None,
161 inhabited,
162 variant_layouts,
163 union_chunks: None,
164 repr,
165 })
166 }
167
168 pub fn is_variant_always_uninhabited(&self, variant_id: VariantId) -> bool {
169 self.variant_layouts[variant_id]
170 .as_ref()
171 .is_none_or(|layout| layout.inhabited.always_false())
172 }
173
174 pub fn is_variant_always_inhabited(&self, variant_id: VariantId) -> bool {
175 self.variant_layouts[variant_id]
176 .as_ref()
177 .is_some_and(|layout| layout.inhabited.always_true())
178 }
179
180 pub fn is_c_repr(&self) -> bool {
181 self.repr.repr_algo == ReprAlgorithm::C
182 }
183}
184
185#[derive(Debug, Clone, PartialEq)]
188#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
189#[serde_state(state_implements = DedupSerializerState)]
190pub enum Discriminator {
191 Known(VariantId),
193 Invalid,
195 Branch {
197 offset: OffsetExpr,
199 #[serde_state(stateless)]
201 int_ty: IntegerTy,
202 children: Vec<(std::ops::RangeInclusive<IntegerValue>, Discriminator)>,
205 fallback: Box<Discriminator>,
207 },
208}
209
210#[derive(Debug, Clone, PartialEq)]
212#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
213pub struct Size {
214 pub chosen: Option<SizeExpr>,
218 pub guarantee: Option<SizeExpr>,
220}
221
222#[derive(Debug, Clone, PartialEq)]
224#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
225pub struct OffsetExpr {
226 pub guarantee: Option<OffsetGuarantee>,
228 pub chosen: Option<ByteCount>,
230}
231
232impl Size {
233 pub fn new(chosen: impl Into<Option<ByteCount>>) -> Self {
234 Self::from_expr(
235 chosen
236 .into()
237 .map(|chosen| SizeExprKind::from_usize(u128::from(chosen)).into_expr()),
238 )
239 }
240
241 pub fn from_expr(chosen: impl Into<Option<SizeExpr>>) -> Self {
242 Self {
243 chosen: chosen.into(),
244 guarantee: None,
245 }
246 }
247}
248
249impl OffsetExpr {
250 pub fn new(chosen: impl Into<Option<ByteCount>>) -> Self {
251 Self {
252 guarantee: None,
253 chosen: chosen.into(),
254 }
255 }
256}
257
258#[derive(Debug, Clone, PartialEq, Eq, Hash)]
261#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
262#[serde_state(state_implements = DedupSerializerState)]
263pub struct InhabitedPredicate(pub HashConsed<InhabitedPredicateKind>);
264
265#[derive(Debug, Clone, PartialEq, Eq, Hash)]
266#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
267#[cfg_attr(
268 feature = "charon_on_charon",
269 charon::variants_prefix("InhabitedPredicate")
270)]
271pub enum InhabitedPredicateKind {
272 True,
273 False,
274 ConstIsZero(ConstantExpr),
276 GenericType(Ty),
278 And(Vec<InhabitedPredicate>),
279 Or(Vec<InhabitedPredicate>),
280}
281
282impl InhabitedPredicate {
283 pub fn new(kind: InhabitedPredicateKind) -> Self {
284 Self(HashConsed::new(kind))
285 }
286
287 pub fn kind(&self) -> &InhabitedPredicateKind {
288 self.0.inner()
289 }
290
291 pub fn with_kind_mut<R>(&mut self, f: impl FnOnce(&mut InhabitedPredicateKind) -> R) -> R {
292 self.0.with_inner_mut(f)
293 }
294
295 pub fn mk_true() -> Self {
296 InhabitedPredicateKind::True.into_pred()
297 }
298
299 pub fn mk_false() -> Self {
300 InhabitedPredicateKind::False.into_pred()
301 }
302
303 pub fn always_true(&self) -> bool {
304 matches!(self.kind(), InhabitedPredicateKind::True)
305 }
306
307 pub fn always_false(&self) -> bool {
308 matches!(self.kind(), InhabitedPredicateKind::False)
309 }
310
311 pub fn is_known(&self) -> bool {
312 self.always_true() || self.always_false()
313 }
314
315 pub fn as_bool(&self) -> Option<bool> {
316 match self.kind() {
317 InhabitedPredicateKind::True => Some(true),
318 InhabitedPredicateKind::False => Some(false),
319 _ => None,
320 }
321 }
322
323 pub fn normalize(mut self, krate: &TranslatedCrate, for_target: Option<&TargetTriple>) -> Self {
324 #[derive(Visitor)]
325 struct NormalizeInhabitedPredicate<'a> {
326 krate: &'a TranslatedCrate,
327 for_target: Option<&'a TargetTriple>,
328 }
329
330 fn fold_concrete_values(
331 predicates: &mut Vec<InhabitedPredicate>,
332 f: impl Fn(bool, bool) -> bool,
333 ) -> Option<bool> {
334 predicates
335 .extract_if(.., |pred| pred.is_known())
336 .map(|pred| pred.as_bool().unwrap())
337 .reduce(f)
338 }
339
340 impl VisitAstMut for NormalizeInhabitedPredicate<'_> {
341 fn exit_inhabited_predicate_kind(&mut self, pred: &mut InhabitedPredicateKind) {
342 *pred = match pred {
343 InhabitedPredicateKind::True | InhabitedPredicateKind::False => return,
344 InhabitedPredicateKind::ConstIsZero(value) => {
345 if let Some(value) = value.as_usize_literal() {
346 if value == 0 {
347 InhabitedPredicateKind::True
348 } else {
349 InhabitedPredicateKind::False
350 }
351 } else {
352 return;
353 }
354 }
355 InhabitedPredicateKind::GenericType(ty) => {
356 let mut new = ty.inhabited_predicate(self.krate, self.for_target);
357 if let InhabitedPredicateKind::GenericType(new_ty) = new.kind()
358 && new_ty == ty
359 {
360 return;
361 }
362 self.visit(&mut new);
363 new.kind().clone()
364 }
365 InhabitedPredicateKind::And(predicates) => {
366 for pred in std::mem::take(predicates) {
367 match pred.kind() {
368 InhabitedPredicateKind::And(nested) => {
369 predicates.extend(nested.iter().cloned())
370 }
371 _ => predicates.push(pred),
372 }
373 }
374 if let Some(value) = fold_concrete_values(predicates, |x, y| x && y)
375 && !value
376 {
377 InhabitedPredicateKind::False
378 } else if predicates.is_empty() {
379 InhabitedPredicateKind::True
380 } else if predicates.len() == 1 {
381 predicates.pop().unwrap().kind().clone()
382 } else {
383 return;
384 }
385 }
386 InhabitedPredicateKind::Or(predicates) => {
387 for pred in std::mem::take(predicates) {
388 match pred.kind() {
389 InhabitedPredicateKind::Or(nested) => {
390 predicates.extend(nested.iter().cloned())
391 }
392 _ => predicates.push(pred),
393 }
394 }
395 if let Some(value) = fold_concrete_values(predicates, |x, y| x || y)
396 && value
397 {
398 InhabitedPredicateKind::True
399 } else if predicates.is_empty() {
400 InhabitedPredicateKind::False
401 } else if predicates.len() == 1 {
402 predicates.pop().unwrap().kind().clone()
403 } else {
404 return;
405 }
406 }
407 };
408 }
409 }
410
411 NormalizeInhabitedPredicate { krate, for_target }.visit(&mut self);
412 self
413 }
414}
415
416impl InhabitedPredicateKind {
417 pub fn into_pred(self) -> InhabitedPredicate {
418 InhabitedPredicate::new(self)
419 }
420}
421
422impl Ty {
423 pub fn inhabited_predicate(
424 &self,
425 krate: &TranslatedCrate,
426 for_target: Option<&TargetTriple>,
427 ) -> InhabitedPredicate {
428 match self.kind() {
429 TyKind::Never => InhabitedPredicate::mk_false(),
430 TyKind::Array(ty, len, _) => match len.as_usize_literal() {
431 Some(0) => InhabitedPredicate::mk_true(),
432 Some(_) => ty.inhabited_predicate(krate, for_target),
433 None => InhabitedPredicateKind::Or(vec![
434 InhabitedPredicateKind::ConstIsZero(len.clone()).into_pred(),
435 ty.inhabited_predicate(krate, for_target),
436 ])
437 .into_pred(),
438 },
439 TyKind::Adt(ty_ref)
440 if let Some(decl) = krate.type_decls.get(ty_ref.id)
441 && let Some(layout) = if let Some(target) = for_target {
442 decl.layout.get(target)
443 } else {
444 decl.layout.values().exactly_one().ok()
445 } =>
446 {
447 layout.inhabited.clone().substitute(&ty_ref.generics)
448 }
449 TyKind::TypeVar(_) | TyKind::TraitType(..) | TyKind::Adt(_) => {
450 InhabitedPredicateKind::GenericType(self.clone()).into_pred()
451 }
452 TyKind::Scalar(_)
453 | TyKind::Slice(..)
454 | TyKind::Ref(..)
455 | TyKind::RawPtr(..)
456 | TyKind::FnDef(..)
457 | TyKind::FnPtr(..)
458 | TyKind::DynTrait(..)
459 | TyKind::Pattern(..)
460 | TyKind::PtrMetadata(..)
461 | TyKind::Error(_) => InhabitedPredicate::mk_true(),
462 }
463 }
464}
465
466impl Default for InhabitedPredicate {
467 fn default() -> Self {
468 Self::mk_true()
469 }
470}
471
472impl std::ops::Deref for InhabitedPredicate {
473 type Target = InhabitedPredicateKind;
474
475 fn deref(&self) -> &Self::Target {
476 self.kind()
477 }
478}
479
480#[derive(Debug, Default, Clone, PartialEq, Eq)]
486#[derive(Serialize, Deserialize)]
487pub struct ReprOptions {
488 pub repr_algo: ReprAlgorithm,
489 pub align_modif: Option<AlignmentModifier>,
490 pub transparent: bool,
491 pub explicit_discr_type: Option<IntegerTy>,
493}
494
495#[derive(Debug, Default, Clone, PartialEq, Eq)]
498#[derive(Serialize, Deserialize)]
499pub enum ReprAlgorithm {
500 #[default]
502 Rust,
503 C,
505 Simd,
507}
508
509#[derive(Debug, Clone, PartialEq, Eq)]
512#[derive(Serialize, Deserialize)]
513pub enum AlignmentModifier {
514 Align(ByteCount),
515 Pack(ByteCount),
516}
517
518#[derive(Debug, Clone, PartialEq)]
519#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
520#[serde_state(stateless)]
521pub struct TargetInfo {
522 pub arch: from_rustc::Arch,
524 pub vendor: String,
526 pub os: from_rustc::Os,
528 pub env: from_rustc::Env,
530 pub cfg_abi: from_rustc::CfgAbi,
532 pub families: Vec<String>,
535 pub binary_format: from_rustc::BinaryFormat,
537 pub target_pointer_size: ByteCount,
539 pub is_little_endian: bool,
541 pub c_enum_smallest_repr_ty: IntTy,
543 #[serde(with = "SeqHashMapToArray::<ScalarTy, ByteCount>")]
545 pub primitive_alignments: SeqHashMap<ScalarTy, ByteCount>,
546}
547
548#[derive(Debug, PartialEq, Eq)]
549pub enum DiscriminantReadError {
550 UninitByte,
552 InvalidDiscriminant,
554}
555
556impl Discriminator {
557 pub fn trivial(variant_id: VariantId) -> Self {
559 Self::Known(variant_id)
560 }
561
562 pub fn read_discriminant(
566 &self,
567 read: impl Fn(ByteCount, IntegerTy) -> Result<IntegerValue, DiscriminantReadError> + Copy,
568 ) -> Result<VariantId, DiscriminantReadError> {
569 match self {
570 Discriminator::Known(id) => Ok(*id),
571 Discriminator::Invalid => Err(DiscriminantReadError::InvalidDiscriminant),
572 Discriminator::Branch {
573 offset,
574 int_ty,
575 fallback,
576 children,
577 } => {
578 let offset = offset
579 .chosen
580 .expect("a discriminator must have a concrete offset");
581 let val = read(offset, *int_ty)?;
582 for (range, child) in children {
583 if range.contains(&val) {
584 return child.read_discriminant(read);
585 }
586 }
587 fallback.read_discriminant(read)
588 }
589 }
590 }
591}
592
593impl ReprOptions {
594 pub fn guarantees_fixed_field_order(&self) -> bool {
604 self.repr_algo == ReprAlgorithm::C || self.explicit_discr_type.is_some()
605 }
606}
607
608impl IntTy {
609 pub fn target_size(&self, ptr_size: ByteCount) -> usize {
612 match self {
613 IntTy::Isize => ptr_size as usize,
614 IntTy::I8 => size_of::<i8>(),
615 IntTy::I16 => size_of::<i16>(),
616 IntTy::I32 => size_of::<i32>(),
617 IntTy::I64 => size_of::<i64>(),
618 IntTy::I128 => size_of::<i128>(),
619 }
620 }
621}
622impl UIntTy {
623 pub fn target_size(&self, ptr_size: ByteCount) -> usize {
626 match self {
627 UIntTy::Usize => ptr_size as usize,
628 UIntTy::U8 => size_of::<u8>(),
629 UIntTy::U16 => size_of::<u16>(),
630 UIntTy::U32 => size_of::<u32>(),
631 UIntTy::U64 => size_of::<u64>(),
632 UIntTy::U128 => size_of::<u128>(),
633 }
634 }
635}
636impl FloatTy {
637 pub fn target_size(&self) -> usize {
640 match self {
641 FloatTy::F16 => size_of::<u16>(),
642 FloatTy::F32 => size_of::<u32>(),
643 FloatTy::F64 => size_of::<u64>(),
644 FloatTy::F128 => size_of::<u128>(),
645 }
646 }
647}