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, WherePredicateTarget},
  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_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_args = true;
 572                     let ty = Ty::from_hir(ctx, type_ref);
 573                     substs.push(ty);
 574                 }
 575             }
 576         }
 577     }
 578
 579     // handle defaults. In expression or pattern path segments without
 580     // explicitly specified type arguments, missing type arguments are inferred
 581     // (i.e. defaults aren't used).
 582     if !infer_args || had_explicit_args {
 583         if let Some(def_generic) = def_generic {
 584             let defaults = ctx.db.generic_defaults(def_generic);
 585             assert_eq!(total_len, defaults.len());
 586
 587             for default_ty in defaults.iter().skip(substs.len()) {
 588                 // each default can depend on the previous parameters
 589                 let substs_so_far = Substs(substs.clone().into());
 590                 substs.push(default_ty.clone().subst(&substs_so_far));
 591             }
 592         }
 593     }
 594
 595     // add placeholders for args that were not provided
 596     // FIXME: emit diagnostics in contexts where this is not allowed
 597     for _ in substs.len()..total_len {
 598         substs.push(Ty::Unknown);
 599     }
 600     assert_eq!(substs.len(), total_len);
 601
 602     Substs(substs.into())
 603 }
 604
 605 impl TraitRef {
 606     fn from_path(
 607         ctx: &TyLoweringContext<'_>,
 608         path: &Path,
 609         explicit_self_ty: Option<Ty>,
 610     ) -> Option<Self> {
 611         let resolved =
 612             match ctx.resolver.resolve_path_in_type_ns_fully(ctx.db.upcast(), path.mod_path())? {
 613                 TypeNs::TraitId(tr) => tr,
 614                 _ => return None,
 615             };
 616         let segment = path.segments().last().expect("path should have at least one segment");
 617         Some(TraitRef::from_resolved_path(ctx, resolved, segment, explicit_self_ty))
 618     }
 619
 620     pub(crate) fn from_resolved_path(
 621         ctx: &TyLoweringContext<'_>,
 622         resolved: TraitId,
 623         segment: PathSegment<'_>,
 624         explicit_self_ty: Option<Ty>,
 625     ) -> Self {
 626         let mut substs = TraitRef::substs_from_path(ctx, segment, resolved);
 627         if let Some(self_ty) = explicit_self_ty {
 628             make_mut_slice(&mut substs.0)[0] = self_ty;
 629         }
 630         TraitRef { trait_: resolved, substs }
 631     }
 632
 633     fn from_hir(
 634         ctx: &TyLoweringContext<'_>,
 635         type_ref: &TypeRef,
 636         explicit_self_ty: Option<Ty>,
 637     ) -> Option<Self> {
 638         let path = match type_ref {
 639             TypeRef::Path(path) => path,
 640             _ => return None,
 641         };
 642         TraitRef::from_path(ctx, path, explicit_self_ty)
 643     }
 644
 645     fn substs_from_path(
 646         ctx: &TyLoweringContext<'_>,
 647         segment: PathSegment<'_>,
 648         resolved: TraitId,
 649     ) -> Substs {
 650         substs_from_path_segment(ctx, segment, Some(resolved.into()), false)
 651     }
 652
 653     pub(crate) fn from_type_bound(
 654         ctx: &TyLoweringContext<'_>,
 655         bound: &TypeBound,
 656         self_ty: Ty,
 657     ) -> Option<TraitRef> {
 658         match bound {
 659             TypeBound::Path(path) => TraitRef::from_path(ctx, path, Some(self_ty)),
 660             TypeBound::Error => None,
 661         }
 662     }
 663 }
 664
 665 impl GenericPredicate {
 666     pub(crate) fn from_where_predicate<'a>(
 667         ctx: &'a TyLoweringContext<'a>,
 668         where_predicate: &'a WherePredicate,
 669     ) -> impl Iterator<Item = GenericPredicate> + 'a {
 670         let self_ty = match &where_predicate.target {
 671             WherePredicateTarget::TypeRef(type_ref) => Ty::from_hir(ctx, type_ref),
 672             WherePredicateTarget::TypeParam(param_id) => {
 673                 let generic_def = ctx.resolver.generic_def().expect("generics in scope");
 674                 let generics = generics(ctx.db.upcast(), generic_def);
 675                 let param_id = hir_def::TypeParamId { parent: generic_def, local_id: *param_id };
 676                 match ctx.type_param_mode {
 677                     TypeParamLoweringMode::Placeholder => Ty::Placeholder(param_id),
 678                     TypeParamLoweringMode::Variable => {
 679                         let idx = generics.param_idx(param_id).expect("matching generics");
 680                         Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, idx))
 681                     }
 682                 }
 683             }
 684         };
 685         GenericPredicate::from_type_bound(ctx, &where_predicate.bound, self_ty)
 686     }
 687
 688     pub(crate) fn from_type_bound<'a>(
 689         ctx: &'a TyLoweringContext<'a>,
 690         bound: &'a TypeBound,
 691         self_ty: Ty,
 692     ) -> impl Iterator<Item = GenericPredicate> + 'a {
 693         let trait_ref = TraitRef::from_type_bound(ctx, bound, self_ty);
 694         iter::once(trait_ref.clone().map_or(GenericPredicate::Error, GenericPredicate::Implemented))
 695             .chain(
 696                 trait_ref
 697                     .into_iter()
 698                     .flat_map(move |tr| assoc_type_bindings_from_type_bound(ctx, bound, tr)),
 699             )
 700     }
 701 }
 702
 703 fn assoc_type_bindings_from_type_bound<'a>(
 704     ctx: &'a TyLoweringContext<'a>,
 705     bound: &'a TypeBound,
 706     trait_ref: TraitRef,
 707 ) -> impl Iterator<Item = GenericPredicate> + 'a {
 708     let last_segment = match bound {
 709         TypeBound::Path(path) => path.segments().last(),
 710         TypeBound::Error => None,
 711     };
 712     last_segment
 713         .into_iter()
 714         .flat_map(|segment| segment.args_and_bindings.into_iter())
 715         .flat_map(|args_and_bindings| args_and_bindings.bindings.iter())
 716         .flat_map(move |binding| {
 717             let found = associated_type_by_name_including_super_traits(
 718                 ctx.db,
 719                 trait_ref.clone(),
 720                 &binding.name,
 721             );
 722             let (super_trait_ref, associated_ty) = match found {
 723                 None => return SmallVec::<[GenericPredicate; 1]>::new(),
 724                 Some(t) => t,
 725             };
 726             let projection_ty = ProjectionTy { associated_ty, parameters: super_trait_ref.substs };
 727             let mut preds = SmallVec::with_capacity(
 728                 binding.type_ref.as_ref().map_or(0, |_| 1) + binding.bounds.len(),
 729             );
 730             if let Some(type_ref) = &binding.type_ref {
 731                 let ty = Ty::from_hir(ctx, type_ref);
 732                 let projection_predicate =
 733                     ProjectionPredicate { projection_ty: projection_ty.clone(), ty };
 734                 preds.push(GenericPredicate::Projection(projection_predicate));
 735             }
 736             for bound in &binding.bounds {
 737                 preds.extend(GenericPredicate::from_type_bound(
 738                     ctx,
 739                     bound,
 740                     Ty::Projection(projection_ty.clone()),
 741                 ));
 742             }
 743             preds
 744         })
 745 }
 746
 747 impl ReturnTypeImplTrait {
 748     fn from_hir(ctx: &TyLoweringContext, bounds: &[TypeBound]) -> Self {
 749         mark::hit!(lower_rpit);
 750         let self_ty = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0));
 751         let predicates = ctx.with_shifted_in(DebruijnIndex::ONE, |ctx| {
 752             bounds
 753                 .iter()
 754                 .flat_map(|b| GenericPredicate::from_type_bound(ctx, b, self_ty.clone()))
 755                 .collect()
 756         });
 757         ReturnTypeImplTrait { bounds: Binders::new(1, predicates) }
 758     }
 759 }
 760
 761 fn count_impl_traits(type_ref: &TypeRef) -> usize {
 762     let mut count = 0;
 763     type_ref.walk(&mut |type_ref| {
 764         if matches!(type_ref, TypeRef::ImplTrait(_)) {
 765             count += 1;
 766         }
 767     });
 768     count
 769 }
 770
 771 /// Build the signature of a callable item (function, struct or enum variant).
 772 pub fn callable_item_sig(db: &dyn HirDatabase, def: CallableDefId) -> PolyFnSig {
 773     match def {
 774         CallableDefId::FunctionId(f) => fn_sig_for_fn(db, f),
 775         CallableDefId::StructId(s) => fn_sig_for_struct_constructor(db, s),
 776         CallableDefId::EnumVariantId(e) => fn_sig_for_enum_variant_constructor(db, e),
 777     }
 778 }
 779
 780 pub fn associated_type_shorthand_candidates<R>(
 781     db: &dyn HirDatabase,
 782     res: TypeNs,
 783     mut cb: impl FnMut(&Name, &TraitRef, TypeAliasId) -> Option<R>,
 784 ) -> Option<R> {
 785     let traits_from_env: Vec<_> = match res {
 786         TypeNs::SelfType(impl_id) => match db.impl_trait(impl_id) {
 787             None => vec![],
 788             Some(trait_ref) => vec![trait_ref.value],
 789         },
 790         TypeNs::GenericParam(param_id) => {
 791             let predicates = db.generic_predicates_for_param(param_id);
 792             let mut traits_: Vec<_> = predicates
 793                 .iter()
 794                 .filter_map(|pred| match &pred.value {
 795                     GenericPredicate::Implemented(tr) => Some(tr.clone()),
 796                     _ => None,
 797                 })
 798                 .collect();
 799             // Handle `Self::Type` referring to own associated type in trait definitions
 800             if let GenericDefId::TraitId(trait_id) = param_id.parent {
 801                 let generics = generics(db.upcast(), trait_id.into());
 802                 if generics.params.types[param_id.local_id].provenance
 803                     == TypeParamProvenance::TraitSelf
 804                 {
 805                     let trait_ref = TraitRef {
 806                         trait_: trait_id,
 807                         substs: Substs::bound_vars(&generics, DebruijnIndex::INNERMOST),
 808                     };
 809                     traits_.push(trait_ref);
 810                 }
 811             }
 812             traits_
 813         }
 814         _ => vec![],
 815     };
 816
 817     for t in traits_from_env.into_iter().flat_map(move |t| all_super_trait_refs(db, t)) {
 818         let data = db.trait_data(t.trait_);
 819
 820         for (name, assoc_id) in &data.items {
 821             match assoc_id {
 822                 AssocItemId::TypeAliasId(alias) => {
 823                     if let Some(result) = cb(name, &t, *alias) {
 824                         return Some(result);
 825                     }
 826                 }
 827                 AssocItemId::FunctionId(_) | AssocItemId::ConstId(_) => {}
 828             }
 829         }
 830     }
 831
 832     None
 833 }
 834
 835 /// Build the type of all specific fields of a struct or enum variant.
 836 pub(crate) fn field_types_query(
 837     db: &dyn HirDatabase,
 838     variant_id: VariantId,
 839 ) -> Arc<ArenaMap<LocalFieldId, Binders<Ty>>> {
 840     let var_data = variant_data(db.upcast(), variant_id);
 841     let (resolver, def): (_, GenericDefId) = match variant_id {
 842         VariantId::StructId(it) => (it.resolver(db.upcast()), it.into()),
 843         VariantId::UnionId(it) => (it.resolver(db.upcast()), it.into()),
 844         VariantId::EnumVariantId(it) => (it.parent.resolver(db.upcast()), it.parent.into()),
 845     };
 846     let generics = generics(db.upcast(), def);
 847     let mut res = ArenaMap::default();
 848     let ctx =
 849         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
 850     for (field_id, field_data) in var_data.fields().iter() {
 851         res.insert(field_id, Binders::new(generics.len(), Ty::from_hir(&ctx, &field_data.type_ref)))
 852     }
 853     Arc::new(res)
 854 }
 855
 856 /// This query exists only to be used when resolving short-hand associated types
 857 /// like `T::Item`.
 858 ///
 859 /// See the analogous query in rustc and its comment:
 860 /// https://github.com/rust-lang/rust/blob/9150f844e2624eb013ec78ca08c1d416e6644026/src/librustc_typeck/astconv.rs#L46
 861 /// This is a query mostly to handle cycles somewhat gracefully; e.g. the
 862 /// following bounds are disallowed: `T: Foo<U::Item>, U: Foo<T::Item>`, but
 863 /// these are fine: `T: Foo<U::Item>, U: Foo<()>`.
 864 pub(crate) fn generic_predicates_for_param_query(
 865     db: &dyn HirDatabase,
 866     param_id: TypeParamId,
 867 ) -> Arc<[Binders<GenericPredicate>]> {
 868     let resolver = param_id.parent.resolver(db.upcast());
 869     let ctx =
 870         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
 871     let generics = generics(db.upcast(), param_id.parent);
 872     resolver
 873         .where_predicates_in_scope()
 874         // we have to filter out all other predicates *first*, before attempting to lower them
 875         .filter(|pred| match &pred.target {
 876             WherePredicateTarget::TypeRef(type_ref) => {
 877                 Ty::from_hir_only_param(&ctx, type_ref) == Some(param_id)
 878             }
 879             WherePredicateTarget::TypeParam(local_id) => *local_id == param_id.local_id,
 880         })
 881         .flat_map(|pred| {
 882             GenericPredicate::from_where_predicate(&ctx, pred)
 883                 .map(|p| Binders::new(generics.len(), p))
 884         })
 885         .collect()
 886 }
 887
 888 pub(crate) fn generic_predicates_for_param_recover(
 889     _db: &dyn HirDatabase,
 890     _cycle: &[String],
 891     _param_id: &TypeParamId,
 892 ) -> Arc<[Binders<GenericPredicate>]> {
 893     Arc::new([])
 894 }
 895
 896 impl TraitEnvironment {
 897     pub fn lower(db: &dyn HirDatabase, resolver: &Resolver) -> Arc<TraitEnvironment> {
 898         let ctx = TyLoweringContext::new(db, &resolver)
 899             .with_type_param_mode(TypeParamLoweringMode::Placeholder);
 900         let mut predicates = resolver
 901             .where_predicates_in_scope()
 902             .flat_map(|pred| GenericPredicate::from_where_predicate(&ctx, pred))
 903             .collect::<Vec<_>>();
 904
 905         if let Some(def) = resolver.generic_def() {
 906             let container: Option<AssocContainerId> = match def {
 907                 // FIXME: is there a function for this?
 908                 GenericDefId::FunctionId(f) => Some(f.lookup(db.upcast()).container),
 909                 GenericDefId::AdtId(_) => None,
 910                 GenericDefId::TraitId(_) => None,
 911                 GenericDefId::TypeAliasId(t) => Some(t.lookup(db.upcast()).container),
 912                 GenericDefId::ImplId(_) => None,
 913                 GenericDefId::EnumVariantId(_) => None,
 914                 GenericDefId::ConstId(c) => Some(c.lookup(db.upcast()).container),
 915             };
 916             if let Some(AssocContainerId::TraitId(trait_id)) = container {
 917                 // add `Self: Trait<T1, T2, ...>` to the environment in trait
 918                 // function default implementations (and hypothetical code
 919                 // inside consts or type aliases)
 920                 test_utils::mark::hit!(trait_self_implements_self);
 921                 let substs = Substs::type_params(db, trait_id);
 922                 let trait_ref = TraitRef { trait_: trait_id, substs };
 923                 let pred = GenericPredicate::Implemented(trait_ref);
 924
 925                 predicates.push(pred);
 926             }
 927         }
 928
 929         Arc::new(TraitEnvironment { predicates })
 930     }
 931 }
 932
 933 /// Resolve the where clause(s) of an item with generics.
 934 pub(crate) fn generic_predicates_query(
 935     db: &dyn HirDatabase,
 936     def: GenericDefId,
 937 ) -> Arc<[Binders<GenericPredicate>]> {
 938     let resolver = def.resolver(db.upcast());
 939     let ctx =
 940         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
 941     let generics = generics(db.upcast(), def);
 942     resolver
 943         .where_predicates_in_scope()
 944         .flat_map(|pred| {
 945             GenericPredicate::from_where_predicate(&ctx, pred)
 946                 .map(|p| Binders::new(generics.len(), p))
 947         })
 948         .collect()
 949 }
 950
 951 /// Resolve the default type params from generics
 952 pub(crate) fn generic_defaults_query(
 953     db: &dyn HirDatabase,
 954     def: GenericDefId,
 955 ) -> Arc<[Binders<Ty>]> {
 956     let resolver = def.resolver(db.upcast());
 957     let ctx =
 958         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
 959     let generic_params = generics(db.upcast(), def);
 960
 961     let defaults = generic_params
 962         .iter()
 963         .enumerate()
 964         .map(|(idx, (_, p))| {
 965             let mut ty = p.default.as_ref().map_or(Ty::Unknown, |t| Ty::from_hir(&ctx, t));
 966
 967             // Each default can only refer to previous parameters.
 968             ty.walk_mut_binders(
 969                 &mut |ty, binders| match ty {
 970                     Ty::Bound(BoundVar { debruijn, index }) if *debruijn == binders => {
 971                         if *index >= idx {
 972                             // type variable default referring to parameter coming
 973                             // after it. This is forbidden (FIXME: report
 974                             // diagnostic)
 975                             *ty = Ty::Unknown;
 976                         }
 977                     }
 978                     _ => {}
 979                 },
 980                 DebruijnIndex::INNERMOST,
 981             );
 982
 983             Binders::new(idx, ty)
 984         })
 985         .collect();
 986
 987     defaults
 988 }
 989
 990 fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
 991     let data = db.function_data(def);
 992     let resolver = def.resolver(db.upcast());
 993     let ctx_params = TyLoweringContext::new(db, &resolver)
 994         .with_impl_trait_mode(ImplTraitLoweringMode::Variable)
 995         .with_type_param_mode(TypeParamLoweringMode::Variable);
 996     let params = data.params.iter().map(|tr| Ty::from_hir(&ctx_params, tr)).collect::<Vec<_>>();
 997     let ctx_ret = TyLoweringContext::new(db, &resolver)
 998         .with_impl_trait_mode(ImplTraitLoweringMode::Opaque)
 999         .with_type_param_mode(TypeParamLoweringMode::Variable);
