Do not compute entry parent when not required.

3 files changed, 127 insertions, 100 deletions

diff --git a/compiler/rustc_middle/src/hir/map/collector.rs b/compiler/rustc_middle/src/hir/map/collector.rs
index 3b804819fb5..23780b38196 100644
--- a/compiler/rustc_middle/src/hir/map/collector.rs
+++ b/compiler/rustc_middle/src/hir/map/collector.rs
@@ -1,5 +1,5 @@
 use crate::arena::Arena;
-use crate::hir::map::{Entry, HirOwnerData, Map};
+use crate::hir::map::{HirOwnerData, Map};
 use crate::hir::{Owner, OwnerNodes, ParentedNode};
 use crate::ich::StableHashingContext;
 use rustc_data_structures::fingerprint::Fingerprint;
@@ -61,6 +61,13 @@ fn hash_body(
     stable_hasher.finish()
 }
 
+/// Represents an entry and its parent `HirId`.
+#[derive(Copy, Clone, Debug)]
+pub struct Entry<'hir> {
+    parent: HirId,
+    node: Node<'hir>,
+}
+
 impl<'a, 'hir> NodeCollector<'a, 'hir> {
     pub(super) fn root(
         sess: &'a Session,
diff --git a/compiler/rustc_middle/src/hir/map/mod.rs b/compiler/rustc_middle/src/hir/map/mod.rs
index 973707c59fa..5e6e79540d6 100644
--- a/compiler/rustc_middle/src/hir/map/mod.rs
+++ b/compiler/rustc_middle/src/hir/map/mod.rs
@@ -14,6 +14,7 @@ use rustc_hir::intravisit;
 use rustc_hir::intravisit::Visitor;
 use rustc_hir::itemlikevisit::ItemLikeVisitor;
 use rustc_hir::*;
+use rustc_index::vec::Idx;
 use rustc_span::hygiene::MacroKind;
 use rustc_span::source_map::Spanned;
 use rustc_span::symbol::{kw, Ident, Symbol};
@@ -23,13 +24,6 @@ use rustc_target::spec::abi::Abi;
 pub mod blocks;
 mod collector;
 
-/// Represents an entry and its parent `HirId`.
-#[derive(Copy, Clone, Debug)]
-pub struct Entry<'hir> {
-    parent: HirId,
-    node: Node<'hir>,
-}
-
 fn fn_decl<'hir>(node: Node<'hir>) -> Option<&'hir FnDecl<'hir>> {
     match node {
         Node::Item(Item { kind: ItemKind::Fn(sig, _, _), .. })
@@ -108,10 +102,48 @@ impl<'hir> Iterator for ParentHirIterator<'_, 'hir> {
             }
 
             self.current_id = parent_id;
-            if let Some(entry) = self.map.find_entry(parent_id) {
-                return Some((parent_id, entry.node));
+            if let Some(node) = self.map.find(parent_id) {
+                return Some((parent_id, node));
+            }
+            // If this `HirId` doesn't have an entry, skip it and look for its `parent_id`.
+        }
+    }
+}
+
+/// An iterator that walks up the ancestor tree of a given `HirId`.
+/// Constructed using `tcx.hir().parent_owner_iter(hir_id)`.
+pub struct ParentOwnerIterator<'map, 'hir> {
+    current_id: HirId,
+    map: &'map Map<'hir>,
+}
+
+impl<'hir> Iterator for ParentOwnerIterator<'_, 'hir> {
+    type Item = (HirId, Node<'hir>);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.current_id.local_id.index() != 0 {
+            self.current_id.local_id = ItemLocalId::new(0);
+            if let Some(node) = self.map.find(self.current_id) {
+                return Some((self.current_id, node));
+            }
+        }
+        if self.current_id == CRATE_HIR_ID {
+            return None;
+        }
+        loop {
+            // There are nodes that do not have entries, so we need to skip them.
+            let parent_id = self.map.def_key(self.current_id.owner).parent;
+
+            let parent_id = parent_id.map_or(CRATE_HIR_ID.owner, |local_def_index| {
+                let def_id = LocalDefId { local_def_index };
+                self.map.local_def_id_to_hir_id(def_id).owner
+            });
+            self.current_id = HirId::make_owner(parent_id);
+
+            // If this `HirId` doesn't have an entry, skip it and look for its `parent_id`.
+            if let Some(node) = self.map.find(self.current_id) {
+                return Some((self.current_id, node));
             }
-            // If this `HirId` doesn't have an `Entry`, skip it and look for its `parent_id`.
         }
     }
 }
