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 (def, res) = match (self.resolver.generic_def(), res) {
607 (Some(def), Some(res)) => (def, res),
608 _ => return TyKind::Error.intern(Interner),
610 let ty = named_associated_type_shorthand_candidates(
614 Some(segment.name.clone()),
615 move |name, t, associated_ty| {
616 if name != segment.name {
620 // FIXME: `substs_from_path_segment()` pushes `TyKind::Error` for every parent
621 // generic params. It's inefficient to splice the `Substitution`s, so we may want
622 // that method to optionally take parent `Substitution` as we already know them at
623 // this point (`t.substitution`).
624 let substs = self.substs_from_path_segment(
626 Some(associated_ty.into()),
631 let len_self = generics(self.db.upcast(), associated_ty.into()).len_self();
633 let substs = Substitution::from_iter(
635 substs.iter(Interner).take(len_self).chain(t.substitution.iter(Interner)),
638 let substs = match self.type_param_mode {
639 ParamLoweringMode::Placeholder => {
640 // if we're lowering to placeholders, we have to put
642 let generics = generics(self.db.upcast(), def);
643 let s = generics.placeholder_subst(self.db);
644 s.apply(substs, Interner)
646 ParamLoweringMode::Variable => substs,
648 // We need to shift in the bound vars, since
649 // associated_type_shorthand_candidates does not do that
650 let substs = substs.shifted_in_from(Interner, self.in_binders);
652 TyKind::Alias(AliasTy::Projection(ProjectionTy {
653 associated_ty_id: to_assoc_type_id(associated_ty),
654 substitution: substs,
661 ty.unwrap_or_else(|| TyKind::Error.intern(Interner))
666 segment: PathSegment<'_>,
670 let generic_def = match typeable {
671 TyDefId::BuiltinType(_) => None,
672 TyDefId::AdtId(it) => Some(it.into()),
673 TyDefId::TypeAliasId(it) => Some(it.into()),
675 let substs = self.substs_from_path_segment(segment, generic_def, infer_args, None);
676 self.db.ty(typeable).substitute(Interner, &substs)
679 /// Collect generic arguments from a path into a `Substs`. See also
680 /// `create_substs_for_ast_path` and `def_to_ty` in rustc.
681 pub(super) fn substs_from_path(
684 // Note that we don't call `db.value_type(resolved)` here,
685 // `ValueTyDefId` is just a convenient way to pass generics and
686 // special-case enum variants
687 resolved: ValueTyDefId,
690 let last = path.segments().last().expect("path should have at least one segment");
691 let (segment, generic_def) = match resolved {
692 ValueTyDefId::FunctionId(it) => (last, Some(it.into())),
693 ValueTyDefId::StructId(it) => (last, Some(it.into())),
694 ValueTyDefId::UnionId(it) => (last, Some(it.into())),
695 ValueTyDefId::ConstId(it) => (last, Some(it.into())),
696 ValueTyDefId::StaticId(_) => (last, None),
697 ValueTyDefId::EnumVariantId(var) => {
698 // the generic args for an enum variant may be either specified
699 // on the segment referring to the enum, or on the segment
700 // referring to the variant. So `Option::<T>::None` and
701 // `Option::None::<T>` are both allowed (though the former is
702 // preferred). See also `def_ids_for_path_segments` in rustc.
703 let len = path.segments().len();
704 let penultimate = len.checked_sub(2).and_then(|idx| path.segments().get(idx));
705 let segment = match penultimate {
706 Some(segment) if segment.args_and_bindings.is_some() => segment,
709 (segment, Some(var.parent.into()))
712 self.substs_from_path_segment(segment, generic_def, infer_args, None)
715 fn substs_from_path_segment(
717 segment: PathSegment<'_>,
718 def: Option<GenericDefId>,
720 explicit_self_ty: Option<Ty>,
722 // Remember that the item's own generic args come before its parent's.
723 let mut substs = Vec::new();
724 let def = if let Some(d) = def {
727 return Substitution::empty(Interner);
729 let def_generics = generics(self.db.upcast(), def);
730 let (parent_params, self_params, type_params, const_params, impl_trait_params) =
731 def_generics.provenance_split();
732 let item_len = self_params + type_params + const_params + impl_trait_params;
733 let total_len = parent_params + item_len;
735 let ty_error = TyKind::Error.intern(Interner).cast(Interner);
737 let mut def_generic_iter = def_generics.iter_id();
739 let fill_self_params = || {
740 for x in explicit_self_ty
742 .map(|x| x.cast(Interner))
743 .chain(iter::repeat(ty_error.clone()))
746 if let Some(id) = def_generic_iter.next() {
747 assert!(id.is_left());
752 let mut had_explicit_args = false;
754 if let Some(generic_args) = &segment.args_and_bindings {
755 if !generic_args.has_self_type {
758 let expected_num = if generic_args.has_self_type {
759 self_params + type_params + const_params
761 type_params + const_params
763 let skip = if generic_args.has_self_type && self_params == 0 { 1 } else { 0 };
764 // if args are provided, it should be all of them, but we can't rely on that
765 for arg in generic_args
768 .filter(|arg| !matches!(arg, GenericArg::Lifetime(_)))
772 if let Some(id) = def_generic_iter.next() {
773 if let Some(x) = generic_arg_to_chalk(
778 |_, type_ref| self.lower_ty(type_ref),
780 const_or_path_to_chalk(
785 self.type_param_mode,
791 had_explicit_args = true;
794 // we just filtered them out
795 never!("Unexpected lifetime argument");
803 // These params include those of parent.
804 let remaining_params: SmallVec<[_; 2]> = def_generic_iter
805 .map(|eid| match eid {
806 Either::Left(_) => ty_error.clone(),
807 Either::Right(x) => unknown_const_as_generic(self.db.const_param_ty(x)),
810 assert_eq!(remaining_params.len() + substs.len(), total_len);
812 // handle defaults. In expression or pattern path segments without
813 // explicitly specified type arguments, missing type arguments are inferred
814 // (i.e. defaults aren't used).
815 // Generic parameters for associated types are not supposed to have defaults, so we just
817 let is_assoc_ty = if let GenericDefId::TypeAliasId(id) = def {
818 let container = id.lookup(self.db.upcast()).container;
819 matches!(container, ItemContainerId::TraitId(_))
823 if !is_assoc_ty && (!infer_args || had_explicit_args) {
824 let defaults = self.db.generic_defaults(def);
825 assert_eq!(total_len, defaults.len());
826 let parent_from = item_len - substs.len();
828 for (idx, default_ty) in defaults[substs.len()..item_len].iter().enumerate() {
829 // each default can depend on the previous parameters
830 let substs_so_far = Substitution::from_iter(
832 substs.iter().cloned().chain(remaining_params[idx..].iter().cloned()),
834 substs.push(default_ty.clone().substitute(Interner, &substs_so_far));
837 // Keep parent's params as unknown.
838 let mut remaining_params = remaining_params;
839 substs.extend(remaining_params.drain(parent_from..));
841 substs.extend(remaining_params);
844 assert_eq!(substs.len(), total_len);
845 Substitution::from_iter(Interner, substs)
848 fn lower_trait_ref_from_path(
851 explicit_self_ty: Option<Ty>,
852 ) -> Option<TraitRef> {
854 match self.resolver.resolve_path_in_type_ns_fully(self.db.upcast(), path.mod_path())? {
855 TypeNs::TraitId(tr) => tr,
858 let segment = path.segments().last().expect("path should have at least one segment");
859 Some(self.lower_trait_ref_from_resolved_path(resolved, segment, explicit_self_ty))
862 pub(crate) fn lower_trait_ref_from_resolved_path(
865 segment: PathSegment<'_>,
866 explicit_self_ty: Option<Ty>,
868 let substs = self.trait_ref_substs_from_path(segment, resolved, explicit_self_ty);
869 TraitRef { trait_id: to_chalk_trait_id(resolved), substitution: substs }
874 trait_ref: &HirTraitRef,
875 explicit_self_ty: Option<Ty>,
876 ) -> Option<TraitRef> {
877 self.lower_trait_ref_from_path(&trait_ref.path, explicit_self_ty)
880 fn trait_ref_substs_from_path(
882 segment: PathSegment<'_>,
884 explicit_self_ty: Option<Ty>,
886 self.substs_from_path_segment(segment, Some(resolved.into()), false, explicit_self_ty)
889 pub(crate) fn lower_where_predicate(
891 where_predicate: &'a WherePredicate,
892 ignore_bindings: bool,
893 ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
894 match where_predicate {
895 WherePredicate::ForLifetime { target, bound, .. }
896 | WherePredicate::TypeBound { target, bound } => {
897 let self_ty = match target {
898 WherePredicateTypeTarget::TypeRef(type_ref) => self.lower_ty(type_ref),
899 WherePredicateTypeTarget::TypeOrConstParam(param_id) => {
900 let generic_def = self.resolver.generic_def().expect("generics in scope");
901 let generics = generics(self.db.upcast(), generic_def);
902 let param_id = hir_def::TypeOrConstParamId {
906 let placeholder = to_placeholder_idx(self.db, param_id);
907 match self.type_param_mode {
908 ParamLoweringMode::Placeholder => TyKind::Placeholder(placeholder),
909 ParamLoweringMode::Variable => {
910 let idx = generics.param_idx(param_id).expect("matching generics");
911 TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, idx))
917 self.lower_type_bound(bound, self_ty, ignore_bindings)
921 WherePredicate::Lifetime { .. } => vec![].into_iter(),
925 pub(crate) fn lower_type_bound(
927 bound: &'a TypeBound,
929 ignore_bindings: bool,
930 ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
931 let mut bindings = None;
932 let trait_ref = match bound {
933 TypeBound::Path(path, TraitBoundModifier::None) => {
934 bindings = self.lower_trait_ref_from_path(path, Some(self_ty));
938 // ignore `T: Drop` or `T: Destruct` bounds.
939 // - `T: ~const Drop` has a special meaning in Rust 1.61 that we don't implement.
940 // (So ideally, we'd only ignore `~const Drop` here)
941 // - `Destruct` impls are built-in in 1.62 (current nightlies as of 08-04-2022), so until
942 // the builtin impls are supported by Chalk, we ignore them here.
943 if let Some(lang) = lang_attr(self.db.upcast(), tr.hir_trait_id()) {
944 if lang == "drop" || lang == "destruct" {
950 .map(WhereClause::Implemented)
951 .map(crate::wrap_empty_binders)
953 TypeBound::Path(path, TraitBoundModifier::Maybe) => {
954 let sized_trait = self
956 .lang_item(self.resolver.krate(), SmolStr::new_inline("sized"))
957 .and_then(|lang_item| lang_item.as_trait());
958 // Don't lower associated type bindings as the only possible relaxed trait bound
959 // `?Sized` has no of them.
960 // If we got another trait here ignore the bound completely.
962 .lower_trait_ref_from_path(path, Some(self_ty.clone()))
963 .map(|trait_ref| trait_ref.hir_trait_id());
964 if trait_id == sized_trait {
965 self.unsized_types.borrow_mut().insert(self_ty);
969 TypeBound::ForLifetime(_, path) => {
970 // FIXME Don't silently drop the hrtb lifetimes here
971 bindings = self.lower_trait_ref_from_path(path, Some(self_ty));
972 bindings.clone().map(WhereClause::Implemented).map(crate::wrap_empty_binders)
974 TypeBound::Lifetime(_) => None,
975 TypeBound::Error => None,
977 trait_ref.into_iter().chain(
980 .filter(move |_| !ignore_bindings)
981 .flat_map(move |tr| self.assoc_type_bindings_from_type_bound(bound, tr)),
985 fn assoc_type_bindings_from_type_bound(
987 bound: &'a TypeBound,
989 ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
990 let last_segment = match bound {
991 TypeBound::Path(path, TraitBoundModifier::None) | TypeBound::ForLifetime(_, path) => {
992 path.segments().last()
994 TypeBound::Path(_, TraitBoundModifier::Maybe)
996 | TypeBound::Lifetime(_) => None,
1000 .filter_map(|segment| segment.args_and_bindings)
1001 .flat_map(|args_and_bindings| &args_and_bindings.bindings)
1002 .flat_map(move |binding| {
1003 let found = associated_type_by_name_including_super_traits(
1008 let (super_trait_ref, associated_ty) = match found {
1009 None => return SmallVec::new(),
1012 // FIXME: `substs_from_path_segment()` pushes `TyKind::Error` for every parent
1013 // generic params. It's inefficient to splice the `Substitution`s, so we may want
1014 // that method to optionally take parent `Substitution` as we already know them at
1015 // this point (`super_trait_ref.substitution`).
1016 let substitution = self.substs_from_path_segment(
1017 // FIXME: This is hack. We shouldn't really build `PathSegment` directly.
1018 PathSegment { name: &binding.name, args_and_bindings: binding.args.as_deref() },
1019 Some(associated_ty.into()),
1020 false, // this is not relevant
1021 Some(super_trait_ref.self_type_parameter(Interner)),
1023 let self_params = generics(self.db.upcast(), associated_ty.into()).len_self();
1024 let substitution = Substitution::from_iter(
1029 .chain(super_trait_ref.substitution.iter(Interner)),
1031 let projection_ty = ProjectionTy {
1032 associated_ty_id: to_assoc_type_id(associated_ty),
1035 let mut preds: SmallVec<[_; 1]> = SmallVec::with_capacity(
1036 binding.type_ref.as_ref().map_or(0, |_| 1) + binding.bounds.len(),
1038 if let Some(type_ref) = &binding.type_ref {
1039 let ty = self.lower_ty(type_ref);
1041 AliasEq { alias: AliasTy::Projection(projection_ty.clone()), ty };
1042 preds.push(crate::wrap_empty_binders(WhereClause::AliasEq(alias_eq)));
1044 for bound in &binding.bounds {
1045 preds.extend(self.lower_type_bound(
1047 TyKind::Alias(AliasTy::Projection(projection_ty.clone())).intern(Interner),
1055 fn lower_dyn_trait(&self, bounds: &[Interned<TypeBound>]) -> Ty {
1056 let self_ty = TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(Interner);
1057 // INVARIANT: The principal trait bound, if present, must come first. Others may be in any
1058 // order but should be in the same order for the same set but possibly different order of
1059 // bounds in the input.
1060 // INVARIANT: If this function returns `DynTy`, there should be at least one trait bound.
1061 // These invariants are utilized by `TyExt::dyn_trait()` and chalk.
1062 let bounds = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
1063 let mut bounds: Vec<_> = bounds
1065 .flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false))
1068 let mut multiple_regular_traits = false;
1069 let mut multiple_same_projection = false;
1070 bounds.sort_unstable_by(|lhs, rhs| {
1071 use std::cmp::Ordering;
1072 match (lhs.skip_binders(), rhs.skip_binders()) {
1073 (WhereClause::Implemented(lhs), WhereClause::Implemented(rhs)) => {
1074 let lhs_id = lhs.trait_id;
1075 let lhs_is_auto = ctx.db.trait_data(from_chalk_trait_id(lhs_id)).is_auto;
1076 let rhs_id = rhs.trait_id;
1077 let rhs_is_auto = ctx.db.trait_data(from_chalk_trait_id(rhs_id)).is_auto;
1079 if !lhs_is_auto && !rhs_is_auto {
1080 multiple_regular_traits = true;
1082 // Note that the ordering here is important; this ensures the invariant
1084 (lhs_is_auto, lhs_id).cmp(&(rhs_is_auto, rhs_id))
1086 (WhereClause::Implemented(_), _) => Ordering::Less,
1087 (_, WhereClause::Implemented(_)) => Ordering::Greater,
1088 (WhereClause::AliasEq(lhs), WhereClause::AliasEq(rhs)) => {
1089 match (&lhs.alias, &rhs.alias) {
1090 (AliasTy::Projection(lhs_proj), AliasTy::Projection(rhs_proj)) => {
1091 // We only compare the `associated_ty_id`s. We shouldn't have
1092 // multiple bounds for an associated type in the correct Rust code,
1093 // and if we do, we error out.
1094 if lhs_proj.associated_ty_id == rhs_proj.associated_ty_id {
1095 multiple_same_projection = true;
1097 lhs_proj.associated_ty_id.cmp(&rhs_proj.associated_ty_id)
1099 // We don't produce `AliasTy::Opaque`s yet.
1100 _ => unreachable!(),
1103 // We don't produce `WhereClause::{TypeOutlives, LifetimeOutlives}` yet.
1104 _ => unreachable!(),
1108 if multiple_regular_traits || multiple_same_projection {
1112 if bounds.first().and_then(|b| b.trait_id()).is_none() {
1113 // When there's no trait bound, that's an error. This happens when the trait refs
1118 // As multiple occurrences of the same auto traits *are* permitted, we dedulicate the
1119 // bounds. We shouldn't have repeated elements besides auto traits at this point.
1122 Some(QuantifiedWhereClauses::from_iter(Interner, bounds))
1125 if let Some(bounds) = bounds {
1126 let bounds = crate::make_single_type_binders(bounds);
1127 TyKind::Dyn(DynTy { bounds, lifetime: static_lifetime() }).intern(Interner)
1129 // FIXME: report error
1130 // (additional non-auto traits, associated type rebound, or no resolved trait)
1131 TyKind::Error.intern(Interner)
1135 fn lower_impl_trait(
1137 bounds: &[Interned<TypeBound>],
1139 ) -> ReturnTypeImplTrait {
1140 cov_mark::hit!(lower_rpit);
1141 let self_ty = TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(Interner);
1142 let predicates = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
1143 let mut predicates: Vec<_> = bounds
1145 .flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false))
1148 if !ctx.unsized_types.borrow().contains(&self_ty) {
1149 let krate = func.lookup(ctx.db.upcast()).module(ctx.db.upcast()).krate();
1150 let sized_trait = ctx
1152 .lang_item(krate, SmolStr::new_inline("sized"))
1153 .and_then(|lang_item| lang_item.as_trait().map(to_chalk_trait_id));
1154 let sized_clause = sized_trait.map(|trait_id| {
1155 let clause = WhereClause::Implemented(TraitRef {
1157 substitution: Substitution::from1(Interner, self_ty.clone()),
1159 crate::wrap_empty_binders(clause)
1161 predicates.extend(sized_clause.into_iter());
1162 predicates.shrink_to_fit();
1166 ReturnTypeImplTrait { bounds: crate::make_single_type_binders(predicates) }
1170 fn count_impl_traits(type_ref: &TypeRef) -> usize {
1172 type_ref.walk(&mut |type_ref| {
1173 if matches!(type_ref, TypeRef::ImplTrait(_)) {
1180 /// Build the signature of a callable item (function, struct or enum variant).
1181 pub(crate) fn callable_item_sig(db: &dyn HirDatabase, def: CallableDefId) -> PolyFnSig {
1183 CallableDefId::FunctionId(f) => fn_sig_for_fn(db, f),
1184 CallableDefId::StructId(s) => fn_sig_for_struct_constructor(db, s),
1185 CallableDefId::EnumVariantId(e) => fn_sig_for_enum_variant_constructor(db, e),
1189 pub fn associated_type_shorthand_candidates<R>(
1190 db: &dyn HirDatabase,
1193 cb: impl FnMut(&Name, &TraitRef, TypeAliasId) -> Option<R>,
1195 named_associated_type_shorthand_candidates(db, def, res, None, cb)
1198 fn named_associated_type_shorthand_candidates<R>(
1199 db: &dyn HirDatabase,
1200 // If the type parameter is defined in an impl and we're in a method, there
1201 // might be additional where clauses to consider
1204 assoc_name: Option<Name>,
1205 mut cb: impl FnMut(&Name, &TraitRef, TypeAliasId) -> Option<R>,
1207 let mut search = |t| {
1208 for t in all_super_trait_refs(db, t) {
1209 let data = db.trait_data(t.hir_trait_id());
1211 for (name, assoc_id) in &data.items {
1212 if let AssocItemId::TypeAliasId(alias) = assoc_id {
1213 if let Some(result) = cb(name, &t, *alias) {
1214 return Some(result);
1223 TypeNs::SelfType(impl_id) => {
1224 // we're _in_ the impl -- the binders get added back later. Correct,
1225 // but it would be nice to make this more explicit
1226 let trait_ref = db.impl_trait(impl_id)?.into_value_and_skipped_binders().0;
1228 let impl_id_as_generic_def: GenericDefId = impl_id.into();
1229 if impl_id_as_generic_def != def {
1230 // `trait_ref` contains `BoundVar`s bound by impl's `Binders`, but here we need
1231 // `BoundVar`s from `def`'s point of view.
1232 // FIXME: A `HirDatabase` query may be handy if this process is needed in more
1233 // places. It'd be almost identical as `impl_trait_query` where `resolver` would be
1234 // of `def` instead of `impl_id`.
1235 let starting_idx = generics(db.upcast(), def).len_self();
1236 let subst = TyBuilder::subst_for_def(db, impl_id, None)
1237 .fill_with_bound_vars(DebruijnIndex::INNERMOST, starting_idx)
1239 let trait_ref = subst.apply(trait_ref, Interner);
1245 TypeNs::GenericParam(param_id) => {
1246 let predicates = db.generic_predicates_for_param(def, param_id.into(), assoc_name);
1247 let res = predicates.iter().find_map(|pred| match pred.skip_binders().skip_binders() {
1248 // FIXME: how to correctly handle higher-ranked bounds here?
1249 WhereClause::Implemented(tr) => search(
1251 .shifted_out_to(Interner, DebruijnIndex::ONE)
1252 .expect("FIXME unexpected higher-ranked trait bound"),
1256 if let Some(_) = res {
1259 // Handle `Self::Type` referring to own associated type in trait definitions
1260 if let GenericDefId::TraitId(trait_id) = param_id.parent() {
1261 let trait_generics = generics(db.upcast(), trait_id.into());
1262 if trait_generics.params.type_or_consts[param_id.local_id()].is_trait_self() {
1263 let def_generics = generics(db.upcast(), def);
1264 let starting_idx = match def {
1265 GenericDefId::TraitId(_) => 0,
1266 // `def` is an item within trait. We need to substitute `BoundVar`s but
1267 // remember that they are for parent (i.e. trait) generic params so they
1268 // come after our own params.
1269 _ => def_generics.len_self(),
1271 let trait_ref = TyBuilder::trait_ref(db, trait_id)
1272 .fill_with_bound_vars(DebruijnIndex::INNERMOST, starting_idx)
1274 return search(trait_ref);
1283 /// Build the type of all specific fields of a struct or enum variant.
1284 pub(crate) fn field_types_query(
1285 db: &dyn HirDatabase,
1286 variant_id: VariantId,
1287 ) -> Arc<ArenaMap<LocalFieldId, Binders<Ty>>> {
1288 let var_data = variant_id.variant_data(db.upcast());
1289 let (resolver, def): (_, GenericDefId) = match variant_id {
1290 VariantId::StructId(it) => (it.resolver(db.upcast()), it.into()),
1291 VariantId::UnionId(it) => (it.resolver(db.upcast()), it.into()),
1292 VariantId::EnumVariantId(it) => (it.parent.resolver(db.upcast()), it.parent.into()),
1294 let generics = generics(db.upcast(), def);
1295 let mut res = ArenaMap::default();
1297 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1298 for (field_id, field_data) in var_data.fields().iter() {
1299 res.insert(field_id, make_binders(db, &generics, ctx.lower_ty(&field_data.type_ref)));
1304 /// This query exists only to be used when resolving short-hand associated types
1307 /// See the analogous query in rustc and its comment:
1308 /// <https://github.com/rust-lang/rust/blob/9150f844e2624eb013ec78ca08c1d416e6644026/src/librustc_typeck/astconv.rs#L46>
1309 /// This is a query mostly to handle cycles somewhat gracefully; e.g. the
1310 /// following bounds are disallowed: `T: Foo<U::Item>, U: Foo<T::Item>`, but
1311 /// these are fine: `T: Foo<U::Item>, U: Foo<()>`.
1312 pub(crate) fn generic_predicates_for_param_query(
1313 db: &dyn HirDatabase,
1315 param_id: TypeOrConstParamId,
1316 assoc_name: Option<Name>,
1317 ) -> Arc<[Binders<QuantifiedWhereClause>]> {
1318 let resolver = def.resolver(db.upcast());
1320 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1321 let generics = generics(db.upcast(), def);
1322 let mut predicates: Vec<_> = resolver
1323 .where_predicates_in_scope()
1324 // we have to filter out all other predicates *first*, before attempting to lower them
1325 .filter(|pred| match pred {
1326 WherePredicate::ForLifetime { target, bound, .. }
1327 | WherePredicate::TypeBound { target, bound, .. } => {
1329 WherePredicateTypeTarget::TypeRef(type_ref) => {
1330 if ctx.lower_ty_only_param(type_ref) != Some(param_id) {
1334 &WherePredicateTypeTarget::TypeOrConstParam(local_id) => {
1335 let target_id = TypeOrConstParamId { parent: def, local_id };
1336 if target_id != param_id {
1343 TypeBound::ForLifetime(_, path) | TypeBound::Path(path, _) => {
1344 // Only lower the bound if the trait could possibly define the associated
1345 // type we're looking for.
1347 let assoc_name = match &assoc_name {
1349 None => return true,
1351 let tr = match resolver
1352 .resolve_path_in_type_ns_fully(db.upcast(), path.mod_path())
1354 Some(TypeNs::TraitId(tr)) => tr,
1358 all_super_traits(db.upcast(), tr).iter().any(|tr| {
1359 db.trait_data(*tr).items.iter().any(|(name, item)| {
1360 matches!(item, AssocItemId::TypeAliasId(_)) && name == assoc_name
1364 TypeBound::Lifetime(_) | TypeBound::Error => false,
1367 WherePredicate::Lifetime { .. } => false,
1370 ctx.lower_where_predicate(pred, true).map(|p| make_binders(db, &generics, p))
1374 let subst = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1375 let explicitly_unsized_tys = ctx.unsized_types.into_inner();
1376 let implicitly_sized_predicates =
1377 implicitly_sized_clauses(db, param_id.parent, &explicitly_unsized_tys, &subst, &resolver)
1378 .map(|p| make_binders(db, &generics, crate::wrap_empty_binders(p)));
1379 predicates.extend(implicitly_sized_predicates);
1383 pub(crate) fn generic_predicates_for_param_recover(
1384 _db: &dyn HirDatabase,
1386 _def: &GenericDefId,
1387 _param_id: &TypeOrConstParamId,
1388 _assoc_name: &Option<Name>,
1389 ) -> Arc<[Binders<QuantifiedWhereClause>]> {
1393 pub(crate) fn trait_environment_query(
1394 db: &dyn HirDatabase,
1396 ) -> Arc<TraitEnvironment> {
1397 let resolver = def.resolver(db.upcast());
1399 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Placeholder);
1400 let mut traits_in_scope = Vec::new();
1401 let mut clauses = Vec::new();
1402 for pred in resolver.where_predicates_in_scope() {
1403 for pred in ctx.lower_where_predicate(pred, false) {
1404 if let WhereClause::Implemented(tr) = &pred.skip_binders() {
1405 traits_in_scope.push((tr.self_type_parameter(Interner).clone(), tr.hir_trait_id()));
1407 let program_clause: chalk_ir::ProgramClause<Interner> = pred.cast(Interner);
1408 clauses.push(program_clause.into_from_env_clause(Interner));
1412 let container: Option<ItemContainerId> = match def {
1413 // FIXME: is there a function for this?
1414 GenericDefId::FunctionId(f) => Some(f.lookup(db.upcast()).container),
1415 GenericDefId::AdtId(_) => None,
1416 GenericDefId::TraitId(_) => None,
1417 GenericDefId::TypeAliasId(t) => Some(t.lookup(db.upcast()).container),
1418 GenericDefId::ImplId(_) => None,
1419 GenericDefId::EnumVariantId(_) => None,
1420 GenericDefId::ConstId(c) => Some(c.lookup(db.upcast()).container),
1422 if let Some(ItemContainerId::TraitId(trait_id)) = container {
1423 // add `Self: Trait<T1, T2, ...>` to the environment in trait
1424 // function default implementations (and speculative code
1425 // inside consts or type aliases)
1426 cov_mark::hit!(trait_self_implements_self);
1427 let substs = TyBuilder::placeholder_subst(db, trait_id);
1428 let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution: substs };
1429 let pred = WhereClause::Implemented(trait_ref);
1430 let program_clause: chalk_ir::ProgramClause<Interner> = pred.cast(Interner);
1431 clauses.push(program_clause.into_from_env_clause(Interner));
1434 let subst = generics(db.upcast(), def).placeholder_subst(db);
1435 let explicitly_unsized_tys = ctx.unsized_types.into_inner();
1436 let implicitly_sized_clauses =
1437 implicitly_sized_clauses(db, def, &explicitly_unsized_tys, &subst, &resolver).map(|pred| {
1438 let program_clause: chalk_ir::ProgramClause<Interner> = pred.cast(Interner);
1439 program_clause.into_from_env_clause(Interner)
1441 clauses.extend(implicitly_sized_clauses);
1443 let krate = def.module(db.upcast()).krate();
1445 let env = chalk_ir::Environment::new(Interner).add_clauses(Interner, clauses);
1447 Arc::new(TraitEnvironment { krate, traits_from_clauses: traits_in_scope, env })
1450 /// Resolve the where clause(s) of an item with generics.
1451 pub(crate) fn generic_predicates_query(
1452 db: &dyn HirDatabase,
1454 ) -> Arc<[Binders<QuantifiedWhereClause>]> {
1455 let resolver = def.resolver(db.upcast());
1457 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1458 let generics = generics(db.upcast(), def);
1460 let mut predicates = resolver
1461 .where_predicates_in_scope()
1463 ctx.lower_where_predicate(pred, false).map(|p| make_binders(db, &generics, p))
1465 .collect::<Vec<_>>();
1467 let subst = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1468 let explicitly_unsized_tys = ctx.unsized_types.into_inner();
1469 let implicitly_sized_predicates =
1470 implicitly_sized_clauses(db, def, &explicitly_unsized_tys, &subst, &resolver)
1471 .map(|p| make_binders(db, &generics, crate::wrap_empty_binders(p)));
1472 predicates.extend(implicitly_sized_predicates);
1476 /// Generate implicit `: Sized` predicates for all generics that has no `?Sized` bound.
1477 /// Exception is Self of a trait def.
1478 fn implicitly_sized_clauses<'a>(
1479 db: &dyn HirDatabase,
1481 explicitly_unsized_tys: &'a FxHashSet<Ty>,
1482 substitution: &'a Substitution,
1483 resolver: &Resolver,
1484 ) -> impl Iterator<Item = WhereClause> + 'a {
1485 let is_trait_def = matches!(def, GenericDefId::TraitId(..));
1486 let generic_args = &substitution.as_slice(Interner)[is_trait_def as usize..];
1487 let sized_trait = db
1488 .lang_item(resolver.krate(), SmolStr::new_inline("sized"))
1489 .and_then(|lang_item| lang_item.as_trait().map(to_chalk_trait_id));
1491 sized_trait.into_iter().flat_map(move |sized_trait| {
1492 let implicitly_sized_tys = generic_args
1494 .filter_map(|generic_arg| generic_arg.ty(Interner))
1495 .filter(move |&self_ty| !explicitly_unsized_tys.contains(self_ty));
1496 implicitly_sized_tys.map(move |self_ty| {
1497 WhereClause::Implemented(TraitRef {
1498 trait_id: sized_trait,
1499 substitution: Substitution::from1(Interner, self_ty.clone()),
1505 /// Resolve the default type params from generics
1506 pub(crate) fn generic_defaults_query(
1507 db: &dyn HirDatabase,
1509 ) -> Arc<[Binders<chalk_ir::GenericArg<Interner>>]> {
1510 let resolver = def.resolver(db.upcast());
1512 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1513 let generic_params = generics(db.upcast(), def);
1514 let parent_start_idx = generic_params.len_self();
1516 let defaults = generic_params
1519 .map(|(idx, (id, p))| {
1521 TypeOrConstParamData::TypeParamData(p) => p,
1522 TypeOrConstParamData::ConstParamData(_) => {
1523 // FIXME: implement const generic defaults
1524 let val = unknown_const_as_generic(
1525 db.const_param_ty(ConstParamId::from_unchecked(id)),
1527 return make_binders(db, &generic_params, val);
1531 p.default.as_ref().map_or(TyKind::Error.intern(Interner), |t| ctx.lower_ty(t));
1533 // Each default can only refer to previous parameters.
1534 // Type variable default referring to parameter coming
1535 // after it is forbidden (FIXME: report diagnostic)
1536 ty = fallback_bound_vars(ty, idx, parent_start_idx);
1537 crate::make_binders(db, &generic_params, ty.cast(Interner))
1544 pub(crate) fn generic_defaults_recover(
1545 db: &dyn HirDatabase,
1548 ) -> Arc<[Binders<crate::GenericArg>]> {
1549 let generic_params = generics(db.upcast(), *def);
1550 // FIXME: this code is not covered in tests.
1551 // we still need one default per parameter
1552 let defaults = generic_params
1555 let val = match id {
1556 itertools::Either::Left(_) => {
1557 GenericArgData::Ty(TyKind::Error.intern(Interner)).intern(Interner)
1559 itertools::Either::Right(id) => unknown_const_as_generic(db.const_param_ty(id)),
1561 crate::make_binders(db, &generic_params, val)
1568 fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
1569 let data = db.function_data(def);
1570 let resolver = def.resolver(db.upcast());
1571 let ctx_params = TyLoweringContext::new(db, &resolver)
1572 .with_impl_trait_mode(ImplTraitLoweringMode::Variable)
1573 .with_type_param_mode(ParamLoweringMode::Variable);
1574 let params = data.params.iter().map(|(_, tr)| ctx_params.lower_ty(tr)).collect::<Vec<_>>();
1575 let ctx_ret = TyLoweringContext::new(db, &resolver)
1576 .with_impl_trait_mode(ImplTraitLoweringMode::Opaque)
1577 .with_type_param_mode(ParamLoweringMode::Variable);
1578 let ret = ctx_ret.lower_ty(&data.ret_type);
1579 let generics = generics(db.upcast(), def.into());
1580 let sig = CallableSig::from_params_and_return(
1584 if data.has_unsafe_kw() { Safety::Unsafe } else { Safety::Safe },
1586 make_binders(db, &generics, sig)
1589 /// Build the declared type of a function. This should not need to look at the
1591 fn type_for_fn(db: &dyn HirDatabase, def: FunctionId) -> Binders<Ty> {
1592 let generics = generics(db.upcast(), def.into());
1593 let substs = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1597 TyKind::FnDef(CallableDefId::FunctionId(def).to_chalk(db), substs).intern(Interner),
1601 /// Build the declared type of a const.
1602 fn type_for_const(db: &dyn HirDatabase, def: ConstId) -> Binders<Ty> {
1603 let data = db.const_data(def);
1604 let generics = generics(db.upcast(), def.into());
1605 let resolver = def.resolver(db.upcast());
1607 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1609 make_binders(db, &generics, ctx.lower_ty(&data.type_ref))
1612 /// Build the declared type of a static.
1613 fn type_for_static(db: &dyn HirDatabase, def: StaticId) -> Binders<Ty> {
1614 let data = db.static_data(def);
1615 let resolver = def.resolver(db.upcast());
1616 let ctx = TyLoweringContext::new(db, &resolver);
1618 Binders::empty(Interner, ctx.lower_ty(&data.type_ref))
1621 fn fn_sig_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> PolyFnSig {
1622 let struct_data = db.struct_data(def);
1623 let fields = struct_data.variant_data.fields();
1624 let resolver = def.resolver(db.upcast());
1626 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1627 let params = fields.iter().map(|(_, field)| ctx.lower_ty(&field.type_ref)).collect::<Vec<_>>();
1628 let (ret, binders) = type_for_adt(db, def.into()).into_value_and_skipped_binders();
1629 Binders::new(binders, CallableSig::from_params_and_return(params, ret, false, Safety::Safe))
1632 /// Build the type of a tuple struct constructor.
1633 fn type_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> Binders<Ty> {
1634 let struct_data = db.struct_data(def);
1635 if let StructKind::Unit = struct_data.variant_data.kind() {
1636 return type_for_adt(db, def.into());
1638 let generics = generics(db.upcast(), def.into());
1639 let substs = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1643 TyKind::FnDef(CallableDefId::StructId(def).to_chalk(db), substs).intern(Interner),
1647 fn fn_sig_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -> PolyFnSig {
1648 let enum_data = db.enum_data(def.parent);
1649 let var_data = &enum_data.variants[def.local_id];
1650 let fields = var_data.variant_data.fields();
1651 let resolver = def.parent.resolver(db.upcast());
1653 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1654 let params = fields.iter().map(|(_, field)| ctx.lower_ty(&field.type_ref)).collect::<Vec<_>>();
1655 let (ret, binders) = type_for_adt(db, def.parent.into()).into_value_and_skipped_binders();
1656 Binders::new(binders, CallableSig::from_params_and_return(params, ret, false, Safety::Safe))
1659 /// Build the type of a tuple enum variant constructor.
1660 fn type_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -> Binders<Ty> {
1661 let enum_data = db.enum_data(def.parent);
1662 let var_data = &enum_data.variants[def.local_id].variant_data;
1663 if let StructKind::Unit = var_data.kind() {
1664 return type_for_adt(db, def.parent.into());
1666 let generics = generics(db.upcast(), def.parent.into());
1667 let substs = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1671 TyKind::FnDef(CallableDefId::EnumVariantId(def).to_chalk(db), substs).intern(Interner),
1675 fn type_for_adt(db: &dyn HirDatabase, adt: AdtId) -> Binders<Ty> {
1676 let generics = generics(db.upcast(), adt.into());
1677 let subst = generics.bound_vars_subst(db, DebruijnIndex::INNERMOST);
1678 let ty = TyKind::Adt(crate::AdtId(adt), subst).intern(Interner);
1679 make_binders(db, &generics, ty)
1682 fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders<Ty> {
1683 let generics = generics(db.upcast(), t.into());
1684 let resolver = t.resolver(db.upcast());
1686 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1687 if db.type_alias_data(t).is_extern {
1688 Binders::empty(Interner, TyKind::Foreign(crate::to_foreign_def_id(t)).intern(Interner))
1690 let type_ref = &db.type_alias_data(t).type_ref;
1691 let inner = ctx.lower_ty(type_ref.as_deref().unwrap_or(&TypeRef::Error));
1692 make_binders(db, &generics, inner)
1696 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
1697 pub enum CallableDefId {
1698 FunctionId(FunctionId),
1700 EnumVariantId(EnumVariantId),
1702 impl_from!(FunctionId, StructId, EnumVariantId for CallableDefId);
1704 impl CallableDefId {
1705 pub fn krate(self, db: &dyn HirDatabase) -> CrateId {
1706 let db = db.upcast();
1708 CallableDefId::FunctionId(f) => f.lookup(db).module(db),
1709 CallableDefId::StructId(s) => s.lookup(db).container,
1710 CallableDefId::EnumVariantId(e) => e.parent.lookup(db).container,
1716 impl From<CallableDefId> for GenericDefId {
1717 fn from(def: CallableDefId) -> GenericDefId {
1719 CallableDefId::FunctionId(f) => f.into(),
1720 CallableDefId::StructId(s) => s.into(),
1721 CallableDefId::EnumVariantId(e) => e.into(),
1726 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1728 BuiltinType(BuiltinType),
1730 TypeAliasId(TypeAliasId),
1732 impl_from!(BuiltinType, AdtId(StructId, EnumId, UnionId), TypeAliasId for TyDefId);
1734 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1735 pub enum ValueTyDefId {
1736 FunctionId(FunctionId),
1739 EnumVariantId(EnumVariantId),
1743 impl_from!(FunctionId, StructId, UnionId, EnumVariantId, ConstId, StaticId for ValueTyDefId);
1746 pub(crate) fn to_generic_def_id(self) -> Option<GenericDefId> {
1748 Self::FunctionId(id) => Some(id.into()),
1749 Self::StructId(id) => Some(id.into()),
1750 Self::UnionId(id) => Some(id.into()),
1751 Self::EnumVariantId(var) => Some(var.into()),
1752 Self::ConstId(id) => Some(id.into()),
1753 Self::StaticId(_) => None,
1758 /// Build the declared type of an item. This depends on the namespace; e.g. for
1759 /// `struct Foo(usize)`, we have two types: The type of the struct itself, and
1760 /// the constructor function `(usize) -> Foo` which lives in the values
1762 pub(crate) fn ty_query(db: &dyn HirDatabase, def: TyDefId) -> Binders<Ty> {
1764 TyDefId::BuiltinType(it) => Binders::empty(Interner, TyBuilder::builtin(it)),
1765 TyDefId::AdtId(it) => type_for_adt(db, it),
1766 TyDefId::TypeAliasId(it) => type_for_type_alias(db, it),
1770 pub(crate) fn ty_recover(db: &dyn HirDatabase, _cycle: &[String], def: &TyDefId) -> Binders<Ty> {
1771 let generics = match *def {
1772 TyDefId::BuiltinType(_) => return Binders::empty(Interner, TyKind::Error.intern(Interner)),
1773 TyDefId::AdtId(it) => generics(db.upcast(), it.into()),
1774 TyDefId::TypeAliasId(it) => generics(db.upcast(), it.into()),
1776 make_binders(db, &generics, TyKind::Error.intern(Interner))
1779 pub(crate) fn value_ty_query(db: &dyn HirDatabase, def: ValueTyDefId) -> Binders<Ty> {
1781 ValueTyDefId::FunctionId(it) => type_for_fn(db, it),
1782 ValueTyDefId::StructId(it) => type_for_struct_constructor(db, it),
1783 ValueTyDefId::UnionId(it) => type_for_adt(db, it.into()),
1784 ValueTyDefId::EnumVariantId(it) => type_for_enum_variant_constructor(db, it),
1785 ValueTyDefId::ConstId(it) => type_for_const(db, it),
1786 ValueTyDefId::StaticId(it) => type_for_static(db, it),
1790 pub(crate) fn impl_self_ty_query(db: &dyn HirDatabase, impl_id: ImplId) -> Binders<Ty> {
1791 let impl_loc = impl_id.lookup(db.upcast());
1792 let impl_data = db.impl_data(impl_id);
1793 let resolver = impl_id.resolver(db.upcast());
1794 let _cx = stdx::panic_context::enter(format!(
1795 "impl_self_ty_query({:?} -> {:?} -> {:?})",
1796 impl_id, impl_loc, impl_data
1798 let generics = generics(db.upcast(), impl_id.into());
1800 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1801 make_binders(db, &generics, ctx.lower_ty(&impl_data.self_ty))
1804 // returns None if def is a type arg
1805 pub(crate) fn const_param_ty_query(db: &dyn HirDatabase, def: ConstParamId) -> Ty {
1806 let parent_data = db.generic_params(def.parent());
1807 let data = &parent_data.type_or_consts[def.local_id()];
1808 let resolver = def.parent().resolver(db.upcast());
1809 let ctx = TyLoweringContext::new(db, &resolver);
1811 TypeOrConstParamData::TypeParamData(_) => {
1813 Ty::new(Interner, TyKind::Error)
1815 TypeOrConstParamData::ConstParamData(d) => ctx.lower_ty(&d.ty),
1819 pub(crate) fn impl_self_ty_recover(
1820 db: &dyn HirDatabase,
1824 let generics = generics(db.upcast(), (*impl_id).into());
1825 make_binders(db, &generics, TyKind::Error.intern(Interner))
1828 pub(crate) fn impl_trait_query(db: &dyn HirDatabase, impl_id: ImplId) -> Option<Binders<TraitRef>> {
1829 let impl_loc = impl_id.lookup(db.upcast());
1830 let impl_data = db.impl_data(impl_id);
1831 let resolver = impl_id.resolver(db.upcast());
1832 let _cx = stdx::panic_context::enter(format!(
1833 "impl_trait_query({:?} -> {:?} -> {:?})",
1834 impl_id, impl_loc, impl_data
1837 TyLoweringContext::new(db, &resolver).with_type_param_mode(ParamLoweringMode::Variable);
1838 let (self_ty, binders) = db.impl_self_ty(impl_id).into_value_and_skipped_binders();
1839 let target_trait = impl_data.target_trait.as_ref()?;
1840 Some(Binders::new(binders, ctx.lower_trait_ref(target_trait, Some(self_ty))?))
1843 pub(crate) fn return_type_impl_traits(
1844 db: &dyn HirDatabase,
1845 def: hir_def::FunctionId,
1846 ) -> Option<Arc<Binders<ReturnTypeImplTraits>>> {
1847 // FIXME unify with fn_sig_for_fn instead of doing lowering twice, maybe
1848 let data = db.function_data(def);
1849 let resolver = def.resolver(db.upcast());
1850 let ctx_ret = TyLoweringContext::new(db, &resolver)
1851 .with_impl_trait_mode(ImplTraitLoweringMode::Opaque)
1852 .with_type_param_mode(ParamLoweringMode::Variable);
1853 let _ret = (&ctx_ret).lower_ty(&data.ret_type);
1854 let generics = generics(db.upcast(), def.into());
1855 let return_type_impl_traits =
1856 ReturnTypeImplTraits { impl_traits: ctx_ret.opaque_type_data.into_inner() };
1857 if return_type_impl_traits.impl_traits.is_empty() {
1860 Some(Arc::new(make_binders(db, &generics, return_type_impl_traits)))
1864 pub(crate) fn lower_to_chalk_mutability(m: hir_def::type_ref::Mutability) -> Mutability {
1866 hir_def::type_ref::Mutability::Shared => Mutability::Not,
1867 hir_def::type_ref::Mutability::Mut => Mutability::Mut,
1871 /// Checks if the provided generic arg matches its expected kind, then lower them via
1872 /// provided closures. Use unknown if there was kind mismatch.
1874 /// Returns `Some` of the lowered generic arg. `None` if the provided arg is a lifetime.
1875 pub(crate) fn generic_arg_to_chalk<'a, T>(
1876 db: &dyn HirDatabase,
1877 kind_id: Either<TypeParamId, ConstParamId>,
1878 arg: &'a GenericArg,
1880 for_type: impl FnOnce(&mut T, &TypeRef) -> Ty + 'a,
1881 for_const: impl FnOnce(&mut T, &ConstScalarOrPath, Ty) -> Const + 'a,
1882 ) -> Option<crate::GenericArg> {
1883 let kind = match kind_id {
1884 Either::Left(_) => ParamKind::Type,
1885 Either::Right(id) => {
1886 let ty = db.const_param_ty(id);
1887 ParamKind::Const(ty)
1890 Some(match (arg, kind) {
1891 (GenericArg::Type(type_ref), ParamKind::Type) => {
1892 let ty = for_type(this, type_ref);
1893 GenericArgData::Ty(ty).intern(Interner)
1895 (GenericArg::Const(c), ParamKind::Const(c_ty)) => {
1896 GenericArgData::Const(for_const(this, c, c_ty)).intern(Interner)
1898 (GenericArg::Const(_), ParamKind::Type) => {
1899 GenericArgData::Ty(TyKind::Error.intern(Interner)).intern(Interner)
1901 (GenericArg::Type(t), ParamKind::Const(c_ty)) => {
1902 // We want to recover simple idents, which parser detects them
1903 // as types. Maybe here is not the best place to do it, but
1905 if let TypeRef::Path(p) = t {
1906 let p = p.mod_path();
1907 if p.kind == PathKind::Plain {
1908 if let [n] = p.segments() {
1909 let c = ConstScalarOrPath::Path(n.clone());
1911 GenericArgData::Const(for_const(this, &c, c_ty)).intern(Interner),
1916 unknown_const_as_generic(c_ty)
1918 (GenericArg::Lifetime(_), _) => return None,
1922 pub(crate) fn const_or_path_to_chalk(
1923 db: &dyn HirDatabase,
1924 resolver: &Resolver,
1926 value: &ConstScalarOrPath,
1927 mode: ParamLoweringMode,
1928 args: impl FnOnce() -> Generics,
1929 debruijn: DebruijnIndex,
1932 ConstScalarOrPath::Scalar(s) => intern_const_scalar(s.clone(), expected_ty),
1933 ConstScalarOrPath::Path(n) => {
1934 let path = ModPath::from_segments(PathKind::Plain, Some(n.clone()));
1935 path_to_const(db, resolver, &path, mode, args, debruijn)
1936 .unwrap_or_else(|| unknown_const(expected_ty))
1941 /// Replaces any 'free' `BoundVar`s in `s` by `TyKind::Error` from the perspective of generic
1942 /// parameter whose index is `param_index`. A `BoundVar` is free when it is or (syntactically)
1943 /// appears after the generic parameter of `param_index`.
1944 fn fallback_bound_vars<T: TypeFoldable<Interner> + HasInterner<Interner = Interner>>(
1947 parent_start: usize,
1949 // Keep in mind that parent generic parameters, if any, come *after* those of the item in
1950 // question. In the diagrams below, `c*` and `p*` represent generic parameters of the item and
1951 // its parent respectively.
1952 let is_allowed = |index| {
1953 if param_index < parent_start {
1954 // The parameter of `param_index` is one from the item in question. Any parent generic
1955 // parameters or the item's generic parameters that come before `param_index` is
1957 // [c1, .., cj, .., ck, p1, .., pl] where cj is `param_index`
1958 // ^^^^^^ ^^^^^^^^^^ these are allowed
1959 !(param_index..parent_start).contains(&index)
1961 // The parameter of `param_index` is one from the parent generics. Only parent generic
1962 // parameters that come before `param_index` are allowed.
1963 // [c1, .., ck, p1, .., pj, .., pl] where pj is `param_index`
1964 // ^^^^^^ these are allowed
1965 (parent_start..param_index).contains(&index)
1969 crate::fold_free_vars(
1972 if bound.index_if_innermost().map_or(true, is_allowed) {
1973 bound.shifted_in_from(binders).to_ty(Interner)
1975 TyKind::Error.intern(Interner)
1978 |ty, bound, binders| {
1979 if bound.index_if_innermost().map_or(true, is_allowed) {
1980 bound.shifted_in_from(binders).to_const(Interner, ty)
1982 unknown_const(ty.clone())