From d5d485ef9289589332893f2c0ad96cb366afe9d6 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 28 Jun 2020 21:17:27 +0200 Subject: Implement Chalk variable kinds This means we need to keep track of the kinds (general/int/float) of variables in `Canonical`, which requires some more ceremony. (It also exposes some places where we're not really dealing with canonicalization correctly -- another thing to be cleaned up when we switch to using Chalk's types directly.) Should fix the last remaining issue of #2534. --- crates/ra_hir/src/code_model.rs | 10 ++--- crates/ra_hir_ty/src/autoderef.rs | 15 ++++---- crates/ra_hir_ty/src/infer/unify.rs | 55 ++++++++++++++++++++-------- crates/ra_hir_ty/src/lib.rs | 22 +++++++++-- crates/ra_hir_ty/src/method_resolution.rs | 32 ++++++++-------- crates/ra_hir_ty/src/tests/traits.rs | 18 +++++++++ crates/ra_hir_ty/src/traits.rs | 16 ++------ crates/ra_hir_ty/src/traits/chalk/mapping.rs | 43 +++++++++++++++------- 8 files changed, 140 insertions(+), 71 deletions(-) diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs index e86077dd6..479c82fa4 100644 --- a/crates/ra_hir/src/code_model.rs +++ b/crates/ra_hir/src/code_model.rs @@ -1187,7 +1187,7 @@ impl Type { None => return false, }; - let canonical_ty = Canonical { value: self.ty.value.clone(), num_vars: 0 }; + let canonical_ty = Canonical { value: self.ty.value.clone(), kinds: Arc::new([]) }; method_resolution::implements_trait( &canonical_ty, db, @@ -1211,7 +1211,7 @@ impl Type { self.ty.environment.clone(), hir_ty::Obligation::Trait(trait_ref), ), - num_vars: 0, + kinds: Arc::new([]), }; db.trait_solve(self.krate, goal).is_some() @@ -1286,7 +1286,7 @@ impl Type { pub fn autoderef<'a>(&'a self, db: &'a dyn HirDatabase) -> impl Iterator + 'a { // There should be no inference vars in types passed here // FIXME check that? - let canonical = Canonical { value: self.ty.value.clone(), num_vars: 0 }; + let canonical = Canonical { value: self.ty.value.clone(), kinds: Arc::new([]) }; let environment = self.ty.environment.clone(); let ty = InEnvironment { value: canonical, environment }; autoderef(db, Some(self.krate), ty) @@ -1327,7 +1327,7 @@ impl Type { // There should be no inference vars in types passed here // FIXME check that? // FIXME replace Unknown by bound vars here - let canonical = Canonical { value: self.ty.value.clone(), num_vars: 0 }; + let canonical = Canonical { value: self.ty.value.clone(), kinds: Arc::new([]) }; let env = self.ty.environment.clone(); let krate = krate.id; @@ -1358,7 +1358,7 @@ impl Type { // There should be no inference vars in types passed here // FIXME check that? // FIXME replace Unknown by bound vars here - let canonical = Canonical { value: self.ty.value.clone(), num_vars: 0 }; + let canonical = Canonical { value: self.ty.value.clone(), kinds: Arc::new([]) }; let env = self.ty.environment.clone(); let krate = krate.id; diff --git a/crates/ra_hir_ty/src/autoderef.rs b/crates/ra_hir_ty/src/autoderef.rs index 1b0f84c5c..c727012c6 100644 --- a/crates/ra_hir_ty/src/autoderef.rs +++ b/crates/ra_hir_ty/src/autoderef.rs @@ -37,7 +37,7 @@ pub(crate) fn deref( ty: InEnvironment<&Canonical>, ) -> Option> { if let Some(derefed) = ty.value.value.builtin_deref() { - Some(Canonical { value: derefed, num_vars: ty.value.num_vars }) + Some(Canonical { value: derefed, kinds: ty.value.kinds.clone() }) } else { deref_by_trait(db, krate, ty) } @@ -68,8 +68,8 @@ fn deref_by_trait( // Check that the type implements Deref at all let trait_ref = TraitRef { trait_: deref_trait, substs: parameters.clone() }; - let implements_goal = super::Canonical { - num_vars: ty.value.num_vars, + let implements_goal = Canonical { + kinds: ty.value.kinds.clone(), value: InEnvironment { value: Obligation::Trait(trait_ref), environment: ty.environment.clone(), @@ -81,7 +81,7 @@ fn deref_by_trait( // Now do the assoc type projection let projection = super::traits::ProjectionPredicate { - ty: Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, ty.value.num_vars)), + ty: Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, ty.value.kinds.len())), projection_ty: super::ProjectionTy { associated_ty: target, parameters }, }; @@ -89,7 +89,8 @@ fn deref_by_trait( let in_env = InEnvironment { value: obligation, environment: ty.environment }; - let canonical = super::Canonical { num_vars: 1 + ty.value.num_vars, value: in_env }; + let canonical = + Canonical::new(in_env, ty.value.kinds.iter().copied().chain(Some(super::TyKind::General))); let solution = db.trait_solve(krate, canonical)?; @@ -110,7 +111,7 @@ fn deref_by_trait( // assumptions will be broken. We would need to properly introduce // new variables in that case - for i in 1..vars.0.num_vars { + for i in 1..vars.0.kinds.len() { if vars.0.value[i - 1] != Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, i - 1)) { warn!("complex solution for derefing {:?}: {:?}, ignoring", ty.value, solution); @@ -119,7 +120,7 @@ fn deref_by_trait( } Some(Canonical { value: vars.0.value[vars.0.value.len() - 1].clone(), - num_vars: vars.0.num_vars, + kinds: vars.0.kinds.clone(), }) } Solution::Ambig(_) => { diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs index 269495ca0..2e895d911 100644 --- a/crates/ra_hir_ty/src/infer/unify.rs +++ b/crates/ra_hir_ty/src/infer/unify.rs @@ -9,7 +9,7 @@ use test_utils::mark; use super::{InferenceContext, Obligation}; use crate::{ BoundVar, Canonical, DebruijnIndex, GenericPredicate, InEnvironment, InferTy, Substs, Ty, - TypeCtor, TypeWalk, + TyKind, TypeCtor, TypeWalk, }; impl<'a> InferenceContext<'a> { @@ -86,10 +86,20 @@ where } fn into_canonicalized(self, result: T) -> Canonicalized { - Canonicalized { - value: Canonical { value: result, num_vars: self.free_vars.len() }, - free_vars: self.free_vars, - } + let kinds = self + .free_vars + .iter() + .map(|v| match v { + // mapping MaybeNeverTypeVar to the same kind as general ones + // should be fine, because as opposed to int or float type vars, + // they don't restrict what kind of type can go into them, they + // just affect fallback. + InferTy::TypeVar(_) | InferTy::MaybeNeverTypeVar(_) => TyKind::General, + InferTy::IntVar(_) => TyKind::Integer, + InferTy::FloatVar(_) => TyKind::Float, + }) + .collect(); + Canonicalized { value: Canonical { value: result, kinds }, free_vars: self.free_vars } } pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized { @@ -131,26 +141,41 @@ impl Canonicalized { ty } - pub fn apply_solution(&self, ctx: &mut InferenceContext<'_>, solution: Canonical>) { + pub fn apply_solution(&self, ctx: &mut InferenceContext<'_>, solution: Canonical) { // the solution may contain new variables, which we need to convert to new inference vars - let new_vars = Substs((0..solution.num_vars).map(|_| ctx.table.new_type_var()).collect()); + let new_vars = Substs( + solution + .kinds + .iter() + .map(|k| match k { + TyKind::General => ctx.table.new_type_var(), + TyKind::Integer => ctx.table.new_integer_var(), + TyKind::Float => ctx.table.new_float_var(), + }) + .collect(), + ); for (i, ty) in solution.value.into_iter().enumerate() { let var = self.free_vars[i]; // eagerly replace projections in the type; we may be getting types // e.g. from where clauses where this hasn't happened yet - let ty = ctx.normalize_associated_types_in(ty.subst_bound_vars(&new_vars)); + let ty = ctx.normalize_associated_types_in(ty.clone().subst_bound_vars(&new_vars)); ctx.table.unify(&Ty::Infer(var), &ty); } } } -pub fn unify(ty1: &Canonical, ty2: &Canonical) -> Option { +pub fn unify(tys: &Canonical<(Ty, Ty)>) -> Option { let mut table = InferenceTable::new(); - let num_vars = ty1.num_vars.max(ty2.num_vars); - let vars = - Substs::builder(num_vars).fill(std::iter::repeat_with(|| table.new_type_var())).build(); - let ty1_with_vars = ty1.value.clone().subst_bound_vars(&vars); - let ty2_with_vars = ty2.value.clone().subst_bound_vars(&vars); + let vars = Substs( + tys.kinds + .iter() + // we always use type vars here because we want everything to + // fallback to Unknown in the end (kind of hacky, as below) + .map(|_| table.new_type_var()) + .collect(), + ); + let ty1_with_vars = tys.value.0.clone().subst_bound_vars(&vars); + let ty2_with_vars = tys.value.1.clone().subst_bound_vars(&vars); if !table.unify(&ty1_with_vars, &ty2_with_vars) { return None; } @@ -162,7 +187,7 @@ pub fn unify(ty1: &Canonical, ty2: &Canonical) -> Option { } } Some( - Substs::builder(ty1.num_vars) + Substs::builder(tys.kinds.len()) .fill(vars.iter().map(|v| table.resolve_ty_completely(v.clone()))) .build(), ) diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs index c9513b752..7f3f5e771 100644 --- a/crates/ra_hir_ty/src/lib.rs +++ b/crates/ra_hir_ty/src/lib.rs @@ -662,13 +662,27 @@ impl TypeWalk for GenericPredicate { /// Basically a claim (currently not validated / checked) that the contained /// type / trait ref contains no inference variables; any inference variables it -/// contained have been replaced by bound variables, and `num_vars` tells us how -/// many there are. This is used to erase irrelevant differences between types -/// before using them in queries. +/// contained have been replaced by bound variables, and `kinds` tells us how +/// many there are and whether they were normal or float/int variables. This is +/// used to erase irrelevant differences between types before using them in +/// queries. #[derive(Debug, Clone, PartialEq, Eq, Hash)] pub struct Canonical { pub value: T, - pub num_vars: usize, + pub kinds: Arc<[TyKind]>, +} + +impl Canonical { + pub fn new(value: T, kinds: impl IntoIterator) -> Self { + Self { value, kinds: kinds.into_iter().collect() } + } +} + +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] +pub enum TyKind { + General, + Integer, + Float, } /// A function signature as seen by type inference: Several parameter types and diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index c19519cf1..c3edd6885 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -2,7 +2,7 @@ //! For details about how this works in rustc, see the method lookup page in the //! [rustc guide](https://rust-lang.github.io/rustc-guide/method-lookup.html) //! and the corresponding code mostly in librustc_typeck/check/method/probe.rs. -use std::sync::Arc; +use std::{iter, sync::Arc}; use arrayvec::ArrayVec; use hir_def::{ @@ -17,7 +17,8 @@ use rustc_hash::{FxHashMap, FxHashSet}; use super::Substs; use crate::{ autoderef, db::HirDatabase, primitive::FloatBitness, utils::all_super_traits, ApplicationTy, - Canonical, DebruijnIndex, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk, + Canonical, DebruijnIndex, InEnvironment, TraitEnvironment, TraitRef, Ty, TyKind, TypeCtor, + TypeWalk, }; /// This is used as a key for indexing impls. @@ -377,7 +378,7 @@ fn iterate_method_candidates_with_autoref( return true; } let refed = Canonical { - num_vars: deref_chain[0].num_vars, + kinds: deref_chain[0].kinds.clone(), value: Ty::apply_one(TypeCtor::Ref(Mutability::Shared), deref_chain[0].value.clone()), }; if iterate_method_candidates_by_receiver( @@ -393,7 +394,7 @@ fn iterate_method_candidates_with_autoref( return true; } let ref_muted = Canonical { - num_vars: deref_chain[0].num_vars, + kinds: deref_chain[0].kinds.clone(), value: Ty::apply_one(TypeCtor::Ref(Mutability::Mut), deref_chain[0].value.clone()), }; if iterate_method_candidates_by_receiver( @@ -612,18 +613,19 @@ pub(crate) fn inherent_impl_substs( // we create a var for each type parameter of the impl; we need to keep in // mind here that `self_ty` might have vars of its own let vars = Substs::build_for_def(db, impl_id) - .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.num_vars) + .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.kinds.len()) .build(); let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars); - let self_ty_with_vars = - Canonical { num_vars: vars.len() + self_ty.num_vars, value: self_ty_with_vars }; - let substs = super::infer::unify(&self_ty_with_vars, self_ty); + let mut kinds = self_ty.kinds.to_vec(); + kinds.extend(iter::repeat(TyKind::General).take(vars.len())); + let tys = Canonical { kinds: kinds.into(), value: (self_ty_with_vars, self_ty.value.clone()) }; + let substs = super::infer::unify(&tys); // We only want the substs for the vars we added, not the ones from self_ty. // Also, if any of the vars we added are still in there, we replace them by // Unknown. I think this can only really happen if self_ty contained // Unknown, and in that case we want the result to contain Unknown in those // places again. - substs.map(|s| fallback_bound_vars(s.suffix(vars.len()), self_ty.num_vars)) + substs.map(|s| fallback_bound_vars(s.suffix(vars.len()), self_ty.kinds.len())) } /// This replaces any 'free' Bound vars in `s` (i.e. those with indices past @@ -683,15 +685,15 @@ fn generic_implements_goal( trait_: TraitId, self_ty: Canonical, ) -> Canonical> { - let num_vars = self_ty.num_vars; + let mut kinds = self_ty.kinds.to_vec(); let substs = super::Substs::build_for_def(db, trait_) .push(self_ty.value) - .fill_with_bound_vars(DebruijnIndex::INNERMOST, num_vars) + .fill_with_bound_vars(DebruijnIndex::INNERMOST, kinds.len()) .build(); - let num_vars = substs.len() - 1 + self_ty.num_vars; + kinds.extend(iter::repeat(TyKind::General).take(substs.len() - 1)); let trait_ref = TraitRef { trait_, substs }; let obligation = super::Obligation::Trait(trait_ref); - Canonical { num_vars, value: InEnvironment::new(env, obligation) } + Canonical { kinds: kinds.into(), value: InEnvironment::new(env, obligation) } } fn autoderef_method_receiver( @@ -704,9 +706,9 @@ fn autoderef_method_receiver( if let Some(Ty::Apply(ApplicationTy { ctor: TypeCtor::Array, parameters })) = deref_chain.last().map(|ty| &ty.value) { - let num_vars = deref_chain.last().unwrap().num_vars; + let kinds = deref_chain.last().unwrap().kinds.clone(); let unsized_ty = Ty::apply(TypeCtor::Slice, parameters.clone()); - deref_chain.push(Canonical { value: unsized_ty, num_vars }) + deref_chain.push(Canonical { value: unsized_ty, kinds }) } deref_chain } diff --git a/crates/ra_hir_ty/src/tests/traits.rs b/crates/ra_hir_ty/src/tests/traits.rs index 01c919a7e..766790576 100644 --- a/crates/ra_hir_ty/src/tests/traits.rs +++ b/crates/ra_hir_ty/src/tests/traits.rs @@ -3029,3 +3029,21 @@ fn infer_dyn_fn_output() { "### ); } + +#[test] +fn variable_kinds() { + check_types( + r#" +trait Trait { fn get(self, t: T) -> T; } +struct S; +impl Trait for S {} +impl Trait for S {} +fn test() { + S.get(1); + //^^^^^^^^ u128 + S.get(1.); + //^^^^^^^^ f32 +} + "#, + ); +} diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs index 6f43c3a22..2a6d7faef 100644 --- a/crates/ra_hir_ty/src/traits.rs +++ b/crates/ra_hir_ty/src/traits.rs @@ -1,5 +1,5 @@ //! Trait solving using Chalk. -use std::{panic, sync::Arc}; +use std::sync::Arc; use chalk_ir::cast::Cast; use hir_def::{ @@ -8,7 +8,7 @@ use hir_def::{ use ra_db::{impl_intern_key, salsa, CrateId}; use ra_prof::profile; -use crate::{db::HirDatabase, DebruijnIndex}; +use crate::{db::HirDatabase, DebruijnIndex, Substs}; use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk}; @@ -190,15 +190,7 @@ fn solution_from_chalk( solution: chalk_solve::Solution, ) -> Solution { let convert_subst = |subst: chalk_ir::Canonical>| { - let value = subst - .value - .iter(&Interner) - .map(|p| match p.ty(&Interner) { - Some(ty) => from_chalk(db, ty.clone()), - None => unimplemented!(), - }) - .collect(); - let result = Canonical { value, num_vars: subst.binders.len(&Interner) }; + let result = from_chalk(db, subst); SolutionVariables(result) }; match solution { @@ -222,7 +214,7 @@ fn solution_from_chalk( } #[derive(Clone, Debug, PartialEq, Eq)] -pub struct SolutionVariables(pub Canonical>); +pub struct SolutionVariables(pub Canonical); #[derive(Clone, Debug, PartialEq, Eq)] /// A (possible) solution for a proposed goal. diff --git a/crates/ra_hir_ty/src/traits/chalk/mapping.rs b/crates/ra_hir_ty/src/traits/chalk/mapping.rs index ac82ea831..433d6aa03 100644 --- a/crates/ra_hir_ty/src/traits/chalk/mapping.rs +++ b/crates/ra_hir_ty/src/traits/chalk/mapping.rs @@ -17,7 +17,7 @@ use crate::{ primitive::{FloatBitness, FloatTy, IntBitness, IntTy, Signedness}, traits::{builtin, AssocTyValue, Canonical, Impl, Obligation}, ApplicationTy, CallableDef, GenericPredicate, InEnvironment, OpaqueTy, OpaqueTyId, - ProjectionPredicate, ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TypeCtor, + ProjectionPredicate, ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TyKind, TypeCtor, }; use super::interner::*; @@ -555,22 +555,39 @@ where type Chalk = chalk_ir::Canonical; fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Canonical { - let parameter = chalk_ir::CanonicalVarKind::new( - chalk_ir::VariableKind::Ty(chalk_ir::TyKind::General), - chalk_ir::UniverseIndex::ROOT, - ); + let kinds = self + .kinds + .iter() + .map(|k| match k { + TyKind::General => chalk_ir::TyKind::General, + TyKind::Integer => chalk_ir::TyKind::Integer, + TyKind::Float => chalk_ir::TyKind::Float, + }) + .map(|tk| { + chalk_ir::CanonicalVarKind::new( + chalk_ir::VariableKind::Ty(tk), + chalk_ir::UniverseIndex::ROOT, + ) + }); let value = self.value.to_chalk(db); - chalk_ir::Canonical { - value, - binders: chalk_ir::CanonicalVarKinds::from(&Interner, vec![parameter; self.num_vars]), - } + chalk_ir::Canonical { value, binders: chalk_ir::CanonicalVarKinds::from(&Interner, kinds) } } fn from_chalk(db: &dyn HirDatabase, canonical: chalk_ir::Canonical) -> Canonical { - Canonical { - num_vars: canonical.binders.len(&Interner), - value: from_chalk(db, canonical.value), - } + let kinds = canonical + .binders + .iter(&Interner) + .map(|k| match k.kind { + chalk_ir::VariableKind::Ty(tk) => match tk { + chalk_ir::TyKind::General => TyKind::General, + chalk_ir::TyKind::Integer => TyKind::Integer, + chalk_ir::TyKind::Float => TyKind::Float, + }, + chalk_ir::VariableKind::Lifetime => panic!("unexpected lifetime from Chalk"), + chalk_ir::VariableKind::Const(_) => panic!("unexpected const from Chalk"), + }) + .collect(); + Canonical { kinds, value: from_chalk(db, canonical.value) } } } -- cgit v1.2.3