crates/hir_ty/src/lower.rs

   1 //! Methods for lowering the HIR to types. There are two main cases here:
   2 //!
   3 //!  - Lowering a type reference like `&usize` or `Option<foo::bar::Baz>` to a
   4 //!    type: The entry point for this is `Ty::from_hir`.
   5 //!  - Building the type for an item: This happens through the `type_for_def` query.
   6 //!
   7 //! This usually involves resolving names, collecting generic arguments etc.
   8 use std::{iter, sync::Arc};
   9
  10 use base_db::CrateId;
  11 use chalk_ir::{cast::Cast, Mutability, Safety};
  12 use hir_def::{
  13     adt::StructKind,
  14     builtin_type::BuiltinType,
  15     generics::{TypeParamProvenance, WherePredicate, WherePredicateTypeTarget},
  16     path::{GenericArg, Path, PathSegment, PathSegments},
  17     resolver::{HasResolver, Resolver, TypeNs},
  18     type_ref::{TypeBound, TypeRef},
  19     AdtId, AssocContainerId, AssocItemId, ConstId, ConstParamId, EnumId, EnumVariantId, FunctionId,
  20     GenericDefId, HasModule, ImplId, LocalFieldId, Lookup, StaticId, StructId, TraitId,
  21     TypeAliasId, TypeParamId, UnionId, VariantId,
  22 };
  23 use hir_expand::name::Name;
  24 use la_arena::ArenaMap;
  25 use smallvec::SmallVec;
  26 use stdx::impl_from;
  27
  28 use crate::{
  29     db::HirDatabase,
  30     to_assoc_type_id, to_chalk_trait_id, to_placeholder_idx,
  31     traits::chalk::{Interner, ToChalk},
  32     utils::{
  33         all_super_trait_refs, associated_type_by_name_including_super_traits, generics,
  34         variant_data,
  35     },
  36     AliasEq, AliasTy, Binders, BoundVar, CallableSig, DebruijnIndex, FnPointer, FnSig, ImplTraitId,
  37     OpaqueTy, PolyFnSig, ProjectionTy, ReturnTypeImplTrait, ReturnTypeImplTraits, Substitution,
  38     TraitEnvironment, TraitRef, Ty, TyKind, TypeWalk, WhereClause,
  39 };
  40
  41 #[derive(Debug)]
  42 pub struct TyLoweringContext<'a> {
  43     pub db: &'a dyn HirDatabase,
  44     pub resolver: &'a Resolver,
  45     in_binders: DebruijnIndex,
  46     /// Note: Conceptually, it's thinkable that we could be in a location where
  47     /// some type params should be represented as placeholders, and others
  48     /// should be converted to variables. I think in practice, this isn't
  49     /// possible currently, so this should be fine for now.
  50     pub type_param_mode: TypeParamLoweringMode,
  51     pub impl_trait_mode: ImplTraitLoweringMode,
  52     impl_trait_counter: std::cell::Cell<u16>,
  53     /// When turning `impl Trait` into opaque types, we have to collect the
  54     /// bounds at the same time to get the IDs correct (without becoming too
  55     /// complicated). I don't like using interior mutability (as for the
  56     /// counter), but I've tried and failed to make the lifetimes work for
  57     /// passing around a `&mut TyLoweringContext`. The core problem is that
  58     /// we're grouping the mutable data (the counter and this field) together
  59     /// with the immutable context (the references to the DB and resolver).
  60     /// Splitting this up would be a possible fix.
  61     opaque_type_data: std::cell::RefCell<Vec<ReturnTypeImplTrait>>,
  62 }
  63
  64 impl<'a> TyLoweringContext<'a> {
  65     pub fn new(db: &'a dyn HirDatabase, resolver: &'a Resolver) -> Self {
  66         let impl_trait_counter = std::cell::Cell::new(0);
  67         let impl_trait_mode = ImplTraitLoweringMode::Disallowed;
  68         let type_param_mode = TypeParamLoweringMode::Placeholder;
  69         let in_binders = DebruijnIndex::INNERMOST;
  70         let opaque_type_data = std::cell::RefCell::new(Vec::new());
  71         Self {
  72             db,
  73             resolver,
  74             in_binders,
  75             impl_trait_mode,
  76             impl_trait_counter,
  77             type_param_mode,
  78             opaque_type_data,
  79         }
  80     }
  81
  82     pub fn with_debruijn<T>(
  83         &self,
  84         debruijn: DebruijnIndex,
  85         f: impl FnOnce(&TyLoweringContext) -> T,
  86     ) -> T {
  87         let opaque_ty_data_vec = self.opaque_type_data.replace(Vec::new());
  88         let new_ctx = Self {
  89             in_binders: debruijn,
  90             impl_trait_counter: std::cell::Cell::new(self.impl_trait_counter.get()),
  91             opaque_type_data: std::cell::RefCell::new(opaque_ty_data_vec),
  92             ..*self
  93         };
  94         let result = f(&new_ctx);
  95         self.impl_trait_counter.set(new_ctx.impl_trait_counter.get());
  96         self.opaque_type_data.replace(new_ctx.opaque_type_data.into_inner());
  97         result
  98     }
  99
 100     pub fn with_shifted_in<T>(
 101         &self,
 102         debruijn: DebruijnIndex,
 103         f: impl FnOnce(&TyLoweringContext) -> T,
 104     ) -> T {
 105         self.with_debruijn(self.in_binders.shifted_in_from(debruijn), f)
 106     }
 107
 108     pub fn with_impl_trait_mode(self, impl_trait_mode: ImplTraitLoweringMode) -> Self {
 109         Self { impl_trait_mode, ..self }
 110     }
 111
 112     pub fn with_type_param_mode(self, type_param_mode: TypeParamLoweringMode) -> Self {
 113         Self { type_param_mode, ..self }
 114     }
 115 }
 116
 117 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 118 pub enum ImplTraitLoweringMode {
 119     /// `impl Trait` gets lowered into an opaque type that doesn't unify with
 120     /// anything except itself. This is used in places where values flow 'out',
 121     /// i.e. for arguments of the function we're currently checking, and return
 122     /// types of functions we're calling.
 123     Opaque,
 124     /// `impl Trait` gets lowered into a type variable. Used for argument
 125     /// position impl Trait when inside the respective function, since it allows
 126     /// us to support that without Chalk.
 127     Param,
 128     /// `impl Trait` gets lowered into a variable that can unify with some
 129     /// type. This is used in places where values flow 'in', i.e. for arguments
 130     /// of functions we're calling, and the return type of the function we're
 131     /// currently checking.
 132     Variable,
 133     /// `impl Trait` is disallowed and will be an error.
 134     Disallowed,
 135 }
 136
 137 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 138 pub enum TypeParamLoweringMode {
 139     Placeholder,
 140     Variable,
 141 }
 142
 143 impl<'a> TyLoweringContext<'a> {
 144     pub fn lower_ty(&self, type_ref: &TypeRef) -> Ty {
 145         self.lower_ty_ext(type_ref).0
 146     }
 147
 148     fn lower_ty_ext(&self, type_ref: &TypeRef) -> (Ty, Option<TypeNs>) {
 149         let mut res = None;
 150         let ty = match type_ref {
 151             TypeRef::Never => TyKind::Never.intern(&Interner),
 152             TypeRef::Tuple(inner) => {
 153                 let inner_tys = inner.iter().map(|tr| self.lower_ty(tr));
 154                 TyKind::Tuple(inner_tys.len(), Substitution::from_iter(&Interner, inner_tys))
 155                     .intern(&Interner)
 156             }
 157             TypeRef::Path(path) => {
 158                 let (ty, res_) = self.lower_path(path);
 159                 res = res_;
 160                 ty
 161             }
 162             TypeRef::RawPtr(inner, mutability) => {
 163                 let inner_ty = self.lower_ty(inner);
 164                 TyKind::Raw(lower_to_chalk_mutability(*mutability), inner_ty).intern(&Interner)
 165             }
 166             TypeRef::Array(inner) => {
 167                 let inner_ty = self.lower_ty(inner);
 168                 TyKind::Array(inner_ty).intern(&Interner)
 169             }
 170             TypeRef::Slice(inner) => {
 171                 let inner_ty = self.lower_ty(inner);
 172                 TyKind::Slice(inner_ty).intern(&Interner)
 173             }
 174             TypeRef::Reference(inner, _, mutability) => {
 175                 let inner_ty = self.lower_ty(inner);
 176                 TyKind::Ref(lower_to_chalk_mutability(*mutability), inner_ty).intern(&Interner)
 177             }
 178             TypeRef::Placeholder => TyKind::Unknown.intern(&Interner),
 179             TypeRef::Fn(params, is_varargs) => {
 180                 let substs = Substitution(params.iter().map(|tr| self.lower_ty(tr)).collect());
 181                 TyKind::Function(FnPointer {
 182                     num_args: substs.len() - 1,
 183                     sig: FnSig { abi: (), safety: Safety::Safe, variadic: *is_varargs },
 184                     substs,
 185                 })
 186                 .intern(&Interner)
 187             }
 188             TypeRef::DynTrait(bounds) => {
 189                 let self_ty =
 190                     TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(&Interner);
 191                 let predicates = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
 192                     bounds
 193                         .iter()
 194                         .flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false))
 195                         .collect()
 196                 });
 197                 TyKind::Dyn(predicates).intern(&Interner)
 198             }
 199             TypeRef::ImplTrait(bounds) => {
 200                 match self.impl_trait_mode {
 201                     ImplTraitLoweringMode::Opaque => {
 202                         let idx = self.impl_trait_counter.get();
 203                         self.impl_trait_counter.set(idx + 1);
 204
 205                         assert!(idx as usize == self.opaque_type_data.borrow().len());
 206                         // this dance is to make sure the data is in the right
 207                         // place even if we encounter more opaque types while
 208                         // lowering the bounds
 209                         self.opaque_type_data
 210                             .borrow_mut()
 211                             .push(ReturnTypeImplTrait { bounds: Binders::new(1, Vec::new()) });
 212                         // We don't want to lower the bounds inside the binders
 213                         // we're currently in, because they don't end up inside
 214                         // those binders. E.g. when we have `impl Trait<impl
 215                         // OtherTrait<T>>`, the `impl OtherTrait<T>` can't refer
 216                         // to the self parameter from `impl Trait`, and the
 217                         // bounds aren't actually stored nested within each
 218                         // other, but separately. So if the `T` refers to a type
 219                         // parameter of the outer function, it's just one binder
 220                         // away instead of two.
 221                         let actual_opaque_type_data = self
 222                             .with_debruijn(DebruijnIndex::INNERMOST, |ctx| {
 223                                 ctx.lower_impl_trait(&bounds)
 224                             });
 225                         self.opaque_type_data.borrow_mut()[idx as usize] = actual_opaque_type_data;
 226
 227                         let func = match self.resolver.generic_def() {
 228                             Some(GenericDefId::FunctionId(f)) => f,
 229                             _ => panic!("opaque impl trait lowering in non-function"),
 230                         };
 231                         let impl_trait_id = ImplTraitId::ReturnTypeImplTrait(func, idx);
 232                         let opaque_ty_id = self.db.intern_impl_trait_id(impl_trait_id).into();
 233                         let generics = generics(self.db.upcast(), func.into());
 234                         let parameters = Substitution::bound_vars(&generics, self.in_binders);
 235                         TyKind::Alias(AliasTy::Opaque(OpaqueTy {
 236                             opaque_ty_id,
 237                             substitution: parameters,
 238                         }))
 239                         .intern(&Interner)
 240                     }
 241                     ImplTraitLoweringMode::Param => {
 242                         let idx = self.impl_trait_counter.get();
 243                         // FIXME we're probably doing something wrong here
 244                         self.impl_trait_counter.set(idx + count_impl_traits(type_ref) as u16);
 245                         if let Some(def) = self.resolver.generic_def() {
 246                             let generics = generics(self.db.upcast(), def);
 247                             let param = generics
 248                                 .iter()
 249                                 .filter(|(_, data)| {
 250                                     data.provenance == TypeParamProvenance::ArgumentImplTrait
 251                                 })
 252                                 .nth(idx as usize)
 253                                 .map_or(TyKind::Unknown, |(id, _)| {
 254                                     TyKind::Placeholder(to_placeholder_idx(self.db, id))
 255                                 });
 256                             param.intern(&Interner)
 257                         } else {
 258                             TyKind::Unknown.intern(&Interner)
 259                         }
 260                     }
 261                     ImplTraitLoweringMode::Variable => {
 262                         let idx = self.impl_trait_counter.get();
 263                         // FIXME we're probably doing something wrong here
 264                         self.impl_trait_counter.set(idx + count_impl_traits(type_ref) as u16);
 265                         let (parent_params, self_params, list_params, _impl_trait_params) =
 266                             if let Some(def) = self.resolver.generic_def() {
 267                                 let generics = generics(self.db.upcast(), def);
 268                                 generics.provenance_split()
 269                             } else {
 270                                 (0, 0, 0, 0)
 271                             };
 272                         TyKind::BoundVar(BoundVar::new(
 273                             self.in_binders,
 274                             idx as usize + parent_params + self_params + list_params,
 275                         ))
 276                         .intern(&Interner)
 277                     }
 278                     ImplTraitLoweringMode::Disallowed => {
 279                         // FIXME: report error
 280                         TyKind::Unknown.intern(&Interner)
 281                     }
 282                 }
 283             }
 284             TypeRef::Error => TyKind::Unknown.intern(&Interner),
 285         };
 286         (ty, res)
 287     }
 288
 289     /// This is only for `generic_predicates_for_param`, where we can't just
 290     /// lower the self types of the predicates since that could lead to cycles.
 291     /// So we just check here if the `type_ref` resolves to a generic param, and which.
 292     fn lower_ty_only_param(&self, type_ref: &TypeRef) -> Option<TypeParamId> {
 293         let path = match type_ref {
 294             TypeRef::Path(path) => path,
 295             _ => return None,
 296         };
 297         if path.type_anchor().is_some() {
 298             return None;
 299         }
 300         if path.segments().len() > 1 {
 301             return None;
 302         }
 303         let resolution =
 304             match self.resolver.resolve_path_in_type_ns(self.db.upcast(), path.mod_path()) {
 305                 Some((it, None)) => it,
 306                 _ => return None,
 307             };
 308         if let TypeNs::GenericParam(param_id) = resolution {
 309             Some(param_id)
 310         } else {
 311             None
 312         }
 313     }
 314
 315     pub(crate) fn lower_ty_relative_path(
 316         &self,
 317         ty: Ty,
 318         // We need the original resolution to lower `Self::AssocTy` correctly
 319         res: Option<TypeNs>,
 320         remaining_segments: PathSegments<'_>,
 321     ) -> (Ty, Option<TypeNs>) {
 322         if remaining_segments.len() == 1 {
 323             // resolve unselected assoc types
 324             let segment = remaining_segments.first().unwrap();
 325             (self.select_associated_type(res, segment), None)
 326         } else if remaining_segments.len() > 1 {
 327             // FIXME report error (ambiguous associated type)
 328             (TyKind::Unknown.intern(&Interner), None)
 329         } else {
 330             (ty, res)
 331         }
 332     }
 333
 334     pub(crate) fn lower_partly_resolved_path(
 335         &self,
 336         resolution: TypeNs,
 337         resolved_segment: PathSegment<'_>,
 338         remaining_segments: PathSegments<'_>,
 339         infer_args: bool,
 340     ) -> (Ty, Option<TypeNs>) {
 341         let ty = match resolution {
 342             TypeNs::TraitId(trait_) => {
 343                 // if this is a bare dyn Trait, we'll directly put the required ^0 for the self type in there
 344                 let self_ty = if remaining_segments.len() == 0 {
 345                     Some(
 346                         TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0))
 347                             .intern(&Interner),
 348                     )
 349                 } else {
 350                     None
 351                 };
 352                 let trait_ref =
 353                     self.lower_trait_ref_from_resolved_path(trait_, resolved_segment, self_ty);
 354                 let ty = if remaining_segments.len() == 1 {
 355                     let segment = remaining_segments.first().unwrap();
 356                     let found = associated_type_by_name_including_super_traits(
 357                         self.db,
 358                         trait_ref,
 359                         &segment.name,
 360                     );
 361                     match found {
 362                         Some((super_trait_ref, associated_ty)) => {
 363                             // FIXME handle type parameters on the segment
 364                             TyKind::Alias(AliasTy::Projection(ProjectionTy {
 365                                 associated_ty_id: to_assoc_type_id(associated_ty),
 366                                 substitution: super_trait_ref.substitution,
 367                             }))
 368                             .intern(&Interner)
 369                         }
 370                         None => {
 371                             // FIXME: report error (associated type not found)
 372                             TyKind::Unknown.intern(&Interner)
 373                         }
 374                     }
 375                 } else if remaining_segments.len() > 1 {
 376                     // FIXME report error (ambiguous associated type)
 377                     TyKind::Unknown.intern(&Interner)
 378                 } else {
 379                     TyKind::Dyn(Arc::new([WhereClause::Implemented(trait_ref)])).intern(&Interner)
 380                 };
 381                 return (ty, None);
 382             }
 383             TypeNs::GenericParam(param_id) => {
 384                 let generics = generics(
 385                     self.db.upcast(),
 386                     self.resolver.generic_def().expect("generics in scope"),
 387                 );
 388                 match self.type_param_mode {
 389                     TypeParamLoweringMode::Placeholder => {
 390                         TyKind::Placeholder(to_placeholder_idx(self.db, param_id))
 391                     }
 392                     TypeParamLoweringMode::Variable => {
 393                         let idx = generics.param_idx(param_id).expect("matching generics");
 394                         TyKind::BoundVar(BoundVar::new(self.in_binders, idx))
 395                     }
 396                 }
 397                 .intern(&Interner)
 398             }
 399             TypeNs::SelfType(impl_id) => {
 400                 let generics = generics(self.db.upcast(), impl_id.into());
 401                 let substs = match self.type_param_mode {
 402                     TypeParamLoweringMode::Placeholder => {
 403                         Substitution::type_params_for_generics(self.db, &generics)
 404                     }
 405                     TypeParamLoweringMode::Variable => {
 406                         Substitution::bound_vars(&generics, self.in_binders)
 407                     }
 408                 };
 409                 self.db.impl_self_ty(impl_id).subst(&substs)
 410             }
 411             TypeNs::AdtSelfType(adt) => {
 412                 let generics = generics(self.db.upcast(), adt.into());
 413                 let substs = match self.type_param_mode {
 414                     TypeParamLoweringMode::Placeholder => {
 415                         Substitution::type_params_for_generics(self.db, &generics)
 416                     }
 417                     TypeParamLoweringMode::Variable => {
 418                         Substitution::bound_vars(&generics, self.in_binders)
 419                     }
 420                 };
 421                 self.db.ty(adt.into()).subst(&substs)
 422             }
 423
 424             TypeNs::AdtId(it) => self.lower_path_inner(resolved_segment, it.into(), infer_args),
 425             TypeNs::BuiltinType(it) => {
 426                 self.lower_path_inner(resolved_segment, it.into(), infer_args)
 427             }
 428             TypeNs::TypeAliasId(it) => {
 429                 self.lower_path_inner(resolved_segment, it.into(), infer_args)
 430             }
 431             // FIXME: report error
 432             TypeNs::EnumVariantId(_) => return (TyKind::Unknown.intern(&Interner), None),
 433         };
 434         self.lower_ty_relative_path(ty, Some(resolution), remaining_segments)
 435     }
 436
 437     pub(crate) fn lower_path(&self, path: &Path) -> (Ty, Option<TypeNs>) {
 438         // Resolve the path (in type namespace)
 439         if let Some(type_ref) = path.type_anchor() {
 440             let (ty, res) = self.lower_ty_ext(&type_ref);
 441             return self.lower_ty_relative_path(ty, res, path.segments());
 442         }
 443         let (resolution, remaining_index) =
 444             match self.resolver.resolve_path_in_type_ns(self.db.upcast(), path.mod_path()) {
 445                 Some(it) => it,
 446                 None => return (TyKind::Unknown.intern(&Interner), None),
 447             };
 448         let (resolved_segment, remaining_segments) = match remaining_index {
 449             None => (
 450                 path.segments().last().expect("resolved path has at least one element"),
 451                 PathSegments::EMPTY,
 452             ),
 453             Some(i) => (path.segments().get(i - 1).unwrap(), path.segments().skip(i)),
 454         };
 455         self.lower_partly_resolved_path(resolution, resolved_segment, remaining_segments, false)
 456     }
 457
 458     fn select_associated_type(&self, res: Option<TypeNs>, segment: PathSegment<'_>) -> Ty {
 459         if let Some(res) = res {
 460             let ty = associated_type_shorthand_candidates(
 461                 self.db,
 462                 res,
 463                 move |name, t, associated_ty| {
 464                     if name == segment.name {
 465                         let substs = match self.type_param_mode {
 466                             TypeParamLoweringMode::Placeholder => {
 467                                 // if we're lowering to placeholders, we have to put
 468                                 // them in now
 469                                 let s = Substitution::type_params(
 470                                     self.db,
 471                                     self.resolver.generic_def().expect(
 472                                         "there should be generics if there's a generic param",
 473                                     ),
 474                                 );
 475                                 t.substitution.clone().subst_bound_vars(&s)
 476                             }
 477                             TypeParamLoweringMode::Variable => t.substitution.clone(),
 478                         };
 479                         // We need to shift in the bound vars, since
 480                         // associated_type_shorthand_candidates does not do that
 481                         let substs = substs.shift_bound_vars(self.in_binders);
 482                         // FIXME handle type parameters on the segment
 483                         return Some(
 484                             TyKind::Alias(AliasTy::Projection(ProjectionTy {
 485                                 associated_ty_id: to_assoc_type_id(associated_ty),
 486                                 substitution: substs,
 487                             }))
 488                             .intern(&Interner),
 489                         );
 490                     }
 491
 492                     None
 493                 },
 494             );
 495
 496             ty.unwrap_or(TyKind::Unknown.intern(&Interner))
 497         } else {
 498             TyKind::Unknown.intern(&Interner)
 499         }
 500     }
 501
 502     fn lower_path_inner(
 503         &self,
 504         segment: PathSegment<'_>,
 505         typeable: TyDefId,
 506         infer_args: bool,
 507     ) -> Ty {
 508         let generic_def = match typeable {
 509             TyDefId::BuiltinType(_) => None,
 510             TyDefId::AdtId(it) => Some(it.into()),
 511             TyDefId::TypeAliasId(it) => Some(it.into()),
 512         };
 513         let substs = self.substs_from_path_segment(segment, generic_def, infer_args);
 514         self.db.ty(typeable).subst(&substs)
 515     }
 516
 517     /// Collect generic arguments from a path into a `Substs`. See also
 518     /// `create_substs_for_ast_path` and `def_to_ty` in rustc.
 519     pub(super) fn substs_from_path(
 520         &self,
 521         path: &Path,
 522         // Note that we don't call `db.value_type(resolved)` here,
 523         // `ValueTyDefId` is just a convenient way to pass generics and
 524         // special-case enum variants
 525         resolved: ValueTyDefId,
 526         infer_args: bool,
 527     ) -> Substitution {
 528         let last = path.segments().last().expect("path should have at least one segment");
 529         let (segment, generic_def) = match resolved {
 530             ValueTyDefId::FunctionId(it) => (last, Some(it.into())),
 531             ValueTyDefId::StructId(it) => (last, Some(it.into())),
 532             ValueTyDefId::UnionId(it) => (last, Some(it.into())),
 533             ValueTyDefId::ConstId(it) => (last, Some(it.into())),
 534             ValueTyDefId::StaticId(_) => (last, None),
 535             ValueTyDefId::EnumVariantId(var) => {
 536                 // the generic args for an enum variant may be either specified
 537                 // on the segment referring to the enum, or on the segment
 538                 // referring to the variant. So `Option::<T>::None` and
 539                 // `Option::None::<T>` are both allowed (though the former is
 540                 // preferred). See also `def_ids_for_path_segments` in rustc.
 541                 let len = path.segments().len();
 542                 let penultimate = if len >= 2 { path.segments().get(len - 2) } else { None };
 543                 let segment = match penultimate {
 544                     Some(segment) if segment.args_and_bindings.is_some() => segment,
 545                     _ => last,
 546                 };
 547                 (segment, Some(var.parent.into()))
 548             }
 549         };
 550         self.substs_from_path_segment(segment, generic_def, infer_args)
 551     }
 552
 553     fn substs_from_path_segment(
 554         &self,
 555         segment: PathSegment<'_>,
 556         def_generic: Option<GenericDefId>,
 557         infer_args: bool,
 558     ) -> Substitution {
 559         let mut substs = Vec::new();
 560         let def_generics = def_generic.map(|def| generics(self.db.upcast(), def));
 561
 562         let (parent_params, self_params, type_params, impl_trait_params) =
 563             def_generics.map_or((0, 0, 0, 0), |g| g.provenance_split());
 564         let total_len = parent_params + self_params + type_params + impl_trait_params;
 565
 566         substs.extend(iter::repeat(TyKind::Unknown.intern(&Interner)).take(parent_params));
 567
 568         let mut had_explicit_type_args = false;
 569
 570         if let Some(generic_args) = &segment.args_and_bindings {
 571             if !generic_args.has_self_type {
 572                 substs.extend(iter::repeat(TyKind::Unknown.intern(&Interner)).take(self_params));
 573             }
 574             let expected_num =
 575                 if generic_args.has_self_type { self_params + type_params } else { type_params };
 576             let skip = if generic_args.has_self_type && self_params == 0 { 1 } else { 0 };
 577             // if args are provided, it should be all of them, but we can't rely on that
 578             for arg in generic_args
 579                 .args
 580                 .iter()
 581                 .filter(|arg| matches!(arg, GenericArg::Type(_)))
 582                 .skip(skip)
 583                 .take(expected_num)
 584             {
 585                 match arg {
 586                     GenericArg::Type(type_ref) => {
 587                         had_explicit_type_args = true;
 588                         let ty = self.lower_ty(type_ref);
 589                         substs.push(ty);
 590                     }
 591                     GenericArg::Lifetime(_) => {}
 592                 }
 593             }
 594         }
 595
 596         // handle defaults. In expression or pattern path segments without
 597         // explicitly specified type arguments, missing type arguments are inferred
 598         // (i.e. defaults aren't used).
 599         if !infer_args || had_explicit_type_args {
 600             if let Some(def_generic) = def_generic {
 601                 let defaults = self.db.generic_defaults(def_generic);
 602                 assert_eq!(total_len, defaults.len());
 603
 604                 for default_ty in defaults.iter().skip(substs.len()) {
 605                     // each default can depend on the previous parameters
 606                     let substs_so_far = Substitution(substs.clone().into());
 607                     substs.push(default_ty.clone().subst(&substs_so_far));
 608                 }
 609             }
 610         }
 611
 612         // add placeholders for args that were not provided
 613         // FIXME: emit diagnostics in contexts where this is not allowed
 614         for _ in substs.len()..total_len {
 615             substs.push(TyKind::Unknown.intern(&Interner));
 616         }
 617         assert_eq!(substs.len(), total_len);
 618
 619         Substitution(substs.into())
 620     }
 621
 622     fn lower_trait_ref_from_path(
 623         &self,
 624         path: &Path,
 625         explicit_self_ty: Option<Ty>,
 626     ) -> Option<TraitRef> {
 627         let resolved =
 628             match self.resolver.resolve_path_in_type_ns_fully(self.db.upcast(), path.mod_path())? {
 629                 TypeNs::TraitId(tr) => tr,
 630                 _ => return None,
 631             };
 632         let segment = path.segments().last().expect("path should have at least one segment");
 633         Some(self.lower_trait_ref_from_resolved_path(resolved, segment, explicit_self_ty))
 634     }
 635
 636     pub(crate) fn lower_trait_ref_from_resolved_path(
 637         &self,
 638         resolved: TraitId,
 639         segment: PathSegment<'_>,
 640         explicit_self_ty: Option<Ty>,
 641     ) -> TraitRef {
 642         let mut substs = self.trait_ref_substs_from_path(segment, resolved);
 643         if let Some(self_ty) = explicit_self_ty {
 644             substs.0[0] = self_ty;
 645         }
 646         TraitRef { trait_id: to_chalk_trait_id(resolved), substitution: substs }
 647     }
 648
 649     fn lower_trait_ref(
 650         &self,
 651         type_ref: &TypeRef,
 652         explicit_self_ty: Option<Ty>,
 653     ) -> Option<TraitRef> {
 654         let path = match type_ref {
 655             TypeRef::Path(path) => path,
 656             _ => return None,
 657         };
 658         self.lower_trait_ref_from_path(path, explicit_self_ty)
 659     }
 660
 661     fn trait_ref_substs_from_path(
 662         &self,
 663         segment: PathSegment<'_>,
 664         resolved: TraitId,
 665     ) -> Substitution {
 666         self.substs_from_path_segment(segment, Some(resolved.into()), false)
 667     }
 668
 669     pub(crate) fn lower_where_predicate(
 670         &'a self,
 671         where_predicate: &'a WherePredicate,
 672         ignore_bindings: bool,
 673     ) -> impl Iterator<Item = WhereClause> + 'a {
 674         match where_predicate {
 675             WherePredicate::ForLifetime { target, bound, .. }
 676             | WherePredicate::TypeBound { target, bound } => {
 677                 let self_ty = match target {
 678                     WherePredicateTypeTarget::TypeRef(type_ref) => self.lower_ty(type_ref),
 679                     WherePredicateTypeTarget::TypeParam(param_id) => {
 680                         let generic_def = self.resolver.generic_def().expect("generics in scope");
 681                         let generics = generics(self.db.upcast(), generic_def);
 682                         let param_id =
 683                             hir_def::TypeParamId { parent: generic_def, local_id: *param_id };
 684                         let placeholder = to_placeholder_idx(self.db, param_id);
 685                         match self.type_param_mode {
 686                             TypeParamLoweringMode::Placeholder => TyKind::Placeholder(placeholder),
 687                             TypeParamLoweringMode::Variable => {
 688                                 let idx = generics.param_idx(param_id).expect("matching generics");
 689                                 TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, idx))
 690                             }
 691                         }
 692                         .intern(&Interner)
 693                     }
 694                 };
 695                 self.lower_type_bound(bound, self_ty, ignore_bindings)
 696                     .collect::<Vec<_>>()
 697                     .into_iter()
 698             }
 699             WherePredicate::Lifetime { .. } => vec![].into_iter(),
 700         }
 701     }
 702
 703     pub(crate) fn lower_type_bound(
 704         &'a self,
 705         bound: &'a TypeBound,
 706         self_ty: Ty,
 707         ignore_bindings: bool,
 708     ) -> impl Iterator<Item = WhereClause> + 'a {
 709         let mut bindings = None;
 710         let trait_ref = match bound {
 711             TypeBound::Path(path) => {
 712                 bindings = self.lower_trait_ref_from_path(path, Some(self_ty));
 713                 bindings.clone().map(WhereClause::Implemented)
 714             }
 715             TypeBound::Lifetime(_) => None,
 716             TypeBound::Error => None,
 717         };
 718         trait_ref.into_iter().chain(
 719             bindings
 720                 .into_iter()
 721                 .filter(move |_| !ignore_bindings)
 722                 .flat_map(move |tr| self.assoc_type_bindings_from_type_bound(bound, tr)),
 723         )
 724     }
 725
 726     fn assoc_type_bindings_from_type_bound(
 727         &'a self,
 728         bound: &'a TypeBound,
 729         trait_ref: TraitRef,
 730     ) -> impl Iterator<Item = WhereClause> + 'a {
 731         let last_segment = match bound {
 732             TypeBound::Path(path) => path.segments().last(),
 733             TypeBound::Error | TypeBound::Lifetime(_) => None,
 734         };
 735         last_segment
 736             .into_iter()
 737             .flat_map(|segment| segment.args_and_bindings.into_iter())
 738             .flat_map(|args_and_bindings| args_and_bindings.bindings.iter())
 739             .flat_map(move |binding| {
 740                 let found = associated_type_by_name_including_super_traits(
 741                     self.db,
 742                     trait_ref.clone(),
 743                     &binding.name,
 744                 );
 745                 let (super_trait_ref, associated_ty) = match found {
 746                     None => return SmallVec::<[WhereClause; 1]>::new(),
 747                     Some(t) => t,
 748                 };
 749                 let projection_ty = ProjectionTy {
 750                     associated_ty_id: to_assoc_type_id(associated_ty),
 751                     substitution: super_trait_ref.substitution,
 752                 };
 753                 let mut preds = SmallVec::with_capacity(
 754                     binding.type_ref.as_ref().map_or(0, |_| 1) + binding.bounds.len(),
 755                 );
 756                 if let Some(type_ref) = &binding.type_ref {
 757                     let ty = self.lower_ty(type_ref);
 758                     let alias_eq =
 759                         AliasEq { alias: AliasTy::Projection(projection_ty.clone()), ty };
 760                     preds.push(WhereClause::AliasEq(alias_eq));
 761                 }
 762                 for bound in &binding.bounds {
 763                     preds.extend(self.lower_type_bound(
 764                         bound,
 765                         TyKind::Alias(AliasTy::Projection(projection_ty.clone())).intern(&Interner),
 766                         false,
 767                     ));
 768                 }
 769                 preds
 770             })
 771     }
 772
 773     fn lower_impl_trait(&self, bounds: &[TypeBound]) -> ReturnTypeImplTrait {
 774         cov_mark::hit!(lower_rpit);
 775         let self_ty =
 776             TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(&Interner);
 777         let predicates = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
 778             bounds.iter().flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false)).collect()
 779         });
 780         ReturnTypeImplTrait { bounds: Binders::new(1, predicates) }
 781     }
 782 }
 783
 784 fn count_impl_traits(type_ref: &TypeRef) -> usize {
 785     let mut count = 0;
 786     type_ref.walk(&mut |type_ref| {
 787         if matches!(type_ref, TypeRef::ImplTrait(_)) {
 788             count += 1;
 789         }
 790     });
 791     count
 792 }
 793
 794 /// Build the signature of a callable item (function, struct or enum variant).
 795 pub fn callable_item_sig(db: &dyn HirDatabase, def: CallableDefId) -> PolyFnSig {
 796     match def {
 797         CallableDefId::FunctionId(f) => fn_sig_for_fn(db, f),
 798         CallableDefId::StructId(s) => fn_sig_for_struct_constructor(db, s),
 799         CallableDefId::EnumVariantId(e) => fn_sig_for_enum_variant_constructor(db, e),
 800     }
 801 }
 802
 803 pub fn associated_type_shorthand_candidates<R>(
 804     db: &dyn HirDatabase,
 805     res: TypeNs,
 806     mut cb: impl FnMut(&Name, &TraitRef, TypeAliasId) -> Option<R>,
 807 ) -> Option<R> {
 808     let traits_from_env: Vec<_> = match res {
 809         TypeNs::SelfType(impl_id) => match db.impl_trait(impl_id) {
 810             None => vec![],
 811             Some(trait_ref) => vec![trait_ref.value],
 812         },
 813         TypeNs::GenericParam(param_id) => {
 814             let predicates = db.generic_predicates_for_param(param_id);
 815             let mut traits_: Vec<_> = predicates
 816                 .iter()
 817                 .filter_map(|pred| match &pred.value {
 818                     WhereClause::Implemented(tr) => Some(tr.clone()),
 819                     _ => None,
 820                 })
 821                 .collect();
 822             // Handle `Self::Type` referring to own associated type in trait definitions
 823             if let GenericDefId::TraitId(trait_id) = param_id.parent {
 824                 let generics = generics(db.upcast(), trait_id.into());
 825                 if generics.params.types[param_id.local_id].provenance
 826                     == TypeParamProvenance::TraitSelf
 827                 {
 828                     let trait_ref = TraitRef {
 829                         trait_id: to_chalk_trait_id(trait_id),
 830                         substitution: Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST),
 831                     };
 832                     traits_.push(trait_ref);
 833                 }
 834             }
 835             traits_
 836         }
 837         _ => vec![],
 838     };
 839
 840     for t in traits_from_env.into_iter().flat_map(move |t| all_super_trait_refs(db, t)) {
 841         let data = db.trait_data(t.hir_trait_id());
 842
 843         for (name, assoc_id) in &data.items {
 844             match assoc_id {
 845                 AssocItemId::TypeAliasId(alias) => {
 846                     if let Some(result) = cb(name, &t, *alias) {
 847                         return Some(result);
 848                     }
 849                 }
 850                 AssocItemId::FunctionId(_) | AssocItemId::ConstId(_) => {}
 851             }
 852         }
 853     }
 854
 855     None
 856 }
 857
 858 /// Build the type of all specific fields of a struct or enum variant.
 859 pub(crate) fn field_types_query(
 860     db: &dyn HirDatabase,
 861     variant_id: VariantId,
 862 ) -> Arc<ArenaMap<LocalFieldId, Binders<Ty>>> {
 863     let var_data = variant_data(db.upcast(), variant_id);
 864     let (resolver, def): (_, GenericDefId) = match variant_id {
 865         VariantId::StructId(it) => (it.resolver(db.upcast()), it.into()),
 866         VariantId::UnionId(it) => (it.resolver(db.upcast()), it.into()),
 867         VariantId::EnumVariantId(it) => (it.parent.resolver(db.upcast()), it.parent.into()),
 868     };
 869     let generics = generics(db.upcast(), def);
 870     let mut res = ArenaMap::default();
 871     let ctx =
 872         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
 873     for (field_id, field_data) in var_data.fields().iter() {
 874         res.insert(field_id, Binders::new(generics.len(), ctx.lower_ty(&field_data.type_ref)))
 875     }
 876     Arc::new(res)
 877 }
 878
 879 /// This query exists only to be used when resolving short-hand associated types
 880 /// like `T::Item`.
 881 ///
 882 /// See the analogous query in rustc and its comment:
 883 /// https://github.com/rust-lang/rust/blob/9150f844e2624eb013ec78ca08c1d416e6644026/src/librustc_typeck/astconv.rs#L46
 884 /// This is a query mostly to handle cycles somewhat gracefully; e.g. the
 885 /// following bounds are disallowed: `T: Foo<U::Item>, U: Foo<T::Item>`, but
 886 /// these are fine: `T: Foo<U::Item>, U: Foo<()>`.
 887 pub(crate) fn generic_predicates_for_param_query(
 888     db: &dyn HirDatabase,
 889     param_id: TypeParamId,
 890 ) -> Arc<[Binders<WhereClause>]> {
 891     let resolver = param_id.parent.resolver(db.upcast());
 892     let ctx =
 893         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
 894     let generics = generics(db.upcast(), param_id.parent);
 895     resolver
 896         .where_predicates_in_scope()
 897         // we have to filter out all other predicates *first*, before attempting to lower them
 898         .filter(|pred| match pred {
 899             WherePredicate::ForLifetime { target, .. }
 900             | WherePredicate::TypeBound { target, .. } => match target {
 901                 WherePredicateTypeTarget::TypeRef(type_ref) => {
 902                     ctx.lower_ty_only_param(type_ref) == Some(param_id)
 903                 }
 904                 WherePredicateTypeTarget::TypeParam(local_id) => *local_id == param_id.local_id,
 905             },
 906             WherePredicate::Lifetime { .. } => false,
 907         })
 908         .flat_map(|pred| {
 909             ctx.lower_where_predicate(pred, true).map(|p| Binders::new(generics.len(), p))
 910         })
 911         .collect()
 912 }
 913
 914 pub(crate) fn generic_predicates_for_param_recover(
 915     _db: &dyn HirDatabase,
 916     _cycle: &[String],
 917     _param_id: &TypeParamId,
 918 ) -> Arc<[Binders<WhereClause>]> {
 919     Arc::new([])
 920 }
 921
 922 pub(crate) fn trait_environment_query(
 923     db: &dyn HirDatabase,
 924     def: GenericDefId,
 925 ) -> Arc<TraitEnvironment> {
 926     let resolver = def.resolver(db.upcast());
 927     let ctx = TyLoweringContext::new(db, &resolver)
 928         .with_type_param_mode(TypeParamLoweringMode::Placeholder);
 929     let mut traits_in_scope = Vec::new();
 930     let mut clauses = Vec::new();
 931     for pred in resolver.where_predicates_in_scope() {
 932         for pred in ctx.lower_where_predicate(pred, false) {
 933             if let WhereClause::Implemented(tr) = &pred {
 934                 traits_in_scope.push((tr.self_type_parameter().clone(), tr.hir_trait_id()));
 935             }
 936             let program_clause: chalk_ir::ProgramClause<Interner> =
 937                 pred.clone().to_chalk(db).cast(&Interner);
 938             clauses.push(program_clause.into_from_env_clause(&Interner));
 939         }
 940     }
 941
 942     let container: Option<AssocContainerId> = match def {
 943         // FIXME: is there a function for this?
 944         GenericDefId::FunctionId(f) => Some(f.lookup(db.upcast()).container),
 945         GenericDefId::AdtId(_) => None,
 946         GenericDefId::TraitId(_) => None,
 947         GenericDefId::TypeAliasId(t) => Some(t.lookup(db.upcast()).container),
 948         GenericDefId::ImplId(_) => None,
 949         GenericDefId::EnumVariantId(_) => None,
 950         GenericDefId::ConstId(c) => Some(c.lookup(db.upcast()).container),
 951     };
 952     if let Some(AssocContainerId::TraitId(trait_id)) = container {
 953         // add `Self: Trait<T1, T2, ...>` to the environment in trait
 954         // function default implementations (and hypothetical code
 955         // inside consts or type aliases)
 956         cov_mark::hit!(trait_self_implements_self);
 957         let substs = Substitution::type_params(db, trait_id);
 958         let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution: substs };
 959         let pred = WhereClause::Implemented(trait_ref);
 960         let program_clause: chalk_ir::ProgramClause<Interner> = pred.to_chalk(db).cast(&Interner);
 961         clauses.push(program_clause.into_from_env_clause(&Interner));
 962     }
 963
 964     let env = chalk_ir::Environment::new(&Interner).add_clauses(&Interner, clauses);
 965
 966     Arc::new(TraitEnvironment { traits_from_clauses: traits_in_scope, env })
 967 }
 968
 969 /// Resolve the where clause(s) of an item with generics.
 970 pub(crate) fn generic_predicates_query(
 971     db: &dyn HirDatabase,
 972     def: GenericDefId,
 973 ) -> Arc<[Binders<WhereClause>]> {
 974     let resolver = def.resolver(db.upcast());
 975     let ctx =
 976         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
 977     let generics = generics(db.upcast(), def);
 978     resolver
 979         .where_predicates_in_scope()
 980         .flat_map(|pred| {
 981             ctx.lower_where_predicate(pred, false).map(|p| Binders::new(generics.len(), p))
 982         })
 983         .collect()
 984 }
 985
 986 /// Resolve the default type params from generics
 987 pub(crate) fn generic_defaults_query(
 988     db: &dyn HirDatabase,
 989     def: GenericDefId,
 990 ) -> Arc<[Binders<Ty>]> {
 991     let resolver = def.resolver(db.upcast());
 992     let ctx =
 993         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
 994     let generic_params = generics(db.upcast(), def);
 995
 996     let defaults = generic_params
 997         .iter()
 998         .enumerate()
 999         .map(|(idx, (_, p))| {
1000             let mut ty =
1001                 p.default.as_ref().map_or(TyKind::Unknown.intern(&Interner), |t| ctx.lower_ty(t));
1002
1003             // Each default can only refer to previous parameters.
1004             ty.walk_mut_binders(
1005                 &mut |ty, binders| match ty.interned_mut() {
1006                     TyKind::BoundVar(BoundVar { debruijn, index }) if *debruijn == binders => {
1007                         if *index >= idx {
1008                             // type variable default referring to parameter coming
1009                             // after it. This is forbidden (FIXME: report
1010                             // diagnostic)
1011                             *ty = TyKind::Unknown.intern(&Interner);
1012                         }
1013                     }
1014                     _ => {}
1015                 },
1016                 DebruijnIndex::INNERMOST,
1017             );
1018
1019             Binders::new(idx, ty)
1020         })
1021         .collect();
1022
1023     defaults
1024 }
1025
1026 fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
1027     let data = db.function_data(def);
1028     let resolver = def.resolver(db.upcast());
1029     let ctx_params = TyLoweringContext::new(db, &resolver)
1030         .with_impl_trait_mode(ImplTraitLoweringMode::Variable)
1031         .with_type_param_mode(TypeParamLoweringMode::Variable);
1032     let params = data.params.iter().map(|tr| (&ctx_params).lower_ty(tr)).collect::<Vec<_>>();
1033     let ctx_ret = TyLoweringContext::new(db, &resolver)
1034         .with_impl_trait_mode(ImplTraitLoweringMode::Opaque)
1035         .with_type_param_mode(TypeParamLoweringMode::Variable);
1036     let ret = (&ctx_ret).lower_ty(&data.ret_type);
1037     let generics = generics(db.upcast(), def.into());
1038     let num_binders = generics.len();
1039     Binders::new(num_binders, CallableSig::from_params_and_return(params, ret, data.is_varargs))
1040 }
1041
1042 /// Build the declared type of a function. This should not need to look at the
1043 /// function body.
1044 fn type_for_fn(db: &dyn HirDatabase, def: FunctionId) -> Binders<Ty> {
1045     let generics = generics(db.upcast(), def.into());
1046     let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
1047     Binders::new(
1048         substs.len(),
1049         TyKind::FnDef(CallableDefId::FunctionId(def).to_chalk(db), substs).intern(&Interner),
1050     )
1051 }
1052
1053 /// Build the declared type of a const.
1054 fn type_for_const(db: &dyn HirDatabase, def: ConstId) -> Binders<Ty> {
1055     let data = db.const_data(def);
1056     let generics = generics(db.upcast(), def.into());
1057     let resolver = def.resolver(db.upcast());
1058     let ctx =
1059         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1060
1061     Binders::new(generics.len(), ctx.lower_ty(&data.type_ref))
1062 }
1063
1064 /// Build the declared type of a static.
1065 fn type_for_static(db: &dyn HirDatabase, def: StaticId) -> Binders<Ty> {
1066     let data = db.static_data(def);
1067     let resolver = def.resolver(db.upcast());
1068     let ctx = TyLoweringContext::new(db, &resolver);
1069
1070     Binders::new(0, ctx.lower_ty(&data.type_ref))
1071 }
1072
1073 fn fn_sig_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> PolyFnSig {
1074     let struct_data = db.struct_data(def);
1075     let fields = struct_data.variant_data.fields();
1076     let resolver = def.resolver(db.upcast());
1077     let ctx =
1078         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1079     let params = fields.iter().map(|(_, field)| ctx.lower_ty(&field.type_ref)).collect::<Vec<_>>();
1080     let ret = type_for_adt(db, def.into());
1081     Binders::new(ret.num_binders, CallableSig::from_params_and_return(params, ret.value, false))
1082 }
1083
1084 /// Build the type of a tuple struct constructor.
1085 fn type_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> Binders<Ty> {
1086     let struct_data = db.struct_data(def);
1087     if let StructKind::Unit = struct_data.variant_data.kind() {
1088         return type_for_adt(db, def.into());
1089     }
1090     let generics = generics(db.upcast(), def.into());
1091     let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
1092     Binders::new(
1093         substs.len(),
1094         TyKind::FnDef(CallableDefId::StructId(def).to_chalk(db), substs).intern(&Interner),
1095     )
1096 }
1097
1098 fn fn_sig_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -> PolyFnSig {
1099     let enum_data = db.enum_data(def.parent);
1100     let var_data = &enum_data.variants[def.local_id];
1101     let fields = var_data.variant_data.fields();
1102     let resolver = def.parent.resolver(db.upcast());
1103     let ctx =
1104         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1105     let params = fields.iter().map(|(_, field)| ctx.lower_ty(&field.type_ref)).collect::<Vec<_>>();
1106     let ret = type_for_adt(db, def.parent.into());
1107     Binders::new(ret.num_binders, CallableSig::from_params_and_return(params, ret.value, false))
1108 }
1109
1110 /// Build the type of a tuple enum variant constructor.
1111 fn type_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -> Binders<Ty> {
1112     let enum_data = db.enum_data(def.parent);
1113     let var_data = &enum_data.variants[def.local_id].variant_data;
1114     if let StructKind::Unit = var_data.kind() {
1115         return type_for_adt(db, def.parent.into());
1116     }
1117     let generics = generics(db.upcast(), def.parent.into());
1118     let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
1119     Binders::new(
1120         substs.len(),
1121         TyKind::FnDef(CallableDefId::EnumVariantId(def).to_chalk(db), substs).intern(&Interner),
1122     )
1123 }
1124
1125 fn type_for_adt(db: &dyn HirDatabase, adt: AdtId) -> Binders<Ty> {
1126     let generics = generics(db.upcast(), adt.into());
1127     let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
1128     Binders::new(substs.len(), Ty::adt_ty(adt, substs))
1129 }
1130
1131 fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders<Ty> {
1132     let generics = generics(db.upcast(), t.into());
1133     let resolver = t.resolver(db.upcast());
1134     let ctx =
1135         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1136     if db.type_alias_data(t).is_extern {
1137         Binders::new(0, TyKind::ForeignType(crate::to_foreign_def_id(t)).intern(&Interner))
1138     } else {
1139         let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
1140         let type_ref = &db.type_alias_data(t).type_ref;
1141         let inner = ctx.lower_ty(type_ref.as_ref().unwrap_or(&TypeRef::Error));
1142         Binders::new(substs.len(), inner)
1143     }
1144 }
1145
1146 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
1147 pub enum CallableDefId {
1148     FunctionId(FunctionId),
1149     StructId(StructId),
1150     EnumVariantId(EnumVariantId),
1151 }
1152 impl_from!(FunctionId, StructId, EnumVariantId for CallableDefId);
1153
1154 impl CallableDefId {
1155     pub fn krate(self, db: &dyn HirDatabase) -> CrateId {
1156         let db = db.upcast();
1157         match self {
1158             CallableDefId::FunctionId(f) => f.lookup(db).module(db),
1159             CallableDefId::StructId(s) => s.lookup(db).container,
1160             CallableDefId::EnumVariantId(e) => e.parent.lookup(db).container,
1161         }
1162         .krate()
1163     }
1164 }
1165
1166 impl From<CallableDefId> for GenericDefId {
1167     fn from(def: CallableDefId) -> GenericDefId {
1168         match def {
1169             CallableDefId::FunctionId(f) => f.into(),
1170             CallableDefId::StructId(s) => s.into(),
1171             CallableDefId::EnumVariantId(e) => e.into(),
1172         }
1173     }
1174 }
1175
1176 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1177 pub enum TyDefId {
1178     BuiltinType(BuiltinType),
1179     AdtId(AdtId),
1180     TypeAliasId(TypeAliasId),
1181 }
1182 impl_from!(BuiltinType, AdtId(StructId, EnumId, UnionId), TypeAliasId for TyDefId);
1183
1184 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1185 pub enum ValueTyDefId {
1186     FunctionId(FunctionId),
1187     StructId(StructId),
1188     UnionId(UnionId),
1189     EnumVariantId(EnumVariantId),
1190     ConstId(ConstId),
1191     StaticId(StaticId),
1192 }
1193 impl_from!(FunctionId, StructId, UnionId, EnumVariantId, ConstId, StaticId for ValueTyDefId);
1194
1195 /// Build the declared type of an item. This depends on the namespace; e.g. for
1196 /// `struct Foo(usize)`, we have two types: The type of the struct itself, and
1197 /// the constructor function `(usize) -> Foo` which lives in the values
1198 /// namespace.
1199 pub(crate) fn ty_query(db: &dyn HirDatabase, def: TyDefId) -> Binders<Ty> {
1200     match def {
1201         TyDefId::BuiltinType(it) => Binders::new(0, Ty::builtin(it)),
1202         TyDefId::AdtId(it) => type_for_adt(db, it),
1203         TyDefId::TypeAliasId(it) => type_for_type_alias(db, it),
1204     }
1205 }
1206
1207 pub(crate) fn ty_recover(db: &dyn HirDatabase, _cycle: &[String], def: &TyDefId) -> Binders<Ty> {
1208     let num_binders = match *def {
1209         TyDefId::BuiltinType(_) => 0,
1210         TyDefId::AdtId(it) => generics(db.upcast(), it.into()).len(),
1211         TyDefId::TypeAliasId(it) => generics(db.upcast(), it.into()).len(),
1212     };
1213     Binders::new(num_binders, TyKind::Unknown.intern(&Interner))
1214 }
1215
1216 pub(crate) fn value_ty_query(db: &dyn HirDatabase, def: ValueTyDefId) -> Binders<Ty> {
1217     match def {
1218         ValueTyDefId::FunctionId(it) => type_for_fn(db, it),
1219         ValueTyDefId::StructId(it) => type_for_struct_constructor(db, it),
1220         ValueTyDefId::UnionId(it) => type_for_adt(db, it.into()),
1221         ValueTyDefId::EnumVariantId(it) => type_for_enum_variant_constructor(db, it),
1222         ValueTyDefId::ConstId(it) => type_for_const(db, it),
1223         ValueTyDefId::StaticId(it) => type_for_static(db, it),
1224     }
1225 }
1226
1227 pub(crate) fn impl_self_ty_query(db: &dyn HirDatabase, impl_id: ImplId) -> Binders<Ty> {
1228     let impl_data = db.impl_data(impl_id);
1229     let resolver = impl_id.resolver(db.upcast());
1230     let generics = generics(db.upcast(), impl_id.into());
1231     let ctx =
1232         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1233     Binders::new(generics.len(), ctx.lower_ty(&impl_data.target_type))
1234 }
1235
1236 pub(crate) fn const_param_ty_query(db: &dyn HirDatabase, def: ConstParamId) -> Ty {
1237     let parent_data = db.generic_params(def.parent);
1238     let data = &parent_data.consts[def.local_id];
1239     let resolver = def.parent.resolver(db.upcast());
1240     let ctx = TyLoweringContext::new(db, &resolver);
1241
1242     ctx.lower_ty(&data.ty)
1243 }
1244
1245 pub(crate) fn impl_self_ty_recover(
1246     db: &dyn HirDatabase,
1247     _cycle: &[String],
1248     impl_id: &ImplId,
1249 ) -> Binders<Ty> {
1250     let generics = generics(db.upcast(), (*impl_id).into());
1251     Binders::new(generics.len(), TyKind::Unknown.intern(&Interner))
1252 }
1253
1254 pub(crate) fn impl_trait_query(db: &dyn HirDatabase, impl_id: ImplId) -> Option<Binders<TraitRef>> {
1255     let impl_data = db.impl_data(impl_id);
1256     let resolver = impl_id.resolver(db.upcast());
1257     let ctx =
1258         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1259     let self_ty = db.impl_self_ty(impl_id);
1260     let target_trait = impl_data.target_trait.as_ref()?;
1261     Some(Binders::new(self_ty.num_binders, ctx.lower_trait_ref(target_trait, Some(self_ty.value))?))
1262 }
1263
1264 pub(crate) fn return_type_impl_traits(
1265     db: &dyn HirDatabase,
1266     def: hir_def::FunctionId,
1267 ) -> Option<Arc<Binders<ReturnTypeImplTraits>>> {
1268     // FIXME unify with fn_sig_for_fn instead of doing lowering twice, maybe
1269     let data = db.function_data(def);
1270     let resolver = def.resolver(db.upcast());
1271     let ctx_ret = TyLoweringContext::new(db, &resolver)
1272         .with_impl_trait_mode(ImplTraitLoweringMode::Opaque)
1273         .with_type_param_mode(TypeParamLoweringMode::Variable);
1274     let _ret = (&ctx_ret).lower_ty(&data.ret_type);
1275     let generics = generics(db.upcast(), def.into());
1276     let num_binders = generics.len();
1277     let return_type_impl_traits =
1278         ReturnTypeImplTraits { impl_traits: ctx_ret.opaque_type_data.into_inner() };
1279     if return_type_impl_traits.impl_traits.is_empty() {
1280         None
1281     } else {
1282         Some(Arc::new(Binders::new(num_binders, return_type_impl_traits)))
1283     }
1284 }
1285
1286 pub(crate) fn lower_to_chalk_mutability(m: hir_def::type_ref::Mutability) -> Mutability {
1287     match m {
1288         hir_def::type_ref::Mutability::Shared => Mutability::Not,
1289         hir_def::type_ref::Mutability::Mut => Mutability::Mut,
1290     }
1291 }