2 files changed, 122 insertions, 12 deletions

diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs
index 1ddf5fca6..cc686ea6a 100644
--- a/crates/ra_hir_def/src/find_path.rs
+++ b/crates/ra_hir_def/src/find_path.rs
@@ -1,18 +1,35 @@
 //! An algorithm to find a path to refer to a certain item.
 
-use crate::{ModuleDefId, path::ModPath, ModuleId};
+use crate::{
+    db::DefDatabase,
+    item_scope::ItemInNs,
+    path::{ModPath, PathKind},
+    ModuleId,
+};
 
-pub fn find_path(item: ModuleDefId, from: ModuleId) -> ModPath {
+pub fn find_path(db: &impl DefDatabase, item: ItemInNs, from: ModuleId) -> ModPath {
+    // 1. Find all locations that the item could be imported from (i.e. that are visible)
+    //    - this needs to consider other crates, for reexports from transitive dependencies
+    //    - filter by visibility
+    // 2. For each of these, go up the module tree until we find an
+    //    item/module/crate that is already in scope (including because it is in
+    //    the prelude, and including aliases!)
+    // 3. Then select the one that gives the shortest path
+    let def_map = db.crate_def_map(from.krate);
+    let from_scope: &crate::item_scope::ItemScope = &def_map.modules[from.local_id].scope;
+    if let Some((name, _)) = from_scope.reverse_get(item) {
+        return ModPath::from_simple_segments(PathKind::Plain, vec![name.clone()]);
+    }
     todo!()
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
-    use ra_db::{fixture::WithFixture, SourceDatabase};
-    use crate::{db::DefDatabase, test_db::TestDB};
-    use ra_syntax::ast::AstNode;
+    use crate::test_db::TestDB;
     use hir_expand::hygiene::Hygiene;
+    use ra_db::fixture::WithFixture;
+    use ra_syntax::ast::AstNode;
 
     /// `code` needs to contain a cursor marker; checks that `find_path` for the
     /// item the `path` refers to returns that same path when called from the
@@ -21,13 +38,26 @@ mod tests {
         let (db, pos) = TestDB::with_position(code);
         let module = db.module_for_file(pos.file_id);
         let parsed_path_file = ra_syntax::SourceFile::parse(&format!("use {};", path));
-        let ast_path = parsed_path_file.syntax_node().descendants().find_map(ra_syntax::ast::Path::cast).unwrap();
+        let ast_path = parsed_path_file
+            .syntax_node()
+            .descendants()
+            .find_map(ra_syntax::ast::Path::cast)
+            .unwrap();
         let mod_path = ModPath::from_src(ast_path, &Hygiene::new_unhygienic()).unwrap();
 
         let crate_def_map = db.crate_def_map(module.krate);
-        let resolved = crate_def_map.resolve_path(&db, module.local_id, &mod_path, crate::item_scope::BuiltinShadowMode::Module).0.take_types().unwrap();
+        let resolved = crate_def_map
+            .resolve_path(
+                &db,
+                module.local_id,
+                &mod_path,
+                crate::item_scope::BuiltinShadowMode::Module,
+            )
+            .0
+            .take_types()
+            .unwrap();
 
-        let found_path = find_path(resolved, module);
+        let found_path = find_path(&db, ItemInNs::Types(resolved), module);
 
         assert_eq!(mod_path, found_path);
     }
@@ -35,10 +65,58 @@ mod tests {
     #[test]
     fn same_module() {
         let code = r#"
-//- /main.rs
-struct S;
-<|>
-"#;
+            //- /main.rs
+            struct S;
+            <|>
+        "#;
         check_found_path(code, "S");
     }
+
+    #[test]
+    fn sub_module() {
+        let code = r#"
+            //- /main.rs
+            mod foo {
+                pub struct S;
+            }
+            <|>
+        "#;
+        check_found_path(code, "foo::S");
+    }
+
+    #[test]
+    fn same_crate() {
+        let code = r#"
+            //- /main.rs
+            mod foo;
+            struct S;
+            //- /foo.rs
+            <|>
+        "#;
+        check_found_path(code, "crate::S");
+    }
+
+    #[test]
+    fn different_crate() {
+        let code = r#"
+            //- /main.rs crate:main deps:std
+            <|>
+            //- /std.rs crate:std
+            pub struct S;
+        "#;
+        check_found_path(code, "std::S");
+    }
+
+    #[test]
+    fn same_crate_reexport() {
+        let code = r#"
+            //- /main.rs
+            mod bar {
+                mod foo { pub(super) struct S; }
+                pub(crate) use foo::*;
+            }
+            <|>
+        "#;
+        check_found_path(code, "bar::S");
+    }
 }
diff --git a/crates/ra_hir_def/src/item_scope.rs b/crates/ra_hir_def/src/item_scope.rs
index fe7bb9779..f88502d78 100644
--- a/crates/ra_hir_def/src/item_scope.rs
+++ b/crates/ra_hir_def/src/item_scope.rs
@@ -104,6 +104,15 @@ impl ItemScope {
         }
     }
 
+    pub(crate) fn reverse_get(&self, item: ItemInNs) -> Option<(&Name, Visibility)> {
+        for (name, per_ns) in &self.visible {
+            if let Some(vis) = item.match_with(*per_ns) {
+                return Some((name, vis));
+            }
+        }
+        None
+    }
+
     pub(crate) fn traits<'a>(&'a self) -> impl Iterator<Item = TraitId> + 'a {
         self.visible.values().filter_map(|def| match def.take_types() {
             Some(ModuleDefId::TraitId(t)) => Some(t),
@@ -173,3 +182,26 @@ impl PerNs {
         }
     }
 }
+
+#[derive(Clone, Copy, PartialEq, Eq)]
+pub enum ItemInNs {
+    Types(ModuleDefId),
+    Values(ModuleDefId),
+    Macros(MacroDefId),
+}
+
+impl ItemInNs {
+    fn match_with(self, per_ns: PerNs) -> Option<Visibility> {
+        match self {
+            ItemInNs::Types(def) => {
+                per_ns.types.filter(|(other_def, _)| *other_def == def).map(|(_, vis)| vis)
+            },
+            ItemInNs::Values(def) => {
+                per_ns.values.filter(|(other_def, _)| *other_def == def).map(|(_, vis)| vis)
+            },
+            ItemInNs::Macros(def) => {
+                per_ns.macros.filter(|(other_def, _)| *other_def == def).map(|(_, vis)| vis)
+            },
+        }
+    }
+}