Skip to main content

charon_lib/ast/
bodies.rs

1//! The bodies of functions.
2use crate::ast::*;
3use crate::ids::IndexVec;
4use crate::llbc_ast;
5use crate::ullbc_ast;
6use crate::utils::serialize_map_to_array::SeqHashMapToArray;
7use derive_generic_visitor::{Drive, DriveMut, DriveTwo};
8use enum_as_inner::EnumAsInner;
9use serde_state::DeserializeState;
10use serde_state::SerializeState;
11
12pub mod asm;
13pub mod expressions;
14pub mod places;
15pub mod safety;
16pub mod structured;
17pub mod unstructured;
18pub mod values;
19
20pub use asm::*;
21pub use expressions::*;
22pub use places::*;
23pub use safety::*;
24pub use values::*;
25
26/// The body of a function.
27///
28/// A normal function has a body that's either structured or unstructured. These are two equivalent
29/// representations of the same function body, which only differ in how control-flow is
30/// represented. By default bodies are structured; passing `--ullbc` to Charon makes bodies
31/// unstructured.
32///
33/// Besides these, some functions have virtual bodies or no body, see the doc for each variant.
34#[derive(Debug, Clone)]
35#[derive(EnumAsInner)]
36#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
37#[serde_state(state_implements = DedupSerializerState)]
38#[cfg_attr(feature = "charon_on_charon", charon::variants_suffix("Body"))]
39pub enum Body {
40    /// Body represented as a control-flow graph (CFG), i.e. with numbered blocks and jumps/GOTOs
41    /// between them. This is available when passing `--ullbc` to Charon.
42    ///
43    /// This is also the same structure as rustc's MIR, and is in fact a direct translation of it.
44    Unstructured(ullbc_ast::ExprBody),
45    /// Body represented with structured control flow, i.e. with nested `if`/`match`/`loop` blocks.
46    /// This is available when `--ullbc` is not passed to Charon.
47    ///
48    /// This structure is recovered from the unstructured body in the `ullbc_to_llbc` pass.
49    Structured(llbc_ast::ExprBody),
50    /// A façade body that dispatches to one of several per-target function bodies. This is created
51    /// during multi-target merging (using `--target`) to represent functions that have a different
52    /// implementation across targets.
53    TargetDispatch(
54        #[serde(with = "SeqHashMapToArray::<TargetTriple, FunDeclRef>")]
55        SeqHashMap<TargetTriple, FunDeclRef>,
56    ),
57    /// Function declared in an `extern { ... }` block.
58    Extern {
59        /// The foreign symbol name.
60        symbol: String,
61        /// The function that the linker binds this symbol to. Only computed with `--link-extern-fns`.
62        definition: LinkedExtern,
63    },
64    /// Rust intrinsic function. This describes a "built-in" operation that must be handled by the
65    /// codegen backend.
66    Intrinsic {
67        /// The intrinsic name.
68        name: String,
69        /// The argument names, None if not available.
70        arg_names: Vec<Option<String>>,
71        /// A fallback body that backends can use if they don't implement the intrinsic themselves.
72        fallback: Option<FunDeclRef>,
73        /// Whether the fallback body is marked `#[miri::intrinsic_fallback_is_spec]`, in which case
74        /// it exactly describes the behavior of the intrinsic. Otherwise the fallback is only one of
75        /// the valid implementations of the intrinsic, e.g. the fallback may have less UB or less
76        /// non-determinism.
77        fallback_is_spec: bool,
78    },
79    /// A body that the user chose not to translate, based on opacity settings like
80    /// `--include`/`--opaque`.
81    Opaque,
82    /// A body that was not available.
83    ///
84    /// These can occur when using a sysroot that doesn't have MIR for all the standard library
85    /// functions. This is the case of the sysroot that ships with every Rust toolchain, but Charon
86    /// uses a custom-built sysroot that does. So this shouldn't happen unless you're passing
87    /// `--sysroot` to charon.
88    Missing,
89    /// We encountered an error while translating this body.
90    #[serde_state(stateless)]
91    Error(Error),
92}
93
94/// The function that the linker binds an extern function's symbol to.
95#[derive(Debug, Clone)]
96#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
97#[serde_state(state_implements = DedupSerializerState)]
98pub enum LinkedExtern {
99    /// A strong definition, e.g. `#[no_mangle]` or `#[export_name]`.
100    StronglyLinked(FunDeclRef),
101    /// Weak definitions (`#[linkage = "weak"]`), which the linker only binds the symbol to if
102    /// there's no strong definition. If there are several, the linker may pick any of them.
103    WeaklyLinked(Vec<FunDeclRef>),
104    /// Linked to the default allocator through rustc's allocator shim. This needs to be handled
105    /// separately, as the signatures aren't ABI-compatible: the arguments need to be
106    /// transmuted (e.g. `Alignment` -> `usize`).
107    AllocatorShim(FunDeclRef),
108    /// No function of the crate or its dependencies is exported under this symbol.
109    Unlinked,
110}
111
112generate_index_type!(LocalId, "");
113
114/// The local variables of a body.
115#[derive(Debug, Default, Clone)]
116#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
117pub struct Locals {
118    /// The number of local variables used for the input arguments.
119    pub arg_count: usize,
120    /// The local variables.
121    /// We always have, in the following order:
122    /// - the local used for the return value (index 0)
123    /// - the `arg_count` input arguments
124    /// - the remaining locals, used for the intermediate computations
125    pub locals: IndexVec<LocalId, Local>,
126}
127
128/// A variable
129#[derive(Debug, Clone)]
130#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
131pub struct Local {
132    /// Unique index identifying the variable
133    pub index: LocalId,
134    /// Variable name - may be `None` if the variable was introduced by Rust
135    /// through desugaring.
136    pub name: Option<String>,
137    /// Span of the variable declaration.
138    pub span: Span,
139    /// The variable type
140    #[cfg_attr(feature = "charon_on_charon", charon::rename("local_ty"))]
141    pub ty: Ty,
142    /// Whether this local was declared `mut`. Anonymous locals are always mutable.
143    #[cfg_attr(feature = "charon_on_charon", charon::rename("is_mutable"))]
144    pub mutable: bool,
145    /// List of constraints that apply to this local throughout the function body. For example,
146    /// `let x: Self = ...;` produces a `x == Self` constraint.
147    pub borrowck_constraints: Vec<PlaceTypeConstraint>,
148    /// If this local is a drop flag, this is the place whose initialization state it tracks.
149    pub drop_flag_for: Option<Place>,
150}
151
152/// An expression body.
153/// TODO: arg_count should be stored in GFunDecl below. But then,
154///       the print is obfuscated and Aeneas may need some refactoring.
155#[derive(Debug, Clone)]
156#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
157#[cfg_attr(feature = "charon_on_charon", charon::rename("GexprBody"))]
158pub struct GExprBody<T> {
159    pub span: Span,
160    /// The number of regions existentially bound in this body. We introduce fresh such regions
161    /// during translation instead of the erased regions that rustc gives us.
162    pub bound_body_regions: usize,
163    /// The local variables.
164    pub locals: Locals,
165    /// The statements and blocks that compose this body.
166    pub body: T,
167    /// For each line inside the body, we record any whole-line `//` comments found before it. They
168    /// are added to statements in the late `recover_body_comments` pass.
169    #[cfg_attr(feature = "charon_on_charon", charon::opaque)]
170    pub comments: Vec<(u32, Vec<String>)>,
171}
172
173generate_index_type!(BranchId, "Branch");
174
175/// The value inspected by a switch. Must be of integer, bool or char type.
176#[derive(Debug, Clone, PartialEq, Eq)]
177#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
178#[cfg_attr(feature = "charon_on_charon", charon::variants_prefix("Switch"))]
179pub enum SwitchScrutinee {
180    /// Inspect the value produced by an operand.
181    Value(Operand),
182    /// Inspect the discriminant of an enum place.
183    Discriminant(Place),
184}
185
186/// A branching operation.
187#[derive(Debug, Clone, PartialEq, Eq)]
188#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
189pub struct SwitchData {
190    /// The value to branch over.
191    pub scrutinee: SwitchScrutinee,
192    /// Which branch to take for each value of the scrutinee. Several values may point to the same
193    /// branch, and not all values may be accounted for.
194    ///
195    /// If the scrutinee is an operand, the constant expressions are literal values. If the
196    /// scrutinee is a discriminant read, the expressions are of the form
197    /// `ConstantExprKind::Discriminant`.
198    pub branches: Vec<(ConstantExpr, BranchId)>,
199    /// Branch to use if the scrutinee didn't match any of the values above. `None` if the set of
200    /// branch values is known to be exhaustive.
201    pub fallback: Option<BranchId>,
202}
203
204/// A function operand is used in function calls.
205/// It either designates a top-level function, or a place in case
206/// we are using function pointers stored in local variables.
207#[derive(Debug, Clone, PartialEq, Eq)]
208#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
209#[cfg_attr(feature = "charon_on_charon", charon::variants_prefix("FnOp"))]
210pub enum FnOperand {
211    /// Regular case: call to a top-level function, trait method, etc.
212    Regular(FnPtr),
213    /// Call through a function pointer, instantiated with the given regions.
214    Dynamic(Operand, RegionArgs),
215}
216
217#[derive(Debug, Clone, PartialEq, Eq)]
218#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
219pub struct Call {
220    pub func: FnOperand,
221    pub args: Vec<Operand>,
222    pub safety: CallSafety,
223}
224
225/// Whether we statically know something about the safety of this call, that takes
226/// precedence over the safety of the callee's signature.
227#[derive(Debug, Copy, Clone, PartialEq, Eq)]
228#[derive(EnumAsInner)]
229#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
230pub enum CallSafety {
231    /// As safe as the callee's signature.
232    Inherit,
233    /// Safe despite an unsafe signature: desugared drops, and calls to safe `#[target_feature]` functions
234    /// from contexts that enable the required features.
235    Safe,
236    /// Unsafe despite a safe signature: calls to `#[target_feature]` functions from contexts
237    /// that don't enable the required features, and explicit calls to `Drop` methods.
238    Unsafe,
239}
240
241/// Borrow-checking constraint that enforces a relation between the type of the given place and the
242/// provided type.
243#[derive(Debug, Clone, PartialEq, Eq)]
244#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
245pub struct PlaceTypeConstraint {
246    pub place: Place,
247    pub ty: Ty,
248    #[serde_state(stateless)]
249    pub variance: Variance,
250}
251
252/// Statements that only affect borrow-checking. They are no-ops at runtime.
253#[derive(Debug, Clone, PartialEq, Eq)]
254#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
255pub enum BorrowckStatement {
256    /// Acts like a read of the place.
257    FakeRead(Place),
258    /// Apply a constraint to this place at this point in the function. For example, `x =
259    /// Option::<&'static u32>::None;` emits a `tmp := Option::<&'static u32>` constraint.
260    SetType(PlaceTypeConstraint),
261    /// Require an outlives predicate to hold.
262    SetOutlives(OutlivesPred),
263}
264
265/// (U)LLBC is a language with side-effects: a statement may abort in a way that isn't tracked by
266/// control-flow. The three kinds of abort are:
267/// - Panic
268/// - Undefined behavior (caused by an "assume")
269/// - Unwind termination
270#[derive(Debug, Clone, PartialEq, Eq)]
271#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
272#[cfg_attr(feature = "charon_on_charon", charon::variants_prefix("Abort"))]
273pub enum AbortKind {
274    /// A built-in panicking function, or a panic due to a failed built-in check (e.g. for
275    /// out-of-bounds accesses).
276    Panic,
277    /// Undefined behavior in the rust abstract machine.
278    UndefinedBehavior,
279    /// Unwind had to stop for ABI reasons or because cleanup code panicked again.
280    UnwindTerminate(UnwindTerminateReason),
281}
282
283/// Why unwinding had to stop.
284#[derive(Debug, Copy, Clone, PartialEq, Eq)]
285#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
286pub enum UnwindTerminateReason {
287    /// Unwinding out of a function that cannot unwind (e.g. an `extern "C"` function).
288    Abi,
289    /// Cleanup code panicked again.
290    InCleanup,
291}
292
293/// A `Drop` statement/terminator can mean two things, depending on what MIR phase we retrieved
294/// from rustc: it could be a real drop, or it could be a "conditional drop", which is where drop
295/// may happen depending on whether the borrow-checker determines a drop is needed.
296#[derive(Debug, Copy, Clone, PartialEq, Eq)]
297#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
298pub enum DropKind {
299    /// A real drop. This calls `<T as Destruct>::drop_glue(&mut place)` and marks the
300    /// place as moved-out-of. Use `--desugar-drops` to transform all such drops to an actual
301    /// function call.
302    ///
303    /// The `drop_glue` method is added by Charon to the `Destruct` trait to make it possible
304    /// to track drop code in polymorphic code. It contains the same code as the
305    /// `core::ptr::drop_glue<T>` builtin would.
306    ///
307    /// Drop are precise in MIR `elaborated` and `optimized`.
308    Precise,
309    /// A conditional drop, which may or may not end up running drop code depending on the code
310    /// path that led to it. A conditional drop may also become a partial drop (dropping only the
311    /// subplaces that haven't been moved out of), may be conditional on the code path that led to
312    /// it, or become an async drop. The exact semantics are left intentionally unspecified by
313    /// rustc developers. To elaborate such drops into precise drops, pass `--precise-drops` to
314    /// Charon.
315    ///
316    /// A conditional drop may also be passed an unaligned place when dropping fields of packed
317    /// structs. Such a thing is UB for a precise drop.
318    ///
319    /// Drop are conditional in MIR `built` and `promoted`.
320    Conditional,
321}
322
323/// Check the value of an operand and abort if the value is not expected. This is introduced to
324/// avoid a lot of small branches.
325///
326/// We translate MIR asserts (introduced for out-of-bounds accesses or divisions by zero for
327/// instance) to this. We then eliminate them in [crate::transform::resugar::reconstruct_fallible_operations],
328/// because they're implicit in the semantics of our array accesses etc. Finally we introduce new asserts in
329/// [crate::transform::resugar::reconstruct_asserts].
330#[derive(Debug, Clone, PartialEq, Eq)]
331#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
332#[cfg_attr(feature = "charon_on_charon", charon::rename("Assertion"))]
333pub struct Assert {
334    pub cond: Operand,
335    /// The value that the operand should evaluate to for the assert to succeed.
336    pub expected: bool,
337    /// The kind of check performed by this assert. This is only used for error reporting, as the check
338    /// is actually performed by the instructions preceding the assert.
339    pub check_kind: Option<BuiltinAssertKind>,
340    /// The call to a panicking function that happens when the check fails
341    pub call: Box<Call>,
342}
343
344/// The kind of a built-in assertion, which may panic and unwind. These are removed
345/// by `reconstruct_fallible_operations` because they're implicit in the semantics of (U)LLBC.
346/// This kind should only be used for error-reporting purposes, as the check itself
347/// is performed in the instructions preceding the assert.
348#[derive(Debug, Clone, PartialEq, Eq)]
349#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
350pub enum BuiltinAssertKind {
351    BoundsCheck { len: Operand, index: Operand },
352    Overflow(BinOp, Operand, Operand),
353    OverflowNeg(Operand),
354    DivisionByZero(Operand),
355    RemainderByZero(Operand),
356    MisalignedPointerDereference { required: Operand, found: Operand },
357    NullPointerDereference,
358    NullReferenceCreated,
359    InvalidEnumConstruction(Operand),
360    ResumedAfterReturn,
361    ResumedAfterPanic,
362    ResumedAfterDrop,
363}
364
365impl Body {
366    /// Whether there is an actual body with statements etc, as opposed to the body being missing
367    /// for some reason.
368    pub fn has_contents(&self) -> bool {
369        match self {
370            Body::Unstructured(..) | Body::Structured(..) => true,
371            Body::Extern { .. }
372            | Body::Intrinsic { .. }
373            | Body::Opaque
374            | Body::Missing
375            | Body::Error(..)
376            | Body::TargetDispatch(..) => false,
377        }
378    }
379
380    pub fn locals(&self) -> &Locals {
381        match self {
382            Body::Structured(body) => &body.locals,
383            Body::Unstructured(body) => &body.locals,
384            _ => panic!("called `locals` on a missing body"),
385        }
386    }
387}
388
389impl Locals {
390    pub fn new(arg_count: usize) -> Self {
391        Self {
392            arg_count,
393            locals: Default::default(),
394        }
395    }
396
397    /// Creates a new variable and returns a place pointing to it.
398    /// Warning: don't forget to `StorageLive` it before using it.
399    pub fn new_var(&mut self, name: Option<String>, ty: Ty) -> Place {
400        let local_id = self.locals.push_with(|index| Local {
401            index,
402            name,
403            span: Span::dummy(),
404            ty: ty.clone(),
405            mutable: true,
406            borrowck_constraints: Vec::new(),
407            drop_flag_for: None,
408        });
409        Place::new(local_id, ty)
410    }
411
412    /// Gets a place pointing to the corresponding variable.
413    pub fn place_for_var(&self, local_id: LocalId) -> Place {
414        let ty = self.locals[local_id].ty.clone();
415        Place::new(local_id, ty)
416    }
417
418    /// All the locals, including the return local and arguments.
419    pub fn iter(&self) -> impl Iterator<Item = &Local> {
420        self.locals.iter()
421    }
422
423    /// The input argument locals.
424    pub fn arguments(&self) -> impl Iterator<Item = &Local> {
425        self.locals.iter().skip(1).take(self.arg_count)
426    }
427
428    /// The local used for the return value.
429    pub fn return_local(&self) -> &Local {
430        &self.locals[LocalId::ZERO]
431    }
432
433    /// Returns whether this local is the special return local or one of the input argument locals.
434    pub fn is_return_or_arg(&self, lid: LocalId) -> bool {
435        lid.index() <= self.arg_count
436    }
437
438    /// The place where we write the return value.
439    pub fn return_place(&self) -> Place {
440        self.place_for_var(LocalId::ZERO)
441    }
442
443    /// Locals that aren't arguments or return values.
444    pub fn non_argument_locals(&self) -> impl Iterator<Item = (LocalId, &Local)> {
445        self.locals.iter_enumerated().skip(1 + self.arg_count)
446    }
447}
448
449impl SwitchData {
450    /// If this is a switch over a boolean, return its `then` and `else` branches.
451    pub fn as_if(&self) -> Option<(BranchId, BranchId)> {
452        let SwitchScrutinee::Value(scrutinee) = &self.scrutinee else {
453            return None;
454        };
455        if !matches!(scrutinee.ty().kind(), TyKind::Scalar(ScalarTy::Bool)) {
456            return None;
457        }
458
459        let branch_for = |value| {
460            self.branches
461                .iter()
462                .find_map(|(case, branch_id)| match case.kind() {
463                    ConstantExprKind::Bool(case_value) if *case_value == value => Some(*branch_id),
464                    _ => None,
465                })
466                .or(self.fallback)
467        };
468        Some((branch_for(true)?, branch_for(false)?))
469    }
470
471    /// Group the explicit switch values by the branch they select.
472    pub fn group_by_branch(&self) -> IndexVec<BranchId, Vec<ConstantExpr>> {
473        let mut grouped = IndexVec::new();
474        if let Some(branch_id) = self.fallback {
475            grouped.get_or_extend_and_insert(branch_id, Vec::new);
476        }
477        for (value, branch_id) in &self.branches {
478            grouped
479                .get_or_extend_and_insert(*branch_id, Vec::new)
480                .push(value.clone());
481        }
482        grouped
483    }
484}
485
486impl std::ops::Index<LocalId> for Locals {
487    type Output = Local;
488    fn index(&self, local_id: LocalId) -> &Self::Output {
489        &self.locals[local_id]
490    }
491}
492impl std::ops::IndexMut<LocalId> for Locals {
493    fn index_mut(&mut self, local_id: LocalId) -> &mut Self::Output {
494        &mut self.locals[local_id]
495    }
496}