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

rustc_hir_analysis/collect/
item_bounds.rs
