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