Auto merge of #103965 - petrochenkov:effvisperf3, r=oli-obk

resolve: More detailed effective visibility tracking for imports

Per-`DefId` tracking is not enough, due to glob imports in particular, which have a single `DefId` for the whole glob import item.
We need to track this stuff per every introduced name (`NameBinding`).

Also drop `extern` blocks from the effective visibility table, they are nominally private and it doesn't make sense to keep them there.

Later commits add some debug-only invariant checking and optimiaztions to mitigate regressions in https://github.com/rust-lang/rust/pull/103965#issuecomment-1304256445.

This is a bugfix and continuation of https://github.com/rust-lang/rust/pull/102026.

2 files changed, 147 insertions, 94 deletions

diff --git a/compiler/rustc_resolve/src/effective_visibilities.rs b/compiler/rustc_resolve/src/effective_visibilities.rs
index 17ce854cb43..fa6d34be0cc 100644
--- a/compiler/rustc_resolve/src/effective_visibilities.rs
+++ b/compiler/rustc_resolve/src/effective_visibilities.rs
@@ -1,16 +1,38 @@
-use crate::{ImportKind, NameBindingKind, Resolver};
+use crate::{ImportKind, NameBinding, NameBindingKind, Resolver, ResolverTree};
 use rustc_ast::ast;
 use rustc_ast::visit;
 use rustc_ast::visit::Visitor;
 use rustc_ast::Crate;
 use rustc_ast::EnumDef;
+use rustc_data_structures::intern::Interned;
 use rustc_hir::def_id::LocalDefId;
 use rustc_hir::def_id::CRATE_DEF_ID;
-use rustc_middle::middle::privacy::Level;
-use rustc_middle::ty::{DefIdTree, Visibility};
+use rustc_middle::middle::privacy::{EffectiveVisibilities, EffectiveVisibility, Level};
+use rustc_middle::ty::Visibility;
+
+type ImportId<'a> = Interned<'a, NameBinding<'a>>;
+
+#[derive(Clone, Copy)]
+enum ParentId<'a> {
+    Def(LocalDefId),
+    Import(ImportId<'a>),
+}
+
+impl ParentId<'_> {
+    fn level(self) -> Level {
+        match self {
+            ParentId::Def(_) => Level::Direct,
+            ParentId::Import(_) => Level::Reexported,
+        }
+    }
+}
 
 pub struct EffectiveVisibilitiesVisitor<'r, 'a> {
     r: &'r mut Resolver<'a>,
+    /// While walking import chains we need to track effective visibilities per-binding, and def id
+    /// keys in `Resolver::effective_visibilities` are not enough for that, because multiple
+    /// bindings can correspond to a single def id in imports. So we keep a separate table.
+    import_effective_visibilities: EffectiveVisibilities<ImportId<'a>>,
     changed: bool,
 }
 
