charon_lib/transform/add_missing_info/
compute_layout_guarantees.rs

1//! Compute layout facts guaranteed by the language, following the rules of the Rust Reference:
2//! <https://doc.rust-lang.org/reference/type-layout.html>.
3use itertools::Itertools;
4
5use crate::ast::*;
6use crate::options::TranslateOptions;
7use crate::transform::{TransformCtx, ctx::TransformPass};
8
9pub struct Transform;
10
11struct Guarantees {
12    size: SizeExpr,
13    align: SizeExpr,
14    offsets: IndexVec<VariantId, IndexVec<FieldId, OffsetGuarantee>>,
15}
16
17fn compute_guarantees(
18    krate: &TranslatedCrate,
19    target: &TargetTriple,
20    decl: &TypeDecl,
21) -> Option<Guarantees> {
22    let layout = decl.layout.get(target)?;
23    let repr = &layout.repr;
24    let field_tys = |fields: &IndexVec<FieldId, Field>| {
25        fields.iter().map(|field| field.ty.clone()).collect_vec()
26    };
27
28    // The fields of each variant. Structs and unions are modeled as having exactly one variant.
29    let variants: Vec<(Option<VariantId>, Vec<Ty>)> = match &decl.kind {
30        TypeDeclKind::Struct(fields) | TypeDeclKind::Union(fields) => {
31            vec![(None, field_tys(fields))]
32        }
33        TypeDeclKind::Enum(variants) => variants
34            .iter_enumerated()
35            .map(|(id, variant)| (Some(id), field_tys(&variant.fields)))
36            .collect(),
37        // An alias has the layout of the aliased type.
38        TypeDeclKind::Alias(ty) => {
39            return Some(Guarantees {
40                size: SizeExpr::size_of(ty),
41                align: SizeExpr::align_of(ty),
42                offsets: IndexVec::new(),
43            });
44        }
45        TypeDeclKind::Opaque | TypeDeclKind::Error(_) => return None,
46    };
47
48    // `repr(packed)` caps the alignment of each field, for the purpose of positioning them.
49    // <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.alignment.packed-fields>
50    let field_align = |ty: &Ty| {
51        let align = SizeExpr::align_of(ty);
52        match repr.align_modif {
53            Some(AlignmentModifier::Pack(pack)) => {
54                SizeExprKind::Min(vec![align, SizeExpr::from_usize(pack.into())]).into_expr()
55            }
56            _ => align,
57        }
58    };
59
60    // The alignment of the type is the largest of the given alignments; `repr(align)` raises it.
61    // <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.alignment.align>
62    let type_align = |mut aligns: Vec<SizeExpr>| {
63        if let Some(AlignmentModifier::Align(align)) = repr.align_modif {
64            aligns.push(SizeExpr::from_usize(align.into()));
65        }
66        SizeExpr::max_align(aligns)
67    };
68
69    // The type has the layout of its single non-1-ZST field. Since the other fields are 1-ZSTs,
70    // that's the maximum size and alignment over all the fields.
71    // <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.transparent>
72    if repr.transparent {
73        let Ok([(_, fields)]) = <[_; 1]>::try_from(variants) else {
74            unreachable!("repr(transparent) on a type with multiple variants");
75        };
76        let size = SizeExpr::max_size(fields.iter().map(SizeExpr::size_of).collect());
77        let align = SizeExpr::max_align(fields.iter().map(SizeExpr::align_of).collect());
78        let offsets = fields
79            .iter()
80            .map(SizeExpr::align_of)
81            .map(OffsetGuarantee::GuaranteedAlignment)
82            .collect();
83        return Some(Guarantees {
84            size,
85            align,
86            offsets: [offsets].into(),
87        });
88    }
89
90    // `repr(C)` and `repr(int)` enums have a tag of the given type, or of the C default one.
91    // <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.c.enum>
92    // <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.primitive.enum>
93    let tag_ty = (decl.kind.is_enum() && repr.guarantees_fixed_field_order()).then(|| {
94        let int_ty = repr.explicit_discr_type.unwrap_or(IntegerTy::Signed(
95            krate.target_information[target].c_enum_smallest_repr_ty,
96        ));
97        TyKind::Scalar(ScalarTy::Integer(int_ty)).into_ty()
98    });
99    let is_repr_c_like = repr.repr_algo == ReprAlgorithm::C || tag_ty.is_some();
100
101    // All the fields are at offset zero; the size is the largest field size rounded up to the alignment.
102    // <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.c.union>.
103    if decl.kind.is_union() && is_repr_c_like {
104        let Ok([(_, fields)]) = <[_; 1]>::try_from(variants) else {
105            unreachable!("union with multiple variants");
106        };
107        let offsets = vec![OffsetGuarantee::AtOffset(SizeExpr::from_usize(0)); fields.len()].into();
108        let align = type_align(fields.iter().map(field_align).collect());
109        let size = SizeExpr::align_to(
110            SizeExpr::max_size(fields.iter().map(SizeExpr::size_of).collect()),
111            align.clone(),
112        );
113        return Some(Guarantees {
114            size,
115            align,
116            offsets: [offsets].into(),
117        });
118    }
119
120    // A field-less enum has the layout of its tag.
121    // <https://doc.rust-lang.org/reference/type-layout.html#reprc-field-less-enums>
122    // <https://doc.rust-lang.org/reference/type-layout.html#primitive-representation-of-field-less-enums>
123    if let TypeDeclKind::Enum(variants) = &decl.kind
124        && variants.iter().all(|variant| variant.fields.is_empty())
125        && let Some(tag_ty) = &tag_ty
126    {
127        return Some(Guarantees {
128            size: SizeExpr::size_of(tag_ty),
129            align: SizeExpr::align_of(tag_ty),
130            offsets: variants.map_ref(|_| IndexVec::new()),
131        });
132    }
133
134    // The fields of each variant are laid out in order, each at the first properly aligned
135    // offset after the previous one. The size is the end of the last field (of any variant),
136    // rounded up to the alignment.
137    // <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.c.struct>
138    // <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.c.adt>
139    // <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.primitive.adt>
140    if is_repr_c_like {
141        // The end of the last field of each variant.
142        let variant_ends = variants.iter().filter_map(|(variant, fields)| {
143            let (last, ty) = fields.iter().enumerate().next_back()?;
144            let offset = SizeExpr::offset_of(decl.self_ref(), *variant, FieldId::from_usize(last));
145            Some(SizeExprKind::Plus(offset, SizeExpr::size_of(ty)).into_expr())
146        });
147        let field_aligns = variants
148            .iter()
149            .flat_map(|(_, fields)| fields.iter().map(field_align))
150            .collect_vec();
151        let tag_size = tag_ty.as_ref().map(SizeExpr::size_of);
152        let tag_align = tag_ty.as_ref().map(SizeExpr::align_of);
153
154        let after_tag = tag_size.clone().map(|tag_size| match repr.repr_algo {
155            // `repr(C)`: the fields of all variants form a union placed after the
156            // tag `(tag, union { fields.. })`, so all first fields are at the offset of that union.
157            ReprAlgorithm::C => OffsetGuarantee::AtOffset(SizeExpr::align_to(
158                tag_size,
159                SizeExpr::max_align(field_aligns.clone()),
160            )),
161            // `repr(int)`: each variant is its own struct `(tag, fields..)`, so
162            // the first field is aligned to itself.
163            ReprAlgorithm::Rust => OffsetGuarantee::ReprCField(FieldPredecessor::Tag),
164        });
165
166        let align = type_align(tag_align.into_iter().chain(field_aligns).collect());
167        let size = SizeExpr::max_size(tag_size.into_iter().chain(variant_ends).collect());
168        let size = SizeExpr::align_to(size, align.clone());
169        let offsets = variants
170            .iter()
171            .map(|(_, fields)| {
172                (0..fields.len())
173                    .map(|f| match (f, &after_tag) {
174                        (0, None) => OffsetGuarantee::AtOffset(SizeExpr::from_usize(0)),
175                        (0, Some(after_tag)) => after_tag.clone(),
176                        (f, _) => OffsetGuarantee::ReprCField(FieldPredecessor::Field(
177                            FieldId::from_usize(f - 1),
178                        )),
179                    })
180                    .collect()
181            })
182            .collect();
183        return Some(Guarantees {
184            size,
185            align,
186            offsets,
187        });
188    }
189
190    // `repr(Rust)` only guarantees that the fields are aligned and don't overlap, and that the
191    // alignment is at least that of the fields. The size is at least the end of every field.
192    // <https://doc.rust-lang.org/reference/type-layout.html#r-layout.repr.rust.layout>
193    let fields = variants.iter().flat_map(|(_, fields)| fields);
194    let align = type_align(fields.map(field_align).collect());
195    let field_ends = variants.iter().flat_map(|(variant, fields)| {
196        fields.iter().enumerate().map(move |(f, ty)| {
197            let offset = SizeExpr::offset_of(decl.self_ref(), *variant, FieldId::from_usize(f));
198            SizeExprKind::Plus(offset, SizeExpr::size_of(ty)).into_expr()
199        })
200    });
201    let size = SizeExpr::max_size(field_ends.collect());
202    let offsets = variants
203        .iter()
204        .map(|(_, fields)| {
205            fields
206                .iter()
207                .map(|ty| OffsetGuarantee::GuaranteedAlignment(field_align(ty)))
208                .collect()
209        })
210        .collect();
211    Some(Guarantees {
212        size: SizeExpr::at_least(SizeExpr::align_to(size, align.clone())),
213        align: SizeExpr::at_least(align),
214        offsets,
215    })
216}
217
218impl TransformPass for Transform {
219    fn should_run(&self, options: &TranslateOptions) -> bool {
220        !options.no_compute_layout_guarantees
221    }
222
223    fn transform_ctx(&self, ctx: &mut TransformCtx) {
224        let target = ctx
225            .translated
226            .target_information
227            .keys()
228            .exactly_one()
229            .expect("layout guarantees expect exactly one target")
230            .clone();
231
232        ctx.for_each_type_decl(|ctx, decl| {
233            let Some(guarantees) = compute_guarantees(&ctx.translated, &target, decl) else {
234                return;
235            };
236
237            let Some(layout) = decl.layout.get_mut(&target) else {
238                return;
239            };
240
241            // Normalize Inhabited predicates
242            layout.inhabited = layout.inhabited.clone().normalize(&ctx.translated, None);
243            for layout in layout.variant_layouts.iter_mut().flatten() {
244                layout.inhabited = layout.inhabited.clone().normalize(&ctx.translated, None);
245            }
246
247            layout.size.guarantee = Some(guarantees.size.normalize(None, None, false));
248            layout.align.guarantee = Some(guarantees.align.normalize(None, None, false));
249            for (variant, offsets) in layout.variant_layouts.iter_mut().zip(guarantees.offsets) {
250                if let Some(variant) = variant {
251                    for (offset, guarantee) in variant.field_offsets.iter_mut().zip(offsets) {
252                        offset.guarantee = Some(guarantee);
253                    }
254                }
255            }
256        });
257    }
258}
charon_lib/transform/add_missing_info/compute_layout_guarantees.rs

charon_lib/transform/add_missing_info/
compute_layout_guarantees.rs
