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;
33 use itertools::Itertools;
34 use smallvec::SmallVec;
38 expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule, Lookup,
39 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::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::TraitEnvironment;
54 pub use walk::TypeWalk;
57 cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind,
60 pub use crate::traits::chalk::Interner;
62 pub type ForeignDefId = chalk_ir::ForeignDefId<Interner>;
63 pub type AssocTypeId = chalk_ir::AssocTypeId<Interner>;
64 pub type FnDefId = chalk_ir::FnDefId<Interner>;
65 pub type ClosureId = chalk_ir::ClosureId<Interner>;
66 pub type OpaqueTyId = chalk_ir::OpaqueTyId<Interner>;
67 pub type PlaceholderIndex = chalk_ir::PlaceholderIndex;
69 pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>;
71 pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
74 pub fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef {
76 trait_id: to_chalk_trait_id(self.trait_(db)),
77 substitution: self.substitution.clone(),
81 pub fn self_type_parameter(&self) -> &Ty {
82 &self.substitution.interned()[0].assert_ty_ref(&Interner)
85 fn trait_(&self, db: &dyn HirDatabase) -> TraitId {
86 match from_assoc_type_id(self.associated_ty_id).lookup(db.upcast()).container {
87 AssocContainerId::TraitId(it) => it,
88 _ => panic!("projection ty without parent trait"),
93 pub type FnSig = chalk_ir::FnSig<Interner>;
96 pub fn single(ty: Ty) -> Substitution {
97 Substitution::intern({
98 let mut v = SmallVec::new();
99 v.push(ty.cast(&Interner));
104 pub fn prefix(&self, n: usize) -> Substitution {
105 Substitution::intern(self.interned()[..std::cmp::min(self.len(&Interner), n)].into())
108 pub fn suffix(&self, n: usize) -> Substitution {
109 Substitution::intern(
110 self.interned()[self.len(&Interner) - std::cmp::min(self.len(&Interner), n)..].into(),
115 /// Return an index of a parameter in the generic type parameter list by it's id.
116 pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option<usize> {
117 generics(db.upcast(), id.parent).param_idx(id)
121 pub fn new(num_binders: usize, value: T) -> Self {
122 Self { num_binders, value }
125 pub fn wrap_empty(value: T) -> Self
129 Self { num_binders: 0, value: value.shift_bound_vars(DebruijnIndex::ONE) }
132 pub fn as_ref(&self) -> Binders<&T> {
133 Binders { num_binders: self.num_binders, value: &self.value }
136 pub fn map<U>(self, f: impl FnOnce(T) -> U) -> Binders<U> {
137 Binders { num_binders: self.num_binders, value: f(self.value) }
140 pub fn filter_map<U>(self, f: impl FnOnce(T) -> Option<U>) -> Option<Binders<U>> {
141 Some(Binders { num_binders: self.num_binders, value: f(self.value)? })
144 pub fn skip_binders(&self) -> &T {
148 pub fn into_value_and_skipped_binders(self) -> (T, usize) {
149 (self.value, self.num_binders)
153 impl<T: Clone> Binders<&T> {
154 pub fn cloned(&self) -> Binders<T> {
155 Binders { num_binders: self.num_binders, value: self.value.clone() }
159 impl<T: TypeWalk> Binders<T> {
160 /// Substitutes all variables.
161 pub fn subst(self, subst: &Substitution) -> T {
162 assert_eq!(subst.len(&Interner), self.num_binders);
163 self.value.subst_bound_vars(subst)
168 pub fn self_type_parameter(&self) -> &Ty {
169 &self.substitution.at(&Interner, 0).assert_ty_ref(&Interner)
172 pub fn hir_trait_id(&self) -> TraitId {
173 from_chalk_trait_id(self.trait_id)
178 pub fn is_implemented(&self) -> bool {
179 matches!(self, WhereClause::Implemented(_))
182 pub fn trait_ref(&self, db: &dyn HirDatabase) -> Option<TraitRef> {
184 WhereClause::Implemented(tr) => Some(tr.clone()),
185 WhereClause::AliasEq(AliasEq { alias: AliasTy::Projection(proj), .. }) => {
186 Some(proj.trait_ref(db))
188 WhereClause::AliasEq(_) => None,
193 impl<T> Canonical<T> {
194 pub fn new(value: T, kinds: impl IntoIterator<Item = TyVariableKind>) -> Self {
195 let kinds = kinds.into_iter().map(|tk| {
196 chalk_ir::CanonicalVarKind::new(
197 chalk_ir::VariableKind::Ty(tk),
198 chalk_ir::UniverseIndex::ROOT,
201 Self { value, binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds) }
205 /// A function signature as seen by type inference: Several parameter types and
207 #[derive(Clone, PartialEq, Eq, Debug)]
208 pub struct CallableSig {
209 params_and_return: Arc<[Ty]>,
213 /// A polymorphic function signature.
214 pub type PolyFnSig = Binders<CallableSig>;
217 pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty, is_varargs: bool) -> CallableSig {
219 CallableSig { params_and_return: params.into(), is_varargs }
222 pub fn from_fn_ptr(fn_ptr: &FnPointer) -> CallableSig {
224 // FIXME: what to do about lifetime params? -> return PolyFnSig
225 params_and_return: fn_ptr
228 .shift_bound_vars_out(DebruijnIndex::ONE)
231 .map(|arg| arg.assert_ty_ref(&Interner).clone())
233 is_varargs: fn_ptr.sig.variadic,
237 pub fn params(&self) -> &[Ty] {
238 &self.params_and_return[0..self.params_and_return.len() - 1]
241 pub fn ret(&self) -> &Ty {
242 &self.params_and_return[self.params_and_return.len() - 1]
247 pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
248 match self.kind(&Interner) {
249 TyKind::Ref(mutability, ty) => Some((ty, *mutability)),
254 pub fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)> {
255 match self.kind(&Interner) {
256 TyKind::Ref(mutability, ty) => Some((ty, Rawness::Ref, *mutability)),
257 TyKind::Raw(mutability, ty) => Some((ty, Rawness::RawPtr, *mutability)),
262 pub fn strip_references(&self) -> &Ty {
263 let mut t: &Ty = self;
265 while let TyKind::Ref(_mutability, ty) = t.kind(&Interner) {
272 pub fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)> {
273 match self.kind(&Interner) {
274 TyKind::Adt(AdtId(adt), parameters) => Some((*adt, parameters)),
279 pub fn as_tuple(&self) -> Option<&Substitution> {
280 match self.kind(&Interner) {
281 TyKind::Tuple(_, substs) => Some(substs),
286 pub fn as_generic_def(&self, db: &dyn HirDatabase) -> Option<GenericDefId> {
287 match *self.kind(&Interner) {
288 TyKind::Adt(AdtId(adt), ..) => Some(adt.into()),
289 TyKind::FnDef(callable, ..) => {
290 Some(db.lookup_intern_callable_def(callable.into()).into())
292 TyKind::AssociatedType(type_alias, ..) => Some(from_assoc_type_id(type_alias).into()),
293 TyKind::ForeignType(type_alias, ..) => Some(from_foreign_def_id(type_alias).into()),
298 pub fn is_never(&self) -> bool {
299 matches!(self.kind(&Interner), TyKind::Never)
302 pub fn is_unknown(&self) -> bool {
303 matches!(self.kind(&Interner), TyKind::Error)
306 pub fn equals_ctor(&self, other: &Ty) -> bool {
307 match (self.kind(&Interner), other.kind(&Interner)) {
308 (TyKind::Adt(adt, ..), TyKind::Adt(adt2, ..)) => adt == adt2,
309 (TyKind::Slice(_), TyKind::Slice(_)) | (TyKind::Array(_), TyKind::Array(_)) => true,
310 (TyKind::FnDef(def_id, ..), TyKind::FnDef(def_id2, ..)) => def_id == def_id2,
311 (TyKind::OpaqueType(ty_id, ..), TyKind::OpaqueType(ty_id2, ..)) => ty_id == ty_id2,
312 (TyKind::AssociatedType(ty_id, ..), TyKind::AssociatedType(ty_id2, ..)) => {
315 (TyKind::ForeignType(ty_id, ..), TyKind::ForeignType(ty_id2, ..)) => ty_id == ty_id2,
316 (TyKind::Closure(id1, _), TyKind::Closure(id2, _)) => id1 == id2,
317 (TyKind::Ref(mutability, ..), TyKind::Ref(mutability2, ..))
318 | (TyKind::Raw(mutability, ..), TyKind::Raw(mutability2, ..)) => {
319 mutability == mutability2
322 TyKind::Function(FnPointer { num_args, sig, .. }),
323 TyKind::Function(FnPointer { num_args: num_args2, sig: sig2, .. }),
324 ) => num_args == num_args2 && sig == sig2,
325 (TyKind::Tuple(cardinality, _), TyKind::Tuple(cardinality2, _)) => {
326 cardinality == cardinality2
328 (TyKind::Str, TyKind::Str) | (TyKind::Never, TyKind::Never) => true,
329 (TyKind::Scalar(scalar), TyKind::Scalar(scalar2)) => scalar == scalar2,
334 /// If this is a `dyn Trait` type, this returns the `Trait` part.
335 fn dyn_trait_ref(&self) -> Option<&TraitRef> {
336 match self.kind(&Interner) {
337 TyKind::Dyn(dyn_ty) => {
338 dyn_ty.bounds.value.interned().get(0).and_then(|b| match b.skip_binders() {
339 WhereClause::Implemented(trait_ref) => Some(trait_ref),
347 /// If this is a `dyn Trait`, returns that trait.
348 pub fn dyn_trait(&self) -> Option<TraitId> {
349 self.dyn_trait_ref().map(|it| it.trait_id).map(from_chalk_trait_id)
352 fn builtin_deref(&self) -> Option<Ty> {
353 match self.kind(&Interner) {
354 TyKind::Ref(.., ty) => Some(ty.clone()),
355 TyKind::Raw(.., ty) => Some(ty.clone()),
360 pub fn callable_def(&self, db: &dyn HirDatabase) -> Option<CallableDefId> {
361 match self.kind(&Interner) {
362 &TyKind::FnDef(def, ..) => Some(db.lookup_intern_callable_def(def.into())),
367 pub fn as_fn_def(&self, db: &dyn HirDatabase) -> Option<FunctionId> {
368 if let Some(CallableDefId::FunctionId(func)) = self.callable_def(db) {
375 pub fn callable_sig(&self, db: &dyn HirDatabase) -> Option<CallableSig> {
376 match self.kind(&Interner) {
377 TyKind::Function(fn_ptr) => Some(CallableSig::from_fn_ptr(fn_ptr)),
378 TyKind::FnDef(def, parameters) => {
379 let callable_def = db.lookup_intern_callable_def((*def).into());
380 let sig = db.callable_item_signature(callable_def);
381 Some(sig.subst(¶meters))
383 TyKind::Closure(.., substs) => {
384 let sig_param = substs.at(&Interner, 0).assert_ty_ref(&Interner);
385 sig_param.callable_sig(db)
391 /// Returns the type parameters of this type if it has some (i.e. is an ADT
392 /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
393 pub fn substs(&self) -> Option<&Substitution> {
394 match self.kind(&Interner) {
395 TyKind::Adt(_, substs)
396 | TyKind::FnDef(_, substs)
397 | TyKind::Function(FnPointer { substs, .. })
398 | TyKind::Tuple(_, substs)
399 | TyKind::OpaqueType(_, substs)
400 | TyKind::AssociatedType(_, substs)
401 | TyKind::Closure(.., substs) => Some(substs),
406 fn substs_mut(&mut self) -> Option<&mut Substitution> {
407 match self.interned_mut() {
408 TyKind::Adt(_, substs)
409 | TyKind::FnDef(_, substs)
410 | TyKind::Function(FnPointer { substs, .. })
411 | TyKind::Tuple(_, substs)
412 | TyKind::OpaqueType(_, substs)
413 | TyKind::AssociatedType(_, substs)
414 | TyKind::Closure(.., substs) => Some(substs),
419 pub fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<QuantifiedWhereClause>> {
420 match self.kind(&Interner) {
421 TyKind::OpaqueType(opaque_ty_id, ..) => {
422 match db.lookup_intern_impl_trait_id((*opaque_ty_id).into()) {
423 ImplTraitId::AsyncBlockTypeImplTrait(def, _expr) => {
424 let krate = def.module(db.upcast()).krate();
425 if let Some(future_trait) = db
426 .lang_item(krate, "future_trait".into())
427 .and_then(|item| item.as_trait())
429 // This is only used by type walking.
430 // Parameters will be walked outside, and projection predicate is not used.
431 // So just provide the Future trait.
432 let impl_bound = Binders::new(
434 WhereClause::Implemented(TraitRef {
435 trait_id: to_chalk_trait_id(future_trait),
436 substitution: Substitution::empty(&Interner),
439 Some(vec![impl_bound])
444 ImplTraitId::ReturnTypeImplTrait(..) => None,
447 TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
448 let predicates = match db.lookup_intern_impl_trait_id(opaque_ty.opaque_ty_id.into())
450 ImplTraitId::ReturnTypeImplTrait(func, idx) => {
451 db.return_type_impl_traits(func).map(|it| {
454 .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
455 data.subst(&opaque_ty.substitution)
458 // It always has an parameter for Future::Output type.
459 ImplTraitId::AsyncBlockTypeImplTrait(..) => unreachable!(),
462 predicates.map(|it| it.value)
464 TyKind::Placeholder(idx) => {
465 let id = from_placeholder_idx(db, *idx);
466 let generic_params = db.generic_params(id.parent);
467 let param_data = &generic_params.types[id.local_id];
468 match param_data.provenance {
469 hir_def::generics::TypeParamProvenance::ArgumentImplTrait => {
470 let substs = TyBuilder::type_params_subst(db, id.parent);
472 .generic_predicates(id.parent)
474 .map(|pred| pred.clone().subst(&substs))
475 .filter(|wc| match &wc.skip_binders() {
476 WhereClause::Implemented(tr) => tr.self_type_parameter() == self,
477 WhereClause::AliasEq(AliasEq {
478 alias: AliasTy::Projection(proj),
480 }) => proj.self_type_parameter() == self,
494 pub fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId> {
495 match self.kind(&Interner) {
496 TyKind::AssociatedType(id, ..) => {
497 match from_assoc_type_id(*id).lookup(db.upcast()).container {
498 AssocContainerId::TraitId(trait_id) => Some(trait_id),
502 TyKind::Alias(AliasTy::Projection(projection_ty)) => {
503 match from_assoc_type_id(projection_ty.associated_ty_id)
507 AssocContainerId::TraitId(trait_id) => Some(trait_id),
516 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
517 pub enum ImplTraitId {
518 ReturnTypeImplTrait(hir_def::FunctionId, u16),
519 AsyncBlockTypeImplTrait(hir_def::DefWithBodyId, ExprId),
522 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
523 pub struct ReturnTypeImplTraits {
524 pub(crate) impl_traits: Vec<ReturnTypeImplTrait>,
527 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
528 pub(crate) struct ReturnTypeImplTrait {
529 pub(crate) bounds: Binders<Vec<QuantifiedWhereClause>>,
532 pub fn to_foreign_def_id(id: TypeAliasId) -> ForeignDefId {
533 chalk_ir::ForeignDefId(salsa::InternKey::as_intern_id(&id))
536 pub fn from_foreign_def_id(id: ForeignDefId) -> TypeAliasId {
537 salsa::InternKey::from_intern_id(id.0)
540 pub fn to_assoc_type_id(id: TypeAliasId) -> AssocTypeId {
541 chalk_ir::AssocTypeId(salsa::InternKey::as_intern_id(&id))
544 pub fn from_assoc_type_id(id: AssocTypeId) -> TypeAliasId {
545 salsa::InternKey::from_intern_id(id.0)
548 pub fn from_placeholder_idx(db: &dyn HirDatabase, idx: PlaceholderIndex) -> TypeParamId {
549 assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT);
550 let interned_id = salsa::InternKey::from_intern_id(salsa::InternId::from(idx.idx));
551 db.lookup_intern_type_param_id(interned_id)
554 pub fn to_placeholder_idx(db: &dyn HirDatabase, id: TypeParamId) -> PlaceholderIndex {
555 let interned_id = db.intern_type_param_id(id);
557 ui: chalk_ir::UniverseIndex::ROOT,
558 idx: salsa::InternKey::as_intern_id(&interned_id).as_usize(),
562 pub fn to_chalk_trait_id(id: TraitId) -> ChalkTraitId {
563 chalk_ir::TraitId(salsa::InternKey::as_intern_id(&id))
566 pub fn from_chalk_trait_id(id: ChalkTraitId) -> TraitId {
567 salsa::InternKey::from_intern_id(id.0)