crates/hir_ty/src/lib.rs

   1 //! The type system. We currently use this to infer types for completion, hover
   2 //! information and various assists.
   3 #[allow(unused)]
   4 macro_rules! eprintln {
   5     ($($tt:tt)*) => { stdx::eprintln!($($tt)*) };
   6 }
   7
   8 mod autoderef;
   9 pub mod primitive;
  10 pub mod traits;
  11 pub mod method_resolution;
  12 mod op;
  13 mod lower;
  14 pub(crate) mod infer;
  15 pub(crate) mod utils;
  16 mod chalk_cast;
  17 mod chalk_ext;
  18 mod builder;
  19 mod walk;
  20 mod types;
  21
  22 pub mod display;
  23 pub mod db;
  24 pub mod diagnostics;
  25
  26 #[cfg(test)]
  27 mod tests;
  28 #[cfg(test)]
  29 mod test_db;
  30
  31 use std::sync::Arc;
  32
  33 use itertools::Itertools;
  34 use smallvec::SmallVec;
  35
  36 use base_db::salsa;
  37 use hir_def::{
  38     expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule, Lookup,
  39     TraitId, TypeAliasId, TypeParamId,
  40 };
  41
  42 use crate::{db::HirDatabase, display::HirDisplay, utils::generics};
  43
  44 pub use autoderef::autoderef;
  45 pub use builder::TyBuilder;
  46 pub use chalk_ext::TyExt;
  47 pub use infer::{could_unify, InferenceResult, InferenceVar};
  48 pub use lower::{
  49     associated_type_shorthand_candidates, callable_item_sig, CallableDefId, ImplTraitLoweringMode,
  50     TyDefId, TyLoweringContext, ValueTyDefId,
  51 };
  52 pub use traits::TraitEnvironment;
  53 pub use types::*;
  54 pub use walk::TypeWalk;
  55
  56 pub use chalk_ir::{
  57     cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind,
  58 };
  59
  60 pub use crate::traits::chalk::Interner;
  61
  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;
  68
  69 pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>;
  70
  71 pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
  72
  73 impl ProjectionTy {
  74     pub fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef {
  75         TraitRef {
  76             trait_id: to_chalk_trait_id(self.trait_(db)),
  77             substitution: self.substitution.clone(),
  78         }
  79     }
  80
  81     pub fn self_type_parameter(&self) -> &Ty {
  82         &self.substitution.interned()[0].assert_ty_ref(&Interner)
  83     }
  84
  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"),
  89         }
  90     }
  91 }
  92
  93 pub type FnSig = chalk_ir::FnSig<Interner>;
  94
  95 impl Substitution {
  96     pub fn single(ty: Ty) -> Substitution {
  97         Substitution::intern({
  98             let mut v = SmallVec::new();
  99             v.push(ty.cast(&Interner));
 100             v
 101         })
 102     }
 103
 104     pub fn prefix(&self, n: usize) -> Substitution {
 105         Substitution::intern(self.interned()[..std::cmp::min(self.len(&Interner), n)].into())
 106     }
 107
 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(),
 111         )
 112     }
 113 }
 114
 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)
 118 }
 119
 120 impl<T> Binders<T> {
 121     pub fn new(num_binders: usize, value: T) -> Self {
 122         Self { num_binders, value }
 123     }
 124
 125     pub fn wrap_empty(value: T) -> Self
 126     where
 127         T: TypeWalk,
 128     {
 129         Self { num_binders: 0, value: value.shift_bound_vars(DebruijnIndex::ONE) }
 130     }
 131
 132     pub fn as_ref(&self) -> Binders<&T> {
 133         Binders { num_binders: self.num_binders, value: &self.value }
 134     }
 135
 136     pub fn map<U>(self, f: impl FnOnce(T) -> U) -> Binders<U> {
 137         Binders { num_binders: self.num_binders, value: f(self.value) }
 138     }
 139
 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)? })
 142     }
 143
 144     pub fn skip_binders(&self) -> &T {
 145         &self.value
 146     }
 147
 148     pub fn into_value_and_skipped_binders(self) -> (T, usize) {
 149         (self.value, self.num_binders)
 150     }
 151 }
 152
 153 impl<T: Clone> Binders<&T> {
 154     pub fn cloned(&self) -> Binders<T> {
 155         Binders { num_binders: self.num_binders, value: self.value.clone() }
 156     }
 157 }
 158
 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)
 164     }
 165 }
 166
 167 impl TraitRef {
 168     pub fn self_type_parameter(&self) -> &Ty {
 169         &self.substitution.at(&Interner, 0).assert_ty_ref(&Interner)
 170     }
 171
 172     pub fn hir_trait_id(&self) -> TraitId {
 173         from_chalk_trait_id(self.trait_id)
 174     }
 175 }
 176
 177 impl WhereClause {
 178     pub fn is_implemented(&self) -> bool {
 179         matches!(self, WhereClause::Implemented(_))
 180     }
 181
 182     pub fn trait_ref(&self, db: &dyn HirDatabase) -> Option<TraitRef> {
 183         match self {
 184             WhereClause::Implemented(tr) => Some(tr.clone()),
 185             WhereClause::AliasEq(AliasEq { alias: AliasTy::Projection(proj), .. }) => {
 186                 Some(proj.trait_ref(db))
 187             }
 188             WhereClause::AliasEq(_) => None,
 189         }
 190     }
 191 }
 192
 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,
 199             )
 200         });
 201         Self { value, binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds) }
 202     }
 203 }
 204
 205 /// A function signature as seen by type inference: Several parameter types and
 206 /// one return type.
 207 #[derive(Clone, PartialEq, Eq, Debug)]
 208 pub struct CallableSig {
 209     params_and_return: Arc<[Ty]>,
 210     is_varargs: bool,
 211 }
 212
 213 /// A polymorphic function signature.
 214 pub type PolyFnSig = Binders<CallableSig>;
 215
 216 impl CallableSig {
 217     pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty, is_varargs: bool) -> CallableSig {
 218         params.push(ret);
 219         CallableSig { params_and_return: params.into(), is_varargs }
 220     }
 221
 222     pub fn from_fn_ptr(fn_ptr: &FnPointer) -> CallableSig {
 223         CallableSig {
 224             // FIXME: what to do about lifetime params? -> return PolyFnSig
 225             params_and_return: fn_ptr
 226                 .substs
 227                 .clone()
 228                 .shift_bound_vars_out(DebruijnIndex::ONE)
 229                 .interned()
 230                 .iter()
 231                 .map(|arg| arg.assert_ty_ref(&Interner).clone())
 232                 .collect(),
 233             is_varargs: fn_ptr.sig.variadic,
 234         }
 235     }
 236
 237     pub fn params(&self) -> &[Ty] {
 238         &self.params_and_return[0..self.params_and_return.len() - 1]
 239     }
 240
 241     pub fn ret(&self) -> &Ty {
 242         &self.params_and_return[self.params_and_return.len() - 1]
 243     }
 244 }
 245
 246 impl Ty {
 247     pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
 248         match self.kind(&Interner) {
 249             TyKind::Ref(mutability, ty) => Some((ty, *mutability)),
 250             _ => None,
 251         }
 252     }
 253
 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)),
 258             _ => None,
 259         }
 260     }
 261
 262     pub fn strip_references(&self) -> &Ty {
 263         let mut t: &Ty = self;
 264
 265         while let TyKind::Ref(_mutability, ty) = t.kind(&Interner) {
 266             t = ty;
 267         }
 268
 269         t
 270     }
 271
 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)),
 275             _ => None,
 276         }
 277     }
 278
 279     pub fn as_tuple(&self) -> Option<&Substitution> {
 280         match self.kind(&Interner) {
 281             TyKind::Tuple(_, substs) => Some(substs),
 282             _ => None,
 283         }
 284     }
 285
 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())
 291             }
 292             TyKind::AssociatedType(type_alias, ..) => Some(from_assoc_type_id(type_alias).into()),
 293             TyKind::Foreign(type_alias, ..) => Some(from_foreign_def_id(type_alias).into()),
 294             _ => None,
 295         }
 296     }
 297
 298     pub fn is_never(&self) -> bool {
 299         matches!(self.kind(&Interner), TyKind::Never)
 300     }
 301
 302     pub fn is_unknown(&self) -> bool {
 303         matches!(self.kind(&Interner), TyKind::Error)
 304     }
 305
 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, ..)) => {
 313                 ty_id == ty_id2
 314             }
 315             (TyKind::Foreign(ty_id, ..), TyKind::Foreign(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
 320             }
 321             (
 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
 327             }
 328             (TyKind::Str, TyKind::Str) | (TyKind::Never, TyKind::Never) => true,
 329             (TyKind::Scalar(scalar), TyKind::Scalar(scalar2)) => scalar == scalar2,
 330             _ => false,
 331         }
 332     }
 333
 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),
 340                     _ => None,
 341                 })
 342             }
 343             _ => None,
 344         }
 345     }
 346
 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)
 350     }
 351
 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()),
 356             _ => None,
 357         }
 358     }
 359
 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())),
 363             _ => None,
 364         }
 365     }
 366
 367     pub fn as_fn_def(&self, db: &dyn HirDatabase) -> Option<FunctionId> {
 368         if let Some(CallableDefId::FunctionId(func)) = self.callable_def(db) {
 369             Some(func)
 370         } else {
 371             None
 372         }
 373     }
 374
 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(&parameters))
 382             }
 383             TyKind::Closure(.., substs) => {
 384                 let sig_param = substs.at(&Interner, 0).assert_ty_ref(&Interner);
 385                 sig_param.callable_sig(db)
 386             }
 387             _ => None,
 388         }
 389     }
 390
 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),
 402             _ => None,
 403         }
 404     }
 405
 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),
 415             _ => None,
 416         }
 417     }
 418
 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())
 428                         {
 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(
 433                                 0,
 434                                 WhereClause::Implemented(TraitRef {
 435                                     trait_id: to_chalk_trait_id(future_trait),
 436                                     substitution: Substitution::empty(&Interner),
 437                                 }),
 438                             );
 439                             Some(vec![impl_bound])
 440                         } else {
 441                             None
 442                         }
 443                     }
 444                     ImplTraitId::ReturnTypeImplTrait(..) => None,
 445                 }
 446             }
 447             TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
 448                 let predicates = match db.lookup_intern_impl_trait_id(opaque_ty.opaque_ty_id.into())
 449                 {
 450                     ImplTraitId::ReturnTypeImplTrait(func, idx) => {
 451                         db.return_type_impl_traits(func).map(|it| {
 452                             let data = (*it)
 453                                 .as_ref()
 454                                 .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
 455                             data.subst(&opaque_ty.substitution)
 456                         })
 457                     }
 458                     // It always has an parameter for Future::Output type.
 459                     ImplTraitId::AsyncBlockTypeImplTrait(..) => unreachable!(),
 460                 };
 461
 462                 predicates.map(|it| it.value)
 463             }
 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);
 471                         let predicates = db
 472                             .generic_predicates(id.parent)
 473                             .into_iter()
 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),
 479                                     ty: _,
 480                                 }) => proj.self_type_parameter() == self,
 481                                 _ => false,
 482                             })
 483                             .collect_vec();
 484
 485                         Some(predicates)
 486                     }
 487                     _ => None,
 488                 }
 489             }
 490             _ => None,
 491         }
 492     }
 493
 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),
 499                     _ => None,
 500                 }
 501             }
 502             TyKind::Alias(AliasTy::Projection(projection_ty)) => {
 503                 match from_assoc_type_id(projection_ty.associated_ty_id)
 504                     .lookup(db.upcast())
 505                     .container
 506                 {
 507                     AssocContainerId::TraitId(trait_id) => Some(trait_id),
 508                     _ => None,
 509                 }
 510             }
 511             _ => None,
 512         }
 513     }
 514 }
 515
 516 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
 517 pub enum ImplTraitId {
 518     ReturnTypeImplTrait(hir_def::FunctionId, u16),
 519     AsyncBlockTypeImplTrait(hir_def::DefWithBodyId, ExprId),
 520 }
 521
 522 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 523 pub struct ReturnTypeImplTraits {
 524     pub(crate) impl_traits: Vec<ReturnTypeImplTrait>,
 525 }
 526
 527 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 528 pub(crate) struct ReturnTypeImplTrait {
 529     pub(crate) bounds: Binders<Vec<QuantifiedWhereClause>>,
 530 }
 531
 532 pub fn to_foreign_def_id(id: TypeAliasId) -> ForeignDefId {
 533     chalk_ir::ForeignDefId(salsa::InternKey::as_intern_id(&id))
 534 }
 535
 536 pub fn from_foreign_def_id(id: ForeignDefId) -> TypeAliasId {
 537     salsa::InternKey::from_intern_id(id.0)
 538 }
 539
 540 pub fn to_assoc_type_id(id: TypeAliasId) -> AssocTypeId {
 541     chalk_ir::AssocTypeId(salsa::InternKey::as_intern_id(&id))
 542 }
 543
 544 pub fn from_assoc_type_id(id: AssocTypeId) -> TypeAliasId {
 545     salsa::InternKey::from_intern_id(id.0)
 546 }
 547
 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)
 552 }
 553
 554 pub fn to_placeholder_idx(db: &dyn HirDatabase, id: TypeParamId) -> PlaceholderIndex {
 555     let interned_id = db.intern_type_param_id(id);
 556     PlaceholderIndex {
 557         ui: chalk_ir::UniverseIndex::ROOT,
 558         idx: salsa::InternKey::as_intern_id(&interned_id).as_usize(),
 559     }
 560 }
 561
 562 pub fn to_chalk_trait_id(id: TraitId) -> ChalkTraitId {
 563     chalk_ir::TraitId(salsa::InternKey::as_intern_id(&id))
 564 }
 565
 566 pub fn from_chalk_trait_id(id: ChalkTraitId) -> TraitId {
 567     salsa::InternKey::from_intern_id(id.0)
 568 }