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
   4 #![warn(rust_2018_idioms, unused_lifetimes, semicolon_in_expressions_from_macros)]
   5
   6 #[allow(unused)]
   7 macro_rules! eprintln {
   8     ($($tt:tt)*) => { stdx::eprintln!($($tt)*) };
   9 }
  10
  11 mod autoderef;
  12 mod builder;
  13 mod chalk_db;
  14 mod chalk_ext;
  15 pub mod consteval;
  16 mod infer;
  17 mod inhabitedness;
  18 mod interner;
  19 mod lower;
  20 mod mapping;
  21 mod tls;
  22 mod utils;
  23 mod walk;
  24 pub mod db;
  25 pub mod diagnostics;
  26 pub mod display;
  27 pub mod method_resolution;
  28 pub mod primitive;
  29 pub mod traits;
  30
  31 #[cfg(test)]
  32 mod tests;
  33 #[cfg(test)]
  34 mod test_db;
  35
  36 use std::sync::Arc;
  37
  38 use chalk_ir::{
  39     fold::{Shift, TypeFoldable},
  40     interner::HasInterner,
  41     NoSolution,
  42 };
  43 use hir_def::{expr::ExprId, type_ref::Rawness, TypeOrConstParamId};
  44 use itertools::Either;
  45 use utils::Generics;
  46
  47 use crate::{consteval::unknown_const, db::HirDatabase, utils::generics};
  48
  49 pub use autoderef::autoderef;
  50 pub use builder::{ParamKind, TyBuilder};
  51 pub use chalk_ext::*;
  52 pub use infer::{
  53     could_coerce, could_unify, Adjust, Adjustment, AutoBorrow, BindingMode, InferenceDiagnostic,
  54     InferenceResult,
  55 };
  56 pub use interner::Interner;
  57 pub use lower::{
  58     associated_type_shorthand_candidates, CallableDefId, ImplTraitLoweringMode, TyDefId,
  59     TyLoweringContext, ValueTyDefId,
  60 };
  61 pub use mapping::{
  62     from_assoc_type_id, from_chalk_trait_id, from_foreign_def_id, from_placeholder_idx,
  63     lt_from_placeholder_idx, to_assoc_type_id, to_chalk_trait_id, to_foreign_def_id,
  64     to_placeholder_idx,
  65 };
  66 pub use traits::TraitEnvironment;
  67 pub use utils::{all_super_traits, is_fn_unsafe_to_call};
  68 pub use walk::TypeWalk;
  69
  70 pub use chalk_ir::{
  71     cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind,
  72 };
  73
  74 pub type ForeignDefId = chalk_ir::ForeignDefId<Interner>;
  75 pub type AssocTypeId = chalk_ir::AssocTypeId<Interner>;
  76 pub type FnDefId = chalk_ir::FnDefId<Interner>;
  77 pub type ClosureId = chalk_ir::ClosureId<Interner>;
  78 pub type OpaqueTyId = chalk_ir::OpaqueTyId<Interner>;
  79 pub type PlaceholderIndex = chalk_ir::PlaceholderIndex;
  80
  81 pub type VariableKind = chalk_ir::VariableKind<Interner>;
  82 pub type VariableKinds = chalk_ir::VariableKinds<Interner>;
  83 pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>;
  84 pub type Binders<T> = chalk_ir::Binders<T>;
  85 pub type Substitution = chalk_ir::Substitution<Interner>;
  86 pub type GenericArg = chalk_ir::GenericArg<Interner>;
  87 pub type GenericArgData = chalk_ir::GenericArgData<Interner>;
  88
  89 pub type Ty = chalk_ir::Ty<Interner>;
  90 pub type TyKind = chalk_ir::TyKind<Interner>;
  91 pub type DynTy = chalk_ir::DynTy<Interner>;
  92 pub type FnPointer = chalk_ir::FnPointer<Interner>;
  93 // pub type FnSubst = chalk_ir::FnSubst<Interner>;
  94 pub use chalk_ir::FnSubst;
  95 pub type ProjectionTy = chalk_ir::ProjectionTy<Interner>;
  96 pub type AliasTy = chalk_ir::AliasTy<Interner>;
  97 pub type OpaqueTy = chalk_ir::OpaqueTy<Interner>;
  98 pub type InferenceVar = chalk_ir::InferenceVar;
  99
 100 pub type Lifetime = chalk_ir::Lifetime<Interner>;
 101 pub type LifetimeData = chalk_ir::LifetimeData<Interner>;
 102 pub type LifetimeOutlives = chalk_ir::LifetimeOutlives<Interner>;
 103
 104 pub type Const = chalk_ir::Const<Interner>;
 105 pub type ConstData = chalk_ir::ConstData<Interner>;
 106 pub type ConstValue = chalk_ir::ConstValue<Interner>;
 107 pub type ConcreteConst = chalk_ir::ConcreteConst<Interner>;
 108
 109 pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
 110 pub type TraitRef = chalk_ir::TraitRef<Interner>;
 111 pub type QuantifiedWhereClause = Binders<WhereClause>;
 112 pub type QuantifiedWhereClauses = chalk_ir::QuantifiedWhereClauses<Interner>;
 113 pub type Canonical<T> = chalk_ir::Canonical<T>;
 114
 115 pub type FnSig = chalk_ir::FnSig<Interner>;
 116
 117 pub type InEnvironment<T> = chalk_ir::InEnvironment<T>;
 118 pub type Environment = chalk_ir::Environment<Interner>;
 119 pub type DomainGoal = chalk_ir::DomainGoal<Interner>;
 120 pub type Goal = chalk_ir::Goal<Interner>;
 121 pub type AliasEq = chalk_ir::AliasEq<Interner>;
 122 pub type Solution = chalk_solve::Solution<Interner>;
 123 pub type ConstrainedSubst = chalk_ir::ConstrainedSubst<Interner>;
 124 pub type Guidance = chalk_solve::Guidance<Interner>;
 125 pub type WhereClause = chalk_ir::WhereClause<Interner>;
 126
 127 // FIXME: get rid of this
 128 pub fn subst_prefix(s: &Substitution, n: usize) -> Substitution {
 129     Substitution::from_iter(
 130         Interner,
 131         s.as_slice(Interner)[..std::cmp::min(s.len(Interner), n)].iter().cloned(),
 132     )
 133 }
 134
 135 /// Return an index of a parameter in the generic type parameter list by it's id.
 136 pub fn param_idx(db: &dyn HirDatabase, id: TypeOrConstParamId) -> Option<usize> {
 137     generics(db.upcast(), id.parent).param_idx(id)
 138 }
 139
 140 pub(crate) fn wrap_empty_binders<T>(value: T) -> Binders<T>
 141 where
 142     T: TypeFoldable<Interner> + HasInterner<Interner = Interner>,
 143 {
 144     Binders::empty(Interner, value.shifted_in_from(Interner, DebruijnIndex::ONE))
 145 }
 146
 147 pub(crate) fn make_type_and_const_binders<T: HasInterner<Interner = Interner>>(
 148     which_is_const: impl Iterator<Item = Option<Ty>>,
 149     value: T,
 150 ) -> Binders<T> {
 151     Binders::new(
 152         VariableKinds::from_iter(
 153             Interner,
 154             which_is_const.map(|x| {
 155                 if let Some(ty) = x {
 156                     chalk_ir::VariableKind::Const(ty)
 157                 } else {
 158                     chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General)
 159                 }
 160             }),
 161         ),
 162         value,
 163     )
 164 }
 165
 166 pub(crate) fn make_single_type_binders<T: HasInterner<Interner = Interner>>(
 167     value: T,
 168 ) -> Binders<T> {
 169     Binders::new(
 170         VariableKinds::from_iter(
 171             Interner,
 172             std::iter::once(chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General)),
 173         ),
 174         value,
 175     )
 176 }
 177
 178 pub(crate) fn make_binders_with_count<T: HasInterner<Interner = Interner>>(
 179     db: &dyn HirDatabase,
 180     count: usize,
 181     generics: &Generics,
 182     value: T,
 183 ) -> Binders<T> {
 184     let it = generics.iter_id().take(count).map(|id| match id {
 185         Either::Left(_) => None,
 186         Either::Right(id) => Some(db.const_param_ty(id)),
 187     });
 188     crate::make_type_and_const_binders(it, value)
 189 }
 190
 191 pub(crate) fn make_binders<T: HasInterner<Interner = Interner>>(
 192     db: &dyn HirDatabase,
 193     generics: &Generics,
 194     value: T,
 195 ) -> Binders<T> {
 196     make_binders_with_count(db, usize::MAX, generics, value)
 197 }
 198
 199 // FIXME: get rid of this
 200 pub fn make_canonical<T: HasInterner<Interner = Interner>>(
 201     value: T,
 202     kinds: impl IntoIterator<Item = TyVariableKind>,
 203 ) -> Canonical<T> {
 204     let kinds = kinds.into_iter().map(|tk| {
 205         chalk_ir::CanonicalVarKind::new(
 206             chalk_ir::VariableKind::Ty(tk),
 207             chalk_ir::UniverseIndex::ROOT,
 208         )
 209     });
 210     Canonical { value, binders: chalk_ir::CanonicalVarKinds::from_iter(Interner, kinds) }
 211 }
 212
 213 // FIXME: get rid of this, just replace it by FnPointer
 214 /// A function signature as seen by type inference: Several parameter types and
 215 /// one return type.
 216 #[derive(Clone, PartialEq, Eq, Debug)]
 217 pub struct CallableSig {
 218     params_and_return: Arc<[Ty]>,
 219     is_varargs: bool,
 220 }
 221
 222 has_interner!(CallableSig);
 223
 224 /// A polymorphic function signature.
 225 pub type PolyFnSig = Binders<CallableSig>;
 226
 227 impl CallableSig {
 228     pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty, is_varargs: bool) -> CallableSig {
 229         params.push(ret);
 230         CallableSig { params_and_return: params.into(), is_varargs }
 231     }
 232
 233     pub fn from_fn_ptr(fn_ptr: &FnPointer) -> CallableSig {
 234         CallableSig {
 235             // FIXME: what to do about lifetime params? -> return PolyFnSig
 236             params_and_return: fn_ptr
 237                 .substitution
 238                 .clone()
 239                 .shifted_out_to(Interner, DebruijnIndex::ONE)
 240                 .expect("unexpected lifetime vars in fn ptr")
 241                 .0
 242                 .as_slice(Interner)
 243                 .iter()
 244                 .map(|arg| arg.assert_ty_ref(Interner).clone())
 245                 .collect(),
 246             is_varargs: fn_ptr.sig.variadic,
 247         }
 248     }
 249
 250     pub fn to_fn_ptr(&self) -> FnPointer {
 251         FnPointer {
 252             num_binders: 0,
 253             sig: FnSig { abi: (), safety: Safety::Safe, variadic: self.is_varargs },
 254             substitution: FnSubst(Substitution::from_iter(
 255                 Interner,
 256                 self.params_and_return.iter().cloned(),
 257             )),
 258         }
 259     }
 260
 261     pub fn params(&self) -> &[Ty] {
 262         &self.params_and_return[0..self.params_and_return.len() - 1]
 263     }
 264
 265     pub fn ret(&self) -> &Ty {
 266         &self.params_and_return[self.params_and_return.len() - 1]
 267     }
 268 }
 269
 270 impl TypeFoldable<Interner> for CallableSig {
 271     fn fold_with<E>(
 272         self,
 273         folder: &mut dyn chalk_ir::fold::TypeFolder<Interner, Error = E>,
 274         outer_binder: DebruijnIndex,
 275     ) -> Result<Self, E> {
 276         let vec = self.params_and_return.to_vec();
 277         let folded = vec.fold_with(folder, outer_binder)?;
 278         Ok(CallableSig { params_and_return: folded.into(), is_varargs: self.is_varargs })
 279     }
 280 }
 281
 282 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
 283 pub enum ImplTraitId {
 284     ReturnTypeImplTrait(hir_def::FunctionId, u16),
 285     AsyncBlockTypeImplTrait(hir_def::DefWithBodyId, ExprId),
 286 }
 287
 288 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 289 pub struct ReturnTypeImplTraits {
 290     pub(crate) impl_traits: Vec<ReturnTypeImplTrait>,
 291 }
 292
 293 has_interner!(ReturnTypeImplTraits);
 294
 295 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 296 pub(crate) struct ReturnTypeImplTrait {
 297     pub(crate) bounds: Binders<Vec<QuantifiedWhereClause>>,
 298 }
 299
 300 pub fn static_lifetime() -> Lifetime {
 301     LifetimeData::Static.intern(Interner)
 302 }
 303
 304 pub(crate) fn fold_free_vars<T: HasInterner<Interner = Interner> + TypeFoldable<Interner>>(
 305     t: T,
 306     for_ty: impl FnMut(BoundVar, DebruijnIndex) -> Ty,
 307     for_const: impl FnMut(Ty, BoundVar, DebruijnIndex) -> Const,
 308 ) -> T {
 309     use chalk_ir::{fold::TypeFolder, Fallible};
 310     struct FreeVarFolder<F1, F2>(F1, F2);
 311     impl<
 312             'i,
 313             F1: FnMut(BoundVar, DebruijnIndex) -> Ty + 'i,
 314             F2: FnMut(Ty, BoundVar, DebruijnIndex) -> Const + 'i,
 315         > TypeFolder<Interner> for FreeVarFolder<F1, F2>
 316     {
 317         type Error = NoSolution;
 318
 319         fn as_dyn(&mut self) -> &mut dyn TypeFolder<Interner, Error = Self::Error> {
 320             self
 321         }
 322
 323         fn interner(&self) -> Interner {
 324             Interner
 325         }
 326
 327         fn fold_free_var_ty(
 328             &mut self,
 329             bound_var: BoundVar,
 330             outer_binder: DebruijnIndex,
 331         ) -> Fallible<Ty> {
 332             Ok(self.0(bound_var, outer_binder))
 333         }
 334
 335         fn fold_free_var_const(
 336             &mut self,
 337             ty: Ty,
 338             bound_var: BoundVar,
 339             outer_binder: DebruijnIndex,
 340         ) -> Fallible<Const> {
 341             Ok(self.1(ty, bound_var, outer_binder))
 342         }
 343     }
 344     t.fold_with(&mut FreeVarFolder(for_ty, for_const), DebruijnIndex::INNERMOST)
 345         .expect("fold failed unexpectedly")
 346 }
 347
 348 pub(crate) fn fold_tys<T: HasInterner<Interner = Interner> + TypeFoldable<Interner>>(
 349     t: T,
 350     mut for_ty: impl FnMut(Ty, DebruijnIndex) -> Ty,
 351     binders: DebruijnIndex,
 352 ) -> T {
 353     fold_tys_and_consts(
 354         t,
 355         |x, d| match x {
 356             Either::Left(x) => Either::Left(for_ty(x, d)),
 357             Either::Right(x) => Either::Right(x),
 358         },
 359         binders,
 360     )
 361 }
 362
 363 pub(crate) fn fold_tys_and_consts<T: HasInterner<Interner = Interner> + TypeFoldable<Interner>>(
 364     t: T,
 365     f: impl FnMut(Either<Ty, Const>, DebruijnIndex) -> Either<Ty, Const>,
 366     binders: DebruijnIndex,
 367 ) -> T {
 368     use chalk_ir::{
 369         fold::{TypeFolder, TypeSuperFoldable},
 370         Fallible,
 371     };
 372     struct TyFolder<F>(F);
 373     impl<'i, F: FnMut(Either<Ty, Const>, DebruijnIndex) -> Either<Ty, Const> + 'i>
 374         TypeFolder<Interner> for TyFolder<F>
 375     {
 376         type Error = NoSolution;
 377
 378         fn as_dyn(&mut self) -> &mut dyn TypeFolder<Interner, Error = Self::Error> {
 379             self
 380         }
 381
 382         fn interner(&self) -> Interner {
 383             Interner
 384         }
 385
 386         fn fold_ty(&mut self, ty: Ty, outer_binder: DebruijnIndex) -> Fallible<Ty> {
 387             let ty = ty.super_fold_with(self.as_dyn(), outer_binder)?;
 388             Ok(self.0(Either::Left(ty), outer_binder).left().unwrap())
 389         }
 390
 391         fn fold_const(&mut self, c: Const, outer_binder: DebruijnIndex) -> Fallible<Const> {
 392             Ok(self.0(Either::Right(c), outer_binder).right().unwrap())
 393         }
 394     }
 395     t.fold_with(&mut TyFolder(f), binders).expect("fold failed unexpectedly")
 396 }
 397
 398 /// 'Canonicalizes' the `t` by replacing any errors with new variables. Also
 399 /// ensures there are no unbound variables or inference variables anywhere in
 400 /// the `t`.
 401 pub fn replace_errors_with_variables<T>(t: &T) -> Canonical<T>
 402 where
 403     T: HasInterner<Interner = Interner> + TypeFoldable<Interner> + Clone,
 404     T: HasInterner<Interner = Interner>,
 405 {
 406     use chalk_ir::{
 407         fold::{TypeFolder, TypeSuperFoldable},
 408         Fallible,
 409     };
 410     struct ErrorReplacer {
 411         vars: usize,
 412     }
 413     impl TypeFolder<Interner> for ErrorReplacer {
 414         type Error = NoSolution;
 415
 416         fn as_dyn(&mut self) -> &mut dyn TypeFolder<Interner, Error = Self::Error> {
 417             self
 418         }
 419
 420         fn interner(&self) -> Interner {
 421             Interner
 422         }
 423
 424         fn fold_ty(&mut self, ty: Ty, outer_binder: DebruijnIndex) -> Fallible<Ty> {
 425             if let TyKind::Error = ty.kind(Interner) {
 426                 let index = self.vars;
 427                 self.vars += 1;
 428                 Ok(TyKind::BoundVar(BoundVar::new(outer_binder, index)).intern(Interner))
 429             } else {
 430                 let ty = ty.super_fold_with(self.as_dyn(), outer_binder)?;
 431                 Ok(ty)
 432             }
 433         }
 434
 435         fn fold_inference_ty(
 436             &mut self,
 437             _var: InferenceVar,
 438             _kind: TyVariableKind,
 439             _outer_binder: DebruijnIndex,
 440         ) -> Fallible<Ty> {
 441             if cfg!(debug_assertions) {
 442                 // we don't want to just panic here, because then the error message
 443                 // won't contain the whole thing, which would not be very helpful
 444                 Err(NoSolution)
 445             } else {
 446                 Ok(TyKind::Error.intern(Interner))
 447             }
 448         }
 449
 450         fn fold_free_var_ty(
 451             &mut self,
 452             _bound_var: BoundVar,
 453             _outer_binder: DebruijnIndex,
 454         ) -> Fallible<Ty> {
 455             if cfg!(debug_assertions) {
 456                 // we don't want to just panic here, because then the error message
 457                 // won't contain the whole thing, which would not be very helpful
 458                 Err(NoSolution)
 459             } else {
 460                 Ok(TyKind::Error.intern(Interner))
 461             }
 462         }
 463
 464         fn fold_inference_const(
 465             &mut self,
 466             ty: Ty,
 467             _var: InferenceVar,
 468             _outer_binder: DebruijnIndex,
 469         ) -> Fallible<Const> {
 470             if cfg!(debug_assertions) {
 471                 Err(NoSolution)
 472             } else {
 473                 Ok(unknown_const(ty))
 474             }
 475         }
 476
 477         fn fold_free_var_const(
 478             &mut self,
 479             ty: Ty,
 480             _bound_var: BoundVar,
 481             _outer_binder: DebruijnIndex,
 482         ) -> Fallible<Const> {
 483             if cfg!(debug_assertions) {
 484                 Err(NoSolution)
 485             } else {
 486                 Ok(unknown_const(ty))
 487             }
 488         }
 489
 490         fn fold_inference_lifetime(
 491             &mut self,
 492             _var: InferenceVar,
 493             _outer_binder: DebruijnIndex,
 494         ) -> Fallible<Lifetime> {
 495             if cfg!(debug_assertions) {
 496                 Err(NoSolution)
 497             } else {
 498                 Ok(static_lifetime())
 499             }
 500         }
 501
 502         fn fold_free_var_lifetime(
 503             &mut self,
 504             _bound_var: BoundVar,
 505             _outer_binder: DebruijnIndex,
 506         ) -> Fallible<Lifetime> {
 507             if cfg!(debug_assertions) {
 508                 Err(NoSolution)
 509             } else {
 510                 Ok(static_lifetime())
 511             }
 512         }
 513     }
 514     let mut error_replacer = ErrorReplacer { vars: 0 };
 515     let value = match t.clone().fold_with(&mut error_replacer, DebruijnIndex::INNERMOST) {
 516         Ok(t) => t,
 517         Err(_) => panic!("Encountered unbound or inference vars in {:?}", t),
 518     };
 519     let kinds = (0..error_replacer.vars).map(|_| {
 520         chalk_ir::CanonicalVarKind::new(
 521             chalk_ir::VariableKind::Ty(TyVariableKind::General),
 522             chalk_ir::UniverseIndex::ROOT,
 523         )
 524     });
 525     Canonical { value, binders: chalk_ir::CanonicalVarKinds::from_iter(Interner, kinds) }
 526 }