charon_lib/transform/add_missing_info/
add_implied_outlives.rs

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

charon_lib/transform/add_missing_info/
add_implied_outlives.rs
