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

rustc_hir_analysis/collect/
item_bounds.rs
