aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_analysis/src/descriptors/module/nameres.rs
diff options
context:
space:
mode:
authorAleksey Kladov <[email protected]>2018-11-27 18:45:42 +0000
committerAleksey Kladov <[email protected]>2018-11-27 18:45:42 +0000
commitd659b7a2f03788eb0f4f15e3730bbf65a18ed818 (patch)
treec7112f1e0785606ab67b3df8d7a8b411909f54e1 /crates/ra_analysis/src/descriptors/module/nameres.rs
parent9f08341aa486ea59cb488635f19e960523568fb8 (diff)
start descriptors -> hir rename
Diffstat (limited to 'crates/ra_analysis/src/descriptors/module/nameres.rs')
-rw-r--r--crates/ra_analysis/src/descriptors/module/nameres.rs549
1 files changed, 0 insertions, 549 deletions
diff --git a/crates/ra_analysis/src/descriptors/module/nameres.rs b/crates/ra_analysis/src/descriptors/module/nameres.rs
deleted file mode 100644
index d2964f67f..000000000
--- a/crates/ra_analysis/src/descriptors/module/nameres.rs
+++ /dev/null
@@ -1,549 +0,0 @@
1//! Name resolution algorithm. The end result of the algorithm is `ItemMap`: a
2//! map with maps each module to it's scope: the set of items, visible in the
3//! module. That is, we only resolve imports here, name resolution of item
4//! bodies will be done in a separate step.
5//!
6//! Like Rustc, we use an interative per-crate algorithm: we start with scopes
7//! containing only directly defined items, and then iteratively resolve
8//! imports.
9//!
10//! To make this work nicely in the IDE scenarios, we place `InputModuleItems`
11//! in between raw syntax and name resolution. `InputModuleItems` are computed
12//! using only the module's syntax, and it is all directly defined items plus
13//! imports. The plain is to make `InputModuleItems` independent of local
14//! modifications (that is, typing inside a function shold not change IMIs),
15//! such that the results of name resolution can be preserved unless the module
16//! structure itself is modified.
17use std::{
18 sync::Arc,
19 time::Instant,
20 ops::Index,
21};
22
23use rustc_hash::FxHashMap;
24
25use ra_syntax::{
26 SyntaxNode, SyntaxNodeRef, TextRange,
27 SmolStr, SyntaxKind::{self, *},
28 ast::{self, ModuleItemOwner, AstNode}
29};
30
31use crate::{
32 Cancelable, FileId,
33 loc2id::{DefId, DefLoc},
34 descriptors::{
35 Path, PathKind,
36 DescriptorDatabase,
37 module::{ModuleId, ModuleTree, ModuleSourceNode},
38 },
39 input::SourceRootId,
40 arena::{Arena, Id}
41};
42
43/// Identifier of item within a specific file. This is stable over reparses, so
44/// it's OK to use it as a salsa key/value.
45pub(crate) type FileItemId = Id<SyntaxNode>;
46
47/// Maps item's `SyntaxNode`s to `FileItemId` and back.
48#[derive(Debug, PartialEq, Eq, Default)]
49pub(crate) struct FileItems {
50 arena: Arena<SyntaxNode>,
51}
52
53impl FileItems {
54 fn alloc(&mut self, item: SyntaxNode) -> FileItemId {
55 self.arena.alloc(item)
56 }
57 fn id_of(&self, item: SyntaxNodeRef) -> FileItemId {
58 let (id, _item) = self
59 .arena
60 .iter()
61 .find(|(_id, i)| i.borrowed() == item)
62 .unwrap();
63 id
64 }
65}
66
67impl Index<FileItemId> for FileItems {
68 type Output = SyntaxNode;
69 fn index(&self, idx: FileItemId) -> &SyntaxNode {
70 &self.arena[idx]
71 }
72}
73
74pub(crate) fn file_items(db: &impl DescriptorDatabase, file_id: FileId) -> Arc<FileItems> {
75 let source_file = db.file_syntax(file_id);
76 let source_file = source_file.borrowed();
77 let mut res = FileItems::default();
78 source_file
79 .syntax()
80 .descendants()
81 .filter_map(ast::ModuleItem::cast)
82 .map(|it| it.syntax().owned())
83 .for_each(|it| {
84 res.alloc(it);
85 });
86 Arc::new(res)
87}
88
89pub(crate) fn file_item(
90 db: &impl DescriptorDatabase,
91 file_id: FileId,
92 file_item_id: FileItemId,
93) -> SyntaxNode {
94 db._file_items(file_id)[file_item_id].clone()
95}
96
97/// Item map is the result of the name resolution. Item map contains, for each
98/// module, the set of visible items.
99#[derive(Default, Debug, PartialEq, Eq)]
100pub(crate) struct ItemMap {
101 pub(crate) per_module: FxHashMap<ModuleId, ModuleScope>,
102}
103
104#[derive(Debug, Default, PartialEq, Eq, Clone)]
105pub(crate) struct ModuleScope {
106 items: FxHashMap<SmolStr, Resolution>,
107}
108
109impl ModuleScope {
110 pub(crate) fn entries<'a>(&'a self) -> impl Iterator<Item = (&'a SmolStr, &Resolution)> + 'a {
111 self.items.iter()
112 }
113 pub(crate) fn get(&self, name: &SmolStr) -> Option<&Resolution> {
114 self.items.get(name)
115 }
116}
117
118/// A set of items and imports declared inside a module, without relation to
119/// other modules.
120///
121/// This stands in-between raw syntax and name resolution and alow us to avoid
122/// recomputing name res: if `InputModuleItems` are the same, we can avoid
123/// running name resolution.
124#[derive(Debug, Default, PartialEq, Eq)]
125pub(crate) struct InputModuleItems {
126 items: Vec<ModuleItem>,
127 imports: Vec<Import>,
128}
129
130#[derive(Debug, PartialEq, Eq)]
131struct ModuleItem {
132 id: FileItemId,
133 name: SmolStr,
134 kind: SyntaxKind,
135 vis: Vis,
136}
137
138#[derive(Debug, PartialEq, Eq)]
139enum Vis {
140 // Priv,
141 Other,
142}
143
144#[derive(Debug, Clone, PartialEq, Eq)]
145struct Import {
146 path: Path,
147 kind: ImportKind,
148}
149
150#[derive(Debug, Clone, Copy, PartialEq, Eq)]
151pub(crate) struct NamedImport {
152 file_item_id: FileItemId,
153 relative_range: TextRange,
154}
155
156impl NamedImport {
157 pub(crate) fn range(&self, db: &impl DescriptorDatabase, file_id: FileId) -> TextRange {
158 let syntax = db._file_item(file_id, self.file_item_id);
159 let offset = syntax.borrowed().range().start();
160 self.relative_range + offset
161 }
162}
163
164#[derive(Debug, Clone, PartialEq, Eq)]
165enum ImportKind {
166 Glob,
167 Named(NamedImport),
168}
169
170pub(crate) fn input_module_items(
171 db: &impl DescriptorDatabase,
172 source_root: SourceRootId,
173 module_id: ModuleId,
174) -> Cancelable<Arc<InputModuleItems>> {
175 let module_tree = db._module_tree(source_root)?;
176 let source = module_id.source(&module_tree);
177 let file_items = db._file_items(source.file_id());
178 let res = match source.resolve(db) {
179 ModuleSourceNode::SourceFile(it) => {
180 let items = it.borrowed().items();
181 InputModuleItems::new(&file_items, items)
182 }
183 ModuleSourceNode::Module(it) => {
184 let items = it
185 .borrowed()
186 .item_list()
187 .into_iter()
188 .flat_map(|it| it.items());
189 InputModuleItems::new(&file_items, items)
190 }
191 };
192 Ok(Arc::new(res))
193}
194
195pub(crate) fn item_map(
196 db: &impl DescriptorDatabase,
197 source_root: SourceRootId,
198) -> Cancelable<Arc<ItemMap>> {
199 let start = Instant::now();
200 let module_tree = db._module_tree(source_root)?;
201 let input = module_tree
202 .modules()
203 .map(|id| {
204 let items = db._input_module_items(source_root, id)?;
205 Ok((id, items))
206 })
207 .collect::<Cancelable<FxHashMap<_, _>>>()?;
208 let mut resolver = Resolver {
209 db: db,
210 input: &input,
211 source_root,
212 module_tree,
213 result: ItemMap::default(),
214 };
215 resolver.resolve()?;
216 let res = resolver.result;
217 let elapsed = start.elapsed();
218 log::info!("item_map: {:?}", elapsed);
219 Ok(Arc::new(res))
220}
221
222/// Resolution is basically `DefId` atm, but it should account for stuff like
223/// multiple namespaces, ambiguity and errors.
224#[derive(Debug, Clone, PartialEq, Eq)]
225pub(crate) struct Resolution {
226 /// None for unresolved
227 pub(crate) def_id: Option<DefId>,
228 /// ident by whitch this is imported into local scope.
229 pub(crate) import: Option<NamedImport>,
230}
231
232// #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
233// enum Namespace {
234// Types,
235// Values,
236// }
237
238// #[derive(Debug)]
239// struct PerNs<T> {
240// types: Option<T>,
241// values: Option<T>,
242// }
243
244impl InputModuleItems {
245 fn new<'a>(
246 file_items: &FileItems,
247 items: impl Iterator<Item = ast::ModuleItem<'a>>,
248 ) -> InputModuleItems {
249 let mut res = InputModuleItems::default();
250 for item in items {
251 res.add_item(file_items, item);
252 }
253 res
254 }
255
256 fn add_item(&mut self, file_items: &FileItems, item: ast::ModuleItem) -> Option<()> {
257 match item {
258 ast::ModuleItem::StructDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
259 ast::ModuleItem::EnumDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
260 ast::ModuleItem::FnDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
261 ast::ModuleItem::TraitDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
262 ast::ModuleItem::TypeDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
263 ast::ModuleItem::ImplItem(_) => {
264 // impls don't define items
265 }
266 ast::ModuleItem::UseItem(it) => self.add_use_item(file_items, it),
267 ast::ModuleItem::ExternCrateItem(_) => {
268 // TODO
269 }
270 ast::ModuleItem::ConstDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
271 ast::ModuleItem::StaticDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
272 ast::ModuleItem::Module(it) => self.items.push(ModuleItem::new(file_items, it)?),
273 }
274 Some(())
275 }
276
277 fn add_use_item(&mut self, file_items: &FileItems, item: ast::UseItem) {
278 let file_item_id = file_items.id_of(item.syntax());
279 let start_offset = item.syntax().range().start();
280 Path::expand_use_item(item, |path, range| {
281 let kind = match range {
282 None => ImportKind::Glob,
283 Some(range) => ImportKind::Named(NamedImport {
284 file_item_id,
285 relative_range: range - start_offset,
286 }),
287 };
288 self.imports.push(Import { kind, path })
289 })
290 }
291}
292
293impl ModuleItem {
294 fn new<'a>(file_items: &FileItems, item: impl ast::NameOwner<'a>) -> Option<ModuleItem> {
295 let name = item.name()?.text();
296 let kind = item.syntax().kind();
297 let vis = Vis::Other;
298 let id = file_items.id_of(item.syntax());
299 let res = ModuleItem {
300 id,
301 name,
302 kind,
303 vis,
304 };
305 Some(res)
306 }
307}
308
309struct Resolver<'a, DB> {
310 db: &'a DB,
311 input: &'a FxHashMap<ModuleId, Arc<InputModuleItems>>,
312 source_root: SourceRootId,
313 module_tree: Arc<ModuleTree>,
314 result: ItemMap,
315}
316
317impl<'a, DB> Resolver<'a, DB>
318where
319 DB: DescriptorDatabase,
320{
321 fn resolve(&mut self) -> Cancelable<()> {
322 for (&module_id, items) in self.input.iter() {
323 self.populate_module(module_id, items)
324 }
325
326 for &module_id in self.input.keys() {
327 crate::db::check_canceled(self.db)?;
328 self.resolve_imports(module_id);
329 }
330 Ok(())
331 }
332
333 fn populate_module(&mut self, module_id: ModuleId, input: &InputModuleItems) {
334 let file_id = module_id.source(&self.module_tree).file_id();
335
336 let mut module_items = ModuleScope::default();
337
338 for import in input.imports.iter() {
339 if let Some(name) = import.path.segments.iter().last() {
340 if let ImportKind::Named(import) = import.kind {
341 module_items.items.insert(
342 name.clone(),
343 Resolution {
344 def_id: None,
345 import: Some(import),
346 },
347 );
348 }
349 }
350 }
351
352 for item in input.items.iter() {
353 if item.kind == MODULE {
354 // handle submodules separatelly
355 continue;
356 }
357 let def_loc = DefLoc::Item {
358 file_id,
359 id: item.id,
360 };
361 let def_id = self.db.id_maps().def_id(def_loc);
362 let resolution = Resolution {
363 def_id: Some(def_id),
364 import: None,
365 };
366 module_items.items.insert(item.name.clone(), resolution);
367 }
368
369 for (name, mod_id) in module_id.children(&self.module_tree) {
370 let def_loc = DefLoc::Module {
371 id: mod_id,
372 source_root: self.source_root,
373 };
374 let def_id = self.db.id_maps().def_id(def_loc);
375 let resolution = Resolution {
376 def_id: Some(def_id),
377 import: None,
378 };
379 module_items.items.insert(name, resolution);
380 }
381
382 self.result.per_module.insert(module_id, module_items);
383 }
384
385 fn resolve_imports(&mut self, module_id: ModuleId) {
386 for import in self.input[&module_id].imports.iter() {
387 self.resolve_import(module_id, import);
388 }
389 }
390
391 fn resolve_import(&mut self, module_id: ModuleId, import: &Import) {
392 let ptr = match import.kind {
393 ImportKind::Glob => return,
394 ImportKind::Named(ptr) => ptr,
395 };
396
397 let mut curr = match import.path.kind {
398 // TODO: handle extern crates
399 PathKind::Plain => return,
400 PathKind::Self_ => module_id,
401 PathKind::Super => {
402 match module_id.parent(&self.module_tree) {
403 Some(it) => it,
404 // TODO: error
405 None => return,
406 }
407 }
408 PathKind::Crate => module_id.crate_root(&self.module_tree),
409 };
410
411 for (i, name) in import.path.segments.iter().enumerate() {
412 let is_last = i == import.path.segments.len() - 1;
413
414 let def_id = match self.result.per_module[&curr].items.get(name) {
415 None => return,
416 Some(res) => match res.def_id {
417 Some(it) => it,
418 None => return,
419 },
420 };
421
422 if !is_last {
423 curr = match self.db.id_maps().def_loc(def_id) {
424 DefLoc::Module { id, .. } => id,
425 _ => return,
426 }
427 } else {
428 self.update(module_id, |items| {
429 let res = Resolution {
430 def_id: Some(def_id),
431 import: Some(ptr),
432 };
433 items.items.insert(name.clone(), res);
434 })
435 }
436 }
437 }
438
439 fn update(&mut self, module_id: ModuleId, f: impl FnOnce(&mut ModuleScope)) {
440 let module_items = self.result.per_module.get_mut(&module_id).unwrap();
441 f(module_items)
442 }
443}
444
445#[cfg(test)]
446mod tests {
447 use crate::{
448 AnalysisChange,
449 mock_analysis::{MockAnalysis, analysis_and_position},
450 descriptors::{DescriptorDatabase, module::ModuleDescriptor},
451 input::FilesDatabase,
452};
453 use super::*;
454
455 fn item_map(fixture: &str) -> (Arc<ItemMap>, ModuleId) {
456 let (analysis, pos) = analysis_and_position(fixture);
457 let db = analysis.imp.db;
458 let source_root = db.file_source_root(pos.file_id);
459 let descr = ModuleDescriptor::guess_from_position(&*db, pos)
460 .unwrap()
461 .unwrap();
462 let module_id = descr.module_id;
463 (db._item_map(source_root).unwrap(), module_id)
464 }
465
466 #[test]
467 fn test_item_map() {
468 let (item_map, module_id) = item_map(
469 "
470 //- /lib.rs
471 mod foo;
472
473 use crate::foo::bar::Baz;
474 <|>
475
476 //- /foo/mod.rs
477 pub mod bar;
478
479 //- /foo/bar.rs
480 pub struct Baz;
481 ",
482 );
483 let name = SmolStr::from("Baz");
484 let resolution = &item_map.per_module[&module_id].items[&name];
485 assert!(resolution.def_id.is_some());
486 }
487
488 #[test]
489 fn typing_inside_a_function_should_not_invalidate_item_map() {
490 let mock_analysis = MockAnalysis::with_files(
491 "
492 //- /lib.rs
493 mod foo;
494
495 use crate::foo::bar::Baz;
496
497 fn foo() -> i32 {
498 1 + 1
499 }
500 //- /foo/mod.rs
501 pub mod bar;
502
503 //- /foo/bar.rs
504 pub struct Baz;
505 ",
506 );
507
508 let file_id = mock_analysis.id_of("/lib.rs");
509 let mut host = mock_analysis.analysis_host();
510
511 let source_root = host.analysis().imp.db.file_source_root(file_id);
512
513 {
514 let db = host.analysis().imp.db;
515 let events = db.log_executed(|| {
516 db._item_map(source_root).unwrap();
517 });
518 assert!(format!("{:?}", events).contains("_item_map"))
519 }
520
521 let mut change = AnalysisChange::new();
522
523 change.change_file(
524 file_id,
525 "
526 mod foo;
527
528 use crate::foo::bar::Baz;
529
530 fn foo() -> i32 { 92 }
531 "
532 .to_string(),
533 );
534
535 host.apply_change(change);
536
537 {
538 let db = host.analysis().imp.db;
539 let events = db.log_executed(|| {
540 db._item_map(source_root).unwrap();
541 });
542 assert!(
543 !format!("{:?}", events).contains("_item_map"),
544 "{:#?}",
545 events
546 )
547 }
548 }
549}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-19 18:23:27 +0100