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