Auto merge of #89124 - cjgillot:owner-info, r=michaelwoerister

Index and hash HIR as part of lowering

Part of https://github.com/rust-lang/rust/pull/88186
~Based on https://github.com/rust-lang/rust/pull/88880 (see merge commit).~

Once HIR is lowered, it is later indexed by the `index_hir` query and hashed for `crate_hash`. This PR moves those post-processing steps to lowering itself. As a side objective, the HIR crate data structure is refactored as an `IndexVec<LocalDefId, Option<OwnerInfo<'hir>>>` where `OwnerInfo` stores all the relevant information for an HIR owner.

r? `@michaelwoerister`
cc `@petrochenkov`

4 files changed, 503 insertions, 84 deletions

diff --git a/compiler/rustc_ast_lowering/src/expr.rs b/compiler/rustc_ast_lowering/src/expr.rs
index 6027027428e..22f93f50788 100644
--- a/compiler/rustc_ast_lowering/src/expr.rs
+++ b/compiler/rustc_ast_lowering/src/expr.rs
@@ -252,9 +252,10 @@ impl<'hir> LoweringContext<'_, 'hir> {
                     }
                     // Merge attributes into the inner expression.
                     if !e.attrs.is_empty() {
-                        let old_attrs = self.attrs.get(&ex.hir_id).map(|la| *la).unwrap_or(&[]);
+                        let old_attrs =
+                            self.attrs.get(&ex.hir_id.local_id).map(|la| *la).unwrap_or(&[]);
                         self.attrs.insert(
-                            ex.hir_id,
+                            ex.hir_id.local_id,
                             &*self.arena.alloc_from_iter(
                                 e.attrs
                                     .iter()
diff --git a/compiler/rustc_ast_lowering/src/index.rs b/compiler/rustc_ast_lowering/src/index.rs
new file mode 100644
index 00000000000..dc2b1a730fb
--- /dev/null
+++ b/compiler/rustc_ast_lowering/src/index.rs
@@ -0,0 +1,364 @@
+use rustc_data_structures::fx::FxHashMap;
+use rustc_hir as hir;
+use rustc_hir::def_id::LocalDefId;
+use rustc_hir::definitions;
+use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor};
+use rustc_hir::*;
+use rustc_index::vec::{Idx, IndexVec};
+use rustc_session::Session;
+use rustc_span::source_map::SourceMap;
+use rustc_span::{Span, DUMMY_SP};
+
+use std::iter::repeat;
+use tracing::debug;
+
+/// A visitor that walks over the HIR and collects `Node`s into a HIR map.
+pub(super) struct NodeCollector<'a, 'hir> {
+    /// Source map
+    source_map: &'a SourceMap,
+    bodies: &'a IndexVec<ItemLocalId, Option<&'hir Body<'hir>>>,
+
+    /// Outputs
+    nodes: IndexVec<ItemLocalId, Option<ParentedNode<'hir>>>,
+    parenting: FxHashMap<LocalDefId, ItemLocalId>,
+
+    /// The parent of this node
+    parent_node: hir::ItemLocalId,
+
+    owner: LocalDefId,
+
+    definitions: &'a definitions::Definitions,
+}
+
+fn insert_vec_map<K: Idx, V: Clone>(map: &mut IndexVec<K, Option<V>>, k: K, v: V) {
+    let i = k.index();
+    let len = map.len();
+    if i >= len {
+        map.extend(repeat(None).take(i - len + 1));
+    }
+    debug_assert!(map[k].is_none());
+    map[k] = Some(v);
+}
+
+pub(super) fn index_hir<'hir>(
+    sess: &Session,
+    definitions: &definitions::Definitions,
+    item: hir::OwnerNode<'hir>,
+    bodies: &IndexVec<ItemLocalId, Option<&'hir Body<'hir>>>,
+) -> (IndexVec<ItemLocalId, Option<ParentedNode<'hir>>>, FxHashMap<LocalDefId, ItemLocalId>) {
+    let mut nodes = IndexVec::new();
+    // This node's parent should never be accessed: the owner's parent is computed by the
+    // hir_owner_parent query.  Make it invalid (= ItemLocalId::MAX) to force an ICE whenever it is
+    // used.
+    nodes.push(Some(ParentedNode { parent: ItemLocalId::INVALID, node: item.into() }));
+    let mut collector = NodeCollector {
+        source_map: sess.source_map(),
+        definitions,
+        owner: item.def_id(),
+        parent_node: ItemLocalId::new(0),
+        nodes,
+        bodies,
+        parenting: FxHashMap::default(),
+    };
+
+    match item {
+        OwnerNode::Crate(citem) => collector.visit_mod(&citem, citem.inner, hir::CRATE_HIR_ID),
+        OwnerNode::Item(item) => collector.visit_item(item),
+        OwnerNode::TraitItem(item) => collector.visit_trait_item(item),
+        OwnerNode::ImplItem(item) => collector.visit_impl_item(item),
+        OwnerNode::ForeignItem(item) => collector.visit_foreign_item(item),
+    };
+
+    (collector.nodes, collector.parenting)
+}
+
+impl<'a, 'hir> NodeCollector<'a, 'hir> {
+    fn insert(&mut self, span: Span, hir_id: HirId, node: Node<'hir>) {
+        debug_assert_eq!(self.owner, hir_id.owner);
+        debug_assert_ne!(hir_id.local_id.as_u32(), 0);
+
+        // Make sure that the DepNode of some node coincides with the HirId
+        // owner of that node.
+        if cfg!(debug_assertions) {
+            if hir_id.owner != self.owner {
+                panic!(
+                    "inconsistent DepNode at `{:?}` for `{:?}`: \
+                     current_dep_node_owner={} ({:?}), hir_id.owner={} ({:?})",
+                    self.source_map.span_to_diagnostic_string(span),
+                    node,
+                    self.definitions.def_path(self.owner).to_string_no_crate_verbose(),
+                    self.owner,
+                    self.definitions.def_path(hir_id.owner).to_string_no_crate_verbose(),
+                    hir_id.owner,
+                )
+            }
+        }
+
+        insert_vec_map(
+            &mut self.nodes,
+            hir_id.local_id,
+            ParentedNode { parent: self.parent_node, node: node },
+        );
+    }
+
+    fn with_parent<F: FnOnce(&mut Self)>(&mut self, parent_node_id: HirId, f: F) {
+        debug_assert_eq!(parent_node_id.owner, self.owner);
+        let parent_node = self.parent_node;
+        self.parent_node = parent_node_id.local_id;
+        f(self);
+        self.parent_node = parent_node;
+    }
+
+    fn insert_nested(&mut self, item: LocalDefId) {
+        self.parenting.insert(item, self.parent_node);
+    }
+}
+
+impl<'a, 'hir> Visitor<'hir> for NodeCollector<'a, 'hir> {
+    type Map = !;
+
+    /// Because we want to track parent items and so forth, enable
+    /// deep walking so that we walk nested items in the context of
+    /// their outer items.
+
+    fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
+        panic!("`visit_nested_xxx` must be manually implemented in this visitor");
+    }
+
+    fn visit_nested_item(&mut self, item: ItemId) {
+        debug!("visit_nested_item: {:?}", item);
+        self.insert_nested(item.def_id);
+    }
+
+    fn visit_nested_trait_item(&mut self, item_id: TraitItemId) {
+        self.insert_nested(item_id.def_id);
+    }
+
+    fn visit_nested_impl_item(&mut self, item_id: ImplItemId) {
+        self.insert_nested(item_id.def_id);
+    }
+
+    fn visit_nested_foreign_item(&mut self, foreign_id: ForeignItemId) {
+        self.insert_nested(foreign_id.def_id);
+    }
+
+    fn visit_nested_body(&mut self, id: BodyId) {
+        debug_assert_eq!(id.hir_id.owner, self.owner);
+        let body = self.bodies[id.hir_id.local_id].unwrap();
+        self.visit_body(body);
+    }
+
+    fn visit_param(&mut self, param: &'hir Param<'hir>) {
+        let node = Node::Param(param);
+        self.insert(param.pat.span, param.hir_id, node);
+        self.with_parent(param.hir_id, |this| {
+            intravisit::walk_param(this, param);
+        });
+    }
+
+    fn visit_item(&mut self, i: &'hir Item<'hir>) {
+        debug!("visit_item: {:?}", i);
+        debug_assert_eq!(i.def_id, self.owner);
+        self.with_parent(i.hir_id(), |this| {
+            if let ItemKind::Struct(ref struct_def, _) = i.kind {
+                // If this is a tuple or unit-like struct, register the constructor.
+                if let Some(ctor_hir_id) = struct_def.ctor_hir_id() {
+                    this.insert(i.span, ctor_hir_id, Node::Ctor(struct_def));
+                }
+            }
+            intravisit::walk_item(this, i);
+        });
+    }
+
+    fn visit_foreign_item(&mut self, fi: &'hir ForeignItem<'hir>) {
+        debug_assert_eq!(fi.def_id, self.owner);
+        self.with_parent(fi.hir_id(), |this| {
+            intravisit::walk_foreign_item(this, fi);
+        });
+    }
+
+    fn visit_generic_param(&mut self, param: &'hir GenericParam<'hir>) {
+        self.insert(param.span, param.hir_id, Node::GenericParam(param));
+        intravisit::walk_generic_param(self, param);
+    }
+
+    fn visit_const_param_default(&mut self, param: HirId, ct: &'hir AnonConst) {
+        self.with_parent(param, |this| {
+            intravisit::walk_const_param_default(this, ct);
+        })
+    }
+
+    fn visit_trait_item(&mut self, ti: &'hir TraitItem<'hir>) {
+        debug_assert_eq!(ti.def_id, self.owner);
+        self.with_parent(ti.hir_id(), |this| {
+            intravisit::walk_trait_item(this, ti);
+        });
+    }
+
+    fn visit_impl_item(&mut self, ii: &'hir ImplItem<'hir>) {
+        debug_assert_eq!(ii.def_id, self.owner);
+        self.with_parent(ii.hir_id(), |this| {
+            intravisit::walk_impl_item(this, ii);
+        });
+    }
+
+    fn visit_pat(&mut self, pat: &'hir Pat<'hir>) {
+        let node =
+            if let PatKind::Binding(..) = pat.kind { Node::Binding(pat) } else { Node::Pat(pat) };
+        self.insert(pat.span, pat.hir_id, node);
+
+        self.with_parent(pat.hir_id, |this| {
+            intravisit::walk_pat(this, pat);
+        });
+    }
+
+    fn visit_arm(&mut self, arm: &'hir Arm<'hir>) {
+        let node = Node::Arm(arm);
+
+        self.insert(arm.span, arm.hir_id, node);
+
+        self.with_parent(arm.hir_id, |this| {
+            intravisit::walk_arm(this, arm);
+        });
+    }
+
+    fn visit_anon_const(&mut self, constant: &'hir AnonConst) {
+        self.insert(DUMMY_SP, constant.hir_id, Node::AnonConst(constant));
+
+        self.with_parent(constant.hir_id, |this| {
+            intravisit::walk_anon_const(this, constant);
+        });
+    }
+
+    fn visit_expr(&mut self, expr: &'hir Expr<'hir>) {
+        self.insert(expr.span, expr.hir_id, Node::Expr(expr));
+
+        self.with_parent(expr.hir_id, |this| {
+            intravisit::walk_expr(this, expr);
+        });
+    }
+
+    fn visit_stmt(&mut self, stmt: &'hir Stmt<'hir>) {
+        self.insert(stmt.span, stmt.hir_id, Node::Stmt(stmt));
+
+        self.with_parent(stmt.hir_id, |this| {
+            intravisit::walk_stmt(this, stmt);
+        });
+    }
+
+    fn visit_path_segment(&mut self, path_span: Span, path_segment: &'hir PathSegment<'hir>) {
+        if let Some(hir_id) = path_segment.hir_id {
+            self.insert(path_span, hir_id, Node::PathSegment(path_segment));
+        }
+        intravisit::walk_path_segment(self, path_span, path_segment);
+    }
+
+    fn visit_ty(&mut self, ty: &'hir Ty<'hir>) {
+        self.insert(ty.span, ty.hir_id, Node::Ty(ty));
+
+        self.with_parent(ty.hir_id, |this| {
+            intravisit::walk_ty(this, ty);
+        });
+    }
+
+    fn visit_infer(&mut self, inf: &'hir InferArg) {
+        self.insert(inf.span, inf.hir_id, Node::Infer(inf));
+
+        self.with_parent(inf.hir_id, |this| {
+            intravisit::walk_inf(this, inf);
+        });
+    }
+
+    fn visit_trait_ref(&mut self, tr: &'hir TraitRef<'hir>) {
+        self.insert(tr.path.span, tr.hir_ref_id, Node::TraitRef(tr));
+
+        self.with_parent(tr.hir_ref_id, |this| {
+            intravisit::walk_trait_ref(this, tr);
+        });
+    }
+
+    fn visit_fn(
+        &mut self,
+        fk: intravisit::FnKind<'hir>,
+        fd: &'hir FnDecl<'hir>,
+        b: BodyId,
+        s: Span,
+        id: HirId,
+    ) {
+        assert_eq!(self.owner, id.owner);
+        assert_eq!(self.parent_node, id.local_id);
+        intravisit::walk_fn(self, fk, fd, b, s, id);
+    }
+
+    fn visit_block(&mut self, block: &'hir Block<'hir>) {
+        self.insert(block.span, block.hir_id, Node::Block(block));
+        self.with_parent(block.hir_id, |this| {
+            intravisit::walk_block(this, block);
+        });
+    }
+
+    fn visit_local(&mut self, l: &'hir Local<'hir>) {
+        self.insert(l.span, l.hir_id, Node::Local(l));
+        self.with_parent(l.hir_id, |this| {
+            intravisit::walk_local(this, l);
+        })
+    }
+
+    fn visit_lifetime(&mut self, lifetime: &'hir Lifetime) {
+        self.insert(lifetime.span, lifetime.hir_id, Node::Lifetime(lifetime));
+    }
+
+    fn visit_vis(&mut self, visibility: &'hir Visibility<'hir>) {
+        match visibility.node {
+            VisibilityKind::Public | VisibilityKind::Crate(_) | VisibilityKind::Inherited => {}
+            VisibilityKind::Restricted { hir_id, .. } => {
+                self.insert(visibility.span, hir_id, Node::Visibility(visibility));
+                self.with_parent(hir_id, |this| {
+                    intravisit::walk_vis(this, visibility);
+                });
+            }
+        }
+    }
+
+    fn visit_variant(&mut self, v: &'hir Variant<'hir>, g: &'hir Generics<'hir>, item_id: HirId) {
+        self.insert(v.span, v.id, Node::Variant(v));
+        self.with_parent(v.id, |this| {
+            // Register the constructor of this variant.
+            if let Some(ctor_hir_id) = v.data.ctor_hir_id() {
+                this.insert(v.span, ctor_hir_id, Node::Ctor(&v.data));
+            }
+            intravisit::walk_variant(this, v, g, item_id);
+        });
+    }
+
+    fn visit_field_def(&mut self, field: &'hir FieldDef<'hir>) {
+        self.insert(field.span, field.hir_id, Node::Field(field));
+        self.with_parent(field.hir_id, |this| {
+            intravisit::walk_field_def(this, field);
+        });
+    }
+
+    fn visit_trait_item_ref(&mut self, ii: &'hir TraitItemRef) {
+        // Do not visit the duplicate information in TraitItemRef. We want to
+        // map the actual nodes, not the duplicate ones in the *Ref.
+        let TraitItemRef { id, ident: _, kind: _, span: _, defaultness: _ } = *ii;
+
+        self.visit_nested_trait_item(id);
+    }
+
+    fn visit_impl_item_ref(&mut self, ii: &'hir ImplItemRef) {
+        // Do not visit the duplicate information in ImplItemRef. We want to
+        // map the actual nodes, not the duplicate ones in the *Ref.
+        let ImplItemRef { id, ident: _, kind: _, span: _, defaultness: _ } = *ii;
+
+        self.visit_nested_impl_item(id);
+    }
+
+    fn visit_foreign_item_ref(&mut self, fi: &'hir ForeignItemRef) {
+        // Do not visit the duplicate information in ForeignItemRef. We want to
+        // map the actual nodes, not the duplicate ones in the *Ref.
+        let ForeignItemRef { id, ident: _, span: _ } = *fi;
+
+        self.visit_nested_foreign_item(id);
+    }
+}
diff --git a/compiler/rustc_ast_lowering/src/item.rs b/compiler/rustc_ast_lowering/src/item.rs
index a5a4de81f12..e8747f2c5f8 100644
--- a/compiler/rustc_ast_lowering/src/item.rs
+++ b/compiler/rustc_ast_lowering/src/item.rs
@@ -10,6 +10,7 @@ use rustc_errors::struct_span_err;
 use rustc_hir as hir;
 use rustc_hir::def::{DefKind, Res};
 use rustc_hir::def_id::LocalDefId;
