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