Relaxation for crate graph mergin

Partially fixes #15656 . When a crate graph is extended which is the case when new workspaces are added to the project
the rules for deduplication were too strict. One problem that arises from this is that in certain conditions
when we see the same crate having different `CrateOrigin`s the first form would be maintained. This approach however
results in some unwanted results such as making renaming forbidden as this has been recently only made available for
local crates. The given example in #15656 can still not be resolved with this PR as that involves taking inconsistencies
between dependencies into consideration. This will be addressed in a future PR.

11 files changed, 515 insertions, 54 deletions

diff --git a/crates/base-db/src/fixture.rs b/crates/base-db/src/fixture.rs
index 3f5ccb621c7..3da555a47ac 100644
--- a/crates/base-db/src/fixture.rs
+++ b/crates/base-db/src/fixture.rs
@@ -13,9 +13,9 @@ 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, ProcMacros, ReleaseChannel,
-    SourceDatabaseExt, SourceRoot, SourceRootId,
+    Change, CrateDisplayName, CrateGraph, CrateId, Dependency, DependencyKind, Edition, Env,
+    FileId, FilePosition, FileRange, ProcMacro, ProcMacroExpander, ProcMacroExpansionError,
+    ProcMacros, ReleaseChannel, SourceDatabaseExt, SourceRoot, SourceRootId,
 };
 
 pub const WORKSPACE: SourceRootId = SourceRootId(0);
@@ -237,7 +237,12 @@ impl ChangeFixture {
                 crate_graph
                     .add_dep(
                         from_id,
-                        Dependency::with_prelude(CrateName::new(&to).unwrap(), to_id, prelude),
+                        Dependency::with_prelude(
+                            CrateName::new(&to).unwrap(),
+                            to_id,
+                            prelude,
+                            DependencyKind::Normal,
+                        ),
                     )
                     .unwrap();
             }
@@ -275,7 +280,14 @@ impl ChangeFixture {
 
             for krate in all_crates {
                 crate_graph
-                    .add_dep(krate, Dependency::new(CrateName::new("core").unwrap(), core_crate))
+                    .add_dep(
+                        krate,
+                        Dependency::new(
+                            CrateName::new("core").unwrap(),
+                            core_crate,
+                            DependencyKind::Normal,
+                        ),
+                    )
                     .unwrap();
             }
         }
@@ -317,7 +329,11 @@ impl ChangeFixture {
                 crate_graph
                     .add_dep(
                         krate,
-                        Dependency::new(CrateName::new("proc_macros").unwrap(), proc_macros_crate),
+                        Dependency::new(
+                            CrateName::new("proc_macros").unwrap(),
+                            proc_macros_crate,
+                            DependencyKind::Normal,
+                        ),
                     )
                     .unwrap();
             }
diff --git a/crates/base-db/src/input.rs b/crates/base-db/src/input.rs
index 65db5c0fc7d..fb69e667ad9 100644
--- a/crates/base-db/src/input.rs
+++ b/crates/base-db/src/input.rs
@@ -8,7 +8,7 @@
 
 use std::{fmt, mem, ops, panic::RefUnwindSafe, str::FromStr, sync};
 
-use cfg::CfgOptions;
+use cfg::{CfgDiff, CfgOptions};
 use la_arena::{Arena, Idx};
 use rustc_hash::{FxHashMap, FxHashSet};
 use syntax::SmolStr;
