1 //! The type system. We currently use this to infer types for completion, hover
2 //! information and various assists.
4 macro_rules! eprintln {
5 ($($tt:tt)*) => { stdx::eprintln!($($tt)*) };
11 pub mod method_resolution;
34 use itertools::Itertools;
38 expr::ExprId, type_ref::Rawness, AssocContainerId, ConstParamId, FunctionId, GenericDefId,
39 HasModule, LifetimeParamId, Lookup, TraitId, TypeAliasId, TypeParamId,
42 use crate::{db::HirDatabase, display::HirDisplay, utils::generics};
44 pub use autoderef::autoderef;
45 pub use builder::TyBuilder;
46 pub use chalk_ext::{ProjectionTyExt, TyExt};
47 pub use infer::{could_unify, InferenceResult, InferenceVar};
49 associated_type_shorthand_candidates, callable_item_sig, CallableDefId, ImplTraitLoweringMode,
50 TyDefId, TyLoweringContext, ValueTyDefId,
52 pub use traits::{chalk::Interner, TraitEnvironment};
54 pub use walk::TypeWalk;
57 cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind,
60 pub type ForeignDefId = chalk_ir::ForeignDefId<Interner>;
61 pub type AssocTypeId = chalk_ir::AssocTypeId<Interner>;
62 pub type FnDefId = chalk_ir::FnDefId<Interner>;
63 pub type ClosureId = chalk_ir::ClosureId<Interner>;
64 pub type OpaqueTyId = chalk_ir::OpaqueTyId<Interner>;
65 pub type PlaceholderIndex = chalk_ir::PlaceholderIndex;
67 pub type VariableKind = chalk_ir::VariableKind<Interner>;
68 pub type VariableKinds = chalk_ir::VariableKinds<Interner>;
69 pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>;
71 pub type Lifetime = chalk_ir::Lifetime<Interner>;
72 pub type LifetimeData = chalk_ir::LifetimeData<Interner>;
73 pub type LifetimeOutlives = chalk_ir::LifetimeOutlives<Interner>;
75 pub type Const = chalk_ir::Const<Interner>;
76 pub type ConstData = chalk_ir::ConstData<Interner>;
77 pub type ConstValue = chalk_ir::ConstValue<Interner>;
78 pub type ConcreteConst = chalk_ir::ConcreteConst<Interner>;
80 pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
82 pub type FnSig = chalk_ir::FnSig<Interner>;
84 // FIXME: get rid of this
85 pub fn subst_prefix(s: &Substitution, n: usize) -> Substitution {
86 Substitution::intern(s.interned()[..std::cmp::min(s.len(&Interner), n)].into())
89 /// Return an index of a parameter in the generic type parameter list by it's id.
90 pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option<usize> {
91 generics(db.upcast(), id.parent).param_idx(id)
94 pub fn wrap_empty_binders<T>(value: T) -> Binders<T>
98 Binders::empty(&Interner, value.shifted_in_from(DebruijnIndex::ONE))
101 pub fn make_only_type_binders<T>(num_vars: usize, value: T) -> Binders<T> {
103 VariableKinds::from_iter(
105 std::iter::repeat(chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General))
113 pub fn hir_trait_id(&self) -> TraitId {
114 from_chalk_trait_id(self.trait_id)
118 impl<T> Canonical<T> {
119 pub fn new(value: T, kinds: impl IntoIterator<Item = TyVariableKind>) -> Self {
120 let kinds = kinds.into_iter().map(|tk| {
121 chalk_ir::CanonicalVarKind::new(
122 chalk_ir::VariableKind::Ty(tk),
123 chalk_ir::UniverseIndex::ROOT,
126 Self { value, binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds) }
130 /// A function signature as seen by type inference: Several parameter types and
132 #[derive(Clone, PartialEq, Eq, Debug)]
133 pub struct CallableSig {
134 params_and_return: Arc<[Ty]>,
138 /// A polymorphic function signature.
139 pub type PolyFnSig = Binders<CallableSig>;
142 pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty, is_varargs: bool) -> CallableSig {
144 CallableSig { params_and_return: params.into(), is_varargs }
147 pub fn from_fn_ptr(fn_ptr: &FnPointer) -> CallableSig {
149 // FIXME: what to do about lifetime params? -> return PolyFnSig
150 params_and_return: fn_ptr
153 .shifted_out_to(DebruijnIndex::ONE)
154 .expect("unexpected lifetime vars in fn ptr")
158 .map(|arg| arg.assert_ty_ref(&Interner).clone())
160 is_varargs: fn_ptr.sig.variadic,
164 pub fn params(&self) -> &[Ty] {
165 &self.params_and_return[0..self.params_and_return.len() - 1]
168 pub fn ret(&self) -> &Ty {
169 &self.params_and_return[self.params_and_return.len() - 1]
174 pub fn as_reference(&self) -> Option<(&Ty, Lifetime, Mutability)> {
175 match self.kind(&Interner) {
176 TyKind::Ref(mutability, lifetime, ty) => Some((ty, *lifetime, *mutability)),
181 pub fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)> {
182 match self.kind(&Interner) {
183 TyKind::Ref(mutability, _, ty) => Some((ty, Rawness::Ref, *mutability)),
184 TyKind::Raw(mutability, ty) => Some((ty, Rawness::RawPtr, *mutability)),
189 pub fn strip_references(&self) -> &Ty {
190 let mut t: &Ty = self;
192 while let TyKind::Ref(_mutability, _lifetime, ty) = t.kind(&Interner) {
199 pub fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)> {
200 match self.kind(&Interner) {
201 TyKind::Adt(AdtId(adt), parameters) => Some((*adt, parameters)),
206 pub fn as_tuple(&self) -> Option<&Substitution> {
207 match self.kind(&Interner) {
208 TyKind::Tuple(_, substs) => Some(substs),
213 pub fn as_generic_def(&self, db: &dyn HirDatabase) -> Option<GenericDefId> {
214 match *self.kind(&Interner) {
215 TyKind::Adt(AdtId(adt), ..) => Some(adt.into()),
216 TyKind::FnDef(callable, ..) => {
217 Some(db.lookup_intern_callable_def(callable.into()).into())
219 TyKind::AssociatedType(type_alias, ..) => Some(from_assoc_type_id(type_alias).into()),
220 TyKind::Foreign(type_alias, ..) => Some(from_foreign_def_id(type_alias).into()),
225 pub fn is_never(&self) -> bool {
226 matches!(self.kind(&Interner), TyKind::Never)
229 pub fn is_unknown(&self) -> bool {
230 matches!(self.kind(&Interner), TyKind::Error)
233 pub fn equals_ctor(&self, other: &Ty) -> bool {
234 match (self.kind(&Interner), other.kind(&Interner)) {
235 (TyKind::Adt(adt, ..), TyKind::Adt(adt2, ..)) => adt == adt2,
236 (TyKind::Slice(_), TyKind::Slice(_)) | (TyKind::Array(_, _), TyKind::Array(_, _)) => {
239 (TyKind::FnDef(def_id, ..), TyKind::FnDef(def_id2, ..)) => def_id == def_id2,
240 (TyKind::OpaqueType(ty_id, ..), TyKind::OpaqueType(ty_id2, ..)) => ty_id == ty_id2,
241 (TyKind::AssociatedType(ty_id, ..), TyKind::AssociatedType(ty_id2, ..)) => {
244 (TyKind::Foreign(ty_id, ..), TyKind::Foreign(ty_id2, ..)) => ty_id == ty_id2,
245 (TyKind::Closure(id1, _), TyKind::Closure(id2, _)) => id1 == id2,
246 (TyKind::Ref(mutability, ..), TyKind::Ref(mutability2, ..))
247 | (TyKind::Raw(mutability, ..), TyKind::Raw(mutability2, ..)) => {
248 mutability == mutability2
251 TyKind::Function(FnPointer { num_binders, sig, .. }),
252 TyKind::Function(FnPointer { num_binders: num_binders2, sig: sig2, .. }),
253 ) => num_binders == num_binders2 && sig == sig2,
254 (TyKind::Tuple(cardinality, _), TyKind::Tuple(cardinality2, _)) => {
255 cardinality == cardinality2
257 (TyKind::Str, TyKind::Str) | (TyKind::Never, TyKind::Never) => true,
258 (TyKind::Scalar(scalar), TyKind::Scalar(scalar2)) => scalar == scalar2,
263 /// If this is a `dyn Trait` type, this returns the `Trait` part.
264 fn dyn_trait_ref(&self) -> Option<&TraitRef> {
265 match self.kind(&Interner) {
266 TyKind::Dyn(dyn_ty) => dyn_ty.bounds.skip_binders().interned().get(0).and_then(|b| {
267 match b.skip_binders() {
268 WhereClause::Implemented(trait_ref) => Some(trait_ref),
276 /// If this is a `dyn Trait`, returns that trait.
277 pub fn dyn_trait(&self) -> Option<TraitId> {
278 self.dyn_trait_ref().map(|it| it.trait_id).map(from_chalk_trait_id)
281 fn builtin_deref(&self) -> Option<Ty> {
282 match self.kind(&Interner) {
283 TyKind::Ref(.., ty) => Some(ty.clone()),
284 TyKind::Raw(.., ty) => Some(ty.clone()),
289 pub fn callable_def(&self, db: &dyn HirDatabase) -> Option<CallableDefId> {
290 match self.kind(&Interner) {
291 &TyKind::FnDef(def, ..) => Some(db.lookup_intern_callable_def(def.into())),
296 pub fn as_fn_def(&self, db: &dyn HirDatabase) -> Option<FunctionId> {
297 if let Some(CallableDefId::FunctionId(func)) = self.callable_def(db) {
304 pub fn callable_sig(&self, db: &dyn HirDatabase) -> Option<CallableSig> {
305 match self.kind(&Interner) {
306 TyKind::Function(fn_ptr) => Some(CallableSig::from_fn_ptr(fn_ptr)),
307 TyKind::FnDef(def, parameters) => {
308 let callable_def = db.lookup_intern_callable_def((*def).into());
309 let sig = db.callable_item_signature(callable_def);
310 Some(sig.substitute(&Interner, ¶meters))
312 TyKind::Closure(.., substs) => {
313 let sig_param = substs.at(&Interner, 0).assert_ty_ref(&Interner);
314 sig_param.callable_sig(db)
320 /// Returns the type parameters of this type if it has some (i.e. is an ADT
321 /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
322 pub fn substs(&self) -> Option<&Substitution> {
323 match self.kind(&Interner) {
324 TyKind::Adt(_, substs)
325 | TyKind::FnDef(_, substs)
326 | TyKind::Tuple(_, substs)
327 | TyKind::OpaqueType(_, substs)
328 | TyKind::AssociatedType(_, substs)
329 | TyKind::Closure(.., substs) => Some(substs),
330 TyKind::Function(FnPointer { substitution: substs, .. }) => Some(&substs.0),
335 fn substs_mut(&mut self) -> Option<&mut Substitution> {
336 match self.interned_mut() {
337 TyKind::Adt(_, substs)
338 | TyKind::FnDef(_, substs)
339 | TyKind::Tuple(_, substs)
340 | TyKind::OpaqueType(_, substs)
341 | TyKind::AssociatedType(_, substs)
342 | TyKind::Closure(.., substs) => Some(substs),
343 TyKind::Function(FnPointer { substitution: substs, .. }) => Some(&mut substs.0),
348 pub fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<QuantifiedWhereClause>> {
349 match self.kind(&Interner) {
350 TyKind::OpaqueType(opaque_ty_id, ..) => {
351 match db.lookup_intern_impl_trait_id((*opaque_ty_id).into()) {
352 ImplTraitId::AsyncBlockTypeImplTrait(def, _expr) => {
353 let krate = def.module(db.upcast()).krate();
354 if let Some(future_trait) = db
355 .lang_item(krate, "future_trait".into())
356 .and_then(|item| item.as_trait())
358 // This is only used by type walking.
359 // Parameters will be walked outside, and projection predicate is not used.
360 // So just provide the Future trait.
361 let impl_bound = Binders::empty(
363 WhereClause::Implemented(TraitRef {
364 trait_id: to_chalk_trait_id(future_trait),
365 substitution: Substitution::empty(&Interner),
368 Some(vec![impl_bound])
373 ImplTraitId::ReturnTypeImplTrait(..) => None,
376 TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
377 let predicates = match db.lookup_intern_impl_trait_id(opaque_ty.opaque_ty_id.into())
379 ImplTraitId::ReturnTypeImplTrait(func, idx) => {
380 db.return_type_impl_traits(func).map(|it| {
383 .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
384 data.substitute(&Interner, &opaque_ty.substitution)
387 // It always has an parameter for Future::Output type.
388 ImplTraitId::AsyncBlockTypeImplTrait(..) => unreachable!(),
391 predicates.map(|it| it.into_value_and_skipped_binders().0)
393 TyKind::Placeholder(idx) => {
394 let id = from_placeholder_idx(db, *idx);
395 let generic_params = db.generic_params(id.parent);
396 let param_data = &generic_params.types[id.local_id];
397 match param_data.provenance {
398 hir_def::generics::TypeParamProvenance::ArgumentImplTrait => {
399 let substs = TyBuilder::type_params_subst(db, id.parent);
401 .generic_predicates(id.parent)
403 .map(|pred| pred.clone().substitute(&Interner, &substs))
404 .filter(|wc| match &wc.skip_binders() {
405 WhereClause::Implemented(tr) => {
406 tr.self_type_parameter(&Interner) == self
408 WhereClause::AliasEq(AliasEq {
409 alias: AliasTy::Projection(proj),
411 }) => proj.self_type_parameter(&Interner) == self,
425 pub fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId> {
426 match self.kind(&Interner) {
427 TyKind::AssociatedType(id, ..) => {
428 match from_assoc_type_id(*id).lookup(db.upcast()).container {
429 AssocContainerId::TraitId(trait_id) => Some(trait_id),
433 TyKind::Alias(AliasTy::Projection(projection_ty)) => {
434 match from_assoc_type_id(projection_ty.associated_ty_id)
438 AssocContainerId::TraitId(trait_id) => Some(trait_id),
447 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
448 pub enum ImplTraitId {
449 ReturnTypeImplTrait(hir_def::FunctionId, u16),
450 AsyncBlockTypeImplTrait(hir_def::DefWithBodyId, ExprId),
453 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
454 pub struct ReturnTypeImplTraits {
455 pub(crate) impl_traits: Vec<ReturnTypeImplTrait>,
458 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
459 pub(crate) struct ReturnTypeImplTrait {
460 pub(crate) bounds: Binders<Vec<QuantifiedWhereClause>>,
463 pub fn to_foreign_def_id(id: TypeAliasId) -> ForeignDefId {
464 chalk_ir::ForeignDefId(salsa::InternKey::as_intern_id(&id))
467 pub fn from_foreign_def_id(id: ForeignDefId) -> TypeAliasId {
468 salsa::InternKey::from_intern_id(id.0)
471 pub fn to_assoc_type_id(id: TypeAliasId) -> AssocTypeId {
472 chalk_ir::AssocTypeId(salsa::InternKey::as_intern_id(&id))
475 pub fn from_assoc_type_id(id: AssocTypeId) -> TypeAliasId {
476 salsa::InternKey::from_intern_id(id.0)
479 pub fn from_placeholder_idx(db: &dyn HirDatabase, idx: PlaceholderIndex) -> TypeParamId {
480 assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT);
481 let interned_id = salsa::InternKey::from_intern_id(salsa::InternId::from(idx.idx));
482 db.lookup_intern_type_param_id(interned_id)
485 pub fn to_placeholder_idx(db: &dyn HirDatabase, id: TypeParamId) -> PlaceholderIndex {
486 let interned_id = db.intern_type_param_id(id);
488 ui: chalk_ir::UniverseIndex::ROOT,
489 idx: salsa::InternKey::as_intern_id(&interned_id).as_usize(),
493 pub fn lt_from_placeholder_idx(db: &dyn HirDatabase, idx: PlaceholderIndex) -> LifetimeParamId {
494 assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT);
495 let interned_id = salsa::InternKey::from_intern_id(salsa::InternId::from(idx.idx));
496 db.lookup_intern_lifetime_param_id(interned_id)
499 pub fn const_from_placeholder_idx(db: &dyn HirDatabase, idx: PlaceholderIndex) -> ConstParamId {
500 assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT);
501 let interned_id = salsa::InternKey::from_intern_id(salsa::InternId::from(idx.idx));
502 db.lookup_intern_const_param_id(interned_id)
505 pub fn to_chalk_trait_id(id: TraitId) -> ChalkTraitId {
506 chalk_ir::TraitId(salsa::InternKey::as_intern_id(&id))
509 pub fn from_chalk_trait_id(id: ChalkTraitId) -> TraitId {
510 salsa::InternKey::from_intern_id(id.0)
513 pub fn static_lifetime() -> Lifetime {
514 LifetimeData::Static.intern(&Interner)
517 pub fn dummy_usize_const() -> Const {
518 let usize_ty = chalk_ir::TyKind::Scalar(Scalar::Uint(UintTy::Usize)).intern(&Interner);
519 chalk_ir::ConstData {
521 value: chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst { interned: () }),