diff options
Diffstat (limited to 'vendor/chalk-solve-0.87.0/src/clauses')
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) { + ¶meters_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) +} |