Skip to main content

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, PartialEq)]
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    /// For unions: the `(offset, size)` ranges of bytes that aren't padding, i.e. that are data in
35    /// at least one field. The other bytes are lost on a typed copy. `None` for non-unions and when
36    /// the layout isn't known.
37    #[serde_state(stateless)]
38    pub union_chunks: Option<Vec<(ByteCount, ByteCount)>>,
39    /// The representation options of this type declaration as annotated by the user.
40    #[serde_state(stateless)]
41    pub repr: ReprOptions,
42}
43
44/// The layouts of a type, for each target.
45#[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/// Simplified layout of a single variant.
63///
64/// Maps fields to their offset within the layout.
65#[derive(Debug, Default, Clone, PartialEq)]
66#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
67pub struct VariantLayout {
68    /// The offset of each field.
69    pub field_offsets: IndexVec<FieldId, OffsetExpr>,
70    /// Whether the variant has any valid possible value.
71    /// Note that uninhabited types can have arbitrary layouts.
72    pub inhabited: InhabitedPredicate,
73    /// How to write the tag when constructing this variant. Each entry means: write `value` at
74    /// byte `offset`. Mirrors MiniRust's `Variant::tagger`.
75    #[serde_state(stateless)]
76    pub tagger: Vec<(ByteCount, IntegerValue)>,
77}
78
79impl Layout {
80    /// Construct a layout for this type. The returned layout contains no size-related information.
81    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/// Decision tree used to determine the active variant by reading memory. Mirrors MiniRust's
186/// `Discriminator`.
187#[derive(Debug, Clone, PartialEq)]
188#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
189#[serde_state(state_implements = DedupSerializerState)]
190pub enum Discriminator {
191    /// The variant is known.
192    Known(VariantId),
193    /// No valid variant (e.g., invalid tag value).
194    Invalid,
195    /// Branch on an integer value read from memory at `offset`.
196    Branch {
197        /// Byte offset to read from.
198        offset: OffsetExpr,
199        /// Integer type to read.
200        #[serde_state(stateless)]
201        int_ty: IntegerTy,
202        /// If the integer is in one of these ranges, continue with the given `Discriminator`. The
203        /// ranges are sorted.
204        children: Vec<(std::ops::RangeInclusive<IntegerValue>, Discriminator)>,
205        /// Fallback if no range in `children` matches.
206        fallback: Box<Discriminator>,
207    },
208}
209
210/// An expression denoting a size in bytes.
211#[derive(Debug, Clone, PartialEq)]
212#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
213pub struct Size {
214    /// The size chosen by this rustc run. For sized types, this is a plain integer, and for unsized
215    /// types, this is an expression describing how to compute this size based on the values found
216    /// in the pointer metadata. This can be `None` for polymorphic types.
217    pub chosen: Option<SizeExpr>,
218    /// The guarantees about this size that can be relied on according to the Rust Reference.
219    pub guarantee: Option<SizeExpr>,
220}
221
222/// An expression denoting an offset in bytes.
223#[derive(Debug, Clone, PartialEq)]
224#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
225pub struct OffsetExpr {
226    /// The guarantees about this offset that can be relied on according to the Rust Reference.
227    pub guarantee: Option<OffsetGuarantee>,
228    /// The offset chosen by this rustc run. `None` for unsized fields.
229    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/// Represents whether a type or variant is inhabited. Like rustc's `InhabitedPredicate`, this can
259/// depend on generic parameters and constant values.
260#[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    /// Inhabited when this constant is zero.
275    ConstIsZero(ConstantExpr),
276    /// Inhabited when this generic type is inhabited.
277    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/// The representation options as annotated by the user.
481///
482/// NOTE: This does not include the compiler internal `#[repr(linear)]`. Similarly, enum
483/// discriminant representations are encoded in [`Variant::discriminant`] and [`Discriminator`]
484/// instead.
485#[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    /// The type supplied to `repr(..)`, if any.
492    pub explicit_discr_type: Option<IntegerTy>,
493}
494
495/// Describes which layout algorithm is used for representing the corresponding type.
496/// Depends on the `#[repr(...)]` used.
497#[derive(Debug, Default, Clone, PartialEq, Eq)]
498#[derive(Serialize, Deserialize)]
499pub enum ReprAlgorithm {
500    /// The default layout algorithm. Used without an explicit `Ĺ—epr` or for `repr(Rust)`.
501    #[default]
502    Rust,
503    /// The C layout algorithm as enforced by `repr(C)`.
504    C,
505    /// The SIMD vector layout algorithm as enforced by the unstable `repr(simd)`.
506    Simd,
507}
508
509/// Describes modifiers to the alignment and packing of the corresponding type.
510/// Represents `repr(align(n))` and `repr(packed(n))`.
511#[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    /// The target architecture, as seen by `cfg(target_arch)`.
523    pub arch: from_rustc::Arch,
524    /// The target vendor, as seen by `cfg(target_vendor)`.
525    pub vendor: String,
526    /// The target OS, as seen by `cfg(target_os)`.
527    pub os: from_rustc::Os,
528    /// The target environment, as seen by `cfg(target_env)`.
529    pub env: from_rustc::Env,
530    /// The target ABI, as seen by `cfg(target_abi)`.
531    pub cfg_abi: from_rustc::CfgAbi,
532    /// The target families, as seen by `cfg(target_family)` (e.g. `unix`, or both `unix` and
533    /// `wasm`), as rustc spells them.
534    pub families: Vec<String>,
535    /// The binary format of the target's object files.
536    pub binary_format: from_rustc::BinaryFormat,
537    /// The pointer size of the target in bytes.
538    pub target_pointer_size: ByteCount,
539    /// Whether the target platform uses little endian byte order.
540    pub is_little_endian: bool,
541    /// The minimum size of a [`repr(C)`] enum.
542    pub c_enum_smallest_repr_ty: IntTy,
543    /// Alignments for primitive types.
544    #[serde(with = "SeqHashMapToArray::<ScalarTy, ByteCount>")]
545    pub primitive_alignments: SeqHashMap<ScalarTy, ByteCount>,
546}
547
548#[derive(Debug, PartialEq, Eq)]
549pub enum DiscriminantReadError {
550    /// We read an uninitialized byte.
551    UninitByte,
552    /// We reached an invalid discriminant state.
553    InvalidDiscriminant,
554}
555
556impl Discriminator {
557    /// Make a trivial discriminator that always returns the given variant id.
558    pub fn trivial(variant_id: VariantId) -> Self {
559        Self::Known(variant_id)
560    }
561
562    /// Read a discriminant from memory. The `read` function simulates reading an integer of the
563    /// given type at the given byte offset from memory and can return `UninitByte` if the byte
564    /// could not be read.
565    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    /// Whether this representation options guarantee a fixed
595    /// field ordering for the type.
596    ///
597    /// Since we don't support `repr(linear)` yet, this is the case if it's either `repr(C)` or an
598    /// explicit discriminant type for an enum with fields (if it doesn't have fields, this
599    /// obviously doesn't matter anyway).
600    ///
601    /// Cf. <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.c.struct>
602    /// and <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.primitive.adt>.
603    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    /// Important: this returns the target byte count for the types.
610    /// Must not be used for host types from rustc.
611    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    /// Important: this returns the target byte count for the types.
624    /// Must not be used for host types from rustc.
625    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    /// Important: this returns the target byte count for the types.
638    /// Must not be used for host types from rustc.
639    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}