1 //! Methods for lowering the HIR to types. There are two main cases here:
3 //! - Lowering a type reference like `&usize` or `Option<foo::bar::Baz>` to a
4 //! type: The entry point for this is `TyLoweringContext::lower_ty`.
5 //! - Building the type for an item: This happens through the `ty` query.
7 //! This usually involves resolving names, collecting generic arguments etc.
9 cell::{Cell, RefCell, RefMut},
16 cast::Cast, fold::Shift, fold::TypeFoldable, interner::HasInterner, Mutability, Safety,
21 body::{Expander, LowerCtx},
22 builtin_type::BuiltinType,
24 TypeOrConstParamData, TypeParamProvenance, WherePredicate, WherePredicateTypeTarget,
28 path::{GenericArg, ModPath, Path, PathKind, PathSegment, PathSegments},
29 resolver::{HasResolver, Resolver, TypeNs},
31 ConstScalarOrPath, TraitBoundModifier, TraitRef as HirTraitRef, TypeBound, TypeRef,
33 AdtId, AssocItemId, ConstId, ConstParamId, EnumId, EnumVariantId, FunctionId, GenericDefId,
34 HasModule, ImplId, ItemContainerId, LocalFieldId, Lookup, StaticId, StructId, TraitId,
35 TypeAliasId, TypeOrConstParamId, TypeParamId, UnionId, VariantId,
37 use hir_expand::{name::Name, ExpandResult};
38 use itertools::Either;
39 use la_arena::ArenaMap;
40 use rustc_hash::FxHashSet;
41 use smallvec::SmallVec;
42 use stdx::{impl_from, never};
43 use syntax::{ast, SmolStr};
47 consteval::{intern_const_scalar, path_to_const, unknown_const, unknown_const_as_generic},
50 mapping::{from_chalk_trait_id, ToChalk},
51 static_lifetime, to_assoc_type_id, to_chalk_trait_id, to_placeholder_idx,
53 utils::{all_super_trait_refs, associated_type_by_name_including_super_traits, generics},
54 AliasEq, AliasTy, Binders, BoundVar, CallableSig, Const, DebruijnIndex, DynTy, FnPointer,
55 FnSig, FnSubst, GenericArgData, ImplTraitId, Interner, ParamKind, PolyFnSig, ProjectionTy,
56 QuantifiedWhereClause, QuantifiedWhereClauses, ReturnTypeImplTrait, ReturnTypeImplTraits,
57 Substitution, TraitEnvironment, TraitRef, TraitRefExt, Ty, TyBuilder, TyKind, WhereClause,
61 pub struct TyLoweringContext<'a> {
62 pub db: &'a dyn HirDatabase,
63 pub resolver: &'a Resolver,
64 in_binders: DebruijnIndex,
65 /// Note: Conceptually, it's thinkable that we could be in a location where
66 /// some type params should be represented as placeholders, and others
67 /// should be converted to variables. I think in practice, this isn't
68 /// possible currently, so this should be fine for now.
69 pub type_param_mode: ParamLoweringMode,
70 pub impl_trait_mode: ImplTraitLoweringMode,
71 impl_trait_counter: Cell<u16>,
72 /// When turning `impl Trait` into opaque types, we have to collect the
73 /// bounds at the same time to get the IDs correct (without becoming too
74 /// complicated). I don't like using interior mutability (as for the
75 /// counter), but I've tried and failed to make the lifetimes work for
76 /// passing around a `&mut TyLoweringContext`. The core problem is that
77 /// we're grouping the mutable data (the counter and this field) together
78 /// with the immutable context (the references to the DB and resolver).
79 /// Splitting this up would be a possible fix.
80 opaque_type_data: RefCell<Vec<ReturnTypeImplTrait>>,
81 expander: RefCell<Option<Expander>>,
82 /// Tracks types with explicit `?Sized` bounds.
83 pub(crate) unsized_types: RefCell<FxHashSet<Ty>>,
86 impl<'a> TyLoweringContext<'a> {
87 pub fn new(db: &'a dyn HirDatabase, resolver: &'a Resolver) -> Self {
88 let impl_trait_counter = Cell::new(0);
89 let impl_trait_mode = ImplTraitLoweringMode::Disallowed;
90 let type_param_mode = ParamLoweringMode::Placeholder;
91 let in_binders = DebruijnIndex::INNERMOST;
92 let opaque_type_data = RefCell::new(Vec::new());
101 expander: RefCell::new(None),
102 unsized_types: RefCell::default(),
106 pub fn with_debruijn<T>(
108 debruijn: DebruijnIndex,
109 f: impl FnOnce(&TyLoweringContext<'_>) -> T,
111 let opaque_ty_data_vec = self.opaque_type_data.take();
112 let expander = self.expander.take();
113 let unsized_types = self.unsized_types.take();
115 in_binders: debruijn,
116 impl_trait_counter: Cell::new(self.impl_trait_counter.get()),
117 opaque_type_data: RefCell::new(opaque_ty_data_vec),
118 expander: RefCell::new(expander),
119 unsized_types: RefCell::new(unsized_types),
122 let result = f(&new_ctx);
123 self.impl_trait_counter.set(new_ctx.impl_trait_counter.get());
124 self.opaque_type_data.replace(new_ctx.opaque_type_data.into_inner());
125 self.expander.replace(new_ctx.expander.into_inner());
126 self.unsized_types.replace(new_ctx.unsized_types.into_inner());
130 pub fn with_shifted_in<T>(
132 debruijn: DebruijnIndex,
133 f: impl FnOnce(&TyLoweringContext<'_>) -> T,
135 self.with_debruijn(self.in_binders.shifted_in_from(debruijn), f)
138 pub fn with_impl_trait_mode(self, impl_trait_mode: ImplTraitLoweringMode) -> Self {
139 Self { impl_trait_mode, ..self }
142 pub fn with_type_param_mode(self, type_param_mode: ParamLoweringMode) -> Self {
143 Self { type_param_mode, ..self }
147 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
148 pub enum ImplTraitLoweringMode {
149 /// `impl Trait` gets lowered into an opaque type that doesn't unify with
150 /// anything except itself. This is used in places where values flow 'out',
151 /// i.e. for arguments of the function we're currently checking, and return
152 /// types of functions we're calling.
154 /// `impl Trait` gets lowered into a type variable. Used for argument
155 /// position impl Trait when inside the respective function, since it allows
156 /// us to support that without Chalk.
158 /// `impl Trait` gets lowered into a variable that can unify with some
159 /// type. This is used in places where values flow 'in', i.e. for arguments
160 /// of functions we're calling, and the return type of the function we're
161 /// currently checking.
163 /// `impl Trait` is disallowed and will be an error.
167 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
168 pub enum ParamLoweringMode {
173 impl<'a> TyLoweringContext<'a> {
174 pub fn lower_ty(&self, type_ref: &TypeRef) -> Ty {
175 self.lower_ty_ext(type_ref).0
178 fn generics(&self) -> Generics {
183 .expect("there should be generics if there's a generic param"),
187 pub fn lower_ty_ext(&self, type_ref: &TypeRef) -> (Ty, Option<TypeNs>) {
189 let ty = match type_ref {
190 TypeRef::Never => TyKind::Never.intern(Interner),
191 TypeRef::Tuple(inner) => {
192 let inner_tys = inner.iter().map(|tr| self.lower_ty(tr));
193 TyKind::Tuple(inner_tys.len(), Substitution::from_iter(Interner, inner_tys))
196 TypeRef::Path(path) => {
197 let (ty, res_) = self.lower_path(path);
201 TypeRef::RawPtr(inner, mutability) => {
202 let inner_ty = self.lower_ty(inner);
203 TyKind::Raw(lower_to_chalk_mutability(*mutability), inner_ty).intern(Interner)
205 TypeRef::Array(inner, len) => {
206 let inner_ty = self.lower_ty(inner);
207 let const_len = const_or_path_to_chalk(
212 self.type_param_mode,
217 TyKind::Array(inner_ty, const_len).intern(Interner)
219 TypeRef::Slice(inner) => {
220 let inner_ty = self.lower_ty(inner);
221 TyKind::Slice(inner_ty).intern(Interner)
223 TypeRef::Reference(inner, _, mutability) => {
224 let inner_ty = self.lower_ty(inner);
225 let lifetime = static_lifetime();
226 TyKind::Ref(lower_to_chalk_mutability(*mutability), lifetime, inner_ty)
229 TypeRef::Placeholder => TyKind::Error.intern(Interner),
230 &TypeRef::Fn(ref params, variadic, is_unsafe) => {
231 let substs = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
232 Substitution::from_iter(Interner, params.iter().map(|(_, tr)| ctx.lower_ty(tr)))
234 TyKind::Function(FnPointer {
235 num_binders: 0, // FIXME lower `for<'a> fn()` correctly
238 safety: if is_unsafe { Safety::Unsafe } else { Safety::Safe },
241 substitution: FnSubst(substs),
245 TypeRef::DynTrait(bounds) => self.lower_dyn_trait(bounds),
246 TypeRef::ImplTrait(bounds) => {
247 match self.impl_trait_mode {
248 ImplTraitLoweringMode::Opaque => {
249 let idx = self.impl_trait_counter.get();
250 self.impl_trait_counter.set(idx + 1);
251 let func = match self.resolver.generic_def() {
252 Some(GenericDefId::FunctionId(f)) => f,
253 _ => panic!("opaque impl trait lowering in non-function"),
256 assert!(idx as usize == self.opaque_type_data.borrow().len());
257 // this dance is to make sure the data is in the right
258 // place even if we encounter more opaque types while
259 // lowering the bounds
260 self.opaque_type_data.borrow_mut().push(ReturnTypeImplTrait {
261 bounds: crate::make_single_type_binders(Vec::new()),
263 // We don't want to lower the bounds inside the binders
264 // we're currently in, because they don't end up inside
265 // those binders. E.g. when we have `impl Trait<impl
266 // OtherTrait<T>>`, the `impl OtherTrait<T>` can't refer
267 // to the self parameter from `impl Trait`, and the
268 // bounds aren't actually stored nested within each
269 // other, but separately. So if the `T` refers to a type
270 // parameter of the outer function, it's just one binder
271 // away instead of two.
272 let actual_opaque_type_data = self
273 .with_debruijn(DebruijnIndex::INNERMOST, |ctx| {
274 ctx.lower_impl_trait(bounds, func)
276 self.opaque_type_data.borrow_mut()[idx as usize] = actual_opaque_type_data;
278 let impl_trait_id = ImplTraitId::ReturnTypeImplTrait(func, idx);
279 let opaque_ty_id = self.db.intern_impl_trait_id(impl_trait_id).into();
280 let generics = generics(self.db.upcast(), func.into());
281 let parameters = generics.bound_vars_subst(self.db, self.in_binders);
282 TyKind::OpaqueType(opaque_ty_id, parameters).intern(Interner)
284 ImplTraitLoweringMode::Param => {
285 let idx = self.impl_trait_counter.get();
286 // FIXME we're probably doing something wrong here
287 self.impl_trait_counter.set(idx + count_impl_traits(type_ref) as u16);
288 if let Some(def) = self.resolver.generic_def() {
289 let generics = generics(self.db.upcast(), def);
292 .filter(|(_, data)| {
295 TypeOrConstParamData::TypeParamData(data)
296 if data.provenance == TypeParamProvenance::ArgumentImplTrait
300 .map_or(TyKind::Error, |(id, _)| {
301 TyKind::Placeholder(to_placeholder_idx(self.db, id))
303 param.intern(Interner)
305 TyKind::Error.intern(Interner)
308 ImplTraitLoweringMode::Variable => {
309 let idx = self.impl_trait_counter.get();
310 // FIXME we're probably doing something wrong here
311 self.impl_trait_counter.set(idx + count_impl_traits(type_ref) as u16);
318 ) = if let Some(def) = self.resolver.generic_def() {
319 let generics = generics(self.db.upcast(), def);
320 generics.provenance_split()
324 TyKind::BoundVar(BoundVar::new(
326 idx as usize + self_params + list_params + const_params,
330 ImplTraitLoweringMode::Disallowed => {
331 // FIXME: report error
332 TyKind::Error.intern(Interner)
336 TypeRef::Macro(macro_call) => {
337 let (mut expander, recursion_start) = {
338 match RefMut::filter_map(self.expander.borrow_mut(), Option::as_mut) {
339 // There already is an expander here, this means we are already recursing
340 Ok(expander) => (expander, false),
341 // No expander was created yet, so we are at the start of the expansion recursion
342 // and therefore have to create an expander.
344 RefMut::map(expander, |it| {
345 it.insert(Expander::new(
348 self.resolver.module(),
356 let macro_call = macro_call.to_node(self.db.upcast());
357 match expander.enter_expand::<ast::Type>(self.db.upcast(), macro_call) {
358 Ok(ExpandResult { value: Some((mark, expanded)), .. }) => {
359 let ctx = LowerCtx::new(self.db.upcast(), expander.current_file_id());
360 let type_ref = TypeRef::from_ast(&ctx, expanded);
363 let ty = self.lower_ty(&type_ref);
369 .exit(self.db.upcast(), mark);
379 // drop the expander, resetting it to pre-recursion state
381 *self.expander.borrow_mut() = None;
383 ty.unwrap_or_else(|| TyKind::Error.intern(Interner))
385 TypeRef::Error => TyKind::Error.intern(Interner),
390 /// This is only for `generic_predicates_for_param`, where we can't just
391 /// lower the self types of the predicates since that could lead to cycles.
392 /// So we just check here if the `type_ref` resolves to a generic param, and which.
393 fn lower_ty_only_param(&self, type_ref: &TypeRef) -> Option<TypeOrConstParamId> {
394 let path = match type_ref {
395 TypeRef::Path(path) => path,
398 if path.type_anchor().is_some() {
401 if path.segments().len() > 1 {
405 match self.resolver.resolve_path_in_type_ns(self.db.upcast(), path.mod_path()) {
406 Some((it, None)) => it,
410 TypeNs::GenericParam(param_id) => Some(param_id.into()),
415 pub(crate) fn lower_ty_relative_path(
418 // We need the original resolution to lower `Self::AssocTy` correctly
420 remaining_segments: PathSegments<'_>,
421 ) -> (Ty, Option<TypeNs>) {
422 match remaining_segments.len() {
425 // resolve unselected assoc types
426 let segment = remaining_segments.first().unwrap();
427 (self.select_associated_type(res, segment), None)
430 // FIXME report error (ambiguous associated type)
431 (TyKind::Error.intern(Interner), None)
436 pub(crate) fn lower_partly_resolved_path(
439 resolved_segment: PathSegment<'_>,
440 remaining_segments: PathSegments<'_>,
442 ) -> (Ty, Option<TypeNs>) {
443 let ty = match resolution {
444 TypeNs::TraitId(trait_) => {
445 let ty = match remaining_segments.len() {
448 self.lower_trait_ref_from_resolved_path(trait_, resolved_segment, None);
449 let segment = remaining_segments.first().unwrap();
452 .trait_data(trait_ref.hir_trait_id())
453 .associated_type_by_name(segment.name);
456 Some(associated_ty) => {
457 // FIXME: `substs_from_path_segment()` pushes `TyKind::Error` for every parent
458 // generic params. It's inefficient to splice the `Substitution`s, so we may want
459 // that method to optionally take parent `Substitution` as we already know them at
460 // this point (`trait_ref.substitution`).
461 let substitution = self.substs_from_path_segment(
463 Some(associated_ty.into()),
468 generics(self.db.upcast(), associated_ty.into()).len_self();
469 let substitution = Substitution::from_iter(
474 .chain(trait_ref.substitution.iter(Interner)),
476 TyKind::Alias(AliasTy::Projection(ProjectionTy {
477 associated_ty_id: to_assoc_type_id(associated_ty),
483 // FIXME: report error (associated type not found)
484 TyKind::Error.intern(Interner)
489 // Trait object type without dyn; this should be handled in upstream. See
491 stdx::never!("unexpected fully resolved trait path");
492 TyKind::Error.intern(Interner)
495 // FIXME report error (ambiguous associated type)
496 TyKind::Error.intern(Interner)
501 TypeNs::GenericParam(param_id) => {
502 let generics = generics(
504 self.resolver.generic_def().expect("generics in scope"),
506 match self.type_param_mode {
507 ParamLoweringMode::Placeholder => {
508 TyKind::Placeholder(to_placeholder_idx(self.db, param_id.into()))
510 ParamLoweringMode::Variable => {
511 let idx = match generics.param_idx(param_id.into()) {
513 never!("no matching generics");
514 return (TyKind::Error.intern(Interner), None);
519 TyKind::BoundVar(BoundVar::new(self.in_binders, idx))
524 TypeNs::SelfType(impl_id) => {
526 self.resolver.generic_def().expect("impl should have generic param scope");
527 let generics = generics(self.db.upcast(), def);
529 match self.type_param_mode {
530 ParamLoweringMode::Placeholder => {
531 // `def` can be either impl itself or item within, and we need impl itself
533 let generics = generics.parent_generics().unwrap_or(&generics);
534 let subst = generics.placeholder_subst(self.db);
535 self.db.impl_self_ty(impl_id).substitute(Interner, &subst)
537 ParamLoweringMode::Variable => {
538 let starting_from = match def {
539 GenericDefId::ImplId(_) => 0,
540 // `def` is an item within impl. We need to substitute `BoundVar`s but
541 // remember that they are for parent (i.e. impl) generic params so they
542 // come after our own params.
543 _ => generics.len_self(),
545 TyBuilder::impl_self_ty(self.db, impl_id)
546 .fill_with_bound_vars(self.in_binders, starting_from)
551 TypeNs::AdtSelfType(adt) => {
552 let generics = generics(self.db.upcast(), adt.into());
553 let substs = match self.type_param_mode {
554 ParamLoweringMode::Placeholder => generics.placeholder_subst(self.db),
555 ParamLoweringMode::Variable => {
556 generics.bound_vars_subst(self.db, self.in_binders)
559 self.db.ty(adt.into()).substitute(Interner, &substs)
562 TypeNs::AdtId(it) => self.lower_path_inner(resolved_segment, it.into(), infer_args),
563 TypeNs::BuiltinType(it) => {
564 self.lower_path_inner(resolved_segment, it.into(), infer_args)
566 TypeNs::TypeAliasId(it) => {
567 self.lower_path_inner(resolved_segment, it.into(), infer_args)
569 // FIXME: report error
570 TypeNs::EnumVariantId(_) => return (TyKind::Error.intern(Interner), None),
572 self.lower_ty_relative_path(ty, Some(resolution), remaining_segments)
575 pub(crate) fn lower_path(&self, path: &Path) -> (Ty, Option<TypeNs>) {
576 // Resolve the path (in type namespace)
577 if let Some(type_ref) = path.type_anchor() {
578 let (ty, res) = self.lower_ty_ext(type_ref);
579 return self.lower_ty_relative_path(ty, res, path.segments());
582 let (resolution, remaining_index) =
583 match self.resolver.resolve_path_in_type_ns(self.db.upcast(), path.mod_path()) {
585 None => return (TyKind::Error.intern(Interner), None),
588 if matches!(resolution, TypeNs::TraitId(_)) && remaining_index.is_none() {
589 // trait object type without dyn
590 let bound = TypeBound::Path(path.clone(), TraitBoundModifier::None);
591 let ty = self.lower_dyn_trait(&[Interned::new(bound)]);
595 let (resolved_segment, remaining_segments) = match remaining_index {
597 path.segments().last().expect("resolved path has at least one element"),
600 Some(i) => (path.segments().get(i - 1).unwrap(), path.segments().skip(i)),
602 self.lower_partly_resolved_path(resolution, resolved_segment, remaining_segments, false)
605 fn select_associated_type(&self, res: Option<TypeNs>, segment: PathSegment<'_>) -> Ty {
606 let Some((def, res)) = self.resolver.generic_def().zip(res) else {
607 return TyKind::Error.intern(Interner);
609 let ty = named_associated_type_shorthand_candidates(
613 Some(segment.name.clone()),
614 move |name, t, associated_ty| {
615 if name != segment.name {
619 let parent_subst = t.substitution.clone();
620 let parent_subst = match self.type_param_mode {
621 ParamLoweringMode::Placeholder => {
622 // if we're lowering to placeholders, we have to put them in now.
623 let generics = generics(self.db.upcast(), def);
624 let s = generics.placeholder_subst(self.db);
625 s.apply(parent_subst, Interner)
627 ParamLoweringMode::Variable => {
628 // We need to shift in the bound vars, since
629 // `named_associated_type_shorthand_candidates` does not do that.
630 parent_subst.shifted_in_from(Interner, self.in_binders)
634 // FIXME: `substs_from_path_segment()` pushes `TyKind::Error` for every parent
635 // generic params. It's inefficient to splice the `Substitution`s, so we may want
636 // that method to optionally take parent `Substitution` as we already know them at
637 // this point (`t.substitution`).
638 let substs = self.substs_from_path_segment(
640 Some(associated_ty.into()),
645 let len_self = generics(self.db.upcast(), associated_ty.into()).len_self();
647 let substs = Substitution::from_iter(
649 substs.iter(Interner).take(len_self).chain(parent_subst.iter(Interner)),
653 TyKind::Alias(AliasTy::Projection(ProjectionTy {
654 associated_ty_id: to_assoc_type_id(associated_ty),
655 substitution: substs,
662 ty.unwrap_or_else(|| TyKind::Error.intern(Interner))
667 segment: PathSegment<'_>,
671 let generic_def = match typeable {
672 TyDefId::BuiltinType(_) => None,
673 TyDefId::AdtId(it) => Some(it.into()),
674 TyDefId::TypeAliasId(it) => Some(it.into()),
676 let substs = self.substs_from_path_segment(segment, generic_def, infer_args, None);
677 self.db.ty(typeable).substitute(Interner, &substs)
680 /// Collect generic arguments from a path into a `Substs`. See also
681 /// `create_substs_for_ast_path` and `def_to_ty` in rustc.
682 pub(super) fn substs_from_path(
685 // Note that we don't call `db.value_type(resolved)` here,
686 // `ValueTyDefId` is just a convenient way to pass generics and
687 // special-case enum variants
688 resolved: ValueTyDefId,
691 let last = path.segments().last().expect("path should have at least one segment");
692 let (segment, generic_def) = match resolved {
693 ValueTyDefId::FunctionId(it) => (last, Some(it.into())),
694 ValueTyDefId::StructId(it) => (last, Some(it.into())),
695 ValueTyDefId::UnionId(it) => (last, Some(it.into())),
696 ValueTyDefId::ConstId(it) => (last, Some(it.into())),
697 ValueTyDefId::StaticId(_) => (last, None),
698 ValueTyDefId::EnumVariantId(var) => {
699 // the generic args for an enum variant may be either specified
700 // on the segment referring to the enum, or on the segment
701 // referring to the variant. So `Option::<T>::None` and
702 // `Option::None::<T>` are both allowed (though the former is
703 // preferred). See also `def_ids_for_path_segments` in rustc.
704 let len = path.segments().len();
705 let penultimate = len.checked_sub(2).and_then(|idx| path.segments().get(idx));
706 let segment = match penultimate {
707 Some(segment) if segment.args_and_bindings.is_some() => segment,
710 (segment, Some(var.parent.into()))
713 self.substs_from_path_segment(segment, generic_def, infer_args, None)
716 fn substs_from_path_segment(
718 segment: PathSegment<'_>,
719 def: Option<GenericDefId>,
721 explicit_self_ty: Option<Ty>,
723 // Remember that the item's own generic args come before its parent's.
724 let mut substs = Vec::new();
725 let def = if let Some(d) = def {
728 return Substitution::empty(Interner);
730 let def_generics = generics(self.db.upcast(), def);
731 let (parent_params, self_params, type_params, const_params, impl_trait_params) =
732 def_generics.provenance_split();
733 let item_len = self_params + type_params + const_params + impl_trait_params;
734 let total_len = parent_params + item_len;
736 let ty_error = TyKind::Error.intern(Interner).cast(Interner);
738 let mut def_generic_iter = def_generics.iter_id();
740 let fill_self_params = || {
741 for x in explicit_self_ty
743 .map(|x| x.cast(Interner))
744 .chain(iter::repeat(ty_error.clone()))
747 if let Some(id) = def_generic_iter.next() {
748 assert!(id.is_left());
753 let mut had_explicit_args = false;
755 if let Some(generic_args) = &segment.args_and_bindings {
756 if !generic_args.has_self_type {
759 let expected_num = if generic_args.has_self_type {
760 self_params + type_params + const_params
762 type_params + const_params
764 let skip = if generic_args.has_self_type && self_params == 0 { 1 } else { 0 };
765 // if args are provided, it should be all of them, but we can't rely on that
766 for arg in generic_args
769 .filter(|arg| !matches!(arg, GenericArg::Lifetime(_)))
773 if let Some(id) = def_generic_iter.next() {
774 if let Some(x) = generic_arg_to_chalk(
779 |_, type_ref| self.lower_ty(type_ref),
781 const_or_path_to_chalk(
786 self.type_param_mode,
792 had_explicit_args = true;
795 // we just filtered them out
796 never!("Unexpected lifetime argument");
804 // These params include those of parent.
805 let remaining_params: SmallVec<[_; 2]> = def_generic_iter
806 .map(|eid| match eid {
807 Either::Left(_) => ty_error.clone(),
808 Either::Right(x) => unknown_const_as_generic(self.db.const_param_ty(x)),
811 assert_eq!(remaining_params.len() + substs.len(), total_len);
813 // handle defaults. In expression or pattern path segments without
814 // explicitly specified type arguments, missing type arguments are inferred
815 // (i.e. defaults aren't used).
816 // Generic parameters for associated types are not supposed to have defaults, so we just
818 let is_assoc_ty = if let GenericDefId::TypeAliasId(id) = def {
819 let container = id.lookup(self.db.upcast()).container;
820 matches!(container, ItemContainerId::TraitId(_))
824 if !is_assoc_ty && (!infer_args || had_explicit_args) {
825 let defaults = self.db.generic_defaults(def);
826 assert_eq!(total_len, defaults.len());
827 let parent_from = item_len - substs.len();
829 for (idx, default_ty) in defaults[substs.len()..item_len].iter().enumerate() {
830 // each default can depend on the previous parameters
831 let substs_so_far = Substitution::from_iter(
833 substs.iter().cloned().chain(remaining_params[idx..].iter().cloned()),
835 substs.push(default_ty.clone().substitute(Interner, &substs_so_far));
838 // Keep parent's params as unknown.
839 let mut remaining_params = remaining_params;
840 substs.extend(remaining_params.drain(parent_from..));
842 substs.extend(remaining_params);
845 assert_eq!(substs.len(), total_len);
846 Substitution::from_iter(Interner, substs)
849 fn lower_trait_ref_from_path(
852 explicit_self_ty: Option<Ty>,
853 ) -> Option<TraitRef> {
855 match self.resolver.resolve_path_in_type_ns_fully(self.db.upcast(), path.mod_path())? {
856 TypeNs::TraitId(tr) => tr,
859 let segment = path.segments().last().expect("path should have at least one segment");
860 Some(self.lower_trait_ref_from_resolved_path(resolved, segment, explicit_self_ty))
863 pub(crate) fn lower_trait_ref_from_resolved_path(
866 segment: PathSegment<'_>,
867 explicit_self_ty: Option<Ty>,
869 let substs = self.trait_ref_substs_from_path(segment, resolved, explicit_self_ty);
870 TraitRef { trait_id: to_chalk_trait_id(resolved), substitution: substs }
875 trait_ref: &HirTraitRef,
876 explicit_self_ty: Option<Ty>,
877 ) -> Option<TraitRef> {
878 self.lower_trait_ref_from_path(&trait_ref.path, explicit_self_ty)
881 fn trait_ref_substs_from_path(
883 segment: PathSegment<'_>,
885 explicit_self_ty: Option<Ty>,
887 self.substs_from_path_segment(segment, Some(resolved.into()), false, explicit_self_ty)
890 pub(crate) fn lower_where_predicate(
892 where_predicate: &'a WherePredicate,
893 ignore_bindings: bool,
894 ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
895 match where_predicate {
896 WherePredicate::ForLifetime { target, bound, .. }
897 | WherePredicate::TypeBound { target, bound } => {
898 let self_ty = match target {
899 WherePredicateTypeTarget::TypeRef(type_ref) => self.lower_ty(type_ref),
900 WherePredicateTypeTarget::TypeOrConstParam(param_id) => {
901 let generic_def = self.resolver.generic_def().expect("generics in scope");
902 let generics = generics(self.db.upcast(), generic_def);
903 let param_id = hir_def::TypeOrConstParamId {
907 let placeholder = to_placeholder_idx(self.db, param_id);
908 match self.type_param_mode {
909 ParamLoweringMode::Placeholder => TyKind::Placeholder(placeholder),
910 ParamLoweringMode::Variable => {
911 let idx = generics.param_idx(param_id).expect("matching generics");
912 TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, idx))
918 self.lower_type_bound(bound, self_ty, ignore_bindings)
922 WherePredicate::Lifetime { .. } => vec![].into_iter(),
926 pub(crate) fn lower_type_bound(
928 bound: &'a TypeBound,
930 ignore_bindings: bool,
931 ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
932 let mut bindings = None;
933 let trait_ref = match bound {
934 TypeBound::Path(path, TraitBoundModifier::None) => {
935 bindings = self.lower_trait_ref_from_path(path, Some(self_ty));
939 // ignore `T: Drop` or `T: Destruct` bounds.
940 // - `T: ~const Drop` has a special meaning in Rust 1.61 that we don't implement.
941 // (So ideally, we'd only ignore `~const Drop` here)
942 // - `Destruct` impls are built-in in 1.62 (current nightlies as of 08-04-2022), so until
943 // the builtin impls are supported by Chalk, we ignore them here.
944 if let Some(lang) = lang_attr(self.db.upcast(), tr.hir_trait_id()) {
945 if lang == "drop" || lang == "destruct" {
951 .map(WhereClause::Implemented)
952 .map(crate::wrap_empty_binders)
954 TypeBound::Path(path, TraitBoundModifier::Maybe) => {
955 let sized_trait = self
957 .lang_item(self.resolver.krate(), SmolStr::new_inline("sized"))
958 .and_then(|lang_item| lang_item.as_trait());
959 // Don't lower associated type bindings as the only possible relaxed trait bound
960 // `?Sized` has no of them.
961 // If we got another trait here ignore the bound completely.
963 .lower_trait_ref_from_path(path, Some(self_ty.clone()))
964 .map(|trait_ref| trait_ref.hir_trait_id());
965 if trait_id == sized_trait {
966 self.unsized_types.borrow_mut().insert(self_ty);
970 TypeBound::ForLifetime(_, path) => {
971 // FIXME Don't silently drop the hrtb lifetimes here
972 bindings = self.lower_trait_ref_from_path(path, Some(self_ty));
973 bindings.clone().map(WhereClause::Implemented).map(crate::wrap_empty_binders)
975 TypeBound::Lifetime(_) => None,
976 TypeBound::Error => None,
978 trait_ref.into_iter().chain(
981 .filter(move |_| !ignore_bindings)
982 .flat_map(move |tr| self.assoc_type_bindings_from_type_bound(bound, tr)),
986 fn assoc_type_bindings_from_type_bound(
988 bound: &'a TypeBound,
990 ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
991 let last_segment = match bound {
992 TypeBound::Path(path, TraitBoundModifier::None) | TypeBound::ForLifetime(_, path) => {
993 path.segments().last()
995 TypeBound::Path(_, TraitBoundModifier::Maybe)
997 | TypeBound::Lifetime(_) => None,
1001 .filter_map(|segment| segment.args_and_bindings)
1002 .flat_map(|args_and_bindings| &args_and_bindings.bindings)
1003 .flat_map(move |binding| {
1004 let found = associated_type_by_name_including_super_traits(
1009 let (super_trait_ref, associated_ty) = match found {
1010 None => return SmallVec::new(),
1013 // FIXME: `substs_from_path_segment()` pushes `TyKind::Error` for every parent
1014 // generic params. It's inefficient to splice the `Substitution`s, so we may want
1015 // that method to optionally take parent `Substitution` as we already know them at
1016 // this point (`super_trait_ref.substitution`).
1017 let substitution = self.substs_from_path_segment(
1018 // FIXME: This is hack. We shouldn't really build `PathSegment` directly.
1019 PathSegment { name: &binding.name, args_and_bindings: binding.args.as_deref() },
1020 Some(associated_ty.into()),
1021 false, // this is not relevant
1022 Some(super_trait_ref.self_type_parameter(Interner)),
1024 let self_params = generics(self.db.upcast(), associated_ty.into()).len_self();
1025 let substitution = Substitution::from_iter(
1030 .chain(super_trait_ref.substitution.iter(Interner)),
1032 let projection_ty = ProjectionTy {
1033 associated_ty_id: to_assoc_type_id(associated_ty),
1036 let mut preds: SmallVec<[_; 1]> = SmallVec::with_capacity(
1037 binding.type_ref.as_ref().map_or(0, |_| 1) + binding.bounds.len(),
1039 if let Some(type_ref) = &binding.type_ref {
1040 let ty = self.lower_ty(type_ref);
1042 AliasEq { alias: AliasTy::Projection(projection_ty.clone()), ty };
1043 preds.push(crate::wrap_empty_binders(WhereClause::AliasEq(alias_eq)));
1045 for bound in &binding.bounds {
1046 preds.extend(self.lower_type_bound(
1048 TyKind::Alias(AliasTy::Projection(projection_ty.clone())).intern(Interner),
1056 fn lower_dyn_trait(&self, bounds: &[Interned<TypeBound>]) -> Ty {
1057 let self_ty = TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(Interner);
1058 // INVARIANT: The principal trait bound, if present, must come first. Others may be in any
1059 // order but should be in the same order for the same set but possibly different order of
1060 // bounds in the input.
1061 // INVARIANT: If this function returns `DynTy`, there should be at least one trait bound.
1062 // These invariants are utilized by `TyExt::dyn_trait()` and chalk.
1063 let bounds = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
1064 let mut bounds: Vec<_> = bounds
1066 .flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false))
1069 let mut multiple_regular_traits = false;
1070 let mut multiple_same_projection = false;
1071 bounds.sort_unstable_by(|lhs, rhs| {
1072 use std::cmp::Ordering;
1073 match (lhs.skip_binders(), rhs.skip_binders()) {
1074 (WhereClause::Implemented(lhs), WhereClause::Implemented(rhs)) => {
1075 let lhs_id = lhs.trait_id;
1076 let lhs_is_auto = ctx.db.trait_data(from_chalk_trait_id(lhs_id)).is_auto;
1077 let rhs_id = rhs.trait_id;
1078 let rhs_is_auto = ctx.db.trait_data(from_chalk_trait_id(rhs_id)).is_auto;
1080 if !lhs_is_auto && !rhs_is_auto {
1081 multiple_regular_traits = true;
1083 // Note that the ordering here is important; this ensures the invariant
1085 (lhs_is_auto, lhs_id).cmp(&(rhs_is_auto, rhs_id))
1087 (WhereClause::Implemented(_), _) => Ordering::Less,
1088 (_, WhereClause::Implemented(_)) => Ordering::Greater,
1089 (WhereClause::AliasEq(lhs), WhereClause::AliasEq(rhs)) => {
1090 match (&lhs.alias, &rhs.alias) {
1091 (AliasTy::Projection(lhs_proj), AliasTy::Projection(rhs_proj)) => {
1092 // We only compare the `associated_ty_id`s. We shouldn't have
1093 // multiple bounds for an associated type in the correct Rust code,
1094 // and if we do, we error out.
1095 if lhs_proj.associated_ty_id == rhs_proj.associated_ty_id {
1096 multiple_same_projection = true;
1098 lhs_proj.associated_ty_id.cmp(&rhs_proj.associated_ty_id)
1100 // We don't produce `AliasTy::Opaque`s yet.
1101 _ => unreachable!(),
1104 // We don't produce `WhereClause::{TypeOutlives, LifetimeOutlives}` yet.
1105 _ => unreachable!(),
1109 if multiple_regular_traits || multiple_same_projection {
1113 if bounds.first().and_then(|b| b.trait_id()).is_none() {
1114 // When there's no trait bound, that's an error. This happens when the trait refs
1119 // As multiple occurrences of the same auto traits *are* permitted, we dedulicate the
1120 // bounds. We shouldn't have repeated elements besides auto traits at this point.
1123 Some(QuantifiedWhereClauses::from_iter(Interner, bounds))
1126 if let Some(bounds) = bounds {
1127 let bounds = crate::make_single_type_binders(bounds);
1128 TyKind::Dyn(DynTy { bounds, lifetime: static_lifetime() }).intern(Interner)
1130 // FIXME: report error
1131 // (additional non-auto traits, associated type rebound, or no resolved trait)
1132 TyKind::Error.intern(Interner)
1136 fn lower_impl_trait(
1138 bounds: &[Interned<TypeBound>],
1140 ) -> ReturnTypeImplTrait {
1141 cov_mark::hit!(lower_rpit);
1142 let self_ty = TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(Interner);
1143 let predicates = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
1144 let mut predicates: Vec<_> = bounds
1146 .flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false))
1149 if !ctx.unsized_types.borrow().contains(&self_ty) {
1150 let krate = func.lookup(ctx.db.upcast()).module(ctx.db.upcast()).krate();
1151 let sized_trait = ctx
1153 .lang_item(krate, SmolStr::new_inline("sized"))
1154 .and_then(|lang_item| lang_item.as_trait().map(to_chalk_trait_id));
1155 let sized_clause = sized_trait.map(|trait_id| {
1156 let clause = WhereClause::Implemented(TraitRef {
1158 substitution: Substitution::from1(Interner, self_ty.clone()),
1160 crate::wrap_empty_binders(clause)
1162 predicates.extend(sized_clause.into_iter());
1163 predicates.shrink_to_fit();
1167 ReturnTypeImplTrait { bounds: crate::make_single_type_binders(predicates) }
1171 fn count_impl_traits(type_ref: &TypeRef) -> usize {
1173 type_ref.walk(&mut |type_ref| {
1174 if matches!(type_ref, TypeRef::ImplTrait(_)) {
1181 /// Build the signature of a callable item (function, struct or enum variant).
1182 pub(crate) fn callable_item_sig(db: &dyn HirDatabase, def: CallableDefId) -> PolyFnSig {
1184 CallableDefId::FunctionId(f) => fn_sig_for_fn(db, f),
1185 CallableDefId::StructId(s) => fn_sig_for_struct_constructor(db, s),
1186 CallableDefId::EnumVariantId(e) => fn_sig_for_enum_variant_constructor(db, e),
1190 pub fn associated_type_shorthand_candidates<R>(
1191 db: &dyn HirDatabase,
1194 mut cb: impl FnMut(&Name, TypeAliasId) -> Option<R>,
1196 named_associated_type_shorthand_candidates(db, def, res, None, |name, _, id| cb(name, id))
1199 fn named_associated_type_shorthand_candidates<R>(
1200 db: &dyn HirDatabase,
1201 // If the type parameter is defined in an impl and we're in a method, there
1202 // might be additional where clauses to consider
1205 assoc_name: Option<Name>,
1206 // Do NOT let `cb` touch `TraitRef` outside of `TyLoweringContext`. Its substitution contains
1207 // free `BoundVar`s that need to be shifted and only `TyLoweringContext` knows how to do that
1208 // properly (see `TyLoweringContext::select_associated_type()`).
1209 mut cb: impl FnMut(&Name, &TraitRef, TypeAliasId) -> Option<R>,
1211 let mut search = |t| {
1212 for t in all_super_trait_refs(db, t) {
1213 let data = db.trait_data(t.hir_trait_id());
1215 for (name, assoc_id) in &data.items {
1216 if let AssocItemId::TypeAliasId(alias) = assoc_id {
1217 if let Some(result) = cb(name, &t, *alias) {
1218 return Some(result);
1227 TypeNs::SelfType(impl_id) => {
1228 // we're _in_ the impl -- the binders get added back later. Correct,
1229 // but it would be nice to make this more explicit
1230 let trait_ref = db.impl_trait(impl_id)?.into_value_and_skipped_binders().0;
1232 let impl_id_as_generic_def: GenericDefId = impl_id.into();
1233 if impl_id_as_generic_def != def {
1234 // `trait_ref` contains `BoundVar`s bound by impl's `Binders`, but here we need
1235 // `BoundVar`s from `def`'s point of view.
1236 // FIXME: A `HirDatabase` query may be handy if this process is needed in more
1237 // places. It'd be almost identical as `impl_trait_query` where `resolver` would be
1238 // of `def` instead of `impl_id`.
1239 let starting_idx = generics(db.upcast(), def).len_self();
1240 let subst = TyBuilder::subst_for_def(db, impl_id, None)
1241 .fill_with_bound_vars(DebruijnIndex::INNERMOST, starting_idx)
1243 let trait_ref = subst.apply(trait_ref, Interner);
1249 TypeNs::GenericParam(param_id) => {
1250 let predicates = db.generic_predicates_for_param(def, param_id.into(), assoc_name);
1251 let res = predicates.iter().find_map(|pred| match pred.skip_binders().skip_binders() {
1252 // FIXME: how to correctly handle higher-ranked bounds here?
1253 WhereClause::Implemented(tr) => search(
1255 .shifted_out_to(Interner, DebruijnIndex::ONE)
1256 .expect("FIXME unexpected higher-ranked trait bound"),
1260 if let Some(_) = res {
1263 // Handle `Self::Type` referring to own associated type in trait definitions
1264 if let GenericDefId::TraitId(trait_id) = param_id.parent() {
1265 let trait_generics = generics(db.upcast(), trait_id.into());
1266 if trait_generics.params.type_or_consts[param_id.local_id()].is_trait_self() {
1267 let def_generics = generics(db.upcast(), def);
1268 let starting_idx = match def {
1269 GenericDefId::TraitId(_) => 0,
1270 // `def` is an item within trait. We need to substitute `BoundVar`s but
1271 // remember that they are for parent (i.e. trait) generic params so they
1272 // come after our own params.
1273 _ => def_generics.len_self(),
1275 let trait_ref = TyBuilder::trait_ref(db, trait_id)
1276 .fill_with_bound_vars(DebruijnIndex::INNERMOST, starting_idx)
1278 return search(trait_ref);
1287 /// Build the type of all specific fields of a struct or enum variant.
1288 pub(crate) fn field_types_query(
1289 db: &dyn HirDatabase,
1290 variant_id: VariantId,
1291 ) -> Arc<ArenaMap<LocalFieldId, Binders<Ty>>> {
1292 let var_data = variant_id.variant_data(db.upcast());
1293 let (resolver, def): (_, GenericDefId) = match variant_id {
1294 VariantId::StructId(it) => (it.resolver(db.upcast()), it.into()),
1295 VariantId::UnionId(it) => (it.resolver(db.upcast()), it.into()),
1296 VariantId::EnumVariantId(it) => (it.parent.resolver(db.upcast()), it.parent.into()),
1298 let generics = generics(db.upcast(), def);
1299 let mut res = ArenaMap::default();
1301 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1302 for (field_id, field_data) in var_data.fields().iter() {
1303 res.insert(field_id, make_binders(db, &generics, ctx.lower_ty(&field_data.type_ref)));
1308 /// This query exists only to be used when resolving short-hand associated types
1311 /// See the analogous query in rustc and its comment:
1312 /// <https://github.com/rust-lang/rust/blob/9150f844e2624eb013ec78ca08c1d416e6644026/src/librustc_typeck/astconv.rs#L46>
1313 /// This is a query mostly to handle cycles somewhat gracefully; e.g. the
1314 /// following bounds are disallowed: `T: Foo<U::Item>, U: Foo<T::Item>`, but
1315 /// these are fine: `T: Foo<U::Item>, U: Foo<()>`.
1316 pub(crate) fn generic_predicates_for_param_query(
1317 db: &dyn HirDatabase,
1319 param_id: TypeOrConstParamId,
1320 assoc_name: Option<Name>,
1321 ) -> Arc<[Binders<QuantifiedWhereClause>]> {
1322 let resolver = def.resolver(db.upcast());
1324 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1325 let generics = generics(db.upcast(), def);
1326 let mut predicates: Vec<_> = resolver
1327 .where_predicates_in_scope()
1328 // we have to filter out all other predicates *first*, before attempting to lower them
1329 .filter(|pred| match pred {
1330 WherePredicate::ForLifetime { target, bound, .. }
1331 | WherePredicate::TypeBound { target, bound, .. } => {
1333 WherePredicateTypeTarget::TypeRef(type_ref) => {
1334 if ctx.lower_ty_only_param(type_ref) != Some(param_id) {
1338 &WherePredicateTypeTarget::TypeOrConstParam(local_id) => {
1339 let target_id = TypeOrConstParamId { parent: def, local_id };
1340 if target_id != param_id {
1347 TypeBound::ForLifetime(_, path) | TypeBound::Path(path, _) => {
1348 // Only lower the bound if the trait could possibly define the associated
1349 // type we're looking for.
1351 let assoc_name = match &assoc_name {
1353 None => return true,
1355 let tr = match resolver
1356 .resolve_path_in_type_ns_fully(db.upcast(), path.mod_path())
1358 Some(TypeNs::TraitId(tr)) => tr,
1362 all_super_traits(db.upcast(), tr).iter().any(|tr| {
1363 db.trait_data(*tr).items.iter().any(|(name, item)| {
1364 matches!(item, AssocItemId::TypeAliasId(_)) && name == assoc_name
1368 TypeBound::Lifetime(_) | TypeBound::Error => false,
1371 WherePredicate::Lifetime { .. } => false,
1374 ctx.lower_where_predicate(pred, true).map(|p| make_binders(db, &generics, p))
1378 let subst = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1379 let explicitly_unsized_tys = ctx.unsized_types.into_inner();
1380 let implicitly_sized_predicates =
1381 implicitly_sized_clauses(db, param_id.parent, &explicitly_unsized_tys, &subst, &resolver)
1382 .map(|p| make_binders(db, &generics, crate::wrap_empty_binders(p)));
1383 predicates.extend(implicitly_sized_predicates);
1387 pub(crate) fn generic_predicates_for_param_recover(
1388 _db: &dyn HirDatabase,
1390 _def: &GenericDefId,
1391 _param_id: &TypeOrConstParamId,
1392 _assoc_name: &Option<Name>,
1393 ) -> Arc<[Binders<QuantifiedWhereClause>]> {
1397 pub(crate) fn trait_environment_query(
1398 db: &dyn HirDatabase,
1400 ) -> Arc<TraitEnvironment> {
1401 let resolver = def.resolver(db.upcast());
1403 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Placeholder);
1404 let mut traits_in_scope = Vec::new();
1405 let mut clauses = Vec::new();
1406 for pred in resolver.where_predicates_in_scope() {
1407 for pred in ctx.lower_where_predicate(pred, false) {
1408 if let WhereClause::Implemented(tr) = &pred.skip_binders() {
1409 traits_in_scope.push((tr.self_type_parameter(Interner).clone(), tr.hir_trait_id()));
1411 let program_clause: chalk_ir::ProgramClause<Interner> = pred.cast(Interner);
1412 clauses.push(program_clause.into_from_env_clause(Interner));
1416 let container: Option<ItemContainerId> = match def {
1417 // FIXME: is there a function for this?
1418 GenericDefId::FunctionId(f) => Some(f.lookup(db.upcast()).container),
1419 GenericDefId::AdtId(_) => None,
1420 GenericDefId::TraitId(_) => None,
1421 GenericDefId::TypeAliasId(t) => Some(t.lookup(db.upcast()).container),
1422 GenericDefId::ImplId(_) => None,
1423 GenericDefId::EnumVariantId(_) => None,
1424 GenericDefId::ConstId(c) => Some(c.lookup(db.upcast()).container),
1426 if let Some(ItemContainerId::TraitId(trait_id)) = container {
1427 // add `Self: Trait<T1, T2, ...>` to the environment in trait
1428 // function default implementations (and speculative code
1429 // inside consts or type aliases)
1430 cov_mark::hit!(trait_self_implements_self);
1431 let substs = TyBuilder::placeholder_subst(db, trait_id);
1432 let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution: substs };
1433 let pred = WhereClause::Implemented(trait_ref);
1434 let program_clause: chalk_ir::ProgramClause<Interner> = pred.cast(Interner);
1435 clauses.push(program_clause.into_from_env_clause(Interner));
1438 let subst = generics(db.upcast(), def).placeholder_subst(db);
1439 let explicitly_unsized_tys = ctx.unsized_types.into_inner();
1440 let implicitly_sized_clauses =
1441 implicitly_sized_clauses(db, def, &explicitly_unsized_tys, &subst, &resolver).map(|pred| {
1442 let program_clause: chalk_ir::ProgramClause<Interner> = pred.cast(Interner);
1443 program_clause.into_from_env_clause(Interner)
1445 clauses.extend(implicitly_sized_clauses);
1447 let krate = def.module(db.upcast()).krate();
1449 let env = chalk_ir::Environment::new(Interner).add_clauses(Interner, clauses);
1451 Arc::new(TraitEnvironment { krate, traits_from_clauses: traits_in_scope, env })
1454 /// Resolve the where clause(s) of an item with generics.
1455 pub(crate) fn generic_predicates_query(
1456 db: &dyn HirDatabase,
1458 ) -> Arc<[Binders<QuantifiedWhereClause>]> {
1459 let resolver = def.resolver(db.upcast());
1461 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1462 let generics = generics(db.upcast(), def);
1464 let mut predicates = resolver
1465 .where_predicates_in_scope()
1467 ctx.lower_where_predicate(pred, false).map(|p| make_binders(db, &generics, p))
1469 .collect::<Vec<_>>();
1471 let subst = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1472 let explicitly_unsized_tys = ctx.unsized_types.into_inner();
1473 let implicitly_sized_predicates =
1474 implicitly_sized_clauses(db, def, &explicitly_unsized_tys, &subst, &resolver)
1475 .map(|p| make_binders(db, &generics, crate::wrap_empty_binders(p)));
1476 predicates.extend(implicitly_sized_predicates);
1480 /// Generate implicit `: Sized` predicates for all generics that has no `?Sized` bound.
1481 /// Exception is Self of a trait def.
1482 fn implicitly_sized_clauses<'a>(
1483 db: &dyn HirDatabase,
1485 explicitly_unsized_tys: &'a FxHashSet<Ty>,
1486 substitution: &'a Substitution,
1487 resolver: &Resolver,
1488 ) -> impl Iterator<Item = WhereClause> + 'a {
1489 let is_trait_def = matches!(def, GenericDefId::TraitId(..));
1490 let generic_args = &substitution.as_slice(Interner)[is_trait_def as usize..];
1491 let sized_trait = db
1492 .lang_item(resolver.krate(), SmolStr::new_inline("sized"))
1493 .and_then(|lang_item| lang_item.as_trait().map(to_chalk_trait_id));
1495 sized_trait.into_iter().flat_map(move |sized_trait| {
1496 let implicitly_sized_tys = generic_args
1498 .filter_map(|generic_arg| generic_arg.ty(Interner))
1499 .filter(move |&self_ty| !explicitly_unsized_tys.contains(self_ty));
1500 implicitly_sized_tys.map(move |self_ty| {
1501 WhereClause::Implemented(TraitRef {
1502 trait_id: sized_trait,
1503 substitution: Substitution::from1(Interner, self_ty.clone()),
1509 /// Resolve the default type params from generics
1510 pub(crate) fn generic_defaults_query(
1511 db: &dyn HirDatabase,
1513 ) -> Arc<[Binders<chalk_ir::GenericArg<Interner>>]> {
1514 let resolver = def.resolver(db.upcast());
1516 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1517 let generic_params = generics(db.upcast(), def);
1518 let parent_start_idx = generic_params.len_self();
1520 let defaults = generic_params
1523 .map(|(idx, (id, p))| {
1525 TypeOrConstParamData::TypeParamData(p) => p,
1526 TypeOrConstParamData::ConstParamData(_) => {
1527 // FIXME: implement const generic defaults
1528 let val = unknown_const_as_generic(
1529 db.const_param_ty(ConstParamId::from_unchecked(id)),
1531 return make_binders(db, &generic_params, val);
1535 p.default.as_ref().map_or(TyKind::Error.intern(Interner), |t| ctx.lower_ty(t));
1537 // Each default can only refer to previous parameters.
1538 // Type variable default referring to parameter coming
1539 // after it is forbidden (FIXME: report diagnostic)
1540 ty = fallback_bound_vars(ty, idx, parent_start_idx);
1541 crate::make_binders(db, &generic_params, ty.cast(Interner))
1548 pub(crate) fn generic_defaults_recover(
1549 db: &dyn HirDatabase,
1552 ) -> Arc<[Binders<crate::GenericArg>]> {
1553 let generic_params = generics(db.upcast(), *def);
1554 // FIXME: this code is not covered in tests.
1555 // we still need one default per parameter
1556 let defaults = generic_params
1559 let val = match id {
1560 itertools::Either::Left(_) => {
1561 GenericArgData::Ty(TyKind::Error.intern(Interner)).intern(Interner)
1563 itertools::Either::Right(id) => unknown_const_as_generic(db.const_param_ty(id)),
1565 crate::make_binders(db, &generic_params, val)
1572 fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
1573 let data = db.function_data(def);
1574 let resolver = def.resolver(db.upcast());
1575 let ctx_params = TyLoweringContext::new(db, &resolver)
1576 .with_impl_trait_mode(ImplTraitLoweringMode::Variable)
1577 .with_type_param_mode(ParamLoweringMode::Variable);
1578 let params = data.params.iter().map(|(_, tr)| ctx_params.lower_ty(tr)).collect::<Vec<_>>();
1579 let ctx_ret = TyLoweringContext::new(db, &resolver)
1580 .with_impl_trait_mode(ImplTraitLoweringMode::Opaque)
1581 .with_type_param_mode(ParamLoweringMode::Variable);
1582 let ret = ctx_ret.lower_ty(&data.ret_type);
1583 let generics = generics(db.upcast(), def.into());
1584 let sig = CallableSig::from_params_and_return(
1588 if data.has_unsafe_kw() { Safety::Unsafe } else { Safety::Safe },
1590 make_binders(db, &generics, sig)
1593 /// Build the declared type of a function. This should not need to look at the
1595 fn type_for_fn(db: &dyn HirDatabase, def: FunctionId) -> Binders<Ty> {
1596 let generics = generics(db.upcast(), def.into());
1597 let substs = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1601 TyKind::FnDef(CallableDefId::FunctionId(def).to_chalk(db), substs).intern(Interner),
1605 /// Build the declared type of a const.
1606 fn type_for_const(db: &dyn HirDatabase, def: ConstId) -> Binders<Ty> {
1607 let data = db.const_data(def);
1608 let generics = generics(db.upcast(), def.into());
1609 let resolver = def.resolver(db.upcast());
1611 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1613 make_binders(db, &generics, ctx.lower_ty(&data.type_ref))
1616 /// Build the declared type of a static.
1617 fn type_for_static(db: &dyn HirDatabase, def: StaticId) -> Binders<Ty> {
1618 let data = db.static_data(def);
1619 let resolver = def.resolver(db.upcast());
1620 let ctx = TyLoweringContext::new(db, &resolver);
1622 Binders::empty(Interner, ctx.lower_ty(&data.type_ref))
1625 fn fn_sig_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> PolyFnSig {
1626 let struct_data = db.struct_data(def);
1627 let fields = struct_data.variant_data.fields();
1628 let resolver = def.resolver(db.upcast());
1630 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1631 let params = fields.iter().map(|(_, field)| ctx.lower_ty(&field.type_ref)).collect::<Vec<_>>();
1632 let (ret, binders) = type_for_adt(db, def.into()).into_value_and_skipped_binders();
1633 Binders::new(binders, CallableSig::from_params_and_return(params, ret, false, Safety::Safe))
1636 /// Build the type of a tuple struct constructor.
1637 fn type_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> Binders<Ty> {
1638 let struct_data = db.struct_data(def);
1639 if let StructKind::Unit = struct_data.variant_data.kind() {
1640 return type_for_adt(db, def.into());
1642 let generics = generics(db.upcast(), def.into());
1643 let substs = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1647 TyKind::FnDef(CallableDefId::StructId(def).to_chalk(db), substs).intern(Interner),
1651 fn fn_sig_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -> PolyFnSig {
1652 let enum_data = db.enum_data(def.parent);
1653 let var_data = &enum_data.variants[def.local_id];
1654 let fields = var_data.variant_data.fields();
1655 let resolver = def.parent.resolver(db.upcast());
1657 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1658 let params = fields.iter().map(|(_, field)| ctx.lower_ty(&field.type_ref)).collect::<Vec<_>>();
1659 let (ret, binders) = type_for_adt(db, def.parent.into()).into_value_and_skipped_binders();
1660 Binders::new(binders, CallableSig::from_params_and_return(params, ret, false, Safety::Safe))
1663 /// Build the type of a tuple enum variant constructor.
1664 fn type_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -> Binders<Ty> {
1665 let enum_data = db.enum_data(def.parent);
1666 let var_data = &enum_data.variants[def.local_id].variant_data;
1667 if let StructKind::Unit = var_data.kind() {
1668 return type_for_adt(db, def.parent.into());
1670 let generics = generics(db.upcast(), def.parent.into());
1671 let substs = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1675 TyKind::FnDef(CallableDefId::EnumVariantId(def).to_chalk(db), substs).intern(Interner),
1679 fn type_for_adt(db: &dyn HirDatabase, adt: AdtId) -> Binders<Ty> {
1680 let generics = generics(db.upcast(), adt.into());
1681 let subst = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1682 let ty = TyKind::Adt(crate::AdtId(adt), subst).intern(Interner);
1683 make_binders(db, &generics, ty)
1686 fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders<Ty> {
1687 let generics = generics(db.upcast(), t.into());
1688 let resolver = t.resolver(db.upcast());
1690 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1691 if db.type_alias_data(t).is_extern {
1692 Binders::empty(Interner, TyKind::Foreign(crate::to_foreign_def_id(t)).intern(Interner))
1694 let type_ref = &db.type_alias_data(t).type_ref;
1695 let inner = ctx.lower_ty(type_ref.as_deref().unwrap_or(&TypeRef::Error));
1696 make_binders(db, &generics, inner)
1700 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
1701 pub enum CallableDefId {
1702 FunctionId(FunctionId),
1704 EnumVariantId(EnumVariantId),
1706 impl_from!(FunctionId, StructId, EnumVariantId for CallableDefId);
1708 impl CallableDefId {
1709 pub fn krate(self, db: &dyn HirDatabase) -> CrateId {
1710 let db = db.upcast();
1712 CallableDefId::FunctionId(f) => f.lookup(db).module(db),
1713 CallableDefId::StructId(s) => s.lookup(db).container,
1714 CallableDefId::EnumVariantId(e) => e.parent.lookup(db).container,
1720 impl From<CallableDefId> for GenericDefId {
1721 fn from(def: CallableDefId) -> GenericDefId {
1723 CallableDefId::FunctionId(f) => f.into(),
1724 CallableDefId::StructId(s) => s.into(),
1725 CallableDefId::EnumVariantId(e) => e.into(),
1730 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1732 BuiltinType(BuiltinType),
1734 TypeAliasId(TypeAliasId),
1736 impl_from!(BuiltinType, AdtId(StructId, EnumId, UnionId), TypeAliasId for TyDefId);
1738 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1739 pub enum ValueTyDefId {
1740 FunctionId(FunctionId),
1743 EnumVariantId(EnumVariantId),
1747 impl_from!(FunctionId, StructId, UnionId, EnumVariantId, ConstId, StaticId for ValueTyDefId);
1750 pub(crate) fn to_generic_def_id(self) -> Option<GenericDefId> {
1752 Self::FunctionId(id) => Some(id.into()),
1753 Self::StructId(id) => Some(id.into()),
1754 Self::UnionId(id) => Some(id.into()),
1755 Self::EnumVariantId(var) => Some(var.into()),
1756 Self::ConstId(id) => Some(id.into()),
1757 Self::StaticId(_) => None,
1762 /// Build the declared type of an item. This depends on the namespace; e.g. for
1763 /// `struct Foo(usize)`, we have two types: The type of the struct itself, and
1764 /// the constructor function `(usize) -> Foo` which lives in the values
1766 pub(crate) fn ty_query(db: &dyn HirDatabase, def: TyDefId) -> Binders<Ty> {
1768 TyDefId::BuiltinType(it) => Binders::empty(Interner, TyBuilder::builtin(it)),
1769 TyDefId::AdtId(it) => type_for_adt(db, it),
1770 TyDefId::TypeAliasId(it) => type_for_type_alias(db, it),
1774 pub(crate) fn ty_recover(db: &dyn HirDatabase, _cycle: &[String], def: &TyDefId) -> Binders<Ty> {
1775 let generics = match *def {
1776 TyDefId::BuiltinType(_) => return Binders::empty(Interner, TyKind::Error.intern(Interner)),
1777 TyDefId::AdtId(it) => generics(db.upcast(), it.into()),
1778 TyDefId::TypeAliasId(it) => generics(db.upcast(), it.into()),
1780 make_binders(db, &generics, TyKind::Error.intern(Interner))
1783 pub(crate) fn value_ty_query(db: &dyn HirDatabase, def: ValueTyDefId) -> Binders<Ty> {
1785 ValueTyDefId::FunctionId(it) => type_for_fn(db, it),
1786 ValueTyDefId::StructId(it) => type_for_struct_constructor(db, it),
1787 ValueTyDefId::UnionId(it) => type_for_adt(db, it.into()),
1788 ValueTyDefId::EnumVariantId(it) => type_for_enum_variant_constructor(db, it),
1789 ValueTyDefId::ConstId(it) => type_for_const(db, it),
1790 ValueTyDefId::StaticId(it) => type_for_static(db, it),
1794 pub(crate) fn impl_self_ty_query(db: &dyn HirDatabase, impl_id: ImplId) -> Binders<Ty> {
1795 let impl_loc = impl_id.lookup(db.upcast());
1796 let impl_data = db.impl_data(impl_id);
1797 let resolver = impl_id.resolver(db.upcast());
1798 let _cx = stdx::panic_context::enter(format!(
1799 "impl_self_ty_query({impl_id:?} -> {impl_loc:?} -> {impl_data:?})"
1801 let generics = generics(db.upcast(), impl_id.into());
1803 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1804 make_binders(db, &generics, ctx.lower_ty(&impl_data.self_ty))
1807 // returns None if def is a type arg
1808 pub(crate) fn const_param_ty_query(db: &dyn HirDatabase, def: ConstParamId) -> Ty {
1809 let parent_data = db.generic_params(def.parent());
1810 let data = &parent_data.type_or_consts[def.local_id()];
1811 let resolver = def.parent().resolver(db.upcast());
1812 let ctx = TyLoweringContext::new(db, &resolver);
1814 TypeOrConstParamData::TypeParamData(_) => {
1816 Ty::new(Interner, TyKind::Error)
1818 TypeOrConstParamData::ConstParamData(d) => ctx.lower_ty(&d.ty),
1822 pub(crate) fn impl_self_ty_recover(
1823 db: &dyn HirDatabase,
1827 let generics = generics(db.upcast(), (*impl_id).into());
1828 make_binders(db, &generics, TyKind::Error.intern(Interner))
1831 pub(crate) fn impl_trait_query(db: &dyn HirDatabase, impl_id: ImplId) -> Option<Binders<TraitRef>> {
1832 let impl_loc = impl_id.lookup(db.upcast());
1833 let impl_data = db.impl_data(impl_id);
1834 let resolver = impl_id.resolver(db.upcast());
1835 let _cx = stdx::panic_context::enter(format!(
1836 "impl_trait_query({impl_id:?} -> {impl_loc:?} -> {impl_data:?})"
1839 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1840 let (self_ty, binders) = db.impl_self_ty(impl_id).into_value_and_skipped_binders();
1841 let target_trait = impl_data.target_trait.as_ref()?;
1842 Some(Binders::new(binders, ctx.lower_trait_ref(target_trait, Some(self_ty))?))
1845 pub(crate) fn return_type_impl_traits(
1846 db: &dyn HirDatabase,
1847 def: hir_def::FunctionId,
1848 ) -> Option<Arc<Binders<ReturnTypeImplTraits>>> {
1849 // FIXME unify with fn_sig_for_fn instead of doing lowering twice, maybe
1850 let data = db.function_data(def);
1851 let resolver = def.resolver(db.upcast());
1852 let ctx_ret = TyLoweringContext::new(db, &resolver)
1853 .with_impl_trait_mode(ImplTraitLoweringMode::Opaque)
1854 .with_type_param_mode(ParamLoweringMode::Variable);
1855 let _ret = ctx_ret.lower_ty(&data.ret_type);
1856 let generics = generics(db.upcast(), def.into());
1857 let return_type_impl_traits =
1858 ReturnTypeImplTraits { impl_traits: ctx_ret.opaque_type_data.into_inner() };
1859 if return_type_impl_traits.impl_traits.is_empty() {
1862 Some(Arc::new(make_binders(db, &generics, return_type_impl_traits)))
1866 pub(crate) fn lower_to_chalk_mutability(m: hir_def::type_ref::Mutability) -> Mutability {
1868 hir_def::type_ref::Mutability::Shared => Mutability::Not,
1869 hir_def::type_ref::Mutability::Mut => Mutability::Mut,
1873 /// Checks if the provided generic arg matches its expected kind, then lower them via
1874 /// provided closures. Use unknown if there was kind mismatch.
1876 /// Returns `Some` of the lowered generic arg. `None` if the provided arg is a lifetime.
1877 pub(crate) fn generic_arg_to_chalk<'a, T>(
1878 db: &dyn HirDatabase,
1879 kind_id: Either<TypeParamId, ConstParamId>,
1880 arg: &'a GenericArg,
1882 for_type: impl FnOnce(&mut T, &TypeRef) -> Ty + 'a,
1883 for_const: impl FnOnce(&mut T, &ConstScalarOrPath, Ty) -> Const + 'a,
1884 ) -> Option<crate::GenericArg> {
1885 let kind = match kind_id {
1886 Either::Left(_) => ParamKind::Type,
1887 Either::Right(id) => {
1888 let ty = db.const_param_ty(id);
1889 ParamKind::Const(ty)
1892 Some(match (arg, kind) {
1893 (GenericArg::Type(type_ref), ParamKind::Type) => {
1894 let ty = for_type(this, type_ref);
1895 GenericArgData::Ty(ty).intern(Interner)
1897 (GenericArg::Const(c), ParamKind::Const(c_ty)) => {
1898 GenericArgData::Const(for_const(this, c, c_ty)).intern(Interner)
1900 (GenericArg::Const(_), ParamKind::Type) => {
1901 GenericArgData::Ty(TyKind::Error.intern(Interner)).intern(Interner)
1903 (GenericArg::Type(t), ParamKind::Const(c_ty)) => {
1904 // We want to recover simple idents, which parser detects them
1905 // as types. Maybe here is not the best place to do it, but
1907 if let TypeRef::Path(p) = t {
1908 let p = p.mod_path();
1909 if p.kind == PathKind::Plain {
1910 if let [n] = p.segments() {
1911 let c = ConstScalarOrPath::Path(n.clone());
1913 GenericArgData::Const(for_const(this, &c, c_ty)).intern(Interner),
1918 unknown_const_as_generic(c_ty)
1920 (GenericArg::Lifetime(_), _) => return None,
1924 pub(crate) fn const_or_path_to_chalk(
1925 db: &dyn HirDatabase,
1926 resolver: &Resolver,
1928 value: &ConstScalarOrPath,
1929 mode: ParamLoweringMode,
1930 args: impl FnOnce() -> Generics,
1931 debruijn: DebruijnIndex,
1934 ConstScalarOrPath::Scalar(s) => intern_const_scalar(s.clone(), expected_ty),
1935 ConstScalarOrPath::Path(n) => {
1936 let path = ModPath::from_segments(PathKind::Plain, Some(n.clone()));
1937 path_to_const(db, resolver, &path, mode, args, debruijn)
1938 .unwrap_or_else(|| unknown_const(expected_ty))
1943 /// Replaces any 'free' `BoundVar`s in `s` by `TyKind::Error` from the perspective of generic
1944 /// parameter whose index is `param_index`. A `BoundVar` is free when it is or (syntactically)
1945 /// appears after the generic parameter of `param_index`.
1946 fn fallback_bound_vars<T: TypeFoldable<Interner> + HasInterner<Interner = Interner>>(
1949 parent_start: usize,
1951 // Keep in mind that parent generic parameters, if any, come *after* those of the item in
1952 // question. In the diagrams below, `c*` and `p*` represent generic parameters of the item and
1953 // its parent respectively.
1954 let is_allowed = |index| {
1955 if param_index < parent_start {
1956 // The parameter of `param_index` is one from the item in question. Any parent generic
1957 // parameters or the item's generic parameters that come before `param_index` is
1959 // [c1, .., cj, .., ck, p1, .., pl] where cj is `param_index`
1960 // ^^^^^^ ^^^^^^^^^^ these are allowed
1961 !(param_index..parent_start).contains(&index)
1963 // The parameter of `param_index` is one from the parent generics. Only parent generic
1964 // parameters that come before `param_index` are allowed.
1965 // [c1, .., ck, p1, .., pj, .., pl] where pj is `param_index`
1966 // ^^^^^^ these are allowed
1967 (parent_start..param_index).contains(&index)
1971 crate::fold_free_vars(
1974 if bound.index_if_innermost().map_or(true, is_allowed) {
1975 bound.shifted_in_from(binders).to_ty(Interner)
1977 TyKind::Error.intern(Interner)
1980 |ty, bound, binders| {
1981 if bound.index_if_innermost().map_or(true, is_allowed) {
1982 bound.shifted_in_from(binders).to_const(Interner, ty)