charon_lib/transform/normalize/
partial_monomorphization.rs1use 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#[derive(Visitor)]
30struct MutabilityShapeBuilder<'pm, 'ctx> {
31 pm: &'pm PartialMonomorphizer<'ctx>,
32 params: GenericParams,
34 extracted: GenericArgs,
36 binder_depth: DeBruijnId,
38}
39
40impl<'pm, 'ctx> MutabilityShapeBuilder<'pm, 'ctx> {
41 fn compute_shape(
62 pm: &'pm PartialMonomorphizer<'ctx>,
63 target_params: &GenericParams,
64 args: &GenericArgs,
65 ) -> (MutabilityShape, GenericArgs) {
66 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 let _ = VisitWithBinderDepth::new(&mut builder).visit(&mut shape_contents);
91
92 let shape_params = {
93 let mut shape_params = builder.params;
94 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 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 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 return;
152 };
153 Id::get_arg_vec_mut(&mut self.extracted).push(shifted_val);
155 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 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 return;
195 };
196
197 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 self.extracted
207 .trait_refs
208 .extend(shifted_generics.trait_refs);
209
210 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 fn visit_trait_ref(&mut self, _tref: &mut TraitRef) -> ControlFlow<Self::Break> {
232 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 span: Span,
250 specialize_adts: bool,
252 infected_types: HashSet<TypeDeclId>,
254 generic_params: HashMap<ItemId, GenericParams>,
259 partial_mono_shapes: SeqHashMap<(ItemId, MutabilityShape), ItemId>,
263 reverse_shape_map: HashMap<ItemId, (ItemId, MutabilityShape)>,
265 to_process: VecDeque<ItemId>,
267}
268
269impl<'a> PartialMonomorphizer<'a> {
270 pub fn new(ctx: &'a mut TransformCtx, specialize_adts: bool) -> Self {
271 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 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 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 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 false
326 } else {
327 tref.generics.types.iter().any(|ty| self.is_infected(ty))
328 };
329 ty_infected || args_infected
330 }
331 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 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 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); (base_id, &new_generics)
367 } else {
368 (id, generics)
369 };
370
371 let item_params = self.generic_params.get(&id)?;
373 let (shape, shape_args) =
374 MutabilityShapeBuilder::compute_shape(self, item_params, generics);
375
376 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 pub fn process_item(&mut self, item: &mut ItemRefMut<'_>) {
419 let _ = item.drive_mut(self);
420 }
421
422 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 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 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 let mut visitor =
521 PartialMonomorphizer::new(ctx, matches!(include_types, MonomorphizeMut::All));
522 while let Some(id) = visitor.to_process.pop_front() {
523 let mut decl = if visitor.reverse_shape_map.contains_key(&id) {
526 visitor.create_pending_instantiation(id)
528 } else {
529 match visitor.ctx.translated.remove_item_temporarily(id) {
532 Some(decl) => decl,
533 None => continue,
534 }
535 };
536 visitor.process_item(&mut decl.as_mut());
539 visitor.ctx.translated.put_item_back(id, decl);
541 }
542 }
543}