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