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