aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_ide
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_ide')
-rw-r--r--crates/ra_ide/Cargo.toml1
-rw-r--r--crates/ra_ide/src/ide_db/change.rs386
-rw-r--r--crates/ra_ide/src/ide_db/feature_flags.rs71
-rw-r--r--crates/ra_ide/src/ide_db/line_index.rs283
-rw-r--r--crates/ra_ide/src/ide_db/line_index_utils.rs334
-rw-r--r--crates/ra_ide/src/ide_db/mod.rs137
-rw-r--r--crates/ra_ide/src/ide_db/symbol_index.rs445
-rw-r--r--crates/ra_ide/src/lib.rs5
-rw-r--r--crates/ra_ide/src/wasm_shims.rs19
9 files changed, 4 insertions, 1677 deletions
diff --git a/crates/ra_ide/Cargo.toml b/crates/ra_ide/Cargo.toml
index 53817d1f7..9ace35229 100644
--- a/crates/ra_ide/Cargo.toml
+++ b/crates/ra_ide/Cargo.toml
@@ -28,6 +28,7 @@ once_cell = "1.2.0"
28ra_syntax = { path = "../ra_syntax" } 28ra_syntax = { path = "../ra_syntax" }
29ra_text_edit = { path = "../ra_text_edit" } 29ra_text_edit = { path = "../ra_text_edit" }
30ra_db = { path = "../ra_db" } 30ra_db = { path = "../ra_db" }
31ra_ide_db = { path = "../ra_ide_db" }
31ra_cfg = { path = "../ra_cfg" } 32ra_cfg = { path = "../ra_cfg" }
32ra_fmt = { path = "../ra_fmt" } 33ra_fmt = { path = "../ra_fmt" }
33ra_prof = { path = "../ra_prof" } 34ra_prof = { path = "../ra_prof" }
diff --git a/crates/ra_ide/src/ide_db/change.rs b/crates/ra_ide/src/ide_db/change.rs
deleted file mode 100644
index 62ffa6920..000000000
--- a/crates/ra_ide/src/ide_db/change.rs
+++ /dev/null
@@ -1,386 +0,0 @@
1//! FIXME: write short doc here
2
3use std::{fmt, sync::Arc, time};
4
5use ra_db::{
6 salsa::{Database, Durability, SweepStrategy},
7 CrateGraph, CrateId, FileId, RelativePathBuf, SourceDatabase, SourceDatabaseExt, SourceRoot,
8 SourceRootId,
9};
10use ra_prof::{memory_usage, profile, Bytes};
11use ra_syntax::SourceFile;
12#[cfg(not(feature = "wasm"))]
13use rayon::prelude::*;
14use rustc_hash::FxHashMap;
15
16use crate::ide_db::{
17 symbol_index::{SymbolIndex, SymbolsDatabase},
18 DebugData, RootDatabase,
19};
20
21#[derive(Default)]
22pub struct AnalysisChange {
23 new_roots: Vec<(SourceRootId, bool)>,
24 roots_changed: FxHashMap<SourceRootId, RootChange>,
25 files_changed: Vec<(FileId, Arc<String>)>,
26 libraries_added: Vec<LibraryData>,
27 crate_graph: Option<CrateGraph>,
28 debug_data: DebugData,
29}
30
31impl fmt::Debug for AnalysisChange {
32 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
33 let mut d = fmt.debug_struct("AnalysisChange");
34 if !self.new_roots.is_empty() {
35 d.field("new_roots", &self.new_roots);
36 }
37 if !self.roots_changed.is_empty() {
38 d.field("roots_changed", &self.roots_changed);
39 }
40 if !self.files_changed.is_empty() {
41 d.field("files_changed", &self.files_changed.len());
42 }
43 if !self.libraries_added.is_empty() {
44 d.field("libraries_added", &self.libraries_added.len());
45 }
46 if !self.crate_graph.is_none() {
47 d.field("crate_graph", &self.crate_graph);
48 }
49 d.finish()
50 }
51}
52
53impl AnalysisChange {
54 pub fn new() -> AnalysisChange {
55 AnalysisChange::default()
56 }
57
58 pub fn add_root(&mut self, root_id: SourceRootId, is_local: bool) {
59 self.new_roots.push((root_id, is_local));
60 }
61
62 pub fn add_file(
63 &mut self,
64 root_id: SourceRootId,
65 file_id: FileId,
66 path: RelativePathBuf,
67 text: Arc<String>,
68 ) {
69 let file = AddFile { file_id, path, text };
70 self.roots_changed.entry(root_id).or_default().added.push(file);
71 }
72
73 pub fn change_file(&mut self, file_id: FileId, new_text: Arc<String>) {
74 self.files_changed.push((file_id, new_text))
75 }
76
77 pub fn remove_file(&mut self, root_id: SourceRootId, file_id: FileId, path: RelativePathBuf) {
78 let file = RemoveFile { file_id, path };
79 self.roots_changed.entry(root_id).or_default().removed.push(file);
80 }
81
82 pub fn add_library(&mut self, data: LibraryData) {
83 self.libraries_added.push(data)
84 }
85
86 pub fn set_crate_graph(&mut self, graph: CrateGraph) {
87 self.crate_graph = Some(graph);
88 }
89
90 pub fn set_debug_crate_name(&mut self, crate_id: CrateId, name: String) {
91 self.debug_data.crate_names.insert(crate_id, name);
92 }
93
94 pub fn set_debug_root_path(&mut self, source_root_id: SourceRootId, path: String) {
95 self.debug_data.root_paths.insert(source_root_id, path);
96 }
97}
98
99#[derive(Debug)]
100struct AddFile {
101 file_id: FileId,
102 path: RelativePathBuf,
103 text: Arc<String>,
104}
105
106#[derive(Debug)]
107struct RemoveFile {
108 file_id: FileId,
109 path: RelativePathBuf,
110}
111
112#[derive(Default)]
113struct RootChange {
114 added: Vec<AddFile>,
115 removed: Vec<RemoveFile>,
116}
117
118impl fmt::Debug for RootChange {
119 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
120 fmt.debug_struct("AnalysisChange")
121 .field("added", &self.added.len())
122 .field("removed", &self.removed.len())
123 .finish()
124 }
125}
126
127pub struct LibraryData {
128 root_id: SourceRootId,
129 root_change: RootChange,
130 symbol_index: SymbolIndex,
131}
132
133impl fmt::Debug for LibraryData {
134 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
135 f.debug_struct("LibraryData")
136 .field("root_id", &self.root_id)
137 .field("root_change", &self.root_change)
138 .field("n_symbols", &self.symbol_index.len())
139 .finish()
140 }
141}
142
143impl LibraryData {
144 pub fn prepare(
145 root_id: SourceRootId,
146 files: Vec<(FileId, RelativePathBuf, Arc<String>)>,
147 ) -> LibraryData {
148 let _p = profile("LibraryData::prepare");
149
150 #[cfg(not(feature = "wasm"))]
151 let iter = files.par_iter();
152 #[cfg(feature = "wasm")]
153 let iter = files.iter();
154
155 let symbol_index = SymbolIndex::for_files(iter.map(|(file_id, _, text)| {
156 let parse = SourceFile::parse(text);
157 (*file_id, parse)
158 }));
159 let mut root_change = RootChange::default();
160 root_change.added = files
161 .into_iter()
162 .map(|(file_id, path, text)| AddFile { file_id, path, text })
163 .collect();
164 LibraryData { root_id, root_change, symbol_index }
165 }
166}
167
168const GC_COOLDOWN: time::Duration = time::Duration::from_millis(100);
169
170impl RootDatabase {
171 pub(crate) fn request_cancellation(&mut self) {
172 let _p = profile("RootDatabase::request_cancellation");
173 self.salsa_runtime_mut().synthetic_write(Durability::LOW);
174 }
175
176 pub(crate) fn apply_change(&mut self, change: AnalysisChange) {
177 let _p = profile("RootDatabase::apply_change");
178 self.request_cancellation();
179 log::info!("apply_change {:?}", change);
180 if !change.new_roots.is_empty() {
181 let mut local_roots = Vec::clone(&self.local_roots());
182 for (root_id, is_local) in change.new_roots {
183 let root =
184 if is_local { SourceRoot::new_local() } else { SourceRoot::new_library() };
185 let durability = durability(&root);
186 self.set_source_root_with_durability(root_id, Arc::new(root), durability);
187 if is_local {
188 local_roots.push(root_id);
189 }
190 }
191 self.set_local_roots_with_durability(Arc::new(local_roots), Durability::HIGH);
192 }
193
194 for (root_id, root_change) in change.roots_changed {
195 self.apply_root_change(root_id, root_change);
196 }
197 for (file_id, text) in change.files_changed {
198 let source_root_id = self.file_source_root(file_id);
199 let source_root = self.source_root(source_root_id);
200 let durability = durability(&source_root);
201 self.set_file_text_with_durability(file_id, text, durability)
202 }
203 if !change.libraries_added.is_empty() {
204 let mut libraries = Vec::clone(&self.library_roots());
205 for library in change.libraries_added {
206 libraries.push(library.root_id);
207 self.set_source_root_with_durability(
208 library.root_id,
209 Arc::new(SourceRoot::new_library()),
210 Durability::HIGH,
211 );
212 self.set_library_symbols_with_durability(
213 library.root_id,
214 Arc::new(library.symbol_index),
215 Durability::HIGH,
216 );
217 self.apply_root_change(library.root_id, library.root_change);
218 }
219 self.set_library_roots_with_durability(Arc::new(libraries), Durability::HIGH);
220 }
221 if let Some(crate_graph) = change.crate_graph {
222 self.set_crate_graph_with_durability(Arc::new(crate_graph), Durability::HIGH)
223 }
224
225 Arc::make_mut(&mut self.debug_data).merge(change.debug_data)
226 }
227
228 fn apply_root_change(&mut self, root_id: SourceRootId, root_change: RootChange) {
229 let mut source_root = SourceRoot::clone(&self.source_root(root_id));
230 let durability = durability(&source_root);
231 for add_file in root_change.added {
232 self.set_file_text_with_durability(add_file.file_id, add_file.text, durability);
233 self.set_file_relative_path_with_durability(
234 add_file.file_id,
235 add_file.path.clone(),
236 durability,
237 );
238 self.set_file_source_root_with_durability(add_file.file_id, root_id, durability);
239 source_root.insert_file(add_file.path, add_file.file_id);
240 }
241 for remove_file in root_change.removed {
242 self.set_file_text_with_durability(remove_file.file_id, Default::default(), durability);
243 source_root.remove_file(&remove_file.path);
244 }
245 self.set_source_root_with_durability(root_id, Arc::new(source_root), durability);
246 }
247
248 pub(crate) fn maybe_collect_garbage(&mut self) {
249 if cfg!(feature = "wasm") {
250 return;
251 }
252
253 if self.last_gc_check.elapsed() > GC_COOLDOWN {
254 self.last_gc_check = crate::wasm_shims::Instant::now();
255 }
256 }
257
258 pub(crate) fn collect_garbage(&mut self) {
259 if cfg!(feature = "wasm") {
260 return;
261 }
262
263 let _p = profile("RootDatabase::collect_garbage");
264 self.last_gc = crate::wasm_shims::Instant::now();
265
266 let sweep = SweepStrategy::default().discard_values().sweep_all_revisions();
267
268 self.query(ra_db::ParseQuery).sweep(sweep);
269 self.query(hir::db::ParseMacroQuery).sweep(sweep);
270
271 // Macros do take significant space, but less then the syntax trees
272 // self.query(hir::db::MacroDefQuery).sweep(sweep);
273 // self.query(hir::db::MacroArgQuery).sweep(sweep);
274 // self.query(hir::db::MacroExpandQuery).sweep(sweep);
275
276 self.query(hir::db::AstIdMapQuery).sweep(sweep);
277
278 self.query(hir::db::BodyWithSourceMapQuery).sweep(sweep);
279
280 self.query(hir::db::ExprScopesQuery).sweep(sweep);
281 self.query(hir::db::DoInferQuery).sweep(sweep);
282 self.query(hir::db::BodyQuery).sweep(sweep);
283 }
284
285 pub(crate) fn per_query_memory_usage(&mut self) -> Vec<(String, Bytes)> {
286 let mut acc: Vec<(String, Bytes)> = vec![];
287 let sweep = SweepStrategy::default().discard_values().sweep_all_revisions();
288 macro_rules! sweep_each_query {
289 ($($q:path)*) => {$(
290 let before = memory_usage().allocated;
291 self.query($q).sweep(sweep);
292 let after = memory_usage().allocated;
293 let q: $q = Default::default();
294 let name = format!("{:?}", q);
295 acc.push((name, before - after));
296
297 let before = memory_usage().allocated;
298 self.query($q).sweep(sweep.discard_everything());
299 let after = memory_usage().allocated;
300 let q: $q = Default::default();
301 let name = format!("{:?} (deps)", q);
302 acc.push((name, before - after));
303 )*}
304 }
305 sweep_each_query![
306 // SourceDatabase
307 ra_db::ParseQuery
308 ra_db::SourceRootCratesQuery
309
310 // AstDatabase
311 hir::db::AstIdMapQuery
312 hir::db::InternMacroQuery
313 hir::db::MacroArgQuery
314 hir::db::MacroDefQuery
315 hir::db::ParseMacroQuery
316 hir::db::MacroExpandQuery
317
318 // DefDatabase
319 hir::db::RawItemsQuery
320 hir::db::ComputeCrateDefMapQuery
321 hir::db::StructDataQuery
322 hir::db::UnionDataQuery
323 hir::db::EnumDataQuery
324 hir::db::ImplDataQuery
325 hir::db::TraitDataQuery
326 hir::db::TypeAliasDataQuery
327 hir::db::FunctionDataQuery
328 hir::db::ConstDataQuery
329 hir::db::StaticDataQuery
330 hir::db::BodyWithSourceMapQuery
331 hir::db::BodyQuery
332 hir::db::ExprScopesQuery
333 hir::db::GenericParamsQuery
334 hir::db::AttrsQuery
335 hir::db::ModuleLangItemsQuery
336 hir::db::CrateLangItemsQuery
337 hir::db::LangItemQuery
338 hir::db::DocumentationQuery
339
340 // InternDatabase
341 hir::db::InternFunctionQuery
342 hir::db::InternStructQuery
343 hir::db::InternUnionQuery
344 hir::db::InternEnumQuery
345 hir::db::InternConstQuery
346 hir::db::InternStaticQuery
347 hir::db::InternTraitQuery
348 hir::db::InternTypeAliasQuery
349 hir::db::InternImplQuery
350
351 // HirDatabase
352 hir::db::DoInferQuery
353 hir::db::TyQuery
354 hir::db::ValueTyQuery
355 hir::db::ImplSelfTyQuery
356 hir::db::ImplTraitQuery
357 hir::db::FieldTypesQuery
358 hir::db::CallableItemSignatureQuery
359 hir::db::GenericPredicatesForParamQuery
360 hir::db::GenericPredicatesQuery
361 hir::db::GenericDefaultsQuery
362 hir::db::ImplsInCrateQuery
363 hir::db::ImplsForTraitQuery
364 hir::db::TraitSolverQuery
365 hir::db::InternTypeCtorQuery
366 hir::db::InternChalkImplQuery
367 hir::db::InternAssocTyValueQuery
368 hir::db::AssociatedTyDataQuery
369 hir::db::AssociatedTyValueQuery
370 hir::db::TraitSolveQuery
371 hir::db::TraitDatumQuery
372 hir::db::StructDatumQuery
373 hir::db::ImplDatumQuery
374 ];
375 acc.sort_by_key(|it| std::cmp::Reverse(it.1));
376 acc
377 }
378}
379
380fn durability(source_root: &SourceRoot) -> Durability {
381 if source_root.is_library {
382 Durability::HIGH
383 } else {
384 Durability::LOW
385 }
386}
diff --git a/crates/ra_ide/src/ide_db/feature_flags.rs b/crates/ra_ide/src/ide_db/feature_flags.rs
deleted file mode 100644
index 85617640d..000000000
--- a/crates/ra_ide/src/ide_db/feature_flags.rs
+++ /dev/null
@@ -1,71 +0,0 @@
1//! FIXME: write short doc here
2
3use rustc_hash::FxHashMap;
4
5/// Feature flags hold fine-grained toggles for all *user-visible* features of
6/// rust-analyzer.
7///
8/// The exists such that users are able to disable any annoying feature (and,
9/// with many users and many features, some features are bound to be annoying
10/// for some users)
11///
12/// Note that we purposefully use run-time checked strings, and not something
13/// checked at compile time, to keep things simple and flexible.
14///
15/// Also note that, at the moment, `FeatureFlags` also store features for
16/// `ra_lsp_server`. This should be benign layering violation.
17#[derive(Debug)]
18pub struct FeatureFlags {
19 flags: FxHashMap<String, bool>,
20}
21
22impl FeatureFlags {
23 fn new(flags: &[(&str, bool)]) -> FeatureFlags {
24 let flags = flags
25 .iter()
26 .map(|&(name, value)| {
27 check_flag_name(name);
28 (name.to_string(), value)
29 })
30 .collect();
31 FeatureFlags { flags }
32 }
33
34 pub fn set(&mut self, flag: &str, value: bool) -> Result<(), ()> {
35 match self.flags.get_mut(flag) {
36 None => Err(()),
37 Some(slot) => {
38 *slot = value;
39 Ok(())
40 }
41 }
42 }
43
44 pub fn get(&self, flag: &str) -> bool {
45 match self.flags.get(flag) {
46 None => panic!("unknown flag: {:?}", flag),
47 Some(value) => *value,
48 }
49 }
50}
51
52impl Default for FeatureFlags {
53 fn default() -> FeatureFlags {
54 FeatureFlags::new(&[
55 ("lsp.diagnostics", true),
56 ("completion.insertion.add-call-parenthesis", true),
57 ("completion.enable-postfix", true),
58 ("notifications.workspace-loaded", true),
59 ("notifications.cargo-toml-not-found", true),
60 ])
61 }
62}
63
64fn check_flag_name(flag: &str) {
65 for c in flag.bytes() {
66 match c {
67 b'a'..=b'z' | b'-' | b'.' => (),
68 _ => panic!("flag name does not match conventions: {:?}", flag),
69 }
70 }
71}
diff --git a/crates/ra_ide/src/ide_db/line_index.rs b/crates/ra_ide/src/ide_db/line_index.rs
deleted file mode 100644
index 6f99ca3a7..000000000
--- a/crates/ra_ide/src/ide_db/line_index.rs
+++ /dev/null
@@ -1,283 +0,0 @@
1//! FIXME: write short doc here
2
3use ra_syntax::TextUnit;
4use rustc_hash::FxHashMap;
5use superslice::Ext;
6
7#[derive(Clone, Debug, PartialEq, Eq)]
8pub struct LineIndex {
9 pub(crate) newlines: Vec<TextUnit>,
10 pub(crate) utf16_lines: FxHashMap<u32, Vec<Utf16Char>>,
11}
12
13#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
14pub struct LineCol {
15 /// Zero-based
16 pub line: u32,
17 /// Zero-based
18 pub col_utf16: u32,
19}
20
21#[derive(Clone, Debug, Hash, PartialEq, Eq)]
22pub(crate) struct Utf16Char {
23 pub(crate) start: TextUnit,
24 pub(crate) end: TextUnit,
25}
26
27impl Utf16Char {
28 fn len(&self) -> TextUnit {
29 self.end - self.start
30 }
31}
32
33impl LineIndex {
34 pub fn new(text: &str) -> LineIndex {
35 let mut utf16_lines = FxHashMap::default();
36 let mut utf16_chars = Vec::new();
37
38 let mut newlines = vec![0.into()];
39 let mut curr_row = 0.into();
40 let mut curr_col = 0.into();
41 let mut line = 0;
42 for c in text.chars() {
43 curr_row += TextUnit::of_char(c);
44 if c == '\n' {
45 newlines.push(curr_row);
46
47 // Save any utf-16 characters seen in the previous line
48 if !utf16_chars.is_empty() {
49 utf16_lines.insert(line, utf16_chars);
50 utf16_chars = Vec::new();
51 }
52
53 // Prepare for processing the next line
54 curr_col = 0.into();
55 line += 1;
56 continue;
57 }
58
59 let char_len = TextUnit::of_char(c);
60 if char_len.to_usize() > 1 {
61 utf16_chars.push(Utf16Char { start: curr_col, end: curr_col + char_len });
62 }
63
64 curr_col += char_len;
65 }
66
67 // Save any utf-16 characters seen in the last line
68 if !utf16_chars.is_empty() {
69 utf16_lines.insert(line, utf16_chars);
70 }
71
72 LineIndex { newlines, utf16_lines }
73 }
74
75 pub fn line_col(&self, offset: TextUnit) -> LineCol {
76 let line = self.newlines.upper_bound(&offset) - 1;
77 let line_start_offset = self.newlines[line];
78 let col = offset - line_start_offset;
79
80 LineCol { line: line as u32, col_utf16: self.utf8_to_utf16_col(line as u32, col) as u32 }
81 }
82
83 pub fn offset(&self, line_col: LineCol) -> TextUnit {
84 //FIXME: return Result
85 let col = self.utf16_to_utf8_col(line_col.line, line_col.col_utf16);
86 self.newlines[line_col.line as usize] + col
87 }
88
89 fn utf8_to_utf16_col(&self, line: u32, mut col: TextUnit) -> usize {
90 if let Some(utf16_chars) = self.utf16_lines.get(&line) {
91 let mut correction = TextUnit::from_usize(0);
92 for c in utf16_chars {
93 if col >= c.end {
94 correction += c.len() - TextUnit::from_usize(1);
95 } else {
96 // From here on, all utf16 characters come *after* the character we are mapping,
97 // so we don't need to take them into account
98 break;
99 }
100 }
101
102 col -= correction;
103 }
104
105 col.to_usize()
106 }
107
108 fn utf16_to_utf8_col(&self, line: u32, col: u32) -> TextUnit {
109 let mut col: TextUnit = col.into();
110 if let Some(utf16_chars) = self.utf16_lines.get(&line) {
111 for c in utf16_chars {
112 if col >= c.start {
113 col += c.len() - TextUnit::from_usize(1);
114 } else {
115 // From here on, all utf16 characters come *after* the character we are mapping,
116 // so we don't need to take them into account
117 break;
118 }
119 }
120 }
121
122 col
123 }
124}
125
126#[cfg(test)]
127/// Simple reference implementation to use in proptests
128pub fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
129 let mut res = LineCol { line: 0, col_utf16: 0 };
130 for (i, c) in text.char_indices() {
131 if i + c.len_utf8() > offset.to_usize() {
132 // if it's an invalid offset, inside a multibyte char
133 // return as if it was at the start of the char
134 break;
135 }
136 if c == '\n' {
137 res.line += 1;
138 res.col_utf16 = 0;
139 } else {
140 res.col_utf16 += 1;
141 }
142 }
143 res
144}
145
146#[cfg(test)]
147mod test_line_index {
148 use super::*;
149 use proptest::{prelude::*, proptest};
150 use ra_text_edit::test_utils::{arb_offset, arb_text};
151
152 #[test]
153 fn test_line_index() {
154 let text = "hello\nworld";
155 let index = LineIndex::new(text);
156 assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 });
157 assert_eq!(index.line_col(1.into()), LineCol { line: 0, col_utf16: 1 });
158 assert_eq!(index.line_col(5.into()), LineCol { line: 0, col_utf16: 5 });
159 assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 0 });
160 assert_eq!(index.line_col(7.into()), LineCol { line: 1, col_utf16: 1 });
161 assert_eq!(index.line_col(8.into()), LineCol { line: 1, col_utf16: 2 });
162 assert_eq!(index.line_col(10.into()), LineCol { line: 1, col_utf16: 4 });
163 assert_eq!(index.line_col(11.into()), LineCol { line: 1, col_utf16: 5 });
164 assert_eq!(index.line_col(12.into()), LineCol { line: 1, col_utf16: 6 });
165
166 let text = "\nhello\nworld";
167 let index = LineIndex::new(text);
168 assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 });
169 assert_eq!(index.line_col(1.into()), LineCol { line: 1, col_utf16: 0 });
170 assert_eq!(index.line_col(2.into()), LineCol { line: 1, col_utf16: 1 });
171 assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 5 });
172 assert_eq!(index.line_col(7.into()), LineCol { line: 2, col_utf16: 0 });
173 }
174
175 fn arb_text_with_offset() -> BoxedStrategy<(TextUnit, String)> {
176 arb_text().prop_flat_map(|text| (arb_offset(&text), Just(text))).boxed()
177 }
178
179 fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
180 let mut res = LineCol { line: 0, col_utf16: 0 };
181 for (i, c) in text.char_indices() {
182 if i + c.len_utf8() > offset.to_usize() {
183 // if it's an invalid offset, inside a multibyte char
184 // return as if it was at the start of the char
185 break;
186 }
187 if c == '\n' {
188 res.line += 1;
189 res.col_utf16 = 0;
190 } else {
191 res.col_utf16 += 1;
192 }
193 }
194 res
195 }
196
197 proptest! {
198 #[test]
199 fn test_line_index_proptest((offset, text) in arb_text_with_offset()) {
200 let expected = to_line_col(&text, offset);
201 let line_index = LineIndex::new(&text);
202 let actual = line_index.line_col(offset);
203
204 assert_eq!(actual, expected);
205 }
206 }
207}
208
209#[cfg(test)]
210mod test_utf8_utf16_conv {
211 use super::*;
212
213 #[test]
214 fn test_char_len() {
215 assert_eq!('メ'.len_utf8(), 3);
216 assert_eq!('メ'.len_utf16(), 1);
217 }
218
219 #[test]
220 fn test_empty_index() {
221 let col_index = LineIndex::new(
222 "
223const C: char = 'x';
224",
225 );
226 assert_eq!(col_index.utf16_lines.len(), 0);
227 }
228
229 #[test]
230 fn test_single_char() {
231 let col_index = LineIndex::new(
232 "
233const C: char = 'メ';
234",
235 );
236
237 assert_eq!(col_index.utf16_lines.len(), 1);
238 assert_eq!(col_index.utf16_lines[&1].len(), 1);
239 assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() });
240
241 // UTF-8 to UTF-16, no changes
242 assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15);
243
244 // UTF-8 to UTF-16
245 assert_eq!(col_index.utf8_to_utf16_col(1, 22.into()), 20);
246
247 // UTF-16 to UTF-8, no changes
248 assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from(15));
249
250 // UTF-16 to UTF-8
251 assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from(21));
252 }
253
254 #[test]
255 fn test_string() {
256 let col_index = LineIndex::new(
257 "
258const C: char = \"メ メ\";
259",
260 );
261
262 assert_eq!(col_index.utf16_lines.len(), 1);
263 assert_eq!(col_index.utf16_lines[&1].len(), 2);
264 assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() });
265 assert_eq!(col_index.utf16_lines[&1][1], Utf16Char { start: 21.into(), end: 24.into() });
266
267 // UTF-8 to UTF-16
268 assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15);
269
270 assert_eq!(col_index.utf8_to_utf16_col(1, 21.into()), 19);
271 assert_eq!(col_index.utf8_to_utf16_col(1, 25.into()), 21);
272
273 assert!(col_index.utf8_to_utf16_col(2, 15.into()) == 15);
274
275 // UTF-16 to UTF-8
276 assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from_usize(15));
277
278 assert_eq!(col_index.utf16_to_utf8_col(1, 18), TextUnit::from_usize(20));
279 assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from_usize(23));
280
281 assert_eq!(col_index.utf16_to_utf8_col(2, 15), TextUnit::from_usize(15));
282 }
283}
diff --git a/crates/ra_ide/src/ide_db/line_index_utils.rs b/crates/ra_ide/src/ide_db/line_index_utils.rs
deleted file mode 100644
index faa3d665f..000000000
--- a/crates/ra_ide/src/ide_db/line_index_utils.rs
+++ /dev/null
@@ -1,334 +0,0 @@
1//! FIXME: write short doc here
2
3use ra_syntax::{TextRange, TextUnit};
4use ra_text_edit::{AtomTextEdit, TextEdit};
5
6use crate::ide_db::line_index::{LineCol, LineIndex, Utf16Char};
7
8#[derive(Debug, Clone)]
9enum Step {
10 Newline(TextUnit),
11 Utf16Char(TextRange),
12}
13
14#[derive(Debug)]
15struct LineIndexStepIter<'a> {
16 line_index: &'a LineIndex,
17 next_newline_idx: usize,
18 utf16_chars: Option<(TextUnit, std::slice::Iter<'a, Utf16Char>)>,
19}
20
21impl<'a> LineIndexStepIter<'a> {
22 fn from(line_index: &LineIndex) -> LineIndexStepIter {
23 let mut x = LineIndexStepIter { line_index, next_newline_idx: 0, utf16_chars: None };
24 // skip first newline since it's not real
25 x.next();
26 x
27 }
28}
29
30impl<'a> Iterator for LineIndexStepIter<'a> {
31 type Item = Step;
32 fn next(&mut self) -> Option<Step> {
33 self.utf16_chars
34 .as_mut()
35 .and_then(|(newline, x)| {
36 let x = x.next()?;
37 Some(Step::Utf16Char(TextRange::from_to(*newline + x.start, *newline + x.end)))
38 })
39 .or_else(|| {
40 let next_newline = *self.line_index.newlines.get(self.next_newline_idx)?;
41 self.utf16_chars = self
42 .line_index
43 .utf16_lines
44 .get(&(self.next_newline_idx as u32))
45 .map(|x| (next_newline, x.iter()));
46 self.next_newline_idx += 1;
47 Some(Step::Newline(next_newline))
48 })
49 }
50}
51
52#[derive(Debug)]
53struct OffsetStepIter<'a> {
54 text: &'a str,
55 offset: TextUnit,
56}
57
58impl<'a> Iterator for OffsetStepIter<'a> {
59 type Item = Step;
60 fn next(&mut self) -> Option<Step> {
61 let (next, next_offset) = self
62 .text
63 .char_indices()
64 .filter_map(|(i, c)| {
65 if c == '\n' {
66 let next_offset = self.offset + TextUnit::from_usize(i + 1);
67 let next = Step::Newline(next_offset);
68 Some((next, next_offset))
69 } else {
70 let char_len = TextUnit::of_char(c);
71 if char_len.to_usize() > 1 {
72 let start = self.offset + TextUnit::from_usize(i);
73 let end = start + char_len;
74 let next = Step::Utf16Char(TextRange::from_to(start, end));
75 let next_offset = end;
76 Some((next, next_offset))
77 } else {
78 None
79 }
80 }
81 })
82 .next()?;
83 let next_idx = (next_offset - self.offset).to_usize();
84 self.text = &self.text[next_idx..];
85 self.offset = next_offset;
86 Some(next)
87 }
88}
89
90#[derive(Debug)]
91enum NextSteps<'a> {
92 Use,
93 ReplaceMany(OffsetStepIter<'a>),
94 AddMany(OffsetStepIter<'a>),
95}
96
97#[derive(Debug)]
98struct TranslatedEdit<'a> {
99 delete: TextRange,
100 insert: &'a str,
101 diff: i64,
102}
103
104struct Edits<'a> {
105 edits: &'a [AtomTextEdit],
106 current: Option<TranslatedEdit<'a>>,
107 acc_diff: i64,
108}
109
110impl<'a> Edits<'a> {
111 fn from_text_edit(text_edit: &'a TextEdit) -> Edits<'a> {
112 let mut x = Edits { edits: text_edit.as_atoms(), current: None, acc_diff: 0 };
113 x.advance_edit();
114 x
115 }
116 fn advance_edit(&mut self) {
117 self.acc_diff += self.current.as_ref().map_or(0, |x| x.diff);
118 match self.edits.split_first() {
119 Some((next, rest)) => {
120 let delete = self.translate_range(next.delete);
121 let diff = next.insert.len() as i64 - next.delete.len().to_usize() as i64;
122 self.current = Some(TranslatedEdit { delete, insert: &next.insert, diff });
123 self.edits = rest;
124 }
125 None => {
126 self.current = None;
127 }
128 }
129 }
130
131 fn next_inserted_steps(&mut self) -> Option<OffsetStepIter<'a>> {
132 let cur = self.current.as_ref()?;
133 let res = Some(OffsetStepIter { offset: cur.delete.start(), text: &cur.insert });
134 self.advance_edit();
135 res
136 }
137
138 fn next_steps(&mut self, step: &Step) -> NextSteps {
139 let step_pos = match *step {
140 Step::Newline(n) => n,
141 Step::Utf16Char(r) => r.end(),
142 };
143 match &mut self.current {
144 Some(edit) => {
145 if step_pos <= edit.delete.start() {
146 NextSteps::Use
147 } else if step_pos <= edit.delete.end() {
148 let iter = OffsetStepIter { offset: edit.delete.start(), text: &edit.insert };
149 // empty slice to avoid returning steps again
150 edit.insert = &edit.insert[edit.insert.len()..];
151 NextSteps::ReplaceMany(iter)
152 } else {
153 let iter = OffsetStepIter { offset: edit.delete.start(), text: &edit.insert };
154 // empty slice to avoid returning steps again
155 edit.insert = &edit.insert[edit.insert.len()..];
156 self.advance_edit();
157 NextSteps::AddMany(iter)
158 }
159 }
160 None => NextSteps::Use,
161 }
162 }
163
164 fn translate_range(&self, range: TextRange) -> TextRange {
165 if self.acc_diff == 0 {
166 range
167 } else {
168 let start = self.translate(range.start());
169 let end = self.translate(range.end());
170 TextRange::from_to(start, end)
171 }
172 }
173
174 fn translate(&self, x: TextUnit) -> TextUnit {
175 if self.acc_diff == 0 {
176 x
177 } else {
178 TextUnit::from((x.to_usize() as i64 + self.acc_diff) as u32)
179 }
180 }
181
182 fn translate_step(&self, x: &Step) -> Step {
183 if self.acc_diff == 0 {
184 x.clone()
185 } else {
186 match *x {
187 Step::Newline(n) => Step::Newline(self.translate(n)),
188 Step::Utf16Char(r) => Step::Utf16Char(self.translate_range(r)),
189 }
190 }
191 }
192}
193
194#[derive(Debug)]
195struct RunningLineCol {
196 line: u32,
197 last_newline: TextUnit,
198 col_adjust: TextUnit,
199}
200
201impl RunningLineCol {
202 fn new() -> RunningLineCol {
203 RunningLineCol { line: 0, last_newline: TextUnit::from(0), col_adjust: TextUnit::from(0) }
204 }
205
206 fn to_line_col(&self, offset: TextUnit) -> LineCol {
207 LineCol {
208 line: self.line,
209 col_utf16: ((offset - self.last_newline) - self.col_adjust).into(),
210 }
211 }
212
213 fn add_line(&mut self, newline: TextUnit) {
214 self.line += 1;
215 self.last_newline = newline;
216 self.col_adjust = TextUnit::from(0);
217 }
218
219 fn adjust_col(&mut self, range: TextRange) {
220 self.col_adjust += range.len() - TextUnit::from(1);
221 }
222}
223
224pub fn translate_offset_with_edit(
225 line_index: &LineIndex,
226 offset: TextUnit,
227 text_edit: &TextEdit,
228) -> LineCol {
229 let mut state = Edits::from_text_edit(&text_edit);
230
231 let mut res = RunningLineCol::new();
232
233 macro_rules! test_step {
234 ($x:ident) => {
235 match &$x {
236 Step::Newline(n) => {
237 if offset < *n {
238 return res.to_line_col(offset);
239 } else {
240 res.add_line(*n);
241 }
242 }
243 Step::Utf16Char(x) => {
244 if offset < x.end() {
245 // if the offset is inside a multibyte char it's invalid
246 // clamp it to the start of the char
247 let clamp = offset.min(x.start());
248 return res.to_line_col(clamp);
249 } else {
250 res.adjust_col(*x);
251 }
252 }
253 }
254 };
255 }
256
257 for orig_step in LineIndexStepIter::from(line_index) {
258 loop {
259 let translated_step = state.translate_step(&orig_step);
260 match state.next_steps(&translated_step) {
261 NextSteps::Use => {
262 test_step!(translated_step);
263 break;
264 }
265 NextSteps::ReplaceMany(ns) => {
266 for n in ns {
267 test_step!(n);
268 }
269 break;
270 }
271 NextSteps::AddMany(ns) => {
272 for n in ns {
273 test_step!(n);
274 }
275 }
276 }
277 }
278 }
279
280 loop {
281 match state.next_inserted_steps() {
282 None => break,
283 Some(ns) => {
284 for n in ns {
285 test_step!(n);
286 }
287 }
288 }
289 }
290
291 res.to_line_col(offset)
292}
293
294#[cfg(test)]
295mod test {
296 use proptest::{prelude::*, proptest};
297 use ra_text_edit::test_utils::{arb_offset, arb_text_with_edit};
298 use ra_text_edit::TextEdit;
299
300 use crate::ide_db::line_index;
301
302 use super::*;
303
304 #[derive(Debug)]
305 struct ArbTextWithEditAndOffset {
306 text: String,
307 edit: TextEdit,
308 edited_text: String,
309 offset: TextUnit,
310 }
311
312 fn arb_text_with_edit_and_offset() -> BoxedStrategy<ArbTextWithEditAndOffset> {
313 arb_text_with_edit()
314 .prop_flat_map(|x| {
315 let edited_text = x.edit.apply(&x.text);
316 let arb_offset = arb_offset(&edited_text);
317 (Just(x), Just(edited_text), arb_offset).prop_map(|(x, edited_text, offset)| {
318 ArbTextWithEditAndOffset { text: x.text, edit: x.edit, edited_text, offset }
319 })
320 })
321 .boxed()
322 }
323
324 proptest! {
325 #[test]
326 fn test_translate_offset_with_edit(x in arb_text_with_edit_and_offset()) {
327 let expected = line_index::to_line_col(&x.edited_text, x.offset);
328 let line_index = LineIndex::new(&x.text);
329 let actual = translate_offset_with_edit(&line_index, x.offset, &x.edit);
330
331 assert_eq!(actual, expected);
332 }
333 }
334}
diff --git a/crates/ra_ide/src/ide_db/mod.rs b/crates/ra_ide/src/ide_db/mod.rs
deleted file mode 100644
index 0df4d510f..000000000
--- a/crates/ra_ide/src/ide_db/mod.rs
+++ /dev/null
@@ -1,137 +0,0 @@
1//! FIXME: write short doc here
2
3pub mod line_index;
4pub mod line_index_utils;
5pub mod feature_flags;
6pub mod symbol_index;
7pub mod change;
8
9use std::sync::Arc;
10
11use ra_db::{
12 salsa::{self, Database, Durability},
13 Canceled, CheckCanceled, CrateId, FileId, FileLoader, FileLoaderDelegate, RelativePath,
14 SourceDatabase, SourceRootId,
15};
16use rustc_hash::FxHashMap;
17
18use crate::ide_db::{
19 feature_flags::FeatureFlags, line_index::LineIndex, symbol_index::SymbolsDatabase,
20};
21
22#[salsa::database(
23 ra_db::SourceDatabaseStorage,
24 ra_db::SourceDatabaseExtStorage,
25 LineIndexDatabaseStorage,
26 symbol_index::SymbolsDatabaseStorage,
27 hir::db::InternDatabaseStorage,
28 hir::db::AstDatabaseStorage,
29 hir::db::DefDatabaseStorage,
30 hir::db::HirDatabaseStorage
31)]
32#[derive(Debug)]
33pub(crate) struct RootDatabase {
34 runtime: salsa::Runtime<RootDatabase>,
35 pub(crate) feature_flags: Arc<FeatureFlags>,
36 pub(crate) debug_data: Arc<DebugData>,
37 pub(crate) last_gc: crate::wasm_shims::Instant,
38 pub(crate) last_gc_check: crate::wasm_shims::Instant,
39}
40
41impl FileLoader for RootDatabase {
42 fn file_text(&self, file_id: FileId) -> Arc<String> {
43 FileLoaderDelegate(self).file_text(file_id)
44 }
45 fn resolve_relative_path(
46 &self,
47 anchor: FileId,
48 relative_path: &RelativePath,
49 ) -> Option<FileId> {
50 FileLoaderDelegate(self).resolve_relative_path(anchor, relative_path)
51 }
52 fn relevant_crates(&self, file_id: FileId) -> Arc<Vec<CrateId>> {
53 FileLoaderDelegate(self).relevant_crates(file_id)
54 }
55}
56
57impl salsa::Database for RootDatabase {
58 fn salsa_runtime(&self) -> &salsa::Runtime<RootDatabase> {
59 &self.runtime
60 }
61 fn salsa_runtime_mut(&mut self) -> &mut salsa::Runtime<Self> {
62 &mut self.runtime
63 }
64 fn on_propagated_panic(&self) -> ! {
65 Canceled::throw()
66 }
67 fn salsa_event(&self, event: impl Fn() -> salsa::Event<RootDatabase>) {
68 match event().kind {
69 salsa::EventKind::DidValidateMemoizedValue { .. }
70 | salsa::EventKind::WillExecute { .. } => {
71 self.check_canceled();
72 }
73 _ => (),
74 }
75 }
76}
77
78impl Default for RootDatabase {
79 fn default() -> RootDatabase {
80 RootDatabase::new(None, FeatureFlags::default())
81 }
82}
83
84impl RootDatabase {
85 pub fn new(lru_capacity: Option<usize>, feature_flags: FeatureFlags) -> RootDatabase {
86 let mut db = RootDatabase {
87 runtime: salsa::Runtime::default(),
88 last_gc: crate::wasm_shims::Instant::now(),
89 last_gc_check: crate::wasm_shims::Instant::now(),
90 feature_flags: Arc::new(feature_flags),
91 debug_data: Default::default(),
92 };
93 db.set_crate_graph_with_durability(Default::default(), Durability::HIGH);
94 db.set_local_roots_with_durability(Default::default(), Durability::HIGH);
95 db.set_library_roots_with_durability(Default::default(), Durability::HIGH);
96 let lru_capacity = lru_capacity.unwrap_or(ra_db::DEFAULT_LRU_CAP);
97 db.query_mut(ra_db::ParseQuery).set_lru_capacity(lru_capacity);
98 db.query_mut(hir::db::ParseMacroQuery).set_lru_capacity(lru_capacity);
99 db.query_mut(hir::db::MacroExpandQuery).set_lru_capacity(lru_capacity);
100 db
101 }
102}
103
104impl salsa::ParallelDatabase for RootDatabase {
105 fn snapshot(&self) -> salsa::Snapshot<RootDatabase> {
106 salsa::Snapshot::new(RootDatabase {
107 runtime: self.runtime.snapshot(self),
108 last_gc: self.last_gc,
109 last_gc_check: self.last_gc_check,
110 feature_flags: Arc::clone(&self.feature_flags),
111 debug_data: Arc::clone(&self.debug_data),
112 })
113 }
114}
115
116#[salsa::query_group(LineIndexDatabaseStorage)]
117pub(crate) trait LineIndexDatabase: ra_db::SourceDatabase + CheckCanceled {
118 fn line_index(&self, file_id: FileId) -> Arc<LineIndex>;
119}
120
121fn line_index(db: &impl LineIndexDatabase, file_id: FileId) -> Arc<LineIndex> {
122 let text = db.file_text(file_id);
123 Arc::new(LineIndex::new(&*text))
124}
125
126#[derive(Debug, Default, Clone)]
127pub(crate) struct DebugData {
128 pub(crate) root_paths: FxHashMap<SourceRootId, String>,
129 pub(crate) crate_names: FxHashMap<CrateId, String>,
130}
131
132impl DebugData {
133 pub(crate) fn merge(&mut self, other: DebugData) {
134 self.root_paths.extend(other.root_paths.into_iter());
135 self.crate_names.extend(other.crate_names.into_iter());
136 }
137}
diff --git a/crates/ra_ide/src/ide_db/symbol_index.rs b/crates/ra_ide/src/ide_db/symbol_index.rs
deleted file mode 100644
index c66eeb8e2..000000000
--- a/crates/ra_ide/src/ide_db/symbol_index.rs
+++ /dev/null
@@ -1,445 +0,0 @@
1//! This module handles fuzzy-searching of functions, structs and other symbols
2//! by name across the whole workspace and dependencies.
3//!
4//! It works by building an incrementally-updated text-search index of all
5//! symbols. The backbone of the index is the **awesome** `fst` crate by
6//! @BurntSushi.
7//!
8//! In a nutshell, you give a set of strings to `fst`, and it builds a
9//! finite state machine describing this set of strings. The strings which
10//! could fuzzy-match a pattern can also be described by a finite state machine.
11//! What is freaking cool is that you can now traverse both state machines in
12//! lock-step to enumerate the strings which are both in the input set and
13//! fuzz-match the query. Or, more formally, given two languages described by
14//! FSTs, one can build a product FST which describes the intersection of the
15//! languages.
16//!
17//! `fst` does not support cheap updating of the index, but it supports unioning
18//! of state machines. So, to account for changing source code, we build an FST
19//! for each library (which is assumed to never change) and an FST for each Rust
20//! file in the current workspace, and run a query against the union of all
21//! those FSTs.
22use std::{
23 fmt,
24 hash::{Hash, Hasher},
25 mem,
26 sync::Arc,
27};
28
29use fst::{self, Streamer};
30use ra_db::{
31 salsa::{self, ParallelDatabase},
32 FileId, SourceDatabaseExt, SourceRootId,
33};
34use ra_syntax::{
35 ast::{self, NameOwner},
36 match_ast, AstNode, Parse, SmolStr, SourceFile,
37 SyntaxKind::{self, *},
38 SyntaxNode, SyntaxNodePtr, TextRange, WalkEvent,
39};
40#[cfg(not(feature = "wasm"))]
41use rayon::prelude::*;
42
43use crate::ide_db::RootDatabase;
44
45#[derive(Debug)]
46pub struct Query {
47 query: String,
48 lowercased: String,
49 only_types: bool,
50 libs: bool,
51 exact: bool,
52 limit: usize,
53}
54
55impl Query {
56 pub fn new(query: String) -> Query {
57 let lowercased = query.to_lowercase();
58 Query {
59 query,
60 lowercased,
61 only_types: false,
62 libs: false,
63 exact: false,
64 limit: usize::max_value(),
65 }
66 }
67
68 pub fn only_types(&mut self) {
69 self.only_types = true;
70 }
71
72 pub fn libs(&mut self) {
73 self.libs = true;
74 }
75
76 pub fn exact(&mut self) {
77 self.exact = true;
78 }
79
80 pub fn limit(&mut self, limit: usize) {
81 self.limit = limit
82 }
83}
84
85#[salsa::query_group(SymbolsDatabaseStorage)]
86pub(crate) trait SymbolsDatabase: hir::db::HirDatabase {
87 fn file_symbols(&self, file_id: FileId) -> Arc<SymbolIndex>;
88 #[salsa::input]
89 fn library_symbols(&self, id: SourceRootId) -> Arc<SymbolIndex>;
90 /// The set of "local" (that is, from the current workspace) roots.
91 /// Files in local roots are assumed to change frequently.
92 #[salsa::input]
93 fn local_roots(&self) -> Arc<Vec<SourceRootId>>;
94 /// The set of roots for crates.io libraries.
95 /// Files in libraries are assumed to never change.
96 #[salsa::input]
97 fn library_roots(&self) -> Arc<Vec<SourceRootId>>;
98}
99
100fn file_symbols(db: &impl SymbolsDatabase, file_id: FileId) -> Arc<SymbolIndex> {
101 db.check_canceled();
102 let parse = db.parse(file_id);
103
104 let symbols = source_file_to_file_symbols(&parse.tree(), file_id);
105
106 // FIXME: add macros here
107
108 Arc::new(SymbolIndex::new(symbols))
109}
110
111pub(crate) fn world_symbols(db: &RootDatabase, query: Query) -> Vec<FileSymbol> {
112 /// Need to wrap Snapshot to provide `Clone` impl for `map_with`
113 struct Snap(salsa::Snapshot<RootDatabase>);
114 impl Clone for Snap {
115 fn clone(&self) -> Snap {
116 Snap(self.0.snapshot())
117 }
118 }
119
120 let buf: Vec<Arc<SymbolIndex>> = if query.libs {
121 let snap = Snap(db.snapshot());
122 #[cfg(not(feature = "wasm"))]
123 let buf = db
124 .library_roots()
125 .par_iter()
126 .map_with(snap, |db, &lib_id| db.0.library_symbols(lib_id))
127 .collect();
128
129 #[cfg(feature = "wasm")]
130 let buf = db.library_roots().iter().map(|&lib_id| snap.0.library_symbols(lib_id)).collect();
131
132 buf
133 } else {
134 let mut files = Vec::new();
135 for &root in db.local_roots().iter() {
136 let sr = db.source_root(root);
137 files.extend(sr.walk())
138 }
139
140 let snap = Snap(db.snapshot());
141 #[cfg(not(feature = "wasm"))]
142 let buf =
143 files.par_iter().map_with(snap, |db, &file_id| db.0.file_symbols(file_id)).collect();
144
145 #[cfg(feature = "wasm")]
146 let buf = files.iter().map(|&file_id| snap.0.file_symbols(file_id)).collect();
147
148 buf
149 };
150 query.search(&buf)
151}
152
153pub(crate) fn index_resolve(db: &RootDatabase, name_ref: &ast::NameRef) -> Vec<FileSymbol> {
154 let name = name_ref.text();
155 let mut query = Query::new(name.to_string());
156 query.exact();
157 query.limit(4);
158 world_symbols(db, query)
159}
160
161#[derive(Default)]
162pub(crate) struct SymbolIndex {
163 symbols: Vec<FileSymbol>,
164 map: fst::Map,
165}
166
167impl fmt::Debug for SymbolIndex {
168 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
169 f.debug_struct("SymbolIndex").field("n_symbols", &self.symbols.len()).finish()
170 }
171}
172
173impl PartialEq for SymbolIndex {
174 fn eq(&self, other: &SymbolIndex) -> bool {
175 self.symbols == other.symbols
176 }
177}
178
179impl Eq for SymbolIndex {}
180
181impl Hash for SymbolIndex {
182 fn hash<H: Hasher>(&self, hasher: &mut H) {
183 self.symbols.hash(hasher)
184 }
185}
186
187impl SymbolIndex {
188 fn new(mut symbols: Vec<FileSymbol>) -> SymbolIndex {
189 fn cmp_key<'a>(s1: &'a FileSymbol) -> impl Ord + 'a {
190 unicase::Ascii::new(s1.name.as_str())
191 }
192 #[cfg(not(feature = "wasm"))]
193 symbols.par_sort_by(|s1, s2| cmp_key(s1).cmp(&cmp_key(s2)));
194
195 #[cfg(feature = "wasm")]
196 symbols.sort_by(|s1, s2| cmp_key(s1).cmp(&cmp_key(s2)));
197
198 let mut builder = fst::MapBuilder::memory();
199
200 let mut last_batch_start = 0;
201
202 for idx in 0..symbols.len() {
203 if symbols.get(last_batch_start).map(cmp_key) == symbols.get(idx + 1).map(cmp_key) {
204 continue;
205 }
206
207 let start = last_batch_start;
208 let end = idx + 1;
209 last_batch_start = end;
210
211 let key = symbols[start].name.as_str().to_lowercase();
212 let value = SymbolIndex::range_to_map_value(start, end);
213
214 builder.insert(key, value).unwrap();
215 }
216
217 let map = fst::Map::from_bytes(builder.into_inner().unwrap()).unwrap();
218 SymbolIndex { symbols, map }
219 }
220
221 pub(crate) fn len(&self) -> usize {
222 self.symbols.len()
223 }
224
225 pub(crate) fn memory_size(&self) -> usize {
226 self.map.as_fst().size() + self.symbols.len() * mem::size_of::<FileSymbol>()
227 }
228
229 #[cfg(not(feature = "wasm"))]
230 pub(crate) fn for_files(
231 files: impl ParallelIterator<Item = (FileId, Parse<ast::SourceFile>)>,
232 ) -> SymbolIndex {
233 let symbols = files
234 .flat_map(|(file_id, file)| source_file_to_file_symbols(&file.tree(), file_id))
235 .collect::<Vec<_>>();
236 SymbolIndex::new(symbols)
237 }
238
239 #[cfg(feature = "wasm")]
240 pub(crate) fn for_files(
241 files: impl Iterator<Item = (FileId, Parse<ast::SourceFile>)>,
242 ) -> SymbolIndex {
243 let symbols = files
244 .flat_map(|(file_id, file)| source_file_to_file_symbols(&file.tree(), file_id))
245 .collect::<Vec<_>>();
246 SymbolIndex::new(symbols)
247 }
248
249 fn range_to_map_value(start: usize, end: usize) -> u64 {
250 debug_assert![start <= (std::u32::MAX as usize)];
251 debug_assert![end <= (std::u32::MAX as usize)];
252
253 ((start as u64) << 32) | end as u64
254 }
255
256 fn map_value_to_range(value: u64) -> (usize, usize) {
257 let end = value as u32 as usize;
258 let start = (value >> 32) as usize;
259 (start, end)
260 }
261}
262
263impl Query {
264 pub(crate) fn search(self, indices: &[Arc<SymbolIndex>]) -> Vec<FileSymbol> {
265 let mut op = fst::map::OpBuilder::new();
266 for file_symbols in indices.iter() {
267 let automaton = fst::automaton::Subsequence::new(&self.lowercased);
268 op = op.add(file_symbols.map.search(automaton))
269 }
270 let mut stream = op.union();
271 let mut res = Vec::new();
272 while let Some((_, indexed_values)) = stream.next() {
273 if res.len() >= self.limit {
274 break;
275 }
276 for indexed_value in indexed_values {
277 let symbol_index = &indices[indexed_value.index];
278 let (start, end) = SymbolIndex::map_value_to_range(indexed_value.value);
279
280 for symbol in &symbol_index.symbols[start..end] {
281 if self.only_types && !is_type(symbol.ptr.kind()) {
282 continue;
283 }
284 if self.exact && symbol.name != self.query {
285 continue;
286 }
287 res.push(symbol.clone());
288 }
289 }
290 }
291 res
292 }
293}
294
295fn is_type(kind: SyntaxKind) -> bool {
296 match kind {
297 STRUCT_DEF | ENUM_DEF | TRAIT_DEF | TYPE_ALIAS_DEF => true,
298 _ => false,
299 }
300}
301
302/// The actual data that is stored in the index. It should be as compact as
303/// possible.
304#[derive(Debug, Clone, PartialEq, Eq, Hash)]
305pub(crate) struct FileSymbol {
306 pub(crate) file_id: FileId,
307 pub(crate) name: SmolStr,
308 pub(crate) ptr: SyntaxNodePtr,
309 pub(crate) name_range: Option<TextRange>,
310 pub(crate) container_name: Option<SmolStr>,
311}
312
313fn source_file_to_file_symbols(source_file: &SourceFile, file_id: FileId) -> Vec<FileSymbol> {
314 let mut symbols = Vec::new();
315 let mut stack = Vec::new();
316
317 for event in source_file.syntax().preorder() {
318 match event {
319 WalkEvent::Enter(node) => {
320 if let Some(mut symbol) = to_file_symbol(&node, file_id) {
321 symbol.container_name = stack.last().cloned();
322
323 stack.push(symbol.name.clone());
324 symbols.push(symbol);
325 }
326 }
327
328 WalkEvent::Leave(node) => {
329 if to_symbol(&node).is_some() {
330 stack.pop();
331 }
332 }
333 }
334 }
335
336 symbols
337}
338
339fn to_symbol(node: &SyntaxNode) -> Option<(SmolStr, SyntaxNodePtr, TextRange)> {
340 fn decl<N: NameOwner>(node: N) -> Option<(SmolStr, SyntaxNodePtr, TextRange)> {
341 let name = node.name()?;
342 let name_range = name.syntax().text_range();
343 let name = name.text().clone();
344 let ptr = SyntaxNodePtr::new(node.syntax());
345
346 Some((name, ptr, name_range))
347 }
348 match_ast! {
349 match node {
350 ast::FnDef(it) => { decl(it) },
351 ast::StructDef(it) => { decl(it) },
352 ast::EnumDef(it) => { decl(it) },
353 ast::TraitDef(it) => { decl(it) },
354 ast::Module(it) => { decl(it) },
355 ast::TypeAliasDef(it) => { decl(it) },
356 ast::ConstDef(it) => { decl(it) },
357 ast::StaticDef(it) => { decl(it) },
358 _ => None,
359 }
360 }
361}
362
363fn to_file_symbol(node: &SyntaxNode, file_id: FileId) -> Option<FileSymbol> {
364 to_symbol(node).map(move |(name, ptr, name_range)| FileSymbol {
365 name,
366 ptr,
367 file_id,
368 name_range: Some(name_range),
369 container_name: None,
370 })
371}
372
373#[cfg(test)]
374mod tests {
375 use crate::{display::NavigationTarget, mock_analysis::single_file, Query};
376 use ra_syntax::{
377 SmolStr,
378 SyntaxKind::{FN_DEF, STRUCT_DEF},
379 };
380
381 #[test]
382 fn test_world_symbols_with_no_container() {
383 let code = r#"
384 enum FooInner { }
385 "#;
386
387 let mut symbols = get_symbols_matching(code, "FooInner");
388
389 let s = symbols.pop().unwrap();
390
391 assert_eq!(s.name(), "FooInner");
392 assert!(s.container_name().is_none());
393 }
394
395 #[test]
396 fn test_world_symbols_include_container_name() {
397 let code = r#"
398fn foo() {
399 enum FooInner { }
400}
401 "#;
402
403 let mut symbols = get_symbols_matching(code, "FooInner");
404
405 let s = symbols.pop().unwrap();
406
407 assert_eq!(s.name(), "FooInner");
408 assert_eq!(s.container_name(), Some(&SmolStr::new("foo")));
409
410 let code = r#"
411mod foo {
412 struct FooInner;
413}
414 "#;
415
416 let mut symbols = get_symbols_matching(code, "FooInner");
417
418 let s = symbols.pop().unwrap();
419
420 assert_eq!(s.name(), "FooInner");
421 assert_eq!(s.container_name(), Some(&SmolStr::new("foo")));
422 }
423
424 #[test]
425 fn test_world_symbols_are_case_sensitive() {
426 let code = r#"
427fn foo() {}
428
429struct Foo;
430 "#;
431
432 let symbols = get_symbols_matching(code, "Foo");
433
434 let fn_match = symbols.iter().find(|s| s.name() == "foo").map(|s| s.kind());
435 let struct_match = symbols.iter().find(|s| s.name() == "Foo").map(|s| s.kind());
436
437 assert_eq!(fn_match, Some(FN_DEF));
438 assert_eq!(struct_match, Some(STRUCT_DEF));
439 }
440
441 fn get_symbols_matching(text: &str, query: &str) -> Vec<NavigationTarget> {
442 let (analysis, _) = single_file(text);
443 analysis.symbol_search(Query::new(query.into())).unwrap()
444 }
445}
diff --git a/crates/ra_ide/src/lib.rs b/crates/ra_ide/src/lib.rs
index 66f365cc3..1527b27d4 100644
--- a/crates/ra_ide/src/lib.rs
+++ b/crates/ra_ide/src/lib.rs
@@ -10,7 +10,9 @@
10// For proving that RootDatabase is RefUnwindSafe. 10// For proving that RootDatabase is RefUnwindSafe.
11#![recursion_limit = "128"] 11#![recursion_limit = "128"]
12 12
13mod ide_db; 13mod ide_db {
14 pub use ra_ide_db::*;
15}
14 16
15mod db; 17mod db;
16pub mod mock_analysis; 18pub mod mock_analysis;
@@ -39,7 +41,6 @@ mod typing;
39mod matching_brace; 41mod matching_brace;
40mod display; 42mod display;
41mod inlay_hints; 43mod inlay_hints;
42mod wasm_shims;
43mod expand; 44mod expand;
44mod expand_macro; 45mod expand_macro;
45 46
diff --git a/crates/ra_ide/src/wasm_shims.rs b/crates/ra_ide/src/wasm_shims.rs
deleted file mode 100644
index 088cc9be4..000000000
--- a/crates/ra_ide/src/wasm_shims.rs
+++ /dev/null
@@ -1,19 +0,0 @@
1//! FIXME: write short doc here
2
3#[cfg(not(feature = "wasm"))]
4pub use std::time::Instant;
5
6#[cfg(feature = "wasm")]
7#[derive(Clone, Copy, Debug)]
8pub struct Instant;
9
10#[cfg(feature = "wasm")]
11impl Instant {
12 pub fn now() -> Self {
13 Self
14 }
15
16 pub fn elapsed(&self) -> std::time::Duration {
17 std::time::Duration::new(0, 0)
18 }
19}