rustc_hir_analysis/
collect.rs

1//! "Collection" is the process of determining the type and other external
2//! details of each item in Rust. Collection is specifically concerned
3//! with *inter-procedural* things -- for example, for a function
4//! definition, collection will figure out the type and signature of the
5//! function, but it will not visit the *body* of the function in any way,
6//! nor examine type annotations on local variables (that's the job of
7//! type *checking*).
8//!
9//! Collecting is ultimately defined by a bundle of queries that
10//! inquire after various facts about the items in the crate (e.g.,
11//! `type_of`, `generics_of`, `predicates_of`, etc). See the `provide` function
12//! for the full set.
13//!
14//! At present, however, we do run collection across all items in the
15//! crate as a kind of pass. This should eventually be factored away.
16
17use std::assert_matches::assert_matches;
18use std::cell::Cell;
19use std::iter;
20use std::ops::Bound;
21
22use rustc_abi::ExternAbi;
23use rustc_ast::Recovered;
24use rustc_data_structures::fx::{FxHashSet, FxIndexMap};
25use rustc_data_structures::unord::UnordMap;
26use rustc_errors::{
27    Applicability, Diag, DiagCtxtHandle, E0228, ErrorGuaranteed, StashKey, struct_span_code_err,
28};
29use rustc_hir::def::DefKind;
30use rustc_hir::def_id::{DefId, LocalDefId};
31use rustc_hir::intravisit::{self, InferKind, Visitor, VisitorExt, walk_generics};
32use rustc_hir::{self as hir, GenericParamKind, HirId, Node, PreciseCapturingArgKind};
33use rustc_infer::infer::{InferCtxt, TyCtxtInferExt};
34use rustc_infer::traits::ObligationCause;
35use rustc_middle::hir::nested_filter;
36use rustc_middle::query::Providers;
37use rustc_middle::ty::util::{Discr, IntTypeExt};
38use rustc_middle::ty::{self, AdtKind, Const, IsSuggestable, Ty, TyCtxt, TypingMode, fold_regions};
39use rustc_middle::{bug, span_bug};
40use rustc_span::{DUMMY_SP, Ident, Span, Symbol, kw, sym};
41use rustc_trait_selection::error_reporting::traits::suggestions::NextTypeParamName;
42use rustc_trait_selection::infer::InferCtxtExt;
43use rustc_trait_selection::traits::ObligationCtxt;
44use tracing::{debug, instrument};
45
46use crate::errors;
47use crate::hir_ty_lowering::errors::assoc_tag_str;
48use crate::hir_ty_lowering::{FeedConstTy, HirTyLowerer, RegionInferReason};
49
50pub(crate) mod dump;
51mod generics_of;
52mod item_bounds;
53mod predicates_of;
54mod resolve_bound_vars;
55mod type_of;
56
57///////////////////////////////////////////////////////////////////////////
58
59pub(crate) fn provide(providers: &mut Providers) {
60    resolve_bound_vars::provide(providers);
61    *providers = Providers {
62        type_of: type_of::type_of,
63        type_of_opaque: type_of::type_of_opaque,
64        type_of_opaque_hir_typeck: type_of::type_of_opaque_hir_typeck,
65        type_alias_is_lazy: type_of::type_alias_is_lazy,
66        item_bounds: item_bounds::item_bounds,
67        explicit_item_bounds: item_bounds::explicit_item_bounds,
68        item_self_bounds: item_bounds::item_self_bounds,
69        explicit_item_self_bounds: item_bounds::explicit_item_self_bounds,
70        item_non_self_bounds: item_bounds::item_non_self_bounds,
71        impl_super_outlives: item_bounds::impl_super_outlives,
72        generics_of: generics_of::generics_of,
73        predicates_of: predicates_of::predicates_of,
74        explicit_predicates_of: predicates_of::explicit_predicates_of,
75        explicit_super_predicates_of: predicates_of::explicit_super_predicates_of,
76        explicit_implied_predicates_of: predicates_of::explicit_implied_predicates_of,
77        explicit_supertraits_containing_assoc_item:
78            predicates_of::explicit_supertraits_containing_assoc_item,
79        trait_explicit_predicates_and_bounds: predicates_of::trait_explicit_predicates_and_bounds,
80        const_conditions: predicates_of::const_conditions,
81        explicit_implied_const_bounds: predicates_of::explicit_implied_const_bounds,
82        type_param_predicates: predicates_of::type_param_predicates,
83        trait_def,
84        adt_def,
85        fn_sig,
86        impl_trait_header,
87        coroutine_kind,
88        coroutine_for_closure,
89        opaque_ty_origin,
90        rendered_precise_capturing_args,
91        const_param_default,
92        ..*providers
93    };
94}
95
96///////////////////////////////////////////////////////////////////////////
97
98/// Context specific to some particular item. This is what implements [`HirTyLowerer`].
99///
100/// # `ItemCtxt` vs `FnCtxt`
101///
102/// `ItemCtxt` is primarily used to type-check item signatures and lower them
103/// from HIR to their [`ty::Ty`] representation, which is exposed using [`HirTyLowerer`].
104/// It's also used for the bodies of items like structs where the body (the fields)
105/// are just signatures.
106///
107/// This is in contrast to `FnCtxt`, which is used to type-check bodies of
108/// functions, closures, and `const`s -- anywhere that expressions and statements show up.
109///
110/// An important thing to note is that `ItemCtxt` does no inference -- it has no [`InferCtxt`] --
111/// while `FnCtxt` does do inference.
112///
113/// [`InferCtxt`]: rustc_infer::infer::InferCtxt
114///
115/// # Trait predicates
116///
117/// `ItemCtxt` has information about the predicates that are defined
118/// on the trait. Unfortunately, this predicate information is
119/// available in various different forms at various points in the
120/// process. So we can't just store a pointer to e.g., the HIR or the
121/// parsed ty form, we have to be more flexible. To this end, the
122/// `ItemCtxt` is parameterized by a `DefId` that it uses to satisfy
123/// `probe_ty_param_bounds` requests, drawing the information from
124/// the HIR (`hir::Generics`), recursively.
125pub(crate) struct ItemCtxt<'tcx> {
126    tcx: TyCtxt<'tcx>,
127    item_def_id: LocalDefId,
128    tainted_by_errors: Cell<Option<ErrorGuaranteed>>,
129}
130
131///////////////////////////////////////////////////////////////////////////
132
133#[derive(Default)]
134pub(crate) struct HirPlaceholderCollector {
135    pub spans: Vec<Span>,
136    // If any of the spans points to a const infer var, then suppress any messages
137    // that may try to turn that const infer into a type parameter.
138    pub may_contain_const_infer: bool,
139}
140
141impl<'v> Visitor<'v> for HirPlaceholderCollector {
142    fn visit_infer(&mut self, _inf_id: HirId, inf_span: Span, kind: InferKind<'v>) -> Self::Result {
143        self.spans.push(inf_span);
144
145        if let InferKind::Const(_) | InferKind::Ambig(_) = kind {
146            self.may_contain_const_infer = true;
147        }
148    }
149}
150
151pub(crate) struct CollectItemTypesVisitor<'tcx> {
152    pub tcx: TyCtxt<'tcx>,
153}
154
155/// If there are any placeholder types (`_`), emit an error explaining that this is not allowed
156/// and suggest adding type parameters in the appropriate place, taking into consideration any and
157/// all already existing generic type parameters to avoid suggesting a name that is already in use.
158pub(crate) fn placeholder_type_error<'tcx>(
159    cx: &dyn HirTyLowerer<'tcx>,
160    generics: Option<&hir::Generics<'_>>,
161    placeholder_types: Vec<Span>,
162    suggest: bool,
163    hir_ty: Option<&hir::Ty<'_>>,
164    kind: &'static str,
165) {
166    if placeholder_types.is_empty() {
167        return;
168    }
169
170    placeholder_type_error_diag(cx, generics, placeholder_types, vec![], suggest, hir_ty, kind)
171        .emit();
172}
173
174pub(crate) fn placeholder_type_error_diag<'cx, 'tcx>(
175    cx: &'cx dyn HirTyLowerer<'tcx>,
176    generics: Option<&hir::Generics<'_>>,
177    placeholder_types: Vec<Span>,
178    additional_spans: Vec<Span>,
179    suggest: bool,
180    hir_ty: Option<&hir::Ty<'_>>,
181    kind: &'static str,
182) -> Diag<'cx> {
183    if placeholder_types.is_empty() {
184        return bad_placeholder(cx, additional_spans, kind);
185    }
186
187    let params = generics.map(|g| g.params).unwrap_or_default();
188    let type_name = params.next_type_param_name(None);
189    let mut sugg: Vec<_> =
190        placeholder_types.iter().map(|sp| (*sp, (*type_name).to_string())).collect();
191
192    if let Some(generics) = generics {
193        if let Some(span) = params.iter().find_map(|arg| match arg.name {
194            hir::ParamName::Plain(Ident { name: kw::Underscore, span }) => Some(span),
195            _ => None,
196        }) {
197            // Account for `_` already present in cases like `struct S<_>(_);` and suggest
198            // `struct S<T>(T);` instead of `struct S<_, T>(T);`.
199            sugg.push((span, (*type_name).to_string()));
200        } else if let Some(span) = generics.span_for_param_suggestion() {
201            // Account for bounds, we want `fn foo<T: E, K>(_: K)` not `fn foo<T, K: E>(_: K)`.
202            sugg.push((span, format!(", {type_name}")));
203        } else {
204            sugg.push((generics.span, format!("<{type_name}>")));
205        }
206    }
207
208    let mut err =
209        bad_placeholder(cx, placeholder_types.into_iter().chain(additional_spans).collect(), kind);
210
211    // Suggest, but only if it is not a function in const or static
212    if suggest {
213        let mut is_fn = false;
214        let mut is_const_or_static = false;
215
216        if let Some(hir_ty) = hir_ty
217            && let hir::TyKind::BareFn(_) = hir_ty.kind
218        {
219            is_fn = true;
220
221            // Check if parent is const or static
222            is_const_or_static = matches!(
223                cx.tcx().parent_hir_node(hir_ty.hir_id),
224                Node::Item(&hir::Item {
225                    kind: hir::ItemKind::Const(..) | hir::ItemKind::Static(..),
226                    ..
227                }) | Node::TraitItem(&hir::TraitItem { kind: hir::TraitItemKind::Const(..), .. })
228                    | Node::ImplItem(&hir::ImplItem { kind: hir::ImplItemKind::Const(..), .. })
229            );
230        }
231
232        // if function is wrapped around a const or static,
233        // then don't show the suggestion
234        if !(is_fn && is_const_or_static) {
235            err.multipart_suggestion(
236                "use type parameters instead",
237                sugg,
238                Applicability::HasPlaceholders,
239            );
240        }
241    }
242
243    err
244}
245
246fn reject_placeholder_type_signatures_in_item<'tcx>(
247    tcx: TyCtxt<'tcx>,
248    item: &'tcx hir::Item<'tcx>,
249) {
250    let (generics, suggest) = match &item.kind {
251        hir::ItemKind::Union(_, _, generics)
252        | hir::ItemKind::Enum(_, _, generics)
253        | hir::ItemKind::TraitAlias(_, generics, _)
254        | hir::ItemKind::Trait(_, _, _, generics, ..)
255        | hir::ItemKind::Impl(hir::Impl { generics, .. })
256        | hir::ItemKind::Struct(_, _, generics) => (generics, true),
257        hir::ItemKind::TyAlias(_, _, generics) => (generics, false),
258        // `static`, `fn` and `const` are handled elsewhere to suggest appropriate type.
259        _ => return,
260    };
261
262    let mut visitor = HirPlaceholderCollector::default();
263    visitor.visit_item(item);
264
265    let icx = ItemCtxt::new(tcx, item.owner_id.def_id);
266
267    placeholder_type_error(
268        icx.lowerer(),
269        Some(generics),
270        visitor.spans,
271        suggest && !visitor.may_contain_const_infer,
272        None,
273        item.kind.descr(),
274    );
275}
276
277impl<'tcx> Visitor<'tcx> for CollectItemTypesVisitor<'tcx> {
278    type NestedFilter = nested_filter::OnlyBodies;
279
280    fn maybe_tcx(&mut self) -> Self::MaybeTyCtxt {
281        self.tcx
282    }
283
284    fn visit_item(&mut self, item: &'tcx hir::Item<'tcx>) {
285        lower_item(self.tcx, item.item_id());
286        reject_placeholder_type_signatures_in_item(self.tcx, item);
287        intravisit::walk_item(self, item);
288    }
289
290    fn visit_generics(&mut self, generics: &'tcx hir::Generics<'tcx>) {
291        for param in generics.params {
292            match param.kind {
293                hir::GenericParamKind::Lifetime { .. } => {}
294                hir::GenericParamKind::Type { default: Some(_), .. } => {
295                    self.tcx.ensure_ok().type_of(param.def_id);
296                }
297                hir::GenericParamKind::Type { .. } => {}
298                hir::GenericParamKind::Const { default, .. } => {
299                    self.tcx.ensure_ok().type_of(param.def_id);
300                    if let Some(default) = default {
301                        // need to store default and type of default
302                        self.tcx.ensure_ok().const_param_default(param.def_id);
303                        if let hir::ConstArgKind::Anon(ac) = default.kind {
304                            self.tcx.ensure_ok().type_of(ac.def_id);
305                        }
306                    }
307                }
308            }
309        }
310        intravisit::walk_generics(self, generics);
311    }
312
313    fn visit_expr(&mut self, expr: &'tcx hir::Expr<'tcx>) {
314        if let hir::ExprKind::Closure(closure) = expr.kind {
315            self.tcx.ensure_ok().generics_of(closure.def_id);
316            self.tcx.ensure_ok().codegen_fn_attrs(closure.def_id);
317            // We do not call `type_of` for closures here as that
318            // depends on typecheck and would therefore hide
319            // any further errors in case one typeck fails.
320        }
321        intravisit::walk_expr(self, expr);
322    }
323
324    /// Don't call `type_of` on opaque types, since that depends on type checking function bodies.
325    /// `check_item_type` ensures that it's called instead.
326    fn visit_opaque_ty(&mut self, opaque: &'tcx hir::OpaqueTy<'tcx>) {
327        let def_id = opaque.def_id;
328        self.tcx.ensure_ok().generics_of(def_id);
329        self.tcx.ensure_ok().predicates_of(def_id);
330        self.tcx.ensure_ok().explicit_item_bounds(def_id);
331        self.tcx.ensure_ok().explicit_item_self_bounds(def_id);
332        self.tcx.ensure_ok().item_bounds(def_id);
333        self.tcx.ensure_ok().item_self_bounds(def_id);
334        if self.tcx.is_conditionally_const(def_id) {
335            self.tcx.ensure_ok().explicit_implied_const_bounds(def_id);
336            self.tcx.ensure_ok().const_conditions(def_id);
337        }
338        intravisit::walk_opaque_ty(self, opaque);
339    }
340
341    fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem<'tcx>) {
342        lower_trait_item(self.tcx, trait_item.trait_item_id());
343        intravisit::walk_trait_item(self, trait_item);
344    }
345
346    fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem<'tcx>) {
347        lower_impl_item(self.tcx, impl_item.impl_item_id());
348        intravisit::walk_impl_item(self, impl_item);
349    }
350}
351
352///////////////////////////////////////////////////////////////////////////
353// Utility types and common code for the above passes.
354
355fn bad_placeholder<'cx, 'tcx>(
356    cx: &'cx dyn HirTyLowerer<'tcx>,
357    mut spans: Vec<Span>,
358    kind: &'static str,
359) -> Diag<'cx> {
360    let kind = if kind.ends_with('s') { format!("{kind}es") } else { format!("{kind}s") };
361
362    spans.sort();
363    cx.dcx().create_err(errors::PlaceholderNotAllowedItemSignatures { spans, kind })
364}
365
366impl<'tcx> ItemCtxt<'tcx> {
367    pub(crate) fn new(tcx: TyCtxt<'tcx>, item_def_id: LocalDefId) -> ItemCtxt<'tcx> {
368        ItemCtxt { tcx, item_def_id, tainted_by_errors: Cell::new(None) }
369    }
370
371    pub(crate) fn lower_ty(&self, hir_ty: &hir::Ty<'tcx>) -> Ty<'tcx> {
372        self.lowerer().lower_ty(hir_ty)
373    }
374
375    pub(crate) fn hir_id(&self) -> hir::HirId {
376        self.tcx.local_def_id_to_hir_id(self.item_def_id)
377    }
378
379    pub(crate) fn node(&self) -> hir::Node<'tcx> {
380        self.tcx.hir_node(self.hir_id())
381    }
382
383    fn check_tainted_by_errors(&self) -> Result<(), ErrorGuaranteed> {
384        match self.tainted_by_errors.get() {
385            Some(err) => Err(err),
386            None => Ok(()),
387        }
388    }
389}
390
391impl<'tcx> HirTyLowerer<'tcx> for ItemCtxt<'tcx> {
392    fn tcx(&self) -> TyCtxt<'tcx> {
393        self.tcx
394    }
395
396    fn dcx(&self) -> DiagCtxtHandle<'_> {
397        self.tcx.dcx().taintable_handle(&self.tainted_by_errors)
398    }
399
400    fn item_def_id(&self) -> LocalDefId {
401        self.item_def_id
402    }
403
404    fn re_infer(&self, span: Span, reason: RegionInferReason<'_>) -> ty::Region<'tcx> {
405        if let RegionInferReason::ObjectLifetimeDefault = reason {
406            let e = struct_span_code_err!(
407                self.dcx(),
408                span,
409                E0228,
410                "the lifetime bound for this object type cannot be deduced \
411                from context; please supply an explicit bound"
412            )
413            .emit();
414            ty::Region::new_error(self.tcx(), e)
415        } else {
416            // This indicates an illegal lifetime in a non-assoc-trait position
417            ty::Region::new_error_with_message(self.tcx(), span, "unelided lifetime in signature")
418        }
419    }
420
421    fn ty_infer(&self, _: Option<&ty::GenericParamDef>, span: Span) -> Ty<'tcx> {
422        Ty::new_error_with_message(self.tcx(), span, "bad placeholder type")
423    }
424
425    fn ct_infer(&self, _: Option<&ty::GenericParamDef>, span: Span) -> Const<'tcx> {
426        ty::Const::new_error_with_message(self.tcx(), span, "bad placeholder constant")
427    }
428
429    fn register_trait_ascription_bounds(
430        &self,
431        _: Vec<(ty::Clause<'tcx>, Span)>,
432        _: HirId,
433        span: Span,
434    ) {
435        self.dcx().span_delayed_bug(span, "trait ascription type not allowed here");
436    }
437
438    fn probe_ty_param_bounds(
439        &self,
440        span: Span,
441        def_id: LocalDefId,
442        assoc_ident: Ident,
443    ) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> {
444        self.tcx.at(span).type_param_predicates((self.item_def_id, def_id, assoc_ident))
445    }
446
447    fn lower_assoc_shared(
448        &self,
449        span: Span,
450        item_def_id: DefId,
451        item_segment: &rustc_hir::PathSegment<'tcx>,
452        poly_trait_ref: ty::PolyTraitRef<'tcx>,
453        assoc_tag: ty::AssocTag,
454    ) -> Result<(DefId, ty::GenericArgsRef<'tcx>), ErrorGuaranteed> {
455        if let Some(trait_ref) = poly_trait_ref.no_bound_vars() {
456            let item_args = self.lowerer().lower_generic_args_of_assoc_item(
457                span,
458                item_def_id,
459                item_segment,
460                trait_ref.args,
461            );
462            Ok((item_def_id, item_args))
463        } else {
464            // There are no late-bound regions; we can just ignore the binder.
465            let (mut mpart_sugg, mut inferred_sugg) = (None, None);
466            let mut bound = String::new();
467
468            match self.node() {
469                hir::Node::Field(_) | hir::Node::Ctor(_) | hir::Node::Variant(_) => {
470                    let item = self
471                        .tcx
472                        .hir_expect_item(self.tcx.hir_get_parent_item(self.hir_id()).def_id);
473                    match &item.kind {
474                        hir::ItemKind::Enum(_, _, generics)
475                        | hir::ItemKind::Struct(_, _, generics)
476                        | hir::ItemKind::Union(_, _, generics) => {
477                            let lt_name = get_new_lifetime_name(self.tcx, poly_trait_ref, generics);
478                            let (lt_sp, sugg) = match generics.params {
479                                [] => (generics.span, format!("<{lt_name}>")),
480                                [bound, ..] => (bound.span.shrink_to_lo(), format!("{lt_name}, ")),
481                            };
482                            mpart_sugg = Some(errors::AssociatedItemTraitUninferredGenericParamsMultipartSuggestion {
483                                fspan: lt_sp,
484                                first: sugg,
485                                sspan: span.with_hi(item_segment.ident.span.lo()),
486                                second: format!(
487                                    "{}::",
488                                    // Replace the existing lifetimes with a new named lifetime.
489                                    self.tcx.instantiate_bound_regions_uncached(
490                                        poly_trait_ref,
491                                        |_| {
492                                            ty::Region::new_early_param(self.tcx, ty::EarlyParamRegion {
493                                                index: 0,
494                                                name: Symbol::intern(&lt_name),
495                                            })
496                                        }
497                                    ),
498                                ),
499                            });
500                        }
501                        _ => {}
502                    }
503                }
504                hir::Node::Item(hir::Item {
505                    kind:
506                        hir::ItemKind::Struct(..) | hir::ItemKind::Enum(..) | hir::ItemKind::Union(..),
507                    ..
508                }) => {}
509                hir::Node::Item(_)
510                | hir::Node::ForeignItem(_)
511                | hir::Node::TraitItem(_)
512                | hir::Node::ImplItem(_) => {
513                    inferred_sugg = Some(span.with_hi(item_segment.ident.span.lo()));
514                    bound = format!(
515                        "{}::",
516                        // Erase named lt, we want `<A as B<'_>::C`, not `<A as B<'a>::C`.
517                        self.tcx.anonymize_bound_vars(poly_trait_ref).skip_binder(),
518                    );
519                }
520                _ => {}
521            }
522
523            Err(self.tcx().dcx().emit_err(errors::AssociatedItemTraitUninferredGenericParams {
524                span,
525                inferred_sugg,
526                bound,
527                mpart_sugg,
528                what: assoc_tag_str(assoc_tag),
529            }))
530        }
531    }
532
533    fn probe_adt(&self, _span: Span, ty: Ty<'tcx>) -> Option<ty::AdtDef<'tcx>> {
534        // FIXME(#103640): Should we handle the case where `ty` is a projection?
535        ty.ty_adt_def()
536    }
537
538    fn record_ty(&self, _hir_id: hir::HirId, _ty: Ty<'tcx>, _span: Span) {
539        // There's no place to record types from signatures?
540    }
541
542    fn infcx(&self) -> Option<&InferCtxt<'tcx>> {
543        None
544    }
545
546    fn lower_fn_sig(
547        &self,
548        decl: &hir::FnDecl<'tcx>,
549        generics: Option<&hir::Generics<'_>>,
550        hir_id: rustc_hir::HirId,
551        hir_ty: Option<&hir::Ty<'_>>,
552    ) -> (Vec<Ty<'tcx>>, Ty<'tcx>) {
553        let tcx = self.tcx();
554        // We proactively collect all the inferred type params to emit a single error per fn def.
555        let mut visitor = HirPlaceholderCollector::default();
556        let mut infer_replacements = vec![];
557
558        if let Some(generics) = generics {
559            walk_generics(&mut visitor, generics);
560        }
561
562        let input_tys = decl
563            .inputs
564            .iter()
565            .enumerate()
566            .map(|(i, a)| {
567                if let hir::TyKind::Infer(()) = a.kind {
568                    if let Some(suggested_ty) =
569                        self.lowerer().suggest_trait_fn_ty_for_impl_fn_infer(hir_id, Some(i))
570                    {
571                        infer_replacements.push((a.span, suggested_ty.to_string()));
572                        return Ty::new_error_with_message(tcx, a.span, suggested_ty.to_string());
573                    }
574                }
575
576                // Only visit the type looking for `_` if we didn't fix the type above
577                visitor.visit_ty_unambig(a);
578                self.lowerer().lower_arg_ty(a, None)
579            })
580            .collect();
581
582        let output_ty = match decl.output {
583            hir::FnRetTy::Return(output) => {
584                if let hir::TyKind::Infer(()) = output.kind
585                    && let Some(suggested_ty) =
586                        self.lowerer().suggest_trait_fn_ty_for_impl_fn_infer(hir_id, None)
587                {
588                    infer_replacements.push((output.span, suggested_ty.to_string()));
589                    Ty::new_error_with_message(tcx, output.span, suggested_ty.to_string())
590                } else {
591                    visitor.visit_ty_unambig(output);
592                    self.lower_ty(output)
593                }
594            }
595            hir::FnRetTy::DefaultReturn(..) => tcx.types.unit,
596        };
597
598        if !(visitor.spans.is_empty() && infer_replacements.is_empty()) {
599            // We check for the presence of
600            // `ident_span` to not emit an error twice when we have `fn foo(_: fn() -> _)`.
601
602            let mut diag = crate::collect::placeholder_type_error_diag(
603                self,
604                generics,
605                visitor.spans,
606                infer_replacements.iter().map(|(s, _)| *s).collect(),
607                !visitor.may_contain_const_infer,
608                hir_ty,
609                "function",
610            );
611
612            if !infer_replacements.is_empty() {
613                diag.multipart_suggestion(
614                    format!(
615                        "try replacing `_` with the type{} in the corresponding trait method \
616                         signature",
617                        rustc_errors::pluralize!(infer_replacements.len()),
618                    ),
619                    infer_replacements,
620                    Applicability::MachineApplicable,
621                );
622            }
623
624            diag.emit();
625        }
626
627        (input_tys, output_ty)
628    }
629}
630
631/// Synthesize a new lifetime name that doesn't clash with any of the lifetimes already present.
632fn get_new_lifetime_name<'tcx>(
633    tcx: TyCtxt<'tcx>,
634    poly_trait_ref: ty::PolyTraitRef<'tcx>,
635    generics: &hir::Generics<'tcx>,
636) -> String {
637    let existing_lifetimes = tcx
638        .collect_referenced_late_bound_regions(poly_trait_ref)
639        .into_iter()
640        .filter_map(|lt| {
641            if let ty::BoundRegionKind::Named(_, name) = lt {
642                Some(name.as_str().to_string())
643            } else {
644                None
645            }
646        })
647        .chain(generics.params.iter().filter_map(|param| {
648            if let hir::GenericParamKind::Lifetime { .. } = &param.kind {
649                Some(param.name.ident().as_str().to_string())
650            } else {
651                None
652            }
653        }))
654        .collect::<FxHashSet<String>>();
655
656    let a_to_z_repeat_n = |n| {
657        (b'a'..=b'z').map(move |c| {
658            let mut s = '\''.to_string();
659            s.extend(std::iter::repeat(char::from(c)).take(n));
660            s
661        })
662    };
663
664    // If all single char lifetime names are present, we wrap around and double the chars.
665    (1..).flat_map(a_to_z_repeat_n).find(|lt| !existing_lifetimes.contains(lt.as_str())).unwrap()
666}
667
668#[instrument(level = "debug", skip_all)]
669fn lower_item(tcx: TyCtxt<'_>, item_id: hir::ItemId) {
670    let it = tcx.hir_item(item_id);
671    debug!(item = ?it.kind.ident(), id = %it.hir_id());
672    let def_id = item_id.owner_id.def_id;
673    let icx = ItemCtxt::new(tcx, def_id);
674
675    match &it.kind {
676        // These don't define types.
677        hir::ItemKind::ExternCrate(..)
678        | hir::ItemKind::Use(..)
679        | hir::ItemKind::Macro(..)
680        | hir::ItemKind::Mod(..)
681        | hir::ItemKind::GlobalAsm { .. } => {}
682        hir::ItemKind::ForeignMod { items, .. } => {
683            for item in *items {
684                let item = tcx.hir_foreign_item(item.id);
685                tcx.ensure_ok().generics_of(item.owner_id);
686                tcx.ensure_ok().type_of(item.owner_id);
687                tcx.ensure_ok().predicates_of(item.owner_id);
688                if tcx.is_conditionally_const(def_id) {
689                    tcx.ensure_ok().explicit_implied_const_bounds(def_id);
690                    tcx.ensure_ok().const_conditions(def_id);
691                }
692                match item.kind {
693                    hir::ForeignItemKind::Fn(..) => {
694                        tcx.ensure_ok().codegen_fn_attrs(item.owner_id);
695                        tcx.ensure_ok().fn_sig(item.owner_id)
696                    }
697                    hir::ForeignItemKind::Static(..) => {
698                        tcx.ensure_ok().codegen_fn_attrs(item.owner_id);
699                        let mut visitor = HirPlaceholderCollector::default();
700                        visitor.visit_foreign_item(item);
701                        placeholder_type_error(
702                            icx.lowerer(),
703                            None,
704                            visitor.spans,
705                            false,
706                            None,
707                            "static variable",
708                        );
709                    }
710                    _ => (),
711                }
712            }
713        }
714        hir::ItemKind::Enum(..) => {
715            tcx.ensure_ok().generics_of(def_id);
716            tcx.ensure_ok().type_of(def_id);
717            tcx.ensure_ok().predicates_of(def_id);
718            lower_enum_variant_types(tcx, def_id.to_def_id());
719        }
720        hir::ItemKind::Impl { .. } => {
721            tcx.ensure_ok().generics_of(def_id);
722            tcx.ensure_ok().type_of(def_id);
723            tcx.ensure_ok().impl_trait_header(def_id);
724            tcx.ensure_ok().predicates_of(def_id);
725            tcx.ensure_ok().associated_items(def_id);
726        }
727        hir::ItemKind::Trait(..) => {
728            tcx.ensure_ok().generics_of(def_id);
729            tcx.ensure_ok().trait_def(def_id);
730            tcx.at(it.span).explicit_super_predicates_of(def_id);
731            tcx.ensure_ok().predicates_of(def_id);
732            tcx.ensure_ok().associated_items(def_id);
733        }
734        hir::ItemKind::TraitAlias(..) => {
735            tcx.ensure_ok().generics_of(def_id);
736            tcx.at(it.span).explicit_implied_predicates_of(def_id);
737            tcx.at(it.span).explicit_super_predicates_of(def_id);
738            tcx.ensure_ok().predicates_of(def_id);
739        }
740        hir::ItemKind::Struct(_, struct_def, _) | hir::ItemKind::Union(_, struct_def, _) => {
741            tcx.ensure_ok().generics_of(def_id);
742            tcx.ensure_ok().type_of(def_id);
743            tcx.ensure_ok().predicates_of(def_id);
744
745            for f in struct_def.fields() {
746                tcx.ensure_ok().generics_of(f.def_id);
747                tcx.ensure_ok().type_of(f.def_id);
748                tcx.ensure_ok().predicates_of(f.def_id);
749            }
750
751            if let Some(ctor_def_id) = struct_def.ctor_def_id() {
752                lower_variant_ctor(tcx, ctor_def_id);
753            }
754        }
755
756        hir::ItemKind::TyAlias(..) => {
757            tcx.ensure_ok().generics_of(def_id);
758            tcx.ensure_ok().type_of(def_id);
759            tcx.ensure_ok().predicates_of(def_id);
760        }
761
762        hir::ItemKind::Static(_, ty, ..) | hir::ItemKind::Const(_, ty, ..) => {
763            tcx.ensure_ok().generics_of(def_id);
764            tcx.ensure_ok().type_of(def_id);
765            tcx.ensure_ok().predicates_of(def_id);
766            if !ty.is_suggestable_infer_ty() {
767                let mut visitor = HirPlaceholderCollector::default();
768                visitor.visit_item(it);
769                placeholder_type_error(
770                    icx.lowerer(),
771                    None,
772                    visitor.spans,
773                    false,
774                    None,
775                    it.kind.descr(),
776                );
777            }
778        }
779
780        hir::ItemKind::Fn { .. } => {
781            tcx.ensure_ok().generics_of(def_id);
782            tcx.ensure_ok().type_of(def_id);
783            tcx.ensure_ok().predicates_of(def_id);
784            tcx.ensure_ok().fn_sig(def_id);
785            tcx.ensure_ok().codegen_fn_attrs(def_id);
786        }
787    }
788}
789
790fn lower_trait_item(tcx: TyCtxt<'_>, trait_item_id: hir::TraitItemId) {
791    let trait_item = tcx.hir_trait_item(trait_item_id);
792    let def_id = trait_item_id.owner_id;
793    tcx.ensure_ok().generics_of(def_id);
794    let icx = ItemCtxt::new(tcx, def_id.def_id);
795
796    match trait_item.kind {
797        hir::TraitItemKind::Fn(..) => {
798            tcx.ensure_ok().codegen_fn_attrs(def_id);
799            tcx.ensure_ok().type_of(def_id);
800            tcx.ensure_ok().fn_sig(def_id);
801        }
802
803        hir::TraitItemKind::Const(ty, body_id) => {
804            tcx.ensure_ok().type_of(def_id);
805            if !tcx.dcx().has_stashed_diagnostic(ty.span, StashKey::ItemNoType)
806                && !(ty.is_suggestable_infer_ty() && body_id.is_some())
807            {
808                // Account for `const C: _;`.
809                let mut visitor = HirPlaceholderCollector::default();
810                visitor.visit_trait_item(trait_item);
811                placeholder_type_error(
812                    icx.lowerer(),
813                    None,
814                    visitor.spans,
815                    false,
816                    None,
817                    "associated constant",
818                );
819            }
820        }
821
822        hir::TraitItemKind::Type(_, Some(_)) => {
823            tcx.ensure_ok().item_bounds(def_id);
824            tcx.ensure_ok().item_self_bounds(def_id);
825            tcx.ensure_ok().type_of(def_id);
826            // Account for `type T = _;`.
827            let mut visitor = HirPlaceholderCollector::default();
828            visitor.visit_trait_item(trait_item);
829            placeholder_type_error(
830                icx.lowerer(),
831                None,
832                visitor.spans,
833                false,
834                None,
835                "associated type",
836            );
837        }
838
839        hir::TraitItemKind::Type(_, None) => {
840            tcx.ensure_ok().item_bounds(def_id);
841            tcx.ensure_ok().item_self_bounds(def_id);
842            // #74612: Visit and try to find bad placeholders
843            // even if there is no concrete type.
844            let mut visitor = HirPlaceholderCollector::default();
845            visitor.visit_trait_item(trait_item);
846
847            placeholder_type_error(
848                icx.lowerer(),
849                None,
850                visitor.spans,
851                false,
852                None,
853                "associated type",
854            );
855        }
856    };
857
858    tcx.ensure_ok().predicates_of(def_id);
859}
860
861fn lower_impl_item(tcx: TyCtxt<'_>, impl_item_id: hir::ImplItemId) {
862    let def_id = impl_item_id.owner_id;
863    tcx.ensure_ok().generics_of(def_id);
864    tcx.ensure_ok().type_of(def_id);
865    tcx.ensure_ok().predicates_of(def_id);
866    let impl_item = tcx.hir_impl_item(impl_item_id);
867    let icx = ItemCtxt::new(tcx, def_id.def_id);
868    match impl_item.kind {
869        hir::ImplItemKind::Fn(..) => {
870            tcx.ensure_ok().codegen_fn_attrs(def_id);
871            tcx.ensure_ok().fn_sig(def_id);
872        }
873        hir::ImplItemKind::Type(_) => {
874            // Account for `type T = _;`
875            let mut visitor = HirPlaceholderCollector::default();
876            visitor.visit_impl_item(impl_item);
877
878            placeholder_type_error(
879                icx.lowerer(),
880                None,
881                visitor.spans,
882                false,
883                None,
884                "associated type",
885            );
886        }
887        hir::ImplItemKind::Const(ty, _) => {
888            // Account for `const T: _ = ..;`
889            if !ty.is_suggestable_infer_ty() {
890                let mut visitor = HirPlaceholderCollector::default();
891                visitor.visit_impl_item(impl_item);
892                placeholder_type_error(
893                    icx.lowerer(),
894                    None,
895                    visitor.spans,
896                    false,
897                    None,
898                    "associated constant",
899                );
900            }
901        }
902    }
903}
904
905fn lower_variant_ctor(tcx: TyCtxt<'_>, def_id: LocalDefId) {
906    tcx.ensure_ok().generics_of(def_id);
907    tcx.ensure_ok().type_of(def_id);
908    tcx.ensure_ok().predicates_of(def_id);
909}
910
911fn lower_enum_variant_types(tcx: TyCtxt<'_>, def_id: DefId) {
912    let def = tcx.adt_def(def_id);
913    let repr_type = def.repr().discr_type();
914    let initial = repr_type.initial_discriminant(tcx);
915    let mut prev_discr = None::<Discr<'_>>;
916
917    // fill the discriminant values and field types
918    for variant in def.variants() {
919        let wrapped_discr = prev_discr.map_or(initial, |d| d.wrap_incr(tcx));
920        prev_discr = Some(
921            if let ty::VariantDiscr::Explicit(const_def_id) = variant.discr {
922                def.eval_explicit_discr(tcx, const_def_id).ok()
923            } else if let Some(discr) = repr_type.disr_incr(tcx, prev_discr) {
924                Some(discr)
925            } else {
926                let span = tcx.def_span(variant.def_id);
927                tcx.dcx().emit_err(errors::EnumDiscriminantOverflowed {
928                    span,
929                    discr: prev_discr.unwrap().to_string(),
930                    item_name: tcx.item_ident(variant.def_id),
931                    wrapped_discr: wrapped_discr.to_string(),
932                });
933                None
934            }
935            .unwrap_or(wrapped_discr),
936        );
937
938        for f in &variant.fields {
939            tcx.ensure_ok().generics_of(f.did);
940            tcx.ensure_ok().type_of(f.did);
941            tcx.ensure_ok().predicates_of(f.did);
942        }
943
944        // Lower the ctor, if any. This also registers the variant as an item.
945        if let Some(ctor_def_id) = variant.ctor_def_id() {
946            lower_variant_ctor(tcx, ctor_def_id.expect_local());
947        }
948    }
949}
950
951#[derive(Clone, Copy)]
952struct NestedSpan {
953    span: Span,
954    nested_field_span: Span,
955}
956
957impl NestedSpan {
958    fn to_field_already_declared_nested_help(&self) -> errors::FieldAlreadyDeclaredNestedHelp {
959        errors::FieldAlreadyDeclaredNestedHelp { span: self.span }
960    }
961}
962
963#[derive(Clone, Copy)]
964enum FieldDeclSpan {
965    NotNested(Span),
966    Nested(NestedSpan),
967}
968
969impl From<Span> for FieldDeclSpan {
970    fn from(span: Span) -> Self {
971        Self::NotNested(span)
972    }
973}
974
975impl From<NestedSpan> for FieldDeclSpan {
976    fn from(span: NestedSpan) -> Self {
977        Self::Nested(span)
978    }
979}
980
981struct FieldUniquenessCheckContext<'tcx> {
982    tcx: TyCtxt<'tcx>,
983    seen_fields: FxIndexMap<Ident, FieldDeclSpan>,
984}
985
986impl<'tcx> FieldUniquenessCheckContext<'tcx> {
987    fn new(tcx: TyCtxt<'tcx>) -> Self {
988        Self { tcx, seen_fields: FxIndexMap::default() }
989    }
990
991    /// Check if a given field `ident` declared at `field_decl` has been declared elsewhere before.
992    fn check_field_decl(&mut self, field_name: Ident, field_decl: FieldDeclSpan) {
993        use FieldDeclSpan::*;
994        let field_name = field_name.normalize_to_macros_2_0();
995        match (field_decl, self.seen_fields.get(&field_name).copied()) {
996            (NotNested(span), Some(NotNested(prev_span))) => {
997                self.tcx.dcx().emit_err(errors::FieldAlreadyDeclared::NotNested {
998                    field_name,
999                    span,
1000                    prev_span,
1001                });
1002            }
1003            (NotNested(span), Some(Nested(prev))) => {
1004                self.tcx.dcx().emit_err(errors::FieldAlreadyDeclared::PreviousNested {
1005                    field_name,
1006                    span,
1007                    prev_span: prev.span,
1008                    prev_nested_field_span: prev.nested_field_span,
1009                    prev_help: prev.to_field_already_declared_nested_help(),
1010                });
1011            }
1012            (
1013                Nested(current @ NestedSpan { span, nested_field_span, .. }),
1014                Some(NotNested(prev_span)),
1015            ) => {
1016                self.tcx.dcx().emit_err(errors::FieldAlreadyDeclared::CurrentNested {
1017                    field_name,
1018                    span,
1019                    nested_field_span,
1020                    help: current.to_field_already_declared_nested_help(),
1021                    prev_span,
1022                });
1023            }
1024            (Nested(current @ NestedSpan { span, nested_field_span }), Some(Nested(prev))) => {
1025                self.tcx.dcx().emit_err(errors::FieldAlreadyDeclared::BothNested {
1026                    field_name,
1027                    span,
1028                    nested_field_span,
1029                    help: current.to_field_already_declared_nested_help(),
1030                    prev_span: prev.span,
1031                    prev_nested_field_span: prev.nested_field_span,
1032                    prev_help: prev.to_field_already_declared_nested_help(),
1033                });
1034            }
1035            (field_decl, None) => {
1036                self.seen_fields.insert(field_name, field_decl);
1037            }
1038        }
1039    }
1040}
1041
1042fn lower_variant<'tcx>(
1043    tcx: TyCtxt<'tcx>,
1044    variant_did: Option<LocalDefId>,
1045    ident: Ident,
1046    discr: ty::VariantDiscr,
1047    def: &hir::VariantData<'tcx>,
1048    adt_kind: ty::AdtKind,
1049    parent_did: LocalDefId,
1050) -> ty::VariantDef {
1051    let mut field_uniqueness_check_ctx = FieldUniquenessCheckContext::new(tcx);
1052    let fields = def
1053        .fields()
1054        .iter()
1055        .inspect(|field| {
1056            field_uniqueness_check_ctx.check_field_decl(field.ident, field.span.into());
1057        })
1058        .map(|f| ty::FieldDef {
1059            did: f.def_id.to_def_id(),
1060            name: f.ident.name,
1061            vis: tcx.visibility(f.def_id),
1062            safety: f.safety,
1063            value: f.default.map(|v| v.def_id.to_def_id()),
1064        })
1065        .collect();
1066    let recovered = match def {
1067        hir::VariantData::Struct { recovered: Recovered::Yes(guar), .. } => Some(*guar),
1068        _ => None,
1069    };
1070    ty::VariantDef::new(
1071        ident.name,
1072        variant_did.map(LocalDefId::to_def_id),
1073        def.ctor().map(|(kind, _, def_id)| (kind, def_id.to_def_id())),
1074        discr,
1075        fields,
1076        parent_did.to_def_id(),
1077        recovered,
1078        adt_kind == AdtKind::Struct && tcx.has_attr(parent_did, sym::non_exhaustive)
1079            || variant_did
1080                .is_some_and(|variant_did| tcx.has_attr(variant_did, sym::non_exhaustive)),
1081    )
1082}
1083
1084fn adt_def(tcx: TyCtxt<'_>, def_id: LocalDefId) -> ty::AdtDef<'_> {
1085    use rustc_hir::*;
1086
1087    let Node::Item(item) = tcx.hir_node_by_def_id(def_id) else {
1088        bug!("expected ADT to be an item");
1089    };
1090
1091    let repr = tcx.repr_options_of_def(def_id);
1092    let (kind, variants) = match &item.kind {
1093        ItemKind::Enum(_, def, _) => {
1094            let mut distance_from_explicit = 0;
1095            let variants = def
1096                .variants
1097                .iter()
1098                .map(|v| {
1099                    let discr = if let Some(e) = &v.disr_expr {
1100                        distance_from_explicit = 0;
1101                        ty::VariantDiscr::Explicit(e.def_id.to_def_id())
1102                    } else {
1103                        ty::VariantDiscr::Relative(distance_from_explicit)
1104                    };
1105                    distance_from_explicit += 1;
1106
1107                    lower_variant(
1108                        tcx,
1109                        Some(v.def_id),
1110                        v.ident,
1111                        discr,
1112                        &v.data,
1113                        AdtKind::Enum,
1114                        def_id,
1115                    )
1116                })
1117                .collect();
1118
1119            (AdtKind::Enum, variants)
1120        }
1121        ItemKind::Struct(ident, def, _) | ItemKind::Union(ident, def, _) => {
1122            let adt_kind = match item.kind {
1123                ItemKind::Struct(..) => AdtKind::Struct,
1124                _ => AdtKind::Union,
1125            };
1126            let variants = std::iter::once(lower_variant(
1127                tcx,
1128                None,
1129                *ident,
1130                ty::VariantDiscr::Relative(0),
1131                def,
1132                adt_kind,
1133                def_id,
1134            ))
1135            .collect();
1136
1137            (adt_kind, variants)
1138        }
1139        _ => bug!("{:?} is not an ADT", item.owner_id.def_id),
1140    };
1141    tcx.mk_adt_def(def_id.to_def_id(), kind, variants, repr)
1142}
1143
1144fn trait_def(tcx: TyCtxt<'_>, def_id: LocalDefId) -> ty::TraitDef {
1145    let item = tcx.hir_expect_item(def_id);
1146
1147    let (is_alias, is_auto, safety, items) = match item.kind {
1148        hir::ItemKind::Trait(is_auto, safety, .., items) => {
1149            (false, is_auto == hir::IsAuto::Yes, safety, items)
1150        }
1151        hir::ItemKind::TraitAlias(..) => (true, false, hir::Safety::Safe, &[][..]),
1152        _ => span_bug!(item.span, "trait_def_of_item invoked on non-trait"),
1153    };
1154
1155    // Only regular traits can be const.
1156    let constness = if !is_alias && tcx.has_attr(def_id, sym::const_trait) {
1157        hir::Constness::Const
1158    } else {
1159        hir::Constness::NotConst
1160    };
1161
1162    let paren_sugar = tcx.has_attr(def_id, sym::rustc_paren_sugar);
1163    if paren_sugar && !tcx.features().unboxed_closures() {
1164        tcx.dcx().emit_err(errors::ParenSugarAttribute { span: item.span });
1165    }
1166
1167    // Only regular traits can be marker.
1168    let is_marker = !is_alias && tcx.has_attr(def_id, sym::marker);
1169
1170    let rustc_coinductive = tcx.has_attr(def_id, sym::rustc_coinductive);
1171    let is_fundamental = tcx.has_attr(def_id, sym::fundamental);
1172
1173    // FIXME: We could probably do way better attribute validation here.
1174    let mut skip_array_during_method_dispatch = false;
1175    let mut skip_boxed_slice_during_method_dispatch = false;
1176    for attr in tcx.get_attrs(def_id, sym::rustc_skip_during_method_dispatch) {
1177        if let Some(lst) = attr.meta_item_list() {
1178            for item in lst {
1179                if let Some(ident) = item.ident() {
1180                    match ident.as_str() {
1181                        "array" => skip_array_during_method_dispatch = true,
1182                        "boxed_slice" => skip_boxed_slice_during_method_dispatch = true,
1183                        _ => (),
1184                    }
1185                }
1186            }
1187        }
1188    }
1189
1190    let specialization_kind = if tcx.has_attr(def_id, sym::rustc_unsafe_specialization_marker) {
1191        ty::trait_def::TraitSpecializationKind::Marker
1192    } else if tcx.has_attr(def_id, sym::rustc_specialization_trait) {
1193        ty::trait_def::TraitSpecializationKind::AlwaysApplicable
1194    } else {
1195        ty::trait_def::TraitSpecializationKind::None
1196    };
1197    let must_implement_one_of = tcx
1198        .get_attr(def_id, sym::rustc_must_implement_one_of)
1199        // Check that there are at least 2 arguments of `#[rustc_must_implement_one_of]`
1200        // and that they are all identifiers
1201        .and_then(|attr| match attr.meta_item_list() {
1202            Some(items) if items.len() < 2 => {
1203                tcx.dcx().emit_err(errors::MustImplementOneOfAttribute { span: attr.span() });
1204
1205                None
1206            }
1207            Some(items) => items
1208                .into_iter()
1209                .map(|item| item.ident().ok_or(item.span()))
1210                .collect::<Result<Box<[_]>, _>>()
1211                .map_err(|span| {
1212                    tcx.dcx().emit_err(errors::MustBeNameOfAssociatedFunction { span });
1213                })
1214                .ok()
1215                .zip(Some(attr.span())),
1216            // Error is reported by `rustc_attr!`
1217            None => None,
1218        })
1219        // Check that all arguments of `#[rustc_must_implement_one_of]` reference
1220        // functions in the trait with default implementations
1221        .and_then(|(list, attr_span)| {
1222            let errors = list.iter().filter_map(|ident| {
1223                let item = items.iter().find(|item| item.ident == *ident);
1224
1225                match item {
1226                    Some(item) if matches!(item.kind, hir::AssocItemKind::Fn { .. }) => {
1227                        if !tcx.defaultness(item.id.owner_id).has_value() {
1228                            tcx.dcx().emit_err(errors::FunctionNotHaveDefaultImplementation {
1229                                span: item.span,
1230                                note_span: attr_span,
1231                            });
1232
1233                            return Some(());
1234                        }
1235
1236                        return None;
1237                    }
1238                    Some(item) => {
1239                        tcx.dcx().emit_err(errors::MustImplementNotFunction {
1240                            span: item.span,
1241                            span_note: errors::MustImplementNotFunctionSpanNote { span: attr_span },
1242                            note: errors::MustImplementNotFunctionNote {},
1243                        });
1244                    }
1245                    None => {
1246                        tcx.dcx().emit_err(errors::FunctionNotFoundInTrait { span: ident.span });
1247                    }
1248                }
1249
1250                Some(())
1251            });
1252
1253            (errors.count() == 0).then_some(list)
1254        })
1255        // Check for duplicates
1256        .and_then(|list| {
1257            let mut set: UnordMap<Symbol, Span> = Default::default();
1258            let mut no_dups = true;
1259
1260            for ident in &*list {
1261                if let Some(dup) = set.insert(ident.name, ident.span) {
1262                    tcx.dcx()
1263                        .emit_err(errors::FunctionNamesDuplicated { spans: vec![dup, ident.span] });
1264
1265                    no_dups = false;
1266                }
1267            }
1268
1269            no_dups.then_some(list)
1270        });
1271
1272    let deny_explicit_impl = tcx.has_attr(def_id, sym::rustc_deny_explicit_impl);
1273    let implement_via_object = !tcx.has_attr(def_id, sym::rustc_do_not_implement_via_object);
1274
1275    ty::TraitDef {
1276        def_id: def_id.to_def_id(),
1277        safety,
1278        constness,
1279        paren_sugar,
1280        has_auto_impl: is_auto,
1281        is_marker,
1282        is_coinductive: rustc_coinductive || is_auto,
1283        is_fundamental,
1284        skip_array_during_method_dispatch,
1285        skip_boxed_slice_during_method_dispatch,
1286        specialization_kind,
1287        must_implement_one_of,
1288        implement_via_object,
1289        deny_explicit_impl,
1290    }
1291}
1292
1293#[instrument(level = "debug", skip(tcx), ret)]
1294fn fn_sig(tcx: TyCtxt<'_>, def_id: LocalDefId) -> ty::EarlyBinder<'_, ty::PolyFnSig<'_>> {
1295    use rustc_hir::Node::*;
1296    use rustc_hir::*;
1297
1298    let hir_id = tcx.local_def_id_to_hir_id(def_id);
1299
1300    let icx = ItemCtxt::new(tcx, def_id);
1301
1302    let output = match tcx.hir_node(hir_id) {
1303        TraitItem(hir::TraitItem {
1304            kind: TraitItemKind::Fn(sig, TraitFn::Provided(_)),
1305            generics,
1306            ..
1307        })
1308        | Item(hir::Item { kind: ItemKind::Fn { sig, generics, .. }, .. }) => {
1309            lower_fn_sig_recovering_infer_ret_ty(&icx, sig, generics, def_id)
1310        }
1311
1312        ImplItem(hir::ImplItem { kind: ImplItemKind::Fn(sig, _), generics, .. }) => {
1313            // Do not try to infer the return type for a impl method coming from a trait
1314            if let Item(hir::Item { kind: ItemKind::Impl(i), .. }) = tcx.parent_hir_node(hir_id)
1315                && i.of_trait.is_some()
1316            {
1317                icx.lowerer().lower_fn_ty(
1318                    hir_id,
1319                    sig.header.safety(),
1320                    sig.header.abi,
1321                    sig.decl,
1322                    Some(generics),
1323                    None,
1324                )
1325            } else {
1326                lower_fn_sig_recovering_infer_ret_ty(&icx, sig, generics, def_id)
1327            }
1328        }
1329
1330        TraitItem(hir::TraitItem {
1331            kind: TraitItemKind::Fn(FnSig { header, decl, span: _ }, _),
1332            generics,
1333            ..
1334        }) => icx.lowerer().lower_fn_ty(
1335            hir_id,
1336            header.safety(),
1337            header.abi,
1338            decl,
1339            Some(generics),
1340            None,
1341        ),
1342
1343        ForeignItem(&hir::ForeignItem { kind: ForeignItemKind::Fn(sig, _, _), .. }) => {
1344            let abi = tcx.hir_get_foreign_abi(hir_id);
1345            compute_sig_of_foreign_fn_decl(tcx, def_id, sig.decl, abi, sig.header.safety())
1346        }
1347
1348        Ctor(data) => {
1349            assert_matches!(data.ctor(), Some(_));
1350            let adt_def_id = tcx.hir_get_parent_item(hir_id).def_id.to_def_id();
1351            let ty = tcx.type_of(adt_def_id).instantiate_identity();
1352            let inputs = data.fields().iter().map(|f| tcx.type_of(f.def_id).instantiate_identity());
1353            // constructors for structs with `layout_scalar_valid_range` are unsafe to call
1354            let safety = match tcx.layout_scalar_valid_range(adt_def_id) {
1355                (Bound::Unbounded, Bound::Unbounded) => hir::Safety::Safe,
1356                _ => hir::Safety::Unsafe,
1357            };
1358            ty::Binder::dummy(tcx.mk_fn_sig(inputs, ty, false, safety, ExternAbi::Rust))
1359        }
1360
1361        Expr(&hir::Expr { kind: hir::ExprKind::Closure { .. }, .. }) => {
1362            // Closure signatures are not like other function
1363            // signatures and cannot be accessed through `fn_sig`. For
1364            // example, a closure signature excludes the `self`
1365            // argument. In any case they are embedded within the
1366            // closure type as part of the `ClosureArgs`.
1367            //
1368            // To get the signature of a closure, you should use the
1369            // `sig` method on the `ClosureArgs`:
1370            //
1371            //    args.as_closure().sig(def_id, tcx)
1372            bug!("to get the signature of a closure, use `args.as_closure().sig()` not `fn_sig()`",);
1373        }
1374
1375        x => {
1376            bug!("unexpected sort of node in fn_sig(): {:?}", x);
1377        }
1378    };
1379    ty::EarlyBinder::bind(output)
1380}
1381
1382fn lower_fn_sig_recovering_infer_ret_ty<'tcx>(
1383    icx: &ItemCtxt<'tcx>,
1384    sig: &'tcx hir::FnSig<'tcx>,
1385    generics: &'tcx hir::Generics<'tcx>,
1386    def_id: LocalDefId,
1387) -> ty::PolyFnSig<'tcx> {
1388    if let Some(infer_ret_ty) = sig.decl.output.is_suggestable_infer_ty() {
1389        return recover_infer_ret_ty(icx, infer_ret_ty, generics, def_id);
1390    }
1391
1392    icx.lowerer().lower_fn_ty(
1393        icx.tcx().local_def_id_to_hir_id(def_id),
1394        sig.header.safety(),
1395        sig.header.abi,
1396        sig.decl,
1397        Some(generics),
1398        None,
1399    )
1400}
1401
1402fn recover_infer_ret_ty<'tcx>(
1403    icx: &ItemCtxt<'tcx>,
1404    infer_ret_ty: &'tcx hir::Ty<'tcx>,
1405    generics: &'tcx hir::Generics<'tcx>,
1406    def_id: LocalDefId,
1407) -> ty::PolyFnSig<'tcx> {
1408    let tcx = icx.tcx;
1409    let hir_id = tcx.local_def_id_to_hir_id(def_id);
1410
1411    let fn_sig = tcx.typeck(def_id).liberated_fn_sigs()[hir_id];
1412
1413    // Typeck doesn't expect erased regions to be returned from `type_of`.
1414    // This is a heuristic approach. If the scope has region parameters,
1415    // we should change fn_sig's lifetime from `ReErased` to `ReError`,
1416    // otherwise to `ReStatic`.
1417    let has_region_params = generics.params.iter().any(|param| match param.kind {
1418        GenericParamKind::Lifetime { .. } => true,
1419        _ => false,
1420    });
1421    let fn_sig = fold_regions(tcx, fn_sig, |r, _| match r.kind() {
1422        ty::ReErased => {
1423            if has_region_params {
1424                ty::Region::new_error_with_message(
1425                    tcx,
1426                    DUMMY_SP,
1427                    "erased region is not allowed here in return type",
1428                )
1429            } else {
1430                tcx.lifetimes.re_static
1431            }
1432        }
1433        _ => r,
1434    });
1435
1436    let mut visitor = HirPlaceholderCollector::default();
1437    visitor.visit_ty_unambig(infer_ret_ty);
1438
1439    let mut diag = bad_placeholder(icx.lowerer(), visitor.spans, "return type");
1440    let ret_ty = fn_sig.output();
1441
1442    // Don't leak types into signatures unless they're nameable!
1443    // For example, if a function returns itself, we don't want that
1444    // recursive function definition to leak out into the fn sig.
1445    let mut recovered_ret_ty = None;
1446    if let Some(suggestable_ret_ty) = ret_ty.make_suggestable(tcx, false, None) {
1447        diag.span_suggestion(
1448            infer_ret_ty.span,
1449            "replace with the correct return type",
1450            suggestable_ret_ty,
1451            Applicability::MachineApplicable,
1452        );
1453        recovered_ret_ty = Some(suggestable_ret_ty);
1454    } else if let Some(sugg) = suggest_impl_trait(
1455        &tcx.infer_ctxt().build(TypingMode::non_body_analysis()),
1456        tcx.param_env(def_id),
1457        ret_ty,
1458    ) {
1459        diag.span_suggestion(
1460            infer_ret_ty.span,
1461            "replace with an appropriate return type",
1462            sugg,
1463            Applicability::MachineApplicable,
1464        );
1465    } else if ret_ty.is_closure() {
1466        diag.help("consider using an `Fn`, `FnMut`, or `FnOnce` trait bound");
1467    }
1468
1469    // Also note how `Fn` traits work just in case!
1470    if ret_ty.is_closure() {
1471        diag.note(
1472            "for more information on `Fn` traits and closure types, see \
1473                     https://doc.rust-lang.org/book/ch13-01-closures.html",
1474        );
1475    }
1476    let guar = diag.emit();
1477    ty::Binder::dummy(tcx.mk_fn_sig(
1478        fn_sig.inputs().iter().copied(),
1479        recovered_ret_ty.unwrap_or_else(|| Ty::new_error(tcx, guar)),
1480        fn_sig.c_variadic,
1481        fn_sig.safety,
1482        fn_sig.abi,
1483    ))
1484}
1485
1486pub fn suggest_impl_trait<'tcx>(
1487    infcx: &InferCtxt<'tcx>,
1488    param_env: ty::ParamEnv<'tcx>,
1489    ret_ty: Ty<'tcx>,
1490) -> Option<String> {
1491    let format_as_assoc: fn(_, _, _, _, _) -> _ =
1492        |tcx: TyCtxt<'tcx>,
1493         _: ty::GenericArgsRef<'tcx>,
1494         trait_def_id: DefId,
1495         assoc_item_def_id: DefId,
1496         item_ty: Ty<'tcx>| {
1497            let trait_name = tcx.item_name(trait_def_id);
1498            let assoc_name = tcx.item_name(assoc_item_def_id);
1499            Some(format!("impl {trait_name}<{assoc_name} = {item_ty}>"))
1500        };
1501    let format_as_parenthesized: fn(_, _, _, _, _) -> _ =
1502        |tcx: TyCtxt<'tcx>,
1503         args: ty::GenericArgsRef<'tcx>,
1504         trait_def_id: DefId,
1505         _: DefId,
1506         item_ty: Ty<'tcx>| {
1507            let trait_name = tcx.item_name(trait_def_id);
1508            let args_tuple = args.type_at(1);
1509            let ty::Tuple(types) = *args_tuple.kind() else {
1510                return None;
1511            };
1512            let types = types.make_suggestable(tcx, false, None)?;
1513            let maybe_ret =
1514                if item_ty.is_unit() { String::new() } else { format!(" -> {item_ty}") };
1515            Some(format!(
1516                "impl {trait_name}({}){maybe_ret}",
1517                types.iter().map(|ty| ty.to_string()).collect::<Vec<_>>().join(", ")
1518            ))
1519        };
1520
1521    for (trait_def_id, assoc_item_def_id, formatter) in [
1522        (
1523            infcx.tcx.get_diagnostic_item(sym::Iterator),
1524            infcx.tcx.get_diagnostic_item(sym::IteratorItem),
1525            format_as_assoc,
1526        ),
1527        (
1528            infcx.tcx.lang_items().future_trait(),
1529            infcx.tcx.lang_items().future_output(),
1530            format_as_assoc,
1531        ),
1532        (
1533            infcx.tcx.lang_items().fn_trait(),
1534            infcx.tcx.lang_items().fn_once_output(),
1535            format_as_parenthesized,
1536        ),
1537        (
1538            infcx.tcx.lang_items().fn_mut_trait(),
1539            infcx.tcx.lang_items().fn_once_output(),
1540            format_as_parenthesized,
1541        ),
1542        (
1543            infcx.tcx.lang_items().fn_once_trait(),
1544            infcx.tcx.lang_items().fn_once_output(),
1545            format_as_parenthesized,
1546        ),
1547    ] {
1548        let Some(trait_def_id) = trait_def_id else {
1549            continue;
1550        };
1551        let Some(assoc_item_def_id) = assoc_item_def_id else {
1552            continue;
1553        };
1554        if infcx.tcx.def_kind(assoc_item_def_id) != DefKind::AssocTy {
1555            continue;
1556        }
1557        let sugg = infcx.probe(|_| {
1558            let args = ty::GenericArgs::for_item(infcx.tcx, trait_def_id, |param, _| {
1559                if param.index == 0 { ret_ty.into() } else { infcx.var_for_def(DUMMY_SP, param) }
1560            });
1561            if !infcx
1562                .type_implements_trait(trait_def_id, args, param_env)
1563                .must_apply_modulo_regions()
1564            {
1565                return None;
1566            }
1567            let ocx = ObligationCtxt::new(&infcx);
1568            let item_ty = ocx.normalize(
1569                &ObligationCause::dummy(),
1570                param_env,
1571                Ty::new_projection_from_args(infcx.tcx, assoc_item_def_id, args),
1572            );
1573            // FIXME(compiler-errors): We may benefit from resolving regions here.
1574            if ocx.select_where_possible().is_empty()
1575                && let item_ty = infcx.resolve_vars_if_possible(item_ty)
1576                && let Some(item_ty) = item_ty.make_suggestable(infcx.tcx, false, None)
1577                && let Some(sugg) = formatter(
1578                    infcx.tcx,
1579                    infcx.resolve_vars_if_possible(args),
1580                    trait_def_id,
1581                    assoc_item_def_id,
1582                    item_ty,
1583                )
1584            {
1585                return Some(sugg);
1586            }
1587
1588            None
1589        });
1590
1591        if sugg.is_some() {
1592            return sugg;
1593        }
1594    }
1595    None
1596}
1597
1598fn impl_trait_header(tcx: TyCtxt<'_>, def_id: LocalDefId) -> Option<ty::ImplTraitHeader<'_>> {
1599    let icx = ItemCtxt::new(tcx, def_id);
1600    let item = tcx.hir_expect_item(def_id);
1601    let impl_ = item.expect_impl();
1602    impl_.of_trait.as_ref().map(|ast_trait_ref| {
1603        let selfty = tcx.type_of(def_id).instantiate_identity();
1604
1605        check_impl_constness(tcx, impl_.constness, ast_trait_ref);
1606
1607        let trait_ref = icx.lowerer().lower_impl_trait_ref(ast_trait_ref, selfty);
1608
1609        ty::ImplTraitHeader {
1610            trait_ref: ty::EarlyBinder::bind(trait_ref),
1611            safety: impl_.safety,
1612            polarity: polarity_of_impl(tcx, def_id, impl_, item.span),
1613            constness: impl_.constness,
1614        }
1615    })
1616}
1617
1618fn check_impl_constness(
1619    tcx: TyCtxt<'_>,
1620    constness: hir::Constness,
1621    hir_trait_ref: &hir::TraitRef<'_>,
1622) {
1623    if let hir::Constness::NotConst = constness {
1624        return;
1625    }
1626
1627    let Some(trait_def_id) = hir_trait_ref.trait_def_id() else { return };
1628    if tcx.is_const_trait(trait_def_id) {
1629        return;
1630    }
1631
1632    let trait_name = tcx.item_name(trait_def_id).to_string();
1633    let (local_trait_span, suggestion_pre) =
1634        match (trait_def_id.is_local(), tcx.sess.is_nightly_build()) {
1635            (true, true) => (
1636                Some(tcx.def_span(trait_def_id).shrink_to_lo()),
1637                if tcx.features().const_trait_impl() {
1638                    ""
1639                } else {
1640                    "enable `#![feature(const_trait_impl)]` in your crate and "
1641                },
1642            ),
1643            (false, _) | (_, false) => (None, ""),
1644        };
1645    tcx.dcx().emit_err(errors::ConstImplForNonConstTrait {
1646        trait_ref_span: hir_trait_ref.path.span,
1647        trait_name,
1648        local_trait_span,
1649        suggestion_pre,
1650        marking: (),
1651        adding: (),
1652    });
1653}
1654
1655fn polarity_of_impl(
1656    tcx: TyCtxt<'_>,
1657    def_id: LocalDefId,
1658    impl_: &hir::Impl<'_>,
1659    span: Span,
1660) -> ty::ImplPolarity {
1661    let is_rustc_reservation = tcx.has_attr(def_id, sym::rustc_reservation_impl);
1662    match &impl_ {
1663        hir::Impl { polarity: hir::ImplPolarity::Negative(span), of_trait, .. } => {
1664            if is_rustc_reservation {
1665                let span = span.to(of_trait.as_ref().map_or(*span, |t| t.path.span));
1666                tcx.dcx().span_err(span, "reservation impls can't be negative");
1667            }
1668            ty::ImplPolarity::Negative
1669        }
1670        hir::Impl { polarity: hir::ImplPolarity::Positive, of_trait: None, .. } => {
1671            if is_rustc_reservation {
1672                tcx.dcx().span_err(span, "reservation impls can't be inherent");
1673            }
1674            ty::ImplPolarity::Positive
1675        }
1676        hir::Impl { polarity: hir::ImplPolarity::Positive, of_trait: Some(_), .. } => {
1677            if is_rustc_reservation {
1678                ty::ImplPolarity::Reservation
1679            } else {
1680                ty::ImplPolarity::Positive
1681            }
1682        }
1683    }
1684}
1685
1686/// Returns the early-bound lifetimes declared in this generics
1687/// listing. For anything other than fns/methods, this is just all
1688/// the lifetimes that are declared. For fns or methods, we have to
1689/// screen out those that do not appear in any where-clauses etc using
1690/// `resolve_lifetime::early_bound_lifetimes`.
1691fn early_bound_lifetimes_from_generics<'a, 'tcx>(
1692    tcx: TyCtxt<'tcx>,
1693    generics: &'a hir::Generics<'a>,
1694) -> impl Iterator<Item = &'a hir::GenericParam<'a>> {
1695    generics.params.iter().filter(move |param| match param.kind {
1696        GenericParamKind::Lifetime { .. } => !tcx.is_late_bound(param.hir_id),
1697        _ => false,
1698    })
1699}
1700
1701fn compute_sig_of_foreign_fn_decl<'tcx>(
1702    tcx: TyCtxt<'tcx>,
1703    def_id: LocalDefId,
1704    decl: &'tcx hir::FnDecl<'tcx>,
1705    abi: ExternAbi,
1706    safety: hir::Safety,
1707) -> ty::PolyFnSig<'tcx> {
1708    let hir_id = tcx.local_def_id_to_hir_id(def_id);
1709    let fty =
1710        ItemCtxt::new(tcx, def_id).lowerer().lower_fn_ty(hir_id, safety, abi, decl, None, None);
1711
1712    // Feature gate SIMD types in FFI, since I am not sure that the
1713    // ABIs are handled at all correctly. -huonw
1714    if !tcx.features().simd_ffi() {
1715        let check = |hir_ty: &hir::Ty<'_>, ty: Ty<'_>| {
1716            if ty.is_simd() {
1717                let snip = tcx
1718                    .sess
1719                    .source_map()
1720                    .span_to_snippet(hir_ty.span)
1721                    .map_or_else(|_| String::new(), |s| format!(" `{s}`"));
1722                tcx.dcx().emit_err(errors::SIMDFFIHighlyExperimental { span: hir_ty.span, snip });
1723            }
1724        };
1725        for (input, ty) in iter::zip(decl.inputs, fty.inputs().skip_binder()) {
1726            check(input, *ty)
1727        }
1728        if let hir::FnRetTy::Return(ty) = decl.output {
1729            check(ty, fty.output().skip_binder())
1730        }
1731    }
1732
1733    fty
1734}
1735
1736fn coroutine_kind(tcx: TyCtxt<'_>, def_id: LocalDefId) -> Option<hir::CoroutineKind> {
1737    match tcx.hir_node_by_def_id(def_id) {
1738        Node::Expr(&hir::Expr {
1739            kind:
1740                hir::ExprKind::Closure(&rustc_hir::Closure {
1741                    kind: hir::ClosureKind::Coroutine(kind),
1742                    ..
1743                }),
1744            ..
1745        }) => Some(kind),
1746        _ => None,
1747    }
1748}
1749
1750fn coroutine_for_closure(tcx: TyCtxt<'_>, def_id: LocalDefId) -> DefId {
1751    let &rustc_hir::Closure { kind: hir::ClosureKind::CoroutineClosure(_), body, .. } =
1752        tcx.hir_node_by_def_id(def_id).expect_closure()
1753    else {
1754        bug!()
1755    };
1756
1757    let &hir::Expr {
1758        kind:
1759            hir::ExprKind::Closure(&rustc_hir::Closure {
1760                def_id,
1761                kind: hir::ClosureKind::Coroutine(_),
1762                ..
1763            }),
1764        ..
1765    } = tcx.hir_body(body).value
1766    else {
1767        bug!()
1768    };
1769
1770    def_id.to_def_id()
1771}
1772
1773fn opaque_ty_origin<'tcx>(tcx: TyCtxt<'tcx>, def_id: LocalDefId) -> hir::OpaqueTyOrigin<DefId> {
1774    match tcx.hir_node_by_def_id(def_id).expect_opaque_ty().origin {
1775        hir::OpaqueTyOrigin::FnReturn { parent, in_trait_or_impl } => {
1776            hir::OpaqueTyOrigin::FnReturn { parent: parent.to_def_id(), in_trait_or_impl }
1777        }
1778        hir::OpaqueTyOrigin::AsyncFn { parent, in_trait_or_impl } => {
1779            hir::OpaqueTyOrigin::AsyncFn { parent: parent.to_def_id(), in_trait_or_impl }
1780        }
1781        hir::OpaqueTyOrigin::TyAlias { parent, in_assoc_ty } => {
1782            hir::OpaqueTyOrigin::TyAlias { parent: parent.to_def_id(), in_assoc_ty }
1783        }
1784    }
1785}
1786
1787fn rendered_precise_capturing_args<'tcx>(
1788    tcx: TyCtxt<'tcx>,
1789    def_id: LocalDefId,
1790) -> Option<&'tcx [PreciseCapturingArgKind<Symbol, Symbol>]> {
1791    if let Some(ty::ImplTraitInTraitData::Trait { opaque_def_id, .. }) =
1792        tcx.opt_rpitit_info(def_id.to_def_id())
1793    {
1794        return tcx.rendered_precise_capturing_args(opaque_def_id);
1795    }
1796
1797    tcx.hir_node_by_def_id(def_id).expect_opaque_ty().bounds.iter().find_map(|bound| match bound {
1798        hir::GenericBound::Use(args, ..) => {
1799            Some(&*tcx.arena.alloc_from_iter(args.iter().map(|arg| match arg {
1800                PreciseCapturingArgKind::Lifetime(_) => {
1801                    PreciseCapturingArgKind::Lifetime(arg.name())
1802                }
1803                PreciseCapturingArgKind::Param(_) => PreciseCapturingArgKind::Param(arg.name()),
1804            })))
1805        }
1806        _ => None,
1807    })
1808}
1809
1810fn const_param_default<'tcx>(
1811    tcx: TyCtxt<'tcx>,
1812    def_id: LocalDefId,
1813) -> ty::EarlyBinder<'tcx, Const<'tcx>> {
1814    let default_ct = match tcx.hir_node_by_def_id(def_id) {
1815        hir::Node::GenericParam(hir::GenericParam {
1816            kind: hir::GenericParamKind::Const { default: Some(ct), .. },
1817            ..
1818        }) => ct,
1819        _ => span_bug!(
1820            tcx.def_span(def_id),
1821            "`const_param_default` expected a generic parameter with a constant"
1822        ),
1823    };
1824    let icx = ItemCtxt::new(tcx, def_id);
1825    let identity_args = ty::GenericArgs::identity_for_item(tcx, def_id);
1826    let ct = icx
1827        .lowerer()
1828        .lower_const_arg(default_ct, FeedConstTy::Param(def_id.to_def_id(), identity_args));
1829    ty::EarlyBinder::bind(ct)
1830}