rustc_resolve/
lib.rs

1//! This crate is responsible for the part of name resolution that doesn't require type checker.
2//!
3//! Module structure of the crate is built here.
4//! Paths in macros, imports, expressions, types, patterns are resolved here.
5//! Label and lifetime names are resolved here as well.
6//!
7//! Type-relative name resolution (methods, fields, associated items) happens in `rustc_hir_analysis`.
8
9// tidy-alphabetical-start
10#![allow(internal_features)]
11#![allow(rustc::diagnostic_outside_of_impl)]
12#![allow(rustc::untranslatable_diagnostic)]
13#![doc(html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/")]
14#![doc(rust_logo)]
15#![feature(assert_matches)]
16#![feature(box_patterns)]
17#![feature(if_let_guard)]
18#![feature(iter_intersperse)]
19#![feature(rustc_attrs)]
20#![feature(rustdoc_internals)]
21#![recursion_limit = "256"]
22// tidy-alphabetical-end
23
24use std::cell::{Cell, RefCell};
25use std::collections::BTreeSet;
26use std::fmt;
27use std::sync::Arc;
28
29use diagnostics::{ImportSuggestion, LabelSuggestion, Suggestion};
30use effective_visibilities::EffectiveVisibilitiesVisitor;
31use errors::{ParamKindInEnumDiscriminant, ParamKindInNonTrivialAnonConst};
32use imports::{Import, ImportData, ImportKind, NameResolution};
33use late::{
34    ForwardGenericParamBanReason, HasGenericParams, PathSource, PatternSource,
35    UnnecessaryQualification,
36};
37use macros::{MacroRulesBinding, MacroRulesScope, MacroRulesScopeRef};
38use rustc_arena::{DroplessArena, TypedArena};
39use rustc_ast::expand::StrippedCfgItem;
40use rustc_ast::node_id::NodeMap;
41use rustc_ast::{
42    self as ast, AngleBracketedArg, CRATE_NODE_ID, Crate, Expr, ExprKind, GenericArg, GenericArgs,
43    LitKind, NodeId, Path, attr,
44};
45use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexMap, FxIndexSet};
46use rustc_data_structures::intern::Interned;
47use rustc_data_structures::steal::Steal;
48use rustc_data_structures::sync::FreezeReadGuard;
49use rustc_data_structures::unord::{UnordMap, UnordSet};
50use rustc_errors::{Applicability, Diag, ErrCode, ErrorGuaranteed};
51use rustc_expand::base::{DeriveResolution, SyntaxExtension, SyntaxExtensionKind};
52use rustc_feature::BUILTIN_ATTRIBUTES;
53use rustc_hir::def::Namespace::{self, *};
54use rustc_hir::def::{
55    self, CtorOf, DefKind, DocLinkResMap, LifetimeRes, NonMacroAttrKind, PartialRes, PerNS,
56};
57use rustc_hir::def_id::{CRATE_DEF_ID, CrateNum, DefId, LOCAL_CRATE, LocalDefId, LocalDefIdMap};
58use rustc_hir::definitions::DisambiguatorState;
59use rustc_hir::{PrimTy, TraitCandidate};
60use rustc_index::bit_set::DenseBitSet;
61use rustc_metadata::creader::{CStore, CrateLoader};
62use rustc_middle::metadata::ModChild;
63use rustc_middle::middle::privacy::EffectiveVisibilities;
64use rustc_middle::query::Providers;
65use rustc_middle::span_bug;
66use rustc_middle::ty::{
67    self, DelegationFnSig, Feed, MainDefinition, RegisteredTools, ResolverGlobalCtxt,
68    ResolverOutputs, TyCtxt, TyCtxtFeed,
69};
70use rustc_query_system::ich::StableHashingContext;
71use rustc_session::lint::builtin::PRIVATE_MACRO_USE;
72use rustc_session::lint::{BuiltinLintDiag, LintBuffer};
73use rustc_span::hygiene::{ExpnId, LocalExpnId, MacroKind, SyntaxContext, Transparency};
74use rustc_span::{DUMMY_SP, Ident, Span, Symbol, kw, sym};
75use smallvec::{SmallVec, smallvec};
76use tracing::debug;
77
78type Res = def::Res<NodeId>;
79
80mod build_reduced_graph;
81mod check_unused;
82mod def_collector;
83mod diagnostics;
84mod effective_visibilities;
85mod errors;
86mod ident;
87mod imports;
88mod late;
89mod macros;
90pub mod rustdoc;
91
92pub use macros::registered_tools_ast;
93
94rustc_fluent_macro::fluent_messages! { "../messages.ftl" }
95
96#[derive(Debug)]
97enum Weak {
98    Yes,
99    No,
100}
101
102#[derive(Copy, Clone, PartialEq, Debug)]
103enum Determinacy {
104    Determined,
105    Undetermined,
106}
107
108impl Determinacy {
109    fn determined(determined: bool) -> Determinacy {
110        if determined { Determinacy::Determined } else { Determinacy::Undetermined }
111    }
112}
113
114/// A specific scope in which a name can be looked up.
115/// This enum is currently used only for early resolution (imports and macros),
116/// but not for late resolution yet.
117#[derive(Clone, Copy, Debug)]
118enum Scope<'ra> {
119    DeriveHelpers(LocalExpnId),
120    DeriveHelpersCompat,
121    MacroRules(MacroRulesScopeRef<'ra>),
122    CrateRoot,
123    // The node ID is for reporting the `PROC_MACRO_DERIVE_RESOLUTION_FALLBACK`
124    // lint if it should be reported.
125    Module(Module<'ra>, Option<NodeId>),
126    MacroUsePrelude,
127    BuiltinAttrs,
128    ExternPrelude,
129    ToolPrelude,
130    StdLibPrelude,
131    BuiltinTypes,
132}
133
134/// Names from different contexts may want to visit different subsets of all specific scopes
135/// with different restrictions when looking up the resolution.
136/// This enum is currently used only for early resolution (imports and macros),
137/// but not for late resolution yet.
138#[derive(Clone, Copy, Debug)]
139enum ScopeSet<'ra> {
140    /// All scopes with the given namespace.
141    All(Namespace),
142    /// Crate root, then extern prelude (used for mixed 2015-2018 mode in macros).
143    AbsolutePath(Namespace),
144    /// All scopes with macro namespace and the given macro kind restriction.
145    Macro(MacroKind),
146    /// All scopes with the given namespace, used for partially performing late resolution.
147    /// The node id enables lints and is used for reporting them.
148    Late(Namespace, Module<'ra>, Option<NodeId>),
149}
150
151/// Everything you need to know about a name's location to resolve it.
152/// Serves as a starting point for the scope visitor.
153/// This struct is currently used only for early resolution (imports and macros),
154/// but not for late resolution yet.
155#[derive(Clone, Copy, Debug)]
156struct ParentScope<'ra> {
157    module: Module<'ra>,
158    expansion: LocalExpnId,
159    macro_rules: MacroRulesScopeRef<'ra>,
160    derives: &'ra [ast::Path],
161}
162
163impl<'ra> ParentScope<'ra> {
164    /// Creates a parent scope with the passed argument used as the module scope component,
165    /// and other scope components set to default empty values.
166    fn module(module: Module<'ra>, resolver: &Resolver<'ra, '_>) -> ParentScope<'ra> {
167        ParentScope {
168            module,
169            expansion: LocalExpnId::ROOT,
170            macro_rules: resolver.arenas.alloc_macro_rules_scope(MacroRulesScope::Empty),
171            derives: &[],
172        }
173    }
174}
175
176#[derive(Copy, Debug, Clone)]
177struct InvocationParent {
178    parent_def: LocalDefId,
179    impl_trait_context: ImplTraitContext,
180    in_attr: bool,
181}
182
183impl InvocationParent {
184    const ROOT: Self = Self {
185        parent_def: CRATE_DEF_ID,
186        impl_trait_context: ImplTraitContext::Existential,
187        in_attr: false,
188    };
189}
190
191#[derive(Copy, Debug, Clone)]
192enum ImplTraitContext {
193    Existential,
194    Universal,
195    InBinding,
196}
197
198/// Used for tracking import use types which will be used for redundant import checking.
199///
200/// ### Used::Scope Example
201///
202/// ```rust,compile_fail
203/// #![deny(redundant_imports)]
204/// use std::mem::drop;
205/// fn main() {
206///     let s = Box::new(32);
207///     drop(s);
208/// }
209/// ```
210///
211/// Used::Other is for other situations like module-relative uses.
212#[derive(Clone, Copy, PartialEq, PartialOrd, Debug)]
213enum Used {
214    Scope,
215    Other,
216}
217
218#[derive(Debug)]
219struct BindingError {
220    name: Ident,
221    origin: BTreeSet<Span>,
222    target: BTreeSet<Span>,
223    could_be_path: bool,
224}
225
226#[derive(Debug)]
227enum ResolutionError<'ra> {
228    /// Error E0401: can't use type or const parameters from outer item.
229    GenericParamsFromOuterItem(Res, HasGenericParams, DefKind),
230    /// Error E0403: the name is already used for a type or const parameter in this generic
231    /// parameter list.
232    NameAlreadyUsedInParameterList(Ident, Span),
233    /// Error E0407: method is not a member of trait.
234    MethodNotMemberOfTrait(Ident, String, Option<Symbol>),
235    /// Error E0437: type is not a member of trait.
236    TypeNotMemberOfTrait(Ident, String, Option<Symbol>),
237    /// Error E0438: const is not a member of trait.
238    ConstNotMemberOfTrait(Ident, String, Option<Symbol>),
239    /// Error E0408: variable `{}` is not bound in all patterns.
240    VariableNotBoundInPattern(BindingError, ParentScope<'ra>),
241    /// Error E0409: variable `{}` is bound in inconsistent ways within the same match arm.
242    VariableBoundWithDifferentMode(Ident, Span),
243    /// Error E0415: identifier is bound more than once in this parameter list.
244    IdentifierBoundMoreThanOnceInParameterList(Ident),
245    /// Error E0416: identifier is bound more than once in the same pattern.
246    IdentifierBoundMoreThanOnceInSamePattern(Ident),
247    /// Error E0426: use of undeclared label.
248    UndeclaredLabel { name: Symbol, suggestion: Option<LabelSuggestion> },
249    /// Error E0429: `self` imports are only allowed within a `{ }` list.
250    SelfImportsOnlyAllowedWithin { root: bool, span_with_rename: Span },
251    /// Error E0430: `self` import can only appear once in the list.
252    SelfImportCanOnlyAppearOnceInTheList,
253    /// Error E0431: `self` import can only appear in an import list with a non-empty prefix.
254    SelfImportOnlyInImportListWithNonEmptyPrefix,
255    /// Error E0433: failed to resolve.
256    FailedToResolve {
257        segment: Option<Symbol>,
258        label: String,
259        suggestion: Option<Suggestion>,
260        module: Option<ModuleOrUniformRoot<'ra>>,
261    },
262    /// Error E0434: can't capture dynamic environment in a fn item.
263    CannotCaptureDynamicEnvironmentInFnItem,
264    /// Error E0435: attempt to use a non-constant value in a constant.
265    AttemptToUseNonConstantValueInConstant {
266        ident: Ident,
267        suggestion: &'static str,
268        current: &'static str,
269        type_span: Option<Span>,
270    },
271    /// Error E0530: `X` bindings cannot shadow `Y`s.
272    BindingShadowsSomethingUnacceptable {
273        shadowing_binding: PatternSource,
274        name: Symbol,
275        participle: &'static str,
276        article: &'static str,
277        shadowed_binding: Res,
278        shadowed_binding_span: Span,
279    },
280    /// Error E0128: generic parameters with a default cannot use forward-declared identifiers.
281    ForwardDeclaredGenericParam(Symbol, ForwardGenericParamBanReason),
282    // FIXME(generic_const_parameter_types): This should give custom output specifying it's only
283    // problematic to use *forward declared* parameters when the feature is enabled.
284    /// ERROR E0770: the type of const parameters must not depend on other generic parameters.
285    ParamInTyOfConstParam { name: Symbol },
286    /// generic parameters must not be used inside const evaluations.
287    ///
288    /// This error is only emitted when using `min_const_generics`.
289    ParamInNonTrivialAnonConst { name: Symbol, param_kind: ParamKindInNonTrivialAnonConst },
290    /// generic parameters must not be used inside enum discriminants.
291    ///
292    /// This error is emitted even with `generic_const_exprs`.
293    ParamInEnumDiscriminant { name: Symbol, param_kind: ParamKindInEnumDiscriminant },
294    /// Error E0735: generic parameters with a default cannot use `Self`
295    ForwardDeclaredSelf(ForwardGenericParamBanReason),
296    /// Error E0767: use of unreachable label
297    UnreachableLabel { name: Symbol, definition_span: Span, suggestion: Option<LabelSuggestion> },
298    /// Error E0323, E0324, E0325: mismatch between trait item and impl item.
299    TraitImplMismatch {
300        name: Ident,
301        kind: &'static str,
302        trait_path: String,
303        trait_item_span: Span,
304        code: ErrCode,
305    },
306    /// Error E0201: multiple impl items for the same trait item.
307    TraitImplDuplicate { name: Ident, trait_item_span: Span, old_span: Span },
308    /// Inline asm `sym` operand must refer to a `fn` or `static`.
309    InvalidAsmSym,
310    /// `self` used instead of `Self` in a generic parameter
311    LowercaseSelf,
312    /// A never pattern has a binding.
313    BindingInNeverPattern,
314}
315
316enum VisResolutionError<'a> {
317    Relative2018(Span, &'a ast::Path),
318    AncestorOnly(Span),
319    FailedToResolve(Span, String, Option<Suggestion>),
320    ExpectedFound(Span, String, Res),
321    Indeterminate(Span),
322    ModuleOnly(Span),
323}
324
325/// A minimal representation of a path segment. We use this in resolve because we synthesize 'path
326/// segments' which don't have the rest of an AST or HIR `PathSegment`.
327#[derive(Clone, Copy, Debug)]
328struct Segment {
329    ident: Ident,
330    id: Option<NodeId>,
331    /// Signals whether this `PathSegment` has generic arguments. Used to avoid providing
332    /// nonsensical suggestions.
333    has_generic_args: bool,
334    /// Signals whether this `PathSegment` has lifetime arguments.
335    has_lifetime_args: bool,
336    args_span: Span,
337}
338
339impl Segment {
340    fn from_path(path: &Path) -> Vec<Segment> {
341        path.segments.iter().map(|s| s.into()).collect()
342    }
343
344    fn from_ident(ident: Ident) -> Segment {
345        Segment {
346            ident,
347            id: None,
348            has_generic_args: false,
349            has_lifetime_args: false,
350            args_span: DUMMY_SP,
351        }
352    }
353
354    fn from_ident_and_id(ident: Ident, id: NodeId) -> Segment {
355        Segment {
356            ident,
357            id: Some(id),
358            has_generic_args: false,
359            has_lifetime_args: false,
360            args_span: DUMMY_SP,
361        }
362    }
363
364    fn names_to_string(segments: &[Segment]) -> String {
365        names_to_string(segments.iter().map(|seg| seg.ident.name))
366    }
367}
368
369impl<'a> From<&'a ast::PathSegment> for Segment {
370    fn from(seg: &'a ast::PathSegment) -> Segment {
371        let has_generic_args = seg.args.is_some();
372        let (args_span, has_lifetime_args) = if let Some(args) = seg.args.as_deref() {
373            match args {
374                GenericArgs::AngleBracketed(args) => {
375                    let found_lifetimes = args
376                        .args
377                        .iter()
378                        .any(|arg| matches!(arg, AngleBracketedArg::Arg(GenericArg::Lifetime(_))));
379                    (args.span, found_lifetimes)
380                }
381                GenericArgs::Parenthesized(args) => (args.span, true),
382                GenericArgs::ParenthesizedElided(span) => (*span, true),
383            }
384        } else {
385            (DUMMY_SP, false)
386        };
387        Segment {
388            ident: seg.ident,
389            id: Some(seg.id),
390            has_generic_args,
391            has_lifetime_args,
392            args_span,
393        }
394    }
395}
396
397/// An intermediate resolution result.
398///
399/// This refers to the thing referred by a name. The difference between `Res` and `Item` is that
400/// items are visible in their whole block, while `Res`es only from the place they are defined
401/// forward.
402#[derive(Debug, Copy, Clone)]
403enum LexicalScopeBinding<'ra> {
404    Item(NameBinding<'ra>),
405    Res(Res),
406}
407
408impl<'ra> LexicalScopeBinding<'ra> {
409    fn res(self) -> Res {
410        match self {
411            LexicalScopeBinding::Item(binding) => binding.res(),
412            LexicalScopeBinding::Res(res) => res,
413        }
414    }
415}
416
417#[derive(Copy, Clone, PartialEq, Debug)]
418enum ModuleOrUniformRoot<'ra> {
419    /// Regular module.
420    Module(Module<'ra>),
421
422    /// Virtual module that denotes resolution in crate root with fallback to extern prelude.
423    CrateRootAndExternPrelude,
424
425    /// Virtual module that denotes resolution in extern prelude.
426    /// Used for paths starting with `::` on 2018 edition.
427    ExternPrelude,
428
429    /// Virtual module that denotes resolution in current scope.
430    /// Used only for resolving single-segment imports. The reason it exists is that import paths
431    /// are always split into two parts, the first of which should be some kind of module.
432    CurrentScope,
433}
434
435#[derive(Debug)]
436enum PathResult<'ra> {
437    Module(ModuleOrUniformRoot<'ra>),
438    NonModule(PartialRes),
439    Indeterminate,
440    Failed {
441        span: Span,
442        label: String,
443        suggestion: Option<Suggestion>,
444        is_error_from_last_segment: bool,
445        /// The final module being resolved, for instance:
446        ///
447        /// ```compile_fail
448        /// mod a {
449        ///     mod b {
450        ///         mod c {}
451        ///     }
452        /// }
453        ///
454        /// use a::not_exist::c;
455        /// ```
456        ///
457        /// In this case, `module` will point to `a`.
458        module: Option<ModuleOrUniformRoot<'ra>>,
459        /// The segment name of target
460        segment_name: Symbol,
461        error_implied_by_parse_error: bool,
462    },
463}
464
465impl<'ra> PathResult<'ra> {
466    fn failed(
467        ident: Ident,
468        is_error_from_last_segment: bool,
469        finalize: bool,
470        error_implied_by_parse_error: bool,
471        module: Option<ModuleOrUniformRoot<'ra>>,
472        label_and_suggestion: impl FnOnce() -> (String, Option<Suggestion>),
473    ) -> PathResult<'ra> {
474        let (label, suggestion) =
475            if finalize { label_and_suggestion() } else { (String::new(), None) };
476        PathResult::Failed {
477            span: ident.span,
478            segment_name: ident.name,
479            label,
480            suggestion,
481            is_error_from_last_segment,
482            module,
483            error_implied_by_parse_error,
484        }
485    }
486}
487
488#[derive(Debug)]
489enum ModuleKind {
490    /// An anonymous module; e.g., just a block.
491    ///
492    /// ```
493    /// fn main() {
494    ///     fn f() {} // (1)
495    ///     { // This is an anonymous module
496    ///         f(); // This resolves to (2) as we are inside the block.
497    ///         fn f() {} // (2)
498    ///     }
499    ///     f(); // Resolves to (1)
500    /// }
501    /// ```
502    Block,
503    /// Any module with a name.
504    ///
505    /// This could be:
506    ///
507    /// * A normal module – either `mod from_file;` or `mod from_block { }` –
508    ///   or the crate root (which is conceptually a top-level module).
509    ///   The crate root will have `None` for the symbol.
510    /// * A trait or an enum (it implicitly contains associated types, methods and variant
511    ///   constructors).
512    Def(DefKind, DefId, Option<Symbol>),
513}
514
515impl ModuleKind {
516    /// Get name of the module.
517    fn name(&self) -> Option<Symbol> {
518        match *self {
519            ModuleKind::Block => None,
520            ModuleKind::Def(.., name) => name,
521        }
522    }
523}
524
525/// A key that identifies a binding in a given `Module`.
526///
527/// Multiple bindings in the same module can have the same key (in a valid
528/// program) if all but one of them come from glob imports.
529#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
530struct BindingKey {
531    /// The identifier for the binding, always the `normalize_to_macros_2_0` version of the
532    /// identifier.
533    ident: Ident,
534    ns: Namespace,
535    /// 0 if ident is not `_`, otherwise a value that's unique to the specific
536    /// `_` in the expanded AST that introduced this binding.
537    disambiguator: u32,
538}
539
540impl BindingKey {
541    fn new(ident: Ident, ns: Namespace) -> Self {
542        let ident = ident.normalize_to_macros_2_0();
543        BindingKey { ident, ns, disambiguator: 0 }
544    }
545}
546
547type Resolutions<'ra> = RefCell<FxIndexMap<BindingKey, &'ra RefCell<NameResolution<'ra>>>>;
548
549/// One node in the tree of modules.
550///
551/// Note that a "module" in resolve is broader than a `mod` that you declare in Rust code. It may be one of these:
552///
553/// * `mod`
554/// * crate root (aka, top-level anonymous module)
555/// * `enum`
556/// * `trait`
557/// * curly-braced block with statements
558///
559/// You can use [`ModuleData::kind`] to determine the kind of module this is.
560struct ModuleData<'ra> {
561    /// The direct parent module (it may not be a `mod`, however).
562    parent: Option<Module<'ra>>,
563    /// What kind of module this is, because this may not be a `mod`.
564    kind: ModuleKind,
565
566    /// Mapping between names and their (possibly in-progress) resolutions in this module.
567    /// Resolutions in modules from other crates are not populated until accessed.
568    lazy_resolutions: Resolutions<'ra>,
569    /// True if this is a module from other crate that needs to be populated on access.
570    populate_on_access: Cell<bool>,
571
572    /// Macro invocations that can expand into items in this module.
573    unexpanded_invocations: RefCell<FxHashSet<LocalExpnId>>,
574
575    /// Whether `#[no_implicit_prelude]` is active.
576    no_implicit_prelude: bool,
577
578    glob_importers: RefCell<Vec<Import<'ra>>>,
579    globs: RefCell<Vec<Import<'ra>>>,
580
581    /// Used to memoize the traits in this module for faster searches through all traits in scope.
582    traits: RefCell<Option<Box<[(Ident, NameBinding<'ra>)]>>>,
583
584    /// Span of the module itself. Used for error reporting.
585    span: Span,
586
587    expansion: ExpnId,
588}
589
590/// All modules are unique and allocated on a same arena,
591/// so we can use referential equality to compare them.
592#[derive(Clone, Copy, PartialEq, Eq, Hash)]
593#[rustc_pass_by_value]
594struct Module<'ra>(Interned<'ra, ModuleData<'ra>>);
595
596// Allows us to use Interned without actually enforcing (via Hash/PartialEq/...) uniqueness of the
597// contained data.
598// FIXME: We may wish to actually have at least debug-level assertions that Interned's guarantees
599// are upheld.
600impl std::hash::Hash for ModuleData<'_> {
601    fn hash<H>(&self, _: &mut H)
602    where
603        H: std::hash::Hasher,
604    {
605        unreachable!()
606    }
607}
608
609impl<'ra> ModuleData<'ra> {
610    fn new(
611        parent: Option<Module<'ra>>,
612        kind: ModuleKind,
613        expansion: ExpnId,
614        span: Span,
615        no_implicit_prelude: bool,
616    ) -> Self {
617        let is_foreign = match kind {
618            ModuleKind::Def(_, def_id, _) => !def_id.is_local(),
619            ModuleKind::Block => false,
620        };
621        ModuleData {
622            parent,
623            kind,
624            lazy_resolutions: Default::default(),
625            populate_on_access: Cell::new(is_foreign),
626            unexpanded_invocations: Default::default(),
627            no_implicit_prelude,
628            glob_importers: RefCell::new(Vec::new()),
629            globs: RefCell::new(Vec::new()),
630            traits: RefCell::new(None),
631            span,
632            expansion,
633        }
634    }
635}
636
637impl<'ra> Module<'ra> {
638    fn for_each_child<'tcx, R, F>(self, resolver: &mut R, mut f: F)
639    where
640        R: AsMut<Resolver<'ra, 'tcx>>,
641        F: FnMut(&mut R, Ident, Namespace, NameBinding<'ra>),
642    {
643        for (key, name_resolution) in resolver.as_mut().resolutions(self).borrow().iter() {
644            if let Some(binding) = name_resolution.borrow().binding {
645                f(resolver, key.ident, key.ns, binding);
646            }
647        }
648    }
649
650    /// This modifies `self` in place. The traits will be stored in `self.traits`.
651    fn ensure_traits<'tcx, R>(self, resolver: &mut R)
652    where
653        R: AsMut<Resolver<'ra, 'tcx>>,
654    {
655        let mut traits = self.traits.borrow_mut();
656        if traits.is_none() {
657            let mut collected_traits = Vec::new();
658            self.for_each_child(resolver, |_, name, ns, binding| {
659                if ns != TypeNS {
660                    return;
661                }
662                if let Res::Def(DefKind::Trait | DefKind::TraitAlias, _) = binding.res() {
663                    collected_traits.push((name, binding))
664                }
665            });
666            *traits = Some(collected_traits.into_boxed_slice());
667        }
668    }
669
670    fn res(self) -> Option<Res> {
671        match self.kind {
672            ModuleKind::Def(kind, def_id, _) => Some(Res::Def(kind, def_id)),
673            _ => None,
674        }
675    }
676
677    // Public for rustdoc.
678    fn def_id(self) -> DefId {
679        self.opt_def_id().expect("`ModuleData::def_id` is called on a block module")
680    }
681
682    fn opt_def_id(self) -> Option<DefId> {
683        match self.kind {
684            ModuleKind::Def(_, def_id, _) => Some(def_id),
685            _ => None,
686        }
687    }
688
689    // `self` resolves to the first module ancestor that `is_normal`.
690    fn is_normal(self) -> bool {
691        matches!(self.kind, ModuleKind::Def(DefKind::Mod, _, _))
692    }
693
694    fn is_trait(self) -> bool {
695        matches!(self.kind, ModuleKind::Def(DefKind::Trait, _, _))
696    }
697
698    fn nearest_item_scope(self) -> Module<'ra> {
699        match self.kind {
700            ModuleKind::Def(DefKind::Enum | DefKind::Trait, ..) => {
701                self.parent.expect("enum or trait module without a parent")
702            }
703            _ => self,
704        }
705    }
706
707    /// The [`DefId`] of the nearest `mod` item ancestor (which may be this module).
708    /// This may be the crate root.
709    fn nearest_parent_mod(self) -> DefId {
710        match self.kind {
711            ModuleKind::Def(DefKind::Mod, def_id, _) => def_id,
712            _ => self.parent.expect("non-root module without parent").nearest_parent_mod(),
713        }
714    }
715
716    fn is_ancestor_of(self, mut other: Self) -> bool {
717        while self != other {
718            if let Some(parent) = other.parent {
719                other = parent;
720            } else {
721                return false;
722            }
723        }
724        true
725    }
726}
727
728impl<'ra> std::ops::Deref for Module<'ra> {
729    type Target = ModuleData<'ra>;
730
731    fn deref(&self) -> &Self::Target {
732        &self.0
733    }
734}
735
736impl<'ra> fmt::Debug for Module<'ra> {
737    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
738        write!(f, "{:?}", self.res())
739    }
740}
741
742/// Records a possibly-private value, type, or module definition.
743#[derive(Clone, Copy, Debug)]
744struct NameBindingData<'ra> {
745    kind: NameBindingKind<'ra>,
746    ambiguity: Option<(NameBinding<'ra>, AmbiguityKind)>,
747    /// Produce a warning instead of an error when reporting ambiguities inside this binding.
748    /// May apply to indirect ambiguities under imports, so `ambiguity.is_some()` is not required.
749    warn_ambiguity: bool,
750    expansion: LocalExpnId,
751    span: Span,
752    vis: ty::Visibility<DefId>,
753}
754
755/// All name bindings are unique and allocated on a same arena,
756/// so we can use referential equality to compare them.
757type NameBinding<'ra> = Interned<'ra, NameBindingData<'ra>>;
758
759// Allows us to use Interned without actually enforcing (via Hash/PartialEq/...) uniqueness of the
760// contained data.
761// FIXME: We may wish to actually have at least debug-level assertions that Interned's guarantees
762// are upheld.
763impl std::hash::Hash for NameBindingData<'_> {
764    fn hash<H>(&self, _: &mut H)
765    where
766        H: std::hash::Hasher,
767    {
768        unreachable!()
769    }
770}
771
772trait ToNameBinding<'ra> {
773    fn to_name_binding(self, arenas: &'ra ResolverArenas<'ra>) -> NameBinding<'ra>;
774}
775
776impl<'ra> ToNameBinding<'ra> for NameBinding<'ra> {
777    fn to_name_binding(self, _: &'ra ResolverArenas<'ra>) -> NameBinding<'ra> {
778        self
779    }
780}
781
782#[derive(Clone, Copy, Debug)]
783enum NameBindingKind<'ra> {
784    Res(Res),
785    Module(Module<'ra>),
786    Import { binding: NameBinding<'ra>, import: Import<'ra> },
787}
788
789impl<'ra> NameBindingKind<'ra> {
790    /// Is this a name binding of an import?
791    fn is_import(&self) -> bool {
792        matches!(*self, NameBindingKind::Import { .. })
793    }
794}
795
796#[derive(Debug)]
797struct PrivacyError<'ra> {
798    ident: Ident,
799    binding: NameBinding<'ra>,
800    dedup_span: Span,
801    outermost_res: Option<(Res, Ident)>,
802    parent_scope: ParentScope<'ra>,
803    /// Is the format `use a::{b,c}`?
804    single_nested: bool,
805}
806
807#[derive(Debug)]
808struct UseError<'a> {
809    err: Diag<'a>,
810    /// Candidates which user could `use` to access the missing type.
811    candidates: Vec<ImportSuggestion>,
812    /// The `DefId` of the module to place the use-statements in.
813    def_id: DefId,
814    /// Whether the diagnostic should say "instead" (as in `consider importing ... instead`).
815    instead: bool,
816    /// Extra free-form suggestion.
817    suggestion: Option<(Span, &'static str, String, Applicability)>,
818    /// Path `Segment`s at the place of use that failed. Used for accurate suggestion after telling
819    /// the user to import the item directly.
820    path: Vec<Segment>,
821    /// Whether the expected source is a call
822    is_call: bool,
823}
824
825#[derive(Clone, Copy, PartialEq, Debug)]
826enum AmbiguityKind {
827    BuiltinAttr,
828    DeriveHelper,
829    MacroRulesVsModularized,
830    GlobVsOuter,
831    GlobVsGlob,
832    GlobVsExpanded,
833    MoreExpandedVsOuter,
834}
835
836impl AmbiguityKind {
837    fn descr(self) -> &'static str {
838        match self {
839            AmbiguityKind::BuiltinAttr => "a name conflict with a builtin attribute",
840            AmbiguityKind::DeriveHelper => "a name conflict with a derive helper attribute",
841            AmbiguityKind::MacroRulesVsModularized => {
842                "a conflict between a `macro_rules` name and a non-`macro_rules` name from another module"
843            }
844            AmbiguityKind::GlobVsOuter => {
845                "a conflict between a name from a glob import and an outer scope during import or macro resolution"
846            }
847            AmbiguityKind::GlobVsGlob => "multiple glob imports of a name in the same module",
848            AmbiguityKind::GlobVsExpanded => {
849                "a conflict between a name from a glob import and a macro-expanded name in the same module during import or macro resolution"
850            }
851            AmbiguityKind::MoreExpandedVsOuter => {
852                "a conflict between a macro-expanded name and a less macro-expanded name from outer scope during import or macro resolution"
853            }
854        }
855    }
856}
857
858/// Miscellaneous bits of metadata for better ambiguity error reporting.
859#[derive(Clone, Copy, PartialEq)]
860enum AmbiguityErrorMisc {
861    SuggestCrate,
862    SuggestSelf,
863    FromPrelude,
864    None,
865}
866
867struct AmbiguityError<'ra> {
868    kind: AmbiguityKind,
869    ident: Ident,
870    b1: NameBinding<'ra>,
871    b2: NameBinding<'ra>,
872    misc1: AmbiguityErrorMisc,
873    misc2: AmbiguityErrorMisc,
874    warning: bool,
875}
876
877impl<'ra> NameBindingData<'ra> {
878    fn module(&self) -> Option<Module<'ra>> {
879        match self.kind {
880            NameBindingKind::Module(module) => Some(module),
881            NameBindingKind::Import { binding, .. } => binding.module(),
882            _ => None,
883        }
884    }
885
886    fn res(&self) -> Res {
887        match self.kind {
888            NameBindingKind::Res(res) => res,
889            NameBindingKind::Module(module) => module.res().unwrap(),
890            NameBindingKind::Import { binding, .. } => binding.res(),
891        }
892    }
893
894    fn is_ambiguity_recursive(&self) -> bool {
895        self.ambiguity.is_some()
896            || match self.kind {
897                NameBindingKind::Import { binding, .. } => binding.is_ambiguity_recursive(),
898                _ => false,
899            }
900    }
901
902    fn warn_ambiguity_recursive(&self) -> bool {
903        self.warn_ambiguity
904            || match self.kind {
905                NameBindingKind::Import { binding, .. } => binding.warn_ambiguity_recursive(),
906                _ => false,
907            }
908    }
909
910    fn is_possibly_imported_variant(&self) -> bool {
911        match self.kind {
912            NameBindingKind::Import { binding, .. } => binding.is_possibly_imported_variant(),
913            NameBindingKind::Res(Res::Def(
914                DefKind::Variant | DefKind::Ctor(CtorOf::Variant, ..),
915                _,
916            )) => true,
917            NameBindingKind::Res(..) | NameBindingKind::Module(..) => false,
918        }
919    }
920
921    fn is_extern_crate(&self) -> bool {
922        match self.kind {
923            NameBindingKind::Import { import, .. } => {
924                matches!(import.kind, ImportKind::ExternCrate { .. })
925            }
926            NameBindingKind::Module(module)
927                if let ModuleKind::Def(DefKind::Mod, def_id, _) = module.kind =>
928            {
929                def_id.is_crate_root()
930            }
931            _ => false,
932        }
933    }
934
935    fn is_import(&self) -> bool {
936        matches!(self.kind, NameBindingKind::Import { .. })
937    }
938
939    /// The binding introduced by `#[macro_export] macro_rules` is a public import, but it might
940    /// not be perceived as such by users, so treat it as a non-import in some diagnostics.
941    fn is_import_user_facing(&self) -> bool {
942        matches!(self.kind, NameBindingKind::Import { import, .. }
943            if !matches!(import.kind, ImportKind::MacroExport))
944    }
945
946    fn is_glob_import(&self) -> bool {
947        match self.kind {
948            NameBindingKind::Import { import, .. } => import.is_glob(),
949            _ => false,
950        }
951    }
952
953    fn is_assoc_item(&self) -> bool {
954        matches!(self.res(), Res::Def(DefKind::AssocConst | DefKind::AssocFn | DefKind::AssocTy, _))
955    }
956
957    fn macro_kind(&self) -> Option<MacroKind> {
958        self.res().macro_kind()
959    }
960
961    // Suppose that we resolved macro invocation with `invoc_parent_expansion` to binding `binding`
962    // at some expansion round `max(invoc, binding)` when they both emerged from macros.
963    // Then this function returns `true` if `self` may emerge from a macro *after* that
964    // in some later round and screw up our previously found resolution.
965    // See more detailed explanation in
966    // https://github.com/rust-lang/rust/pull/53778#issuecomment-419224049
967    fn may_appear_after(
968        &self,
969        invoc_parent_expansion: LocalExpnId,
970        binding: NameBinding<'_>,
971    ) -> bool {
972        // self > max(invoc, binding) => !(self <= invoc || self <= binding)
973        // Expansions are partially ordered, so "may appear after" is an inversion of
974        // "certainly appears before or simultaneously" and includes unordered cases.
975        let self_parent_expansion = self.expansion;
976        let other_parent_expansion = binding.expansion;
977        let certainly_before_other_or_simultaneously =
978            other_parent_expansion.is_descendant_of(self_parent_expansion);
979        let certainly_before_invoc_or_simultaneously =
980            invoc_parent_expansion.is_descendant_of(self_parent_expansion);
981        !(certainly_before_other_or_simultaneously || certainly_before_invoc_or_simultaneously)
982    }
983
984    // Its purpose is to postpone the determination of a single binding because
985    // we can't predict whether it will be overwritten by recently expanded macros.
986    // FIXME: How can we integrate it with the `update_resolution`?
987    fn determined(&self) -> bool {
988        match &self.kind {
989            NameBindingKind::Import { binding, import, .. } if import.is_glob() => {
990                import.parent_scope.module.unexpanded_invocations.borrow().is_empty()
991                    && binding.determined()
992            }
993            _ => true,
994        }
995    }
996}
997
998#[derive(Default, Clone)]
999struct ExternPreludeEntry<'ra> {
1000    binding: Option<NameBinding<'ra>>,
1001    introduced_by_item: bool,
1002}
1003
1004impl ExternPreludeEntry<'_> {
1005    fn is_import(&self) -> bool {
1006        self.binding.is_some_and(|binding| binding.is_import())
1007    }
1008}
1009
1010struct DeriveData {
1011    resolutions: Vec<DeriveResolution>,
1012    helper_attrs: Vec<(usize, Ident)>,
1013    has_derive_copy: bool,
1014}
1015
1016struct MacroData {
1017    ext: Arc<SyntaxExtension>,
1018    nrules: usize,
1019    macro_rules: bool,
1020}
1021
1022impl MacroData {
1023    fn new(ext: Arc<SyntaxExtension>) -> MacroData {
1024        MacroData { ext, nrules: 0, macro_rules: false }
1025    }
1026}
1027
1028/// The main resolver class.
1029///
1030/// This is the visitor that walks the whole crate.
1031pub struct Resolver<'ra, 'tcx> {
1032    tcx: TyCtxt<'tcx>,
1033
1034    /// Item with a given `LocalDefId` was defined during macro expansion with ID `ExpnId`.
1035    expn_that_defined: UnordMap<LocalDefId, ExpnId>,
1036
1037    graph_root: Module<'ra>,
1038
1039    prelude: Option<Module<'ra>>,
1040    extern_prelude: FxIndexMap<Ident, ExternPreludeEntry<'ra>>,
1041
1042    /// N.B., this is used only for better diagnostics, not name resolution itself.
1043    field_names: LocalDefIdMap<Vec<Ident>>,
1044
1045    /// Span of the privacy modifier in fields of an item `DefId` accessible with dot syntax.
1046    /// Used for hints during error reporting.
1047    field_visibility_spans: FxHashMap<DefId, Vec<Span>>,
1048
1049    /// All imports known to succeed or fail.
1050    determined_imports: Vec<Import<'ra>>,
1051
1052    /// All non-determined imports.
1053    indeterminate_imports: Vec<Import<'ra>>,
1054
1055    // Spans for local variables found during pattern resolution.
1056    // Used for suggestions during error reporting.
1057    pat_span_map: NodeMap<Span>,
1058
1059    /// Resolutions for nodes that have a single resolution.
1060    partial_res_map: NodeMap<PartialRes>,
1061    /// Resolutions for import nodes, which have multiple resolutions in different namespaces.
1062    import_res_map: NodeMap<PerNS<Option<Res>>>,
1063    /// An import will be inserted into this map if it has been used.
1064    import_use_map: FxHashMap<Import<'ra>, Used>,
1065    /// Resolutions for labels (node IDs of their corresponding blocks or loops).
1066    label_res_map: NodeMap<NodeId>,
1067    /// Resolutions for lifetimes.
1068    lifetimes_res_map: NodeMap<LifetimeRes>,
1069    /// Lifetime parameters that lowering will have to introduce.
1070    extra_lifetime_params_map: NodeMap<Vec<(Ident, NodeId, LifetimeRes)>>,
1071
1072    /// `CrateNum` resolutions of `extern crate` items.
1073    extern_crate_map: UnordMap<LocalDefId, CrateNum>,
1074    module_children: LocalDefIdMap<Vec<ModChild>>,
1075    trait_map: NodeMap<Vec<TraitCandidate>>,
1076
1077    /// A map from nodes to anonymous modules.
1078    /// Anonymous modules are pseudo-modules that are implicitly created around items
1079    /// contained within blocks.
1080    ///
1081    /// For example, if we have this:
1082    ///
1083    ///  fn f() {
1084    ///      fn g() {
1085    ///          ...
1086    ///      }
1087    ///  }
1088    ///
1089    /// There will be an anonymous module created around `g` with the ID of the
1090    /// entry block for `f`.
1091    block_map: NodeMap<Module<'ra>>,
1092    /// A fake module that contains no definition and no prelude. Used so that
1093    /// some AST passes can generate identifiers that only resolve to local or
1094    /// lang items.
1095    empty_module: Module<'ra>,
1096    module_map: FxIndexMap<DefId, Module<'ra>>,
1097    binding_parent_modules: FxHashMap<NameBinding<'ra>, Module<'ra>>,
1098
1099    underscore_disambiguator: u32,
1100
1101    /// Maps glob imports to the names of items actually imported.
1102    glob_map: FxIndexMap<LocalDefId, FxIndexSet<Symbol>>,
1103    glob_error: Option<ErrorGuaranteed>,
1104    visibilities_for_hashing: Vec<(LocalDefId, ty::Visibility)>,
1105    used_imports: FxHashSet<NodeId>,
1106    maybe_unused_trait_imports: FxIndexSet<LocalDefId>,
1107
1108    /// Privacy errors are delayed until the end in order to deduplicate them.
1109    privacy_errors: Vec<PrivacyError<'ra>>,
1110    /// Ambiguity errors are delayed for deduplication.
1111    ambiguity_errors: Vec<AmbiguityError<'ra>>,
1112    /// `use` injections are delayed for better placement and deduplication.
1113    use_injections: Vec<UseError<'tcx>>,
1114    /// Crate-local macro expanded `macro_export` referred to by a module-relative path.
1115    macro_expanded_macro_export_errors: BTreeSet<(Span, Span)>,
1116
1117    arenas: &'ra ResolverArenas<'ra>,
1118    dummy_binding: NameBinding<'ra>,
1119    builtin_types_bindings: FxHashMap<Symbol, NameBinding<'ra>>,
1120    builtin_attrs_bindings: FxHashMap<Symbol, NameBinding<'ra>>,
1121    registered_tool_bindings: FxHashMap<Ident, NameBinding<'ra>>,
1122    /// Binding for implicitly declared names that come with a module,
1123    /// like `self` (not yet used), or `crate`/`$crate` (for root modules).
1124    module_self_bindings: FxHashMap<Module<'ra>, NameBinding<'ra>>,
1125
1126    used_extern_options: FxHashSet<Symbol>,
1127    macro_names: FxHashSet<Ident>,
1128    builtin_macros: FxHashMap<Symbol, SyntaxExtensionKind>,
1129    registered_tools: &'tcx RegisteredTools,
1130    macro_use_prelude: FxIndexMap<Symbol, NameBinding<'ra>>,
1131    macro_map: FxHashMap<DefId, MacroData>,
1132    dummy_ext_bang: Arc<SyntaxExtension>,
1133    dummy_ext_derive: Arc<SyntaxExtension>,
1134    non_macro_attr: MacroData,
1135    local_macro_def_scopes: FxHashMap<LocalDefId, Module<'ra>>,
1136    ast_transform_scopes: FxHashMap<LocalExpnId, Module<'ra>>,
1137    unused_macros: FxIndexMap<LocalDefId, (NodeId, Ident)>,
1138    /// A map from the macro to all its potentially unused arms.
1139    unused_macro_rules: FxIndexMap<NodeId, DenseBitSet<usize>>,
1140    proc_macro_stubs: FxHashSet<LocalDefId>,
1141    /// Traces collected during macro resolution and validated when it's complete.
1142    single_segment_macro_resolutions:
1143        Vec<(Ident, MacroKind, ParentScope<'ra>, Option<NameBinding<'ra>>, Option<Span>)>,
1144    multi_segment_macro_resolutions:
1145        Vec<(Vec<Segment>, Span, MacroKind, ParentScope<'ra>, Option<Res>, Namespace)>,
1146    builtin_attrs: Vec<(Ident, ParentScope<'ra>)>,
1147    /// `derive(Copy)` marks items they are applied to so they are treated specially later.
1148    /// Derive macros cannot modify the item themselves and have to store the markers in the global
1149    /// context, so they attach the markers to derive container IDs using this resolver table.
1150    containers_deriving_copy: FxHashSet<LocalExpnId>,
1151    /// Parent scopes in which the macros were invoked.
1152    /// FIXME: `derives` are missing in these parent scopes and need to be taken from elsewhere.
1153    invocation_parent_scopes: FxHashMap<LocalExpnId, ParentScope<'ra>>,
1154    /// `macro_rules` scopes *produced* by expanding the macro invocations,
1155    /// include all the `macro_rules` items and other invocations generated by them.
1156    output_macro_rules_scopes: FxHashMap<LocalExpnId, MacroRulesScopeRef<'ra>>,
1157    /// `macro_rules` scopes produced by `macro_rules` item definitions.
1158    macro_rules_scopes: FxHashMap<LocalDefId, MacroRulesScopeRef<'ra>>,
1159    /// Helper attributes that are in scope for the given expansion.
1160    helper_attrs: FxHashMap<LocalExpnId, Vec<(Ident, NameBinding<'ra>)>>,
1161    /// Ready or in-progress results of resolving paths inside the `#[derive(...)]` attribute
1162    /// with the given `ExpnId`.
1163    derive_data: FxHashMap<LocalExpnId, DeriveData>,
1164
1165    /// Avoid duplicated errors for "name already defined".
1166    name_already_seen: FxHashMap<Symbol, Span>,
1167
1168    potentially_unused_imports: Vec<Import<'ra>>,
1169
1170    potentially_unnecessary_qualifications: Vec<UnnecessaryQualification<'ra>>,
1171
1172    /// Table for mapping struct IDs into struct constructor IDs,
1173    /// it's not used during normal resolution, only for better error reporting.
1174    /// Also includes of list of each fields visibility
1175    struct_constructors: LocalDefIdMap<(Res, ty::Visibility<DefId>, Vec<ty::Visibility<DefId>>)>,
1176
1177    lint_buffer: LintBuffer,
1178
1179    next_node_id: NodeId,
1180
1181    node_id_to_def_id: NodeMap<Feed<'tcx, LocalDefId>>,
1182
1183    disambiguator: DisambiguatorState,
1184
1185    /// Indices of unnamed struct or variant fields with unresolved attributes.
1186    placeholder_field_indices: FxHashMap<NodeId, usize>,
1187    /// When collecting definitions from an AST fragment produced by a macro invocation `ExpnId`
1188    /// we know what parent node that fragment should be attached to thanks to this table,
1189    /// and how the `impl Trait` fragments were introduced.
1190    invocation_parents: FxHashMap<LocalExpnId, InvocationParent>,
1191
1192    legacy_const_generic_args: FxHashMap<DefId, Option<Vec<usize>>>,
1193    /// Amount of lifetime parameters for each item in the crate.
1194    item_generics_num_lifetimes: FxHashMap<LocalDefId, usize>,
1195    delegation_fn_sigs: LocalDefIdMap<DelegationFnSig>,
1196
1197    main_def: Option<MainDefinition>,
1198    trait_impls: FxIndexMap<DefId, Vec<LocalDefId>>,
1199    /// A list of proc macro LocalDefIds, written out in the order in which
1200    /// they are declared in the static array generated by proc_macro_harness.
1201    proc_macros: Vec<LocalDefId>,
1202    confused_type_with_std_module: FxIndexMap<Span, Span>,
1203    /// Whether lifetime elision was successful.
1204    lifetime_elision_allowed: FxHashSet<NodeId>,
1205
1206    /// Names of items that were stripped out via cfg with their corresponding cfg meta item.
1207    stripped_cfg_items: Vec<StrippedCfgItem<NodeId>>,
1208
1209    effective_visibilities: EffectiveVisibilities,
1210    doc_link_resolutions: FxIndexMap<LocalDefId, DocLinkResMap>,
1211    doc_link_traits_in_scope: FxIndexMap<LocalDefId, Vec<DefId>>,
1212    all_macro_rules: UnordSet<Symbol>,
1213
1214    /// Invocation ids of all glob delegations.
1215    glob_delegation_invoc_ids: FxHashSet<LocalExpnId>,
1216    /// Analogue of module `unexpanded_invocations` but in trait impls, excluding glob delegations.
1217    /// Needed because glob delegations wait for all other neighboring macros to expand.
1218    impl_unexpanded_invocations: FxHashMap<LocalDefId, FxHashSet<LocalExpnId>>,
1219    /// Simplified analogue of module `resolutions` but in trait impls, excluding glob delegations.
1220    /// Needed because glob delegations exclude explicitly defined names.
1221    impl_binding_keys: FxHashMap<LocalDefId, FxHashSet<BindingKey>>,
1222
1223    /// This is the `Span` where an `extern crate foo;` suggestion would be inserted, if `foo`
1224    /// could be a crate that wasn't imported. For diagnostics use only.
1225    current_crate_outer_attr_insert_span: Span,
1226
1227    mods_with_parse_errors: FxHashSet<DefId>,
1228
1229    // Stores pre-expansion and pre-placeholder-fragment-insertion names for `impl Trait` types
1230    // that were encountered during resolution. These names are used to generate item names
1231    // for APITs, so we don't want to leak details of resolution into these names.
1232    impl_trait_names: FxHashMap<NodeId, Symbol>,
1233}
1234
1235/// This provides memory for the rest of the crate. The `'ra` lifetime that is
1236/// used by many types in this crate is an abbreviation of `ResolverArenas`.
1237#[derive(Default)]
1238pub struct ResolverArenas<'ra> {
1239    modules: TypedArena<ModuleData<'ra>>,
1240    local_modules: RefCell<Vec<Module<'ra>>>,
1241    imports: TypedArena<ImportData<'ra>>,
1242    name_resolutions: TypedArena<RefCell<NameResolution<'ra>>>,
1243    ast_paths: TypedArena<ast::Path>,
1244    dropless: DroplessArena,
1245}
1246
1247impl<'ra> ResolverArenas<'ra> {
1248    fn new_module(
1249        &'ra self,
1250        parent: Option<Module<'ra>>,
1251        kind: ModuleKind,
1252        expn_id: ExpnId,
1253        span: Span,
1254        no_implicit_prelude: bool,
1255        module_map: &mut FxIndexMap<DefId, Module<'ra>>,
1256        module_self_bindings: &mut FxHashMap<Module<'ra>, NameBinding<'ra>>,
1257    ) -> Module<'ra> {
1258        let module = Module(Interned::new_unchecked(self.modules.alloc(ModuleData::new(
1259            parent,
1260            kind,
1261            expn_id,
1262            span,
1263            no_implicit_prelude,
1264        ))));
1265        let def_id = module.opt_def_id();
1266        if def_id.is_none_or(|def_id| def_id.is_local()) {
1267            self.local_modules.borrow_mut().push(module);
1268        }
1269        if let Some(def_id) = def_id {
1270            module_map.insert(def_id, module);
1271            let vis = ty::Visibility::<DefId>::Public;
1272            let binding = (module, vis, module.span, LocalExpnId::ROOT).to_name_binding(self);
1273            module_self_bindings.insert(module, binding);
1274        }
1275        module
1276    }
1277    fn local_modules(&'ra self) -> std::cell::Ref<'ra, Vec<Module<'ra>>> {
1278        self.local_modules.borrow()
1279    }
1280    fn alloc_name_binding(&'ra self, name_binding: NameBindingData<'ra>) -> NameBinding<'ra> {
1281        Interned::new_unchecked(self.dropless.alloc(name_binding))
1282    }
1283    fn alloc_import(&'ra self, import: ImportData<'ra>) -> Import<'ra> {
1284        Interned::new_unchecked(self.imports.alloc(import))
1285    }
1286    fn alloc_name_resolution(&'ra self) -> &'ra RefCell<NameResolution<'ra>> {
1287        self.name_resolutions.alloc(Default::default())
1288    }
1289    fn alloc_macro_rules_scope(&'ra self, scope: MacroRulesScope<'ra>) -> MacroRulesScopeRef<'ra> {
1290        Interned::new_unchecked(self.dropless.alloc(Cell::new(scope)))
1291    }
1292    fn alloc_macro_rules_binding(
1293        &'ra self,
1294        binding: MacroRulesBinding<'ra>,
1295    ) -> &'ra MacroRulesBinding<'ra> {
1296        self.dropless.alloc(binding)
1297    }
1298    fn alloc_ast_paths(&'ra self, paths: &[ast::Path]) -> &'ra [ast::Path] {
1299        self.ast_paths.alloc_from_iter(paths.iter().cloned())
1300    }
1301    fn alloc_pattern_spans(&'ra self, spans: impl Iterator<Item = Span>) -> &'ra [Span] {
1302        self.dropless.alloc_from_iter(spans)
1303    }
1304}
1305
1306impl<'ra, 'tcx> AsMut<Resolver<'ra, 'tcx>> for Resolver<'ra, 'tcx> {
1307    fn as_mut(&mut self) -> &mut Resolver<'ra, 'tcx> {
1308        self
1309    }
1310}
1311
1312impl<'tcx> Resolver<'_, 'tcx> {
1313    fn opt_local_def_id(&self, node: NodeId) -> Option<LocalDefId> {
1314        self.opt_feed(node).map(|f| f.key())
1315    }
1316
1317    fn local_def_id(&self, node: NodeId) -> LocalDefId {
1318        self.feed(node).key()
1319    }
1320
1321    fn opt_feed(&self, node: NodeId) -> Option<Feed<'tcx, LocalDefId>> {
1322        self.node_id_to_def_id.get(&node).copied()
1323    }
1324
1325    fn feed(&self, node: NodeId) -> Feed<'tcx, LocalDefId> {
1326        self.opt_feed(node).unwrap_or_else(|| panic!("no entry for node id: `{node:?}`"))
1327    }
1328
1329    fn local_def_kind(&self, node: NodeId) -> DefKind {
1330        self.tcx.def_kind(self.local_def_id(node))
1331    }
1332
1333    /// Adds a definition with a parent definition.
1334    fn create_def(
1335        &mut self,
1336        parent: LocalDefId,
1337        node_id: ast::NodeId,
1338        name: Option<Symbol>,
1339        def_kind: DefKind,
1340        expn_id: ExpnId,
1341        span: Span,
1342    ) -> TyCtxtFeed<'tcx, LocalDefId> {
1343        assert!(
1344            !self.node_id_to_def_id.contains_key(&node_id),
1345            "adding a def for node-id {:?}, name {:?}, data {:?} but a previous def exists: {:?}",
1346            node_id,
1347            name,
1348            def_kind,
1349            self.tcx.definitions_untracked().def_key(self.node_id_to_def_id[&node_id].key()),
1350        );
1351
1352        // FIXME: remove `def_span` body, pass in the right spans here and call `tcx.at().create_def()`
1353        let feed = self.tcx.create_def(parent, name, def_kind, None, &mut self.disambiguator);
1354        let def_id = feed.def_id();
1355
1356        // Create the definition.
1357        if expn_id != ExpnId::root() {
1358            self.expn_that_defined.insert(def_id, expn_id);
1359        }
1360
1361        // A relative span's parent must be an absolute span.
1362        debug_assert_eq!(span.data_untracked().parent, None);
1363        let _id = self.tcx.untracked().source_span.push(span);
1364        debug_assert_eq!(_id, def_id);
1365
1366        // Some things for which we allocate `LocalDefId`s don't correspond to
1367        // anything in the AST, so they don't have a `NodeId`. For these cases
1368        // we don't need a mapping from `NodeId` to `LocalDefId`.
1369        if node_id != ast::DUMMY_NODE_ID {
1370            debug!("create_def: def_id_to_node_id[{:?}] <-> {:?}", def_id, node_id);
1371            self.node_id_to_def_id.insert(node_id, feed.downgrade());
1372        }
1373
1374        feed
1375    }
1376
1377    fn item_generics_num_lifetimes(&self, def_id: DefId) -> usize {
1378        if let Some(def_id) = def_id.as_local() {
1379            self.item_generics_num_lifetimes[&def_id]
1380        } else {
1381            self.tcx.generics_of(def_id).own_counts().lifetimes
1382        }
1383    }
1384
1385    pub fn tcx(&self) -> TyCtxt<'tcx> {
1386        self.tcx
1387    }
1388
1389    /// This function is very slow, as it iterates over the entire
1390    /// [Resolver::node_id_to_def_id] map just to find the [NodeId]
1391    /// that corresponds to the given [LocalDefId]. Only use this in
1392    /// diagnostics code paths.
1393    fn def_id_to_node_id(&self, def_id: LocalDefId) -> NodeId {
1394        self.node_id_to_def_id
1395            .items()
1396            .filter(|(_, v)| v.key() == def_id)
1397            .map(|(k, _)| *k)
1398            .get_only()
1399            .unwrap()
1400    }
1401}
1402
1403impl<'ra, 'tcx> Resolver<'ra, 'tcx> {
1404    pub fn new(
1405        tcx: TyCtxt<'tcx>,
1406        attrs: &[ast::Attribute],
1407        crate_span: Span,
1408        current_crate_outer_attr_insert_span: Span,
1409        arenas: &'ra ResolverArenas<'ra>,
1410    ) -> Resolver<'ra, 'tcx> {
1411        let root_def_id = CRATE_DEF_ID.to_def_id();
1412        let mut module_map = FxIndexMap::default();
1413        let mut module_self_bindings = FxHashMap::default();
1414        let graph_root = arenas.new_module(
1415            None,
1416            ModuleKind::Def(DefKind::Mod, root_def_id, None),
1417            ExpnId::root(),
1418            crate_span,
1419            attr::contains_name(attrs, sym::no_implicit_prelude),
1420            &mut module_map,
1421            &mut module_self_bindings,
1422        );
1423        let empty_module = arenas.new_module(
1424            None,
1425            ModuleKind::Def(DefKind::Mod, root_def_id, None),
1426            ExpnId::root(),
1427            DUMMY_SP,
1428            true,
1429            &mut Default::default(),
1430            &mut Default::default(),
1431        );
1432
1433        let mut node_id_to_def_id = NodeMap::default();
1434        let crate_feed = tcx.create_local_crate_def_id(crate_span);
1435
1436        crate_feed.def_kind(DefKind::Mod);
1437        let crate_feed = crate_feed.downgrade();
1438        node_id_to_def_id.insert(CRATE_NODE_ID, crate_feed);
1439
1440        let mut invocation_parents = FxHashMap::default();
1441        invocation_parents.insert(LocalExpnId::ROOT, InvocationParent::ROOT);
1442
1443        let mut extern_prelude: FxIndexMap<Ident, ExternPreludeEntry<'_>> = tcx
1444            .sess
1445            .opts
1446            .externs
1447            .iter()
1448            .filter(|(_, entry)| entry.add_prelude)
1449            .map(|(name, _)| (Ident::from_str(name), Default::default()))
1450            .collect();
1451
1452        if !attr::contains_name(attrs, sym::no_core) {
1453            extern_prelude.insert(Ident::with_dummy_span(sym::core), Default::default());
1454            if !attr::contains_name(attrs, sym::no_std) {
1455                extern_prelude.insert(Ident::with_dummy_span(sym::std), Default::default());
1456            }
1457        }
1458
1459        let registered_tools = tcx.registered_tools(());
1460
1461        let pub_vis = ty::Visibility::<DefId>::Public;
1462        let edition = tcx.sess.edition();
1463
1464        let mut resolver = Resolver {
1465            tcx,
1466
1467            expn_that_defined: Default::default(),
1468
1469            // The outermost module has def ID 0; this is not reflected in the
1470            // AST.
1471            graph_root,
1472            prelude: None,
1473            extern_prelude,
1474
1475            field_names: Default::default(),
1476            field_visibility_spans: FxHashMap::default(),
1477
1478            determined_imports: Vec::new(),
1479            indeterminate_imports: Vec::new(),
1480
1481            pat_span_map: Default::default(),
1482            partial_res_map: Default::default(),
1483            import_res_map: Default::default(),
1484            import_use_map: Default::default(),
1485            label_res_map: Default::default(),
1486            lifetimes_res_map: Default::default(),
1487            extra_lifetime_params_map: Default::default(),
1488            extern_crate_map: Default::default(),
1489            module_children: Default::default(),
1490            trait_map: NodeMap::default(),
1491            underscore_disambiguator: 0,
1492            empty_module,
1493            module_map,
1494            block_map: Default::default(),
1495            binding_parent_modules: FxHashMap::default(),
1496            ast_transform_scopes: FxHashMap::default(),
1497
1498            glob_map: Default::default(),
1499            glob_error: None,
1500            visibilities_for_hashing: Default::default(),
1501            used_imports: FxHashSet::default(),
1502            maybe_unused_trait_imports: Default::default(),
1503
1504            privacy_errors: Vec::new(),
1505            ambiguity_errors: Vec::new(),
1506            use_injections: Vec::new(),
1507            macro_expanded_macro_export_errors: BTreeSet::new(),
1508
1509            arenas,
1510            dummy_binding: (Res::Err, pub_vis, DUMMY_SP, LocalExpnId::ROOT).to_name_binding(arenas),
1511            builtin_types_bindings: PrimTy::ALL
1512                .iter()
1513                .map(|prim_ty| {
1514                    let binding = (Res::PrimTy(*prim_ty), pub_vis, DUMMY_SP, LocalExpnId::ROOT)
1515                        .to_name_binding(arenas);
1516                    (prim_ty.name(), binding)
1517                })
1518                .collect(),
1519            builtin_attrs_bindings: BUILTIN_ATTRIBUTES
1520                .iter()
1521                .map(|builtin_attr| {
1522                    let res = Res::NonMacroAttr(NonMacroAttrKind::Builtin(builtin_attr.name));
1523                    let binding =
1524                        (res, pub_vis, DUMMY_SP, LocalExpnId::ROOT).to_name_binding(arenas);
1525                    (builtin_attr.name, binding)
1526                })
1527                .collect(),
1528            registered_tool_bindings: registered_tools
1529                .iter()
1530                .map(|ident| {
1531                    let binding = (Res::ToolMod, pub_vis, ident.span, LocalExpnId::ROOT)
1532                        .to_name_binding(arenas);
1533                    (*ident, binding)
1534                })
1535                .collect(),
1536            module_self_bindings,
1537
1538            used_extern_options: Default::default(),
1539            macro_names: FxHashSet::default(),
1540            builtin_macros: Default::default(),
1541            registered_tools,
1542            macro_use_prelude: Default::default(),
1543            macro_map: FxHashMap::default(),
1544            dummy_ext_bang: Arc::new(SyntaxExtension::dummy_bang(edition)),
1545            dummy_ext_derive: Arc::new(SyntaxExtension::dummy_derive(edition)),
1546            non_macro_attr: MacroData::new(Arc::new(SyntaxExtension::non_macro_attr(edition))),
1547            invocation_parent_scopes: Default::default(),
1548            output_macro_rules_scopes: Default::default(),
1549            macro_rules_scopes: Default::default(),
1550            helper_attrs: Default::default(),
1551            derive_data: Default::default(),
1552            local_macro_def_scopes: FxHashMap::default(),
1553            name_already_seen: FxHashMap::default(),
1554            potentially_unused_imports: Vec::new(),
1555            potentially_unnecessary_qualifications: Default::default(),
1556            struct_constructors: Default::default(),
1557            unused_macros: Default::default(),
1558            unused_macro_rules: Default::default(),
1559            proc_macro_stubs: Default::default(),
1560            single_segment_macro_resolutions: Default::default(),
1561            multi_segment_macro_resolutions: Default::default(),
1562            builtin_attrs: Default::default(),
1563            containers_deriving_copy: Default::default(),
1564            lint_buffer: LintBuffer::default(),
1565            next_node_id: CRATE_NODE_ID,
1566            node_id_to_def_id,
1567            disambiguator: DisambiguatorState::new(),
1568            placeholder_field_indices: Default::default(),
1569            invocation_parents,
1570            legacy_const_generic_args: Default::default(),
1571            item_generics_num_lifetimes: Default::default(),
1572            main_def: Default::default(),
1573            trait_impls: Default::default(),
1574            proc_macros: Default::default(),
1575            confused_type_with_std_module: Default::default(),
1576            lifetime_elision_allowed: Default::default(),
1577            stripped_cfg_items: Default::default(),
1578            effective_visibilities: Default::default(),
1579            doc_link_resolutions: Default::default(),
1580            doc_link_traits_in_scope: Default::default(),
1581            all_macro_rules: Default::default(),
1582            delegation_fn_sigs: Default::default(),
1583            glob_delegation_invoc_ids: Default::default(),
1584            impl_unexpanded_invocations: Default::default(),
1585            impl_binding_keys: Default::default(),
1586            current_crate_outer_attr_insert_span,
1587            mods_with_parse_errors: Default::default(),
1588            impl_trait_names: Default::default(),
1589        };
1590
1591        let root_parent_scope = ParentScope::module(graph_root, &resolver);
1592        resolver.invocation_parent_scopes.insert(LocalExpnId::ROOT, root_parent_scope);
1593        resolver.feed_visibility(crate_feed, ty::Visibility::Public);
1594
1595        resolver
1596    }
1597
1598    fn new_module(
1599        &mut self,
1600        parent: Option<Module<'ra>>,
1601        kind: ModuleKind,
1602        expn_id: ExpnId,
1603        span: Span,
1604        no_implicit_prelude: bool,
1605    ) -> Module<'ra> {
1606        let module_map = &mut self.module_map;
1607        let module_self_bindings = &mut self.module_self_bindings;
1608        self.arenas.new_module(
1609            parent,
1610            kind,
1611            expn_id,
1612            span,
1613            no_implicit_prelude,
1614            module_map,
1615            module_self_bindings,
1616        )
1617    }
1618
1619    fn next_node_id(&mut self) -> NodeId {
1620        let start = self.next_node_id;
1621        let next = start.as_u32().checked_add(1).expect("input too large; ran out of NodeIds");
1622        self.next_node_id = ast::NodeId::from_u32(next);
1623        start
1624    }
1625
1626    fn next_node_ids(&mut self, count: usize) -> std::ops::Range<NodeId> {
1627        let start = self.next_node_id;
1628        let end = start.as_usize().checked_add(count).expect("input too large; ran out of NodeIds");
1629        self.next_node_id = ast::NodeId::from_usize(end);
1630        start..self.next_node_id
1631    }
1632
1633    pub fn lint_buffer(&mut self) -> &mut LintBuffer {
1634        &mut self.lint_buffer
1635    }
1636
1637    pub fn arenas() -> ResolverArenas<'ra> {
1638        Default::default()
1639    }
1640
1641    fn feed_visibility(&mut self, feed: Feed<'tcx, LocalDefId>, vis: ty::Visibility) {
1642        let feed = feed.upgrade(self.tcx);
1643        feed.visibility(vis.to_def_id());
1644        self.visibilities_for_hashing.push((feed.def_id(), vis));
1645    }
1646
1647    pub fn into_outputs(self) -> ResolverOutputs {
1648        let proc_macros = self.proc_macros;
1649        let expn_that_defined = self.expn_that_defined;
1650        let extern_crate_map = self.extern_crate_map;
1651        let maybe_unused_trait_imports = self.maybe_unused_trait_imports;
1652        let glob_map = self.glob_map;
1653        let main_def = self.main_def;
1654        let confused_type_with_std_module = self.confused_type_with_std_module;
1655        let effective_visibilities = self.effective_visibilities;
1656
1657        let stripped_cfg_items = self
1658            .stripped_cfg_items
1659            .into_iter()
1660            .filter_map(|item| {
1661                let parent_module =
1662                    self.node_id_to_def_id.get(&item.parent_module)?.key().to_def_id();
1663                Some(StrippedCfgItem { parent_module, ident: item.ident, cfg: item.cfg })
1664            })
1665            .collect();
1666
1667        let global_ctxt = ResolverGlobalCtxt {
1668            expn_that_defined,
1669            visibilities_for_hashing: self.visibilities_for_hashing,
1670            effective_visibilities,
1671            extern_crate_map,
1672            module_children: self.module_children,
1673            glob_map,
1674            maybe_unused_trait_imports,
1675            main_def,
1676            trait_impls: self.trait_impls,
1677            proc_macros,
1678            confused_type_with_std_module,
1679            doc_link_resolutions: self.doc_link_resolutions,
1680            doc_link_traits_in_scope: self.doc_link_traits_in_scope,
1681            all_macro_rules: self.all_macro_rules,
1682            stripped_cfg_items,
1683        };
1684        let ast_lowering = ty::ResolverAstLowering {
1685            legacy_const_generic_args: self.legacy_const_generic_args,
1686            partial_res_map: self.partial_res_map,
1687            import_res_map: self.import_res_map,
1688            label_res_map: self.label_res_map,
1689            lifetimes_res_map: self.lifetimes_res_map,
1690            extra_lifetime_params_map: self.extra_lifetime_params_map,
1691            next_node_id: self.next_node_id,
1692            node_id_to_def_id: self
1693                .node_id_to_def_id
1694                .into_items()
1695                .map(|(k, f)| (k, f.key()))
1696                .collect(),
1697            disambiguator: self.disambiguator,
1698            trait_map: self.trait_map,
1699            lifetime_elision_allowed: self.lifetime_elision_allowed,
1700            lint_buffer: Steal::new(self.lint_buffer),
1701            delegation_fn_sigs: self.delegation_fn_sigs,
1702        };
1703        ResolverOutputs { global_ctxt, ast_lowering }
1704    }
1705
1706    fn create_stable_hashing_context(&self) -> StableHashingContext<'_> {
1707        StableHashingContext::new(self.tcx.sess, self.tcx.untracked())
1708    }
1709
1710    fn crate_loader<T>(&mut self, f: impl FnOnce(&mut CrateLoader<'_, '_>) -> T) -> T {
1711        f(&mut CrateLoader::new(
1712            self.tcx,
1713            &mut CStore::from_tcx_mut(self.tcx),
1714            &mut self.used_extern_options,
1715        ))
1716    }
1717
1718    fn cstore(&self) -> FreezeReadGuard<'_, CStore> {
1719        CStore::from_tcx(self.tcx)
1720    }
1721
1722    fn dummy_ext(&self, macro_kind: MacroKind) -> Arc<SyntaxExtension> {
1723        match macro_kind {
1724            MacroKind::Bang => Arc::clone(&self.dummy_ext_bang),
1725            MacroKind::Derive => Arc::clone(&self.dummy_ext_derive),
1726            MacroKind::Attr => Arc::clone(&self.non_macro_attr.ext),
1727        }
1728    }
1729
1730    /// Runs the function on each namespace.
1731    fn per_ns<F: FnMut(&mut Self, Namespace)>(&mut self, mut f: F) {
1732        f(self, TypeNS);
1733        f(self, ValueNS);
1734        f(self, MacroNS);
1735    }
1736
1737    fn is_builtin_macro(&mut self, res: Res) -> bool {
1738        self.get_macro(res).is_some_and(|macro_data| macro_data.ext.builtin_name.is_some())
1739    }
1740
1741    fn macro_def(&self, mut ctxt: SyntaxContext) -> DefId {
1742        loop {
1743            match ctxt.outer_expn_data().macro_def_id {
1744                Some(def_id) => return def_id,
1745                None => ctxt.remove_mark(),
1746            };
1747        }
1748    }
1749
1750    /// Entry point to crate resolution.
1751    pub fn resolve_crate(&mut self, krate: &Crate) {
1752        self.tcx.sess.time("resolve_crate", || {
1753            self.tcx.sess.time("finalize_imports", || self.finalize_imports());
1754            let exported_ambiguities = self.tcx.sess.time("compute_effective_visibilities", || {
1755                EffectiveVisibilitiesVisitor::compute_effective_visibilities(self, krate)
1756            });
1757            self.tcx.sess.time("check_hidden_glob_reexports", || {
1758                self.check_hidden_glob_reexports(exported_ambiguities)
1759            });
1760            self.tcx
1761                .sess
1762                .time("finalize_macro_resolutions", || self.finalize_macro_resolutions(krate));
1763            self.tcx.sess.time("late_resolve_crate", || self.late_resolve_crate(krate));
1764            self.tcx.sess.time("resolve_main", || self.resolve_main());
1765            self.tcx.sess.time("resolve_check_unused", || self.check_unused(krate));
1766            self.tcx.sess.time("resolve_report_errors", || self.report_errors(krate));
1767            self.tcx
1768                .sess
1769                .time("resolve_postprocess", || self.crate_loader(|c| c.postprocess(krate)));
1770        });
1771
1772        // Make sure we don't mutate the cstore from here on.
1773        self.tcx.untracked().cstore.freeze();
1774    }
1775
1776    fn traits_in_scope(
1777        &mut self,
1778        current_trait: Option<Module<'ra>>,
1779        parent_scope: &ParentScope<'ra>,
1780        ctxt: SyntaxContext,
1781        assoc_item: Option<(Symbol, Namespace)>,
1782    ) -> Vec<TraitCandidate> {
1783        let mut found_traits = Vec::new();
1784
1785        if let Some(module) = current_trait {
1786            if self.trait_may_have_item(Some(module), assoc_item) {
1787                let def_id = module.def_id();
1788                found_traits.push(TraitCandidate { def_id, import_ids: smallvec![] });
1789            }
1790        }
1791
1792        self.visit_scopes(ScopeSet::All(TypeNS), parent_scope, ctxt, |this, scope, _, _| {
1793            match scope {
1794                Scope::Module(module, _) => {
1795                    this.traits_in_module(module, assoc_item, &mut found_traits);
1796                }
1797                Scope::StdLibPrelude => {
1798                    if let Some(module) = this.prelude {
1799                        this.traits_in_module(module, assoc_item, &mut found_traits);
1800                    }
1801                }
1802                Scope::ExternPrelude | Scope::ToolPrelude | Scope::BuiltinTypes => {}
1803                _ => unreachable!(),
1804            }
1805            None::<()>
1806        });
1807
1808        found_traits
1809    }
1810
1811    fn traits_in_module(
1812        &mut self,
1813        module: Module<'ra>,
1814        assoc_item: Option<(Symbol, Namespace)>,
1815        found_traits: &mut Vec<TraitCandidate>,
1816    ) {
1817        module.ensure_traits(self);
1818        let traits = module.traits.borrow();
1819        for (trait_name, trait_binding) in traits.as_ref().unwrap().iter() {
1820            if self.trait_may_have_item(trait_binding.module(), assoc_item) {
1821                let def_id = trait_binding.res().def_id();
1822                let import_ids = self.find_transitive_imports(&trait_binding.kind, *trait_name);
1823                found_traits.push(TraitCandidate { def_id, import_ids });
1824            }
1825        }
1826    }
1827
1828    // List of traits in scope is pruned on best effort basis. We reject traits not having an
1829    // associated item with the given name and namespace (if specified). This is a conservative
1830    // optimization, proper hygienic type-based resolution of associated items is done in typeck.
1831    // We don't reject trait aliases (`trait_module == None`) because we don't have access to their
1832    // associated items.
1833    fn trait_may_have_item(
1834        &mut self,
1835        trait_module: Option<Module<'ra>>,
1836        assoc_item: Option<(Symbol, Namespace)>,
1837    ) -> bool {
1838        match (trait_module, assoc_item) {
1839            (Some(trait_module), Some((name, ns))) => self
1840                .resolutions(trait_module)
1841                .borrow()
1842                .iter()
1843                .any(|(key, _name_resolution)| key.ns == ns && key.ident.name == name),
1844            _ => true,
1845        }
1846    }
1847
1848    fn find_transitive_imports(
1849        &mut self,
1850        mut kind: &NameBindingKind<'_>,
1851        trait_name: Ident,
1852    ) -> SmallVec<[LocalDefId; 1]> {
1853        let mut import_ids = smallvec![];
1854        while let NameBindingKind::Import { import, binding, .. } = kind {
1855            if let Some(node_id) = import.id() {
1856                let def_id = self.local_def_id(node_id);
1857                self.maybe_unused_trait_imports.insert(def_id);
1858                import_ids.push(def_id);
1859            }
1860            self.add_to_glob_map(*import, trait_name);
1861            kind = &binding.kind;
1862        }
1863        import_ids
1864    }
1865
1866    fn new_disambiguated_key(&mut self, ident: Ident, ns: Namespace) -> BindingKey {
1867        let ident = ident.normalize_to_macros_2_0();
1868        let disambiguator = if ident.name == kw::Underscore {
1869            self.underscore_disambiguator += 1;
1870            self.underscore_disambiguator
1871        } else {
1872            0
1873        };
1874        BindingKey { ident, ns, disambiguator }
1875    }
1876
1877    fn resolutions(&mut self, module: Module<'ra>) -> &'ra Resolutions<'ra> {
1878        if module.populate_on_access.get() {
1879            module.populate_on_access.set(false);
1880            self.build_reduced_graph_external(module);
1881        }
1882        &module.0.0.lazy_resolutions
1883    }
1884
1885    fn resolution(
1886        &mut self,
1887        module: Module<'ra>,
1888        key: BindingKey,
1889    ) -> &'ra RefCell<NameResolution<'ra>> {
1890        *self
1891            .resolutions(module)
1892            .borrow_mut()
1893            .entry(key)
1894            .or_insert_with(|| self.arenas.alloc_name_resolution())
1895    }
1896
1897    /// Test if AmbiguityError ambi is any identical to any one inside ambiguity_errors
1898    fn matches_previous_ambiguity_error(&self, ambi: &AmbiguityError<'_>) -> bool {
1899        for ambiguity_error in &self.ambiguity_errors {
1900            // if the span location and ident as well as its span are the same
1901            if ambiguity_error.kind == ambi.kind
1902                && ambiguity_error.ident == ambi.ident
1903                && ambiguity_error.ident.span == ambi.ident.span
1904                && ambiguity_error.b1.span == ambi.b1.span
1905                && ambiguity_error.b2.span == ambi.b2.span
1906                && ambiguity_error.misc1 == ambi.misc1
1907                && ambiguity_error.misc2 == ambi.misc2
1908            {
1909                return true;
1910            }
1911        }
1912        false
1913    }
1914
1915    fn record_use(&mut self, ident: Ident, used_binding: NameBinding<'ra>, used: Used) {
1916        self.record_use_inner(ident, used_binding, used, used_binding.warn_ambiguity);
1917    }
1918
1919    fn record_use_inner(
1920        &mut self,
1921        ident: Ident,
1922        used_binding: NameBinding<'ra>,
1923        used: Used,
1924        warn_ambiguity: bool,
1925    ) {
1926        if let Some((b2, kind)) = used_binding.ambiguity {
1927            let ambiguity_error = AmbiguityError {
1928                kind,
1929                ident,
1930                b1: used_binding,
1931                b2,
1932                misc1: AmbiguityErrorMisc::None,
1933                misc2: AmbiguityErrorMisc::None,
1934                warning: warn_ambiguity,
1935            };
1936            if !self.matches_previous_ambiguity_error(&ambiguity_error) {
1937                // avoid duplicated span information to be emit out
1938                self.ambiguity_errors.push(ambiguity_error);
1939            }
1940        }
1941        if let NameBindingKind::Import { import, binding } = used_binding.kind {
1942            if let ImportKind::MacroUse { warn_private: true } = import.kind {
1943                // Do not report the lint if the macro name resolves in stdlib prelude
1944                // even without the problematic `macro_use` import.
1945                let found_in_stdlib_prelude = self.prelude.is_some_and(|prelude| {
1946                    self.maybe_resolve_ident_in_module(
1947                        ModuleOrUniformRoot::Module(prelude),
1948                        ident,
1949                        MacroNS,
1950                        &ParentScope::module(self.empty_module, self),
1951                        None,
1952                    )
1953                    .is_ok()
1954                });
1955                if !found_in_stdlib_prelude {
1956                    self.lint_buffer().buffer_lint(
1957                        PRIVATE_MACRO_USE,
1958                        import.root_id,
1959                        ident.span,
1960                        BuiltinLintDiag::MacroIsPrivate(ident),
1961                    );
1962                }
1963            }
1964            // Avoid marking `extern crate` items that refer to a name from extern prelude,
1965            // but not introduce it, as used if they are accessed from lexical scope.
1966            if used == Used::Scope {
1967                if let Some(entry) = self.extern_prelude.get(&ident.normalize_to_macros_2_0()) {
1968                    if !entry.introduced_by_item && entry.binding == Some(used_binding) {
1969                        return;
1970                    }
1971                }
1972            }
1973            let old_used = self.import_use_map.entry(import).or_insert(used);
1974            if *old_used < used {
1975                *old_used = used;
1976            }
1977            if let Some(id) = import.id() {
1978                self.used_imports.insert(id);
1979            }
1980            self.add_to_glob_map(import, ident);
1981            self.record_use_inner(
1982                ident,
1983                binding,
1984                Used::Other,
1985                warn_ambiguity || binding.warn_ambiguity,
1986            );
1987        }
1988    }
1989
1990    #[inline]
1991    fn add_to_glob_map(&mut self, import: Import<'_>, ident: Ident) {
1992        if let ImportKind::Glob { id, .. } = import.kind {
1993            let def_id = self.local_def_id(id);
1994            self.glob_map.entry(def_id).or_default().insert(ident.name);
1995        }
1996    }
1997
1998    fn resolve_crate_root(&mut self, ident: Ident) -> Module<'ra> {
1999        debug!("resolve_crate_root({:?})", ident);
2000        let mut ctxt = ident.span.ctxt();
2001        let mark = if ident.name == kw::DollarCrate {
2002            // When resolving `$crate` from a `macro_rules!` invoked in a `macro`,
2003            // we don't want to pretend that the `macro_rules!` definition is in the `macro`
2004            // as described in `SyntaxContext::apply_mark`, so we ignore prepended opaque marks.
2005            // FIXME: This is only a guess and it doesn't work correctly for `macro_rules!`
2006            // definitions actually produced by `macro` and `macro` definitions produced by
2007            // `macro_rules!`, but at least such configurations are not stable yet.
2008            ctxt = ctxt.normalize_to_macro_rules();
2009            debug!(
2010                "resolve_crate_root: marks={:?}",
2011                ctxt.marks().into_iter().map(|(i, t)| (i.expn_data(), t)).collect::<Vec<_>>()
2012            );
2013            let mut iter = ctxt.marks().into_iter().rev().peekable();
2014            let mut result = None;
2015            // Find the last opaque mark from the end if it exists.
2016            while let Some(&(mark, transparency)) = iter.peek() {
2017                if transparency == Transparency::Opaque {
2018                    result = Some(mark);
2019                    iter.next();
2020                } else {
2021                    break;
2022                }
2023            }
2024            debug!(
2025                "resolve_crate_root: found opaque mark {:?} {:?}",
2026                result,
2027                result.map(|r| r.expn_data())
2028            );
2029            // Then find the last semi-opaque mark from the end if it exists.
2030            for (mark, transparency) in iter {
2031                if transparency == Transparency::SemiOpaque {
2032                    result = Some(mark);
2033                } else {
2034                    break;
2035                }
2036            }
2037            debug!(
2038                "resolve_crate_root: found semi-opaque mark {:?} {:?}",
2039                result,
2040                result.map(|r| r.expn_data())
2041            );
2042            result
2043        } else {
2044            debug!("resolve_crate_root: not DollarCrate");
2045            ctxt = ctxt.normalize_to_macros_2_0();
2046            ctxt.adjust(ExpnId::root())
2047        };
2048        let module = match mark {
2049            Some(def) => self.expn_def_scope(def),
2050            None => {
2051                debug!(
2052                    "resolve_crate_root({:?}): found no mark (ident.span = {:?})",
2053                    ident, ident.span
2054                );
2055                return self.graph_root;
2056            }
2057        };
2058        let module = self.expect_module(
2059            module.opt_def_id().map_or(LOCAL_CRATE, |def_id| def_id.krate).as_def_id(),
2060        );
2061        debug!(
2062            "resolve_crate_root({:?}): got module {:?} ({:?}) (ident.span = {:?})",
2063            ident,
2064            module,
2065            module.kind.name(),
2066            ident.span
2067        );
2068        module
2069    }
2070
2071    fn resolve_self(&mut self, ctxt: &mut SyntaxContext, module: Module<'ra>) -> Module<'ra> {
2072        let mut module = self.expect_module(module.nearest_parent_mod());
2073        while module.span.ctxt().normalize_to_macros_2_0() != *ctxt {
2074            let parent = module.parent.unwrap_or_else(|| self.expn_def_scope(ctxt.remove_mark()));
2075            module = self.expect_module(parent.nearest_parent_mod());
2076        }
2077        module
2078    }
2079
2080    fn record_partial_res(&mut self, node_id: NodeId, resolution: PartialRes) {
2081        debug!("(recording res) recording {:?} for {}", resolution, node_id);
2082        if let Some(prev_res) = self.partial_res_map.insert(node_id, resolution) {
2083            panic!("path resolved multiple times ({prev_res:?} before, {resolution:?} now)");
2084        }
2085    }
2086
2087    fn record_pat_span(&mut self, node: NodeId, span: Span) {
2088        debug!("(recording pat) recording {:?} for {:?}", node, span);
2089        self.pat_span_map.insert(node, span);
2090    }
2091
2092    fn is_accessible_from(
2093        &self,
2094        vis: ty::Visibility<impl Into<DefId>>,
2095        module: Module<'ra>,
2096    ) -> bool {
2097        vis.is_accessible_from(module.nearest_parent_mod(), self.tcx)
2098    }
2099
2100    fn set_binding_parent_module(&mut self, binding: NameBinding<'ra>, module: Module<'ra>) {
2101        if let Some(old_module) = self.binding_parent_modules.insert(binding, module) {
2102            if module != old_module {
2103                span_bug!(binding.span, "parent module is reset for binding");
2104            }
2105        }
2106    }
2107
2108    fn disambiguate_macro_rules_vs_modularized(
2109        &self,
2110        macro_rules: NameBinding<'ra>,
2111        modularized: NameBinding<'ra>,
2112    ) -> bool {
2113        // Some non-controversial subset of ambiguities "modularized macro name" vs "macro_rules"
2114        // is disambiguated to mitigate regressions from macro modularization.
2115        // Scoping for `macro_rules` behaves like scoping for `let` at module level, in general.
2116        match (
2117            self.binding_parent_modules.get(&macro_rules),
2118            self.binding_parent_modules.get(&modularized),
2119        ) {
2120            (Some(macro_rules), Some(modularized)) => {
2121                macro_rules.nearest_parent_mod() == modularized.nearest_parent_mod()
2122                    && modularized.is_ancestor_of(*macro_rules)
2123            }
2124            _ => false,
2125        }
2126    }
2127
2128    fn extern_prelude_get(&mut self, ident: Ident, finalize: bool) -> Option<NameBinding<'ra>> {
2129        if ident.is_path_segment_keyword() {
2130            // Make sure `self`, `super` etc produce an error when passed to here.
2131            return None;
2132        }
2133
2134        let norm_ident = ident.normalize_to_macros_2_0();
2135        let binding = self.extern_prelude.get(&norm_ident).cloned().and_then(|entry| {
2136            Some(if let Some(binding) = entry.binding {
2137                if finalize {
2138                    if !entry.is_import() {
2139                        self.crate_loader(|c| c.process_path_extern(ident.name, ident.span));
2140                    } else if entry.introduced_by_item {
2141                        self.record_use(ident, binding, Used::Other);
2142                    }
2143                }
2144                binding
2145            } else {
2146                let crate_id = if finalize {
2147                    let Some(crate_id) =
2148                        self.crate_loader(|c| c.process_path_extern(ident.name, ident.span))
2149                    else {
2150                        return Some(self.dummy_binding);
2151                    };
2152                    crate_id
2153                } else {
2154                    self.crate_loader(|c| c.maybe_process_path_extern(ident.name))?
2155                };
2156                let crate_root = self.expect_module(crate_id.as_def_id());
2157                let vis = ty::Visibility::<DefId>::Public;
2158                (crate_root, vis, DUMMY_SP, LocalExpnId::ROOT).to_name_binding(self.arenas)
2159            })
2160        });
2161
2162        if let Some(entry) = self.extern_prelude.get_mut(&norm_ident) {
2163            entry.binding = binding;
2164        }
2165
2166        binding
2167    }
2168
2169    /// Rustdoc uses this to resolve doc link paths in a recoverable way. `PathResult<'a>`
2170    /// isn't something that can be returned because it can't be made to live that long,
2171    /// and also it's a private type. Fortunately rustdoc doesn't need to know the error,
2172    /// just that an error occurred.
2173    fn resolve_rustdoc_path(
2174        &mut self,
2175        path_str: &str,
2176        ns: Namespace,
2177        parent_scope: ParentScope<'ra>,
2178    ) -> Option<Res> {
2179        let segments: Result<Vec<_>, ()> = path_str
2180            .split("::")
2181            .enumerate()
2182            .map(|(i, s)| {
2183                let sym = if s.is_empty() {
2184                    if i == 0 {
2185                        // For a path like `::a::b`, use `kw::PathRoot` as the leading segment.
2186                        kw::PathRoot
2187                    } else {
2188                        return Err(()); // occurs in cases like `String::`
2189                    }
2190                } else {
2191                    Symbol::intern(s)
2192                };
2193                Ok(Segment::from_ident(Ident::with_dummy_span(sym)))
2194            })
2195            .collect();
2196        let Ok(segments) = segments else { return None };
2197
2198        match self.maybe_resolve_path(&segments, Some(ns), &parent_scope, None) {
2199            PathResult::Module(ModuleOrUniformRoot::Module(module)) => Some(module.res().unwrap()),
2200            PathResult::NonModule(path_res) => {
2201                path_res.full_res().filter(|res| !matches!(res, Res::Def(DefKind::Ctor(..), _)))
2202            }
2203            PathResult::Module(ModuleOrUniformRoot::ExternPrelude) | PathResult::Failed { .. } => {
2204                None
2205            }
2206            PathResult::Module(..) | PathResult::Indeterminate => unreachable!(),
2207        }
2208    }
2209
2210    /// Retrieves definition span of the given `DefId`.
2211    fn def_span(&self, def_id: DefId) -> Span {
2212        match def_id.as_local() {
2213            Some(def_id) => self.tcx.source_span(def_id),
2214            // Query `def_span` is not used because hashing its result span is expensive.
2215            None => self.cstore().def_span_untracked(def_id, self.tcx.sess),
2216        }
2217    }
2218
2219    fn field_idents(&self, def_id: DefId) -> Option<Vec<Ident>> {
2220        match def_id.as_local() {
2221            Some(def_id) => self.field_names.get(&def_id).cloned(),
2222            None => Some(
2223                self.tcx
2224                    .associated_item_def_ids(def_id)
2225                    .iter()
2226                    .map(|&def_id| {
2227                        Ident::new(self.tcx.item_name(def_id), self.tcx.def_span(def_id))
2228                    })
2229                    .collect(),
2230            ),
2231        }
2232    }
2233
2234    /// Checks if an expression refers to a function marked with
2235    /// `#[rustc_legacy_const_generics]` and returns the argument index list
2236    /// from the attribute.
2237    fn legacy_const_generic_args(&mut self, expr: &Expr) -> Option<Vec<usize>> {
2238        if let ExprKind::Path(None, path) = &expr.kind {
2239            // Don't perform legacy const generics rewriting if the path already
2240            // has generic arguments.
2241            if path.segments.last().unwrap().args.is_some() {
2242                return None;
2243            }
2244
2245            let res = self.partial_res_map.get(&expr.id)?.full_res()?;
2246            if let Res::Def(def::DefKind::Fn, def_id) = res {
2247                // We only support cross-crate argument rewriting. Uses
2248                // within the same crate should be updated to use the new
2249                // const generics style.
2250                if def_id.is_local() {
2251                    return None;
2252                }
2253
2254                if let Some(v) = self.legacy_const_generic_args.get(&def_id) {
2255                    return v.clone();
2256                }
2257
2258                let attr = self.tcx.get_attr(def_id, sym::rustc_legacy_const_generics)?;
2259                let mut ret = Vec::new();
2260                for meta in attr.meta_item_list()? {
2261                    match meta.lit()?.kind {
2262                        LitKind::Int(a, _) => ret.push(a.get() as usize),
2263                        _ => panic!("invalid arg index"),
2264                    }
2265                }
2266                // Cache the lookup to avoid parsing attributes for an item multiple times.
2267                self.legacy_const_generic_args.insert(def_id, Some(ret.clone()));
2268                return Some(ret);
2269            }
2270        }
2271        None
2272    }
2273
2274    fn resolve_main(&mut self) {
2275        let module = self.graph_root;
2276        let ident = Ident::with_dummy_span(sym::main);
2277        let parent_scope = &ParentScope::module(module, self);
2278
2279        let Ok(name_binding) = self.maybe_resolve_ident_in_module(
2280            ModuleOrUniformRoot::Module(module),
2281            ident,
2282            ValueNS,
2283            parent_scope,
2284            None,
2285        ) else {
2286            return;
2287        };
2288
2289        let res = name_binding.res();
2290        let is_import = name_binding.is_import();
2291        let span = name_binding.span;
2292        if let Res::Def(DefKind::Fn, _) = res {
2293            self.record_use(ident, name_binding, Used::Other);
2294        }
2295        self.main_def = Some(MainDefinition { res, is_import, span });
2296    }
2297}
2298
2299fn names_to_string(names: impl Iterator<Item = Symbol>) -> String {
2300    let mut result = String::new();
2301    for (i, name) in names.filter(|name| *name != kw::PathRoot).enumerate() {
2302        if i > 0 {
2303            result.push_str("::");
2304        }
2305        if Ident::with_dummy_span(name).is_raw_guess() {
2306            result.push_str("r#");
2307        }
2308        result.push_str(name.as_str());
2309    }
2310    result
2311}
2312
2313fn path_names_to_string(path: &Path) -> String {
2314    names_to_string(path.segments.iter().map(|seg| seg.ident.name))
2315}
2316
2317/// A somewhat inefficient routine to obtain the name of a module.
2318fn module_to_string(mut module: Module<'_>) -> Option<String> {
2319    let mut names = Vec::new();
2320    loop {
2321        if let ModuleKind::Def(.., name) = module.kind {
2322            if let Some(parent) = module.parent {
2323                // `unwrap` is safe: the presence of a parent means it's not the crate root.
2324                names.push(name.unwrap());
2325                module = parent
2326            } else {
2327                break;
2328            }
2329        } else {
2330            names.push(sym::opaque_module_name_placeholder);
2331            let Some(parent) = module.parent else {
2332                return None;
2333            };
2334            module = parent;
2335        }
2336    }
2337    if names.is_empty() {
2338        return None;
2339    }
2340    Some(names_to_string(names.iter().rev().copied()))
2341}
2342
2343#[derive(Copy, Clone, Debug)]
2344struct Finalize {
2345    /// Node ID for linting.
2346    node_id: NodeId,
2347    /// Span of the whole path or some its characteristic fragment.
2348    /// E.g. span of `b` in `foo::{a, b, c}`, or full span for regular paths.
2349    path_span: Span,
2350    /// Span of the path start, suitable for prepending something to it.
2351    /// E.g. span of `foo` in `foo::{a, b, c}`, or full span for regular paths.
2352    root_span: Span,
2353    /// Whether to report privacy errors or silently return "no resolution" for them,
2354    /// similarly to speculative resolution.
2355    report_private: bool,
2356    /// Tracks whether an item is used in scope or used relatively to a module.
2357    used: Used,
2358}
2359
2360impl Finalize {
2361    fn new(node_id: NodeId, path_span: Span) -> Finalize {
2362        Finalize::with_root_span(node_id, path_span, path_span)
2363    }
2364
2365    fn with_root_span(node_id: NodeId, path_span: Span, root_span: Span) -> Finalize {
2366        Finalize { node_id, path_span, root_span, report_private: true, used: Used::Other }
2367    }
2368}
2369
2370pub fn provide(providers: &mut Providers) {
2371    providers.registered_tools = macros::registered_tools;
2372}