aboutsummaryrefslogtreecommitdiff
path: root/crates
diff options
context:
space:
mode:
authorbors[bot] <26634292+bors[bot]@users.noreply.github.com>2021-06-10 22:28:14 +0100
committerGitHub <[email protected]>2021-06-10 22:28:14 +0100
commitc4c1fcb8e902adcc7879996fa7f53200fb36ce33 (patch)
tree47210c5b426680b218362ca4dd58f2ee79cf6244 /crates
parentf4da4de7cdd4a7dfe40a417b0100b83ec50d1e1d (diff)
parent690cd953273317ee4f3eaefd95bbd3538e929522 (diff)
Merge #9206
9206: minor: Speed up fst items lookup during completions r=SomeoneToIgnore a=SomeoneToIgnore Part of https://github.com/rust-analyzer/rust-analyzer/issues/7542 A number of profile calls added for `import_on_the_fly` contents. Before: <img width="606" alt="Screenshot 2021-06-11 at 00 19 13" src="https://user-images.githubusercontent.com/2690773/121598998-22321e80-ca4b-11eb-9a3d-dc9cb2936705.png"> After: <img width="859" alt="Screenshot 2021-06-11 at 00 19 27" src="https://user-images.githubusercontent.com/2690773/121599022-2a8a5980-ca4b-11eb-82b6-13ab0ed56d58.png"> As a result, low hanging fruit was spotted: crazy amount of `fst_path` calls. Reducing that won ~200ms in the `import_on_the_fly @ sel` case in the `integrated_completion_benchmark`: <img width="861" alt="Screenshot 2021-06-11 at 00 19 38" src="https://user-images.githubusercontent.com/2690773/121599277-7d641100-ca4b-11eb-8667-53206994de27.png"> I'm not sure how to proceed with the remaining `???` marks in such methods as `collect_import_map` though: there's nothing but library calls in cycles, but maybe I'll come up with something later. Co-authored-by: Kirill Bulatov <[email protected]>
Diffstat (limited to 'crates')
-rw-r--r--crates/base_db/src/lib.rs1
-rw-r--r--crates/hir/src/lib.rs4
-rw-r--r--crates/hir_def/src/import_map.rs169
-rw-r--r--crates/hir_def/src/lang_item.rs1
-rw-r--r--crates/hir_def/src/per_ns.rs2
-rw-r--r--crates/ide_db/src/symbol_index.rs2
6 files changed, 97 insertions, 82 deletions
diff --git a/crates/base_db/src/lib.rs b/crates/base_db/src/lib.rs
index 62bf2a4b2..54baa3a63 100644
--- a/crates/base_db/src/lib.rs
+++ b/crates/base_db/src/lib.rs
@@ -120,6 +120,7 @@ impl<T: SourceDatabaseExt> FileLoader for FileLoaderDelegate<&'_ T> {
120 } 120 }
121 121
122 fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>> { 122 fn relevant_crates(&self, file_id: FileId) -> Arc<FxHashSet<CrateId>> {
123 let _p = profile::span("relevant_crates");
123 let source_root = self.0.file_source_root(file_id); 124 let source_root = self.0.file_source_root(file_id);
124 self.0.source_root_crates(source_root) 125 self.0.source_root_crates(source_root)
125 } 126 }
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index debc3ee62..b9c1dc44d 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -191,6 +191,7 @@ impl Crate {
191 db: &dyn DefDatabase, 191 db: &dyn DefDatabase,
192 query: import_map::Query, 192 query: import_map::Query,
193 ) -> impl Iterator<Item = Either<ModuleDef, MacroDef>> { 193 ) -> impl Iterator<Item = Either<ModuleDef, MacroDef>> {
194 let _p = profile::span("query_external_importables");
194 import_map::search_dependencies(db, self.into(), query).into_iter().map(|item| match item { 195 import_map::search_dependencies(db, self.into(), query).into_iter().map(|item| match item {
195 ItemInNs::Types(mod_id) | ItemInNs::Values(mod_id) => Either::Left(mod_id.into()), 196 ItemInNs::Types(mod_id) | ItemInNs::Values(mod_id) => Either::Left(mod_id.into()),
196 ItemInNs::Macros(mac_id) => Either::Right(mac_id.into()), 197 ItemInNs::Macros(mac_id) => Either::Right(mac_id.into()),
@@ -2185,6 +2186,7 @@ impl Type {
2185 name: Option<&Name>, 2186 name: Option<&Name>,
2186 mut callback: impl FnMut(&Ty, Function) -> Option<T>, 2187 mut callback: impl FnMut(&Ty, Function) -> Option<T>,
2187 ) -> Option<T> { 2188 ) -> Option<T> {
2189 let _p = profile::span("iterate_method_candidates");
2188 // There should be no inference vars in types passed here 2190 // There should be no inference vars in types passed here
2189 // FIXME check that? 2191 // FIXME check that?
2190 // FIXME replace Unknown by bound vars here 2192 // FIXME replace Unknown by bound vars here
@@ -2218,6 +2220,7 @@ impl Type {
2218 name: Option<&Name>, 2220 name: Option<&Name>,
2219 mut callback: impl FnMut(&Ty, AssocItem) -> Option<T>, 2221 mut callback: impl FnMut(&Ty, AssocItem) -> Option<T>,
2220 ) -> Option<T> { 2222 ) -> Option<T> {
2223 let _p = profile::span("iterate_path_candidates");
2221 let canonical = hir_ty::replace_errors_with_variables(&self.ty); 2224 let canonical = hir_ty::replace_errors_with_variables(&self.ty);
2222 2225
2223 let env = self.env.clone(); 2226 let env = self.env.clone();
@@ -2255,6 +2258,7 @@ impl Type {
2255 &'a self, 2258 &'a self,
2256 db: &'a dyn HirDatabase, 2259 db: &'a dyn HirDatabase,
2257 ) -> impl Iterator<Item = Trait> + 'a { 2260 ) -> impl Iterator<Item = Trait> + 'a {
2261 let _p = profile::span("applicable_inherent_traits");
2258 self.autoderef(db) 2262 self.autoderef(db)
2259 .filter_map(|derefed_type| derefed_type.ty.dyn_trait()) 2263 .filter_map(|derefed_type| derefed_type.ty.dyn_trait())
2260 .flat_map(move |dyn_trait_id| hir_ty::all_super_traits(db.upcast(), dyn_trait_id)) 2264 .flat_map(move |dyn_trait_id| hir_ty::all_super_traits(db.upcast(), dyn_trait_id))
diff --git a/crates/hir_def/src/import_map.rs b/crates/hir_def/src/import_map.rs
index 960cabb5f..404e3e153 100644
--- a/crates/hir_def/src/import_map.rs
+++ b/crates/hir_def/src/import_map.rs
@@ -1,6 +1,6 @@
1//! A map of all publicly exported items in a crate. 1//! A map of all publicly exported items in a crate.
2 2
3use std::{cmp::Ordering, fmt, hash::BuildHasherDefault, sync::Arc}; 3use std::{fmt, hash::BuildHasherDefault, sync::Arc};
4 4
5use base_db::CrateId; 5use base_db::CrateId;
6use fst::{self, Streamer}; 6use fst::{self, Streamer};
@@ -69,81 +69,11 @@ pub struct ImportMap {
69impl ImportMap { 69impl ImportMap {
70 pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> { 70 pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
71 let _p = profile::span("import_map_query"); 71 let _p = profile::span("import_map_query");
72 let def_map = db.crate_def_map(krate);
73 let mut import_map = Self::default();
74
75 // We look only into modules that are public(ly reexported), starting with the crate root.
76 let empty = ImportPath { segments: vec![] };
77 let root = def_map.module_id(def_map.root());
78 let mut worklist = vec![(root, empty)];
79 while let Some((module, mod_path)) = worklist.pop() {
80 let ext_def_map;
81 let mod_data = if module.krate == krate {
82 &def_map[module.local_id]
83 } else {
84 // The crate might reexport a module defined in another crate.
85 ext_def_map = module.def_map(db);
86 &ext_def_map[module.local_id]
87 };
88
89 let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
90 let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
91 if per_ns.is_none() {
92 None
93 } else {
94 Some((name, per_ns))
95 }
96 });
97
98 for (name, per_ns) in visible_items {
99 let mk_path = || {
100 let mut path = mod_path.clone();
101 path.segments.push(name.clone());
102 path
103 };
104
105 for item in per_ns.iter_items() {
106 let path = mk_path();
107 let path_len = path.len();
108 let import_info =
109 ImportInfo { path, container: module, is_trait_assoc_item: false };
110
111 if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
112 import_map.collect_trait_assoc_items(
113 db,
114 tr,
115 matches!(item, ItemInNs::Types(_)),
116 &import_info,
117 );
118 }
119 72
120 match import_map.map.entry(item) { 73 let mut import_map = collect_import_map(db, krate);
121 Entry::Vacant(entry) => {
122 entry.insert(import_info);
123 }
124 Entry::Occupied(mut entry) => {
125 // If the new path is shorter, prefer that one.
126 if path_len < entry.get().path.len() {
127 *entry.get_mut() = import_info;
128 } else {
129 continue;
130 }
131 }
132 }
133
134 // If we've just added a path to a module, descend into it. We might traverse
135 // modules multiple times, but only if the new path to it is shorter than the
136 // first (else we `continue` above).
137 if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
138 worklist.push((mod_id, mk_path()));
139 }
140 }
141 }
142 }
143 74
144 let mut importables = import_map.map.iter().collect::<Vec<_>>(); 75 let mut importables = import_map.map.iter().collect::<Vec<_>>();
145 76 importables.sort_by_cached_key(|(_, import_info)| fst_path(&import_info.path));
146 importables.sort_by(cmp);
147 77
148 // Build the FST, taking care not to insert duplicate values. 78 // Build the FST, taking care not to insert duplicate values.
149 79
@@ -151,13 +81,13 @@ impl ImportMap {
151 let mut last_batch_start = 0; 81 let mut last_batch_start = 0;
152 82
153 for idx in 0..importables.len() { 83 for idx in 0..importables.len() {
154 if let Some(next_item) = importables.get(idx + 1) { 84 let key = fst_path(&importables[last_batch_start].1.path);
155 if cmp(&importables[last_batch_start], next_item) == Ordering::Equal { 85 if let Some((_, next_import_info)) = importables.get(idx + 1) {
86 if key == fst_path(&next_import_info.path) {
156 continue; 87 continue;
157 } 88 }
158 } 89 }
159 90
160 let key = fst_path(&importables[last_batch_start].1.path);
161 builder.insert(key, last_batch_start as u64).unwrap(); 91 builder.insert(key, last_batch_start as u64).unwrap();
162 92
163 last_batch_start = idx + 1; 93 last_batch_start = idx + 1;
@@ -185,6 +115,7 @@ impl ImportMap {
185 is_type_in_ns: bool, 115 is_type_in_ns: bool,
186 original_import_info: &ImportInfo, 116 original_import_info: &ImportInfo,
187 ) { 117 ) {
118 let _p = profile::span("collect_trait_assoc_items");
188 for (assoc_item_name, item) in &db.trait_data(tr).items { 119 for (assoc_item_name, item) in &db.trait_data(tr).items {
189 let module_def_id = match item { 120 let module_def_id = match item {
190 AssocItemId::FunctionId(f) => ModuleDefId::from(*f), 121 AssocItemId::FunctionId(f) => ModuleDefId::from(*f),
@@ -210,6 +141,84 @@ impl ImportMap {
210 } 141 }
211} 142}
212 143
144fn collect_import_map(db: &dyn DefDatabase, krate: CrateId) -> ImportMap {
145 let _p = profile::span("collect_import_map");
146
147 let def_map = db.crate_def_map(krate);
148 let mut import_map = ImportMap::default();
149
150 // We look only into modules that are public(ly reexported), starting with the crate root.
151 let empty = ImportPath { segments: vec![] };
152 let root = def_map.module_id(def_map.root());
153 let mut worklist = vec![(root, empty)];
154 while let Some((module, mod_path)) = worklist.pop() {
155 let ext_def_map;
156 let mod_data = if module.krate == krate {
157 &def_map[module.local_id]
158 } else {
159 // The crate might reexport a module defined in another crate.
160 ext_def_map = module.def_map(db);
161 &ext_def_map[module.local_id]
162 };
163
164 let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
165 let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
166 if per_ns.is_none() {
167 None
168 } else {
169 Some((name, per_ns))
170 }
171 });
172
173 for (name, per_ns) in visible_items {
174 let mk_path = || {
175 let mut path = mod_path.clone();
176 path.segments.push(name.clone());
177 path
178 };
179
180 for item in per_ns.iter_items() {
181 let path = mk_path();
182 let path_len = path.len();
183 let import_info =
184 ImportInfo { path, container: module, is_trait_assoc_item: false };
185
186 if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
187 import_map.collect_trait_assoc_items(
188 db,
189 tr,
190 matches!(item, ItemInNs::Types(_)),
191 &import_info,
192 );
193 }
194
195 match import_map.map.entry(item) {
196 Entry::Vacant(entry) => {
197 entry.insert(import_info);
198 }
199 Entry::Occupied(mut entry) => {
200 // If the new path is shorter, prefer that one.
201 if path_len < entry.get().path.len() {
202 *entry.get_mut() = import_info;
203 } else {
204 continue;
205 }
206 }
207 }
208
209 // If we've just added a path to a module, descend into it. We might traverse
210 // modules multiple times, but only if the new path to it is shorter than the
211 // first (else we `continue` above).
212 if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
213 worklist.push((mod_id, mk_path()));
214 }
215 }
216 }
217 }
218
219 import_map
220}
221
213impl PartialEq for ImportMap { 222impl PartialEq for ImportMap {
214 fn eq(&self, other: &Self) -> bool { 223 fn eq(&self, other: &Self) -> bool {
215 // `fst` and `importables` are built from `map`, so we don't need to compare them. 224 // `fst` and `importables` are built from `map`, so we don't need to compare them.
@@ -240,17 +249,12 @@ impl fmt::Debug for ImportMap {
240} 249}
241 250
242fn fst_path(path: &ImportPath) -> String { 251fn fst_path(path: &ImportPath) -> String {
252 let _p = profile::span("fst_path");
243 let mut s = path.to_string(); 253 let mut s = path.to_string();
244 s.make_ascii_lowercase(); 254 s.make_ascii_lowercase();
245 s 255 s
246} 256}
247 257
248fn cmp((_, lhs): &(&ItemInNs, &ImportInfo), (_, rhs): &(&ItemInNs, &ImportInfo)) -> Ordering {
249 let lhs_str = fst_path(&lhs.path);
250 let rhs_str = fst_path(&rhs.path);
251 lhs_str.cmp(&rhs_str)
252}
253
254#[derive(Debug, Eq, PartialEq, Hash)] 258#[derive(Debug, Eq, PartialEq, Hash)]
255pub enum ImportKind { 259pub enum ImportKind {
256 Module, 260 Module,
@@ -338,6 +342,7 @@ impl Query {
338 } 342 }
339 343
340 fn import_matches(&self, import: &ImportInfo, enforce_lowercase: bool) -> bool { 344 fn import_matches(&self, import: &ImportInfo, enforce_lowercase: bool) -> bool {
345 let _p = profile::span("import_map::Query::import_matches");
341 if import.is_trait_assoc_item { 346 if import.is_trait_assoc_item {
342 if self.exclude_import_kinds.contains(&ImportKind::AssociatedItem) { 347 if self.exclude_import_kinds.contains(&ImportKind::AssociatedItem) {
343 return false; 348 return false;
diff --git a/crates/hir_def/src/lang_item.rs b/crates/hir_def/src/lang_item.rs
index 9e90f745c..3a45cbfa1 100644
--- a/crates/hir_def/src/lang_item.rs
+++ b/crates/hir_def/src/lang_item.rs
@@ -141,6 +141,7 @@ impl LangItems {
141 ) where 141 ) where
142 T: Into<AttrDefId> + Copy, 142 T: Into<AttrDefId> + Copy,
143 { 143 {
144 let _p = profile::span("collect_lang_item");
144 if let Some(lang_item_name) = lang_attr(db, item) { 145 if let Some(lang_item_name) = lang_attr(db, item) {
145 self.items.entry(lang_item_name).or_insert_with(|| constructor(item)); 146 self.items.entry(lang_item_name).or_insert_with(|| constructor(item));
146 } 147 }
diff --git a/crates/hir_def/src/per_ns.rs b/crates/hir_def/src/per_ns.rs
index a594afce6..a9f13cb82 100644
--- a/crates/hir_def/src/per_ns.rs
+++ b/crates/hir_def/src/per_ns.rs
@@ -62,6 +62,7 @@ impl PerNs {
62 } 62 }
63 63
64 pub fn filter_visibility(self, mut f: impl FnMut(Visibility) -> bool) -> PerNs { 64 pub fn filter_visibility(self, mut f: impl FnMut(Visibility) -> bool) -> PerNs {
65 let _p = profile::span("PerNs::filter_visibility");
65 PerNs { 66 PerNs {
66 types: self.types.filter(|(_, v)| f(*v)), 67 types: self.types.filter(|(_, v)| f(*v)),
67 values: self.values.filter(|(_, v)| f(*v)), 68 values: self.values.filter(|(_, v)| f(*v)),
@@ -86,6 +87,7 @@ impl PerNs {
86 } 87 }
87 88
88 pub fn iter_items(self) -> impl Iterator<Item = ItemInNs> { 89 pub fn iter_items(self) -> impl Iterator<Item = ItemInNs> {
90 let _p = profile::span("PerNs::iter_items");
89 self.types 91 self.types
90 .map(|it| ItemInNs::Types(it.0)) 92 .map(|it| ItemInNs::Types(it.0))
91 .into_iter() 93 .into_iter()
diff --git a/crates/ide_db/src/symbol_index.rs b/crates/ide_db/src/symbol_index.rs
index 5c372a7e5..000f87a85 100644
--- a/crates/ide_db/src/symbol_index.rs
+++ b/crates/ide_db/src/symbol_index.rs
@@ -197,6 +197,7 @@ pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec<FileSymbol> {
197} 197}
198 198
199pub fn crate_symbols(db: &RootDatabase, krate: CrateId, query: Query) -> Vec<FileSymbol> { 199pub fn crate_symbols(db: &RootDatabase, krate: CrateId, query: Query) -> Vec<FileSymbol> {
200 let _p = profile::span("crate_symbols").detail(|| format!("{:?}", query));
200 // FIXME(#4842): This now depends on CrateDefMap, why not build the entire symbol index from 201 // FIXME(#4842): This now depends on CrateDefMap, why not build the entire symbol index from
201 // that instead? 202 // that instead?
202 203
@@ -321,6 +322,7 @@ impl SymbolIndex {
321 322
322impl Query { 323impl Query {
323 pub(crate) fn search(self, indices: &[&SymbolIndex]) -> Vec<FileSymbol> { 324 pub(crate) fn search(self, indices: &[&SymbolIndex]) -> Vec<FileSymbol> {
325 let _p = profile::span("symbol_index::Query::search");
324 let mut op = fst::map::OpBuilder::new(); 326 let mut op = fst::map::OpBuilder::new();
325 for file_symbols in indices.iter() { 327 for file_symbols in indices.iter() {
326 let automaton = fst::automaton::Subsequence::new(&self.lowercased); 328 let automaton = fst::automaton::Subsequence::new(&self.lowercased);