aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_analysis/src/hir/module/nameres.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_analysis/src/hir/module/nameres.rs')
-rw-r--r--crates/ra_analysis/src/hir/module/nameres.rs446
1 files changed, 0 insertions, 446 deletions
diff --git a/crates/ra_analysis/src/hir/module/nameres.rs b/crates/ra_analysis/src/hir/module/nameres.rs
deleted file mode 100644
index d4ecc010b..000000000
--- a/crates/ra_analysis/src/hir/module/nameres.rs
+++ /dev/null
@@ -1,446 +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};
20
21use rustc_hash::FxHashMap;
22use ra_syntax::{
23 TextRange,
24 SmolStr, SyntaxKind::{self, *},
25 ast::{self, AstNode}
26};
27use ra_db::SourceRootId;
28
29use crate::{
30 Cancelable, FileId,
31 hir::{
32 DefId, DefLoc,
33 SourceItemId, SourceFileItemId, SourceFileItems,
34 Path, PathKind,
35 HirDatabase,
36 module::{ModuleId, ModuleTree},
37 },
38};
39
40/// Item map is the result of the name resolution. Item map contains, for each
41/// module, the set of visible items.
42#[derive(Default, Debug, PartialEq, Eq)]
43pub(crate) struct ItemMap {
44 pub(crate) per_module: FxHashMap<ModuleId, ModuleScope>,
45}
46
47#[derive(Debug, Default, PartialEq, Eq, Clone)]
48pub(crate) struct ModuleScope {
49 items: FxHashMap<SmolStr, Resolution>,
50}
51
52impl ModuleScope {
53 pub(crate) fn entries<'a>(&'a self) -> impl Iterator<Item = (&'a SmolStr, &Resolution)> + 'a {
54 self.items.iter()
55 }
56 pub(crate) fn get(&self, name: &SmolStr) -> Option<&Resolution> {
57 self.items.get(name)
58 }
59}
60
61/// A set of items and imports declared inside a module, without relation to
62/// other modules.
63///
64/// This stands in-between raw syntax and name resolution and alow us to avoid
65/// recomputing name res: if `InputModuleItems` are the same, we can avoid
66/// running name resolution.
67#[derive(Debug, Default, PartialEq, Eq)]
68pub(crate) struct InputModuleItems {
69 items: Vec<ModuleItem>,
70 imports: Vec<Import>,
71}
72
73#[derive(Debug, PartialEq, Eq)]
74struct ModuleItem {
75 id: SourceFileItemId,
76 name: SmolStr,
77 kind: SyntaxKind,
78 vis: Vis,
79}
80
81#[derive(Debug, PartialEq, Eq)]
82enum Vis {
83 // Priv,
84 Other,
85}
86
87#[derive(Debug, Clone, PartialEq, Eq)]
88struct Import {
89 path: Path,
90 kind: ImportKind,
91}
92
93#[derive(Debug, Clone, Copy, PartialEq, Eq)]
94pub(crate) struct NamedImport {
95 file_item_id: SourceFileItemId,
96 relative_range: TextRange,
97}
98
99impl NamedImport {
100 pub(crate) fn range(&self, db: &impl HirDatabase, file_id: FileId) -> TextRange {
101 let source_item_id = SourceItemId {
102 file_id,
103 item_id: self.file_item_id,
104 };
105 let syntax = db.file_item(source_item_id);
106 let offset = syntax.borrowed().range().start();
107 self.relative_range + offset
108 }
109}
110
111#[derive(Debug, Clone, PartialEq, Eq)]
112enum ImportKind {
113 Glob,
114 Named(NamedImport),
115}
116
117/// Resolution is basically `DefId` atm, but it should account for stuff like
118/// multiple namespaces, ambiguity and errors.
119#[derive(Debug, Clone, PartialEq, Eq)]
120pub(crate) struct Resolution {
121 /// None for unresolved
122 pub(crate) def_id: Option<DefId>,
123 /// ident by whitch this is imported into local scope.
124 pub(crate) import: Option<NamedImport>,
125}
126
127// #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
128// enum Namespace {
129// Types,
130// Values,
131// }
132
133// #[derive(Debug)]
134// struct PerNs<T> {
135// types: Option<T>,
136// values: Option<T>,
137// }
138
139impl InputModuleItems {
140 pub(in crate::hir) fn new<'a>(
141 file_items: &SourceFileItems,
142 items: impl Iterator<Item = ast::ModuleItem<'a>>,
143 ) -> InputModuleItems {
144 let mut res = InputModuleItems::default();
145 for item in items {
146 res.add_item(file_items, item);
147 }
148 res
149 }
150
151 fn add_item(&mut self, file_items: &SourceFileItems, item: ast::ModuleItem) -> Option<()> {
152 match item {
153 ast::ModuleItem::StructDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
154 ast::ModuleItem::EnumDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
155 ast::ModuleItem::FnDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
156 ast::ModuleItem::TraitDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
157 ast::ModuleItem::TypeDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
158 ast::ModuleItem::ImplItem(_) => {
159 // impls don't define items
160 }
161 ast::ModuleItem::UseItem(it) => self.add_use_item(file_items, it),
162 ast::ModuleItem::ExternCrateItem(_) => {
163 // TODO
164 }
165 ast::ModuleItem::ConstDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
166 ast::ModuleItem::StaticDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
167 ast::ModuleItem::Module(it) => self.items.push(ModuleItem::new(file_items, it)?),
168 }
169 Some(())
170 }
171
172 fn add_use_item(&mut self, file_items: &SourceFileItems, item: ast::UseItem) {
173 let file_item_id = file_items.id_of(item.syntax());
174 let start_offset = item.syntax().range().start();
175 Path::expand_use_item(item, |path, range| {
176 let kind = match range {
177 None => ImportKind::Glob,
178 Some(range) => ImportKind::Named(NamedImport {
179 file_item_id,
180 relative_range: range - start_offset,
181 }),
182 };
183 self.imports.push(Import { kind, path })
184 })
185 }
186}
187
188impl ModuleItem {
189 fn new<'a>(file_items: &SourceFileItems, item: impl ast::NameOwner<'a>) -> Option<ModuleItem> {
190 let name = item.name()?.text();
191 let kind = item.syntax().kind();
192 let vis = Vis::Other;
193 let id = file_items.id_of(item.syntax());
194 let res = ModuleItem {
195 id,
196 name,
197 kind,
198 vis,
199 };
200 Some(res)
201 }
202}
203
204pub(in crate::hir) struct Resolver<'a, DB> {
205 pub db: &'a DB,
206 pub input: &'a FxHashMap<ModuleId, Arc<InputModuleItems>>,
207 pub source_root: SourceRootId,
208 pub module_tree: Arc<ModuleTree>,
209 pub result: ItemMap,
210}
211
212impl<'a, DB> Resolver<'a, DB>
213where
214 DB: HirDatabase,
215{
216 pub(in crate::hir) fn resolve(mut self) -> Cancelable<ItemMap> {
217 for (&module_id, items) in self.input.iter() {
218 self.populate_module(module_id, items)
219 }
220
221 for &module_id in self.input.keys() {
222 self.db.check_canceled()?;
223 self.resolve_imports(module_id);
224 }
225 Ok(self.result)
226 }
227
228 fn populate_module(&mut self, module_id: ModuleId, input: &InputModuleItems) {
229 let file_id = module_id.source(&self.module_tree).file_id();
230
231 let mut module_items = ModuleScope::default();
232
233 for import in input.imports.iter() {
234 if let Some(name) = import.path.segments.iter().last() {
235 if let ImportKind::Named(import) = import.kind {
236 module_items.items.insert(
237 name.clone(),
238 Resolution {
239 def_id: None,
240 import: Some(import),
241 },
242 );
243 }
244 }
245 }
246
247 for item in input.items.iter() {
248 if item.kind == MODULE {
249 // handle submodules separatelly
250 continue;
251 }
252 let def_loc = DefLoc::Item {
253 source_item_id: SourceItemId {
254 file_id,
255 item_id: item.id,
256 },
257 };
258 let def_id = def_loc.id(self.db);
259 let resolution = Resolution {
260 def_id: Some(def_id),
261 import: None,
262 };
263 module_items.items.insert(item.name.clone(), resolution);
264 }
265
266 for (name, mod_id) in module_id.children(&self.module_tree) {
267 let def_loc = DefLoc::Module {
268 id: mod_id,
269 source_root: self.source_root,
270 };
271 let def_id = def_loc.id(self.db);
272 let resolution = Resolution {
273 def_id: Some(def_id),
274 import: None,
275 };
276 module_items.items.insert(name, resolution);
277 }
278
279 self.result.per_module.insert(module_id, module_items);
280 }
281
282 fn resolve_imports(&mut self, module_id: ModuleId) {
283 for import in self.input[&module_id].imports.iter() {
284 self.resolve_import(module_id, import);
285 }
286 }
287
288 fn resolve_import(&mut self, module_id: ModuleId, import: &Import) {
289 let ptr = match import.kind {
290 ImportKind::Glob => return,
291 ImportKind::Named(ptr) => ptr,
292 };
293
294 let mut curr = match import.path.kind {
295 // TODO: handle extern crates
296 PathKind::Plain => return,
297 PathKind::Self_ => module_id,
298 PathKind::Super => {
299 match module_id.parent(&self.module_tree) {
300 Some(it) => it,
301 // TODO: error
302 None => return,
303 }
304 }
305 PathKind::Crate => module_id.crate_root(&self.module_tree),
306 };
307
308 for (i, name) in import.path.segments.iter().enumerate() {
309 let is_last = i == import.path.segments.len() - 1;
310
311 let def_id = match self.result.per_module[&curr].items.get(name) {
312 None => return,
313 Some(res) => match res.def_id {
314 Some(it) => it,
315 None => return,
316 },
317 };
318
319 if !is_last {
320 curr = match def_id.loc(self.db) {
321 DefLoc::Module { id, .. } => id,
322 _ => return,
323 }
324 } else {
325 self.update(module_id, |items| {
326 let res = Resolution {
327 def_id: Some(def_id),
328 import: Some(ptr),
329 };
330 items.items.insert(name.clone(), res);
331 })
332 }
333 }
334 }
335
336 fn update(&mut self, module_id: ModuleId, f: impl FnOnce(&mut ModuleScope)) {
337 let module_items = self.result.per_module.get_mut(&module_id).unwrap();
338 f(module_items)
339 }
340}
341
342#[cfg(test)]
343mod tests {
344 use ra_db::FilesDatabase;
345 use crate::{
346 AnalysisChange,
347 mock_analysis::{MockAnalysis, analysis_and_position},
348 hir::{self, HirDatabase},
349};
350 use super::*;
351
352 fn item_map(fixture: &str) -> (Arc<ItemMap>, ModuleId) {
353 let (analysis, pos) = analysis_and_position(fixture);
354 let db = analysis.imp.db;
355 let source_root = db.file_source_root(pos.file_id);
356 let descr = hir::Module::guess_from_position(&*db, pos)
357 .unwrap()
358 .unwrap();
359 let module_id = descr.module_id;
360 (db.item_map(source_root).unwrap(), module_id)
361 }
362
363 #[test]
364 fn test_item_map() {
365 let (item_map, module_id) = item_map(
366 "
367 //- /lib.rs
368 mod foo;
369
370 use crate::foo::bar::Baz;
371 <|>
372
373 //- /foo/mod.rs
374 pub mod bar;
375
376 //- /foo/bar.rs
377 pub struct Baz;
378 ",
379 );
380 let name = SmolStr::from("Baz");
381 let resolution = &item_map.per_module[&module_id].items[&name];
382 assert!(resolution.def_id.is_some());
383 }
384
385 #[test]
386 fn typing_inside_a_function_should_not_invalidate_item_map() {
387 let mock_analysis = MockAnalysis::with_files(
388 "
389 //- /lib.rs
390 mod foo;
391
392 use crate::foo::bar::Baz;
393
394 fn foo() -> i32 {
395 1 + 1
396 }
397 //- /foo/mod.rs
398 pub mod bar;
399
400 //- /foo/bar.rs
401 pub struct Baz;
402 ",
403 );
404
405 let file_id = mock_analysis.id_of("/lib.rs");
406 let mut host = mock_analysis.analysis_host();
407
408 let source_root = host.analysis().imp.db.file_source_root(file_id);
409
410 {
411 let db = host.analysis().imp.db;
412 let events = db.log_executed(|| {
413 db.item_map(source_root).unwrap();
414 });
415 assert!(format!("{:?}", events).contains("item_map"))
416 }
417
418 let mut change = AnalysisChange::new();
419
420 change.change_file(
421 file_id,
422 "
423 mod foo;
424
425 use crate::foo::bar::Baz;
426
427 fn foo() -> i32 { 92 }
428 "
429 .to_string(),
430 );
431
432 host.apply_change(change);
433
434 {
435 let db = host.analysis().imp.db;
436 let events = db.log_executed(|| {
437 db.item_map(source_root).unwrap();
438 });
439 assert!(
440 !format!("{:?}", events).contains("_item_map"),
441 "{:#?}",
442 events
443 )
444 }
445 }
446}
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-18 23:42:38 +0100