diff options
Diffstat (limited to 'vendor/chalk-ir/src/fold.rs')
| -rw-r--r-- | vendor/chalk-ir/src/fold.rs | 920 |
1 files changed, 920 insertions, 0 deletions
diff --git a/vendor/chalk-ir/src/fold.rs b/vendor/chalk-ir/src/fold.rs new file mode 100644 index 000000000..b15cbff7a --- /dev/null +++ b/vendor/chalk-ir/src/fold.rs @@ -0,0 +1,920 @@ +//! Traits for transforming bits of IR. + +use crate::*; +use std::convert::Infallible; +use std::fmt::Debug; + +mod binder_impls; +mod boring_impls; +mod in_place; +pub mod shift; +mod subst; + +pub use self::shift::Shift; +pub use self::subst::Subst; + +/// A "folder" is a transformer that can be used to make a copy of +/// some term -- that is, some bit of IR, such as a `Goal` -- with +/// certain changes applied. The idea is that it contains methods that +/// let you swap types/lifetimes for new types/lifetimes; meanwhile, +/// each bit of IR implements the `TypeFoldable` trait which, given a +/// `FallibleTypeFolder`, will reconstruct itself, invoking the folder's +/// methods to transform each of the types/lifetimes embedded within. +/// +/// As the name suggests, folds performed by `FallibleTypeFolder` can +/// fail (with type `Error`); if the folder cannot fail, consider +/// implementing `TypeFolder` instead (which is an infallible, but +/// otherwise equivalent, trait). +/// +/// # Usage patterns +/// +/// ## Substituting for free variables +/// +/// Most of the time, though, we are not interested in adjust +/// arbitrary types/lifetimes, but rather just free variables (even +/// more often, just free existential variables) that appear within +/// the term. +/// +/// For this reason, the `FallibleTypeFolder` trait extends two other +/// traits that contain methods that are invoked when just those particular +/// +/// In particular, folders can intercept references to free variables +/// (either existentially or universally quantified) and replace them +/// with other types/lifetimes as appropriate. +/// +/// To create a folder `F`, one never implements `FallibleTypeFolder` +/// directly, but instead implements one of each of these three sub-traits: +/// +/// - `FreeVarFolder` -- folds `BoundVar` instances that appear free +/// in the term being folded (use `DefaultFreeVarFolder` to +/// ignore/forbid these altogether) +/// - `InferenceFolder` -- folds existential `InferenceVar` instances +/// that appear in the term being folded (use +/// `DefaultInferenceFolder` to ignore/forbid these altogether) +/// - `PlaceholderFolder` -- folds universal `Placeholder` instances +/// that appear in the term being folded (use +/// `DefaultPlaceholderFolder` to ignore/forbid these altogether) +/// +/// To **apply** a folder, use the `TypeFoldable::try_fold_with` method, +/// like so +/// +/// ```rust,ignore +/// let x = x.try_fold_with(&mut folder, 0); +/// ``` +pub trait FallibleTypeFolder<I: Interner> { + /// The type this folder returns when folding fails. This is + /// commonly [`NoSolution`]. + type Error; + + /// Creates a `dyn` value from this folder. Unfortunately, this + /// must be added manually to each impl of FallibleTypeFolder; it + /// permits the default implements below to create a + /// `&mut dyn FallibleTypeFolder` from `Self` without knowing what + /// `Self` is (by invoking this method). Effectively, this limits + /// impls of `FallibleTypeFolder` to types for which we are able to + /// create a dyn value (i.e., not `[T]` types). + fn as_dyn(&mut self) -> &mut dyn FallibleTypeFolder<I, Error = Self::Error>; + + /// Top-level callback: invoked for each `Ty<I>` that is + /// encountered when folding. By default, invokes + /// `try_super_fold_with`, which will in turn invoke the more + /// specialized folding methods below, like `try_fold_free_var_ty`. + fn try_fold_ty( + &mut self, + ty: Ty<I>, + outer_binder: DebruijnIndex, + ) -> Result<Ty<I>, Self::Error> { + ty.try_super_fold_with(self.as_dyn(), outer_binder) + } + + /// Top-level callback: invoked for each `Lifetime<I>` that is + /// encountered when folding. By default, invokes + /// `try_super_fold_with`, which will in turn invoke the more + /// specialized folding methods below, like `try_fold_free_var_lifetime`. + fn try_fold_lifetime( + &mut self, + lifetime: Lifetime<I>, + outer_binder: DebruijnIndex, + ) -> Result<Lifetime<I>, Self::Error> { + lifetime.try_super_fold_with(self.as_dyn(), outer_binder) + } + + /// Top-level callback: invoked for each `Const<I>` that is + /// encountered when folding. By default, invokes + /// `try_super_fold_with`, which will in turn invoke the more + /// specialized folding methods below, like `try_fold_free_var_const`. + fn try_fold_const( + &mut self, + constant: Const<I>, + outer_binder: DebruijnIndex, + ) -> Result<Const<I>, Self::Error> { + constant.try_super_fold_with(self.as_dyn(), outer_binder) + } + + /// Invoked for every program clause. By default, recursively folds the goals contents. + fn try_fold_program_clause( + &mut self, + clause: ProgramClause<I>, + outer_binder: DebruijnIndex, + ) -> Result<ProgramClause<I>, Self::Error> { + clause.try_super_fold_with(self.as_dyn(), outer_binder) + } + + /// Invoked for every goal. By default, recursively folds the goals contents. + fn try_fold_goal( + &mut self, + goal: Goal<I>, + outer_binder: DebruijnIndex, + ) -> Result<Goal<I>, Self::Error> { + goal.try_super_fold_with(self.as_dyn(), outer_binder) + } + + /// If overridden to return true, then folding will panic if a + /// free variable is encountered. This should be done if free + /// type/lifetime variables are not expected. + fn forbid_free_vars(&self) -> bool { + false + } + + /// Invoked for `TyKind::BoundVar` instances that are not bound + /// within the type being folded over: + /// + /// - `depth` is the depth of the `TyKind::BoundVar`; this has + /// been adjusted to account for binders in scope. + /// - `binders` is the number of binders in scope. + /// + /// This should return a type suitable for a context with + /// `binders` in scope. + fn try_fold_free_var_ty( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Result<Ty<I>, Self::Error> { + if self.forbid_free_vars() { + panic!( + "unexpected free variable with depth `{:?}` with outer binder {:?}", + bound_var, outer_binder + ) + } else { + let bound_var = bound_var.shifted_in_from(outer_binder); + Ok(TyKind::<I>::BoundVar(bound_var).intern(self.interner())) + } + } + + /// As `try_fold_free_var_ty`, but for lifetimes. + fn try_fold_free_var_lifetime( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Result<Lifetime<I>, Self::Error> { + if self.forbid_free_vars() { + panic!( + "unexpected free variable with depth `{:?}` with outer binder {:?}", + bound_var, outer_binder + ) + } else { + let bound_var = bound_var.shifted_in_from(outer_binder); + Ok(LifetimeData::<I>::BoundVar(bound_var).intern(self.interner())) + } + } + + /// As `try_fold_free_var_ty`, but for constants. + fn try_fold_free_var_const( + &mut self, + ty: Ty<I>, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Result<Const<I>, Self::Error> { + if self.forbid_free_vars() { + panic!( + "unexpected free variable with depth `{:?}` with outer binder {:?}", + bound_var, outer_binder + ) + } else { + let bound_var = bound_var.shifted_in_from(outer_binder); + Ok(ConstData { + ty: ty.try_fold_with(self.as_dyn(), outer_binder)?, + value: ConstValue::<I>::BoundVar(bound_var), + } + .intern(self.interner())) + } + } + + /// If overridden to return true, we will panic when a free + /// placeholder type/lifetime/const is encountered. + fn forbid_free_placeholders(&self) -> bool { + false + } + + /// Invoked for each occurrence of a placeholder type; these are + /// used when we instantiate binders universally. Returns a type + /// to use instead, which should be suitably shifted to account + /// for `binders`. + /// + /// - `universe` is the universe of the `TypeName::ForAll` that was found + /// - `binders` is the number of binders in scope + #[allow(unused_variables)] + fn try_fold_free_placeholder_ty( + &mut self, + universe: PlaceholderIndex, + outer_binder: DebruijnIndex, + ) -> Result<Ty<I>, Self::Error> { + if self.forbid_free_placeholders() { + panic!("unexpected placeholder type `{:?}`", universe) + } else { + Ok(universe.to_ty::<I>(self.interner())) + } + } + + /// As with `try_fold_free_placeholder_ty`, but for lifetimes. + #[allow(unused_variables)] + fn try_fold_free_placeholder_lifetime( + &mut self, + universe: PlaceholderIndex, + outer_binder: DebruijnIndex, + ) -> Result<Lifetime<I>, Self::Error> { + if self.forbid_free_placeholders() { + panic!("unexpected placeholder lifetime `{:?}`", universe) + } else { + Ok(universe.to_lifetime(self.interner())) + } + } + + /// As with `try_fold_free_placeholder_ty`, but for constants. + #[allow(unused_variables)] + fn try_fold_free_placeholder_const( + &mut self, + ty: Ty<I>, + universe: PlaceholderIndex, + outer_binder: DebruijnIndex, + ) -> Result<Const<I>, Self::Error> { + if self.forbid_free_placeholders() { + panic!("unexpected placeholder const `{:?}`", universe) + } else { + Ok(universe.to_const( + self.interner(), + ty.try_fold_with(self.as_dyn(), outer_binder)?, + )) + } + } + + /// If overridden to return true, inference variables will trigger + /// panics when folded. Used when inference variables are + /// unexpected. + fn forbid_inference_vars(&self) -> bool { + false + } + + /// Invoked for each occurrence of a inference type; these are + /// used when we instantiate binders universally. Returns a type + /// to use instead, which should be suitably shifted to account + /// for `binders`. + /// + /// - `universe` is the universe of the `TypeName::ForAll` that was found + /// - `binders` is the number of binders in scope + #[allow(unused_variables)] + fn try_fold_inference_ty( + &mut self, + var: InferenceVar, + kind: TyVariableKind, + outer_binder: DebruijnIndex, + ) -> Result<Ty<I>, Self::Error> { + if self.forbid_inference_vars() { + panic!("unexpected inference type `{:?}`", var) + } else { + Ok(var.to_ty(self.interner(), kind)) + } + } + + /// As with `try_fold_inference_ty`, but for lifetimes. + #[allow(unused_variables)] + fn try_fold_inference_lifetime( + &mut self, + var: InferenceVar, + outer_binder: DebruijnIndex, + ) -> Result<Lifetime<I>, Self::Error> { + if self.forbid_inference_vars() { + panic!("unexpected inference lifetime `'{:?}`", var) + } else { + Ok(var.to_lifetime(self.interner())) + } + } + + /// As with `try_fold_inference_ty`, but for constants. + #[allow(unused_variables)] + fn try_fold_inference_const( + &mut self, + ty: Ty<I>, + var: InferenceVar, + outer_binder: DebruijnIndex, + ) -> Result<Const<I>, Self::Error> { + if self.forbid_inference_vars() { + panic!("unexpected inference const `{:?}`", var) + } else { + Ok(var.to_const( + self.interner(), + ty.try_fold_with(self.as_dyn(), outer_binder)?, + )) + } + } + + /// Gets the interner that is being folded from. + fn interner(&self) -> I; +} + +/// A "folder" is a transformer that can be used to make a copy of +/// some term -- that is, some bit of IR, such as a `Goal` -- with +/// certain changes applied. The idea is that it contains methods that +/// let you swap types/lifetimes for new types/lifetimes; meanwhile, +/// each bit of IR implements the `TypeFoldable` trait which, given a +/// `TypeFolder`, will reconstruct itself, invoking the folder's methods +/// to transform each of the types/lifetimes embedded within. +/// +/// Folds performed by `TypeFolder` cannot fail. If folds might fail, +/// consider implementing `FallibleTypeFolder` instead (which is a +/// fallible, but otherwise equivalent, trait). +/// +/// # Usage patterns +/// +/// ## Substituting for free variables +/// +/// Most of the time, though, we are not interested in adjust +/// arbitrary types/lifetimes, but rather just free variables (even +/// more often, just free existential variables) that appear within +/// the term. +/// +/// For this reason, the `TypeFolder` trait extends two other traits that +/// contain methods that are invoked when just those particular +/// +/// In particular, folders can intercept references to free variables +/// (either existentially or universally quantified) and replace them +/// with other types/lifetimes as appropriate. +/// +/// To create a folder `F`, one never implements `TypeFolder` directly, but instead +/// implements one of each of these three sub-traits: +/// +/// - `FreeVarFolder` -- folds `BoundVar` instances that appear free +/// in the term being folded (use `DefaultFreeVarFolder` to +/// ignore/forbid these altogether) +/// - `InferenceFolder` -- folds existential `InferenceVar` instances +/// that appear in the term being folded (use +/// `DefaultInferenceFolder` to ignore/forbid these altogether) +/// - `PlaceholderFolder` -- folds universal `Placeholder` instances +/// that appear in the term being folded (use +/// `DefaultPlaceholderFolder` to ignore/forbid these altogether) +/// +/// To **apply** a folder, use the `TypeFoldable::fold_with` method, like so +/// +/// ```rust,ignore +/// let x = x.fold_with(&mut folder, 0); +/// ``` +pub trait TypeFolder<I: Interner>: FallibleTypeFolder<I, Error = Infallible> { + /// Creates a `dyn` value from this folder. Unfortunately, this + /// must be added manually to each impl of TypeFolder; it permits the + /// default implements below to create a `&mut dyn TypeFolder` from + /// `Self` without knowing what `Self` is (by invoking this + /// method). Effectively, this limits impls of `TypeFolder` to types + /// for which we are able to create a dyn value (i.e., not `[T]` + /// types). + fn as_dyn(&mut self) -> &mut dyn TypeFolder<I>; + + /// Top-level callback: invoked for each `Ty<I>` that is + /// encountered when folding. By default, invokes + /// `super_fold_with`, which will in turn invoke the more + /// specialized folding methods below, like `fold_free_var_ty`. + fn fold_ty(&mut self, ty: Ty<I>, outer_binder: DebruijnIndex) -> Ty<I> { + ty.super_fold_with(TypeFolder::as_dyn(self), outer_binder) + } + + /// Top-level callback: invoked for each `Lifetime<I>` that is + /// encountered when folding. By default, invokes + /// `super_fold_with`, which will in turn invoke the more + /// specialized folding methods below, like `fold_free_var_lifetime`. + fn fold_lifetime(&mut self, lifetime: Lifetime<I>, outer_binder: DebruijnIndex) -> Lifetime<I> { + lifetime.super_fold_with(TypeFolder::as_dyn(self), outer_binder) + } + + /// Top-level callback: invoked for each `Const<I>` that is + /// encountered when folding. By default, invokes + /// `super_fold_with`, which will in turn invoke the more + /// specialized folding methods below, like `fold_free_var_const`. + fn fold_const(&mut self, constant: Const<I>, outer_binder: DebruijnIndex) -> Const<I> { + constant.super_fold_with(TypeFolder::as_dyn(self), outer_binder) + } + + /// Invoked for every program clause. By default, recursively folds the goals contents. + fn fold_program_clause( + &mut self, + clause: ProgramClause<I>, + outer_binder: DebruijnIndex, + ) -> ProgramClause<I> { + clause.super_fold_with(TypeFolder::as_dyn(self), outer_binder) + } + + /// Invoked for every goal. By default, recursively folds the goals contents. + fn fold_goal(&mut self, goal: Goal<I>, outer_binder: DebruijnIndex) -> Goal<I> { + goal.super_fold_with(TypeFolder::as_dyn(self), outer_binder) + } + + /// If overridden to return true, then folding will panic if a + /// free variable is encountered. This should be done if free + /// type/lifetime variables are not expected. + fn forbid_free_vars(&self) -> bool { + false + } + + /// Invoked for `TyKind::BoundVar` instances that are not bound + /// within the type being folded over: + /// + /// - `depth` is the depth of the `TyKind::BoundVar`; this has + /// been adjusted to account for binders in scope. + /// - `binders` is the number of binders in scope. + /// + /// This should return a type suitable for a context with + /// `binders` in scope. + fn fold_free_var_ty(&mut self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> Ty<I> { + if TypeFolder::forbid_free_vars(self) { + panic!( + "unexpected free variable with depth `{:?}` with outer binder {:?}", + bound_var, outer_binder + ) + } else { + let bound_var = bound_var.shifted_in_from(outer_binder); + TyKind::<I>::BoundVar(bound_var).intern(TypeFolder::interner(self)) + } + } + + /// As `fold_free_var_ty`, but for lifetimes. + fn fold_free_var_lifetime( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Lifetime<I> { + if TypeFolder::forbid_free_vars(self) { + panic!( + "unexpected free variable with depth `{:?}` with outer binder {:?}", + bound_var, outer_binder + ) + } else { + let bound_var = bound_var.shifted_in_from(outer_binder); + LifetimeData::<I>::BoundVar(bound_var).intern(TypeFolder::interner(self)) + } + } + + /// As `fold_free_var_ty`, but for constants. + fn fold_free_var_const( + &mut self, + ty: Ty<I>, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Const<I> { + if TypeFolder::forbid_free_vars(self) { + panic!( + "unexpected free variable with depth `{:?}` with outer binder {:?}", + bound_var, outer_binder + ) + } else { + let bound_var = bound_var.shifted_in_from(outer_binder); + ConstData { + ty: ty.fold_with(TypeFolder::as_dyn(self), outer_binder), + value: ConstValue::<I>::BoundVar(bound_var), + } + .intern(TypeFolder::interner(self)) + } + } + + /// If overridden to return true, we will panic when a free + /// placeholder type/lifetime/const is encountered. + fn forbid_free_placeholders(&self) -> bool { + false + } + + /// Invoked for each occurrence of a placeholder type; these are + /// used when we instantiate binders universally. Returns a type + /// to use instead, which should be suitably shifted to account + /// for `binders`. + /// + /// - `universe` is the universe of the `TypeName::ForAll` that was found + /// - `binders` is the number of binders in scope + #[allow(unused_variables)] + fn fold_free_placeholder_ty( + &mut self, + universe: PlaceholderIndex, + outer_binder: DebruijnIndex, + ) -> Ty<I> { + if TypeFolder::forbid_free_placeholders(self) { + panic!("unexpected placeholder type `{:?}`", universe) + } else { + universe.to_ty::<I>(TypeFolder::interner(self)) + } + } + + /// As with `fold_free_placeholder_ty`, but for lifetimes. + #[allow(unused_variables)] + fn fold_free_placeholder_lifetime( + &mut self, + universe: PlaceholderIndex, + outer_binder: DebruijnIndex, + ) -> Lifetime<I> { + if TypeFolder::forbid_free_placeholders(self) { + panic!("unexpected placeholder lifetime `{:?}`", universe) + } else { + universe.to_lifetime(TypeFolder::interner(self)) + } + } + + /// As with `fold_free_placeholder_ty`, but for constants. + #[allow(unused_variables)] + fn fold_free_placeholder_const( + &mut self, + ty: Ty<I>, + universe: PlaceholderIndex, + outer_binder: DebruijnIndex, + ) -> Const<I> { + if TypeFolder::forbid_free_placeholders(self) { + panic!("unexpected placeholder const `{:?}`", universe) + } else { + universe.to_const( + TypeFolder::interner(self), + ty.fold_with(TypeFolder::as_dyn(self), outer_binder), + ) + } + } + + /// If overridden to return true, inference variables will trigger + /// panics when folded. Used when inference variables are + /// unexpected. + fn forbid_inference_vars(&self) -> bool { + false + } + + /// Invoked for each occurrence of a inference type; these are + /// used when we instantiate binders universally. Returns a type + /// to use instead, which should be suitably shifted to account + /// for `binders`. + /// + /// - `universe` is the universe of the `TypeName::ForAll` that was found + /// - `binders` is the number of binders in scope + #[allow(unused_variables)] + fn fold_inference_ty( + &mut self, + var: InferenceVar, + kind: TyVariableKind, + outer_binder: DebruijnIndex, + ) -> Ty<I> { + if TypeFolder::forbid_inference_vars(self) { + panic!("unexpected inference type `{:?}`", var) + } else { + var.to_ty(TypeFolder::interner(self), kind) + } + } + + /// As with `fold_inference_ty`, but for lifetimes. + #[allow(unused_variables)] + fn fold_inference_lifetime( + &mut self, + var: InferenceVar, + outer_binder: DebruijnIndex, + ) -> Lifetime<I> { + if TypeFolder::forbid_inference_vars(self) { + panic!("unexpected inference lifetime `'{:?}`", var) + } else { + var.to_lifetime(TypeFolder::interner(self)) + } + } + + /// As with `fold_inference_ty`, but for constants. + #[allow(unused_variables)] + fn fold_inference_const( + &mut self, + ty: Ty<I>, + var: InferenceVar, + outer_binder: DebruijnIndex, + ) -> Const<I> { + if TypeFolder::forbid_inference_vars(self) { + panic!("unexpected inference const `{:?}`", var) + } else { + var.to_const( + TypeFolder::interner(self), + ty.fold_with(TypeFolder::as_dyn(self), outer_binder), + ) + } + } + + /// Gets the interner that is being folded from. + fn interner(&self) -> I; +} + +/// Applies the given `TypeFolder` to a value, producing a folded result +/// of type `Self::Result`. The result type is typically the same as +/// the source type, but in some cases we convert from borrowed +/// to owned as well (e.g., the folder for `&T` will fold to a fresh +/// `T`; well, actually `T::Result`). +pub trait TypeFoldable<I: Interner>: Debug + Sized { + /// Apply the given folder `folder` to `self`; `binders` is the + /// number of binders that are in scope when beginning the + /// folder. Typically `binders` starts as 0, but is adjusted when + /// we encounter `Binders<T>` in the IR or other similar + /// constructs. + fn try_fold_with<E>( + self, + folder: &mut dyn FallibleTypeFolder<I, Error = E>, + outer_binder: DebruijnIndex, + ) -> Result<Self, E>; + + /// A convenient alternative to `try_fold_with` for use with infallible + /// folders. Do not override this method, to ensure coherence with + /// `try_fold_with`. + fn fold_with(self, folder: &mut dyn TypeFolder<I>, outer_binder: DebruijnIndex) -> Self { + self.try_fold_with(FallibleTypeFolder::as_dyn(folder), outer_binder) + .unwrap() + } +} + +/// For types where "fold" invokes a callback on the `TypeFolder`, the +/// `TypeSuperFoldable` trait captures the recursive behavior that folds all +/// the contents of the type. +pub trait TypeSuperFoldable<I: Interner>: TypeFoldable<I> { + /// Recursively folds the value. + fn try_super_fold_with<E>( + self, + folder: &mut dyn FallibleTypeFolder<I, Error = E>, + outer_binder: DebruijnIndex, + ) -> Result<Self, E>; + + /// A convenient alternative to `try_super_fold_with` for use with + /// infallible folders. Do not override this method, to ensure coherence + /// with `try_super_fold_with`. + fn super_fold_with(self, folder: &mut dyn TypeFolder<I>, outer_binder: DebruijnIndex) -> Self { + self.try_super_fold_with(FallibleTypeFolder::as_dyn(folder), outer_binder) + .unwrap() + } +} + +/// "Folding" a type invokes the `try_fold_ty` method on the folder; this +/// usually (in turn) invokes `try_super_fold_ty` to fold the individual +/// parts. +impl<I: Interner> TypeFoldable<I> for Ty<I> { + fn try_fold_with<E>( + self, + folder: &mut dyn FallibleTypeFolder<I, Error = E>, + outer_binder: DebruijnIndex, + ) -> Result<Self, E> { + folder.try_fold_ty(self, outer_binder) + } +} + +/// "Super fold" for a type invokes te more detailed callbacks on the type +impl<I> TypeSuperFoldable<I> for Ty<I> +where + I: Interner, +{ + fn try_super_fold_with<E>( + self, + folder: &mut dyn FallibleTypeFolder<I, Error = E>, + outer_binder: DebruijnIndex, + ) -> Result<Ty<I>, E> { + let interner = folder.interner(); + Ok(match self.kind(interner) { + TyKind::BoundVar(bound_var) => { + if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) { + // This variable was bound outside of the binders + // that we have traversed during folding; + // therefore, it is free. Let the folder have a + // crack at it. + folder.try_fold_free_var_ty(bound_var1, outer_binder)? + } else { + // This variable was bound within the binders that + // we folded over, so just return a bound + // variable. + self + } + } + TyKind::Dyn(clauses) => { + TyKind::Dyn(clauses.clone().try_fold_with(folder, outer_binder)?) + .intern(folder.interner()) + } + TyKind::InferenceVar(var, kind) => { + folder.try_fold_inference_ty(*var, *kind, outer_binder)? + } + TyKind::Placeholder(ui) => folder.try_fold_free_placeholder_ty(*ui, outer_binder)?, + TyKind::Alias(proj) => TyKind::Alias(proj.clone().try_fold_with(folder, outer_binder)?) + .intern(folder.interner()), + TyKind::Function(fun) => { + TyKind::Function(fun.clone().try_fold_with(folder, outer_binder)?) + .intern(folder.interner()) + } + TyKind::Adt(id, substitution) => TyKind::Adt( + id.try_fold_with(folder, outer_binder)?, + substitution.clone().try_fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::AssociatedType(assoc_ty, substitution) => TyKind::AssociatedType( + assoc_ty.try_fold_with(folder, outer_binder)?, + substitution.clone().try_fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Scalar(scalar) => TyKind::Scalar(scalar.try_fold_with(folder, outer_binder)?) + .intern(folder.interner()), + TyKind::Str => TyKind::Str.intern(folder.interner()), + TyKind::Tuple(arity, substitution) => TyKind::Tuple( + *arity, + substitution.clone().try_fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::OpaqueType(opaque_ty, substitution) => TyKind::OpaqueType( + opaque_ty.try_fold_with(folder, outer_binder)?, + substitution.clone().try_fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Slice(substitution) => { + TyKind::Slice(substitution.clone().try_fold_with(folder, outer_binder)?) + .intern(folder.interner()) + } + TyKind::FnDef(fn_def, substitution) => TyKind::FnDef( + fn_def.try_fold_with(folder, outer_binder)?, + substitution.clone().try_fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Ref(mutability, lifetime, ty) => TyKind::Ref( + mutability.try_fold_with(folder, outer_binder)?, + lifetime.clone().try_fold_with(folder, outer_binder)?, + ty.clone().try_fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Raw(mutability, ty) => TyKind::Raw( + mutability.try_fold_with(folder, outer_binder)?, + ty.clone().try_fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Never => TyKind::Never.intern(folder.interner()), + TyKind::Array(ty, const_) => TyKind::Array( + ty.clone().try_fold_with(folder, outer_binder)?, + const_.clone().try_fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Closure(id, substitution) => TyKind::Closure( + id.try_fold_with(folder, outer_binder)?, + substitution.clone().try_fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Generator(id, substitution) => TyKind::Generator( + id.try_fold_with(folder, outer_binder)?, + substitution.clone().try_fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::GeneratorWitness(id, substitution) => TyKind::GeneratorWitness( + id.try_fold_with(folder, outer_binder)?, + substitution.clone().try_fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Foreign(id) => { + TyKind::Foreign(id.try_fold_with(folder, outer_binder)?).intern(folder.interner()) + } + TyKind::Error => TyKind::Error.intern(folder.interner()), + }) + } +} + +/// "Folding" a lifetime invokes the `fold_lifetime` method on the folder; this +/// usually (in turn) invokes `super_fold_lifetime` to fold the individual +/// parts. +impl<I: Interner> TypeFoldable<I> for Lifetime<I> { + fn try_fold_with<E>( + self, + folder: &mut dyn FallibleTypeFolder<I, Error = E>, + outer_binder: DebruijnIndex, + ) -> Result<Self, E> { + folder.try_fold_lifetime(self, outer_binder) + } +} + +impl<I> TypeSuperFoldable<I> for Lifetime<I> +where + I: Interner, +{ + fn try_super_fold_with<E>( + self, + folder: &mut dyn FallibleTypeFolder<I, Error = E>, + outer_binder: DebruijnIndex, + ) -> Result<Lifetime<I>, E> { + let interner = folder.interner(); + match self.data(interner) { + LifetimeData::BoundVar(bound_var) => { + if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) { + // This variable was bound outside of the binders + // that we have traversed during folding; + // therefore, it is free. Let the folder have a + // crack at it. + folder.try_fold_free_var_lifetime(bound_var1, outer_binder) + } else { + // This variable was bound within the binders that + // we folded over, so just return a bound + // variable. + Ok(self) + } + } + LifetimeData::InferenceVar(var) => { + folder.try_fold_inference_lifetime(*var, outer_binder) + } + LifetimeData::Placeholder(universe) => { + folder.try_fold_free_placeholder_lifetime(*universe, outer_binder) + } + LifetimeData::Static => Ok(LifetimeData::<I>::Static.intern(folder.interner())), + LifetimeData::Erased => Ok(LifetimeData::<I>::Erased.intern(folder.interner())), + LifetimeData::Phantom(void, ..) => match *void {}, + } + } +} + +/// "Folding" a const invokes the `fold_const` method on the folder; this +/// usually (in turn) invokes `super_fold_const` to fold the individual +/// parts. +impl<I: Interner> TypeFoldable<I> for Const<I> { + fn try_fold_with<E>( + self, + folder: &mut dyn FallibleTypeFolder<I, Error = E>, + outer_binder: DebruijnIndex, + ) -> Result<Self, E> { + folder.try_fold_const(self, outer_binder) + } +} + +impl<I> TypeSuperFoldable<I> for Const<I> +where + I: Interner, +{ + fn try_super_fold_with<E>( + self, + folder: &mut dyn FallibleTypeFolder<I, Error = E>, + outer_binder: DebruijnIndex, + ) -> Result<Const<I>, E> { + let interner = folder.interner(); + let ConstData { ref ty, ref value } = self.data(interner); + let mut fold_ty = || ty.clone().try_fold_with(folder, outer_binder); + match value { + ConstValue::BoundVar(bound_var) => { + if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) { + folder.try_fold_free_var_const(ty.clone(), bound_var1, outer_binder) + } else { + Ok(self) + } + } + ConstValue::InferenceVar(var) => { + folder.try_fold_inference_const(ty.clone(), *var, outer_binder) + } + ConstValue::Placeholder(universe) => { + folder.try_fold_free_placeholder_const(ty.clone(), *universe, outer_binder) + } + ConstValue::Concrete(ev) => Ok(ConstData { + ty: fold_ty()?, + value: ConstValue::Concrete(ConcreteConst { + interned: ev.interned.clone(), + }), + } + .intern(folder.interner())), + } + } +} + +/// Folding a goal invokes the `fold_goal` callback (which will, by +/// default, invoke super-fold). +impl<I: Interner> TypeFoldable<I> for Goal<I> { + fn try_fold_with<E>( + self, + folder: &mut dyn FallibleTypeFolder<I, Error = E>, + outer_binder: DebruijnIndex, + ) -> Result<Self, E> { + folder.try_fold_goal(self, outer_binder) + } +} + +/// Superfold folds recursively. +impl<I: Interner> TypeSuperFoldable<I> for Goal<I> { + fn try_super_fold_with<E>( + self, + folder: &mut dyn FallibleTypeFolder<I, Error = E>, + outer_binder: DebruijnIndex, + ) -> Result<Self, E> { + let interner = folder.interner(); + Ok(Goal::new( + interner, + self.data(interner) + .clone() + .try_fold_with(folder, outer_binder)?, + )) + } +} + +/// Folding a program clause invokes the `fold_program_clause` +/// callback on the folder (which will, by default, invoke the +/// `super_fold_with` method on the program clause). +impl<I: Interner> TypeFoldable<I> for ProgramClause<I> { + fn try_fold_with<E>( + self, + folder: &mut dyn FallibleTypeFolder<I, Error = E>, + outer_binder: DebruijnIndex, + ) -> Result<Self, E> { + folder.try_fold_program_clause(self, outer_binder) + } +} |