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,
  39     LifetimeParamId, Lookup, 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::{ProjectionTyExt, 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::{chalk::Interner, 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 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;
  66
  67 pub type VariableKind = chalk_ir::VariableKind<Interner>;
  68 pub type VariableKinds = chalk_ir::VariableKinds<Interner>;
  69 pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>;
  70
  71 pub type Lifetime = chalk_ir::Lifetime<Interner>;
  72 pub type LifetimeData = chalk_ir::LifetimeData<Interner>;
  73 pub type LifetimeOutlives = chalk_ir::LifetimeOutlives<Interner>;
  74
  75 pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
  76
  77 pub type FnSig = chalk_ir::FnSig<Interner>;
  78
  79 impl Substitution {
  80     pub fn single(ty: Ty) -> Substitution {
  81         Substitution::intern({
  82             let mut v = SmallVec::new();
  83             v.push(ty.cast(&Interner));
  84             v
  85         })
  86     }
  87
  88     pub fn prefix(&self, n: usize) -> Substitution {
  89         Substitution::intern(self.interned()[..std::cmp::min(self.len(&Interner), n)].into())
  90     }
  91
  92     pub fn suffix(&self, n: usize) -> Substitution {
  93         Substitution::intern(
  94             self.interned()[self.len(&Interner) - std::cmp::min(self.len(&Interner), n)..].into(),
  95         )
  96     }
  97 }
  98
  99 /// Return an index of a parameter in the generic type parameter list by it's id.
 100 pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option<usize> {
 101     generics(db.upcast(), id.parent).param_idx(id)
 102 }
 103
 104 impl<T> Binders<T> {
 105     pub fn wrap_empty(value: T) -> Self
 106     where
 107         T: TypeWalk,
 108     {
 109         Binders::empty(&Interner, value.shifted_in_from(DebruijnIndex::ONE))
 110     }
 111 }
 112
 113 impl<T: TypeWalk> Binders<T> {
 114     /// Substitutes all variables.
 115     pub fn substitute(self, interner: &Interner, subst: &Substitution) -> T {
 116         let (value, binders) = self.into_value_and_skipped_binders();
 117         assert_eq!(subst.len(interner), binders.len(interner));
 118         value.subst_bound_vars(subst)
 119     }
 120 }
 121
 122 pub fn make_only_type_binders<T>(num_vars: usize, value: T) -> Binders<T> {
 123     Binders::new(
 124         VariableKinds::from_iter(
 125             &Interner,
 126             std::iter::repeat(chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General))
 127                 .take(num_vars),
 128         ),
 129         value,
 130     )
 131 }
 132
 133 impl TraitRef {
 134     pub fn self_type_parameter(&self, interner: &Interner) -> &Ty {
 135         &self.substitution.at(interner, 0).assert_ty_ref(interner)
 136     }
 137
 138     pub fn hir_trait_id(&self) -> TraitId {
 139         from_chalk_trait_id(self.trait_id)
 140     }
 141 }
 142
 143 impl WhereClause {
 144     pub fn is_implemented(&self) -> bool {
 145         matches!(self, WhereClause::Implemented(_))
 146     }
 147
 148     pub fn trait_ref(&self, db: &dyn HirDatabase) -> Option<TraitRef> {
 149         match self {
 150             WhereClause::Implemented(tr) => Some(tr.clone()),
 151             WhereClause::AliasEq(AliasEq { alias: AliasTy::Projection(proj), .. }) => {
 152                 Some(proj.trait_ref(db))
 153             }
 154             WhereClause::AliasEq(_) => None,
 155         }
 156     }
 157 }
 158
 159 impl<T> Canonical<T> {
 160     pub fn new(value: T, kinds: impl IntoIterator<Item = TyVariableKind>) -> Self {
 161         let kinds = kinds.into_iter().map(|tk| {
 162             chalk_ir::CanonicalVarKind::new(
 163                 chalk_ir::VariableKind::Ty(tk),
 164                 chalk_ir::UniverseIndex::ROOT,
 165             )
 166         });
 167         Self { value, binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds) }
 168     }
 169 }
 170
 171 /// A function signature as seen by type inference: Several parameter types and
 172 /// one return type.
 173 #[derive(Clone, PartialEq, Eq, Debug)]
 174 pub struct CallableSig {
 175     params_and_return: Arc<[Ty]>,
 176     is_varargs: bool,
 177 }
 178
 179 /// A polymorphic function signature.
 180 pub type PolyFnSig = Binders<CallableSig>;
 181
 182 impl CallableSig {
 183     pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty, is_varargs: bool) -> CallableSig {
 184         params.push(ret);
 185         CallableSig { params_and_return: params.into(), is_varargs }
 186     }
 187
 188     pub fn from_fn_ptr(fn_ptr: &FnPointer) -> CallableSig {
 189         CallableSig {
 190             // FIXME: what to do about lifetime params? -> return PolyFnSig
 191             params_and_return: fn_ptr
 192                 .substs
 193                 .clone()
 194                 .shifted_out_to(DebruijnIndex::ONE)
 195                 .expect("unexpected lifetime vars in fn ptr")
 196                 .interned()
 197                 .iter()
 198                 .map(|arg| arg.assert_ty_ref(&Interner).clone())
 199                 .collect(),
 200             is_varargs: fn_ptr.sig.variadic,
 201         }
 202     }
 203
 204     pub fn params(&self) -> &[Ty] {
 205         &self.params_and_return[0..self.params_and_return.len() - 1]
 206     }
 207
 208     pub fn ret(&self) -> &Ty {
 209         &self.params_and_return[self.params_and_return.len() - 1]
 210     }
 211 }
 212
 213 impl Ty {
 214     pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
 215         match self.kind(&Interner) {
 216             TyKind::Ref(mutability, ty) => Some((ty, *mutability)),
 217             _ => None,
 218         }
 219     }
 220
 221     pub fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)> {
 222         match self.kind(&Interner) {
 223             TyKind::Ref(mutability, ty) => Some((ty, Rawness::Ref, *mutability)),
 224             TyKind::Raw(mutability, ty) => Some((ty, Rawness::RawPtr, *mutability)),
 225             _ => None,
 226         }
 227     }
 228
 229     pub fn strip_references(&self) -> &Ty {
 230         let mut t: &Ty = self;
 231
 232         while let TyKind::Ref(_mutability, ty) = t.kind(&Interner) {
 233             t = ty;
 234         }
 235
 236         t
 237     }
 238
 239     pub fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)> {
 240         match self.kind(&Interner) {
 241             TyKind::Adt(AdtId(adt), parameters) => Some((*adt, parameters)),
 242             _ => None,
 243         }
 244     }
 245
 246     pub fn as_tuple(&self) -> Option<&Substitution> {
 247         match self.kind(&Interner) {
 248             TyKind::Tuple(_, substs) => Some(substs),
 249             _ => None,
 250         }
 251     }
 252
 253     pub fn as_generic_def(&self, db: &dyn HirDatabase) -> Option<GenericDefId> {
 254         match *self.kind(&Interner) {
 255             TyKind::Adt(AdtId(adt), ..) => Some(adt.into()),
 256             TyKind::FnDef(callable, ..) => {
 257                 Some(db.lookup_intern_callable_def(callable.into()).into())
 258             }
 259             TyKind::AssociatedType(type_alias, ..) => Some(from_assoc_type_id(type_alias).into()),
 260             TyKind::Foreign(type_alias, ..) => Some(from_foreign_def_id(type_alias).into()),
 261             _ => None,
 262         }
 263     }
 264
 265     pub fn is_never(&self) -> bool {
 266         matches!(self.kind(&Interner), TyKind::Never)
 267     }
 268
 269     pub fn is_unknown(&self) -> bool {
 270         matches!(self.kind(&Interner), TyKind::Error)
 271     }
 272
 273     pub fn equals_ctor(&self, other: &Ty) -> bool {
 274         match (self.kind(&Interner), other.kind(&Interner)) {
 275             (TyKind::Adt(adt, ..), TyKind::Adt(adt2, ..)) => adt == adt2,
 276             (TyKind::Slice(_), TyKind::Slice(_)) | (TyKind::Array(_), TyKind::Array(_)) => true,
 277             (TyKind::FnDef(def_id, ..), TyKind::FnDef(def_id2, ..)) => def_id == def_id2,
 278             (TyKind::OpaqueType(ty_id, ..), TyKind::OpaqueType(ty_id2, ..)) => ty_id == ty_id2,
 279             (TyKind::AssociatedType(ty_id, ..), TyKind::AssociatedType(ty_id2, ..)) => {
 280                 ty_id == ty_id2
 281             }
 282             (TyKind::Foreign(ty_id, ..), TyKind::Foreign(ty_id2, ..)) => ty_id == ty_id2,
 283             (TyKind::Closure(id1, _), TyKind::Closure(id2, _)) => id1 == id2,
 284             (TyKind::Ref(mutability, ..), TyKind::Ref(mutability2, ..))
 285             | (TyKind::Raw(mutability, ..), TyKind::Raw(mutability2, ..)) => {
 286                 mutability == mutability2
 287             }
 288             (
 289                 TyKind::Function(FnPointer { num_args, sig, .. }),
 290                 TyKind::Function(FnPointer { num_args: num_args2, sig: sig2, .. }),
 291             ) => num_args == num_args2 && sig == sig2,
 292             (TyKind::Tuple(cardinality, _), TyKind::Tuple(cardinality2, _)) => {
 293                 cardinality == cardinality2
 294             }
 295             (TyKind::Str, TyKind::Str) | (TyKind::Never, TyKind::Never) => true,
 296             (TyKind::Scalar(scalar), TyKind::Scalar(scalar2)) => scalar == scalar2,
 297             _ => false,
 298         }
 299     }
 300
 301     /// If this is a `dyn Trait` type, this returns the `Trait` part.
 302     fn dyn_trait_ref(&self) -> Option<&TraitRef> {
 303         match self.kind(&Interner) {
 304             TyKind::Dyn(dyn_ty) => dyn_ty.bounds.skip_binders().interned().get(0).and_then(|b| {
 305                 match b.skip_binders() {
 306                     WhereClause::Implemented(trait_ref) => Some(trait_ref),
 307                     _ => None,
 308                 }
 309             }),
 310             _ => None,
 311         }
 312     }
 313
 314     /// If this is a `dyn Trait`, returns that trait.
 315     pub fn dyn_trait(&self) -> Option<TraitId> {
 316         self.dyn_trait_ref().map(|it| it.trait_id).map(from_chalk_trait_id)
 317     }
 318
 319     fn builtin_deref(&self) -> Option<Ty> {
 320         match self.kind(&Interner) {
 321             TyKind::Ref(.., ty) => Some(ty.clone()),
 322             TyKind::Raw(.., ty) => Some(ty.clone()),
 323             _ => None,
 324         }
 325     }
 326
 327     pub fn callable_def(&self, db: &dyn HirDatabase) -> Option<CallableDefId> {
 328         match self.kind(&Interner) {
 329             &TyKind::FnDef(def, ..) => Some(db.lookup_intern_callable_def(def.into())),
 330             _ => None,
 331         }
 332     }
 333
 334     pub fn as_fn_def(&self, db: &dyn HirDatabase) -> Option<FunctionId> {
 335         if let Some(CallableDefId::FunctionId(func)) = self.callable_def(db) {
 336             Some(func)
 337         } else {
 338             None
 339         }
 340     }
 341
 342     pub fn callable_sig(&self, db: &dyn HirDatabase) -> Option<CallableSig> {
 343         match self.kind(&Interner) {
 344             TyKind::Function(fn_ptr) => Some(CallableSig::from_fn_ptr(fn_ptr)),
 345             TyKind::FnDef(def, parameters) => {
 346                 let callable_def = db.lookup_intern_callable_def((*def).into());
 347                 let sig = db.callable_item_signature(callable_def);
 348                 Some(sig.substitute(&Interner, &parameters))
 349             }
 350             TyKind::Closure(.., substs) => {
 351                 let sig_param = substs.at(&Interner, 0).assert_ty_ref(&Interner);
 352                 sig_param.callable_sig(db)
 353             }
 354             _ => None,
 355         }
 356     }
 357
 358     /// Returns the type parameters of this type if it has some (i.e. is an ADT
 359     /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
 360     pub fn substs(&self) -> Option<&Substitution> {
 361         match self.kind(&Interner) {
 362             TyKind::Adt(_, substs)
 363             | TyKind::FnDef(_, substs)
 364             | TyKind::Function(FnPointer { substs, .. })
 365             | TyKind::Tuple(_, substs)
 366             | TyKind::OpaqueType(_, substs)
 367             | TyKind::AssociatedType(_, substs)
 368             | TyKind::Closure(.., substs) => Some(substs),
 369             _ => None,
 370         }
 371     }
 372
 373     fn substs_mut(&mut self) -> Option<&mut Substitution> {
 374         match self.interned_mut() {
 375             TyKind::Adt(_, substs)
 376             | TyKind::FnDef(_, substs)
 377             | TyKind::Function(FnPointer { substs, .. })
 378             | TyKind::Tuple(_, substs)
 379             | TyKind::OpaqueType(_, substs)
 380             | TyKind::AssociatedType(_, substs)
 381             | TyKind::Closure(.., substs) => Some(substs),
 382             _ => None,
 383         }
 384     }
 385
 386     pub fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<QuantifiedWhereClause>> {
 387         match self.kind(&Interner) {
 388             TyKind::OpaqueType(opaque_ty_id, ..) => {
 389                 match db.lookup_intern_impl_trait_id((*opaque_ty_id).into()) {
 390                     ImplTraitId::AsyncBlockTypeImplTrait(def, _expr) => {
 391                         let krate = def.module(db.upcast()).krate();
 392                         if let Some(future_trait) = db
 393                             .lang_item(krate, "future_trait".into())
 394                             .and_then(|item| item.as_trait())
 395                         {
 396                             // This is only used by type walking.
 397                             // Parameters will be walked outside, and projection predicate is not used.
 398                             // So just provide the Future trait.
 399                             let impl_bound = Binders::empty(
 400                                 &Interner,
 401                                 WhereClause::Implemented(TraitRef {
 402                                     trait_id: to_chalk_trait_id(future_trait),
 403                                     substitution: Substitution::empty(&Interner),
 404                                 }),
 405                             );
 406                             Some(vec![impl_bound])
 407                         } else {
 408                             None
 409                         }
 410                     }
 411                     ImplTraitId::ReturnTypeImplTrait(..) => None,
 412                 }
 413             }
 414             TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
 415                 let predicates = match db.lookup_intern_impl_trait_id(opaque_ty.opaque_ty_id.into())
 416                 {
 417                     ImplTraitId::ReturnTypeImplTrait(func, idx) => {
 418                         db.return_type_impl_traits(func).map(|it| {
 419                             let data = (*it)
 420                                 .as_ref()
 421                                 .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
 422                             data.substitute(&Interner, &opaque_ty.substitution)
 423                         })
 424                     }
 425                     // It always has an parameter for Future::Output type.
 426                     ImplTraitId::AsyncBlockTypeImplTrait(..) => unreachable!(),
 427                 };
 428
 429                 predicates.map(|it| it.into_value_and_skipped_binders().0)
 430             }
 431             TyKind::Placeholder(idx) => {
 432                 let id = from_placeholder_idx(db, *idx);
 433                 let generic_params = db.generic_params(id.parent);
 434                 let param_data = &generic_params.types[id.local_id];
 435                 match param_data.provenance {
 436                     hir_def::generics::TypeParamProvenance::ArgumentImplTrait => {
 437                         let substs = TyBuilder::type_params_subst(db, id.parent);
 438                         let predicates = db
 439                             .generic_predicates(id.parent)
 440                             .into_iter()
 441                             .map(|pred| pred.clone().substitute(&Interner, &substs))
 442                             .filter(|wc| match &wc.skip_binders() {
 443                                 WhereClause::Implemented(tr) => {
 444                                     tr.self_type_parameter(&Interner) == self
 445                                 }
 446                                 WhereClause::AliasEq(AliasEq {
 447                                     alias: AliasTy::Projection(proj),
 448                                     ty: _,
 449                                 }) => proj.self_type_parameter(&Interner) == self,
 450                                 _ => false,
 451                             })
 452                             .collect_vec();
 453
 454                         Some(predicates)
 455                     }
 456                     _ => None,
 457                 }
 458             }
 459             _ => None,
 460         }
 461     }
 462
 463     pub fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId> {
 464         match self.kind(&Interner) {
 465             TyKind::AssociatedType(id, ..) => {
 466                 match from_assoc_type_id(*id).lookup(db.upcast()).container {
 467                     AssocContainerId::TraitId(trait_id) => Some(trait_id),
 468                     _ => None,
 469                 }
 470             }
 471             TyKind::Alias(AliasTy::Projection(projection_ty)) => {
 472                 match from_assoc_type_id(projection_ty.associated_ty_id)
 473                     .lookup(db.upcast())
 474                     .container
 475                 {
 476                     AssocContainerId::TraitId(trait_id) => Some(trait_id),
 477                     _ => None,
 478                 }
 479             }
 480             _ => None,
 481         }
 482     }
 483 }
 484
 485 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
 486 pub enum ImplTraitId {
 487     ReturnTypeImplTrait(hir_def::FunctionId, u16),
 488     AsyncBlockTypeImplTrait(hir_def::DefWithBodyId, ExprId),
 489 }
 490
 491 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 492 pub struct ReturnTypeImplTraits {
 493     pub(crate) impl_traits: Vec<ReturnTypeImplTrait>,
 494 }
 495
 496 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 497 pub(crate) struct ReturnTypeImplTrait {
 498     pub(crate) bounds: Binders<Vec<QuantifiedWhereClause>>,
 499 }
 500
 501 pub fn to_foreign_def_id(id: TypeAliasId) -> ForeignDefId {
 502     chalk_ir::ForeignDefId(salsa::InternKey::as_intern_id(&id))
 503 }
 504
 505 pub fn from_foreign_def_id(id: ForeignDefId) -> TypeAliasId {
 506     salsa::InternKey::from_intern_id(id.0)
 507 }
 508
 509 pub fn to_assoc_type_id(id: TypeAliasId) -> AssocTypeId {
 510     chalk_ir::AssocTypeId(salsa::InternKey::as_intern_id(&id))
 511 }
 512
 513 pub fn from_assoc_type_id(id: AssocTypeId) -> TypeAliasId {
 514     salsa::InternKey::from_intern_id(id.0)
 515 }
 516
 517 pub fn from_placeholder_idx(db: &dyn HirDatabase, idx: PlaceholderIndex) -> TypeParamId {
 518     assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT);
 519     let interned_id = salsa::InternKey::from_intern_id(salsa::InternId::from(idx.idx));
 520     db.lookup_intern_type_param_id(interned_id)
 521 }
 522
 523 pub fn to_placeholder_idx(db: &dyn HirDatabase, id: TypeParamId) -> PlaceholderIndex {
 524     let interned_id = db.intern_type_param_id(id);
 525     PlaceholderIndex {
 526         ui: chalk_ir::UniverseIndex::ROOT,
 527         idx: salsa::InternKey::as_intern_id(&interned_id).as_usize(),
 528     }
 529 }
 530
 531 pub fn lt_from_placeholder_idx(db: &dyn HirDatabase, idx: PlaceholderIndex) -> LifetimeParamId {
 532     assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT);
 533     let interned_id = salsa::InternKey::from_intern_id(salsa::InternId::from(idx.idx));
 534     db.lookup_intern_lifetime_param_id(interned_id)
 535 }
 536
 537 pub fn to_chalk_trait_id(id: TraitId) -> ChalkTraitId {
 538     chalk_ir::TraitId(salsa::InternKey::as_intern_id(&id))
 539 }
 540
 541 pub fn from_chalk_trait_id(id: ChalkTraitId) -> TraitId {
 542     salsa::InternKey::from_intern_id(id.0)
 543 }