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