charon_lib/transform/add_missing_info/
add_implied_outlives.rs1use 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 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#[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 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 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(®ion);
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 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 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 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 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 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 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 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 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}