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