From 4e2a6ac7eae3ff193962421cc3c86e5d8f9a7e31 Mon Sep 17 00:00:00 2001
From: Alexandru Macovei <alexnmaco@gmail.com>
Date: Thu, 1 Apr 2021 14:01:59 +0300
Subject: Avoid duplicating VfsPath in vfs::path_interner::PathInterner by
 using an IndexSet

---
 Cargo.lock                      |  1 +
 crates/vfs/Cargo.toml           |  1 +
 crates/vfs/src/path_interner.rs | 29 ++++++++++++++++-------------
 3 files changed, 18 insertions(+), 13 deletions(-)

diff --git a/Cargo.lock b/Cargo.lock
index e40c12a92..ca0311595 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1867,6 +1867,7 @@ name = "vfs"
 version = "0.0.0"
 dependencies = [
  "fst",
+ "indexmap",
  "paths",
  "rustc-hash",
 ]
diff --git a/crates/vfs/Cargo.toml b/crates/vfs/Cargo.toml
index c318a68f7..894944b18 100644
--- a/crates/vfs/Cargo.toml
+++ b/crates/vfs/Cargo.toml
@@ -14,3 +14,4 @@ rustc-hash = "1.0"
 fst = "0.4"
 
 paths = { path = "../paths", version = "0.0.0" }
+indexmap = "1.6.2"
diff --git a/crates/vfs/src/path_interner.rs b/crates/vfs/src/path_interner.rs
index 2189e5e25..6e049f0d4 100644
--- a/crates/vfs/src/path_interner.rs
+++ b/crates/vfs/src/path_interner.rs
@@ -1,15 +1,22 @@
 //! Maps paths to compact integer ids. We don't care about clearings paths which
 //! no longer exist -- the assumption is total size of paths we ever look at is
 //! not too big.
-use rustc_hash::FxHashMap;
+use std::hash::BuildHasherDefault;
+
+use indexmap::IndexSet;
+use rustc_hash::FxHasher;
 
 use crate::{FileId, VfsPath};
 
 /// Structure to map between [`VfsPath`] and [`FileId`].
-#[derive(Default)]
 pub(crate) struct PathInterner {
-    map: FxHashMap<VfsPath, FileId>,
-    vec: Vec<VfsPath>,
+    map: IndexSet<VfsPath, BuildHasherDefault<FxHasher>>,
+}
+
+impl Default for PathInterner {
+    fn default() -> Self {
+        Self { map: IndexSet::default() }
+    }
 }
 
 impl PathInterner {
@@ -17,7 +24,7 @@ impl PathInterner {
     ///
     /// If `path` does not exists in `self`, returns [`None`].
     pub(crate) fn get(&self, path: &VfsPath) -> Option<FileId> {
-        self.map.get(path).copied()
+        self.map.get_index_of(path).map(|i| FileId(i as u32))
     }
 
     /// Insert `path` in `self`.
@@ -25,13 +32,9 @@ impl PathInterner {
     /// - If `path` already exists in `self`, returns its associated id;
     /// - Else, returns a newly allocated id.
     pub(crate) fn intern(&mut self, path: VfsPath) -> FileId {
-        if let Some(id) = self.get(&path) {
-            return id;
-        }
-        let id = FileId(self.vec.len() as u32);
-        self.map.insert(path.clone(), id);
-        self.vec.push(path);
-        id
+        let (id, _added) = self.map.insert_full(path);
+        assert!(id < u32::MAX as usize);
+        FileId(id as u32)
     }
 
     /// Returns the path corresponding to `id`.
@@ -40,6 +43,6 @@ impl PathInterner {
     ///
     /// Panics if `id` does not exists in `self`.
     pub(crate) fn lookup(&self, id: FileId) -> &VfsPath {
-        &self.vec[id.0 as usize]
+        self.map.get_index(id.0 as usize).unwrap()
     }
 }
-- 
cgit v1.2.3