aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir/src/module/nameres.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir/src/module/nameres.rs')
-rw-r--r--crates/ra_hir/src/module/nameres.rs509
1 files changed, 0 insertions, 509 deletions
diff --git a/crates/ra_hir/src/module/nameres.rs b/crates/ra_hir/src/module/nameres.rs
deleted file mode 100644
index 3c6851a0a..000000000
--- a/crates/ra_hir/src/module/nameres.rs
+++ /dev/null
@@ -1,509 +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::sync::Arc;
18
19use rustc_hash::FxHashMap;
20use ra_syntax::{
21 TextRange,
22 SyntaxKind::{self, *},
23 ast::{self, AstNode}
24};
25use ra_db::{SourceRootId, Cancelable, FileId};
26
27use crate::{
28 HirFileId,
29 DefId, DefLoc, DefKind,
30 SourceItemId, SourceFileItemId, SourceFileItems,
31 Path, PathKind,
32 HirDatabase, Crate,
33 Name, AsName,
34 module::{Module, ModuleId, ModuleTree},
35};
36
37/// Item map is the result of the name resolution. Item map contains, for each
38/// module, the set of visible items.
39// FIXME: currenty we compute item map per source-root. We should do it per crate instead.
40#[derive(Default, Debug, PartialEq, Eq)]
41pub struct ItemMap {
42 pub per_module: FxHashMap<ModuleId, ModuleScope>,
43}
44
45#[derive(Debug, Default, PartialEq, Eq, Clone)]
46pub struct ModuleScope {
47 items: FxHashMap<Name, Resolution>,
48}
49
50impl ModuleScope {
51 pub fn entries<'a>(&'a self) -> impl Iterator<Item = (&'a Name, &'a Resolution)> + 'a {
52 self.items.iter()
53 }
54 pub fn get(&self, name: &Name) -> Option<&Resolution> {
55 self.items.get(name)
56 }
57}
58
59/// A set of items and imports declared inside a module, without relation to
60/// other modules.
61///
62/// This stands in-between raw syntax and name resolution and alow us to avoid
63/// recomputing name res: if `InputModuleItems` are the same, we can avoid
64/// running name resolution.
65#[derive(Debug, Default, PartialEq, Eq)]
66pub struct InputModuleItems {
67 pub(crate) items: Vec<ModuleItem>,
68 imports: Vec<Import>,
69}
70
71#[derive(Debug, PartialEq, Eq)]
72pub(crate) struct ModuleItem {
73 pub(crate) id: SourceItemId,
74 pub(crate) name: Name,
75 kind: SyntaxKind,
76 vis: Vis,
77}
78
79#[derive(Debug, PartialEq, Eq)]
80enum Vis {
81 // Priv,
82 Other,
83}
84
85#[derive(Debug, Clone, PartialEq, Eq)]
86struct Import {
87 path: Path,
88 kind: ImportKind,
89}
90
91#[derive(Debug, Clone, Copy, PartialEq, Eq)]
92pub struct NamedImport {
93 pub file_item_id: SourceFileItemId,
94 pub relative_range: TextRange,
95}
96
97impl NamedImport {
98 // FIXME: this is only here for one use-case in completion. Seems like a
99 // pretty gross special case.
100 pub fn range(&self, db: &impl HirDatabase, file_id: FileId) -> TextRange {
101 let source_item_id = SourceItemId {
102 file_id: file_id.into(),
103 item_id: Some(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 struct Resolution {
121 /// None for unresolved
122 pub def_id: PerNs<DefId>,
123 /// ident by whitch this is imported into local scope.
124 pub import: Option<NamedImport>,
125}
126
127#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
128pub enum Namespace {
129 Types,
130 Values,
131}
132
133#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
134pub struct PerNs<T> {
135 pub types: Option<T>,
136 pub values: Option<T>,
137}
138
139impl<T> PerNs<T> {
140 pub fn none() -> PerNs<T> {
141 PerNs {
142 types: None,
143 values: None,
144 }
145 }
146
147 pub fn values(t: T) -> PerNs<T> {
148 PerNs {
149 types: None,
150 values: Some(t),
151 }
152 }
153
154 pub fn types(t: T) -> PerNs<T> {
155 PerNs {
156 types: Some(t),
157 values: None,
158 }
159 }
160
161 pub fn both(types: T, values: T) -> PerNs<T> {
162 PerNs {
163 types: Some(types),
164 values: Some(values),
165 }
166 }
167
168 pub fn is_none(&self) -> bool {
169 self.types.is_none() && self.values.is_none()
170 }
171
172 pub fn take(self, namespace: Namespace) -> Option<T> {
173 match namespace {
174 Namespace::Types => self.types,
175 Namespace::Values => self.values,
176 }
177 }
178
179 pub fn take_types(self) -> Option<T> {
180 self.types
181 }
182
183 pub fn take_values(self) -> Option<T> {
184 self.values
185 }
186
187 pub fn get(&self, namespace: Namespace) -> Option<&T> {
188 self.as_ref().take(namespace)
189 }
190
191 pub fn as_ref(&self) -> PerNs<&T> {
192 PerNs {
193 types: self.types.as_ref(),
194 values: self.values.as_ref(),
195 }
196 }
197
198 pub fn and_then<U>(self, f: impl Fn(T) -> Option<U>) -> PerNs<U> {
199 PerNs {
200 types: self.types.and_then(&f),
201 values: self.values.and_then(&f),
202 }
203 }
204
205 pub fn map<U>(self, f: impl Fn(T) -> U) -> PerNs<U> {
206 PerNs {
207 types: self.types.map(&f),
208 values: self.values.map(&f),
209 }
210 }
211}
212
213impl InputModuleItems {
214 pub(crate) fn add_item(
215 &mut self,
216 file_id: HirFileId,
217 file_items: &SourceFileItems,
218 item: ast::ModuleItem,
219 ) -> Option<()> {
220 match item {
221 ast::ModuleItem::StructDef(it) => {
222 self.items.push(ModuleItem::new(file_id, file_items, it)?)
223 }
224 ast::ModuleItem::EnumDef(it) => {
225 self.items.push(ModuleItem::new(file_id, file_items, it)?)
226 }
227 ast::ModuleItem::FnDef(it) => {
228 self.items.push(ModuleItem::new(file_id, file_items, it)?)
229 }
230 ast::ModuleItem::TraitDef(it) => {
231 self.items.push(ModuleItem::new(file_id, file_items, it)?)
232 }
233 ast::ModuleItem::TypeDef(it) => {
234 self.items.push(ModuleItem::new(file_id, file_items, it)?)
235 }
236 ast::ModuleItem::ImplBlock(_) => {
237 // impls don't define items
238 }
239 ast::ModuleItem::UseItem(it) => self.add_use_item(file_items, it),
240 ast::ModuleItem::ExternCrateItem(_) => {
241 // TODO
242 }
243 ast::ModuleItem::ConstDef(it) => {
244 self.items.push(ModuleItem::new(file_id, file_items, it)?)
245 }
246 ast::ModuleItem::StaticDef(it) => {
247 self.items.push(ModuleItem::new(file_id, file_items, it)?)
248 }
249 ast::ModuleItem::Module(it) => {
250 self.items.push(ModuleItem::new(file_id, file_items, it)?)
251 }
252 }
253 Some(())
254 }
255
256 fn add_use_item(&mut self, file_items: &SourceFileItems, item: ast::UseItem) {
257 let file_item_id = file_items.id_of_unchecked(item.syntax());
258 let start_offset = item.syntax().range().start();
259 Path::expand_use_item(item, |path, range| {
260 let kind = match range {
261 None => ImportKind::Glob,
262 Some(range) => ImportKind::Named(NamedImport {
263 file_item_id,
264 relative_range: range - start_offset,
265 }),
266 };
267 self.imports.push(Import { kind, path })
268 })
269 }
270}
271
272impl ModuleItem {
273 fn new<'a>(
274 file_id: HirFileId,
275 file_items: &SourceFileItems,
276 item: impl ast::NameOwner<'a>,
277 ) -> Option<ModuleItem> {
278 let name = item.name()?.as_name();
279 let kind = item.syntax().kind();
280 let vis = Vis::Other;
281 let item_id = Some(file_items.id_of_unchecked(item.syntax()));
282 let id = SourceItemId { file_id, item_id };
283 let res = ModuleItem {
284 id,
285 name,
286 kind,
287 vis,
288 };
289 Some(res)
290 }
291}
292
293pub(crate) struct Resolver<'a, DB> {
294 db: &'a DB,
295 input: &'a FxHashMap<ModuleId, Arc<InputModuleItems>>,
296 source_root: SourceRootId,
297 module_tree: Arc<ModuleTree>,
298 result: ItemMap,
299}
300
301impl<'a, DB> Resolver<'a, DB>
302where
303 DB: HirDatabase,
304{
305 pub(crate) fn new(
306 db: &'a DB,
307 input: &'a FxHashMap<ModuleId, Arc<InputModuleItems>>,
308 source_root: SourceRootId,
309 module_tree: Arc<ModuleTree>,
310 ) -> Resolver<'a, DB> {
311 Resolver {
312 db,
313 input,
314 source_root,
315 module_tree,
316 result: ItemMap::default(),
317 }
318 }
319
320 pub(crate) fn resolve(mut self) -> Cancelable<ItemMap> {
321 for (&module_id, items) in self.input.iter() {
322 self.populate_module(module_id, Arc::clone(items))?;
323 }
324
325 for &module_id in self.input.keys() {
326 self.db.check_canceled()?;
327 self.resolve_imports(module_id)?;
328 }
329 Ok(self.result)
330 }
331
332 fn populate_module(
333 &mut self,
334 module_id: ModuleId,
335 input: Arc<InputModuleItems>,
336 ) -> Cancelable<()> {
337 let mut module_items = ModuleScope::default();
338
339 // Populate extern crates prelude
340 {
341 let root_id = module_id.crate_root(&self.module_tree);
342 let file_id = root_id.source(&self.module_tree).file_id();
343 let crate_graph = self.db.crate_graph();
344 if let Some(crate_id) = crate_graph.crate_id_for_crate_root(file_id.as_original_file())
345 {
346 let krate = Crate::new(crate_id);
347 for dep in krate.dependencies(self.db) {
348 if let Some(module) = dep.krate.root_module(self.db)? {
349 let def_id = module.def_id(self.db);
350 self.add_module_item(
351 &mut module_items,
352 dep.name.clone(),
353 PerNs::types(def_id),
354 );
355 }
356 }
357 };
358 }
359 for import in input.imports.iter() {
360 if let Some(name) = import.path.segments.iter().last() {
361 if let ImportKind::Named(import) = import.kind {
362 module_items.items.insert(
363 name.clone(),
364 Resolution {
365 def_id: PerNs::none(),
366 import: Some(import),
367 },
368 );
369 }
370 }
371 }
372 // Populate explicitly declared items, except modules
373 for item in input.items.iter() {
374 if item.kind == MODULE {
375 continue;
376 }
377 // depending on the item kind, the location can define something in
378 // the values namespace, the types namespace, or both
379 let kind = DefKind::for_syntax_kind(item.kind);
380 let def_id = kind.map(|k| {
381 let def_loc = DefLoc {
382 kind: k,
383 source_root_id: self.source_root,
384 module_id,
385 source_item_id: item.id,
386 };
387 def_loc.id(self.db)
388 });
389 let resolution = Resolution {
390 def_id,
391 import: None,
392 };
393 module_items.items.insert(item.name.clone(), resolution);
394 }
395
396 // Populate modules
397 for (name, module_id) in module_id.children(&self.module_tree) {
398 let def_loc = DefLoc {
399 kind: DefKind::Module,
400 source_root_id: self.source_root,
401 module_id,
402 source_item_id: module_id.source(&self.module_tree).0,
403 };
404 let def_id = def_loc.id(self.db);
405 self.add_module_item(&mut module_items, name, PerNs::types(def_id));
406 }
407
408 self.result.per_module.insert(module_id, module_items);
409 Ok(())
410 }
411
412 fn add_module_item(&self, module_items: &mut ModuleScope, name: Name, def_id: PerNs<DefId>) {
413 let resolution = Resolution {
414 def_id,
415 import: None,
416 };
417 module_items.items.insert(name, resolution);
418 }
419
420 fn resolve_imports(&mut self, module_id: ModuleId) -> Cancelable<()> {
421 for import in self.input[&module_id].imports.iter() {
422 self.resolve_import(module_id, import)?;
423 }
424 Ok(())
425 }
426
427 fn resolve_import(&mut self, module_id: ModuleId, import: &Import) -> Cancelable<()> {
428 let ptr = match import.kind {
429 ImportKind::Glob => return Ok(()),
430 ImportKind::Named(ptr) => ptr,
431 };
432
433 let mut curr: ModuleId = match import.path.kind {
434 PathKind::Plain | PathKind::Self_ => module_id,
435 PathKind::Super => {
436 match module_id.parent(&self.module_tree) {
437 Some(it) => it,
438 // TODO: error
439 None => return Ok(()),
440 }
441 }
442 PathKind::Crate => module_id.crate_root(&self.module_tree),
443 };
444
445 for (i, name) in import.path.segments.iter().enumerate() {
446 let is_last = i == import.path.segments.len() - 1;
447
448 let def_id = match self.result.per_module[&curr].items.get(name) {
449 Some(res) if !res.def_id.is_none() => res.def_id,
450 _ => return Ok(()),
451 };
452
453 if !is_last {
454 let type_def_id = if let Some(d) = def_id.take(Namespace::Types) {
455 d
456 } else {
457 return Ok(());
458 };
459 curr = match type_def_id.loc(self.db) {
460 DefLoc {
461 kind: DefKind::Module,
462 module_id: target_module_id,
463 source_root_id,
464 ..
465 } => {
466 if source_root_id == self.source_root {
467 target_module_id
468 } else {
469 let module = Module::new(self.db, source_root_id, target_module_id)?;
470 let path = Path {
471 segments: import.path.segments[i + 1..].iter().cloned().collect(),
472 kind: PathKind::Crate,
473 };
474 let def_id = module.resolve_path(self.db, &path)?;
475 if !def_id.is_none() {
476 self.update(module_id, |items| {
477 let res = Resolution {
478 def_id: def_id,
479 import: Some(ptr),
480 };
481 items.items.insert(name.clone(), res);
482 })
483 }
484 return Ok(());
485 }
486 }
487 _ => return Ok(()),
488 }
489 } else {
490 self.update(module_id, |items| {
491 let res = Resolution {
492 def_id: def_id,
493 import: Some(ptr),
494 };
495 items.items.insert(name.clone(), res);
496 })
497 }
498 }
499 Ok(())
500 }
501
502 fn update(&mut self, module_id: ModuleId, f: impl FnOnce(&mut ModuleScope)) {
503 let module_items = self.result.per_module.get_mut(&module_id).unwrap();
504 f(module_items)
505 }
506}
507
508#[cfg(test)]
509mod tests;
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-09 10:22:43 +0000