@@ -19,21 +41,57 @@ impl<'r, 'a> EffectiveVisibilitiesVisitor<'r, 'a> {
     /// For now, this doesn't resolve macros (FIXME) and cannot resolve Impl, as we
     /// need access to a TyCtxt for that.
     pub fn compute_effective_visibilities<'c>(r: &'r mut Resolver<'a>, krate: &'c Crate) {
-        let mut visitor = EffectiveVisibilitiesVisitor { r, changed: false };
+        let mut visitor = EffectiveVisibilitiesVisitor {
+            r,
+            import_effective_visibilities: Default::default(),
+            changed: false,
+        };
 
-        visitor.update(CRATE_DEF_ID, Visibility::Public, CRATE_DEF_ID, Level::Direct);
+        visitor.update(CRATE_DEF_ID, CRATE_DEF_ID);
         visitor.set_bindings_effective_visibilities(CRATE_DEF_ID);
 
         while visitor.changed {
-            visitor.reset();
+            visitor.changed = false;
             visit::walk_crate(&mut visitor, krate);
         }
 
+        // Update visibilities for import def ids. These are not used during the
+        // `EffectiveVisibilitiesVisitor` pass, because we have more detailed binding-based
+        // information, but are used by later passes. Effective visibility of an import def id
+        // is the maximum value among visibilities of bindings corresponding to that def id.
+        for (binding, eff_vis) in visitor.import_effective_visibilities.iter() {
+            let NameBindingKind::Import { import, .. } = binding.kind else { unreachable!() };
+            if let Some(node_id) = import.id() {
+                let mut update = |node_id| {
+                    r.effective_visibilities.update_eff_vis(
+                        r.local_def_id(node_id),
+                        eff_vis,
+                        ResolverTree(&r.definitions, &r.crate_loader),
+                    )
+                };
+                update(node_id);
+                if let ImportKind::Single { additional_ids: (id1, id2), .. } = import.kind {
+                    // In theory all the single import IDs have individual visibilities and
+                    // effective visibilities, but in practice these IDs go straigth to HIR
+                    // where all their few uses assume that their (effective) visibility
+                    // applies to the whole syntactic `use` item. So they all get the same
+                    // value which is the maximum of all bindings. Maybe HIR for imports
+                    // shouldn't use three IDs at all.
+                    if id1 != ast::DUMMY_NODE_ID {
+                        update(id1);
+                    }
+                    if id2 != ast::DUMMY_NODE_ID {
+                        update(id2);
+                    }
+                }
+            }
+        }
+
         info!("resolve::effective_visibilities: {:#?}", r.effective_visibilities);
     }
 
-    fn reset(&mut self) {
-        self.changed = false;
+    fn nearest_normal_mod(&mut self, def_id: LocalDefId) -> LocalDefId {
+        self.r.get_nearest_non_block_module(def_id.to_def_id()).nearest_parent_mod().expect_local()
     }
 
     /// Update effective visibilities of bindings in the given module,
@@ -48,92 +106,83 @@ impl<'r, 'a> EffectiveVisibilitiesVisitor<'r, 'a> {
                 // Set the given effective visibility level to `Level::Direct` and
                 // sets the rest of the `use` chain to `Level::Reexported` until
                 // we hit the actual exported item.
+                let mut parent_id = ParentId::Def(module_id);
+                while let NameBindingKind::Import { binding: nested_binding, .. } = binding.kind {
+                    let binding_id = ImportId::new_unchecked(binding);
+                    self.update_import(binding_id, parent_id);
 
-                // FIXME: tag and is_public() condition should be removed, but assertions occur.
-                let tag = if binding.is_import() { Level::Reexported } else { Level::Direct };
-                if binding.vis.is_public() {
-                    let mut prev_parent_id = module_id;
-                    let mut level = Level::Direct;
-                    while let NameBindingKind::Import { binding: nested_binding, import, .. } =
-                        binding.kind
-                    {
-                        let mut update = |node_id| {
-                            self.update(
-                                self.r.local_def_id(node_id),
-                                binding.vis.expect_local(),
-                                prev_parent_id,
-                                level,
-                            )
-                        };
-                        match import.kind {
-                            ImportKind::Single { id, additional_ids, .. } => {
-                                // In theory all the import IDs have individual visibilities and
-                                // effective visibilities, but in practice these IDs go straigth to
-                                // HIR where all their few uses assume that their (effective)
-                                // visibility applies to the whole syntactic `use` item. So we
-                                // update them all to the maximum value among the potential
-                                // individual effective visibilities. Maybe HIR for imports
-                                // shouldn't use three IDs at all.
-                                update(id);
-                                update(additional_ids.0);
-                                update(additional_ids.1);
-                                prev_parent_id = self.r.local_def_id(id);
-                            }
-                            ImportKind::Glob { id, .. } | ImportKind::ExternCrate { id, .. } => {
-                                update(id);
-                                prev_parent_id = self.r.local_def_id(id);
-                            }
-                            ImportKind::MacroUse => {
-                                // In theory we should reset the parent id to something private
-                                // here, but `macro_use` imports always refer to external items,
-                                // so it doesn't matter and we can just do nothing.
-                            }
-                            ImportKind::MacroExport => {
-                                // In theory we should reset the parent id to something public
-                                // here, but it has the same effect as leaving the previous parent,
-                                // so we can just do nothing.
-                            }
-                        }
-
-                        level = Level::Reexported;
-                        binding = nested_binding;
-                    }
+                    parent_id = ParentId::Import(binding_id);
+                    binding = nested_binding;
                 }
 
                 if let Some(def_id) = binding.res().opt_def_id().and_then(|id| id.as_local()) {
-                    self.update(def_id, binding.vis.expect_local(), module_id, tag);
+                    self.update_def(def_id, binding.vis.expect_local(), parent_id);
                 }
             }
         }
     }
 