1000     let ret = Ty::from_hir(&ctx_ret, &data.ret_type);
1001     let generics = generics(db.upcast(), def.into());
1002     let num_binders = generics.len();
1003     Binders::new(num_binders, FnSig::from_params_and_return(params, ret, data.is_varargs))
1004 }
1005
1006 /// Build the declared type of a function. This should not need to look at the
1007 /// function body.
1008 fn type_for_fn(db: &dyn HirDatabase, def: FunctionId) -> Binders<Ty> {
1009     let generics = generics(db.upcast(), def.into());
1010     let substs = Substs::bound_vars(&generics, DebruijnIndex::INNERMOST);
1011     Binders::new(substs.len(), Ty::apply(TypeCtor::FnDef(def.into()), substs))
1012 }
1013
1014 /// Build the declared type of a const.
1015 fn type_for_const(db: &dyn HirDatabase, def: ConstId) -> Binders<Ty> {
1016     let data = db.const_data(def);
1017     let generics = generics(db.upcast(), def.into());
1018     let resolver = def.resolver(db.upcast());
1019     let ctx =
1020         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1021
1022     Binders::new(generics.len(), Ty::from_hir(&ctx, &data.type_ref))
1023 }
1024
1025 /// Build the declared type of a static.
1026 fn type_for_static(db: &dyn HirDatabase, def: StaticId) -> Binders<Ty> {
1027     let data = db.static_data(def);
1028     let resolver = def.resolver(db.upcast());
1029     let ctx = TyLoweringContext::new(db, &resolver);
1030
1031     Binders::new(0, Ty::from_hir(&ctx, &data.type_ref))
1032 }
1033
1034 /// Build the declared type of a static.
1035 fn type_for_builtin(def: BuiltinType) -> Ty {
1036     Ty::simple(match def {
1037         BuiltinType::Char => TypeCtor::Char,
1038         BuiltinType::Bool => TypeCtor::Bool,
1039         BuiltinType::Str => TypeCtor::Str,
1040         BuiltinType::Int(t) => TypeCtor::Int(IntTy::from(t).into()),
1041         BuiltinType::Float(t) => TypeCtor::Float(FloatTy::from(t).into()),
1042     })
1043 }
1044
1045 fn fn_sig_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> PolyFnSig {
1046     let struct_data = db.struct_data(def);
1047     let fields = struct_data.variant_data.fields();
1048     let resolver = def.resolver(db.upcast());
1049     let ctx =
1050         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1051     let params =
1052         fields.iter().map(|(_, field)| Ty::from_hir(&ctx, &field.type_ref)).collect::<Vec<_>>();
1053     let ret = type_for_adt(db, def.into());
1054     Binders::new(ret.num_binders, FnSig::from_params_and_return(params, ret.value, false))
1055 }
1056
1057 /// Build the type of a tuple struct constructor.
1058 fn type_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> Binders<Ty> {
1059     let struct_data = db.struct_data(def);
1060     if let StructKind::Unit = struct_data.variant_data.kind() {
1061         return type_for_adt(db, def.into());
1062     }
1063     let generics = generics(db.upcast(), def.into());
1064     let substs = Substs::bound_vars(&generics, DebruijnIndex::INNERMOST);
1065     Binders::new(substs.len(), Ty::apply(TypeCtor::FnDef(def.into()), substs))
1066 }
1067
1068 fn fn_sig_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -> PolyFnSig {
1069     let enum_data = db.enum_data(def.parent);
1070     let var_data = &enum_data.variants[def.local_id];
1071     let fields = var_data.variant_data.fields();
1072     let resolver = def.parent.resolver(db.upcast());
1073     let ctx =
1074         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1075     let params =
1076         fields.iter().map(|(_, field)| Ty::from_hir(&ctx, &field.type_ref)).collect::<Vec<_>>();
1077     let ret = type_for_adt(db, def.parent.into());
1078     Binders::new(ret.num_binders, FnSig::from_params_and_return(params, ret.value, false))
1079 }
1080
1081 /// Build the type of a tuple enum variant constructor.
1082 fn type_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -> Binders<Ty> {
1083     let enum_data = db.enum_data(def.parent);
1084     let var_data = &enum_data.variants[def.local_id].variant_data;
1085     if let StructKind::Unit = var_data.kind() {
1086         return type_for_adt(db, def.parent.into());
1087     }
1088     let generics = generics(db.upcast(), def.parent.into());
1089     let substs = Substs::bound_vars(&generics, DebruijnIndex::INNERMOST);
1090     Binders::new(substs.len(), Ty::apply(TypeCtor::FnDef(def.into()), substs))
1091 }
1092
1093 fn type_for_adt(db: &dyn HirDatabase, adt: AdtId) -> Binders<Ty> {
1094     let generics = generics(db.upcast(), adt.into());
1095     let substs = Substs::bound_vars(&generics, DebruijnIndex::INNERMOST);
1096     Binders::new(substs.len(), Ty::apply(TypeCtor::Adt(adt), substs))
1097 }
1098
1099 fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders<Ty> {
1100     let generics = generics(db.upcast(), t.into());
1101     let resolver = t.resolver(db.upcast());
1102     let ctx =
1103         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1104     let type_ref = &db.type_alias_data(t).type_ref;
1105     let substs = Substs::bound_vars(&generics, DebruijnIndex::INNERMOST);
1106     let inner = Ty::from_hir(&ctx, type_ref.as_ref().unwrap_or(&TypeRef::Error));
1107     Binders::new(substs.len(), inner)
1108 }
1109
1110 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
1111 pub enum CallableDefId {
1112     FunctionId(FunctionId),
1113     StructId(StructId),
1114     EnumVariantId(EnumVariantId),
1115 }
1116 impl_from!(FunctionId, StructId, EnumVariantId for CallableDefId);
1117
1118 impl CallableDefId {
1119     pub fn krate(self, db: &dyn HirDatabase) -> CrateId {
1120         let db = db.upcast();
1121         match self {
1122             CallableDefId::FunctionId(f) => f.lookup(db).module(db),
1123             CallableDefId::StructId(s) => s.lookup(db).container.module(db),
1124             CallableDefId::EnumVariantId(e) => e.parent.lookup(db).container.module(db),
1125         }
1126         .krate
1127     }
1128 }
1129
1130 impl From<CallableDefId> for GenericDefId {
1131     fn from(def: CallableDefId) -> GenericDefId {
1132         match def {
1133             CallableDefId::FunctionId(f) => f.into(),
1134             CallableDefId::StructId(s) => s.into(),
1135             CallableDefId::EnumVariantId(e) => e.into(),
1136         }
1137     }
1138 }
1139
1140 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1141 pub enum TyDefId {
1142     BuiltinType(BuiltinType),
1143     AdtId(AdtId),
1144     TypeAliasId(TypeAliasId),
1145 }
1146 impl_from!(BuiltinType, AdtId(StructId, EnumId, UnionId), TypeAliasId for TyDefId);
1147
1148 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1149 pub enum ValueTyDefId {
1150     FunctionId(FunctionId),
1151     StructId(StructId),
1152     UnionId(UnionId),
1153     EnumVariantId(EnumVariantId),
1154     ConstId(ConstId),
1155     StaticId(StaticId),
1156 }
1157 impl_from!(FunctionId, StructId, UnionId, EnumVariantId, ConstId, StaticId for ValueTyDefId);
1158
1159 /// Build the declared type of an item. This depends on the namespace; e.g. for
1160 /// `struct Foo(usize)`, we have two types: The type of the struct itself, and
1161 /// the constructor function `(usize) -> Foo` which lives in the values
1162 /// namespace.
1163 pub(crate) fn ty_query(db: &dyn HirDatabase, def: TyDefId) -> Binders<Ty> {
1164     match def {
1165         TyDefId::BuiltinType(it) => Binders::new(0, type_for_builtin(it)),
1166         TyDefId::AdtId(it) => type_for_adt(db, it),
1167         TyDefId::TypeAliasId(it) => type_for_type_alias(db, it),
1168     }
1169 }
1170
1171 pub(crate) fn ty_recover(db: &dyn HirDatabase, _cycle: &[String], def: &TyDefId) -> Binders<Ty> {
1172     let num_binders = match *def {
1173         TyDefId::BuiltinType(_) => 0,
1174         TyDefId::AdtId(it) => generics(db.upcast(), it.into()).len(),
1175         TyDefId::TypeAliasId(it) => generics(db.upcast(), it.into()).len(),
1176     };
1177     Binders::new(num_binders, Ty::Unknown)
1178 }
1179
1180 pub(crate) fn value_ty_query(db: &dyn HirDatabase, def: ValueTyDefId) -> Binders<Ty> {
1181     match def {
1182         ValueTyDefId::FunctionId(it) => type_for_fn(db, it),
1183         ValueTyDefId::StructId(it) => type_for_struct_constructor(db, it),
1184         ValueTyDefId::UnionId(it) => type_for_adt(db, it.into()),
1185         ValueTyDefId::EnumVariantId(it) => type_for_enum_variant_constructor(db, it),
1186         ValueTyDefId::ConstId(it) => type_for_const(db, it),
1187         ValueTyDefId::StaticId(it) => type_for_static(db, it),
1188     }
1189 }
1190
1191 pub(crate) fn impl_self_ty_query(db: &dyn HirDatabase, impl_id: ImplId) -> Binders<Ty> {
1192     let impl_data = db.impl_data(impl_id);
1193     let resolver = impl_id.resolver(db.upcast());
1194     let generics = generics(db.upcast(), impl_id.into());
1195     let ctx =
1196         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1197     Binders::new(generics.len(), Ty::from_hir(&ctx, &impl_data.target_type))
1198 }
1199
1200 pub(crate) fn impl_self_ty_recover(
1201     db: &dyn HirDatabase,
1202     _cycle: &[String],
1203     impl_id: &ImplId,
1204 ) -> Binders<Ty> {
1205     let generics = generics(db.upcast(), (*impl_id).into());
1206     Binders::new(generics.len(), Ty::Unknown)
1207 }
1208
1209 pub(crate) fn impl_trait_query(db: &dyn HirDatabase, impl_id: ImplId) -> Option<Binders<TraitRef>> {
1210     let impl_data = db.impl_data(impl_id);
1211     let resolver = impl_id.resolver(db.upcast());
1212     let ctx =
1213         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
1214     let self_ty = db.impl_self_ty(impl_id);
1215     let target_trait = impl_data.target_trait.as_ref()?;
1216     Some(Binders::new(
1217         self_ty.num_binders,
1218         TraitRef::from_hir(&ctx, target_trait, Some(self_ty.value))?,
1219     ))
1220 }
1221
1222 pub(crate) fn return_type_impl_traits(
1223     db: &dyn HirDatabase,
1224     def: hir_def::FunctionId,
1225 ) -> Option<Arc<Binders<ReturnTypeImplTraits>>> {
1226     // FIXME unify with fn_sig_for_fn instead of doing lowering twice, maybe
1227     let data = db.function_data(def);
1228     let resolver = def.resolver(db.upcast());
1229     let ctx_ret = TyLoweringContext::new(db, &resolver)
1230         .with_impl_trait_mode(ImplTraitLoweringMode::Opaque)
1231         .with_type_param_mode(TypeParamLoweringMode::Variable);
1232     let _ret = Ty::from_hir(&ctx_ret, &data.ret_type);
1233     let generics = generics(db.upcast(), def.into());
1234     let num_binders = generics.len();
1235     let return_type_impl_traits =
1236         ReturnTypeImplTraits { impl_traits: ctx_ret.opaque_type_data.into_inner() };
1237     if return_type_impl_traits.impl_traits.is_empty() {
1238         None
1239     } else {
1240         Some(Arc::new(Binders::new(num_binders, return_type_impl_traits)))
1241     }
1242 }