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