-    fn update(
-        &mut self,
-        def_id: LocalDefId,
+    fn effective_vis(&self, parent_id: ParentId<'a>) -> Option<EffectiveVisibility> {
+        match parent_id {
+            ParentId::Def(def_id) => self.r.effective_visibilities.effective_vis(def_id),
+            ParentId::Import(binding) => self.import_effective_visibilities.effective_vis(binding),
+        }
+        .copied()
+    }
+
+    /// The update is guaranteed to not change the table and we can skip it.
+    fn is_noop_update(
+        &self,
+        parent_id: ParentId<'a>,
         nominal_vis: Visibility,
-        parent_id: LocalDefId,
-        tag: Level,
-    ) {
-        let module_id = self
-            .r
-            .get_nearest_non_block_module(def_id.to_def_id())
-            .nearest_parent_mod()
-            .expect_local();
-        if nominal_vis == Visibility::Restricted(module_id)
-            || self.r.visibilities[&parent_id] == Visibility::Restricted(module_id)
-        {
+        default_vis: Visibility,
+    ) -> bool {
+        nominal_vis == default_vis
+            || match parent_id {
+                ParentId::Def(def_id) => self.r.visibilities[&def_id],
+                ParentId::Import(binding) => binding.vis.expect_local(),
+            } == default_vis
+    }
+
+    fn update_import(&mut self, binding: ImportId<'a>, parent_id: ParentId<'a>) {
+        let NameBindingKind::Import { import, .. } = binding.kind else { unreachable!() };
+        let nominal_vis = binding.vis.expect_local();
+        let default_vis = Visibility::Restricted(
+            import
+                .id()
+                .map(|id| self.nearest_normal_mod(self.r.local_def_id(id)))
+                .unwrap_or(CRATE_DEF_ID),
+        );
+        if self.is_noop_update(parent_id, nominal_vis, default_vis) {
             return;
         }
-        let mut effective_visibilities = std::mem::take(&mut self.r.effective_visibilities);
-        self.changed |= effective_visibilities.update(
+        self.changed |= self.import_effective_visibilities.update(
+            binding,
+            nominal_vis,
+            default_vis,
+            self.effective_vis(parent_id),
+            parent_id.level(),
+            ResolverTree(&self.r.definitions, &self.r.crate_loader),
+        );
+    }
+
+    fn update_def(&mut self, def_id: LocalDefId, nominal_vis: Visibility, parent_id: ParentId<'a>) {
+        let default_vis = Visibility::Restricted(self.nearest_normal_mod(def_id));
+        if self.is_noop_update(parent_id, nominal_vis, default_vis) {
+            return;
+        }
+        self.changed |= self.r.effective_visibilities.update(
             def_id,
             nominal_vis,
-            || Visibility::Restricted(module_id),
-            parent_id,
-            tag,
-            &*self.r,
+            if def_id == CRATE_DEF_ID { Visibility::Public } else { default_vis },
+            self.effective_vis(parent_id),
+            parent_id.level(),
+            ResolverTree(&self.r.definitions, &self.r.crate_loader),
         );
-        self.r.effective_visibilities = effective_visibilities;
+    }
+
+    fn update(&mut self, def_id: LocalDefId, parent_id: LocalDefId) {
+        self.update_def(def_id, self.r.visibilities[&def_id], ParentId::Def(parent_id));
     }
 }
 
@@ -151,12 +200,6 @@ impl<'r, 'ast> Visitor<'ast> for EffectiveVisibilitiesVisitor<'ast, 'r> {
                 "ast::ItemKind::MacCall encountered, this should not anymore appear at this stage"
             ),
 
-            // Foreign modules inherit level from parents.
-            ast::ItemKind::ForeignMod(..) => {
-                let parent_id = self.r.local_parent(def_id);
-                self.update(def_id, Visibility::Public, parent_id, Level::Direct);
-            }
-
             ast::ItemKind::Mod(..) => {
                 self.set_bindings_effective_visibilities(def_id);
                 visit::walk_item(self, item);
@@ -167,18 +210,14 @@ impl<'r, 'ast> Visitor<'ast> for EffectiveVisibilitiesVisitor<'ast, 'r> {
                 for variant in variants {
                     let variant_def_id = self.r.local_def_id(variant.id);
                     for field in variant.data.fields() {
-                        let field_def_id = self.r.local_def_id(field.id);
-                        let vis = self.r.visibilities[&field_def_id];
-                        self.update(field_def_id, vis, variant_def_id, Level::Direct);
+                        self.update(self.r.local_def_id(field.id), variant_def_id);
                     }
                 }
             }
 
             ast::ItemKind::Struct(ref def, _) | ast::ItemKind::Union(ref def, _) => {
                 for field in def.fields() {
-                    let field_def_id = self.r.local_def_id(field.id);
-                    let vis = self.r.visibilities[&field_def_id];
-                    self.update(field_def_id, vis, def_id, Level::Direct);
+                    self.update(self.r.local_def_id(field.id), def_id);
                 }
             }
 
@@ -194,6 +233,7 @@ impl<'r, 'ast> Visitor<'ast> for EffectiveVisibilitiesVisitor<'ast, 'r> {
             | ast::ItemKind::TyAlias(..)
             | ast::ItemKind::TraitAlias(..)
             | ast::ItemKind::MacroDef(..)
+            | ast::ItemKind::ForeignMod(..)
             | ast::ItemKind::Fn(..) => return,
         }
     }
