rustc_hir_analysis/collect/
item_bounds.rs

1use rustc_data_structures::fx::{FxIndexMap, FxIndexSet};
2use rustc_hir as hir;
3use rustc_infer::traits::util;
4use rustc_middle::ty::{
5    self, GenericArgs, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt,
6    Upcast, shift_vars,
7};
8use rustc_middle::{bug, span_bug};
9use rustc_span::Span;
10use rustc_span::def_id::{DefId, LocalDefId};
11use tracing::{debug, instrument};
12
13use super::ItemCtxt;
14use super::predicates_of::assert_only_contains_predicates_from;
15use crate::hir_ty_lowering::{
16    HirTyLowerer, ImpliedBoundsContext, OverlappingAsssocItemConstraints, PredicateFilter,
17};
18
19/// For associated types we include both bounds written on the type
20/// (`type X: Trait`) and predicates from the trait: `where Self::X: Trait`.
21///
22/// Note that this filtering is done with the items identity args to
23/// simplify checking that these bounds are met in impls. This means that
24/// a bound such as `for<'b> <Self as X<'b>>::U: Clone` can't be used, as in
25/// `hr-associated-type-bound-1.rs`.
26fn associated_type_bounds<'tcx>(
27    tcx: TyCtxt<'tcx>,
28    assoc_item_def_id: LocalDefId,
29    hir_bounds: &'tcx [hir::GenericBound<'tcx>],
30    span: Span,
31    filter: PredicateFilter,
32) -> &'tcx [(ty::Clause<'tcx>, Span)] {
33    ty::print::with_reduced_queries!({
34        let item_ty = Ty::new_projection_from_args(
35            tcx,
36            assoc_item_def_id.to_def_id(),
37            GenericArgs::identity_for_item(tcx, assoc_item_def_id),
38        );
39
40        let icx = ItemCtxt::new(tcx, assoc_item_def_id);
41        let mut bounds = Vec::new();
42        icx.lowerer().lower_bounds(
43            item_ty,
44            hir_bounds,
45            &mut bounds,
46            ty::List::empty(),
47            filter,
48            OverlappingAsssocItemConstraints::Allowed,
49        );
50
51        match filter {
52            PredicateFilter::All
53            | PredicateFilter::SelfOnly
54            | PredicateFilter::SelfTraitThatDefines(_)
55            | PredicateFilter::SelfAndAssociatedTypeBounds => {
56                // Implicit bounds are added to associated types unless a `?Trait` bound is found.
57                icx.lowerer().add_implicit_sizedness_bounds(
58                    &mut bounds,
59                    item_ty,
60                    hir_bounds,
61                    ImpliedBoundsContext::AssociatedTypeOrImplTrait,
62                    span,
63                );
64                icx.lowerer().add_default_traits(
65                    &mut bounds,
66                    item_ty,
67                    hir_bounds,
68                    ImpliedBoundsContext::AssociatedTypeOrImplTrait,
69                    span,
70                );
71
72                // Also collect `where Self::Assoc: Trait` from the parent trait's where clauses.
73                let trait_def_id = tcx.local_parent(assoc_item_def_id);
74                let trait_predicates = tcx.trait_explicit_predicates_and_bounds(trait_def_id);
75
76                let item_trait_ref =
77                    ty::TraitRef::identity(tcx, tcx.parent(assoc_item_def_id.to_def_id()));
78                bounds.extend(trait_predicates.predicates.iter().copied().filter_map(
79                    |(clause, span)| {
80                        remap_gat_vars_and_recurse_into_nested_projections(
81                            tcx,
82                            filter,
83                            item_trait_ref,
84                            assoc_item_def_id,
85                            span,
86                            clause,
87                        )
88                    },
89                ));
90            }
91            // `ConstIfConst` is only interested in `[const]` bounds.
92            PredicateFilter::ConstIfConst | PredicateFilter::SelfConstIfConst => {
93                // FIXME(const_trait_impl): We *could* uplift the
94                // `where Self::Assoc: [const] Trait` bounds from the parent trait
95                // here too, but we'd need to split `const_conditions` into two
96                // queries (like we do for `trait_explicit_predicates_and_bounds`)
97                // since we need to also filter the predicates *out* of the const
98                // conditions or they lead to cycles in the trait solver when
99                // utilizing these bounds. For now, let's do nothing.
100            }
101        }
102
103        let bounds = tcx.arena.alloc_from_iter(bounds);
104        debug!(
105            "associated_type_bounds({}) = {:?}",
106            tcx.def_path_str(assoc_item_def_id.to_def_id()),
107            bounds
108        );
109
110        assert_only_contains_predicates_from(filter, bounds, item_ty);
111
112        bounds
113    })
114}
115
116/// The code below is quite involved, so let me explain.
117///
118/// We loop here, because we also want to collect vars for nested associated items as
119/// well. For example, given a clause like `Self::A::B`, we want to add that to the
120/// item bounds for `A`, so that we may use that bound in the case that `Self::A::B` is
121/// rigid.
122///
123/// Secondly, regarding bound vars, when we see a where clause that mentions a GAT
124/// like `for<'a, ...> Self::Assoc<'a, ...>: Bound<'b, ...>`, we want to turn that into
125/// an item bound on the GAT, where all of the GAT args are substituted with the GAT's
126/// param regions, and then keep all of the other late-bound vars in the bound around.
127/// We need to "compress" the binder so that it doesn't mention any of those vars that
128/// were mapped to params.
129fn remap_gat_vars_and_recurse_into_nested_projections<'tcx>(
130    tcx: TyCtxt<'tcx>,
131    filter: PredicateFilter,
132    item_trait_ref: ty::TraitRef<'tcx>,
133    assoc_item_def_id: LocalDefId,
134    span: Span,
135    clause: ty::Clause<'tcx>,
136) -> Option<(ty::Clause<'tcx>, Span)> {
137    let mut clause_ty = match clause.kind().skip_binder() {
138        ty::ClauseKind::Trait(tr) => tr.self_ty(),
139        ty::ClauseKind::Projection(proj) => proj.projection_term.self_ty(),
140        ty::ClauseKind::TypeOutlives(outlives) => outlives.0,
141        ty::ClauseKind::HostEffect(host) => host.self_ty(),
142        _ => return None,
143    };
144
145    let gat_vars = loop {
146        if let ty::Alias(ty::Projection, alias_ty) = *clause_ty.kind() {
147            if alias_ty.trait_ref(tcx) == item_trait_ref
148                && alias_ty.def_id == assoc_item_def_id.to_def_id()
149            {
150                // We have found the GAT in question...
151                // Return the vars, since we may need to remap them.
152                break &alias_ty.args[item_trait_ref.args.len()..];
153            } else {
154                // Only collect *self* type bounds if the filter is for self.
155                match filter {
156                    PredicateFilter::All => {}
157                    PredicateFilter::SelfOnly => {
158                        return None;
159                    }
160                    PredicateFilter::SelfTraitThatDefines(_)
161                    | PredicateFilter::SelfConstIfConst
162                    | PredicateFilter::SelfAndAssociatedTypeBounds
163                    | PredicateFilter::ConstIfConst => {
164                        unreachable!(
165                            "invalid predicate filter for \
166                            `remap_gat_vars_and_recurse_into_nested_projections`"
167                        )
168                    }
169                }
170
171                clause_ty = alias_ty.self_ty();
172                continue;
173            }
174        }
175
176        return None;
177    };
178
179    // Special-case: No GAT vars, no mapping needed.
180    if gat_vars.is_empty() {
181        return Some((clause, span));
182    }
183
184    // First, check that all of the GAT args are substituted with a unique late-bound arg.
185    // If we find a duplicate, then it can't be mapped to the definition's params.
186    let mut mapping = FxIndexMap::default();
187    let generics = tcx.generics_of(assoc_item_def_id);
188    for (param, var) in std::iter::zip(&generics.own_params, gat_vars) {
189        let existing = match var.kind() {
190            ty::GenericArgKind::Lifetime(re) => {
191                if let ty::RegionKind::ReBound(ty::BoundVarIndexKind::Bound(ty::INNERMOST), bv) =
192                    re.kind()
193                {
194                    mapping.insert(bv.var, tcx.mk_param_from_def(param))
195                } else {
196                    return None;
197                }
198            }
199            ty::GenericArgKind::Type(ty) => {
200                if let ty::Bound(ty::BoundVarIndexKind::Bound(ty::INNERMOST), bv) = *ty.kind() {
201                    mapping.insert(bv.var, tcx.mk_param_from_def(param))
202                } else {
203                    return None;
204                }
205            }
206            ty::GenericArgKind::Const(ct) => {
207                if let ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(ty::INNERMOST), bv) =
208                    ct.kind()
209                {
210                    mapping.insert(bv.var, tcx.mk_param_from_def(param))
211                } else {
212                    return None;
213                }
214            }
215        };
216
217        if existing.is_some() {
218            return None;
219        }
220    }
221
222    // Finally, map all of the args in the GAT to the params we expect, and compress
223    // the remaining late-bound vars so that they count up from var 0.
224    let mut folder =
225        MapAndCompressBoundVars { tcx, binder: ty::INNERMOST, still_bound_vars: vec![], mapping };
226    let pred = clause.kind().skip_binder().fold_with(&mut folder);
227
228    Some((
229        ty::Binder::bind_with_vars(pred, tcx.mk_bound_variable_kinds(&folder.still_bound_vars))
230            .upcast(tcx),
231        span,
232    ))
233}
234
235/// Given some where clause like `for<'b, 'c> <Self as Trait<'a_identity>>::Gat<'b>: Bound<'c>`,
236/// the mapping will map `'b` back to the GAT's `'b_identity`. Then we need to compress the
237/// remaining bound var `'c` to index 0.
238///
239/// This folder gives us: `for<'c> <Self as Trait<'a_identity>>::Gat<'b_identity>: Bound<'c>`,
240/// which is sufficient for an item bound for `Gat`, since all of the GAT's args are identity.
241struct MapAndCompressBoundVars<'tcx> {
242    tcx: TyCtxt<'tcx>,
243    /// How deep are we? Makes sure we don't touch the vars of nested binders.
244    binder: ty::DebruijnIndex,
245    /// List of bound vars that remain unsubstituted because they were not
246    /// mentioned in the GAT's args.
247    still_bound_vars: Vec<ty::BoundVariableKind>,
248    /// Subtle invariant: If the `GenericArg` is bound, then it should be
249    /// stored with the debruijn index of `INNERMOST` so it can be shifted
250    /// correctly during substitution.
251    mapping: FxIndexMap<ty::BoundVar, ty::GenericArg<'tcx>>,
252}
253
254impl<'tcx> TypeFolder<TyCtxt<'tcx>> for MapAndCompressBoundVars<'tcx> {
255    fn cx(&self) -> TyCtxt<'tcx> {
256        self.tcx
257    }
258
259    fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
260    where
261        ty::Binder<'tcx, T>: TypeSuperFoldable<TyCtxt<'tcx>>,
262    {
263        self.binder.shift_in(1);
264        let out = t.super_fold_with(self);
265        self.binder.shift_out(1);
266        out
267    }
268
269    fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
270        if !ty.has_bound_vars() {
271            return ty;
272        }
273
274        if let ty::Bound(ty::BoundVarIndexKind::Bound(binder), old_bound) = *ty.kind()
275            && self.binder == binder
276        {
277            let mapped = if let Some(mapped) = self.mapping.get(&old_bound.var) {
278                mapped.expect_ty()
279            } else {
280                // If we didn't find a mapped generic, then make a new one.
281                // Allocate a new var idx, and insert a new bound ty.
282                let var = ty::BoundVar::from_usize(self.still_bound_vars.len());
283                self.still_bound_vars.push(ty::BoundVariableKind::Ty(old_bound.kind));
284                let mapped = Ty::new_bound(
285                    self.tcx,
286                    ty::INNERMOST,
287                    ty::BoundTy { var, kind: old_bound.kind },
288                );
289                self.mapping.insert(old_bound.var, mapped.into());
290                mapped
291            };
292
293            shift_vars(self.tcx, mapped, self.binder.as_u32())
294        } else {
295            ty.super_fold_with(self)
296        }
297    }
298
299    fn fold_region(&mut self, re: ty::Region<'tcx>) -> ty::Region<'tcx> {
300        if let ty::ReBound(ty::BoundVarIndexKind::Bound(binder), old_bound) = re.kind()
301            && self.binder == binder
302        {
303            let mapped = if let Some(mapped) = self.mapping.get(&old_bound.var) {
304                mapped.expect_region()
305            } else {
306                let var = ty::BoundVar::from_usize(self.still_bound_vars.len());
307                self.still_bound_vars.push(ty::BoundVariableKind::Region(old_bound.kind));
308                let mapped = ty::Region::new_bound(
309                    self.tcx,
310                    ty::INNERMOST,
311                    ty::BoundRegion { var, kind: old_bound.kind },
312                );
313                self.mapping.insert(old_bound.var, mapped.into());
314                mapped
315            };
316
317            shift_vars(self.tcx, mapped, self.binder.as_u32())
318        } else {
319            re
320        }
321    }
322
323    fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
324        if !ct.has_bound_vars() {
325            return ct;
326        }
327
328        if let ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(binder), old_bound) = ct.kind()
329            && self.binder == binder
330        {
331            let mapped = if let Some(mapped) = self.mapping.get(&old_bound.var) {
332                mapped.expect_const()
333            } else {
334                let var = ty::BoundVar::from_usize(self.still_bound_vars.len());
335                self.still_bound_vars.push(ty::BoundVariableKind::Const);
336                let mapped = ty::Const::new_bound(self.tcx, ty::INNERMOST, ty::BoundConst { var });
337                self.mapping.insert(old_bound.var, mapped.into());
338                mapped
339            };
340
341            shift_vars(self.tcx, mapped, self.binder.as_u32())
342        } else {
343            ct.super_fold_with(self)
344        }
345    }
346
347    fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
348        if !p.has_bound_vars() { p } else { p.super_fold_with(self) }
349    }
350}
351
352/// Opaque types don't inherit bounds from their parent: for return position
353/// impl trait it isn't possible to write a suitable predicate on the
354/// containing function and for type-alias impl trait we don't have a backwards
355/// compatibility issue.
356#[instrument(level = "trace", skip(tcx, item_ty))]
357fn opaque_type_bounds<'tcx>(
358    tcx: TyCtxt<'tcx>,
359    opaque_def_id: LocalDefId,
360    hir_bounds: &'tcx [hir::GenericBound<'tcx>],
361    item_ty: Ty<'tcx>,
362    span: Span,
363    filter: PredicateFilter,
364) -> &'tcx [(ty::Clause<'tcx>, Span)] {
365    ty::print::with_reduced_queries!({
366        let icx = ItemCtxt::new(tcx, opaque_def_id);
367        let mut bounds = Vec::new();
368        icx.lowerer().lower_bounds(
369            item_ty,
370            hir_bounds,
371            &mut bounds,
372            ty::List::empty(),
373            filter,
374            OverlappingAsssocItemConstraints::Allowed,
375        );
376        // Implicit bounds are added to opaque types unless a `?Trait` bound is found
377        match filter {
378            PredicateFilter::All
379            | PredicateFilter::SelfOnly
380            | PredicateFilter::SelfTraitThatDefines(_)
381            | PredicateFilter::SelfAndAssociatedTypeBounds => {
382                icx.lowerer().add_implicit_sizedness_bounds(
383                    &mut bounds,
384                    item_ty,
385                    hir_bounds,
386                    ImpliedBoundsContext::AssociatedTypeOrImplTrait,
387                    span,
388                );
389                icx.lowerer().add_default_traits(
390                    &mut bounds,
391                    item_ty,
392                    hir_bounds,
393                    ImpliedBoundsContext::AssociatedTypeOrImplTrait,
394                    span,
395                );
396            }
397            //`ConstIfConst` is only interested in `[const]` bounds.
398            PredicateFilter::ConstIfConst | PredicateFilter::SelfConstIfConst => {}
399        }
400        debug!(?bounds);
401
402        tcx.arena.alloc_slice(&bounds)
403    })
404}
405
406pub(super) fn explicit_item_bounds(
407    tcx: TyCtxt<'_>,
408    def_id: LocalDefId,
409) -> ty::EarlyBinder<'_, &'_ [(ty::Clause<'_>, Span)]> {
410    explicit_item_bounds_with_filter(tcx, def_id, PredicateFilter::All)
411}
412
413pub(super) fn explicit_item_self_bounds(
414    tcx: TyCtxt<'_>,
415    def_id: LocalDefId,
416) -> ty::EarlyBinder<'_, &'_ [(ty::Clause<'_>, Span)]> {
417    explicit_item_bounds_with_filter(tcx, def_id, PredicateFilter::SelfOnly)
418}
419
420pub(super) fn explicit_item_bounds_with_filter(
421    tcx: TyCtxt<'_>,
422    def_id: LocalDefId,
423    filter: PredicateFilter,
424) -> ty::EarlyBinder<'_, &'_ [(ty::Clause<'_>, Span)]> {
425    match tcx.opt_rpitit_info(def_id.to_def_id()) {
426        // RPITIT's bounds are the same as opaque type bounds, but with
427        // a projection self type.
428        Some(ty::ImplTraitInTraitData::Trait { opaque_def_id, .. }) => {
429            let opaque_ty = tcx.hir_node_by_def_id(opaque_def_id.expect_local()).expect_opaque_ty();
430            let bounds =
431                associated_type_bounds(tcx, def_id, opaque_ty.bounds, opaque_ty.span, filter);
432            return ty::EarlyBinder::bind(bounds);
433        }
434        Some(ty::ImplTraitInTraitData::Impl { .. }) => {
435            span_bug!(tcx.def_span(def_id), "RPITIT in impl should not have item bounds")
436        }
437        None => {}
438    }
439
440    let bounds = match tcx.hir_node_by_def_id(def_id) {
441        hir::Node::TraitItem(hir::TraitItem {
442            kind: hir::TraitItemKind::Type(bounds, _),
443            span,
444            ..
445        }) => associated_type_bounds(tcx, def_id, bounds, *span, filter),
446        hir::Node::OpaqueTy(hir::OpaqueTy { bounds, origin, span, .. }) => match origin {
447            // Since RPITITs are lowered as projections in `<dyn HirTyLowerer>::lower_ty`,
448            // when we're asking for the item bounds of the *opaques* in a trait's default
449            // method signature, we need to map these projections back to opaques.
450            rustc_hir::OpaqueTyOrigin::FnReturn {
451                parent,
452                in_trait_or_impl: Some(hir::RpitContext::Trait),
453            }
454            | rustc_hir::OpaqueTyOrigin::AsyncFn {
455                parent,
456                in_trait_or_impl: Some(hir::RpitContext::Trait),
457            } => {
458                let args = GenericArgs::identity_for_item(tcx, def_id);
459                let item_ty = Ty::new_opaque(tcx, def_id.to_def_id(), args);
460                let bounds = &*tcx.arena.alloc_slice(
461                    &opaque_type_bounds(tcx, def_id, bounds, item_ty, *span, filter)
462                        .to_vec()
463                        .fold_with(&mut AssocTyToOpaque { tcx, fn_def_id: parent.to_def_id() }),
464                );
465                assert_only_contains_predicates_from(filter, bounds, item_ty);
466                bounds
467            }
468            rustc_hir::OpaqueTyOrigin::FnReturn {
469                parent: _,
470                in_trait_or_impl: None | Some(hir::RpitContext::TraitImpl),
471            }
472            | rustc_hir::OpaqueTyOrigin::AsyncFn {
473                parent: _,
474                in_trait_or_impl: None | Some(hir::RpitContext::TraitImpl),
475            }
476            | rustc_hir::OpaqueTyOrigin::TyAlias { parent: _, .. } => {
477                let args = GenericArgs::identity_for_item(tcx, def_id);
478                let item_ty = Ty::new_opaque(tcx, def_id.to_def_id(), args);
479                let bounds = opaque_type_bounds(tcx, def_id, bounds, item_ty, *span, filter);
480                assert_only_contains_predicates_from(filter, bounds, item_ty);
481                bounds
482            }
483        },
484        hir::Node::Item(hir::Item { kind: hir::ItemKind::TyAlias(..), .. }) => &[],
485        node => bug!("item_bounds called on {def_id:?} => {node:?}"),
486    };
487
488    ty::EarlyBinder::bind(bounds)
489}
490
491pub(super) fn item_bounds(tcx: TyCtxt<'_>, def_id: DefId) -> ty::EarlyBinder<'_, ty::Clauses<'_>> {
492    tcx.explicit_item_bounds(def_id).map_bound(|bounds| {
493        tcx.mk_clauses_from_iter(util::elaborate(tcx, bounds.iter().map(|&(bound, _span)| bound)))
494    })
495}
496
497pub(super) fn item_self_bounds(
498    tcx: TyCtxt<'_>,
499    def_id: DefId,
500) -> ty::EarlyBinder<'_, ty::Clauses<'_>> {
501    tcx.explicit_item_self_bounds(def_id).map_bound(|bounds| {
502        tcx.mk_clauses_from_iter(
503            util::elaborate(tcx, bounds.iter().map(|&(bound, _span)| bound)).filter_only_self(),
504        )
505    })
506}
507
508/// This exists as an optimization to compute only the item bounds of the item
509/// that are not `Self` bounds.
510pub(super) fn item_non_self_bounds(
511    tcx: TyCtxt<'_>,
512    def_id: DefId,
513) -> ty::EarlyBinder<'_, ty::Clauses<'_>> {
514    let all_bounds: FxIndexSet<_> = tcx.item_bounds(def_id).skip_binder().iter().collect();
515    let own_bounds: FxIndexSet<_> = tcx.item_self_bounds(def_id).skip_binder().iter().collect();
516    if all_bounds.len() == own_bounds.len() {
517        ty::EarlyBinder::bind(ty::ListWithCachedTypeInfo::empty())
518    } else {
519        ty::EarlyBinder::bind(tcx.mk_clauses_from_iter(all_bounds.difference(&own_bounds).copied()))
520    }
521}
522
523/// This exists as an optimization to compute only the supertraits of this impl's
524/// trait that are outlives bounds.
525pub(super) fn impl_super_outlives(
526    tcx: TyCtxt<'_>,
527    def_id: DefId,
528) -> ty::EarlyBinder<'_, ty::Clauses<'_>> {
529    tcx.impl_trait_header(def_id).trait_ref.map_bound(|trait_ref| {
530        let clause: ty::Clause<'_> = trait_ref.upcast(tcx);
531        tcx.mk_clauses_from_iter(util::elaborate(tcx, [clause]).filter(|clause| {
532            matches!(
533                clause.kind().skip_binder(),
534                ty::ClauseKind::TypeOutlives(_) | ty::ClauseKind::RegionOutlives(_)
535            )
536        }))
537    })
538}
539
540struct AssocTyToOpaque<'tcx> {
541    tcx: TyCtxt<'tcx>,
542    fn_def_id: DefId,
543}
544
545impl<'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTyToOpaque<'tcx> {
546    fn cx(&self) -> TyCtxt<'tcx> {
547        self.tcx
548    }
549
550    fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
551        if let ty::Alias(ty::Projection, projection_ty) = ty.kind()
552            && let Some(ty::ImplTraitInTraitData::Trait { fn_def_id, .. }) =
553                self.tcx.opt_rpitit_info(projection_ty.def_id)
554            && fn_def_id == self.fn_def_id
555        {
556            self.tcx.type_of(projection_ty.def_id).instantiate(self.tcx, projection_ty.args)
557        } else {
558            ty.super_fold_with(self)
559        }
560    }
561}
rustc_hir_analysis/collect/item_bounds.rs

rustc_hir_analysis/collect/
item_bounds.rs
