37 files changed, 814 insertions, 294 deletions

diff --git a/crates/ra_assists/src/handlers/auto_import.rs b/crates/ra_assists/src/handlers/auto_import.rs
index edf96d50e..5092bf336 100644
--- a/crates/ra_assists/src/handlers/auto_import.rs
+++ b/crates/ra_assists/src/handlers/auto_import.rs
@@ -130,7 +130,7 @@ impl AutoImportAssets {
     fn search_for_imports(&self, db: &RootDatabase) -> BTreeSet<ModPath> {
         let _p = profile("auto_import::search_for_imports");
         let current_crate = self.module_with_name_to_import.krate();
-        ImportsLocator::new(db)
+        ImportsLocator::new(db, current_crate)
             .find_imports(&self.get_search_query())
             .into_iter()
             .filter_map(|candidate| match &self.import_candidate {
@@ -841,4 +841,105 @@ fn main() {
             ",
         )
     }
+
+    #[test]
+    fn dep_import() {
+        check_assist(
+            auto_import,
+            r"
+                    //- /lib.rs crate:dep
+                    pub struct Struct;
+
+                    //- /main.rs crate:main deps:dep
+                    fn main() {
+                        Struct<|>
+                    }",
+            r"use dep::Struct;
+
+fn main() {
+    Struct
+}
+",
+        );
+    }
+
+    #[test]
+    fn whole_segment() {
+        // Tests that only imports whose last segment matches the identifier get suggested.
+        check_assist(
+            auto_import,
+            r"
+                    //- /lib.rs crate:dep
+                    pub mod fmt {
+                        pub trait Display {}
+                    }
+
+                    pub fn panic_fmt() {}
+
+                    //- /main.rs crate:main deps:dep
+                    struct S;
+
+                    impl f<|>mt::Display for S {}",
+            r"use dep::fmt;
+
+struct S;
+impl fmt::Display for S {}
+",
+        );
+    }
+
+    #[test]
+    fn macro_generated() {
+        // Tests that macro-generated items are suggested from external crates.
+        check_assist(
+            auto_import,
+            r"
+                    //- /lib.rs crate:dep
+
+                    macro_rules! mac {
+                        () => {
+                            pub struct Cheese;
+                        };
+                    }
+
+                    mac!();
+
+                    //- /main.rs crate:main deps:dep
+
+                    fn main() {
+                        Cheese<|>;
+                    }",
+            r"use dep::Cheese;
+
+fn main() {
+    Cheese;
+}
+",
+        );
+    }
+
+    #[test]
+    fn casing() {
+        // Tests that differently cased names don't interfere and we only suggest the matching one.
+        check_assist(
+            auto_import,
+            r"
+                    //- /lib.rs crate:dep
+
+                    pub struct FMT;
+                    pub struct fmt;
+
+                    //- /main.rs crate:main deps:dep
+
+                    fn main() {
+                        FMT<|>;
+                    }",
+            r"use dep::FMT;
+
+fn main() {
+    FMT;
+}
+",
+        );
+    }
 }
diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs
index a8d6466ea..bf26048f2 100644
--- a/crates/ra_db/src/input.rs
+++ b/crates/ra_db/src/input.rs
@@ -15,12 +15,10 @@ use std::{
 
 use ra_cfg::CfgOptions;
 use ra_syntax::SmolStr;
-use rustc_hash::FxHashMap;
-use rustc_hash::FxHashSet;
+use ra_tt::TokenExpander;
+use rustc_hash::{FxHashMap, FxHashSet};
 
 use crate::{RelativePath, RelativePathBuf};
-use fmt::Display;
-use ra_tt::TokenExpander;
 
 /// `FileId` is an integer which uniquely identifies a file. File paths are
 /// messy and system-dependent, so most of the code should work directly with
@@ -111,7 +109,7 @@ impl CrateName {
     }
 }
 
-impl Display for CrateName {
+impl fmt::Display for CrateName {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f, "{}", self.0)
     }
diff --git a/crates/ra_db/src/lib.rs b/crates/ra_db/src/lib.rs
index 2ab314884..80ddb6058 100644
--- a/crates/ra_db/src/lib.rs
+++ b/crates/ra_db/src/lib.rs
@@ -7,6 +7,7 @@ use std::{panic, sync::Arc};
 
 use ra_prof::profile;
 use ra_syntax::{ast, Parse, SourceFile, TextRange, TextSize};
+use rustc_hash::FxHashSet;
 
 pub use crate::{
     cancellation::Canceled,
@@ -95,7 +96,7 @@ pub trait FileLoader {
     /// `struct StrPath(str)` for clarity some day, but it's a bit messy, so we
     /// get by with a `&str` for the time being.
     fn resolve_path(&self, anchor: FileId, path: &str) -> Option<FileId>;
-    fn relevant_crates(&self, file_id: FileId) -> Arc<Vec<CrateId>>;
+    fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>>;
 }
 
 /// Database which stores all significant input facts: source code and project
@@ -133,16 +134,21 @@ pub trait SourceDatabaseExt: SourceDatabase {
     #[salsa::input]
     fn source_root(&self, id: SourceRootId) -> Arc<SourceRoot>;
 
-    fn source_root_crates(&self, id: SourceRootId) -> Arc<Vec<CrateId>>;
+    fn source_root_crates(&self, id: SourceRootId) -> Arc<FxHashSet<CrateId>>;
 }
 
 fn source_root_crates(
     db: &(impl SourceDatabaseExt + SourceDatabase),
     id: SourceRootId,
-) -> Arc<Vec<CrateId>> {
-    let root = db.source_root(id);
+) -> Arc<FxHashSet<CrateId>> {
     let graph = db.crate_graph();
-    let res = root.walk().filter_map(|it| graph.crate_id_for_crate_root(it)).collect::<Vec<_>>();
+    let res = graph
+        .iter()
+        .filter(|&krate| {
+            let root_file = graph[krate].root_file_id;
+            db.file_source_root(root_file) == id
+        })
+        .collect::<FxHashSet<_>>();
     Arc::new(res)
 }
 
@@ -156,7 +162,7 @@ impl<T: SourceDatabaseExt> FileLoader for FileLoaderDelegate<&'_ T> {
     fn resolve_path(&self, anchor: FileId, path: &str) -> Option<FileId> {
         // FIXME: this *somehow* should be platform agnostic...
         if std::path::Path::new(path).is_absolute() {
-            let krate = *self.relevant_crates(anchor).get(0)?;
+            let krate = *self.relevant_crates(anchor).iter().next()?;
             let (extern_source_id, relative_file) =
                 self.0.crate_graph()[krate].extern_source.extern_path(path.as_ref())?;
 
@@ -175,7 +181,7 @@ impl<T: SourceDatabaseExt> FileLoader for FileLoaderDelegate<&'_ T> {
         }
     }
 
-    fn relevant_crates(&self, file_id: FileId) -> Arc<Vec<CrateId>> {
+    fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>> {
         let source_root = self.0.file_source_root(file_id);
         self.0.source_root_crates(source_root)
     }
diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index 4a06f3bcd..1a9f6cc76 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -9,6 +9,7 @@ use hir_def::{
     builtin_type::BuiltinType,
     docs::Documentation,
     expr::{BindingAnnotation, Pat, PatId},
+    import_map,
     per_ns::PerNs,
     resolver::{HasResolver, Resolver},
     type_ref::{Mutability, TypeRef},
@@ -98,6 +99,23 @@ impl Crate {
         db.crate_graph()[self.id].display_name.as_ref().cloned()
     }
 
+    pub fn query_external_importables(
+        self,
+        db: &dyn DefDatabase,
+        query: &str,
+    ) -> impl Iterator<Item = Either<ModuleDef, MacroDef>> {
+        import_map::search_dependencies(
+            db,
+            self.into(),
+            import_map::Query::new(query).anchor_end().case_sensitive().limit(40),
+        )
+        .into_iter()
+        .map(|item| match item {
+            ItemInNs::Types(mod_id) | ItemInNs::Values(mod_id) => Either::Left(mod_id.into()),
+            ItemInNs::Macros(mac_id) => Either::Right(mac_id.into()),
+        })
+    }
+
     pub fn all(db: &dyn HirDatabase) -> Vec<Crate> {
         db.crate_graph().iter().map(|id| Crate { id }).collect()
     }
diff --git a/crates/ra_hir/src/semantics.rs b/crates/ra_hir/src/semantics.rs
index 7c1f79f27..a232a5856 100644
--- a/crates/ra_hir/src/semantics.rs
+++ b/crates/ra_hir/src/semantics.rs
@@ -122,8 +122,9 @@ impl<'db, DB: HirDatabase> Semantics<'db, DB> {
         let macro_call =
             self.find_file(actual_macro_call.syntax().clone()).with_value(actual_macro_call);
         let sa = self.analyze2(macro_call.map(|it| it.syntax()), None);
+        let krate = sa.resolver.krate()?;
         let macro_call_id = macro_call
-            .as_call_id(self.db, |path| sa.resolver.resolve_path_as_macro(self.db, &path))?;
+            .as_call_id(self.db, krate, |path| sa.resolver.resolve_path_as_macro(self.db, &path))?;
         hir_expand::db::expand_hypothetical(self.db, macro_call_id, hypothetical_args, token_to_map)
     }
 
diff --git a/crates/ra_hir/src/source_analyzer.rs b/crates/ra_hir/src/source_analyzer.rs
index 4b509f07c..7c6bbea13 100644
--- a/crates/ra_hir/src/source_analyzer.rs
+++ b/crates/ra_hir/src/source_analyzer.rs
@@ -307,7 +307,8 @@ impl SourceAnalyzer {
         db: &dyn HirDatabase,
         macro_call: InFile<&ast::MacroCall>,
     ) -> Option<HirFileId> {
-        let macro_call_id = macro_call.as_call_id(db.upcast(), |path| {
+        let krate = self.resolver.krate()?;
+        let macro_call_id = macro_call.as_call_id(db.upcast(), krate, |path| {
             self.resolver.resolve_path_as_macro(db.upcast(), &path)
         })?;
         Some(macro_call_id.as_file())
diff --git a/crates/ra_hir_def/Cargo.toml b/crates/ra_hir_def/Cargo.toml
index b85358308..ef1f65ee0 100644
--- a/crates/ra_hir_def/Cargo.toml
+++ b/crates/ra_hir_def/Cargo.toml
@@ -14,6 +14,9 @@ rustc-hash = "1.1.0"
 either = "1.5.3"
 anymap = "0.12.1"
 drop_bomb = "0.1.4"
+fst = { version = "0.4", default-features = false }
+itertools = "0.9.0"
+indexmap = "1.4.0"
 
 stdx = { path = "../stdx" }
 
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 807195d25..53599e74a 100644
--- a/crates/ra_hir_def/src/data.rs
+++ b/crates/ra_hir_def/src/data.rs
@@ -99,7 +99,7 @@ impl FunctionData {
 }
 
 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/import_map.rs b/crates/ra_hir_def/src/import_map.rs
index 4284a0a91..36b4fdd81 100644
--- a/crates/ra_hir_def/src/import_map.rs
+++ b/crates/ra_hir_def/src/import_map.rs
@@ -1,9 +1,11 @@
 //! A map of all publicly exported items in a crate.
 
-use std::{collections::hash_map::Entry, fmt, sync::Arc};
+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::FxHashMap;
+use rustc_hash::FxHasher;
 
 use crate::{
     db::DefDatabase,
@@ -13,6 +15,8 @@ use crate::{
     ModuleDefId, ModuleId,
 };
 
+type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
+
 /// A map from publicly exported items to the path needed to import/name them from a downstream
 /// crate.
 ///
@@ -21,16 +25,24 @@ use crate::{
 ///
 /// 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.
-#[derive(Eq, PartialEq)]
 pub struct ImportMap {
-    map: FxHashMap<ItemInNs, ModPath>,
+    map: FxIndexMap<ItemInNs, ModPath>,
+
+    /// 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 = FxHashMap::with_capacity_and_hasher(64, Default::default());
+        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![] };
@@ -88,7 +100,34 @@ impl ImportMap {
             }
         }
 
-        Arc::new(Self { map: import_map })
+        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);
+
+            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.
@@ -97,6 +136,15 @@ impl ImportMap {
     }
 }
 
+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
@@ -117,19 +165,135 @@ impl fmt::Debug for ImportMap {
     }
 }
 
+fn fst_path(path: &ModPath) -> String {
+    let mut s = path.to_string();
+    s.make_ascii_lowercase();
+    s
+}
+
+fn cmp((_, lhs): &(&ItemInNs, &ModPath), (_, rhs): &(&ItemInNs, &ModPath)) -> Ordering {
+    let lhs_str = fst_path(lhs);
+    let rhs_str = fst_path(rhs);
+    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]];
+
+            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];
+                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];
+                    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;
+    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 import_maps: Vec<_> = crate_graph
+        let s = crate_graph
             .iter()
             .filter_map(|krate| {
                 let cdata = &crate_graph[krate];
@@ -139,9 +303,41 @@ mod tests {
 
                 Some(format!("{}:\n{:?}", name, map))
             })
-            .collect();
+            .join("\n");
+        s
+    }
 
-        import_maps.join("\n")
+    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]
@@ -328,4 +524,143 @@ mod tests {
         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/lib.rs b/crates/ra_hir_def/src/lib.rs
index de490fcc5..edc59e5a8 100644
--- a/crates/ra_hir_def/src/lib.rs
+++ b/crates/ra_hir_def/src/lib.rs
@@ -417,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>;
 }
@@ -425,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)
     }
 }
 
