1 files changed, 163 insertions, 84 deletions

diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs
index 4db798473..06701a830 100644
--- a/crates/ra_hir_def/src/find_path.rs
+++ b/crates/ra_hir_def/src/find_path.rs
@@ -1,9 +1,8 @@
 //! An algorithm to find a path to refer to a certain item.
 
-use std::sync::Arc;
-
 use hir_expand::name::{known, AsName, Name};
 use ra_prof::profile;
+use rustc_hash::FxHashSet;
 use test_utils::mark;
 
 use crate::{
@@ -11,7 +10,7 @@ use crate::{
     item_scope::ItemInNs,
     path::{ModPath, PathKind},
     visibility::Visibility,
-    CrateId, ModuleDefId, ModuleId,
+    ModuleDefId, ModuleId,
 };
 
 // FIXME: handle local items
@@ -20,7 +19,7 @@ use crate::{
 /// *from where* you're referring to the item, hence the `from` parameter.
 pub fn find_path(db: &dyn DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> {
     let _p = profile("find_path");
-    db.find_path_inner(item, from, MAX_PATH_LEN)
+    find_path_inner(db, item, from, MAX_PATH_LEN)
 }
 
 const MAX_PATH_LEN: usize = 15;
@@ -36,20 +35,9 @@ impl ModPath {
         let first_segment = self.segments.first();
         first_segment == Some(&known::alloc) || first_segment == Some(&known::core)
     }
-
-    fn len(&self) -> usize {
-        self.segments.len()
-            + match self.kind {
-                PathKind::Plain => 0,
-                PathKind::Super(i) => i as usize,
-                PathKind::Crate => 1,
-                PathKind::Abs => 0,
-                PathKind::DollarCrate(_) => 1,
-            }
-    }
 }
 
-pub(crate) fn find_path_inner_query(
+fn find_path_inner(
     db: &dyn DefDatabase,
     item: ItemInNs,
     from: ModuleId,
@@ -133,31 +121,67 @@ pub(crate) fn find_path_inner_query(
     }
 
     // - otherwise, look for modules containing (reexporting) it and import it from one of those
+
     let crate_root = ModuleId { local_id: def_map.root, krate: from.krate };
     let crate_attrs = db.attrs(crate_root.into());
     let prefer_no_std = crate_attrs.by_key("no_std").exists();
-    let importable_locations = find_importable_locations(db, item, from);
     let mut best_path = None;
     let mut best_path_len = max_len;
-    for (module_id, name) in importable_locations {
-        let mut path = match db.find_path_inner(
-            ItemInNs::Types(ModuleDefId::ModuleId(module_id)),
-            from,
-            best_path_len - 1,
-        ) {
-            None => continue,
-            Some(path) => path,
-        };
-        path.segments.push(name);
 
-        let new_path = if let Some(best_path) = best_path {
-            select_best_path(best_path, path, prefer_no_std)
-        } else {
-            path
-        };
-        best_path_len = new_path.len();
-        best_path = Some(new_path);
+    if item.krate(db) == Some(from.krate) {
+        // Item was defined in the same crate that wants to import it. It cannot be found in any
+        // dependency in this case.
+
+        let local_imports = find_local_import_locations(db, item, from);
+        for (module_id, name) in local_imports {
+            if let Some(mut path) = find_path_inner(
+                db,
+                ItemInNs::Types(ModuleDefId::ModuleId(module_id)),
+                from,
+                best_path_len - 1,
+            ) {
+                path.segments.push(name);
+
+                let new_path = if let Some(best_path) = best_path {
+                    select_best_path(best_path, path, prefer_no_std)
+                } else {
+                    path
+                };
+                best_path_len = new_path.len();
+                best_path = Some(new_path);
+            }
+        }
+    } else {
+        // Item was defined in some upstream crate. This means that it must be exported from one,
+        // too (unless we can't name it at all). It could *also* be (re)exported by the same crate
+        // that wants to import it here, but we always prefer to use the external path here.
+
+        let crate_graph = db.crate_graph();
+        let extern_paths = crate_graph[from.krate].dependencies.iter().filter_map(|dep| {
+            let import_map = db.import_map(dep.crate_id);
+            import_map.import_info_for(item).and_then(|info| {
+                // Determine best path for containing module and append last segment from `info`.
+                let mut path = find_path_inner(
+                    db,
+                    ItemInNs::Types(ModuleDefId::ModuleId(info.container)),
+                    from,
+                    best_path_len - 1,
+                )?;
+                path.segments.push(info.path.segments.last().unwrap().clone());
+                Some(path)
+            })
+        });
+
+        for path in extern_paths {
+            let new_path = if let Some(best_path) = best_path {
+                select_best_path(best_path, path, prefer_no_std)
+            } else {
+                path
+            };
+            best_path = Some(new_path);
+        }
     }
+
     best_path
 }
 
@@ -185,69 +209,86 @@ fn select_best_path(old_path: ModPath, new_path: ModPath, prefer_no_std: bool) -
     }
 }
 
-fn find_importable_locations(
+/// Finds locations in `from.krate` from which `item` can be imported by `from`.
+fn find_local_import_locations(
     db: &dyn DefDatabase,
     item: ItemInNs,
     from: ModuleId,
 ) -> Vec<(ModuleId, Name)> {
-    let crate_graph = db.crate_graph();
-    let mut result = Vec::new();
-    // We only look in the crate from which we are importing, and the direct
-    // dependencies. We cannot refer to names from transitive dependencies
-    // directly (only through reexports in direct dependencies).
-    for krate in Some(from.krate)
-        .into_iter()
-        .chain(crate_graph[from.krate].dependencies.iter().map(|dep| dep.crate_id))
-    {
-        result.extend(
-            db.importable_locations_of(item, krate)
-                .iter()
-                .filter(|(_, _, vis)| vis.is_visible_from(db, from))
-                .map(|(m, n, _)| (*m, n.clone())),
-        );
-    }
-    result
-}
+    let _p = profile("find_local_import_locations");
+
+    // `from` can import anything below `from` with visibility of at least `from`, and anything
+    // above `from` with any visibility. That means we do not need to descend into private siblings
+    // of `from` (and similar).
+
+    let def_map = db.crate_def_map(from.krate);
+
+    // Compute the initial worklist. We start with all direct child modules of `from` as well as all
+    // of its (recursive) parent modules.
+    let data = &def_map.modules[from.local_id];
+    let mut worklist = data
+        .children
+        .values()
+        .map(|child| ModuleId { krate: from.krate, local_id: *child })
+        .collect::<Vec<_>>();
+    let mut parent = data.parent;
+    while let Some(p) = parent {
+        worklist.push(ModuleId { krate: from.krate, local_id: p });
+        parent = def_map.modules[p].parent;
+    }
+
+    let mut seen: FxHashSet<_> = FxHashSet::default();
+
+    let mut locations = Vec::new();
+    while let Some(module) = worklist.pop() {
+        if !seen.insert(module) {
+            continue; // already processed this module
+        }
+
+        let ext_def_map;
+        let data = if module.krate == from.krate {
+            &def_map[module.local_id]
+        } else {
+            // The crate might reexport a module defined in another crate.
+            ext_def_map = db.crate_def_map(module.krate);
+            &ext_def_map[module.local_id]
+        };
 
-/// Collects all locations from which we might import the item in a particular
-/// crate. These include the original definition of the item, and any
-/// non-private `use`s.
-///
-/// Note that the crate doesn't need to be the one in which the item is defined;
-/// it might be re-exported in other crates.
-pub(crate) fn importable_locations_of_query(
-    db: &dyn DefDatabase,
-    item: ItemInNs,
-    krate: CrateId,
-) -> Arc<[(ModuleId, Name, Visibility)]> {
-    let _p = profile("importable_locations_of_query");
-    let def_map = db.crate_def_map(krate);
-    let mut result = Vec::new();
-    for (local_id, data) in def_map.modules.iter() {
         if let Some((name, vis)) = data.scope.name_of(item) {
-            let is_private = if let Visibility::Module(private_to) = vis {
-                private_to.local_id == local_id
-            } else {
-                false
-            };
-            let is_original_def = if let Some(module_def_id) = item.as_module_def_id() {
-                data.scope.declarations().any(|it| it == module_def_id)
-            } else {
-                false
-            };
-            if is_private && !is_original_def {
+            if vis.is_visible_from(db, from) {
+                let is_private = if let Visibility::Module(private_to) = vis {
+                    private_to.local_id == module.local_id
+                } else {
+                    false
+                };
+                let is_original_def = if let Some(module_def_id) = item.as_module_def_id() {
+                    data.scope.declarations().any(|it| it == module_def_id)
+                } else {
+                    false
+                };
+
                 // Ignore private imports. these could be used if we are
                 // in a submodule of this module, but that's usually not
                 // what the user wants; and if this module can import
                 // the item and we're a submodule of it, so can we.
                 // Also this keeps the cached data smaller.
-                continue;
+                if !is_private || is_original_def {
+                    locations.push((module, name.clone()));
+                }
+            }
+        }
+
+        // Descend into all modules visible from `from`.
+        for (_, per_ns) in data.scope.entries() {
+            if let Some((ModuleDefId::ModuleId(module), vis)) = per_ns.take_types_vis() {
+                if vis.is_visible_from(db, from) {
+                    worklist.push(module);
+                }
             }
-            result.push((ModuleId { krate, local_id }, name.clone(), vis));
         }
     }
 
-    Arc::from(result)
+    locations
 }
 
 #[cfg(test)]
@@ -264,8 +305,8 @@ mod tests {
     /// `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
     /// module the cursor is in.
-    fn check_found_path(code: &str, path: &str) {
-        let (db, pos) = TestDB::with_position(code);
+    fn check_found_path(ra_fixture: &str, path: &str) {
+        let (db, pos) = TestDB::with_position(ra_fixture);
         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
@@ -396,6 +437,44 @@ mod tests {
     }
 
     #[test]
+    fn partially_imported() {
+        // Tests that short paths are used even for external items, when parts of the path are
+        // already in scope.
+        check_found_path(
+            r#"
+            //- /main.rs crate:main deps:ra_syntax
+
+            use ra_syntax::ast;
+            <|>
+
+            //- /lib.rs crate:ra_syntax
+            pub mod ast {
+                pub enum ModuleItem {
+                    A, B, C,
+                }
+            }
+        "#,
+            "ast::ModuleItem",
+        );
+
+        check_found_path(
+            r#"
+            //- /main.rs crate:main deps:ra_syntax
+
+            <|>
+
+            //- /lib.rs crate:ra_syntax
+            pub mod ast {
+                pub enum ModuleItem {
+                    A, B, C,
+                }
+            }
+        "#,
+            "ra_syntax::ast::ModuleItem",
+        );
+    }
+
+    #[test]
     fn same_crate_reexport() {
         let code = r#"
             //- /main.rs