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.shifted_in_from(DebruijnIndex::ONE))
 128     }
 129 }
 130
 131 impl<T: TypeWalk> Binders<T> {
 132     /// Substitutes all variables.
 133     pub fn substitute(self, interner: &Interner, 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                 .shifted_out_to(DebruijnIndex::ONE)
 213                 .expect("unexpected lifetime vars in fn ptr")
 214                 .interned()
 215                 .iter()
 216                 .map(|arg| arg.assert_ty_ref(&Interner).clone())
 217                 .collect(),
 218             is_varargs: fn_ptr.sig.variadic,
 219         }
 220     }
 221
 222     pub fn params(&self) -> &[Ty] {
 223         &self.params_and_return[0..self.params_and_return.len() - 1]
 224     }
 225
 226     pub fn ret(&self) -> &Ty {
 227         &self.params_and_return[self.params_and_return.len() - 1]
 228     }
 229 }
 230
 231 impl Ty {
 232     pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
 233         match self.kind(&Interner) {
 234             TyKind::Ref(mutability, ty) => Some((ty, *mutability)),
 235             _ => None,
 236         }
 237     }
 238
 239     pub fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)> {
 240         match self.kind(&Interner) {
 241             TyKind::Ref(mutability, ty) => Some((ty, Rawness::Ref, *mutability)),
 242             TyKind::Raw(mutability, ty) => Some((ty, Rawness::RawPtr, *mutability)),
 243             _ => None,
 244         }
 245     }
 246
 247     pub fn strip_references(&self) -> &Ty {
 248         let mut t: &Ty = self;
 249
 250         while let TyKind::Ref(_mutability, ty) = t.kind(&Interner) {
 251             t = ty;
 252         }
 253
 254         t
 255     }
 256
 257     pub fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)> {
 258         match self.kind(&Interner) {
 259             TyKind::Adt(AdtId(adt), parameters) => Some((*adt, parameters)),
 260             _ => None,
 261         }
 262     }
 263
 264     pub fn as_tuple(&self) -> Option<&Substitution> {
 265         match self.kind(&Interner) {
 266             TyKind::Tuple(_, substs) => Some(substs),
 267             _ => None,
 268         }
 269     }
 270
 271     pub fn as_generic_def(&self, db: &dyn HirDatabase) -> Option<GenericDefId> {
 272         match *self.kind(&Interner) {
 273             TyKind::Adt(AdtId(adt), ..) => Some(adt.into()),
 274             TyKind::FnDef(callable, ..) => {
 275                 Some(db.lookup_intern_callable_def(callable.into()).into())
 276             }
 277             TyKind::AssociatedType(type_alias, ..) => Some(from_assoc_type_id(type_alias).into()),
 278             TyKind::Foreign(type_alias, ..) => Some(from_foreign_def_id(type_alias).into()),
 279             _ => None,
 280         }
 281     }
 282
 283     pub fn is_never(&self) -> bool {
 284         matches!(self.kind(&Interner), TyKind::Never)
 285     }
 286
 287     pub fn is_unknown(&self) -> bool {
 288         matches!(self.kind(&Interner), TyKind::Error)
 289     }
 290
 291     pub fn equals_ctor(&self, other: &Ty) -> bool {
 292         match (self.kind(&Interner), other.kind(&Interner)) {
 293             (TyKind::Adt(adt, ..), TyKind::Adt(adt2, ..)) => adt == adt2,
 294             (TyKind::Slice(_), TyKind::Slice(_)) | (TyKind::Array(_), TyKind::Array(_)) => true,
 295             (TyKind::FnDef(def_id, ..), TyKind::FnDef(def_id2, ..)) => def_id == def_id2,
 296             (TyKind::OpaqueType(ty_id, ..), TyKind::OpaqueType(ty_id2, ..)) => ty_id == ty_id2,
 297             (TyKind::AssociatedType(ty_id, ..), TyKind::AssociatedType(ty_id2, ..)) => {
 298                 ty_id == ty_id2
 299             }
 300             (TyKind::Foreign(ty_id, ..), TyKind::Foreign(ty_id2, ..)) => ty_id == ty_id2,
 301             (TyKind::Closure(id1, _), TyKind::Closure(id2, _)) => id1 == id2,
 302             (TyKind::Ref(mutability, ..), TyKind::Ref(mutability2, ..))
 303             | (TyKind::Raw(mutability, ..), TyKind::Raw(mutability2, ..)) => {
 304                 mutability == mutability2
 305             }
 306             (
 307                 TyKind::Function(FnPointer { num_args, sig, .. }),
 308                 TyKind::Function(FnPointer { num_args: num_args2, sig: sig2, .. }),
 309             ) => num_args == num_args2 && sig == sig2,
 310             (TyKind::Tuple(cardinality, _), TyKind::Tuple(cardinality2, _)) => {
 311                 cardinality == cardinality2
 312             }
 313             (TyKind::Str, TyKind::Str) | (TyKind::Never, TyKind::Never) => true,
 314             (TyKind::Scalar(scalar), TyKind::Scalar(scalar2)) => scalar == scalar2,
 315             _ => false,
 316         }
 317     }
 318
 319     /// If this is a `dyn Trait` type, this returns the `Trait` part.
 320     fn dyn_trait_ref(&self) -> Option<&TraitRef> {
 321         match self.kind(&Interner) {
 322             TyKind::Dyn(dyn_ty) => dyn_ty.bounds.skip_binders().interned().get(0).and_then(|b| {
 323                 match b.skip_binders() {
 324                     WhereClause::Implemented(trait_ref) => Some(trait_ref),
 325                     _ => None,
 326                 }
 327             }),
 328             _ => None,
 329         }
 330     }
 331
 332     /// If this is a `dyn Trait`, returns that trait.
 333     pub fn dyn_trait(&self) -> Option<TraitId> {
 334         self.dyn_trait_ref().map(|it| it.trait_id).map(from_chalk_trait_id)
 335     }
 336
 337     fn builtin_deref(&self) -> Option<Ty> {
 338         match self.kind(&Interner) {
 339             TyKind::Ref(.., ty) => Some(ty.clone()),
 340             TyKind::Raw(.., ty) => Some(ty.clone()),
 341             _ => None,
 342         }
 343     }
 344
 345     pub fn callable_def(&self, db: &dyn HirDatabase) -> Option<CallableDefId> {
 346         match self.kind(&Interner) {
 347             &TyKind::FnDef(def, ..) => Some(db.lookup_intern_callable_def(def.into())),
 348             _ => None,
 349         }
 350     }
 351
 352     pub fn as_fn_def(&self, db: &dyn HirDatabase) -> Option<FunctionId> {
 353         if let Some(CallableDefId::FunctionId(func)) = self.callable_def(db) {
 354             Some(func)
 355         } else {
 356             None
 357         }
 358     }
 359
 360     pub fn callable_sig(&self, db: &dyn HirDatabase) -> Option<CallableSig> {
 361         match self.kind(&Interner) {
 362             TyKind::Function(fn_ptr) => Some(CallableSig::from_fn_ptr(fn_ptr)),
 363             TyKind::FnDef(def, parameters) => {
 364                 let callable_def = db.lookup_intern_callable_def((*def).into());
 365                 let sig = db.callable_item_signature(callable_def);
 366                 Some(sig.substitute(&Interner, &parameters))
 367             }
 368             TyKind::Closure(.., substs) => {
 369                 let sig_param = substs.at(&Interner, 0).assert_ty_ref(&Interner);
 370                 sig_param.callable_sig(db)
 371             }
 372             _ => None,
 373         }
 374     }
 375
 376     /// Returns the type parameters of this type if it has some (i.e. is an ADT
 377     /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
 378     pub fn substs(&self) -> Option<&Substitution> {
 379         match self.kind(&Interner) {
 380             TyKind::Adt(_, substs)
 381             | TyKind::FnDef(_, substs)
 382             | TyKind::Function(FnPointer { substs, .. })
 383             | TyKind::Tuple(_, substs)
 384             | TyKind::OpaqueType(_, substs)
 385             | TyKind::AssociatedType(_, substs)
 386             | TyKind::Closure(.., substs) => Some(substs),
 387             _ => None,
 388         }
 389     }
 390
 391     fn substs_mut(&mut self) -> Option<&mut Substitution> {
 392         match self.interned_mut() {
 393             TyKind::Adt(_, substs)
 394             | TyKind::FnDef(_, substs)
 395             | TyKind::Function(FnPointer { substs, .. })
 396             | TyKind::Tuple(_, substs)
 397             | TyKind::OpaqueType(_, substs)
 398             | TyKind::AssociatedType(_, substs)
 399             | TyKind::Closure(.., substs) => Some(substs),
 400             _ => None,
 401         }
 402     }
 403
 404     pub fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<QuantifiedWhereClause>> {
 405         match self.kind(&Interner) {
 406             TyKind::OpaqueType(opaque_ty_id, ..) => {
 407                 match db.lookup_intern_impl_trait_id((*opaque_ty_id).into()) {
 408                     ImplTraitId::AsyncBlockTypeImplTrait(def, _expr) => {
 409                         let krate = def.module(db.upcast()).krate();
 410                         if let Some(future_trait) = db
 411                             .lang_item(krate, "future_trait".into())
 412                             .and_then(|item| item.as_trait())
 413                         {
 414                             // This is only used by type walking.
 415                             // Parameters will be walked outside, and projection predicate is not used.
 416                             // So just provide the Future trait.
 417                             let impl_bound = Binders::empty(
 418                                 &Interner,
 419                                 WhereClause::Implemented(TraitRef {
 420                                     trait_id: to_chalk_trait_id(future_trait),
 421                                     substitution: Substitution::empty(&Interner),
 422                                 }),
 423                             );
 424                             Some(vec![impl_bound])
 425                         } else {
 426                             None
 427                         }
 428                     }
 429                     ImplTraitId::ReturnTypeImplTrait(..) => None,
 430                 }
 431             }
 432             TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
 433                 let predicates = match db.lookup_intern_impl_trait_id(opaque_ty.opaque_ty_id.into())
 434                 {
 435                     ImplTraitId::ReturnTypeImplTrait(func, idx) => {
 436                         db.return_type_impl_traits(func).map(|it| {
 437                             let data = (*it)
 438                                 .as_ref()
 439                                 .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
 440                             data.substitute(&Interner, &opaque_ty.substitution)
 441                         })
 442                     }
 443                     // It always has an parameter for Future::Output type.
 444                     ImplTraitId::AsyncBlockTypeImplTrait(..) => unreachable!(),
 445                 };
 446
 447                 predicates.map(|it| it.into_value_and_skipped_binders().0)
 448             }
 449             TyKind::Placeholder(idx) => {
 450                 let id = from_placeholder_idx(db, *idx);
 451                 let generic_params = db.generic_params(id.parent);
 452                 let param_data = &generic_params.types[id.local_id];
 453                 match param_data.provenance {
 454                     hir_def::generics::TypeParamProvenance::ArgumentImplTrait => {
 455                         let substs = TyBuilder::type_params_subst(db, id.parent);
 456                         let predicates = db
 457                             .generic_predicates(id.parent)
 458                             .into_iter()
 459                             .map(|pred| pred.clone().substitute(&Interner, &substs))
 460                             .filter(|wc| match &wc.skip_binders() {
 461                                 WhereClause::Implemented(tr) => {
 462                                     tr.self_type_parameter(&Interner) == self
 463                                 }
 464                                 WhereClause::AliasEq(AliasEq {
 465                                     alias: AliasTy::Projection(proj),
 466                                     ty: _,
 467                                 }) => proj.self_type_parameter(&Interner) == self,
 468                                 _ => false,
 469                             })
 470                             .collect_vec();
 471
 472                         Some(predicates)
 473                     }
 474                     _ => None,
 475                 }
 476             }
 477             _ => None,
 478         }
 479     }
 480
 481     pub fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId> {
 482         match self.kind(&Interner) {
 483             TyKind::AssociatedType(id, ..) => {
 484                 match from_assoc_type_id(*id).lookup(db.upcast()).container {
 485                     AssocContainerId::TraitId(trait_id) => Some(trait_id),
 486                     _ => None,
 487                 }
 488             }
 489             TyKind::Alias(AliasTy::Projection(projection_ty)) => {
 490                 match from_assoc_type_id(projection_ty.associated_ty_id)
 491                     .lookup(db.upcast())
 492                     .container
 493                 {
 494                     AssocContainerId::TraitId(trait_id) => Some(trait_id),
 495                     _ => None,
 496                 }
 497             }
 498             _ => None,
 499         }
 500     }
 501 }
 502
 503 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
 504 pub enum ImplTraitId {
 505     ReturnTypeImplTrait(hir_def::FunctionId, u16),
 506     AsyncBlockTypeImplTrait(hir_def::DefWithBodyId, ExprId),
 507 }
 508
 509 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 510 pub struct ReturnTypeImplTraits {
 511     pub(crate) impl_traits: Vec<ReturnTypeImplTrait>,
 512 }
 513
 514 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 515 pub(crate) struct ReturnTypeImplTrait {
 516     pub(crate) bounds: Binders<Vec<QuantifiedWhereClause>>,
 517 }
 518
 519 pub fn to_foreign_def_id(id: TypeAliasId) -> ForeignDefId {
 520     chalk_ir::ForeignDefId(salsa::InternKey::as_intern_id(&id))
 521 }
 522
 523 pub fn from_foreign_def_id(id: ForeignDefId) -> TypeAliasId {
 524     salsa::InternKey::from_intern_id(id.0)
 525 }
 526
 527 pub fn to_assoc_type_id(id: TypeAliasId) -> AssocTypeId {
 528     chalk_ir::AssocTypeId(salsa::InternKey::as_intern_id(&id))
 529 }
 530
 531 pub fn from_assoc_type_id(id: AssocTypeId) -> TypeAliasId {
 532     salsa::InternKey::from_intern_id(id.0)
 533 }
 534
 535 pub fn from_placeholder_idx(db: &dyn HirDatabase, idx: PlaceholderIndex) -> TypeParamId {
 536     assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT);
 537     let interned_id = salsa::InternKey::from_intern_id(salsa::InternId::from(idx.idx));
 538     db.lookup_intern_type_param_id(interned_id)
 539 }
 540
 541 pub fn to_placeholder_idx(db: &dyn HirDatabase, id: TypeParamId) -> PlaceholderIndex {
 542     let interned_id = db.intern_type_param_id(id);
 543     PlaceholderIndex {
 544         ui: chalk_ir::UniverseIndex::ROOT,
 545         idx: salsa::InternKey::as_intern_id(&interned_id).as_usize(),
 546     }
 547 }
 548
 549 pub fn to_chalk_trait_id(id: TraitId) -> ChalkTraitId {
 550     chalk_ir::TraitId(salsa::InternKey::as_intern_id(&id))
 551 }
 552
 553 pub fn from_chalk_trait_id(id: ChalkTraitId) -> TraitId {
 554     salsa::InternKey::from_intern_id(id.0)
 555 }