Merge branch 'master' into keyword_completion

# Conflicts:
#	docs/user/generated_features.adoc

14 files changed, 999 insertions, 157 deletions

diff --git a/crates/ra_hir_def/src/attr.rs b/crates/ra_hir_def/src/attr.rs
index 8b6c0bede..2eeba0572 100644
--- a/crates/ra_hir_def/src/attr.rs
+++ b/crates/ra_hir_def/src/attr.rs
@@ -87,12 +87,18 @@ impl Attrs {
     }
 
     pub(crate) fn new(owner: &dyn AttrsOwner, hygiene: &Hygiene) -> Attrs {
+        let docs = ast::CommentIter::from_syntax_node(owner.syntax()).doc_comment_text().map(
+            |docs_text| Attr {
+                input: Some(AttrInput::Literal(SmolStr::new(docs_text))),
+                path: ModPath::from(hir_expand::name!(doc)),
+            },
+        );
         let mut attrs = owner.attrs().peekable();
         let entries = if attrs.peek().is_none() {
             // Avoid heap allocation
             None
         } else {
-            Some(attrs.flat_map(|ast| Attr::from_src(ast, hygiene)).collect())
+            Some(attrs.flat_map(|ast| Attr::from_src(ast, hygiene)).chain(docs).collect())
         };
         Attrs { entries }
     }
