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