+use rustc_index::vec::Idx;
 use rustc_span::source_map::{respan, DesugaringKind};
 use rustc_span::symbol::{kw, sym, Ident};
 use rustc_span::Span;
@@ -99,11 +100,12 @@ impl<'hir> LoweringContext<'_, 'hir> {
     ) -> T {
         let old_len = self.in_scope_lifetimes.len();
 
-        let parent_generics = match self.owners[parent_hir_id].unwrap().expect_item().kind {
-            hir::ItemKind::Impl(hir::Impl { ref generics, .. })
-            | hir::ItemKind::Trait(_, _, ref generics, ..) => generics.params,
-            _ => &[],
-        };
+        let parent_generics =
+            match self.owners[parent_hir_id].as_ref().unwrap().node().expect_item().kind {
+                hir::ItemKind::Impl(hir::Impl { ref generics, .. })
+                | hir::ItemKind::Trait(_, _, ref generics, ..) => generics.params,
+                _ => &[],
+            };
         let lt_def_names = parent_generics.iter().filter_map(|param| match param.kind {
             hir::GenericParamKind::Lifetime { .. } => Some(param.name.normalize_to_macros_2_0()),
             _ => None,
@@ -493,7 +495,7 @@ impl<'hir> LoweringContext<'_, 'hir> {
                         let kind = hir::ItemKind::Use(path, hir::UseKind::Single);
                         let vis = this.rebuild_vis(&vis);
                         if let Some(attrs) = attrs {
-                            this.attrs.insert(hir::HirId::make_owner(new_id), attrs);
+                            this.attrs.insert(hir::ItemLocalId::new(0), attrs);
                         }
 
                         let item = hir::Item {
@@ -568,7 +570,7 @@ impl<'hir> LoweringContext<'_, 'hir> {
                         let kind =
                             this.lower_use_tree(use_tree, &prefix, id, &mut vis, &mut ident, attrs);
                         if let Some(attrs) = attrs {
-                            this.attrs.insert(hir::HirId::make_owner(new_hir_id), attrs);
+                            this.attrs.insert(hir::ItemLocalId::new(0), attrs);
                         }
 
                         let item = hir::Item {
@@ -971,7 +973,9 @@ impl<'hir> LoweringContext<'_, 'hir> {
     ) -> hir::BodyId {
         let body = hir::Body { generator_kind: self.generator_kind, params, value };
         let id = body.id();
-        self.bodies.insert(id, body);
+        debug_assert_eq!(id.hir_id.owner, self.current_hir_id_owner);
+        self.bodies.ensure_contains_elem(id.hir_id.local_id, || None);
+        self.bodies[id.hir_id.local_id] = Some(self.arena.alloc(body));
         id
     }
 
@@ -1124,7 +1128,7 @@ impl<'hir> LoweringContext<'_, 'hir> {
                 //
                 // If this is the simple case, this parameter will end up being the same as the
                 // original parameter, but with a different pattern id.
-                let stmt_attrs = this.attrs.get(&parameter.hir_id).copied();
+                let stmt_attrs = this.attrs.get(&parameter.hir_id.local_id).copied();
                 let (new_parameter_pat, new_parameter_id) = this.pat_ident(desugared_span, ident);
                 let new_parameter = hir::Param {
                     hir_id: parameter.hir_id,
diff --git a/compiler/rustc_ast_lowering/src/lib.rs b/compiler/rustc_ast_lowering/src/lib.rs
index 92b482e90ee..92e08da7a97 100644
--- a/compiler/rustc_ast_lowering/src/lib.rs
+++ b/compiler/rustc_ast_lowering/src/lib.rs
@@ -33,16 +33,18 @@
 #![feature(crate_visibility_modifier)]
 #![feature(box_patterns)]
 #![feature(iter_zip)]
+#![feature(never_type)]
 #![recursion_limit = "256"]
 
-use rustc_ast::node_id::NodeMap;
 use rustc_ast::token::{self, Token};
 use rustc_ast::tokenstream::{CanSynthesizeMissingTokens, TokenStream, TokenTree};
 use rustc_ast::visit;
 use rustc_ast::{self as ast, *};
 use rustc_ast_pretty::pprust;
 use rustc_data_structures::captures::Captures;
-use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::fingerprint::Fingerprint;
+use rustc_data_structures::fx::FxHashSet;
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_data_structures::sync::Lrc;
 use rustc_errors::{struct_span_err, Applicability};
 use rustc_hir as hir;
@@ -52,13 +54,14 @@ use rustc_hir::definitions::{DefKey, DefPathData, Definitions};
 use rustc_hir::intravisit;
 use rustc_hir::{ConstArg, GenericArg, InferKind, ParamName};
 use rustc_index::vec::{Idx, IndexVec};
+use rustc_query_system::ich::StableHashingContext;
 use rustc_session::lint::builtin::BARE_TRAIT_OBJECTS;
 use rustc_session::lint::{BuiltinLintDiagnostics, LintBuffer};
 use rustc_session::utils::{FlattenNonterminals, NtToTokenstream};
 use rustc_session::Session;
 use rustc_span::edition::Edition;
 use rustc_span::hygiene::ExpnId;
-use rustc_span::source_map::{respan, CachingSourceMapView, DesugaringKind};
+use rustc_span::source_map::{respan, DesugaringKind};
 use rustc_span::symbol::{kw, sym, Ident, Symbol};
 use rustc_span::{Span, DUMMY_SP};
 
@@ -76,6 +79,7 @@ macro_rules! arena_vec {
 mod asm;
 mod block;
 mod expr;
+mod index;
 mod item;
 mod pat;
 mod path;
@@ -97,13 +101,14 @@ struct LoweringContext<'a, 'hir: 'a> {
     arena: &'hir Arena<'hir>,
 
     /// The items being lowered are collected here.
-    owners: IndexVec<LocalDefId, Option<hir::OwnerNode<'hir>>>,
-    bodies: BTreeMap<hir::BodyId, hir::Body<'hir>>,
+    owners: IndexVec<LocalDefId, Option<hir::OwnerInfo<'hir>>>,
+    /// Bodies inside the owner being lowered.
+    bodies: IndexVec<hir::ItemLocalId, Option<&'hir hir::Body<'hir>>>,
+    /// Attributes inside the owner being lowered.
+    attrs: BTreeMap<hir::ItemLocalId, &'hir [Attribute]>,
 
     generator_kind: Option<hir::GeneratorKind>,
 
-    attrs: BTreeMap<hir::HirId, &'hir [Attribute]>,
-
     /// When inside an `async` context, this is the `HirId` of the
     /// `task_context` local bound to the resume argument of the generator.
     task_context: Option<hir::HirId>,
@@ -152,6 +157,9 @@ struct LoweringContext<'a, 'hir: 'a> {
     item_local_id_counter: hir::ItemLocalId,
     node_id_to_hir_id: IndexVec<NodeId, Option<hir::HirId>>,
 
+    /// NodeIds that are lowered inside the current HIR owner.
+    local_node_ids: Vec<NodeId>,
+
     allow_try_trait: Option<Lrc<[Symbol]>>,
     allow_gen_future: Option<Lrc<[Symbol]>>,
 }
@@ -178,11 +186,13 @@ pub trait ResolverAstLowering {
     /// This should only return `None` during testing.
     fn definitions(&mut self) -> &mut Definitions;
 
+    fn create_stable_hashing_context(&self) -> StableHashingContext<'_>;
+
     fn lint_buffer(&mut self) -> &mut LintBuffer;
 
     fn next_node_id(&mut self) -> NodeId;
 
-    fn take_trait_map(&mut self) -> NodeMap<Vec<hir::TraitCandidate>>;
+    fn take_trait_map(&mut self, node: NodeId) -> Option<Vec<hir::TraitCandidate>>;
 
     fn opt_local_def_id(&self, node: NodeId) -> Option<LocalDefId>;
 
@@ -200,37 +210,6 @@ pub trait ResolverAstLowering {
     ) -> LocalDefId;
 }
 
-struct LoweringHasher<'a> {
-    source_map: CachingSourceMapView<'a>,
-    resolver: &'a dyn ResolverAstLowering,
-}
-
-impl<'a> rustc_span::HashStableContext for LoweringHasher<'a> {
-    #[inline]
-    fn hash_spans(&self) -> bool {
-        true
-    }
-
-    #[inline]
-    fn def_span(&self, id: LocalDefId) -> Span {
-        self.resolver.def_span(id)
-    }
-
-    #[inline]
-    fn def_path_hash(&self, def_id: DefId) -> DefPathHash {
-        self.resolver.def_path_hash(def_id)
-    }
-
-    #[inline]
-    fn span_data_to_lines_and_cols(
-        &mut self,
-        span: &rustc_span::SpanData,
-    ) -> Option<(Lrc<rustc_span::SourceFile>, usize, rustc_span::BytePos, usize, rustc_span::BytePos)>
-    {
-        self.source_map.span_data_to_lines_and_cols(span)
-    }
-}
-
 /// Context of `impl Trait` in code, which determines whether it is allowed in an HIR subtree,
 /// and if so, what meaning it has.
 #[derive(Debug)]
@@ -314,13 +293,14 @@ pub fn lower_crate<'a, 'hir>(
 ) -> &'hir hir::Crate<'hir> {
     let _prof_timer = sess.prof.verbose_generic_activity("hir_lowering");
 
+    let owners = IndexVec::from_fn_n(|_| None, resolver.definitions().def_index_count());
     LoweringContext {
         sess,
         resolver,
         nt_to_tokenstream,
         arena,
-        owners: IndexVec::default(),
-        bodies: BTreeMap::new(),
+        owners,
+        bodies: IndexVec::new(),
         attrs: BTreeMap::default(),
         catch_scope: None,
         loop_scope: None,
@@ -331,6 +311,7 @@ pub fn lower_crate<'a, 'hir>(
         current_hir_id_owner: CRATE_DEF_ID,
         item_local_id_counter: hir::ItemLocalId::new(0),
         node_id_to_hir_id: IndexVec::new(),
+        local_node_ids: Vec::new(),
         generator_kind: None,
         task_context: None,
         current_item: None,
@@ -420,13 +401,7 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
             hir::OwnerNode::Crate(lctx.arena.alloc(module))
         });
 
-        let mut trait_map: FxHashMap<_, FxHashMap<_, _>> = FxHashMap::default();
-        for (k, v) in self.resolver.take_trait_map().into_iter() {
-            if let Some(Some(hir_id)) = self.node_id_to_hir_id.get(k) {
-                let map = trait_map.entry(hir_id.owner).or_default();
-                map.insert(hir_id.local_id, v.into_boxed_slice());
-            }
-        }
+        let hir_hash = self.compute_hir_hash();
 
         let mut def_id_to_hir_id = IndexVec::default();
 
@@ -441,24 +416,29 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
 
         self.resolver.definitions().init_def_id_to_hir_id_mapping(def_id_to_hir_id);
 
-        #[cfg(debug_assertions)]
-        for (&id, attrs) in self.attrs.iter() {
-            // Verify that we do not store empty slices in the map.
-            if attrs.is_empty() {
-                panic!("Stored empty attributes for {:?}", id);
-            }
-        }
-
-        let krate =
-            hir::Crate { owners: self.owners, bodies: self.bodies, trait_map, attrs: self.attrs };
+        let krate = hir::Crate { owners: self.owners, hir_hash };
         self.arena.alloc(krate)
     }
 
-    fn create_stable_hashing_context(&self) -> LoweringHasher<'_> {
-        LoweringHasher {
-            source_map: CachingSourceMapView::new(self.sess.source_map()),
-            resolver: self.resolver,
-        }
+    /// Compute the hash for the HIR of the full crate.
+    /// This hash will then be part of the crate_hash which is stored in the metadata.
+    fn compute_hir_hash(&mut self) -> Fingerprint {
+        let definitions = self.resolver.definitions();
+        let mut hir_body_nodes: Vec<_> = self
+            .owners
+            .iter_enumerated()
+            .filter_map(|(def_id, info)| {
+                let info = info.as_ref()?;
+                let def_path_hash = definitions.def_path_hash(def_id);
+                Some((def_path_hash, info))
+            })
+            .collect();
+        hir_body_nodes.sort_unstable_by_key(|bn| bn.0);
+
+        let mut stable_hasher = StableHasher::new();
+        let mut hcx = self.resolver.create_stable_hashing_context();
+        hir_body_nodes.hash_stable(&mut hcx, &mut stable_hasher);
+        stable_hasher.finish()
     }
 
     fn with_hir_id_owner(
@@ -468,25 +448,91 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
     ) -> LocalDefId {
         let def_id = self.resolver.local_def_id(owner);
 
-        // Always allocate the first `HirId` for the owner itself.
-        let _old = self.node_id_to_hir_id.insert(owner, hir::HirId::make_owner(def_id));
-        debug_assert_eq!(_old, None);
-
+        let current_attrs = std::mem::take(&mut self.attrs);
+        let current_bodies = std::mem::take(&mut self.bodies);
+        let current_node_ids = std::mem::take(&mut self.local_node_ids);
         let current_owner = std::mem::replace(&mut self.current_hir_id_owner, def_id);
         let current_local_counter =
             std::mem::replace(&mut self.item_local_id_counter, hir::ItemLocalId::new(1));
 
+        // Always allocate the first `HirId` for the owner itself.
+        let _old = self.node_id_to_hir_id.insert(owner, hir::HirId::make_owner(def_id));
+        debug_assert_eq!(_old, None);
+        self.local_node_ids.push(owner);
+
         let item = f(self);
+        debug_assert_eq!(def_id, item.def_id());
+        let info = self.make_owner_info(item);
 
+        self.attrs = current_attrs;
+        self.bodies = current_bodies;
+        self.local_node_ids = current_node_ids;
         self.current_hir_id_owner = current_owner;
         self.item_local_id_counter = current_local_counter;
 
-        let _old = self.owners.insert(def_id, item);
+        let _old = self.owners.insert(def_id, info);
         debug_assert!(_old.is_none());
 
         def_id
     }
 
+    fn make_owner_info(&mut self, node: hir::OwnerNode<'hir>) -> hir::OwnerInfo<'hir> {
+        let attrs = std::mem::take(&mut self.attrs);
+        let bodies = std::mem::take(&mut self.bodies);
+        let local_node_ids = std::mem::take(&mut self.local_node_ids);
+        let trait_map = local_node_ids
+            .into_iter()
+            .filter_map(|node_id| {
+                let hir_id = self.node_id_to_hir_id[node_id]?;
+                let traits = self.resolver.take_trait_map(node_id)?;
+                Some((hir_id.local_id, traits.into_boxed_slice()))
+            })
+            .collect();
+
+        #[cfg(debug_assertions)]
+        for (&id, attrs) in attrs.iter() {
+            // Verify that we do not store empty slices in the map.
+            if attrs.is_empty() {
+                panic!("Stored empty attributes for {:?}", id);
+            }
+        }
+
+        let (hash_including_bodies, hash_without_bodies) = self.hash_owner(node, &bodies);
+        let (nodes, parenting) =
+            index::index_hir(self.sess, self.resolver.definitions(), node, &bodies);
+        let nodes = hir::OwnerNodes { hash_including_bodies, hash_without_bodies, nodes, bodies };
+        let attrs = {
+            let mut hcx = self.resolver.create_stable_hashing_context();
+            let mut stable_hasher = StableHasher::new();
+            attrs.hash_stable(&mut hcx, &mut stable_hasher);
+            let hash = stable_hasher.finish();
+            hir::AttributeMap { map: attrs, hash }
+        };
+
+        hir::OwnerInfo { nodes, parenting, attrs, trait_map }
+    }
+
+    /// Hash the HIR node twice, one deep and one shallow hash.  This allows to differentiate
+    /// queries which depend on the full HIR tree and those which only depend on the item signature.
+    fn hash_owner(
+        &mut self,
+        node: hir::OwnerNode<'hir>,
+        bodies: &IndexVec<hir::ItemLocalId, Option<&'hir hir::Body<'hir>>>,
+    ) -> (Fingerprint, Fingerprint) {
+        let mut hcx = self.resolver.create_stable_hashing_context();
+        let mut stable_hasher = StableHasher::new();
+        hcx.with_hir_bodies(true, node.def_id(), bodies, |hcx| {
+            node.hash_stable(hcx, &mut stable_hasher)
+        });
+        let hash_including_bodies = stable_hasher.finish();
+        let mut stable_hasher = StableHasher::new();
+        hcx.with_hir_bodies(false, node.def_id(), bodies, |hcx| {
+            node.hash_stable(hcx, &mut stable_hasher)
+        });
+        let hash_without_bodies = stable_hasher.finish();
+        (hash_including_bodies, hash_without_bodies)
+    }
+
     /// This method allocates a new `HirId` for the given `NodeId` and stores it in
     /// the `LoweringContext`'s `NodeId => HirId` map.
     /// Take care not to call this method if the resulting `HirId` is then not
@@ -501,6 +547,7 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
             let owner = self.current_hir_id_owner;
             let local_id = self.item_local_id_counter;
             self.item_local_id_counter.increment_by(1);
+            self.local_node_ids.push(ast_node_id);
             hir::HirId { owner, local_id }
         })
     }
@@ -547,7 +594,7 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
             allow_internal_unstable,
             reason,
             self.sess.edition(),
-            self.create_stable_hashing_context(),
+            self.resolver.create_stable_hashing_context(),
         )
     }
 
