aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_ide_db/src
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_ide_db/src')
-rw-r--r--crates/ra_ide_db/src/change.rs387
-rw-r--r--crates/ra_ide_db/src/defs.rs172
-rw-r--r--crates/ra_ide_db/src/feature_flags.rs71
-rw-r--r--crates/ra_ide_db/src/imports_locator.rs72
-rw-r--r--crates/ra_ide_db/src/lib.rs140
-rw-r--r--crates/ra_ide_db/src/line_index.rs284
-rw-r--r--crates/ra_ide_db/src/line_index_utils.rs341
-rw-r--r--crates/ra_ide_db/src/symbol_index.rs372
-rw-r--r--crates/ra_ide_db/src/wasm_shims.rs19
9 files changed, 1858 insertions, 0 deletions
diff --git a/crates/ra_ide_db/src/change.rs b/crates/ra_ide_db/src/change.rs
new file mode 100644
index 000000000..4668784d3
--- /dev/null
+++ b/crates/ra_ide_db/src/change.rs
@@ -0,0 +1,387 @@
1//! Defines a unit of change that can applied to a state of IDE to get the next
2//! state. Changes are transactional.
3
4use std::{fmt, sync::Arc, time};
5
6use ra_db::{
7 salsa::{Database, Durability, SweepStrategy},
8 CrateGraph, CrateId, FileId, RelativePathBuf, SourceDatabase, SourceDatabaseExt, SourceRoot,
9 SourceRootId,
10};
11use ra_prof::{memory_usage, profile, Bytes};
12use ra_syntax::SourceFile;
13#[cfg(not(feature = "wasm"))]
14use rayon::prelude::*;
15use rustc_hash::FxHashMap;
16
17use crate::{
18 symbol_index::{SymbolIndex, SymbolsDatabase},
19 DebugData, RootDatabase,
20};
21
22#[derive(Default)]
23pub struct AnalysisChange {
24 new_roots: Vec<(SourceRootId, bool)>,
25 roots_changed: FxHashMap<SourceRootId, RootChange>,
26 files_changed: Vec<(FileId, Arc<String>)>,
27 libraries_added: Vec<LibraryData>,
28 crate_graph: Option<CrateGraph>,
29 debug_data: DebugData,
30}
31
32impl fmt::Debug for AnalysisChange {
33 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
34 let mut d = fmt.debug_struct("AnalysisChange");
35 if !self.new_roots.is_empty() {
36 d.field("new_roots", &self.new_roots);
37 }
38 if !self.roots_changed.is_empty() {
39 d.field("roots_changed", &self.roots_changed);
40 }
41 if !self.files_changed.is_empty() {
42 d.field("files_changed", &self.files_changed.len());
43 }
44 if !self.libraries_added.is_empty() {
45 d.field("libraries_added", &self.libraries_added.len());
46 }
47 if !self.crate_graph.is_none() {
48 d.field("crate_graph", &self.crate_graph);
49 }
50 d.finish()
51 }
52}
53
54impl AnalysisChange {
55 pub fn new() -> AnalysisChange {
56 AnalysisChange::default()
57 }
58
59 pub fn add_root(&mut self, root_id: SourceRootId, is_local: bool) {
60 self.new_roots.push((root_id, is_local));
61 }
62
63 pub fn add_file(
64 &mut self,
65 root_id: SourceRootId,
66 file_id: FileId,
67 path: RelativePathBuf,
68 text: Arc<String>,
69 ) {
70 let file = AddFile { file_id, path, text };
71 self.roots_changed.entry(root_id).or_default().added.push(file);
72 }
73
74 pub fn change_file(&mut self, file_id: FileId, new_text: Arc<String>) {
75 self.files_changed.push((file_id, new_text))
76 }
77
78 pub fn remove_file(&mut self, root_id: SourceRootId, file_id: FileId, path: RelativePathBuf) {
79 let file = RemoveFile { file_id, path };
80 self.roots_changed.entry(root_id).or_default().removed.push(file);
81 }
82
83 pub fn add_library(&mut self, data: LibraryData) {
84 self.libraries_added.push(data)
85 }
86
87 pub fn set_crate_graph(&mut self, graph: CrateGraph) {
88 self.crate_graph = Some(graph);
89 }
90
91 pub fn set_debug_crate_name(&mut self, crate_id: CrateId, name: String) {
92 self.debug_data.crate_names.insert(crate_id, name);
93 }
94
95 pub fn set_debug_root_path(&mut self, source_root_id: SourceRootId, path: String) {
96 self.debug_data.root_paths.insert(source_root_id, path);
97 }
98}
99
100#[derive(Debug)]
101struct AddFile {
102 file_id: FileId,
103 path: RelativePathBuf,
104 text: Arc<String>,
105}
106
107#[derive(Debug)]
108struct RemoveFile {
109 file_id: FileId,
110 path: RelativePathBuf,
111}
112
113#[derive(Default)]
114struct RootChange {
115 added: Vec<AddFile>,
116 removed: Vec<RemoveFile>,
117}
118
119impl fmt::Debug for RootChange {
120 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
121 fmt.debug_struct("AnalysisChange")
122 .field("added", &self.added.len())
123 .field("removed", &self.removed.len())
124 .finish()
125 }
126}
127
128pub struct LibraryData {
129 root_id: SourceRootId,
130 root_change: RootChange,
131 symbol_index: SymbolIndex,
132}
133
134impl fmt::Debug for LibraryData {
135 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
136 f.debug_struct("LibraryData")
137 .field("root_id", &self.root_id)
138 .field("root_change", &self.root_change)
139 .field("n_symbols", &self.symbol_index.len())
140 .finish()
141 }
142}
143
144impl LibraryData {
145 pub fn prepare(
146 root_id: SourceRootId,
147 files: Vec<(FileId, RelativePathBuf, Arc<String>)>,
148 ) -> LibraryData {
149 let _p = profile("LibraryData::prepare");
150
151 #[cfg(not(feature = "wasm"))]
152 let iter = files.par_iter();
153 #[cfg(feature = "wasm")]
154 let iter = files.iter();
155
156 let symbol_index = SymbolIndex::for_files(iter.map(|(file_id, _, text)| {
157 let parse = SourceFile::parse(text);
158 (*file_id, parse)
159 }));
160 let mut root_change = RootChange::default();
161 root_change.added = files
162 .into_iter()
163 .map(|(file_id, path, text)| AddFile { file_id, path, text })
164 .collect();
165 LibraryData { root_id, root_change, symbol_index }
166 }
167}
168
169const GC_COOLDOWN: time::Duration = time::Duration::from_millis(100);
170
171impl RootDatabase {
172 pub fn request_cancellation(&mut self) {
173 let _p = profile("RootDatabase::request_cancellation");
174 self.salsa_runtime_mut().synthetic_write(Durability::LOW);
175 }
176
177 pub fn apply_change(&mut self, change: AnalysisChange) {
178 let _p = profile("RootDatabase::apply_change");
179 self.request_cancellation();
180 log::info!("apply_change {:?}", change);
181 if !change.new_roots.is_empty() {
182 let mut local_roots = Vec::clone(&self.local_roots());
183 for (root_id, is_local) in change.new_roots {
184 let root =
185 if is_local { SourceRoot::new_local() } else { SourceRoot::new_library() };
186 let durability = durability(&root);
187 self.set_source_root_with_durability(root_id, Arc::new(root), durability);
188 if is_local {
189 local_roots.push(root_id);
190 }
191 }
192 self.set_local_roots_with_durability(Arc::new(local_roots), Durability::HIGH);
193 }
194
195 for (root_id, root_change) in change.roots_changed {
196 self.apply_root_change(root_id, root_change);
197 }
198 for (file_id, text) in change.files_changed {
199 let source_root_id = self.file_source_root(file_id);
200 let source_root = self.source_root(source_root_id);
201 let durability = durability(&source_root);
202 self.set_file_text_with_durability(file_id, text, durability)
203 }
204 if !change.libraries_added.is_empty() {
205 let mut libraries = Vec::clone(&self.library_roots());
206 for library in change.libraries_added {
207 libraries.push(library.root_id);
208 self.set_source_root_with_durability(
209 library.root_id,
210 Arc::new(SourceRoot::new_library()),
211 Durability::HIGH,
212 );
213 self.set_library_symbols_with_durability(
214 library.root_id,
215 Arc::new(library.symbol_index),
216 Durability::HIGH,
217 );
218 self.apply_root_change(library.root_id, library.root_change);
219 }
220 self.set_library_roots_with_durability(Arc::new(libraries), Durability::HIGH);
221 }
222 if let Some(crate_graph) = change.crate_graph {
223 self.set_crate_graph_with_durability(Arc::new(crate_graph), Durability::HIGH)
224 }
225
226 Arc::make_mut(&mut self.debug_data).merge(change.debug_data)
227 }
228
229 fn apply_root_change(&mut self, root_id: SourceRootId, root_change: RootChange) {
230 let mut source_root = SourceRoot::clone(&self.source_root(root_id));
231 let durability = durability(&source_root);
232 for add_file in root_change.added {
233 self.set_file_text_with_durability(add_file.file_id, add_file.text, durability);
234 self.set_file_relative_path_with_durability(
235 add_file.file_id,
236 add_file.path.clone(),
237 durability,
238 );
239 self.set_file_source_root_with_durability(add_file.file_id, root_id, durability);
240 source_root.insert_file(add_file.path, add_file.file_id);
241 }
242 for remove_file in root_change.removed {
243 self.set_file_text_with_durability(remove_file.file_id, Default::default(), durability);
244 source_root.remove_file(&remove_file.path);
245 }
246 self.set_source_root_with_durability(root_id, Arc::new(source_root), durability);
247 }
248
249 pub fn maybe_collect_garbage(&mut self) {
250 if cfg!(feature = "wasm") {
251 return;
252 }
253
254 if self.last_gc_check.elapsed() > GC_COOLDOWN {
255 self.last_gc_check = crate::wasm_shims::Instant::now();
256 }
257 }
258
259 pub fn collect_garbage(&mut self) {
260 if cfg!(feature = "wasm") {
261 return;
262 }
263
264 let _p = profile("RootDatabase::collect_garbage");
265 self.last_gc = crate::wasm_shims::Instant::now();
266
267 let sweep = SweepStrategy::default().discard_values().sweep_all_revisions();
268
269 self.query(ra_db::ParseQuery).sweep(sweep);
270 self.query(hir::db::ParseMacroQuery).sweep(sweep);
271
272 // Macros do take significant space, but less then the syntax trees
273 // self.query(hir::db::MacroDefQuery).sweep(sweep);
274 // self.query(hir::db::MacroArgQuery).sweep(sweep);
275 // self.query(hir::db::MacroExpandQuery).sweep(sweep);
276
277 self.query(hir::db::AstIdMapQuery).sweep(sweep);
278
279 self.query(hir::db::BodyWithSourceMapQuery).sweep(sweep);
280
281 self.query(hir::db::ExprScopesQuery).sweep(sweep);
282 self.query(hir::db::DoInferQuery).sweep(sweep);
283 self.query(hir::db::BodyQuery).sweep(sweep);
284 }
285
286 pub fn per_query_memory_usage(&mut self) -> Vec<(String, Bytes)> {
287 let mut acc: Vec<(String, Bytes)> = vec![];
288 let sweep = SweepStrategy::default().discard_values().sweep_all_revisions();
289 macro_rules! sweep_each_query {
290 ($($q:path)*) => {$(
291 let before = memory_usage().allocated;
292 self.query($q).sweep(sweep);
293 let after = memory_usage().allocated;
294 let q: $q = Default::default();
295 let name = format!("{:?}", q);
296 acc.push((name, before - after));
297
298 let before = memory_usage().allocated;
299 self.query($q).sweep(sweep.discard_everything());
300 let after = memory_usage().allocated;
301 let q: $q = Default::default();
302 let name = format!("{:?} (deps)", q);
303 acc.push((name, before - after));
304 )*}
305 }
306 sweep_each_query![
307 // SourceDatabase
308 ra_db::ParseQuery
309 ra_db::SourceRootCratesQuery
310
311 // AstDatabase
312 hir::db::AstIdMapQuery
313 hir::db::InternMacroQuery
314 hir::db::MacroArgQuery
315 hir::db::MacroDefQuery
316 hir::db::ParseMacroQuery
317 hir::db::MacroExpandQuery
318
319 // DefDatabase
320 hir::db::RawItemsQuery
321 hir::db::ComputeCrateDefMapQuery
322 hir::db::StructDataQuery
323 hir::db::UnionDataQuery
324 hir::db::EnumDataQuery
325 hir::db::ImplDataQuery
326 hir::db::TraitDataQuery
327 hir::db::TypeAliasDataQuery
328 hir::db::FunctionDataQuery
329 hir::db::ConstDataQuery
330 hir::db::StaticDataQuery
331 hir::db::BodyWithSourceMapQuery
332 hir::db::BodyQuery
333 hir::db::ExprScopesQuery
334 hir::db::GenericParamsQuery
335 hir::db::AttrsQuery
336 hir::db::ModuleLangItemsQuery
337 hir::db::CrateLangItemsQuery
338 hir::db::LangItemQuery
339 hir::db::DocumentationQuery
340
341 // InternDatabase
342 hir::db::InternFunctionQuery
343 hir::db::InternStructQuery
344 hir::db::InternUnionQuery
345 hir::db::InternEnumQuery
346 hir::db::InternConstQuery
347 hir::db::InternStaticQuery
348 hir::db::InternTraitQuery
349 hir::db::InternTypeAliasQuery
350 hir::db::InternImplQuery
351
352 // HirDatabase
353 hir::db::DoInferQuery
354 hir::db::TyQuery
355 hir::db::ValueTyQuery
356 hir::db::ImplSelfTyQuery
357 hir::db::ImplTraitQuery
358 hir::db::FieldTypesQuery
359 hir::db::CallableItemSignatureQuery
360 hir::db::GenericPredicatesForParamQuery
361 hir::db::GenericPredicatesQuery
362 hir::db::GenericDefaultsQuery
363 hir::db::ImplsInCrateQuery
364 hir::db::ImplsForTraitQuery
365 hir::db::TraitSolverQuery
366 hir::db::InternTypeCtorQuery
367 hir::db::InternChalkImplQuery
368 hir::db::InternAssocTyValueQuery
369 hir::db::AssociatedTyDataQuery
370 hir::db::AssociatedTyValueQuery
371 hir::db::TraitSolveQuery
372 hir::db::TraitDatumQuery
373 hir::db::StructDatumQuery
374 hir::db::ImplDatumQuery
375 ];
376 acc.sort_by_key(|it| std::cmp::Reverse(it.1));
377 acc
378 }
379}
380
381fn durability(source_root: &SourceRoot) -> Durability {
382 if source_root.is_library {
383 Durability::HIGH
384 } else {
385 Durability::LOW
386 }
387}
diff --git a/crates/ra_ide_db/src/defs.rs b/crates/ra_ide_db/src/defs.rs
new file mode 100644
index 000000000..030f44f86
--- /dev/null
+++ b/crates/ra_ide_db/src/defs.rs
@@ -0,0 +1,172 @@
1//! `NameDefinition` keeps information about the element we want to search references for.
2//! The element is represented by `NameKind`. It's located inside some `container` and
3//! has a `visibility`, which defines a search scope.
4//! Note that the reference search is possible for not all of the classified items.
5
6// FIXME: this badly needs rename/rewrite (matklad, 2020-02-06).
7
8use hir::{
9 Adt, HasSource, ImplBlock, InFile, Local, MacroDef, Module, ModuleDef, SourceBinder,
10 StructField, TypeParam, VariantDef,
11};
12use ra_prof::profile;
13use ra_syntax::{
14 ast::{self, AstNode, VisibilityOwner},
15 match_ast,
16};
17
18use crate::RootDatabase;
19
20#[derive(Debug, PartialEq, Eq)]
21pub enum NameKind {
22 Macro(MacroDef),
23 StructField(StructField),
24 ModuleDef(ModuleDef),
25 SelfType(ImplBlock),
26 Local(Local),
27 TypeParam(TypeParam),
28}
29
30#[derive(PartialEq, Eq)]
31pub struct NameDefinition {
32 pub visibility: Option<ast::Visibility>,
33 /// FIXME: this doesn't really make sense. For example, builtin types don't
34 /// really have a module.
35 pub container: Module,
36 pub kind: NameKind,
37}
38
39pub fn classify_name(
40 sb: &mut SourceBinder<RootDatabase>,
41 name: InFile<&ast::Name>,
42) -> Option<NameDefinition> {
43 let _p = profile("classify_name");
44 let parent = name.value.syntax().parent()?;
45
46 match_ast! {
47 match parent {
48 ast::BindPat(it) => {
49 let src = name.with_value(it);
50 let local = sb.to_def(src)?;
51 Some(NameDefinition {
52 visibility: None,
53 container: local.module(sb.db),
54 kind: NameKind::Local(local),
55 })
56 },
57 ast::RecordFieldDef(it) => {
58 let src = name.with_value(it);
59 let field: hir::StructField = sb.to_def(src)?;
60 Some(from_struct_field(sb.db, field))
61 },
62 ast::Module(it) => {
63 let def = sb.to_def(name.with_value(it))?;
64 Some(from_module_def(sb.db, def.into(), None))
65 },
66 ast::StructDef(it) => {
67 let src = name.with_value(it);
68 let def: hir::Struct = sb.to_def(src)?;
69 Some(from_module_def(sb.db, def.into(), None))
70 },
71 ast::EnumDef(it) => {
72 let src = name.with_value(it);
73 let def: hir::Enum = sb.to_def(src)?;
74 Some(from_module_def(sb.db, def.into(), None))
75 },
76 ast::TraitDef(it) => {
77 let src = name.with_value(it);
78 let def: hir::Trait = sb.to_def(src)?;
79 Some(from_module_def(sb.db, def.into(), None))
80 },
81 ast::StaticDef(it) => {
82 let src = name.with_value(it);
83 let def: hir::Static = sb.to_def(src)?;
84 Some(from_module_def(sb.db, def.into(), None))
85 },
86 ast::EnumVariant(it) => {
87 let src = name.with_value(it);
88 let def: hir::EnumVariant = sb.to_def(src)?;
89 Some(from_module_def(sb.db, def.into(), None))
90 },
91 ast::FnDef(it) => {
92 let src = name.with_value(it);
93 let def: hir::Function = sb.to_def(src)?;
94 Some(from_module_def(sb.db, def.into(), None))
95 },
96 ast::ConstDef(it) => {
97 let src = name.with_value(it);
98 let def: hir::Const = sb.to_def(src)?;
99 Some(from_module_def(sb.db, def.into(), None))
100 },
101 ast::TypeAliasDef(it) => {
102 let src = name.with_value(it);
103 let def: hir::TypeAlias = sb.to_def(src)?;
104 Some(from_module_def(sb.db, def.into(), None))
105 },
106 ast::MacroCall(it) => {
107 let src = name.with_value(it);
108 let def = sb.to_def(src.clone())?;
109
110 let module = sb.to_module_def(src.file_id.original_file(sb.db))?;
111
112 Some(NameDefinition {
113 visibility: None,
114 container: module,
115 kind: NameKind::Macro(def),
116 })
117 },
118 ast::TypeParam(it) => {
119 let src = name.with_value(it);
120 let def = sb.to_def(src)?;
121 Some(NameDefinition {
122 visibility: None,
123 container: def.module(sb.db),
124 kind: NameKind::TypeParam(def),
125 })
126 },
127 _ => None,
128 }
129 }
130}
131
132pub fn from_struct_field(db: &RootDatabase, field: StructField) -> NameDefinition {
133 let kind = NameKind::StructField(field);
134 let parent = field.parent_def(db);
135 let container = parent.module(db);
136 let visibility = match parent {
137 VariantDef::Struct(s) => s.source(db).value.visibility(),
138 VariantDef::Union(e) => e.source(db).value.visibility(),
139 VariantDef::EnumVariant(e) => e.source(db).value.parent_enum().visibility(),
140 };
141 NameDefinition { kind, container, visibility }
142}
143
144pub fn from_module_def(
145 db: &RootDatabase,
146 def: ModuleDef,
147 module: Option<Module>,
148) -> NameDefinition {
149 let kind = NameKind::ModuleDef(def);
150 let (container, visibility) = match def {
151 ModuleDef::Module(it) => {
152 let container = it.parent(db).or_else(|| Some(it)).unwrap();
153 let visibility = it.declaration_source(db).and_then(|s| s.value.visibility());
154 (container, visibility)
155 }
156 ModuleDef::EnumVariant(it) => {
157 let container = it.module(db);
158 let visibility = it.source(db).value.parent_enum().visibility();
159 (container, visibility)
160 }
161 ModuleDef::Function(it) => (it.module(db), it.source(db).value.visibility()),
162 ModuleDef::Const(it) => (it.module(db), it.source(db).value.visibility()),
163 ModuleDef::Static(it) => (it.module(db), it.source(db).value.visibility()),
164 ModuleDef::Trait(it) => (it.module(db), it.source(db).value.visibility()),
165 ModuleDef::TypeAlias(it) => (it.module(db), it.source(db).value.visibility()),
166 ModuleDef::Adt(Adt::Struct(it)) => (it.module(db), it.source(db).value.visibility()),
167 ModuleDef::Adt(Adt::Union(it)) => (it.module(db), it.source(db).value.visibility()),
168 ModuleDef::Adt(Adt::Enum(it)) => (it.module(db), it.source(db).value.visibility()),
169 ModuleDef::BuiltinType(..) => (module.unwrap(), None),
170 };
171 NameDefinition { kind, container, visibility }
172}
diff --git a/crates/ra_ide_db/src/feature_flags.rs b/crates/ra_ide_db/src/feature_flags.rs
new file mode 100644
index 000000000..1b3cabf4d
--- /dev/null
+++ b/crates/ra_ide_db/src/feature_flags.rs
@@ -0,0 +1,71 @@
1//! See docs for `FeatureFlags`.
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_db/src/imports_locator.rs b/crates/ra_ide_db/src/imports_locator.rs
new file mode 100644
index 000000000..86383bcd0
--- /dev/null
+++ b/crates/ra_ide_db/src/imports_locator.rs
@@ -0,0 +1,72 @@
1//! This module contains an import search funcionality that is provided to the ra_assists module.
2//! Later, this should be moved away to a separate crate that is accessible from the ra_assists module.
3
4use hir::{db::HirDatabase, ModuleDef, SourceBinder};
5use ra_prof::profile;
6use ra_syntax::{ast, AstNode, SyntaxKind::NAME};
7
8use crate::{
9 defs::classify_name,
10 defs::NameKind,
11 symbol_index::{self, FileSymbol, Query},
12 RootDatabase,
13};
14
15pub struct ImportsLocator<'a> {
16 source_binder: SourceBinder<'a, RootDatabase>,
17}
18
19impl<'a> ImportsLocator<'a> {
20 pub fn new(db: &'a RootDatabase) -> Self {
21 Self { source_binder: SourceBinder::new(db) }
22 }
23
24 pub fn find_imports(&mut self, name_to_import: &str) -> Vec<ModuleDef> {
25 let _p = profile("search_for_imports");
26 let db = self.source_binder.db;
27
28 let project_results = {
29 let mut query = Query::new(name_to_import.to_string());
30 query.exact();
31 query.limit(40);
32 symbol_index::world_symbols(db, query)
33 };
34 let lib_results = {
35 let mut query = Query::new(name_to_import.to_string());
36 query.libs();
37 query.exact();
38 query.limit(40);
39 symbol_index::world_symbols(db, query)
40 };
41
42 project_results
43 .into_iter()
44 .chain(lib_results.into_iter())
45 .filter_map(|import_candidate| self.get_name_definition(db, &import_candidate))
46 .filter_map(|name_definition_to_import| match name_definition_to_import {
47 NameKind::ModuleDef(module_def) => Some(module_def),
48 _ => None,
49 })
50 .collect()
51 }
52
53 fn get_name_definition(
54 &mut self,
55 db: &impl HirDatabase,
56 import_candidate: &FileSymbol,
57 ) -> Option<NameKind> {
58 let _p = profile("get_name_definition");
59 let file_id = import_candidate.file_id.into();
60 let candidate_node = import_candidate.ptr.to_node(&db.parse_or_expand(file_id)?);
61 let candidate_name_node = if candidate_node.kind() != NAME {
62 candidate_node.children().find(|it| it.kind() == NAME)?
63 } else {
64 candidate_node
65 };
66 classify_name(
67 &mut self.source_binder,
68 hir::InFile { file_id, value: &ast::Name::cast(candidate_name_node)? },
69 )
70 .map(|it| it.kind)
71 }
72}
diff --git a/crates/ra_ide_db/src/lib.rs b/crates/ra_ide_db/src/lib.rs
new file mode 100644
index 000000000..877ac3c38
--- /dev/null
+++ b/crates/ra_ide_db/src/lib.rs
@@ -0,0 +1,140 @@
1//! This crate defines the core datastructure representing IDE state -- `RootDatabase`.
2//!
3//! It is mainly a `HirDatabase` for semantic analysis, plus a `SymbolsDatabase`, for fuzzy search.
4
5pub mod line_index;
6pub mod line_index_utils;
7pub mod feature_flags;
8pub mod symbol_index;
9pub mod change;
10pub mod defs;
11pub mod imports_locator;
12mod wasm_shims;
13
14use std::sync::Arc;
15
16use ra_db::{
17 salsa::{self, Database, Durability},
18 Canceled, CheckCanceled, CrateId, FileId, FileLoader, FileLoaderDelegate, RelativePath,
19 SourceDatabase, SourceRootId,
20};
21use rustc_hash::FxHashMap;
22
23use crate::{feature_flags::FeatureFlags, line_index::LineIndex, symbol_index::SymbolsDatabase};
24
25#[salsa::database(
26 ra_db::SourceDatabaseStorage,
27 ra_db::SourceDatabaseExtStorage,
28 LineIndexDatabaseStorage,
29 symbol_index::SymbolsDatabaseStorage,
30 hir::db::InternDatabaseStorage,
31 hir::db::AstDatabaseStorage,
32 hir::db::DefDatabaseStorage,
33 hir::db::HirDatabaseStorage
34)]
35#[derive(Debug)]
36pub struct RootDatabase {
37 runtime: salsa::Runtime<RootDatabase>,
38 pub feature_flags: Arc<FeatureFlags>,
39 pub(crate) debug_data: Arc<DebugData>,
40 pub last_gc: crate::wasm_shims::Instant,
41 pub last_gc_check: crate::wasm_shims::Instant,
42}
43
44impl FileLoader for RootDatabase {
45 fn file_text(&self, file_id: FileId) -> Arc<String> {
46 FileLoaderDelegate(self).file_text(file_id)
47 }
48 fn resolve_relative_path(
49 &self,
50 anchor: FileId,
51 relative_path: &RelativePath,
52 ) -> Option<FileId> {
53 FileLoaderDelegate(self).resolve_relative_path(anchor, relative_path)
54 }
55 fn relevant_crates(&self, file_id: FileId) -> Arc<Vec<CrateId>> {
56 FileLoaderDelegate(self).relevant_crates(file_id)
57 }
58}
59
60impl salsa::Database for RootDatabase {
61 fn salsa_runtime(&self) -> &salsa::Runtime<RootDatabase> {
62 &self.runtime
63 }
64 fn salsa_runtime_mut(&mut self) -> &mut salsa::Runtime<Self> {
65 &mut self.runtime
66 }
67 fn on_propagated_panic(&self) -> ! {
68 Canceled::throw()
69 }
70 fn salsa_event(&self, event: impl Fn() -> salsa::Event<RootDatabase>) {
71 match event().kind {
72 salsa::EventKind::DidValidateMemoizedValue { .. }
73 | salsa::EventKind::WillExecute { .. } => {
74 self.check_canceled();
75 }
76 _ => (),
77 }
78 }
79}
80
81impl Default for RootDatabase {
82 fn default() -> RootDatabase {
83 RootDatabase::new(None, FeatureFlags::default())
84 }
85}
86
87impl RootDatabase {
88 pub fn new(lru_capacity: Option<usize>, feature_flags: FeatureFlags) -> RootDatabase {
89 let mut db = RootDatabase {
90 runtime: salsa::Runtime::default(),
91 last_gc: crate::wasm_shims::Instant::now(),
92 last_gc_check: crate::wasm_shims::Instant::now(),
93 feature_flags: Arc::new(feature_flags),
94 debug_data: Default::default(),
95 };
96 db.set_crate_graph_with_durability(Default::default(), Durability::HIGH);
97 db.set_local_roots_with_durability(Default::default(), Durability::HIGH);
98 db.set_library_roots_with_durability(Default::default(), Durability::HIGH);
99 let lru_capacity = lru_capacity.unwrap_or(ra_db::DEFAULT_LRU_CAP);
100 db.query_mut(ra_db::ParseQuery).set_lru_capacity(lru_capacity);
101 db.query_mut(hir::db::ParseMacroQuery).set_lru_capacity(lru_capacity);
102 db.query_mut(hir::db::MacroExpandQuery).set_lru_capacity(lru_capacity);
103 db
104 }
105}
106
107impl salsa::ParallelDatabase for RootDatabase {
108 fn snapshot(&self) -> salsa::Snapshot<RootDatabase> {
109 salsa::Snapshot::new(RootDatabase {
110 runtime: self.runtime.snapshot(self),
111 last_gc: self.last_gc,
112 last_gc_check: self.last_gc_check,
113 feature_flags: Arc::clone(&self.feature_flags),
114 debug_data: Arc::clone(&self.debug_data),
115 })
116 }
117}
118
119#[salsa::query_group(LineIndexDatabaseStorage)]
120pub trait LineIndexDatabase: ra_db::SourceDatabase + CheckCanceled {
121 fn line_index(&self, file_id: FileId) -> Arc<LineIndex>;
122}
123
124fn line_index(db: &impl LineIndexDatabase, file_id: FileId) -> Arc<LineIndex> {
125 let text = db.file_text(file_id);
126 Arc::new(LineIndex::new(&*text))
127}
128
129#[derive(Debug, Default, Clone)]
130pub(crate) struct DebugData {
131 pub(crate) root_paths: FxHashMap<SourceRootId, String>,
132 pub(crate) crate_names: FxHashMap<CrateId, String>,
133}
134
135impl DebugData {
136 pub(crate) fn merge(&mut self, other: DebugData) {
137 self.root_paths.extend(other.root_paths.into_iter());
138 self.crate_names.extend(other.crate_names.into_iter());
139 }
140}
diff --git a/crates/ra_ide_db/src/line_index.rs b/crates/ra_ide_db/src/line_index.rs
new file mode 100644
index 000000000..452c87ac5
--- /dev/null
+++ b/crates/ra_ide_db/src/line_index.rs
@@ -0,0 +1,284 @@
1//! `LineIndex` maps flat `TextUnit` offsets into `(Line, Column)`
2//! representation.
3
4use ra_syntax::TextUnit;
5use rustc_hash::FxHashMap;
6use superslice::Ext;
7
8#[derive(Clone, Debug, PartialEq, Eq)]
9pub struct LineIndex {
10 pub(crate) newlines: Vec<TextUnit>,
11 pub(crate) utf16_lines: FxHashMap<u32, Vec<Utf16Char>>,
12}
13
14#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
15pub struct LineCol {
16 /// Zero-based
17 pub line: u32,
18 /// Zero-based
19 pub col_utf16: u32,
20}
21
22#[derive(Clone, Debug, Hash, PartialEq, Eq)]
23pub(crate) struct Utf16Char {
24 pub(crate) start: TextUnit,
25 pub(crate) end: TextUnit,
26}
27
28impl Utf16Char {
29 fn len(&self) -> TextUnit {
30 self.end - self.start
31 }
32}
33
34impl LineIndex {
35 pub fn new(text: &str) -> LineIndex {
36 let mut utf16_lines = FxHashMap::default();
37 let mut utf16_chars = Vec::new();
38
39 let mut newlines = vec![0.into()];
40 let mut curr_row = 0.into();
41 let mut curr_col = 0.into();
42 let mut line = 0;
43 for c in text.chars() {
44 curr_row += TextUnit::of_char(c);
45 if c == '\n' {
46 newlines.push(curr_row);
47
48 // Save any utf-16 characters seen in the previous line
49 if !utf16_chars.is_empty() {
50 utf16_lines.insert(line, utf16_chars);
51 utf16_chars = Vec::new();
52 }
53
54 // Prepare for processing the next line
55 curr_col = 0.into();
56 line += 1;
57 continue;
58 }
59
60 let char_len = TextUnit::of_char(c);
61 if char_len.to_usize() > 1 {
62 utf16_chars.push(Utf16Char { start: curr_col, end: curr_col + char_len });
63 }
64
65 curr_col += char_len;
66 }
67
68 // Save any utf-16 characters seen in the last line
69 if !utf16_chars.is_empty() {
70 utf16_lines.insert(line, utf16_chars);
71 }
72
73 LineIndex { newlines, utf16_lines }
74 }
75
76 pub fn line_col(&self, offset: TextUnit) -> LineCol {
77 let line = self.newlines.upper_bound(&offset) - 1;
78 let line_start_offset = self.newlines[line];
79 let col = offset - line_start_offset;
80
81 LineCol { line: line as u32, col_utf16: self.utf8_to_utf16_col(line as u32, col) as u32 }
82 }
83
84 pub fn offset(&self, line_col: LineCol) -> TextUnit {
85 //FIXME: return Result
86 let col = self.utf16_to_utf8_col(line_col.line, line_col.col_utf16);
87 self.newlines[line_col.line as usize] + col
88 }
89
90 fn utf8_to_utf16_col(&self, line: u32, mut col: TextUnit) -> usize {
91 if let Some(utf16_chars) = self.utf16_lines.get(&line) {
92 let mut correction = TextUnit::from_usize(0);
93 for c in utf16_chars {
94 if col >= c.end {
95 correction += c.len() - TextUnit::from_usize(1);
96 } else {
97 // From here on, all utf16 characters come *after* the character we are mapping,
98 // so we don't need to take them into account
99 break;
100 }
101 }
102
103 col -= correction;
104 }
105
106 col.to_usize()
107 }
108
109 fn utf16_to_utf8_col(&self, line: u32, col: u32) -> TextUnit {
110 let mut col: TextUnit = col.into();
111 if let Some(utf16_chars) = self.utf16_lines.get(&line) {
112 for c in utf16_chars {
113 if col >= c.start {
114 col += c.len() - TextUnit::from_usize(1);
115 } else {
116 // From here on, all utf16 characters come *after* the character we are mapping,
117 // so we don't need to take them into account
118 break;
119 }
120 }
121 }
122
123 col
124 }
125}
126
127#[cfg(test)]
128/// Simple reference implementation to use in proptests
129pub fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
130 let mut res = LineCol { line: 0, col_utf16: 0 };
131 for (i, c) in text.char_indices() {
132 if i + c.len_utf8() > offset.to_usize() {
133 // if it's an invalid offset, inside a multibyte char
134 // return as if it was at the start of the char
135 break;
136 }
137 if c == '\n' {
138 res.line += 1;
139 res.col_utf16 = 0;
140 } else {
141 res.col_utf16 += 1;
142 }
143 }
144 res
145}
146
147#[cfg(test)]
148mod test_line_index {
149 use super::*;
150 use proptest::{prelude::*, proptest};
151 use ra_text_edit::test_utils::{arb_offset, arb_text};
152
153 #[test]
154 fn test_line_index() {
155 let text = "hello\nworld";
156 let index = LineIndex::new(text);
157 assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 });
158 assert_eq!(index.line_col(1.into()), LineCol { line: 0, col_utf16: 1 });
159 assert_eq!(index.line_col(5.into()), LineCol { line: 0, col_utf16: 5 });
160 assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 0 });
161 assert_eq!(index.line_col(7.into()), LineCol { line: 1, col_utf16: 1 });
162 assert_eq!(index.line_col(8.into()), LineCol { line: 1, col_utf16: 2 });
163 assert_eq!(index.line_col(10.into()), LineCol { line: 1, col_utf16: 4 });
164 assert_eq!(index.line_col(11.into()), LineCol { line: 1, col_utf16: 5 });
165 assert_eq!(index.line_col(12.into()), LineCol { line: 1, col_utf16: 6 });
166
167 let text = "\nhello\nworld";
168 let index = LineIndex::new(text);
169 assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 });
170 assert_eq!(index.line_col(1.into()), LineCol { line: 1, col_utf16: 0 });
171 assert_eq!(index.line_col(2.into()), LineCol { line: 1, col_utf16: 1 });
172 assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 5 });
173 assert_eq!(index.line_col(7.into()), LineCol { line: 2, col_utf16: 0 });
174 }
175
176 fn arb_text_with_offset() -> BoxedStrategy<(TextUnit, String)> {
177 arb_text().prop_flat_map(|text| (arb_offset(&text), Just(text))).boxed()
178 }
179
180 fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
181 let mut res = LineCol { line: 0, col_utf16: 0 };
182 for (i, c) in text.char_indices() {
183 if i + c.len_utf8() > offset.to_usize() {
184 // if it's an invalid offset, inside a multibyte char
185 // return as if it was at the start of the char
186 break;
187 }
188 if c == '\n' {
189 res.line += 1;
190 res.col_utf16 = 0;
191 } else {
192 res.col_utf16 += 1;
193 }
194 }
195 res
196 }
197
198 proptest! {
199 #[test]
200 fn test_line_index_proptest((offset, text) in arb_text_with_offset()) {
201 let expected = to_line_col(&text, offset);
202 let line_index = LineIndex::new(&text);
203 let actual = line_index.line_col(offset);
204
205 assert_eq!(actual, expected);
206 }
207 }
208}
209
210#[cfg(test)]
211mod test_utf8_utf16_conv {
212 use super::*;
213
214 #[test]
215 fn test_char_len() {
216 assert_eq!('メ'.len_utf8(), 3);
217 assert_eq!('メ'.len_utf16(), 1);
218 }
219
220 #[test]
221 fn test_empty_index() {
222 let col_index = LineIndex::new(
223 "
224const C: char = 'x';
225",
226 );
227 assert_eq!(col_index.utf16_lines.len(), 0);
228 }
229
230 #[test]
231 fn test_single_char() {
232 let col_index = LineIndex::new(
233 "
234const C: char = 'メ';
235",
236 );
237
238 assert_eq!(col_index.utf16_lines.len(), 1);
239 assert_eq!(col_index.utf16_lines[&1].len(), 1);
240 assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() });
241
242 // UTF-8 to UTF-16, no changes
243 assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15);
244
245 // UTF-8 to UTF-16
246 assert_eq!(col_index.utf8_to_utf16_col(1, 22.into()), 20);
247
248 // UTF-16 to UTF-8, no changes
249 assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from(15));
250
251 // UTF-16 to UTF-8
252 assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from(21));
253 }
254
255 #[test]
256 fn test_string() {
257 let col_index = LineIndex::new(
258 "
259const C: char = \"メ メ\";
260",
261 );
262
263 assert_eq!(col_index.utf16_lines.len(), 1);
264 assert_eq!(col_index.utf16_lines[&1].len(), 2);
265 assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() });
266 assert_eq!(col_index.utf16_lines[&1][1], Utf16Char { start: 21.into(), end: 24.into() });
267
268 // UTF-8 to UTF-16
269 assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15);
270
271 assert_eq!(col_index.utf8_to_utf16_col(1, 21.into()), 19);
272 assert_eq!(col_index.utf8_to_utf16_col(1, 25.into()), 21);
273
274 assert!(col_index.utf8_to_utf16_col(2, 15.into()) == 15);
275
276 // UTF-16 to UTF-8
277 assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from_usize(15));
278
279 assert_eq!(col_index.utf16_to_utf8_col(1, 18), TextUnit::from_usize(20));
280 assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from_usize(23));
281
282 assert_eq!(col_index.utf16_to_utf8_col(2, 15), TextUnit::from_usize(15));
283 }
284}
diff --git a/crates/ra_ide_db/src/line_index_utils.rs b/crates/ra_ide_db/src/line_index_utils.rs
new file mode 100644
index 000000000..435b06511
--- /dev/null
+++ b/crates/ra_ide_db/src/line_index_utils.rs
@@ -0,0 +1,341 @@
1//! Code actions can specify desirable final position of the cursor.
2//!
3//! The position is specified as a `TextUnit` in the final file. We need to send
4//! it in `(Line, Column)` coordinate though. However, we only have a LineIndex
5//! for a file pre-edit!
6//!
7//! Code in this module applies this "to (Line, Column) after edit"
8//! transformation.
9
10use ra_syntax::{TextRange, TextUnit};
11use ra_text_edit::{AtomTextEdit, TextEdit};
12
13use crate::line_index::{LineCol, LineIndex, Utf16Char};
14
15pub fn translate_offset_with_edit(
16 line_index: &LineIndex,
17 offset: TextUnit,
18 text_edit: &TextEdit,
19) -> LineCol {
20 let mut state = Edits::from_text_edit(&text_edit);
21
22 let mut res = RunningLineCol::new();
23
24 macro_rules! test_step {
25 ($x:ident) => {
26 match &$x {
27 Step::Newline(n) => {
28 if offset < *n {
29 return res.to_line_col(offset);
30 } else {
31 res.add_line(*n);
32 }
33 }
34 Step::Utf16Char(x) => {
35 if offset < x.end() {
36 // if the offset is inside a multibyte char it's invalid
37 // clamp it to the start of the char
38 let clamp = offset.min(x.start());
39 return res.to_line_col(clamp);
40 } else {
41 res.adjust_col(*x);
42 }
43 }
44 }
45 };
46 }
47
48 for orig_step in LineIndexStepIter::from(line_index) {
49 loop {
50 let translated_step = state.translate_step(&orig_step);
51 match state.next_steps(&translated_step) {
52 NextSteps::Use => {
53 test_step!(translated_step);
54 break;
55 }
56 NextSteps::ReplaceMany(ns) => {
57 for n in ns {
58 test_step!(n);
59 }
60 break;
61 }
62 NextSteps::AddMany(ns) => {
63 for n in ns {
64 test_step!(n);
65 }
66 }
67 }
68 }
69 }
70
71 loop {
72 match state.next_inserted_steps() {
73 None => break,
74 Some(ns) => {
75 for n in ns {
76 test_step!(n);
77 }
78 }
79 }
80 }
81
82 res.to_line_col(offset)
83}
84
85#[derive(Debug, Clone)]
86enum Step {
87 Newline(TextUnit),
88 Utf16Char(TextRange),
89}
90
91#[derive(Debug)]
92struct LineIndexStepIter<'a> {
93 line_index: &'a LineIndex,
94 next_newline_idx: usize,
95 utf16_chars: Option<(TextUnit, std::slice::Iter<'a, Utf16Char>)>,
96}
97
98impl LineIndexStepIter<'_> {
99 fn from(line_index: &LineIndex) -> LineIndexStepIter {
100 let mut x = LineIndexStepIter { line_index, next_newline_idx: 0, utf16_chars: None };
101 // skip first newline since it's not real
102 x.next();
103 x
104 }
105}
106
107impl Iterator for LineIndexStepIter<'_> {
108 type Item = Step;
109 fn next(&mut self) -> Option<Step> {
110 self.utf16_chars
111 .as_mut()
112 .and_then(|(newline, x)| {
113 let x = x.next()?;
114 Some(Step::Utf16Char(TextRange::from_to(*newline + x.start, *newline + x.end)))
115 })
116 .or_else(|| {
117 let next_newline = *self.line_index.newlines.get(self.next_newline_idx)?;
118 self.utf16_chars = self
119 .line_index
120 .utf16_lines
121 .get(&(self.next_newline_idx as u32))
122 .map(|x| (next_newline, x.iter()));
123 self.next_newline_idx += 1;
124 Some(Step::Newline(next_newline))
125 })
126 }
127}
128
129#[derive(Debug)]
130struct OffsetStepIter<'a> {
131 text: &'a str,
132 offset: TextUnit,
133}
134
135impl Iterator for OffsetStepIter<'_> {
136 type Item = Step;
137 fn next(&mut self) -> Option<Step> {
138 let (next, next_offset) = self
139 .text
140 .char_indices()
141 .filter_map(|(i, c)| {
142 if c == '\n' {
143 let next_offset = self.offset + TextUnit::from_usize(i + 1);
144 let next = Step::Newline(next_offset);
145 Some((next, next_offset))
146 } else {
147 let char_len = TextUnit::of_char(c);
148 if char_len.to_usize() > 1 {
149 let start = self.offset + TextUnit::from_usize(i);
150 let end = start + char_len;
151 let next = Step::Utf16Char(TextRange::from_to(start, end));
152 let next_offset = end;
153 Some((next, next_offset))
154 } else {
155 None
156 }
157 }
158 })
159 .next()?;
160 let next_idx = (next_offset - self.offset).to_usize();
161 self.text = &self.text[next_idx..];
162 self.offset = next_offset;
163 Some(next)
164 }
165}
166
167#[derive(Debug)]
168enum NextSteps<'a> {
169 Use,
170 ReplaceMany(OffsetStepIter<'a>),
171 AddMany(OffsetStepIter<'a>),
172}
173
174#[derive(Debug)]
175struct TranslatedEdit<'a> {
176 delete: TextRange,
177 insert: &'a str,
178 diff: i64,
179}
180
181struct Edits<'a> {
182 edits: &'a [AtomTextEdit],
183 current: Option<TranslatedEdit<'a>>,
184 acc_diff: i64,
185}
186
187impl<'a> Edits<'a> {
188 fn from_text_edit(text_edit: &'a TextEdit) -> Edits<'a> {
189 let mut x = Edits { edits: text_edit.as_atoms(), current: None, acc_diff: 0 };
190 x.advance_edit();
191 x
192 }
193 fn advance_edit(&mut self) {
194 self.acc_diff += self.current.as_ref().map_or(0, |x| x.diff);
195 match self.edits.split_first() {
196 Some((next, rest)) => {
197 let delete = self.translate_range(next.delete);
198 let diff = next.insert.len() as i64 - next.delete.len().to_usize() as i64;
199 self.current = Some(TranslatedEdit { delete, insert: &next.insert, diff });
200 self.edits = rest;
201 }
202 None => {
203 self.current = None;
204 }
205 }
206 }
207
208 fn next_inserted_steps(&mut self) -> Option<OffsetStepIter<'a>> {
209 let cur = self.current.as_ref()?;
210 let res = Some(OffsetStepIter { offset: cur.delete.start(), text: &cur.insert });
211 self.advance_edit();
212 res
213 }
214
215 fn next_steps(&mut self, step: &Step) -> NextSteps {
216 let step_pos = match *step {
217 Step::Newline(n) => n,
218 Step::Utf16Char(r) => r.end(),
219 };
220 match &mut self.current {
221 Some(edit) => {
222 if step_pos <= edit.delete.start() {
223 NextSteps::Use
224 } else if step_pos <= edit.delete.end() {
225 let iter = OffsetStepIter { offset: edit.delete.start(), text: &edit.insert };
226 // empty slice to avoid returning steps again
227 edit.insert = &edit.insert[edit.insert.len()..];
228 NextSteps::ReplaceMany(iter)
229 } else {
230 let iter = OffsetStepIter { offset: edit.delete.start(), text: &edit.insert };
231 // empty slice to avoid returning steps again
232 edit.insert = &edit.insert[edit.insert.len()..];
233 self.advance_edit();
234 NextSteps::AddMany(iter)
235 }
236 }
237 None => NextSteps::Use,
238 }
239 }
240
241 fn translate_range(&self, range: TextRange) -> TextRange {
242 if self.acc_diff == 0 {
243 range
244 } else {
245 let start = self.translate(range.start());
246 let end = self.translate(range.end());
247 TextRange::from_to(start, end)
248 }
249 }
250
251 fn translate(&self, x: TextUnit) -> TextUnit {
252 if self.acc_diff == 0 {
253 x
254 } else {
255 TextUnit::from((x.to_usize() as i64 + self.acc_diff) as u32)
256 }
257 }
258
259 fn translate_step(&self, x: &Step) -> Step {
260 if self.acc_diff == 0 {
261 x.clone()
262 } else {
263 match *x {
264 Step::Newline(n) => Step::Newline(self.translate(n)),
265 Step::Utf16Char(r) => Step::Utf16Char(self.translate_range(r)),
266 }
267 }
268 }
269}
270
271#[derive(Debug)]
272struct RunningLineCol {
273 line: u32,
274 last_newline: TextUnit,
275 col_adjust: TextUnit,
276}
277
278impl RunningLineCol {
279 fn new() -> RunningLineCol {
280 RunningLineCol { line: 0, last_newline: TextUnit::from(0), col_adjust: TextUnit::from(0) }
281 }
282
283 fn to_line_col(&self, offset: TextUnit) -> LineCol {
284 LineCol {
285 line: self.line,
286 col_utf16: ((offset - self.last_newline) - self.col_adjust).into(),
287 }
288 }
289
290 fn add_line(&mut self, newline: TextUnit) {
291 self.line += 1;
292 self.last_newline = newline;
293 self.col_adjust = TextUnit::from(0);
294 }
295
296 fn adjust_col(&mut self, range: TextRange) {
297 self.col_adjust += range.len() - TextUnit::from(1);
298 }
299}
300
301#[cfg(test)]
302mod test {
303 use proptest::{prelude::*, proptest};
304 use ra_text_edit::test_utils::{arb_offset, arb_text_with_edit};
305 use ra_text_edit::TextEdit;
306
307 use crate::line_index;
308
309 use super::*;
310
311 #[derive(Debug)]
312 struct ArbTextWithEditAndOffset {
313 text: String,
314 edit: TextEdit,
315 edited_text: String,
316 offset: TextUnit,
317 }
318
319 fn arb_text_with_edit_and_offset() -> BoxedStrategy<ArbTextWithEditAndOffset> {
320 arb_text_with_edit()
321 .prop_flat_map(|x| {
322 let edited_text = x.edit.apply(&x.text);
323 let arb_offset = arb_offset(&edited_text);
324 (Just(x), Just(edited_text), arb_offset).prop_map(|(x, edited_text, offset)| {
325 ArbTextWithEditAndOffset { text: x.text, edit: x.edit, edited_text, offset }
326 })
327 })
328 .boxed()
329 }
330
331 proptest! {
332 #[test]
333 fn test_translate_offset_with_edit(x in arb_text_with_edit_and_offset()) {
334 let expected = line_index::to_line_col(&x.edited_text, x.offset);
335 let line_index = LineIndex::new(&x.text);
336 let actual = translate_offset_with_edit(&line_index, x.offset, &x.edit);
337
338 assert_eq!(actual, expected);
339 }
340 }
341}
diff --git a/crates/ra_ide_db/src/symbol_index.rs b/crates/ra_ide_db/src/symbol_index.rs
new file mode 100644
index 000000000..64ddf2f95
--- /dev/null
+++ b/crates/ra_ide_db/src/symbol_index.rs
@@ -0,0 +1,372 @@
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.
22
23use std::{
24 fmt,
25 hash::{Hash, Hasher},
26 mem,
27 sync::Arc,
28};
29
30use fst::{self, Streamer};
31use ra_db::{
32 salsa::{self, ParallelDatabase},
33 FileId, SourceDatabaseExt, SourceRootId,
34};
35use ra_syntax::{
36 ast::{self, NameOwner},
37 match_ast, AstNode, Parse, SmolStr, SourceFile,
38 SyntaxKind::{self, *},
39 SyntaxNode, SyntaxNodePtr, TextRange, WalkEvent,
40};
41#[cfg(not(feature = "wasm"))]
42use rayon::prelude::*;
43
44use crate::RootDatabase;
45
46#[derive(Debug)]
47pub struct Query {
48 query: String,
49 lowercased: String,
50 only_types: bool,
51 libs: bool,
52 exact: bool,
53 limit: usize,
54}
55
56impl Query {
57 pub fn new(query: String) -> Query {
58 let lowercased = query.to_lowercase();
59 Query {
60 query,
61 lowercased,
62 only_types: false,
63 libs: false,
64 exact: false,
65 limit: usize::max_value(),
66 }
67 }
68
69 pub fn only_types(&mut self) {
70 self.only_types = true;
71 }
72
73 pub fn libs(&mut self) {
74 self.libs = true;
75 }
76
77 pub fn exact(&mut self) {
78 self.exact = true;
79 }
80
81 pub fn limit(&mut self, limit: usize) {
82 self.limit = limit
83 }
84}
85
86#[salsa::query_group(SymbolsDatabaseStorage)]
87pub trait SymbolsDatabase: hir::db::HirDatabase {
88 fn file_symbols(&self, file_id: FileId) -> Arc<SymbolIndex>;
89 #[salsa::input]
90 fn library_symbols(&self, id: SourceRootId) -> Arc<SymbolIndex>;
91 /// The set of "local" (that is, from the current workspace) roots.
92 /// Files in local roots are assumed to change frequently.
93 #[salsa::input]
94 fn local_roots(&self) -> Arc<Vec<SourceRootId>>;
95 /// The set of roots for crates.io libraries.
96 /// Files in libraries are assumed to never change.
97 #[salsa::input]
98 fn library_roots(&self) -> Arc<Vec<SourceRootId>>;
99}
100
101fn file_symbols(db: &impl SymbolsDatabase, file_id: FileId) -> Arc<SymbolIndex> {
102 db.check_canceled();
103 let parse = db.parse(file_id);
104
105 let symbols = source_file_to_file_symbols(&parse.tree(), file_id);
106
107 // FIXME: add macros here
108
109 Arc::new(SymbolIndex::new(symbols))
110}
111
112pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec<FileSymbol> {
113 /// Need to wrap Snapshot to provide `Clone` impl for `map_with`
114 struct Snap(salsa::Snapshot<RootDatabase>);
115 impl Clone for Snap {
116 fn clone(&self) -> Snap {
117 Snap(self.0.snapshot())
118 }
119 }
120
121 let buf: Vec<Arc<SymbolIndex>> = if query.libs {
122 let snap = Snap(db.snapshot());
123 #[cfg(not(feature = "wasm"))]
124 let buf = db
125 .library_roots()
126 .par_iter()
127 .map_with(snap, |db, &lib_id| db.0.library_symbols(lib_id))
128 .collect();
129
130 #[cfg(feature = "wasm")]
131 let buf = db.library_roots().iter().map(|&lib_id| snap.0.library_symbols(lib_id)).collect();
132
133 buf
134 } else {
135 let mut files = Vec::new();
136 for &root in db.local_roots().iter() {
137 let sr = db.source_root(root);
138 files.extend(sr.walk())
139 }
140
141 let snap = Snap(db.snapshot());
142 #[cfg(not(feature = "wasm"))]
143 let buf =
144 files.par_iter().map_with(snap, |db, &file_id| db.0.file_symbols(file_id)).collect();
145
146 #[cfg(feature = "wasm")]
147 let buf = files.iter().map(|&file_id| snap.0.file_symbols(file_id)).collect();
148
149 buf
150 };
151 query.search(&buf)
152}
153
154pub fn index_resolve(db: &RootDatabase, name_ref: &ast::NameRef) -> Vec<FileSymbol> {
155 let name = name_ref.text();
156 let mut query = Query::new(name.to_string());
157 query.exact();
158 query.limit(4);
159 world_symbols(db, query)
160}
161
162#[derive(Default)]
163pub struct SymbolIndex {
164 symbols: Vec<FileSymbol>,
165 map: fst::Map,
166}
167
168impl fmt::Debug for SymbolIndex {
169 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
170 f.debug_struct("SymbolIndex").field("n_symbols", &self.symbols.len()).finish()
171 }
172}
173
174impl PartialEq for SymbolIndex {
175 fn eq(&self, other: &SymbolIndex) -> bool {
176 self.symbols == other.symbols
177 }
178}
179
180impl Eq for SymbolIndex {}
181
182impl Hash for SymbolIndex {
183 fn hash<H: Hasher>(&self, hasher: &mut H) {
184 self.symbols.hash(hasher)
185 }
186}
187
188impl SymbolIndex {
189 fn new(mut symbols: Vec<FileSymbol>) -> SymbolIndex {
190 fn cmp_key<'a>(s1: &'a FileSymbol) -> impl Ord + 'a {
191 unicase::Ascii::new(s1.name.as_str())
192 }
193 #[cfg(not(feature = "wasm"))]
194 symbols.par_sort_by(|s1, s2| cmp_key(s1).cmp(&cmp_key(s2)));
195
196 #[cfg(feature = "wasm")]
197 symbols.sort_by(|s1, s2| cmp_key(s1).cmp(&cmp_key(s2)));
198
199 let mut builder = fst::MapBuilder::memory();
200
201 let mut last_batch_start = 0;
202
203 for idx in 0..symbols.len() {
204 if symbols.get(last_batch_start).map(cmp_key) == symbols.get(idx + 1).map(cmp_key) {
205 continue;
206 }
207
208 let start = last_batch_start;
209 let end = idx + 1;
210 last_batch_start = end;
211
212 let key = symbols[start].name.as_str().to_lowercase();
213 let value = SymbolIndex::range_to_map_value(start, end);
214
215 builder.insert(key, value).unwrap();
216 }
217
218 let map = fst::Map::from_bytes(builder.into_inner().unwrap()).unwrap();
219 SymbolIndex { symbols, map }
220 }
221
222 pub fn len(&self) -> usize {
223 self.symbols.len()
224 }
225
226 pub fn memory_size(&self) -> usize {
227 self.map.as_fst().size() + self.symbols.len() * mem::size_of::<FileSymbol>()
228 }
229
230 #[cfg(not(feature = "wasm"))]
231 pub(crate) fn for_files(
232 files: impl ParallelIterator<Item = (FileId, Parse<ast::SourceFile>)>,
233 ) -> SymbolIndex {
234 let symbols = files
235 .flat_map(|(file_id, file)| source_file_to_file_symbols(&file.tree(), file_id))
236 .collect::<Vec<_>>();
237 SymbolIndex::new(symbols)
238 }
239
240 #[cfg(feature = "wasm")]
241 pub(crate) fn for_files(
242 files: impl Iterator<Item = (FileId, Parse<ast::SourceFile>)>,
243 ) -> SymbolIndex {
244 let symbols = files
245 .flat_map(|(file_id, file)| source_file_to_file_symbols(&file.tree(), file_id))
246 .collect::<Vec<_>>();
247 SymbolIndex::new(symbols)
248 }
249
250 fn range_to_map_value(start: usize, end: usize) -> u64 {
251 debug_assert![start <= (std::u32::MAX as usize)];
252 debug_assert![end <= (std::u32::MAX as usize)];
253
254 ((start as u64) << 32) | end as u64
255 }
256
257 fn map_value_to_range(value: u64) -> (usize, usize) {
258 let end = value as u32 as usize;
259 let start = (value >> 32) as usize;
260 (start, end)
261 }
262}
263
264impl Query {
265 pub(crate) fn search(self, indices: &[Arc<SymbolIndex>]) -> Vec<FileSymbol> {
266 let mut op = fst::map::OpBuilder::new();
267 for file_symbols in indices.iter() {
268 let automaton = fst::automaton::Subsequence::new(&self.lowercased);
269 op = op.add(file_symbols.map.search(automaton))
270 }
271 let mut stream = op.union();
272 let mut res = Vec::new();
273 while let Some((_, indexed_values)) = stream.next() {
274 if res.len() >= self.limit {
275 break;
276 }
277 for indexed_value in indexed_values {
278 let symbol_index = &indices[indexed_value.index];
279 let (start, end) = SymbolIndex::map_value_to_range(indexed_value.value);
280
281 for symbol in &symbol_index.symbols[start..end] {
282 if self.only_types && !is_type(symbol.ptr.kind()) {
283 continue;
284 }
285 if self.exact && symbol.name != self.query {
286 continue;
287 }
288 res.push(symbol.clone());
289 }
290 }
291 }
292 res
293 }
294}
295
296fn is_type(kind: SyntaxKind) -> bool {
297 match kind {
298 STRUCT_DEF | ENUM_DEF | TRAIT_DEF | TYPE_ALIAS_DEF => true,
299 _ => false,
300 }
301}
302
303/// The actual data that is stored in the index. It should be as compact as
304/// possible.
305#[derive(Debug, Clone, PartialEq, Eq, Hash)]
306pub struct FileSymbol {
307 pub file_id: FileId,
308 pub name: SmolStr,
309 pub ptr: SyntaxNodePtr,
310 pub name_range: Option<TextRange>,
311 pub container_name: Option<SmolStr>,
312}
313
314fn source_file_to_file_symbols(source_file: &SourceFile, file_id: FileId) -> Vec<FileSymbol> {
315 let mut symbols = Vec::new();
316 let mut stack = Vec::new();
317
318 for event in source_file.syntax().preorder() {
319 match event {
320 WalkEvent::Enter(node) => {
321 if let Some(mut symbol) = to_file_symbol(&node, file_id) {
322 symbol.container_name = stack.last().cloned();
323
324 stack.push(symbol.name.clone());
325 symbols.push(symbol);
326 }
327 }
328
329 WalkEvent::Leave(node) => {
330 if to_symbol(&node).is_some() {
331 stack.pop();
332 }
333 }
334 }
335 }
336
337 symbols
338}
339
340fn to_symbol(node: &SyntaxNode) -> Option<(SmolStr, SyntaxNodePtr, TextRange)> {
341 fn decl<N: NameOwner>(node: N) -> Option<(SmolStr, SyntaxNodePtr, TextRange)> {
342 let name = node.name()?;
343 let name_range = name.syntax().text_range();
344 let name = name.text().clone();
345 let ptr = SyntaxNodePtr::new(node.syntax());
346
347 Some((name, ptr, name_range))
348 }
349 match_ast! {
350 match node {
351 ast::FnDef(it) => { decl(it) },
352 ast::StructDef(it) => { decl(it) },
353 ast::EnumDef(it) => { decl(it) },
354 ast::TraitDef(it) => { decl(it) },
355 ast::Module(it) => { decl(it) },
356 ast::TypeAliasDef(it) => { decl(it) },
357 ast::ConstDef(it) => { decl(it) },
358 ast::StaticDef(it) => { decl(it) },
359 _ => None,
360 }
361 }
362}
363
364fn to_file_symbol(node: &SyntaxNode, file_id: FileId) -> Option<FileSymbol> {
365 to_symbol(node).map(move |(name, ptr, name_range)| FileSymbol {
366 name,
367 ptr,
368 file_id,
369 name_range: Some(name_range),
370 container_name: None,
371 })
372}
diff --git a/crates/ra_ide_db/src/wasm_shims.rs b/crates/ra_ide_db/src/wasm_shims.rs
new file mode 100644
index 000000000..7af9f9d9b
--- /dev/null
+++ b/crates/ra_ide_db/src/wasm_shims.rs
@@ -0,0 +1,19 @@
1//! A version of `std::time::Instant` that doesn't panic in WASM.
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}
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-26 15:05:27 +0100