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