diff options
Diffstat (limited to 'compiler/rustc_traits/src/chalk')
| -rw-r--r-- | compiler/rustc_traits/src/chalk/db.rs | 588 | ||||
| -rw-r--r-- | compiler/rustc_traits/src/chalk/lowering.rs | 886 | ||||
| -rw-r--r-- | compiler/rustc_traits/src/chalk/mod.rs | 229 |
3 files changed, 1703 insertions, 0 deletions
diff --git a/compiler/rustc_traits/src/chalk/db.rs b/compiler/rustc_traits/src/chalk/db.rs new file mode 100644 index 00000000000..4c8be8eb610 --- /dev/null +++ b/compiler/rustc_traits/src/chalk/db.rs @@ -0,0 +1,588 @@ +//! Provides the `RustIrDatabase` implementation for `chalk-solve` +//! +//! The purpose of the `chalk_solve::RustIrDatabase` is to get data about +//! specific types, such as bounds, where clauses, or fields. This file contains +//! the minimal logic to assemble the types for `chalk-solve` by calling out to +//! either the `TyCtxt` (for information about types) or +//! `crate::chalk::lowering` (to lower rustc types into Chalk types). + +use rustc_middle::traits::ChalkRustInterner as RustInterner; +use rustc_middle::ty::subst::{InternalSubsts, Subst, SubstsRef}; +use rustc_middle::ty::{self, AssocItemContainer, AssocKind, TyCtxt}; + +use rustc_hir::def_id::DefId; + +use rustc_span::symbol::sym; + +use std::fmt; +use std::sync::Arc; + +use crate::chalk::lowering::LowerInto; + +pub struct RustIrDatabase<'tcx> { + pub tcx: TyCtxt<'tcx>, + pub interner: RustInterner<'tcx>, +} + +impl fmt::Debug for RustIrDatabase<'_> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "RustIrDatabase") + } +} + +impl<'tcx> chalk_solve::RustIrDatabase<RustInterner<'tcx>> for RustIrDatabase<'tcx> { + fn interner(&self) -> &RustInterner<'tcx> { + &self.interner + } + + fn associated_ty_data( + &self, + assoc_type_id: chalk_ir::AssocTypeId<RustInterner<'tcx>>, + ) -> Arc<chalk_solve::rust_ir::AssociatedTyDatum<RustInterner<'tcx>>> { + let def_id = assoc_type_id.0; + let assoc_item = self.tcx.associated_item(def_id); + let trait_def_id = match assoc_item.container { + AssocItemContainer::TraitContainer(def_id) => def_id, + _ => unimplemented!("Not possible??"), + }; + match assoc_item.kind { + AssocKind::Type => {} + _ => unimplemented!("Not possible??"), + } + let bound_vars = bound_vars_for_item(self.tcx, def_id); + let binders = binders_for(&self.interner, bound_vars); + // FIXME(chalk): this really isn't right I don't think. The functions + // for GATs are a bit hard to figure out. Are these supposed to be where + // clauses or bounds? + let predicates = self.tcx.predicates_defined_on(def_id).predicates; + let where_clauses: Vec<_> = predicates + .iter() + .map(|(wc, _)| wc.subst(self.tcx, &bound_vars)) + .filter_map(|wc| LowerInto::<Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>>>::lower_into(wc, &self.interner)).collect(); + + Arc::new(chalk_solve::rust_ir::AssociatedTyDatum { + trait_id: chalk_ir::TraitId(trait_def_id), + id: assoc_type_id, + name: (), + binders: chalk_ir::Binders::new( + binders, + chalk_solve::rust_ir::AssociatedTyDatumBound { bounds: vec![], where_clauses }, + ), + }) + } + + fn trait_datum( + &self, + trait_id: chalk_ir::TraitId<RustInterner<'tcx>>, + ) -> Arc<chalk_solve::rust_ir::TraitDatum<RustInterner<'tcx>>> { + let def_id = trait_id.0; + let trait_def = self.tcx.trait_def(def_id); + + let bound_vars = bound_vars_for_item(self.tcx, def_id); + let binders = binders_for(&self.interner, bound_vars); + let predicates = self.tcx.predicates_defined_on(def_id).predicates; + let where_clauses: Vec<_> = predicates + .iter() + .map(|(wc, _)| wc.subst(self.tcx, &bound_vars)) + .filter_map(|wc| LowerInto::<Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>>>::lower_into(wc, &self.interner)).collect(); + let associated_ty_ids: Vec<_> = self + .tcx + .associated_items(def_id) + .in_definition_order() + .filter(|i| i.kind == AssocKind::Type) + .map(|i| chalk_ir::AssocTypeId(i.def_id)) + .collect(); + + let well_known = + if self.tcx.lang_items().sized_trait().map(|t| def_id == t).unwrap_or(false) { + Some(chalk_solve::rust_ir::WellKnownTrait::Sized) + } else if self.tcx.lang_items().copy_trait().map(|t| def_id == t).unwrap_or(false) { + Some(chalk_solve::rust_ir::WellKnownTrait::Copy) + } else if self.tcx.lang_items().clone_trait().map(|t| def_id == t).unwrap_or(false) { + Some(chalk_solve::rust_ir::WellKnownTrait::Clone) + } else if self.tcx.lang_items().drop_trait().map(|t| def_id == t).unwrap_or(false) { + Some(chalk_solve::rust_ir::WellKnownTrait::Drop) + } else if self.tcx.lang_items().fn_trait().map(|t| def_id == t).unwrap_or(false) { + Some(chalk_solve::rust_ir::WellKnownTrait::Fn) + } else if self.tcx.lang_items().fn_once_trait().map(|t| def_id == t).unwrap_or(false) { + Some(chalk_solve::rust_ir::WellKnownTrait::FnOnce) + } else if self.tcx.lang_items().fn_mut_trait().map(|t| def_id == t).unwrap_or(false) { + Some(chalk_solve::rust_ir::WellKnownTrait::FnMut) + } else { + None + }; + Arc::new(chalk_solve::rust_ir::TraitDatum { + id: trait_id, + binders: chalk_ir::Binders::new( + binders, + chalk_solve::rust_ir::TraitDatumBound { where_clauses }, + ), + flags: chalk_solve::rust_ir::TraitFlags { + auto: trait_def.has_auto_impl, + marker: trait_def.is_marker, + upstream: !def_id.is_local(), + fundamental: self.tcx.has_attr(def_id, sym::fundamental), + non_enumerable: true, + coinductive: false, + }, + associated_ty_ids, + well_known, + }) + } + + fn adt_datum( + &self, + adt_id: chalk_ir::AdtId<RustInterner<'tcx>>, + ) -> Arc<chalk_solve::rust_ir::AdtDatum<RustInterner<'tcx>>> { + let adt_def = adt_id.0; + + let bound_vars = bound_vars_for_item(self.tcx, adt_def.did); + let binders = binders_for(&self.interner, bound_vars); + + let predicates = self.tcx.predicates_of(adt_def.did).predicates; + let where_clauses: Vec<_> = predicates + .iter() + .map(|(wc, _)| wc.subst(self.tcx, bound_vars)) + .filter_map(|wc| LowerInto::<Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>>>::lower_into(wc, &self.interner)) + .collect(); + let fields = match adt_def.adt_kind() { + ty::AdtKind::Struct | ty::AdtKind::Union => { + let variant = adt_def.non_enum_variant(); + variant + .fields + .iter() + .map(|field| { + self.tcx + .type_of(field.did) + .subst(self.tcx, bound_vars) + .lower_into(&self.interner) + }) + .collect() + } + // FIXME(chalk): handle enums; force_impl_for requires this + ty::AdtKind::Enum => vec![], + }; + let struct_datum = Arc::new(chalk_solve::rust_ir::AdtDatum { + id: adt_id, + binders: chalk_ir::Binders::new( + binders, + chalk_solve::rust_ir::AdtDatumBound { fields, where_clauses }, + ), + flags: chalk_solve::rust_ir::AdtFlags { + upstream: !adt_def.did.is_local(), + fundamental: adt_def.is_fundamental(), + phantom_data: adt_def.is_phantom_data(), + }, + }); + struct_datum + } + + fn fn_def_datum( + &self, + fn_def_id: chalk_ir::FnDefId<RustInterner<'tcx>>, + ) -> Arc<chalk_solve::rust_ir::FnDefDatum<RustInterner<'tcx>>> { + let def_id = fn_def_id.0; + let bound_vars = bound_vars_for_item(self.tcx, def_id); + let binders = binders_for(&self.interner, bound_vars); + + let predicates = self.tcx.predicates_defined_on(def_id).predicates; + let where_clauses: Vec<_> = predicates + .iter() + .map(|(wc, _)| wc.subst(self.tcx, &bound_vars)) + .filter_map(|wc| LowerInto::<Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>>>::lower_into(wc, &self.interner)).collect(); + + let sig = self.tcx.fn_sig(def_id); + let inputs_and_output = sig.inputs_and_output(); + let (inputs_and_output, iobinders, _) = crate::chalk::lowering::collect_bound_vars( + &self.interner, + self.tcx, + &inputs_and_output, + ); + + let argument_types = inputs_and_output[..inputs_and_output.len() - 1] + .iter() + .map(|t| t.subst(self.tcx, &bound_vars).lower_into(&self.interner)) + .collect(); + + let return_type = inputs_and_output[inputs_and_output.len() - 1] + .subst(self.tcx, &bound_vars) + .lower_into(&self.interner); + + let bound = chalk_solve::rust_ir::FnDefDatumBound { + inputs_and_output: chalk_ir::Binders::new( + iobinders, + chalk_solve::rust_ir::FnDefInputsAndOutputDatum { argument_types, return_type }, + ), + where_clauses, + }; + Arc::new(chalk_solve::rust_ir::FnDefDatum { + id: fn_def_id, + abi: sig.abi(), + binders: chalk_ir::Binders::new(binders, bound), + }) + } + + fn impl_datum( + &self, + impl_id: chalk_ir::ImplId<RustInterner<'tcx>>, + ) -> Arc<chalk_solve::rust_ir::ImplDatum<RustInterner<'tcx>>> { + let def_id = impl_id.0; + let bound_vars = bound_vars_for_item(self.tcx, def_id); + let binders = binders_for(&self.interner, bound_vars); + + let trait_ref = self.tcx.impl_trait_ref(def_id).expect("not an impl"); + let trait_ref = trait_ref.subst(self.tcx, bound_vars); + + let predicates = self.tcx.predicates_of(def_id).predicates; + let where_clauses: Vec<_> = predicates + .iter() + .map(|(wc, _)| wc.subst(self.tcx, bound_vars)) + .filter_map(|wc| LowerInto::<Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>>>::lower_into(wc, &self.interner)).collect(); + + let value = chalk_solve::rust_ir::ImplDatumBound { + trait_ref: trait_ref.lower_into(&self.interner), + where_clauses, + }; + + Arc::new(chalk_solve::rust_ir::ImplDatum { + polarity: chalk_solve::rust_ir::Polarity::Positive, + binders: chalk_ir::Binders::new(binders, value), + impl_type: chalk_solve::rust_ir::ImplType::Local, + associated_ty_value_ids: vec![], + }) + } + + fn impls_for_trait( + &self, + trait_id: chalk_ir::TraitId<RustInterner<'tcx>>, + parameters: &[chalk_ir::GenericArg<RustInterner<'tcx>>], + ) -> Vec<chalk_ir::ImplId<RustInterner<'tcx>>> { + let def_id = trait_id.0; + + // FIXME(chalk): use TraitDef::for_each_relevant_impl, but that will + // require us to be able to interconvert `Ty<'tcx>`, and we're + // not there yet. + + let all_impls = self.tcx.all_impls(def_id); + let matched_impls = all_impls.filter(|impl_def_id| { + use chalk_ir::could_match::CouldMatch; + let trait_ref = self.tcx.impl_trait_ref(*impl_def_id).unwrap(); + let bound_vars = bound_vars_for_item(self.tcx, *impl_def_id); + + let self_ty = trait_ref.self_ty(); + let self_ty = self_ty.subst(self.tcx, bound_vars); + let lowered_ty = self_ty.lower_into(&self.interner); + + parameters[0].assert_ty_ref(&self.interner).could_match(&self.interner, &lowered_ty) + }); + + let impls = matched_impls.map(chalk_ir::ImplId).collect(); + impls + } + + fn impl_provided_for( + &self, + auto_trait_id: chalk_ir::TraitId<RustInterner<'tcx>>, + adt_id: chalk_ir::AdtId<RustInterner<'tcx>>, + ) -> bool { + let trait_def_id = auto_trait_id.0; + let adt_def = adt_id.0; + let all_impls = self.tcx.all_impls(trait_def_id); + for impl_def_id in all_impls { + let trait_ref = self.tcx.impl_trait_ref(impl_def_id).unwrap(); + let self_ty = trait_ref.self_ty(); + match self_ty.kind { + ty::Adt(impl_adt_def, _) => { + if impl_adt_def == adt_def { + return true; + } + } + _ => {} + } + } + false + } + + fn associated_ty_value( + &self, + associated_ty_id: chalk_solve::rust_ir::AssociatedTyValueId<RustInterner<'tcx>>, + ) -> Arc<chalk_solve::rust_ir::AssociatedTyValue<RustInterner<'tcx>>> { + let def_id = associated_ty_id.0; + let assoc_item = self.tcx.associated_item(def_id); + let impl_id = match assoc_item.container { + AssocItemContainer::TraitContainer(def_id) => def_id, + _ => unimplemented!("Not possible??"), + }; + match assoc_item.kind { + AssocKind::Type => {} + _ => unimplemented!("Not possible??"), + } + let bound_vars = bound_vars_for_item(self.tcx, def_id); + let binders = binders_for(&self.interner, bound_vars); + let ty = self.tcx.type_of(def_id); + + Arc::new(chalk_solve::rust_ir::AssociatedTyValue { + impl_id: chalk_ir::ImplId(impl_id), + associated_ty_id: chalk_ir::AssocTypeId(def_id), + value: chalk_ir::Binders::new( + binders, + chalk_solve::rust_ir::AssociatedTyValueBound { ty: ty.lower_into(&self.interner) }, + ), + }) + } + + fn custom_clauses(&self) -> Vec<chalk_ir::ProgramClause<RustInterner<'tcx>>> { + vec![] + } + + fn local_impls_to_coherence_check( + &self, + _trait_id: chalk_ir::TraitId<RustInterner<'tcx>>, + ) -> Vec<chalk_ir::ImplId<RustInterner<'tcx>>> { + unimplemented!() + } + + fn opaque_ty_data( + &self, + opaque_ty_id: chalk_ir::OpaqueTyId<RustInterner<'tcx>>, + ) -> Arc<chalk_solve::rust_ir::OpaqueTyDatum<RustInterner<'tcx>>> { + let bound_vars = bound_vars_for_item(self.tcx, opaque_ty_id.0); + let binders = binders_for(&self.interner, bound_vars); + let predicates = self.tcx.predicates_defined_on(opaque_ty_id.0).predicates; + let where_clauses: Vec<_> = predicates + .iter() + .map(|(wc, _)| wc.subst(self.tcx, &bound_vars)) + .filter_map(|wc| LowerInto::<Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>>>::lower_into(wc, &self.interner)).collect(); + + let value = chalk_solve::rust_ir::OpaqueTyDatumBound { + bounds: chalk_ir::Binders::new(binders, where_clauses), + }; + Arc::new(chalk_solve::rust_ir::OpaqueTyDatum { + opaque_ty_id, + bound: chalk_ir::Binders::new(chalk_ir::VariableKinds::new(&self.interner), value), + }) + } + + /// Since Chalk can't handle all Rust types currently, we have to handle + /// some specially for now. Over time, these `Some` returns will change to + /// `None` and eventually this function will be removed. + fn force_impl_for( + &self, + well_known: chalk_solve::rust_ir::WellKnownTrait, + ty: &chalk_ir::TyData<RustInterner<'tcx>>, + ) -> Option<bool> { + use chalk_ir::TyData::*; + match well_known { + chalk_solve::rust_ir::WellKnownTrait::Sized => match ty { + Apply(apply) => match apply.name { + chalk_ir::TypeName::Adt(chalk_ir::AdtId(adt_def)) => match adt_def.adt_kind() { + ty::AdtKind::Struct | ty::AdtKind::Union => None, + ty::AdtKind::Enum => { + let constraint = self.tcx.adt_sized_constraint(adt_def.did); + if !constraint.0.is_empty() { unimplemented!() } else { Some(true) } + } + }, + _ => None, + }, + Dyn(_) + | Alias(_) + | Placeholder(_) + | Function(_) + | InferenceVar(_, _) + | BoundVar(_) => None, + }, + chalk_solve::rust_ir::WellKnownTrait::Copy + | chalk_solve::rust_ir::WellKnownTrait::Clone => match ty { + Apply(apply) => match apply.name { + chalk_ir::TypeName::Adt(chalk_ir::AdtId(adt_def)) => match adt_def.adt_kind() { + ty::AdtKind::Struct | ty::AdtKind::Union => None, + ty::AdtKind::Enum => { + let constraint = self.tcx.adt_sized_constraint(adt_def.did); + if !constraint.0.is_empty() { unimplemented!() } else { Some(true) } + } + }, + _ => None, + }, + Dyn(_) + | Alias(_) + | Placeholder(_) + | Function(_) + | InferenceVar(_, _) + | BoundVar(_) => None, + }, + chalk_solve::rust_ir::WellKnownTrait::Drop => None, + chalk_solve::rust_ir::WellKnownTrait::Fn => None, + chalk_solve::rust_ir::WellKnownTrait::FnMut => None, + chalk_solve::rust_ir::WellKnownTrait::FnOnce => None, + chalk_solve::rust_ir::WellKnownTrait::Unsize => None, + } + } + + fn program_clauses_for_env( + &self, + environment: &chalk_ir::Environment<RustInterner<'tcx>>, + ) -> chalk_ir::ProgramClauses<RustInterner<'tcx>> { + chalk_solve::program_clauses_for_env(self, environment) + } + + fn well_known_trait_id( + &self, + well_known_trait: chalk_solve::rust_ir::WellKnownTrait, + ) -> Option<chalk_ir::TraitId<RustInterner<'tcx>>> { + use chalk_solve::rust_ir::WellKnownTrait::*; + let def_id = match well_known_trait { + Sized => self.tcx.lang_items().sized_trait(), + Copy => self.tcx.lang_items().copy_trait(), + Clone => self.tcx.lang_items().clone_trait(), + Drop => self.tcx.lang_items().drop_trait(), + Fn => self.tcx.lang_items().fn_trait(), + FnMut => self.tcx.lang_items().fn_mut_trait(), + FnOnce => self.tcx.lang_items().fn_once_trait(), + Unsize => self.tcx.lang_items().unsize_trait(), + }; + def_id.map(chalk_ir::TraitId) + } + + fn is_object_safe(&self, trait_id: chalk_ir::TraitId<RustInterner<'tcx>>) -> bool { + self.tcx.is_object_safe(trait_id.0) + } + + fn hidden_opaque_type( + &self, + _id: chalk_ir::OpaqueTyId<RustInterner<'tcx>>, + ) -> chalk_ir::Ty<RustInterner<'tcx>> { + // FIXME(chalk): actually get hidden ty + self.tcx.mk_ty(ty::Tuple(self.tcx.intern_substs(&[]))).lower_into(&self.interner) + } + + fn closure_kind( + &self, + _closure_id: chalk_ir::ClosureId<RustInterner<'tcx>>, + substs: &chalk_ir::Substitution<RustInterner<'tcx>>, + ) -> chalk_solve::rust_ir::ClosureKind { + let kind = &substs.parameters(&self.interner)[substs.len(&self.interner) - 3]; + match kind.assert_ty_ref(&self.interner).data(&self.interner) { + chalk_ir::TyData::Apply(apply) => match apply.name { + chalk_ir::TypeName::Scalar(scalar) => match scalar { + chalk_ir::Scalar::Int(int_ty) => match int_ty { + chalk_ir::IntTy::I8 => chalk_solve::rust_ir::ClosureKind::Fn, + chalk_ir::IntTy::I16 => chalk_solve::rust_ir::ClosureKind::FnMut, + chalk_ir::IntTy::I32 => chalk_solve::rust_ir::ClosureKind::FnOnce, + _ => bug!("bad closure kind"), + }, + _ => bug!("bad closure kind"), + }, + _ => bug!("bad closure kind"), + }, + _ => bug!("bad closure kind"), + } + } + + fn closure_inputs_and_output( + &self, + _closure_id: chalk_ir::ClosureId<RustInterner<'tcx>>, + substs: &chalk_ir::Substitution<RustInterner<'tcx>>, + ) -> chalk_ir::Binders<chalk_solve::rust_ir::FnDefInputsAndOutputDatum<RustInterner<'tcx>>> + { + let sig = &substs.parameters(&self.interner)[substs.len(&self.interner) - 2]; + match sig.assert_ty_ref(&self.interner).data(&self.interner) { + chalk_ir::TyData::Function(f) => { + let substitution = f.substitution.parameters(&self.interner); + let return_type = + substitution.last().unwrap().assert_ty_ref(&self.interner).clone(); + // Closure arguments are tupled + let argument_tuple = substitution[0].assert_ty_ref(&self.interner); + let argument_types = match argument_tuple.data(&self.interner) { + chalk_ir::TyData::Apply(apply) => match apply.name { + chalk_ir::TypeName::Tuple(_) => apply + .substitution + .iter(&self.interner) + .map(|arg| arg.assert_ty_ref(&self.interner)) + .cloned() + .collect(), + _ => bug!("Expecting closure FnSig args to be tupled."), + }, + _ => bug!("Expecting closure FnSig args to be tupled."), + }; + + chalk_ir::Binders::new( + chalk_ir::VariableKinds::from( + &self.interner, + (0..f.num_binders).map(|_| chalk_ir::VariableKind::Lifetime), + ), + chalk_solve::rust_ir::FnDefInputsAndOutputDatum { argument_types, return_type }, + ) + } + _ => panic!("Invalid sig."), + } + } + + fn closure_upvars( + &self, + _closure_id: chalk_ir::ClosureId<RustInterner<'tcx>>, + substs: &chalk_ir::Substitution<RustInterner<'tcx>>, + ) -> chalk_ir::Binders<chalk_ir::Ty<RustInterner<'tcx>>> { + let inputs_and_output = self.closure_inputs_and_output(_closure_id, substs); + let tuple = substs.parameters(&self.interner).last().unwrap().assert_ty_ref(&self.interner); + inputs_and_output.map_ref(|_| tuple.clone()) + } + + fn closure_fn_substitution( + &self, + _closure_id: chalk_ir::ClosureId<RustInterner<'tcx>>, + substs: &chalk_ir::Substitution<RustInterner<'tcx>>, + ) -> chalk_ir::Substitution<RustInterner<'tcx>> { + let substitution = &substs.parameters(&self.interner)[0..substs.len(&self.interner) - 3]; + chalk_ir::Substitution::from(&self.interner, substitution) + } +} + +/// Creates a `InternalSubsts` that maps each generic parameter to a higher-ranked +/// var bound at index `0`. For types, we use a `BoundVar` index equal to +/// the type parameter index. For regions, we use the `BoundRegion::BrNamed` +/// variant (which has a `DefId`). +fn bound_vars_for_item(tcx: TyCtxt<'tcx>, def_id: DefId) -> SubstsRef<'tcx> { + InternalSubsts::for_item(tcx, def_id, |param, substs| match param.kind { + ty::GenericParamDefKind::Type { .. } => tcx + .mk_ty(ty::Bound( + ty::INNERMOST, + ty::BoundTy { + var: ty::BoundVar::from(param.index), + kind: ty::BoundTyKind::Param(param.name), + }, + )) + .into(), + + ty::GenericParamDefKind::Lifetime => tcx + .mk_region(ty::RegionKind::ReLateBound( + ty::INNERMOST, + ty::BoundRegion::BrAnon(substs.len() as u32), + )) + .into(), + + ty::GenericParamDefKind::Const => tcx + .mk_const(ty::Const { + val: ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from(param.index)), + ty: tcx.type_of(param.def_id), + }) + .into(), + }) +} + +fn binders_for<'tcx>( + interner: &RustInterner<'tcx>, + bound_vars: SubstsRef<'tcx>, +) -> chalk_ir::VariableKinds<RustInterner<'tcx>> { + chalk_ir::VariableKinds::from( + interner, + bound_vars.iter().map(|arg| match arg.unpack() { + ty::subst::GenericArgKind::Lifetime(_re) => chalk_ir::VariableKind::Lifetime, + ty::subst::GenericArgKind::Type(_ty) => { + chalk_ir::VariableKind::Ty(chalk_ir::TyKind::General) + } + ty::subst::GenericArgKind::Const(c) => { + chalk_ir::VariableKind::Const(c.ty.lower_into(interner)) + } + }), + ) +} diff --git a/compiler/rustc_traits/src/chalk/lowering.rs b/compiler/rustc_traits/src/chalk/lowering.rs new file mode 100644 index 00000000000..a043fa3f4c8 --- /dev/null +++ b/compiler/rustc_traits/src/chalk/lowering.rs @@ -0,0 +1,886 @@ +//! Contains the logic to lower rustc types into Chalk types +//! +//! In many cases there is a 1:1 relationship between a rustc type and a Chalk type. +//! For example, a `SubstsRef` maps almost directly to a `Substitution`. In some +//! other cases, such as `Param`s, there is no Chalk type, so we have to handle +//! accordingly. +//! +//! ## `Ty` lowering +//! Much of the `Ty` lowering is 1:1 with Chalk. (Or will be eventually). A +//! helpful table for what types lower to what can be found in the +//! [Chalk book](http://rust-lang.github.io/chalk/book/types/rust_types.html). +//! The most notable difference lies with `Param`s. To convert from rustc to +//! Chalk, we eagerly and deeply convert `Param`s to placeholders (in goals) or +//! bound variables (for clause generation through functions in `db`). +//! +//! ## `Region` lowering +//! Regions are handled in rustc and Chalk is quite differently. In rustc, there +//! is a difference between "early bound" and "late bound" regions, where only +//! the late bound regions have a `DebruijnIndex`. Moreover, in Chalk all +//! regions (Lifetimes) have an associated index. In rustc, only `BrAnon`s have +//! an index, whereas `BrNamed` don't. In order to lower regions to Chalk, we +//! convert all regions into `BrAnon` late-bound regions. +//! +//! ## `Const` lowering +//! Chalk doesn't handle consts currently, so consts are currently lowered to +//! an empty tuple. +//! +//! ## Bound variable collection +//! Another difference between rustc and Chalk lies in the handling of binders. +//! Chalk requires that we store the bound parameter kinds, whereas rustc does +//! not. To lower anything wrapped in a `Binder`, we first deeply find any bound +//! variables from the current `Binder`. + +use rustc_middle::traits::{ + ChalkEnvironmentAndGoal, ChalkEnvironmentClause, ChalkRustInterner as RustInterner, +}; +use rustc_middle::ty::fold::TypeFolder; +use rustc_middle::ty::subst::{GenericArg, GenericArgKind, SubstsRef}; +use rustc_middle::ty::{ + self, Binder, BoundRegion, Region, RegionKind, Ty, TyCtxt, TyKind, TypeFoldable, TypeVisitor, +}; +use rustc_span::def_id::DefId; + +use std::collections::btree_map::{BTreeMap, Entry}; + +use chalk_ir::fold::shift::Shift; + +/// Essentially an `Into` with a `&RustInterner` parameter +crate trait LowerInto<'tcx, T> { + /// Lower a rustc construct (e.g., `ty::TraitPredicate`) to a chalk type, consuming `self`. + fn lower_into(self, interner: &RustInterner<'tcx>) -> T; +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::Substitution<RustInterner<'tcx>>> for SubstsRef<'tcx> { + fn lower_into( + self, + interner: &RustInterner<'tcx>, + ) -> chalk_ir::Substitution<RustInterner<'tcx>> { + chalk_ir::Substitution::from(interner, self.iter().map(|s| s.lower_into(interner))) + } +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::AliasTy<RustInterner<'tcx>>> for ty::ProjectionTy<'tcx> { + fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::AliasTy<RustInterner<'tcx>> { + chalk_ir::AliasTy::Projection(chalk_ir::ProjectionTy { + associated_ty_id: chalk_ir::AssocTypeId(self.item_def_id), + substitution: self.substs.lower_into(interner), + }) + } +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::InEnvironment<chalk_ir::Goal<RustInterner<'tcx>>>> + for ChalkEnvironmentAndGoal<'tcx> +{ + fn lower_into( + self, + interner: &RustInterner<'tcx>, + ) -> chalk_ir::InEnvironment<chalk_ir::Goal<RustInterner<'tcx>>> { + let clauses = self.environment.into_iter().filter_map(|clause| match clause { + ChalkEnvironmentClause::Predicate(predicate) => { + // FIXME(chalk): forall + match predicate.bound_atom(interner.tcx).skip_binder() { + ty::PredicateAtom::Trait(predicate, _) => { + let predicate = ty::Binder::bind(predicate); + let (predicate, binders, _named_regions) = + collect_bound_vars(interner, interner.tcx, &predicate); + + Some( + chalk_ir::ProgramClauseData(chalk_ir::Binders::new( + binders, + chalk_ir::ProgramClauseImplication { + consequence: chalk_ir::DomainGoal::FromEnv( + chalk_ir::FromEnv::Trait( + predicate.trait_ref.lower_into(interner), + ), + ), + conditions: chalk_ir::Goals::new(interner), + priority: chalk_ir::ClausePriority::High, + }, + )) + .intern(interner), + ) + } + ty::PredicateAtom::RegionOutlives(predicate) => { + let predicate = ty::Binder::bind(predicate); + let (predicate, binders, _named_regions) = + collect_bound_vars(interner, interner.tcx, &predicate); + + Some( + chalk_ir::ProgramClauseData(chalk_ir::Binders::new( + binders, + chalk_ir::ProgramClauseImplication { + consequence: chalk_ir::DomainGoal::Holds( + chalk_ir::WhereClause::LifetimeOutlives( + chalk_ir::LifetimeOutlives { + a: predicate.0.lower_into(interner), + b: predicate.1.lower_into(interner), + }, + ), + ), + conditions: chalk_ir::Goals::new(interner), + priority: chalk_ir::ClausePriority::High, + }, + )) + .intern(interner), + ) + } + // FIXME(chalk): need to add TypeOutlives + ty::PredicateAtom::TypeOutlives(_) => None, + ty::PredicateAtom::Projection(predicate) => { + let predicate = ty::Binder::bind(predicate); + let (predicate, binders, _named_regions) = + collect_bound_vars(interner, interner.tcx, &predicate); + + Some( + chalk_ir::ProgramClauseData(chalk_ir::Binders::new( + binders, + chalk_ir::ProgramClauseImplication { + consequence: chalk_ir::DomainGoal::Holds( + chalk_ir::WhereClause::AliasEq( + predicate.lower_into(interner), + ), + ), + conditions: chalk_ir::Goals::new(interner), + priority: chalk_ir::ClausePriority::High, + }, + )) + .intern(interner), + ) + } + ty::PredicateAtom::WellFormed(..) + | ty::PredicateAtom::ObjectSafe(..) + | ty::PredicateAtom::ClosureKind(..) + | ty::PredicateAtom::Subtype(..) + | ty::PredicateAtom::ConstEvaluatable(..) + | ty::PredicateAtom::ConstEquate(..) => { + bug!("unexpected predicate {}", predicate) + } + } + } + ChalkEnvironmentClause::TypeFromEnv(ty) => Some( + chalk_ir::ProgramClauseData(chalk_ir::Binders::new( + chalk_ir::VariableKinds::new(interner), + chalk_ir::ProgramClauseImplication { + consequence: chalk_ir::DomainGoal::FromEnv(chalk_ir::FromEnv::Ty( + ty.lower_into(interner).shifted_in(interner), + )), + conditions: chalk_ir::Goals::new(interner), + priority: chalk_ir::ClausePriority::High, + }, + )) + .intern(interner), + ), + }); + + let goal: chalk_ir::GoalData<RustInterner<'tcx>> = self.goal.lower_into(&interner); + chalk_ir::InEnvironment { + environment: chalk_ir::Environment { + clauses: chalk_ir::ProgramClauses::from(&interner, clauses), + }, + goal: goal.intern(&interner), + } + } +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::GoalData<RustInterner<'tcx>>> for ty::Predicate<'tcx> { + fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::GoalData<RustInterner<'tcx>> { + // FIXME(chalk): forall + match self.bound_atom(interner.tcx).skip_binder() { + ty::PredicateAtom::Trait(predicate, _) => { + ty::Binder::bind(predicate).lower_into(interner) + } + ty::PredicateAtom::RegionOutlives(predicate) => { + let predicate = ty::Binder::bind(predicate); + let (predicate, binders, _named_regions) = + collect_bound_vars(interner, interner.tcx, &predicate); + + chalk_ir::GoalData::Quantified( + chalk_ir::QuantifierKind::ForAll, + chalk_ir::Binders::new( + binders, + chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::Holds( + chalk_ir::WhereClause::LifetimeOutlives(chalk_ir::LifetimeOutlives { + a: predicate.0.lower_into(interner), + b: predicate.1.lower_into(interner), + }), + )) + .intern(interner), + ), + ) + } + // FIXME(chalk): TypeOutlives + ty::PredicateAtom::TypeOutlives(_predicate) => { + chalk_ir::GoalData::All(chalk_ir::Goals::new(interner)) + } + ty::PredicateAtom::Projection(predicate) => { + ty::Binder::bind(predicate).lower_into(interner) + } + ty::PredicateAtom::WellFormed(arg) => match arg.unpack() { + GenericArgKind::Type(ty) => match ty.kind { + // FIXME(chalk): In Chalk, a placeholder is WellFormed if it + // `FromEnv`. However, when we "lower" Params, we don't update + // the environment. + ty::Placeholder(..) => chalk_ir::GoalData::All(chalk_ir::Goals::new(interner)), + + _ => { + let (ty, binders, _named_regions) = + collect_bound_vars(interner, interner.tcx, &ty::Binder::bind(ty)); + + chalk_ir::GoalData::Quantified( + chalk_ir::QuantifierKind::ForAll, + chalk_ir::Binders::new( + binders, + chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::WellFormed( + chalk_ir::WellFormed::Ty(ty.lower_into(interner)), + )) + .intern(interner), + ), + ) + } + }, + // FIXME(chalk): handle well formed consts + GenericArgKind::Const(..) => { + chalk_ir::GoalData::All(chalk_ir::Goals::new(interner)) + } + GenericArgKind::Lifetime(lt) => bug!("unexpect well formed predicate: {:?}", lt), + }, + + ty::PredicateAtom::ObjectSafe(t) => chalk_ir::GoalData::DomainGoal( + chalk_ir::DomainGoal::ObjectSafe(chalk_ir::TraitId(t)), + ), + + // FIXME(chalk): other predicates + // + // We can defer this, but ultimately we'll want to express + // some of these in terms of chalk operations. + ty::PredicateAtom::ClosureKind(..) + | ty::PredicateAtom::Subtype(..) + | ty::PredicateAtom::ConstEvaluatable(..) + | ty::PredicateAtom::ConstEquate(..) => { + chalk_ir::GoalData::All(chalk_ir::Goals::new(interner)) + } + } + } +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::TraitRef<RustInterner<'tcx>>> + for rustc_middle::ty::TraitRef<'tcx> +{ + fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::TraitRef<RustInterner<'tcx>> { + chalk_ir::TraitRef { + trait_id: chalk_ir::TraitId(self.def_id), + substitution: self.substs.lower_into(interner), + } + } +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::GoalData<RustInterner<'tcx>>> + for ty::PolyTraitPredicate<'tcx> +{ + fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::GoalData<RustInterner<'tcx>> { + let (ty, binders, _named_regions) = collect_bound_vars(interner, interner.tcx, &self); + + chalk_ir::GoalData::Quantified( + chalk_ir::QuantifierKind::ForAll, + chalk_ir::Binders::new( + binders, + chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::Holds( + chalk_ir::WhereClause::Implemented(ty.trait_ref.lower_into(interner)), + )) + .intern(interner), + ), + ) + } +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::AliasEq<RustInterner<'tcx>>> + for rustc_middle::ty::ProjectionPredicate<'tcx> +{ + fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::AliasEq<RustInterner<'tcx>> { + chalk_ir::AliasEq { + ty: self.ty.lower_into(interner), + alias: self.projection_ty.lower_into(interner), + } + } +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::GoalData<RustInterner<'tcx>>> + for ty::PolyProjectionPredicate<'tcx> +{ + fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::GoalData<RustInterner<'tcx>> { + let (ty, binders, _named_regions) = collect_bound_vars(interner, interner.tcx, &self); + + chalk_ir::GoalData::Quantified( + chalk_ir::QuantifierKind::ForAll, + chalk_ir::Binders::new( + binders, + chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::Holds( + chalk_ir::WhereClause::AliasEq(ty.lower_into(interner)), + )) + .intern(interner), + ), + ) + } +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::Ty<RustInterner<'tcx>>> for Ty<'tcx> { + fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::Ty<RustInterner<'tcx>> { + use chalk_ir::TyData; + use rustc_ast as ast; + use TyKind::*; + + let empty = || chalk_ir::Substitution::empty(interner); + let struct_ty = + |def_id| chalk_ir::TypeName::Adt(chalk_ir::AdtId(interner.tcx.adt_def(def_id))); + let apply = |name, substitution| { + TyData::Apply(chalk_ir::ApplicationTy { name, substitution }).intern(interner) + }; + let int = |i| apply(chalk_ir::TypeName::Scalar(chalk_ir::Scalar::Int(i)), empty()); + let uint = |i| apply(chalk_ir::TypeName::Scalar(chalk_ir::Scalar::Uint(i)), empty()); + let float = |f| apply(chalk_ir::TypeName::Scalar(chalk_ir::Scalar::Float(f)), empty()); + + match self.kind { + Bool => apply(chalk_ir::TypeName::Scalar(chalk_ir::Scalar::Bool), empty()), + Char => apply(chalk_ir::TypeName::Scalar(chalk_ir::Scalar::Char), empty()), + Int(ty) => match ty { + ast::IntTy::Isize => int(chalk_ir::IntTy::Isize), + ast::IntTy::I8 => int(chalk_ir::IntTy::I8), + ast::IntTy::I16 => int(chalk_ir::IntTy::I16), + ast::IntTy::I32 => int(chalk_ir::IntTy::I32), + ast::IntTy::I64 => int(chalk_ir::IntTy::I64), + ast::IntTy::I128 => int(chalk_ir::IntTy::I128), + }, + Uint(ty) => match ty { + ast::UintTy::Usize => uint(chalk_ir::UintTy::Usize), + ast::UintTy::U8 => uint(chalk_ir::UintTy::U8), + ast::UintTy::U16 => uint(chalk_ir::UintTy::U16), + ast::UintTy::U32 => uint(chalk_ir::UintTy::U32), + ast::UintTy::U64 => uint(chalk_ir::UintTy::U64), + ast::UintTy::U128 => uint(chalk_ir::UintTy::U128), + }, + Float(ty) => match ty { + ast::FloatTy::F32 => float(chalk_ir::FloatTy::F32), + ast::FloatTy::F64 => float(chalk_ir::FloatTy::F64), + }, + Adt(def, substs) => apply(struct_ty(def.did), substs.lower_into(interner)), + Foreign(_def_id) => unimplemented!(), + Str => apply(chalk_ir::TypeName::Str, empty()), + Array(ty, len) => { + let value = match len.val { + ty::ConstKind::Value(val) => { + chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst { interned: val }) + } + ty::ConstKind::Bound(db, bound) => { + chalk_ir::ConstValue::BoundVar(chalk_ir::BoundVar::new( + chalk_ir::DebruijnIndex::new(db.as_u32()), + bound.index(), + )) + } + _ => unimplemented!("Const not implemented. {:?}", len.val), + }; + apply( + chalk_ir::TypeName::Array, + chalk_ir::Substitution::from( + interner, + &[ + chalk_ir::GenericArgData::Ty(ty.lower_into(interner)).intern(interner), + chalk_ir::GenericArgData::Const( + chalk_ir::ConstData { ty: len.ty.lower_into(interner), value } + .intern(interner), + ) + .intern(interner), + ], + ), + ) + } + Slice(ty) => apply( + chalk_ir::TypeName::Slice, + chalk_ir::Substitution::from1( + interner, + chalk_ir::GenericArgData::Ty(ty.lower_into(interner)).intern(interner), + ), + ), + RawPtr(ptr) => { + let name = match ptr.mutbl { + ast::Mutability::Mut => chalk_ir::TypeName::Raw(chalk_ir::Mutability::Mut), + ast::Mutability::Not => chalk_ir::TypeName::Raw(chalk_ir::Mutability::Not), + }; + apply(name, chalk_ir::Substitution::from1(interner, ptr.ty.lower_into(interner))) + } + Ref(region, ty, mutability) => { + let name = match mutability { + ast::Mutability::Mut => chalk_ir::TypeName::Ref(chalk_ir::Mutability::Mut), + ast::Mutability::Not => chalk_ir::TypeName::Ref(chalk_ir::Mutability::Not), + }; + apply( + name, + chalk_ir::Substitution::from( + interner, + &[ + chalk_ir::GenericArgData::Lifetime(region.lower_into(interner)) + .intern(interner), + chalk_ir::GenericArgData::Ty(ty.lower_into(interner)).intern(interner), + ], + ), + ) + } + FnDef(def_id, substs) => apply( + chalk_ir::TypeName::FnDef(chalk_ir::FnDefId(def_id)), + substs.lower_into(interner), + ), + FnPtr(sig) => { + let (inputs_and_outputs, binders, _named_regions) = + collect_bound_vars(interner, interner.tcx, &sig.inputs_and_output()); + TyData::Function(chalk_ir::Fn { + num_binders: binders.len(interner), + substitution: chalk_ir::Substitution::from( + interner, + inputs_and_outputs.iter().map(|ty| { + chalk_ir::GenericArgData::Ty(ty.lower_into(interner)).intern(interner) + }), + ), + }) + .intern(interner) + } + Dynamic(predicates, region) => TyData::Dyn(chalk_ir::DynTy { + bounds: predicates.lower_into(interner), + lifetime: region.lower_into(interner), + }) + .intern(interner), + Closure(def_id, substs) => apply( + chalk_ir::TypeName::Closure(chalk_ir::ClosureId(def_id)), + substs.lower_into(interner), + ), + Generator(_def_id, _substs, _) => unimplemented!(), + GeneratorWitness(_) => unimplemented!(), + Never => apply(chalk_ir::TypeName::Never, empty()), + Tuple(substs) => { + apply(chalk_ir::TypeName::Tuple(substs.len()), substs.lower_into(interner)) + } + Projection(proj) => TyData::Alias(proj.lower_into(interner)).intern(interner), + Opaque(def_id, substs) => { + TyData::Alias(chalk_ir::AliasTy::Opaque(chalk_ir::OpaqueTy { + opaque_ty_id: chalk_ir::OpaqueTyId(def_id), + substitution: substs.lower_into(interner), + })) + .intern(interner) + } + // This should have been done eagerly prior to this, and all Params + // should have been substituted to placeholders + Param(_) => panic!("Lowering Param when not expected."), + Bound(db, bound) => TyData::BoundVar(chalk_ir::BoundVar::new( + chalk_ir::DebruijnIndex::new(db.as_u32()), + bound.var.index(), + )) + .intern(interner), + Placeholder(_placeholder) => TyData::Placeholder(chalk_ir::PlaceholderIndex { + ui: chalk_ir::UniverseIndex { counter: _placeholder.universe.as_usize() }, + idx: _placeholder.name.as_usize(), + }) + .intern(interner), + Infer(_infer) => unimplemented!(), + Error(_) => apply(chalk_ir::TypeName::Error, empty()), + } + } +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::Lifetime<RustInterner<'tcx>>> for Region<'tcx> { + fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::Lifetime<RustInterner<'tcx>> { + use rustc_middle::ty::RegionKind::*; + + match self { + ReEarlyBound(_) => { + panic!("Should have already been substituted."); + } + ReLateBound(db, br) => match br { + ty::BoundRegion::BrAnon(var) => { + chalk_ir::LifetimeData::BoundVar(chalk_ir::BoundVar::new( + chalk_ir::DebruijnIndex::new(db.as_u32()), + *var as usize, + )) + .intern(interner) + } + ty::BoundRegion::BrNamed(_def_id, _name) => unimplemented!(), + ty::BrEnv => unimplemented!(), + }, + ReFree(_) => unimplemented!(), + // FIXME(chalk): need to handle ReStatic + ReStatic => unimplemented!(), + ReVar(_) => unimplemented!(), + RePlaceholder(placeholder_region) => { + chalk_ir::LifetimeData::Placeholder(chalk_ir::PlaceholderIndex { + ui: chalk_ir::UniverseIndex { counter: placeholder_region.universe.index() }, + idx: 0, + }) + .intern(interner) + } + ReEmpty(_) => unimplemented!(), + // FIXME(chalk): need to handle ReErased + ReErased => unimplemented!(), + } + } +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::GenericArg<RustInterner<'tcx>>> for GenericArg<'tcx> { + fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::GenericArg<RustInterner<'tcx>> { + match self.unpack() { + ty::subst::GenericArgKind::Type(ty) => { + chalk_ir::GenericArgData::Ty(ty.lower_into(interner)) + } + ty::subst::GenericArgKind::Lifetime(lifetime) => { + chalk_ir::GenericArgData::Lifetime(lifetime.lower_into(interner)) + } + ty::subst::GenericArgKind::Const(_) => chalk_ir::GenericArgData::Ty( + chalk_ir::TyData::Apply(chalk_ir::ApplicationTy { + name: chalk_ir::TypeName::Tuple(0), + substitution: chalk_ir::Substitution::empty(interner), + }) + .intern(interner), + ), + } + .intern(interner) + } +} + +// We lower into an Option here since there are some predicates which Chalk +// doesn't have a representation for yet (as a `WhereClause`), but are so common +// that we just are accepting the unsoundness for now. The `Option` will +// eventually be removed. +impl<'tcx> LowerInto<'tcx, Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>>> + for ty::Predicate<'tcx> +{ + fn lower_into( + self, + interner: &RustInterner<'tcx>, + ) -> Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>> { + // FIXME(chalk): forall + match self.bound_atom(interner.tcx).skip_binder() { + ty::PredicateAtom::Trait(predicate, _) => { + let predicate = ty::Binder::bind(predicate); + let (predicate, binders, _named_regions) = + collect_bound_vars(interner, interner.tcx, &predicate); + + Some(chalk_ir::Binders::new( + binders, + chalk_ir::WhereClause::Implemented(predicate.trait_ref.lower_into(interner)), + )) + } + ty::PredicateAtom::RegionOutlives(predicate) => { + let predicate = ty::Binder::bind(predicate); + let (predicate, binders, _named_regions) = + collect_bound_vars(interner, interner.tcx, &predicate); + + Some(chalk_ir::Binders::new( + binders, + chalk_ir::WhereClause::LifetimeOutlives(chalk_ir::LifetimeOutlives { + a: predicate.0.lower_into(interner), + b: predicate.1.lower_into(interner), + }), + )) + } + ty::PredicateAtom::TypeOutlives(_predicate) => None, + ty::PredicateAtom::Projection(_predicate) => None, + ty::PredicateAtom::WellFormed(_ty) => None, + + ty::PredicateAtom::ObjectSafe(..) + | ty::PredicateAtom::ClosureKind(..) + | ty::PredicateAtom::Subtype(..) + | ty::PredicateAtom::ConstEvaluatable(..) + | ty::PredicateAtom::ConstEquate(..) => bug!("unexpected predicate {}", &self), + } + } +} + +impl<'tcx> LowerInto<'tcx, chalk_ir::Binders<chalk_ir::QuantifiedWhereClauses<RustInterner<'tcx>>>> + for Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>> +{ + fn lower_into( + self, + interner: &RustInterner<'tcx>, + ) -> chalk_ir::Binders<chalk_ir::QuantifiedWhereClauses<RustInterner<'tcx>>> { + let (predicates, binders, _named_regions) = + collect_bound_vars(interner, interner.tcx, &self); + let where_clauses = predicates.into_iter().map(|predicate| match predicate { + ty::ExistentialPredicate::Trait(ty::ExistentialTraitRef { def_id, substs }) => { + chalk_ir::Binders::new( + chalk_ir::VariableKinds::new(interner), + chalk_ir::WhereClause::Implemented(chalk_ir::TraitRef { + trait_id: chalk_ir::TraitId(def_id), + substitution: substs.lower_into(interner), + }), + ) + } + ty::ExistentialPredicate::Projection(_predicate) => unimplemented!(), + ty::ExistentialPredicate::AutoTrait(def_id) => chalk_ir::Binders::new( + chalk_ir::VariableKinds::new(interner), + chalk_ir::WhereClause::Implemented(chalk_ir::TraitRef { + trait_id: chalk_ir::TraitId(def_id), + substitution: chalk_ir::Substitution::empty(interner), + }), + ), + }); + let value = chalk_ir::QuantifiedWhereClauses::from(interner, where_clauses); + chalk_ir::Binders::new(binders, value) + } +} + +/// To collect bound vars, we have to do two passes. In the first pass, we +/// collect all `BoundRegion`s and `ty::Bound`s. In the second pass, we then +/// replace `BrNamed` into `BrAnon`. The two separate passes are important, +/// since we can only replace `BrNamed` with `BrAnon`s with indices *after* all +/// "real" `BrAnon`s. +/// +/// It's important to note that because of prior substitution, we may have +/// late-bound regions, even outside of fn contexts, since this is the best way +/// to prep types for chalk lowering. +crate fn collect_bound_vars<'a, 'tcx, T: TypeFoldable<'tcx>>( + interner: &RustInterner<'tcx>, + tcx: TyCtxt<'tcx>, + ty: &'a Binder<T>, +) -> (T, chalk_ir::VariableKinds<RustInterner<'tcx>>, BTreeMap<DefId, u32>) { + let mut bound_vars_collector = BoundVarsCollector::new(); + ty.as_ref().skip_binder().visit_with(&mut bound_vars_collector); + let mut parameters = bound_vars_collector.parameters; + let named_parameters: BTreeMap<DefId, u32> = bound_vars_collector + .named_parameters + .into_iter() + .enumerate() + .map(|(i, def_id)| (def_id, (i + parameters.len()) as u32)) + .collect(); + + let mut bound_var_substitutor = NamedBoundVarSubstitutor::new(tcx, &named_parameters); + let new_ty = ty.as_ref().skip_binder().fold_with(&mut bound_var_substitutor); + + for var in named_parameters.values() { + parameters.insert(*var, chalk_ir::VariableKind::Lifetime); + } + + (0..parameters.len()).for_each(|i| { + parameters + .get(&(i as u32)) + .or_else(|| bug!("Skipped bound var index: ty={:?}, parameters={:?}", ty, parameters)); + }); + + let binders = chalk_ir::VariableKinds::from(interner, parameters.into_iter().map(|(_, v)| v)); + + (new_ty, binders, named_parameters) +} + +crate struct BoundVarsCollector<'tcx> { + binder_index: ty::DebruijnIndex, + crate parameters: BTreeMap<u32, chalk_ir::VariableKind<RustInterner<'tcx>>>, + crate named_parameters: Vec<DefId>, +} + +impl<'tcx> BoundVarsCollector<'tcx> { + crate fn new() -> Self { + BoundVarsCollector { + binder_index: ty::INNERMOST, + parameters: BTreeMap::new(), + named_parameters: vec![], + } + } +} + +impl<'tcx> TypeVisitor<'tcx> for BoundVarsCollector<'tcx> { + fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool { + self.binder_index.shift_in(1); + let result = t.super_visit_with(self); + self.binder_index.shift_out(1); + result + } + + fn visit_ty(&mut self, t: Ty<'tcx>) -> bool { + match t.kind { + ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => { + match self.parameters.entry(bound_ty.var.as_u32()) { + Entry::Vacant(entry) => { + entry.insert(chalk_ir::VariableKind::Ty(chalk_ir::TyKind::General)); + } + Entry::Occupied(entry) => match entry.get() { + chalk_ir::VariableKind::Ty(_) => {} + _ => panic!(), + }, + } + } + + _ => (), + }; + + t.super_visit_with(self) + } + + fn visit_region(&mut self, r: Region<'tcx>) -> bool { + match r { + ty::ReLateBound(index, br) if *index == self.binder_index => match br { + ty::BoundRegion::BrNamed(def_id, _name) => { + if self.named_parameters.iter().find(|d| *d == def_id).is_none() { + self.named_parameters.push(*def_id); + } + } + + ty::BoundRegion::BrAnon(var) => match self.parameters.entry(*var) { + Entry::Vacant(entry) => { + entry.insert(chalk_ir::VariableKind::Lifetime); + } + Entry::Occupied(entry) => match entry.get() { + chalk_ir::VariableKind::Lifetime => {} + _ => panic!(), + }, + }, + + ty::BrEnv => unimplemented!(), + }, + + ty::ReEarlyBound(_re) => { + // FIXME(chalk): jackh726 - I think we should always have already + // substituted away `ReEarlyBound`s for `ReLateBound`s, but need to confirm. + unimplemented!(); + } + + _ => (), + }; + + r.super_visit_with(self) + } +} + +/// This is used to replace `BoundRegion::BrNamed` with `BoundRegion::BrAnon`. +/// Note: we assume that we will always have room for more bound vars. (i.e. we +/// won't ever hit the `u32` limit in `BrAnon`s). +struct NamedBoundVarSubstitutor<'a, 'tcx> { + tcx: TyCtxt<'tcx>, + binder_index: ty::DebruijnIndex, + named_parameters: &'a BTreeMap<DefId, u32>, +} + +impl<'a, 'tcx> NamedBoundVarSubstitutor<'a, 'tcx> { + fn new(tcx: TyCtxt<'tcx>, named_parameters: &'a BTreeMap<DefId, u32>) -> Self { + NamedBoundVarSubstitutor { tcx, binder_index: ty::INNERMOST, named_parameters } + } +} + +impl<'a, 'tcx> TypeFolder<'tcx> for NamedBoundVarSubstitutor<'a, 'tcx> { + fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { + self.tcx + } + + fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> Binder<T> { + self.binder_index.shift_in(1); + let result = t.super_fold_with(self); + self.binder_index.shift_out(1); + result + } + + fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { + t.super_fold_with(self) + } + + fn fold_region(&mut self, r: Region<'tcx>) -> Region<'tcx> { + match r { + ty::ReLateBound(index, br) if *index == self.binder_index => match br { + ty::BoundRegion::BrNamed(def_id, _name) => { + match self.named_parameters.get(def_id) { + Some(idx) => { + return self.tcx.mk_region(RegionKind::ReLateBound( + *index, + BoundRegion::BrAnon(*idx), + )); + } + None => panic!("Missing `BrNamed`."), + } + } + ty::BrEnv => unimplemented!(), + ty::BoundRegion::BrAnon(_) => {} + }, + _ => (), + }; + + r.super_fold_with(self) + } +} + +/// Used to substitute `Param`s with placeholders. We do this since Chalk +/// have a notion of `Param`s. +crate struct ParamsSubstitutor<'tcx> { + tcx: TyCtxt<'tcx>, + binder_index: ty::DebruijnIndex, + list: Vec<rustc_middle::ty::ParamTy>, + crate params: rustc_data_structures::fx::FxHashMap<usize, rustc_middle::ty::ParamTy>, + crate named_regions: BTreeMap<DefId, u32>, +} + +impl<'tcx> ParamsSubstitutor<'tcx> { + crate fn new(tcx: TyCtxt<'tcx>) -> Self { + ParamsSubstitutor { + tcx, + binder_index: ty::INNERMOST, + list: vec![], + params: rustc_data_structures::fx::FxHashMap::default(), + named_regions: BTreeMap::default(), + } + } +} + +impl<'tcx> TypeFolder<'tcx> for ParamsSubstitutor<'tcx> { + fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { + self.tcx + } + + fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> Binder<T> { + self.binder_index.shift_in(1); + let result = t.super_fold_with(self); + self.binder_index.shift_out(1); + result + } + + fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { + match t.kind { + // FIXME(chalk): currently we convert params to placeholders starting at + // index `0`. To support placeholders, we'll actually need to do a + // first pass to collect placeholders. Then we can insert params after. + ty::Placeholder(_) => unimplemented!(), + ty::Param(param) => match self.list.iter().position(|r| r == ¶m) { + Some(_idx) => self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType { + universe: ty::UniverseIndex::from_usize(0), + name: ty::BoundVar::from_usize(_idx), + })), + None => { + self.list.push(param); + let idx = self.list.len() - 1; + self.params.insert(idx, param); + self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType { + universe: ty::UniverseIndex::from_usize(0), + name: ty::BoundVar::from_usize(idx), + })) + } + }, + + _ => t.super_fold_with(self), + } + } + + fn fold_region(&mut self, r: Region<'tcx>) -> Region<'tcx> { + match r { + // FIXME(chalk) - jackh726 - this currently isn't hit in any tests. + // This covers any region variables in a goal, right? + ty::ReEarlyBound(_re) => match self.named_regions.get(&_re.def_id) { + Some(idx) => self.tcx.mk_region(RegionKind::ReLateBound( + self.binder_index, + BoundRegion::BrAnon(*idx), + )), + None => { + let idx = self.named_regions.len() as u32; + self.named_regions.insert(_re.def_id, idx); + self.tcx.mk_region(RegionKind::ReLateBound( + self.binder_index, + BoundRegion::BrAnon(idx), + )) + } + }, + + _ => r.super_fold_with(self), + } + } +} diff --git a/compiler/rustc_traits/src/chalk/mod.rs b/compiler/rustc_traits/src/chalk/mod.rs new file mode 100644 index 00000000000..f18b4ca65f6 --- /dev/null +++ b/compiler/rustc_traits/src/chalk/mod.rs @@ -0,0 +1,229 @@ +//! Calls `chalk-solve` to solve a `ty::Predicate` +//! +//! In order to call `chalk-solve`, this file must convert a +//! `ChalkCanonicalGoal` into a Chalk ucanonical goal. It then calls Chalk, and +//! converts the answer back into rustc solution. + +crate mod db; +crate mod lowering; + +use rustc_data_structures::fx::FxHashMap; + +use rustc_index::vec::IndexVec; + +use rustc_middle::infer::canonical::{CanonicalTyVarKind, CanonicalVarKind}; +use rustc_middle::traits::ChalkRustInterner; +use rustc_middle::ty::query::Providers; +use rustc_middle::ty::subst::GenericArg; +use rustc_middle::ty::{ + self, Bound, BoundVar, ParamTy, Region, RegionKind, Ty, TyCtxt, TypeFoldable, +}; + +use rustc_infer::infer::canonical::{ + Canonical, CanonicalVarValues, Certainty, QueryRegionConstraints, QueryResponse, +}; +use rustc_infer::traits::{self, ChalkCanonicalGoal}; + +use crate::chalk::db::RustIrDatabase as ChalkRustIrDatabase; +use crate::chalk::lowering::{LowerInto, ParamsSubstitutor}; + +use chalk_solve::Solution; + +crate fn provide(p: &mut Providers) { + *p = Providers { evaluate_goal, ..*p }; +} + +crate fn evaluate_goal<'tcx>( + tcx: TyCtxt<'tcx>, + obligation: ChalkCanonicalGoal<'tcx>, +) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, ()>>, traits::query::NoSolution> { + let interner = ChalkRustInterner { tcx }; + + // Chalk doesn't have a notion of `Params`, so instead we use placeholders. + let mut params_substitutor = ParamsSubstitutor::new(tcx); + let obligation = obligation.fold_with(&mut params_substitutor); + let _params: FxHashMap<usize, ParamTy> = params_substitutor.params; + let max_universe = obligation.max_universe.index(); + + let _lowered_goal: chalk_ir::UCanonical< + chalk_ir::InEnvironment<chalk_ir::Goal<ChalkRustInterner<'tcx>>>, + > = chalk_ir::UCanonical { + canonical: chalk_ir::Canonical { + binders: chalk_ir::CanonicalVarKinds::from( + &interner, + obligation.variables.iter().map(|v| match v.kind { + CanonicalVarKind::PlaceholderTy(_ty) => unimplemented!(), + CanonicalVarKind::PlaceholderRegion(_ui) => unimplemented!(), + CanonicalVarKind::Ty(ty) => match ty { + CanonicalTyVarKind::General(ui) => chalk_ir::WithKind::new( + chalk_ir::VariableKind::Ty(chalk_ir::TyKind::General), + chalk_ir::UniverseIndex { counter: ui.index() }, + ), + CanonicalTyVarKind::Int => chalk_ir::WithKind::new( + chalk_ir::VariableKind::Ty(chalk_ir::TyKind::Integer), + chalk_ir::UniverseIndex::root(), + ), + CanonicalTyVarKind::Float => chalk_ir::WithKind::new( + chalk_ir::VariableKind::Ty(chalk_ir::TyKind::Float), + chalk_ir::UniverseIndex::root(), + ), + }, + CanonicalVarKind::Region(ui) => chalk_ir::WithKind::new( + chalk_ir::VariableKind::Lifetime, + chalk_ir::UniverseIndex { counter: ui.index() }, + ), + CanonicalVarKind::Const(_ui) => unimplemented!(), + CanonicalVarKind::PlaceholderConst(_pc) => unimplemented!(), + }), + ), + value: obligation.value.lower_into(&interner), + }, + universes: max_universe + 1, + }; + + let solver_choice = chalk_solve::SolverChoice::SLG { max_size: 32, expected_answers: None }; + let mut solver = solver_choice.into_solver::<ChalkRustInterner<'tcx>>(); + + let db = ChalkRustIrDatabase { tcx, interner }; + let solution = solver.solve(&db, &_lowered_goal); + + // Ideally, the code to convert *back* to rustc types would live close to + // the code to convert *from* rustc types. Right now though, we don't + // really need this and so it's really minimal. + // Right now, we also treat a `Unique` solution the same as + // `Ambig(Definite)`. This really isn't right. + let make_solution = |_subst: chalk_ir::Substitution<_>| { + let mut var_values: IndexVec<BoundVar, GenericArg<'tcx>> = IndexVec::new(); + _subst.parameters(&interner).iter().for_each(|p| { + // FIXME(chalk): we should move this elsewhere, since this is + // essentially inverse of lowering a `GenericArg`. + let _data = p.data(&interner); + match _data { + chalk_ir::GenericArgData::Ty(_t) => { + use chalk_ir::TyData; + use rustc_ast as ast; + + let _data = _t.data(&interner); + let kind = match _data { + TyData::Apply(_application_ty) => match _application_ty.name { + chalk_ir::TypeName::Adt(_struct_id) => unimplemented!(), + chalk_ir::TypeName::Scalar(scalar) => match scalar { + chalk_ir::Scalar::Bool => ty::Bool, + chalk_ir::Scalar::Char => ty::Char, + chalk_ir::Scalar::Int(int_ty) => match int_ty { + chalk_ir::IntTy::Isize => ty::Int(ast::IntTy::Isize), + chalk_ir::IntTy::I8 => ty::Int(ast::IntTy::I8), + chalk_ir::IntTy::I16 => ty::Int(ast::IntTy::I16), + chalk_ir::IntTy::I32 => ty::Int(ast::IntTy::I32), + chalk_ir::IntTy::I64 => ty::Int(ast::IntTy::I64), + chalk_ir::IntTy::I128 => ty::Int(ast::IntTy::I128), + }, + chalk_ir::Scalar::Uint(int_ty) => match int_ty { + chalk_ir::UintTy::Usize => ty::Uint(ast::UintTy::Usize), + chalk_ir::UintTy::U8 => ty::Uint(ast::UintTy::U8), + chalk_ir::UintTy::U16 => ty::Uint(ast::UintTy::U16), + chalk_ir::UintTy::U32 => ty::Uint(ast::UintTy::U32), + chalk_ir::UintTy::U64 => ty::Uint(ast::UintTy::U64), + chalk_ir::UintTy::U128 => ty::Uint(ast::UintTy::U128), + }, + chalk_ir::Scalar::Float(float_ty) => match float_ty { + chalk_ir::FloatTy::F32 => ty::Float(ast::FloatTy::F32), + chalk_ir::FloatTy::F64 => ty::Float(ast::FloatTy::F64), + }, + }, + chalk_ir::TypeName::Array => unimplemented!(), + chalk_ir::TypeName::FnDef(_) => unimplemented!(), + chalk_ir::TypeName::Closure(_) => unimplemented!(), + chalk_ir::TypeName::Never => unimplemented!(), + chalk_ir::TypeName::Tuple(_size) => unimplemented!(), + chalk_ir::TypeName::Slice => unimplemented!(), + chalk_ir::TypeName::Raw(_) => unimplemented!(), + chalk_ir::TypeName::Ref(_) => unimplemented!(), + chalk_ir::TypeName::Str => unimplemented!(), + chalk_ir::TypeName::OpaqueType(_ty) => unimplemented!(), + chalk_ir::TypeName::AssociatedType(_assoc_ty) => unimplemented!(), + chalk_ir::TypeName::Error => unimplemented!(), + }, + TyData::Placeholder(_placeholder) => { + unimplemented!(); + } + TyData::Alias(_alias_ty) => unimplemented!(), + TyData::Function(_quantified_ty) => unimplemented!(), + TyData::BoundVar(_bound) => Bound( + ty::DebruijnIndex::from_usize(_bound.debruijn.depth() as usize), + ty::BoundTy { + var: ty::BoundVar::from_usize(_bound.index), + kind: ty::BoundTyKind::Anon, + }, + ), + TyData::InferenceVar(_, _) => unimplemented!(), + TyData::Dyn(_) => unimplemented!(), + }; + let _ty: Ty<'_> = tcx.mk_ty(kind); + let _arg: GenericArg<'_> = _ty.into(); + var_values.push(_arg); + } + chalk_ir::GenericArgData::Lifetime(_l) => { + let _data = _l.data(&interner); + let _lifetime: Region<'_> = match _data { + chalk_ir::LifetimeData::BoundVar(_var) => { + tcx.mk_region(RegionKind::ReLateBound( + rustc_middle::ty::DebruijnIndex::from_usize( + _var.debruijn.depth() as usize + ), + rustc_middle::ty::BoundRegion::BrAnon(_var.index as u32), + )) + } + chalk_ir::LifetimeData::InferenceVar(_var) => unimplemented!(), + chalk_ir::LifetimeData::Placeholder(_index) => unimplemented!(), + chalk_ir::LifetimeData::Phantom(_, _) => unimplemented!(), + }; + let _arg: GenericArg<'_> = _lifetime.into(); + var_values.push(_arg); + } + chalk_ir::GenericArgData::Const(_) => unimplemented!(), + } + }); + let sol = Canonical { + max_universe: ty::UniverseIndex::from_usize(0), + variables: obligation.variables.clone(), + value: QueryResponse { + var_values: CanonicalVarValues { var_values }, + region_constraints: QueryRegionConstraints::default(), + certainty: Certainty::Proven, + value: (), + }, + }; + &*tcx.arena.alloc(sol) + }; + solution + .map(|s| match s { + Solution::Unique(_subst) => { + // FIXME(chalk): handle constraints + make_solution(_subst.value.subst) + } + Solution::Ambig(_guidance) => { + match _guidance { + chalk_solve::Guidance::Definite(_subst) => make_solution(_subst.value), + chalk_solve::Guidance::Suggested(_) => unimplemented!(), + chalk_solve::Guidance::Unknown => { + // chalk_fulfill doesn't use the var_values here, so + // let's just ignore that + let sol = Canonical { + max_universe: ty::UniverseIndex::from_usize(0), + variables: obligation.variables.clone(), + value: QueryResponse { + var_values: CanonicalVarValues { var_values: IndexVec::new() } + .make_identity(tcx), + region_constraints: QueryRegionConstraints::default(), + certainty: Certainty::Ambiguous, + value: (), + }, + }; + &*tcx.arena.alloc(sol) + } + } + } + }) + .ok_or(traits::query::NoSolution) +} |