@@ -791,9 +838,10 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
         if attrs.is_empty() {
             None
         } else {
+            debug_assert_eq!(id.owner, self.current_hir_id_owner);
             let ret = self.arena.alloc_from_iter(attrs.iter().map(|a| self.lower_attr(a)));
             debug_assert!(!ret.is_empty());
-            self.attrs.insert(id, ret);
+            self.attrs.insert(id.local_id, ret);
             Some(ret)
         }
     }
@@ -819,9 +867,11 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
     }
 
     fn alias_attrs(&mut self, id: hir::HirId, target_id: hir::HirId) {
-        if let Some(&a) = self.attrs.get(&target_id) {
+        debug_assert_eq!(id.owner, self.current_hir_id_owner);
+        debug_assert_eq!(target_id.owner, self.current_hir_id_owner);
+        if let Some(&a) = self.attrs.get(&target_id.local_id) {
             debug_assert!(!a.is_empty());
-            self.attrs.insert(id, a);
+            self.attrs.insert(id.local_id, a);
         }
     }
 
@@ -2066,7 +2116,7 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
         let hir_id = self.next_id();
         if let Some(a) = attrs {
             debug_assert!(!a.is_empty());
-            self.attrs.insert(hir_id, a);
+            self.attrs.insert(hir_id.local_id, a);
         }
         let local = hir::Local { hir_id, init, pat, source, span: self.lower_span(span), ty: None };
         self.stmt(span, hir::StmtKind::Local(self.arena.alloc(local)))