crates/hir_ty/src/lower.rs

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