diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:19:03 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:19:03 +0000 |
commit | 64d98f8ee037282c35007b64c2649055c56af1db (patch) | |
tree | 5492bcf97fce41ee1c0b1cc2add283f3e66cdab0 /vendor/chalk-ir | |
parent | Adding debian version 1.67.1+dfsg1-1. (diff) | |
download | rustc-64d98f8ee037282c35007b64c2649055c56af1db.tar.xz rustc-64d98f8ee037282c35007b64c2649055c56af1db.zip |
Merging upstream version 1.68.2+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/chalk-ir')
-rw-r--r-- | vendor/chalk-ir/.cargo-checksum.json | 1 | ||||
-rw-r--r-- | vendor/chalk-ir/Cargo.toml | 37 | ||||
-rw-r--r-- | vendor/chalk-ir/README.md | 3 | ||||
-rw-r--r-- | vendor/chalk-ir/src/cast.rs | 364 | ||||
-rw-r--r-- | vendor/chalk-ir/src/could_match.rs | 213 | ||||
-rw-r--r-- | vendor/chalk-ir/src/debug.rs | 1016 | ||||
-rw-r--r-- | vendor/chalk-ir/src/fold.rs | 920 | ||||
-rw-r--r-- | vendor/chalk-ir/src/fold/binder_impls.rs | 73 | ||||
-rw-r--r-- | vendor/chalk-ir/src/fold/boring_impls.rs | 244 | ||||
-rw-r--r-- | vendor/chalk-ir/src/fold/in_place.rs | 263 | ||||
-rw-r--r-- | vendor/chalk-ir/src/fold/shift.rs | 177 | ||||
-rw-r--r-- | vendor/chalk-ir/src/fold/subst.rs | 118 | ||||
-rw-r--r-- | vendor/chalk-ir/src/interner.rs | 702 | ||||
-rw-r--r-- | vendor/chalk-ir/src/lib.rs | 3055 | ||||
-rw-r--r-- | vendor/chalk-ir/src/visit.rs | 422 | ||||
-rw-r--r-- | vendor/chalk-ir/src/visit/binder_impls.rs | 47 | ||||
-rw-r--r-- | vendor/chalk-ir/src/visit/boring_impls.rs | 261 | ||||
-rw-r--r-- | vendor/chalk-ir/src/visit/visitors.rs | 41 | ||||
-rw-r--r-- | vendor/chalk-ir/src/zip.rs | 543 |
19 files changed, 0 insertions, 8500 deletions
diff --git a/vendor/chalk-ir/.cargo-checksum.json b/vendor/chalk-ir/.cargo-checksum.json deleted file mode 100644 index 7b2915873..000000000 --- a/vendor/chalk-ir/.cargo-checksum.json +++ /dev/null @@ -1 +0,0 @@ -{"files":{"Cargo.toml":"ccde3a8b1652787636f0a34b43eb557bfce1e7e9a92b4634a6f666e512d8d491","README.md":"64cba0ddf3e9b5c168fbe069f1a84c401ce0b33e765ea49acb1345d0923afe8d","src/cast.rs":"b2a6dc2fe33d58df3021d1e83f3823d68a14afff2a484fe0a5c8514290112c17","src/could_match.rs":"a341b8b11615ca738498c722b61695307da170f14754c281fbf2b778d3e82348","src/debug.rs":"63c152c41ae1adcdd1cca725162bef1b42e19307d3b4dfc228d43743d6c6daf2","src/fold.rs":"aa00b9aed253895eb532ba0f89dfb5e971743ea258437cea492c2f90f01c9b23","src/fold/binder_impls.rs":"47ee10eac8081e15148a43e9a1dae32712b0b14d565c9ed5082985abda9302a4","src/fold/boring_impls.rs":"6958c7d0d8315d6864b4d2ec4638544567d6262e1f50fb28df02ac1d57804d90","src/fold/in_place.rs":"83bf2fb5d2b6d8fcd7a2389779329cfc72e83b223eb9dac899635e2deab5a9c9","src/fold/shift.rs":"4119c8e3bb40279ab416ace3bea2137fc917440bb50b37c870c56f9351d508db","src/fold/subst.rs":"6254d62b2bf92d8114384701734a53780119836b0aaf87392dda161ea7b93526","src/interner.rs":"41f5780894b29542db0f7a46386e60f321c527bfd02cbf5be89b45be14a4dc3c","src/lib.rs":"e7fd2eab6a8cae0b0e8bce4b2a0fcb7a67da991755b11d9e9351ba2ec0cf5f87","src/visit.rs":"c914621e2bb77290b3d064cd52d4703ad438daa0c167f8fe0c3fb696a2674b84","src/visit/binder_impls.rs":"9afc460830fd9de249c4120461624432edf715e8661cf28c36e9f2ff47e2a13e","src/visit/boring_impls.rs":"412cdfc9f78edf3a5f6d6ad2f60e21087263c74bca1236420115608333ae9704","src/visit/visitors.rs":"3af422b5179a364483575eec03d68cb277a308508b89a19915f4d76aed9dc696","src/zip.rs":"d86c20f0d44ecf6dae9dae02540d0beb04081a7721337a9dfa3c1b0a4b8cb4f7"},"package":"43aa55deff4e7fbdb09fa014543372f2c95a06835ac487b9ce57b5099b950838"}
\ No newline at end of file diff --git a/vendor/chalk-ir/Cargo.toml b/vendor/chalk-ir/Cargo.toml deleted file mode 100644 index 16e1e83b2..000000000 --- a/vendor/chalk-ir/Cargo.toml +++ /dev/null @@ -1,37 +0,0 @@ -# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO -# -# When uploading crates to the registry Cargo will automatically -# "normalize" Cargo.toml files for maximal compatibility -# with all versions of Cargo and also rewrite `path` dependencies -# to registry (e.g., crates.io) dependencies. -# -# If you are reading this file be aware that the original Cargo.toml -# will likely look very different (and much more reasonable). -# See Cargo.toml.orig for the original contents. - -[package] -edition = "2018" -name = "chalk-ir" -version = "0.87.0" -authors = [ - "Rust Compiler Team", - "Chalk developers", -] -description = "Chalk's internal representation of types, goals, and clauses" -readme = "README.md" -keywords = [ - "compiler", - "traits", - "prolog", -] -license = "MIT OR Apache-2.0" -repository = "https://github.com/rust-lang/chalk" - -[dependencies.bitflags] -version = "1.2.1" - -[dependencies.chalk-derive] -version = "=0.87.0" - -[dependencies.lazy_static] -version = "1.4.0" diff --git a/vendor/chalk-ir/README.md b/vendor/chalk-ir/README.md deleted file mode 100644 index 968ad4937..000000000 --- a/vendor/chalk-ir/README.md +++ /dev/null @@ -1,3 +0,0 @@ -A rust type library for chalk. - -See [Github](https://github.com/rust-lang/chalk) for up-to-date information. diff --git a/vendor/chalk-ir/src/cast.rs b/vendor/chalk-ir/src/cast.rs deleted file mode 100644 index 0c6b682ca..000000000 --- a/vendor/chalk-ir/src/cast.rs +++ /dev/null @@ -1,364 +0,0 @@ -//! Upcasts, to avoid writing out wrapper types. - -use crate::*; -use std::marker::PhantomData; - -/// The `Cast` trait is used to make annoying upcasts between -/// logically equivalent types that imply wrappers. For example, one -/// could convert a `DomainGoal` into a `Goal` by doing: -/// -/// ```ignore -/// let goal: Goal = domain_goal.cast(); -/// ``` -/// -/// This is equivalent to the more explicit: -/// -/// ```ignore -/// let goal: Goal = Goal::DomainGoal(domain_goal) -/// ``` -/// -/// Another useful trick is the `casted()` iterator adapter, which -/// casts each element in the iterator as it is produced (you must -/// have the `Caster` trait in scope for that). -/// -/// # Invariant -/// -/// `Cast` imposes a key invariant. You can only implement `T: -/// Cast<U>` if both `T` and `U` have the same semantic meaning. Also, -/// as part of this, they should always use the same set of free -/// variables (the `Canonical` implementation, for example, relies on -/// that). -/// -/// # Iterators -/// -/// If you import the `Caster` trait, you can also write `.casted()` on an -/// iterator chain to cast every instance within. -/// -/// # Implementing Cast -/// -/// Do not implement `Cast` directly. Instead, implement `CastTo`. -/// This split setup allows us to write `foo.cast::<T>()` to mean -/// "cast to T". -pub trait Cast: Sized { - /// Cast a value to type `U` using `CastTo`. - fn cast<U>(self, interner: U::Interner) -> U - where - Self: CastTo<U>, - U: HasInterner, - { - self.cast_to(interner) - } -} - -impl<T> Cast for T {} - -/// The "helper" trait for `cast` that actually implements the -/// transformations. You can also use this if you want to have -/// functions that take (e.g.) an `impl CastTo<Goal<_>>` or something -/// like that. -pub trait CastTo<T: HasInterner>: Sized { - /// Cast a value to type `T`. - fn cast_to(self, interner: T::Interner) -> T; -} - -macro_rules! reflexive_impl { - (for($($t:tt)*) $u:ty) => { - impl<$($t)*> CastTo<$u> for $u { - fn cast_to(self, _interner: <$u as HasInterner>::Interner) -> $u { - self - } - } - }; - ($u:ty) => { - impl CastTo<$u> for $u { - fn cast_to(self, interner: <$u as HasInterner>::Interner) -> $u { - self - } - } - }; -} - -reflexive_impl!(for(I: Interner) TyKind<I>); -reflexive_impl!(for(I: Interner) LifetimeData<I>); -reflexive_impl!(for(I: Interner) ConstData<I>); -reflexive_impl!(for(I: Interner) TraitRef<I>); -reflexive_impl!(for(I: Interner) DomainGoal<I>); -reflexive_impl!(for(I: Interner) Goal<I>); -reflexive_impl!(for(I: Interner) WhereClause<I>); -reflexive_impl!(for(I: Interner) ProgramClause<I>); -reflexive_impl!(for(I: Interner) QuantifiedWhereClause<I>); -reflexive_impl!(for(I: Interner) VariableKind<I>); -reflexive_impl!(for(I: Interner) VariableKinds<I>); -reflexive_impl!(for(I: Interner) CanonicalVarKind<I>); -reflexive_impl!(for(I: Interner) CanonicalVarKinds<I>); -reflexive_impl!(for(I: Interner) Constraint<I>); - -impl<I: Interner> CastTo<WhereClause<I>> for TraitRef<I> { - fn cast_to(self, _interner: I) -> WhereClause<I> { - WhereClause::Implemented(self) - } -} - -impl<I: Interner> CastTo<WhereClause<I>> for AliasEq<I> { - fn cast_to(self, _interner: I) -> WhereClause<I> { - WhereClause::AliasEq(self) - } -} - -impl<I: Interner> CastTo<WhereClause<I>> for LifetimeOutlives<I> { - fn cast_to(self, _interner: I) -> WhereClause<I> { - WhereClause::LifetimeOutlives(self) - } -} - -impl<I: Interner> CastTo<WhereClause<I>> for TypeOutlives<I> { - fn cast_to(self, _interner: I) -> WhereClause<I> { - WhereClause::TypeOutlives(self) - } -} - -impl<T, I> CastTo<DomainGoal<I>> for T -where - T: CastTo<WhereClause<I>>, - I: Interner, -{ - fn cast_to(self, interner: I) -> DomainGoal<I> { - DomainGoal::Holds(self.cast(interner)) - } -} - -impl<T, I: Interner> CastTo<Goal<I>> for T -where - T: CastTo<DomainGoal<I>>, -{ - fn cast_to(self, interner: I) -> Goal<I> { - GoalData::DomainGoal(self.cast(interner)).intern(interner) - } -} - -impl<I: Interner> CastTo<DomainGoal<I>> for Normalize<I> { - fn cast_to(self, _interner: I) -> DomainGoal<I> { - DomainGoal::Normalize(self) - } -} - -impl<I: Interner> CastTo<DomainGoal<I>> for WellFormed<I> { - fn cast_to(self, _interner: I) -> DomainGoal<I> { - DomainGoal::WellFormed(self) - } -} - -impl<I: Interner> CastTo<DomainGoal<I>> for FromEnv<I> { - fn cast_to(self, _interner: I) -> DomainGoal<I> { - DomainGoal::FromEnv(self) - } -} - -impl<I: Interner> CastTo<Goal<I>> for EqGoal<I> { - fn cast_to(self, interner: I) -> Goal<I> { - GoalData::EqGoal(self).intern(interner) - } -} - -impl<I: Interner> CastTo<Goal<I>> for SubtypeGoal<I> { - fn cast_to(self, interner: I) -> Goal<I> { - GoalData::SubtypeGoal(self).intern(interner) - } -} - -impl<I: Interner, T: HasInterner<Interner = I> + CastTo<Goal<I>>> CastTo<Goal<I>> for Binders<T> { - fn cast_to(self, interner: I) -> Goal<I> { - GoalData::Quantified( - QuantifierKind::ForAll, - self.map(|bound| bound.cast(interner)), - ) - .intern(interner) - } -} - -impl<I: Interner> CastTo<TyKind<I>> for AliasTy<I> { - fn cast_to(self, _interner: I) -> TyKind<I> { - TyKind::Alias(self) - } -} - -impl<I: Interner> CastTo<GenericArg<I>> for Ty<I> { - fn cast_to(self, interner: I) -> GenericArg<I> { - GenericArg::new(interner, GenericArgData::Ty(self)) - } -} - -impl<I: Interner> CastTo<GenericArg<I>> for Lifetime<I> { - fn cast_to(self, interner: I) -> GenericArg<I> { - GenericArg::new(interner, GenericArgData::Lifetime(self)) - } -} - -impl<I: Interner> CastTo<GenericArg<I>> for Const<I> { - fn cast_to(self, interner: I) -> GenericArg<I> { - GenericArg::new(interner, GenericArgData::Const(self)) - } -} - -impl<I: Interner> CastTo<GenericArg<I>> for GenericArg<I> { - fn cast_to(self, _interner: I) -> GenericArg<I> { - self - } -} - -impl<T, I> CastTo<ProgramClause<I>> for T -where - T: CastTo<DomainGoal<I>>, - I: Interner, -{ - fn cast_to(self, interner: I) -> ProgramClause<I> { - let implication = ProgramClauseImplication { - consequence: self.cast(interner), - conditions: Goals::empty(interner), - constraints: Constraints::empty(interner), - priority: ClausePriority::High, - }; - - ProgramClauseData(Binders::empty(interner, implication.shifted_in(interner))) - .intern(interner) - } -} - -impl<I, T> CastTo<ProgramClause<I>> for Binders<T> -where - I: Interner, - T: HasInterner<Interner = I> + CastTo<DomainGoal<I>>, -{ - fn cast_to(self, interner: I) -> ProgramClause<I> { - ProgramClauseData(self.map(|bound| ProgramClauseImplication { - consequence: bound.cast(interner), - conditions: Goals::empty(interner), - constraints: Constraints::empty(interner), - priority: ClausePriority::High, - })) - .intern(interner) - } -} - -impl<T, U> CastTo<Option<U>> for Option<T> -where - T: CastTo<U>, - U: HasInterner, -{ - fn cast_to(self, interner: U::Interner) -> Option<U> { - self.map(|v| v.cast(interner)) - } -} - -impl<T, U, I> CastTo<InEnvironment<U>> for InEnvironment<T> -where - T: HasInterner<Interner = I> + CastTo<U>, - U: HasInterner<Interner = I>, - I: Interner, -{ - fn cast_to(self, interner: U::Interner) -> InEnvironment<U> { - self.map(|v| v.cast(interner)) - } -} - -impl<T, U, E> CastTo<Result<U, E>> for Result<T, E> -where - T: CastTo<U>, - U: HasInterner, -{ - fn cast_to(self, interner: U::Interner) -> Result<U, E> { - self.map(|v| v.cast(interner)) - } -} - -impl<T> HasInterner for Option<T> -where - T: HasInterner, -{ - type Interner = T::Interner; -} - -impl<T, E> HasInterner for Result<T, E> -where - T: HasInterner, -{ - type Interner = T::Interner; -} - -impl<T, U> CastTo<Canonical<U>> for Canonical<T> -where - T: CastTo<U> + HasInterner, - U: HasInterner<Interner = T::Interner>, -{ - fn cast_to(self, interner: T::Interner) -> Canonical<U> { - // Subtle point: It should be ok to re-use the binders here, - // because `cast()` never introduces new inference variables, - // nor changes the "substance" of the type we are working - // with. It just introduces new wrapper types. - Canonical { - value: self.value.cast(interner), - binders: self.binders.cast(interner), - } - } -} - -impl<T, U> CastTo<Vec<U>> for Vec<T> -where - T: CastTo<U> + HasInterner, - U: HasInterner, -{ - fn cast_to(self, interner: U::Interner) -> Vec<U> { - self.into_iter().casted(interner).collect() - } -} - -impl<T> CastTo<T> for &T -where - T: Clone + HasInterner, -{ - fn cast_to(self, _interner: T::Interner) -> T { - self.clone() - } -} - -/// An iterator that casts each element to some other type. -pub struct Casted<IT, U: HasInterner> { - interner: U::Interner, - iterator: IT, - _cast: PhantomData<U>, -} - -impl<IT: Iterator, U> Iterator for Casted<IT, U> -where - IT::Item: CastTo<U>, - U: HasInterner, -{ - type Item = U; - - fn next(&mut self) -> Option<Self::Item> { - self.iterator.next().map(|item| item.cast_to(self.interner)) - } - - fn size_hint(&self) -> (usize, Option<usize>) { - self.iterator.size_hint() - } -} - -/// An iterator adapter that casts each element we are iterating over -/// to some other type. -pub trait Caster: Iterator + Sized { - /// Cast each element in this iterator. - fn casted<U>(self, interner: U::Interner) -> Casted<Self, U> - where - Self::Item: CastTo<U>, - U: HasInterner, - { - Casted { - interner, - iterator: self, - _cast: PhantomData, - } - } -} - -impl<I> Caster for I where I: Iterator {} diff --git a/vendor/chalk-ir/src/could_match.rs b/vendor/chalk-ir/src/could_match.rs deleted file mode 100644 index 9f94ff47a..000000000 --- a/vendor/chalk-ir/src/could_match.rs +++ /dev/null @@ -1,213 +0,0 @@ -//! Fast matching check for zippable values. - -use crate::interner::HasInterner; -use crate::zip::{Zip, Zipper}; -use crate::*; - -/// A fast check to see whether two things could ever possibly match. -pub trait CouldMatch<T: ?Sized + HasInterner> { - /// Checks whether `self` and `other` could possibly match. - fn could_match( - &self, - interner: T::Interner, - db: &dyn UnificationDatabase<T::Interner>, - other: &T, - ) -> bool; -} - -#[allow(unreachable_code, unused_variables)] -impl<T, I> CouldMatch<T> for T -where - T: Zip<I> + ?Sized + HasInterner<Interner = I>, - I: Interner, -{ - fn could_match(&self, interner: I, db: &dyn UnificationDatabase<I>, other: &T) -> bool { - return Zip::zip_with( - &mut MatchZipper { interner, db }, - Variance::Invariant, - self, - other, - ) - .is_ok(); - - struct MatchZipper<'i, I> { - interner: I, - db: &'i dyn UnificationDatabase<I>, - } - - impl<'i, I: Interner> Zipper<I> for MatchZipper<'i, I> { - fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()> { - let interner = self.interner; - let matches = |a: &Substitution<I>, b: &Substitution<I>| { - a.iter(interner) - .zip(b.iter(interner)) - .all(|(p_a, p_b)| p_a.could_match(interner, self.db, p_b)) - }; - let could_match = match (a.kind(interner), b.kind(interner)) { - (TyKind::Adt(id_a, substitution_a), TyKind::Adt(id_b, substitution_b)) => { - id_a == id_b - && self - .zip_substs( - variance, - Some(self.unification_database().adt_variance(*id_a)), - substitution_a.as_slice(interner), - substitution_b.as_slice(interner), - ) - .is_ok() - } - ( - TyKind::AssociatedType(assoc_ty_a, substitution_a), - TyKind::AssociatedType(assoc_ty_b, substitution_b), - ) => assoc_ty_a == assoc_ty_b && matches(substitution_a, substitution_b), - (TyKind::Scalar(scalar_a), TyKind::Scalar(scalar_b)) => scalar_a == scalar_b, - (TyKind::Str, TyKind::Str) => true, - ( - TyKind::Tuple(arity_a, substitution_a), - TyKind::Tuple(arity_b, substitution_b), - ) => arity_a == arity_b && matches(substitution_a, substitution_b), - ( - TyKind::OpaqueType(opaque_ty_a, substitution_a), - TyKind::OpaqueType(opaque_ty_b, substitution_b), - ) => opaque_ty_a == opaque_ty_b && matches(substitution_a, substitution_b), - (TyKind::Slice(ty_a), TyKind::Slice(ty_b)) => { - ty_a.could_match(interner, self.db, ty_b) - } - ( - TyKind::FnDef(fn_def_a, substitution_a), - TyKind::FnDef(fn_def_b, substitution_b), - ) => { - fn_def_a == fn_def_b - && self - .zip_substs( - variance, - Some(self.unification_database().fn_def_variance(*fn_def_a)), - substitution_a.as_slice(interner), - substitution_b.as_slice(interner), - ) - .is_ok() - } - ( - TyKind::Ref(mutability_a, lifetime_a, ty_a), - TyKind::Ref(mutability_b, lifetime_b, ty_b), - ) => { - mutability_a == mutability_b - && lifetime_a.could_match(interner, self.db, lifetime_b) - && ty_a.could_match(interner, self.db, ty_b) - } - (TyKind::Raw(mutability_a, ty_a), TyKind::Raw(mutability_b, ty_b)) => { - mutability_a == mutability_b && ty_a.could_match(interner, self.db, ty_b) - } - (TyKind::Never, TyKind::Never) => true, - (TyKind::Array(ty_a, const_a), TyKind::Array(ty_b, const_b)) => { - ty_a.could_match(interner, self.db, ty_b) - && const_a.could_match(interner, self.db, const_b) - } - ( - TyKind::Closure(id_a, substitution_a), - TyKind::Closure(id_b, substitution_b), - ) => id_a == id_b && matches(substitution_a, substitution_b), - ( - TyKind::Generator(generator_a, substitution_a), - TyKind::Generator(generator_b, substitution_b), - ) => { - generator_a == generator_b - && self - .zip_substs( - variance, - None, - substitution_a.as_slice(interner), - substitution_b.as_slice(interner), - ) - .is_ok() - } - ( - TyKind::GeneratorWitness(generator_a, substitution_a), - TyKind::GeneratorWitness(generator_b, substitution_b), - ) => { - generator_a == generator_b - && self - .zip_substs( - variance, - None, - substitution_a.as_slice(interner), - substitution_b.as_slice(interner), - ) - .is_ok() - } - (TyKind::Foreign(foreign_ty_a), TyKind::Foreign(foreign_ty_b)) => { - foreign_ty_a == foreign_ty_b - } - (TyKind::Error, TyKind::Error) => true, - - _ => true, - }; - - if could_match { - Ok(()) - } else { - Err(NoSolution) - } - } - - fn zip_lifetimes( - &mut self, - variance: Variance, - _: &Lifetime<I>, - _: &Lifetime<I>, - ) -> Fallible<()> { - Ok(()) - } - - fn zip_consts( - &mut self, - variance: Variance, - _: &Const<I>, - _: &Const<I>, - ) -> Fallible<()> { - Ok(()) - } - - fn zip_binders<T>( - &mut self, - variance: Variance, - a: &Binders<T>, - b: &Binders<T>, - ) -> Fallible<()> - where - T: HasInterner + Zip<I>, - { - Zip::zip_with(self, variance, &a.value, &b.value) - } - - fn interner(&self) -> I { - self.interner - } - - fn unification_database(&self) -> &dyn UnificationDatabase<I> { - self.db - } - } - } -} - -impl<I: Interner> CouldMatch<DomainGoal<I>> for ProgramClauseData<I> { - fn could_match( - &self, - interner: I, - db: &dyn UnificationDatabase<I>, - other: &DomainGoal<I>, - ) -> bool { - self.0.value.consequence.could_match(interner, db, other) - } -} - -impl<I: Interner> CouldMatch<DomainGoal<I>> for ProgramClause<I> { - fn could_match( - &self, - interner: I, - db: &dyn UnificationDatabase<I>, - other: &DomainGoal<I>, - ) -> bool { - self.data(interner).could_match(interner, db, other) - } -} diff --git a/vendor/chalk-ir/src/debug.rs b/vendor/chalk-ir/src/debug.rs deleted file mode 100644 index 76d66edf5..000000000 --- a/vendor/chalk-ir/src/debug.rs +++ /dev/null @@ -1,1016 +0,0 @@ -//! Debug impls for types. - -use std::fmt::{self, Debug, Display, Error, Formatter}; - -use super::*; - -/// Wrapper to allow forwarding to `Display::fmt`, `Debug::fmt`, etc. -pub struct Fmt<F>(pub F) -where - F: Fn(&mut fmt::Formatter<'_>) -> fmt::Result; - -impl<F> fmt::Display for Fmt<F> -where - F: Fn(&mut fmt::Formatter<'_>) -> fmt::Result, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - (self.0)(f) - } -} - -impl<I: Interner> Debug for TraitId<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_trait_id(*self, fmt).unwrap_or_else(|| write!(fmt, "TraitId({:?})", self.0)) - } -} - -impl<I: Interner> Debug for AdtId<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_adt_id(*self, fmt).unwrap_or_else(|| write!(fmt, "AdtId({:?})", self.0)) - } -} - -impl<I: Interner> Debug for AssocTypeId<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_assoc_type_id(*self, fmt) - .unwrap_or_else(|| write!(fmt, "AssocTypeId({:?})", self.0)) - } -} - -impl<I: Interner> Debug for FnDefId<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> std::fmt::Result { - I::debug_fn_def_id(*self, fmt).unwrap_or_else(|| write!(fmt, "FnDefId({:?})", self.0)) - } -} - -impl<I: Interner> Debug for ClosureId<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> std::fmt::Result { - I::debug_closure_id(*self, fmt).unwrap_or_else(|| write!(fmt, "ClosureId({:?})", self.0)) - } -} - -impl<I: Interner> Debug for GeneratorId<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> std::fmt::Result { - I::debug_generator_id(*self, fmt) - .unwrap_or_else(|| write!(fmt, "GeneratorId({:?})", self.0)) - } -} - -impl<I: Interner> Debug for ForeignDefId<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> std::fmt::Result { - I::debug_foreign_def_id(*self, fmt) - .unwrap_or_else(|| write!(fmt, "ForeignDefId({:?})", self.0)) - } -} - -impl<I: Interner> Debug for Ty<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_ty(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<I: Interner> Debug for Lifetime<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_lifetime(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<I: Interner> Debug for Const<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_const(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<I: Interner> Debug for ConcreteConst<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "{:?}", self.interned) - } -} - -impl<I: Interner> Debug for GenericArg<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_generic_arg(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<I: Interner> Debug for Goal<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_goal(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<I: Interner> Debug for Goals<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_goals(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<I: Interner> Debug for ProgramClauseImplication<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_program_clause_implication(self, fmt) - .unwrap_or_else(|| write!(fmt, "ProgramClauseImplication(?)")) - } -} - -impl<I: Interner> Debug for ProgramClause<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_program_clause(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<I: Interner> Debug for ProgramClauses<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_program_clauses(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<I: Interner> Debug for Constraints<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_constraints(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<I: Interner> Debug for SeparatorTraitRef<'_, I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_separator_trait_ref(self, fmt) - .unwrap_or_else(|| write!(fmt, "SeparatorTraitRef(?)")) - } -} - -impl<I: Interner> Debug for AliasTy<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_alias(self, fmt).unwrap_or_else(|| write!(fmt, "AliasTy(?)")) - } -} - -impl<I: Interner> Debug for QuantifiedWhereClauses<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_quantified_where_clauses(self, fmt) - .unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<I: Interner> Debug for ProjectionTy<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_projection_ty(self, fmt).unwrap_or_else(|| { - unimplemented!("cannot format ProjectionTy without setting Program in tls") - }) - } -} - -impl<I: Interner> Debug for OpaqueTy<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_opaque_ty(self, fmt).unwrap_or_else(|| { - unimplemented!("cannot format OpaqueTy without setting Program in tls") - }) - } -} - -impl<I: Interner> Display for Substitution<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_substitution(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<I: Interner> Debug for OpaqueTyId<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_opaque_ty_id(*self, fmt).unwrap_or_else(|| write!(fmt, "OpaqueTyId({:?})", self.0)) - } -} - -impl Display for UniverseIndex { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "U{}", self.counter) - } -} - -impl Debug for UniverseIndex { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "U{}", self.counter) - } -} - -impl<I: Interner> Debug for TyData<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - self.kind.fmt(fmt) - } -} - -impl<I: Interner> Debug for TyKind<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match self { - TyKind::BoundVar(db) => write!(fmt, "{:?}", db), - TyKind::Dyn(clauses) => write!(fmt, "{:?}", clauses), - TyKind::InferenceVar(var, TyVariableKind::General) => write!(fmt, "{:?}", var), - TyKind::InferenceVar(var, TyVariableKind::Integer) => write!(fmt, "{:?}i", var), - TyKind::InferenceVar(var, TyVariableKind::Float) => write!(fmt, "{:?}f", var), - TyKind::Alias(alias) => write!(fmt, "{:?}", alias), - TyKind::Placeholder(index) => write!(fmt, "{:?}", index), - TyKind::Function(function) => write!(fmt, "{:?}", function), - TyKind::Adt(id, substitution) => write!(fmt, "{:?}<{:?}>", id, substitution), - TyKind::AssociatedType(assoc_ty, substitution) => { - write!(fmt, "{:?}<{:?}>", assoc_ty, substitution) - } - TyKind::Scalar(scalar) => write!(fmt, "{:?}", scalar), - TyKind::Str => write!(fmt, "Str"), - TyKind::Tuple(arity, substitution) => write!(fmt, "{:?}<{:?}>", arity, substitution), - TyKind::OpaqueType(opaque_ty, substitution) => { - write!(fmt, "!{:?}<{:?}>", opaque_ty, substitution) - } - TyKind::Slice(substitution) => write!(fmt, "{{slice}}<{:?}>", substitution), - TyKind::FnDef(fn_def, substitution) => write!(fmt, "{:?}<{:?}>", fn_def, substitution), - TyKind::Ref(mutability, lifetime, ty) => match mutability { - Mutability::Mut => write!(fmt, "(&{:?} mut {:?})", lifetime, ty), - Mutability::Not => write!(fmt, "(&{:?} {:?})", lifetime, ty), - }, - TyKind::Raw(mutability, ty) => match mutability { - Mutability::Mut => write!(fmt, "(*mut {:?})", ty), - Mutability::Not => write!(fmt, "(*const {:?})", ty), - }, - TyKind::Never => write!(fmt, "Never"), - TyKind::Array(ty, const_) => write!(fmt, "[{:?}; {:?}]", ty, const_), - TyKind::Closure(id, substitution) => { - write!(fmt, "{{closure:{:?}}}<{:?}>", id, substitution) - } - TyKind::Generator(generator, substitution) => { - write!(fmt, "{:?}<{:?}>", generator, substitution) - } - TyKind::GeneratorWitness(witness, substitution) => { - write!(fmt, "{:?}<{:?}>", witness, substitution) - } - TyKind::Foreign(foreign_ty) => write!(fmt, "{:?}", foreign_ty), - TyKind::Error => write!(fmt, "{{error}}"), - } - } -} - -impl Debug for BoundVar { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let BoundVar { debruijn, index } = self; - write!(fmt, "{:?}.{:?}", debruijn, index) - } -} - -impl Debug for DebruijnIndex { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let DebruijnIndex { depth } = self; - write!(fmt, "^{}", depth) - } -} - -impl<I: Interner> Debug for DynTy<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let DynTy { bounds, lifetime } = self; - write!(fmt, "dyn {:?} + {:?}", bounds, lifetime) - } -} - -impl Debug for InferenceVar { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "?{}", self.index) - } -} - -impl<I: Interner> Debug for FnSubst<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "{:?}", self.0) - } -} - -impl<I: Interner> Debug for FnPointer<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - // FIXME -- we should introduce some names or something here - let FnPointer { - num_binders, - substitution, - sig, - } = self; - write!( - fmt, - "{}{:?} for<{}> {:?}", - match sig.safety { - Safety::Unsafe => "unsafe ", - Safety::Safe => "", - }, - sig.abi, - num_binders, - substitution - ) - } -} - -impl<I: Interner> Debug for LifetimeData<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match self { - LifetimeData::BoundVar(db) => write!(fmt, "'{:?}", db), - LifetimeData::InferenceVar(var) => write!(fmt, "'{:?}", var), - LifetimeData::Placeholder(index) => write!(fmt, "'{:?}", index), - LifetimeData::Static => write!(fmt, "'static"), - LifetimeData::Erased => write!(fmt, "'<erased>"), - LifetimeData::Phantom(..) => unreachable!(), - } - } -} - -impl<I: Interner> VariableKinds<I> { - fn debug(&self) -> VariableKindsDebug<'_, I> { - VariableKindsDebug(self) - } - - /// Helper method for debugging variable kinds. - pub fn inner_debug(&self, interner: I) -> VariableKindsInnerDebug<'_, I> { - VariableKindsInnerDebug { - variable_kinds: self, - interner, - } - } -} - -struct VariableKindsDebug<'a, I: Interner>(&'a VariableKinds<I>); - -impl<'a, I: Interner> Debug for VariableKindsDebug<'a, I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_variable_kinds_with_angles(self.0, fmt) - .unwrap_or_else(|| write!(fmt, "{:?}", self.0.interned)) - } -} - -/// Helper struct for showing debug output for `VariableKinds`. -pub struct VariableKindsInnerDebug<'a, I: Interner> { - variable_kinds: &'a VariableKinds<I>, - interner: I, -} - -impl<'a, I: Interner> Debug for VariableKindsInnerDebug<'a, I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - // NB: We print variable kinds as a list delimited by `<>`, - // like `<K1, K2, ..>`. This is because variable kind lists - // are always associated with binders like `forall<type> { - // ... }`. - write!(fmt, "<")?; - for (index, binder) in self.variable_kinds.iter(self.interner).enumerate() { - if index > 0 { - write!(fmt, ", ")?; - } - match binder { - VariableKind::Ty(TyVariableKind::General) => write!(fmt, "type")?, - VariableKind::Ty(TyVariableKind::Integer) => write!(fmt, "integer type")?, - VariableKind::Ty(TyVariableKind::Float) => write!(fmt, "float type")?, - VariableKind::Lifetime => write!(fmt, "lifetime")?, - VariableKind::Const(ty) => write!(fmt, "const: {:?}", ty)?, - } - } - write!(fmt, ">") - } -} - -impl<I: Interner> Debug for ConstData<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match &self.value { - ConstValue::BoundVar(db) => write!(fmt, "{:?}", db), - ConstValue::InferenceVar(var) => write!(fmt, "{:?}", var), - ConstValue::Placeholder(index) => write!(fmt, "{:?}", index), - ConstValue::Concrete(evaluated) => write!(fmt, "{:?}", evaluated), - } - } -} - -impl<I: Interner> Debug for GoalData<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match self { - GoalData::Quantified(qkind, ref subgoal) => write!( - fmt, - "{:?}{:?} {{ {:?} }}", - qkind, - subgoal.binders.debug(), - subgoal.value - ), - GoalData::Implies(ref wc, ref g) => write!(fmt, "if ({:?}) {{ {:?} }}", wc, g), - GoalData::All(ref goals) => write!(fmt, "all{:?}", goals), - GoalData::Not(ref g) => write!(fmt, "not {{ {:?} }}", g), - GoalData::EqGoal(ref wc) => write!(fmt, "{:?}", wc), - GoalData::SubtypeGoal(ref wc) => write!(fmt, "{:?}", wc), - GoalData::DomainGoal(ref wc) => write!(fmt, "{:?}", wc), - GoalData::CannotProve => write!(fmt, r"¯\_(ツ)_/¯"), - } - } -} - -/// Helper struct for showing debug output for `Goals`. -pub struct GoalsDebug<'a, I: Interner> { - goals: &'a Goals<I>, - interner: I, -} - -impl<'a, I: Interner> Debug for GoalsDebug<'a, I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "(")?; - for (goal, index) in self.goals.iter(self.interner).zip(0..) { - if index > 0 { - write!(fmt, ", ")?; - } - write!(fmt, "{:?}", goal)?; - } - write!(fmt, ")")?; - Ok(()) - } -} - -impl<I: Interner> Goals<I> { - /// Show debug output for `Goals`. - pub fn debug(&self, interner: I) -> GoalsDebug<'_, I> { - GoalsDebug { - goals: self, - interner, - } - } -} - -/// Helper struct for showing debug output for `GenericArgData`. -pub struct GenericArgDataInnerDebug<'a, I: Interner>(&'a GenericArgData<I>); - -impl<'a, I: Interner> Debug for GenericArgDataInnerDebug<'a, I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match self.0 { - GenericArgData::Ty(n) => write!(fmt, "{:?}", n), - GenericArgData::Lifetime(n) => write!(fmt, "{:?}", n), - GenericArgData::Const(n) => write!(fmt, "{:?}", n), - } - } -} - -impl<I: Interner> GenericArgData<I> { - /// Helper method for debugging `GenericArgData`. - pub fn inner_debug(&self) -> GenericArgDataInnerDebug<'_, I> { - GenericArgDataInnerDebug(self) - } -} - -/// Helper struct for showing debug output for program clause implications. -pub struct ProgramClauseImplicationDebug<'a, I: Interner> { - pci: &'a ProgramClauseImplication<I>, - interner: I, -} - -impl<'a, I: Interner> Debug for ProgramClauseImplicationDebug<'a, I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let ProgramClauseImplicationDebug { pci, interner } = self; - write!(fmt, "{:?}", pci.consequence)?; - - let conditions = pci.conditions.as_slice(*interner); - - let conds = conditions.len(); - if conds == 0 { - return Ok(()); - } - - write!(fmt, " :- ")?; - for cond in &conditions[..conds - 1] { - write!(fmt, "{:?}, ", cond)?; - } - write!(fmt, "{:?}", conditions[conds - 1]) - } -} - -impl<I: Interner> ProgramClauseImplication<I> { - /// Show debug output for the program clause implication. - pub fn debug(&self, interner: I) -> ProgramClauseImplicationDebug<'_, I> { - ProgramClauseImplicationDebug { - pci: self, - interner, - } - } -} - -/// Helper struct for showing debug output for application types. -pub struct TyKindDebug<'a, I: Interner> { - ty: &'a TyKind<I>, - interner: I, -} - -impl<'a, I: Interner> Debug for TyKindDebug<'a, I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let interner = self.interner; - match self.ty { - TyKind::BoundVar(db) => write!(fmt, "{:?}", db), - TyKind::Dyn(clauses) => write!(fmt, "{:?}", clauses), - TyKind::InferenceVar(var, TyVariableKind::General) => write!(fmt, "{:?}", var), - TyKind::InferenceVar(var, TyVariableKind::Integer) => write!(fmt, "{:?}i", var), - TyKind::InferenceVar(var, TyVariableKind::Float) => write!(fmt, "{:?}f", var), - TyKind::Alias(alias) => write!(fmt, "{:?}", alias), - TyKind::Placeholder(index) => write!(fmt, "{:?}", index), - TyKind::Function(function) => write!(fmt, "{:?}", function), - TyKind::Adt(id, substitution) => { - write!(fmt, "{:?}{:?}", id, substitution.with_angle(interner)) - } - TyKind::AssociatedType(assoc_ty, substitution) => { - write!(fmt, "{:?}{:?}", assoc_ty, substitution.with_angle(interner)) - } - TyKind::Scalar(scalar) => write!(fmt, "{:?}", scalar), - TyKind::Str => write!(fmt, "Str"), - TyKind::Tuple(arity, substitution) => { - write!(fmt, "{:?}{:?}", arity, substitution.with_angle(interner)) - } - TyKind::OpaqueType(opaque_ty, substitution) => write!( - fmt, - "!{:?}{:?}", - opaque_ty, - substitution.with_angle(interner) - ), - TyKind::Slice(ty) => write!(fmt, "[{:?}]", ty), - TyKind::FnDef(fn_def, substitution) => { - write!(fmt, "{:?}{:?}", fn_def, substitution.with_angle(interner)) - } - TyKind::Ref(mutability, lifetime, ty) => match mutability { - Mutability::Mut => write!(fmt, "(&{:?} mut {:?})", lifetime, ty), - Mutability::Not => write!(fmt, "(&{:?} {:?})", lifetime, ty), - }, - TyKind::Raw(mutability, ty) => match mutability { - Mutability::Mut => write!(fmt, "(*mut {:?})", ty), - Mutability::Not => write!(fmt, "(*const {:?})", ty), - }, - TyKind::Never => write!(fmt, "Never"), - TyKind::Array(ty, const_) => write!(fmt, "[{:?}; {:?}]", ty, const_), - TyKind::Closure(id, substitution) => write!( - fmt, - "{{closure:{:?}}}{:?}", - id, - substitution.with_angle(interner) - ), - TyKind::Generator(generator, substitution) => write!( - fmt, - "{:?}{:?}", - generator, - substitution.with_angle(interner) - ), - TyKind::GeneratorWitness(witness, substitution) => { - write!(fmt, "{:?}{:?}", witness, substitution.with_angle(interner)) - } - TyKind::Foreign(foreign_ty) => write!(fmt, "{:?}", foreign_ty,), - TyKind::Error => write!(fmt, "{{error}}"), - } - } -} - -impl<I: Interner> TyKind<I> { - /// Show debug output for the application type. - pub fn debug(&self, interner: I) -> TyKindDebug<'_, I> { - TyKindDebug { ty: self, interner } - } -} - -/// Helper struct for showing debug output for substitutions. -pub struct SubstitutionDebug<'a, I: Interner> { - substitution: &'a Substitution<I>, - interner: I, -} - -impl<'a, I: Interner> Debug for SubstitutionDebug<'a, I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let SubstitutionDebug { - substitution, - interner, - } = self; - let mut first = true; - - write!(fmt, "[")?; - - for (index, value) in substitution.iter(*interner).enumerate() { - if first { - first = false; - } else { - write!(fmt, ", ")?; - } - - write!(fmt, "?{} := {:?}", index, value)?; - } - - write!(fmt, "]")?; - - Ok(()) - } -} - -impl<I: Interner> Substitution<I> { - /// Show debug output for the substitution. - pub fn debug(&self, interner: I) -> SubstitutionDebug<'_, I> { - SubstitutionDebug { - substitution: self, - interner, - } - } -} - -impl Debug for PlaceholderIndex { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let PlaceholderIndex { ui, idx } = self; - write!(fmt, "!{}_{}", ui.counter, idx) - } -} - -impl<I: Interner> TraitRef<I> { - /// Returns a "Debuggable" type that prints like `P0 as Trait<P1..>`. - pub fn with_as(&self) -> impl std::fmt::Debug + '_ { - SeparatorTraitRef { - trait_ref: self, - separator: " as ", - } - } - - /// Returns a "Debuggable" type that prints like `P0: Trait<P1..>`. - pub fn with_colon(&self) -> impl std::fmt::Debug + '_ { - SeparatorTraitRef { - trait_ref: self, - separator: ": ", - } - } -} - -impl<I: Interner> Debug for TraitRef<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - Debug::fmt(&self.with_as(), fmt) - } -} - -/// Trait ref with associated separator used for debug output. -pub struct SeparatorTraitRef<'me, I: Interner> { - /// The `TraitRef` itself. - pub trait_ref: &'me TraitRef<I>, - - /// The separator used for displaying the `TraitRef`. - pub separator: &'me str, -} - -/// Helper struct for showing debug output for the `SeperatorTraitRef`. -pub struct SeparatorTraitRefDebug<'a, 'me, I: Interner> { - separator_trait_ref: &'a SeparatorTraitRef<'me, I>, - interner: I, -} - -impl<'a, 'me, I: Interner> Debug for SeparatorTraitRefDebug<'a, 'me, I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let SeparatorTraitRefDebug { - separator_trait_ref, - interner, - } = self; - let parameters = separator_trait_ref - .trait_ref - .substitution - .as_slice(*interner); - write!( - fmt, - "{:?}{}{:?}{:?}", - parameters[0], - separator_trait_ref.separator, - separator_trait_ref.trait_ref.trait_id, - Angle(¶meters[1..]) - ) - } -} - -impl<'me, I: Interner> SeparatorTraitRef<'me, I> { - /// Show debug output for the `SeperatorTraitRef`. - pub fn debug<'a>(&'a self, interner: I) -> SeparatorTraitRefDebug<'a, 'me, I> { - SeparatorTraitRefDebug { - separator_trait_ref: self, - interner, - } - } -} - -impl<I: Interner> Debug for LifetimeOutlives<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "{:?}: {:?}", self.a, self.b) - } -} - -impl<I: Interner> Debug for TypeOutlives<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "{:?}: {:?}", self.ty, self.lifetime) - } -} - -/// Helper struct for showing debug output for projection types. -pub struct ProjectionTyDebug<'a, I: Interner> { - projection_ty: &'a ProjectionTy<I>, - interner: I, -} - -impl<'a, I: Interner> Debug for ProjectionTyDebug<'a, I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let ProjectionTyDebug { - projection_ty, - interner, - } = self; - write!( - fmt, - "({:?}){:?}", - projection_ty.associated_ty_id, - projection_ty.substitution.with_angle(*interner) - ) - } -} - -impl<I: Interner> ProjectionTy<I> { - /// Show debug output for the projection type. - pub fn debug(&self, interner: I) -> ProjectionTyDebug<'_, I> { - ProjectionTyDebug { - projection_ty: self, - interner, - } - } -} - -/// Helper struct for showing debug output for opaque types. -pub struct OpaqueTyDebug<'a, I: Interner> { - opaque_ty: &'a OpaqueTy<I>, - interner: I, -} - -impl<'a, I: Interner> Debug for OpaqueTyDebug<'a, I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let OpaqueTyDebug { - opaque_ty, - interner, - } = self; - write!( - fmt, - "{:?}{:?}", - opaque_ty.opaque_ty_id, - opaque_ty.substitution.with_angle(*interner) - ) - } -} - -impl<I: Interner> OpaqueTy<I> { - /// Show debug output for the opaque type. - pub fn debug(&self, interner: I) -> OpaqueTyDebug<'_, I> { - OpaqueTyDebug { - opaque_ty: self, - interner, - } - } -} - -/// Wraps debug output in angle brackets (`<>`). -pub struct Angle<'a, T>(pub &'a [T]); - -impl<'a, T: Debug> Debug for Angle<'a, T> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - if !self.0.is_empty() { - write!(fmt, "<")?; - for (index, elem) in self.0.iter().enumerate() { - if index > 0 { - write!(fmt, ", {:?}", elem)?; - } else { - write!(fmt, "{:?}", elem)?; - } - } - write!(fmt, ">")?; - } - Ok(()) - } -} - -impl<I: Interner> Debug for Normalize<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "Normalize({:?} -> {:?})", self.alias, self.ty) - } -} - -impl<I: Interner> Debug for AliasEq<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "AliasEq({:?} = {:?})", self.alias, self.ty) - } -} - -impl<I: Interner> Debug for WhereClause<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match self { - WhereClause::Implemented(tr) => write!(fmt, "Implemented({:?})", tr.with_colon()), - WhereClause::AliasEq(a) => write!(fmt, "{:?}", a), - WhereClause::LifetimeOutlives(l_o) => write!(fmt, "{:?}", l_o), - WhereClause::TypeOutlives(t_o) => write!(fmt, "{:?}", t_o), - } - } -} - -impl<I: Interner> Debug for FromEnv<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match self { - FromEnv::Trait(t) => write!(fmt, "FromEnv({:?})", t.with_colon()), - FromEnv::Ty(t) => write!(fmt, "FromEnv({:?})", t), - } - } -} - -impl<I: Interner> Debug for WellFormed<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match self { - WellFormed::Trait(t) => write!(fmt, "WellFormed({:?})", t.with_colon()), - WellFormed::Ty(t) => write!(fmt, "WellFormed({:?})", t), - } - } -} - -impl<I: Interner> Debug for DomainGoal<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match self { - DomainGoal::Holds(n) => write!(fmt, "{:?}", n), - DomainGoal::WellFormed(n) => write!(fmt, "{:?}", n), - DomainGoal::FromEnv(n) => write!(fmt, "{:?}", n), - DomainGoal::Normalize(n) => write!(fmt, "{:?}", n), - DomainGoal::IsLocal(n) => write!(fmt, "IsLocal({:?})", n), - DomainGoal::IsUpstream(n) => write!(fmt, "IsUpstream({:?})", n), - DomainGoal::IsFullyVisible(n) => write!(fmt, "IsFullyVisible({:?})", n), - DomainGoal::LocalImplAllowed(tr) => { - write!(fmt, "LocalImplAllowed({:?})", tr.with_colon(),) - } - DomainGoal::Compatible => write!(fmt, "Compatible"), - DomainGoal::DownstreamType(n) => write!(fmt, "DownstreamType({:?})", n), - DomainGoal::Reveal => write!(fmt, "Reveal"), - DomainGoal::ObjectSafe(n) => write!(fmt, "ObjectSafe({:?})", n), - } - } -} - -impl<I: Interner> Debug for EqGoal<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "({:?} = {:?})", self.a, self.b) - } -} - -impl<I: Interner> Debug for SubtypeGoal<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "({:?} <: {:?})", self.a, self.b) - } -} - -impl<T: HasInterner + Debug> Debug for Binders<T> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let Binders { - ref binders, - ref value, - } = *self; - write!(fmt, "for{:?} ", binders.debug())?; - Debug::fmt(value, fmt) - } -} - -impl<I: Interner> Debug for ProgramClauseData<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "{:?}", self.0) - } -} - -impl<I: Interner> Debug for Environment<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - write!(fmt, "Env({:?})", self.clauses) - } -} - -impl<I: Interner> Debug for CanonicalVarKinds<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_canonical_var_kinds(self, fmt) - .unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} - -impl<T: HasInterner + Display> Canonical<T> { - /// Display the canonicalized item. - pub fn display(&self, interner: T::Interner) -> CanonicalDisplay<'_, T> { - CanonicalDisplay { - canonical: self, - interner, - } - } -} - -/// Helper struct for displaying canonicalized items. -pub struct CanonicalDisplay<'a, T: HasInterner> { - canonical: &'a Canonical<T>, - interner: T::Interner, -} - -impl<'a, T: HasInterner + Display> Display for CanonicalDisplay<'a, T> { - fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> { - let Canonical { binders, value } = self.canonical; - let interner = self.interner; - let binders = binders.as_slice(interner); - if binders.is_empty() { - // Ordinarily, we try to print all binder levels, if they - // are empty, but we can skip in this *particular* case - // because we know that `Canonical` terms are never - // supposed to contain free variables. In other words, - // all "bound variables" that appear inside the canonical - // value must reference values that appear in `binders`. - write!(f, "{}", value)?; - } else { - write!(f, "for<")?; - - for (i, pk) in binders.iter().enumerate() { - if i > 0 { - write!(f, ",")?; - } - write!(f, "?{}", pk.skip_kind())?; - } - - write!(f, "> {{ {} }}", value)?; - } - - Ok(()) - } -} - -impl<I: Interner> Debug for GenericArgData<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match self { - GenericArgData::Ty(t) => write!(fmt, "Ty({:?})", t), - GenericArgData::Lifetime(l) => write!(fmt, "Lifetime({:?})", l), - GenericArgData::Const(c) => write!(fmt, "Const({:?})", c), - } - } -} - -impl<I: Interner> Debug for VariableKind<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match self { - VariableKind::Ty(TyVariableKind::General) => write!(fmt, "type"), - VariableKind::Ty(TyVariableKind::Integer) => write!(fmt, "integer type"), - VariableKind::Ty(TyVariableKind::Float) => write!(fmt, "float type"), - VariableKind::Lifetime => write!(fmt, "lifetime"), - VariableKind::Const(ty) => write!(fmt, "const: {:?}", ty), - } - } -} - -impl<I: Interner, T: Debug> Debug for WithKind<I, T> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - let value = self.skip_kind(); - match &self.kind { - VariableKind::Ty(TyVariableKind::General) => write!(fmt, "{:?} with kind type", value), - VariableKind::Ty(TyVariableKind::Integer) => { - write!(fmt, "{:?} with kind integer type", value) - } - VariableKind::Ty(TyVariableKind::Float) => { - write!(fmt, "{:?} with kind float type", value) - } - VariableKind::Lifetime => write!(fmt, "{:?} with kind lifetime", value), - VariableKind::Const(ty) => write!(fmt, "{:?} with kind {:?}", value, ty), - } - } -} - -impl<I: Interner> Debug for Constraint<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - match self { - Constraint::LifetimeOutlives(a, b) => write!(fmt, "{:?}: {:?}", a, b), - Constraint::TypeOutlives(ty, lifetime) => write!(fmt, "{:?}: {:?}", ty, lifetime), - } - } -} - -impl<I: Interner> Display for ConstrainedSubst<I> { - #[rustfmt::skip] - fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> { - let ConstrainedSubst { subst, constraints } = self; - - let mut first = true; - - let subst = format!("{}", Fmt(|f| Display::fmt(subst, f))); - if subst != "[]" { - write!(f, "substitution {}", subst)?; - first = false; - } - - let constraints = format!("{}", Fmt(|f| Debug::fmt(constraints, f))); - if constraints != "[]" { - if !first { write!(f, ", ")?; } - write!(f, "lifetime constraints {}", constraints)?; - first = false; - } - - let _ = first; - Ok(()) - } -} - -impl<I: Interner> Substitution<I> { - /// Displays the substitution in the form `< P0, .. Pn >`, or (if - /// the substitution is empty) as an empty string. - pub fn with_angle(&self, interner: I) -> Angle<'_, GenericArg<I>> { - Angle(self.as_slice(interner)) - } -} - -impl<I: Interner> Debug for Substitution<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - Display::fmt(self, fmt) - } -} - -impl<I: Interner> Debug for Variances<I> { - fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { - I::debug_variances(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) - } -} diff --git a/vendor/chalk-ir/src/fold.rs b/vendor/chalk-ir/src/fold.rs deleted file mode 100644 index b15cbff7a..000000000 --- a/vendor/chalk-ir/src/fold.rs +++ /dev/null @@ -1,920 +0,0 @@ -//! 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) - } -} diff --git a/vendor/chalk-ir/src/fold/binder_impls.rs b/vendor/chalk-ir/src/fold/binder_impls.rs deleted file mode 100644 index 1f44c1629..000000000 --- a/vendor/chalk-ir/src/fold/binder_impls.rs +++ /dev/null @@ -1,73 +0,0 @@ -//! This module contains impls of `TypeFoldable` for those types that -//! introduce binders. -//! -//! The more interesting impls of `TypeFoldable` remain in the `fold` module. - -use crate::*; - -impl<I: Interner> TypeFoldable<I> for FnPointer<I> { - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - let FnPointer { - num_binders, - substitution, - sig, - } = self; - Ok(FnPointer { - num_binders, - substitution: substitution.try_fold_with(folder, outer_binder.shifted_in())?, - sig: FnSig { - abi: sig.abi, - safety: sig.safety, - variadic: sig.variadic, - }, - }) - } -} - -impl<T, I: Interner> TypeFoldable<I> for Binders<T> -where - T: HasInterner<Interner = I> + TypeFoldable<I>, - I: Interner, -{ - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - let Binders { - binders: self_binders, - value: self_value, - } = self; - let value = self_value.try_fold_with(folder, outer_binder.shifted_in())?; - let binders = VariableKinds { - interned: self_binders.interned().clone(), - }; - Ok(Binders::new(binders, value)) - } -} - -impl<I, T> TypeFoldable<I> for Canonical<T> -where - I: Interner, - T: HasInterner<Interner = I> + TypeFoldable<I>, -{ - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - let Canonical { - binders: self_binders, - value: self_value, - } = self; - let value = self_value.try_fold_with(folder, outer_binder.shifted_in())?; - let binders = CanonicalVarKinds { - interned: self_binders.interned().clone(), - }; - Ok(Canonical { binders, value }) - } -} diff --git a/vendor/chalk-ir/src/fold/boring_impls.rs b/vendor/chalk-ir/src/fold/boring_impls.rs deleted file mode 100644 index fb4e3e30b..000000000 --- a/vendor/chalk-ir/src/fold/boring_impls.rs +++ /dev/null @@ -1,244 +0,0 @@ -//! This module contains "rote and uninteresting" impls of `TypeFoldable` for -//! various types. In general, we prefer to derive `TypeFoldable`, but -//! sometimes that doesn't work for whatever reason. -//! -//! The more interesting impls of `TypeFoldable` remain in the `fold` module. - -use super::in_place; -use crate::*; -use std::marker::PhantomData; - -impl<T: TypeFoldable<I>, I: Interner> TypeFoldable<I> for Vec<T> { - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - in_place::fallible_map_vec(self, |e| e.try_fold_with(folder, outer_binder)) - } -} - -impl<T: TypeFoldable<I>, I: Interner> TypeFoldable<I> for Box<T> { - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - in_place::fallible_map_box(self, |e| e.try_fold_with(folder, outer_binder)) - } -} - -macro_rules! tuple_fold { - ($($n:ident),*) => { - impl<$($n: TypeFoldable<I>,)* I: Interner> TypeFoldable<I> for ($($n,)*) { - fn try_fold_with<Error>(self, folder: &mut dyn FallibleTypeFolder<I, Error = Error>, outer_binder: DebruijnIndex) -> Result<Self, Error> - { - #[allow(non_snake_case)] - let ($($n),*) = self; - Ok(($($n.try_fold_with(folder, outer_binder)?,)*)) - } - } - } -} - -tuple_fold!(A, B); -tuple_fold!(A, B, C); -tuple_fold!(A, B, C, D); -tuple_fold!(A, B, C, D, E); - -impl<T: TypeFoldable<I>, I: Interner> TypeFoldable<I> for Option<T> { - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - match self { - None => Ok(None), - Some(e) => Ok(Some(e.try_fold_with(folder, outer_binder)?)), - } - } -} - -impl<I: Interner> TypeFoldable<I> for GenericArg<I> { - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - let interner = folder.interner(); - - let data = self - .data(interner) - .clone() - .try_fold_with(folder, outer_binder)?; - Ok(GenericArg::new(interner, data)) - } -} - -impl<I: Interner> TypeFoldable<I> for Substitution<I> { - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - let interner = folder.interner(); - - let folded = self - .iter(interner) - .cloned() - .map(|p| p.try_fold_with(folder, outer_binder)); - Substitution::from_fallible(interner, folded) - } -} - -impl<I: Interner> TypeFoldable<I> for Goals<I> { - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - let interner = folder.interner(); - let folded = self - .iter(interner) - .cloned() - .map(|p| p.try_fold_with(folder, outer_binder)); - Goals::from_fallible(interner, folded) - } -} - -impl<I: Interner> TypeFoldable<I> for ProgramClauses<I> { - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - let interner = folder.interner(); - let folded = self - .iter(interner) - .cloned() - .map(|p| p.try_fold_with(folder, outer_binder)); - ProgramClauses::from_fallible(interner, folded) - } -} - -impl<I: Interner> TypeFoldable<I> for QuantifiedWhereClauses<I> { - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - let interner = folder.interner(); - let folded = self - .iter(interner) - .cloned() - .map(|p| p.try_fold_with(folder, outer_binder)); - QuantifiedWhereClauses::from_fallible(interner, folded) - } -} - -impl<I: Interner> TypeFoldable<I> for Constraints<I> { - fn try_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> Result<Self, E> { - let interner = folder.interner(); - let folded = self - .iter(interner) - .cloned() - .map(|p| p.try_fold_with(folder, outer_binder)); - Constraints::from_fallible(interner, folded) - } -} - -#[doc(hidden)] -#[macro_export] -macro_rules! copy_fold { - ($t:ty) => { - impl<I: Interner> $crate::fold::TypeFoldable<I> for $t { - fn try_fold_with<E>( - self, - _folder: &mut dyn ($crate::fold::FallibleTypeFolder<I, Error = E>), - _outer_binder: DebruijnIndex, - ) -> ::std::result::Result<Self, E> { - Ok(self) - } - } - }; -} - -copy_fold!(bool); -copy_fold!(usize); -copy_fold!(UniverseIndex); -copy_fold!(PlaceholderIndex); -copy_fold!(QuantifierKind); -copy_fold!(DebruijnIndex); -copy_fold!(()); -copy_fold!(UintTy); -copy_fold!(IntTy); -copy_fold!(FloatTy); -copy_fold!(Scalar); -copy_fold!(ClausePriority); -copy_fold!(Mutability); -copy_fold!(Safety); - -#[doc(hidden)] -#[macro_export] -macro_rules! id_fold { - ($t:ident) => { - impl<I: Interner> $crate::fold::TypeFoldable<I> for $t<I> { - fn try_fold_with<E>( - self, - _folder: &mut dyn ($crate::fold::FallibleTypeFolder<I, Error = E>), - _outer_binder: DebruijnIndex, - ) -> ::std::result::Result<Self, E> { - Ok(self) - } - } - }; -} - -id_fold!(ImplId); -id_fold!(AdtId); -id_fold!(TraitId); -id_fold!(AssocTypeId); -id_fold!(OpaqueTyId); -id_fold!(FnDefId); -id_fold!(ClosureId); -id_fold!(GeneratorId); -id_fold!(ForeignDefId); - -impl<I: Interner> TypeSuperFoldable<I> for ProgramClauseData<I> { - fn try_super_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> ::std::result::Result<Self, E> { - Ok(ProgramClauseData( - self.0.try_fold_with(folder, outer_binder)?, - )) - } -} - -impl<I: Interner> TypeSuperFoldable<I> for ProgramClause<I> { - fn try_super_fold_with<E>( - self, - folder: &mut dyn FallibleTypeFolder<I, Error = E>, - outer_binder: DebruijnIndex, - ) -> ::std::result::Result<Self, E> { - let clause = self.data(folder.interner()).clone(); - Ok(clause - .try_super_fold_with(folder, outer_binder)? - .intern(folder.interner())) - } -} - -impl<I: Interner> TypeFoldable<I> for PhantomData<I> { - fn try_fold_with<E>( - self, - _folder: &mut dyn FallibleTypeFolder<I, Error = E>, - _outer_binder: DebruijnIndex, - ) -> ::std::result::Result<Self, E> { - Ok(PhantomData) - } -} diff --git a/vendor/chalk-ir/src/fold/in_place.rs b/vendor/chalk-ir/src/fold/in_place.rs deleted file mode 100644 index 263da617d..000000000 --- a/vendor/chalk-ir/src/fold/in_place.rs +++ /dev/null @@ -1,263 +0,0 @@ -//! Subroutines to help implementers of `TypeFoldable` avoid unnecessary heap allocations. - -use std::marker::PhantomData; -use std::{mem, ptr}; - -fn is_zst<T>() -> bool { - mem::size_of::<T>() == 0 -} - -fn is_layout_identical<T, U>() -> bool { - mem::size_of::<T>() == mem::size_of::<U>() && mem::align_of::<T>() == mem::align_of::<U>() -} - -/// Maps a `Box<T>` to a `Box<U>`, reusing the underlying storage if possible. -pub(super) fn fallible_map_box<T, U, E>( - b: Box<T>, - map: impl FnOnce(T) -> Result<U, E>, -) -> Result<Box<U>, E> { - // This optimization is only valid when `T` and `U` have the same size/alignment and is not - // useful for ZSTs. - if !is_layout_identical::<T, U>() || is_zst::<T>() { - return map(*b).map(Box::new); - } - - let raw = Box::into_raw(b); - unsafe { - let val = ptr::read(raw); - - // Box<T> -> Box<MaybeUninit<U>> - let mut raw: Box<mem::MaybeUninit<U>> = Box::from_raw(raw.cast()); - - // If `map` panics or returns an error, `raw` will free the memory associated with `b`, but - // not drop the boxed value itself since it is wrapped in `MaybeUninit`. This is what we - // want since the boxed value was moved into `map`. - let mapped_val = map(val)?; - ptr::write(raw.as_mut_ptr(), mapped_val); - - // Box<MaybeUninit<U>> -> Box<U> - Ok(Box::from_raw(Box::into_raw(raw).cast())) - } -} - -/// Maps a `Vec<T>` to a `Vec<U>`, reusing the underlying storage if possible. -pub(super) fn fallible_map_vec<T, U, E>( - vec: Vec<T>, - mut map: impl FnMut(T) -> Result<U, E>, -) -> Result<Vec<U>, E> { - // This optimization is only valid when `T` and `U` have the same size/alignment and is not - // useful for ZSTs. - if !is_layout_identical::<T, U>() || is_zst::<T>() { - return vec.into_iter().map(map).collect(); - } - - let mut vec = VecMappedInPlace::<T, U>::new(vec); - - unsafe { - for i in 0..vec.len { - let place = vec.ptr.add(i); - let val = ptr::read(place); - - // Set `map_in_progress` so the drop impl for `VecMappedInPlace` can handle the other - // elements correctly in case `map` panics or returns an error. - vec.map_in_progress = i; - let mapped_val = map(val)?; - - ptr::write(place as *mut U, mapped_val); - } - - Ok(vec.finish()) - } -} - -/// Takes ownership of a `Vec` that is being mapped in place, cleaning up if the map fails. -struct VecMappedInPlace<T, U> { - ptr: *mut T, - len: usize, - cap: usize, - - map_in_progress: usize, - _elem_tys: PhantomData<(T, U)>, -} - -impl<T, U> VecMappedInPlace<T, U> { - fn new(mut vec: Vec<T>) -> Self { - assert!(is_layout_identical::<T, U>()); - - // FIXME: This is just `Vec::into_raw_parts`. Use that instead when it is stabilized. - let ptr = vec.as_mut_ptr(); - let len = vec.len(); - let cap = vec.capacity(); - mem::forget(vec); - - VecMappedInPlace { - ptr, - len, - cap, - - map_in_progress: 0, - _elem_tys: PhantomData, - } - } - - /// Converts back into a `Vec` once the map is complete. - unsafe fn finish(self) -> Vec<U> { - let this = mem::ManuallyDrop::new(self); - Vec::from_raw_parts(this.ptr as *mut U, this.len, this.cap) - } -} - -/// `VecMappedInPlace` drops everything but the element that was passed to `map` when it panicked or -/// returned an error. Everything before that index in the vector has type `U` (it has been mapped) -/// and everything after it has type `T` (it has not been mapped). -/// -/// ```text -/// mapped -/// | not yet mapped -/// |----| |-----| -/// [UUUU UxTT TTTT] -/// ^ -/// `map_in_progress` (not dropped) -/// ``` -impl<T, U> Drop for VecMappedInPlace<T, U> { - fn drop(&mut self) { - // Drop mapped elements of type `U`. - for i in 0..self.map_in_progress { - unsafe { - ptr::drop_in_place(self.ptr.add(i) as *mut U); - } - } - - // Drop unmapped elements of type `T`. - for i in (self.map_in_progress + 1)..self.len { - unsafe { - ptr::drop_in_place(self.ptr.add(i)); - } - } - - // Free the underlying storage for the `Vec`. - // `len` is 0 because the elements were handled above. - unsafe { - Vec::from_raw_parts(self.ptr, 0, self.cap); - } - } -} - -#[cfg(test)] -mod tests { - use std::fmt; - use std::sync::{Arc, Mutex}; - - /// A wrapper around `T` that records when it is dropped. - struct RecordDrop<T: fmt::Display> { - id: T, - drops: Arc<Mutex<Vec<String>>>, - } - - impl<T: fmt::Display> RecordDrop<T> { - fn new(id: T, drops: &Arc<Mutex<Vec<String>>>) -> Self { - RecordDrop { - id, - drops: drops.clone(), - } - } - } - - impl RecordDrop<u8> { - fn map_to_char(self) -> RecordDrop<char> { - let this = std::mem::ManuallyDrop::new(self); - RecordDrop { - id: (this.id + b'A') as char, - drops: this.drops.clone(), - } - } - } - - impl<T: fmt::Display> Drop for RecordDrop<T> { - fn drop(&mut self) { - self.drops.lock().unwrap().push(format!("{}", self.id)); - } - } - - #[test] - fn vec_no_cleanup_after_success() { - let drops = Arc::new(Mutex::new(Vec::new())); - let to_fold = (0u8..5).map(|i| RecordDrop::new(i, &drops)).collect(); - - let res: Result<_, ()> = super::fallible_map_vec(to_fold, |x| Ok(x.map_to_char())); - - assert!(res.is_ok()); - assert!(drops.lock().unwrap().is_empty()); - } - - #[test] - fn vec_cleanup_after_panic() { - let drops = Arc::new(Mutex::new(Vec::new())); - let to_fold = (0u8..5).map(|i| RecordDrop::new(i, &drops)).collect(); - - let res = std::panic::catch_unwind(|| { - let _: Result<_, ()> = super::fallible_map_vec(to_fold, |x| { - if x.id == 3 { - panic!(); - } - - Ok(x.map_to_char()) - }); - }); - - assert!(res.is_err()); - assert_eq!(*drops.lock().unwrap(), &["3", "A", "B", "C", "4"]); - } - - #[test] - fn vec_cleanup_after_early_return() { - let drops = Arc::new(Mutex::new(Vec::new())); - let to_fold = (0u8..5).map(|i| RecordDrop::new(i, &drops)).collect(); - - let res = super::fallible_map_vec(to_fold, |x| { - if x.id == 2 { - return Err(()); - } - - Ok(x.map_to_char()) - }); - - assert!(res.is_err()); - assert_eq!(*drops.lock().unwrap(), &["2", "A", "B", "3", "4"]); - } - - #[test] - fn box_no_cleanup_after_success() { - let drops = Arc::new(Mutex::new(Vec::new())); - let to_fold = Box::new(RecordDrop::new(0, &drops)); - - let res: Result<Box<_>, ()> = super::fallible_map_box(to_fold, |x| Ok(x.map_to_char())); - - assert!(res.is_ok()); - assert!(drops.lock().unwrap().is_empty()); - } - - #[test] - fn box_cleanup_after_panic() { - let drops = Arc::new(Mutex::new(Vec::new())); - let to_fold = Box::new(RecordDrop::new(0, &drops)); - - let res = std::panic::catch_unwind(|| { - let _: Result<Box<()>, ()> = super::fallible_map_box(to_fold, |_| panic!()); - }); - - assert!(res.is_err()); - assert_eq!(*drops.lock().unwrap(), &["0"]); - } - - #[test] - fn box_cleanup_after_early_return() { - let drops = Arc::new(Mutex::new(Vec::new())); - let to_fold = Box::new(RecordDrop::new(0, &drops)); - - let res: Result<Box<()>, _> = super::fallible_map_box(to_fold, |_| Err(())); - - assert!(res.is_err()); - assert_eq!(*drops.lock().unwrap(), &["0"]); - } -} diff --git a/vendor/chalk-ir/src/fold/shift.rs b/vendor/chalk-ir/src/fold/shift.rs deleted file mode 100644 index f7e5e4a4a..000000000 --- a/vendor/chalk-ir/src/fold/shift.rs +++ /dev/null @@ -1,177 +0,0 @@ -//! Shifting of debruijn indices - -use crate::*; - -/// Methods for converting debruijn indices to move values into or out -/// of binders. -pub trait Shift<I: Interner>: TypeFoldable<I> { - /// Shifts this term in one level of binders. - fn shifted_in(self, interner: I) -> Self; - - /// Shifts a term valid at `outer_binder` so that it is - /// valid at the innermost binder. See [`DebruijnIndex::shifted_in_from`] - /// for a detailed explanation. - fn shifted_in_from(self, interner: I, source_binder: DebruijnIndex) -> Self; - - /// Shifts this term out one level of binders. - fn shifted_out(self, interner: I) -> Fallible<Self>; - - /// Shifts a term valid at the innermost binder so that it is - /// valid at `outer_binder`. See [`DebruijnIndex::shifted_out_to`] - /// for a detailed explanation. - fn shifted_out_to(self, interner: I, target_binder: DebruijnIndex) -> Fallible<Self>; -} - -impl<T: TypeFoldable<I>, I: Interner> Shift<I> for T { - fn shifted_in(self, interner: I) -> Self { - self.shifted_in_from(interner, DebruijnIndex::ONE) - } - - fn shifted_in_from(self, interner: I, source_binder: DebruijnIndex) -> T { - self.try_fold_with( - &mut Shifter { - source_binder, - interner, - }, - DebruijnIndex::INNERMOST, - ) - .unwrap() - } - - fn shifted_out_to(self, interner: I, target_binder: DebruijnIndex) -> Fallible<T> { - self.try_fold_with( - &mut DownShifter { - target_binder, - interner, - }, - DebruijnIndex::INNERMOST, - ) - } - - fn shifted_out(self, interner: I) -> Fallible<Self> { - self.shifted_out_to(interner, DebruijnIndex::ONE) - } -} - -/// A folder that adjusts debruijn indices by a certain amount. -#[derive(FallibleTypeFolder)] -struct Shifter<I: Interner> { - source_binder: DebruijnIndex, - interner: I, -} - -impl<I: Interner> Shifter<I> { - /// Given a free variable at `depth`, shifts that depth to `depth - /// + self.adjustment`, and then wraps *that* within the internal - /// set `binders`. - fn adjust(&self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> BoundVar { - bound_var - .shifted_in_from(self.source_binder) - .shifted_in_from(outer_binder) - } -} - -impl<I: Interner> TypeFolder<I> for Shifter<I> { - fn as_dyn(&mut self) -> &mut dyn TypeFolder<I> { - self - } - - fn fold_free_var_ty(&mut self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> Ty<I> { - TyKind::<I>::BoundVar(self.adjust(bound_var, outer_binder)) - .intern(TypeFolder::interner(self)) - } - - fn fold_free_var_lifetime( - &mut self, - bound_var: BoundVar, - outer_binder: DebruijnIndex, - ) -> Lifetime<I> { - LifetimeData::<I>::BoundVar(self.adjust(bound_var, outer_binder)) - .intern(TypeFolder::interner(self)) - } - - fn fold_free_var_const( - &mut self, - ty: Ty<I>, - bound_var: BoundVar, - outer_binder: DebruijnIndex, - ) -> Const<I> { - // const types don't have free variables, so we can skip folding `ty` - self.adjust(bound_var, outer_binder) - .to_const(TypeFolder::interner(self), ty) - } - - fn interner(&self) -> I { - self.interner - } -} - -//--------------------------------------------------------------------------- - -/// A shifter that reduces debruijn indices -- in other words, which lifts a value -/// *out* from binders. Consider this example: -/// -struct DownShifter<I> { - target_binder: DebruijnIndex, - interner: I, -} - -impl<I> DownShifter<I> { - /// Given a reference to a free variable at depth `depth` - /// (appearing within `binders` internal binders), attempts to - /// lift that free variable out from `adjustment` levels of - /// binders (i.e., convert it to depth `depth - - /// self.adjustment`). If the free variable is bound by one of - /// those internal binders (i.e., `depth < self.adjustment`) the - /// this will fail with `Err`. Otherwise, returns the variable at - /// this new depth (but adjusted to appear within `binders`). - fn adjust(&self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> Fallible<BoundVar> { - match bound_var.shifted_out_to(self.target_binder) { - Some(bound_var1) => Ok(bound_var1.shifted_in_from(outer_binder)), - None => Err(NoSolution), - } - } -} - -impl<I: Interner> FallibleTypeFolder<I> for DownShifter<I> { - type Error = NoSolution; - - fn as_dyn(&mut self) -> &mut dyn FallibleTypeFolder<I, Error = Self::Error> { - self - } - - fn try_fold_free_var_ty( - &mut self, - bound_var: BoundVar, - outer_binder: DebruijnIndex, - ) -> Fallible<Ty<I>> { - Ok(TyKind::<I>::BoundVar(self.adjust(bound_var, outer_binder)?).intern(self.interner())) - } - - fn try_fold_free_var_lifetime( - &mut self, - bound_var: BoundVar, - outer_binder: DebruijnIndex, - ) -> Fallible<Lifetime<I>> { - Ok( - LifetimeData::<I>::BoundVar(self.adjust(bound_var, outer_binder)?) - .intern(self.interner()), - ) - } - - fn try_fold_free_var_const( - &mut self, - ty: Ty<I>, - bound_var: BoundVar, - outer_binder: DebruijnIndex, - ) -> Fallible<Const<I>> { - // const types don't have free variables, so we can skip folding `ty` - Ok(self - .adjust(bound_var, outer_binder)? - .to_const(self.interner(), ty)) - } - - fn interner(&self) -> I { - self.interner - } -} diff --git a/vendor/chalk-ir/src/fold/subst.rs b/vendor/chalk-ir/src/fold/subst.rs deleted file mode 100644 index 7cff8d89c..000000000 --- a/vendor/chalk-ir/src/fold/subst.rs +++ /dev/null @@ -1,118 +0,0 @@ -use super::*; -use crate::fold::shift::Shift; - -/// Substitution used during folding -#[derive(FallibleTypeFolder)] -pub struct Subst<'s, I: Interner> { - /// Values to substitute. A reference to a free variable with - /// index `i` will be mapped to `parameters[i]` -- if `i > - /// parameters.len()`, then we will leave the variable untouched. - parameters: &'s [GenericArg<I>], - interner: I, -} - -impl<I: Interner> Subst<'_, I> { - /// Applies the substitution by folding - pub fn apply<T: TypeFoldable<I>>(interner: I, parameters: &[GenericArg<I>], value: T) -> T { - value - .try_fold_with( - &mut Subst { - parameters, - interner, - }, - DebruijnIndex::INNERMOST, - ) - .unwrap() - } -} - -impl<I: Interner> TypeFolder<I> for Subst<'_, I> { - fn as_dyn(&mut self) -> &mut dyn TypeFolder<I> { - self - } - - /// We are eliminating one binder, but binders outside of that get preserved. - /// - /// So e.g. consider this: - /// - /// ```notrust - /// for<A, B> { for<C> { [A, C] } } - /// // ^ the binder we are substituing with `[u32]` - /// ``` - /// - /// Here, `A` would be `^1.0` and `C` would be `^0.0`. We will replace `^0.0` with the - /// 0th index from the list (`u32`). We will convert `^1.0` (A) to `^0.0` -- i.e., shift - /// it **out** of one level of binder (the `for<C>` binder we are eliminating). - /// - /// This gives us as a result: - /// - /// ```notrust - /// for<A, B> { [A, u32] } - /// ^ represented as `^0.0` - /// ``` - fn fold_free_var_ty(&mut self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> Ty<I> { - if let Some(index) = bound_var.index_if_innermost() { - match self.parameters[index].data(TypeFolder::interner(self)) { - GenericArgData::Ty(t) => t - .clone() - .shifted_in_from(TypeFolder::interner(self), outer_binder), - _ => panic!("mismatched kinds in substitution"), - } - } else { - bound_var - .shifted_out() - .expect("cannot fail because this is not the innermost") - .shifted_in_from(outer_binder) - .to_ty(TypeFolder::interner(self)) - } - } - - /// see `fold_free_var_ty` - fn fold_free_var_lifetime( - &mut self, - bound_var: BoundVar, - outer_binder: DebruijnIndex, - ) -> Lifetime<I> { - if let Some(index) = bound_var.index_if_innermost() { - match self.parameters[index].data(TypeFolder::interner(self)) { - GenericArgData::Lifetime(l) => l - .clone() - .shifted_in_from(TypeFolder::interner(self), outer_binder), - _ => panic!("mismatched kinds in substitution"), - } - } else { - bound_var - .shifted_out() - .unwrap() - .shifted_in_from(outer_binder) - .to_lifetime(TypeFolder::interner(self)) - } - } - - /// see `fold_free_var_ty` - fn fold_free_var_const( - &mut self, - ty: Ty<I>, - bound_var: BoundVar, - outer_binder: DebruijnIndex, - ) -> Const<I> { - if let Some(index) = bound_var.index_if_innermost() { - match self.parameters[index].data(TypeFolder::interner(self)) { - GenericArgData::Const(c) => c - .clone() - .shifted_in_from(TypeFolder::interner(self), outer_binder), - _ => panic!("mismatched kinds in substitution"), - } - } else { - bound_var - .shifted_out() - .unwrap() - .shifted_in_from(outer_binder) - .to_const(TypeFolder::interner(self), ty) - } - } - - fn interner(&self) -> I { - self.interner - } -} diff --git a/vendor/chalk-ir/src/interner.rs b/vendor/chalk-ir/src/interner.rs deleted file mode 100644 index 4959e4b74..000000000 --- a/vendor/chalk-ir/src/interner.rs +++ /dev/null @@ -1,702 +0,0 @@ -//! Encapsulates the concrete representation of core types such as types and goals. -use crate::AliasTy; -use crate::AssocTypeId; -use crate::CanonicalVarKind; -use crate::CanonicalVarKinds; -use crate::ClosureId; -use crate::Constraint; -use crate::Constraints; -use crate::FnDefId; -use crate::ForeignDefId; -use crate::GeneratorId; -use crate::GenericArg; -use crate::GenericArgData; -use crate::Goal; -use crate::GoalData; -use crate::Goals; -use crate::InEnvironment; -use crate::Lifetime; -use crate::LifetimeData; -use crate::OpaqueTy; -use crate::OpaqueTyId; -use crate::ProgramClause; -use crate::ProgramClauseData; -use crate::ProgramClauseImplication; -use crate::ProgramClauses; -use crate::ProjectionTy; -use crate::QuantifiedWhereClause; -use crate::QuantifiedWhereClauses; -use crate::SeparatorTraitRef; -use crate::Substitution; -use crate::TraitId; -use crate::Ty; -use crate::TyData; -use crate::VariableKind; -use crate::VariableKinds; -use crate::Variance; -use crate::Variances; -use crate::{AdtId, TyKind}; -use crate::{Const, ConstData}; -use std::fmt::{self, Debug}; -use std::hash::Hash; -use std::marker::PhantomData; -use std::sync::Arc; - -/// A "interner" encapsulates the concrete representation of -/// certain "core types" from chalk-ir. All the types in chalk-ir are -/// parameterized by a `I: Interner`, and so (e.g.) if they want to -/// store a type, they don't store a `Ty<I>` instance directly, but -/// rather prefer a `Ty<I>`. You can think of `I::Type` as the -/// interned representation (and, indeed, it may well be an interned -/// pointer, e.g. in rustc). -/// -/// Type families allow chalk to be embedded in different contexts -/// where the concrete representation of core types varies. They also -/// allow us to write generic code that reasons about multiple -/// distinct sets of types by using distinct generic type parameters -/// (e.g., `SourceI` and `TargetI`) -- even if those type parameters -/// wind up being mapped to the same underlying type families in the -/// end. -pub trait Interner: Debug + Copy + Eq + Hash + Sized { - /// "Interned" representation of types. In normal user code, - /// `Self::InternedType` is not referenced. Instead, we refer to - /// `Ty<Self>`, which wraps this type. - /// - /// An `InternedType` must be something that can be created from a - /// `TyKind` (by the [`intern_ty`][Self::intern_ty] method) and then later - /// converted back (by the [`ty_data`][Self::ty_data] method). The interned form - /// must also introduce indirection, either via a `Box`, `&`, or - /// other pointer type. - type InternedType: Debug + Clone + Eq + Hash; - - /// "Interned" representation of lifetimes. In normal user code, - /// `Self::InternedLifetime` is not referenced. Instead, we refer to - /// `Lifetime<Self>`, which wraps this type. - /// - /// An `InternedLifetime` must be something that can be created - /// from a `LifetimeData` (by the [`intern_lifetime`][Self::intern_lifetime] method) and - /// then later converted back (by the [`lifetime_data`][Self::lifetime_data] method). - type InternedLifetime: Debug + Clone + Eq + Hash; - - /// "Interned" representation of const expressions. In normal user code, - /// `Self::InternedConst` is not referenced. Instead, we refer to - /// `Const<Self>`, which wraps this type. - /// - /// An `InternedConst` must be something that can be created - /// from a `ConstData` (by the [`intern_const`][Self::intern_const] method) and - /// then later converted back (by the [`const_data`][Self::const_data] method). - type InternedConst: Debug + Clone + Eq + Hash; - - /// "Interned" representation of an evaluated const value. - /// `Self::InternedConcreteConst` is not referenced. Instead, - /// we refer to `ConcreteConst<Self>`, which wraps this type. - /// - /// `InternedConcreteConst` instances are not created by chalk, - /// it can only make a query asking about equality of two - /// evaluated consts. - type InternedConcreteConst: Debug + Clone + Eq + Hash; - - /// "Interned" representation of a "generic parameter", which can - /// be either a type or a lifetime. In normal user code, - /// `Self::InternedGenericArg` is not referenced. Instead, we refer to - /// `GenericArg<Self>`, which wraps this type. - /// - /// An `InternedType` is created by `intern_generic_arg` and can be - /// converted back to its underlying data via `generic_arg_data`. - type InternedGenericArg: Debug + Clone + Eq + Hash; - - /// "Interned" representation of a "goal". In normal user code, - /// `Self::InternedGoal` is not referenced. Instead, we refer to - /// `Goal<Self>`, which wraps this type. - /// - /// An `InternedGoal` is created by `intern_goal` and can be - /// converted back to its underlying data via `goal_data`. - type InternedGoal: Debug + Clone + Eq + Hash; - - /// "Interned" representation of a list of goals. In normal user code, - /// `Self::InternedGoals` is not referenced. Instead, we refer to - /// `Goals<Self>`, which wraps this type. - /// - /// An `InternedGoals` is created by `intern_goals` and can be - /// converted back to its underlying data via `goals_data`. - type InternedGoals: Debug + Clone + Eq + Hash; - - /// "Interned" representation of a "substitution". In normal user code, - /// `Self::InternedSubstitution` is not referenced. Instead, we refer to - /// `Substitution<Self>`, which wraps this type. - /// - /// An `InternedSubstitution` is created by `intern_substitution` and can be - /// converted back to its underlying data via `substitution_data`. - type InternedSubstitution: Debug + Clone + Eq + Hash; - - /// "Interned" representation of a list of program clauses. In normal user code, - /// `Self::InternedProgramClauses` is not referenced. Instead, we refer to - /// `ProgramClauses<Self>`, which wraps this type. - /// - /// An `InternedProgramClauses` is created by `intern_program_clauses` and can be - /// converted back to its underlying data via `program_clauses_data`. - type InternedProgramClauses: Debug + Clone + Eq + Hash; - - /// "Interned" representation of a "program clause". In normal user code, - /// `Self::InternedProgramClause` is not referenced. Instead, we refer to - /// `ProgramClause<Self>`, which wraps this type. - /// - /// An `InternedProgramClause` is created by `intern_program_clause` and can be - /// converted back to its underlying data via `program_clause_data`. - type InternedProgramClause: Debug + Clone + Eq + Hash; - - /// "Interned" representation of a list of quantified where clauses. - /// In normal user code, `Self::InternedQuantifiedWhereClauses` is not referenced. - /// Instead, we refer to `QuantifiedWhereClauses<Self>`, which wraps this type. - /// - /// An `InternedQuantifiedWhereClauses` is created by `intern_quantified_where_clauses` - /// and can be converted back to its underlying data via `quantified_where_clauses_data`. - type InternedQuantifiedWhereClauses: Debug + Clone + Eq + Hash; - - /// "Interned" representation of a list of variable kinds. - /// In normal user code, `Self::InternedVariableKinds` is not referenced. - /// Instead, we refer to `VariableKinds<Self>`, which wraps this type. - /// - /// An `InternedVariableKinds` is created by `intern_generic_arg_kinds` - /// and can be converted back to its underlying data via `variable_kinds_data`. - type InternedVariableKinds: Debug + Clone + Eq + Hash; - - /// "Interned" representation of a list of variable kinds with universe index. - /// In normal user code, `Self::InternedCanonicalVarKinds` is not referenced. - /// Instead, we refer to `CanonicalVarKinds<Self>`, which wraps this type. - /// - /// An `InternedCanonicalVarKinds` is created by - /// `intern_canonical_var_kinds` and can be converted back - /// to its underlying data via `canonical_var_kinds_data`. - type InternedCanonicalVarKinds: Debug + Clone + Eq + Hash; - - /// "Interned" representation of a list of region constraints. - /// In normal user code, `Self::InternedConstraints` is not referenced. - /// Instead, we refer to `Constraints<Self>`, which wraps this type. - /// - /// An `InternedConstraints` is created by `intern_constraints` - /// and can be converted back to its underlying data via `constraints_data`. - type InternedConstraints: Debug + Clone + Eq + Hash; - - /// "Interned" representation of a list of `chalk_ir::Variance`. - /// In normal user code, `Self::InternedVariances` is not referenced. - /// Instead, we refer to `Variances<Self>`, which wraps this type. - /// - /// An `InternedVariances` is created by - /// `intern_variances` and can be converted back - /// to its underlying data via `variances_data`. - type InternedVariances: Debug + Clone + Eq + Hash; - - /// The core "id" type used for trait-ids and the like. - type DefId: Debug + Copy + Eq + Hash; - - /// The ID type for ADTs - type InternedAdtId: Debug + Copy + Eq + Hash; - - /// Representation of identifiers. - type Identifier: Debug + Clone + Eq + Hash; - - /// Representation of function ABI (e.g. calling convention). - type FnAbi: Debug + Copy + Eq + Hash; - - /// Prints the debug representation of a type-kind-id. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_adt_id(adt_id: AdtId<Self>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a type-kind-id. - /// Returns `None` to fallback to the default debug output (e.g., - /// if no info about current program is available from TLS). - #[allow(unused_variables)] - fn debug_trait_id( - trait_id: TraitId<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a type-kind-id. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_assoc_type_id( - type_id: AssocTypeId<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of an opaque type. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_opaque_ty_id( - opaque_ty_id: OpaqueTyId<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a function-def-id. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_fn_def_id( - fn_def_id: FnDefId<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a closure id. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_closure_id( - fn_def_id: ClosureId<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a foreign-def-id. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_foreign_def_id( - foreign_def_id: ForeignDefId<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of an alias. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_generator_id( - generator_id: GeneratorId<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of an alias. To get good - /// results, this requires inspecting TLS, and is difficult to - /// code without reference to a specific interner (and hence - /// fully known types). - /// - /// Returns `None` to fallback to the default debug output (e.g., - /// if no info about current program is available from TLS). - #[allow(unused_variables)] - fn debug_alias(alias: &AliasTy<Self>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a ProjectionTy. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_projection_ty( - projection_ty: &ProjectionTy<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of an OpaqueTy. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_opaque_ty( - opaque_ty: &OpaqueTy<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a type. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_ty(ty: &Ty<Self>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a lifetime. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_lifetime( - lifetime: &Lifetime<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a const. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_const(constant: &Const<Self>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of an parameter. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_generic_arg( - generic_arg: &GenericArg<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a parameter kinds list. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_variable_kinds( - variable_kinds: &VariableKinds<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a parameter kinds list, with angle brackets. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_variable_kinds_with_angles( - variable_kinds: &VariableKinds<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of an parameter kinds list with universe index. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_canonical_var_kinds( - canonical_var_kinds: &CanonicalVarKinds<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of an goal. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_goal(goal: &Goal<Self>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a list of goals. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_goals(goals: &Goals<Self>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a ProgramClauseImplication. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_program_clause_implication( - pci: &ProgramClauseImplication<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a ProgramClause. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_program_clause( - clause: &ProgramClause<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a ProgramClauses. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_program_clauses( - clauses: &ProgramClauses<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a Substitution. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_substitution( - substitution: &Substitution<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a SeparatorTraitRef. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_separator_trait_ref( - separator_trait_ref: &SeparatorTraitRef<'_, Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a QuantifiedWhereClauses. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_quantified_where_clauses( - clauses: &QuantifiedWhereClauses<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a Constraints. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_constraints( - clauses: &Constraints<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Prints the debug representation of a Variances. - /// Returns `None` to fallback to the default debug output. - #[allow(unused_variables)] - fn debug_variances( - variances: &Variances<Self>, - fmt: &mut fmt::Formatter<'_>, - ) -> Option<fmt::Result> { - None - } - - /// Create an "interned" type from `ty`. This is not normally - /// invoked directly; instead, you invoke `TyKind::intern` (which - /// will ultimately call this method). - fn intern_ty(self, kind: TyKind<Self>) -> Self::InternedType; - - /// Lookup the `TyKind` from an interned type. - fn ty_data(self, ty: &Self::InternedType) -> &TyData<Self>; - - /// Create an "interned" lifetime from `lifetime`. This is not - /// normally invoked directly; instead, you invoke - /// `LifetimeData::intern` (which will ultimately call this - /// method). - fn intern_lifetime(self, lifetime: LifetimeData<Self>) -> Self::InternedLifetime; - - /// Lookup the `LifetimeData` that was interned to create a `InternedLifetime`. - fn lifetime_data(self, lifetime: &Self::InternedLifetime) -> &LifetimeData<Self>; - - /// Create an "interned" const from `const`. This is not - /// normally invoked directly; instead, you invoke - /// `ConstData::intern` (which will ultimately call this - /// method). - fn intern_const(self, constant: ConstData<Self>) -> Self::InternedConst; - - /// Lookup the `ConstData` that was interned to create a `InternedConst`. - fn const_data(self, constant: &Self::InternedConst) -> &ConstData<Self>; - - /// Determine whether two concrete const values are equal. - fn const_eq( - self, - ty: &Self::InternedType, - c1: &Self::InternedConcreteConst, - c2: &Self::InternedConcreteConst, - ) -> bool; - - /// Create an "interned" parameter from `data`. This is not - /// normally invoked directly; instead, you invoke - /// `GenericArgData::intern` (which will ultimately call this - /// method). - fn intern_generic_arg(self, data: GenericArgData<Self>) -> Self::InternedGenericArg; - - /// Lookup the `LifetimeData` that was interned to create a `InternedLifetime`. - fn generic_arg_data(self, lifetime: &Self::InternedGenericArg) -> &GenericArgData<Self>; - - /// Create an "interned" goal from `data`. This is not - /// normally invoked directly; instead, you invoke - /// `GoalData::intern` (which will ultimately call this - /// method). - fn intern_goal(self, data: GoalData<Self>) -> Self::InternedGoal; - - /// Lookup the `GoalData` that was interned to create a `InternedGoal`. - fn goal_data(self, goal: &Self::InternedGoal) -> &GoalData<Self>; - - /// Create an "interned" goals from `data`. This is not - /// normally invoked directly; instead, you invoke - /// `GoalsData::intern` (which will ultimately call this - /// method). - fn intern_goals<E>( - self, - data: impl IntoIterator<Item = Result<Goal<Self>, E>>, - ) -> Result<Self::InternedGoals, E>; - - /// Lookup the `GoalsData` that was interned to create a `InternedGoals`. - fn goals_data(self, goals: &Self::InternedGoals) -> &[Goal<Self>]; - - /// Create an "interned" substitution from `data`. This is not - /// normally invoked directly; instead, you invoke - /// `SubstitutionData::intern` (which will ultimately call this - /// method). - fn intern_substitution<E>( - self, - data: impl IntoIterator<Item = Result<GenericArg<Self>, E>>, - ) -> Result<Self::InternedSubstitution, E>; - - /// Lookup the `SubstitutionData` that was interned to create a `InternedSubstitution`. - fn substitution_data(self, substitution: &Self::InternedSubstitution) -> &[GenericArg<Self>]; - - /// Create an "interned" program clause from `data`. This is not - /// normally invoked directly; instead, you invoke - /// `ProgramClauseData::intern` (which will ultimately call this - /// method). - fn intern_program_clause(self, data: ProgramClauseData<Self>) -> Self::InternedProgramClause; - - /// Lookup the `ProgramClauseData` that was interned to create a `ProgramClause`. - fn program_clause_data(self, clause: &Self::InternedProgramClause) -> &ProgramClauseData<Self>; - - /// Create an "interned" program clauses from `data`. This is not - /// normally invoked directly; instead, you invoke - /// `ProgramClauses::from_iter` (which will ultimately call this - /// method). - fn intern_program_clauses<E>( - self, - data: impl IntoIterator<Item = Result<ProgramClause<Self>, E>>, - ) -> Result<Self::InternedProgramClauses, E>; - - /// Lookup the `ProgramClauseData` that was interned to create a `ProgramClause`. - fn program_clauses_data(self, clauses: &Self::InternedProgramClauses) - -> &[ProgramClause<Self>]; - - /// Create an "interned" quantified where clauses from `data`. This is not - /// normally invoked directly; instead, you invoke - /// `QuantifiedWhereClauses::from_iter` (which will ultimately call this - /// method). - fn intern_quantified_where_clauses<E>( - self, - data: impl IntoIterator<Item = Result<QuantifiedWhereClause<Self>, E>>, - ) -> Result<Self::InternedQuantifiedWhereClauses, E>; - - /// Lookup the slice of `QuantifiedWhereClause` that was interned to - /// create a `QuantifiedWhereClauses`. - fn quantified_where_clauses_data( - self, - clauses: &Self::InternedQuantifiedWhereClauses, - ) -> &[QuantifiedWhereClause<Self>]; - - /// Create an "interned" parameter kinds from `data`. This is not - /// normally invoked directly; instead, you invoke - /// `VariableKinds::from_iter` (which will ultimately call this - /// method). - fn intern_generic_arg_kinds<E>( - self, - data: impl IntoIterator<Item = Result<VariableKind<Self>, E>>, - ) -> Result<Self::InternedVariableKinds, E>; - - /// Lookup the slice of `VariableKinds` that was interned to - /// create a `VariableKinds`. - fn variable_kinds_data( - self, - variable_kinds: &Self::InternedVariableKinds, - ) -> &[VariableKind<Self>]; - - /// Create "interned" variable kinds with universe index from `data`. This is not - /// normally invoked directly; instead, you invoke - /// `CanonicalVarKinds::from_iter` (which will ultimately call this - /// method). - fn intern_canonical_var_kinds<E>( - self, - data: impl IntoIterator<Item = Result<CanonicalVarKind<Self>, E>>, - ) -> Result<Self::InternedCanonicalVarKinds, E>; - - /// Lookup the slice of `CanonicalVariableKind` that was interned to - /// create a `CanonicalVariableKinds`. - fn canonical_var_kinds_data( - self, - canonical_var_kinds: &Self::InternedCanonicalVarKinds, - ) -> &[CanonicalVarKind<Self>]; - - /// Create "interned" constraints from `data`. This is not - /// normally invoked dirctly; instead, you invoke - /// `Constraints::from_iter` (which will ultimately call this - /// method). - fn intern_constraints<E>( - self, - data: impl IntoIterator<Item = Result<InEnvironment<Constraint<Self>>, E>>, - ) -> Result<Self::InternedConstraints, E>; - - /// Lookup the slice of `Constraint` that was interned to - /// create a `Constraints`. - fn constraints_data( - self, - constraints: &Self::InternedConstraints, - ) -> &[InEnvironment<Constraint<Self>>]; - - /// Create "interned" variances from `data`. This is not - /// normally invoked directly; instead, you invoke - /// `Variances::from` (which will ultimately call this - /// method). - fn intern_variances<E>( - self, - data: impl IntoIterator<Item = Result<Variance, E>>, - ) -> Result<Self::InternedVariances, E>; - - /// Lookup the slice of `Variance` that was interned to - /// create a `Variances`. - fn variances_data(self, variances: &Self::InternedVariances) -> &[Variance]; -} - -/// Implemented by types that have an associated interner (which -/// are virtually all of the types in chalk-ir, for example). -/// This lets us map from a type like `Ty<I>` to the parameter `I`. -/// -/// It's particularly useful for writing `TypeFoldable` impls for generic types like -/// `Binder<T>`, since it allows us to figure out the interner of `T`. -pub trait HasInterner { - /// The interner associated with the type. - type Interner: Interner; -} - -impl<T: HasInterner> HasInterner for [T] { - type Interner = T::Interner; -} - -impl<T: HasInterner> HasInterner for Vec<T> { - type Interner = T::Interner; -} - -impl<T: HasInterner> HasInterner for Box<T> { - type Interner = T::Interner; -} - -impl<T: HasInterner> HasInterner for Arc<T> { - type Interner = T::Interner; -} - -impl<T: HasInterner + ?Sized> HasInterner for &T { - type Interner = T::Interner; -} - -impl<I: Interner> HasInterner for PhantomData<I> { - type Interner = I; -} - -impl<A, B, I> HasInterner for (A, B) -where - A: HasInterner<Interner = I>, - B: HasInterner<Interner = I>, - I: Interner, -{ - type Interner = I; -} - -impl<A, B, C, I> HasInterner for (A, B, C) -where - A: HasInterner<Interner = I>, - B: HasInterner<Interner = I>, - C: HasInterner<Interner = I>, - I: Interner, -{ - type Interner = I; -} - -impl<'a, T: HasInterner> HasInterner for std::slice::Iter<'a, T> { - type Interner = T::Interner; -} diff --git a/vendor/chalk-ir/src/lib.rs b/vendor/chalk-ir/src/lib.rs deleted file mode 100644 index 5cf44b0c3..000000000 --- a/vendor/chalk-ir/src/lib.rs +++ /dev/null @@ -1,3055 +0,0 @@ -//! Defines the IR for types and logical predicates. - -#![deny(rust_2018_idioms)] -#![warn(missing_docs)] - -// Allows macros to refer to this crate as `::chalk_ir` -extern crate self as chalk_ir; - -use crate::cast::{Cast, CastTo, Caster}; -use crate::fold::shift::Shift; -use crate::fold::{FallibleTypeFolder, Subst, TypeFoldable, TypeFolder, TypeSuperFoldable}; -use crate::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor, VisitExt}; -use chalk_derive::{ - FallibleTypeFolder, HasInterner, TypeFoldable, TypeSuperVisitable, TypeVisitable, Zip, -}; -use std::marker::PhantomData; -use std::ops::ControlFlow; - -pub use crate::debug::SeparatorTraitRef; -#[macro_use(bitflags)] -extern crate bitflags; -/// Uninhabited (empty) type, used in combination with `PhantomData`. -#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub enum Void {} - -/// Many of our internal operations (e.g., unification) are an attempt -/// to perform some operation which may not complete. -pub type Fallible<T> = Result<T, NoSolution>; - -/// A combination of `Fallible` and `Floundered`. -pub enum FallibleOrFloundered<T> { - /// Success - Ok(T), - /// No solution. See `chalk_ir::NoSolution`. - NoSolution, - /// Floundered. See `chalk_ir::Floundered`. - Floundered, -} - -/// Indicates that the attempted operation has "no solution" -- i.e., -/// cannot be performed. -#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct NoSolution; - -/// Indicates that the complete set of program clauses for this goal -/// cannot be enumerated. -pub struct Floundered; - -macro_rules! impl_debugs { - ($($id:ident), *) => { - $( - impl<I: Interner> std::fmt::Debug for $id<I> { - fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> { - write!(fmt, "{}({:?})", stringify!($id), self.0) - } - } - )* - }; -} - -#[macro_use] -pub mod zip; - -#[macro_use] -pub mod fold; - -#[macro_use] -pub mod visit; - -pub mod cast; - -pub mod interner; -use interner::{HasInterner, Interner}; - -pub mod could_match; -pub mod debug; - -/// Variance -#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] -pub enum Variance { - /// a <: b - Covariant, - /// a == b - Invariant, - /// b <: a - Contravariant, -} - -impl Variance { - /// `a.xform(b)` combines the variance of a context with the - /// variance of a type with the following meaning. If we are in a - /// context with variance `a`, and we encounter a type argument in - /// a position with variance `b`, then `a.xform(b)` is the new - /// variance with which the argument appears. - /// - /// Example 1: - /// - /// ```ignore - /// *mut Vec<i32> - /// ``` - /// - /// Here, the "ambient" variance starts as covariant. `*mut T` is - /// invariant with respect to `T`, so the variance in which the - /// `Vec<i32>` appears is `Covariant.xform(Invariant)`, which - /// yields `Invariant`. Now, the type `Vec<T>` is covariant with - /// respect to its type argument `T`, and hence the variance of - /// the `i32` here is `Invariant.xform(Covariant)`, which results - /// (again) in `Invariant`. - /// - /// Example 2: - /// - /// ```ignore - /// fn(*const Vec<i32>, *mut Vec<i32) - /// ``` - /// - /// The ambient variance is covariant. A `fn` type is - /// contravariant with respect to its parameters, so the variance - /// within which both pointer types appear is - /// `Covariant.xform(Contravariant)`, or `Contravariant`. `*const - /// T` is covariant with respect to `T`, so the variance within - /// which the first `Vec<i32>` appears is - /// `Contravariant.xform(Covariant)` or `Contravariant`. The same - /// is true for its `i32` argument. In the `*mut T` case, the - /// variance of `Vec<i32>` is `Contravariant.xform(Invariant)`, - /// and hence the outermost type is `Invariant` with respect to - /// `Vec<i32>` (and its `i32` argument). - /// - /// Source: Figure 1 of "Taming the Wildcards: - /// Combining Definition- and Use-Site Variance" published in PLDI'11. - /// (Doc from rustc) - pub fn xform(self, other: Variance) -> Variance { - match (self, other) { - (Variance::Invariant, _) => Variance::Invariant, - (_, Variance::Invariant) => Variance::Invariant, - (_, Variance::Covariant) => self, - (Variance::Covariant, Variance::Contravariant) => Variance::Contravariant, - (Variance::Contravariant, Variance::Contravariant) => Variance::Covariant, - } - } - - /// Converts `Covariant` into `Contravariant` and vice-versa. `Invariant` - /// stays the same. - pub fn invert(self) -> Variance { - match self { - Variance::Invariant => Variance::Invariant, - Variance::Covariant => Variance::Contravariant, - Variance::Contravariant => Variance::Covariant, - } - } -} - -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner)] -/// The set of assumptions we've made so far, and the current number of -/// universal (forall) quantifiers we're within. -pub struct Environment<I: Interner> { - /// The clauses in the environment. - pub clauses: ProgramClauses<I>, -} - -impl<I: Interner> Copy for Environment<I> where I::InternedProgramClauses: Copy {} - -impl<I: Interner> Environment<I> { - /// Creates a new environment. - pub fn new(interner: I) -> Self { - Environment { - clauses: ProgramClauses::empty(interner), - } - } - - /// Adds (an iterator of) clauses to the environment. - pub fn add_clauses<II>(&self, interner: I, clauses: II) -> Self - where - II: IntoIterator<Item = ProgramClause<I>>, - { - let mut env = self.clone(); - env.clauses = - ProgramClauses::from_iter(interner, env.clauses.iter(interner).cloned().chain(clauses)); - env - } - - /// True if any of the clauses in the environment have a consequence of `Compatible`. - /// Panics if the conditions or constraints of that clause are not empty. - pub fn has_compatible_clause(&self, interner: I) -> bool { - self.clauses.as_slice(interner).iter().any(|c| { - let ProgramClauseData(implication) = c.data(interner); - match implication.skip_binders().consequence { - DomainGoal::Compatible => { - // We currently don't generate `Compatible` with any conditions or constraints - // If this was needed, for whatever reason, then a third "yes, but must evaluate" - // return value would have to be added. - assert!(implication.skip_binders().conditions.is_empty(interner)); - assert!(implication.skip_binders().constraints.is_empty(interner)); - true - } - _ => false, - } - }) - } -} - -/// A goal with an environment to solve it in. -#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable)] -#[allow(missing_docs)] -pub struct InEnvironment<G: HasInterner> { - pub environment: Environment<G::Interner>, - pub goal: G, -} - -impl<G: HasInterner<Interner = I> + Copy, I: Interner> Copy for InEnvironment<G> where - I::InternedProgramClauses: Copy -{ -} - -impl<G: HasInterner> InEnvironment<G> { - /// Creates a new environment/goal pair. - pub fn new(environment: &Environment<G::Interner>, goal: G) -> Self { - InEnvironment { - environment: environment.clone(), - goal, - } - } - - /// Maps the goal without touching the environment. - pub fn map<OP, H>(self, op: OP) -> InEnvironment<H> - where - OP: FnOnce(G) -> H, - H: HasInterner<Interner = G::Interner>, - { - InEnvironment { - environment: self.environment, - goal: op(self.goal), - } - } -} - -impl<G: HasInterner> HasInterner for InEnvironment<G> { - type Interner = G::Interner; -} - -/// Different signed int types. -#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] -#[allow(missing_docs)] -pub enum IntTy { - Isize, - I8, - I16, - I32, - I64, - I128, -} - -/// Different unsigned int types. -#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] -#[allow(missing_docs)] -pub enum UintTy { - Usize, - U8, - U16, - U32, - U64, - U128, -} - -/// Different kinds of float types. -#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] -#[allow(missing_docs)] -pub enum FloatTy { - F32, - F64, -} - -/// Types of scalar values. -#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] -#[allow(missing_docs)] -pub enum Scalar { - Bool, - Char, - Int(IntTy), - Uint(UintTy), - Float(FloatTy), -} - -/// Whether a function is safe or not. -#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub enum Safety { - /// Safe - Safe, - /// Unsafe - Unsafe, -} - -/// Whether a type is mutable or not. -#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub enum Mutability { - /// Mutable - Mut, - /// Immutable - Not, -} - -/// An universe index is how a universally quantified parameter is -/// represented when it's binder is moved into the environment. -/// An example chain of transformations would be: -/// `forall<T> { Goal(T) }` (syntactical representation) -/// `forall { Goal(?0) }` (used a DeBruijn index) -/// `Goal(!U1)` (the quantifier was moved to the environment and replaced with a universe index) -/// See <https://rustc-dev-guide.rust-lang.org/borrow_check/region_inference.html#placeholders-and-universes> for more. -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct UniverseIndex { - /// The counter for the universe index, starts with 0. - pub counter: usize, -} - -impl UniverseIndex { - /// Root universe index (0). - pub const ROOT: UniverseIndex = UniverseIndex { counter: 0 }; - - /// Root universe index (0). - pub fn root() -> UniverseIndex { - Self::ROOT - } - - /// Whether one universe can "see" another. - pub fn can_see(self, ui: UniverseIndex) -> bool { - self.counter >= ui.counter - } - - /// Increases the index counter. - pub fn next(self) -> UniverseIndex { - UniverseIndex { - counter: self.counter + 1, - } - } -} - -/// Maps the universes found in the `u_canonicalize` result (the -/// "canonical" universes) to the universes found in the original -/// value (and vice versa). When used as a folder -- i.e., from -/// outside this module -- converts from "canonical" universes to the -/// original (but see the `UMapToCanonical` folder). -#[derive(Clone, Debug)] -pub struct UniverseMap { - /// A reverse map -- for each universe Ux that appears in - /// `quantified`, the corresponding universe in the original was - /// `universes[x]`. - pub universes: Vec<UniverseIndex>, -} - -impl UniverseMap { - /// Creates a new universe map. - pub fn new() -> Self { - UniverseMap { - universes: vec![UniverseIndex::root()], - } - } - - /// Number of canonical universes. - pub fn num_canonical_universes(&self) -> usize { - self.universes.len() - } -} - -/// The id for an Abstract Data Type (i.e. structs, unions and enums). -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct AdtId<I: Interner>(pub I::InternedAdtId); - -/// The id of a trait definition; could be used to load the trait datum by -/// invoking the [`trait_datum`] method. -/// -/// [`trait_datum`]: ../chalk_solve/trait.RustIrDatabase.html#tymethod.trait_datum -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct TraitId<I: Interner>(pub I::DefId); - -/// The id for an impl. -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct ImplId<I: Interner>(pub I::DefId); - -/// Id for a specific clause. -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct ClauseId<I: Interner>(pub I::DefId); - -/// The id for the associated type member of a trait. The details of the type -/// can be found by invoking the [`associated_ty_data`] method. -/// -/// [`associated_ty_data`]: ../chalk_solve/trait.RustIrDatabase.html#tymethod.associated_ty_data -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct AssocTypeId<I: Interner>(pub I::DefId); - -/// Id for an opaque type. -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct OpaqueTyId<I: Interner>(pub I::DefId); - -/// Function definition id. -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct FnDefId<I: Interner>(pub I::DefId); - -/// Id for Rust closures. -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct ClosureId<I: Interner>(pub I::DefId); - -/// Id for Rust generators. -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct GeneratorId<I: Interner>(pub I::DefId); - -/// Id for foreign types. -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct ForeignDefId<I: Interner>(pub I::DefId); - -impl_debugs!(ImplId, ClauseId); - -/// A Rust type. The actual type data is stored in `TyKind`. -#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)] -pub struct Ty<I: Interner> { - interned: I::InternedType, -} - -impl<I: Interner> Ty<I> { - /// Creates a type from `TyKind`. - pub fn new(interner: I, data: impl CastTo<TyKind<I>>) -> Self { - let ty_kind = data.cast(interner); - Ty { - interned: I::intern_ty(interner, ty_kind), - } - } - - /// Gets the interned type. - pub fn interned(&self) -> &I::InternedType { - &self.interned - } - - /// Gets the underlying type data. - pub fn data(&self, interner: I) -> &TyData<I> { - I::ty_data(interner, &self.interned) - } - - /// Gets the underlying type kind. - pub fn kind(&self, interner: I) -> &TyKind<I> { - &I::ty_data(interner, &self.interned).kind - } - - /// Creates a `FromEnv` constraint using this type. - pub fn from_env(&self) -> FromEnv<I> { - FromEnv::Ty(self.clone()) - } - - /// Creates a WF-constraint for this type. - pub fn well_formed(&self) -> WellFormed<I> { - WellFormed::Ty(self.clone()) - } - - /// Creates a domain goal `FromEnv(T)` where `T` is this type. - pub fn into_from_env_goal(self, interner: I) -> DomainGoal<I> { - self.from_env().cast(interner) - } - - /// If this is a `TyKind::BoundVar(d)`, returns `Some(d)` else `None`. - pub fn bound_var(&self, interner: I) -> Option<BoundVar> { - if let TyKind::BoundVar(bv) = self.kind(interner) { - Some(*bv) - } else { - None - } - } - - /// If this is a `TyKind::InferenceVar(d)`, returns `Some(d)` else `None`. - pub fn inference_var(&self, interner: I) -> Option<InferenceVar> { - if let TyKind::InferenceVar(depth, _) = self.kind(interner) { - Some(*depth) - } else { - None - } - } - - /// Returns true if this is a `BoundVar` or an `InferenceVar` of `TyVariableKind::General`. - pub fn is_general_var(&self, interner: I, binders: &CanonicalVarKinds<I>) -> bool { - match self.kind(interner) { - TyKind::BoundVar(bv) - if bv.debruijn == DebruijnIndex::INNERMOST - && binders.at(interner, bv.index).kind - == VariableKind::Ty(TyVariableKind::General) => - { - true - } - TyKind::InferenceVar(_, TyVariableKind::General) => true, - _ => false, - } - } - - /// Returns true if this is an `Alias`. - pub fn is_alias(&self, interner: I) -> bool { - matches!(self.kind(interner), TyKind::Alias(..)) - } - - /// Returns true if this is an `IntTy` or `UintTy`. - pub fn is_integer(&self, interner: I) -> bool { - matches!( - self.kind(interner), - TyKind::Scalar(Scalar::Int(_) | Scalar::Uint(_)) - ) - } - - /// Returns true if this is a `FloatTy`. - pub fn is_float(&self, interner: I) -> bool { - matches!(self.kind(interner), TyKind::Scalar(Scalar::Float(_))) - } - - /// Returns `Some(adt_id)` if this is an ADT, `None` otherwise - pub fn adt_id(&self, interner: I) -> Option<AdtId<I>> { - match self.kind(interner) { - TyKind::Adt(adt_id, _) => Some(*adt_id), - _ => None, - } - } - - /// True if this type contains "bound" types/lifetimes, and hence - /// needs to be shifted across binders. This is a very inefficient - /// check, intended only for debug assertions, because I am lazy. - pub fn needs_shift(&self, interner: I) -> bool { - self.has_free_vars(interner) - } -} - -/// Contains the data for a Ty -#[derive(Clone, PartialEq, Eq, Hash, HasInterner)] -pub struct TyData<I: Interner> { - /// The kind - pub kind: TyKind<I>, - /// Type flags - pub flags: TypeFlags, -} - -bitflags! { - /// Contains flags indicating various properties of a Ty - pub struct TypeFlags : u16 { - /// Does the type contain an InferenceVar - const HAS_TY_INFER = 1; - /// Does the type contain a lifetime with an InferenceVar - const HAS_RE_INFER = 1 << 1; - /// Does the type contain a ConstValue with an InferenceVar - const HAS_CT_INFER = 1 << 2; - /// Does the type contain a Placeholder TyKind - const HAS_TY_PLACEHOLDER = 1 << 3; - /// Does the type contain a lifetime with a Placeholder - const HAS_RE_PLACEHOLDER = 1 << 4; - /// Does the type contain a ConstValue Placeholder - const HAS_CT_PLACEHOLDER = 1 << 5; - /// True when the type has free lifetimes related to a local context - const HAS_FREE_LOCAL_REGIONS = 1 << 6; - /// Does the type contain a projection of an associated type - const HAS_TY_PROJECTION = 1 << 7; - /// Does the type contain an opaque type - const HAS_TY_OPAQUE = 1 << 8; - /// Does the type contain an unevaluated const projection - const HAS_CT_PROJECTION = 1 << 9; - /// Does the type contain an error - const HAS_ERROR = 1 << 10; - /// Does the type contain any free lifetimes - const HAS_FREE_REGIONS = 1 << 11; - /// True when the type contains lifetimes that will be substituted when function is called - const HAS_RE_LATE_BOUND = 1 << 12; - /// True when the type contains an erased lifetime - const HAS_RE_ERASED = 1 << 13; - /// Does the type contain placeholders or inference variables that could be replaced later - const STILL_FURTHER_SPECIALIZABLE = 1 << 14; - - /// True when the type contains free names local to a particular context - const HAS_FREE_LOCAL_NAMES = TypeFlags::HAS_TY_INFER.bits - | TypeFlags::HAS_CT_INFER.bits - | TypeFlags::HAS_TY_PLACEHOLDER.bits - | TypeFlags::HAS_CT_PLACEHOLDER.bits - | TypeFlags::HAS_FREE_LOCAL_REGIONS.bits; - - /// Does the type contain any form of projection - const HAS_PROJECTION = TypeFlags::HAS_TY_PROJECTION.bits - | TypeFlags::HAS_TY_OPAQUE.bits - | TypeFlags::HAS_CT_PROJECTION.bits; - } -} -/// Type data, which holds the actual type information. -#[derive(Clone, PartialEq, Eq, Hash, HasInterner)] -pub enum TyKind<I: Interner> { - /// Abstract data types, i.e., structs, unions, or enumerations. - /// For example, a type like `Vec<T>`. - Adt(AdtId<I>, Substitution<I>), - - /// an associated type like `Iterator::Item`; see `AssociatedType` for details - AssociatedType(AssocTypeId<I>, Substitution<I>), - - /// a scalar type like `bool` or `u32` - Scalar(Scalar), - - /// a tuple of the given arity - Tuple(usize, Substitution<I>), - - /// an array type like `[T; N]` - Array(Ty<I>, Const<I>), - - /// a slice type like `[T]` - Slice(Ty<I>), - - /// a raw pointer type like `*const T` or `*mut T` - Raw(Mutability, Ty<I>), - - /// a reference type like `&T` or `&mut T` - Ref(Mutability, Lifetime<I>, Ty<I>), - - /// a placeholder for opaque types like `impl Trait` - OpaqueType(OpaqueTyId<I>, Substitution<I>), - - /// a function definition - FnDef(FnDefId<I>, Substitution<I>), - - /// the string primitive type - Str, - - /// the never type `!` - Never, - - /// A closure. - Closure(ClosureId<I>, Substitution<I>), - - /// A generator. - Generator(GeneratorId<I>, Substitution<I>), - - /// A generator witness. - GeneratorWitness(GeneratorId<I>, Substitution<I>), - - /// foreign types - Foreign(ForeignDefId<I>), - - /// This can be used to represent an error, e.g. during name resolution of a type. - /// Chalk itself will not produce this, just pass it through when given. - Error, - - /// instantiated from a universally quantified type, e.g., from - /// `forall<T> { .. }`. Stands in as a representative of "some - /// unknown type". - Placeholder(PlaceholderIndex), - - /// A "dyn" type is a trait object type created via the "dyn Trait" syntax. - /// In the chalk parser, the traits that the object represents is parsed as - /// a QuantifiedInlineBound, and is then changed to a list of where clauses - /// during lowering. - /// - /// See the `Opaque` variant for a discussion about the use of - /// binders here. - Dyn(DynTy<I>), - - /// An "alias" type represents some form of type alias, such as: - /// - An associated type projection like `<T as Iterator>::Item` - /// - `impl Trait` types - /// - Named type aliases like `type Foo<X> = Vec<X>` - Alias(AliasTy<I>), - - /// A function type such as `for<'a> fn(&'a u32)`. - /// Note that "higher-ranked" types (starting with `for<>`) are either - /// function types or dyn types, and do not appear otherwise in Rust - /// surface syntax. - Function(FnPointer<I>), - - /// References the binding at the given depth. The index is a [de - /// Bruijn index], so it counts back through the in-scope binders. - BoundVar(BoundVar), - - /// Inference variable defined in the current inference context. - InferenceVar(InferenceVar, TyVariableKind), -} - -impl<I: Interner> Copy for TyKind<I> -where - I::InternedLifetime: Copy, - I::InternedSubstitution: Copy, - I::InternedVariableKinds: Copy, - I::InternedQuantifiedWhereClauses: Copy, - I::InternedType: Copy, - I::InternedConst: Copy, -{ -} - -impl<I: Interner> TyKind<I> { - /// Casts the type data to a type. - pub fn intern(self, interner: I) -> Ty<I> { - Ty::new(interner, self) - } - - /// Compute type flags for a TyKind - pub fn compute_flags(&self, interner: I) -> TypeFlags { - match self { - TyKind::Adt(_, substitution) - | TyKind::AssociatedType(_, substitution) - | TyKind::Tuple(_, substitution) - | TyKind::Closure(_, substitution) - | TyKind::Generator(_, substitution) - | TyKind::GeneratorWitness(_, substitution) - | TyKind::FnDef(_, substitution) - | TyKind::OpaqueType(_, substitution) => substitution.compute_flags(interner), - TyKind::Scalar(_) | TyKind::Str | TyKind::Never | TyKind::Foreign(_) => { - TypeFlags::empty() - } - TyKind::Error => TypeFlags::HAS_ERROR, - TyKind::Slice(ty) | TyKind::Raw(_, ty) => ty.data(interner).flags, - TyKind::Ref(_, lifetime, ty) => { - lifetime.compute_flags(interner) | ty.data(interner).flags - } - TyKind::Array(ty, const_ty) => { - let flags = ty.data(interner).flags; - let const_data = const_ty.data(interner); - flags - | const_data.ty.data(interner).flags - | match const_data.value { - ConstValue::BoundVar(_) | ConstValue::Concrete(_) => TypeFlags::empty(), - ConstValue::InferenceVar(_) => { - TypeFlags::HAS_CT_INFER | TypeFlags::STILL_FURTHER_SPECIALIZABLE - } - ConstValue::Placeholder(_) => { - TypeFlags::HAS_CT_PLACEHOLDER | TypeFlags::STILL_FURTHER_SPECIALIZABLE - } - } - } - TyKind::Placeholder(_) => TypeFlags::HAS_TY_PLACEHOLDER, - TyKind::Dyn(dyn_ty) => { - let lifetime_flags = dyn_ty.lifetime.compute_flags(interner); - let mut dyn_flags = TypeFlags::empty(); - for var_kind in dyn_ty.bounds.skip_binders().iter(interner) { - match &(var_kind.skip_binders()) { - WhereClause::Implemented(trait_ref) => { - dyn_flags |= trait_ref.substitution.compute_flags(interner) - } - WhereClause::AliasEq(alias_eq) => { - dyn_flags |= alias_eq.alias.compute_flags(interner); - dyn_flags |= alias_eq.ty.data(interner).flags; - } - WhereClause::LifetimeOutlives(lifetime_outlives) => { - dyn_flags |= lifetime_outlives.a.compute_flags(interner) - | lifetime_outlives.b.compute_flags(interner); - } - WhereClause::TypeOutlives(type_outlives) => { - dyn_flags |= type_outlives.ty.data(interner).flags; - dyn_flags |= type_outlives.lifetime.compute_flags(interner); - } - } - } - lifetime_flags | dyn_flags - } - TyKind::Alias(alias_ty) => alias_ty.compute_flags(interner), - TyKind::BoundVar(_) => TypeFlags::empty(), - TyKind::InferenceVar(_, _) => TypeFlags::HAS_TY_INFER, - TyKind::Function(fn_pointer) => fn_pointer.substitution.0.compute_flags(interner), - } - } -} - -/// Identifies a particular bound variable within a binder. -/// Variables are identified by the combination of a [`DebruijnIndex`], -/// which identifies the *binder*, and an index within that binder. -/// -/// Consider this case: -/// -/// ```ignore -/// forall<'a, 'b> { forall<'c, 'd> { ... } } -/// ``` -/// -/// Within the `...` term: -/// -/// * the variable `'a` have a debruijn index of 1 and index 0 -/// * the variable `'b` have a debruijn index of 1 and index 1 -/// * the variable `'c` have a debruijn index of 0 and index 0 -/// * the variable `'d` have a debruijn index of 0 and index 1 -/// -/// The variables `'a` and `'b` both have debruijn index of 1 because, -/// counting out, they are the 2nd binder enclosing `...`. The indices -/// identify the location *within* that binder. -/// -/// The variables `'c` and `'d` both have debruijn index of 0 because -/// they appear in the *innermost* binder enclosing the `...`. The -/// indices identify the location *within* that binder. -#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)] -pub struct BoundVar { - /// Debruijn index, which identifies the binder. - pub debruijn: DebruijnIndex, - /// Index within the binder. - pub index: usize, -} - -impl BoundVar { - /// Creates a new bound variable. - pub fn new(debruijn: DebruijnIndex, index: usize) -> Self { - Self { debruijn, index } - } - - /// Casts the bound variable to a type. - pub fn to_ty<I: Interner>(self, interner: I) -> Ty<I> { - TyKind::<I>::BoundVar(self).intern(interner) - } - - /// Wrap the bound variable in a lifetime. - pub fn to_lifetime<I: Interner>(self, interner: I) -> Lifetime<I> { - LifetimeData::<I>::BoundVar(self).intern(interner) - } - - /// Wraps the bound variable in a constant. - pub fn to_const<I: Interner>(self, interner: I, ty: Ty<I>) -> Const<I> { - ConstData { - ty, - value: ConstValue::<I>::BoundVar(self), - } - .intern(interner) - } - - /// True if this variable is bound within the `amount` innermost binders. - pub fn bound_within(self, outer_binder: DebruijnIndex) -> bool { - self.debruijn.within(outer_binder) - } - - /// Adjusts the debruijn index (see [`DebruijnIndex::shifted_in`]). - #[must_use] - pub fn shifted_in(self) -> Self { - BoundVar::new(self.debruijn.shifted_in(), self.index) - } - - /// Adjusts the debruijn index (see [`DebruijnIndex::shifted_in`]). - #[must_use] - pub fn shifted_in_from(self, outer_binder: DebruijnIndex) -> Self { - BoundVar::new(self.debruijn.shifted_in_from(outer_binder), self.index) - } - - /// Adjusts the debruijn index (see [`DebruijnIndex::shifted_in`]). - #[must_use] - pub fn shifted_out(self) -> Option<Self> { - self.debruijn - .shifted_out() - .map(|db| BoundVar::new(db, self.index)) - } - - /// Adjusts the debruijn index (see [`DebruijnIndex::shifted_in`]). - #[must_use] - pub fn shifted_out_to(self, outer_binder: DebruijnIndex) -> Option<Self> { - self.debruijn - .shifted_out_to(outer_binder) - .map(|db| BoundVar::new(db, self.index)) - } - - /// Return the index of the bound variable, but only if it is bound - /// at the innermost binder. Otherwise, returns `None`. - pub fn index_if_innermost(self) -> Option<usize> { - self.index_if_bound_at(DebruijnIndex::INNERMOST) - } - - /// Return the index of the bound variable, but only if it is bound - /// at the innermost binder. Otherwise, returns `None`. - pub fn index_if_bound_at(self, debruijn: DebruijnIndex) -> Option<usize> { - if self.debruijn == debruijn { - Some(self.index) - } else { - None - } - } -} - -/// References the binder at the given depth. The index is a [de -/// Bruijn index], so it counts back through the in-scope binders, -/// with 0 being the innermost binder. This is used in impls and -/// the like. For example, if we had a rule like `for<T> { (T: -/// Clone) :- (T: Copy) }`, then `T` would be represented as a -/// `BoundVar(0)` (as the `for` is the innermost binder). -/// -/// [de Bruijn index]: https://en.wikipedia.org/wiki/De_Bruijn_index -#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)] -pub struct DebruijnIndex { - depth: u32, -} - -impl DebruijnIndex { - /// Innermost index. - pub const INNERMOST: DebruijnIndex = DebruijnIndex { depth: 0 }; - /// One level higher than the innermost index. - pub const ONE: DebruijnIndex = DebruijnIndex { depth: 1 }; - - /// Creates a new de Bruijn index with a given depth. - pub fn new(depth: u32) -> Self { - DebruijnIndex { depth } - } - - /// Depth of the De Bruijn index, counting from 0 starting with - /// the innermost binder. - pub fn depth(self) -> u32 { - self.depth - } - - /// True if the binder identified by this index is within the - /// binder identified by the index `outer_binder`. - /// - /// # Example - /// - /// Imagine you have the following binders in scope - /// - /// ```ignore - /// forall<a> forall<b> forall<c> - /// ``` - /// - /// then the Debruijn index for `c` would be `0`, the index for - /// `b` would be 1, and so on. Now consider the following calls: - /// - /// * `c.within(a) = true` - /// * `b.within(a) = true` - /// * `a.within(a) = false` - /// * `a.within(c) = false` - pub fn within(self, outer_binder: DebruijnIndex) -> bool { - self < outer_binder - } - - /// Returns the resulting index when this value is moved into - /// through one binder. - #[must_use] - pub fn shifted_in(self) -> DebruijnIndex { - self.shifted_in_from(DebruijnIndex::ONE) - } - - /// Update this index in place by shifting it "in" through - /// `amount` number of binders. - pub fn shift_in(&mut self) { - *self = self.shifted_in(); - } - - /// Adds `outer_binder` levels to the `self` index. Intuitively, this - /// shifts the `self` index, which was valid at the outer binder, - /// so that it is valid at the innermost binder. - /// - /// Example: Assume that the following binders are in scope: - /// - /// ```ignore - /// for<A> for<B> for<C> for<D> - /// ^ outer binder - /// ``` - /// - /// Assume further that the `outer_binder` argument is 2, - /// which means that it is referring to the `for<B>` binder - /// (since `D` would be the innermost binder). - /// - /// This means that `self` is relative to the binder `B` -- so - /// if `self` is 0 (`INNERMOST`), then it refers to `B`, - /// and if `self` is 1, then it refers to `A`. - /// - /// We will return as follows: - /// - /// * `0.shifted_in_from(2) = 2` -- i.e., `B`, when shifted in to the binding level `D`, has index 2 - /// * `1.shifted_in_from(2) = 3` -- i.e., `A`, when shifted in to the binding level `D`, has index 3 - /// * `2.shifted_in_from(1) = 3` -- here, we changed the `outer_binder` to refer to `C`. - /// Therefore `2` (relative to `C`) refers to `A`, so the result is still 3 (since `A`, relative to the - /// innermost binder, has index 3). - #[must_use] - pub fn shifted_in_from(self, outer_binder: DebruijnIndex) -> DebruijnIndex { - DebruijnIndex::new(self.depth() + outer_binder.depth()) - } - - /// Returns the resulting index when this value is moved out from - /// `amount` number of new binders. - #[must_use] - pub fn shifted_out(self) -> Option<DebruijnIndex> { - self.shifted_out_to(DebruijnIndex::ONE) - } - - /// Update in place by shifting out from `amount` binders. - pub fn shift_out(&mut self) { - *self = self.shifted_out().unwrap(); - } - - /// Subtracts `outer_binder` levels from the `self` index. Intuitively, this - /// shifts the `self` index, which was valid at the innermost - /// binder, to one that is valid at the binder `outer_binder`. - /// - /// This will return `None` if the `self` index is internal to the - /// outer binder (i.e., if `self < outer_binder`). - /// - /// Example: Assume that the following binders are in scope: - /// - /// ```ignore - /// for<A> for<B> for<C> for<D> - /// ^ outer binder - /// ``` - /// - /// Assume further that the `outer_binder` argument is 2, - /// which means that it is referring to the `for<B>` binder - /// (since `D` would be the innermost binder). - /// - /// This means that the result is relative to the binder `B` -- so - /// if `self` is 0 (`INNERMOST`), then it refers to `B`, - /// and if `self` is 1, then it refers to `A`. - /// - /// We will return as follows: - /// - /// * `1.shifted_out_to(2) = None` -- i.e., the binder for `C` can't be named from the binding level `B` - /// * `3.shifted_out_to(2) = Some(1)` -- i.e., `A`, when shifted out to the binding level `B`, has index 1 - pub fn shifted_out_to(self, outer_binder: DebruijnIndex) -> Option<DebruijnIndex> { - if self.within(outer_binder) { - None - } else { - Some(DebruijnIndex::new(self.depth() - outer_binder.depth())) - } - } -} - -/// A "DynTy" represents a trait object (`dyn Trait`). Trait objects -/// are conceptually very related to an "existential type" of the form -/// `exists<T> { T: Trait }` (another example of such type is `impl Trait`). -/// `DynTy` represents the bounds on that type. -/// -/// The "bounds" here represents the unknown self type. So, a type like -/// `dyn for<'a> Fn(&'a u32)` would be represented with two-levels of -/// binder, as "depicted" here: -/// -/// ```notrust -/// exists<type> { -/// vec![ -/// // A QuantifiedWhereClause: -/// forall<region> { ^1.0: Fn(&^0.0 u32) } -/// ] -/// } -/// ``` -/// -/// The outer `exists<type>` binder indicates that there exists -/// some type that meets the criteria within, but that type is not -/// known. It is referenced within the type using `^1.0`, indicating -/// a bound type with debruijn index 1 (i.e., skipping through one -/// level of binder). -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner)] -pub struct DynTy<I: Interner> { - /// The unknown self type. - pub bounds: Binders<QuantifiedWhereClauses<I>>, - /// Lifetime of the `DynTy`. - pub lifetime: Lifetime<I>, -} - -impl<I: Interner> Copy for DynTy<I> -where - I::InternedLifetime: Copy, - I::InternedQuantifiedWhereClauses: Copy, - I::InternedVariableKinds: Copy, -{ -} - -/// A type, lifetime or constant whose value is being inferred. -#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)] -pub struct InferenceVar { - index: u32, -} - -impl From<u32> for InferenceVar { - fn from(index: u32) -> InferenceVar { - InferenceVar { index } - } -} - -impl InferenceVar { - /// Gets the underlying index value. - pub fn index(self) -> u32 { - self.index - } - - /// Wraps the inference variable in a type. - pub fn to_ty<I: Interner>(self, interner: I, kind: TyVariableKind) -> Ty<I> { - TyKind::<I>::InferenceVar(self, kind).intern(interner) - } - - /// Wraps the inference variable in a lifetime. - pub fn to_lifetime<I: Interner>(self, interner: I) -> Lifetime<I> { - LifetimeData::<I>::InferenceVar(self).intern(interner) - } - - /// Wraps the inference variable in a constant. - pub fn to_const<I: Interner>(self, interner: I, ty: Ty<I>) -> Const<I> { - ConstData { - ty, - value: ConstValue::<I>::InferenceVar(self), - } - .intern(interner) - } -} - -/// A function signature. -#[derive(Clone, Copy, PartialEq, Eq, Hash, HasInterner, Debug)] -#[allow(missing_docs)] -pub struct FnSig<I: Interner> { - pub abi: I::FnAbi, - pub safety: Safety, - pub variadic: bool, -} -/// A wrapper for the substs on a Fn. -#[derive(Clone, PartialEq, Eq, Hash, HasInterner, TypeFoldable, TypeVisitable)] -pub struct FnSubst<I: Interner>(pub Substitution<I>); - -impl<I: Interner> Copy for FnSubst<I> where I::InternedSubstitution: Copy {} - -/// for<'a...'z> X -- all binders are instantiated at once, -/// and we use deBruijn indices within `self.ty` -#[derive(Clone, PartialEq, Eq, Hash, HasInterner)] -#[allow(missing_docs)] -pub struct FnPointer<I: Interner> { - pub num_binders: usize, - pub sig: FnSig<I>, - pub substitution: FnSubst<I>, -} - -impl<I: Interner> Copy for FnPointer<I> where I::InternedSubstitution: Copy {} - -impl<I: Interner> FnPointer<I> { - /// Represent the current `Fn` as if it was wrapped in `Binders` - pub fn into_binders(self, interner: I) -> Binders<FnSubst<I>> { - Binders::new( - VariableKinds::from_iter( - interner, - (0..self.num_binders).map(|_| VariableKind::Lifetime), - ), - self.substitution, - ) - } - - /// Represent the current `Fn` as if it was wrapped in `Binders` - pub fn as_binders(&self, interner: I) -> Binders<&FnSubst<I>> { - Binders::new( - VariableKinds::from_iter( - interner, - (0..self.num_binders).map(|_| VariableKind::Lifetime), - ), - &self.substitution, - ) - } -} - -/// Constants. -#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)] -pub struct Const<I: Interner> { - interned: I::InternedConst, -} - -impl<I: Interner> Const<I> { - /// Create a `Const` using something that can be cast to const data. - pub fn new(interner: I, data: impl CastTo<ConstData<I>>) -> Self { - Const { - interned: I::intern_const(interner, data.cast(interner)), - } - } - - /// Gets the interned constant. - pub fn interned(&self) -> &I::InternedConst { - &self.interned - } - - /// Gets the constant data from the interner. - pub fn data(&self, interner: I) -> &ConstData<I> { - I::const_data(interner, &self.interned) - } - - /// If this is a `ConstData::BoundVar(d)`, returns `Some(d)` else `None`. - pub fn bound_var(&self, interner: I) -> Option<BoundVar> { - if let ConstValue::BoundVar(bv) = &self.data(interner).value { - Some(*bv) - } else { - None - } - } - - /// If this is a `ConstData::InferenceVar(d)`, returns `Some(d)` else `None`. - pub fn inference_var(&self, interner: I) -> Option<InferenceVar> { - if let ConstValue::InferenceVar(iv) = &self.data(interner).value { - Some(*iv) - } else { - None - } - } - - /// True if this const is a "bound" const, and hence - /// needs to be shifted across binders. Meant for debug assertions. - pub fn needs_shift(&self, interner: I) -> bool { - match &self.data(interner).value { - ConstValue::BoundVar(_) => true, - ConstValue::InferenceVar(_) => false, - ConstValue::Placeholder(_) => false, - ConstValue::Concrete(_) => false, - } - } -} - -/// Constant data, containing the constant's type and value. -#[derive(Clone, PartialEq, Eq, Hash, HasInterner)] -pub struct ConstData<I: Interner> { - /// Type that holds the constant. - pub ty: Ty<I>, - /// The value of the constant. - pub value: ConstValue<I>, -} - -/// A constant value, not necessarily concrete. -#[derive(Clone, PartialEq, Eq, Hash, HasInterner)] -pub enum ConstValue<I: Interner> { - /// Bound var (e.g. a parameter). - BoundVar(BoundVar), - /// Constant whose value is being inferred. - InferenceVar(InferenceVar), - /// Lifetime on some yet-unknown placeholder. - Placeholder(PlaceholderIndex), - /// Concrete constant value. - Concrete(ConcreteConst<I>), -} - -impl<I: Interner> Copy for ConstValue<I> where I::InternedConcreteConst: Copy {} - -impl<I: Interner> ConstData<I> { - /// Wraps the constant data in a `Const`. - pub fn intern(self, interner: I) -> Const<I> { - Const::new(interner, self) - } -} - -/// Concrete constant, whose value is known (as opposed to -/// inferred constants and placeholders). -#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)] -pub struct ConcreteConst<I: Interner> { - /// The interned constant. - pub interned: I::InternedConcreteConst, -} - -impl<I: Interner> ConcreteConst<I> { - /// Checks whether two concrete constants are equal. - pub fn const_eq(&self, ty: &Ty<I>, other: &ConcreteConst<I>, interner: I) -> bool { - interner.const_eq(&ty.interned, &self.interned, &other.interned) - } -} - -/// A Rust lifetime. -#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)] -pub struct Lifetime<I: Interner> { - interned: I::InternedLifetime, -} - -impl<I: Interner> Lifetime<I> { - /// Create a lifetime from lifetime data - /// (or something that can be cast to lifetime data). - pub fn new(interner: I, data: impl CastTo<LifetimeData<I>>) -> Self { - Lifetime { - interned: I::intern_lifetime(interner, data.cast(interner)), - } - } - - /// Gets the interned value. - pub fn interned(&self) -> &I::InternedLifetime { - &self.interned - } - - /// Gets the lifetime data. - pub fn data(&self, interner: I) -> &LifetimeData<I> { - I::lifetime_data(interner, &self.interned) - } - - /// If this is a `Lifetime::BoundVar(d)`, returns `Some(d)` else `None`. - pub fn bound_var(&self, interner: I) -> Option<BoundVar> { - if let LifetimeData::BoundVar(bv) = self.data(interner) { - Some(*bv) - } else { - None - } - } - - /// If this is a `Lifetime::InferenceVar(d)`, returns `Some(d)` else `None`. - pub fn inference_var(&self, interner: I) -> Option<InferenceVar> { - if let LifetimeData::InferenceVar(depth) = self.data(interner) { - Some(*depth) - } else { - None - } - } - - /// True if this lifetime is a "bound" lifetime, and hence - /// needs to be shifted across binders. Meant for debug assertions. - pub fn needs_shift(&self, interner: I) -> bool { - match self.data(interner) { - LifetimeData::BoundVar(_) => true, - LifetimeData::InferenceVar(_) => false, - LifetimeData::Placeholder(_) => false, - LifetimeData::Static => false, - LifetimeData::Erased => false, - LifetimeData::Phantom(..) => unreachable!(), - } - } - - ///compute type flags for Lifetime - fn compute_flags(&self, interner: I) -> TypeFlags { - match self.data(interner) { - LifetimeData::InferenceVar(_) => { - TypeFlags::HAS_RE_INFER - | TypeFlags::HAS_FREE_LOCAL_REGIONS - | TypeFlags::HAS_FREE_REGIONS - } - LifetimeData::Placeholder(_) => { - TypeFlags::HAS_RE_PLACEHOLDER - | TypeFlags::HAS_FREE_LOCAL_REGIONS - | TypeFlags::HAS_FREE_REGIONS - } - LifetimeData::Static => TypeFlags::HAS_FREE_REGIONS, - LifetimeData::Phantom(_, _) => TypeFlags::empty(), - LifetimeData::BoundVar(_) => TypeFlags::HAS_RE_LATE_BOUND, - LifetimeData::Erased => TypeFlags::HAS_RE_ERASED, - } - } -} - -/// Lifetime data, including what kind of lifetime it is and what it points to. -#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)] -pub enum LifetimeData<I: Interner> { - /// See TyKind::BoundVar. - BoundVar(BoundVar), - /// Lifetime whose value is being inferred. - InferenceVar(InferenceVar), - /// Lifetime on some yet-unknown placeholder. - Placeholder(PlaceholderIndex), - /// Static lifetime - Static, - /// An erased lifetime, used by rustc to improve caching when we doesn't - /// care about lifetimes - Erased, - /// Lifetime on phantom data. - Phantom(Void, PhantomData<I>), -} - -impl<I: Interner> LifetimeData<I> { - /// Wrap the lifetime data in a lifetime. - pub fn intern(self, interner: I) -> Lifetime<I> { - Lifetime::new(interner, self) - } -} - -/// Index of an universally quantified parameter in the environment. -/// Two indexes are required, the one of the universe itself -/// and the relative index inside the universe. -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct PlaceholderIndex { - /// Index *of* the universe. - pub ui: UniverseIndex, - /// Index *in* the universe. - pub idx: usize, -} - -impl PlaceholderIndex { - /// Wrap the placeholder instance in a lifetime. - pub fn to_lifetime<I: Interner>(self, interner: I) -> Lifetime<I> { - LifetimeData::<I>::Placeholder(self).intern(interner) - } - - /// Create an interned type. - pub fn to_ty<I: Interner>(self, interner: I) -> Ty<I> { - TyKind::Placeholder(self).intern(interner) - } - - /// Wrap the placeholder index in a constant. - pub fn to_const<I: Interner>(self, interner: I, ty: Ty<I>) -> Const<I> { - ConstData { - ty, - value: ConstValue::Placeholder(self), - } - .intern(interner) - } -} -/// Represents some extra knowledge we may have about the type variable. -/// ```ignore -/// let x: &[u32]; -/// let i = 1; -/// x[i] -/// ``` -/// In this example, `i` is known to be some type of integer. We can infer that -/// it is `usize` because that is the only integer type that slices have an -/// `Index` impl for. `i` would have a `TyVariableKind` of `Integer` to guide the -/// inference process. -#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] -#[allow(missing_docs)] -pub enum TyVariableKind { - General, - Integer, - Float, -} - -/// The "kind" of variable. Type, lifetime or constant. -#[derive(Clone, PartialEq, Eq, Hash)] -#[allow(missing_docs)] -pub enum VariableKind<I: Interner> { - Ty(TyVariableKind), - Lifetime, - Const(Ty<I>), -} - -impl<I: Interner> interner::HasInterner for VariableKind<I> { - type Interner = I; -} - -impl<I: Interner> Copy for VariableKind<I> where I::InternedType: Copy {} - -impl<I: Interner> VariableKind<I> { - fn to_bound_variable(&self, interner: I, bound_var: BoundVar) -> GenericArg<I> { - match self { - VariableKind::Ty(_) => { - GenericArgData::Ty(TyKind::BoundVar(bound_var).intern(interner)).intern(interner) - } - VariableKind::Lifetime => { - GenericArgData::Lifetime(LifetimeData::BoundVar(bound_var).intern(interner)) - .intern(interner) - } - VariableKind::Const(ty) => GenericArgData::Const( - ConstData { - ty: ty.clone(), - value: ConstValue::BoundVar(bound_var), - } - .intern(interner), - ) - .intern(interner), - } - } -} - -/// A generic argument, see `GenericArgData` for more information. -#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)] -pub struct GenericArg<I: Interner> { - interned: I::InternedGenericArg, -} - -impl<I: Interner> GenericArg<I> { - /// Constructs a generic argument using `GenericArgData`. - pub fn new(interner: I, data: GenericArgData<I>) -> Self { - let interned = I::intern_generic_arg(interner, data); - GenericArg { interned } - } - - /// Gets the interned value. - pub fn interned(&self) -> &I::InternedGenericArg { - &self.interned - } - - /// Gets the underlying data. - pub fn data(&self, interner: I) -> &GenericArgData<I> { - I::generic_arg_data(interner, &self.interned) - } - - /// Asserts that this is a type argument. - pub fn assert_ty_ref(&self, interner: I) -> &Ty<I> { - self.ty(interner).unwrap() - } - - /// Asserts that this is a lifetime argument. - pub fn assert_lifetime_ref(&self, interner: I) -> &Lifetime<I> { - self.lifetime(interner).unwrap() - } - - /// Asserts that this is a constant argument. - pub fn assert_const_ref(&self, interner: I) -> &Const<I> { - self.constant(interner).unwrap() - } - - /// Checks whether the generic argument is a type. - pub fn is_ty(&self, interner: I) -> bool { - match self.data(interner) { - GenericArgData::Ty(_) => true, - GenericArgData::Lifetime(_) => false, - GenericArgData::Const(_) => false, - } - } - - /// Returns the type if it is one, `None` otherwise. - pub fn ty(&self, interner: I) -> Option<&Ty<I>> { - match self.data(interner) { - GenericArgData::Ty(t) => Some(t), - _ => None, - } - } - - /// Returns the lifetime if it is one, `None` otherwise. - pub fn lifetime(&self, interner: I) -> Option<&Lifetime<I>> { - match self.data(interner) { - GenericArgData::Lifetime(t) => Some(t), - _ => None, - } - } - - /// Returns the constant if it is one, `None` otherwise. - pub fn constant(&self, interner: I) -> Option<&Const<I>> { - match self.data(interner) { - GenericArgData::Const(c) => Some(c), - _ => None, - } - } - - /// Compute type flags for GenericArg<I> - fn compute_flags(&self, interner: I) -> TypeFlags { - match self.data(interner) { - GenericArgData::Ty(ty) => ty.data(interner).flags, - GenericArgData::Lifetime(lifetime) => lifetime.compute_flags(interner), - GenericArgData::Const(constant) => { - let data = constant.data(interner); - let flags = data.ty.data(interner).flags; - match data.value { - ConstValue::BoundVar(_) => flags, - ConstValue::InferenceVar(_) => { - flags | TypeFlags::HAS_CT_INFER | TypeFlags::STILL_FURTHER_SPECIALIZABLE - } - ConstValue::Placeholder(_) => { - flags - | TypeFlags::HAS_CT_PLACEHOLDER - | TypeFlags::STILL_FURTHER_SPECIALIZABLE - } - ConstValue::Concrete(_) => flags, - } - } - } - } -} - -/// Generic arguments data. -#[derive(Clone, PartialEq, Eq, Hash, TypeVisitable, TypeFoldable, Zip)] -pub enum GenericArgData<I: Interner> { - /// Type argument - Ty(Ty<I>), - /// Lifetime argument - Lifetime(Lifetime<I>), - /// Constant argument - Const(Const<I>), -} - -impl<I: Interner> Copy for GenericArgData<I> -where - I::InternedType: Copy, - I::InternedLifetime: Copy, - I::InternedConst: Copy, -{ -} - -impl<I: Interner> GenericArgData<I> { - /// Create an interned type. - pub fn intern(self, interner: I) -> GenericArg<I> { - GenericArg::new(interner, self) - } -} - -/// A value with an associated variable kind. -#[derive(Clone, PartialEq, Eq, Hash)] -pub struct WithKind<I: Interner, T> { - /// The associated variable kind. - pub kind: VariableKind<I>, - /// The wrapped value. - value: T, -} - -impl<I: Interner, T: Copy> Copy for WithKind<I, T> where I::InternedType: Copy {} - -impl<I: Interner, T> HasInterner for WithKind<I, T> { - type Interner = I; -} - -impl<I: Interner, T> From<WithKind<I, T>> for (VariableKind<I>, T) { - fn from(with_kind: WithKind<I, T>) -> Self { - (with_kind.kind, with_kind.value) - } -} - -impl<I: Interner, T> WithKind<I, T> { - /// Creates a `WithKind` from a variable kind and a value. - pub fn new(kind: VariableKind<I>, value: T) -> Self { - Self { kind, value } - } - - /// Maps the value in `WithKind`. - pub fn map<U, OP>(self, op: OP) -> WithKind<I, U> - where - OP: FnOnce(T) -> U, - { - WithKind { - kind: self.kind, - value: op(self.value), - } - } - - /// Maps a function taking `WithKind<I, &T>` over `&WithKind<I, T>`. - pub fn map_ref<U, OP>(&self, op: OP) -> WithKind<I, U> - where - OP: FnOnce(&T) -> U, - { - WithKind { - kind: self.kind.clone(), - value: op(&self.value), - } - } - - /// Extract the value, ignoring the variable kind. - pub fn skip_kind(&self) -> &T { - &self.value - } -} - -/// A variable kind with universe index. -#[allow(type_alias_bounds)] -pub type CanonicalVarKind<I: Interner> = WithKind<I, UniverseIndex>; - -/// An alias, which is a trait indirection such as a projection or opaque type. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner, Zip)] -pub enum AliasTy<I: Interner> { - /// An associated type projection. - Projection(ProjectionTy<I>), - /// An opaque type. - Opaque(OpaqueTy<I>), -} - -impl<I: Interner> Copy for AliasTy<I> where I::InternedSubstitution: Copy {} - -impl<I: Interner> AliasTy<I> { - /// Create an interned type for this alias. - pub fn intern(self, interner: I) -> Ty<I> { - Ty::new(interner, self) - } - - /// Compute type flags for aliases - fn compute_flags(&self, interner: I) -> TypeFlags { - match self { - AliasTy::Projection(projection_ty) => { - TypeFlags::HAS_TY_PROJECTION | projection_ty.substitution.compute_flags(interner) - } - AliasTy::Opaque(opaque_ty) => { - TypeFlags::HAS_TY_OPAQUE | opaque_ty.substitution.compute_flags(interner) - } - } - } -} - -/// A projection `<P0 as TraitName<P1..Pn>>::AssocItem<Pn+1..Pm>`. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner)] -pub struct ProjectionTy<I: Interner> { - /// The id for the associated type member. - pub associated_ty_id: AssocTypeId<I>, - /// The substitution for the projection. - pub substitution: Substitution<I>, -} - -impl<I: Interner> Copy for ProjectionTy<I> where I::InternedSubstitution: Copy {} - -/// An opaque type `opaque type T<..>: Trait = HiddenTy`. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner)] -pub struct OpaqueTy<I: Interner> { - /// The id for the opaque type. - pub opaque_ty_id: OpaqueTyId<I>, - /// The substitution for the opaque type. - pub substitution: Substitution<I>, -} - -impl<I: Interner> Copy for OpaqueTy<I> where I::InternedSubstitution: Copy {} - -/// A trait reference describes the relationship between a type and a trait. -/// This can be used in two forms: -/// - `P0: Trait<P1..Pn>` (e.g. `i32: Copy`), which mentions that the type -/// implements the trait. -/// - `<P0 as Trait<P1..Pn>>` (e.g. `i32 as Copy`), which casts the type to -/// that specific trait. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner)] -pub struct TraitRef<I: Interner> { - /// The trait id. - pub trait_id: TraitId<I>, - /// The substitution, containing both the `Self` type and the parameters. - pub substitution: Substitution<I>, -} - -impl<I: Interner> Copy for TraitRef<I> where I::InternedSubstitution: Copy {} - -impl<I: Interner> TraitRef<I> { - /// Gets all type parameters in this trait ref, including `Self`. - pub fn type_parameters(&self, interner: I) -> impl Iterator<Item = Ty<I>> + '_ { - self.substitution - .iter(interner) - .filter_map(move |p| p.ty(interner)) - .cloned() - } - - /// Gets the type parameters of the `Self` type in this trait ref. - pub fn self_type_parameter(&self, interner: I) -> Ty<I> { - self.type_parameters(interner).next().unwrap() - } - - /// Construct a `FromEnv` using this trait ref. - pub fn from_env(self) -> FromEnv<I> { - FromEnv::Trait(self) - } - - /// Construct a `WellFormed` using this trait ref. - pub fn well_formed(self) -> WellFormed<I> { - WellFormed::Trait(self) - } -} - -/// Lifetime outlives, which for `'a: 'b`` checks that the lifetime `'a` -/// is a superset of the value of `'b`. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner, Zip)] -#[allow(missing_docs)] -pub struct LifetimeOutlives<I: Interner> { - pub a: Lifetime<I>, - pub b: Lifetime<I>, -} - -impl<I: Interner> Copy for LifetimeOutlives<I> where I::InternedLifetime: Copy {} - -/// Type outlives, which for `T: 'a` checks that the type `T` -/// lives at least as long as the lifetime `'a` -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner, Zip)] -pub struct TypeOutlives<I: Interner> { - /// The type which must outlive the given lifetime. - pub ty: Ty<I>, - /// The lifetime which the type must outlive. - pub lifetime: Lifetime<I>, -} - -impl<I: Interner> Copy for TypeOutlives<I> -where - I::InternedLifetime: Copy, - I::InternedType: Copy, -{ -} - -/// Where clauses that can be written by a Rust programmer. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeSuperVisitable, HasInterner, Zip)] -pub enum WhereClause<I: Interner> { - /// Type implements a trait. - Implemented(TraitRef<I>), - /// Type is equal to an alias. - AliasEq(AliasEq<I>), - /// One lifetime outlives another. - LifetimeOutlives(LifetimeOutlives<I>), - /// Type outlives a lifetime. - TypeOutlives(TypeOutlives<I>), -} - -impl<I: Interner> Copy for WhereClause<I> -where - I::InternedSubstitution: Copy, - I::InternedLifetime: Copy, - I::InternedType: Copy, -{ -} - -/// Checks whether a type or trait ref is well-formed. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner, Zip)] -pub enum WellFormed<I: Interner> { - /// A predicate which is true when some trait ref is well-formed. - /// For example, given the following trait definitions: - /// - /// ```notrust - /// trait Clone { ... } - /// trait Copy where Self: Clone { ... } - /// ``` - /// - /// then we have the following rule: - /// - /// ```notrust - /// WellFormed(?Self: Copy) :- ?Self: Copy, WellFormed(?Self: Clone) - /// ``` - Trait(TraitRef<I>), - - /// A predicate which is true when some type is well-formed. - /// For example, given the following type definition: - /// - /// ```notrust - /// struct Set<K> where K: Hash { - /// ... - /// } - /// ``` - /// - /// then we have the following rule: `WellFormedTy(Set<K>) :- Implemented(K: Hash)`. - Ty(Ty<I>), -} - -impl<I: Interner> Copy for WellFormed<I> -where - I::InternedType: Copy, - I::InternedSubstitution: Copy, -{ -} - -/// Checks whether a type or trait ref can be derived from the contents of the environment. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner, Zip)] -pub enum FromEnv<I: Interner> { - /// A predicate which enables deriving everything which should be true if we *know* that - /// some trait ref is well-formed. For example given the above trait definitions, we can use - /// `FromEnv(T: Copy)` to derive that `T: Clone`, like in: - /// - /// ```notrust - /// forall<T> { - /// if (FromEnv(T: Copy)) { - /// T: Clone - /// } - /// } - /// ``` - Trait(TraitRef<I>), - - /// A predicate which enables deriving everything which should be true if we *know* that - /// some type is well-formed. For example given the above type definition, we can use - /// `FromEnv(Set<K>)` to derive that `K: Hash`, like in: - /// - /// ```notrust - /// forall<K> { - /// if (FromEnv(Set<K>)) { - /// K: Hash - /// } - /// } - /// ``` - Ty(Ty<I>), -} - -impl<I: Interner> Copy for FromEnv<I> -where - I::InternedType: Copy, - I::InternedSubstitution: Copy, -{ -} - -/// A "domain goal" is a goal that is directly about Rust, rather than a pure -/// logical statement. As much as possible, the Chalk solver should avoid -/// decomposing this enum, and instead treat its values opaquely. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeSuperVisitable, HasInterner, Zip)] -pub enum DomainGoal<I: Interner> { - /// Simple goal that is true if the where clause is true. - Holds(WhereClause<I>), - - /// True if the type or trait ref is well-formed. - WellFormed(WellFormed<I>), - - /// True if the trait ref can be derived from in-scope where clauses. - FromEnv(FromEnv<I>), - - /// True if the alias type can be normalized to some other type - Normalize(Normalize<I>), - - /// True if a type is considered to have been "defined" by the current crate. This is true for - /// a `struct Foo { }` but false for a `#[upstream] struct Foo { }`. However, for fundamental types - /// like `Box<T>`, it is true if `T` is local. - IsLocal(Ty<I>), - - /// True if a type is *not* considered to have been "defined" by the current crate. This is - /// false for a `struct Foo { }` but true for a `#[upstream] struct Foo { }`. However, for - /// fundamental types like `Box<T>`, it is true if `T` is upstream. - IsUpstream(Ty<I>), - - /// True if a type and its input types are fully visible, known types. That is, there are no - /// unknown type parameters anywhere in this type. - /// - /// More formally, for each struct S<P0..Pn>: - /// forall<P0..Pn> { - /// IsFullyVisible(S<P0...Pn>) :- - /// IsFullyVisible(P0), - /// ... - /// IsFullyVisible(Pn) - /// } - /// - /// Note that any of these types can have lifetimes in their parameters too, but we only - /// consider type parameters. - IsFullyVisible(Ty<I>), - - /// Used to dictate when trait impls are allowed in the current (local) crate based on the - /// orphan rules. - /// - /// `LocalImplAllowed(T: Trait)` is true if the type T is allowed to impl trait Trait in - /// the current crate. Under the current rules, this is unconditionally true for all types if - /// the Trait is considered to be "defined" in the current crate. If that is not the case, then - /// `LocalImplAllowed(T: Trait)` can still be true if `IsLocal(T)` is true. - LocalImplAllowed(TraitRef<I>), - - /// Used to activate the "compatible modality" rules. Rules that introduce predicates that have - /// to do with "all compatible universes" should depend on this clause so that they only apply - /// if this is present. - Compatible, - - /// Used to indicate that a given type is in a downstream crate. Downstream crates contain the - /// current crate at some level of their dependencies. - /// - /// Since chalk does not actually see downstream types, this is usually introduced with - /// implication on a fresh, universally quantified type. - /// - /// forall<T> { if (DownstreamType(T)) { /* ... */ } } - /// - /// This makes a new type `T` available and makes `DownstreamType(T)` provable for that type. - DownstreamType(Ty<I>), - - /// Used to activate the "reveal mode", in which opaque (`impl Trait`) types can be equated - /// to their actual type. - Reveal, - - /// Used to indicate that a trait is object safe. - ObjectSafe(TraitId<I>), -} - -impl<I: Interner> Copy for DomainGoal<I> -where - I::InternedSubstitution: Copy, - I::InternedLifetime: Copy, - I::InternedType: Copy, -{ -} - -/// A where clause that can contain `forall<>` or `exists<>` quantifiers. -pub type QuantifiedWhereClause<I> = Binders<WhereClause<I>>; - -impl<I: Interner> WhereClause<I> { - /// Turn a where clause into the WF version of it i.e.: - /// * `Implemented(T: Trait)` maps to `WellFormed(T: Trait)` - /// * `ProjectionEq(<T as Trait>::Item = Foo)` maps to `WellFormed(<T as Trait>::Item = Foo)` - /// * any other clause maps to itself - pub fn into_well_formed_goal(self, interner: I) -> DomainGoal<I> { - match self { - WhereClause::Implemented(trait_ref) => WellFormed::Trait(trait_ref).cast(interner), - wc => wc.cast(interner), - } - } - - /// Same as `into_well_formed_goal` but with the `FromEnv` predicate instead of `WellFormed`. - pub fn into_from_env_goal(self, interner: I) -> DomainGoal<I> { - match self { - WhereClause::Implemented(trait_ref) => FromEnv::Trait(trait_ref).cast(interner), - wc => wc.cast(interner), - } - } - - /// If where clause is a `TraitRef`, returns its trait id. - pub fn trait_id(&self) -> Option<TraitId<I>> { - match self { - WhereClause::Implemented(trait_ref) => Some(trait_ref.trait_id), - WhereClause::AliasEq(_) => None, - WhereClause::LifetimeOutlives(_) => None, - WhereClause::TypeOutlives(_) => None, - } - } -} - -impl<I: Interner> QuantifiedWhereClause<I> { - /// As with `WhereClause::into_well_formed_goal`, but for a - /// quantified where clause. For example, `forall<T> { - /// Implemented(T: Trait)}` would map to `forall<T> { - /// WellFormed(T: Trait) }`. - pub fn into_well_formed_goal(self, interner: I) -> Binders<DomainGoal<I>> { - self.map(|wc| wc.into_well_formed_goal(interner)) - } - - /// As with `WhereClause::into_from_env_goal`, but mapped over any - /// binders. For example, `forall<T> { - /// Implemented(T: Trait)}` would map to `forall<T> { - /// FromEnv(T: Trait) }`. - pub fn into_from_env_goal(self, interner: I) -> Binders<DomainGoal<I>> { - self.map(|wc| wc.into_from_env_goal(interner)) - } - - /// If the underlying where clause is a `TraitRef`, returns its trait id. - pub fn trait_id(&self) -> Option<TraitId<I>> { - self.skip_binders().trait_id() - } -} - -impl<I: Interner> DomainGoal<I> { - /// Convert `Implemented(...)` into `FromEnv(...)`, but leave other - /// goals unchanged. - pub fn into_from_env_goal(self, interner: I) -> DomainGoal<I> { - match self { - DomainGoal::Holds(wc) => wc.into_from_env_goal(interner), - goal => goal, - } - } - - /// Lists generic arguments that are inputs to this domain goal. - pub fn inputs(&self, interner: I) -> Vec<GenericArg<I>> { - match self { - DomainGoal::Holds(WhereClause::AliasEq(alias_eq)) => { - vec![GenericArgData::Ty(alias_eq.alias.clone().intern(interner)).intern(interner)] - } - _ => Vec::new(), - } - } -} - -/// Equality goal: tries to prove that two values are equal. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, Zip)] -#[allow(missing_docs)] -pub struct EqGoal<I: Interner> { - pub a: GenericArg<I>, - pub b: GenericArg<I>, -} - -impl<I: Interner> Copy for EqGoal<I> where I::InternedGenericArg: Copy {} - -/// Subtype goal: tries to prove that `a` is a subtype of `b` -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, Zip)] -#[allow(missing_docs)] -pub struct SubtypeGoal<I: Interner> { - pub a: Ty<I>, - pub b: Ty<I>, -} - -impl<I: Interner> Copy for SubtypeGoal<I> where I::InternedType: Copy {} - -/// Proves that the given type alias **normalizes** to the given -/// type. A projection `T::Foo` normalizes to the type `U` if we can -/// **match it to an impl** and that impl has a `type Foo = V` where -/// `U = V`. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, Zip)] -#[allow(missing_docs)] -pub struct Normalize<I: Interner> { - pub alias: AliasTy<I>, - pub ty: Ty<I>, -} - -impl<I: Interner> Copy for Normalize<I> -where - I::InternedSubstitution: Copy, - I::InternedType: Copy, -{ -} - -/// Proves **equality** between an alias and a type. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, Zip)] -#[allow(missing_docs)] -pub struct AliasEq<I: Interner> { - pub alias: AliasTy<I>, - pub ty: Ty<I>, -} - -impl<I: Interner> Copy for AliasEq<I> -where - I::InternedSubstitution: Copy, - I::InternedType: Copy, -{ -} - -impl<I: Interner> HasInterner for AliasEq<I> { - type Interner = I; -} - -/// Indicates that the `value` is universally quantified over `N` -/// parameters of the given kinds, where `N == self.binders.len()`. A -/// variable with depth `i < N` refers to the value at -/// `self.binders[i]`. Variables with depth `>= N` are free. -/// -/// (IOW, we use deBruijn indices, where binders are introduced in reverse order -/// of `self.binders`.) -#[derive(Clone, PartialEq, Eq, Hash)] -pub struct Binders<T: HasInterner> { - /// The binders that quantify over the value. - pub binders: VariableKinds<T::Interner>, - - /// The value being quantified over. - value: T, -} - -impl<T: HasInterner + Copy> Copy for Binders<T> where - <T::Interner as Interner>::InternedVariableKinds: Copy -{ -} - -impl<T: HasInterner> HasInterner for Binders<T> { - type Interner = T::Interner; -} - -impl<T: Clone + HasInterner> Binders<&T> { - /// Converts a `Binders<&T>` to a `Binders<T>` by cloning `T`. - pub fn cloned(self) -> Binders<T> { - self.map(Clone::clone) - } -} - -impl<T: HasInterner> Binders<T> { - /// Create new binders. - pub fn new(binders: VariableKinds<T::Interner>, value: T) -> Self { - Self { binders, value } - } - - /// Wraps the given value in a binder without variables, i.e. `for<> - /// (value)`. Since our deBruijn indices count binders, not variables, this - /// is sometimes useful. - pub fn empty(interner: T::Interner, value: T) -> Self { - let binders = VariableKinds::empty(interner); - Self { binders, value } - } - - /// Skips the binder and returns the "bound" value. This is a - /// risky thing to do because it's easy to get confused about - /// De Bruijn indices and the like. `skip_binder` is only valid - /// when you are either extracting data that has nothing to - /// do with bound vars, or you are being very careful about - /// your depth accounting. - /// - /// Some examples where `skip_binder` is reasonable: - /// - /// - extracting the `TraitId` from a TraitRef; - /// - checking if there are any fields in a StructDatum - pub fn skip_binders(&self) -> &T { - &self.value - } - - /// Skips the binder and returns the "bound" value as well as the skipped free variables. This - /// is just as risky as [`skip_binders`][Self::skip_binders]. - pub fn into_value_and_skipped_binders(self) -> (T, VariableKinds<T::Interner>) { - (self.value, self.binders) - } - - /// Converts `&Binders<T>` to `Binders<&T>`. Produces new `Binders` - /// with cloned quantifiers containing a reference to the original - /// value, leaving the original in place. - pub fn as_ref(&self) -> Binders<&T> { - Binders { - binders: self.binders.clone(), - value: &self.value, - } - } - - /// Maps the binders by applying a function. - pub fn map<U, OP>(self, op: OP) -> Binders<U> - where - OP: FnOnce(T) -> U, - U: HasInterner<Interner = T::Interner>, - { - let value = op(self.value); - Binders { - binders: self.binders, - value, - } - } - - /// Transforms the inner value according to the given function; returns - /// `None` if the function returns `None`. - pub fn filter_map<U, OP>(self, op: OP) -> Option<Binders<U>> - where - OP: FnOnce(T) -> Option<U>, - U: HasInterner<Interner = T::Interner>, - { - let value = op(self.value)?; - Some(Binders { - binders: self.binders, - value, - }) - } - - /// Maps a function taking `Binders<&T>` over `&Binders<T>`. - pub fn map_ref<'a, U, OP>(&'a self, op: OP) -> Binders<U> - where - OP: FnOnce(&'a T) -> U, - U: HasInterner<Interner = T::Interner>, - { - self.as_ref().map(op) - } - - /// Creates a `Substitution` containing bound vars such that applying this - /// substitution will not change the value, i.e. `^0.0, ^0.1, ^0.2` and so - /// on. - pub fn identity_substitution(&self, interner: T::Interner) -> Substitution<T::Interner> { - Substitution::from_iter( - interner, - self.binders - .iter(interner) - .enumerate() - .map(|p| p.to_generic_arg(interner)), - ) - } - - /// Creates a fresh binders that contains a single type - /// variable. The result of the closure will be embedded in this - /// binder. Note that you should be careful with what you return - /// from the closure to account for the binder that will be added. - /// - /// XXX FIXME -- this is potentially a pretty footgun-y function. - pub fn with_fresh_type_var( - interner: T::Interner, - op: impl FnOnce(Ty<T::Interner>) -> T, - ) -> Binders<T> { - // The new variable is at the front and everything afterwards is shifted up by 1 - let new_var = TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(interner); - let value = op(new_var); - let binders = VariableKinds::from1(interner, VariableKind::Ty(TyVariableKind::General)); - Binders { binders, value } - } - - /// Returns the number of binders. - pub fn len(&self, interner: T::Interner) -> usize { - self.binders.len(interner) - } -} - -impl<T, I> Binders<Binders<T>> -where - T: TypeFoldable<I> + HasInterner<Interner = I>, - I: Interner, -{ - /// This turns two levels of binders (`for<A> for<B>`) into one level (`for<A, B>`). - pub fn fuse_binders(self, interner: T::Interner) -> Binders<T> { - let num_binders = self.len(interner); - // generate a substitution to shift the indexes of the inner binder: - let subst = Substitution::from_iter( - interner, - self.value - .binders - .iter(interner) - .enumerate() - .map(|(i, pk)| (i + num_binders, pk).to_generic_arg(interner)), - ); - let binders = VariableKinds::from_iter( - interner, - self.binders - .iter(interner) - .chain(self.value.binders.iter(interner)) - .cloned(), - ); - let value = self.value.substitute(interner, &subst); - Binders { binders, value } - } -} - -impl<T: HasInterner> From<Binders<T>> for (VariableKinds<T::Interner>, T) { - fn from(binders: Binders<T>) -> Self { - (binders.binders, binders.value) - } -} - -impl<T, I> Binders<T> -where - T: TypeFoldable<I> + HasInterner<Interner = I>, - I: Interner, -{ - /// Substitute `parameters` for the variables introduced by these - /// binders. So if the binders represent (e.g.) `<X, Y> { T }` and - /// parameters is the slice `[A, B]`, then returns `[X => A, Y => - /// B] T`. - pub fn substitute(self, interner: I, parameters: &(impl AsParameters<I> + ?Sized)) -> T { - let parameters = parameters.as_parameters(interner); - assert_eq!(self.binders.len(interner), parameters.len()); - Subst::apply(interner, parameters, self.value) - } -} - -/// Allows iterating over a Binders<Vec<T>>, for instance. -/// Each element will include the same set of parameter bounds. -impl<V, U> IntoIterator for Binders<V> -where - V: HasInterner + IntoIterator<Item = U>, - U: HasInterner<Interner = V::Interner>, -{ - type Item = Binders<U>; - type IntoIter = BindersIntoIterator<V>; - - fn into_iter(self) -> Self::IntoIter { - BindersIntoIterator { - iter: self.value.into_iter(), - binders: self.binders, - } - } -} - -/// `IntoIterator` for binders. -pub struct BindersIntoIterator<V: HasInterner + IntoIterator> { - iter: <V as IntoIterator>::IntoIter, - binders: VariableKinds<V::Interner>, -} - -impl<V> Iterator for BindersIntoIterator<V> -where - V: HasInterner + IntoIterator, - <V as IntoIterator>::Item: HasInterner<Interner = V::Interner>, -{ - type Item = Binders<<V as IntoIterator>::Item>; - fn next(&mut self) -> Option<Self::Item> { - self.iter - .next() - .map(|v| Binders::new(self.binders.clone(), v)) - } -} - -/// Represents one clause of the form `consequence :- conditions` where -/// `conditions = cond_1 && cond_2 && ...` is the conjunction of the individual -/// conditions. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner, Zip)] -pub struct ProgramClauseImplication<I: Interner> { - /// The consequence of the clause, which holds if the conditions holds. - pub consequence: DomainGoal<I>, - - /// The condition goals that should hold. - pub conditions: Goals<I>, - - /// The lifetime constraints that should be proven. - pub constraints: Constraints<I>, - - /// The relative priority of the implication. - pub priority: ClausePriority, -} - -/// Specifies how important an implication is. -#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] -pub enum ClausePriority { - /// High priority, the solver should prioritize this. - High, - - /// Low priority, this implication has lower chance to be relevant to the goal. - Low, -} - -impl std::ops::BitAnd for ClausePriority { - type Output = ClausePriority; - fn bitand(self, rhs: ClausePriority) -> Self::Output { - match (self, rhs) { - (ClausePriority::High, ClausePriority::High) => ClausePriority::High, - _ => ClausePriority::Low, - } - } -} - -/// Contains the data for a program clause. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, HasInterner, Zip)] -pub struct ProgramClauseData<I: Interner>(pub Binders<ProgramClauseImplication<I>>); - -impl<I: Interner> ProgramClauseImplication<I> { - /// Change the implication into an application holding a `FromEnv` goal. - pub fn into_from_env_clause(self, interner: I) -> ProgramClauseImplication<I> { - if self.conditions.is_empty(interner) { - ProgramClauseImplication { - consequence: self.consequence.into_from_env_goal(interner), - conditions: self.conditions.clone(), - constraints: self.constraints.clone(), - priority: self.priority, - } - } else { - self - } - } -} - -impl<I: Interner> ProgramClauseData<I> { - /// Change the program clause data into a `FromEnv` program clause. - pub fn into_from_env_clause(self, interner: I) -> ProgramClauseData<I> { - ProgramClauseData(self.0.map(|i| i.into_from_env_clause(interner))) - } - - /// Intern the program clause data. - pub fn intern(self, interner: I) -> ProgramClause<I> { - ProgramClause { - interned: interner.intern_program_clause(self), - } - } -} - -/// A program clause is a logic expression used to describe a part of the program. -#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)] -pub struct ProgramClause<I: Interner> { - interned: I::InternedProgramClause, -} - -impl<I: Interner> ProgramClause<I> { - /// Create a new program clause using `ProgramClauseData`. - pub fn new(interner: I, clause: ProgramClauseData<I>) -> Self { - let interned = interner.intern_program_clause(clause); - Self { interned } - } - - /// Change the clause into a `FromEnv` clause. - pub fn into_from_env_clause(self, interner: I) -> ProgramClause<I> { - let program_clause_data = self.data(interner); - let new_clause = program_clause_data.clone().into_from_env_clause(interner); - Self::new(interner, new_clause) - } - - /// Get the interned program clause. - pub fn interned(&self) -> &I::InternedProgramClause { - &self.interned - } - - /// Get the program clause data. - pub fn data(&self, interner: I) -> &ProgramClauseData<I> { - interner.program_clause_data(&self.interned) - } -} - -/// Wraps a "canonicalized item". Items are canonicalized as follows: -/// -/// All unresolved existential variables are "renumbered" according to their -/// first appearance; the kind/universe of the variable is recorded in the -/// `binders` field. -#[derive(Clone, Debug, PartialEq, Eq, Hash)] -pub struct Canonical<T: HasInterner> { - /// The item that is canonicalized. - pub value: T, - - /// The kind/universe of the variable. - pub binders: CanonicalVarKinds<T::Interner>, -} - -impl<T: HasInterner> HasInterner for Canonical<T> { - type Interner = T::Interner; -} - -/// A "universe canonical" value. This is a wrapper around a -/// `Canonical`, indicating that the universes within have been -/// "renumbered" to start from 0 and collapse unimportant -/// distinctions. -/// -/// To produce one of these values, use the `u_canonicalize` method. -#[derive(Clone, Debug, PartialEq, Eq, Hash)] -pub struct UCanonical<T: HasInterner> { - /// The wrapped `Canonical`. - pub canonical: Canonical<T>, - - /// The number of universes that have been collapsed. - pub universes: usize, -} - -impl<T: HasInterner> UCanonical<T> { - /// Checks whether the universe canonical value is a trivial - /// substitution (e.g. an identity substitution). - pub fn is_trivial_substitution( - &self, - interner: T::Interner, - canonical_subst: &Canonical<AnswerSubst<T::Interner>>, - ) -> bool { - let subst = &canonical_subst.value.subst; - assert_eq!( - self.canonical.binders.len(interner), - subst.as_slice(interner).len() - ); - subst.is_identity_subst(interner) - } - - /// Creates an identity substitution. - pub fn trivial_substitution(&self, interner: T::Interner) -> Substitution<T::Interner> { - let binders = &self.canonical.binders; - Substitution::from_iter( - interner, - binders - .iter(interner) - .enumerate() - .map(|(index, pk)| { - let bound_var = BoundVar::new(DebruijnIndex::INNERMOST, index); - match &pk.kind { - VariableKind::Ty(_) => { - GenericArgData::Ty(TyKind::BoundVar(bound_var).intern(interner)) - .intern(interner) - } - VariableKind::Lifetime => GenericArgData::Lifetime( - LifetimeData::BoundVar(bound_var).intern(interner), - ) - .intern(interner), - VariableKind::Const(ty) => GenericArgData::Const( - ConstData { - ty: ty.clone(), - value: ConstValue::BoundVar(bound_var), - } - .intern(interner), - ) - .intern(interner), - } - }) - .collect::<Vec<_>>(), - ) - } -} - -#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)] -/// A general goal; this is the full range of questions you can pose to Chalk. -pub struct Goal<I: Interner> { - interned: I::InternedGoal, -} - -impl<I: Interner> Goal<I> { - /// Create a new goal using `GoalData`. - pub fn new(interner: I, interned: GoalData<I>) -> Self { - let interned = I::intern_goal(interner, interned); - Self { interned } - } - - /// Gets the interned goal. - pub fn interned(&self) -> &I::InternedGoal { - &self.interned - } - - /// Gets the interned goal data. - pub fn data(&self, interner: I) -> &GoalData<I> { - interner.goal_data(&self.interned) - } - - /// Create a goal using a `forall` or `exists` quantifier. - pub fn quantify(self, interner: I, kind: QuantifierKind, binders: VariableKinds<I>) -> Goal<I> { - GoalData::Quantified(kind, Binders::new(binders, self)).intern(interner) - } - - /// Takes a goal `G` and turns it into `not { G }`. - pub fn negate(self, interner: I) -> Self { - GoalData::Not(self).intern(interner) - } - - /// Takes a goal `G` and turns it into `compatible { G }`. - pub fn compatible(self, interner: I) -> Self { - // compatible { G } desugars into: forall<T> { if (Compatible, DownstreamType(T)) { G } } - // This activates the compatible modality rules and introduces an anonymous downstream type - GoalData::Quantified( - QuantifierKind::ForAll, - Binders::with_fresh_type_var(interner, |ty| { - GoalData::Implies( - ProgramClauses::from_iter( - interner, - vec![DomainGoal::Compatible, DomainGoal::DownstreamType(ty)], - ), - self.shifted_in(interner), - ) - .intern(interner) - }), - ) - .intern(interner) - } - - /// Create an implication goal that holds if the predicates are true. - pub fn implied_by(self, interner: I, predicates: ProgramClauses<I>) -> Goal<I> { - GoalData::Implies(predicates, self).intern(interner) - } - - /// True if this goal is "trivially true" -- i.e., no work is - /// required to prove it. - pub fn is_trivially_true(&self, interner: I) -> bool { - match self.data(interner) { - GoalData::All(goals) => goals.is_empty(interner), - _ => false, - } - } -} - -impl<I> Goal<I> -where - I: Interner, -{ - /// Creates a single goal that only holds if a list of goals holds. - pub fn all<II>(interner: I, iter: II) -> Self - where - II: IntoIterator<Item = Goal<I>>, - { - let mut iter = iter.into_iter(); - if let Some(goal0) = iter.next() { - if let Some(goal1) = iter.next() { - // More than one goal to prove - let goals = Goals::from_iter( - interner, - Some(goal0).into_iter().chain(Some(goal1)).chain(iter), - ); - GoalData::All(goals).intern(interner) - } else { - // One goal to prove - goal0 - } - } else { - // No goals to prove, always true - GoalData::All(Goals::empty(interner)).intern(interner) - } - } -} - -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner, Zip)] -/// A general goal; this is the full range of questions you can pose to Chalk. -pub enum GoalData<I: Interner> { - /// Introduces a binding at depth 0, shifting other bindings up - /// (deBruijn index). - Quantified(QuantifierKind, Binders<Goal<I>>), - - /// A goal that holds given some clauses (like an if-statement). - Implies(ProgramClauses<I>, Goal<I>), - - /// List of goals that all should hold. - All(Goals<I>), - - /// Negation: the inner goal should not hold. - Not(Goal<I>), - - /// Make two things equal; the rules for doing so are well known to the logic - EqGoal(EqGoal<I>), - - /// Make one thing a subtype of another; the rules for doing so are well known to the logic - SubtypeGoal(SubtypeGoal<I>), - - /// A "domain goal" indicates some base sort of goal that can be - /// proven via program clauses - DomainGoal(DomainGoal<I>), - - /// Indicates something that cannot be proven to be true or false - /// definitively. This can occur with overflow but also with - /// unifications of skolemized variables like `forall<X,Y> { X = Y - /// }`. Of course, that statement is false, as there exist types - /// X, Y where `X = Y` is not true. But we treat it as "cannot - /// prove" so that `forall<X,Y> { not { X = Y } }` also winds up - /// as cannot prove. - CannotProve, -} - -impl<I: Interner> Copy for GoalData<I> -where - I::InternedType: Copy, - I::InternedLifetime: Copy, - I::InternedGenericArg: Copy, - I::InternedSubstitution: Copy, - I::InternedGoal: Copy, - I::InternedGoals: Copy, - I::InternedProgramClauses: Copy, - I::InternedVariableKinds: Copy, -{ -} - -impl<I: Interner> GoalData<I> { - /// Create an interned goal. - pub fn intern(self, interner: I) -> Goal<I> { - Goal::new(interner, self) - } -} - -/// Kinds of quantifiers in the logic, such as `forall` and `exists`. -#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)] -pub enum QuantifierKind { - /// Universal quantifier `ForAll`. - /// - /// A formula with the universal quantifier `forall(x). P(x)` is satisfiable - /// if and only if the subformula `P(x)` is true for all possible values for x. - ForAll, - - /// Existential quantifier `Exists`. - /// - /// A formula with the existential quantifier `exists(x). P(x)` is satisfiable - /// if and only if there exists at least one value for all possible values of x - /// which satisfies the subformula `P(x)`. - - /// In the context of chalk, the existential quantifier usually demands the - /// existence of exactly one instance (i.e. type) that satisfies the formula - /// (i.e. type constraints). More than one instance means that the result is ambiguous. - Exists, -} - -/// A constraint on lifetimes. -/// -/// When we search for solutions within the trait system, we essentially ignore -/// lifetime constraints, instead gathering them up to return with our solution -/// for later checking. This allows for decoupling between type and region -/// checking in the compiler. -#[derive(Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner, Zip)] -pub enum Constraint<I: Interner> { - /// Outlives constraint `'a: 'b`, indicating that the value of `'a` must be - /// a superset of the value of `'b`. - LifetimeOutlives(Lifetime<I>, Lifetime<I>), - - /// Type outlives constraint `T: 'a`, indicating that the type `T` must live - /// at least as long as the value of `'a`. - TypeOutlives(Ty<I>, Lifetime<I>), -} - -impl<I: Interner> Copy for Constraint<I> -where - I::InternedLifetime: Copy, - I::InternedType: Copy, -{ -} - -impl<I: Interner> Substitution<I> { - /// A substitution is an **identity substitution** if it looks - /// like this - /// - /// ```text - /// ?0 := ?0 - /// ?1 := ?1 - /// ?2 := ?2 - /// ... - /// ``` - /// - /// Basically, each value is mapped to a type or lifetime with its - /// same index. - pub fn is_identity_subst(&self, interner: I) -> bool { - self.iter(interner).zip(0..).all(|(generic_arg, index)| { - let index_db = BoundVar::new(DebruijnIndex::INNERMOST, index); - match generic_arg.data(interner) { - GenericArgData::Ty(ty) => match ty.kind(interner) { - TyKind::BoundVar(depth) => index_db == *depth, - _ => false, - }, - GenericArgData::Lifetime(lifetime) => match lifetime.data(interner) { - LifetimeData::BoundVar(depth) => index_db == *depth, - _ => false, - }, - GenericArgData::Const(constant) => match &constant.data(interner).value { - ConstValue::BoundVar(depth) => index_db == *depth, - _ => false, - }, - } - }) - } - - /// Apply the substitution to a value. - pub fn apply<T>(&self, value: T, interner: I) -> T - where - T: TypeFoldable<I>, - { - Substitute::apply(self, value, interner) - } - - /// Gets an iterator of all type parameters. - pub fn type_parameters(&self, interner: I) -> impl Iterator<Item = Ty<I>> + '_ { - self.iter(interner) - .filter_map(move |p| p.ty(interner)) - .cloned() - } - - /// Compute type flags for Substitution<I> - fn compute_flags(&self, interner: I) -> TypeFlags { - let mut flags = TypeFlags::empty(); - for generic_arg in self.iter(interner) { - flags |= generic_arg.compute_flags(interner); - } - flags - } -} - -#[derive(FallibleTypeFolder)] -struct SubstFolder<'i, I: Interner, A: AsParameters<I>> { - interner: I, - subst: &'i A, -} - -impl<I: Interner, A: AsParameters<I>> SubstFolder<'_, I, A> { - /// Index into the list of parameters. - pub fn at(&self, index: usize) -> &GenericArg<I> { - let interner = self.interner; - &self.subst.as_parameters(interner)[index] - } -} - -/// Convert a value to a list of parameters. -pub trait AsParameters<I: Interner> { - /// Convert the current value to parameters. - fn as_parameters(&self, interner: I) -> &[GenericArg<I>]; -} - -impl<I: Interner> AsParameters<I> for Substitution<I> { - #[allow(unreachable_code, unused_variables)] - fn as_parameters(&self, interner: I) -> &[GenericArg<I>] { - self.as_slice(interner) - } -} - -impl<I: Interner> AsParameters<I> for [GenericArg<I>] { - fn as_parameters(&self, _interner: I) -> &[GenericArg<I>] { - self - } -} - -impl<I: Interner> AsParameters<I> for [GenericArg<I>; 1] { - fn as_parameters(&self, _interner: I) -> &[GenericArg<I>] { - self - } -} - -impl<I: Interner> AsParameters<I> for Vec<GenericArg<I>> { - fn as_parameters(&self, _interner: I) -> &[GenericArg<I>] { - self - } -} - -impl<T, I: Interner> AsParameters<I> for &T -where - T: ?Sized + AsParameters<I>, -{ - fn as_parameters(&self, interner: I) -> &[GenericArg<I>] { - T::as_parameters(self, interner) - } -} - -/// An extension trait to anything that can be represented as list of `GenericArg`s that signifies -/// that it can applied as a substituion to a value -pub trait Substitute<I: Interner>: AsParameters<I> { - /// Apply the substitution to a value. - fn apply<T: TypeFoldable<I>>(&self, value: T, interner: I) -> T; -} - -impl<I: Interner, A: AsParameters<I>> Substitute<I> for A { - fn apply<T>(&self, value: T, interner: I) -> T - where - T: TypeFoldable<I>, - { - value - .try_fold_with( - &mut SubstFolder { - interner, - subst: self, - }, - DebruijnIndex::INNERMOST, - ) - .unwrap() - } -} - -/// Utility for converting a list of all the binders into scope -/// into references to those binders. Simply pair the binders with -/// the indices, and invoke `to_generic_arg()` on the `(binder, -/// index)` pair. The result will be a reference to a bound -/// variable of appropriate kind at the corresponding index. -pub trait ToGenericArg<I: Interner> { - /// Converts the binders in scope to references to those binders. - fn to_generic_arg(&self, interner: I) -> GenericArg<I> { - self.to_generic_arg_at_depth(interner, DebruijnIndex::INNERMOST) - } - - /// Converts the binders at the specified depth to references to those binders. - fn to_generic_arg_at_depth(&self, interner: I, debruijn: DebruijnIndex) -> GenericArg<I>; -} - -impl<'a, I: Interner> ToGenericArg<I> for (usize, &'a VariableKind<I>) { - fn to_generic_arg_at_depth(&self, interner: I, debruijn: DebruijnIndex) -> GenericArg<I> { - let &(index, binder) = self; - let bound_var = BoundVar::new(debruijn, index); - binder.to_bound_variable(interner, bound_var) - } -} - -impl<'i, I: Interner, A: AsParameters<I>> TypeFolder<I> for SubstFolder<'i, I, A> { - fn as_dyn(&mut self) -> &mut dyn TypeFolder<I> { - self - } - - fn fold_free_var_ty(&mut self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> Ty<I> { - assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST); - let ty = self.at(bound_var.index); - let ty = ty.assert_ty_ref(TypeFolder::interner(self)); - ty.clone() - .shifted_in_from(TypeFolder::interner(self), outer_binder) - } - - fn fold_free_var_lifetime( - &mut self, - bound_var: BoundVar, - outer_binder: DebruijnIndex, - ) -> Lifetime<I> { - assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST); - let l = self.at(bound_var.index); - let l = l.assert_lifetime_ref(TypeFolder::interner(self)); - l.clone() - .shifted_in_from(TypeFolder::interner(self), outer_binder) - } - - fn fold_free_var_const( - &mut self, - _ty: Ty<I>, - bound_var: BoundVar, - outer_binder: DebruijnIndex, - ) -> Const<I> { - assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST); - let c = self.at(bound_var.index); - let c = c.assert_const_ref(TypeFolder::interner(self)); - c.clone() - .shifted_in_from(TypeFolder::interner(self), outer_binder) - } - - fn interner(&self) -> I { - self.interner - } -} - -macro_rules! interned_slice_common { - ($seq:ident, $data:ident => $elem:ty, $intern:ident => $interned:ident) => { - /// List of interned elements. - #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)] - pub struct $seq<I: Interner> { - interned: I::$interned, - } - - impl<I: Interner> $seq<I> { - /// Get the interned elements. - pub fn interned(&self) -> &I::$interned { - &self.interned - } - - /// Returns a slice containing the elements. - pub fn as_slice(&self, interner: I) -> &[$elem] { - Interner::$data(interner, &self.interned) - } - - /// Index into the sequence. - pub fn at(&self, interner: I, index: usize) -> &$elem { - &self.as_slice(interner)[index] - } - - /// Create an empty sequence. - pub fn empty(interner: I) -> Self { - Self::from_iter(interner, None::<$elem>) - } - - /// Check whether this is an empty sequence. - pub fn is_empty(&self, interner: I) -> bool { - self.as_slice(interner).is_empty() - } - - /// Get an iterator over the elements of the sequence. - pub fn iter(&self, interner: I) -> std::slice::Iter<'_, $elem> { - self.as_slice(interner).iter() - } - - /// Get the length of the sequence. - pub fn len(&self, interner: I) -> usize { - self.as_slice(interner).len() - } - } - }; -} - -macro_rules! interned_slice { - ($seq:ident, $data:ident => $elem:ty, $intern:ident => $interned:ident) => { - interned_slice_common!($seq, $data => $elem, $intern => $interned); - - impl<I: Interner> $seq<I> { - /// Tries to create a sequence using an iterator of element-like things. - pub fn from_fallible<E>( - interner: I, - elements: impl IntoIterator<Item = Result<impl CastTo<$elem>, E>>, - ) -> Result<Self, E> { - Ok(Self { - interned: I::$intern(interner, elements.into_iter().casted(interner))?, - }) - } - - /// Create a sequence from elements - pub fn from_iter( - interner: I, - elements: impl IntoIterator<Item = impl CastTo<$elem>>, - ) -> Self { - Self::from_fallible( - interner, - elements - .into_iter() - .map(|el| -> Result<$elem, ()> { Ok(el.cast(interner)) }), - ) - .unwrap() - } - - /// Create a sequence from a single element. - pub fn from1(interner: I, element: impl CastTo<$elem>) -> Self { - Self::from_iter(interner, Some(element)) - } - } - }; -} - -interned_slice!( - QuantifiedWhereClauses, - quantified_where_clauses_data => QuantifiedWhereClause<I>, - intern_quantified_where_clauses => InternedQuantifiedWhereClauses -); - -interned_slice!( - ProgramClauses, - program_clauses_data => ProgramClause<I>, - intern_program_clauses => InternedProgramClauses -); - -interned_slice!( - VariableKinds, - variable_kinds_data => VariableKind<I>, - intern_generic_arg_kinds => InternedVariableKinds -); - -interned_slice!( - CanonicalVarKinds, - canonical_var_kinds_data => CanonicalVarKind<I>, - intern_canonical_var_kinds => InternedCanonicalVarKinds -); - -interned_slice!(Goals, goals_data => Goal<I>, intern_goals => InternedGoals); - -interned_slice!( - Constraints, - constraints_data => InEnvironment<Constraint<I>>, - intern_constraints => InternedConstraints -); - -interned_slice!( - Substitution, - substitution_data => GenericArg<I>, - intern_substitution => InternedSubstitution -); - -interned_slice_common!( - Variances, - variances_data => Variance, - intern_variance => InternedVariances -); - -impl<I: Interner> Variances<I> { - /// Tries to create a list of canonical variable kinds using an iterator. - pub fn from_fallible<E>( - interner: I, - variances: impl IntoIterator<Item = Result<Variance, E>>, - ) -> Result<Self, E> { - Ok(Variances { - interned: I::intern_variances(interner, variances.into_iter())?, - }) - } - - /// Creates a list of canonical variable kinds using an iterator. - pub fn from_iter(interner: I, variances: impl IntoIterator<Item = Variance>) -> Self { - Self::from_fallible( - interner, - variances - .into_iter() - .map(|p| -> Result<Variance, ()> { Ok(p) }), - ) - .unwrap() - } - - /// Creates a list of canonical variable kinds from a single canonical variable kind. - pub fn from1(interner: I, variance: Variance) -> Self { - Self::from_iter(interner, Some(variance)) - } -} - -/// Combines a substitution (`subst`) with a set of region constraints -/// (`constraints`). This represents the result of a query; the -/// substitution stores the values for the query's unknown variables, -/// and the constraints represents any region constraints that must -/// additionally be solved. -#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner)] -pub struct ConstrainedSubst<I: Interner> { - /// The substitution that is being constrained. - /// - /// NB: The `is_trivial` routine relies on the fact that `subst` is folded first. - pub subst: Substitution<I>, - - /// Region constraints that constrain the substitution. - pub constraints: Constraints<I>, -} - -/// The resulting substitution after solving a goal. -#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner)] -pub struct AnswerSubst<I: Interner> { - /// The substitution result. - /// - /// NB: The `is_trivial` routine relies on the fact that `subst` is folded first. - pub subst: Substitution<I>, - - /// List of constraints that are part of the answer. - pub constraints: Constraints<I>, - - /// Delayed subgoals, used when the solver answered with an (incomplete) `Answer` (instead of a `CompleteAnswer`). - pub delayed_subgoals: Vec<InEnvironment<Goal<I>>>, -} - -/// Logic to decide the Variance for a given subst -pub trait UnificationDatabase<I> -where - Self: std::fmt::Debug, - I: Interner, -{ - /// Gets the variances for the substitution of a fn def - fn fn_def_variance(&self, fn_def_id: FnDefId<I>) -> Variances<I>; - - /// Gets the variances for the substitution of a adt - fn adt_variance(&self, adt_id: AdtId<I>) -> Variances<I>; -} diff --git a/vendor/chalk-ir/src/visit.rs b/vendor/chalk-ir/src/visit.rs deleted file mode 100644 index c761ab46f..000000000 --- a/vendor/chalk-ir/src/visit.rs +++ /dev/null @@ -1,422 +0,0 @@ -//! Traits for visiting bits of IR. -use std::fmt::Debug; -use std::ops::ControlFlow; - -use crate::{ - BoundVar, Const, ConstValue, DebruijnIndex, DomainGoal, Goal, InferenceVar, Interner, Lifetime, - LifetimeData, PlaceholderIndex, ProgramClause, Ty, TyKind, WhereClause, -}; - -mod binder_impls; -mod boring_impls; -pub mod visitors; - -pub use visitors::VisitExt; - -/// Unwraps a `ControlFlow` or propagates its `Break` value. -/// This replaces the `Try` implementation that would be used -/// with `std::ops::ControlFlow`. -#[macro_export] -macro_rules! try_break { - ($expr:expr) => { - match $expr { - std::ops::ControlFlow::Continue(c) => c, - std::ops::ControlFlow::Break(b) => return std::ops::ControlFlow::Break(b), - } - }; -} - -/// A "visitor" recursively folds some term -- that is, some bit of IR, -/// such as a `Goal`, and computes a value as a result. -/// -/// -/// To **apply** a visitor, use the `TypeVisitable::visit_with` method, like so -/// -/// ```rust,ignore -/// let result = x.visit_with(&mut visitor, 0); -/// ``` -pub trait TypeVisitor<I: Interner> { - /// The "break type" of the visitor, often `()`. It represents the result - /// the visitor yields when it stops visiting. - type BreakTy; - - /// Creates a `dyn` value from this visitor. Unfortunately, this - /// must be added manually to each impl of visitor; it permits the - /// default implements below to create a `&mut dyn TypeVisitor` from - /// `Self` without knowing what `Self` is (by invoking this - /// method). Effectively, this limits impls of `visitor` to types - /// for which we are able to create a dyn value (i.e., not `[T]` - /// types). - fn as_dyn(&mut self) -> &mut dyn TypeVisitor<I, BreakTy = Self::BreakTy>; - - /// Top-level callback: invoked for each `Ty<I>` that is - /// encountered when visiting. By default, invokes - /// `super_visit_with`, which will in turn invoke the more - /// specialized visiting methods below, like `visit_free_var`. - fn visit_ty(&mut self, ty: &Ty<I>, outer_binder: DebruijnIndex) -> ControlFlow<Self::BreakTy> { - ty.super_visit_with(self.as_dyn(), outer_binder) - } - - /// Top-level callback: invoked for each `Lifetime<I>` that is - /// encountered when visiting. By default, invokes - /// `super_visit_with`, which will in turn invoke the more - /// specialized visiting methods below, like `visit_free_var`. - fn visit_lifetime( - &mut self, - lifetime: &Lifetime<I>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<Self::BreakTy> { - lifetime.super_visit_with(self.as_dyn(), outer_binder) - } - - /// Top-level callback: invoked for each `Const<I>` that is - /// encountered when visiting. By default, invokes - /// `super_visit_with`, which will in turn invoke the more - /// specialized visiting methods below, like `visit_free_var`. - fn visit_const( - &mut self, - constant: &Const<I>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<Self::BreakTy> { - constant.super_visit_with(self.as_dyn(), outer_binder) - } - - /// Invoked for every program clause. By default, recursively visits the goals contents. - fn visit_program_clause( - &mut self, - clause: &ProgramClause<I>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<Self::BreakTy> { - clause.super_visit_with(self.as_dyn(), outer_binder) - } - - /// Invoked for every goal. By default, recursively visits the goals contents. - fn visit_goal( - &mut self, - goal: &Goal<I>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<Self::BreakTy> { - goal.super_visit_with(self.as_dyn(), outer_binder) - } - - /// Invoked for each domain goal. - fn visit_domain_goal( - &mut self, - domain_goal: &DomainGoal<I>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<Self::BreakTy> { - domain_goal.super_visit_with(self.as_dyn(), outer_binder) - } - - /// If overridden to return true, then visiting will panic if a - /// free variable is encountered. This should be done if free - /// type/lifetime/const variables are not expected. - fn forbid_free_vars(&self) -> bool { - false - } - - /// Invoked for `BoundVar` instances that are not bound - /// within the type being visited over: - fn visit_free_var( - &mut self, - bound_var: BoundVar, - outer_binder: DebruijnIndex, - ) -> ControlFlow<Self::BreakTy> { - if self.forbid_free_vars() { - panic!( - "unexpected free variable `{:?}` with outer binder {:?}", - bound_var, outer_binder - ) - } else { - ControlFlow::Continue(()) - } - } - - /// If overridden to return true, we will panic when a free - /// placeholder type/lifetime 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. - fn visit_free_placeholder( - &mut self, - universe: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> ControlFlow<Self::BreakTy> { - if self.forbid_free_placeholders() { - panic!("unexpected placeholder type `{:?}`", universe) - } else { - ControlFlow::Continue(()) - } - } - - /// Invoked for each where clause. - fn visit_where_clause( - &mut self, - where_clause: &WhereClause<I>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<Self::BreakTy> { - where_clause.super_visit_with(self.as_dyn(), outer_binder) - } - - /// If overridden to return true, inference variables will trigger - /// panics when visited. 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. - fn visit_inference_var( - &mut self, - var: InferenceVar, - _outer_binder: DebruijnIndex, - ) -> ControlFlow<Self::BreakTy> { - if self.forbid_inference_vars() { - panic!("unexpected inference type `{:?}`", var) - } else { - ControlFlow::Continue(()) - } - } - - /// Gets the visitor's interner. - fn interner(&self) -> I; -} - -/// Applies the given `visitor` to a value, producing a visited result -/// of type `TypeVisitor::Result`. -pub trait TypeVisitable<I: Interner>: Debug { - /// Apply the given visitor `visitor` to `self`; `binders` is the - /// number of binders that are in scope when beginning the - /// visitor. Typically `binders` starts as 0, but is adjusted when - /// we encounter `Binders<T>` in the IR or other similar - /// constructs. - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B>; -} - -/// For types where "visit" invokes a callback on the `visitor`, the -/// `TypeSuperVisitable` trait captures the recursive behavior that visits all -/// the contents of the type. -pub trait TypeSuperVisitable<I: Interner>: TypeVisitable<I> { - /// Recursively visits the type contents. - fn super_visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B>; -} - -/// "visiting" a type invokes the `visit_ty` method on the visitor; this -/// usually (in turn) invokes `super_visit_ty` to visit the individual -/// parts. -impl<I: Interner> TypeVisitable<I> for Ty<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - visitor.visit_ty(self, outer_binder) - } -} - -/// "Super visit" for a type invokes the more detailed callbacks on the type -impl<I> TypeSuperVisitable<I> for Ty<I> -where - I: Interner, -{ - fn super_visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - let interner = visitor.interner(); - match self.kind(interner) { - TyKind::BoundVar(bound_var) => { - if bound_var.shifted_out_to(outer_binder).is_some() { - visitor.visit_free_var(*bound_var, outer_binder) - } else { - ControlFlow::Continue(()) - } - } - TyKind::Dyn(clauses) => clauses.visit_with(visitor, outer_binder), - TyKind::InferenceVar(var, _) => visitor.visit_inference_var(*var, outer_binder), - TyKind::Placeholder(ui) => visitor.visit_free_placeholder(*ui, outer_binder), - TyKind::Alias(proj) => proj.visit_with(visitor, outer_binder), - TyKind::Function(fun) => fun.visit_with(visitor, outer_binder), - TyKind::Adt(_id, substitution) => substitution.visit_with(visitor, outer_binder), - TyKind::AssociatedType(_assoc_ty, substitution) => { - substitution.visit_with(visitor, outer_binder) - } - TyKind::Scalar(scalar) => scalar.visit_with(visitor, outer_binder), - TyKind::Str => ControlFlow::Continue(()), - TyKind::Tuple(arity, substitution) => { - try_break!(arity.visit_with(visitor, outer_binder)); - substitution.visit_with(visitor, outer_binder) - } - TyKind::OpaqueType(opaque_ty, substitution) => { - try_break!(opaque_ty.visit_with(visitor, outer_binder)); - substitution.visit_with(visitor, outer_binder) - } - TyKind::Slice(substitution) => substitution.visit_with(visitor, outer_binder), - TyKind::FnDef(fn_def, substitution) => { - try_break!(fn_def.visit_with(visitor, outer_binder)); - substitution.visit_with(visitor, outer_binder) - } - TyKind::Ref(mutability, lifetime, ty) => { - try_break!(mutability.visit_with(visitor, outer_binder)); - try_break!(lifetime.visit_with(visitor, outer_binder)); - ty.visit_with(visitor, outer_binder) - } - TyKind::Raw(mutability, ty) => { - try_break!(mutability.visit_with(visitor, outer_binder)); - ty.visit_with(visitor, outer_binder) - } - TyKind::Never => ControlFlow::Continue(()), - TyKind::Array(ty, const_) => { - try_break!(ty.visit_with(visitor, outer_binder)); - const_.visit_with(visitor, outer_binder) - } - TyKind::Closure(id, substitution) => { - try_break!(id.visit_with(visitor, outer_binder)); - substitution.visit_with(visitor, outer_binder) - } - TyKind::Generator(generator, substitution) => { - try_break!(generator.visit_with(visitor, outer_binder)); - substitution.visit_with(visitor, outer_binder) - } - TyKind::GeneratorWitness(witness, substitution) => { - try_break!(witness.visit_with(visitor, outer_binder)); - substitution.visit_with(visitor, outer_binder) - } - TyKind::Foreign(foreign_ty) => foreign_ty.visit_with(visitor, outer_binder), - TyKind::Error => ControlFlow::Continue(()), - } - } -} - -impl<I: Interner> TypeVisitable<I> for Lifetime<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - visitor.visit_lifetime(self, outer_binder) - } -} - -impl<I: Interner> TypeSuperVisitable<I> for Lifetime<I> { - fn super_visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - let interner = visitor.interner(); - match self.data(interner) { - LifetimeData::BoundVar(bound_var) => { - if bound_var.shifted_out_to(outer_binder).is_some() { - visitor.visit_free_var(*bound_var, outer_binder) - } else { - ControlFlow::Continue(()) - } - } - LifetimeData::InferenceVar(var) => visitor.visit_inference_var(*var, outer_binder), - LifetimeData::Placeholder(universe) => { - visitor.visit_free_placeholder(*universe, outer_binder) - } - LifetimeData::Static | LifetimeData::Erased => ControlFlow::Continue(()), - LifetimeData::Phantom(void, ..) => match *void {}, - } - } -} - -impl<I: Interner> TypeVisitable<I> for Const<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - visitor.visit_const(self, outer_binder) - } -} - -impl<I: Interner> TypeSuperVisitable<I> for Const<I> { - fn super_visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - let interner = visitor.interner(); - match &self.data(interner).value { - ConstValue::BoundVar(bound_var) => { - if bound_var.shifted_out_to(outer_binder).is_some() { - visitor.visit_free_var(*bound_var, outer_binder) - } else { - ControlFlow::Continue(()) - } - } - ConstValue::InferenceVar(var) => visitor.visit_inference_var(*var, outer_binder), - ConstValue::Placeholder(universe) => { - visitor.visit_free_placeholder(*universe, outer_binder) - } - ConstValue::Concrete(_) => ControlFlow::Continue(()), - } - } -} - -impl<I: Interner> TypeVisitable<I> for Goal<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - visitor.visit_goal(self, outer_binder) - } -} - -impl<I: Interner> TypeSuperVisitable<I> for Goal<I> { - fn super_visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - let interner = visitor.interner(); - self.data(interner).visit_with(visitor, outer_binder) - } -} - -impl<I: Interner> TypeVisitable<I> for ProgramClause<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - visitor.visit_program_clause(self, outer_binder) - } -} - -impl<I: Interner> TypeVisitable<I> for WhereClause<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - visitor.visit_where_clause(self, outer_binder) - } -} - -impl<I: Interner> TypeVisitable<I> for DomainGoal<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - visitor.visit_domain_goal(self, outer_binder) - } -} diff --git a/vendor/chalk-ir/src/visit/binder_impls.rs b/vendor/chalk-ir/src/visit/binder_impls.rs deleted file mode 100644 index 709f99044..000000000 --- a/vendor/chalk-ir/src/visit/binder_impls.rs +++ /dev/null @@ -1,47 +0,0 @@ -//! This module contains impls of `TypeVisitable` for those types that -//! introduce binders. -//! -//! The more interesting impls of `TypeVisitable` remain in the `visit` module. - -use crate::interner::HasInterner; -use crate::{ - Binders, Canonical, ControlFlow, DebruijnIndex, FnPointer, Interner, TypeVisitable, TypeVisitor, -}; - -impl<I: Interner> TypeVisitable<I> for FnPointer<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - self.substitution - .visit_with(visitor, outer_binder.shifted_in()) - } -} - -impl<T, I: Interner> TypeVisitable<I> for Binders<T> -where - T: HasInterner + TypeVisitable<I>, -{ - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - self.value.visit_with(visitor, outer_binder.shifted_in()) - } -} - -impl<I, T> TypeVisitable<I> for Canonical<T> -where - I: Interner, - T: HasInterner<Interner = I> + TypeVisitable<I>, -{ - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - self.value.visit_with(visitor, outer_binder.shifted_in()) - } -} diff --git a/vendor/chalk-ir/src/visit/boring_impls.rs b/vendor/chalk-ir/src/visit/boring_impls.rs deleted file mode 100644 index 512d9ecd8..000000000 --- a/vendor/chalk-ir/src/visit/boring_impls.rs +++ /dev/null @@ -1,261 +0,0 @@ -//! This module contains "rote and uninteresting" impls of `TypeVisitable` for -//! various types. In general, we prefer to derive `TypeVisitable`, but -//! sometimes that doesn't work for whatever reason. -//! -//! The more interesting impls of `TypeVisitable` remain in the `visit` module. - -use crate::{ - try_break, AdtId, AssocTypeId, ClausePriority, ClosureId, Constraints, ControlFlow, - DebruijnIndex, FloatTy, FnDefId, ForeignDefId, GeneratorId, GenericArg, Goals, ImplId, IntTy, - Interner, Mutability, OpaqueTyId, PlaceholderIndex, ProgramClause, ProgramClauses, - QuantifiedWhereClauses, QuantifierKind, Safety, Scalar, Substitution, TraitId, - TypeSuperVisitable, TypeVisitable, TypeVisitor, UintTy, UniverseIndex, -}; -use std::{marker::PhantomData, sync::Arc}; - -/// Convenience function to visit all the items in the iterator it. -pub fn visit_iter<'i, T, I, B>( - it: impl Iterator<Item = T>, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, -) -> ControlFlow<B> -where - T: TypeVisitable<I>, - I: 'i + Interner, -{ - for e in it { - try_break!(e.visit_with(visitor, outer_binder)); - } - ControlFlow::Continue(()) -} - -impl<T: TypeVisitable<I>, I: Interner> TypeVisitable<I> for &T { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - T::visit_with(self, visitor, outer_binder) - } -} - -impl<T: TypeVisitable<I>, I: Interner> TypeVisitable<I> for Vec<T> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - visit_iter(self.iter(), visitor, outer_binder) - } -} - -impl<T: TypeVisitable<I>, I: Interner> TypeVisitable<I> for &[T] { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - visit_iter(self.iter(), visitor, outer_binder) - } -} - -impl<T: TypeVisitable<I>, I: Interner> TypeVisitable<I> for Box<T> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - T::visit_with(self, visitor, outer_binder) - } -} - -impl<T: TypeVisitable<I>, I: Interner> TypeVisitable<I> for Arc<T> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - T::visit_with(self, visitor, outer_binder) - } -} - -macro_rules! tuple_visit { - ($($n:ident),*) => { - impl<$($n: TypeVisitable<I>,)* I: Interner> TypeVisitable<I> for ($($n,)*) { - fn visit_with<BT>(&self, visitor: &mut dyn TypeVisitor<I, BreakTy = BT>, outer_binder: DebruijnIndex) -> ControlFlow<BT> { - #[allow(non_snake_case)] - let &($(ref $n),*) = self; - $( - try_break!($n.visit_with(visitor, outer_binder)); - )* - ControlFlow::Continue(()) - } - } - } -} - -tuple_visit!(A, B); -tuple_visit!(A, B, C); -tuple_visit!(A, B, C, D); -tuple_visit!(A, B, C, D, E); - -impl<T: TypeVisitable<I>, I: Interner> TypeVisitable<I> for Option<T> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - match self { - Some(e) => e.visit_with(visitor, outer_binder), - None => ControlFlow::Continue(()), - } - } -} - -impl<I: Interner> TypeVisitable<I> for GenericArg<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - let interner = visitor.interner(); - self.data(interner).visit_with(visitor, outer_binder) - } -} - -impl<I: Interner> TypeVisitable<I> for Substitution<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - let interner = visitor.interner(); - visit_iter(self.iter(interner), visitor, outer_binder) - } -} - -impl<I: Interner> TypeVisitable<I> for Goals<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - let interner = visitor.interner(); - visit_iter(self.iter(interner), visitor, outer_binder) - } -} - -#[doc(hidden)] -#[macro_export] -macro_rules! const_visit { - ($t:ty) => { - impl<I: Interner> $crate::visit::TypeVisitable<I> for $t { - fn visit_with<B>( - &self, - _visitor: &mut dyn ($crate::visit::TypeVisitor<I, BreakTy = B>), - _outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - ControlFlow::Continue(()) - } - } - }; -} - -const_visit!(bool); -const_visit!(usize); -const_visit!(UniverseIndex); -const_visit!(PlaceholderIndex); -const_visit!(QuantifierKind); -const_visit!(DebruijnIndex); -const_visit!(ClausePriority); -const_visit!(()); -const_visit!(Scalar); -const_visit!(UintTy); -const_visit!(IntTy); -const_visit!(FloatTy); -const_visit!(Mutability); -const_visit!(Safety); - -#[doc(hidden)] -#[macro_export] -macro_rules! id_visit { - ($t:ident) => { - impl<I: Interner> $crate::visit::TypeVisitable<I> for $t<I> { - fn visit_with<B>( - &self, - _visitor: &mut dyn ($crate::visit::TypeVisitor<I, BreakTy = B>), - _outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - ControlFlow::Continue(()) - } - } - }; -} - -id_visit!(ImplId); -id_visit!(AdtId); -id_visit!(TraitId); -id_visit!(OpaqueTyId); -id_visit!(AssocTypeId); -id_visit!(FnDefId); -id_visit!(ClosureId); -id_visit!(GeneratorId); -id_visit!(ForeignDefId); - -impl<I: Interner> TypeSuperVisitable<I> for ProgramClause<I> { - fn super_visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - let interner = visitor.interner(); - - self.data(interner).0.visit_with(visitor, outer_binder) - } -} - -impl<I: Interner> TypeVisitable<I> for ProgramClauses<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - let interner = visitor.interner(); - - visit_iter(self.iter(interner), visitor, outer_binder) - } -} - -impl<I: Interner> TypeVisitable<I> for Constraints<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - let interner = visitor.interner(); - - visit_iter(self.iter(interner), visitor, outer_binder) - } -} - -impl<I: Interner> TypeVisitable<I> for QuantifiedWhereClauses<I> { - fn visit_with<B>( - &self, - visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - let interner = visitor.interner(); - - visit_iter(self.iter(interner), visitor, outer_binder) - } -} - -impl<I: Interner> TypeVisitable<I> for PhantomData<I> { - fn visit_with<B>( - &self, - _visitor: &mut dyn TypeVisitor<I, BreakTy = B>, - _outer_binder: DebruijnIndex, - ) -> ControlFlow<B> { - ControlFlow::Continue(()) - } -} diff --git a/vendor/chalk-ir/src/visit/visitors.rs b/vendor/chalk-ir/src/visit/visitors.rs deleted file mode 100644 index 51c087840..000000000 --- a/vendor/chalk-ir/src/visit/visitors.rs +++ /dev/null @@ -1,41 +0,0 @@ -//! TypeVisitor helpers - -use crate::{BoundVar, ControlFlow, DebruijnIndex, Interner, TypeVisitable, TypeVisitor}; - -/// TypeVisitor extensions. -pub trait VisitExt<I: Interner>: TypeVisitable<I> { - /// Check whether there are free (non-bound) variables. - fn has_free_vars(&self, interner: I) -> bool { - let flow = self.visit_with( - &mut FindFreeVarsVisitor { interner }, - DebruijnIndex::INNERMOST, - ); - matches!(flow, ControlFlow::Break(_)) - } -} - -impl<T, I: Interner> VisitExt<I> for T where T: TypeVisitable<I> {} - -struct FindFreeVarsVisitor<I: Interner> { - interner: I, -} - -impl<I: Interner> TypeVisitor<I> for FindFreeVarsVisitor<I> { - type BreakTy = (); - - fn as_dyn(&mut self) -> &mut dyn TypeVisitor<I, BreakTy = Self::BreakTy> { - self - } - - fn interner(&self) -> I { - self.interner - } - - fn visit_free_var( - &mut self, - _bound_var: BoundVar, - _outer_binder: DebruijnIndex, - ) -> ControlFlow<()> { - ControlFlow::Break(()) - } -} diff --git a/vendor/chalk-ir/src/zip.rs b/vendor/chalk-ir/src/zip.rs deleted file mode 100644 index afa4a13cb..000000000 --- a/vendor/chalk-ir/src/zip.rs +++ /dev/null @@ -1,543 +0,0 @@ -//! Traits for "zipping" types, walking through two structures and checking that they match. - -use crate::fold::TypeFoldable; -use crate::*; -use std::fmt::Debug; -use std::sync::Arc; - -/// When we zip types, we basically traverse the structure, ensuring -/// that it matches. When we come to types/lifetimes, we invoke the -/// callback methods in the zipper to match them up. Primarily used -/// during unification or similar operations. -/// -/// So e.g. if you had `A: Eq<B>` zipped with `X: Eq<Y>`, then the zipper -/// would get two callbacks, one pairing `A` and `X`, and the other pairing -/// `B` and `Y`. -/// -/// For things other than types/lifetimes, the zip impls will -/// guarantee equality. So e.g. if you have `A: Eq<B>` zipped with `X: -/// Ord<Y>`, you would wind up with an error, no matter what zipper -/// you are using. This is because the traits `Eq` and `Ord` are -/// represented by two distinct `ItemId` values, and the impl for -/// `ItemId` requires that all `ItemId` in the two zipped values match -/// up. -pub trait Zipper<I: Interner> { - /// Indicates that the two types `a` and `b` were found in matching spots. - fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()>; - - /// Indicates that the two lifetimes `a` and `b` were found in matching spots. - fn zip_lifetimes( - &mut self, - variance: Variance, - a: &Lifetime<I>, - b: &Lifetime<I>, - ) -> Fallible<()>; - - /// Indicates that the two consts `a` and `b` were found in matching spots. - fn zip_consts(&mut self, variance: Variance, a: &Const<I>, b: &Const<I>) -> Fallible<()>; - - /// Zips two values appearing beneath binders. - fn zip_binders<T>( - &mut self, - variance: Variance, - a: &Binders<T>, - b: &Binders<T>, - ) -> Fallible<()> - where - T: Clone + HasInterner<Interner = I> + Zip<I> + TypeFoldable<I>; - - /// Zips two substs - fn zip_substs( - &mut self, - ambient: Variance, - variances: Option<Variances<I>>, - a: &[GenericArg<I>], - b: &[GenericArg<I>], - ) -> Fallible<()> - where - Self: Sized, - { - for (i, (a, b)) in a.iter().zip(b.iter()).enumerate() { - let variance = variances - .as_ref() - .map(|v| v.as_slice(self.interner())[i]) - .unwrap_or(Variance::Invariant); - Zip::zip_with(self, ambient.xform(variance), a, b)?; - } - Ok(()) - } - - /// Retrieves the interner from the underlying zipper object - fn interner(&self) -> I; - - /// Retrieves the `UnificationDatabase` from the underlying zipper object - fn unification_database(&self) -> &dyn UnificationDatabase<I>; -} - -impl<'f, Z, I> Zipper<I> for &'f mut Z -where - I: Interner, - Z: Zipper<I>, -{ - fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()> { - (**self).zip_tys(variance, a, b) - } - - fn zip_lifetimes( - &mut self, - variance: Variance, - a: &Lifetime<I>, - b: &Lifetime<I>, - ) -> Fallible<()> { - (**self).zip_lifetimes(variance, a, b) - } - - fn zip_consts(&mut self, variance: Variance, a: &Const<I>, b: &Const<I>) -> Fallible<()> { - (**self).zip_consts(variance, a, b) - } - - fn zip_binders<T>(&mut self, variance: Variance, a: &Binders<T>, b: &Binders<T>) -> Fallible<()> - where - T: Clone + HasInterner<Interner = I> + Zip<I> + TypeFoldable<I>, - { - (**self).zip_binders(variance, a, b) - } - - fn interner(&self) -> I { - Z::interner(*self) - } - - fn unification_database(&self) -> &dyn UnificationDatabase<I> { - (**self).unification_database() - } -} - -/// The `Zip` trait walks two values, invoking the `Zipper` methods where -/// appropriate, but otherwise requiring strict equality. -/// -/// See `Zipper` trait for more details. -/// -/// To implement the trait, typically you would use one of the macros -/// like `eq_zip!`, `struct_zip!`, or `enum_zip!`. -pub trait Zip<I>: Debug -where - I: Interner, -{ - /// Uses the zipper to walk through two values, ensuring that they match. - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()>; -} - -impl<'a, T: ?Sized + Zip<I>, I: Interner> Zip<I> for &'a T { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - <T as Zip<I>>::zip_with(zipper, variance, a, b) - } -} - -impl<I: Interner> Zip<I> for () { - fn zip_with<Z: Zipper<I>>(_: &mut Z, _: Variance, _: &Self, _: &Self) -> Fallible<()> { - Ok(()) - } -} - -impl<T: Zip<I>, I: Interner> Zip<I> for Vec<T> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - <[T] as Zip<I>>::zip_with(zipper, variance, a, b) - } -} - -impl<T: Zip<I>, I: Interner> Zip<I> for [T] { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - if a.len() != b.len() { - return Err(NoSolution); - } - - for (a_elem, b_elem) in a.iter().zip(b) { - Zip::zip_with(zipper, variance, a_elem, b_elem)?; - } - - Ok(()) - } -} - -impl<T: Zip<I>, I: Interner> Zip<I> for Arc<T> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - <T as Zip<I>>::zip_with(zipper, variance, a, b) - } -} - -impl<T: Zip<I>, I: Interner> Zip<I> for Box<T> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - <T as Zip<I>>::zip_with(zipper, variance, a, b) - } -} - -impl<T: Zip<I>, U: Zip<I>, I: Interner> Zip<I> for (T, U) { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - Zip::zip_with(zipper, variance, &a.0, &b.0)?; - Zip::zip_with(zipper, variance, &a.1, &b.1)?; - Ok(()) - } -} - -impl<I: Interner> Zip<I> for Ty<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - zipper.zip_tys(variance, a, b) - } -} - -impl<I: Interner> Zip<I> for Lifetime<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - zipper.zip_lifetimes(variance, a, b) - } -} - -impl<I: Interner> Zip<I> for Const<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - zipper.zip_consts(variance, a, b) - } -} -impl<I: Interner, T> Zip<I> for Binders<T> -where - T: Clone + HasInterner<Interner = I> + Zip<I> + TypeFoldable<I>, -{ - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - zipper.zip_binders(variance, a, b) - } -} - -/// Generates a Zip impl that requires the two values be -/// equal. Suitable for atomic, scalar values. -macro_rules! eq_zip { - ($I:ident => $t:ty) => { - impl<$I: Interner> Zip<$I> for $t { - fn zip_with<Z: Zipper<$I>>( - _zipper: &mut Z, - _variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - if a != b { - return Err(NoSolution); - } - Ok(()) - } - } - }; -} - -eq_zip!(I => AdtId<I>); -eq_zip!(I => TraitId<I>); -eq_zip!(I => AssocTypeId<I>); -eq_zip!(I => OpaqueTyId<I>); -eq_zip!(I => GeneratorId<I>); -eq_zip!(I => ForeignDefId<I>); -eq_zip!(I => FnDefId<I>); -eq_zip!(I => ClosureId<I>); -eq_zip!(I => QuantifierKind); -eq_zip!(I => PhantomData<I>); -eq_zip!(I => PlaceholderIndex); -eq_zip!(I => ClausePriority); -eq_zip!(I => Mutability); -eq_zip!(I => Scalar); - -impl<T: HasInterner<Interner = I> + Zip<I>, I: Interner> Zip<I> for InEnvironment<T> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - Zip::zip_with(zipper, variance, &a.environment, &b.environment)?; - Zip::zip_with(zipper, variance, &a.goal, &b.goal)?; - Ok(()) - } -} - -impl<I: Interner> Zip<I> for Environment<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - assert_eq!(a.clauses.len(interner), b.clauses.len(interner)); // or different numbers of clauses - Zip::zip_with( - zipper, - variance, - a.clauses.as_slice(interner), - b.clauses.as_slice(interner), - )?; - Ok(()) - } -} - -impl<I: Interner> Zip<I> for Goals<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?; - Ok(()) - } -} - -impl<I: Interner> Zip<I> for ProgramClauses<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?; - Ok(()) - } -} - -impl<I: Interner> Zip<I> for Constraints<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?; - Ok(()) - } -} - -impl<I: Interner> Zip<I> for QuantifiedWhereClauses<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?; - Ok(()) - } -} - -// Annoyingly, Goal cannot use `enum_zip` because some variants have -// two parameters, and I'm too lazy to make the macro account for the -// relevant name mangling. -impl<I: Interner> Zip<I> for Goal<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - Zip::zip_with(zipper, variance, a.data(interner), b.data(interner)) - } -} - -// I'm too lazy to make `enum_zip` support type parameters. -impl<I: Interner> Zip<I> for VariableKind<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - match (a, b) { - (VariableKind::Ty(a), VariableKind::Ty(b)) if a == b => Ok(()), - (VariableKind::Lifetime, VariableKind::Lifetime) => Ok(()), - (VariableKind::Const(ty_a), VariableKind::Const(ty_b)) => { - Zip::zip_with(zipper, variance, ty_a, ty_b) - } - (VariableKind::Ty(_), _) - | (VariableKind::Lifetime, _) - | (VariableKind::Const(_), _) => panic!("zipping things of mixed kind"), - } - } -} - -impl<I: Interner> Zip<I> for GenericArg<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - Zip::zip_with(zipper, variance, a.data(interner), b.data(interner)) - } -} - -impl<I: Interner> Zip<I> for ProgramClause<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - Zip::zip_with(zipper, variance, a.data(interner), b.data(interner)) - } -} - -impl<I: Interner> Zip<I> for TraitRef<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - Zip::zip_with(zipper, variance, &a.trait_id, &b.trait_id)?; - zipper.zip_substs( - variance, - None, - a.substitution.as_slice(interner), - b.substitution.as_slice(interner), - ) - } -} - -impl<I: Interner> Zip<I> for ProjectionTy<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - Zip::zip_with(zipper, variance, &a.associated_ty_id, &b.associated_ty_id)?; - zipper.zip_substs( - variance, - None, - a.substitution.as_slice(interner), - b.substitution.as_slice(interner), - ) - } -} - -impl<I: Interner> Zip<I> for OpaqueTy<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - Zip::zip_with(zipper, variance, &a.opaque_ty_id, &b.opaque_ty_id)?; - zipper.zip_substs( - variance, - None, - a.substitution.as_slice(interner), - b.substitution.as_slice(interner), - ) - } -} - -impl<I: Interner> Zip<I> for DynTy<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - Zip::zip_with( - zipper, - variance.xform(Variance::Invariant), - &a.bounds, - &b.bounds, - )?; - Zip::zip_with( - zipper, - variance.xform(Variance::Contravariant), - &a.lifetime, - &b.lifetime, - )?; - Ok(()) - } -} - -impl<I: Interner> Zip<I> for FnSubst<I> { - fn zip_with<Z: Zipper<I>>( - zipper: &mut Z, - variance: Variance, - a: &Self, - b: &Self, - ) -> Fallible<()> { - let interner = zipper.interner(); - // Parameters - Zip::zip_with( - zipper, - variance.xform(Variance::Contravariant), - &a.0.as_slice(interner)[..a.0.len(interner) - 1], - &b.0.as_slice(interner)[..b.0.len(interner) - 1], - )?; - // Return type - Zip::zip_with( - zipper, - variance, - a.0.iter(interner).last().unwrap(), - b.0.iter(interner).last().unwrap(), - )?; - Ok(()) - } -} |