Merge commit 'aa9bc8612514d216f84eec218dfd19ab83f3598a' into sync-from-ra

5 files changed, 298 insertions, 163 deletions

diff --git a/src/tools/rust-analyzer/crates/base-db/Cargo.toml b/src/tools/rust-analyzer/crates/base-db/Cargo.toml
index f6a1075c190..6001772c86e 100644
--- a/src/tools/rust-analyzer/crates/base-db/Cargo.toml
+++ b/src/tools/rust-analyzer/crates/base-db/Cargo.toml
@@ -15,6 +15,10 @@ doctest = false
 salsa = "0.17.0-pre.2"
 rustc-hash = "1.1.0"
 
+triomphe.workspace = true
+
+la-arena = { version = "0.3.0", path = "../../lib/la-arena" }
+
 # local deps
 cfg.workspace = true
 profile.workspace = true
diff --git a/src/tools/rust-analyzer/crates/base-db/src/change.rs b/src/tools/rust-analyzer/crates/base-db/src/change.rs
index b57f2345767..6a3b36b2312 100644
--- a/src/tools/rust-analyzer/crates/base-db/src/change.rs
+++ b/src/tools/rust-analyzer/crates/base-db/src/change.rs
@@ -1,19 +1,21 @@
 //! Defines a unit of change that can applied to the database to get the next
 //! state. Changes are transactional.
 
-use std::{fmt, sync::Arc};
+use std::fmt;
 
 use salsa::Durability;
+use triomphe::Arc;
 use vfs::FileId;
 
