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().best_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 import_source(&self) -> NameBinding<'ra> {
895        match self.kind {
896            NameBindingKind::Import { binding, .. } => binding,
897            _ => unreachable!(),
898        }
899    }
900
901    fn is_ambiguity_recursive(&self) -> bool {
902        self.ambiguity.is_some()
903            || match self.kind {
904                NameBindingKind::Import { binding, .. } => binding.is_ambiguity_recursive(),
905                _ => false,
906            }
907    }
908
909    fn warn_ambiguity_recursive(&self) -> bool {
910        self.warn_ambiguity
911            || match self.kind {
912                NameBindingKind::Import { binding, .. } => binding.warn_ambiguity_recursive(),
913                _ => false,
914            }
915    }
916
917    fn is_possibly_imported_variant(&self) -> bool {
918        match self.kind {
919            NameBindingKind::Import { binding, .. } => binding.is_possibly_imported_variant(),
920            NameBindingKind::Res(Res::Def(
921                DefKind::Variant | DefKind::Ctor(CtorOf::Variant, ..),
922                _,
923            )) => true,
924            NameBindingKind::Res(..) | NameBindingKind::Module(..) => false,
925        }
926    }
927
928    fn is_extern_crate(&self) -> bool {
929        match self.kind {
930            NameBindingKind::Import { import, .. } => {
931                matches!(import.kind, ImportKind::ExternCrate { .. })
932            }
933            NameBindingKind::Module(module)
934                if let ModuleKind::Def(DefKind::Mod, def_id, _) = module.kind =>
935            {
936                def_id.is_crate_root()
937            }
938            _ => false,
939        }
940    }
941
942    fn is_import(&self) -> bool {
943        matches!(self.kind, NameBindingKind::Import { .. })
944    }
945
946    /// The binding introduced by `#[macro_export] macro_rules` is a public import, but it might
947    /// not be perceived as such by users, so treat it as a non-import in some diagnostics.
948    fn is_import_user_facing(&self) -> bool {
949        matches!(self.kind, NameBindingKind::Import { import, .. }
950            if !matches!(import.kind, ImportKind::MacroExport))
951    }
952
953    fn is_glob_import(&self) -> bool {
954        match self.kind {
955            NameBindingKind::Import { import, .. } => import.is_glob(),
956            _ => false,
957        }
958    }
959
960    fn is_assoc_item(&self) -> bool {
961        matches!(self.res(), Res::Def(DefKind::AssocConst | DefKind::AssocFn | DefKind::AssocTy, _))
962    }
963
964    fn macro_kind(&self) -> Option<MacroKind> {
965        self.res().macro_kind()
966    }
967
968    // Suppose that we resolved macro invocation with `invoc_parent_expansion` to binding `binding`
969    // at some expansion round `max(invoc, binding)` when they both emerged from macros.
970    // Then this function returns `true` if `self` may emerge from a macro *after* that
971    // in some later round and screw up our previously found resolution.
972    // See more detailed explanation in
973    // https://github.com/rust-lang/rust/pull/53778#issuecomment-419224049
974    fn may_appear_after(
975        &self,
976        invoc_parent_expansion: LocalExpnId,
977        binding: NameBinding<'_>,
978    ) -> bool {
979        // self > max(invoc, binding) => !(self <= invoc || self <= binding)
980        // Expansions are partially ordered, so "may appear after" is an inversion of
981        // "certainly appears before or simultaneously" and includes unordered cases.
982        let self_parent_expansion = self.expansion;
983        let other_parent_expansion = binding.expansion;
984        let certainly_before_other_or_simultaneously =
985            other_parent_expansion.is_descendant_of(self_parent_expansion);
986        let certainly_before_invoc_or_simultaneously =
987            invoc_parent_expansion.is_descendant_of(self_parent_expansion);
988        !(certainly_before_other_or_simultaneously || certainly_before_invoc_or_simultaneously)
989    }
990
991    // Its purpose is to postpone the determination of a single binding because
992    // we can't predict whether it will be overwritten by recently expanded macros.
993    // FIXME: How can we integrate it with the `update_resolution`?
994    fn determined(&self) -> bool {
995        match &self.kind {
996            NameBindingKind::Import { binding, import, .. } if import.is_glob() => {
997                import.parent_scope.module.unexpanded_invocations.borrow().is_empty()
998                    && binding.determined()
999            }
1000            _ => true,
1001        }
1002    }
1003}
1004
1005#[derive(Default, Clone)]
1006struct ExternPreludeEntry<'ra> {
1007    binding: Option<NameBinding<'ra>>,
1008    introduced_by_item: bool,
1009}
1010
1011impl ExternPreludeEntry<'_> {
1012    fn is_import(&self) -> bool {
1013        self.binding.is_some_and(|binding| binding.is_import())
1014    }
1015}
1016
1017struct DeriveData {
1018    resolutions: Vec<DeriveResolution>,
1019    helper_attrs: Vec<(usize, Ident)>,
1020    has_derive_copy: bool,
1021}
1022
1023struct MacroData {
1024    ext: Arc<SyntaxExtension>,
1025    nrules: usize,
1026    macro_rules: bool,
1027}
1028
1029impl MacroData {
1030    fn new(ext: Arc<SyntaxExtension>) -> MacroData {
1031        MacroData { ext, nrules: 0, macro_rules: false }
1032    }
1033}
1034
1035/// The main resolver class.
1036///
1037/// This is the visitor that walks the whole crate.
1038pub struct Resolver<'ra, 'tcx> {
1039    tcx: TyCtxt<'tcx>,
1040
1041    /// Item with a given `LocalDefId` was defined during macro expansion with ID `ExpnId`.
1042    expn_that_defined: UnordMap<LocalDefId, ExpnId>,
1043
1044    graph_root: Module<'ra>,
1045
1046    prelude: Option<Module<'ra>>,
1047    extern_prelude: FxIndexMap<Ident, ExternPreludeEntry<'ra>>,
1048
1049    /// N.B., this is used only for better diagnostics, not name resolution itself.
1050    field_names: LocalDefIdMap<Vec<Ident>>,
1051
1052    /// Span of the privacy modifier in fields of an item `DefId` accessible with dot syntax.
1053    /// Used for hints during error reporting.
1054    field_visibility_spans: FxHashMap<DefId, Vec<Span>>,
1055
1056    /// All imports known to succeed or fail.
1057    determined_imports: Vec<Import<'ra>>,
1058
1059    /// All non-determined imports.
1060    indeterminate_imports: Vec<Import<'ra>>,
1061
1062    // Spans for local variables found during pattern resolution.
1063    // Used for suggestions during error reporting.
1064    pat_span_map: NodeMap<Span>,
1065
1066    /// Resolutions for nodes that have a single resolution.
1067    partial_res_map: NodeMap<PartialRes>,
1068    /// Resolutions for import nodes, which have multiple resolutions in different namespaces.
1069    import_res_map: NodeMap<PerNS<Option<Res>>>,
1070    /// An import will be inserted into this map if it has been used.
1071    import_use_map: FxHashMap<Import<'ra>, Used>,
1072    /// Resolutions for labels (node IDs of their corresponding blocks or loops).
1073    label_res_map: NodeMap<NodeId>,
1074    /// Resolutions for lifetimes.
1075    lifetimes_res_map: NodeMap<LifetimeRes>,
1076    /// Lifetime parameters that lowering will have to introduce.
1077    extra_lifetime_params_map: NodeMap<Vec<(Ident, NodeId, LifetimeRes)>>,
1078
1079    /// `CrateNum` resolutions of `extern crate` items.
1080    extern_crate_map: UnordMap<LocalDefId, CrateNum>,
1081    module_children: LocalDefIdMap<Vec<ModChild>>,
1082    trait_map: NodeMap<Vec<TraitCandidate>>,
1083
1084    /// A map from nodes to anonymous modules.
1085    /// Anonymous modules are pseudo-modules that are implicitly created around items
1086    /// contained within blocks.
1087    ///
1088    /// For example, if we have this:
1089    ///
1090    ///  fn f() {
1091    ///      fn g() {
1092    ///          ...
1093    ///      }
1094    ///  }
1095    ///
1096    /// There will be an anonymous module created around `g` with the ID of the
1097    /// entry block for `f`.
1098    block_map: NodeMap<Module<'ra>>,
1099    /// A fake module that contains no definition and no prelude. Used so that
1100    /// some AST passes can generate identifiers that only resolve to local or
1101    /// lang items.
1102    empty_module: Module<'ra>,
1103    module_map: FxIndexMap<DefId, Module<'ra>>,
1104    binding_parent_modules: FxHashMap<NameBinding<'ra>, Module<'ra>>,
1105
1106    underscore_disambiguator: u32,
1107
1108    /// Maps glob imports to the names of items actually imported.
1109    glob_map: FxIndexMap<LocalDefId, FxIndexSet<Symbol>>,
1110    glob_error: Option<ErrorGuaranteed>,
1111    visibilities_for_hashing: Vec<(LocalDefId, ty::Visibility)>,
1112    used_imports: FxHashSet<NodeId>,
1113    maybe_unused_trait_imports: FxIndexSet<LocalDefId>,
1114
1115    /// Privacy errors are delayed until the end in order to deduplicate them.
1116    privacy_errors: Vec<PrivacyError<'ra>>,
1117    /// Ambiguity errors are delayed for deduplication.
1118    ambiguity_errors: Vec<AmbiguityError<'ra>>,
1119    /// `use` injections are delayed for better placement and deduplication.
1120    use_injections: Vec<UseError<'tcx>>,
1121    /// Crate-local macro expanded `macro_export` referred to by a module-relative path.
1122    macro_expanded_macro_export_errors: BTreeSet<(Span, Span)>,
1123
1124    arenas: &'ra ResolverArenas<'ra>,
1125    dummy_binding: NameBinding<'ra>,
1126    builtin_types_bindings: FxHashMap<Symbol, NameBinding<'ra>>,
1127    builtin_attrs_bindings: FxHashMap<Symbol, NameBinding<'ra>>,
1128    registered_tool_bindings: FxHashMap<Ident, NameBinding<'ra>>,
1129    /// Binding for implicitly declared names that come with a module,
1130    /// like `self` (not yet used), or `crate`/`$crate` (for root modules).
1131    module_self_bindings: FxHashMap<Module<'ra>, NameBinding<'ra>>,
1132
1133    used_extern_options: FxHashSet<Symbol>,
1134    macro_names: FxHashSet<Ident>,
1135    builtin_macros: FxHashMap<Symbol, SyntaxExtensionKind>,
1136    registered_tools: &'tcx RegisteredTools,
1137    macro_use_prelude: FxIndexMap<Symbol, NameBinding<'ra>>,
1138    local_macro_map: FxHashMap<LocalDefId, &'ra MacroData>,
1139    /// Lazily populated cache of macros loaded from external crates.
1140    extern_macro_map: RefCell<FxHashMap<DefId, &'ra MacroData>>,
1141    dummy_ext_bang: Arc<SyntaxExtension>,
1142    dummy_ext_derive: Arc<SyntaxExtension>,
1143    non_macro_attr: &'ra MacroData,
1144    local_macro_def_scopes: FxHashMap<LocalDefId, Module<'ra>>,
1145    ast_transform_scopes: FxHashMap<LocalExpnId, Module<'ra>>,
1146    unused_macros: FxIndexMap<LocalDefId, (NodeId, Ident)>,
1147    /// A map from the macro to all its potentially unused arms.
1148    unused_macro_rules: FxIndexMap<NodeId, DenseBitSet<usize>>,
1149    proc_macro_stubs: FxHashSet<LocalDefId>,
1150    /// Traces collected during macro resolution and validated when it's complete.
1151    single_segment_macro_resolutions:
1152        Vec<(Ident, MacroKind, ParentScope<'ra>, Option<NameBinding<'ra>>, Option<Span>)>,
1153    multi_segment_macro_resolutions:
1154        Vec<(Vec<Segment>, Span, MacroKind, ParentScope<'ra>, Option<Res>, Namespace)>,
1155    builtin_attrs: Vec<(Ident, ParentScope<'ra>)>,
1156    /// `derive(Copy)` marks items they are applied to so they are treated specially later.
1157    /// Derive macros cannot modify the item themselves and have to store the markers in the global
1158    /// context, so they attach the markers to derive container IDs using this resolver table.
1159    containers_deriving_copy: FxHashSet<LocalExpnId>,
1160    /// Parent scopes in which the macros were invoked.
1161    /// FIXME: `derives` are missing in these parent scopes and need to be taken from elsewhere.
1162    invocation_parent_scopes: FxHashMap<LocalExpnId, ParentScope<'ra>>,
1163    /// `macro_rules` scopes *produced* by expanding the macro invocations,
1164    /// include all the `macro_rules` items and other invocations generated by them.
1165    output_macro_rules_scopes: FxHashMap<LocalExpnId, MacroRulesScopeRef<'ra>>,
1166    /// `macro_rules` scopes produced by `macro_rules` item definitions.
1167    macro_rules_scopes: FxHashMap<LocalDefId, MacroRulesScopeRef<'ra>>,
1168    /// Helper attributes that are in scope for the given expansion.
1169    helper_attrs: FxHashMap<LocalExpnId, Vec<(Ident, NameBinding<'ra>)>>,
1170    /// Ready or in-progress results of resolving paths inside the `#[derive(...)]` attribute
1171    /// with the given `ExpnId`.
1172    derive_data: FxHashMap<LocalExpnId, DeriveData>,
1173
1174    /// Avoid duplicated errors for "name already defined".
1175    name_already_seen: FxHashMap<Symbol, Span>,
1176
1177    potentially_unused_imports: Vec<Import<'ra>>,
1178
1179    potentially_unnecessary_qualifications: Vec<UnnecessaryQualification<'ra>>,
1180
1181    /// Table for mapping struct IDs into struct constructor IDs,
1182    /// it's not used during normal resolution, only for better error reporting.
1183    /// Also includes of list of each fields visibility
1184    struct_constructors: LocalDefIdMap<(Res, ty::Visibility<DefId>, Vec<ty::Visibility<DefId>>)>,
1185
1186    lint_buffer: LintBuffer,
1187
1188    next_node_id: NodeId,
1189
1190    node_id_to_def_id: NodeMap<Feed<'tcx, LocalDefId>>,
1191
1192    disambiguator: DisambiguatorState,
1193
1194    /// Indices of unnamed struct or variant fields with unresolved attributes.
1195    placeholder_field_indices: FxHashMap<NodeId, usize>,
1196    /// When collecting definitions from an AST fragment produced by a macro invocation `ExpnId`
1197    /// we know what parent node that fragment should be attached to thanks to this table,
1198    /// and how the `impl Trait` fragments were introduced.
1199    invocation_parents: FxHashMap<LocalExpnId, InvocationParent>,
1200
1201    legacy_const_generic_args: FxHashMap<DefId, Option<Vec<usize>>>,
1202    /// Amount of lifetime parameters for each item in the crate.
1203    item_generics_num_lifetimes: FxHashMap<LocalDefId, usize>,
1204    delegation_fn_sigs: LocalDefIdMap<DelegationFnSig>,
1205
1206    main_def: Option<MainDefinition>,
1207    trait_impls: FxIndexMap<DefId, Vec<LocalDefId>>,
1208    /// A list of proc macro LocalDefIds, written out in the order in which
1209    /// they are declared in the static array generated by proc_macro_harness.
1210    proc_macros: Vec<LocalDefId>,
1211    confused_type_with_std_module: FxIndexMap<Span, Span>,
1212    /// Whether lifetime elision was successful.
1213    lifetime_elision_allowed: FxHashSet<NodeId>,
1214
1215    /// Names of items that were stripped out via cfg with their corresponding cfg meta item.
1216    stripped_cfg_items: Vec<StrippedCfgItem<NodeId>>,
1217
1218    effective_visibilities: EffectiveVisibilities,
1219    doc_link_resolutions: FxIndexMap<LocalDefId, DocLinkResMap>,
1220    doc_link_traits_in_scope: FxIndexMap<LocalDefId, Vec<DefId>>,
1221    all_macro_rules: UnordSet<Symbol>,
1222
1223    /// Invocation ids of all glob delegations.
1224    glob_delegation_invoc_ids: FxHashSet<LocalExpnId>,
1225    /// Analogue of module `unexpanded_invocations` but in trait impls, excluding glob delegations.
1226    /// Needed because glob delegations wait for all other neighboring macros to expand.
1227    impl_unexpanded_invocations: FxHashMap<LocalDefId, FxHashSet<LocalExpnId>>,
1228    /// Simplified analogue of module `resolutions` but in trait impls, excluding glob delegations.
1229    /// Needed because glob delegations exclude explicitly defined names.
1230    impl_binding_keys: FxHashMap<LocalDefId, FxHashSet<BindingKey>>,
1231
1232    /// This is the `Span` where an `extern crate foo;` suggestion would be inserted, if `foo`
1233    /// could be a crate that wasn't imported. For diagnostics use only.
1234    current_crate_outer_attr_insert_span: Span,
1235
1236    mods_with_parse_errors: FxHashSet<DefId>,
1237
1238    // Stores pre-expansion and pre-placeholder-fragment-insertion names for `impl Trait` types
1239    // that were encountered during resolution. These names are used to generate item names
1240    // for APITs, so we don't want to leak details of resolution into these names.
1241    impl_trait_names: FxHashMap<NodeId, Symbol>,
1242}
1243
1244/// This provides memory for the rest of the crate. The `'ra` lifetime that is
1245/// used by many types in this crate is an abbreviation of `ResolverArenas`.
1246#[derive(Default)]
1247pub struct ResolverArenas<'ra> {
1248    modules: TypedArena<ModuleData<'ra>>,
1249    local_modules: RefCell<Vec<Module<'ra>>>,
1250    imports: TypedArena<ImportData<'ra>>,
1251    name_resolutions: TypedArena<RefCell<NameResolution<'ra>>>,
1252    ast_paths: TypedArena<ast::Path>,
1253    macros: TypedArena<MacroData>,
1254    dropless: DroplessArena,
1255}
1256
1257impl<'ra> ResolverArenas<'ra> {
1258    fn new_module(
1259        &'ra self,
1260        parent: Option<Module<'ra>>,
1261        kind: ModuleKind,
1262        expn_id: ExpnId,
1263        span: Span,
1264        no_implicit_prelude: bool,
1265        module_map: &mut FxIndexMap<DefId, Module<'ra>>,
1266        module_self_bindings: &mut FxHashMap<Module<'ra>, NameBinding<'ra>>,
1267    ) -> Module<'ra> {
1268        let module = Module(Interned::new_unchecked(self.modules.alloc(ModuleData::new(
1269            parent,
1270            kind,
1271            expn_id,
1272            span,
1273            no_implicit_prelude,
1274        ))));
1275        let def_id = module.opt_def_id();
1276        if def_id.is_none_or(|def_id| def_id.is_local()) {
1277            self.local_modules.borrow_mut().push(module);
1278        }
1279        if let Some(def_id) = def_id {
1280            module_map.insert(def_id, module);
1281            let vis = ty::Visibility::<DefId>::Public;
1282            let binding = (module, vis, module.span, LocalExpnId::ROOT).to_name_binding(self);
1283            module_self_bindings.insert(module, binding);
1284        }
1285        module
1286    }
1287    fn local_modules(&'ra self) -> std::cell::Ref<'ra, Vec<Module<'ra>>> {
1288        self.local_modules.borrow()
1289    }
1290    fn alloc_name_binding(&'ra self, name_binding: NameBindingData<'ra>) -> NameBinding<'ra> {
1291        Interned::new_unchecked(self.dropless.alloc(name_binding))
1292    }
1293    fn alloc_import(&'ra self, import: ImportData<'ra>) -> Import<'ra> {
1294        Interned::new_unchecked(self.imports.alloc(import))
1295    }
1296    fn alloc_name_resolution(&'ra self) -> &'ra RefCell<NameResolution<'ra>> {
1297        self.name_resolutions.alloc(Default::default())
1298    }
1299    fn alloc_macro_rules_scope(&'ra self, scope: MacroRulesScope<'ra>) -> MacroRulesScopeRef<'ra> {
1300        self.dropless.alloc(Cell::new(scope))
1301    }
1302    fn alloc_macro_rules_binding(
1303        &'ra self,
1304        binding: MacroRulesBinding<'ra>,
1305    ) -> &'ra MacroRulesBinding<'ra> {
1306        self.dropless.alloc(binding)
1307    }
1308    fn alloc_ast_paths(&'ra self, paths: &[ast::Path]) -> &'ra [ast::Path] {
1309        self.ast_paths.alloc_from_iter(paths.iter().cloned())
1310    }
1311    fn alloc_macro(&'ra self, macro_data: MacroData) -> &'ra MacroData {
1312        self.macros.alloc(macro_data)
1313    }
1314    fn alloc_pattern_spans(&'ra self, spans: impl Iterator<Item = Span>) -> &'ra [Span] {
1315        self.dropless.alloc_from_iter(spans)
1316    }
1317}
1318
1319impl<'ra, 'tcx> AsMut<Resolver<'ra, 'tcx>> for Resolver<'ra, 'tcx> {
1320    fn as_mut(&mut self) -> &mut Resolver<'ra, 'tcx> {
1321        self
1322    }
1323}
1324
1325impl<'tcx> Resolver<'_, 'tcx> {
1326    fn opt_local_def_id(&self, node: NodeId) -> Option<LocalDefId> {
1327        self.opt_feed(node).map(|f| f.key())
1328    }
1329
1330    fn local_def_id(&self, node: NodeId) -> LocalDefId {
1331        self.feed(node).key()
1332    }
1333
1334    fn opt_feed(&self, node: NodeId) -> Option<Feed<'tcx, LocalDefId>> {
1335        self.node_id_to_def_id.get(&node).copied()
1336    }
1337
1338    fn feed(&self, node: NodeId) -> Feed<'tcx, LocalDefId> {
1339        self.opt_feed(node).unwrap_or_else(|| panic!("no entry for node id: `{node:?}`"))
1340    }
1341
1342    fn local_def_kind(&self, node: NodeId) -> DefKind {
1343        self.tcx.def_kind(self.local_def_id(node))
1344    }
1345
1346    /// Adds a definition with a parent definition.
1347    fn create_def(
1348        &mut self,
1349        parent: LocalDefId,
1350        node_id: ast::NodeId,
1351        name: Option<Symbol>,
1352        def_kind: DefKind,
1353        expn_id: ExpnId,
1354        span: Span,
1355    ) -> TyCtxtFeed<'tcx, LocalDefId> {
1356        assert!(
1357            !self.node_id_to_def_id.contains_key(&node_id),
1358            "adding a def for node-id {:?}, name {:?}, data {:?} but a previous def exists: {:?}",
1359            node_id,
1360            name,
1361            def_kind,
1362            self.tcx.definitions_untracked().def_key(self.node_id_to_def_id[&node_id].key()),
1363        );
1364
1365        // FIXME: remove `def_span` body, pass in the right spans here and call `tcx.at().create_def()`
1366        let feed = self.tcx.create_def(parent, name, def_kind, None, &mut self.disambiguator);
1367        let def_id = feed.def_id();
1368
1369        // Create the definition.
1370        if expn_id != ExpnId::root() {
1371            self.expn_that_defined.insert(def_id, expn_id);
1372        }
1373
1374        // A relative span's parent must be an absolute span.
1375        debug_assert_eq!(span.data_untracked().parent, None);
1376        let _id = self.tcx.untracked().source_span.push(span);
1377        debug_assert_eq!(_id, def_id);
1378
1379        // Some things for which we allocate `LocalDefId`s don't correspond to
1380        // anything in the AST, so they don't have a `NodeId`. For these cases
1381        // we don't need a mapping from `NodeId` to `LocalDefId`.
1382        if node_id != ast::DUMMY_NODE_ID {
1383            debug!("create_def: def_id_to_node_id[{:?}] <-> {:?}", def_id, node_id);
1384            self.node_id_to_def_id.insert(node_id, feed.downgrade());
1385        }
1386
1387        feed
1388    }
1389
1390    fn item_generics_num_lifetimes(&self, def_id: DefId) -> usize {
1391        if let Some(def_id) = def_id.as_local() {
1392            self.item_generics_num_lifetimes[&def_id]
1393        } else {
1394            self.tcx.generics_of(def_id).own_counts().lifetimes
1395        }
1396    }
1397
1398    pub fn tcx(&self) -> TyCtxt<'tcx> {
1399        self.tcx
1400    }
1401
1402    /// This function is very slow, as it iterates over the entire
1403    /// [Resolver::node_id_to_def_id] map just to find the [NodeId]
1404    /// that corresponds to the given [LocalDefId]. Only use this in
1405    /// diagnostics code paths.
1406    fn def_id_to_node_id(&self, def_id: LocalDefId) -> NodeId {
1407        self.node_id_to_def_id
1408            .items()
1409            .filter(|(_, v)| v.key() == def_id)
1410            .map(|(k, _)| *k)
1411            .get_only()
1412            .unwrap()
1413    }
1414}
1415
1416impl<'ra, 'tcx> Resolver<'ra, 'tcx> {
1417    pub fn new(
1418        tcx: TyCtxt<'tcx>,
1419        attrs: &[ast::Attribute],
1420        crate_span: Span,
1421        current_crate_outer_attr_insert_span: Span,
1422        arenas: &'ra ResolverArenas<'ra>,
1423    ) -> Resolver<'ra, 'tcx> {
1424        let root_def_id = CRATE_DEF_ID.to_def_id();
1425        let mut module_map = FxIndexMap::default();
1426        let mut module_self_bindings = FxHashMap::default();
1427        let graph_root = arenas.new_module(
1428            None,
1429            ModuleKind::Def(DefKind::Mod, root_def_id, None),
1430            ExpnId::root(),
1431            crate_span,
1432            attr::contains_name(attrs, sym::no_implicit_prelude),
1433            &mut module_map,
1434            &mut module_self_bindings,
1435        );
1436        let empty_module = arenas.new_module(
1437            None,
1438            ModuleKind::Def(DefKind::Mod, root_def_id, None),
1439            ExpnId::root(),
1440            DUMMY_SP,
1441            true,
1442            &mut Default::default(),
1443            &mut Default::default(),
1444        );
1445
1446        let mut node_id_to_def_id = NodeMap::default();
1447        let crate_feed = tcx.create_local_crate_def_id(crate_span);
1448
1449        crate_feed.def_kind(DefKind::Mod);
1450        let crate_feed = crate_feed.downgrade();
1451        node_id_to_def_id.insert(CRATE_NODE_ID, crate_feed);
1452
1453        let mut invocation_parents = FxHashMap::default();
1454        invocation_parents.insert(LocalExpnId::ROOT, InvocationParent::ROOT);
1455
1456        let mut extern_prelude: FxIndexMap<Ident, ExternPreludeEntry<'_>> = tcx
1457            .sess
1458            .opts
1459            .externs
1460            .iter()
1461            .filter(|(_, entry)| entry.add_prelude)
1462            .map(|(name, _)| (Ident::from_str(name), Default::default()))
1463            .collect();
1464
1465        if !attr::contains_name(attrs, sym::no_core) {
1466            extern_prelude.insert(Ident::with_dummy_span(sym::core), Default::default());
1467            if !attr::contains_name(attrs, sym::no_std) {
1468                extern_prelude.insert(Ident::with_dummy_span(sym::std), Default::default());
1469            }
1470        }
1471
1472        let registered_tools = tcx.registered_tools(());
1473
1474        let pub_vis = ty::Visibility::<DefId>::Public;
1475        let edition = tcx.sess.edition();
1476
1477        let mut resolver = Resolver {
1478            tcx,
1479
1480            expn_that_defined: Default::default(),
1481
1482            // The outermost module has def ID 0; this is not reflected in the
1483            // AST.
1484            graph_root,
1485            prelude: None,
1486            extern_prelude,
1487
1488            field_names: Default::default(),
1489            field_visibility_spans: FxHashMap::default(),
1490
1491            determined_imports: Vec::new(),
1492            indeterminate_imports: Vec::new(),
1493
1494            pat_span_map: Default::default(),
1495            partial_res_map: Default::default(),
1496            import_res_map: Default::default(),
1497            import_use_map: Default::default(),
1498            label_res_map: Default::default(),
1499            lifetimes_res_map: Default::default(),
1500            extra_lifetime_params_map: Default::default(),
1501            extern_crate_map: Default::default(),
1502            module_children: Default::default(),
1503            trait_map: NodeMap::default(),
1504            underscore_disambiguator: 0,
1505            empty_module,
1506            module_map,
1507            block_map: Default::default(),
1508            binding_parent_modules: FxHashMap::default(),
1509            ast_transform_scopes: FxHashMap::default(),
1510
1511            glob_map: Default::default(),
1512            glob_error: None,
1513            visibilities_for_hashing: Default::default(),
1514            used_imports: FxHashSet::default(),
1515            maybe_unused_trait_imports: Default::default(),
1516
1517            privacy_errors: Vec::new(),
1518            ambiguity_errors: Vec::new(),
1519            use_injections: Vec::new(),
1520            macro_expanded_macro_export_errors: BTreeSet::new(),
1521
1522            arenas,
1523            dummy_binding: (Res::Err, pub_vis, DUMMY_SP, LocalExpnId::ROOT).to_name_binding(arenas),
1524            builtin_types_bindings: PrimTy::ALL
1525                .iter()
1526                .map(|prim_ty| {
1527                    let binding = (Res::PrimTy(*prim_ty), pub_vis, DUMMY_SP, LocalExpnId::ROOT)
1528                        .to_name_binding(arenas);
1529                    (prim_ty.name(), binding)
1530                })
1531                .collect(),
1532            builtin_attrs_bindings: BUILTIN_ATTRIBUTES
1533                .iter()
1534                .map(|builtin_attr| {
1535                    let res = Res::NonMacroAttr(NonMacroAttrKind::Builtin(builtin_attr.name));
1536                    let binding =
1537                        (res, pub_vis, DUMMY_SP, LocalExpnId::ROOT).to_name_binding(arenas);
1538                    (builtin_attr.name, binding)
1539                })
1540                .collect(),
1541            registered_tool_bindings: registered_tools
1542                .iter()
1543                .map(|ident| {
1544                    let binding = (Res::ToolMod, pub_vis, ident.span, LocalExpnId::ROOT)
1545                        .to_name_binding(arenas);
1546                    (*ident, binding)
1547                })
1548                .collect(),
1549            module_self_bindings,
1550
1551            used_extern_options: Default::default(),
1552            macro_names: FxHashSet::default(),
1553            builtin_macros: Default::default(),
1554            registered_tools,
1555            macro_use_prelude: Default::default(),
1556            local_macro_map: Default::default(),
1557            extern_macro_map: Default::default(),
1558            dummy_ext_bang: Arc::new(SyntaxExtension::dummy_bang(edition)),
1559            dummy_ext_derive: Arc::new(SyntaxExtension::dummy_derive(edition)),
1560            non_macro_attr: arenas
1561                .alloc_macro(MacroData::new(Arc::new(SyntaxExtension::non_macro_attr(edition)))),
1562            invocation_parent_scopes: Default::default(),
1563            output_macro_rules_scopes: Default::default(),
1564            macro_rules_scopes: Default::default(),
1565            helper_attrs: Default::default(),
1566            derive_data: Default::default(),
1567            local_macro_def_scopes: FxHashMap::default(),
1568            name_already_seen: FxHashMap::default(),
1569            potentially_unused_imports: Vec::new(),
1570            potentially_unnecessary_qualifications: Default::default(),
1571            struct_constructors: Default::default(),
1572            unused_macros: Default::default(),
1573            unused_macro_rules: Default::default(),
1574            proc_macro_stubs: Default::default(),
1575            single_segment_macro_resolutions: Default::default(),
1576            multi_segment_macro_resolutions: Default::default(),
1577            builtin_attrs: Default::default(),
1578            containers_deriving_copy: Default::default(),
1579            lint_buffer: LintBuffer::default(),
1580            next_node_id: CRATE_NODE_ID,
1581            node_id_to_def_id,
1582            disambiguator: DisambiguatorState::new(),
1583            placeholder_field_indices: Default::default(),
1584            invocation_parents,
1585            legacy_const_generic_args: Default::default(),
1586            item_generics_num_lifetimes: Default::default(),
1587            main_def: Default::default(),
1588            trait_impls: Default::default(),
1589            proc_macros: Default::default(),
1590            confused_type_with_std_module: Default::default(),
1591            lifetime_elision_allowed: Default::default(),
1592            stripped_cfg_items: Default::default(),
1593            effective_visibilities: Default::default(),
1594            doc_link_resolutions: Default::default(),
1595            doc_link_traits_in_scope: Default::default(),
1596            all_macro_rules: Default::default(),
1597            delegation_fn_sigs: Default::default(),
1598            glob_delegation_invoc_ids: Default::default(),
1599            impl_unexpanded_invocations: Default::default(),
1600            impl_binding_keys: Default::default(),
1601            current_crate_outer_attr_insert_span,
1602            mods_with_parse_errors: Default::default(),
1603            impl_trait_names: Default::default(),
1604        };
1605
1606        let root_parent_scope = ParentScope::module(graph_root, &resolver);
1607        resolver.invocation_parent_scopes.insert(LocalExpnId::ROOT, root_parent_scope);
1608        resolver.feed_visibility(crate_feed, ty::Visibility::Public);
1609
1610        resolver
1611    }
1612
1613    fn new_module(
1614        &mut self,
1615        parent: Option<Module<'ra>>,
1616        kind: ModuleKind,
1617        expn_id: ExpnId,
1618        span: Span,
1619        no_implicit_prelude: bool,
1620    ) -> Module<'ra> {
1621        let module_map = &mut self.module_map;
1622        let module_self_bindings = &mut self.module_self_bindings;
1623        self.arenas.new_module(
1624            parent,
1625            kind,
1626            expn_id,
1627            span,
1628            no_implicit_prelude,
1629            module_map,
1630            module_self_bindings,
1631        )
1632    }
1633
1634    fn new_local_macro(&mut self, def_id: LocalDefId, macro_data: MacroData) -> &'ra MacroData {
1635        let mac = self.arenas.alloc_macro(macro_data);
1636        self.local_macro_map.insert(def_id, mac);
1637        mac
1638    }
1639
1640    fn next_node_id(&mut self) -> NodeId {
1641        let start = self.next_node_id;
1642        let next = start.as_u32().checked_add(1).expect("input too large; ran out of NodeIds");
1643        self.next_node_id = ast::NodeId::from_u32(next);
1644        start
1645    }
1646
1647    fn next_node_ids(&mut self, count: usize) -> std::ops::Range<NodeId> {
1648        let start = self.next_node_id;
1649        let end = start.as_usize().checked_add(count).expect("input too large; ran out of NodeIds");
1650        self.next_node_id = ast::NodeId::from_usize(end);
1651        start..self.next_node_id
1652    }
1653
1654    pub fn lint_buffer(&mut self) -> &mut LintBuffer {
1655        &mut self.lint_buffer
1656    }
1657
1658    pub fn arenas() -> ResolverArenas<'ra> {
1659        Default::default()
1660    }
1661
1662    fn feed_visibility(&mut self, feed: Feed<'tcx, LocalDefId>, vis: ty::Visibility) {
1663        let feed = feed.upgrade(self.tcx);
1664        feed.visibility(vis.to_def_id());
1665        self.visibilities_for_hashing.push((feed.def_id(), vis));
1666    }
1667
1668    pub fn into_outputs(self) -> ResolverOutputs {
1669        let proc_macros = self.proc_macros;
1670        let expn_that_defined = self.expn_that_defined;
1671        let extern_crate_map = self.extern_crate_map;
1672        let maybe_unused_trait_imports = self.maybe_unused_trait_imports;
1673        let glob_map = self.glob_map;
1674        let main_def = self.main_def;
1675        let confused_type_with_std_module = self.confused_type_with_std_module;
1676        let effective_visibilities = self.effective_visibilities;
1677
1678        let stripped_cfg_items = self
1679            .stripped_cfg_items
1680            .into_iter()
1681            .filter_map(|item| {
1682                let parent_module =
1683                    self.node_id_to_def_id.get(&item.parent_module)?.key().to_def_id();
1684                Some(StrippedCfgItem { parent_module, ident: item.ident, cfg: item.cfg })
1685            })
1686            .collect();
1687
1688        let global_ctxt = ResolverGlobalCtxt {
1689            expn_that_defined,
1690            visibilities_for_hashing: self.visibilities_for_hashing,
1691            effective_visibilities,
1692            extern_crate_map,
1693            module_children: self.module_children,
1694            glob_map,
1695            maybe_unused_trait_imports,
1696            main_def,
1697            trait_impls: self.trait_impls,
1698            proc_macros,
1699            confused_type_with_std_module,
1700            doc_link_resolutions: self.doc_link_resolutions,
1701            doc_link_traits_in_scope: self.doc_link_traits_in_scope,
1702            all_macro_rules: self.all_macro_rules,
1703            stripped_cfg_items,
1704        };
1705        let ast_lowering = ty::ResolverAstLowering {
1706            legacy_const_generic_args: self.legacy_const_generic_args,
1707            partial_res_map: self.partial_res_map,
1708            import_res_map: self.import_res_map,
1709            label_res_map: self.label_res_map,
1710            lifetimes_res_map: self.lifetimes_res_map,
1711            extra_lifetime_params_map: self.extra_lifetime_params_map,
1712            next_node_id: self.next_node_id,
1713            node_id_to_def_id: self
1714                .node_id_to_def_id
1715                .into_items()
1716                .map(|(k, f)| (k, f.key()))
1717                .collect(),
1718            disambiguator: self.disambiguator,
1719            trait_map: self.trait_map,
1720            lifetime_elision_allowed: self.lifetime_elision_allowed,
1721            lint_buffer: Steal::new(self.lint_buffer),
1722            delegation_fn_sigs: self.delegation_fn_sigs,
1723        };
1724        ResolverOutputs { global_ctxt, ast_lowering }
1725    }
1726
1727    fn create_stable_hashing_context(&self) -> StableHashingContext<'_> {
1728        StableHashingContext::new(self.tcx.sess, self.tcx.untracked())
1729    }
1730
1731    fn crate_loader<T>(&mut self, f: impl FnOnce(&mut CrateLoader<'_, '_>) -> T) -> T {
1732        f(&mut CrateLoader::new(
1733            self.tcx,
1734            &mut CStore::from_tcx_mut(self.tcx),
1735            &mut self.used_extern_options,
1736        ))
1737    }
1738
1739    fn cstore(&self) -> FreezeReadGuard<'_, CStore> {
1740        CStore::from_tcx(self.tcx)
1741    }
1742
1743    fn dummy_ext(&self, macro_kind: MacroKind) -> Arc<SyntaxExtension> {
1744        match macro_kind {
1745            MacroKind::Bang => Arc::clone(&self.dummy_ext_bang),
1746            MacroKind::Derive => Arc::clone(&self.dummy_ext_derive),
1747            MacroKind::Attr => Arc::clone(&self.non_macro_attr.ext),
1748        }
1749    }
1750
1751    /// Runs the function on each namespace.
1752    fn per_ns<F: FnMut(&mut Self, Namespace)>(&mut self, mut f: F) {
1753        f(self, TypeNS);
1754        f(self, ValueNS);
1755        f(self, MacroNS);
1756    }
1757
1758    fn is_builtin_macro(&self, res: Res) -> bool {
1759        self.get_macro(res).is_some_and(|macro_data| macro_data.ext.builtin_name.is_some())
1760    }
1761
1762    fn macro_def(&self, mut ctxt: SyntaxContext) -> DefId {
1763        loop {
1764            match ctxt.outer_expn_data().macro_def_id {
1765                Some(def_id) => return def_id,
1766                None => ctxt.remove_mark(),
1767            };
1768        }
1769    }
1770
1771    /// Entry point to crate resolution.
1772    pub fn resolve_crate(&mut self, krate: &Crate) {
1773        self.tcx.sess.time("resolve_crate", || {
1774            self.tcx.sess.time("finalize_imports", || self.finalize_imports());
1775            let exported_ambiguities = self.tcx.sess.time("compute_effective_visibilities", || {
1776                EffectiveVisibilitiesVisitor::compute_effective_visibilities(self, krate)
1777            });
1778            self.tcx.sess.time("check_hidden_glob_reexports", || {
1779                self.check_hidden_glob_reexports(exported_ambiguities)
1780            });
1781            self.tcx
1782                .sess
1783                .time("finalize_macro_resolutions", || self.finalize_macro_resolutions(krate));
1784            self.tcx.sess.time("late_resolve_crate", || self.late_resolve_crate(krate));
1785            self.tcx.sess.time("resolve_main", || self.resolve_main());
1786            self.tcx.sess.time("resolve_check_unused", || self.check_unused(krate));
1787            self.tcx.sess.time("resolve_report_errors", || self.report_errors(krate));
1788            self.tcx
1789                .sess
1790                .time("resolve_postprocess", || self.crate_loader(|c| c.postprocess(krate)));
1791        });
1792
1793        // Make sure we don't mutate the cstore from here on.
1794        self.tcx.untracked().cstore.freeze();
1795    }
1796
1797    fn traits_in_scope(
1798        &mut self,
1799        current_trait: Option<Module<'ra>>,
1800        parent_scope: &ParentScope<'ra>,
1801        ctxt: SyntaxContext,
1802        assoc_item: Option<(Symbol, Namespace)>,
1803    ) -> Vec<TraitCandidate> {
1804        let mut found_traits = Vec::new();
1805
1806        if let Some(module) = current_trait {
1807            if self.trait_may_have_item(Some(module), assoc_item) {
1808                let def_id = module.def_id();
1809                found_traits.push(TraitCandidate { def_id, import_ids: smallvec![] });
1810            }
1811        }
1812
1813        self.visit_scopes(ScopeSet::All(TypeNS), parent_scope, ctxt, |this, scope, _, _| {
1814            match scope {
1815                Scope::Module(module, _) => {
1816                    this.traits_in_module(module, assoc_item, &mut found_traits);
1817                }
1818                Scope::StdLibPrelude => {
1819                    if let Some(module) = this.prelude {
1820                        this.traits_in_module(module, assoc_item, &mut found_traits);
1821                    }
1822                }
1823                Scope::ExternPrelude | Scope::ToolPrelude | Scope::BuiltinTypes => {}
1824                _ => unreachable!(),
1825            }
1826            None::<()>
1827        });
1828
1829        found_traits
1830    }
1831
1832    fn traits_in_module(
1833        &mut self,
1834        module: Module<'ra>,
1835        assoc_item: Option<(Symbol, Namespace)>,
1836        found_traits: &mut Vec<TraitCandidate>,
1837    ) {
1838        module.ensure_traits(self);
1839        let traits = module.traits.borrow();
1840        for (trait_name, trait_binding) in traits.as_ref().unwrap().iter() {
1841            if self.trait_may_have_item(trait_binding.module(), assoc_item) {
1842                let def_id = trait_binding.res().def_id();
1843                let import_ids = self.find_transitive_imports(&trait_binding.kind, *trait_name);
1844                found_traits.push(TraitCandidate { def_id, import_ids });
1845            }
1846        }
1847    }
1848
1849    // List of traits in scope is pruned on best effort basis. We reject traits not having an
1850    // associated item with the given name and namespace (if specified). This is a conservative
1851    // optimization, proper hygienic type-based resolution of associated items is done in typeck.
1852    // We don't reject trait aliases (`trait_module == None`) because we don't have access to their
1853    // associated items.
1854    fn trait_may_have_item(
1855        &mut self,
1856        trait_module: Option<Module<'ra>>,
1857        assoc_item: Option<(Symbol, Namespace)>,
1858    ) -> bool {
1859        match (trait_module, assoc_item) {
1860            (Some(trait_module), Some((name, ns))) => self
1861                .resolutions(trait_module)
1862                .borrow()
1863                .iter()
1864                .any(|(key, _name_resolution)| key.ns == ns && key.ident.name == name),
1865            _ => true,
1866        }
1867    }
1868
1869    fn find_transitive_imports(
1870        &mut self,
1871        mut kind: &NameBindingKind<'_>,
1872        trait_name: Ident,
1873    ) -> SmallVec<[LocalDefId; 1]> {
1874        let mut import_ids = smallvec![];
1875        while let NameBindingKind::Import { import, binding, .. } = kind {
1876            if let Some(node_id) = import.id() {
1877                let def_id = self.local_def_id(node_id);
1878                self.maybe_unused_trait_imports.insert(def_id);
1879                import_ids.push(def_id);
1880            }
1881            self.add_to_glob_map(*import, trait_name);
1882            kind = &binding.kind;
1883        }
1884        import_ids
1885    }
1886
1887    fn new_disambiguated_key(&mut self, ident: Ident, ns: Namespace) -> BindingKey {
1888        let ident = ident.normalize_to_macros_2_0();
1889        let disambiguator = if ident.name == kw::Underscore {
1890            self.underscore_disambiguator += 1;
1891            self.underscore_disambiguator
1892        } else {
1893            0
1894        };
1895        BindingKey { ident, ns, disambiguator }
1896    }
1897
1898    fn resolutions(&mut self, module: Module<'ra>) -> &'ra Resolutions<'ra> {
1899        if module.populate_on_access.get() {
1900            module.populate_on_access.set(false);
1901            self.build_reduced_graph_external(module);
1902        }
1903        &module.0.0.lazy_resolutions
1904    }
1905
1906    fn resolution(
1907        &mut self,
1908        module: Module<'ra>,
1909        key: BindingKey,
1910    ) -> &'ra RefCell<NameResolution<'ra>> {
1911        *self
1912            .resolutions(module)
1913            .borrow_mut()
1914            .entry(key)
1915            .or_insert_with(|| self.arenas.alloc_name_resolution())
1916    }
1917
1918    /// Test if AmbiguityError ambi is any identical to any one inside ambiguity_errors
1919    fn matches_previous_ambiguity_error(&self, ambi: &AmbiguityError<'_>) -> bool {
1920        for ambiguity_error in &self.ambiguity_errors {
1921            // if the span location and ident as well as its span are the same
1922            if ambiguity_error.kind == ambi.kind
1923                && ambiguity_error.ident == ambi.ident
1924                && ambiguity_error.ident.span == ambi.ident.span
1925                && ambiguity_error.b1.span == ambi.b1.span
1926                && ambiguity_error.b2.span == ambi.b2.span
1927                && ambiguity_error.misc1 == ambi.misc1
1928                && ambiguity_error.misc2 == ambi.misc2
1929            {
1930                return true;
1931            }
1932        }
1933        false
1934    }
1935
1936    fn record_use(&mut self, ident: Ident, used_binding: NameBinding<'ra>, used: Used) {
1937        self.record_use_inner(ident, used_binding, used, used_binding.warn_ambiguity);
1938    }
1939
1940    fn record_use_inner(
1941        &mut self,
1942        ident: Ident,
1943        used_binding: NameBinding<'ra>,
1944        used: Used,
1945        warn_ambiguity: bool,
1946    ) {
1947        if let Some((b2, kind)) = used_binding.ambiguity {
1948            let ambiguity_error = AmbiguityError {
1949                kind,
1950                ident,
1951                b1: used_binding,
1952                b2,
1953                misc1: AmbiguityErrorMisc::None,
1954                misc2: AmbiguityErrorMisc::None,
1955                warning: warn_ambiguity,
1956            };
1957            if !self.matches_previous_ambiguity_error(&ambiguity_error) {
1958                // avoid duplicated span information to be emit out
1959                self.ambiguity_errors.push(ambiguity_error);
1960            }
1961        }
1962        if let NameBindingKind::Import { import, binding } = used_binding.kind {
1963            if let ImportKind::MacroUse { warn_private: true } = import.kind {
1964                // Do not report the lint if the macro name resolves in stdlib prelude
1965                // even without the problematic `macro_use` import.
1966                let found_in_stdlib_prelude = self.prelude.is_some_and(|prelude| {
1967                    self.maybe_resolve_ident_in_module(
1968                        ModuleOrUniformRoot::Module(prelude),
1969                        ident,
1970                        MacroNS,
1971                        &ParentScope::module(self.empty_module, self),
1972                        None,
1973                    )
1974                    .is_ok()
1975                });
1976                if !found_in_stdlib_prelude {
1977                    self.lint_buffer().buffer_lint(
1978                        PRIVATE_MACRO_USE,
1979                        import.root_id,
1980                        ident.span,
1981                        BuiltinLintDiag::MacroIsPrivate(ident),
1982                    );
1983                }
1984            }
1985            // Avoid marking `extern crate` items that refer to a name from extern prelude,
1986            // but not introduce it, as used if they are accessed from lexical scope.
1987            if used == Used::Scope {
1988                if let Some(entry) = self.extern_prelude.get(&ident.normalize_to_macros_2_0()) {
1989                    if !entry.introduced_by_item && entry.binding == Some(used_binding) {
1990                        return;
1991                    }
1992                }
1993            }
1994            let old_used = self.import_use_map.entry(import).or_insert(used);
1995            if *old_used < used {
1996                *old_used = used;
1997            }
1998            if let Some(id) = import.id() {
1999                self.used_imports.insert(id);
2000            }
2001            self.add_to_glob_map(import, ident);
2002            self.record_use_inner(
2003                ident,
2004                binding,
2005                Used::Other,
2006                warn_ambiguity || binding.warn_ambiguity,
2007            );
2008        }
2009    }
2010
2011    #[inline]
2012    fn add_to_glob_map(&mut self, import: Import<'_>, ident: Ident) {
2013        if let ImportKind::Glob { id, .. } = import.kind {
2014            let def_id = self.local_def_id(id);
2015            self.glob_map.entry(def_id).or_default().insert(ident.name);
2016        }
2017    }
2018
2019    fn resolve_crate_root(&mut self, ident: Ident) -> Module<'ra> {
2020        debug!("resolve_crate_root({:?})", ident);
2021        let mut ctxt = ident.span.ctxt();
2022        let mark = if ident.name == kw::DollarCrate {
2023            // When resolving `$crate` from a `macro_rules!` invoked in a `macro`,
2024            // we don't want to pretend that the `macro_rules!` definition is in the `macro`
2025            // as described in `SyntaxContext::apply_mark`, so we ignore prepended opaque marks.
2026            // FIXME: This is only a guess and it doesn't work correctly for `macro_rules!`
2027            // definitions actually produced by `macro` and `macro` definitions produced by
2028            // `macro_rules!`, but at least such configurations are not stable yet.
2029            ctxt = ctxt.normalize_to_macro_rules();
2030            debug!(
2031                "resolve_crate_root: marks={:?}",
2032                ctxt.marks().into_iter().map(|(i, t)| (i.expn_data(), t)).collect::<Vec<_>>()
2033            );
2034            let mut iter = ctxt.marks().into_iter().rev().peekable();
2035            let mut result = None;
2036            // Find the last opaque mark from the end if it exists.
2037            while let Some(&(mark, transparency)) = iter.peek() {
2038                if transparency == Transparency::Opaque {
2039                    result = Some(mark);
2040                    iter.next();
2041                } else {
2042                    break;
2043                }
2044            }
2045            debug!(
2046                "resolve_crate_root: found opaque mark {:?} {:?}",
2047                result,
2048                result.map(|r| r.expn_data())
2049            );
2050            // Then find the last semi-opaque mark from the end if it exists.
2051            for (mark, transparency) in iter {
2052                if transparency == Transparency::SemiOpaque {
2053                    result = Some(mark);
2054                } else {
2055                    break;
2056                }
2057            }
2058            debug!(
2059                "resolve_crate_root: found semi-opaque mark {:?} {:?}",
2060                result,
2061                result.map(|r| r.expn_data())
2062            );
2063            result
2064        } else {
2065            debug!("resolve_crate_root: not DollarCrate");
2066            ctxt = ctxt.normalize_to_macros_2_0();
2067            ctxt.adjust(ExpnId::root())
2068        };
2069        let module = match mark {
2070            Some(def) => self.expn_def_scope(def),
2071            None => {
2072                debug!(
2073                    "resolve_crate_root({:?}): found no mark (ident.span = {:?})",
2074                    ident, ident.span
2075                );
2076                return self.graph_root;
2077            }
2078        };
2079        let module = self.expect_module(
2080            module.opt_def_id().map_or(LOCAL_CRATE, |def_id| def_id.krate).as_def_id(),
2081        );
2082        debug!(
2083            "resolve_crate_root({:?}): got module {:?} ({:?}) (ident.span = {:?})",
2084            ident,
2085            module,
2086            module.kind.name(),
2087            ident.span
2088        );
2089        module
2090    }
2091
2092    fn resolve_self(&mut self, ctxt: &mut SyntaxContext, module: Module<'ra>) -> Module<'ra> {
2093        let mut module = self.expect_module(module.nearest_parent_mod());
2094        while module.span.ctxt().normalize_to_macros_2_0() != *ctxt {
2095            let parent = module.parent.unwrap_or_else(|| self.expn_def_scope(ctxt.remove_mark()));
2096            module = self.expect_module(parent.nearest_parent_mod());
2097        }
2098        module
2099    }
2100
2101    fn record_partial_res(&mut self, node_id: NodeId, resolution: PartialRes) {
2102        debug!("(recording res) recording {:?} for {}", resolution, node_id);
2103        if let Some(prev_res) = self.partial_res_map.insert(node_id, resolution) {
2104            panic!("path resolved multiple times ({prev_res:?} before, {resolution:?} now)");
2105        }
2106    }
2107
2108    fn record_pat_span(&mut self, node: NodeId, span: Span) {
2109        debug!("(recording pat) recording {:?} for {:?}", node, span);
2110        self.pat_span_map.insert(node, span);
2111    }
2112
2113    fn is_accessible_from(
2114        &self,
2115        vis: ty::Visibility<impl Into<DefId>>,
2116        module: Module<'ra>,
2117    ) -> bool {
2118        vis.is_accessible_from(module.nearest_parent_mod(), self.tcx)
2119    }
2120
2121    fn set_binding_parent_module(&mut self, binding: NameBinding<'ra>, module: Module<'ra>) {
2122        if let Some(old_module) = self.binding_parent_modules.insert(binding, module) {
2123            if module != old_module {
2124                span_bug!(binding.span, "parent module is reset for binding");
2125            }
2126        }
2127    }
2128
2129    fn disambiguate_macro_rules_vs_modularized(
2130        &self,
2131        macro_rules: NameBinding<'ra>,
2132        modularized: NameBinding<'ra>,
2133    ) -> bool {
2134        // Some non-controversial subset of ambiguities "modularized macro name" vs "macro_rules"
2135        // is disambiguated to mitigate regressions from macro modularization.
2136        // Scoping for `macro_rules` behaves like scoping for `let` at module level, in general.
2137        match (
2138            self.binding_parent_modules.get(&macro_rules),
2139            self.binding_parent_modules.get(&modularized),
2140        ) {
2141            (Some(macro_rules), Some(modularized)) => {
2142                macro_rules.nearest_parent_mod() == modularized.nearest_parent_mod()
2143                    && modularized.is_ancestor_of(*macro_rules)
2144            }
2145            _ => false,
2146        }
2147    }
2148
2149    fn extern_prelude_get(&mut self, ident: Ident, finalize: bool) -> Option<NameBinding<'ra>> {
2150        if ident.is_path_segment_keyword() {
2151            // Make sure `self`, `super` etc produce an error when passed to here.
2152            return None;
2153        }
2154
2155        let norm_ident = ident.normalize_to_macros_2_0();
2156        let binding = self.extern_prelude.get(&norm_ident).cloned().and_then(|entry| {
2157            Some(if let Some(binding) = entry.binding {
2158                if finalize {
2159                    if !entry.is_import() {
2160                        self.crate_loader(|c| c.process_path_extern(ident.name, ident.span));
2161                    } else if entry.introduced_by_item {
2162                        self.record_use(ident, binding, Used::Other);
2163                    }
2164                }
2165                binding
2166            } else {
2167                let crate_id = if finalize {
2168                    let Some(crate_id) =
2169                        self.crate_loader(|c| c.process_path_extern(ident.name, ident.span))
2170                    else {
2171                        return Some(self.dummy_binding);
2172                    };
2173                    crate_id
2174                } else {
2175                    self.crate_loader(|c| c.maybe_process_path_extern(ident.name))?
2176                };
2177                let crate_root = self.expect_module(crate_id.as_def_id());
2178                let vis = ty::Visibility::<DefId>::Public;
2179                (crate_root, vis, DUMMY_SP, LocalExpnId::ROOT).to_name_binding(self.arenas)
2180            })
2181        });
2182
2183        if let Some(entry) = self.extern_prelude.get_mut(&norm_ident) {
2184            entry.binding = binding;
2185        }
2186
2187        binding
2188    }
2189
2190    /// Rustdoc uses this to resolve doc link paths in a recoverable way. `PathResult<'a>`
2191    /// isn't something that can be returned because it can't be made to live that long,
2192    /// and also it's a private type. Fortunately rustdoc doesn't need to know the error,
2193    /// just that an error occurred.
2194    fn resolve_rustdoc_path(
2195        &mut self,
2196        path_str: &str,
2197        ns: Namespace,
2198        parent_scope: ParentScope<'ra>,
2199    ) -> Option<Res> {
2200        let segments: Result<Vec<_>, ()> = path_str
2201            .split("::")
2202            .enumerate()
2203            .map(|(i, s)| {
2204                let sym = if s.is_empty() {
2205                    if i == 0 {
2206                        // For a path like `::a::b`, use `kw::PathRoot` as the leading segment.
2207                        kw::PathRoot
2208                    } else {
2209                        return Err(()); // occurs in cases like `String::`
2210                    }
2211                } else {
2212                    Symbol::intern(s)
2213                };
2214                Ok(Segment::from_ident(Ident::with_dummy_span(sym)))
2215            })
2216            .collect();
2217        let Ok(segments) = segments else { return None };
2218
2219        match self.maybe_resolve_path(&segments, Some(ns), &parent_scope, None) {
2220            PathResult::Module(ModuleOrUniformRoot::Module(module)) => Some(module.res().unwrap()),
2221            PathResult::NonModule(path_res) => {
2222                path_res.full_res().filter(|res| !matches!(res, Res::Def(DefKind::Ctor(..), _)))
2223            }
2224            PathResult::Module(ModuleOrUniformRoot::ExternPrelude) | PathResult::Failed { .. } => {
2225                None
2226            }
2227            PathResult::Module(..) | PathResult::Indeterminate => unreachable!(),
2228        }
2229    }
2230
2231    /// Retrieves definition span of the given `DefId`.
2232    fn def_span(&self, def_id: DefId) -> Span {
2233        match def_id.as_local() {
2234            Some(def_id) => self.tcx.source_span(def_id),
2235            // Query `def_span` is not used because hashing its result span is expensive.
2236            None => self.cstore().def_span_untracked(def_id, self.tcx.sess),
2237        }
2238    }
2239
2240    fn field_idents(&self, def_id: DefId) -> Option<Vec<Ident>> {
2241        match def_id.as_local() {
2242            Some(def_id) => self.field_names.get(&def_id).cloned(),
2243            None => Some(
2244                self.tcx
2245                    .associated_item_def_ids(def_id)
2246                    .iter()
2247                    .map(|&def_id| {
2248                        Ident::new(self.tcx.item_name(def_id), self.tcx.def_span(def_id))
2249                    })
2250                    .collect(),
2251            ),
2252        }
2253    }
2254
2255    /// Checks if an expression refers to a function marked with
2256    /// `#[rustc_legacy_const_generics]` and returns the argument index list
2257    /// from the attribute.
2258    fn legacy_const_generic_args(&mut self, expr: &Expr) -> Option<Vec<usize>> {
2259        if let ExprKind::Path(None, path) = &expr.kind {
2260            // Don't perform legacy const generics rewriting if the path already
2261            // has generic arguments.
2262            if path.segments.last().unwrap().args.is_some() {
2263                return None;
2264            }
2265
2266            let res = self.partial_res_map.get(&expr.id)?.full_res()?;
2267            if let Res::Def(def::DefKind::Fn, def_id) = res {
2268                // We only support cross-crate argument rewriting. Uses
2269                // within the same crate should be updated to use the new
2270                // const generics style.
2271                if def_id.is_local() {
2272                    return None;
2273                }
2274
2275                if let Some(v) = self.legacy_const_generic_args.get(&def_id) {
2276                    return v.clone();
2277                }
2278
2279                let attr = self.tcx.get_attr(def_id, sym::rustc_legacy_const_generics)?;
2280                let mut ret = Vec::new();
2281                for meta in attr.meta_item_list()? {
2282                    match meta.lit()?.kind {
2283                        LitKind::Int(a, _) => ret.push(a.get() as usize),
2284                        _ => panic!("invalid arg index"),
2285                    }
2286                }
2287                // Cache the lookup to avoid parsing attributes for an item multiple times.
2288                self.legacy_const_generic_args.insert(def_id, Some(ret.clone()));
2289                return Some(ret);
2290            }
2291        }
2292        None
2293    }
2294
2295    fn resolve_main(&mut self) {
2296        let module = self.graph_root;
2297        let ident = Ident::with_dummy_span(sym::main);
2298        let parent_scope = &ParentScope::module(module, self);
2299
2300        let Ok(name_binding) = self.maybe_resolve_ident_in_module(
2301            ModuleOrUniformRoot::Module(module),
2302            ident,
2303            ValueNS,
2304            parent_scope,
2305            None,
2306        ) else {
2307            return;
2308        };
2309
2310        let res = name_binding.res();
2311        let is_import = name_binding.is_import();
2312        let span = name_binding.span;
2313        if let Res::Def(DefKind::Fn, _) = res {
2314            self.record_use(ident, name_binding, Used::Other);
2315        }
2316        self.main_def = Some(MainDefinition { res, is_import, span });
2317    }
2318}
2319
2320fn names_to_string(names: impl Iterator<Item = Symbol>) -> String {
2321    let mut result = String::new();
2322    for (i, name) in names.filter(|name| *name != kw::PathRoot).enumerate() {
2323        if i > 0 {
2324            result.push_str("::");
2325        }
2326        if Ident::with_dummy_span(name).is_raw_guess() {
2327            result.push_str("r#");
2328        }
2329        result.push_str(name.as_str());
2330    }
2331    result
2332}
2333
2334fn path_names_to_string(path: &Path) -> String {
2335    names_to_string(path.segments.iter().map(|seg| seg.ident.name))
2336}
2337
2338/// A somewhat inefficient routine to obtain the name of a module.
2339fn module_to_string(mut module: Module<'_>) -> Option<String> {
2340    let mut names = Vec::new();
2341    loop {
2342        if let ModuleKind::Def(.., name) = module.kind {
2343            if let Some(parent) = module.parent {
2344                // `unwrap` is safe: the presence of a parent means it's not the crate root.
2345                names.push(name.unwrap());
2346                module = parent
2347            } else {
2348                break;
2349            }
2350        } else {
2351            names.push(sym::opaque_module_name_placeholder);
2352            let Some(parent) = module.parent else {
2353                return None;
2354            };
2355            module = parent;
2356        }
2357    }
2358    if names.is_empty() {
2359        return None;
2360    }
2361    Some(names_to_string(names.iter().rev().copied()))
2362}
2363
2364#[derive(Copy, Clone, Debug)]
2365struct Finalize {
2366    /// Node ID for linting.
2367    node_id: NodeId,
2368    /// Span of the whole path or some its characteristic fragment.
2369    /// E.g. span of `b` in `foo::{a, b, c}`, or full span for regular paths.
2370    path_span: Span,
2371    /// Span of the path start, suitable for prepending something to it.
2372    /// E.g. span of `foo` in `foo::{a, b, c}`, or full span for regular paths.
2373    root_span: Span,
2374    /// Whether to report privacy errors or silently return "no resolution" for them,
2375    /// similarly to speculative resolution.
2376    report_private: bool,
2377    /// Tracks whether an item is used in scope or used relatively to a module.
2378    used: Used,
2379}
2380
2381impl Finalize {
2382    fn new(node_id: NodeId, path_span: Span) -> Finalize {
2383        Finalize::with_root_span(node_id, path_span, path_span)
2384    }
2385
2386    fn with_root_span(node_id: NodeId, path_span: Span, root_span: Span) -> Finalize {
2387        Finalize { node_id, path_span, root_span, report_private: true, used: Used::Other }
2388    }
2389}
2390
2391pub fn provide(providers: &mut Providers) {
2392    providers.registered_tools = macros::registered_tools;
2393}