9 files changed, 110 insertions, 153 deletions

diff --git a/crates/base_db/src/fixture.rs b/crates/base_db/src/fixture.rs
index 5c9824814..cad6866aa 100644
--- a/crates/base_db/src/fixture.rs
+++ b/crates/base_db/src/fixture.rs
@@ -57,7 +57,7 @@
 //! fn insert_source_code_here() {}
 //! "
 //! ```
-use std::{str::FromStr, sync::Arc};
+use std::{mem, str::FromStr, sync::Arc};
 
 use cfg::CfgOptions;
 use rustc_hash::FxHashMap;
@@ -148,6 +148,7 @@ impl ChangeFixture {
         let mut file_set = FileSet::default();
         let source_root_prefix = "/".to_string();
         let mut file_id = FileId(0);
+        let mut roots = Vec::new();
 
         let mut file_position = None;
 
@@ -168,6 +169,10 @@ impl ChangeFixture {
             let meta = FileMeta::from(entry);
             assert!(meta.path.starts_with(&source_root_prefix));
 
+            if meta.introduce_new_source_root {
+                roots.push(SourceRoot::new_local(mem::take(&mut file_set)));
+            }
+
             if let Some(krate) = meta.krate {
                 let crate_name = CrateName::normalize_dashes(&krate);
                 let crate_id = crate_graph.add_crate_root(
@@ -215,7 +220,8 @@ impl ChangeFixture {
             }
         }
 
-        change.set_roots(vec![SourceRoot::new_local(file_set)]);
+        roots.push(SourceRoot::new_local(mem::take(&mut file_set)));
+        change.set_roots(roots);
         change.set_crate_graph(crate_graph);
 
         ChangeFixture { file_position, files, change }
@@ -229,6 +235,7 @@ struct FileMeta {
     cfg: CfgOptions,
     edition: Edition,
     env: Env,
+    introduce_new_source_root: bool,
 }
 
 impl From<Fixture> for FileMeta {
@@ -247,6 +254,7 @@ impl From<Fixture> for FileMeta {
                 .as_ref()
                 .map_or(Edition::Edition2018, |v| Edition::from_str(&v).unwrap()),
             env: f.env.into_iter().collect(),
+            introduce_new_source_root: f.introduce_new_source_root,
         }
     }
 }
diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs
index b5f7e4200..d0def2181 100644
--- a/crates/base_db/src/input.rs
+++ b/crates/base_db/src/input.rs
@@ -274,6 +274,33 @@ impl CrateGraph {
         deps.into_iter()
     }
 
+    /// Returns an iterator over all transitive reverse dependencies of the given crate.
+    pub fn transitive_reverse_dependencies(
+        &self,
+        of: CrateId,
+    ) -> impl Iterator<Item = CrateId> + '_ {
+        let mut worklist = vec![of];
+        let mut rev_deps = FxHashSet::default();
+        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))
+        });
+
+        while let Some(krate) = worklist.pop() {
+            if let Some(krate_rev_deps) = inverted_graph.get(&krate) {
+                krate_rev_deps
+                    .iter()
+                    .copied()
+                    .filter(|&rev_dep| rev_deps.insert(rev_dep))
+                    .for_each(|rev_dep| worklist.push(rev_dep));
+            }
+        }
+
+        rev_deps.into_iter()
+    }
+
     /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
     /// come before the crate itself).
     pub fn crates_in_topological_order(&self) -> Vec<CrateId> {
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index f0bc2c7b9..ad79a79f8 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -60,6 +60,7 @@ use hir_ty::{
     InEnvironment, Interner, Obligation, ProjectionPredicate, ProjectionTy, Scalar, Substs, Ty,
     TyDefId, TyKind, TyVariableKind,
 };
+use itertools::Itertools;
 use rustc_hash::FxHashSet;
 use stdx::{format_to, impl_from};
 use syntax::{
@@ -141,7 +142,6 @@ impl Crate {
             .collect()
     }
 
-    // FIXME: add `transitive_reverse_dependencies`.
     pub fn reverse_dependencies(self, db: &dyn HirDatabase) -> Vec<Crate> {
         let crate_graph = db.crate_graph();
         crate_graph
@@ -153,6 +153,14 @@ impl Crate {
             .collect()
     }
 
+    pub fn transitive_reverse_dependencies(self, db: &dyn HirDatabase) -> Vec<Crate> {
+        db.crate_graph()
+            .transitive_reverse_dependencies(self.id)
+            .into_iter()
+            .map(|id| Crate { id })
+            .collect()
+    }
+
     pub fn root_module(self, db: &dyn HirDatabase) -> Module {
         let def_map = db.crate_def_map(self.id);
         Module { id: def_map.module_id(def_map.root()) }
@@ -1541,11 +1549,17 @@ impl Impl {
         };
 
         let mut all = Vec::new();
-        def_crates.into_iter().for_each(|id| {
+        def_crates.iter().for_each(|&id| {
             all.extend(db.inherent_impls_in_crate(id).all_impls().map(Self::from).filter(filter))
         });
         let fp = TyFingerprint::for_impl(&ty.value);
-        for id in db.crate_graph().iter() {
+        for id in def_crates
+            .iter()
+            .flat_map(|&id| Crate { id }.transitive_reverse_dependencies(db))
+            .map(|Crate { id }| id)
+            .chain(def_crates.iter().copied())
+            .unique()
+        {
             match fp {
                 Some(fp) => all.extend(
                     db.trait_impls_in_crate(id).for_self_ty(fp).map(Self::from).filter(filter),
@@ -1560,7 +1574,8 @@ impl Impl {
     pub fn all_for_trait(db: &dyn HirDatabase, trait_: Trait) -> Vec<Impl> {
         let krate = trait_.module(db).krate();
         let mut all = Vec::new();
-        for Crate { id } in krate.reverse_dependencies(db).into_iter().chain(Some(krate)) {
+        for Crate { id } in krate.transitive_reverse_dependencies(db).into_iter().chain(Some(krate))
+        {
             let impls = db.trait_impls_in_crate(id);
             all.extend(impls.for_trait(trait_.id).map(Self::from))
         }
diff --git a/crates/ide/src/display.rs b/crates/ide/src/display.rs
index 1f7b665c0..71e97d6b4 100644
--- a/crates/ide/src/display.rs
+++ b/crates/ide/src/display.rs
@@ -2,8 +2,7 @@
 //! into types that may be used to render in a UI.
 
 pub(crate) mod navigation_target;
-mod short_label;
 
 pub(crate) use navigation_target::{ToNav, TryToNav};
 
-pub(crate) use syntax::display::{function_declaration, macro_label};
+pub(crate) use syntax::display::macro_label;
diff --git a/crates/ide/src/display/navigation_target.rs b/crates/ide/src/display/navigation_target.rs
index 69c3751a1..c086de163 100644
--- a/crates/ide/src/display/navigation_target.rs
+++ b/crates/ide/src/display/navigation_target.rs
@@ -5,9 +5,10 @@ use std::fmt;
 use either::Either;
 use hir::{
     AssocItem, Documentation, FieldSource, HasAttrs, HasSource, HirDisplay, InFile, ModuleSource,
+    Semantics,
 };
 use ide_db::{
-    base_db::{FileId, FileRange, SourceDatabase},
+    base_db::{FileId, FileRange},
     symbol_index::FileSymbolKind,
     SymbolKind,
 };
@@ -19,8 +20,6 @@ use syntax::{
 
 use crate::FileSymbol;
 
-use super::short_label::ShortLabel;
-
 /// `NavigationTarget` represents and element in the editor's UI which you can
 /// click on to navigate to a particular piece of code.
 ///
@@ -502,21 +501,22 @@ impl TryToNav for hir::ConstParam {
 ///
 /// e.g. `struct Name`, `enum Name`, `fn Name`
 pub(crate) fn description_from_symbol(db: &RootDatabase, symbol: &FileSymbol) -> Option<String> {
-    let parse = db.parse(symbol.file_id);
-    let node = symbol.ptr.to_node(parse.tree().syntax());
+    let sema = Semantics::new(db);
+    let parse = sema.parse(symbol.file_id);
+    let node = symbol.ptr.to_node(parse.syntax());
 
     match_ast! {
         match node {
-            ast::Fn(it) => it.short_label(),
-            ast::Struct(it) => it.short_label(),
-            ast::Enum(it) => it.short_label(),
-            ast::Trait(it) => it.short_label(),
-            ast::Module(it) => it.short_label(),
-            ast::TypeAlias(it) => it.short_label(),
-            ast::Const(it) => it.short_label(),
-            ast::Static(it) => it.short_label(),
-            ast::RecordField(it) => it.short_label(),
-            ast::Variant(it) => it.short_label(),
+            ast::Fn(it) => sema.to_def(&it).map(|it| it.display(db).to_string()),
+            ast::Struct(it) => sema.to_def(&it).map(|it| it.display(db).to_string()),
+            ast::Enum(it) => sema.to_def(&it).map(|it| it.display(db).to_string()),
+            ast::Trait(it) => sema.to_def(&it).map(|it| it.display(db).to_string()),
+            ast::Module(it) => sema.to_def(&it).map(|it| it.display(db).to_string()),
+            ast::TypeAlias(it) => sema.to_def(&it).map(|it| it.display(db).to_string()),
+            ast::Const(it) => sema.to_def(&it).map(|it| it.display(db).to_string()),
+            ast::Static(it) => sema.to_def(&it).map(|it| it.display(db).to_string()),
+            ast::RecordField(it) => sema.to_def(&it).map(|it| it.display(db).to_string()),
+            ast::Variant(it) => sema.to_def(&it).map(|it| it.display(db).to_string()),
             _ => None,
         }
     }
diff --git a/crates/ide/src/display/short_label.rs b/crates/ide/src/display/short_label.rs
deleted file mode 100644
index 2df9266b4..000000000
--- a/crates/ide/src/display/short_label.rs
+++ /dev/null
@@ -1,128 +0,0 @@
-//! FIXME: write short doc here
-
-use stdx::format_to;
-use syntax::ast::{self, AstNode, NameOwner, VisibilityOwner};
-
-pub(crate) trait ShortLabel {
-    fn short_label(&self) -> Option<String>;
-}
-
-impl ShortLabel for ast::Fn {
-    fn short_label(&self) -> Option<String> {
-        Some(crate::display::function_declaration(self))
-    }
-}
-
-impl ShortLabel for ast::Struct {
-    fn short_label(&self) -> Option<String> {
-        short_label_from_node(self, "struct ")
-    }
-}
-
-impl ShortLabel for ast::Union {
-    fn short_label(&self) -> Option<String> {
-        short_label_from_node(self, "union ")
-    }
-}
-
-impl ShortLabel for ast::Enum {
-    fn short_label(&self) -> Option<String> {
-        short_label_from_node(self, "enum ")
-    }
-}
-
-impl ShortLabel for ast::Trait {
-    fn short_label(&self) -> Option<String> {
-        if self.unsafe_token().is_some() {
-            short_label_from_node(self, "unsafe trait ")
-        } else {
-            short_label_from_node(self, "trait ")
-        }
-    }
-}
-
-impl ShortLabel for ast::Module {
-    fn short_label(&self) -> Option<String> {
-        short_label_from_node(self, "mod ")
-    }
-}
-
-impl ShortLabel for ast::SourceFile {
-    fn short_label(&self) -> Option<String> {
-        None
-    }
-}
-
-impl ShortLabel for ast::BlockExpr {
-    fn short_label(&self) -> Option<String> {
-        None
-    }
-}
-
-impl ShortLabel for ast::TypeAlias {
-    fn short_label(&self) -> Option<String> {
-        let mut buf = short_label_from_node(self, "type ")?;
-        if let Some(type_ref) = self.ty() {
-            format_to!(buf, " = {}", type_ref.syntax());
-        }
-        Some(buf)
-    }
-}
-
-impl ShortLabel for ast::Const {
-    fn short_label(&self) -> Option<String> {
-        short_label_from_ty(self, self.ty(), "const ")
-    }
-}
-
-impl ShortLabel for ast::Static {
-    fn short_label(&self) -> Option<String> {
-        short_label_from_ty(self, self.ty(), "static ")
-    }
-}
-
-impl ShortLabel for ast::RecordField {
-    fn short_label(&self) -> Option<String> {
-        short_label_from_ty(self, self.ty(), "")
-    }
-}
-
-impl ShortLabel for ast::Variant {
-    fn short_label(&self) -> Option<String> {
-        Some(self.name()?.text().to_string())
-    }
-}
-
-impl ShortLabel for ast::ConstParam {
-    fn short_label(&self) -> Option<String> {
-        let mut buf = "const ".to_owned();
-        buf.push_str(self.name()?.text());
-        if let Some(type_ref) = self.ty() {
-            format_to!(buf, ": {}", type_ref.syntax());
-        }
-        Some(buf)
-    }
-}
-
-fn short_label_from_ty<T>(node: &T, ty: Option<ast::Type>, prefix: &str) -> Option<String>
-where
-    T: NameOwner + VisibilityOwner,
-{
-    let mut buf = short_label_from_node(node, prefix)?;
-
-    if let Some(type_ref) = ty {
-        format_to!(buf, ": {}", type_ref.syntax());
-    }
-
-    Some(buf)
-}
-
-fn short_label_from_node<T>(node: &T, label: &str) -> Option<String>
-where
-    T: NameOwner + VisibilityOwner,
-{
-    let mut buf = node.visibility().map(|v| format!("{} ", v.syntax())).unwrap_or_default();
-    buf.push_str(label);
-    buf.push_str(node.name()?.text());
-    Some(buf)
-}
diff --git a/crates/ide/src/references.rs b/crates/ide/src/references.rs
index e8a5666bc..379674530 100644
--- a/crates/ide/src/references.rs
+++ b/crates/ide/src/references.rs
@@ -1271,4 +1271,27 @@ fn foo(_: bool) -> bo$0ol { true }
             "#]],
         );
     }
+
+    #[test]
+    fn test_transitive() {
+        check(
+            r#"
+//- /level3.rs new_source_root: crate:level3
+pub struct Fo$0o;
+//- /level2.rs new_source_root: crate:level2 deps:level3
+pub use level3::Foo;
+//- /level1.rs new_source_root: crate:level1 deps:level2
+pub use level2::Foo;
+//- /level0.rs new_source_root: crate:level0 deps:level1
+pub use level1::Foo;
+"#,
+            expect![[r#"
+                Foo Struct FileId(0) 0..15 11..14
+
+                FileId(1) 16..19
+                FileId(2) 16..19
+                FileId(3) 16..19
+            "#]],
+        );
+    }
 }
diff --git a/crates/ide_db/src/search.rs b/crates/ide_db/src/search.rs
index d00a8b6e7..f56221a6c 100644
--- a/crates/ide_db/src/search.rs
+++ b/crates/ide_db/src/search.rs
@@ -260,7 +260,7 @@ impl Definition {
             let mut res = source_root.iter().map(|id| (id, None)).collect::<FxHashMap<_, _>>();
 
             let krate = module.krate();
-            for rev_dep in krate.reverse_dependencies(db) {
+            for rev_dep in krate.transitive_reverse_dependencies(db) {
                 let root_file = rev_dep.root_file(db);
                 let source_root_id = db.file_source_root(root_file);
                 let source_root = db.source_root(source_root_id);
diff --git a/crates/test_utils/src/fixture.rs b/crates/test_utils/src/fixture.rs
index e3f57f3b2..6bc824e94 100644
--- a/crates/test_utils/src/fixture.rs
+++ b/crates/test_utils/src/fixture.rs
@@ -14,6 +14,7 @@ pub struct Fixture {
     pub cfg_key_values: Vec<(String, String)>,
     pub edition: Option<String>,
     pub env: FxHashMap<String, String>,
+    pub introduce_new_source_root: bool,
 }
 
 impl Fixture {
@@ -70,6 +71,7 @@ impl Fixture {
         let mut cfg_atoms = Vec::new();
         let mut cfg_key_values = Vec::new();
         let mut env = FxHashMap::default();
+        let mut introduce_new_source_root = false;
         for component in components[1..].iter() {
             let (key, value) = split_once(component, ':').unwrap();
             match key {
@@ -91,11 +93,22 @@ impl Fixture {
                         }
                     }
                 }
+                "new_source_root" => introduce_new_source_root = true,
                 _ => panic!("bad component: {:?}", component),
             }
         }
 
-        Fixture { path, text: String::new(), krate, deps, cfg_atoms, cfg_key_values, edition, env }
+        Fixture {
+            path,
+            text: String::new(),
+            krate,
+            deps,
+            cfg_atoms,
+            cfg_key_values,
+            edition,
+            env,
+            introduce_new_source_root,
+        }
     }
 }