From d50a1a0fe9055bf03b9746cb341b251af8e7b326 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Mon, 8 Jun 2020 13:00:31 +0200 Subject: Profile `world_symbols` --- crates/ra_ide_db/src/symbol_index.rs | 2 ++ 1 file changed, 2 insertions(+) diff --git a/crates/ra_ide_db/src/symbol_index.rs b/crates/ra_ide_db/src/symbol_index.rs index acc31fe3b..299b47c6a 100644 --- a/crates/ra_ide_db/src/symbol_index.rs +++ b/crates/ra_ide_db/src/symbol_index.rs @@ -132,6 +132,8 @@ fn file_symbols(db: &impl SymbolsDatabase, file_id: FileId) -> Arc // | VS Code | kbd:[Ctrl+T] // |=== pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec { + let _p = ra_prof::profile("world_symbols").detail(|| query.query.clone()); + /// Need to wrap Snapshot to provide `Clone` impl for `map_with` struct Snap(salsa::Snapshot); impl Clone for Snap { -- cgit v1.2.3 From 54936e8aa212ea5fdf737d8e1b0a02c231ed89eb Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Mon, 8 Jun 2020 13:00:53 +0200 Subject: Fix the symbol query limit --- crates/ra_ide_db/src/symbol_index.rs | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/crates/ra_ide_db/src/symbol_index.rs b/crates/ra_ide_db/src/symbol_index.rs index 299b47c6a..78c714356 100644 --- a/crates/ra_ide_db/src/symbol_index.rs +++ b/crates/ra_ide_db/src/symbol_index.rs @@ -300,9 +300,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); @@ -314,6 +311,10 @@ impl Query { if self.exact && symbol.name != self.query { continue; } + + if res.len() >= self.limit { + return res; + } res.push(symbol.clone()); } } -- cgit v1.2.3 From 4bcf8c8c68bd791f295aa06ef7903c006be3f356 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Tue, 9 Jun 2020 17:32:42 +0200 Subject: Add an FST index to `ImportMap` --- Cargo.lock | 2 + crates/ra_hir_def/Cargo.toml | 2 + crates/ra_hir_def/src/import_map.rs | 253 +++++++++++++++++++++++++++++++++++- crates/ra_hir_expand/src/name.rs | 7 + 4 files changed, 261 insertions(+), 3 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index df79334c9..4c5551968 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -981,7 +981,9 @@ dependencies = [ "anymap", "drop_bomb", "either", + "fst", "insta", + "itertools", "log", "once_cell", "ra_arena", diff --git a/crates/ra_hir_def/Cargo.toml b/crates/ra_hir_def/Cargo.toml index b85358308..bd69abfc7 100644 --- a/crates/ra_hir_def/Cargo.toml +++ b/crates/ra_hir_def/Cargo.toml @@ -14,6 +14,8 @@ 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" stdx = { path = "../stdx" } diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs index 4284a0a91..e9b2fe26e 100644 --- a/crates/ra_hir_def/src/import_map.rs +++ b/crates/ra_hir_def/src/import_map.rs @@ -1,7 +1,10 @@ //! A map of all publicly exported items in a crate. +use std::cmp::Ordering; use std::{collections::hash_map::Entry, fmt, sync::Arc}; +use fst::{self, Streamer}; +use itertools::Itertools; use ra_db::CrateId; use rustc_hash::FxHashMap; @@ -21,9 +24,17 @@ 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, + + /// 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, + fst: fst::Map>, } impl ImportMap { @@ -88,7 +99,34 @@ impl ImportMap { } } - Arc::new(Self { map: import_map }) + let mut importables = import_map.iter().collect::>(); + + 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: String = fst_path(&importables[start].1).collect(); + + 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 +135,14 @@ impl ImportMap { } } +impl PartialEq for ImportMap { + fn eq(&self, other: &Self) -> bool { + self.importables == other.importables + } +} + +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,13 +163,97 @@ impl fmt::Debug for ImportMap { } } +fn fst_path(path: &ModPath) -> impl Iterator + '_ { + path.segments + .iter() + .map(|name| name.as_text().unwrap()) + .intersperse("::") + .flat_map(|s| s.chars().map(|c| c.to_ascii_lowercase())) +} + +fn cmp((_, lhs): &(&ItemInNs, &ModPath), (_, rhs): &(&ItemInNs, &ModPath)) -> Ordering { + let lhs_chars = fst_path(lhs); + let rhs_chars = fst_path(rhs); + lhs_chars.cmp(rhs_chars) +} + +#[derive(Debug)] +pub struct Query { + query: String, + anchor_end: bool, +} + +impl Query { + pub fn new(query: impl AsRef) -> Self { + Self { query: query.as_ref().to_lowercase(), anchor_end: false } + } + + /// 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 } + } +} + +/// Searches dependencies of `krate` for an importable path matching `query`. +/// +/// This returns all items that could be imported from within `krate`, excluding paths inside +/// `krate` itself. +pub fn search_dependencies<'a>( + db: &'a dyn DefDatabase, + krate: CrateId, + query: Query, +) -> Vec { + let _p = ra_prof::profile("import_map::global_search").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.query); + + 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.query { + continue; + } + } + + // Add the items from this `ModPath` group. Those are all subsequent items in + // `importables` whose paths match `path`. + res.extend(importables.iter().copied().take_while(|item| { + let item_path = &import_map.map[item]; + fst_path(item_path).eq(fst_path(path)) + })); + } + } + + res +} + #[cfg(test)] mod tests { use super::*; use crate::test_db::TestDB; use insta::assert_snapshot; 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); @@ -144,6 +274,40 @@ mod tests { 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 + ) + }) + }) + .collect::>() + .join("\n") + } + #[test] fn smoke() { let map = import_map( @@ -328,4 +492,87 @@ 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 (v) + dep::fmt (t) + dep::Fmt (t) + 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 (v) + dep::fmt (t) + dep::Fmt (t) + dep::Fmt (m) + "###); + } } diff --git a/crates/ra_hir_expand/src/name.rs b/crates/ra_hir_expand/src/name.rs index 660bdfe33..f306d9641 100644 --- a/crates/ra_hir_expand/src/name.rs +++ b/crates/ra_hir_expand/src/name.rs @@ -67,6 +67,13 @@ impl Name { _ => None, } } + + pub fn as_text(&self) -> Option<&str> { + match &self.0 { + Repr::Text(s) => Some(s.as_str()), + _ => None, + } + } } pub trait AsName { -- cgit v1.2.3 From 6463d3ac63a479e33d923593e720696b38a1a54c Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Tue, 9 Jun 2020 18:47:14 +0200 Subject: symbol_index: allow querying a single crate --- crates/ra_ide_db/src/symbol_index.rs | 43 ++++++++++++++++++++++++++++-------- 1 file changed, 34 insertions(+), 9 deletions(-) diff --git a/crates/ra_ide_db/src/symbol_index.rs b/crates/ra_ide_db/src/symbol_index.rs index 78c714356..c974891ea 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 Arc::new(SymbolIndex::new(symbols)) } +/// Need to wrap Snapshot to provide `Clone` impl for `map_with` +struct Snap(salsa::Snapshot); +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 @@ -134,14 +143,6 @@ fn file_symbols(db: &impl SymbolsDatabase, file_id: FileId) -> Arc pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec { let _p = ra_prof::profile("world_symbols").detail(|| query.query.clone()); - /// Need to wrap Snapshot to provide `Clone` impl for `map_with` - struct Snap(salsa::Snapshot); - impl Clone for Snap { - fn clone(&self) -> Snap { - Snap(self.0.snapshot()) - } - } - let buf: Vec> = if query.libs { let snap = Snap(db.snapshot()); #[cfg(not(feature = "wasm"))] @@ -175,6 +176,30 @@ pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec { query.search(&buf) } +pub fn crate_symbols(db: &RootDatabase, krate: CrateId, query: Query) -> Vec { + 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::>(); + + #[cfg(feature = "wasm")] + let buf = files.iter().map(|&file_id| snap.0.file_symbols(file_id)).collect::>(); + + query.search(&buf) +} + pub fn index_resolve(db: &RootDatabase, name_ref: &ast::NameRef) -> Vec { let name = name_ref.text(); let mut query = Query::new(name.to_string()); -- cgit v1.2.3 From b01fb22494eaf64c02c17fc38598a3a2dbd8e980 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Tue, 9 Jun 2020 18:48:00 +0200 Subject: ra_hir: expose `import_map::search_dependencies` --- crates/ra_hir/src/code_model.rs | 14 ++++++++++++++ 1 file changed, 14 insertions(+) diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs index 4a06f3bcd..c8329d971 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,19 @@ 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> { + import_map::search_dependencies(db, self.into(), import_map::Query::new(query).anchor_end()) + .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 { db.crate_graph().iter().map(|id| Crate { id }).collect() } -- cgit v1.2.3 From a70a0ca73ceac339de4e1df6d561894e485ba5ee Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Tue, 9 Jun 2020 18:48:44 +0200 Subject: ImportsLocator: use ImportMap for non-local crates --- crates/ra_assists/src/handlers/auto_import.rs | 47 ++++++++++++++++++++++++++- crates/ra_ide_db/src/imports_locator.rs | 46 +++++++++++++------------- 2 files changed, 70 insertions(+), 23 deletions(-) diff --git a/crates/ra_assists/src/handlers/auto_import.rs b/crates/ra_assists/src/handlers/auto_import.rs index edf96d50e..1f4142747 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 { 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,49 @@ 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() { + 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 {} +", + ); + } } 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> { 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 { -- cgit v1.2.3 From 781b514e5886cbaff88483cdeddc504effef299c Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Wed, 10 Jun 2020 11:39:06 +0200 Subject: Add test for macro generated items --- crates/ra_assists/src/handlers/auto_import.rs | 31 +++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) diff --git a/crates/ra_assists/src/handlers/auto_import.rs b/crates/ra_assists/src/handlers/auto_import.rs index 1f4142747..86a173ff5 100644 --- a/crates/ra_assists/src/handlers/auto_import.rs +++ b/crates/ra_assists/src/handlers/auto_import.rs @@ -865,6 +865,7 @@ fn main() { #[test] fn whole_segment() { + // Tests that only imports whose last segment matches the identifier get suggested. check_assist( auto_import, r" @@ -883,6 +884,36 @@ fn main() { 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; +} ", ); } -- cgit v1.2.3 From bcf875f46ae5142c42ddac8094e1b6652182d4be Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Wed, 10 Jun 2020 11:52:00 +0200 Subject: Clean up import_map.rs --- crates/ra_hir_def/src/import_map.rs | 45 +++++++++++++++++-------------------- crates/ra_hir_expand/src/name.rs | 7 ------ 2 files changed, 20 insertions(+), 32 deletions(-) diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs index e9b2fe26e..f2e4ca2db 100644 --- a/crates/ra_hir_def/src/import_map.rs +++ b/crates/ra_hir_def/src/import_map.rs @@ -1,10 +1,8 @@ //! A map of all publicly exported items in a crate. -use std::cmp::Ordering; -use std::{collections::hash_map::Entry, fmt, sync::Arc}; +use std::{cmp::Ordering, collections::hash_map::Entry, fmt, sync::Arc}; use fst::{self, Streamer}; -use itertools::Itertools; use ra_db::CrateId; use rustc_hash::FxHashMap; @@ -118,7 +116,7 @@ impl ImportMap { let start = last_batch_start; last_batch_start = idx + 1; - let key: String = fst_path(&importables[start].1).collect(); + let key = fst_path(&importables[start].1); builder.insert(key, start as u64).unwrap(); } @@ -137,7 +135,8 @@ impl ImportMap { impl PartialEq for ImportMap { fn eq(&self, other: &Self) -> bool { - self.importables == other.importables + // `fst` and `importables` are built from `map`, so we don't need to compare them. + self.map == other.map } } @@ -163,18 +162,16 @@ impl fmt::Debug for ImportMap { } } -fn fst_path(path: &ModPath) -> impl Iterator + '_ { - path.segments - .iter() - .map(|name| name.as_text().unwrap()) - .intersperse("::") - .flat_map(|s| s.chars().map(|c| c.to_ascii_lowercase())) +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_chars = fst_path(lhs); - let rhs_chars = fst_path(rhs); - lhs_chars.cmp(rhs_chars) + let lhs_str = fst_path(lhs); + let rhs_str = fst_path(rhs); + lhs_str.cmp(&rhs_str) } #[derive(Debug)] @@ -184,8 +181,8 @@ pub struct Query { } impl Query { - pub fn new(query: impl AsRef) -> Self { - Self { query: query.as_ref().to_lowercase(), anchor_end: false } + pub fn new(query: &str) -> Self { + Self { query: query.to_lowercase(), anchor_end: false } } /// Only returns items whose paths end with the (case-insensitive) query string as their last @@ -197,14 +194,13 @@ impl Query { /// Searches dependencies of `krate` for an importable path matching `query`. /// -/// This returns all items that could be imported from within `krate`, excluding paths inside -/// `krate` itself. +/// 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 { - let _p = ra_prof::profile("import_map::global_search").detail(|| format!("{:?}", query)); + let _p = ra_prof::profile("search_dependencies").detail(|| format!("{:?}", query)); let graph = db.crate_graph(); let import_maps: Vec<_> = @@ -239,7 +235,7 @@ pub fn search_dependencies<'a>( // `importables` whose paths match `path`. res.extend(importables.iter().copied().take_while(|item| { let item_path = &import_map.map[item]; - fst_path(item_path).eq(fst_path(path)) + fst_path(item_path) == fst_path(path) })); } } @@ -252,6 +248,7 @@ 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}; @@ -259,7 +256,7 @@ mod tests { 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]; @@ -269,9 +266,8 @@ mod tests { Some(format!("{}:\n{:?}", name, map)) }) - .collect(); - - import_maps.join("\n") + .join("\n"); + s } fn search_dependencies_of(ra_fixture: &str, krate_name: &str, query: Query) -> String { @@ -304,7 +300,6 @@ mod tests { ) }) }) - .collect::>() .join("\n") } diff --git a/crates/ra_hir_expand/src/name.rs b/crates/ra_hir_expand/src/name.rs index f306d9641..660bdfe33 100644 --- a/crates/ra_hir_expand/src/name.rs +++ b/crates/ra_hir_expand/src/name.rs @@ -67,13 +67,6 @@ impl Name { _ => None, } } - - pub fn as_text(&self) -> Option<&str> { - match &self.0 { - Repr::Text(s) => Some(s.as_str()), - _ => None, - } - } } pub trait AsName { -- cgit v1.2.3 From 56c7145993f94a12bf923f08cbd62d963e62bbd1 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Wed, 10 Jun 2020 12:30:33 +0200 Subject: Limit import map queries --- crates/ra_hir/src/code_model.rs | 16 ++++++++------ crates/ra_hir_def/src/import_map.rs | 42 ++++++++++++++++++++++++++++++++++++- 2 files changed, 51 insertions(+), 7 deletions(-) diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs index c8329d971..a55fe03a6 100644 --- a/crates/ra_hir/src/code_model.rs +++ b/crates/ra_hir/src/code_model.rs @@ -104,12 +104,16 @@ impl Crate { db: &dyn DefDatabase, query: &str, ) -> impl Iterator> { - import_map::search_dependencies(db, self.into(), import_map::Query::new(query).anchor_end()) - .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()), - }) + import_map::search_dependencies( + db, + self.into(), + import_map::Query::new(query).anchor_end().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 { diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs index f2e4ca2db..70368d8df 100644 --- a/crates/ra_hir_def/src/import_map.rs +++ b/crates/ra_hir_def/src/import_map.rs @@ -178,11 +178,12 @@ fn cmp((_, lhs): &(&ItemInNs, &ModPath), (_, rhs): &(&ItemInNs, &ModPath)) -> Or pub struct Query { query: String, anchor_end: bool, + limit: usize, } impl Query { pub fn new(query: &str) -> Self { - Self { query: query.to_lowercase(), anchor_end: false } + Self { query: query.to_lowercase(), anchor_end: false, limit: usize::max_value() } } /// Only returns items whose paths end with the (case-insensitive) query string as their last @@ -190,6 +191,11 @@ impl Query { 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 } + } } /// Searches dependencies of `krate` for an importable path matching `query`. @@ -237,6 +243,11 @@ pub fn search_dependencies<'a>( let item_path = &import_map.map[item]; fst_path(item_path) == fst_path(path) })); + + if res.len() >= query.limit { + res.truncate(query.limit); + return res; + } } } @@ -570,4 +581,33 @@ mod tests { dep::Fmt (m) "###); } + + #[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) + "###); + } } -- cgit v1.2.3 From ed2817e599a9c0e812af26587badad6da7a4d949 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Wed, 10 Jun 2020 12:37:00 +0200 Subject: Move limit check down --- crates/ra_ide_db/src/symbol_index.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/crates/ra_ide_db/src/symbol_index.rs b/crates/ra_ide_db/src/symbol_index.rs index c974891ea..ac0a201df 100644 --- a/crates/ra_ide_db/src/symbol_index.rs +++ b/crates/ra_ide_db/src/symbol_index.rs @@ -337,10 +337,10 @@ impl Query { continue; } + res.push(symbol.clone()); if res.len() >= self.limit { return res; } - res.push(symbol.clone()); } } } -- cgit v1.2.3 From 7e83ed99a887f959bd4cf97357faf373a09f9269 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Wed, 10 Jun 2020 16:04:55 +0200 Subject: Respect casing when searching for imports --- crates/ra_assists/src/handlers/auto_import.rs | 25 +++++++++++ crates/ra_hir/src/code_model.rs | 2 +- crates/ra_hir_def/src/import_map.rs | 60 ++++++++++++++++++++++++--- 3 files changed, 81 insertions(+), 6 deletions(-) diff --git a/crates/ra_assists/src/handlers/auto_import.rs b/crates/ra_assists/src/handlers/auto_import.rs index 86a173ff5..5092bf336 100644 --- a/crates/ra_assists/src/handlers/auto_import.rs +++ b/crates/ra_assists/src/handlers/auto_import.rs @@ -914,6 +914,31 @@ impl fmt::Display for S {} 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_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs index a55fe03a6..1a9f6cc76 100644 --- a/crates/ra_hir/src/code_model.rs +++ b/crates/ra_hir/src/code_model.rs @@ -107,7 +107,7 @@ impl Crate { import_map::search_dependencies( db, self.into(), - import_map::Query::new(query).anchor_end().limit(40), + import_map::Query::new(query).anchor_end().case_sensitive().limit(40), ) .into_iter() .map(|item| match item { diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs index 70368d8df..a55d7d83b 100644 --- a/crates/ra_hir_def/src/import_map.rs +++ b/crates/ra_hir_def/src/import_map.rs @@ -177,13 +177,21 @@ fn cmp((_, lhs): &(&ItemInNs, &ModPath), (_, rhs): &(&ItemInNs, &ModPath)) -> Or #[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 { query: query.to_lowercase(), anchor_end: false, limit: usize::max_value() } + 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 @@ -196,6 +204,11 @@ impl Query { 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`. @@ -212,7 +225,7 @@ pub fn search_dependencies<'a>( let import_maps: Vec<_> = graph[krate].dependencies.iter().map(|dep| db.import_map(dep.crate_id)).collect(); - let automaton = fst::automaton::Subsequence::new(&query.query); + let automaton = fst::automaton::Subsequence::new(&query.lowercased); let mut op = fst::map::OpBuilder::new(); for map in &import_maps { @@ -232,17 +245,27 @@ pub fn search_dependencies<'a>( if query.anchor_end { // Last segment must match query. let last = path.segments.last().unwrap().to_string(); - if last.to_lowercase() != query.query { + 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`. - res.extend(importables.iter().copied().take_while(|item| { + 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); @@ -582,6 +605,33 @@ mod tests { "###); } + #[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 (v) + dep::FMT (t) + 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 (v) + dep::FMT (t) + "###); + } + #[test] fn search_limit() { let res = search_dependencies_of( -- cgit v1.2.3 From dd22657407bb0ab24d141275fd4f0d87269262c8 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Wed, 10 Jun 2020 16:15:49 +0200 Subject: ImportMap: use IndexMap internally It iterates in insertion order, which makes the ordering more predictable. --- Cargo.lock | 1 + crates/ra_hir_def/Cargo.toml | 1 + crates/ra_hir_def/src/import_map.rs | 21 ++++++++++++--------- 3 files changed, 14 insertions(+), 9 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 4c5551968..e6338e316 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -982,6 +982,7 @@ dependencies = [ "drop_bomb", "either", "fst", + "indexmap", "insta", "itertools", "log", diff --git a/crates/ra_hir_def/Cargo.toml b/crates/ra_hir_def/Cargo.toml index bd69abfc7..ef1f65ee0 100644 --- a/crates/ra_hir_def/Cargo.toml +++ b/crates/ra_hir_def/Cargo.toml @@ -16,6 +16,7 @@ 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/import_map.rs b/crates/ra_hir_def/src/import_map.rs index a55d7d83b..36b4fdd81 100644 --- a/crates/ra_hir_def/src/import_map.rs +++ b/crates/ra_hir_def/src/import_map.rs @@ -1,10 +1,11 @@ //! A map of all publicly exported items in a crate. -use std::{cmp::Ordering, 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, @@ -14,6 +15,8 @@ use crate::{ ModuleDefId, ModuleId, }; +type FxIndexMap = IndexMap>; + /// A map from publicly exported items to the path needed to import/name them from a downstream /// crate. /// @@ -23,7 +26,7 @@ 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. pub struct ImportMap { - map: FxHashMap, + map: FxIndexMap, /// List of keys stored in `map`, sorted lexicographically by their `ModPath`. Indexed by the /// values returned by running `fst`. @@ -39,7 +42,7 @@ impl ImportMap { pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc { 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![] }; @@ -588,9 +591,9 @@ mod tests { let res = search_dependencies_of(ra_fixture, "main", Query::new("fmt")); assert_snapshot!(res, @r###" - dep::Fmt (v) dep::fmt (t) dep::Fmt (t) + dep::Fmt (v) dep::Fmt (m) dep::fmt::Display (t) dep::format (v) @@ -598,9 +601,9 @@ mod tests { let res = search_dependencies_of(ra_fixture, "main", Query::new("fmt").anchor_end()); assert_snapshot!(res, @r###" - dep::Fmt (v) dep::fmt (t) dep::Fmt (t) + dep::Fmt (v) dep::Fmt (m) "###); } @@ -618,17 +621,17 @@ mod tests { let res = search_dependencies_of(ra_fixture, "main", Query::new("FMT")); assert_snapshot!(res, @r###" - dep::FMT (v) - dep::FMT (t) 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 (v) dep::FMT (t) + dep::FMT (v) "###); } -- cgit v1.2.3 From 6766a6b0e189f47d7a405c872598bca9a2395360 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Thu, 11 Jun 2020 12:03:08 +0200 Subject: Add symbol index FIXME --- crates/ra_ide_db/src/symbol_index.rs | 3 +++ 1 file changed, 3 insertions(+) diff --git a/crates/ra_ide_db/src/symbol_index.rs b/crates/ra_ide_db/src/symbol_index.rs index ac0a201df..aab918973 100644 --- a/crates/ra_ide_db/src/symbol_index.rs +++ b/crates/ra_ide_db/src/symbol_index.rs @@ -177,6 +177,9 @@ pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec { } pub fn crate_symbols(db: &RootDatabase, krate: CrateId, query: Query) -> Vec { + // 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]; -- cgit v1.2.3