@@ -452,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())?;
@@ -461,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())
         }
     }
 }
@@ -476,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/path.rs b/crates/ra_hir_def/src/path.rs
index bfa921de2..ba16442bd 100644
--- a/crates/ra_hir_def/src/path.rs
+++ b/crates/ra_hir_def/src/path.rs
@@ -323,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/test_db.rs b/crates/ra_hir_def/src/test_db.rs
index bcfa66ac9..4581d8745 100644
--- a/crates/ra_hir_def/src/test_db.rs
+++ b/crates/ra_hir_def/src/test_db.rs
@@ -7,6 +7,7 @@ use std::{
 
 use hir_expand::db::AstDatabase;
 use ra_db::{salsa, CrateId, FileId, FileLoader, FileLoaderDelegate, Upcast};
+use rustc_hash::FxHashSet;
 
 use crate::db::DefDatabase;
 
@@ -59,7 +60,7 @@ impl FileLoader for TestDB {
     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)
     }
 }
diff --git a/crates/ra_hir_expand/Cargo.toml b/crates/ra_hir_expand/Cargo.toml
index 2cd522766..e5c9f3e99 100644
--- a/crates/ra_hir_expand/Cargo.toml
+++ b/crates/ra_hir_expand/Cargo.toml
@@ -10,6 +10,7 @@ doctest = false
 [dependencies]
 log = "0.4.8"
 either = "1.5.3"
+rustc-hash = "1.0.0"
 
 ra_arena = { path = "../ra_arena" }
 ra_db = { path = "../ra_db" }
diff --git a/crates/ra_hir_expand/src/builtin_derive.rs b/crates/ra_hir_expand/src/builtin_derive.rs
index 1dc9cac66..26b667b55 100644
--- a/crates/ra_hir_expand/src/builtin_derive.rs
+++ b/crates/ra_hir_expand/src/builtin_derive.rs
@@ -8,8 +8,7 @@ use ra_syntax::{
     match_ast,
 };
 
