rustc_hir_analysis/collect/
item_bounds.rs

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

rustc_hir_analysis/collect/
item_bounds.rs
