charon_lib/ast/items/
layout.rs

1//! The layout of types.
2use 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/// Type layout information.
13///
14/// Does not include information about niches.
15/// If the type does not have a fully known layout (e.g. it is ?Sized)
16/// some of the layout parts are not available.
17#[derive(Debug, Clone, SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
18pub struct Layout {
19    /// The size of the type in bytes.
20    pub size: Size,
21    /// The alignment, in bytes.
22    pub align: Size,
23    /// Decision tree that determines the active variant by reading memory. Only `Some` for enums.
24    pub discriminator: Option<Discriminator>,
25    /// Whether the type has any valid value.
26    /// Note that uninhabited types can have arbitrary layouts: `(u32, !)` has space for the `u32`
27    /// and `enum E2 { A, B(!), C(i32, !) }` may have space for a discriminant.
28    pub inhabited: InhabitedPredicate,
29    /// Map from `VariantId` to the corresponding field layouts. Some variants don't have a
30    /// meaningful layout due to being uninhabited (though an uninhabited variant may have a
31    /// layout). Structs and unions are modeled as having exactly one variant.
32    pub variant_layouts: IndexVec<VariantId, Option<VariantLayout>>,
33    /// The representation options of this type declaration as annotated by the user.
34    #[serde_state(stateless)]
35    pub repr: ReprOptions,
36}
37
38/// Simplified layout of a single variant.
39///
40/// Maps fields to their offset within the layout.
41#[derive(Debug, Default, Clone, SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
42pub struct VariantLayout {
43    /// The offset of each field.
44    pub field_offsets: IndexVec<FieldId, OffsetExpr>,
45    /// Whether the variant has any valid possible value.
46    /// Note that uninhabited types can have arbitrary layouts.
47    pub inhabited: InhabitedPredicate,
48    /// How to write the tag when constructing this variant. Each entry means: write `value` at
49    /// byte `offset`. Mirrors MiniRust's `Variant::tagger`.
50    #[serde_state(stateless)]
51    pub tagger: Vec<(ByteCount, IntegerValue)>,
52}
53
54impl Layout {
55    /// Construct a layout for this type. The returned layout contains no size-related information.
56    pub fn for_type(
57        krate: &TranslatedCrate,
58        kind: &TypeDeclKind,
59        repr: ReprOptions,
60    ) -> Option<Self> {
61        let fields_inhabited = |fields: &IndexVec<FieldId, Field>| {
62            InhabitedPredicateKind::And(
63                fields
64                    .iter()
65                    .map(|field| field.ty.inhabited_predicate(krate, None))
66                    .collect(),
67            )
68            .into_pred()
69        };
70
71        let (inhabited, variant_layouts) = match kind {
72            TypeDeclKind::Struct(fields) => {
73                let inhabited = fields_inhabited(fields);
74                let field_offsets = fields
75                    .iter()
76                    .map(|_| OffsetExpr::new(None::<ByteCount>))
77                    .collect();
78                let layouts = vec![Some(VariantLayout {
79                    field_offsets,
80                    inhabited: inhabited.clone(),
81                    tagger: Vec::new(),
82                })]
83                .into();
84                (inhabited, layouts)
85            }
86            TypeDeclKind::Union(fields) => {
87                let inhabited = InhabitedPredicateKind::Or(
88                    fields
89                        .iter()
90                        .map(|field| field.ty.inhabited_predicate(krate, None))
91                        .collect(),
92                )
93                .into_pred();
94                let field_offsets = fields
95                    .iter()
96                    .map(|_| OffsetExpr::new(None::<ByteCount>))
97                    .collect();
98                let layouts = vec![Some(VariantLayout {
99                    field_offsets,
100                    inhabited: inhabited.clone(),
101                    tagger: Vec::new(),
102                })]
103                .into();
104                (inhabited, layouts)
105            }
106            TypeDeclKind::Enum(variants) => {
107                let mut layouts = IndexVec::new();
108                let mut variant_predicates = Vec::new();
109                for variant in variants {
110                    let variant_inhabited = fields_inhabited(&variant.fields);
111                    let field_offsets = variant
112                        .fields
113                        .iter()
114                        .map(|_| OffsetExpr::new(None::<ByteCount>))
115                        .collect();
116                    layouts.push(Some(VariantLayout {
117                        field_offsets,
118                        inhabited: variant_inhabited.clone(),
119                        tagger: Vec::new(),
120                    }));
121                    variant_predicates.push(variant_inhabited);
122                }
123                (
124                    InhabitedPredicateKind::Or(variant_predicates).into_pred(),
125                    layouts,
126                )
127            }
128            TypeDeclKind::Alias(ty) => (ty.inhabited_predicate(krate, None), IndexVec::new()),
129            TypeDeclKind::Opaque | TypeDeclKind::Error(_) => return None,
130        };
131
132        Some(Self {
133            size: Size::from_expr(None),
134            align: Size::from_expr(None),
135            discriminator: None,
136            inhabited,
137            variant_layouts,
138            repr,
139        })
140    }
141
142    pub fn is_variant_always_uninhabited(&self, variant_id: VariantId) -> bool {
143        self.variant_layouts[variant_id]
144            .as_ref()
145            .is_none_or(|layout| layout.inhabited.always_false())
146    }
147
148    pub fn is_variant_always_inhabited(&self, variant_id: VariantId) -> bool {
149        self.variant_layouts[variant_id]
150            .as_ref()
151            .is_some_and(|layout| layout.inhabited.always_true())
152    }
153
154    pub fn is_c_repr(&self) -> bool {
155        self.repr.repr_algo == ReprAlgorithm::C
156    }
157}
158
159/// Decision tree used to determine the active variant by reading memory. Mirrors MiniRust's
160/// `Discriminator`.
161#[derive(Debug, Clone, SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
162#[serde_state(state_implements = DedupSerializerState)]
163pub enum Discriminator {
164    /// The variant is known.
165    Known(VariantId),
166    /// No valid variant (e.g., invalid tag value).
167    Invalid,
168    /// Branch on an integer value read from memory at `offset`.
169    Branch {
170        /// Byte offset to read from.
171        offset: OffsetExpr,
172        /// Integer type to read.
173        #[serde_state(stateless)]
174        int_ty: IntegerTy,
175        /// If the integer is in one of these ranges, continue with the given `Discriminator`. The
176        /// ranges are sorted.
177        children: Vec<(std::ops::RangeInclusive<IntegerValue>, Discriminator)>,
178        /// Fallback if no range in `children` matches.
179        fallback: Box<Discriminator>,
180    },
181}
182
183/// An expression denoting a size in bytes.
184#[derive(Debug, Clone, SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
185pub struct Size {
186    /// The size chosen by this rustc run. For sized types, this is a plain integer, and for unsized
187    /// types, this is an expression describing how to compute this size based on the values found
188    /// in the pointer metadata. This can be `None` for polymorphic types.
189    pub chosen: Option<SizeExpr>,
190    /// The guarantees about this size that can be relied on according to the Rust Reference.
191    pub guarantee: Option<SizeExpr>,
192}
193
194/// An expression denoting an offset in bytes.
195#[derive(Debug, Clone, SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
196pub struct OffsetExpr {
197    /// The guarantees about this offset that can be relied on according to the Rust Reference.
198    pub guarantee: Option<OffsetGuarantee>,
199    /// The offset chosen by this rustc run. `None` for unsized fields.
200    pub chosen: Option<ByteCount>,
201}
202
203impl Size {
204    pub fn new(chosen: impl Into<Option<ByteCount>>) -> Self {
205        Self::from_expr(
206            chosen
207                .into()
208                .map(|chosen| SizeExprKind::from_usize(u128::from(chosen)).into_expr()),
209        )
210    }
211
212    pub fn from_expr(chosen: impl Into<Option<SizeExpr>>) -> Self {
213        Self {
214            chosen: chosen.into(),
215            guarantee: None,
216        }
217    }
218}
219
220impl OffsetExpr {
221    pub fn new(chosen: impl Into<Option<ByteCount>>) -> Self {
222        Self {
223            guarantee: None,
224            chosen: chosen.into(),
225        }
226    }
227}
228
229/// Represents whether a type or variant is inhabited. Like rustc's `InhabitedPredicate`, this can
230/// depend on generic parameters and constant values.
231#[derive(
232    Debug, Clone, PartialEq, Eq, Hash, SerializeState, DeserializeState, Drive, DriveMut, DriveTwo,
233)]
234#[serde_state(state_implements = DedupSerializerState)]
235pub struct InhabitedPredicate(pub HashConsed<InhabitedPredicateKind>);
236
237#[derive(
238    Debug, Clone, PartialEq, Eq, Hash, SerializeState, DeserializeState, Drive, DriveMut, DriveTwo,
239)]
240#[cfg_attr(
241    feature = "charon_on_charon",
242    charon::variants_prefix("InhabitedPredicate")
243)]
244pub enum InhabitedPredicateKind {
245    True,
246    False,
247    /// Inhabited when this constant is zero.
248    ConstIsZero(ConstantExpr),
249    /// Inhabited when this generic type is inhabited.
250    GenericType(Ty),
251    And(Vec<InhabitedPredicate>),
252    Or(Vec<InhabitedPredicate>),
253}
254
255impl InhabitedPredicate {
256    pub fn new(kind: InhabitedPredicateKind) -> Self {
257        Self(HashConsed::new(kind))
258    }
259
260    pub fn kind(&self) -> &InhabitedPredicateKind {
261        self.0.inner()
262    }
263
264    pub fn with_kind_mut<R>(&mut self, f: impl FnOnce(&mut InhabitedPredicateKind) -> R) -> R {
265        self.0.with_inner_mut(f)
266    }
267
268    pub fn mk_true() -> Self {
269        InhabitedPredicateKind::True.into_pred()
270    }
271
272    pub fn mk_false() -> Self {
273        InhabitedPredicateKind::False.into_pred()
274    }
275
276    pub fn always_true(&self) -> bool {
277        matches!(self.kind(), InhabitedPredicateKind::True)
278    }
279
280    pub fn always_false(&self) -> bool {
281        matches!(self.kind(), InhabitedPredicateKind::False)
282    }
283
284    pub fn is_known(&self) -> bool {
285        self.always_true() || self.always_false()
286    }
287
288    pub fn as_bool(&self) -> Option<bool> {
289        match self.kind() {
290            InhabitedPredicateKind::True => Some(true),
291            InhabitedPredicateKind::False => Some(false),
292            _ => None,
293        }
294    }
295
296    pub fn normalize(mut self, krate: &TranslatedCrate, for_target: Option<&TargetTriple>) -> Self {
297        #[derive(Visitor)]
298        struct NormalizeInhabitedPredicate<'a> {
299            krate: &'a TranslatedCrate,
300            for_target: Option<&'a TargetTriple>,
301        }
302
303        fn fold_concrete_values(
304            predicates: &mut Vec<InhabitedPredicate>,
305            f: impl Fn(bool, bool) -> bool,
306        ) -> Option<bool> {
307            predicates
308                .extract_if(.., |pred| pred.is_known())
309                .map(|pred| pred.as_bool().unwrap())
310                .reduce(f)
311        }
312
313        impl VisitAstMut for NormalizeInhabitedPredicate<'_> {
314            fn exit_inhabited_predicate_kind(&mut self, pred: &mut InhabitedPredicateKind) {
315                *pred = match pred {
316                    InhabitedPredicateKind::True | InhabitedPredicateKind::False => return,
317                    InhabitedPredicateKind::ConstIsZero(value) => {
318                        if let Some(value) = value.as_usize_literal() {
319                            if value == 0 {
320                                InhabitedPredicateKind::True
321                            } else {
322                                InhabitedPredicateKind::False
323                            }
324                        } else {
325                            return;
326                        }
327                    }
328                    InhabitedPredicateKind::GenericType(ty) => {
329                        let mut new = ty.inhabited_predicate(self.krate, self.for_target);
330                        if let InhabitedPredicateKind::GenericType(new_ty) = new.kind()
331                            && new_ty == ty
332                        {
333                            return;
334                        }
335                        self.visit(&mut new);
336                        new.kind().clone()
337                    }
338                    InhabitedPredicateKind::And(predicates) => {
339                        for pred in std::mem::take(predicates) {
340                            match pred.kind() {
341                                InhabitedPredicateKind::And(nested) => {
342                                    predicates.extend(nested.iter().cloned())
343                                }
344                                _ => predicates.push(pred),
345                            }
346                        }
347                        if let Some(value) = fold_concrete_values(predicates, |x, y| x && y)
348                            && !value
349                        {
350                            InhabitedPredicateKind::False
351                        } else if predicates.is_empty() {
352                            InhabitedPredicateKind::True
353                        } else if predicates.len() == 1 {
354                            predicates.pop().unwrap().kind().clone()
355                        } else {
356                            return;
357                        }
358                    }
359                    InhabitedPredicateKind::Or(predicates) => {
360                        for pred in std::mem::take(predicates) {
361                            match pred.kind() {
362                                InhabitedPredicateKind::Or(nested) => {
363                                    predicates.extend(nested.iter().cloned())
364                                }
365                                _ => predicates.push(pred),
366                            }
367                        }
368                        if let Some(value) = fold_concrete_values(predicates, |x, y| x || y)
369                            && value
370                        {
371                            InhabitedPredicateKind::True
372                        } else if predicates.is_empty() {
373                            InhabitedPredicateKind::False
374                        } else if predicates.len() == 1 {
375                            predicates.pop().unwrap().kind().clone()
376                        } else {
377                            return;
378                        }
379                    }
380                };
381            }
382        }
383
384        NormalizeInhabitedPredicate { krate, for_target }.visit(&mut self);
385        self
386    }
387}
388
389impl InhabitedPredicateKind {
390    pub fn into_pred(self) -> InhabitedPredicate {
391        InhabitedPredicate::new(self)
392    }
393}
394
395impl Ty {
396    pub fn inhabited_predicate(
397        &self,
398        krate: &TranslatedCrate,
399        for_target: Option<&TargetTriple>,
400    ) -> InhabitedPredicate {
401        match self.kind() {
402            TyKind::Never => InhabitedPredicate::mk_false(),
403            TyKind::Array(ty, len, _) => match len.as_usize_literal() {
404                Some(0) => InhabitedPredicate::mk_true(),
405                Some(_) => ty.inhabited_predicate(krate, for_target),
406                None => InhabitedPredicateKind::Or(vec![
407                    InhabitedPredicateKind::ConstIsZero(len.clone()).into_pred(),
408                    ty.inhabited_predicate(krate, for_target),
409                ])
410                .into_pred(),
411            },
412            TyKind::Adt(ty_ref)
413                if let Some(decl) = krate.type_decls.get(ty_ref.id)
414                    && let Some(layout) = if let Some(target) = for_target {
415                        decl.layout.get(target)
416                    } else {
417                        decl.layout.values().exactly_one().ok()
418                    } =>
419            {
420                layout.inhabited.clone().substitute(&ty_ref.generics)
421            }
422            TyKind::TypeVar(_) | TyKind::TraitType(..) | TyKind::Adt(_) => {
423                InhabitedPredicateKind::GenericType(self.clone()).into_pred()
424            }
425            TyKind::Scalar(_)
426            | TyKind::Slice(..)
427            | TyKind::Ref(..)
428            | TyKind::RawPtr(..)
429            | TyKind::FnDef(..)
430            | TyKind::FnPtr(..)
431            | TyKind::DynTrait(..)
432            | TyKind::Pattern(..)
433            | TyKind::PtrMetadata(..)
434            | TyKind::Error(_) => InhabitedPredicate::mk_true(),
435        }
436    }
437}
438
439impl Default for InhabitedPredicate {
440    fn default() -> Self {
441        Self::mk_true()
442    }
443}
444
445impl std::ops::Deref for InhabitedPredicate {
446    type Target = InhabitedPredicateKind;
447
448    fn deref(&self) -> &Self::Target {
449        self.kind()
450    }
451}
452
453/// The representation options as annotated by the user.
454///
455/// NOTE: This does not include less common/unstable representations such as `#[repr(simd)]`
456/// or the compiler internal `#[repr(linear)]`. Similarly, enum discriminant representations
457/// are encoded in [`Variant::discriminant`] and [`Discriminator`] instead.
458#[derive(Debug, Default, Clone, PartialEq, Eq, Serialize, Deserialize)]
459pub struct ReprOptions {
460    pub repr_algo: ReprAlgorithm,
461    pub align_modif: Option<AlignmentModifier>,
462    pub transparent: bool,
463    /// The type supplied to `repr(..)`, if any.
464    pub explicit_discr_type: Option<IntegerTy>,
465}
466
467/// Describes which layout algorithm is used for representing the corresponding type.
468/// Depends on the `#[repr(...)]` used.
469#[derive(Debug, Default, Clone, PartialEq, Eq, Serialize, Deserialize)]
470pub enum ReprAlgorithm {
471    /// The default layout algorithm. Used without an explicit `ŗepr` or for `repr(Rust)`.
472    #[default]
473    Rust,
474    /// The C layout algorithm as enforced by `repr(C)`.
475    C,
476}
477
478/// Describes modifiers to the alignment and packing of the corresponding type.
479/// Represents `repr(align(n))` and `repr(packed(n))`.
480#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
481pub enum AlignmentModifier {
482    Align(ByteCount),
483    Pack(ByteCount),
484}
485
486#[derive(Clone, Drive, DriveMut, DriveTwo, SerializeState, DeserializeState)]
487#[serde_state(stateless)]
488pub struct TargetInfo {
489    /// The pointer size of the target in bytes.
490    pub target_pointer_size: ByteCount,
491    /// Whether the target platform uses little endian byte order.
492    pub is_little_endian: bool,
493    /// The minimum size of a [`repr(C)`] enum.
494    pub c_enum_smallest_repr_ty: IntTy,
495    /// Alignments for primitive types.
496    #[serde(with = "SeqHashMapToArray::<ScalarTy, ByteCount>")]
497    pub primitive_alignments: SeqHashMap<ScalarTy, ByteCount>,
498}
499
500#[derive(Debug, PartialEq, Eq)]
501pub enum DiscriminantReadError {
502    /// We read an uninitialized byte.
503    UninitByte,
504    /// We reached an invalid discriminant state.
505    InvalidDiscriminant,
506}
507
508impl Discriminator {
509    /// Make a trivial discriminator that always returns the given variant id.
510    pub fn trivial(variant_id: VariantId) -> Self {
511        Self::Known(variant_id)
512    }
513
514    /// Read a discriminant from memory. The `read` function simulates reading an integer of the
515    /// given type at the given byte offset from memory and can return `UninitByte` if the byte
516    /// could not be read.
517    pub fn read_discriminant(
518        &self,
519        read: impl Fn(ByteCount, IntegerTy) -> Result<IntegerValue, DiscriminantReadError> + Copy,
520    ) -> Result<VariantId, DiscriminantReadError> {
521        match self {
522            Discriminator::Known(id) => Ok(*id),
523            Discriminator::Invalid => Err(DiscriminantReadError::InvalidDiscriminant),
524            Discriminator::Branch {
525                offset,
526                int_ty,
527                fallback,
528                children,
529            } => {
530                let offset = offset
531                    .chosen
532                    .expect("a discriminator must have a concrete offset");
533                let val = read(offset, *int_ty)?;
534                for (range, child) in children {
535                    if range.contains(&val) {
536                        return child.read_discriminant(read);
537                    }
538                }
539                fallback.read_discriminant(read)
540            }
541        }
542    }
543}
544
545impl ReprOptions {
546    /// Whether this representation options guarantee a fixed
547    /// field ordering for the type.
548    ///
549    /// Since we don't support `repr(simd)` or `repr(linear)` yet, this is
550    /// the case if it's either `repr(C)` or an explicit discriminant type for
551    /// an enum with fields (if it doesn't have fields, this obviously doesn't matter anyway).
552    ///
553    /// Cf. <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.c.struct>
554    /// and <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.primitive.adt>.
555    pub fn guarantees_fixed_field_order(&self) -> bool {
556        self.repr_algo == ReprAlgorithm::C || self.explicit_discr_type.is_some()
557    }
558}
559
560impl IntTy {
561    /// Important: this returns the target byte count for the types.
562    /// Must not be used for host types from rustc.
563    pub fn target_size(&self, ptr_size: ByteCount) -> usize {
564        match self {
565            IntTy::Isize => ptr_size as usize,
566            IntTy::I8 => size_of::<i8>(),
567            IntTy::I16 => size_of::<i16>(),
568            IntTy::I32 => size_of::<i32>(),
569            IntTy::I64 => size_of::<i64>(),
570            IntTy::I128 => size_of::<i128>(),
571        }
572    }
573}
574impl UIntTy {
575    /// Important: this returns the target byte count for the types.
576    /// Must not be used for host types from rustc.
577    pub fn target_size(&self, ptr_size: ByteCount) -> usize {
578        match self {
579            UIntTy::Usize => ptr_size as usize,
580            UIntTy::U8 => size_of::<u8>(),
581            UIntTy::U16 => size_of::<u16>(),
582            UIntTy::U32 => size_of::<u32>(),
583            UIntTy::U64 => size_of::<u64>(),
584            UIntTy::U128 => size_of::<u128>(),
585        }
586    }
587}
588impl FloatTy {
589    /// Important: this returns the target byte count for the types.
590    /// Must not be used for host types from rustc.
591    pub fn target_size(&self) -> usize {
592        match self {
593            FloatTy::F16 => size_of::<u16>(),
594            FloatTy::F32 => size_of::<u32>(),
595            FloatTy::F64 => size_of::<u64>(),
596            FloatTy::F128 => size_of::<u128>(),
597        }
598    }
599}
charon_lib/ast/items/layout.rs

charon_lib/ast/items/
layout.rs
