rustc_hir_analysis/hir_ty_lowering/
bounds.rs

1use std::ops::ControlFlow;
2
3use rustc_data_structures::fx::{FxIndexMap, FxIndexSet};
4use rustc_errors::codes::*;
5use rustc_errors::struct_span_code_err;
6use rustc_hir as hir;
7use rustc_hir::def::{DefKind, Res};
8use rustc_hir::def_id::{CRATE_DEF_ID, DefId, LocalDefId};
9use rustc_hir::{AmbigArg, LangItem, PolyTraitRef};
10use rustc_middle::bug;
11use rustc_middle::ty::{
12    self as ty, IsSuggestable, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitableExt,
13    TypeVisitor, Upcast,
14};
15use rustc_span::{ErrorGuaranteed, Ident, Span, Symbol, kw, sym};
16use rustc_trait_selection::traits;
17use smallvec::SmallVec;
18use tracing::{debug, instrument};
19
20use super::errors::GenericsArgsErrExtend;
21use crate::errors;
22use crate::hir_ty_lowering::{
23    AssocItemQSelf, FeedConstTy, HirTyLowerer, PredicateFilter, RegionInferReason,
24};
25
26#[derive(Debug, Default)]
27struct CollectedBound {
28    /// `Trait`
29    positive: bool,
30    /// `?Trait`
31    maybe: bool,
32    /// `!Trait`
33    negative: bool,
34}
35
36impl CollectedBound {
37    /// Returns `true` if any of `Trait`, `?Trait` or `!Trait` were encountered.
38    fn any(&self) -> bool {
39        self.positive || self.maybe || self.negative
40    }
41}
42
43#[derive(Debug)]
44struct CollectedSizednessBounds {
45    // Collected `Sized` bounds
46    sized: CollectedBound,
47    // Collected `MetaSized` bounds
48    meta_sized: CollectedBound,
49    // Collected `PointeeSized` bounds
50    pointee_sized: CollectedBound,
51}
52
53impl CollectedSizednessBounds {
54    /// Returns `true` if any of `Trait`, `?Trait` or `!Trait` were encountered for `Sized`,
55    /// `MetaSized` or `PointeeSized`.
56    fn any(&self) -> bool {
57        self.sized.any() || self.meta_sized.any() || self.pointee_sized.any()
58    }
59}
60
61fn search_bounds_for<'tcx>(
62    hir_bounds: &'tcx [hir::GenericBound<'tcx>],
63    self_ty_where_predicates: Option<(LocalDefId, &'tcx [hir::WherePredicate<'tcx>])>,
64    mut f: impl FnMut(&'tcx PolyTraitRef<'tcx>),
65) {
66    let mut search_bounds = |hir_bounds: &'tcx [hir::GenericBound<'tcx>]| {
67        for hir_bound in hir_bounds {
68            let hir::GenericBound::Trait(ptr) = hir_bound else {
69                continue;
70            };
71
72            f(ptr)
73        }
74    };
75
76    search_bounds(hir_bounds);
77    if let Some((self_ty, where_clause)) = self_ty_where_predicates {
78        for clause in where_clause {
79            if let hir::WherePredicateKind::BoundPredicate(pred) = clause.kind
80                && pred.is_param_bound(self_ty.to_def_id())
81            {
82                search_bounds(pred.bounds);
83            }
84        }
85    }
86}
87
88fn collect_unbounds<'tcx>(
89    hir_bounds: &'tcx [hir::GenericBound<'tcx>],
90    self_ty_where_predicates: Option<(LocalDefId, &'tcx [hir::WherePredicate<'tcx>])>,
91) -> SmallVec<[&'tcx PolyTraitRef<'tcx>; 1]> {
92    let mut unbounds: SmallVec<[_; 1]> = SmallVec::new();
93    search_bounds_for(hir_bounds, self_ty_where_predicates, |ptr| {
94        if matches!(ptr.modifiers.polarity, hir::BoundPolarity::Maybe(_)) {
95            unbounds.push(ptr);
96        }
97    });
98    unbounds
99}
100
101fn collect_bounds<'a, 'tcx>(
102    hir_bounds: &'a [hir::GenericBound<'tcx>],
103    self_ty_where_predicates: Option<(LocalDefId, &'tcx [hir::WherePredicate<'tcx>])>,
104    target_did: DefId,
105) -> CollectedBound {
106    let mut collect_into = CollectedBound::default();
107    search_bounds_for(hir_bounds, self_ty_where_predicates, |ptr| {
108        if !matches!(ptr.trait_ref.path.res, Res::Def(DefKind::Trait, did) if did == target_did) {
109            return;
110        }
111
112        match ptr.modifiers.polarity {
113            hir::BoundPolarity::Maybe(_) => collect_into.maybe = true,
114            hir::BoundPolarity::Negative(_) => collect_into.negative = true,
115            hir::BoundPolarity::Positive => collect_into.positive = true,
116        }
117    });
118    collect_into
119}
120
121fn collect_sizedness_bounds<'tcx>(
122    tcx: TyCtxt<'tcx>,
123    hir_bounds: &'tcx [hir::GenericBound<'tcx>],
124    self_ty_where_predicates: Option<(LocalDefId, &'tcx [hir::WherePredicate<'tcx>])>,
125    span: Span,
126) -> CollectedSizednessBounds {
127    let sized_did = tcx.require_lang_item(LangItem::Sized, span);
128    let sized = collect_bounds(hir_bounds, self_ty_where_predicates, sized_did);
129
130    let meta_sized_did = tcx.require_lang_item(LangItem::MetaSized, span);
131    let meta_sized = collect_bounds(hir_bounds, self_ty_where_predicates, meta_sized_did);
132
133    let pointee_sized_did = tcx.require_lang_item(LangItem::PointeeSized, span);
134    let pointee_sized = collect_bounds(hir_bounds, self_ty_where_predicates, pointee_sized_did);
135
136    CollectedSizednessBounds { sized, meta_sized, pointee_sized }
137}
138
139/// Add a trait bound for `did`.
140fn add_trait_bound<'tcx>(
141    tcx: TyCtxt<'tcx>,
142    bounds: &mut Vec<(ty::Clause<'tcx>, Span)>,
143    self_ty: Ty<'tcx>,
144    did: DefId,
145    span: Span,
146) {
147    let trait_ref = ty::TraitRef::new(tcx, did, [self_ty]);
148    // Preferable to put sizedness obligations first, since we report better errors for `Sized`
149    // ambiguity.
150    bounds.insert(0, (trait_ref.upcast(tcx), span));
151}
152
153impl<'tcx> dyn HirTyLowerer<'tcx> + '_ {
154    /// Skip `PointeeSized` bounds.
155    ///
156    /// `PointeeSized` is a "fake bound" insofar as anywhere a `PointeeSized` bound exists, there
157    /// is actually the absence of any bounds. This avoids limitations around non-global where
158    /// clauses being preferred over item bounds (where `PointeeSized` bounds would be
159    /// proven) - which can result in errors when a `PointeeSized` supertrait/bound/predicate is
160    /// added to some items.
161    pub(crate) fn should_skip_sizedness_bound<'hir>(
162        &self,
163        bound: &'hir hir::GenericBound<'tcx>,
164    ) -> bool {
165        bound
166            .trait_ref()
167            .and_then(|tr| tr.trait_def_id())
168            .map(|did| self.tcx().is_lang_item(did, LangItem::PointeeSized))
169            .unwrap_or(false)
170    }
171
172    /// Adds sizedness bounds to a trait, trait alias, parameter, opaque type or associated type.
173    ///
174    /// - On parameters, opaque type and associated types, add default `Sized` bound if no explicit
175    ///   sizedness bounds are present.
176    /// - On traits and trait aliases, add default `MetaSized` supertrait if no explicit sizedness
177    ///   bounds are present.
178    /// - On parameters, opaque type, associated types and trait aliases, add a `MetaSized` bound if
179    ///   a `?Sized` bound is present.
180    pub(crate) fn add_sizedness_bounds(
181        &self,
182        bounds: &mut Vec<(ty::Clause<'tcx>, Span)>,
183        self_ty: Ty<'tcx>,
184        hir_bounds: &'tcx [hir::GenericBound<'tcx>],
185        self_ty_where_predicates: Option<(LocalDefId, &'tcx [hir::WherePredicate<'tcx>])>,
186        trait_did: Option<LocalDefId>,
187        span: Span,
188    ) {
189        let tcx = self.tcx();
190
191        // Skip adding any default bounds if `#![rustc_no_implicit_bounds]`
192        if tcx.has_attr(CRATE_DEF_ID, sym::rustc_no_implicit_bounds) {
193            return;
194        }
195
196        let meta_sized_did = tcx.require_lang_item(LangItem::MetaSized, span);
197        let pointee_sized_did = tcx.require_lang_item(LangItem::PointeeSized, span);
198
199        // If adding sizedness bounds to a trait, then there are some relevant early exits
200        if let Some(trait_did) = trait_did {
201            let trait_did = trait_did.to_def_id();
202            // Never add a default supertrait to `PointeeSized`.
203            if trait_did == pointee_sized_did {
204                return;
205            }
206            // Don't add default sizedness supertraits to auto traits because it isn't possible to
207            // relax an automatically added supertrait on the defn itself.
208            if tcx.trait_is_auto(trait_did) {
209                return;
210            }
211        } else {
212            // Report invalid unbounds on sizedness-bounded generic parameters.
213            let unbounds = collect_unbounds(hir_bounds, self_ty_where_predicates);
214            self.check_and_report_invalid_unbounds_on_param(unbounds);
215        }
216
217        let collected = collect_sizedness_bounds(tcx, hir_bounds, self_ty_where_predicates, span);
218        if (collected.sized.maybe || collected.sized.negative)
219            && !collected.sized.positive
220            && !collected.meta_sized.any()
221            && !collected.pointee_sized.any()
222        {
223            // `?Sized` is equivalent to `MetaSized` (but only add the bound if there aren't any
224            // other explicit ones) - this can happen for trait aliases as well as bounds.
225            add_trait_bound(tcx, bounds, self_ty, meta_sized_did, span);
226        } else if !collected.any() {
227            if trait_did.is_some() {
228                // If there are no explicit sizedness bounds on a trait then add a default
229                // `MetaSized` supertrait.
230                add_trait_bound(tcx, bounds, self_ty, meta_sized_did, span);
231            } else {
232                // If there are no explicit sizedness bounds on a parameter then add a default
233                // `Sized` bound.
234                let sized_did = tcx.require_lang_item(LangItem::Sized, span);
235                add_trait_bound(tcx, bounds, self_ty, sized_did, span);
236            }
237        }
238    }
239
240    /// Checks whether `Self: DefaultAutoTrait` bounds should be added on trait super bounds
241    /// or associated items.
242    ///
243    /// To keep backward compatibility with existing code, `experimental_default_bounds` bounds
244    /// should be added everywhere, including super bounds. However this causes a huge performance
245    /// costs. For optimization purposes instead of adding default supertraits, bounds
246    /// are added to the associated items:
247    ///
248    /// ```ignore(illustrative)
249    /// // Default bounds are generated in the following way:
250    /// trait Trait {
251    ///     fn foo(&self) where Self: Leak {}
252    /// }
253    ///
254    /// // instead of this:
255    /// trait Trait: Leak {
256    ///     fn foo(&self) {}
257    /// }
258    /// ```
259    /// It is not always possible to do this because of backward compatibility:
260    ///
261    /// ```ignore(illustrative)
262    /// pub trait Trait<Rhs = Self> {}
263    /// pub trait Trait1 : Trait {}
264    /// //~^ ERROR: `Rhs` requires `DefaultAutoTrait`, but `Self` is not `DefaultAutoTrait`
265    /// ```
266    ///
267    /// or:
268    ///
269    /// ```ignore(illustrative)
270    /// trait Trait {
271    ///     type Type where Self: Sized;
272    /// }
273    /// trait Trait2<T> : Trait<Type = T> {}
274    /// //~^ ERROR: `DefaultAutoTrait` required for `Trait2`, by implicit  `Self: DefaultAutoTrait` in `Trait::Type`
275    /// ```
276    ///
277    /// Therefore, `experimental_default_bounds` are still being added to supertraits if
278    /// the `SelfTyParam` or `AssocItemConstraint` were found in a trait header.
279    fn requires_default_supertraits(
280        &self,
281        hir_bounds: &'tcx [hir::GenericBound<'tcx>],
282        hir_generics: &'tcx hir::Generics<'tcx>,
283    ) -> bool {
284        struct TraitInfoCollector;
285
286        impl<'tcx> hir::intravisit::Visitor<'tcx> for TraitInfoCollector {
287            type Result = ControlFlow<()>;
288
289            fn visit_assoc_item_constraint(
290                &mut self,
291                _constraint: &'tcx hir::AssocItemConstraint<'tcx>,
292            ) -> Self::Result {
293                ControlFlow::Break(())
294            }
295
296            fn visit_ty(&mut self, t: &'tcx hir::Ty<'tcx, AmbigArg>) -> Self::Result {
297                if matches!(
298                    &t.kind,
299                    hir::TyKind::Path(hir::QPath::Resolved(
300                        _,
301                        hir::Path { res: hir::def::Res::SelfTyParam { .. }, .. },
302                    ))
303                ) {
304                    return ControlFlow::Break(());
305                }
306                hir::intravisit::walk_ty(self, t)
307            }
308        }
309
310        let mut found = false;
311        for bound in hir_bounds {
312            found |= hir::intravisit::walk_param_bound(&mut TraitInfoCollector, bound).is_break();
313        }
314        found |= hir::intravisit::walk_generics(&mut TraitInfoCollector, hir_generics).is_break();
315        found
316    }
317
318    /// Implicitly add `Self: DefaultAutoTrait` clauses on trait associated items if
319    /// they are not added as super trait bounds to the trait itself. See
320    /// `requires_default_supertraits` for more information.
321    pub(crate) fn add_default_trait_item_bounds(
322        &self,
323        trait_item: &hir::TraitItem<'tcx>,
324        bounds: &mut Vec<(ty::Clause<'tcx>, Span)>,
325    ) {
326        let tcx = self.tcx();
327        if !tcx.sess.opts.unstable_opts.experimental_default_bounds {
328            return;
329        }
330
331        let parent = tcx.local_parent(trait_item.hir_id().owner.def_id);
332        let hir::Node::Item(parent_trait) = tcx.hir_node_by_def_id(parent) else {
333            unreachable!();
334        };
335
336        let (trait_generics, trait_bounds) = match parent_trait.kind {
337            hir::ItemKind::Trait(_, _, _, generics, supertraits, _) => (generics, supertraits),
338            hir::ItemKind::TraitAlias(_, generics, supertraits) => (generics, supertraits),
339            _ => unreachable!(),
340        };
341
342        if !self.requires_default_supertraits(trait_bounds, trait_generics) {
343            let self_ty_where_predicates = (parent, trait_item.generics.predicates);
344            self.add_default_traits(
345                bounds,
346                tcx.types.self_param,
347                &[],
348                Some(self_ty_where_predicates),
349                trait_item.span,
350            );
351        }
352    }
353
354    /// Lazily sets `experimental_default_bounds` to true on trait super bounds.
355    /// See `requires_default_supertraits` for more information.
356    pub(crate) fn add_default_super_traits(
357        &self,
358        trait_def_id: LocalDefId,
359        bounds: &mut Vec<(ty::Clause<'tcx>, Span)>,
360        hir_bounds: &'tcx [hir::GenericBound<'tcx>],
361        hir_generics: &'tcx hir::Generics<'tcx>,
362        span: Span,
363    ) {
364        if !self.tcx().sess.opts.unstable_opts.experimental_default_bounds {
365            return;
366        }
367
368        assert!(matches!(self.tcx().def_kind(trait_def_id), DefKind::Trait | DefKind::TraitAlias));
369        if self.requires_default_supertraits(hir_bounds, hir_generics) {
370            let self_ty_where_predicates = (trait_def_id, hir_generics.predicates);
371            self.add_default_traits(
372                bounds,
373                self.tcx().types.self_param,
374                hir_bounds,
375                Some(self_ty_where_predicates),
376                span,
377            );
378        }
379    }
380
381    pub(crate) fn add_default_traits(
382        &self,
383        bounds: &mut Vec<(ty::Clause<'tcx>, Span)>,
384        self_ty: Ty<'tcx>,
385        hir_bounds: &[hir::GenericBound<'tcx>],
386        self_ty_where_predicates: Option<(LocalDefId, &'tcx [hir::WherePredicate<'tcx>])>,
387        span: Span,
388    ) {
389        self.tcx().default_traits().iter().for_each(|default_trait| {
390            self.add_default_trait(
391                *default_trait,
392                bounds,
393                self_ty,
394                hir_bounds,
395                self_ty_where_predicates,
396                span,
397            );
398        });
399    }
400
401    /// Add a `experimental_default_bounds` bound to the `bounds` if appropriate.
402    ///
403    /// Doesn't add the bound if the HIR bounds contain any of `Trait`, `?Trait` or `!Trait`.
404    pub(crate) fn add_default_trait(
405        &self,
406        trait_: hir::LangItem,
407        bounds: &mut Vec<(ty::Clause<'tcx>, Span)>,
408        self_ty: Ty<'tcx>,
409        hir_bounds: &[hir::GenericBound<'tcx>],
410        self_ty_where_predicates: Option<(LocalDefId, &'tcx [hir::WherePredicate<'tcx>])>,
411        span: Span,
412    ) {
413        let tcx = self.tcx();
414        let trait_id = tcx.lang_items().get(trait_);
415        if let Some(trait_id) = trait_id
416            && self.should_add_default_traits(trait_id, hir_bounds, self_ty_where_predicates)
417        {
418            add_trait_bound(tcx, bounds, self_ty, trait_id, span);
419        }
420    }
421
422    /// Returns `true` if default trait bound should be added.
423    fn should_add_default_traits<'a>(
424        &self,
425        trait_def_id: DefId,
426        hir_bounds: &'a [hir::GenericBound<'tcx>],
427        self_ty_where_predicates: Option<(LocalDefId, &'tcx [hir::WherePredicate<'tcx>])>,
428    ) -> bool {
429        let collected = collect_bounds(hir_bounds, self_ty_where_predicates, trait_def_id);
430        !self.tcx().has_attr(CRATE_DEF_ID, sym::rustc_no_implicit_bounds) && !collected.any()
431    }
432
433    /// Lower HIR bounds into `bounds` given the self type `param_ty` and the overarching late-bound vars if any.
434    ///
435    /// ### Examples
436    ///
437    /// ```ignore (illustrative)
438    /// fn foo<T>() where for<'a> T: Trait<'a> + Copy {}
439    /// //                ^^^^^^^ ^  ^^^^^^^^^^^^^^^^ `hir_bounds`, in HIR form
440    /// //                |       |
441    /// //                |       `param_ty`, in ty form
442    /// //                `bound_vars`, in ty form
443    ///
444    /// fn bar<T>() where T: for<'a> Trait<'a> + Copy {} // no overarching `bound_vars` here!
445    /// //                ^  ^^^^^^^^^^^^^^^^^^^^^^^^ `hir_bounds`, in HIR form
446    /// //                |
447    /// //                `param_ty`, in ty form
448    /// ```
449    ///
450    /// ### A Note on Binders
451    ///
452    /// There is an implied binder around `param_ty` and `hir_bounds`.
453    /// See `lower_poly_trait_ref` for more details.
454    #[instrument(level = "debug", skip(self, hir_bounds, bounds))]
455    pub(crate) fn lower_bounds<'hir, I: IntoIterator<Item = &'hir hir::GenericBound<'tcx>>>(
456        &self,
457        param_ty: Ty<'tcx>,
458        hir_bounds: I,
459        bounds: &mut Vec<(ty::Clause<'tcx>, Span)>,
460        bound_vars: &'tcx ty::List<ty::BoundVariableKind>,
461        predicate_filter: PredicateFilter,
462    ) where
463        'tcx: 'hir,
464    {
465        for hir_bound in hir_bounds {
466            if self.should_skip_sizedness_bound(hir_bound) {
467                continue;
468            }
469
470            // In order to avoid cycles, when we're lowering `SelfTraitThatDefines`,
471            // we skip over any traits that don't define the given associated type.
472            if let PredicateFilter::SelfTraitThatDefines(assoc_ident) = predicate_filter {
473                if let Some(trait_ref) = hir_bound.trait_ref()
474                    && let Some(trait_did) = trait_ref.trait_def_id()
475                    && self.tcx().trait_may_define_assoc_item(trait_did, assoc_ident)
476                {
477                    // Okay
478                } else {
479                    continue;
480                }
481            }
482
483            match hir_bound {
484                hir::GenericBound::Trait(poly_trait_ref) => {
485                    let hir::TraitBoundModifiers { constness, polarity } = poly_trait_ref.modifiers;
486                    let _ = self.lower_poly_trait_ref(
487                        &poly_trait_ref.trait_ref,
488                        poly_trait_ref.span,
489                        constness,
490                        polarity,
491                        param_ty,
492                        bounds,
493                        predicate_filter,
494                    );
495                }
496                hir::GenericBound::Outlives(lifetime) => {
497                    // `ConstIfConst` is only interested in `[const]` bounds.
498                    if matches!(
499                        predicate_filter,
500                        PredicateFilter::ConstIfConst | PredicateFilter::SelfConstIfConst
501                    ) {
502                        continue;
503                    }
504
505                    let region = self.lower_lifetime(lifetime, RegionInferReason::OutlivesBound);
506                    let bound = ty::Binder::bind_with_vars(
507                        ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(param_ty, region)),
508                        bound_vars,
509                    );
510                    bounds.push((bound.upcast(self.tcx()), lifetime.ident.span));
511                }
512                hir::GenericBound::Use(..) => {
513                    // We don't actually lower `use` into the type layer.
514                }
515            }
516        }
517    }
518
519    /// Lower an associated item constraint from the HIR into `bounds`.
520    ///
521    /// ### A Note on Binders
522    ///
523    /// Given something like `T: for<'a> Iterator<Item = &'a u32>`,
524    /// the `trait_ref` here will be `for<'a> T: Iterator`.
525    /// The `constraint` data however is from *inside* the binder
526    /// (e.g., `&'a u32`) and hence may reference bound regions.
527    #[instrument(level = "debug", skip(self, bounds, duplicates, path_span))]
528    pub(super) fn lower_assoc_item_constraint(
529        &self,
530        hir_ref_id: hir::HirId,
531        trait_ref: ty::PolyTraitRef<'tcx>,
532        constraint: &hir::AssocItemConstraint<'tcx>,
533        bounds: &mut Vec<(ty::Clause<'tcx>, Span)>,
534        duplicates: &mut FxIndexMap<DefId, Span>,
535        path_span: Span,
536        predicate_filter: PredicateFilter,
537    ) -> Result<(), ErrorGuaranteed> {
538        let tcx = self.tcx();
539
540        let assoc_tag = if constraint.gen_args.parenthesized
541            == hir::GenericArgsParentheses::ReturnTypeNotation
542        {
543            ty::AssocTag::Fn
544        } else if let hir::AssocItemConstraintKind::Equality { term: hir::Term::Const(_) } =
545            constraint.kind
546        {
547            ty::AssocTag::Const
548        } else {
549            ty::AssocTag::Type
550        };
551
552        // Given something like `U: Trait<T = X>`, we want to produce a predicate like
553        // `<U as Trait>::T = X`.
554        // This is somewhat subtle in the event that `T` is defined in a supertrait of `Trait`,
555        // because in that case we need to upcast. I.e., we want to produce
556        // `<B as SuperTrait<i32>>::T == X` for `B: SubTrait<T = X>` where
557        //
558        //     trait SubTrait: SuperTrait<i32> {}
559        //     trait SuperTrait<A> { type T; }
560        let candidate = if self.probe_trait_that_defines_assoc_item(
561            trait_ref.def_id(),
562            assoc_tag,
563            constraint.ident,
564        ) {
565            // Simple case: The assoc item is defined in the current trait.
566            trait_ref
567        } else {
568            // Otherwise, we have to walk through the supertraits to find
569            // one that does define it.
570            self.probe_single_bound_for_assoc_item(
571                || traits::supertraits(tcx, trait_ref),
572                AssocItemQSelf::Trait(trait_ref.def_id()),
573                assoc_tag,
574                constraint.ident,
575                path_span,
576                Some(constraint),
577            )?
578        };
579
580        let assoc_item = self
581            .probe_assoc_item(
582                constraint.ident,
583                assoc_tag,
584                hir_ref_id,
585                constraint.span,
586                candidate.def_id(),
587            )
588            .expect("failed to find associated item");
589
590        duplicates
591            .entry(assoc_item.def_id)
592            .and_modify(|prev_span| {
593                self.dcx().emit_err(errors::ValueOfAssociatedStructAlreadySpecified {
594                    span: constraint.span,
595                    prev_span: *prev_span,
596                    item_name: constraint.ident,
597                    def_path: tcx.def_path_str(assoc_item.container_id(tcx)),
598                });
599            })
600            .or_insert(constraint.span);
601
602        let projection_term = if let ty::AssocTag::Fn = assoc_tag {
603            let bound_vars = tcx.late_bound_vars(constraint.hir_id);
604            ty::Binder::bind_with_vars(
605                self.lower_return_type_notation_ty(candidate, assoc_item.def_id, path_span)?.into(),
606                bound_vars,
607            )
608        } else {
609            // Create the generic arguments for the associated type or constant by joining the
610            // parent arguments (the arguments of the trait) and the own arguments (the ones of
611            // the associated item itself) and construct an alias type using them.
612            let alias_term = candidate.map_bound(|trait_ref| {
613                let item_segment = hir::PathSegment {
614                    ident: constraint.ident,
615                    hir_id: constraint.hir_id,
616                    res: Res::Err,
617                    args: Some(constraint.gen_args),
618                    infer_args: false,
619                };
620
621                let alias_args = self.lower_generic_args_of_assoc_item(
622                    path_span,
623                    assoc_item.def_id,
624                    &item_segment,
625                    trait_ref.args,
626                );
627                debug!(?alias_args);
628
629                ty::AliasTerm::new_from_args(tcx, assoc_item.def_id, alias_args)
630            });
631
632            // Provide the resolved type of the associated constant to `type_of(AnonConst)`.
633            if let Some(const_arg) = constraint.ct() {
634                if let hir::ConstArgKind::Anon(anon_const) = const_arg.kind {
635                    let ty = alias_term
636                        .map_bound(|alias| tcx.type_of(alias.def_id).instantiate(tcx, alias.args));
637                    let ty = check_assoc_const_binding_type(
638                        self,
639                        constraint.ident,
640                        ty,
641                        constraint.hir_id,
642                    );
643                    tcx.feed_anon_const_type(anon_const.def_id, ty::EarlyBinder::bind(ty));
644                }
645            }
646
647            alias_term
648        };
649
650        match constraint.kind {
651            hir::AssocItemConstraintKind::Equality { .. } if let ty::AssocTag::Fn = assoc_tag => {
652                return Err(self.dcx().emit_err(crate::errors::ReturnTypeNotationEqualityBound {
653                    span: constraint.span,
654                }));
655            }
656            // Lower an equality constraint like `Item = u32` as found in HIR bound `T: Iterator<Item = u32>`
657            // to a projection predicate: `<T as Iterator>::Item = u32`.
658            hir::AssocItemConstraintKind::Equality { term } => {
659                let term = match term {
660                    hir::Term::Ty(ty) => self.lower_ty(ty).into(),
661                    hir::Term::Const(ct) => self.lower_const_arg(ct, FeedConstTy::No).into(),
662                };
663
664                // Find any late-bound regions declared in `ty` that are not
665                // declared in the trait-ref or assoc_item. These are not well-formed.
666                //
667                // Example:
668                //
669                //     for<'a> <T as Iterator>::Item = &'a str // <-- 'a is bad
670                //     for<'a> <T as FnMut<(&'a u32,)>>::Output = &'a str // <-- 'a is ok
671                let late_bound_in_projection_ty =
672                    tcx.collect_constrained_late_bound_regions(projection_term);
673                let late_bound_in_term =
674                    tcx.collect_referenced_late_bound_regions(trait_ref.rebind(term));
675                debug!(?late_bound_in_projection_ty);
676                debug!(?late_bound_in_term);
677
678                // FIXME: point at the type params that don't have appropriate lifetimes:
679                // struct S1<F: for<'a> Fn(&i32, &i32) -> &'a i32>(F);
680                //                         ----  ----     ^^^^^^^
681                // NOTE(associated_const_equality): This error should be impossible to trigger
682                //                                  with associated const equality constraints.
683                self.validate_late_bound_regions(
684                    late_bound_in_projection_ty,
685                    late_bound_in_term,
686                    |br_name| {
687                        struct_span_code_err!(
688                            self.dcx(),
689                            constraint.span,
690                            E0582,
691                            "binding for associated type `{}` references {}, \
692                             which does not appear in the trait input types",
693                            constraint.ident,
694                            br_name
695                        )
696                    },
697                );
698
699                match predicate_filter {
700                    PredicateFilter::All
701                    | PredicateFilter::SelfOnly
702                    | PredicateFilter::SelfAndAssociatedTypeBounds => {
703                        let bound = projection_term.map_bound(|projection_term| {
704                            ty::ClauseKind::Projection(ty::ProjectionPredicate {
705                                projection_term,
706                                term,
707                            })
708                        });
709                        bounds.push((bound.upcast(tcx), constraint.span));
710                    }
711                    // SelfTraitThatDefines is only interested in trait predicates.
712                    PredicateFilter::SelfTraitThatDefines(_) => {}
713                    // `ConstIfConst` is only interested in `[const]` bounds.
714                    PredicateFilter::ConstIfConst | PredicateFilter::SelfConstIfConst => {}
715                }
716            }
717            // Lower a constraint like `Item: Debug` as found in HIR bound `T: Iterator<Item: Debug>`
718            // to a bound involving a projection: `<T as Iterator>::Item: Debug`.
719            hir::AssocItemConstraintKind::Bound { bounds: hir_bounds } => {
720                match predicate_filter {
721                    PredicateFilter::All
722                    | PredicateFilter::SelfAndAssociatedTypeBounds
723                    | PredicateFilter::ConstIfConst => {
724                        let projection_ty = projection_term
725                            .map_bound(|projection_term| projection_term.expect_ty(self.tcx()));
726                        // Calling `skip_binder` is okay, because `lower_bounds` expects the `param_ty`
727                        // parameter to have a skipped binder.
728                        let param_ty =
729                            Ty::new_alias(tcx, ty::Projection, projection_ty.skip_binder());
730                        self.lower_bounds(
731                            param_ty,
732                            hir_bounds,
733                            bounds,
734                            projection_ty.bound_vars(),
735                            predicate_filter,
736                        );
737                    }
738                    PredicateFilter::SelfOnly
739                    | PredicateFilter::SelfTraitThatDefines(_)
740                    | PredicateFilter::SelfConstIfConst => {}
741                }
742            }
743        }
744        Ok(())
745    }
746
747    /// Lower a type, possibly specially handling the type if it's a return type notation
748    /// which we otherwise deny in other positions.
749    pub fn lower_ty_maybe_return_type_notation(&self, hir_ty: &hir::Ty<'tcx>) -> Ty<'tcx> {
750        let hir::TyKind::Path(qpath) = hir_ty.kind else {
751            return self.lower_ty(hir_ty);
752        };
753
754        let tcx = self.tcx();
755        match qpath {
756            hir::QPath::Resolved(opt_self_ty, path)
757                if let [mod_segments @ .., trait_segment, item_segment] = &path.segments[..]
758                    && item_segment.args.is_some_and(|args| {
759                        matches!(
760                            args.parenthesized,
761                            hir::GenericArgsParentheses::ReturnTypeNotation
762                        )
763                    }) =>
764            {
765                // We don't allow generics on the module segments.
766                let _ =
767                    self.prohibit_generic_args(mod_segments.iter(), GenericsArgsErrExtend::None);
768
769                let item_def_id = match path.res {
770                    Res::Def(DefKind::AssocFn, item_def_id) => item_def_id,
771                    Res::Err => {
772                        return Ty::new_error_with_message(
773                            tcx,
774                            hir_ty.span,
775                            "failed to resolve RTN",
776                        );
777                    }
778                    _ => bug!("only expected method resolution for fully qualified RTN"),
779                };
780                let trait_def_id = tcx.parent(item_def_id);
781
782                // Good error for `where Trait::method(..): Send`.
783                let Some(self_ty) = opt_self_ty else {
784                    let guar = self.report_missing_self_ty_for_resolved_path(
785                        trait_def_id,
786                        hir_ty.span,
787                        item_segment,
788                        ty::AssocTag::Type,
789                    );
790                    return Ty::new_error(tcx, guar);
791                };
792                let self_ty = self.lower_ty(self_ty);
793
794                let trait_ref = self.lower_mono_trait_ref(
795                    hir_ty.span,
796                    trait_def_id,
797                    self_ty,
798                    trait_segment,
799                    false,
800                );
801
802                // SUBTLE: As noted at the end of `try_append_return_type_notation_params`
803                // in `resolve_bound_vars`, we stash the explicit bound vars of the where
804                // clause onto the item segment of the RTN type. This allows us to know
805                // how many bound vars are *not* coming from the signature of the function
806                // from lowering RTN itself.
807                //
808                // For example, in `where for<'a> <T as Trait<'a>>::method(..): Other`,
809                // the `late_bound_vars` of the where clause predicate (i.e. this HIR ty's
810                // parent) will include `'a` AND all the early- and late-bound vars of the
811                // method. But when lowering the RTN type, we just want the list of vars
812                // we used to resolve the trait ref. We explicitly stored those back onto
813                // the item segment, since there's no other good place to put them.
814                let candidate =
815                    ty::Binder::bind_with_vars(trait_ref, tcx.late_bound_vars(item_segment.hir_id));
816
817                match self.lower_return_type_notation_ty(candidate, item_def_id, hir_ty.span) {
818                    Ok(ty) => Ty::new_alias(tcx, ty::Projection, ty),
819                    Err(guar) => Ty::new_error(tcx, guar),
820                }
821            }
822            hir::QPath::TypeRelative(hir_self_ty, segment)
823                if segment.args.is_some_and(|args| {
824                    matches!(args.parenthesized, hir::GenericArgsParentheses::ReturnTypeNotation)
825                }) =>
826            {
827                let self_ty = self.lower_ty(hir_self_ty);
828                let (item_def_id, bound) = match self.resolve_type_relative_path(
829                    self_ty,
830                    hir_self_ty,
831                    ty::AssocTag::Fn,
832                    segment,
833                    hir_ty.hir_id,
834                    hir_ty.span,
835                    None,
836                ) {
837                    Ok(result) => result,
838                    Err(guar) => return Ty::new_error(tcx, guar),
839                };
840
841                // Don't let `T::method` resolve to some `for<'a> <T as Tr<'a>>::method`,
842                // which may happen via a higher-ranked where clause or supertrait.
843                // This is the same restrictions as associated types; even though we could
844                // support it, it just makes things a lot more difficult to support in
845                // `resolve_bound_vars`, since we'd need to introduce those as elided
846                // bound vars on the where clause too.
847                if bound.has_bound_vars() {
848                    return Ty::new_error(
849                        tcx,
850                        self.dcx().emit_err(errors::AssociatedItemTraitUninferredGenericParams {
851                            span: hir_ty.span,
852                            inferred_sugg: Some(hir_ty.span.with_hi(segment.ident.span.lo())),
853                            bound: format!("{}::", tcx.anonymize_bound_vars(bound).skip_binder()),
854                            mpart_sugg: None,
855                            what: tcx.def_descr(item_def_id),
856                        }),
857                    );
858                }
859
860                match self.lower_return_type_notation_ty(bound, item_def_id, hir_ty.span) {
861                    Ok(ty) => Ty::new_alias(tcx, ty::Projection, ty),
862                    Err(guar) => Ty::new_error(tcx, guar),
863                }
864            }
865            _ => self.lower_ty(hir_ty),
866        }
867    }
868
869    /// Do the common parts of lowering an RTN type. This involves extending the
870    /// candidate binder to include all of the early- and late-bound vars that are
871    /// defined on the function itself, and constructing a projection to the RPITIT
872    /// return type of that function.
873    fn lower_return_type_notation_ty(
874        &self,
875        candidate: ty::PolyTraitRef<'tcx>,
876        item_def_id: DefId,
877        path_span: Span,
878    ) -> Result<ty::AliasTy<'tcx>, ErrorGuaranteed> {
879        let tcx = self.tcx();
880        let mut emitted_bad_param_err = None;
881        // If we have an method return type bound, then we need to instantiate
882        // the method's early bound params with suitable late-bound params.
883        let mut num_bound_vars = candidate.bound_vars().len();
884        let args = candidate.skip_binder().args.extend_to(tcx, item_def_id, |param, _| {
885            let arg = match param.kind {
886                ty::GenericParamDefKind::Lifetime => ty::Region::new_bound(
887                    tcx,
888                    ty::INNERMOST,
889                    ty::BoundRegion {
890                        var: ty::BoundVar::from_usize(num_bound_vars),
891                        kind: ty::BoundRegionKind::Named(param.def_id, param.name),
892                    },
893                )
894                .into(),
895                ty::GenericParamDefKind::Type { .. } => {
896                    let guar = *emitted_bad_param_err.get_or_insert_with(|| {
897                        self.dcx().emit_err(crate::errors::ReturnTypeNotationIllegalParam::Type {
898                            span: path_span,
899                            param_span: tcx.def_span(param.def_id),
900                        })
901                    });
902                    Ty::new_error(tcx, guar).into()
903                }
904                ty::GenericParamDefKind::Const { .. } => {
905                    let guar = *emitted_bad_param_err.get_or_insert_with(|| {
906                        self.dcx().emit_err(crate::errors::ReturnTypeNotationIllegalParam::Const {
907                            span: path_span,
908                            param_span: tcx.def_span(param.def_id),
909                        })
910                    });
911                    ty::Const::new_error(tcx, guar).into()
912                }
913            };
914            num_bound_vars += 1;
915            arg
916        });
917
918        // Next, we need to check that the return-type notation is being used on
919        // an RPITIT (return-position impl trait in trait) or AFIT (async fn in trait).
920        let output = tcx.fn_sig(item_def_id).skip_binder().output();
921        let output = if let ty::Alias(ty::Projection, alias_ty) = *output.skip_binder().kind()
922            && tcx.is_impl_trait_in_trait(alias_ty.def_id)
923        {
924            alias_ty
925        } else {
926            return Err(self.dcx().emit_err(crate::errors::ReturnTypeNotationOnNonRpitit {
927                span: path_span,
928                ty: tcx.liberate_late_bound_regions(item_def_id, output),
929                fn_span: tcx.hir_span_if_local(item_def_id),
930                note: (),
931            }));
932        };
933
934        // Finally, move the fn return type's bound vars over to account for the early bound
935        // params (and trait ref's late bound params). This logic is very similar to
936        // `rustc_middle::ty::predicate::Clause::instantiate_supertrait`
937        // and it's no coincidence why.
938        let shifted_output = tcx.shift_bound_var_indices(num_bound_vars, output);
939        Ok(ty::EarlyBinder::bind(shifted_output).instantiate(tcx, args))
940    }
941}
942
943/// Detect and reject early-bound & escaping late-bound generic params in the type of assoc const bindings.
944///
945/// FIXME(const_generics): This is a temporary and semi-artificial restriction until the
946/// arrival of *generic const generics*[^1].
947///
948/// It might actually be possible that we can already support early-bound generic params
949/// in such types if we just lifted some more checks in other places, too, for example
950/// inside `HirTyLowerer::lower_anon_const`. However, even if that were the case, we should
951/// probably gate this behind another feature flag.
952///
953/// [^1]: <https://github.com/rust-lang/project-const-generics/issues/28>.
954fn check_assoc_const_binding_type<'tcx>(
955    cx: &dyn HirTyLowerer<'tcx>,
956    assoc_const: Ident,
957    ty: ty::Binder<'tcx, Ty<'tcx>>,
958    hir_id: hir::HirId,
959) -> Ty<'tcx> {
960    // We can't perform the checks for early-bound params during name resolution unlike E0770
961    // because this information depends on *type* resolution.
962    // We can't perform these checks in `resolve_bound_vars` either for the same reason.
963    // Consider the trait ref `for<'a> Trait<'a, C = { &0 }>`. We need to know the fully
964    // resolved type of `Trait::C` in order to know if it references `'a` or not.
965
966    let ty = ty.skip_binder();
967    if !ty.has_param() && !ty.has_escaping_bound_vars() {
968        return ty;
969    }
970
971    let mut collector = GenericParamAndBoundVarCollector {
972        cx,
973        params: Default::default(),
974        vars: Default::default(),
975        depth: ty::INNERMOST,
976    };
977    let mut guar = ty.visit_with(&mut collector).break_value();
978
979    let tcx = cx.tcx();
980    let ty_note = ty
981        .make_suggestable(tcx, false, None)
982        .map(|ty| crate::errors::TyOfAssocConstBindingNote { assoc_const, ty });
983
984    let enclosing_item_owner_id = tcx
985        .hir_parent_owner_iter(hir_id)
986        .find_map(|(owner_id, parent)| parent.generics().map(|_| owner_id))
987        .unwrap();
988    let generics = tcx.generics_of(enclosing_item_owner_id);
989    for index in collector.params {
990        let param = generics.param_at(index as _, tcx);
991        let is_self_param = param.name == kw::SelfUpper;
992        guar.get_or_insert(cx.dcx().emit_err(crate::errors::ParamInTyOfAssocConstBinding {
993            span: assoc_const.span,
994            assoc_const,
995            param_name: param.name,
996            param_def_kind: tcx.def_descr(param.def_id),
997            param_category: if is_self_param {
998                "self"
999            } else if param.kind.is_synthetic() {
1000                "synthetic"
1001            } else {
1002                "normal"
1003            },
1004            param_defined_here_label:
1005                (!is_self_param).then(|| tcx.def_ident_span(param.def_id).unwrap()),
1006            ty_note,
1007        }));
1008    }
1009    for (var_def_id, var_name) in collector.vars {
1010        guar.get_or_insert(cx.dcx().emit_err(
1011            crate::errors::EscapingBoundVarInTyOfAssocConstBinding {
1012                span: assoc_const.span,
1013                assoc_const,
1014                var_name,
1015                var_def_kind: tcx.def_descr(var_def_id),
1016                var_defined_here_label: tcx.def_ident_span(var_def_id).unwrap(),
1017                ty_note,
1018            },
1019        ));
1020    }
1021
1022    let guar = guar.unwrap_or_else(|| bug!("failed to find gen params or bound vars in ty"));
1023    Ty::new_error(tcx, guar)
1024}
1025
1026struct GenericParamAndBoundVarCollector<'a, 'tcx> {
1027    cx: &'a dyn HirTyLowerer<'tcx>,
1028    params: FxIndexSet<u32>,
1029    vars: FxIndexSet<(DefId, Symbol)>,
1030    depth: ty::DebruijnIndex,
1031}
1032
1033impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for GenericParamAndBoundVarCollector<'_, 'tcx> {
1034    type Result = ControlFlow<ErrorGuaranteed>;
1035
1036    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(
1037        &mut self,
1038        binder: &ty::Binder<'tcx, T>,
1039    ) -> Self::Result {
1040        self.depth.shift_in(1);
1041        let result = binder.super_visit_with(self);
1042        self.depth.shift_out(1);
1043        result
1044    }
1045
1046    fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
1047        match ty.kind() {
1048            ty::Param(param) => {
1049                self.params.insert(param.index);
1050            }
1051            ty::Bound(db, bt) if *db >= self.depth => {
1052                self.vars.insert(match bt.kind {
1053                    ty::BoundTyKind::Param(def_id, name) => (def_id, name),
1054                    ty::BoundTyKind::Anon => {
1055                        let reported = self
1056                            .cx
1057                            .dcx()
1058                            .delayed_bug(format!("unexpected anon bound ty: {:?}", bt.var));
1059                        return ControlFlow::Break(reported);
1060                    }
1061                });
1062            }
1063            _ if ty.has_param() || ty.has_bound_vars() => return ty.super_visit_with(self),
1064            _ => {}
1065        }
1066        ControlFlow::Continue(())
1067    }
1068
1069    fn visit_region(&mut self, re: ty::Region<'tcx>) -> Self::Result {
1070        match re.kind() {
1071            ty::ReEarlyParam(param) => {
1072                self.params.insert(param.index);
1073            }
1074            ty::ReBound(db, br) if db >= self.depth => {
1075                self.vars.insert(match br.kind {
1076                    ty::BoundRegionKind::Named(def_id, name) => (def_id, name),
1077                    ty::BoundRegionKind::Anon | ty::BoundRegionKind::ClosureEnv => {
1078                        let guar = self
1079                            .cx
1080                            .dcx()
1081                            .delayed_bug(format!("unexpected bound region kind: {:?}", br.kind));
1082                        return ControlFlow::Break(guar);
1083                    }
1084                });
1085            }
1086            _ => {}
1087        }
1088        ControlFlow::Continue(())
1089    }
1090
1091    fn visit_const(&mut self, ct: ty::Const<'tcx>) -> Self::Result {
1092        match ct.kind() {
1093            ty::ConstKind::Param(param) => {
1094                self.params.insert(param.index);
1095            }
1096            ty::ConstKind::Bound(db, ty::BoundVar { .. }) if db >= self.depth => {
1097                let guar = self.cx.dcx().delayed_bug("unexpected escaping late-bound const var");
1098                return ControlFlow::Break(guar);
1099            }
1100            _ if ct.has_param() || ct.has_bound_vars() => return ct.super_visit_with(self),
1101            _ => {}
1102        }
1103        ControlFlow::Continue(())
1104    }
1105}