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