diff --git a/crates/ra_hir_def/src/body.rs b/crates/ra_hir_def/src/body.rs
index 273036cee..4f2350915 100644
--- a/crates/ra_hir_def/src/body.rs
+++ b/crates/ra_hir_def/src/body.rs
@@ -97,7 +97,7 @@ impl Expander {
 
         let macro_call = InFile::new(self.current_file_id, &macro_call);
 
-        if let Some(call_id) = macro_call.as_call_id(db, |path| {
+        if let Some(call_id) = macro_call.as_call_id(db, self.crate_def_map.krate, |path| {
             if let Some(local_scope) = local_scope {
                 if let Some(def) = path.as_ident().and_then(|n| local_scope.get_legacy_macro(n)) {
                     return Some(def);
diff --git a/crates/ra_hir_def/src/data.rs b/crates/ra_hir_def/src/data.rs
index e2130d931..53599e74a 100644
--- a/crates/ra_hir_def/src/data.rs
+++ b/crates/ra_hir_def/src/data.rs
@@ -34,6 +34,7 @@ pub struct FunctionData {
     /// True if the first param is `self`. This is relevant to decide whether this
     /// can be called as a method.
     pub has_self_param: bool,
+    pub is_unsafe: bool,
     pub visibility: RawVisibility,
 }
 
@@ -85,17 +86,20 @@ impl FunctionData {
             ret_type
         };
 
+        let is_unsafe = src.value.unsafe_token().is_some();
+
         let vis_default = RawVisibility::default_for_container(loc.container);
         let visibility =
             RawVisibility::from_ast_with_default(db, vis_default, src.map(|s| s.visibility()));
 
-        let sig = FunctionData { name, params, ret_type, has_self_param, visibility, attrs };
+        let sig =
+            FunctionData { name, params, ret_type, has_self_param, is_unsafe, visibility, attrs };
         Arc::new(sig)
     }
 }
 
 fn desugar_future_path(orig: TypeRef) -> Path {
-    let path = path![std::future::Future];
+    let path = path![core::future::Future];
     let mut generic_args: Vec<_> = std::iter::repeat(None).take(path.segments.len() - 1).collect();
     let mut last = GenericArgs::empty();
     last.bindings.push(AssociatedTypeBinding {
diff --git a/crates/ra_hir_def/src/db.rs b/crates/ra_hir_def/src/db.rs
index 945a0025e..10cc26480 100644
--- a/crates/ra_hir_def/src/db.rs
+++ b/crates/ra_hir_def/src/db.rs
@@ -1,7 +1,7 @@
 //! Defines database & queries for name resolution.
 use std::sync::Arc;
 
-use hir_expand::{db::AstDatabase, name::Name, HirFileId};
+use hir_expand::{db::AstDatabase, HirFileId};
 use ra_db::{salsa, CrateId, SourceDatabase, Upcast};
 use ra_prof::profile;
 use ra_syntax::SmolStr;
@@ -12,13 +12,10 @@ use crate::{
     body::{scope::ExprScopes, Body, BodySourceMap},
     data::{ConstData, FunctionData, ImplData, StaticData, TraitData, TypeAliasData},
     docs::Documentation,
-    find_path,
     generics::GenericParams,
-    item_scope::ItemInNs,
+    import_map::ImportMap,
     lang_item::{LangItemTarget, LangItems},
     nameres::{raw::RawItems, CrateDefMap},
-    path::ModPath,
-    visibility::Visibility,
     AttrDefId, ConstId, ConstLoc, DefWithBodyId, EnumId, EnumLoc, FunctionId, FunctionLoc,
     GenericDefId, ImplId, ImplLoc, ModuleId, StaticId, StaticLoc, StructId, StructLoc, TraitId,
     TraitLoc, TypeAliasId, TypeAliasLoc, UnionId, UnionLoc,
@@ -113,15 +110,8 @@ pub trait DefDatabase: InternDatabase + AstDatabase + Upcast<dyn AstDatabase> {
     #[salsa::invoke(Documentation::documentation_query)]
     fn documentation(&self, def: AttrDefId) -> Option<Documentation>;
 
-    #[salsa::invoke(find_path::importable_locations_of_query)]
-    fn importable_locations_of(
-        &self,
-        item: ItemInNs,
-        krate: CrateId,
-    ) -> Arc<[(ModuleId, Name, Visibility)]>;
-
-    #[salsa::invoke(find_path::find_path_inner_query)]
-    fn find_path_inner(&self, item: ItemInNs, from: ModuleId, max_len: usize) -> Option<ModPath>;
+    #[salsa::invoke(ImportMap::import_map_query)]
+    fn import_map(&self, krate: CrateId) -> Arc<ImportMap>;
 }
 
 fn crate_def_map_wait(db: &impl DefDatabase, krate: CrateId) -> Arc<CrateDefMap> {
diff --git a/crates/ra_hir_def/src/docs.rs b/crates/ra_hir_def/src/docs.rs
index b221ae1ce..2630b3d89 100644
--- a/crates/ra_hir_def/src/docs.rs
+++ b/crates/ra_hir_def/src/docs.rs
@@ -29,6 +29,13 @@ impl Documentation {
         Documentation(s.into())
     }
 
+    pub fn from_ast<N>(node: &N) -> Option<Documentation>
+    where
+        N: ast::DocCommentsOwner + ast::AttrsOwner,
+    {
+        docs_from_ast(node)
+    }
+
     pub fn as_str(&self) -> &str {
         &*self.0
     }
@@ -70,6 +77,45 @@ impl Documentation {
     }
 }
 
-pub(crate) fn docs_from_ast(node: &impl ast::DocCommentsOwner) -> Option<Documentation> {
-    node.doc_comment_text().map(|it| Documentation::new(&it))
+pub(crate) fn docs_from_ast<N>(node: &N) -> Option<Documentation>
+where
+    N: ast::DocCommentsOwner + ast::AttrsOwner,
+{
+    let doc_comment_text = node.doc_comment_text();
+    let doc_attr_text = expand_doc_attrs(node);
+    let docs = merge_doc_comments_and_attrs(doc_comment_text, doc_attr_text);
+    docs.map(|it| Documentation::new(&it))
+}
+
+fn merge_doc_comments_and_attrs(
+    doc_comment_text: Option<String>,
+    doc_attr_text: Option<String>,
+) -> Option<String> {
+    match (doc_comment_text, doc_attr_text) {
+        (Some(mut comment_text), Some(attr_text)) => {
+            comment_text.push_str("\n\n");
+            comment_text.push_str(&attr_text);
+            Some(comment_text)
+        }
+        (Some(comment_text), None) => Some(comment_text),
+        (None, Some(attr_text)) => Some(attr_text),
+        (None, None) => None,
+    }
+}
+
+fn expand_doc_attrs(owner: &dyn ast::AttrsOwner) -> Option<String> {
+    let mut docs = String::new();
+    for attr in owner.attrs() {
+        if let Some(("doc", value)) =
+            attr.as_simple_key_value().as_ref().map(|(k, v)| (k.as_str(), v.as_str()))
+        {
+            docs.push_str(value);
+            docs.push_str("\n\n");
+        }
+    }
+    if docs.is_empty() {
+        None
+    } else {
+        Some(docs.trim_end_matches("\n\n").to_owned())
+    }
 }
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
diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs
new file mode 100644
index 000000000..68e20d06b
--- /dev/null
+++ b/crates/ra_hir_def/src/import_map.rs
@@ -0,0 +1,679 @@
+//! A map of all publicly exported items in a crate.
+
+use std::{cmp::Ordering, fmt, hash::BuildHasherDefault, sync::Arc};
+
+use fst::{self, Streamer};
+use indexmap::{map::Entry, IndexMap};
+use ra_db::CrateId;
+use rustc_hash::FxHasher;
+
+use crate::{
+    db::DefDatabase,
+    item_scope::ItemInNs,
+    path::{ModPath, PathKind},
+    visibility::Visibility,
+    ModuleDefId, ModuleId,
+};
+
+type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
+
+/// Item import details stored in the `ImportMap`.
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub struct ImportInfo {
+    /// A path that can be used to import the item, relative to the crate's root.
+    pub path: ModPath,
+    /// The module containing this item.
+    pub container: ModuleId,
+}
+
+/// A map from publicly exported items to the path needed to import/name them from a downstream
+/// crate.
+///
+/// Reexports of items are taken into account, ie. if something is exported under multiple
+/// names, the one with the shortest import path will be used.
+///
+/// Note that all paths are relative to the containing crate's root, so the crate name still needs
+/// to be prepended to the `ModPath` before the path is valid.
+pub struct ImportMap {
+    map: FxIndexMap<ItemInNs, ImportInfo>,
+
+    /// List of keys stored in `map`, sorted lexicographically by their `ModPath`. Indexed by the
+    /// values returned by running `fst`.
+    ///
+    /// Since a path can refer to multiple items due to namespacing, we store all items with the
+    /// same path right after each other. This allows us to find all items after the FST gives us
+    /// the index of the first one.
+    importables: Vec<ItemInNs>,
+    fst: fst::Map<Vec<u8>>,
+}
+
+impl ImportMap {
+    pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
+        let _p = ra_prof::profile("import_map_query");
+        let def_map = db.crate_def_map(krate);
+        let mut import_map = FxIndexMap::with_capacity_and_hasher(64, Default::default());
+
+        // We look only into modules that are public(ly reexported), starting with the crate root.
+        let empty = ModPath { kind: PathKind::Plain, segments: vec![] };
+        let root = ModuleId { krate, local_id: def_map.root };
+        let mut worklist = vec![(root, empty)];
+        while let Some((module, mod_path)) = worklist.pop() {
+            let ext_def_map;
+            let mod_data = if module.krate == 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]
+            };
+
+            let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
+                let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
+                if per_ns.is_none() {
+                    None
+                } else {
+                    Some((name, per_ns))
+                }
+            });
+
+            for (name, per_ns) in visible_items {
+                let mk_path = || {
+                    let mut path = mod_path.clone();
+                    path.segments.push(name.clone());
+                    path
+                };
+
+                for item in per_ns.iter_items() {
+                    let path = mk_path();
+                    match import_map.entry(item) {
+                        Entry::Vacant(entry) => {
+                            entry.insert(ImportInfo { path, container: module });
+                        }
+                        Entry::Occupied(mut entry) => {
+                            // If the new path is shorter, prefer that one.
+                            if path.len() < entry.get().path.len() {
+                                *entry.get_mut() = ImportInfo { path, container: module };
+                            } else {
+                                continue;
+                            }
+                        }
+                    }
+
+                    // If we've just added a path to a module, descend into it. We might traverse
+                    // modules multiple times, but only if the new path to it is shorter than the
+                    // first (else we `continue` above).
+                    if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
+                        worklist.push((mod_id, mk_path()));
+                    }
+                }
+            }
+        }
+
+        let mut importables = import_map.iter().collect::<Vec<_>>();
+
+        importables.sort_by(cmp);
+
+        // Build the FST, taking care not to insert duplicate values.
+
+        let mut builder = fst::MapBuilder::memory();
+        let mut last_batch_start = 0;
+
+        for idx in 0..importables.len() {
+            if let Some(next_item) = importables.get(idx + 1) {
+                if cmp(&importables[last_batch_start], next_item) == Ordering::Equal {
+                    continue;
+                }
+            }
+
+            let start = last_batch_start;
+            last_batch_start = idx + 1;
+
+            let key = fst_path(&importables[start].1.path);
+
+            builder.insert(key, start as u64).unwrap();
+        }
+
+        let fst = fst::Map::new(builder.into_inner().unwrap()).unwrap();
+        let importables = importables.iter().map(|(item, _)| **item).collect();
+
+        Arc::new(Self { map: import_map, fst, importables })
+    }
+
+    /// Returns the `ModPath` needed to import/mention `item`, relative to this crate's root.
+    pub fn path_of(&self, item: ItemInNs) -> Option<&ModPath> {
+        Some(&self.map.get(&item)?.path)
+    }
+
+    pub fn import_info_for(&self, item: ItemInNs) -> Option<&ImportInfo> {
+        self.map.get(&item)
+    }
+}
+
+impl PartialEq for ImportMap {
+    fn eq(&self, other: &Self) -> bool {
+        // `fst` and `importables` are built from `map`, so we don't need to compare them.
+        self.map == other.map
+    }
+}
+
+impl Eq for ImportMap {}
+
+impl fmt::Debug for ImportMap {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let mut importable_paths: Vec<_> = self
+            .map
+            .iter()
+            .map(|(item, info)| {
+                let ns = match item {
+                    ItemInNs::Types(_) => "t",
+                    ItemInNs::Values(_) => "v",
+                    ItemInNs::Macros(_) => "m",
+                };
+                format!("- {} ({})", info.path, ns)
+            })
+            .collect();
+
+        importable_paths.sort();
+        f.write_str(&importable_paths.join("\n"))
+    }
+}
+
+fn fst_path(path: &ModPath) -> String {
+    let mut s = path.to_string();
+    s.make_ascii_lowercase();
+    s
+}
+
+fn cmp((_, lhs): &(&ItemInNs, &ImportInfo), (_, rhs): &(&ItemInNs, &ImportInfo)) -> Ordering {
+    let lhs_str = fst_path(&lhs.path);
+    let rhs_str = fst_path(&rhs.path);
+    lhs_str.cmp(&rhs_str)
+}
+
+#[derive(Debug)]
+pub struct Query {
+    query: String,
+    lowercased: String,
+    anchor_end: bool,
+    case_sensitive: bool,
+    limit: usize,
+}
+
+impl Query {
+    pub fn new(query: &str) -> Self {
+        Self {
+            lowercased: query.to_lowercase(),
+            query: query.to_string(),
+            anchor_end: false,
+            case_sensitive: false,
+            limit: usize::max_value(),
+        }
+    }
+
+    /// Only returns items whose paths end with the (case-insensitive) query string as their last
+    /// segment.
+    pub fn anchor_end(self) -> Self {
+        Self { anchor_end: true, ..self }
+    }
+
+    /// Limits the returned number of items to `limit`.
+    pub fn limit(self, limit: usize) -> Self {
+        Self { limit, ..self }
+    }
+
+    /// Respect casing of the query string when matching.
+    pub fn case_sensitive(self) -> Self {
+        Self { case_sensitive: true, ..self }
+    }
+}
+
+/// Searches dependencies of `krate` for an importable path matching `query`.
+///
+/// This returns a list of items that could be imported from dependencies of `krate`.
+pub fn search_dependencies<'a>(
+    db: &'a dyn DefDatabase,
+    krate: CrateId,
+    query: Query,
+) -> Vec<ItemInNs> {
+    let _p = ra_prof::profile("search_dependencies").detail(|| format!("{:?}", query));
+
+    let graph = db.crate_graph();
+    let import_maps: Vec<_> =
+        graph[krate].dependencies.iter().map(|dep| db.import_map(dep.crate_id)).collect();
+
+    let automaton = fst::automaton::Subsequence::new(&query.lowercased);
+
+    let mut op = fst::map::OpBuilder::new();
+    for map in &import_maps {
+        op = op.add(map.fst.search(&automaton));
+    }
+
+    let mut stream = op.union();
+    let mut res = Vec::new();
+    while let Some((_, indexed_values)) = stream.next() {
+        for indexed_value in indexed_values {
+            let import_map = &import_maps[indexed_value.index];
+            let importables = &import_map.importables[indexed_value.value as usize..];
+
+            // Path shared by the importable items in this group.
+            let path = &import_map.map[&importables[0]].path;
+
+            if query.anchor_end {
+                // Last segment must match query.
+                let last = path.segments.last().unwrap().to_string();
+                if last.to_lowercase() != query.lowercased {
+                    continue;
+                }
+            }
+
+            // Add the items from this `ModPath` group. Those are all subsequent items in
+            // `importables` whose paths match `path`.
+            let iter = importables.iter().copied().take_while(|item| {
+                let item_path = &import_map.map[item].path;
+                fst_path(item_path) == fst_path(path)
+            });
+
+            if query.case_sensitive {
+                // FIXME: This does not do a subsequence match.
+                res.extend(iter.filter(|item| {
+                    let item_path = &import_map.map[item].path;
+                    item_path.to_string().contains(&query.query)
+                }));
+            } else {
+                res.extend(iter);
+            }
+
+            if res.len() >= query.limit {
+                res.truncate(query.limit);
+                return res;
+            }
+        }
+    }
+
+    res
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::test_db::TestDB;
+    use insta::assert_snapshot;
+    use itertools::Itertools;
+    use ra_db::fixture::WithFixture;
+    use ra_db::{SourceDatabase, Upcast};
+
+    fn import_map(ra_fixture: &str) -> String {
+        let db = TestDB::with_files(ra_fixture);
+        let crate_graph = db.crate_graph();
+
+        let s = crate_graph
+            .iter()
+            .filter_map(|krate| {
+                let cdata = &crate_graph[krate];
+                let name = cdata.display_name.as_ref()?;
+
+                let map = db.import_map(krate);
+
+                Some(format!("{}:\n{:?}", name, map))
+            })
+            .join("\n");
+        s
+    }
+
+    fn search_dependencies_of(ra_fixture: &str, krate_name: &str, query: Query) -> String {
+        let db = TestDB::with_files(ra_fixture);
+        let crate_graph = db.crate_graph();
+        let krate = crate_graph
+            .iter()
+            .find(|krate| {
+                crate_graph[*krate].display_name.as_ref().map(|n| n.to_string())
+                    == Some(krate_name.to_string())
+            })
+            .unwrap();
+
+        search_dependencies(db.upcast(), krate, query)
+            .into_iter()
+            .filter_map(|item| {
+                let mark = match item {
+                    ItemInNs::Types(_) => "t",
+                    ItemInNs::Values(_) => "v",
+                    ItemInNs::Macros(_) => "m",
+                };
+                item.krate(db.upcast()).map(|krate| {
+                    let map = db.import_map(krate);
+                    let path = map.path_of(item).unwrap();
+                    format!(
+                        "{}::{} ({})",
+                        crate_graph[krate].display_name.as_ref().unwrap(),
+                        path,
+                        mark
+                    )
+                })
+            })
+            .join("\n")
+    }
+
+    #[test]
+    fn smoke() {
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+
+            mod private {
+                pub use lib::Pub;
+                pub struct InPrivateModule;
+            }
+
+            pub mod publ1 {
+                use lib::Pub;
+            }
+
+            pub mod real_pub {
+                pub use lib::Pub;
+            }
+            pub mod real_pu2 { // same path length as above
+                pub use lib::Pub;
+            }
+
+            //- /lib.rs crate:lib
+            pub struct Pub {}
+            pub struct Pub2; // t + v
+            struct Priv;
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - publ1 (t)
+        - real_pu2 (t)
+        - real_pub (t)
+        - real_pub::Pub (t)
+        lib:
+        - Pub (t)
+        - Pub2 (t)
+        - Pub2 (v)
+        "###);
+    }
+
+    #[test]
+    fn prefers_shortest_path() {
+        let map = import_map(
+            r"
+            //- /main.rs crate:main
+
+            pub mod sub {
+                pub mod subsub {
+                    pub struct Def {}
+                }
+
+                pub use super::sub::subsub::Def;
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - sub (t)
+        - sub::Def (t)
+        - sub::subsub (t)
+        "###);
+    }
+
+    #[test]
+    fn type_reexport_cross_crate() {
+        // Reexports need to be visible from a crate, even if the original crate exports the item
+        // at a shorter path.
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+            pub mod m {
+                pub use lib::S;
+            }
+            //- /lib.rs crate:lib
+            pub struct S;
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - m (t)
+        - m::S (t)
+        - m::S (v)
+        lib:
+        - S (t)
+        - S (v)
+        "###);
+    }
+
+    #[test]
+    fn macro_reexport() {
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+            pub mod m {
+                pub use lib::pub_macro;
+            }
+            //- /lib.rs crate:lib
+            #[macro_export]
+            macro_rules! pub_macro {
+                () => {};
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - m (t)
+        - m::pub_macro (m)
+        lib:
+        - pub_macro (m)
+        "###);
+    }
+
+    #[test]
+    fn module_reexport() {
+        // Reexporting modules from a dependency adds all contents to the import map.
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+            pub use lib::module as reexported_module;
+            //- /lib.rs crate:lib
+            pub mod module {
+                pub struct S;
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - reexported_module (t)
+        - reexported_module::S (t)
+        - reexported_module::S (v)
+        lib:
+        - module (t)
+        - module::S (t)
+        - module::S (v)
+        "###);
+    }
+
+    #[test]
+    fn cyclic_module_reexport() {
+        // A cyclic reexport does not hang.
+        let map = import_map(
+            r"
+            //- /lib.rs crate:lib
+            pub mod module {
+                pub struct S;
+                pub use super::sub::*;
+            }
+
+            pub mod sub {
+                pub use super::module;
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        lib:
+        - module (t)
+        - module::S (t)
+        - module::S (v)
+        - sub (t)
+        "###);
+    }
+
+    #[test]
+    fn private_macro() {
+        let map = import_map(
+            r"
+            //- /lib.rs crate:lib
+            macro_rules! private_macro {
+                () => {};
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        lib:
+        "###);
+    }
+
+    #[test]
+    fn namespacing() {
+        let map = import_map(
+            r"
+            //- /lib.rs crate:lib
+            pub struct Thing;     // t + v
+            #[macro_export]
+            macro_rules! Thing {  // m
+                () => {};
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        lib:
+        - Thing (m)
+        - Thing (t)
+        - Thing (v)
+        "###);
+
+        let map = import_map(
+            r"
+            //- /lib.rs crate:lib
+            pub mod Thing {}      // t
+            #[macro_export]
+            macro_rules! Thing {  // m
+                () => {};
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        lib:
+        - Thing (m)
+        - Thing (t)
+        "###);
+    }
+
+    #[test]
+    fn search() {
+        let ra_fixture = r#"
+            //- /main.rs crate:main deps:dep
+            //- /dep.rs crate:dep deps:tdep
+            use tdep::fmt as fmt_dep;
+            pub mod fmt {
+                pub trait Display {
+                    fn fmt();
+                }
+            }
+            #[macro_export]
+            macro_rules! Fmt {
+                () => {};
+            }
+            pub struct Fmt;
+
+            pub fn format() {}
+            pub fn no() {}
+
+            //- /tdep.rs crate:tdep
+            pub mod fmt {
+                pub struct NotImportableFromMain;
+            }
+        "#;
+
+        let res = search_dependencies_of(ra_fixture, "main", Query::new("fmt"));
+        assert_snapshot!(res, @r###"
+        dep::fmt (t)
+        dep::Fmt (t)
+        dep::Fmt (v)
+        dep::Fmt (m)
+        dep::fmt::Display (t)
+        dep::format (v)
+        "###);
+
+        let res = search_dependencies_of(ra_fixture, "main", Query::new("fmt").anchor_end());
+        assert_snapshot!(res, @r###"
+        dep::fmt (t)
+        dep::Fmt (t)
+        dep::Fmt (v)
+        dep::Fmt (m)
+        "###);
+    }
+
+    #[test]
+    fn search_casing() {
+        let ra_fixture = r#"
+            //- /main.rs crate:main deps:dep
+            //- /dep.rs crate:dep
+
+            pub struct fmt;
+            pub struct FMT;
+        "#;
+
+        let res = search_dependencies_of(ra_fixture, "main", Query::new("FMT"));
+
+        assert_snapshot!(res, @r###"
+        dep::fmt (t)
+        dep::fmt (v)
+        dep::FMT (t)
+        dep::FMT (v)
+        "###);
+
+        let res = search_dependencies_of(ra_fixture, "main", Query::new("FMT").case_sensitive());
+
+        assert_snapshot!(res, @r###"
+        dep::FMT (t)
+        dep::FMT (v)
+        "###);
+    }
+
+    #[test]
+    fn search_limit() {
+        let res = search_dependencies_of(
+            r#"
+        //- /main.rs crate:main deps:dep
+        //- /dep.rs crate:dep
+        pub mod fmt {
+            pub trait Display {
+                fn fmt();
+            }
+        }
+        #[macro_export]
+        macro_rules! Fmt {
+            () => {};
+        }
+        pub struct Fmt;
+
+        pub fn format() {}
+        pub fn no() {}
+    "#,
+            "main",
+            Query::new("").limit(2),
+        );
+        assert_snapshot!(res, @r###"
+        dep::fmt (t)
+        dep::Fmt (t)
+        "###);
+    }
+}
diff --git a/crates/ra_hir_def/src/item_scope.rs b/crates/ra_hir_def/src/item_scope.rs
index fc15948ad..b03ba939a 100644
--- a/crates/ra_hir_def/src/item_scope.rs
+++ b/crates/ra_hir_def/src/item_scope.rs
@@ -3,11 +3,12 @@
 
 use hir_expand::name::Name;
 use once_cell::sync::Lazy;
+use ra_db::CrateId;
 use rustc_hash::FxHashMap;
 
 use crate::{
-    per_ns::PerNs, visibility::Visibility, AdtId, BuiltinType, ImplId, MacroDefId, ModuleDefId,
-    TraitId,
+    db::DefDatabase, per_ns::PerNs, visibility::Visibility, AdtId, BuiltinType, HasModule, ImplId,
+    Lookup, MacroDefId, ModuleDefId, TraitId,
 };
 
 #[derive(Debug, Default, PartialEq, Eq)]
@@ -203,4 +204,22 @@ impl ItemInNs {
             ItemInNs::Macros(_) => None,
         }
     }
+
+    /// Returns the crate defining this item (or `None` if `self` is built-in).
+    pub fn krate(&self, db: &dyn DefDatabase) -> Option<CrateId> {
+        Some(match self {
+            ItemInNs::Types(did) | ItemInNs::Values(did) => match did {
+                ModuleDefId::ModuleId(id) => id.krate,
+                ModuleDefId::FunctionId(id) => id.lookup(db).module(db).krate,
+                ModuleDefId::AdtId(id) => id.module(db).krate,
+                ModuleDefId::EnumVariantId(id) => id.parent.lookup(db).container.module(db).krate,
+                ModuleDefId::ConstId(id) => id.lookup(db).container.module(db).krate,
+                ModuleDefId::StaticId(id) => id.lookup(db).container.module(db).krate,
+                ModuleDefId::TraitId(id) => id.lookup(db).container.module(db).krate,
+                ModuleDefId::TypeAliasId(id) => id.lookup(db).module(db).krate,
+                ModuleDefId::BuiltinType(_) => return None,
+            },
+            ItemInNs::Macros(id) => return id.krate,
+        })
+    }
 }
diff --git a/crates/ra_hir_def/src/lib.rs b/crates/ra_hir_def/src/lib.rs
index 5325a2760..edc59e5a8 100644
--- a/crates/ra_hir_def/src/lib.rs
+++ b/crates/ra_hir_def/src/lib.rs
@@ -43,6 +43,7 @@ pub mod child_by_source;
 
 pub mod visibility;
 pub mod find_path;
+pub mod import_map;
 
 #[cfg(test)]
 mod test_db;
@@ -416,6 +417,7 @@ pub trait AsMacroCall {
     fn as_call_id(
         &self,
         db: &dyn db::DefDatabase,
+        krate: CrateId,
         resolver: impl Fn(path::ModPath) -> Option<MacroDefId>,
     ) -> Option<MacroCallId>;
 }
@@ -424,13 +426,14 @@ impl AsMacroCall for InFile<&ast::MacroCall> {
     fn as_call_id(
         &self,
         db: &dyn db::DefDatabase,
+        krate: CrateId,
         resolver: impl Fn(path::ModPath) -> Option<MacroDefId>,
     ) -> Option<MacroCallId> {
         let ast_id = AstId::new(self.file_id, db.ast_id_map(self.file_id).ast_id(self.value));
         let h = Hygiene::new(db.upcast(), self.file_id);
         let path = path::ModPath::from_src(self.value.path()?, &h)?;
 
-        AstIdWithPath::new(ast_id.file_id, ast_id.value, path).as_call_id(db, resolver)
+        AstIdWithPath::new(ast_id.file_id, ast_id.value, path).as_call_id(db, krate, resolver)
     }
 }
 
@@ -451,6 +454,7 @@ impl AsMacroCall for AstIdWithPath<ast::MacroCall> {
     fn as_call_id(
         &self,
         db: &dyn db::DefDatabase,
+        krate: CrateId,
         resolver: impl Fn(path::ModPath) -> Option<MacroDefId>,
     ) -> Option<MacroCallId> {
         let def: MacroDefId = resolver(self.path.clone())?;
@@ -460,13 +464,13 @@ impl AsMacroCall for AstIdWithPath<ast::MacroCall> {
             let hygiene = Hygiene::new(db.upcast(), self.ast_id.file_id);
 
             Some(
-                expand_eager_macro(db.upcast(), macro_call, def, &|path: ast::Path| {
+                expand_eager_macro(db.upcast(), krate, macro_call, def, &|path: ast::Path| {
                     resolver(path::ModPath::from_src(path, &hygiene)?)
                 })?
                 .into(),
             )
         } else {
-            Some(def.as_lazy_macro(db.upcast(), MacroCallKind::FnLike(self.ast_id)).into())
+            Some(def.as_lazy_macro(db.upcast(), krate, MacroCallKind::FnLike(self.ast_id)).into())
         }
     }
 }
@@ -475,12 +479,14 @@ impl AsMacroCall for AstIdWithPath<ast::ModuleItem> {
     fn as_call_id(
         &self,
         db: &dyn db::DefDatabase,
+        krate: CrateId,
         resolver: impl Fn(path::ModPath) -> Option<MacroDefId>,
     ) -> Option<MacroCallId> {
         let def = resolver(self.path.clone())?;
         Some(
             def.as_lazy_macro(
                 db.upcast(),
+                krate,
                 MacroCallKind::Attr(self.ast_id, self.path.segments.last()?.to_string()),
             )
             .into(),
diff --git a/crates/ra_hir_def/src/nameres/collector.rs b/crates/ra_hir_def/src/nameres/collector.rs
index 353a31ad4..976e5e585 100644
--- a/crates/ra_hir_def/src/nameres/collector.rs
+++ b/crates/ra_hir_def/src/nameres/collector.rs
@@ -571,16 +571,18 @@ impl DefCollector<'_> {
                 return false;
             }
 
-            if let Some(call_id) = directive.ast_id.as_call_id(self.db, |path| {
-                let resolved_res = self.def_map.resolve_path_fp_with_macro(
-                    self.db,
-                    ResolveMode::Other,
-                    directive.module_id,
-                    &path,
-                    BuiltinShadowMode::Module,
-                );
-                resolved_res.resolved_def.take_macros()
-            }) {
+            if let Some(call_id) =
+                directive.ast_id.as_call_id(self.db, self.def_map.krate, |path| {
+                    let resolved_res = self.def_map.resolve_path_fp_with_macro(
+                        self.db,
+                        ResolveMode::Other,
+                        directive.module_id,
+                        &path,
+                        BuiltinShadowMode::Module,
+                    );
+                    resolved_res.resolved_def.take_macros()
+                })
+            {
                 resolved.push((directive.module_id, call_id, directive.depth));
                 res = ReachedFixedPoint::No;
                 return false;
@@ -589,9 +591,10 @@ impl DefCollector<'_> {
             true
         });
         attribute_macros.retain(|directive| {
-            if let Some(call_id) = directive
-                .ast_id
-                .as_call_id(self.db, |path| self.resolve_attribute_macro(&directive, &path))
+            if let Some(call_id) =
+                directive.ast_id.as_call_id(self.db, self.def_map.krate, |path| {
+                    self.resolve_attribute_macro(&directive, &path)
+                })
             {
                 resolved.push((directive.module_id, call_id, 0));
                 res = ReachedFixedPoint::No;
@@ -957,11 +960,13 @@ impl ModCollector<'_, '_> {
         }
 
         // Case 2: try to resolve in legacy scope and expand macro_rules
-        if let Some(macro_call_id) = ast_id.as_call_id(self.def_collector.db, |path| {
-            path.as_ident().and_then(|name| {
-                self.def_collector.def_map[self.module_id].scope.get_legacy_macro(&name)
+        if let Some(macro_call_id) =
+            ast_id.as_call_id(self.def_collector.db, self.def_collector.def_map.krate, |path| {
+                path.as_ident().and_then(|name| {
+                    self.def_collector.def_map[self.module_id].scope.get_legacy_macro(&name)
+                })
             })
-        }) {
+        {
             self.def_collector.unexpanded_macros.push(MacroDirective {
                 module_id: self.module_id,
                 ast_id,
diff --git a/crates/ra_hir_def/src/nameres/mod_resolution.rs b/crates/ra_hir_def/src/nameres/mod_resolution.rs
index 386c5cade..cede4a6fc 100644
--- a/crates/ra_hir_def/src/nameres/mod_resolution.rs
+++ b/crates/ra_hir_def/src/nameres/mod_resolution.rs
@@ -61,7 +61,7 @@ impl ModDir {
         };
 
         for candidate in candidate_files.iter() {
-            if let Some(file_id) = db.resolve_relative_path(file_id, candidate) {
+            if let Some(file_id) = db.resolve_path(file_id, candidate.as_str()) {
                 let mut root_non_dir_owner = false;
                 let mut mod_path = RelativePathBuf::new();
                 if !(candidate.ends_with("mod.rs") || attr_path.is_some()) {
diff --git a/crates/ra_hir_def/src/path.rs b/crates/ra_hir_def/src/path.rs
index e84efe2ab..ba16442bd 100644
--- a/crates/ra_hir_def/src/path.rs
+++ b/crates/ra_hir_def/src/path.rs
@@ -76,6 +76,19 @@ impl ModPath {
         }
     }
 
+    /// Returns the number of segments in the path (counting special segments like `$crate` and
+    /// `super`).
+    pub 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 fn is_ident(&self) -> bool {
         self.kind == PathKind::Plain && self.segments.len() == 1
     }
@@ -273,7 +286,7 @@ impl From<Name> for ModPath {
 impl Display for ModPath {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         let mut first_segment = true;
-        let mut add_segment = |s| {
+        let mut add_segment = |s| -> fmt::Result {
             if !first_segment {
                 f.write_str("::")?;
             }
@@ -310,16 +323,16 @@ pub use hir_expand::name as __name;
 
 #[macro_export]
 macro_rules! __known_path {
-    (std::iter::IntoIterator) => {};
-    (std::result::Result) => {};
-    (std::ops::Range) => {};
-    (std::ops::RangeFrom) => {};
-    (std::ops::RangeFull) => {};
-    (std::ops::RangeTo) => {};
-    (std::ops::RangeToInclusive) => {};
-    (std::ops::RangeInclusive) => {};
-    (std::future::Future) => {};
-    (std::ops::Try) => {};
+    (core::iter::IntoIterator) => {};
+    (core::result::Result) => {};
+    (core::ops::Range) => {};
+    (core::ops::RangeFrom) => {};
+    (core::ops::RangeFull) => {};
+    (core::ops::RangeTo) => {};
+    (core::ops::RangeToInclusive) => {};
+    (core::ops::RangeInclusive) => {};
+    (core::future::Future) => {};
+    (core::ops::Try) => {};
     ($path:path) => {
         compile_error!("Please register your known path in the path module")
     };
diff --git a/crates/ra_hir_def/src/per_ns.rs b/crates/ra_hir_def/src/per_ns.rs
index 6e435c8c1..74665c588 100644
--- a/crates/ra_hir_def/src/per_ns.rs
+++ b/crates/ra_hir_def/src/per_ns.rs
@@ -5,7 +5,7 @@
 
 use hir_expand::MacroDefId;
 
-use crate::{visibility::Visibility, ModuleDefId};
+use crate::{item_scope::ItemInNs, visibility::Visibility, ModuleDefId};
 
 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 pub struct PerNs {
@@ -84,4 +84,12 @@ impl PerNs {
             macros: self.macros.or(other.macros),
         }
     }
+
+    pub fn iter_items(self) -> impl Iterator<Item = ItemInNs> {
+        self.types
+            .map(|it| ItemInNs::Types(it.0))
+            .into_iter()
+            .chain(self.values.map(|it| ItemInNs::Values(it.0)).into_iter())
+            .chain(self.macros.map(|it| ItemInNs::Macros(it.0)).into_iter())
+    }
 }
diff --git a/crates/ra_hir_def/src/test_db.rs b/crates/ra_hir_def/src/test_db.rs
index eb83dee79..4581d8745 100644
--- a/crates/ra_hir_def/src/test_db.rs
+++ b/crates/ra_hir_def/src/test_db.rs
@@ -6,9 +6,8 @@ use std::{
 };
 
 use hir_expand::db::AstDatabase;
-use ra_db::{
-    salsa, CrateId, ExternSourceId, FileId, FileLoader, FileLoaderDelegate, RelativePath, Upcast,
-};
+use ra_db::{salsa, CrateId, FileId, FileLoader, FileLoaderDelegate, Upcast};
+use rustc_hash::FxHashSet;
 
 use crate::db::DefDatabase;
 
@@ -58,24 +57,12 @@ impl FileLoader for TestDB {
     fn file_text(&self, file_id: FileId) -> Arc<String> {
         FileLoaderDelegate(self).file_text(file_id)
     }
-    fn resolve_relative_path(
-        &self,
-        anchor: FileId,
-        relative_path: &RelativePath,
-    ) -> Option<FileId> {
-        FileLoaderDelegate(self).resolve_relative_path(anchor, relative_path)
+    fn resolve_path(&self, anchor: FileId, path: &str) -> Option<FileId> {
+        FileLoaderDelegate(self).resolve_path(anchor, path)
     }
-    fn relevant_crates(&self, file_id: FileId) -> Arc<Vec<CrateId>> {
+    fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>> {
         FileLoaderDelegate(self).relevant_crates(file_id)
     }
-
-    fn resolve_extern_path(
-        &self,
-        extern_id: ExternSourceId,
-        relative_path: &RelativePath,
-    ) -> Option<FileId> {
-        FileLoaderDelegate(self).resolve_extern_path(extern_id, relative_path)
-    }
 }
 
 impl TestDB {