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 pointer size of the target in bytes.
497    pub target_pointer_size: ByteCount,
498    /// Whether the target platform uses little endian byte order.
499    pub is_little_endian: bool,
500    /// The minimum size of a [`repr(C)`] enum.
501    pub c_enum_smallest_repr_ty: IntTy,
502    /// Alignments for primitive types.
503    #[serde(with = "SeqHashMapToArray::<ScalarTy, ByteCount>")]
504    pub primitive_alignments: SeqHashMap<ScalarTy, ByteCount>,
505}
506
507#[derive(Debug, PartialEq, Eq)]
508pub enum DiscriminantReadError {
509    /// We read an uninitialized byte.
510    UninitByte,
511    /// We reached an invalid discriminant state.
512    InvalidDiscriminant,
513}
514
515impl Discriminator {
516    /// Make a trivial discriminator that always returns the given variant id.
517    pub fn trivial(variant_id: VariantId) -> Self {
518        Self::Known(variant_id)
519    }
520
521    /// Read a discriminant from memory. The `read` function simulates reading an integer of the
522    /// given type at the given byte offset from memory and can return `UninitByte` if the byte
523    /// could not be read.
524    pub fn read_discriminant(
525        &self,
526        read: impl Fn(ByteCount, IntegerTy) -> Result<IntegerValue, DiscriminantReadError> + Copy,
527    ) -> Result<VariantId, DiscriminantReadError> {
528        match self {
529            Discriminator::Known(id) => Ok(*id),
530            Discriminator::Invalid => Err(DiscriminantReadError::InvalidDiscriminant),
531            Discriminator::Branch {
532                offset,
533                int_ty,
534                fallback,
535                children,
536            } => {
537                let offset = offset
538                    .chosen
539                    .expect("a discriminator must have a concrete offset");
540                let val = read(offset, *int_ty)?;
541                for (range, child) in children {
542                    if range.contains(&val) {
543                        return child.read_discriminant(read);
544                    }
545                }
546                fallback.read_discriminant(read)
547            }
548        }
549    }
550}
551
552impl ReprOptions {
553    /// Whether this representation options guarantee a fixed
554    /// field ordering for the type.
555    ///
556    /// Since we don't support `repr(simd)` or `repr(linear)` yet, this is
557    /// the case if it's either `repr(C)` or an explicit discriminant type for
558    /// an enum with fields (if it doesn't have fields, this obviously doesn't matter anyway).
559    ///
560    /// Cf. <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.c.struct>
561    /// and <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.primitive.adt>.
562    pub fn guarantees_fixed_field_order(&self) -> bool {
563        self.repr_algo == ReprAlgorithm::C || self.explicit_discr_type.is_some()
564    }
565}
566
567impl IntTy {
568    /// Important: this returns the target byte count for the types.
569    /// Must not be used for host types from rustc.
570    pub fn target_size(&self, ptr_size: ByteCount) -> usize {
571        match self {
572            IntTy::Isize => ptr_size as usize,
573            IntTy::I8 => size_of::<i8>(),
574            IntTy::I16 => size_of::<i16>(),
575            IntTy::I32 => size_of::<i32>(),
576            IntTy::I64 => size_of::<i64>(),
577            IntTy::I128 => size_of::<i128>(),
578        }
579    }
580}
581impl UIntTy {
582    /// Important: this returns the target byte count for the types.
583    /// Must not be used for host types from rustc.
584    pub fn target_size(&self, ptr_size: ByteCount) -> usize {
585        match self {
586            UIntTy::Usize => ptr_size as usize,
587            UIntTy::U8 => size_of::<u8>(),
588            UIntTy::U16 => size_of::<u16>(),
589            UIntTy::U32 => size_of::<u32>(),
590            UIntTy::U64 => size_of::<u64>(),
591            UIntTy::U128 => size_of::<u128>(),
592        }
593    }
594}
595impl FloatTy {
596    /// Important: this returns the target byte count for the types.
597    /// Must not be used for host types from rustc.
598    pub fn target_size(&self) -> usize {
599        match self {
600            FloatTy::F16 => size_of::<u16>(),
601            FloatTy::F32 => size_of::<u32>(),
602            FloatTy::F64 => size_of::<u64>(),
603            FloatTy::F128 => size_of::<u128>(),
604        }
605    }
606}
charon_lib/ast/items/layout.rs

charon_lib/ast/items/
layout.rs