@@ -144,7 +176,7 @@ impl<'hir> Map<'hir> {
             bug!(
                 "local_def_id: no entry for `{:?}`, which has a map of `{:?}`",
                 hir_id,
-                self.find_entry(hir_id)
+                self.find(hir_id)
             )
         })
     }
@@ -251,27 +283,61 @@ impl<'hir> Map<'hir> {
             .unwrap_or_else(|| bug!("def_kind: unsupported node: {:?}", local_def_id))
     }
 
-    fn find_entry(&self, id: HirId) -> Option<Entry<'hir>> {
+    pub fn find_parent_node(&self, id: HirId) -> Option<HirId> {
         if id.local_id == ItemLocalId::from_u32(0) {
-            let owner = self.tcx.hir_owner(id.owner);
-            owner.map(|owner| Entry { parent: owner.parent, node: owner.node })
+            let owner = self.tcx.hir_owner(id.owner)?;
+            Some(owner.parent)
         } else {
-            let owner = self.tcx.hir_owner_nodes(id.owner);
-            owner.and_then(|owner| {
-                let node = owner.nodes[id.local_id].as_ref();
-                // FIXME(eddyb) use a single generic type instead of having both
-                // `Entry` and `ParentedNode`, which are effectively the same.
-                // Alternatively, rewrite code using `Entry` to use `ParentedNode`.
-                node.map(|node| Entry {
-                    parent: HirId { owner: id.owner, local_id: node.parent },
-                    node: node.node,
-                })
-            })
+            let owner = self.tcx.hir_owner_nodes(id.owner)?;
+            let node = owner.nodes[id.local_id].as_ref()?;
+            let hir_id = HirId { owner: id.owner, local_id: node.parent };
+            Some(hir_id)
         }
     }
 
