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