charon_lib/transform/add_missing_info/
add_missing_alias_clauses.rs

1//! Rust doesn't require bounds on type aliases to be well-formed. When a type alias mentions
2//! `<T as Trait>::Assoc` without a corresponding `T: Trait` clause, translation leaves an unknown
3//! trait ref. This pass tries to add these missing clauses.
4
5use crate::ast::*;
6use crate::transform::{TransformCtx, ctx::TransformPass};
7use rustc_hash::FxHashMap as HashMap;
8
9#[derive(Visitor)]
10struct ClauseExtractor<'a> {
11    params: &'a mut GenericParams,
12    span: Span,
13    binder_stack: BindingStack<GenericParams>,
14    extracted_clauses: HashMap<PolyTraitDeclRef, TraitClauseId>,
15}
16
17impl<'a> ClauseExtractor<'a> {
18    fn new(params: &'a mut GenericParams, span: Span) -> Self {
19        Self {
20            binder_stack: BindingStack::new(params.clone()),
21            params,
22            span,
23            extracted_clauses: HashMap::default(),
24        }
25    }
26
27    /// Move a trait ref out of the binders to make it a trait clause. Collects all the region
28    /// binders on the way to here into a single binder to make a HRTB.
29    fn extract_trait_clause(&self, trait_: TraitDeclRef) -> Option<(PolyTraitDeclRef, RegionArgs)> {
30        let mut trait_ = RegionBinder::empty(trait_);
31        // Iterate over the binders on the way to this trait ref, skipping the first binder (the
32        // item binder).
33        let mut scope_regions = Vec::new();
34        for (dbid, params) in self.binder_stack.iter_enumerated().rev().skip(1) {
35            for (old_id, region) in params.regions.iter_enumerated() {
36                let new_id = trait_.regions.push_with(|index| {
37                    let mut region = region.clone();
38                    region.index = index;
39                    region
40                });
41                scope_regions.push((dbid, old_id, new_id));
42            }
43        }
44
45        let region_args = RegionArgs::new(
46            scope_regions
47                .iter()
48                .map(|(dbid, id, _)| Region::Var(DeBruijnVar::bound(*dbid, *id)))
49                .collect(),
50        );
51
52        if !scope_regions.is_empty() {
53            // Make all the region variables point at the outer binder.
54            #[derive(Visitor)]
55            struct MoveRegionsToHrtb {
56                binder_depth: DeBruijnId,
57                scope_regions: Vec<(DeBruijnId, RegionId, RegionId)>,
58            }
59
60            impl VisitorWithBinderDepth for MoveRegionsToHrtb {
61                fn binder_depth_mut(&mut self) -> &mut DeBruijnId {
62                    &mut self.binder_depth
63                }
64            }
65
66            impl VisitAstMut for MoveRegionsToHrtb {
67                fn visit<T: AstVisitable>(&mut self, x: &mut T) -> ControlFlow<Self::Break> {
68                    VisitWithBinderDepth::new(self).visit(x)
69                }
70
71                fn enter_region(&mut self, region: &mut Region) {
72                    let Region::Var(var) = region else {
73                        return;
74                    };
75                    let DeBruijnVar::Bound(dbid, old_id) = *var else {
76                        return;
77                    };
78                    let Some(outer_depth) = dbid.sub(self.binder_depth.incr()) else {
79                        return;
80                    };
81                    let Some((_, _, new_id)) = self
82                        .scope_regions
83                        .iter()
84                        .find(|(dbid, id, _)| *dbid == outer_depth && *id == old_id)
85                    else {
86                        return;
87                    };
88                    *var = DeBruijnVar::bound(self.binder_depth, *new_id);
89                }
90            }
91
92            MoveRegionsToHrtb {
93                binder_depth: DeBruijnId::zero(),
94                scope_regions,
95            }
96            .visit(&mut trait_.skip_binder);
97        }
98
99        let trait_ = trait_.move_from_under_binders(self.binder_stack.depth())?;
100        Some((trait_, region_args))
101    }
102}
103
104impl VisitorWithBinderStack for ClauseExtractor<'_> {
105    fn binder_stack_mut(&mut self) -> &mut BindingStack<GenericParams> {
106        &mut self.binder_stack
107    }
108}
109
110impl VisitAstMut for ClauseExtractor<'_> {
111    fn visit<T: AstVisitable>(&mut self, x: &mut T) -> ControlFlow<Self::Break> {
112        VisitWithBinderStack::new(self).visit(x)
113    }
114
115    fn exit_trait_ref_contents(&mut self, tref: &mut TraitRefContents) {
116        if matches!(tref.kind, TraitRefKind::Unknown(_))
117            && let Some((trait_, region_args)) =
118                self.extract_trait_clause(tref.trait_decl_ref.clone())
119        {
120            let clause_id = if let Some(clause_id) = self.extracted_clauses.get(&trait_) {
121                *clause_id
122            } else {
123                let clause_id = self.params.trait_clauses.push_with(|clause_id| TraitParam {
124                    clause_id,
125                    span: Some(self.span),
126                    origin: PredicateOrigin::WhereClauseOnType,
127                    trait_: trait_.clone(),
128                });
129                self.extracted_clauses.insert(trait_, clause_id);
130                clause_id
131            };
132            tref.kind = TraitRefKind::Clause(
133                DeBruijnVar::bound(self.binder_stack.depth(), clause_id),
134                region_args,
135            );
136        }
137    }
138}
139
140pub struct Transform;
141impl TransformPass for Transform {
142    fn transform_ctx(&self, ctx: &mut TransformCtx) {
143        for tdecl in &mut ctx.translated.type_decls {
144            if matches!(tdecl.kind, TypeDeclKind::Alias(_)) {
145                let mut extractor = ClauseExtractor::new(&mut tdecl.generics, tdecl.item_meta.span);
146                extractor.visit(&mut tdecl.kind);
147                extractor.visit(&mut tdecl.layout);
148            }
149        }
150    }
151}
charon_lib/transform/add_missing_info/add_missing_alias_clauses.rs

charon_lib/transform/add_missing_info/
add_missing_alias_clauses.rs
