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

rustc_hir_analysis/collect/
item_bounds.rs
