Skip to main content

charon_lib/transform/resugar/
reconstruct_matches.rs

1//! The way to match on enums in MIR is in two steps: first read the discriminant, then switch on
2//! the resulting integer. This pass records the enum place as the switch scrutinee and replaces
3//! the integer cases with symbolic enum discriminants.
4use std::{
5    collections::{HashMap, HashSet},
6    mem,
7};
8
9use crate::formatter::IntoFormatter;
10use crate::name_matcher::NamePattern;
11use crate::pretty::FmtWithCtx;
12use crate::transform::TransformCtx;
13use crate::transform::ctx::UllbcPass;
14use crate::ullbc_ast::*;
15use crate::{errors::register_error, transform::CowBox};
16
17pub struct Transform {
18    discriminant_intrinsics: HashSet<FunDeclId>,
19}
20
21impl Transform {
22    fn replace_mem_discriminant_call(&self, block: &mut BlockData) {
23        if let TerminatorKind::Call {
24            call, dest, target, ..
25        } = &block.terminator.kind
26            && let FnOperand::Regular(fn_ptr) = &call.func
27            && let FnPtrKind::Fun(fun_id) = fn_ptr.kind.as_ref()
28            && self.discriminant_intrinsics.contains(fun_id)
29            && let [Operand::Move(p)] = call.args.as_slice()
30            && let TyKind::Ref(_, sub_ty, _) = p.ty().kind()
31        {
32            let dest = dest.clone();
33            let p = p.clone().project(ProjectionElem::Deref, sub_ty.clone());
34            let target = *target;
35            let mut statement = Statement::new(
36                block.terminator.span,
37                StatementKind::Assign(dest, Rvalue::Discriminant(p)),
38            );
39            statement.comments_before = mem::take(&mut block.terminator.comments_before);
40            block.statements.push(statement);
41            block.terminator.kind = TerminatorKind::Goto { target };
42        }
43    }
44
45    fn reconstruct_match(&self, ctx: &mut TransformCtx, block: &mut BlockData) {
46        let span = block.terminator.span;
47        let TerminatorKind::Switch { data, branches } = &mut block.terminator.kind else {
48            return;
49        };
50        let SwitchScrutinee::Value(Operand::Move(op_p)) = &data.scrutinee else {
51            return;
52        };
53        // If the last statement is a discriminant read.
54        let Some(last_st) = block.statements.last_mut() else {
55            return;
56        };
57        let StatementKind::Assign(dest, Rvalue::Discriminant(p)) = &last_st.kind else {
58            return;
59        };
60        assert!(dest.is_local()); // The destination should be a variable.
61        if op_p != dest {
62            return;
63        }
64        let scrut_ty = p.ty().clone();
65
66        // Merge the two statements.
67        data.scrutinee = SwitchScrutinee::Discriminant(p.clone());
68        last_st.kind = StatementKind::Nop;
69
70        // Lookup the type of the scrutinee.
71        let TyKind::Adt(tdecl_ref) = scrut_ty.kind() else {
72            return;
73        };
74        let tdecl_ref = tdecl_ref.clone();
75        let adt_id = tdecl_ref.id;
76        let tkind = ctx.translated.type_decls.get(adt_id).map(|x| &x.kind);
77        let Some(TypeDeclKind::Enum(variants)) = tkind else {
78            match tkind {
79                // This can happen if the type was declared as invisible or opaque.
80                None | Some(TypeDeclKind::Opaque) => {
81                    let name = ctx.translated.item_name(adt_id);
82                    register_error!(
83                        ctx,
84                        span,
85                        "reading the discriminant of an opaque enum. \
86                        Add `--include {}` to the `charon` arguments \
87                        to translate this enum.",
88                        name.with_ctx(&ctx.into_fmt())
89                    );
90                }
91                // Don't double-error.
92                Some(TypeDeclKind::Error(..)) => {}
93                Some(_) => {
94                    register_error!(ctx, span, "reading the discriminant of a non-enum type");
95                }
96            }
97            return;
98        };
99
100        // Map from discriminants to variant indices. The discriminant can be of any integer type.
101        let discr_to_id: HashMap<IntegerValue, VariantId> = variants
102            .iter_enumerated()
103            .map(|(id, variant)| (variant.discriminant, id))
104            .collect();
105
106        // Replace the branch values with discriminant constants.
107        let mut covered_discriminants: HashSet<IntegerValue> = HashSet::default();
108        for (value, _) in &mut data.branches {
109            if let ConstantExprKind::Integer(discr) = value.kind()
110                && let Some(variant_id) = discr_to_id.get(discr).copied()
111            {
112                covered_discriminants.insert(*discr);
113                *value = ConstantExpr::new(
114                    ConstantExprKind::Discriminant(tdecl_ref.clone(), variant_id),
115                    value.ty().clone(),
116                );
117            } else {
118                register_error!(
119                    ctx,
120                    block.terminator.span,
121                    "Found incorrect discriminant {value} for enum {adt_id}"
122                );
123            }
124        }
125
126        if covered_discriminants.len() == discr_to_id.len() {
127            // Remove the fallback if the explicit cases cover every variant.
128            let fallback = data.fallback.take();
129            // Remove the fallback branch entirely if unused.
130            if let Some(fallback) = fallback
131                && !data.branches.iter().any(|(_, branch)| *branch == fallback)
132            {
133                branches.pop();
134            }
135        }
136    }
137}
138
139const DISCRIMINANT_INTRINSIC: &str = "core::intrinsics::discriminant_value";
140
141impl Transform {
142    pub fn new(ctx: &mut TransformCtx) -> CowBox<dyn UllbcPass> {
143        let pat = NamePattern::parse(DISCRIMINANT_INTRINSIC).unwrap();
144        // There can be many if we're in mono mode.
145        let discriminant_intrinsics = ctx
146            .translated
147            .item_names
148            .iter()
149            .filter(|(_, name)| pat.matches(&ctx.translated, name))
150            .filter_map(|(id, _)| id.as_fun())
151            .copied()
152            .collect();
153        CowBox::Owned(Box::new(Transform {
154            discriminant_intrinsics,
155        }))
156    }
157}
158
159impl UllbcPass for Transform {
160    fn should_run(&self, options: &crate::options::TranslateOptions) -> bool {
161        options.reconstruct_matches
162    }
163
164    fn transform_body(&self, ctx: &mut TransformCtx, body: &mut ExprBody) {
165        for block in &mut body.body {
166            self.reconstruct_match(ctx, block);
167            self.replace_mem_discriminant_call(block);
168        }
169    }
170}