-use crate::db::AstDatabase;
-use crate::{name, quote, LazyMacroId, MacroCallId, MacroDefId, MacroDefKind};
+use crate::{db::AstDatabase, name, quote, LazyMacroId, MacroDefId, MacroDefKind};
 
 macro_rules! register_builtin {
     ( $($trait:ident => $expand:ident),* ) => {
@@ -156,23 +155,13 @@ fn expand_simple_derive(
 fn find_builtin_crate(db: &dyn AstDatabase, id: LazyMacroId) -> tt::TokenTree {
     // FIXME: make hygiene works for builtin derive macro
     // such that $crate can be used here.
-
-    let m: MacroCallId = id.into();
-    let file_id = m.as_file().original_file(db);
     let cg = db.crate_graph();
-    let krates = db.relevant_crates(file_id);
-    let krate = match krates.get(0) {
-        Some(krate) => krate,
-        None => {
-            let tt = quote! { core };
-            return tt.token_trees[0].clone();
-        }
-    };
+    let krate = db.lookup_intern_macro(id).krate;
 
     // XXX
     //  All crates except core itself should have a dependency on core,
     //  We detect `core` by seeing whether it doesn't have such a dependency.
-    let tt = if cg[*krate].dependencies.iter().any(|dep| dep.name == "core") {
+    let tt = if cg[krate].dependencies.iter().any(|dep| dep.name == "core") {
         quote! { core }
     } else {
         quote! { crate }
@@ -264,10 +253,12 @@ fn partial_ord_expand(
 
 #[cfg(test)]
 mod tests {
-    use super::*;
-    use crate::{test_db::TestDB, AstId, MacroCallId, MacroCallKind, MacroCallLoc};
     use name::{known, Name};
-    use ra_db::{fixture::WithFixture, SourceDatabase};
+    use ra_db::{fixture::WithFixture, CrateId, SourceDatabase};
+
+    use crate::{test_db::TestDB, AstId, MacroCallId, MacroCallKind, MacroCallLoc};
+
+    use super::*;
 
     fn expand_builtin_derive(s: &str, name: Name) -> String {
         let def = find_builtin_derive(&name).unwrap();
@@ -291,7 +282,11 @@ mod tests {
 
         let attr_id = AstId::new(file_id.into(), ast_id_map.ast_id(&items[0]));
 
-        let loc = MacroCallLoc { def, kind: MacroCallKind::Attr(attr_id, name.to_string()) };
+        let loc = MacroCallLoc {
+            def,
+            krate: CrateId(0),
+            kind: MacroCallKind::Attr(attr_id, name.to_string()),
+        };
 
         let id: MacroCallId = db.intern_macro(loc).into();
         let parsed = db.parse_or_expand(id.as_file()).unwrap();
diff --git a/crates/ra_hir_expand/src/builtin_macro.rs b/crates/ra_hir_expand/src/builtin_macro.rs
index 7579546d2..b50eb347c 100644
--- a/crates/ra_hir_expand/src/builtin_macro.rs
+++ b/crates/ra_hir_expand/src/builtin_macro.rs
@@ -1,15 +1,14 @@
 //! Builtin macro
-use crate::db::AstDatabase;
 use crate::{
-    ast::{self, AstToken, HasStringValue},
-    name, AstId, CrateId, MacroDefId, MacroDefKind, TextSize,
+    db::AstDatabase, name, quote, AstId, CrateId, EagerMacroId, LazyMacroId, MacroCallId,
+    MacroDefId, MacroDefKind, TextSize,
 };
 
-use crate::{quote, EagerMacroId, LazyMacroId, MacroCallId};
 use either::Either;
 use mbe::parse_to_token_tree;
 use ra_db::FileId;
 use ra_parser::FragmentKind;
+use ra_syntax::ast::{self, AstToken, HasStringValue};
 
 macro_rules! register_builtin {
     ( LAZY: $(($name:ident, $kind: ident) => $expand:ident),* , EAGER: $(($e_name:ident, $e_kind: ident) => $e_expand:ident),*  ) => {
@@ -333,10 +332,7 @@ fn include_expand(
 }
 
 fn get_env_inner(db: &dyn AstDatabase, arg_id: EagerMacroId, key: &str) -> Option<String> {
-    let call_id: MacroCallId = arg_id.into();
-    let original_file = call_id.as_file().original_file(db);
-
-    let krate = *db.relevant_crates(original_file).get(0)?;
+    let krate = db.lookup_intern_eager_expansion(arg_id).krate;
     db.crate_graph()[krate].env.get(key)
 }
 
@@ -395,6 +391,7 @@ mod tests {
 
         let expander = find_by_name(&macro_calls[0].name().unwrap().as_name()).unwrap();
 
+        let krate = CrateId(0);
         let file_id = match expander {
             Either::Left(expander) => {
                 // the first one should be a macro_rules
@@ -407,6 +404,7 @@ mod tests {
 
                 let loc = MacroCallLoc {
                     def,
+                    krate,
                     kind: MacroCallKind::FnLike(AstId::new(
                         file_id.into(),
                         ast_id_map.ast_id(&macro_calls[1]),
@@ -419,7 +417,7 @@ mod tests {
             Either::Right(expander) => {
                 // the first one should be a macro_rules
                 let def = MacroDefId {
-                    krate: Some(CrateId(0)),
+                    krate: Some(krate),
                     ast_id: Some(AstId::new(file_id.into(), ast_id_map.ast_id(&macro_calls[0]))),
                     kind: MacroDefKind::BuiltInEager(expander),
                     local_inner: false,
@@ -433,6 +431,7 @@ mod tests {
                         def,
                         fragment: FragmentKind::Expr,
                         subtree: Arc::new(parsed_args.clone()),
+                        krate,
                         file_id: file_id.into(),
                     }
                 });
@@ -442,6 +441,7 @@ mod tests {
                     def,
                     fragment,
                     subtree: Arc::new(subtree),
+                    krate,
                     file_id: file_id.into(),
                 };
 
diff --git a/crates/ra_hir_expand/src/eager.rs b/crates/ra_hir_expand/src/eager.rs
index 932f47c30..302d2b3e0 100644
--- a/crates/ra_hir_expand/src/eager.rs
+++ b/crates/ra_hir_expand/src/eager.rs
@@ -25,12 +25,14 @@ use crate::{
     EagerCallLoc, EagerMacroId, InFile, MacroCallId, MacroCallKind, MacroDefId, MacroDefKind,
 };
 
+use ra_db::CrateId;
 use ra_parser::FragmentKind;
 use ra_syntax::{algo::SyntaxRewriter, SyntaxNode};
 use std::sync::Arc;
 
 pub fn expand_eager_macro(
     db: &dyn AstDatabase,
+    krate: CrateId,
     macro_call: InFile<ast::MacroCall>,
     def: MacroDefId,
     resolver: &dyn Fn(ast::Path) -> Option<MacroDefId>,
@@ -47,6 +49,7 @@ pub fn expand_eager_macro(
             def,
             fragment: FragmentKind::Expr,
             subtree: Arc::new(parsed_args.clone()),
+            krate,
             file_id: macro_call.file_id,
         }
     });
@@ -56,14 +59,20 @@ pub fn expand_eager_macro(
     let result = eager_macro_recur(
         db,
         InFile::new(arg_file_id.as_file(), parsed_args.syntax_node()),
+        krate,
         resolver,
     )?;
     let subtree = to_subtree(&result)?;
 
     if let MacroDefKind::BuiltInEager(eager) = def.kind {
         let (subtree, fragment) = eager.expand(db, arg_id, &subtree).ok()?;
-        let eager =
-            EagerCallLoc { def, fragment, subtree: Arc::new(subtree), file_id: macro_call.file_id };
+        let eager = EagerCallLoc {
+            def,
+            fragment,
+            subtree: Arc::new(subtree),
+            krate,
+            file_id: macro_call.file_id,
+        };
 
         Some(db.intern_eager_expansion(eager))
     } else {
@@ -81,11 +90,12 @@ fn lazy_expand(
     db: &dyn AstDatabase,
     def: &MacroDefId,
     macro_call: InFile<ast::MacroCall>,
+    krate: CrateId,
 ) -> Option<InFile<SyntaxNode>> {
     let ast_id = db.ast_id_map(macro_call.file_id).ast_id(&macro_call.value);
 
     let id: MacroCallId =
-        def.as_lazy_macro(db, MacroCallKind::FnLike(macro_call.with_value(ast_id))).into();
+        def.as_lazy_macro(db, krate, MacroCallKind::FnLike(macro_call.with_value(ast_id))).into();
 
     db.parse_or_expand(id.as_file()).map(|node| InFile::new(id.as_file(), node))
 }
@@ -93,6 +103,7 @@ fn lazy_expand(
 fn eager_macro_recur(
     db: &dyn AstDatabase,
     curr: InFile<SyntaxNode>,
+    krate: CrateId,
     macro_resolver: &dyn Fn(ast::Path) -> Option<MacroDefId>,
 ) -> Option<SyntaxNode> {
     let original = curr.value.clone();
@@ -105,18 +116,23 @@ fn eager_macro_recur(
         let def: MacroDefId = macro_resolver(child.path()?)?;
         let insert = match def.kind {
             MacroDefKind::BuiltInEager(_) => {
-                let id: MacroCallId =
-                    expand_eager_macro(db, curr.with_value(child.clone()), def, macro_resolver)?
-                        .into();
+                let id: MacroCallId = expand_eager_macro(
+                    db,
+                    krate,
+                    curr.with_value(child.clone()),
+                    def,
+                    macro_resolver,
+                )?
+                .into();
                 db.parse_or_expand(id.as_file())?
             }
             MacroDefKind::Declarative
             | MacroDefKind::BuiltIn(_)
             | MacroDefKind::BuiltInDerive(_)
             | MacroDefKind::CustomDerive(_) => {
-                let expanded = lazy_expand(db, &def, curr.with_value(child.clone()))?;
+                let expanded = lazy_expand(db, &def, curr.with_value(child.clone()), krate)?;
                 // replace macro inside
-                eager_macro_recur(db, expanded, macro_resolver)?
+                eager_macro_recur(db, expanded, krate, macro_resolver)?
             }
         };
 
diff --git a/crates/ra_hir_expand/src/lib.rs b/crates/ra_hir_expand/src/lib.rs
index f440c073b..5eac2605b 100644
--- a/crates/ra_hir_expand/src/lib.rs
+++ b/crates/ra_hir_expand/src/lib.rs
@@ -209,8 +209,13 @@ pub struct MacroDefId {
 }
 
 impl MacroDefId {
-    pub fn as_lazy_macro(self, db: &dyn db::AstDatabase, kind: MacroCallKind) -> LazyMacroId {
-        db.intern_macro(MacroCallLoc { def: self, kind })
+    pub fn as_lazy_macro(
+        self,
+        db: &dyn db::AstDatabase,
+        krate: CrateId,
+        kind: MacroCallKind,
+    ) -> LazyMacroId {
+        db.intern_macro(MacroCallLoc { def: self, krate, kind })
     }
 }
 
@@ -227,6 +232,7 @@ pub enum MacroDefKind {
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct MacroCallLoc {
     pub(crate) def: MacroDefId,
+    pub(crate) krate: CrateId,
     pub(crate) kind: MacroCallKind,
 }
 
@@ -274,6 +280,7 @@ pub struct EagerCallLoc {
     pub(crate) def: MacroDefId,
     pub(crate) fragment: FragmentKind,
     pub(crate) subtree: Arc<tt::Subtree>,
+    pub(crate) krate: CrateId,
     pub(crate) file_id: HirFileId,
 }
 
diff --git a/crates/ra_hir_expand/src/test_db.rs b/crates/ra_hir_expand/src/test_db.rs
index fdf225f55..09fc18c36 100644
--- a/crates/ra_hir_expand/src/test_db.rs
+++ b/crates/ra_hir_expand/src/test_db.rs
@@ -6,6 +6,7 @@ use std::{
 };
 
 use ra_db::{salsa, CrateId, FileId, FileLoader, FileLoaderDelegate};
+use rustc_hash::FxHashSet;
 
 #[salsa::database(
     ra_db::SourceDatabaseExtStorage,
@@ -44,7 +45,7 @@ impl FileLoader for TestDB {
     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)
     }
 }
diff --git a/crates/ra_hir_ty/src/expr.rs b/crates/ra_hir_ty/src/expr.rs
index f04968e14..7db928dde 100644
--- a/crates/ra_hir_ty/src/expr.rs
+++ b/crates/ra_hir_ty/src/expr.rs
@@ -226,17 +226,19 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
             None => return,
         };
 
-        let std_result_path = path![std::result::Result];
+        let core_result_path = path![core::result::Result];
 
         let resolver = self.func.resolver(db.upcast());
-        let std_result_enum = match resolver.resolve_known_enum(db.upcast(), &std_result_path) {
+        let core_result_enum = match resolver.resolve_known_enum(db.upcast(), &core_result_path) {
             Some(it) => it,
             _ => return,
         };
 
-        let std_result_ctor = TypeCtor::Adt(AdtId::EnumId(std_result_enum));
+        let core_result_ctor = TypeCtor::Adt(AdtId::EnumId(core_result_enum));
         let params = match &mismatch.expected {
-            Ty::Apply(ApplicationTy { ctor, parameters }) if ctor == &std_result_ctor => parameters,
+            Ty::Apply(ApplicationTy { ctor, parameters }) if ctor == &core_result_ctor => {
+                parameters
+            }
             _ => return,
         };
 
diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs
index f965eb2b5..3719f76a6 100644
--- a/crates/ra_hir_ty/src/infer.rs
+++ b/crates/ra_hir_ty/src/infer.rs
@@ -555,13 +555,13 @@ impl<'a> InferenceContext<'a> {
     }
 
     fn resolve_into_iter_item(&self) -> Option<TypeAliasId> {
-        let path = path![std::iter::IntoIterator];
+        let path = path![core::iter::IntoIterator];
         let trait_ = self.resolver.resolve_known_trait(self.db.upcast(), &path)?;
         self.db.trait_data(trait_).associated_type_by_name(&name![Item])
     }
 
     fn resolve_ops_try_ok(&self) -> Option<TypeAliasId> {
-        let path = path![std::ops::Try];
+        let path = path![core::ops::Try];
         let trait_ = self.resolver.resolve_known_trait(self.db.upcast(), &path)?;
         self.db.trait_data(trait_).associated_type_by_name(&name![Ok])
     }
@@ -587,37 +587,37 @@ impl<'a> InferenceContext<'a> {
     }
 
     fn resolve_range_full(&self) -> Option<AdtId> {
-        let path = path![std::ops::RangeFull];
+        let path = path![core::ops::RangeFull];
         let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
         Some(struct_.into())
     }
 
     fn resolve_range(&self) -> Option<AdtId> {
-        let path = path![std::ops::Range];
+        let path = path![core::ops::Range];
         let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
         Some(struct_.into())
     }
 
     fn resolve_range_inclusive(&self) -> Option<AdtId> {
-        let path = path![std::ops::RangeInclusive];
+        let path = path![core::ops::RangeInclusive];
         let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
         Some(struct_.into())
     }
 
     fn resolve_range_from(&self) -> Option<AdtId> {
-        let path = path![std::ops::RangeFrom];
+        let path = path![core::ops::RangeFrom];
         let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
         Some(struct_.into())
     }
 
     fn resolve_range_to(&self) -> Option<AdtId> {
-        let path = path![std::ops::RangeTo];
+        let path = path![core::ops::RangeTo];
         let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
         Some(struct_.into())
     }
 
     fn resolve_range_to_inclusive(&self) -> Option<AdtId> {
-        let path = path![std::ops::RangeToInclusive];
+        let path = path![core::ops::RangeToInclusive];
         let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
         Some(struct_.into())
     }
diff --git a/crates/ra_hir_ty/src/test_db.rs b/crates/ra_hir_ty/src/test_db.rs
index e484968a0..ad04e3e0f 100644
--- a/crates/ra_hir_ty/src/test_db.rs
+++ b/crates/ra_hir_ty/src/test_db.rs
@@ -8,6 +8,7 @@ use std::{
 use hir_def::{db::DefDatabase, AssocItemId, ModuleDefId, ModuleId};
 use hir_expand::{db::AstDatabase, diagnostics::DiagnosticSink};
 use ra_db::{salsa, CrateId, FileId, FileLoader, FileLoaderDelegate, SourceDatabase, Upcast};
+use rustc_hash::FxHashSet;
 use stdx::format_to;
 
 use crate::{db::HirDatabase, diagnostics::Diagnostic, expr::ExprValidator};
@@ -73,7 +74,7 @@ impl FileLoader for TestDB {
     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)
     }
 }
diff --git a/crates/ra_hir_ty/src/tests/simple.rs b/crates/ra_hir_ty/src/tests/simple.rs
index 8a5031756..37659cd02 100644
--- a/crates/ra_hir_ty/src/tests/simple.rs
+++ b/crates/ra_hir_ty/src/tests/simple.rs
@@ -95,7 +95,7 @@ fn foo() {
 fn infer_ranges() {
     let (db, pos) = TestDB::with_position(
         r#"
-//- /main.rs crate:main deps:std
+//- /main.rs crate:main deps:core
 fn test() {
     let a = ..;
     let b = 1..;
@@ -108,7 +108,7 @@ fn test() {
     t<|>;
 }
 
-//- /std.rs crate:std
+//- /core.rs crate:core
 #[prelude_import] use prelude::*;
 mod prelude {}
 
diff --git a/crates/ra_hir_ty/src/tests/traits.rs b/crates/ra_hir_ty/src/tests/traits.rs
index 133fb5f39..e81193a3c 100644
--- a/crates/ra_hir_ty/src/tests/traits.rs
+++ b/crates/ra_hir_ty/src/tests/traits.rs
@@ -10,7 +10,7 @@ use super::{infer, infer_with_mismatches, type_at, type_at_pos};
 fn infer_await() {
     let (db, pos) = TestDB::with_position(
         r#"
-//- /main.rs crate:main deps:std
+//- /main.rs crate:main deps:core
 
 struct IntFuture;
 
@@ -24,7 +24,7 @@ fn test() {
     v<|>;
 }
 
-//- /std.rs crate:std
+//- /core.rs crate:core
 #[prelude_import] use future::*;
 mod future {
     #[lang = "future_trait"]
@@ -42,7 +42,7 @@ mod future {
 fn infer_async() {
     let (db, pos) = TestDB::with_position(
         r#"
-//- /main.rs crate:main deps:std
+//- /main.rs crate:main deps:core
 
 async fn foo() -> u64 {
     128
@@ -54,7 +54,7 @@ fn test() {
     v<|>;
 }
 
-//- /std.rs crate:std
+//- /core.rs crate:core
 #[prelude_import] use future::*;
 mod future {
     #[lang = "future_trait"]
@@ -72,7 +72,7 @@ mod future {
 fn infer_desugar_async() {
     let (db, pos) = TestDB::with_position(
         r#"
-//- /main.rs crate:main deps:std
+//- /main.rs crate:main deps:core
 
 async fn foo() -> u64 {
     128
@@ -83,7 +83,7 @@ fn test() {
     r<|>;
 }
 
-//- /std.rs crate:std
+//- /core.rs crate:core
 #[prelude_import] use future::*;
 mod future {
     trait Future {
@@ -100,7 +100,7 @@ mod future {
 fn infer_try() {
     let (db, pos) = TestDB::with_position(
         r#"
-//- /main.rs crate:main deps:std
+//- /main.rs crate:main deps:core
 
 fn test() {
     let r: Result<i32, u64> = Result::Ok(1);
@@ -108,7 +108,7 @@ fn test() {
     v<|>;
 }
 
-//- /std.rs crate:std
+//- /core.rs crate:core
 
 #[prelude_import] use ops::*;
 mod ops {
@@ -140,9 +140,9 @@ mod result {
 fn infer_for_loop() {
     let (db, pos) = TestDB::with_position(
         r#"
-//- /main.rs crate:main deps:std
+//- /main.rs crate:main deps:core,alloc
 
-use std::collections::Vec;
+use alloc::collections::Vec;
 
 fn test() {
     let v = Vec::new();
@@ -152,7 +152,7 @@ fn test() {
     }
 }
 
-//- /std.rs crate:std
+//- /core.rs crate:core
 
 #[prelude_import] use iter::*;
 mod iter {
@@ -161,6 +161,8 @@ mod iter {
     }
 }
 
+//- /alloc.rs crate:alloc deps:core
+
 mod collections {
     struct Vec<T> {}
     impl<T> Vec<T> {
@@ -168,7 +170,7 @@ mod collections {
         fn push(&mut self, t: T) { }
     }
 
-    impl<T> crate::iter::IntoIterator for Vec<T> {
+    impl<T> IntoIterator for Vec<T> {
         type Item=T;
     }
 }
@@ -2846,12 +2848,12 @@ fn test() {
 fn integer_range_iterate() {
     let t = type_at(
         r#"
-//- /main.rs crate:main deps:std
+//- /main.rs crate:main deps:core
 fn test() {
     for x in 0..100 { x<|>; }
 }
 
-//- /std.rs crate:std
+//- /core.rs crate:core
 pub mod ops {
     pub struct Range<Idx> {
         pub start: Idx,
diff --git a/crates/ra_ide/src/diagnostics.rs b/crates/ra_ide/src/diagnostics.rs
index bf14a467f..f44feaf69 100644
--- a/crates/ra_ide/src/diagnostics.rs
+++ b/crates/ra_ide/src/diagnostics.rs
@@ -321,29 +321,26 @@ mod tests {
     fn test_wrap_return_type() {
         let before = r#"
             //- /main.rs
-            use std::{string::String, result::Result::{self, Ok, Err}};
+            use core::result::Result::{self, Ok, Err};
 
-            fn div(x: i32, y: i32) -> Result<i32, String> {
+            fn div(x: i32, y: i32) -> Result<i32, ()> {
                 if y == 0 {
-                    return Err("div by zero".into());
+                    return Err(());
                 }
                 x / y<|>
             }
 
-            //- /std/lib.rs
-            pub mod string {
-                pub struct String { }
-            }
+            //- /core/lib.rs
             pub mod result {
                 pub enum Result<T, E> { Ok(T), Err(E) }
             }
         "#;
         let after = r#"
-            use std::{string::String, result::Result::{self, Ok, Err}};
+            use core::result::Result::{self, Ok, Err};
 
-            fn div(x: i32, y: i32) -> Result<i32, String> {
+            fn div(x: i32, y: i32) -> Result<i32, ()> {
                 if y == 0 {
-                    return Err("div by zero".into());
+                    return Err(());
                 }
                 Ok(x / y)
             }
@@ -355,7 +352,7 @@ mod tests {
     fn test_wrap_return_type_handles_generic_functions() {
         let before = r#"
             //- /main.rs
-            use std::result::Result::{self, Ok, Err};
+            use core::result::Result::{self, Ok, Err};
 
             fn div<T>(x: T) -> Result<T, i32> {
                 if x == 0 {
@@ -364,13 +361,13 @@ mod tests {
                 <|>x
             }
 
-            //- /std/lib.rs
+            //- /core/lib.rs
             pub mod result {
                 pub enum Result<T, E> { Ok(T), Err(E) }
             }
         "#;
         let after = r#"
-            use std::result::Result::{self, Ok, Err};
+            use core::result::Result::{self, Ok, Err};
 
             fn div<T>(x: T) -> Result<T, i32> {
                 if x == 0 {
@@ -386,32 +383,29 @@ mod tests {
     fn test_wrap_return_type_handles_type_aliases() {
         let before = r#"
             //- /main.rs
-            use std::{string::String, result::Result::{self, Ok, Err}};
+            use core::result::Result::{self, Ok, Err};
 
-            type MyResult<T> = Result<T, String>;
+            type MyResult<T> = Result<T, ()>;
 
             fn div(x: i32, y: i32) -> MyResult<i32> {
                 if y == 0 {
-                    return Err("div by zero".into());
+                    return Err(());
                 }
                 x <|>/ y
             }
 
-            //- /std/lib.rs
-            pub mod string {
-                pub struct String { }
-            }
+            //- /core/lib.rs
             pub mod result {
                 pub enum Result<T, E> { Ok(T), Err(E) }
             }
         "#;
         let after = r#"
-            use std::{string::String, result::Result::{self, Ok, Err}};
+            use core::result::Result::{self, Ok, Err};
 
-            type MyResult<T> = Result<T, String>;
+            type MyResult<T> = Result<T, ()>;
             fn div(x: i32, y: i32) -> MyResult<i32> {
                 if y == 0 {
-                    return Err("div by zero".into());
+                    return Err(());
                 }
                 Ok(x / y)
             }
@@ -423,16 +417,13 @@ mod tests {
     fn test_wrap_return_type_not_applicable_when_expr_type_does_not_match_ok_type() {
         let content = r#"
             //- /main.rs
-            use std::{string::String, result::Result::{self, Ok, Err}};
+            use core::result::Result::{self, Ok, Err};
 
-            fn foo() -> Result<String, i32> {
+            fn foo() -> Result<(), i32> {
                 0<|>
             }
 
-            //- /std/lib.rs
-            pub mod string {
-                pub struct String { }
-            }
+            //- /core/lib.rs
             pub mod result {
                 pub enum Result<T, E> { Ok(T), Err(E) }
             }
@@ -444,7 +435,7 @@ mod tests {
     fn test_wrap_return_type_not_applicable_when_return_type_is_not_result() {
         let content = r#"
             //- /main.rs
-            use std::{string::String, result::Result::{self, Ok, Err}};
+            use core::result::Result::{self, Ok, Err};
 
             enum SomeOtherEnum {
                 Ok(i32),
@@ -455,10 +446,7 @@ mod tests {
                 0<|>
             }
 
-            //- /std/lib.rs
-            pub mod string {
-                pub struct String { }
-            }
+            //- /core/lib.rs
             pub mod result {
                 pub enum Result<T, E> { Ok(T), Err(E) }
             }
diff --git a/crates/ra_ide/src/snapshots/highlighting.html b/crates/ra_ide/src/snapshots/highlighting.html
index e34ff5a7d..33548d43c 100644
--- a/crates/ra_ide/src/snapshots/highlighting.html
+++ b/crates/ra_ide/src/snapshots/highlighting.html
@@ -84,7 +84,9 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
     <span class="keyword">let</span> <span class="variable declaration mutable">y</span> = &<span class="keyword">mut</span> <span class="variable mutable">x</span>;
     <span class="keyword">let</span> <span class="variable declaration">z</span> = &<span class="variable mutable">y</span>;
 
-    <span class="variable mutable">y</span>;
+    <span class="keyword">let</span> <span class="struct">Foo</span> { <span class="field">x</span>: <span class="variable declaration">z</span>, <span class="field">y</span> } = <span class="struct">Foo</span> { <span class="field">x</span>: <span class="variable">z</span>, <span class="field">y</span> };
+
+    <span class="variable">y</span>;
 }
 
 <span class="keyword">enum</span> <span class="enum declaration">Option</span>&lt;<span class="type_param declaration">T</span>&gt; {
diff --git a/crates/ra_ide/src/syntax_highlighting/tests.rs b/crates/ra_ide/src/syntax_highlighting/tests.rs
index 021f8e7e2..949bf59a0 100644
--- a/crates/ra_ide/src/syntax_highlighting/tests.rs
+++ b/crates/ra_ide/src/syntax_highlighting/tests.rs
@@ -7,18 +7,6 @@ use crate::{
     FileRange, TextRange,
 };
 
-/// Highlights the code given by the `ra_fixture` argument, renders the
-/// result as HTML, and compares it with the HTML file given as `snapshot`.
-/// Note that the `snapshot` file is overwritten by the rendered HTML.
-fn check_highlighting(ra_fixture: &str, snapshot: &str, rainbow: bool) {
-    let (analysis, file_id) = single_file(ra_fixture);
-    let dst_file = project_dir().join(snapshot);
-    let actual_html = &analysis.highlight_as_html(file_id, rainbow).unwrap();
-    let expected_html = &read_text(&dst_file);
-    fs::write(dst_file, &actual_html).unwrap();
-    assert_eq_text!(expected_html, actual_html);
-}
-
 #[test]
 fn test_highlighting() {
     check_highlighting(
@@ -77,6 +65,8 @@ fn main() {
     let y = &mut x;
     let z = &y;
 
+    let Foo { x: z, y } = Foo { x: z, y };
+
     y;
 }
 
@@ -334,3 +324,15 @@ impl Foo {
         false,
     )
 }
+
+/// Highlights the code given by the `ra_fixture` argument, renders the
+/// result as HTML, and compares it with the HTML file given as `snapshot`.
+/// Note that the `snapshot` file is overwritten by the rendered HTML.
+fn check_highlighting(ra_fixture: &str, snapshot: &str, rainbow: bool) {
+    let (analysis, file_id) = single_file(ra_fixture);
+    let dst_file = project_dir().join(snapshot);
+    let actual_html = &analysis.highlight_as_html(file_id, rainbow).unwrap();
+    let expected_html = &read_text(&dst_file);
+    fs::write(dst_file, &actual_html).unwrap();
+    assert_eq_text!(expected_html, actual_html);
+}
diff --git a/crates/ra_ide/src/typing.rs b/crates/ra_ide/src/typing.rs
index 533306e2e..83776d2b6 100644
--- a/crates/ra_ide/src/typing.rs
+++ b/crates/ra_ide/src/typing.rs
@@ -21,7 +21,9 @@ use ra_ide_db::{source_change::SourceFileEdit, RootDatabase};
 use ra_syntax::{
     algo::find_node_at_offset,
     ast::{self, AstToken},
-    AstNode, SourceFile, TextRange, TextSize,
+    AstNode, SourceFile,
+    SyntaxKind::{FIELD_EXPR, METHOD_CALL_EXPR},
+    TextRange, TextSize,
 };
 
 use ra_text_edit::TextEdit;
@@ -98,9 +100,12 @@ fn on_dot_typed(file: &SourceFile, offset: TextSize) -> Option<TextEdit> {
     };
     let current_indent_len = TextSize::of(current_indent);
 
+    let parent = whitespace.syntax().parent();
     // Make sure dot is a part of call chain
-    let field_expr = ast::FieldExpr::cast(whitespace.syntax().parent())?;
-    let prev_indent = leading_indent(field_expr.syntax())?;
+    if !matches!(parent.kind(), FIELD_EXPR | METHOD_CALL_EXPR) {
+        return None;
+    }
+    let prev_indent = leading_indent(&parent)?;
     let target_indent = format!("    {}", prev_indent);
     let target_indent_len = TextSize::of(&target_indent);
     if current_indent_len == target_indent_len {
@@ -143,11 +148,11 @@ mod tests {
         })
     }
 
-    fn type_char(char_typed: char, before: &str, after: &str) {
-        let actual = do_type_char(char_typed, before)
+    fn type_char(char_typed: char, ra_fixture_before: &str, ra_fixture_after: &str) {
+        let actual = do_type_char(char_typed, ra_fixture_before)
             .unwrap_or_else(|| panic!("typing `{}` did nothing", char_typed));
 
-        assert_eq_text!(after, &actual);
+        assert_eq_text!(ra_fixture_after, &actual);
     }
 
     fn type_char_noop(char_typed: char, before: &str) {
@@ -249,6 +254,27 @@ fn foo() {
     }
 
     #[test]
+    fn indents_new_chain_call_with_let() {
+        type_char(
+            '.',
+            r#"
+fn main() {
+    let _ = foo
+    <|>
+    bar()
+}
+"#,
+            r#"
+fn main() {
+    let _ = foo
+        .
+    bar()
+}
+"#,
+        );
+    }
+
+    #[test]
     fn indents_continued_chain_call() {
         type_char(
             '.',
diff --git a/crates/ra_ide_db/src/change.rs b/crates/ra_ide_db/src/change.rs
index 5dbe1c1b7..2fc796a85 100644
--- a/crates/ra_ide_db/src/change.rs
+++ b/crates/ra_ide_db/src/change.rs
@@ -16,7 +16,7 @@ use rustc_hash::FxHashMap;
 
 use crate::{
     symbol_index::{SymbolIndex, SymbolsDatabase},
-    DebugData, RootDatabase,
+    RootDatabase,
 };
 
 #[derive(Default)]
@@ -26,7 +26,6 @@ pub struct AnalysisChange {
     files_changed: Vec<(FileId, Arc<String>)>,
     libraries_added: Vec<LibraryData>,
     crate_graph: Option<CrateGraph>,
-    debug_data: DebugData,
 }
 
 impl fmt::Debug for AnalysisChange {
@@ -87,10 +86,6 @@ impl AnalysisChange {
     pub fn set_crate_graph(&mut self, graph: CrateGraph) {
         self.crate_graph = Some(graph);
     }
-
-    pub fn set_debug_root_path(&mut self, source_root_id: SourceRootId, path: String) {
-        self.debug_data.root_paths.insert(source_root_id, path);
-    }
 }
 
 #[derive(Debug)]
@@ -218,8 +213,6 @@ impl RootDatabase {
         if let Some(crate_graph) = change.crate_graph {
             self.set_crate_graph_with_durability(Arc::new(crate_graph), Durability::HIGH)
         }
-
-        Arc::make_mut(&mut self.debug_data).merge(change.debug_data)
     }
 
     fn apply_root_change(&mut self, root_id: SourceRootId, root_change: RootChange) {
diff --git a/crates/ra_ide_db/src/defs.rs b/crates/ra_ide_db/src/defs.rs
index 1826f3ac6..3ef5e74b6 100644
--- a/crates/ra_ide_db/src/defs.rs
+++ b/crates/ra_ide_db/src/defs.rs
@@ -78,6 +78,7 @@ impl Definition {
     }
 }
 
+#[derive(Debug)]
 pub enum NameClass {
     Definition(Definition),
     /// `None` in `if let None = Some(82) {}`
@@ -131,9 +132,11 @@ pub fn classify_name(sema: &Semantics<RootDatabase>, name: &ast::Name) -> Option
                 let local = sema.to_def(&it)?;
 
                 if let Some(record_field_pat) = it.syntax().parent().and_then(ast::RecordFieldPat::cast) {
-                    if let Some(field) = sema.resolve_record_field_pat(&record_field_pat) {
-                        let field = Definition::Field(field);
-                        return Some(NameClass::FieldShorthand { local, field });
+                    if record_field_pat.name_ref().is_none() {
+                        if let Some(field) = sema.resolve_record_field_pat(&record_field_pat) {
+                            let field = Definition::Field(field);
+                            return Some(NameClass::FieldShorthand { local, field });
+                        }
                     }
                 }
 
diff --git a/crates/ra_ide_db/src/imports_locator.rs b/crates/ra_ide_db/src/imports_locator.rs
index bf0d8db60..fff112e66 100644
--- a/crates/ra_ide_db/src/imports_locator.rs
+++ b/crates/ra_ide_db/src/imports_locator.rs
@@ -1,7 +1,7 @@
 //! This module contains an import search funcionality that is provided to the ra_assists module.
 //! Later, this should be moved away to a separate crate that is accessible from the ra_assists module.
 
-use hir::{MacroDef, ModuleDef, Semantics};
+use hir::{Crate, MacroDef, ModuleDef, Semantics};
 use ra_prof::profile;
 use ra_syntax::{ast, AstNode, SyntaxKind::NAME};
 
@@ -11,44 +11,46 @@ use crate::{
     RootDatabase,
 };
 use either::Either;
+use rustc_hash::FxHashSet;
 
 pub struct ImportsLocator<'a> {
     sema: Semantics<'a, RootDatabase>,
+    krate: Crate,
 }
 
 impl<'a> ImportsLocator<'a> {
-    pub fn new(db: &'a RootDatabase) -> Self {
-        Self { sema: Semantics::new(db) }
+    pub fn new(db: &'a RootDatabase, krate: Crate) -> Self {
+        Self { sema: Semantics::new(db), krate }
     }
 
     pub fn find_imports(&mut self, name_to_import: &str) -> Vec<Either<ModuleDef, MacroDef>> {
         let _p = profile("search_for_imports");
         let db = self.sema.db;
 
-        let project_results = {
-            let mut query = Query::new(name_to_import.to_string());
-            query.exact();
-            query.limit(40);
-            symbol_index::world_symbols(db, query)
-        };
-        let lib_results = {
+        // Query dependencies first.
+        let mut candidates: FxHashSet<_> =
+            self.krate.query_external_importables(db, name_to_import).collect();
+
+        // Query the local crate using the symbol index.
+        let local_results = {
             let mut query = Query::new(name_to_import.to_string());
-            query.libs();
             query.exact();
             query.limit(40);
-            symbol_index::world_symbols(db, query)
+            symbol_index::crate_symbols(db, self.krate.into(), query)
         };
 
-        project_results
-            .into_iter()
-            .chain(lib_results.into_iter())
-            .filter_map(|import_candidate| self.get_name_definition(&import_candidate))
-            .filter_map(|name_definition_to_import| match name_definition_to_import {
-                Definition::ModuleDef(module_def) => Some(Either::Left(module_def)),
-                Definition::Macro(macro_def) => Some(Either::Right(macro_def)),
-                _ => None,
-            })
-            .collect()
+        candidates.extend(
+            local_results
+                .into_iter()
+                .filter_map(|import_candidate| self.get_name_definition(&import_candidate))
+                .filter_map(|name_definition_to_import| match name_definition_to_import {
+                    Definition::ModuleDef(module_def) => Some(Either::Left(module_def)),
+                    Definition::Macro(macro_def) => Some(Either::Right(macro_def)),
+                    _ => None,
+                }),
+        );
+
+        candidates.into_iter().collect()
     }
 
     fn get_name_definition(&mut self, import_candidate: &FileSymbol) -> Option<Definition> {
diff --git a/crates/ra_ide_db/src/lib.rs b/crates/ra_ide_db/src/lib.rs
index 727d743b5..a808de4f1 100644
--- a/crates/ra_ide_db/src/lib.rs
+++ b/crates/ra_ide_db/src/lib.rs
@@ -17,9 +17,9 @@ use hir::db::{AstDatabase, DefDatabase};
 use ra_db::{
     salsa::{self, Database, Durability},
     Canceled, CheckCanceled, CrateId, FileId, FileLoader, FileLoaderDelegate, SourceDatabase,
-    SourceRootId, Upcast,
+    Upcast,
 };
-use rustc_hash::FxHashMap;
+use rustc_hash::FxHashSet;
 
 use crate::{line_index::LineIndex, symbol_index::SymbolsDatabase};
 
@@ -36,7 +36,6 @@ use crate::{line_index::LineIndex, symbol_index::SymbolsDatabase};
 #[derive(Debug)]
 pub struct RootDatabase {
     runtime: salsa::Runtime<RootDatabase>,
-    pub(crate) debug_data: Arc<DebugData>,
     pub last_gc: crate::wasm_shims::Instant,
     pub last_gc_check: crate::wasm_shims::Instant,
 }
@@ -60,7 +59,7 @@ impl FileLoader for RootDatabase {
     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)
     }
 }
@@ -98,7 +97,6 @@ impl RootDatabase {
             runtime: salsa::Runtime::default(),
             last_gc: crate::wasm_shims::Instant::now(),
             last_gc_check: crate::wasm_shims::Instant::now(),
-            debug_data: Default::default(),
         };
         db.set_crate_graph_with_durability(Default::default(), Durability::HIGH);
         db.set_local_roots_with_durability(Default::default(), Durability::HIGH);
@@ -121,7 +119,6 @@ impl salsa::ParallelDatabase for RootDatabase {
             runtime: self.runtime.snapshot(self),
             last_gc: self.last_gc,
             last_gc_check: self.last_gc_check,
-            debug_data: Arc::clone(&self.debug_data),
         })
     }
 }
@@ -135,14 +132,3 @@ fn line_index(db: &impl LineIndexDatabase, file_id: FileId) -> Arc<LineIndex> {
     let text = db.file_text(file_id);
     Arc::new(LineIndex::new(&*text))
 }
-
-#[derive(Debug, Default, Clone)]
-pub(crate) struct DebugData {
-    pub(crate) root_paths: FxHashMap<SourceRootId, String>,
-}
-
-impl DebugData {
-    pub(crate) fn merge(&mut self, other: DebugData) {
-        self.root_paths.extend(other.root_paths.into_iter());
-    }
-}
diff --git a/crates/ra_ide_db/src/symbol_index.rs b/crates/ra_ide_db/src/symbol_index.rs
index acc31fe3b..aab918973 100644
--- a/crates/ra_ide_db/src/symbol_index.rs
+++ b/crates/ra_ide_db/src/symbol_index.rs
@@ -29,9 +29,10 @@ use std::{
 };
 
 use fst::{self, Streamer};
+use hir::db::DefDatabase;
 use ra_db::{
     salsa::{self, ParallelDatabase},
-    FileId, SourceDatabaseExt, SourceRootId,
+    CrateId, FileId, SourceDatabaseExt, SourceRootId,
 };
 use ra_syntax::{
     ast::{self, NameOwner},
@@ -110,6 +111,14 @@ fn file_symbols(db: &impl SymbolsDatabase, file_id: FileId) -> Arc<SymbolIndex>
     Arc::new(SymbolIndex::new(symbols))
 }
 
+/// Need to wrap Snapshot to provide `Clone` impl for `map_with`
+struct Snap(salsa::Snapshot<RootDatabase>);
+impl Clone for Snap {
+    fn clone(&self) -> Snap {
+        Snap(self.0.snapshot())
+    }
+}
+
 // Feature: Workspace Symbol
 //
 // Uses fuzzy-search to find types, modules and functions by name across your
@@ -132,13 +141,7 @@ fn file_symbols(db: &impl SymbolsDatabase, file_id: FileId) -> Arc<SymbolIndex>
 // | VS Code | kbd:[Ctrl+T]
 // |===
 pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec<FileSymbol> {
-    /// Need to wrap Snapshot to provide `Clone` impl for `map_with`
-    struct Snap(salsa::Snapshot<RootDatabase>);
-    impl Clone for Snap {
-        fn clone(&self) -> Snap {
-            Snap(self.0.snapshot())
-        }
-    }
+    let _p = ra_prof::profile("world_symbols").detail(|| query.query.clone());
 
     let buf: Vec<Arc<SymbolIndex>> = if query.libs {
         let snap = Snap(db.snapshot());
@@ -173,6 +176,33 @@ pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec<FileSymbol> {
     query.search(&buf)
 }
 
+pub fn crate_symbols(db: &RootDatabase, krate: CrateId, query: Query) -> Vec<FileSymbol> {
+    // FIXME(#4842): This now depends on CrateDefMap, why not build the entire symbol index from
+    // that instead?
+
+    let def_map = db.crate_def_map(krate);
+    let mut files = Vec::new();
+    let mut modules = vec![def_map.root];
+    while let Some(module) = modules.pop() {
+        let data = &def_map[module];
+        files.extend(data.origin.file_id());
+        modules.extend(data.children.values());
+    }
+
+    let snap = Snap(db.snapshot());
+
+    #[cfg(not(feature = "wasm"))]
+    let buf = files
+        .par_iter()
+        .map_with(snap, |db, &file_id| db.0.file_symbols(file_id))
+        .collect::<Vec<_>>();
+
+    #[cfg(feature = "wasm")]
+    let buf = files.iter().map(|&file_id| snap.0.file_symbols(file_id)).collect::<Vec<_>>();
+
+    query.search(&buf)
+}
+
 pub fn index_resolve(db: &RootDatabase, name_ref: &ast::NameRef) -> Vec<FileSymbol> {
     let name = name_ref.text();
     let mut query = Query::new(name.to_string());
@@ -298,9 +328,6 @@ impl Query {
         let mut stream = op.union();
         let mut res = Vec::new();
         while let Some((_, indexed_values)) = stream.next() {
-            if res.len() >= self.limit {
-                break;
-            }
             for indexed_value in indexed_values {
                 let symbol_index = &indices[indexed_value.index];
                 let (start, end) = SymbolIndex::map_value_to_range(indexed_value.value);
@@ -312,7 +339,11 @@ impl Query {
                     if self.exact && symbol.name != self.query {
                         continue;
                     }
+
                     res.push(symbol.clone());
+                    if res.len() >= self.limit {
+                        return res;
+                    }
                 }
             }
         }
diff --git a/crates/ra_project_model/src/lib.rs b/crates/ra_project_model/src/lib.rs
index c1f7e3ac5..cb0e27dce 100644
--- a/crates/ra_project_model/src/lib.rs
+++ b/crates/ra_project_model/src/lib.rs
@@ -47,17 +47,21 @@ pub struct PackageRoot {
     path: PathBuf,
     /// Is a member of the current workspace
     is_member: bool,
+    out_dir: Option<PathBuf>,
 }
 impl PackageRoot {
     pub fn new_member(path: PathBuf) -> PackageRoot {
-        Self { path, is_member: true }
+        Self { path, is_member: true, out_dir: None }
     }
     pub fn new_non_member(path: PathBuf) -> PackageRoot {
-        Self { path, is_member: false }
+        Self { path, is_member: false, out_dir: None }
     }
     pub fn path(&self) -> &Path {
         &self.path
     }
+    pub fn out_dir(&self) -> Option<&Path> {
+        self.out_dir.as_deref()
+    }
     pub fn is_member(&self) -> bool {
         self.is_member
     }
@@ -204,6 +208,7 @@ impl ProjectWorkspace {
                 .map(|pkg| PackageRoot {
                     path: cargo[pkg].root().to_path_buf(),
                     is_member: cargo[pkg].is_member,
+                    out_dir: cargo[pkg].out_dir.clone(),
                 })
                 .chain(sysroot.crates().map(|krate| {
                     PackageRoot::new_non_member(sysroot[krate].root_dir().to_path_buf())
@@ -212,17 +217,6 @@ impl ProjectWorkspace {
         }
     }
 
-    pub fn out_dirs(&self) -> Vec<PathBuf> {
-        match self {
-            ProjectWorkspace::Json { project } => {
-                project.crates.iter().filter_map(|krate| krate.out_dir.as_ref()).cloned().collect()
-            }
-            ProjectWorkspace::Cargo { cargo, sysroot: _ } => {
-                cargo.packages().filter_map(|pkg| cargo[pkg].out_dir.as_ref()).cloned().collect()
-            }
-        }
-    }
-
     pub fn proc_macro_dylib_paths(&self) -> Vec<PathBuf> {
         match self {
             ProjectWorkspace::Json { project } => project
diff --git a/crates/rust-analyzer/src/cli/load_cargo.rs b/crates/rust-analyzer/src/cli/load_cargo.rs
index 8f2aeac77..97367d7c6 100644
--- a/crates/rust-analyzer/src/cli/load_cargo.rs
+++ b/crates/rust-analyzer/src/cli/load_cargo.rs
@@ -36,28 +36,28 @@ pub fn load_cargo(
     )?;
 
     let mut extern_dirs = FxHashSet::default();
-    extern_dirs.extend(ws.out_dirs());
-
-    let mut project_roots = ws.to_roots();
-    project_roots.extend(extern_dirs.iter().cloned().map(PackageRoot::new_non_member));
 
     let (sender, receiver) = unbounded();
     let sender = Box::new(move |t| sender.send(t).unwrap());
-    let (mut vfs, roots) = Vfs::new(
-        project_roots
-            .iter()
-            .map(|pkg_root| {
-                RootEntry::new(
-                    pkg_root.path().to_owned(),
-                    RustPackageFilterBuilder::default()
-                        .set_member(pkg_root.is_member())
-                        .into_vfs_filter(),
-                )
-            })
-            .collect(),
-        sender,
-        Watch(false),
-    );
+
+    let mut roots = Vec::new();
+    let project_roots = ws.to_roots();
+    for root in &project_roots {
+        roots.push(RootEntry::new(
+            root.path().to_owned(),
+            RustPackageFilterBuilder::default().set_member(root.is_member()).into_vfs_filter(),
+        ));
+
+        if let Some(out_dir) = root.out_dir() {
+            extern_dirs.insert(out_dir.to_path_buf());
+            roots.push(RootEntry::new(
+                out_dir.to_owned(),
+                RustPackageFilterBuilder::default().set_member(root.is_member()).into_vfs_filter(),
+            ))
+        }
+    }
+
+    let (mut vfs, roots) = Vfs::new(roots, sender, Watch(false));
 
     let source_roots = roots
         .into_iter()
@@ -111,10 +111,6 @@ pub(crate) fn load(
                         vfs.root2path(root)
                     );
                     analysis_change.add_root(source_root_id, is_local);
-                    analysis_change.set_debug_root_path(
-                        source_root_id,
-                        source_roots[&source_root_id].path().display().to_string(),
-                    );
 
                     let vfs_root_path = vfs.root2path(root);
                     if extern_dirs.contains(&vfs_root_path) {
diff --git a/crates/rust-analyzer/src/global_state.rs b/crates/rust-analyzer/src/global_state.rs
index 73b0f881d..21116e165 100644
--- a/crates/rust-analyzer/src/global_state.rs
+++ b/crates/rust-analyzer/src/global_state.rs
@@ -89,8 +89,7 @@ impl GlobalState {
     ) -> GlobalState {
         let mut change = AnalysisChange::new();
 
-        let extern_dirs: FxHashSet<_> =
-            workspaces.iter().flat_map(ProjectWorkspace::out_dirs).collect();
+        let mut extern_dirs: FxHashSet<PathBuf> = FxHashSet::default();
 
         let mut local_roots = Vec::new();
         let roots: Vec<_> = {
@@ -100,22 +99,22 @@ impl GlobalState {
                     .exclude(exclude_globs.iter().cloned())
                     .into_vfs_filter()
             };
-            workspaces
-                .iter()
-                .flat_map(ProjectWorkspace::to_roots)
-                .map(|pkg_root| {
-                    let path = pkg_root.path().to_owned();
-                    if pkg_root.is_member() {
-                        local_roots.push(path.clone());
-                    }
-                    RootEntry::new(path, create_filter(pkg_root.is_member()))
-                })
-                .chain(
-                    extern_dirs
-                        .iter()
-                        .map(|path| RootEntry::new(path.to_owned(), create_filter(false))),
-                )
-                .collect()
+            let mut roots = Vec::new();
+            for root in workspaces.iter().flat_map(ProjectWorkspace::to_roots) {
+                let path = root.path().to_owned();
+                if root.is_member() {
+                    local_roots.push(path.clone());
+                }
+                roots.push(RootEntry::new(path, create_filter(root.is_member())));
+                if let Some(out_dir) = root.out_dir() {
+                    extern_dirs.insert(out_dir.to_path_buf());
+                    roots.push(RootEntry::new(
+                        out_dir.to_path_buf(),
+                        create_filter(root.is_member()),
+                    ))
+                }
+            }
+            roots
         };
 
         let (task_sender, task_receiver) = unbounded();
@@ -127,7 +126,6 @@ impl GlobalState {
             let vfs_root_path = vfs.root2path(r);
             let is_local = local_roots.iter().any(|it| vfs_root_path.starts_with(it));
             change.add_root(SourceRootId(r.0), is_local);
-            change.set_debug_root_path(SourceRootId(r.0), vfs_root_path.display().to_string());
 
             // FIXME: add path2root in vfs to simpily this logic
             if extern_dirs.contains(&vfs_root_path) {