From 508a1ecad3cf9c9f01022b3e95f9d6a7ad7a4cd5 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 4 Apr 2021 20:22:00 +0200 Subject: Move things in hir_ty into submodules - all the types that will be replaced by Chalk go to `types` - `TypeWalk` impls go to `walk` --- crates/hir/src/lib.rs | 2 +- crates/hir_ty/src/builder.rs | 4 +- crates/hir_ty/src/display.rs | 20 +- crates/hir_ty/src/infer/expr.rs | 6 +- crates/hir_ty/src/infer/pat.rs | 4 +- crates/hir_ty/src/infer/path.rs | 2 +- crates/hir_ty/src/infer/unify.rs | 2 +- crates/hir_ty/src/lib.rs | 695 +----------------------------- crates/hir_ty/src/traits/chalk/mapping.rs | 10 +- crates/hir_ty/src/types.rs | 354 +++++++++++++++ crates/hir_ty/src/walk.rs | 359 +++++++++++++++ 11 files changed, 751 insertions(+), 707 deletions(-) create mode 100644 crates/hir_ty/src/types.rs create mode 100644 crates/hir_ty/src/walk.rs diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs index 19901ed33..b9255dd1d 100644 --- a/crates/hir/src/lib.rs +++ b/crates/hir/src/lib.rs @@ -1822,7 +1822,7 @@ impl Type { match db.trait_solve(self.krate, goal)? { Solution::Unique(SolutionVariables(subst)) => subst .value - .interned(&Interner) + .interned() .first() .map(|ty| self.derived(ty.assert_ty_ref(&Interner).clone())), Solution::Ambig(_) => None, diff --git a/crates/hir_ty/src/builder.rs b/crates/hir_ty/src/builder.rs index 4a9a8058f..0bac31e4c 100644 --- a/crates/hir_ty/src/builder.rs +++ b/crates/hir_ty/src/builder.rs @@ -33,7 +33,7 @@ impl TyBuilder { fn build_internal(self) -> (D, Substitution) { assert_eq!(self.vec.len(), self.param_count); // FIXME: would be good to have a way to construct a chalk_ir::Substitution from the interned form - let subst = Substitution(self.vec); + let subst = Substitution::intern(self.vec); (self.data, subst) } @@ -138,7 +138,7 @@ impl TyBuilder { self.vec.push(fallback().cast(&Interner)); } else { // each default can depend on the previous parameters - let subst_so_far = Substitution(self.vec.clone()); + let subst_so_far = Substitution::intern(self.vec.clone()); self.vec.push(default_ty.clone().subst(&subst_so_far).cast(&Interner)); } } diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs index 385bd9405..148eb7506 100644 --- a/crates/hir_ty/src/display.rs +++ b/crates/hir_ty/src/display.rs @@ -260,7 +260,7 @@ impl HirDisplay for ProjectionTy { write!(f, "<{} as {}", first_parameter, trait_.name)?; if self.substitution.len(&Interner) > 1 { write!(f, "<")?; - f.write_joined(&self.substitution.interned(&Interner)[1..], ", ")?; + f.write_joined(&self.substitution.interned()[1..], ", ")?; write!(f, ">")?; } write!(f, ">::{}", f.db.type_alias_data(from_assoc_type_id(self.associated_ty_id)).name)?; @@ -387,7 +387,7 @@ impl HirDisplay for Ty { write!(f, ",)")?; } else { write!(f, "(")?; - f.write_joined(&*substs.0, ", ")?; + f.write_joined(&*substs.interned(), ", ")?; write!(f, ")")?; } } @@ -415,7 +415,7 @@ impl HirDisplay for Ty { // We print all params except implicit impl Trait params. Still a bit weird; should we leave out parent and self? if total_len > 0 { write!(f, "<")?; - f.write_joined(¶meters.0[..total_len], ", ")?; + f.write_joined(¶meters.interned()[..total_len], ", ")?; write!(f, ">")?; } } @@ -468,7 +468,7 @@ impl HirDisplay for Ty { .map(|generic_def_id| f.db.generic_defaults(generic_def_id)) .filter(|defaults| !defaults.is_empty()) { - None => parameters.0.as_ref(), + None => parameters.interned().as_ref(), Some(default_parameters) => { let mut default_from = 0; for (i, parameter) in parameters.iter(&Interner).enumerate() { @@ -490,11 +490,11 @@ impl HirDisplay for Ty { } } } - ¶meters.0[0..default_from] + ¶meters.interned()[0..default_from] } } } else { - parameters.0.as_ref() + parameters.interned().as_ref() }; if !parameters_to_write.is_empty() { write!(f, "<")?; @@ -517,7 +517,7 @@ impl HirDisplay for Ty { write!(f, "{}::{}", trait_.name, type_alias_data.name)?; if parameters.len(&Interner) > 0 { write!(f, "<")?; - f.write_joined(&*parameters.0, ", ")?; + f.write_joined(&*parameters.interned(), ", ")?; write!(f, ">")?; } } else { @@ -727,13 +727,13 @@ fn write_bounds_like_dyn_trait( // existential) here, which is the only thing that's // possible in actual Rust, and hence don't print it write!(f, "{}", f.db.trait_data(trait_).name)?; - if let [_, params @ ..] = &*trait_ref.substitution.0 { + if let [_, params @ ..] = &*trait_ref.substitution.interned() { if is_fn_trait { if let Some(args) = params.first().and_then(|it| it.assert_ty_ref(&Interner).as_tuple()) { write!(f, "(")?; - f.write_joined(&*args.0, ", ")?; + f.write_joined(&*args.interned(), ", ")?; write!(f, ")")?; } } else if !params.is_empty() { @@ -789,7 +789,7 @@ impl TraitRef { write!(f, "{}", f.db.trait_data(self.hir_trait_id()).name)?; if self.substitution.len(&Interner) > 1 { write!(f, "<")?; - f.write_joined(&self.substitution.interned(&Interner)[1..], ", ")?; + f.write_joined(&self.substitution.interned()[1..], ", ")?; write!(f, ">")?; } Ok(()) diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs index c584a2c08..a87429a24 100644 --- a/crates/hir_ty/src/infer/expr.rs +++ b/crates/hir_ty/src/infer/expr.rs @@ -452,11 +452,7 @@ impl<'a> InferenceContext<'a> { }; match canonicalized.decanonicalize_ty(derefed_ty.value).kind(&Interner) { TyKind::Tuple(_, substs) => name.as_tuple_index().and_then(|idx| { - substs - .interned(&Interner) - .get(idx) - .map(|a| a.assert_ty_ref(&Interner)) - .cloned() + substs.interned().get(idx).map(|a| a.assert_ty_ref(&Interner)).cloned() }), TyKind::Adt(AdtId(hir_def::AdtId::StructId(s)), parameters) => { let local_id = self.db.struct_data(*s).variant_data.field(name)?; diff --git a/crates/hir_ty/src/infer/pat.rs b/crates/hir_ty/src/infer/pat.rs index 5b70d5e5a..469f37dd9 100644 --- a/crates/hir_ty/src/infer/pat.rs +++ b/crates/hir_ty/src/infer/pat.rs @@ -123,7 +123,7 @@ impl<'a> InferenceContext<'a> { let ty = match &body[pat] { &Pat::Tuple { ref args, ellipsis } => { let expectations = match expected.as_tuple() { - Some(parameters) => &*parameters.0, + Some(parameters) => &*parameters.interned(), _ => &[], }; @@ -239,7 +239,7 @@ impl<'a> InferenceContext<'a> { let (inner_ty, alloc_ty) = match expected.as_adt() { Some((adt, subst)) if adt == box_adt => ( subst.at(&Interner, 0).assert_ty_ref(&Interner).clone(), - subst.interned(&Interner).get(1).and_then(|a| a.ty(&Interner).cloned()), + subst.interned().get(1).and_then(|a| a.ty(&Interner).cloned()), ), _ => (self.result.standard_types.unknown.clone(), None), }; diff --git a/crates/hir_ty/src/infer/path.rs b/crates/hir_ty/src/infer/path.rs index 671ea355f..637341b53 100644 --- a/crates/hir_ty/src/infer/path.rs +++ b/crates/hir_ty/src/infer/path.rs @@ -98,7 +98,7 @@ impl<'a> InferenceContext<'a> { let substs = ctx.substs_from_path(path, typable, true); let ty = TyBuilder::value_ty(self.db, typable) .use_parent_substs(&parent_substs) - .fill(substs.interned(&Interner)[parent_substs.len(&Interner)..].iter().cloned()) + .fill(substs.interned()[parent_substs.len(&Interner)..].iter().cloned()) .build(); Some(ty) } diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs index a04b935ef..b7bc48569 100644 --- a/crates/hir_ty/src/infer/unify.rs +++ b/crates/hir_ty/src/infer/unify.rs @@ -284,7 +284,7 @@ impl InferenceTable { substs2: &Substitution, depth: usize, ) -> bool { - substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| { + substs1.iter(&Interner).zip(substs2.iter(&Interner)).all(|(t1, t2)| { self.unify_inner(t1.assert_ty_ref(&Interner), t2.assert_ty_ref(&Interner), depth) }) } diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs index a8c87eadf..40abbce42 100644 --- a/crates/hir_ty/src/lib.rs +++ b/crates/hir_ty/src/lib.rs @@ -16,6 +16,8 @@ pub(crate) mod utils; mod chalk_cast; mod chalk_ext; mod builder; +mod walk; +mod types; pub mod display; pub mod db; @@ -26,23 +28,18 @@ mod tests; #[cfg(test)] mod test_db; -use std::{mem, sync::Arc}; +use std::sync::Arc; -use chalk_ir::cast::{CastTo, Caster}; use itertools::Itertools; use smallvec::SmallVec; use base_db::salsa; use hir_def::{ - expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule, - LifetimeParamId, Lookup, TraitId, TypeAliasId, TypeParamId, + expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule, Lookup, + TraitId, TypeAliasId, TypeParamId, }; -use crate::{ - db::HirDatabase, - display::HirDisplay, - utils::{generics, make_mut_slice}, -}; +use crate::{db::HirDatabase, display::HirDisplay, utils::generics}; pub use autoderef::autoderef; pub use builder::TyBuilder; @@ -53,6 +50,8 @@ pub use lower::{ TyDefId, TyLoweringContext, ValueTyDefId, }; pub use traits::{AliasEq, DomainGoal, InEnvironment, TraitEnvironment}; +pub use types::*; +pub use walk::TypeWalk; pub use chalk_ir::{ cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind, @@ -71,41 +70,6 @@ pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds; pub type ChalkTraitId = chalk_ir::TraitId; -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub enum Lifetime { - Parameter(LifetimeParamId), - Static, -} - -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub struct OpaqueTy { - pub opaque_ty_id: OpaqueTyId, - pub substitution: Substitution, -} - -impl TypeWalk for OpaqueTy { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - self.substitution.walk(f); - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - self.substitution.walk_mut_binders(f, binders); - } -} - -/// A "projection" type corresponds to an (unnormalized) -/// projection like `>::Foo`. Note that the -/// trait and all its parameters are fully known. -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub struct ProjectionTy { - pub associated_ty_id: AssocTypeId, - pub substitution: Substitution, -} - impl ProjectionTy { pub fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef { TraitRef { @@ -115,7 +79,7 @@ impl ProjectionTy { } pub fn self_type_parameter(&self) -> &Ty { - &self.substitution.interned(&Interner)[0].assert_ty_ref(&Interner) + &self.substitution.interned()[0].assert_ty_ref(&Interner) } fn trait_(&self, db: &dyn HirDatabase) -> TraitId { @@ -126,322 +90,11 @@ impl ProjectionTy { } } -impl TypeWalk for ProjectionTy { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - self.substitution.walk(f); - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - self.substitution.walk_mut_binders(f, binders); - } -} - -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub struct DynTy { - /// The unknown self type. - pub bounds: Binders, -} - pub type FnSig = chalk_ir::FnSig; -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub struct FnPointer { - pub num_args: usize, - pub sig: FnSig, - pub substs: Substitution, -} - -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub enum AliasTy { - /// A "projection" type corresponds to an (unnormalized) - /// projection like `>::Foo`. Note that the - /// trait and all its parameters are fully known. - Projection(ProjectionTy), - /// An opaque type (`impl Trait`). - /// - /// This is currently only used for return type impl trait; each instance of - /// `impl Trait` in a return type gets its own ID. - Opaque(OpaqueTy), -} - -impl TypeWalk for AliasTy { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - match self { - AliasTy::Projection(it) => it.walk(f), - AliasTy::Opaque(it) => it.walk(f), - } - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - match self { - AliasTy::Projection(it) => it.walk_mut_binders(f, binders), - AliasTy::Opaque(it) => it.walk_mut_binders(f, binders), - } - } -} -/// A type. -/// -/// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents -/// the same thing (but in a different way). -/// -/// This should be cheap to clone. -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub enum TyKind { - /// Structures, enumerations and unions. - Adt(AdtId, Substitution), - - /// Represents an associated item like `Iterator::Item`. This is used - /// when we have tried to normalize a projection like `T::Item` but - /// couldn't find a better representation. In that case, we generate - /// an **application type** like `(Iterator::Item)`. - AssociatedType(AssocTypeId, Substitution), - - /// a scalar type like `bool` or `u32` - Scalar(Scalar), - - /// A tuple type. For example, `(i32, bool)`. - Tuple(usize, Substitution), - - /// An array with the given length. Written as `[T; n]`. - Array(Ty), - - /// The pointee of an array slice. Written as `[T]`. - Slice(Ty), - - /// A raw pointer. Written as `*mut T` or `*const T` - Raw(Mutability, Ty), - - /// A reference; a pointer with an associated lifetime. Written as - /// `&'a mut T` or `&'a T`. - Ref(Mutability, Ty), - - /// This represents a placeholder for an opaque type in situations where we - /// don't know the hidden type (i.e. currently almost always). This is - /// analogous to the `AssociatedType` type constructor. - /// It is also used as the type of async block, with one type parameter - /// representing the Future::Output type. - OpaqueType(OpaqueTyId, Substitution), - - /// The anonymous type of a function declaration/definition. Each - /// function has a unique type, which is output (for a function - /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`. - /// - /// This includes tuple struct / enum variant constructors as well. - /// - /// For example the type of `bar` here: - /// - /// ``` - /// fn foo() -> i32 { 1 } - /// let bar = foo; // bar: fn() -> i32 {foo} - /// ``` - FnDef(FnDefId, Substitution), - - /// The pointee of a string slice. Written as `str`. - Str, - - /// The never type `!`. - Never, - - /// The type of a specific closure. - /// - /// The closure signature is stored in a `FnPtr` type in the first type - /// parameter. - Closure(ClosureId, Substitution), - - /// Represents a foreign type declared in external blocks. - ForeignType(ForeignDefId), - - /// A pointer to a function. Written as `fn() -> i32`. - /// - /// For example the type of `bar` here: - /// - /// ``` - /// fn foo() -> i32 { 1 } - /// let bar: fn() -> i32 = foo; - /// ``` - Function(FnPointer), - - /// An "alias" type represents some form of type alias, such as: - /// - An associated type projection like `::Item` - /// - `impl Trait` types - /// - Named type aliases like `type Foo = Vec` - Alias(AliasTy), - - /// A placeholder for a type parameter; for example, `T` in `fn f(x: T) - /// {}` when we're type-checking the body of that function. In this - /// situation, we know this stands for *some* type, but don't know the exact - /// type. - Placeholder(PlaceholderIndex), - - /// A bound type variable. This is used in various places: when representing - /// some polymorphic type like the type of function `fn f`, the type - /// parameters get turned into variables; during trait resolution, inference - /// variables get turned into bound variables and back; and in `Dyn` the - /// `Self` type is represented with a bound variable as well. - BoundVar(BoundVar), - - /// A type variable used during type checking. - InferenceVar(InferenceVar, TyVariableKind), - - /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust). - /// - /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)` - /// represents the `Self` type inside the bounds. This is currently - /// implicit; Chalk has the `Binders` struct to make it explicit, but it - /// didn't seem worth the overhead yet. - Dyn(DynTy), - - /// A placeholder for a type which could not be computed; this is propagated - /// to avoid useless error messages. Doubles as a placeholder where type - /// variables are inserted before type checking, since we want to try to - /// infer a better type here anyway -- for the IDE use case, we want to try - /// to infer as much as possible even in the presence of type errors. - Unknown, -} - -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub struct Ty(Arc); - -impl TyKind { - pub fn intern(self, _interner: &Interner) -> Ty { - Ty(Arc::new(self)) - } -} - -impl Ty { - pub fn kind(&self, _interner: &Interner) -> &TyKind { - &self.0 - } - - pub fn interned_mut(&mut self) -> &mut TyKind { - Arc::make_mut(&mut self.0) - } - - pub fn into_inner(self) -> TyKind { - Arc::try_unwrap(self.0).unwrap_or_else(|a| (*a).clone()) - } -} - -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub struct GenericArg { - interned: GenericArgData, -} - -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub enum GenericArgData { - Ty(Ty), -} - -impl GenericArg { - /// Constructs a generic argument using `GenericArgData`. - pub fn new(_interner: &Interner, data: GenericArgData) -> Self { - GenericArg { interned: data } - } - - /// Gets the interned value. - pub fn interned(&self) -> &GenericArgData { - &self.interned - } - - /// Asserts that this is a type argument. - pub fn assert_ty_ref(&self, interner: &Interner) -> &Ty { - self.ty(interner).unwrap() - } - - /// Checks whether the generic argument is a type. - pub fn is_ty(&self, _interner: &Interner) -> bool { - match self.interned() { - GenericArgData::Ty(_) => true, - } - } - - /// Returns the type if it is one, `None` otherwise. - pub fn ty(&self, _interner: &Interner) -> Option<&Ty> { - match self.interned() { - GenericArgData::Ty(t) => Some(t), - } - } -} - -impl TypeWalk for GenericArg { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - match &self.interned { - GenericArgData::Ty(ty) => { - ty.walk(f); - } - } - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - match &mut self.interned { - GenericArgData::Ty(ty) => { - ty.walk_mut_binders(f, binders); - } - } - } -} - -/// A list of substitutions for generic parameters. -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub struct Substitution(SmallVec<[GenericArg; 2]>); - -impl TypeWalk for Substitution { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - for t in self.0.iter() { - t.walk(f); - } - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - for t in &mut self.0 { - t.walk_mut_binders(f, binders); - } - } -} - impl Substitution { - pub fn interned(&self, _: &Interner) -> &[GenericArg] { - &self.0 - } - - pub fn len(&self, _: &Interner) -> usize { - self.0.len() - } - - pub fn is_empty(&self, _: &Interner) -> bool { - self.0.is_empty() - } - - pub fn at(&self, _: &Interner, i: usize) -> &GenericArg { - &self.0[i] - } - - pub fn empty(_: &Interner) -> Substitution { - Substitution(SmallVec::new()) - } - - pub fn iter(&self, _: &Interner) -> std::slice::Iter<'_, GenericArg> { - self.0.iter() - } - pub fn single(ty: Ty) -> Substitution { - Substitution({ + Substitution::intern({ let mut v = SmallVec::new(); v.push(ty.cast(&Interner)); v @@ -449,18 +102,13 @@ impl Substitution { } pub fn prefix(&self, n: usize) -> Substitution { - Substitution(self.0[..std::cmp::min(self.0.len(), n)].into()) + Substitution::intern(self.interned()[..std::cmp::min(self.len(&Interner), n)].into()) } pub fn suffix(&self, n: usize) -> Substitution { - Substitution(self.0[self.0.len() - std::cmp::min(self.0.len(), n)..].into()) - } - - pub fn from_iter( - interner: &Interner, - elements: impl IntoIterator>, - ) -> Self { - Substitution(elements.into_iter().casted(interner).collect()) + Substitution::intern( + self.interned()[self.len(&Interner) - std::cmp::min(self.len(&Interner), n)..].into(), + ) } } @@ -469,12 +117,6 @@ pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option { generics(db.upcast(), id.parent).param_idx(id) } -#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)] -pub struct Binders { - pub num_binders: usize, - pub value: T, -} - impl Binders { pub fn new(num_binders: usize, value: T) -> Self { Self { num_binders, value } @@ -522,27 +164,6 @@ impl Binders { } } -impl TypeWalk for Binders { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - self.value.walk(f); - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - self.value.walk_mut_binders(f, binders.shifted_in()) - } -} - -/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait. -#[derive(Clone, PartialEq, Eq, Debug, Hash)] -pub struct TraitRef { - pub trait_id: ChalkTraitId, - pub substitution: Substitution, -} - impl TraitRef { pub fn self_type_parameter(&self) -> &Ty { &self.substitution.at(&Interner, 0).assert_ty_ref(&Interner) @@ -553,30 +174,6 @@ impl TraitRef { } } -impl TypeWalk for TraitRef { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - self.substitution.walk(f); - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - self.substitution.walk_mut_binders(f, binders); - } -} - -/// Like `generics::WherePredicate`, but with resolved types: A condition on the -/// parameters of a generic item. -#[derive(Debug, Clone, PartialEq, Eq, Hash)] -pub enum WhereClause { - /// The given trait needs to be implemented for its type parameters. - Implemented(TraitRef), - /// An associated type bindings like in `Iterator`. - AliasEq(AliasEq), -} - impl WhereClause { pub fn is_implemented(&self) -> bool { matches!(self, WhereClause::Implemented(_)) @@ -593,56 +190,6 @@ impl WhereClause { } } -impl TypeWalk for WhereClause { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - match self { - WhereClause::Implemented(trait_ref) => trait_ref.walk(f), - WhereClause::AliasEq(alias_eq) => alias_eq.walk(f), - } - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - match self { - WhereClause::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders), - WhereClause::AliasEq(alias_eq) => alias_eq.walk_mut_binders(f, binders), - } - } -} - -pub type QuantifiedWhereClause = Binders; - -#[derive(Debug, Clone, PartialEq, Eq, Hash)] -pub struct QuantifiedWhereClauses(Arc<[QuantifiedWhereClause]>); - -impl QuantifiedWhereClauses { - pub fn from_iter( - _interner: &Interner, - elements: impl IntoIterator, - ) -> Self { - QuantifiedWhereClauses(elements.into_iter().collect()) - } - - pub fn interned(&self) -> &Arc<[QuantifiedWhereClause]> { - &self.0 - } -} - -/// 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 `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 binders: CanonicalVarKinds, -} - impl Canonical { pub fn new(value: T, kinds: impl IntoIterator) -> Self { let kinds = kinds.into_iter().map(|tk| { @@ -679,7 +226,7 @@ impl CallableSig { .substs .clone() .shift_bound_vars_out(DebruijnIndex::ONE) - .interned(&Interner) + .interned() .iter() .map(|arg| arg.assert_ty_ref(&Interner).clone()) .collect(), @@ -696,24 +243,6 @@ impl CallableSig { } } -impl TypeWalk for CallableSig { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - for t in self.params_and_return.iter() { - t.walk(f); - } - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - for t in make_mut_slice(&mut self.params_and_return) { - t.walk_mut_binders(f, binders); - } - } -} - impl Ty { pub fn as_reference(&self) -> Option<(&Ty, Mutability)> { match self.kind(&Interner) { @@ -984,200 +513,6 @@ impl Ty { } } -/// This allows walking structures that contain types to do something with those -/// types, similar to Chalk's `Fold` trait. -pub trait TypeWalk { - fn walk(&self, f: &mut impl FnMut(&Ty)); - fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { - self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST); - } - /// Walk the type, counting entered binders. - /// - /// `TyKind::Bound` variables use DeBruijn indexing, which means that 0 refers - /// to the innermost binder, 1 to the next, etc.. So when we want to - /// substitute a certain bound variable, we can't just walk the whole type - /// and blindly replace each instance of a certain index; when we 'enter' - /// things that introduce new bound variables, we have to keep track of - /// that. Currently, the only thing that introduces bound variables on our - /// side are `TyKind::Dyn` and `TyKind::Opaque`, which each introduce a bound - /// variable for the self type. - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ); - - fn fold_binders( - mut self, - f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty, - binders: DebruijnIndex, - ) -> Self - where - Self: Sized, - { - self.walk_mut_binders( - &mut |ty_mut, binders| { - let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner)); - *ty_mut = f(ty, binders); - }, - binders, - ); - self - } - - fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self - where - Self: Sized, - { - self.walk_mut(&mut |ty_mut| { - let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner)); - *ty_mut = f(ty); - }); - self - } - - /// Substitutes `TyKind::Bound` vars with the given substitution. - fn subst_bound_vars(self, substs: &Substitution) -> Self - where - Self: Sized, - { - self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST) - } - - /// Substitutes `TyKind::Bound` vars with the given substitution. - fn subst_bound_vars_at_depth(mut self, substs: &Substitution, depth: DebruijnIndex) -> Self - where - Self: Sized, - { - self.walk_mut_binders( - &mut |ty, binders| { - if let &mut TyKind::BoundVar(bound) = ty.interned_mut() { - if bound.debruijn >= binders { - *ty = substs.0[bound.index] - .assert_ty_ref(&Interner) - .clone() - .shift_bound_vars(binders); - } - } - }, - depth, - ); - self - } - - /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`. - fn shift_bound_vars(self, n: DebruijnIndex) -> Self - where - Self: Sized, - { - self.fold_binders( - &mut |ty, binders| match ty.kind(&Interner) { - TyKind::BoundVar(bound) if bound.debruijn >= binders => { - TyKind::BoundVar(bound.shifted_in_from(n)).intern(&Interner) - } - _ => ty, - }, - DebruijnIndex::INNERMOST, - ) - } - - /// Shifts debruijn indices of `TyKind::Bound` vars out (down) by `n`. - fn shift_bound_vars_out(self, n: DebruijnIndex) -> Self - where - Self: Sized + std::fmt::Debug, - { - self.fold_binders( - &mut |ty, binders| match ty.kind(&Interner) { - TyKind::BoundVar(bound) if bound.debruijn >= binders => { - TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone())) - .intern(&Interner) - } - _ => ty, - }, - DebruijnIndex::INNERMOST, - ) - } -} - -impl TypeWalk for Ty { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - match self.kind(&Interner) { - TyKind::Alias(AliasTy::Projection(p_ty)) => { - for t in p_ty.substitution.iter(&Interner) { - t.walk(f); - } - } - TyKind::Alias(AliasTy::Opaque(o_ty)) => { - for t in o_ty.substitution.iter(&Interner) { - t.walk(f); - } - } - TyKind::Dyn(dyn_ty) => { - for p in dyn_ty.bounds.value.interned().iter() { - p.walk(f); - } - } - TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => { - ty.walk(f); - } - _ => { - if let Some(substs) = self.substs() { - for t in substs.iter(&Interner) { - t.walk(f); - } - } - } - } - f(self); - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - match self.interned_mut() { - TyKind::Alias(AliasTy::Projection(p_ty)) => { - p_ty.substitution.walk_mut_binders(f, binders); - } - TyKind::Dyn(dyn_ty) => { - for p in make_mut_slice(&mut dyn_ty.bounds.value.0) { - p.walk_mut_binders(f, binders.shifted_in()); - } - } - TyKind::Alias(AliasTy::Opaque(o_ty)) => { - o_ty.substitution.walk_mut_binders(f, binders); - } - TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => { - ty.walk_mut_binders(f, binders); - } - _ => { - if let Some(substs) = self.substs_mut() { - substs.walk_mut_binders(f, binders); - } - } - } - f(self, binders); - } -} - -impl TypeWalk for Vec { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - for t in self { - t.walk(f); - } - } - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - for t in self { - t.walk_mut_binders(f, binders); - } - } -} - #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)] pub enum ImplTraitId { ReturnTypeImplTrait(hir_def::FunctionId, u16), diff --git a/crates/hir_ty/src/traits/chalk/mapping.rs b/crates/hir_ty/src/traits/chalk/mapping.rs index 452b357e8..3a5800885 100644 --- a/crates/hir_ty/src/traits/chalk/mapping.rs +++ b/crates/hir_ty/src/traits/chalk/mapping.rs @@ -220,8 +220,8 @@ impl ToChalk for GenericArg { type Chalk = chalk_ir::GenericArg; fn to_chalk(self, db: &dyn HirDatabase) -> Self::Chalk { - match self.interned { - crate::GenericArgData::Ty(ty) => ty.to_chalk(db).cast(&Interner), + match self.interned() { + crate::GenericArgData::Ty(ty) => ty.clone().to_chalk(db).cast(&Interner), } } @@ -249,7 +249,7 @@ impl ToChalk for Substitution { parameters: chalk_ir::Substitution, ) -> Substitution { let tys = parameters.iter(&Interner).map(|p| from_chalk(db, p.clone())).collect(); - Substitution(tys) + Substitution::intern(tys) } } @@ -546,7 +546,7 @@ pub(super) fn generic_predicate_to_inline_bound( // have the expected self type return None; } - let args_no_self = trait_ref.substitution.interned(&Interner)[1..] + let args_no_self = trait_ref.substitution.interned()[1..] .iter() .map(|ty| ty.clone().to_chalk(db).cast(&Interner)) .collect(); @@ -558,7 +558,7 @@ pub(super) fn generic_predicate_to_inline_bound( return None; } let trait_ = projection_ty.trait_(db); - let args_no_self = projection_ty.substitution.interned(&Interner)[1..] + let args_no_self = projection_ty.substitution.interned()[1..] .iter() .map(|ty| ty.clone().to_chalk(db).cast(&Interner)) .collect(); diff --git a/crates/hir_ty/src/types.rs b/crates/hir_ty/src/types.rs new file mode 100644 index 000000000..d00f8e9ab --- /dev/null +++ b/crates/hir_ty/src/types.rs @@ -0,0 +1,354 @@ +//! This is the home of `Ty` etc. until they get replaced by their chalk_ir +//! equivalents. + +use std::sync::Arc; + +use chalk_ir::{ + cast::{CastTo, Caster}, + BoundVar, Mutability, Scalar, TyVariableKind, +}; +use hir_def::LifetimeParamId; +use smallvec::SmallVec; + +use crate::{ + AliasEq, AssocTypeId, CanonicalVarKinds, ChalkTraitId, ClosureId, FnDefId, FnSig, ForeignDefId, + InferenceVar, Interner, OpaqueTyId, PlaceholderIndex, +}; + +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub enum Lifetime { + Parameter(LifetimeParamId), + Static, +} + +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub struct OpaqueTy { + pub opaque_ty_id: OpaqueTyId, + pub substitution: Substitution, +} + +/// A "projection" type corresponds to an (unnormalized) +/// projection like `>::Foo`. Note that the +/// trait and all its parameters are fully known. +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub struct ProjectionTy { + pub associated_ty_id: AssocTypeId, + pub substitution: Substitution, +} + +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub struct DynTy { + /// The unknown self type. + pub bounds: Binders, +} + +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub struct FnPointer { + pub num_args: usize, + pub sig: FnSig, + pub substs: Substitution, +} + +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub enum AliasTy { + /// A "projection" type corresponds to an (unnormalized) + /// projection like `>::Foo`. Note that the + /// trait and all its parameters are fully known. + Projection(ProjectionTy), + /// An opaque type (`impl Trait`). + /// + /// This is currently only used for return type impl trait; each instance of + /// `impl Trait` in a return type gets its own ID. + Opaque(OpaqueTy), +} + +/// A type. +/// +/// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents +/// the same thing (but in a different way). +/// +/// This should be cheap to clone. +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub enum TyKind { + /// Structures, enumerations and unions. + Adt(chalk_ir::AdtId, Substitution), + + /// Represents an associated item like `Iterator::Item`. This is used + /// when we have tried to normalize a projection like `T::Item` but + /// couldn't find a better representation. In that case, we generate + /// an **application type** like `(Iterator::Item)`. + AssociatedType(AssocTypeId, Substitution), + + /// a scalar type like `bool` or `u32` + Scalar(Scalar), + + /// A tuple type. For example, `(i32, bool)`. + Tuple(usize, Substitution), + + /// An array with the given length. Written as `[T; n]`. + Array(Ty), + + /// The pointee of an array slice. Written as `[T]`. + Slice(Ty), + + /// A raw pointer. Written as `*mut T` or `*const T` + Raw(Mutability, Ty), + + /// A reference; a pointer with an associated lifetime. Written as + /// `&'a mut T` or `&'a T`. + Ref(Mutability, Ty), + + /// This represents a placeholder for an opaque type in situations where we + /// don't know the hidden type (i.e. currently almost always). This is + /// analogous to the `AssociatedType` type constructor. + /// It is also used as the type of async block, with one type parameter + /// representing the Future::Output type. + OpaqueType(OpaqueTyId, Substitution), + + /// The anonymous type of a function declaration/definition. Each + /// function has a unique type, which is output (for a function + /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`. + /// + /// This includes tuple struct / enum variant constructors as well. + /// + /// For example the type of `bar` here: + /// + /// ``` + /// fn foo() -> i32 { 1 } + /// let bar = foo; // bar: fn() -> i32 {foo} + /// ``` + FnDef(FnDefId, Substitution), + + /// The pointee of a string slice. Written as `str`. + Str, + + /// The never type `!`. + Never, + + /// The type of a specific closure. + /// + /// The closure signature is stored in a `FnPtr` type in the first type + /// parameter. + Closure(ClosureId, Substitution), + + /// Represents a foreign type declared in external blocks. + ForeignType(ForeignDefId), + + /// A pointer to a function. Written as `fn() -> i32`. + /// + /// For example the type of `bar` here: + /// + /// ``` + /// fn foo() -> i32 { 1 } + /// let bar: fn() -> i32 = foo; + /// ``` + Function(FnPointer), + + /// An "alias" type represents some form of type alias, such as: + /// - An associated type projection like `::Item` + /// - `impl Trait` types + /// - Named type aliases like `type Foo = Vec` + Alias(AliasTy), + + /// A placeholder for a type parameter; for example, `T` in `fn f(x: T) + /// {}` when we're type-checking the body of that function. In this + /// situation, we know this stands for *some* type, but don't know the exact + /// type. + Placeholder(PlaceholderIndex), + + /// A bound type variable. This is used in various places: when representing + /// some polymorphic type like the type of function `fn f`, the type + /// parameters get turned into variables; during trait resolution, inference + /// variables get turned into bound variables and back; and in `Dyn` the + /// `Self` type is represented with a bound variable as well. + BoundVar(BoundVar), + + /// A type variable used during type checking. + InferenceVar(InferenceVar, TyVariableKind), + + /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust). + /// + /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)` + /// represents the `Self` type inside the bounds. This is currently + /// implicit; Chalk has the `Binders` struct to make it explicit, but it + /// didn't seem worth the overhead yet. + Dyn(DynTy), + + /// A placeholder for a type which could not be computed; this is propagated + /// to avoid useless error messages. Doubles as a placeholder where type + /// variables are inserted before type checking, since we want to try to + /// infer a better type here anyway -- for the IDE use case, we want to try + /// to infer as much as possible even in the presence of type errors. + Unknown, +} + +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub struct Ty(Arc); + +impl TyKind { + pub fn intern(self, _interner: &Interner) -> Ty { + Ty(Arc::new(self)) + } +} + +impl Ty { + pub fn kind(&self, _interner: &Interner) -> &TyKind { + &self.0 + } + + pub fn interned_mut(&mut self) -> &mut TyKind { + Arc::make_mut(&mut self.0) + } + + pub fn into_inner(self) -> TyKind { + Arc::try_unwrap(self.0).unwrap_or_else(|a| (*a).clone()) + } +} + +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub struct GenericArg { + interned: GenericArgData, +} + +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub enum GenericArgData { + Ty(Ty), +} + +impl GenericArg { + /// Constructs a generic argument using `GenericArgData`. + pub fn new(_interner: &Interner, data: GenericArgData) -> Self { + GenericArg { interned: data } + } + + /// Gets the interned value. + pub fn interned(&self) -> &GenericArgData { + &self.interned + } + + /// Asserts that this is a type argument. + pub fn assert_ty_ref(&self, interner: &Interner) -> &Ty { + self.ty(interner).unwrap() + } + + /// Checks whether the generic argument is a type. + pub fn is_ty(&self, _interner: &Interner) -> bool { + match self.interned() { + GenericArgData::Ty(_) => true, + } + } + + /// Returns the type if it is one, `None` otherwise. + pub fn ty(&self, _interner: &Interner) -> Option<&Ty> { + match self.interned() { + GenericArgData::Ty(t) => Some(t), + } + } + + pub fn interned_mut(&mut self) -> &mut GenericArgData { + &mut self.interned + } +} + +/// A list of substitutions for generic parameters. +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub struct Substitution(SmallVec<[GenericArg; 2]>); + +impl Substitution { + pub fn interned(&self) -> &[GenericArg] { + &self.0 + } + + pub fn len(&self, _: &Interner) -> usize { + self.0.len() + } + + pub fn is_empty(&self, _: &Interner) -> bool { + self.0.is_empty() + } + + pub fn at(&self, _: &Interner, i: usize) -> &GenericArg { + &self.0[i] + } + + pub fn empty(_: &Interner) -> Substitution { + Substitution(SmallVec::new()) + } + + pub fn iter(&self, _: &Interner) -> std::slice::Iter<'_, GenericArg> { + self.0.iter() + } + + pub fn from_iter( + interner: &Interner, + elements: impl IntoIterator>, + ) -> Self { + Substitution(elements.into_iter().casted(interner).collect()) + } + + // We can hopefully add this to Chalk + pub fn intern(interned: SmallVec<[GenericArg; 2]>) -> Substitution { + Substitution(interned) + } + + pub fn interned_mut(&mut self) -> &mut SmallVec<[GenericArg; 2]> { + &mut self.0 + } +} + +#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)] +pub struct Binders { + pub num_binders: usize, + pub value: T, +} + +/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait. +#[derive(Clone, PartialEq, Eq, Debug, Hash)] +pub struct TraitRef { + pub trait_id: ChalkTraitId, + pub substitution: Substitution, +} + +/// Like `generics::WherePredicate`, but with resolved types: A condition on the +/// parameters of a generic item. +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub enum WhereClause { + /// The given trait needs to be implemented for its type parameters. + Implemented(TraitRef), + /// An associated type bindings like in `Iterator`. + AliasEq(AliasEq), +} + +pub type QuantifiedWhereClause = Binders; + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct QuantifiedWhereClauses(Arc<[QuantifiedWhereClause]>); + +impl QuantifiedWhereClauses { + pub fn from_iter( + _interner: &Interner, + elements: impl IntoIterator, + ) -> Self { + QuantifiedWhereClauses(elements.into_iter().collect()) + } + + pub fn interned(&self) -> &Arc<[QuantifiedWhereClause]> { + &self.0 + } + + pub fn interned_mut(&mut self) -> &mut Arc<[QuantifiedWhereClause]> { + &mut self.0 + } +} + +/// 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 `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 binders: CanonicalVarKinds, +} diff --git a/crates/hir_ty/src/walk.rs b/crates/hir_ty/src/walk.rs new file mode 100644 index 000000000..fec5c2f42 --- /dev/null +++ b/crates/hir_ty/src/walk.rs @@ -0,0 +1,359 @@ +//! The `TypeWalk` trait (probably to be replaced by Chalk's `Fold` and +//! `Visit`). + +use std::mem; + +use chalk_ir::DebruijnIndex; + +use crate::{ + utils::make_mut_slice, AliasTy, Binders, CallableSig, GenericArg, GenericArgData, Interner, + OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, WhereClause, +}; + +/// This allows walking structures that contain types to do something with those +/// types, similar to Chalk's `Fold` trait. +pub trait TypeWalk { + fn walk(&self, f: &mut impl FnMut(&Ty)); + fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { + self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST); + } + /// Walk the type, counting entered binders. + /// + /// `TyKind::Bound` variables use DeBruijn indexing, which means that 0 refers + /// to the innermost binder, 1 to the next, etc.. So when we want to + /// substitute a certain bound variable, we can't just walk the whole type + /// and blindly replace each instance of a certain index; when we 'enter' + /// things that introduce new bound variables, we have to keep track of + /// that. Currently, the only thing that introduces bound variables on our + /// side are `TyKind::Dyn` and `TyKind::Opaque`, which each introduce a bound + /// variable for the self type. + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ); + + fn fold_binders( + mut self, + f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty, + binders: DebruijnIndex, + ) -> Self + where + Self: Sized, + { + self.walk_mut_binders( + &mut |ty_mut, binders| { + let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner)); + *ty_mut = f(ty, binders); + }, + binders, + ); + self + } + + fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self + where + Self: Sized, + { + self.walk_mut(&mut |ty_mut| { + let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner)); + *ty_mut = f(ty); + }); + self + } + + /// Substitutes `TyKind::Bound` vars with the given substitution. + fn subst_bound_vars(self, substs: &Substitution) -> Self + where + Self: Sized, + { + self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST) + } + + /// Substitutes `TyKind::Bound` vars with the given substitution. + fn subst_bound_vars_at_depth(mut self, substs: &Substitution, depth: DebruijnIndex) -> Self + where + Self: Sized, + { + self.walk_mut_binders( + &mut |ty, binders| { + if let &mut TyKind::BoundVar(bound) = ty.interned_mut() { + if bound.debruijn >= binders { + *ty = substs.interned()[bound.index] + .assert_ty_ref(&Interner) + .clone() + .shift_bound_vars(binders); + } + } + }, + depth, + ); + self + } + + /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`. + fn shift_bound_vars(self, n: DebruijnIndex) -> Self + where + Self: Sized, + { + self.fold_binders( + &mut |ty, binders| match ty.kind(&Interner) { + TyKind::BoundVar(bound) if bound.debruijn >= binders => { + TyKind::BoundVar(bound.shifted_in_from(n)).intern(&Interner) + } + _ => ty, + }, + DebruijnIndex::INNERMOST, + ) + } + + /// Shifts debruijn indices of `TyKind::Bound` vars out (down) by `n`. + fn shift_bound_vars_out(self, n: DebruijnIndex) -> Self + where + Self: Sized + std::fmt::Debug, + { + self.fold_binders( + &mut |ty, binders| match ty.kind(&Interner) { + TyKind::BoundVar(bound) if bound.debruijn >= binders => { + TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone())) + .intern(&Interner) + } + _ => ty, + }, + DebruijnIndex::INNERMOST, + ) + } +} + +impl TypeWalk for Ty { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + match self.kind(&Interner) { + TyKind::Alias(AliasTy::Projection(p_ty)) => { + for t in p_ty.substitution.iter(&Interner) { + t.walk(f); + } + } + TyKind::Alias(AliasTy::Opaque(o_ty)) => { + for t in o_ty.substitution.iter(&Interner) { + t.walk(f); + } + } + TyKind::Dyn(dyn_ty) => { + for p in dyn_ty.bounds.value.interned().iter() { + p.walk(f); + } + } + TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => { + ty.walk(f); + } + _ => { + if let Some(substs) = self.substs() { + for t in substs.iter(&Interner) { + t.walk(f); + } + } + } + } + f(self); + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + match self.interned_mut() { + TyKind::Alias(AliasTy::Projection(p_ty)) => { + p_ty.substitution.walk_mut_binders(f, binders); + } + TyKind::Dyn(dyn_ty) => { + for p in make_mut_slice(dyn_ty.bounds.value.interned_mut()) { + p.walk_mut_binders(f, binders.shifted_in()); + } + } + TyKind::Alias(AliasTy::Opaque(o_ty)) => { + o_ty.substitution.walk_mut_binders(f, binders); + } + TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => { + ty.walk_mut_binders(f, binders); + } + _ => { + if let Some(substs) = self.substs_mut() { + substs.walk_mut_binders(f, binders); + } + } + } + f(self, binders); + } +} + +impl TypeWalk for Vec { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + for t in self { + t.walk(f); + } + } + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + for t in self { + t.walk_mut_binders(f, binders); + } + } +} + +impl TypeWalk for OpaqueTy { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + self.substitution.walk(f); + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + self.substitution.walk_mut_binders(f, binders); + } +} + +impl TypeWalk for ProjectionTy { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + self.substitution.walk(f); + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + self.substitution.walk_mut_binders(f, binders); + } +} + +impl TypeWalk for AliasTy { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + match self { + AliasTy::Projection(it) => it.walk(f), + AliasTy::Opaque(it) => it.walk(f), + } + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + match self { + AliasTy::Projection(it) => it.walk_mut_binders(f, binders), + AliasTy::Opaque(it) => it.walk_mut_binders(f, binders), + } + } +} + +impl TypeWalk for GenericArg { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + match &self.interned() { + GenericArgData::Ty(ty) => { + ty.walk(f); + } + } + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + match self.interned_mut() { + GenericArgData::Ty(ty) => { + ty.walk_mut_binders(f, binders); + } + } + } +} + +impl TypeWalk for Substitution { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + for t in self.iter(&Interner) { + t.walk(f); + } + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + for t in self.interned_mut() { + t.walk_mut_binders(f, binders); + } + } +} + +impl TypeWalk for Binders { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + self.value.walk(f); + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + self.value.walk_mut_binders(f, binders.shifted_in()) + } +} + +impl TypeWalk for TraitRef { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + self.substitution.walk(f); + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + self.substitution.walk_mut_binders(f, binders); + } +} + +impl TypeWalk for WhereClause { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + match self { + WhereClause::Implemented(trait_ref) => trait_ref.walk(f), + WhereClause::AliasEq(alias_eq) => alias_eq.walk(f), + } + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + match self { + WhereClause::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders), + WhereClause::AliasEq(alias_eq) => alias_eq.walk_mut_binders(f, binders), + } + } +} + +impl TypeWalk for CallableSig { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + for t in self.params_and_return.iter() { + t.walk(f); + } + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + for t in make_mut_slice(&mut self.params_and_return) { + t.walk_mut_binders(f, binders); + } + } +} -- cgit v1.2.3 From 645a9c3a274109512839b79d8e86a805a39cd6e1 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 4 Apr 2021 20:27:40 +0200 Subject: Move things from `traits` module to `types` as well --- crates/hir/src/lib.rs | 7 +-- crates/hir_ty/src/autoderef.rs | 6 +-- crates/hir_ty/src/db.rs | 2 +- crates/hir_ty/src/infer.rs | 4 +- crates/hir_ty/src/infer/coerce.rs | 2 +- crates/hir_ty/src/infer/expr.rs | 6 +-- crates/hir_ty/src/lib.rs | 2 +- crates/hir_ty/src/method_resolution.rs | 2 +- crates/hir_ty/src/traits.rs | 88 +------------------------------ crates/hir_ty/src/traits/chalk/mapping.rs | 8 ++- crates/hir_ty/src/types.rs | 64 +++++++++++++++++++++- crates/hir_ty/src/walk.rs | 26 ++++++++- 12 files changed, 107 insertions(+), 110 deletions(-) diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs index b9255dd1d..e41efb385 100644 --- a/crates/hir/src/lib.rs +++ b/crates/hir/src/lib.rs @@ -55,10 +55,11 @@ use hir_ty::{ autoderef, could_unify, method_resolution::{self, TyFingerprint}, primitive::UintTy, - traits::{FnTrait, Solution, SolutionVariables}, + traits::FnTrait, AliasEq, AliasTy, BoundVar, CallableDefId, CallableSig, Canonical, CanonicalVarKinds, Cast, - DebruijnIndex, InEnvironment, Interner, QuantifiedWhereClause, Scalar, Substitution, - TraitEnvironment, Ty, TyBuilder, TyDefId, TyKind, TyVariableKind, WhereClause, + DebruijnIndex, InEnvironment, Interner, QuantifiedWhereClause, Scalar, Solution, + SolutionVariables, Substitution, TraitEnvironment, Ty, TyBuilder, TyDefId, TyKind, + TyVariableKind, WhereClause, }; use itertools::Itertools; use rustc_hash::FxHashSet; diff --git a/crates/hir_ty/src/autoderef.rs b/crates/hir_ty/src/autoderef.rs index 70c56cc45..7ca4af80e 100644 --- a/crates/hir_ty/src/autoderef.rs +++ b/crates/hir_ty/src/autoderef.rs @@ -12,10 +12,8 @@ use hir_expand::name::name; use log::{info, warn}; use crate::{ - db::HirDatabase, - traits::{InEnvironment, Solution}, - AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex, Interner, Ty, - TyBuilder, TyKind, + db::HirDatabase, AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex, + InEnvironment, Interner, Solution, Ty, TyBuilder, TyKind, }; const AUTODEREF_RECURSION_LIMIT: usize = 10; diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs index 58e4247c6..4300680d9 100644 --- a/crates/hir_ty/src/db.rs +++ b/crates/hir_ty/src/db.rs @@ -123,7 +123,7 @@ pub trait HirDatabase: DefDatabase + Upcast { &self, krate: CrateId, goal: crate::Canonical>, - ) -> Option; + ) -> Option; #[salsa::invoke(crate::traits::chalk::program_clauses_for_chalk_env_query)] fn program_clauses_for_chalk_env( diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs index 1b1d4458c..bb885db35 100644 --- a/crates/hir_ty/src/infer.rs +++ b/crates/hir_ty/src/infer.rs @@ -37,8 +37,8 @@ use stdx::impl_from; use syntax::SmolStr; use super::{ - traits::{DomainGoal, Guidance, Solution}, - InEnvironment, ProjectionTy, TraitEnvironment, TraitRef, Ty, TypeWalk, + DomainGoal, Guidance, InEnvironment, ProjectionTy, Solution, TraitEnvironment, TraitRef, Ty, + TypeWalk, }; use crate::{ db::HirDatabase, infer::diagnostics::InferenceDiagnostic, lower::ImplTraitLoweringMode, diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs index 028a4d568..32c273afc 100644 --- a/crates/hir_ty/src/infer/coerce.rs +++ b/crates/hir_ty/src/infer/coerce.rs @@ -7,7 +7,7 @@ use chalk_ir::{cast::Cast, Mutability, TyVariableKind}; use hir_def::lang_item::LangItemTarget; -use crate::{autoderef, traits::Solution, Interner, Ty, TyBuilder, TyKind}; +use crate::{autoderef, Interner, Solution, Ty, TyBuilder, TyKind}; use super::{InEnvironment, InferenceContext}; diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs index a87429a24..ccaae53e9 100644 --- a/crates/hir_ty/src/infer/expr.rs +++ b/crates/hir_ty/src/infer/expr.rs @@ -20,10 +20,10 @@ use crate::{ method_resolution, op, primitive::{self, UintTy}, to_chalk_trait_id, - traits::{chalk::from_chalk, FnTrait, InEnvironment}, + traits::{chalk::from_chalk, FnTrait}, utils::{generics, variant_data, Generics}, - AdtId, Binders, CallableDefId, FnPointer, FnSig, Interner, Rawness, Scalar, Substitution, - TraitRef, Ty, TyBuilder, TyKind, + AdtId, Binders, CallableDefId, FnPointer, FnSig, InEnvironment, Interner, Rawness, Scalar, + Substitution, TraitRef, Ty, TyBuilder, TyKind, }; use super::{ diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs index 40abbce42..76609e2df 100644 --- a/crates/hir_ty/src/lib.rs +++ b/crates/hir_ty/src/lib.rs @@ -49,7 +49,7 @@ pub use lower::{ associated_type_shorthand_candidates, callable_item_sig, CallableDefId, ImplTraitLoweringMode, TyDefId, TyLoweringContext, ValueTyDefId, }; -pub use traits::{AliasEq, DomainGoal, InEnvironment, TraitEnvironment}; +pub use traits::TraitEnvironment; pub use types::*; pub use walk::TypeWalk; diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs index a76586f0c..0e4a620b6 100644 --- a/crates/hir_ty/src/method_resolution.rs +++ b/crates/hir_ty/src/method_resolution.rs @@ -800,7 +800,7 @@ pub fn implements_trait_unique( let goal = generic_implements_goal(db, env, trait_, ty.clone()); let solution = db.trait_solve(krate, goal); - matches!(solution, Some(crate::traits::Solution::Unique(_))) + matches!(solution, Some(crate::Solution::Unique(_))) } /// This creates Substs for a trait with the given Self type and type variables diff --git a/crates/hir_ty/src/traits.rs b/crates/hir_ty/src/traits.rs index e5e8cff33..66d600bfc 100644 --- a/crates/hir_ty/src/traits.rs +++ b/crates/hir_ty/src/traits.rs @@ -8,8 +8,8 @@ use hir_def::{lang_item::LangItemTarget, TraitId}; use stdx::panic_context; use crate::{ - db::HirDatabase, AliasTy, Canonical, DebruijnIndex, HirDisplay, Substitution, Ty, TyKind, - TypeWalk, WhereClause, + db::HirDatabase, AliasEq, AliasTy, Canonical, DomainGoal, Guidance, HirDisplay, InEnvironment, + Solution, SolutionVariables, Ty, TyKind, WhereClause, }; use self::chalk::{from_chalk, Interner, ToChalk}; @@ -70,55 +70,6 @@ impl Default for TraitEnvironment { } } -/// Something (usually a goal), along with an environment. -#[derive(Clone, Debug, PartialEq, Eq, Hash)] -pub struct InEnvironment { - pub environment: chalk_ir::Environment, - pub goal: T, -} - -impl InEnvironment { - pub fn new(environment: chalk_ir::Environment, value: T) -> InEnvironment { - InEnvironment { environment, goal: value } - } -} - -/// Something that needs to be proven (by Chalk) during type checking, e.g. that -/// a certain type implements a certain trait. Proving the Obligation might -/// result in additional information about inference variables. -#[derive(Clone, Debug, PartialEq, Eq, Hash)] -pub enum DomainGoal { - Holds(WhereClause), -} - -#[derive(Clone, Debug, PartialEq, Eq, Hash)] -pub struct AliasEq { - pub alias: AliasTy, - pub ty: Ty, -} - -impl TypeWalk for AliasEq { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - self.ty.walk(f); - match &self.alias { - AliasTy::Projection(projection_ty) => projection_ty.walk(f), - AliasTy::Opaque(opaque) => opaque.walk(f), - } - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - self.ty.walk_mut_binders(f, binders); - match &mut self.alias { - AliasTy::Projection(projection_ty) => projection_ty.walk_mut_binders(f, binders), - AliasTy::Opaque(opaque) => opaque.walk_mut_binders(f, binders), - } - } -} - /// Solve a trait goal using Chalk. pub(crate) fn trait_solve_query( db: &dyn HirDatabase, @@ -246,41 +197,6 @@ fn solution_from_chalk( } } -#[derive(Clone, Debug, PartialEq, Eq)] -pub struct SolutionVariables(pub Canonical); - -#[derive(Clone, Debug, PartialEq, Eq)] -/// A (possible) solution for a proposed goal. -pub enum Solution { - /// The goal indeed holds, and there is a unique value for all existential - /// variables. - Unique(SolutionVariables), - - /// The goal may be provable in multiple ways, but regardless we may have some guidance - /// for type inference. In this case, we don't return any lifetime - /// constraints, since we have not "committed" to any particular solution - /// yet. - Ambig(Guidance), -} - -#[derive(Clone, Debug, PartialEq, Eq)] -/// When a goal holds ambiguously (e.g., because there are multiple possible -/// solutions), we issue a set of *guidance* back to type inference. -pub enum Guidance { - /// The existential variables *must* have the given values if the goal is - /// ever to hold, but that alone isn't enough to guarantee the goal will - /// actually hold. - Definite(SolutionVariables), - - /// There are multiple plausible values for the existentials, but the ones - /// here are suggested as the preferred choice heuristically. These should - /// be used for inference fallback only. - Suggested(SolutionVariables), - - /// There's no useful information to feed back to type inference - Unknown, -} - #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] pub enum FnTrait { FnOnce, diff --git a/crates/hir_ty/src/traits/chalk/mapping.rs b/crates/hir_ty/src/traits/chalk/mapping.rs index 3a5800885..5e4f97a46 100644 --- a/crates/hir_ty/src/traits/chalk/mapping.rs +++ b/crates/hir_ty/src/traits/chalk/mapping.rs @@ -10,11 +10,9 @@ use base_db::salsa::InternKey; use hir_def::{GenericDefId, TypeAliasId}; use crate::{ - db::HirDatabase, - primitive::UintTy, - traits::{Canonical, DomainGoal}, - AliasTy, CallableDefId, FnPointer, GenericArg, InEnvironment, OpaqueTy, ProjectionTy, - QuantifiedWhereClause, Scalar, Substitution, TraitRef, Ty, TypeWalk, WhereClause, + db::HirDatabase, primitive::UintTy, AliasTy, CallableDefId, Canonical, DomainGoal, FnPointer, + GenericArg, InEnvironment, OpaqueTy, ProjectionTy, QuantifiedWhereClause, Scalar, Substitution, + TraitRef, Ty, TypeWalk, WhereClause, }; use super::interner::*; diff --git a/crates/hir_ty/src/types.rs b/crates/hir_ty/src/types.rs index d00f8e9ab..53662fcdc 100644 --- a/crates/hir_ty/src/types.rs +++ b/crates/hir_ty/src/types.rs @@ -11,7 +11,7 @@ use hir_def::LifetimeParamId; use smallvec::SmallVec; use crate::{ - AliasEq, AssocTypeId, CanonicalVarKinds, ChalkTraitId, ClosureId, FnDefId, FnSig, ForeignDefId, + AssocTypeId, CanonicalVarKinds, ChalkTraitId, ClosureId, FnDefId, FnSig, ForeignDefId, InferenceVar, Interner, OpaqueTyId, PlaceholderIndex, }; @@ -352,3 +352,65 @@ pub struct Canonical { pub value: T, pub binders: CanonicalVarKinds, } + +/// Something (usually a goal), along with an environment. +#[derive(Clone, Debug, PartialEq, Eq, Hash)] +pub struct InEnvironment { + pub environment: chalk_ir::Environment, + pub goal: T, +} + +impl InEnvironment { + pub fn new(environment: chalk_ir::Environment, value: T) -> InEnvironment { + InEnvironment { environment, goal: value } + } +} + +/// Something that needs to be proven (by Chalk) during type checking, e.g. that +/// a certain type implements a certain trait. Proving the Obligation might +/// result in additional information about inference variables. +#[derive(Clone, Debug, PartialEq, Eq, Hash)] +pub enum DomainGoal { + Holds(WhereClause), +} + +#[derive(Clone, Debug, PartialEq, Eq, Hash)] +pub struct AliasEq { + pub alias: AliasTy, + pub ty: Ty, +} + +#[derive(Clone, Debug, PartialEq, Eq)] +pub struct SolutionVariables(pub Canonical); + +#[derive(Clone, Debug, PartialEq, Eq)] +/// A (possible) solution for a proposed goal. +pub enum Solution { + /// The goal indeed holds, and there is a unique value for all existential + /// variables. + Unique(SolutionVariables), + + /// The goal may be provable in multiple ways, but regardless we may have some guidance + /// for type inference. In this case, we don't return any lifetime + /// constraints, since we have not "committed" to any particular solution + /// yet. + Ambig(Guidance), +} + +#[derive(Clone, Debug, PartialEq, Eq)] +/// When a goal holds ambiguously (e.g., because there are multiple possible +/// solutions), we issue a set of *guidance* back to type inference. +pub enum Guidance { + /// The existential variables *must* have the given values if the goal is + /// ever to hold, but that alone isn't enough to guarantee the goal will + /// actually hold. + Definite(SolutionVariables), + + /// There are multiple plausible values for the existentials, but the ones + /// here are suggested as the preferred choice heuristically. These should + /// be used for inference fallback only. + Suggested(SolutionVariables), + + /// There's no useful information to feed back to type inference + Unknown, +} diff --git a/crates/hir_ty/src/walk.rs b/crates/hir_ty/src/walk.rs index fec5c2f42..bfb3f1041 100644 --- a/crates/hir_ty/src/walk.rs +++ b/crates/hir_ty/src/walk.rs @@ -6,8 +6,8 @@ use std::mem; use chalk_ir::DebruijnIndex; use crate::{ - utils::make_mut_slice, AliasTy, Binders, CallableSig, GenericArg, GenericArgData, Interner, - OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, WhereClause, + utils::make_mut_slice, AliasEq, AliasTy, Binders, CallableSig, GenericArg, GenericArgData, + Interner, OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, WhereClause, }; /// This allows walking structures that contain types to do something with those @@ -357,3 +357,25 @@ impl TypeWalk for CallableSig { } } } + +impl TypeWalk for AliasEq { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + self.ty.walk(f); + match &self.alias { + AliasTy::Projection(projection_ty) => projection_ty.walk(f), + AliasTy::Opaque(opaque) => opaque.walk(f), + } + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + self.ty.walk_mut_binders(f, binders); + match &mut self.alias { + AliasTy::Projection(projection_ty) => projection_ty.walk_mut_binders(f, binders), + AliasTy::Opaque(opaque) => opaque.walk_mut_binders(f, binders), + } + } +} -- cgit v1.2.3