Skip to main content

charon_lib/transform/normalize/
partial_monomorphization.rs

1//! This module implements partial monomorphization, which allows specializing generic items on
2//! some specific instanciation patterns. This is used by Aeneas to avoid nested mutable borrows:
3//! we transform `Iter<'a, &'b mut T>` to `{Iter::<_, &mut U>}<'a, 'b, T>`, where
4//! ```ignore
5//! struct {Iter::<'a, &'b mut U>}<'a, 'b, U> {
6//!   // the field of `Iter` but instantiated with `T -> &'b mut U`.
7//! }
8//! ```
9//!
10//! Note: We may need to partial-mono the same item multiple times: `Foo::<&mut A, B>`, `Foo::<A,
11//! &mut B>`. Note also that partial-mono is infectious: `Foo<Bar<&mut A>>` generates `Bar::<&mut
12//! A>` then `Foo::<Bar::<&mut A>>``.
13use std::collections::{HashMap, HashSet, VecDeque};
14use std::mem;
15
16use derive_generic_visitor::Visitor;
17
18use crate::ast::visitor::{VisitWithBinderDepth, VisitorWithBinderDepth};
19use crate::formatter::IntoFormatter;
20use crate::options::MonomorphizeMut;
21use crate::pretty::FmtWithCtx;
22use crate::register_error;
23use crate::transform::ctx::TransformPass;
24use crate::{transform::TransformCtx, ullbc_ast::*};
25
26type MutabilityShape = Binder<GenericArgs>;
27
28/// See the docs of `MutabilityShapeBuilder::compute_shape`.
29#[derive(Visitor)]
30struct MutabilityShapeBuilder<'pm, 'ctx> {
31    pm: &'pm PartialMonomorphizer<'ctx>,
32    /// The parameters that will constitute the final binder.
33    params: GenericParams,
34    /// The arguments to pass to the final binder to recover the input arguments.
35    extracted: GenericArgs,
36    /// Current depth under which we're visiting.
37    binder_depth: DeBruijnId,
38}
39
40impl<'pm, 'ctx> MutabilityShapeBuilder<'pm, 'ctx> {
41    /// Compute the mutability "shape" of a set of generic arguments by factoring out the minimal
42    /// amount of information that still allows reconstructing the original arguments while keeping the
43    /// "shape arguments" free of mutable borrows.
44    ///
45    /// For example, for input:
46    ///   <u32, &'a mut &'b A, Option::<&'a mut bool>>
47    /// we want to build:
48    ///   binder<'a, 'b, A, B, C> <A, &'a mut B, Option::<&'b mut C>>
49    /// from which we can recover the original arguments by instantiating it with:
50    ///   <'a, 'a, u32, &'b A, bool>
51    ///
52    /// Formally, given `let (shape, shape_args) = get_mutability_shape(args);`, we have the following:
53    /// - `shape.substitute(shape_args) == args`;
54    /// - `shape_args` contains no infected types;
55    /// - `shape` is as shallow as possible (i.e. takes just enough to get all the infected types
56    ///   and not more).
57    ///
58    /// Note: the input arguments are assumed to have been already partially monomorphized, in the
59    /// sense that we won't recurse inside ADT args because we assume any ADT applied to infected
60    /// args to have been replaced with a fresh infected ADT.
61    fn compute_shape(
62        pm: &'pm PartialMonomorphizer<'ctx>,
63        target_params: &GenericParams,
64        args: &GenericArgs,
65    ) -> (MutabilityShape, GenericArgs) {
66        // We start with the implicit parameters from the original item. We'll need to substitute
67        // them once we've figured out the mapping of explicit parameters, but we'll also be adding
68        // new trait clauses potentially so we can't leave the vector empty (the ids would be
69        // wrong).
70        let mut shape_contents = args.clone();
71        let mut builder = Self {
72            pm,
73            params: GenericParams {
74                regions: IndexVec::new(),
75                types: IndexVec::new(),
76                const_generics: IndexVec::new(),
77                ..target_params.clone()
78            },
79            extracted: GenericArgs {
80                regions: IndexVec::new(),
81                types: IndexVec::new(),
82                const_generics: IndexVec::new(),
83                trait_refs: mem::take(&mut shape_contents.trait_refs),
84            },
85            binder_depth: DeBruijnId::zero(),
86        };
87
88        // Traverse the generics and replace any non-infected type, region or const generic with a
89        // fresh variable.
90        let _ = VisitWithBinderDepth::new(&mut builder).visit(&mut shape_contents);
91
92        let shape_params = {
93            let mut shape_params = builder.params;
94            // Now the explicit params in `shape_params` are correct, and the implicit params are a mix
95            // of the old params and new trait clauses. The old params may refer to the old explicit
96            // params which is wrong and must be fixed up.
97            shape_params.trait_clauses = shape_params.trait_clauses.map_indexed(|i, x| {
98                if i.index() < target_params.trait_clauses.len() {
99                    x.substitute_explicits(&shape_contents)
100                } else {
101                    x
102                }
103            });
104            shape_params.trait_type_constraints =
105                shape_params.trait_type_constraints.map_indexed(|i, x| {
106                    if i.index() < target_params.trait_type_constraints.len() {
107                        x.substitute_explicits(&shape_contents)
108                    } else {
109                        x
110                    }
111                });
112            shape_params.outlives = shape_params
113                .outlives
114                .into_iter()
115                .enumerate()
116                .map(|(i, x)| {
117                    if i < target_params.outlives.len() {
118                        x.substitute_explicits(&shape_contents)
119                    } else {
120                        x
121                    }
122                })
123                .collect();
124            shape_params
125        };
126
127        // The first half of the trait params correspond to the original item clauses so we can
128        // pass them unmodified.
129        shape_contents.trait_refs = shape_params.identity_args().trait_refs;
130        shape_contents
131            .trait_refs
132            .truncate(target_params.trait_clauses.len());
133
134        let shape_args = builder.extracted;
135        let shape = Binder::new(BinderKind::Other, shape_params, shape_contents);
136        (shape, shape_args)
137    }
138
139    /// Replace this value with a fresh variable, and record that we did so.
140    fn replace_with_fresh_var<Id>(
141        &mut self,
142        val: &mut Id::Arg,
143        mk_param: impl FnOnce(Id) -> Id::Param,
144        mk_value: impl FnOnce(DeBruijnVar<Id>) -> Id::Arg,
145    ) where
146        Id: TypeLevelVar,
147        Id::Arg: TyVisitable + Clone,
148    {
149        let Some(shifted_val) = val.clone().move_from_under_binders(self.binder_depth) else {
150            // Give up on this value.
151            return;
152        };
153        // Record the mapping in the output `GenericArgs`.
154        Id::get_arg_vec_mut(&mut self.extracted).push(shifted_val);
155        // Put a fresh param in place of `val`.
156        let id = Id::get_param_vec_mut(&mut self.params).push_with(mk_param);
157        *val = mk_value(DeBruijnVar::bound(self.binder_depth, id));
158    }
159}
160
161impl<'pm, 'ctx> VisitorWithBinderDepth for MutabilityShapeBuilder<'pm, 'ctx> {
162    fn binder_depth_mut(&mut self) -> &mut DeBruijnId {
163        &mut self.binder_depth
164    }
165}
166
167impl<'pm, 'ctx> VisitAstMut for MutabilityShapeBuilder<'pm, 'ctx> {
168    fn visit<T: AstVisitable>(&mut self, x: &mut T) -> ControlFlow<Self::Break> {
169        VisitWithBinderDepth::new(self).visit(x)
170    }
171
172    fn enter_ty(&mut self, ty: &mut Ty) {
173        if !self.pm.is_infected(ty) {
174            self.replace_with_fresh_var(
175                ty,
176                |id| TypeParam::new(id, format!("T{id}"), Variance::Unknown),
177                |v| v.into(),
178            );
179        }
180    }
181    fn exit_ty_kind(&mut self, kind: &mut TyKind) {
182        if let TyKind::Adt(TypeDeclRef { id, generics, .. }) = kind {
183            // Since the type was not replaced with a type var, it's an infected type. We've
184            // traversed it so we have its final explicit arguments. Now we need to satisfy its
185            // predicates. For that we add all its predicates to the new item, and pass those new
186            // trait clauses to it.
187            let Some(target_params) = self.pm.generic_params.get(&(*id).into()) else {
188                return;
189            };
190            let Some(shifted_generics) =
191                generics.clone().move_from_under_binders(self.binder_depth)
192            else {
193                // Give up on this value.
194                return;
195            };
196
197            // Add the target predicates (properly substituted) to the new item params.
198            let num_clauses_before_merge = self.params.trait_clauses.len();
199            self.params.merge_predicates_from(
200                target_params
201                    .clone()
202                    .substitute_explicits(&shifted_generics),
203            );
204
205            // Record the trait arguments in the output `GenericArgs`.
206            self.extracted
207                .trait_refs
208                .extend(shifted_generics.trait_refs);
209
210            // Replace each trait ref with a clause var.
211            for (target_clause_id, tref) in generics.trait_refs.iter_mut_enumerated() {
212                let clause_id = target_clause_id + num_clauses_before_merge;
213                *tref =
214                    self.params.trait_clauses[clause_id].identity_tref_at_depth(self.binder_depth);
215            }
216        }
217    }
218    fn enter_region(&mut self, r: &mut Region) {
219        self.replace_with_fresh_var(
220            r,
221            |id| RegionParam::new(id, None, Variance::Unknown),
222            |v| v.into(),
223        );
224    }
225    // TODO: we're missing type info for this
226    // fn enter_const_generic(&mut self, cg: &mut ConstGeneric) {
227    //     self.replace_with_fresh_var(cg, |id| {
228    //         ConstGenericParam::new(id, format!("N{id}"), cg.ty().clone())
229    //     });
230    // }
231    fn visit_trait_ref(&mut self, _tref: &mut TraitRef) -> ControlFlow<Self::Break> {
232        // We don't touch trait refs or we'd risk adding duplicated extra params. Instead, we fix
233        // them up in `exit_ty_kind` and `compute_shape`.
234        ControlFlow::Continue(())
235    }
236
237    fn visit_constant_expr(
238        &mut self,
239        _: &mut ConstantExpr,
240    ) -> ::std::ops::ControlFlow<Self::Break> {
241        ControlFlow::Continue(())
242    }
243}
244
245#[derive(Visitor)]
246struct PartialMonomorphizer<'a> {
247    ctx: &'a mut TransformCtx,
248    /// Tracks the closest span to emit useful errors.
249    span: Span,
250    /// Whether we partially-monomorphize type declarations.
251    specialize_adts: bool,
252    /// Types that contain mutable references.
253    infected_types: HashSet<TypeDeclId>,
254    /// Map of generic params for each item. We can't use `ctx.translated` because while iterating
255    /// over items the current item isn't available anymore, which would break recursive types.
256    /// This also makes it possible to record the generics of our to-be-added items without adding
257    /// them.
258    generic_params: HashMap<ItemId, GenericParams>,
259    /// Map of partial monomorphizations. The source item applied with the generic params gives the
260    /// target item. The resulting partially-monomorphized item will have the binder params as
261    /// generic params.
262    partial_mono_shapes: SeqHashMap<(ItemId, MutabilityShape), ItemId>,
263    /// Reverse of `partial_mono_shapes`.
264    reverse_shape_map: HashMap<ItemId, (ItemId, MutabilityShape)>,
265    /// Items that need to be processed.
266    to_process: VecDeque<ItemId>,
267}
268
269impl<'a> PartialMonomorphizer<'a> {
270    pub fn new(ctx: &'a mut TransformCtx, specialize_adts: bool) -> Self {
271        // Compute the types that contain `&mut` (even indirectly). We actually can ignore
272        // `&'static mut`, so we simply rely on our "lifetime mutability" computation.
273        let infected_types: HashSet<_> = ctx
274            .translated
275            .type_decls
276            .iter()
277            .filter(|tdecl| {
278                tdecl
279                    .generics
280                    .regions
281                    .iter()
282                    .any(|r| r.mutability.is_mutable())
283            })
284            .map(|tdecl| tdecl.def_id)
285            .collect();
286
287        // Record the generic params of all items.
288        let generic_params: HashMap<ItemId, GenericParams> = ctx
289            .translated
290            .all_items()
291            .map(|item| (item.id(), item.generic_params().clone()))
292            .collect();
293
294        // Enqueue all items to be processed.
295        let to_process = ctx.translated.all_ids().collect();
296        PartialMonomorphizer {
297            ctx,
298            span: Span::dummy(),
299            specialize_adts,
300            infected_types,
301            generic_params,
302            to_process,
303            partial_mono_shapes: SeqHashMap::default(),
304            reverse_shape_map: Default::default(),
305        }
306    }
307
308    /// Whether this type is or contains a `&mut`. This assumes that we've already visited this
309    /// type and partially monomorphized any ADT references.
310    fn is_infected(&self, ty: &Ty) -> bool {
311        match ty.kind() {
312            TyKind::Ref(_, _, RefKind::Mut) => true,
313            TyKind::Ref(_, ty, _)
314            | TyKind::RawPtr(ty, _)
315            | TyKind::Array(ty, ..)
316            | TyKind::Pattern(ty, _)
317            | TyKind::Slice(ty, _) => self.is_infected(ty),
318            TyKind::Adt(tref) => {
319                let ty_infected = self.infected_types.contains(&tref.id);
320                let args_infected = if self.specialize_adts {
321                    // Since we make sure to only call the method on a processed type, any type
322                    // with infected arguments would have been replaced with a fresh instantiated
323                    // (and infected type). Hence we don't need to check the arguments here, only
324                    // the type id.
325                    false
326                } else {
327                    tref.generics.types.iter().any(|ty| self.is_infected(ty))
328                };
329                ty_infected || args_infected
330            }
331            // A function pointer/item by itself doesn't carry any mutable reference, even if it
332            // uses some in its signature. Compare with closures: a closure without captures
333            // doesn't trigger partial mono regardless of its signature.
334            TyKind::FnDef(..) | TyKind::FnPtr(..) => false,
335            TyKind::DynTrait(_) => {
336                register_error!(
337                    self.ctx,
338                    self.span,
339                    "`dyn Trait` is unsupported with `--monomorphize-mut`"
340                );
341                false
342            }
343            TyKind::TypeVar(..)
344            | TyKind::Scalar(..)
345            | TyKind::Never
346            | TyKind::TraitType(..)
347            | TyKind::PtrMetadata(..)
348            | TyKind::Error(_) => false,
349        }
350    }
351
352    /// Given that `generics` apply to item `id`, if any of the generics is infected we generate a
353    /// reference to a new item obtained by partially instantiating item `id`. (That new item isn't
354    /// added immediately but is added to the `to_process` queue to be created later).
355    fn process_generics(&mut self, id: ItemId, generics: &GenericArgs) -> Option<DeclRef<ItemId>> {
356        if !generics.types.iter().any(|ty| self.is_infected(ty)) {
357            return None;
358        }
359
360        // If the type is already an instantiation, transform this reference into a reference to
361        // the original type so we don't instantiate the instantiation.
362        let mut new_generics;
363        let (id, generics) = if let Some(&(base_id, ref shape)) = self.reverse_shape_map.get(&id) {
364            new_generics = shape.clone().apply(generics);
365            let _ = self.visit(&mut new_generics); // New instantiation may require cleanup.
366            (base_id, &new_generics)
367        } else {
368            (id, generics)
369        };
370
371        // Split the args between the infected part and the non-infected part.
372        let item_params = self.generic_params.get(&id)?;
373        let (shape, shape_args) =
374            MutabilityShapeBuilder::compute_shape(self, item_params, generics);
375
376        // Create a new type id.
377        let new_params = shape.params.clone();
378        let key: (ItemId, MutabilityShape) = (id, shape);
379        let new_id = *self
380            .partial_mono_shapes
381            .entry(key.clone())
382            .or_insert_with(|| {
383                let new_id = match id {
384                    ItemId::Type(_) => {
385                        let new_id = self.ctx.translated.type_decls.reserve_slot();
386                        self.infected_types.insert(new_id);
387                        new_id.into()
388                    }
389                    ItemId::Fun(_) => self.ctx.translated.fun_decls.reserve_slot().into(),
390                    ItemId::Global(_) => self.ctx.translated.global_decls.reserve_slot().into(),
391                    ItemId::TraitDecl(_) => self.ctx.translated.trait_decls.reserve_slot().into(),
392                    ItemId::TraitImpl(_) => self.ctx.translated.trait_impls.reserve_slot().into(),
393                };
394                self.generic_params.insert(new_id, new_params);
395                self.reverse_shape_map.insert(new_id, key);
396                self.to_process.push_back(new_id);
397                new_id
398            });
399
400        let fmt_ctx = self.ctx.into_fmt();
401        trace!(
402            "processing {}{}\n output: {}{}",
403            id.with_ctx(&fmt_ctx),
404            generics.with_ctx(&fmt_ctx),
405            new_id.with_ctx(&fmt_ctx),
406            shape_args.with_ctx(&fmt_ctx),
407        );
408        Some(DeclRef {
409            id: new_id,
410            generics: Box::new(shape_args),
411            trait_ref: None,
412        })
413    }
414
415    /// Traverse the item, replacing any type instantiations we don't want with references to
416    /// soon-to-be-created partially-monomorphized types. This does not access the items in
417    /// `self.translated`, which may be missing since we took `item` out for processing.
418    pub fn process_item(&mut self, item: &mut ItemRefMut<'_>) {
419        let _ = item.drive_mut(self);
420    }
421
422    /// Creates the item corresponding to this id by instantiating the item it is based on.
423    ///
424    /// This accesses the items in `self.translated`, which must therefore all be there.
425    /// That's why items are created outside of `process_item`.
426    pub fn create_pending_instantiation(&mut self, new_id: ItemId) -> ItemByVal {
427        let (orig_id, shape) = &self.reverse_shape_map[&new_id];
428        let mut decl = self
429            .ctx
430            .translated
431            .get_item(*orig_id)
432            .unwrap()
433            .to_owned()
434            .substitute_with_self(&shape.skip_binder, &TraitRefKind::SelfId);
435
436        let mut decl_mut = decl.as_mut();
437        decl_mut.set_id(new_id);
438        *decl_mut.generic_params() = shape.params.clone();
439
440        let name_ref = &mut decl_mut.item_meta().name;
441        *name_ref = mem::take::<crate::ast::Name>(name_ref).instantiate(shape.clone());
442        self.ctx
443            .translated
444            .item_names
445            .insert(new_id, decl.as_ref().item_meta().name.clone());
446        if let (ItemId::TraitDecl(orig_trait_id), ItemId::TraitDecl(new_trait_id)) =
447            (*orig_id, new_id)
448        {
449            let names = self.ctx.translated.assoc_item_names[orig_trait_id].clone();
450            self.ctx
451                .translated
452                .assoc_item_names
453                .insert(new_trait_id, names);
454        }
455
456        decl
457    }
458}
459
460impl VisitorWithSpan for PartialMonomorphizer<'_> {
461    fn current_span(&mut self) -> &mut Span {
462        &mut self.span
463    }
464}
465impl VisitAstMut for PartialMonomorphizer<'_> {
466    fn visit<T: AstVisitable>(&mut self, x: &mut T) -> ControlFlow<Self::Break> {
467        // Track a useful enclosing span, for error messages.
468        VisitWithSpan::new(self).visit(x)
469    }
470
471    fn exit_type_decl_ref(&mut self, x: &mut TypeDeclRef) {
472        if x.is_tuple() && self.ctx.options.no_gen_tuple_structs {
473            return;
474        }
475        if self.specialize_adts
476            && let Some(new_decl_ref) = self.process_generics(x.id.into(), &x.generics)
477        {
478            x.id = new_decl_ref.id.try_into().unwrap();
479            x.generics = new_decl_ref.generics;
480        }
481    }
482    fn exit_fn_ptr(&mut self, x: &mut FnPtr) {
483        // TODO: methods. any `Trait::method<&mut A>` requires monomorphizing all the instances of
484        // that method just in case :>>>
485        if let FnPtrKind::Fun(id) = *x.kind
486            && let Some(new_decl_ref) = self.process_generics(id.into(), &x.generics)
487        {
488            *x = new_decl_ref.try_into().unwrap()
489        }
490    }
491    fn exit_fun_decl_ref(&mut self, x: &mut FunDeclRef) {
492        if let Some(new_decl_ref) = self.process_generics(x.id.into(), &x.generics) {
493            *x = new_decl_ref.try_into().unwrap()
494        }
495    }
496    fn exit_global_decl_ref(&mut self, x: &mut GlobalDeclRef) {
497        if let Some(new_decl_ref) = self.process_generics(x.id.into(), &x.generics) {
498            *x = new_decl_ref.try_into().unwrap()
499        }
500    }
501    fn exit_trait_decl_ref(&mut self, x: &mut TraitDeclRef) {
502        if let Some(new_decl_ref) = self.process_generics(x.id.into(), &x.generics) {
503            *x = new_decl_ref.try_into().unwrap()
504        }
505    }
506    fn exit_trait_impl_ref(&mut self, x: &mut TraitImplRef) {
507        if let Some(new_decl_ref) = self.process_generics(x.id.into(), &x.generics) {
508            *x = new_decl_ref.try_into().unwrap()
509        }
510    }
511}
512
513pub struct Transform;
514impl TransformPass for Transform {
515    fn transform_ctx(&self, ctx: &mut TransformCtx) {
516        let Some(include_types) = ctx.options.monomorphize_mut else {
517            return;
518        };
519        // TODO: test name matcher, also with methods
520        let mut visitor =
521            PartialMonomorphizer::new(ctx, matches!(include_types, MonomorphizeMut::All));
522        while let Some(id) = visitor.to_process.pop_front() {
523            // Get the item corresponding to this id, either by creating it or by getting an
524            // existing one.
525            let mut decl = if visitor.reverse_shape_map.contains_key(&id) {
526                // Create the required item by instantiating the item it's based on.
527                visitor.create_pending_instantiation(id)
528            } else {
529                // Take the item out so we can modify it. Warning: don't look up other items in the
530                // meantime as this would break in recursive cases.
531                match visitor.ctx.translated.remove_item_temporarily(id) {
532                    Some(decl) => decl,
533                    None => continue,
534                }
535            };
536            // Visit the item, replacing type instantiations with references to soon-to-be-created
537            // partially-monomorphized types.
538            visitor.process_item(&mut decl.as_mut());
539            // Put the item back.
540            visitor.ctx.translated.put_item_back(id, decl);
541        }
542    }
543}