Auto merge of #74967 - Aaron1011:feature/incr-def-path-table, r=pnkfelix

Implement lazy decoding of DefPathTable during incremental compilation

PR https://github.com/rust-lang/rust/pull/75813 implemented lazy decoding of the `DefPathTable` from crate metadata. However, it requires decoding the entire `DefPathTable` when incremental compilation is active, so that we can map a decoded `DefPathHash` to a `DefId` from an arbitrary crate.

This PR adds support for lazy decoding of dependency `DefPathTable`s when incremental compilation si active.

When we load the incremental cache and dep
graph, we need the ability to map a `DefPathHash` to a `DefId` in the
current compilation session (if the corresponding definition still
exists).

This is accomplished by storing the old `DefId` (that is, the `DefId`
from the previous compilation session) for each `DefPathHash` we need to
remap. Since a `DefPathHash` includes the owning crate, the old crate is
guaranteed to be the right one (if the definition still exists). We then
use the old `DefIndex` as an initial guess, which we validate by
comparing the expected and actual `DefPathHash`es. In most cases,
foreign crates will be completely unchanged, which means that we our
guess will be correct. If our guess is wrong, we fall back to decoding
the entire `DefPathTable` for the foreign crate. This still represents
an improvement over the status quo, since we can skip decoding the
entire `DefPathTable` for other crates (where all of our guesses were
correct).

1 files changed, 52 insertions, 0 deletions

diff --git a/compiler/rustc_metadata/src/rmeta/decoder.rs b/compiler/rustc_metadata/src/rmeta/decoder.rs
index e82449f69fd..f53a4027806 100644
--- a/compiler/rustc_metadata/src/rmeta/decoder.rs
+++ b/compiler/rustc_metadata/src/rmeta/decoder.rs
@@ -77,6 +77,10 @@ crate struct CrateMetadata {
     raw_proc_macros: Option<&'static [ProcMacro]>,
     /// Source maps for code from the crate.
     source_map_import_info: OnceCell<Vec<ImportedSourceFile>>,
+    /// For every definition in this crate, maps its `DefPathHash` to its
+    /// `DefIndex`. See `raw_def_id_to_def_id` for more details about how
+    /// this is used.
+    def_path_hash_map: OnceCell<FxHashMap<DefPathHash, DefIndex>>,
     /// Used for decoding interpret::AllocIds in a cached & thread-safe manner.
     alloc_decoding_state: AllocDecodingState,
     /// The `DepNodeIndex` of the `DepNode` representing this upstream crate.
@@ -1519,6 +1523,53 @@ impl<'a, 'tcx> CrateMetadataRef<'a> {
             .or_insert_with(|| self.root.tables.def_keys.get(self, index).unwrap().decode(self))
     }
 
+    /// Finds the corresponding `DefId` for the provided `DefPathHash`, if it exists.
+    /// This is used by incremental compilation to map a serialized `DefPathHash` to
+    /// its `DefId` in the current session.
+    /// Normally, only one 'main' crate will change between incremental compilation sessions:
+    /// all dependencies will be completely unchanged. In this case, we can avoid
+    /// decoding every `DefPathHash` in the crate, since the `DefIndex` from the previous
+    /// session will still be valid. If our 'guess' is wrong (the `DefIndex` no longer exists,
+    /// or has a different `DefPathHash`, then we need to decode all `DefPathHashes` to determine
+    /// the correct mapping).
+    fn def_path_hash_to_def_id(
+        &self,
+        krate: CrateNum,
+        index_guess: u32,
+        hash: DefPathHash,
+    ) -> Option<DefId> {
+        let def_index_guess = DefIndex::from_u32(index_guess);
+        let old_hash = self
+            .root
+            .tables
+            .def_path_hashes
+            .get(self, def_index_guess)
+            .map(|lazy| lazy.decode(self));
+
+        // Fast path: the definition and its index is unchanged from the
+        // previous compilation session. There is no need to decode anything
+        // else
+        if old_hash == Some(hash) {
+            return Some(DefId { krate, index: def_index_guess });
+        }
+
+        // Slow path: We need to find out the new `DefIndex` of the provided
+        // `DefPathHash`, if its still exists. This requires decoding every `DefPathHash`
+        // stored in this crate.
+        let map = self.cdata.def_path_hash_map.get_or_init(|| {
+            let end_id = self.root.tables.def_path_hashes.size() as u32;
+            let mut map = FxHashMap::with_capacity_and_hasher(end_id as usize, Default::default());
+            for i in 0..end_id {
+                let def_index = DefIndex::from_u32(i);
+                let hash =
+                    self.root.tables.def_path_hashes.get(self, def_index).unwrap().decode(self);
+                map.insert(hash, def_index);
+            }
+            map
+        });
+        map.get(&hash).map(|index| DefId { krate, index: *index })
+    }
+
     // Returns the path leading to the thing with this `id`.
     fn def_path(&self, id: DefIndex) -> DefPath {
         debug!("def_path(cnum={:?}, id={:?})", self.cnum, id);
@@ -1797,6 +1848,7 @@ impl CrateMetadata {
             trait_impls,
             raw_proc_macros,
             source_map_import_info: OnceCell::new(),
+            def_path_hash_map: Default::default(),
             alloc_decoding_state,
             dep_node_index: AtomicCell::new(DepNodeIndex::INVALID),
             cnum,