Skip to main content

charon_lib/transform/add_missing_info/
add_implied_outlives.rs

1//! Make explicit the outlives predicates implied by the well-formedness of a type.
2use derive_generic_visitor::*;
3use itertools::Itertools;
4use std::mem;
5
6use crate::ast::*;
7use crate::transform::{TransformCtx, ctx::TransformPass};
8use crate::utils::CycleDetector;
9
10#[derive(Default)]
11struct OutlivesAtBinder {
12    outlives: SeqHashSet<PolyOutlivesPred>,
13    /// The lifetime of the innermost reference we're inside of. When going under a binder, we keep
14    /// it there.
15    ///
16    /// E.g. in `&'a for<'b> fn(&'b u32, &'c u32)`, the `'a` stays on the outer binder, and we use
17    /// that to add `'c: 'a` but we don't add `'b: 'a` since `'b` is not visible from where `'a`
18    /// is.
19    shorter_region: Option<Region>,
20}
21
22impl OutlivesAtBinder {
23    fn finish(self, outlives: &mut Vec<PolyOutlivesPred>) {
24        debug_assert!(self.shorter_region.is_none());
25        let mut predicates: SeqHashSet<_> = mem::take(outlives).into_iter().collect();
26        predicates.extend(self.outlives);
27        outlives.extend(predicates.into_iter().filter(|pred| {
28            let OutlivesPred(longer, shorter) = &pred.skip_binder;
29            longer != shorter && !longer.is_erased() && !shorter.is_erased()
30        }));
31    }
32}
33
34/// Explore a type and accumulate the outlives predicates it implies.
35#[derive(Visitor)]
36struct OutlivesGatherer<'a> {
37    type_decls: &'a IndexMap<TypeDeclId, TypeDecl>,
38    trait_decls: &'a IndexMap<TraitDeclId, TraitDecl>,
39    item_params: &'a mut GenericParams,
40    binders: BindingStack<OutlivesAtBinder>,
41}
42
43impl<'a> OutlivesGatherer<'a> {
44    fn new(
45        item_params: &'a mut GenericParams,
46        type_decls: &'a IndexMap<TypeDeclId, TypeDecl>,
47        trait_decls: &'a IndexMap<TraitDeclId, TraitDecl>,
48    ) -> Self {
49        Self {
50            type_decls,
51            trait_decls,
52            item_params,
53            binders: BindingStack::new(OutlivesAtBinder::default()),
54        }
55    }
56
57    fn finish(mut self) {
58        let outlives = self.binders.pop().unwrap();
59        debug_assert!(self.binders.is_empty());
60        outlives.finish(&mut self.item_params.outlives);
61    }
62
63    fn add_outlives(&mut self, pred: PolyOutlivesPred) {
64        let (pred, level) = self.binders.place_at_outermost(&pred);
65        level.outlives.insert(pred);
66    }
67    fn add_outliving_region(&mut self, longer: &Region) {
68        // Find the innermost region that affects `longer`: it needs to be bound at a level where
69        // `longer` can be moved to.
70        let Some((bound_depth, pred)) =
71            self.binders.iter_enumerated().find_map(|(depth, binder)| {
72                let shorter = binder.shorter_region.clone()?;
73                let longer = longer.clone().move_from_under_binders(depth)?;
74                let pred = RegionBinder::empty(OutlivesPred(longer, shorter));
75                Some((depth, pred))
76            })
77        else {
78            return;
79        };
80        // Place the predicate at the outermost level.
81        let (pred, level) = self.binders[bound_depth..].place_at_outermost(&pred);
82        level.outlives.insert(pred);
83    }
84
85    fn with_shorter_region(
86        &mut self,
87        region: Region,
88        f: impl FnOnce(&mut Self) -> ControlFlow<Infallible>,
89    ) -> ControlFlow<Infallible> {
90        self.add_outliving_region(&region);
91        let previous = self.binders.innermost_mut().shorter_region.replace(region);
92        let result = f(self);
93        self.binders.innermost_mut().shorter_region = previous;
94        result
95    }
96}
97
98impl VisitAstMut for OutlivesGatherer<'_> {
99    fn visit_binder<T: AstVisitable>(
100        &mut self,
101        binder: &mut Binder<T>,
102    ) -> ControlFlow<Self::Break> {
103        self.binders.push(OutlivesAtBinder::default());
104        let result = self.visit_inner(binder);
105        self.binders
106            .pop()
107            .unwrap()
108            .finish(&mut binder.params.outlives);
109        result
110    }
111
112    fn visit_region_binder<T: AstVisitable>(
113        &mut self,
114        binder: &mut RegionBinder<T>,
115    ) -> ControlFlow<Self::Break> {
116        self.binders.push(OutlivesAtBinder::default());
117        let result = self.visit_inner(binder);
118        self.binders.pop().unwrap().finish(&mut binder.outlives);
119        result
120    }
121
122    fn visit_ty(&mut self, ty: &mut Ty) -> ControlFlow<Self::Break> {
123        if let TyKind::TraitType(proof, type_id, args) = ty.kind()
124            && let Some(decl) = self.trait_decls.get(proof.trait_id())
125            && let Some(assoc) = decl.types.get(*type_id)
126        {
127            // Instantiate the trait parameters under the GAT binder, then the GAT parameters.
128            let assoc = assoc.clone().substitute_with_tref(proof);
129            for pred in assoc.params.outlives.substitute_inner_binder(args) {
130                self.add_outlives(pred);
131            }
132        }
133        match ty.kind() {
134            TyKind::TypeVar(_) | TyKind::TraitType(..) => {
135                self.add_outliving_region(&Region::Lub(ty.clone()));
136                // `T::Assoc: 'a` does not imply `T: 'a`. We temporarily remove `shorter_region`
137                // from all binders while we visit the type.
138                let shorter_regions = self
139                    .binders
140                    .iter_mut()
141                    .map(|binder| binder.shorter_region.take())
142                    .collect_vec();
143                let result = self.visit_inner(ty);
144                for (binder, shorter) in self.binders.iter_mut().zip(shorter_regions) {
145                    binder.shorter_region = shorter;
146                }
147                return result;
148            }
149            TyKind::Adt(type_ref) => {
150                if let Some(decl) = self.type_decls.get(type_ref.id) {
151                    let outlives = decl
152                        .generics
153                        .outlives
154                        .iter()
155                        .cloned()
156                        .map(|pred| pred.substitute(&type_ref.generics))
157                        .collect_vec();
158                    for pred in outlives {
159                        self.add_outlives(pred);
160                    }
161                }
162            }
163            _ => {}
164        }
165        match ty.kind() {
166            TyKind::Ref(region @ (Region::Static | Region::Var(_) | Region::Lub(_)), _, _) => {
167                self.with_shorter_region(region.clone(), |this| this.visit_inner(ty))
168            }
169            _ => self.visit_inner(ty),
170        }
171    }
172
173    fn enter_region(&mut self, region: &mut Region) {
174        if matches!(region, Region::Var(_) | Region::Lub(_)) {
175            self.add_outliving_region(region);
176        }
177    }
178}
179
180struct ClosureOutlivesComputer<'a> {
181    type_decls: &'a mut IndexMap<TypeDeclId, TypeDecl>,
182    trait_decls: &'a IndexMap<TraitDeclId, TraitDecl>,
183    /// Map of types we want to process.
184    closure_tys: SeqHashMap<TypeDeclId, CycleDetector<()>>,
185}
186
187impl<'a> ClosureOutlivesComputer<'a> {
188    fn new(
189        type_decls: &'a mut IndexMap<TypeDeclId, TypeDecl>,
190        trait_decls: &'a IndexMap<TraitDeclId, TraitDecl>,
191    ) -> Self {
192        let closure_tys = type_decls
193            .iter()
194            .filter(|decl| matches!(decl.src, TypeSource::Closure { .. }))
195            .map(|decl| (decl.def_id, CycleDetector::Unprocessed))
196            .collect();
197        Self {
198            type_decls,
199            trait_decls,
200            closure_tys,
201        }
202    }
203
204    fn compute_all(mut self) {
205        for type_id in self.closure_tys.keys().cloned().collect_vec() {
206            self.compute(type_id);
207        }
208    }
209
210    fn compute(&mut self, type_id: TypeDeclId) {
211        if self.closure_tys[&type_id].start_processing() {
212            let mut dependencies = Vec::new();
213            self.type_decls[type_id]
214                .kind
215                .dyn_visit(|type_ref: &TypeDeclRef| {
216                    if self.closure_tys.get(&type_ref.id).is_some() {
217                        dependencies.push(type_ref.id);
218                    }
219                });
220            for dependency in dependencies {
221                self.compute(dependency);
222            }
223
224            // Move the kind out so that the crate can inspect the rest of the decls.
225            let mut kind = mem::replace(&mut self.type_decls[type_id].kind, TypeDeclKind::Opaque);
226            let mut params = mem::take(&mut self.type_decls[type_id].generics);
227            let mut visitor = OutlivesGatherer::new(&mut params, self.type_decls, self.trait_decls);
228            visitor.visit(&mut kind);
229            visitor.finish();
230            self.type_decls[type_id].generics = params;
231            self.type_decls[type_id].kind = kind;
232            self.closure_tys[&type_id].done_processing(());
233        }
234        assert!(
235            matches!(self.closure_tys[&type_id], CycleDetector::Processed(_)),
236            "closure type declarations unexpectedly form a cycle"
237        );
238    }
239}
240
241pub struct Transform;
242
243impl TransformPass for Transform {
244    fn transform_ctx(&self, ctx: &mut TransformCtx) {
245        let type_decls = &mut ctx.translated.type_decls;
246        let trait_decls = &mut ctx.translated.trait_decls;
247
248        // Rustc gives us explicit outlives for ADTs, but we make fake ADTs for closures, so we
249        // infer their outlives predicates here. Thankfully they can't be recursive, which makes
250        // the implementation much easier than having to deal with all ADTs.
251        ClosureOutlivesComputer::new(type_decls, trait_decls).compute_all();
252
253        for fun_decl in &mut ctx.translated.fun_decls {
254            let mut visitor =
255                OutlivesGatherer::new(&mut fun_decl.generics, type_decls, trait_decls);
256            visitor.visit(&mut fun_decl.signature);
257            // The impl header contributes to the implied bounds even if its types are
258            // not mentioned in the signature.
259            match &mut fun_decl.src {
260                FunSource::InherentImpl { self_ty } => {
261                    visitor.visit(self_ty);
262                }
263                FunSource::TraitImpl { trait_ref, .. } => {
264                    visitor.visit(trait_ref);
265                }
266                _ => {}
267            }
268            visitor.finish();
269
270            // Also add implied bounds to the inner binders inside bodies. Implied bounds involving
271            // only body or signature lifetimes must not be kept; they must be checked by
272            // borrow-checking.
273            OutlivesGatherer::new(&mut GenericParams::default(), type_decls, trait_decls)
274                .visit(&mut fun_decl.body);
275        }
276
277        for timpl in &mut ctx.translated.trait_impls {
278            let mut visitor = OutlivesGatherer::new(&mut timpl.generics, type_decls, trait_decls);
279            visitor.visit(&mut timpl.impl_trait);
280            visitor.finish();
281        }
282
283        for trait_id in trait_decls.iter_indices().collect_vec() {
284            // Keep the associated type declarations available while visiting method signatures.
285            let mut methods = mem::take(&mut trait_decls[trait_id].methods);
286            for method in &mut methods {
287                let mut visitor =
288                    OutlivesGatherer::new(&mut method.params, type_decls, trait_decls);
289                visitor.visit(&mut method.skip_binder.signature);
290                visitor.finish();
291            }
292            trait_decls[trait_id].methods = methods;
293        }
294    }
295}