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