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