1 //! Traits for transforming bits of IR.
2 
3 use crate::*;
4 use std::fmt::Debug;
5 
6 mod binder_impls;
7 mod boring_impls;
8 mod in_place;
9 pub mod shift;
10 mod subst;
11 
12 pub use self::shift::Shift;
13 pub use self::subst::Subst;
14 
15 /// A "folder" is a transformer that can be used to make a copy of
16 /// some term -- that is, some bit of IR, such as a `Goal` -- with
17 /// certain changes applied. The idea is that it contains methods that
18 /// let you swap types/lifetimes for new types/lifetimes; meanwhile,
19 /// each bit of IR implements the `Fold` trait which, given a
20 /// `Folder`, will reconstruct itself, invoking the folder's methods
21 /// to transform each of the types/lifetimes embedded within.
22 ///
23 /// # Usage patterns
24 ///
25 /// ## Substituting for free variables
26 ///
27 /// Most of the time, though, we are not interested in adjust
28 /// arbitrary types/lifetimes, but rather just free variables (even
29 /// more often, just free existential variables) that appear within
30 /// the term.
31 ///
32 /// For this reason, the `Folder` trait extends two other traits that
33 /// contain methods that are invoked when just those particular
34 ///
35 /// In particular, folders can intercept references to free variables
36 /// (either existentially or universally quantified) and replace them
37 /// with other types/lifetimes as appropriate.
38 ///
39 /// To create a folder `F`, one never implements `Folder` directly, but instead
40 /// implements one of each of these three sub-traits:
41 ///
42 /// - `FreeVarFolder` -- folds `BoundVar` instances that appear free
43 ///   in the term being folded (use `DefaultFreeVarFolder` to
44 ///   ignore/forbid these altogether)
45 /// - `InferenceFolder` -- folds existential `InferenceVar` instances
46 ///   that appear in the term being folded (use
47 ///   `DefaultInferenceFolder` to ignore/forbid these altogether)
48 /// - `PlaceholderFolder` -- folds universal `Placeholder` instances
49 ///   that appear in the term being folded (use
50 ///   `DefaultPlaceholderFolder` to ignore/forbid these altogether)
51 ///
52 /// To **apply** a folder, use the `Fold::fold_with` method, like so
53 ///
54 /// ```rust,ignore
55 /// let x = x.fold_with(&mut folder, 0);
56 /// ```
57 pub trait Folder<I: Interner> {
58     /// The type this folder returns when folding fails. This is
59     /// commonly [`NoSolution`].
60     type Error;
61 
62     /// Creates a `dyn` value from this folder. Unfortunately, this
63     /// must be added manually to each impl of Folder; it permits the
64     /// default implements below to create a `&mut dyn Folder` from
65     /// `Self` without knowing what `Self` is (by invoking this
66     /// method). Effectively, this limits impls of `Folder` to types
67     /// for which we are able to create a dyn value (i.e., not `[T]`
68     /// types).
as_dyn(&mut self) -> &mut dyn Folder<I, Error = Self::Error>69     fn as_dyn(&mut self) -> &mut dyn Folder<I, Error = Self::Error>;
70 
71     /// Top-level callback: invoked for each `Ty<I>` that is
72     /// encountered when folding. By default, invokes
73     /// `super_fold_with`, which will in turn invoke the more
74     /// specialized folding methods below, like `fold_free_var_ty`.
fold_ty(&mut self, ty: Ty<I>, outer_binder: DebruijnIndex) -> Result<Ty<I>, Self::Error>75     fn fold_ty(&mut self, ty: Ty<I>, outer_binder: DebruijnIndex) -> Result<Ty<I>, Self::Error> {
76         ty.super_fold_with(self.as_dyn(), outer_binder)
77     }
78 
79     /// Top-level callback: invoked for each `Lifetime<I>` that is
80     /// encountered when folding. By default, invokes
81     /// `super_fold_with`, which will in turn invoke the more
82     /// specialized folding methods below, like `fold_free_var_lifetime`.
fold_lifetime( &mut self, lifetime: Lifetime<I>, outer_binder: DebruijnIndex, ) -> Result<Lifetime<I>, Self::Error>83     fn fold_lifetime(
84         &mut self,
85         lifetime: Lifetime<I>,
86         outer_binder: DebruijnIndex,
87     ) -> Result<Lifetime<I>, Self::Error> {
88         lifetime.super_fold_with(self.as_dyn(), outer_binder)
89     }
90 
91     /// Top-level callback: invoked for each `Const<I>` that is
92     /// encountered when folding. By default, invokes
93     /// `super_fold_with`, which will in turn invoke the more
94     /// specialized folding methods below, like `fold_free_var_const`.
fold_const( &mut self, constant: Const<I>, outer_binder: DebruijnIndex, ) -> Result<Const<I>, Self::Error>95     fn fold_const(
96         &mut self,
97         constant: Const<I>,
98         outer_binder: DebruijnIndex,
99     ) -> Result<Const<I>, Self::Error> {
100         constant.super_fold_with(self.as_dyn(), outer_binder)
101     }
102 
103     /// Invoked for every program clause. By default, recursively folds the goals contents.
fold_program_clause( &mut self, clause: ProgramClause<I>, outer_binder: DebruijnIndex, ) -> Result<ProgramClause<I>, Self::Error>104     fn fold_program_clause(
105         &mut self,
106         clause: ProgramClause<I>,
107         outer_binder: DebruijnIndex,
108     ) -> Result<ProgramClause<I>, Self::Error> {
109         clause.super_fold_with(self.as_dyn(), outer_binder)
110     }
111 
112     /// Invoked for every goal. By default, recursively folds the goals contents.
fold_goal( &mut self, goal: Goal<I>, outer_binder: DebruijnIndex, ) -> Result<Goal<I>, Self::Error>113     fn fold_goal(
114         &mut self,
115         goal: Goal<I>,
116         outer_binder: DebruijnIndex,
117     ) -> Result<Goal<I>, Self::Error> {
118         goal.super_fold_with(self.as_dyn(), outer_binder)
119     }
120 
121     /// If overridden to return true, then folding will panic if a
122     /// free variable is encountered. This should be done if free
123     /// type/lifetime variables are not expected.
forbid_free_vars(&self) -> bool124     fn forbid_free_vars(&self) -> bool {
125         false
126     }
127 
128     /// Invoked for `TyKind::BoundVar` instances that are not bound
129     /// within the type being folded over:
130     ///
131     /// - `depth` is the depth of the `TyKind::BoundVar`; this has
132     ///   been adjusted to account for binders in scope.
133     /// - `binders` is the number of binders in scope.
134     ///
135     /// This should return a type suitable for a context with
136     /// `binders` in scope.
fold_free_var_ty( &mut self, bound_var: BoundVar, outer_binder: DebruijnIndex, ) -> Result<Ty<I>, Self::Error>137     fn fold_free_var_ty(
138         &mut self,
139         bound_var: BoundVar,
140         outer_binder: DebruijnIndex,
141     ) -> Result<Ty<I>, Self::Error> {
142         if self.forbid_free_vars() {
143             panic!(
144                 "unexpected free variable with depth `{:?}` with outer binder {:?}",
145                 bound_var, outer_binder
146             )
147         } else {
148             let bound_var = bound_var.shifted_in_from(outer_binder);
149             Ok(TyKind::<I>::BoundVar(bound_var).intern(self.interner()))
150         }
151     }
152 
153     /// As `fold_free_var_ty`, but for lifetimes.
fold_free_var_lifetime( &mut self, bound_var: BoundVar, outer_binder: DebruijnIndex, ) -> Result<Lifetime<I>, Self::Error>154     fn fold_free_var_lifetime(
155         &mut self,
156         bound_var: BoundVar,
157         outer_binder: DebruijnIndex,
158     ) -> Result<Lifetime<I>, Self::Error> {
159         if self.forbid_free_vars() {
160             panic!(
161                 "unexpected free variable with depth `{:?}` with outer binder {:?}",
162                 bound_var, outer_binder
163             )
164         } else {
165             let bound_var = bound_var.shifted_in_from(outer_binder);
166             Ok(LifetimeData::<I>::BoundVar(bound_var).intern(self.interner()))
167         }
168     }
169 
170     /// As `fold_free_var_ty`, but for constants.
fold_free_var_const( &mut self, ty: Ty<I>, bound_var: BoundVar, outer_binder: DebruijnIndex, ) -> Result<Const<I>, Self::Error>171     fn fold_free_var_const(
172         &mut self,
173         ty: Ty<I>,
174         bound_var: BoundVar,
175         outer_binder: DebruijnIndex,
176     ) -> Result<Const<I>, Self::Error> {
177         if self.forbid_free_vars() {
178             panic!(
179                 "unexpected free variable with depth `{:?}` with outer binder {:?}",
180                 bound_var, outer_binder
181             )
182         } else {
183             let bound_var = bound_var.shifted_in_from(outer_binder);
184             Ok(ConstData {
185                 ty: ty.clone().fold_with(self.as_dyn(), outer_binder)?,
186                 value: ConstValue::<I>::BoundVar(bound_var),
187             }
188             .intern(self.interner()))
189         }
190     }
191 
192     /// If overridden to return true, we will panic when a free
193     /// placeholder type/lifetime/const is encountered.
forbid_free_placeholders(&self) -> bool194     fn forbid_free_placeholders(&self) -> bool {
195         false
196     }
197 
198     /// Invoked for each occurrence of a placeholder type; these are
199     /// used when we instantiate binders universally. Returns a type
200     /// to use instead, which should be suitably shifted to account
201     /// for `binders`.
202     ///
203     /// - `universe` is the universe of the `TypeName::ForAll` that was found
204     /// - `binders` is the number of binders in scope
205     #[allow(unused_variables)]
fold_free_placeholder_ty( &mut self, universe: PlaceholderIndex, outer_binder: DebruijnIndex, ) -> Result<Ty<I>, Self::Error>206     fn fold_free_placeholder_ty(
207         &mut self,
208         universe: PlaceholderIndex,
209         outer_binder: DebruijnIndex,
210     ) -> Result<Ty<I>, Self::Error> {
211         if self.forbid_free_placeholders() {
212             panic!("unexpected placeholder type `{:?}`", universe)
213         } else {
214             Ok(universe.to_ty::<I>(self.interner()))
215         }
216     }
217 
218     /// As with `fold_free_placeholder_ty`, but for lifetimes.
219     #[allow(unused_variables)]
fold_free_placeholder_lifetime( &mut self, universe: PlaceholderIndex, outer_binder: DebruijnIndex, ) -> Result<Lifetime<I>, Self::Error>220     fn fold_free_placeholder_lifetime(
221         &mut self,
222         universe: PlaceholderIndex,
223         outer_binder: DebruijnIndex,
224     ) -> Result<Lifetime<I>, Self::Error> {
225         if self.forbid_free_placeholders() {
226             panic!("unexpected placeholder lifetime `{:?}`", universe)
227         } else {
228             Ok(universe.to_lifetime(self.interner()))
229         }
230     }
231 
232     /// As with `fold_free_placeholder_ty`, but for constants.
233     #[allow(unused_variables)]
fold_free_placeholder_const( &mut self, ty: Ty<I>, universe: PlaceholderIndex, outer_binder: DebruijnIndex, ) -> Result<Const<I>, Self::Error>234     fn fold_free_placeholder_const(
235         &mut self,
236         ty: Ty<I>,
237         universe: PlaceholderIndex,
238         outer_binder: DebruijnIndex,
239     ) -> Result<Const<I>, Self::Error> {
240         if self.forbid_free_placeholders() {
241             panic!("unexpected placeholder const `{:?}`", universe)
242         } else {
243             Ok(universe.to_const(self.interner(), ty.fold_with(self.as_dyn(), outer_binder)?))
244         }
245     }
246 
247     /// If overridden to return true, inference variables will trigger
248     /// panics when folded. Used when inference variables are
249     /// unexpected.
forbid_inference_vars(&self) -> bool250     fn forbid_inference_vars(&self) -> bool {
251         false
252     }
253 
254     /// Invoked for each occurrence of a inference type; these are
255     /// used when we instantiate binders universally. Returns a type
256     /// to use instead, which should be suitably shifted to account
257     /// for `binders`.
258     ///
259     /// - `universe` is the universe of the `TypeName::ForAll` that was found
260     /// - `binders` is the number of binders in scope
261     #[allow(unused_variables)]
fold_inference_ty( &mut self, var: InferenceVar, kind: TyVariableKind, outer_binder: DebruijnIndex, ) -> Result<Ty<I>, Self::Error>262     fn fold_inference_ty(
263         &mut self,
264         var: InferenceVar,
265         kind: TyVariableKind,
266         outer_binder: DebruijnIndex,
267     ) -> Result<Ty<I>, Self::Error> {
268         if self.forbid_inference_vars() {
269             panic!("unexpected inference type `{:?}`", var)
270         } else {
271             Ok(var.to_ty(self.interner(), kind))
272         }
273     }
274 
275     /// As with `fold_inference_ty`, but for lifetimes.
276     #[allow(unused_variables)]
fold_inference_lifetime( &mut self, var: InferenceVar, outer_binder: DebruijnIndex, ) -> Result<Lifetime<I>, Self::Error>277     fn fold_inference_lifetime(
278         &mut self,
279         var: InferenceVar,
280         outer_binder: DebruijnIndex,
281     ) -> Result<Lifetime<I>, Self::Error> {
282         if self.forbid_inference_vars() {
283             panic!("unexpected inference lifetime `'{:?}`", var)
284         } else {
285             Ok(var.to_lifetime(self.interner()))
286         }
287     }
288 
289     /// As with `fold_inference_ty`, but for constants.
290     #[allow(unused_variables)]
fold_inference_const( &mut self, ty: Ty<I>, var: InferenceVar, outer_binder: DebruijnIndex, ) -> Result<Const<I>, Self::Error>291     fn fold_inference_const(
292         &mut self,
293         ty: Ty<I>,
294         var: InferenceVar,
295         outer_binder: DebruijnIndex,
296     ) -> Result<Const<I>, Self::Error> {
297         if self.forbid_inference_vars() {
298             panic!("unexpected inference const `{:?}`", var)
299         } else {
300             Ok(var.to_const(self.interner(), ty.fold_with(self.as_dyn(), outer_binder)?))
301         }
302     }
303 
304     /// Gets the interner that is being folded from.
interner(&self) -> I305     fn interner(&self) -> I;
306 }
307 
308 /// Applies the given `Folder` to a value, producing a folded result
309 /// of type `Self::Result`. The result type is typically the same as
310 /// the source type, but in some cases we convert from borrowed
311 /// to owned as well (e.g., the folder for `&T` will fold to a fresh
312 /// `T`; well, actually `T::Result`).
313 pub trait Fold<I: Interner>: Debug {
314     /// The type of value that will be produced once folding is done.
315     /// Typically this is `Self`, unless `Self` contains borrowed
316     /// values, in which case owned values are produced (for example,
317     /// one can fold over a `&T` value where `T: Fold`, in which case
318     /// you get back a `T`, not a `&T`).
319     type Result;
320 
321     /// Apply the given folder `folder` to `self`; `binders` is the
322     /// number of binders that are in scope when beginning the
323     /// folder. Typically `binders` starts as 0, but is adjusted when
324     /// we encounter `Binders<T>` in the IR or other similar
325     /// constructs.
fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>326     fn fold_with<E>(
327         self,
328         folder: &mut dyn Folder<I, Error = E>,
329         outer_binder: DebruijnIndex,
330     ) -> Result<Self::Result, E>;
331 }
332 
333 /// For types where "fold" invokes a callback on the `Folder`, the
334 /// `SuperFold` trait captures the recursive behavior that folds all
335 /// the contents of the type.
336 pub trait SuperFold<I: Interner>: Fold<I> {
337     /// Recursively folds the value.
super_fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>338     fn super_fold_with<E>(
339         self,
340         folder: &mut dyn Folder<I, Error = E>,
341         outer_binder: DebruijnIndex,
342     ) -> Result<Self::Result, E>;
343 }
344 
345 /// "Folding" a type invokes the `fold_ty` method on the folder; this
346 /// usually (in turn) invokes `super_fold_ty` to fold the individual
347 /// parts.
348 impl<I: Interner> Fold<I> for Ty<I> {
349     type Result = Ty<I>;
350 
fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>351     fn fold_with<E>(
352         self,
353         folder: &mut dyn Folder<I, Error = E>,
354         outer_binder: DebruijnIndex,
355     ) -> Result<Self::Result, E> {
356         folder.fold_ty(self, outer_binder)
357     }
358 }
359 
360 /// "Super fold" for a type invokes te more detailed callbacks on the type
361 impl<I> SuperFold<I> for Ty<I>
362 where
363     I: Interner,
364 {
super_fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Ty<I>, E>365     fn super_fold_with<E>(
366         self,
367         folder: &mut dyn Folder<I, Error = E>,
368         outer_binder: DebruijnIndex,
369     ) -> Result<Ty<I>, E> {
370         let interner = folder.interner();
371         Ok(match self.kind(interner) {
372             TyKind::BoundVar(bound_var) => {
373                 if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) {
374                     // This variable was bound outside of the binders
375                     // that we have traversed during folding;
376                     // therefore, it is free. Let the folder have a
377                     // crack at it.
378                     folder.fold_free_var_ty(bound_var1, outer_binder)?
379                 } else {
380                     // This variable was bound within the binders that
381                     // we folded over, so just return a bound
382                     // variable.
383                     self
384                 }
385             }
386             TyKind::Dyn(clauses) => TyKind::Dyn(clauses.clone().fold_with(folder, outer_binder)?)
387                 .intern(folder.interner()),
388             TyKind::InferenceVar(var, kind) => {
389                 folder.fold_inference_ty(*var, *kind, outer_binder)?
390             }
391             TyKind::Placeholder(ui) => folder.fold_free_placeholder_ty(*ui, outer_binder)?,
392             TyKind::Alias(proj) => TyKind::Alias(proj.clone().fold_with(folder, outer_binder)?)
393                 .intern(folder.interner()),
394             TyKind::Function(fun) => TyKind::Function(fun.clone().fold_with(folder, outer_binder)?)
395                 .intern(folder.interner()),
396             TyKind::Adt(id, substitution) => TyKind::Adt(
397                 id.fold_with(folder, outer_binder)?,
398                 substitution.clone().fold_with(folder, outer_binder)?,
399             )
400             .intern(folder.interner()),
401             TyKind::AssociatedType(assoc_ty, substitution) => TyKind::AssociatedType(
402                 assoc_ty.fold_with(folder, outer_binder)?,
403                 substitution.clone().fold_with(folder, outer_binder)?,
404             )
405             .intern(folder.interner()),
406             TyKind::Scalar(scalar) => {
407                 TyKind::Scalar(scalar.fold_with(folder, outer_binder)?).intern(folder.interner())
408             }
409             TyKind::Str => TyKind::Str.intern(folder.interner()),
410             TyKind::Tuple(arity, substitution) => TyKind::Tuple(
411                 *arity,
412                 substitution.clone().fold_with(folder, outer_binder)?,
413             )
414             .intern(folder.interner()),
415             TyKind::OpaqueType(opaque_ty, substitution) => TyKind::OpaqueType(
416                 opaque_ty.fold_with(folder, outer_binder)?,
417                 substitution.clone().fold_with(folder, outer_binder)?,
418             )
419             .intern(folder.interner()),
420             TyKind::Slice(substitution) => {
421                 TyKind::Slice(substitution.clone().fold_with(folder, outer_binder)?)
422                     .intern(folder.interner())
423             }
424             TyKind::FnDef(fn_def, substitution) => TyKind::FnDef(
425                 fn_def.fold_with(folder, outer_binder)?,
426                 substitution.clone().fold_with(folder, outer_binder)?,
427             )
428             .intern(folder.interner()),
429             TyKind::Ref(mutability, lifetime, ty) => TyKind::Ref(
430                 mutability.fold_with(folder, outer_binder)?,
431                 lifetime.clone().fold_with(folder, outer_binder)?,
432                 ty.clone().fold_with(folder, outer_binder)?,
433             )
434             .intern(folder.interner()),
435             TyKind::Raw(mutability, ty) => TyKind::Raw(
436                 mutability.fold_with(folder, outer_binder)?,
437                 ty.clone().fold_with(folder, outer_binder)?,
438             )
439             .intern(folder.interner()),
440             TyKind::Never => TyKind::Never.intern(folder.interner()),
441             TyKind::Array(ty, const_) => TyKind::Array(
442                 ty.clone().fold_with(folder, outer_binder)?,
443                 const_.clone().fold_with(folder, outer_binder)?,
444             )
445             .intern(folder.interner()),
446             TyKind::Closure(id, substitution) => TyKind::Closure(
447                 id.fold_with(folder, outer_binder)?,
448                 substitution.clone().fold_with(folder, outer_binder)?,
449             )
450             .intern(folder.interner()),
451             TyKind::Generator(id, substitution) => TyKind::Generator(
452                 id.fold_with(folder, outer_binder)?,
453                 substitution.clone().fold_with(folder, outer_binder)?,
454             )
455             .intern(folder.interner()),
456             TyKind::GeneratorWitness(id, substitution) => TyKind::GeneratorWitness(
457                 id.fold_with(folder, outer_binder)?,
458                 substitution.clone().fold_with(folder, outer_binder)?,
459             )
460             .intern(folder.interner()),
461             TyKind::Foreign(id) => {
462                 TyKind::Foreign(id.fold_with(folder, outer_binder)?).intern(folder.interner())
463             }
464             TyKind::Error => TyKind::Error.intern(folder.interner()),
465         })
466     }
467 }
468 
469 /// "Folding" a lifetime invokes the `fold_lifetime` method on the folder; this
470 /// usually (in turn) invokes `super_fold_lifetime` to fold the individual
471 /// parts.
472 impl<I: Interner> Fold<I> for Lifetime<I> {
473     type Result = Lifetime<I>;
474 
fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>475     fn fold_with<E>(
476         self,
477         folder: &mut dyn Folder<I, Error = E>,
478         outer_binder: DebruijnIndex,
479     ) -> Result<Self::Result, E> {
480         folder.fold_lifetime(self, outer_binder)
481     }
482 }
483 
484 impl<I> SuperFold<I> for Lifetime<I>
485 where
486     I: Interner,
487 {
super_fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Lifetime<I>, E>488     fn super_fold_with<E>(
489         self,
490         folder: &mut dyn Folder<I, Error = E>,
491         outer_binder: DebruijnIndex,
492     ) -> Result<Lifetime<I>, E> {
493         let interner = folder.interner();
494         match self.data(interner) {
495             LifetimeData::BoundVar(bound_var) => {
496                 if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) {
497                     // This variable was bound outside of the binders
498                     // that we have traversed during folding;
499                     // therefore, it is free. Let the folder have a
500                     // crack at it.
501                     folder.fold_free_var_lifetime(bound_var1, outer_binder)
502                 } else {
503                     // This variable was bound within the binders that
504                     // we folded over, so just return a bound
505                     // variable.
506                     Ok(self)
507                 }
508             }
509             LifetimeData::InferenceVar(var) => folder.fold_inference_lifetime(*var, outer_binder),
510             LifetimeData::Placeholder(universe) => {
511                 folder.fold_free_placeholder_lifetime(*universe, outer_binder)
512             }
513             LifetimeData::Static => Ok(LifetimeData::<I>::Static.intern(folder.interner())),
514             LifetimeData::Empty(ui) => Ok(LifetimeData::<I>::Empty(*ui).intern(folder.interner())),
515             LifetimeData::Erased => Ok(LifetimeData::<I>::Erased.intern(folder.interner())),
516             LifetimeData::Phantom(void, ..) => match *void {},
517         }
518     }
519 }
520 
521 /// "Folding" a const invokes the `fold_const` method on the folder; this
522 /// usually (in turn) invokes `super_fold_const` to fold the individual
523 /// parts.
524 impl<I: Interner> Fold<I> for Const<I> {
525     type Result = Const<I>;
526 
fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>527     fn fold_with<E>(
528         self,
529         folder: &mut dyn Folder<I, Error = E>,
530         outer_binder: DebruijnIndex,
531     ) -> Result<Self::Result, E> {
532         folder.fold_const(self, outer_binder)
533     }
534 }
535 
536 impl<I> SuperFold<I> for Const<I>
537 where
538     I: Interner,
539 {
super_fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Const<I>, E>540     fn super_fold_with<E>(
541         self,
542         folder: &mut dyn Folder<I, Error = E>,
543         outer_binder: DebruijnIndex,
544     ) -> Result<Const<I>, E> {
545         let interner = folder.interner();
546         let ConstData { ref ty, ref value } = self.data(interner);
547         let mut fold_ty = || ty.clone().fold_with(folder, outer_binder);
548         match value {
549             ConstValue::BoundVar(bound_var) => {
550                 if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) {
551                     folder.fold_free_var_const(ty.clone(), bound_var1, outer_binder)
552                 } else {
553                     Ok(self)
554                 }
555             }
556             ConstValue::InferenceVar(var) => {
557                 folder.fold_inference_const(ty.clone(), *var, outer_binder)
558             }
559             ConstValue::Placeholder(universe) => {
560                 folder.fold_free_placeholder_const(ty.clone(), *universe, outer_binder)
561             }
562             ConstValue::Concrete(ev) => Ok(ConstData {
563                 ty: fold_ty()?,
564                 value: ConstValue::Concrete(ConcreteConst {
565                     interned: ev.interned.clone(),
566                 }),
567             }
568             .intern(folder.interner())),
569         }
570     }
571 }
572 
573 /// Folding a goal invokes the `fold_goal` callback (which will, by
574 /// default, invoke super-fold).
575 impl<I: Interner> Fold<I> for Goal<I> {
576     type Result = Goal<I>;
577 
fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>578     fn fold_with<E>(
579         self,
580         folder: &mut dyn Folder<I, Error = E>,
581         outer_binder: DebruijnIndex,
582     ) -> Result<Self::Result, E> {
583         folder.fold_goal(self, outer_binder)
584     }
585 }
586 
587 /// Superfold folds recursively.
588 impl<I: Interner> SuperFold<I> for Goal<I> {
super_fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>589     fn super_fold_with<E>(
590         self,
591         folder: &mut dyn Folder<I, Error = E>,
592         outer_binder: DebruijnIndex,
593     ) -> Result<Self::Result, E> {
594         let interner = folder.interner();
595         Ok(Goal::new(
596             interner,
597             self.data(interner)
598                 .clone()
599                 .fold_with(folder, outer_binder)?,
600         ))
601     }
602 }
603 
604 /// Folding a program clause invokes the `fold_program_clause`
605 /// callback on the folder (which will, by default, invoke the
606 /// `super_fold_with` method on the program clause).
607 impl<I: Interner> Fold<I> for ProgramClause<I> {
608     type Result = ProgramClause<I>;
609 
fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>610     fn fold_with<E>(
611         self,
612         folder: &mut dyn Folder<I, Error = E>,
613         outer_binder: DebruijnIndex,
614     ) -> Result<Self::Result, E> {
615         folder.fold_program_clause(self, outer_binder)
616     }
617 }
618