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