-use crate::{CrateGraph, SourceDatabaseExt, SourceRoot, SourceRootId};
+use crate::{CrateGraph, ProcMacros, SourceDatabaseExt, SourceRoot, SourceRootId};
 
 /// Encapsulate a bunch of raw `.set` calls on the database.
 #[derive(Default)]
 pub struct Change {
     pub roots: Option<Vec<SourceRoot>>,
-    pub files_changed: Vec<(FileId, Option<Arc<String>>)>,
+    pub files_changed: Vec<(FileId, Option<Arc<str>>)>,
     pub crate_graph: Option<CrateGraph>,
+    pub proc_macros: Option<ProcMacros>,
 }
 
 impl fmt::Debug for Change {
@@ -33,7 +35,7 @@ impl fmt::Debug for Change {
 }
 
 impl Change {
-    pub fn new() -> Change {
+    pub fn new() -> Self {
         Change::default()
     }
 
@@ -41,7 +43,7 @@ impl Change {
         self.roots = Some(roots);
     }
 
-    pub fn change_file(&mut self, file_id: FileId, new_text: Option<Arc<String>>) {
+    pub fn change_file(&mut self, file_id: FileId, new_text: Option<Arc<str>>) {
         self.files_changed.push((file_id, new_text))
     }
 
@@ -49,6 +51,10 @@ impl Change {
         self.crate_graph = Some(graph);
     }
 
+    pub fn set_proc_macros(&mut self, proc_macros: ProcMacros) {
+        self.proc_macros = Some(proc_macros);
+    }
+
     pub fn apply(self, db: &mut dyn SourceDatabaseExt) {
         let _p = profile::span("RootDatabase::apply_change");
         if let Some(roots) = self.roots {
@@ -67,11 +73,14 @@ impl Change {
             let source_root = db.source_root(source_root_id);
             let durability = durability(&source_root);
             // XXX: can't actually remove the file, just reset the text
-            let text = text.unwrap_or_default();
+            let text = text.unwrap_or_else(|| Arc::from(""));
             db.set_file_text_with_durability(file_id, text, durability)
         }
         if let Some(crate_graph) = self.crate_graph {
-            db.set_crate_graph_with_durability(Arc::new(crate_graph), Durability::HIGH)
+            db.set_crate_graph_with_durability(Arc::new(crate_graph), Durability::HIGH);
+        }
+        if let Some(proc_macros) = self.proc_macros {
+            db.set_proc_macros_with_durability(Arc::new(proc_macros), Durability::HIGH);
         }
     }
 }
diff --git a/src/tools/rust-analyzer/crates/base-db/src/fixture.rs b/src/tools/rust-analyzer/crates/base-db/src/fixture.rs
index 8a7e9dfadfe..5b11343173b 100644
--- a/src/tools/rust-analyzer/crates/base-db/src/fixture.rs
+++ b/src/tools/rust-analyzer/crates/base-db/src/fixture.rs
@@ -1,24 +1,27 @@
 //! A set of high-level utility fixture methods to use in tests.
-use std::{mem, str::FromStr, sync::Arc};
+use std::{mem, str::FromStr, sync};
 
 use cfg::CfgOptions;
 use rustc_hash::FxHashMap;
 use test_utils::{
-    extract_range_or_offset, Fixture, RangeOrOffset, CURSOR_MARKER, ESCAPED_CURSOR_MARKER,
+    extract_range_or_offset, Fixture, FixtureWithProjectMeta, RangeOrOffset, CURSOR_MARKER,
+    ESCAPED_CURSOR_MARKER,
 };
+use triomphe::Arc;
 use tt::token_id::{Leaf, Subtree, TokenTree};
 use vfs::{file_set::FileSet, VfsPath};
 
 use crate::{
     input::{CrateName, CrateOrigin, LangCrateOrigin},
     Change, CrateDisplayName, CrateGraph, CrateId, Dependency, Edition, Env, FileId, FilePosition,
-    FileRange, ProcMacro, ProcMacroExpander, ProcMacroExpansionError, SourceDatabaseExt,
-    SourceRoot, SourceRootId,
+    FileRange, ProcMacro, ProcMacroExpander, ProcMacroExpansionError, ProcMacros, ReleaseChannel,
+    SourceDatabaseExt, SourceRoot, SourceRootId,
 };
 
 pub const WORKSPACE: SourceRootId = SourceRootId(0);
 
 pub trait WithFixture: Default + SourceDatabaseExt + 'static {
+    #[track_caller]
     fn with_single_file(ra_fixture: &str) -> (Self, FileId) {
         let fixture = ChangeFixture::parse(ra_fixture);
         let mut db = Self::default();
@@ -27,6 +30,7 @@ pub trait WithFixture: Default + SourceDatabaseExt + 'static {
         (db, fixture.files[0])
     }
 
+    #[track_caller]
     fn with_many_files(ra_fixture: &str) -> (Self, Vec<FileId>) {
         let fixture = ChangeFixture::parse(ra_fixture);
         let mut db = Self::default();
@@ -35,6 +39,7 @@ pub trait WithFixture: Default + SourceDatabaseExt + 'static {
         (db, fixture.files)
     }
 
+    #[track_caller]
     fn with_files(ra_fixture: &str) -> Self {
         let fixture = ChangeFixture::parse(ra_fixture);
         let mut db = Self::default();
@@ -43,6 +48,7 @@ pub trait WithFixture: Default + SourceDatabaseExt + 'static {
         db
     }
 
+    #[track_caller]
     fn with_files_extra_proc_macros(
         ra_fixture: &str,
         proc_macros: Vec<(String, ProcMacro)>,
@@ -54,18 +60,21 @@ pub trait WithFixture: Default + SourceDatabaseExt + 'static {
         db
     }
 
+    #[track_caller]
     fn with_position(ra_fixture: &str) -> (Self, FilePosition) {
         let (db, file_id, range_or_offset) = Self::with_range_or_offset(ra_fixture);
         let offset = range_or_offset.expect_offset();
         (db, FilePosition { file_id, offset })
     }
 
+    #[track_caller]
     fn with_range(ra_fixture: &str) -> (Self, FileRange) {
         let (db, file_id, range_or_offset) = Self::with_range_or_offset(ra_fixture);
         let range = range_or_offset.expect_range();
         (db, FileRange { file_id, range })
     }
 
+    #[track_caller]
     fn with_range_or_offset(ra_fixture: &str) -> (Self, FileId, RangeOrOffset) {
         let fixture = ChangeFixture::parse(ra_fixture);
         let mut db = Self::default();
@@ -100,9 +109,16 @@ impl ChangeFixture {
 
     pub fn parse_with_proc_macros(
         ra_fixture: &str,
-        mut proc_macros: Vec<(String, ProcMacro)>,
+        mut proc_macro_defs: Vec<(String, ProcMacro)>,
     ) -> ChangeFixture {
-        let (mini_core, proc_macro_names, fixture) = Fixture::parse(ra_fixture);
+        let FixtureWithProjectMeta { fixture, mini_core, proc_macro_names, toolchain } =
+            FixtureWithProjectMeta::parse(ra_fixture);
+        let toolchain = toolchain
+            .map(|it| {
+                ReleaseChannel::from_str(&it)
+                    .unwrap_or_else(|| panic!("unknown release channel found: {it}"))
+            })
+            .unwrap_or(ReleaseChannel::Stable);
         let mut change = Change::new();
 
         let mut files = Vec::new();
@@ -157,16 +173,16 @@ impl ChangeFixture {
                     meta.edition,
                     Some(crate_name.clone().into()),
                     version,
-                    meta.cfg.clone(),
                     meta.cfg,
+                    Default::default(),
                     meta.env,
-                    Ok(Vec::new()),
                     false,
                     origin,
                     meta.target_data_layout
                         .as_deref()
                         .map(Arc::from)
                         .ok_or_else(|| "target_data_layout unset".into()),
+                    Some(toolchain),
                 );
                 let prev = crates.insert(crate_name.clone(), crate_id);
                 assert!(prev.is_none());
@@ -182,7 +198,7 @@ impl ChangeFixture {
                 default_target_data_layout = meta.target_data_layout;
             }
 
-            change.change_file(file_id, Some(Arc::new(text)));
+            change.change_file(file_id, Some(Arc::from(text)));
             let path = VfsPath::new_virtual_path(meta.path);
             file_set.insert(file_id, path);
             files.push(file_id);
@@ -197,15 +213,15 @@ impl ChangeFixture {
                 Edition::CURRENT,
                 Some(CrateName::new("test").unwrap().into()),
                 None,
-                default_cfg.clone(),
                 default_cfg,
+                Default::default(),
                 Env::default(),
-                Ok(Vec::new()),
                 false,
-                CrateOrigin::CratesIo { repo: None, name: None },
+                CrateOrigin::Local { repo: None, name: None },
                 default_target_data_layout
                     .map(|x| x.into())
                     .ok_or_else(|| "target_data_layout unset".into()),
+                Some(toolchain),
             );
         } else {
             for (from, to, prelude) in crate_deps {
@@ -232,7 +248,7 @@ impl ChangeFixture {
             fs.insert(core_file, VfsPath::new_virtual_path("/sysroot/core/lib.rs".to_string()));
             roots.push(SourceRoot::new_library(fs));
 
-            change.change_file(core_file, Some(Arc::new(mini_core.source_code())));
+            change.change_file(core_file, Some(Arc::from(mini_core.source_code())));
 
             let all_crates = crate_graph.crates_in_topological_order();
 
@@ -241,13 +257,13 @@ impl ChangeFixture {
                 Edition::Edition2021,
                 Some(CrateDisplayName::from_canonical_name("core".to_string())),
                 None,
-                CfgOptions::default(),
-                CfgOptions::default(),
+                Default::default(),
+                Default::default(),
                 Env::default(),
-                Ok(Vec::new()),
                 false,
                 CrateOrigin::Lang(LangCrateOrigin::Core),
                 target_layout.clone(),
+                Some(toolchain),
             );
 
             for krate in all_crates {
@@ -257,12 +273,13 @@ impl ChangeFixture {
             }
         }
 
+        let mut proc_macros = ProcMacros::default();
         if !proc_macro_names.is_empty() {
             let proc_lib_file = file_id;
             file_id.0 += 1;
 
-            proc_macros.extend(default_test_proc_macros());
-            let (proc_macro, source) = filter_test_proc_macros(&proc_macro_names, proc_macros);
+            proc_macro_defs.extend(default_test_proc_macros());
+            let (proc_macro, source) = filter_test_proc_macros(&proc_macro_names, proc_macro_defs);
             let mut fs = FileSet::default();
             fs.insert(
                 proc_lib_file,
@@ -270,7 +287,7 @@ impl ChangeFixture {
             );
             roots.push(SourceRoot::new_library(fs));
 
-            change.change_file(proc_lib_file, Some(Arc::new(source)));
+            change.change_file(proc_lib_file, Some(Arc::from(source)));
 
             let all_crates = crate_graph.crates_in_topological_order();
 
@@ -279,14 +296,15 @@ impl ChangeFixture {
                 Edition::Edition2021,
                 Some(CrateDisplayName::from_canonical_name("proc_macros".to_string())),
                 None,
-                CfgOptions::default(),
-                CfgOptions::default(),
+                Default::default(),
+                Default::default(),
                 Env::default(),
-                Ok(proc_macro),
                 true,
-                CrateOrigin::CratesIo { repo: None, name: None },
+                CrateOrigin::Local { repo: None, name: None },
                 target_layout,
+                Some(toolchain),
             );
+            proc_macros.insert(proc_macros_crate, Ok(proc_macro));
 
             for krate in all_crates {
                 crate_graph
@@ -305,6 +323,7 @@ impl ChangeFixture {
         roots.push(root);
         change.set_roots(roots);
         change.set_crate_graph(crate_graph);
+        change.set_proc_macros(proc_macros);
 
         ChangeFixture { file_position, files, change }
     }
@@ -323,7 +342,7 @@ pub fn identity(_attr: TokenStream, item: TokenStream) -> TokenStream {
             ProcMacro {
                 name: "identity".into(),
                 kind: crate::ProcMacroKind::Attr,
-                expander: Arc::new(IdentityProcMacroExpander),
+                expander: sync::Arc::new(IdentityProcMacroExpander),
             },
         ),
         (
@@ -337,7 +356,7 @@ pub fn derive_identity(item: TokenStream) -> TokenStream {
             ProcMacro {
                 name: "DeriveIdentity".into(),
                 kind: crate::ProcMacroKind::CustomDerive,
-                expander: Arc::new(IdentityProcMacroExpander),
+                expander: sync::Arc::new(IdentityProcMacroExpander),
             },
         ),
         (
@@ -351,7 +370,7 @@ pub fn input_replace(attr: TokenStream, _item: TokenStream) -> TokenStream {
             ProcMacro {
                 name: "input_replace".into(),
                 kind: crate::ProcMacroKind::Attr,
-                expander: Arc::new(AttributeInputReplaceProcMacroExpander),
+                expander: sync::Arc::new(AttributeInputReplaceProcMacroExpander),
             },
         ),
         (
@@ -365,7 +384,7 @@ pub fn mirror(input: TokenStream) -> TokenStream {
             ProcMacro {
                 name: "mirror".into(),
                 kind: crate::ProcMacroKind::FuncLike,
-                expander: Arc::new(MirrorProcMacroExpander),
+                expander: sync::Arc::new(MirrorProcMacroExpander),
             },
         ),
         (
@@ -379,7 +398,7 @@ pub fn shorten(input: TokenStream) -> TokenStream {
             ProcMacro {
                 name: "shorten".into(),
                 kind: crate::ProcMacroKind::FuncLike,
-                expander: Arc::new(ShortenProcMacroExpander),
+                expander: sync::Arc::new(ShortenProcMacroExpander),
             },
         ),
     ]
@@ -428,7 +447,7 @@ fn parse_crate(crate_str: String) -> (String, CrateOrigin, Option<String>) {
         let (version, origin) = match b.split_once(':') {
             Some(("CratesIo", data)) => match data.split_once(',') {
                 Some((version, url)) => {
-                    (version, CrateOrigin::CratesIo { repo: Some(url.to_owned()), name: None })
+                    (version, CrateOrigin::Local { repo: Some(url.to_owned()), name: None })
                 }
                 _ => panic!("Bad crates.io parameter: {data}"),
             },
@@ -436,10 +455,9 @@ fn parse_crate(crate_str: String) -> (String, CrateOrigin, Option<String>) {
         };
         (a.to_owned(), origin, Some(version.to_string()))
     } else {
-        let crate_origin = match &*crate_str {
-            "std" => CrateOrigin::Lang(LangCrateOrigin::Std),
-            "core" => CrateOrigin::Lang(LangCrateOrigin::Core),
-            _ => CrateOrigin::CratesIo { repo: None, name: None },
+        let crate_origin = match LangCrateOrigin::from(&*crate_str) {
+            LangCrateOrigin::Other => CrateOrigin::Local { repo: None, name: None },
+            origin => CrateOrigin::Lang(origin),
         };
         (crate_str, crate_origin, None)
     }
diff --git a/src/tools/rust-analyzer/crates/base-db/src/input.rs b/src/tools/rust-analyzer/crates/base-db/src/input.rs
index 43388e915b5..e8d521b42f8 100644
--- a/src/tools/rust-analyzer/crates/base-db/src/input.rs
+++ b/src/tools/rust-analyzer/crates/base-db/src/input.rs
@@ -6,14 +6,20 @@
 //! actual IO. See `vfs` and `project_model` in the `rust-analyzer` crate for how
 //! actual IO is done and lowered to input.
 
-use std::{fmt, ops, panic::RefUnwindSafe, str::FromStr, sync::Arc};
+use std::{fmt, mem, ops, panic::RefUnwindSafe, str::FromStr, sync};
 
 use cfg::CfgOptions;
-use rustc_hash::FxHashMap;
-use stdx::hash::{NoHashHashMap, NoHashHashSet};
+use la_arena::{Arena, Idx};
+use rustc_hash::{FxHashMap, FxHashSet};
 use syntax::SmolStr;
+use triomphe::Arc;
 use tt::token_id::Subtree;
-use vfs::{file_set::FileSet, AnchoredPath, FileId, VfsPath};
+use vfs::{file_set::FileSet, AbsPathBuf, AnchoredPath, FileId, VfsPath};
+
+// Map from crate id to the name of the crate and path of the proc-macro. If the value is `None`,
+// then the crate for the proc-macro hasn't been build yet as the build data is missing.
+pub type ProcMacroPaths = FxHashMap<CrateId, Result<(Option<String>, AbsPathBuf), String>>;
+pub type ProcMacros = FxHashMap<CrateId, ProcMacroLoadResult>;
 
 /// Files are grouped into source roots. A source root is a directory on the
 /// file systems which is watched for changes. Typically it corresponds to a
@@ -79,17 +85,22 @@ impl SourceRoot {
 ///
 /// `CrateGraph` is `!Serialize` by design, see
 /// <https://github.com/rust-lang/rust-analyzer/blob/master/docs/dev/architecture.md#serialization>
-#[derive(Debug, Clone, Default /* Serialize, Deserialize */)]
+#[derive(Clone, Default)]
 pub struct CrateGraph {
-    arena: NoHashHashMap<CrateId, CrateData>,
+    arena: Arena<CrateData>,
 }
 
-#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
-pub struct CrateId(pub u32);
+impl fmt::Debug for CrateGraph {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_map()
+            .entries(self.arena.iter().map(|(id, data)| (u32::from(id.into_raw()), data)))
+            .finish()
+    }
+}
 
-impl stdx::hash::NoHashHashable for CrateId {}
+pub type CrateId = Idx<CrateData>;
 
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
 pub struct CrateName(SmolStr);
 
 impl CrateName {
@@ -130,8 +141,12 @@ impl ops::Deref for CrateName {
 /// Origin of the crates. It is used in emitting monikers.
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub enum CrateOrigin {
-    /// Crates that are from crates.io official registry,
-    CratesIo { repo: Option<String>, name: Option<String> },
+    /// Crates that are from the rustc workspace
+    Rustc { name: String },
+    /// Crates that are workspace members,
+    Local { repo: Option<String>, name: Option<String> },
+    /// Crates that are non member libraries.
+    Library { repo: Option<String>, name: String },
     /// Crates that are provided by the language, like std, core, proc-macro, ...
     Lang(LangCrateOrigin),
 }
@@ -173,7 +188,7 @@ impl fmt::Display for LangCrateOrigin {
     }
 }
 
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
 pub struct CrateDisplayName {
     // The name we use to display various paths (with `_`).
     crate_name: CrateName,
@@ -249,10 +264,36 @@ pub type TargetLayoutLoadResult = Result<Arc<str>, Arc<str>>;
 pub struct ProcMacro {
     pub name: SmolStr,
     pub kind: ProcMacroKind,
-    pub expander: Arc<dyn ProcMacroExpander>,
+    pub expander: sync::Arc<dyn ProcMacroExpander>,
 }
 
-#[derive(Debug, Clone)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
+pub enum ReleaseChannel {
+    Stable,
+    Beta,
+    Nightly,
+}
+
+impl ReleaseChannel {
+    pub fn as_str(self) -> &'static str {
+        match self {
+            ReleaseChannel::Stable => "stable",
+            ReleaseChannel::Beta => "beta",
+            ReleaseChannel::Nightly => "nightly",
+        }
+    }
+
+    pub fn from_str(str: &str) -> Option<Self> {
+        Some(match str {
+            "" => ReleaseChannel::Stable,
+            "nightly" => ReleaseChannel::Nightly,
+            _ if str.starts_with("beta") => ReleaseChannel::Beta,
+            _ => return None,
+        })
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
 pub struct CrateData {
     pub root_file_id: FileId,
     pub edition: Edition,
@@ -265,13 +306,15 @@ pub struct CrateData {
     /// `Dependency` matters), this name should only be used for UI.
     pub display_name: Option<CrateDisplayName>,
     pub cfg_options: CfgOptions,
-    pub potential_cfg_options: CfgOptions,
-    pub target_layout: TargetLayoutLoadResult,
+    /// The cfg options that could be used by the crate
+    pub potential_cfg_options: Option<CfgOptions>,
     pub env: Env,
     pub dependencies: Vec<Dependency>,
-    pub proc_macro: ProcMacroLoadResult,
     pub origin: CrateOrigin,
     pub is_proc_macro: bool,
+    // FIXME: These things should not be per crate! These are more per workspace crate graph level things
+    pub target_layout: TargetLayoutLoadResult,
+    pub channel: Option<ReleaseChannel>,
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
@@ -290,7 +333,7 @@ pub struct Env {
     entries: FxHashMap<String, String>,
 }
 
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct Dependency {
     pub crate_id: CrateId,
     pub name: CrateName,
@@ -320,12 +363,12 @@ impl CrateGraph {
         display_name: Option<CrateDisplayName>,
         version: Option<String>,
         cfg_options: CfgOptions,
-        potential_cfg_options: CfgOptions,
+        potential_cfg_options: Option<CfgOptions>,
         env: Env,
-        proc_macro: ProcMacroLoadResult,
         is_proc_macro: bool,
         origin: CrateOrigin,
         target_layout: Result<Arc<str>, Arc<str>>,
+        channel: Option<ReleaseChannel>,
     ) -> CrateId {
         let data = CrateData {
             root_file_id,
@@ -335,16 +378,44 @@ impl CrateGraph {
             cfg_options,
             potential_cfg_options,
             env,
-            proc_macro,
             dependencies: Vec::new(),
             origin,
             target_layout,
             is_proc_macro,
+            channel,
         };
-        let crate_id = CrateId(self.arena.len() as u32);
-        let prev = self.arena.insert(crate_id, data);
-        assert!(prev.is_none());
-        crate_id
+        self.arena.alloc(data)
+    }
+
+    /// Remove the crate from crate graph. If any crates depend on this crate, the dependency would be replaced
+    /// with the second input.
+    pub fn remove_and_replace(
+        &mut self,
+        id: CrateId,
+        replace_with: CrateId,
+    ) -> Result<(), CyclicDependenciesError> {
+        for (x, data) in self.arena.iter() {
+            if x == id {
+                continue;
+            }
+            for edge in &data.dependencies {
+                if edge.crate_id == id {
+                    self.check_cycle_after_dependency(edge.crate_id, replace_with)?;
+                }
+            }
+        }
+        // if everything was ok, start to replace
+        for (x, data) in self.arena.iter_mut() {
+            if x == id {
+                continue;
+            }
+            for edge in &mut data.dependencies {
+                if edge.crate_id == id {
+                    edge.crate_id = replace_with;
+                }
+            }
+        }
+        Ok(())
     }
 
     pub fn add_dep(
@@ -354,17 +425,26 @@ impl CrateGraph {
     ) -> Result<(), CyclicDependenciesError> {
         let _p = profile::span("add_dep");
 
-        // Check if adding a dep from `from` to `to` creates a cycle. To figure
-        // that out, look for a  path in the *opposite* direction, from `to` to
-        // `from`.
-        if let Some(path) = self.find_path(&mut NoHashHashSet::default(), dep.crate_id, from) {
+        self.check_cycle_after_dependency(from, dep.crate_id)?;
+
+        self.arena[from].add_dep(dep);
+        Ok(())
+    }
+
+    /// Check if adding a dep from `from` to `to` creates a cycle. To figure
+    /// that out, look for a  path in the *opposite* direction, from `to` to
+    /// `from`.
+    fn check_cycle_after_dependency(
+        &self,
+        from: CrateId,
+        to: CrateId,
+    ) -> Result<(), CyclicDependenciesError> {
+        if let Some(path) = self.find_path(&mut FxHashSet::default(), to, from) {
             let path = path.into_iter().map(|it| (it, self[it].display_name.clone())).collect();
             let err = CyclicDependenciesError { path };
-            assert!(err.from().0 == from && err.to().0 == dep.crate_id);
+            assert!(err.from().0 == from && err.to().0 == to);
             return Err(err);
         }
-
-        self.arena.get_mut(&from).unwrap().add_dep(dep);
         Ok(())
     }
 
@@ -373,14 +453,14 @@ impl CrateGraph {
     }
 
     pub fn iter(&self) -> impl Iterator<Item = CrateId> + '_ {
-        self.arena.keys().copied()
+        self.arena.iter().map(|(idx, _)| idx)
     }
 
     /// Returns an iterator over all transitive dependencies of the given crate,
     /// including the crate itself.
     pub fn transitive_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> {
         let mut worklist = vec![of];
-        let mut deps = NoHashHashSet::default();
+        let mut deps = FxHashSet::default();
 
         while let Some(krate) = worklist.pop() {
             if !deps.insert(krate) {
@@ -397,11 +477,11 @@ impl CrateGraph {
     /// including the crate itself.
     pub fn transitive_rev_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> {
         let mut worklist = vec![of];
-        let mut rev_deps = NoHashHashSet::default();
+        let mut rev_deps = FxHashSet::default();
         rev_deps.insert(of);
 
-        let mut inverted_graph = NoHashHashMap::<_, Vec<_>>::default();
-        self.arena.iter().for_each(|(&krate, data)| {
+        let mut inverted_graph = FxHashMap::<_, Vec<_>>::default();
+        self.arena.iter().for_each(|(krate, data)| {
             data.dependencies
                 .iter()
                 .for_each(|dep| inverted_graph.entry(dep.crate_id).or_default().push(krate))
@@ -424,9 +504,9 @@ impl CrateGraph {
     /// come before the crate itself).
     pub fn crates_in_topological_order(&self) -> Vec<CrateId> {
         let mut res = Vec::new();
-        let mut visited = NoHashHashSet::default();
+        let mut visited = FxHashSet::default();
 
-        for krate in self.arena.keys().copied() {
+        for krate in self.iter() {
             go(self, &mut visited, &mut res, krate);
         }
 
@@ -434,7 +514,7 @@ impl CrateGraph {
 
         fn go(
             graph: &CrateGraph,
-            visited: &mut NoHashHashSet<CrateId>,
+            visited: &mut FxHashSet<CrateId>,
             res: &mut Vec<CrateId>,
             source: CrateId,
         ) {
@@ -450,31 +530,56 @@ impl CrateGraph {
 
     // FIXME: this only finds one crate with the given root; we could have multiple
     pub fn crate_id_for_crate_root(&self, file_id: FileId) -> Option<CrateId> {
-        let (&crate_id, _) =
+        let (crate_id, _) =
             self.arena.iter().find(|(_crate_id, data)| data.root_file_id == file_id)?;
         Some(crate_id)
     }
 
+    pub fn sort_deps(&mut self) {
+        self.arena
+            .iter_mut()
+            .for_each(|(_, data)| data.dependencies.sort_by_key(|dep| dep.crate_id));
+    }
+
     /// Extends this crate graph by adding a complete disjoint second crate
-    /// graph.
+    /// graph and adjust the ids in the [`ProcMacroPaths`] accordingly.
     ///
-    /// The ids of the crates in the `other` graph are shifted by the return
-    /// amount.
-    pub fn extend(&mut self, other: CrateGraph) -> u32 {
-        let start = self.arena.len() as u32;
-        self.arena.extend(other.arena.into_iter().map(|(id, mut data)| {
-            let new_id = id.shift(start);
-            for dep in &mut data.dependencies {
-                dep.crate_id = dep.crate_id.shift(start);
+    /// This will deduplicate the crates of the graph where possible.
+    /// Note that for deduplication to fully work, `self`'s crate dependencies must be sorted by crate id.
+    /// If the crate dependencies were sorted, the resulting graph from this `extend` call will also have the crate dependencies sorted.
+    pub fn extend(&mut self, mut other: CrateGraph, proc_macros: &mut ProcMacroPaths) {
+        let topo = other.crates_in_topological_order();
+        let mut id_map: FxHashMap<CrateId, CrateId> = FxHashMap::default();
+
+        for topo in topo {
+            let crate_data = &mut other.arena[topo];
+            crate_data.dependencies.iter_mut().for_each(|dep| dep.crate_id = id_map[&dep.crate_id]);
+            crate_data.dependencies.sort_by_key(|dep| dep.crate_id);
+
+            let res = self.arena.iter().find_map(
+                |(id, data)| {
+                    if data == crate_data {
+                        Some(id)
+                    } else {
+                        None
+                    }
+                },
+            );
+            if let Some(res) = res {
+                id_map.insert(topo, res);
+            } else {
+                let id = self.arena.alloc(crate_data.clone());
+                id_map.insert(topo, id);
             }
-            (new_id, data)
-        }));
-        start
+        }
+
+        *proc_macros =
+            mem::take(proc_macros).into_iter().map(|(id, macros)| (id_map[&id], macros)).collect();
     }
 
     fn find_path(
         &self,
-        visited: &mut NoHashHashSet<CrateId>,
+        visited: &mut FxHashSet<CrateId>,
         from: CrateId,
         to: CrateId,
     ) -> Option<Vec<CrateId>> {
@@ -500,14 +605,14 @@ impl CrateGraph {
     // Work around for https://github.com/rust-lang/rust-analyzer/issues/6038.
     // As hacky as it gets.
     pub fn patch_cfg_if(&mut self) -> bool {
-        let cfg_if = self.hacky_find_crate("cfg_if");
-        let std = self.hacky_find_crate("std");
+        // we stupidly max by version in an attempt to have all duplicated std's depend on the same cfg_if so that deduplication still works
+        let cfg_if =
+            self.hacky_find_crate("cfg_if").max_by_key(|&it| self.arena[it].version.clone());
+        let std = self.hacky_find_crate("std").next();
         match (cfg_if, std) {
             (Some(cfg_if), Some(std)) => {
-                self.arena.get_mut(&cfg_if).unwrap().dependencies.clear();
-                self.arena
-                    .get_mut(&std)
-                    .unwrap()
+                self.arena[cfg_if].dependencies.clear();
+                self.arena[std]
                     .dependencies
                     .push(Dependency::new(CrateName::new("cfg_if").unwrap(), cfg_if));
                 true
@@ -516,21 +621,15 @@ impl CrateGraph {
         }
     }
 
-    fn hacky_find_crate(&self, display_name: &str) -> Option<CrateId> {
-        self.iter().find(|it| self[*it].display_name.as_deref() == Some(display_name))
+    fn hacky_find_crate<'a>(&'a self, display_name: &'a str) -> impl Iterator<Item = CrateId> + 'a {
+        self.iter().filter(move |it| self[*it].display_name.as_deref() == Some(display_name))
     }
 }
 
 impl ops::Index<CrateId> for CrateGraph {
     type Output = CrateData;
     fn index(&self, crate_id: CrateId) -> &CrateData {
-        &self.arena[&crate_id]
-    }
-}
-
-impl CrateId {
-    fn shift(self, amount: u32) -> CrateId {
-        CrateId(self.0 + amount)
+        &self.arena[crate_id]
     }
 }
 
@@ -632,7 +731,7 @@ impl fmt::Display for CyclicDependenciesError {
 mod tests {
     use crate::CrateOrigin;
 
-    use super::{CfgOptions, CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
+    use super::{CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
 
     #[test]
     fn detect_cyclic_dependency_indirect() {
@@ -642,39 +741,39 @@ mod tests {
             Edition2018,
             None,
             None,
-            CfgOptions::default(),
-            CfgOptions::default(),
+            Default::default(),
+            Default::default(),
             Env::default(),
-            Ok(Vec::new()),
             false,
-            CrateOrigin::CratesIo { repo: None, name: None },
+            CrateOrigin::Local { repo: None, name: None },
             Err("".into()),
+            None,
         );
         let crate2 = graph.add_crate_root(
             FileId(2u32),
             Edition2018,
             None,
             None,
-            CfgOptions::default(),
-            CfgOptions::default(),
+            Default::default(),
+            Default::default(),
             Env::default(),
-            Ok(Vec::new()),
             false,
-            CrateOrigin::CratesIo { repo: None, name: None },
+            CrateOrigin::Local { repo: None, name: None },
             Err("".into()),
+            None,
         );
         let crate3 = graph.add_crate_root(
             FileId(3u32),
             Edition2018,
             None,
             None,
-            CfgOptions::default(),
-            CfgOptions::default(),
+            Default::default(),
+            Default::default(),
             Env::default(),
-            Ok(Vec::new()),
             false,
-            CrateOrigin::CratesIo { repo: None, name: None },
+            CrateOrigin::Local { repo: None, name: None },
             Err("".into()),
+            None,
         );
         assert!(graph
             .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
@@ -695,26 +794,26 @@ mod tests {
             Edition2018,
             None,
             None,
-            CfgOptions::default(),
-            CfgOptions::default(),
+            Default::default(),
+            Default::default(),
             Env::default(),
-            Ok(Vec::new()),
             false,
-            CrateOrigin::CratesIo { repo: None, name: None },
+            CrateOrigin::Local { repo: None, name: None },
             Err("".into()),
+            None,
         );
         let crate2 = graph.add_crate_root(
             FileId(2u32),
             Edition2018,
             None,
             None,
-            CfgOptions::default(),
-            CfgOptions::default(),
+            Default::default(),
+            Default::default(),
             Env::default(),
-            Ok(Vec::new()),
             false,
-            CrateOrigin::CratesIo { repo: None, name: None },
+            CrateOrigin::Local { repo: None, name: None },
             Err("".into()),
+            None,
         );
         assert!(graph
             .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
@@ -732,39 +831,39 @@ mod tests {
             Edition2018,
             None,
             None,
-            CfgOptions::default(),
-            CfgOptions::default(),
+            Default::default(),
+            Default::default(),
             Env::default(),
-            Ok(Vec::new()),
             false,
-            CrateOrigin::CratesIo { repo: None, name: None },
+            CrateOrigin::Local { repo: None, name: None },
             Err("".into()),
+            None,
         );
         let crate2 = graph.add_crate_root(
             FileId(2u32),
             Edition2018,
             None,
             None,
-            CfgOptions::default(),
-            CfgOptions::default(),
+            Default::default(),
+            Default::default(),
             Env::default(),
-            Ok(Vec::new()),
             false,
-            CrateOrigin::CratesIo { repo: None, name: None },
+            CrateOrigin::Local { repo: None, name: None },
             Err("".into()),
+            None,
         );
         let crate3 = graph.add_crate_root(
             FileId(3u32),
             Edition2018,
             None,
             None,
-            CfgOptions::default(),
-            CfgOptions::default(),
+            Default::default(),
+            Default::default(),
             Env::default(),
-            Ok(Vec::new()),
             false,
-            CrateOrigin::CratesIo { repo: None, name: None },
+            CrateOrigin::Local { repo: None, name: None },
             Err("".into()),
+            None,
         );
         assert!(graph
             .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
@@ -782,26 +881,26 @@ mod tests {
             Edition2018,
             None,
             None,
-            CfgOptions::default(),
-            CfgOptions::default(),
+            Default::default(),
+            Default::default(),
             Env::default(),
-            Ok(Vec::new()),
             false,
-            CrateOrigin::CratesIo { repo: None, name: None },
+            CrateOrigin::Local { repo: None, name: None },
             Err("".into()),
+            None,
         );
         let crate2 = graph.add_crate_root(
             FileId(2u32),
             Edition2018,
             None,
             None,
-            CfgOptions::default(),
-            CfgOptions::default(),
+            Default::default(),
+            Default::default(),
             Env::default(),
-            Ok(Vec::new()),
             false,
-            CrateOrigin::CratesIo { repo: None, name: None },
+            CrateOrigin::Local { repo: None, name: None },
             Err("".into()),
+            None,
         );
         assert!(graph
             .add_dep(
diff --git a/src/tools/rust-analyzer/crates/base-db/src/lib.rs b/src/tools/rust-analyzer/crates/base-db/src/lib.rs
index 9720db9d8ac..af204e44e6e 100644
--- a/src/tools/rust-analyzer/crates/base-db/src/lib.rs
+++ b/src/tools/rust-analyzer/crates/base-db/src/lib.rs
@@ -6,18 +6,19 @@ mod input;
 mod change;
 pub mod fixture;
 
-use std::{panic, sync::Arc};
+use std::panic;
 
-use stdx::hash::NoHashHashSet;
+use rustc_hash::FxHashSet;
 use syntax::{ast, Parse, SourceFile, TextRange, TextSize};
+use triomphe::Arc;
 
 pub use crate::{
     change::Change,
     input::{
         CrateData, CrateDisplayName, CrateGraph, CrateId, CrateName, CrateOrigin, Dependency,
         Edition, Env, LangCrateOrigin, ProcMacro, ProcMacroExpander, ProcMacroExpansionError,
-        ProcMacroId, ProcMacroKind, ProcMacroLoadResult, SourceRoot, SourceRootId,
-        TargetLayoutLoadResult,
+        ProcMacroId, ProcMacroKind, ProcMacroLoadResult, ProcMacroPaths, ProcMacros,
+        ReleaseChannel, SourceRoot, SourceRootId, TargetLayoutLoadResult,
     },
 };
 pub use salsa::{self, Cancelled};
@@ -53,13 +54,13 @@ pub struct FileRange {
     pub range: TextRange,
 }
 
-pub const DEFAULT_LRU_CAP: usize = 128;
+pub const DEFAULT_PARSE_LRU_CAP: usize = 128;
 
 pub trait FileLoader {
     /// Text of the file.
-    fn file_text(&self, file_id: FileId) -> Arc<String>;
+    fn file_text(&self, file_id: FileId) -> Arc<str>;
     fn resolve_path(&self, path: AnchoredPath<'_>) -> Option<FileId>;
-    fn relevant_crates(&self, file_id: FileId) -> Arc<NoHashHashSet<CrateId>>;
+    fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>>;
 }
 
 /// Database which stores all significant input facts: source code and project
@@ -73,6 +74,10 @@ pub trait SourceDatabase: FileLoader + std::fmt::Debug {
     /// The crate graph.
     #[salsa::input]
     fn crate_graph(&self) -> Arc<CrateGraph>;
+
+    /// The crate graph.
+    #[salsa::input]
+    fn proc_macros(&self) -> Arc<ProcMacros>;
 }
 
 fn parse_query(db: &dyn SourceDatabase, file_id: FileId) -> Parse<ast::SourceFile> {
@@ -86,7 +91,7 @@ fn parse_query(db: &dyn SourceDatabase, file_id: FileId) -> Parse<ast::SourceFil
 #[salsa::query_group(SourceDatabaseExtStorage)]
 pub trait SourceDatabaseExt: SourceDatabase {
     #[salsa::input]
-    fn file_text(&self, file_id: FileId) -> Arc<String>;
+    fn file_text(&self, file_id: FileId) -> Arc<str>;
     /// Path to a file, relative to the root of its source root.
     /// Source root of the file.
     #[salsa::input]
@@ -95,10 +100,10 @@ pub trait SourceDatabaseExt: SourceDatabase {
     #[salsa::input]
     fn source_root(&self, id: SourceRootId) -> Arc<SourceRoot>;
 
-    fn source_root_crates(&self, id: SourceRootId) -> Arc<NoHashHashSet<CrateId>>;
+    fn source_root_crates(&self, id: SourceRootId) -> Arc<FxHashSet<CrateId>>;
 }
 
-fn source_root_crates(db: &dyn SourceDatabaseExt, id: SourceRootId) -> Arc<NoHashHashSet<CrateId>> {
+fn source_root_crates(db: &dyn SourceDatabaseExt, id: SourceRootId) -> Arc<FxHashSet<CrateId>> {
     let graph = db.crate_graph();
     let res = graph
         .iter()
@@ -114,7 +119,7 @@ fn source_root_crates(db: &dyn SourceDatabaseExt, id: SourceRootId) -> Arc<NoHas
 pub struct FileLoaderDelegate<T>(pub T);
 
 impl<T: SourceDatabaseExt> FileLoader for FileLoaderDelegate<&'_ T> {
-    fn file_text(&self, file_id: FileId) -> Arc<String> {
+    fn file_text(&self, file_id: FileId) -> Arc<str> {
         SourceDatabaseExt::file_text(self.0, file_id)
     }
     fn resolve_path(&self, path: AnchoredPath<'_>) -> Option<FileId> {
@@ -124,7 +129,7 @@ impl<T: SourceDatabaseExt> FileLoader for FileLoaderDelegate<&'_ T> {
         source_root.resolve_path(path)
     }
 
-    fn relevant_crates(&self, file_id: FileId) -> Arc<NoHashHashSet<CrateId>> {
+    fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>> {
         let _p = profile::span("relevant_crates");
         let source_root = self.0.file_source_root(file_id);
         self.0.source_root_crates(source_root)