@@ -155,6 +155,10 @@ impl CrateOrigin {
     pub fn is_local(&self) -> bool {
         matches!(self, CrateOrigin::Local { .. })
     }
+
+    pub fn is_lib(&self) -> bool {
+        matches!(self, CrateOrigin::Library { .. })
+    }
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
@@ -324,6 +328,99 @@ pub struct CrateData {
     pub channel: Option<ReleaseChannel>,
 }
 
+impl CrateData {
+    /**
+    Check if [`other`] is almost equal to [`self`].
+    This method has some obscure bits. These are mostly there to be compliant with
+    some patches. References to the patches are given.
+    */
+    pub fn almost_eq(&self, other: &CrateData) -> bool {
+        if self.root_file_id != other.root_file_id {
+            return false;
+        }
+
+        if self.display_name != other.display_name {
+            return false;
+        }
+
+        if self.is_proc_macro != other.is_proc_macro {
+            return false;
+        }
+
+        if self.edition != other.edition {
+            return false;
+        }
+
+        if self.version != other.version {
+            return false;
+        }
+
+        let mut opts = self.cfg_options.clone();
+        opts.apply_diff(CfgDiff {
+            disable: other.cfg_options.clone().into_iter().collect(),
+            enable: vec![],
+        });
+
+        let mut cfgs = opts.into_iter();
+        if let Some(cfg) = cfgs.next() {
+            // Don't care if rust_analyzer CfgAtom is the only cfg in the difference set of self's and other's cfgs.
+            // https://github.com/rust-lang/rust-analyzer/blob/0840038f02daec6ba3238f05d8caa037d28701a0/crates/project-model/src/workspace.rs#L894
+            if !cfgs.next().is_none() || cfg.to_string() != "rust_analyzer" {
+                return false;
+            }
+        }
+
+        let mut itself = self.dependencies.iter();
+        let mut otself = other.dependencies.iter();
+        let (mut anx, mut bnx) = (itself.next(), otself.next());
+        loop {
+            match (anx, bnx) {
+                (None, None) => {
+                    break;
+                }
+                (None, Some(b)) => {
+                    if b.kind != DependencyKind::Normal {
+                        bnx = otself.next();
+                    } else {
+                        break;
+                    }
+                }
+                (Some(a), None) => {
+                    if a.kind != DependencyKind::Normal {
+                        anx = itself.next();
+                    } else {
+                        break;
+                    }
+                }
+                (Some(a), Some(b)) => {
+                    if a.kind != DependencyKind::Normal {
+                        anx = itself.next();
+                        continue;
+                    }
+
+                    if b.kind != DependencyKind::Normal {
+                        bnx = otself.next();
+                        continue;
+                    }
+
+                    if a != b {
+                        return false;
+                    }
+
+                    anx = itself.next();
+                    bnx = otself.next();
+                }
+            }
+        }
+
+        if self.env != other.env {
+            return false;
+        }
+
+        true
+    }
+}
+
 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub enum Edition {
     Edition2015,
@@ -352,25 +449,42 @@ impl Env {
 }
 
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub enum DependencyKind {
+    Normal,
+    Dev,
+    Build,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct Dependency {
     pub crate_id: CrateId,
     pub name: CrateName,
+    kind: DependencyKind,
     prelude: bool,
 }
 
 impl Dependency {
-    pub fn new(name: CrateName, crate_id: CrateId) -> Self {
-        Self { name, crate_id, prelude: true }
+    pub fn new(name: CrateName, crate_id: CrateId, kind: DependencyKind) -> Self {
+        Self { name, crate_id, prelude: true, kind }
     }
 
-    pub fn with_prelude(name: CrateName, crate_id: CrateId, prelude: bool) -> Self {
-        Self { name, crate_id, prelude }
+    pub fn with_prelude(
+        name: CrateName,
+        crate_id: CrateId,
+        prelude: bool,
+        kind: DependencyKind,
+    ) -> Self {
+        Self { name, crate_id, prelude, kind }
     }
 
     /// Whether this dependency is to be added to the depending crate's extern prelude.
     pub fn is_prelude(&self) -> bool {
         self.prelude
     }
+
+    pub fn kind(&self) -> &DependencyKind {
+        &self.kind
+    }
 }
 
 impl CrateGraph {
@@ -572,25 +686,41 @@ impl CrateGraph {
     /// 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) {
+        enum ExtendStrategy {
+            Dedup(CrateId),
+            Replace(CrateId),
+        }
+
         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
+            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.almost_eq(crate_data) {
+                    if data.origin.is_lib() && crate_data.origin.is_local() {
+                        // See #15656 for a relevant example.
+                        return Some(ExtendStrategy::Replace(id));
                     }
-                },
-            );
+
+                    return Some(ExtendStrategy::Dedup(id));
+                }
+                None
+            });
+
             if let Some(res) = res {
-                id_map.insert(topo, res);
+                match res {
+                    ExtendStrategy::Dedup(res) => id_map.insert(topo, res),
+                    ExtendStrategy::Replace(res) => {
+                        let id = self.arena.alloc(crate_data.clone());
+                        let _ = self.remove_and_replace(res, id);
+                        id_map.insert(topo, id)
+                    }
+                };
             } else {
                 let id = self.arena.alloc(crate_data.clone());
                 id_map.insert(topo, id);
@@ -636,9 +766,11 @@ impl CrateGraph {
         match (cfg_if, std) {
             (Some(cfg_if), Some(std)) => {
                 self.arena[cfg_if].dependencies.clear();
-                self.arena[std]
-                    .dependencies
-                    .push(Dependency::new(CrateName::new("cfg_if").unwrap(), cfg_if));
+                self.arena[std].dependencies.push(Dependency::new(
+                    CrateName::new("cfg_if").unwrap(),
+                    cfg_if,
+                    DependencyKind::Normal,
+                ));
                 true
             }
             _ => false,
@@ -759,7 +891,7 @@ impl fmt::Display for CyclicDependenciesError {
 
 #[cfg(test)]
 mod tests {
-    use crate::CrateOrigin;
+    use crate::{CrateOrigin, DependencyKind};
 
     use super::{CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
 
@@ -806,13 +938,22 @@ mod tests {
             None,
         );
         assert!(graph
-            .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
+            .add_dep(
+                crate1,
+                Dependency::new(CrateName::new("crate2").unwrap(), crate2, DependencyKind::Normal)
+            )
             .is_ok());
         assert!(graph
-            .add_dep(crate2, Dependency::new(CrateName::new("crate3").unwrap(), crate3))
+            .add_dep(
+                crate2,
+                Dependency::new(CrateName::new("crate3").unwrap(), crate3, DependencyKind::Normal)
+            )
             .is_ok());
         assert!(graph
-            .add_dep(crate3, Dependency::new(CrateName::new("crate1").unwrap(), crate1))
+            .add_dep(
+                crate3,
+                Dependency::new(CrateName::new("crate1").unwrap(), crate1, DependencyKind::Normal)
+            )
             .is_err());
     }
 
@@ -846,10 +987,16 @@ mod tests {
             None,
         );
         assert!(graph
-            .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
+            .add_dep(
+                crate1,
+                Dependency::new(CrateName::new("crate2").unwrap(), crate2, DependencyKind::Normal)
+            )
             .is_ok());
         assert!(graph
-            .add_dep(crate2, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
+            .add_dep(
+                crate2,
+                Dependency::new(CrateName::new("crate2").unwrap(), crate2, DependencyKind::Normal)
+            )
             .is_err());
     }
 
@@ -896,10 +1043,16 @@ mod tests {
             None,
         );
         assert!(graph
-            .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2))
+            .add_dep(
+                crate1,
+                Dependency::new(CrateName::new("crate2").unwrap(), crate2, DependencyKind::Normal)
+            )
             .is_ok());
         assert!(graph
-            .add_dep(crate2, Dependency::new(CrateName::new("crate3").unwrap(), crate3))
+            .add_dep(
+                crate2,
+                Dependency::new(CrateName::new("crate3").unwrap(), crate3, DependencyKind::Normal)
+            )
             .is_ok());
     }
 
@@ -935,12 +1088,20 @@ mod tests {
         assert!(graph
             .add_dep(
                 crate1,
-                Dependency::new(CrateName::normalize_dashes("crate-name-with-dashes"), crate2)
+                Dependency::new(
+                    CrateName::normalize_dashes("crate-name-with-dashes"),
+                    crate2,
+                    DependencyKind::Normal
+                )
             )
             .is_ok());
         assert_eq!(
             graph[crate1].dependencies,
-            vec![Dependency::new(CrateName::new("crate_name_with_dashes").unwrap(), crate2)]
+            vec![Dependency::new(
+                CrateName::new("crate_name_with_dashes").unwrap(),
+                crate2,
+                DependencyKind::Normal
+            )]
         );
     }
 }
diff --git a/crates/base-db/src/lib.rs b/crates/base-db/src/lib.rs
index c5c4afa30f7..40cfab88afd 100644
--- a/crates/base-db/src/lib.rs
+++ b/crates/base-db/src/lib.rs
@@ -12,6 +12,7 @@ use rustc_hash::FxHashSet;
 use syntax::{ast, Parse, SourceFile, TextRange, TextSize};
 use triomphe::Arc;
 
+pub use crate::input::DependencyKind;
 pub use crate::{
     change::Change,
     input::{
diff --git a/crates/cfg/src/lib.rs b/crates/cfg/src/lib.rs
index 0aeb0b05052..90dba008ad7 100644
--- a/crates/cfg/src/lib.rs
+++ b/crates/cfg/src/lib.rs
@@ -115,8 +115,8 @@ impl<'a> IntoIterator for &'a CfgOptions {
 #[derive(Default, Clone, Debug, PartialEq, Eq)]
 pub struct CfgDiff {
     // Invariants: No duplicates, no atom that's both in `enable` and `disable`.
-    enable: Vec<CfgAtom>,
-    disable: Vec<CfgAtom>,
+    pub enable: Vec<CfgAtom>,
+    pub disable: Vec<CfgAtom>,
 }
 
 impl CfgDiff {
diff --git a/crates/project-model/src/project_json.rs b/crates/project-model/src/project_json.rs
index 80897f7478c..931eba11576 100644
--- a/crates/project-model/src/project_json.rs
+++ b/crates/project-model/src/project_json.rs
@@ -49,7 +49,7 @@
 //! user explores them belongs to that extension (it's totally valid to change
 //! rust-project.json over time via configuration request!)
 
-use base_db::{CrateDisplayName, CrateId, CrateName, Dependency, Edition};
+use base_db::{CrateDisplayName, CrateId, CrateName, Dependency, DependencyKind, Edition};
 use la_arena::RawIdx;
 use paths::{AbsPath, AbsPathBuf};
 use rustc_hash::FxHashMap;
@@ -135,6 +135,7 @@ impl ProjectJson {
                                 Dependency::new(
                                     dep_data.name,
                                     CrateId::from_raw(RawIdx::from(dep_data.krate as u32)),
+                                    DependencyKind::Normal,
                                 )
                             })
                             .collect::<Vec<_>>(),
diff --git a/crates/project-model/src/workspace.rs b/crates/project-model/src/workspace.rs
index e0209ca15a5..9333570354a 100644
--- a/crates/project-model/src/workspace.rs
+++ b/crates/project-model/src/workspace.rs
@@ -6,8 +6,8 @@ use std::{collections::VecDeque, fmt, fs, iter, process::Command, str::FromStr,
 
 use anyhow::{format_err, Context};
 use base_db::{
-    CrateDisplayName, CrateGraph, CrateId, CrateName, CrateOrigin, Dependency, Edition, Env,
-    FileId, LangCrateOrigin, ProcMacroPaths, ReleaseChannel, TargetLayoutLoadResult,
+    CrateDisplayName, CrateGraph, CrateId, CrateName, CrateOrigin, Dependency, DependencyKind,
+    Edition, Env, FileId, LangCrateOrigin, ProcMacroPaths, ReleaseChannel, TargetLayoutLoadResult,
 };
 use cfg::{CfgDiff, CfgOptions};
 use paths::{AbsPath, AbsPathBuf};
@@ -834,7 +834,7 @@ fn project_json_to_crate_graph(
 
             for dep in &krate.deps {
                 if let Some(&to) = crates.get(&dep.crate_id) {
-                    add_dep(crate_graph, from, dep.name.clone(), to)
+                    add_dep(crate_graph, from, dep.name.clone(), to, dep.kind().to_owned())
                 }
             }
         }
@@ -979,7 +979,7 @@ fn cargo_to_crate_graph(
                     // cargo metadata does not do any normalization,
                     // so we do it ourselves currently
                     let name = CrateName::normalize_dashes(&name);
-                    add_dep(crate_graph, from, name, to);
+                    add_dep(crate_graph, from, name, to, DependencyKind::Normal);
                 }
             }
         }
@@ -999,7 +999,17 @@ fn cargo_to_crate_graph(
                     continue;
                 }
 
-                add_dep(crate_graph, from, name.clone(), to)
+                add_dep(
+                    crate_graph,
+                    from,
+                    name.clone(),
+                    to,
+                    match dep.kind {
+                        DepKind::Normal => DependencyKind::Normal,
+                        DepKind::Dev => DependencyKind::Dev,
+                        DepKind::Build => DependencyKind::Build,
+                    },
+                )
             }
         }
     }
@@ -1187,7 +1197,17 @@ fn handle_rustc_crates(
             let name = CrateName::new(&dep.name).unwrap();
             if let Some(&to) = pkg_to_lib_crate.get(&dep.pkg) {
                 for &from in rustc_pkg_crates.get(&pkg).into_iter().flatten() {
-                    add_dep(crate_graph, from, name.clone(), to);
+                    add_dep(
+                        crate_graph,
+                        from,
+                        name.clone(),
+                        to,
+                        match dep.kind {
+                            DepKind::Normal => DependencyKind::Normal,
+                            DepKind::Dev => DependencyKind::Dev,
+                            DepKind::Build => DependencyKind::Build,
+                        },
+                    );
                 }
             }
         }
@@ -1209,7 +1229,7 @@ fn handle_rustc_crates(
                     // `rust_analyzer` thinks that it should use the one from the `rustc_source`
                     // instead of the one from `crates.io`
                     if !crate_graph[*from].dependencies.iter().any(|d| d.name == name) {
-                        add_dep(crate_graph, *from, name.clone(), to);
+                        add_dep(crate_graph, *from, name.clone(), to, DependencyKind::Normal);
                     }
                 }
             }
@@ -1308,7 +1328,14 @@ impl SysrootPublicDeps {
     /// Makes `from` depend on the public sysroot crates.
     fn add_to_crate_graph(&self, crate_graph: &mut CrateGraph, from: CrateId) {
         for (name, krate, prelude) in &self.deps {
-            add_dep_with_prelude(crate_graph, from, name.clone(), *krate, *prelude);
+            add_dep_with_prelude(
+                crate_graph,
+                from,
+                name.clone(),
+                *krate,
+                *prelude,
+                DependencyKind::Normal,
+            );
         }
     }
 }
@@ -1363,7 +1390,7 @@ fn sysroot_to_crate_graph(
         for &to in sysroot[from].deps.iter() {
             let name = CrateName::new(&sysroot[to].name).unwrap();
             if let (Some(&from), Some(&to)) = (sysroot_crates.get(&from), sysroot_crates.get(&to)) {
-                add_dep(crate_graph, from, name, to);
+                add_dep(crate_graph, from, name, to, DependencyKind::Normal);
             }
         }
     }
@@ -1442,8 +1469,14 @@ fn handle_hack_cargo_workspace(
         .collect()
 }
 
-fn add_dep(graph: &mut CrateGraph, from: CrateId, name: CrateName, to: CrateId) {
-    add_dep_inner(graph, from, Dependency::new(name, to))
+fn add_dep(
+    graph: &mut CrateGraph,
+    from: CrateId,
+    name: CrateName,
+    to: CrateId,
+    kind: DependencyKind,
+) {
+    add_dep_inner(graph, from, Dependency::new(name, to, kind))
 }
 
 fn add_dep_with_prelude(
@@ -1452,12 +1485,20 @@ fn add_dep_with_prelude(
     name: CrateName,
     to: CrateId,
     prelude: bool,
+    kind: DependencyKind,
 ) {
-    add_dep_inner(graph, from, Dependency::with_prelude(name, to, prelude))
+    add_dep_inner(graph, from, Dependency::with_prelude(name, to, prelude, kind))
 }
 
 fn add_proc_macro_dep(crate_graph: &mut CrateGraph, from: CrateId, to: CrateId, prelude: bool) {
-    add_dep_with_prelude(crate_graph, from, CrateName::new("proc_macro").unwrap(), to, prelude);
+    add_dep_with_prelude(
+        crate_graph,
+        from,
+        CrateName::new("proc_macro").unwrap(),
+        to,
+        prelude,
+        DependencyKind::Normal,
+    );
 }
 
 fn add_dep_inner(graph: &mut CrateGraph, from: CrateId, dep: Dependency) {
diff --git a/crates/project-model/test_data/output/cargo_hello_world_project_model.txt b/crates/project-model/test_data/output/cargo_hello_world_project_model.txt
index 727d39a3077..e98f016ca7d 100644
--- a/crates/project-model/test_data/output/cargo_hello_world_project_model.txt
+++ b/crates/project-model/test_data/output/cargo_hello_world_project_model.txt
@@ -48,6 +48,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -112,6 +113,7 @@
                 name: CrateName(
                     "hello_world",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -119,6 +121,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -183,6 +186,7 @@
                 name: CrateName(
                     "hello_world",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -190,6 +194,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -254,6 +259,7 @@
                 name: CrateName(
                     "hello_world",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -261,6 +267,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
diff --git a/crates/project-model/test_data/output/cargo_hello_world_project_model_with_selective_overrides.txt b/crates/project-model/test_data/output/cargo_hello_world_project_model_with_selective_overrides.txt
index 727d39a3077..e98f016ca7d 100644
--- a/crates/project-model/test_data/output/cargo_hello_world_project_model_with_selective_overrides.txt
+++ b/crates/project-model/test_data/output/cargo_hello_world_project_model_with_selective_overrides.txt
@@ -48,6 +48,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -112,6 +113,7 @@
                 name: CrateName(
                     "hello_world",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -119,6 +121,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -183,6 +186,7 @@
                 name: CrateName(
                     "hello_world",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -190,6 +194,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -254,6 +259,7 @@
                 name: CrateName(
                     "hello_world",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -261,6 +267,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
diff --git a/crates/project-model/test_data/output/cargo_hello_world_project_model_with_wildcard_overrides.txt b/crates/project-model/test_data/output/cargo_hello_world_project_model_with_wildcard_overrides.txt
index 89728babd82..7ecd53572e2 100644
--- a/crates/project-model/test_data/output/cargo_hello_world_project_model_with_wildcard_overrides.txt
+++ b/crates/project-model/test_data/output/cargo_hello_world_project_model_with_wildcard_overrides.txt
@@ -47,6 +47,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -110,6 +111,7 @@
                 name: CrateName(
                     "hello_world",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -117,6 +119,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -180,6 +183,7 @@
                 name: CrateName(
                     "hello_world",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -187,6 +191,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -250,6 +255,7 @@
                 name: CrateName(
                     "hello_world",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -257,6 +263,7 @@
                 name: CrateName(
                     "libc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
diff --git a/crates/project-model/test_data/output/rust_project_hello_world_project_model.txt b/crates/project-model/test_data/output/rust_project_hello_world_project_model.txt
index b7bf6cb2774..581a6afc148 100644
--- a/crates/project-model/test_data/output/rust_project_hello_world_project_model.txt
+++ b/crates/project-model/test_data/output/rust_project_hello_world_project_model.txt
@@ -28,6 +28,7 @@
                 name: CrateName(
                     "core",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -168,6 +169,7 @@
                 name: CrateName(
                     "std",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -175,6 +177,7 @@
                 name: CrateName(
                     "core",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -249,6 +252,7 @@
                 name: CrateName(
                     "alloc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -256,6 +260,7 @@
                 name: CrateName(
                     "panic_unwind",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -263,6 +268,7 @@
                 name: CrateName(
                     "panic_abort",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -270,6 +276,7 @@
                 name: CrateName(
                     "core",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -277,6 +284,7 @@
                 name: CrateName(
                     "profiler_builtins",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -284,6 +292,7 @@
                 name: CrateName(
                     "unwind",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -291,6 +300,7 @@
                 name: CrateName(
                     "std_detect",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -298,6 +308,7 @@
                 name: CrateName(
                     "test",
                 ),
+                kind: Normal,
                 prelude: true,
             },
         ],
@@ -438,6 +449,7 @@
                 name: CrateName(
                     "core",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -445,6 +457,7 @@
                 name: CrateName(
                     "alloc",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -452,6 +465,7 @@
                 name: CrateName(
                     "std",
                 ),
+                kind: Normal,
                 prelude: true,
             },
             Dependency {
@@ -459,6 +473,7 @@
                 name: CrateName(
                     "test",
                 ),
+                kind: Normal,
                 prelude: false,
             },
             Dependency {
@@ -466,6 +481,7 @@
                 name: CrateName(
                     "proc_macro",
                 ),
+                kind: Normal,
                 prelude: false,
             },
         ],
diff --git a/crates/rust-analyzer/tests/slow-tests/main.rs b/crates/rust-analyzer/tests/slow-tests/main.rs
index d5991429899..423c07183e2 100644
--- a/crates/rust-analyzer/tests/slow-tests/main.rs
+++ b/crates/rust-analyzer/tests/slow-tests/main.rs
@@ -21,12 +21,12 @@ use std::{collections::HashMap, path::PathBuf, time::Instant};
 use lsp_types::{
     notification::DidOpenTextDocument,
     request::{
-        CodeActionRequest, Completion, Formatting, GotoTypeDefinition, HoverRequest,
+        CodeActionRequest, Completion, Formatting, GotoTypeDefinition, HoverRequest, Rename,
         WillRenameFiles, WorkspaceSymbolRequest,
     },
     CodeActionContext, CodeActionParams, CompletionParams, DidOpenTextDocumentParams,
     DocumentFormattingParams, FileRename, FormattingOptions, GotoDefinitionParams, HoverParams,
-    PartialResultParams, Position, Range, RenameFilesParams, TextDocumentItem,
+    PartialResultParams, Position, Range, RenameFilesParams, RenameParams, TextDocumentItem,
     TextDocumentPositionParams, WorkDoneProgressParams,
 };
 use rust_analyzer::lsp::ext::{OnEnter, Runnables, RunnablesParams};
@@ -1131,3 +1131,207 @@ version = "0.0.0"
 
     server.request::<WorkspaceSymbolRequest>(Default::default(), json!([]));
 }
+
+#[test]
+fn test_deduplicate_crate_differing_in_origin() {
+    let fixture = r#"
+//- /projects/p1/Cargo.toml
+[package]
+name = "p1"
+version = "0.0.0"
+
+//- /projects/p1/src/lib.rs
+pub fn add2(left: usize, right: usize) -> usize {
+    left + right
+}
+
+//- /projects/p2/Cargo.toml
+[package]
+name = "p2"
+version = "0.0.0"
+
+[dependencies]
+p1 = { path = "../p1" }
+
+//- /projects/p2/src/lib.rs
+use p1::add2;
+
+pub fn bar() {}
+    "#;
+
+    let server = Project::with_fixture(fixture)
+        .with_config(serde_json::json!({
+                "linkedProjects" : [
+                    "./projects/p1/Cargo.toml",
+                    "./projects/p2/Cargo.toml"
+                ],
+            }
+        ))
+        .with_config(serde_json::json!({
+            "cargo": { "sysroot": null },
+        }))
+        .server()
+        .wait_until_workspace_is_loaded();
+
+    let doc_id = server.doc_id("./projects/p2/src/lib.rs");
+    let doc2_id = server.doc_id("./projects/p1/src/lib.rs");
+
+    server.request::<Rename>(
+        RenameParams {
+            text_document_position: TextDocumentPositionParams {
+                text_document: doc_id.clone(),
+                position: Position { line: 0, character: 8 },
+            },
+            new_name: "ABC".to_owned(),
+            work_done_progress_params: WorkDoneProgressParams { work_done_token: None },
+        },
+        json!({
+            "documentChanges": [
+                {
+                  "textDocument": {
+                    "uri": doc2_id.uri,
+                    "version": null
+                  },
+                  "edits": [
+                    {
+                      "range": {
+                        "start": {
+                          "line": 0,
+                          "character": 7
+                        },
+                        "end": {
+                          "line": 0,
+                          "character": 11
+                        }
+                      },
+                      "newText": "ABC"
+                    }
+                  ]
+                },
+                {
+                  "textDocument": {
+                    "uri": doc_id.uri,
+                    "version": null
+                  },
+                  "edits": [
+                    {
+                      "range": {
+                        "start": {
+                          "line": 0,
+                          "character": 8
+                        },
+                        "end": {
+                          "line": 0,
+                          "character": 12
+                        }
+                      },
+                      "newText": "ABC"
+                    }
+                  ]
+                },
+            ]
+        }),
+    );
+}
+
+#[test]
+fn test_deduplicate_crate_differing_in_origin_in_rev_resolution_order() {
+    let fixture = r#"
+//- /projects/p1/Cargo.toml
+[package]
+name = "p1"
+version = "0.0.0"
+
+//- /projects/p1/src/lib.rs
+pub fn add2(left: usize, right: usize) -> usize {
+    left + right
+}
+
+//- /projects/p2/Cargo.toml
+[package]
+name = "p2"
+version = "0.0.0"
+
+[dependencies]
+p1 = { path = "../p1" }
+
+//- /projects/p2/src/lib.rs
+use p1::add2;
+
+pub fn bar() {}
+    "#;
+
+    let server = Project::with_fixture(fixture)
+        .with_config(serde_json::json!({
+                "linkedProjects" : [
+                    "./projects/p2/Cargo.toml",
+                    "./projects/p1/Cargo.toml",
+                ],
+            }
+        ))
+        .with_config(serde_json::json!({
+            "cargo": { "sysroot": null },
+        }))
+        .server()
+        .wait_until_workspace_is_loaded();
+
+    let doc_id = server.doc_id("./projects/p2/src/lib.rs");
+    let doc2_id = server.doc_id("./projects/p1/src/lib.rs");
+
+    server.request::<Rename>(
+        RenameParams {
+            text_document_position: TextDocumentPositionParams {
+                text_document: doc_id.clone(),
+                position: Position { line: 0, character: 8 },
+            },
+            new_name: "ABC".to_owned(),
+            work_done_progress_params: WorkDoneProgressParams { work_done_token: None },
+        },
+        json!({
+            "documentChanges": [
+                {
+                  "textDocument": {
+                    "uri": doc2_id.uri,
+                    "version": null
+                  },
+                  "edits": [
+                    {
+                      "range": {
+                        "start": {
+                          "line": 0,
+                          "character": 7
+                        },
+                        "end": {
+                          "line": 0,
+                          "character": 11
+                        }
+                      },
+                      "newText": "ABC"
+                    }
+                  ]
+                },
+                {
+                  "textDocument": {
+                    "uri": doc_id.uri,
+                    "version": null
+                  },
+                  "edits": [
+                    {
+                      "range": {
+                        "start": {
+                          "line": 0,
+                          "character": 8
+                        },
+                        "end": {
+                          "line": 0,
+                          "character": 12
+                        }
+                      },
+                      "newText": "ABC"
+                    }
+                  ]
+                },
+            ]
+        }),
+    );
+}