-    fn get_entry(&self, id: HirId) -> Entry<'hir> {
-        self.find_entry(id).unwrap()
+    pub fn get_parent_node(&self, hir_id: HirId) -> HirId {
+        self.find_parent_node(hir_id).unwrap()
+    }
+
+    /// Retrieves the `Node` corresponding to `id`, returning `None` if cannot be found.
+    pub fn find(&self, id: HirId) -> Option<Node<'hir>> {
+        if id.local_id == ItemLocalId::from_u32(0) {
+            let owner = self.tcx.hir_owner(id.owner)?;
+            Some(owner.node)
+        } else {
+            let owner = self.tcx.hir_owner_nodes(id.owner)?;
+            let node = owner.nodes[id.local_id].as_ref()?;
+            Some(node.node)
+        }
+    }
+
+    /// Retrieves the `Node` corresponding to `id`, panicking if it cannot be found.
+    pub fn get(&self, id: HirId) -> Node<'hir> {
+        self.find(id).unwrap_or_else(|| bug!("couldn't find hir id {} in the HIR map", id))
+    }
+
+    pub fn get_if_local(&self, id: DefId) -> Option<Node<'hir>> {
+        id.as_local().and_then(|id| self.find(self.local_def_id_to_hir_id(id)))
+    }
+
+    pub fn get_generics(&self, id: DefId) -> Option<&'hir Generics<'hir>> {
+        self.get_if_local(id).and_then(|node| match &node {
+            Node::ImplItem(impl_item) => Some(&impl_item.generics),
+            Node::TraitItem(trait_item) => Some(&trait_item.generics),
+            Node::Item(Item {
+                kind:
+                    ItemKind::Fn(_, generics, _)
+                    | ItemKind::TyAlias(_, generics)
+                    | ItemKind::Enum(_, generics)
+                    | ItemKind::Struct(_, generics)
+                    | ItemKind::Union(_, generics)
+                    | ItemKind::Trait(_, _, generics, ..)
+                    | ItemKind::TraitAlias(generics, _)
+                    | ItemKind::Impl(Impl { generics, .. }),
+                ..
+            }) => Some(generics),
+            _ => None,
+        })
     }
 
     pub fn item(&self, id: ItemId) -> &'hir Item<'hir> {
@@ -436,7 +502,7 @@ impl<'hir> Map<'hir> {
 
     pub fn get_module(&self, module: LocalDefId) -> (&'hir Mod<'hir>, Span, HirId) {
         let hir_id = self.local_def_id_to_hir_id(module);
-        match self.get_entry(hir_id).node {
+        match self.get(hir_id) {
             Node::Item(&Item { span, kind: ItemKind::Mod(ref m), .. }) => (m, span, hir_id),
             Node::Crate(item) => (&item, item.inner, hir_id),
             node => panic!("not a module: {:?}", node),
@@ -475,60 +541,18 @@ impl<'hir> Map<'hir> {
         }
     }
 
-    /// Retrieves the `Node` corresponding to `id`, panicking if it cannot be found.
-    pub fn get(&self, id: HirId) -> Node<'hir> {
-        self.find(id).unwrap_or_else(|| bug!("couldn't find hir id {} in the HIR map", id))
-    }
-
-    pub fn get_if_local(&self, id: DefId) -> Option<Node<'hir>> {
-        id.as_local().and_then(|id| self.find(self.local_def_id_to_hir_id(id)))
-    }
-
-    pub fn get_generics(&self, id: DefId) -> Option<&'hir Generics<'hir>> {
-        self.get_if_local(id).and_then(|node| match &node {
-            Node::ImplItem(impl_item) => Some(&impl_item.generics),
-            Node::TraitItem(trait_item) => Some(&trait_item.generics),
-            Node::Item(Item {
-                kind:
-                    ItemKind::Fn(_, generics, _)
-                    | ItemKind::TyAlias(_, generics)
-                    | ItemKind::Enum(_, generics)
-                    | ItemKind::Struct(_, generics)
-                    | ItemKind::Union(_, generics)
-                    | ItemKind::Trait(_, _, generics, ..)
-                    | ItemKind::TraitAlias(generics, _)
-                    | ItemKind::Impl(Impl { generics, .. }),
-                ..
-            }) => Some(generics),
-            _ => None,
-        })
-    }
-
-    /// Retrieves the `Node` corresponding to `id`, returning `None` if cannot be found.
-    pub fn find(&self, hir_id: HirId) -> Option<Node<'hir>> {
-        self.find_entry(hir_id).map(|entry| entry.node)
-    }
-
-    /// Similar to `get_parent`; returns the parent HIR Id, or just `hir_id` if there
-    /// is no parent. Note that the parent may be `CRATE_HIR_ID`, which is not itself
-    /// present in the map, so passing the return value of `get_parent_node` to
-    /// `get` may in fact panic.
-    /// This function returns the immediate parent in the HIR, whereas `get_parent`
-    /// returns the enclosing item. Note that this might not be the actual parent
-    /// node in the HIR -- some kinds of nodes are not in the map and these will
-    /// never appear as the parent node. Thus, you can always walk the parent nodes
-    /// from a node to the root of the HIR (unless you get back the same ID here,
-    /// which can happen if the ID is not in the map itself or is just weird).
-    pub fn get_parent_node(&self, hir_id: HirId) -> HirId {
-        self.get_entry(hir_id).parent
-    }
-
     /// Returns an iterator for the nodes in the ancestor tree of the `current_id`
     /// until the crate root is reached. Prefer this over your own loop using `get_parent_node`.
     pub fn parent_iter(&self, current_id: HirId) -> ParentHirIterator<'_, 'hir> {
         ParentHirIterator { current_id, map: self }
     }
 
+    /// Returns an iterator for the nodes in the ancestor tree of the `current_id`
+    /// until the crate root is reached. Prefer this over your own loop using `get_parent_node`.
+    pub fn parent_owner_iter(&self, current_id: HirId) -> ParentOwnerIterator<'_, 'hir> {
+        ParentOwnerIterator { current_id, map: self }
+    }
+
     /// Checks if the node is left-hand side of an assignment.
     pub fn is_lhs(&self, id: HirId) -> bool {
         match self.find(self.get_parent_node(id)) {
@@ -549,7 +573,7 @@ impl<'hir> Map<'hir> {
     /// Whether `hir_id` corresponds to a `mod` or a crate.
     pub fn is_hir_id_module(&self, hir_id: HirId) -> bool {
         matches!(
-            self.get_entry(hir_id).node,
+            self.get(hir_id),
             Node::Item(Item { kind: ItemKind::Mod(_), .. }) | Node::Crate(..)
         )
     }
@@ -579,8 +603,8 @@ impl<'hir> Map<'hir> {
     pub fn get_return_block(&self, id: HirId) -> Option<HirId> {
         let mut iter = self.parent_iter(id).peekable();
         let mut ignore_tail = false;
-        if let Some(entry) = self.find_entry(id) {
-            if let Node::Expr(Expr { kind: ExprKind::Ret(_), .. }) = entry.node {
+        if let Some(node) = self.find(id) {
+            if let Node::Expr(Expr { kind: ExprKind::Ret(_), .. }) = node {
                 // When dealing with `return` statements, we don't care about climbing only tail
                 // expressions.
                 ignore_tail = true;
@@ -617,23 +641,23 @@ impl<'hir> Map<'hir> {
     /// in the HIR which is recorded by the map and is an item, either an item
     /// in a module, trait, or impl.
     pub fn get_parent_item(&self, hir_id: HirId) -> HirId {
-        for (hir_id, node) in self.parent_iter(hir_id) {
-            match node {
-                Node::Crate(_)
-                | Node::Item(_)
-                | Node::ForeignItem(_)
-                | Node::TraitItem(_)
-                | Node::ImplItem(_) => return hir_id,
-                _ => {}
+        for (hir_id, node) in self.parent_owner_iter(hir_id) {
+            if let Node::Crate(_)
+            | Node::Item(_)
+            | Node::ForeignItem(_)
+            | Node::TraitItem(_)
+            | Node::ImplItem(_) = node
+            {
+                return hir_id;
             }
         }
-        hir_id
+        CRATE_HIR_ID
     }
 
     /// Returns the `HirId` of `id`'s nearest module parent, or `id` itself if no
     /// module parent is in this map.
     pub(super) fn get_module_parent_node(&self, hir_id: HirId) -> HirId {
-        for (hir_id, node) in self.parent_iter(hir_id) {
+        for (hir_id, node) in self.parent_owner_iter(hir_id) {
             if let Node::Item(&Item { kind: ItemKind::Mod(_), .. }) = node {
                 return hir_id;
             }
@@ -707,12 +731,8 @@ impl<'hir> Map<'hir> {
 
     pub fn get_foreign_abi(&self, hir_id: HirId) -> Abi {
         let parent = self.get_parent_item(hir_id);
-        if let Some(entry) = self.find_entry(parent) {
-            if let Entry {
-                node: Node::Item(Item { kind: ItemKind::ForeignMod { abi, .. }, .. }),
-                ..
-            } = entry
-            {
+        if let Some(node) = self.find(parent) {
+            if let Node::Item(Item { kind: ItemKind::ForeignMod { abi, .. }, .. }) = node {
                 return *abi;
             }
         }
@@ -806,7 +826,7 @@ impl<'hir> Map<'hir> {
     }
 
     pub fn opt_span(&self, hir_id: HirId) -> Option<Span> {
-        let span = match self.find_entry(hir_id)?.node {
+        let span = match self.find(hir_id)? {
             Node::Param(param) => param.span,
             Node::Item(item) => match &item.kind {
                 ItemKind::Fn(sig, _, _) => sig.span,
@@ -855,7 +875,7 @@ impl<'hir> Map<'hir> {
     /// Like `hir.span()`, but includes the body of function items
     /// (instead of just the function header)
     pub fn span_with_body(&self, hir_id: HirId) -> Span {
-        match self.find_entry(hir_id).map(|entry| entry.node) {
+        match self.find(hir_id) {
             Some(Node::TraitItem(item)) => item.span,
             Some(Node::ImplItem(impl_item)) => impl_item.span,
             Some(Node::Item(item)) => item.span,
diff --git a/compiler/rustc_middle/src/hir/mod.rs b/compiler/rustc_middle/src/hir/mod.rs
index c13c8404bae..dd1a985353f 100644
--- a/compiler/rustc_middle/src/hir/mod.rs
+++ b/compiler/rustc_middle/src/hir/mod.rs
@@ -38,10 +38,10 @@ pub struct Owner<'tcx> {
 
 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for Owner<'tcx> {
     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
-        let Owner { parent, node } = self;
+        let Owner { node, parent } = self;
         hcx.while_hashing_hir_bodies(false, |hcx| {
             parent.hash_stable(hcx, hasher);
-            node.hash_stable(hcx, hasher);
+            node.hash_stable(hcx, hasher)
         });
     }
 }