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

charon_lib/ast/items/
layout.rs
