Merging upstream version 1.68.2+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

15 files changed, 2704 insertions, 0 deletions

diff --git a/vendor/chalk-solve-0.87.0/src/clauses/builder.rs b/vendor/chalk-solve-0.87.0/src/clauses/builder.rs
new file mode 100644
index 000000000..bbe7c2fd2
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/builder.rs
@@ -0,0 +1,207 @@
+use std::marker::PhantomData;
+
+use crate::cast::{Cast, CastTo};
+use crate::RustIrDatabase;
+use chalk_ir::fold::{Shift, TypeFoldable};
+use chalk_ir::interner::{HasInterner, Interner};
+use chalk_ir::*;
+use tracing::{debug, instrument};
+
+/// The "clause builder" is a useful tool for building up sets of
+/// program clauses. It takes ownership of the output vector while it
+/// lasts, and offers methods like `push_clause` and so forth to
+/// append to it.
+pub struct ClauseBuilder<'me, I: Interner> {
+    pub db: &'me dyn RustIrDatabase<I>,
+    clauses: &'me mut Vec<ProgramClause<I>>,
+    binders: Vec<VariableKind<I>>,
+    parameters: Vec<GenericArg<I>>,
+}
+
+impl<'me, I: Interner> ClauseBuilder<'me, I> {
+    pub fn new(db: &'me dyn RustIrDatabase<I>, clauses: &'me mut Vec<ProgramClause<I>>) -> Self {
+        Self {
+            db,
+            clauses,
+            binders: vec![],
+            parameters: vec![],
+        }
+    }
+
+    /// Pushes a "fact" `forall<..> { consequence }` into the set of
+    /// program clauses, meaning something that we can assume to be
+    /// true unconditionally. The `forall<..>` binders will be
+    /// whichever binders have been pushed (see `push_binders`).
+    pub fn push_fact(&mut self, consequence: impl CastTo<DomainGoal<I>>) {
+        self.push_clause(consequence, None::<Goal<_>>);
+    }
+
+    /// Pushes a "fact" `forall<..> { consequence }` into the set of
+    /// program clauses, meaning something that we can assume to be
+    /// true unconditionally. The `forall<..>` binders will be
+    /// whichever binders have been pushed (see `push_binders`).
+    pub fn push_fact_with_priority(
+        &mut self,
+        consequence: impl CastTo<DomainGoal<I>>,
+        constraints: impl IntoIterator<Item = InEnvironment<Constraint<I>>>,
+        priority: ClausePriority,
+    ) {
+        self.push_clause_with_priority(consequence, None::<Goal<_>>, constraints, priority);
+    }
+
+    /// Pushes a clause `forall<..> { consequence :- conditions }`
+    /// into the set of program clauses, meaning that `consequence`
+    /// can be proven if `conditions` are all true.  The `forall<..>`
+    /// binders will be whichever binders have been pushed (see `push_binders`).
+    pub fn push_clause(
+        &mut self,
+        consequence: impl CastTo<DomainGoal<I>>,
+        conditions: impl IntoIterator<Item = impl CastTo<Goal<I>>>,
+    ) {
+        self.push_clause_with_priority(consequence, conditions, None, ClausePriority::High)
+    }
+
+    pub fn push_fact_with_constraints(
+        &mut self,
+        consequence: impl CastTo<DomainGoal<I>>,
+        constraints: impl IntoIterator<Item = InEnvironment<Constraint<I>>>,
+    ) {
+        self.push_fact_with_priority(consequence, constraints, ClausePriority::High)
+    }
+
+    /// Pushes a clause `forall<..> { consequence :- conditions ; constraints }`
+    /// into the set of program clauses, meaning that `consequence`
+    /// can be proven if `conditions` are all true and `constraints`
+    /// are proven to hold.  The `forall<..>` binders will be whichever binders
+    /// have been pushed (see `push_binders`).
+    pub fn push_clause_with_priority(
+        &mut self,
+        consequence: impl CastTo<DomainGoal<I>>,
+        conditions: impl IntoIterator<Item = impl CastTo<Goal<I>>>,
+        constraints: impl IntoIterator<Item = InEnvironment<Constraint<I>>>,
+        priority: ClausePriority,
+    ) {
+        let interner = self.db.interner();
+        let clause = ProgramClauseImplication {
+            consequence: consequence.cast(interner),
+            conditions: Goals::from_iter(interner, conditions),
+            constraints: Constraints::from_iter(interner, constraints),
+            priority,
+        };
+
+        let clause = if self.binders.is_empty() {
+            // Compensate for the added empty binder
+            clause.shifted_in(interner)
+        } else {
+            clause
+        };
+
+        self.clauses.push(
+            ProgramClauseData(Binders::new(
+                VariableKinds::from_iter(interner, self.binders.clone()),
+                clause,
+            ))
+            .intern(interner),
+        );
+
+        debug!("pushed clause {:?}", self.clauses.last());
+    }
+
+    /// Accesses the placeholders for the current list of parameters in scope.
+    pub fn placeholders_in_scope(&self) -> &[GenericArg<I>] {
+        &self.parameters
+    }
+
+    /// Accesses the placeholders for the current list of parameters in scope,
+    /// in the form of a `Substitution`.
+    pub fn substitution_in_scope(&self) -> Substitution<I> {
+        Substitution::from_iter(
+            self.db.interner(),
+            self.placeholders_in_scope().iter().cloned(),
+        )
+    }
+
+    /// Executes `op` with the `binders` in-scope; `op` is invoked
+    /// with the bound value `v` as a parameter. After `op` finishes,
+    /// the binders are popped from scope.
+    ///
+    /// The new binders are always pushed onto the end of the internal
+    /// list of binders; this means that any extant values where were
+    /// created referencing the *old* list of binders are still valid.
+    #[instrument(level = "debug", skip(self, op))]
+    pub fn push_binders<R, V>(
+        &mut self,
+        binders: Binders<V>,
+        op: impl FnOnce(&mut Self, V) -> R,
+    ) -> R
+    where
+        V: TypeFoldable<I> + HasInterner<Interner = I>,
+        V: std::fmt::Debug,
+    {
+        let old_len = self.binders.len();
+        let interner = self.interner();
+        self.binders.extend(binders.binders.iter(interner).cloned());
+        self.parameters.extend(
+            binders
+                .binders
+                .iter(interner)
+                .zip(old_len..)
+                .map(|(pk, i)| (i, pk).to_generic_arg(interner)),
+        );
+        let value = binders.substitute(self.interner(), &self.parameters[old_len..]);
+        debug!(?value);
+        let res = op(self, value);
+
+        self.binders.truncate(old_len);
+        self.parameters.truncate(old_len);
+        res
+    }
+
+    /// Push a single binder, for a type, at the end of the binder
+    /// list.  The indices of previously bound variables are
+    /// unaffected and hence the context remains usable. Invokes `op`,
+    /// passing a type representing this new type variable in as an
+    /// argument.
+    pub fn push_bound_ty(&mut self, op: impl FnOnce(&mut Self, Ty<I>)) {
+        let interner = self.interner();
+        let binders = Binders::new(
+            VariableKinds::from1(interner, VariableKind::Ty(TyVariableKind::General)),
+            PhantomData::<I>,
+        );
+        self.push_binders(binders, |this, PhantomData| {
+            let ty = this
+                .placeholders_in_scope()
+                .last()
+                .unwrap()
+                .assert_ty_ref(interner)
+                .clone();
+            op(this, ty)
+        });
+    }
+
+    /// Push a single binder, for a lifetime, at the end of the binder
+    /// list.  The indices of previously bound variables are
+    /// unaffected and hence the context remains usable. Invokes `op`,
+    /// passing a lifetime representing this new lifetime variable in as an
+    /// argument.
+    pub fn push_bound_lifetime(&mut self, op: impl FnOnce(&mut Self, Lifetime<I>)) {
+        let interner = self.interner();
+        let binders = Binders::new(
+            VariableKinds::from1(interner, VariableKind::Lifetime),
+            PhantomData::<I>,
+        );
+        self.push_binders(binders, |this, PhantomData| {
+            let lifetime = this
+                .placeholders_in_scope()
+                .last()
+                .unwrap()
+                .assert_lifetime_ref(interner)
+                .clone();
+            op(this, lifetime)
+        });
+    }
+
+    pub fn interner(&self) -> I {
+        self.db.interner()
+    }
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits.rs b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits.rs
new file mode 100644
index 000000000..b5a1c7d57
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits.rs
@@ -0,0 +1,119 @@
+use super::{builder::ClauseBuilder, generalize};
+use crate::{CanonicalVarKinds, Interner, RustIrDatabase, TraitRef, WellKnownTrait};
+use chalk_ir::{Floundered, Substitution, Ty};
+
+mod clone;
+mod copy;
+mod discriminant_kind;
+mod fn_family;
+mod generator;
+mod sized;
+mod tuple;
+mod unsize;
+
+/// For well known traits we have special hard-coded impls, either as an
+/// optimization or to enforce special rules for correctness.
+pub fn add_builtin_program_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    well_known: WellKnownTrait,
+    trait_ref: TraitRef<I>,
+    binders: &CanonicalVarKinds<I>,
+) -> Result<(), Floundered> {
+    // If `trait_ref` contains bound vars, we want to universally quantify them.
+    // `Generalize` collects them for us.
+    let generalized = generalize::Generalize::apply(db.interner(), trait_ref);
+
+    builder.push_binders(generalized, |builder, trait_ref| {
+        let self_ty = trait_ref.self_type_parameter(db.interner());
+        let ty = self_ty.kind(db.interner()).clone();
+
+        match well_known {
+            // Built-in traits are non-enumerable.
+            _ if self_ty.is_general_var(db.interner(), binders) => return Err(Floundered),
+            WellKnownTrait::Sized => {
+                sized::add_sized_program_clauses(db, builder, trait_ref, ty, binders)?;
+            }
+            WellKnownTrait::Copy => {
+                copy::add_copy_program_clauses(db, builder, trait_ref, ty, binders)?;
+            }
+            WellKnownTrait::Clone => {
+                clone::add_clone_program_clauses(db, builder, trait_ref, ty, binders)?;
+            }
+            WellKnownTrait::FnOnce | WellKnownTrait::FnMut | WellKnownTrait::Fn => {
+                fn_family::add_fn_trait_program_clauses(db, builder, well_known, self_ty);
+            }
+            WellKnownTrait::Unsize => {
+                unsize::add_unsize_program_clauses(db, builder, trait_ref, ty)
+            }
+            // DiscriminantKind is automatically implemented for all types
+            WellKnownTrait::DiscriminantKind => builder.push_fact(trait_ref),
+            WellKnownTrait::Generator => {
+                generator::add_generator_program_clauses(db, builder, self_ty)?;
+            }
+            WellKnownTrait::Tuple => {
+                tuple::add_tuple_program_clauses(db, builder, self_ty)?;
+            }
+            // There are no builtin impls provided for the following traits:
+            WellKnownTrait::Unpin
+            | WellKnownTrait::Drop
+            | WellKnownTrait::CoerceUnsized
+            | WellKnownTrait::DispatchFromDyn => (),
+        }
+        Ok(())
+    })
+}
+
+/// Like `add_builtin_program_clauses`, but for `DomainGoal::Normalize` involving
+/// a projection (e.g. `<fn(u8) as FnOnce<(u8,)>>::Output`)
+pub fn add_builtin_assoc_program_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    well_known: WellKnownTrait,
+    self_ty: Ty<I>,
+) -> Result<(), Floundered> {
+    match well_known {
+        WellKnownTrait::FnOnce => {
+            // If `self_ty` contains bound vars, we want to universally quantify them.
+            // `Generalize` collects them for us.
+            let generalized = generalize::Generalize::apply(db.interner(), self_ty);
+
+            builder.push_binders(generalized, |builder, self_ty| {
+                fn_family::add_fn_trait_program_clauses(db, builder, well_known, self_ty);
+                Ok(())
+            })
+        }
+        WellKnownTrait::DiscriminantKind => {
+            discriminant_kind::add_discriminant_clauses(db, builder, self_ty)
+        }
+        WellKnownTrait::Generator => {
+            let generalized = generalize::Generalize::apply(db.interner(), self_ty);
+
+            builder.push_binders(generalized, |builder, self_ty| {
+                generator::add_generator_program_clauses(db, builder, self_ty)
+            })
+        }
+        _ => Ok(()),
+    }
+}
+
+/// Given a trait ref `T0: Trait` and a list of types `U0..Un`, pushes a clause of the form
+/// `Implemented(T0: Trait) :- Implemented(U0: Trait) .. Implemented(Un: Trait)`
+pub fn needs_impl_for_tys<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    trait_ref: TraitRef<I>,
+    tys: impl Iterator<Item = Ty<I>>,
+) {
+    let trait_id = trait_ref.trait_id;
+
+    // The trait must take one parameter (a type)
+    debug_assert_eq!(db.trait_datum(trait_id).binders.len(db.interner()), 1,);
+    builder.push_clause(
+        trait_ref,
+        tys.map(|ty| TraitRef {
+            trait_id,
+            substitution: Substitution::from1(db.interner(), ty),
+        }),
+    );
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/clone.rs b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/clone.rs
new file mode 100644
index 000000000..6d6b3a362
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/clone.rs
@@ -0,0 +1,16 @@
+use crate::clauses::ClauseBuilder;
+use crate::{Interner, RustIrDatabase, TraitRef};
+use chalk_ir::{CanonicalVarKinds, Floundered, TyKind};
+
+use super::copy::add_copy_program_clauses;
+
+pub fn add_clone_program_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    trait_ref: TraitRef<I>,
+    ty: TyKind<I>,
+    binders: &CanonicalVarKinds<I>,
+) -> Result<(), Floundered> {
+    // Implement Clone for types that automaticly implement Copy
+    add_copy_program_clauses(db, builder, trait_ref, ty, binders)
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/copy.rs b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/copy.rs
new file mode 100644
index 000000000..c0174b21e
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/copy.rs
@@ -0,0 +1,99 @@
+use crate::clauses::builtin_traits::needs_impl_for_tys;
+use crate::clauses::ClauseBuilder;
+use crate::{Interner, RustIrDatabase, TraitRef};
+use chalk_ir::{CanonicalVarKinds, Floundered, Substitution, TyKind, TyVariableKind, VariableKind};
+use std::iter;
+use tracing::instrument;
+
+fn push_tuple_copy_conditions<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    trait_ref: TraitRef<I>,
+    arity: usize,
+    substitution: &Substitution<I>,
+) {
+    // Empty tuples are always Copy
+    if arity == 0 {
+        builder.push_fact(trait_ref);
+        return;
+    }
+
+    let interner = db.interner();
+
+    needs_impl_for_tys(
+        db,
+        builder,
+        trait_ref,
+        substitution
+            .iter(interner)
+            .map(|param| param.assert_ty_ref(interner).clone()),
+    );
+}
+
+#[instrument(skip(db, builder))]
+pub fn add_copy_program_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    trait_ref: TraitRef<I>,
+    ty: TyKind<I>,
+    binders: &CanonicalVarKinds<I>,
+) -> Result<(), Floundered> {
+    match ty {
+        TyKind::Tuple(arity, ref substitution) => {
+            push_tuple_copy_conditions(db, builder, trait_ref, arity, substitution)
+        }
+        TyKind::Array(ty, _) => {
+            needs_impl_for_tys(db, builder, trait_ref, iter::once(ty));
+        }
+        TyKind::FnDef(_, _) => {
+            builder.push_fact(trait_ref);
+        }
+        TyKind::Closure(closure_id, ref substitution) => {
+            let closure_fn_substitution = db.closure_fn_substitution(closure_id, substitution);
+            let upvars = db.closure_upvars(closure_id, substitution);
+            let upvars = upvars.substitute(db.interner(), &closure_fn_substitution);
+            needs_impl_for_tys(db, builder, trait_ref, Some(upvars).into_iter());
+        }
+
+        // these impls are in libcore
+        TyKind::Ref(_, _, _)
+        | TyKind::Raw(_, _)
+        | TyKind::Scalar(_)
+        | TyKind::Never
+        | TyKind::Str => {}
+
+        TyKind::Adt(_, _)
+        | TyKind::AssociatedType(_, _)
+        | TyKind::Slice(_)
+        | TyKind::OpaqueType(_, _)
+        | TyKind::Foreign(_)
+        | TyKind::Generator(_, _)
+        | TyKind::GeneratorWitness(_, _)
+        | TyKind::Error => {}
+
+        TyKind::Function(_) => builder.push_fact(trait_ref),
+
+        TyKind::InferenceVar(_, TyVariableKind::Float)
+        | TyKind::InferenceVar(_, TyVariableKind::Integer) => builder.push_fact(trait_ref),
+
+        TyKind::BoundVar(bound_var) => {
+            let var_kind = &binders.at(db.interner(), bound_var.index).kind;
+            match var_kind {
+                VariableKind::Ty(TyVariableKind::Integer)
+                | VariableKind::Ty(TyVariableKind::Float) => builder.push_fact(trait_ref),
+
+                // Don't know enough
+                VariableKind::Ty(TyVariableKind::General) => return Err(Floundered),
+
+                VariableKind::Const(_) | VariableKind::Lifetime => {}
+            }
+        }
+
+        // Don't know enough
+        TyKind::InferenceVar(_, TyVariableKind::General) => return Err(Floundered),
+
+        // These should be handled elsewhere
+        TyKind::Alias(_) | TyKind::Dyn(_) | TyKind::Placeholder(_) => {}
+    };
+    Ok(())
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/discriminant_kind.rs b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/discriminant_kind.rs
new file mode 100644
index 000000000..27d49df75
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/discriminant_kind.rs
@@ -0,0 +1,73 @@
+use crate::clauses::ClauseBuilder;
+use crate::{Interner, RustIrDatabase, TraitRef, WellKnownTrait};
+use chalk_ir::{
+    AliasTy, Floundered, Normalize, ProjectionTy, Substitution, Ty, TyKind, TyVariableKind,
+};
+
+pub fn add_discriminant_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    self_ty: Ty<I>,
+) -> Result<(), Floundered> {
+    let interner = db.interner();
+
+    let can_determine_discriminant = match self_ty.data(interner).kind {
+        TyKind::Adt(..)
+        | TyKind::Array(..)
+        | TyKind::Tuple(..)
+        | TyKind::Slice(..)
+        | TyKind::Raw(..)
+        | TyKind::Ref(..)
+        | TyKind::Scalar(_)
+        | TyKind::Str
+        | TyKind::Never
+        | TyKind::FnDef(..)
+        | TyKind::Generator(..)
+        | TyKind::Closure(..)
+        | TyKind::GeneratorWitness(..)
+        | TyKind::Foreign(_)
+        | TyKind::Dyn(_)
+        | TyKind::Function(..)
+        | TyKind::InferenceVar(_, TyVariableKind::Integer)
+        | TyKind::InferenceVar(_, TyVariableKind::Float) => true,
+        TyKind::OpaqueType(..)
+        | TyKind::Alias(_)
+        | TyKind::BoundVar(_)
+        | TyKind::Placeholder(_)
+        | TyKind::AssociatedType(..)
+        | TyKind::Error
+        | TyKind::InferenceVar(..) => false,
+    };
+
+    if !can_determine_discriminant {
+        return Err(Floundered);
+    }
+
+    let disc_ty = db.discriminant_type(self_ty.clone());
+
+    let trait_id = db
+        .well_known_trait_id(WellKnownTrait::DiscriminantKind)
+        .unwrap();
+    let trait_datum = db.trait_datum(trait_id);
+
+    let associated_ty_id = trait_datum.associated_ty_ids[0];
+    let substitution = Substitution::from1(interner, self_ty);
+
+    let trait_ref = TraitRef {
+        trait_id,
+        substitution: substitution.clone(),
+    };
+
+    let normalize = Normalize {
+        alias: AliasTy::Projection(ProjectionTy {
+            associated_ty_id,
+            substitution,
+        }),
+        ty: disc_ty,
+    };
+
+    builder.push_fact(trait_ref);
+    builder.push_fact(normalize);
+
+    Ok(())
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/fn_family.rs b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/fn_family.rs
new file mode 100644
index 000000000..f2358bc73
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/fn_family.rs
@@ -0,0 +1,155 @@
+use crate::clauses::ClauseBuilder;
+use crate::rust_ir::{ClosureKind, FnDefInputsAndOutputDatum, WellKnownTrait};
+use crate::{Interner, RustIrDatabase, TraitRef};
+use chalk_ir::cast::Cast;
+use chalk_ir::{
+    AliasTy, Binders, Normalize, ProjectionTy, Safety, Substitution, TraitId, Ty, TyKind,
+};
+
+fn push_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    well_known: WellKnownTrait,
+    trait_id: TraitId<I>,
+    self_ty: Ty<I>,
+    arg_sub: Substitution<I>,
+    return_type: Ty<I>,
+) {
+    let interner = db.interner();
+    let tupled = TyKind::Tuple(arg_sub.len(interner), arg_sub).intern(interner);
+    let substitution =
+        Substitution::from_iter(interner, &[self_ty.cast(interner), tupled.cast(interner)]);
+    builder.push_fact(TraitRef {
+        trait_id,
+        substitution: substitution.clone(),
+    });
+
+    // The `Output` type is defined on the `FnOnce`
+    if let WellKnownTrait::FnOnce = well_known {
+        let trait_datum = db.trait_datum(trait_id);
+        assert_eq!(
+            trait_datum.associated_ty_ids.len(),
+            1,
+            "FnOnce trait should have exactly one associated type, found {:?}",
+            trait_datum.associated_ty_ids
+        );
+        // Constructs the alias. For `Fn`, for example, this would look like
+        // `Normalize(<fn(A) -> B as FnOnce<(A,)>>::Output -> B)`
+        let output_id = trait_datum.associated_ty_ids[0];
+        let alias = AliasTy::Projection(ProjectionTy {
+            associated_ty_id: output_id,
+            substitution,
+        });
+        builder.push_fact(Normalize {
+            alias,
+            ty: return_type,
+        });
+    }
+}
+
+fn push_clauses_for_apply<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    well_known: WellKnownTrait,
+    trait_id: TraitId<I>,
+    self_ty: Ty<I>,
+    inputs_and_output: Binders<FnDefInputsAndOutputDatum<I>>,
+) {
+    let interner = db.interner();
+    builder.push_binders(inputs_and_output, |builder, inputs_and_output| {
+        let arg_sub = inputs_and_output
+            .argument_types
+            .iter()
+            .cloned()
+            .map(|ty| ty.cast(interner));
+        let arg_sub = Substitution::from_iter(interner, arg_sub);
+        let output_ty = inputs_and_output.return_type;
+
+        push_clauses(
+            db, builder, well_known, trait_id, self_ty, arg_sub, output_ty,
+        );
+    });
+}
+
+/// Handles clauses for FnOnce/FnMut/Fn.
+/// If `self_ty` is a function, we push a clause of the form
+/// `fn(A1, A2, ..., AN) -> O: FnTrait<(A1, A2, ..., AN)>`, where `FnTrait`
+/// is the trait corresponding to `trait_id` (FnOnce/FnMut/Fn)
+///
+/// If `trait_id` is `FnOnce`, we also push a clause for the output type of the form:
+/// `Normalize(<fn(A) -> B as FnOnce<(A,)>>::Output -> B)`
+/// We do not add the usual `Implemented(fn(A) -> b as FnOnce<(A,)>` clause
+/// as a condition, since we already called `push_fact` with it
+pub fn add_fn_trait_program_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    well_known: WellKnownTrait,
+    self_ty: Ty<I>,
+) {
+    let interner = db.interner();
+    let trait_id = db.well_known_trait_id(well_known).unwrap();
+
+    match self_ty.kind(interner) {
+        TyKind::FnDef(fn_def_id, substitution) => {
+            let fn_def_datum = builder.db.fn_def_datum(*fn_def_id);
+            if fn_def_datum.sig.safety == Safety::Safe && !fn_def_datum.sig.variadic {
+                let bound = fn_def_datum
+                    .binders
+                    .clone()
+                    .substitute(builder.interner(), &substitution);
+                push_clauses_for_apply(
+                    db,
+                    builder,
+                    well_known,
+                    trait_id,
+                    self_ty,
+                    bound.inputs_and_output,
+                );
+            }
+        }
+        TyKind::Closure(closure_id, substitution) => {
+            let closure_kind = db.closure_kind(*closure_id, substitution);
+            let trait_matches = matches!(
+                (well_known, closure_kind),
+                (WellKnownTrait::Fn, ClosureKind::Fn)
+                    | (WellKnownTrait::FnMut, ClosureKind::FnMut | ClosureKind::Fn)
+                    | (WellKnownTrait::FnOnce, _)
+            );
+            if !trait_matches {
+                return;
+            }
+            let closure_inputs_and_output = db.closure_inputs_and_output(*closure_id, substitution);
+            push_clauses_for_apply(
+                db,
+                builder,
+                well_known,
+                trait_id,
+                self_ty,
+                closure_inputs_and_output,
+            );
+        }
+        TyKind::Function(fn_val) if fn_val.sig.safety == Safety::Safe && !fn_val.sig.variadic => {
+            let bound_ref = fn_val.clone().into_binders(interner);
+            builder.push_binders(bound_ref, |builder, orig_sub| {
+                // The last parameter represents the function return type
+                let (arg_sub, fn_output_ty) = orig_sub
+                    .0
+                    .as_slice(interner)
+                    .split_at(orig_sub.0.len(interner) - 1);
+                let arg_sub = Substitution::from_iter(interner, arg_sub);
+                let output_ty = fn_output_ty[0].assert_ty_ref(interner).clone();
+
+                push_clauses(
+                    db,
+                    builder,
+                    well_known,
+                    trait_id,
+                    self_ty.clone(),
+                    arg_sub,
+                    output_ty,
+                );
+            });
+        }
+        _ => {}
+    }
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/generator.rs b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/generator.rs
new file mode 100644
index 000000000..67415bfd7
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/generator.rs
@@ -0,0 +1,76 @@
+use crate::clauses::ClauseBuilder;
+use crate::rust_ir::WellKnownTrait;
+use crate::{Interner, RustIrDatabase, TraitRef};
+use chalk_ir::cast::Cast;
+use chalk_ir::{AliasTy, Floundered, Normalize, ProjectionTy, Substitution, Ty, TyKind};
+
+/// Add implicit impls of the generator trait, i.e., add a clause that all generators implement
+/// `Generator` and clauses for `Generator`'s associated types.
+pub fn add_generator_program_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    self_ty: Ty<I>,
+) -> Result<(), Floundered> {
+    let interner = db.interner();
+
+    match self_ty.kind(interner) {
+        TyKind::Generator(id, substitution) => {
+            let generator_datum = db.generator_datum(*id);
+            let generator_io_datum = generator_datum
+                .input_output
+                .clone()
+                .substitute(interner, &substitution);
+
+            let trait_id = db.well_known_trait_id(WellKnownTrait::Generator).unwrap();
+            let trait_datum = db.trait_datum(trait_id);
+            assert_eq!(
+                trait_datum.associated_ty_ids.len(),
+                2,
+                "Generator trait should have exactly two associated types, found {:?}",
+                trait_datum.associated_ty_ids
+            );
+
+            let substitution = Substitution::from_iter(
+                interner,
+                &[
+                    self_ty.cast(interner),
+                    generator_io_datum.resume_type.cast(interner),
+                ],
+            );
+
+            // generator: Generator<resume_type>
+            builder.push_fact(TraitRef {
+                trait_id,
+                substitution: substitution.clone(),
+            });
+
+            // `Generator::Yield`
+            let yield_id = trait_datum.associated_ty_ids[0];
+            let yield_alias = AliasTy::Projection(ProjectionTy {
+                associated_ty_id: yield_id,
+                substitution: substitution.clone(),
+            });
+            builder.push_fact(Normalize {
+                alias: yield_alias,
+                ty: generator_io_datum.yield_type,
+            });
+
+            // `Generator::Return`
+            let return_id = trait_datum.associated_ty_ids[1];
+            let return_alias = AliasTy::Projection(ProjectionTy {
+                associated_ty_id: return_id,
+                substitution,
+            });
+            builder.push_fact(Normalize {
+                alias: return_alias,
+                ty: generator_io_datum.return_type,
+            });
+
+            Ok(())
+        }
+
+        // Generator trait is non-enumerable
+        TyKind::InferenceVar(..) | TyKind::BoundVar(_) | TyKind::Alias(..) => Err(Floundered),
+        _ => Ok(()),
+    }
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/sized.rs b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/sized.rs
new file mode 100644
index 000000000..3ed46d425
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/sized.rs
@@ -0,0 +1,124 @@
+use std::iter;
+
+use crate::clauses::builtin_traits::needs_impl_for_tys;
+use crate::clauses::ClauseBuilder;
+use crate::rust_ir::AdtKind;
+use crate::{Interner, RustIrDatabase, TraitRef};
+use chalk_ir::{
+    AdtId, CanonicalVarKinds, Floundered, Substitution, TyKind, TyVariableKind, VariableKind,
+};
+
+fn push_adt_sized_conditions<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    trait_ref: TraitRef<I>,
+    adt_id: AdtId<I>,
+    substitution: &Substitution<I>,
+) {
+    let adt_datum = db.adt_datum(adt_id);
+
+    // WF ensures that all enums are Sized, so we only have to consider structs.
+    if adt_datum.kind != AdtKind::Struct {
+        builder.push_fact(trait_ref);
+        return;
+    }
+
+    let interner = db.interner();
+
+    // To check if a struct S<..> is Sized, we only have to look at its last field.
+    // This is because the WF checks for ADTs require that all the other fields must be Sized.
+    let last_field_ty = adt_datum
+        .binders
+        .map_ref(|b| b.variants.clone())
+        .substitute(interner, substitution)
+        .into_iter()
+        .take(1) // We have a struct so we're guaranteed one variant
+        .flat_map(|mut v| v.fields.pop());
+
+    needs_impl_for_tys(db, builder, trait_ref, last_field_ty);
+}
+
+fn push_tuple_sized_conditions<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    trait_ref: TraitRef<I>,
+    arity: usize,
+    substitution: &Substitution<I>,
+) {
+    // Empty tuples are always Sized
+    if arity == 0 {
+        builder.push_fact(trait_ref);
+        return;
+    }
+
+    let interner = db.interner();
+
+    // To check if a tuple is Sized, we only have to look at its last element.
+    // This is because the WF checks for tuples require that all the other elements must be Sized.
+    let last_elem_ty = substitution
+        .iter(interner)
+        .last()
+        .unwrap()
+        .ty(interner)
+        .unwrap()
+        .clone();
+
+    needs_impl_for_tys(db, builder, trait_ref, iter::once(last_elem_ty));
+}
+
+pub fn add_sized_program_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    trait_ref: TraitRef<I>,
+    ty: TyKind<I>,
+    binders: &CanonicalVarKinds<I>,
+) -> Result<(), Floundered> {
+    match ty {
+        TyKind::Adt(adt_id, ref substitution) => {
+            push_adt_sized_conditions(db, builder, trait_ref, adt_id, substitution)
+        }
+        TyKind::Tuple(arity, ref substitution) => {
+            push_tuple_sized_conditions(db, builder, trait_ref, arity, substitution)
+        }
+        TyKind::Array(_, _)
+        | TyKind::Never
+        | TyKind::Closure(_, _)
+        | TyKind::FnDef(_, _)
+        | TyKind::Scalar(_)
+        | TyKind::Raw(_, _)
+        | TyKind::Generator(_, _)
+        | TyKind::GeneratorWitness(_, _)
+        | TyKind::Ref(_, _, _) => builder.push_fact(trait_ref),
+
+        TyKind::AssociatedType(_, _)
+        | TyKind::Slice(_)
+        | TyKind::OpaqueType(_, _)
+        | TyKind::Str
+        | TyKind::Foreign(_)
+        | TyKind::Error => {}
+
+        TyKind::Function(_)
+        | TyKind::InferenceVar(_, TyVariableKind::Float)
+        | TyKind::InferenceVar(_, TyVariableKind::Integer) => builder.push_fact(trait_ref),
+
+        TyKind::BoundVar(bound_var) => {
+            let var_kind = &binders.at(db.interner(), bound_var.index).kind;
+            match var_kind {
+                VariableKind::Ty(TyVariableKind::Integer)
+                | VariableKind::Ty(TyVariableKind::Float) => builder.push_fact(trait_ref),
+
+                // Don't know enough
+                VariableKind::Ty(TyVariableKind::General) => return Err(Floundered),
+
+                VariableKind::Const(_) | VariableKind::Lifetime => {}
+            }
+        }
+
+        // We don't know enough here
+        TyKind::InferenceVar(_, TyVariableKind::General) => return Err(Floundered),
+
+        // These would be handled elsewhere
+        TyKind::Placeholder(_) | TyKind::Dyn(_) | TyKind::Alias(_) => {}
+    }
+    Ok(())
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/tuple.rs b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/tuple.rs
new file mode 100644
index 000000000..a62447827
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/tuple.rs
@@ -0,0 +1,30 @@
+use crate::clauses::ClauseBuilder;
+use crate::rust_ir::WellKnownTrait;
+use crate::{Interner, RustIrDatabase, TraitRef};
+use chalk_ir::{Floundered, Substitution, Ty, TyKind};
+
+/// Add implicit impl for the `Tuple` trait for all tuples
+pub fn add_tuple_program_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    self_ty: Ty<I>,
+) -> Result<(), Floundered> {
+    let interner = db.interner();
+
+    match self_ty.kind(interner) {
+        TyKind::Tuple(..) => {
+            let trait_id = db.well_known_trait_id(WellKnownTrait::Tuple).unwrap();
+
+            builder.push_fact(TraitRef {
+                trait_id,
+                substitution: Substitution::from1(interner, self_ty),
+            });
+
+            Ok(())
+        }
+
+        // Tuple trait is non-enumerable
+        TyKind::InferenceVar(..) | TyKind::BoundVar(_) | TyKind::Alias(..) => Err(Floundered),
+        _ => Ok(()),
+    }
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/unsize.rs b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/unsize.rs
new file mode 100644
index 000000000..6682735b6
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/builtin_traits/unsize.rs
@@ -0,0 +1,479 @@
+use std::collections::HashSet;
+use std::iter;
+use std::ops::ControlFlow;
+
+use crate::clauses::ClauseBuilder;
+use crate::rust_ir::AdtKind;
+use crate::{Interner, RustIrDatabase, TraitRef, WellKnownTrait};
+use chalk_ir::{
+    cast::Cast,
+    interner::HasInterner,
+    visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor},
+    Binders, Const, ConstValue, DebruijnIndex, DomainGoal, DynTy, EqGoal, Goal, LifetimeOutlives,
+    QuantifiedWhereClauses, Substitution, TraitId, Ty, TyKind, TypeOutlives, WhereClause,
+};
+
+struct UnsizeParameterCollector<I: Interner> {
+    interner: I,
+    // FIXME should probably use a bitset instead
+    parameters: HashSet<usize>,
+}
+
+impl<I: Interner> TypeVisitor<I> for UnsizeParameterCollector<I> {
+    type BreakTy = ();
+
+    fn as_dyn(&mut self) -> &mut dyn TypeVisitor<I, BreakTy = Self::BreakTy> {
+        self
+    }
+
+    fn visit_ty(&mut self, ty: &Ty<I>, outer_binder: DebruijnIndex) -> ControlFlow<()> {
+        let interner = self.interner;
+
+        match ty.kind(interner) {
+            TyKind::BoundVar(bound_var) => {
+                // check if bound var refers to the outermost binder
+                if bound_var.debruijn.shifted_in() == outer_binder {
+                    self.parameters.insert(bound_var.index);
+                }
+                ControlFlow::Continue(())
+            }
+            _ => ty.super_visit_with(self, outer_binder),
+        }
+    }
+
+    fn visit_const(&mut self, constant: &Const<I>, outer_binder: DebruijnIndex) -> ControlFlow<()> {
+        let interner = self.interner;
+
+        if let ConstValue::BoundVar(bound_var) = constant.data(interner).value {
+            // check if bound var refers to the outermost binder
+            if bound_var.debruijn.shifted_in() == outer_binder {
+                self.parameters.insert(bound_var.index);
+            }
+        }
+        ControlFlow::Continue(())
+    }
+
+    fn interner(&self) -> I {
+        self.interner
+    }
+}
+
+fn outer_binder_parameters_used<I: Interner>(
+    interner: I,
+    v: &Binders<impl TypeVisitable<I> + HasInterner>,
+) -> HashSet<usize> {
+    let mut visitor = UnsizeParameterCollector {
+        interner,
+        parameters: HashSet::new(),
+    };
+    v.visit_with(&mut visitor, DebruijnIndex::INNERMOST);
+    visitor.parameters
+}
+
+// has nothing to do with occurs check
+struct ParameterOccurenceCheck<'p, I: Interner> {
+    interner: I,
+    parameters: &'p HashSet<usize>,
+}
+
+impl<'p, I: Interner> TypeVisitor<I> for ParameterOccurenceCheck<'p, I> {
+    type BreakTy = ();
+
+    fn as_dyn(&mut self) -> &mut dyn TypeVisitor<I, BreakTy = Self::BreakTy> {
+        self
+    }
+
+    fn visit_ty(&mut self, ty: &Ty<I>, outer_binder: DebruijnIndex) -> ControlFlow<()> {
+        let interner = self.interner;
+
+        match ty.kind(interner) {
+            TyKind::BoundVar(bound_var) => {
+                if bound_var.debruijn.shifted_in() == outer_binder
+                    && self.parameters.contains(&bound_var.index)
+                {
+                    ControlFlow::Break(())
+                } else {
+                    ControlFlow::Continue(())
+                }
+            }
+            _ => ty.super_visit_with(self, outer_binder),
+        }
+    }
+
+    fn visit_const(&mut self, constant: &Const<I>, outer_binder: DebruijnIndex) -> ControlFlow<()> {
+        let interner = self.interner;
+
+        match constant.data(interner).value {
+            ConstValue::BoundVar(bound_var) => {
+                if bound_var.debruijn.shifted_in() == outer_binder
+                    && self.parameters.contains(&bound_var.index)
+                {
+                    ControlFlow::Break(())
+                } else {
+                    ControlFlow::Continue(())
+                }
+            }
+            _ => ControlFlow::Continue(()),
+        }
+    }
+
+    fn interner(&self) -> I {
+        self.interner
+    }
+}
+
+fn uses_outer_binder_params<I: Interner>(
+    interner: I,
+    v: &Binders<impl TypeVisitable<I> + HasInterner>,
+    parameters: &HashSet<usize>,
+) -> bool {
+    let mut visitor = ParameterOccurenceCheck {
+        interner,
+        parameters,
+    };
+
+    let flow = v.visit_with(&mut visitor, DebruijnIndex::INNERMOST);
+    matches!(flow, ControlFlow::Break(_))
+}
+
+fn principal_id<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    bounds: &Binders<QuantifiedWhereClauses<I>>,
+) -> Option<TraitId<I>> {
+    let interner = db.interner();
+
+    bounds
+        .skip_binders()
+        .iter(interner)
+        .filter_map(|b| b.trait_id())
+        .find(|&id| !db.trait_datum(id).is_auto_trait())
+}
+
+fn auto_trait_ids<'a, I: Interner>(
+    db: &'a dyn RustIrDatabase<I>,
+    bounds: &'a Binders<QuantifiedWhereClauses<I>>,
+) -> impl Iterator<Item = TraitId<I>> + 'a {
+    let interner = db.interner();
+
+    bounds
+        .skip_binders()
+        .iter(interner)
+        .filter_map(|clause| clause.trait_id())
+        .filter(move |&id| db.trait_datum(id).is_auto_trait())
+}
+
+pub fn add_unsize_program_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    trait_ref: TraitRef<I>,
+    _ty: TyKind<I>,
+) {
+    let interner = db.interner();
+
+    let source_ty = trait_ref.self_type_parameter(interner);
+    let target_ty = trait_ref
+        .substitution
+        .at(interner, 1)
+        .assert_ty_ref(interner)
+        .clone();
+
+    let unsize_trait_id = trait_ref.trait_id;
+
+    // N.B. here rustc asserts that `TraitRef` is not a higher-ranked bound
+    // i.e. `for<'a> &'a T: Unsize<dyn Trait+'a>` is never provable.
+    //
+    // In chalk it would be awkward to implement and I am not sure
+    // there is a need for it, the original comment states that this restriction
+    // could be lifted.
+    //
+    // for more info visit `fn assemble_candidates_for_unsizing` and
+    // `fn confirm_builtin_unisize_candidate` in rustc.
+
+    match (source_ty.kind(interner), target_ty.kind(interner)) {
+        // dyn Trait + AutoX + 'a -> dyn Trait + AutoY + 'b
+        (
+            TyKind::Dyn(DynTy {
+                bounds: bounds_a,
+                lifetime: lifetime_a,
+            }),
+            TyKind::Dyn(DynTy {
+                bounds: bounds_b,
+                lifetime: lifetime_b,
+            }),
+        ) => {
+            let principal_a = principal_id(db, bounds_a);
+            let principal_b = principal_id(db, bounds_b);
+
+            let auto_trait_ids_a: Vec<_> = auto_trait_ids(db, bounds_a).collect();
+            let auto_trait_ids_b: Vec<_> = auto_trait_ids(db, bounds_b).collect();
+
+            let may_apply = principal_a == principal_b
+                && auto_trait_ids_b
+                    .iter()
+                    .all(|id_b| auto_trait_ids_a.iter().any(|id_a| id_a == id_b));
+
+            if !may_apply {
+                return;
+            }
+
+            // COMMENT FROM RUSTC:
+            // ------------------
+            // Require that the traits involved in this upcast are **equal**;
+            // only the **lifetime bound** is changed.
+            //
+            // This condition is arguably too strong -- it would
+            // suffice for the source trait to be a *subtype* of the target
+            // trait. In particular, changing from something like
+            // `for<'a, 'b> Foo<'a, 'b>` to `for<'a> Foo<'a, 'a>` should be
+            // permitted.
+            // <...>
+            // I've modified this to `.eq` because I want to continue rejecting
+            // that [`old-lub-glb-object.rs`] test (as we have
+            // done for quite some time) before we are firmly comfortable
+            // with what our behavior should be there. -nikomatsakis
+            // ------------------
+
+            // Construct a new trait object type by taking the source ty,
+            // filtering out auto traits of source that are not present in target
+            // and changing source lifetime to target lifetime.
+            //
+            // In order for the coercion to be valid, this new type
+            // should be equal to target type.
+            let new_source_ty = TyKind::Dyn(DynTy {
+                bounds: bounds_a.map_ref(|bounds| {
+                    QuantifiedWhereClauses::from_iter(
+                        interner,
+                        bounds.iter(interner).filter(|bound| {
+                            let trait_id = match bound.trait_id() {
+                                Some(id) => id,
+                                None => return true,
+                            };
+
+                            if auto_trait_ids_a.iter().all(|&id_a| id_a != trait_id) {
+                                return true;
+                            }
+                            auto_trait_ids_b.iter().any(|&id_b| id_b == trait_id)
+                        }),
+                    )
+                }),
+                lifetime: lifetime_b.clone(),
+            })
+            .intern(interner);
+
+            // Check that new source is equal to target
+            let eq_goal = EqGoal {
+                a: new_source_ty.cast(interner),
+                b: target_ty.clone().cast(interner),
+            }
+            .cast(interner);
+
+            // Check that source lifetime outlives target lifetime
+            let lifetime_outlives_goal: Goal<I> = WhereClause::LifetimeOutlives(LifetimeOutlives {
+                a: lifetime_a.clone(),
+                b: lifetime_b.clone(),
+            })
+            .cast(interner);
+
+            builder.push_clause(trait_ref, [eq_goal, lifetime_outlives_goal].iter());
+        }
+
+        // T -> dyn Trait + 'a
+        (_, TyKind::Dyn(DynTy { bounds, lifetime })) => {
+            // Check if all traits in trait object are object safe
+            let object_safe_goals = bounds
+                .skip_binders()
+                .iter(interner)
+                .filter_map(|bound| bound.trait_id())
+                .map(|id| DomainGoal::ObjectSafe(id).cast(interner));
+
+            // Check that T implements all traits of the trait object
+            let source_ty_bounds = bounds
+                .clone()
+                .substitute(interner, &Substitution::from1(interner, source_ty.clone()));
+
+            // Check that T is sized because we can only make
+            // a trait object from a sized type
+            let self_sized_goal: WhereClause<_> = TraitRef {
+                trait_id: db
+                    .well_known_trait_id(WellKnownTrait::Sized)
+                    .expect("Expected Sized to be defined when proving Unsize"),
+                substitution: Substitution::from1(interner, source_ty.clone()),
+            }
+            .cast(interner);
+
+            // Check that `source_ty` outlives `'a`
+            let source_ty_outlives: Goal<_> = WhereClause::TypeOutlives(TypeOutlives {
+                ty: source_ty,
+                lifetime: lifetime.clone(),
+            })
+            .cast(interner);
+
+            builder.push_clause(
+                trait_ref,
+                source_ty_bounds
+                    .iter(interner)
+                    .map(|bound| bound.clone().cast::<Goal<I>>(interner))
+                    .chain(object_safe_goals)
+                    .chain(iter::once(self_sized_goal.cast(interner)))
+                    .chain(iter::once(source_ty_outlives)),
+            );
+        }
+
+        (TyKind::Array(array_ty, _array_const), TyKind::Slice(slice_ty)) => {
+            let eq_goal = EqGoal {
+                a: array_ty.clone().cast(interner),
+                b: slice_ty.clone().cast(interner),
+            };
+
+            builder.push_clause(trait_ref, iter::once(eq_goal));
+        }
+
+        // Adt<T> -> Adt<U>
+        (TyKind::Adt(adt_id_a, substitution_a), TyKind::Adt(adt_id_b, substitution_b)) => {
+            if adt_id_a != adt_id_b {
+                return;
+            }
+
+            let adt_id = *adt_id_a;
+            let adt_datum = db.adt_datum(adt_id);
+
+            // Unsizing of enums is not allowed
+            if adt_datum.kind == AdtKind::Enum {
+                return;
+            }
+
+            // We have a `struct` so we're guaranteed a single variant
+            let fields_len = adt_datum
+                .binders
+                .skip_binders()
+                .variants
+                .last()
+                .unwrap()
+                .fields
+                .len();
+
+            if fields_len == 0 {
+                return;
+            }
+
+            let adt_tail_field = adt_datum
+                .binders
+                .map_ref(|bound| bound.variants.last().unwrap().fields.last().unwrap())
+                .cloned();
+
+            // Collect unsize parameters that last field contains and
+            // ensure there at least one of them.
+            let unsize_parameter_candidates =
+                outer_binder_parameters_used(interner, &adt_tail_field);
+
+            if unsize_parameter_candidates.is_empty() {
+                return;
+            }
+            // Ensure none of the other fields mention the parameters used
+            // in unsizing.
+            // We specifically want variables specified by the outermost binder
+            // i.e. the struct generic arguments binder.
+            if uses_outer_binder_params(
+                interner,
+                &adt_datum
+                    .binders
+                    .map_ref(|bound| &bound.variants.last().unwrap().fields[..fields_len - 1]),
+                &unsize_parameter_candidates,
+            ) {
+                return;
+            }
+
+            let parameters_a = substitution_a.as_slice(interner);
+            let parameters_b = substitution_b.as_slice(interner);
+            // Check that the source adt with the target's
+            // unsizing parameters is equal to the target.
+            // We construct a new substitution where if a parameter is used in the
+            // coercion (i.e. it's a non-lifetime struct parameter used by it's last field),
+            // then we take that parameter from target substitution, otherwise we take
+            // it from the source substitution.
+            //
+            // In order for the coercion to be valid, target struct and
+            // struct with this newly constructed substitution applied to it should be equal.
+            let substitution = Substitution::from_iter(
+                interner,
+                parameters_a.iter().enumerate().map(|(i, p)| {
+                    if unsize_parameter_candidates.contains(&i) {
+                        &parameters_b[i]
+                    } else {
+                        p
+                    }
+                }),
+            );
+
+            let eq_goal = EqGoal {
+                a: TyKind::Adt(adt_id, substitution)
+                    .intern(interner)
+                    .cast(interner),
+                b: target_ty.clone().cast(interner),
+            }
+            .cast(interner);
+
+            // Extract `TailField<T>` and `TailField<U>` from `Struct<T>` and `Struct<U>`.
+            let source_tail_field = adt_tail_field.clone().substitute(interner, substitution_a);
+            let target_tail_field = adt_tail_field.substitute(interner, substitution_b);
+
+            // Check that `TailField<T>: Unsize<TailField<U>>`
+            let last_field_unsizing_goal: Goal<I> = TraitRef {
+                trait_id: unsize_trait_id,
+                substitution: Substitution::from_iter(
+                    interner,
+                    [source_tail_field, target_tail_field].iter().cloned(),
+                ),
+            }
+            .cast(interner);
+
+            builder.push_clause(trait_ref, [eq_goal, last_field_unsizing_goal].iter());
+        }
+
+        // (.., T) -> (.., U)
+        (TyKind::Tuple(arity_a, substitution_a), TyKind::Tuple(arity_b, substitution_b)) => {
+            if arity_a != arity_b || *arity_a == 0 {
+                return;
+            }
+            let arity = arity_a;
+
+            let tail_ty_a = substitution_a.iter(interner).last().unwrap();
+            let tail_ty_b = substitution_b.iter(interner).last().unwrap();
+
+            // Check that the source tuple with the target's
+            // last element is equal to the target.
+            let new_tuple = TyKind::Tuple(
+                *arity,
+                Substitution::from_iter(
+                    interner,
+                    substitution_a
+                        .iter(interner)
+                        .take(arity - 1)
+                        .chain(iter::once(tail_ty_b)),
+                ),
+            )
+            .cast(interner)
+            .intern(interner);
+
+            let eq_goal: Goal<I> = EqGoal {
+                a: new_tuple.cast(interner),
+                b: target_ty.clone().cast(interner),
+            }
+            .cast(interner);
+
+            // Check that `T: Unsize<U>`
+            let last_field_unsizing_goal: Goal<I> = TraitRef {
+                trait_id: unsize_trait_id,
+                substitution: Substitution::from_iter(
+                    interner,
+                    [tail_ty_a, tail_ty_b].iter().cloned(),
+                ),
+            }
+            .cast(interner);
+
+            builder.push_clause(trait_ref, [eq_goal, last_field_unsizing_goal].iter());
+        }
+
+        _ => (),
+    }
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/dyn_ty.rs b/vendor/chalk-solve-0.87.0/src/clauses/dyn_ty.rs
new file mode 100644
index 000000000..505da43f9
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/dyn_ty.rs
@@ -0,0 +1,81 @@
+use super::{builder::ClauseBuilder, generalize};
+use crate::RustIrDatabase;
+use chalk_ir::{cast::Cast, interner::Interner, Ty, TyKind, WhereClause};
+
+/// If the self type `S` of an `Implemented` goal is a `dyn trait` type, we wish
+/// to generate program-clauses that indicates that it implements its own
+/// traits. For example, a `dyn Write` type implements `Write` and so on.
+///
+/// To see how this works, consider as an example the type `dyn Fn(&u8)`. This
+/// is really shorthand for `dyn for<'a> Fn<(&'a u8), Output = ()>`, and we
+/// represent that type as something like this:
+///
+/// ```ignore
+/// dyn(exists<T> {
+///     forall<'a> { Implemented(T: Fn<'a>) },
+///     forall<'a> { AliasEq(<T as Fn<'a>>::Output, ()) },
+/// })
+/// ```
+///
+/// so what we will do is to generate one program clause for each of the
+/// conditions. Thus we get two program clauses:
+///
+/// ```ignore
+/// forall<'a> { Implemented(dyn Fn(&u8): Fn<(&'a u8)>) }
+/// ```
+///
+/// and
+///
+/// ```ignore
+/// forall<'a> { AliasEq(<dyn Fn(&u8) as Fn<'a>>::Output, ()) },
+/// ```
+pub(super) fn build_dyn_self_ty_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    self_ty: Ty<I>,
+) {
+    let interner = db.interner();
+    let dyn_ty = match self_ty.kind(interner) {
+        TyKind::Dyn(dyn_ty) => dyn_ty.clone(),
+        _ => return,
+    };
+    let generalized_dyn_ty = generalize::Generalize::apply(db.interner(), dyn_ty);
+
+    // Here, `self_ty` is the `dyn Fn(&u8)`, and `dyn_ty` is the `exists<T> { ..
+    // }` clauses shown above.
+
+    // Turn free BoundVars in the type into new existentials. E.g.
+    // we might get some `dyn Foo<?X>`, and we don't want to return
+    // a clause with a free variable. We can instead return a
+    // slightly more general clause by basically turning this into
+    // `exists<A> dyn Foo<A>`.
+
+    builder.push_binders(generalized_dyn_ty, |builder, dyn_ty| {
+        for exists_qwc in dyn_ty.bounds.map_ref(|r| r.iter(interner)) {
+            // Replace the `T` from `exists<T> { .. }` with `self_ty`,
+            // yielding clases like
+            //
+            // ```
+            // forall<'a> { Implemented(dyn Fn(&u8): Fn<(&'a u8)>) }
+            // ```
+            let qwc = exists_qwc
+                .cloned()
+                .substitute(interner, &[self_ty.clone().cast(interner)]);
+
+            builder.push_binders(qwc, |builder, bound| match &bound {
+                // For the implemented traits, we need to elaborate super traits and add where clauses from the trait
+                WhereClause::Implemented(trait_ref) => {
+                    super::super_traits::push_trait_super_clauses(
+                        builder.db,
+                        builder,
+                        trait_ref.clone(),
+                    )
+                }
+                // FIXME: Associated item bindings are just taken as facts (?)
+                WhereClause::AliasEq(_) => builder.push_fact(bound),
+                WhereClause::LifetimeOutlives(..) => {}
+                WhereClause::TypeOutlives(..) => {}
+            });
+        }
+    });
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/env_elaborator.rs b/vendor/chalk-solve-0.87.0/src/clauses/env_elaborator.rs
new file mode 100644
index 000000000..29032a7ad
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/env_elaborator.rs
@@ -0,0 +1,107 @@
+use super::program_clauses::ToProgramClauses;
+use crate::clauses::builder::ClauseBuilder;
+use crate::clauses::{match_alias_ty, match_ty};
+use crate::DomainGoal;
+use crate::FromEnv;
+use crate::ProgramClause;
+use crate::RustIrDatabase;
+use crate::Ty;
+use crate::{debug_span, TyKind};
+use chalk_ir::interner::Interner;
+use chalk_ir::visit::{TypeVisitable, TypeVisitor};
+use chalk_ir::{DebruijnIndex, Environment};
+use rustc_hash::FxHashSet;
+use std::ops::ControlFlow;
+use tracing::instrument;
+
+/// When proving a `FromEnv` goal, we elaborate all `FromEnv` goals
+/// found in the environment.
+///
+/// For example, when `T: Clone` is in the environment, we can prove
+/// `T: Copy` by adding the clauses from `trait Clone`, which includes
+/// the rule `FromEnv(T: Copy) :- FromEnv(T: Clone)
+pub(super) fn elaborate_env_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    in_clauses: &[ProgramClause<I>],
+    out: &mut FxHashSet<ProgramClause<I>>,
+    environment: &Environment<I>,
+) {
+    let mut this_round = vec![];
+    let builder = &mut ClauseBuilder::new(db, &mut this_round);
+    let mut elaborater = EnvElaborator {
+        db,
+        builder,
+        environment,
+    };
+    in_clauses.visit_with(&mut elaborater, DebruijnIndex::INNERMOST);
+    out.extend(this_round);
+}
+
+struct EnvElaborator<'me, 'builder, I: Interner> {
+    db: &'me dyn RustIrDatabase<I>,
+    builder: &'builder mut ClauseBuilder<'me, I>,
+    environment: &'me Environment<I>,
+}
+
+impl<'me, 'builder, I: Interner> TypeVisitor<I> for EnvElaborator<'me, 'builder, I> {
+    type BreakTy = ();
+
+    fn as_dyn(&mut self) -> &mut dyn TypeVisitor<I, BreakTy = Self::BreakTy> {
+        self
+    }
+
+    fn interner(&self) -> I {
+        self.db.interner()
+    }
+    #[instrument(level = "debug", skip(self, _outer_binder))]
+    fn visit_ty(&mut self, ty: &Ty<I>, _outer_binder: DebruijnIndex) -> ControlFlow<()> {
+        match ty.kind(self.interner()) {
+            TyKind::Alias(alias_ty) => match_alias_ty(self.builder, self.environment, alias_ty),
+            TyKind::Placeholder(_) => {}
+
+            // FIXME(#203) -- We haven't fully figured out the implied
+            // bounds story around `dyn Trait` types.
+            TyKind::Dyn(_) => (),
+
+            TyKind::Function(_) | TyKind::BoundVar(_) | TyKind::InferenceVar(_, _) => (),
+
+            _ => {
+                // This shouldn't fail because of the above clauses
+                match_ty(self.builder, self.environment, ty)
+                    .map_err(|_| ())
+                    .unwrap()
+            }
+        }
+        ControlFlow::Continue(())
+    }
+
+    fn visit_domain_goal(
+        &mut self,
+        domain_goal: &DomainGoal<I>,
+        outer_binder: DebruijnIndex,
+    ) -> ControlFlow<()> {
+        if let DomainGoal::FromEnv(from_env) = domain_goal {
+            debug_span!("visit_domain_goal", ?from_env);
+            match from_env {
+                FromEnv::Trait(trait_ref) => {
+                    let trait_datum = self.db.trait_datum(trait_ref.trait_id);
+
+                    trait_datum.to_program_clauses(self.builder, self.environment);
+
+                    // If we know that `T: Iterator`, then we also know
+                    // things about `<T as Iterator>::Item`, so push those
+                    // implied bounds too:
+                    for &associated_ty_id in &trait_datum.associated_ty_ids {
+                        self.db
+                            .associated_ty_data(associated_ty_id)
+                            .to_program_clauses(self.builder, self.environment);
+                    }
+                    ControlFlow::Continue(())
+                }
+                FromEnv::Ty(ty) => ty.visit_with(self, outer_binder),
+            }
+        } else {
+            ControlFlow::Continue(())
+        }
+    }
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/generalize.rs b/vendor/chalk-solve-0.87.0/src/clauses/generalize.rs
new file mode 100644
index 000000000..bff05b369
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/generalize.rs
@@ -0,0 +1,99 @@
+//! This gets rid of free variables in a type by replacing them by fresh bound
+//! ones. We use this when building clauses that contain types passed to
+//! `program_clauses`; these may contain variables, and just copying those
+//! variables verbatim leads to problems. Instead, we return a slightly more
+//! general program clause, with new variables in those places. This can only
+//! happen with `dyn Trait` currently; that's the only case where we use the
+//! types passed to `program_clauses` in the clauses we generate.
+
+use chalk_derive::FallibleTypeFolder;
+use chalk_ir::{
+    fold::{TypeFoldable, TypeFolder},
+    interner::{HasInterner, Interner},
+    Binders, BoundVar, Const, ConstData, ConstValue, DebruijnIndex, Lifetime, LifetimeData, Ty,
+    TyKind, TyVariableKind, VariableKind, VariableKinds,
+};
+use rustc_hash::FxHashMap;
+
+#[derive(FallibleTypeFolder)]
+pub struct Generalize<I: Interner> {
+    binders: Vec<VariableKind<I>>,
+    mapping: FxHashMap<BoundVar, usize>,
+    interner: I,
+}
+
+impl<I: Interner> Generalize<I> {
+    pub fn apply<T>(interner: I, value: T) -> Binders<T>
+    where
+        T: HasInterner<Interner = I> + TypeFoldable<I>,
+    {
+        let mut generalize = Generalize {
+            binders: Vec::new(),
+            mapping: FxHashMap::default(),
+            interner,
+        };
+        let value = value
+            .try_fold_with(&mut generalize, DebruijnIndex::INNERMOST)
+            .unwrap();
+        Binders::new(
+            VariableKinds::from_iter(interner, generalize.binders),
+            value,
+        )
+    }
+}
+
+impl<I: Interner> TypeFolder<I> for Generalize<I> {
+    fn as_dyn(&mut self) -> &mut dyn TypeFolder<I> {
+        self
+    }
+
+    fn fold_free_var_ty(&mut self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> Ty<I> {
+        let binder_vec = &mut self.binders;
+        let new_index = self.mapping.entry(bound_var).or_insert_with(|| {
+            let i = binder_vec.len();
+            binder_vec.push(VariableKind::Ty(TyVariableKind::General));
+            i
+        });
+        let new_var = BoundVar::new(outer_binder, *new_index);
+        TyKind::BoundVar(new_var).intern(TypeFolder::interner(self))
+    }
+
+    fn fold_free_var_const(
+        &mut self,
+        ty: Ty<I>,
+        bound_var: BoundVar,
+        outer_binder: DebruijnIndex,
+    ) -> Const<I> {
+        let binder_vec = &mut self.binders;
+        let new_index = self.mapping.entry(bound_var).or_insert_with(|| {
+            let i = binder_vec.len();
+            binder_vec.push(VariableKind::Const(ty.clone()));
+            i
+        });
+        let new_var = BoundVar::new(outer_binder, *new_index);
+        ConstData {
+            ty,
+            value: ConstValue::BoundVar(new_var),
+        }
+        .intern(TypeFolder::interner(self))
+    }
+
+    fn fold_free_var_lifetime(
+        &mut self,
+        bound_var: BoundVar,
+        outer_binder: DebruijnIndex,
+    ) -> Lifetime<I> {
+        let binder_vec = &mut self.binders;
+        let new_index = self.mapping.entry(bound_var).or_insert_with(|| {
+            let i = binder_vec.len();
+            binder_vec.push(VariableKind::Lifetime);
+            i
+        });
+        let new_var = BoundVar::new(outer_binder, *new_index);
+        LifetimeData::BoundVar(new_var).intern(TypeFolder::interner(self))
+    }
+
+    fn interner(&self) -> I {
+        self.interner
+    }
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/program_clauses.rs b/vendor/chalk-solve-0.87.0/src/clauses/program_clauses.rs
new file mode 100644
index 000000000..19811ff8b
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/program_clauses.rs
@@ -0,0 +1,921 @@
+use crate::clauses::builder::ClauseBuilder;
+use crate::rust_ir::*;
+use crate::split::Split;
+use chalk_ir::cast::{Cast, Caster};
+use chalk_ir::interner::Interner;
+use chalk_ir::*;
+use std::iter;
+use tracing::instrument;
+
+/// Trait for lowering a given piece of rust-ir source (e.g., an impl
+/// or struct definition) into its associated "program clauses" --
+/// that is, into the lowered, logical rules that it defines.
+pub trait ToProgramClauses<I: Interner> {
+    fn to_program_clauses(&self, builder: &mut ClauseBuilder<'_, I>, environment: &Environment<I>);
+}
+
+impl<I: Interner> ToProgramClauses<I> for ImplDatum<I> {
+    /// Given `impl<T: Clone> Clone for Vec<T> { ... }`, generate:
+    ///
+    /// ```notrust
+    /// -- Rule Implemented-From-Impl
+    /// forall<T> {
+    ///     Implemented(Vec<T>: Clone) :- Implemented(T: Clone).
+    /// }
+    /// ```
+    ///
+    /// For a negative impl like `impl... !Clone for ...`, however, we
+    /// generate nothing -- this is just a way to *opt out* from the
+    /// default auto trait impls, it doesn't have any positive effect
+    /// on its own.
+    fn to_program_clauses(
+        &self,
+        builder: &mut ClauseBuilder<'_, I>,
+        _environment: &Environment<I>,
+    ) {
+        if self.is_positive() {
+            let binders = self.binders.clone();
+            builder.push_binders(
+                binders,
+                |builder,
+                 ImplDatumBound {
+                     trait_ref,
+                     where_clauses,
+                 }| {
+                    builder.push_clause(trait_ref, where_clauses);
+                },
+            );
+        }
+    }
+}
+
+impl<I: Interner> ToProgramClauses<I> for AssociatedTyValue<I> {
+    /// Given the following trait:
+    ///
+    /// ```notrust
+    /// trait Iterable {
+    ///     type IntoIter<'a>: 'a;
+    /// }
+    /// ```
+    ///
+    /// Then for the following impl:
+    /// ```notrust
+    /// impl<T> Iterable for Vec<T> where T: Clone {
+    ///     type IntoIter<'a> = Iter<'a, T>;
+    /// }
+    /// ```
+    ///
+    /// we generate:
+    ///
+    /// ```notrust
+    /// -- Rule Normalize-From-Impl
+    /// forall<'a, T> {
+    ///     Normalize(<Vec<T> as Iterable>::IntoIter<'a> -> Iter<'a, T>>) :-
+    ///         Implemented(T: Clone),  // (1)
+    ///         Implemented(Iter<'a, T>: 'a).   // (2)
+    /// }
+    /// ```
+    fn to_program_clauses(
+        &self,
+        builder: &mut ClauseBuilder<'_, I>,
+        _environment: &Environment<I>,
+    ) {
+        let impl_datum = builder.db.impl_datum(self.impl_id);
+        let associated_ty = builder.db.associated_ty_data(self.associated_ty_id);
+
+        builder.push_binders(self.value.clone(), |builder, assoc_ty_value| {
+            let all_parameters = builder.placeholders_in_scope().to_vec();
+
+            // Get the projection for this associated type:
+            //
+            // * `impl_params`: `[!T]`
+            // * `projection`: `<Vec<!T> as Iterable>::Iter<'!a>`
+            let (impl_params, projection) = builder
+                .db
+                .impl_parameters_and_projection_from_associated_ty_value(&all_parameters, self);
+
+            // Assemble the full list of conditions for projection to be valid.
+            // This comes in two parts, marked as (1) and (2) in doc above:
+            //
+            // 1. require that the where clauses from the impl apply
+            let interner = builder.db.interner();
+            let impl_where_clauses = impl_datum
+                .binders
+                .map_ref(|b| &b.where_clauses)
+                .into_iter()
+                .map(|wc| wc.cloned().substitute(interner, impl_params));
+
+            // 2. any where-clauses from the `type` declaration in the trait: the
+            //    parameters must be substituted with those of the impl
+            let assoc_ty_where_clauses = associated_ty
+                .binders
+                .map_ref(|b| &b.where_clauses)
+                .into_iter()
+                .map(|wc| wc.cloned().substitute(interner, &projection.substitution));
+
+            // Create the final program clause:
+            //
+            // ```notrust
+            // -- Rule Normalize-From-Impl
+            // forall<'a, T> {
+            //     Normalize(<Vec<T> as Iterable>::IntoIter<'a> -> Iter<'a, T>>) :-
+            //         Implemented(T: Clone),  // (1)
+            //         Implemented(Iter<'a, T>: 'a).   // (2)
+            // }
+            // ```
+            builder.push_clause(
+                Normalize {
+                    alias: AliasTy::Projection(projection.clone()),
+                    ty: assoc_ty_value.ty,
+                },
+                impl_where_clauses.chain(assoc_ty_where_clauses),
+            );
+        });
+    }
+}
+
+impl<I: Interner> ToProgramClauses<I> for OpaqueTyDatum<I> {
+    /// Given `opaque type T<U>: A + B = HiddenTy where U: C;`, we generate:
+    ///
+    /// ```notrust
+    /// AliasEq(T<U> = HiddenTy) :- Reveal.
+    /// AliasEq(T<U> = !T<U>).
+    /// WF(T<U>) :- WF(U: C).
+    /// Implemented(!T<U>: A).
+    /// Implemented(!T<U>: B).
+    /// ```
+    /// where `!T<..>` is the placeholder for the unnormalized type `T<..>`.
+    #[instrument(level = "debug", skip(builder))]
+    fn to_program_clauses(
+        &self,
+        builder: &mut ClauseBuilder<'_, I>,
+        _environment: &Environment<I>,
+    ) {
+        builder.push_binders(self.bound.clone(), |builder, opaque_ty_bound| {
+            let interner = builder.interner();
+            let substitution = builder.substitution_in_scope();
+            let alias = AliasTy::Opaque(OpaqueTy {
+                opaque_ty_id: self.opaque_ty_id,
+                substitution: substitution.clone(),
+            });
+
+            let alias_placeholder_ty =
+                TyKind::OpaqueType(self.opaque_ty_id, substitution).intern(interner);
+
+            // AliasEq(T<..> = HiddenTy) :- Reveal.
+            builder.push_clause(
+                DomainGoal::Holds(
+                    AliasEq {
+                        alias: alias.clone(),
+                        ty: builder.db.hidden_opaque_type(self.opaque_ty_id),
+                    }
+                    .cast(interner),
+                ),
+                iter::once(DomainGoal::Reveal),
+            );
+
+            // AliasEq(T<..> = !T<..>).
+            builder.push_fact(DomainGoal::Holds(
+                AliasEq {
+                    alias,
+                    ty: alias_placeholder_ty.clone(),
+                }
+                .cast(interner),
+            ));
+
+            // WF(!T<..>) :- WF(WC).
+            builder.push_binders(opaque_ty_bound.where_clauses, |builder, where_clauses| {
+                builder.push_clause(
+                    WellFormed::Ty(alias_placeholder_ty.clone()),
+                    where_clauses
+                        .into_iter()
+                        .map(|wc| wc.into_well_formed_goal(interner)),
+                );
+            });
+
+            let substitution = Substitution::from1(interner, alias_placeholder_ty);
+            for bound in opaque_ty_bound.bounds {
+                let bound_with_placeholder_ty = bound.substitute(interner, &substitution);
+                builder.push_binders(bound_with_placeholder_ty, |builder, bound| match &bound {
+                    // For the implemented traits, we need to elaborate super traits and add where clauses from the trait
+                    WhereClause::Implemented(trait_ref) => {
+                        super::super_traits::push_trait_super_clauses(
+                            builder.db,
+                            builder,
+                            trait_ref.clone(),
+                        )
+                    }
+                    // FIXME: Associated item bindings are just taken as facts (?)
+                    WhereClause::AliasEq(_) => builder.push_fact(bound),
+                    WhereClause::LifetimeOutlives(..) => {}
+                    WhereClause::TypeOutlives(..) => {}
+                });
+            }
+        });
+    }
+}
+
+/// Generates the "well-formed" program clauses for an applicative type
+/// with the name `type_name`. For example, given a struct definition:
+///
+/// ```ignore
+/// struct Foo<T: Eq> { }
+/// ```
+///
+/// we would generate the clause:
+///
+/// ```notrust
+/// forall<T> {
+///     WF(Foo<T>) :- WF(T: Eq).
+/// }
+/// ```
+///
+/// # Parameters
+/// - builder -- the clause builder. We assume all the generic types from `Foo` are in scope
+/// - type_name -- in our example above, the name `Foo`
+/// - where_clauses -- the list of where clauses declared on the type (`T: Eq`, in our example)
+fn well_formed_program_clauses<'a, I, Wc>(
+    builder: &'a mut ClauseBuilder<'_, I>,
+    ty: Ty<I>,
+    where_clauses: Wc,
+) where
+    I: Interner,
+    Wc: Iterator<Item = &'a QuantifiedWhereClause<I>>,
+{
+    let interner = builder.interner();
+    builder.push_clause(
+        WellFormed::Ty(ty),
+        where_clauses
+            .cloned()
+            .map(|qwc| qwc.into_well_formed_goal(interner)),
+    );
+}
+
+/// Generates the "fully visible" program clauses for an applicative type
+/// with the name `type_name`. For example, given a struct definition:
+///
+/// ```ignore
+/// struct Foo<T: Eq> { }
+/// ```
+///
+/// we would generate the clause:
+///
+/// ```notrust
+/// forall<T> {
+///     IsFullyVisible(Foo<T>) :- IsFullyVisible(T).
+/// }
+/// ```
+///
+/// # Parameters
+///
+/// - builder -- the clause builder. We assume all the generic types from `Foo` are in scope
+/// - type_name -- in our example above, the name `Foo`
+fn fully_visible_program_clauses<I>(
+    builder: &mut ClauseBuilder<'_, I>,
+    ty: Ty<I>,
+    subst: &Substitution<I>,
+) where
+    I: Interner,
+{
+    let interner = builder.interner();
+    builder.push_clause(
+        DomainGoal::IsFullyVisible(ty),
+        subst
+            .type_parameters(interner)
+            .map(|typ| DomainGoal::IsFullyVisible(typ).cast::<Goal<_>>(interner)),
+    );
+}
+
+/// Generates the "implied bounds" clauses for an applicative
+/// type with the name `type_name`. For example, if `type_name`
+/// represents a struct `S` that is declared like:
+///
+/// ```ignore
+/// struct S<T> where T: Eq {  }
+/// ```
+///
+/// then we would generate the rule:
+///
+/// ```notrust
+/// FromEnv(T: Eq) :- FromEnv(S<T>)
+/// ```
+///
+/// # Parameters
+///
+/// - builder -- the clause builder. We assume all the generic types from `S` are in scope.
+/// - type_name -- in our example above, the name `S`
+/// - where_clauses -- the list of where clauses declared on the type (`T: Eq`, in our example).
+fn implied_bounds_program_clauses<'a, I, Wc>(
+    builder: &'a mut ClauseBuilder<'_, I>,
+    ty: &Ty<I>,
+    where_clauses: Wc,
+) where
+    I: Interner,
+    Wc: Iterator<Item = &'a QuantifiedWhereClause<I>>,
+{
+    let interner = builder.interner();
+
+    for qwc in where_clauses {
+        builder.push_binders(qwc.clone(), |builder, wc| {
+            builder.push_clause(wc.into_from_env_goal(interner), Some(ty.clone().from_env()));
+        });
+    }
+}
+
+impl<I: Interner> ToProgramClauses<I> for AdtDatum<I> {
+    /// Given the following type definition: `struct Foo<T: Eq> { }`, generate:
+    ///
+    /// ```notrust
+    /// -- Rule WellFormed-Type
+    /// forall<T> {
+    ///     WF(Foo<T>) :- WF(T: Eq).
+    /// }
+    ///
+    /// -- Rule Implied-Bound-From-Type
+    /// forall<T> {
+    ///     FromEnv(T: Eq) :- FromEnv(Foo<T>).
+    /// }
+    ///
+    /// forall<T> {
+    ///     IsFullyVisible(Foo<T>) :- IsFullyVisible(T).
+    /// }
+    /// ```
+    ///
+    /// If the type `Foo` is marked `#[upstream]`, we also generate:
+    ///
+    /// ```notrust
+    /// forall<T> { IsUpstream(Foo<T>). }
+    /// ```
+    ///
+    /// Otherwise, if the type `Foo` is not marked `#[upstream]`, we generate:
+    /// ```notrust
+    /// forall<T> { IsLocal(Foo<T>). }
+    /// ```
+    ///
+    /// Given an `#[upstream]` type that is also fundamental:
+    ///
+    /// ```notrust
+    /// #[upstream]
+    /// #[fundamental]
+    /// struct Box<T, U> {}
+    /// ```
+    ///
+    /// We generate the following clauses:
+    ///
+    /// ```notrust
+    /// forall<T, U> { IsLocal(Box<T, U>) :- IsLocal(T). }
+    /// forall<T, U> { IsLocal(Box<T, U>) :- IsLocal(U). }
+    ///
+    /// forall<T, U> { IsUpstream(Box<T, U>) :- IsUpstream(T), IsUpstream(U). }
+    ///
+    /// // Generated for both upstream and local fundamental types
+    /// forall<T, U> { DownstreamType(Box<T, U>) :- DownstreamType(T). }
+    /// forall<T, U> { DownstreamType(Box<T, U>) :- DownstreamType(U). }
+    /// ```
+    ///
+    #[instrument(level = "debug", skip(builder))]
+    fn to_program_clauses(
+        &self,
+        builder: &mut ClauseBuilder<'_, I>,
+        _environment: &Environment<I>,
+    ) {
+        let interner = builder.interner();
+        let binders = self.binders.map_ref(|b| &b.where_clauses).cloned();
+
+        builder.push_binders(binders, |builder, where_clauses| {
+            let self_ty = TyKind::Adt(self.id, builder.substitution_in_scope()).intern(interner);
+
+            well_formed_program_clauses(builder, self_ty.clone(), where_clauses.iter());
+
+            implied_bounds_program_clauses(builder, &self_ty, where_clauses.iter());
+
+            fully_visible_program_clauses(
+                builder,
+                self_ty.clone(),
+                &builder.substitution_in_scope(),
+            );
+
+            // Types that are not marked `#[upstream]` satisfy IsLocal(Ty)
+            if !self.flags.upstream {
+                // `IsLocalTy(Ty)` depends *only* on whether the type
+                // is marked #[upstream] and nothing else
+                builder.push_fact(DomainGoal::IsLocal(self_ty.clone()));
+            } else if self.flags.fundamental {
+                // If a type is `#[upstream]`, but is also
+                // `#[fundamental]`, it satisfies IsLocal if and only
+                // if its parameters satisfy IsLocal
+                for type_param in builder.substitution_in_scope().type_parameters(interner) {
+                    builder.push_clause(
+                        DomainGoal::IsLocal(self_ty.clone()),
+                        Some(DomainGoal::IsLocal(type_param)),
+                    );
+                }
+                builder.push_clause(
+                    DomainGoal::IsUpstream(self_ty.clone()),
+                    builder
+                        .substitution_in_scope()
+                        .type_parameters(interner)
+                        .map(|type_param| DomainGoal::IsUpstream(type_param)),
+                );
+            } else {
+                // The type is just upstream and not fundamental
+                builder.push_fact(DomainGoal::IsUpstream(self_ty.clone()));
+            }
+
+            if self.flags.fundamental {
+                assert!(
+                    builder
+                        .substitution_in_scope()
+                        .type_parameters(interner)
+                        .count()
+                        >= 1,
+                    "Only fundamental types with type parameters are supported"
+                );
+                for type_param in builder.substitution_in_scope().type_parameters(interner) {
+                    builder.push_clause(
+                        DomainGoal::DownstreamType(self_ty.clone()),
+                        Some(DomainGoal::DownstreamType(type_param)),
+                    );
+                }
+            }
+        });
+    }
+}
+
+impl<I: Interner> ToProgramClauses<I> for FnDefDatum<I> {
+    /// Given the following function definition: `fn bar<T>() where T: Eq`, generate:
+    ///
+    /// ```notrust
+    /// -- Rule WellFormed-Type
+    /// forall<T> {
+    ///     WF(bar<T>) :- WF(T: Eq)
+    /// }
+    ///
+    /// -- Rule Implied-Bound-From-Type
+    /// forall<T> {
+    ///     FromEnv(T: Eq) :- FromEnv(bar<T>).
+    /// }
+    ///
+    /// forall<T> {
+    ///     IsFullyVisible(bar<T>) :- IsFullyVisible(T).
+    /// }
+    /// ```
+    #[instrument(level = "debug", skip(builder))]
+    fn to_program_clauses(
+        &self,
+        builder: &mut ClauseBuilder<'_, I>,
+        _environment: &Environment<I>,
+    ) {
+        let interner = builder.interner();
+        let binders = self.binders.map_ref(|b| &b.where_clauses).cloned();
+
+        builder.push_binders(binders, |builder, where_clauses| {
+            let ty = TyKind::FnDef(self.id, builder.substitution_in_scope()).intern(interner);
+
+            well_formed_program_clauses(builder, ty.clone(), where_clauses.iter());
+
+            implied_bounds_program_clauses(builder, &ty, where_clauses.iter());
+
+            fully_visible_program_clauses(builder, ty, &builder.substitution_in_scope());
+        });
+    }
+}
+
+impl<I: Interner> ToProgramClauses<I> for TraitDatum<I> {
+    /// Given the following trait declaration: `trait Ord<T> where Self: Eq<T> { ... }`, generate:
+    ///
+    /// ```notrust
+    /// -- Rule WellFormed-TraitRef
+    /// forall<Self, T> {
+    ///    WF(Self: Ord<T>) :- Implemented(Self: Ord<T>), WF(Self: Eq<T>).
+    /// }
+    /// ```
+    ///
+    /// and the reverse rules:
+    ///
+    /// ```notrust
+    /// -- Rule Implemented-From-Env
+    /// forall<Self, T> {
+    ///    (Self: Ord<T>) :- FromEnv(Self: Ord<T>).
+    /// }
+    ///
+    /// -- Rule Implied-Bound-From-Trait
+    /// forall<Self, T> {
+    ///     FromEnv(Self: Eq<T>) :- FromEnv(Self: Ord<T>).
+    /// }
+    /// ```
+    ///
+    /// As specified in the orphan rules, if a trait is not marked `#[upstream]`, the current crate
+    /// can implement it for any type. To represent that, we generate:
+    ///
+    /// ```notrust
+    /// // `Ord<T>` would not be `#[upstream]` when compiling `std`
+    /// forall<Self, T> { LocalImplAllowed(Self: Ord<T>). }
+    /// ```
+    ///
+    /// For traits that are `#[upstream]` (i.e. not in the current crate), the orphan rules dictate
+    /// that impls are allowed as long as at least one type parameter is local and each type
+    /// prior to that is fully visible. That means that each type prior to the first local
+    /// type cannot contain any of the type parameters of the impl.
+    ///
+    /// This rule is fairly complex, so we expand it and generate a program clause for each
+    /// possible case. This is represented as follows:
+    ///
+    /// ```notrust
+    /// // for `#[upstream] trait Foo<T, U, V> where Self: Eq<T> { ... }`
+    /// forall<Self, T, U, V> {
+    ///     LocalImplAllowed(Self: Foo<T, U, V>) :- IsLocal(Self).
+    /// }
+    ///
+    /// forall<Self, T, U, V> {
+    ///     LocalImplAllowed(Self: Foo<T, U, V>) :-
+    ///         IsFullyVisible(Self),
+    ///         IsLocal(T).
+    /// }
+    ///
+    /// forall<Self, T, U, V> {
+    ///     LocalImplAllowed(Self: Foo<T, U, V>) :-
+    ///         IsFullyVisible(Self),
+    ///         IsFullyVisible(T),
+    ///         IsLocal(U).
+    /// }
+    ///
+    /// forall<Self, T, U, V> {
+    ///     LocalImplAllowed(Self: Foo<T, U, V>) :-
+    ///         IsFullyVisible(Self),
+    ///         IsFullyVisible(T),
+    ///         IsFullyVisible(U),
+    ///         IsLocal(V).
+    /// }
+    /// ```
+    ///
+    /// The overlap check uses compatible { ... } mode to ensure that it accounts for impls that
+    /// may exist in some other *compatible* world. For every upstream trait, we add a rule to
+    /// account for the fact that upstream crates are able to compatibly add impls of upstream
+    /// traits for upstream types.
+    ///
+    /// ```notrust
+    /// // For `#[upstream] trait Foo<T, U, V> where Self: Eq<T> { ... }`
+    /// forall<Self, T, U, V> {
+    ///     Implemented(Self: Foo<T, U, V>) :-
+    ///         Implemented(Self: Eq<T>), // where clauses
+    ///         Compatible,               // compatible modality
+    ///         IsUpstream(Self),
+    ///         IsUpstream(T),
+    ///         IsUpstream(U),
+    ///         IsUpstream(V),
+    ///         CannotProve.              // returns ambiguous
+    /// }
+    /// ```
+    ///
+    /// In certain situations, this is too restrictive. Consider the following code:
+    ///
+    /// ```notrust
+    /// /* In crate std */
+    /// trait Sized { }
+    /// struct str { }
+    ///
+    /// /* In crate bar (depends on std) */
+    /// trait Bar { }
+    /// impl Bar for str { }
+    /// impl<T> Bar for T where T: Sized { }
+    /// ```
+    ///
+    /// Here, because of the rules we've defined, these two impls overlap. The std crate is
+    /// upstream to bar, and thus it is allowed to compatibly implement Sized for str. If str
+    /// can implement Sized in a compatible future, these two impls definitely overlap since the
+    /// second impl covers all types that implement Sized.
+    ///
+    /// The solution we've got right now is to mark Sized as "fundamental" when it is defined.
+    /// This signals to the Rust compiler that it can rely on the fact that str does not
+    /// implement Sized in all contexts. A consequence of this is that we can no longer add an
+    /// implementation of Sized compatibly for str. This is the trade off you make when defining
+    /// a fundamental trait.
+    ///
+    /// To implement fundamental traits, we simply just do not add the rule above that allows
+    /// upstream types to implement upstream traits. Fundamental traits are not allowed to
+    /// compatibly do that.
+    fn to_program_clauses(&self, builder: &mut ClauseBuilder<'_, I>, environment: &Environment<I>) {
+        let interner = builder.interner();
+        let binders = self.binders.map_ref(|b| &b.where_clauses).cloned();
+        builder.push_binders(binders, |builder, where_clauses| {
+            let trait_ref = chalk_ir::TraitRef {
+                trait_id: self.id,
+                substitution: builder.substitution_in_scope(),
+            };
+
+            builder.push_clause(
+                trait_ref.clone().well_formed(),
+                where_clauses
+                    .iter()
+                    .cloned()
+                    .map(|qwc| qwc.into_well_formed_goal(interner))
+                    .casted::<Goal<_>>(interner)
+                    .chain(Some(trait_ref.clone().cast(interner))),
+            );
+
+            // The number of parameters will always be at least 1
+            // because of the Self parameter that is automatically
+            // added to every trait. This is important because
+            // otherwise the added program clauses would not have any
+            // conditions.
+            let type_parameters: Vec<_> = trait_ref.type_parameters(interner).collect();
+
+            if environment.has_compatible_clause(interner) {
+                // Note: even though we do check for a `Compatible` clause here,
+                // we also keep it as a condition for the clauses below, purely
+                // for logical consistency. But really, it's not needed and could be
+                // removed.
+
+                // Drop trait can't have downstream implementation because it can only
+                // be implemented with the same genericity as the struct definition,
+                // i.e. Drop implementation for `struct S<T: Eq> {}` is forced to be
+                // `impl Drop<T: Eq> for S<T> { ... }`. That means that orphan rules
+                // prevent Drop from being implemented in downstream crates.
+                if self.well_known != Some(WellKnownTrait::Drop) {
+                    // Add all cases for potential downstream impls that could exist
+                    for i in 0..type_parameters.len() {
+                        builder.push_clause(
+                            trait_ref.clone(),
+                            where_clauses
+                                .iter()
+                                .cloned()
+                                .casted(interner)
+                                .chain(iter::once(DomainGoal::Compatible.cast(interner)))
+                                .chain((0..i).map(|j| {
+                                    DomainGoal::IsFullyVisible(type_parameters[j].clone())
+                                        .cast(interner)
+                                }))
+                                .chain(iter::once(
+                                    DomainGoal::DownstreamType(type_parameters[i].clone())
+                                        .cast(interner),
+                                ))
+                                .chain(iter::once(GoalData::CannotProve.intern(interner))),
+                        );
+                    }
+                }
+
+                // Fundamental traits can be reasoned about negatively without any ambiguity, so no
+                // need for this rule if the trait is fundamental.
+                if !self.flags.fundamental {
+                    builder.push_clause(
+                        trait_ref.clone(),
+                        where_clauses
+                            .iter()
+                            .cloned()
+                            .casted(interner)
+                            .chain(iter::once(DomainGoal::Compatible.cast(interner)))
+                            .chain(
+                                trait_ref
+                                    .type_parameters(interner)
+                                    .map(|ty| DomainGoal::IsUpstream(ty).cast(interner)),
+                            )
+                            .chain(iter::once(GoalData::CannotProve.intern(interner))),
+                    );
+                }
+            }
+
+            // Orphan rules:
+            if !self.flags.upstream {
+                // Impls for traits declared locally always pass the impl rules
+                builder.push_fact(DomainGoal::LocalImplAllowed(trait_ref.clone()));
+            } else {
+                // Impls for remote traits must have a local type in the right place
+                for i in 0..type_parameters.len() {
+                    builder.push_clause(
+                        DomainGoal::LocalImplAllowed(trait_ref.clone()),
+                        (0..i)
+                            .map(|j| DomainGoal::IsFullyVisible(type_parameters[j].clone()))
+                            .chain(Some(DomainGoal::IsLocal(type_parameters[i].clone()))),
+                    );
+                }
+            }
+
+            // Reverse implied bound rules: given (e.g.) `trait Foo: Bar + Baz`,
+            // we create rules like:
+            //
+            // ```
+            // FromEnv(T: Bar) :- FromEnv(T: Foo)
+            // ```
+            //
+            // and
+            //
+            // ```
+            // FromEnv(T: Baz) :- FromEnv(T: Foo)
+            // ```
+            for qwc in where_clauses {
+                builder.push_binders(qwc, |builder, wc| {
+                    builder.push_clause(
+                        wc.into_from_env_goal(interner),
+                        Some(trait_ref.clone().from_env()),
+                    );
+                });
+            }
+
+            // Finally, for every trait `Foo` we make a rule
+            //
+            // ```
+            // Implemented(T: Foo) :- FromEnv(T: Foo)
+            // ```
+            builder.push_clause(trait_ref.clone(), Some(trait_ref.from_env()));
+        });
+    }
+}
+
+impl<I: Interner> ToProgramClauses<I> for AssociatedTyDatum<I> {
+    /// For each associated type, we define the "projection
+    /// equality" rules. There are always two; one for a successful normalization,
+    /// and one for the "fallback" notion of equality.
+    ///
+    /// Given: (here, `'a` and `T` represent zero or more parameters)
+    ///
+    /// ```notrust
+    /// trait Foo {
+    ///     type Assoc<'a, T>: Bounds where WC;
+    /// }
+    /// ```
+    ///
+    /// we generate the 'fallback' rule:
+    ///
+    /// ```notrust
+    /// -- Rule AliasEq-Placeholder
+    /// forall<Self, 'a, T> {
+    ///     AliasEq(<Self as Foo>::Assoc<'a, T> = (Foo::Assoc<'a, T>)<Self>).
+    /// }
+    /// ```
+    ///
+    /// and
+    ///
+    /// ```notrust
+    /// -- Rule AliasEq-Normalize
+    /// forall<Self, 'a, T, U> {
+    ///     AliasEq(<T as Foo>::Assoc<'a, T> = U) :-
+    ///         Normalize(<T as Foo>::Assoc -> U).
+    /// }
+    /// ```
+    ///
+    /// We used to generate an "elaboration" rule like this:
+    ///
+    /// ```notrust
+    /// forall<T> {
+    ///     T: Foo :- exists<U> { AliasEq(<T as Foo>::Assoc = U) }.
+    /// }
+    /// ```
+    ///
+    /// but this caused problems with the recursive solver. In
+    /// particular, whenever normalization is possible, we cannot
+    /// solve that projection uniquely, since we can now elaborate
+    /// `AliasEq` to fallback *or* normalize it. So instead we
+    /// handle this kind of reasoning through the `FromEnv` predicate.
+    ///
+    /// We also generate rules specific to WF requirements and implied bounds:
+    ///
+    /// ```notrust
+    /// -- Rule WellFormed-AssocTy
+    /// forall<Self, 'a, T> {
+    ///     WellFormed((Foo::Assoc)<Self, 'a, T>) :- WellFormed(Self: Foo), WellFormed(WC).
+    /// }
+    ///
+    /// -- Rule Implied-WC-From-AssocTy
+    /// forall<Self, 'a, T> {
+    ///     FromEnv(WC) :- FromEnv((Foo::Assoc)<Self, 'a, T>).
+    /// }
+    ///
+    /// -- Rule Implied-Bound-From-AssocTy
+    /// forall<Self, 'a, T> {
+    ///     FromEnv(<Self as Foo>::Assoc<'a,T>: Bounds) :- FromEnv(Self: Foo), WC.
+    /// }
+    ///
+    /// -- Rule Implied-Trait-From-AssocTy
+    /// forall<Self,'a, T> {
+    ///     FromEnv(Self: Foo) :- FromEnv((Foo::Assoc)<Self, 'a,T>).
+    /// }
+    /// ```
+    fn to_program_clauses(
+        &self,
+        builder: &mut ClauseBuilder<'_, I>,
+        _environment: &Environment<I>,
+    ) {
+        let interner = builder.interner();
+        let binders = self.binders.clone();
+        builder.push_binders(
+            binders,
+            |builder,
+             AssociatedTyDatumBound {
+                 where_clauses,
+                 bounds,
+             }| {
+                let substitution = builder.substitution_in_scope();
+
+                let projection = ProjectionTy {
+                    associated_ty_id: self.id,
+                    substitution: substitution.clone(),
+                };
+                let projection_ty = AliasTy::Projection(projection.clone()).intern(interner);
+
+                // Retrieve the trait ref embedding the associated type
+                let trait_ref = builder.db.trait_ref_from_projection(&projection);
+
+                // Construct an application from the projection. So if we have `<T as Iterator>::Item`,
+                // we would produce `(Iterator::Item)<T>`.
+                let ty = TyKind::AssociatedType(self.id, substitution).intern(interner);
+
+                let projection_eq = AliasEq {
+                    alias: AliasTy::Projection(projection.clone()),
+                    ty: ty.clone(),
+                };
+
+                // Fallback rule. The solver uses this to move between the projection
+                // and placeholder type.
+                //
+                //    forall<Self> {
+                //        AliasEq(<Self as Foo>::Assoc = (Foo::Assoc)<Self>).
+                //    }
+                builder.push_fact_with_priority(projection_eq, None, ClausePriority::Low);
+
+                // Well-formedness of projection type.
+                //
+                //    forall<Self> {
+                //        WellFormed((Foo::Assoc)<Self>) :- WellFormed(Self: Foo), WellFormed(WC).
+                //    }
+                builder.push_clause(
+                    WellFormed::Ty(ty.clone()),
+                    iter::once(WellFormed::Trait(trait_ref.clone()).cast::<Goal<_>>(interner))
+                        .chain(
+                            where_clauses
+                                .iter()
+                                .cloned()
+                                .map(|qwc| qwc.into_well_formed_goal(interner))
+                                .casted(interner),
+                        ),
+                );
+
+                // Assuming well-formedness of projection type means we can assume
+                // the trait ref as well. Mostly used in function bodies.
+                //
+                //    forall<Self> {
+                //        FromEnv(Self: Foo) :- FromEnv((Foo::Assoc)<Self>).
+                //    }
+                builder.push_clause(FromEnv::Trait(trait_ref.clone()), Some(ty.from_env()));
+
+                // Reverse rule for where clauses.
+                //
+                //    forall<Self> {
+                //        FromEnv(WC) :- FromEnv((Foo::Assoc)<Self>).
+                //    }
+                //
+                // This is really a family of clauses, one for each where clause.
+                for qwc in &where_clauses {
+                    builder.push_binders(qwc.clone(), |builder, wc| {
+                        builder.push_clause(
+                            wc.into_from_env_goal(interner),
+                            Some(FromEnv::Ty(ty.clone())),
+                        );
+                    });
+                }
+
+                // Reverse rule for implied bounds.
+                //
+                //    forall<Self> {
+                //        FromEnv(<Self as Foo>::Assoc: Bounds) :- FromEnv(Self: Foo), WC
+                //    }
+                for quantified_bound in bounds {
+                    builder.push_binders(quantified_bound, |builder, bound| {
+                        for wc in bound.into_where_clauses(interner, projection_ty.clone()) {
+                            builder.push_clause(
+                                wc.into_from_env_goal(interner),
+                                iter::once(
+                                    FromEnv::Trait(trait_ref.clone()).cast::<Goal<_>>(interner),
+                                )
+                                .chain(where_clauses.iter().cloned().casted(interner)),
+                            );
+                        }
+                    });
+                }
+
+                // add new type parameter U
+                builder.push_bound_ty(|builder, ty| {
+                    // `Normalize(<T as Foo>::Assoc -> U)`
+                    let normalize = Normalize {
+                        alias: AliasTy::Projection(projection.clone()),
+                        ty: ty.clone(),
+                    };
+
+                    // `AliasEq(<T as Foo>::Assoc = U)`
+                    let projection_eq = AliasEq {
+                        alias: AliasTy::Projection(projection),
+                        ty,
+                    };
+
+                    // Projection equality rule from above.
+                    //
+                    //    forall<T, U> {
+                    //        AliasEq(<T as Foo>::Assoc = U) :-
+                    //            Normalize(<T as Foo>::Assoc -> U).
+                    //    }
+                    builder.push_clause(projection_eq, Some(normalize));
+                });
+            },
+        );
+    }
+}
diff --git a/vendor/chalk-solve-0.87.0/src/clauses/super_traits.rs b/vendor/chalk-solve-0.87.0/src/clauses/super_traits.rs
new file mode 100644
index 000000000..3110b03e8
--- /dev/null
+++ b/vendor/chalk-solve-0.87.0/src/clauses/super_traits.rs
@@ -0,0 +1,118 @@
+use rustc_hash::FxHashSet;
+
+use super::builder::ClauseBuilder;
+use crate::RustIrDatabase;
+use chalk_ir::{
+    fold::shift::Shift, interner::Interner, Binders, BoundVar, DebruijnIndex, TraitId, TraitRef,
+    WhereClause,
+};
+
+/// Generate `Implemented` clauses for `dyn Trait` and opaque types. We need to generate
+/// `Implemented` clauses for all super traits, and for each trait we require
+/// its where clauses. (See #203.)
+pub(super) fn push_trait_super_clauses<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    builder: &mut ClauseBuilder<'_, I>,
+    trait_ref: TraitRef<I>,
+) {
+    let interner = db.interner();
+    // Given`trait SuperTrait: WC`, which is a super trait
+    // of `Trait` (including actually just being the same trait);
+    // then we want to push
+    // - for `dyn Trait`:
+    //     `Implemented(dyn Trait: SuperTrait) :- WC`.
+    // - for placeholder `!T` of `opaque type T: Trait = HiddenTy`:
+    //     `Implemented(!T: SuperTrait) :- WC`
+
+    let super_trait_refs =
+        super_traits(db, trait_ref.trait_id).substitute(interner, &trait_ref.substitution);
+
+    for q_super_trait_ref in super_trait_refs {
+        builder.push_binders(q_super_trait_ref.clone(), |builder, super_trait_ref| {
+            let trait_datum = db.trait_datum(super_trait_ref.trait_id);
+            let wc = trait_datum
+                .where_clauses()
+                .cloned()
+                .substitute(interner, &super_trait_ref.substitution);
+            builder.push_clause(super_trait_ref, wc);
+        });
+    }
+}
+
+pub fn super_traits<I: Interner>(
+    db: &dyn RustIrDatabase<I>,
+    trait_id: TraitId<I>,
+) -> Binders<Vec<Binders<TraitRef<I>>>> {
+    let interner = db.interner();
+    let mut seen_traits = FxHashSet::default();
+    let trait_datum = db.trait_datum(trait_id);
+    let trait_ref = Binders::empty(
+        db.interner(),
+        TraitRef {
+            trait_id,
+            substitution: trait_datum
+                .binders
+                .identity_substitution(interner)
+                .shifted_in(interner),
+        },
+    );
+    let mut trait_refs = Vec::new();
+    go(db, trait_ref, &mut seen_traits, &mut trait_refs);
+
+    fn go<I: Interner>(
+        db: &dyn RustIrDatabase<I>,
+        trait_ref: Binders<TraitRef<I>>,
+        seen_traits: &mut FxHashSet<TraitId<I>>,
+        trait_refs: &mut Vec<Binders<TraitRef<I>>>,
+    ) {
+        let interner = db.interner();
+        let trait_id = trait_ref.skip_binders().trait_id;
+        // Avoid cycles
+        if !seen_traits.insert(trait_id) {
+            return;
+        }
+        trait_refs.push(trait_ref.clone());
+        let trait_datum = db.trait_datum(trait_id);
+        let super_trait_refs = trait_datum
+            .binders
+            .map_ref(|td| {
+                td.where_clauses
+                    .iter()
+                    .filter_map(|qwc| {
+                        qwc.as_ref().filter_map(|wc| match wc {
+                            WhereClause::Implemented(tr) => {
+                                let self_ty = tr.self_type_parameter(db.interner());
+
+                                // We're looking for where clauses
+                                // of the form `Self: Trait`. That's
+                                // ^1.0 because we're one binder in.
+                                if self_ty.bound_var(db.interner())
+                                    != Some(BoundVar::new(DebruijnIndex::ONE, 0))
+                                {
+                                    return None;
+                                }
+                                Some(tr.clone())
+                            }
+                            WhereClause::AliasEq(_) => None,
+                            WhereClause::LifetimeOutlives(..) => None,
+                            WhereClause::TypeOutlives(..) => None,
+                        })
+                    })
+                    .collect::<Vec<_>>()
+            })
+            // we skip binders on the trait_ref here and add them to the binders
+            // on the trait ref in the loop below. We could probably avoid this if
+            // we could turn the `Binders<Vec<>>` into a `Vec<Binders<>>` easily.
+            .substitute(db.interner(), &trait_ref.skip_binders().substitution);
+        for q_super_trait_ref in super_trait_refs {
+            // So now we need to combine the binders of trait_ref with the
+            // binders of super_trait_ref.
+            let actual_binders = Binders::new(trait_ref.binders.clone(), q_super_trait_ref);
+            let q_super_trait_ref = actual_binders.fuse_binders(interner);
+            go(db, q_super_trait_ref, seen_traits, trait_refs);
+        }
+        seen_traits.remove(&trait_id);
+    }
+
+    Binders::new(trait_datum.binders.binders.clone(), trait_refs)
+}