diff --git a/compiler/rustc_resolve/src/lib.rs b/compiler/rustc_resolve/src/lib.rs
index ee1c97d5ad2..a1ff477c6fe 100644
--- a/compiler/rustc_resolve/src/lib.rs
+++ b/compiler/rustc_resolve/src/lib.rs
@@ -1106,17 +1106,30 @@ impl<'a> AsMut<Resolver<'a>> for Resolver<'a> {
     }
 }
 
-impl<'a, 'b> DefIdTree for &'a Resolver<'b> {
+/// A minimal subset of resolver that can implemenent `DefIdTree`, sometimes
+/// required to satisfy borrow checker by avoiding borrowing the whole resolver.
+#[derive(Clone, Copy)]
+struct ResolverTree<'a, 'b>(&'a Definitions, &'a CrateLoader<'b>);
+
+impl DefIdTree for ResolverTree<'_, '_> {
     #[inline]
     fn opt_parent(self, id: DefId) -> Option<DefId> {
+        let ResolverTree(definitions, crate_loader) = self;
         match id.as_local() {
-            Some(id) => self.definitions.def_key(id).parent,
-            None => self.cstore().def_key(id).parent,
+            Some(id) => definitions.def_key(id).parent,
+            None => crate_loader.cstore().def_key(id).parent,
         }
         .map(|index| DefId { index, ..id })
     }
 }
 
+impl<'a, 'b> DefIdTree for &'a Resolver<'b> {
+    #[inline]
+    fn opt_parent(self, id: DefId) -> Option<DefId> {
+        ResolverTree(&self.definitions, &self.crate_loader).opt_parent(id)
+    }
+}
+
 impl Resolver<'_> {
     fn opt_local_def_id(&self, node: NodeId) -> Option<LocalDefId> {
         self.node_id_to_def_id.get(&node).copied()