From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/chalk-ir-0.80.0/.cargo-checksum.json | 1 + vendor/chalk-ir-0.80.0/Cargo.toml | 29 + vendor/chalk-ir-0.80.0/README.md | 3 + vendor/chalk-ir-0.80.0/src/cast.rs | 364 +++ vendor/chalk-ir-0.80.0/src/could_match.rs | 213 ++ vendor/chalk-ir-0.80.0/src/debug.rs | 1018 +++++++ vendor/chalk-ir-0.80.0/src/fold.rs | 617 +++++ vendor/chalk-ir-0.80.0/src/fold/binder_impls.rs | 78 + vendor/chalk-ir-0.80.0/src/fold/boring_impls.rs | 256 ++ vendor/chalk-ir-0.80.0/src/fold/in_place.rs | 263 ++ vendor/chalk-ir-0.80.0/src/fold/shift.rs | 185 ++ vendor/chalk-ir-0.80.0/src/fold/subst.rs | 123 + vendor/chalk-ir-0.80.0/src/interner.rs | 702 +++++ vendor/chalk-ir-0.80.0/src/lib.rs | 3077 ++++++++++++++++++++++ vendor/chalk-ir-0.80.0/src/visit.rs | 424 +++ vendor/chalk-ir-0.80.0/src/visit/binder_impls.rs | 45 + vendor/chalk-ir-0.80.0/src/visit/boring_impls.rs | 261 ++ vendor/chalk-ir-0.80.0/src/visit/visitors.rs | 41 + vendor/chalk-ir-0.80.0/src/zip.rs | 543 ++++ 19 files changed, 8243 insertions(+) create mode 100644 vendor/chalk-ir-0.80.0/.cargo-checksum.json create mode 100644 vendor/chalk-ir-0.80.0/Cargo.toml create mode 100644 vendor/chalk-ir-0.80.0/README.md create mode 100644 vendor/chalk-ir-0.80.0/src/cast.rs create mode 100644 vendor/chalk-ir-0.80.0/src/could_match.rs create mode 100644 vendor/chalk-ir-0.80.0/src/debug.rs create mode 100644 vendor/chalk-ir-0.80.0/src/fold.rs create mode 100644 vendor/chalk-ir-0.80.0/src/fold/binder_impls.rs create mode 100644 vendor/chalk-ir-0.80.0/src/fold/boring_impls.rs create mode 100644 vendor/chalk-ir-0.80.0/src/fold/in_place.rs create mode 100644 vendor/chalk-ir-0.80.0/src/fold/shift.rs create mode 100644 vendor/chalk-ir-0.80.0/src/fold/subst.rs create mode 100644 vendor/chalk-ir-0.80.0/src/interner.rs create mode 100644 vendor/chalk-ir-0.80.0/src/lib.rs create mode 100644 vendor/chalk-ir-0.80.0/src/visit.rs create mode 100644 vendor/chalk-ir-0.80.0/src/visit/binder_impls.rs create mode 100644 vendor/chalk-ir-0.80.0/src/visit/boring_impls.rs create mode 100644 vendor/chalk-ir-0.80.0/src/visit/visitors.rs create mode 100644 vendor/chalk-ir-0.80.0/src/zip.rs (limited to 'vendor/chalk-ir-0.80.0') diff --git a/vendor/chalk-ir-0.80.0/.cargo-checksum.json b/vendor/chalk-ir-0.80.0/.cargo-checksum.json new file mode 100644 index 000000000..511b61a96 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"b40bd042cd15eab561ed08e8e164e6cde450d4a8a43aa6af0f8cc2022967980d","README.md":"64cba0ddf3e9b5c168fbe069f1a84c401ce0b33e765ea49acb1345d0923afe8d","src/cast.rs":"b2a6dc2fe33d58df3021d1e83f3823d68a14afff2a484fe0a5c8514290112c17","src/could_match.rs":"a341b8b11615ca738498c722b61695307da170f14754c281fbf2b778d3e82348","src/debug.rs":"918411b9c09da2d04b136c9d56b89eb0f0f8b8ada000e2d14df13f03ae112a13","src/fold.rs":"7cd7e9b0c167110acb2c08ec1a1d6c1519bcbedf42ce08914146b173a0424dc3","src/fold/binder_impls.rs":"5c6e4182d71e958fb24e94bdead7998da07f7373c337866e6bf3d2c7be4d0baf","src/fold/boring_impls.rs":"1f139ebfb80f149d9730c7324235dc590a0d09d33fe7038e99253a5125098f7b","src/fold/in_place.rs":"dc7af5175abfd7988d8a31448f5efa6c7a698e2951a1b9e93f8d46db5a5f62fe","src/fold/shift.rs":"93830c06d44fa3757b92e2e835e681bd3e7c8b1aa2ad6cb74a508f8d0be8bd38","src/fold/subst.rs":"79ca4899101b45e14e409a487ab0640771bda824828e657f48a169e597ae954e","src/interner.rs":"63a977e4c2e25bb0290f47e8b30fc1f7128a68baa7d4568db15503b3150fdb4f","src/lib.rs":"892e9d2f99c0009ebe4cfe85f3a030efceecc0b0456c233e4542785c34a5f58a","src/visit.rs":"39a4ec897f39895ab06330d3841b72dbe02dcbf9dafd3fb462c9f10d1c996da7","src/visit/binder_impls.rs":"8218b283a4e8a7eb9f58ce7d331b3a04a875fba0b92b00a701a214d51570ab30","src/visit/boring_impls.rs":"cf809eaf6efba520e3970a52edcf9be45ac49e1e805cfc6d9e9bfe9295bd7da6","src/visit/visitors.rs":"a3de22a55d123b7db32d9524a39aeed1177c512d93eb8a3689cbd5e6c96917fd","src/zip.rs":"3f9515b942a79402b1612081036b9189a6143313e1226d08aab745013ba00075"},"package":"92d8a95548f23618fda86426e4304e563ec2bb7ba0216139f0748d63c107b5f1"} \ No newline at end of file diff --git a/vendor/chalk-ir-0.80.0/Cargo.toml b/vendor/chalk-ir-0.80.0/Cargo.toml new file mode 100644 index 000000000..d17d0e252 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/Cargo.toml @@ -0,0 +1,29 @@ +# 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.80.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 = "Apache-2.0/MIT" +repository = "https://github.com/rust-lang/chalk" +[dependencies.bitflags] +version = "1.2.1" + +[dependencies.chalk-derive] +version = "=0.80.0" + +[dependencies.lazy_static] +version = "1.4.0" diff --git a/vendor/chalk-ir-0.80.0/README.md b/vendor/chalk-ir-0.80.0/README.md new file mode 100644 index 000000000..968ad4937 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/README.md @@ -0,0 +1,3 @@ +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-0.80.0/src/cast.rs b/vendor/chalk-ir-0.80.0/src/cast.rs new file mode 100644 index 000000000..0c6b682ca --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/cast.rs @@ -0,0 +1,364 @@ +//! 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` 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::()` to mean +/// "cast to T". +pub trait Cast: Sized { + /// Cast a value to type `U` using `CastTo`. + fn cast(self, interner: U::Interner) -> U + where + Self: CastTo, + U: HasInterner, + { + self.cast_to(interner) + } +} + +impl 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>` or something +/// like that. +pub trait CastTo: 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); +reflexive_impl!(for(I: Interner) LifetimeData); +reflexive_impl!(for(I: Interner) ConstData); +reflexive_impl!(for(I: Interner) TraitRef); +reflexive_impl!(for(I: Interner) DomainGoal); +reflexive_impl!(for(I: Interner) Goal); +reflexive_impl!(for(I: Interner) WhereClause); +reflexive_impl!(for(I: Interner) ProgramClause); +reflexive_impl!(for(I: Interner) QuantifiedWhereClause); +reflexive_impl!(for(I: Interner) VariableKind); +reflexive_impl!(for(I: Interner) VariableKinds); +reflexive_impl!(for(I: Interner) CanonicalVarKind); +reflexive_impl!(for(I: Interner) CanonicalVarKinds); +reflexive_impl!(for(I: Interner) Constraint); + +impl CastTo> for TraitRef { + fn cast_to(self, _interner: I) -> WhereClause { + WhereClause::Implemented(self) + } +} + +impl CastTo> for AliasEq { + fn cast_to(self, _interner: I) -> WhereClause { + WhereClause::AliasEq(self) + } +} + +impl CastTo> for LifetimeOutlives { + fn cast_to(self, _interner: I) -> WhereClause { + WhereClause::LifetimeOutlives(self) + } +} + +impl CastTo> for TypeOutlives { + fn cast_to(self, _interner: I) -> WhereClause { + WhereClause::TypeOutlives(self) + } +} + +impl CastTo> for T +where + T: CastTo>, + I: Interner, +{ + fn cast_to(self, interner: I) -> DomainGoal { + DomainGoal::Holds(self.cast(interner)) + } +} + +impl CastTo> for T +where + T: CastTo>, +{ + fn cast_to(self, interner: I) -> Goal { + GoalData::DomainGoal(self.cast(interner)).intern(interner) + } +} + +impl CastTo> for Normalize { + fn cast_to(self, _interner: I) -> DomainGoal { + DomainGoal::Normalize(self) + } +} + +impl CastTo> for WellFormed { + fn cast_to(self, _interner: I) -> DomainGoal { + DomainGoal::WellFormed(self) + } +} + +impl CastTo> for FromEnv { + fn cast_to(self, _interner: I) -> DomainGoal { + DomainGoal::FromEnv(self) + } +} + +impl CastTo> for EqGoal { + fn cast_to(self, interner: I) -> Goal { + GoalData::EqGoal(self).intern(interner) + } +} + +impl CastTo> for SubtypeGoal { + fn cast_to(self, interner: I) -> Goal { + GoalData::SubtypeGoal(self).intern(interner) + } +} + +impl + CastTo>> CastTo> for Binders { + fn cast_to(self, interner: I) -> Goal { + GoalData::Quantified( + QuantifierKind::ForAll, + self.map(|bound| bound.cast(interner)), + ) + .intern(interner) + } +} + +impl CastTo> for AliasTy { + fn cast_to(self, _interner: I) -> TyKind { + TyKind::Alias(self) + } +} + +impl CastTo> for Ty { + fn cast_to(self, interner: I) -> GenericArg { + GenericArg::new(interner, GenericArgData::Ty(self)) + } +} + +impl CastTo> for Lifetime { + fn cast_to(self, interner: I) -> GenericArg { + GenericArg::new(interner, GenericArgData::Lifetime(self)) + } +} + +impl CastTo> for Const { + fn cast_to(self, interner: I) -> GenericArg { + GenericArg::new(interner, GenericArgData::Const(self)) + } +} + +impl CastTo> for GenericArg { + fn cast_to(self, _interner: I) -> GenericArg { + self + } +} + +impl CastTo> for T +where + T: CastTo>, + I: Interner, +{ + fn cast_to(self, interner: I) -> ProgramClause { + 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 CastTo> for Binders +where + I: Interner, + T: HasInterner + CastTo>, +{ + fn cast_to(self, interner: I) -> ProgramClause { + ProgramClauseData(self.map(|bound| ProgramClauseImplication { + consequence: bound.cast(interner), + conditions: Goals::empty(interner), + constraints: Constraints::empty(interner), + priority: ClausePriority::High, + })) + .intern(interner) + } +} + +impl CastTo> for Option +where + T: CastTo, + U: HasInterner, +{ + fn cast_to(self, interner: U::Interner) -> Option { + self.map(|v| v.cast(interner)) + } +} + +impl CastTo> for InEnvironment +where + T: HasInterner + CastTo, + U: HasInterner, + I: Interner, +{ + fn cast_to(self, interner: U::Interner) -> InEnvironment { + self.map(|v| v.cast(interner)) + } +} + +impl CastTo> for Result +where + T: CastTo, + U: HasInterner, +{ + fn cast_to(self, interner: U::Interner) -> Result { + self.map(|v| v.cast(interner)) + } +} + +impl HasInterner for Option +where + T: HasInterner, +{ + type Interner = T::Interner; +} + +impl HasInterner for Result +where + T: HasInterner, +{ + type Interner = T::Interner; +} + +impl CastTo> for Canonical +where + T: CastTo + HasInterner, + U: HasInterner, +{ + fn cast_to(self, interner: T::Interner) -> Canonical { + // 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 CastTo> for Vec +where + T: CastTo + HasInterner, + U: HasInterner, +{ + fn cast_to(self, interner: U::Interner) -> Vec { + self.into_iter().casted(interner).collect() + } +} + +impl CastTo 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 { + interner: U::Interner, + iterator: IT, + _cast: PhantomData, +} + +impl Iterator for Casted +where + IT::Item: CastTo, + U: HasInterner, +{ + type Item = U; + + fn next(&mut self) -> Option { + self.iterator.next().map(|item| item.cast_to(self.interner)) + } + + fn size_hint(&self) -> (usize, Option) { + 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(self, interner: U::Interner) -> Casted + where + Self::Item: CastTo, + U: HasInterner, + { + Casted { + interner, + iterator: self, + _cast: PhantomData, + } + } +} + +impl Caster for I where I: Iterator {} diff --git a/vendor/chalk-ir-0.80.0/src/could_match.rs b/vendor/chalk-ir-0.80.0/src/could_match.rs new file mode 100644 index 000000000..9f94ff47a --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/could_match.rs @@ -0,0 +1,213 @@ +//! 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 { + /// Checks whether `self` and `other` could possibly match. + fn could_match( + &self, + interner: T::Interner, + db: &dyn UnificationDatabase, + other: &T, + ) -> bool; +} + +#[allow(unreachable_code, unused_variables)] +impl CouldMatch for T +where + T: Zip + ?Sized + HasInterner, + I: Interner, +{ + fn could_match(&self, interner: I, db: &dyn UnificationDatabase, 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, + } + + impl<'i, I: Interner> Zipper for MatchZipper<'i, I> { + fn zip_tys(&mut self, variance: Variance, a: &Ty, b: &Ty) -> Fallible<()> { + let interner = self.interner; + let matches = |a: &Substitution, b: &Substitution| { + 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, + _: &Lifetime, + ) -> Fallible<()> { + Ok(()) + } + + fn zip_consts( + &mut self, + variance: Variance, + _: &Const, + _: &Const, + ) -> Fallible<()> { + Ok(()) + } + + fn zip_binders( + &mut self, + variance: Variance, + a: &Binders, + b: &Binders, + ) -> Fallible<()> + where + T: HasInterner + Zip, + { + Zip::zip_with(self, variance, &a.value, &b.value) + } + + fn interner(&self) -> I { + self.interner + } + + fn unification_database(&self) -> &dyn UnificationDatabase { + self.db + } + } + } +} + +impl CouldMatch> for ProgramClauseData { + fn could_match( + &self, + interner: I, + db: &dyn UnificationDatabase, + other: &DomainGoal, + ) -> bool { + self.0.value.consequence.could_match(interner, db, other) + } +} + +impl CouldMatch> for ProgramClause { + fn could_match( + &self, + interner: I, + db: &dyn UnificationDatabase, + other: &DomainGoal, + ) -> bool { + self.data(interner).could_match(interner, db, other) + } +} diff --git a/vendor/chalk-ir-0.80.0/src/debug.rs b/vendor/chalk-ir-0.80.0/src/debug.rs new file mode 100644 index 000000000..08a1be78a --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/debug.rs @@ -0,0 +1,1018 @@ +//! 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(pub F) +where + F: Fn(&mut fmt::Formatter<'_>) -> fmt::Result; + +impl fmt::Display for Fmt +where + F: Fn(&mut fmt::Formatter<'_>) -> fmt::Result, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + (self.0)(f) + } +} + +impl Debug for TraitId { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_trait_id(*self, fmt).unwrap_or_else(|| write!(fmt, "TraitId({:?})", self.0)) + } +} + +impl Debug for AdtId { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_adt_id(*self, fmt).unwrap_or_else(|| write!(fmt, "AdtId({:?})", self.0)) + } +} + +impl Debug for AssocTypeId { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_assoc_type_id(*self, fmt) + .unwrap_or_else(|| write!(fmt, "AssocTypeId({:?})", self.0)) + } +} + +impl Debug for FnDefId { + 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 Debug for ClosureId { + fn fmt(&self, fmt: &mut Formatter<'_>) -> std::fmt::Result { + I::debug_closure_id(*self, fmt).unwrap_or_else(|| write!(fmt, "ClosureId({:?})", self.0)) + } +} + +impl Debug for GeneratorId { + fn fmt(&self, fmt: &mut Formatter<'_>) -> std::fmt::Result { + I::debug_generator_id(*self, fmt) + .unwrap_or_else(|| write!(fmt, "GeneratorId({:?})", self.0)) + } +} + +impl Debug for ForeignDefId { + 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 Debug for Ty { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_ty(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl Debug for Lifetime { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_lifetime(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl Debug for Const { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_const(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl Debug for ConcreteConst { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + write!(fmt, "{:?}", self.interned) + } +} + +impl Debug for GenericArg { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_generic_arg(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl Debug for Goal { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_goal(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl Debug for Goals { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_goals(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl Debug for ProgramClauseImplication { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_program_clause_implication(self, fmt) + .unwrap_or_else(|| write!(fmt, "ProgramClauseImplication(?)")) + } +} + +impl Debug for ProgramClause { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_program_clause(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl Debug for ProgramClauses { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_program_clauses(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl Debug for Constraints { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_constraints(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl 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 Debug for AliasTy { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_alias(self, fmt).unwrap_or_else(|| write!(fmt, "AliasTy(?)")) + } +} + +impl Debug for QuantifiedWhereClauses { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_quantified_where_clauses(self, fmt) + .unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl Debug for ProjectionTy { + 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 Debug for OpaqueTy { + 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 Display for Substitution { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_substitution(self, fmt).unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl Debug for OpaqueTyId { + 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 Debug for TyData { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + self.kind.fmt(fmt) + } +} + +impl Debug for TyKind { + 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 Debug for DynTy { + 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 Debug for FnSubst { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + write!(fmt, "{:?}", self.0) + } +} + +impl Debug for FnPointer { + 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 Debug for LifetimeData { + 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::Empty(UniverseIndex::ROOT) => write!(fmt, "'"), + LifetimeData::Empty(universe) => write!(fmt, "'", universe), + LifetimeData::Erased => write!(fmt, "'"), + LifetimeData::Phantom(..) => unreachable!(), + } + } +} + +impl VariableKinds { + 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); + +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, + 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 ``. This is because variable kind lists + // are always associated with binders like `forall { + // ... }`. + 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 Debug for ConstData { + 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 Debug for GoalData { + 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, + 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 Goals { + /// 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); + +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 GenericArgData { + /// 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, + 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 ProgramClauseImplication { + /// 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, + 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 TyKind { + /// 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, + 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 Substitution { + /// 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 TraitRef { + /// Returns a "Debuggable" type that prints like `P0 as Trait`. + pub fn with_as(&self) -> impl std::fmt::Debug + '_ { + SeparatorTraitRef { + trait_ref: self, + separator: " as ", + } + } + + /// Returns a "Debuggable" type that prints like `P0: Trait`. + pub fn with_colon(&self) -> impl std::fmt::Debug + '_ { + SeparatorTraitRef { + trait_ref: self, + separator: ": ", + } + } +} + +impl Debug for TraitRef { + 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, + + /// 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 Debug for LifetimeOutlives { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + write!(fmt, "{:?}: {:?}", self.a, self.b) + } +} + +impl Debug for TypeOutlives { + 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, + 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 ProjectionTy { + /// 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, + 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 OpaqueTy { + /// 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 Debug for Normalize { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + write!(fmt, "Normalize({:?} -> {:?})", self.alias, self.ty) + } +} + +impl Debug for AliasEq { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + write!(fmt, "AliasEq({:?} = {:?})", self.alias, self.ty) + } +} + +impl Debug for WhereClause { + 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 Debug for FromEnv { + 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 Debug for WellFormed { + 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 Debug for DomainGoal { + 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 Debug for EqGoal { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + write!(fmt, "({:?} = {:?})", self.a, self.b) + } +} + +impl Debug for SubtypeGoal { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + write!(fmt, "({:?} <: {:?})", self.a, self.b) + } +} + +impl Debug for Binders { + 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 Debug for ProgramClauseData { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + write!(fmt, "{:?}", self.0) + } +} + +impl Debug for Environment { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + write!(fmt, "Env({:?})", self.clauses) + } +} + +impl Debug for CanonicalVarKinds { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + I::debug_canonical_var_kinds(self, fmt) + .unwrap_or_else(|| write!(fmt, "{:?}", self.interned)) + } +} + +impl Canonical { + /// 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, + 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 Debug for GenericArgData { + 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 Debug for VariableKind { + 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 Debug for WithKind { + 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 Debug for Constraint { + 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 Display for ConstrainedSubst { + #[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 Substitution { + /// 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> { + Angle(self.as_slice(interner)) + } +} + +impl Debug for Substitution { + fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> { + Display::fmt(self, fmt) + } +} + +impl Debug for Variances { + 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-0.80.0/src/fold.rs b/vendor/chalk-ir-0.80.0/src/fold.rs new file mode 100644 index 000000000..e7db15744 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/fold.rs @@ -0,0 +1,617 @@ +//! Traits for transforming bits of IR. + +use crate::*; +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 `Fold` trait which, given a +/// `Folder`, will reconstruct itself, invoking the folder's methods +/// to transform each of the types/lifetimes embedded within. +/// +/// # 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 `Folder` 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 `Folder` 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 `Fold::fold_with` method, like so +/// +/// ```rust,ignore +/// let x = x.fold_with(&mut folder, 0); +/// ``` +pub trait Folder { + /// 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 Folder; it permits the + /// default implements below to create a `&mut dyn Folder` from + /// `Self` without knowing what `Self` is (by invoking this + /// method). Effectively, this limits impls of `Folder` to types + /// for which we are able to create a dyn value (i.e., not `[T]` + /// types). + fn as_dyn(&mut self) -> &mut dyn Folder; + + /// Top-level callback: invoked for each `Ty` 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, outer_binder: DebruijnIndex) -> Result, Self::Error> { + ty.super_fold_with(self.as_dyn(), outer_binder) + } + + /// Top-level callback: invoked for each `Lifetime` 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, + outer_binder: DebruijnIndex, + ) -> Result, Self::Error> { + lifetime.super_fold_with(self.as_dyn(), outer_binder) + } + + /// Top-level callback: invoked for each `Const` 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, + outer_binder: DebruijnIndex, + ) -> Result, Self::Error> { + constant.super_fold_with(self.as_dyn(), outer_binder) + } + + /// Invoked for every program clause. By default, recursively folds the goals contents. + fn fold_program_clause( + &mut self, + clause: ProgramClause, + outer_binder: DebruijnIndex, + ) -> Result, Self::Error> { + clause.super_fold_with(self.as_dyn(), outer_binder) + } + + /// Invoked for every goal. By default, recursively folds the goals contents. + fn fold_goal( + &mut self, + goal: Goal, + outer_binder: DebruijnIndex, + ) -> Result, Self::Error> { + goal.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 fold_free_var_ty( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Result, 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::::BoundVar(bound_var).intern(self.interner())) + } + } + + /// As `fold_free_var_ty`, but for lifetimes. + fn fold_free_var_lifetime( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Result, 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::::BoundVar(bound_var).intern(self.interner())) + } + } + + /// As `fold_free_var_ty`, but for constants. + fn fold_free_var_const( + &mut self, + ty: Ty, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Result, 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.fold_with(self.as_dyn(), outer_binder)?, + value: ConstValue::::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 fold_free_placeholder_ty( + &mut self, + universe: PlaceholderIndex, + outer_binder: DebruijnIndex, + ) -> Result, Self::Error> { + if self.forbid_free_placeholders() { + panic!("unexpected placeholder type `{:?}`", universe) + } else { + Ok(universe.to_ty::(self.interner())) + } + } + + /// As with `fold_free_placeholder_ty`, but for lifetimes. + #[allow(unused_variables)] + fn fold_free_placeholder_lifetime( + &mut self, + universe: PlaceholderIndex, + outer_binder: DebruijnIndex, + ) -> Result, Self::Error> { + if self.forbid_free_placeholders() { + panic!("unexpected placeholder lifetime `{:?}`", universe) + } else { + Ok(universe.to_lifetime(self.interner())) + } + } + + /// As with `fold_free_placeholder_ty`, but for constants. + #[allow(unused_variables)] + fn fold_free_placeholder_const( + &mut self, + ty: Ty, + universe: PlaceholderIndex, + outer_binder: DebruijnIndex, + ) -> Result, Self::Error> { + if self.forbid_free_placeholders() { + panic!("unexpected placeholder const `{:?}`", universe) + } else { + Ok(universe.to_const(self.interner(), ty.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 fold_inference_ty( + &mut self, + var: InferenceVar, + kind: TyVariableKind, + outer_binder: DebruijnIndex, + ) -> Result, Self::Error> { + if self.forbid_inference_vars() { + panic!("unexpected inference type `{:?}`", var) + } else { + Ok(var.to_ty(self.interner(), kind)) + } + } + + /// As with `fold_inference_ty`, but for lifetimes. + #[allow(unused_variables)] + fn fold_inference_lifetime( + &mut self, + var: InferenceVar, + outer_binder: DebruijnIndex, + ) -> Result, Self::Error> { + if self.forbid_inference_vars() { + panic!("unexpected inference lifetime `'{:?}`", var) + } else { + Ok(var.to_lifetime(self.interner())) + } + } + + /// As with `fold_inference_ty`, but for constants. + #[allow(unused_variables)] + fn fold_inference_const( + &mut self, + ty: Ty, + var: InferenceVar, + outer_binder: DebruijnIndex, + ) -> Result, Self::Error> { + if self.forbid_inference_vars() { + panic!("unexpected inference const `{:?}`", var) + } else { + Ok(var.to_const(self.interner(), ty.fold_with(self.as_dyn(), outer_binder)?)) + } + } + + /// Gets the interner that is being folded from. + fn interner(&self) -> I; +} + +/// Applies the given `Folder` 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 Fold: Debug { + /// The type of value that will be produced once folding is done. + /// Typically this is `Self`, unless `Self` contains borrowed + /// values, in which case owned values are produced (for example, + /// one can fold over a `&T` value where `T: Fold`, in which case + /// you get back a `T`, not a `&T`). + type Result; + + /// 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` in the IR or other similar + /// constructs. + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result; +} + +/// For types where "fold" invokes a callback on the `Folder`, the +/// `SuperFold` trait captures the recursive behavior that folds all +/// the contents of the type. +pub trait SuperFold: Fold { + /// Recursively folds the value. + fn super_fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result; +} + +/// "Folding" a type invokes the `fold_ty` method on the folder; this +/// usually (in turn) invokes `super_fold_ty` to fold the individual +/// parts. +impl Fold for Ty { + type Result = Ty; + + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + folder.fold_ty(self, outer_binder) + } +} + +/// "Super fold" for a type invokes te more detailed callbacks on the type +impl SuperFold for Ty +where + I: Interner, +{ + fn super_fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result, 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.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().fold_with(folder, outer_binder)?) + .intern(folder.interner()), + TyKind::InferenceVar(var, kind) => { + folder.fold_inference_ty(*var, *kind, outer_binder)? + } + TyKind::Placeholder(ui) => folder.fold_free_placeholder_ty(*ui, outer_binder)?, + TyKind::Alias(proj) => TyKind::Alias(proj.clone().fold_with(folder, outer_binder)?) + .intern(folder.interner()), + TyKind::Function(fun) => TyKind::Function(fun.clone().fold_with(folder, outer_binder)?) + .intern(folder.interner()), + TyKind::Adt(id, substitution) => TyKind::Adt( + id.fold_with(folder, outer_binder)?, + substitution.clone().fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::AssociatedType(assoc_ty, substitution) => TyKind::AssociatedType( + assoc_ty.fold_with(folder, outer_binder)?, + substitution.clone().fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Scalar(scalar) => { + TyKind::Scalar(scalar.fold_with(folder, outer_binder)?).intern(folder.interner()) + } + TyKind::Str => TyKind::Str.intern(folder.interner()), + TyKind::Tuple(arity, substitution) => TyKind::Tuple( + *arity, + substitution.clone().fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::OpaqueType(opaque_ty, substitution) => TyKind::OpaqueType( + opaque_ty.fold_with(folder, outer_binder)?, + substitution.clone().fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Slice(substitution) => { + TyKind::Slice(substitution.clone().fold_with(folder, outer_binder)?) + .intern(folder.interner()) + } + TyKind::FnDef(fn_def, substitution) => TyKind::FnDef( + fn_def.fold_with(folder, outer_binder)?, + substitution.clone().fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Ref(mutability, lifetime, ty) => TyKind::Ref( + mutability.fold_with(folder, outer_binder)?, + lifetime.clone().fold_with(folder, outer_binder)?, + ty.clone().fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Raw(mutability, ty) => TyKind::Raw( + mutability.fold_with(folder, outer_binder)?, + ty.clone().fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Never => TyKind::Never.intern(folder.interner()), + TyKind::Array(ty, const_) => TyKind::Array( + ty.clone().fold_with(folder, outer_binder)?, + const_.clone().fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Closure(id, substitution) => TyKind::Closure( + id.fold_with(folder, outer_binder)?, + substitution.clone().fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Generator(id, substitution) => TyKind::Generator( + id.fold_with(folder, outer_binder)?, + substitution.clone().fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::GeneratorWitness(id, substitution) => TyKind::GeneratorWitness( + id.fold_with(folder, outer_binder)?, + substitution.clone().fold_with(folder, outer_binder)?, + ) + .intern(folder.interner()), + TyKind::Foreign(id) => { + TyKind::Foreign(id.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 Fold for Lifetime { + type Result = Lifetime; + + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + folder.fold_lifetime(self, outer_binder) + } +} + +impl SuperFold for Lifetime +where + I: Interner, +{ + fn super_fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result, 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.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.fold_inference_lifetime(*var, outer_binder), + LifetimeData::Placeholder(universe) => { + folder.fold_free_placeholder_lifetime(*universe, outer_binder) + } + LifetimeData::Static => Ok(LifetimeData::::Static.intern(folder.interner())), + LifetimeData::Empty(ui) => Ok(LifetimeData::::Empty(*ui).intern(folder.interner())), + LifetimeData::Erased => Ok(LifetimeData::::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 Fold for Const { + type Result = Const; + + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + folder.fold_const(self, outer_binder) + } +} + +impl SuperFold for Const +where + I: Interner, +{ + fn super_fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result, E> { + let interner = folder.interner(); + let ConstData { ref ty, ref value } = self.data(interner); + let mut fold_ty = || ty.clone().fold_with(folder, outer_binder); + match value { + ConstValue::BoundVar(bound_var) => { + if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) { + folder.fold_free_var_const(ty.clone(), bound_var1, outer_binder) + } else { + Ok(self) + } + } + ConstValue::InferenceVar(var) => { + folder.fold_inference_const(ty.clone(), *var, outer_binder) + } + ConstValue::Placeholder(universe) => { + folder.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 Fold for Goal { + type Result = Goal; + + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + folder.fold_goal(self, outer_binder) + } +} + +/// Superfold folds recursively. +impl SuperFold for Goal { + fn super_fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + Ok(Goal::new( + interner, + self.data(interner) + .clone() + .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 Fold for ProgramClause { + type Result = ProgramClause; + + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + folder.fold_program_clause(self, outer_binder) + } +} diff --git a/vendor/chalk-ir-0.80.0/src/fold/binder_impls.rs b/vendor/chalk-ir-0.80.0/src/fold/binder_impls.rs new file mode 100644 index 000000000..baa912499 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/fold/binder_impls.rs @@ -0,0 +1,78 @@ +//! This module contains impls of `Fold` for those types that +//! introduce binders. +//! +//! The more interesting impls of `Fold` remain in the `fold` module. + +use crate::*; + +impl Fold for FnPointer { + type Result = FnPointer; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let FnPointer { + num_binders, + substitution, + sig, + } = self; + Ok(FnPointer { + num_binders, + substitution: substitution.fold_with(folder, outer_binder.shifted_in())?, + sig: FnSig { + abi: sig.abi, + safety: sig.safety, + variadic: sig.variadic, + }, + }) + } +} + +impl Fold for Binders +where + T: HasInterner + Fold, + >::Result: HasInterner, + I: Interner, +{ + type Result = Binders; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let Binders { + binders: self_binders, + value: self_value, + } = self; + let value = self_value.fold_with(folder, outer_binder.shifted_in())?; + let binders = VariableKinds { + interned: self_binders.interned().clone(), + }; + Ok(Binders::new(binders, value)) + } +} + +impl Fold for Canonical +where + I: Interner, + T: HasInterner + Fold, + >::Result: HasInterner, +{ + type Result = Canonical; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let Canonical { + binders: self_binders, + value: self_value, + } = self; + let value = self_value.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-0.80.0/src/fold/boring_impls.rs b/vendor/chalk-ir-0.80.0/src/fold/boring_impls.rs new file mode 100644 index 000000000..9210ecac8 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/fold/boring_impls.rs @@ -0,0 +1,256 @@ +//! This module contains "rote and uninteresting" impls of `Fold` for +//! various types. In general, we prefer to derive `Fold`, but +//! sometimes that doesn't work for whatever reason. +//! +//! The more interesting impls of `Fold` remain in the `fold` module. + +use super::in_place; +use crate::*; +use std::marker::PhantomData; + +impl, I: Interner> Fold for Vec { + type Result = Vec; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + in_place::fallible_map_vec(self, |e| e.fold_with(folder, outer_binder)) + } +} + +impl, I: Interner> Fold for Box { + type Result = Box; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + in_place::fallible_map_box(self, |e| e.fold_with(folder, outer_binder)) + } +} + +macro_rules! tuple_fold { + ($($n:ident),*) => { + impl<$($n: Fold,)* I: Interner> Fold for ($($n,)*) { + type Result = ($($n::Result,)*); + fn fold_with(self, folder: &mut dyn Folder, outer_binder: DebruijnIndex) -> Result + { + #[allow(non_snake_case)] + let ($($n),*) = self; + Ok(($($n.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, I: Interner> Fold for Option { + type Result = Option; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + match self { + None => Ok(None), + Some(e) => Ok(Some(e.fold_with(folder, outer_binder)?)), + } + } +} + +impl Fold for GenericArg { + type Result = GenericArg; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + + let data = self + .data(interner) + .clone() + .fold_with(folder, outer_binder)?; + Ok(GenericArg::new(interner, data)) + } +} + +impl Fold for Substitution { + type Result = Substitution; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + + let folded = self + .iter(interner) + .cloned() + .map(|p| p.fold_with(folder, outer_binder)); + Substitution::from_fallible(interner, folded) + } +} + +impl Fold for Goals { + type Result = Goals; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + let folded = self + .iter(interner) + .cloned() + .map(|p| p.fold_with(folder, outer_binder)); + Goals::from_fallible(interner, folded) + } +} + +impl Fold for ProgramClauses { + type Result = ProgramClauses; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + let folded = self + .iter(interner) + .cloned() + .map(|p| p.fold_with(folder, outer_binder)); + ProgramClauses::from_fallible(interner, folded) + } +} + +impl Fold for QuantifiedWhereClauses { + type Result = QuantifiedWhereClauses; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + let folded = self + .iter(interner) + .cloned() + .map(|p| p.fold_with(folder, outer_binder)); + QuantifiedWhereClauses::from_fallible(interner, folded) + } +} + +impl Fold for Constraints { + type Result = Constraints; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + let folded = self + .iter(interner) + .cloned() + .map(|p| p.fold_with(folder, outer_binder)); + Constraints::from_fallible(interner, folded) + } +} + +#[doc(hidden)] +#[macro_export] +macro_rules! copy_fold { + ($t:ty) => { + impl $crate::fold::Fold for $t { + type Result = Self; + fn fold_with( + self, + _folder: &mut dyn ($crate::fold::Folder), + _outer_binder: DebruijnIndex, + ) -> ::std::result::Result { + 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 $crate::fold::Fold for $t { + type Result = $t; + fn fold_with( + self, + _folder: &mut dyn ($crate::fold::Folder), + _outer_binder: DebruijnIndex, + ) -> ::std::result::Result { + 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 SuperFold for ProgramClauseData { + fn super_fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> ::std::result::Result { + Ok(ProgramClauseData(self.0.fold_with(folder, outer_binder)?)) + } +} + +impl SuperFold for ProgramClause { + fn super_fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> ::std::result::Result { + let clause = self.data(folder.interner()).clone(); + Ok(clause + .super_fold_with(folder, outer_binder)? + .intern(folder.interner())) + } +} + +impl Fold for PhantomData { + type Result = PhantomData; + + fn fold_with( + self, + _folder: &mut dyn Folder, + _outer_binder: DebruijnIndex, + ) -> ::std::result::Result { + Ok(PhantomData) + } +} diff --git a/vendor/chalk-ir-0.80.0/src/fold/in_place.rs b/vendor/chalk-ir-0.80.0/src/fold/in_place.rs new file mode 100644 index 000000000..c81d9113a --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/fold/in_place.rs @@ -0,0 +1,263 @@ +//! Subroutines to help implementers of `Fold` avoid unnecessary heap allocations. + +use std::marker::PhantomData; +use std::{mem, ptr}; + +fn is_zst() -> bool { + mem::size_of::() == 0 +} + +fn is_layout_identical() -> bool { + mem::size_of::() == mem::size_of::() && mem::align_of::() == mem::align_of::() +} + +/// Maps a `Box` to a `Box`, reusing the underlying storage if possible. +pub(super) fn fallible_map_box( + b: Box, + map: impl FnOnce(T) -> Result, +) -> Result, 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::() || is_zst::() { + return map(*b).map(Box::new); + } + + let raw = Box::into_raw(b); + unsafe { + let val = ptr::read(raw); + + // Box -> Box> + let mut raw: Box> = 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> -> Box + Ok(Box::from_raw(Box::into_raw(raw).cast())) + } +} + +/// Maps a `Vec` to a `Vec`, reusing the underlying storage if possible. +pub(super) fn fallible_map_vec( + vec: Vec, + mut map: impl FnMut(T) -> Result, +) -> Result, 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::() || is_zst::() { + return vec.into_iter().map(map).collect(); + } + + let mut vec = VecMappedInPlace::::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 { + ptr: *mut T, + len: usize, + cap: usize, + + map_in_progress: usize, + _elem_tys: PhantomData<(T, U)>, +} + +impl VecMappedInPlace { + fn new(mut vec: Vec) -> Self { + assert!(is_layout_identical::()); + + // 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 { + 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 Drop for VecMappedInPlace { + 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 { + id: T, + drops: Arc>>, + } + + impl RecordDrop { + fn new(id: T, drops: &Arc>>) -> Self { + RecordDrop { + id, + drops: drops.clone(), + } + } + } + + impl RecordDrop { + fn map_to_char(self) -> RecordDrop { + let this = std::mem::ManuallyDrop::new(self); + RecordDrop { + id: (this.id + b'A') as char, + drops: this.drops.clone(), + } + } + } + + impl Drop for RecordDrop { + 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, ()> = 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, ()> = 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, _> = super::fallible_map_box(to_fold, |_| Err(())); + + assert!(res.is_err()); + assert_eq!(*drops.lock().unwrap(), &["0"]); + } +} diff --git a/vendor/chalk-ir-0.80.0/src/fold/shift.rs b/vendor/chalk-ir-0.80.0/src/fold/shift.rs new file mode 100644 index 000000000..2ea957b28 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/fold/shift.rs @@ -0,0 +1,185 @@ +//! Shifting of debruijn indices + +use super::Fold; +use crate::*; + +/// Methods for converting debruijn indices to move values into or out +/// of binders. +pub trait Shift: Fold { + /// Shifts this term in one level of binders. + fn shifted_in(self, interner: I) -> Self::Result; + + /// 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::Result; + + /// Shifts this term out one level of binders. + fn shifted_out(self, interner: I) -> Fallible; + + /// 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; +} + +impl, I: Interner> Shift for T { + fn shifted_in(self, interner: I) -> Self::Result { + self.shifted_in_from(interner, DebruijnIndex::ONE) + } + + fn shifted_in_from(self, interner: I, source_binder: DebruijnIndex) -> T::Result { + self.fold_with( + &mut Shifter { + source_binder, + interner, + }, + DebruijnIndex::INNERMOST, + ) + .unwrap() + } + + fn shifted_out_to(self, interner: I, target_binder: DebruijnIndex) -> Fallible { + self.fold_with( + &mut DownShifter { + target_binder, + interner, + }, + DebruijnIndex::INNERMOST, + ) + } + + fn shifted_out(self, interner: I) -> Fallible { + self.shifted_out_to(interner, DebruijnIndex::ONE) + } +} + +/// A folder that adjusts debruijn indices by a certain amount. +struct Shifter { + source_binder: DebruijnIndex, + interner: I, +} + +impl Shifter { + /// 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 Folder for Shifter { + type Error = NoSolution; + + fn as_dyn(&mut self) -> &mut dyn Folder { + self + } + + fn fold_free_var_ty( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + Ok(TyKind::::BoundVar(self.adjust(bound_var, outer_binder)).intern(self.interner())) + } + + fn fold_free_var_lifetime( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + Ok( + LifetimeData::::BoundVar(self.adjust(bound_var, outer_binder)) + .intern(self.interner()), + ) + } + + fn fold_free_var_const( + &mut self, + ty: Ty, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + // 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 + } +} + +//--------------------------------------------------------------------------- + +/// A shifter that reduces debruijn indices -- in other words, which lifts a value +/// *out* from binders. Consider this example: +/// +struct DownShifter { + target_binder: DebruijnIndex, + interner: I, +} + +impl DownShifter { + /// 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 { + match bound_var.shifted_out_to(self.target_binder) { + Some(bound_var1) => Ok(bound_var1.shifted_in_from(outer_binder)), + None => Err(NoSolution), + } + } +} + +impl Folder for DownShifter { + type Error = NoSolution; + + fn as_dyn(&mut self) -> &mut dyn Folder { + self + } + + fn fold_free_var_ty( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + Ok(TyKind::::BoundVar(self.adjust(bound_var, outer_binder)?).intern(self.interner())) + } + + fn fold_free_var_lifetime( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + Ok( + LifetimeData::::BoundVar(self.adjust(bound_var, outer_binder)?) + .intern(self.interner()), + ) + } + + fn fold_free_var_const( + &mut self, + ty: Ty, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + // 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-0.80.0/src/fold/subst.rs b/vendor/chalk-ir-0.80.0/src/fold/subst.rs new file mode 100644 index 000000000..f7a0b2d69 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/fold/subst.rs @@ -0,0 +1,123 @@ +use super::*; +use crate::fold::shift::Shift; + +/// Substitution used during folding +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], + interner: I, +} + +impl Subst<'_, I> { + /// Applies the substitution by folding + pub fn apply>(interner: I, parameters: &[GenericArg], value: T) -> T::Result { + value + .fold_with( + &mut Subst { + parameters, + interner, + }, + DebruijnIndex::INNERMOST, + ) + .unwrap() + } +} + +impl Folder for Subst<'_, I> { + type Error = NoSolution; + + fn as_dyn(&mut self) -> &mut dyn Folder { + self + } + + /// We are eliminating one binder, but binders outside of that get preserved. + /// + /// So e.g. consider this: + /// + /// ```notrust + /// for { for { [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` binder we are eliminating). + /// + /// This gives us as a result: + /// + /// ```notrust + /// for { [A, u32] } + /// ^ represented as `^0.0` + /// ``` + fn fold_free_var_ty( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + if let Some(index) = bound_var.index_if_innermost() { + match self.parameters[index].data(self.interner()) { + GenericArgData::Ty(t) => { + Ok(t.clone().shifted_in_from(self.interner(), outer_binder)) + } + _ => panic!("mismatched kinds in substitution"), + } + } else { + Ok(bound_var + .shifted_out() + .expect("cannot fail because this is not the innermost") + .shifted_in_from(outer_binder) + .to_ty(self.interner())) + } + } + + /// see `fold_free_var_ty` + fn fold_free_var_lifetime( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + if let Some(index) = bound_var.index_if_innermost() { + match self.parameters[index].data(self.interner()) { + GenericArgData::Lifetime(l) => { + Ok(l.clone().shifted_in_from(self.interner(), outer_binder)) + } + _ => panic!("mismatched kinds in substitution"), + } + } else { + Ok(bound_var + .shifted_out() + .unwrap() + .shifted_in_from(outer_binder) + .to_lifetime(self.interner())) + } + } + + /// see `fold_free_var_ty` + fn fold_free_var_const( + &mut self, + ty: Ty, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + if let Some(index) = bound_var.index_if_innermost() { + match self.parameters[index].data(self.interner()) { + GenericArgData::Const(c) => { + Ok(c.clone().shifted_in_from(self.interner(), outer_binder)) + } + _ => panic!("mismatched kinds in substitution"), + } + } else { + Ok(bound_var + .shifted_out() + .unwrap() + .shifted_in_from(outer_binder) + .to_const(self.interner(), ty)) + } + } + + fn interner(&self) -> I { + self.interner + } +} diff --git a/vendor/chalk-ir-0.80.0/src/interner.rs b/vendor/chalk-ir-0.80.0/src/interner.rs new file mode 100644 index 000000000..8a3f88cc4 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/interner.rs @@ -0,0 +1,702 @@ +//! 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` instance directly, but +/// rather prefer a `Ty`. 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`, 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`, 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`, 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`, 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`, 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`, 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`, 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`, 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`, 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`, 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`, 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`, 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`, 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`, 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`, 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, fmt: &mut fmt::Formatter<'_>) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, fmt: &mut fmt::Formatter<'_>) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, fmt: &mut fmt::Formatter<'_>) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, fmt: &mut fmt::Formatter<'_>) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, fmt: &mut fmt::Formatter<'_>) -> Option { + 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, fmt: &mut fmt::Formatter<'_>) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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 { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + 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::InternedType; + + /// Lookup the `TyKind` from an interned type. + fn ty_data(self, ty: &Self::InternedType) -> &TyData; + + /// 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::InternedLifetime; + + /// Lookup the `LifetimeData` that was interned to create a `InternedLifetime`. + fn lifetime_data(self, lifetime: &Self::InternedLifetime) -> &LifetimeData; + + /// 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::InternedConst; + + /// Lookup the `ConstData` that was interned to create a `InternedConst`. + fn const_data(self, constant: &Self::InternedConst) -> &ConstData; + + /// 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::InternedGenericArg; + + /// Lookup the `LifetimeData` that was interned to create a `InternedLifetime`. + fn generic_arg_data(self, lifetime: &Self::InternedGenericArg) -> &GenericArgData; + + /// 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::InternedGoal; + + /// Lookup the `GoalData` that was interned to create a `InternedGoal`. + fn goal_data(self, goal: &Self::InternedGoal) -> &GoalData; + + /// 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( + self, + data: impl IntoIterator, E>>, + ) -> Result; + + /// Lookup the `GoalsData` that was interned to create a `InternedGoals`. + fn goals_data(self, goals: &Self::InternedGoals) -> &[Goal]; + + /// 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( + self, + data: impl IntoIterator, E>>, + ) -> Result; + + /// Lookup the `SubstitutionData` that was interned to create a `InternedSubstitution`. + fn substitution_data(self, substitution: &Self::InternedSubstitution) -> &[GenericArg]; + + /// 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::InternedProgramClause; + + /// Lookup the `ProgramClauseData` that was interned to create a `ProgramClause`. + fn program_clause_data(self, clause: &Self::InternedProgramClause) -> &ProgramClauseData; + + /// 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( + self, + data: impl IntoIterator, E>>, + ) -> Result; + + /// Lookup the `ProgramClauseData` that was interned to create a `ProgramClause`. + fn program_clauses_data(self, clauses: &Self::InternedProgramClauses) + -> &[ProgramClause]; + + /// 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( + self, + data: impl IntoIterator, E>>, + ) -> Result; + + /// Lookup the slice of `QuantifiedWhereClause` that was interned to + /// create a `QuantifiedWhereClauses`. + fn quantified_where_clauses_data( + self, + clauses: &Self::InternedQuantifiedWhereClauses, + ) -> &[QuantifiedWhereClause]; + + /// 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( + self, + data: impl IntoIterator, E>>, + ) -> Result; + + /// Lookup the slice of `VariableKinds` that was interned to + /// create a `VariableKinds`. + fn variable_kinds_data( + self, + variable_kinds: &Self::InternedVariableKinds, + ) -> &[VariableKind]; + + /// 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( + self, + data: impl IntoIterator, E>>, + ) -> Result; + + /// Lookup the slice of `CanonicalVariableKind` that was interned to + /// create a `CanonicalVariableKinds`. + fn canonical_var_kinds_data( + self, + canonical_var_kinds: &Self::InternedCanonicalVarKinds, + ) -> &[CanonicalVarKind]; + + /// 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( + self, + data: impl IntoIterator>, E>>, + ) -> Result; + + /// Lookup the slice of `Constraint` that was interned to + /// create a `Constraints`. + fn constraints_data( + self, + constraints: &Self::InternedConstraints, + ) -> &[InEnvironment>]; + + /// 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( + self, + data: impl IntoIterator>, + ) -> Result; + + /// 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` to the parameter `I`. +/// +/// It's particularly useful for writing `Fold` impls for generic types like +/// `Binder`, since it allows us to figure out the interner of `T`. +pub trait HasInterner { + /// The interner associated with the type. + type Interner: Interner; +} + +impl HasInterner for [T] { + type Interner = T::Interner; +} + +impl HasInterner for Vec { + type Interner = T::Interner; +} + +impl HasInterner for Box { + type Interner = T::Interner; +} + +impl HasInterner for Arc { + type Interner = T::Interner; +} + +impl HasInterner for &T { + type Interner = T::Interner; +} + +impl HasInterner for PhantomData { + type Interner = I; +} + +impl HasInterner for (A, B) +where + A: HasInterner, + B: HasInterner, + I: Interner, +{ + type Interner = I; +} + +impl HasInterner for (A, B, C) +where + A: HasInterner, + B: HasInterner, + C: HasInterner, + 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-0.80.0/src/lib.rs b/vendor/chalk-ir-0.80.0/src/lib.rs new file mode 100644 index 000000000..9376a6563 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/lib.rs @@ -0,0 +1,3077 @@ +//! 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::{Fold, Folder, Subst, SuperFold}; +use crate::visit::{SuperVisit, Visit, VisitExt, Visitor}; +use chalk_derive::{Fold, HasInterner, SuperVisit, Visit, 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 = Result; + +/// A combination of `Fallible` and `Floundered`. +pub enum FallibleOrFloundered { + /// 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 std::fmt::Debug for $id { + 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 + /// ``` + /// + /// Here, the "ambient" variance starts as covariant. `*mut T` is + /// invariant with respect to `T`, so the variance in which the + /// `Vec` appears is `Covariant.xform(Invariant)`, which + /// yields `Invariant`. Now, the type `Vec` 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, *mut Vec` appears is + /// `Contravariant.xform(Covariant)` or `Contravariant`. The same + /// is true for its `i32` argument. In the `*mut T` case, the + /// variance of `Vec` is `Contravariant.xform(Invariant)`, + /// and hence the outermost type is `Invariant` with respect to + /// `Vec` (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, Fold, Visit, HasInterner)] +/// The set of assumptions we've made so far, and the current number of +/// universal (forall) quantifiers we're within. +pub struct Environment { + /// The clauses in the environment. + pub clauses: ProgramClauses, +} + +impl Copy for Environment where I::InternedProgramClauses: Copy {} + +impl Environment { + /// 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(&self, interner: I, clauses: II) -> Self + where + II: IntoIterator>, + { + 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, Fold, Visit)] +#[allow(missing_docs)] +pub struct InEnvironment { + pub environment: Environment, + pub goal: G, +} + +impl + Copy, I: Interner> Copy for InEnvironment where + I::InternedProgramClauses: Copy +{ +} + +impl InEnvironment { + /// Creates a new environment/goal pair. + pub fn new(environment: &Environment, goal: G) -> Self { + InEnvironment { + environment: environment.clone(), + goal, + } + } + + /// Maps the goal without touching the environment. + pub fn map(self, op: OP) -> InEnvironment + where + OP: FnOnce(G) -> H, + H: HasInterner, + { + InEnvironment { + environment: self.environment, + goal: op(self.goal), + } + } +} + +impl HasInterner for InEnvironment { + 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 { 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 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, +} + +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(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(pub I::DefId); + +/// The id for an impl. +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct ImplId(pub I::DefId); + +/// Id for a specific clause. +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct ClauseId(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(pub I::DefId); + +/// Id for an opaque type. +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct OpaqueTyId(pub I::DefId); + +/// Function definition id. +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct FnDefId(pub I::DefId); + +/// Id for Rust closures. +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct ClosureId(pub I::DefId); + +/// Id for Rust generators. +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct GeneratorId(pub I::DefId); + +/// Id for foreign types. +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct ForeignDefId(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 { + interned: I::InternedType, +} + +impl Ty { + /// Creates a type from `TyKind`. + pub fn new(interner: I, data: impl CastTo>) -> 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::ty_data(interner, &self.interned) + } + + /// Gets the underlying type kind. + pub fn kind(&self, interner: I) -> &TyKind { + &I::ty_data(interner, &self.interned).kind + } + + /// Creates a `FromEnv` constraint using this type. + pub fn from_env(&self) -> FromEnv { + FromEnv::Ty(self.clone()) + } + + /// Creates a WF-constraint for this type. + pub fn well_formed(&self) -> WellFormed { + 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 { + 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 { + 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 { + 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) -> 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> { + 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 { + /// The kind + pub kind: TyKind, + /// 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 { + /// Abstract data types, i.e., structs, unions, or enumerations. + /// For example, a type like `Vec`. + Adt(AdtId, Substitution), + + /// an associated type like `Iterator::Item`; see `AssociatedType` for details + AssociatedType(AssocTypeId, Substitution), + + /// a scalar type like `bool` or `u32` + Scalar(Scalar), + + /// a tuple of the given arity + Tuple(usize, Substitution), + + /// an array type like `[T; N]` + Array(Ty, Const), + + /// a slice type like `[T]` + Slice(Ty), + + /// a raw pointer type like `*const T` or `*mut T` + Raw(Mutability, Ty), + + /// a reference type like `&T` or `&mut T` + Ref(Mutability, Lifetime, Ty), + + /// a placeholder for opaque types like `impl Trait` + OpaqueType(OpaqueTyId, Substitution), + + /// a function definition + FnDef(FnDefId, Substitution), + + /// the string primitive type + Str, + + /// the never type `!` + Never, + + /// A closure. + Closure(ClosureId, Substitution), + + /// A generator. + Generator(GeneratorId, Substitution), + + /// A generator witness. + GeneratorWitness(GeneratorId, Substitution), + + /// foreign types + Foreign(ForeignDefId), + + /// 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 { .. }`. 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), + + /// An "alias" type represents some form of type alias, such as: + /// - An associated type projection like `::Item` + /// - `impl Trait` types + /// - Named type aliases like `type Foo = Vec` + Alias(AliasTy), + + /// 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), + + /// 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 Copy for TyKind +where + I::InternedLifetime: Copy, + I::InternedSubstitution: Copy, + I::InternedVariableKinds: Copy, + I::InternedQuantifiedWhereClauses: Copy, + I::InternedType: Copy, + I::InternedConst: Copy, +{ +} + +impl TyKind { + /// Casts the type data to a type. + pub fn intern(self, interner: I) -> Ty { + 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(self, interner: I) -> Ty { + TyKind::::BoundVar(self).intern(interner) + } + + /// Wrap the bound variable in a lifetime. + pub fn to_lifetime(self, interner: I) -> Lifetime { + LifetimeData::::BoundVar(self).intern(interner) + } + + /// Wraps the bound variable in a constant. + pub fn to_const(self, interner: I, ty: Ty) -> Const { + ConstData { + ty, + value: ConstValue::::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.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.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 { + 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 { + 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: +/// 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 forall forall + /// ``` + /// + /// 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 for for for + /// ^ outer binder + /// ``` + /// + /// Assume further that the `outer_binder` argument is 2, + /// which means that it is referring to the `for` 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 { + 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 for for for + /// ^ outer binder + /// ``` + /// + /// Assume further that the `outer_binder` argument is 2, + /// which means that it is referring to the `for` 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 { + 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: 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 { +/// vec![ +/// // A QuantifiedWhereClause: +/// forall { ^1.0: Fn(&^0.0 u32) } +/// ] +/// } +/// ``` +/// +/// The outer `exists` 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, Fold, Visit, HasInterner)] +pub struct DynTy { + /// The unknown self type. + pub bounds: Binders>, + /// Lifetime of the `DynTy`. + pub lifetime: Lifetime, +} + +impl Copy for DynTy +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 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(self, interner: I, kind: TyVariableKind) -> Ty { + TyKind::::InferenceVar(self, kind).intern(interner) + } + + /// Wraps the inference variable in a lifetime. + pub fn to_lifetime(self, interner: I) -> Lifetime { + LifetimeData::::InferenceVar(self).intern(interner) + } + + /// Wraps the inference variable in a constant. + pub fn to_const(self, interner: I, ty: Ty) -> Const { + ConstData { + ty, + value: ConstValue::::InferenceVar(self), + } + .intern(interner) + } +} + +/// A function signature. +#[derive(Clone, Copy, PartialEq, Eq, Hash, HasInterner, Debug)] +#[allow(missing_docs)] +pub struct FnSig { + pub abi: I::FnAbi, + pub safety: Safety, + pub variadic: bool, +} +/// A wrapper for the substs on a Fn. +#[derive(Clone, PartialEq, Eq, Hash, HasInterner, Fold, Visit)] +pub struct FnSubst(pub Substitution); + +impl Copy for FnSubst 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 { + pub num_binders: usize, + pub sig: FnSig, + pub substitution: FnSubst, +} + +impl Copy for FnPointer where I::InternedSubstitution: Copy {} + +impl FnPointer { + /// Represent the current `Fn` as if it was wrapped in `Binders` + pub fn into_binders(self, interner: I) -> Binders> { + 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> { + 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 { + interned: I::InternedConst, +} + +impl Const { + /// Create a `Const` using something that can be cast to const data. + pub fn new(interner: I, data: impl CastTo>) -> 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::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 { + 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 { + 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 { + /// Type that holds the constant. + pub ty: Ty, + /// The value of the constant. + pub value: ConstValue, +} + +/// A constant value, not necessarily concrete. +#[derive(Clone, PartialEq, Eq, Hash, HasInterner)] +pub enum ConstValue { + /// 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), +} + +impl Copy for ConstValue where I::InternedConcreteConst: Copy {} + +impl ConstData { + /// Wraps the constant data in a `Const`. + pub fn intern(self, interner: I) -> Const { + 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 { + /// The interned constant. + pub interned: I::InternedConcreteConst, +} + +impl ConcreteConst { + /// Checks whether two concrete constants are equal. + pub fn const_eq(&self, ty: &Ty, other: &ConcreteConst, 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 { + interned: I::InternedLifetime, +} + +impl Lifetime { + /// Create a lifetime from lifetime data + /// (or something that can be cast to lifetime data). + pub fn new(interner: I, data: impl CastTo>) -> 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::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 { + 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 { + 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::Empty(_) => 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 | LifetimeData::Empty(_) => 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 { + /// 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 empty lifetime: a lifetime shorter than any other lifetime in a + /// universe with a lesser or equal index. The universe only non-zero in + /// lexical region resolve in rustc, so chalk shouldn't ever see a non-zero + /// index. + Empty(UniverseIndex), + /// An erased lifetime, used by rustc to improve caching when we doesn't + /// care about lifetimes + Erased, + /// Lifetime on phantom data. + Phantom(Void, PhantomData), +} + +impl LifetimeData { + /// Wrap the lifetime data in a lifetime. + pub fn intern(self, interner: I) -> Lifetime { + 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(self, interner: I) -> Lifetime { + LifetimeData::::Placeholder(self).intern(interner) + } + + /// Create an interned type. + pub fn to_ty(self, interner: I) -> Ty { + TyKind::Placeholder(self).intern(interner) + } + + /// Wrap the placeholder index in a constant. + pub fn to_const(self, interner: I, ty: Ty) -> Const { + 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 { + Ty(TyVariableKind), + Lifetime, + Const(Ty), +} + +impl interner::HasInterner for VariableKind { + type Interner = I; +} + +impl Copy for VariableKind where I::InternedType: Copy {} + +impl VariableKind { + fn to_bound_variable(&self, interner: I, bound_var: BoundVar) -> GenericArg { + 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 { + interned: I::InternedGenericArg, +} + +impl GenericArg { + /// Constructs a generic argument using `GenericArgData`. + pub fn new(interner: I, data: GenericArgData) -> 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::generic_arg_data(interner, &self.interned) + } + + /// Asserts that this is a type argument. + pub fn assert_ty_ref(&self, interner: I) -> &Ty { + self.ty(interner).unwrap() + } + + /// Asserts that this is a lifetime argument. + pub fn assert_lifetime_ref(&self, interner: I) -> &Lifetime { + self.lifetime(interner).unwrap() + } + + /// Asserts that this is a constant argument. + pub fn assert_const_ref(&self, interner: I) -> &Const { + 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> { + 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> { + 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> { + match self.data(interner) { + GenericArgData::Const(c) => Some(c), + _ => None, + } + } + + /// Compute type flags for GenericArg + 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, Visit, Fold, Zip)] +pub enum GenericArgData { + /// Type argument + Ty(Ty), + /// Lifetime argument + Lifetime(Lifetime), + /// Constant argument + Const(Const), +} + +impl Copy for GenericArgData +where + I::InternedType: Copy, + I::InternedLifetime: Copy, + I::InternedConst: Copy, +{ +} + +impl GenericArgData { + /// Create an interned type. + pub fn intern(self, interner: I) -> GenericArg { + GenericArg::new(interner, self) + } +} + +/// A value with an associated variable kind. +#[derive(Clone, PartialEq, Eq, Hash)] +pub struct WithKind { + /// The associated variable kind. + pub kind: VariableKind, + /// The wrapped value. + value: T, +} + +impl Copy for WithKind where I::InternedType: Copy {} + +impl HasInterner for WithKind { + type Interner = I; +} + +impl From> for (VariableKind, T) { + fn from(with_kind: WithKind) -> Self { + (with_kind.kind, with_kind.value) + } +} + +impl WithKind { + /// Creates a `WithKind` from a variable kind and a value. + pub fn new(kind: VariableKind, value: T) -> Self { + Self { kind, value } + } + + /// Maps the value in `WithKind`. + pub fn map(self, op: OP) -> WithKind + where + OP: FnOnce(T) -> U, + { + WithKind { + kind: self.kind, + value: op(self.value), + } + } + + /// Maps a function taking `WithKind` over `&WithKind`. + pub fn map_ref(&self, op: OP) -> WithKind + 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 = WithKind; + +/// An alias, which is a trait indirection such as a projection or opaque type. +#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)] +pub enum AliasTy { + /// An associated type projection. + Projection(ProjectionTy), + /// An opaque type. + Opaque(OpaqueTy), +} + +impl Copy for AliasTy where I::InternedSubstitution: Copy {} + +impl AliasTy { + /// Create an interned type for this alias. + pub fn intern(self, interner: I) -> Ty { + 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 `>::AssocItem`. +#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner)] +pub struct ProjectionTy { + /// The id for the associated type member. + pub associated_ty_id: AssocTypeId, + /// The substitution for the projection. + pub substitution: Substitution, +} + +impl Copy for ProjectionTy where I::InternedSubstitution: Copy {} + +impl ProjectionTy { + /// Gets the type parameters of the `Self` type in this alias type. + pub fn self_type_parameter(&self, interner: I) -> Ty { + self.substitution + .iter(interner) + .find_map(move |p| p.ty(interner)) + .unwrap() + .clone() + } +} + +/// An opaque type `opaque type T<..>: Trait = HiddenTy`. +#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner)] +pub struct OpaqueTy { + /// The id for the opaque type. + pub opaque_ty_id: OpaqueTyId, + /// The substitution for the opaque type. + pub substitution: Substitution, +} + +impl Copy for OpaqueTy 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` (e.g. `i32: Copy`), which mentions that the type +/// implements the trait. +/// - `>` (e.g. `i32 as Copy`), which casts the type to +/// that specific trait. +#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner)] +pub struct TraitRef { + /// The trait id. + pub trait_id: TraitId, + /// The substitution, containing both the `Self` type and the parameters. + pub substitution: Substitution, +} + +impl Copy for TraitRef where I::InternedSubstitution: Copy {} + +impl TraitRef { + /// Gets all type parameters in this trait ref, including `Self`. + pub fn type_parameters(&self, interner: I) -> impl Iterator> + '_ { + 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 { + self.type_parameters(interner).next().unwrap() + } + + /// Construct a `FromEnv` using this trait ref. + pub fn from_env(self) -> FromEnv { + FromEnv::Trait(self) + } + + /// Construct a `WellFormed` using this trait ref. + pub fn well_formed(self) -> WellFormed { + 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, Fold, Visit, HasInterner, Zip)] +#[allow(missing_docs)] +pub struct LifetimeOutlives { + pub a: Lifetime, + pub b: Lifetime, +} + +impl Copy for LifetimeOutlives 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, Fold, Visit, HasInterner, Zip)] +pub struct TypeOutlives { + /// The type which must outlive the given lifetime. + pub ty: Ty, + /// The lifetime which the type must outlive. + pub lifetime: Lifetime, +} + +impl Copy for TypeOutlives +where + I::InternedLifetime: Copy, + I::InternedType: Copy, +{ +} + +/// Where clauses that can be written by a Rust programmer. +#[derive(Clone, PartialEq, Eq, Hash, Fold, SuperVisit, HasInterner, Zip)] +pub enum WhereClause { + /// Type implements a trait. + Implemented(TraitRef), + /// Type is equal to an alias. + AliasEq(AliasEq), + /// One lifetime outlives another. + LifetimeOutlives(LifetimeOutlives), + /// Type outlives a lifetime. + TypeOutlives(TypeOutlives), +} + +impl Copy for WhereClause +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, Fold, Visit, HasInterner, Zip)] +pub enum WellFormed { + /// 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), + + /// A predicate which is true when some type is well-formed. + /// For example, given the following type definition: + /// + /// ```notrust + /// struct Set where K: Hash { + /// ... + /// } + /// ``` + /// + /// then we have the following rule: `WellFormedTy(Set) :- Implemented(K: Hash)`. + Ty(Ty), +} + +impl Copy for WellFormed +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, Fold, Visit, HasInterner, Zip)] +pub enum FromEnv { + /// 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 { + /// if (FromEnv(T: Copy)) { + /// T: Clone + /// } + /// } + /// ``` + Trait(TraitRef), + + /// 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)` to derive that `K: Hash`, like in: + /// + /// ```notrust + /// forall { + /// if (FromEnv(Set)) { + /// K: Hash + /// } + /// } + /// ``` + Ty(Ty), +} + +impl Copy for FromEnv +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, Fold, SuperVisit, HasInterner, Zip)] +pub enum DomainGoal { + /// Simple goal that is true if the where clause is true. + Holds(WhereClause), + + /// True if the type or trait ref is well-formed. + WellFormed(WellFormed), + + /// True if the trait ref can be derived from in-scope where clauses. + FromEnv(FromEnv), + + /// True if the alias type can be normalized to some other type + Normalize(Normalize), + + /// 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`, it is true if `T` is local. + IsLocal(Ty), + + /// 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`, it is true if `T` is upstream. + IsUpstream(Ty), + + /// 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: + /// forall { + /// IsFullyVisible(S) :- + /// 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), + + /// 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), + + /// 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 { if (DownstreamType(T)) { /* ... */ } } + /// + /// This makes a new type `T` available and makes `DownstreamType(T)` provable for that type. + DownstreamType(Ty), + + /// 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), +} + +impl Copy for DomainGoal +where + I::InternedSubstitution: Copy, + I::InternedLifetime: Copy, + I::InternedType: Copy, +{ +} + +/// A where clause that can contain `forall<>` or `exists<>` quantifiers. +pub type QuantifiedWhereClause = Binders>; + +impl WhereClause { + /// Turn a where clause into the WF version of it i.e.: + /// * `Implemented(T: Trait)` maps to `WellFormed(T: Trait)` + /// * `ProjectionEq(::Item = Foo)` maps to `WellFormed(::Item = Foo)` + /// * any other clause maps to itself + pub fn into_well_formed_goal(self, interner: I) -> DomainGoal { + 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 { + 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> { + match self { + WhereClause::Implemented(trait_ref) => Some(trait_ref.trait_id), + WhereClause::AliasEq(_) => None, + WhereClause::LifetimeOutlives(_) => None, + WhereClause::TypeOutlives(_) => None, + } + } +} + +impl QuantifiedWhereClause { + /// As with `WhereClause::into_well_formed_goal`, but for a + /// quantified where clause. For example, `forall { + /// Implemented(T: Trait)}` would map to `forall { + /// WellFormed(T: Trait) }`. + pub fn into_well_formed_goal(self, interner: I) -> Binders> { + self.map(|wc| wc.into_well_formed_goal(interner)) + } + + /// As with `WhereClause::into_from_env_goal`, but mapped over any + /// binders. For example, `forall { + /// Implemented(T: Trait)}` would map to `forall { + /// FromEnv(T: Trait) }`. + pub fn into_from_env_goal(self, interner: I) -> Binders> { + 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> { + self.skip_binders().trait_id() + } +} + +impl DomainGoal { + /// Convert `Implemented(...)` into `FromEnv(...)`, but leave other + /// goals unchanged. + pub fn into_from_env_goal(self, interner: I) -> DomainGoal { + 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> { + 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, Fold, Visit, Zip)] +#[allow(missing_docs)] +pub struct EqGoal { + pub a: GenericArg, + pub b: GenericArg, +} + +impl Copy for EqGoal where I::InternedGenericArg: Copy {} + +/// Subtype goal: tries to prove that `a` is a subtype of `b` +#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, Zip)] +#[allow(missing_docs)] +pub struct SubtypeGoal { + pub a: Ty, + pub b: Ty, +} + +impl Copy for SubtypeGoal 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, Fold, Visit, Zip)] +#[allow(missing_docs)] +pub struct Normalize { + pub alias: AliasTy, + pub ty: Ty, +} + +impl Copy for Normalize +where + I::InternedSubstitution: Copy, + I::InternedType: Copy, +{ +} + +/// Proves **equality** between an alias and a type. +#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, Zip)] +#[allow(missing_docs)] +pub struct AliasEq { + pub alias: AliasTy, + pub ty: Ty, +} + +impl Copy for AliasEq +where + I::InternedSubstitution: Copy, + I::InternedType: Copy, +{ +} + +impl HasInterner for AliasEq { + 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 { + /// The binders that quantify over the value. + pub binders: VariableKinds, + + /// The value being quantified over. + value: T, +} + +impl Copy for Binders where + ::InternedVariableKinds: Copy +{ +} + +impl HasInterner for Binders { + type Interner = T::Interner; +} + +impl Binders<&T> { + /// Converts a `Binders<&T>` to a `Binders` by cloning `T`. + pub fn cloned(self) -> Binders { + self.map(Clone::clone) + } +} + +impl Binders { + /// Create new binders. + pub fn new(binders: VariableKinds, 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) { + (self.value, self.binders) + } + + /// Converts `&Binders` 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(self, op: OP) -> Binders + where + OP: FnOnce(T) -> U, + U: HasInterner, + { + 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(self, op: OP) -> Option> + where + OP: FnOnce(T) -> Option, + U: HasInterner, + { + let value = op(self.value)?; + Some(Binders { + binders: self.binders, + value, + }) + } + + /// Maps a function taking `Binders<&T>` over `&Binders`. + pub fn map_ref<'a, U, OP>(&'a self, op: OP) -> Binders + where + OP: FnOnce(&'a T) -> U, + U: HasInterner, + { + 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 { + 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, + ) -> Binders { + // 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 Binders> +where + T: Fold + HasInterner, + T::Result: HasInterner, + I: Interner, +{ + /// This turns two levels of binders (`for for`) into one level (`for`). + pub fn fuse_binders(self, interner: T::Interner) -> Binders { + 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 From> for (VariableKinds, T) { + fn from(binders: Binders) -> Self { + (binders.binders, binders.value) + } +} + +impl Binders +where + T: Fold + HasInterner, + I: Interner, +{ + /// Substitute `parameters` for the variables introduced by these + /// binders. So if the binders represent (e.g.) ` { T }` and + /// parameters is the slice `[A, B]`, then returns `[X => A, Y => + /// B] T`. + pub fn substitute( + self, + interner: I, + parameters: &(impl AsParameters + ?Sized), + ) -> T::Result { + 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>, for instance. +/// Each element will include the same set of parameter bounds. +impl IntoIterator for Binders +where + V: HasInterner + IntoIterator, + U: HasInterner, +{ + type Item = Binders; + type IntoIter = BindersIntoIterator; + + fn into_iter(self) -> Self::IntoIter { + BindersIntoIterator { + iter: self.value.into_iter(), + binders: self.binders, + } + } +} + +/// `IntoIterator` for binders. +pub struct BindersIntoIterator { + iter: ::IntoIter, + binders: VariableKinds, +} + +impl Iterator for BindersIntoIterator +where + V: HasInterner + IntoIterator, + ::Item: HasInterner, +{ + type Item = Binders<::Item>; + fn next(&mut self) -> Option { + 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, Fold, Visit, HasInterner, Zip)] +pub struct ProgramClauseImplication { + /// The consequence of the clause, which holds if the conditions holds. + pub consequence: DomainGoal, + + /// The condition goals that should hold. + pub conditions: Goals, + + /// The lifetime constraints that should be proven. + pub constraints: Constraints, + + /// 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, Fold, HasInterner, Zip)] +pub struct ProgramClauseData(pub Binders>); + +impl ProgramClauseImplication { + /// Change the implication into an application holding a `FromEnv` goal. + pub fn into_from_env_clause(self, interner: I) -> ProgramClauseImplication { + 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 ProgramClauseData { + /// Change the program clause data into a `FromEnv` program clause. + pub fn into_from_env_clause(self, interner: I) -> ProgramClauseData { + ProgramClauseData(self.0.map(|i| i.into_from_env_clause(interner))) + } + + /// Intern the program clause data. + pub fn intern(self, interner: I) -> ProgramClause { + 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 { + interned: I::InternedProgramClause, +} + +impl ProgramClause { + /// Create a new program clause using `ProgramClauseData`. + pub fn new(interner: I, clause: ProgramClauseData) -> 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 { + 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 { + 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 { + /// The item that is canonicalized. + pub value: T, + + /// The kind/universe of the variable. + pub binders: CanonicalVarKinds, +} + +impl HasInterner for Canonical { + 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 { + /// The wrapped `Canonical`. + pub canonical: Canonical, + + /// The number of universes that have been collapsed. + pub universes: usize, +} + +impl UCanonical { + /// 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>, + ) -> 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 { + 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::>(), + ) + } +} + +#[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 { + interned: I::InternedGoal, +} + +impl Goal { + /// Create a new goal using `GoalData`. + pub fn new(interner: I, interned: GoalData) -> 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 { + interner.goal_data(&self.interned) + } + + /// Create a goal using a `forall` or `exists` quantifier. + pub fn quantify(self, interner: I, kind: QuantifierKind, binders: VariableKinds) -> Goal { + 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 { 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) -> Goal { + 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 Goal +where + I: Interner, +{ + /// Creates a single goal that only holds if a list of goals holds. + pub fn all(interner: I, iter: II) -> Self + where + II: IntoIterator>, + { + 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, Fold, Visit, HasInterner, Zip)] +/// A general goal; this is the full range of questions you can pose to Chalk. +pub enum GoalData { + /// Introduces a binding at depth 0, shifting other bindings up + /// (deBruijn index). + Quantified(QuantifierKind, Binders>), + + /// A goal that holds given some clauses (like an if-statement). + Implies(ProgramClauses, Goal), + + /// List of goals that all should hold. + All(Goals), + + /// Negation: the inner goal should not hold. + Not(Goal), + + /// Make two things equal; the rules for doing so are well known to the logic + EqGoal(EqGoal), + + /// Make one thing a subtype of another; the rules for doing so are well known to the logic + SubtypeGoal(SubtypeGoal), + + /// A "domain goal" indicates some base sort of goal that can be + /// proven via program clauses + DomainGoal(DomainGoal), + + /// 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 + /// }`. 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 { not { X = Y } }` also winds up + /// as cannot prove. + CannotProve, +} + +impl Copy for GoalData +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 GoalData { + /// Create an interned goal. + pub fn intern(self, interner: I) -> Goal { + 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, Fold, Visit, HasInterner, Zip)] +pub enum Constraint { + /// Outlives constraint `'a: 'b`, indicating that the value of `'a` must be + /// a superset of the value of `'b`. + LifetimeOutlives(Lifetime, Lifetime), + + /// Type outlives constraint `T: 'a`, indicating that the type `T` must live + /// at least as long as the value of `'a`. + TypeOutlives(Ty, Lifetime), +} + +impl Copy for Constraint +where + I::InternedLifetime: Copy, + I::InternedType: Copy, +{ +} + +impl Substitution { + /// 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(&self, value: T, interner: I) -> T::Result + where + T: Fold, + { + Substitute::apply(self, value, interner) + } + + /// Gets an iterator of all type parameters. + pub fn type_parameters(&self, interner: I) -> impl Iterator> + '_ { + self.iter(interner) + .filter_map(move |p| p.ty(interner)) + .cloned() + } + + /// Compute type flags for Substitution + 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 + } +} + +struct SubstFolder<'i, I: Interner, A: AsParameters> { + interner: I, + subst: &'i A, +} + +impl> SubstFolder<'_, I, A> { + /// Index into the list of parameters. + pub fn at(&self, index: usize) -> &GenericArg { + let interner = self.interner; + &self.subst.as_parameters(interner)[index] + } +} + +/// Convert a value to a list of parameters. +pub trait AsParameters { + /// Convert the current value to parameters. + fn as_parameters(&self, interner: I) -> &[GenericArg]; +} + +impl AsParameters for Substitution { + #[allow(unreachable_code, unused_variables)] + fn as_parameters(&self, interner: I) -> &[GenericArg] { + self.as_slice(interner) + } +} + +impl AsParameters for [GenericArg] { + fn as_parameters(&self, _interner: I) -> &[GenericArg] { + self + } +} + +impl AsParameters for [GenericArg; 1] { + fn as_parameters(&self, _interner: I) -> &[GenericArg] { + self + } +} + +impl AsParameters for Vec> { + fn as_parameters(&self, _interner: I) -> &[GenericArg] { + self + } +} + +impl AsParameters for &T +where + T: ?Sized + AsParameters, +{ + fn as_parameters(&self, interner: I) -> &[GenericArg] { + 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: AsParameters { + /// Apply the substitution to a value. + fn apply>(&self, value: T, interner: I) -> T::Result; +} + +impl> Substitute for A { + fn apply(&self, value: T, interner: I) -> T::Result + where + T: Fold, + { + value + .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 { + /// Converts the binders in scope to references to those binders. + fn to_generic_arg(&self, interner: I) -> GenericArg { + 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; +} + +impl<'a, I: Interner> ToGenericArg for (usize, &'a VariableKind) { + fn to_generic_arg_at_depth(&self, interner: I, debruijn: DebruijnIndex) -> GenericArg { + let &(index, binder) = self; + let bound_var = BoundVar::new(debruijn, index); + binder.to_bound_variable(interner, bound_var) + } +} + +impl<'i, I: Interner, A: AsParameters> Folder for &SubstFolder<'i, I, A> { + type Error = NoSolution; + + fn as_dyn(&mut self) -> &mut dyn Folder { + self + } + + fn fold_free_var_ty( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST); + let ty = self.at(bound_var.index); + let ty = ty.assert_ty_ref(self.interner()); + Ok(ty.clone().shifted_in_from(self.interner(), outer_binder)) + } + + fn fold_free_var_lifetime( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST); + let l = self.at(bound_var.index); + let l = l.assert_lifetime_ref(self.interner()); + Ok(l.clone().shifted_in_from(self.interner(), outer_binder)) + } + + fn fold_free_var_const( + &mut self, + _ty: Ty, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST); + let c = self.at(bound_var.index); + let c = c.assert_const_ref(self.interner()); + Ok(c.clone().shifted_in_from(self.interner(), 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 { + interned: I::$interned, + } + + impl $seq { + /// 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 $seq { + /// Tries to create a sequence using an iterator of element-like things. + pub fn from_fallible( + interner: I, + elements: impl IntoIterator, E>>, + ) -> Result { + 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>, + ) -> 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, + intern_quantified_where_clauses => InternedQuantifiedWhereClauses +); + +interned_slice!( + ProgramClauses, + program_clauses_data => ProgramClause, + intern_program_clauses => InternedProgramClauses +); + +interned_slice!( + VariableKinds, + variable_kinds_data => VariableKind, + intern_generic_arg_kinds => InternedVariableKinds +); + +interned_slice!( + CanonicalVarKinds, + canonical_var_kinds_data => CanonicalVarKind, + intern_canonical_var_kinds => InternedCanonicalVarKinds +); + +interned_slice!(Goals, goals_data => Goal, intern_goals => InternedGoals); + +interned_slice!( + Constraints, + constraints_data => InEnvironment>, + intern_constraints => InternedConstraints +); + +interned_slice!( + Substitution, + substitution_data => GenericArg, + intern_substitution => InternedSubstitution +); + +interned_slice_common!( + Variances, + variances_data => Variance, + intern_variance => InternedVariances +); + +impl Variances { + /// Tries to create a list of canonical variable kinds using an iterator. + pub fn from_fallible( + interner: I, + variances: impl IntoIterator>, + ) -> Result { + 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) -> Self { + Self::from_fallible( + interner, + variances + .into_iter() + .map(|p| -> Result { 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, Fold, Visit, HasInterner)] +pub struct ConstrainedSubst { + /// The substitution that is being constrained. + /// + /// NB: The `is_trivial` routine relies on the fact that `subst` is folded first. + pub subst: Substitution, + + /// Region constraints that constrain the substitution. + pub constraints: Constraints, +} + +/// The resulting substitution after solving a goal. +#[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit, HasInterner)] +pub struct AnswerSubst { + /// The substitution result. + /// + /// NB: The `is_trivial` routine relies on the fact that `subst` is folded first. + pub subst: Substitution, + + /// List of constraints that are part of the answer. + pub constraints: Constraints, + + /// Delayed subgoals, used when the solver answered with an (incomplete) `Answer` (instead of a `CompleteAnswer`). + pub delayed_subgoals: Vec>>, +} + +/// Logic to decide the Variance for a given subst +pub trait UnificationDatabase +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) -> Variances; + + /// Gets the variances for the substitution of a adt + fn adt_variance(&self, adt_id: AdtId) -> Variances; +} diff --git a/vendor/chalk-ir-0.80.0/src/visit.rs b/vendor/chalk-ir-0.80.0/src/visit.rs new file mode 100644 index 000000000..ace1fd5cf --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/visit.rs @@ -0,0 +1,424 @@ +//! 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 `Visit::visit_with` method, like so +/// +/// ```rust,ignore +/// let result = x.visit_with(&mut visitor, 0); +/// ``` +pub trait Visitor { + /// 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 Visitor` 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 Visitor; + + /// Top-level callback: invoked for each `Ty` 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, outer_binder: DebruijnIndex) -> ControlFlow { + ty.super_visit_with(self.as_dyn(), outer_binder) + } + + /// Top-level callback: invoked for each `Lifetime` 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, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + lifetime.super_visit_with(self.as_dyn(), outer_binder) + } + + /// Top-level callback: invoked for each `Const` 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, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + 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, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + 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, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + goal.super_visit_with(self.as_dyn(), outer_binder) + } + + /// Invoked for each domain goal. + fn visit_domain_goal( + &mut self, + domain_goal: &DomainGoal, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + 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 { + 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 { + 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, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + 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 { + 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 `Visitor::Result`. +pub trait Visit: 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` in the IR or other similar + /// constructs. + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow; +} + +/// For types where "visit" invokes a callback on the `visitor`, the +/// `SuperVisit` trait captures the recursive behavior that visits all +/// the contents of the type. +pub trait SuperVisit: Visit { + /// Recursively visits the type contents. + fn super_visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow; +} + +/// "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 Visit for Ty { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + visitor.visit_ty(self, outer_binder) + } +} + +/// "Super visit" for a type invokes the more detailed callbacks on the type +impl SuperVisit for Ty +where + I: Interner, +{ + fn super_visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + 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 Visit for Lifetime { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + visitor.visit_lifetime(self, outer_binder) + } +} + +impl SuperVisit for Lifetime { + fn super_visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + 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::Empty(_) | LifetimeData::Erased => { + ControlFlow::Continue(()) + } + LifetimeData::Phantom(void, ..) => match *void {}, + } + } +} + +impl Visit for Const { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + visitor.visit_const(self, outer_binder) + } +} + +impl SuperVisit for Const { + fn super_visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + 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 Visit for Goal { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + visitor.visit_goal(self, outer_binder) + } +} + +impl SuperVisit for Goal { + fn super_visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + let interner = visitor.interner(); + self.data(interner).visit_with(visitor, outer_binder) + } +} + +impl Visit for ProgramClause { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + visitor.visit_program_clause(self, outer_binder) + } +} + +impl Visit for WhereClause { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + visitor.visit_where_clause(self, outer_binder) + } +} + +impl Visit for DomainGoal { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + visitor.visit_domain_goal(self, outer_binder) + } +} diff --git a/vendor/chalk-ir-0.80.0/src/visit/binder_impls.rs b/vendor/chalk-ir-0.80.0/src/visit/binder_impls.rs new file mode 100644 index 000000000..074450a53 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/visit/binder_impls.rs @@ -0,0 +1,45 @@ +//! This module contains impls of `Visit` for those types that +//! introduce binders. +//! +//! The more interesting impls of `Visit` remain in the `visit` module. + +use crate::interner::HasInterner; +use crate::{Binders, Canonical, ControlFlow, DebruijnIndex, FnPointer, Interner, Visit, Visitor}; + +impl Visit for FnPointer { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + self.substitution + .visit_with(visitor, outer_binder.shifted_in()) + } +} + +impl Visit for Binders +where + T: HasInterner + Visit, +{ + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + self.value.visit_with(visitor, outer_binder.shifted_in()) + } +} + +impl Visit for Canonical +where + I: Interner, + T: HasInterner + Visit, +{ + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + self.value.visit_with(visitor, outer_binder.shifted_in()) + } +} diff --git a/vendor/chalk-ir-0.80.0/src/visit/boring_impls.rs b/vendor/chalk-ir-0.80.0/src/visit/boring_impls.rs new file mode 100644 index 000000000..d4e52d15b --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/visit/boring_impls.rs @@ -0,0 +1,261 @@ +//! This module contains "rote and uninteresting" impls of `Visit` for +//! various types. In general, we prefer to derive `Visit`, but +//! sometimes that doesn't work for whatever reason. +//! +//! The more interesting impls of `Visit` 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, SuperVisit, TraitId, + UintTy, UniverseIndex, Visit, Visitor, +}; +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, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, +) -> ControlFlow +where + T: Visit, + I: 'i + Interner, +{ + for e in it { + try_break!(e.visit_with(visitor, outer_binder)); + } + ControlFlow::Continue(()) +} + +impl, I: Interner> Visit for &T { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + T::visit_with(self, visitor, outer_binder) + } +} + +impl, I: Interner> Visit for Vec { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + visit_iter(self.iter(), visitor, outer_binder) + } +} + +impl, I: Interner> Visit for &[T] { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + visit_iter(self.iter(), visitor, outer_binder) + } +} + +impl, I: Interner> Visit for Box { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + T::visit_with(self, visitor, outer_binder) + } +} + +impl, I: Interner> Visit for Arc { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + T::visit_with(self, visitor, outer_binder) + } +} + +macro_rules! tuple_visit { + ($($n:ident),*) => { + impl<$($n: Visit,)* I: Interner> Visit for ($($n,)*) { + fn visit_with(&self, visitor: &mut dyn Visitor, outer_binder: DebruijnIndex) -> ControlFlow { + #[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, I: Interner> Visit for Option { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + match self { + Some(e) => e.visit_with(visitor, outer_binder), + None => ControlFlow::Continue(()), + } + } +} + +impl Visit for GenericArg { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + let interner = visitor.interner(); + self.data(interner).visit_with(visitor, outer_binder) + } +} + +impl Visit for Substitution { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + let interner = visitor.interner(); + visit_iter(self.iter(interner), visitor, outer_binder) + } +} + +impl Visit for Goals { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + let interner = visitor.interner(); + visit_iter(self.iter(interner), visitor, outer_binder) + } +} + +#[doc(hidden)] +#[macro_export] +macro_rules! const_visit { + ($t:ty) => { + impl $crate::visit::Visit for $t { + fn visit_with( + &self, + _visitor: &mut dyn ($crate::visit::Visitor), + _outer_binder: DebruijnIndex, + ) -> ControlFlow { + 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 $crate::visit::Visit for $t { + fn visit_with( + &self, + _visitor: &mut dyn ($crate::visit::Visitor), + _outer_binder: DebruijnIndex, + ) -> ControlFlow { + 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 SuperVisit for ProgramClause { + fn super_visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + let interner = visitor.interner(); + + self.data(interner).0.visit_with(visitor, outer_binder) + } +} + +impl Visit for ProgramClauses { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + let interner = visitor.interner(); + + visit_iter(self.iter(interner), visitor, outer_binder) + } +} + +impl Visit for Constraints { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + let interner = visitor.interner(); + + visit_iter(self.iter(interner), visitor, outer_binder) + } +} + +impl Visit for QuantifiedWhereClauses { + fn visit_with( + &self, + visitor: &mut dyn Visitor, + outer_binder: DebruijnIndex, + ) -> ControlFlow { + let interner = visitor.interner(); + + visit_iter(self.iter(interner), visitor, outer_binder) + } +} + +impl Visit for PhantomData { + fn visit_with( + &self, + _visitor: &mut dyn Visitor, + _outer_binder: DebruijnIndex, + ) -> ControlFlow { + ControlFlow::Continue(()) + } +} diff --git a/vendor/chalk-ir-0.80.0/src/visit/visitors.rs b/vendor/chalk-ir-0.80.0/src/visit/visitors.rs new file mode 100644 index 000000000..486b51d86 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/visit/visitors.rs @@ -0,0 +1,41 @@ +//! Visitor helpers + +use crate::{BoundVar, ControlFlow, DebruijnIndex, Interner, Visit, Visitor}; + +/// Visitor extensions. +pub trait VisitExt: Visit { + /// 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 VisitExt for T where T: Visit {} + +struct FindFreeVarsVisitor { + interner: I, +} + +impl Visitor for FindFreeVarsVisitor { + type BreakTy = (); + + fn as_dyn(&mut self) -> &mut dyn Visitor { + 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-0.80.0/src/zip.rs b/vendor/chalk-ir-0.80.0/src/zip.rs new file mode 100644 index 000000000..94cc18828 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/zip.rs @@ -0,0 +1,543 @@ +//! Traits for "zipping" types, walking through two structures and checking that they match. + +use crate::fold::Fold; +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` zipped with `X: Eq`, 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` zipped with `X: +/// Ord`, 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 { + /// Indicates that the two types `a` and `b` were found in matching spots. + fn zip_tys(&mut self, variance: Variance, a: &Ty, b: &Ty) -> Fallible<()>; + + /// Indicates that the two lifetimes `a` and `b` were found in matching spots. + fn zip_lifetimes( + &mut self, + variance: Variance, + a: &Lifetime, + b: &Lifetime, + ) -> Fallible<()>; + + /// Indicates that the two consts `a` and `b` were found in matching spots. + fn zip_consts(&mut self, variance: Variance, a: &Const, b: &Const) -> Fallible<()>; + + /// Zips two values appearing beneath binders. + fn zip_binders( + &mut self, + variance: Variance, + a: &Binders, + b: &Binders, + ) -> Fallible<()> + where + T: Clone + HasInterner + Zip + Fold; + + /// Zips two substs + fn zip_substs( + &mut self, + ambient: Variance, + variances: Option>, + a: &[GenericArg], + b: &[GenericArg], + ) -> 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; +} + +impl<'f, Z, I> Zipper for &'f mut Z +where + I: Interner, + Z: Zipper, +{ + fn zip_tys(&mut self, variance: Variance, a: &Ty, b: &Ty) -> Fallible<()> { + (**self).zip_tys(variance, a, b) + } + + fn zip_lifetimes( + &mut self, + variance: Variance, + a: &Lifetime, + b: &Lifetime, + ) -> Fallible<()> { + (**self).zip_lifetimes(variance, a, b) + } + + fn zip_consts(&mut self, variance: Variance, a: &Const, b: &Const) -> Fallible<()> { + (**self).zip_consts(variance, a, b) + } + + fn zip_binders(&mut self, variance: Variance, a: &Binders, b: &Binders) -> Fallible<()> + where + T: Clone + HasInterner + Zip + Fold, + { + (**self).zip_binders(variance, a, b) + } + + fn interner(&self) -> I { + Z::interner(*self) + } + + fn unification_database(&self) -> &dyn UnificationDatabase { + (**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: Debug +where + I: Interner, +{ + /// Uses the zipper to walk through two values, ensuring that they match. + fn zip_with>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()>; +} + +impl<'a, T: ?Sized + Zip, I: Interner> Zip for &'a T { + fn zip_with>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + >::zip_with(zipper, variance, a, b) + } +} + +impl Zip for () { + fn zip_with>(_: &mut Z, _: Variance, _: &Self, _: &Self) -> Fallible<()> { + Ok(()) + } +} + +impl, I: Interner> Zip for Vec { + fn zip_with>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + <[T] as Zip>::zip_with(zipper, variance, a, b) + } +} + +impl, I: Interner> Zip for [T] { + fn zip_with>( + 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, I: Interner> Zip for Arc { + fn zip_with>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + >::zip_with(zipper, variance, a, b) + } +} + +impl, I: Interner> Zip for Box { + fn zip_with>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + >::zip_with(zipper, variance, a, b) + } +} + +impl, U: Zip, I: Interner> Zip for (T, U) { + fn zip_with>( + 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 Zip for Ty { + fn zip_with>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + zipper.zip_tys(variance, a, b) + } +} + +impl Zip for Lifetime { + fn zip_with>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + zipper.zip_lifetimes(variance, a, b) + } +} + +impl Zip for Const { + fn zip_with>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + zipper.zip_consts(variance, a, b) + } +} +impl Zip for Binders +where + T: Clone + HasInterner + Zip + Fold, +{ + fn zip_with>( + 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>( + _zipper: &mut Z, + _variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + if a != b { + return Err(NoSolution); + } + Ok(()) + } + } + }; +} + +eq_zip!(I => AdtId); +eq_zip!(I => TraitId); +eq_zip!(I => AssocTypeId); +eq_zip!(I => OpaqueTyId); +eq_zip!(I => GeneratorId); +eq_zip!(I => ForeignDefId); +eq_zip!(I => FnDefId); +eq_zip!(I => ClosureId); +eq_zip!(I => QuantifierKind); +eq_zip!(I => PhantomData); +eq_zip!(I => PlaceholderIndex); +eq_zip!(I => ClausePriority); +eq_zip!(I => Mutability); +eq_zip!(I => Scalar); + +impl + Zip, I: Interner> Zip for InEnvironment { + fn zip_with>( + 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 Zip for Environment { + fn zip_with>( + 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 Zip for Goals { + fn zip_with>( + 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 Zip for ProgramClauses { + fn zip_with>( + 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 Zip for Constraints { + fn zip_with>( + 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 Zip for QuantifiedWhereClauses { + fn zip_with>( + 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 Zip for Goal { + fn zip_with>( + 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 Zip for VariableKind { + fn zip_with>( + 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 Zip for GenericArg { + fn zip_with>( + 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 Zip for ProgramClause { + fn zip_with>( + 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 Zip for TraitRef { + fn zip_with>( + 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 Zip for ProjectionTy { + fn zip_with>( + 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 Zip for OpaqueTy { + fn zip_with>( + 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 Zip for DynTy { + fn zip_with>( + 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 Zip for FnSubst { + fn zip_with>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + // Parameters + for (a, b) in a.0.as_slice(interner)[..a.0.len(interner) - 1] + .iter() + .zip(b.0.as_slice(interner)[..b.0.len(interner) - 1].iter()) + { + Zip::zip_with(zipper, variance.xform(Variance::Contravariant), a, b)?; + } + // Return type + Zip::zip_with( + zipper, + variance, + a.0.iter(interner).last().unwrap(), + b.0.iter(interner).last().unwrap(), + )?; + Ok(()) + } +} -- cgit v1.2.3