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 pub mod mir;
  17 mod infer;
  18 mod inhabitedness;
  19 mod interner;
  20 mod lower;
  21 mod mapping;
  22 mod tls;
  23 mod utils;
  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::{collections::HashMap, hash::Hash, sync::Arc};
  39
  40 use chalk_ir::{
  41     fold::{Shift, TypeFoldable},
  42     interner::HasInterner,
  43     visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor},
  44     NoSolution, TyData,
  45 };
  46 use either::Either;
  47 use hir_def::{expr::ExprId, type_ref::Rawness, TypeOrConstParamId};
  48 use hir_expand::name;
  49 use la_arena::{Arena, Idx};
  50 use mir::MirEvalError;
  51 use rustc_hash::FxHashSet;
  52 use traits::FnTrait;
  53 use utils::Generics;
  54
  55 use crate::{
  56     consteval::unknown_const, db::HirDatabase, infer::unify::InferenceTable, utils::generics,
  57 };
  58
  59 pub use autoderef::autoderef;
  60 pub use builder::{ParamKind, TyBuilder};
  61 pub use chalk_ext::*;
  62 pub use infer::{
  63     could_coerce, could_unify, Adjust, Adjustment, AutoBorrow, BindingMode, InferenceDiagnostic,
  64     InferenceResult, OverloadedDeref, PointerCast,
  65 };
  66 pub use interner::Interner;
  67 pub use lower::{
  68     associated_type_shorthand_candidates, CallableDefId, ImplTraitLoweringMode, TyDefId,
  69     TyLoweringContext, ValueTyDefId,
  70 };
  71 pub use mapping::{
  72     from_assoc_type_id, from_chalk_trait_id, from_foreign_def_id, from_placeholder_idx,
  73     lt_from_placeholder_idx, to_assoc_type_id, to_chalk_trait_id, to_foreign_def_id,
  74     to_placeholder_idx,
  75 };
  76 pub use traits::TraitEnvironment;
  77 pub use utils::{all_super_traits, is_fn_unsafe_to_call};
  78
  79 pub use chalk_ir::{
  80     cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind,
  81 };
  82
  83 pub type ForeignDefId = chalk_ir::ForeignDefId<Interner>;
  84 pub type AssocTypeId = chalk_ir::AssocTypeId<Interner>;
  85 pub type FnDefId = chalk_ir::FnDefId<Interner>;
  86 pub type ClosureId = chalk_ir::ClosureId<Interner>;
  87 pub type OpaqueTyId = chalk_ir::OpaqueTyId<Interner>;
  88 pub type PlaceholderIndex = chalk_ir::PlaceholderIndex;
  89
  90 pub type VariableKind = chalk_ir::VariableKind<Interner>;
  91 pub type VariableKinds = chalk_ir::VariableKinds<Interner>;
  92 pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>;
  93 /// Represents generic parameters and an item bound by them. When the item has parent, the binders
  94 /// also contain the generic parameters for its parent. See chalk's documentation for details.
  95 ///
  96 /// One thing to keep in mind when working with `Binders` (and `Substitution`s, which represent
  97 /// generic arguments) in rust-analyzer is that the ordering within *is* significant - the generic
  98 /// parameters/arguments for an item MUST come before those for its parent. This is to facilitate
  99 /// the integration with chalk-solve, which mildly puts constraints as such. See #13335 for its
 100 /// motivation in detail.
 101 pub type Binders<T> = chalk_ir::Binders<T>;
 102 /// Interned list of generic arguments for an item. When an item has parent, the `Substitution` for
 103 /// it contains generic arguments for both its parent and itself. See chalk's documentation for
 104 /// details.
 105 ///
 106 /// See `Binders` for the constraint on the ordering.
 107 pub type Substitution = chalk_ir::Substitution<Interner>;
 108 pub type GenericArg = chalk_ir::GenericArg<Interner>;
 109 pub type GenericArgData = chalk_ir::GenericArgData<Interner>;
 110
 111 pub type Ty = chalk_ir::Ty<Interner>;
 112 pub type TyKind = chalk_ir::TyKind<Interner>;
 113 pub type TypeFlags = chalk_ir::TypeFlags;
 114 pub type DynTy = chalk_ir::DynTy<Interner>;
 115 pub type FnPointer = chalk_ir::FnPointer<Interner>;
 116 // pub type FnSubst = chalk_ir::FnSubst<Interner>;
 117 pub use chalk_ir::FnSubst;
 118 pub type ProjectionTy = chalk_ir::ProjectionTy<Interner>;
 119 pub type AliasTy = chalk_ir::AliasTy<Interner>;
 120 pub type OpaqueTy = chalk_ir::OpaqueTy<Interner>;
 121 pub type InferenceVar = chalk_ir::InferenceVar;
 122
 123 pub type Lifetime = chalk_ir::Lifetime<Interner>;
 124 pub type LifetimeData = chalk_ir::LifetimeData<Interner>;
 125 pub type LifetimeOutlives = chalk_ir::LifetimeOutlives<Interner>;
 126
 127 pub type Const = chalk_ir::Const<Interner>;
 128 pub type ConstData = chalk_ir::ConstData<Interner>;
 129 pub type ConstValue = chalk_ir::ConstValue<Interner>;
 130 pub type ConcreteConst = chalk_ir::ConcreteConst<Interner>;
 131
 132 pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
 133 pub type TraitRef = chalk_ir::TraitRef<Interner>;
 134 pub type QuantifiedWhereClause = Binders<WhereClause>;
 135 pub type QuantifiedWhereClauses = chalk_ir::QuantifiedWhereClauses<Interner>;
 136 pub type Canonical<T> = chalk_ir::Canonical<T>;
 137
 138 pub type FnSig = chalk_ir::FnSig<Interner>;
 139
 140 pub type InEnvironment<T> = chalk_ir::InEnvironment<T>;
 141 pub type Environment = chalk_ir::Environment<Interner>;
 142 pub type DomainGoal = chalk_ir::DomainGoal<Interner>;
 143 pub type Goal = chalk_ir::Goal<Interner>;
 144 pub type AliasEq = chalk_ir::AliasEq<Interner>;
 145 pub type Solution = chalk_solve::Solution<Interner>;
 146 pub type ConstrainedSubst = chalk_ir::ConstrainedSubst<Interner>;
 147 pub type Guidance = chalk_solve::Guidance<Interner>;
 148 pub type WhereClause = chalk_ir::WhereClause<Interner>;
 149
 150 /// A constant can have reference to other things. Memory map job is holding
 151 /// the neccessary bits of memory of the const eval session to keep the constant
 152 /// meaningful.
 153 #[derive(Debug, Default, Clone, PartialEq, Eq)]
 154 pub struct MemoryMap(pub HashMap<usize, Vec<u8>>);
 155
 156 impl MemoryMap {
 157     fn insert(&mut self, addr: usize, x: Vec<u8>) {
 158         self.0.insert(addr, x);
 159     }
 160
 161     /// This functions convert each address by a function `f` which gets the byte intervals and assign an address
 162     /// to them. It is useful when you want to load a constant with a memory map in a new memory. You can pass an
 163     /// allocator function as `f` and it will return a mapping of old addresses to new addresses.
 164     fn transform_addresses(
 165         &self,
 166         mut f: impl FnMut(&[u8]) -> Result<usize, MirEvalError>,
 167     ) -> Result<HashMap<usize, usize>, MirEvalError> {
 168         self.0.iter().map(|x| Ok((*x.0, f(x.1)?))).collect()
 169     }
 170 }
 171
 172 /// A concrete constant value
 173 #[derive(Debug, Clone, PartialEq, Eq)]
 174 pub enum ConstScalar {
 175     Bytes(Vec<u8>, MemoryMap),
 176     /// Case of an unknown value that rustc might know but we don't
 177     // FIXME: this is a hack to get around chalk not being able to represent unevaluatable
 178     // constants
 179     // https://github.com/rust-lang/rust-analyzer/pull/8813#issuecomment-840679177
 180     // https://rust-lang.zulipchat.com/#narrow/stream/144729-wg-traits/topic/Handling.20non.20evaluatable.20constants'.20equality/near/238386348
 181     Unknown,
 182 }
 183
 184 impl Hash for ConstScalar {
 185     fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
 186         core::mem::discriminant(self).hash(state);
 187         if let ConstScalar::Bytes(b, _) = self {
 188             b.hash(state)
 189         }
 190     }
 191 }
 192
 193 /// Return an index of a parameter in the generic type parameter list by it's id.
 194 pub fn param_idx(db: &dyn HirDatabase, id: TypeOrConstParamId) -> Option<usize> {
 195     generics(db.upcast(), id.parent).param_idx(id)
 196 }
 197
 198 pub(crate) fn wrap_empty_binders<T>(value: T) -> Binders<T>
 199 where
 200     T: TypeFoldable<Interner> + HasInterner<Interner = Interner>,
 201 {
 202     Binders::empty(Interner, value.shifted_in_from(Interner, DebruijnIndex::ONE))
 203 }
 204
 205 pub(crate) fn make_type_and_const_binders<T: HasInterner<Interner = Interner>>(
 206     which_is_const: impl Iterator<Item = Option<Ty>>,
 207     value: T,
 208 ) -> Binders<T> {
 209     Binders::new(
 210         VariableKinds::from_iter(
 211             Interner,
 212             which_is_const.map(|x| {
 213                 if let Some(ty) = x {
 214                     chalk_ir::VariableKind::Const(ty)
 215                 } else {
 216                     chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General)
 217                 }
 218             }),
 219         ),
 220         value,
 221     )
 222 }
 223
 224 pub(crate) fn make_single_type_binders<T: HasInterner<Interner = Interner>>(
 225     value: T,
 226 ) -> Binders<T> {
 227     Binders::new(
 228         VariableKinds::from_iter(
 229             Interner,
 230             std::iter::once(chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General)),
 231         ),
 232         value,
 233     )
 234 }
 235
 236 pub(crate) fn make_binders_with_count<T: HasInterner<Interner = Interner>>(
 237     db: &dyn HirDatabase,
 238     count: usize,
 239     generics: &Generics,
 240     value: T,
 241 ) -> Binders<T> {
 242     let it = generics.iter_id().take(count).map(|id| match id {
 243         Either::Left(_) => None,
 244         Either::Right(id) => Some(db.const_param_ty(id)),
 245     });
 246     crate::make_type_and_const_binders(it, value)
 247 }
 248
 249 pub(crate) fn make_binders<T: HasInterner<Interner = Interner>>(
 250     db: &dyn HirDatabase,
 251     generics: &Generics,
 252     value: T,
 253 ) -> Binders<T> {
 254     make_binders_with_count(db, usize::MAX, generics, value)
 255 }
 256
 257 // FIXME: get rid of this, just replace it by FnPointer
 258 /// A function signature as seen by type inference: Several parameter types and
 259 /// one return type.
 260 #[derive(Clone, PartialEq, Eq, Debug)]
 261 pub struct CallableSig {
 262     params_and_return: Arc<[Ty]>,
 263     is_varargs: bool,
 264     safety: Safety,
 265 }
 266
 267 has_interner!(CallableSig);
 268
 269 /// A polymorphic function signature.
 270 pub type PolyFnSig = Binders<CallableSig>;
 271
 272 impl CallableSig {
 273     pub fn from_params_and_return(
 274         mut params: Vec<Ty>,
 275         ret: Ty,
 276         is_varargs: bool,
 277         safety: Safety,
 278     ) -> CallableSig {
 279         params.push(ret);
 280         CallableSig { params_and_return: params.into(), is_varargs, safety }
 281     }
 282
 283     pub fn from_fn_ptr(fn_ptr: &FnPointer) -> CallableSig {
 284         CallableSig {
 285             // FIXME: what to do about lifetime params? -> return PolyFnSig
 286             params_and_return: fn_ptr
 287                 .substitution
 288                 .clone()
 289                 .shifted_out_to(Interner, DebruijnIndex::ONE)
 290                 .expect("unexpected lifetime vars in fn ptr")
 291                 .0
 292                 .as_slice(Interner)
 293                 .iter()
 294                 .map(|arg| arg.assert_ty_ref(Interner).clone())
 295                 .collect(),
 296             is_varargs: fn_ptr.sig.variadic,
 297             safety: fn_ptr.sig.safety,
 298         }
 299     }
 300
 301     pub fn to_fn_ptr(&self) -> FnPointer {
 302         FnPointer {
 303             num_binders: 0,
 304             sig: FnSig { abi: (), safety: self.safety, variadic: self.is_varargs },
 305             substitution: FnSubst(Substitution::from_iter(
 306                 Interner,
 307                 self.params_and_return.iter().cloned(),
 308             )),
 309         }
 310     }
 311
 312     pub fn params(&self) -> &[Ty] {
 313         &self.params_and_return[0..self.params_and_return.len() - 1]
 314     }
 315
 316     pub fn ret(&self) -> &Ty {
 317         &self.params_and_return[self.params_and_return.len() - 1]
 318     }
 319 }
 320
 321 impl TypeFoldable<Interner> for CallableSig {
 322     fn try_fold_with<E>(
 323         self,
 324         folder: &mut dyn chalk_ir::fold::FallibleTypeFolder<Interner, Error = E>,
 325         outer_binder: DebruijnIndex,
 326     ) -> Result<Self, E> {
 327         let vec = self.params_and_return.to_vec();
 328         let folded = vec.try_fold_with(folder, outer_binder)?;
 329         Ok(CallableSig {
 330             params_and_return: folded.into(),
 331             is_varargs: self.is_varargs,
 332             safety: self.safety,
 333         })
 334     }
 335 }
 336
 337 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
 338 pub enum ImplTraitId {
 339     ReturnTypeImplTrait(hir_def::FunctionId, RpitId),
 340     AsyncBlockTypeImplTrait(hir_def::DefWithBodyId, ExprId),
 341 }
 342
 343 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 344 pub struct ReturnTypeImplTraits {
 345     pub(crate) impl_traits: Arena<ReturnTypeImplTrait>,
 346 }
 347
 348 has_interner!(ReturnTypeImplTraits);
 349
 350 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 351 pub struct ReturnTypeImplTrait {
 352     pub(crate) bounds: Binders<Vec<QuantifiedWhereClause>>,
 353 }
 354
 355 pub type RpitId = Idx<ReturnTypeImplTrait>;
 356
 357 pub fn static_lifetime() -> Lifetime {
 358     LifetimeData::Static.intern(Interner)
 359 }
 360
 361 pub(crate) fn fold_free_vars<T: HasInterner<Interner = Interner> + TypeFoldable<Interner>>(
 362     t: T,
 363     for_ty: impl FnMut(BoundVar, DebruijnIndex) -> Ty,
 364     for_const: impl FnMut(Ty, BoundVar, DebruijnIndex) -> Const,
 365 ) -> T {
 366     use chalk_ir::fold::TypeFolder;
 367
 368     #[derive(chalk_derive::FallibleTypeFolder)]
 369     #[has_interner(Interner)]
 370     struct FreeVarFolder<
 371         F1: FnMut(BoundVar, DebruijnIndex) -> Ty,
 372         F2: FnMut(Ty, BoundVar, DebruijnIndex) -> Const,
 373     >(F1, F2);
 374     impl<
 375             F1: FnMut(BoundVar, DebruijnIndex) -> Ty,
 376             F2: FnMut(Ty, BoundVar, DebruijnIndex) -> Const,
 377         > TypeFolder<Interner> for FreeVarFolder<F1, F2>
 378     {
 379         fn as_dyn(&mut self) -> &mut dyn TypeFolder<Interner, Error = Self::Error> {
 380             self
 381         }
 382
 383         fn interner(&self) -> Interner {
 384             Interner
 385         }
 386
 387         fn fold_free_var_ty(&mut self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> Ty {
 388             self.0(bound_var, outer_binder)
 389         }
 390
 391         fn fold_free_var_const(
 392             &mut self,
 393             ty: Ty,
 394             bound_var: BoundVar,
 395             outer_binder: DebruijnIndex,
 396         ) -> Const {
 397             self.1(ty, bound_var, outer_binder)
 398         }
 399     }
 400     t.fold_with(&mut FreeVarFolder(for_ty, for_const), DebruijnIndex::INNERMOST)
 401 }
 402
 403 pub(crate) fn fold_tys<T: HasInterner<Interner = Interner> + TypeFoldable<Interner>>(
 404     t: T,
 405     mut for_ty: impl FnMut(Ty, DebruijnIndex) -> Ty,
 406     binders: DebruijnIndex,
 407 ) -> T {
 408     fold_tys_and_consts(
 409         t,
 410         |x, d| match x {
 411             Either::Left(x) => Either::Left(for_ty(x, d)),
 412             Either::Right(x) => Either::Right(x),
 413         },
 414         binders,
 415     )
 416 }
 417
 418 pub(crate) fn fold_tys_and_consts<T: HasInterner<Interner = Interner> + TypeFoldable<Interner>>(
 419     t: T,
 420     f: impl FnMut(Either<Ty, Const>, DebruijnIndex) -> Either<Ty, Const>,
 421     binders: DebruijnIndex,
 422 ) -> T {
 423     use chalk_ir::fold::{TypeFolder, TypeSuperFoldable};
 424     #[derive(chalk_derive::FallibleTypeFolder)]
 425     #[has_interner(Interner)]
 426     struct TyFolder<F: FnMut(Either<Ty, Const>, DebruijnIndex) -> Either<Ty, Const>>(F);
 427     impl<F: FnMut(Either<Ty, Const>, DebruijnIndex) -> Either<Ty, Const>> TypeFolder<Interner>
 428         for TyFolder<F>
 429     {
 430         fn as_dyn(&mut self) -> &mut dyn TypeFolder<Interner, Error = Self::Error> {
 431             self
 432         }
 433
 434         fn interner(&self) -> Interner {
 435             Interner
 436         }
 437
 438         fn fold_ty(&mut self, ty: Ty, outer_binder: DebruijnIndex) -> Ty {
 439             let ty = ty.super_fold_with(self.as_dyn(), outer_binder);
 440             self.0(Either::Left(ty), outer_binder).left().unwrap()
 441         }
 442
 443         fn fold_const(&mut self, c: Const, outer_binder: DebruijnIndex) -> Const {
 444             self.0(Either::Right(c), outer_binder).right().unwrap()
 445         }
 446     }
 447     t.fold_with(&mut TyFolder(f), binders)
 448 }
 449
 450 /// 'Canonicalizes' the `t` by replacing any errors with new variables. Also
 451 /// ensures there are no unbound variables or inference variables anywhere in
 452 /// the `t`.
 453 pub fn replace_errors_with_variables<T>(t: &T) -> Canonical<T>
 454 where
 455     T: HasInterner<Interner = Interner> + TypeFoldable<Interner> + Clone,
 456 {
 457     use chalk_ir::{
 458         fold::{FallibleTypeFolder, TypeSuperFoldable},
 459         Fallible,
 460     };
 461     struct ErrorReplacer {
 462         vars: usize,
 463     }
 464     impl FallibleTypeFolder<Interner> for ErrorReplacer {
 465         type Error = NoSolution;
 466
 467         fn as_dyn(&mut self) -> &mut dyn FallibleTypeFolder<Interner, Error = Self::Error> {
 468             self
 469         }
 470
 471         fn interner(&self) -> Interner {
 472             Interner
 473         }
 474
 475         fn try_fold_ty(&mut self, ty: Ty, outer_binder: DebruijnIndex) -> Fallible<Ty> {
 476             if let TyKind::Error = ty.kind(Interner) {
 477                 let index = self.vars;
 478                 self.vars += 1;
 479                 Ok(TyKind::BoundVar(BoundVar::new(outer_binder, index)).intern(Interner))
 480             } else {
 481                 ty.try_super_fold_with(self.as_dyn(), outer_binder)
 482             }
 483         }
 484
 485         fn try_fold_inference_ty(
 486             &mut self,
 487             _var: InferenceVar,
 488             _kind: TyVariableKind,
 489             _outer_binder: DebruijnIndex,
 490         ) -> Fallible<Ty> {
 491             if cfg!(debug_assertions) {
 492                 // we don't want to just panic here, because then the error message
 493                 // won't contain the whole thing, which would not be very helpful
 494                 Err(NoSolution)
 495             } else {
 496                 Ok(TyKind::Error.intern(Interner))
 497             }
 498         }
 499
 500         fn try_fold_free_var_ty(
 501             &mut self,
 502             _bound_var: BoundVar,
 503             _outer_binder: DebruijnIndex,
 504         ) -> Fallible<Ty> {
 505             if cfg!(debug_assertions) {
 506                 // we don't want to just panic here, because then the error message
 507                 // won't contain the whole thing, which would not be very helpful
 508                 Err(NoSolution)
 509             } else {
 510                 Ok(TyKind::Error.intern(Interner))
 511             }
 512         }
 513
 514         fn try_fold_inference_const(
 515             &mut self,
 516             ty: Ty,
 517             _var: InferenceVar,
 518             _outer_binder: DebruijnIndex,
 519         ) -> Fallible<Const> {
 520             if cfg!(debug_assertions) {
 521                 Err(NoSolution)
 522             } else {
 523                 Ok(unknown_const(ty))
 524             }
 525         }
 526
 527         fn try_fold_free_var_const(
 528             &mut self,
 529             ty: Ty,
 530             _bound_var: BoundVar,
 531             _outer_binder: DebruijnIndex,
 532         ) -> Fallible<Const> {
 533             if cfg!(debug_assertions) {
 534                 Err(NoSolution)
 535             } else {
 536                 Ok(unknown_const(ty))
 537             }
 538         }
 539
 540         fn try_fold_inference_lifetime(
 541             &mut self,
 542             _var: InferenceVar,
 543             _outer_binder: DebruijnIndex,
 544         ) -> Fallible<Lifetime> {
 545             if cfg!(debug_assertions) {
 546                 Err(NoSolution)
 547             } else {
 548                 Ok(static_lifetime())
 549             }
 550         }
 551
 552         fn try_fold_free_var_lifetime(
 553             &mut self,
 554             _bound_var: BoundVar,
 555             _outer_binder: DebruijnIndex,
 556         ) -> Fallible<Lifetime> {
 557             if cfg!(debug_assertions) {
 558                 Err(NoSolution)
 559             } else {
 560                 Ok(static_lifetime())
 561             }
 562         }
 563     }
 564     let mut error_replacer = ErrorReplacer { vars: 0 };
 565     let value = match t.clone().try_fold_with(&mut error_replacer, DebruijnIndex::INNERMOST) {
 566         Ok(t) => t,
 567         Err(_) => panic!("Encountered unbound or inference vars in {t:?}"),
 568     };
 569     let kinds = (0..error_replacer.vars).map(|_| {
 570         chalk_ir::CanonicalVarKind::new(
 571             chalk_ir::VariableKind::Ty(TyVariableKind::General),
 572             chalk_ir::UniverseIndex::ROOT,
 573         )
 574     });
 575     Canonical { value, binders: chalk_ir::CanonicalVarKinds::from_iter(Interner, kinds) }
 576 }
 577
 578 pub fn callable_sig_from_fnonce(
 579     self_ty: &Ty,
 580     env: Arc<TraitEnvironment>,
 581     db: &dyn HirDatabase,
 582 ) -> Option<CallableSig> {
 583     let krate = env.krate;
 584     let fn_once_trait = FnTrait::FnOnce.get_id(db, krate)?;
 585     let output_assoc_type = db.trait_data(fn_once_trait).associated_type_by_name(&name![Output])?;
 586
 587     let mut table = InferenceTable::new(db, env.clone());
 588     let b = TyBuilder::trait_ref(db, fn_once_trait);
 589     if b.remaining() != 2 {
 590         return None;
 591     }
 592
 593     // Register two obligations:
 594     // - Self: FnOnce<?args_ty>
 595     // - <Self as FnOnce<?args_ty>>::Output == ?ret_ty
 596     let args_ty = table.new_type_var();
 597     let trait_ref = b.push(self_ty.clone()).push(args_ty.clone()).build();
 598     let projection = TyBuilder::assoc_type_projection(
 599         db,
 600         output_assoc_type,
 601         Some(trait_ref.substitution.clone()),
 602     )
 603     .build();
 604     table.register_obligation(trait_ref.cast(Interner));
 605     let ret_ty = table.normalize_projection_ty(projection);
 606
 607     let ret_ty = table.resolve_completely(ret_ty);
 608     let args_ty = table.resolve_completely(args_ty);
 609
 610     let params =
 611         args_ty.as_tuple()?.iter(Interner).map(|it| it.assert_ty_ref(Interner)).cloned().collect();
 612
 613     Some(CallableSig::from_params_and_return(params, ret_ty, false, Safety::Safe))
 614 }
 615
 616 struct PlaceholderCollector<'db> {
 617     db: &'db dyn HirDatabase,
 618     placeholders: FxHashSet<TypeOrConstParamId>,
 619 }
 620
 621 impl PlaceholderCollector<'_> {
 622     fn collect(&mut self, idx: PlaceholderIndex) {
 623         let id = from_placeholder_idx(self.db, idx);
 624         self.placeholders.insert(id);
 625     }
 626 }
 627
 628 impl TypeVisitor<Interner> for PlaceholderCollector<'_> {
 629     type BreakTy = ();
 630
 631     fn as_dyn(&mut self) -> &mut dyn TypeVisitor<Interner, BreakTy = Self::BreakTy> {
 632         self
 633     }
 634
 635     fn interner(&self) -> Interner {
 636         Interner
 637     }
 638
 639     fn visit_ty(
 640         &mut self,
 641         ty: &Ty,
 642         outer_binder: DebruijnIndex,
 643     ) -> std::ops::ControlFlow<Self::BreakTy> {
 644         let has_placeholder_bits = TypeFlags::HAS_TY_PLACEHOLDER | TypeFlags::HAS_CT_PLACEHOLDER;
 645         let TyData { kind, flags } = ty.data(Interner);
 646
 647         if let TyKind::Placeholder(idx) = kind {
 648             self.collect(*idx);
 649         } else if flags.intersects(has_placeholder_bits) {
 650             return ty.super_visit_with(self, outer_binder);
 651         } else {
 652             // Fast path: don't visit inner types (e.g. generic arguments) when `flags` indicate
 653             // that there are no placeholders.
 654         }
 655
 656         std::ops::ControlFlow::Continue(())
 657     }
 658
 659     fn visit_const(
 660         &mut self,
 661         constant: &chalk_ir::Const<Interner>,
 662         _outer_binder: DebruijnIndex,
 663     ) -> std::ops::ControlFlow<Self::BreakTy> {
 664         if let chalk_ir::ConstValue::Placeholder(idx) = constant.data(Interner).value {
 665             self.collect(idx);
 666         }
 667         std::ops::ControlFlow::Continue(())
 668     }
 669 }
 670
 671 /// Returns unique placeholders for types and consts contained in `value`.
 672 pub fn collect_placeholders<T>(value: &T, db: &dyn HirDatabase) -> Vec<TypeOrConstParamId>
 673 where
 674     T: ?Sized + TypeVisitable<Interner>,
 675 {
 676     let mut collector = PlaceholderCollector { db, placeholders: FxHashSet::default() };
 677     value.visit_with(&mut collector, DebruijnIndex::INNERMOST);
 678     collector.placeholders.into_iter().collect()
 679 }