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