diff options
Diffstat (limited to 'vendor/chalk-solve-0.87.0/src/clauses/builtin_traits')
8 files changed, 1052 insertions, 0 deletions
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()); + } + + _ => (), + } +} |